数据通信网络设计的性价比课件

数据通信网络设计的性价比张国强guoqiang@2010-10-16数据通信网络设计的性价比张国强1现状经验性一般利用率超过35%考虑升级带宽，教育网70%升级带宽，科技网60%升级带宽网络拥塞频繁出现平均链路利用率低，但链路利用率分布严重不均衡现状经验性2ISP的链路利用率统计ISP的链路利用率统计3问题从传输的角度，现有的网络设计是否合理？传输容量设计代价可扩展性目标以较低的成本实现高传输容量和高可扩展的网络问题从传输的角度，现有的网络设计是否合理？4流量模型(1)每个节点都可以产生、转发、接收数据包每个时间步，R个数据包注入网络数据包具有随机的源和目标地址每个路由器端口vi都被赋值带宽C(vi),表示在一个时间步最多能传输的数据包个数,也记为C(e)拥塞发生在端口级当新到达和产生的数据包个数超过C(vi)时，将被存储在端口的出口缓存队列中，以FIFO的方式在后面的时间步得到服务每个数据包都按照特定的路由算法路由如果有多条路径，则随机选一条流量模型(1)每个节点都可以产生、转发、接收数据包5流量模型(2)当网络报文产生率R较小时，每个报文都能得到及时处理。此时，网络报文产生率与递交率相等，网络处于自由态。当R增加到一定程度时，网络报文产生率R将超过网络的递交能力，网络进入拥塞态。从自由态到拥塞态存在一个相变点Rc。流量模型(2)当网络报文产生率R较小时，每个报文都能得到及时6网络设计目标(1)网络传输能力用Rc衡量网络设计目标(1)网络传输能力7网络设计目标(2)网络设计代价经济成本

技术瓶颈能否用现有技术水平实现设计代价度量方法：在固定的前提下，用来表征一个网络的设计代价网络设计目标(2)网络设计代价设计代价度量方法：8网络设计目标(3)可扩展性现实的网络特征大规模演化可扩展的网络设计对网络投资者和运营者具有长期的好处度量方法用Rc和Cmax随网络规模的增长趋势来衡量网络设计目标(3)可扩展性9网络设计目标(4)端到端性能通过平均传输路径长度衡量网络设计目标(4)端到端性能10网络设计选择(1)拓扑结构随机网络(ER)小世界网络(WS)网格(Lattice)环(Ring)BAPAHOT网络设计选择(1)拓扑结构11网络设计选择(2)路由算法(topology-based)最短路径（跳数）路由RIP,BGP有效路由(Yan’06)最小化路径的节点度之和网络设计选择(2)路由算法(topology-based)12网络设计选择(3)带宽分配策略均匀与度成正比与介数成正比与有效介数成正比网络设计选择(3)带宽分配策略13问题1：Rc和Cmax的可行范围Cmax的取值范围[1,M]Rc的最小值为0,最大值由如下定理给出：定理：给定网络G，对任何一个网络设计方案，其Rc的上界是2M/L（L是平均最短路径长度）；这一上界当且仅当采用（BC,SPR)时达到。问题1：Rc和Cmax的可行范围Cmax的取值范围[1,M14（1）证明2M/L为上界

网络每个时间步最多移动2M个数据包到下一跳，而每个数据包平均需要移动步，意味着网络每个时间步平均最多消费个数据包。依据Little律，有（2）证明2M/L为上确界，即(BC,SPR)是Rc=2M/L的充分条件当采用（BC,SPR）时，有（1）证明2M/L为上界15（3）（BC,SPR)是Rc=2M/L的必要条件Rc=2M/L当且仅当a)，表明路由必须是最短路径路由b)网络平均每一步能平均移动2M个数据包到下一跳在SPR中，在自由态平均每个时间步到达端口vi的数据包个数平均为当R=2M/L时，网络中平均的数据包个数为为了每个时间步移动2M个数据包，每个端口需要移动个数据包，正对应了BC的带宽分配策略（3）（BC,SPR)是Rc=2M/L的必要条件16(a)BA(b)Regularnetworks（1）不同的网络能呈现不同的网络设计目标可行解空间（2）除了完全规则的网络，最大Rc和最小Cmax无法同时达到，存在折中问题(a)BA(b)Regularnetworks（1）不17传输容量和设计代价的折中问题RcCmax传输容量和设计代价的折中问题RcCmax18可扩展性RcCmax可扩展性RcCmax19平均路径长度平均路径长度20真实路由器拓扑和路由协议真实ISP路由器级拓扑在不同带宽赋值策略和路由协议组合下的结果：1实际ISP的路由器级拓扑与HOT模型类似2OSPF的weight赋值策略更倾向于聚合流量真实路由器拓扑和路由协议真实ISP路由器级拓扑在不同带宽赋值21总结给出了更符合实际的网络流模型提出了网络设计是一个多目标优化的过程理论分析了网络设计方案的可行解空间探讨了网络设计的性价比和可扩展性总结给出了更符合实际的网络流模型22与本报告相关文章GuoqiangZhang,“Oncost-effectivecommunicationnetworkdesigning”,EurophysicsLettters(EPL),89,38003,2010.GuoqiangZhangandGuoqingZhang,“Communicationnetworkdesigning:transmissioncapacity,costandscalability”,ScienceinChinaseriesF,accepted.GuoqingZhang,ShiZhou,DiWang,GangYan,andGuoqiangZhang,“Enhancingnetworktransmissioncapacitybyefficientlyallocatingnodecapability”,PhysicaA(2010)doi:10.1016/j.physa.2010.09.022.GuoqingZhang,DiWang,andGuojieLi,“Enhancingthetransmissionefficiencybyedgedeletioninscale-freenetworks”,PhysicalReviewE76,017101,2007.与本报告相关文章GuoqiangZhang,“Onco23其它复杂网络方面的文章GuoqiangZhang,“Traversabilityofthegraphspacewithgivendegreesequenceunderedgerewiring”,ElectronicsLetters,46(5),351-352,2010.GuoqiangZhang,“linkpowercoordinationforenergyconservationincomplexcommunicationnetworks”,EurophysicsLetters,accepted，availableonlineat:/abs/1010.1894.GuoqiangZhang,BronoQuotin,andShiZhou,“PhasechangesintheevolutionoftheIPv4andIPv6AS-levelInternettopologies”,ComputerCommunications,doi:10.1016/com.2010.06.004

,2010.GuoqingZhang,GuoqiangZhang,Su-QiCheng,andTaoZhou,“Symbioticeffect:aguidelinefornetworkmodelingmethod”,EurophysicsLetters,87,68002,2009.GuoqingZhang,GuoqiangZhang,QingfengYang,SuqiCheng,andTaoZhou,“EvolutionoftheInternetanditscores”,NewJournalofPh