數(shù)據(jù)通信網(wǎng)絡(luò)設(shè)計的性價比張國強guoqiang@2010-10-16數(shù)據(jù)通信網(wǎng)絡(luò)設(shè)計的性價比張國強1現(xiàn)狀經(jīng)驗性一般利用率超過35%考慮升級帶寬，教育網(wǎng)70%升級帶寬，科技網(wǎng)60%升級帶寬網(wǎng)絡(luò)擁塞頻繁出現(xiàn)平均鏈路利用率低，但鏈路利用率分布嚴(yán)重不均衡現(xiàn)狀經(jīng)驗性2ISP的鏈路利用率統(tǒng)計ISP的鏈路利用率統(tǒng)計3問題從傳輸?shù)慕嵌?，現(xiàn)有的網(wǎng)絡(luò)設(shè)計是否合理？傳輸容量設(shè)計代價可擴展性目標(biāo)以較低的成本實現(xiàn)高傳輸容量和高可擴展的網(wǎng)絡(luò)問題從傳輸?shù)慕嵌?，現(xiàn)有的網(wǎng)絡(luò)設(shè)計是否合理？4流量模型(1)每個節(jié)點都可以產(chǎn)生、轉(zhuǎn)發(fā)、接收數(shù)據(jù)包每個時間步，R個數(shù)據(jù)包注入網(wǎng)絡(luò)數(shù)據(jù)包具有隨機的源和目標(biāo)地址每個路由器端口vi都被賦值帶寬C(vi),表示在一個時間步最多能傳輸?shù)臄?shù)據(jù)包個數(shù),也記為C(e)擁塞發(fā)生在端口級當(dāng)新到達(dá)和產(chǎn)生的數(shù)據(jù)包個數(shù)超過C(vi)時，將被存儲在端口的出口緩存隊列中，以FIFO的方式在后面的時間步得到服務(wù)每個數(shù)據(jù)包都按照特定的路由算法路由如果有多條路徑，則隨機選一條流量模型(1)每個節(jié)點都可以產(chǎn)生、轉(zhuǎn)發(fā)、接收數(shù)據(jù)包5流量模型(2)當(dāng)網(wǎng)絡(luò)報文產(chǎn)生率R較小時，每個報文都能得到及時處理。此時，網(wǎng)絡(luò)報文產(chǎn)生率與遞交率相等，網(wǎng)絡(luò)處于自由態(tài)。當(dāng)R增加到一定程度時，網(wǎng)絡(luò)報文產(chǎn)生率R將超過網(wǎng)絡(luò)的遞交能力，網(wǎng)絡(luò)進(jìn)入擁塞態(tài)。從自由態(tài)到擁塞態(tài)存在一個相變點Rc。流量模型(2)當(dāng)網(wǎng)絡(luò)報文產(chǎn)生率R較小時，每個報文都能得到及時6網(wǎng)絡(luò)設(shè)計目標(biāo)(1)網(wǎng)絡(luò)傳輸能力用Rc衡量網(wǎng)絡(luò)設(shè)計目標(biāo)(1)網(wǎng)絡(luò)傳輸能力7網(wǎng)絡(luò)設(shè)計目標(biāo)(2)網(wǎng)絡(luò)設(shè)計代價經(jīng)濟(jì)成本

技術(shù)瓶頸能否用現(xiàn)有技術(shù)水平實現(xiàn)設(shè)計代價度量方法：在固定的前提下，用來表征一個網(wǎng)絡(luò)的設(shè)計代價網(wǎng)絡(luò)設(shè)計目標(biāo)(2)網(wǎng)絡(luò)設(shè)計代價設(shè)計代價度量方法：8網(wǎng)絡(luò)設(shè)計目標(biāo)(3)可擴展性現(xiàn)實的網(wǎng)絡(luò)特征大規(guī)模演化可擴展的網(wǎng)絡(luò)設(shè)計對網(wǎng)絡(luò)投資者和運營者具有長期的好處度量方法用Rc和Cmax隨網(wǎng)絡(luò)規(guī)模的增長趨勢來衡量網(wǎng)絡(luò)設(shè)計目標(biāo)(3)可擴展性9網(wǎng)絡(luò)設(shè)計目標(biāo)(4)端到端性能通過平均傳輸路徑長度衡量網(wǎng)絡(luò)設(shè)計目標(biāo)(4)端到端性能10網(wǎng)絡(luò)設(shè)計選擇(1)拓?fù)浣Y(jié)構(gòu)隨機網(wǎng)絡(luò)(ER)小世界網(wǎng)絡(luò)(WS)網(wǎng)格(Lattice)環(huán)(Ring)BAPAHOT網(wǎng)絡(luò)設(shè)計選擇(1)拓?fù)浣Y(jié)構(gòu)11網(wǎng)絡(luò)設(shè)計選擇(2)路由算法(topology-based)最短路徑（跳數(shù)）路由RIP,BGP有效路由(Yan’06)最小化路徑的節(jié)點度之和網(wǎng)絡(luò)設(shè)計選擇(2)路由算法(topology-based)12網(wǎng)絡(luò)設(shè)計選擇(3)帶寬分配策略均勻與度成正比與介數(shù)成正比與有效介數(shù)成正比網(wǎng)絡(luò)設(shè)計選擇(3)帶寬分配策略13問題1：Rc和Cmax的可行范圍Cmax的取值范圍[1,M]Rc的最小值為0,最大值由如下定理給出：定理：給定網(wǎng)絡(luò)G，對任何一個網(wǎng)絡(luò)設(shè)計方案，其Rc的上界是2M/L（L是平均最短路徑長度）；這一上界當(dāng)且僅當(dāng)采用（BC,SPR)時達(dá)到。問題1：Rc和Cmax的可行范圍Cmax的取值范圍[1,M14（1）證明2M/L為上界

網(wǎng)絡(luò)每個時間步最多移動2M個數(shù)據(jù)包到下一跳，而每個數(shù)據(jù)包平均需要移動步，意味著網(wǎng)絡(luò)每個時間步平均最多消費個數(shù)據(jù)包。依據(jù)Little律，有（2）證明2M/L為上確界，即(BC,SPR)是Rc=2M/L的充分條件當(dāng)采用（BC,SPR）時，有（1）證明2M/L為上界15（3）（BC,SPR)是Rc=2M/L的必要條件Rc=2M/L當(dāng)且僅當(dāng)a)，表明路由必須是最短路徑路由b)網(wǎng)絡(luò)平均每一步能平均移動2M個數(shù)據(jù)包到下一跳在SPR中，在自由態(tài)平均每個時間步到達(dá)端口vi的數(shù)據(jù)包個數(shù)平均為當(dāng)R=2M/L時，網(wǎng)絡(luò)中平均的數(shù)據(jù)包個數(shù)為為了每個時間步移動2M個數(shù)據(jù)包，每個端口需要移動個數(shù)據(jù)包，正對應(yīng)了BC的帶寬分配策略（3）（BC,SPR)是Rc=2M/L的必要條件16(a)BA(b)Regularnetworks（1）不同的網(wǎng)絡(luò)能呈現(xiàn)不同的網(wǎng)絡(luò)設(shè)計目標(biāo)可行解空間（2）除了完全規(guī)則的網(wǎng)絡(luò)，最大Rc和最小Cmax無法同時達(dá)到，存在折中問題(a)BA(b)Regularnetworks（1）不17傳輸容量和設(shè)計代價的折中問題RcCmax傳輸容量和設(shè)計代價的折中問題RcCmax18可擴展性RcCmax可擴展性RcCmax19平均路徑長度平均路徑長度20真實路由器拓?fù)浜吐酚蓞f(xié)議真實ISP路由器級拓?fù)湓诓煌瑤捹x值策略和路由協(xié)議組合下的結(jié)果：1實際ISP的路由器級拓?fù)渑cHOT模型類似2OSPF的weight賦值策略更傾向于聚合流量真實路由器拓?fù)浜吐酚蓞f(xié)議真實ISP路由器級拓?fù)湓诓煌瑤捹x值21總結(jié)給出了更符合實際的網(wǎng)絡(luò)流模型提出了網(wǎng)絡(luò)設(shè)計是一個多目標(biāo)優(yōu)化的過程理論分析了網(wǎng)絡(luò)設(shè)計方案的可行解空間探討了網(wǎng)絡(luò)設(shè)計的性價比和可擴展性總結(jié)給出了更符合實際的網(wǎng)絡(luò)流模型22與本報告相關(guān)文章GuoqiangZhang,“Oncost-effectivecommunicationnetworkdesigning”,EurophysicsLettters(EPL),89,38003,2010.GuoqiangZhangandGuoqingZhang,“Communicationnetworkdesigning:transmissioncapacity,costandscalability”,ScienceinChinaseriesF,accepted.GuoqingZhang,ShiZhou,DiWang,GangYan,andGuoqiangZhang,“Enhancingnetworktransmissioncapacitybyefficientlyallocatingnodecapability”,PhysicaA(2010)doi:10.1016/j.physa.2010.09.022.GuoqingZhang,DiWang,andGuojieLi,“Enhancingthetransmissionefficiencybyedgedeletioninscale-freenetworks”,PhysicalReviewE76,017101,2007.與本報告相關(guān)文章GuoqiangZhang,“Onco23其它復(fù)雜網(wǎng)絡(luò)方面的文章GuoqiangZhang,“Traversabilityofthegraphspacewithgivendegreesequenceunderedgerewiring”,ElectronicsLetters,46(5),351-352,2010.GuoqiangZhang,“l(fā)inkpowercoordinationforenergyconservationincomplexcommunicationnetworks”,EurophysicsLetters,accepted，availableonlineat:/abs/1010.1894.GuoqiangZhang,BronoQuotin,andShiZhou,“PhasechangesintheevolutionoftheIPv4andIPv6AS-levelInternettopologies”,ComputerCommunications,doi:10.1016/com.2010.06.004

,2010.GuoqingZhang,GuoqiangZhang,Su-QiCheng,andTaoZhou,“Symbioticeffect:aguidelinefornetworkmodelingmethod”,EurophysicsLetters,87,68002,2009.GuoqingZhang,GuoqiangZhang,QingfengYang,SuqiCheng,andTaoZhou,“EvolutionoftheInternetanditscores”,NewJournalofPh