CN111131053B

CN111131053B - Path selection method and device and router

Info

Publication number: CN111131053B
Application number: CN201811272011.XA
Authority: CN
Inventors: 黄灿灿; 陈华南; 伍佑明; 龚霞; 朱永庆
Original assignee: China Telecom Corp Ltd
Current assignee: China Telecom Corp Ltd
Priority date: 2018-10-30
Filing date: 2018-10-30
Publication date: 2021-09-14
Anticipated expiration: 2038-10-30
Also published as: CN111131053A

Abstract

The present disclosure relates to the field of multicast, and in particular, to a method and an apparatus for selecting a path by bit index explicit replication equal cost multipath, and a router. Under the BIER ECMP scene, the forwarding rule of the message is changed by marking, the message is selected with equal cost and multiple paths according to the entropy value, the influence of the BFRID value on some target nodes by the state of the target node smaller than the target node is avoided, and the message is forwarded according to the fixed path. Therefore, the original forwarding table is reserved, the forwarding table does not need to be split, and the memory resource of the router is saved.

Description

Path selection method and device and router

Technical Field

The present disclosure relates to the multicast field, and in particular, to a method and an apparatus for selecting an Equal Cost Multiple Path (ECMP) Path by Bit Index Explicit Replication (BIER).

Background

The BIER is a new multicast message forwarding technology, which makes the intermediate router no longer need to maintain the multicast group state, and greatly reduces the resource and power consumption of the router.

The Forwarding mechanism of BIER is based on the entry (entry) corresponding to the first 1 on the right of the BFRID (Bit Forwarding Router ID, Bit Forwarding routing identifier) to perform table lookup. However, in an ECMP scenario, when a certain destination node has multiple equivalent paths, the path of a packet arriving at the destination node may be affected by other destination nodes whose BFRID is smaller than itself, and especially when a link fails, unnecessary packet loss may be caused.

In order to solve the problem, the related technology splits the forwarding table according to the number of the ECMP paths, and disperses the ECMP paths into the split forwarding tables, so that an entry in each forwarding table has only a unique next hop, and for a specific receiver, the multicast message is forwarded always following the same path, thereby avoiding that the receiver with a high BFRID value is influenced by the receiver with a low BFRID value.

Disclosure of Invention

The inventor finds that the number of forwarding tables in the related art is in proportion to the number of ECMP paths, and in a large network, a large number of ECMP paths exist, a large number of forwarding tables are generated, and a large amount of memory resources of a router are required to be occupied to maintain the forwarding tables.

In view of this, the present disclosure provides a path selection scheme, in a BIER ECMP scenario, a forwarding rule of a message is changed by a label, and the message selects an equivalent multipath according to an entropy value, so as to avoid that some destination nodes are affected by a state where a BFRID value is smaller than the destination node of the destination node, and implement that the message is forwarded according to a fixed path. Therefore, the original forwarding table is reserved, the forwarding table does not need to be split, and the memory resource of the router is saved.

Some embodiments of the present disclosure provide a path selection method for bit-indexed explicit replication of equal cost multipath, including:

searching an inlet corresponding to the message in an on-site forwarding routing table;

judging whether the bit mask corresponding to the searched entry is marked with an equivalent multipath mark;

if the equivalent multipath mark is marked, searching an entry with equivalent multipath;

and selecting a path from the equal cost multiple paths according to the entropy value of the message to forward the message.

In some embodiments, the equal cost multipath marker is marked on the bit mask of the equal cost multipath.

In some embodiments, finding an entry with equal cost multipaths comprises:

and searching corresponding entries from the second 1 on the right in the bit forwarding routing identifier of the edge router serving as a message receiver, and if the entry does not have the equivalent multipath, continuously searching the corresponding entry of the next 1 to the left until the entry with the equivalent multipath is searched.

In some embodiments, selecting a path from the equal cost multiple paths for message forwarding according to the entropy of the message includes:

calculating the hash value of the quintuple information of the message;

calculating a remainder of the hash value divided by the number of equal cost multipaths;

and selecting a corresponding path from the equal cost multipath according to the remainder to forward the message.

In some embodiments, the looking up the entry corresponding to the packet in the ingress forwarding routing table includes:

and searching an entry corresponding to the first 1 on the right in the bit forwarding routing identifier of the edge router serving as the message receiver in the bit forwarding routing table.

Some embodiments of the present disclosure provide a path selection apparatus for bit-indexed explicit replication of equal cost multipath, including:

the first searching module is configured to search an inlet corresponding to the message in the on-bit forwarding routing table;

the judging module is configured to judge whether the bit mask corresponding to the searched entry is marked with an equivalent multipath mark;

a second searching module configured to search for an entry having an equal cost multipath if the equal cost multipath marker is marked;

and the path selection module is configured to select one path from the equal cost multiple paths according to the entropy value of the message to forward the message.

In some embodiments, the second lookup module is configured to:

In some embodiments, a path selection module configured to:

calculating the hash value of the quintuple information of the message;

a memory; and

a processor coupled to the memory, the processor configured to perform the path selection method of any of the preceding embodiments based on instructions stored in the memory.

Some embodiments of the present disclosure provide a router including the path selection device of any of the foregoing embodiments.

Some embodiments of the present disclosure propose a computer-readable storage medium having stored thereon a computer program which, when executed by a processor, implements the path selection method of any of the preceding embodiments.

Drawings

The drawings that will be used in the description of the embodiments or the related art will be briefly described below. The present disclosure will be more clearly understood from the following detailed description, which proceeds with reference to the accompanying drawings,

it is to be understood that the drawings in the following description are merely exemplary of the disclosure, and that other drawings may be derived from those drawings by one of ordinary skill in the art without undue inventive faculty.

Fig. 1 is a schematic diagram of a path selection method of BIER ECMP according to some embodiments of the disclosure.

Fig. 2 is a schematic diagram of a BIER domain and Bit Forwarding Routing (BFR) tables on each router therein according to some embodiments of the present disclosure.

Fig. 3 is a schematic diagram of a related art solution.

Figure 4 is a label diagram of a Bit Forwarding Routing (BFR) table of some embodiments of the present disclosure.

Fig. 5 is a schematic diagram of a path selection device of BIER ECMP according to some embodiments of the disclosure.

Fig. 6 is a schematic diagram of a path selection device of BIER ECMP according to some embodiments of the disclosure.

Detailed Description

The technical solutions in the embodiments of the present disclosure will be clearly and completely described below with reference to the drawings in the embodiments of the present disclosure.

The method comprises the steps of changing a forwarding rule of a message through a mark in a BIER ECMP scene, selecting equivalent multi-path for the message according to an entropy value, avoiding the influence of the state that BFRID values of some target nodes are smaller than the target nodes of the target nodes, and realizing the forwarding of the message according to a fixed path. Therefore, the original forwarding table is reserved, the forwarding table does not need to be split, and the memory resource of the router is saved.

Fig. 1 is a schematic diagram of a path selection method of BIER ECMP according to some embodiments of the disclosure. As shown in fig. 1, the method of this embodiment includes:

in step 110, the ingress corresponding to the packet is looked up in the forwarding-in-place routing table.

The bit Forwarding routing table is a bfr (bit Forwarding router) table, which is called a Forwarding table for short.

In some embodiments, the looking up the entry corresponding to the packet in the ingress forwarding routing table includes: and the bit forwarding routing table searches an entry corresponding to the first 1 on the right side in the bit forwarding routing identifier (namely BFRID) of the edge router serving as a message receiver.

BFRID, abbreviated as ID, is also called bit string (bit string), among others.

In step 120, it is determined whether the bit mask corresponding to the found entry is marked with an equal-cost multi-path mark.

In some embodiments, the equal cost multipath marker is marked on a Bit Mask (BM) of the equal cost multipath, i.e., the Bit Mask that is the same as the Bit Mask of the equal cost multipath is marked with the equal cost multipath marker. The present disclosure does not limit the labeling form of the equal cost multipath mark.

Wherein, BM is also denoted as F-BM (Forwarding-Bit Mask).

At step 130, if labeled with an equal cost multipath label, an entry with an equal cost multipath is found.

In some embodiments, finding an entry with equal cost multipaths comprises: starting from the second right 1 in the bit forwarding route identifier of the edge router as the message receiver, searching for a corresponding entry, if the entry does not have an equivalent multipath, continuing to search for the entry corresponding to the next 1 to the left, for example, continuing to search for the entry corresponding to the third right 1 in the bit forwarding route identifier until an entry having an equivalent multipath is found.

In step 140, a path is selected from the equal cost multiple paths according to the entropy of the packet for packet forwarding.

firstly, calculating a hash value of quintuple information of a message; then, calculating the remainder of the Hash value divided by the number of the equal cost multipath, namely performing modular operation; then, since the number of the different remainders is equal to the number of the equal cost multiple paths, the corresponding path can be selected from the equal cost multiple paths according to the remainders to forward the message.

Some application examples are listed below.

As shown in fig. 2, BIER domain includes router A, B, C, D, E, F, where router A, D, E, F is an edge router, router a is assumed to be an ingress router, D, E, F are egress routers, and router D, E, F has BFRIDs (abbreviated IDs) of 0001, 0010, 0100, respectively, where the ID of the router is the smallest of all destinations. The BFRA forwarding table, the BFRB forwarding table, and the BFRC forwarding table are BFR tables on router A, B, C, respectively. The contents of each BFR table are shown in fig. 2.

According to the BFRB forwarding table, the path from A to D is A-B-C-D, and the ECMP path from A to F comprises: A-B-C-F and A-B-E-F.

When only F receives (namely when the receiver only has F), the entry 2 is checked, and the path to the F message is A-B-E-F or A-B-C-F.

When there are D and F to receive (i.e. when the receiver has D and F), the rightmost bit is matched, and since D is smaller than the ID value of F, the lookup is performed based on the value of D. Looking at entry1 here, the path of the message to F can only go A-B-C-F. This is the case where the destination node is affected by the state of the BFRID value being smaller than its own destination node, as described above.

When a fault occurs between the router C and the router F, the router B does not know that the fault occurs between the router C and the router F in a short time, so that the next hop is continuously selected to forward the message to the router C, and the message to the router F is discarded on the router C. If no destination D exists, B selects the next hop to be the router E for message forwarding, and the message to F is smoothly forwarded through A-B-E-F.

For the above problem, as shown in fig. 3, in the related art, the forwarding table is split according to the number of ECMP paths, and the ECMP paths are dispersed into the multiple split forwarding tables, so that an entry in each forwarding table has only a unique next hop, and for a specific receiver, the multicast packet is forwarded always following the same path, so that the receiver with a high BFRID value is prevented from being affected by the receiver with a low BFRID value. The number of forwarding tables in the related art is proportional to the number of ECMP paths, and in a large network, a large number of ECMP paths exist, a large number of forwarding tables are generated, and a large amount of memory resources of a router are required to be occupied to maintain the forwarding tables.

According to the scheme of the disclosure, marks are marked on the F-BMs of the equivalent multipath (called equivalent multipath marks), and both 0011 and 0110 are marked with a mark "×" as shown in fig. 4.

When a message reaches router B, if the F-BM corresponding to the searched entry is marked, it is one of ECMP paths of a certain entry.

Then, an entry with equal cost multipath is searched, and the searching method comprises the following steps: and searching the second 1 of the right number in the Bitstring to find the corresponding entry, and if the entry does not have ECMP, continuing to search the third 1 of the right number in the Bitstring until the entry with the ECMP path is found. As shown in fig. 4, entry 2 is found, and entry 2 is the entry with the ECMP path.

And then, selecting one of the next hops for forwarding according to the entropy value of the message. For example, assume that the hash value of the quintuple information of the packet is 5, and the number of equal cost multipaths is 2, and 5 modulo 2 yields 1. The result of the modulo operation has two cases, 0 and 1, assuming 0 corresponds to path B-C-F and 1 corresponds to path B-E-F. The path B-E-F is selected according to the result 1 of the modulo operation, i.e. the down-hop selection E of B.

For a specific multicast flow, its entropy value is determined, so the next hop of its selection is determined, thus it can be guaranteed that the traffic always follows the same path to forward.

Therefore, under the BIER ECMP scene, the forwarding rule of the message is changed by marking, the message is subjected to equal cost multi-path selection according to the entropy value, the influence of the BFRID value on some target nodes by the state of the target node smaller than the target node is avoided, and the message is forwarded according to the fixed path. Therefore, the original forwarding table is reserved, the forwarding table does not need to be split, and the memory resource of the router is saved.

Fig. 5 is a schematic diagram of a path selection device with bit-indexed explicit replication of equal cost multipaths according to some embodiments of the present disclosure.

As shown in fig. 5, the apparatus 500 of this embodiment includes:

the first lookup module 510 is configured to lookup an entry corresponding to the packet in the in-place forwarding routing table.

The determining module 520 is configured to determine whether the bit mask corresponding to the found entry is marked with an equal-cost multi-path mark. Wherein the equal cost multipath marker is marked on the bit mask of the equal cost multipath.

A second lookup module 530 configured to lookup an entry having an equal cost multipath if labeled with an equal cost multipath label.

And the path selection module 540 is configured to select one path from the equal cost multiple paths according to the entropy of the message to forward the message.

The first lookup module 510 is configured to lookup, in the bit forwarding routing table, an entry corresponding to the first 1 on the right in the bit forwarding routing identifier of the edge router as the message receiver.

In some embodiments, the second lookup module 530 is configured to: and searching corresponding entries from the second 1 on the right in the bit forwarding routing identifier of the edge router serving as a message receiver, and if the entry does not have the equivalent multipath, continuously searching the corresponding entry of the next 1 to the left until the entry with the equivalent multipath is searched.

In some embodiments, the path selection module 540 is configured to:

calculating the hash value of the quintuple information of the message;

Fig. 6 is a schematic diagram of a path selection device with bit-indexed explicit replication of equal cost multipaths according to some embodiments of the present disclosure.

As shown in fig. 6, the apparatus 600 of this embodiment includes: a memory 610 and a processor 620 coupled to the memory 610, the processor 620 being configured to execute the path selection method of any of the foregoing embodiments based on instructions stored in the memory 610.

Memory 610 may include, for example, system memory, fixed non-volatile storage media, and the like. The system memory stores, for example, an operating system, an application program, a Boot Loader (Boot Loader), and other programs.

The apparatus 600 may also include an input-output interface 630, a network interface 640, a storage interface 650, and the like. These

interfaces

630, 640, 650 and the connections between the memory 610 and the processor 620 may be, for example, via a bus 660. The input/output interface 630 provides a connection interface for input/output devices such as a display, a mouse, a keyboard, and a touch screen. The network interface 640 provides a connection interface for various networking devices. The storage interface 650 provides a connection interface for external storage devices such as an SD card and a usb disk.

As will be appreciated by one skilled in the art, embodiments of the present disclosure may be provided as a method, system, or computer program product. Accordingly, the present disclosure may take the form of an entirely hardware embodiment, an entirely software embodiment or an embodiment combining software and hardware aspects. Furthermore, the present disclosure may take the form of a computer program product embodied on one or more computer-usable non-transitory storage media (including, but not limited to, disk storage, CD-ROM, optical storage, and the like) having computer-usable program code embodied therein.

The present disclosure is described with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems), and computer program products according to embodiments of the disclosure. It will be understood that each flow and/or block of the flow diagrams and/or block diagrams, and combinations of flows and/or blocks in the flow diagrams and/or block diagrams, can be implemented by computer program instructions. These computer program instructions may be provided to a processor of a general purpose computer, special purpose computer, embedded processor, or other programmable data processing apparatus to produce a machine, such that the instructions, which execute via the processor of the computer or other programmable data processing apparatus, create means for implementing the functions specified in the flowchart flow or flows and/or block diagram block or blocks.

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

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

The above description is only exemplary of the present disclosure and is not intended to limit the present disclosure, so that any modification, equivalent replacement, or improvement made within the spirit and principle of the present disclosure should be included in the scope of the present disclosure.

Claims

1. A path selection method for bit-indexed explicit replication of equal cost multipath, comprising:

2. The method of claim 1, wherein the equal cost multipath marker is marked on a bit mask of the equal cost multipath.

3. The method of claim 1, wherein finding an entry with equal cost multipaths comprises:

4. The method of claim 1, wherein selecting a path from the equal cost multipaths for message forwarding based on the entropy of the message comprises:

calculating the hash value of the quintuple information of the message;

5. The method of claim 1, wherein looking up the corresponding entry of the packet in the ingress forwarding routing table comprises:

6. A path selection device for bit indexed explicit replication of equal cost multipaths, comprising:

7. The apparatus of claim 6, wherein the second lookup module is configured to:

8. The apparatus of claim 6, wherein the path selection module is configured to:

calculating the hash value of the quintuple information of the message;

9. A path selection device for bit indexed explicit replication of equal cost multipaths, comprising:

a memory; and

a processor coupled to the memory, the processor configured to perform the path selection method of any of claims 1-5 based on instructions stored in the memory.

10. A router comprising a path selection device as claimed in any one of claims 6 to 9.

11. A computer-readable storage medium, on which a computer program is stored which, when being executed by a processor, carries out the path selection method according to any one of claims 1 to 5.