網際網路之路徑選擇演算法的比較與分析

Abstract

自治系統是一群路徑器和網路的集合，其受單一的管理當局所控制，且使 用相同的路徑選擇協定。由各自治立系統之間透過路徑器的連接而形成的 一個虛擬網路，則稱成為網際網路。當網際網路不斷的成長時，如何從路 徑器本身至各目的地之間快速的找到有效的路徑，以便傳輸封包將更顯得 重要。在同一個自治系統內的各路徑器，將使用IGP 交換彼此的控制訊息 ，並且建立本身的架構路徑表。在TCP/IP網際網路的環境下，現今的 IGP 將所使用的路徑選擇演算法分為二大類：DVR 和LSR 兩種演算法。 DVR 主要功能是在路徑器之間交換彼此之控制訊息以更正自己的架構路徑 表。LSR 則是各路徑器傳遞獨立系統之實際網路拓撲的狀態後，計算出到 各目的地之架構選擇表。以DVR 為基礎的RIP 是目前使用最廣泛的IGP ， 以LSR 為基礎的OSPF 則是被新提議的IGP。在本論文中，將針對TCP/IP網 際網路環境下，RIP 和OSPF協定執行路徑選擇演算法時，所花費的頻寬消 耗和更正時間進行績效評估。對於各種網路拓撲及規模之自治系統，我們 將分析兩種路徑選擇演算法之效能，同時探討它們在網路發生異常時之反 應回覆能力。從而我們提出兩種改良型的路徑選擇演算法，RIP*與OSPF* ，以改善原RIP和OSPF。 最後，針對如何決定和製作網際網路之路徑選擇 演算法，將建議一系列的指導方針。 As Internet continues to grow in size, it is important to select the best routing path as quickly as possible. The Internet is composed of a set of Autonomous Systems (ASs) , where each AS consists of routers and networks under one administrative autho- rity. The Interior Gateway Protocols (IGPs) are used by Internet routers to build routing tables and distribute routing informat- ion inside an AS. In the Transmission Control Protocol/ Internet Protocol (TCP/IP) network, an IGP usually implements either the Distance-Vector Routing (DVR) or the Link-State Routing (LSR) algorithm. In DVR, a router knows the length of the shorest path from each of its neighbors to every destination in the Internet, and uses this information to compute its own distance and next router to each destination. In LSR, a router must know the enti- re network or the Internet topology because routes are computed locally. The DVR-based Routing Information Protocol (RIP) is the most popular IGP in use, where the LSR-based Open Shortest Path First (OSPF) is a proposed new IGP. In this thesis, RIP and OSPF are compared by using the performance criteria of bandwidth consumption(message size) and updating time (routing table updating time) . The efficiency and effectiveness of both routing algorithms are analyzed with resp- ect to different network topologies. Their robustnessis discuss- ed upon network failures. Two improved algorithms, RIP* and OSPF*, are proposed to overcome the shortcomings of RIP and OSPF*, respectively. Both RIP* and OSPF* perform much better than the the original algorithms. A list of guideline about how to choose and implement the Internet routing algorithms is also suggested.