CN108259326B

CN108259326B - Routing table updating method and device, distribution node and leaf message forwarding equipment

Info

Publication number: CN108259326B
Application number: CN201611246731.XA
Authority: CN
Inventors: 喻径舟; 何子键
Original assignee: Huawei Technologies Co Ltd
Current assignee: Huawei Technologies Co Ltd
Priority date: 2016-12-29
Filing date: 2016-12-29
Publication date: 2020-06-26
Anticipated expiration: 2036-12-29
Also published as: CN108259326A

Abstract

A method, a device, a distribution node and a leaf message forwarding device for updating a routing table are provided, the method comprises the following steps: the distribution node receives a message sent by the inlet node; the message is a message which is not successfully matched in a preposed hot spot routing table stored on the inlet node; matching the matching item fields in the distribution table according to the destination IP address of the message; if the destination IP address is successfully matched with the first matching item field in the distribution table, acquiring the physical box number of a first search node where the routing information of the first prefix sub-tree corresponding to the first matching item field is located; determining congestion of a first search node and acquiring routing information of a first prefix sub-tree; sending the routing information of the first prefix subtree to an inlet node so as to update a preposed hot point routing table; and/or adding the routing information of the first prefix subtree into a post-positioned hot point routing table stored on the distribution node; the routing table entry of the back hot spot routing table and the routing table entry of the front hot spot routing table contain the same field.

Description

Routing table updating method and device, distribution node and leaf message forwarding equipment

Technical Field

The present invention relates to the field of communications technologies, and in particular, to a method and an apparatus for updating a routing table, a distribution node, and a leaf packet forwarding device.

Background

The router is mainly used for forwarding network Protocol (IP) messages, that is, forwarding messages arriving at an input port of the router to a correct output port according to a destination IP address in a message header. The route searching is a process of searching a routing table in a router according to a destination IP address of the message to obtain the output port information of the message.

As networks evolve, the demands for the throughput of routers increase. In the prior art, a method for improving the throughput of a router is horizontal expansion (Scale Out), that is, the whole router is constructed by stacking a plurality of boxes, the performance is improved mainly by increasing the number of boxes, and the Scale effect is easily realized, so that the cost is reduced.

A horizontally extended distributed router and a route lookup method in the prior art are described below. The distributed router comprises an entrance computing node, a rebound computing node and an exit computing node, and further comprises other computing nodes. The ingress computing node receives the network packet and determines to which of the bounce computing nodes to route the received network packet. Specifically, the ingress computing node generates hash keys based on the received destination IP address, each hash key corresponding to a different computing node (e.g., a bounce computing node) of the distributed router, such that, after the ingress computing node determines a particular bounce computing node, the ingress computing node sends the network packet to the determined bounce computing node without performing a route lookup. The bounce computing node determines where to route the network packet based on the destination IP address. In particular, each bounce compute node stores a different set (e.g., subset, portion, etc.) of routing entries. The bounce computing node determines the particular egress computing node responsible for the departure of the network packet from the distributed router.

In the route searching method, the Hash key generated by the destination IP address is adopted to perform distributed storage of the route table, so that a large number of route entries are repeated, Hash (Hash) conflicts exist because the distributed route searching is performed on the basis of the Hash key, an additional mechanism is needed for solving the Hash conflicts, and false hits are also caused. Thus, the overall routing efficiency is low.

Disclosure of Invention

The embodiment of the invention provides a method and a device for updating a routing table, a distribution node and leaf message forwarding equipment, which are used for solving the technical problem of low efficiency of a routing mechanism of a distributed router in the prior art.

In a first aspect, an embodiment of the present invention provides a method for updating a routing table, which is described from the perspective of a distribution node of a packet forwarding system. The distribution node receives the message sent by the inlet node of the message forwarding system; the message is the message which is not successfully matched in the preposed hot point routing table stored on the inlet node by the inlet node. The routing table entry of the preposed hot spot routing table comprises a prefix field and an exit port field, and the exit port field comprises a physical box number and an exit port of an exit node of the message forwarding system. The distribution node is stored with a distribution table, the distribution table entry of the distribution table comprises a matching item field and a search node number field, the matching item field is a prefix corresponding to a root node of a prefix sub-tree, and the search node number field is a physical box number of a search node where the routing information of the prefix sub-tree is located. The distribution node performs matching of the matching item field in the distribution table according to the target network protocol IP address of the message and the principle of Longest Prefix Matching (LPM); if the destination IP address is successfully matched with the first matching item field in the allocation table, the allocation node acquires the physical box number of a first search node where the routing information of a first prefix sub-tree using the first matching item field as a prefix is located; the first searching node is a searching node of the message forwarding system; and the distribution node determines the congestion of the first search node and acquires the routing information of the first prefix sub-tree. The distribution node sends the routing information of the first prefix subtree to the inlet node, and the routing information of the first prefix subtree is used for updating the preposed hot point routing table; and/or the distribution node adds the routing information of the first prefix sub-tree to a post-positioned hot point routing table stored on the distribution node; wherein a routing table entry of the post-hotspot routing table comprises the prefix field and the egress port field. The routing table updating method in the embodiment of the invention has the advantages of timely response to the congestion condition brought by the distributed routing search, accurate positioning, timely updating, and capability of controlling the congestion at millisecond level, so that packet loss is not easy to occur, and the load of a processor of the message forwarding equipment is small.

In one possible design, the assigning node determining that the first lookup node is congested includes: the distribution node stores the message into a queue corresponding to the first matching item field; the distribution node determines whether the total length of the messages in the queue exceeds a preset threshold value or not; and if the total length of the message exceeds the preset threshold value, the distribution node determines that the first search node is congested. By the method, whether the searching node is congested or not can be determined rapidly, and the reaction time of congestion control is prolonged.

In one possible design, the queue corresponds to a flag bit, and the flag bit is used to characterize whether the post-hotspot routing table is valid, and the method further includes: when the message is dequeued, the distribution node determines whether the post-hot point routing table is valid according to the flag bit corresponding to the queue; and when the post-hot point routing table is effective, the distribution node matches the message in the post-hot point routing table and sends the message to an outlet node corresponding to the successfully matched prefix field. By the method, the message does not need to be sent to the first searching node, so that the congestion of the first searching node can be reduced, and the message forwarding efficiency is improved.

In one possible design, adding, by the distribution node, the routing information of the first prefix sub-tree to a post-hotspot routing table stored on the distribution node includes: and the distribution node adds the routing information of the first prefix subtree to the post-hot point routing table and sets the value of the flag bit corresponding to the queue as the effective value representing the post-hot point routing table. The method can quickly judge the flow direction of the message and improve the message processing speed.

In one possible design, the obtaining, by the distribution node, the routing information of the prefix sub-tree corresponding to the matching item that is successfully matched includes: the distribution node sends an update request message to the first search node, a processor or an SDN controller on a physical box where the distribution node is located, wherein the update request message is used for requesting routing information of a prefix sub-tree corresponding to a matching item which is successfully matched; and the distribution node receives the routing information of the prefix sub-tree corresponding to the matching item sent by the first search node, the processor or the SDN controller.

In one possible design, the update request message includes an identification of the prefix sub-tree and a physical box number in which the leaf allocation node is located.

In a second aspect, an embodiment of the present invention provides a method for searching a route. The method is described from the perspective of leaf message forwarding devices of a message forwarding system. In the method, leaf message forwarding equipment receives a message. The leaf message forwarding equipment matches in a preposed hot spot routing table stored on the leaf message forwarding equipment according to the target IP address of the message and an LPM principle; the routing table entry of the preposed hot spot routing table comprises a prefix field and an exit port field, and the exit port field comprises an exit leaf message forwarding device identifier and an exit port of the message forwarding system. If the leaf message forwarding equipment is not successfully matched in the preposed hot spot routing table, matching the matching item fields in a distribution table according to the target IP address and the LPM principle; the distribution table item of the distribution table comprises a matching item field and a core message forwarding device identification field, wherein the matching item field is a prefix corresponding to a root node of a prefix sub-tree, and the core message forwarding device identification field is an identification of the core message forwarding device where the routing information of the prefix sub-tree is located; the core message forwarding device is a core message forwarding device of the message forwarding system. If the destination IP address is successfully matched with the first matching item field in the distribution table, the leaf message forwarding equipment acquires the identifier of the first core message forwarding equipment in which the routing information of a first prefix sub-tree using the first matching item field as a prefix is located; the leaf message forwarding equipment determines that the first core message forwarding equipment is congested and acquires the routing information of the first prefix sub-tree; the leaf message forwarding equipment updates the routing information of the first prefix subtree to the preposed hot point routing table; and/or the leaf message forwarding equipment adds the routing information of the first prefix sub-tree to a post-positioned hot point routing table stored on the leaf message forwarding equipment; wherein a routing table entry of the post-hotspot routing table comprises the prefix field and the egress port field. The routing table updating method in the embodiment of the invention has the advantages of timely response to the congestion condition brought by the distributed routing search, accurate positioning, timely updating, and capability of controlling the congestion at millisecond level, so that packet loss is not easy to occur, and the load of a processor of the message forwarding equipment is small.

In one possible design, the determining, by the leaf packet forwarding device, that the core packet forwarding device is congested includes: the leaf message forwarding equipment stores the message into a queue corresponding to the first matching item field; the leaf message forwarding equipment determines whether the total length of the messages in the queue exceeds a preset threshold value or not; and if the total length of the messages exceeds the preset threshold value, the leaf message forwarding equipment determines that the first core message forwarding equipment is congested.

In one possible design, the queue corresponds to a flag bit, and the flag bit is used to characterize whether the post-hotspot routing table is valid, and the method further includes: when the message is dequeued, the leaf message forwarding equipment determines whether the post hot point routing table is effective or not according to the flag bit corresponding to the queue; and when the post-hot-point routing table is effective, the leaf message forwarding equipment matches the message in the post-hot-point routing table and sends the message to an outlet node corresponding to the successfully-matched prefix field.

In one possible design, adding, by a leaf packet forwarding device, the routing information of the first prefix sub-tree to a post-hotspot routing table stored on the leaf packet forwarding device includes: and the leaf message forwarding equipment adds the routing information of the first prefix subtree to the post-hot point routing table, and sets the value of the flag bit corresponding to the queue as a value representing the effectiveness of the post-hot point routing table.

In one possible design, the pre-hotspot routing table and the post-hotspot routing table are the same hotspot routing table.

In one possible design, the obtaining, by the leaf packet forwarding device, the routing information of the prefix sub-tree corresponding to the successfully matched matching item includes: the leaf message forwarding equipment sends an update request message to the first core message forwarding equipment, a processor or an SDN controller on the leaf message forwarding equipment, wherein the update request message is used for requesting the routing information of the prefix sub-tree corresponding to the matching item successfully matched; and the leaf message forwarding equipment receives the routing information of the prefix sub-tree corresponding to the matching item sent by the first core message forwarding equipment, the processor or the SDN controller.

In one possible design, the update request message includes an identifier of the prefix sub-tree and an identifier of the leaf packet forwarding device.

In a third aspect, an embodiment of the present invention provides an allocation node. The distribution node includes: a transmit port, a receive port, and a processor. The sending port may be configured to perform the sending step in the routing table updating method of the first aspect. The receiving port may perform the steps of receiving or obtaining in the routing table update method of the first aspect described above. The processor may perform the steps added, matched or determined in the routing table update method of the first aspect described above.

In a fourth aspect, an embodiment of the present invention provides a routing table updating apparatus, where the routing table updating apparatus includes a functional module configured to implement the method in the first aspect.

In a fifth aspect, an embodiment of the present invention provides a leaf packet forwarding device. The leaf message forwarding device comprises: at least two ports, a transmit port, a receive port, and a processor. The sending port may be configured to perform the sending step in the routing table updating method of the second aspect. The receiving port may perform the steps of receiving or obtaining in the routing table update method of the second aspect described above. The processor may perform the steps added, matched or determined in the routing table update method of the second aspect described above.

In a sixth aspect, the present invention also provides a computer storage medium having program code stored thereon, where the program code includes instructions for implementing any possible implementation manner of the methods of the first and second aspects.

Drawings

Fig. 1 is a structural diagram of a message forwarding system according to an embodiment of the present invention;

FIGS. 2 a-2 b are schematic diagrams of a prefix and a prefix sub-tree according to an embodiment of the present invention;

fig. 3 is a structural diagram of another message forwarding system provided in the embodiment of the present invention;

fig. 4 is a structural diagram of a message forwarding device according to an embodiment of the present invention;

fig. 5 is a flowchart of a method for updating a routing table according to an embodiment of the present invention;

fig. 6 is a schematic diagram of a queue corresponding to a matching entry according to an embodiment of the present invention;

fig. 7 is a structural diagram of another message forwarding system according to an embodiment of the present invention;

FIG. 8 is a diagram illustrating another prefix sub-tree according to an embodiment of the present invention;

fig. 9 is a flowchart of another routing table updating method according to an embodiment of the present invention;

fig. 10 is a functional block diagram of a routing table updating apparatus according to an embodiment of the present invention.

Detailed Description

Hereinafter, the embodiment of the present invention will be described in detail.

The term "and/or" herein is merely an association describing an associated object, meaning that three relationships may exist, e.g., a and/or B, may mean: a exists alone, A and B exist simultaneously, and B exists alone. In addition, the character "/" herein generally indicates that the former and latter related objects are in an "or" relationship.

To facilitate the description of the method for updating a routing table in the embodiment of the present invention, a method for searching a route and a message forwarding system to which the method can be applied in the embodiment of the present invention are described first. Fig. 1 is a block diagram of a possible message forwarding system according to an embodiment of the present invention. As shown in fig. 1, the packet forwarding system includes a controller, at least one ingress node, at least one distribution node, at least one lookup node, and at least one egress node. In practical applications, a physical box may include only one type of node, or may be a collection of multiple types of nodes. For example, a physical box may include both ingress and distribution nodes. A physical box may include both an entry node and a lookup node. A physical box may include both ingress and egress nodes. A physical box may include both distribution nodes and look-up nodes. A physical box may include both a lookup node and an egress node. A physical box may include both ingress nodes and allocation and lookup nodes. A physical box may include both ingress nodes and also distribution nodes and egress nodes. A physical box may include both ingress nodes, and also lookup nodes and egress nodes. A physical box may include both distribution nodes and look-up and egress nodes. A physical box may include both ingress nodes and also allocation, lookup and egress nodes. The controller may be provided separately from each node or in the same physical box as either node. These physical boxes are stacked to form the complete router. Of course, in practice, these physical boxes may be distributed in different areas and manufactured by different manufacturers.

In the structure shown in fig. 1, what is transmitted between each type of node is a message, for example, an ingress node receives a message and then transmits the message to any distribution node, the distribution node transmits the message to a searched search node after searching, then the search node transmits the message to a determined egress node after determining an egress node of the message, and then the egress node transmits the message to other network elements.

It should be understood that the structure shown in fig. 1 only shows one possible scenario of the message forwarding system, but the embodiment of the present invention is not limited thereto. The message forwarding system may further include other components, and the embodiment of the present invention is not limited.

The ingress node may store a hot spot routing table, where a routing table entry of the hot spot routing table includes a prefix field and an egress port field, and the egress port field includes a physical box number and an egress port of an egress node of the packet forwarding system. The hotspot routing table may include prefixes that are used more frequently.

Alternatively, the prefix may be represented by a three-valued bit string consisting of "0", "1", and "".

In one possible example, the routing table entry of the hot spot routing table includes a prefix field, an egress port field, such as shown in table one.

Prefix	Output port field
		0000*	31-02

Watch 1

In the example of table one, the routing table entry indicates that the packet matching the prefix 0000 × needs to be forwarded from the egress port number 02 of the egress node with physical box number 31.

The distribution nodes are stored with distribution tables, and the distribution tables stored on each distribution node are the same. The distribution table items of the distribution table comprise matching item fields and search node number fields, the matching item fields are prefixes corresponding to root nodes of a prefix sub-tree, and the search node number fields are physical box numbers of search nodes where the routing information of the prefix sub-tree is located.

Specifically, the prefix tree may be a binary tree or a multi-branch tree. The prefix tree is a binary or multi-way tree built from the bit strings in the prefix. If one bit is considered at a time, a binary tree, also known as a unit Trie, is built. Fig. 2a shows a unit prefix tree. The prefix tree includes 11 real prefixes, the left sides p 0-p 10 in fig. 2a, corresponding nodes in the unit Trie tree are represented by black circles, and connection points are represented by white circles. If multiple bits are considered each time, a multiple-bit Trie tree is built. The number of bits considered each time is generally fixed and is called the step size of the Trie tree (english: stride).

The multi-bit Trie can be regarded as that a unit Trie is divided into a plurality of subtrees according to stride, and a Trie node is created for each subtree. Each Trie node has an associated prefix, and the associated prefix of one Trie node is a prefix value on a root node of a subtree corresponding to the Trie node.

Fig. 2b shows a multi-bit Trie with stride equal to 3 built based on the prefixes in fig. 2 a. The multi-bit Trie includes 7 Trie nodes, such as Trie Node T1-Trie Node T7 shown in fig. 2b, and each Trie Node is a prefix sub-tree. Each prefix sub-tree contains at least one real prefix. Each Trie node is configured with a prefix node, for example, the root node of the prefix subtree T1 corresponds to a prefix p0, and the root node of the prefix subtree T2 corresponds to a prefix 000, which is not a real prefix.

For example, the allocation table created based on each prefix sub-tree shown in fig. 2b is shown in table two.

Matching items	Looking up node number
		*	10
000*	11
		100*	12
111*	13
		000010*	14
000011*	15
		111010*	16

Watch two

In table two, the matching entry field of the first entry is a prefix corresponding to the root node of the prefix sub-tree T1, the lookup node number field is 10, and it indicates that the routing information corresponding to all the real prefixes (prefix p1 and prefix p2) of the prefix sub-tree T1 is stored in the lookup node with physical box number 10. Similarly, the matching entry field of the second entry is the prefix corresponding to the root node of the prefix sub-tree T2. The matching item field of the third table item is the prefix corresponding to the root node of the prefix sub-tree T3. The matching item field of the fourth table item is a prefix corresponding to the root node of the prefix sub-tree T4. The matching item field of the fifth table item is a prefix corresponding to the root node of the prefix sub-tree T5. The matching item field of the sixth entry is a prefix corresponding to the root node of the prefix sub-tree T6. The matching item field of the seventh table item is a prefix corresponding to the root node of the prefix sub-tree T7.

Correspondingly, the lookup node may store a real routing table, and the real routing table may store routing information of all real prefixes of a partial prefix sub-tree. Therefore, each searching node only needs to maintain the routing table entry of a part of the real prefixes, so that the resources consumed for maintaining the routing table are less, and the searching nodes can conveniently and quickly search.

Optionally, each prefix sub-tree may be assigned a search node, or a group of search nodes. In the case of a set of lookup nodes, one of the lookup nodes in the set of lookup nodes may be the primary lookup node and the other lookup nodes may be backup lookup nodes.

The table entry of the real routing table comprises a real prefix of at least one prefix sub-tree and a physical box number and an exit port of the corresponding exit node. For example, the actual routing table entry on the lookup node with physical box number 10 is shown as table three, for example.

True prefix	Output port
		P1，0*	20-01
P2，10*	21-02

Watch III

Table three shows the routing information of the prefix subtree T1, and the prefix subtree T1 includes two real prefixes, p1, denoted 0 × and p2, denoted 10 × respectively. The real prefix is filled in the real prefix field, and the exit port field is the physical box number and the exit port of the exit node of the message forwarding system.

In the example of table three, the first routing table entry indicates that the packet matching prefix 0 x needs to be forwarded from the port number 01 of the egress node with physical box number 21.

How the route lookup is performed will be described below. When a message enters the ingress node, the ingress node may match in the hot routing table as shown in table one according to the destination IP address of the message, and if the matching is successful, the message is sent to the egress node corresponding to the prefix that is successfully matched for forwarding. If the matching is unsuccessful, the entry node can randomly select a distribution node and send the message to the distribution node. And the distribution node matches in a distribution table shown as a table two according to the target IP address of the message and the LPM principle, if the matching is successful, the physical box number of the search node corresponding to the matching item successfully matched is obtained, and the message is sent to the search node corresponding to the obtained physical box number. After receiving the message, the searching node matches in the real routing table shown in table three according to the target IP address of the message and the LPM principle, obtains the physical box number and the output port of the outlet node corresponding to the successfully matched real prefix, and sends the message to the obtained outlet node. The egress node forwards the message according to the egress port. At this point, the forwarding process of a message in the message forwarding system is finished.

It can be seen from the above description that, in the embodiment of the present invention, the real routing tables are stored in a distributed manner on different lookup nodes, so that the routing tables can be distributed more uniformly, and the pressure of the routing table specification of a single node is reduced. Furthermore, the distribution node and the search node adopt the LPM matching principle when matching, so that no conflict exists when distributing the search node, and the false hit condition does not exist, so that the route search efficiency is higher on the whole.

It should be noted that, if the flow allocated to a certain lookup node is greater than the processing capability of the lookup node, the lookup node may be congested or even lose packets, so that the packet processing delay is increased, and the throughput of the packet forwarding system is reduced. To solve the technical problem, an embodiment of the present invention provides a method for solving congestion of a lookup node, and specifically, in an architecture of a packet forwarding system shown in fig. 1, when determining a lookup node to which a packet needs to be sent, an allocation node determines whether the lookup node is congested, and if the lookup node is congested, obtains routing information of a prefix sub-tree to which the packet is successfully matched in an allocation table, and sends the routing information of the prefix sub-tree to an ingress node, so that the ingress node can update the routing information of the prefix sub-tree to a hot spot routing table in time (for convenience of description, the hot spot routing table stored on the ingress node is hereinafter referred to as a pre-hot spot routing table). Therefore, when the entry node is matched with the hot spot routing table next time, the hit rate is improved, and then the messages distributed to the searching node for route searching are reduced, so that the problem of searching node congestion is solved, the message processing time delay is reduced, and the throughput rate of the message forwarding system is improved.

Referring to the packet forwarding system shown in fig. 3, a difference from the packet forwarding system shown in fig. 1 is that a distribution node and an egress node may have a connection relationship, and a post-hotspot routing table may be set on the distribution node, where the post-hotspot routing table has a structure the same as that of a pre-hotspot routing table, and for example, both include a prefix field and an egress port field. When judging that a certain searching node is congested, the distribution node can acquire the routing information of the prefix sub-tree successfully matched with the message in the distribution table, and add the routing information of the prefix sub-tree into the post-hotspot routing table. Therefore, the message which reaches the distribution node and needs to be distributed to the search node can be matched in the post hot point routing table, and the message is sent to the exit node which is successfully matched. The exit node forwards the message according to the exit port without sending the message to the searching node, so that the message sent to the searching node for route searching is reduced, the problem of congestion of the searching node is solved, the message processing time delay is reduced, and the throughput rate of the message forwarding system is improved.

Furthermore, the distribution node can also send the routing information of the prefix sub-tree to the inlet node, so that the inlet node can update the routing information of the prefix sub-tree to the preposed hot spot routing table in time, when the inlet node is matched with the hot spot routing table next time, the hit rate can be improved, and then the messages distributed to the search node for routing search can be reduced, thereby solving the problem of congestion of the search node, further reducing the message processing time delay and improving the throughput rate of the message forwarding system.

The same parts of the message forwarding system shown in fig. 3 and the message forwarding system shown in fig. 1 will not be described again, and please refer to the foregoing description of each node of the message forwarding system shown in fig. 1.

Referring next to fig. 4, fig. 4 is a possible structural diagram of a message forwarding device according to an embodiment of the present invention. The message forwarding device is, for example, one possible structure diagram of the above ingress node, distribution node, lookup node, egress node, and controller. As shown in fig. 4, the message forwarding apparatus includes: processor 10, transmitting port 20, receiving port 30, memory 40. The memory 40, the transmitting port 20 and the receiving port 30, and the processor 10 may be connected by a bus. Of course, in practical applications, the memory 40, the transmitting port 20, the receiving port 30 and the processor 10 may be not in a bus structure, but may be in other structures, such as a star structure, and the present application is not limited in particular.

Optionally, the processor 10 may be a general-purpose central processing unit or an Application Specific Integrated Circuit (ASIC), may be one or more Integrated circuits for controlling program execution, may be a hardware Circuit developed by using a Field Programmable Gate Array (FPGA), and may be a baseband processor.

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

Optionally, the Memory 40 may include one or more of a Read Only Memory (ROM), a Random Access Memory (RAM), and a disk Memory. Memory 40 is used to store data and/or instructions required by processor 10 during operation. The number of the memory 40 may be one or more. The memory 40 may also be used to store the hot spot routing table, the allocation table, and the real routing table described above.

Alternatively, the transmitting port 20 and the receiving port 30 may be physically independent from each other or integrated together.

The sum of the optional sending ports 20 and receiving ports 30 is at least two, the sending port 20 for message output may also be referred to as an egress port, and the receiving port 30 for message input may also be referred to as an ingress port.

Referring to fig. 5, a flowchart of a method for updating a routing table according to an embodiment of the present invention is shown. As shown in fig. 5, the method includes:

step 101: the ingress node receives the packet. For example, the ingress node receives messages sent from other message forwarding systems, or the ingress node receives messages sent from a host or server connected to the ingress node. Typically, the message includes a header, a body, and a check code. The header may include a source IP address and a destination IP address.

Step 102: the ingress node matches in the pre-hotspot routing table according to the destination IP address of the packet to determine the egress port information of the packet, i.e., the physical box number and the egress port where the egress node is located. Optionally, the matching result includes matching success and matching failure. If the matching is successful, the inlet node sends the message to the outlet node in the outlet port information corresponding to the prefix field successfully matched, and the outlet node forwards the message according to the outlet port. If the matching is not successful, step 103 is executed, that is, the message is sent to any distribution node. The method can rapidly forward the message and reduce the burden of distributing nodes and searching nodes.

For example, the destination IP address of the packet is 111110010 (binary description, simplified to 9bits for convenience of description), in practical application, the destination IP address may be of other lengths, for example, 32bits, and the matching is performed in the previous hot spot routing table as described in table one, and the matching result is that the matching is not successful, that is, the routing information corresponding to the destination IP address is not stored in the previous hot spot routing table, so the ingress node may execute step 103, and send the packet to any distribution node, for example, the first distribution node.

Optionally, in step 103, the ingress node may consider load balancing and send the packet to the distribution node with a smaller workload. Of course, in actual use, the allocation may be completely random, or alternatively.

The distribution node receiving the message may perform step 104, i.e. perform matching in the distribution table according to the destination IP address of the message, for example, perform matching of matching entry fields in the distribution table described above by using the LPM principle. If the destination IP address is successfully matched with the first matching entry field in the allocation table, the allocation node further obtains the physical box number of the first lookup node corresponding to the successfully matched matching entry in step 104. Specifically, for example, the physical box number of the first lookup node where the routing information of the first prefix sub-tree corresponding to the first matching entry field is located is the lookup node of the packet forwarding system.

For example, the destination IP address of the packet is 111110010, and the distribution node performs matching in the distribution table shown in the foregoing table two, and performs matching according to the LPM principle, and then matches the fourth entry 111 of the matching entry field, so that the distribution node obtains the physical box number 13 of the lookup node where the routing information of the prefix sub-tree corresponding to the fourth entry 111 is located.

After determining the first look-up node number, the allocating node performs step 105 of determining whether the first look-up node is congested. Alternatively, step 105 may be implemented in a variety of ways, as will be illustrated below.

One possible implementation of step 105 is: the distribution node stores the message into a queue corresponding to the first matching item field; the distribution node determines whether the total length of the messages in the queue exceeds a preset threshold value or not; and if the total length of the message exceeds a preset threshold value, the distribution node determines that the first search node is congested.

In a practical example, the distribution node may establish a Queue for each matching entry field in the distribution table, which is referred to as a distribution Queue (RQ) for convenience of description, and as shown in fig. 6, fig. 6 is a schematic diagram of the Queue established for each matching entry field. In fig. 6, it is assumed that the matching entry field of the allocation table has n entries, where n is a positive integer. So one RQ can be established for each of the n matches, for a total of n RQs. Because the routing information of the prefix sub-tree corresponding to one matching item can be stored in one or more lookup nodes, a message corresponding to an RQ can be stored in one or more egress queues (english: Output Queue, abbreviated as OQ) corresponding to the RQ; because the routing information of the prefix sub-tree corresponding to the multiple matching items can be stored in the same search node, each OQ can store at least two RQ corresponding messages. Each OQ corresponds to a lookup node. Therefore, the number k of OQs is an integer greater than or equal to 2.

It should be noted that, if the routing information of the prefix sub-tree corresponding to one matching item is stored in two or more than two lookup nodes (all the routing information of the prefix sub-tree is stored in each lookup node), the packet in the RQ corresponding to the matching item may be scheduled to the OQ corresponding to the two or more than two lookup nodes by a scheduling mechanism, for example, randomly scheduling or alternatively scheduling.

Optionally, after the message is stored in the OQ, the message may be dequeued according to a first-in first-out principle and sent to the corresponding lookup node. If the search capability of a certain search node is not enough to cope with, congestion may occur, and the congestion may be transmitted to a corresponding RQ, which is represented in the RQ, that is, the packet congestion corresponding to the RQ, so the total length of the packet corresponding to the RQ (or called as the depth of the RQ) may increase, and when the depth of the RQ is greater than the queue capacity, a packet loss may occur.

Therefore, when the depth of the RQ is greater than the preset threshold, that is, the total length of the packet corresponding to the RQ is greater than the preset threshold, it is determined that the lookup node is congested.

In practical applications, it may also be determined whether the first searching node is congested through other embodiments, for example, when the first searching node determines that it is congested, notification information is sent to all the distribution nodes to notify that it is currently in a congested state. For another example, the distribution node determines whether the packet sending rate of the port scheduled to the first lookup node exceeds a threshold, and if the packet sending rate exceeds the threshold, it indicates that the first lookup node is congested, otherwise, it indicates that the first lookup node is not congested.

Regardless of which way the congestion of the first searching node is determined, if the congestion of the first searching node is determined, the distribution node can normally send the message to the first searching node according to the flow.

If it is determined that the first lookup node is congested, the distribution node may perform step 106, that is, obtain the routing information of the prefix sub-tree corresponding to the matching item that is successfully matched. For example, the routing information of the first prefix sub-tree corresponding to the first matching item successfully matched is obtained.

Optionally, step 106 may include: step 1061, the distribution node sends an update request message, where the update request message is used to request the routing information of the prefix sub-tree corresponding to the matching item that is successfully matched; step 1062: the distribution node receives the routing information of the prefix sub-tree.

Specifically, in step 1061, the distribution node may send the update request information to the first lookup node, a processor in a physical box where the distribution node is located, or a Software Defined Network (SDN) controller. Because the first search node is a node where the routing information of the prefix sub-tree corresponding to the matching item successfully matched is stored, the routing information of the prefix sub-tree can be requested from the first search node. The processor or SDN controller typically stores routing information for all nodes, so it may also request routing information for the prefix sub-tree from the processor and SDN.

Optionally, the format of the update request message sent by the distribution node is, for example, as shown in table five.

Find physical box number of node

Physical box number of distribution node

Identification of prefix subtree (ID)

Watch five

In table five, the physical box number of the lookup node and the physical box number of the allocation node may also be replaced by other tags capable of uniquely identifying a lookup node or an allocation node. The ID of the prefix sub-tree is used to indicate which routing information of the prefix sub-tree is requested, so the ID of the prefix sub-tree can be filled, and the prefix corresponding to the root node of the prefix sub-tree can also be filled, that is, the matching item that is successfully matched.

Optionally, when the first lookup node, the processor, or the SDN controller receives update request information sent by the distribution node, the first lookup node, the processor, or the SDN controller may obtain routing information of the prefix sub-tree according to the update request information, and send the routing information to the requesting distribution node. For example, when receiving the update request information in the format shown in table five, the routing information of the prefix sub-tree may be obtained according to the ID of the prefix sub-tree. And then sending the acquired routing information of the prefix sub-tree to the distribution node according to the physical box number of the distribution node.

Optionally, a format of the update response message sent by the first lookup node, the processor, or the SDN controller is, for example, as shown in table six.

Watch six

In table six, the number of routes field is used to indicate how many pieces of route information are included in the update response message, and this field is an optional field. The ith routing information field (i takes values from 1 to p) is used to fill in the routing information. The completion flag field is used to indicate that the update is completed, and since in actual operation, one update can be completed by multiple update response messages, the completion flag field is used to inform the distribution node whether the update is completed or not. The completion flags field is an optional field.

After receiving the update response message, the distribution node can know which prefix sub-tree the routing information in the update response message is according to the ID of the prefix sub-tree.

The physical box number of the distribution node may make the distribution node know that the update response message is sent to itself.

When receiving an update response message sent by the first lookup node, the processor, or the SDN controller, the allocation node may extract the routing information of the prefix sub-tree from the update response message.

The foregoing only illustrates one possible implementation manner of the update request message and the update response message, and in practical applications, the update request message and the update response message may also be sent in a type transmission format, which is not limited in particular in the embodiment of the present invention.

In the above, the routing information of the prefix sub-tree corresponding to the matching item that is possibly successfully matched is described, but in practical application, the distribution node may also obtain the routing information of the prefix sub-tree in other ways, and the embodiment of the present invention is not limited specifically.

After the distribution node obtains the routing information of the prefix sub-tree, for example, the routing information of the first prefix sub-tree, only step 107 may be executed next, that is, the distribution node sends the routing information of the prefix sub-tree to the ingress node; step 109 may be executed only, that is, the routing information of the prefix sub-tree is added to the post-hotspot routing table stored on the distribution node; step 107 and step 109 may be performed.

In step 107, the routing information of the prefix sub-tree may be sent to all ingress nodes, or may be sent only to the ingress node from which the packet originated. For the case where the ingress node and the distribution node are located in the same physical box, the routing information sent in step 107 may be sent via a bus inside the physical box. For the case where the ingress node and the distribution node are not located in the same physical box, the sending of the routing information in step 107 may be through a communication line between the physical boxes.

After the ingress node receives the routing information of the prefix sub-tree sent by the allocating node, the ingress node performs step 108, that is, updates the routing information of the prefix sub-tree into the pre-hotspot routing table. Therefore, when a message with the highest position of the destination IP address as the matching item reaches the ingress node, the ingress node matches the destination IP address in the updated preposed hot point routing table, so that the matching is successful, and then directly sends the message to the physical box where the successfully matched egress node is located, and the ingress node can forward the message according to the successfully matched egress port. Because the successfully matched message can not be sent to the matching node and can not enter the RQ, the number of the messages distributed to the first searching node is reduced, the congestion condition of the first searching node is improved, and the processing capacity of the distribution node is reduced.

In addition, the method in this embodiment reacts to the congestion situation in time, the location is accurate (for example, it can be accurately located which search node is congested), and the update response time is about 2ms, so the congestion is controlled at ms level, packet loss is not easy, and the processing load of the processor is small.

The implementation of step 109 is described next. Specifically, a post-hotspot routing table is created on the distribution node, and the format of the post-hotspot routing table may be the same. A flag bit is then maintained for each match in the allocation table, e.g., one flag bit for each RQ queue. The initial value of the flag bit is 0, false, or other value that characterizes the invalidity of the post-hotspot routing table.

Optionally, when the distribution node acquires the routing information of the prefix sub-tree corresponding to the matching item successfully matched in step 106, step 109 is executed to store the routing information of the prefix sub-tree into the post-hotspot routing table. Therefore, when the messages in the RQ corresponding to the prefix sub-tree are dequeued, matching can be performed in the post hot point routing table, and matching is successful, then the distribution node directly sends the messages to the physical box where the successfully matched exit node is located, and the entry node can forward the messages according to the successfully matched exit port. Because the successfully matched messages can not be sent to the first searching node, the number of the messages processed by the first searching node is reduced, and the congestion condition of the first searching node is improved.

Optionally, at the same time as or after step 109, the allocating node further sets the value of the flag bit corresponding to the RQ corresponding to the prefix sub-tree to the value representing that the post-hotspot routing table is valid. Therefore, when the message in the RQ corresponding to the prefix sub-tree is dequeued, the flag bit can be checked first, and if the value of the flag bit represents that the post-hotspot routing table is invalid, the message is directly sent to the corresponding lookup node for routing lookup; if the value of the zone bit indicates that the post hot spot routing table is effective, the routing search is directly carried out through the post hot spot routing table. By setting the flag bit, the flow direction of the message can be judged quickly, and the message processing speed is improved.

In addition to the technical effect described in step 107, the embodiment of step 109 reacts more timely to congestion because the update response time of the updated post-hotspot routing table is about 4 microseconds (us) and the update signaling occupies about 0.128% of the bandwidth.

It should be noted that, if there are both a pre-hotspot routing table and a post-hotspot routing table, the update request message shown in the foregoing table five may further include an object field, where the object field is used to indicate whether the object requesting the update is the pre-hotspot routing table or the post-hotspot routing table. Accordingly, the object field may also be included in the update response message shown in table six. Optionally, the object field may be composed of two bits, where the first bit identifies an update of the pre-hotspot routing table, and the second bit identifies an update of the post-hotspot routing table, for example, 10 indicates an update of the pre-hotspot routing table, 01 indicates an update of the post-hotspot routing table, and 11 indicates an update of the pre-hotspot routing table and the post-hotspot routing table.

The message forwarding system shown in fig. 1 is configured to logically divide each node, but in actual deployment, the ingress node and the distribution node may be in one physical box, i.e. the hot spot routing table and the distribution table are stored on the same physical device. For example, in the network structure of the actually deployed packet forwarding system shown in fig. 7, the network structure is a leaf-spine (leaf-spine) topology structure. The message forwarding system comprises 2m leaf switches (leaf switch 1-leaf switch 2m respectively) and m core switches (core switch 1-core switch m respectively), wherein m is a positive integer. Each leaf switch is connected with m core switches respectively, and each core switch is connected with 2m leaf switches respectively. Each leaf switch may also connect no more than m hosts or servers. Of course, in practical applications, the switch in fig. 7 may also be other message forwarding devices, such as a router, and the embodiment of the present invention is not limited in particular.

In the packet forwarding system as shown in fig. 7, the leaf switch can implement both the function of an ingress node and the function of an allocation node, so that the leaf switch can store the hot spot routing table and the allocation table at the same time, and when the leaf switch queries that the hot spot routing table is not successfully matched, the leaf switch can continue to search the allocation table locally. Further, the leaf switch may also implement the function of the egress node. The core switch may implement the functionality of a lookup node.

Of course, fig. 7 only shows one network structure in actual deployment, and in actual application, the method shown in fig. 5 is also applicable to other network structures, such as a class 3 clos (clos) structure based on fat tree (fat-tree) topology, for example, a more-level clos structure. When the method shown in fig. 5 is actually implemented in these network structures, the principle is the same as or similar to that of the structure shown in fig. 7, so the following will describe in detail the implementation process of updating the hot spot routing table in this type of close architecture by taking the packet forwarding system shown in fig. 7 as an example.

Fig. 8 is a schematic diagram of a prefix sub-tree in the present embodiment. In the prefix subtrees shown in fig. 8, there are 4 prefix subtrees, i.e., prefix subtree T10 to prefix subtree T13. The root prefix of the prefix sub-tree T10, i.e., the root node, is the prefix R0. The root prefix of the prefix subtree T11 is a prefix R1. The root prefix of the prefix subtree T12 is a prefix R2. The root prefix of the prefix subtree T13 is a prefix R3. Prefixes R0 through R3 are non-true prefixes. Prefixes R0 through R3 fill the matching entry fields of the allocation table, respectively.

The prefix sub-tree T10 contains a real prefix p11 and a real prefix p 12. The prefix sub-tree T11 contains a real prefix p13 and a real prefix p 17. The prefix sub-tree T12 contains a real prefix p14, a real prefix p15, and a real prefix p 16. The prefix sub-tree T13 contains the real prefix p 18. Real prefix p11 through real prefix p18 may fill prefix fields in a hot spot routing table, real routing table.

Assuming that the routing information of the prefix sub-tree T10 and the prefix sub-tree T12 is stored in the core switch 1, the real routing table stored on the core switch 1 is, for example, as shown in table seven.

True prefix	Output port
		p11:1*	2-01
p12：01*	4-03
		p14：1110*	7-02
p15:1111*	6-03
		p16:11110*	2-02

Watch seven

Assuming that the routing information of the prefix sub-tree T11 and the prefix sub-tree T13 is stored in the core switch 3, the stored real routing table on the core switch 3 is, for example, as shown in table eight.

True prefix	Output port
		p13:0101*	4-01
p17：01000*	5-03
		p18：11110010*	6-02

Table eight

Assuming that the routing information of the prefix sub-tree T11 is also stored in the core switch 2, the stored real routing table on the core switch 2 is shown, for example, in table nine.

True prefix	Output port
		p13:0101*	4-01
p17：01000*	5-03

Watch nine

Assuming that the routing information of the prefix sub-tree T13 is also stored in the core switch 4, the stored real routing table on the core switch 4 is shown, for example, as table ten.

True prefix	Output port
		p18：11110010*	6-02

Watch ten

The allocation table stored on the leaf switch is shown, for example, in table eleven.

Watch eleven

In table eleven, the core switch identification field corresponds to the physical box number of the lookup node in the aforementioned allocation table. In addition, in the present embodiment, an RQ ID field may be added in the allocation table for filling the RQID corresponding to each matching entry. Of course, in actual use, a corresponding relation table between the matching item and the RQ ID may be established.

Referring to fig. 9, fig. 9 is a flowchart illustrating a method for updating a routing table according to an embodiment of the present invention. As shown in fig. 9, the method includes:

step 201: the leaf switch receives the message. For example, leaf switch 1 receives a message sent by a host.

Step 202: and the leaf switch carries out matching in the preposed hot spot routing table according to the destination IP address of the message. The implementation of step 102 is the same, and therefore, is not described herein again.

Step 203: if the matching in step 202 is not successful, the leaf switch performs matching in the allocation table according to the destination IP address of the packet, and obtains the core switch identifier corresponding to the matching item successfully matched. For example, the destination IP address of the packet is 111110010 (binary description, simplified to 9bits), and the length of the packet is 1.2K. The leaf switch 1 queries the pre-hot point routing table according to the LPM principle, and the matching is not successful, so the leaf switch 1 queries the distribution table shown in table eleven according to the LPM principle, and hits a third matching entry, i.e., R2: 111, the corresponding core switch is identified as core switch 1.

Step 204: the leaf switch determines whether the core switch is congested. Continuing with the foregoing example as an example, after the third matching entry is hit, the leaf switch 1 continues to read the RQ ID of the third matching entry as 2. And then storing the message into a queue with the RQ ID of 2. At this time, the total length of the packet (the number of bytes already added to the length of the stored packet) of the queue with the RQ ID of 2 becomes, for example, 10.2K. Assuming that the preset threshold is 10K, the total length of the packets in the queue with RQ ID 2 at this time exceeds the threshold, so it can be determined that the core switch 1 is in the congestion state.

Optionally, state information as shown in table twelve may be maintained on the leaf switch for each RQ.

Watch twelve

Therefore, the leaf switch can obtain the existing byte number of each RQ message according to the twelve inquiry in the table, and the total length of each RQ message at present can be obtained by adding the length of the newly stored message. Of course, in actual application, the existing byte number of each RQ message may also be recorded in other forms, and the embodiment of the present invention is not limited specifically.

Step 205: and if the core switch is congested, obtaining the routing information of the prefix sub-tree corresponding to the matching item which is successfully matched.

Optionally, step 205 includes: step 2051: the leaf switch sends an update request message to the core switch, a processor on the leaf switch or an SDN controller; step 2052: and the leaf switch receives the routing information of the prefix subtree corresponding to the matching item which is successfully matched.

Continuing with the foregoing example as an example, the matching entry successfully matched is the third entry R2, and the corresponding core switch is the core switch 1. Accordingly, leaf switch 1 may send an update request message to core switch 1, a processor on leaf switch 1, or an SDN controller. For example, as shown in table thirteen, the message format sent to the processor or the SDN processor may be added with a field for filling the communication address of the processor or the SDN controller, or the "core switch identification" field in table thirteen may be replaced with a field for filling the communication address of the processor or the SDN controller.

Core switch identification	Leaf switch identification	ID of prefix sub-tree
			Core switch
1	Leaf exchanger 1	T12

Watch thirteen

When the core switch 1 receives the message request message as shown in table thirteen, all the routing information in the stored prefix sub-tree T12 is encapsulated into an update response message, which is sent to the leaf switch 1. Optionally, the message response message is as shown in table fourteen.

Table fourteen

In practical applications, the length of the message is limited, and then the routing information of the prefix sub-tree can be sent through a plurality of messages, for example, divided into two messages as shown in table fifteen.

Fifteen items of table

Step 206: the leaf switch updates the routing information of the prefix subtree to the preposed hot spot routing table. For example, the leaf switch 1 updates the routing information of the prefix sub-tree T12 into the pre-hotspot routing table, and then the new entry of the pre-hotspot routing table is shown in table sixteen.

Prefix	Output port field
		…	…
p14:1110*	7-02
		p15:1111*	6-03
p16:11110*	2-02

Watch sixteen

Assuming that the leaf switch 1 receives a message again at this time, and the destination IP address of the message is also 111110010, the leaf switch matches the pre-hot-point routing table shown in table sixteen, hits p15, and obtains the egress port information corresponding to the successfully matched real prefix, i.e., the port 02 on the leaf switch 7. The leaf switch 1 then sends the message to the leaf switch 7 via the message forwarding system shown in fig. 7. The message does not need to be matched in an allocation table, stored in an RQ (resource request) and sent to the core switch 1 for route searching, so that the congestion of the distributed table lookup can be reduced.

If the leaf switch is further provided with a post-hotspot routing table, the leaf switch may further execute step 207, that is, update the routing information of the prefix sub-tree into the post-hotspot routing table.

For example, state information as shown in table seventeen is maintained on leaf switch 1 for each RQ.

Seventeen table

After the leaf switch updates the routing information of the prefix sub-tree into the post-hot-point routing table, the flag bit of the RQ with the RQ ID of 2 can be updated to be 1, which represents that the post-hot-point routing table is valid.

Optionally, in practical application, the pre-hotspot routing table and the post-hotspot routing table may be the same table, or may be two separate tables.

Under the condition of having the zone bit, when the message is dequeued, the zone bit can be inquired first, if the value of the zone bit indicates that the post hot point routing table is effective, the post hot point routing table can be inquired, and then the message is forwarded to the leaf switch which is successfully matched. If the value of the flag bit indicates that the post-hot point routing table is invalid, the message can be sent to the core switch successfully matched in the distribution table for further routing lookup.

For example, in the state shown in table seventeen, when a packet in queue 1 is dequeued and the length of the packet is 0.5K, the depth of queue 1 is updated to 4K (the number of bytes minus the length of the dequeued packet). At this time, the flag bit corresponding to the queue 1 is 0, which indicates that the post hot-point routing table is invalid, so that the message is sent to the core switch 2 or the core switch 3 (random selection or polling, or selection according to the scheduling result of the scheduler) to query the real routing table.

At this time, there is another message forwarding system, the destination IP address of the message is 010100001, and the message length is 1.2K. The leaf switch queries the allocation table according to the LPM rule and hits the second entry, i.e., R1: 010. Reading the ID of the RQ to be 1, storing the message into a queue 1, and updating the depth of the queue 1 to be 5.2K. Assuming that the preset threshold is 5K, the leaf switch sends an update request message to the core switch 2 or the core switch 3 (randomly selected or polled, or selected according to the scheduling result of the scheduler), or may also send the update request message to a processor or an SDN controller of the leaf switch. The update request message sent to the core switch 2 is shown in table eighteen, for example.

Core switch identification	Leaf switch identification	ID of prefix sub-tree
			Core switch
2	Leaf exchanger 1	T11

Watch eighteen

After receiving the update request message, the core switch 2 encapsulates all the routing information of the maintained prefix sub-tree T11 into an update response message, and sends the update response message to the leaf switch 1. The update response message is shown in table nineteen, for example.

Table nineteen

After receiving the update response message, the leaf switch 1 may store the routing information into the post-hotspot routing table, and the new entry in the post-hotspot routing table is shown in table twenty.

Prefix	Output port field
		…	…
p13:0101*	4-01
		p17:01000*	5-03

Watch twenty

Then, the leaf switch 1 changes the flag bit of the queue 1 to 1, and the representation post-hotspot routing table is valid.

Assuming that a packet in the queue 1 is dequeued at this time, the destination IP address of the packet is 010110101, and the leaf switch 1 can check the value of the flag bit of the queue 1, because the value is changed to 1 in the foregoing step, the post hot point routing table is represented to be valid, and then the leaf switch 1 can use the destination IP address of the packet to look up a table according to the LPM principle, hit the table entry p13:0101, obtain the egress port information, i.e., port 01 of the leaf switch 4, and then forward the packet. The message is not sent to core switch 2 and core switch 3, thereby reducing congestion of the distributed lookup table.

As can be seen from the above description, the method for updating a routing table in the embodiment of the present invention reacts in time to congestion caused by searching for a distributed route, and is accurate in positioning, and the congestion can be controlled at millisecond level in time of updating, so that packet loss is not easy, and the load of a processor of a packet forwarding device is small.

Based on the same inventive concept, an embodiment of the present invention further provides a message forwarding device (as shown in fig. 4), where the message forwarding device is configured to implement any one of the foregoing methods.

Optionally, when the message forwarding device is a distribution node, the receiving port 30 is configured to receive a message sent by an entry node of a message forwarding system; the message is the message of the inlet node which is not successfully matched in the preposed hot point routing table; the routing table entry of the preposed hot spot routing table comprises a prefix field and an exit port field, and the exit port field comprises a physical box number and an exit port of an exit node of the message forwarding system;

a processor 10, configured to perform matching of the matching entry field in an allocation table according to a Longest Prefix Match (LPM) principle according to a destination network protocol (IP) address of the packet; the distribution table entry of the distribution table comprises a matching entry field and a search node number field, the matching entry field is a prefix corresponding to a root node of a prefix sub-tree, and the search node number field is a physical box number of a search node where the routing information of the prefix sub-tree is located.

The processor 10 is further configured to, if the destination IP address is successfully matched with the first matching entry field in the allocation table, obtain a physical box number of a first lookup node where routing information of a first prefix sub-tree using the first matching entry field as a prefix is located; the first searching node is a searching node of the message forwarding system; determining that the first search node is congested, and acquiring routing information of the first prefix sub-tree; a sending port 20, configured to send routing information of the first prefix sub-tree to the ingress node, where the routing information of the first prefix sub-tree is used to update the pre-hotspot routing table; and/or processor 10 is further configured to add routing information of the first prefix sub-tree to a post-hotspot routing table stored on the distribution node; wherein a routing table entry of the post-hotspot routing table comprises the prefix field and the egress port field.

Optionally, the processor 10 is configured to: storing the message into a queue corresponding to the first matching item field; determining whether the total length of the messages in the queue exceeds a preset threshold value; and if the total length of the message exceeds the preset threshold value, determining that the first search node is congested.

Optionally, the queue corresponds to a flag, where the flag is used to characterize whether the post-hotspot routing table is valid, and the processor 10 is configured to: when the message is dequeued, determining whether the postposition hot point routing table is effective or not according to the flag bit corresponding to the queue; when the post-hot point routing table is valid, the distribution node matches the message in the post-hot point routing table; the sending port 20 is further configured to send the packet to an egress node corresponding to the prefix field successfully matched.

Optionally, the processor 10 is configured to add the routing information of the first prefix sub-tree to the post-hotspot routing table, and set a value of a flag bit corresponding to the queue to a value that characterizes that the post-hotspot routing table is valid.

Optionally, when the message forwarding device in fig. 4 is a leaf message forwarding device, such as the leaf switch, the receiving port 30 is configured to receive a message; a processor 10, configured to perform matching in a pre-hot point routing table stored on the leaf packet forwarding device according to a Longest Prefix Match (LPM) principle according to a destination network protocol (IP) address of the packet; the routing table entry of the preposed hot spot routing table comprises a prefix field and an output port field, and the output port field comprises an outlet leaf message forwarding device identifier and an output port of the message forwarding system; the processor 10 is further configured to, if the matching is not successful in the pre-hotspot routing table, perform matching of the matching entry field in an allocation table according to the LPM principle and according to the destination IP address; the distribution table item of the distribution table comprises a matching item field and a core message forwarding device identification field, wherein the matching item field is a prefix corresponding to a root node of a prefix sub-tree, and the core message forwarding device identification field is an identification of the core message forwarding device where the routing information of the prefix sub-tree is located; the core message forwarding device is a core message forwarding device of the message forwarding system; if the destination IP address is successfully matched with the first matching item field in the distribution table, acquiring an identifier of a first core message forwarding device in which the routing information of a first prefix sub-tree using the first matching item field as a prefix is located; and determining congestion of the first core message forwarding equipment, and acquiring routing information of the first prefix sub-tree.

The processor 10 is further configured to update the routing information of the first prefix sub-tree to the pre-hotspot routing table; and/or the routing information of the first prefix sub-tree is also used for adding the routing information of the first prefix sub-tree into a post-positioned hot point routing table stored on the leaf message forwarding equipment; wherein a routing table entry of the post-hotspot routing table comprises the prefix field and the egress port field.

Optionally, the processor 10 is configured to store the packet into a queue corresponding to the first matching entry field; determining whether the total length of the messages in the queue exceeds a preset threshold value; and if the total length of the message exceeds the preset threshold value, determining that the first core message forwarding equipment is congested.

Optionally, the queue corresponds to a flag bit, where the flag bit is used to characterize whether the post-hotspot routing table is valid or not,

the processor 10 is further configured to determine whether the post hot spot routing table is valid according to a flag bit corresponding to the queue when dequeuing the packet; when the post-hot point routing table is effective, matching the message in the post-hot point routing table; the sending port 20 is further configured to send the packet to an egress node corresponding to the prefix field successfully matched.

Optionally, the pre-hotspot routing table and the post-hotspot routing table are the same hotspot routing table.

Based on the same inventive concept, the embodiment of the present invention further provides a routing table updating apparatus, which includes a functional module for executing the foregoing method steps. In one possible implementation, as shown in fig. 10, the route lookup apparatus includes a receiving unit 301, a processing unit 302, and a sending unit 303.

When the routing table updating apparatus is a distribution node, the receiving unit 301 is configured to receive a packet sent by an entry node of a packet forwarding system; the message is the message of the inlet node which is not successfully matched in the preposed hot point routing table; the routing table entry of the preposed hot spot routing table comprises a prefix field and an exit port field, and the exit port field comprises a physical box number and an exit port of an exit node of the message forwarding system; a processing unit 302, configured to perform matching on the matching entry field in an allocation table according to a Longest Prefix Match (LPM) rule based on a destination network protocol IP address of the packet; the distribution table entry of the distribution table comprises a matching entry field and a search node number field, the matching entry field is a prefix corresponding to a root node of a prefix sub-tree, and the search node number field is a physical box number of a search node where the routing information of the prefix sub-tree is located.

The processing unit 302 is further configured to, if the destination IP address is successfully matched with the first matching entry field in the allocation table, obtain a physical box number of a first lookup node where routing information of a first prefix sub-tree using the first matching entry field as a prefix is located; the first searching node is a searching node of the message forwarding system; and determining that the first searching node is congested, and acquiring the routing information of the first prefix sub-tree.

A sending unit 303, configured to send routing information of the first prefix sub-tree to the ingress node, where the routing information of the first prefix sub-tree is used to update the pre-hotspot routing table; and/or the processing unit 302 is further configured to add the routing information of the first prefix sub-tree to a post-hotspot routing table stored on the distribution node; wherein a routing table entry of the post-hotspot routing table comprises the prefix field and the egress port field.

Optionally, the processing unit 302 is configured to: storing the message into a queue corresponding to the first matching item field; determining whether the total length of the messages in the queue exceeds a preset threshold value; and if the total length of the message exceeds the preset threshold value, determining that the first search node is congested.

Optionally, the queue corresponds to a flag, where the flag is used to characterize whether the post-hotspot routing table is valid, and the processing unit 302 is configured to: when the message is dequeued, determining whether the postposition hot point routing table is effective or not according to the flag bit corresponding to the queue; when the post-hot point routing table is valid, the distribution node matches the message in the post-hot point routing table; the sending unit 303 is further configured to send the packet to an egress node corresponding to the prefix field successfully matched.

Optionally, the processing unit 302 is configured to add the routing information of the first prefix sub-tree to the post-hotspot routing table, and set a value of a flag bit corresponding to the queue to a value that characterizes that the post-hotspot routing table is valid.

Various changes and specific examples in the routing lookup method in the foregoing embodiment are also applicable to the routing table updating apparatus in this embodiment and the packet forwarding device in fig. 4, and through the foregoing detailed description of the routing update method, those skilled in the art can clearly know the implementation methods of the routing table updating apparatus in this embodiment and the packet forwarding device in fig. 4, so for the brevity of the description, detailed descriptions are not repeated here.

As will be appreciated by one skilled in the art, embodiments of the present invention may be provided as a method, system, or computer program product. Accordingly, embodiments of the present invention may take the form of an entirely hardware embodiment, an entirely software embodiment or an embodiment combining software and hardware aspects. Furthermore, embodiments of 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, and the like) having computer-usable program code embodied therein.

The present application 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 will be understood that each flow and/or block of the flow diagrams and/or block diagrams, and combinations of flows and/or blocks in the flow diagrams and/or block diagrams, can be implemented by computer program instructions. These computer program instructions may be provided to a processor of a general purpose computer, special purpose computer, embedded processor, or other programmable data processing apparatus to produce a machine, such that the instructions, which execute via the processor of the computer or other programmable data processing apparatus, create means for implementing the functions specified in the flowchart flow or flows and/or block diagram block or blocks.

These computer program instructions may also be stored in a computer-readable memory that can direct a computer or other programmable data processing apparatus to function in a particular manner, such that the instructions stored in the computer-readable memory produce an article of manufacture including instruction means which implement the function specified in the flowchart flow or flows and/or block diagram block or blocks.

These computer program instructions may also be loaded onto a computer or other programmable data processing apparatus to cause a series of operational steps to be performed on the computer or other programmable apparatus to produce a computer implemented process such that the instructions which execute on the computer or other programmable apparatus provide steps for implementing the functions specified in the flowchart flow or flows and/or block diagram block or blocks.

It will be apparent to those skilled in the art that various changes and modifications may be made in the present application without departing from the spirit and scope of the application. Thus, if such modifications and variations of the present application fall within the scope of the claims of the present application and their equivalents, the present application is intended to include such modifications and variations as well.

Claims

1. A method for updating a routing table, comprising:

a distribution node of a message forwarding system receives a message sent by an inlet node of the message forwarding system; the message is a message which is successfully unmatched in a preposed hot point routing table stored on the inlet node by the inlet node; the distribution nodes are stored with distribution tables, the distribution table items of the distribution tables comprise matching item fields and search node number fields, the matching item fields are prefixes corresponding to root nodes of a prefix sub-tree, and the search node number fields are physical box numbers of search nodes where the routing information of the prefix sub-tree is located;

the distribution node performs matching of the matching item field in the distribution table according to the target network protocol IP address of the message and the principle of Longest Prefix Matching (LPM);

if the destination IP address is successfully matched with the first matching item field in the distribution table, the distribution node acquires the physical box number of a first search node where the routing information of a first prefix sub-tree using the first matching item field as a prefix is located; the first searching node is a searching node of the message forwarding system;

the distribution node determines that the first search node is congested and acquires the routing information of the first prefix sub-tree;

the distribution node sends the routing information of the first prefix sub-tree to the inlet node, and the routing information of the first prefix sub-tree is used for updating the preposed hot point routing table; and/or the distribution node adds the routing information of the first prefix sub-tree to a post-hot point routing table stored on the distribution node;

the routing table entries of the pre-hotspot routing table and the post-hotspot routing table both include a prefix field and an egress port field, and the egress port field includes a physical box number and an egress port of an egress node of the packet forwarding system.

2. The method of claim 1, wherein the allocating node determining that the first look-up node is congested comprises:

the distribution node stores the message into a queue corresponding to the first matching item field;

the distribution node determines whether the total length of the messages in the queue exceeds a preset threshold value or not;

and if the total length of the message exceeds the preset threshold value, the distribution node determines that the first search node is congested.

3. The method of claim 2, wherein the queue corresponds to a flag bit, the flag bit being used to characterize whether the post-hotspot routing table is valid, the method further comprising:

when the message is dequeued, the distribution node determines whether the post-hot point routing table is valid according to the flag bit corresponding to the queue;

and when the post-hot point routing table is effective, the distribution node matches the message in the post-hot point routing table and sends the message to an outlet node corresponding to the successfully matched prefix field.

4. The method of claim 3, wherein the allocating node adding the routing information of the first prefix sub-tree to a post-hotspot routing table stored on the allocating node, comprises:

and the distribution node adds the routing information of the first prefix subtree to the post-hot point routing table and sets the value of the flag bit corresponding to the queue as a value representing the effectiveness of the post-hot point routing table.

5. A method for route lookup, comprising:

a leaf message forwarding device of a message forwarding system receives a message;

the leaf message forwarding equipment matches in a preposed hot spot routing table stored on the leaf message forwarding equipment according to the Longest Prefix Matching (LPM) principle according to the destination network protocol IP address of the message;

if the leaf message forwarding equipment is not successfully matched in the preposed hot spot routing table, matching the matching item fields in a distribution table according to the target IP address and the LPM principle; the distribution table item of the distribution table comprises a matching item field and a core message forwarding device identification field, wherein the matching item field is a prefix corresponding to a root node of a prefix sub-tree, and the core message forwarding device identification field is an identification of the core message forwarding device where the routing information of the prefix sub-tree is located; the core message forwarding device is a core message forwarding device of the message forwarding system;

if the destination IP address is successfully matched with the first matching item field in the distribution table, the leaf message forwarding equipment acquires an identifier of first core message forwarding equipment in which routing information of a first prefix sub-tree using the first matching item field as a prefix is located;

the leaf message forwarding equipment determines that the first core message forwarding equipment is congested and acquires routing information of the first prefix sub-tree;

the leaf message forwarding equipment updates the routing information of the first prefix sub-tree to the preposed hot point routing table; and/or the leaf message forwarding equipment adds the routing information of the first prefix sub-tree to a post-positioned hot point routing table stored on the leaf message forwarding equipment;

the routing table entries of the pre-hotspot routing table and the post-hotspot routing table include a prefix field and an egress port field, and the egress port field includes an egress leaf packet forwarding device identifier and an egress port of the packet forwarding system.

6. The method of claim 5, wherein the leaf packet forwarding device determining that the core packet forwarding device is congested comprises:

the leaf message forwarding equipment stores the message into a queue corresponding to the first matching item field;

the leaf message forwarding equipment determines whether the total length of the messages in the queue exceeds a preset threshold value or not;

and if the total length of the messages exceeds the preset threshold value, the leaf message forwarding equipment determines that the first core message forwarding equipment is congested.

7. The method of claim 6, wherein the queue corresponds to a flag bit, the flag bit being used to characterize whether the post-hotspot routing table is valid, the method further comprising:

when the message is dequeued, the leaf message forwarding equipment determines whether the post hot point routing table is valid according to the flag bit corresponding to the queue;

and when the post-hot-point routing table is valid, the leaf message forwarding equipment matches the message in the post-hot-point routing table and sends the message to an exit node corresponding to the successfully-matched prefix field.

8. The method of claim 6, wherein the leaf packet forwarding device adding the routing information of the first prefix sub-tree to a post-hot-spot routing table stored on the leaf packet forwarding device, comprises:

and the leaf message forwarding equipment adds the routing information of the first prefix subtree to the post-hot point routing table, and sets the value of the flag bit corresponding to the queue as a value representing the effectiveness of the post-hot point routing table.

9. The method of any of claims 5-8, wherein the pre-hotspot routing table and the post-hotspot routing table are the same hotspot routing table.

10. A routing table updating apparatus, comprising:

a receiving unit, configured to receive a packet sent by an ingress node of a packet forwarding system; the message is the message of the inlet node which is not successfully matched in the preposed hot point routing table;

a processing unit, configured to perform matching of the matching entry field in an allocation table according to a Longest Prefix Match (LPM) principle according to a destination network protocol (IP) address of the packet; the distribution table items of the distribution table comprise matching item fields and search node number fields, the matching item fields are prefixes corresponding to root nodes of a prefix sub-tree, and the search node number fields are physical box numbers of search nodes where the routing information of the prefix sub-tree is located;

the processing unit is further configured to, if the destination IP address is successfully matched with the first matching entry field in the allocation table, obtain a physical box number of a first lookup node where routing information of a first prefix sub-tree using the first matching entry field as a prefix is located; the first searching node is a searching node of the message forwarding system; determining that the first look-up node is congested; and obtaining the routing information of the first prefix sub-tree;

a sending unit, configured to send routing information of the first prefix sub-tree to the ingress node, where the routing information of the first prefix sub-tree is used to update the pre-hotspot routing table; and/or the processing unit is further configured to add routing information of the first prefix sub-tree to a post-hotspot routing table stored on the distribution node; the routing table entries of the pre-hotspot routing table and the post-hotspot routing table both include a prefix field and an egress port field, and the egress port field includes a physical box number and an egress port of an egress node of the packet forwarding system.

11. The apparatus as defined in claim 10, wherein the processing unit is to: storing the message into a queue corresponding to the first matching item field; determining whether the total length of the messages in the queue exceeds a preset threshold value; and if the total length of the message exceeds the preset threshold value, determining that the first search node is congested.

12. The apparatus as claimed in claim 11, wherein said queue corresponds to a flag bit, said flag bit is used for characterizing whether said post-hotspot routing table is valid, said processing unit is used for: when the message is dequeued, determining whether the postposition hot point routing table is effective or not according to the flag bit corresponding to the queue; when the post-hot point routing table is valid, the distribution node matches the message in the post-hot point routing table;

and the sending unit is also used for sending the message to the outlet node corresponding to the prefix field successfully matched.

13. The apparatus of claim 12, wherein the processing unit is configured to add routing information of the first prefix sub-tree to the post-hotspot routing table, and to set a value of a flag bit corresponding to the queue to a value that characterizes the post-hotspot routing table as valid.

14. An allocation node, comprising:

a receiving port, configured to receive a packet sent by an ingress node of a packet forwarding system; the message is the message of the inlet node which is not successfully matched in the preposed hot point routing table;

the processor is used for matching the matching item fields in the distribution table according to the IP address of the destination network protocol of the message and the principle of Longest Prefix Matching (LPM); the distribution table items of the distribution table comprise matching item fields and search node number fields, the matching item fields are prefixes corresponding to root nodes of a prefix sub-tree, and the search node number fields are physical box numbers of search nodes where the routing information of the prefix sub-tree is located;

the processor is further configured to, if the destination IP address is successfully matched with the first matching entry field in the allocation table, obtain a physical box number of a first lookup node where routing information of a first prefix sub-tree using the first matching entry field as a prefix is located; the first searching node is a searching node of the message forwarding system; determining that the first look-up node is congested; and obtaining the routing information of the first prefix sub-tree;

a sending port, configured to send routing information of the first prefix sub-tree to the ingress node, where the routing information of the first prefix sub-tree is used to update the pre-hotspot routing table; and/or the processor is further configured to add routing information of the first prefix sub-tree to a post-hotspot routing table stored on the distribution node; the routing table entries of the pre-hotspot routing table and the post-hotspot routing table both include a prefix field and an egress port field, and the egress port field includes a physical box number and an egress port of an egress node of the packet forwarding system.

15. The distribution node of claim 14, wherein the processor is configured to: storing the message into a queue corresponding to the first matching item field; determining whether the total length of the messages in the queue exceeds a preset threshold value; and if the total length of the message exceeds the preset threshold value, determining that the first search node is congested.

16. The distribution node of claim 15, wherein the queue corresponds to a flag bit, the flag bit being used to characterize whether the post-hotspot routing table is valid, the processor being configured to: when the message is dequeued, determining whether the postposition hot point routing table is effective or not according to the flag bit corresponding to the queue; when the post-hot point routing table is valid, the distribution node matches the message in the post-hot point routing table;

and the sending port is also used for sending the message to the outlet node corresponding to the prefix field successfully matched.

17. The distribution node of claim 16, wherein the processor is configured to add routing information for the first prefix sub-tree to the post-hotspot routing table and to set a value of a flag bit corresponding to the queue to a value that characterizes the post-hotspot routing table as valid.

18. A leaf message forwarding device, comprising:

a receiving port for receiving a message;

the processor is used for matching in a preposed hot spot routing table stored on the leaf message forwarding equipment according to the Longest Prefix Matching (LPM) principle according to the destination network protocol IP address of the message;

the processor is further configured to, if the matching is not successful in the pre-hotspot routing table, perform matching of the matching entry field in an allocation table according to the LPM principle and according to the destination IP address; the distribution table item of the distribution table comprises a matching item field and a core message forwarding device identification field, wherein the matching item field is a prefix corresponding to a root node of a prefix sub-tree, and the core message forwarding device identification field is an identification of the core message forwarding device where the routing information of the prefix sub-tree is located; the core message forwarding device is a core message forwarding device of the message forwarding system; if the destination IP address is successfully matched with the first matching item field in the distribution table, acquiring the identifier of a first core message forwarding device in which the routing information of a first prefix sub-tree using the first matching item field as a prefix is located; determining that the first core packet forwarding device is congested; and obtaining the routing information of the first prefix sub-tree;

the processor is further configured to update routing information of the first prefix sub-tree to the pre-hotspot routing table; and/or the routing information of the first prefix sub-tree is also used for adding the routing information of the first prefix sub-tree into a post-positioned hot point routing table stored on the leaf message forwarding equipment; the routing table entries of the pre-hotspot routing table and the post-hotspot routing table both include a prefix field and an egress port field, and the egress port field includes an egress leaf packet forwarding device identifier and an egress port of the packet forwarding system.

19. The leaf message forwarding device of claim 18, wherein the processor is configured to store the message in a queue corresponding to the first matching entry field; determining whether the total length of the messages in the queue exceeds a preset threshold value; and if the total length of the message exceeds the preset threshold value, determining that the first core message forwarding equipment is congested.

20. The leaf message forwarding device of claim 19 wherein the leaf message forwarding device further comprises a sending port, the queue corresponds to a flag bit, the flag bit is used to indicate whether the post hot spot routing table is valid,

the processor is further configured to determine whether the post hot spot routing table is valid according to a flag bit corresponding to the queue when dequeuing the packet; when the post-hot point routing table is effective, matching the message in the post-hot point routing table;

21. The leaf packet forwarding device of claim 20, wherein the processor is configured to add routing information of the first prefix sub-tree to the post-hot-point routing table, and set a value of a flag bit corresponding to the queue to a value that characterizes the post-hot-point routing table as valid.

22. The leaf packet forwarding device of any one of claims 18-21, wherein the pre-hotspot routing table and the post-hotspot routing table are the same hotspot routing table.