[科普中国]-自适应路由

概述

互连网络路由器是大规模并行处理机(MassivelyParallelProeessors，MPP)系统的关键部件，其性能优劣直接影响系统性能，因而其如何高效、简洁地设计和实现对整个系统起着关键作用。

路由器根据其所采用的路由算法可分为确定性和自适应路由器两种，确定性路由器唯一确定路径、不受网络状态影响，因而实现简单，已在很多商用MPP中采用，典型的如IntelParagon中采用的2Dmesh路由器、CrayT3D中采用的3Dtorus路由器等；自适应路由器对于一对源和目的结点，视网络的工作状态，可有多条路径可选，因而有灵活性好、网络的通道利用率高和网络容错能力强等优点，正逐步为新一代的MPP系统所采用，但其工程实现难度较大，目前仅在少数商用MPP系统中得以实现(如CaryT3E)中实现了完全自适应的路由器)，对它的研究一直是国内外的热点。

路由器设计中的中心问题是路由算法、切换技术和流控策略。确定性路由算法实现简单，但网络利用率低，阻塞严重。

自适应路由算法，尤其是完全自适应路由算法消除了这种缺陷，减少了网络的阻塞延迟，提高了网络的利用率，但实现难度较大。虫孔路由(Wormholeoruting)是当今MPP系统中普遍采用的切换技术，在源结点处将要传送的消息报文划分成多个微片(Filt)，消息头微片带路由信息，当头微片所需某通道空闲时，头微片经其向前传送，通道被消息报文所占用，后续数据微片以流水方式尾随头微片经其向前传送，直到尾微片经其传送后释放该通道;当头微片所需某通道被占用而受阻时，后续微片也被阻塞、存储在路径中各相应路由器的缓冲器中。虚通道流控策略是当今普遍采用的流控方式，能有效提高网络利用率，同时避免死锁，综合采用虚通道流控与一些特殊的仲裁策略能有效提高网络性能。1

PBFAA算法PBFAA算法是一个基于平面的完全自适应最短虫孔路由算法(Planar一BasedFullyAdaptiveAlgorithm，PBFAA)。

人们对直接网络中采用虫孔路由切换技术的自适应路由算法已进行了大量研究，提出了很多算法，但它们或存在自适应性受限，或存在代价较大，或存在灵活性不够等缺点.在已有算法的基础上，以低通信延迟、高网络吞吐率和易VLSI实现为设计目标，提出了一个可扩展性好、自适应性强的基于平面的完全自适应路由算法PBFAA。

算法中将网络分成两个虚拟网VIN0和VI1I，VlN0中的虚通道按平面自适应路由策略路由消息，VIN1中的虚通道可完全自适应路由消息，由VIN0保证算法的无死锁性.由于两个网络均具有自适应性，故与已有一些较好的算法如（channel）相比，该算法自适应性更强，更能充分有效地利用网络资源，提高网络吞吐率，且容错能力更强一下面用n维mesh网络介绍PBFAA算法:

1)算法为每条物理通道设置4条虚通道，用VCdimension，label，direction来表示，其中dimension表示该虚通道沿哪一维传递消息；label表示虚通道的序号，取值0，1，2或3；direction可以为+(表示消息将沿正向传递)或-(表示消息将沿着逆向传递)。例如VC¨，一表示结点的第一维上的序号为1的负向虚通道。

2)将网络划分成两个虚拟网：VIN0和VIN1。在VIN0中使用序号从0至2的虚通道；在VIN1中使用序号为3的虚通道。

3)在VIN0中，按平面自适应路由策略选择趋于目的结点的虚通道路由消息；在VIN1中，按完全自适应最短路径路由策略选择趋于目的结点的虚通道路由消息。在两虚拟网中按相应路由策略可被选择的虚通道均称为所需虚通道，空闲的所需虚通道称为可用虚通道。

4)当一条消息的头微片到达某一结点时，如该结点是目的结点则消息被接收，否则：

a)若有可用虚通道，则对可用虚通道按最大间距输出虚通道选择策略，对相应维虚通道提出申请Req；若没有可用虚通道，则暂停提出申请，等待直至有所需虚通道变为可用再同上提出申请；

b)若申请被响应，则沿相应虚通道将消息传向邻近结点；若申请未被响应，则在下一拍重新执行同上述a)的操作，直至有申请被响应后将消息传向邻近结点。在每一中间结点上都重复执行上述操作，直至将消息传至目的结点。所谓最大间距输出虚通道选择策略是指在允许访问的通道中，对所在维的维间距(中间结点到目的结点)绝对值最大的虚通道首先提出申请，以缩小寻径区域。

VIN0中采用的平面自适应路由策略为：在n维mesh网络中，对每条物理通道的虚通道进行排序，用Ci,j表示第i维上的所有序号为j的虚通道构成的集合，它可分为正向的虚通道集合Ci,j+和逆向的虚通道集合Ci,j-平面自适应

路由算法定义n一1个自适应平面A0至An-1，每个平面由相邻二维上的虚通道构成：Ai=Ci,0+Ci+1,1+Ci+1,2，0≤i≤n-2。算法可分为两级(高层和低层)：

高层算法：(在自适应平面之间)

1) For i=0，iISLLEO门限，且MEO层路径包含ISL数量≤ISLLEO门限执行步骤9；否则执行步骤10

步骤8建立LEO卫星层最优通信路径，完成传输任务

步骤9建立MEO卫星层最优通信路径，完成传输任务

步骤10建立GEO卫星层最优通信路径，完成传输任务

步骤11统计多层网络的特征参量，分析网络性能

步骤12更新时间区间，完成新路由表计算，并完成卫星越区切换2

特征多层卫星网络自适应路由策略具有如下特征：业务通过LEO源卫星和目标卫星接入卫星系统，根据QOS需要和网络状态选择传输该业务的卫星层，如果LEO层网络资源不能满足该业务要求，就将该业务转到MEO层传输甚至GEO层传输对于地面源/目标，直接接入MEO或GEO卫星情况。因为路由算法实现简单，所以未作详细分析。另外仿真结果所示，LEO层的路径如果包含6条或7条ISL，时延将大于200ms。这时如果将该业务转移到MEO，传输时间更短，占用星上资源更少。而且如果地面源和目标位置被同一MEO或GEO卫星覆盖这，时就将该业务转到MEO和GEO传输，以减少星上资源的占用。该策略考虑时延指标和ISL带宽占用状况，最优路径选择兼顾卫星系统有效性和可靠性。2