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

电子科技大学UNIVERSITY OF ELECTRONIC SCIENCE AND TECHNOLOGY OF CHINA专业学位硕士学位论文MASTER THESIS FOR PROFESSIONAL DEGREE论文题目传送网路由规划关键算法研究学科专业电子与通信工程学号201122010324作者姓名曹东指导教师王晟教授分类号密级UDC注1学位论文传送网路由规划关键算法研究(题名和副题名)曹东(作者姓名)指导教师王晟教授电子科技大学成都(姓名、职称、单位名称)申请学位级别硕士专业学位类别工程硕士工程领域名称电子与通信工程提交论文日期2014年3月12论文答辩日期2014年5月20学位授予单位和日期电子科技大学2014年6月27答辩委员会主席冷甦鹏评阅人注1:注明《国际十进分类法UDC》的类号。RESEARCH ON KEY ALGORITHMS OFROUTING PLANNING IN WORKSA Master Thesis Submitted toUniversity of Electronic Science and Technology of ChinaMajor: Electronic munication EngineeringAuthor: Cao DongAdvisor: Prof. Wang ShengSchool:School munication & Information Engineering独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知,除了文中特别加以标注和致谢的地方外,论文中不包含其他人已经发表或撰写过的研究成果,也不包含为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。作者签名:日期:年月日论文使用授权本学位论文作者完全了解电子科技大学有关保留、使用学位论文的规定,有权保留并向国家有关部门或机构送交论文的复印件和磁盘,允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全部或部分内容编入有关数据库进行检索,可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。(保密的学位论文在解密后应遵守此规定)作者签名:导师签名:日期:年月摘要I摘要随着网络技术和服务的不断演进和革新,各种应用层出不穷,内容出现爆发式增长,传送网承载的流量迅猛增长,为了缓解或根治传送网的压力,人们把目光转向了网络架构升级或重构,为代表的内容中心网络和以OpenFlow协议为代表的SDN网络的研究热潮。然而,无论是内容中心网络还是SDN网络,传送网的路由规划都是解决问题的关键之一。对业务的路由规划将直接影响到传送网的业务接纳能力和资源利用能力。本文以SDN下的PCE系统作为切入点来研究光网络作为传送网(OTN)的路由规划问题。光网络的路由规划,需考虑光网络自身的约束,主要有波长连续性和光参损耗。所谓的波长连续性是指同一光路在其所经过的光纤链路上须使用同一波长;光参损耗是指任意业务节点对间建立连接须克服光信号在传输过程中出现的非线性衰减。文献中把光网络下的路由问题称为RWA,近二十年内提出了大量静态和动态RWA算法,其中不乏优秀的建模,例如波长分层图模型,然而大部分RWA算法并未考虑光节点的波长转换能力以及光参损耗约束。本文针对不同的业务下发场景,提出了解决上述多约束的有路通路由算法和最优中继分配算法。针对离散到达的新业务,本文提出了自下而上和自上而下两种解决方案。与传统的RWA算法相似,自下而上的解决方案采用在物理拓扑上直接计算前K条备选最短路,然后顺序对备选路进行多约束条件地校验,最后进行波长资源分配;自上而下的解决方案通过预处理光参损耗约束生成可达表,利用可达表构造虚拓扑,在虚拓扑上进行选路并最终实现物理路由映射和波长资源分配。波长资源分配采用First-fit策略。本文通过实验对自下而上和自上而下的解决方案进行对比,选择了性能更优的自上而下的解决方案来设计有路通路由算法。针对网络故障生成的重路由业务,本文提出了最优中继分配算法,是一种多目标算法,试图通过合理分配中继资源达到低阻塞率、少使用中继资源的目标。通过业务类型分析,将原问题分解为单中继、双中继和多中继分配三个子问题。针对前两个子问题分别提出了构建单中继互斥模型从而转换为二部图的最大匹配问题和构建分层配对关系模型从而转换为最大配对最大匹配问题的最优算法,并分析了算法的时间复杂度;对于多中继分配子问题,给出了近优解算法。通过和有路通路由算法对比,最优中继分配算法能有效减少业务阻塞,提高资源利用率。关键词:光