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

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

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

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

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

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

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

1)算法为每条物理通道设置4条虚通道，用VC_{dimension，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网络中，对每条物理通道的虚通道进行排序，用C_i,j表示第i维上的所有序号为j的虚通道构成的集合，它可分为正向的虚通道集合C_i,j 和逆向的虚通道集合C_i,j-平面自适应

路由算法定义n一1个自适应平面A₀至A_n-1，每个平面由相邻二维上的虚通道构成：A_i=C_i,0 C_{i 1,1} C_{i 1,2，}0≤i≤n-2。算法可分为两级(高层和低层)：

1. 高层算法：(在自适应平面之间)1) For i=0，i<(m-1)，i do在A平面中自适应地路由消息趋近目的结点(见低层算法)end。2)在上述过程结束后，若消息还未到达目的结点，则通过A_n-2=C_n-1,0中的虚通道路由消息至目的结点。

2. 低层算法(在自适平面内)：

自适应平面A包含虚通道集合C_i,0，C_{i 1,1}和C_{i 1,2}在A内消息在第i维和第i 1维上趋近目的结点，自适应地路由。为避免死锁，将消息分为两类，一类是在路由过程中需增加第i维地址的称为增向消息，另一类需减小第i维地址的称为减向消息。同时，将A中的虚通道分成两个单独的虚拟子网：增向子网(包括虚通道集合C_i,0 和C_{i 1,1})和减向子网(包括虚通道集合C_i,0-和C_{i 1,2})。这样，增向消息在增向子网上路由，减向消息在减向子网上路由，每一消息都能在相应子网中自适应地趋近于目的结点。当消息到达的中间结点的第i维地址与目的结点的第i维地址相等时，在A内的路由过程结束，转向下一个高层步骤。

多层卫星网络中的路由策略不同于传统的静态路由。虽然星座拓扑是周期性和确定性的动态路由能够动态地维护路由表并适时地交换路由信息。自适应路由策略需要知道网络中每条ISL上的长度和通信量，自适应地选择符合有效性和可靠性要求的最优路径。路由计算应用离散化的方式在每一个固定时刻t_k计算路由和更新路由表，t_k=kΔt，k=0,1,2,......,K−1并认为在时间区间Δt内网络拓扑结构不变，路由恒定采用固定时间切换策略在路由表更新同时发生切换。

为了进行网络分析需要如下假定：

1. 网络卫星相互独立；

2. 每颗卫星节点承担不同业务负载按照业务模型而定；

3. 每个卫星节点承载的业务独立业务量与卫星覆盖的范围大小和地理位置相关；

自适应路由路由算法

路由算法采用Bellman-Ford后向路由算法最优路径的判则为该路径的综合权重(TPW，totalpathweight)TPW表示了一条路径的时延和带宽占用综合性能，考虑的也是有效和可靠综合性能。TPW由三部分组成，上行链路时延D_u、下行链路时延D_d和路径上每个ISL_wi的链路权重LW_wi，表示路径上ISL的集合W={w₁,w₂,.......,w_i,......,w_ns-1}，|W|=n_s−1表示该条路径包含n_s−1条ISL，n_s为该路径上的卫星数量(包括源卫星和目标卫星)。其中地面源和目标位置确定之后，采用仰角最大接入方案选定源卫星和目标卫星。

其中D_wi表示ISL_wi的传输时延，W_wi表示平均星上处理和交换时延，f是信息量权重参数。D_u、D_d和D_wi的求解只需知道卫星空间位置坐标，用链路长度除以传输速度即可，无需冗。

根据Jackson原理，针对数据包业务，可以将每条ISL看成单服务窗混合制排队模型M/M/1/m，数据包到来的间隔时间服从负指数分布，参数为β；服务时间是参数为μ为负指数分布，每条ISL有m个数据包排队容量。当系统中已有m个数据包时，新来的数据包不再进入排队。数据包被丢弃，有

ρ=β/μ

数据包的平均处理和交换时延为

自适应路由策略步骤

多层卫星网络中的路由策略步骤如下：

步骤1设定基本参数，网络初始化

步骤2固定一个时刻t_k，在该时间区间t求解卫星轨道参量，计算卫星位置坐标和ISL长度，建立网络拓扑结构

步骤3按照设定的业务模型，计算MLSN的ISL负载

步骤4根据排队理论，计算数据包星上处理/交换的时延，如式(14)所示

步骤5根据地面源/目标位置，寻找每个卫星层中源卫星和目标卫星(LEO、MEO和GEO源/目标卫星)

步骤6根据QOS需求和网络状态，选择传输业务的卫星层，按照Bellman-Ford路由算法寻找最优路径，缺省的业务承载卫星层为LEO层，但是如果MEO源/目标卫星相同，且LEO源/目标卫星不同，执行步骤9；如果GEO源/目标卫星相同，且LEO和MEO源/目标卫星不同，执行步骤10；否则执行步骤7

步骤7如果该LEO层路径包含ISL数量≤ISL_LEO门限，执行步骤8；如果该LEO层路径包含ISL数量>ISL_LEO门限，且MEO层路径包含ISL数量≤ISL_LEO门限执行步骤9；否则执行步骤10

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

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

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

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

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

自适应路由特征

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

自适应构件是跟随建筑信息模型（BIM）概念而产生的理念，作为某些特性参数可变的部件，贯穿于整个设计项目的CAD和CAE过程。自适应构件主要表现为Revit族，主要应用于建筑设计和水电供暖行业。但随着建筑信息模型（BIM）的深化及普及，自适应构件将更广泛的应用于如勘测、土木工程、规划等众多领域。

在BIM项目设计过程中，使用自适应构件功能，可以在整个设计项目的任意过程中，创立拥有变量参数的自适应构件。在随后的设计过程中，如需要变动，可直接修改某个参数，在不影响项目进程的情况下，修改成新的方案。

使用自适应构件功能，可以轻松的自行创建内建族文件，这些文件可沿用到另外的项目当中，而不必重新设立参数。

路由选择方法的精确描述，属于网路软件的一部分。对它的要求是正确、简单、可靠、稳定、公平和优化。

路由选择算法可分为自适应型和非自适应型两大类。自适应型的特点在于它的路由选择能在一定程度上随网路运行状态（如流量和拓扑）而改变，可避开出现异态的节点或链路。非自适应型采用静态路由选择算法。常见的非自适应型有扩散式、随机式、固定式等；而自适应型有集中式、孤立式、分布式等。

固定式是一种应用范围比较广的非自适应型路由选择算法。它是根据网路拓扑和信息流量的统计模型事先确定各节点的路由表，每个节点的路由表指明从该节点出发到某个目的节点所应该选择的输出链路以及下一节点。路由表由算法确定，而在固定式中是事先预定的。

最短路径算法为最常用的算法，它寻求在源节点和目的节点之间能沿着长度最短的路径来传送分组。这里所指的“长度”赋于特别含义，既可以是实际距离，也可以是平均时延或者链路费用。长度参数是路由表的依据，如果参数值来自网路运行的当前状态，路由表变为动态生成，这样的路由选择算法就属于自适应型。

Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。Dijkstra算法是很有代表性的算法。Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。

首先，引进一个辅助向量D，它的每个分量D[i]表示当前所找到的从始点v到每个终点vi的的长度：如D[3]=2表示从始点v到终点3的路径相对最小长度为2。这里强调相对就是说在算法过程中D的值是在不断逼近最终结果但在过程中不一定就等于长度。它的初始状态为：若从v到vi有弧，则D为弧上的权值；否则置D为∞。显然，长度为 D[j]=Min{D | vi∈V} 的路径就是从v出发的长度最短的一条。此路径为(v,vj)。 那么，下一条长度次短的是哪一条呢？假设该次短路径的终点是vk，则可想而知，这条路径或者是(v,vk)，或者是(v,vj,vk)。它的长度或者是从v到vk的弧上的权值，或者是D[j]和从vj到vk的弧上的权值之和。 一般情况下，假设S为已求得的终点的集合，则可证明：下一条最短路径（设其终点为X）或者是弧(v,x)，或者是中间只经过S中的顶点而最后到达顶点X的路径。因此，下一条长度次短的的长度必是D[j]=Min{D | vi∈V-S} 其中，D或者是弧(v,vi)上的权值，或者是D[k](vk∈S)和弧(vk,vi)上的权值之和。

算法描述如下：

1）arcs表示弧上的权值。若不存在，则置arcs为∞。S为已找到从v出发的的终点的集合，初始状态为空集。那么，从v出发到图上其余各顶点vi可能达到的度的初值为D=arcs[Locate Vex(G,v),i] vi∈V

2）选择vj，使得D[j]=Min{D | vi∈V-S} 3）修改从v出发到集合V-S上任一顶点vk可达的最短路径长度。