蔡建宏，李躍新

（湖北大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，湖北 武漢 430064）

1 Hose模型的基本思想

要實(shí)現(xiàn)一個(gè)虛擬專(zhuān)用網(wǎng)（Virtual Private Network，VPN），可以使用許多種技術(shù)如IPSEC，隧道技術(shù)或者使用一些特殊的協(xié)議。然而對(duì)資源分配與管理卻沒(méi)有得到應(yīng)有的重視，目前這種管理僅僅限于從一個(gè)VPN的終端到其他所有終端的分配，稱這種方式為Pipe模型。目前，Amit等[1]提出了一種更為優(yōu)秀的管理方法，取名為Hose模型。

Hose模型可以看成一個(gè)VPN的服務(wù)接口以及一個(gè)性能的抽象。一個(gè)Hose在提供一個(gè)到網(wǎng)絡(luò)的連接的同時(shí)還能滿足對(duì)帶寬的限制，它允許在不用去預(yù)測(cè)點(diǎn)到點(diǎn)的負(fù)載的情況下去發(fā)送、接收信息。

Pipe模型與Hose模型之間的區(qū)別如圖1所示。圖1（a）表示Pipe模型：它在提供鏈路的同時(shí)要求指明從一個(gè)VPN的終端到其他所有終端所需的帶寬的預(yù)留值。圖1（b）表示Hose模型：它僅僅要求一個(gè)Hose連接到VPN時(shí)指明一個(gè)入度和出度的帶寬值，無(wú)須理會(huì)其他Hose。

圖1 （a）Pipe模型；(b)Hose模型

在Hose模型中，通信網(wǎng)絡(luò)可以看成是一個(gè)無(wú)向圖G=（V，E），V表示結(jié)點(diǎn)集，E表示邊集合。對(duì)e∈E的每一條邊都有一個(gè)每單元預(yù)留的價(jià)值ce和一個(gè)容量的極限值Ce。在本文中，為簡(jiǎn)化問(wèn)題，在無(wú)特殊注釋時(shí)，ce的值1，Ce的值被看成無(wú)限大。VPN的終端集Q就被看成結(jié)點(diǎn)集V的子集即Q∈V。

在以上對(duì)Hose模型的描述中，并沒(méi)有在所有VPN終端之間指明它們的完全的流量矩陣，也就是說(shuō)對(duì)v∈Q的每一個(gè)結(jié)點(diǎn)v，只需要兩個(gè)參數(shù)b-v和b+v，其中b-v表示結(jié)點(diǎn)v可以接受的最大信息量（入度），b+v表示結(jié)點(diǎn)v可以發(fā)送的最大信息量（出度）。

Hose模型這樣設(shè)計(jì)的目的是要在網(wǎng)絡(luò)中預(yù)留足夠多的帶寬并在各VPN終端之間路由信息，以此保證這些被預(yù)留的帶寬可以有效地支持網(wǎng)絡(luò)中的每個(gè)信息流量矩陣。然而，要使一個(gè)信息矩陣是有效的當(dāng)且僅當(dāng)每一對(duì)終端（u,v），它們的非負(fù)需求值duv都要滿足以下的公式：

在VPN的邊e∈E上所預(yù)留的帶寬我們用ye來(lái)表示。那么總成本或預(yù)留的權(quán)值。

W這樣定義是為了能找到一個(gè)最低成本預(yù)留值。

Hose模型如何通過(guò)共享鏈路來(lái)節(jié)省帶寬，示意如圖2所示。3個(gè)VPN終端q1,q2,q3是對(duì)稱的（即它們的入度、出度帶寬相等），分別等于1，2，2個(gè)單元。

當(dāng)一個(gè)獨(dú)立的最短路徑方法用來(lái)連接VPN終端時(shí)網(wǎng)絡(luò)中相關(guān)鏈路的帶寬情況如圖3所示。這是Pipe模型中最常用的方法。那么，q1和q2之間的最短路徑要經(jīng)過(guò)結(jié)點(diǎn)B，q1和q3之間的最短路徑要經(jīng)過(guò)結(jié)點(diǎn)A。這樣整個(gè)網(wǎng)絡(luò)的預(yù)留帶寬為16個(gè)單元。如圖4所示，Hose模型假設(shè)所有路徑都通過(guò)結(jié)點(diǎn)C，經(jīng)過(guò)復(fù)用整個(gè)網(wǎng)絡(luò)的預(yù)留的帶寬減少到12個(gè)單元。我們注意到在圖4中q1到q2的路徑經(jīng)過(guò)了結(jié)點(diǎn)C而，比圖圖3中通過(guò)結(jié)點(diǎn)B的路徑要長(zhǎng)。然而，既然終端q1不能接受和發(fā)送超過(guò)1個(gè)的信息量，那么預(yù)留在從終端q1到結(jié)點(diǎn)C的每一條鏈路（在一個(gè)方向上）的帶寬就是1個(gè)單元，它可以被兩條路徑共享。

圖2 Hose模型節(jié)省帶寬示意

圖3 獨(dú)立最短路徑

圖4 假設(shè)所有圖形都經(jīng)過(guò)節(jié)點(diǎn)C

由上述說(shuō)明我們知道，Pipe模型的VPN供給非常簡(jiǎn)單，因?yàn)槊恳粚?duì)終端（u,v）∈Q的信息量是固定的，而且被寫(xiě)進(jìn)了供給的算法中。然而，Hose模型去掉了這種簡(jiǎn)單的供給同時(shí)具有易于配置和復(fù)用收益的優(yōu)點(diǎn)。

2 Hose模型變量

在Hose模型中尋找最小成本的預(yù)留帶寬的問(wèn)題可以歸結(jié)為以下幾種不同的條件。首先，對(duì)入度、出度的帶寬（b-v和b+v v∈Q）可以有以下3種定義方法：

對(duì)稱：b-v=b+v?v∈Q。

非對(duì)稱：b-v和b+v可以為任意值。

另外，它還受到路由條件的制約。

樹(shù)路由：根據(jù)每條邊上預(yù)留的帶寬形成一個(gè)樹(shù)T，而從u∈Q到v∈Q信息量一定要沿著樹(shù)T中從u到v的路徑路由。

不分裂路由：對(duì)每一對(duì)在Q中不同的結(jié)點(diǎn)（u,v），信息量是沿著一個(gè)唯一的路徑Puv。Puv不依賴信息矩陣，而且它可以不等于Pvu 。

可分裂路由：對(duì)每一對(duì)在Q中不同的結(jié)點(diǎn)（u,v），信息量可以被任意分配到幾條不同路徑上。它不依賴信息矩陣，而且從u到v的路徑與從v到u的路徑可以不同。

可分裂動(dòng)態(tài)路由：對(duì)每一對(duì)在Q中不同的結(jié)點(diǎn)（u,v），信息量可以被任意分配到幾條不同路徑上，但它依賴于信息矩陣。

3 建造一個(gè)Hose模型的VPN

在這一部分，只建造對(duì)稱可分裂路由的情況。主要討論了如何在一個(gè)網(wǎng)絡(luò)G（V,E）中建造一個(gè)有效的Hose的問(wèn)題。通過(guò)下面的敘述我們可以看到建造一個(gè)Hose與校驗(yàn)一個(gè)Hose是緊密關(guān)聯(lián)的。

3.1 對(duì)稱樹(shù)路由

對(duì)于對(duì)稱樹(shù)路由，給出一個(gè)時(shí)間復(fù)雜度是多項(xiàng)級(jí)的算法。在假定鏈路無(wú)容量限制的條件下計(jì)算一個(gè)VPN樹(shù)的最小成本。該算法定義了一個(gè)數(shù)量函數(shù)Q（T,r）。其中T,r分別表示樹(shù)，和一個(gè)根結(jié)點(diǎn)。dT（r，v）則是樹(shù)T中從r到終端v的路徑長(zhǎng)度。

存在一個(gè)優(yōu)化根結(jié)點(diǎn)r，它能使Q（T，r）等于一個(gè)樹(shù)預(yù)留帶寬的最小權(quán)值。為此，使用了一個(gè)以r為根結(jié)點(diǎn)按寬度優(yōu)先搜索圖G得到的一個(gè)有向樹(shù)。以下是設(shè)計(jì)的算法：

//輸入:圖 G,終端集合Q,帶寬 b

// 輸出: 優(yōu)化預(yù)留帶寬樹(shù)T_ opt,優(yōu)化結(jié)點(diǎn) r_ opt

forall_ nodes （r , G）

T_r = r;

Qu = r; // queue for BFS

while （Qu.empty（）==false）

v = Qu.pop（）;

forall_ inout _edges （e,v）

w = G.opposite（v,e）;

I if （w is not in T_r）

添加邊 （v,w） 到 T_ r;

Qu.append（w）;

去掉樹(shù)T中非終端的葉子結(jié)點(diǎn)

計(jì)算 Q（T r,r）;

if （Q（T_ r, r） < Q（T_opt,r_opt）

T_opt = T_ r;

return T_opt,r_opt;

3.2 可分裂路由

在可分裂路由的Hose模型中找到一個(gè)優(yōu)化解意味著在一個(gè)指定的網(wǎng)絡(luò)圖G=(V,E)中使優(yōu)化問(wèn)題最小。即使最小。這里ce,ye分別代表邊e上的成本，和預(yù)留的帶寬。顯然，直到x11,…x100都為0算法結(jié)束。最終，我們得到一個(gè)優(yōu)化解即：x1=x2=…=x10=1，x11=x12=…=x100=0。我們注意到切位算法僅僅重復(fù)了91次解線性規(guī)劃和找一個(gè)沖突約束。

3.3 Hose模型的VPN算法與實(shí)現(xiàn)

在上一部分的討論中，假設(shè)預(yù)先知道了能保留最小權(quán)值的結(jié)點(diǎn)r。然而，實(shí)際應(yīng)用中這種情況卻不常見(jiàn)。相反，整數(shù)規(guī)劃必須計(jì)算每一個(gè)屬于集合V的結(jié)點(diǎn)r，以期獲得優(yōu)化解。另一個(gè)在實(shí)現(xiàn)中要注意的一點(diǎn)是要連接所有終端v到核心結(jié)點(diǎn)集合S。在使用寬度優(yōu)先搜索（BFS）去連接所有結(jié)點(diǎn)v，找到最終樹(shù)的預(yù)留帶寬前，不必將集合S中所有結(jié)點(diǎn)連接到一個(gè)超結(jié)點(diǎn)。

// 輸入:圖 G, S中核心結(jié)點(diǎn)隊(duì)列 Qu,距離 dist

//如果結(jié)點(diǎn) v 屬于集合 s ,那么 dist [ v ] = 1，否則 dist [v] = INFINITY

//輸出: 預(yù)留帶寬樹(shù) T

用非核心結(jié)點(diǎn)建造樹(shù)T;

while （ == Qu.empty（））

v = Qu.pop（）;

forall_inout_edges （e,v）

w = G.opposite（v,e）;

if （ dist[w] == INFINITY）

dist[w] = dist[v] + 1;

Qu.append（w）;

添加 e,w 到 T;

去掉樹(shù)T中非終端的葉子結(jié)點(diǎn);

return T;

4 結(jié)語(yǔ)

Hose模型的概念已經(jīng)被證實(shí)并且它顯示了很多有意義的行為和表象。本文研究限定在對(duì)稱的樹(shù)、不可分裂路由的情況。在此限定下，提出了一些方法去校驗(yàn)給定的Hose預(yù)留的帶寬。設(shè)計(jì)的校驗(yàn)算法能有效地判斷給定的Hose路由和預(yù)留的帶寬是否在各種形式的路由中都有效。同時(shí)，該算法還能判斷預(yù)留的帶寬是嚴(yán)謹(jǐn)?shù)模ㄊ褂昧怂薪o定的容量）還是寬松的（浪費(fèi)一些帶寬）。

[參考文獻(xiàn)]

[1]AMIT K，RAJEEV R，AVI S，et al.Algorithms for provisioning virtual private networks in the Hose model[J].Proceedings of ACM Sigcomm，2001（4）：135-146.

[2]AMIT K，RAJEEV R，AVI S，et al. Algorithms for provisioning virtual private networks in the Hose model[J].IEEE/ACM Transactions on Networking，2002（4）：565-578.

[3]徐雷鳴，龐博，趙耀. NS與網(wǎng)絡(luò)模擬[M].北京：人民郵電出版社，2003.

[4]楊磊，李仁發(fā)，王東，等.虛擬專(zhuān)用網(wǎng)（VPN）QOS述評(píng)[J].小型微型計(jì)算機(jī)系統(tǒng)，2003（6）：983-986.