（通信与信息系统专业论文）ptn网络规划与优化软件系统的设计与实现.pdf

中文摘要 中文摘要 随着网络业务流量从t d m 为主向以分组数据业务为主转变，光传送网也经 历着变革。传统的光传送网对于基于分组的i p 业务和新的业务的传送，存在着很 多缺点。电信业务p 化对光传送网提出了分组传送的要求。分组传送网在这种背 景之下产生。对分组传送网进行规划与优化可以提高网络效率、减少运营商的运 营成本，如何有效规划与优化分组传送网就成了运营商的当务之急。 本文系统的研究了网络规划与优化的各种技术，针对分组传送网，设计了一 套p t n 网络规划与优化软件系统。 本文首先介绍了与p t n 网络规划与优化有关的技术，从软件设计的角度介绍 了规划软件的系统架构。文中对规划软件使用的有关技术进行了较为详细的介绍。 作为一个实用型的软件系统，规划软件将规划流程分为几大模块。文中对各 模块的功能进行描述。与此同时，对场景规划模块的设计与实现进行详细阐述。 场景规划模块主要涉及网络拓扑规划和业务分配和保护。本文针对p t n 网络的特 点，改进了网状网拓扑规划的删枝算法，提高了算法规划与优化的效率。本文提 出一种基于背离路径的k t h 最短路径实用搜索算法，提高了求取网络中前k 条最 短路径的效率，该算法在业务分配与保护算法中具有很好的应用。 文章最后用示例对规划软件的相关功能进行演示，演示结果达到了预期目的。 关键词：分组传送网，网络规划与优化，业务分配，拓扑规划，软件系统 a b s t r a c t a b s t r a c t a st h en e t w o r kt r a f f i cc h a n g i n gf r o mt d mt op a c k e t - b a s e dd a t as e r v i c e s ，o p t i c a l t r a n s m i s s i o nn e t w o r ki sa l s ou n d e r g o i n gc h a n g e t r a d i t i o n a lo p t i c a lt r a n s m i s s i o n n e t w o r k sh a v em a n ys h o r t c o m i n g st ot r a n s p o r tp a c k e t - b a s e di ps e r v i c e s s o ，p a c k e t t r a n s p o r tn e t w o r kh a se m e r g e d n e t w o r kp l a n n i n ga n do p t i m i z a t i o n c s _ r li m p r o v e n e t w o r ke f f i c i e n c y , r e d u c eo p e r a t i n gc o s t s ，o p e r a t o r s h o wt o e f f e c t i v e l yp l a na n d o p t i m i z et h ep a c k e tt r a n s p o r tn e t w o r kh a v eb e c o m ei m p e r a t i v e a f t e rs t u d y i n gv a r i o u st e c h n o l o g i e so ft h en e t w o r kp l a n n i n ga n do p t i m i z a t i o n ，a p t nn e t w o r kp l a n n i n ga n do p t i m i z a t i o ns o 脚a r es y s t e mi sd e s i g n e di nt h i sa r t i c l e f i r s t ，t h i sp a p e ri n t r o d u c e ss o m er e l a t e dt e c h n o l o g i e so fp 1 1 崎n e t w o r kp l a n n i n g a n do p t i m i z a t i o n t h e n , t h i sp a p e ri n t r o d u c e ss y s t e ma r c h i t e c t u r eo ft h i sn e t w o r k p l a n n i n ga n do p t i m i z a t i o ns o f t w a r es y s t e m a l s o ，t h i sp a p e ri n t r o d u c e si m p o r t a n t s 0 f b v v a r et e c h n o l o g i e si nd e t a i l a sap r a c t i c a ls o r w a r es y s t e m ，p l a n n i n ga n do p t i m i z a t i o np r o c e s si sd i v i d e di n t o s e v e r a lm o d u l e si nt h i sp l a n n i n gs o f t w a r e w bd e s c r i b et h ef u n c t i o no fe a c hm o d u l ei n t h i st e x t a tt h es a l t l et i m e ，w eg i v eam o r ed e t a i l e di n t r o d u c t i o no ft h ed e s i g n i n ga n d i m p l e m e n t a t i o nt ot h es c e n ep l a n n i n gm o d u l e n e t w o r kt o p o l o g yp l a n n i n ga n dt r a f f i c d i s t r i b u t i o na n dp r o t e c t i o ni st h em o s ti m p o r t c n ti nt h es c e n ep l a n n i n gm o d u l e b a s e d o nt h ec h a r a c t e r i s t i e so fp t nn e t w o r k ，t h i sp a p e rp r o v i d e sa ni m p r o v e da l g o r i t h mf o r m e s ht o p o l o g yp l a n n i n g , w h i c hi m p r o v e dt h ep e r f o r m a n c eo ft r a d i t i o n a lp r u n i n g a l g o r i t h m t 1 l i sp a p e rp r e s e n t sap r a c t i c a la l g o r i t h mf o rf i n d i n gt h ek t hs h o r t e s tp a t h ， t h ea l g o r i t h mh a sag o o da p p l i c a t i o ni nt h et r a f f i cd i s t r i b u t i o na n d p r o t e c t i o na l g o r i t h m a tl a s t ，w eu s ea ne x a m p l et ov e i l 蛳n gt h er e l e v a n tf u n c t i o no ft h e s o f t - w a r e s y s t e m k e y w o r d s ： p t n ，n e t w o r kp l a n n i n ga n do p t i m i z a t i o n ，t r a f f i ca s s i g n m e n t ，t o p o l o g y p l a n n i n g ，s o f t w a r es y s t e m i i 图目录 图目录 图2 1 共享保护环王作原理8 图2 2 网络规划与优化基本流程图9 图3 1 系统规划流程：1 4 图3 2 系统结构框图1 6 图3 3 各模块之间的关系17 图3 - 4j p f 插件技术图示18 图3 5j n i 技术图示1 9 图3 - 6m v c 组件之间的关系2 0 图3 7 数据库应用层次模型2 0 图4 - 1i m ae 1 到a t ms t m 1 的汇聚2 3 图4 - 2 业务创建模块( t c ) 用例图2 4 图4 - 3 线性保护多样性2 5 图4 - 4l s p 路径规划流程图2 9 图4 5 背离路径图示。3 2 图4 - 6n s f n e t 网络3 5 图4 _ 7 场景规划模块( s p ) 用例图3 6 图4 8 通用业务分配算法流程图3 7 图4 _ 9 网络拓扑优化流程图3 8 图4 - 1 0 网络绿地规划用例图3 9 图4 1 l 网状网拓扑规划流程图4 0 图4 - 1 2 优化后的删枝算法流程图4 2 图4 - 1 3 环网拓扑规划流程图4 4 图4 - 1 4 网络分析模块( n a ) 用例图4 5 图4 - 1 5 网络仿真模块( n s ) 用例图一4 7 图5 1 系统登陆语言选择框。4 9 图5 2 软件系统主界面5 0 图5 3 节点编辑对话框5 1 图5 - 4 系统主界面( 创建了2 0 个节点) 5 2 图5 5 节点属性框5 2 图5 - 6 业务矩阵属性设置框5 3 图5 7 业务编辑对话框5 4 图5 8 业务连接图示5 4 图5 - 9 业务连接属性框5 5 图5 1 0 节点距离及费用设置框5 6 图5 1l 网状网拓扑规划参数设置一5 6 v 图目录 图5 1 2 环网拓扑规划参数设置5 7 图5 。1 3 网状网拓扑规划结果5 8 图5 1 4 环网拓扑规划结果5 8 图5 1 5 绿地规划之后的系统界面显示5 9 图5 1 6l s p 路由业务选择框6 0 图5 1 7l s p 路由结果显示框6 0 图5 1 8l s p 信息6 l 图5 1 9 待规划链路选择框6 2 图5 2 0 待规划链路规划结果6 2 图5 2 1 规划优化结果提示框6 3 图5 2 2 规划优化结果显示框6 3 图5 2 3 链路选择框6 4 图5 2 4 链路分析结果6 4 图5 。2 5 节点选择框6 5 图5 2 6 节点分析结果6 5 图5 2 7 全网分析选择框6 6 图5 2 8 全网分析结果6 6 图5 2 9 方案选择框6 6 图5 3 0 方案对比结果6 7 图5 31 手工仿真界面6 8 图5 3 2 自动仿真界面6 9 v i 表目录 表目录 表3 1p t n 网络层次结构1 3 表3 2 软件系统的模块划分1 5 表4 1l s p 隧道属性2 6 表4 - 2 本文算法与文献 2 1 的算法结果对比3 5 缩略词表 英文缩写 d w d m p t n m v c s d h 田d m n g n m p l s t - m p l s p b t p b b w d m o a m s l a q o s p w l s p m s t p s t m t m o x c o d u 后 d p p s p p a p s 英文全称 缩略词表 d e n s ew a v e l e n g t hd i v i s i o nm u l t i p l e x i n g p a c k e tt r a n s p o r tn e t w o r k m o d e l v i e w c o n t r o l s y n c h r o n o u sd i 百t a lh i e r a r c h y t i m ed i v i s i o nm u l t i p l e x i n g n e x tg e n e r a t i o nn e t w o r k m u l t i - p r o t o c 0 1l a b e ls w i t c h i n g t r a n s p o r tm u l t i p r o t o c o ll a b e ls w i t c h i n g p r o v i d e rb a c k b o n et r a n s p o r t p r o v i d e rb a c k b o n eb r i d g e w a v e l e n g t hd i v i s i o nm u l t i p l e x i n g o p e r a t i o n a d m i n i s t r a t i o n a n d m a i n t e n a n c e s e r v i c e - l e v e la g r e e m e n t q u a l i t yo fs e r v i c e p s e u d o w i r e l a b e l s w i t c h i n gp a t h m u l t i - s e v i c et r a n s p o r tp l a t f o r m s y n c h r o n o u st r a s p o r tm o d u l e t e r m i n a lm u l t i p l e x e r o p t i c a lc r o s s 。c o n n e c t o p t i c a lc h a n n e ld a t au n i tk d e d i c a t e dp a t hp r o t e c t i o n s h a r e dp a t hp r o t e c t i o n a u t o m a t i cp r o t e c t i o ns w i t c h e d 中文释义 密集波分复用 分组传送网 模型视图控制器 同步数字体系 时分复用 下一代网络 多协议标签交换 传送m p l s 运营商骨干网传输 运营商骨干网桥 波分复用 操作、管理、维护 服务等级协议 服务质量 伪线 标签交换路径 多业务传输平台 同步传送模块 终端复用设备 光交叉互联设备 光信道数据单元k 专用通道保护 共享通路保护 自动保护倒换 主要数学符号表 符号类别 变量 常量 集合 v 芒 主要数学符号表 示例 口 c 矿 v a v 口v a 萑v i x 字体、说明或用法 斜体字符 正体大写字符 斜体大写字符 集合矿中的任意元素 变量a 属于集合y 变量a 不属于集合矿 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：4 亟堑量盔 日期：矽p 年广月日 论文使用授权 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：尘避导师签名：一日期：力p 年f 月形日 第一章绪论 1 1课题背景 第一章绪论 在i t u t 提出的下一代网络体系结构中，传送层网络包括现有的光传送网和 i p m p l s 网络。网络融合大势所趋，m p l s 将是实现网络融合的一项关键技术。现 在的网络与以前相比，有了翻天覆地的变化，主要表现为各种基于i p 的应用业务 不断涌现。可以说，网络中的业务流量已经从t d m 为主转变为以分组数据业务为 主【1 1 。新型业务的出现对光传送网提出了很大的挑战。传统的光传送网对基于分组 的口业务和一些新的业务的承载方式，存在着很多不足之处。例如，业务分配处 理复杂、带宽使用效率低、网络和业务可扩展性差等。电信业务口化对光传送网 的挑战促使光传送网向下一代光传送网发展，以更好地适应口业务发展的要求。 分组传送网( p t n ) 就是在这种背景之产生的。p t n 在全网的部署是未来发展的 必然选择。 网络规划与优化作为运营商的一个永恒话题，具有非常重要的意义。运营商 在新建一个网络之前，首先要对这个新建网络进行规划，进行成本分析。关于网 络的成本，运营商要考虑的有投资性成本和操作成本两个方面。投资成本由采购 设备和铺设光纤的费用组成，操作成本由维护和操作网络所需要的各种费用组成。 通过网络规划技术可以控制运营商的投资性成本。对于一个网络来说，如何提高 网络带宽利用率是值得探讨的，网络优化技术是一种好的方法，通过网络优化， 可以有效管理网络流量的路由，保证网络更加稳定可靠，从而帮助运营商降低运 营成本。考虑到投资回报方面的各种情况，运营商迫切希望有一些好的网络规划 与优化软件用于决策。 综上所述，分组传送网是近年来出现的一种新型传送网，基于分组传送网的 传输网络规划与优化是一个值得研究的具有经济意义和实用价值的课题。 1 2课题研究的目的及意义 传输网在整个网络中占据着非常重要的地位，是电信网络体系中位于底层的 基石，进行传输网络的规划与优化将为传输网络的长期发展打下坚实的基础。业 电子科技大学硕士学位论文 务驱动是技术发展的原动力，而目前通信业务发展已经很明确地呈现出承载口化 的趋势。未来的光传输网络将主要负责p 以太网流量的传送，为分组的流量特征 而优化，向着智能的、融合的、宽带的、综合的方向发展【2 1 。分组传送网是针对分 组业务流量的突发性和统计复用传送的要求而专门设计的。p t n 以分组业务为核 心，秉承了光传输的传统优势，是一种适用于p 化分组业务的传送网络。 对于运营商来说，掌握了传输网就掌握了主动权，因为传输网络控制着整个 电信网络。电信运营商为了满足自身竞争的需要以及用户业务的需求关系，需要 与时俱进的对传输网络进行升级。运营商采用人工手动的方式对规模庞大的网络 进行规划和优化是不现实的。考虑到时间成本和人力成本，电信运营商迫切需要 优秀的网络规划工具和软件帮助决策。这种软件应该具有强大的工程建设能力， 具有很强的灵活性，这样才能提高效率，缩短交付等待时间。 分组传送网是一种新型的传送网，运营商迫切需要能够对分组传送网进行规 划与优化的软件指导其新建网络。本项目组结合国内某大型企业的需求，对p t n 网络规划与优化系统进行了全面的研究，开发出了一套面向工程的p t n 网络规划 与优化软件系统。 1 3国内外研究现状和发展态势 传统的光传送网是基于s d h 、d w d m 的，业务的驱动产生了分组传送的需求。 p t n 是一种适合分组传送的传送网，具有很多优点。例如，p t n 可以建立双向的 点到点连接通道，来支持分组业务。这种连接通道具有弹性带宽分配，与分组业 务的特点相吻合。同时，p t n 网络继承了s d h 技术o a m 机制，可以实现业务的 q o s 保证。目前，国内的运营商已经对p t n 进行了试商用【3 】，但是，对于这种新 型的传送网络进行规划与优化的研究还比较少。 从现有的文献资料来看，与通信网络规划有关的专利基本上是针对无线网络 的。对光传送网规划与优化的软件相对无线网络来说少之又少，主要是一些网络 运营商与设备厂商合作开发的专用软件。本项目组与国内某大型企业合作，一期、 二期项目中开发了基于s d h 、d w d m 的网络规划与优化软件系统，三期工程顺应 了光传送网的发展，开发了一套面向工程的p t n 网络规划与优化软件系统。可以 说，解决了光网络规划与优化的燃眉之急。 2 第一章绪论 1 4主要工作及创新点 在p t n 网络规划与优化软件系统的开发过程中，本人所做工作如下： 1 ) 研究了网络拓扑规划问题，针对p t n 网络进行网状网拓扑和环网拓扑的 规划。 2 ) 对p t n 网络业务分配和保护算法进行了深入研究，针对不同的规划场景 实现了不同规划目标的业务分配算法。 3 1 ) 参与了p t n 网络规划与优化软件系统的设计与实现，主要负责了软件的 总体设计，网络拓扑规划与优化，业务分配与保护算法设计与实现等。 本文在以下几方面有一定的创新： 1 ) 针对新型的p t n 网络，开发了一套p t n 网络规划与优化软件系统。该软 件具有实用性，可以规划实际的p t n 网络。这将对以后的p t n 网络大规 模商用提供强有力的支持。 2 ) 改进了用于网状网拓扑规划的删枝算法，提高了算法规划与优化的效率。 3 ) 提出了一种基于背离路径的k t h 最短路径实用搜索算法，提高了求取网络 中前k 条最短路径的效率。该算法在业务分配与保护算法中具有很好的 应用。 1 5论文结构及内容安排 本文主要研究了p t n 网络规划与优化相关技术，设计并实现了一套面向工程 的p t n 网络规划与优化软件系统。 本文分为6 章，以下是具体内容安排。 第二章介绍了与p t n 网络规划与优化的有关的技术。首先介绍了p t n 网络的 层次架构和p t n 网络主要技术及优缺点。其次介绍了网络拓扑规划与优化的相关 算法。最后介绍了业务分配和保护的相关算法。 第三章介绍了p t n 网络规划与优化系统的总体设计，并说明了软件系统架构 和关键技术。 第四章介绍了系统各模块的设计与实现。其中，对网络拓扑规划和业务分配 与保护算法在相应的模块中进行了描述。 3 电子科技大学硕士学位论文 第五章设计了一个与系统相关应用有关的例子，对软件系统的实际使用进行 演示。 第六章总结了现有工作，并进一步探讨了改进方案。 4 第二章p t n 网络规划与优化相关技术 第二章p t n 网络规划与优化相关技术 2 1p t n 网络简介 分组传送网主流技术有两种，一种是基于m p l s 技术的传送m p l s ( t - m p l s ) ， 另一种是基于以太网技术的运营商骨干传输( p b t ) 。t - m p l s 着眼于解决i p m p l s 网络的复杂性，而p b t 着眼于解决以太网的缺点【4 】。t - m p l s 去除了m p l s 的第 三层的一些功能，简化了实现上的复杂度，同时增强了网络的o a m 功能。p b t 则通过以太帧的改造，解决了p b b 存在的流量工程问题。 相比p b t 标准，t - m p l s 技术更有发展前景。t - m p l s 已经完成了大部分标 准化工作，标准化更成熟。而且，t - m p l s 采用基于电信网络的体系架构和设计思 想，可以采用现有的电信网络运营方式，减少运营商的员工培训等运营成本。综 合以上考虑，本项目组所开发的p t n 网络规划与优化软件系统基于t - m p l s 技术。 2 1 1t - m p l s 分组传送网分层结构 t - m p l s 可以分为电路层、通路层、段层三层。各层完成不同的功能，下面对 各层的功能进行简要描述。 1 1 电路层( t m c ) 电路层也称为伪线层( p w 层) ，t m c 是t - m p l sc h a n n e l 的缩写。一个t m c 连接传送一个客户业务实体。电路层的连接和用户业务的关系是一一对应的，其 连接跨越了整个网络。电路层主要关注业务端到端的服务质量。 2 ) 通路层( t m p ) 通路层也称为隧道层( l s p 层) ，t m p 是t - m p l sp a t h 的缩写。根据业务实际 需求，多个t m c 连接可以复用到一个t m p 中。t m c 实体在t m p 域的边界完成 t m c 信号的复用与解复用。 3 ) 段层( 聊s ) 段层主要关注链路资源的互通性。t m s 是t - m p l ss e c t i o n 的缩写。t m s 提供 了两个相邻t - m p l s 节点之间的o a m 监视。 本项目的规划软件主要考虑了用户业务到伪线层的适配以及伪线到隧道层的 复用。t - m p l s 采用i e t f 定义的端到端伪线模拟仿真映射技术( p w e 3 ) 进行用户业 5 电子科技大学硕士学位论文 务信号的仿真【5 】【6 】【7 】【8 】【9 】。用户业务到伪线层的具体适配规则参见4 1 1 小节的描述。 隧道层对应隧道l s p 连接。多个p w 可以复用到一个l s p 隧道中进行传送，具体 规则参见4 2 1 小节描述。 2 1 2t - m p l s 分组传送网拓扑结构 通信网的拓扑结构主要有5 种类型【1 0 】【1 1 】：链形、星形、树形、环形和网状网。 下面简单介绍各种拓扑形式的特点。 链形拓扑也称为线形拓扑，各个网络节点连成一条线。链形拓扑结构简单、 经济，但存在可靠性差等缺点，任意网络节点的中断均会导致网络业务中断。链 形拓扑适用于节点间有大业务量且业务量相对稳定的传输网。 星形拓扑存在一个中心节点，其他网络节点通过链形拓扑的形式连接到中心 节点上。通过中心节点的控制，星形网络可以具有灵活的带宽管理功能，成本较 低。由于中心节点的存在，会出现中心节点的瓶颈问题，如果中心节点出现故障， 会导致网络业务中断。该拓扑适用于用户接入网环境，也可用本地中继网。 树形拓扑可以看作星形拓扑与链形拓扑两者的结合。树形拓扑适合于广播式 业务，与星形拓扑类似，也存在中心节点的安全和潜在瓶颈问题，现实中常用于 广播电视网中。 环形拓扑中各个网络节点互联成为一个环形。环形拓扑是一种实现简单，可 靠性强的拓扑。环形拓扑可以形成自愈环，具有很灵活保护方式。 网状网拓扑组成的通信网，由多个网络节点互相连接而成。可以根据需求网 络的不同连通性要求和生存性要求设计不同的网状网拓扑。网状网拓扑的实现方 式比较灵活，通常应用于可靠性要求高的网络中，比如骨干传输网。 具体到p t n 网络规划与优化软件系统，由于可靠性、生存性的要求，p t n 网 络拓扑类型主要是网状网拓扑和环形拓扑。软件系统中规划出来的拓扑形式是这 两种拓扑的结合。 2 1 3t - m p l s 的生存性技术 t - m p l s 具有完善的生存性技术。t - m p l s 网络生存性主要包括基于传送平面 的保护倒换和基于控制平面的恢复两种形式，是保障t - m p l s 网络性能的一个重 要方面。基于传送平面的保护倒换包括线性保护倒换和共享保护环两种。基于控 制平面的恢复是指在网络发生故障后，由控制平面采取协调措施，重新为业务计 算工作路径，也可以预先计算保护路径，在发生故障后启用保护路径【l2 1 。 6 第二章p t n 网络规划与优化相关技术 本项目组开发的规划软件主要考虑了t - m p l s 网络的线性保护倒换技术和共 享保护环技术。下面对这两种技术进行简要介绍。 1 ) 线性保护倒换 t - m p l s 线性保护倒换由丌u tg 8 1 3 1 1 3 】进行了标准化。标准中规范了端到端 路径保护和子网连接保护两种保护结构，具体可分为1 + 1 和1 ：l 两种类型。线性保 护类似于传统光网络中的1 + 1 保护和1 ：l 保护。 在线性保护倒换方面，规划软件主要考虑了端到端路径保护，包括单向1 + 1 路径保护和双向1 ：1 路径保护。 2 ) 共享保护环( t m s p r i n g ) t - m p l s 共享保护环保护倒换机制由r r u tg 8 1 3 2 t 1 4 】迸行了标准化。标准中规 范了绕回保护( w r a p p i n g ) 和源路由保护( s t e e r i n g ) 两种机制。下面说明两者之 间的区别。 图2 1 描述了网络发生故障时，使用t - m p l s 绕回保护、源路由保护的 t m s p r i n g 工作原理。图2 1 ( a ) 描述了网络正常工作情况下的业务流量q 的工作 路径，工作路径为a b c _ f ，走外环。图2 1 ( b ) 描述了在网络链路召专c 发生故障后，使用绕回保护机制的情况，在邻近故障链路召寸c 上游节点b 进行 了保护倒换操作，新的路径为彳j 占哼ajd 专e 专f - - 9 c 专f 。图2 1 ( c ) 描 述了发生链路故障后，采用源路由保护的情况，从节点a 到f 的业务流量q 改走 内环到达目的节点，新的路径为a d 一五专f 。发生网络故障后，相比绕回保 护，新形成的路径源路由保护要短。 源路由保护方式类似于线性保护，对于环网保护，规划软件中主要考虑了绕 回保护。 7 电子科技大学硕士学位论文 e = = = 承载工作流量的带宽 亡二= 保护流量的可用带宽 图2 1 共享保护环工作原理 2 2p t n 网络规划与优化 网络规划与优化的目标是在已知网络节点和节点间的连接情况( 有时只知道 网络业务汇聚节点) 的情况下，对给定业务进行分析和预测，寻找一种较高性价 比的网络结构来传送网络业务。 本节首先介绍网络规划与优化的基本流程，接着介绍一些和p t n 网络规划有 关的算法。 8 第二章p t n 网络规划与优化相关技术 2 2 1网络规划与优化基本流程 网络规划的过程涉及很多方面，规划结果必须满足预先设定的目标。需要合 理的方法对网络节点进行优化设计，也要用业务分配与保护算法为网络业务进行 路由、保护、分配网络资源等。一般的网络规划与优化的基本流程如图2 - 2 所示。 图2 - 2 网络规划与优化基本流程图 要进行网络规划，首先要确定网络的基本需求。例如，基本拓扑结构类型， 节点的功能结构，网络的生存性需求等。在这个阶段，有时还要增加网络业务需 求的分析。网络的生存性体现为网络的可靠性需求，它是指在人为或者自然的破 坏作用下，通信网在规定条件下和规定时间内的生存能力，主要体现在连通性和 性能指标两个方面【1 5 】。常用的可靠性判断依据有以下几条： 1 ) 网络中给定的节点对之间至少有一条路径 2 ) 网络中的一个指定节点可以与一组节点相互通信 3 ) 网络中可以相互连通的节点数目大于某一闽值 4 ) 网络中任意两个节点间的传输延时小于某一阈值 5 1 网络吞吐量超过某一阈值 在确定了网络的基本参数之后，接着进行网络的拓扑规划。拓扑规划根据用 9 电子科技大学硕士学位论文 户给定的生存性要求，结合节点的功能结构，业务流量需求等，可以规划成不同 的拓扑形式。通信网络主要的拓扑形式在2 1 2 节进行了简要介绍。 在确定了拓扑结构之后，要对网络进行业务规划。业务规划根据不同的规划 目标和约束条件有不同的规划方式。规划目标通常是最小化整个网络的成本，约 束条件可以是用户指定的一些约束条件，例如负载均衡，业务必须经过某些节点 和链路，不能经过某些节点和链路等。在业务规划过程中，根据网络拓扑结构的 已知条件分为不同的情况。常见的是已知节点位置和节点间的链路带宽要求进行 业务分配。还有一些时候某些链路的带宽待规划，在业务分配结束后，还要对这 些链路的带宽进行规划。 网络设计是一个很复杂的过程，上述的各个步骤通常需要反复进行，在得到 不同方案之后，进行评估，最后采用较优的方案。在评估阶段，通常可以进行网 络仿真，设置一些网络故障进行模拟分析，以检测设计出来的网络的可靠性。 2 2 2 p t n 网络规划与优化相关算法 网络规划中两个重要环节是拓扑规划和业务规划。在p t n 网络中涉及的拓扑 形式主要有网状网拓扑和环网拓扑。对于业务规划主要涉及业务分配和保护的一 些算法。其中的一些算法可以借鉴文献中提出传统光网络的规划算法。 对于环网拓扑，可以借鉴的组网方法有以下几种： 1 ) 利用节点之间的业务流量矩阵进行组网【1 6 】 该算法基本思想是首先将业务流量最大的两个节点相连，把这两个节点标记 为已处理，再从未标记的节点中取与当前端节点业务流量较大的节点与相应的端 节点相连，循环处理所有未标记节点，最后将首尾端节点相连成环拓扑。 2 ) 利用最短哈密尔顿( h a m i l t o n ) 回路进行组网【1 。7 】 图论中的哈密尔顿回路是指经过图中每一个节点一次且仅有一次的回路。如 果这个图中的边是带权值的，那么存在一个权值最小的哈密尔顿回路，称为最短 哈密尔顿回路。可见，在规划环网时如果找出最短哈密尔顿回路，就可以得到一 个优化的环网拓扑结构。该算法中，选取链路权值是关键。可以综合考虑网络中 节点之间的距离，业务流量分布情况和链路造价等费用来合成链路权值，这样可 以得到一个较优的环拓扑。规划软件中规划环网采用本算法。 对于网状网拓扑，组网方法主要是增加连接的算法和减少连接的算法。 1 ) 基于增加连接的组网算法 此类算法首先利用链路权值构造最小代价生成树，然后在构造出来的生成树 1 0 第二章p t n 网络规划与优化相关技术 上增加一些链路，用来改善网络的连通性，以达到预先的要求。构造最小代价生 成树的方法主要是一些经典算法，例如p r i m 、k r u s k a l 以及b o r u v k a 等。 2 ) 基于减少连接的组网算法【1 9 1 1 2 0 l 减少连接的算法中具有代表性的算法是y a g e d 删枝算法。该算法的主要思想 为：首先构造一个完全连通的初始网络，接着计算当前网络的连通度，看是否满 足目标网络的可靠性指标，如果不符合则将上一次的优化结果作为最终优化结果。 若符合则继续进行删枝优化，根据某种规则选取一条待删除的链路标为待删除， 进行业务分配。如果存在业务不能进行分配或者网络成本( 网络成本根据需要可 以有不同的表示方式) 变大，那么选取的待删除的链路不能删除。继续进行循环 删枝。直到处理所有待删除链路。y a g e d 删枝算法同时考虑了网络成本和可靠性指 标的问题，规划软件中规划网状网采用本算法。 业务规划涉及为业务寻找工作路径和保护路径的问题。寻找路径的基本算法 是d i j k s t r a 算法。寻路算法主要有固定路由算法和备用路由算法。固定路由算法的 主要思想是在网络业务到达前，对任意节点对间确定一条固定的可用路由。该算 法的优点是简单、速度快。不足之处是网络的平均阻塞率较高，因为当此条路由 上的资源己被耗尽时，所有的连接请求被阻塞。备用路由算法的基本思路是对任 意节点对间的业务确定多条备用的可用路由，并按一定的优先顺序排列，排在最 前面的称为主路由，其它的则视为备用路由。当主路由不可用时，依次尝试使用 备用路由。备用路由算法相对于固定路由算法来说，其优点是使网络的平均阻塞 率大大降低，并且使网络具有较强的故障恢复能力。规划软件中使用了备用路由 算法对业务进行分配。 业务保护方式分为通道保护和链路保护，规划软件中主要考虑了通路保护的 问题。根据业务的不同要求保护路径与工作路径满足链路分离或者节点分离，这 样可以抵抗单链路或单节点故障。 2 3本章小结 本章主要介绍了p t n 网络的相关知识和网络规划与优化的相关的一些技术。 首先介绍了p t n 网络的分层结构，以及p t n 网络的拓扑结构和生存性技术。其次 介绍了网络拓扑规划与优化的基本流程。最后针对p t n 网络，对与p t n 网络规划 与优化的一些算法进行了介绍。 电子科技大学硕士学位论文 第三章p t n 网络规划与优化软件系统总体设计与实现 3 1p t n 软件系统概述 3 1 1业务规划场景 该软件系统应用于p t n 网络的规划与优化。规划场景是指实际网络规划中的 应用抽象。软件系统中的规划场景是合作厂商根据实际用户需求提出的。涉及业 务规划场景有以下四种： ( 1 ) 网络拓扑确定，链路带宽确定，进行业务分配。 该场景对应后面章节的拓扑已知场景，具体又分为两种情况： a ) 对新业务的增量式规划 b ) 对全部业务进行规划 对于第一种情况是在网络中现有已分配业务的时候对新增业务进行规划，已 分配业务保持不变。 对于第二种情况是对网络中的所有业务进行重新规划。 两种情况可以统一，第二种情况相当于第一种情况新增批量业务( 把已分配 业务也看成未分配的) ，在新增批量业务到来前网络中没有已分配业务的情况。 规划软件在算法设计时考虑了第一种情况兼容第二种情况。 ( 2 ) 网络拓扑确定，链路带宽待规划。 此场景对应后面章节的链路待规划场景，在用户业务已知的情况下，根据业 务带宽需求，计算网络拓扑中带宽未知的链路的带宽需求，并对业务进行路由分 配。 此场景允许部分链路带宽固定( 不需要规划) 。 对于此场景，可以让用户指定每条带宽待规划的链路的最大链路带宽( 默认 为线路侧接口最大速率1 0 0 g ) 。在进行业务分配时，根据业务的规划目标进行路 由规划。规划完之后输出每条带宽待规划的链路的实际需要带宽。 ( 3 ) 网络拓扑优化 此场景是在场景1 和场景2 的规划结果上，进行有目的的删枝，删枝后的网 络拓扑仍可满足现有业务的需求。 1 2 第三章p t n 网络规划与优化软件系统总体设计与实现 系统考虑的删枝策略是：选择业务最少的链路，删除此链路，对业务重新分 配，如果网络拓扑仍可满足所有业务的需求，则循环删枝操作，否则将该链路标 为不可删，循环删枝操作，直到所有链路都标为不可删，删枝结束。 对于删枝过程中的业务规划过程类似于场景l 中的情况二。 ( 4 ) 网络绿地规划 此场景在用户业务已知、拓扑未知( 用户需指定网络的节点分布) 的情况下， 根据业务带宽需求，进行拓扑规划( 绿地规划) 。拓扑规划分为网状网规划和环网 规划。本文中绿地规划主要考虑拓扑规划，涉及的业务分配等功能整合到了拓扑 已知场景之中。 规划软件考虑将网络连成全连通图( 每两个节点之间都有连接) ，按照类似于 场景3 的规划方式进行网络拓扑优化，具体算法根据实际情况做了改进，详细说 明见4 2 5 小节。 3 1 2 网络层次关系 本软件系统面向的是基于的p t n 网络。该p t n 网络规划系统根据t - m p l s 的 分层结构进行层次划分，可以支持多层规划。网络层次包括用户业务需求层、p w 层、l s p 隧道层、物理拓扑层等。具体的分层结构如表3 1 所示。 表3 1p t n 网络层次结构 p t n 网络层次结构 层划分层内容速率 用户侧接口：t d m e l 、i m a e l 、 2 m s ，1 0 0 m s ，1 5 5 m s ，1 0 0 0 m s 用户业务需求层其中f e ，g e ，a t ms t m - 1 业务 f e 、g e 、a t ms t m 1 、c ls t m 1 4 为有弹性业务，速率由用户确定 p w 层用户业务的封装对应封装的用户业务速率 l s p 隧道层p