ATM 網路中多點通訊之最佳路由選擇

Abstract

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.