资源描述
Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,INSTITUTE OF COMPUTING,TECHNOLOGY,数据通信网络设计的性价比,张国强,2010-10-16,现状,经验性,一般利用率超过35%考虑升级带宽，教育网70%升级带宽，科技网60%升级带宽,网络拥塞频繁出现,平均链路利用率低，但链路利用率分布严重不均衡,ISP的链路利用率统计,问题,从传输的角度，现有的网络设计是否合理？,传输容量,设计代价,可扩展性,目标,以较低的成本实现高传输容量和高可扩展的网络,流量模型(1),每个节点都可以产生、转发、接收数据包,每个时间步，R个数据包注入网络,数据包具有随机的源和目标地址,每个路由器端口,v,i,都被赋值带宽,C(v,i,),表示在一个时间步最多能传输的数据包个数,也记为,C(e),拥塞发生在端口级,当新到达和产生的数据包个数超过,C(v,i,),时，将被存储在端口的出口缓存队列中，以FIFO的方式在后面的时间步得到服务,每个数据包都按照特定的路由算法路由,如果有多条路径，则随机选一条,流量模型(2),当网络报文产生率,R,较小时，每个报文都能得到及时处理。此时，网络报文产生率与递交率相等，网络处于自由态。,当,R,增加到一定程度时，网络报文产生率,R,将超过网络的递交能力，网络进入拥塞态。,从自由态到拥塞态存在一个相变点,R,c,。,网络设计目标(1),网络传输能力,用,R,c,衡量,网络设计目标(2),网络设计代价,经济成本,技术瓶颈,能否用现有技术水平实现,设计代价度量方法：,在 固定的前提下，用 来表征一个网络的设计代价,网络设计目标(3),可扩展性,现实的网络特征,大规模,演化,可扩展的网络设计对网络投资者和运营者具有长期的好处,度量方法,用,R,c,和C,max,随网络规模的增长趋势来衡量,网络设计目标(4),端到端性能,通过平均传输路径长度衡量,网络设计选择(1),拓扑结构,随机网络(ER),小世界网络(WS),网格(Lattice),环(Ring),BA,PA,HOT,网络设计选择(2),路由算法(topology-based),最短路径（跳数）路由,RIP,BGP,有效路由(Yan06),最小化路径的节点度之和,网络设计选择(3),带宽分配策略,均匀,与度成正比,与介数成正比,与有效介数成正比,问题1：,R,c,和,C,max,的可行范围,C,max,的取值范围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,和最小,C,max,无法同时达到，存在折中问题,传输容量和设计代价的折中问题,Rc,C,max,可扩展性,Rc,C,max,平均路径长度,真实路由器拓扑和路由协议,真实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:,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 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 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.,谢谢！,谢谢观看,/,欢迎下载,BY FAITH I MEAN A VISION OF GOOD ONE CHERISHES AND THE ENTHUSIASM THAT PUSHES ONE TO SEEK ITS FULFILLMENT REGARDLESS OF OBSTACLES.BY FAITH I BY FAITH,内容总结,数据通信网络设计的性价比。2010-10-16。平均链路利用率低，但链路利用率分布严重不均衡。以较低的成本实现高传输容量和高可扩展的网络。每个数据包都按照特定的路由算法路由。当网络报文产生率R较小时，每个报文都能得到及时处理。（2）证明2M/L为上确界，即(BC,SPR)是Rc=2M/L的充分条件。（3）（BC,SPR)是Rc=2M/L的必要条件。b)网络平均每一步能平均移动2M个数据包到下一跳。在SPR中，在自由态平均每个时间步到达端口vi的数据包个数平均为。为了每个时间步移动2M个数据包，每个端口需要移动。（2）除了完全规则的网络，最大Rc和最小Cmax无法同时达到，存在折中问题。谢谢观看/欢迎下载,
展开阅读全文