（通信与信息系统专业论文）片上网络面向应用路由算法的研究.pdf

摘要川i i | f l | | | i | i i f f i i i i | | | i l f l i | | i | l | i l i 驯y 2 0 6 8 0 2 7随着半导体技术的发展，芯片上集成的i p 核数量急剧增加，传统的总线型片上系统已经不能满足其性能要求，一种新兴的借鉴传统计算机网络的技术片上网络成为了片上系统通信的解决途径。片上网络各个i p 核之间通过路由器组成的网络相连，之间相互通信需要路由算法来查找与之通信的相应路由器节点。而针对特定的具体应用设计片上网络时，需要考虑面积、时延及功耗等具体要求的限制，对芯片性能有更高的要求，而在面向特定应用的片上网络上使用通用的路由算法效率很低，所以针对特定的具体应用设计片上网络时通常要根据系统的通信特性来设计面向应用的路由算法。本文首先对片上网络及其基本概念做出了总结和分析，介绍了片上网络交换机制和现有的一些通用路由算法概况，然后指出通用路由算法在特定应用下效率很低，并介绍了当前比较典型的三种面向特定应用路由算法，并对三种算法在时延、吞吐和能耗等方面同通用路由算法进行了分析比较。网络中源节点和目的节点都处在边缘并且跨度较大时往往会增加信道依赖图中的环路出现的概率，我们提出了一种新型的面向应用路由算法，通过限制这类源节点和目的节点都处在边缘的通信流的路径，来减少了信道依赖图中环路的概率，同时降低网络中间区域出现热点的概率，达到流量均衡的目的。为了使较大的通信流尽可能多的路径，我们以减小的通信路径比例最小为目标打破依赖图中的环路，最后加以仿真验证，证明其具有更为优良的网络性能。关键词：片上网络信道依赖图自适应面向应用路由算法a b s t r a c tw i t ht h ed e v e l o p m e n to fs e m i c o n d u c t o rt e c h n o l o g y ，t h ei n t e g r a t i o no fi pc o r eo nt h ec h i ph a sr i s e nd r a m a t i c a l l y ，a n dt h et r a d i t i o n a lb u s b a s e ds y s t e mo nac h i pc o u l d n tm e e ti t sp e r f o r m a n c er e q u i r e m e n t s a ne m e r g i n gt e c h n o l o g y ，d r a w i n go nt r a d i t i o n a lc o m p u t e rn e t w o r k s n e t w o r k o n - c h i pb e c o m e sas o l u t i o no fc o m m u n i c a t i o no n ac h i p t h ev a r i o u si pc o r eo nt h en e t w o r k - o n - c h i pc o m m u n i c a t e 、 ，i t he a c ho t h e rt h r o u g ht h en e t w o r kc o n s i s t i n go fr o u t e r sb yt h ew a yo fr o u t i n g h o w e v e r , w h e nd e s i g n i n gn e t w o r k - o n - c h i pf o rs p e c i f i ca p p l i c a t i o n s ，w en e e dt oc o n s i d e rh i g h e rp e r f o r m a n c eo fa r e a , d e l a ya n dp o w e rc o n s u m p t i o n ，b u ti th a sv e r yl o we f f i c i e n c yw h e nu s i n gg e n e r a lp u r p o s er o u t i n ga l g o r i t h m t h e r e f o r e ，w ed e s i g na p p l i c a t i o n s p e c i f i cr o u t i n ga l g o r i t h ms p e c i f i ca p p l i c a t i o n sb a s e do nt h ec o m m u n i c a t i o nc h a r a c t e r i s t i c so ft h es y s t e mt od e s i g n i nt h i sp a p e r , w es u m m a r i z ea n da n a l y z et h en e t w o r k - o n - c h i pa n di t sb a s i cc o n c e p t si n t h ef i r s tp l a c e ，a n dt h e nw ei n t r o d u c es o m eo ft h ee x i s t i n gs w i t c hm e c h a n i s m sa n d 西v eag e n e r a lo v e r v i e w o ft h er o u t i n ga l g o r i t h m ，a n dp o i n t i n go u tt h a tt h ee f f i c i e n c yo fc o m m o np u r p o s er o u t i n ga l g o r i t h mi nap a r t i c u l a ra p p l i c a t i o ni sv e r yl o wi sf o l l o w e d o nt h i sb a s i s ，w ed e s c r i b et h ec u r r e n tr e l a t i v e l yt h r e et y p i c a la p p l i c a t i o n - s p e c i f i cr o u t i n ga l g o r i t h m sa n di t sc o m p a r i s o no ft h ed e l a y ，t h r o u g h p u ta n da v e r a g ed e g r e eo fa d a p t i v e ，e t c t h ec o m m u n i c a t i o n sw h o s es o u r c en o d e a n dd e s t i n a t i o nn o d ea r eb o t l li nt h ee d g eo ft h en e t w o r ka n df a ra w a yf r o me a c ho t h e rt e n dt oi n c r e a s et h el o o pp r o b a b i l i t yo ft h ec h a n n e ld e p e n d e n c yg r a p h w cp r o p o s ean e wa p p l i c a t i o n s p e c i f i cr o u t i n ga l g o r i t h mb yl i m i t i n gt h i st y p eo fc o m m u n i c a t i o nb yt h ee d g ew a yo ft h en e t w o r kt or e d u c et h ep r o b a b i l i t yo ft h el o o pi nt h ec h a n n e ld e p e n d e n c yg r a p ha n dt h ep r o b a b i l i t yo fm i d d l eh o ts p o t sa r e ae m e r g e n c eo ft h en e t w o r k w eh a sat a r g e to fm i n i m i z i n gt h ep e r c e n t a g eo fr e m a i n i n gc o m m u n i c a t i o np a t h sa f t e rb r e a k i n ga l lc y c l e si nt h ec h a n n e ld e p e n d e n c yg r a p h t h ef m a lp e r f o r m a n c es i m u l a t i o np r o v e st h a tt h en e t w o r kp e r f o r m a n c eo ft h en e wr o u t i n ga l g o r i t h mi sm u c hm o r ee x c e l l e n t k e y w o r d ：n e t w o r k - o n - c h i pc h a n n e ld e p e n d e n c yg r a p ha d a p t i v ea p p l i c a t i o n s p e c i f i cr o u t i n ga l g o r i t h m第一章绪论第一章绪论1 1 片上网络产生的技术背景2 0 世纪9 0 年代，随着半导体工艺的不断发展，片上系统s o c 在集成电路向集成系统转变下产生，随着芯片的不断完善和发展，现在s o c 中可以集成多个处理器、模拟电路、存储器及片上可编程逻辑的i p 核【1 1 。当前，s o c 广泛应用于设计大规模集成电路系统，集成度不断的变大，使得s o c 相关技术变得越来越复杂，在一块芯片上集成大量m 核将越来越普遍，当前s o c 主要以总线方式和点到点的连接方式连接各个口核，但是随着技术的发展，s o c 可以包含的i p 核数量增至成千上万时，传统的以总线结构的s o c 设计方法越来越难以适应大规模片上数据通信的要求。( 1 ) 传统总线结构问题随着电路规模越来越大，芯片上集成的i p 核越来越多，之间需要通信的数据量越来越大，传统的总线方式可扩展性问题【2 1 【3 1 越来越明显，传统总线结构无法支持两对或者更多对节点之间同时进行通信，资源利用率低，不能提供很好的并行处理能力。( 2 ) 单一时钟同步问题总线结构要求全局时钟同步，但是随着芯片工艺尺寸越来越小，工作频率迅速上升，而且时钟网络的功耗将占据芯片总功耗的大部分，由单一系统时钟同步全芯片的工作将极其困难。在这种技术背景下，片上网络n o c ( n e t w o r k o n - c h i p ) 应运而生。片上网络就是将宏观计算机网络的技术移植到芯片设计中来，各个通信节点之间通过网络的方式相互连接，采用基于分层方法来替代原先的传统总线，实现了处理单元( i p核) 与通信结构( 网络) 的分离。但片上网络并不是计算机网络技术的简单复制和移植，由于芯片在功耗和面积上存在限制，片上网络又有其独特的特点。n o c 的片上通信技术不仅具有良好的可扩展性，还提供了很好的并行处理能力，能够解决片上处理器规模变大时总线结构所产生的一系列问题，在芯片上势必成为替代总线通信方式的一种理想的解决方案。1 2 片上网络结构与优势片上网络的概念刚被提出，就引起了国际上各大研究机构的重视，很快成为了热门国际前沿学术领域。一个片上网络的基本结构应该包括i p 核、路由器、网2片上网络面向应用路由算法的研究络接口和链路。i p 核即处理单元，可以是现有意义上的c p u 、s o c ，也可以使各种专用功能的m 核和存储器等等，各个i p 核可以是同构的，也可以是异构的；路由器通过路由算法协议为分组选择路径，实现路由策略；网络接口用来分离网络通信和计算单元( i p 核) ；链路实现节点之间的连接，包含了一个或多个逻辑、物理信道。图1 1 给出了一个4 x 42 dm e s h 拓扑结构的片上网络，包含了一个片上网络的所有基本组成，该结构没有采用总线，而是采用了一般m e s h 型网络拓扑结构，通过一定的路由算法可以实现任意两个i p 之间的通信，可采用分组交换、电路交换或其它的交换机制，使用同步异步或其他逻辑来实现。图1 14 x 42 dm e s h 拓扑结构的片上网络片上网络较传统的总线型片上系统有以下优点：( 1 ) 较强的可扩展性。n o c 的网络拓扑结构使其具有很好的可扩展性，并且具备并行通信能力，使得通信带宽较总线型高出几个数量级，解决了总线型片上系统的地址资源限制，更适用于大型集成系统。( 2 ) 网络中每条链路较短，仅连接有限数量的节点，这使得每条链路上的时延、能耗得以减小，信号完整性得到加强。( 3 ) n o c 中各个口核路由器之间通过短线互连，可以使用全局同步、局部异步技术【4 】【5 】【6 1 ( g l o b a l a s y n c h r o n o u sl o c a ls y n c h r o n o u s ，g a l s ) 来避免由全局时钟同步带来的时钟倾斜等问题和网络规模扩大后时钟同步困难问题，从而降低了芯片的功耗。由此可见，n o c 具有总线式结构无法比拟的优势，在不久的将来，n o c 必将代替总线式结构成为下一代主流的片上多核互连结构。1 3 论文研究的主要意义n o c 作为一个崭新的集成电路设计理论体系，在国际上刚刚起步。随着技术的不断发展，越来越多的研究机构意识到n o c 的潜力，纷纷投入到其中并推动着第一章绪论3它的发展，使得n o c 成为了一个十分活跃的技术前沿领域。国际上有瑞典皇家理工学院、斯坦福大学、普林斯顿大学等，国内的合肥工业大学、西北工业大学、中科院、西安电子科技大学、国防科技大学、上海交通大学、电子科技大学、清华大学、浙江大学等高校近年来也围绕n o c 的相关技术开展了广泛的研究和实践。随着应用种类的不断增加，片上需要集成大量的异质i p 核，基于规则拓扑的片上网络结构无法体现特定应用的特征，等结构多应用于由同构组件组成的网络，造成片上资源的浪费。例如m e s h 、t o r u s当用于集成大量异质i p 核的特定应用系统时，将会出现分组路由跳数多、端到端时延大、功耗高等方面的问题，主要原因在于：1 ) 实现某具体应用的i p 核尺寸大小不一，将这些p 核布置在规则的拓扑结构上会造成芯片面积和功耗的浪费；2 ) 所要实现的某种具体应用的i p 核之间的通信关系已知且固定，而且并非所有组件间都有通信关系，规则拓扑结构没有考虑到网络中组件通信的区域特性，因此规则网络将会增加网络的连线数量，而且也会因为路由跳数过多而使得分组端到端时延较大。所以根据具体的应用来设计优化功耗和性能等参数的面向应用的拓扑结构便显得尤为重要。面向应用的片上网络能够针对特定应用下口核之间流量的特征，结合异质i p核的特点进行互连系统设计，其特点主要在于i p 核的尺寸不一以及i p 核之间的通信关系和流量的不对等性，这样的系统能够在片上资源消耗最小的情况下取得良好的性能，因此面向应用的片上网络设计已经逐步成为解决异质片上系统多核互连设计的主要方法。片上网络当前研究比较成熟的技术是针对通用芯片设计提出的i p 核间互连。然而，随着应用种类的不断增加，基于通用芯片设计的互连结构无法充分利用特定应用这一特征，同时，还会造成片上资源的巨大浪费1 7 。然而，面向应用片上网络互连设计正是针对特定应用下m 核之间的流量特征进行的互连系统具体设计，它可以在片上资源消耗最小情况下使得系统性能最好。因此，面向应用片上网络设计已日益成为解决片上系统多核互连设计的主要方法。面向应用片上网络设计主要包括网络结构设计和网络协议设计两大部分。在网络结构设计中最关键问题就是拓扑结构的设计，因为拓扑结构对面积、能耗、网络性能等都有直接影响。如拓扑结构中路由器、网络接口、链路等的数量直接决定了芯片面积的使用，而这些在很大程度上依赖于网络的应用，它需要满足具体应用。对于面向应用系统，其应用特征主要体现在核流 虱( c o r eg r a p h , c g ) q b t s ，它描述了实现特定应用i p 核的种类及其之间的通信关系，同时给出了i p 核之间的流量特性。在拓扑结构和c g 的基础之上，面向应用系统设计就需要采用高效的映射算法将c g 中所有i p 核映射【1 0 1 1 1 1 】【1 2 1 到所设计拓扑的网络节点上去，从而构成面向应用的片上网络结构。网络协议规定了片上网络数据传输的方式、时机和路径等机制，其中最重要4片上网络面向应用路由算法的研究的协议之一是路由算法。路由算法给出了数据从源口核传输到目的i p 核所走的路径选择策略。它需要针对具体拓扑结构进行具体设计，一般需要考虑网络的连通性、死锁和活锁、自适应性、负载均衡性、容错性等问题。路由算法在很大程度上决定了数据在网络的传输时延及网络吞吐，为此，一个高效的路由算法必须能够使网络具有良好的时延和吞吐性能。上面介绍的那些路由算法是在网络通信流未知的情况下只根据网络拓扑特性来设计，而在面向应用片上网络领域，使用上面介绍的通用路由算法没有很好的利用具体应用已知的信息来，从而限制了网络性能的提升，在第三章我们将介绍片上网络面向应用路由算法的设计方法和主要步骤。1 4 论文主要工作与安排本文从片上网络的技术背景入手，经过阅读大量文献，对片上网络相关基础知识有了初步的了解，通过总结掌握了片上网络通用路由算法和面向应用路由算法的研究动态。本文将针对面向应用的片上网络路由算法进行分析、研究和创新。本文的工作安排如下：第一章：绪论。本章主要介绍片上网络产生的技术背景，由于传统总线型片上系统s o c 在结构和性能上无法满足越来越多的m 核集成到芯片上，基于网络互连的片上系统n o c 应运而生，之后简要地提出针对具体应用来实现片上网络的必要性。第二章：片上网络关键技术简介。本章从交换机制、虚信道和路由算法等方面介绍了片上网络的基本概念，并且介绍了当前在片上网络中经常使用的各种路由算法，最后介绍了面向应用片上网络的设计组成部分。第三章：片上网络面向应用路由算法。本章先介绍了面向应用路由算法相关的基本概念，介绍并分析对比了当前提出的三种经典路由算法和三种通用路由算法。第四章：新型面向应用路由算法。本章针对现有路由算法中网络中间区域产生环路的概率很大并且算法对网络通信流流量不均衡等缺点，提出了一种新型的面向应用路由算法，通过限制边缘通信流的传输路径和根据流量大的通信流路径尽可能多的原则来破除依赖图中的环路等方式优化网络性能，并介绍了这个算法的设计思路和实现方式。第五章：总结与展望。本章对全文做出了总结，分析了工作中存在的不足，并在此基础上展望未来工作重点和努力方向。第二章片上网络关键技术简介5第二章片上网络关键技术简介自上个世纪9 0 年代末，片上网络的概念被提出后，国际上展开了对其各个方面的研究，主要是借鉴并行计算机的互连网络，所以片上网络和并行计算机互连网络有很多相似点，如交换机制路由算法等等基本概念，但在规模和功耗等方面又有不同的限制。本章将从交换机制、虚信道和路由算法等方面介绍了片上网络的基本概念，并且对当前在片上网络中经常使用的各种类型路由算法进行了简要介绍，最后提出面向应用片上网络设计的组成部分。2 1 交换机制片上网络经常使用四种类型的交换机制：电路交换( c i r c u i ts w i t c h i n g ) 分组交换( p a c k e ts w i t c h i n g ) 、虚切通交换( v i r t u a l c u t - t h r o u g hs w i t c h i n g ) 和虫孔交换( w o r m h o l es w i t c h i n g ) 。下面分别介绍这些交换机制的特点。2 1 1 电路交换电路交换1 1 3 j 最早产生于公共交换电话网( p s t n ) ，是一种面向连接的交换机制。在开始通信之前，一般要通过一个建链分组按照一定的路由规则选路，然后建链，同时预定所经过路径的信道资源。收端在成功收到这个信息头后将沿原路返回一个应答，发端收到这个应答后便开始传输数据。数据部分在网络中传输时将独占此路径中各段链路的整个带宽，并且不需要再做路由选择。当通信结束后，发端向收端发出终止通信的要求，并沿路拆链，释放对各段链路的使用权。这就是电路交换的主要工作过程，工作过程时序图如图2 1 所示。采用面向连接的方式可以保证片上网络一些特定业务的服务质量。在多媒体业务中，分组一般数量较少，但分组较长，所以采用电路交换方式较有优势。因为当分组较长时，数据部分的传输时间远大于路径建立的时间，并且由于独占整个物理带宽，因此可以保证高吞吐和低时延。2 1 2 分组交换分组交换是先将数据完全存储，然后进行路由决策，最后再转发到下一节点的一种交换机制。它是在片上网络中最早使用的一种交换机制，片上网络中的分组交换主要以分组为流控单位，每个分组的大小可以不等，并且每个分组有一个分组头，存有源节点地址，目的节点地址以及其它一些控制信息。路由节点接收到一个分组后，先将整个分组存储在缓存器中，从分组头中获取所需的路由信息，由路由器的路由决策单元选择一条输出通道后，置位交叉矩阵中的内部连接，如果下一跳路由节点中有足够的空间存放此分组，就将此分组转发到下一路由节点。6片上网络面向应用路由算法的研究其工作原理如图2 2 所示。时间图2 1 电路交换工作过程时序图图2 2 分组交换工作过程时序图图2 3 中显示了分组交换机制的一个5 微片大小分组在4 个信道之间传送的时隙图，从图中可以看出缓存分配是以分组为单位，整个分组存到当前节点后再将其发送到下一节点。由图可知，分组交换的时延与跳数成正比，因此它无法很好的适应网络规模的扩展。并且在每个路由节点中要提供至少一个分组大小的缓存资源，因此会使芯片面积增加。0名1263olz 34 567891 01 l 1 21 3 1 41 31 61 71 8l 譬c y c l e图2 3 分组交换5 微片大小分组时隙图2 1 3 虚切通交换虚切通交换【1 3 】也将分组进一步划分为更小的微片，大小通常为若干个比特，并将所有的微片按顺序排好，将所需的路由信息放入第一个微片中( 称作头微片，后续微片分为数据微片和尾微片) 。由于路由信息只包含于头微片中，所以路由节点没有必要等整个分组都接收完以后再进行转发。在无阻塞的情况下，路由节点收到头微片后，从中读取路由信息，然后由路由决策单元负责选路，如果输出通道空闲，则将头微片转发出去，后续微片紧随头微片向前路由，从而大大缩小了分组交换的时延。当头微片所请求的输出通道全忙时，头微片就地缓存在中间节点，随后的数据微片也依次前往并缓存在该节点中，如果阻塞的时间足够长，则整个分组的微片都将存放在该中间节点中，因此像分组交换一样，中间节点也要提供至少一个分组大小的缓存资源。虽然运用虚切通和分组交换的路由节点缓存器大小相同，但采用虚切通交换第二章片上网络关键技术简介7机制的芯片面积要小于运用分组交换的芯片面积。这是因为分组交换需要“整存整取”，所以在路由器中需要加入一个复杂的分组结束探测装置来接收变长度的分组。在没有发生完全阻塞的情况下，虚切通交换只激活一个或几个微片大小的缓存资源，而分组交换要激活全部的缓存资源，因此在吞吐量相同的情况下，虚切通机制的能耗低于分组交换。2 1 4 虫孔交换虫孔交换1 1 4 1 5 】是当今片上网络中的主流交换机制。它和虚切通交换的基本思想大体相同，只是二者在发生阻塞时所表现出的行为不同。在虫孔交换中，微片的种类分为头微片，数据微片和尾微片，并且允许一个分组只由一个微片组成。当头微片发生阻塞时，分组中的所有微片都将停止前进，也就是说发生阻塞时头微片缓存在当前节点，数据微片就地缓存在其后的若干个中间节点中。每个路由节点只需提供一个微片大小的缓存资源。在无竞争的情况下，虫孔交换和虚切通交换的时延性能基本相同，并且可以通过在每个路由节点适当增加缓存数量来进一步提高吞吐量。优良的时延性能，较小的缓存要求以及大吞吐量是虫孔交换最突出的优点。虫孔交换也有自身的一些缺点，像分组交换一样，虫孔交换也是一种无连接的交换机制，不能运用到分组较长的多媒体应用当中。当发生阻塞时，虫孔交换中的各个微片将会就地阻塞，从而使信道相关性扩展到了多个相邻的节点，并且将大大增加其它分组被阻塞的可能性，因此使死锁问题变得更加复杂，并且在网络负荷较重时，时延将变得不可预测。图2 4 示意了被阻微片导致其它分组无法前进的例子。在图中，分组a 的头微片被分组b 的数据微片阻挡，导致a 的所有微片就地阻塞，从而进一步阻塞了请求2 号路由器缓存资源的分组c 。可以运用虚信道流控技术缓解上述阻塞问题，在一定程度上提高虫孔交换机制的吞吐量。一头微片图数据微片一占用- - 请求图2 4 虫孔交换阻塞示例2 2 虚信道的引入虚信道技术流控最早由文献n q 提出，一种方法是，一条物理链路可以支持多8片上网络面向应用路由算法的研究条逻辑链路或虚信道并多路复用该物理链路。物理链路协议必须能够区分使用物理链路的虚信道。最初引入虚信道技术的目的是为了解决虫孔交换网络中的死锁问题。虚信道的主要优点是可以避免死锁、优化物理通道利用率、降低阻塞概率、降低分组时延、增大网络吞吐量和提供区分服务。普通f i f o 缓冲器两条虚信遭并联图2 5 普通缓冲器的转换要实现一条物理通道分成两条虚信道，可以将普通的f i f o 缓冲器转换成如图2 5 所示的两对缓冲器并联的形式，也就是将一条物理信道多路复用，分解为几条虚信道，每条单向虚信道由一对独立管理的缓冲器实现。图2 6 ( a ) 示意了没有使用虚信道技术的情况下路由器r 1 和r 2 之间的连接情况，图( b ) 是添加了虚信道时的连接情况。c a ) 未使用虚信道( b ) 使用了虚信道图2 6 路由器连接对比在片上网络中使用虚信道可以解决虫孔交换机制的阻塞问题，在每个物理信道上设置多个缓存区，每个缓存区对应一个虚信道，并以时分复用的方式使用这条物理信道。虚信道的方式可以高效的使用物理信道的带宽和缓存，但需要使用额外的位或信号来区分各个虚信道，并且还需要增加一定的控制逻辑，从而加大路由器的复杂性和路由器时延【l 7 1 。虚信道的引用也可以用来解决路由算法出现的死锁问题。虚信道的使用也带来一些问题【1 8 l ：路由器处理头微片的复杂度增加；缓冲区微片数量的增加导致路由器交叉开关和仲裁单元更加复杂，使路由器的实现变得非常复杂；增大的路由器对分组的处理时延；不同的虚信道上的负载不均衡对片上网络的性能也有比较较大的影响。第二章片上网络关键技术简介92 3 路由算法概述2 3 1 路由定义路由算法确定如何将一个分组从源节点发送到目的节点，它按照一定的规则确定分组到达目的节点的路径。路由算法在很大程度上决定分组的端到端时延以及整个网络的吞吐，高效的路由算法能够使片上网络获得优良的时延和吞吐性能。设计路由算法时，经常考虑下面一些因素：( 1 ) 连通性：将分组从任何源节点路由到任何目的节点的能力。( 2 ) 自适应性：存在竞争和故障部件时，通过其它可选路径路由分组的能力。( 3 ) 死锁和活锁：确保分组不会永远阻塞或者永远在网络中游荡但到达不了目的节点的能力。( 4 ) 容错性：在存在故障部件时对分组进行路由的能力。如何在网络中存在故障节点的情况下，将分组有效地送到目的节点是容错路由设计的首要目标。为达到有效传送目的，应该尽量采用最短路径同时避免死锁的产生。( 5 ) 均衡性：网络中业务的不均衡性要求路由算法能够具有均衡负载的能力。负载均衡算法可以使交换网络中的各种资源( 包括缓存资源与链路资源) 能够得到充分利用，避免网络中某些部分资源充足，而其它部分资源紧张的现象。负载均衡算法可以通过提高资源的利用率来增加系统的吞吐率，降低分组端到端时延。( 6 ) 服务质量保证：由于网络中很多业务( 实时性分组，多媒体数据等) 对服务质量( q o s ) 有要求，因此路由算法设计中除了传统的参数外还要考虑一些q o s 参数，如链路剩余带宽，丢失率，时延抖动等。网络中q o s 路由算法需要考虑的问题有：参数的选择、状态信息的选择和路由策略。2 3 2 路由算法分类路由算法可以根据不同的标准进行分类，主要包括以下几种：按照目的地的数量：分为单播路由和多播路由。单播路由的目的地只有一个，而多播路由的目的地有多个。按照路由决策地点：分为集中式路由、分布式路由、源路由和多阶段路由。集中式路由是由路由控制中心周期性的收集各链路的状态，经过路由计算后再周期性的为网络中的各个节点提供路由表。分布式路由是网络中各节点通过交换路由信息，独立的计算到达各节点的路由。源路由是指源节点决定该消息或分组的所有路径，并在发送之前将此路由信息存于分组头中。将以上各种路由算法的特点混合后可以得到多阶段路由。在多阶段路由中，源节点计算一些目的节点，它们之间的路径以一种分布式的方式建立。按照路由是否具有自适应性：即路由算法是否能够适应网络状态的变化，分1 0片上网络面向应用路由算法的研究为无关路由和自适应路由。无关路由又可以分为确定性路由和随机路由，无关路由算法在选择路径时不考虑任何网络当前状态信息。确定性路由是在给定源和目的节点地址后以网络拓扑为依据，按照某一固定的原则进行路由。其优点是算法简单，实现容易。但是，由于确定性路由算法忽略了路径多样性因此它不能充分利用片上网络提供的链路资源，具有一定的盲目性。x y 维序路由就是确定性路由算法的典型例子。而随机路由是随机选择分组的路由路径。自适应路由算法能够根据网络当前所处的状态，对分组的传输路径进行优化，它有效的利用了片上网络的链路资源。其又可分为部分自适应路由和完全自适应路由。自适应路由算法的设计思想是在路由计算时根据网络当前所处的状态，在源节点和目的节点之间的所有可达路径中，选择一条最优的路径。自适应路由算法的优点在于能够获得更低的分组传输时延和更高的网络吞吐性能，但是它必须保证无死锁发生，且其实现复杂度也相应增加。按照选择路径是否最短：分为最短路由和绕道路由。最短路由算法只选择将分组或报文送到离目的地最近的通道，又称为最小路由，绕道路由则提供远离目的地的通道，又称为非最小路由，它具有一定的容错能力。按照应用需求是否给定：分为通用路由算法和面向应用路由算法。通用路由算法在任意应用任意流量配置下均能保证网络的连通性，具有一般通用性。而面向应用路由算法是根据具体应用流量模型而设计的，只在这个特定的应用流量模型下使用，而并不适用于其他应用下，具有特定专一性。通用路由算法设计简单，在任意流量配置下均可使用，但是网络性能较差，面向应用路由算法设计相对较复杂，而且只针对单一应用流量模型设计，但是由于应用流量模型己知，可以不考虑应用中那些并不通信的节点之间连通，只针对相互通信的节点，能使网络性能得到极大提高。需要注意的是，上述分类方法之间存在一定的重叠，一种路由算法可以既属于确定性路由，又属于最短路由。因此，对一个路由算法应进行多角度分析。2 3 3 死锁、活锁及饥饿任何系统的资源都是有限的，特别是对于片上网络这样一个资源限制较为严格的系统，避免死锁，活锁及饥饿一直是路由算法设计中首先要考虑的问题。无论哪类路由算法都应该有效的解决死锁，活锁及饥饿问题。2 3 3 1 死锁死锁形成的根本原因是对于有限资源的不合理使用，具体是指分组对网络资源的申请形成一种环形的依赖关系，构成死锁的所有分组由于无法打破这种环形依赖而各自锁定在相应的位置，无法继续路由的一种情形。如图2 7 所示，分组l在占用路由器1 资源的同时，申请路由器2 的资源，而此时分组2 占用了分组1第二章片上网络关键技术简介感嘲鋈盥瑚鋈一l 兰= = 蔓叫图2 7 死锁的形成1 ) 死锁避免死锁的发生将严重影响网络的性能，时延，吞吐等将受到极大的影响，甚至可能导致整个网络的瘫痪。因此，在路由设计中必须避免死锁的发生。主要有以下两种方法：( 1 ) 通过在路由算法中设置禁用某些资源来防止出现路径环。这类方法实现简单，硬件资源需求较少，所以在片上网络得到广泛的应用，但是不能充分利用资源，无法实现完全自适应路由。( 2 ) 引入虚信道技术，将物理信道分为若干逻辑信道，进而形成虚网络来避免死锁。引入虚信道增加了硬件实现的复杂度，虚信道调度策略会影响不同虚信道上的负载均衡性，同时虚信道的增加会增大芯片的面积。d a l l y 提出了一种通过信道依赖图来检验路由算法是否产生死锁的方法，信道依赖图( c h a n n e l d e p e n d e n c yg r a p h ) c d g 是一个以网络中各个信道为顶点以信道之间的依赖关系为边的有向图。两个顶点( 信道) 之间存在一条边表示分组经过一个信道之后可以在下一个信道中传输。d a l l y 提出并证明了一个定理1 1 9 1 ：如果信道依赖图c d g 中不存在环，那么该路由算法将不会产生死锁。根据这个定理，打破信道依赖图中所有的环将会避免死锁的发生，而去掉环中某条边( 信道依赖关系) 就可以打破这个环，所以，可以通过限制网络中某些转弯来避免死锁。例如图2 8 所示为一个3 x 3m e s h 拓扑和它在x y 维序路由算法下的信道依赖图，依赖图中的各个节点对应于m e s h 中的相应的边( 信道) ，而依赖图中的边代表各个信1 2片上网络面向应用路由算法的研究道之间的依赖关系，如g d 到d a 存在一条边，表示允许分组经过信道g d 后随即进入信道d a ，g d 到d e 不存在一条边，就是说分组经过信道g d 之后不允许进入信道d e ，这是因为x y 路由算法要求先进行x 方向的路由，直到与目的节点在同一个y 维坐标上再进行y 方向的路由。不允许经过y 方向路由之后再进行x 方向的路由。h i图2 83 3m e s h 网络和其在x y 路由算法f 的信道依赖图2 ) 死锁检测与恢复一种能够适用于任何路由算法的死锁解决方法是死锁检测与恢复机制【2 0 ，该机制中需要合理的死锁检测策略，当检测到死锁发生时，则启动死锁恢复机制。死锁检测方法最简单的方法是超时判断，它为每个分组设置一个时间限制，当分组在网络中传输的时间超过了这个时间限制，就认为网络中发生了死锁。死锁恢复一般有两种方法：( 1 ) 消极死锁恢复法，采用丢弃、偏移路由来处理死锁分组。( 2 ) 积极死锁恢复法，通过分配其它资源来传送死锁分组到达目的节点。在文献 2 1 】瞄】中使用了一种基于软件的恢复机制，采用这种机制，路由器在检测到死锁分组之后，本地节点将这个死锁分组吸收，暂时缓存在本地节点中。这样原来的死锁分组占用的资源被释放给其它分组使用，网络从死锁中恢复过来。缓存在本地节点中的死锁分组在网络有空闲的资源后，重新注入到网络中，因此不会发生数据的丢失。死锁检测与恢复机制能够与任何路由算法结合实现无死锁，所以降低了路由算法的设计复杂度，使得路由算法能够最大化的利用网络资源。但是现有基于分组等待时间判定是否发生死锁的策略较难确定时延门限数值，不合理的门限数值设定可能检测不到真实的死锁。此外，该策略也会带来额外的硬件开销。除了上面所述的死锁避免和死锁检测与恢复机制外，通过路由器结构设计也能够实现无死锁路由。在文献【2 1 1 【2 2 1 中针对2 dm e s h 片上网络结构，增加了在y 维的一条物理链路，同时将路由器内部分为左右两部分，然后分别通过路由器左右第二章片上网络关键技术简介1 3两部分实现上下方向朝左右方向转弯分组的传输，从而避免了来自不同方向的分组构成资源等待环，因此实现了无死锁路由。2 3 3 2 活锁由于分组到达目的节点所需的资源被其它分组占用，导致分组只能围绕着目的节点而永远不能到达目的地，这种情况称为活锁。这样，分组即使没有被永远堵塞，也可能无法到达目的节点。活锁的发生无谓地消耗网络资源，从外观上看来，死锁和活锁是无法区分的。活锁的发生是由于存在非最短路由，因此，活锁的避免相对比较容易，最简单的方法是限制使用绕道路由，即采用最短路径算法( s h o r t e s tp a t hr o u t i n g ) ，它规定只能使用最短路径。也可以给每个分组设置一个生存时间( t i m et ol i v e ，t t l ) ，并配备一个t 1 l 计数器。发送端对每个分组的t t l 赋一个正的初值，分组每经过一个路由器，丌l 的值就减1 ，当t t l = o 时，就将该分组丢弃。还有一种方法就是根据分组在网络中传输的时间长短设定不同的优先级，即在网络中传输时间越长的分组优先级越高，并且会被优先传递。分组在目的节点周围绕圈时，它在网络中传输的时间就会增加，优先级也会随之增加，总有一个时刻它的优先级会大于占有它所需信道的分组的优先级，从而可以解除活锁。但是这种方法和设置t t l 的方法都不能百分之百的解决活锁问题，因为可能出现同时有两个分组具有相同的优先级，或者同时有两个分组的1 几都计数到零的情况。当这两种情况发生时，活锁仍可能发生。2 3 3 1 饥饿如果网络资源紧张，某个低优先级的分组由于所请求的资源总是分配给其它高优先级分组，从而导致该分组的永远不能到达目的地，这种现象叫做饥饿。饥饿现象是三种情况中最简单的一种，避免的方法就是使用正确的资源分配机制。简单的请求轮询机制就足以保证资源的公平使用。如果由于通信业务的需要必须对分组分配不同的优先级，则为了避免饿死现象的出现，必须限制高优先级分组的数目，并且要为低优先级的分组保留一部分资源。需要明确的是，死锁、活锁及饿死这三种现象并不是孤立的。随着网络流量的动态变化，一种现象的发生很可能导致另外一种现象的发生。笼统的说，使用缓存资源小的系统比使用缓存资源大的系统、流量大的网络中比流量小的网络中更容易产生这三种现象。大多数传统的避免这三种现象的策略都是以牺牲缓存资源为代价的，而片上网络对面积资源要求严格，特别是路由器缓存资源的大小，所以这类方法都不能很好的移植到片上网络中。如何运用较少的缓存资源确保无死锁、活锁及饿死是目前片上网络技术发展的关键。1 4片上网络面向应用路由算法的研究2 4 典型片上网络路由算法2 4 1 确定路由算法确定路由算法是一种常见的路由算法，它的路由路径只与源节点和目的节点有关，给定源节点和目的节点，路由路径就确定了，与当前网络状态无关。确定路由路由算法简单，在低流量、低拥塞网络环境下能获得较低的时延。但是当网络流量和拥塞增加时，性能迅速下降。在确定路由算法中，由于维序路由路由逻辑简单易实现，被广泛使用。维序路由中，每个分组一次只在一个维上路由，当在这个维上到达恰当的坐标后，才按由低维到高维的顺序在另外的维上路由。因为分组是按照严格的单调维数变化在通道内路由，所以维序路由没有死锁。按照在不同拓扑结构的网络中路由，维序路由包括了2 dm e s h 中的x y 路由和超立方中的e c u b e 路由。1 1x y 维序路由算法x y 维序路由是最简单、也最常用的确定性路由算法。分组首先在x 维上路由，当分组到达与目的节点同一列时，转向在y 维上的路由，最后到达目的节点。如图2 9 所示：源节点是a ，目的节点是b ，分组首先沿x 维到达与目的节点同一列的c 点，然后转向y 维的路由。该算法硬件设计和实现简单，在网络流量不大时，具有小的时延，并且可防死锁和活锁。图2 9 维序x y 路由算法但是，当源节点和目的节点确定时，路由路径就唯一确定，因此路径中有一条链路或节点发生故障时，分组就不能正确传输，所以该算法缺乏自适应性。同时，该算法在m e s h 结构的网络中容易造成网络中央负载过大，会产生热点( h o t s p o t ) 或热点区域。2 】e c u b e 路由算法在n 维立方体中，每个节点用n 个b i t 的二进制编号表示。每个节点有n 条输出通道，其中第i 条通道对应第i 维。在e c u b e 路由算法中，分组的头部携带目的节点的地址d 。当1 1 _ 维立方体的一个节点v 收到一个分组时，e c u b e 路由算法第二章片上网络关键技术简介1 5计算路由向量c = d o v ，其中0 是逻辑运算中的异或运算。如果c = o ，说明分组到达目的节点，则传向i p 核，否则，分组将被送往第k 维的输出通道，其中k 是c 最右边( 或者最左边) 为l 的那一维【2 3 1 。、d i m 2j，( a )i m li m 40 1 l o0 1 1 l1 1 1 01 1 1 l( b )图2 1 0e - c u b e 路由算法举例来说，如图2 1 0 所示，一个由s = 0 1 1 0 产生的分组的目的节点为d = l 1 0 1 。首先计算路由向量c l = 蜘s = 1 1 0 1 0 0 1 1 0 = l o l l 。取最右边不为零的一位为k ，则k = l ，说明这个分组将会被送往第1 维上的通道。然后到达v l = 0 1 1 1 ，再计算路由向量c 2 = d o v l = 1 1 0 1 0 0 11 1 = 1 0 1 0 ，得到k = 2 ，然后把分组送到2 维的通道上。随即到达v 2 = o 1 0 1 ，再计算一次c 3 = d o v 2 = 1 1 0 1 0 0 1 0 l = 1 0 0 0 ，得到k = 4 ，接着把分组送到第4 维的通道上。最后到达目的节点d = 1 1 0 1 。最终，得到的路由过程是：0 1 l o 专0 1 1 l 寸0 1 0 l 专1 1 0 l从上面的路由过程可以看出，虽然维序x y 路由与e - c u b e 路由是在不同维数的网络中路由，但是他们有一个共同点：即一次只在一个维上路由，直到在该维上到达与目的节点相同的节点，再按照维数单调变化的顺序该变方向在其它维上路由，维序x y 路由是从x 维改变到y 维的顺序，e c u b e 路由是从低维到高维( 或从高维到低维) 的顺序。2 4 2 随机路由算法随机路由算法基于概率将分组发送到目的节点，并假定每个分组迟早都能达到其目的节点，算法简单，且能容错，但其速度慢，并且占用大量的网络资源。为了避免分组在网络中无限制地游走，算法规定了分组的生存时间t t l 。分组在网络中随机路由时都有一个最长时间限制，超过此时间，分组将被丢弃。1 ) 洪泛随机路由算法概率洪泛路由算法( p r o b a b i l i s t i ef l o o d ) ：这是最简单的随