基于層疊網(wǎng)技術(shù)的互聯(lián)網(wǎng)基礎(chǔ)設(shè)施若干問題之研究.pdf

1、隨著互聯(lián)網(wǎng)技術(shù)的普及，計算機(jī)網(wǎng)絡(luò)對于人們的影響不斷加深，互聯(lián)網(wǎng)應(yīng)用的更新速度可謂同新月異。與此形成鮮明對比的是，今天的互聯(lián)網(wǎng)基礎(chǔ)設(shè)施與其誕生初期相比并沒有太大本質(zhì)上的區(qū)別。伴隨互聯(lián)網(wǎng)規(guī)模的不斷擴(kuò)大以及新興應(yīng)用的不斷涌現(xiàn)，原有基礎(chǔ)設(shè)施的一些不足之處開始變得越來越明顯。例如：BGP路由機(jī)制存在路由故障恢復(fù)時間長以及路徑膨脹等問題，可能嚴(yán)重影響端到端的傳輸性能；對組播等多元化傳輸模式支持的缺乏以及對QoS的保障的缺失則大大增加了網(wǎng)絡(luò)應(yīng)用在這些

2、方面的實現(xiàn)難度。而另一方面，過去人們一直習(xí)慣把基礎(chǔ)設(shè)施與終端節(jié)點(diǎn)(主機(jī)或各類服務(wù)器)對立起來，由基礎(chǔ)設(shè)施提供接入及數(shù)據(jù)傳輸?shù)然A(chǔ)服務(wù)，而終端節(jié)點(diǎn)只負(fù)責(zé)網(wǎng)絡(luò)應(yīng)用程序的運(yùn)行。這個模型意味著要改造互聯(lián)網(wǎng)基礎(chǔ)設(shè)施必將波及原有大量的網(wǎng)絡(luò)設(shè)備(如所有的路由器)，需要大量的投入，在應(yīng)用前景尚不明朗的情況下，網(wǎng)絡(luò)運(yùn)營商在面對新技術(shù)時往往采取比較保守的態(tài)度。這也促成了互聯(lián)網(wǎng)基礎(chǔ)設(shè)施發(fā)展的遲滯狀態(tài)。 層疊網(wǎng)(overlay network)，的出現(xiàn)

3、使人們對互聯(lián)網(wǎng)基礎(chǔ)設(shè)施有了新的認(rèn)識。層疊網(wǎng)是指網(wǎng)絡(luò)中的一部分節(jié)點(diǎn)為了實現(xiàn)某一特定目標(biāo)，利用原有網(wǎng)絡(luò)所提供的基礎(chǔ)服務(wù)自發(fā)形成的上層網(wǎng)絡(luò)。近年來，以彈性層疊網(wǎng)(resilient overlay network)和層疊網(wǎng)組播(overlay multicast)為代表的層疊網(wǎng)應(yīng)用技術(shù)開始興起。雖然這些層疊網(wǎng)建立在終端節(jié)點(diǎn)之上并都以網(wǎng)絡(luò)應(yīng)用自居，但它們的最終目的是為了提供路由或組播這些人們原本認(rèn)為應(yīng)當(dāng)由基礎(chǔ)設(shè)施來提供的基礎(chǔ)性服務(wù)。因此認(rèn)為，各

4、種形式的層疊網(wǎng)本身可以成為互聯(lián)網(wǎng)基礎(chǔ)實施的重要組成部分，同時層疊網(wǎng)技術(shù)可以成為改造和更新當(dāng)前互聯(lián)網(wǎng)基礎(chǔ)設(shè)施的一個重要手段。這一觀點(diǎn)主要基于以下兩個事實：首先，從提供基礎(chǔ)服務(wù)的角度來看，許多由終端節(jié)點(diǎn)組成的層疊網(wǎng)與由路由器組成的第三層網(wǎng)絡(luò)具有相同的目的，在大多數(shù)情況下，前者可以看作是對后者有效的補(bǔ)充；其次，層疊網(wǎng)技術(shù)的一個重要思想是通過少部分節(jié)點(diǎn)的協(xié)同合作來實現(xiàn)面向應(yīng)用的基礎(chǔ)服務(wù)，這不需要全面和徹底地改造原有的互聯(lián)網(wǎng)基礎(chǔ)設(shè)施，大大降低了實

5、現(xiàn)成本，具有良好的靈活性和可行性。根據(jù)以往的經(jīng)驗，層疊網(wǎng)在提高路由質(zhì)量和提供組播服務(wù)等方面能夠?qū)Ξ?dāng)前的互聯(lián)網(wǎng)基礎(chǔ)設(shè)施起到很好的補(bǔ)充作用，但真正要讓層疊網(wǎng)成為基礎(chǔ)設(shè)施的一部分，還有許多關(guān)鍵問題亟待解決，本文正是圍繞這些問題展開討論的。 本文的創(chuàng)新點(diǎn)主要有以下三條： 1、開創(chuàng)性地提出了在考慮BGP路由策略干擾情況下的路由層疊網(wǎng)的節(jié)點(diǎn)部署問題的數(shù)學(xué)模型，并將該問題分解成層疊路徑布局與層疊路徑合并兩個子問題。針對這兩個問題分別設(shè)

6、計了LASER算法和最大交集啟發(fā)式算法，這套算法組合能在多項式時間內(nèi)針對特定的連接需求集計算出一個路由層疊網(wǎng)節(jié)點(diǎn)布局方案，以盡可能少的層疊節(jié)點(diǎn)成本消除BGP路由策略所帶來的路徑膨脹問題，實現(xiàn)最短AS路徑路由。 2、創(chuàng)造性地提出了動態(tài)層疊網(wǎng)的概念并針對動態(tài)層疊網(wǎng)的拓?fù)鋽M合問題設(shè)計了一個全新的網(wǎng)絡(luò)原語-JRF。JRF原語的獨(dú)特之處在于它巧妙地借用了組播路由器的功能幫助層疊節(jié)點(diǎn)獲取底層網(wǎng)絡(luò)信息，同時又避免了IP組播的一些缺點(diǎn)，具有很好