一個最佳繞徑法的實驗

Abstract

隨著Internet的快速發展，有愈來愈多的電腦連接上網路。網路要能正常 運作的話，繞徑協定(routing protocol)扮演了相當重要的角色。一個良 好的繞徑協定必須確保網路能正確順暢地運作。但是一個繞徑協定究竟能 做到多好呢？這便是我們在這篇論文中想要試圖解決的問題。這個答案不 論在學術上或實用上都會有其重要的貢獻。 在這篇論文中，我們藉由修改最短路徑法(shortest path routing)提出 一套我們自己的方法，以求得一良好的封包平均延遲時間。這個方法首先 計算出網路上各個來源及目的節點間的數條最短路徑，接下來在來源到目 的節點間的各個中介節點中，封包都會根據當時的網路狀況重新被指定到 最短的路徑上，以因應網路上瞬息萬變的狀況。此外，重新指定路徑時只 能選擇之前所找出的數條路徑中的一條，所以不會造成任何的迴圈。根據 我們的實驗，此繞徑法的效能比單一最短路徑法好上許多，特別是當網路 的負載很重時。

As the rapid development of Internet, a growing number of computers are connected to the global computer network. For proper operation of the network, the routing protocols play an important role. A good routing protocol ensures the network to operate correctly and smoothly.But how well can a routing protocol perform ? This is the problem we try to solve in this thesis.The solution will be very valuable both academically and practically. In this thesis, we propose a method that can obtain a good average packet delay based on a modified shortest path routing. This method first calculates several shortest routes for each origin-destination pair in the network. Then in the course from the origin node to the destination node, a packet is rerouted to the shortest route in every node according to the traffic condition at that time so that it can adapt to the changing traffic. Besides, because the rerouting is restricted to the previously selected routes, no loop will be formed. According to our experiment, this routing approach performs much better than single shortest path routing, especially when the network is under heavy load.