传送网路由规划关键算法研究.pdf

分类号密级

UDC 注 1


学位论文

传送网路由规划关键算法研究
(题名和副题名)

曹东
(作者姓名)


指导教师王晟教授
电子科技大学成都


(姓名、职称、单位名称)
申请学位级别硕士专业学位类别工程硕士
工程领域名称电子与通信工程
提交论文日期 2014 年 3 月 12 论文答辩日期 2014 年 5 月 20
学位授予单位和日期电子科技大学 2014 年 6 月 27
答辩委员会主席冷甦鹏
评阅人
注 1:注明《国际十进分类法 UDC》的类号。
RESEARCH ON KEY ALGORITHMS OF
ROUTING PLANNING IN TRANSPORT
NETWORKS





A Master Thesis Submitted to
University of Electronic Science and Technology of China





Major: Electronic munication Engineering
Author: Cao Dong
Advisor: Prof. Wang Sheng
School: School munication & Information
Engineering
独创性声明
本人声明所呈交的学位论文是本人在导师指导下进行的研究工作
及取得的研究成果。据我所知,除了文中特别加以标注和致谢的地方
外,论文中不包含其他人已经发表或撰写过的研究成果,也不包含为
获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与
我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的
说明并表示谢意。

作者签名: 日期: 年月日

论文使用授权
本学位论文作者完全了解电子科技大学有关保留、使用学位论文
的规定,有权保留并向国家有关部门或机构送交论文的复印件和磁盘,
允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全
部或部分内容编入有关数据库进行检索,可以采用影印、缩印或扫描
等复制手段保存、汇编学位论文。
(保密的学位论文在解密后应遵守此规定)

作者签名: 导师签名:
日期: 年月
摘要
摘要
随着网络技术和服务的不断演进和革新,各种应用层出不穷,内容出现爆发
式增长,传送网承载的流量迅猛增长,为了缓解或根治传送网的压力,人们把目
光转向了网络架构升级或重构,N 为代表的内容中心网络和
以 OpenFlow 协议为代表的 SDN 网络的研究热潮。然而,无论是内容中心网络还
是 SDN 网络,传送网的路由规划都是解决问题的关键之一。对业务的路由规划将
直接影响到传送网的业务接纳能力和资源利用能力。本文以 SDN 下的 PCE 系统作
为切入点来研究光网络作为传送网(OTN)的路由规划问题。
光网络的路由规划,需考虑光网络自身的约束,主要有波长连续性和光参损
耗。所谓的波长连续性是指同一光路在其所经过的光纤链路上须使用同一波长;
光参损耗是指任意业务节点对间建立连接须克服光信号在传输过程中出现的非线
性衰减。文献中把光网络下的路由问题称为 RWA,近二十年内提出了大量静态和
动态 RWA 算法,其中不乏优秀的建模,例如波长分层图模型,然而大部分 RWA
算法并未考虑光节点的波长转换能力以及光参损耗约束。本文针对不同的业务下
发场景,提出了解决上述多约束的有路通路由算法和最优中继分配算法。
针对离散到达的新业务,本文提出了自下而上和自上而下两种解决方案。与
传统的 RWA 算法相似,自下而上的解决方案采用在物理拓扑上直接计算前 K 条备
选最短路,然后顺序对备选路进行多约束条件地校验,最后进行波长资源分配;
自上而下的解决方案通过预处理光参损耗约束生成可达表,利用可达表构造虚拓
扑,在虚拓扑上进行选路并最终实现物理路由映射和波长资源分配。波长资源分
配采用 First-fit 策略。本文通过实验对自下而上和自上而下的解决方案进行对比,
选择了性能更优的自上而下的解决方案来设计有路通路由算法。
针对网络故障生成的重路由业务,本文提出了最优中继分配算法,是一种多
目标算法,试图通过合理分配中继资源达到低阻塞率、少使用中继资源的目标。
通过业务类型分析,将原问题分解为单中继、双中继和多中继分配三个子问题。
针对前两个子问题分别提出了构建单中继互斥模型从而转换为二部图的最大匹配
问题和构建分层配对关系模型从而转换为最大配对最大