（电磁场与微波技术专业论文）多层多域光网络层域划分及路由算法研究.pdf

t 产 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致i 胄 中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：墨垒至日期： 2 0 l o 1 0 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 本人签各一邸彳 导师签名：型丝兰 同期： r 觌：? pi | j 妇 二 多层多域光网络层域划分及路由算法研究 摘要 自动交换光网络( a s o n ) 是能够智能化地自动完成光网 接功能的新一代光传送网，路由技术是它的核心技术之一， a s o n 连接的动态选路方面发挥了重要的作用。a s o n 的路由 种，层域路由是其中的一种。 ， 本课题主要关注自动交换光网络( a s o n ) 中的层域路由 们的研究旨在揭露影响层域路由的因素，并根据这种因素设计性能优 良的层域路由算法和层域划分方法。 我们发现，层域划分、静态路由表运算和动态路由优选等因素均 对层域路由的阻塞性能有着显著影响。这种影响具体表现在底层域对 高层域屏蔽路由信息和域间链路呈现高阻塞两个方面，我们将其称之 为域问路由屏蔽效应和域间链路拥堵效应。 我们结合传统的扁平网络路由和波长分配技术，对层域光网络固 定路由、固定备选路由进行研究，发现这些成熟的路由技术均能够提 高层域光网络的路由性能。在此基础上，我们开发了一种新的路由算 法，这种算法在域间路由层面采用固定备选路由，在域内路由层面上 采用固定路由，因此减少了全网统一采用固定备选路由所带来的信令 开销和路由存储开销。经过数学分析和仿真，我们证明了这种算法在 付出较小代价的前提下得到了较大的性能增益。 在路由算法的研究过程中，我们发现使用现有技术对路由算法进 行改进带来的增益并不可观，而改变层域结构对于路由的影响更为显 著。因此我们就光网络层域结构对层域路由的影响进行了深入研究。 我们将层域结构抽象出两种属性( 域数目，域相对大小) ，并通 过这两种属性提出一个参数a ( 域间业务种类总数域内业务种类总 数) 。我们使用该参数将网络的层域结构这一静态量与网络的阻塞性 能这一动态量联系起来，解决了如何分域能够使层域路由的阻塞性能 更好的问题。在此基础上，我们提出了一套评估和衡量层域结构的好 坏的框架。 最后，我们实现了分层分域光网络路由仿真平台，这种平台具有 方便的界面进行网络拓扑输入、层域划分、路由算法开发与应用、离 散事件路由算法仿真。仿真得到的数据经处理后，也证明我们分析的 正确性。 关键词：a s o n ，层域路由，r w a ，分层划域 r e s e a r c ho fc l u s t e r i n ga n dr o u t i n g a l g o r i t h mo fh i e r a r c h i c a lo p t i c a l n e t w o r k a b s t r a c t a s o ni sn e wg e n e r a t i o no p t i c a lt r a n s m i s s i o nn e t w o r kw h i c hc a n i n t e l l i g e n t l ya n da u t o m a t i c a l l y f u l f i l lt h e s w i t c h i n ga n dc o n n e c t i n g f u n c t i o no fo p t i c a ln e t w o r k r o u t i n gi st h ek e yt e c h n o l o g yo fa s o n ，a n d i s i m p o r t a n ti nd y n a m i cr o u t e s e l e c t i o ns t a g ei na s o nc o n n e c t i o n e s t a b l i s h m e n t t h e r ea r et h r e e r o u t i n gt e c h n o l o g i e s i na s o n ，a n d h i e r a r c h i c a lr o u t i n gi so n eo ft h e m t h i sw o r km a i n l yf o c u s e so nh i e r a r c h i c a lr o u t i n gp r o b l e mi na s o n t h ep u r p o s eo fo u rr e s e a r c hi st or e v e a lt h ef a c t o r sw h i c hi n f l u e n c et h e p e r f o r m a n c eo fh i e r a r c h i c a lr o u t i n g a n da c c o r d i n gt ot h a tw ec a nd e s i g n w e l lp e r f o r m e dh i e r a r c h i c a lr o u t i n ga l g o r i t h ma n dc l u s t e r i n ga l g o r i t h m w ef o u n dt h a th i e r a r c h i c a l c l u s t e r i n g ，s t a t i cr o u t i n gt a b l ea n d d y n a m i cr o u t es e l e c t i o ni m p o s e do nb l o c k i n gp e r f o r m a n c eo fo p t i c a l h i e r a r c h i c a ln e t w o r k i np a r t i c u l a r , t h e r ea r et w ok i n d so fi n f l u e n c e s ， w h i c ha r et h a tl o w e rd o m a i n ss h i e l dr o u t ei n f o r m a t i o nf r o mh i g h e r d o m a i n s ，a n dt h a ti n t e r - d o m a i nl i n kh a sh e a v yl o a d w ec a l lt h e ml o w e r d o m a i n ss h i e l d i n ga n dh e a v yl o a do fi n t e r - d o m a i nl i n k b a s e do nt h er o u t i n ga n dw a v e l e n g t ha s s i g n m e n tt e c h n o l o g yo f t r a d i t i o n a lf l a tn e t w o r k ，w ed i dr e s e a r c ho nf i x e dr o u t i n ga n df i x e d a l t e r n a t i v er o u t i n g ，a n df o u n dt h a tt h e s em a t u r et e c h n o l o g i e sc o u l d i m p r o v et h er o u t i n gp e r f o r m a n c eo fo p t i c a lh i e r a r c h i c a ln e t w o r k f u r t h e r m o r e ，w ed e v e l o p e d an o v e l r o u t i n ga l g o r i t h m ，w h i c h f u nf i x e d a l t e r n a t i v er o u t i n go ni n t e r - d o m a i nr o u t i n g ，a n dr u nf i x e dr o u t i n go n i n n e r - d o m a i nr o u t i n g s ot h i sr o u t i n ga l g o r i t h mc o u l dr e d u c et h ec o s to f i n s t a l l i n gf i x e da l t e r n a t i v er o u t i n go ne n t i r en e t w o r k t h r o u g hm a t h a n a l y z ea n ds i m u l a t i o n ，w ep r o v e dt h a t t h i s a l g o r i t h mc o u l dg e tg o o d p e r f o r m a n c eg a i nb yl i t t l ec o s t t h r o u g hr e s e a r c ho fh i e r a r c h i c a l l i t t l ep e r f o r m a n c eg a i nb yu s i n gc u r r e n t h eh i e r a r c h i c a ls t r u c t u r eh a dm o r e p e r f o r m a n c eo fo p t i c a lh i e r a r c h i c a ln e t w o r k s ow ed i df o r w a r dr e s e a r c h o nt h ei n f l u e n c eo fh i e r a r c h i c a ls t r u c t u r eo nh i e r a r c h i c a lr o u t i n g w ea b s t r a c t e dt w op r o p e r t i e s ( t h en u m b e ro fc l u s t e r s ，t h ev a r i a n c eo f c l u s t e rs i z ed i s t r i b u t i o n ) f r o mh i e r a r c h i c a ls t r u c t u r e ，a n dt h r o u g hw h i c h w ep r o p o s e dap r o p e r t y 口( t h et o t a lk i n do fi n t e r c l u s t e rt r a f f i c t h et o t a l k i n do fi n n e r - c l u s t e rt r a f f i c ) w eu s e dat ob u i l dc o n n e c t i o nb e t w e e nt h e s t a t i cp r o p e r t y ( h i e r a r c h i c a ls t r u c t u r e ) a n dd y n a m i cp r o p e r t y ( b l o c k i n g p e r f o r m a n c e ) ，a n df i g u r e d o u th o wt od o c l u s t e r i n g c o u l dm a k e h i e r a r c h i c a ls t r u c t u r e h a v i n g s m a l l b l o c k i n gp r o b a b i l i t y l a t e r , w e p r o p o s e daf r a m e w o r kt h a tc o u l da s s e sa n de v a l u a t et h ep e r f o r m a n c eo f h i e r a r c h i c a ls t r u c t u r e a tl a s t ，w ed e v e l o p e das i m u l a t i o np l a t f o r mp r o v i d i n gc o n v e n i e n t u s e ri n t e r f a c et oi n p u tt o p o l o g y , t od oc l u s t e r i n g ，t od e v e l o ph i e r a r c h i c a l r o u t i n ga l g o r i t h m ，a n d t or u ns i m u l a t i o n t h er e s u l t p r o v e d o u r c o n c h l s i o n s k e y w o r d s ：a s o n ，h i e r a r c h i c a lr o u t i n g ，r w a ，c l u s t e r i n g 产 目录 第一章绪论1 1 1自动交换光网络( a s o n ) 的背景。1 1 2a s o n 分层分域路由的计算机制1 1 3题目的意义3 1 4本论文主要内容5 第二章多层多域光网络的结构和路由协议6 2 1a s o n 的多层多域结构6 2 2a s o n 多层多域路由协议9 2 2 1层域路由功能要求9 2 2 2层域路由协议1 0 第三章多层多域光网络的路由特性1 3 3 1分层分域路由的实现1 3 3 1 1初始化计算层备选路由1 3 3 1 2分层选路1 4 3 2分层分域路由性能分析1 5 3 2 1分层分域结构的路由屏蔽效应1 5 3 2 2分层分域路由的域间拥堵效应1 6 3 3多层多域环境下固定备选路由( f a r ) 的改进1 7 3 3 1静态与动态结合的部分f a r 算法。1 9 第四章多层多域光网络层域划分的路由特性2 4 之 4 1网络状态2 5 4 2阻塞率分析2 7 4 3层域划分与口的关系2 8 4 4仿真和结果2 9 4 5 结论3 1 第五章仿真平台的设计与实现3 2 5 1平台设计3 2 5 1 1层域结构的表达3 2 5 1 2仿真流程的设计3 5 5 2仿真的实现4 2 5 2 1平台的框架4 2 5 2 2框架内容及功能4 3 5 2 3具体实现4 3 5 3平台的效果演示( 图尽量与提交的布重叠) 4 7 5 3 1三种视图4 7 5 3 2域操作4 8 5 3 3分层划域辅助工具4 9 5 3 算法选择和结果显示5 0 第六章综述5 0 参考文献5 2 j l | 【谢5 3 作者攻读学位期间发表的学术论文目录。5 3 玎 1 广 ， 北京邮i 乜入学2 0 1 0 届毕业设计( 论文) 1 绪论 1 1 自动交换光网络( a s o n ) 的背景 自动交换光网络( a s o n ) 是能够智能化地自动完成光网络交换连接功能的 新一代光传送网，路由技术是它的核心技术之一，它在实现a s o n 连接的动态 选路方面发挥了重要的作用。在传统的i p 网络里，数据转发是逐跳进行的、面 向无连接的方式，不需要事先建立连接。同l p 网络的路由不同，在基于电路交 换的光网络中，数据的交换是基于端到端的，需要事先建立连接，同时a s o n 路由实现了控制和传送通道的分离，使得在传送连接建立请求时不会影响已有的 业务，也不会使现存的连接丢失。在路由协议方面，由于光网络中的路由协议并 不直接参与数据平面的交换，因此可以认为其是不影响业务的，这就使得光网络 的路由协议可以非常灵活地包含各种新的信息。由于光网络中的连接是显示路由 的，因此不同的网元不需要使用相同的路由算法；另外，光网络中的带宽统计也 要比i p 网络简单，从而使得带宽资源的管理更加容易。综合以上特点，目前 h u t 、i e t f 和o i f 三大国际组织都提出了关于a s o n 路由的相关草案。其中， 为适应未来规模同益巨大的网络的发展要求，解决单一路由域中成千上万的设备 对路由以及连接管理带来的诸多问题，迫切需要对网络分域，实现分层的网络路 由体系，为此，l t u tg 8 0 8 0 1 给出了路由域层次与子网点集( 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 ) 。另外，i e t f 也对a s o n 的域问路由体系进行了明确的阐述。在分层路由结构中，整个通信 网络可以被划分为多个子网，子网内部的详细拓扑信息可以通过拓扑抽象算法进 行有选择的汇聚，经过汇聚和简化后的路由信息将被广播到其他的子网中。这种 分层多域的路由结构可以大大减少域问路由信息的交互，从而保证了大规模网络 的路由可扩展性。随着智能光网络规模的逐渐扩大，对其进行分层、分域势在必 行。 路由问题是层域光网络的核心问题，基于不同的网络层次、网络结构、业务 要求、资源要求等都会有不同的路由策略，下面我们就从路由的计算机制和路由 算法设计两方面分别来对路由策略进行介绍。 1 2 a s o n 分层分域路由的计算机制 首先，单从机制的主要分类来看，路由的计算机制一般分为集中式路由计算 北京邮电人学2 0 1 0 届毕业设计( 论文) 机制和分布式计算机制两大类，后者主要用来解决大规模网络内的路由问题，本 项目的路由算法实现机制为分布式路由【2 】。分布式路由相比集中式路由，从路 由获得的方式、各业务路由问的协调、计算速度、容量利用效率及实现难度五个 方面都有着明显的区别，具体分析如下。 1 ) 路由获得的方式上的区别：集中式路由算法要求有一个中心控制节点， 它需要知道整个网络的物理拓扑结构、节点连接情况、业务资源使用状况、路由 表等状态信息。在分布式控制方式中，通常是由业务的源宿节点来启动路由的计 算过程。而且网络中的每个节点甚至网关节点无需知道全网络的所有资源，只需 要知道同自己相关的链路资源信息，仅仅利用邻接链路或者附近链路信息来计算 路由。 2 ) 各业务路由问的协调上的区别：在集中式路由机制下，由于所有业务的 路由均由中心控制节点来统一计算，各路由的计算顺序由中心控制节点来决定， 一方面可以使性能更优化，另一方面也可以避免在计算各业务的路由时的资源竞 争问题。而在分布式路由机制下，由于各路由计算过程由各业务的源宿节点分别 激活，“各自为政”，因此这一问题是不可避免的。 3 ) 计算速度上的区别：对于集中式路由机制而言，由于在计算路由时需要 知道全网的拓扑、资源、业务、路由信息，而保持这些信息的更新就需要节点数 据库和中心控制器之间频繁的通信，每更新一次网络数据库需要统计的信息很 多，难以保持快速的响应时间。另一方面，集中式计算要求在网络范围内为所有 业务模拟和计算各种可能的路由，在全网范围进行业务优化排序，资源的优化分 配，通路的优化选择均需要大量的时间。这两点决定了集中式路由机制下的计算 速度比较慢。对于分布式路由机制而言，由于无需知道全网所有信息，各节点的 邻接链路资源数据库的信息的更新可以在很短的时间内完成，分布式的搜索路 由，发现空闲资源的过程也远比集中式的方式节约时间，因此计算速度要比集中 式方法要快的多。 4 ) 容量利用效率上的区别：从上面的分析我们可以看出，分布式路由计算 的核心思路就是“利用局部信息，以最快的速度为业务需求找到一条可用路由”， 而集中式路由计算的核心思路就是“综合考虑全局信息，在资源利用情况、业务 路由情况、拓扑连接信息等条件的限制下，得出一个适合各业务的路由的优化的 整体方案”。因此，在相同的网络拓扑、空闲容量、业务需求的条件下，集中式 的路由机制可以得到更优化的路由组合，各路由之间可以更充分的实现资源的共 享，高级别的业务更容易优先得到恢复资源，整体业务路由建立的成功率较高。 虽然分布式路由计算在不断发展中，也进行了一些改进，采用了一些方法来促进 业务路由问的资源共享，以提高整体的资源利用效率。但由于其算法是基于局部 2 r 北京邮l 乜人学2 0 1 0 届毕业设计( 论文) 网络信息这一“先天不足”，无法用可控和有效的方式接入网络空闲备用容量， 路由算法不具有可预测性，使得其容量利用效率仍比集中式要差。 5 ) 实现难度上的区别：综合比较集中式和分布式两种路由机制，它们在实 现上都各有相对困难的方面：对于集中式路由机制而言，在实现上的困难之处主 要是需要维持一个完整、一致和准确的庞大网络数据库，随着网络规模的扩大和 动态变化，其存储、响应时间、准确性和成本都是问题。而对于分稚式路由机制 来说，它需要解决如何在提高路由计算速度的基础上解决路由计算时的资源竞 争，降低网络阻塞，合理配置网络资源，提高资源利用效率。 国际电信联盟( i t u t ) 在g 7 7 1 5 协议中对在a s o n 多层多域网络中建立 交换连接( s c ) 和软永久连接( s p c ) 选路的功能结构和要求早已做了描述，提 出了a s o n 网络的路由体系结构。a s o n 路由体系结构支持g 8 0 8 0 协议定义的 不同的路由方式：层次路由( h i e r a r c h i c a lr o u t i n g ) 、源路由( s o u r c er o u t i n g ) 和逐 跳路由( s t e p b y s t e pr o u t i n g ) 。不同的模式导致了节点之间控制功能模块的不同 分布和连接控制器之间不同的关系。 1 ) 层次路由模式：在a s o n 网络中，从水平方向来说，一般可划分成不同 二 的路由域，每个路由域又可分为不同的子网。而子网之间可以相互嵌套，一个大 的子网( 上层子网) 内部可包含若干小的子网( 下层子网) ，形成层次的结构。 每个子网都知道本身的拓扑结构并能进行动态连接控制，但对层次结构中的上层 _ 或者下层子网的拓扑结构不了解。 2 ) 源路由模式：对源路由模式而言，它与层次路由有很多相似之处。但在 源路由模式中，连接过程是通过分布的节点中的c c 和r c 分段联合完成的。在 嚣 源路由模式中，从源节点开始连接每所经过的一个路由域，则其入口节点( 第一 个节点) 要负责本路由域中的路由选择，并负责判断连接所需要进入的下一个路 由域的入口节点，这样逐个路由域进行选路，直到最终到达目的节点所在的路由 域。 3 ) 逐跳路由模式：逐跳路由模式同源路由模式大致相同，所不同之处在于： 在逐跳路由方式下，路由的选择是以节点为单位逐跳选择的，与m 网中数据包 的转发方式类似，而源路由模式是以经过的路由域为单位逐段选择路由的。 有关下一代智能光网络演进的主要研究方向还是在多层多域的多级分布式 实现上，所以我们主要基于其中的层次路由模式来进行a s o n 层域划分和路出 问题的分析和研究。 1 3 题目的意义 如今，路由型网络逐渐成为下一代网络的主流，其代表是各类基于i p 的网 北京邮 乜人学2 0 1 0 届毕业设汁( 论义) 络，例如i n t e r n e t 、移动核心网等等。路由型网络的核心技术就是路由技术。 路由技术通常分为几个必要的组成部分：寻址、路由信息交换、路由选择。 寻址的意义是将网络中每个节点通过一个全网唯一的地址标示；路由信息交换是 指在各个路由单元之间通过某种机制交换拓扑信息，使每个路由单元能够获悉全 网拓扑；而路由选择则是当业务到达时，根据业务源点和目的点的地址标示，结 合路由信息交换所得到的拓扑，计算出业务从源点到目的点的到达路径，并将业 务数据在路径上的每个节点进行转发。路由选择目前大多数采用表驱动路由技 术，即每个路由单元维护一张一段时间内不变的路由表，业务到来时查询路由表 以确定路由。 寻址的代表技术是i p 地址技术，路由信息交换的代表技术是以r i p 路由协 议为代表的距离矢量路由泛洪技术和以o s p f 为代表的链路状态路由泛洪技术， 而路由选择的代表技术是c i s c o 的e i g r p 路由选择技术。 光网络过去是交换型网络，但是随着a s o n 将控制平面引入光网络，光网 络开始向路由型网络转化。 随着时间的发展，非层域路由型网络( 或称为扁平网络) 的规模逐渐变大， 网络的路由模块的负担也越来越大。如图i - i 所示，网络原本有4 个节点a 、b 、 c 、d ，路由表条目有6 条，当网络新增一个节点e 时，为了维持路由表完整， 路由表需要增加4 个条目。 a b ( b a ) b c ( c 功 c d ( d c ) d a ( a d ) b d ( d b ) a c ( c a ) e a ( a d e b ( b d e c ( c 日 e d ( d d 一图i - i 拓扑规族变大对路由的影响 而如图1 2 所示，网络节点数目为n 时，路由表条目数为c ：。当网络新增 一个节点时，为了维持路由表完整，路由表需要增加n 个条目。 由此可见，随着网络规模的增大，路由表条目的增加几乎是指数级的。由路 由选择的概念可以得知，路由选择的第一步就是通过源节点和目的节点在路由表 中查找对应条目，根据计算机理论，n 长的路由表查询时问最短为o ( 1 0 9 n ) ，也 就是说，路由表越长，查询时间也越长。而由路由信息交换的概念得知，路由单 4 北京邮i 【1 人学2 0 1 0 届毕业设计( 论文) 元之间通过协议过程交换各自知悉的网络拓扑信息，然后根据所有邻居的路由信 息计算全网拓扑和路由。拿r i p 路由协议举例，r i p 路由信息交换的内容是各路 由单元自己的路由表，每个路由单元通过知悉自己邻居持有的路由表“根据谣言 进行路由计算”。也就是说，网络规模的增大，路有表条目的增长，也使得需要 泛洪的信息增多，泛洪因此需要占用更多网络带宽，也需要更长时间才能收敛。 曰 嚣 i ： 图1 - 2 拓扑规模变大对路由的影响 为了解决这一矛盾，将网络分层分域，层域之间采用分布式路由，能够大大 减少每个域内路由模块的负担。每个域的路由单元仅维护自己域内的拓扑信息和 路由信息，因而减小了路由单元的负担，同时由于每层的泛洪只在域内进行，因 此任意一个节点的故障就不会引起整个网络的泛洪，而是只引起其域内的泛洪。 但是由此带来的代价是，对于每条业务而言，层域路由模块算出的路由比集 中式路由模块算出的路由更容易阻塞( 也就是更不容易为路由成功分配波长资 源) 。这是由于上层的路由单元被下层路由单元屏蔽了底层拓扑信息导致的，后 面会详细讨论这一问题。 经研究发现，采用同种路由协议和算法的网络，不同分域方案最终造成的网 络路由性能是不一样的，而找到最优的分域方案，为未来网络的建设和升级提供 理论依据，就成为一个非常重要而且有意义的课题。 对于一个已经划分好层域的网络来说，不同的路由算法所造成的路由性能是 不一样的。最短跳路由算法也许能够使得每条业务的路由最短，但是却使得某些 链路，尤其是域问链路尤为拥堵，造成了为路由分配波长的成功率不高。因此， 综合利用各种拓扑信息提出新的层域路由算法，也是一个非常有吸引力的课题。 1 4 本论文主要内容 文章的第二章主要介绍多层多域光网络的结构和多层多域路由协议的内容， 5 北京邮电大学2 0 1 0 届毕业设计( 论义) 这一部分是后面所有研究的基础。 第三章介绍了我们对层域光网络路由性能的研究。首先，就路由协议的实现 做了详细介绍，这也是我们进行数学分析和仿真逻辑设计的必要前提；然后，我 们将传统扁平光网络中常见的路由技术改进后运用于层域光网络，研究其代价 性能增益。基于这种研究，我们提出了一种新型的层域光网络路由算法，这种算 法在域内路由部分采用固定路由，在域问路由部分采用固定备选路由，因而相对 于全网固定备选路由，节省了大量路由存储开销。而且这种算法不需要根据网络 的实时运行状态进行路由优选，这样就节省了维护动态链路状态的信令开销。我 们详细介绍了证明这种算法性能的数学计算，并提供了仿真数据。 第四章，我们介绍了网络分层分域结构对路由的影响。我们将这个问题分解 三个子问题：求解网络某一时刻正在运行的域内业务、域问业务数目及其概率； 网络在运行一定数量的域内业务、域间业务情况下，阻塞率如何；网络域内业务、 域间业务静态比率和分层分域结构的关系。这三个问题将网络的层域划分这种静 态属性和网络的路由阻塞率这种动态属性结合起来。这三个问题，每个问题组成 一小节，在每节中我们详细介绍了这三个子问题的数学分析求解过程。最后，我 们将数学分析的结论用仿真验证。 第五章，我们介绍了仿真平台的使用界面与实际开发细节，以供后续研究者 参考。 。 2 多层多域光网络的结构和路由协议 2 1a s o n 的多层多域结构 作为电信标准化组织的国际电信联盟( i t u t ) 将自动交换光网络 ( a s o n a s t n ) 定位为全球性统一的传送网，预计将来会有数千台的交换机和 数百万台的终端节点接入到这个网络中来。对于这样一个规模巨大的网络，如果 将所有的网络设备放在单一路由域中来管理，将会对路由以及连接管理等带来诸 多问题，如：单个节点需要维护过于庞大的路由表；路由协议拓扑信息的分发过 - 于频繁，给信令网的带宽，信令的处理带来严重的负担；网络拓扑收敛速度受到 限制，影响呼n q 连接的建立以及保护恢复的速度；基于g m p l s 的多颗粒度交 、 换也要求多层路由的支持。因此分层的网络路由体系成为a s o n 的必然选择。 为适应a s o n 路由体系的发展要求，u tg 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 0 6 与o i f 2 0 0 2 2 3 0 8 等则给出了a s o n 分层路由的一种 实现思想f 3 1 。 6 广 北京邮i 乜人学2 0 1 0 届毕业设计( 论文) 为了实现按照地理位置、运营商的策略等来提供路由服务等目的，网络可以 分成不同的路由域( r a ) 。路由域由子网，连接子网的链路以及这些链路的端点 ( s n p p ) 组成，可递归分割。显然，最小路由域包含两个子网及一条链路。 如图2 1 所示。路由域a 可分割为路由域b ，c ，d ，e 和f ，它们之间通过 s n p p ( 如图所示的圆点) 链路连接；这些低层的路由域可递归地被分割成层次 级别更低的路由域；如e 被分割为路由域g 与h 。分割时应保证同一层的路由 域互相不重叠。 图2 1 路由域层次与s n p p 链路关系 罗 在域的内部，下层路由域的内部结构对上层来说是不可见的，如域a 看到 的拓扑就是图2 1 中的b ，c ，d ，e ，f 及相关的s n p p 链路；域e 看到的拓扑 是g ，h 及相关的s n p p 链路；而在域的外部，如域a 的外部，只能看见路由域 b ，d 与f 最外面的s n p p 链路，而看不到域a 的内部。 在分层路由的最底层，子网点( s n p ) 被唯一地指配给一条s n p p 链路。下 层边界的s n p p 链路集完全包含在上层的一条s n p p 链路中。上层一条s n p p 链 路集可包含下层多条s n p p 链路。每一层的s n p p 链路只与一个路由域关联。某 一层的s n p p 链路，如果同时满足如下两个条件：不属于上层的边界，属于下层 的边界，则与该s n p p 链路相关联的点( 如路由域e ) 就产生一个s n p p 链路层 次。 图2 2 中域的分层采用了包含策略，这时下层路由域完全包含在相关的上层 路由域中，因此上层路由域的边界是其下一层路由域及其s n p p 链路的子集。 路由域分层后，要实现路由功能，每个路由域必须与一个路由执行器( r p ) 相关联。通过路由控制器( r c ) 之间分布式的联盟方式来完成路由服务。对等 ( r c ) 之问交换路由信息并通过对路由信息库的操作答复远端r c 的查询，r c 具有路由业务接口，以提供跨域的路由业务。为实现g 8 0 8 0 所定义的三种路由 方式，r c 之间的联盟方式有两种：联合联盟方式与合作联盟方式。 r c 以路由控制域( r c d ) 的形式实现其功能。对内呈现分布式的特点，由 一组分布式的路由实体组成；对外呈现抽象的特点，隐藏了其内部的分发细节。 7 北京邮i 乜人学2 0 1 0 届毕业设计( 论文) 只提供与r c 特征相同的分发接口。每个r c d 内部可以使用不同的方式来表示 路由信息，但是r c d 之间交换的路由信息，其语义必须与r c 分发接口之间所 交换的一致。 图2 3 给出了r a ，r p ，r c 和r c d 之f b j 的关系。 分层的r p 通过r c 栈来实现，栈的级别对应着路由的层次。图2 3 给出了 利用r c 栈来实现r p 的一种思想，虚框表示了r c 的位置，圆点表示子网点集 s n p p 。 镣丹磁 旗一l 绥 。一一一一一一一一一一- 一一- 图2 2 r a 、r p 、r c 以及r c d 之间的关系 | 鬟欺i 静缆 竹钳疑i l 锋址 3 苍；一| | i 一 ；一 il 一 卜一一j 。- 。- - - _ | 。_ _ _ 三堕时，s 5 0 。 m + 1 ，、第o 层域收到的连接请求中域间业务所占部分域间业务种类 r 1 第0 层域收到的连接请求中域内业务所占部分域内业务种类 不等式后半部分即【1 】的结论，域间业务的路由到第一层时，分为一跳与多 1 6 北京邮i 【1 人学2 0 1 0 届毕业设计( 论文) 跳两种。若是多跳，由于存在转接域、源域、宿域会转化为3 个以上0 层域转接 请求；若是一跳，除连接源宿域的网关链路的两个邻接节点恰好为业务源宿外， 翌 均会转化为1 个以上o 层域。( 这种情况占，概率很低) 。由于域间业务经过 c 。磊 路由组合与实例化后会转化成多个第0 层域连接请求，故得证不等式前半部分。 以上两式说明：层域的划分将网络的业务分为域问业务和域内业务。域问业 务总要占用域问链路，域内链路则不占用域问链路。而只要最底层域多于两个， 域间链路无论是种类还是动态到达率均高于域内链路。域间链路的拥堵正是由于 此导致。 域问链路的拥堵和域间业务的高到达率，一起导致阻塞率居高不下。 针对这一点，我们设计了一些固定备选路由( f i x e da l t e r n a t i v er o u t i n g ) 算 法来规避域间链路的拥堵。 3 3 多层多域环境下固定备选路由( f a r ) 的改进 固定备选路由算法主要包括两部分内容：静态路由表冗余和动态路由选择。 静态路由表冗余是指在进行路由计算时，为每个路由项( 源宿节点对) 计算若干 条路由作为路由备选集；动态路由选择是指业务动态到达后，采用不同的策略在 路由备选集中进行优选，最后挑选出一个在规定策略下最优的路由进行资源预 留。 我们选择在动态路由选择过程上寻找突破口。根据传统的集中式r w a 理论， 耗费一倍的路由表存储空间，为每条路由配备一条没有公共链路的备选路由，动 态路由选择时，考察两条路由的资源状态，使用各种策略进行优选，最终胜出的 那条路由进行资源分配，这种做法能够显著提高路由的性能。将这种理论借鉴到 层域路由中，我们提出以下路由策略： 1 ) 动态层间均衡路由算法( d y n a m i cm u l t i l a y e rb a l a n c i n gr o u t i n g a l g o r i t h m ，d m l b ) 区别于最短跳策略，d m l b 借鉴最小负载( l l ) 的思想，将抽象路由的容 量瓶颈作为评价参数。当某个业务连接请求r 2 p ，d ，z j 到来时，其中s ，d n ， 表示该请求对应的源宿节点，x 表示该业务的带宽请求，本文我们主要针对一个 波长粒度业务，即x = l 。在同层选路过程中，对于步骤( 2 ) 预计算出来的k 条 路径集合p 作为备选路由集，我们将它内部元素的权重以便从中确定一条最优的 端到端路由( 这里的路由包含抽象的下层逻辑节点信息) 。假设网络当前处于任 意状态l f ，当前到达的连接请求为，。，算法将根据网络当前状态t , ，切合上层乃 至更高层的逻辑节点依据请求，。下发的细化指令，从本路由域的路由表t 中挑 1 7 北京邮电人学2 0 1 0 届毕业设计( 论文) 选出若干条抽象路由信息组成备选路由集p ，并从中选出一条最优路由p 。用 口缈，) 表示缈状态下链路l 在波长平面t o 上的可用通路数( 即可用光纤数) ， d m l b 将根据( 1 ) 式确定最优通路p ： p 2 学 磊呀口呲h 式( 3 1 ) 即取通路集合中带宽瓶颈( b o t t l e n e c k ) 最大的那条通路为最优通路，参与 路由细化。 - 2 ) 最优网关链路动态层f b j 均衡路由算法( d y n a m i cm u l t i l a y e rr o u t i n g a l g o r i t h mb a s e d o no p t i m i z e dg a t e w a y s ，d m l o g ) 、 d m l b 预计算备选路由进行层间拓扑抽象时，采用星型聚合方法。此时， 本域所有的进出域网桥链路相当于聚合到了同一端点，星型聚合使得接下来的路 由计算对网桥链路的选择可以归纳为一种首次命中( f i r s t f i t ，f f ) 方式，这时对 于上层逻辑节点来说，下层域的域内侧信息被完全屏蔽，比较计算只限于域问链 路，所以对于下层每个聚合为逻辑节点的路由域来说，所有的进出域网关缺乏一 个优选验证的过程。如图3 3 所示，n a 和n b 分别是域a 和b 的网关节点， z ，it - ，z ：，s z 册 表示与节点n a 相邻的域内侧链路集合， f iz ：，z ：，t ”( 表示与 n b 相邻的域内侧链路集合。当链路l 上的可用波长资源很丰富但与其相邻的域 内侧链路无可用波长资源时，如果上层选路结果包含此域间链路，则最终的路由 将不可用。鉴于此，我们在d m l b 的基础上提出了一种由网关节点结合域内侧 优选的改进策略。 b 域 图3 - 3d m l o g 算法场景示意图 在计算抽象路由的容量瓶颈时，d m l b 的评价链路集合为 r ，i -1 1 厶il l ，l 2 , l 3 l n ，其中le p 。在d m l o g 中，我