（计算机软件与理论专业论文）kary+ncube网络中的死锁及负载均衡研究.pdf

摘要 摘要 作为互连网络中一种流行的拓扑网络，k - a r yn c u b e 网络目前面临着多应用、 多业务以及业务分布不均等问题，这就要求设计的路由算法要有较强的负载均衡 能力，以及所采用的死锁解决算法具有适应各种网络业务的能力。 当前相关技术都没有很好地解决这些问题，如负载均衡路由算法存在着资源 利用失衡等问题；死锁方面则存在着死锁检测时误检率过高等问题。基于此，本 文的主要工作和贡献包括如下两方面： 1 在研究现有死锁技术的基础上，提出了基于环的死锁检测路由算法( c y c l e b a s e dd e a d l o c kd e t e c t i o nr o u t i n ga l g o r i t h m ，c d d ) 。与传统检测算法仅采用超时机 制不同，c d d 从信道依赖环一死锁形成的原因入手对死锁进行检测。根据k a r y n - c u b e 网络拓扑特性，c d d 分别检测同维环中形成的死锁与不同维( 即异维) 环中 形成的死锁。在同维中c d d 运用流控策略，即分组进入当前所在信道前，该信道 的缓存剩余量大小进行检测：在异维中c d d 则通过分组的转向来检测。c d d 继 而对那些初步检测判定为死锁的分组，分别根据其所申请的所有输出信道处于忙 状态的时间间隔做最后的检测。本文运用o p n e t 仿真软件对其进行仿真，结果表 明，c d d 与现有s o f t - b a s e d 死锁检测算法相比，具有较低的死锁误检率，较低的 时间门限值敏感性等。 2 针对现有负载均衡路由算法存在的问题，提出了跨区域的适应性路由算法 ( q u a d r a n tc r o s s i n gr o u t i n ga l g o r i t h m ，q c r ) 。q c r 按照分组源、目的结点相对 位置将网络划分路由区域，并给予这些区域不同的权重，同时设定跨区域规则， 允许分组根据网络负载状态，跨区域路由。这就提高了分组路由的适应性，并使 网络的负载更均衡。网络的负载程度由输出端口等待分组请求的时间间隔的大小 决定。运用o p n e t 对q c r 在不同流量模式下进行仿真，结果表明，相比已有同 类算法，如维序算法，d u a t o 及g a l 等算法，q c r 的性能优于这些传统路由算法。 关键词：k - a r yn - c u b e 网络路由算法负载均衡死锁 a b s t r a c t a b s t r a c t a sap o p u l a rt o p o l o g yo fi n t e r c o n n e c t i o nn e t w o r k ，k - a r yn - c u b eh a sf a c e dm a n y p r o b l e m sc u r r e n t l y , s u c ha sm u l t i - a p p l i c a t i o n ，m u l t i - b u s i n e s sa n dt h ei m b a l a n c eo f t r a f f i cd i s t r i b u t i o n ，w h i c hr e q u i r e st h er o u t i n ga l g o r i t h m st ob el o a db a l a n c e da n dt h e d e a d l o c k - f r e ea l g o r i t h m st ob ea d a p t i v eu n d e rv a r i o u st r a f f i cm o d e s c u r r e n tt e c h n o l o g i e ss o l v et h e s ep r o b l e m si n a d e q u a t e l y , s u c ha st h ei m b a l a n c eo f r e s o u r c eu t i l i z i n gi nl o a db a l a n c i n gr o u t i n ga l g o r i t h m sa n dt o oh i g hr a t eo ff a l s e d e a d l o c kd e t e c t i o ni np r e v i o u sd e a d l o c kd e t e c t i o na l g o r i t h m s t os o l v e t h e s ep r o b l e m s ， t w on e w a l g o r i t h m sa r ep r e s e n t e di nt h i sp a p e r b a s e do no ft h ea n a l y s i so ft h ee x i s t i n gd e a d l o c kt e c h n o l o g i e s ，c d d ( c y c l eb a s e d d e a d l o c kd e t e c t i o nr o u t i n ga l g o r i t h m ) i sp r o p o s e df i r s t l y d i f f e r e n tf r o mt r a d i t i o n a l d e a d l o c kd e t e c t i o nm e c h a n i s mo ft i m e o u t ，c d du s e st h ec o n d i t i o n so fc y c l i c d e p e n d e n c yt od e t e c td e a d l o c kp a c k e t s b a s e do nt h ef e a t u r e so ft o p o l o g yo fk - a r y n - c u b en e t w o r k s ，t h ed e t e c t i o ni sd i v i d e di n t od e a d l o c kd e t e c t i o ni nt h es a m ed i m e n s i o n a n dd e a d l o c kd e t e c t i o ni nt h ed i f f e r e n td i m e n s i o n i nt h es a m ed i m e n s i o nd e t e c t i o n , c d du t i l i z e st h es t r a t e g yo ff l o wc o n t r o l ，i e t h ed e a d l o c ki sd e t e c t e da c c o r d i n gt ot h e r e m a i n e db u f f e r si nt h ec h a n n e l sb e f o r et h ep a c k e t sc o m ei n t ot h e s ec h a n n e l s ；m i l ei n d i f f e r e n td i m e n s i o n s ，d e a d l o c ki sd e t e c t e db yt h et u r n i n go ft h ep a c k e t s t h e n ，c d d u s e st h ei n t e r v a lo fb u s yt i m eo fa l lt h eo u t p u tc h a n n e l st h e s ep a c k e t sa p p l y i n gf o rt h e f i n a ld e t e c t i o n s e c o n d l y , i nv i e wo fp r o b l e m so ft h ee x i s t i n gl o a db a l a n c i n gr o u t i n ga l g o r i t h m s ，a n e w q u a d r a n tc r o s s i n gr o u t i n g ( q c r ) a l g o r i t h mi sp r o p o s e d a c c o r d i n gt os o u r c ea n d d e s t i n a t i o nn o d eo fe a c hp a c k e t ，n e t w o r ki sd i v i d e di n t os e v e r a lq u a d r a n t s 谢t l lv a r i o u s w e i g h t s q c rs e t sq u a d r a n tc r o s s i n gr u l e sa n da l l o w sp a c k e t st oc r o s sq u a d r a n t sb a s e d o nt h en e t w o r ks t a t e ，w h i c hm a k e st r a f f i cd i s t r i b u t i o nm o r eb a l a n c e d n e t w o r ks t a t ei s d e t e r m i n e db yt h ei n t e r v a lb e t w e e nt h el a s tt w or e q u e s t st ot h es a m eo u t p u t f i n a l l y , p e r f o r m a n c eo ft h ep r o p o s e dr o u t i n ga l g o r i t h m si se v a l u a t e db yo p n e t u n d e rv a r i o u st r a f f i cm o d e sa n dc o m p a r i s o n s 、i t l lt h ee x i s t i n ga l g o r i t h m s ( c d dv s s o f t b a s e d ，q c rv s d i m e n s i o no r d e rr o u t i n ga l g o r i t h m ，d u a t o ，a n do a l ) a r em a d e t h er e s u l t ss h o wt h a tc d dh a sl o w e rr a t eo ff a l s ed e a d l o c kd e t e c t i o n ，l e s ss e n s i t i v i t yo f t h et i m e - t h r e s h o l da n dq c ra c h i e v e sb e a e rp e r f o r m a n c e k e y w o r d s ：k - a r yn - - c u b en e t w o r kr o u t i n ga l g o r i t h m l o a db a l a n c e d e a d l o c k 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签 j 再褫 i 一、 0日迎丛q 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文 在解密后遵守此规定) 本学位论文属于保密，在一年解密后适用本授权书 本人签名： 导师签名： 日期 日期 第一章绪论 第一章绪论 1 1 研究背景及价值 作为一种流行的拓扑网络，互连网络( i n t e r c o n n e c t i o nn e t w o r k s ) 【l 】已经应用于 电话网，多处理器系统等诸多领域。互连网络按拓扑主要分为直接互连网络( d i r e c t i n t e r c o n n e c t i o nn e t w o r k s ) 和间接互连网络( i n d i r e c ti n t e r c o n n e c t i o nn e t w o r k ) 两种主要 的拓扑形式。其中，直接互连网络又称为静态网络或者基于路由器的网络( r o u t e r b a s e dn e t w o r k ) 【2 】；间接互连网络又称为动态网络或者基于交叉开关的网络 ( s w i t c h - b a s e dn e t w o r k ) 。直接互连网络中的结点直接相连。每一个结点都是具有 完整路由器功能的自治系统，既可以是业务的源和宿，又可以是转发业务的中间 结点。相对的，间接互连网络是根据连接要求动态实现各种通信模式的互连网络。 在间接互连网络中，单个结点并不具有完整的路由器功能，只能实现源、宿或者 转发中的一种功能。在控制信号的作用下，通过交叉开关的设置来建立输入、输 出端口之间间接的、可变的连接通路。 直接互连网络【1 1 的应用非常广泛，从传统并行计算机系统等，到现在的太比特 交换机路由器【2 】以及无线通信域h o n e y c o m b 网络【3 】 4 】，应用于w d m 网络的t o r u s 结构f 5 】h e x a g o n a l 网络还在化学领域【6 】以及无线a d h o c 网络【7 1 中得到了应用。 k a r yn - c u b e 网络作为直接互连网络中最重要的一种网络拓扑，由于具有拓扑结 构规整，结点度低和在单芯片上容易实现等特点，已得到了广泛的应用。如s g i o r i g i n2 0 0 0 【引，c r a yt 3 d t 9 t 3 e 【1 0 1 ，i p s c 2 t 1 1 1 ，j - m a c h i n e 1 2 1 ，i w a r p l l 3 】，全球第一 台太比特路由器a v i c it s r 【1 4 1 ，以及目前全球运算最快的超级计算机b l u e o e n e l 1 5 1 等都采用了该结构作为系统的互连网络。最近又有研究人员将其引进到 微电子与通信的交叉领域片上网络( n e t w o r k o n c h i p ，n o c ) j 6 】中，用于解决 芯片上因系统芯片( s y s t e m o n c h i p ，s o c ) 中的总线结构带来的时钟同步f 1 7 】等问 题，同时实现网络中各口核( d s p ，p r o c e s s o r ，m e m o r y 等1 之间的高速互连，最终 实现芯片上芯片间通信的高吞吐，低延迟，低能耗，以及占有较少的芯片面积等。 在信息化高速发展的今天，信息技术的先进程度已经成为衡量一个国家的综合 实力一个重要的标准。不论是互连网络的核心路由器，乃至太比特路由器，还是 在国际上刚处于研发阶段，而国内刚处于起步阶段的片上网络等都需要k - a r y n c u b e 网络的技术支撑。可以说，对k a r yn c u b e 网络的研究具有直接的现实价值 和战略意义。 2 k - a r yn c u b e 网络中的死锁及负载均衡研究 1 2k - a r yn c u b e 网络研究基础及现状 k a r yn c u b e 网络的关键技术主要包括拓扑结构的定义，交换机制的研究，路由 算法研究等。而拓扑结构的定义主要是针对k - a r yn - c u b e 网络的网络拓扑外观设计 进行的，力图做到较小的网络直径，较高的对分宽度带宽，以及实现规则形，对 称性，路经多样性等。交换机制主要定义了分组通过交换结构的方式，也即路由 器内部所采用消息传递方式。路由算法主要任务是完成分组的路径选择。 本部分针对k a r yn c u b e 网络的几大关键技术，简要介绍这些技术的理论基础 及研究现状。 1 2 1 拓扑结构 k a r yn c u b e 网络作为直接互连网络的一种，直接进行点与点之间的连接。每个 开关元件固定与一个结点相连，以建立该结点与邻结点之间的连接通路。这种网 络一旦构成就固定不变，控制简单，便于分布式管理，具有良好的可扩展性。 k - a r yn - c u b e 网络以结点集合的方式组织起来，每一个结点都有自己的处理机、 本地存储器，及其它辅助装置。结点之间通过收发信息实现相互通信。网络中每 个结点仅连接少量的其它结点以实现整个网络的互连，而这些结点即为他们的邻 结点。哪些结点为邻结点是由网络的拓扑结构来定义的。与非邻结点进行通信时， 需要通过邻结点来转发消息。为了解决k a r yn c u b e 网络中的路由消息的复杂性问 题，每个结点通常由一个路由控制器进行控制。路由控制器负责控制连接它与本 地装置的本地输入输出通道，和连接它与邻结点路由器的网络输入输出通道。 为便于探讨k a r yn - c u b e 网络各方面的性能，及该网络的拓扑特点，有必要把 k a n ，n c u b e 网络等直接互连网络的网络性能指标参数作一简单介绍。 1 2 1 1 网络性能指标参数 直接互连网络的拓扑结构对网络的性能有很大的影响，主要的性能参数【3 j 有： 1 距离和直径：网络中，任意两结点间沿最短路径通信所经过的边称为这两 个结点间的距离，整个网络距离的平均值为平均距离，记为d 。任意两结 点间距离的最大值称为该网络的直径，记为d 。 2 度：结点度指与结点相连节的边数( 链路或者通道数) ，表示结点所需的i o 端口数，模块化要求结点度保持恒定。根据通道到结点的方向，结点度可 以迸一步表示为：结点度= 入度+ 出度。其中入度表示进入结点的通道数， 出度表示从结点出来的通道数。网络中个结点度的最大值为网络的度。 第一章绪论 3 3 网络规模：在直接互连网络中，网络的总结点数和总边数称为网络的规模， 它反映了网络的大小及实现成本，也反映了该网络所能连接的部件的多少。 4 对分宽度和对分带宽：当网络被切成相等或者相近的子网络时，所要移除 的最小边数称为网络的对分宽度b 。如果每一信道的带宽都为w ，则对分 带宽为b = b w 。对分带宽是衡量一个网络吞吐量的一个重要参数。 5 规则性与对称性：规则性是指网络结点连接所遵循确定的规则。在一个规 则网络中，各结点连接的相邻结点数是相等的。任意两个结点间通信的路 径算法比较规则和简单。规则性还可以用对称性来描述。在全对称性网络 中，每个结点在图中的地位是等同的：局部对称性网络中只有部分结点在 集合位置上和其余部分结点对称。 6 路径多样性：是指网络中任意两点之间都具有多条等价的不相交的路径， 一个具有路径多样性的网络可以提供容错能力和负载均衡能力。 7 连通性：它指的是当网络被分为两个不连通的网络时，所需去除的最小的 边的数量。该参数用来衡量网络发生故障时网络的抗毁性( r e s i l i e n c e ) 。 8 成本：一般由边的数量决定。 9 可扩展性及平面性：可扩展性是指网络拓扑性能保持不变的情况下，扩充 。结点的能力；平面性是指网络拓扑在平面上能否实现。这两个参数直接关 系到直接互连网络实现的经济性和适应性，是设计时必须要考虑的问题。 1 2 1 2 拓扑结构定义 拓扑结构指结点以何种方式互连，及结点间的链路配置。拓扑结构形式化描述 常采用图的形式，将网络结点称为图中的点，连接结点的物理链路称为图中的边。 首先简要介绍一下直接互连网络的一些拓扑结构。直接互连网络除了包含k - a r y n c u b e 结构的网络外，还有m e s h 结构网络，h y p e c u b e 结构网络等。 1 n 维网格g 埘 g 。由k o 毛吒一。个结点组成，毛表示i 维上的结点数。每一个结点由n 维 坐标( x o ，而，毛一。) 唯一标识，其中0 薯也- 1 。若两个结点( x o ，而，一。) 和 ( ，乃，以一1 ) 满足以下条件则称它们是邻结点：存在i 使得t = 以1r x i = 咒其 中，( = 0 ，1 ，( i 1 ) ，( i + 1 ) ，( n - 1 ) ) 。 一般当n = 2 时，将该网格结构称为m e s h 结构。该结构为网格结构中最常用的 拓扑结构之一。下文所提的m e s h 结构均指该类型的结构。 4 k - a r yn c u b e 网络中的死锁及负载均衡研究 图1 1 ( 3 4 ) 网格结构 如图1 1 为3 x 4 的m e s h 结构图。它有两个维度( x 维与y 维) ，在x 维上有4 个结点，在y 维上有3 个结点。其中由结点l ( 1 ，1 ) ，2 ( 1 ，2 ) 的坐标可知，在x 维 上，结点1 的该维坐标大小与结点n ：的大小相同；在y 维上，结点l 的该维坐 标大小比结点2 的该维结点坐标小l 。故知，l 与2 为邻结点。 2 k 元n 网格( k a r y n - m e s h ) g 。 若n 维网格瓯满足= 岛= k 2 = = 吒- l ，则称其为k 元n 网格( k a r y n - m e s h ) 。 其中2 元n 网格常称为超立方结构( h y p e r c u b e ) ，如图1 2 所示为2 x 2 超立方结构。 图1 22 x 2 超立方结构 3 n 维t o r u s 网络q 鳞由k o 向吒一。个结点组成，毛表示i 维上的结点数。每一个结点由n 维 坐标( x o ，x l ，一1 ) 唯一标识，其中0 薯也- 1 。若两个结点( ，x l ，x n i ) 和 ( y 。，m ，y 一) 满足以下条件则称它们是邻结点：存在i 使得薯= ( + 1 ) m o d k 且 t = m 其中，( i = 0 , 1 ，( i 1 ) ，( i + 1 ) ，( n - 1 ) ) 。 由t o r u s 结构定义可知它有取模运算，因而比m e s h 具有更多的边，这些边通常 称为环回信道( w r a p a r o u i l dc h a n n e l s ) 。如图1 3 箭头所指链路为环回信道。这些环 第一章绪论 回信道的作用就是使t o r u s 网络中结点不再有位于中心或者边缘的区别，各结点在 每一维度上均有两个邻结点，故共有2 n 个邻居，亦即t o r u s 网络具有全网对称性。 w r a p a r d u n dc h a n n e l 图1 3 ( 5 x 7 ) 一2 dt o m s 结构 如图1 3 为( 5 x 7 ) 2 dt o r u s 结构，即2 维t o r u s 结构的网络，共有两个维度，其 中一个维度( 一般称之为x 维) 有5 个结点，另一维( 称之为y 维) 有7 个结点。 4 k - a r yn - c u b e ( k 元n 立方) 网络q 。 若n 维t o r u s 网络q 满足= 岛= 也= = 吒- l ，则称其为k - a r yn - c u b e ( k 元n 立方) 网络。 可以看出，k - a r yn c u b e 网络是n 维t o r u s 网络的一种特例，也即当n 维t o m s 网络中的所有维度上的结点数目都一样时，便成为了k a r yn - c u b e 网络；该网络也 有环回信道，在下文中也被称之为同维环。 如图1 4 ，( a ) 图( 3 x 3 ) - 2 dt o r u s ，即3 - a r y2 - c u b e 网络的拓扑结构。该网络共有 两维，每维的结点数目为3 。图( b ) 为3 - a r y3 - c u b e 网络的拓扑结构，也即为 ( 3 x 3 x 3 ) 一3 dt o r u s 结构，共有3 个维度，每个维度都有5 个结点。 国一铲 7 入 一2 圆k 留l钍 i 一1 2 ) 卜 v 甚卜甚卜 上 - c ( o 2 ) k ( a ) 图( 3 3 ) 2 dt o r u s 结构 图( b ) ( 3 x 3 x 3 ) 一3 dt o m s 结构 图1 4 k - a r yn - c u b e 网络拓扑结构 6 k a r yn c u b e 网络中的死锁及负载均衡研究 在k - a r yn - c u b e 网络基础上，最近还有一些人提出一些类似的结构，如d i a g o n a l t o r u s 1 羽，d u a l t o r u s 1 9 1 ，e 2 d t o r u s l 2 0 】以及r e c u r s i v ed i a g o n a lt o r u s 【2 l 】等。 很明显，理想的拓扑结构是全连接结构，即每个结点都与网络中的所有其它结 点相邻，所以消息传递不用经过任何中间结点。网络规模为n 的全连接结构中， 每个路由器需要( n 1 ) 条链路，当网络规模较大时，网络的成本非常的高。另外， 一个结点物理连接的数量由于受到硬件技术的限制也可能很大。 这些工程和可扩展性方面的困难排除了使用全连接的实用性。为此研究人员提 出并研究了大量的网络拓扑结构，目标是在网络成本和网络性能方面找到一种平 衡。在表1 1 中汇总了一些直接互连网络拓扑结构的重要特性以及它们之间的比 较，其中为结点数，刀为维度数目。 各种网络结构各有特点与优势，当在高性能与价格做适当权衡时，具有较好拓 扑结构性( 如结点度低、直径较小等) 、算法容易实现以及容错性好的网络是较合 适的选择。因此，具有较好的扩展性，较低的网络直径等性能的k a r yn c u b e 网络 正是本文研究所选择的拓扑结构。 表1 1 直接互连网络拓扑性能参数表 网络 结点度直径链路数目对分带宽对称性网络规模和说 类型 dd，b明 线形阵列2一1 一1 1 非n 个 结点 环形网2 l - 2 j n 2 是 n 今 结点 全连接一1 l 是 个结点 n ( l n 一1 ) 2 ( n 2 ) 2 二叉树3 2 ( o o g n 一1 ) n ll非树高 o o g n q 非 2 一d m e s h4 2 ( 万一1 )2 ( n 一打)捆( 瓶瓶) 个结点 2 - d t o r u s4 2 晦2 j 2 是 2 厨( 届届) 个结点 星型n 一1 2 一1 l n 2 j 非 n 个结点 超立方 刀拧 2 n 2是n = 2 n k a r y n - 1n - i n c u b e网2 n 2 n n 2 2 n ， 是 个结点 络 第一章绪论 7 1 2 2 交换机制 交换机制决定着分组从源结点到目的结点之间路由时，通过各结点交换结构的 方式，直接影响着网络的性能，以及路由算法的设计。它同时还决定了内部开关 连接路由器的输入和输出端口的时机和方式等。 k - a r yn - c u b e 网络中比较常见的交换机制有电路交换( c i r c u i ts w i t c h i n g ，c s ) 存储转发交换( s t o r ea n df o r w a r ds w i t c h i n g ，s & f ) 虫孔交换( w o r m h o l es w i t c h i n g ， w s ) 2 2 j ，虚切通交换( v i r t u a lc u tt h o u g h ，v c t ) 等【2 3 1 。还有一些人提出了比较 有特点的交换方式，如管道式电路交换( p i p e l i n e dc i r c u i ts w i t c h i n g ，p c s ) 2 4 1 ，以及 将虫孔交换与虚切通交换相结合的交换方式【2 5 】等各种交换方式。 、 1 电路交换( c i r c u i ts w i t c h i n g ) 该交换方式是早期采用的一种交换方式。它要求每次传输消息前都要在源结点 与目的结点之间先建立一条专用链路。链路的建立通过向网络注入一个头片( h e a d f l i t ) ，利用该头片探测网络来完成。首先，源结点向网络中注入一个头片，该头片 一边朝目的结点前进一边建立链路。若头片在中间结点受阻，它便产生一个释放 片( r e l e a s ef l i t ) 并发回源结点，同时释放已占链路。一旦头片到达目的结点，等它便产 生一个应答片( a c k n o w l e d g e m e n tf l i t ) 并发回源结点。当源结点收到应答片时，源结 点便知链路已成功建立并开始发送数据片( d a t af l i t ) ，传输结束后释放所占用链路。 电路交换中，每次传输数据前都要在源结点与目的结点之间建立一条专用的通 信线路。一旦进入数据传输阶段，消息就不会阻塞。因此电路交换的优点是可靠 性高，几乎没有抖动，能够很好的保证服务质量( q u a l i t yo f s e r v i c e ，q o s ) 。同时， 当消息传送次数不是很频繁且消息很长，即消息传输时间远远大于路径建立时间 的时候，电路交换也是有优势的。但是由于它的独占性，链路带宽得不到复用， 有可能阻塞其它的消息，所以链路利用率低。因此，在数据网络中一般不考虑采 用电路交换的方式。 2 存储转发交换( s t o r ea n df o r w a r ds w t i c h i n g ) 在电路切换中，只有电路建立后才开始进行整个消息的传输。因此该交换中对 消息进行固定带宽分配的方式，严重影响了网络资源( 链路等) 的利用率，为此，储 转发交换相继被提出了。该交换机制将消息进行切割，分割为各个较小的分组， 因此也经常将这种交换称之为分组交换( p a c k e ts w i t c h i n g ) 。每个分组的前几个字 节包含路由和控制信息，可以独立从源结点到目的结点独立路由，绕开各种故障 或者拥塞区域等。中问结点在接受到分组后，首先将整个分组接收下来放在当前 中间结点的缓冲区内，然后读取分组头部受携带的路由信息进行查表路由。如果 当前结点不是该分组的目的结点，则按照所查的路由表将分组转发出去，否则分 组被提交到网络的高层处理，完成存储与转发的整个过程。一 8 k - a r yn c u b e 网络中的死锁及负载均衡研究 采用该交机制的路由算法具有一定的容错性与负载均衡性；同时，由于该交换 机制相对电路交换的固定带宽分配来说，它的带宽是动态分配的，这样就使得通 信链路的带宽资源利用率大大提高了，因此，非常适合应用在一些含有的突发性 业务的网络，如计算机网络等。当然，该交换机制也具有一定的缺陷性。该机制 将报文分成多个分组进行传输，各分组头所携带的控制信息必然要引入额外的开 销；另外，分组交换的端到端时延与结点对之间的距离成正比，随着网络规模的 扩大，网络时延也会越来越大，不适合应用于大规模的网络中。 3 虫孔交换( w o r m h o l es w i t c h i n g ) 该交换机制是受虫子，蚯蚓等动物的前行过程启发而设计的一种相对智能型的 交换机制。蚯蚓等动物的身体分为很多结状部分，在前行过程中，头部首先向前 探路，而身体的其它结状部分随着身体的前行，慢慢前行。直至到达目的地。在 虫孔交换机制的设计时，将整个分组分割为更小的片( f l i t ) 。这些片可分为头片( h e a d n m 与数据片( d a t af l i t ) 两类。头片含有路由信息，可进行路径的选择，数据片不具 有选路功能。整个分组的路由是由头片带路，数据片紧跟头片向目的结点路由来 实现的。而该交换机制特别设计时强调每个信道只有一个片大小的缓存。 该交换机制下的传输时延可粗略计算为： = d + l w 其中d 为源目的结点间的跳数，三为消息长度，形为信道带宽。 由上式可以看出，当l w d 时，时延对距离不敏感，因此适合于大规模网 络结构的应用。正是由于这个优点，虫孔交换机制被广泛应用于当前的商用并行 计算机，太比特路由器等中。但是，它也存在自身克服的缺点，当输出信道繁忙 而导致头片受阻时，尾随其后的数据片也不能前进，都停留在网络中各结点的缓 存中等待，这进一步阻塞了其它头片，造成网络拥塞，性能下降。 4 虚切通交换( v i r t u a lc u t - t h o u g hs w i t c h i n g ) 虚切通交换的提出正是为了弥补虫孔交换的不足，两者的不同之处在于虚切通 交换的结点缓存设为1 个或几个分组大小。当头片受阻时，虚切通交换允许后续 数据片继续前进到头片受阻的结点，并释放它们所占的资源，从而减少了进一步 阻塞的可能。它与虫孔交换一样，其平均时延对距离也不敏感，并且由于它增加 了信道中缓存的大小，使得后续的数据片可以进入该结点的缓存而非停留在中途 路径上的各个结点中，因而其阻塞概率小，可以达到比虫孔交换更大的吞吐量。 5 管道式电路交换( p i p ec i r c u i ts w i t c h i n g ) 管道式电路交换综合了电路交换与虫孔交换的特点。它将分组进行分割成片， 并像虫孔交换一样，用头片来探测路径。头片在探测路径以及受阻释放路径的过 程，是运用电路交换机制的方法进行的。比较特殊的是，管道式电路交换机制下， 在头片到达目的地发挥反馈之前，源结点中的数据片和尾片都不得发送。这样相 。第一章绪论 9 当于为每个分组建立了端到端连接，从而确保时延上界，而且在头片探路过程中， 绕开了故障区域，后续分组可以在存在故障区域的情况下到达目的地。因而该交 换机制具有一定的容错性。同时也保证了数据的可靠传输，比较适用于传输质量 要求高的业务。当然，该交换机制也具有一定的缺陷性，如建立连接开销过大， 很容易造成网络饱和，吞吐能力差等。 由于电路交换，管道式电路交换等交换方式都需要进行链路的建立，使得这些 额外开销过大，而存储转发交换等中端到端的时延与结点对之间的距离成正比， 不具有扩展性。所以，相对比较普遍适用的，而且优异的交换机制就要算冲孔交 换与虚切通交换了。这两种交换方式均采用流水线式的消息传输模式，使得端到 端的时延对距离不敏感。与虚切通的大缓存需求不同，虫孔交换要求信道的缓存 只有一个片的大小，这就减少了交换结构设计的复杂度，同时减少了硬件设计的 成本。但是，虫孔交换机制与虚切通交换机制相比，它的最突出的缺点就是，由 于它要求信道的缓存只能为一个片的大小，所以分组在向前路由时，其数据游被 分散在头片后面的众多中间结点中，并占用着这些中间结点的相应信道的缓存资 源，从而易于阻塞其它分组的前行。特别是在高负载下，分组之间的相互阻塞最 终导致网络中出现大面积拥塞区域，严重降低了网络的整体性能。故此，在本文 后面的所有仿真中，均采用虚切通交换机制进行。 1 2 3 路由算法 路由算法主要职责是确定分组由源结点向目的结点路由时的路经选择，决定着 分组在网络各结点中进行路由决策时转发端口的选择。并在很大程度上决定分组 的端到端时延和整个网络的吞吐，乃至路由器结构的硬件设计等。 在一个实际的路由器设计中，路由决策处理应尽可能的快速，以减少网络时延。 一个好的路由算法还应具有很好的硬件可行性。而且，路由决策通常不应该要求 网络全局状态信息。提供这些全局状态信息增加了额外的网络流量并要求每个路 由器额外的存储空间。下面是一个好的路由算法法设计时首先要考虑的一些因素： 1 连通性：分组在任意两结点间都可以路由的能力，即保证网络中任意两结 点之间的可达性。 2 自适应性：存在竞争和故障部件时，通过其他可选路径路由分组的能力。 3 死锁和活锁的解决性：确保分组不会永远阻塞或者永远在网络中游荡而到 达不了目的结点的能力。 4 容错性：在存在故障部件时对分组进行路由的能力。 5 均衡性：网络中业务的不均衡性要求路由算法能够具有均衡负载的能力。 负载均衡算法可以使交换网络中的各种资源能够得到充分利用，避免网络 1 0 k - a r yn - c u b e 网络中的死锁及负载均衡研究 中某些部分资源充足，而其他部分资源紧张的现象。 6 服务质量保证：由于网络中很多业务对服务质量( q o s ) 有要求，因此路 由算法设计中除传统参数外还要考虑一些q o s 参数，如链路剩余带宽等。 k - a r yn - c u b e 网络路由算法( 本文指单播路由算法) 可按照多种方式进行分类。 为便于研究，一般将其分为确定路由算法和自适应路由算法。 确定性路由算法指，分组在从其源结点向目的结点的路由过程中，只选择某一 条路径。不管网络状态是否拥塞，确定性路由算法都不会改变它的路径选择。维 序路f l = j ( d i m e n s i o no r d e rr o u t i n g ，d o r ) 2 6 l 是一种常用到的确定性路由算法。它是指 每个分组在一段时间内只在同一个维度空间内传送。这种路由算法设计简单，易 于实现，设计成本较低。但是由于它没有适应性，不能提供多条可选路径，所以 无法适应网络负载的变化，不具有负载均衡能力；以及在网络出现故障的情况下， 使得某些分组无法到达目的结点，没有容错性。 针对确定性路由算法的这些缺陷，适应性路由算法被提出了。适应性路由算法 可以细分为部分适应性路由算法与完全适应性路由算法。按照路径的长度又可以 将适应性路由算法分为最短路径适应性路由算法和非最短路径适应性路由算法。 部分适应性路由算法是指分组在其可进行路由的路由区域内，只能选择该区域内 的一部分路径进行适应性路由。比较典型的部分适应性路由算法主要有转弯模型 ( t u r n m o d e l ) 【2 7 l 中的三个路由算法：西优先路由算法( w e s t f i r s t ) ，北最后路由 算法( n o r t hl a s t ) ，以及负优先路由算法( n e g a t i v ef i r s t ) 。这些算法在第三章有 具体介绍，在此就不加以赘述。 相对于前两类算法，完全适应性路由算法可在允许的区域内的任何路径上路 由。分组从源结点向目的结点路由过程中，可根据网络的负载状况，选择负载较 轻，路径较短的区域进行路由。这样就可以绕开故障或者热点区域进行路由，所 以具有较强的负载均衡性与容错性。最短路径适应性路由算法比较有代表性的算 法有d u a t o 2 8 】算法等，该算法允许分组在最短路径区域内适应性路由，相比维序路 由算法等确定性路由算法，提高了网络的吞吐、时延等性能。非最短路径适应性 路由算法主要指分组既可以在最短路径适应性路由，也可以在非最短路径路由区 域适应性路由，典型的算法有g o a l t 2 9 】算法，g a l 算法【3 0 】，a c q r 算法【3 l 】等算法。 在k a r yn c u b e 网络中，这些算法基本都是以区域( q u a d r a n t ) 进行路由的。不同 之处主要在于它们对衡量网络负载的参考因子的选择不同；相同之处是它们都将 将网络进行区域划分，并只允许分组在某一区域进行适应性路由。 由于死锁、活锁、饿死是路由算法设计时，首先要解决的问题。它们的产生会 对路由算法的设计产生极大的影响，所以下- - d , 节专门对这三种研究课题的相关 技术基础与现状作一简单介绍。 第一章绪论 1 2 4 死锁、活锁、饿死 自适应路由算法设计不好将会导致路由死锁，活锁，饿死，因此，这三者的解 决，是路由算法，特别是适应性的负载均衡路由算法设计时首先要考虑的。 死锁是由于分组争用网络中的缓冲区资源，得不到前进所需的空闲缓冲空间造 成的。路由芯片或开关需要一定的缓冲空间来存储部分分组或整个分组，但是缓 冲器的容量是有限的。对于那些还没有到达目的结点的分组，一方面请求缓冲区， 另一方面又占用当前缓冲区，就可能产生死锁。当某些分组因为请求的缓冲区己 满而不能朝着它们的目的地前进时，死锁发生了。处于死锁配置内的所有分组将 永远被阻塞。路由过程存在相互依存的环形信道依赖结构是死锁产生的必要条件。 死锁的解决主要有两种方式：死锁避免，死锁检测与恢复。死锁避免中，只有 当申请的资源不破坏全局状态安全时，分组才可以获得它所申请的资源。这种策 略应该避免发送额外的分组来更新全局状态，否则这些分组既消耗网络带宽，也 可能会导致死锁。比较常用的死锁避免方法有转弯模型以及d u a t o 提出的虚信道模 型邛j 。转弯模型主要是针对m e s h 网络提出的死锁避免解决方案。它是通过禁止分 组在路由时的部分转弯来打破环形依赖关系来解决死锁的。虚信道模型生要是将 一条物理信道分为几条逻辑信道，在分组路由时，根据分组所在位置不同等不同 情况，限制分组对一部分逻辑信道的使用，从而解决死锁的。可以将整个死锁检 测与恢复策略的过程分为两个阶段g 检测过程与恢复过程。由于该策略要求网络 在资源分配时不进行任何检查，所以可能出现死锁。因此必须提供某种检测机制 进行死锁的检测。如果检测到死锁，就必须释放该死锁分组所占用的某些资源并 分配给其它分组，用以解除死锁。为了释放资源，通常就需要将检测的分组移出 其所占用的缓冲资源，并对该