张国清-删边扩容策略在接入网流量优化中的应用

INSTITUTEOFCOMPUTINGTECHNOLOGY“删边扩容”策略在接入网流量优化中的应用报告人：张国清[e-mail]CHNOLOGY内容提要一、删边扩容方法简介二、删边扩容方法在接入网流量优化中的应用三、在互联网工程中的其它应用INSTITUTEOFCOMPUTINGTECHNOLOGY一、删边扩容方法简介背景知识：网络容量序参数网络中累积包的速率网络容量网络由自由/非拥塞状态到拥塞状态突变时的临界RR无拥塞发生R开始拥塞tWRCRHtlim)(cRcRcRINSTITUTEOFCOMPUTINGTECHNOLOGY背景知识一般方法：增加节点能力、加边、改变路由策略网络拓扑结构影响动态流量（最短路径路由）均匀网络承载更多的网络容量无高介数Hub节点流量负载在网络均匀分担异质性网络容易发生拥塞高介数Hub节点流量负载聚集介数：静态拓扑和动态流量之间的桥梁，在最短路由算法和每个节点具有相同发包条件下，介数恰好量化了一个节点要处理的流量。数学分析：动机：使异质性网络趋于均匀INSTITUTEOFCOMPUTINGTECHNOLOGY删边扩容方法步骤：(1)计算每个节点i的介数gi(2)给每条边赋权Wij=gigj，gi,gj分别是一条边两端节点的介数，并按边权从大到小排序(3)按一定的比例从大到小删除网络的边，但要保持网络连通，如遇到删边后网络不连通，要保留该边，再依次删去后面的边。(4)按广泛使用的流量模型，计算网络容量Rc。研究结果：INSTITUTEOFCOMPUTINGTECHNOLOGY试验结果和讨论BA模型下，C=1不同去边比例下，序参数－R曲线网络容量和平均最短路径随去边比例变化曲线Guo-QingZhang,DiWang,Guo-JieLi.Enhancingthetransmissionefficiencybyedgedeletioninscale-freenetworks,PhysicalReviewE76,017101(2007)INSTITUTEOFCOMPUTINGTECHNOLOGY(0,0.08]内网络结构改变很小，近似于scale-free容量提高显著，更有意义大概[0.22,0.35]，近似于ERER图容量远大于BA0.48突跳点时网络近似于树状结构L迅速增大交叉节点增多，介数分布不均匀INSTITUTEOFCOMPUTINGTECHNOLOGY在城市交通中的例子：例1：交叉口的禁行管理；例2：放射加环状INSTITUTEOFCOMPUTINGTECHNOLOGY二、删边扩容方法在接入网流量优化中的应用现状公有网络公共场所政府企业小区校园家庭网络INSTITUTEOFCOMPUTINGTECHNOLOGY互联网中NAT设备保有量产量：千台产值：亿NT2006年33,486千台2007年约27,200千台2008年约27,200千台2002年—2008年具有地址转换（NAT）功能的设备产量累计1亿台以上，约80%产品销往北美、欧洲、中国大陆、日本INSTITUTEOFCOMPUTINGTECHNOLOGYNAT-BUS现状多级NAT的存在致使路由无法按物理上的最短路径转发，造成了路由瓶颈，无谓地消耗了大量的网络带宽资源，恶化了用户体验意义在IPv4地址逐步耗尽，而IPv6短时期无法广泛部署的情况下，基于多级NAT的网络结构必然长期存在。优化多级NAT环境下的节点之间的路由对网络的演进至关重要。公有网络私有网络第一级NAT设备第二级NAT设备1、消除瓶颈、优化数据传输路径、扩充网络容量2、扩大网络用户接入数量INSTITUTEOFCOMPUTINGTECHNOLOGYNAT组网需要解决的关键问题•改变TCP/IP应用程序间的遂路通知方式。•在私有网络内找到可以协助通讯双方进行路径协商的节点。（最坏情况下用于转发）•私网穿越算法要能适应NAT设备的多样性，及NAT组合产生的复杂性。–漏斗型–IP限制型–IP+端口限制型–对称型•应用方式研究–对SDP协议的扩展–与Socket接口的集成–作为驱动程序、应用插件INSTITUTEOFCOMPUTINGTECHNOLOGYIPVN系统概念模型私有网络IPVNSIP呼叫服务实体(P)主机A(H)主机B(H)公有网络SIP信令NAT通道建立服务实体(C)NATNAT通道建立NATINSTITUTEOFCOMPUTINGTECHNOLOGY公有网络Firewall(NAT)家庭网络NAT私有网络NAT私有网络CCCC微波炉小区停车厂智能家电及物联网络INSTITUTEOFCOMPUTINGTECHNOLOGY与现有NAT穿越方法的对比对比项IPVNICESTUNTURN目标网络设备设备设备通道构成直通、中继直通、中继直通中继是否进行设备类型测试不需要需要需要不需要直通下穿越设备类型3种2种2种不支持直通私有网络穿越支持，多层穿越不支持不支持不支持通道数量多个（=2）一个一个一个通道间管理特征支持不支持不支持不支持算法与应用的耦合程度(SDP协议)低，独立于端口描述，可成为独立驱动高，是端口描述的组成部分高，是端口描述的组成部分高，是端口描述的组成部分INSTITUTEOFCOMPUTINGTECHNOLOGYIPVN核心专利群多层NAT网络中面向应用的名字注册系统及方法申请号200810102343.3多层NAT环境下面向应用的名字注册系统及其服务方法申请号200810102278.4一种通信网络系统及通信方法、通信设备申请号200810115782.8一种系统终端设备建立NAT穿越通道的方法申请号200810104586.0实现端到端通信的可配置NAT设备及其数据转发方法申请号200810117963.4多级NAT网络中的网络地址覆盖判别设备、装置及方法申请号200810056962.3同根多层NAT网络中服务资源地址获取系统及方法（迭代型)申请号200810056964.2同根多层NAT网络中服务资源地址获取系统及方法申请号200810057190.5INSTITUTEOFCOMPUTINGTECHNOLOGY三、在互联网工程中的其它应用:3.1覆盖网中转发节点选取方法ABCEFDAS4AS3AS1AS2CoreStubTransitINSTITUTEOFCOMPUTINGTECHNOLOGY三、在互联网工程中的其它应用:3.2网络节能问题与解决方法依据网络负载自适应地调整活跃链路的数量按哪种策略调整最优化INSTITUTEOFCOMPUTINGTECHNOLOGY表1三种网络不同的链路关闭策略达到的节能效果图1三种网络不同的链路关闭策略对网络吞吐能力的影响“linkpowercoordinationforenergyconservationincomplexcommunicationnetworks”,EPL,inpressINSTITUTEOFCOMPUTINGTECHNOLOGY小结删边扩容是一种在一定条件下可以扩大网络容量的路由策略。在实际工作中更关注避开大权重（是介数而不是度）的边。在研究中有很多变种，工程中的变种更多。期待今后有更多这方面的研究和实际应用。INSTITUTEOFCOMPUTINGTECHNOLOGY相关论文1.Guo-QingZhang,DiWang,andGuo-JieLi,Enhancingthetransmissionefficiencybyedgedeletioninscale-freenetworks,PhysicalReviewE76,017101,2007.2.Guo-QingZhang,ShiZhou,DiWang,GangYan,andGuo-QiangZhang,Enhancingnetworktransmissioncapacitybyefficientlyallocatingnodecapability,PhysicaA(2010)doi:10.1016/j.physa.2010.09.022.3.GuoqiangZhangandGuoqingZhang,“Communicationnetworkdesigning:transmissioncapacity,costandscalability”,ScienceinChinaseriesF,accepted.4.Guo-QiangZhang，linkpowercoordinationforenergyconservationincomplexcommunicationnetworks,EPL,inpress5.张国清，互联网拓扑结构知识发现及其应用，通信学报（预期2010年10月出版）INSTITUTEOFCOMPUTINGTECHNOLOGY谢谢！