基於遺傳演算法之高效率且容錯的非同步傳輸網路路由安排

Abstract

在本論文中，我們提出了一個基於遺傳演算法的有效非同步傳輸網路路由 安排方法。為了處理非同步傳輸網路之流量管理、擁塞控制及服務品質， 我們採用一個擴充式多階層網路路由拓樸型態，它包含一組多階層集中式 路由安排伺服器，以進行上述之管理。非同步傳輸網路是一個具有寬頻的 高速網路，它整合了各種資訊媒介於同一個網路系統之上。為了滿足多樣 媒介、不同性質的客戶、富變化性及有選擇性的多點連接方式，設計出一 個短的封包傳輸延遲時間及高容錯的非同步傳輸網路路由安排演算法是相 當重要的。藉由遺傳演算法，我們發展了一個有效且具容錯能力的非同步 傳輸網路路由安排方法來滿足網路上各式各樣需求。我們同時發展出數學 模式，以表示適切函數，此函數可以描述非同步傳輸網路的行為及特性。 我們的路由安排演算法可對數個參數，如封包延遲時間、頻寬及服務品質 ，同時進行最佳化，並且當一個可接受的網路拓樸型態產生時，我們可以 停止演算法的重覆迴圈。因此在短時間內我們就可以得到一個可接受的網 路拓樸型態。本篇論文的最大貢獻是在於我們為非同步傳輸網路設計了一 個高效率的路由安排演算法，它可在不需要任何備用光纖線路的情況下提 供容錯能力，並且減少封包延遲時間及提供有效的頻寬配置。我們以 C 語言進行基於遺傳演算法的網路路由安排模擬，分析其結果顯示，我們的 路由安排演算法比其它的演算法有較低的封包延遲時間、較佳的頻寬配置 及較高的網路可靠度。 In this thesis, we present an efficient ATM network routing method based on the genetic algorithm. We use an expanding hierarchical network routing topology which includes a set of hierarchical centralized routing servers for handling of traffic management, congestion control, and quality of services for an ATM network. The ATM network is a broadband, high speed network. It integrates various media into the same network. Thus, low cell delay and high fault tolerance ability are important for developing an ATM network routing algorithm to suit the diverse payload, dissimilar customers, and capriciously selectable multipoint connections. To meet these diversiform requirements, we develop an efficient and fault tolerant ATM network routing by the genetic algorithm. A mathematical model has been developed as the fitness function to characterize the behavior of an ATM network. Our genetic algorithm optimizes several coefficients such as delay, and quality of services simultaneously and stops the iteration loop when an acceptable network topology is found. Consequently, the derived network topology has short routing time. The main contribution of this thesis is designing an efficient routing algorithm for ATM network routing which is fault tolerant requiring any redundant optical fiber links, reduce cell delay time, and enhances bandwidth allocation. The network routing the genetic algorithm is simulated by C to analyze the figures merit using our approach. Simulation results show that our routing algorithm has lower cell delay, better bandwidth and reliability than other routing algorithm.