• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

    Hose模型的虛擬專用網(wǎng)建造研究

    2018-04-27 12:27:20蔡建宏李躍新
    無(wú)線互聯(lián)科技 2018年8期
    關(guān)鍵詞:信息量結(jié)點(diǎn)路由

    蔡建宏,李躍新

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

    1 Hose模型的基本思想

    要實(shí)現(xiàn)一個(gè)虛擬專用網(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ā),王東,等.虛擬專用網(wǎng)(VPN)QOS述評(píng)[J].小型微型計(jì)算機(jī)系統(tǒng),2003(6):983-986.

    猜你喜歡
    信息量結(jié)點(diǎn)路由
    基于信息理論的交通信息量度量
    探究路由與環(huán)路的問(wèn)題
    Ladyzhenskaya流體力學(xué)方程組的確定模與確定結(jié)點(diǎn)個(gè)數(shù)估計(jì)
    如何增加地方電視臺(tái)時(shí)政新聞的信息量
    新聞傳播(2016年11期)2016-07-10 12:04:01
    基于多尺度互信息量的數(shù)字視頻幀篡改檢測(cè)
    基于聯(lián)合熵和交互信息量的視頻篡改檢測(cè)
    PRIME和G3-PLC路由機(jī)制對(duì)比
    WSN中基于等高度路由的源位置隱私保護(hù)
    eNSP在路由交換課程教學(xué)改革中的應(yīng)用
    河南科技(2014年5期)2014-02-27 14:08:56
    基于Raspberry PI為結(jié)點(diǎn)的天氣云測(cè)量網(wǎng)絡(luò)實(shí)現(xiàn)
    大连市| 镇赉县| 大同县| 临桂县| 韶山市| 晋中市| 南昌市| 文登市| 比如县| 清丰县| 德令哈市| 嘉黎县| 通州市| 靖江市| 滁州市| 广昌县| 枣庄市| 福鼎市| 崇明县| 垣曲县| 和硕县| 普洱| 自贡市| 安福县| 芦溪县| 灵石县| 平利县| 雷州市| 黄浦区| 丰原市| 中方县| 河南省| 图木舒克市| 县级市| 辽阳市| 天柱县| 靖江市| 昌乐县| 衡阳市| 长顺县| 静海县|