考慮端對端服務品質要求之近似最佳化群播允入控制與路由演算法
Other Title
Minimum-Cost Multicast Routing for Multi-Layered
Multimedia Distribution
Multimedia Distribution
Date Issued
2004
Date
2004
Author(s)
DOI
922213E002079
Abstract
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.
Publisher
臺北市：國立臺灣大學資訊管理學系暨研究所
Type
other
File(s)![Thumbnail Image]()
Loading...
Name
922213E002079.pdf
Size
201.1 KB
Format
Adobe PDF
Checksum
(MD5):cce4b30e0bce40d426b4e06a385632ea