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

Abstract

ATM 網路必須經由多點路由選擇演算法來提供有效的多點通訊服務，例如 ：視訊會議。我們先前曾提出一個以分割 (partition) 為基礎的最佳化 多點路由選擇演算法，確保在 ATM 網路上產生的負載或封包 (cell) 數 為最小。但由於高計算複雜度的限制，該演算法並無法有效應用於實際的 ATM 網路。本論文提出一結合類神經網路與分割技術的近似最佳化多點路 由選擇演算法。此演算法首先將網路多點路由選擇問題分割成子問題的集 合，並應用類神經網路預估每個子問題的最低負載。所有藉由分割產生的 子問題以預估之最低負載排序並加以處理。實驗數據顯示，藉由類神經網 路的負載預估，僅須分割有限數目的子問題就能獲得可接受甚至是最佳的 多點路由。此外，實驗數據亦顯示本演算法在子問題數目及模擬計算時間 上均優於我們之前所提出的最佳多點路由選擇演算法。 ATM networks are expected to efficiently provide multicast communication services(e.g., video conferencing) by means of a feasible multicast routing algorithm. Ourearlier research has presented an optimal partition-based multicast routing algorithmwhich guarantees a minimum number of cells to be generated in an ATM network.The limitation of the algorithm is the unviability for realistic ATM networks due to highcomputation complexity. In this paper, we propose a near- optimal Minimum-LoadMulticast Routing (MLMR) algorithm by means of the combination of the neuralnetwork and partition methods. The algorithm first partitions the search space of theproblem into a set of subproblems and neural network is applied to predict theminimum load of each subproblem generated. All subproblems are then processedby means of partition in increasing order of their expected minimum load.Experimental results show that by introducing the neural network technique, only limited number of subproblems are required to obtain an acceptable,even optimal, solution. Compared to the regular partition-based optimal minimum-loadmulticast routing algorithm, the MLMR algorithm exhibits great superiority both in thenumber of subproblems and the computation time.