1、INSTITUTE OF COMPUTING TECHNOLOGYINSTITUTE OF COMPUTING TECHNOLOGY1數據通信網絡設計的性價比數據通信網絡設計的性價比2010-10-16INSTITUTE OF COMPUTING TECHNOLOGY2現狀現狀l經驗性l一般利用率超過35%考慮升級帶寬，教育網70%升級帶寬，科技網60%升級帶寬l網絡擁塞頻繁出現l平均鏈路利用率低，但鏈路利用率分布嚴重不均衡INSTITUTE OF COMPUTING TECHNOLOGY3ISP的鏈路利用率統計INSTITUTE OF COMPUTING TECHNOLOGY4問題問題l從傳

2、輸的角度，現有的網絡設計是否合理？l傳輸容量l設計代價l可擴展性l目標l以較低的成本實現高傳輸容量和高可擴展的網絡INSTITUTE OF COMPUTING TECHNOLOGY5流量模型流量模型(1)l每個節點都可以產生、轉發、接收數據包l每個時間步，R個數據包注入網絡l數據包具有隨機的源和目標地址l每個路由器端口vi都被賦值帶寬C(vi) ,表示在一個時間步最多能傳輸的數據包個數,也記為C(e)l擁塞發生在端口級l當新到達和產生的數據包個數超過C(vi)時，將被存儲在端口的出口緩存隊列中，以FIFO的方式在后面的時間步得到服務l每個數據包都按照特定的路由算法路由l如果有多條路徑，則隨機選

3、一條INSTITUTE OF COMPUTING TECHNOLOGY6流量模型流量模型(2)l當網絡報文產生率R較小時，每個報文都能得到及時處理。此時，網絡報文產生率與遞交率相等，網絡處于自由態。l當R增加到一定程度時，網絡報文產生率R將超過網絡的遞交能力，網絡進入擁塞態。l從自由態到擁塞態存在一個相變點Rc。INSTITUTE OF COMPUTING TECHNOLOGY7網絡設計目標網絡設計目標(1)l網絡傳輸能力l用Rc衡量INSTITUTE OF COMPUTING TECHNOLOGY8網絡設計目標網絡設計目標(2)l網絡設計代價l經濟成本 l技術瓶頸能否用現有技術水平實現設計代

4、價度量方法：在 固定的前提下，用 來表征一個網絡的設計代價INSTITUTE OF COMPUTING TECHNOLOGY9網絡設計目標網絡設計目標(3)l可擴展性l現實的網絡特征l大規模l演化l可擴展的網絡設計對網絡投資者和運營者具有長期的好處l度量方法l用Rc和Cmax隨網絡規模的增長趨勢來衡量INSTITUTE OF COMPUTING TECHNOLOGY10網絡設計目標網絡設計目標(4)l端到端性能l通過平均傳輸路徑長度衡量INSTITUTE OF COMPUTING TECHNOLOGY11網絡設計選擇網絡設計選擇(1)l拓撲結構l隨機網絡(ER)l小世界網絡(WS)l網格(La

5、ttice)l環(Ring)lBAlPAlHOTINSTITUTE OF COMPUTING TECHNOLOGY12網絡設計選擇網絡設計選擇(2)l路由算法(topology-based)l最短路徑（跳數）路由lRIP, BGPl有效路由(Yan06)l最小化路徑的節點度之和INSTITUTE OF COMPUTING TECHNOLOGY13網絡設計選擇網絡設計選擇(3)l帶寬分配策略l均勻l與度成正比l與介數成正比l與有效介數成正比INSTITUTE OF COMPUTING TECHNOLOGY14問題問題1：Rc和和Cmax的可行范圍的可行范圍lCmax的取值范圍1, MlRc的最小

6、值為0,最大值由如下定理給出：l定理：給定網絡G，對任何一個網絡設計方案，其Rc的上界是2M/L（L是平均最短路徑長度）；這一上界當且僅當采用（BC, SPR)時達到。INSTITUTE OF COMPUTING TECHNOLOGY15（1）證明2M/L為上界 網絡每個時間步最多移動2M個數據包到下一跳，而每個數據包平均需要移動 步，意味著網絡每個時間步平均最多消費 個數據包。依據Little律，有（2）證明2M/L為上確界，即(BC, SPR)是Rc=2M/L的充分條件當采用（BC, SPR）時，有INSTITUTE OF COMPUTING TECHNOLOGY16（3）（BC, SPR

7、)是Rc=2M/L的必要條件 Rc=2M/L當且僅當a) ，表明路由必須是最短路徑路由b)網絡平均每一步能平均移動2M個數據包到下一跳 在SPR中，在自由態平均每個時間步到達端口vi的數據包個數平均為 當R=2M/L時，網絡中平均的數據包個數為 為了每個時間步移動2M個數據包，每個端口需要移動 個數據包，正對應了BC的帶寬分配策略INSTITUTE OF COMPUTING TECHNOLOGY17(a) BA(b) Regular networks（1）不同的網絡能呈現不同的網絡設計目標可行解空間（2）除了完全規則的網絡，最大Rc和最小Cmax無法同時達到，存在折中問題INSTITUTE O

8、F COMPUTING TECHNOLOGY18傳輸容量和設計代價的折中問題傳輸容量和設計代價的折中問題RcCmaxINSTITUTE OF COMPUTING TECHNOLOGY19可擴展性可擴展性RcCmaxINSTITUTE OF COMPUTING TECHNOLOGY20平均路徑長度平均路徑長度INSTITUTE OF COMPUTING TECHNOLOGY21真實路由器拓撲和路由協議真實路由器拓撲和路由協議真實ISP路由器級拓撲在不同帶寬賦值策略和路由協議組合下的結果：1 實際ISP的路由器級拓撲與HOT模型類似2 OSPF的weight賦值策略更傾向于聚合流量INSTITUT

9、E OF COMPUTING TECHNOLOGY22總結總結l給出了更符合實際的網絡流模型l提出了網絡設計是一個多目標優化的過程l理論分析了網絡設計方案的可行解空間l探討了網絡設計的性價比和可擴展性INSTITUTE OF COMPUTING TECHNOLOGY23與本報告相關文章與本報告相關文章lGuoqiang Zhang, “On cost-effective communication network designing”, Europhysics Lettters (EPL), 89, 38003, 2010.lGuoqiang Zhang and Guoqing Zhang,

10、“Communication network designing: transmission capacity, cost and scalability”, Science in China series F, accepted.lGuoqing 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.phy

11、sa.2010.09.022.lGuoqing Zhang, Di Wang, and Guojie Li, “Enhancing the transmission efficiency by edge deletion in scale-free networks”, Physical Review E 76, 017101, 2007.INSTITUTE OF COMPUTING TECHNOLOGY24其它復雜網絡方面的文章其它復雜網絡方面的文章lGuoqiang Zhang, “Traversability of the graph space with given degree se

12、quence under edge rewiring”, Electronics Letters, 46(5), 351-352, 2010.lGuoqiang Zhang, “link power coordination for energy conservation in complex communication networks”, Europhysics Letters, accepted， available online at: .lGuoqiang Zhang, Brono Quotin, and Shi Zhou, “Phase changes in the evoluti

13、on of the IPv4 and IPv6 AS-level Internet topologies”, Computer Communications, doi:10.1016/com.2010.06.004 , 2010.lGuoqing Zhang, Guoqiang Zhang, Su-Qi Cheng, and Tao Zhou, “Symbiotic effect: a guideline for network modeling method”, Europhysics Letters, 87, 68002, 2009.lGuoqing Zhang, Guoqiang Zhang, Qingfeng Yang, Suqi Cheng, and Tao Zhou, “Evolution of the Internet and it