“刪邊擴(kuò)容”策略在接入網(wǎng)流量優(yōu)化中的應(yīng)用

報告人：張國清gqzhang@“刪邊擴(kuò)容”策略在接入網(wǎng)流量優(yōu)化中的應(yīng)用1內(nèi)容提要一、刪邊擴(kuò)容方法簡介二、刪邊擴(kuò)容方法在接入網(wǎng)流量優(yōu)化中的應(yīng)用三、在互聯(lián)網(wǎng)工程中的其它應(yīng)用內(nèi)容提要一、刪邊擴(kuò)容方法簡介2

一、刪邊擴(kuò)容方法簡介背景知識：

網(wǎng)絡(luò)容量序參數(shù)網(wǎng)絡(luò)中累積包的速率網(wǎng)絡(luò)容量網(wǎng)絡(luò)由自由/非擁塞狀態(tài)到擁塞狀態(tài)突變時的臨界RR<無擁塞發(fā)生R>開始擁塞一、刪邊擴(kuò)容方法簡介背景知識：3背景知識一般方法：增加節(jié)點(diǎn)能力、加邊、改變路由策略網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)影響動態(tài)流量（最短路徑路由）均勻網(wǎng)絡(luò)承載更多的網(wǎng)絡(luò)容量無高介數(shù)Hub節(jié)點(diǎn)流量負(fù)載在網(wǎng)絡(luò)均勻分擔(dān)異質(zhì)性網(wǎng)絡(luò)容易發(fā)生擁塞高介數(shù)Hub節(jié)點(diǎn)流量負(fù)載聚集介數(shù)：靜態(tài)拓?fù)浜蛣討B(tài)流量之間的橋梁，在最短路由算法和每個節(jié)點(diǎn)具有相同發(fā)包條件下，介數(shù)恰好量化了一個節(jié)點(diǎn)要處理的流量。數(shù)學(xué)分析：動機(jī)：使異質(zhì)性網(wǎng)絡(luò)趨于均勻背景知識一般方法：增加節(jié)點(diǎn)能力、加邊、改變路由策略4刪邊擴(kuò)容方法步驟：(1)計算每個節(jié)點(diǎn)i的介數(shù)gi(2)給每條邊賦權(quán)Wij=gi

gj

，gi,gj分別是一條邊兩端節(jié)點(diǎn)的介數(shù)，并按邊權(quán)從大到小排序(3)按一定的比例從大到小刪除網(wǎng)絡(luò)的邊，但要保持網(wǎng)絡(luò)連通，如遇到刪邊后網(wǎng)絡(luò)不連通，要保留該邊，再依次刪去后面的邊。(4)按廣泛使用的流量模型，計算網(wǎng)絡(luò)容量Rc。

研究結(jié)果：刪邊擴(kuò)容策略在接入網(wǎng)流量優(yōu)化中的應(yīng)用5試驗(yàn)結(jié)果和討論BA模型下，C=1

不同去邊比例下，序參數(shù)－R曲線網(wǎng)絡(luò)容量和平均最短路徑隨去邊比例變化曲線Guo-QingZhang,DiWang,Guo-JieLi.Enhancingthetransmissionefficiencybyedgedeletioninscale-freenetworks,PhysicalReviewE76,017101(2007)試驗(yàn)結(jié)果和討論BA模型下，C=1不同去邊比例下，序6(0,0.08]內(nèi)網(wǎng)絡(luò)結(jié)構(gòu)改變很小，近似于scale-free容量提高顯著，更有意義大概[0.22,0.35]，近似于ERER圖容量遠(yuǎn)大于BA0.48突跳點(diǎn)時網(wǎng)絡(luò)近似于樹狀結(jié)構(gòu)L迅速增大交叉節(jié)點(diǎn)增多，介數(shù)分布不均勻(0,0.08]內(nèi)網(wǎng)絡(luò)結(jié)構(gòu)改變很小，近似于scale-fre7在城市交通中的例子：例1：交叉口的禁行管理；例2：放射加環(huán)狀在城市交通中的例子：例1：交叉口的禁行管理；8

二、刪邊擴(kuò)容方法在接入網(wǎng)流量優(yōu)化中的應(yīng)用現(xiàn)狀公有網(wǎng)絡(luò)公共場所政府企業(yè)小區(qū)校園家庭網(wǎng)絡(luò)

二、刪邊擴(kuò)容方法在接入網(wǎng)流量優(yōu)化中的應(yīng)用現(xiàn)狀公有網(wǎng)絡(luò)公共場9互聯(lián)網(wǎng)中NAT設(shè)備保有量2006年

33,486千臺2007年約27,200千臺2008年約27,200千臺2002年—2008年具有地址轉(zhuǎn)換（NAT）功能的設(shè)備產(chǎn)量累計1億臺以上，約80%產(chǎn)品銷往北美、歐洲、中國大陸、日本互聯(lián)網(wǎng)中NAT設(shè)備保有量2006年33,486千臺210NAT-BUS現(xiàn)狀多級NAT的存在致使路由無法按物理上的最短路徑轉(zhuǎn)發(fā)，造成了路由瓶頸，無謂地消耗了大量的網(wǎng)絡(luò)帶寬資源，惡化了用戶體驗(yàn)意義在IPv4地址逐步耗盡，而IPv6短時期無法廣泛部署的情況下，基于多級NAT的網(wǎng)絡(luò)結(jié)構(gòu)必然長期存在。優(yōu)化多級NAT環(huán)境下的節(jié)點(diǎn)之間的路由對網(wǎng)絡(luò)的演進(jìn)至關(guān)重要。公有網(wǎng)絡(luò)私有網(wǎng)絡(luò)第一級NAT設(shè)備第二級NAT設(shè)備1、消除瓶頸、優(yōu)化數(shù)據(jù)傳輸路徑、擴(kuò)充網(wǎng)絡(luò)容量2、擴(kuò)大網(wǎng)絡(luò)用戶接入數(shù)量NAT-BUS現(xiàn)狀公有網(wǎng)絡(luò)私有網(wǎng)絡(luò)第一級NAT設(shè)備第二級NA11NAT組網(wǎng)需要解決的關(guān)鍵問題改變TCP/IP應(yīng)用程序間的遂路通知方式。在私有網(wǎng)絡(luò)內(nèi)找到可以協(xié)助通訊雙方進(jìn)行路徑協(xié)商的節(jié)點(diǎn)。（最壞情況下用于轉(zhuǎn)發(fā)）私網(wǎng)穿越算法要能適應(yīng)NAT設(shè)備的多樣性，及NAT組合產(chǎn)生的復(fù)雜性。漏斗型IP限制型IP+端口限制型對稱型應(yīng)用方式研究對SDP協(xié)議的擴(kuò)展與Socket接口的集成作為驅(qū)動程序、應(yīng)用插件NAT組網(wǎng)需要解決的關(guān)鍵問題改變TCP/IP應(yīng)用程序間的遂路12IPVN系統(tǒng)概念模型私有網(wǎng)絡(luò)IPVNSIP呼叫服務(wù)實(shí)體(P)主機(jī)A(H)主機(jī)B(H)公有網(wǎng)絡(luò)SIP信令NAT通道建立服務(wù)實(shí)體(C)NATNAT通道建立NATIPVN系統(tǒng)概念模型私有網(wǎng)絡(luò)IPVNSIP呼叫服務(wù)主機(jī)A主機(jī)13公有網(wǎng)絡(luò)Firewall(NAT)家庭網(wǎng)絡(luò)NAT私有網(wǎng)絡(luò)NAT私有網(wǎng)絡(luò)CCCC微波爐小區(qū)停車廠智能家電及物聯(lián)網(wǎng)絡(luò)公有網(wǎng)絡(luò)Firewall(NAT)家庭網(wǎng)絡(luò)NAT私有網(wǎng)絡(luò)NA14與現(xiàn)有NAT穿越方法的對比對比項(xiàng)IPVNICESTUNTURN目標(biāo)網(wǎng)絡(luò)設(shè)備設(shè)備設(shè)備通道構(gòu)成直通、中繼直通、中繼直通中繼是否進(jìn)行設(shè)備類型測試不需要需要需要不需要直通下穿越設(shè)備類型3種2種2種不支持直通私有網(wǎng)絡(luò)穿越支持，多層穿越不支持不支持不支持通道數(shù)量多個（>=2）一個一個一個通道間管理特征支持不支持不支持不支持算法與應(yīng)用的耦合程度(SDP協(xié)議)低，獨(dú)立于端口描述，可成為獨(dú)立驅(qū)動高，是端口描述的組成部分高，是端口描述的組成部分高，是端口描述的組成部分與現(xiàn)有NAT穿越方法的對比對比項(xiàng)IPVNICESTUNTUR15IPVN核心專利群多層NAT網(wǎng)絡(luò)中面向應(yīng)用的名字注冊系統(tǒng)及方法申請?zhí)?00810102343.3多層NAT環(huán)境下面向應(yīng)用的名字注冊系統(tǒng)及其服務(wù)方法申請?zhí)?00810102278.4一種通信網(wǎng)絡(luò)系統(tǒng)及通信方法、通信設(shè)備申請?zhí)?00810115782.8一種系統(tǒng)終端設(shè)備建立NAT穿越通道的方法申請?zhí)?00810104586.0實(shí)現(xiàn)端到端通信的可配置NAT設(shè)備及其數(shù)據(jù)轉(zhuǎn)發(fā)方法申請?zhí)?00810117963.4多級NAT網(wǎng)絡(luò)中的網(wǎng)絡(luò)地址覆蓋判別設(shè)備、裝置及方法申請?zhí)?00810056962.3同根多層NAT網(wǎng)絡(luò)中服務(wù)資源地址獲取系統(tǒng)及方法（迭代型)申請?zhí)?00810056964.2同根多層NAT網(wǎng)絡(luò)中服務(wù)資源地址獲取系統(tǒng)及方法申請?zhí)?00810057190.5IPVN核心專利群多層NAT網(wǎng)絡(luò)中面向應(yīng)用的名字注冊系統(tǒng)及方16三、在互聯(lián)網(wǎng)工程中的其它應(yīng)用:

3.1覆蓋網(wǎng)中轉(zhuǎn)發(fā)節(jié)點(diǎn)選取方法ABCEFDAS4AS3AS1AS2CoreStubTransit三、在互聯(lián)網(wǎng)工程中的其它應(yīng)用:

3.1覆蓋網(wǎng)中轉(zhuǎn)發(fā)節(jié)點(diǎn)選取17三、在互聯(lián)網(wǎng)工程中的其它應(yīng)用:

3.2網(wǎng)絡(luò)節(jié)能問題與解決方法依據(jù)網(wǎng)絡(luò)負(fù)載自適應(yīng)地調(diào)整活躍鏈路的數(shù)量按哪種策略調(diào)整最優(yōu)化三、在互聯(lián)網(wǎng)工程中的其它應(yīng)用:

3.2網(wǎng)絡(luò)節(jié)能問題與解決方法18表1三種網(wǎng)絡(luò)不同的鏈路關(guān)閉策略達(dá)到的節(jié)能效果圖1三種網(wǎng)絡(luò)不同的鏈路關(guān)閉策略對網(wǎng)絡(luò)吞吐能力的影響“l(fā)inkpowercoordinationforenergyconservationincomplexcommunicationnetworks”,EPL,inpress表1三種網(wǎng)絡(luò)不同的鏈路關(guān)閉策略達(dá)到的節(jié)能效果圖1三種網(wǎng)絡(luò)不19小結(jié)刪邊擴(kuò)容是一種在一定條件下可以擴(kuò)大網(wǎng)絡(luò)容量的路由策略。在實(shí)際工作中更關(guān)注避開大權(quán)重（是介數(shù)而不是度）的邊。在研究中有很多變種，工程中的變種更多。期待今后有更多這方面的研究和實(shí)際應(yīng)用。小結(jié)刪邊擴(kuò)容是一種在一定條件下可以擴(kuò)大網(wǎng)絡(luò)容量的路由策略。20相關(guān)論文Guo-QingZhang,DiWang,andGuo-JieLi,Enhancingthetransmissionefficiencybyedgedeletioninscale-freenetworks,PhysicalReviewE76,017101,2007.Guo-QingZhang,ShiZhou,DiWang,GangYan,andGuo-QiangZhang,Enhancingnetworktransmissioncapacitybyefficientlyallocatingnodecapability,PhysicaA(2010)doi:10.1016/j.physa.2010.09.022.GuoqiangZhangandGuoqingZhang,“Communicationnetworkdesigning:transmissioncapacity,costandscalability”,ScienceinChinaseriesF,accepted.Guo-QiangZhang，linkpowercoordinationforenergyconservationincomplexcommunicationnetworks,EPL,inpress張國清，互聯(lián)網(wǎng)拓?fù)浣Y(jié)構(gòu)知識發(fā)現(xiàn)及其應(yīng)用，通信學(xué)報（預(yù)期2010年10月出版）相關(guān)論文Guo-QingZhang,DiWang,21謝謝！謝謝！22“刪邊擴(kuò)容”策略在接入網(wǎng)流量優(yōu)化中的應(yīng)用

報告人：張國清gqzhang@“刪邊擴(kuò)容”策略在接入網(wǎng)流量優(yōu)化中的應(yīng)用23內(nèi)容提要一、刪邊擴(kuò)容方法簡介二、刪邊擴(kuò)容方法在接入網(wǎng)流量優(yōu)化中的應(yīng)用三、在互聯(lián)網(wǎng)工程中的其它應(yīng)用內(nèi)容提要一、刪邊擴(kuò)容方法簡介24

一、刪邊擴(kuò)容方法簡介背景知識：

網(wǎng)絡(luò)容量序參數(shù)網(wǎng)絡(luò)中累積包的速率網(wǎng)絡(luò)容量網(wǎng)絡(luò)由自由/非擁塞狀態(tài)到擁塞狀態(tài)突變時的臨界RR<無擁塞發(fā)生R>開始擁塞一、刪邊擴(kuò)容方法簡介背景知識：25背景知識一般方法：增加節(jié)點(diǎn)能力、加邊、改變路由策略網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)影響動態(tài)流量（最短路徑路由）均勻網(wǎng)絡(luò)承載更多的網(wǎng)絡(luò)容量無高介數(shù)Hub節(jié)點(diǎn)流量負(fù)載在網(wǎng)絡(luò)均勻分擔(dān)異質(zhì)性網(wǎng)絡(luò)容易發(fā)生擁塞高介數(shù)Hub節(jié)點(diǎn)流量負(fù)載聚集介數(shù)：靜態(tài)拓?fù)浜蛣討B(tài)流量之間的橋梁，在最短路由算法和每個節(jié)點(diǎn)具有相同發(fā)包條件下，介數(shù)恰好量化了一個節(jié)點(diǎn)要處理的流量。數(shù)學(xué)分析：動機(jī)：使異質(zhì)性網(wǎng)絡(luò)趨于均勻背景知識一般方法：增加節(jié)點(diǎn)能力、加邊、改變路由策略26刪邊擴(kuò)容方法步驟：(1)計算每個節(jié)點(diǎn)i的介數(shù)gi(2)給每條邊賦權(quán)Wij=gi

gj

，gi,gj分別是一條邊兩端節(jié)點(diǎn)的介數(shù)，并按邊權(quán)從大到小排序(3)按一定的比例從大到小刪除網(wǎng)絡(luò)的邊，但要保持網(wǎng)絡(luò)連通，如遇到刪邊后網(wǎng)絡(luò)不連通，要保留該邊，再依次刪去后面的邊。(4)按廣泛使用的流量模型，計算網(wǎng)絡(luò)容量Rc。

研究結(jié)果：刪邊擴(kuò)容策略在接入網(wǎng)流量優(yōu)化中的應(yīng)用27試驗(yàn)結(jié)果和討論BA模型下，C=1

不同去邊比例下，序參數(shù)－R曲線網(wǎng)絡(luò)容量和平均最短路徑隨去邊比例變化曲線Guo-QingZhang,DiWang,Guo-JieLi.Enhancingthetransmissionefficiencybyedgedeletioninscale-freenetworks,PhysicalReviewE76,017101(2007)試驗(yàn)結(jié)果和討論BA模型下，C=1不同去邊比例下，序28(0,0.08]內(nèi)網(wǎng)絡(luò)結(jié)構(gòu)改變很小，近似于scale-free容量提高顯著，更有意義大概[0.22,0.35]，近似于ERER圖容量遠(yuǎn)大于BA0.48突跳點(diǎn)時網(wǎng)絡(luò)近似于樹狀結(jié)構(gòu)L迅速增大交叉節(jié)點(diǎn)增多，介數(shù)分布不均勻(0,0.08]內(nèi)網(wǎng)絡(luò)結(jié)構(gòu)改變很小，近似于scale-fre29在城市交通中的例子：例1：交叉口的禁行管理；例2：放射加環(huán)狀在城市交通中的例子：例1：交叉口的禁行管理；30

二、刪邊擴(kuò)容方法在接入網(wǎng)流量優(yōu)化中的應(yīng)用現(xiàn)狀公有網(wǎng)絡(luò)公共場所政府企業(yè)小區(qū)校園家庭網(wǎng)絡(luò)

二、刪邊擴(kuò)容方法在接入網(wǎng)流量優(yōu)化中的應(yīng)用現(xiàn)狀公有網(wǎng)絡(luò)公共場31互聯(lián)網(wǎng)中NAT設(shè)備保有量2006年

33,486千臺2007年約27,200千臺2008年約27,200千臺2002年—2008年具有地址轉(zhuǎn)換（NAT）功能的設(shè)備產(chǎn)量累計1億臺以上，約80%產(chǎn)品銷往北美、歐洲、中國大陸、日本互聯(lián)網(wǎng)中NAT設(shè)備保有量2006年33,486千臺232NAT-BUS現(xiàn)狀多級NAT的存在致使路由無法按物理上的最短路徑轉(zhuǎn)發(fā)，造成了路由瓶頸，無謂地消耗了大量的網(wǎng)絡(luò)帶寬資源，惡化了用戶體驗(yàn)意義在IPv4地址逐步耗盡，而IPv6短時期無法廣泛部署的情況下，基于多級NAT的網(wǎng)絡(luò)結(jié)構(gòu)必然長期存在。優(yōu)化多級NAT環(huán)境下的節(jié)點(diǎn)之間的路由對網(wǎng)絡(luò)的演進(jìn)至關(guān)重要。公有網(wǎng)絡(luò)私有網(wǎng)絡(luò)第一級NAT設(shè)備第二級NAT設(shè)備1、消除瓶頸、優(yōu)化數(shù)據(jù)傳輸路徑、擴(kuò)充網(wǎng)絡(luò)容量2、擴(kuò)大網(wǎng)絡(luò)用戶接入數(shù)量NAT-BUS現(xiàn)狀公有網(wǎng)絡(luò)私有網(wǎng)絡(luò)第一級NAT設(shè)備第二級NA33NAT組網(wǎng)需要解決的關(guān)鍵問題改變TCP/IP應(yīng)用程序間的遂路通知方式。在私有網(wǎng)絡(luò)內(nèi)找到可以協(xié)助通訊雙方進(jìn)行路徑協(xié)商的節(jié)點(diǎn)。（最壞情況下用于轉(zhuǎn)發(fā)）私網(wǎng)穿越算法要能適應(yīng)NAT設(shè)備的多樣性，及NAT組合產(chǎn)生的復(fù)雜性。漏斗型IP限制型IP+端口限制型對稱型應(yīng)用方式研究對SDP協(xié)議的擴(kuò)展與Socket接口的集成作為驅(qū)動程序、應(yīng)用插件NAT組網(wǎng)需要解決的關(guān)鍵問題改變TCP/IP應(yīng)用程序間的遂路34IPVN系統(tǒng)概念模型私有網(wǎng)絡(luò)IPVNSIP呼叫服務(wù)實(shí)體(P)主機(jī)A(H)主機(jī)B(H)公有網(wǎng)絡(luò)SIP信令NAT通道建立服務(wù)實(shí)體(C)NATNAT通道建立NATIPVN系統(tǒng)概念模型私有網(wǎng)絡(luò)IPVNSIP呼叫服務(wù)主機(jī)A主機(jī)35公有網(wǎng)絡(luò)Firewall(NAT)家庭網(wǎng)絡(luò)NAT私有網(wǎng)絡(luò)NAT私有網(wǎng)絡(luò)CCCC微波爐小區(qū)停車廠智能家電及物聯(lián)網(wǎng)絡(luò)公有網(wǎng)絡(luò)Firewall(NAT)家庭網(wǎng)絡(luò)NAT私有網(wǎng)絡(luò)NA36與現(xiàn)有NAT穿越方法的對比對比項(xiàng)IPVNICESTUNTURN目標(biāo)網(wǎng)絡(luò)設(shè)備設(shè)備設(shè)備通道構(gòu)成直通、中繼直通、中繼直通中繼是否進(jìn)行設(shè)備類型測試不需要需要需要不需要直通下穿越設(shè)備類型3種2種2種不支持直通私有網(wǎng)絡(luò)穿越支持，多層穿越不支持不支持不支持通道數(shù)量多個（>=2）一個一個一個通道間管理特征支持不支持不支持不支持算法與應(yīng)用的耦合程度(SDP協(xié)議)低，獨(dú)立于端口描述，可成為獨(dú)立驅(qū)動高，是端口描述的組成部分高，是端口描述的組成部分高，是端口描述的組成部分與現(xiàn)有NAT穿越方法的對比對比項(xiàng)IPVNICESTUNTUR37IPVN核心專利群多層NAT網(wǎng)絡(luò)中面向應(yīng)用的名字注冊系統(tǒng)及方法申請?zhí)?00810102343.3多層NAT環(huán)境下面向應(yīng)用的名字注冊系統(tǒng)及其服務(wù)方法申請?zhí)?00810102278.4一種通信網(wǎng)絡(luò)系統(tǒng)及通信方法、通信設(shè)備申請?zhí)?00810115782.8一種系統(tǒng)終端設(shè)備建立NAT穿越通道的方法申請?zhí)?00810104586.0實(shí)現(xiàn)端到端通信的可配置NAT設(shè)備及其數(shù)據(jù)轉(zhuǎn)發(fā)方法申請?zhí)?00810117963.4多級NAT網(wǎng)絡(luò)中的網(wǎng)絡(luò)地址覆蓋判別設(shè)備、裝置及方法申請?zhí)?00810056962.3同根多層NAT網(wǎng)絡(luò)中服務(wù)資源地址獲取系統(tǒng)及方法（迭代型)申請?zhí)?00810056964.2同根多層NAT網(wǎng)絡(luò)中服務(wù)資源地址獲取系統(tǒng)及方法申請?zhí)?00810057190.5IPVN核心專利群多層NAT網(wǎng)絡(luò)中面向應(yīng)用的名字注冊系統(tǒng)及方38三、在互聯(lián)網(wǎng)工程中的其它應(yīng)用:

3.1覆蓋網(wǎng)中轉(zhuǎn)發(fā)節(jié)點(diǎn)選取方法ABCEFDAS4AS3AS1AS2CoreStubTransit三、在互聯(lián)網(wǎng)工程中的其它應(yīng)用:

3.1覆蓋網(wǎng)中轉(zhuǎn)發(fā)節(jié)點(diǎn)選取39三、在互聯(lián)網(wǎng)工程中的其它應(yīng)用:

3.2網(wǎng)絡(luò)節(jié)能問題與解決方法依據(jù)網(wǎng)絡(luò)負(fù)載自適應(yīng)地調(diào)整活躍鏈路的數(shù)量按哪種策略調(diào)整最優(yōu)化三、在互聯(lián)網(wǎng)工程中的其它應(yīng)用:

3.2網(wǎng)絡(luò)節(jié)能問題與解決方法40表1三種網(wǎng)絡(luò)不同的鏈路關(guān)閉策略達(dá)到的節(jié)能效果圖1三種網(wǎng)絡(luò)不同的鏈路關(guān)閉策略對網(wǎng)絡(luò)吞吐能力的影響“l(fā)inkpowercoordinationforenergyconservationincomplexcommunicationnetworks”,EPL,inpress表1三種網(wǎng)絡(luò)不同的鏈路關(guān)閉策略達(dá)到的節(jié)能效果圖1三種網(wǎng)絡(luò)不41小結(jié)刪邊擴(kuò)容是一種在一定條件下可以擴(kuò)大網(wǎng)絡(luò)容量的路由策略。在實(shí)際工作