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

下一代全光网络中的寻路和波长选择 (RWA)问题 孙卫强 2002年4月6日 希望通过这个报告… 了解全光网络的几个基本概念 了解RWA问题的背景 了解RWA问题的简单原理 算法不是重点！ 欢迎随时纠正和讨论 提纲 光网络基本概念 RWA问题的简介 静态RWA问题 动态RWA问题 几种波长选择算法 关于RWA值得讨论的两个问题 我们的研究内容和计划 光网络基本概念 光传送网基本概念 光交叉连接设备（OXC） 光网中的寻路 OSPF-TE,ISIS-TE或者距离向量协议等 源路由(Source Routing) 光网中的信令 根据寻路结果来建立光通路（Light Path) CR-LDP,RSVP-TE等 光传送网 光网络基本概念 光传送网基本概念 光交叉连接设备（OXC） 光网中的寻路 OSPF-TE,ISIS-TE或者距离向量协议等 源路由(Source Routing) 光网中的信令 根据寻路结果来建立光通路（Light Path) CR-LDP,RSVP-TE等 光传送网中的节点结构 光网络基本概念 光传送网基本概念 光交叉连接设备（OXC） 光网中的寻路 OSPF-TE,ISIS-TE或者距离向量协议等 源选路(Source Routing) 光网中的信令 根据寻路结果来建立光通路（Light Path) CR-LDP,RSVP-TE等 We are here … 光网络基本概念 RWA问题的简介 RWA问题的由来 RWA问题的地位 RWA问题的分类 静态RWA问题 动态RWA问题 几种波长选择算法 RWA值得讨论的两个问题 我们的研究内容和计划 RWA问题的由来 传统网络中网络寻路和资源分配问题 IP网络提供尽力服务，只有寻路，没有资源分配 ATM、Packet over SDH等网络需要寻路，同时也有资源的分配问题，但是资源的分配不具有全局重要性 DWDM网络中的波长一致性条件 要求从入口到出口使用同一个波长 波长分配具有全局重要性 合适地选择波长，使得：所需波长数目最小、网络吞吐率最大或者连接请求阻塞概率最小 连接请求阻塞示例 RWA问题的地位 来自客户网络的连接请求到达边缘节点 边缘节点进行RWA计算，选择路径和波长， 也就是选择光通路。 由光传送网的信令负责光通路的建立 光通路的建立过程 RWA问题的分类 静态问题—SLE(Static Lightpath Establishment) 所有业务量事先确定，连接建立后不拆除 RWA的目标：所使用的波长/光纤数目最小——网络建设成本最低 增量式/动态问题—DLE(Dynamic..) 业务逐渐到达，或者建立恢复链路 RWA的目标：连接请求被阻塞的概率最小——网络运行性能最好 We are here … 光网络基本概念 RWA问题简介 静态RWA问题 静态RWA问题的数学描述 静态RWA问题的解决 动态RWA问题 几种波长选择算法 RWA值得讨论的两个问题 我们的研究内容和计划 静态RWA问题数学描述 静态RWA问题的解决 属于NPC类问题，求解困难 通常将寻路和波长选择分开 寻路问题的解决 固定寻路 固定可选寻路 波长选择问题的解决 近似的，启发式方法 We are here … 光网络基本概念 RWA问题简介 静态RWA问题 动态RWA问题 几种波长选择算法 RWA值得讨论的两个问题 我们的研究内容和计划 DLE问题 比较复杂，目前尚没有比较完整的算法 从理论上来说，寻路和波长选择需要同时被考虑，才能达到全局资源的最优化使用 现有的算法也将寻路和波长选择分开 动态寻路方式 代价最小路径 最不拥塞路径 采用适合于动态寻路算法的波长选择算法 几种波长选择算法 First-Fit(FF)算法 Least Used(LU) 和Most Used(MU) 算法 Min-Product(MP)算法 几种波长选择算法 几种波长选择算法 RCL(Relative Capacity Loss) and Distributed RCL算法 We are here … 光网络基本概念 RWA问题简介 静态RWA问题 动态RWA问题 几种波长选择算法 RWA值得讨论的两个问题 集中控制还是分布式控制 波长转换到底需不需要 我们的研究内容和计划 集中还是分布？ 集中式控制 网管中心集中控制资源分配（决策者） 光节点只负责利用信令建立/拆除光通路（实施者） 分布式控制 光节点自主寻路，需要运行寻路协议 集中还是分布？ 集中式控制 减少光节点复杂度 组塞率为 0 可扩展性差，容错性较差 分布式控制 容错性能较好 需要复杂的寻路协议 波长转换需不需要？ 优点： 可以使寻路和波长分配算法得到简化 提高网络利用效率，但是效果不明显？ 缺点： 导致数据传输中的时延增大 连接建立的开销