Design and Analysis of Distributed QoS Multicast Routing Algorithms
Date Issued
2006
Date
2006
Author(s)
Huang, Tzu-Lun
DOI
en-US
Abstract
How to provide an efficient quality of service (QoS) routing in wide area networks (WAN) or in Internet has been an important research issue since about 1990. In the dissertation, we propose efficient heuristic-based distributed algorithms for addressing the problem of multicast routing with multiple QoS constraints. Two types of multicast routing problem are considered, bi-criteria routing and multi-criteria routing. In bi-criteria routing, we first review some existing algorithms, and point out errors in the well-known algorithm due to Jia [24] by two counter examples. We then propose an algorithm that improves Jia’s algorithm. A fix to Jia’s algorithm is given, and a generalization of his algorithm, including relaxation of routing constraints, allowing for dynamic updating of multicast group, and consideration of fault-tolerance and recovery in the routing network. In multi-criteria routing, we extend our result, based on our new algorithm of bi-criteria routing, to consider a generalized model of the QoS routing. We point out an inherent distinction between these two problems in terms of solution complexities. For both algorithms, we have made a computational analysis and given correctness proofs. To compare with many well-known algorithms/protocols, we perform simulations. Our simulation results indicate that our proposed algorithms have a better performance than existing ones.
Subjects
群播路由
分散式演算法
多條件限制路由
多條件限制
QoS 路由演算法
QoS 路由協定
容錯
multicast routing
distributed algorithm
constrained Steiner tree
multi-constrained routing
multiple constraints
QoS routing algorithm
QoS routing protocol
fault tolerant
NP-completeness
heuristics
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-95-D88526002-1.pdf
Size
23.31 KB
Format
Adobe PDF
Checksum
(MD5):2210684438e6d48dd867c73bc824bd77