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

摘要

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

主权项

一种阶数灵活的低直径大规模互连网络拓扑结构，其特征在于，整个拓扑分成两层结构，由a个路由节点全互连组成一个大的超级路由节点作为第一层结构，超级路由节点中的a个路由节点分别记为第0路由节点、第1路由节点、…、第t路由节点、…、第a‑1路由节点，0≤t≤a‑1，a、t均为整数；第二层结构则是以第一层结构为基础，将每个超级路由节点按Galaxy图的方式连接其它超级路由节点，其中所述的连接是由第一层结构中a个路由节点各引出的h条链路提供，h为整数；Galaxy图中有n个簇(cluster)，记为第0簇、第1簇,…,第k簇,…,第n‑1簇，0≤k≤n‑1，n、k为整数；每个簇内有q个节点，每个节点即拓扑结构第一层结构的一个超级路由节点，且满足q＝4l+δ，其中δ∈{‑1,0,1}，l为整数，q个节点分别记为第0节点、第1节点、…、第i节点、…、第q‑1节点；0≤i≤q‑1，i、q为整数；每个节点引出(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簇内；每个超级路由节点引出ah条链路连接其它超级路由节点，满足ah≥n‑1+(q‑δ)/2，其中n‑1条链路连接Galaxy图中其它簇的超级路由节点，(q‑δ)/2条链路连接同一个簇的其它超级路由节点；每个超级路由节点中包含a个路由节点，每个路由节点由三维坐标(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路由节点，每个路由节点引出a‑1条链路连接同一个超级路由节点内的其它a‑1个路由节点，引出h条链路连接其它超级路由节点；每个路由节点连接p个终端，每个终端则由四维坐标(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终端，0≤c≤p‑1，p、c均为整数。