下一代全光网络中的

下一代全光网络中的寻路和波长选择(RWA)问题孙卫强2002年4月6日17January2020InformationNetworksLab,USTC希望通过这个报告…了解全光网络的几个基本概念了解RWA问题的背景了解RWA问题的简单原理算法不是重点！欢迎随时纠正和讨论17January2020InformationNetworksLab,USTC提纲光网络基本概念RWA问题的简介静态RWA问题动态RWA问题几种波长选择算法关于RWA值得讨论的两个问题我们的研究内容和计划17January2020InformationNetworksLab,USTC光网络基本概念光传送网基本概念光交叉连接设备（OXC）光网中的寻路OSPF-TE,ISIS-TE或者距离向量协议等源路由(SourceRouting)光网中的信令根据寻路结果来建立光通路（LightPath)CR-LDP,RSVP-TE等17January2020InformationNetworksLab,USTC光传送网OXCOXCOXCOXCOXCOXCOXC连接请求ClientNetworkAClientNetworkB光网络基本概念入口节点出口节点光通路光交叉连接(OXC)LightPath=route+wavelength17January2020InformationNetworksLab,USTC光网络基本概念光传送网基本概念光交叉连接设备（OXC）光网中的寻路OSPF-TE,ISIS-TE或者距离向量协议等源路由(SourceRouting)光网中的信令根据寻路结果来建立光通路（LightPath)CR-LDP,RSVP-TE等17January2020InformationNetworksLab,USTC光传送网中的节点结构NxNPhotonicSwitchλ1NxNPhotonicSwitchλ2NxNPhotonicSwitchλ3NxNPhotonicSwitchλw...光纤λ1λ2λ3λwλ1λ2λ3λwλ1λ2λ3λwλ1λ2λ3λw光纤结构之一：全波长转换结构之二：无波长转换光网络基本概念ＮＸＮ的光交叉连接设备，每个端口一根光纤，每根光纤复用ｗ个波长17January2020InformationNetworksLab,USTC光网络基本概念光传送网基本概念光交叉连接设备（OXC）光网中的寻路OSPF-TE,ISIS-TE或者距离向量协议等源选路(SourceRouting)光网中的信令根据寻路结果来建立光通路（LightPath)CR-LDP,RSVP-TE等17January2020InformationNetworksLab,USTCWearehere…光网络基本概念RWA问题的简介RWA问题的由来RWA问题的地位RWA问题的分类静态RWA问题动态RWA问题几种波长选择算法RWA值得讨论的两个问题我们的研究内容和计划17January2020InformationNetworksLab,USTCRWA问题的由来传统网络中网络寻路和资源分配问题IP网络提供尽力服务，只有寻路，没有资源分配ATM、PacketoverSDH等网络需要寻路，同时也有资源的分配问题，但是资源的分配不具有全局重要性DWDM网络中的波长一致性条件要求从入口到出口使用同一个波长波长分配具有全局重要性合适地选择波长，使得：所需波长数目最小、网络吞吐率最大或者连接请求阻塞概率最小17January2020InformationNetworksLab,USTC连接请求阻塞示例OXC-aOXC-cOXC-dOXC-bOXC-eOXC-gOXC-fλ1λ1连接请求－1(a--g)连接请求－2(c--g)×请求２被组塞17January2020InformationNetworksLab,USTCRWA问题的地位1.来自客户网络的连接请求到达边缘节点2.边缘节点进行RWA计算，选择路径和波长，也就是选择光通路。3.由光传送网的信令负责光通路的建立17January2020InformationNetworksLab,USTC光通路的建立过程OXCOXCOXCOXCOXCOXCOXCClientNetworkAClientNetworkB（2）边缘节点或者网管中心进行RWA计算（4）连接结束通过信令拆除光通路（3）通过信令建立光通路（1）来自客户网络的连接请求到达边缘节点17January2020InformationNetworksLab,USTCRWA问题的分类静态问题—SLE(StaticLightpathEstablishment)所有业务量事先确定，连接建立后不拆除RWA的目标：所使用的波长/光纤数目最小——网络建设成本最低增量式/动态问题—DLE(Dynamic..)业务逐渐到达，或者建立恢复链路RWA的目标：连接请求被阻塞的概率最小——网络运行性能最好17January2020InformationNetworksLab,USTCWearehere…光网络基本概念RWA问题简介静态RWA问题静态RWA问题的数学描述静态RWA问题的解决动态RWA问题几种波长选择算法RWA值得讨论的两个问题我们的研究内容和计划17January2020InformationNetworksLab,USTC静态RWA问题数学描述Minimize：FmaxSuchthat11,0otherwisejdifjsif0,,,maxdssdwijsdwijsdwsdwsdwsdwksdwjkisdwijwdssdwijFFFFijFF静态RWA问题17January2020InformationNetworksLab,USTC静态RWA问题的解决属于NPC类问题，求解困难通常将寻路和波长选择分开寻路问题的解决固定寻路固定可选寻路波长选择问题的解决近似的，启发式方法静态RWA问题17January2020InformationNetworksLab,USTCWearehere…光网络基本概念RWA问题简介静态RWA问题动态RWA问题几种波长选择算法RWA值得讨论的两个问题我们的研究内容和计划17January2020InformationNetworksLab,USTCDLE问题比较复杂，目前尚没有比较完整的算法从理论上来说，寻路和波长选择需要同时被考虑，才能达到全局资源的最优化使用现有的算法也将寻路和波长选择分开动态寻路方式代价最小路径最不拥塞路径采用适合于动态寻路算法的波长选择算法17January2020InformationNetworksLab,USTC几种波长选择算法First-Fit(FF)算法LeastUsed(LU)和MostUsed(MU)算法Min-Product(MP)算法)(plljD选择一个波长，使得最小其中Dlj是链路l上面波长j已经被占用的光纤的数目，)(p是通道p上所有的链路的集合Least-Loaded(LL)算法)(minmax)(ljlplSjDMp在路径p上最拥挤的链路上选择残留能力最大的波长。17January2020InformationNetworksLab,USTC几种波长选择算法MAX-SUM(M∑)算法最大的波长该算法选择满足通路，是当前状态所有可能的分配以后的网络状态，是将波长假设：通路的通路容量定义为，：波长的通路容量定义为，链路容量定义为：在状态PpWjplpljllpjRPjjjlrpRjlrjprDMjlr)),('()('),,,(),(),,(),,(,)(),,(1)()(minmin17January2020InformationNetworksLab,USTC几种波长选择算法RCL(RelativeCapacityLoss)andDistributedRCL算法最小使得：选择波长算法对此进行了改进，最小，也就是满足最大，满足),,(/)),,'(),,((RCL))),('()),((()),('(jprjprjprjpjRpjRpjRPpPpPp17January2020InformationNetworksLab,USTCWearehere…光网络基本概念RWA问题简介静态RWA问题动态RWA问题几种波长选择算法RWA值得讨论的两个问题集中控制还是分布式控制波长转换到底需不需要我们的研究内容和计划17January2020InformationNetworksLab,USTC集中还是分布？集中式控制网管中心集中控制资源分配（决策者）光节点只负责利用信令建立/拆除光通路（实施者）分布式控制光节点自主寻路，需要运行寻路协议值得讨论的两个问题17January2020InformationNetworksLab,USTC集中还是分布？集中式控制减少光节点复杂度组塞率为0可扩展性差，容错性较差分布式控制容错性能较好需要复杂的寻路协议值得讨论的两个问题17January2020InformationNetworksLab,USTC波长转换需不需要？优点：可以使寻路和波长分配算法得到简化提高网络利用效率，但是效果不明显？缺点：导致数据传输中的时延增大连接建立的开销增加网络建设和维护的成本升高值得讨论的两个问题17January2020InformationNetworksLab,USTC波长转换需不需要？节点数目＝100节点数目＝500值得讨论的两个问题17January2020InformationNetworksLab,USTCAbouttofinish…光网络基本概念RWA问题简介静态RWA问题RWA值得讨论的两个问题动态RWA问题几种波长选择算法我们的研究内容和计划17January2020InformationNetworksLab,USTC我们的研究内容和计划分析波长选择协议SWAP的性能连接建立时间和hop数目的关系在某种连接请求到达分布下，连接请求的阻塞概率修正现有阻塞概率计算方法计算时考虑信令的影响：需要锁定部分资源造成阻塞概率上升在ns上实现一个寻路和波长选择算法的研究平台和OBS小组讨论建立统一仿真平台的必要性和可行性在该平台上对各种波长选择算法进行仿真，改进和创新？研究波长转换器的数量和位置对光网性能的影响17January2020InformationNetworksLab,USTC我们的研究内容和计划(2)继续深入研究RWA问题计算集中式控制的复杂度研究分布式情况下，路由协议必须做哪些改动，新的寻路协议的开销有多大动态RWA问题的分析组播RWA问题？OBS中的寻路和波长选择问题RWA问题和光网络中的保护与恢复17January2020InformationNetworksLab,USTCQ&Atime~~PPT文档下载：~sunwq/optical/RWA.ppt