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

數(shù)據(jù)通信網(wǎng)絡(luò)設(shè)計(jì)的性價(jià)比,張國(guó)強(qiáng) guoqiang 2010-10-16,現(xiàn)狀,經(jīng)驗(yàn)性 一般利用率超過(guò)35%考慮升級(jí)帶寬，教育網(wǎng)70%升級(jí)帶寬，科技網(wǎng)60%升級(jí)帶寬 網(wǎng)絡(luò)擁塞頻繁出現(xiàn) 平均鏈路利用率低，但鏈路利用率分布嚴(yán)重不均衡,ISP的鏈路利用率統(tǒng)計(jì),問(wèn)題,從傳輸?shù)慕嵌?，現(xiàn)有的網(wǎng)絡(luò)設(shè)計(jì)是否合理？ 傳輸容量 設(shè)計(jì)代價(jià) 可擴(kuò)展性 目標(biāo) 以較低的成本實(shí)現(xiàn)高傳輸容量和高可擴(kuò)展的網(wǎng)絡(luò),流量模型(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ù)超過(guò)C(vi)時(shí)，將被存儲(chǔ)在端口的出口緩存隊(duì)列中，以FIFO的方式在后面的時(shí)間步得到服務(wù) 每個(gè)數(shù)據(jù)包都按照特定的路由算法路由 如果有多條路徑，則隨機(jī)選一條,流量模型(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將超過(guò)網(wǎng)絡(luò)的遞交能力，網(wǎng)絡(luò)進(jìn)入擁塞態(tài)。 從自由態(tài)到擁塞態(tài)存在一個(gè)相變點(diǎn)Rc。,網(wǎng)絡(luò)設(shè)計(jì)目標(biāo)(1),網(wǎng)絡(luò)傳輸能力 用Rc衡量,網(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à)度量方法： 在 固定的前提下，用 來(lái)表征一個(gè)網(wǎng)絡(luò)的設(shè)計(jì)代價(jià),網(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ì)來(lái)衡量,網(wǎng)絡(luò)設(shè)計(jì)目標(biāo)(4),端到端性能 通過(guò)平均傳輸路徑長(zhǎng)度衡量,網(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) BA PA HOT,網(wǎng)絡(luò)設(shè)計(jì)選擇(2),路由算法(topology-based) 最短路徑（跳數(shù)）路由 RIP, BGP 有效路由(Yan06) 最小化路徑的節(jié)點(diǎn)度之和,網(wǎng)絡(luò)設(shè)計(jì)選擇(3),帶寬分配策略 均勻 與度成正比 與介數(shù)成正比 與有效介數(shù)成正比,問(wèn)題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）證明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í)，有,（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的帶寬分配策略,(a) BA,(b) Regular networks,（1）不同的網(wǎng)絡(luò)能呈現(xiàn)不同的網(wǎng)絡(luò)設(shè)計(jì)目標(biāo)可行解空間 （2）除了完全規(guī)則的網(wǎng)絡(luò)，最大Rc和最小Cmax無(wú)法同時(shí)達(dá)到，存在折中問(wèn)題,傳輸容量和設(shè)計(jì)代價(jià)的折中問(wèn)題,Rc,Cmax,可擴(kuò)展性,Rc,Cmax,平均路徑長(zhǎng)度,真實(shí)路由器拓?fù)浜吐酚蓞f(xié)議,真實(shí)ISP路由器級(jí)拓?fù)湓诓煌瑤捹x值策略和路由協(xié)議組合下的結(jié)果： 1 實(shí)際ISP的路由器級(jí)拓?fù)渑cHOT模型類(lèi)似 2 OSPF的weight賦值策略更傾向于聚合流量,總結(jié),給出了更符合實(shí)際的網(wǎng)絡(luò)流模型 提出了網(wǎng)絡(luò)設(shè)計(jì)是一個(gè)多目標(biāo)優(yōu)化的過(guò)程 傳輸容量、設(shè)計(jì)代價(jià)、可擴(kuò)展性 理論分析了網(wǎng)絡(luò)設(shè)計(jì)方案的可行解空間 探討了網(wǎng)絡(luò)設(shè)計(jì)的性價(jià)比和可擴(kuò)展性,與本報(bào)告相關(guān)文章,Guoqiang Zhang, “On cost-effective communication network designing”, Europhysics Lettters (EPL), 89, 38003, 2010. Guoqiang Zhang and Guoqing Zhang, “Communication network designing: transmission capacity, cost and scalability”, Science in China series F, accepted. Guoqing Zhang, Shi Zhou, Di Wang, Gang Yan, and Guoqiang Zhang, “Enhancing network transmission capacity by efficiently allocating node capability”, Physica A (2010) doi:10.1016/j.physa.2010.09.022. Guoqing Zhang, Di Wang, and Guojie Li, “Enhancing the transmission efficiency by edge deletion in scale-free networks”, Physical Review E 76, 017101, 2007.,其它復(fù)雜網(wǎng)絡(luò)方面的文章,Guoqiang Zhang, “Traversability of the graph space with given degree sequence under edge rewiring”, Electronics Letters, 46(5), 351-352, 2010. Guoqiang Zhang, “l(fā)ink power coordination for energy conservation in complex communication networks”, Europhysics Letters, accepted， available online at: /abs/1010.1894. Guoqiang Zhang, Brono Quotin, and Shi Zhou, “Phase changes in the evolution of the IPv4 and IPv6 AS-level Internet topologies”, Computer Communications, doi:10.1016/com.2010.06.004 , 2010. Guoqing Zhang, Guoqiang Zhang, Su-Qi Cheng, and Tao Zhou, “Symbiotic effect: a guideline for network modeling method”, Europhysics Letters, 87, 68002, 2009. Guoqing Zhang, Guoqiang Zhang, Qingfeng Yang, Suqi Cheng, and Tao Zhou, “Evolution of the Internet and its cores”, New Jo