（计算机软件与理论专业论文）互连网络中的路由算法研究.pdf

摘要 摘要 互连网络是一种流行的网络拓扑，现已广泛应用于电话网络、多处理器系统、 分布式计算机系统及路由器交换机等领域。作为互连网络结构之一的直连网络， 以其简单的结构、良好的扩展性及便于实现分布式管理等，正被引入到新一代的 大容量核心路由器中。 直连网络中不均匀业务的存在要求现有路由算法具有负载均衡能力。然而直连 网络中传统的路由算法未能很好地均衡网络流量，如确定性的维序算法对于一对 源宿结点只提供一条固定的路径，使得分组无法绕过网络中的拥塞区域：最短路 径算法的d u a t o 算法无法充分利用网络中的非最短路径资源；非最短路径算法的 g a l 算法是针对恶性流量模式设计的，善意模式下性能不佳。 本文主要对直连网络的负载均衡路由算法进行了研究，主要的工作和贡献包括 如下两个方面： l 。根据自然界中的气体扩散现象，提出了一神新的负载均衡路由算法一g d ( g a sd i f f u s j o nb a s e dr o u t i n ga l g o r i t h m ) 。该算法是最短路径完全适应性算法，使用基 于软件的死锁恢复机制来检测和解除死锁；它根据端口的超时分组数来确定端口 的拥塞程度，然后以此为参考来随机路由分组，将分组从拥塞程度重的端口分流 到拥塞程度轻的端口来均衡网络负载。我们使用o p n l t 软件在基于虚切通交换机 制下的k a r vn c u b e 网络中对其进行仿真，发现在相同的网络仿真环境下，g d 算 法的性能要优于传统路由算法( 如维序算法、d u a l o 算法、g a l 算法等) 。 2 研究了生物智能在路由算法中的应用，并提出了一种适用于直连网络的智能 路由算法一f o a ( f o n a r d o n l va g e n tr o u t i n ga 1 9 0 r i t h m ) 。该算法仍是最短路径完全 适应性算法，采用基于软件的死锁恢复机制来检测和解除死锁；它使用前向代理 来收集网络中的有限全局信息即当前结点到其源结点的旅行时间，并以此来更新 结点的旅行时间表；算法根据结点旅行时间表所记录的历史信息和当前的链路状 态来共同确定一个邻结点的路由质量，并以此为参考随机路由分组来均衡网络负 载。我们将f o a 算法与传统算法( 如维序算法、d u a t 0 算法、g a 蹲法等) 在基于 虚切通交换机制下的k a r yn c u b e 网络中进行了仿真比较。仿真结果表明，相对于 传统路由算法，该算法有着较低的时延和较高的吞吐。 关键词：直连网络负载均衡交换机制路由算法生物智能 a b s t r a c t a b s t r a c t 1 1 1 t c l n n e c t i o nn c m o r k sh a v er e c c 玎t l yf o u n dw i d ea p p i i c a t i o n s ，f r o mt e l e p h o n e n e t w o r k s ，m u l t i - p r o c c s s o rs y s t e m ，d i s t r i b u t e ds y s t e m st og w i t c h e s r o u t e r s a n dd i r e c t i n t e - c 0 加e c t i o nn e t 、o r k ( d l n ) ，咖et y p eo f t h ei n t e - c o 肌e c l i o nn e t w o r kn o ws e n ，e sa s a9 0 0 dc a n d i d a t ef o rt e r a b j tr o u t e rs w i t c h i n gf a b r i c so w i n gt oi t sc h 缸a c i e r i s t i c so f g o o ds c a i a b i i i t y 卸de 越yd i s t r i b u t i o nc o n t r 0 1 t h en o n - u n i f b 珊t r a 硒ci j ld i n r e q u i r e sa v a j l a b l er o u t i n ga l g o r i t h m st od i s t 曲u t e l h ed a l af l o we v e n i y 绑o n ga l lt h ep h y s i c a ll i n l 【s h o w e v e f ，t h et 珏d i t i o n a lr o u t i n g a i g o r i t h m s i nd i n ，s u c h 硒d i m e n s i o no r d e r 枷t i n ga i g o r i t h m ( d o r ) ，d u a t o s a 1 9 0 r i t h m ，g a le t c ，d on o tb a l 卸c ct h et f a f ：f i cv e r yw e l l f o re x a m p l e ，d o ro n l y p r o v i d e s eu n c h 卸g e dp a t hf o rac c n a i ns o u r c e d e s t i n a t i o np a i r t h a tp a c k e t sc a i l n o t b y p a 鲻c o n g e s t e da r e 弱i nt h en e h o r k ；d u a t o sa l g o r i t t l l ni sam i n i m a la l g o f i t h m w i i hn o n m i n i m a lp a t h su n e x p l o i t e d ；g a lw 硒d e s i g n e df o rt h ea d v e r s a r i a lt r a f f i ca n d g i v e sb a dp e r f b 册a n c eu n d e rt h eb e n j g nt r a f ! f i c t os o l v et h i sp r o b l e m ，t 、on e w r o u t i n ga l g o r i t h m sw e r cp r e s e n t e df b rd i n ，g d ( g 勰d i f f u s i o nb 弱e dr o u t i n ga l g o r i t h m ) w h i c hw 豁i n s p i r e d 的mt h eg a sd i f f u s i o n p h e n o m e n o ni nt h en a t u r e 卸df o a ( f o 刑a r d o n l ya g c n tm u t i n ga 1 9 0 r i t h m ) w h i c hi s a ni n t e g c n ta i g o r i t 量l i n b a s e d 彻s w a 删i n t e l “g e n c c m i n i m a ia d a p t j v er o u t j n gi s a d o p t e da n ds o f t w a r e b a s e dr e c 0 v e r ym e c h 柚i s mi su s e dt od e t e c ta n dr e s o l v ed e a d l o c k s i nb o t ha l g o r i t h m s i i ig d ，p a c k e t sa r er o u t e ds t o c h a s t i c a l l ya c c o r d i n gt ot h ec o n g c s t i o n d e g r c eo fap o nw h i c hi sm e a s u r e db yt h en u m b e ro fp a c k e t sw h i c hc a nn o tb cs e n to u t i na 舀v 胁p e r i o d a sar c s u l t ，f e w e rp a c k e t sw i l lb er o u t e dt ot b ep o nw h i c hh a sh i g l l e r c o n g e s t i o nd e g r c et ob a l a n c et h ei o a d hf o a ，o n l yf o r w a r da g c n t sa r eu s e dt 0u p d a t e t h er o u t i n gi n f 0 咖a t i o nr e i a i e dt ot e i rs o u r c en o d ew h j i et f a v e i i n gt ot h ed e s t i n a t i 叩 b e s j d e s ，p a c k e t s 盯em u t e d 啪d o m l yb a s e d 伽t h eg o o d n e s so fan e i g l l b o rw h i c hi s m e a s u r e db yn o to n l yt h er o u l i n gj n f b n n a t j o nr e c o r d e di nt h er o u t i n gt a b l eb u ta l s ot h e c l l r 咒n tl 如k n d i 哟靠i no r d e ft o 咒a c hl o a db a l a n c e s i m u l a t i o n sw e f ec a r r i e do u tw i t h o p n e ts o f l w a r ei nk a r yn - c u b en e m o r k si nw h i c hv j n u a lc l l tt h r o u g l ls w j t c h i n g m e c h a n i s mi su s e d ，柚di h er c s u l t ss b o wt h a tb o t h a l g o r i t h 加sa c h i e v eab e t t e r p e b 呻a n c et h a no t h e rp o p u j a ra i g o r i t h m ss u c ha sd o r ，d u a t o sa l g o n t h ma n dg a l k e y w o r d ：d i r e c ti n t e r c o e c t i o n e t w o r k l o a db a l a n c e s w i t c h i n gm e c h a n i s m r o u t i n ga l g o r i t h ms w a 珊j n t e j g e n c e 创新性声明 本人声明所呈交的论文是我个人在导师的指导下进行的研究工作及所取得的 研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文 中不包含其它人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大 学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志所做的任 何贡献均己在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 垒篮蚕日期：筮盟：f 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印、或其它复制手段保存论文。( 保密的论 文在解密后遵守此规定) 本学位论文属于保密，在一年解密后适用本授权书。 本人签名： 堡缝蚕 第1 章绪论 第1 章绪论 1 1互连网络基础 互连网络( i i l t e r c o n n e c t j o nn e t w o r l 【s ) 1 1 ，2 】是一种流行的网络拓扑，在诸多领域 如电话网、多处理器系统【3 蚓、并行计算机系统、路由器交换机【3 7 】等都有应用。互 连网络按结点连接方式分为直接互连网络( d i r e di n t e r 0 0 彻e d i o nn e m o r k s ，简称直 连网络) 和间接互连网络( j n d j f e c tj n t e r c o n n e d i o nn e m o r l 【s ) 。直接互连网络中， 结点和它的邻结点之间通过物理链路直接相连，网络中的每个结点都有完整的路 由器功能，能转发目的地不是本结点的数据包：间接互连网络中，通过交叉开关 控制结点问的相连与否，单个结点不具备路由功能，任意两个结点间的通信必须 通过某些交换机进行。此外，直连网络中，网络配置完毕后结点之间的连接状态 是固定不变的，即拓扑结构一旦形成就不再改变，因此也称作静态网络；而间接 互连网络中，结构是不固定的，是动态确定的。因为直连网络的结构是静态不变 的，所以控制简单，便于实现分布式管理，同时还具有良好的可扩展性，因此直 连网络有着及其广泛的应用，从传统的并行计算机、多处理器系统到现在的太比 特路由器【4 5 l 都有应用。本文主要针对直连网络做些研究工作。 1 1 1 直连网络拓扑结构及表示方法 直连网络的拓扑结构决定了相邻结点之闻的连接方式，一般采用正交结构实 现。网络拓扑正交的充分必要条件是：结点可以在一个正交的n 维空间内组织起 来，每条链路都要在一维中产生一个偏移量。正交拓扑进一步分为严格正交和弱 正交。严格正交拓扑中，每个结点至少有一条链路通过每一维；弱正交中，有的 结点在某些维上没有链路。严格正交结构规则，路由简单；弱正交拓扑则没有这 个优势。 我们主要讨论直连网络中的严格正交结构，代表性拓扑结构有网格( m e s h ) ，带 环网格f r o m s ) 及超立方体( h y p e r c u b e ) 等。网络结构的形式化描述常采用图的形式， 将网络中的结点称为图中的点，连接两结点的物理链路称为图中的边。 1 n 维网格( n m e s h ) g m g m 中的结点以n 维坐标( 如，d ，d ，。以一。) 来标识，其中，d ，( 0 s f s n 一1 ) 为整数， 且o d 。e 岛一1 ，为j 维上结点总数。对于两个结点a ( ，。一。) 和 b ( ) ，。，m 。以一。) ，如果存在维i ，使得葺一咒= 1 ，0 s fs n 一1 ，且f ，o s ，s n 一1 ， 有x ，一y ；成立，则称这两个结点相邻。例如，图1 1 中的( a ) 是二维网格结构。 2 n 维网格的特例k a r y m e s h 网络 如果n 维网格中的每一维结点总数都相同且均为k 。则我们就称该m e s h 网络 为k a r yn m e s h 网络，简称k 元n 网格。图1 1 中的( a ) 是5 a r y 2 m e s h 结构。 互连网络中的路由算法研究 3 n 维带环网络c h ( t o m s ) 同n 维网格( n m e s h ) ，网络中的结点仍以n 维坐标似。，d 。，d ：。彳。) 来标识，其 中，d ( 0 s f n 一1 ) 为整数，且o s 4 七，一1 ，t 为j 维结点总数。两种网络的不同 之处在于邻结点的定义：在带环网络中，对于结点a ( ，。) 和结点 b ( y o ，m 。以一1 ) ，如果存在维i ，使得“一m ) m o d t 1 ，o f n 一1 ，且- f ， o ，n 一1 ，有z i ，y ，成立，则a 是b 的邻结点，b 是a 的邻结点。例如，图1 1 中的是二维带环网络。 4 n 维带环网络的特例k a r vn b e 网络 如果n 维带环网络中的每一维结点总数都相同且均为k ，我们就称该带环网络 为k a r y n c i l b e 网络。图1 1 中的( b ) 是5 - a r y 2 c u b c 结构。 5 k - a r yn h y p e r c i i b e 网络 此网络中每一维上的结点总数均为k ，结点以n 维坐标 。，d ，d ：。以一。) 来标识， 其中d 。( 0 s f 兰忍一1 ) 为k 进制数。对于结点a ( ， 。一。) 和结点b ( ，而。一，) ，若 存在i ，使得葺一y 。一1 ，0 f s 刀一1 ，其中1 为k 进制数中的1 ，同时有- f ， o sjs n 一1 ，有x ，- ) ，j 成立，则称a 和b 相邻，b 和a 相邻。图1 1 中的( c ) 是2 一a r y 4 h y p e r c i l b e 网络。 ( a ) 5 a r y2 - m e s h 中叶呻叶 每 中叶呻叶叶 命 奄 命叶叶呻 6令6 岁 ( c ) 2 a r y4 h y p e r c u b o 5 - a r y 2 d b e 图1 1 直连网络中的典型拓扑示意图 其中，m e s h 结构简单，实现容易，但结构不对称，中间结点容易阻塞，应 用较少；t 0 n l s 和h y p e 蜘b e 网络都是对称网络，能将流量分布的比较均匀，应 用较为广泛，如a v l c i 公司推出的太比特路由器就采用了3 d t o s 交换结构1 4 】， 第l 章绪论 而p l u r i s 则采用了超立方体( h y p e r c u b e ) 结构1 5 l 。 1 1 2 直连网路性能指标 评价网络性能的最重要的指标是平均时延( 服务的质量) 和吞吐量( 单位时 间内服务的数量) 。一个网络，平均时延越低，网络吞吐越高，说明该网络性能 越好。 为了定量的描述直连网络拓扑结构对网络性能的影响程度，有必要定义一些 评价指标，常用指标如下： 1 网络的规模 在直连网络中，网络的总结点数和总链路数统称为网络的规模，它反映了网 络的大小和实现成本。 2 距离和直径 网络中，两个结点间的距离指的是这两结点间沿最短路径通信所经过的边 数，两网络中两结点间距离的最大值称为该网络的直径，网络中所有两结点间距 离的平均值称为该网络的平均距离。网络的直径决定了网络的端到端时延的最大 值，而网络的平均距离则决定了网络的平均端到端时延。 3 度 在网络拓扑图中，结点所直接相连的结点数称为该结点的度，换句话说，_ = 个结点的邻接结点总数即为该结点的度。在单向通信的情况下，进入结点的通道 数称为该结点的入度，从结点出来的通道数称为该结点的出度。该结点的度就是 该结点的入度和出度之和，而网络的度则是网络中各结点度的最大值。结点的度 反映了结点所需的】o 端口数，反映了结点的成本。 4 对分宽度( b i s e c t i o nw i d l h ) 和对分带宽( b i s e c t i o nb 卸d w i d t h ) 对分宽度是指将网络分成相等( 或近似相等) 的两部分时所需去掉的信道的最 小数目，而对分带宽则为对分宽度和信道带宽的乘积。对分宽度是衡量网络可靠 性的一个重要参数；而对分带宽则是衡量网络吞吐量的一个重要参数。 5 规则性( r e g u i a r i t y ) 和对称性( s y m m e t 功 规则性是指网络结点的连接方式有一个确定统一的规则，如所有结点都具有 相等的邻结点总数等。对称性描述的是结点在图中的地位问题。在全对称网络中， 每个结点在图中的地位是等同的；局部对称网络中，只有部分结点在几何位置上 和其余部分结点对称。 6 路径多样性( p a t hd i v e r s i t y ) 路径多样性是指网络中任意两结点问都具有多条不相交的通信路径。如果一 个网络具有路径多样性，那么从物理上说，该网络就具有了容错和负载均衡能力。 7 可伸展性( e x p a n s j b i l i t y ) 和可扩展性( e x t e n s i b i l i t y ) 互连网络中的路由算法研究 可伸展性指的是，在保持网络拓扑结构不变的情况下，网络增加结点的能力； 而网络的可扩展性指的是在保持网络的拓扑结构不变并且不降低原有网络性能的 情况下，网络扩充结点的能力。 表1 1 几种常见的直连网络拓扑结构的性能参数 网络拓扑结点总数链路总数网络的 网络直径 对分宽是否 度度对称 2 一d m e s h尽x 瓜 2 ( j v 一j v ) 4 2 ( 一1 )瓜 否 3 d m e s h瓶x 辐x 瓶 3 ( 一剖2 ) 6 3 ( 柯一1 ) n 2否 2 d 1 0 n i s瓜x 瓜 2 4 心j | 越 2 万是 3 d t o m瓶x 抵x 瓶 3 6 nf 2 j 2 2是 2 a r vnn 2 | 4n | 2n | 2n | 2 是 h y p e r c u b e ( 总维数j v 2 ) 表1 1 给出了几种常见的直连网络拓扑结构的性能参数。从表中我们可以看 出，在相同结点数的情况下，t o 邝s 的网络直径比m e s h 小，有着较小的网络时延； 对分宽度比m e s h 大，网络抗毁性较好；但需要的链路数比m e s h 多，网络成本较 高。此外，t o m s 和h y p c r c u b e 是对称结构，而m e s h 不具有对称结构，靠近网络 中心的信道要比周边信道承受更大的通信密度，网络性能较差，但m e s h 结构简单， 扩展性好，在相同的对分宽度下能提供更高的链路带宽。这三种结构中，h y p e r c i l b e 具有最大的度，路径冗余度大，可靠性高；但其对分宽度较大，相同的吞吐率下 链路带宽低于其它网络拓扑的链路带宽。 一1 2直连网络中路由算法研究 1 2 1 常见交换机制 交换机制定义了数据包通过交换结构的方式，而路由算法决定了源宿结点间 的通信路径。路由算法不能脱离交换机制来设计，它们都对网络的性能有着非常 重要的影响。 常用的交换机制有电路交换、存储转发交换( 也称分组交换) 、虫孔交换【6 l ， 虚切通交换川及混合交换如管道式电路交换【8 】等。 1 电路交换( c i r c l l i ts w i t c h i n 酌 电路交换源自电信网络中的电话交换方式：消息在传输之前先建立一条源宿结 点问的物理路径；消息传输期间，消息独占该路径；最后由消息的最后几位( 标 志着消息的传输结束) 释放掉该路径。因为消息传输时独占整个物理路径，因而 不会阻塞，所以该交换机制可靠性高，无抖动，能够很好的保证服务质量( 即o o s ， 第1 章绪论 5 q u a l i t yo fs e r v i c e ) ，适用于一次需要传输大量数据或要求保证q o s 的场合；另一 方面由于消息传输期间对物理链路的独占性，阻塞了其它消息的请求，网络链路 利用率低，因此，现在直连网络中已很少采用这种机制。 2 存储转发交换( s t o r ea n df 0 刑a f ds w i t c h i n 曲 为了克服电路交换链路利用率低的弊端，人们提出了存储转发交换。该交换机 制在源结点将消息分割成多个分组，每个分组都携带有路由信息，能独立选路； 中间结点收到分组后，先把整个分组都接收下来放在缓冲区，然后读分组的首部 查路由表，如果该分组的目的地不是本结点则将分组给转发出去，否则直接将分 组交给上层处理，这就是所谓的“存储转发”。 可以看出，该交换机制动态分配传输带宽( 只在传输分组时才分配) ，因此通 信线路的利用率大大提高，适用于突发性业务。此外，因为每个分组都能独立路 由，所以能绕开网络中的故障和拥塞区域，提高网络性能。但该机制也存在缺陷， 它需要将消息切割成分组，这将会增加系统开销；每个分组都携带有路由消息， 增加了网络开销；每个分组都单独路由，如果它们到达目的地的顺序与源结点发 送顺序不一致，则在目的地需要将这些分组重新组装成原来的消息，增加了系统 开销；此外，源宿结点的端到端时延与源宿结点间的距离成正比，网络的最大通 信时延将随网络直径的增长而增长，因此该交换机制不适合规模较大的网络结构。 3 虫孔交换( w b 咖h o l es w i t c h i n 曲 该机制模拟了虫子前进的行为，虫子的头部先行探路，然后身体的其余部分紧 跟着头部前进。具体实现是系统迸一步将分组切割成更小的片( n i t ) ，由头片携带路 由信息先行找路，后面的数据片和尾片以流水线的方式紧随头片直至目的地。此 交换机制中，每个结点只有一个片大小的缓存，用于实现流水线传输。 该机制下的通信时延对距离不敏感，因而适用于大规模网络。但是一旦头片受 阻，所有后续片只能就地缓存，即被迫停留在其他结点的缓存中，这又进一步堵 塞了其他片的传输，造成网络性能下降，因此虫孔交换机制下的搠塞控制值得深 入研究。 ， 4 虚切通交换( v i n u a lc l l t t h r o u g hs w i t c h i n g ) 直连网络中的虚切通交换机制类似虫孔交换，唯一不同的是结点缓存被扩充为 1 个或几个分组的大小。这样，当头片受阻时，后续片可以继续前进至头片受阻的 结点，从而减少网络拥塞，提高网络的吞吐。 5 管道式电路交换机制( p i p e l j n e dc i r c u j ts w i t c h i n g ) 管道式电路交换机制是综合通信网的电路交换和虫孔交换提出的，类似因特网 中的虚电路交换机制。管道式电路交换机制下，分组仍被切割成片，由头片负责 建立一条源宿结点自j 的通信路径，并且在头片到达目的地发回反馈片之前，源结 6 互连网络中的路由算法研究 点中的数据片和尾片都不得发送。管道式电路交换机制通过这种方式来保证数据 的可靠传输，适用于对数据传输质量要求高的业务。 可以看出，虚切通交换引入了流水式消息传输，而虫孔交换使用细粒度的流水 线，从而进一步降低了对缓冲器的要求。在分组交换和虚切通交换中，消息完全 缓冲在结点内，从而消息消耗的网络带宽与网络负载成正比；在虫孔交换中，被 阻塞的消息可能占用多个结点的缓存和多条信道，影响其他消息前进，从而加重 阻塞，所以当网络饱和时，网络拥塞会很严重，平均时延也会很大。虚切通交换 在低负载下与虫孔交换相似，在高负载下链路竞争迫使整个消息缓存在每个结点， 近似于分组交换。综上所述。虚切通交换性能较好，对负载的适应性较为灵活， 我们在后续的算法仿真中，直连网络的交换机制采用的均是虚切通交换。 1 2 2 路由算法设计 路由算法规定了分组从源结点到目的地所走的路径。一个好的路由算法，能 在网络重载下提高网络的吞吐，在网络轻载下降低网络平均时延，对网络的性能 有着举足轻重的影响。这里的路由算法包含两部分，路由协议和路由策略，其中 路由协议用于收集网络信息以形成路由表，路由策略规定了查询路由表选择下一 结点的方式。另外，流量控制决定了分组使用结点缓存的方式，一般是和路由算 法绑定在一起。下面讨论的路由算法偏重于路由策略。 直连网络中现有的路由算法( 我们主要讨论单播路由) ，按路由的适应性程度 可分为确定性路由算法和适应性路由算法，按路径长度可分为最短路径路由算法 和非晟短路径路由算法。其中，确定性路由中，源宿结点间的通信路径是由源结 点和目的结点的相对位置所决定的，即对于同一对源宿结点，所有的消息使用的 都是同一条路径。这种路由算法简单易实现，缺点是没有容错和负载均衡能力， 典型的有维序算法1 9 】，现已被很多商用产品所采纳，如i t i t e lp 盯a 9 0 i l ，m 1 1 r j m a c h i n e 及c m vt 3 d 等。而适应性路由算法则相反，为同一对源宿结点提供了多条可选路 径，消息可以根据网络状态来选择某一条路径，能绕过网络中的故障区域和拥塞 区域。其中适应性算法进一步可分为完全适应性算法( 算法可以使用全部的可用 路径) 和部分自适应算法( 算法只能使用有限的可选路径) ，d u a t o 算法i l o 】是完全 适应性算法，转弯模型【l l l 是典型的部分适应性算法。最短路由算法只允许分组走 源宿结点间的最短路径，而非最短路由算法除了使用最短路径外还考虑使用非最 短路径。 路由算法对网络性能有着非常重要的影响，一个好的路由算法能提高网络吞 吐，降低网络的平均时延。我们在设计路由算法中应该考虑多种因素。其中一些 基本要求如下： 第】章绪论 7 1 连通性：要求算法能给出网络中任意两结点间的路径，即保证网络中任两 结点间都是可达的。 2 无饥饿：算法应能保证不会有分组一直在等待调度，即永远得不到输出。 3 无活锁：算法能保证分组不会永远在网络中游荡，永远到达不了目的地。 4 无死锁：保证分组不被永久阻塞。 此外，还有一些可选因素： 1 ) 适应性：算法提供替代路径的能力。 容错性：算法能保证所有分组都能绕过网络故障区域到达目的地。 3 ) 负载均衡：算法能将流量分布地比较均匀，能充分利用网络中各种资源， 如缓存资源和链路资源等，避免出现一些资源匮乏而另一些资源富余的情 况。 4 ) 服务质量保证：一些业务如语音和图像传输等，对服务质量( o o s ，q u a l i t y o f s e i c e l 有着较高的要求。在设计这些业务的算法时除了上述普通因素，还 要考虑对应的o o s 参数如链路剩余带宽、包丢失率、时延抖动等。 通常一个算法是侧重于某一个可选因素，不存在面面俱到的算法。而我们研 究的算法则侧重于负载均衡。下面我们将针对算法中的饥饿、活锁和死锁的问题 进行详细的讨论。 1 2 3 路由算法中的饥饿，活锁与死锁 如前所述，饥饿指的是分组一直在等待调度输出，却永远得不到这个机会。 一般是由于调度策略不公平引起的，采用公平的调度策略如轮转调度，就可以避 免这个问题。 而活锁指的是分组的路径中出现了环，而分组不停地绕环路由，永远摆脱不 了这个环，即永远到达不了目的地。非最短路由算法可能会存在这个问题；而最 短路由不会出现这种情况。现有对活锁的处理方法有两种，一种是主动的( a c t i v e ) ， 即在分组头部增加一个域以记录到目前为止所访问的全部结点的集合，每次路由 时选择不在此集合中的邻结点来路由，这种方式能彻底避免活锁的出现，不过开 销较大：另一种是被动的( p a s s i v e ) ，通常是规定分组的最大生存期或允许的最多跳 数，当分组的生存期或可走的跳数耗尽时，无论该分组是否到达目的地，都要将 此分组销毁，该方法开销较小，但不能彻底地去除活锁，只能减少活锁发生的机 会。 死锁发生的原因是网络中出现了对资源的环形请求链，请求链中的所有分组 都因请求己占资源的使用而被阻塞，无法向前路由。我们以二维网络为例来详细 介绍一下这种环形资源请求关系。二维网络中存在的环形请求依赖只有两种情况： 顺时针方向的环形依赖( 图1 2 中的( a ) ) 和逆时针方向的环形请求( 图1 2 中的( b ) ) 。 8 互连网络中的路由算法研究 ( a ) 顺时针方向 ( b ) 逆时针方向 图1 2 二维网络中的死锁环 图1 2 中结点端口以结点号加端口链路方向代码来命名，方向的标识同平面 图，即上北( n ) 下南( s ) ，左西( w ) 右东( e ) ，例如1 n 代表的是结点1 的北端口。其 中，每个端口都只有一个缓冲区。下面我们以顺时针方向的环形依赖为例来详细 介绍一下死锁的形成。图1 2 ( a ) 中，1 e 端口缓冲区中有一分组a ，申请2 s 端口的 已被分组b 占领的缓冲区，分组a 等待；分组b 同时申请3 w 端口的已被分组c 占领的缓冲区，分组b 等待；分组c 同时又申请4 n 端口的己被分组d 占领的缓 第1 章绪论 9 冲区，分组c 等待：分组d 申请被分组a 占领的1 e 缓存，被迫等待，如此形成 了端口缓存的环形请求，每个分组都无法前进。 形成死锁的必要条件有四个：( 1 ) 对资源的互斥请求，即在某一时刻，只能有 一个分组在使用某一资源。( 2 ) 分组占有资源并继续申请其它资源。( 3 ) 分组对资源 的请求成为环行链。( 4 ) 分组所占资源不能被剥夺，只能分组自己释放。 上述四个必要条件是形成死锁的表面原因，而死锁发生的根本原因是分组在 竞争有限的资源。如果网络拥有无限资源，那么每个分组的请求都能够满足，就 不会出现分组被阻塞的情况，也就不会有死锁的发生。 下面，我们讨论一下死锁的解决办法： l 死锁的预防 破坏死锁形成的必要条件。其中( 1 ) 和( 4 ) 是无法破除的。要破除( 2 ) ，分组在发 送之前必须申请到所有的所需资源并予以保留，典型的铡子是允许回溯的各种基 于电路交换的路由算法。破除( 3 ) ，一般是对网络中的资源进行编号排序，并规定 只能按照升序( 或降序) 的方式来申请这些资源，这方面的典型算法有维序算法 和跳步算法1 1 2 l 。其中x y 路由算法( 维序算法的一种) ，对路由维度进行排序，规 定分组先走x 维，在x 维上到达目的地，再走y 维，在y 维上到达目的地即最终 的目的地，以此来防止死锁的发生。而正跳步算法( 跳步算法中最简单的一种) ， 对结点缓存资源进行分类编号排序，分组在源结点被放入0 类缓存器，而当分组 从结点a 的i 类缓存器一个跳步到结点b 时，该分组将被放入结点b 的i + 1 类缓 存器。 这种防止死锁的方式实现简单，但对路由作了诸多限制，无法充分利用网络 资源，因而资源利用率不高。 2 死锁的避免 死锁避免不对资源的使用做预先的限制，只在分配资源时避免死锁环的出现， 常见做法是限制路由转弯。这方面的典型算法有维序算法和转弯模型。维序算法 按照既定的维度顺序来路由分组，只有当前维度上己到达目的地才可以进行下一 维度上的路由。图1 3 给出了x y 路由所允许的转弯，其中水平方向代表x 方向， 垂直方向代表y 方向。 厂。i ： ：- j 图1 3x y 路由所允许的转弯( 实线) ；一 ! - - _ l 互连网络中的路由算法研究 其实没必要限制这么多转弯就可以避免死锁环的出现。转弯模型1 1 1 1 只禁止两 个转弯，并由此提出了三种路由算法即西优先路由算法、北最后路由算法和负优 先路由算法，图1 4 给出了这三种算法所允许的路由转弯，其中方向的标识同平面 图，即上北下南，左西右东。 厂。；， l _ jlj 口 这种方式通过限制路由方向的“转向”来避免信道的环形依赖，但同时降低 了算法的路由自由度，网络资源没有得到充分利用。 3 增加资源 从根本上来解决死锁问题。一般是增加缓存资源，即给每条物理链路分配多 个缓存队列( 通常这些队列被称为虚信道1 3 9 j ) ，这些队列分时使用同一条物理链路， 以此来减少成环的机会。图1 5 给出了使用虚信道来避免死锁的方式。 图1 5 中，每个端口对应着两个缓存队列，图中阴影部分代表有分组。存在如 下的缓存申请顺序：2 w 端口a 队列中的分组b 申请已满的1 s 端口缓冲区，1 s 端 口的a 缓冲区的分组a 申请已满的4 e 端口缓存，4 e 端口a 缓存中的分组d 申请 已满的3 n 端口缓存，3 n 端口a 队列的分组c 申请2 w 端口缓存，发现b 队列是 空闲的，申请成功，前进至结点2 中，释放所占结点3 缓存，从而分组d 、a 、b 都可以l j 进。当然，如果不对分组申请资源作些限制，只是这样单纯增加缓存资 源，只能减少死锁发生的概率，不能绝对避免死锁。例如，如果图1 5 中2 w 端口 的b 队列也是满的，按照前述的资源申请顺序就会发生死锁。 一 广l 第l 章绪论 n o d e 4 图1 5 使用虚信道来避免死锁 n o d e3 t o n l s 网络中的单维上存在环形链路，无法通过限制转弯来避免这种死锁环的 产生，一般采用虚信道方式来解决单维上的环形死锁。d _ i i a t o 算法就采用了这种方 式来避免单维上的死锁。下面我们以单维上的逆时针方向的资源申请为例，探讨 一下d i i a t o 算法的具体解决办法。 n o d eon o d e l d e 2 n 0 d e3 n o d e 4 图1 6d u a l 0 算法单维死锁环的解 图1 6 中，每条物理链路对应两个缓存队列，即两条虚信道，编号分别为0 和 1 。d u a l o 算法对虚信道的使用做了限制，以彻底消除死锁环的发生。其中，逆时 针方向的虚信道使用规则如下：如果分组在当前维上未经过环回信道( 连接某维 上第一个结点和最后一个结点的信道称为该维的环回信道。) ，并且所在的当前结 点不是该维上最后一个结点时，分组使用o 信道；若分组已使用过环回信道或者 正在进行环回连接( 分组位于该维上最后一个结点) 时，分组选择1 信道。d u a t o 算法是最短路径算法，所以有些虚信道是不需要的，如图中未标注的虚信道在逆 时针资源申请时均未被使用到。 互连网络中的路由算法研究 d u a i o 算法使用上面的策略来避免单维上出现死锁环，对于多维上的死锁环， 则采用了维序路由的方法。此外，为了增加算法的适应性，d u a t o 给每条链路增加 了一条以上的适应性信道，供分组任意使用。算法优先选择适应性虚信道，只有 所有的适应性信道都不可用，才考虑确定性维序信道。至此，可以看出d u a t o 算 法实际上是综合了上面的三种死锁解决方法：死锁预防一规定路由维度顺序，死 锁避免一限制路由转弯，增加资源一增加虚信道。 此外，p d r 算法l ”】对每个无死锁路径赋予一个虚信道，分组路由时只需选择 某一虚信道，然后在此虚信道组成的虚网络中路由至目的地。 使用虚信道不仅可以减少死锁环的发生概率，还有其他两个优点：一是通过 虚信道可以将网络划分成若干个不同平面上的虚网络，虚网络之间不存在环形路 由依赖；另一方面，增加了网络资源，一定程度上减少了网络拥塞的发生。不过， 虚信道技术实现复杂，需要额外的系统开销。 4 死锁恢复 前面的死锁预防算法对网络资源的使用做了诸多限制，资源利用率不高；而 死锁避免算法常常无法作到完全自适应，不利于均衡网络流量。鉴于死锁发生的 概率不是很大，研究者提出了基于死锁恢复策略的自适应算法，即不对路由作任 何限制，而采用一定的机制检测出死锁的存在，然后再解除。 典型的死锁恢复算法有c r 算法【1 4 j ，d j s h a 算法1 1 5 j 和基于软件的恢复算法【1 6 1 。 其中c r 算法利用虫孔路由机制下分组的“无压”特性来判断头片是否已到达目的 地，即假设源宿结点间的距离为n ，则源结点在发送第n + 1 片时就可以判断分组的 头片已到达目的地；若头片未到达目的地，说明头片被阻塞，则源结点拆除已建 立的路径，并销毁所有己发送分组，等待一段时间再重发。 与基于消极策略( 即丢弃死锁分组然后重传) 的c r 算法不同，d j s h a 采用了 一种积极的策略：它首先通过超时机制来检测出死锁( 如果一个分组超时不能发 送，则被判定为死锁分组。) ；死锁发生时并不简单地销毁死锁分组然后重传，而 是将死锁分组发往由各结点的死锁缓存所形成的死锁恢复路径上来解除死锁。 基于软件的恢复算法也是一种积极的恢复算法：死锁发生后，将死锁分组先 发往本结点高层，隔段时间再重新注入网络。此外，它还使用了限制注入机制来 防止死锁的发生，即当处于忙状态的输出虚信道数超过一个给定阀值时，结点停 止向网络中注入新分组；它通过测量分组所需求的信道状态来检测死锁，如果分 组所能使用的全部输出虚信道都有被阻塞分组时，则判定该分组为死锁分组。 现有的很多死锁检测机制都是基于超时机制的，这种策略中的时间门限由于 受分组长度的影响而不容易确定，并且存在死锁分组同步恢复会引起恢复过度的 问题。q d a r 旧算法采用了一种综合考虑分组的等待发送时间和链路队长的死锁 第1 章绪论 检测策略，如果某队列队长超过设定的队长门限值，则检测该队列队头分组，若 该分组的等待发送时间超过给定的时间门限值，则认为该分组发生死锁。 死锁恢复能最大程度地开发算法的适应度，但实现复杂，系统开销大。 1 3 论文内容及结构 互连网络是种应用广泛的网络，从电话网、多处理器系统、并行计算机系 统到路由器交换机都有应用。而作为互连网络结构之的直连网络，以其简单的 结构、良好的扩展性及便于实现分布式管理等，正被引入到新代的大容量核心 路由器中。 路由算法设计一直是直连网络研究的热点，本章从拓扑结构、性能参数，交 换机制这三个方面给出直连网络中路由算法设计的基础，并给出了直连网络中路 由算法的分类和设计原则。 本文的内容及结构安排如下：第二章对直连网络中现有负载均衡算法进行了 分析和比较；第三章作者结合气体扩散现象提出了一种新的负载均衡路由算法 g d ( g a sd i f 知s i o nb 笛e d o u f i n g a l g o f i t h m ) ；第四章对生物智能在路由中的应用进行 了深入的研究，并提出了直连网络中的智能路由算法f o a ( f o 九a r d o n l ya g c n t r o u t i n ga l g o r i t h m ) ：第五章总结全文。 第2 章现有负载均衡路由算法研究 第2 章现有负载均衡路由算法研究 2 1直连网络中的负载均衡问题 直连网络中业务的不均衡性要求路由算法应具有均衡负载的能力，能使得网 络中的各种资源( 包括缓存资源与链路资源等) 得到充分利用。对于一个网络来 说时延特性和吞吐量是其两个最重要的技术指标。其中，时延特性反映了网络 传输数据的快速性，而吞吐量则反映了网络传输能力的