最小延時分散式尋徑演算法之模擬

Abstract

隨著電腦網路的蓬勃發展，傳輸線速率大幅提升及交換元件處理整度的加快，如何使資料快速且正確地傳送到目的地，關鍵便在於路徑的選取。在選取路徑時，必須小心地選擇最適當的傳輸路徑，以避免有些路線負荷過重，而有些則是閒置的情形發生。而路徑選擇法便是在解決這個問題。 分散式路徑選擇法在應用上具有迅速、韌性及最佳效率等特性，因此較中央控制式路徑選擇法適用於連接節點眾多的電腦網路尋徑上。分散式路徑選擇法需要每條路線上的路線延遲梯度，這個值可利用極微小擾動分析的方法來估計。其中的擾動分析是於排隊系統上用來做線上估計系統性能敏感度或梯度的一種技巧。 本篇論文的目的是先推導GI/G/I排隊系統的極微小擾動分析估計方法，並將此估計方法應用於最小延時分散式尋徑演算法上。然後針對由個人電腦連接成的網路，利用NetBIOS進行資料傳輸，來模擬最小延時分散式尋徑演算法的運作情形。除了利用可解析分式得到之路線延遲梯度進行模擬外，也利用我們推導之極微小擾動分析方法估計到的值進行模擬。

The problem of obtaining efficient routing procedures for fast delivery of messages to ther destinations is of utmost importance in the design of modern computer networkd. By routing we mean the decisions regarding the outgoing link to be used for transmitting messages at each node. The distributed routing algorithm has the characteristic of reliability, toughness, and optimal efficiency over the applications. Therefore, it is more suitable than centralized facility to the problem of routing in complex networks. The distributed routing algorithm assumes knowledge of the link delay gradients for all links. And the perturbation analysis (PA) technique can be used to estimate the delay gradient. The PA technique was developed to provide on-line estimatio of performance sensitivities or gradients of queueing systems. The purpose of this paper, first, is to derive the infinitesimal perturbation analysis (IPA) estimator for GI/G/1 queueing system. Then we used the IPA technique to estimate the link delay gradients. Second, we used NetBIOS to transmit the messages and implemented the minimum delay distributed routing algorithm on simulated networks. We used the link delay gradients not only based on analytical formula but also IPA approach to implement the simulation.