CN108123878A - A kind of method for routing, device and data transfer equipment - Google Patents

Abstract

The present invention, which provides a kind of method for routing, device and data transfer equipment, this method, to be included：Data transfer equipment obtains data packet；Data transfer equipment determines the next-hop exit port of the data packet whether is matched in default routing table；Wherein, the exit port in default routing table is the exit port of not congestion；If the next-hop exit port of the data packet is not matched in default routing table, data transfer equipment determines next-hop exit port of the first port as the data packet to purpose data transfer equipment in other ports in addition to the congestion exit port to the purpose data transfer equipment of the data packet recorded in congestion information table of data transfer equipment；Data transfer equipment sends the data packet by first port.A kind of strong method for routing of autgmentability, the network suitable for multi-layer clos frameworks can be provided by this method.

Description

A routing method, device and data forwarding device

technical field

The present invention relates to the technical field of communications, in particular to a routing method, device and data forwarding equipment.

Background technique

With the development of network technology, the data center has become the infrastructure for providing Internet services, distributed parallel computing, etc. Designing scalable network architecture and efficient routing algorithms for data centers is a research hotspot in the current academic circles. The industry generally adopts the clos (clos) architecture to build data centers. With the rapid development of services such as web applications, big data analysis, and cloud computing, the demand for switching network capacity of data centers is also increasing. The two-level clos architecture based on leaf-spine is far from meeting the capacity requirements of the business. In the future, more clos architectures will be needed to build large-scale data centers.

The quality of the load balancing effect in the data center will directly affect the user experience. A distributed processing scheme is proposed in the prior art to perform load scheduling on the data center traffic, which specifically includes: when the data message is sent from the source node to the destination In the process of the node, the selected path identifier and the congestion measurement value of each link in the path are encapsulated in a data message and sent to the destination node together. When a message needs to be sent from the destination node to the source node, the path identifier and the congestion situation corresponding to the path are encapsulated in a data message to inform the source node. In this way, the source node can know which of the different paths to the destination node is the least congested. When there is a data message to be sent to the destination node, the least congested path is preferred for sending the data message.

In the above routing scheme, with the expansion of the clos level, the number of end-to-end paths increases exponentially, and the scale of entries required by the scheme also increases exponentially. For example, the number of entries required by the three-level clos architecture is 100. Existing switches cannot support such a large number of entries. In addition, because the end-to-end paths increase exponentially, the time required to maintain real-time congestion information of all end-to-end paths on the switch also increases exponentially. Under the two-level clos architecture based on leaf-spine, the number of end-to-end paths is 24, and the time required to obtain the congestion information of all end-to-end paths is acceptable. However, the number of end-to-end paths under the 3-level clos architecture is 576, and the number of end-to-end paths under the 4-level clos architecture is as high as 13824. It will take a long time to obtain real-time congestion information on all paths for traffic scheduling. Therefore, the above routing scheme is less effective in a multi-level clos architecture, that is, the above routing scheme has poor scalability.

Contents of the invention

Embodiments of the present invention provide a routing method, device, and data forwarding device to solve the technical problem of poor scalability of routing methods in the prior art.

In a first aspect, an embodiment of the present invention provides a routing method, and the method is described from the perspective of each data forwarding device on a data packet transmission path. In this method, the data forwarding device obtains the data packet. For example, if it is a source data forwarding device, it can generate a data packet; if it is a non-source data forwarding device, it can receive a data packet from an upper layer data forwarding device. Then the data forwarding device determines whether the next hop egress port of the data packet is matched in the preset routing table; wherein, the egress ports in the preset routing table are all uncongested egress ports. If the next hop exit port of the data packet is not matched in the preset routing table, the destination data of the data packet recorded by the data forwarding device in the congestion removal information table of the data forwarding device Among the ports other than the congested egress port of the forwarding device, the first port is determined as the next hop egress port of the data packet to the destination data forwarding device. Then the data forwarding device sends the data packet through the first port. In the embodiment of the present invention, on the one hand, the ports that record congestion are in the congestion information table, so the number of entries required is relatively small; One of them is used as the next hop output port, that is, the data forwarding device selects an available next hop for the data packet hop by hop, instead of selecting an end-to-end optimal path like the method in the prior art, so there is no need to wait for feedback from all end points The usage of the end-to-end path, so there is no need to wait for a long time. To sum up, the routing method in the embodiment of the present invention has strong scalability and is suitable for a network with a multi-level clos architecture.

In a possible design, the data forwarding device further determines the congested port to each destination data forwarding device among all the ports of the data forwarding device; The port numbers of the congested ports of each destination data forwarding device are recorded in the congestion information table. In the embodiment of the present invention, each data forwarding device establishes and maintains the congestion information table, so it is more convenient and easy to implement.

In a possible design, described from the perspective of a non-source data forwarding device, the method further includes: the data forwarding device determines whether all ports from the data forwarding device to each destination data forwarding device are in a congested state; If all ports from the data forwarding device to the first destination data forwarding device among the respective destination data forwarding devices are in a congested state, the data forwarding device sends first notification information to the upper-layer data forwarding device, and the first A notification message is used to notify the upper-layer data forwarding device that the data forwarding device cannot serve as the next hop for the upper-layer data forwarding device to reach the first destination data forwarding device; All ports of the second destination data forwarding device in the destination data forwarding device are not in a congested state, then the data forwarding device sends second notification information to the upper layer data forwarding device, and the second notification information is used to notify the upper layer A data forwarding device, where the data forwarding device can serve as a next hop for the upper layer data forwarding device to reach the second destination data forwarding device. Through this method, the upper-layer data forwarding device can be notified of its own congestion status, so that the upper-layer data forwarding device can determine the congested port.

In a possible design, the description is made from the perspective of the non-purpose data forwarding device and the upper-layer data forwarding device of the non-purpose data forwarding device. The data forwarding device determines that each destination data The congested port of the forwarding device includes: the data forwarding device receiving third notification information sent by each lower-layer data forwarding device connected to the port of the data forwarding device; A data forwarding device on the path of each destination data forwarding device; the third notification information is used to indicate whether each lower layer data forwarding device can serve as a next hop for the data forwarding device to reach each destination data forwarding device; The data forwarding device determines a congested port to each destination data forwarding device among all ports of the data forwarding device according to the third notification information. Through this method, the data forwarding device can know the congestion situation from the lower layer data forwarding device to the destination data forwarding device, and then can determine its own unavailable next-hop egress port, and can know the congestion points of the unavailable next-hop egress port.

In combination with any of the above possible designs, the method further includes: if the uncongested egress port of the data forwarding device changes to a congested egress port, the data forwarding device also determines the preset routing table whether the congested outport is included in the preset routing table; if the preset routing table includes the congested outport, the data forwarding device will include the entry of the congested outport from the preset routing table delete. Through this method, the preset routing table can be updated according to the congestion state of the port, so that the outgoing port in the preset routing table is always an available next-hop outgoing port.

In combination with any of the above possible designs, after the first port is determined as the next hop port for the data packet to the destination forwarding device, the method further includes: the data forwarding device Create a new entry in the preset routing table for the data flow corresponding to the data packet, and the outgoing port of the new entry is the first port. Through this method, subsequent data packets of the data flow can be sent according to the first port, saving data packet forwarding time.

In a second aspect, an embodiment of the present invention provides a data forwarding device. The data forwarding device includes: at least two ports, a transmitter, a receiver and a processor. The sender can be used to execute the sending step in the routing method in the aforementioned first aspect. The receiver may perform the receiving or obtaining step in the routing method in the aforementioned first aspect. The processor may execute the steps of establishing, deleting, recording or determining in the routing method in the aforementioned first aspect.

In a third aspect, an embodiment of the present invention provides a routing device, where the routing device includes a functional module for implementing the method described in the first aspect.

In a fourth aspect, an embodiment of the present invention further provides a computer storage medium, where program code is stored on the computer storage medium, and the program code includes instructions for realizing any possible implementation of the method in the first aspect. .

Description of drawings

Figure 1a is a structural diagram of a switching network provided by an embodiment of the present invention;

1b-1c are structural diagrams of a data center provided by an embodiment of the present invention;

FIG. 2 is a structural diagram of a data forwarding device provided by an embodiment of the present invention;

FIG. 3 is a flowchart of a routing method provided by an embodiment of the present invention;

Fig. 4 is a functional block diagram of a routing device provided by an embodiment of the present invention.

Detailed ways

Embodiments of the present invention provide a routing method, device, and data forwarding device to solve the technical problem of poor scalability of routing methods in the prior art.

The term "and/or" in this article is just an association relationship describing associated objects, which means that there can be three relationships, for example, A and/or B can mean: A exists alone, A and B exist simultaneously, and there exists alone B these three situations. In addition, the character "/" in this article generally indicates that the contextual objects are an "or" relationship.

The implementation process and purpose of the solutions in the embodiments of the present invention will be described in detail below in conjunction with the accompanying drawings.

A routing method provided by an embodiment of the present invention can be applied to a data center with an m-level clos architecture, where m is an integer greater than or equal to 2. The method can also be applied to a switched network as shown in Fig. 1a.

In the method, the data forwarding device detects the congestion state of the port on the structure of the existing data center and the switching network, and when the link corresponding to the port is congested, the port is deleted from the available next hop to the destination data forwarding device. After deletion, if the available next hop to the destination data forwarding device is 0, the data forwarding device notifies all upper layer data forwarding devices that they cannot reach the destination data switching device through itself. The upper-layer data forwarding device updates its own available next-hop entry corresponding to the destination data forwarding device. During traffic scheduling, the data forwarding device selects an available next hop for data packets hop by hop based on the real-time feedback of congestion information. Therefore, the method is highly scalable and suitable for networks with multi-level clos architectures.

Specifically, in the switching network shown in FIG. 1 a , multiple paths from the source switch to the destination switch are simply shown, and the switches on the paths are called intermediate switches, such as intermediate switches 1 to 4 . It should be understood that, in practice, the switching network may include more paths, and the number of intermediate switches on each path may also be greater.

Specifically, please refer to FIG. 1 b , which is a network structure diagram of a data center with a three-level clos architecture provided by an embodiment of the present invention. In this embodiment, the 3-level clos architecture takes a 3-element fat-tree topology as an example. The network structure is divided into three layers from top to bottom. The three layers from top to bottom are the core layer, aggregation layer, and edge layer. The switches at the core layer are called core switches, the switches at the aggregation layer are called aggregation switches, and the switches at the edge layer are called edge switches. Hosts or servers are directly connected to edge switches. In practical application, the devices distributed in the three layers may be other devices for data forwarding, such as routers, which are collectively referred to as data forwarding devices herein for ease of description.

It should be noted that in clos architectures with different topologies or in different scenarios, the names of data forwarding devices at all levels will be slightly different. For example, an edge switch in a two-level leaf-spine clos architecture can also be called a leaf switch. A core switch in a 2-level leaf-spine clos architecture can also be called a spine switch. For another example, an edge switch may be called an access switch functionally. In terms of the structure of the switch, the edge switch may also be referred to as an on-rack (English: Top-of-Rack, TOR for short) switch. For ease of description, they are collectively referred to as data forwarding devices in this document.

Please continue to refer to Figure 1b, the n-element fat tree network includes 2n performance optimization data centers (English: Performance optimization datacenter, Pod for short), and each data forwarding device has 2n ports. Therefore, in this embodiment, the network structure of the data center where n is 3 includes 6 Pods, the number of edge switches and aggregation switches in each Pod is 3, and the core switches have 3 core groups, which are core groups 0 to core group 2. Each core group has 3 core switches. The number of hosts or servers connected to each Pod is n ² , that is, 9, and the total number of hosts that the network can support is (2n) ³ /4, that is, 54. Each switch has 6 ports. The 6 ports of 1 aggregation switch in each Pod are connected to 3 core switches in 1 core group, and are connected to 3 edge switches in the same Pod, and the core groups connected to each aggregation switch are different. The 6 ports of each edge switch are respectively connected to 3 aggregation switches and 3 hosts in the same Pod. For example, as shown in FIG. 1b, aggregation switch 0 in Pod0 is connected to three core switches in core group 0, and is connected to three edge switches in Pod0. Aggregation switch 1 in Pod0 is connected to the three core switches in core group 1 and connected to the three edge switches in Pod0. Aggregation switch 2 in Pod0 is connected to the three core switches in core group 2 and connected to the three edge switches in Pod0. The connections of the switches in other Pods are similar, and will not be repeated here.

In FIG. 1b , Pod0 to Pod6 represent the numbers of the Pods. In practical applications, different Pods can also be identified by other identifiers. The numbers 0 to 2 of the switches at the core layer are used to uniquely identify the core switches in the same core group. Similarly, the numbers 0 to 2 of the switches at the aggregation layer are used to uniquely identify the aggregation switches in the same Pod, and the numbers of the switches at the edge layer 0 to 2 are used to uniquely identify the edge switch in the same Pod. In practice, other identifiers can also be used to identify the aggregation switch or the edge switch in the same Pod.

Please refer to Figure 1c again, which is another presentation of the 3-level clos architecture in Figure 1b. In this embodiment, the value of n is 3, and each access switch has 2n ports. The number is 2n ² , which are the access switch 1 to the access switch n+1, and then to the access switch 2n ² . The aggregation switch and the core switch form a layer, and there are n layers in total, namely layer 1 to layer n. Each level includes 2n aggregation switches, which are respectively aggregation switch 1 to aggregation switch 2n. Each aggregation switch has 2n ports. The n ports of each convergence switch are respectively connected to n core switches included in each layer, and the n core switches are respectively core switch 1 to core switch n. The other n ports of each convergence switch are connected to n access switches. Each core switch has 2n ports. Each aggregation switch is connected to each core switch respectively. The n ports of each access switch are connected to an aggregation switch of n layers. The other n ports of each access switch can be connected to hosts or servers. The number of hosts or servers that can be connected to 2n ² access switches is 2n ³ . Corresponding to the structure in Figure 1b, core switch 0 to core switch 2 in core group 0 and aggregation switch 0 in each Pod form the first layer, and core switch 0 to core switch 2 in core group 1 and aggregation switch 1 in each Pod The second layer is formed, and the core switch 1 to core switch 2 of the core group 2 and the aggregation switch 2 in each Pod form the third layer.

Some technical terms in this article are described in the embodiments of the present invention by taking the terms in the existing data center network structure as examples, which may change with the evolution of the network, and the specific evolution can refer to the description in the corresponding standards.

Please refer to FIG. 2 next. FIG. 2 is a possible structural diagram of a data forwarding device provided by an embodiment of the present invention. The data forwarding device is, for example, the aforementioned edge switch, access switch, convergence switch, and core switch. As shown in FIG. 2 , the data forwarding device includes: a processor 10 , a transmitter 20 , a receiver 30 , a memory 40 and a port 50 . The memory 40, the transmitter 20 and the receiver 30, and the processor 10 may be connected via a bus. Of course, in practical applications, the memory 40, the transmitter 20, the receiver 30, and the processor 10 may not have a bus structure, but may be other structures, such as a star structure, which is not specifically limited in this application.

Optionally, the processor 10 may specifically be a central processing unit, an application-specific integrated circuit (English: Application Specific Integrated Circuit, ASIC for short), may be one or more integrated circuits for controlling program execution, and may be an on-site A hardware circuit developed by a programmable gate array (English: Field Programmable Gate Array, FPGA for short) may be a baseband processor.

Optionally, the processor 10 may include at least one processing core.

Optionally, the memory 40 may include a read-only memory (English: Read Only Memory, ROM for short), a random access memory (English: Random Access Memory, RAM for short), and a disk storage. The memory 40 is used to store data required by the processor 10 during operation. The number of memory 40 is one or more.

Optionally, the number of ports 50 is one or more, and is used for connecting with the upper-layer or lower-layer data forwarding device. If the data forwarding device is a data forwarding device connected to a host or a server, such as the above-mentioned access switch or edge switch, port 50 is also used to connect to the host or server.

Optionally, the transmitter 20 and the receiver 30 may be physically independent from each other or integrated together. The transmitter 20 can send data to adjacent data forwarding devices through the port 50 . The receiver 30 can receive data sent by an adjacent data forwarding device through the port 50 .

Next, please refer to FIG. 3 , which is a flowchart of the routing method in the embodiment of the present invention. As shown in Figure 3, the method includes:

Step 101: the data forwarding device obtains the data packet;

Step 102: The data forwarding device determines whether the next-hop egress port of the data packet is matched in the preset routing table; wherein, the egress ports in the preset routing table are all uncongested egress ports;

Step 103: If the next hop port of the data packet is not matched in the preset routing table, the data forwarding device forwards the destination data of the data packet recorded in the congestion removal information table of the data forwarding device Among the ports other than the congested egress port of the device, the first port is determined as the next hop egress port of the data packet to the destination data forwarding device;

Step 104: The data forwarding device sends the data packet through the first port.

It should be noted that in the embodiment of the present invention, congestion and non-congestion are relative terms, and the situation of congestion and non-congestion can be set by the user according to actual needs, and the congestion standards of different network structures can also be different , which can be set according to the actual situation. The judgment thresholds or standards about congestion and non-congestion herein are just examples, and are not intended to limit the present invention.

In step 101, the data forwarding device may obtain the data packet in but not limited to the following two ways, one is to generate the data packet by itself, and the other is to receive the data packet from the upper layer device. For example, when the data forwarding device is the source data forwarding device, the data packet may be generated by the data forwarding device. If the data forwarding device is a non-source data forwarding device, the data forwarding device may receive data packets from the upper layer data forwarding device.

No matter which method is used to obtain the data packet, after the data packet is obtained, step 102 is executed next, that is, the data forwarding device determines whether the next hop egress port of the data packet is matched in the preset routing table. Wherein, the outgoing ports in the preset routing table are non-congested outgoing ports, that is, available outgoing ports.

Optionally, real-time updating can be used to ensure that when step 102 is performed in the preset routing table, all outgoing ports in the preset routing table are uncongested outgoing ports, which will be described in detail later.

Optionally, the preset routing table may be a routing table established by a method in the prior art, or the routing table may be updated by using a method in the prior art. For example, the entry included in the preset routing table includes two fields, the first field is the hash (hash) value of the five-tuple of the data packet, and the second field is the next-hop outgoing port number. Wherein, the quintuple of the data packet may include a source network protocol (English: Internet Protocol, IP for short) address, a source port number, a destination IP address, a destination port number, and a transport layer protocol. By hashing the five-tuple, the hash value of the five-tuple can be obtained.

Optionally, the quintuples of all data packets in each data flow are the same, so the next-hop egress port in the preset routing entry is for each data flow. Therefore, the data packets of the same data flow will be matched to the same next-hop egress port.

The above description is based on data flow scheduling, so the routing table is based on data flow routing table, but in practice, it can also be based on flow cluster (flowlet) scheduling, correspondingly, the default routing table can be flowlet routing table , the flowlets are divided by a minimum time interval. The time interval between adjacent data packets in a flowlet is smaller than the minimum time interval. As long as the minimum time interval is greater than the maximum delay difference of the equal-cost multipath, multiple flowlets can be scheduled to different Paths go up without being out of order. The flowlet forwarding mechanism is well known to those skilled in the art, and will not be repeated here.

For example, in step 102, the data forwarding device can calculate the hash value of the five-tuple of the data packet, and then use the hash value to match in the preset routing table, and then determine whether the match is successful, if the match is successful , then the next-hop egress port corresponding to the hash value of the successfully matched quintuple is the next-hop egress port of the data packet; the data forwarding device can send the data packet through the matched next-hop egress port. If the next hop egress port of the data packet is not successfully matched in the preset routing table, the data forwarding device executes step 103 .

It should be noted that, in the determination process in step 102, the matching content is different according to the matching field in the entry of the preset routing table. For example, if the first field included in the entry of the preset routing table is the flow identifier of the data flow, and the second field is the corresponding next-hop exit port number, then in step 102, the data forwarding device can Obtain the flow identifier of the data packet, and then match it in the preset routing table according to the flow identifier to determine whether there is a next-hop egress port corresponding to the data packet in the preset routing table. This part of the content is well known to those skilled in the art, so it will not be repeated here.

In step 103, the data forwarding device determines the first port as the first port of the data packet to the destination data forwarding device among other ports recorded in the congestion information table of the data forwarding device except the congested outbound port of the destination data forwarding device for the data packet. The next hop outbound port of the forwarding device.

In order to facilitate the understanding of the routing method in the embodiment of the present invention, the following will first introduce the process for the data forwarding device to obtain the congestion information table.

A possible implementation manner of obtaining the congestion information table is as follows: the data forwarding device determines the congested port to each destination data forwarding device among all the ports of the data forwarding device; The port numbers of the congested ports of the device are recorded in the congestion information table, and the congestion information table also includes the congestion points of each congested port. In other words, the congestion record table maintained by the data forwarding device records the unavailable next-hop egress ports from the data forwarding device to each destination data forwarding device. Further, the congestion information table can also record the number of congestion points of each unavailable next-hop egress port.

Generally speaking, there are two main reasons for the unavailability of the next-hop egress port. One is congestion from the local data forwarding device to the next-hop data forwarding device, and the other is congestion from the next-hop data forwarding device to the destination data forwarding device. Therefore, the number of congestion points can reflect how many places are congested from the current data forwarding device to the destination forwarding device.

Therefore, based on the above two reasons, the data forwarding device can determine the congested port of each destination data forwarding device among all the ports of the data forwarding device, which can be implemented from two aspects. Whether the device is congested, on the other hand, is to determine whether the next hop data forwarding device is congested to the destination data forwarding device.

Wherein, determining whether the data forwarding device to the next-hop data forwarding device is congested may be by judging whether the number of data streams dispatched to the port connected to the next-hop data forwarding device exceeds a threshold, if the number of data streams exceeds the threshold, It means that the port is congested, otherwise, it means that the port is not congested. It may also be judged whether the packet sending rate of the port scheduled to connect to the next-hop data forwarding device exceeds the threshold. If the packet sending rate exceeds the threshold, it indicates that the port is congested; otherwise, it indicates that the port is not congested. This solution is applicable to the upper-layer data forwarding device from the source data forwarding device to the destination data forwarding device.

For example, such as the network structure shown in Figure 1c, access switch 1 has 2n ports, wherein n ports are used to connect hosts or servers, and the other n ports are used to connect uplink aggregation switches, for example Connect aggregation switches 1 of n layers. Regardless of which other access switch the destination data forwarding device is, for example, access switch 2n ² , and access switch 1 is, for example, the source switch, then aggregation switches 1 on n levels are reachable next-hop switches, so the connection The n ports of aggregation switch 1 may be called uplink ports. Furthermore, the access switch 1 can determine whether the aggregation switch 1 on the access switch 1 to n layers is congested. For example, there are already 20 data flows currently scheduled to the aggregation switch 1 on layer 1, which exceeds the threshold of 10, indicating that this path It is already congested and unavailable, so the port connected to aggregation switch 1 at level 1 can be recorded in the congestion information table. Currently, there are 5 data flows scheduled to aggregation switch 1 on layer n, and the threshold value is less than 10, indicating that this path is not congested and can be used as an available next-hop egress port.

Optionally, please refer to Table 1, which is a possible format of the congestion record table.

Destination Data Forwarding Device Unavailable next hop egress port 1 {port number: congestion points} 2 {port number: congestion points} … … k {port number: congestion points}

Table I

In Table 1, the congestion record table may include two fields, namely a "destination data forwarding device" field and an "unavailable next hop egress port" field. The "destination data forwarding device" can be filled with either the identifier of the destination data forwarding device or the address of the destination data forwarding device, such as an IP address. In practice, the content filled in this field only needs to be able to uniquely identify the destination data forwarding device, which is not specifically limited in this embodiment of the present invention. The "unavailable next hop egress port" field may be filled with the congested port number (the content before the colon) and the congestion point of the congested port (the content after the colon). Of course, in practical applications, the congestion record table may also include other fields, which are not specifically limited in this embodiment of the present invention.

Taking the previous example as an example, assume that the port number of aggregation switch 1 on connection level 1 of access switch 1 is 1, and the port number of aggregation switch 1 on connection level n is 3, and assume that the destination data forwarding device is an access switch 2. According to Table 1, the congestion record table saved on the access switch 1 can be shown in Table 2.

Destination Data Forwarding Device Unavailable next hop egress port IP address of access switch 2 {1:1}

Table II

It can be seen from Table 2 that because port 1 is congested, port 1 is recorded in the "unavailable next hop exit port" field, and the congestion point of port 1 is increased by 1, which is also recorded in the "unavailable next hop exit port" field. middle. But port 3 is not congested, so it is not recorded in Table 2.

Optionally, if the data forwarding device is an upper-layer data forwarding device, that is, the upper-layer data forwarding device of the non-purpose data forwarding device and the destination data forwarding device, it is determined whether the next-hop data forwarding device is congested to the destination data forwarding device, which may specifically include : The data forwarding device receives the third notification information sent by each lower layer data forwarding device connected to the port of the data forwarding device; wherein each lower layer data forwarding device is a data forwarding device on the path to each destination data forwarding device; the third notification The information is used to represent whether each lower layer data forwarding device can be used as a data forwarding device to reach the next hop of each destination data forwarding device; the data forwarding device determines the congestion of all ports of the data forwarding device to each destination data forwarding device according to the third notification information port.

It should be noted that the upper-layer data forwarding device and the lower-layer data forwarding device mentioned in this article are defined by the flow direction of the data packet. The upper-layer data forwarding device is the source of the data packet, and the lower-layer data forwarding device is the destination of the data packet. . Taking the network structure in Figure 1c as an example, access switch 1 wants to send data packets to aggregation switch 1 at layer n, then aggregation switch 1 at layer n is the lower-layer switch of access switch 1, and access switch 1 is It is the upper-layer switch of aggregation switch 1 of layer n.

Optionally, the lower-layer data forwarding device may encapsulate the third notification information and send it to the upper-layer data forwarding device together with the data packet, for example, through virtual extensible local area network (English: Virtual eXtensible Local Area Network, VXLAN for short) technology for encapsulation.

Optionally, the data forwarding device at the lower layer may construct a new message to send the third notification information. A possible new message format is shown in Table 3.

flag bit Destination Data Forwarding Device

Table three

As shown in Table 1, the new message format, that is, the format of the third notification information, may include two fields, namely a "flag bit" field and a "destination data forwarding device" field. In practice, other fields may also be included, which are not specifically limited in this embodiment of the present invention.

Optionally, the "flag bit" field can be represented by 0 and 1, for example, 1 indicates that it cannot be used as the next hop, and 0 indicates that it can be used as the next hop. Of course, in practical applications, the "flag bit" field can also be filled with other values, for example, "true" and "false" respectively indicate that the next hop can be used and the next hop cannot be used.

Optionally, the "destination data forwarding device" field may be filled with either the identifier of the destination data forwarding device or the address of the destination data forwarding device, such as an IP address. In practice, the content filled in this field only needs to be able to uniquely identify the destination data forwarding device, which is not specifically limited in this embodiment of the present invention.

Regardless of the sending method, when the data forwarding device receives the third notification information sent by each lower-layer data forwarding device, it can determine whether the lower-layer data forwarding device can serve as The next hop to reach the destination data forwarding device identified in the "destination data forwarding device" field, and then the congested port to each destination data forwarding device among all ports of the data forwarding device can be determined.

Optionally, the "destination data forwarding device" field may identify either one destination data forwarding device or a group of destination data forwarding devices.

For example, please continue to refer to the network structure shown in FIG. 1c. Assume that aggregation switch 1 on layer n finds that all core switches from itself to layer n are in a congested state based on the determination of the above two aspects, so aggregation switch 1 on layer n cannot reach access switch n+1 to access switch 2n ² , at this time, the convergence switch 1 on level n can send the third notification information to the access switch 1, in which the "flag bit" field can be filled with 1, and the "destination data forwarding device" The fields can be filled with the identifiers or addresses of the access switch n+1 to the access switch ²ⁿ² , then the access switch 1 can update Table 2 to obtain Table 4 after receiving the third notification information.

Table four

Optionally, when a port changes from a congested state to an uncongested state, the congestion point can be reduced by 1 in the congestion record table, and when the congestion point is reduced to 0, the port can be deleted from the congestion record table.

Optionally, if the data forwarding device is a non-source data forwarding device, that is, the lower layer data forwarding device, then correspondingly, the data forwarding device also determines whether all ports from itself to each destination data forwarding device are in a congested state; All ports of the first destination data forwarding device in each destination data forwarding device are in a congested state, then the data forwarding device sends the first notification information to the upper layer data forwarding device, and the first notification information is used to notify the upper layer data forwarding device that it cannot As the next hop from the upper layer data forwarding device to the first destination data forwarding device; The data forwarding device sends second notification information, and the second notification information is used to notify the upper layer data forwarding device that the data forwarding device can serve as a next hop for the upper layer data forwarding device to reach the second destination data forwarding device.

Among them, the first notification information and the second notification information are similar to the third notification information, the difference is that the third notification information includes two cases that can be used as the next hop Including the situation that cannot be used as the next hop, the second notification information only includes the situation that can be used as the next hop, but the three can use the same sending method and format, for example, use the message structure shown in Table 3 to send separately .

For example, the data forwarding device in step 103 is the aggregation switch 1 on layer n, and the aggregation switch 1 determines according to the methods in the above two aspects that all ports to the access switch 2 are in a congested state, then it can send The access switch 1 sends the first notification information. Assuming that the aggregation switch 1 determines according to the above two methods that all ports to the access switch 3 are not all in a congested state, that is, they can reach the access switch 3, then the aggregation switch 1 can send data to the access switch 1. Send the second notification information.

In the above description, each data forwarding device records and maintains the congestion record table by itself as an example, but in actual application, the controller in the network structure can exchange congestion information with each data forwarding device, establish and maintain the congestion record table, In step 103, the data forwarding device may acquire its own congestion record table from the controller.

In addition, it should be noted that in the above description, although the congestion information table is used as an example for illustration, in practice, it is also possible to create and maintain a non-congested information table, that is, non-congested ports can be recorded in the non-congested information table . Congestion information table and non-congestion information are two opposite expressions of the same thing, so the effect they can achieve is the same. The difference is that, generally speaking, the number of congested ports is less than the number of uncongested ports , so the congestion information table can reduce the amount of recorded data, saving storage space and maintenance costs.

Optionally, in order to ensure that the outgoing ports in the preset routing table are all available next-hop outgoing ports, and because the congestion record table will change with time, the method in the embodiment of the present invention further includes: if When the uncongested outgoing port of the data forwarding device is changed to a congested outgoing port, the data forwarding device also determines whether the congested outgoing port is included in the preset routing table; if the congested outgoing port is included in the preset routing table, the data The forwarding device deletes the entry including the congested egress port from the preset routing table. Through this method, it can be guaranteed that the outgoing port in the preset routing table is always an available next-hop outgoing port.

For example, in the aforementioned Tables 2 to 4, port 3 changes from an uncongested outgoing port to a congested outgoing port, then the access switch 1 will check whether port 3 is included in its local routing table, and if so, it will The entry containing port 3 is removed from the routing table. This avoids that in step 102, port 3 is matched, but port 3 is congested again, resulting in delay or failure in sending data packets. For the data flow corresponding to port 3, if there is a data packet of this data flow to be sent, then in step 102, the updated routing table can be used for matching, because it has been deleted, so the matching will fail, and then continue to go through step 103 again An outbound port is selected for the data packet, and then sent out through step 104 .

After introducing the congestion record table, step 103 will continue to be introduced below.

Because there is no next-hop egress port matching the data packet in the preset routing table, the data forwarding device can first check the congestion egress port of the destination data forwarding device recorded in the congestion information table, and then remove the congestion Among the ports other than the egress port, the first port is determined as the next hop egress port for the data packet to the destination data forwarding device.

Optionally, the first port may be a port randomly selected from other ports except the congestion outgoing port, or may be a port selected through certain rules, such as through Equal Cost MultiPath (English: Equal Cost MultiPath, referred to as : ECMP) mechanism to select the first port, and may also select the first port through a random load balancing (English: Valiant Load Balancing, referred to as: VLB) mechanism.

For example, the destination data forwarding device of the data packet is the access switch 2, and according to the congestion information table shown in Table 2, the access switch 1 determines that the port 1 of the access switch 2 is connected to the aggregation switch 1 of the layer 1 Port 1 is congested, so a port can be randomly selected from the remaining n-1 ports, for example, port 3, that is, the port connected to aggregation switch 1 of layer n as the first port, in other words, port 3 is selected as the data The packet arrives at the next hop egress port of access switch 2.

After the next hop-out port is determined, step 104 may be performed next, that is, the data forwarding device sends the data packet through the first port. For example, access switch 1 sends data packets through port 3.

On the transmission path of the data packet, in addition to the destination data forwarding device, the data forwarding devices at the upper layer from the source data forwarding device to the destination data forwarding device can all be executed according to steps 101 to 104.

Optionally, after step 104, the method further includes: creating a new entry for the data flow corresponding to the data packet in the preset routing table, and the outbound port of the new entry is the first port. For example, the first field of the new entry is the flow identifier, and the outbound port of the second field is port 3. Through this method, subsequent packets of the data flow can be forwarded according to the first port, saving data packet forwarding time.

Optionally, when a data packet arrives at a certain data forwarding device, if there is a single path from the data forwarding device to the destination data forwarding device, it can be forwarded directly from the single path, and the outbound port of the single path can be recorded in the preset in the routing table. This saves forwarding time.

Next, the complete process of sending a data packet from the source data forwarding device to the destination data forwarding device will be described. Please continue to refer to Figure 1c, assuming that the access switch 1 is the source data forwarding device, and the access switch 2n ² is the destination data forwarding device. equipment. As the source data forwarding device, the access switch 1 can first query the routing table saved by itself to determine whether the next hop exit port of the data packet can be matched. For example, if no match is found, then the congestion information shown in Table 2 can be First determine the congested port in the table, and find that the access switch 2n ² does not currently have a congested port, and then select a port from all the ports reachable to the access switch 2n ² as the next hop egress port, for example, select port 3, That is, connect the port of aggregation switch 1 on layer n, and then send the data packet from port 3 to aggregation switch 1 on layer n (in FIG. 1c, the solid arrow indicates the transmission path of the data packet). Optionally, the access switch 1 may create a new entry of the data flow corresponding to the data packet in the preset routing table, and the next hop exit port corresponding to the new entry is port 3 .

When the data packet arrives at the aggregation switch 1 on layer n, the aggregation switch 1 can also perform matching in its own saved routing table, and the result is that it is matched to the next hop egress port, for example, it is connected to the core switch n on layer n, then the The aggregation switch 1 sends the data packet to the core switch n.

When the data packet reaches the core switch n, because in the network structure of Figure 1c, there is only one path from the aggregation switch on each level to a certain access switch, so there is only one path from the core switch to a certain access switch, Therefore, the core switch can directly forward the message according to the next-hop egress port recorded in the preset routing table. Therefore, in this embodiment, the core switch n will forward the data packet according to the next hop exit port in the locally stored routing table, and the data packet will be sent to the aggregation switch 2n on layer n.

When the data packet reaches the aggregation switch 2n on layer n, because the lower layer of the aggregation switch 2n is the destination data forwarding device, that is, the access switch 2n ² , the aggregation switch 2n also performs single-path forwarding, that is, through the locally saved routing table The next hop egress port forwards the data packet, and the data packet will be sent to the access switch 2n ² . So far, the data packet is sent from the source data forwarding device, that is, the access switch 1 to the destination data forwarding device, that is, the access switch 2n ² .

The implementation process of the switching network shown in FIG. 1a is similar to the example described above, so it will not be described in detail here.

It can be seen from the above description that, in the first aspect, in the embodiment of the present invention, the data forwarding device feeds back information about whether the link from itself to the destination data forwarding device is available, unlike the routing scheme in the prior art, which requires feedback The utilization rate of each path between the source data forwarding device and the destination data forwarding device; second aspect, in the embodiment of the present invention, the feedback is not from the destination data forwarding device to the source data forwarding device, but from the congested data Forwarding equipment to the upper data forwarding equipment; thirdly, when the data forwarding equipment performs traffic scheduling, it only needs to select the available next-hop outbound port, that is, the route is selected hop by hop, instead of selecting the optimal path as in the prior art , so one end-to-end path is selected at a time. Therefore, the solution in the embodiment of the present invention has strong scalability and can be easily extended to a multi-level clos architecture. Furthermore, because the congested ports are recorded, there are fewer table entries occupied, which is an order of magnitude difference from the table entries occupied by the routing scheme in the prior art, and this advantage becomes larger and larger as the clos level increases. For details, please refer to Table 5, which is a comparison of table item gaps between the scheme in the embodiment of the present invention and the routing scheme described in the background art.

Table five

Furthermore, no matter how big the clos level is, the congestion information is real-time, because when a data forwarding device detects that a certain port is congested, it only needs to delete the port from the available next hop of the destination data forwarding device. In addition, usually when a data forwarding device has no available next hop to the destination data forwarding device, or when there is no available next hop to an available next hop, the data forwarding device will notify the upper layer data forwarding device, so The method in the embodiment of the present invention also takes less time to feed back the congestion information.

Based on the same inventive concept, an embodiment of the present invention further provides a data forwarding device (as shown in FIG. 2 ), where the data forwarding device is used to implement the aforementioned method.

Specifically, the processor 10 is configured to obtain the data packet, and determine whether the next-hop outgoing port of the data packet is matched in the preset routing table; wherein, the outgoing ports in the preset routing table are not The congested outgoing ports are all ports in port 50; if the next hop outgoing port of the data packet is not matched in the preset routing table, the processor 10 is also used Among other ports recorded in the congestion information table to the congested egress port of the destination data forwarding device of the data packet, determine the first port as the next hop egress port of the data packet to the destination data forwarding device; The outgoing ports in the congestion information table and the other ports are all ports in the port 50; the sender 20 sends the data packet through the first port.

Optionally, the processor 10 is further configured to: determine a congested port to each destination data forwarding device among the at least two ports; The port number of the port is recorded in the congestion information table.

Optionally, if the data forwarding device is a non-source data forwarding device, the processor 10 is further configured to: determine whether all ports from the data forwarding device to each destination data forwarding device are in a congested state;

The sender 20 is further configured to: if all ports from the data forwarding device to the first destination data forwarding device among the respective destination data forwarding devices are in a congested state, send first notification information to the upper layer data forwarding device, and the The first notification information is used to notify the upper-layer data forwarding device that the data forwarding device cannot serve as the next hop for the upper-layer data forwarding device to reach the first destination data forwarding device; if the data forwarding device arrives at the All ports of the second destination data forwarding device in each destination data forwarding device are not in a congested state, then sending second notification information to the upper layer data forwarding device, the second notification information is used to notify the upper layer data forwarding device, The data forwarding device can serve as a next hop for the upper layer data forwarding device to reach the second destination data forwarding device.

Optionally, the receiver 30 is configured to receive third notification information sent by each lower-layer data forwarding device connected to the port of the data forwarding device; wherein, each lower-layer data forwarding device forwards the data forwarding device on the path of the device; the third notification information is used to represent whether each lower layer data forwarding device can serve as the next hop for the data forwarding device to reach each destination data forwarding device; the processor 10 also It is configured to: determine, according to the third notification information, a congested port to each destination data forwarding device among the at least two ports.

Optionally, the processor 10 is further configured to: if the uncongested egress port of the data forwarding device is changed to a congested egress port, determine whether the congested egress port is included in the preset routing table; When the preset routing table includes the congested egress port, delete the entry including the congested egress port from the preset routing table.

Optionally, the processor 10 is further configured to: after determining the first port as the next hop port for the data packet to the destination forwarding device, in the preset routing table for the data packet A new entry is created for the corresponding data flow, and the outbound port of the new entry is the first port.

Based on the same inventive concept, an embodiment of the present invention also provides a routing device. The routing device is used to implement the routing method shown in FIG. 3 . Next, please refer to FIG. 4, the routing device includes: a processing unit 201, configured to obtain a data packet; determine whether the next hop port of the data packet is matched in the preset routing table; wherein, the preset The outgoing ports in the preset routing table are all non-congested outgoing ports; if the next hop outgoing port of the data packet is not matched in the preset routing table, record it in the congestion removal information table of the data forwarding device Among other ports other than the congested outgoing port of the destination data forwarding device for the data packet, determine the first port as the next hop outgoing port for the data packet to the destination data forwarding device; the sending unit 202 is configured to pass The first port sends the data packet.

Optionally, the processing unit 201 is further configured to: determine a congested port to each destination data forwarding device among all ports of the data forwarding device; The port numbers of the congested ports are recorded in the congestion information table.

Optionally, if the data forwarding device is a non-source data forwarding device, the processing unit 201 further uses: determining whether all ports from the data forwarding device to each destination data forwarding device are in a congested state; the sending unit 202 further It is used for: if all the ports from the data forwarding device to the first destination data forwarding device among the various destination data forwarding devices are in a congested state, sending first notification information to the upper layer data forwarding device, the first notification The information is used to notify the upper-layer data forwarding device that the data forwarding device cannot serve as the next hop for the upper-layer data forwarding device to reach the first destination data forwarding device; If all the ports of the second destination data forwarding device in the forwarding device are not in a congested state, then the second notification information is sent to the upper layer data forwarding device, and the second notification information is used to notify the upper layer data forwarding device that the data The forwarding device can serve as a next hop for the upper layer data forwarding device to reach the second destination data forwarding device.

Optionally, the routing device further includes a receiving unit 203, and the receiving unit 203 is configured to: receive third notification information sent by each lower-layer data forwarding device connected to the port of the data forwarding device; wherein, each lower-layer data forwarding device is a data forwarding device on the path to each destination data forwarding device; the third notification information is used to represent whether each lower layer data forwarding device can reach each destination data forwarding device as the data forwarding device The next hop; the processing unit 201 is further configured to: determine, according to the third notification information, a congested port to each destination data forwarding device among all ports of the data forwarding device.

Optionally, the processing unit 201 is further configured to: if the uncongested egress port of the data forwarding device is changed to a congested egress port, determine whether the congested egress port is included in the preset routing table; When the preset routing table includes the congested egress port, delete the entry including the congested egress port from the preset routing table.

Optionally, the processing unit 201 is further configured to: after the first port is determined as the next hop port for the data packet to the destination forwarding device, in the preset routing table for the data packet A new entry is created for the corresponding data flow, and the outbound port of the new entry is the first port.

The various variations and specific examples of the routing method in the foregoing embodiment in FIG. 3 are also applicable to the routing device and data forwarding device in this embodiment. Through the foregoing detailed description of the routing method, those skilled in the art can clearly understand that this The implementation methods of the routing device and the data forwarding device in the embodiments are not described in detail here for the sake of brevity.

Those skilled in the art should understand that the embodiments of the present invention may be provided as methods, systems, or computer program products. Accordingly, the present invention can take the form of an entirely hardware embodiment, an entirely software embodiment, or an embodiment combining software and hardware aspects. Furthermore, the present invention may take the form of a computer program product embodied on one or more computer-usable storage media (including but not limited to disk storage, optical storage, etc.) having computer-usable program code embodied therein.

The present invention is described with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems), and computer program products according to embodiments of the invention. It should be understood that each procedure and/or block in the flowchart and/or block diagram, and a combination of procedures and/or blocks in the flowchart and/or block diagram can be realized by computer program instructions. These computer program instructions may be provided to a general purpose computer, special purpose computer, embedded processor, or processor of other programmable data processing equipment to produce a machine such that the instructions executed by the processor of the computer or other programmable data processing equipment produce a An apparatus for realizing the functions specified in one or more procedures of the flowchart and/or one or more blocks of the block diagram.

These computer program instructions may also be stored in a computer-readable memory capable of directing a computer or other programmable data processing apparatus to operate in a specific manner, such that the instructions stored in the computer-readable memory produce an article of manufacture comprising instruction means, the instructions The device realizes the function specified in one or more procedures of the flowchart and/or one or more blocks of the block diagram.

These computer program instructions can also be loaded onto a computer or other programmable data processing device, causing a series of operational steps to be performed on the computer or other programmable device to produce a computer-implemented process, thereby The instructions provide steps for implementing the functions specified in the flow chart or blocks of the flowchart and/or the block or blocks of the block diagrams.

Obviously, those skilled in the art can make various changes and modifications to the present invention without departing from the spirit and scope of the present invention. Thus, if these modifications and variations of the present invention fall within the scope of the claims of the present invention and equivalent technologies thereof, the present invention also intends to include these modifications and variations.

Claims (18)

1. A routing method, characterized in that, comprising: The data forwarding device obtains the data packet; The data forwarding device determines whether the next-hop egress port of the data packet is matched in the preset routing table; wherein, the egress ports in the preset routing table are all uncongested egress ports; If the next hop out port of the data packet is not matched in the preset routing table, the destination data of the data packet recorded by the data forwarding device in the de-congestion information table of the data forwarding device Among the ports other than the congested egress port of the forwarding device, determine the first port as the next hop egress port of the data packet to the destination data forwarding device; The data forwarding device sends the data packet through the first port. 2. The method of claim 1, further comprising: The data forwarding device determines a congested port to each destination data forwarding device among all ports of the data forwarding device; The data forwarding device records the respective destination data forwarding devices and the port numbers of the congested ports corresponding to the respective destination data forwarding devices in the congestion information table. 3. The method according to claim 2, wherein if the data forwarding device is a non-source data forwarding device, the method further comprises: The data forwarding device determines whether all ports from the data forwarding device to the respective destination data forwarding devices are in a congested state; If all ports from the data forwarding device to the first destination data forwarding device among the respective destination data forwarding devices are in a congested state, the data forwarding device sends first notification information to the upper-layer data forwarding device, and the first The notification information is used to notify the upper-layer data forwarding device that the data forwarding device cannot serve as the next hop for the upper-layer data forwarding device to reach the first destination data forwarding device; If all the ports from the data forwarding device to the second destination data forwarding device among the respective destination data forwarding devices are not in a congested state, the data forwarding device sends second notification information to the upper layer data forwarding device, and the The second notification information is used to notify the upper-layer data forwarding device that the data forwarding device can serve as a next hop for the upper-layer data forwarding device to reach the second destination data forwarding device. 4. The method according to claim 2 or 3, wherein the data forwarding device determines a congested port to each destination data forwarding device among all ports of the data forwarding device, comprising: The data forwarding device receives the third notification information sent by each lower-layer data forwarding device connected to the port of the data forwarding device; wherein, each lower-layer data forwarding device is on the path to each destination data forwarding device A data forwarding device; the third notification information is used to represent whether each lower layer data forwarding device can serve as a next hop for the data forwarding device to reach each destination data forwarding device; The data forwarding device determines a congested port to each destination data forwarding device among all ports of the data forwarding device according to the third notification information. 5. The method according to any one of claims 1-4, further comprising: If the uncongested egress port of the data forwarding device is changed to a congested egress port, the data forwarding device further determines whether the congested egress port is included in the preset routing table; If the preset routing table includes the congested egress port, the data forwarding device deletes the entry including the congested egress port from the preset routing table. 6. The method according to any one of claims 1-5, wherein after said determining the first port as the next hop port for the data packet to the destination forwarding device, the method further include: The data forwarding device creates a new entry in the preset routing table for the data flow corresponding to the data packet, and the outbound port of the new entry is the first port. 7. A data forwarding device, characterized in that, comprising: at least two ports; A processor, configured to obtain a data packet, and determine whether a next-hop egress port of the data packet is matched in a preset routing table; wherein, the egress ports in the preset routing table are all uncongested egress ports And both are ports in the at least two ports; if the next hop port of the data packet is not matched in the preset routing table, the processor is also used to In addition to other ports recorded in the congestion information table to the congested egress port of the destination data forwarding device of the data packet, determine the first port as the next hop egress port of the data packet to the destination data forwarding device; The egress port in the congestion information table and the other ports are ports in the at least two ports; a sender, for sending the data packet through the first port. 8. The data forwarding device according to claim 7, wherein the processor is further configured to: determine the congested port of each destination data forwarding device among the at least two ports; The forwarding device and the port numbers corresponding to the congested ports of the respective destination data forwarding devices are recorded in the congestion information table. 9. The data forwarding device according to claim 8, wherein if the data forwarding device is a non-source data forwarding device, the processor is further configured to: Whether all ports of the forwarding device are in a congested state; The sender is further configured to: if all ports from the data forwarding device to the first destination data forwarding device among the respective destination data forwarding devices are in a congested state, send first notification information to the upper layer data forwarding device, so The first notification information is used to notify the upper-layer data forwarding device that the data forwarding device cannot serve as the next hop for the upper-layer data forwarding device to reach the first destination data forwarding device; If all the ports of the second destination data forwarding device in each of the above destination data forwarding devices are not in a congested state, then the second notification information is sent to the upper layer data forwarding device, and the second notification information is used to notify the upper layer data forwarding device , the data forwarding device can serve as a next hop for the upper layer data forwarding device to reach the second destination data forwarding device. 10. The data forwarding device according to claim 8 or 9, wherein the data forwarding device further comprises a receiver, The receiver is configured to receive third notification information sent by each lower-layer data forwarding device connected to the port of the data forwarding device; wherein each lower-layer data forwarding device is a path to each destination data forwarding device The data forwarding device above; the third notification information is used to represent whether each lower layer data forwarding device can serve as the next hop for the data forwarding device to reach each destination data forwarding device; The processor is further configured to: determine a congested port to each destination data forwarding device among the at least two ports according to the third notification information. 11. The data forwarding device according to any one of claims 7-10, wherein the processor is further configured to: if an uncongested egress port of the data forwarding device is changed to a congested egress port, determine Whether the preset routing table contains the congested outgoing port; if the preset routing table contains the congested outgoing port, the entry containing the congested outgoing port will be removed from the preset routing table Deleted in . 12. The data forwarding device according to any one of claims 7-11, wherein the processor is further configured to: determine the first port as the destination of the data packet to the destination forwarding device After the next hop egress port, a new entry is established for the data flow corresponding to the data packet in the preset routing table, and the egress port of the new entry is the first port. 13. A routing device, characterized in that it comprises: A processing unit, configured to obtain a data packet; determine whether the next hop egress port of the data packet is matched in the preset routing table; wherein, the egress ports in the preset routing table are all uncongested egress ports ; If the next hop exit port of the data packet is not matched in the preset routing table, the congestion exit port of the destination data forwarding device of the data packet recorded in the congestion removal information table of the data forwarding device Among the other ports, the first port is determined as the next hop port for the data packet to the destination data forwarding device; a sending unit, configured to send the data packet through the first port. 14. The routing device according to claim 13, wherein the processing unit is further configured to: determine a congested port to each destination data forwarding device among all ports of the data forwarding device; The data forwarding device and the port numbers corresponding to the congested ports of the respective destination data forwarding devices are recorded in the congestion information table. 15. The routing device according to claim 14, wherein if the data forwarding device is a non-source data forwarding device, the processing unit is further used to: determine the data forwarding device to each destination data forwarding device Whether all the ports of are in congested state; The sending unit is further configured to: if all ports from the data forwarding device to the first destination data forwarding device among the respective destination data forwarding devices are in a congested state, send first notification information to the upper data forwarding device, The first notification information is used to notify the upper-layer data forwarding device that the data forwarding device cannot serve as the next hop for the upper-layer data forwarding device to reach the first destination data forwarding device; If all the ports of the second destination data forwarding device in the respective destination data forwarding devices are not in a congested state, then send second notification information to the upper layer data forwarding device, the second notification information is used to notify the upper layer data forwarding device device, and the data forwarding device can serve as a next hop for the upper layer data forwarding device to reach the second destination data forwarding device. 16. The routing device according to claim 14 or 15, characterized in that, the routing device further comprises a receiving unit, The receiving unit is configured to: receive third notification information sent by each lower-layer data forwarding device connected to the port of the data forwarding device; wherein, each lower-layer data forwarding device is a path to each destination data forwarding device The data forwarding device above; the third notification information is used to represent whether each lower layer data forwarding device can serve as the next hop for the data forwarding device to reach each destination data forwarding device; The processing unit is further configured to: determine a congested port to each destination data forwarding device among all ports of the data forwarding device according to the third notification information. 17. The routing device according to any one of claims 13-16, wherein the processing unit is further configured to: if the uncongested egress port of the data forwarding device is changed to a congested egress port, determine the whether the preset routing table contains the congested outgoing port; if the preset routing table contains the congested outgoing port, remove the entry containing the congested outgoing port from the preset routing table Deleted in . 18. The routing device according to any one of claims 13-17, wherein the processing unit is further configured to: determine the first port as the destination forwarding device for the data packet After jumping out of the port, a new entry is established in the preset routing table for the data flow corresponding to the data packet, and the outgoing port of the new entry is the first port.