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

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

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