（电磁场与微波技术专业论文）ason网络分域优化机制及算法的研究.pdf

摘要 a s o n 网络分域优化机制及算法的研究 摘要 a s o n 作为下一代光网络的发展方向，其优化问题也是今后研究 的一大热点。随着a s o n 网络规模日益扩大，路由负荷也随之剧增， 单一的路由域( r a ) 中成千上万的设备给路由管理和连接管理带来 了诸多问题，例如路由算法的效率急剧下降。此外，网络管理员的权 限和职责的差异、区域的分散性都给网络管理造成了极大困难。目前， 国际标准化组织i e t f 和o i f 对现有口分组网络中已有的路由协议进 行改造和扩展，将其应用于光网络，已经提出了一些草案。a s o n 的 网络分层分域的框架正逐步得到完善。但是关于a s o n 的分域技术 在光网络中的具体实现，目前还没有统一而成熟的结果。 本文从网络资源整合与划分角度，考虑a s o n 网络的优化问题， 通过对a s o n 网络进行域的划分从而实现网络能在升级扩容后依然 保持良好的性能，并且方便管理者管理，有效地减少路由负荷等。分 域的a s o n 网络中，可以让每个路由域有独自的运行、诊断和自动 失效恢复能力；同时域内的变化不会影响到其他的路由域，便于某个 路由域独立的应用新技术和新拓扑。本论文的主要工作如下： ( 1 ) 对a s o n 网络优化中的一个问题网络结构的优化。通 过对a s o n 网络拓扑进行区域的划分，来完成a s o n 网络资源的合 理配置来达到优化a s o n 网络的目的。 ( 2 ) 提出了实现四种分域算法及程序实现方法。通过路由域整 合的方法，对四种分域算法进行了重优化。 ( 3 ) 论文采用o p n e t 仿真软件对各种算法进行了仿真，通过 实验数据对分域优化机制进行了综合全面的分析，最后对分域优化算 法进行了具体的描述和评价。 关键词自动交换光网络( a s o n ) 网络优化分域优化机制路由 域( r a ) 分域算法 t h er e s e a r c ho fn e t w o r k p a r t i t i o n a l g o r i t h m sf o ra s o no p t i m i t i o n a b s t r a c t n o w a d a y s m o r ea n dm o r er e s e a r c h e sf o c u so na s o no p t i m i t i o n 愈t h ee x p o n e n t i a lg r o w t ho ft h ed a t at r a f f i c ，m o r ea n dm o r en e t w o r k f a c i l i t i e sh a v eb e e nb u i l t ，s ot h em a n a g e m e n to ft h o u s a n d so fn e t w o r k f a c i l i t i e si nas i n g l er o u t i n ga r e a ( r a ) b e c o m e sm o r ea n dm o r ed i f f i c u l t t h en e e df o rp r o p a g a t i n gr o u t i n gi n f o r m a t i o ni si n c r e a s i n g ，w h i l et h e e f f i c i e n c yo ft h er o u t i n ga l g o r i t h m s i sd e s c e n t t h en e t w o r kp a r t i t i o n c o u l d b ei n t r o d u c e di n t on e t w o r ko p t i m i t i o no fa s o n ，p u r s u i n gf o r i n t e g r a t i n g a n d a s s i g n i n g t h en e t w o r kr e s o u r c e e a c hr o u t e a r e a i n d e p e n d e n t l yo p e r a t e d a n di n s p e c t e d e a c hr o u t ea r e ah a di t so w n p r o t e c t i o ns c h e m e t h e r e f o r e ，t h ec h a n g e si ns o m er o u t i n g a r e ac o u l dn o t a f f e c to t h e rr o u t i n ga r e a s ；n e wt e c h n o l o g ya n dn e wt o p o l o g yw e r ee a s i l y a p p l i e di nt h er o u t ea r e a s t h i sp a p e rp r e s e n t e da no v e r v i e wo ft h ed e v e l o p m e n t ，f e a t u r e sa n d r o u t i n ga r c h i t e c t u r eo fa s o n ，b r i e f l yi n t r o d u c e dt h er o u t i n gp r o t o c o lo f a s o na n dt h ei n t e r - d o m a i nr o u t i n gp r o t o c o l s ，s u c ha sd d r p , p c ea n d b g et h i sp a p e rf o c u s e do nt h er e s e a r c ho fn e t w o r kp a r t i t i o na l g o r i t h m s f o ra s o no p t i m i t i o n t h e r ew e r em a n yi n n o v a t i v e r e s e a r c h e si nn e t w o r kp a r t i t i o n a l g o r i t h m sf o ra s o no p t i m i t i o n ，w h i c ho ft h e ma r el i s t e da sf o l l o w s ： 1 f o u ra l g o r i t h m sf o ra s o nn e t w o r kp a r t i t i o nw e r ep r o p o s e d t h e a l g o r i t h m sw e r ed e s i g n e dt oa c h i e v eal o wi n t e r a c t i o nb e t w e e nd o m a i n s i na l li n t r a c a l t i e ro p t i c a ln e t w o r k 2 a c c o r d i n g t ot h es i m u l a t i o no no p m e tp l a t f o r m ，t h e p e r f o r m a n c e so ft h e s ef o u ra l g o r i t h m sw e r ec o m p a r e d k e yw o r d s ：a u t o m a t i c a l l ys w i t c h e dt r a n s p o r tn e t w o r k ( a s o n ) n e t w o r ko p t i m i t i o nn e t w o r kp a r t i t i o nr o u t i n ga r e a ( r a ) n e t w o r k p a r t i t i o na l g o r i t h m 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 成，乒 本人签名：笙坚坠日期：趟：! ：兰 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 本人签名：叠丛墨查 、 导师签名：兰z 乞导师签名：芝垒丝 日期：破! ! ：兰 日期：塑多：至二 北京邮电大学硕士学位论文第一章绪论 第一章绪论 自动交换光网络( a s o n ) 是下一代光网络发展的关键技术。a s o n 是在 传统光网络中引入控制平面，以实现光网络动态、快速的连接建立，并能实现 网络资源的优化配置，对业务提供有效的保护恢复，支持多粒度交换、多种新 型业务、动态带宽分配以及分布式连接建立和恢复，从而使光网络具有了高度 的智能。本文将重点对a s o n 的分域优化机制和算法进行研究。本章首先给出 了a s o n 的体系结构，然后介绍了a s o n 网络优化的研究背景，最后介绍论文 的主要工作和组织结构。 1 1a s o n 体系结构 随着光通信技术的发展，d w d m 解决了光通信中传输容量的问题，网络结 构的矛盾日益凸现出来，随着波长路由器、o a d m 、o x c 等技术日渐成熟， 智能光网络呼之欲出。1 9 9 8 年以美国s y c a m o r e 公司为代表的一批创业型小公 司在市场和网络建设的驱动下，率先提出了智能光网络( i o n ) 的概念，1 9 9 9 年，由北电和朗讯公司牵头在t i x l 5 会议上提出了a s o n 的概念和研究方向， 并受到众多通信厂商和运营商的认可和重视。t 1 x 1 将a s o n 结构作为北美的 建议提交给r r u t 。在2 0 0 0 年的u - t 会议上，正式确定由s g l 5 组开展a s o n 的标准化工作。自动交换光网络一经被正式提出，得到众多通信厂商和运营商 的重视和肯定。经过了几年的发展，智能光网络技术的研究取得了巨大的进展。 在概念上，与底层无关的智能光网络称为自动交换传送网( a s t n ) ，而底层为 光传送网( o ，i n ) 的a s t n 称为自动交换光网络( a s o n ) 。 智能光网络不仅可以适用于当前环形、线性和点到点的网络拓扑结构，而 且更适应于m e s h 网络结构，智能化的控制和管理使网络具有很强的灵活性。 自动交换光网络在传统的光传送网中引入了控制平面，使网络具有了动态交换 的能力，满足了数据业务的发展对网络功能提出的要求，对传送网技术和概念 的发展是一次重大的、具有革命意义的变化。 l t u tg 7 7 1 5 定义了在a s o n 网络中建立s c 和s p c 连接选路功能的结构 和要求。主要内容包括a s o n 选路结构、路径选择、路由属性、抽象信息和状 态图转移等功能组成单元。g 7 7 1 5 的目的是提供一种与协议无关的方法，用来 描述用于a s o n 的路由技术。从实现路由功能上来讲，路由体系结构包括与协 议无关的部件如链路资源管理器( u t m ) 和r c ，以及与协议相关的部件如协 北京邮电大学硕上学位论文第一章绪论 议控制器( p c ) 。其中l r m 向r c 提供所有s n p p 链路信息，并将其控制的链 路资源的状态改变告知r c ；r c 负责处理用于路由的抽象信息；而p c 则依据 信息经过的参考点( 如e n n i ，i n n i ) 处理与协议相关的消息，并将路由原语 传递给r c 。 可以看出，路由模块不仅具有路由选择的功能，还具备网络资源和拓扑自 动发现的功能，网络节点的控制实体之间实时地交换网络链路连接和资源利用 等信息，并在此基础上自动形成整个网络的拓扑信息，根据这些拓扑信息能够 为各种业务计算出符合要求的路由。a s o n 路由，不仅能够支持传统的集中式 路由方案，还能够提供分布式控制的路由计算，即网络的每个节点都有能力为 用户提供光通道的路由。按照g 8 0 8 0 的定义，a s o n 支持三种路由方式：分层 路由、源端路由和逐跳路由。 智能光网络路由的体系结构如图1 - 1 所示。这里，客户网络里的口路由器 附属于一个光核心网络，通过动态建立的光通道连接到它们的对等实体。其中， 智能光网络路由体系结构也隶属于整个网络结构之下。这个体系结构可以通过 两种网络模型来实现，即层叠模型和对等模型。层叠模型是一个客户服务器模 型，其中m 域是光域的客户。在这个模型里，光网络为口分组提供通过光域 传送的点到点光链路。每个终端用户可以通过一个明确的信令和路由接口，即 用户网络接口( 切m ) ，向光网络请求高带宽连接。同时，通过使用一个明确的 信令和路由接口，即网络网络接口( n n i ) ，可以进行子网连接。 图1 - 1 智能光网络中的路由体系结构 在对等模型里，终端用户是所有其他网元的对等体，能完全访问光网络拓 扑。通过这些信息，终端用户可以计算通过光网络的路由以满足特定需求，如 跳数、不同路由、延迟限制和可靠性要求等。 2 北京邮电大学硕上学位论文第一章绪论 1 2a s o n 网络分域优化研究的意义 自从2 0 世纪9 0 年代开始，全世界的通信建设和应用明显地加快了前进的 步伐。随着因特网的快速发展，口业务呈现爆炸式增长，电信网络从以承载语 音业务转向以承载数据业务为主。这给原有的网络带来了巨大的挑战。现有的 网络已经难以适应网络业务的发展需求。同时，网络的建设由于受到各个历史 时期不同的通信网体制、网络建设思想、技术经济客观条件等的限制，现有网 络存在结构复杂、技术体制不统一、运行维护困难、新业务提供不易等各种问 题。要改变现有网络无法满足发展需求的局面，对网络进行优化已势在必行。 广大电信运营商和设备厂商己经意识到对网络进行优化所带来的巨大经济效 益，特别是随着国内电信运营业竞争格局的形成，各大运营商为提升自身竞争 力，需要不断的优化现有网络、推出新业务、提升服务水平。因此，科学地进 行网络的优化已经成为运营商重点考虑的问题。而对于设备厂商来说，随着技 术的进步和市场需求的变化，其扮演的角色已经从过去单一的设备提供商，转 变成要求能够提供设备的应用、组网乃至运营等一系列解决方案的提供商角色。 在这种情况下，也迫切需要一套适合于自己要求的网络优化方法，以便能够更 好地满足运营商要求，提供优质的服务，增强自身的竞争能力。在a s o n 研究 深入的今天运营商未进行大规模建设的原因之一就是a s o n 网络规划与优划 的难题，因此对a s o n 优化的研究是菲常有必要且有意义的，可以为a s o n 网 络优化提供一定的参考。 随着光网络的规模日益扩大，路由的负荷也随之剧增，采用单一路由域( 凡蛐 给路由及连接管理都带来了诸多不便。此外。管理员的权限和职责不同以及区 域的分散性，网络由不同的设备厂商设备构成以及为将来的网络扩展考虑，都 迫切要求对a s o n 的网络进行分域，实现分层的网络路由体系，从而方便管理 者管理，同时有效的减少路由负荷并且为网络升级打好基础。为此g 8 0 8 0 给 出了路由域层次与子网点集( s n p p ) 的关系，g 7 7 1 5 y 1 7 0 6 阐述了a s o n 的路 由结构与需求，o i f 则在o i f 2 0 0 2 2 3 中给出了a s o n 分层路由的实现思想和相 应的域问路由协议( d d r p ) ，同时，正邗也对a s o n 的域间路由体系做出了进 一步的规范，但这些协议还不完善，具体的实现方案还有待进一步研究。 大规模网络的结构一般较复杂，往往包含多种单一结构，目前对复合结构 网络的优化研究较少，因此较为可行的办法就是首先将大型网络进行区域划分， 再对每个结构单一的区域分别进行优化这样不仅可降低优化网络的时间复杂 度，同时也是符合实际情况的，特别是目前一些较大型的网络，已经根据城市 规模进行了区域划分，但其并没有规范化的具体实施办法。现有网络的区域划 3 北京邮电人学硕士学位论文第一章绪论 分主要是依靠人工进行的，规划人员根据自身经验来对复杂网络进行区域划分， 这种人工区域划分方式存在有以下两方面的缺陷：一方面对规划人员专业知识 要求较高，另一方面增加了规划人员工作量，特别是对于大型网络，节点数上 百个，需要规划人员逐一确定每个节点所属区域，其工作量是相当大的。虽然， 目前己有一些辅助性网络规划软件考虑进了网络的分域问题，但其主要是提供 了区域划分的后续处理，如将区域自j 业务需求转化为区域内业务需求，将各区 域内部路由转化为跨区域路由等，而如何划分区域，划分多少个区域，每个区 域包含哪些节点仍然需要人为确定。因此有必要对网络区域划分具体方法进行 研究，提出切实可行的且易于计算机实现的算法。 1 3 论文研究内容及论文组成 论文的主要研究内容集中在分域的优化算法实现方面，具体工作如下：( 1 ) 对a s o n 网络优化中的一个问题网络结构的优化进行研究。通过对a s o n 网络拓扑进行区域的划分，来完成a s o n 网络资源的合理配置来达到优化 a s o n 网络的目的。( 2 ) 提出了实现四种分域算法( 基于节点d 的分域算法， 基于最高节点度的分域算法，基于业务的分域算法，基于地理位置的分域算法) ， 完成了算法的实现。 ( 3 ) 对四种分域算法在o p n e t 平台上进行仿真，比较了 应用四种算法进行分域后的网络性能参数。结果显示，基于业务的分域算法在 域间流量的问题上表现出了较好的性能，而基于地理位置的分域算法在域的平 均直径方面表现出较好的性能。 论文首先在第二章对a s o n 的优化机制作了简要的介绍。接着在第三章提 出了四种分域优化算法，并对四种分域算法进行了优化。第四章将分域算法应 用到n s f n e t 网络拓扑进行的仿真，并对仿真结果进行了分析。最后在第五章 对论文的内容和后续的工作进行了总结。 参考文献 【1 】删- ts t u d yg r o u p1 5 g 7 7 1 5 戌1 7 0 6 g 7 7 1 5 付1 7 0 6 - 2 0 0 2 a r c h i t e c t u r ea n d r e q u i r e m e n t sf o rr o u t i n gi na u t o m a t i c a l l ys w i t c h e do p t i c a ln e t w o r k s n - u - t 2 0 0 2 【2 】r r u - tr e c g 8 0 8 0 y 1 3 0 4 ，“a r c h i t e c t u r eo ft h ea u t o m a t i c a l l ys w i t c h e do p t i c a l n e t w o r k ( a s o n ) ”，2 0 0 1 【3 】韦乐平，鬈自动交换光网络的总体结构和标准框架”， 电信科学，2 0 0 1 年第5 期。 【4 】张杰，徐云斌，宋鸿升，桂煊，顾畹仪，自动交换光网络a s o n ，北京：人民邮 4 【5 】5 【6 】 阴 电出版社，2 0 0 4 年。 a bm c d o n a l d ，t fz n a t i ，“a m o b i l i t y - b a s e df r a m e w o r kf o ra d a p t i v ed 璐t e 血gi n w i r e l e s sa dh o en e t w o r k s ，”i e e ej s e l e c t a r e a sc o m m u n 1 7 ，1 4 6 6 1 4 8 7 ( 1 9 9 9 ) y r e k h t e r ，t l i ，s h a r e s ，i e t fr f c4 2 7 1 ，“ab o r d e rg a t e w a yp r o t o c o l4 ( b g p - 4 ) ，”j a n u a r y2 0 0 6 j 。lkr o m 【, 町f4 9 2 7 ，“p c e c ps p e c i f i cr e q u i r e m e n t sf o ri n t e r - a r e am p l sa n d g m p l st r a f f i c e n g i n e e r i n g , ”j u n e2 0 0 7 s 北京邮电人学硕士学位论文第二章a s o n 的优化机制 第二章a s o n 分域优化机制 2 1a s o n 优化中的分域问题 自动交换光网络( a s o n ) 是能够智能化地自动完成光网络交换连接功能的 新一代光传送网。a s o n 作为下一代光网络的发展方向，其优化问题也是今后 研究的一大热点。a s o n 的自动交换功能改变了传统光网络的业务配置方式。 在传统的网络规划中，业务的路由和网络拓扑设计都是在网络规划阶段同时完 成，所以可以在网络规划的同时完成网络的优化。a s o n 引入控制平面之后， 连接的建立和拆除都是动态过程，由控制平面的路由控制器r c 完成路由计算 的功能。虽然可以通过固定路由表的方式限制业务的选路，但是这种模式使得 动态连接建立不是基于网络的现状进行，故无法保证其路径是否优化。所以 a s o n 网络优化必须分解成连个部分：路由优化和网络结构优化。其中路由优 化通过改进路由控制器r c 中的算法来体现，而网络结构的优化可以沿袭传统 光网络优化设计的模式，在网络规划阶段完成。 每个最优化问题都包含一组限定条件( c o n s t r a i n t ) 和一个优化函数 ( o p t i m i z a t i o nf u n c t i o n ) ，符合限制条件的问题求解方案成为可行解( f e a s i b l e s o l u t i o n ) ，使优化函数取得最佳值的可行解称为最优解( o p t i m a ls o l u t i o n ) ， 通过对限制条件和优化函数的设计，可实现不同类型的优化算法。按照限制条 件和优化目标，可将a s o n 优化问题划分成若干领域，这些领域之间存在相互 交叉的关系，如图2 1 所示。 我们对网络进行优化规划的目标有很多，包括提高网络生存性、提高资源 利用率、降低投资、提高投资收益比等，例如资源的优化，即对使用不合理的 资源进行重路由，以使得全网的资源利用趋于合理，还可以进行碎片整理，节 约网络资源。具体优化可以按照单目标进行，也可以按照多目标的方式进行， 常用的应该是多目标优化，即把最重要的目标作为优化目标，其它目标作为约 束条件来进行综合的优化和规划。 6 北京邮电大学硕 ：学位论文 第二章a s o n 的优化机制 业务预测 、 、 一， 图2 1a s o n 优化的研究颁域 a s o n 的自动交换功能改变了传统光网络的业务配置方式。在传统的网络 规划中，业务的路由和网络拓扑设计都是在网络规划阶段同时完成，所以可以 在网络规划的同时完成网络的优化。引入控制平面之后，连接的建立和拆除都 是动态过程，由控制平面的路由控制器r c 完成路由计算的功能。虽然可以通 过固定路由表的方式限制业务的选路，但是这种模式使得动态连接建立不是基 于网络的现状进行，故无法保证其路径是否优化。所以a s o n 网络优化必须分 解成两个部分：路由优化和网络结构优化。其中路由优化通过改进路由控制器 r c 中的算法来体现，而网络结构的优化可以沿袭传统光网络优化设计的模式。 我们对网络进行优化的目标有很多，包括提高网络生存性、提高资源利用 率、降低投资、提高投资收益比等，例如资源的优化，即对使用不合理的资源 进行重路由，以使得全网的资源利用趋于合理，还可以进行碎片整理，节约网 络资源。具体优化可以按照单目标进行，也可以按照多目标的方式进行，常用 的应该是多目标优化，即把最重要的目标作为优化目标，其它目标作为约束条 件来进行综合的优化和规划。 7 北京邮电大学硕士学位论文 第二章a s o n 的优化机制 图2 - 2 网绍优化流程图 如图2 2 所示为a s o n 网络优化技术的方案流程图，下面我们将结合给出 的流程图方案重点从网络结构优化进行介绍。 8 北京邮电大学硕上学位论文 第二章a s o n 的优化机制 本论文的研究点主要是从a s o n 优化中的网络结构优化入手，通过划分路 由域来实现a s o n 的网络优化。网络结构优化主要解决拓扑设计和网络划分的 问题。拓扑设计问题在所有的网络中均存在，目前在s d h 网络中广泛采用环形 和链形结构进行组网，a s o n 主要是基于网状网( m e s h ) 结构而设计的，采用 m e s h 结构可以提高网络的生存性，简化网络结构和提高资源的利用率。然而要 充分发挥m e s h 结构的优势需要基于合理的容量设计，主要包括工作容量设计 和本分容量设计。可以在传统光网络规划设计的基础上，通过对业务量的预测， 采用网络规划设计辅助工具软件进行网络的模拟，按照一定的比例来分配。 网络划分问题解决“如何划分大网络”的问题。当网络规模扩大时，很多 路由算法的效率急剧下降，而且，从网管角度看，网络规模过大也会造成管理 上的困难。目前解决这个问题的方法是对网络进行划分。传送网可以从垂直方 向分解为若干独立的传送网络层，即层网络，相邻层网络之间具有客户朋艮务者 关系。每一层网络在水平方向又可以按照该层内部结构分割为若干部分，从而 分层和分割是正交关系。 随着a s o n 网络规模日益扩大，路由负荷也随之剧增，单一的路由域( 1 认) 中成千上万的设备给路由管理和连接管理带来了诸多问题，例如路由算法的效 率急剧下降。此外，网络管理员的权限和职责的差异、区域的分散性都给网络 管理造成了极大困难。 因此我们从网络资源整合与划分角度，考虑a s o n 网络的优化问题时，要 通过对a s o n 网络进行域的划分从而实现网络能在升级扩容后依然保持良好的 性能，并且方便管理者管理，有效地减少路由负荷等。分域a s o n 网络中，可 以实现分层的网络路由体系，让分域模型中的每个路由域有独自的运行、诊断 和自动失效恢复能力；同时域内的变化不会影响到其他的路由域，便于某个路 由域独立的应用新技术和新拓扑。在多个路由域中，域和域之间只传递概括后 的路由信息，而不是全部路由信息，这样可以有效减少网络路由负荷，提高网 络伸缩性以及可管理性。网络中的r a 由子网、连接子网的链路和这些链路的 端点组成，可进行递归分割，一直被分割到最小的包含两个子网和一条链路的 子路由域。 分域是a s o n 网络区别与其他传统骨干网络的一大特色之一正是由于引 入了分域的概念，才允许按照区域对a s o n 网络进行管理，因此，在a s o n 网 络优化阶段，如何对网络进行划分是必须要考虑的问题。 2 2 分域对域间接口的要求 9 北京邮电人学硕一t ：学位论义第一二章a s o n 的优化机制 由于目前域间接口并不完善，因此，在a s o n 分域问题上，需要考虑如下 五种情况： 1 通过域间接口实现对a s o n 分域的规划( 如图2 3 ) ；在这种情况下， 需要域间接口比较成熟，规划人员按照网络的实际情况，直接对a s o n 进行分 域。在域内，使用s p c s c 连接。 网络与网络接口 f n n i a s o n 域鸵 卜； 图2 - 3 域间接口实现分域 2 当域间互连互通不理想的时候，a s o n 网络的分域通过i p 路由器来完成 ( 如图2 4 ) ，业务自动通过客户端发起连接或者拆除，在每一个a s o n 域内， 可以存在多种独立的保护与恢复方式。 ( u n l )( u n i ，用户网络接口 脚蝴a s 。誓娜，二删二脚n 域般u n i 圳_ jlj 洲 删r _ i d r _ 1 一”1 图2 4 i p 路由器实现分域 3 当域间互连互通不理想的时候，除了通过方式2 分域以外，还可以通过 u n i 接1 3 进行域的划分( 如图2 5 ) 。 脚端口一i 魏? 上脚n 域缎零撕 _ - _ _ h c j 、i j 耻幂u 用户网络接口 a s o k ? 毒毒。： 。一 一 l n q i l 1 jlj 11刺1 鼎r - i dr 弋引“ 图2 - 5u n i 接口实现分域 4 当域间互连互通不理想的时候，除了通过2 、3 方式分域以外，还可以 通过永久连接( p c ) 进行域的划分( 如图2 6 ) 。 1 0 北京邮电大学硕l j 学位论文 第_ 二章a s o n 的优化机制 翱陵、 j 、i 、 l ，i j 。，。鳘a s 。n 域带2 按 ，譬i 。=一一 阢连新i11 涮 蒯r 订r - 面五叫“。 5 传统的s d h 网络也可以将两个a s o n 域连接在一起，带外i p 网络完成 艮卜旦! 【曩 、。 一- 一；：篡。i 、一 网络的优化规划工作一般是离线进行的，但是它- q 现网有接口，可以在线 把现网上的数据采集过来进行分析和处理，利用这些资料，对现网进行优化分 析，并把优化后的数据逐条下载到网管上，动态实现对网络优化的管理。 网络中路由域的划分可以基于管理权利限制，也可以基于技术，可以基于 地理部署位置，也可以基于网络层次。可以把路由域划分为水平方向的分割和 垂直方向的分层，这两种方式是相互独立而又统一的。网络中的路由域由子网、 连接子网的链路和这些链路的端点( s n p p ) 组成，它们可递归地分割，可一直到 最小的包含两个子网和一条链路的子路由域。当在同一层次中的路由域再次进 2 3a s o n 网络的优化算法 在a s o n 的优化的过程中，采用现代优化理论和算法是非常重要的一点， 也是区别于其它传统网络的不同之处。 a s o n 的网络规划输出结果应该在设备配置、客量需求、流量模式和网络 可用性方面达到成本最小、路由最优、而且a s o n 网络的计算是基于开放的、 分布式的机制进行的，在性能方面必须满足业务的需要，如分层的保护和恢复 机制以及对失效的处理等。因此，需要先进的算法和模拟技术来支持逻辑层和 物理层的设计，在每一层使网络资源最大化。 根据a s o n 的动态特性、业务需求以及节点线路等的具体要求，建立a s o n 北京邮电大学硕士学位论文第二章a s o n 的优化机制 网络模型，依据网络模型建立a s o n 网络规划的多目标函数，并设立约束条件。 根据实际需要可以选择合适的现代优化算法求解该函数，比较常用的算法有遗 传算法、模拟退火、禁忌搜索、蚁群算法等。有关这些算法在第一阶段报告稿 中有具体算法描述，本文仅简单阐述这些算法的基本原理和特性。 1 穷举法 穷举法是指对所有可行解进行评测。在任何一个网络规划问题中，通常会 有大量的可行解，对每一个可行解，都要通过完整的计算过程来完成对所需网 络参数的评估。显然，穷举法适用于可行解有限且评估标准较为简单的情况。 2 分支定界法 分支定界是用于改进穷举速度的一种技术。关键是采用一些方法来缩小优 化解评估标准的范围。该法不必对所有可行解进行评估，通过确定的界限可排 除部分解。尽管分支定界法可以减少需进行开销评估的解的数目，但剩下的解 的数目仍很多，这大大限制了可处理问题的规模。 3 放宽条件法 放宽条件法是一种使有限制的优化问题简单化的技术。大致思路是剔除一 些限制条件或者是用一些较为宽松的限制来替代。这个较低的界限会对得的可 行解的优劣给出一定的信息，即与实际最优解在距离上的限制。通常放宽条件 法不能用与最低约束同样的开销获得可行解，此时可能会存在某些放宽差距。 4 模拟退火法 模拟退火算法( s i m u l a t e da n n e a l i n g , s a ) 是一种随机寻优算法，其出发点是 基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火 法采用了一种模拟金属冷却直至冻结成最小能量状态的晶体结构的过程，在一 个更为普遍的系统中寻找一种最小值。该算法1 9 5 3 年由m e t r o p o l i s 等人提出， 1 9 8 3 年k i r k p a t r i c k 等人将其用于组合优化。模拟退火算法与统计力学中的热 平衡相似，在给定温度下，该算法可在一定概率下“爬山 到代价更高的解，以 防搜索过程陷入局部极小，当温度趋于零时，求得整体最优解。 就像名字中所表达的，由于该算法适合较大范围内的优化问题，故而引起 了广泛的关注，特别是当所求的全局最大最小解隐藏在很多的局部最大最小解 中时。模拟退火法无法避免产生局部最小值，但从总体上说，该算法还是能够 给出较优解的。在优化过程中，解容易产生在低开销区域而非高开销区域中。 模拟退火法实现简单，所以在组合优化问题中模拟退火法比较受欢迎。该算法 的缺点是对c p u 的要求高，且对一个已存在的较好解来说，很难进行额外的改 善。 5 禁忌搜索法 北京邮电大学硕十学位论文 第二章a s o n 的优化机制 禁忌搜索算法是一种新型启发式算法。基本思想是一种随机的本地搜索， 但是某些移动被禁止。简单的禁忌搜索法的基本思想是：给定一个当前解( 初 始解) 和一种邻域，然后在当前解的邻域中确定若干候选解；若最佳候选解对 应的目标值优于“b e s ts of a r ”状态，则忽视其禁忌特性，用其替代当前解和“b e s t s of a r 状态，并将其相应的对象加入禁忌列表，同时修改禁忌列表中各对象的 任期；若不存在上述候选解，则选择在候选解中选择非禁忌的最佳状态为新的 当前解，而无视它与当前解的优劣，同时将相应得对象加入禁忌表，并修改禁 忌表中各对象的任期；如此重复上述迭代搜索过程，直至满足停止准则。 禁止态搜索的效率仅取决于禁止列表的定义和操作方式。由于禁止态的搜 索本身没有任何限制，该算法是一种非常通用的策略。尽管禁止态搜索法在实 现上比模拟退火更为复杂，但该算法不受特殊问题的限制。 6 连续平滑近似法 此方法的基本思路与模拟退火法类似，但却不包含可以影响解的变化的各 变量。该算法的目标函数是以一种确定的方式连续地进行处理的，而且只有对 当前目标函数有利的变化才是可以接受的。基本思路是：起始的目标函数可以 近似的线性( 二阶导数) 反映全局属性，当该过程包含的对属性的描述越来越 精确时，就会向实际目标函数收敛了。 与模拟退火法的随机特性形成尖锐的对比，故而连续平滑近似法的反复次 数会少得多；但在另一方面，该算法对开销函数的评估较为复杂。 7 模拟分配法 模拟分配( & 让) 是一种通用的随机组和优化方法，该法与模拟退火法有 些类似。s a l 算法产生离散时间随机过程轨线，称为分配过程。分配过程的目 标是为实现传输容量需求提供足够的网络容量资源。该方法的主要优点在于可 以指定不同的分配规则( 比如考虑路径的差别) 并应用于分配过程。 8 遗传算法 遗传算法( g e n e t i ca l g o r i t h m ) 是生物进化理论和现代计算技术相互结合所 形成的一种全新的算法，由美国密西根大学h o l l a n d 教授和他的学生提出并发 展。遗传算法解决问题具有鲁棒性、全局最优性、高效并行性的特点，既不要 求函数的连续性，也不要求函数的导数信息，在出现非连通性和非凸性的情况 下也能求解。遗传算法已经在许多研究领域得到了广泛的应用【1 1 】。 但是，遗传算法需要经过多次反复以找到高质量的解，也就是说，要花费 很长的时间来产生优秀解。当各子串在构造上存在相似的阻塞性时，向全局解 的收敛就会变得很困难。另一方面，该算法允许在较大空间内进行搜索。认识 领域在对问题的描述和对参数、操作的选择过程中起到了很重要的作用。 北京邮电大学硕j ：学位论文 第二章a s o n 的优化机制 对任何可以产生多种解的网络结构优化方法来说，都可以采用遗传规划来 做加速优化器。如果问题的公式化表示是一个多商品流问题，且该问题的限制 条件只涉及到边缘的流量，可以采用以下方法：对一对解要寻找一个切点( 将 一个网络化分为两个子网的一系列网络元素) ，在该切点，两个解流量相同， 但切点两侧两个子网内的解是不同的。这样，就可以通过将切点两侧的两个不 同解相结合产生新的可行解。 9 蚁群算法 蚁群算法是一种基于模拟蚂蚁群行为的随机搜索优化算法。虽然单个蚂蚁 的能力非常有限，但多个蚂蚁构成的群体具有找到蚁穴与食物之间最短路径的 能力，这种能力是靠其在所经过的路径上留下的一种挥发性分泌物( p h e r o m o n e ) 来实现的。蚂蚁个体间通过这种信息的交流寻求通向食物的最短路径。已有相 关计算实例表明该算法具有良好的收敛速度，且在得到的最优解更接近理论的 最优解。 1 0 启发式算法 这是一种可以对操作进行选择的搜索技术。该算法以解决特殊问题的实践 经验为基础( 比如：首先考虑较大的需求再考虑小的需求) 。由于这些规则是 从获得较好结果的实践经验中总结出来的，所以可能无法通过数学方法进行严 格证明。这些规则为问题的求解定义了一条“路径 。尽管最初看起来这不是 解决这类问题的最佳方法，但还是令人惊讶地在优化问题的世界里散布开来； 举个例子来说，该算法已经被应用在智能网的计算中【1 4 】。启发式算法可与其 它算法结合使用以便降低该算法的复杂性。该算法可以在合理的计算时间中找 到解( 多项式的次数由问题的规模决定) ，但是无法保证每一个解都是最优的。 尽管所求得的解与实际的优化解存在一定的距离，但还是将该解的某些属 性标记为可接受，以便减少优化解的个数。度的把握要依赖于遗传算法的质量。 鉴于该算法的实践基础，如果可以对误差率进行估计，算法质量就会得到加强。 2 4 分域算法对协议的支持 路由技术是a s o n 网络优化的核心技术之一，它在实现a s o n 连接的动态 选路方面发挥了重要的作用。目前u - t 、i 口t f 和o 三大国际组织都提出了 关于a s o n 路由的相关草案。为了适应未来规模日益巨大的网络的发展要求， 解决单一路由域( r a ) 成千上万的设备对路由以及连接管理带来的诸多问题，迫 切需要对网络分域，实现分层的网络路由体系，为此，g 8 0 8 0 给出了路由域层 次与子网点集( s n p p ) 的关系，g 7 7 1 5 y 1 7 0 6 阐述了a s o n 的路由结构与需求， 1 4 北京邮电人学硕七学位论文 第二章a s o n 的优化机制 o i f 则在0 i f 2 0 0 2 2 3 中给出了a s o n 分层路由的一种实现思想和相应的域问路 由协议( d d r p ) ，同时，i e t f 也对a s o n 的域问路由体系进行了明确的解释。 以下对分域算法支持的协议进行简单介绍。 1 、b g p b g p 属于外部网关协议，为t c p i p 互联网设计，用于多个自治域之间， 主要完成不同运营商网络之间的路由计算。严格来讲，b g p 既不基于纯粹的链 路状态算法，也不基于纯粹的距离向量算法。b g p 使用t c p 作为传输协议，对 于网络的拓扑结构无限制，只对增量路由进行发送，而非周期性的广播所有路 由信息。在a s o n 中，b g p 被推荐作为不同运营商网络之间e n n i 的域问路 由协议。 i e t f 于1 9 8 9 年发表了b g p 的第一个版本，之后分别于1 9 9 0 、1 9 9 1 、1 9 9 5 年发表了b g p 2 、b g p - 3 、b g p - 4 ，目前b g p 4 是最新版本。b g p - 4 是用于多 个自治域之间的路由协议，主要功能是在各个实现了b g p 4 协议的系统之间交 换网络可达性信息。这些信息包括一个路由所穿越的自治系统列表，它们足以 建立一个表示连接状态的图。 b g p 的重要特点是基于策略的路由协议体系，不要求对整个路由表进行周 期性地刷新，而是可以根据各种路由需求和限制条件( 如经济、安全以及政治 考虑等) 提供各种强制性的路由策略。 2 、d d r p d d r p 为域问路由协议，目前0 1 f 将d d r p 改称为“运营商内基于o s p f 的 e m 虮路由”。但是d d r p 并不是一个全新的路由协议，它是基于o s p f 的域 到域路由协议，用于提供一个应用于电路交换光网络的域问路由，不定义控制 域内的点到点路由协议，也不规定域内使用任何特定的路由协议。d d r p 采用 分级路由结构，而同时又在每个路由等级运行g m p l s o s p f 路由协议。 d d r p 通过g 7 7 1 5 中定义的路由控制器在不同的通信实体之间进行控制， 在两个通信实体之间的路由控制器可能会是多个“口跳 。 为了满足网络的可扩展性要求，o i f 要求域问路由协议支持分级路由方式， 并至少支持4 个等级。在每个路由等级应使用基于链路状态的路由算法。初期 o i f 对e m 灯路由的要求是应以已有的路由协议为基础，而不是发明一种新 的协议，并应该使用支持多等级路由的路由协议，如p n n i 。但是很多人反对使 用p