基于覆蓋網(wǎng)絡(luò)的多路徑流量均衡研究

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

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

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

為了描述模型，定義如下符號(hào)，如表1所示。