（通信与信息系统专业论文）基于模糊逻辑的qos路由算法研究.pdf

基于模糊逻辑的q o s 路由算法研究 摘要 ( 在通信网络中，路由控制问题对于网络服务的提供者和网络的伎 用者来说都是非常重要的。在传统的数据网中，路由仂、议只使用h o p 数或时延等单一因素作为衡量路径性能的依据，并使用最短路由算法 进行路径代价的计算。然而，在综合业务数字宽带网络中承载着各种 不同的业务类型，它们都具有不同的q o s ( q u a l i t y o f s e r v i c e ) 要 求，要想找出一个在不同q o s 要求之间折衷的适当的度量值是十分 困难的，也是不恰当的。因此，需要设计出一种能满足不同q o s 要 求的路由策略。但是多度量值的q o s 路由选择是一个n p c o m p l e t e ( 非 确定性多项式穷尽) 问题，使用传统的多目标优化方法是不太恰当的。 在本论文中，我们研究一种基于模糊逻辑的q o s 路由方法，这种 方法即能满足不同业务的q o s 路由要求，又能均衡网络链路的负载。 模糊逻辑方法是解决o o s 路由问题的比较理想的方法。因为q o s 路由 具有多性能准则折衷的特性，它的有些性能是相互冲突的，而模糊逻 辑方法是一个解决多性能准则折衷问题和处理公式上不能求解的复 杂系统的有效工具。此外，q o s 路由问题中包含两类非确定性因素， 一个是由于网络中业务量的非确定性导致q o s 路由的非确定性本质， 另一个是优化目标的模糊性( 由于对语音等数据传输质量的人为判决 而导致的模糊性) 。模糊逻辑方法能很好地处理q o s 路由问题的非确 定性。仿真实验证明q o s 模糊路由算法能提高网络的吞吐量和利用率 等网络性能。 模糊规则库对于模糊路由选择模型来说是很重要的，因为它是 模糊路由推理的依据。卜而所讨论的q o s 模糊路由算法的模糊规则库 是靠专家知识人工添加的，当模糊参数或模糊参数子集数一多时，模 糊规则的数目将会指数倍地增大，若面对数干条甚至更多的模糊规则 数，再有经验的专家也难以胜任。为了解决以上的问题，本论文提出 了一种新的基于神经网络的q o s 模糊路由选择算法，该算法利用神经 网络的学习能力从输入输出数据中提取出模糊规则，使模糊系统有了 自学习的能力，弥补了过去模糊规则只能凭经验设计、调试周期长的 缺陷。仿真实验证明改进后的q o s 模糊路由算法具有了自学习建立规 则库的能力。3 本论文的结构如下：第一章介绍了路由技术的基本原理；第二章 描述了模糊逻辑和神经网络；第三章首先研究了q o s 路由和采用模糊 逻辑方法来进行q o s 路由选择的原因，接着对模糊路由算法模型作一 阐述，最后进行仿真实验的验证工作。第四章提出了一种新的改进算 法并完成了仿真实验，最后对本论文内容进行总结。 关键字路由选择? 模糊逻辑? 服务质量：神经网络 a l g o r i t h mr e s e a r c ho f q o s r o u t i n g b a s e do nf u z z yl o g i c a b s t r a c t r o u t i n g c o n t r o lo ft e l e c o m n m n i c a t i o nn e t w o r k si s i m p o r t a n t t ob o t h n e t w o r ks e r v i c ep r o v i d e r sa n dn e t w o r ku s e r s i nt r a d i t i o n a ld a t a n e t w o r k s r o u t i n gp r o t o c o l su s u a l l yc h a r a c t e r i z et h en e t w o r kw i t has i n g l em e t r i c s u c ha s h o p - c o u n to rd e l a y s h o r t e s t p a t ha l g o r i t h m sa r et h e nu s e di n t h e s en e t w o r k sf o r p a t hc o m p u t a t i o n t h es u b j e c t i v i t yo ft o d a y sq o s r e q u i r e m e n t so ft h ed i v e r s et r a f f i cc l a s s e si nb i s d na n dt h ec o m p l e x t r a d e o f f sa m o n gt h e mm a k ei td i f f i c u l tt od e f i n ea na p p r o p r i a t eu n i q u e r o u t i n gm e t r i c m o r e o v e r g i v e nt h ed i s t i n c tc h a r a c t e r i s t i c so ft h ev a r i o u s t r a f f i c d a s s e s ，t h es a m em e t r i ci sn o tu n i v e r s a l l ya p p l i c a b l e h e n c e ，a n e w r o u t i n gp a r a d i g mt h a te m p h a s i z e ss e a r c h i n gf o ra l la c c e p t a b l ep a t h s a t i s f y i n g v a r i o u s q o sr e q u i r e m e n t s i sn e e d e df o r i n t e g r a t e d c o m m u n i c a t i o nn e t w o r k s h o w e v e r , i ti sk n o w nt h a ts u c h a r o u t i n g p r o b l e mi n v o l v i n gt w o o rm o r ea d d i t i v eo r m u l t i p l i c a t i v eq o sp a r a m e t e r s i n m l yp o s s i b l e c o m b i n a t i o ni s n p c o m p l e t e h e n c e ，c o n v e n t i o n a l m u l t i o b j e c t i v eo p t i m i z a t i o na p p r o a c h e sm a yn o tb et h em o s ta p p l i c a b l e t e c h n i q u e s t ob e u s e df o rt h i sp r o b l e m i nt h i sp a p e r , w es t u d ya q o sr o u t i n ga p p r o a c hb a s e do nf u z z yl o g i c ， 厂一 w h i c hi sn o t o n l y t om e e tt h eq o sr e q u i r e m e n t so fd i f f e r e n tt r a f f i c s e r v i c e sb u tt ob a l a l l c et h el o a di nt h en e t w o r kl i n k sa sw e l l q o s r o u t i n g p r o b l e mi s i n d e e dw e l ls u i t e df o rt h ea n a l y s i su s i n gf u z z yl o g i cb e c a u s e o ft h e i rc h a r a c t e r i s t i c so f h a v i n gm u l t i p l ep e r f o m a a n c ec r i t e r i a , s o m eo f w h i c ha l eo f t e n c o n f l i c t h a g t h ef u z z ya p p r o a c h c a l lb eu s e da sa l l e f f e c t i v et o o lf o r q u i c k l yo b t a i n i n g ag o o d c o m p r o m i s es o l u t i o n a n d s o l v i n gp r o b l e m st h a t a r ed i f f i c u l tt ot a c k l em a t h e m a t i c a l l y m o r e o v e r , t h e r ea r et w o t y p e s o fi n a c c u r a c y i n c o r p o r a t e d mt h e q o sr o u t i n g p r o b l e m o n e i st h ea m b i g u i t yi n h e r i t e di nt h en a t u r eo ft h et r a f f i cf l o w s ， a n dt h eo t h e ri st h ef u z z yg o a l sf o re a c ho ft h eo b j e c t i v ef u n c t i o n s f o r h a n d l i n gs u c h k i n d so fv a g u e n e s s ，i ti s n o th a r dt oi m a g et h a tt h ef u z z y a p p r o a c h i ss u i t a b l ef o r s o l v i n gq o sr o u t i n gp r o b l e m s e x p e r i m e n t e d r e s u l t sa r e p r e s e n t e d w h i c hd e m o n s t r a t et h a tt h e f u z z yq o sr o u t i n g a l g o r i t h m c a l li n c r e a s et h e t h r o u g h p u t a n du t i l m a t i o no ft h e c o m m u n i c a t i o nn e t w o r k a sw e k n o w , t h ef u z z yr u l e - b a s ei sv e r yi m p o r t a n tf o rt h eq o sf u z z y r o u t i n ga l g o r i t h m ，b e c a u s ei t i st h eb a s i so ft h cf u z z yi n f e r e n c es y s t c m t h ep r o p o s e dq o sf u z z y r o u t i n ga l g o r i t h m u s e s e x p e r tk n o w l e d g et o d e s i g nt h er u l e b a s eb yh a n d i f t h en u m b e ro f f u z z yr n l e si st o ol a r g ef o r e x p e l st od e s i g nb yh a n d ，a ni m p r o v e dq o sf u z z yr o u t i n ga l g o r i t h mt h a t c a ns o l v et h i sp r o b l e mi sn e e d e d i nt h i sp a p e r , w ep r o p o s ean e wq o s f u z z ya p p r o a c h b a s e do nn e u r a ln e t w o r k s t h e f i t z z yn i l ec a n b ee x t r a c t e d 厂 f r o ms a m p l e sb yu s i n gt h ed c l a l g o r i t h m t h en e wa l g o r i t h mi sa b l et o a v o i dt h e d i s a d v a n t a g e t h a tt h er u l e - b a s ec a l l o n l y b ee s t a b l i s h e d b y e x p e r tk n o w l e d g ea n dm a k et h ed e b u g g i n gp r o c e s s e a s i e ra n df a s t e r s i m u l a t i o nr e s u l t sd e m o n s t r a t et h a tt h en e wm o d e li sa ne f f e c t i v e a p p r o a c hf o re s t a b l i s h h l gt h er u l e - b a s e t h e p a p e ri so r g a n i z e da sf o l l o w s i nc h a p t e r1 ，w ei n t r o d u c eb a s i c c o n c e p t so f t h er o u t h l gt e c h n o l o g i e s i nc h a p t e r2 ，w ed e s c r i b et h ef u z z y t h e o r ya l l dn e u r nn e t w o r k s i nc h a p t e r3 ，f i r s t ，t h eq o sm u t i n ga n dt h e n e e df o rf u z z yl o g i ca r ep r e s e n t e d s e c o n d , aq o s f u z z yr o u t i n gm o d e li s d e s c r i b e d f i n a l l y , t h es i m u l a t i o n r e s u l t sa r ea n a l y z e d i nc h a p t e r 4 ，an e w q o sf u z z r o u t i n ga p p r o a c hb a s e do nn e u r a ln e t w o r k si sp r o p o s e da n d t e s t e d t h ec o n c l u s i o no ft h e p a p e r i sa l s o p r e s e n t e d k e yw o r d s r o u t i n g ，f u z z yl o g i c ，q o s ，n e u r a ln e t w o k s 厂 上海交通大学硕士学位论文 第一章路由选择的基本原理 路( r o u t e ) 的概念出现于本世纪70 年代，当时的网络结构较简单，因此 直至80 年代中期出现：r 大规模的网络结构后，路由技术才得到r 广泛的应用。 在i s o o s i 体系结构中，路由技术是第三层( 网络层) 的功能i ，如图l 一1 所示。网 络层的主要功能是在通信系统之间提供建立、保持和终止网络连接的手段， 并为传输层实体通过网络连接交换网络服务数据单元提供功能和规程方面 的手段。其主要任务为( 1 ) 向传输层提供服务，并使得高层的设计考虑不依赖 于数据传送技术和中继或路由；( 2 ) 路由选择和执行交换功能，用户可能不仅 仅在两个端系统之间进行通信，而往往要在包括中继系统在内的开放系统之 间通信，中继系统需执行路由选择和交换功能，为两个端用户提供端到端连 接；当传送的数据需要跨越一个网络的边界时，网络层应该对不同网络中分组 的长度、寻址方式、通信协议进行转换，使得异种网络能够互联。( 3 ) 数据链 路的复用，即让多对通信用户共享数据链路，如逻辑信道和虚电路。 a i 嚣) ii c a t i o na l o f ti c a t m u l a v e r p r e s e n t a t i p 1 e s e n t a t i o n 一 l a y e r s e s s i o ns e s s i o n 1r l 斛p r t r m m p o r t t r a n s p o r t l a v e rl a v e r n e t w c t kn e t _ o r kn e t * 切n e 协a r k 一一-一 l a v e rl a v e r d a t a 一】i n kd a t a - i i i d a 协一l i n k d a t a - i i l l k 一一一 l a v e r p h v s i c a l p h y s i c a lp h y s i c a lp h y s i c a 】 - 一-一 l a v e rl a v e rl a v e r iilill 图i - ii s o o s i 的体系结构 f i g 1 - 1s y s t e ms t r u c t u r eo f i s o o s i 对于实际的网络协议( 如ip 协议) 来说，其本身并不涉及具体的路由选择 细节，它只说明路由选择的一般原理和规则，具体的路由选择是指路由表的建立与 上海交通大学硕：l 学位论文 刷新机制，南一组独立的路由选择协议( r o u t i n gp r o t o c 0 1 ) 描述。路南选择的过程 是由路由算法米完成的，路由算法可以运行在网络主机上，也可运行在专用的路由 设备上，如路由器是一种网络瓦联泼备，其主要功能就是进行路由选择。 所谓路由选择指的是在分布式交换网中每个节点具有自动选择传送数 掘到达目的地的最佳路径的能力，就是说节点设备( 如节点上的交换机、路 由器等) 根据一定的原则通过计算来确定每一分组发往宿端的最佳输出链 路。 路由选择技术涉及两个方面的内容：最佳路径的选择( 路由技术) 及信包存网 络上的传递( 交换技术) ，交换过程相对简单，丽路径的选择过程比较复杂。具体将 在1 2 和1 3 小节q 介绍。 1 。1 路由选择技术的发展 路由选择技术的发展有以下几个阶段“j 。 1 1 1 共享介质l a n 许多校网网是基于共享物理介质的，如i o mb s 的以太网段，使用昂贵的 基于软件的路由器把这些网段互连起来。lan 的集线器( hub ) 不象路由器端 口那么昂贵，因此网络管理者尽力使每个网段的用户数多些而保持网内网段数较 少。 然而毕竟每个网段连接的用户数有限，随着交换技术的进一步发展，出现了 交换式集线器，或称第二层交换。这种设各本质上是个多端1 ：3 的学习桥获 取网段上书机与其端口的每一个连接。它检查进来的通信流，推断出连到每个端 口上所有主机的m ac 地址，用这个信息米建立本地分组转发表。进来的帧不用 向全部端口进行广播，只需被送到该帧的目的主机的局域网端口。这种交换技术 提高了局域网的有效容量，只要不涉及同一端口，多个传输可以l 一时进行。然而广 播消息及目地址没有在转发表中包括的帧仍会被送到所有端口。多数情况下，连 在交换集线器上的主机要比共享式的多些，但j 。播域仍限制了每个网段上的最大 主机数。 i n t e r n e t 和i n t r a n e t 存企业中广泛应用，多媒体业务和应用的引入，趸增加 了任意两台机器之间互连的需求。 4 厂 上海交通大学硕士学位论文 i i 2 “一次路由，多次交换” 随稽通过传统路南器的通信量的不断增长，这些基于软件的路南器便容易 成为网络中限制性能的瓶颈。由于这些路由器的处理能力无法跟上通信量的增长 许多厂商开始寻找新的办法，使大部分网络流量绕过路由器。这种办法称作“一 次路由，多次交换”。小同一商开发j ，小同的变体，但慕本的思想是一致的，即把路 由器的路由计算与分组转发功能分开。路由计算因其涉及路由协议，创建路由表， 初始化路山选择，及数据流的安全处理等将由软件处理。分组转发是一个相对简 单的过程，可以用高速而费用相地低廉的硬件来实现。问题的关键就在于如何识 别那些已明确路由的帧“流”来避免对每一个帧都执行路由计算。一旦帧的“流” 识别出来了，“一次路由，多次交换”就可以实现了。 根据“一次路由，多次交换”的思想，不同的厂商都有自己独特的设计，如 i p s i “n 的i ps w i t c h i n g ，c a b l e t r o n 的安全快速虚拟网络( s s r ) ，3 c o m 的f a s ti p 。 这些设计都通过采用上述办法克服了传统路由器的性能局限，但是，他们都引入 了各个厂商特有的协议或硬件，很难进行扩展和互通。唯一的一个“一次路由， 多次交换”的多厂商设计并获得一定程度成功的是m p o a ( a 硎上多协议) 标准， 它使用路由服务器完成子网闸ip 数据流的路由计算，由a t m 网络体系结构完成 分组转发功能。它有多厂商支持，并可咀提供端到端的性能保证。但是它结构非 常复杂，而且实现起来费用也很昂贵，只适用于那些atm 楼区骨干网的用户环 境。 i i 3 第三层学习网桥 随着硬件技术的不断发展，从第二层交换演变出一种新的技术“第三 层学习网桥”出现。与第二层交换通过m ac 地址来获知设备的端口位置不同， 这种新设各可以通过第三层ip 地址来状知与每个交换端口有关的设备。 通常第= 层学习网桥都作为已有路由器的前端设备，监视经过它们到达路 南器的数据流，截取】p 地址，建立简单的路冉表。通过这张表，它就可以自己进 行子网间的分组交换，减轻路由器的工作负担。但是它不使用路由协泌( 如r1 p ig r p ，ospf 等) ，因此不能与其他路由器或是别的第三层学习网桥进行通 信。这种第三层学习网桥容易安装，在一个路由器超负荷运转的情况下，可以作为 临时替代的解决方案。 上海交通大学硕士学位论芷 1 1 4 路由交换的引入 新一代产品的引入正改变着网络管理者对交换和路南的认识，这些产品通 常称作路由交换，基于硬件的路由器或是线速路由器。 传统的路由产品巾，是由运行在一个或多个相对较慢丽且昂贵的微处理器 上的软件来实现路由功能的。相反，路由交换技术执行ip 选路是用专用的硬件， 如通过专用的路由asci 芯片，使用共享存储器或交叉矩阵交换，这些路由器 的乔吐量比足够线速驱动多个千兆以太网链路所需要的吞吐量还要高。费用相对 较低。 路由交换有许多优于基本ip 路由的功能： ( 】) 支持诸如ospf 和rip 等路由协议，可以在】p 路由网络作为对等 或替代路由器： ( 2 ) 支持rsvp 等多种优先级别，可为网络提供q p 务级别( cos ) 分类： ( 3 ) 支持ip 组播路由，使路由器可以处理诸如视频信息等广播多媒体通信， 路由器只把组播分组发送到已经登记了的参与该次通信的端口： ( 4 ) 支持多个骨干网链路的中继，从而实现更人规模、更有弹性的骨干网互 连。由于路由交换的高速分组转发能力，多数路由交换设备只包含局域网接口， 并且只是于园区网络和建筑物网络。j 。域网的一些性能低速的帧中继接 口、外部协议支持( 如b g p ，即边界网关协议) 、大型互连网规模的路由表 一留给现有的骨丁网络由器来实现。 基于a s i c 设计。线速的路由交换技术能够队和第二层交换技术相同的性能 水平转发i p 数据包，因而不必再避开路由问题。基于路由交换技术的设备与标 准的基于软件的路由器有良好的互操作性，配置也很相似。在网络流量模式从传 统的8 0 2 0 ( 子网内子网间) 转为任意点之间互连的发展趋势下，以线速路由交 换设备作为骨干网的高速转发节点是一个很好的选择。 1 2 交换技术 在通信系统中，如果在两端之间并不是通过专用线路连接，而是要经过 通信网络的接续过程来建立连接，那么就需要网络的各个中间节点实现转接 功能，从而提供一条端系统与端系统之间的数据通路。我们通常将喇络节点 以某种转接方式来实现数据通路接续的技术称为交换( s w i t c h i n g ) 。 交换算法相对比较简单，大多数路由选择协议的交换算法都相同。一般情况 6 上海交通大学硕士学位论文 下，一个主机确定将菜一信包发往另一主机，信包中含有信宿机的地址，该地址属 于网络层地址，或称为协议地址。通过某种方式确定转发路由器地址后。信源机将 该路由器的物理地址加到信包中并将信包发往此路由器，该物理地址是介质存取 控制( m a c ) 层地址。 路由器接收到信包后，检查信包的协议地址，确定是否能将信包转发至f 一 驿站。如果路山器无法确定，则拘信包放弃；如果能够确定，则将信包中的物理地 址改为下一驿站的物理地址并转发至下一驿站。下一驿站若是信宿机，则说明已 完成发送工作；若不是信宿机，则该驿站通常为另路由器，该路由器执行i 前一 路由器丰 同的处理工作。由此可见，在信包传递过程中，信包中的物理地址不断改 变而其| 力设地址( 即信宿机地址) 不变。 现代通信网中的交换方式可分为电路交换、报文交换和分组交换。 住宽带综合通信网出现以前，电路交换和分组交换分别以两种独立的网 络交换方式为人们提供两类性质不同的电信业务，即实对话音和非实时数据 业务。但随着信息活动的丰富，人们越来越迫切地需要通信网络把话音、数 据和阁像结合起来，并以一种统一的接入方式提供综合的多媒体服务。于是， 通信界和计算机界朝藉多媒体综合服务展开了激烈的竞争。计算机界开发了 分组交换、帧中继( f r a m er e l a y ) 、快速分组交换，以及专用的信元交换： 通信界则发展了电路交换、多速率电路交换、快速电路交换等。 1 , 2 1 电路交换 电路交换足最早用于通信的交换方式，所谓电路交换足指交换系统为通 信的双方寻找并建立一条全程物理通路，以供双方传输信号( 信息) ，直至 信息交换结束。 电路交换的幕木过程是：在开始正式的数据传输之前，首先由通信的一 方发起呼叫，一直等到与另一方建市起条转按式的数据通路，然后才开始 数据传输。在整个传输期间，该通路始终为通信双方占用。当所有的数据传 输结束后，可以由任何一方发起断开连接，从而释放连接，如图1 - 2 所示。 电路交换具有以下几个特点。其主要的优点在于：数据传输时延小，提 供的电路对用户是透明的，信息传送的吞吐薰大。然而，电路交换有两个主 要的缺点，其一就是必须有一个呼叫建立过程( 时延较大) ，另一个更大的 弱点就是电路建立后，专供通信的双方使用，即所占用的带宽是固定的，当 无信息传输时，所建立的电路末被利用，所以网络资源的利用率较低，尤其 是对于具有突发性的计算机数据而言效率更低。因此，电路交换不能适应网 上# 堕望查釜堡圭兰堡垒苎一一 一一。 络发展的需求。 o 瓣鬻冀纂篆嚣翕鬻谍巢纛缀 戮徽孺j 篙嚣器黑篇淼溜篡 望嘉璧鬈耋蒸鬈嚣鬟裟黧裂鬟掣麓嚣羰釜 烹篓耄鬟譬霪慧鐾鬟警笔笔套荨鬈萎篡篙凳纛数磊淤主蓑 网络中交换与传输的数据单元，它包含将璺芨遮削c 髓刚。姒计。” 短很不一致。 jl 延 p k 0 传捶时延 毒输 1 f l 匿1 2电路交换示惠图 n g ，1 2 c i r c u i ts w i t c h i n g 寻找输出 线路时间 呼叫处理时蜘 l 海交通大学硕士学位论文 程度和利用率。 1 2 3 分组交换 分组交换足另一种存储一转发方式的交换，它与报文交换的不同之处在 ：所处理的数据单元的长度不同。一段长的报文被分割、装配成多个较短的 数据单元，每个单元称为分组( p a c k e t ) 。进行分组交换时，发送端先要将 传送的信息分割成若干个规定长度的数据块，冉装配成一个个分组。装配过 程中要对各个分组避行编号，并附加 ：源端和宿端的地址以及约定的其他信 息，这样每个分组都带钉个分组头和校验序列。然后将各个分组分别送入 通信子网中进行交换传输。当这些分组到达目的端系统后，被重新组装成原 来的报文递交给用户。 abc i 拳 、 传输时延i i报文 1 传播时延 、 f e ： 报文 芝 、_ f 图i - 3 报丈交换示意图 f i g 1 3m c ss a g es w i t c h i n g 存储一转发时延 分组交换的特点为：( 1 ) “管道化”( p i p e l i n i n g ) 效应，如图i - 4 所示。 当第1 个分绢在从节点b 到c 传输的时候，i 司时有第2 个分组在从a 到b 传 输，第1 个分组在从c 到d 传输的同时，第2 个分组正从b 到c ，而第3 分 组正从a 到b 传输。由于级联的多条通信链路能被同时使用，所以设备利用 9 上海交遁大学硕士学佗论文 率可以显著提高。而且又冈为采用了长度较短的分组，中间节点通常只需要 在内存中开辟个小的缓冲区就可以了，对分组的处理速度也就加快了，所 以传输效率可大大提高。通过分组交换网引入的时延大大低于报文交换产生 的时延。( 2 ) 蒯为每个分组的长度较短，从而使得传输或处理过程中出错的 可能性比起耀段的长报文出错的可能性要低得多。f n j 分组交换也意味着按分 组纠错，发现错误只需重发出锗的或及其相关联的分组，这使得差错控制过 程中，分组的重发概率较低，从而提高了通信效率。( 3 ) 在多路由的网络中， 各分组可独立地存网中传输，从而有可能减少拥挤，网络可靠性就能提高。 若路由选择采取动态路由算法，当通信网内某处发生故障时，分组能自动避 开故障选择迂回路由传输，不会造成通信巾断。 abcd 变换节点 t + 抟辅时生 分组l 、 分组2 之组2 - 、 l 分蛆3 传措时延 f f 图1 - 4分组交抉示意图 f i g 1 4 p a c k e ts w i t c h i n g 存储转发时艇 总的来说，以上三种交换方式在实际的路由选择过程巾的区别为：电路 交换中各连接的路由是在连接建立时由复杂的路选算、法在整个网络中确定 的，信令系统住路由经过的各个网络设备内填写路由表以标识交换信息，一 条连接上的一次通信中所有信息都经过和同的路由。在报文交换和分组交换 中，路由信息由各个分组头携带，交换设备杏看到来的分组头中的地址信息， 并根据当时的网络状态选择一条路由，将分组转发到下级的网络设备中。 1 0 上海交通大学硕士学位论文 对于分组交换，糟采用数据报传输方式同一、i k 务的不同分组在网络中经过 的路径可能彳；同，但若采用虚电路传输方式时，同业务的路由枉虚呼叫时 就确定下来，因此其分组被传送的路径是相同的。 1 3 路由技术 路由技术的目的就是找出到达下一站 的最佳路径。最佳路径依赖于不同的衡量标 准，例如可使用路径长度作为衡量标准。在 确定最佳路径的路由算法中，路由表 ( r o u t i n gt a b l e s ) 是一个重要的数据结构， 其中包含了网络的路由信息，算法通过建立 和维护路由表进行最佳路径的确定。 路由算法根据算法要求在路由表中填写 各种路由信息其中最基本的是口标驿站 ( h o p ) 信息( 见表1 1 ) 。这一组信息告诉 d e s t i n a t i o n n e x t h o p l 2 7a f 2 4c l 5 2b l 1 6c l 表1 - i 目标驿站路由表 t a b l e1 - 1r o u t i n gt a b l e so fd e s t i n a t i o n l l o p 路由器，在信包发往信宿机的过程中，最佳选择是将信息转发至下一驿站( n e x t h o p ) 所代表的节点。当路由器接收到一个输入信息时，首先检奁信包的目标地址， 然后尝试找出与此目标地址相匹配的下一驿站，若匹配成功则进行信包转发，台则 放弃该信包。除了目标驿站信息外，根据不同的路南算法，路南表中还包含有其 它内容，例如最佳路径的衡量标准等信息。 在路由器之间传输的各种信息巾。有关路由选择的信息称为路由刷新报文 ( r o u t i n gu p d a t em e s s a g e ) 。路由刷新撒文通常是全部或部分路由表内容。通过 对所有路由信息的分析，路由器可建寺一个详细的网络拓扑图。例如，用于链接 状态路由算法的链接状态广播报文通知其它路由器有关自身的链接状态，通过这 些信息路由器可建立一个完整的网络拓扑图，通过拓扑图便可确定到达目标的最 佳路径。 1 3 1 路由算法的设计目标 一个弹想的路由算法应具有如下特点： ( 1 ) 正确性：算法必须正确。 ( 2 ) 简单性：算法应使用节点上最少的运行资源，这样可以节省开销、减少 时延，而目应该尽量少使用节点间链路的带宽，如果为了计算合适的路由必须使 i 海交通大学硕士学位论文 用网络其它节点发来的大量状态信息，额外开销就会较大，当算法运行在低档设 备上时效率尤为重要。 ( 3 ) 自适应性，或称健j j 性：算法应能适应业务量和网络拓扑的变化。当 i 硼络中的业务量发生变化时，算法能自适应地改变路由。当节点、链路出现 故障时或当修复后重新t 作时，算法应能及时找到一条替换的路径。 ( 4 ) 稳定性：算法必须收敛，当业务负载和拓扑变化时，没有过多的振荡。 所谓振荡，是指算法得出的路由是在一些路由之间来回不停地变化。由于路 由器位于瓦联网络的连接点上，有着相当重要的地位，若算法不稳定将造成严重的 后果。优秀的路由算法经得起时间的检验并且在任何情况下都能稳定地工作。 ( 5 ) 公平性：算法对所有的用户必须是同等的，仅指在分配的优先级范 围内。例如，仅考虑使某一对用户的端到端时延为最小，就明显不符合公甲 性的要求。 ( 6 ) 快速收敛性：路由算法要求能够快速收敛。这里所指的收敛是指最佳 路径能迅速被网上所有路由器所接受。若发生网络故障导致线路断开或恢复，相 应路由器向网络发出路由刷新报义，促使其它路由器重新计算最佳路径，更新路由 表，同时又向网络发送刷新报文，直至所有路由器都相互认可这些最佳路径。收敛 慢的算法将导致路由环问题及网络损耗。 图1 - 5 给出了一个路南环的例子。在该情况下，tl 时刻一信包到达路南器 1 ，路由器1 已经进行了路由刷新，指明了路由器2 是该信包的下一驿站，于是将 信包转发至路由器2 。由于算法的慢收敛，路由器2 还未进行路由刷新，路由表指 明其下一 5 葶站为路由器1 ，于是路由器2 义将信包转发全路由器1 ，这样信包将在 两个路由器间来回传递，形成环路，直至信包交换超时被丢弃或路由器2 刷新路由 表才能终止。 ( 7 ) 最优性：路选算法应该能提供最佳路由，从而使平均分组时延最小 而吞畦量最大。这里“最佳”可以是由多个因素决定的，如链路长度、数据 率、链路容量、传输时延、节点缓冲区被占用程度、链路的差错率、分组的 丢失率等。显然不存在一种绝对最佳的路由算法，所谓“最佳”只能是相对 于某一种特定要求下得m 的较为合理的选择而已。 实际上没有个算法能全部满足上述要求，有的还可能是矛盾的。例如， 要使吞蛙量最大就可能会增加时延。然而，路选算法的效能可能影响时延随 着吞吐量增加而增加的快慢，而且一个好的算法可能得到一个较好的吞吐量 门限，在这个门限值上时延过大就必须进行流控。 上海交橱大学硕士学位论文 a f t e r r e f r e s h i n g b e f o r e r e f r e s h i n g 图1 - 5 慢收敛与路由环 f i g 1 5 s 1 0 wc o n v e r g e n c ea n d r o u t i n gl o o p 1 3 2 路由算法的衡量标准 路由信息表中包含了交换所需的如何确定最佳路径的要求，即确定最佳路 径的标准，路由算法根据这些标准进行计算。复杂的算法往往综合多种标准，常用 的衡量标准有： ( 1 ) 路径长度 路径长度是使用最普遍的标准，一些协议许可网络管理员对网络的线路赋 予一定的代价值，在此类情况下，最佳路径就是所经过的每条线路的代价总和。有 些协议定义驿站数量为标准，即路径上所经过的网络设备( 如路由器) 的数量。 ( 2 ) 可靠性 在路由算法中，可靠性是指每个网络连接的可靠性，通常用每位的错误率表 示。有些网络连接可能经常发生故障，i n 发生故障时，有些网络连接能很快或很容 易恢复。可靠性可通过对网络连接赋予相应的数值来确定。 ( 3 ) 时延 时延是指将信包从信源机发送到信宿机所经过的时间，时延受很多因素影 响，例如：网络带宽、路由器端口队列数量、网络负荷以及实际传输的距离等。 ( 4 ) 带宽 带宽是指网络连接的通信能力，虽然带宽代表了网络连接所能达到的最高 的通信速率，但往往宽带连接慰昧着网络更繁忙，传送一个信包所需要实际时间 可能更k ，因此宽带连接并不一定能提供更好的路由能力。 ( 5 ) 负载 负载是指网络设备( 如路由器) 的繁忙程度。负载有多种计算方式，如cpu 上海交通大学硕士学位论文 利用率、每秒处理舶信包数量等，对这些参数的监控过程本身也怒j f 嘲络的_ - 利，负 载。 1 3 3 路由算法的分类 路选算法的分类有各种方法，表卜2 给出了路选算法的基本要素，这些 要素可以用来对路由选择算法进行分类。 1分类要素 每一节点( 分布式) 中央节点( 集中式) 。决策地点 源节点 节点子集 分组( 数据撤) 决策时间 会话( 虚电路) 链路数 设施代价 性能准则 时延 吞吐量 无 网络信息源本地 ( 与路由选择有关的相邻节点 信息)路径上的节点 所有节点 静态一一简单类算法 动态更新时间：连续变更、 路选策略 周期性变更、主要负载改变时、 拓扑改变时 表1 - 2 路由算法的基本要素 ( 1 ) 静态或动态路由算法 静态路由算法对网络拓扑结构或运行状态的改变不作反应，由管理员在 路由使用前建立的，只有管理员才能对路由表进行修改。静态路由算法的设计简 1 4 上海交通大学硕士学位论文 单，在可预知网络的通信量且网络结构简单的情况下使用静态路由算、法。动态路 由算法通过分析路由刷新报文。能够进行实时调整以适应网络的变化。动态路由 更新时间可以基于不周的方式，如连续变更、周期性变更、仪在主要负载改 变时、或翥仅当网络拓扑改变时( 增加、删除节点或链路) 。路选决策可以 是针对每个分组的( 常用在数据报方式中) ，也可以是在会话或连接建市时 进行( 如采用虚电路方式) 。 i 嘲络信息源指与路由选择有天的信息采集途径。对予静态路选，不需要 信息源。信息采集的途径依次是存当前执行路选的本地节点上、通过相邻节 点、或者根据路径上先前分组所累积的信息、或者是网络中全部节点。 ( 2 ) 集巾式或分布式路由算法 这是根据决策地点的不同而进行的分类。对于集中式算法，一个中央节 点承担企部路由选择任务，从网络中的各节点获取网络运行状态信息，并将 确定的路由传播到相关的节点。分布式算法包含节点之间的协同工作，如信 息共享和计算运行。一个特殊情形是由源节点来决策，它决定分组如何按路 由传送，并在分组头部装载捕述路由的信息。在某些重要的网络中，路由选 择是由称为路选节点组成的节点子集来完成的。 在考虑路选算法采用集中式还是分布式时需要折衷，集中式算法较为简 单，而且不大可能引起路南表的不一致性，冈为不需要如同分布式算法那样 必须考虑各个节点之间的信息的一致性。但是另一方面，运行集中式算法的 中央节点必须获取全网所有节点上的即时信息，而这又因为时延的影响往往 是过时的。对于分布式算法来说，正好相反，它们有较快的适应性，而且能 通过决策节点与相邻区域的交互，来保证更精确捕述网络运行状态的信息， 但是当需要优化路选和避免不一致的路由表时，难以保持节点间的协调工 作。 ( 3 ) 单重路由或多重路由算法 单重路由算法对同一信宿机提供一条最佳路由，多重路由算法对同一信宿 机提供多条路由以供选择，允许在复杂的线路上进行多重通信。多重路径算法不 仅提高了通信量而且提高了通信的可靠性。 ( 4 ) 单层或多层结构路由算法 单层结构巾，刚络上所有的路由器是对等的，而在多层结构中，存在主干路 南器与分支路甫器。信包从分支路南器转发至主干路南器，再传送至信宿机所在 区域的主干路由器，再从这一位置通过一个或多个分支路由器最终到达信宿机。 路由系统将一组逻辑节点称为域或自治系统。在层次结构中，有些路由器只 能存自治系统内相百通信，位于自治系统顶层的路由器可与其它自治系统的顶层 上海交通大学硕士学位论文 路由器进行通信。层次结构的主要优点在于模仿了公司的组织结卡勾，阂为网络的 大部分通信量存在于分公司内部( 自治系统) ，自治系统内的路由器只需清楚系 统内其它路l j _ 】器的情况。因此系统内的路由算法可进行简化，相应减少了路由刷 新时产生的通信量。 ( 5 ) 单点或多点路由算法 传统的单点路由箅法是针对单点通信业务而设计的，随着会议电视、分布 式处理等多点通信业务的人量涌现，使用传统的点到点通信机制支持多点通信的 低效率令人难以忍受，同时多媒体业务的各媒体之间女u 音频与视频、视听信号与 数据需要达成松散的同步关系，网络支持多点通信将冉助于实现这