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

INSTITUTEOFCOMPUTINGTECHNOLOGY数据通信网络 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 的性价比张国强guoqiang@ict.ac.cn2010-10-16INSTITUTEOFCOMPUTINGTECHNOLOGY现状 经验性 一般利用率超过35%考虑升级带宽，教育网70%升级带宽，科技网60%升级带宽 网络拥塞频繁出现 平均链路利用率低，但链路利用率分布严重不均衡INSTITUTEOFCOMPUTINGTECHNOLOGYISP的链路利用率统计INSTITUTEOFCOMPUTINGTECHNOLOGY问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 从传输的角度，现有的网络设计是否合理？ 传输容量 设计代价 可扩展性 目标 以较低的成本实现高传输容量和高可扩展的网络INSTITUTEOFCOMPUTINGTECHNOLOGY流量模型(1) 每个节点都可以产生、转发、接收数据包 每个时间步，R个数据包注入网络 数据包具有随机的源和目标地址 每个路由器端口vi都被赋值带宽C(vi), 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示在一个时间步最多能传输的数据包个数,也记为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，对任何一个网络设计 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 ，其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与本报告相关文章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.INSTITUTEOFCOMPUTINGTECHNOLOGY其它复杂网络方面的文章GuoqiangZhang,“Traversabilityofthegraphspacewithgivendegreesequenceunderedgerewiring”,ElectronicsLetters,46(5),351-352,2010.GuoqiangZhang,“linkpowercoordinationforenergyconservationincomplexcommunicationnetworks”,EurophysicsLetters,accepted，availableonlineat:http://arxiv.org/abs/1010.1894.GuoqiangZhang,BronoQuotin,andShiZhou,“PhasechangesintheevolutionoftheIPv4andIPv6AS-levelInternettopologies”,ComputerCommunications,doi:10.1016/j.comcom.2010.06.004 ,2010.GuoqingZhang,GuoqiangZhang,Su-QiCheng,andTaoZhou,“Symbioticeffect:aguidelinefornetworkmodelingmethod”,EurophysicsLetters,87,68002,2009.GuoqingZhang,GuoqiangZhang,QingfengYang,SuqiCheng,andTaoZhou,“EvolutionoftheInternetanditscores”,NewJournalofPhysics,10,123027，2008.ShiZhou,GuoqiangZhang,andGuoqingZhang.“ChineseInternetAS-Leveltopology”,IETCommunications,1(2):209-214,2007.INSTITUTEOFCOMPUTINGTECHNOLOGY