数据通信网络设计的性价比.ppt

数据通信网络设计的性价比,张国强 guoqiang 2010-10-16,现状,经验性 一般利用率超过35%考虑升级带宽，教育网70%升级带宽，科技网60%升级带宽 网络拥塞频繁出现 平均链路利用率低，但链路利用率分布严重不均衡,ISP的链路利用率统计,问题,从传输的角度，现有的网络设计是否合理？ 传输容量 设计代价 可扩展性 目标 以较低的成本实现高传输容量和高可扩展的网络,流量模型(1),每个节点都可以产生、转发、接收数据包 每个时间步，R个数据包注入网络 数据包具有随机的源和目标地址 每个路由器端口vi都被赋值带宽C(vi) ,表示在一个时间步最多能传输的数据包个数,也记为C(e) 拥塞发生在端口级 当新到达和产生的数据包个数超过C(vi)时，将被存储在端口的出口缓存队列中，以FIFO的方式在后面的时间步得到服务 每个数据包都按照特定的路由算法路由 如果有多条路径，则随机选一条,流量模型(2),当网络报文产生率R较小时，每个报文都能得到及时处理。此时，网络报文产生率与递交率相等，网络处于自由态。 当R增加到一定程度时，网络报文产生率R将超过网络的递交能力，网络进入拥塞态。 从自由态到拥塞态存在一个相变点Rc。,网络设计目标(1),网络传输能力 用Rc衡量,网络设计目标(2),网络设计代价 经济成本 技术瓶颈 能否用现有技术水平实现,设计代价度量方法： 在 固定的前提下，用 来表征一个网络的设计代价,网络设计目标(3),可扩展性 现实的网络特征 大规模 演化 可扩展的网络设计对网络投资者和运营者具有长期的好处 度量方法 用Rc和Cmax随网络规模的增长趋势来衡量,网络设计目标(4),端到端性能 通过平均传输路径长度衡量,网络设计选择(1),拓扑结构 随机网络(ER) 小世界网络(WS) 网格(Lattice) 环(Ring) BA PA HOT,网络设计选择(2),路由算法(topology-based) 最短路径（跳数）路由 RIP, BGP 有效路由(Yan06) 最小化路径的节点度之和,网络设计选择(3),带宽分配策略 均匀 与度成正比 与介数成正比 与有效介数成正比,问题1：Rc和Cmax的可行范围,Cmax的取值范围1, M Rc的最小值为0,最大值由如下定理给出： 定理：给定网络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中，在自由态平均每个时间步到达端口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赋值策略更倾向于聚合流量,总结,给出了更符合实际的网络流模型 提出了网络设计是一个多目标优化的过程 传输容量、设计代价、可扩展性 理论分析了网络设计方案的可行解空间 探讨了网络设计的性价比和可扩展性,与本报告相关文章,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.,其它复杂网络方面的文章,Guoqiang Zhang, “Traversability of the graph space with given degree sequence under edge rewiring”, Electronics Letters, 46(5), 351-352, 2010. Guoqiang Zhang, “link 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