CN113691446A

CN113691446A - Method and device for sending message

Info

Publication number: CN113691446A
Application number: CN202010427453.8A
Authority: CN
Inventors: 李臣习; 兰如钦; 刘国权; 李海潮; 胡志波
Original assignee: Huawei Technologies Co Ltd
Current assignee: Huawei Technologies Co Ltd
Priority date: 2020-05-19
Filing date: 2020-05-19
Publication date: 2021-11-23
Anticipated expiration: 2040-05-19
Also published as: WO2021233168A1; CN113691446B

Abstract

The embodiment of the application provides a message sending method and device, relates to the field of communication, and can shorten the length of a label stack of a message. The method comprises the following steps: a first network node determines that a first forwarding path for forwarding a packet is unavailable; in response to determining that the first forwarding path is unavailable, the first network node determines a second forwarding path for forwarding the packet; the first network node adds a label stack corresponding to a second forwarding path in the message, wherein the label stack comprises a node label of the second network node, the label stack does not comprise a link label of a link between the first network node and the second network node, or the label stack does not comprise a node label of a network node between the first network node and the second network node, the shortest path between the first network node and the second network node does not comprise the first forwarding path, and the second network node is a network node on the second forwarding path; and the first network node sends the message added with the label stack.

Description

Method and device for sending message

Technical Field

The present application relates to the field of communications, and in particular, to a method and an apparatus for sending a packet.

Background

When a link failure occurs in a network, a route stored by a network node (i.e., a network device such as a Router (RT)) needs to be converged. An Interior Gateway Protocol (IGP) or Border Gateway Protocol (BGP) may be run in the network. As shown in fig. 1, when a link between RT1 and RT7 fails, the route from RT1 to RT7 converges from original RT1- > RT7 to RT1- > RT2- > RT7, the route from RT2 to RT7 converges from original RT2- > RT1- > RT7 to RT2- > RT3- > RT7, and so on until the route converges to RT 7. In the above convergence process, if there is a difference in convergence performance between network nodes, a problem of a convergence loop (convergence micro-loop) may result. For example, if the convergence rate of RT2 is slower than that of RT1, a loop is formed between RT1 and RT2, that is, RT1 forwards the message to be sent to RT7 to RT2, and since RT2 converges slowly, RT2 receives the message sent by RT1, and then forwards the message according to the traffic forwarding path before convergence (i.e., path RT2-RT1-RT7), that is, re-sends the message to RT1, thereby forming a loop.

In the related art, a Segment Routing (SR) technique may be used to solve the problem of the convergence loop. As shown in fig. 2, assuming that a link between RT1 and RT7 fails, after RT1 converges, a Label Switching Path (LSP) may be determined again for a packet that originally needs to be forwarded through the failed link according to a forwarding requirement, and a label stack corresponding to the LSP is added to the packet to be forwarded. The label stack includes link information, such as a link Segment Identification (SID), that the LSP passes through. The label stack may be, for example, {1001,1002,1003,1004,1005}, where 1001 is the neighbor segment label (Adj-SID) between RT2 and RT3, Adj-SID may also be referred to as the link label, 1002 is the link label between RT3 and RT4, 1003 is the link label between RT4 and RT5, 1004 is the link label between RT5 and RT6, and 1005 is the link label between RT6 and RT 7. In this way, traffic forwarded to RT7 via RT1 may be forwarded according to the label stack pushed by RT1 without relying on convergence by other network nodes (e.g., RT2), thereby avoiding convergence loop problems.

However, limited by hardware capabilities, the label stack capability of each network node is limited, i.e., the number of layers of labels that can be pushed in the label stack of each network node is limited (e.g., 2, 3, 6, or 10 layers, etc.). The longer the forwarding path is, the longer the label stack (which may also be referred to as deeper), and when the length of the label stack exceeds the label stack capability of the network node, the label stack cannot be pushed, that is, the packet cannot be forwarded according to the label stack. For example, as shown in fig. 2, when the label stack corresponding to the forwarding path includes a 5-layer label, and the label stack capability of the RT1 is a 3-layer label, the RT1 cannot forward the packet according to the label stack.

Disclosure of Invention

Embodiments of the present application provide a method and an apparatus for sending a packet, which can shorten a length of a label stack of a packet, and can support more scenarios (for example, scenarios that can support a longer forwarding path) under the condition that a label stack capability of a network device is not changed.

In a first aspect, an embodiment of the present application provides a method for sending a packet, including: a first network node determines that a first forwarding path for forwarding a packet is unavailable; in response to determining that the first forwarding path is unavailable, the first network node determines a second forwarding path for forwarding the packet; the first network node adds a label stack corresponding to a second forwarding path in the message, wherein the label stack comprises a node label of the second network node, the label stack does not comprise a link label of a link between the first network node and the second network node, or the label stack does not comprise a node label of a network node between the first network node and the second network node, the shortest path between the first network node and the second network node does not comprise the first forwarding path, and the second network node is a network node on the second forwarding path; and the first network node sends the message added with the label stack.

Based on the method provided by the embodiment of the application, the packet can be forwarded to the second network node according to the node label of the second network node in the label stack, one or more link labels or node labels between the first network node and the second network node do not need to be added in the label stack, the length of the label stack can be shortened, and under the condition that the label stack capability of the network device is not changed, more scenes (for example, a scene of a longer forwarding path can be supported).

In one possible implementation, the unavailability of the first forwarding path for forwarding the packet includes at least one of: the minimum link cost of the first forwarding path is greater than or equal to a preset threshold; or the first forwarding path fails; or the first forwarding path is congested.

In a possible implementation manner, the second network node is a network node that is farthest away from the first network node among the M network nodes, the M network nodes are respectively located on the second forwarding paths, the shortest path from the first network node to each network node among the M network nodes respectively does not include the first forwarding path, and M is an integer greater than or equal to 1. It can be understood that the second network node is a network node farthest from the first network node among the M network nodes, that is, the second network node is a network node that is separated from the first network node by the maximum number of network node hops among the M network nodes, and since the label stack does not include a link label or a node label of a link between the first network node and the second network node, the length of the label stack can be shortened to a greater extent.

In one possible implementation, the second forwarding path includes a third network node, and the third network node is a next-hop network node of the second network node in the second forwarding path, and the method further includes: the first network node determining whether a minimum link cost between the second network node and the third network node is greater than a minimum link cost between the first network node and the third network node; the label stack further comprises a link label between the second network node and the third network node when the minimum link overhead between the second network node and the third network node is greater than the minimum link overhead between the first network node and the third network node. This is because when the minimum link cost between the second network node and the third network node is greater than the minimum link cost between the first network node and the third network node, the direct link between the second network node and the third network node is not the shortest path between the second network node and the third network node, and since the second network node may not have converged or has not learned that a link in the network has failed, the shortest path between the second network node and the third network node autonomously determined by the second network node may include a failed link, resulting in a loop problem. Therefore, a link label between the second network node and the third network node needs to be added to the label stack, so that the second network node can send the packet to the third network node according to the link label between the second network node and the third network node, and the problem of a loop is avoided.

In one possible implementation, the second forwarding path includes a third network node, and the third network node is a next-hop network node of the second network node in the second forwarding path, and the method further includes: the first network node determines whether the minimum link cost between the second network node and the third network node is less than or equal to the minimum link cost between the first network node and the third network node; the label stack does not include a link label between the second network node and the third network node when the minimum link overhead between the second network node and the third network node is less than or equal to the minimum link overhead between the first network node and the third network node. This is because when the minimum link cost between the second network node and the third network node is less than or equal to the minimum link cost between the first network node and the third network node, the direct link between the second network node and the third network node is the shortest path between the second network node and the third network node, and the second network node can autonomously (i.e., according to its own path plan) send the packet to the third network node, so that it is not necessary to add a link label between the second network node and the third network node in the label stack.

In one possible implementation, the second forwarding path includes a fourth network node, and the fourth network node is a next-hop network node of a third network node in the second forwarding path, and the method further includes: the first network node determining whether a minimum link cost between the third network node and the fourth network node is greater than a minimum link cost between the first network node and the fourth network node; when the minimum link overhead between the third network node and the fourth network node is greater than the minimum link overhead between the first network node and the fourth network node, the label stack further includes a link label between the third network node and the fourth network node.

In one possible implementation, the second forwarding path includes a fourth network node, and the fourth network node is a next-hop network node of a third network node in the second forwarding path, and the method further includes: the first network node determines whether the minimum link cost between the third network node and the fourth network node is less than or equal to the minimum link cost between the first network node and the fourth network node; when the minimum link overhead between the third network node and the fourth network node is less than or equal to the minimum link overhead between the first network node and the fourth network node, the label stack does not include a link label between the third network node and the fourth network node.

In one possible implementation, when the label stack does not include a link label between the second network node and the third network node, and the label stack includes a link label between the third network node and the fourth network node, the label stack further includes a node label of the third network node. This is because the second network node may not be able to identify the link label between the third network node and the fourth network node, and when the packet is forwarded to the second network node, the second network node may not be able to determine how to send the packet according to the link label between the third network node and the fourth network node. Therefore, a node label of the third network node needs to be added to the label stack, so that the second network node sends the packet to the third network node, and the third network node forwards the packet to the fourth network node according to the link label between the third network node and the fourth network node.

In a second aspect, an embodiment of the present application provides a first network node, including: a determining unit, configured to determine that a first forwarding path for forwarding a packet is unavailable; the determining unit is further used for determining a second forwarding path for forwarding the message in response to determining that the first forwarding path is unavailable; a processing unit, configured to add a label stack corresponding to a second forwarding path in the packet, where the label stack includes a node label of the second network node, and the label stack does not include a link label of a link between the first network node and the second network node, or the label stack does not include a node label of a network node between the first network node and the second network node, a shortest path between the first network node and the second network node does not include the first forwarding path, and the second network node is a network node on the second forwarding path; and the sending unit is used for sending the message added with the label stack.

In a possible implementation manner, the second network node is a network node that is farthest away from the first network node among the M network nodes, the M network nodes are respectively located on the second forwarding paths, the shortest path from the first network node to each network node among the M network nodes respectively does not include the first forwarding path, and M is an integer greater than or equal to 1.

In a possible implementation manner, the second forwarding path includes a third network node, and the third network node is a next-hop network node of the second network node in the second forwarding path, and the determining unit is further configured to: determining whether a minimum link cost between the second network node and the third network node is greater than a minimum link cost between the first network node and the third network node; the label stack further comprises a link label between the second network node and the third network node when the minimum link overhead between the second network node and the third network node is greater than the minimum link overhead between the first network node and the third network node.

In a possible implementation manner, the second forwarding path includes a third network node, and the third network node is a next-hop network node of the second network node in the second forwarding path, and the determining unit is further configured to: determining whether a minimum link cost between the second network node and the third network node is less than or equal to a minimum link cost between the first network node and the third network node; the label stack does not include a link label between the second network node and the third network node when the minimum link overhead between the second network node and the third network node is less than or equal to the minimum link overhead between the first network node and the third network node.

In a possible implementation manner, the second forwarding path includes a fourth network node, and the fourth network node is a next-hop network node of a third network node in the second forwarding path, and the determining unit is further configured to: determining whether a minimum link cost between the third network node and the fourth network node is greater than a minimum link cost between the first network node and the fourth network node; when the minimum link overhead between the third network node and the fourth network node is greater than the minimum link overhead between the first network node and the fourth network node, the label stack further includes a link label between the third network node and the fourth network node.

In a possible implementation manner, the second forwarding path includes a fourth network node, and the fourth network node is a next-hop network node of a third network node in the second forwarding path, and the determining unit is further configured to: determining whether a minimum link cost between the third network node and the fourth network node is less than or equal to a minimum link cost between the first network node and the fourth network node; when the minimum link overhead between the third network node and the fourth network node is less than or equal to the minimum link overhead between the first network node and the fourth network node, the label stack does not include a link label between the third network node and the fourth network node.

In one possible implementation, when the label stack does not include a link label between the second network node and the third network node, and the label stack includes a link label between the third network node and the fourth network node, the label stack further includes a node label of the third network node.

In a third aspect, the present application also provides a communication device, which may be a first network node or a chip. The communication device comprises a processor for implementing any one of the methods provided by the first aspect above. The communication device may also include a memory for storing program instructions and data, which may be memory integrated within the communication device or off-chip memory disposed external to the communication device. The memory is coupled to the processor, and the processor can call and execute the program instructions stored in the memory, so as to implement any one of the methods provided by the first aspect. The memory may be located in the processor or the memory may be located separate from the processor. The communication apparatus may further include a transceiver (communication interface/interface circuit) for the communication apparatus to communicate with other devices, for example, a next hop network node of the first network node.

In a fourth aspect, the present application provides a computer-readable storage medium comprising instructions which, when executed on a computer, cause the computer to perform any one of the methods provided by the first aspect above.

In a fifth aspect, the present application provides a computer program product comprising instructions which, when run on a computer, cause the computer to perform any one of the methods provided by the first aspect above.

In a sixth aspect, the present application provides a chip system, where the chip system includes a processor and may further include a memory, and is configured to implement any one of the methods provided in the first aspect. The chip system may be formed by a chip, and may also include a chip and other discrete devices.

A seventh aspect of the present application provides a system for sending a packet, including a first network node and a second network node, where: the first network node is used for determining that a first forwarding path for forwarding the message is unavailable; determining a second forwarding path for forwarding the message in response to determining that the first forwarding path is unavailable; adding a label stack corresponding to the second forwarding path in the message; the label stack comprises a node label of the second network node, and the label stack does not comprise a link label of a link between the first network node and the second network node, or the label stack does not comprise a node label of a network node between the first network node and the second network node, the shortest path between the first network node and the second network node does not comprise a first forwarding path, and the second network node is a network node on the second forwarding path; sending the message added with the label stack to a second network node; and the second network node receives the message added with the label stack and sends the message according to the label stack.

Drawings

FIG. 1 is a diagram of a network architecture in the prior art;

FIG. 2 is a diagram illustrating another prior art network architecture;

fig. 3 is a schematic diagram of a network architecture according to an embodiment of the present application;

fig. 4 is a schematic structural diagram of a first network node according to an embodiment of the present application;

fig. 5 is a schematic signal diagram applicable to a method for sending a message according to an embodiment of the present application;

fig. 6 is a schematic diagram of another network architecture provided in the embodiment of the present application;

fig. 7 is a schematic diagram of a shortest path tree of RT1 according to an embodiment of the present disclosure;

fig. 8 is a schematic diagram of another network architecture provided in the embodiment of the present application;

fig. 9 is a schematic diagram of another network architecture provided in the embodiment of the present application;

fig. 10 is a schematic structural diagram of another first network node according to an embodiment of the present application.

Detailed Description

The embodiment of the present application provides a method for sending a packet, which may be applied to an autonomous network system, for example, to an IGP network. The method can be applied to situations such as link failure or congestion in the IGP network.

Fig. 3 is a schematic diagram of a network architecture according to an embodiment of the present application. The network architecture may include a first network node, a sixth network node, and other network nodes (e.g., network node 1-network node 5).

When the first network node determines that a first forwarding path for forwarding the packet is not available, the first network node determines a second forwarding path for forwarding the packet in response to determining that the first forwarding path is not available. For example, the first forwarding path may include a link between the first network node and the sixth network node, and when the link fails, the first network node determines a second forwarding path for forwarding the packet, and the second forwarding path may include a link between the forwarding nodes 1 to 5, that is, the first network node may forward the packet to the sixth network node through the forwarding nodes 1 to 5. The first network node may add a label stack corresponding to the second forwarding path to the packet, so that the forwarding nodes 1 to 5 may forward the packet according to the label stack.

Limited by hardware capability, the label stack capability of each network node is limited, that is, the number of layers of labels that can be pushed in the label stack of each network node is limited (for example, the number of labels that can be pushed is 2, 3, 6, or 10, that is, 2 labels, 3 labels, 6 labels, or 10 labels can be pushed). The longer the forwarding path is, the longer (deeper) the label stack will be, and when the length of the label stack exceeds the label stack capability of the network node, the network node will not be able to correctly process the packet containing the label stack.

The embodiment of the application provides a method for sending a message, which comprises the following steps: a first network node determines that a first forwarding path for forwarding a packet is unavailable; in response to determining that the first forwarding path is unavailable, the first network node determines a second forwarding path for forwarding the packet; the first network node adds a label stack corresponding to a second forwarding path in the message, wherein the label stack comprises a node label of the second network node, the label stack does not comprise a link label of a link between the first network node and the second network node, or the label stack does not comprise a node label of a node between the first network node and the second network node, the shortest path between the first network node and the second network node does not comprise the first forwarding path, and the second network node is a node on the second forwarding path; and the first network node sends the message added with the label stack.

The first network node in fig. 3 in this embodiment of the application may be implemented by a device, or may be a functional module in a device, which is not specifically limited in this embodiment of the application. It is understood that the above functions may be network elements in a hardware device, or software functions running on dedicated hardware, or virtualization functions instantiated on a platform (e.g., a cloud platform), or a system-on-chip. In the embodiment of the present application, the chip system may be composed of a chip, and may also include a chip and other discrete devices.

For example, the apparatus for implementing the functions of the first network node provided in the embodiments of the present application may be implemented by the apparatus 400 in fig. 4. Fig. 4 is a schematic hardware structure diagram of an apparatus 400 according to an embodiment of the present disclosure. The apparatus 400 includes at least one processor 401 for implementing the functions of the first network node provided in the embodiments of the present application. Also included in the apparatus 400 is a bus 402 and at least one communication interface 404. The apparatus 400 may also include a memory 403.

In the embodiment of the present application, the processor may be a Central Processing Unit (CPU), a general purpose processor, a Network Processor (NP), a Digital Signal Processor (DSP), a microprocessor, a microcontroller, a Programmable Logic Device (PLD), or any combination thereof. The processor may also be any other means having a processing function such as a circuit, device or software module.

Bus 402 may be used to transfer information between the above components.

A communication interface 404 for communicating with other devices or communication networks, such as ethernet, Radio Access Network (RAN), Wireless Local Area Network (WLAN), etc. The communication interface 404 may be an interface, a circuit, a transceiver, or other device capable of implementing communication, and is not limited in this application. The communication interface 404 may be coupled to the processor 401. The coupling in the embodiments of the present application is an indirect coupling or a communication connection between devices, units or modules, and may be an electrical, mechanical or other form for information interaction between the devices, units or modules.

In the embodiments of the present application, the memory may be a read-only memory (ROM) or other types of static storage devices that can store static information and instructions, a Random Access Memory (RAM) or other types of dynamic storage devices that can store information and instructions, an electrically erasable programmable read-only memory (EEPROM), a compact disc read-only memory (CD-ROM) or other optical disc storage, optical disc storage (including compact disc, laser disc, optical disc, digital versatile disc, blu-ray disc, etc.), magnetic disk storage media or other magnetic storage devices, or any other medium that can be used to carry or store desired program code in the form of instructions or data structures and that can be accessed by a computer, but is not limited to such. The memory may be stand alone or coupled to the processor, such as through bus 402. The memory may also be integral to the processor.

The memory 403 is used for storing program instructions, and can be controlled by the processor 401 to execute, so as to implement the methods provided by the following embodiments of the present application. Processor 401 is configured to call and execute instructions stored in memory 403 to implement the methods provided by the embodiments described below in the present application.

Optionally, the computer-executable instructions in the embodiments of the present application may also be referred to as application program codes, which are not specifically limited in the embodiments of the present application.

Optionally, the memory 403 may be included in the processor 401.

In particular implementations, processor 401 may include one or more CPUs such as CPU0 and CPU1 in fig. 4 as an example.

In particular implementations, apparatus 400 may include multiple processors, such as processor 401 and processor 405 in fig. 4, for example, as an example. Each of these processors may be a single-core (single-CPU) processor or a multi-core (multi-CPU) processor. A processor herein may refer to one or more devices, circuits, and/or processing cores for processing data (e.g., computer program instructions).

The apparatus 400 may be a general-purpose device or a special-purpose device. In a particular implementation, the first network node 400 may be a router, a switching device (switch) supporting a routing protocol, a bridge, a gateway, or a device having a similar structure as in fig. 4. The embodiment of the present application does not limit the type of the apparatus 400.

The technical solutions in the embodiments of the present application will be described below with reference to the drawings in the embodiments of the present application. In the embodiments of the present application, terms such as "first" and "second" are used to distinguish the same or similar items having substantially the same function and action. Those skilled in the art will appreciate that the terms "first," "second," etc. do not denote any order or quantity, nor do the terms "first," "second," etc. denote any order or importance.

For convenience of understanding, the method for sending a message provided in the embodiments of the present application is specifically described below with reference to the accompanying drawings.

As shown in fig. 5, an embodiment of the present application provides a method for sending a message, including:

501. the first network node determines that a first forwarding path for forwarding the packet is unavailable.

Wherein the first forwarding path being unavailable comprises at least one of: the minimum link cost of the first forwarding path is greater than or equal to a preset threshold; or, the first forwarding path fails; alternatively, the first forwarding path is congested.

502. In response to determining that the first forwarding path is unavailable, the first network node determines a second forwarding path for forwarding the packet.

For example, assuming that the first forwarding path includes a direct link between the first network node and the sixth network node, when the first network device determines that the direct link between the first network node and the sixth network node has a fault, fault convergence (simply referred to as convergence) may be performed. Convergence refers to that after discovering a link failure, the first network node updates its own routing table or Shortest Path Tree (SPT) according to a related algorithm (e.g., Dijkstra algorithm) to eliminate the influence of the failed link on the subsequent traffic forwarding process. The converged first network node may re-determine a forwarding path, that is, a second forwarding path, for the packet to be forwarded to the sixth network node. Alternatively, the forwarding path may also be referred to as a convergence path, and the present application is not limited thereto. The message to be sent to the sixth network node may be a message received by the first network node from another network node, or a message generated by the first network node, which is not limited in the present application.

For example, as shown in fig. 6, it is assumed that a network is provided with 7 routers (R1 to R7 in fig. 6), each router is a network node, taking the first network node as RT1 and the sixth network node as RT7 as an example, when RT1 determines that a direct link between RT1 and RT7 fails, a forwarding path, that is, a second forwarding path, may be determined again for a packet (packet) to be forwarded to RT 7. That is, the direct link between the RT1 and the RT7 is abandoned, and the packet is forwarded to the RT7 through other network nodes. For example, the second forwarding path determined by RT1 may be RT1- > RT2- > RT3- > RT4- > RT5- > RT6- > RT 7.

In addition, after the first network node determines that a link other than the direct link of the first network node fails, the first network node may also perform failure convergence, and determine a second forwarding path for a message that originally needs to pass through the failed link on the first network node. For example, as shown in fig. 6, taking the first network node as RT2, the sixth network node as RT7, and the failed link as a link between RT1 and RT7 as an example, when RT2 determines that a direct link between RT1 and RT7 fails, a forwarding path (second forwarding path) may be determined again for a packet to be forwarded to RT 7. Illustratively, the second forwarding path may be RT2- > RT3- > RT4- > RT5- > RT6- > RT 7.

503. And the first network node adds a label stack corresponding to the second forwarding path in the message.

The label stack includes a node label of the second network node, and the label stack does not include a link label of a link between the first network node and the second network node, or the label stack does not include a node label of a node between the first network node and the second network node, the shortest path between the first network node and the second network node does not include the first forwarding path, and the second network node is a node on the second forwarding path.

In one possible design, the second network node is a network node that is farthest away from the first network node among the M network nodes, the M network nodes are respectively located on the second forwarding paths, and the shortest path from the first network node to each network node among the M network nodes respectively does not include the first forwarding path, and M is an integer greater than or equal to 1.

Since the shortest paths between the first network node and the M network nodes, respectively, do not comprise the first forwarding path, the M network nodes are network nodes that are not affected by the unavailable first forwarding path. The second network node is a network node farthest from the first network node among the M network nodes, that is, the second network node is a network node that is the most distant from the first network node among the M network nodes by the hop count of the network node.

Illustratively, still as shown in fig. 6, taking the first network node as RT1, the sixth network node as RT7, and the first forwarding path includes a direct link between RT1 and RT7, the M network nodes may include RT2, RT3, and RT 4. This is because for RT2, no matter whether the direct link of RT1 to RT7 fails, the shortest path of RT1 to RT2 is unaffected, being RT1- > RT 2. For RT3, no matter whether the direct link from RT1 to RT7 fails, the shortest path from RT1 to RT3 is unaffected, being RT1- > RT2- > RT 3. For RT4, no matter whether the direct link from RT1 to RT7 fails, the shortest path from RT1 to RT4 is unaffected, and is RT1- > RT2- > RT3- > RT 4. Among RT2, RT3, and RT4, RT4 is farthest from RT1, i.e., RT4 is two hops away from RT1, the number of network node hops is the largest, so the second network node may be RT 4.

Alternatively, the M network nodes may be considered to include all network nodes on the edge that does not include the failed link in the shortest path tree before convergence of the first network node, and the second network node may be a leaf network node of the edge that does not include the failed link. Illustratively, as shown in fig. 7, for the shortest path tree corresponding to RT1 before fault convergence, the shortest path tree includes two edges, root network nodes of the two edges are both RT1, leaf network nodes of the two edges are RT4 and RT5, respectively, since the edge whose leaf network node is RT4 does not include a fault link, RT1 may determine that M network nodes include RT2, RT3, and RT4, and the second network node is RT 4.

After the first network node determines the second network node, the node label of the second network node may be added to (i.e., pushed to) the label stack. In this way, the packet can be forwarded to the second network node according to the node label of the second network node without pressing one or more link labels or node labels between the first network node and the second network node in the label stack, so that the purpose of shortening the label stack can be achieved.

Further, if the second forwarding path further includes other network nodes after the second network node, the first network node may start hop-by-hop probing from the second network node to determine whether the label stack needs to include other link labels or node labels.

Optionally, if the second forwarding path includes a third network node, where the third network node is a next-hop network node of the second network node in the second forwarding path, the first network node may determine whether the minimum link cost between the second network node and the third network node is less than the sum of the minimum link cost between the first network node and the third network node and the minimum link cost between the first network node and the second network node. The minimum link cost between the second network node and the third network node refers to the minimum cost of a direct link between the second network node and the third network node, the minimum link cost between the first network node and the third network node refers to the cost of all links included in the shortest path between the first network node and the third network node, and the minimum link cost between the first network node and the second network node refers to the cost of all links included in the shortest path between the first network node and the second network node.

Since the minimum link overhead between the first network node and the second network node is greater than 0, whether the minimum link overhead between the second network node and the third network node is less than the sum of the minimum link overhead between the first network node and the third network node and the minimum link overhead between the first network node and the second network node can be simplified to whether the minimum link overhead between the second network node and the third network node is less than or equal to the minimum link overhead between the first network node and the third network node. In this way, the first network node may determine whether the minimum link cost between the second network node and the third network node is less than or equal to the minimum link cost between the first network node and the third network node (or the first network node may determine whether the minimum link cost between the second network node and the third network node is greater than the minimum link cost between the first network node and the third network node), which simplifies the operation process and saves the operation cost.

The label stack does not include a link label between the second network node and the third network node when the minimum link overhead between the second network node and the third network node is less than or equal to the minimum link overhead between the first network node and the third network node. This is because when the minimum link cost between the second network node and the third network node is less than or equal to the minimum link cost between the first network node and the third network node, the direct link between the second network node and the third network node is the shortest path between the second network node and the third network node, and the second network node can autonomously (i.e., according to its own path plan) send the packet to the third network node, so that it is not necessary to add a link label between the second network node and the third network node in the label stack.

The label stack further comprises a link label between the second network node and the third network node when the minimum link overhead between the second network node and the third network node is greater than the minimum link overhead between the first network node and the third network node. This is because when the minimum link cost between the second network node and the third network node is greater than the minimum link cost between the first network node and the third network node, the direct link between the second network node and the third network node is not the shortest path between the second network node and the third network node, and since the second network node may not have converged or has not learned that a link in the network has failed, the shortest path between the second network node and the third network node autonomously determined by the second network node may include a failed link, resulting in a loop problem. Therefore, a link label between the second network node and the third network node needs to be added to the label stack, so that the second network node can send the packet to the third network node according to the link label between the second network node and the third network node, and the problem of a loop is avoided.

Illustratively, as shown in fig. 8, taking the first network node as RT1, the second network node as RT4, and the third network node as RT5 as an example, if the link overhead of the direct link between RT4 and RT5 is 1000, and the minimum link overhead between RT1 and RT5 is 30 (before network convergence, the shortest path between RT1 and RT5 may be RT1- > RT7- > RT6- > RT5), at this time the direct link between RT4 and RT5 is not the shortest path between RT4 and RT5, when the packet is forwarded to RT4, since RT4 may not have converged or yet has learned that the link between RT1 and RT7 failed, therefore, RT4 may forward the packet through RT4- > RT3- > RT2- > RT1- > RT7 (the minimum link cost of the forwarding path is less than 1000), so that a loop is created between RT3 and RT4, i.e., RT3 forwards the packet to RT4, RT4 forwards the packet to RT 3. Therefore, a link label between the RT4 and the RT5 needs to be added to the label stack, so that the RT4 can send the packet to the RT5 according to the link label between the RT4 and the RT5, thereby avoiding the loop problem.

Optionally, if the second forwarding path further includes a fourth network node, where the fourth network node is a next-hop network node of the third network node in the second forwarding path, the first network node determines whether a minimum link cost between the third network node and the fourth network node is greater than a minimum link cost between the first network node and the fourth network node (or the first network node determines whether a minimum link cost between the third network node and the fourth network node is less than or equal to a minimum link cost between the first network node and the fourth network node). The minimum link cost between the third network node and the fourth network node is the minimum cost of a direct link between the third network node and the fourth network node, and the minimum link cost between the first network node and the fourth network node is the cost of all links included in the shortest path between the first network node and the fourth network node.

The label stack does not include a link label between the third network node and the fourth network node when the minimum link overhead between the third network node and the fourth network node is less than or equal to the minimum link overhead between the first network node and the fourth network node. The label stack further comprises a link label between the third network node and the fourth network node when the minimum link overhead between the third network node and the fourth network node is greater than the minimum link overhead between the first network node and the fourth network node.

Optionally, if the label stack does not include a node label between the second network node and the third network node, but includes a link label between the third network node and the fourth network node, the label stack may further include a node label of the third network node. This is because the second network node may not be able to identify the link label between the third network node and the fourth network node, and when the packet is forwarded to the second network node, the second network node may not be able to determine how to send the packet according to the link label between the third network node and the fourth network node. Therefore, a node label of the third network node needs to be added to the label stack, so that the second network node sends the packet to the third network node, and the third network node forwards the packet to the fourth network node according to the link label between the third network node and the fourth network node.

Optionally, if there is a fifth network node, which is a next-hop network node of the fourth network node in the second forwarding path, it may be determined whether the label stack includes a link label between the fourth network node and the fifth network node, and so on until a last-hop network node (e.g., a sixth network node) in the second forwarding path is detected. The specific process may refer to the related description above, and is not described herein again.

The following describes a generation process of a label stack with reference to a specific scenario.

In some embodiments, as shown in fig. 6, taking the first network node as RT1 as an example, RT1 determines the second network node as RT4 and may push the node label of RT4 onto the label stack. RT1 may then begin hop-by-hop probing from RT4, determining whether the minimum link overhead between RT4 and RT5 satisfies equation (1):

RT4->RT5(cost)<RT4->RT1(cost)+RT1->RT5(cost)(1)

wherein RT4- > RT5(cost) represents the minimum link overhead between RT4 and RT5, that is, the minimum overhead of a direct link between RT4 and RT5, which may be determined by RT1 based on the routing information before convergence; RT4- > RT1(cost) represents the minimum link cost between RT4 and RT1, i.e., the cost of the link comprised by the shortest path between RT4 and RT1, and the minimum link cost between RT4 and RT1 is determined by RT1 based on the routing information before convergence; RT1- > RT5(cost) represents the minimum link overhead between RT1 and RT5, i.e. the overhead of the link comprised by the shortest path between RT1 and RT 5; and the minimum link overhead between RT1 and RT5 is determined by RT1 based on the routing information before convergence.

Since RT4- > RT1(cost) is greater than 0 in equation (1), equation (1) can simplify equation (2):

RT4->RT5(cost)<＝RT1->RT5(cost) (2)

if equation (2) is satisfied, the link label between RT4 and RT5 is not pushed in the label stack. If equation (2) is not satisfied, the link label between RT4 and RT5 is pushed in the label stack.

As shown in fig. 6, the minimum link overhead between RT4 and RT5 is 10, RT1 determines from the path information before convergence that the shortest path between RT1 and RT5 is RT1- > RT7- > RT6- > RT5, that is, the minimum link overhead between RT1 and RT5 includes the minimum overhead of the direct link between RT1 and RT7, the minimum overhead of the direct link between RT7 and RT6, and the minimum overhead of the direct link between RT6 and RT5, that is, the minimum link overhead between RT1 and RT5 is 10+10+10 ═ 30, 10< 30, equation (2) is satisfied, and thus the link label between RT4 and RT5 may not push the label stack.

RT1 may then continue probing RT5 through RT6 to determine whether RT5- > RT6(cost) < ═ RT1- > RT6(cost) is satisfied, and since 10< ═ 20, the link label between RT5 and RT6 may not be pushed in the label stack. RT1 continues to probe RT6 through RT7 and determines whether RT6- > RT7(cost) < ═ RT1- > RT7(cost) is satisfied, and since 10< ═ 10, the link label between RT6 and RT7 is not pushed in the label stack. Finally, only the node label of RT4 needs to be pressed in the label stack, and compared with the prior art, five-layer link labels such as {1001,1002,1003,1004,1005} and the like are needed in the label stack.

As shown in fig. 8, taking the first network node as RT1 as an example, RT1 determines the second network node as RT4 and may push the node label of RT4 onto the label stack. Then RT1 may probe RT4 to RT5, determining whether RT4- > RT5(cost) < ═ RT1- > RT5(cost) is satisfied; since RT4- > RT5(cost) is 1000, RT1- > RT5(cost) is 30, RT4- > RT5(cost) <rt 1- > RT5(cost) is not satisfied; the link label between RT4 and RT5 is pressed into the label stack. RT1 may then continue probing RT5 through RT6 to determine if RT5- > RT6(cost) < ═ RT1- > RT6(cost) is satisfied, and since 10< ═ 20, the link label between RT5 and RT6 is not pushed in the label stack. Probing RT6 through RT7 continues to determine whether RT6- > RT7(cost) < ═ RT1- > RT7(cost) is satisfied, and since 10< 10, the link label between RT6 and RT7 is not pushed in the label stack. Finally, node labels of RT4 and link labels between RT4 and RT5 need to be pushed in the label stack, and compared with the prior art, five-layer link labels such as {1001,1002,1003,1004,1005} are needed in the labels.

In another possible design, as shown in fig. 9, taking the first network node as RT1 as an example, RT1 may first generate a complete label stack for the second forwarding path, where the complete label stack includes a link label for each link in the second forwarding path. For example, the full label stack may include {1001,1002,1003,1004,1005 }; where 1001 is the link label between RT2 and RT3, 1002 is the link label between RT3 and RT4, 1003 is the link label between RT4 and RT5, 1004 is the link label between RT5 and RT6, and 1005 is the link label between RT6 and RT 7.

After RT1 determines that the second network node is RT4, the link label between RT1 to RT4 may be replaced with the node label of RT 4. For example, 1001 and 1002 in the label stack may be replaced with 4000, where 4000 is the node label of RT 4.

Compared with the prior art that the label stack needs to include the link label of each link in the forwarding path, the label stack is compressed by adopting the node label to replace the link label, so that the label stack is as short as possible, and under the condition that the label stack capability of the network equipment is not changed, more scenes (for example, the scenes of longer forwarding paths can be supported).

Then RT1 may probe RT4 to RT5, determining whether RT4- > RT5(cost) < ═ RT1- > RT5(cost) is satisfied; since 10< > 30, the link label between RT4 and RT5 may be deleted from the label stack. RT1 may then continue probing RT5 through RT6, determining whether RT5- > RT6(cost) < ═ RT1- > RT6(cost) is satisfied, and since 10< ═ 20, the link label between RT5 and RT6 may be deleted from the label stack. Probing RT6 through RT7 continues to determine whether RT6- > RT7(cost) < ═ RT1- > RT7(cost) is satisfied, and since 10< 10, the link label between RT6 and RT7 can be deleted from the label stack. The final label stack only comprises RT4 node labels, and compared with the prior art, five-layer link labels such as {1001,1002,1003,1004,1005} are required in the label stack.

504. And the first network node sends the message added with the label stack.

The first network node sends a message to a next hop network node of the first network node in the second forwarding path. The packet carries a label stack, which is a label stack corresponding to the second forwarding path.

For example, as shown in fig. 6, taking the first network node as RT1 as an example, RT1 may send a packet to the next-hop network node of RT1 in the second forwarding path (i.e., RT2), where the packet carries label stack {4000}, and 4000 is a node label of the second network node (RT 4).

After the RT2 receives the packet, it determines that the packet needs to be forwarded to the network node corresponding to the node label 4000 (i.e., RT4) according to the node label 4000 in the label stack, and according to the shortest path tree of itself or by looking up a routing table, the RT2 may determine that the next-hop network node is RT3, and then sends the packet to RT 3.

Similarly, after receiving the packet, RT3 determines, according to node label 4000 in the label stack, that the packet needs to be forwarded to the network node corresponding to node label 4000 (i.e., RT4), and according to its shortest path tree, RT3 may determine that the next-hop network node is RT4, and then sends the packet to RT 4.

After receiving the message, the RT4 deletes (pops up) the node label 4000, identifies the destination address of the message (the sixth network node, i.e., RT7), and the RT4 may determine the next-hop network node to be RT5 according to its own shortest path tree, and then sends the message to RT 5. Optionally, the destination address of the packet may be encapsulated in an Internet Protocol (IP) layer, and the label stack may be encapsulated in a multiprotocol label switching (MPLS) layer, where after a node label in the MPLS layer is deleted, the destination address in the IP layer is exposed, so that the RT4 may identify the destination address of the packet.

After receiving the message, RT5 identifies the destination address of the message (RT7), and according to its shortest path tree, RT5 can determine the next-hop network node as RT6, and then sends the message to RT 6.

After receiving the message, RT6 identifies the destination address of the message (RT7), and according to its shortest path tree, RT6 can determine the next-hop network node as RT7, and then sends the message to RT7, so that RT7 can receive the message.

Based on the method provided by the embodiment of the application, when the first network node determines that the first forwarding path for forwarding the message is unavailable, the second forwarding path for forwarding the message can be determined again; the first network node adds a label stack corresponding to a second forwarding path in the message, wherein the label stack comprises a node label of the second network node, the label stack does not comprise a link label of a link between the first network node and the second network node, or the label stack does not comprise a node label of a node between the first network node and the second network node, the shortest path between the first network node and the second network node does not comprise the first forwarding path, and the second network node is a node on the second forwarding path; and the first network node sends the message added with the label stack. In this way, the packet may be forwarded to the second network node according to the node label of the second network node in the label stack, without adding one or more link labels or node labels between the first network node and the second network node in the label stack, which may shorten the length of the label stack, and may support more scenarios (e.g., may support a scenario of a longer forwarding path) under the condition that the label stack capability of the network device is not changed.

In the embodiments provided in the present application, the method provided in the embodiments of the present application is introduced from the perspective of the first network node and the interaction between the first network node and other network nodes. In order to implement the functions in the method provided by the embodiments of the present application, the first network node may include a hardware structure and/or a software module, and implement the functions in the form of a hardware structure, a software module, or a hardware structure and a software module. Whether any of the above-described functions is implemented as a hardware structure, a software module, or a hardware structure plus a software module depends upon the particular application and design constraints imposed on the technical solution.

In the case of dividing the functional modules according to the respective functions, fig. 10 shows a schematic structural diagram of a possible apparatus involved in the foregoing embodiments, where the apparatus may be a first network node 10, and the first network node 10 includes: a determining unit 1001, a processing unit 1002, and a transmitting unit 1003. In this embodiment of the present application, the determining unit 1001 is configured to determine that a first forwarding path for forwarding a packet is unavailable; a determining unit 1001, configured to determine, in response to determining that the first forwarding path is unavailable, a second forwarding path for forwarding the packet; a processing unit 1002, configured to add a label stack corresponding to a second forwarding path in the packet, where the label stack includes a node label of a second network node, and the label stack does not include a link label of a link between the first network node and the second network node, or the label stack does not include a node label of a network node between the first network node and the second network node, a shortest path between the first network node and the second network node does not include the first forwarding path, and the second network node is a network node on the second forwarding path; a sending unit 1003, configured to send the packet to which the label stack is added.

In the method embodiment shown in fig. 5, the determining unit 1001 may be configured to support the first network node to perform the procedures 501 and 502 in fig. 5. The processing unit 1002 is configured to enable the first network node to perform the process 503 in fig. 5. The sending unit 1003 is configured to support the first network node to execute the process 504 in fig. 5.

The determining unit 1001 and the processing unit 1002 may be the processor 401 and/or the processor 405 in fig. 4. The transmitting unit 1003 may be the communication interface 404 in fig. 4.

The division of the modules in the embodiments of the present application is schematic, and only one logical function division is provided, and in actual implementation, there may be another division manner, and in addition, each functional module in each embodiment of the present application may be integrated in one processor, may also exist alone physically, or may also be integrated in one module by two or more modules. The integrated module can be realized in a hardware mode, and can also be realized in a software functional module mode. For example, in the embodiment of the present application, the receiving unit and the transmitting unit may be integrated into the transceiving unit.

The method provided by the embodiment of the present application may be implemented in whole or in part by software, hardware, firmware, or any combination thereof. When implemented in software, may be implemented in whole or in part in the form of a computer program product. The computer program product includes one or more computer instructions. When loaded and executed on a computer, cause the processes or functions described in accordance with the embodiments of the invention to occur, in whole or in part. The computer may be a general purpose computer, a special purpose computer, a computer network, a network appliance, a user device, or other programmable apparatus. The computer instructions may be stored on a computer readable storage medium or transmitted from one computer readable storage medium to another, for example, from one website, computer, server, or data center to another website, computer, server, or data center via wire (e.g., coaxial cable, fiber optic, Digital Subscriber Line (DSL)) or wireless (e.g., infrared, wireless, microwave, etc.). The computer-readable storage medium can be any available medium that can be accessed by a computer or a data storage device, such as a server, a data center, etc., that incorporates one or more of the available media. The usable medium may be a magnetic medium (e.g., floppy disk, hard disk, magnetic tape), an optical medium (e.g., Digital Video Disk (DVD)), or a semiconductor medium (e.g., Solid State Drive (SSD)), among others.

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

Claims

1. A method for sending a message, comprising:

a first network node determines that a first forwarding path for forwarding a packet is unavailable;

in response to determining that the first forwarding path is unavailable, the first network node determining a second forwarding path for forwarding the packet;

the first network node adds a label stack corresponding to the second forwarding path in the message, where the label stack includes a node label of a second network node, and the label stack does not include a link label of a link between the first network node and the second network node, or the label stack does not include a node label of a network node between the first network node and the second network node, and a shortest path between the first network node and the second network node does not include the first forwarding path, and the second network node is a network node on the second forwarding path;

and the first network node sends the message added with the label stack.

2. The method of claim 1, wherein the unavailability of the first forwarding path for forwarding the packet comprises at least one of:

the minimum link cost of the first forwarding path is greater than or equal to a preset threshold; or

The first forwarding path fails; or

The first forwarding path is congested.

3. The method according to claim 1 or 2,

the second network node is a network node which is farthest away from the first network node among the M network nodes, the M network nodes are respectively located on the second forwarding paths, the shortest path from the first network node to each network node among the M network nodes respectively does not include the first forwarding path, and M is an integer greater than or equal to 1.

4. The method of any of claims 1 to 3, wherein the second forwarding path comprises a third network node, the third network node being a next hop network node of the second network node in the second forwarding path, the method further comprising:

the first network node determining whether a minimum link overhead between the second network node and the third network node is greater than a minimum link overhead between the first network node and the third network node;

the label stack further comprises a link label between the second network node and the third network node when the minimum link overhead between the second network node and the third network node is greater than the minimum link overhead between the first network node and the third network node.

5. The method of any of claims 1 to 3, wherein the second forwarding path comprises a third network node, the third network node being a next hop network node of the second network node in the second forwarding path, the method further comprising:

the first network node determining whether a minimum link overhead between the second network node and the third network node is less than or equal to a minimum link overhead between the first network node and the third network node;

the label stack does not include a link label between the second network node and the third network node when a minimum link overhead between the second network node and the third network node is less than or equal to a minimum link overhead between the first network node and the third network node.

6. The method of claim 4 or 5, wherein the second forwarding path comprises a fourth network node that is a next hop network node of the third network node in the second forwarding path, the method further comprising:

the first network node determining whether a minimum link overhead between the third network node and the fourth network node is greater than a minimum link overhead between the first network node and the fourth network node;

the label stack further includes a link label between the third network node and the fourth network node when the minimum link overhead between the third network node and the fourth network node is greater than the minimum link overhead between the first network node and the fourth network node.

7. The method of claim 4 or 5, wherein the second forwarding path comprises a fourth network node that is a next hop network node of the third network node in the second forwarding path, the method further comprising:

the first network node determining whether a minimum link overhead between the third network node and the fourth network node is less than or equal to a minimum link overhead between the first network node and the fourth network node;

when the minimum link overhead between the third network node and the fourth network node is less than or equal to the minimum link overhead between the first network node and the fourth network node, the label stack does not include a link label between the third network node and the fourth network node.

8. The method of claim 6,

when the label stack does not include a link label between the second network node and the third network node, and the label stack includes a link label between the third network node and the fourth network node, the label stack also includes a node label of the third network node.

9. A first network node, comprising:

a determining unit, configured to determine that a first forwarding path for forwarding a packet is unavailable;

the determining unit is further configured to determine, in response to determining that the first forwarding path is unavailable, a second forwarding path for forwarding the packet;

a processing unit, configured to add a label stack corresponding to the second forwarding path in the packet, where the label stack includes a node label of a second network node, and the label stack does not include a link label of a link between the first network node and the second network node, or the label stack does not include a node label of a network node between the first network node and the second network node, a shortest path between the first network node and the second network node does not include the first forwarding path, and the second network node is a network node on the second forwarding path;

and the sending unit is used for sending the message added with the label stack.

10. The first network node of claim 9, wherein the first forwarding path for forwarding packets is unavailable and comprises at least one of:

The first forwarding path fails; or

The first forwarding path is congested.

11. The first network node according to claim 9 or 10,

12. The first network node according to any of claims 9 to 11, wherein the second forwarding path comprises a third network node, the third network node being a next hop network node of the second network node in the second forwarding path, the determining unit further configured to:

determining whether a minimum link overhead between the second network node and the third network node is greater than a minimum link overhead between the first network node and the third network node;

13. The first network node according to any of claims 9 to 11, wherein the second forwarding path comprises a third network node, the third network node being a next hop network node of the second network node in the second forwarding path, the determining unit further configured to:

determining whether a minimum link overhead between the second network node and the third network node is less than or equal to a minimum link overhead between the first network node and the third network node;

14. The first network node according to claim 12 or 13, wherein the second forwarding path comprises a fourth network node, the fourth network node being a next hop network node of the third network node in the second forwarding path, the determining unit further configured to:

determining whether a minimum link overhead between the third network node and the fourth network node is greater than a minimum link overhead between the first network node and the fourth network node;

15. The first network node according to claim 12 or 13, wherein the second forwarding path comprises a fourth network node, the fourth network node being a next hop network node of the third network node in the second forwarding path, the determining unit further configured to:

determining whether a minimum link overhead between the third network node and the fourth network node is less than or equal to a minimum link overhead between the first network node and the fourth network node;

16. The first network node of claim 14,

17. A system for message transmission, comprising a first network node and a second network node, wherein:

the first network node is configured to determine that a first forwarding path for forwarding a packet is unavailable; determining a second forwarding path for forwarding the packet in response to determining that the first forwarding path is unavailable; adding a label stack corresponding to the second forwarding path in the message; the label stack comprises a node label of the second network node and the label stack does not comprise a link label of a link between the first network node and the second network node or the label stack does not comprise a node label of a network node between the first network node and the second network node, the shortest path between the first network node and the second network node does not comprise the first forwarding path, the second network node is a network node on the second forwarding path; sending the packet with the label stack added to the second network node;

and the second network node receives the message added with the label stack and sends the message according to the label stack.

18. A readable storage medium storing instructions that, when executed, cause the method of any of claims 1-8 to be implemented.