以波長路由為基礎之多波長分工網路上之高效率群播樹合併演算法設計
Other Title
Minimum-Cost Multicast Routing for Multi-Layered
Multimedia Distribution
Multimedia Distribution
Date Issued
2005
Date
2005
Author(s)
DOI
932213E002111
Abstract
In this report, we attempt to solve the problem of min-cost multi-cast
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 mul-timedia
distribution. This problem has been proved to be NP-hard. We pro-pose
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 net-works,
random networks, and scale-free networks. According to the experi-ment
results, the Lagrangean based heuristic can achieve up to 23.23% im-provement
compared to the M-T-M heuristic.
Publisher
臺北市：國立臺灣大學資訊管理學系暨研究所
Type
other
File(s)![Thumbnail Image]()
Loading...
Name
932213E002111.pdf
Size
268.83 KB
Format
Adobe PDF
Checksum
(MD5):5606a9e99366f6d8faaa974ce77bca4d