研究生: |
陳一太 |
---|---|
論文名稱: |
多重路徑演算法的設計與分析 Design and Analysis of Multiple Disjoint Paths Protocol |
指導教授: | 陳俊祥 |
學位類別: |
碩士 Master |
系所名稱: |
資訊教育研究所 Graduate Institute of Information and Computer Education |
畢業學年度: | 82 |
語文別: | 中文 |
論文頁數: | 40 |
中文關鍵詞: | 多重路徑 、演算法 |
論文種類: | 學術論文 |
相關次數: | 點閱:139 下載:0 |
分享至: |
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報 |
就網路技術方面來看,兩個網路如何相互傳遞訊息(intercommunication)無疑是最重要的技術。如果沒有它,個個網路將如同分散在四處的資訊孤島。如何將訊息正確且有效率地送達給對方則取快決於路由研究算法(Routing Algorithm)。
傳統使用在ARPANET上的Routing Algorithm只有在兩個網路上找一條最短路徑,隨著網路應用軟體不斷發展,找一條路徑的演算法已逐漸無法滿足需求。因此多重路徑演算法在追求效率、穩定以及安全性的今天逐漸受到重視。
在本論文中,我們提一個在分散式非同步網路上的多重路徑演算法,且經由模擬實驗此演算法的確可以找出預期的多重路徑。
The core among the networking technologies is the interconnection part. Without it, the networks spread all over the world are still isolated information islands. Routing, finding a path from a point to another on the interconnected networks, plays one of the most important roles in providing connectiveites, on which information can be delivered correctly and hopefully efficiently. Single shortest path routing has been focused and utilized all the way since the old day of the ARPANET. Due to the significant expansion in the varieties of information applications and services on networking environments, single path routing has been challenged to its lack of efficiency, reliability, security, flexibility, and so forth. Therefore, the needs of deploying multiple paths for routing has arisen.
In this thesis, we present a distributed asynchronous algorithm for finding K node - or link - disjoint paths of minimum total length from a source to a destination for any K ≧ 1. This algorithm finds K disjoint paths in K iterations of the distributed shortest path algorithm. At each iteration, the algorithm applies a graph transformation derived from Suurballe [9, 10]. We show how to use the algorithm to maintain shortest sets of disjoint paths for any source - sink pair.