CN103095588B - Based on the adaptive routing method without dead of multiple spanning tree - Google Patents

Abstract

The invention discloses a deadlock-free adaptive routing method based on multiple spanning trees, and relates to the technical field of network communication. The method specifically includes: determining each root node of a multiple spanning tree, and constructing a multiple spanning tree; assigning different source/destination network communication node pairs to different spanning trees, so that different source/destination network communication node pairs pass through different Spanning tree transfers data; breaks resource cycle dependence in communication network topology graph, avoids potential deadlock; uses routing and arbitration unit to replace routing table in router; adopts dynamic buffer allocation strategy for said router. The method of the invention effectively reduces the congestion of root nodes and bubble nodes in each spanning tree, and improves the communication performance of the irregular network. When the network scale increases, the method of the invention has good scalability.

Description

Deadlock-free Adaptive Routing Method Based on Multiple Spanning Trees

technical field

The invention relates to the technical field of network communication, in particular to a deadlock-free adaptive routing method based on multiple spanning trees.

Background technique

The traditional up/down routing method applied to irregular network communication is to build a spanning tree in the network and select only one node as the root node. It is a distributed deadlock-free routing method with certain adaptability in irregular networks. In general, the up/down routing method is to route the communication data between nodes in a spanning tree. The data packet starting from the source node first moves along the spanning tree to the root node, and then moves along the spanning tree to the target node. Usually, we randomly select one of the nodes with the shortest distance from all other nodes as the root node of the spanning tree. In this way, the links between nodes in all network topology graphs can be marked as up or down according to the positional relationship between the nodes they connect and the root node. For example, for two adjacent nodes u and v in the network, if the distance from u to the root node is farther than the distance from v to the root node, then the state of the link (u, v) is up, and vice versa. If u and v have the same distance from the root node, then the direction of the link between them is from the node with the small ID number to the node with the large ID number. For example, if node u has a smaller ID number than node v, then the state of link (u, v) is up. Figure 1(a) shows an irregular network topology with eight nodes, and Figure 1(b) shows the spanning tree in the up/down routing method with node 1 as the root node, and it can be seen that there is no cycle in the figure.

The routing route between the source node and the target node follows the following rules: 0 or more links whose state is up need to be before 0 or more links whose state is down. That is, the packet needs to go through the link whose state is up first and then the link whose state is down. Such a routing route avoids possible resource circular dependencies in packet delivery. That is, the up/down routing method is a deadlock-free routing method. Moreover, in the spanning tree generated by the up/down routing method, there may be multiple routing routes conforming to the rules for different source/destination node pairs, which brings a certain degree of adaptability to the up/down routing method.

The advantage of the up/down routing method lies in the simple router structure and certain adaptability. Its disadvantage is that the routing route between source/destination nodes may not be the shortest route between two nodes, and the physical link close to the root node may become very congested and become the bottleneck of the entire network communication.

The traditional method to avoid deadlock is to divide a physical link into multiple virtual links, so that different data packets can be transmitted in different virtual links of the same physical link. Another method to avoid deadlock is called bubble flow control method. The principle of this method is to limit the injection of data packets that form circular dependencies. In this way, the resources in the rings that may form circular dependencies in the network topology diagram can never be occupied at the same time, so that the data packets in the rings can always continue to move forward to their destination nodes. At the same time, the bubble flow control method is easy to implement. In fact, the present invention uses the bubble flow control method to avoid deadlock.

In the traditional up/down routing method, most data packets are transmitted through the root node of the spanning tree. In this way, the root node may become the bottleneck of network communication in many cases, especially when the scale of the network becomes larger. In most cases, the root node is not the destination node of the data packet, it only plays the role of an intermediate node in the transmission of the data packet.

Contents of the invention

(1) Technical problems to be solved

The invention mainly solves the technical problem that the physical link near the root node of the spanning tree is easily congested in the existing up/down routing method, and improves the flexibility of routing and the scalability of network scale to a large extent.

(2) Technical solution

In order to solve the above problems, the present invention provides a deadlock-free adaptive routing method based on multiple spanning trees, comprising the following steps:

S1. Determine each root node of the multiple spanning tree, and construct the multiple spanning tree;

S2. Assign different source/destination network communication node pairs to different spanning trees, so that different source/destination network communication node pairs transmit data through different spanning trees;

S3. Break the circular dependence of resources in the topology diagram of the communication network to avoid potential deadlocks;

S4. In the router, use the routing and arbitration unit to replace the routing table;

S5. Adopt a dynamic buffer allocation strategy for the router.

Preferably, the step S1 further includes the following steps:

S101. Determine the first root node, so that the average distance for other nodes to communicate through the spanning tree with it as the root node is the shortest, and the first root node is obtained according to the following formula:

$\mathrm{<span\; class="notranslate">\; FR</span>}<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; min</span>}}_{\mathrm{<span\; class="notranslate">\; r</span>}}<span\; class="notranslate">\; \{</span>\underset{\mathrm{<span\; class="notranslate">\; u</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; v</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}{\mathrm{<span\; class="notranslate">\; dist</span>}}_{\mathrm{<span\; class="notranslate">\; r</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; u</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; v</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \}</span><span\; class="notranslate">\; ,</span>$

Among them, dist _r (u, v) represents the distance between u node and v node in the conventional up/down routing method;

S102. Determine the second root node so that the number of nodes involved in the cyclic dependency of the input port buffers of each node in the communication network topology and the sum of the communication distances between all nodes are as small as possible, and the second root node is based on the following The formula yields:

$\mathrm{<span\; class="notranslate">\; SR</span>}<span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; u</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; v</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}\frac{\mathrm{<span\; class="notranslate">\; \&Delta;dist</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; u</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; v</span>}<span\; class="notranslate">\; )</span>}{{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}_{\mathrm{<span\; class="notranslate">\; c</span>}}\mathrm{<span\; class="notranslate">\; size</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; ,</span>$

Among them, size(c) represents the number of nodes in the circular dependency, ∑ _c size(c) represents the total number of all nodes involved in all identified circular dependencies, Σ _{u, v} Δdist(u, v) represents the number of new root nodes The sum of the shortened communication distances between all nodes brought about;

S103. Determine the remaining root nodes according to the following formula:

$\mathrm{<span\; class="notranslate">\; h</span>}<span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; u</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; v</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}\frac{\mathrm{<span\; class="notranslate">\; \&Delta;dist</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; u</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; v</span>}<span\; class="notranslate">\; )</span>}{\mathrm{<span\; class="notranslate">\; \&Delta;T</span>}}<span\; class="notranslate">\; ,</span>$

$\mathrm{<span\; class="notranslate">\; \&Delta;T</span>}<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}_{{\mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; c</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}}\mathrm{<span\; class="notranslate">\; size</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}_{{\mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; c</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}}\mathrm{<span\; class="notranslate">\; size</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ,</span>$

Among them, c ₁ and c ₂ are the sets of nodes involved in the cyclic dependency in the network before and after the establishment of the new spanning tree, and Δdist(u,v) represents the reduced communication distance between each node after the establishment of the new spanning tree.

Preferably, said step S2 further includes the following steps:

S201. Assign a group of source/destination network communication node pairs to a spanning tree with the shortest communication distance therewith;

S202. The network communication node pairs with the same source node and different destination nodes are allocated to different spanning trees in a balanced manner;

S203. When the communication distances of a group of source/destination network communication node pairs in multiple spanning trees are the smallest and equal, assign the group of source/destination network communication node pairs to any spanning tree.

Preferably, said step S3 further includes the following steps:

S301. Find a ring in the communication network topology diagram where resource circular dependency may occur;

S302. Find a restricted port in each ring. When the restricted port satisfies a predetermined rule, the data packet is allowed to pass through it. When the restricted port does not meet the predetermined rule, the data packet is not allowed to pass through it. The predetermined rule is that the next hop port is redundant or equal to two buffer areas;

The input port in a node can be determined as the limit port according to the following benefit measurement formula:

$\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; v</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\underset{{\mathrm{<span\; class="notranslate">\; v</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; C</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}\mathrm{<span\; class="notranslate">\; size</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; C</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ,</span>$

Wherein, the input port i of node v is the limiting port in the circular dependency C, size(C) is the size of the circular dependency C, and the input port with the above-mentioned benefit measurement value is selected as the limiting port;

S303. When the benefit measurement values of the two input ports are equal, select the input port in the node with a small degree as the restricted port;

S304. After selecting each restricted port, the benefit measurement value of each port of each node must be updated, that is, the nodes contained in the broken circular dependency and the cycle measurement values of the input ports in these nodes are all to subtract the size of the circular dependency;

S305. Repeat the above steps until all circular dependencies are broken.

Preferably, said step S4 further includes the following steps:

S401. Divide the data packets passing through a certain port of the router into two types: one type is the data packet with the router as the source node; the other type is the data packet with the router as the intermediate node through the router;

S402. Classify the data packet with the router as the source node according to the specific spanning tree where it is delivered, and the expression of the situation in the routing equation is: the flag bit representing the spanning tree multiplied by the data packet in the spanning tree If the port is a restricted port in the spanning tree, it needs to be multiplied by the restricted port flag;

S403. Divide the data packet with the router as an intermediate node into two types according to the state of the physical link arriving at the router: one of them is the data packet arriving at the router through the physical link whose state is up; the other is Data packets arriving at the router through the physical link in the state of Down;

S404. Classify the data packet that takes the router as an intermediate node and arrives at the router through a physical link in the upper state according to the spanning tree where it is specifically delivered, and the expression of the situation in the routing equation is: a sign representing the spanning tree The bit is multiplied by the sum of the flag bits of each destination node in the spanning tree of the data packet, if the port is a restricted port in the spanning tree, it is also required to be multiplied by the flag bit of the restricted port;

S405. Classify the data packet that takes the router as an intermediate node and arrives at the router through a physical link in the lower state according to the spanning tree where it is specifically delivered, and the expression of the situation in the routing equation is: a sign representing the spanning tree multiplied by the previous hop flag bit and then multiplied by the sum of the flag bits of each destination node in the spanning tree of the data packet, if the port is a restricted port in the spanning tree, it needs to be multiplied by the restricted port flag bit ;

S406. Add the expressions in the above routing equations, multiply the flag bit of the next hop free buffer area, and multiply it by the output port buffer area queue length flag bit to invert.

Preferably, said step S5 further includes the following steps:

S501. Divide the cache area resources into two categories, one is a specific cache area, and the other is a central cache area;

S502. Bind a specific buffer area to a specific input port, so that each input port has a specific buffer area sufficient to hold a data packet;

S503, the central buffer area can be allocated to any input port;

S504. Each buffer area is provided with a flag bit for marking its status, a flag bit for marking whether it is occupied by an application, and a flag bit for marking whether it is already occupied;

S505. Allocate more resources of the central buffer area to the input port connected to the root node and the restricted port.

(3) Beneficial effects

The method of the invention effectively reduces the congestion of root nodes and bubble nodes in each spanning tree, and improves the communication performance of the irregular network. When the network scale increases, the method of the invention has good scalability.

Description of drawings

Figure 1(a) is a schematic diagram of an irregular network with eight network nodes, and (b) is a schematic diagram of a spanning tree in the traditional up/down routing method;

Fig. 2 is a schematic diagram of an irregular network with two spanning trees conforming to the traditional routing method;

Fig. 3 is the flowchart of the inventive method;

Fig. 4 is the routing logic diagram of VCT exchange router;

Figure 5 is a schematic diagram of the circular dependency of resources in an irregular network with multiple spanning trees, where (a) represents an irregular network with only input ports, (b) represents the circular dependency of resources in the network, and (c) represents the resource cycle in the spanning tree 2 _a in 8 is selected as the restricted port, and (d) indicates that 3 _a in spanning tree 1 and 7 _a and 6 _b in spanning tree 8 are selected as restricted ports.

Detailed ways

The specific implementation manners of the present invention will be further described in detail below in conjunction with the accompanying drawings and embodiments. The following examples are used to illustrate the present invention, but are not intended to limit the scope of the present invention.

The present invention proposes a new deadlock-free adaptive routing method based on multiple spanning trees. The core idea of the method is to establish multiple spanning trees for an irregular network, so that data packets between different source/destination nodes are passed on the spanning tree. This technology can evenly distribute data packets on the network to different spanning trees, so that they can be transmitted through their respective root nodes, thereby directly improving the congestion near the root node of a single spanning tree. As shown in Figure 2, we have constructed two spanning trees with nodes 1 and 8 as root nodes in the network.

There cannot be a cycle in the topology graph of a certain spanning tree, but there may be a circular dependency of resources among multiple spanning trees. The present invention adopts a method of selecting a bubble node for each loop existing in the topological graph to avoid the occurrence of potential circular dependencies. The corresponding port of the bubble node is restricted rather than completely prohibited, and the restricted port is only allowed to transmit data packets if it can provide enough buffer area. The invention also proposes a new method for dynamically allocating buffer areas to improve the performance of the entire network and alleviate the congestion of root nodes and bubble nodes in each spanning tree.

Fig. 3 is the flowchart of the method of the present invention, and the present invention provides a kind of non-deadlock self-adaptive routing method based on multiple spanning tree, comprises the following steps:

Step S1: Select each root node of the multiple spanning tree and construct the spanning tree. The selection of the root node of each spanning tree is crucial for all spanning tree based routing methods. Different from the spanning tree root node selection methods used in the previous methods, the present invention needs to use two different heuristic algorithms to select the first root node and the remaining root nodes respectively.

Step S101: The first root node needs to have the characteristic that the average distance through which other nodes communicate is the shortest. Use the formula:

$\mathrm{<span\; class="notranslate">\; FR</span>}<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; min</span>}}_{\mathrm{<span\; class="notranslate">\; r</span>}}<span\; class="notranslate">\; \{</span>\underset{\mathrm{<span\; class="notranslate">\; u</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; v</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}{\mathrm{<span\; class="notranslate">\; dist</span>}}_{\mathrm{<span\; class="notranslate">\; r</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; u</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; v</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \}</span>$

We can get the root node we need. where dist _r (u,v) represents the distance between node u and node v in the traditional up/down routing method.

Step S102: After selecting the first root node, we need to select the second root node. Although the algorithm is based on the same idea, the selection of the second root node and the remaining root nodes are based on different formulas. Because the more nodes involved in network communication that may have resource circular dependencies, the greater the impact on network performance, so when selecting the rest of the root nodes, we should try to make the circular dependencies of the input port buffers of each node in the network topology involved. The sum of the number of nodes and the communication distance between all nodes is the smallest. For the second root node, the selection is made according to the following formula:

$\mathrm{<span\; class="notranslate">\; SR</span>}<span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; u</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; v</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}\frac{\mathrm{<span\; class="notranslate">\; \&Delta;dist</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; u</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; v</span>}<span\; class="notranslate">\; )</span>}{{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}_{\mathrm{<span\; class="notranslate">\; c</span>}}\mathrm{<span\; class="notranslate">\; size</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; ,</span>$

Where size(c) represents the number of nodes in the circular dependency, ∑ _c size(c) represents the total number of nodes involved in all identified circular dependencies, ∑ _{u, v} Δdist(u, v) represents the number of nodes brought by the newly added root node The sum of the shortened communication distances between all nodes coming from .

Step S103: the third node and the fourth node can be selected according to the following formula:

$\mathrm{<span\; class="notranslate">\; h</span>}<span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; u</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; v</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}\frac{\mathrm{<span\; class="notranslate">\; \&Delta;dist</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; u</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; v</span>}<span\; class="notranslate">\; )</span>}{\mathrm{<span\; class="notranslate">\; \&Delta;T</span>}}<span\; class="notranslate">\; ,</span>$

$\mathrm{<span\; class="notranslate">\; \&Delta;T</span>}<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}_{{\mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; c</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}}\mathrm{<span\; class="notranslate">\; size</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}_{{\mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; c</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}}\mathrm{<span\; class="notranslate">\; size</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ,</span>$

Among them, c ₁ and c ₂ are the sets of nodes involved in the cyclic dependency in the network before and after the establishment of the new spanning tree, and Δdist(u,v) represents the reduced communication distance between each node after the establishment of the new spanning tree. It should be noted that when ΔT=0, it needs to be removed from the above formula.

Step S2: In the method proposed by the present invention, a network has multiple spanning trees, so that different source/destination network communication node pairs can transmit data packets through different spanning trees. The advantage of this is that the entire network load can be balanced to transmit data packets, and at the same time, it can avoid the problem that the physical link cannot be fully utilized caused by different spanning trees using different virtual channels to transmit data packets. How to assign different source/destination network node pairs to different spanning trees is crucial to the load balancing of irregular networks.

Step S201: Allocate a group of source/destination network communication node pairs to a spanning tree whose communication distance is the shortest.

Step S202: In order to achieve better load balancing, network communication nodes corresponding to the same source node and different destination nodes should be distributed to different spanning trees in a balanced manner.

Step S203: When the communication distances of a group of source/destination network communication node pairs in multiple spanning trees are the smallest and equal, this group of network communication node pairs can be assigned to any spanning tree. The assignment of provides some flexibility.

Step S3: The deadlock-free adaptive routing method based on multiple spanning trees not only provides shorter communication paths between different nodes, but also effectively improves the adaptability of the entire routing algorithm. However, this algorithm also brings some possible resource cycle dependencies in the network topology graph. These circular dependencies can be broken and potential deadlocks avoided by following these steps:

Step S301: Find a cycle in which resource circular dependency may occur in the network topology graph.

Step S302: Then find some restricted ports in each ring. When these restricted ports meet predetermined requirements, data packets are allowed to pass through them, and when they do not meet predetermined requirements, data packets are not allowed to pass through them. When selecting restricted ports, follow these rules:

1. Each circular dependency contains at least one node with restricted ports;

2. The selection of nodes containing restricted ports is based on the corresponding input ports rather than the entire node;

3. Try to avoid selecting the input port in the root node as the restricted port;

4. The number of restricted ports contained in all nodes in the network cannot exceed a given threshold;

5. Try to choose the input port in the network node with a small degree as the restricted port.

An input port in a node can be selected as a limit port according to the following benefit metering formula:

$\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; v</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\underset{{\mathrm{<span\; class="notranslate">\; v</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; C</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}\mathrm{<span\; class="notranslate">\; size</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; C</span>}<span\; class="notranslate">\; )</span>$

Among them, the input port i of node v is the restricted port in the circular dependency C. size(C) is the size of the circular dependency C. The more nodes involved in circular dependencies, the greater the impact on the performance of the entire network. Therefore, the input port with the above-mentioned large benefit measurement value is preferentially selected as the limiting port.

Step S303: When the benefit measurement values of the two input ports are equal, select the input port of the node with a small degree, because a node with a large degree will be responsible for transmitting more traffic in the network.

Step S304: After each restricted port is selected, the benefit measurement of each port of each node must be updated accordingly, that is, the cycle of the nodes contained in the broken circular dependency and the input ports of these nodes The metered values are all minus the size of the circular dependency.

Step S305: Repeat the above steps until all circular dependencies are broken.

Step S4: In the router, a routing and arbitration unit is used to replace the routing table.

Step S401: Divide the data packets passing through a certain port of the router into two types: one type is the data packet with the router as the source node; the other type is the data packet with the router as the intermediate node through the router;

Step S402: Classify the data packet with the router as the source node according to the spanning tree where it is delivered. The sum of the flag bits of each destination node in , if the port is a restricted port in the spanning tree, it needs to be multiplied by the restricted port flag;

Step S403: divide the data packet with the router as the intermediate node into two types according to the state of the physical link arriving at the router: one type is the data packet arriving at the router through the physical link whose state is up; the other type It is the data packet that arrives at the router through the physical link in the lower state;

Step S404: Classify the data packets that take the router as an intermediate node and arrive at the router through a physical link in the upper state according to the spanning tree where they are delivered. The expression of the situation in the routing equation is: represents the spanning tree The flag bit is multiplied by the sum of the flag bits of each destination node of the data packet in the spanning tree, and if the port is a restricted port in the spanning tree, the flag bit of the restricted port needs to be multiplied;

Step S405: Classify the data packets that take the router as an intermediate node and arrive at the router through the physical link in the state according to the spanning tree where they are delivered. The expression of the situation in the routing equation is: represents the spanning tree The flag bit is multiplied by the last hop flag bit and then multiplied by the sum of the flag bits of each destination node in the spanning tree of the data packet. If the port is a restricted port in the spanning tree, it needs to be multiplied by the restricted port flag bit;

Step S406: Add the expressions in the above routing equations, multiply the flag of the next hop free buffer area, and multiply by the output port buffer queue length flag to invert.

In step S4, a new router structure including k input and output ports is proposed to meet the application requirements of the deadlock-free adaptive routing method based on multiple spanning trees on the network.

The new routing header contains two flag bits used to indicate the spanning tree to which the message belongs, one flag bit used to indicate whether the previous hop is up or down, and a set of flag bits used to indicate the destination address, for example : A network with 16 nodes requires a four-bit flag to represent the destination address.

The new router structure includes:

k*n signals representing the state of the output port. n represents the number of spanning trees, and k represents the number of output ports. For example: S _{i, j} = 1 The i-th output port is up on the j-th spanning tree; otherwise, it is down. These signals are fixed values after all spanning trees have been established.

k signals representing the queue length of each output port. For example: q _i =1 means that the output queue length of the i-th port is at least 1, otherwise the queue is empty.

The k signals represent whether each output port is a limited output port. For example: C _i =1 indicates that the i-th output port and its corresponding physical link are restricted.

2*k represents the number of available buffers for the input port of the next hop node corresponding to each output port. For example: bi _{, 1} , bi _{, 2} = 00, 01, 10, 11 means that the number of available caches for the input port of the next hop node corresponding to the i-th output port is 0, 1, 2, and 3 more.

The routing equation is used to realize the function of the routing table, and the logic used to replace the routing table is very simple.

As shown in Figure 2, the routing equation of port b of node 5 is:

${\mathrm{<span\; class="notranslate">\; R</span>}}_{\mathrm{<span\; class="notranslate">\; b</span>}}<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; b</span>}}_{\mathrm{<span\; class="notranslate">\; 1,1</span>}}<span\; class="notranslate">\; \&Center\; Dot;</span>\stackrel{<span\; class="notranslate">\; \&OverBar;</span>}{{\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}}<span\; class="notranslate">\; \&Center\; Dot;</span>{\mathrm{<span\; class="notranslate">\; C</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; \&Center\; Dot;</span><span\; class="notranslate">\; (</span>\stackrel{<span\; class="notranslate">\; \&OverBar;</span>}{\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; \&Center\; Dot;</span><span\; class="notranslate">\; (</span>\stackrel{<span\; class="notranslate">\; \&OverBar;</span>}{{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}}{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}\stackrel{<span\; class="notranslate">\; \&OverBar;</span>}{{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 3</span>}}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 3</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; \&CenterDot;</span>\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; \&Center\; Dot;</span><span\; class="notranslate">\; (</span>{\stackrel{<span\; class="notranslate">\; \&OverBar;</span>}{{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}}\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}\stackrel{<span\; class="notranslate">\; \&OverBar;</span>}{{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 3</span>}}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 3</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>$

$\stackrel{<span\; class="notranslate">\; \&OverBar;</span>}{\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; \&CenterDot;</span>\stackrel{<span\; class="notranslate">\; \&OverBar;</span>}{{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}}\stackrel{<span\; class="notranslate">\; \&OverBar;</span>}{{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}}{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 3</span>}}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; \&Center\; Dot;</span><span\; class="notranslate">\; (</span>\stackrel{<span\; class="notranslate">\; \&OverBar;</span>}{{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}}{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}\stackrel{<span\; class="notranslate">\; \&OverBar;</span>}{{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 3</span>}}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 3</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span>$

$<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; b</span>}}_{\mathrm{<span\; class="notranslate">\; 1,1</span>}}<span\; class="notranslate">\; \&Center\; Dot;</span>\stackrel{<span\; class="notranslate">\; \&OverBar;</span>}{{\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}}<span\; class="notranslate">\; \&Center\; Dot;</span>{\mathrm{<span\; class="notranslate">\; C</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; \&Center\; Dot;</span><span\; class="notranslate">\; (</span>\stackrel{<span\; class="notranslate">\; \&OverBar;</span>}{{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}}{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}\stackrel{<span\; class="notranslate">\; \&OverBar;</span>}{{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 3</span>}}}<span\; class="notranslate">\; +</span>\stackrel{<span\; class="notranslate">\; \&OverBar;</span>}{\mathrm{<span\; class="notranslate">\; t</span>}}\stackrel{<span\; class="notranslate">\; \&OverBar;</span>}{<span\; class="notranslate">\; \&Center\; Dot;</span>{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}}\stackrel{<span\; class="notranslate">\; \&OverBar;</span>}{{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}}{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 3</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 3</span>}}<span\; class="notranslate">\; )</span>$

q ₂ =1 indicates that the queue length of the output port is at least 1. Represents the data packet passed on the spanning tree 8 with node 5 as the intermediate node, Represents the data packet passed on spanning tree 1 with node 5 as the intermediate node, and Represents data packets with node 5 as the source node on spanning tree 1 and spanning tree 8.

Step S5: In order to make full use of the limited cache to store resources, the present invention proposes a new dynamic cache allocation strategy.

Step S501: Firstly, the cache resources are divided into two categories, one is a specific cache, and the other is a central cache.

Step S502: Bind a specific buffer area to a specific input port, so that each input port has a specific buffer area enough to hold a data packet.

Step S503: The central buffer can be allocated to any input port. An input port can hold as many central buffers as needed and release them after the packet delivery is complete.

Step S504: Each buffer has a flag bit used to mark their status, a flag bit used to mark whether they are occupied by an application, and a flag bit used to mark whether they have been occupied.

Step S505: Allocate more central cache resources to the input ports connected to the root node and the restricted ports, so as to prevent these locations from becoming a bottleneck of network communication.

The present invention realizes above-mentioned non-deadlock self-adaptive routing method based on multiple spanning tree and dynamic cache allocation strategy with Java language, also has traditional up/down routing method, routing method based on Duato principle, multi-layer Routing method, area ordering Label-based routing method. Among them, the routing method based on the Duato principle and the multi-layer routing method need multiple virtual links, so it is necessary to allocate two or more buffer areas for all router ports. The irregular network topology used for testing is randomly generated, and physical links are randomly added between network nodes under the condition that the degree of each node does not exceed 4.

The invention realizes all root node selection situations with three or four spanning trees in the network topology. Table 1 below shows the processor time for selecting the first root node and the average processor time for selecting the remaining root nodes in networks with 16, 32, 64, 128, 256, and 512 nodes.

Table 1

number of nodes 16 32 64 128 256 512 first root node 1.01 1.98 3.90 14.68 248.5 65428 The remaining root nodes (3 spanning trees) 1.02 2.09 4.11 16.79 260.4 66099 The remaining root nodes (4 spanning trees) 1.04 2.15 4.75 16.43 260.0 66048

The performance of different routing algorithms is usually evaluated by two quantities: the delay of delivering a data packet and the maximum load of the entire network. In a network with 32 nodes and 116 physical links. The traditional up/down routing method reaches the saturation point soon after the network load is slightly greater than 0.1. The extended routing method based on Duato's principle reaches the saturation point when the network load is 0.24. The performance of the multi-layer routing method is obviously better than the traditional up/down routing method and the extended routing method based on the Duato principle. When the network load is 0.18, it can accept slightly more traffic than the extended routing method based on the Duato principle. The deadlock-free self-adaptive routing method based on multiple spanning trees proposed by the present invention, no matter whether the dynamic cache area allocation strategy proposed by the present invention is applied or not, its performance is obviously better than the routing method based on area sorting labels in any case.

In a network of 64 network nodes and 232 physical links, the region ordering label-based routing method performed better than the multiple spanning tree-based deadlock-free adaptive routing method, but its performance was significantly worse in all cases A version of dynamic buffer allocation based on a deadlock-free adaptive routing method based on multiple spanning trees.

When the scale of the network increases, the above differences will be more obvious. That is to say, the method proposed by the present invention has better scalability. In a network with 128 network nodes and 464 physical links, it can be found that when the number of spanning trees is 3, the performance of the method of the present invention is the best. The number of optimal spanning trees in a network is affected by the number of network nodes in the network, the number of physical links and the number of buffer areas for each input port.

The specific router implementation method of the deadlock-free adaptive routing method based on multiple spanning trees will be described in detail below. Assume that the router has k input or output ports based on VCT switching. As shown in FIG. 4 , the routing header of the data packet contains two identification bits t ₁ t ₂ used to identify which spanning tree the data packet is transmitted on. A set of identification bits used to identify the destination node, for example, a network with 16 nodes requires 4 identification bits d ₁ d ₂ d ₃ d ₄ to represent the destination node. A flag s used to identify the last state, when s=1, indicates that the previous jump is down, and vice versa, the previous jump is up.

The identification bits s _1,1 , s _1,2 , s _2,1 , s _2,2 , . . . , s _k,1 , s _k,2 are used to identify the state of the output link. s _i,j = 1 means that the state of the i-th output link of the j-th spanning tree is up, otherwise it is down. After the spanning tree in the network is established, the values of the identification bits s ₁ , 1, s ₁ , 2, s ₂ , 1, s 2, ₂ , ..., s _{k, 1} , s _{k, 2} are fixed up. The selection of output links in the whole routing process must follow the rules of the up/down routing algorithm. That is to say, when the state of the previous hop is up, all output links are candidate links, and when the state of the previous hop is down, only the output link whose state is down can be selected.

The identification bits q ₁ , q ₂ ,...,q _k also identify the state of the buffer queue corresponding to the output link, and when q _i =1, it means that the length of the buffer queue corresponding to the i-th output link is at least 1 , otherwise the queue is empty. Here, k identification bits C ₁ , C ₂ , . . . , C _k are used to identify whether the k output ports in the router are restricted ports. When C _i =1, the state of the i-th port of the router and the physical link connected to it is a restricted state. When the state of a physical link is limited, the data packet can only be selected for transmission when the number of free buffer areas of the next-hop port connected to it is greater than or equal to 2. The identification bits b ₁ and b ₂ are used to indicate the number of free buffer areas of the corresponding next-hop input port of the output port. When the values of b ₁ and b ₂ are 00, 01, 10 and 11 respectively, it indicates the next-hop input port The number of free buffers is 0,1,2,3.

The entire routing logic part is not complicated, we use the routing and arbitration unit to realize the function of the routing table. The logic to implement the routing table function is very simple. As shown in FIG. 5 , the data packets with node 5 as the source node can be evenly distributed to the two spanning trees. The specific allocation method is as follows: 5→1(8) (the data packet is transmitted on spanning tree 8 with 5 as the source node), 5→6(8), 5→2(8), 5→3(1), 5→4(1), 5→8(1), 5→7(1). In our network, only the data packets whose destination nodes are 3, 2, and 8 may pass through port b of node 5. Packets 5→3 and 5→8 passed in spanning tree 1 go through the restricted link.

Now consider the packet with node 5 as the transit node. The data packet arriving at node 5 through the physical link whose state is up can be delivered to nodes 3, 8, 2; the data packet arriving at node 5 through the physical link whose state is down can be delivered to node 3 and node 8. In this way, the routing equation of port b of node 5 is:

${\mathrm{<span\; class="notranslate">\; R</span>}}_{\mathrm{<span\; class="notranslate">\; b</span>}}<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; b</span>}}_{\mathrm{<span\; class="notranslate">\; 1,1</span>}}<span\; class="notranslate">\; \&CenterDot;</span>\stackrel{<span\; class="notranslate">\; \&OverBar;</span>}{{\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}}<span\; class="notranslate">\; \&Center\; Dot;</span>{\mathrm{<span\; class="notranslate">\; C</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; \&CenterDot;</span><span\; class="notranslate">\; (</span>\stackrel{<span\; class="notranslate">\; \&OverBar;</span>}{\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; \&Center\; Dot;</span><span\; class="notranslate">\; (</span>\stackrel{<span\; class="notranslate">\; \&OverBar;</span>}{{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}}{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}\stackrel{<span\; class="notranslate">\; \&OverBar;</span>}{{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 3</span>}}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 3</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; \&Center\; Dot;</span>\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; \&Center\; Dot;</span><span\; class="notranslate">\; (</span>{\stackrel{<span\; class="notranslate">\; \&OverBar;</span>}{{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}}\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}\stackrel{<span\; class="notranslate">\; \&OverBar;</span>}{{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 3</span>}}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 3</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; +</span>$

$\stackrel{<span\; class="notranslate">\; \&OverBar;</span>}{\mathrm{<span\; class="notranslate">\; t</span>}}<span\; class="notranslate">\; \&Center\; Dot;</span>\stackrel{<span\; class="notranslate">\; \&OverBar;</span>}{{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}}\stackrel{<span\; class="notranslate">\; \&OverBar;</span>}{{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}}{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 3</span>}}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; \&Center\; Dot;</span><span\; class="notranslate">\; (</span>\stackrel{<span\; class="notranslate">\; \&OverBar;</span>}{{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}}{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}\stackrel{<span\; class="notranslate">\; \&OverBar;</span>}{{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 3</span>}}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 3</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; )</span>$

$<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; b</span>}}_{\mathrm{<span\; class="notranslate">\; 1,1</span>}}<span\; class="notranslate">\; \&Center\; Dot;</span>\stackrel{<span\; class="notranslate">\; \&OverBar;</span>}{{\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}}<span\; class="notranslate">\; \&CenterDot;</span>{\mathrm{<span\; class="notranslate">\; C</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; \&CenterDot;</span><span\; class="notranslate">\; (</span>\stackrel{<span\; class="notranslate">\; \&OverBar;</span>}{{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}}{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}\stackrel{<span\; class="notranslate">\; \&OverBar;</span>}{{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 3</span>}}}<span\; class="notranslate">\; +</span>\stackrel{<span\; class="notranslate">\; \&OverBar;</span>}{\mathrm{<span\; class="notranslate">\; t</span>}}\stackrel{<span\; class="notranslate">\; \&OverBar;</span>}{<span\; class="notranslate">\; \&CenterDot;</span>{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}}\stackrel{<span\; class="notranslate">\; \&OverBar;</span>}{{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}}{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 3</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}{\mathrm{<span\; class="notranslate">\; d</span>}}_{\mathrm{<span\; class="notranslate">\; 3</span>}}<span\; class="notranslate">\; )</span>$

q ₂ =1 means that the queue length of the output port is at least 1, Represents the data packet passed on the spanning tree 8 with node 5 as the intermediate node, Represents the data packet passed on spanning tree 1 with node 5 as the intermediate node, and Represents data packets with node 5 as the source node on spanning tree 1 and spanning tree 8.

Among the multiple candidate ports provided by the routing unit, it is generally preferred to select an unrestricted port, so that the next-hop port has more buffers. When there are two ports whose status is unrestricted, the one with the smaller degree of the node where the port is located is usually selected. Because choosing a node with a smaller degree tends to bring less network congestion. When the number of candidate ports is still more than 1, one of them is randomly selected, so the selection logic of the present invention is also very simple.

The above is only a preferred embodiment of the present invention, it should be pointed out that for those of ordinary skill in the art, without departing from the technical principle of the present invention, some improvements and replacements can also be made, these improvements and replacements It should also be regarded as the protection scope of the present invention.

Claims (2)

1. A deadlock-free adaptive routing method based on multiple spanning trees, characterized in that, comprising the following steps: S1. Determine each root node of the multiple spanning tree, and construct the multiple spanning tree; S2. Assign different source/destination network communication node pairs to different spanning trees, so that different source/destination network communication node pairs transmit data through different spanning trees; S3. Break the circular dependence of resources in the topology diagram of the communication network to avoid potential deadlocks; S4. In the router, use the routing and arbitration unit to replace the routing table; S5. Adopting a dynamic buffer allocation strategy for the router; Said step S1 further comprises the following steps: S101. Determine the first root node, so that the average distance for other nodes to communicate through the spanning tree with it as the root node is the shortest, and the first root node is obtained according to the following formula: $\mathrm{<span\; class="notranslate">\; FR</span>}<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; min</span>}}_{\mathrm{<span\; class="notranslate">\; r</span>}}<span\; class="notranslate">\; \{</span>\underset{\mathrm{<span\; class="notranslate">\; u</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; v</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}{\mathrm{<span\; class="notranslate">\; dist</span>}}_{\mathrm{<span\; class="notranslate">\; r</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; u</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; v</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \}</span><span\; class="notranslate">\; ,</span>$ Among them, dist _r (u, v) represents the distance between u node and v node in the conventional up/down routing method; S102. Determine the second root node so that the number of nodes involved in the cyclic dependency of the input port buffer of each node in the communication network topology and the sum of the communication distances between all nodes are as small as possible, and the second root node is based on the following The formula yields: $\mathrm{<span\; class="notranslate">\; SR</span>}<span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; u</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; v</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}\frac{\mathrm{<span\; class="notranslate">\; \&Delta;dist</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; u</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; v</span>}<span\; class="notranslate">\; )</span>}{{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}_{\mathrm{<span\; class="notranslate">\; c</span>}}\mathrm{<span\; class="notranslate">\; size</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; ,</span>$ Among them, size(c) indicates the number of nodes in the circular dependency, ∑ _c size(c) indicates the total number of all nodes involved in all identified circular dependencies, ∑ _u,v Δdist(u,v) indicates the number of new root nodes The sum of the shortened communication distances between all nodes brought about; S103. Determine the remaining root nodes according to the following formula: $\mathrm{<span\; class="notranslate">\; h</span>}<span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; u</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; v</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}\frac{\mathrm{<span\; class="notranslate">\; \&Delta;dist</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; u</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; v</span>}<span\; class="notranslate">\; )</span>}{\mathrm{<span\; class="notranslate">\; \&Delta;T</span>}}<span\; class="notranslate">\; ,</span>$ $\mathrm{<span\; class="notranslate">\; \&Delta;T</span>}<span\; class="notranslate">\; =</span>{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}_{{\mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; c</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}}\mathrm{<span\; class="notranslate">\; size</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}_{\mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; \&Element;</span>{\mathrm{<span\; class="notranslate">\; c</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}}\mathrm{<span\; class="notranslate">\; size</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; c</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ,</span>$ Among them, c ₁ and c ₂ are the node sets involved in the cyclic dependency in the network before and after the establishment of the new spanning tree, and Δdist(u,v) represents the communication distance reduced between each node after the establishment of the new spanning tree; Said step S3 further comprises the following steps: S301. Find a ring in the communication network topology diagram where resource circular dependency may occur; S302. Find a restricted port in each ring. When the restricted port satisfies a predetermined rule, the data packet is allowed to pass through it. When the restricted port does not meet the predetermined rule, the data packet is not allowed to pass through it. The predetermined rule is that the next hop port is redundant or equal to two buffer areas; The input port in a node can be determined as the limit port according to the following benefit measurement formula: $\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; v</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\underset{{\mathrm{<span\; class="notranslate">\; v</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; C</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}\mathrm{<span\; class="notranslate">\; size</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; C</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ,</span>$ Wherein, the input port i of node v is the limiting port in the circular dependency C, size(C) is the size of the circular dependency C, and the input port with the above-mentioned benefit measurement value is selected as the limiting port; S303. When the benefit measurement values of the two input ports are equal, select the input port in the node with a small degree as the restricted port; S304. After each restricted port is selected, the benefit measurement value of each port of each node must be updated, that is, the nodes contained in the broken circular dependency and the cycle measurement values of the input ports in these nodes are all to subtract the size of the circular dependency; S305. Repeat the above steps until all circular dependencies are broken; Said step S4 further comprises the following steps: S401. Divide the data packets passing through a certain port of the router into two types: one type is the data packet with the router as the source node; the other type is the data packet with the router as the intermediate node through the router; S402. Classify the data packet with the router as the source node according to the spanning tree where it is specifically delivered, and classify the data packet with the router as the source node according to the spanning tree where it is specifically delivered, expressed in the routing equation as: : Indicates that the flag bit of the spanning tree is multiplied by the sum of the flag bits of each destination node of the data packet in the spanning tree, if the data packet with the router as the source node passes through the output port of the router, the spanning tree If the port is restricted, it needs to be multiplied by the flag bit of the restricted port; S403. Divide the data packet with the router as an intermediate node into two types according to the state of the physical link arriving at the router: one of them is the data packet arriving at the router through the physical link whose state is up; the other is Data packets arriving at the router through the physical link in the state of Down; S404. Classify the data packets that arrive at the router with the router as the intermediate node and through the physical link whose state is up according to the spanning tree where it is delivered, and classify the data packets that use the router as the intermediate node and pass through the physical link whose state is up The data packet arriving at the router is expressed in the routing equation according to the classification of the spanning tree where it is specifically delivered: the flag bit representing the spanning tree multiplied by the flag bit of each destination node of the data packet in the spanning tree And, if the data packet that takes the router as an intermediate node and arrives at the router through a physical link in the state is a restricted port in the spanning tree through the output port of the router, then it needs to be multiplied by the restricted port flag; S405. Classify the data packets that arrive at the router with the router as the intermediate node and through the physical link in the lower state according to the spanning tree where the specific delivery is located, and classify the data packets that use the router as the intermediate node and pass through the physical link in the lower state The data packet arriving at the router is expressed in the routing equation according to the classification of the spanning tree where it is specifically delivered: the flag bit representing the spanning tree is multiplied by the last hop flag bit and then multiplied by the data packet in the spanning tree. The sum of the flag bits of each destination node, if the data packet that takes the router as an intermediate node and reaches the router through the physical link in the lower state passes through the output port of the router and is a restricted port in the spanning tree, it needs to be multiplied by to limit the port flag; S406. Add the expressions in the above-mentioned routing equations, multiply the flag bit of the next hop free buffer area, and multiply by the output port buffer area queue length flag bit to invert; Said step S5 further comprises the following steps: S501. Divide the cache area resources into two categories, one is a specific cache area, and the other is a central cache area; S502. Bind a specific buffer area to a specific input port, so that each input port has a specific buffer area sufficient to hold a data packet; S503, the central buffer area can be allocated to any input port; S504. Each buffer area is provided with a flag bit for marking its status, a flag bit for marking whether it is occupied by an application, and a flag bit for marking whether it is already occupied; S505. Allocate more resources of the central buffer area to the input port connected to the root node and the restricted port. 2. The method according to claim 1, wherein said step S2 further comprises the following steps: S201. Assign a group of source/destination network communication node pairs to a spanning tree with the shortest communication distance therewith; S202. The network communication node pairs with the same source node and different destination nodes are allocated to different spanning trees in a balanced manner; S203. When the communication distances of a group of source/destination network communication node pairs in multiple spanning trees are the smallest and equal, assign the group of source/destination network communication node pairs to any spanning tree.