（通信与信息系统专业论文）自动交换光网络（ason）中路由与波长分配算法（rwa）问题的研究及仿真.pdf

声明 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：擅丝趣 日期：坦 1 - ) 2 节点。 这种方法虽然简单，但却需要较多的波长资源。在动态流量情况 下，如果出现波长冲突，则会导致严重的流阻塞。因为没有替代 路由，所以在这种算法工作下，网络不具备链路故障恢复能力。 图3 2l 直l 定路由选择策略 ( 2 ) 固定的备用路由选路策略( f a r ：f i x e da l t e r n a t e dr o u t i n g ) ：网 络中每个节点维护一张路由表，里面是它到其他节点的一系列路 由，其中包括作为工作光通道的最短路由和作为备用光通道的路 由。备用路由一般不跨越工作路由的链路段，即它们在物理上是 分离的，所以这种机制又叫做链路分离或边分离机制。当节点收 到连接请求时，按照工作路由建立光通路，若工作路由已被占用 或失效，则在备用路由中选择次短路由。如图3 - 3 所示，节点0 3 7 到节点2 的备用路由依次经过0 专5 专4 专2 节点。这种选路法的优 点是简单且具有链路故障恢复机制，与固定选路法相比，流量被 阻塞的概率显著减小。 图3 3 州定的备川路由选路策略f a r ( 3 )自适应备用路由选路策略( a r ：a d a p t i r er o u t i n g ) ：从性能上看， a r 是一种较好的方案。f r 和f a r 方案都不能考虑到网络的当前状 态，而a r 则可以根据当前的网络状态动态地进行路由选择。a r 具 体可以细分为两种，一种是受限a r ，另一种是非受限a r 。受限a r 与f a r 相似，同样是预先为每一对源宿节点建立备用路由集，集 合中的路由排列是无序的，当需要建立连接时，根据当前的网络 状态选择最合适的一条路由，这种方案的代表算法有l l r l ，f p l c 等；而非受限a r 则不事先建立备选路由集，而是在请求到达时完 全动态地计算出一条连接源宿节点的路由。这种方案的代表算法 有p a c k ，s p r e a d 等。 上述3 种选路方法中，固定路由选路法选取路由时间最短，因为它不考 虑网络资源占用状态且可以离线预先计算，所以所花费时间代价最小。缺点 是无法随网络业务的动态变换自适应调整节点对间的路由，而进行流量工程 控制，因此会导致网络性能劣化，增加网络阻塞率。 自适应的备用路由选路策略性能最优，因为它在分配路由时考虑网络资 源的占用状态。当业务到达时，依据网络目前资源占用状态，充分比较多条 备用路由上的波长分配策略，得到该业务的最优分配方案。它在三种分配方 案种效果最好，但计算需要时间最长。 固定的备用路由选路策略( f i x e da l t e r n a t e dr o u t i n g ) 介于前两种策略之 间，它部分考虑了网络的状态，性能介于前两者之间，三种路由策略的性能 对比如下表3 1 所示： 表3 1 三种路由策略性能对比 固定路由选路策略 l 固定备用路由选路策略l 自适应备用路e h 选路策略 f rif a rl a r 业务类型均匀分布均匀分布或动态分布动态分布 选路路由时间 最小( 离线预先计算) 中等 人( 实时计算) 代价 考虑当前网络 否是 是 状态 网络阻塞率人中等小 流量控制功能否能能 链路故障恢复否能能 由于将路由问题和波长分配问题分开，减小了r w a 算法的时间复杂度， 同时路由计算通常可以离线计算，即在网络业务到达前路由计算完成，当业 务到达时直接利用计算的路由结果，所以通常需要网络建立相关的路由信息 数据库，保存路由计算信息。备用路由的数目同网络的连接度有关。 3 , 3 波长分配算法 本文主要关注动态波长分配算法7 3 舳，动态波长分配的目标不是将波长需 求最小化，而是假定波长总数不变，使得建立的连接最多和对流量的阻塞概率最 小。 当源宿节点有多条波长可用时，波长分配算法则从中选择一条最合适的波长 建立光通道。目前常用波长分配算法可分为三类：基于局部信息的波长分配算法、 基于全局资源信息的波长分配算法和基于全局通路信息的波长分配算法。 ( 1 ) 基于局部信息的波长分配算法： 该类算法仅考虑待分配业务路由上的资源使用信息，是最简单的一种波长分 配方案，常见的算法有： 随机分配算法( r a ：r a n d o ma s s i g n m e n t ) 随机分配算法思路为：首先遍历所有波长，确定在选定路由上的可用波长 集合，接着从可用波长集合中随机等概的选取一波长。随机分配算法不考虑 当前的网络资源( 各链路上的各波长) 的占用情况，所以时间复杂度低。由于 需要遍历所有波长以确定可用波长集合，其时间复杂，可简单的用0 ( w ) 表示， 其中w 为光纤中的复用波长数。但本算法对网络性能的改善不明显。 首次命中算法( f f ：f i r s t f i t ) 首次命中算法在网络的规划阶段，对所有的波长都统一编号，该编号可以 按波长的大d , l l 顷序编号，也可以随机编号，一般按波长的大d , j l 顶序编号，接 着选用可用波长集( 即还有剩余信道的波长的集合) 中编号最小的波长来建立 光路。同随机分配算法一样，首次命中算法也不考虑当前的网络状态，由于 3 9 是按顺序检查波长集合，将发现的第一个空闲波长分配给呼叫，其时问复杂 度为o ( w ) 。 ( 2 ) 基于全局资源信息的波长分配算法 该类算法对全网所有波长资源使用情况进行分析，根据分析结果选取最适合 全网的一个可用波长。常见的算法有最小使用( l u ：l e a s tu s e d ) 和最大使用算 法( m u ：m o s tu s e d ) 。 最小使用算法( l u ：l e a s tu s e d ) 最小使用算法根据网络目前的状态统计出各波长的使用情况，将波长按 波长使用率升序排列，在选定路由上按序检查波长，直到找到一可用波长。 由于每次都是选择使用率最低的可用波长，因此最小使用算法趋向于使各波 长的使用率平均。但是也正是由于这种趋向，也使业务在建立波长通道时 更容易被阻塞。最小使用算法需要利用目前的网络资源( 各链路上的各波 长) 的占用情况，其时间复杂度要高于首次命中与随机分配，其时间复杂度 为o ( w l f ) 。 最大使用算法( m u ，m o s tu s e d ) 最大使用算法与最小使用算法一样，也根据网络目前的状态统计出各波长 的使用情况，在选用波长时则是选择使用率最高的波长。最大使用算法需要 利用目前的网络资源( 各链路上的各波长) 的占用情况，其时间复杂度与最小 使用算法一样为o ( w l f ) 。 ( 3 ) 基于全局通路信息的波长分配算法 在为业务需求分配波长时，必须考虑原有的业务波长通道的建立情况，根据 对其的影响来选择一个可用波长。本算法包括最大总和算法( m s ：m a xs u m ) 和最小影响算法( l i ：l e a s ti n f l u e n c e ) 。 最大总和( m s ：m a xs u m ) m s 算法是指选择波长之后，保证全网其它通路的剩余可用信道数总和最 大；其基本思路是对所有波长，依次计算分配该波长入后，网络中的其它所 有通道在入上降低的可用信道数的总和，选定降低总和最小的波长。m a x s u m 算法在分配波长时考虑了网络的状态，故而能大大提高算法的性能。同样是 利用全网的波长占用信息，在选择空闲波长时，全局最大总和算法的目的是 保证分配该波长后全网所有通路的的可用信道数最大。在具体计算时，待分 配的业务本身除外( 因为无论分配哪个空闲波长，对本身所产生的影响都是相 同的，都只会减少一个信道) ，计算该业务分配某波长后网络中其他业务所剩 余的可用信道数的总和，取其中最大的一个值所对应的那个波长。 r a i n 删p i u o t k - ( t , a ) ，乓( a 五) ) ) 最小影响算法( l i ：l e a s ti n f l u e n c e ) 最小影响算法是指选择波长之后，对全网其它通路影响最小。l i 算法为 新业务在选定路由上分配波长时，是选择对全网影响最小的波长。其过程为 首先计算网络中与新业务相关的业务在新业务选定路由上各波长遭遇的瓶 颈链路数，接着选择具有最小瓶颈链路总数的波长。l i 算法也是考虑网络状 态的一种算法，思路与m a x s u m 算法较为类似，算法计算的都是分配某波长 后，对其他工作业务的影响的绝对值。 该算法公式表示如下： m i l l 掀i 一抛，名) ，只( p ，五) ) 婵俄，- k 懿p h “矿l 3 4 仿真及其结果分析 3 4 1 仿真环境 仿真环境【2 7 】【3 0 1 【3 1 1 使用了基于n s 2 扩展的o w n s ( o p t i c a lw d m n e t w o r k s i m u l a t i o n ) 软件，其中o w n s 是可升级和可扩展的仿真环境，是由华盛顿州 立大学的电子与计算机科学学院的“黎明网络研究实验室”( d a w n n e t w o r k i n gr e s e a r c hl a b ) 在n s 2 基础上开发的。o w n s 仿真工具的目标是 将w d m 光网络重要特性集成在该软件中，如光交换节点、多波长链路、虚 拟拓扑和交换策略及路由算法，从而实现对w d m 光网络路由协议及其它算 法的研究b 4 1 。 n s ( n e t w o r ks i m u l a t o r ) 是由u cb e r k e l e y 开发的事件驱动的网络性能模 拟软件，可用于模拟不同的i p 网络，它可实现多种网络协议、路由器队列管 理机制和路由算法，如t c p 、u d p 、f t p 、t e l n e t 等协议，d r o pt a i l 、r e d 、 c b q 等路由队列管理机制，d i j k s t r a 等路由算法。鉴于o w n s 对n s 2 的兼容 性，本仿真环境采用l i n u x 7 3 + n s 2 1 b 6 + o w n s 。 n s 主要由t c l 、t k 、o t c l 、t c l c l 、t c l d e b u g ，n a m ，x g r a p h ，g t i t m ，s g b ， c w e b ，z l i b 等功能模块构成，如图3 4 所示。 ( 1 ) t c ht c l 提供了一个强有力的平台，可以生成面向多种平台的应用 程序、协议、驱动程序等等。它与t k ( t o o l k i t ) 协作，可生成g u i 应用程序，可在p c 、u n i x 和m a c i n t o s h 上运行。t e l 还可用来完 成与网页相关的任务，或是为应用程序提供强有力的命令语言。 ( 2 ) t k ：与t e l 协调工作的图形工具包。 4 1 ( 3 ) o t c l ：m i to b j e c tt c l 的简称，是t c l t k 面向对象编程的扩展。 ( 4 ) t c l c l ：此目录下含t c l c + + 的接口，v i c 、v a t 、n s 、r t p 、p l a y 和n a m 都会用到。 ( 5 ) n s ：n s 的主体代码，内含一个节点移动产生器、两个传输事件产 生器。 ( 6 ) n a m ：即u c b l b n l n e t w o r k a n i m a t o r ，它与n s 协同工作，动态 表现n s 仿真过程。 图3 4 n s 功能模块不意图 3 4 1 1o w n s 简介 在w d m 网络研究中，仿真已经成为不可缺少的手段。由于各个研究组织都 使用自己的仿真假设条件和仿真平台，缺少一个开放的公共的仿真环境来对以往 的协议模块进行重用，并对所已得到的结果进行对比和交流，随着研究的深入和 扩展，这种仿真平台的差异性导致的问题会越来越突出，因此有必要开发这样一 个开放的统一性的环境，来服务于各个研究组织和团体。 o w n s 3 4 1 利用已存在的协议和仿真组件、便于添加新协议的开放性框架将 w d m 光网络的重要特性集中于其中，能迅速开发w d m 技术为相关的研究者们 带来巨大的便利。 如图3 5 所示，o w n s 的体系结构由物理层和逻辑层组成，物理层由光交换 节点和多波长链路组成，分组的传输是在物理层上实现的。逻辑层由路由模块和 波长分配模块组成，二者合作生成和维护虚拟拓扑。多波长链路的多信道组织在 逻辑层集中维护，波长分配模块与路由模块协同工作来计算波长分配，建立光路 并构建虚拟拓扑。根据上述波长分配的结果，光节点转发到来的流量通过多波长 链路到相应的下一跳。 在o w n s 中，使用固定备用路由策略f a r 作为默认路由协议，使用首次命 中算法作为默认波长分配算法，其它的r w a 算法目前没有实现。另外，为适应 4 2 w d m 光网络的电路交换环境，o w n s 对n s 中原有的流量生成器进行改造，目 i 仃，o w n s 开发出三种会话流量生成器：应用层会话流量固定比特速率( a p p l i c a t i o n s e s s i o n t r a f f i c c b r ) 、应用层会话流量肘旨数分柿( a p p l i c a t i o n s e s s i o n 集中式多信道结构 图回 3 5o w n s 体系结构 t r a f f i c e x p o n e n t i a l ) 和应用层会话流量泊松分布( a p p l i c a t i o n s e s s i o n t r a f f i c p a r e t o ) ；流量生成器包括两个参量，即会话平均到达速率( m s a r ) 和会话平 均持续时间( m s h t 一) ，会话流量到达用泊松分布的模型描述，并用会话平均到达 速率( m s a r - ) 表示；会话持续时间用指数分布模型描述，用会话平均持续时间 ( m s h t 一) 表示。对每个会话，分组内部到达时间分布可用固定比特速率( c b r ) 、 指数分布和p a r e t o 分布描述。 图3 6 描述了w d m 光网络仿真模型的组成以及各个模块的相互作用。其 中，光交换节点、多波长链路、路由部件以及波长分配部分由w d m n o d e 、 d u p l e x - f i b e r l i n k 、r o u t e l o g i c w a v e l e n g t h 和w a s s i g n l o g i c 对象分别实现。用于 产生数据包的业务源由传输层的a g e n t w d m 和应用层的a p p l i c a t i o i n s e s s i o n t r a f f i c 组成。波长分配部分与路由部分协同工作，计算波长分配，建立光路以及 构建虚拓，根据上面的计算结果，光节点通过多波长链路将输入业务转发到相应 的下一跳节点。 4 3 各个组成模块的主要功能以及设计实现方法如下所述： 图3 - 6o w n s 部件组成汞1 交互 1 光交换节点 w d m n o d e 对象派生于n s 的n o d e 对象，同时它代表一个光交换节点 的实例，由端口分类器和光路分类器组成。端口分类器解复用和转发数据 包到达各自相应的链路。光路分类器与w a s s i g n l o g i c 对象相互作用，为输 入会话业务建立光链路，更新目前虚拓扑状态；源节点的光分路器将自己产 生的数据包向w a s s i g n l o g i c 发出链路请求。另外，业务经过节点的光分路 器仅向w a s s i g n l o g i c 询问转发信息；光分路器也同时仿真波长转换的延时， 光分路器的对象由c l a s s i f i e r a d d r l i g h t p a t h 类对象实现。 2 多波长链路 扩展n s 中的双工链路形成多波长的双工链路d u p l e x f i b e r l i n k ，它与 传统链路的区别在于：多波长链路没有队列组件，这是由光波通信特点所决 定的；所有的多信道结构、波长利用率和拓扑信息由w a s s i g n l o g i c 集中维 护。 3 波长分配部分 波长分配组件负责计算波长分配，建立链路和拓扑结构。w a s s i g n l o g i c 的对象用于存储波长分配算法的必备信息，负责完成端到端的波长通道连接 建立。波长分配机制默认为首次命中波长分配算法，首次命中波长分配算法 是在连接建立过程中，源节点将选取的第一个空闲波长作为请求波长，如果 中途节点的同一波长被占用，就需要在可变换的波长范围内寻找本地的第一 个空闲波长执行波长变换；如果中途节点没有波长变换能力或可变换波长都 被占用，就会出现连接请求拒绝。图3 7 是用首次命中算法实现波长路由的 流程图。 4 路由部分 路由部分计算需要建立光路的路由，使用某种特定的路由算法。传统网 络与w d m 网络路由算法相似，路由部分作为r o u t e l o g i c w a v e l e n g t h 类的 对象，是由n s 的r o u t e l o g i c 类派生而来的：仿真器通过 r o u t e l o g i c w a v e l e n g t h 集中维护网络路由信息，此处采用固定最短路由算法 作为默认路由。r o u t e l o g i c w a v e l e n g t h 为w a s s i g n l o g i c 提供路由信息来引 导输入业务。新的路由算法可通过派生r o u t e l o g i c w a v e l e n g t h 类来产生。 3 4 1 2o w n s 版本的扩展 由于o w n s 软件开发出的路由协议只有f a r ，波长分配算法只有f i r s t f i t ， 其它的r w a 算法目前没有实现，无法进行r w a 算法之间的性能比较，故需要 自行开发相应的路由算法和波长分配算法。目前，重新扩展的波长算法有随机分 配算法，考虑到n s 2 中有自带的路由协议算法，故未进行其他路由协议的扩展。 此处扩展的波长分配算法为随机分配算法r a n d o m a s s i g n m e n t ，扩展的波长 分配算法的c + + 源文件为w d m - w a s s i g n r a c c ，是从w a s s i g n l o g i c 类继承产生 的。扩展的t c l 脚本文件为n s w d m w a s s i g n r a t c l 。首先，将上述两文件复制到 目录h o m e y y c n s a l l i n o n e 2 1 b 6 n s 2 1 b 6 目录下，并修改n s a l l i n o n e 2 1 b 6 n s 2 1 b 6 目录下的m a k e f i l e i n 文件，在其中的”o b jc c = f t 加上： o b j c c = 0 w n s n s 一2 c l a s s i f i e r a d d r 一1i g h t p a t h ，0 | 0 w n s n s 一2 w d m - r o u t e o o w n s n s 一2 s e s s i o n t r a f g e n 。0l o w n s n s 一2 c b rs e s s i o nt r a f f i c 0 | 0 w n s n s 一2 e x p o os e s si o n 。o | o w n s n s 一2 w d m - w a s s i g n o | o w n s n s 一2 f i b e r d e l a y o | o w n s n s 一2 s e s si o n t r a f - r c v r 0 | o w n s n s 一2 w d m - a g e n t ，0 | 0 w l v s n s - 2 w d i n - w a s s i g n - r a 0 + 一新加顼 4 5 图3 7 采用f i r s t f i t 算法实现波长路由的流程图 其次，更新l l o m e y y c n s a l l i n o n e 2 1 b 6 n s - 2 1 b 6 t c l l i b 中的i l s l i b t c l 文件， 在其中加上 s o u r c e e m u l a t e n s e m u l a t e t c l o w n ss c r i p t s o u r c c ( 1 砖n s t c l n s w d m l i n k t c l s o u r c e o 骶s t c l n s w d m - n o d e t c l s o u r c 8 帆s t c l n s w d m - r o u t e t c l s o u r c e j o 助v s t c i n s w d m w a s s i g n t c l s o u r c e 。o w s t c l n s w e m - s o u r c e t c l s o u r c e o g n s t c l n s w d m w a s s i g n - r a t c l 一赣力b 项 s o u r c e o 助v s t c j n s w d m d e f a u lt t c l e n do fo w n ss c r i p t s i m u l a t o ri n s t p r o ci n i ta r g s 最后，重新编译安装整个a s a l l i n o n e 2 1 6 ，运行h o m e y y c n s a l l i n o n e - 2 1 b 6 目录下的i n s t a l l 文件：i n s t a l l i n s t a l lr e c o r d t x t 即可。其中用到重定向“ ”到 文本文件i n s t a l lr e c o r d t x t 。 3 4 2 性能参数 各种r w a 算法性能依据参数不同，常用的有阻塞率、链路利用率、端到端 包时延、吞吐量等，本平台通过以下两个参数衡量算法的性能： 1 ) 阻塞率( b l o c k i n gp r o b a b i l i t y ) ：业务到达时为其建立光路时被拒绝的统计概 率。 2 ) 链路利用率( l i n ku t i l i z a t i o n ) ：链路带宽有效利用的百分率，即使用的链路 带宽与总带宽之比。 s i a ! l i f i o n 藓2 袖蝼”矧图画图 f i l ee d i t s e t t i n g sh e l p b i n b a c k u pi n s t a l1 _ 3 - i o r r o r t x tx g 叼散q2 1 c w e bi 惦t a l1 _ 4 一e r r o r t x ts 曲z li b _ 1 i 3 9 e 0 9 p a t c h t ：1 8 0 4 gt-it麓tclposixstrpath i n s t a ll _ e r r o r t x tt e l b o x r o o 垤l o c a l h o s tn s - a l1i n e _ 2 1 b 6 】op u d h o m e 魁c n s a lli n o n e - 2 1 b 6 r o o t 扈l o c a l h o s tn s a l l i n o n e - 2 1 b 6 】i n s a t l l i n s t a l i _ r e c o r d t x t b a s h ：i n s a t l1 ：n os u c hf il e r o o t l o c a l h e s tn s - a lli n o n e - 2 o k ，t h e9 b f l i pr 屯u t i n e ss e e m 【r 垤1 0 l h e s tn s - a l l i n o n e - 2 r o o t e l o c a l h o s tn s a l ii n o n e - 2 o f j 1 c 群瓤蚓扣 幽t o ：f 尜型! 竺兰! ! ：竺! ：竺)”o 河丌 1 b 6 】v ii 憾t a ll _ r e c o r d t x t l b 6 , d 露凰因 f i l ee d i t s e t t i n g sh e l p 9 0 9n s ：h 蛳嘴a lii n o n e - 2 1 b 6 n s - 2 1 b 6 n s 9 1 0o t c l ： h o m e y n s - a l1i n o 神1 b e o t c l - 1 o a 5 9 1 1t c l c l ：，h o m e g 啦n s a iii n o n e - 2 1 b g t c l c l - i 0 b 9 9 1 2t c l b 0 4 ： h o m e 阱，n p a ll i n o n e - 2 1 b 6 t o l b o x 9 1 3t k 8 0 4 ： h e m e ，毡s 女c n s a l l i n o n e - 2 i b 6 t k b o x 9 1 4h a m h o m e j g p j c n s - a lli n o n e - 2 i b 6 怕妒i o a 8 怕m 9 1 5x g r a p h ：h e 螂c 惦a lii n o n e - 2 1 l 5 x 9 r a p h - 1 2 1 9 1 69 t i t m ： h o m e y h c n s a lii n o n e - 2 1 b s i t m ，e d r i v e r ，s 9 b 2 a l t ，s 9 b 知s ，s 9 b 2 c n s ，s 9 b 2 h i e r n s 9 1 7i 9 1 8y o uc 拥d e l e t e ，h 邯哈g s l c n s a lii n o n e - 2 i b g t c l 8 0 4a n d 0 4i f 图3 8 加入o w n s 扩展部分后重新安装截图 4 7 3 4 3 仿真及其分析 仿真一：采用固定路由算法，f f 波长分配和r a 随机波长分配，对阻塞率【4 l 】仿 真。 仿真脚本主要参数设置如下： s e t v a l ( w v l e n _ a s s i g n ) f i r s t f i t 妖波长分配算法) # s e t v a l ( w v l e n _ a s s i g n )r a n d o m a s s i g n m e n t s e t v a l ( n o d e _ n u m ) 2 0 敢网络节点数) s e t v a l ( 1 i n k _ b w ) 8 m b s 撑( 链路带宽) s e t v a l ( 1 i n k _ w v l e n _ n u m ) 1 6 故每条链路的波长 通道数) s e t v a l ( 1 i n k _ d e l a y ) 1 0 m s 撑( 链路延迟) s e t v a l ( t r a f _ t y p e )e x p o n e n t i a l 敢源节点业务类型) s e t v a l ( t r a f _ e x p _ b u r s t _ t i m e ) o 7 撑( 业务突发时间) s e t v a l ( t r a f _ e x p _ i d l e _ t i m e ) 0 1 敢业务停发时间) s e t v a l ( t r a f _ h o l d i n g _ t i m e ) 1 0 0 敬业务接续时间) s e t v a l ( t r a f _ p k t _ s i z e ) 1 0 0 0 敢数据包尺寸) s e t v a l ( t r a f _ p k t _ r a t e ) 0 5 m b s 敢数据包到达速率) 丘b 帅sa f i _ 熵； 嗍- _ 一-卜 客l力潮1 2 1 1 r o l l 室 j 压 剑 i 由- _ l ：弘借口| 幅轴_ - p o ，鼬 一州i 嘲 图3 - 9n s f n e t l 6 节点网络拓扑 如图3 - 9 所示，选取1 6 节点的n s f n e t 网络作为仿真的拓扑，全部节点位 于同一路由域内，各节点没有波长转换能力，网络节点间为一条光纤连接，链路 带宽为8 m b s ，每光纤1 6 波，业务的到达满足到达率为入的泊松过程，且到达 每个节点概率相同，连接保持时间满足均值为l i t 的指数分布，故到达每个节点 的业务强度为入u ，单位为爱尔兰。业务问隔时问和保持时间都遵循指数分布。 仿真一采用的路由算法为固定路由算法，波长分配算法为首次命中和随机分配算 法，仿真给出了在网络负载变化的条件时，网络的阻塞率和链路利用率的变化情 况。 从图3 1 0 阻塞率曲线图可以看出，f f 波长分配算法总体性能要优于随机波 长分配算法性能，在低中度负载的业务强度下，性能更好；随着业务强度的增加， 二者的性能曲线相互靠近，且趋向一致，说明两种算法的的性能差异逐渐缩小， 这是由于业务增多时占用资源增加，导致可用空闲波长数越来越少，两种波长算 法可选择的波长数逐渐减少所致。 b l o c k i 怕p r o b 曲ii i t y 图3 1 0 使用固定路由算法的阻塞率 仿真二：采用固定路由算法和固定备用路由算法，f f 波长分配算法，对链路 利用率仿真，仿真脚本的主要参数设置如下： s e t v a l ( w v l c n _ r o u t i n g ) w d m s e s s i o n 敢固定备用路由算法) s e t v a l ( w v l e n _ a s s i g n ) f i r s t f i t 撑( 波长分配算法) s e t v a l ( w v l e n _ a s s i g n ) f i r s t f i t 敢波长分配算法) s e t v a l ( n o d e _ n u m ) 2 0 联网络节点数) s e t v a l ( 1 i n k _ b w ) 8 m b s 敢链路带宽) s e t v a l ( 1 i n k _ w v l e n _ n u m ) 3 2妖每条链路的波长通 道数) s e t v a l ( 1 i n k _ d e l a y ) l o m s 敢链路延迟) 4 9 s e t v a l ( t r a f _ t y p e )e x p o n e n t i a l舟( 源节点业务类型) s e t v a l ( t r a f _ e x p _ b u r s t _ t i m e ) o 7 撑( 业务突发时间) s e t v a l ( t r a f _ e x p i d l e _ t i m e ) o 1 敢业务停发时问) s e t v a l ( t r a f _ h o l d i n g _ t i m e ) 1 0 o 敢业务接续时i 可) s e t v a l ( t r a f _ _ p k t _ s i z e ) 1 0 0 0 嘶数据包尺寸) s e t v a l ( t r a f _ p k t _ r a t e ) 0 。5 m b s 敢数据包到达速率) 仍采用图3 - 9 的拓扑图，1 6 个节点位于同一路由域内，各节点没有波长 转换能力，网络节点间为一条光纤连接，每光纤3 2 波，链路带宽为8 m b s ， 业务的到达满足到达率为入的泊松( p o s s i o n ) 过程，且到达每个节点概率相 同，连接保持时间满足均值为1 p 的指数分布，故到达每个节点的业务强度 为入u ，单位为爱尔兰。业务间隔时间和保持时间都遵循指数分布。仿真二 采用的路由算法分别为固定路由算法和固定备用路由算法，波长分配算法为 f i r s t f i t ，仿真给出了在网络负载变化时，链路利用率的变化情况。 图3 - 1 1 使用固定路由算法和固定备用路由算法时的链路利用率 图3 1 1 所示，p a t h l 表示固定路由算法，p a t h 2 表示固定备用路由f a r 算法。由图可以看出，在低业务强度的情况下，固定路由算法和固定备用路 由算法的链路利用率相同，因为低业务强度可用的链路资源丰富，此时发生 阻塞的概率很低，f a r 算法基本只用主路由，没有启动备用路由，故此时 f a r 路由算法等同于固定路由算法。随着业务强度的增加，固定备用路由算 法的链路利用率逐渐超过固定路由算法的利用率，这是由于随着网络资源占 用增加，首选的主路由阻塞概率增加，故备用路由使用得更加频繁所致。 3 5 本章小结 本章首先介绍了w d m 光网络中r w a 问题，并对常用的r w a 算法进 行了理论上的性能分析；对o w n s 进行了扩展，在原有的基础上新添加了随 机波长分配算法，并利用新扩展的n s 2 + o w n s 仿真平台，设计网络拓扑、 网络流量，运行两种路由策略( 固定最短径路由算法和固定备用路由算法) 和两种波长分配算法( 首次命中算法和随机波长分配算法) ，分别对w d m 光网络的阻塞率和链路资源利用率进行了仿真，仿真结果表明，与理论分析 基本一致，此扩展后的仿真平台具有一定的有效性。同时也为下一章对f a r 算法的改进在仿真上作了支持。 第四章a s o n 中r w a 算法的研究及改进 本章主要分两部分，首先介绍了a s o n 中的路由与波长分配r w a 算法 的新特点，同时对w d m 光网络的r w a 算法进行了分析，对w d m 网络中 的一些路由和波长分配算法进行了改造与扩展，使之能适用于a s o n 网络； 其次，对固定备用路由算法( f a r ) 进行了改进，提出了与部分链路无关的 备用路由算法d p l p ，该算法在大连通度的m e s h 型网络中选路特性优于 f a r ，同时，该算法还对解决网络的生存性问题有一定的借鉴意义。 4 1a s o n 涉及的r w a 问题 4 1 1a s o n 的路由算法 相对于传统v c d m 光网络，a s o n 中的路由问题【4 】【1 2 】f 1 5 】【1 7 】有自己的新要 求和特点。由于a s o n 采用了分布式控制技术，波长路由的光网络能够实现 更大范围内的联网。为了有效地管理网络，通常把整个网络依据技术、地域、 管理等差别划分为多个域，各个域相对独立，他们之间通过n n i 接口进行信 息交互。从路由角度来看，这些域又可能被划分为多个路由域，网络拓扑和 资源利用信息只在每个域内进行通告，域与域之间只交换可达性信息。 在路由的选择原则方面，当域与域之间具有多路由时，选择的最佳路由 是经过域数目最少，每个域内的最佳路由，以便近似于全网的最佳路由；在 同一路由域内，由于路由数据库很难绝对同步，导致各节点分别计算的优化 路由不是最优路由，因此需要提高路由计算的性能，例如采用重路由计算方 法。 4 1 2 a s o n 的波长分配 在a s o n 中，由于受价格和性能的限制，波长变换器仍不会被广泛使用， 因此主要基于波长连续性限制条件，讨论a s o n 波长分配问题。另外，在 a s o n 的分布式控制模式下，每个节点无法获得全局的光通道及波长使用信 息，只具有本节点或本路由域的波长信息，所以传统w d m 网络中的一些波 长分配算法，并不是都可以直接应用在a s o n 网络中，一些可以直接运用， 一些经过修改可以应用，一些则是不适合应用的，以下分别加以讨论。 在传统的w d m 网络中，大多数r w a 算法都是基于集中控制式架构的， 通过掌握全网的拓扑和资源利用信息的网管系统来负责建立连接，因此易于 实现集中的路由和波长分配算法。集中控制式的波长分配方法主要有两类， 5 2 一类是分布式波长预留方案，另一类是集中式r w a 算法。 分布式波长预留方案是一种典型的分布式控制架构下的r w a 算法，通常 情况下，网络中的每个节点只知道网络的拓扑信息，收到连接建立请求后， 根据已经计算的路由，发送控制消息去寻找合适的波长。此类算法本身就适 应分布式控制环境，故对其扩展应用到a s o n 中比较容易。例如后向波长预 留方案、前向波长预留方案等。 集中式的r w a 算法是目前研究最多的一类算法，使用这类算法的网络要 求有一个中央控制节点，拥有全局的拓扑和资源使用信息，由它来集中处理 用户的连接请求，利用基于全局的信息来计算路由和分配波长。由_ 于我们主 要研究的是单路由域条件下的路由，所以扩展这类算法也非常有意义。以下 主要讨论集中式的r w a 算法。 在常见的波长分配算法中，基于局部信息的r a n d o m f f 算法都可以直接 用来分配波长。因为在a s o n 中，通过业务路由经过的各路由域之间的合作， 得到业务通路上的可用波长集是比较容易的，可采用从源端节点出发，沿着 选择的路由节点依次减少可用波长集，最后由目的节点来确定最后选定的波 长的方式实现。因此，基于局部信息的r a n d o m f f 可以直接应用在a s o n 中的波长中；而对于最少使用( l u ) 和最大使用( m u ) 算法，应用的前提 都是要求具有全网的波长使用信息；另一类算法相对容量损失( r c l ) 和相 对最小影响( r l i ) ，也是基于全网业务通路和波长使用信息来分配波长的。 这两类算法所要求的条件在a s o n 中较难满足，所以它们最多只可能在单路 由域中使用。然而，这两类算法的计算复杂度都比较高，基本上不能适应 a s o n 光通道动态、实时提供的要求，所以它们不适合a s o n 网络。 图4 1 给出由智能光节点组成的单路由域网络的f a r 和f f 波长分配的 算法流程，每个节点拥有路由域全部的或部分的路由信息，使用扩展的 o s p f t e 完成路由信息数据库的同步，利用r s v p t e 来创建交换连接。每 个节点同等的接受和处理用户请求，支持源端的路由方式。 经过以上分析可知，r a n d o m 和f f 波长分配算法都可直接应用到a s o n 中，当基于单路由域和波长连续性限制条件下研究波长分配子问题时，主要 考虑的是路由选择子问题。 4 1 2 1 基于波长信息完全分发的r w a 算法 集中控制模式下的三种路由算法f r f a r a r 已经在第三章做了详细的 介绍，这三种算法都能直接应用到a s o n 中。在三种算法中，a r 是性能最 好的，因为在选路的过程中，a r 考虑了网络当前的状态，但在分布式的a s o n 网络中，实时计算路由花销时间较长，实现过程中考虑因素多，复杂性高， 5 3 在此不予考虑。以下主要介绍其它两种相对简单高效的路由算法： ( 1 ) 固定最短径算法( f s p ：f i x e ds h o r t e s tp a t h ) 本算法是一种最简单直接的r w a 方案，在全网拓扑已知的情况下，采用 d i j k s t r a 算法为每一对源宿节点预先计算出一条路由，在每个节点上形成路 由表。当连接请求到达时，接收请求的节点查询本地路由表，获得到目的地 节点的最短径路由，此处的最短路径是指路出所经过的跳数最少。得到路出 后，在该路由上寻找通路上能够使用的波长信道，如果无可用信道，则该次 连接请求被拒绝；如果有多个可用波长信道，则根据f f 算法选取其中的一 个，然后采用分配的波长，通过信令协议去创建连接，节点在预留资源后， 将通过路由协议及时地将波长使用信息向全网进行通告。 ( 2 ) 固定备选路由算法( f a r ) 在f a r 算法中，我们为每一个源宿节点对预计算两条路由，一条是最短 路径作为主用路由，另一条是在网络拓扑中去除主用路由的所有链路后( 保 留节点) ，重新调用d i j k s t r a 算法得到的源宿节点对之间的最短径路由，这样 做的主要目的是考虑网络的抗毁性，保证主用路由和备用路由的无重边。 节点接收剑连接建立请求 寄崔臂骑鑫 l ! 毒磐找亟i _ 卜需攫觜骑荔 l ；离譬找查一一连接建立拒绝j可使用的波长信道可使用的波长信道一4 攸姥“砒”， 、- ， 一一， ：山路由协议将波长使i t ：用信息进行全