光网络中资源分配算法的研究

论文摘要

全光网络可以在光上直接进行交换和路由,突破了传统光网络需要进行光电转换的瓶颈。同时光网络中的资源分配问题也由传统的光硬件资源分配问题扩展到路由和波长资源的分配问题。静态路由和波长分配问题是在全光网络中,针对静态业务请求提出的路由和波长资源分配的问题。在光网络中进行路由时,单个链路或者节点损坏都会引起整条光通路失效。保护机制可以使得光网络在发生故障时及时切换到备用系统,确保网络信息顺利的传输。求解静态路由和波长分配问题时,本文选取基于通路的保护机制。此外为了节省网络资源,多个低速业务可以利用业务疏导机制汇聚到一个高速波长上传输。由于低速业务的绑定方式将影响业务请求的路由和波长分配,因此本文研究了路由和波长分配问题中的业务疏导问题。解决静态路由和波长问题的方法有建立ILP模型求解和启发式算法。启发式算法可以得到资源分配问题的近似解,求解时间较短。但是启发式算法得到不是最优解,而且当网络规模较大时算法的性能无法判定。本文的第二章建立了静态路由和波长分配问题的保护和业务疏导ILP模型,同时针对大规模网络的路由和波长分配问题提出了不同的分解机制。本文利用拉格朗日松弛算法、Primal和Dual分解算法对大规模网络的ILP模型进行了分解求解。利用计算机软件测试表明,求解ILP模型可以得到资源分配的最优解。但是该问题是NP-C问题,在网络规模较大时求解时间较长,甚至无法得到可行解。利用数学分解的方法对ILP模型进行分解后求解,可以降低减问题的规模,模块化解决问题。理论上数学分解方法可以得到和原模型相同的最优解。测试表明经过有限次迭代,分解算法可以得到接近原模型最优解的可行解且求解时间较短。光多播利用分光节点完成光信号的复制和转发,减少了光网络的资源消耗。由于分光节点代价比较昂贵,在光网络中只有一部分节点可以配置成为分光节点。在有限的分光节点条件下,优化分光节点配置,使用最少的网络资源完成业务请求的问题,称为分光节点配置问题。本文的第三章在静态的业务请求下分别提出了解决分光节点配置问题的ILP模型和MF启发式算法。文中搭建计算机仿真平台验证了,ILP模型可以得到最优解,但是求解时间较长,在网络规模较大时无法得到可行解。MF算法不依赖于多播树的建立算法,可以得到接近最优解的近似解,求解时间较短。第四章针对可预测的动态变化的业务请求,提出了分光节点的鲁棒配置算法。文中的测试验证了,利用鲁棒算法配置分光节点,与静态算法相比可以使网络资源的消耗在各种业务请求情况下都相对较优,稳定性好,总的资源消耗少,更符合实际的网络状况。第五章对全文进行了总结和展望。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 光网络概述
• 1.2 全光网络中的路由和保护
• 1.2.1 光网络的RWA 问题
• 1.2.2 光网络的保护问题
• 1.2.3 业务疏导
• 1.3 光网络多播
• 1.3.1 光网络多播
• 1.3.2 分光节点配置
• 1.4 光网络中资源分配算法
• 1.5 本文的主要贡献及内容安排
• 第二章 大规模网络的静态光网络路由和波长分配
• 2.1 研究背景
• 2.2 静态路由和波长分配的ILP 模型
• 2.2.1 RWA 问题的ILP 模型
• 2.2.2 RWA 的保护模型
• 2.2.3 RWA 的业务疏导模型
• 2.3 大规模网络的RWA 问题
• 2.3.1 分解方法介绍
• 2.3.2 RWA 保护模型分解
• 2.3.3 业务疏导模型分解
• 2.4 计算结果及数据分析
• 2.4.1 RWA 保护模型
• 2.4.2 业务疏导模型
• 2.5 本章小结
• 第三章 静态光网络分光节点配置
• 3.1 研究背景
• 3.2 分光节点配置的ILP 模型
• 3.3 分光节点配置的启发式算法
• 3.3.1 最大度算法
• 3.3.2 MF 算法
• 3.3.3 k 条最短路算法
• 3.3.4 MF 算法复杂度计算
• 3.4 计算结果及数据分析
• 3.5 本章小结
• 第四章 动态光网络分光节点配置
• 4.1 研究背景
• 4.2 分光节点的鲁棒配置ILP 模型
• 4.2.1 鲁棒配置模型
• 4.2.2 有保护的鲁棒模型
• 4.3 鲁棒配置算法的性能分析
• 4.3.1 无保护的鲁棒模型
• 4.3.2 有保护的鲁棒模型
• 4.4 本章小结
• 第五章 全文总结
• 致谢
• 参考文献
• 攻读硕士学位期间的研究成果
• 个人简历