标题: ATM 网路中多点通讯之最佳路由选择
Optimal Multicast Routing for ATM Networks
作者: 颜孟慈
Meng-Tzu Yen
杨启瑞
Maria C. Yuang
资讯科学与工程研究所
关键字: 多点通讯 ; 路由选择 ; 负载 ; 延迟时间 ; 演算法;Multicasting ; Routing ; Load ; Delay ; Algorithm
公开日期: 1994
摘要: ATM 网路必须经由多点路由选择演算法来提供有效的多点通讯服务,例如
:视讯会议。学术界已提出数种最低成本的多点路由选择演算法,但是这
些演算法的复杂度太高,以致于不适合用在 ATM网路上。本论文提出一最
佳多点路由选择演算法,此演算法确保在网路上产生的负载或细包数为最
小。假设每个链节的成本为一,则最低负载的多点路由选择演算法就变成
最低成本的多点路由选择演算法。本演算法藉由分割来决定最低成本的多
点路由。复杂度分析显示,本演算法优于 Balakrishnan的演算法-着名
的多点路由选择演算法之一,特别是在目地点个数远小于网路的情况下。
实验数据亦显示,本演算法实际上的效能更胜于其理论分析值。此外,根
据本演算法,吾人又提出两种适合不同需求的变形演算法。第一种是在最
小负载的限制下,找出满足最小[最大延迟时间]条件的多点路由,此演算
法可应用在对负载较敏感的网路上。第二种则是找出满足一定延迟时间的
最小负载多点路由,此演算法适合对延迟时间较敏感的应用。
ATM networks are required to efficiently provide multicast
communication services such as video conferencing by means of
feasible multicast routing algorithms. Several minimum- cost
multicast routing algorithms with various degrees of
computational complexity have been proposed. These algorithms ,
however, can be inappropriate for ATM networks due to their
high complexities. This thesis initially presents an optimal
multicast routing algorithm which guarantees the minimum load
or the minimum number of cells to be generated throughout the
network. The minimum-load multicast routing algorithm simply
corresponds to a minimum-cost multicast routing algorithm if
the cost of each link is assumed to be unity. This algorithm
efficiently determines the minimum-load multicast route by
means of partition. Complexity analysis shows its superiority
over the Balakrishnan's algorithm, one of promising multicast
routing algorithm especially when the number of destinations is
smaller than the size of the network. Experimental realistic
results further exhibit even better efficiency than its
theoretical results. Moreover, based on this multicast routing
algorithm, we propose two variants of the algorithm for
applications with different requirements. The first variant
determines the multicast route satisfying condition min[max
(delay)] subject to the constraint of the minimum load. The
second variant determines the minimum-load route subject to the
constraint of a delay bound. The former can be applied for load-
sensitive networks, whereas the latter can be applied for delay-
sensitive applications.
URI: http://140.113.39.130/cdrfb3/record/nctu/#NT830392026
http://hdl.handle.net/11536/58947
显示于类别:Thesis