WO2018033060A1 - Message switching method and device - Google Patents

Abstract

The embodiments of the invention provide a message switching method and device. The method comprises: a first node receives a message to be forwarded, wherein a destination address of the message is a second node; the first node looks up, from pre-generated topologies, a target topology corresponding to the message, wherein the pre-generated topologies comprise: a first topology and a second topology generated according to an MRT algorithm, and a third topology generated according to a SPF algorithm, and the first, second and third topologies are different from each other; and the first node looks up, in the target topology, a next hop node used to forward the message to the second node, and forwards, on the basis of a preconfigured forwarding mechanism, and to the next hope node, the message, wherein the preconfigured forwarding mechanism adopts a segment routing and forwarding mechanism on the basis of a tunneling encapsulation method and with respect to each topology and each prefix-sid. The embodiment of the invention is employed to achieve the goal of combining a segment routing network and the MTR function.

Description

Message forwarding method and device Technical field

The present invention relates to the field of communications, and in particular to a packet forwarding method and apparatus.

Background technique

Maximum Redundant Trees (MRT) Fast Re-Route (FRR) is a newer FRR technology that uses two different forwarding topologies. Point link or node failure provides 100% protection. The MRT architecture defines two forwarding mechanisms, namely, the Label Distribution Protocol (LDP) forwarding mechanism and the network protocol-tunnel (IP-tunnel) forwarding mechanism. The LDP forwarding mechanism distinguishes between the default topology forwarding behavior and the MRT forwarding behavior through different labels, so that the forwarding plane can support MRT-FRR without any upgrade. The IP-tunnel forwarding mechanism needs to waste the dedicated MRT loopback address to support forwarding. It also enables the forwarding plane to support MRT-FRR without any upgrade. In contrast, the LDP forwarding mechanism is more reasonable. Therefore, the default maximum redundancy tree configuration file of the MRT architecture uses the LDP forwarding mechanism in the default MRT profile. Currently, other MRT profiles are not defined.

The segmentation routing technology will enable a node to specify its forwarding path for the message instead of forwarding it according to the general shortest path. By adding the segment list information related to the segment ID segment ID to the message, it is not required. The status information of each path is maintained on the intermediate node. Segmented routing primarily extends the IGP to support advertising and learning segment IDs. Generally, in the network where the segmentation route is deployed, the LDP and the Resource ReSerVation Protocol-Traffic Extension (RSVP-TE) are no longer needed. In the segmented routing network, the known FRR technology has a Topology Independent Loop Free Alternate (TI-LFA), but the protection rules defined by TI-LFA are very complicated and immature.

The introduction of MRT functionality in a segmented routing network will be of great significance, but there has been no literature discussing this aspect so far, so in the related art, segmentation routing cannot be implemented. The network is combined with the MTR function.

Summary of the invention

The embodiment of the invention provides a packet forwarding method and device, so as to solve at least the problem that the segment routing network and the MTR function cannot be combined in the related art.

According to an embodiment of the present invention, a packet forwarding method is provided, including: a first node receives a packet to be forwarded, where a destination address of the packet is a second node; and the first node is in advance Searching for a target topology corresponding to the packet in the generated topology, where the pre-generated topology includes: a first topology and a second topology generated according to a maximum redundancy tree MRT algorithm, and obtained according to a shortest path first SPF algorithm a third topology, the first topology and the second topology and the third topology are different from each other; the first node looks up in the target topology for forwarding to the second node a hop node, and forwarding the message to the next hop node based on a predetermined forwarding mechanism, wherein the predetermined forwarding mechanism adopts a segmented route forwarding based on a tunnel nesting manner of each prefix per prefix per prefix mechanism.

Optionally, the method further includes: determining, by the first node, a route from the first topology to the destination address and a route from the second topology to the destination address according to the MRT algorithm a protection route for protecting a route to the destination address in the third topology, and determining that a topology corresponding to the protection route is a protection topology; and/or, the first node according to the color flag information from the Determining a protection route for protecting a route to the destination address in the third topology from a route to a tunnel end point in a topology and a route to a tunnel end point in the second topology, and determining a corresponding path of the protection route The topology is a protection topology, where the tunnel endpoint is a remote node selected by the first node for the protection destination address, and the remote node is loop-free for the fault point, when the fault occurs. The first node uses the MRT tunnel encapsulation message to the remote node.

Optionally, the searching, by the first node, the target topology corresponding to the packet in the pre-generated topology includes: determining, by the first node, a chain in the third topology for reaching the second node Whether the road has a fault; in the case that it is determined that there is no fault, the first node determines that the third topology is the target topology; and/or, in the event that a fault is determined, The first node determines that the protection topology is the target topology.

Optionally, before the receiving, by the first node, the packet to be forwarded, the method further includes: the first node generating, according to the MRT algorithm, the first topology and the second topology, and according to The SPF algorithm generates the third topology.

Optionally, the first node generates the first topology and the second topology according to the MRT algorithm, and the third topology is generated according to the SPF algorithm, where the first node determines the An MRT Island where a node is located, wherein the MRT Island is an open shortest path first OSPF or intermediate system on the first node and other nodes in the same domain area or the same level as the first node After the segmentation route SR and the maximum redundancy tree profile MRT profile are enabled in the intermediate system ISIS instance, the first node and the other nodes negotiate with each other in the area or level where the first node is located; The first node generates the first topology and the second topology based on the MRT Island running the MRT algorithm, and the third topology is generated by running the SPF algorithm based on the area or level.

Optionally, the predetermined forwarding mechanism is specified in the MRT profile.

Optionally, the method further includes at least one of: the first node assigns a first prefix-sid to the first topology for a node-level prefix local to the first node, and the first prefix -sid flooding in the domain area or level of the MRT Island; the first node is a node-level prefix local to the first node, and assigns a second prefix-sid to the second topology, and The second prefix-sid is flooded in a domain area or a hierarchy level in which the MRT Island is located; the first node is a node-level and a non-node-level prefix local to the first node, and the third topology is allocated to the third topology. a third prefix-sid, and flooding the third prefix-sid in all domain or hierarchy levels in which the first node is located; the first node receiving a prefix of the pre-generated topology on other nodes -sid, recording a prefix-sid of the pre-generated topology on the other node and continuing to advertise a prefix-sid of the pre-generated topology on the other node to a node other than the other node .

Optionally, the forwarding, by the first node, the packet to the next hop node includes: Determining, by the first node, an outgoing label of the first node that matches the packet; the first node encapsulating the outgoing label of the first node into the packet, and sending the encapsulated packet Go to the next hop node.

Optionally, the determining, by the first node, the outbound label of the first node that matches the packet includes: when the target topology is the third topology, the first node corresponding to the target The outbound label of the topology is calculated by the first node based on the third prefix index prefix-sid of the destination prefix prefix corresponding to the destination address and the SRGB of the next hop node.

Optionally, the determining, by the first node, the outbound label of the first node that matches the packet includes: when the target topology is the first topology or the second topology: When the two nodes are the nodes in the MRT Island and the destination prefix prefix corresponding to the destination address is the node-level prefix prefix of the second node, the first node determines the corresponding location of the first node by: An outbound label of the target topology: an outbound label of the first node corresponding to the target topology is prefixed by the first node based on a prefix index of the node level prefix prefix of the second node corresponding to the target topology SRGB calculation with the next hop node; if the second node is not the node in the MRT Island or the destination prefix prefix corresponding to the destination address is the non-node level prefix of the second node The first node determines whether the next hop node is a node outside the MRT Island; when the determination result is no, the first node determines the corresponding state of the first node by: An outgoing label of the topological topology: the outgoing label of the first node corresponding to the target topology is a label stack, the outer label is a label of the first node to the tunnel end point, and the inner layer label is the tunnel end point to the a label of the destination prefix prefix; wherein the outer label is referenced by the first node based on a node-level prefix prefix of the tunnel destination, a prefix index prefix corresponding to the target topology, and the target topology to the SRGB calculation of the next hop node of the tunnel end point, the inner layer label is calculated by the first node based on the prefix index prefix-sid of the third topology and the SRGB of the tunnel end point based on the destination prefix prefix Obtaining; when the determination result is yes, the first node determines an outbound label of the first node corresponding to the target topology by: the outbound label of the first node corresponding to the target topology is Determining, by the first node, a prefix index prefix-sid corresponding to the third topology and the next hop by the destination prefix prefix The point is calculated by SRGB.

Optionally, the first node encapsulates the outgoing label of the first node into the packet, and includes at least one of the following: when the packet type of the packet is an Internet Protocol IP packet, The outbound label of the first node is pressed on the IP header of the IP packet; when the packet type of the packet is a fragmented route SR label packet, the stack of the label stack of the SR label packet is used. The top tag is replaced with the outgoing tag of the first node.

Optionally, the determining, by the first node, the outgoing label of the first node includes: when the first node and the second node are the same node, the first node is determined based on the target topology. The next hop node is the first node, and the first node does not have a label.

Optionally, the method further includes: when the first node and the second node are the same node, the method includes: when the packet type of the packet is an Internet Protocol IP packet, the first Sending, by the node, the packet to the control plane of the first node; and/or, when the packet type of the packet is a fragmented route SR label packet, the first node sends the SR The stack top label of the label stack of the label message pops up, and continues to be forwarded based on the lower layer label or IP header lookup table of the label stack of the message.

According to another embodiment of the present invention, a message forwarding device is further provided, where the device is applied to a first node, and includes: a receiving module, configured to receive a packet to be forwarded, where the packet is The destination address is a second node, and the search module is configured to search for a target topology corresponding to the packet in a pre-generated topology, where the pre-generated topology includes: a first generated according to a maximum redundancy tree MRT algorithm. a topology and a second topology, according to a third topology obtained by the shortest path first SPF algorithm, the first topology and the second topology and the third topology are different from each other; a forwarding module configured to be at the target Finding, in the topology, a next hop node for forwarding to the second node, and forwarding the packet to the next hop node based on a predetermined forwarding mechanism, where the predetermined forwarding mechanism adopts per prefix based on each topology The segmentation route forwarding mechanism of the tunnel nesting mode of the index prefix-sid.

Optionally, the apparatus further includes: a determining module, configured to follow a route from the first topology to the destination address and the second topology to the destination according to the MRT algorithm Determining, in the routing of the address, a protection route for protecting a route to the destination address in the third topology, and determining that the topology corresponding to the protection route is a protection topology; and/or, according to the color flag information, from the Determining a protection route for protecting a route to the destination address in the third topology from a route to a tunnel end point in a topology and a route to a tunnel end point in the second topology, and determining a corresponding path of the protection route The topology is a protection topology, where the tunnel endpoint is a remote node selected by the first node for the protection destination address, and the remote node is loop-free for the fault point, when the fault occurs. The first node uses the MRT tunnel encapsulation message to the remote node.

According to still another embodiment of the present invention, a storage medium is also provided. The storage medium is arranged to store program code for performing the above steps.

Through the invention, the MRT function is introduced in the segment routing network, thereby achieving the purpose of combining the segment routing network with the MTR function.

DRAWINGS

The drawings described herein are intended to provide a further understanding of the invention, and are intended to be a part of the invention. In the drawing:

1 is a flowchart of a packet forwarding method according to an embodiment of the present invention;

2 is a schematic diagram of an MRT Profile according to an embodiment of the present invention;

3 is a network topology diagram according to a specific embodiment of the present invention;

4 is a network topology diagram according to a second embodiment of the present invention;

FIG. 5 is a network topology diagram according to a third embodiment of the present invention; FIG.

FIG. 6 is a structural block diagram of a message forwarding apparatus according to an embodiment of the present invention; FIG.

FIG. 7 is a block diagram showing a preferred structure of a message forwarding apparatus according to an embodiment of the present invention.

detailed description

The invention will be described in detail below with reference to the drawings in conjunction with the embodiments. It should be noted, The embodiments in the present application and the features in the embodiments may be combined with each other without conflict.

It is to be understood that the terms "first", "second" and the like in the specification and claims of the present invention are used to distinguish similar objects, and are not necessarily used to describe a particular order or order.

In this embodiment, a packet forwarding method is provided. FIG. 1 is a flowchart of a packet forwarding method according to an embodiment of the present invention. As shown in FIG. 1, the process includes the following steps:

Step S102, the first node receives the packet to be forwarded, where the destination address of the packet is the second node;

Step S104: The first node searches for a target topology corresponding to the foregoing packet in a pre-generated topology, where the pre-generated topology includes: a first topology and a second topology generated according to a maximum redundancy tree MRT algorithm, According to a third topology obtained by a Shortest Path First (SPF) algorithm, the first topology and the second topology and the third topology are different from each other;

Step S106, the first node searches for a next hop node for forwarding to the second node in the target topology, and forwards the packet to the next hop node according to a predetermined forwarding mechanism, where the predetermined forwarding mechanism is adopted. A segmented route forwarding mechanism based on the tunnel nesting manner of prefix-sid per prefix per topology.

The first node may be any node in the MRT Island, and the second node may be any node in the SR Domain, and the second node may be in the MRT Island or outside the MRT Island. One of the first topology and the second topology may be an MRT-red topology, and one is an MRT-blue topology; and the third topology may be an MT-default topology.

In the foregoing embodiment, when the first node forwards the packet to the next hop node, the first node may perform forwarding according to a predetermined forwarding mechanism, which is a tunnel nesting manner based on the per-segment per-segment routing global block SRGB. Segmented route forwarding mechanism.

Through the above steps, the MRT function is introduced in the segment routing network, thereby achieving the purpose of combining the segment routing network with the MTR function.

In an optional embodiment, the foregoing method further includes: (can receive the message to be forwarded The foregoing step is performed in the embodiment: the first node determines, according to the MRT algorithm, the route from the first topology to the destination address and the route from the second topology to the destination address to protect the third topology to the destination address. Protecting the route of the route, and determining that the topology corresponding to the protection route is a protection topology; and/or, the first node according to the color flag information from the first topology to the tunnel end point and the route from the second topology to the tunnel end point Determining a protection route for protecting a route to a destination address in the third topology, and determining that the topology corresponding to the protection route is a protection topology, wherein the tunnel end point is a remote node selected by the first node as a protection destination address The remote node is loop-free for the fault point. When the fault occurs, the first node uses the MRT tunnel to the remote node to encapsulate the packet. In this embodiment, when determining the protection topology, the first topology may be determined as the protection topology, and the second topology may be determined as the protection topology. The specific topology selected as the protection topology needs to be determined according to actual conditions.

In an optional embodiment, the searching, by the first node, the target topology corresponding to the foregoing packet in the pre-generated topology includes: determining, by the first node, whether the link used to reach the second node in the third topology is A fault occurs; the first node determines that the third topology is the target topology in the case that it is determined that there is no fault; and/or, in the case that the fault is determined, the first node determines that the protection topology is the target topology. In this embodiment, when the link is faulty, the packet can be forwarded according to the default topology. After the link is faulty, the protection topology is used to forward the packet.

In an optional embodiment, before the receiving, by the first node, the packet to be forwarded, the method further includes: the first node generates the first topology and the second topology according to the MRT algorithm, and generates according to the SPF algorithm. Get the third topology.

In an optional embodiment, the first node generates the first topology and the second topology according to the foregoing MRT algorithm, and generates the third topology according to the SPF algorithm, where the first node determines the MRT Island where the first node is located. The MRT Island is an Open Shortest Path First (OSPF) or intermediate system to an intermediate system on the first node and other nodes in the same domain area or the same level as the first node. (Intermediate system to Intermediate system, referred to as ISIS), the segmentation route SR and the maximum redundancy tree configuration file MRT profile are enabled in the first section. The first node and the other nodes are mutually negotiated in the area or level where the point is located; the first node generates the first topology and the second topology based on the MRT Island running MRT algorithm, and generates the SPF algorithm based on the above area or level. The third topology.

In an optional embodiment, the foregoing predetermined forwarding mechanism is specified in the MRT profile. That is, the segmented route forwarding mechanism based on the tunnel nesting manner of the prefix-sid per prefix per topology is adopted.

In an optional embodiment, the foregoing method further includes at least one of the following: the first node is a node-level prefix local to the first node, and the first prefix-sid is allocated to the first topology, and the first prefix-sid is Flooding in the domain area or level of the MRT Island; the first node is a node-level prefix local to the first node, and a second prefix-sid is allocated for the second topology, and the second prefix-sid is located at the MRT Island. Flooding in the domain area or level level; the first node is a node-level and non-node-level prefix local to the first node, and a third prefix-sid is allocated for the third topology, and the third prefix-sid is in the first node. Flooding in all domain or level levels; the first node receives the prefix-sid of the pre-generated topology on the other node, records the prefix-sid of the pre-generated topology on the other node, and the other The prefix-sid of the pre-generated topology on the node continues to be advertised to nodes other than the other nodes. In this embodiment, the first prefix-sid, the second prefix-sid, and the third prefix-sid are independent of each other.

In an optional embodiment, the first node forwarding the packet to the next hop node includes: the first node determining an outgoing label of the first node that matches the packet; the first node The outgoing label of the node is encapsulated into the above packet, and the encapsulated packet is sent to the next hop node. In this embodiment, the label encapsulation manner is different for different types of packets.

In an optional embodiment, the first node determines that the egress label of the first node that matches the packet includes: when the target topology is the third topology, the label of the corresponding target topology of the first node is A node is calculated based on the third prefix index prefix-sid of the destination prefix prefix corresponding to the destination address and the SRGB of the next hop node.

In an optional embodiment, the first node determines the first section that matches the message. The outbound label of the point includes: when the target topology is the first topology or the second topology: if the second node is a node in the MRT Island and the destination prefix corresponding to the destination address is a node-level prefix prefix of the second node The first node determines an outbound label of the first node corresponding to the target topology by: the outbound label of the corresponding target topology of the first node is corresponding to the target topology of the first node based on the node level prefix of the second node The prefix index prefix-sid is calculated by the SRGB of the next hop node; if the second node is not the node in the MRT Island or the destination prefix prefix corresponding to the destination address is the non-node level prefix of the second node, the foregoing A node determines whether the next hop node is a node outside the MRT Island; when the determination result is no, the first node determines, by the following manner, the outbound label of the first node corresponding to the target topology: the first node corresponding to the target topology The label is the label stack, and the outer label is the label of the first node to the tunnel end point, and the inner label is the above a label from the end of the track to the destination prefix; wherein the outer label is prefixed by the first node based on the prefix index of the corresponding target topology of the node-level prefix prefix of the tunnel end point and the next hop from the target topology to the tunnel end point The SRGB of the node is calculated, and the inner layer label is calculated by the first node based on the prefix index prefix-sid of the third topology of the destination prefix prefix and the SRGB of the tunnel end point; when the judgment result is yes, the first node passes the following The method determines an outbound label of the corresponding target topology of the first node: the outbound label of the corresponding target topology of the first node is determined by the first node based on the prefix index prefix-sid of the third topology of the destination prefix prefix and the next hop node Calculated by SRGB.

In an optional embodiment, the first node encapsulates the outgoing label of the first node into the packet, and includes at least one of the following: when the packet type of the packet is an Internet Protocol IP packet, The IP address of the IP packet is stamped with the outgoing label of the first node. When the packet type of the packet is a fragmented routing SR label, the top label of the label stack of the SR label is replaced with the first label. The outgoing label of a node.

In an optional embodiment, the determining, by the first node, the outbound label of the first node includes: when the first node and the second node are the same node, the first node determines the next hop node based on the target topology. For the first node, the first node does not have a label.

In an optional embodiment, the method further includes: when the first node and the second section are When the point is the same node, the first node sends the packet to the control plane of the first node when the packet type of the packet is an Internet Protocol IP packet; and/or, when the packet is When the packet type is a segment-routed SR-tag packet, the first node pops up the stack-top label of the label stack of the SR-tag packet, and continues to forward the packet based on the lower-layer label or the IP header of the label stack of the packet.

The present invention will be described below in conjunction with specific embodiments:

In the embodiment of the present invention, the segmentation route is combined with the MRT technology to provide an MRT-FRR method based on the segmentation route forwarding mechanism. In this embodiment, an MRT profile is added to the MRT architecture, and the segment routing and forwarding mechanism is used to distinguish the default topology forwarding behavior and the MRT topology forwarding behavior by using the segment routing and forwarding mechanism.

The MRT-FRR method based on the segment routing and forwarding mechanism in the embodiment of the present invention includes the following steps:

The first step is to define a new MRT profile MRT Profile. Compared with the default default MRT profile, the difference is mainly reflected in the SR-LSP based on multi-prefix-sid tunneling forwarding mechanism. The SR-LSP is an LSP based on the fragment routing (SR) type, which is similar to the LDP LSP. The SR-LSP tunneling forwarding mechanism is that the SR LSP in the MRT topology is established with the MRT egress node as the destination node. After the MRT FRR switchover occurs, on the MRT Ingress node, the SR LSP in the default topology is the tunnel nested in the MRT. Topology of the SR LSP. When the SR-LSP tunneling forwarding mechanism is used, the MRT ingress node needs to perceive the SR label corresponding to the default topology allocated by the MRT egress node for the destination prefix. Multi-prefix-sid refers to each prefix-sid per topology, that is, the default topology is different from the MRT-red topology and the prefix-sid in the MRT-blue topology.

In the second step, the MRT is enabled in the corresponding IGP instance on each node in the IGP area/level (which may be only a part of the node) and the new MRT profile is supported, and the corresponding MRT Island is generated for the new MRT profile. Based on the MRT Island running MRT algorithm to generate the corresponding MRT-red topology and MRT-blue topology, the corresponding MT-IDs are recorded as MT-red and MT-blue, respectively. In addition, the MT-ID corresponding to the default topology generated by the SPF algorithm can be recorded as MT-default.

The third step is to enable the IGP instance on each node of the segmentation route. If the MRT is also enabled and the new MRT profile is supported, the MT-default prefix-sid is not assigned to the MT-default. -default node-sid (usually the prefix-sid corresponding to a loopback route, the same below), and also assign the MT-red prefix-sid of the node-level MT-red node-sid to MT-red, and MT-blue The MT-blue prefix-sid of the node level is assigned as the MT-blue node-sid. The three node-sids are flooded with (MT-default, prefix), (MT-red, prefix), and (MT-blue, prefix) reachable notification messages, where (MT-default, prefix) can be between areas. Flooding, but (MT-red, prefix) and (MT-blue, prefix) flood only in the area.

It should be noted that only the nodes in the above MRT Island need to additionally allocate MT-red node-sid and MT-blue node-sid for their node-level prefix. The non-node-level prefix in the MRT Island can also be assigned the corresponding MT-red prefix-sid and MT-blue prefix-sid, but it is not required. Generally, it is not recommended to allocate. If it is allocated, its corresponding entry establishment process and node. The establishment process of the class prefix is completely similar; the node-level and non-node-level prefix outside the MRT Island do not need to allocate the corresponding MT-red prefix-sid and MT-blue prefix-sid because of the original in these prefixes. On the advertising node, the MRT is not perceived, and it is impossible to allocate the MRT-related MT-red prefix-sid and MT-blue prefix-sid.

In the fourth step, the source node S in the MRT Island calculates the SPF primary next hop and the MRT-blue/red next hop for the node-level prefix (denoted as D-loopback0) of the other destination node D in the Island, ie (MT- Default, D-loopback0) will contain the SPF main next hop, (MT-blue, D-loopback0) will contain the MRT-blue next hop, (MT-red, D-loopback0) will contain MRT-red One jump. And determining whether the MRT-blue next hop or the MRT-red next hop protects the SPF primary next hop by the MRT algorithm.

The MT-default SR outgoing label in the SPF primary next hop is calculated based on the offset of the (MT-default, D-loopback0) corresponding prefix-sid in the SRGB of the next hop node; in the MRT-red next hop The MRT-red SR outgoing label is calculated based on the offset of the (MT-red, D-loopback0) corresponding prefix-sid in the SRGB of the next hop node; the above MRT-blue next The MRT-blue SR outgoing label in the hop is calculated based on the offset of the corresponding prefix-sid of (MT-blue, D-loopback0) in the SRGB of the next hop node.

According to (MT-default, D-loopback0), a corresponding FTN entry is generated. The primary NHLFE includes the SPF primary next hop and the corresponding MT-default SR outgoing label, and the MRT-FRR standby NHLFE includes the above selected for protecting the SPF primary. The next hop MRT-red next hop or MRT-blue next hop and the corresponding MRT-red SR outgoing label or MRT-blue SR outgoing label. According to (MT-default, D-loopback0), the corresponding ILM entry is also generated, and the MT-default SR incoming tag is calculated based on the offset of the (MT-default, prefix) corresponding prefix-sid in the SRGB of the S node, NHLFE Same as the above FTN entry.

The S-node can also generate a corresponding Incoming Label Map (ILM) entry for (MT-red, D-loopback0), and the MT-red SR is based on the label (MT-red, D-loopback0). The corresponding prefix-sid is calculated by offsetting in the SRGB of the S node, and the NHLFE includes the MRT-red next hop and the corresponding MT-red SR outgoing label. The corresponding ILM entry is also generated for (MT-blue, D-loopback0), and the MT-blue SR input tag is calculated based on the offset of the corresponding prefix-sid of the (MT-blue, D-loopback0) in the S node. The NHLFE contains the MRT-blue next hop and the corresponding MT-blue SR outgoing label.

In the fifth step, the source node S in the MRT Island also calculates the SPF primary next hop and the MRT for other prefixes within the Island or other outside of the Island (ie all other prefixes in the network except the node level prefix in the MRT Island where the S is located). -FRR backup next hop, MRT-FRR backup next hop is represented as the corresponding MRT Egress node (denoted as E, the corresponding node level prefix is marked as E-loopback0) and the color flag information prompt is selected to the M node of the E node The red path is also the MRT-blue path to protect the above SPF primary next hop.

The MT-default SR outgoing label in the SPF primary next hop is calculated based on the offset of the (MT-default, prefix) corresponding prefix-sid in the SRGB of the next hop node; the MRT-FRR backup next hop will correspond to one In the label stack: the underlying label is the MT-default SR label assigned by the E node for the destination prefix, that is, based on the offset of the (MT-default, prefix) corresponding prefix-sid in the SRGB of the E node; the upper label is S to E's MRT-blue or MRT-red road The SR entry label corresponding to the path (selecting the MRT-blue or MRT-red path according to the color flag information), that is, based on the (MT-red, E-loopback0) or (MT-blue, E-loopback0) corresponding prefix-sid The offset is calculated in the SRGB of the S node. Before the actual forwarding, the top-level SR into the label needs to be searched for the corresponding SR ILM entry and replaced with the outgoing label and the direct next hop, that is, the above-mentioned incoming label stack is converted into the outgoing label stack.

According to (MT-default, prefix), a corresponding FTN entry is generated. The primary NHLFE includes the foregoing SPF primary next hop and the corresponding MT-default SR outgoing label, and the standby NHLFE includes the MRT Egress node E and its corresponding color flag information. The calculated inbound label stack (used to be replaced with the label stack before being actually forwarded). According to (MT-default, prefix), the corresponding ILM entry is also generated, and the MT-default SR entry tag is calculated based on the offset of the (MT-default, prefix) corresponding prefix-sid in the S node SRGB, NHLFE and the above The FTN entries are the same. If the prefix is an S node local or direct prefix, there is no NHLFE information.

In the sixth step, when the fault occurs, the IP or SR label unicast traffic is forwarded along the MRT path as follows: The MRT Ingress node directs the IP packet based on the corresponding FTN entry of the MT-default, prefix, or the ILM entry guides the SR. Label packet forwarding. Specifically divided into two cases:

1) If the traffic matches the FTN or ILM entry corresponding to a node-level (MT-default, prefix) in the MRT Island, the top-level label of the SR-label packet MT-default SR is switched into the MRT- The red or MRT-blue SR is sent to the MRT-red or MRT-blue next hop after the label is sent out; or the IP packet is directly pressed onto the MRT-red or MRT-blue SR and sent to the MRT-red or MRT- Blue next hop.

2) If the traffic matches the FTN or ILM entry corresponding to the other (MT-default, prefix), the top-level label of the SR-label packet, the MT-default SR, is switched to the MT that the MRT Egress node allocates for the prefix. The -default SR tag is then pressed to the MRT-red or MRT-blue SR of the MRT Egress node and sent to the MRT-red or MRT-blue next hop of the MRT Egress node; or the IP packet is directly pressed. The MR-red or MRT-blue SR that is up to the MRT Egress node is sent out to the MRT-red or MRT-blue next hop to the MRT Egress node.

The MRT Transit node forwards the message based on the corresponding SR ILM entry to the MRT Egress node level (MT-red, prefix) or (MT-blue, prefix), and continues to exchange the MRT-red or MRT-blue SR into the label. The MRT-red or MRT-blue SR is sent out to the MRT-red or MRT-blue next hop.

After the MRT Egress node is dropped to its own MRT-red or MRT-blue SR tag, the MLD-based SR tag corresponding to the lower layer (MT-default, prefix) is used to search for the corresponding ILM entry to forward the packet, or IP address. After the packet header is exposed, it is forwarded directly based on the destination IP address.

The technical solutions in the embodiments of the present invention are further described in detail below with reference to the accompanying drawings:

In this embodiment, the MRT profile in the embodiment of the present invention is first described:

2 is a schematic diagram of an MRT profile according to an embodiment of the present invention. The MRT profile shown in FIG. 2 is basically the same as the default MRT profile defined in RFC7812. The difference is that the MRT Forwarding Mechanism option is SR-LSP based on multi-prefix. -sid tunneling Option.

Specific embodiment 1

This embodiment will describe the MRT path forwarding process in which the destination prefix is located in the MRT Island. FIG. 3 is a network topology diagram according to a specific embodiment of the present invention. As shown in FIG. 3, OSPF is running in the network, and all nodes are in the same area. The segment routing function is enabled in the corresponding OSPF instance, and the MRT profile defined in the foregoing embodiment of the present invention is enabled. S establishes the MRT path to the prefix of the destination node D as the source node, and then protects the SPF main path based on this MRT path. Including the following steps:

Step S301: After the SR is enabled in the OSPF instance on each node of the S, A, B, and D, and the MRT profile defined in the embodiment of the present invention, they form an MRT Island in the area. In addition, the MRT SR-LSP based on multi-prefix-sid tunneling option is used as the forwarding mechanism in the MRT profile. In addition to the MT-default prefix-sid, each node in the MRT Island additionally allocates the MT-red prefix-sid. With MT-blue prefix-sid, for example, three types of node-level prefix S-loopback0 can be assigned on the S node. The prefix-sid is respectively recorded as: (MT-default, S-loopback0) node-sid, (MT-red, S-loopback0) node-sid, (MT-blue, S-loopback0) node-sid. In addition, it can be noted that the SRGB of the S node is SRGB_S, and the other nodes are similar.

The MT-default topology in the area is obtained based on the SPF algorithm on each node in the MRT Island, and the MT-red and MT-blue topologies are obtained based on the MRT algorithm. For example, on the S node, the MT-default path to the destination node D is S-D, the MT-red path is also S-D, and the MT-blue path is S-A-B-D.

Each node generates a corresponding prefix entry based on the topology. For example, on the S node, the MT-default next hop of the node-level prefix D-loopback0 in the MT-default topology to the destination node D is D, and the MT-blue topology is selected. The MT-blue path is given to protect the MT-default next hop D, then the corresponding MRT-FRR next hop will be copied to the next hop in the above MT-blue, that is, A, which is called MRT-blue next hop. . Assume (MT-default, D-loopback0) node-sid is default_SID0_D, (MT-red, D-loopback0) node-sid is red_SID0_D, (MT-blue, D-loopback0) node-sid is blue_SID0_D, then MT- The outgoing label corresponding to the default next hop D is SRGB_D[default_SID0_D], and the outgoing label corresponding to the next hop A of the MRT-blue is SRGB_A[blue_SID0__D]. The following is an example of the entries on some nodes:

S node:

FTN for(MT-default, D-loopback0)

Primary NHLFE: The next hop is D, and the outgoing label is SRGB_D[default_SID0_D]

Standby NHLFE: the next hop is A, and the outgoing label is SRGB_A[blue_SID0_D]

ILM for(MT-default, D-loopback0)

The entry tag is SRGB_S[default_SID0_D]

Primary NHLFE: The next hop is D, and the outgoing label is SRGB_D[default_SID0_D]

Standby NHLFE: the next hop is A, and the outgoing label is SRGB_A[blue_SID0_D]

A node:

ILM for(MT-blue, D-loopback0)

The entry tag is SRGB_A[blue_SID0_D]

NHLFE: The next hop is B, and the outgoing label is SRGB_B[blue_SID0_D]

Node B:

ILM for(MT-blue, D-loopback0)

The entry tag is SRGB_B[blue_SID0_D]

NHLFE: The next hop is D, and the outgoing label is SRGB_D[blue_SID0_D]

D node:

ILM for(MT-blue, D-loopback0)

The entry tag is SRGB_D[blue_SID0_D]

NHLFE: None. Indicates that the SR-LSP has been terminated.

Step S302: When the link SD is faulty, the S node will switch the traffic to the MRT-blue next hop A prepared in advance, that is, the packet will be reported to the destination D-loopback0. The text is forwarded along the MT-blue path SABD.

If the S receives the MT-default SR label packet, it is forwarded based on the ILM for (MT-default, D-loopback0) entry, and the inbound label SRGB_S[default_SID0_D] is exchanged to the outbound label SRGB_A[blue_SID0_D]; if S If the IP packet is received, it is forwarded based on the FTN for (MT-default, D-loopback0) entry, and the label SRGB_A[blue_SID0_D] is directly pressed on the IP header.

Step S303, after receiving the packet, the node A is matched with the ILM_for (MT-blue, D-loopback0) entry according to the top label of the packet, and continues to exchange the top label SRGB_A[blue_SID0_D] of the packet. It is sent to B after SRGB_B[blue_SID0_D].

Step S304, after receiving the packet, the node B matches the ILM for (MT-blue, D-loopback0) entry according to the top label of the packet, and continues to the top label SRGB_B[blue_SID0_D] of the packet. It is sent to D after being exchanged to SRGB_D[blue_SID0_D].

Step S305: After receiving the packet, the D node selects the SLM_D[blue_SID0_D] according to the top label of the packet, and matches the ILM for (MT-blue, D-loopback0) entry to terminate the SR-LSP locally. The IP header continues to forward. Since the IP header is D-loopback0, the packet is sent to the control plane.

In step S306, for the non-node level prefix on the D node, such as D-loopback1, the corresponding three prefix-sids may also be allocated, for example: (MT-default, D-loopback1) prefix-sid, (MT-red , D-loopback1) prefix-sid, (MT-blue, D-loopback1) prefix-sid. And the nodes in the MRT Island are similar to the steps in the step S301 to the D-loopback1, and the forwarding behavior is similar to the steps S302-305, and will not be described again.

Preferably, the optimization method in the embodiment of the present invention may be that the corresponding MT-red node-sid and MT-blue node-sid are additionally allocated only for the node level prefix in the MRT Island. The following describes how each node establishes a corresponding entry for D-loopback1 under this optimization method. Other embodiments will also be described in accordance with this optimization method, and assume that each node's loopback0prefix is a node-level prefix, and other prefixes are non-node-level prefixes.

It should be noted that, according to the foregoing optimization method, if the prefix is a node-level prefix in the area and the advertised node is a node in the MRT Island, the entry is established for the prefix according to step S301, otherwise, Step S307 creates an entry.

Step S307, on the S node, the MT-default next hop in the MT-default topology to D-loopback1 is D, and the MT-blue path (SABD) given in the MT-blue topology is selected to protect the MT-default next. When D is hopped, the next hop of the MRT-FRR backup is the MRT Egress node D and the color flag information is MRT-blue. Assume (MT-default, D-loopback1) that the prefix-sid is default_SID1_D. The following is an example of the entries on some nodes:

S node:

FTN for(MT-default, D-loopback1)

Primary NHLFE: The next hop is D, and the outgoing label is SRGB_D[default_SID1_D]

Prepare NHLFE: The top-level tag is SRGB_S[blue_SID0__D]

The underlying label is SRGB_D[default_SID1_D]

ILM for(MT-default,D-loopback1)

The entry tag is SRGB_S[default_SID1_D]

Primary NHLFE: The next hop is D, and the outgoing label is SRGB_D[default_SID1_D]

Prepare NHLFE: Top-level tag is SRGB_S[blue_SID0_D]

The underlying label is SRGB_D[default_SID1_D]

ILM for(MT-blue, D-loopback0)

The entry tag is SRGB_S[blue_SID0_D]

NHLFE: The next hop is A, and the outgoing label is SRGB_A[blue_SID0_D]

D node:

ILM for(MT-default,D-loopback1)

The entry tag is SRGB_D[default_SID1_D]

NHLFE: None. Indicates that the SR-LSP has been terminated.

Step S308, for the packet sent to the destination D-loopback1, when the link SD fails, the S node will switch the traffic as the MRT ingress node to the MRT-blue path prepared to the remote MRT Egress node D in advance. , that is, the message is forwarded along the MT-blue path SABD.

If the S receives an MT-default SR tag, it is forwarded based on the ILM for (MT-default, D-loopback 1) entry, and the tag SRGB_S[default_SID1_D] is exchanged to the tag SRGB_D[default_SID1_D]. SRGB_A[blue_SID0_D] is sent to the next hop A. If the S receives an IP packet, it is forwarded based on the FTN for (MT-default, D-loopback1) entry and is directly pressed on the IP header. After the label SRGB_D[default_SID1_D], press SRGB_A[blue_SID0_D] and send it to the next hop A.

In step S309, the process of receiving the message by the node A is the same as step S303.

In step S310, the process of receiving the message by the Node B is the same as that of step S304.

In step S311, after receiving the message, the D node continuously plays off the labels SRGB_D[blue_SID0_D] and SRGB_D[default_SID1_D], and continues to forward based on the IP header. Since the IP header is D-loopback0, the packet is sent to the control plane.

According to the foregoing embodiment, when the packet is forwarded along the MRT path, the MRT Island is actually forwarded along the SR-LSP in the corresponding MRT topology, wherein the node-level prefix in the MRT Island is actually the MT-default SR-LSP. It is attached to the MT-blue or MT-red SR-LSP, and the other prefix actually carries its MT-default SR-LSP on the MT-blue or MT-red SR-LSP to the MRT Egress node.

Specific embodiment 2

This embodiment will describe the MRT path forwarding process in which the destination prefix is outside the MRT Island. FIG. 4 is a network topology diagram according to the second embodiment of the present invention. As shown in FIG. 4, the network runs OSPF, and includes two areas, all nodes. The segment routing function is enabled in the corresponding OSPF instance, and the MRT profiles defined in the embodiment of the present invention are enabled in the S, A, B, and C in the area1. S establishes the MRT path to the prefix of the destination node D as the source node, and then protects the SPF main path based on this MRT path. Including the following steps:

In step S401, the SR is enabled in the OSPF instance of all the nodes in area1 and area2. Each node is assigned SRGB.

In the step S402, if the MRT profiles defined in the embodiment of the present invention are enabled in the OSPF instance on the S, A, B, and C nodes in the area1, they form an MRT Island in the area1. In addition, the MRT SR-LSP based on multi-prefix-sid tunneling option is used as the forwarding mechanism in the MRT profile. In addition to the MT-default prefix-sid, each node in the MRT Island additionally allocates the MT-red prefix-sid. With the MT-blue prefix-sid, for example, on the Node B, the three prefix-sids assigned to the node-level prefix B-loopback0 can be respectively recorded as: (MT-default, B-loopback0) node-sid, (MT-red , B-loopback0) node-sid, (MT-blue, B-loopback0) node-sid.

Each node will get the MT-default topology in the area based on the SPF algorithm, and based on The MRT algorithm obtains MT-red and MT-blue topologies. For example, on the S node, the MT-default path to the destination node A is S-A, the MT-blue path is also S-A, and the MT-red path is S-C-B-A.

The entries established by the nodes in the MRT Island for the node-level prefixes in the MRT Island are completely similar to the entries established for the prefix D-loopback0 in the step S301 of the first embodiment, and the destination IP matches the corresponding node-level prefix in the MRT Island. The forwarding behavior of the traffic is also completely similar to steps S302-305, and will not be described again.

Step S403: On the S node, the MT-default next hop in the MT-default topology to the prefix D-loopback0 is C (assuming that the ABR1 in the area1 is the advertised node of the prefix D-loopback0, the MT to the destination node ABR1 is used. The default path to determine the next hop). For prefix D-loopback0, it can be assumed that the remote node selected by the Tunnel Endpoint Selection method (refer to RFC7812) is A, assuming S is the GADAG root in MRT Island, and S<<A<<B<<C<<S, then The MRT-blue path to node A is SA, which can be used to protect the MT-default next hop C above. Assume (MT-default, D-loopback0) prefix-sid is default_SID0_D. The following is an example of the entries on some nodes:

S node:

FTN for(MT-default, D-loopback0)

Primary NHLFE: The next hop is C, and the outgoing label is SRGB_C[default_SID0_D]

Prepare NHLFE: Top-level tag is SRGB_S[blue_SID0_A]

The underlying label is SRGB_A[default_SID0_D]

ILM for(MT-default, D-loopback0)

The entry tag is SRGB_S[default_SID0_D]

Primary NHLFE: The next hop is C, and the outgoing label is SRGB_C[default_SID0_D]

Prepare NHLFE: Top-level tag is SRGB_S[blue_SID0_A]

The underlying label is SRGB_A[default_SID0_D]

ILM for(MT-blue,A-loopback0)

The entry tag is SRGB_S[blue_SID0_A]

NHLFE: The next hop is A, and the outgoing label is SRGB_A[blue_SID0_A]

A node:

ILM for(MT-blue,A-loopback0)

The entry tag is SRGB_A[blue_SID0_A]

NHLFE: None. Indicates that the SR-LSP has been terminated.

ILM for(MT-default, D-loopback0)

The entry tag is SRGB_A[default_SID0_D]

NHLFE: The next hop is ABR3, and the outgoing label is SRGB_ABR3[default_SID0_D]

ABR3 node:

ILM for(MT-default, D-loopback0)

The entry tag is SRGB_ABR3[default_SID0_D]

NHLFE: The next hop is ABR2, and the outgoing label is SRGB_ABR2[default_SID0_D]

ABR2 node:

ILM for(MT-default, D-loopback0)

The entry tag is SRGB_ABR2[default_SID0_D]

NHLFE: The next hop is D, and the outgoing label is SRGB_D[default_SID0_D]

D node:

ILM for(MT-default, D-loopback0)

The entry tag is SRGB_D[default_SID0_D]

NHLFE: None. Indicates that the SR-LSP has been terminated.

Step S404: For the packet sent to the destination D-loopback0, when the link S-C fails, the S node will switch the traffic as the MRT ingress node to the remotely prepared to the far end. The MRT-blue path of the MRT Egress node A begins to forward the message along the MT-blue path S-A.

If the S receives the MT-default SR tag packet, it is forwarded based on the ILM for (MT-default, D-loopback0) entry, and the inbound tag SRGB_S[default_SID0_D] is exchanged to the outbound tag SRGB_A[default_SID0_D]. SRGB_A[blue_SID0_A] is sent to the next hop A. If the S receives an IP packet, it is forwarded based on the FTN for (MT-default, D-loopback0) entry and is directly pressed on the IP header. After the label SRGB_A[default_SID0_D], press SRGB_A[blue_SID0_A] and send it to the next hop A.

Step S405, after receiving the message, the node A bounces off the label SRGB_A[blue_SID0_A], and exchanges the lower layer label SRGB_A[default_SID0_D] into SRGB_ABR3[default_SID0_D] and sends it to the next hop ABR3.

Step S406, after receiving the message, the ABR3 node exchanges the label SRGB_ABR3[default_SID0_D] into SRGB_ABR2[default_SID0_D] and sends it to the next hop ABR2.

Step S407, after receiving the message, the ABR2 node exchanges the label SRGB_ABR2[default_SID0_D] into SRGB_D[default_SID0_D] and sends it to the next hop D.

Step S408: After receiving the packet, the D node bounces off the label SRGB_D[default_SID0_D], and continues forwarding according to the IP header. Since the IP header is D-loopback0, the packet is sent to the control plane.

According to the foregoing embodiment, it is known that when the packet is forwarded along the MRT path, it is actually forwarded along the SR-LSP in the corresponding MRT topology in the MRT Island. After leaving the MRT Island, it will be forwarded along the SR-LSP in the default topology. Conforms to the forwarding rules defined by FEC7812.

Concrete embodiment 3

This embodiment will describe the MRT path forwarding process in which the destination prefix is outside the MRT Island, and in particular, how to implement the cross-domain forwarding rule defined by RFC7812 based on the SR-LSP. Figure 5 is based on The network topology diagram of the third embodiment of the present invention, as shown in FIG. 5, runs OSPF in the network, and includes two areas, and all nodes enable segmentation routing function in the corresponding OSPF instance, where S and A in area1 The B, C, and C enable the MRT profile defined in the embodiment of the present invention. The B, E, D, and F in the area 2 also enable the MRT profile defined in the embodiment of the present invention. S establishes the MRT path to the prefix of the destination node D as the source node, and then protects the SPF main path based on this MRT path. Including the following steps:

In step S501, the SR is enabled in the OSPF instance of all the nodes in area1 and area2. Each node is assigned SRGB.

Step S502: After the MRT profiles defined in the embodiment of the present invention are enabled in the OSPF instance on the S, A, B, and C nodes in the area 1, they form an MRT Island in the area1. In addition, the MRT SR-LSP based on multi-prefix-sid tunneling option is used as the forwarding mechanism in the MRT profile. In addition to the MT-default prefix-sid, each node in the MRT Island additionally allocates the MT-red prefix-sid. With the MT-blue prefix-sid, for example, on the Node B, the three prefix-sids assigned to the node-level prefix B-loopback0 can be respectively recorded as: (MT-default, B-loopback0) node-sid, (MT-red , B-loopback0) node-sid, (MT-blue, B-loopback0) node-sid.

On each node, the MT-default topology in the area is obtained based on the SPF algorithm, and the MT-red and MT-blue topologies are obtained based on the MRT algorithm. For example, on the S node, the MT-default path to the destination node B is S-C-B, the MT-red path is also S-C-B, and the MT-blue path is S-A-B.

The entries established by the nodes in the MRT Island in the area1 for the node-level prefix in the MRT Island are completely similar to the entries established in the step S301 of the first embodiment for the prefix D-loopback0, and the destination IP matches the MRT Island. The forwarding behavior of the traffic of the corresponding node-level prefix is also completely similar to steps S302-305. No longer.

In step S503, the MRT profile defined in the embodiment of the present invention is also enabled in the OSPF instance on each of the nodes B, E, D, and F in area2, and then an MRT Island is formed in area2, and correspondingly generated in area2. MT-default topology, as well as MT-red and MT-blue Topology. Assume that the shortest path from B to D in the default topology is F.

The entries established by the nodes in the MRT Island in the area 2 for the node-level prefix in the MRT Island are completely similar to the entries established in the step S301 of the first embodiment for the prefix D-loopback 0, and the destination IP matches the corresponding in the MRT Island. The forwarding behavior of the traffic of the node-level prefix is also completely similar to steps S302-305. No longer.

Step S504: On the S node, the MT-default next hop in the MT-default topology to the prefix D-loopback0 is C (assuming that the ABR1 in the area1 is the advertised node of the prefix D-loopback0, the MT to the destination node ABR1 is used. The default path to determine the next hop). For prefix D-loopback0, assume that the remote node selected by the Tunnel Endpoint Selection method (refer to RFC7812) is B, assuming S is the GADAG root in MRT Island, and S<<A<<B<<C<<S, then The MRT-blue path of Node B is SAB, which can be used to protect the MT-default next hop C above. Assume (MT-default, D-loopback0) prefix-sid is default_SID0_D. The following is an example of the entries on some nodes:

S node:

FTN for(MT-default, D-loopback0)

Primary NHLFE: The next hop is C, and the outgoing label is SRGB_C[default_SID0_D]

Prepare NHLFE: Top-level entry tag is SRGB_S[blue_SID0_B]

The underlying label is SRGB_B[default_SID0_D]

ILM for(MT-default, D-loopback0)

The entry tag is SRGB_S[default_SID0_D]

Primary NHLFE: The next hop is C, and the outgoing label is SRGB_C[default_SID0_D]

Prepare NHLFE: Top-level entry tag is SRGB_S[blue_SID0_B]

The underlying label is SRGB_B[default_SID0_D]

ILM for(MT-blue,B-loopback0)

The entry tag is SRGB_S[blue_SID0_B]

NHLFE: The next hop is A, and the outgoing label is SRGB_A[blue_SID0_B]

A node:

ILM for(MT-blue,B-loopback0)

The entry tag is SRGB_A[blue_SID0_B]

NHLFE: The next hop is B, and the outgoing label is SRGB_B[blue_SID0_B]

Node B:

ILM for(MT-blue,B-loopback0)

The entry tag is SRGB_B[blue_SID0_B]

NHLFE: None. Indicates that the SR-LSP has been terminated.

ILM for(MT-default, D-loopback0)

The entry tag is SRGB_B[default_SID0_D]

NHLFE: The next hop is F, and the outgoing label is SRGB_F[default_SID0_D]

F node:

ILM for(MT-default, D-loopback0)

The entry tag is SRGB_F[default_SID0_D]

NHLFE: The next hop is D, and the outgoing label is SRGB_D[default_SID0_D]

D node:

ILM for(MT-default, D-loopback0)

The entry tag is SRGB_D[default_SID0_D]

NHLFE: None. Indicates that the SR-LSP has been terminated.

Step S505: For the packet sent to the destination D-loopback0, when the link SC fails, the S node will switch the traffic as the MRT ingress node to the MRT-blue path prepared to the remote MRT Egress Node B in advance. , that is, the message is forwarded along the MT-blue path SAB.

If the S receives the MT-default SR tag packet, it is forwarded based on the ILM for (MT-default, D-loopback0) entry, and the inbound tag SRGB_S[default_SID0_D] is exchanged to the outbound tag SRGB_B[default_SID0_D]. SRGB_A[blue_SID0_B] is sent to the next hop A. If the S receives an IP packet, it is forwarded based on the FTN for (MT-default, D-loopback0) entry and is directly pressed on the IP header. After the label SRGB_B[default_SID0_D], press SRGB_A[blue_SID0_B] and send it to the next hop A.

Step S506, after receiving the message, the node A exchanges the label SRGB_A[blue_SID0_B] into SRGB_B[blue_SID0_B] and sends it to the next hop B.

Step S507, after receiving the message, the Node B bounces off the label SRGB_B[blue_SID0_B], and exchanges the label SRGB_B[default_SID0_D] into SRGB_F[default_SID0_D] and sends it to the next hop F.

Step S508, after receiving the message, the F node exchanges the label SRGB_F[default_SID0_D] into SRGB_D[default_SID0_D] and sends it to the next hop D.

Step S509: After receiving the packet, the D node bounces off the label SRGB_D[default_SID0_D], and continues to forward the packet based on the IP header. Since the IP header is D-loopback0, the packet is sent to the control plane.

According to the foregoing embodiment, it is known that when the packet is forwarded along the MRT path, the MRT Island in the area1 is actually forwarded along the SR-LSP in the corresponding MRT topology, and after leaving the area1 to enter the area2, the SR in the default topology will be along. LSP forwarding. Conforms to the forwarding rules defined by FEC7812.

Through the description of the above embodiments, those skilled in the art can clearly understand that the method according to the above embodiment can be implemented by means of software plus a necessary general hardware platform, and of course, by hardware, but in many cases, the former is A better implementation. Based on such understanding, the technical solution of the present invention, which is essential or contributes to the prior art, may be embodied in the form of a software product stored in a storage medium (such as ROM/RAM, disk, The optical disc includes a plurality of instructions for causing a terminal device (which may be a mobile phone, a computer, a server, or a network device, etc.) to perform various embodiments of the present invention. The method described.

In this embodiment, a message forwarding device is also provided, which is used to implement the foregoing embodiments and preferred embodiments, and has not been described again. As used below, the term "module" may implement a combination of software and/or hardware of a predetermined function. Although the apparatus described in the following embodiments is preferably implemented in software, hardware, or a combination of software and hardware, is also possible and contemplated.

FIG. 6 is a structural block diagram of a message forwarding apparatus according to an embodiment of the present invention. The apparatus may be applied to a first node. As shown in FIG. 6, the apparatus includes a receiving module 62, a searching module 64, and a forwarding module 66. Explain the device:

The receiving module 62 is configured to receive the packet to be forwarded, where the destination address of the packet is the second node, and the searching module 64 is connected to the receiving module 62, and is configured to search for the packet in the pre-generated topology. Corresponding target topology, wherein the pre-generated topology comprises: a first topology and a second topology generated according to a maximum redundancy tree MRT algorithm, and a third topology obtained according to a shortest path first SPF algorithm, the first topology and the first topology The second topology and the third topology are different from each other; the forwarding module 66 is connected to the foregoing searching module 64, configured to search for the next hop node for forwarding to the second node in the target topology, and to perform the foregoing according to a predetermined forwarding mechanism. The message is forwarded to the next hop node, wherein the predetermined forwarding mechanism adopts a segmented route forwarding mechanism based on the tunnel nesting manner of the prefix-sid per prefix per topology.

FIG. 7 is a block diagram showing a preferred structure of a message forwarding device according to an embodiment of the present invention. As shown in FIG. 7 (FIG. 7 is only an example), the device includes a determining module in addition to all the modules shown in FIG. 6. 72, the device is described below:

The determining module 72 is connected to the receiving module 62, and is configured to determine, according to the foregoing MRT algorithm, a route from the first topology to the destination address and a route from the second topology to the destination address, to protect the third topology to the destination address. Protecting the route of the route, and determining that the topology corresponding to the protection route is a protection topology; and/or determining the route from the first topology to the tunnel end point and the route from the second topology to the tunnel end point according to the color flag information. Protecting the protection route of the route to the destination address in the foregoing third topology, and determining the topology corresponding to the protection route is to protect The topology of the tunnel, wherein the tunnel end point is a remote node selected by the first node for the protection destination address, and the remote node is loop-free for the fault point, and the first node is used to the remote end when the fault occurs. The MRT tunnel of the node encapsulates the packet.

In an optional embodiment, the foregoing searching module 64 may search for a target topology corresponding to the foregoing packet in a pre-generated topology by determining whether a link for reaching the second node in the third topology is present. The fault is determined; in the case that it is determined that there is no fault, the third topology is determined to be the target topology; and/or, in the case that the fault is determined, the protection topology is determined to be the target topology. In this embodiment, when the link is faulty, the packet can be forwarded according to the default topology. After the link is faulty, the protection topology is used to forward the packet.

In an optional embodiment, the foregoing apparatus further includes a first processing module, configured to: before receiving the packet to be forwarded, generate a first topology and a second topology according to an MRT algorithm, and generate and generate according to an SPF algorithm. The third topology.

In an optional embodiment, the first processing module may generate the first topology and the second topology according to the foregoing MRT algorithm, and generate a third topology according to the SPF algorithm: determining the MRT where the first node is located. Island, where the MRT Island is enabled by the OSPF or ISIS instance at the first node and other nodes at the same domain area or level as the first node, and the maximum redundant tree profile MRT After the profile is formed by the first node and other nodes in the area or level where the first node is located; generating the first topology and the second topology based on the MRT Island running MRT algorithm, and running the SPF algorithm based on the above area or level Generate a third topology.

In an optional embodiment, the foregoing predetermined forwarding mechanism is specified in the MRT profile. That is, the segmented route forwarding mechanism based on the tunnel nesting manner of the prefix-sid per prefix per topology is adopted.

In an optional embodiment, the apparatus further includes a second processing module, configured to perform at least one of: assigning a first prefix-sid to the first topology for a node-level prefix local to the first node, and The first prefix-sid is at the domain or level of the MRT Island. Flooding; assigning a second prefix-sid to the second topology for the node-level prefix local to the first node, and flooding the second prefix-sid in the domain or level of the MRT Island; The local node-level and non-node-level prefix allocates a third prefix-sid for the third topology, and floods the third prefix-sid in all domain areas or levels of the first node; receiving the above on other nodes The prefix-sid of the pre-generated topology records the prefix-sid of the pre-generated topology on the other node and continues to advertise the prefix-sid of the pre-generated topology on the other node to nodes other than the other nodes. In this embodiment, the first prefix-sid, the second prefix-sid, and the third prefix-sid are independent of each other.

In an optional embodiment, the forwarding module 66 may forward the packet to the next hop node by: determining an outgoing label of the first node that matches the packet; and using the outgoing label of the first node. The packet is encapsulated into the foregoing packet, and the encapsulated packet is sent to the next hop node. In this embodiment, the label encapsulation manner is different for different types of packets.

In an optional embodiment, the forwarding module 66 may determine, according to the following manner, an outgoing label of the first node that matches the packet: when the target topology is the third topology, the corresponding target topology of the first node is The label is calculated by the first node based on the third prefix index prefix-sid of the destination prefix prefix corresponding to the destination address and the SRGB of the next hop node.

In an optional embodiment, the forwarding module 66 may determine, according to the manner, the outgoing label of the first node that matches the foregoing packet: when the target topology is the first topology or the second topology: if the second node is When the node in the MRT Island is the node prefix prefix of the second node, the first node determines the outbound label of the first node corresponding to the target topology by: The outbound label of the corresponding target topology is calculated by the first node based on the prefix index prefix-sid of the corresponding target topology of the node-level prefix prefix of the second node and the SRGB of the next hop node; if the second node is not the MRT Island When the destination prefix corresponding to the node or the destination address is the non-node level prefix of the second node, the first node determines whether the next hop node is a node other than the MRT Island; when the judgment result is no, the first node Determining an outbound label of the first node corresponding to the target topology by: the first node corresponding to the target topology The outgoing label is the label stack, and the outer label is the label of the first node to the tunnel end point, and the inner label is a label of the tunnel end point to the destination prefix prefix; wherein the outer label is prefixed by the prefix index of the corresponding target topology of the first node based on the node level prefix of the tunnel end point and the next to the tunnel end point in the target topology The SRGB calculation of the hop node is obtained by the first node based on the prefix index prefix-sid of the third topology based on the destination prefix prefix and the SRGB of the tunnel end point; when the judgment result is yes, the first node passes The outbound label of the corresponding target topology of the first node is determined as follows: the outbound label of the corresponding target topology of the first node is determined by the first node based on the prefix index prefix-sid and the next hop node of the corresponding third topology of the destination prefix prefix The SRGB is calculated.

In an optional embodiment, the forwarding module 66 may encapsulate the outgoing label of the first node into the packet by using at least one of the following manners: when the packet type of the packet is an Internet Protocol IP packet, The outbound label of the first node is pressed on the IP header of the IP packet; when the packet type of the packet is a fragmented route SR label, the top label of the label stack of the SR label is replaced. The outgoing label of the first node.

In an optional embodiment, the forwarding module 66 may determine the outgoing label of the first node by: when the first node and the second node are the same node, the first node is determined according to the target topology. The one-hop node is the first node, and the first node does not have a label.

In an optional embodiment, the foregoing apparatus further includes a third processing module, configured to: when the first node and the second node are the same node, perform the following operations: when the packet type of the packet is an Internet Protocol IP address When the packet is sent, the first node sends the packet to the control plane of the first node; and/or, when the packet type of the packet is a fragmented route SR label packet, the first node sends the SR label. The stack top label of the label stack of the message pops up, and continues to be forwarded based on the lower layer label or IP header lookup table of the label stack of the above message.

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

Embodiments of the present invention also provide a storage medium. Optionally, in this embodiment, on The storage medium may be arranged to store program code for performing the steps described above.

Optionally, in the embodiment, the foregoing storage medium may include, but is not limited to, a USB flash drive, a Read-Only Memory (ROM), and a Random Access Memory (RAM). A variety of media that can store program code, such as a hard disk, a disk, or an optical disk.

Optionally, in the embodiment, the processor performs the above steps according to the stored program code in the storage medium.

For example, the specific examples in this embodiment may refer to the examples described in the foregoing embodiments and the optional embodiments, and details are not described herein again.

The method in the embodiment of the present invention can fill the gap between the segmentation route and the MRT technology in the related technology, and provides a valuable exploration for the evolution of the future network.

It will be apparent to those skilled in the art that the various modules or steps of the present invention described above can be implemented by a general-purpose computing device that can be centralized on a single computing device or distributed across a network of multiple computing devices. Alternatively, they may be implemented by program code executable by the computing device such that they may be stored in the storage device by the computing device and, in some cases, may be different from the order herein. The steps shown or described are performed, or they are separately fabricated into individual integrated circuit modules, or a plurality of modules or steps thereof are fabricated as a single integrated circuit module. Thus, the invention is not limited to any specific combination of hardware and software.

The above description is only the preferred embodiment of the present invention, and is not intended to limit the present invention, and various modifications and changes can be made to the present invention. Any modifications, equivalent substitutions, improvements, etc. made within the spirit and scope of the present invention are intended to be included within the scope of the present invention.

Industrial applicability

As described above, the packet forwarding method and apparatus provided by the embodiments of the present invention have the following beneficial effects: the MRT function is introduced in the segment routing network, thereby implementing the segment routing network and The purpose of combining MTR functions.

Claims (16)

A packet forwarding method includes: The first node receives the packet to be forwarded, where the destination address of the packet is the second node; The first node searches for a target topology corresponding to the packet in a pre-generated topology, where the pre-generated topology includes: a first topology and a second topology generated according to a maximum redundancy tree MRT algorithm, According to a third topology obtained by the shortest path first SPF algorithm, the first topology and the second topology and the third topology are different from each other; The first node searches for a next hop node for forwarding to the second node in the target topology, and forwards the message to the next hop node based on a predetermined forwarding mechanism, where The scheduled forwarding mechanism adopts a segmented route forwarding mechanism based on the tunnel nesting manner of the prefix-sid per prefix per topology. The method of claim 1 wherein the method further comprises: Determining, by the MRT algorithm, the route from the first topology to the destination address and the route in the second topology to the destination address according to the MRT algorithm, for protecting the third topology to Protecting the route of the route of the destination address, and determining that the topology corresponding to the protection route is a protection topology; and/or, Determining, by the first node, the route from the first topology to the tunnel end point and the route in the second topology to the tunnel end point according to the color flag information, for protecting the third topology to the destination address Determining the route of the route, and determining that the topology corresponding to the protection route is a protection topology, where the tunnel end point is a remote node selected by the first node as a protection destination address, and the remote node is directed to a fault point. The loop-free loop-free, the first node uses the MRT tunnel encapsulation message to the remote node when the fault occurs. The method according to claim 2, wherein the searching, by the first node, the target topology corresponding to the packet in a pre-generated topology comprises: Determining, by the first node, whether a link for reaching the second node in the third topology is faulty; In the case that it is determined that there is no failure, the first node determines that the third topology is the target topology; and/or, The first node determines that the protection topology is the target topology in the event that a failure is determined. The method according to claim 1, wherein the method further comprises: before the receiving, by the first node, the message to be forwarded, the method further comprises: The first node generates the first topology and the second topology according to the MRT algorithm, and generates the third topology according to the SPF algorithm. The method according to claim 4, wherein the first node generates the first topology and the second topology according to the MRT algorithm, and generates the third topology according to the SPF algorithm, including: Determining, by the first node, an MRT Island where the first node is located, where the MRT Island is by using the first node and other nodes at the same domain area or level as the first node After the shortest path first OSPF or the intermediate system to the intermediate system ISIS instance enables the segment routing SR and the maximum redundancy tree configuration file MRT profile, the first node and the location are within the area or level where the first node is located. Said that other nodes are mutually negotiated; The first node generates the first topology and the second topology by running the MRT algorithm based on the MRT Island, and generating the third topology by running the SPF algorithm based on the area or level. The method of claim 5 wherein said predetermined forwarding mechanism is employed in said MRT profile. The method of claim 5, wherein the method further comprises at least one of the following: The first node is a node-level prefix local to the first node, and allocates a first prefix-sid to the first topology, and the first prefix-sid is in a domain area or a hierarchy level where the MRT Island is located. Flooding; The first node is a node-level prefix local to the first node, and a second prefix-sid is allocated to the second topology, and the second prefix-sid is in a domain area or a hierarchy level where the MRT Island is located. Flooding; The first node is a node-level and non-node-level prefix local to the first node, and a third prefix-sid is allocated to the third topology, and the third prefix-sid is located at the first node. Flooding in all domain or level levels; The first node receives a prefix-sid of the pre-generated topology on other nodes, records a prefix-sid of the pre-generated topology on the other nodes, and the pre-generated on the other nodes The prefix-sid of the topology continues to be advertised to nodes other than the other nodes. The method of claim 1, wherein the forwarding, by the first node, the message to the next hop node comprises: Determining, by the first node, an outgoing label of the first node that matches the packet; The first node encapsulates the outgoing label of the first node to the packet, and sends the encapsulated packet to the next hop node. The method according to claim 8, wherein the first node determines that the outgoing label of the first node that matches the packet comprises: When the target topology is the third topology, the outbound label of the first node corresponding to the target topology is determined by the first node based on the third prefix index prefix-sid of the destination prefix prefix corresponding to the destination address. The SRGB of the next hop node is calculated. The method according to claim 8, wherein the first node determines that the outgoing label of the first node that matches the packet comprises: When the target topology is the first topology or the second topology: If the second node is a node in the MRT Island and the destination prefix prefix corresponding to the destination address is a node-level prefix prefix of the second node, the first node determines the first manner by: An outbound label of the node corresponding to the target topology: an outbound label of the first node corresponding to the target topology is prefixed by the first node to the target topology based on a node level prefix prefix of the second node Index prefix-sid and SRGB calculation of the next hop node are obtained; If the second node is not a node in the MRT Island or a destination prefix prefix corresponding to the destination address is a non-node level prefix of the second node, the first node determines the next hop Whether the node is a node outside the MRT Island; When the determination result is no, the first node determines, according to the manner, the outbound label of the first node corresponding to the target topology: the outbound label of the first node corresponding to the target topology is a label stack, and The layer label is a label of the first node to the tunnel end point, and the inner layer label is a label of the tunnel end point to the destination prefix prefix; wherein the outer layer label is based on the tunnel end point by the first node a prefix index prefix of the node level prefix corresponding to the target topology and an SRGB of the next hop node in the target topology to the tunnel end point, where the inner layer label is based on the first node Determining, by the prefix prefix, the prefix index prefix-sid of the third topology and the SRGB of the tunnel end point; When the result of the determination is YES, the first node determines an outbound label of the first node corresponding to the target topology by: the outbound label of the first node corresponding to the target topology is by the first The node is calculated based on the prefix index prefix-sid of the third topology and the SRGB of the next hop node of the destination prefix prefix. The method according to claim 8, wherein the first node encapsulates the outgoing label of the first node onto the message to include at least one of the following: When the packet type of the packet is an Internet Protocol IP packet, the outbound label of the first node is pressed on the IP header of the IP packet; When the packet type of the packet is a fragmented route SR label packet, the SR is The top label of the label stack of the label message is replaced with the outgoing label of the first node. The method of claim 8, wherein the determining, by the first node, the outgoing label of the first node comprises: When the first node and the second node are the same node, the next hop node determined by the first node based on the target topology is the first node, and the first node does not label. The method of claim 1 wherein the method further comprises: When the first node and the second node are the same node, the first node sends the packet to the office when the packet type of the packet is an Internet Protocol IP packet. The control plane of the first node; and/or, when the packet type of the packet is a fragmented route SR label message, the first node sets the top label of the label stack of the SR label message Pop up and continue forwarding based on the lower label or IP header lookup table of the label stack of the message. A packet forwarding device is applied to the first node, and includes: a receiving module, configured to receive a packet to be forwarded, where the destination address of the packet is a second node; a search module, configured to search for a target topology corresponding to the packet in a pre-generated topology, where the pre-generated topology includes: a first topology and a second topology generated according to a maximum redundancy tree MRT algorithm, According to a third topology obtained by the shortest path first SPF algorithm, the first topology and the second topology and the third topology are different from each other; a forwarding module, configured to look up a next hop node for forwarding to the second node in the target topology, and forward the message to the next hop node based on a predetermined forwarding mechanism, where The scheduled forwarding mechanism adopts a segmented route forwarding mechanism based on the tunnel nesting manner of the prefix-sid per prefix per topology. The apparatus of claim 14 wherein said apparatus further comprises: a determining module, configured to determine, according to the MRT algorithm, a route from the first topology to the destination address and a route to the destination address in the second topology to protect the third topology a route for protecting the route of the destination address, and determining that the topology corresponding to the protection route is a protection topology; and/or, according to the color flag information, the route from the first topology to the tunnel end point and the second topology Determining, by the route to the end of the tunnel, a protection route for protecting the route to the destination address in the third topology, and determining that the topology corresponding to the protection route is a protection topology, where the tunnel endpoint is the A remote node selected by a node for protecting a destination address, the remote node being loop-free for a fault point, and the first node using an MRT tunnel encapsulation to the remote node when a fault occurs Message. A storage medium, the storage medium comprising a stored program, wherein the program is executed to perform the method of any one of claims 1 to 13.

Images