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

數(shù)據(jù)通信網(wǎng)絡(luò)設(shè)計的性價比,張國強 guoqiang 2010-10-16,現(xiàn)狀,經(jīng)驗性 一般利用率超過35%考慮升級帶寬，教育網(wǎng)70%升級帶寬，科技網(wǎng)60%升級帶寬 網(wǎng)絡(luò)擁塞頻繁出現(xiàn) 平均鏈路利用率低，但鏈路利用率分布嚴(yán)重不均衡,ISP的鏈路利用率統(tǒng)計,問題,從傳輸?shù)慕嵌龋F(xiàn)有的網(wǎng)絡(luò)設(shè)計是否合理？ 傳輸容量 設(shè)計代價 可擴展性 目標(biāo) 以較低的成本實現(xiàn)高傳輸容量和高可擴展的網(wǎng)絡(luò),流量模型(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)新到達和產(chǎn)生的數(shù)據(jù)包個數(shù)超過C(vi)時，將被存儲在端口的出口緩存隊列中，以FIFO的方式在后面的時間步得到服務(wù) 每個數(shù)據(jù)包都按照特定的路由算法路由 如果有多條路徑，則隨機選一條,流量模型(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ò)進入擁塞態(tài)。 從自由態(tài)到擁塞態(tài)存在一個相變點Rc。,網(wǎng)絡(luò)設(shè)計目標(biāo)(1),網(wǎng)絡(luò)傳輸能力 用Rc衡量,網(wǎng)絡(luò)設(shè)計目標(biāo)(2),網(wǎng)絡(luò)設(shè)計代價 經(jīng)濟成本 技術(shù)瓶頸 能否用現(xiàn)有技術(shù)水平實現(xiàn),設(shè)計代價度量方法： 在 固定的前提下，用 來表征一個網(wǎng)絡(luò)的設(shè)計代價,網(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)(4),端到端性能 通過平均傳輸路徑長度衡量,網(wǎng)絡(luò)設(shè)計選擇(1),拓撲結(jié)構(gòu) 隨機網(wǎng)絡(luò)(ER) 小世界網(wǎng)絡(luò)(WS) 網(wǎng)格(Lattice) 環(huán)(Ring) BA PA HOT,網(wǎng)絡(luò)設(shè)計選擇(2),路由算法(topology-based) 最短路徑（跳數(shù)）路由 RIP, BGP 有效路由(Yan06) 最小化路徑的節(jié)點度之和,網(wǎng)絡(luò)設(shè)計選擇(3),帶寬分配策略 均勻 與度成正比 與介數(shù)成正比 與有效介數(shù)成正比,問題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)時達到。,（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）時，有,（3）（BC, SPR)是Rc=2M/L的必要條件 Rc=2M/L當(dāng)且僅當(dāng) a) ，表明路由必須是最短路徑路由 b)網(wǎng)絡(luò)平均每一步能平均移動2M個數(shù)據(jù)包到下一跳 在SPR中，在自由態(tài)平均每個時間步到達端口vi的數(shù)據(jù)包個數(shù)平均為 當(dāng)R=2M/L時，網(wǎng)絡(luò)中平均的數(shù)據(jù)包個數(shù)為 為了每個時間步移動2M個數(shù)據(jù)包，每個端口需要移動 個數(shù)據(jù)包，正對應(yīng)了BC的帶寬分配策略,(a) BA,(b) Regular networks,（1）不同的網(wǎng)絡(luò)能呈現(xiàn)不同的網(wǎng)絡(luò)設(shè)計目標(biāo)可行解空間 （2）除了完全規(guī)則的網(wǎng)絡(luò)，最大Rc和最小Cmax無法同時達到，存在折中問題,傳輸容量和設(shè)計代價的折中問題,Rc,Cmax,可擴展性,Rc,Cmax,平均路徑長度,真實路由器拓撲和路由協(xié)議,真實ISP路由器級拓撲在不同帶寬賦值策略和路由協(xié)議組合下的結(jié)果： 1 實際ISP的路由器級拓撲與HOT模型類似 2 OSPF的weight賦值策略更傾向于聚合流量,總結(jié),給出了更符合實際的網(wǎng)絡(luò)流模型 提出了網(wǎng)絡(luò)設(shè)計是一個多目標(biāo)優(yōu)化的過程 傳輸容量、設(shè)計代價、可擴展性 理論分析了網(wǎng)絡(luò)設(shè)計方案的可行解空間 探討了網(wǎng)絡(luò)設(shè)計的性價比和可擴展性,與本報告相關(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