多路徑負載平衡演算法:特徵、效能分析及改良

Abstract

Multihoming已被運用在許多的大型的機構和企業環境用以提升網路運作的穩定性，它除了可使企業網路併用多條聯外線路減少線路失敗率(link failure rate)並可以用許多條比專線成比低廉且不需重新佈線的最後一哩線路(last miles)如ADSL， Cable Modem， Power link ，和Wimax等來取代一條專線，用以減低線路成本。 在企業多條聯外路徑的Multihoming環境其量測及選擇路徑的方式已經有BGP， RON等相關研究加以探討，但是使用負載平衡方式來探討的研究還在發展。BGP和RON需要連接的ISP特別支援以交換大量路由訊息，使用線路負載平衡方式則是一種不需要ISP提供支援的方式，企業使用一個單一(standalone)的線路負載平衡網路設備來連接多條ISP線路，這個網路設備將負責量測線路的交通情況及分配流量。目前有許多商業設備提供這樣的功能，在這些設備裡面，負載平衡的演算法扮演了網路交通量測及分配的重要腳色。 負載平衡演算法有許多種類和形式，本篇論文提出了一個分析架構，以四個特性參數來分類及比較不同演算法，並使用實境模擬(emulation)的方式產生不同的traffic load來比較這些特性參數和演算法在頻寬聚合及處理網路擁塞情形下的效能。模擬的結果顯示了不同演算法的特性、適用的網路環境、及相對的弱點。 本研究的第二部分，針對負載平衡演算法用於端對端(end-to-end)的量測及流量分配遇到的三個問題: 即時性、量測成本過高及頻寬使用率，提出了一個解決方法WSDM。端對端的量測用於多路徑的網路架構主要在尋找最佳的線路。越即時的量測越能反映網路的情況進而避開有問題的線路，但是也可能產生過多的量測封包，所以「即時」和「精簡網路資源的使用」成為了兩難。此外，傳統在點對點量測及選擇線路的方法上都是使用某個量測時段中最佳的路徑來分配線路，這會造成其他線路頻寬使用的閒置。在這篇研究所提WSDM的方法，經過emulation的驗證，其使用權重方式能有效率的使用頻寬，並可用少量的資源達成即時點對點的量測。

Multihoming has been applied in many large enterprises and organizations. In order to increase the reliability or reduce the cost for a multihoming network, many accessing technologies are used in the so-called “last mile”, such as ADSL, cable modem, power link, and WiMAX. The measuring and path-selecting operations of multihoming networks that employ Border Gateway Protocol (BGP) and Resilient Overlay Network (RON) have been discussed in many studies, but few refer to using load-balanced mechanism. BGP and RON must exchange routing information among the inter-connected ISPs rapidly to report a link failure situation, while a load-balanced mechanism can be performed on standalone equipment without support from ISPs. Load-balanced algorithms play important rules in standalone equipment to measure traffic conditions and select the proper path. This study proposes an analytical model which uses four parameters to reveal the measuring and path-selecting behaviors of various load-balanced algorithms in multihoming networks. These load-balanced algorithms are compared under traffic aggregation and congestion conditions in an emulation environment. The emulation results display the characteristics, the network condition suitable for use, and the weakness of each algorithm. The second part of this research proposes an end-to-end measuring algorithm to resolve problems of applying load-balanced algorithms in end-to-end transmissions in a multihoming network. End-to-end measurement is performed in a multihoming network to locate the optimum path for a particular destination. Although this leads to more accurate network evaluations and fewer transmissions to failed links, more measurements occupy more multihoming equipment resources by using extra packets for end-to-end measurement, incurring heavy network traffic. Therefore, a trade-off exists between timely measurement and resource usage. Aside from this trade-off, bandwidth utilization is another issue in which the conventional end-to-end measurement approach only uses one optimal path within measuring interval idling links. This study also proposes a per-connection timely end-to-end measurement approach, called Weighted Self-Detected Measurement (WSDM), which consumes few resources. Our results further demonstrate that the proposed approach can effectively utilize bandwidth and keep clear of the outage path in an emulation environment.