1、INSTITUTE OF COMPUTING TECHNOLOGYINSTITUTE OF COMPUTING TECHNOLOGY数据通信网络设计的性价比数据通信网络设计的性价比张国强2010-10-16INSTITUTE OF COMPUTING TECHNOLOGY现状现状l经验性l一般利用率超过35%考虑升级带宽，教育网70%升级带宽，科技网60%升级带宽l网络拥塞频繁出现l平均链路利用率低，但链路利用率分布严重不均衡INSTITUTE OF COMPUTING TECHNOLOGYISP的链路利用率统计INSTITUTE OF COMPUTING TECHNOLOGY问题问题l从传输
2、的角度，现有的网络设计是否合理？l传输容量l设计代价l可扩展性l目标l以较低的成本实现高传输容量和高可扩展的网络INSTITUTE OF COMPUTING TECHNOLOGY流量模型流量模型(1)l每个节点都可以产生、转发、接收数据包l每个时间步，R个数据包注入网络l数据包具有随机的源和目标地址l每个路由器端口vi都被赋值带宽C(vi),表示在一个时间步最多能传输的数据包个数,也记为C(e)l拥塞发生在端口级l当新到达和产生的数据包个数超过C(vi)时，将被存储在端口的出口缓存队列中，以FIFO的方式在后面的时间步得到服务l每个数据包都按照特定的路由算法路由l如果有多条路径，则随机选一条I
3、NSTITUTE OF COMPUTING TECHNOLOGY流量模型流量模型(2)l当网络报文产生率R较小时，每个报文都能得到及时处理。此时，网络报文产生率与递交率相等，网络处于自由态。l当R增加到一定程度时，网络报文产生率R将超过网络的递交能力，网络进入拥塞态。l从自由态到拥塞态存在一个相变点Rc。INSTITUTE OF COMPUTING TECHNOLOGY网络设计目标网络设计目标(1)l网络传输能力l用Rc衡量INSTITUTE OF COMPUTING TECHNOLOGY网络设计目标网络设计目标(2)l网络设计代价l经济成本 l技术瓶颈能否用现有技术水平实现设计代价度量方法：
4、在 固定的前提下，用 来表征一个网络的设计代价INSTITUTE OF COMPUTING TECHNOLOGY网络设计目标网络设计目标(3)l可扩展性l现实的网络特征l大规模l演化l可扩展的网络设计对网络投资者和运营者具有长期的好处l度量方法l用Rc和Cmax随网络规模的增长趋势来衡量INSTITUTE OF COMPUTING TECHNOLOGY网络设计目标网络设计目标(4)l端到端性能l通过平均传输路径长度衡量INSTITUTE OF COMPUTING TECHNOLOGY网络设计选择网络设计选择(1)l拓扑结构l随机网络(ER)l小世界网络(WS)l网格(Lattice)l环(Ri
5、ng)lBAlPAlHOTINSTITUTE OF COMPUTING TECHNOLOGY网络设计选择网络设计选择(2)l路由算法(topology-based)l最短路径（跳数）路由lRIP,BGPl有效路由(Yan06)l最小化路径的节点度之和INSTITUTE OF COMPUTING TECHNOLOGY网络设计选择网络设计选择(3)l带宽分配策略l均匀l与度成正比l与介数成正比l与有效介数成正比INSTITUTE OF COMPUTING TECHNOLOGY问题问题1：Rc和和Cmax的可行范围的可行范围lCmax的取值范围1,MlRc的最小值为0,最大值由如下定理给出：l定理：
6、给定网络G，对任何一个网络设计方案，其Rc的上界是2M/L（L是平均最短路径长度）；这一上界当且仅当采用（BC,SPR)时达到。INSTITUTE OF COMPUTING TECHNOLOGY（1）证明2M/L为上界 网络每个时间步最多移动2M个数据包到下一跳，而每个数据包平均需要移动 步，意味着网络每个时间步平均最多消费 个数据包。依据Little律，有（2）证明2M/L为上确界，即(BC,SPR)是Rc=2M/L的充分条件当采用（BC,SPR）时，有INSTITUTE OF COMPUTING TECHNOLOGY（3）（BC,SPR)是Rc=2M/L的必要条件 Rc=2M/L当且仅当a
7、)，表明路由必须是最短路径路由b)网络平均每一步能平均移动2M个数据包到下一跳 在SPR中，在自由态平均每个时间步到达端口vi的数据包个数平均为 当R=2M/L时，网络中平均的数据包个数为 为了每个时间步移动2M个数据包，每个端口需要移动 个数据包，正对应了BC的带宽分配策略INSTITUTE OF COMPUTING TECHNOLOGY(a)BA(b)Regular networks（1）不同的网络能呈现不同的网络设计目标可行解空间（2）除了完全规则的网络，最大Rc和最小Cmax无法同时达到，存在折中问题INSTITUTE OF COMPUTING TECHNOLOGY传输容量和设计代价的
8、折中问题传输容量和设计代价的折中问题RcCmaxINSTITUTE OF COMPUTING TECHNOLOGY可扩展性可扩展性RcCmaxINSTITUTE OF COMPUTING TECHNOLOGY平均路径长度平均路径长度INSTITUTE OF COMPUTING TECHNOLOGY真实路由器拓扑和路由协议真实路由器拓扑和路由协议真实ISP路由器级拓扑在不同带宽赋值策略和路由协议组合下的结果：1 实际ISP的路由器级拓扑与HOT模型类似2 OSPF的weight赋值策略更倾向于聚合流量INSTITUTE OF COMPUTING TECHNOLOGY总结总结l给出了更符合实际的网
9、络流模型l提出了网络设计是一个多目标优化的过程l理论分析了网络设计方案的可行解空间l探讨了网络设计的性价比和可扩展性INSTITUTE OF COMPUTING TECHNOLOGY与本报告相关文章与本报告相关文章1.Guoqiang Zhang,“On cost-effective communication network designing”,Europhysics Lettters(EPL),89,38003,2010.2.Guoqiang Zhang and Guoqing Zhang,“Communication network designing:transmission cap
10、acity,cost and scalability”,Science in China series F,accepted.3.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.4.Guoqing Zhang,Di Wang,and Guojie Li,“Enhanc
11、ing the transmission efficiency by edge deletion in scale-free networks”,Physical Review E 76,017101,2007.INSTITUTE OF COMPUTING TECHNOLOGY其它复杂网络方面的文章其它复杂网络方面的文章1.Guoqiang Zhang,“Traversability of the graph space with given degree sequence under edge rewiring”,Electronics Letters,46(5),351-352,2010.
12、2.Guoqiang Zhang,“link power coordination for energy conservation in complex communication networks”,Europhysics Letters,accepted，available online at:http:/arxiv.org/abs/1010.1894.3.Guoqiang Zhang,Brono Quotin,and Shi Zhou,“Phase changes in the evolution of the IPv4 and IPv6 AS-level Internet topolo
13、gies”,Computer Communications,doi:10.1016/com.2010.06.004 ,2010.4.Guoqing Zhang,Guoqiang Zhang,Su-Qi Cheng,and Tao Zhou,“Symbiotic effect:a guideline for network modeling method”,Europhysics Letters,87,68002,2009.5.Guoqing Zhang,Guoqiang Zhang,Qingfeng Yang,Suqi Cheng,and Tao Zhou,“Evolution of the Internet and its cores”,New Journal of Physics,10,123027，2008.6.Shi Zhou,Guoqiang Zhang,and Guoqing Zhang.“Chinese Internet AS-Level topology”,IET Communications,1(2):209-214,2007.INSTITUTE OF COMPUTING TECHNOLOGY
