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