3.2 基于超節(jié)點(diǎn)的覆蓋網(wǎng)拓?fù)錁?gòu)建

3.2.1 問(wèn)題的描述

構(gòu)建路由覆蓋網(wǎng)絡(luò)拓?fù)?，使得網(wǎng)絡(luò)的總時(shí)延最小，因此，問(wèn)題可以定義如下：用圖Gu（Vu, Eu）表示IP網(wǎng)絡(luò)拓?fù)?，其中?span id="2hayjy4" class="italic">Vu和Eu分別表示物理網(wǎng)絡(luò)的節(jié)點(diǎn)集合和鏈路（即邊）集合。相應(yīng)地Go（Vo, Eo）表示一個(gè)覆蓋網(wǎng)拓?fù)洌?span id="ov9h4pv" class="italic">Vo表示覆蓋網(wǎng)絡(luò)節(jié)點(diǎn)集且Vo∈Vu, Eo是覆蓋網(wǎng)鏈路的集合。N=|Vu|和M=|Vo|分別表示物理網(wǎng)絡(luò)和覆蓋網(wǎng)絡(luò)的規(guī)模。對(duì)于m, n, i, j∈Gu，布爾變量是一個(gè)物理鏈路指示器，當(dāng)節(jié)點(diǎn)m和n之間的物理路徑包含物理鏈路ij 時(shí)，=1，否則=0；而對(duì)于x, y, m, n∈Go, 表示一個(gè)覆蓋網(wǎng)鏈路指示器，當(dāng)覆蓋網(wǎng)路徑xy包含覆蓋鏈路mn時(shí)，=1，否則=0。Dij表示物理鏈路ij的時(shí)延。路由覆蓋網(wǎng)拓?fù)錁?gòu)建問(wèn)題可以表述為：構(gòu)建一個(gè)覆蓋網(wǎng)絡(luò)拓?fù)洌沟镁W(wǎng)絡(luò)的總時(shí)延最小，用公式表示如下：

3.2.2 超節(jié)點(diǎn)的選取

實(shí)現(xiàn)上述目標(biāo)的第一步就是要選擇盡量少的能提供最短路由的節(jié)點(diǎn)作為路由覆蓋網(wǎng)的核心節(jié)點(diǎn)。研究表明在物理網(wǎng)絡(luò)中有少量具有較高介數(shù)中心的節(jié)點(diǎn)頻繁出現(xiàn)在最短路徑上[7][17]；也就是說(shuō)，少量中繼節(jié)點(diǎn)可以為大多數(shù)的端到端通信節(jié)點(diǎn)提供最優(yōu)的路由，這些中繼節(jié)點(diǎn)具有較高的介數(shù)中心。我們稱這些中繼節(jié)點(diǎn)為超節(jié)點(diǎn)（Super-Relay nodes）。節(jié)點(diǎn)的介數(shù)中心[143]定義為網(wǎng)絡(luò)中所有最短路徑中經(jīng)過(guò)該節(jié)點(diǎn)的路徑的數(shù)目占最短路徑總數(shù)比例，用公式表示如下：

其中V表示節(jié)點(diǎn)集，σst是節(jié)點(diǎn)s和t間的最短路徑的數(shù)目，σst（v）表示節(jié)點(diǎn)s和t間的最短路徑中經(jīng)過(guò)節(jié)點(diǎn)v的路徑數(shù)目。

綜上所述，要提高路由覆蓋網(wǎng)絡(luò)的性能，選擇并合理連接超節(jié)點(diǎn)是至關(guān)重要的。為了驗(yàn)證超節(jié)點(diǎn)在路由中的重要性，我們以一個(gè)真實(shí)的物理網(wǎng)絡(luò)CN070[137]為例，統(tǒng)計(jì)了節(jié)點(diǎn)的介數(shù)中心分布情況，結(jié)果如圖3-5所示。CN070反映了2006年中國(guó)大陸互聯(lián)網(wǎng)中核心路由器的連接情況。網(wǎng)絡(luò)中鏈路的權(quán)重直接影響節(jié)點(diǎn)間最短路徑的選擇，進(jìn)而影響節(jié)點(diǎn)的介數(shù)中心的計(jì)算。因此，我們?cè)趨^(qū)間[40-240]Mb/s隨機(jī)為CN070中每條鏈路進(jìn)行賦值，該值代表鏈路的可用帶寬；而鏈路的權(quán)重設(shè)置為該鏈路可用帶寬的倒數(shù)。為鏈路賦值不同的權(quán)重可以產(chǎn)生不同加權(quán)網(wǎng)絡(luò)拓?fù)?。如圖3-5所示，橫坐標(biāo)是按介數(shù)中心降序排列的節(jié)點(diǎn)的ID，縱坐標(biāo)是介數(shù)中心；圖中的星型線是CN070加權(quán)網(wǎng)絡(luò)中節(jié)點(diǎn)的介數(shù)中心，圓圈線是相應(yīng)的無(wú)權(quán)網(wǎng)絡(luò)中節(jié)點(diǎn)的介數(shù)中心。圖3-5中，加權(quán)網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的介數(shù)中心是對(duì)鏈路賦值2000次后所得的平均值。由圖可以看出，只有少數(shù)節(jié)點(diǎn)具有較高的介數(shù)中心，且加權(quán)網(wǎng)絡(luò)中節(jié)點(diǎn)的介數(shù)中心與相應(yīng)的無(wú)權(quán)網(wǎng)絡(luò)中節(jié)點(diǎn)的介數(shù)中心具有相同的分布。這表明，我們可以根據(jù)無(wú)權(quán)網(wǎng)絡(luò)計(jì)算節(jié)點(diǎn)的介數(shù)中心，并選擇少量具有較高介數(shù)中心的節(jié)點(diǎn)作為覆蓋網(wǎng)絡(luò)的超節(jié)點(diǎn)。而加權(quán)網(wǎng)絡(luò)的鏈路權(quán)重是動(dòng)態(tài)變化的，很難精確測(cè)量。

圖3-5 物理網(wǎng)絡(luò)中節(jié)點(diǎn)的介數(shù)中心

根據(jù)上面的分析，我們從無(wú)權(quán)網(wǎng)絡(luò)中選取一定數(shù)量的具有較高介數(shù)中心的節(jié)點(diǎn)作為超節(jié)點(diǎn)。只有當(dāng)物理網(wǎng)絡(luò)拓?fù)浒l(fā)生變化時(shí)，才重新計(jì)算超節(jié)點(diǎn)，這樣的選取方法簡(jiǎn)單，復(fù)雜度小。超節(jié)點(diǎn)的數(shù)量取決于物理網(wǎng)絡(luò)的規(guī)模，實(shí)驗(yàn)結(jié)果表明，選取10%左右的超節(jié)點(diǎn)便可以提供較好的性能。

3.2.3 K最小生成樹(shù)覆蓋網(wǎng)拓?fù)?/h3>

我們構(gòu)造的覆蓋網(wǎng)拓?fù)溆沙?jié)點(diǎn)（Super-Relay nodes）和普通節(jié)點(diǎn)（Ordinary-Relay nodes）構(gòu)成，其中超節(jié)點(diǎn)是按照3.2.2節(jié)中所述方法從無(wú)權(quán)物理網(wǎng)絡(luò)中選取一定數(shù)量的具有較高介數(shù)中心的節(jié)點(diǎn)；而普通節(jié)點(diǎn)是根據(jù)端系統(tǒng)或用戶的需求選擇的主機(jī)節(jié)點(diǎn)。因此，超節(jié)點(diǎn)相對(duì)穩(wěn)定，服務(wù)周期長(zhǎng)，是物理網(wǎng)絡(luò)中選取的介數(shù)中心較高的路由器節(jié)點(diǎn)，或者是連接到該路由器的服務(wù)器；而普通節(jié)點(diǎn)則是根據(jù)用戶的需求選擇的主機(jī)節(jié)點(diǎn)并將其映射到物理網(wǎng)絡(luò)中，如圖3-6所示，節(jié)點(diǎn)A、B、E、F、G和I是普通節(jié)點(diǎn)，節(jié)點(diǎn)C、D和H代表超節(jié)點(diǎn)。

圖3-6 基于超節(jié)點(diǎn)的2-MST覆蓋網(wǎng)絡(luò)拓?fù)?/p>

我們提出的覆蓋網(wǎng)絡(luò)拓?fù)錁?gòu)建算法是基于超節(jié)點(diǎn)的K最小生樹(shù)（K Minimum Spanning Tree based on Super-Relay nodes, SR-KMST）。構(gòu)建過(guò)程中，首先將所有覆蓋網(wǎng)節(jié)點(diǎn)（包括超節(jié)點(diǎn)和普通節(jié)點(diǎn)）連接形成K最小生成樹(shù)（K-MST），假如，超節(jié)點(diǎn)間沒(méi)有形成全網(wǎng)狀結(jié)構(gòu)，則在超節(jié)點(diǎn)之間增加覆蓋網(wǎng)鏈路，使之形成全網(wǎng)狀結(jié)構(gòu)。K值的選取依據(jù)節(jié)點(diǎn)的度約束來(lái)決定。構(gòu)建K最小生成樹(shù)時(shí)，設(shè)置覆蓋網(wǎng)鏈路的權(quán)重為該鏈路對(duì)應(yīng)的IP路徑所包含的物理鏈路的跳數(shù)。眾所周知，最小生成樹(shù)是連接所有節(jié)點(diǎn)的代價(jià)最小的樹(shù)；而構(gòu)建K最小生成樹(shù)可以確保兩個(gè)覆蓋網(wǎng)節(jié)點(diǎn)間存在K條相對(duì)獨(dú)立的覆蓋路徑，這可以提高可靠性和容錯(cuò)性。另一方面，超節(jié)點(diǎn)之間形成全網(wǎng)狀結(jié)構(gòu)，可以減少路徑長(zhǎng)度，降低路由代價(jià)（如時(shí)延）；且同一個(gè)超節(jié)點(diǎn)集可以服務(wù)于不同的普通節(jié)點(diǎn)集，形成多個(gè)不同的覆蓋網(wǎng)絡(luò)。

圖3-6顯示了基于超節(jié)點(diǎn)的2最小生成樹(shù)（SR-2MST）覆蓋網(wǎng)絡(luò)的構(gòu)建過(guò)程，在覆蓋網(wǎng)絡(luò)（Overlay Network）中，黑色實(shí)線和黑色虛線分別表示兩個(gè)最少重疊的最小生成樹(shù)；為了在超節(jié)點(diǎn)C、D和H之間形成全網(wǎng)狀結(jié)構(gòu)，在節(jié)點(diǎn)C和H之間增加一條覆蓋鏈路CH（紅色虛線所示）。

算法SR-KMST的具體描述如下：

SR-KMST算法

Gu（Vu, Eu）和G′u（V′u, E′u）分別表示一個(gè)加權(quán)物理網(wǎng)絡(luò)和對(duì)應(yīng)的無(wú)權(quán)網(wǎng)絡(luò)。VSR和VOR分別表示組成覆蓋網(wǎng)絡(luò)的超節(jié)點(diǎn)集和普通節(jié)點(diǎn)集。N r=|V SR|為超節(jié)點(diǎn)的數(shù)量。MST（G）表示圖G的最小生成樹(shù)中邊的集合，假如G是一個(gè)非連通圖，則MST（G）表示G中各部分所形成的森林。

輸入：G′u（V′u, E′u）和VOR

輸出：覆蓋網(wǎng)絡(luò)拓?fù)?span id="fn74zpv" class="italic">GO

① 計(jì)算G′u（V′u, E′u）中所有節(jié)點(diǎn)的介數(shù)中心，記為BCs。

② 從BCs中選取介數(shù)中心最高的Nr個(gè)節(jié)點(diǎn)作為超節(jié)點(diǎn)，記為VSR。

③ 連接No=|VSR∪VOR|個(gè)覆蓋網(wǎng)節(jié)點(diǎn)形成一個(gè)全網(wǎng)狀拓?fù)?span id="eopvjma" class="italic">GTO。

④ 初始化GTO中每條覆蓋網(wǎng)鏈路的權(quán)重為其對(duì)應(yīng)的物理路徑的跳數(shù)。

⑤ 在拓?fù)?span id="qalj7bz" class="italic">GTO中應(yīng)用下列方法計(jì)算K最小生成樹(shù)Fk：

G0=GTO；

F0=null；

For j=1…k do

Tj=MST（Gj-1）；

Fj=Fj-1∪Tj；

Gj=Gj-1\Tj；

End For

⑥ 連接Nr個(gè)超節(jié)點(diǎn)形成全網(wǎng)狀結(jié)構(gòu)G relay，其中每條鏈路的權(quán)重為其對(duì)應(yīng)的IP路徑的跳數(shù)。

⑦GO=F k∪Grelay。

表3-1顯示了算法SR-KMST與已有覆蓋網(wǎng)絡(luò)拓?fù)錁?gòu)建算法FM[23]、KMST[63]、MT[136]和AC[25]。在計(jì)算復(fù)雜度和節(jié)點(diǎn)度方面的對(duì)比分析，其中N和M 分別表示物理網(wǎng)絡(luò)和覆蓋網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)目，No是由算法SR-KMST構(gòu)造的覆蓋網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)目，Nr是超節(jié)點(diǎn)的數(shù)目，LP表示物理網(wǎng)絡(luò)中路由路徑的平均跳數(shù)。計(jì)算復(fù)雜度體現(xiàn)了構(gòu)造覆蓋網(wǎng)拓?fù)涞拇鷥r(jià)，而節(jié)點(diǎn)度的大小決定了覆蓋網(wǎng)絡(luò)中節(jié)點(diǎn)需維護(hù)的鄰居節(jié)點(diǎn)的個(gè)數(shù)，在一定程度上反映了覆蓋網(wǎng)絡(luò)的維護(hù)代價(jià)。

表3-1 性能比較

從表3-1中可以看出，F(xiàn)M具有最小的計(jì)算復(fù)雜度。由于K的值遠(yuǎn)小于M 的值，因此KMST與FM的復(fù)雜度相同，而SR-KMST的復(fù)雜度略大于KMST的復(fù)雜度（No≥M）。在SR-KMST中，雖然超節(jié)點(diǎn)之間形成全網(wǎng)狀結(jié)構(gòu)，但與FM算法相比較，SR-KMST中節(jié)點(diǎn)度非常?。?span id="tuflovk" class="italic">M?Nr, M-1?K），這表明SR-KMST具有一定的可擴(kuò)展性。