數(shù)據(jù)通信網(wǎng)絡(luò)設(shè)計(jì)的性價(jià)比課件

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

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

網(wǎng)絡(luò)每個(gè)時(shí)間步最多移動(dòng)2M個(gè)數(shù)據(jù)包到下一跳，而每個(gè)數(shù)據(jù)包平均需要移動(dòng)步，意味著網(wǎng)絡(luò)每個(gè)時(shí)間步平均最多消費(fèi)個(gè)數(shù)據(jù)包。依據(jù)Little律，有（2）證明2M/L為上確界，即(BC,SPR)是Rc=2M/L的充分條件當(dāng)采用（BC,SPR）時(shí)，有（1）證明2M/L為上界15（3）（BC,SPR)是Rc=2M/L的必要條件Rc=2M/L當(dāng)且僅當(dāng)a)，表明路由必須是最短路徑路由b)網(wǎng)絡(luò)平均每一步能平均移動(dòng)2M個(gè)數(shù)據(jù)包到下一跳在SPR中，在自由態(tài)平均每個(gè)時(shí)間步到達(dá)端口vi的數(shù)據(jù)包個(gè)數(shù)平均為當(dāng)R=2M/L時(shí)，網(wǎng)絡(luò)中平均的數(shù)據(jù)包個(gè)數(shù)為為了每個(gè)時(shí)間步移動(dòng)2M個(gè)數(shù)據(jù)包，每個(gè)端口需要移動(dòng)個(gè)數(shù)據(jù)包，正對(duì)應(yīng)了BC的帶寬分配策略（3）（BC,SPR)是Rc=2M/L的必要條件16(a)BA(b)Regularnetworks（1）不同的網(wǎng)絡(luò)能呈現(xiàn)不同的網(wǎng)絡(luò)設(shè)計(jì)目標(biāo)可行解空間（2）除了完全規(guī)則的網(wǎng)絡(luò)，最大Rc和最小Cmax無法同時(shí)達(dá)到，存在折中問題(a)BA(b)Regularnetworks（1）不17傳輸容量和設(shè)計(jì)代價(jià)的折中問題RcCmax傳輸容量和設(shè)計(jì)代價(jià)的折中問題RcCmax18可擴(kuò)展性RcCmax可擴(kuò)展性RcCmax19平均路徑長(zhǎng)度平均路徑長(zhǎng)度20真實(shí)路由器拓?fù)浜吐酚蓞f(xié)議真實(shí)ISP路由器級(jí)拓?fù)湓诓煌瑤捹x值策略和路由協(xié)議組合下的結(jié)果：1實(shí)際ISP的路由器級(jí)拓?fù)渑cHOT模型類似2OSPF的weight賦值策略更傾向于聚合流量真實(shí)路由器拓?fù)浜吐酚蓞f(xié)議真實(shí)ISP路由器級(jí)拓?fù)湓诓煌瑤捹x值21總結(jié)給出了更符合實(shí)際的網(wǎng)絡(luò)流模型提出了網(wǎng)絡(luò)設(shè)計(jì)是一個(gè)多目標(biāo)優(yōu)化的過程理論分析了網(wǎng)絡(luò)設(shè)計(jì)方案的可行解空間探討了網(wǎng)絡(luò)設(shè)計(jì)的性價(jià)比和可擴(kuò)展性總結(jié)給出了更符合實(shí)際的網(wǎng)絡(luò)流模型22與本報(bào)告相關(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.與本報(bào)告相關(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