在非同步傳輸模式下限制節點分支之群播演算法則

Abstract

在未來的網路中,非同步傳輸模式(ATM)將扮演著極為重要之角色。同樣 的,群播(multicast)也將大量的被使用。因此,如何在非同步傳輸模式中 建立一群播樹也就成為了重要的問題。而節點分支個數的限制在上述的問 題中是一項重要的關鍵,節點延遲與封包遺失都可能是未考慮節點分支個 數,造成交換機不堪負荷的後果。在本論文中,我們探討了相關之演算法, 也提出一個考慮節點分支之演算法,此演算法不僅可以得到較少成本的群 播樹,而且是一分散式演算法且適用於動態的環境。並經由數值模擬的方 法驗證,本演算法極為有效。 In the future networks, ATM will be the most important technology and multicast connection will be the most popular mechanism. There are several restrictions for constructing a multicast tree in ATM network. Degree constraint is the most important one. If the degree constraint is ignored,the nodal delay and packet loss will be increased. Then, the performance of multicast tree will be degraded. In this thesis, we propose a distributed algorithm for multicast tree construction. This algorithm finds a minimum total link cost multicast tree under a degree constraint. We will compare the proposed algorithm with heuristic naive algorithm and Waxman's greedy algorithm. The results show that our algorithm is very efficient.