下一代全光网络中的寻路和波长选择 (RWA)问题.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,Information Networks Lab,USTC,*,下一代全光网络中的寻路和波长选择(,RWA),问题,孙卫强,2002年4月6日,希望通过这个报告,了解全光网络的几个基本概念,了解,RWA,问题的背景,了解,RWA,问题的简单原理,算法不是重点！,欢迎随时纠正和讨论,Information Networks Lab,USTC,提纲,光网络基本概念,RWA,问题的简介,静态,RWA,问题,动态,RWA,问题,几种波长选择算法,关于,RWA,值得讨论的两个问题,我们的研究内容和计划,Information Networks Lab,USTC,光网络基本概念,光传送网基本概念,光交叉连接设备（,OXC）,光网中的寻路,OSPF-TE,ISIS-TE,或者距离向量协议等,源路由(,Source Routing),光网中的信令,根据寻路结果来建立光通路（,Light Path),CR-LDP,RSVP-TE,等,Information Networks Lab,USTC,光传送网,光网络基本概念,入口节点,出口节点,光通路,光交叉连接,(,OXC),Light Path=route+wavelength,Information Networks Lab,USTC,光网络基本概念,光传送网基本概念光交叉连接设备（,OXC）,光网中的寻路,OSPF-TE,ISIS-TE,或者距离向量协议等,源路由(,Source Routing),光网中的信令,根据寻路结果来建立光通路（,Light Path),CR-LDP,RSVP-TE,等,Information Networks Lab,USTC,光传送网中的节点结构,结构之一：全波长转换,结构之二：无波长转换,光网络基本概念,的光交叉连接设备，每个端口一根光纤，每根光纤复用个波长,Information Networks Lab,USTC,光网络基本概念,光传送网基本概念,光交叉连接设备（,OXC）,光网中的寻路,OSPF-TE,ISIS-TE,或者距离向量协议等,源选路(,Source Routing),光网中的信令,根据寻路结果来建立光通路（,Light Path),CR-LDP,RSVP-TE,等,Information Networks Lab,USTC,We are here,光网络基本概念,RWA,问题的简介,RWA,问题的由来,RWA,问题的地位,RWA,问题的分类,静态,RWA,问题,动态,RWA,问题,几种波长选择算法,RWA,值得讨论的两个问题,我们的研究内容和计划,Information Networks Lab,USTC,RWA,问题的由来,传统网络中网络寻路和资源分配问题,IP,网络提供尽力服务，只有寻路没有资源分配,ATM、Packet over SDH,等,网络需要寻路，同时也有资源的分配问题，但是资源的分配不具有全局重要性,DWDM,网络,中的波长一致性条件,要求从入口到出口使用同一个波长,波长分配具有全局重要性,合适地选择波长，使得：所需波长数目最小、网络吞吐率最大,或者,连接请求阻塞概率最小,Information Networks Lab,USTC,连接请求阻塞示例,请求被组塞,Information Networks Lab,USTC,RWA,问题的地位,来自客户网络的连接请求到达边缘节点,边缘节点进行,RWA,计算，选择路径和波长，,也就是选择光通路。,由光传送网的信令负责光通路的建立,Information Networks Lab,USTC,光通路的建立过程,（2）边缘节点或者网管中心进行,RWA,计算,（4）连接结束通过信令拆除光通路,（3）通过信令建立光通路,（,1）来自客户网络的连接请求到达边缘节点,Information Networks Lab,USTC,RWA,问题的分类,静态问题,SLE(Static Lightpath Establishment,),所有业务量事先确定，连接建立后不拆除,RWA,的目标,：所使用的波长/光纤数目最小网络建设成本最低,增量式,/,动态问题,DLE(Dynamic.),业务逐渐到达，或者建立恢复链路,RWA,的目标连接请求被阻塞的概率最小网络运行性能最好,Information Networks Lab,USTC,We are here,光网络基本概念,RWA,问题简介,静态,RWA,问题,静态,RWA,问题的数学描述,静态,RWA,问题的解决,动态,RWA,问题,几种波长选择算法,RWA,值得讨论的两个问题,我们的研究内容和计划,Information Networks Lab,USTC,静态,RWA,问题数学描述,Minimize：,F,max,Such that,静态,RWA,问题,Information Networks Lab,USTC,静态,RWA,问题的解决,属于,NPC,类问题，求解困难,通常将寻路和波长选择分开,寻路问题的解决,固定寻路,固定可选寻路,波长选择问题的解决,近似的，启发式方法,静态,RWA,问题,Information Networks Lab,USTC,We are here,光网络基本概念,RWA,问题简介,静态,RWA,问题,动态,RWA,问题,几种波长选择算法,RWA,值得讨论的两个问题,我们的研究内容和计划,Information Networks Lab,USTC,DLE,问题,比较复杂，目前尚没有比较完整的算法,从理论上来说，寻路和波长选择需要同时被考虑，才能达到全局资源的最优化使用,现有的算法也将寻路和波长选择分开,动态寻路方式,代价最小路径,最不拥塞路径,采用适合于动态寻路算法的波长选择算法,Information Networks Lab,USTC,几种波长选择算法,First-Fit(FF),算法,Least Used(LU),和,Most Used(MU),算法,Min-Product(MP),算法,选择一个波长，使得,最小,其中,D,lj,是链路,l,上面波长,j,已经被占用的光纤的数目，,是通道,p,上所有的链路的集合,Least-Loaded(LL),算法,在路径,p,上最拥挤的链路上,选择残留能力最大的波长。,Information Networks Lab,USTC,几种波长选择算法,MAX-SUM(M,),算法,Information Networks Lab,USTC,几种波长选择算法,RCL(Relative Capacity Loss)and,Distributed RCL,算法,Information Networks Lab,USTC,We are here,光网络基本概念,RWA,问题简介,静态,RWA,问题,动态,RWA,问题,几种波长选择算法,RWA,值得讨论的两个问题,集中控制还是分布式控制,波长转换到底需不需要,我们的研究内容和计划,Information Networks Lab,USTC,集中还是分布？,集中式控制,网管中心集中控制资源分配（决策者）,光节点只负责利用信令建立/拆除光通路（实施者）,分布式控制,光节点自主寻路，需要运行寻路协议,值得讨论的两个问题,Information Networks Lab,USTC,集中还是分布？,集中式控制,减少光节点复杂度,组塞率为 0,可扩展性差，容错性较差,分布式控制,容错性能较好,需要复杂的寻路协议,值得讨论的两个问题,Information Networks Lab,USTC,波长转换需不需要？,优点：,可以使寻路和波长分配算法得到简化,提高网络利用效率，但是效果不明显？,缺点：,导致数据传输中的时延增大,连接建立的开销增加,网络建设和维护的成本升高,值得讨论的两个问题,Information Networks Lab,USTC,波长转换需不需要？,节点数目100,节点数目500,值得讨论的两个问题,Information Networks Lab,USTC,About to finish,光网络基本概念,RWA,问题简介,静态,RWA,问题,RWA,值得讨论的两个问题,动态,RWA,问题,几种波长选择算法,我们的研究内容和计划,Information Networks Lab,USTC,我们的研究内容和计划,分析波长选择协议,SWAP,的性能,连接建立时间和,hop,数目的关系,在某种连接请求到达分布下，连接请求的阻塞概率,修正现有阻塞概率计算方法,计算时考虑信令的影响：需要锁定部分资源造成阻塞概率上升,在,ns,上实现一个寻路和波长选择算法的研究平台,和,OBS,小组讨论建立统一仿真平台的必要性和可行性,在该平台上对各种波长选择算法进行仿真，改进和创新？,研究波长转换器的数量和位置对光网性能的影响,Information Networks Lab,USTC,我们的研究内容和计划(2),继续深入研究,RWA,问题,计算集中式控制的复杂度,研究分布式情况下，路由协议必须做哪些改动，新的寻路协议的开销有多大,动态,RWA,问题的分析,组播,RWA,问题？,OBS,中的寻路和波长选择问题,RWA,问题和光网络中的保护与恢复,Information Networks Lab,USTC,Q&A time,谢谢大家，,欢迎提问！,PPT,文档下载：,192.168.3.1/,sunwq,/optical/RWA.,ppt,Information Networks Lab,USTC,