CN120301816A

CN120301816A - Method and device for sending routing request

Info

Publication number: CN120301816A
Application number: CN202510404745.2A
Authority: CN
Inventors: 陈静静; 韩钊; 孙华锦
Original assignee: Shandong Yunhai Guochuang Cloud Computing Equipment Industry Innovation Center Co Ltd
Current assignee: Shandong Yunhai Guochuang Cloud Computing Equipment Industry Innovation Center Co Ltd
Priority date: 2025-04-01
Filing date: 2025-04-01
Publication date: 2025-07-11

Abstract

The embodiment of the present application provides a method and device for sending a routing request, wherein the method includes: obtaining the codes of the source terminal and the target terminal; determining the target layer where the nearest common parent node is located in the thinned fat tree network structure according to the codes of the source terminal and the target terminal; according to the target sub-network where the source terminal and the target terminal are located, and the routing nodes included in the first routing node set and the second routing node set, transmitting the target routing request sent by the source terminal upward to the target parent node on the target layer through the routing nodes in the target sub-network, and the target parent node transmits the target routing request downward to the target terminal through the routing nodes in the target sub-network. Through the present application, the problem of mutual interference between sub-networks in the data transmission process in the related art is solved, thereby achieving the effect of non-interference between sub-networks.

Description

Method and device for sending route request

Technical Field

The embodiment of the application relates to the field of computers, in particular to a method and a device for sending a routing request.

Background

The dual-host routing refers to dividing a network into two sub-networks, using two hosts to transmit data in the respective sub-networks, and can be implemented by a router or a switch, which can provide faster and reliable data transmission, and can also improve the fault tolerance and load balancing capability of the network. In dual host routing, data typically passes through multiple network devices and paths to ensure that the data is securely transferred.

When a routing path is selected, the conventional routing algorithm may occupy routing node resources of adjacent subnetworks, so that the requirements that two subnetworks are mutually independent and not disturbed cannot be met.

There is currently no effective solution to the above problems.

Disclosure of Invention

The embodiment of the application provides a method and a device for sending a routing request, which at least solve the problem of mutual interference among sub-networks in the data transmission process in the related technology.

According to one embodiment of the present application, there is provided a method for transmitting a routing request, applied to a thinned fat-tree network structure, wherein a relation between a total number of layers of the thinned fat-tree network structure and a total number n of source nodes is l= (log ₂ n) -1, a relation between a number k _i of i-th layer routing nodes and a number k _i-1 of i-1 layer routing nodes is k _i＝k_l-1/2, i e {1, 2..l }, i is an integer greater than or equal to 1, the thinned fat-tree network structure is divided into a first sub-network and a second sub-network, a first set of routing nodes includes routing nodes in the first sub-network, and a second set of routing nodes includes routing nodes in the second sub-network, the method further includes acquiring codes of source terminals and target terminals, wherein the source terminals and the target terminals are source terminals in the thinned fat-tree network structure, and the source terminals and the target terminals are in the same sub-network; determining a target layer where a nearest public father node is located in the thinned fat tree network structure according to codes of the source terminal and the target terminal, wherein the public father node is a father node common to the source terminal and the target terminal, transmitting a target routing request sent by the source terminal to a target father node on the target layer through a routing node in the target child network according to a target child network where the source terminal and the target terminal are located and a routing node included in the first routing node set and the second routing node set, transmitting the target routing request downwards to the target terminal through the routing node in the target child network by the target father node, wherein the target subnetwork is the first subnetwork or the second subnetwork.

In an exemplary embodiment, determining the target layer where the nearest public parent node is located in the thinned fat-tree network structure according to the codes of the source terminal and the target terminal comprises performing binary exclusive-or operation on the codes of the source terminal and the target terminal in a binary form under the condition that the codes of the source terminal and the target terminal are represented by X-bit binary numbers to obtain an exclusive-or result, wherein X is an integer greater than 2, and determining the target layer where the nearest public parent node is located in the thinned fat-tree network structure according to the exclusive-or result.

In an exemplary embodiment, determining the target layer where the nearest public parent node is located in the thinned fat tree network structure through the exclusive or result comprises deleting the lower two bits in the exclusive or result to obtain a first target binary number, determining the bit number of the bit where the non-zero value occurs first in the first target binary number according to the sequence from low to high, and determining the bit number of the bit as the layer number of the target layer where the nearest public parent node is located.

In an exemplary embodiment, according to the destination sub-network where the source terminal and the destination terminal are located and the routing nodes included in the first routing node set and the second routing node set, the destination routing request sent by the source terminal is transmitted upward to the destination parent node on the destination layer through the routing nodes in the destination sub-network, and the method includes determining, in a case that the destination routing request is transmitted upward to the routing node whose j-th layer is encoded as d _j in the thinned fat tree network structure, the encoding d _j+1,0、d_j+1,1 of two routing nodes connected to the d _j in the j+1 th layer, i e {0,1,..m } the destination layer is the m-th layer, m is greater than or equal to 1 and less than or equal to the m, and sending the destination routing request from the d _j to the d _j+1,0 or the d _j+1,1 according to whether the d _j+1,0、d_j+1,1 is located in the destination routing node set corresponding to the destination sub-network, wherein in a case that the destination sub-network is the first routing node is the m-th layer, and m is the m-th layer, m is the m routing node.

In an exemplary embodiment, in the case that the target route request is transmitted to the routing node of the j-th layer encoded as d _j in the thinned fat tree network structure, determining the codes d _j+1,0、d_j+1,1 of two routing nodes connected to the d _j in the j+1-th layer includes obtaining the d _j+1,0 and the d _j+1,1 by the following formula:

wherein bin is a binary exclusive-or function in binary form that converts an integer into a binary number, Is a round down function.

In an exemplary embodiment, the sending of the target routing request from the d _j to the d _j+1,0 or the d _j+1,1 according to the source terminal and the target sub-network where the target terminal is located and whether the d _j+1,0、d_j+1,1 is located in a target routing node set corresponding to the target sub-network includes determining a first target routing node at the d _j+1,0、d_j+1,1 according to whether the d _j+1,0、d_j+1,1 is located in a target routing node set corresponding to the target sub-network, and sending the target routing request from the d _j to the first target routing node.

In an exemplary embodiment, determining a first target routing node at d _j+1,0、d_j+1,1 according to whether d _j+1,0、d_j+1,1 is located in a set of target routing nodes corresponding to the target subnetwork includes determining that one routing node is the first target routing node at d _j+1,0、d_j+1,1 randomly when d _j+1,0、d_j+1,1 is located in the set of target routing nodes, or determining that a routing node with the shortest distance from d _j in d _j+1,0、d_j+1,1 is the first target routing node when d _j+1,0、d_j+1,1 is located in the set of target routing nodes, or determining that a routing node with the smallest load in d _j+1,0、d_j+1,1 is the first target routing node when d _j+1,0、d_j+1,1 is located in the set of target routing nodes.

In an exemplary embodiment, determining a first target routing node at d _j+1,0、d_j+1,1 according to whether d _j+1,0、d_j+1,1 is located in a set of target routing nodes corresponding to the target subnetwork, and determining a node located in the set of target routing nodes at d _j+1,0、d_j+1,1 as the first target routing node if one routing node in d _j+1,0、d_j+1,1 is located in the set of target routing nodes.

In an exemplary embodiment, each routing node in the thinned fat tree network structure comprises two uplink ports and four downlink ports, wherein the two uplink ports are respectively a first uplink port and a second uplink port, the codes of the first uplink port are smaller than those of the second uplink port, the four downlink ports are respectively a first downlink port, a second downlink port, a third downlink port and a fourth downlink port, the codes of the first downlink port, the codes of the second downlink port, the codes of the third downlink port and the codes of the fourth downlink port are sequentially increased, the first downlink port, the second downlink port, the third downlink port and the fourth downlink port of a routing node d _i on an ith layer in the thinned fat tree network structure are respectively connected with four routing nodes of a d _i-1,0、d_i-1,1、d_i-1,2、d_i-1,3 on an ith layer, the codes of d _i-1,0、d_i-1,1、d_i-1,2、d_i-1,3 are sequentially increased, the codes of the first downlink port on the ith layer in the fat tree network structure are sequentially increased, and the codes of the first downlink port and the second downlink port on a second layer in the fat tree network structure are sequentially increased, and the codes of the first node d _i on the first layer in the fat tree network structure are sequentially increased, and the nodes of the two nodes on the first layer in the destination nodes are sequentially increased, and the two nodes on the first layer in the destination nodes are sequentially increased in the two nodes are sequentially increased in the mode, and the two downlink nodes are sequentially and each in the mode.

In an exemplary embodiment, the destination routing request is transmitted downwards to the destination terminal by the destination father node through a routing node in the destination sub-network, and the method comprises the steps of performing binary form bit exclusive-or operation on codes of the source terminal and the destination terminal in the case that the codes of the source terminal and the destination terminal are represented by X-bit binary numbers to obtain an exclusive-or result, wherein X is an integer greater than 2, obtaining m valid bits through the exclusive-or result, and transmitting the destination routing request downwards to the destination terminal by the destination father node through a downlink port of the routing node in the destination sub-network according to the m valid bits.

In an exemplary embodiment, obtaining m significant bits through the exclusive or result includes deleting the lower two bits in the code of the target terminal to obtain a second target binary number, and determining m bits from low to high of the second target binary number as the m significant bits in the case that the target layer where the nearest public parent node is located is an mth layer.

In an exemplary embodiment, the transmitting the target routing request downward to the target terminal through the downstream port of the routing node in the target sub-network by the target parent node according to the m valid bits includes determining codes d _r-1,0、d_r-1,1、d_r-1,2、d_r-1,3 r e {0, 1..m } of four routing nodes connected to the d _r in the r-1 layer, the target layer being an m-th layer, m being greater than or equal to 1 and less than or equal to the l, determining a first routing node and a second routing node in the d _r-1,0、d_r-1,1、d_r-1,2、d_r-1,3 according to the m valid bits, and transmitting the target routing request from the d _r to the first routing node or the second routing node according to whether the first routing node and the second routing node are located in a set of target routing nodes corresponding to the target sub-network, in the case that the target routing request is transmitted downward to the routing node of the r-layer coding d _r in the thinned fat-tree network structure.

In one exemplary embodiment, determining the code d _r-1,0、d_r-1,1、d_r-1,2、d_r-1,3 of the four routing nodes in layer r-1 connected to d _r includes deriving d _r-1,0、d_r-1,1、d_r-1,2、d_r-1,3 by:

d_r-1,0＝bin(2*d_r)^bin(0);

d_r-1,1＝bin(2*d_r)^bin(1);

d_r-1,2＝bin(2*d_r)^bin(2);

d_r-1,3＝bin(2*d_r)^bin(3);

Wherein bin is an exclusive-or function in binary form that converts an integer into a binary number.

In an exemplary embodiment, determining a first routing node and a second routing node in the d _r-1,0、d_r-1,1、d_r-1,2、d_r-1,3 according to the m significant bits includes reordering the d _r-1,0、d_r-1,1、d_r-1,2、d_r-1,3 to obtain d '_r-1,0、d′_r-1,1、d′_r-1,2、d′_r-1,3, wherein the codes of the d' _r-1,0、d′_r-1,1、d′_r-1,2、d′_r-1,3 sequentially increase, determining d '_r-1,2 connected to a third downstream port of the d _r as the first routing node and d' _r-1,3 connected to the fourth downstream port as the second routing node when the corresponding significant bit of the m significant bits encoded by the r-th layer is a non-zero value, and determining d '_r-1,0 connected to a first downstream port of the d _r as the first routing node and d' _r-1,1 connected to a second downstream port of the d _r as the second routing node when the corresponding significant bit of the m significant bits encoded by the r-th layer is zero.

In an exemplary embodiment, the sending the target routing request from d _r to the first routing node or the second routing node according to whether the first routing node and the second routing node are located in a target routing node set corresponding to the target subnetwork includes determining a second target routing node in the first routing node or the second routing node according to whether the first routing node and the second routing node are located in the target routing node set, and sending the target routing request from d _r to the second target routing node.

In an exemplary embodiment, determining a second target routing node in the first routing node and the second routing node according to whether the first routing node and the second routing node are located in the target routing node set or not includes determining one routing node as the second target routing node in the case that the first routing node and the second routing node are located in the target routing node set at random, or determining the routing node with the shortest load in the first routing node and the second routing node as the second target routing node in the case that the first routing node and the second routing node are located in the target routing node set, wherein the routing node with the shortest distance from d _r in the first routing node and the second routing node is determined as the second target routing node in the case that the first routing node and the second routing node are located in the target routing node set.

In one exemplary embodiment, determining a second target routing node among the first routing node and the second routing node according to whether the first routing node and the second routing node are located in the target routing node set or not further comprises determining a node located in the target routing node set among the first routing node and the second routing node as the second target routing node if one of the first routing node and the second routing node is located in the target routing node set.

In an exemplary embodiment, the routing node of layer 0, which is encoded as d ₀, is connected to four source nodes, which are encoded as s ₀、s₁、s₂、s₃, in the thinned fat-tree network structure, and the relationship between d ₀ and s ₀、s₁、s₂、s₃ is:

s₀＝bin(2*d₀)^bin(0);

s₁＝bin(2*d₀)^bin(1);

s₂＝bin(2*d₀)^bin(2);

s₃＝bin(2*d₀)^bin(3);

The method comprises the steps of converting an integer into a binary form, performing an exclusive OR function in the binary form, wherein the source node is a terminal connected with a routing node in a layer 0, the source node comprises a source terminal and a target terminal, the target father node sends a target routing request to the target terminal through the routing node in a target sub-network, the target father node sends the target routing request to the target routing node through the routing node in the target sub-network, the target routing node is a node connected with the target terminal, and the target routing node sends the target routing request to the target terminal through a downlink port connected with the target terminal.

According to another embodiment of the present application, an apparatus for sending a routing request is provided, which includes an obtaining module configured to obtain codes of a source terminal and a target terminal, where the source terminal and the target terminal are source nodes in a thinned fat-tree network structure, and the source terminal and the target terminal are in a same sub-network, a determining module configured to determine a target layer where a nearest public parent node is located in the thinned fat-tree network structure according to the codes of the source terminal and the target terminal, where the public parent node is a common parent node of the source terminal and the target terminal, and a sending module configured to transmit, through a routing node in the target sub-network, a target routing request sent by the source terminal to a target node on the target layer, where the target parent node is a common parent node of the source terminal and the target terminal, and a routing node in a first routing node set and a second routing node set include a routing node in the first routing node, and the target parent node in the target sub-network is a first routing node set, and the target parent node in the target sub-network is transmitted to the target sub-network.

According to a further embodiment of the application, there is also provided a computer readable storage medium having stored therein a computer program, wherein the computer program is arranged to perform the steps of any of the method embodiments described above when run.

According to a further embodiment of the application there is also provided an electronic device comprising a memory having stored therein a computer program and a processor arranged to run the computer program to perform the steps of any of the method embodiments described above.

According to a further embodiment of the application, there is also provided a computer program product comprising a computer program which, when executed by a processor, implements the steps of any of the method embodiments described above.

The method comprises the steps of obtaining codes of a source terminal and a target terminal, wherein the source terminal and the target terminal are source nodes in a thinned fat tree network structure, the source terminal and the target terminal are in the same sub-network, determining a target layer where a nearest public father node is located in the thinned fat tree network structure according to the codes of the source terminal and the target terminal, wherein the public father node is a father node common to the source terminal and the target terminal, and transmitting a target routing request sent by the source terminal to the target father node on the target layer through a routing node in the target son network according to a target son network where the source terminal and the target terminal are located and a routing node included in a first routing node set and a second routing node set, and transmitting the target routing request downwards to the target terminal through the routing node in the target son network by the target father node, wherein the target son network is the first son network or the second son network.

Because the thinned fat-tree network structure and the routing nodes contained in the thinned fat-tree network are divided, the intermediate routing nodes are determined according to the target sub-networks where the source terminal and the target terminal are located and the divided routing node sets, and the transmission of the target routing request from the source terminal to the target father node and then to the target terminal is realized. Therefore, the problem of mutual interference among the sub-networks in the data transmission process in the related technology can be solved, and the effect of mutual non-interference among the sub-networks is achieved.

Drawings

FIG. 1 is a schematic diagram of a four-layer thinned fat-tree network architecture in accordance with an embodiment of the present application;

FIG. 2 is a diagram of a thin fat-tree network architecture of dual hosts according to an embodiment of the present application;

Fig. 3 is a hardware configuration block diagram of a server apparatus of a method of transmitting a routing request according to an embodiment of the present application;

FIG. 4 is a flow chart of a method of sending a routing request according to an embodiment of the present application;

FIG. 5 is a schematic diagram of a routing node upstream port connection according to an embodiment of the present application;

FIG. 6 is a port connection schematic diagram of a routing node according to an embodiment of the present application;

FIG. 7 is a schematic diagram of a routing node connected to a source node according to an embodiment of the present application;

Fig. 8 is a block diagram of an apparatus for transmitting a routing request according to an embodiment of the present application.

Detailed Description

The thinned fat tree network is derived from the fat tree network, and compared with the traditional fat tree network, the thinned fat tree network structure has the following advantages:

(1) The number of layers and the number of nodes of the routing node are greatly reduced, so that the complexity of the network is reduced, the number of high-layer links is reduced, and the network cost is reduced;

(2) The utilization rate of a higher-layer link is improved;

(2) The load of the link of the routing node at the lower layer is reduced, and the load of the link of the routing node at the lower layer is reduced;

(4) Compared with the traditional fat tree network, the thinned fat tree network has a shorter network diameter, and can effectively reduce network transmission delay.

Fig. 1 is a schematic diagram of a four-layer thinned fat tree network structure according to an embodiment of the present application, as shown in fig. 1, circles in a flutter structure represent routing nodes, each routing node contains four link ports of two in and two out, the routing node does not generate network traffic and is responsible for transmission, routing and relay of traffic generated by a terminal node, a box in a topology represents a terminal node, and each terminal node has a requirement of sending and receiving traffic, and a specific topology structure is as follows:

1) A relationship between the number of layer 0 routing nodes k ₀ and the number of source nodes n, k ₀ =n/2;

2) The relation between the topological structure layer number l and the source node number n is l= (log ₂ n) -1;

3) The relationship of the number of i-layer routing nodes, k _i, to the number of i-layer routing nodes, k _i-1, k _i＝k_i-1/2, where i ε {1,2,..l };

4) Each routing node of the i-th layer is connected with four routing nodes of the i-1-th layer, i epsilon {1,2,..l };

Assuming that one routing node of the ith layer is encoded as d _i, the connection of the four routing nodes of the ith-1 layer linked thereto, encoded as d _i-1,0、d_i-1,1、d_i-1,2、d_i-1,3, is as follows:

d_i-1,0＝bin(2*d_i)^bin(0)

d_i-1,1＝bin(2*d_i)^bin(1)

d_i-1,2＝bin(2*d_i)^bin(2)

d_i-1,3＝bin(2*d_i)^bin(3)

wherein, bin converts the integer into binary form, and the A is binary form and is exclusive-OR function according to the bit;

5) Each routing node of layer 0 is connected to four source nodes, assuming that one routing node of layer 0 is coded as d _i, and the connections of the four source nodes of the source node linked thereto are coded as s ₀、s₁、s₂、s₃, the relationship is as follows:

s₀＝bin(2*d_i)^bin(0)

s₁＝bin(2*d_i)^bin(1)

s₂＝bin(2*d_i)^bin(2)

s₃＝bin(2*d_i)^bin(3)

6) Each line in the topology is bi-directional.

The dual-host function means that two hosts are connected in the system, namely, two hosts are connected on a network topology, a source node of a control part of each host divides the network into two subnets, and the dual hosts work together to achieve the effects of improving the reliability, fault tolerance and performance of the system.

For a fat-tree topology structure supporting the thinning of dual hosts, there is a need that two sub-networks controlled by two hosts do not interfere with each other, however, when a routing path is selected by a conventional routing algorithm, a situation that a source node inside a single sub-network transmits a data packet to each other by using a routing node and a path of an adjacent sub-network may occur, for example, fig. 2 is a schematic diagram of a thinned fat-tree network structure of dual hosts according to an embodiment of the present application, as shown in fig. 2, a terminal node 0-11 and a routing node to which the terminal node belongs are controlled by a first host, belong to a first sub-network, and a routing node set D _0,i included in an i-th layer in the first sub-network is specifically as follows:

the terminal nodes 12-31 and the routing nodes to which they belong are controlled by the second host, and the routing node set D _0,i included in the ith layer in the first subnetwork of the second subnetwork is specifically as follows:

when the source node 16 of the second subnetwork transmits data packets to the source node 13, if a conventional routing algorithm is used, one path that may exist is:

Source node 16- > routing node 9 (layer 0) - > routing node 5 (layer 1) - > routing node 2 (layer 2) - > routing node 0 (layer 3) - > routing node 0 (layer 2) - > routing node 2 (layer 1) - > routing node 6 (layer 0) - > source node 13;

Wherein the path of "routing node 0 (layer 2) - > routing node 2 (layer 1) '' belongs to the first subnetwork. That is, when the second sub-network transmits data, the routing node and path of the first sub-network are used, and the routing resource of the first sub-network is occupied, so that the two sub-networks are mutually disturbed.

Therefore, based on the above problems, the application provides a self-adaptive routing algorithm of a thinned fat-tree network structure suitable for double-host control, which dynamically monitors routing node sets of each layer in a sub-network controlled by double hosts according to the routing node sets contained in each layer in the sub-network, thereby avoiding the condition that other sub-network routing resources are occupied during data transmission, ensuring the mutual noninterference among the sub-networks, realizing self-adaptive routing during data transmission, and improving the high-efficiency utilization of network resources and the quick response of data transmission.

Embodiments of the present application will be described in detail below with reference to the accompanying drawings in conjunction with the embodiments.

It should be noted that the terms "first," "second," and the like in the description and the claims of the present application and the above figures are used for distinguishing between similar objects and not necessarily for describing a particular sequential or chronological order.

The method embodiments provided in the embodiments of the present application may be executed in a server apparatus or similar computing device. Taking the example of running on a server device, fig. 3 is a block diagram of the hardware structure of the server device of the method for sending a routing request according to an embodiment of the present application. As shown in fig. 3, the server device may include one or more (only one is shown in fig. 3) processors 302 (the processor 302 may include, but is not limited to, a microprocessor MCU, a programmable logic device FPGA, or the like processing means) and a memory 304 for storing data, wherein the server device may further include a transmission device 306 for communication functions and an input-output device 308. It will be appreciated by those of ordinary skill in the art that the structure shown in fig. 3 is merely illustrative and is not intended to limit the structure of the server apparatus described above. For example, the server device may also include more or fewer components than shown in fig. 3, or have a different configuration than shown in fig. 3.

The memory 304 may be used to store a computer program, for example, a software program of application software and a module, such as a computer program corresponding to a method of sending a routing request in an embodiment of the present application, and the processor 302 executes the computer program stored in the memory 304, thereby performing various functional applications and data processing, that is, implementing the above-mentioned method. Memory 304 may include high-speed random access memory, and may also include non-volatile memory, such as one or more magnetic storage devices, flash memory, or other non-volatile solid-state memory. In some examples, memory 304 may further include memory located remotely from processor 302, which may be connected to the server device via a network. Examples of such networks include, but are not limited to, the internet, intranets, local area networks, mobile communication networks, and combinations thereof.

The transmission device 306 is used to receive or transmit data via a network. Specific examples of the network described above may include a wireless network provided by a communication provider of a server device. In one example, the transmission device 306 includes a network adapter (Network Interface Controller, simply referred to as a NIC) that may connect to other network devices through a base station to communicate with the internet. In one example, the transmission device 106 may be a Radio Frequency (RF) module, which is configured to communicate with the internet wirelessly.

In this embodiment, a method for sending a routing request is provided, and fig. 4 is a flowchart of a method for sending a routing request according to an embodiment of the present application, as shown in fig. 4, where the flowchart includes the following steps:

Step S402, obtaining codes of a source terminal and a target terminal, wherein the source terminal and the target terminal are source nodes in the thinned fat-tree network structure, and the source terminal and the target terminal are in the same sub-network;

The source terminal S may be a transmitting node terminal of the data routing request, the code of which may be represented by a binary number, for example, in a four-layer thinned fat-tree network structure, the terminal node 12 may be represented by 01100, the code of which may be represented by a binary number, for example, in a four-layer thinned fat-tree network structure, the terminal node 7 may be represented by 00111, and binary representations of the source terminal and the target terminal may be acquired, respectively, when routing is required.

Step S404, determining a target layer where a nearest public parent node is located in the thinned fat tree network structure according to codes of the source terminal and the target terminal, wherein the public parent node is a common parent node of the source terminal and the target terminal;

The parent node may be a routing node directly connected to the current routing node in a routing node of a layer above the current routing node in the tree structure, and the common parent node may be a common parent node of two routing nodes in the tree structure, that is, a lowest common ancestor node of two nodes, for example, in fig. 1, the parent node of the layer 0 node 4 is a layer 1 node 2 and a node 3, the parent node of the layer 0 node 9 is a layer 1 node 4 and a node 5, and the common parent nodes of the layer 0 node 4 and the node 9 are a layer 3 node 0 and a node 1. The number of layers where the nearest common parent node is located is determined in the thinned fat-tree network structure by the binary representation of the source terminal S and the binary representation of the target terminal D.

Specifically, under the condition that codes of the source terminal and the target terminal are represented by X-bit binary numbers, performing binary form bit exclusive-OR operation on the codes of the source terminal and the target terminal to obtain an exclusive-OR result, wherein X is an integer greater than 2, and determining a target layer where the nearest public father node is located in the thinned fat tree network structure through the exclusive-OR result.

Step S406, according to the source terminal, the target sub-network where the target terminal is located, and the routing nodes included in the first routing node set and the second routing node set, the target routing request sent by the source terminal is transmitted upward to the target parent node on the target layer through the routing nodes in the target sub-network, and the target parent node transmits the target routing request downward to the target terminal through the routing nodes in the target sub-network, where the target sub-network is the first sub-network or the second sub-network.

The target sub-network may be a sub-network where the source terminal and the target terminal are located, where the source terminal and the target terminal are located in the same sub-network, the sub-network may be a first sub-network or a second sub-network in the thinned fat-tree network structure shown in fig. 2, the first routing node set includes routing nodes in the first sub-network, the second routing node set includes routing nodes in the second sub-network, and the target parent node may be any public parent node in a layer number where a nearest public parent node is located.

According to the source terminal, the target sub-network where the target terminal is located and the routing nodes included in each sub-network, determining the routing nodes, sending the target routing request from the source terminal to the target father node through the determined routing nodes, and then sending the target routing request to the target terminal through the target father node.

The method comprises the steps of obtaining codes of a source terminal and a target terminal, wherein the source terminal and the target terminal are source nodes in a thinned fat tree network structure, the source terminal and the target terminal are in the same sub-network, determining a target layer where a nearest public father node is located in the thinned fat tree network structure according to the codes of the source terminal and the target terminal, wherein the public father node is a father node common to the source terminal and the target terminal, and transmitting a target routing request sent by the source terminal to the target father node on the target layer through a routing node in the target son network according to a target son network where the source terminal and the target terminal are located and a routing node included in a first routing node set and a second routing node set, and transmitting the target routing request downwards to the target terminal through the routing node in the target son network by the target father node, wherein the target son network is the first son network or the second son network. The method solves the problem of mutual interference among the sub-networks in the data transmission process in the related technology, achieves the effect of mutual non-interference among the sub-networks, and improves the high-efficiency utilization of network resources and the quick response of data transmission.

The main execution body of the above steps may be a server, a terminal, or the like, but is not limited thereto.

As an optional implementation manner, determining the target layer where the nearest public father node is located in the thinned fat tree network structure through the exclusive or result comprises deleting the lower two bits in the exclusive or result to obtain a first target binary number, determining the bit number of the bit where the non-zero value appears first in the first target binary number according to the sequence from low to high, and determining the bit number of the bit as the layer number of the target layer where the nearest public father node is located.

For example, in the thinned network structure shown in fig. 2, assuming that the source terminal node S is encoded as 15, the target terminal node D is encoded as 27, binary representations thereof are s=01111 and d=11010, respectively, performing bitwise exclusive-or operation on S and D, and deleting the lower two bits in the exclusive-or result, so as to obtain a first target binary number I, where a specific calculation manner of the first target binary number I is as follows:

I=011_^110_=101_

Each bit in the target binary number I is traversed from high to low, and the number of bits of the first occurring bit with a value of non-zero is determined as the number of layers of the target layer where the nearest public parent node is located, where the number of bits of the bit should be determined from low to high, for example, i=101, and it can be seen that the number of layers of the target layer where the nearest public parent node is located is 3 when the first occurring bit with a value of 1 is 3.

As an optional implementation manner, according to the destination sub-network where the source terminal and the destination terminal are located and the routing nodes included in the first routing node set and the second routing node set, the destination routing request sent by the source terminal is transmitted upwards to the destination father node on the destination layer through the routing nodes in the destination sub-network, where the destination routing request is transmitted upwards to the routing node with the j-th layer encoded as d _j in the thinned fat tree network structure, the encoding d _j+1,0、d_j+1,1, i e {0,1,..m } of two routing nodes connected with the d _j in the j+1-th layer is determined, where m is greater than or equal to 1 and less than or equal to the m; and sending the target routing request from the d _j to the d _j+1,0 or the d _j+1,1 according to whether the d _k+1,0、d_j+1,1 is located in a target routing node set corresponding to the target subnetwork, where the target routing node set is the first routing node set when the target subnetwork is the first subnetwork, and the target routing node set is the second routing node set when the target subnetwork is the second subnetwork.

The target routing node set includes routing nodes in a target sub-network, where the target routing node set may be a first routing node set or may be a second routing node set, where each routing node in the target routing node set is directly connected to two routing nodes of a previous layer, fig. 5 is an uplink port connection schematic diagram of routing nodes according to an embodiment of the present application, as shown in fig. 5, each circle represents one routing node, each routing node d _j of a j-th layer is connected to two routing nodes d _j+1,0、d_j+1,1 of a j-th layer, and it is determined that the sub-network where the routing node of the j-th layer is located, and if the routing node of the j-th layer is located in the same state as a source terminal and a target terminal in the target sub-network, a target routing request is sent from the routing node d _j of the j-th layer to the routing node of the target routing node set of the j-th layer, and repeatedly executing the steps until the target routing request is sent to the target parent node.

Specifically, according to whether d _j+1,0、d_j+1,1 is located in the set of target routing nodes corresponding to the target subnetwork, a first target routing node is determined at d _j+1,0、d_j+1,1, and the target routing request is sent from d _j to the first target routing node.

For example, the target sub-network where the source terminal and the target terminal are located is a first sub-network, the routing node d _i+1,0 of the j+1th layer is in the first routing node set, the routing node d _i+1,0 is determined as the first target routing node when the routing node d _i+1,1 is in the second routing node set, and meanwhile, the target routing request is sent from the routing node d _j of the j+1th layer to the first target routing node d _i+1,0 of the j+1th layer. And determining the transmitted routing node according to the sub-network where the source terminal, the target terminal and the routing node are located, which is beneficial to ensuring that data transmission is only carried out in the sub-network and avoiding occupying the routing resources of the adjacent sub-network.

Alternatively, the d _j+1,0, the d _j+1,1 are obtained by the following formula:

As an alternative implementation manner, according to whether d _j+1,0、d_j+1,1 is located in the target routing node set corresponding to the target sub-network, determining a first target routing node at d _j+1,0、d_j+1,1 includes determining that one routing node is the first target routing node at random in d _j+1,0、d_j+1,1 when d _j+1,0、d_j+1,1 is located in the target routing node set, or determining that a routing node with the shortest distance from d _j in d _j+1,0、d_j+1,1 is the first target routing node when d _j+1,0、d_j+1,1 is located in the target routing node set, or determining that a routing node with the smallest load in d _j+1,0、d_j+1,1 is the first target routing node when d _j+1,0、d_j+1,1 is located in the target routing node set.

The mode of selecting the first target routing node can be selected according to specific application scenes and system requirements, for example, the randomness of a system can be increased by randomly selecting one routing node, the risk of unbalanced node load is reduced, the delay of data transmission can be reduced by selecting the routing node with the shortest distance, the instantaneity of the system is improved, the load of the system can be effectively balanced by selecting the routing node with the smallest load, the pressure of a single node is reduced, the stability and the reliability of the system are improved, and the like.

As an optional implementation manner, determining the first target routing node at d _j+1,0、d_j+1,1 according to whether d _j+1,0、d_j+1,1 is located in the target routing node set corresponding to the target subnetwork, where the node in d _j+1,0、d_j+1,1 is located in the target routing node set, determining the node in d _j+1,0、d_j+1,1 located in the target routing node set as the first target routing node.

As an optional implementation manner, each routing node in the thinned fat tree network structure comprises two uplink ports and four downlink ports, wherein the two uplink ports are respectively a first uplink port and a second uplink port, the codes of the first uplink port are smaller than those of the second uplink port, the four downlink ports are respectively a first downlink port, a second downlink port, a third downlink port and a fourth downlink port, the codes of the first downlink port, the codes of the second downlink port, the codes of the third downlink port and the codes of the fourth downlink port are sequentially increased, the codes of a routing node d _i on an ith layer in the thinned fat tree network structure are respectively connected with four routing nodes of a d _i-1,0、d_i-1,1、d_i-1,2、d_i-1,3 on an ith-1 layer, the codes of d _i-1,0、d_i-1,1、d_i-1,2、d_i-1,3 are sequentially increased, the codes of the first downlink port, the codes of the third downlink port and the fourth downlink port are sequentially increased, the codes of the routing node d _i on the ith layer in the thinned fat tree network structure are sequentially increased, and the codes of the first node d _i on the first layer in the fat tree network structure are sequentially increased, and the codes of the node d 3725 on the second layer in the fat tree network structure are sequentially increased.

The thinned fat-tree network structure can be divided into a plurality of sub-networks, such as 2,3, 4, etc., and the number of the source nodes and the routing nodes contained in each sub-network is not limited, and only the source nodes in each sub-network are required to be guaranteed to be adjacent. Taking two sub-networks as an example, the thinned fat tree network structure is divided into two sub-networks, namely a first sub-network and a second sub-network, wherein the first sub-network and the second sub-network can be randomly divided, so long as the source node labels of the first sub-network are smaller than the source node labels of the second sub-network, namely, the source nodes in the two sub-networks are ensured to be adjacent, the two sub-networks can be mutually independent and do not interfere with each other, for example, as shown in fig. 2, the source nodes 0-11 belong to the first sub-network, and the source nodes 12-31 belong to the second sub-network.

In the thinned fat tree network structure, each routing node is directly connected with six routing nodes, for example, fig. 6 is a port connection schematic diagram of a routing node according to an embodiment of the present application, as shown in fig. 6, each circle represents one routing node, each routing node of the ith layer is connected with two routing nodes of the (i+1) th layer and four routing nodes of the (i-1) th layer, where the routing node d _i+1,0、d_i+1,1 of the (i+1) th layer corresponds to a first uplink port and a second uplink port coded as 1 and 2, and the routing node d _i-1,0、d_i-1,1、d_i-1,2、d_i-1,3 of the (i-1) th layer corresponds to a first downlink port, a second downlink port, a third downlink port and a fourth downlink port coded as 1, 2, 3 and 4, respectively, and each routing node is connected with a plurality of uplink ports and a plurality of downlink ports, so that flexibility and fault tolerance of the network can be enhanced, and efficiency and reliability of data transmission can be improved.

As an alternative implementation manner, the destination routing request is transmitted downwards to the destination terminal by the destination father node through the routing node in the destination sub-network, and the method comprises the steps of performing binary form bit exclusive OR operation on codes of the source terminal and the destination terminal under the condition that the codes of the source terminal and the destination terminal are represented by X-bit binary numbers to obtain an exclusive OR result, wherein X is an integer greater than 2, obtaining m valid bits through the exclusive OR result, and transmitting the destination routing request downwards to the destination terminal by the destination father node through a downlink port of the routing node in the destination sub-network according to the m valid bits.

The m valid bits may be determined according to an exclusive or result obtained by performing binary form bit exclusive or operation on the code S of the source terminal and the code D of the target terminal, traversing the m valid bits in order from high to low, determining a downlink port of the routing node corresponding to each valid bit according to the value on each valid bit, and transmitting the target routing request to the target terminal through the determined downlink port.

The method comprises the steps of deleting the lower two bits in the code of the target terminal to obtain a second target binary number, and determining m bits from low to high of the second target binary number as m valid bits under the condition that an m-th layer is the target layer of the nearest public father node.

For example, the source terminal node S encodes 9, the target terminal node D encodes 1, the binary representations of the source terminal node S and the target terminal node D are s=01001 and d=00001, the binary exclusive-or operation is performed on S and D, and the lower two bits in the exclusive-or result are deleted, so as to obtain a first target binary number I, where a specific calculation manner of the first target binary number I is as follows:

I=010_^000_=010_

The first target binary number I can show that the target layer where the nearest public father node is located is layer 2, the lower two bits of the binary representation of the target terminal are intercepted to obtain a second target binary number, and the two bits from low to high in the second target binary number are determined to be target binary numbers DI= _00__.

As an alternative implementation manner, the method for transmitting the target routing request downwards to the target terminal through the downlink port of the routing node in the target sub-network according to the m valid bits comprises the steps of determining codes d _r-1,0、d_r-1,1、d_r-1,2、d_r-1,3 r epsilon {0,1,. M } of four routing nodes connected with the d _r in a r-1 layer when the target routing request is transmitted downwards to the routing node coded as d _r in the thinned fat tree network structure, wherein the target layer is an m-th layer, m is greater than or equal to 1 and less than or equal to l, determining a first routing node and a second routing node in the d _r-1,0、d_r-1,1、d_r-1,2、d_r-1,3 according to the m valid bits, and transmitting the target routing request from the d _r to the first routing node or the second routing node according to whether the first routing node and the second routing node are located in a target routing node set corresponding to the target sub-network.

As shown in fig. 6, each routing node is connected with four routing nodes of the next layer, a first routing node and a second routing node of a routing node d _r corresponding to each valid bit are determined according to the value of each valid bit on m valid bits DI of a binary representation of a target terminal, and the target routing request is sent from d _r to the first routing node or the second routing node according to a sub-network where the first routing node and the second routing node are located.

Specifically, d ' _r-1,0、d′_r-1,1、d′_r-1,2、d′_r-1,3 is obtained by reordering d _r-1,0、d_r-1,1、d_r-1,2、d_r-1,3 to obtain d ' _r-1,0、d′_r-1,1、d′_r-1,2、d′_r-1,3, wherein the codes of d ' _r-1,0、d′_r-1,1、d′_r-1,2、d′_r-1,3 are sequentially increased, d ' _r-1,2 connected with a third downlink port of d _r is determined to be the first routing node when the code of the r layer is a non-zero value in m valid bits, d ' _r-1,3 connected with the fourth downlink port is determined to be the second routing node when the code of the r layer is a zero value in m valid bits, d ' _r-1,0 connected with a first downlink port of d _r is determined to be the first routing node when the code of the m valid bits is a zero value in m valid bits, and d ' _r-1,1 connected with a second downlink port of d _r is determined to be the second routing node.

Alternatively, the d _r-1,0、d_r-1,1、d_r-1,2、d_r-1,3 is obtained by the following formula:

d_r-1,0＝bin(2*d_r)^bin(0);

d_r-1,1＝bin(2*d_r)^bin(1);

d_r-1,2＝bin(2*d_r)^bin(2);

d_r-1,3＝bin(2*d_r)^bin(3);

As an optional implementation manner, the step of sending the target routing request from d _r to the first routing node or the second routing node according to whether the first routing node and the second routing node are located in the target routing node set corresponding to the target sub-network includes determining a second target routing node in the first routing node or the second routing node according to whether the first routing node and the second routing node are located in the target routing node set, and sending the target routing request from d _r to the second target routing node.

For example, the target sub-network where the source terminal and the target terminal are located is a second sub-network, the first routing node is in the first routing node set, and the second routing node is in the second routing node set, then the second routing node is determined to be the second target routing node, and meanwhile, the target routing request is sent from d _r to the second target routing node. And determining the transmitted routing node according to the sub-network where the source terminal, the target terminal and the routing node are located, which is beneficial to ensuring that data transmission is only carried out in the sub-network and avoiding occupying the routing resources of the adjacent sub-network.

Specifically, when the first routing node and the second routing node are both located in the target routing node set, one routing node is randomly selected by the first routing node and the second routing node to be determined as the second target routing node, or when the first routing node and the second routing node are both located in the target routing node set, the routing node with the shortest distance from d _r in the first routing node and the second routing node is determined as the second target routing node, or when the first routing node and the second routing node are both located in the target routing node set, the routing node with the smallest load in the first routing node and the second routing node is determined as the second target routing node.

The mode of selecting the second target routing node can be selected according to specific application scenes and system requirements, for example, the randomness of a system can be increased by randomly selecting one routing node, the risk of unbalanced node load is reduced, the delay of data transmission can be reduced by selecting the routing node with the shortest distance, the instantaneity of the system is improved, the load of the system can be effectively balanced by selecting the routing node with the smallest load, the pressure of a single node is reduced, the stability and the reliability of the system are improved, and the like.

As an optional implementation manner, according to whether the first routing node and the second routing node are located in the target routing node set, determining a second target routing node in the first routing node and the second routing node, and determining a node located in the target routing node set in the first routing node and the second routing node as the second target routing node in the case that one routing node in the first routing node and the second routing node is located in the target routing node set.

As an optional implementation manner, the routing node coded as d ₀ of the layer 0 in the thinned fat tree network structure is connected with four source nodes coded as s ₀、s₁、s₂、s₃, and the relationship between d ₀ and s ₀、s₁、s₂、s₃ is that:

s₀＝bin(2*d₀)^bin(0);

s₁＝bin(2*d₀)^bin(1);

s₂＝bin(2*d₀)^bin(2);

s₃＝bin(2*d₀)^bin(3);

Fig. 7 is a schematic structural diagram of connection between a routing node and a source node according to an embodiment of the present application, as shown in fig. 7, a circle represents a routing node, each square represents a source node, each routing node is connected to four source nodes, a corresponding port is selected according to the last two bits of the binary representation of the target terminal, a target routing request is sent from the target routing node to the target terminal, for example, the last two bits are 00, an S0 port is selected, the last two bits are 01, an S1 port is selected, the last two bits are 10, an S2 port is selected, and the last two bits are 11, an S3 port is selected.

As an alternative embodiment, taking the fat tree network topology thinned in fig. 2 as an example, assume that the source terminal s=10000 (code 16) located in the second sub-network sends a target routing request to the target terminal d=01101 (code 13) also located in the first sub-network, and the specific routing method is as follows:

step S0, route node sets are divided according to two networks:

the routing node set D _0,i included in the ith layer of the first subnetwork and the routing node set D _1,i included in the ith layer of the second subnetwork are calculated, as shown in fig. 2, where the routing node sets included in each layer of the first subnetwork are as follows:

the routing node set contained in each layer of the second sub-network is as follows:

Step S1, performing exclusive or on the binary representations of the source terminal S and the destination terminal D by bits, and removing the lowest two bits from the exclusive or result, where the result is recorded as i=100_ 011_ =111_.

Step S2, determining the layer number of the nearest public father node of the source terminal S and the target terminal D:

Looking at bit of '1' in I from high to low, the first occurrence of bit takes on value '1', at bit 3, the nearest public parent node of S and D is at layer 3. The significant bit m of I is 3 bits from low to high.

Step S3, routing from S up to S and D a nearest common parent node F:

S301, calculating codes d _0,0、d′_0,1 of two routing nodes of the 0 th layer connected with the S according to the specific calculation formula as follows, wherein the current target routing request is in the S:

d_0,0＝bin(d_i/2)=1000

d_0,1＝bin(d_i/2)^bin(1)=1001

Judging whether D _0,0、d_0,1 is located in a routing node set D _1,0 of the layer 0 of the second sub-network, wherein D _0,0、d_0,1 is located in D _1,0, and then the routing can be upwards routed through any one of two ports upwards in S, assuming that D _0,1 =1001 is reached through a port 2 upwards in S, but the layer 3 of the nearest public father node F is not reached, and continuing the upward routing;

S302, the current destination route request is d _0,1 =1001, and the codes d _1,0、d_1,1 of the two routing nodes of the layer 1 connected with d _0,1 =1001 are calculated as follows:

d_1,0＝bin(d_0,1/2)=0100

d_1,1＝bin(d_0,1/2)^bin(1)=0101

Judging whether D _1,0、d_1,1 is located in the routing node set D _1,1 of the layer 1 of the second sub-network, wherein D _1,0、d_1,1 is located in D _1,1, and then the routing can be upwards performed through any one of two ports upwards with D _0,1 =1001, assuming that D _1,1 =0101 is reached through port 2 upwards with D _0,1 =1001, but the layer 3 where the nearest public father node F is located is not reached, and continuing the upward routing;

s303, calculating the codes d _2,0、d_2,1 of two routing nodes of the layer 2 connected with d _1,1 =0101, wherein the specific calculation formula is as follows:

d_2,0＝bin(d_1,1/2)=0010

d_2,1＝bin(d_1,1/2)^bin(1)=0011

Judging whether D _2,0、d_2,1 is located in a routing node set D _1,2 of the layer 2 of the second sub-network, wherein D _2,0、d_2,1 is located in D _1,2, and then the upward routing can be carried out through any one of two ports upward with D _1,1 =0101;

S304, calculating codes d _3,0、d_3,1 of two routing nodes of the 3 rd layer connected with d _2,0 =0010, wherein the specific calculation formula is as follows:

d_3,0＝bin(d_2,0/2)=0000

d_3,1＝bin(d_2,0/2)^bin(1)=0001

Determining whether D _3,0、d_3,1 is located in the routing node set D _1,3 of the third layer of the second subnetwork, that D _3,0、d_3,1 is located in D _1,3, the route can be upward through any one of the two ports upward with D _2,0 =0010, and assuming that D _3,1 =0001 is reached through port 2 upward with D _2,0 =0010, the nearest public parent node D _3,1 =0001 is reached, that is, the target parent node of the third layer of the target layer (the nearest public parent node F) is reached, and the downward route starts.

Step S4, the target parent node 0001 of the third layer is routed downward to the routing node 0110 of layer 0 connected to the target terminal d=01101:

Intercepting the significant bit corresponding to D according to the significant bit of I to obtain DI=011 __, looking up the significant bit of DI from high to low, and for each significant bit The following steps are performed:

The first valid bit of DI from high to low is 0 in S101, which is already routed to layer 3 routing node d _3,1 =0001, and four layer 2 routing nodes d _2,0、d_2,1、d_2,2、d_2,3 connected to d _3,1 =0001 are calculated as follows:

d_2,0＝bin(2*d₃)^bin(0)=0010

d_2,1＝bin(2*d₃)^bin(1)=0011

d_2,2＝bin(2*d₃)^bin(2)=0000

d_2,3＝bin(2*d₃)^bin(3)=0001

The four routing nodes are ordered from small to large to obtain d' _2,0＝0000、d′_2,1＝0001、d′_2,2＝0010、d′_2,3 =0011, and the valid bit is at the moment Selecting the downward output ports with the left side being numbered 1 and 2 to be routed downwards to the next layer, focusing on D ' _2,0＝0000、d′_2,1 =0001 only, judging the routing node set where D ' _2,0＝0000、d′_2,1 =0001 is located, and selecting the downward output port with the number being numbered 2 to be routed downwards to the next layer because D ' _2,1 is located in D _1,2 only;

The second valid bit of DI from high to low is 1 in S102, which is already routed to layer 2 routing node d '_2,1 =0001, and the four layer 1 routing nodes d _1,0、d_1,1、d_1,2、d_1,3 connected to d' _2,1 =0001 are calculated as follows:

d_1,0＝bin(2*d_2,1)^bin(0)=0010

d_1,1＝bin(2*d_2,1)^bin(1)=0011

d_1,2＝bin(2*d_2,1)^bin(2)=0000

d_1,3＝bin(2*d_2,1)^bin(3)=0001

The four routing nodes are ordered from small to large to obtain d' _1,0＝0000、d′_1,1＝0001、d′_1,2＝0010、d′_1,3 =0011, and the valid bit is at the moment Selecting the downward output ports with the right side being marked with 3 and 4 to be routed downwards to the next layer, focusing on D ' _1,2＝0010、d′_1,3 =0011 only, judging the routing node set where D ' _1,2＝0010、d′_1,3 =0011 is located, and selecting the downward output port with the right side being marked with 4 to be routed downwards to the next layer because D ' _1,3 =0011 is located in D _1,1;

The third valid bit of DI from high to low is 1 in S103, and the routing node d' _1,3 =0011 already routed to layer 1 is calculated as follows:

d_0,0＝bin(2*d_1,3)^bin(0)=0110

d_0,1＝bin(2*d_1,3)^bin(1)=0111

d_0,2＝bin(2*d_1,3)^bin(2)=0100

d_0,3＝bin(2*d_1,3)^bin(3)=0101

The four routing nodes are ordered from small to large to obtain d' _0,0＝0100、d′_0,1＝0101、d′_0,2＝0110、d′_0,3 =0111, and the valid bit is at the moment The down output ports numbered 3 and 4 on the right are selected to be routed down to the next layer, only D '_0,2＝0110、d′_0,3 =0111 is concerned at this time, the set of routing nodes where D' _0,2＝0110、d′_0,3 =0111 is determined to be located is selected to be routed down to the next layer because D '_0,2＝0110、d′_0,3 =0111 is located in D _1,0, the down output ports numbered 3 or 4 are selected to be routed down to the next layer, the selected port numbered 4 is assumed to be routed down, D' _0,3 =0111 is reached to the 0 th layer at this time, and the valid bit traversal is completed.

And S5, routing from the routing node of the 0 th layer connected with the target terminal D to the target terminal D, wherein the lowest two digits of the D are checked to be 01, and then the routing from the output port S1 corresponding to the routing node D' _0,3 =0111 connected with the D at the 0 th layer to the target terminal D is finished, and the destination D=01101 is reached at the moment, and the routing is finished.

From the description of the above embodiments, it will be clear to a person skilled in the art that the method according to the above embodiments may be implemented by means of software plus the necessary general hardware platform, but of course also by means of hardware, but in many cases the former is a preferred embodiment. Based on such understanding, the technical solution of the present application may be embodied essentially or in a part contributing to the prior art in the form of a software product stored in a storage medium (e.g. ROM/RAM, magnetic disk, optical disk) comprising instructions for causing a terminal device (which may be a mobile phone, a computer, a server, or a network device, etc.) to perform the method according to the embodiments of the present application.

In this embodiment, a device is further provided, and the device is used to implement the foregoing embodiments and preferred embodiments, which are not described in detail. As used below, the term "module" may be a combination of software and/or hardware that implements a predetermined function. While the means described in the following embodiments are preferably implemented in software, implementation in hardware, or a combination of software and hardware, is also possible and contemplated.

Fig. 8 is a block diagram of an apparatus for sending a routing request according to an embodiment of the present application, as shown in fig. 8, where the apparatus includes an obtaining module 802 configured to obtain codes of a source terminal and a target terminal, where the source terminal and the target terminal are source nodes in a thinned fat-tree network structure, and the source terminal and the target terminal are in the same sub-network, a determining module 804 configured to determine a target layer where a nearest common parent node is located in the thinned fat-tree network structure according to the codes of the source terminal and the target terminal, where the common parent node is a common parent node of the source terminal and the target terminal, and a sending module 806 configured to transmit a target routing request sent by the source terminal to a target parent node on the target layer through a routing node in a first routing node set and a second routing node set, where the target node transmits the target request to the target node through the destination node in the target sub-network is a first routing node, and the target node is a second routing node in the first routing node set, and the target node is the second routing node is the first routing node.

In an exemplary embodiment, the apparatus is further configured to, in a case where the codes of the source terminal and the target terminal are represented by X-bit binary numbers, perform a binary type bitwise exclusive-or operation on the codes of the source terminal and the codes of the target terminal to obtain an exclusive-or result, where X is an integer greater than 2, and determine, in the thinned fat-tree network structure, a target layer where the nearest public parent node is located by the exclusive-or result.

In an exemplary embodiment, the apparatus is further configured to delete the lower two bits in the exclusive-or result to obtain a first target binary number, determine, in order from low to high, a number of bits of the first target binary number where the first non-zero value occurs, and determine the number of bits of the first bit as a number of layers of a target layer where the nearest common parent node is located.

In an exemplary embodiment, the apparatus is further configured to determine codes d _j+1,0、d_j+1,1, i e {0, 1..m } of two routing nodes connected to the d _j in a j+1 th layer, where the target routing request is transmitted up to a routing node coded as d _j in the thinned fat-tree network structure, the target layer being the m-th layer, where m is greater than or equal to 1 and less than or equal to the l, and send the target routing request from the d _j to the d _j+1,0 or the d _j+1,1 according to whether the d _j+1,0、d_j+1,1 is located in a set of target routing nodes corresponding to the target subnetwork, where the set of target routing nodes is the first set of routing nodes in a case where the target subnetwork is the second subnetwork.

In an exemplary embodiment, the apparatus is further configured to obtain the d _j+1,0, the d _j+1,1 by the following formula:

In an exemplary embodiment, the apparatus is further configured to determine a first target routing node at d _j+1,0、d_j+1,1 according to whether d _j+1,0、d_j+1,1 is located in a set of target routing nodes corresponding to the target subnetwork, and send the target routing request from d _j to the first target routing node.

In an exemplary embodiment, the apparatus is further configured to determine, if the d _j+1,0、d_j+1,1 are both located in the target routing node set, that one routing node is randomly selected by the d _j+1,0、d_j+1,1 to be the first target routing node, or determine, if the d _j+1,0、d_j+1,1 are both located in the target routing node set, that a routing node in the d _j+1,0、d_j+1,1 that is the shortest distance from the dj is the first target routing node, or determine, if the d _j+1,0、d_j+1,1 are both located in the target routing node set, that a routing node in the d _j+1,0、d_j+1,1 that is the least loaded is the first target routing node.

In an exemplary embodiment, the apparatus is further configured to determine a node in d _j+1,0、d_j+1,1 that is located in the set of target routing nodes as the first target routing node if one routing node in d _j+1,0、d_j+1,1 is located in the set of target routing nodes.

In an exemplary embodiment, the apparatus is further configured to, when the codes of the source terminal and the target terminal are represented by X-bit binary numbers, perform binary type bitwise exclusive-or operation on the codes of the source terminal and the codes of the target terminal to obtain an exclusive-or result, where X is an integer greater than 2, obtain m valid bits according to the exclusive-or result, and transmit, by the target parent node, the target routing request to the target terminal through a downstream port of a routing node in the target subnetwork according to the m valid bits.

In an exemplary embodiment, the device is further configured to delete the lower two bits in the code of the target terminal to obtain a second target binary number, and determine m bits from low to high of the second target binary number as the m significant bits if the target layer where the nearest public parent node is located is an mth layer.

In an exemplary embodiment, the apparatus is further configured to determine that, in a case where the destination routing request is transmitted down to a routing node whose r-th layer is encoded as d _r in the thinned fat-tree network structure, the encoding d _r-1,0、d_r-1,1、d_r-1,2、d_r-1,3 r e {0,1,..m } of four routing nodes connected to the d _r in the r-1-th layer is the m-th layer, m is greater than or equal to 1 and less than or equal to the l, determine a first routing node and a second routing node in the d _r-1,0、d_r-1,1、d_r-1,2、d_r-1,3 according to the m valid bits, and send the destination routing request from the d _r to the first routing node or the second routing node according to whether the first routing node and the second routing node are located in a set of destination routing nodes corresponding to the destination subnetwork.

In an exemplary embodiment, the apparatus is further configured to obtain the d _r-1,0、d_r-1,1、d_r-1,2、d_r-1,3 by the following formula:

d_r-1,0＝bin(2*d_r)^bin(0);

d_r-1,1＝bin(2*d_r)^bin(1);

d_r-1,2＝bin(2*d_r)^bin(2);

d_r-1,3＝bin(2*d_r)^bin(3);

In an exemplary embodiment, the apparatus is further configured to reorder the d _r-1,0、d_r-1,1、d_r-1,2、d_r-1,3 to obtain d '_r-1,0、d′_r-1,1、d′_r-1,2、d′_r-1,3, where the codes of d' _r-1,0、d′_r-1,1、d′_r-1,2、d′_r-1,3 increase sequentially, determine d '_r-1,2 connected to a third downstream port of the d _r as the first routing node and d' _r-1,3 connected to the fourth downstream port as the second routing node if the code of the r layer is a non-zero value in the m valid bits, determine d '_r-1,0 connected to a first downstream port of the d _r as the first routing node and d' _r-1,1 connected to a second downstream port of the d _r as the second routing node if the code of the m valid bits is a zero.

In an exemplary embodiment, the apparatus is further configured to determine a second target routing node from among the first routing node and the second routing node according to whether the first routing node and the second routing node are located in the target routing node set, and send the target routing request from the d _r to the second target routing node.

In an exemplary embodiment, the apparatus is further configured to determine, when the first routing node and the second routing node are both located in the set of target routing nodes, that one routing node is randomly selected by the first routing node and the second routing node to be determined as the second target routing node, or determine, when the first routing node and the second routing node are both located in the set of target routing nodes, that a routing node with a shortest distance from d _r of the first routing node and the second routing node is determined as the second target routing node, or determine, when the first routing node and the second routing node are both located in the set of target routing nodes, that a routing node with a smallest load of the first routing node and the second routing node is determined as the second target routing node.

In an exemplary embodiment, the apparatus is further configured to determine a node of the first routing node and the second routing node that is located in the set of target routing nodes as the second target routing node if one of the first routing node and the second routing node is located in the set of target routing nodes.

In an exemplary embodiment, the apparatus is further configured to send, by the target parent node, the target routing request to the target routing node through a routing node in the target subnetwork, where the target routing node is a node to which a target terminal is connected, and the target routing node sends, by a downstream port connected to the target terminal, the target routing request to the target terminal, and the routing node of layer 0 in the thinned fat-tree network structure, which is encoded with d ₀, is connected to four source nodes, which are encoded with s ₀、s₁、s₂、s₃, where the relationship between d ₀ and s ₀、s₁、s₂、s₃ is:

s₀＝bin(2*d₀)^bin(0);

s1=bin(2*d₀)^bin(1);

s₂＝bin(2*d₀)^bin(2);

s₃＝bin(2*d₀)^bin(3);

The binary form is an exclusive OR function by bits, the source node is a terminal connected with a routing node in the layer 0, and the source node comprises a source terminal and a target terminal.

It should be noted that each of the above modules may be implemented by software or hardware, and the latter may be implemented by, but not limited to, the above modules all being located in the same processor, or each of the above modules being located in different processors in any combination.

Embodiments of the present application also provide a computer readable storage medium having a computer program stored therein, wherein the computer program is arranged to perform the steps of any of the method embodiments described above when run.

In an exemplary embodiment, the computer readable storage medium may include, but is not limited to, a USB flash disk, a Read-Only Memory (ROM), a random access Memory (Random Access Memory, RAM), a removable hard disk, a magnetic disk, or an optical disk, etc. various media in which a computer program may be stored.

An embodiment of the application also provides an electronic device comprising a memory having stored therein a computer program and a processor arranged to run the computer program to perform the steps of any of the method embodiments described above.

In an exemplary embodiment, the electronic device may further include a transmission device connected to the processor, and an input/output device connected to the processor.

Embodiments of the application also provide a computer program product comprising a computer program which, when executed by a processor, implements the steps of any of the method embodiments described above.

Specific examples in this embodiment may refer to the examples described in the foregoing embodiments and the exemplary implementation, and this embodiment is not described herein.

It will be appreciated by those skilled in the art that the modules or steps of the application described above may be implemented in a general purpose computing device, they may be concentrated on a single computing device, or distributed across a network of computing devices, they may be implemented in program code executable by computing devices, so that they may be stored in a storage device for execution by computing devices, and in some cases, the steps shown or described may be performed in a different order than that shown or described herein, or they may be separately fabricated into individual integrated circuit modules, or multiple modules or steps of them may be fabricated into a single integrated circuit module. Thus, the present application is not limited to any specific combination of hardware and software.

The above description is only of the preferred embodiments of the present application and is not intended to limit the present application, but various modifications and variations can be made to the present application by those skilled in the art. Any modification, equivalent replacement, improvement, etc. made within the principle of the present application should be included in the protection scope of the present application.

Claims

1. A method of sending a routing request, characterized by being applied to a thinned fat-tree network structure, the thinned fat-tree network structure having a relationship between a total number of layers, i= (log ₂ n) -1, and a total number of source nodes, n, a relationship between a number of i-layer routing nodes, k _i, and a number of i-layer routing nodes, k _i-1, k _i＝k_i-1/2, i e {1, 2..i }, i being an integer greater than or equal to 1, the thinned fat-tree network structure being divided into a first sub-network and a second sub-network, a first set of routing nodes comprising routing nodes in the first sub-network, and a second set of routing nodes comprising routing nodes in the second sub-network, the method further comprising:

acquiring codes of a source terminal and a target terminal, wherein the source terminal and the target terminal are source nodes in the thinned fat-tree network structure, and the source terminal and the target terminal are in the same sub-network;

Determining a target layer where a nearest public father node is located in the thinned fat tree network structure according to codes of the source terminal and the target terminal, wherein the public father node is a father node common to the source terminal and the target terminal, and transmitting a target routing request sent by the source terminal to a target father node on the target layer through a routing node in the target sub-network according to a target sub-network where the source terminal and the target terminal are located and a routing node included in the first routing node set and the second routing node set, and transmitting the target routing request downwards to the target terminal through the routing node in the target sub-network by the target father node, wherein the target sub-network is the first sub-network or the second sub-network.

2. The method of claim 1, wherein determining a target layer in which a nearest common parent node is located in the thinned fat-tree network structure based on the encoding of the source terminal and the target terminal comprises:

Under the condition that codes of the source terminal and the target terminal are represented by X-bit binary numbers, performing binary form bit exclusive-OR operation on the codes of the source terminal and the target terminal to obtain an exclusive-OR result, wherein X is an integer greater than 2;

and determining a target layer where the nearest public father node is located in the thinned fat tree network structure through the exclusive OR result.

3. The method of claim 2, wherein determining the target layer in which the nearest common parent node is located in the thinned fat-tree network structure by the exclusive-or result comprises:

Deleting the lower two bits in the exclusive-or result to obtain a first target binary number;

Determining the number of bits in which the first occurring non-zero value is located in the first target binary number in the order from low to high;

and determining the bit number of the bit as the layer number of the target layer where the nearest public father node is located.

4. The method according to claim 1, wherein transmitting the target routing request sent by the source terminal up to the target parent node on the target layer through the routing nodes in the target child network according to the target child network where the source terminal and the target terminal are located and the routing nodes included in the first routing node set and the second routing node set, includes:

Determining codes d _j+1,0、d_j+1,1 of two routing nodes connected with d _j in a j+1 layer under the condition that the target routing request is transmitted upwards to a routing node coded as d _j in a j layer in the thinned fat tree network structure, wherein i epsilon {0, 1..m }, the target layer is an m layer, and m is greater than or equal to 1 and less than or equal to l;

And sending the target routing request from the d _j to the d _j+1,0 or the d _j+1,1 according to whether the d _j+1,0、d_j+1,1 is located in the target routing node set corresponding to the target subnetwork, wherein the target routing node set is the first routing node set when the target subnetwork is the first subnetwork, and the target routing node set is the second routing node set when the target subnetwork is the second subnetwork.

5. The method of claim 4, wherein determining the code d _j+1,0、d_j+1,1 of two routing nodes connected to d _j in a j+1 layer in the case where the target routing request is transmitted to a routing node coded as d _j in a j-th layer in the thinned fat-tree network structure, comprises:

the d _j+1,0, the d _j+1,1 are obtained by the following formula:

Wherein bin is an exclusive or function in binary form for converting an integer into a binary number, Is a round down function.

6. The method of claim 4, wherein sending the target routing request from the d _j to the d _j+1,0 or the d _j+1,1 according to the source terminal and the target sub-network in which the target terminal is located, and whether the d _j+1,0、d_j+1,1 is located in a set of target routing nodes corresponding to the target sub-network, comprises:

determining a first target routing node at d _j+1,0、d_j+1,1 according to whether d _j+1,0、d_j+1,1 is located in the set of target routing nodes corresponding to the target subnetwork;

The target routing request is sent from the d _j to the first target routing node.

7. The method of claim 6, wherein determining a first target routing node at d _j+1,0、d_j+1,1 based on whether d _j+1,0、d_j+1,1 is located in the set of target routing nodes corresponding to the target subnetwork, comprises:

in the case that the d _j+1,0、d_j+1,1 are all located in the target routing node set, randomly selecting a routing node at the d _j+1,0、d_j+1,1 to determine the routing node as the first target routing node, or

Determining the routing node with the shortest distance from the d _j in the d _j+1,0、d_j+1,1 as the first target routing node under the condition that the d _j+1,0、d_j+1,1 is positioned in the target routing node set, or

And determining the routing node with the smallest load in d _j+1,0、d_j+1,1 as the first target routing node under the condition that d _j+1,0、d_j+1,1 is located in the target routing node set.

8. The method of claim 6, wherein determining a first target routing node at d _j+1,0、d_j+1,1 based on whether d _j+1,0、d_j+1,1 is located in the set of target routing nodes corresponding to the target subnetwork, further comprising:

In the case that one routing node in d _j+1,0、d_j+1,1 is located in the target routing node set, determining the node in d _j+1,0、d_j+1,1 that is located in the target routing node set as the first target routing node.

9. The method of claim 1, wherein each of the routing nodes in the thinned fat-tree network structure comprises:

The system comprises two uplink ports and four downlink ports, wherein the two uplink ports are a first uplink port and a second uplink port respectively, and the code of the first uplink port is smaller than that of the second uplink port;

the four downlink ports are respectively a first downlink port, a second downlink port, a third downlink port and a fourth downlink port, and the codes of the first downlink port, the second downlink port, the third downlink port and the fourth downlink port are sequentially increased;

the first downlink port, the second downlink port, the third downlink port and the fourth downlink port of the routing node d _i on the ith layer in the thinned fat tree network structure are respectively connected with four routing nodes of the ith-1 layer, which are coded as d _i-1,0、d_i-1,1、d_i-1,2、d_i-1,3, and the codes of d _i-1,0、d_i-1,1、d_i-1,2、d_i-1,3 are sequentially increased;

The first uplink port and the second uplink port of the routing node d _i on the ith layer are connected with two routing nodes coded as d _i+1,0、d_i+1,1 on the (i+1) th layer, and the codes of d _i+1,0、d_i+1,1 are sequentially increased;

The source nodes of the first subnetwork in the thinned fat tree network structure are all encoded smaller than the labels of the source nodes of the second subnetwork.

10. The method of claim 9, wherein transmitting the target routing request by the target parent node down to the target terminal through a routing node in the target subnetwork, comprises:

obtaining m valid bits through the exclusive OR result;

And transmitting the target routing request downwards to the target terminal through a downlink port of a routing node in the target sub-network by the target father node according to the m valid bits.

11. The method of claim 10, wherein obtaining m significant bits from the exclusive-or result comprises:

deleting the lower two bits in the code of the target terminal to obtain a second target binary number;

and determining m bits from low to high of the second target binary number as the m significant bits under the condition that the target layer where the nearest public father node is located is an m-th layer.

12. The method of claim 10, wherein the transmitting the target routing request by the target parent node down to the target terminal through a downstream port of a routing node in the target subnetwork according to the m valid bits comprises:

Determining codes d _r-1,0、d_r-1,1、d_r-1,2、d_r-1,3 r epsilon {0, 1..m } of four routing nodes connected with d _r in an r-1 layer under the condition that the target routing request is transmitted downwards to a routing node with the r layer coded as d _r in the thinned fat tree network structure, wherein the target layer is an m-th layer, and m is greater than or equal to 1 and less than or equal to l;

Determining a first routing node and a second routing node in the d _r-1,0、d_r-1,1、d_r-1,2、d_r-1,3 according to the m valid bits;

And sending the target routing request from the d _r to the first routing node or the second routing node according to whether the first routing node and the second routing node are located in a target routing node set corresponding to the target sub-network.

13. The method of claim 12, wherein determining the code d _r-1,0、d_r-1,1、d_r-1,2、d_r-1,3 of the four routing nodes in layer r-1 connected to d _r comprises:

The d _r-1,0、d_r-1,1、d_r-1,2、d_r-1,3 is obtained by the following formula:

d_r-1,0＝bin(2*d_r)∧bin(0);

d_r-1,1＝bin2*d_r)∧bin(1);

d_r-1,2＝bin(2*d_r)∧bin(2);

d_r-1,3＝bin(2*d_r)∧bin(3);

Wherein bin is an exclusive or function in binary form that converts an integer into a binary number.

14. The method of claim 12, wherein determining a first routing node and a second routing node in the d _r-1,0、d_r-1,1、d_r-1,2、d_r-1,3 based on the m significant bits comprises;

Reordering d _r-1,0、d_r-1,1、d_r-1,2、d_r-1,3 to obtain d '_r-1,0、d′_r-1,1、d′_r-1,2、d′_r-1,3, wherein the codes of d' _r-1,0、d′_r-1,1、d′_r-1,2、d′_r-1,3 are sequentially increased;

Determining d '_r-1,2 connected to a third downstream port of the d _r as the first routing node and d' _r-1,3 connected to the fourth downstream port as the second routing node, in the case that a significant bit corresponding to the r-th layer encoding of the m significant bits is a non-zero value;

And in the case that the significance bit corresponding to the r layer coding in the m significance bits is zero, determining d '_r-1,0 connected with a first downlink port of d _r as the first routing node, and determining d' _r-1,1 connected with a second downlink port of d _r as the second routing node.

15. The method of claim 12, wherein the sending the target routing request from the d _r to the first routing node or the second routing node according to whether the first routing node and the second routing node are located in a set of target routing nodes corresponding to the target subnetwork comprises:

Determining a second target routing node in the first routing node and the second routing node according to whether the first routing node and the second routing node are positioned in the target routing node set or not;

and sending the target routing request from the d _r to the second target routing node.

16. The method of claim 15, wherein determining a second destination routing node among the first routing node and the second routing node based on whether the first routing node and the second routing node are located in the set of destination routing nodes comprises:

In the case that the first routing node and the second routing node are both positioned in the target routing node set, one routing node is randomly selected from the first routing node and the second routing node to be determined as the second target routing node, or

Under the condition that the first routing node and the second routing node are both positioned in the target routing node set, determining the routing node with the shortest distance from d _r in the first routing node and the second routing node as the second target routing node, or

And under the condition that the first routing node and the second routing node are both positioned in the target routing node set, determining the routing node with the smallest load in the first routing node and the second routing node as the second target routing node.

17. The method of claim 15, wherein determining a second destination routing node among the first routing node and the second routing node based on whether the first routing node and the second routing node are located in the set of destination routing nodes, further comprises:

And determining the node in the target routing node set in the first routing node and the second routing node as the second target routing node under the condition that one routing node in the first routing node and the second routing node is in the target routing node set.

18. The method according to any one of claims 1 to 17, wherein a routing node encoded as d ₀ at layer 0 in the thinned fat tree network structure is connected to four source nodes encoded as s ₀、s₁、s₂、s₃, the relationship between d ₀ and s ₀、s₁、s₂、s₃ being:

s₀＝bin(2*d₀)∧bin(0);

s₁＝bin(2*d₀)∧bin(1);

s₂＝bin(2*d₀)∧bin(2);

s₃＝bin(2*d₀)∧bin(3);

the method comprises the steps of converting an integer into a binary form, wherein a is an exclusive OR function of the binary form according to bits, and the source node is a terminal connected with a routing node in a layer 0 and comprises a source terminal and a target terminal;

the sending, by the target parent node, the target routing request to the target terminal through a routing node in the target subnetwork, including:

The target father node sends the target route request to the target route node through a route node in the target sub-network, wherein the target route node is a node connected with a target terminal;

and the target routing node sends a target routing request to the target terminal through a downlink port connected with the target terminal.

19. An apparatus for transmitting a routing request, comprising:

the acquisition module is used for acquiring codes of a source terminal and a target terminal, wherein the source terminal and the target terminal are source nodes in a thinned fat tree network structure, and the source terminal and the target terminal are in the same sub-network;

The determining module is used for determining a target layer where a nearest public father node is located in the thinned fat tree network structure according to codes of the source terminal and the target terminal, wherein the public father node is a father node common to the source terminal and the target terminal;

and the sending module is used for transmitting the target routing request sent by the source terminal to a target father node on the target layer through the routing nodes in the target sub-network according to the source terminal, the target sub-network where the target terminal is located, and the routing nodes included in a first routing node set and a second routing node set, and transmitting the target routing request downwards to the target terminal through the routing nodes in the target sub-network by the target father node, wherein the target sub-network is a first sub-network or a second sub-network, the first routing node set comprises the routing nodes in the first sub-network, and the second routing node set comprises the routing nodes in the second sub-network.

20. A computer-readable storage medium comprising,

The computer readable storage medium has stored therein a computer program, wherein the computer program when executed by a processor realizes the steps of the method as claimed in any of claims 1 to 18.

21. An electronic device comprising a memory, a processor and a computer program stored on the memory and executable on the processor, characterized in that,

The processor, when executing the computer program, implements the steps of the method as claimed in any one of claims 1 to 18.

22. A computer program product comprising a computer program, characterized in that,

Which computer program, when being executed by a processor, carries out the steps of the method as claimed in any one of claims 1 to 18.