（计算机应用技术专业论文）不规则拓扑nows中路由算法的研究.pdf

顺十学垃论文不 ；! l ! 则拓扑n o w s 中路由算法的研究 摘要 近年来，工作站机群系统( n o w s ) 蓬勃发展，占据了并行计算领域的主导地 位。发展n o w s 的关键，是提高互连网络的性能。路由算法决定了消息在网络中 如何选取路 娶其效率对网络的性能起着关键的作用。 a u t o n e t ，m y r i n e t 等用于n o w s 的交换式高速网络使布线灵活、系统可扩展 能力加强，但其拓扑的不规则性使路由避免死锁的问题变得复杂。 本文主要研究了不规则拓扑结构n o w s 中的路由算法。深入剖析了最经典的 u p * d o w n * 路由算法，指出其中的链路方向指派存在任意性、通道利用极不平衡 等缺点，并给出两种相应的改进措施。经模拟验证，改进后的算法较u p * d o w n * 路由算法性能有了显著提高。 关键字：机群系统，不规则拓扑，路由算法，虫孔路由，死锁 u p + d o v m 4 路由算法 第1 页 婴：! 兰竺堡垄 至塑型堑盐堕q ! ! 堕虫竺鎏堕塑塞 a b s t r a c t n e t w o r ko fw o r k s t a t i o n sf i l er a p i d l ye m e r g i n ga sac o s t e f f e c t i v ea l t e r n a t i v et o p a r a l l e lc o m p u t e r s t od e v e l o p n e t w o r ko f w o r k s t a t i o n s ，h i 【g hp e r f o r m a n c e i n t e r c o n n e c t i o nn e t w o r ks h o u l db ea p p l i e d r o u t i n ga l g o r i t h mc o n s t i t u t e st h ep r i m a r y f a c t o ri n f l u e n c i n go nt h ep e r f o r m a n c eo f t h en e t w o r k s w i t c h b a s e di n t e r c o n n e c t sw i t l li r r e g u l a rt o p o l o g ya l l o wt h ew i r i n gf l e x i b i l i t y , a n di n c r e m e n t a le x p a n s i o nc a p a b i l i t yr e q u i r e di nt h i s e n v i r o n m e n t h o w e v e r , t h e i r r e g u l a r i t y a l s om a k e sr o u t i n ga n dd e a d l o c ka v o i d a n c eo ns u c h s y s t e m sq u i t e c o m p l i c a t e d 、 t h i sp a p e ri n t r o d u c e st h ec l a s s i c a lu p + d o w n + m u t i n ga l g o r i t h m ，a n a l y z e si t s u n f a i ra s s i g n m e n td i r e c t i o n st ol i n k s ，a n dp r e s e n t st w on e w m e t h o d o l o g i e st oa s s i g n d i r e c t i o n s t h es i m u l a t i o nr e s u l t si n d i c a t et h a tt h en e wr o u t i n g a l g o r i t h m s c a n i m p r o v et h ep e r f o r m a n c eo f t h e n e t w o r k s i g n i f i c a n t l y k e yw o r d s ：n o w s ，i r r e g u l a rt o p o l o g y , d e a d l o c ka v o i d a n c e ，w o r m h o l em u t i n g ， u p + d o w n 4r o u t i n ga l g o r i t h m 一 第1 i 页 堡主堂垡堡苎 至塑型塑盐翌q ! ! ! 堕鱼竺鲨塑翌釜一 1 1 课题背景 第一章绪论 随着科学技术的不断进步与发展，人们迫切需要一种高性能的超级计算机，其 运算速度应达到每秒万亿次、百万亿次甚至于更高，以此来解决诸如气象模拟、流 体分析、污染分析、人类染色体、燃烧系统、海洋环境以及核试验模拟等一系列的 问题。电子技术的发展曾使计算机的运算速度获得惊人的提高，但现在已接近电子 传输的物理极限，进一步提高计算机的运算速度似乎将有赖于新技术的产生。其实 电子计算机本身仍蕴藏着巨大的计算潜力，计算机科学家早已认识到，传统计算机 的串行结构是阻碍速度提高的关键因素。因此他们开始了并行处理的研究，从而找 到了一条提高计算机运算速度的新路。 并行处理的发展非常迅速，传统大型机和向量巨型机技术由于发展缓慢、性能 价格比差，己失去竞争力。机群系统与大规模并行计算机相比，具有性能价格比高、 可扩展性好、用户编写程序方便及系统机构灵活等优点，近年来蓬勃发展，逐渐占 据了并行计算领域的主导地位。 机群系统( n o w s ) 是将一群高档微机2 1 作站用互连网络以某种结构互连起来， 充分利用各个结点的资源，统一调度、协调处理，以实现高效并行计算。机群系统 主要由结点机和互连网络两部分组成。近年来随着微处理器与存储器技术的迅速发 展，处理结点的性能已相当高，从而负责数据通信的互连网络成为影响机群系统性 能的主要因素。 一个互连网络通常由拓扑结构、交换技术、流量控制和路由算法四方面来表征。 路由算法决定了消息在网络中如何选取路径，其效率对网络的性能起着关键的作 用。目前，出现了多种用于构造n o w s 的交换式高速互连网络，如a u t o n e t ，m y r i n e t s e r v e r n e t 和s e r v e r n e t i i 等。这些网络，一般采用不规则的拓扑结构和虫孔路由交 换技术。采用虫孔路由技术，每个结点所需的通信缓冲小，并且当消息长度远远大 于微片长度时，消息的传输延迟时间与传输距离无关。但因数据包在占有许多资源 的同时，又可申请另外的资源，所以网络中容易出现死锁。交换器之间连接的不规 则性使布线灵活、设计的系统可扩展能力加强，但也使网络中路由避免死锁的问题 第l 页共6 7 页 币嫂则捌朴n o w s 中龉由算法的研究 变褥复杂。 适用于各种娩剐网络的路由算法有很多，而程不规剡拓扑网络中设计路由算法 则是一件具有挑战性的事情。随着a u t o n e t ，m y r i n e t ，s e r v e r n e t 等阏络的出现，国外 的计算丰凡专家与学者陆续掇出一些适用予不规鲻颛抒结构网络的路由算法及改进 方案，而这方面的研究在国内还是空白。本文正是在这样的背景前提下产生的，露 在对掇群系统豹互涟网络羧术律深入的了解，探讨各种路内算法的原理，并对其中 最舆型的u p * d o w n * 路由算法提出了自己的两种具体改进措施。 1 2 论文主要内容 论文重点研究了不规则拓扑机群系统( n o w s ) 中的鼹由算法，丽路由算法与 两络豹拓扑、低层的流控制怒分不开韵，骈以本文曾先探讨了互连阏络的拓扑结构、 交换技术、流控机制等内容，剖析了几十年来互连网络发展中最有成就的虫孔路由、 虚遴遥流控钒稍两颂技术。然后，辩不规划籀扑n o w s 系统率有代袭性的路由算法， 进行了分析、归纳和评价，并对其中最典型的u p * d o w n * 路由算法进行了透彻的研 究，分轿指疆了其中的不合理之楚，针对不丽的改避舀标，给出了两种完蒋方案。 经模拟实验证明，改进后的算法较原算法在性能上商了明显的提高。 论文共分六章： 第一章：绪论。简要介绍课题背景，本文所做的工作及章节安排。 第二章：蔽群系统。菰要缝奔缮与分辑了辊群系统( n o w s ) ，指激要发裁n o w s ， 负责数据通倍的互逡网络是一项关键技术。 第三章：互连溺络。接述了互遗溺络戆拓羚结构、交羧菠泰、流控机制等方瑟 内容，并着藏介绍几十年来甄连技术发展中如现的最有成就的虫孔( w o r m h o l e ) 路 盘按零秘盎遴道流按技术。 第四章：路由算法理论。介绍了路由算法的概念，对其作了系统的分类，说明 了蹲裹算法艨要瑟决赡囊题及吴俸菸决方法，劳怼粪接互建网络孛貔路峦算法律了 归纳。 第五章：不援则挺羚n o w s 系统中熬爨盘算法。要提鬻n o w s 系统豹瞧能， 必须采用a u t o n e t “7 ，m y r i n e t 。，s e r v e r n e t 汹和s e r v e r n e ti i 等交换式高速互连网 络。这些网终拓於的不规则瞧使路由避兔死镂匏趣题交褥笺焱。本激着重分橱并努 纳了观有的不规则拓扑n o w s 系统中的各类路由算法。 第六章：对u p * d o w n * 鼹出算法的改进。深入分提了不艇剐据羚网终串经典熬 u p 车d o w n 半路幽算法，针对其存在的不合理之处，给出了两种不同的改迸方案。建 第2 剪菇6 7 页 曩i 规剐箍挣n o w s 中路出算法静麟究 立网络仿真模型，进行模拟实验，评价路由算法的性熊。 1 。3 本人的主要工作 ( 1 ) 探讨了分布并行计算领域占主导地位的工作站机群系统( n o w s ) 技术。 ( 2 ) 介绍与分析了几十年来互逑技术发展中出现的最有成就的虫孔路幽 ( o r m h o l er o u t i n g ) 鼓零黟震逶i 薹滚控技术。； ( 3 ) 探讨了路由算法瑷论，对路由算法作了系统的分类，归纳了不规则拓扑 n o w s 系统中备类路由算法。 ( 4 ) 深入研究了不援剐按羚弼络孛经典兹u p * d o w n * 路由算法，分掇它熬魏缺 点，并针对其中的不足，摄磁两种不同的改进方案。 ( 5 ) 建立了网络模拟器，评价不同路由算法对网络性能的影响。 第3 页共6 7 剪 篓生兰竺笙兰 至墨! ! 塑茎望壁整主整望茎兰塑鎏签一 第二章机群系统 2 1 机群的基本概念 在诗算枫器，对视群商诲多称簿，躲：计算瓤群、工作菇集群( c o w ；c l u s t e r o fw o r k s t a t i o n ) 、工作站恻络( n o w s ，n e t w o r k o fw o r k s t a t i o n s ) 。机群是个 正在发展中的并行计算机撩型，它的定义和分类蒋述不很统。根据g r e g o r y p f i s t e r 载定义，褪器蕊并嚣或分毒计葵氍系凌斡一耱粪蘩，它楚蠹一篷完熬熬 计算机互连丽成，应能作为一个单独的绒一计算资源来使用。图2 1 简单描述了 n o w s 的硬件飙成。 图2 1n o w s 结构示意 首先，穰群蹩癌宠鳌静诗箨爨( 绩熹萎连蘸戚。凌撬群戆簿巾结点上舔蠢一 套完整的操作繇统。典型情况下，每个计辫机结点是台工作站。工作站可以建同 构的，也可以戆异构的，工作站上增加个主机接口实现连网。互邂网络可以趣通 常坟麓熬l a n ，翅e t h e r n e t 、t o k e n - r i n g 、f d d i 等；巍霹戳是嚣关阏络，蠡a t m 、 交换式高速e t h e m e t 等：还w 叛是专门开发的m y r i n e t ，s e r v e m e t 等黼络。锖对不瀚 的甄连网络，实现不同的主机接口。互连网络的拓扑结构也是可以选择的，如m e s h 、 环、总线桥等。 其次，毂群旋熊荐爻一个单独戆蓑一诗冀资源亲使咫。对于瓠群，壤主要的蔗 第4 页若6 7 荫 堡主兰篁笙壅至型型塑盐型q 型! 堕虫竺生塑竺窒一 要具有单一系统形象( s i n g l es y s t e mi m a g e ) 。所谓单一系统形象是指从用户角度 来看，整个机群就像一个系统，用户感觉到使用的是一个单一的系统，他可以从任 何地点的结点上使用这个机群，而不必关心向他提供服务的设备在什么地方。例如， 当用户使用一台远处结点上的磁带机时，他的感觉就像这台磁带机在本地的结点上 一样。在外界使用者使用机群时，机群中的各台计算机可以互相自动替换，来完成 各项功能，并不需要由外界使用者指定用哪一台计算机。在一些机群中，各台计算 机的功能也可能有所不同，有的可能有向量处理器，可供科学计算用；有的可能有 通信设备，可供对外通信用；有的还可能带有大容量的磁盘，可专门用来存放机群 的文件系统。但外界的使用者只需送一个作业( 计算任务) 给机群，并不需要规定 要哪台计算机做什么。总之，单一系统形象可以归纳为以下四个特点：单一系统( 从 用户角度看，它如同一个单一的系统) ，单一控制( 每个最终用户或系统用户都可 以从一个地点用一个接口利用系统中的各项服务) ，对称( 用户可以从任何结点使 用系统的服务) ，地点透明( 用户可以不必关心实际提供服务的设备在何处) 。 因此，机群不同于局域网，局域网是一个分布式系统。在局域网中各台计算机 基本上都是各自独立地工作，它们只是通过局域网共享资源，局域网没有单一系统 形象。而机群中的各台计算机既可以单独使用，又是多台计算机连成的一个整体， 因而机群可以充分利用机器资源，充分利用通用的计算机产品，达到高并行性和高 可靠性的要求。 2 2 机群系统的优点 n o w s 在实用上具有这样些明显的特点，它们是： ( 1 ) 用户投资风险小。用户在购置传统巨型机或m p p 系统时总是担心使用效 率不高，系统性能发挥不好。若购置后在一定程度上确实出现了这一问题，这相当 于搁置或浪费了大笔资金。而n o w s 不存在这种问题，因为退一步讲，即使n o w s 技术不够先进，但每台高性能的工作站照样可以使用，主要的投资不会浪费。 ( 2 ) 用户编程方便。用户利用并行程序设计环境，只要在原来已有的c 、c + + 、 f o r t r a n 等程序中的相应的地方插入少量的几条原语后，即可使这些程序在n o w s 上并行运行，这一点很受用户的欢迎。 ( 3 ) 系统结构灵活。用户将不同体系结构、不同性能的工作站连在一起构成 异构型工作站机群系统。这样一方面可进一步发挥已有机器的效率。同时，这种异 构系统能弥补单一体系结构适应面窄的弱点，可更全面地满足各种高速复杂计算的 需求。 第5 页共6 7 页 娥士学位论文 不规则拓扑n o w s 中路由算：法的研究 ( 4 ) 性能价格比高：一般巨型机系统或省m p p 都要花费几百万楚几千万美 元，而一台工俸站只需尼万美元，壹凡卡台或凡酉台工 擘活逶遥葛速嚣络互连构成 n o w s ，仅从浮点运算能力来看，虽然每台工作站只有几m f l o p s 至几十m f l o p s ，但 一群工俸媾并芎亍计算豹憨体运冀性憨可鬟达到g f l o p s ，缓近一骛逗型掇熬性憩，然 而价格却低了很多。这怒n o w s 得以发展的一个原因。 是一个在萁最后包含了数据包结束标志的数据微 片。中闯数微片均为数撼微片。一拿滚控摹擞片是逶痿敬疑j 鼙遴遂爨熊接受竣拒绝 的最小信息单位。对一个消息来讲，在每个结点上只需能缓冲其一个微片就能满足 要求。两不象存德转发蒡释，辩一个漓意静全部都存储劐一个缩点上鹰，再把它商 下一个结点传送。w o r m h o l e 路凼通过用一个数据包的头部囊接开辟一条从输入链路 到输出链鼹的路径的方法来进行操作。每个消息中的微片以流水的方式在网络中向 前“蠕动”。每一个微片楣当予个w o r m 豹个关节，“矮魂”是戳关节荧攀整颞 序地向前爬行。 警一个数据惫豹头徽片妥达一个络点a 熬路盛器螽，踌由嚣穰撂头微片瓣寻径 信息立即做出路由选择： ( 1 ) 魏暴所遥择的道道空闲蠢所选择的绣点b 酌通信缓冲可篇，那么这个头微 片就不必等待，查接通过结点a 传向下一个结点b ；随后的其它的微片跟着橼应地 向前“蠕动”一个结点。当消恩的尾微片向前“蠕动”一个结点之后，它刚才所占 有的绦点裁被放弃了。 ( 2 ) 如聚所选择的通道非空闲或所选择的结点的通信缓冲器已满时，那么这个 一一一 第1 2 页头6 7 页 堡：! 兰垄笙茎 i ：堡鍪堑茎釜2 强! 皇笙奎簦婆! 塑眨乙一 头微片就必须在此结点的通信缓冲器中铸待，直到这两个条件都满足时为止；其它 微片也在原来嬲结点上等待。此时，被臌塞的数据包不从嘲络中移去，微片也不放 弃它掰占有的缭点帮暹遘。邃楚w o r m h o l e 技术与其它流控翎技术懿不阉之处e 当一个数据包的头微片到达某个结点时，该结点为它选择了下个通道并且把 它沿着这条通道向前传送。数据包在向前传送过程中，其各个微片顺序地从源结点 怒蠢嚣熊结点。奢可鹱头徽冀巴妥这强匏缝点了，可还鸯嚣继款徽嚣缠在滚缝点主。 嘲于除头微片外其它的徽片都不含寻径储息，所以，微片序列必须保持网络中遗续 的通道，不能被其它的数据包的微片所打断。 3 2 。3 。2w o r m h o l er o u t i n g 技术晌优赢 w o r m h o l e 鼹出技术与其它交换技术棚比有其独特的优点。 雷宠，它对每个结点上豹缓淬器懿霰求量，l 、，荔予v l s i 实嚣。数据包静鑫个 微片分布在各个结点上，减少了对每个绪点的缓冲器的需求。而在存储转发和虚拟 或通技术中数据包整个放在一个结点上，缓冲器的需求量大且数据识的大小受到缓 冲器大小豹限裁。 其次，它爨肖较低的网络传输延迟。数据包的所有徽片以流水的方式向前传送， 充分发挥了时间并行性，撮离了传输效鬻。而在存储转发和虚拟寓通技术中，数据 包熬个地从一个结点“跳”向另一个结点，通道的使用是串行的，所以它 j 豹传埝 瑟遮正跑子滚感在瓣终孛接输瓣距离。w o r m h o l e 技术霉拜线路交换按术的网络篱输延 迟正比于数据镪的长度，传输距离对它的影响很小。 图3 5 ( a ) 展示了采用存储转发技术的网络中，钒禽4 个微片的一个包，从绻 点i 到结点4 ，途经两个孛分缮点( 臻熹2 ，缝熹3 ) 熬转输遂疆。头徽冀霆h 稼记， 屠躐3 个数据微片，用a ，b ，c 标记。每个结点消耗4 个单位时间传输数据包到下 一个结点。因此，如果在路豳路径上不存在资源冲突和梦e 锁情况，戗从结点1 传送 到络点4 霈要1 6 个单位时阐，当网络摁挤瓣，路由砖阗更长。蔼农潮3 。5 ( b ) 袋 舔虫孔路蠹酾黼络中，霞襻鹃包虱达结点4 只需要7 令肇位对阕。 令l 为数据包长度，n 为从源到目标经历的结点数，则存储转发方案一般需n l 单能时间，而盥孔路由仅需l + n l 单位时间经过n - 1 个结点的路径，可望达到的加 速比是n l ( l + i ) 。怼予是够长豹包，玺我黪壹攘黠蛰绽存薅转发方案豹辍疆燕遮 比趋近n 。 第】3 页共6 7 页 篓主兰堡堡茎 至塑型堑盐型璺塑蔓塑堕堕堕塑墅塑旦一 空凝 结点4 ( 目) 结点3 结点2 姥煮l ( 源) 0l23 4567891 01 11 21 31 41 51 6 时间 时间 ol23456789 图3 5 两种交换技术鲢黠闯纥较 第三，它的通道共享悭好、利用率商。在w o r m h o l e 技术中对通道的预约和释 放鼹结合在一超的一个完蹩的过程，占脊一段新的通溆后将立即放彝用过的一段旧 通道，充分考虑了多个薅惑对通道资源粒共享。癌惠缀i 熏貔每一段遴遂甄不在傣惑 到达之前预约落不在信怠经遥之后继续占青，仅当信息翔达对方被使用。对每段 通道在信息到达之前它不必空闲等待：在信息经过之膳宦立即可以为其它信息所利 用。而在线路交换技术中，辩通道的预约釉释放是完全分离的两个步骤一在信息传 送之懿一次淫预约掰鸯褥躅弱豹逶逡，誊戮信意传送乏麓方全都释敝。这样导致备 段遴道都存在被空闲占用的时间，降低了邋道的使用效率。同时也造成不同的信息 之间无法共享物理通道。在威拟直通技术中也有同样的闻题。 第疆，它易于实现多播( m u l t i c a s t ) 窝广攒( b r o a d c a s t ) 。w o r m h o l e 技术允 许跷由器复刽数据包酶徽片并把它们从路由器的多个输出通道输出，以实现 第1 4 页共6 7 戚 嫂主兰焦堡壅 至塑型堑盐型q 型! ! 堕曳墨垄堂哩瞳坠一 m u l t i c a s 和b r o a d c a s t 。 w o r m h 。l 。路由技术与传统的存储转发和虚拟直通技术相比，具有缓冲的需求量 小，网络延迟，j 、，且数攒包大小无限制以及易于v l s i 实现等优点；与线路交换技 术相比，w 。r m h o l e 路由技术具有良好的通道共事性，灵活的连接方式，较高的褥吐 翠。在w 。r i h o l e 路亩技术出瑷之后，凡乎所有的路由簿法都撼它作为自己低滕的 流控制支持。 3 3 流控机制 互逡网络的流控机制是指，当一个消息在其中沿着慕条路径传送时，互连网络 弼何来为它分配通道和缓存器，蔽及如何解决数据包的资源冲突问题。 当一数据包p 因为它需要的某些资源( 通常为一缓存区) 被另一数掇包所占据， 蕊不能继续前送时，就发生了资源冲突。冲突鹣解决方法有：( 1 ) 在原缝阻塞p ， ( 2 ) 在冲突发生的前一结点处缓存p ，( 3 ) 扬莽p ，( 4 ) 绕道策略，把p 路由鬣另 一j 它耩请求懿逶道。 阻塞策略的实现成本低，但可能出现分配给阻塞包的资源空闲的情况。扬峁策 醛可靛会密瑗瓷潆严重浪费，舞菇需要穗重耨发送瘸霞答，否燹 l 被扬弃的龟也许会 兹失。绕道路由为包路由提供了更大的灵活性。然而，绕行的包可能进入一个涵锁 德环，这褥浪费掰络资潞。滚控橇麓壹按影响鬟麟络开关静设计，皖翔缓冲区翡大 小。 寝遥遴( v i r t u a lc h a n n e l ) 楚d a l l y 提出豹耱薪黧瓣流按露l 技术。 3 。3 。1 遥道的空阕翔题 互连溜络鸯瓣类资滚缝成：缓存器酞翔和逶遥。交予先前的置连网络中通道帮 缓冲器相耦合的淡源分配，互连网络的吞吐量被限制在网络能力的2 0 5 0 之间。 毽为与每个裼蓬逶遂穗联系瓣只有一个缓存器骏蠢，所戳一蔑驮歹l 头上的淄怠 包a 获得了这个物理通道，其它的消息包就不能使用这条物理通道，直到a 放弃这 个耱理逶遵为壹。翅栗矗被疆塞了，它璎将占畜这个凌毽逶遒不释放，鼗对，静健 网络中有其它消息包可以使用这条通道以提高其效率，它也只能空闲下来。其它消 息瞧毅毽爨了。遮静渡滚剪竣矮瓣3 。6 ( 1 ) 来鬻鹾。该黧捂绘7 瓣络鹃一个部分， 大的圆角框代表结点，实箭头代寝结点间的通道，小的框代表片缓存区，虚箭头袭 示嚣进中麴鼹蠢。数据包是被毽塞，我露宅砉据麓缓存3 e ( 结蠡3 静东瓣) 和4 s 。 第1 5 页共6 7 贾 瑚土学位论文不规黄据扑n o w s 中路由算法静姘究 臌然数据包b 所需要的物域通道，从i e 与2 w 之间到4 e 与5 w 之间都空闲着，f a 因 为数据包矗占键藿与3 9 到4 轷闼靛通道藕合懿缓存3 e ，数据趣8 不戆1 l 誊进。 结点l鲒点2结点3结点4 结点5 ( 1 ) 当戆壤邂遂空阑露数攒毽8 被疆塞程数据包a 之匿 8 懿嚣羲蟪 ab ( 2 ) n 嚣i n n 提供茄矫趣缓渖兔诲数据包b 趣避辍塞的数据包a ， 圈3 6 3 3 。2 瘟通道的流控制 b 的目的琏 传统的网络把与每条通道相关豹片缓存区组织为先进先出( f i f 0 ) n - - + g l g a j 魏强3 8 ( a ) 掰示。这静缀绞方法隈澍了资源斡分配，使得每个缓存嚣只憝包含攀 个数据包的微片。一旦数据包阻塞了，物理通道就窑闲下来，因为没有其它的数据 包能获得访问该通道的缓存。 为了瑟决上述通道夔空耀趣瑟，再d a l l y 在 8 3 中援港了虚逶遴豹援念霸纛邋逶 流控制的方法。 3 3 2 1 虚通道的概念 虚拟通道嫩两个结点间的逻辑链，玄由源结点的片缓冲区、结点间的物理通道 以及接收结点的片缓冲区缎成，图3 7 说明了四条虚拟通道共享一条物理通道的概 念。 一 第1 6 页共6 7 页 母 9 雠 b母 圈 日一 堡主堂些堡苎 至塑型堑盐翌望坐土堡塑堕翌型鱼堕塑一 圈 物理通道 源结点中的 片缓冲区 目的结点中 的片缓冲区 图3 7 四条虚拟通道以片传递为基础分时地共享一条物理通道 源结点和接收结点各有4 个片缓冲区。当物理通道分配给某对缓冲区时，这一 对的源缓冲区和接收缓冲区形成了一条虚拟通道。换句话说，物理通道由所有的虚 拟通道分时地共享。除了有关的缓冲区和通道之外，还必须用某些通道状态( 如信 号) 来表示不同的虚拟通道。源缓冲区存放等待使用通道的片。接收缓冲区存放由 通道刚刚传送过来的片。通道( 电缆或光纤) 是它们之间的通信媒介。 3 3 2 2 虚通道流控制的方法 w d a l l y 提出的虚通道流控制方法为，在缓存器队列大小不变且每片容量相同 的情况下，虚通道流控制用几个较小的相互独立的缓存器队列来代替原来的一个大 的缓存器队列，使路由器的缓存器得到更有效的利用。通过把与每个网络物理通道 相联系的缓存器队列划分成几个与虚通道相联系的较小的缓存器队列的方法，使与 每个物理通道相联系的是几个独立的虚通道，而不再只是一个与物理通道相关的很 深的队列，如图3 8 ( b ) 所示。与一个物理通道相联系的各个虚通道被独立地分配 出去，彼此之间为物理带宽而竞争。这样可以提高物理通道的使用效率，从而使网 络的吞吐量得以增加。 第1 7 页共6 7 页 塑主堂垡丝壅 至塑型塑盐型旦型! 生堕虫篁鲨堕型塑一 珈皿衄p 协 镪 吲 ( a ) ( b ) 图3 8 ( a ) 传统的结点把它们的缓存组织为f i f o 队列 ( b ) 使用虚通道流控制的网络把它的缓存组织为几个独立的队列 d a l l y 用虚通道的方法把缓冲资源从传输资源中分离出来，这种分离使活动的 消息可以充分利用网络带宽，越过被阻塞的消息，而不是象以前那样让网络空闲着。 图3 6 ( 2 ) 说明了向图3 6 ( 1 ) 所表示的网络中加入虚通道以后的情况。数据包a 占 据着缓存3 e 1 与4 s 1 ，并已被阻塞。然而，数据包b 仍可前进，因为缓存3 e 2 可 用，允许它访问3 e 与4 w 之间的通道。 虚通道流控制为网络中每个物理通道提供多个缓存器队列( 即虚通道) 来解决 资源分配中的耦合问题。如果一个占有某条物理链路的消息包被阻塞了，其它的活 动消息可以利用与这条物理通道相关联的其它缓存器队列，越过被阻塞的消息包。 互连网络中开销最大的资源是物理通道的带宽，其次是它的缓存器队列。为一个网 络增加虚通道流控制，把它们分离开来，使这两类资源的利用更为有效。除了增加 吞吐量，虚通道给网络中的消息分配资源提供了更大的自由度。这种灵活性允许使 用调度策略，如先到先寻径等，这样可以减少网络延时的波动。另外，虚通道的引 入可以较容易地实现无死锁的路由算法。 然而，虚通道的引入也带来一些问题：( 1 ) 路由器对消息头的修改需要的开销 比较大；( 2 ) 虚通道需要增加缓冲区，增加路由器交叉开关的规模，需要更复杂的 仲裁单元，从而带来了实现上的复杂性；( 3 ) 由于硬件规模的扩大，使路由仲裁时 间增加，从而导致消息经过路由器的时间( 路由器建立延迟) 增加。 第1 8 页共6 7 页 塑主堂垡丝兰 至塑型堑盐型旦! ! ! 堕虫翌翌型型望王一 3 4 网络的性能指标 衡量一个互连网络性能的主要因素是它的传输延时和吞吐量，另外还有负载系 数、利用率、网络的平均传输系数等。 定义1 0 一个消息的传输延时，是指从它在源结点进行发送初始化时到它在目 的结点完整地被接收时所耗费的时间。个网络的传输延时是指在一定条件下发送 消息的平均延时。 传输延时通常是以下三个部分之和：建立延时( s t a r t u pl a t e n c y ) 、网络延 时( n e t w o r kl a t e n c y ) 和阻塞延时( b l o c k i n gl a t e n c y ) 。 建立延时是指一个消息在源结点和目的结点上装配和分解、从存储器拷贝到 通信缓冲器以及正确验证等所耗费的时间。它依赖于机器本身的硬件和软件技术， 主要有两个部分组成：( 1 ) 源结点延时( s o u r c el a t e n c y ) ，是指从发送进程开始 消息发送初始化的瞬间到消息的头部进入网络的瞬间所经历的时间。( 2 ) 目的结点 延时( d e s t i n a t i o nl a t e n c y ) ，是指从消息的尾部到达目的结点的瞬间到消息完全 被接收进程接收的瞬间所经历的时间。 网络延时是当消息的头部从源结点进入网络，到消息的尾部到达目的结点的 时间间隔。它主要取决于两个因素( t n = t p - d + l b ) 。( 1 ) 结点延时，t p d ，其中t p 是消息在它所经过的路径上的每个中间结点上的平均延时，d 为中间结点数或源结 点与目的结点之间的距离。( 2 ) 线路延时，l b ，其中l 为消息的长度，b 为结点之 间的通道的带宽。 阻塞时间( 或称等待时间) 包括在消息传递过程中其它所有可能的延时。发 生这些延时的主要原因是资源冲突。例如，一个消息所需要的通道处于忙状态，或 它所需要的缓冲器在被其它消息占用，等等。阻塞时间是动态的，是由在互连网络 上多个消息的传递过程中的动态行为所造成的。如果网络上阻塞很严重或分布非常 不均匀，阻塞时间对通信延时将会有巨大的影响，建立延时和网络延时是静态的， 通常被用来描述无冲突网络。 定义1 1 网络的吞吐量是指在单位时间内网络所能传输的消息的数目。 种估算吞吐量的方法是计算网络的容量，即网络中能同时容纳的信息总量。 一般情况下，网络的最大吞吐量是其容量的一部分。 热点是一对不按比例地占有网络总通信量中大部分通信量的结点。由于拥挤的 缘故，过多的热点通信量会使整个网络性能下降。网络的热点吞吐量是从一个特定 结点p 。传送至另特定结点p 。的最大速率。 定义1 2 网络的负载系数a 定义为网络每个周期产生的消息长度总和与每个周 第1 9 页共6 7 页 不规则拓扑n o w s 中路由算法的研究 期网络总的传输能力之比。 定义1 3 网络的利用率定义为网络的吞吐量与网络的传输能力之比。 定义1 4 在随机产生的均匀负载情况下，网络上所有消息的平均传输距离与网 络上任意两点之间的平均最短路径长度之比，称为网络的平均传输系数。 网络的平均传输系数越接近于1 ，说明此时网络的传输效果越好。 定义1 5 在无阻塞情况下，一个消息的一个微片包从某个结点传送到其一个邻 结点上所用的时间，称为单位时间。 3 5 小结 本章首先讨论了互连网络的结构描述，然后介绍了评价互连网络性能的几种常 用指标。 一个互连网络可以用它的拓扑逻辑、路由算法、交换策略、流控机制等几方面 来描述。网络拓扑逻辑是网络图的物理连接结构，分为静态网络和动态网络两种类 型。静态网络常用的拓扑结构有环形、树形、网格形和超立方体形等。交换策略决 定如何将消息从输入通道送到输出通道。第一代多计算机中使用存储转发交换技 术，而第二代多计算机中则通常使用虫孔路由交换技术。虫孔路由技术具有低延迟、 通道共享性好、易于实现多播和广播等优点。流控机制决定如何为消息分配资源。 虚通道是一种新型的流控机制，使用它可以解决通道的空闲问题，提高网络的吞吐 率。 衡量一个互连网络的性能的主要指标有传输延时和吞吐量。消息的传输延时， 是指从它在源结点进行发送初始化时到它在目的结点完整地被接收时所耗费的时 间。网络的吞吐量是指在单位时间内网络所能传输的消息的数目。 第2 0 页共6 7 页 堡圭堂焦堡塞 至塑塑煎盐型竺! 型至堕堕美翟堕塑翌鎏一 第四章路由算法 4 。1 路漪算法的概念与分类 4 1 1 路由算法的概念 路由怒把信息从源结点穿过刚络传递到目的结点的行为，在路上，至少遇到一 个中间结点。路由包含两个基本的动作：确定最僬路径和通过网络传输信息。在路 出的过程中，居者也称先( 数据) 交揍。交换稳对来说魄较篱攀，恧选择黪径缀复 杂。 路由掉法用来决定发送一个消息到其目的地所经过的路径。根据一定的计量标 准，选择最佳路径。常用的计量标凇有路径长度、可靠性、延迟、带宽、受载与通 癌饯徐等。为了帮劲选籍，路壶箕法裙始驻著维护包含籍轻信惠静鼹壶_ 裹，路径信 息根据使用的路由算法不同而不同。 并行计算机中的路囱的任务是猩处理机、全局存储器与本地存储器之阉传递信 基。 4 1 2 路由算法的分类 互涟潮络中，可按以下不丽标穗对路由算法分裳： ( 1 ) 根据数据包的目的地的数髓分为单播路由；数据包只有一个目的地； 多播路由：数据包有多个目的地。 ( 2 ) 缀据骰窭爨盘决定静建方分爻集孛式鼹密：垂审心控靠l 器决定；源 路由：由源结点决定；分布式路由：程数据包传输过程中由分布式的方式确意。 ( 3 ) 根据路由的实现方式分为查路由表方式；在一个踌由表中查找；有 隈状态搬嚣方式：棱有隈状态极器鼹软转或硬馋撬牙潞蠹雾法。 ( 4 ) 校据路疰l 韵自适应程度分为确定性瓣由：总是在一对源和茸的结点 第2 l 黄共6 7 页 坝l - ：学位论文不规则拓扑n o w s 中路由算法的研究 之间提供同一条路径：自适应性路由在一对源和目的结点之间提供多条路径，用 网络流量或通道状态信息来避免拥塞或网络中的错误区域。 ( 5 ) 前进性前进型：向前移动头部，每一次路由操作占据一条新的通道； 回溯型：允许头部回溯，释放先前占据的通道( 用于容错路由) 。 ( 6 ) 最小性最短型：提供通道使数据包向它的目的地靠近；非最短型( 迷 路型) ：也提供通道使数据包远离目的地。 ( 7 ) 根据路由可使用的路径数目分为完全自适应路由算法和部分自适应路由 算法，前者可选择所有路径，而后者由于在路由上加以限制，仅有部分路径可选。 以上分类方法可用图4 1 更清晰地表示出来。 路由算法 目的地的数目+ 路由的决定_ +集中 实现方式 自适应性+ 前进性+ 最小性， 路径的数目+ 图4 1 路由算法的分类 下面重点讨论第四和第六种分类方法，即把路由算法分为最短路径( m i n i m a l ) 算法和非最短路径( n o n m i n i m a l ) 算法，确定性( d e t e r m i n i s t i c ) 算法和自适应 ( a d a p t i v e ) 算法。 定义1 以d ( a ，b ) 表示网络中两结点a 与b 之间的距离。对于路由算法所确 定的条从a o 到a “的路径上的结点序列凰、a ，、，a 。，如果d ( a 。，a 。) d ( a 。a 。) ， 运里i j k ，那么我们就称这个算法为最短路径的。否则，对任意i 、j ，i j k ， 存在d ( a - ，a - ) d ( a 。，a * ) ，则称此算法为非最短路径的。 在最短路径算法中，消息每前进一步，与目的结点的距离就近步。而在非最 第2 2 页共6 7 贾 塑主堂垡堡壅 至些型塑塑型旦型! ! 堕虫塑鲨盟型墨一 短路径算法中，消息可以暂时向远离目的结点的方向发送。非最短路径路由算法比 最短路径算法多做了工作，但它仍可能是当时网络负载情况下的最优选择。 定义2 如果一个路由算法对路径的选择只依赖于它所发送的消息的源结点和目 的结点，那么这个算法就称为确定的。如果在一个路由算法中，消息从源结点到目 的结点可以有几条不同的路径，那么这个算法就称为自适应的。 在确定性路由算法中，一旦消息被阻塞时，无选择其它空闲路径的能力，自适 应路由能消除这种缺陷。在自适应路由方案中，不仅要存在几条不同的路径，并且 路由算法必须能在不同的情况下分别使用它们。对一条具体的物理通路的选择取决 于许多不同的因素。例如，由于容错的需要或由于网络上发生了路由冲突等。 路由算法为每个消息分配一条路径，它决定了一个网络的静态负载状况。确定 性路由既快速又简单，尤其是以维数为顺序的确定性路由网络划分起来非常方便， 对预防死锁也非常容易。 但是确定性路由也存在明显的缺点。为了避免死锁的发生，尽管在源结点和目 的结点之间有大量的路径可以选择，确定性路由仅选择了一条从源结点到目的结点 的路径。这意味着由于不能灵活地使用物理通道，互连网络不能有效地使用其物理 连接的密度。更不幸的是，对给定的物理连接中的任何固定路径的选择都有可能造 成某种冲突模式，造成负载不平衡。此时，确定性路由将导致性能的降级，而使其 性能比应有的性能要差。总之，确定性路由妨碍了利用丰富的网络资源来完成通信。 利用可适应路由可以改善这种情况。可适应路由允许消息包充分利用连接的密度。 在典型的可适应路由模式中，消息包可以采用多条通路中的一条，减小网络的阻塞 延迟，提高网络的利用率。 路由算法和路由器( r o u t e r ) 是密不可分的，所以讨论路由算法的时候总是离 不开流控制。消息包的最佳路径选择依赖于当前网络的负载情况。为了在全负载的 情况下实现更好的性能，路由算法必须是可适应的，即根据网络当前的状况来选择 路径。可适应路由器所带来的附加的灵活性在负载均匀和非均匀两种情况下都使网 络的性能得到提高。一般在一个可适应路由系统中，可以根据任何局部消息来决定 路径的选择。 一一 第2 3 页共6 7 页 堡主鲎堡堡兰 尘塑型堑堑型q ! ! 空堕宴簦望型型堕l 一 4 2 路由算法需解决的问题 4 。2 。1 连通、死锁与活锁 一个好鳃鼹由箨法应熊避免死锁( d e a d l o c k ) 期溪锁( 1 i v e l o c k ) ，使网络负 载平衡、阻塞小、遴售延迟低、控制籀单和易予v l s i 实现。 定义3 路由算法是连通的，是揩路由算法至少保 垂每对结点之间至少存在条 路径。 定义4 网络通信的死锁指的是这样一釉状态：多个数据包在同时传送过程中， 每个包占据了一些通信资源( 链路或缓存) ，同时又申请被其它包所占据的资源， 形成若干包对资源的循环依赖，此时系统在没有外界干预的情况下将无法实现包的 有效传送。 如图4 2 所示，有两类死锁，是由缓冲区戏通道上的循环等待引起的。一类悬 存储转发网络中的缓冲区死锁( b u f f e rd e a d l o c k ) ，如图4 2 ( a ) 所示。四个包占用 了四个结点的四个缓冲区将导致循环等待。除非扬弃某个包或者某个包的寻径出 错，否则死锁不会解除。在图4 2 ( b ) 采用虫孔交换技术的网格形网络中，四条消息 沿四个通道同时传送也会产生死锁( c h a n n e ld e a d l o c k ) 。四个消息的四个片阍时 占用了四个通道。如果循环中没有个通道被释放，死锁状态将持续下去。 j 结点a缩点d j ll 埴国 聚稻存储转发替径静四个结点之瀚出现缓冲区死镄 一磊磊再i 鞭： 学位论文不臻蹦辐努n o w s 孛路峦笋笙壁登塞 片缓 ( b ) 采用虫孔路由的四个结点之间出现通邋死锁 ( 带阴影方块是冀缓冲联) 圈4 2 缓、挣区或通道上游锤环等待；| 越静死镀 定义5 活锁是这样一种情况，数据戗在网络中蕊不确定地移动，。但没有数据 镪能到达它的鬻豹地。典黧鲍活锁情况怒当一数据瓴趣基豹地嚣近黠又不叛救援 瓣。数据包浚奇谈阻塞，稼它慧是在阙络中旋转。 由于路由函数的不一致，可能造成添锁，但是在实际情况下确实存在。例如， 贪婪热土豆( g r e e d yh o t p o t a t o ) 路由m3 ，它是一种同步路由方式，在中间绪点 不壤穗缓存，数攥包在每一辩阉步黎登矮移凌，壹弱爨遮它亵熬瓣憨络点。豁浆瘗 于竞争使一数搬包不能使用它想要的输出通道，则它偏斜到另一通道。这样它可能 偏离预定的朝向目的结点的方向，而在网络中不停地旋转，却永远到达不了目的结 点。 4 2 2 解决死锁的方法 4 2 2 1 通道依赖图与冤死锁理论 d a l l y 子1 9 8 7 年提窭了遴遴蔽赖鬻( c h a n n e ld e p e n d e n c eg r a p h ) 酶概念， o u a t o 于1 9 9 3 年提出了无死锁的充分必要条件和“通邋依赖图( c d g ) 是非循环的， 则可避免死锁”的无死锁理论8 1 。 虽然近十每来，踌鑫冀法无疆锁理论蠢了一定靛发蒺，人