3D Torus互连网络结构下的单播自适应路由算法研究

legumen

               
打算把上学期写的课程论文，挨个贴出来，一方面是学习回顾与总结，另一方面大家有谁用的着的可以看看（有些都是看了一段时间的英文资料和一些书籍才整出来的）。大家都造过课程论文，了解课程论文的出产过程，我只保证我贴出来的论文，其内容不纯属抄袭，而且都是我看懂了的。-_-
这些文章纯属学习交流之用，如做他用责任自负。如果我侵犯了谁的权益，请您别去法院告我……提前拜谢orz
P.S.有些公示编辑器编辑的公式，以及图片可能显示不出来，我就不整成图片再排版了，如果需要原文的可以和我联系。这里要给出的所有论文都存在对提出的理论缺乏定量性能分析，或者定量性能分析不够的通病，这实在是没有办法的事情，有时候一篇论文就给10天的期限，而且往往是几篇论文的期限靠的很近，没有精力和能力来完成对理论的充分验证，让大家见笑了。
有问题的地方请大家指正。



3D Torus互连网络结构下的单播自适应路由算法研究


摘要：拓扑结构和路由算法是影响并行分布计算系统网络性能的重要因素。针对在商用产品中应用取得成功的3D Torus网络结构，基于维序路由算法和DP协议，设计了一种单播自适应最小路由算法，再结合随机路由算法的优点，对算法进行改进。该算法使用多路径路由对网络的负载平衡进行了增强，预期可以提高网络吞吐量；同时它具有报文保序性；是一种无死锁算法。
关键词：3D
Torus；DP协议；路由算法；分布并行计算系统；
1  引言
直连网络（Direct Interconnection Network），简称DIN是一种常见的网络拓扑形式 ,已经广泛应用于多处理器系统（Multi-processor）,多计算机系统(Multi-computer)，以及集群系统（cluster）中。网状（Mesh）网络是人们较早研究的一种直连网络。它结构规则，简单易于实现。但是Mesh结构不对称，会极大地影响网络性能。Torus环网是一种完全对称的直连网络拓扑形式，近年来针对它的研究越来越多[1,2]。Torus网络具有很多优秀的网络特性，如规则对称性，路径多样性以及良好的扩展性。因此它广泛应用于许多商用系统中，例如，IBM公司的Blue Gene/L[3]，Cray公司的T3D/T3E[4]都采用3D Torus网络；另一家通信设备制造商，Avici公司在其推出的世界上第一台太比特路由器中也采用Torus网络作为其交换网络拓扑[5]。
路由算法是决定网络性能关键因素之一。避免活锁和死锁一直是路由算法设计中考虑的首要问题。其中，活锁是指分组总不能到达目的的节点的情况，通过采用最短路径算法即可避免活锁的产生[1]。而死锁是指分组对网络资源的申请形成一种环形依赖关系,构成死锁的所有分组由于无法打破这种环形依赖而无法继续路由的一种形式。
通过在路由算法设计中破坏资源的环形依赖关系，可以达到无死锁的目的。例如，广泛应用于实际系统中的维序路由算法（Dimension Order，简称DO）[1]。该算法简单易于实现，但是它是确定性路由算法，不能充分利用网络资源，无法根据网络状态实现自适应路由。通过使用Duato协议[6]（DP），可以以DO为基础设计出完全自适应最小路径和非最小路径的路由算法。
本文以DO为基础，使用DP协议设计了一种针对3D Torus的自适应路由算法，并改进了此算法，使其可以增强网络的负载平衡性能，并且报文具有保序性。
2  预备知识
首先介绍一些基本概念。
2.1      3D Torus
定义 1：直连网络拓扑图
可以抽象为图G，是由一个非空有限集合N和集合C构成的二元组，记为


  
  
  
  
  
  
  
  
  
  
  
  






  
  
  
  
  
  
  
  
  
  
  
  




file:///C:/DOCUME%7E1/STONEJ%7E1/LOCALS%7E1/Temp/msohtml1/01/clip_image002.gif




。其中N为直连网络的节点集，元素n∈N为直连网络中的一个节点。C为直连网络的信道集，其元素c=a,nb>，是直连网络中从na指向nb的单向信道。
定义 2：n维Torus网络 是由k0×k1×…×kn-1个节点构成，其中ki表示第i维的节点数。网络上的每一个节点都可用一个n维向量(x0,x1,…,xn-1)表示。其中，0≤xi≤xi
-1。节点(x0,x1,…,xn-1)和节点(y0,y1,…,yn-1)相连接的条件是iff.

file:///C:/DOCUME%7E1/STONEJ%7E1/LOCALS%7E1/Temp/msohtml1/01/clip_image004.gif


i使

file:///C:/DOCUME%7E1/STONEJ%7E1/LOCALS%7E1/Temp/msohtml1/01/clip_image006.gif


，而

file:///C:/DOCUME%7E1/STONEJ%7E1/LOCALS%7E1/Temp/msohtml1/01/clip_image008.gif


j≠i，有xj=yj。图1给出一个4元3立方3D Torus网络的例子。
我们可以知道3D
Torus网络中的每一个节点都与三维正负方向上的其他6个邻居节点直接相连，可以分别以+X，+Y，+Z，-X，-Y，-Z代表这6个方向。当有分组的数据经过一个节点时，数据的去向有7种，除了流向上述6种方向连接的邻节点之外，还可以不再输出转发，即该节点就是分组数据的目标节点时，数据流向节点内部。

file:///C:/DOCUME%7E1/STONEJ%7E1/LOCALS%7E1/Temp/msohtml1/01/clip_image010.jpg
图1 4×4×4
3D Torus结构示意图
2.2     
虫孔路由（Wormhole Routing）和虚通道（Virtual Channel）
虫孔路由事实上是一种交换技术，它主要是用来解决互连网络中传输时延太大的问题[7]。在采用虫孔路由技术的互连网络中，将分组数据切分成若干微片（flit）。每个分组的头一个微片为头微片（head flit），它包含了路由信息，其他微片（体微片和尾微片）仅包含数据信息。当头微片沿着一定的路径传送后，属于同一个分组中的微片就沿着头微片走过的路径，以隧道方式（pipeline）一个接着一个依次传送。在传送时如果头微片被阻塞，则同一个分组中的其它微片分别在当前所在的节点存储。这样在每个节点上的缓存只需要存储一个或几个微片，不需要存储整个分组，这就大大降低了对缓存空间的要求。
交换网络的资源概括起来包括两类：缓存（buffer）和通道（channel）。如果为每一个通道对应一个缓存，那么在进行资源申请与管理时，这两个资源作为一个整体对使用。这种资源管理的方式导致一旦缓存数据被阻塞，即使通道闲置也不能为其他分组数据服务。为了增多相邻节点间的通道数目，又在物理线路上尽量节省资源，就产生了进行物理通道复用的虚通道技术（VC）。每个VC对应多个缓存，通过这种技术一个物理网络可以划分成不相关的逻辑网络，从而解决了上述问题。一方面，通过提高网络的连接度可以绕过网络中的拥塞节点和失效的节点。另一方面，虚通道可以为某些特定的分组提供保证通信带宽的能力。图2式VC缓存的组织形式示意图。当虫孔路由的尾微片经过某一个VC时，分配给对应分组的VC就被释放掉，可以被别的分组使用。


  
  
  
  
  
  
  
  
  
  
  
  




file:///C:/DOCUME%7E1/STONEJ%7E1/LOCALS%7E1/Temp/msohtml1/01/clip_image002.jpg
a）                     b）
图2 虚通道缓存组织形式
a）传统缓存组织形式；b）虚通道缓存组织形式
3  EDDR路由算法
本文基于DO算法和DP方法设计了一种路由算法，并在负载平衡和报文保序方面对算法做了改进，因此称该算法为EDDR（Enhanced DO and DP based Routing
Algorithm）。本章节中将对该算法进行介绍。
3.1     
定理和定义
定义 3：通道相关是指，某一报文当前缓存在某一节点a中，正在申请a的临界点b的输入通道作为输出的流向，那么就说，当前报文在节点a中占有的通道与要申请的b中的通道是相关的。把网络中相关通道以图的形式表示出来，图中的节点为通道，边表示两个节点对应的通道相关，即为通道相关图。
算法无死锁定理：互连网络I的连接路由函数R是无死锁的充要条件是：存在一个路由子函数R1，它是连接的而且在它的通道相关图中没有环路。该定理的一个引理是：若直连网络G中的所有信道可按一定规则标号，而路由算法R沿着信道序号严格递增或者递减的顺序路由分组，那么该算法R是无死锁的[7]。
3.2     
DP协议
DP协议[6]：该方法从确定性或部分自适应路由算法开始，提供完全自适应最小路径和非最小路径路由算法。当限制为最小路径时，推出的算法叫做Duato协议（DP），步骤如下：
1． 给定一个互连网络I1，为该网络选取一个现有的路由算法R1。R1必须是无死锁和连接的，它可以是确定性路由或自适应路由。对于虫孔交换，建议R1是最小路径算法。令C1为当前点上的通道集合。
2. 将每个物理通道分成一组附加需通道，令C为网络中所有通道的集合，对于从节点x到节点y的路径，令Cxy属于该路径中节点x的输出通道集合。定义新的路由函数R为：


  
  
  
  
  
  
  
  
  
  
  
  




file:///C:/DOCUME%7E1/STONEJ%7E1/LOCALS%7E1/Temp/msohtml1/01/clip_image002.gif


也就是说，新的路由函数可以使用所有的新通道，或者是R1提供的通道。选择函数可以以任何方式定义。但是建议给属于最小路径的新通道较高的优先级。在虫孔交换中，建议限制R只使用最小路径。
3. 对于虫孔交换，确认的R1扩展通道相关图是无环的。如果是无环的，则算法有效；否则取消并返回步骤1。
3.3   
适用于Torus网络的确定性路由算法
针对环网，Dally和Seitz提出了一种无死锁确定性路由算法的设计方法[7]。考虑某个连接路由函数和它的通道相关图D，该方法使用虚通道技术，在D中加入几条边用以把解开相关环，这样就在虚通道间建立了全序关系，并将它们加以编号。每当一个物理通道分成两个虚通道解开一个环时，要引入一个新的虚通道，并为新加的虚通道赋予不同的值作为相应索引，以建立虚通道间的次序。如下例子说明这种方法如何应用于1D Torus（Ring）以及高维的Torus（k元n立方）。
考虑一个4节点的单项环，节点记为ni，i={0,1,2,3}，每个相邻节点之间由一条单向通道相连。令ci，i={0,1,2,3}为节点ni的输出通道。这样，定义一个路由函数：如果当前节点ni等于目的节点nj，则存储报文。否则使用通道ci，

file:///C:/DOCUME%7E1/STONEJ%7E1/LOCALS%7E1/Temp/msohtml1/01/clip_image004.gif


。图3（a）显示了该网络。图3（b）是其对应的通道相关图，图内包括一个环。于是，将物理通道ci分成c0i和c1i两个虚通道，如图3（c）所示。虚通道按其索引排序。路由函数被重新定义，严格按照升序方式使用虚通道。新的路由函数描述为：如果当前节点ni等于目的节点nj，则存储报文。否则，如果j，使用虚通道c0i；如果j>i，使用虚通道c1i。图3（d）给出了该路由函数的通道相关图。可以看出，此时，由于使用虚通道c03可到达节点c0，环被解开了。图中没有通道c00和c13，因为它们永远不会用到。
该算法可以进行扩展，使其适用于单向k元n立方体。例如，对于k元3立方网络来说，将每个物理通道分成两个虚通道。通道标识为cdvi，这里d={0,1,2}，表示通道穿过的维度；v={0,1}指名虚通道的编号；i={0,…,k-1}，指出相应环中的位置。路由函数按维度升序进行路由，在每一维内使用用于环的路由函数，属于维序路由算法。
只需简单的对每个环的两个方向都使用该算法，就可以将算法扩展到双向通道上的Torus网络。由于报文只沿最小路径路由，一个方向的通道和另一个方向的通道之间不存在相关。因此，该算法是无死锁的。

file:///C:/DOCUME%7E1/STONEJ%7E1/LOCALS%7E1/Temp/msohtml1/01/clip_image006.jpg
图3 单向环及通道相关图
3.4     
EDDR算法
首先，针对3.3节中提出的适合双向3D Torus结构的确定性路由算法，使用DP协议来定义一个完全自适应最小路由算法。在每个物理通道上增加一个新的虚通道（每个方向一个）。新的虚通道可用于完全自适应最小路由。因为，此时扩展通道相关图是无环的，所以最终路由算法是无死锁的。由于该算法在双向环上适用，一些虚通道将永远不可能被使用，因此可以去掉。但是这种优化会导致网络中不同的节点采用不同的路由器。为了进一步讨论的方便，我们暂不做此方面的优化工作。现在，已经得到了一个完全自适应的最小路由算法，考虑对当前算法再做进一步的改进。
设计3D Torus网络中的报文路由算法面临以下两个问题：1.多路径负载均衡。3D Torus网络的一个重要优点就是能够提供比较多的冗余路径。路由算法应能有效地利用这些冗余路径平衡负载，减少拥塞发生的可能性，提高交换网络的吞吐率和可靠性。2.报文保序。报文乱序会影响TCP连接的性能，因此，虽然没有严格地禁止在路由器中出现报文乱序现象[8]，但是为了提高整个网络的运行效率，要求路由器能够避免报文乱序[9]。因此属于同一个流的报文经过交换网络不能乱序。
3D Torus网络中具有代表性的两个路由算法是：
1．   
随机路由算法
选择源节点和目的节点之间所有等价路径中任意一条作为报文的路径，这样从一个节点到另一个节点去的报文可以在所有的等价路径上平衡负载。这种方法不限制报文在不同路径上进行负载均衡的自由度，可以最大限度地利用交换网络中的冗余路径提高吞吐率，但是无法保证报文不乱序。必须在目的节点处进行报文重定序，这样增加了额外的开销且增大了报文的延迟。
2．   
维序路由算法
为每一个报文按照固定的维序（例如按照XYZ维序）确定路径，这样从一个节点到另一个节点去的所有报文经过的路径完全相同，从而保证不乱序。这种方法限制网络中任意节点对之间的报文在固定路径上传输，节省了报文重定序的开销，但是无法利用交换网络中的冗余路径平衡负载，当某些节点对之间产生突发流量时，系统中易出现“热点”，可能在某些节点处产生拥塞，导致整个交换网络的吞吐率急剧下降。
结合如上两种算法的优点，希望EDDR算法增强其网络负载平衡，并且使报文具有保序性，节省下因报文重定序而带来的资源开销。目前为止EDDR已经是多路径的算法，但是不具备报文保序性。为此，需要设计一种路径选择的策略来改进算法，该策略应该使得所有同组数据的报文使用相同的路由。可以在源节点处对报文进行Hash分类，限制同类报文走相同路径。其主要想法是：
1）. 在报文注入网络的时候，计算源节点(x1,y1,z1)和目的节点(x2,y2,z2)之间的距离向量(Δx,Δy，Δz)。使用源节点(x1,y1,z1)、目的节点(x2,y2,z2)、距离向量(Δx,Δy，Δz)，以及报文所在的分组标识号进行Hash操作，得到一个Hash Code。将该Hash Code和距离向量信息添加到路由信息域中。
2）. 在网络路由的时候，使用一个输出维度选择函数，根据Hash Code选择距离向量中维度分量不为0的部分中的具体一维，作为输出指向。如前文2.1部分所述，节点有7种路由方向，所以在输出维度选择函数中，如果发现距离向量的所有分量都为0，说明当前节点就是目的节点，此时把路由输出指向节点内部；否则，设计一个函数，用Hash
Code，所有不为0的分量维度号，以及分量上的数值，选定一维。根据选定的维度的数值正负情况，将该维度上的数值减1或者加1后更新到路由信息域中。现在给出一个简单的输出维度分量选择的函数例子：
假设Hash
Code为H，Δx、Δy、Δz中不为0的分量个数为d,d∈{0,1,2,3}。则函数可设计为：


  
  
  
  
  
  
  
  
  
  
  
  




file:///C:/DOCUME%7E1/STONEJ%7E1/LOCALS%7E1/Temp/msohtml1/01/clip_image002.gif


此处仅给出一个简单的例子，需要进一步的研究以设计更好的Hash函数。另外，如果考虑粗粒度的Hash分类，可以只在报文注入时计算一次路径，即用Hash Code来表征(XYZ,XZY,YXZ,YZX,ZXY,ZYZ)6种排列组合中的一种，在节点路由时按照Hash Code来查表获得维序排列方式，再按该排列方式来依次在3个维度上路由。此种粗粒度的划分，相当于只在这六条路径上进行负载平衡。
4  算法性能分析
在此对EDDR算法进行简单的感性分析。
EDDR算法是3D Torus网络中的单播完全自适应最短路由算法。它可以有效的进行网络负载平衡，并具有报文保序的功能。它与随机路由算法相比，增加了报文保序性；和维序路由算法相比，代价增加不多，但是负载均衡能力却得到了很大提高，有利于提高交换网络的总吞吐率。细粒度的Hash函数需要进一步研究设计，如果考虑粗粒度Hash，虽然不能提供最大程度的负载均衡，但是预计可以以较小的代价满足多路径负载均衡和报文保序的要求。
5 结束语
3D Torus网络结构是最适于新一代高性能路由器多级交换网络设计的体系结构[10]。EDDR路由算法作为一种完全自适应的路由算法，可以有效解决该类交换网络中报文路由的两个关键问题：多路径负载均衡和报文保序。预计其可以提高系统吞吐率，具有较好的性能。在Hash函数设计，以及算法模拟与性能分析方面还有许多研究可做。

参考文献
[1] Dally W, TowlesB. Principles and Practices of Interconnection
Networks[M]. San Francisco:
Morgan Kaufmann Press , 2004.
[2] Liu Guqing, Chen Zhen, Qiu Zhiliang, et al. Research on the Link
Traffic and Delay of a Direct Networks[J]. Journal of Xidian University,
2003 , 30(7) : 96-100.
[3] Adiga N R, Almasi G S. An Overview of the BlueGene/L
Supercomputer[A]. Proc of Super Computing 2002[C]. Baltimore: IEEE, 2002. 1-22.
[4] Cray Inc. http:// www.cray.com. Cray XT3 Datasheet.
[5] Gu Huaxi, Qiu Zhiliang, Liu Zengji, et al. A New Fault-tolerant
Routing Algorithm in a Novel Interconnection Network[J]. Journal of Xidian University,
2003 , 30(7) : 108-114.
[6] P.T. Gaughan and S. Yalamanchili, Adaptive
routing protocols for hypercube interconnection networks. IEEE Computer, 1993, 26(5)
: 12-23.
[7] Dally W J , Seitz C L. Deadlock-free Message Routing in
Multiprocessor Interconnection Networks[J ]. IEEE Trans on Computer, 1987, 36(5)
: 547-553.
[8] F. Baker. RFC1812. Requirements for IP Veresion 4 Routers.
http://www.faqs.org/rfcs/rfc1812.html
,
1995-06
[9] J. Bennett, C. Partridge, N. Shectman. Packet reordering is not
pathological network behavior. IEEE/ACM Trans. Networking, 1999, 7(6): 798-798
[10] 管剑波, 孙志刚, 卢锡城. 使用多级交换网络进行高性能路由器设计. 计算机研究与发展, 2005; 42(6) : 970-970
               
               
               
               
               

本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u/17503/showart_479767.html