摘要：現(xiàn)有網(wǎng)絡發(fā)送數(shù)據(jù)都集中在一條最優(yōu)路徑上，使得網(wǎng)絡流量不均衡，擁塞不可避免。傳統(tǒng)的IP網(wǎng)絡難以拓展，文章在應用層上對覆蓋網(wǎng)絡進行流量均衡，利用覆蓋網(wǎng)絡之間的互動性給出了覆蓋網(wǎng)絡的多路徑流量均衡模型，在該模型上研究了輸入流量和輸出流量的分配算法，并通過仿真實驗說明了可以有效地減小網(wǎng)絡的端到端延遲。
關鍵詞：覆蓋網(wǎng)絡；多路徑路由；流量均衡

0 概述
    覆蓋網(wǎng)絡是以底層的物理網(wǎng)絡為基礎，在此基礎上建立的虛擬網(wǎng)絡。覆蓋網(wǎng)絡中的節(jié)點間的虛擬連接是邏輯上的，與底層的物理網(wǎng)相比，覆蓋網(wǎng)絡具有更好的靈活性。覆蓋網(wǎng)絡中的節(jié)點與傳統(tǒng)網(wǎng)絡中的節(jié)點相比，具有處理功能，即存儲一處理一轉(zhuǎn)發(fā)功能。多路徑路由是相對于單路徑的路由來說的，現(xiàn)在的Intemet中的路由使用的是單路徑路由，不支持多路徑路由。文獻中給出了覆蓋網(wǎng)絡上的負載均衡多播路由算法，文獻中對多路徑路由做了研究，文章指出了多路徑對吞吐量的增大，可靠性的提高有著良好的作用。文獻通過對網(wǎng)絡拓撲的連通性和節(jié)點間距離建模，比較了覆蓋路由相對普通的IP層路由的優(yōu)勢。文獻提出彈性覆蓋網(wǎng)絡(Resilience Overlay Networks，RON)，是MIT的And-ersen等人對多路徑覆蓋路由系統(tǒng)的最早的實現(xiàn)方案，通過不斷探測網(wǎng)絡的狀態(tài)，然后選擇一個中間節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)，實現(xiàn)系統(tǒng)對網(wǎng)絡鏈路失效的快速檢測和“繞行”。流量的均衡對于減少端到端時延，擁塞控制和充分利用網(wǎng)絡有著重要的意義。但是，上述文獻中并沒有給出覆蓋網(wǎng)絡的多路徑路由技術在網(wǎng)絡流量均衡中的應用，因此本文提出在覆蓋網(wǎng)絡上用多路徑路由技術對覆蓋網(wǎng)絡流量進行均衡的方法。
    本文在建立一種覆蓋網(wǎng)絡的多路徑流量均衡的模型的基礎上，引入一個網(wǎng)絡流量預測算法，通過網(wǎng)絡節(jié)點間的協(xié)作對網(wǎng)絡流量進行均衡。

1 覆蓋網(wǎng)絡的多路徑流量均衡模型
    相比現(xiàn)在研究較多的傳統(tǒng)單路徑網(wǎng)絡的流量均衡，本文采用的是多路徑方案對網(wǎng)絡流量進行均衡。相比于單路徑使網(wǎng)絡流量過于匯集，多路徑可以讓網(wǎng)絡流量分配到多條可行的路徑上，提高網(wǎng)絡的吞吐能力，降低網(wǎng)絡的時延。
    本文的模型建立基于如下假設：
    (1)覆蓋網(wǎng)絡上的節(jié)點具有足夠的數(shù)據(jù)處理能力和轉(zhuǎn)發(fā)能力，即節(jié)點數(shù)據(jù)處理和數(shù)據(jù)轉(zhuǎn)發(fā)與時延相比開銷很小，網(wǎng)絡的延遲主要產(chǎn)生在傳輸鏈路上。
    (2)覆蓋網(wǎng)絡上的節(jié)點的內(nèi)部包括不同類型的流量成分，這些流量成分可以按照一定的標準劃分，本文中按照目的節(jié)點來劃分流量。
    (3)覆蓋網(wǎng)絡可以通過一定的檢測機制檢測網(wǎng)絡的時延信息。
    本文中所用的路由是源路由，即所有的路由信息都是由源節(jié)點規(guī)劃完成，路徑上的節(jié)點只負責轉(zhuǎn)發(fā)，不對路徑作任何改變。源節(jié)點通過不斷探測得到鏈路信息，這樣節(jié)點就會擁有整個網(wǎng)絡拓撲，進而根據(jù)網(wǎng)絡的拓撲，鏈路的時延、帶寬等信息規(guī)劃出多條路徑。這些路徑構(gòu)成路徑集，本文中的路徑集中的路徑都是不相交的路徑(disljoint paths)。
    進入節(jié)點S且目的節(jié)點為t的流量可以劃分成兩個部分：節(jié)點S始發(fā)到目的節(jié)點t的流量和經(jīng)過節(jié)點S中轉(zhuǎn)而發(fā)往目的節(jié)點t的流量。多路徑的路由選擇過程從網(wǎng)絡流量角度來看分為兩步：第一步是各鏈路流入節(jié)點S的過程，第二步是通過選路機制進行多路徑的轉(zhuǎn)發(fā)過程，將流量分配到不同的路徑上去。為了說明此問題，下面給出圖示。

    為了描述模型，定義如下符號，如表1所示。

    設網(wǎng)絡用G(V，E)表示，其中V表示頂點，E表示頂點間的邊。
    定義輸入鏈路i的利用率：，這里表示流經(jīng)i鏈路流量與i鏈路容量的比值。
    根據(jù)前面的分析可知，節(jié)點S到t的總流量可以表示為：。
    延遲對于發(fā)送數(shù)據(jù)來說是衡量鏈路好壞的一個重要參數(shù)，本文通過考慮節(jié)點的端到端的延遲來分析網(wǎng)絡是否均衡。
    輸入排隊延遲為輸入鏈路的隊列長度除以鏈路的速度，
   
    上述定義的延遲在后面的仿真中將用到。

2 流量輸入的帶寬分配算法
    輸入的帶寬分配方法主要是解決輸入鏈路的不均衡利用問題。網(wǎng)絡均衡在數(shù)學上的表示是各輸入鏈路的帶寬利用率的方差最小。即使得最小，因此該問題可以轉(zhuǎn)化為以下問題：
    目標函數(shù)：求解輸入鏈路i上以t為目的節(jié)點的流量

    式(1)的含義是：輸入的流量要小于輸出的容量，以避免節(jié)點擁塞，因此將輸出鏈路的總?cè)萘孔鳛檩斎腈溌返目偭髁康募s束；輸入鏈路的總的流量要小于目的t的總流量。
   
    這里將其定義為平均鏈路利用率。
    式(1)條件下的最小值是存在的，但是問題的求解非常困難。因此，這里用一個近似算法來替代上式的求解。定義一個帶寬分配周期，將平均鏈路利用率作為參考值，根據(jù)上一周期的輸入鏈路利用率是否大于平均鏈路利用率而調(diào)整分配帶寬。設置一個鏈路i調(diào)整帶寬
   
   

3 多路徑流量輸出分配算法
    多路徑流量分配算法是指通過多路徑算法實現(xiàn)對節(jié)點的流量按照某些特定的要求分配到多條路徑上，并實現(xiàn)網(wǎng)絡性能的優(yōu)化。
    在此，為了實現(xiàn)節(jié)點流量的多路徑分配，定義一個分配概率矩陣。通過調(diào)節(jié)該矩陣實現(xiàn)流量的合理分配，使得流量的分配更加均衡。
   
    矩陣元素Piyj表示數(shù)據(jù)通過鏈路i到目的Vj的概率，在這里我們把其作為流量分配的比例。以t為目的節(jié)點，分配到鏈路i的流量為。
    上述分配的流量需要滿足以下約束：
   
    式(2)表示：分配到輸出鏈路上的流量要小于輸出鏈路的容量；輸出的總的流量應小于流到目的節(jié)點的總流量。
    網(wǎng)絡是動態(tài)的，通過分析多路徑網(wǎng)絡的實際運行過程可知，在很多情況下流量在一定時間段內(nèi)具有相對穩(wěn)定性，因此可以用預測算法對下一時段的流量進行預測。上式(2)求解計算開銷較大，下面通過預測算法來決定概率分配矩陣。
    對流量進行周期性的預測。設tf為預測周期，tp為探測周期，每到一個探測周期對網(wǎng)絡性能(時延、吞吐率、丟包率等)進行探測，預測周期是由若干個探測周期組成的。覆蓋網(wǎng)絡可以通過一定的檢測機制對網(wǎng)絡鏈路的時延狀況進行評估。
   
    式中：為第j個預測周期，對鏈路i分配流量比率的預測；fi為當前鏈路i的流量；為節(jié)點當前的總流量；β為權(quán)重因子，調(diào)節(jié)β的大小可以調(diào)節(jié)預測部分和當前部分在決策中的權(quán)重；為第j-1個預測周期，鏈路i的預測流量；為第j-1個預測周期，節(jié)點的預測總流量用上述預測的概率來作為分配矩陣中的概率，即令。

4 仿真實驗
    通過NS2的GT-ITM的Waxman模型模擬出如下圖的網(wǎng)絡拓撲，節(jié)點數(shù)為10，設節(jié)點鏈路的容量都是10Mb／s，輸入鏈路的速率為50M／s。圖2實驗拓撲圖。

    本文通過分析時延特性來說明對網(wǎng)絡性能的改善。網(wǎng)絡中的節(jié)點加上負載大小是隨機的，以N2到N4為例來分析端到端時延特性，通過對比單路徑和多路徑的端到端的時延來實現(xiàn)。單路徑表示N2-NO-N4，多路徑包括路徑1和路徑2，其中路徑1表示N2-N6-N4，路徑2表示N2-N0-N4?？梢钥吹酵ㄟ^多路徑路徑1和路徑2相比于單路徑可以有效地減少端到端的延遲。路徑1和路徑2的端到端延遲相差不大，說明負載在網(wǎng)絡中是較為均衡的。

5 結(jié)語
    傳統(tǒng)的網(wǎng)絡只負責報文的盡力而為的轉(zhuǎn)發(fā)服務，網(wǎng)絡中流量按照單條路徑轉(zhuǎn)發(fā)，各節(jié)點之間缺少相互的協(xié)調(diào)工作。本文通過覆蓋網(wǎng)絡模型的建立，對網(wǎng)絡流量進行預測并通過多路徑傳輸，使得節(jié)點的端到端延遲大大減小，為解決流量均衡問題提供了一條新思路。