基于覆蓋網(wǎng)絡(luò)的應(yīng)用層選播結(jié)構(gòu)研究

基于覆蓋網(wǎng)絡(luò)的應(yīng)用層選播結(jié)構(gòu)研究

1基于網(wǎng)絡(luò)的應(yīng)用層選播技術(shù)選播是基于rfc1546的一個新的網(wǎng)絡(luò)模型。它被用作每個節(jié)點的多個接口，并與一個列表地址合并，以表示未來網(wǎng)絡(luò)的三種通信模式之一。正如所選播種一樣，將有害節(jié)點標記為不同節(jié)點的多個接口，并將有害節(jié)點的發(fā)送給經(jīng)過傳輸?shù)刂返暮瘮?shù)調(diào)整為具有這些地址的接口，并根據(jù)路徑協(xié)議距離測量“最新”。（anyzer）可以有效平衡網(wǎng)絡(luò)負荷，減少路徑和鏈接的數(shù)量，簡化主機配置等網(wǎng)絡(luò)應(yīng)用，提高網(wǎng)絡(luò)服務(wù)質(zhì)量（qui值）。它可以在網(wǎng)站鏡像、dns、負載平衡、移動多段、算術(shù)和其他領(lǐng)域發(fā)揮重要作用。起初選播的研究集中在網(wǎng)絡(luò)層,即通過網(wǎng)絡(luò)的拓撲結(jié)構(gòu)由路由器來完成選路,具有高效性.但是它本身也存在兩個局限性限制了網(wǎng)絡(luò)層選播的發(fā)展:其一,在網(wǎng)絡(luò)層實現(xiàn)選播過程中可能產(chǎn)生“無狀態(tài)服務(wù)”問題,由于選播數(shù)據(jù)包在路由到“最優(yōu)”服務(wù)節(jié)點過程中不依賴于以前的數(shù)據(jù)包這個自然屬性,當請求的數(shù)據(jù)包屬于面向連接的應(yīng)用或者被分段,那么選播服務(wù)的效率反而可能低于單播.其二,選播路由表不遵從單播的路由匯聚規(guī)則,因為共享某個Anycast地址的選播組成員節(jié)點可能分散在Internet的不同地方.若用單播路由協(xié)議對每個Anycast地址作為獨立的路由表項進行處理,則可能導(dǎo)致路由表的膨脹.這便是Anycast存在的可擴展性問題.因此近年來人們把研究目光轉(zhuǎn)向了應(yīng)用層.與IP選播相比,它具有易于部署和實現(xiàn),無需修改路由信息,能根據(jù)網(wǎng)絡(luò)動態(tài)變化實現(xiàn)服務(wù)定制,有較好的靈活性和擴展性等優(yōu)勢.目前最新的研究是關(guān)于一類基于代理的應(yīng)用層選播結(jié)構(gòu),即選播的路由不再由路由器完成而是通過代理實現(xiàn)最近服務(wù)器的選擇.但是目前的這類系統(tǒng)主要關(guān)注于某種特定的目標,如為了保證端到端的時延,對服務(wù)代理的帶寬資源進行優(yōu)化或者對服務(wù)代理進行某種設(shè)置來保證特定系統(tǒng)的可靠性等,并沒有提出一種效率高、通用性好的基于服務(wù)代理的選播結(jié)構(gòu)的構(gòu)造方法,來保證網(wǎng)絡(luò)負載的均衡和網(wǎng)絡(luò)的服務(wù)質(zhì)量.本文提出一種基于覆蓋網(wǎng)的應(yīng)用層選播(ApplicationLayerAnycastOverlayNetwork,ALAON)構(gòu)造方法,為選播的實現(xiàn)提供了良好的基礎(chǔ).2aloln結(jié)構(gòu)2.1基于網(wǎng)絡(luò)的仿真OverlayNetwork技術(shù)是一種構(gòu)造網(wǎng)絡(luò)方法,它與特定技術(shù)、特定層次無關(guān).它可在原有物理網(wǎng)絡(luò)的基礎(chǔ)上,按照某種需要構(gòu)造一個虛擬網(wǎng)絡(luò),以此來支持原網(wǎng)絡(luò)沒有或很難提供的功能,并能最大限度地保證與原有網(wǎng)絡(luò)的兼容性.OverlayNetwork無需物理構(gòu)造,而只需要邏輯融合,即可提供所需的服務(wù),并由此改善下層網(wǎng)絡(luò)的一些相關(guān)屬性,而且可以在與現(xiàn)有網(wǎng)絡(luò)兼容的基礎(chǔ)上,較為靈活地解決當前網(wǎng)絡(luò)體系結(jié)構(gòu)所存在的問題.2.2基于自治域內(nèi)選播的選播協(xié)調(diào)管理機制在網(wǎng)絡(luò)體系結(jié)構(gòu)總思想的指導(dǎo)下,用OverlayNetwork的思想來解決選播所面臨的問題.我們把ALAON結(jié)構(gòu)分為三層:基礎(chǔ)網(wǎng)絡(luò)層、覆蓋網(wǎng)絡(luò)層和選播應(yīng)用層.底層基礎(chǔ)網(wǎng)絡(luò)層為真實物理網(wǎng)絡(luò)節(jié)點(或服務(wù)器)和鏈路,利用現(xiàn)有TCP/IP協(xié)議族在物理鏈路上提供基本的物理層傳輸、網(wǎng)絡(luò)通信和網(wǎng)絡(luò)層路由等功能.中間層為覆蓋網(wǎng)絡(luò)層,其節(jié)點為服務(wù)代理節(jié)點及選播成員,它們之間用虛擬的覆蓋網(wǎng)絡(luò)鏈路進行連接,生成并維護OverlayNetwork網(wǎng)絡(luò)拓撲結(jié)構(gòu),并按照一定的算法實現(xiàn)選播路由.最上層是選播應(yīng)用層,為端用戶和選播應(yīng)用程序提供應(yīng)用接口.因為本文的研究的內(nèi)容與關(guān)鍵在于覆蓋網(wǎng)絡(luò)的構(gòu)造.本文將ALAON覆蓋網(wǎng)的構(gòu)造方案通過自治域內(nèi)選播和自治域間的選播分層結(jié)構(gòu)來實現(xiàn):首先,把選播組成員分成若干個自治域,這里的自治域直接采用當前Internet為保證單播服務(wù)所劃分的自治區(qū)域概念,在域內(nèi)部署服務(wù)代理(ServerAgent)節(jié)點,通過以它為根節(jié)點,選播成員為葉子節(jié)點構(gòu)成一棵組播樹的方式來實現(xiàn)對域內(nèi)的選播資源的管理;其次,在每個自治域內(nèi)選舉較高處理能力及可靠性的SA節(jié)點來調(diào)度和管理域間資源,從而保證網(wǎng)絡(luò)的負載平衡和選播服務(wù)的質(zhì)量.ALAON體系結(jié)構(gòu)拓撲圖見圖1.3aloan節(jié)點部署根據(jù)上面提到的ALAON的體系結(jié)構(gòu),其部署重點在于代理節(jié)點P的數(shù)量和位置.真實的物理網(wǎng)絡(luò)可用無相圖G(V,E)來表示,定義客戶端節(jié)點的集合C?V及它們的需求dc;服務(wù)器節(jié)點的集合S?V及它們的服務(wù)能力cs;邊的權(quán)重ωe,e∈E.實際上就是構(gòu)造這樣一個虛擬代理覆蓋拓撲G′(P,E′),其中P為代理節(jié)點的集合,E′為虛擬鏈路的集合.由此可見ALAON節(jié)點部署問題實際上就是一個優(yōu)化問題,應(yīng)考慮平衡網(wǎng)絡(luò)資源利用代價,代理服務(wù)器的部署可分解為以下2個優(yōu)化目標:(1)找到合適的代理服務(wù)節(jié)點的位置及數(shù)量;(2)優(yōu)化鏈路的總流量.條件2不能決定代理節(jié)點的位置和維數(shù),但是可以對條件1部署的代理節(jié)點的效率進行檢驗.對任意一個選播系統(tǒng),設(shè)總共需要部署M(0≤M≤N)個代理服務(wù)節(jié)點,Pi表示節(jié)點i是否被選為代理節(jié)點,對于?i∈V,Pi∈{0,1}.ai(i≤N)表示與路由器Ri鏈接的選播組的數(shù)量,而兩個路由器Ri與Rj之間的最短距離wij(0≤i,j≤N),從而得到ALAON節(jié)點部署的目標函數(shù)如下.min∑j=1N(∑i=1Nwij×pij)×aimin∑j=1Ν(∑i=1Νwij×pij)×ai,其約束條件如下:(1)每個代理至少與一個路由器相連,Pi≤∑j=1NpijΡi≤∑j=1Νpij;(2)為了控制覆蓋網(wǎng)的規(guī)模,最多部署M個代理節(jié)點,∑i=1Npi≤M∑i=1Νpi≤Μ;(3)每一個路由器Rj只能與一個代理相連,有∑i∈Vpij=1.∑i∈Vpij=1.由此可見,從目標函數(shù)和約束條件看,此問題是整數(shù)劃問題(integerslinearprogram).隨著網(wǎng)絡(luò)規(guī)模的變化,這種組合優(yōu)化NP難問題,很難采用傳統(tǒng)的優(yōu)化算法進行求解,這里采用啟發(fā)式算法進行求解.4覆蓋鏈路的選取在進行虛擬鏈路選取時,由于虛擬鏈路所連接的是端用戶,而端用戶的不穩(wěn)定性必然對虛擬鏈路的可靠性有所影響,因此在進行虛擬鏈路的選取時首先要考慮鏈路的可靠性;另一方面,每條虛擬鏈路都有路由代價,因此在進行虛擬鏈路的選取時還要考慮到全局網(wǎng)絡(luò)的路由代價問題.所以,覆蓋網(wǎng)上虛擬鏈路的選取設(shè)計關(guān)鍵在于使網(wǎng)絡(luò)的可靠性要高,并且使網(wǎng)絡(luò)的路由代價最低.因此,在給定覆蓋拓撲維護開銷的條件下,選擇合適的覆蓋鏈路,對構(gòu)造高性能的覆蓋網(wǎng)絡(luò)拓撲具有重要意義.設(shè)網(wǎng)絡(luò)流量總費用為f(x),xe代表流經(jīng)邊e的流量,we代表邊e的權(quán)重,鏈路選取的目標函數(shù):minf(x)=∑e∈Ewexeminf(x)=∑e∈Ewexe,約束條件為∑e∈out(ni)xe?∑e∈in(ni)xe=bi,?ni∈V,xe≥0∑e∈out(ni)xe-∑e∈in(ni)xe=bi,?ni∈V,xe≥0式中,bi表示流過節(jié)點ni的相對剩余流量,當節(jié)點ni代理節(jié)點時,bi為非零實數(shù);當ni為普通節(jié)點時,bi為零.在實際選取鏈路時,我們假設(shè)所有的邊都是連通的,如若不然,則必能找到兩條連通的邊來代替不連通的兩點.這樣鏈路選取問題可以看作固定費用網(wǎng)絡(luò)流的問題(FixedChargeNetworkFlowProblem),并被證明是NP難問題.這里用動態(tài)偏坡優(yōu)化算法(DynamicSlopeScalingProcedure(DSSP))進行求解.5aloan仿真算法與代理結(jié)構(gòu)開發(fā)的比較本文的實驗?zāi)繕酥饕球炞C兩個方面:一是,代理的數(shù)量隨著代理節(jié)點費用的改變的變化情況;二是,代理節(jié)點的費用隨著鏈路跳數(shù)的增加而變化的情況.利用GT-ITM網(wǎng)絡(luò)生成工具根據(jù)Waxman模型隨機生成節(jié)點為250的拓撲圖作為底層物理網(wǎng)絡(luò),覆蓋網(wǎng)絡(luò)的最大代理節(jié)點數(shù)設(shè)為80.為了驗證本文提出的選播代理覆蓋結(jié)構(gòu)的優(yōu)越性,從代理節(jié)點數(shù)目和鏈路跳數(shù)兩方面對此算法和隨機生成算法進行仿真,比較兩者的性能.從圖2～3中,可以看出,隨著代理節(jié)點的數(shù)量以及鏈路跳數(shù)的變化,隨機算法和ALAON算法的變化有相同的趨勢;從圖2可以得到隨著代理節(jié)點數(shù)量的增多,覆蓋層的維護代價增大,但是ALAON算法較隨機算法有更好的性能;從圖3分析可得隨著網(wǎng)絡(luò)規(guī)模增大,選播服務(wù)的代理費用隨著鏈路跳數(shù)的增加而增加,在鏈路選取的方法中將多余的邊用已有的邊代替,這樣代理的費用一般會降低.同時,在逐漸增加網(wǎng)絡(luò)規(guī)模過程中,隨機算