?

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

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

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

?

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