阶数灵活的低直径大规模互连网络拓扑结构及路由方法

摘要

本发明公开了一种阶数灵活的低直径大规模互连网络拓扑结构及其路由方法，解决已有互连网络拓扑结构无法克服现有路由器工艺的缺点与不足的问题。技术方案是：整个拓扑由nq个超级路由节点按照n个簇、每个簇内q个超级路由节点、以Galaxy图的方式连接而成。每个超级路由节点中包含a个全互连的路由节点，每个超级路由节点引出ah条链路连接其它超级路由节点，n-1条链路连接Galaxy图中其它簇的超级路由节点，(q-δ)/2条链路连接同一个簇的其它超级路由节点。每个路由节点连接p个终端，引出a-1条链路连接同一超级路由节点内的其它a-1个路由节点，h条链路连接其它超级路由节点。本发明相比目前互连网络拓扑结构，具有低网络直径和灵活配置的优点，有效支持E级HPC系统。

说明书

技术领域

本发明涉及通信领域中的互连网络，具体涉及一种用于大规模互连网络的阶数灵 活的低直径拓扑结构及其路由方法。

背景技术

当下，大规模计算系统的规模已经超过几万个节点，如我国的天河2号超级计算机 系统和IBM的蓝色基因(BlueGene/Q)系统。这些大规模计算系统对系统的整体性能、构造 成本以及功耗都有严格的要求和需求。互连网络是大规模计算系统的重要组成部分，而且 在完成整个系统的设计目标中占有重要地位。端到端的网络延迟、网络带宽以及成本和功 耗开销都是用来评估互连网络的重要指标。设计网络拓扑结构对构造大规模计算系统的互 连网络非常重要。

为满足更多不同应用和规模的大规模计算系统，网络拓扑结构设计需要考虑以下 三个指标：

1.成本开销和能耗开销性价比。对于E(Exascale＝10¹⁸＝百亿亿(10²×10⁸×10⁸) Flops)级高性能计算(HighPerformanceComputing，HPC)系统，系统平台成本要求在200M 美元以下和功耗开销要在20MW以下。在整个E级HPC系统构造中，构造互连网络的成本开销 和功耗开销能占到整个系统的33％和50％。所以，一个成本开销和能耗开销性价比高的拓 扑结构对E级HPC系统必不可少。

2.端到端延迟。端到端的延迟主要决定于网络直径和实际系统的物理部署。一个 好的拓扑结构不仅要求网络直径低还要求便于部署，因此，更低的端到端延迟也是优化网 络性能的重要指标。

3.拓扑结构的灵活性。高性能计算系统因为应用需求不同，从几百到几万个节点 的规模需求也不一样。所以，拓扑结构的灵活性也是拓扑设计中的重要指标，需要拓扑结构 的灵活性可以在有限的路由器工艺下支持不同的网络规模。

但是，在有限功耗、面积约束下，满足不断增长的互连带宽及性能需求，实现大规 模、高密度、高性能的系统互连网络，完成上述目标存在一些挑战。端到端的延迟主要决定 于网络直径和实际系统的物理部署。所以，一些拓扑结构已经被提出来解决低网络直径的 拓扑结构，如：Dragonfly、HyperX、Skywalk和SlimFly等，可是这些拓扑结构在现有的路由 器工艺条件下难以实现E级计算系统。目前，构造低直径拓扑结构的都是基于高阶路由器， 但是，由于芯片的物理资源和功耗开销限制路由芯片阶数的增长，这些低直径拓扑结构难 以任意扩展规模。在电信号互连的路由芯片中，SerDes的面积、Crossbar的复杂性以及芯片 边界带宽的限制使得芯片在保证每个端口带宽的同时阶数增长困难。而且，阶数的增长会 导致路由芯片更大的功耗负担。例如，一个单向SerDes链路传输一个数据位(bit)的数据需 要消耗20pJ，那么Intel最新提出来的Omni-path架构需要在SerDes上消耗160W。因此，目前 有研究提出使用硅光子学来解决芯片带宽、电能耗等问题。Altera和Avago已经生产出一款 应用了嵌入式并行光模块MicroPOD的FPGA芯片。尽管相关光信号技术日渐成熟，但是因为 光模块聚合的限制使得每个路由芯片仍然不能引出更多的端口。随着E级计算时代的到来， 路由器阶数的问题越来越重要。另外一个挑战则是如何折中设计互连网络。为了控制系统 的复杂性，数据中心提出使用机柜规模的计算系统代替传统的模块系统，机柜规模的计算 系统可以提供高带宽，针对机柜级的应用提出灵活有效的路由机制和拥塞控制。这样的系 统同样适用于高性能计算系统的一些固定应用。但是，如何折中机柜间和机柜内部的带宽 来实现整个系统的最优性能仍是一个开放性课题。

自从FlattenedButterfly结构的提出，使用高阶路由器搭建互连网络系统是主 要手段。很多高阶拓扑也相继提出，如Fattree结构、Dragonfly结构、HyperX结构、Skywalk 结构、SlimFly结构等。高阶拓扑结构相比低阶拓扑结构能够获得更小的网络直径，比如 Torus和Mesh。然而，目前这些高阶拓扑结构采用当前工艺的路由器不能够支持E级HPC系 统。Fattree结构是最经典的高阶拓扑结构之一，可以通过添加层数来增加规模且不使用 更高阶的路由器，但Fattree拓扑结构难以扩展，且在物理实现时，布线密度和布线不规整 是其非常大的缺点。Dragonfly结构不仅网络直径低而且结合了电线通信和光缆通信的优 势减少成本开销，但是，一旦路由器阶数确定，其所能搭建的最大规模一定。HyperX结构是 一个可以灵活配置的拓扑结构，但是每一维结构上都是全互连导致扩展性受限。Skywalk结 构虽然可以支持任意规模并且限制链路的长度，但是路由策略等因素都是不可控制的。 SlimFly是直径为2能近似支持最大规模的结构，但是受限于固定的路径和网络规模。

发明内容

本发明的一个目的在于针对基于已有互连网络拓扑结构无法克服现有路由器工 艺的缺点与不足，无法支持E级HPC系统，提供一种阶数灵活的低直径大规模互连网络拓扑 结构。

本发明另一个目的是在所设计的拓扑结构上提供一种路由方法。

为了达到第一个目的，本发明采用以下技术方案实现：阶数灵活的低直径大规模 互连网络拓扑结构，整个拓扑分成两层结构，由a个路由节点全互连组成一个大的超级路由 节点作为第一层结构，超级路由节点中的a个路由节点分别记为第0路由节点、第1路由节 点、…、第t路由节点、…、第a-1路由节点，0≤t≤a-1，a、t均为整数。第二层结构则是以第一 层结构为基础，将每个超级路由节点按Galaxy图的方式连接其它超级路由节点，其中所述 的连接是由第一层结构中a个路由节点各引出的h条链路提供，h为整数。Galaxy图是一个可 以灵活配置的图，根据实际系统的配置需求，调整Galaxy图的参数配置，从而构建整个网络 拓扑。

本发明Galaxy图由参数n、q决定，n、q均为整数。

Galaxy图中有n个簇(cluster)，记为第0簇、第1簇,…,第k簇,…,第n-1簇，0≤k≤ n-1，k为整数。每个簇内有q个节点且满足其中δ∈{-1,0,1}，为整数，q个节点 分别记为第0节点、第1节点、…、第i节点、…、第q-1节点。0≤i≤q-1，i为整数。每个节点引 出(q-δ)/2条链路连接同一簇的其它(q-δ)/2个节点，并引出n-1条链路分别连接其它n-1个 簇中的节点。

每个节点用二维坐标表示，第k簇内的第i节点的二维坐标记为(a_i0a_i1…a_is… a_i(n-1),k)，第一维的n元组a_i0a_i1…a_is…a_i(n-1)表示的是当前超级路由节点分别与其他n-1个 簇有连接关系的超级路由节点的编号，i表示该节点为第k簇内的第i节点，其中a_is表示第k 簇的第i节点(a_i0a_i1…a_is…a_i(n-1),k)连接第s簇的节点(a_j0a_j1…a_jk…a_j(n-1),s)，其中a_jk＝ a_is，0≤a_is≤q-1，0≤j≤q-1，a_ik＝i，0≤s≤n-1，s、j均为整数。第二维的k表示该节点位于 第k簇内。

Galaxy图中第k簇跟第s簇两个节点之间相连的条件如下：

(1)若k<s，那么：

当且仅当a_is-a_js∈X，(a_i0a_i1…a_is…a_i(n-1),k)与(a_j0a_j1…a_js…a_j(n-1),k)相连。

当且仅当a_ik-a_jk∈X′，(a_i0a_i1…a_ik…a_i(n-1),s)与(a_j0a_j1…a_jk…a_j(n-1),s)相连。

当且仅当a_is＝a_jk，(a_i0a_i1…a_is…a_i(n-1),k)与(a_j0a_j1…a_jk…a_j(n-1),s)相连。

(2)若k＝s，那么：

当且仅当a_is-a_js∈X，(a_i0a_i1…a_is…a_i(n-1),k)与(a_j0a_j1…a_js…a_j(n-1),k)相连。

(3)若k>s，那么：

当且仅当a_is-a_js∈X′，(a_i0a_i1…a_is…a_i(n-1),k)与(a_j0a_j1…a_js…a_j(n-1),k)相连。

当且仅当a_ik-a_jk∈X，(a_i0a_i1…a_ik…a_i(n-1),s)与(a_j0a_j1…a_jk…a_j(n-1),s)相连。

当且仅当a_is＝a_jk，(a_i0a_i1…a_is…a_i(n-1),k)与(a_j0a_j1…a_jk…a_j(n-1),s)相连。

其中，X和X′定义如下，ξ为有限域F_q的生成元：

(1)如果则X＝{1,ξ²,…,ξ^q-3}，X′＝{ξ,ξ³,…,ξ^q-2}；

(2)如果则

(3)如果则

需要说明的是，在求集合X和X′时候，都需要对集合中的元素作模q运算得出的值 才是集合的内容；Galaxy图中第k簇跟第s簇两个节点之间相连条件判断时，表达式a_is-a_js等是否属于集合X或X′，也是对a_is-a_js作模q运算再判断是否属于集合X或X′，但为了表达的 简洁性，相关数学论文中没有特别说明要作模q运算[MaciejBesta等,SlimFly：ACost EffectiveLow-DiameterNetworkTopology”(一种成本有效的低直径网络拓扑Slim Fly),InternationalConferenceforHighPerformanceComputing,Networking, StorageandAnalysis2014(SC2014),第二章节第二部分]。因此，本发明中在求集合X和 X′、以及判断Galaxy图中第k簇跟第s簇两个节点之间是否相连时，没有特别说明要作模q操 作。

实际结构中，每个路由节点由三维坐标(a_i0a_i1...a_ik...a_i(n-1),k,t)表示，a_i0a_i1… a_ik…a_i(n-1)和k表示该路由节点所在的超级路由节点在Galaxy图的位置，t则表示该路由节 点是超级路由节点(a_i0a_i1...a_ik...a_i(n-1),k)的第t路由节点，而且满足每个路由节点提供 给第二层结构的h条链路满足ah≥n-1+(q-δ)/2。每个终端则由四维坐标 (a_i0a_i1...a_ik...a_i(n-1),k,t,c)表示，c表示该终端是路由节点(a_i0a_i1...a_ik...a_i(n-1),k,t) 的第c终端，p为每个路由节点所连接的终端数，0≤c≤p-1，p、c均为整数。

因此，本发明拓扑结构是将nq个超级路由节点划分成n个簇、每个簇内q个超级路 由节点、并将nq个超级路由节点按照Galaxy图的方式连接而成，每个超级路由节点中包含a 个路由节点，每个路由节点连接p个终端。每个路由节点引出a-1条链路连接同一个超级路 由节点内的其它a-1个路由节点，引出h条链路连接其它超级路由节点。那么，一个超级路由 节点引出ah条链路连接其它超级路由节点，满足ah≥n-1+(q-δ)/2，其中n-1条链路连接 Galaxy图中其它簇的超级路由节点，(q-δ)/2条链路连接同一个簇的其它超级路由节点。

为了达到第二个目的，本发明采用以下技术方案：一种基于所述阶数灵活的低直 径大规模互连网络拓扑结构的路由方法，查找报文从路由节点(a_i0a_i1…a_ik…a_i(n-1),k,t₁) 到目的终端(a_j0a_j1…a_jk…a_j(n-1),s,t₂,c)的路由包含以下步骤，其中t₁和t₂分别为路由节点 在超级路由节点中的编号，0≤t₁≤a-1，0≤t₂≤a-1，t₁、t₂均为整数：

(1)检测目前报文所在的路由节点(a_i0a_i1…a_ik…a_i(n-1),k,t₁)和目的终端(a_j0a_j1… a_jk…a_j(n-1),s,t₂,c)所在的路由节点(a_j0a_j1…a_jk…a_j(n-1),s,t₂)是否为同一个路由节点，即 检测是否满足a_ik＝a_jk、k＝s且t₁＝t₂；

若a_ik＝a_jk、k＝s且t₁＝t₂，表明报文所在的路由节点和目的终端所在的路由节点 为同一个路由节点，则将目的终端(a_j0a_j1…a_jk…a_j(n-1),s,t₂,c)作为下一跳节点，路由寻找 结束；

否则，a_ik≠a_jk或k≠s或t₁≠t₂，表明报文所在的路由节点和目的终端所在的路由 节点不为同一个路由节点，进入步骤(2)；

(2)检测报文所在的路由节点(a_i0a_i1…a_ik…a_i(n-1),k,t₁)和目的终端所在的路由 节点(a_j0a_j1…a_jk…a_j(n-1),s,t₂)是否在同一个超级路由节点内，即检测是否满足a_ik＝a_jk且k ＝s；

若a_ik＝a_jk且k＝s，表明报文所在的路由节点和目的终端所在的路由节点在同一 个超级路由节点内，则将目的终端所在的路由节点(a_j0a_j1…a_jk…a_j(n-1),s,t₂)作为下一跳 节点，转步骤(1)；

否则，a_ik≠a_jk或k≠s，表明报文所在的路由节点和目的终端所在的路由节点不在 同一个超级路由节点内，则进入步骤(3)；

(3)检测报文所在的超级路由节点(a_i0a_i1…a_ik…a_i(n-1),k)和目的终端所在的超级 路由节点(a_j0a_j1…a_jk…a_j(n-1),s)是否相连，方法是：若k<s且a_is＝a_jk，进入步骤(3.1)；若k ＝s且a_js-a_is∈X，进入步骤(3.2)；若k>s且a_is＝a_jk，进入步骤(3.3)；否则，步骤(3.1)、 (3.2)、(3.3)的条件均不满足，表明报文所在的超级路由节点和目的终端所在的超级路由 节点不相连，转步骤(4)；

(3.1)k<s且a_is＝a_jk，表明报文所在的超级路由节点和目的终端所在的超级路由 节点相连。若报文所在的路由节点(a_i0a_i1…a_ik…a_i(n-1),k,t₁)和目的超级路由节点(a_j0a_j1… a_jk…a_j(n-1),s)相连的路由节点是同一个路由节点即 其中为下取整操作，则路由节点作为下一跳，进入步骤(1)；若则将报文所在的超级路由节点 (a_i0a_i1...a_ik...a_i(n-1),k)和目的超级路由节点(a_j0a_j1...a_jk...a_j(n-1),s)相连的路由节点 作为下一跳，进入步骤(1)；

(3.2)k＝s且a_js-a_is∈X，表明报文所在的超级路由节点和目的终端所在的超级路 由节点相连。若报文所在的路由节点(a_i0a_i1…a_ik…a_i(n-1),k,t₁)和目的超级路由节点 (a_j0a_j1...a_jk...a_j(n-1),s)相连的路由节点是同一个路由节点即 其中Δ为a_js-a_is模q的值在集合X中从小到大排序的序号，则路由节点 作为下一跳，其中λ为a_is-a_js模q的值在集合X中从小到大排序的序 号，进入步骤(1)；若则将报文所在的超级路由节点(a_i0a_i1...a_ik...a_i(n-1),k)和 目的超级路由节点(a_j0a_j1...a_jk...a_j(n-1),s)相连的路由节点作为 下一跳，进入步骤(1)；

(3.3)k>s且a_is＝a_jk，表明报文所在的超级路由节点和目的终端所在的超级路由 节点相连。若报文所在的路由节点(a_i0a_i1…a_ik…a_i(n-1),k,t₁)和目的超级路由节点 (a_j0a_j1...a_jk...a_j(n-1),s)相连的路由节点是同一个路由 节点即则路由节点作为下一跳，进 入步骤(1)；若则将报文所在的超级路由节点(a_i0a_i1...a_ik...a_i(n-1), k)和目的超级路由节点(a_j0a_j1...a_jk...a_j(n-1),s)相连的路由节点 作为下一跳，进入步骤(1)；

(4)找到与报文所在的超级路由节点(a_i0a_i1...a_is...a_i(n-1),k)和目的超级路由节 点(a_j0a_j1...a_jk...a_j(n-1),s)的公共超级路由节点，寻找方法如下：若k<s，进入步骤(4.1)； 若k＝s，进入步骤(4.2)；若k>s，进入步骤(4.3)；

(4.1)若a_is-a_jk∈X，进入步骤(4.1.1)；若a_is-a_jk∈X′，进入步骤(4.1.2)；

(4.1.1)a_is-a_jk∈X，表明报文所在的超级路由节点和目的终端所在的超级路由节 点的公共超级路由节点在第k簇中，则满足a_ls＝a_jk的超级路由节点(a_l0a_l1...a_ls...a_l(n-1), k)是公共超级路由节点，其中0≤l≤q-1，l为整数；

若报文所在的路由节点(a_i0a_i1…a_ik…a_i(n-1),k,t₁)和公共超级路由节点 (a_l0a_l1...a_lk...a_l(n-1),k)相连的路由节点是同一个路由节点即 其中Δ为a_lk-a_ik模q的值在集合X中从小到大排序的序号，则路由节点 作为下一跳，其中λ为a_ik-a_lk模q的值在集合X中从小到大排序的序 号，进入步骤(1)；

若则将报文所在的超级路由节点(a_i0a_i1...a_is...a_i(n-1),k)和公共超级 路由节点(a_l0a_l1...a_ls...a_l(n-1),k)相连的路由节点作为下一跳，其 中Δ为a_lk-a_ik模q的值在集合X中从小到大排序的序号，进入步骤(1)；

(4.1.2)a_is-a_jk∈X′，表明报文所在的超级路由节点和目的终端所在的超级路由 节点的公共超级路由节点在第s簇中，则满足a_is＝a_lk的超级路由节点 (a_l0a_l1...a_lk...a_l(n-1),s)是公共超级路由节点，其中0≤l≤q-1，l为整数；

若报文所在的路由节点(a_i0a_i1…a_is…a_i(n-1),k,t₁)和公共超级路由节点 (a_l0a_l1...a_lk...a_l(n-1),s)相连的路由节点是同一个 路由节点即则路由节点作为下 一跳，进入步骤(1)；

若则将报文所在的超级路由节点(a_i0a_i1...a_ik...a_i(n-1), k)和公共超级路由节点(a_l0a_l1...a_lk...a_l(n-1),s)相连的路由节点 作为下一跳，进入步骤(1)；

(4.2)按从大到小的顺序遍历第k簇所有超级路由节点(a_l0a_l1...a_lk...a_l(n-1),k) 满足a_lk-a_ik∈X且a_jk-a_lk∈X的最小值，则超级路由节点(a_l0a_l1...a_ls...a_l(n-1),k)是公共超 级路由节点，其中0≤l≤q-1，l为整数；

若报文所在的路由节点(a_i0a_i1…a_is…a_i(n-1),k,t₁)和公共超级路由节点 (a_l0a_l1...a_ls...a_l(n-1),k)相连的路由节点是同一个路由节点即 其中Δ为a_lk-a_ik模q的值在集合X中从小到大排序的序号，则路由节点 作为下一跳，其中λ为a_ik-a_lk模q的值在集合X中从小到大排序的序 号，进入步骤(1)；

若则将报文所在的超级路由节点(a_i0a_i1...a_ik...a_i(n-1),k)和公共超级 路由节点(a_l0a_l1...a_lk...a_l(n-1),k)相连的路由节点作为下一跳，其 中Δ为a_lk-a_ik模q的值在集合X中从小到大排序的序号，进入步骤(1)；

(4.3)若a_is-a_jk∈X，进入步骤(4.3.1)；若a_is-a_jk∈X′，进入步骤(4.3.2)；

(4.3.1)a_is-a_jk∈X，表明报文所在的超级路由节点和目的终端所在的超级路由节 点的公共超级路由节点在第s簇中，则满足a_lk＝a_is的超级路由节点(a_l0a_l1...a_lk...a_l(n-1), s)是公共超级路由节点，其中0≤l≤q-1，l为整数；

若报文所在的路由节点(a_i0a_i1…a_is…a_i(n-1),k,t₁)和公共超级路由节点 (a_l0a_l1...a_lk...a_l(n-1),s)相连的路由节点是同一个路 由节点即则路由节点作为下一 跳，进入步骤(1)；

若则将报文所在的超级路由节点(a_i0a_i1...a_is...a_i(n-1),k)和公 共超级路由节点(a_l0a_l1...a_lk...a_l(n-1),s)相连的路由节点 作为下一跳，进入步骤(1)；

(4.3.2)a_is-a_jk∈X′，表明报文所在的超级路由节点和目的终端所在的超级路由 节点的公共超级路由节点在第k簇中，则满足a_ls＝a_jk的超级路由节点 (a_l0a_l1...a_lk...a_l(n-1),k)是公共超级路由节点，其中0≤l≤q-1，l为整数；

若报文所在的路由节点(a_i0a_i1…a_ik…a_i(n-1),k,t₁)和公共超级路由节点 (a_l0a_l1...a_lk...a_l(n-1),k)相连的路由节点是同一个路由节点即 其中Δ为a_lk-a_ik模q的值在集合X中从小到大排序的序号，则路由节点 作为下一跳，其中λ为a_ik-a_lk模q的值在集合X中从小到大排序的序 号，λ为整数且从0开始排序，进入步骤(1)；

若则将报文所在的超级路由节点(a_i0a_i1...a_is...a_i(n-1),k)和公共超级 路由节点(a_l0a_l1...a_lk...a_l(n-1),k)相连的路由节点作为下一跳，其 中Δ为a_lk-a_ik模q的值在集合X中从小到大排序的序号，Δ为整数且从0开始排序，进入步骤 (1)。

本发明相对于现有技术具有如下的优点及效果：

(1)本发明大规模互连网络拓扑结构在不受路由器阶数限制时，增长规模是连续 性的。若在路由器芯片工艺受限的情况下，该结构可以用阶数不同的路由芯片搭建同一种 规模的网络也可以用同一阶数的路由芯片搭建不同规模的网络，即网络规模为nqap，路由 节点的阶数为a+h+p-1，可以通过调整参数n、a、p、q、h来实现不同需求的网络构建。因此，本 发明拓扑结构可以克服现有路由器工艺的缺点与不足，支持E级HPC系统；

(2)本发明大规模互连网络拓扑结构是由多参数配置的层次化结构，因此可以根 据实际系统的需求，调整参数n、a、p、q、h来满足系统二分带宽、网络直径等性能的需求；

(3)本发明大规模互连网络拓扑结构采用的Galaxy图可以根据实际系统需求按照 簇或者超级节点的大小把结构划分为若干个模块便于物理布局，并结合光缆和电缆成本与 距离上的差别，有效降低物理成本的开销；且Galaxy图是一个可以灵活配置的图，根据实际 系统的配置需求，调整Galaxy图的参数配置，从而灵活构建整个网络拓扑，并支持不同规模 HPC系统的网络构建；

(4)本发明大规模互连网络拓扑结构中，任意两个簇之间有q条链路而且超级路由 节点内部是全互连结构，使得超级路由节点之间以及路由节点之间拥有多条冗余链路，因 此本发明的路由方法可以找到多条路径，有效提升拓扑结构的通信效率及容错性。

附图说明

图1是本发明阶数灵活的低直径大规模互连网络拓扑结构的第一层结构即超级路 由节点结构图，其中超级路由节点内的路由器数量为a＝3；

图2是本发明阶数灵活的低直径大规模互连网络拓扑结构的第二层结构的宏观图 即Galaxy图，其中簇的数量为n＝2，每个簇的节点数量为q＝5；

图3是本发明阶数灵活的低直径大规模互连网络拓扑结构，其中Galaxy图的配置n ＝2和q＝5，每个超级路由节点的路由节点数量a＝3，并详细标出超级路由节点(00,0)和 (13,1)以及(11,0)之间的连接情况；

图4是本发明阶数灵活的低直径大规模互连网络拓扑结构的路由方法流程图。

具体实施方式

下面结合实施例及附图对本发明作进一步详细的描述，但本发明的实施方案不限 于此。

本实例公开了大规模互连网络拓扑结构的各层结构，如图1所示，一个超级路由节 点内的3个路由节点全互连而成作为第一层结构；此时每个路由节点分别用两个端口连接2 个终端，另两个端口分别连接同一个超级路由节点内的其他两个路由节点。如图2所示拓扑 结构的第二层结构宏观图，每个超级路由节点引出2条链路连接同一簇的另外两个超级路 由节点，并引出1条链路连接另一簇的1个超级路由节点，其中n＝2和q＝5，则集合X＝{1, 4}、X′＝{2,3}。由配置为n＝2、q＝5的Galaxy图和每3个路由节点组成的单个超级路由节点 以构成如图3所示的本发明拓扑结构，该拓扑结构包含两层结构。在第二层结构中，超级路 由节点之间的链路分别来自第一层结构中各个路由节点，即每个超级路由节点中的3个路 由节点分别引出1条链路连接其他3个超级路由节点。

本实例拓扑结构由2个簇和每个簇5个超级路由节点组成，其中每个超级路由节点 含3个路由节点和6个终端，在本实例中n＝2、q＝5、a＝3及p＝2。

本实例的大规模互连网络拓扑结构中按照超级路由节点和路由节点以及终端所 处位置坐标为其编号。

每个超级路由节点使用二维坐标(a_i0a_i1…a_is…a_i(n-1),k)表示，第一维的n元组 a_i0a_i1…a_is…a_i(n-1)表示的是当前超级路由节点分别与其他n-1个簇有连接关系的超级路由 节点的编号，其中a_is表示第k簇的第i节点(a_i0a_i1…a_is…a_i(n-1),k)连接第s簇的节点 (a_j0a_j1…a_jk…a_j(n-1),s)，其中，a_jk＝a_is，a_ik＝i。第二维的k则表示当前超级路由节点位于第 k簇内。如图2所示的本发明拓扑结构第二层结构的宏观图，按照上述坐标给各个超级路由 节点编号，n＝2、q＝5，因此结构中各个超级路由节点的坐标为(a_i0a_i1,k)，其中对于编号为 (11,0)的超级路由节点，k为0，表示该超级路由节点位于第0号簇，a₁₀为1，表示该超级路由 节点位于第0号簇第1号超级路由节点结构，a₁₁为1，表示该超级路由节点与位于第1簇且其 a_i0坐标为1的超级路由节点有连接关系。因此编号为(13,1)的超级路由节点与编号为(11, 0)的超级路由节点有连接。对于坐标值为(13,1)的超级路由节点，由于a₃₀为1，表示该超级 路由节点与位于第0簇且其a_i1坐标为1的超级路由节点有连接关系，进而进一步验证编号为 (13,1)的超级路由节点与编号为(11,0)的超级路由节点有连接。因为q＝5，则集合X＝{1, 4}，因为a₂₀-a₁₀＝1，所以a₂₀-a₁₀∈X，因此编号为(11,0)和(22,0)的超级路由节点之间有连 接关系。同理，编号为(21,1)和(42,1)的超级路由节点之间有连接关系，其中a₂₁-a₁₁∈X。

对于每个路由节点，使用的是3维坐标(a_i0a_i1…a_ik…a_i(n-1),k,t)，第一维和第二维 表示的都是该路由节点所在超级路由节点的坐标，第3维的t则表示路由节点(a_i0a_i1…a_ik… a_i(n-1),k,t)是所在超级路由节点(a_i0a_i1…a_ik…a_i(n-1),k)的第t路由节点。如图3所示的整个 拓扑结构，编号为(00,0,0)、(00,0,1)以及(00,0,2)的路由节点位于超级路由节点(00,0) 结构中，每个路由节点分别引出一条链路连接超级路由节点(11,0)、(44,0)以及(00,1)。

对于每个终端，使用的是4维坐标(a_i0a_i1…a_ik…a_i(n-1),k,t,c)，第一维和第二维表 示的是该终端所在超级路由节点(a_i0a_i1…a_ik…a_i(n-1),k)的编号，第三维表示的是该终端所 在路由节点(a_i0a_i1…a_ik…a_i(n-1),k,t)的编号，第四维表示的是该终端在路由节点(a_i0a_i1… a_ik…a_i(n-1),k,t)所连接终端的编号，其中0≤c≤p-1。

如图3所示的拓扑结构，利用本发明阶数灵活的低直径大规模互连网络拓扑结构 的路由方法寻找终端(00,0,2,0)到终端(13,1,2,0)的路径，步骤如下：

(1)检测终端(00,0,2,0)和终端(13,1,2,0)是否连接同一个路由节点上，经检测， 它们不连接在同一路由节点上；

(2)检测终端(00,0,2,0)和终端(13,1,2,0)所在的路由节点是否连接同一个超级 路由节点上，经检测，它们不连接在同一个超级路由节点上；

(3)检测终端(00,0,2,0)和终端(13,1,2,0)所在的超级路由节点是否相连，经检 测，两个终端所在的超级路由节点之间没有相连；

(4)寻找与终端(00,0,2,0)和终端(13,1,2,0)所在超级路由节点共同相连的超级 路由节点。从图3可以看到编号为(11,0)的超级路由节点是超级路由节点(00,0)和(13,1) 的公共超级路由节点，超级路由节点(00,0)中的路由节点(00,0,0)连接超级路由节点(11, 0)的路由节点(11,0,1)，因此，则将路由节点(00,0,0)作为下一跳。

接下来将路由节点(00,0,0)作为当前路由节点，检测路由节点(00,0,0)和目的路 由节点(13,1,2)是否连接在同一路由节点上，如图3所示，两个路由节点不是连接在同一个 路由节点上，同时，也不在同一个超级路由节点内，而且两个路由节点所在的超级路由节点 之间不相连。继续寻找两个路由节点所在的超级路由节点的公共超级路由节点并将当前路 由节点所在的超级路由节点与公共超级路由节点相连的路由节点作为下一跳，即与路由节 点(00,0,0)相连的路由节点(11,0,1)作为下一跳。

接下来将路由节点(11,0,1)作为当前路由节点，检测路由节点(11,0,1)和目的路 由节点(13,1,2)是否连接在同一路由节点上，如图3所示，两个路由节点不是连接在同一个 路由节点上，同时，也不在同一个超级路由节点内，但是两个路由节点所在的超级路由节点 之间相连。继续寻找两个路由节点所在的超级路由节点之间相连的路由节点作为下一跳， 即与路由节点(11,0,1)相连的路由节点(11,0,2)作为下一跳。

接下来将路由节点(11,0,2)作为当前路由节点，检测路由节点(11,0,2)和目的路 由节点(13,1,2)是否连接在同一路由节点上，如图3所示，两个路由节点不是连接在同一个 路由节点上，同时，也不在同一个超级路由节点内，但是两个路由节点所在的超级路由节点 之间相连。继续寻找两个路由节点所在的超级路由节点之间相连的路由节点作为下一跳， 即与路由节点(11,0,2)相连的路由节点(13,1,2)作为下一跳。

路由节点(13,1,2)就是目的终端(13,1,2,0)所连接的路由节点，路由寻找结束。

上述实施例为本发明最短路径路由算法实施方式，但本发明的实施方式并不受上 述实施例的限制，其它的任何未背离本发明的精神实质与原理下所作的改变、修饰、替代、 组合、简化，均应为等效的置换方式，都包含在本发明的保护范围之内。