https://scholars.lib.ntu.edu.tw/handle/123456789/105198
標題: | 考慮端對端服務品質要求之近似最佳化群播允入控制與路由演算法 | 其他標題: | Minimum-Cost Multicast Routing for Multi-Layered Multimedia Distribution | 作者: | 林永松 | 公開日期: | 2004 | 出版社: | 臺北市:國立臺灣大學資訊管理學系暨研究所 | 摘要: | In this report, we attempt to solve the problem of min-cost multicast routing for multi-layered multimedia distribution. More specifically, for (i) a given network topology (ii) the destinations of a multicast group and (iii) the bandwidth requirement of each destination, we attempt to find a feasible routing solution to minimize the cost of a multicast tree for multi-layered multimedia distribution. This problem has been proved to be NP-hard. We propose two adjustment procedures, namely: the tie breaking procedure and the drop-and-add procedure to enhance the solution quality of the modified T-M heuristic. We also formally model this problem as an optimization problem and apply the Lagrangean relaxation method and the subgradient method to solve the problem. Computational experiments are performed on regular networks, random networks, and scale-free networks. According to the experiment results, the Lagrangean based heuristic can achieve up to 23.23% improvement compared to the M-T-M heuristic. |
URI: | http://ntur.lib.ntu.edu.tw//handle/246246/18842 | 其他識別: | 922213E002079 | Rights: | 國立臺灣大學資訊管理學系暨研究所 |
顯示於: | 資訊管理學系 |
檔案 | 描述 | 大小 | 格式 | |
---|---|---|---|---|
922213E002079.pdf | 201.1 kB | Adobe PDF | 檢視/開啟 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。