通信网络设计的性价比-科学网—构建全球华人科学社区

INSTITUTEOFCOMPUTINGTECHNOLOGY数据通信网络设计的性价比张国强[e-mail]2010-10-16INSTITUTEOFCOMPUTINGTECHNOLOGY现状经验性一般利用率超过35%考虑升级带宽，教育网70%升级带宽，科技网60%升级带宽网络拥塞频繁出现平均链路利用率低，但链路利用率分布严重不均衡INSTITUTEOFCOMPUTINGTECHNOLOGYISP的链路利用率统计INSTITUTEOFCOMPUTINGTECHNOLOGY问题从传输的角度，现有的网络设计是否合理？传输容量设计代价可扩展性目标以较低的成本实现高传输容量和高可扩展的网络INSTITUTEOFCOMPUTINGTECHNOLOGY流量模型(1)每个节点都可以产生、转发、接收数据包每个时间步，R个数据包注入网络数据包具有随机的源和目标地址每个路由器端口vi都被赋值带宽C(vi),表示在一个时间步最多能传输的数据包个数,也记为C(e)拥塞发生在端口级当新到达和产生的数据包个数超过C(vi)时，将被存储在端口的出口缓存队列中，以FIFO的方式在后面的时间步得到服务每个数据包都按照特定的路由算法路由如果有多条路径，则随机选一条INSTITUTEOFCOMPUTINGTECHNOLOGY流量模型(2)当网络报文产生率R较小时，每个报文都能得到及时处理。此时，网络报文产生率与递交率相等，网络处于自由态。当R增加到一定程度时，网络报文产生率R将超过网络的递交能力，网络进入拥塞态。从自由态到拥塞态存在一个相变点Rc。INSTITUTEOFCOMPUTINGTECHNOLOGY网络设计目标(1)网络传输能力用Rc衡量INSTITUTEOFCOMPUTINGTECHNOLOGY网络设计目标(2)网络设计代价经济成本技术瓶颈能否用现有技术水平实现设计代价度量方法：在固定的前提下，用来表征一个网络的设计代价INSTITUTEOFCOMPUTINGTECHNOLOGY网络设计目标(3)可扩展性现实的网络特征大规模演化可扩展的网络设计对网络投资者和运营者具有长期的好处度量方法用Rc和Cmax随网络规模的增长趋势来衡量INSTITUTEOFCOMPUTINGTECHNOLOGY网络设计目标(4)端到端性能通过平均传输路径长度衡量INSTITUTEOFCOMPUTINGTECHNOLOGY网络设计选择(1)拓扑结构随机网络(ER)小世界网络(WS)网格(Lattice)环(Ring)BAPAHOTINSTITUTEOFCOMPUTINGTECHNOLOGY网络设计选择(2)路由算法(topology-based)最短路径（跳数）路由RIP,BGP有效路由(Yan’06)最小化路径的节点度之和INSTITUTEOFCOMPUTINGTECHNOLOGY网络设计选择(3)带宽分配策略均匀与度成正比与介数成正比与有效介数成正比INSTITUTEOFCOMPUTINGTECHNOLOGY问题1：Rc和Cmax的可行范围Cmax的取值范围[1,M]Rc的最小值为0,最大值由如下定理给出：定理：给定网络G，对任何一个网络设计方案，其Rc的上界是2M/L（L是平均最短路径长度）；这一上界当且仅当采用（BC,SPR)时达到。INSTITUTEOFCOMPUTINGTECHNOLOGY（1）证明2M/L为上界网络每个时间步最多移动2M个数据包到下一跳，而每个数据包平均需要移动步，意味着网络每个时间步平均最多消费个数据包。依据Little律，有（2）证明2M/L为上确界，即(BC,SPR)是Rc=2M/L的充分条件当采用（BC,SPR）时，有INSTITUTEOFCOMPUTINGTECHNOLOGY（3）（BC,SPR)是Rc=2M/L的必要条件Rc=2M/L当且仅当a)，表明路由必须是最短路径路由b)网络平均每一步能平均移动2M个数据包到下一跳在SPR中，在自由态平均每个时间步到达端口vi的数据包个数平均为当R=2M/L时，网络中平均的数据包个数为为了每个时间步移动2M个数据包，每个端口需要移动个数据包，正对应了BC的带宽分配策略INSTITUTEOFCOMPUTINGTECHNOLOGY(a)BA(b)Regularnetworks（1）不同的网络能呈现不同的网络设计目标可行解空间（2）除了完全规则的网络，最大Rc和最小Cmax无法同时达到，存在折中问题INSTITUTEOFCOMPUTINGTECHNOLOGY传输容量和设计代价的折中问题RcCmaxINSTITUTEOFCOMPUTINGTECHNOLOGY可扩展性RcCmaxINSTITUTEOFCOMPUTINGTECHNOLOGY平均路径长度INSTITUTEOFCOMPUTINGTECHNOLOGY真实路由器拓扑和路由协议真实ISP路由器级拓扑在不同带宽赋值策略和路由协议组合下的结果：1实际ISP的路由器级拓扑与HOT模型类似2OSPF的weight赋值策略更倾向于聚合流量INSTITUTEOFCOMPUTINGTECHNOLOGY总结给出了更符合实际的网络流模型提出了网络设计是一个多目标优化的过程理论分析了网络设计方案的可行解空间探讨了网络设计的性价比和可扩展性INSTITUTEOFCOMPUTINGTECHNOLOGY与本报告相关文章1.GuoqiangZhang,“Oncost-effectivecommunicationnetworkdesigning”,EurophysicsLettters(EPL),89,38003,2010.2.GuoqiangZhangandGuoqingZhang,“Communicationnetworkdesigning:transmissioncapacity,costandscalability”,ScienceinChinaseriesF,accepted.3.GuoqingZhang,ShiZhou,DiWang,GangYan,andGuoqiangZhang,“Enhancingnetworktransmissioncapacitybyefficientlyallocatingnodecapability”,PhysicaA(2010)doi:10.1016/j.physa.2010.09.022.4.GuoqingZhang,DiWang,andGuojieLi,“Enhancingthetransmissionefficiencybyedgedeletioninscale-freenetworks”,PhysicalReviewE76,017101,2007.INSTITUTEOFCOMPUTINGTECHNOLOGY其它复杂网络方面的文章1.GuoqiangZhang,“Traversabilityofthegraphspacewithgivendegreesequenceunderedgerewiring”,ElectronicsLetters,46(5),351-352,2010.2.GuoqiangZhang,“linkpowercoordinationforenergyconservationincomplexcommunicationnetworks”,EurophysicsLetters,accepted，availableonlineat:“PhasechangesintheevolutionoftheIPv4andIPv6AS-levelInternettopologies”,ComputerCommunications,doi:10.1016/j.comcom.2010.06.004,2010.4.GuoqingZhang,GuoqiangZhang,Su-QiCheng,andTaoZhou,“Symbioticeffect:aguidelinefornetworkmodelingmethod”,EurophysicsLetters,87,68002,2009.5.GuoqingZhang,GuoqiangZhang,QingfengYang,SuqiCheng,andTaoZhou,“EvolutionoftheInternetanditscores”,NewJournalofPhysics,10,123027，2008.6.ShiZhou,GuoqiangZhang,andGuoqingZhang.“ChineseInternetAS-Leveltopology”,IETCommunications,1(2):209-214,2007.INSTITUTEOFCOMPUTINGTECHNOLOGY