基于平衡超立方体的数据中心网络及其容错路由方法

本技术属于数据中心网络构建与可靠通信，具体的说是涉及一种基于平衡超立方体的数据中心网络及其容错路由方法。

背景技术：

1、随着云计算、人工智能训练、大数据分析及实时交互业务快速发展，现代数据中心的计算任务与数据流量呈指数级增长。数据中心网络作为服务器互联、分布式计算与数据传输的核心基础设施，其拓扑结构直接决定网络直径、节点连通性、多路径冗余能力与扩容性能。因此，拓扑架构的时延特性、容错能力与部署成本，直接影响超大规模数据中心的传输效率、运行稳定性与运维成本，是高性能数据中心设计的核心关键。

2、现有数据中心网络拓扑主要分为交换机中心型与服务器中心型两类，均存在明显技术缺陷。以fat-tree为代表的交换机中心型架构通过多层交换结构实现稳定吞吐，但高度依赖高端口高密度交换机。网络扩容时需更换高端设备并重构布线，硬件与施工成本随规模超线性增长，扩容代价大、扩展能力受限，难以支撑百万级超大规模数据中心的迭代扩展。

3、服务器中心型拓扑将部分路由功能下放至服务器，交换机仅负责基础转发，可采用低端口商用设备组网，具备部署成本低、组网灵活度高的优势，是当前高性能数据中心组网的主流研究方向。但该类拓扑普遍存在固有架构缺陷，无法在时延性能、容错能力与规模化扩容成本之间实现均衡优化，具体缺陷体现在以下方面：

4、其一，时延性能不佳，传统拓扑的网络直径与平均传输跳数随网络扩张快速增加，传输路径更长，且传统路由依赖全局遍历计算路径，复杂度高、收敛慢，大规模高并发场景下时延累积明显，难以适配ai推理、实时算力调度等低时延业务需求；其二，容错稳定性有限，数据中心长期运行易出现节点与链路故障，而现有拓扑顶点连通度较低、冗余传输路径较少，多节点故障时易出现网络割裂、路径中断、吞吐量下降等问题，故障自愈能力弱，无法保障网络持续可靠传输；其三，扩容实用性差、成本偏高，bcube、dcell等扩容需为服务器增设网卡，显著提升硬件与运维成本，ficonn、hsdc等虽无需扩展服务器端口，但网络扩容上限低，不支持精细化按需扩容，难以适配数据中心渐进式规模化建设需求。

技术实现思路

1、针对现有数据中心网络拓扑存在的时延性能差、容错能力弱、扩容成本高、扩展灵活性差的技术缺陷，本技术提供一种一种基于平衡超立方体的数据中心网络及其容错路由方法，解决了传统拓扑无法兼顾低时延传输、高节点连通容错与低成本规模化扩展的行业痛点，规避了现有服务器中心型拓扑扩容需增设服务器网卡、故障冗余路径不足、路由计算开销大等问题，可满足超大规模数据中心低时延、高可靠、低成本的组网部署需求。

2、为了达到上述目的，本技术是通过以下技术方案实现的：

3、本技术是一种基于平衡超立方体的数据中心网络，所述数据中心网络拓扑结构表示为，其特征在于：基于维平衡超立方体构建服务器中心型数据中心网络，将维平衡超立方体中的每一个顶点映射为交换机，将维平衡超立方体中的每一条边映射为双端口的服务器，服务器中心型数据中心网络包括台交换机和台服务器，每台服务器仅与两台交换机连接，服务器与服务器之间以及交换机与交换机之间均不设置直接物理链路，也就是说服务器之间不设置直接物理连接，交换机之间也不设置直接物理连接，交换机作为服务器之间的中间转发设备。在服务器中心型数据中心网络中，每台交换机采用一个位四进制字符串进行标识，交换机地址记为，其中，对于任意两个位四进制字符串和，定义函数和分别表示四进制字符串和对应的十进制数值，当和满足中的邻接关系且时，在中设置一台服务器，并将该服务器记为即连接相邻交换机和的服务器地址表示为，其中，和分别为所述服务器连接的两台交换机的地址；通过限定，保证每台服务器具有唯一的地址表示，服务器地址表示为，并满足下列两条规则之一：

4、规则1、，且；

5、规则2、，且；

6、服务器的和交换机之间的连接规则

7、对于任意服务器，其中一个网络端口连接至地址为的交换机，另一个网络端口连接至地址为的交换机。服务器与交换机之间的物理链路分别表示为和。

8、因此，对于任意服务器和任意交换机，服务器与交换机直接连接，当且仅当，或者。

9、对于任意两台交换机和，二者通过服务器间接连接，当且仅当和满足上述中服务器地址规则。

10、在所述连接方式下，每台服务器仅连接其地址中记录的两台交换机，不连接其他交换机；交换机仅与服务器连接，不与其他交换机直接连接；服务器仅与交换机连接，不与其他服务器直接连接。

11、本技术还提供了一种基于平衡超立方体的数据中心网络的容错路由方法具体包括如下步骤：

12、步骤1、构建逻辑网络：将服务器中心型数据中心网络内所有交换机抽象为透明节点得到的逻辑网络，对于任意整数，所述逻辑网络表示为无向图，其中，是边集合，为逻辑节点集合，逻辑节点集合中的每个节点对应于中的一台服务器，并表示为，其中，；所述逻辑网络为正则图且具有与平衡超立方体相对应的规则递归结构；具体的，对于逻辑网络中的任意节点，与交换机连接且不同于节点的其他服务器节点，以及与交换机连接且不同于节点的其他服务器节点，均为节点的逻辑邻居。由于平衡超立方体中的每个顶点关联条边，除服务器节点所对应的边外，交换机和交换机分别还连接台服务器，因此，每个逻辑节点均具有个逻辑邻居。由此，所述逻辑网络为正则图，且具有与平衡超立方体相对应的规则递归结构

13、步骤2、输入逻辑网络、获取故障服务器节点集合以及两个不同的非故障源服务器节点和目的服务器节点，其中，，并判断源服务器节点和目的服务器节点是否相邻，当源服务器节点和目的服务器节点在逻辑网络中相邻，即时，直接返回路径；当故障节点数量超出的容错保证范围时，在删除故障节点后的逻辑网络中采用图搜索方法搜索可行路径，当源服务器节点和目的服务器节点在逻辑网络中不相邻，则基于逻辑网络的递归结构将逻辑网络划分为四个维子网络及相邻子网络之间的连接节点集合，且将子网络和连接节点集合统称为逻辑网络的子结构，并统计各子网络中的故障节点数量；

14、步骤3、根据所述源服务器节点、目的服务器节点所在的子结构，以及各子网络中的故障节点数量，构造所述源服务器节点和目的服务器节点进入目标子结构的无故障局部路径；

15、步骤4、通过递归路由连接步骤3构造的进入目标子结构的无故障局部路径，得到从所述源服务器节点至所述目的服务器节点的无故障逻辑路径；定义局部路径连接方法，将分别从源服务器节点和目的服务器节点出发的两条无故障局部路径连接为完整的无故障逻辑路径。

16、步骤5、在完成无故障逻辑路径构造后，根据所述无故障逻辑路径中相邻服务器节点共同连接的交换机，将所述无故障逻辑路径转换为所述物理网络中的容错传输路径。完成步骤4的无故障逻辑路径构造后，检查所生成的无故障逻辑路径中的各服务器节点是否均不属于故障服务器节点集合，对于无故障逻辑路径中任意两个相邻服务器节点，根据任意两个相邻服务器节点地址中相同的交换机地址确定共同连接的交换机，并通过所述交换机完成两个服务器节点之间的数据转发，从而将逻辑网络中的无故障逻辑路径转换为物理网络中的容错传输路径。

17、本技术的进一步改进在于：在步骤1中，在逻辑网络中的每台服务器对应一个逻辑节点，逻辑节点表示中连接交换机和交换机的服务器，其中，，，其中，；逻辑节点满足以下两种地址关系规则中的一种：

18、规则1、，且；

19、规则2、，且；

20、对于所述逻辑网络中的两个逻辑节点和，当且仅当满足、、或中的至少一个条件时，所述逻辑节点和相邻。具体而言，对于逻辑网络中的任意两个不同源服务器节点和目的服务器节点令、、、，当且仅当满足、、或中的任意一个条件时，源服务器节点和目的服务器节点在逻辑网络中相邻，即当两台服务器所连接的两台交换机中至少存在一台相同交换机时，两台服务器构成逻辑邻接关系。

21、本技术的进一步改进在于：步骤1具体包括如下步骤：

22、步骤1.1、构造四个与第层逻辑网络同构的子网络，：当时，逻辑网络由节点、、和组成，当时，基于第层逻辑网络构造四个与第层逻辑网络同构的子网络：、、和；对于任意逻辑节点，将逻辑节点和逻辑节点分别增加相同的四进制地址位，得到地址位为的子网络中的对应节点，通过将四进制地址位分别增加至逻辑节点和逻辑节点，得到地址位为的子网络中的节点；

23、步骤1.2、对于任意，定义连接地址位为的子网络和地址位为的子网络的节点集合为：

24、

25、其中，和分别表示维平衡超立方体中的两个相邻维平衡超立方体子图，节点表示连接交换机和交换机即源服务器节点和目的服务器节点的服务器，其中，交换机属于，交换机属于。所述节点集合用于实现子网络与子网络之间的连接。由此确认逻辑网络四个子网络、、、以及连接相邻子网络的连接节点集合递归构成，将子网络和连接节点集合统称为逻辑网络的子结构。

26、本技术的进一步改进在于：在步骤2中，所述逻辑网络的点连通度为，当时，删除所述故障服务器节点集合后的逻辑网络保持连通，任意两个非故障服务器节点之间至少存在一条不经过故障节点的路径。

27、本技术的进一步改进在于：在步骤2中，基于逻辑网络的递归结构对逻辑网络进行划分并统计各子结构中的故障节点数量具体包括如下步骤：

28、步骤2.1、对于任意，将逻辑网络中的四个维子网络分别记为，将相邻子网络之间的连接节点集合分别记为；

29、步骤2.2、分别统计四个子网络、、、中的故障服务器节点集合，通过改变的取值，将源服务器节点和目的服务器节点所在的子结构转换为由表示的对应位置关系。

30、本技术的进一步改进在于：步骤3中的无故障局部路径通过算法获得，所述算法是本技术提出的局部路径构造方法，包括、和三个子程序，设为目标子结构，、、和为从当前节点至目标子结构的过程中经过的中间子结构，即，对于任意子结构，采用表示源服务器节点在子结构中的邻居集合，采用表示源服务器节点在子结构中的非故障邻居集合，当任意节点在目标子结构中存在非故障邻居时，直接进入所述目标子结构，当不能直接进入时，经中间子结构和中间子结构绕行，当绕行失败时，进一步经中间子结构和中间子结构扩大搜索范围后进入目标子结构，具体的构造所述源服务器节点和目的服务器节点进入所述目标子结构的无故障局部路径包括：

31、当源服务器节点在目标子网络中存在非故障邻居时，采用，即从中选择一个满足的目的服务器节点，并返回路径；

32、当源服务器节点不能直接进入目标子结构时，采用，即首先遍历源服务器节点在中间子结构中的非故障邻居，当目的服务器节点在目标子结构中存在非故障邻居，即时，调用构造目的服务器节点进入目标子结构的路径，并将源服务器节点添加至该路径的起始位置；若中间子结构不能进入目标子结构，则依次选择源服务器节点在中间子结构中的非故障邻居，以及目的服务器节点在中间子结构中的非故障邻居，当时，采用构造节点进入目标子结构的路径，并依次连接节点、目的服务器节点、节点及节点进入目标子结构的路径；

33、当采用仍不能进入目标子结构时，采用扩大局部路径的搜索范围，即首先遍历源服务器节点在中间子结构中的非故障邻居，当目的服务器节点在中间子结构中存在非故障邻居，即时，以目的服务器节点作为新的当前节点调用，并将源服务器节点连接至生成的局部路径；若源服务器节点不能直接进入中间子结构，则遍历源服务器节点在中间子结构中的非故障邻居，再遍历目的服务器节点在中间子结构中的非故障邻居，当时，以节点作为新的当前节点调用，并依次连接源服务器节点、目的服务器节点及生成的局部路径。

34、所述、和分别用于直接进入目标子网络、经过一层中间结构绕行进入目标子网络以及经过多层中间结构绕行进入目标子网络，并根据局部故障服务器节点的分布情况选择使用。

35、本技术的进一步改进在于：在步骤4中，所述源服务器节点至所述目的服务器节点的无故障逻辑路径通过算法进行连接，是本发明提出的局部路径连接方法，包括、和三个子程序，

36、当两条无故障局部路径存在公共节点时，在第一个公共节点处截取并连接对应子路径，当两条局部路径不存在公共节点时，在所述目标子结构中递归调用，构造两条局部路径末端节点之间的无故障路径并进行拼接，具体为：

37、对于任意路径，采用表示路径的末端节点，采用表示路径的反向路径，采用表示路径中从节点至节点的子路径，设路径以源服务器节点为起点，路径以目的服务器节点为起点，且路径和路径的末端节点均位于相同的目标子结构中；

38、只有路径时，采用，即，当源服务器节点位于路径中时，直接返回；当源服务器节点不位于路径中时，将所述目标子结构作为新的当前拓扑范围，递归执行所述步骤，构造源服务器节点至路径末端节点的无故障路径，并将该无故障路径与反向路径连接；

39、只有路径时，采用，即当目的服务器节点位于路径中时，直接返回；当目的服务器节点不位于路径中时，将所述目标子结构作为新的当前拓扑范围，递归执行所述步骤，构造路径末端节点至目的服务器节点的无故障路径，并将该无故障路径连接在路径之后；

40、当存在路径和路径时，采用连接两条局部路径，即若，则查找路径和路径中的第一个公共节点，提取路径中从源服务器节点至公共节点的子路径，以及反向路径中从公共节点至目的服务器节点的子路径，并返回；若，将所述目标子结构作为新的当前拓扑范围，递归执行所述步骤，构造路径末端节点和路径末端节点之间的无故障路径，再依次连接路径、路径和反向路径，得到路径。

41、根据源服务器节点、目的服务器节点所在的子结构，以及各子结构中的故障节点数量，选择和里适配的子程序。

42、当节点和节点均位于子网络，且时，在子网络内递归调用。由于维子网络的点连通度为，故当其中的故障节点数不大于时，该子网络删除故障节点后仍保持连通；

43、当节点和节点均位于子网络，但时，分别调用构造节点和节点经连接节点集合进入相邻子网络的局部路径和局部路径，再调用在子网络中连接路径和路径；

44、当节点和节点位于不同子结构时，选择一个能够使局部路径在其中汇合的共同目标子网络，并根据目标子结构及中间子结构的故障节点分布，分别调用、或，将节点和节点引导至所述共同目标子结构，再调用、或连接所生成的局部路径。

45、当节点和节点均位于连接节点集合中时，从子网络和子网络中选择故障节点数量较少的子网络，其中，分别调用构造节点和节点进入子网络的局部路径，并采用连接；当一个节点位于子网络，另一个节点位于连接节点集合、相邻子网络、非相邻子网络或相应连接节点集合时，根据、或是否不大于，选择在故障节点较少的子网络中递归连接，或者利用和绕过故障节点较密集的子网络。对于具有旋转对称关系的其余节点位置情况，通过改变的取值按照相同方式构造容错路径

46、本技术的有益效果是：

47、本技术采用服务器中心型网络结构，每台服务器仅需配置固定数量的网络端口，网络扩展过程中无需增加服务器网卡数量，能够降低硬件配置成本和网络布线复杂度。

48、本技术采用规则的节点地址编码和递归式网络结构，可在保持已有服务器端口配置和连接关系基本不变的情况下实现网络扩展，具有良好的可扩展性和结构一致性。

49、本技术采用规则、对称的网络连接结构，能够有效控制网络规模扩展过程中通信路径长度的增长，减少服务器之间的数据转发跳数，提高数据传输效率和网络通信性能。

50、本技术所构造的逻辑网络具有较高的连通性，在部分服务器发生故障的情况下，仍能够维持非故障服务器之间的通信，提高数据中心网络的可靠性和抗故障能力。

51、本技术的容错路由方法能够根据源节点、目的节点及故障节点在各子网络中的分布情况，选择适当的递归路由和跨子网络转发方式，避开故障区域并完成非故障服务器之间的路径构造，提高故障环境下路由过程的适应性和通信可靠性。