CN115468572A - Path planning method and related equipment - Google Patents

Abstract

The embodiment of the application provides a path planning method and related equipment, wherein the method comprises the following steps: configuring a tunnel equivalent multi-path ECMP group for traffic load balancing on first network equipment, wherein the member of the tunnel ECMP group consists of a plurality of tunnels, the plurality of tunnels comprise a first tunnel, and the first tunnel forwards traffic to a destination address based on a first path; when the first path fails, calculating a second path according to the path information of each path passed by each tunnel except the first tunnel, wherein the second path is not intersected with each path; the first tunnel is rerouted to the second path. The method and the device can relieve network congestion.

Description

Path planning method and related equipment

technical field

The present invention relates to the field of communication technology, in particular to a path planning method and related equipment.

Background technique

Load balance refers to that when a network node forwards traffic, it distributes the load (traffic) destined for the same destination address to multiple links/paths for forwarding. Load balancing technology is widely used because it can flexibly expand link resources, increase network capacity, and improve network reliability. According to the type of sharing path, it can be divided into trunk load balancing, routing load balancing, tunnel load balancing, etc.

Wherein, tunnel load balancing means that in a virtual private network (virtual private network, VPN) scenario, there are multiple tunnels to the same destination node on the ingress node, and traffic is shared among the multiple tunnels for forwarding. Tunneling provides a technology for encapsulating one type of packet in another type of packet so that the packet can be transmitted on a heterogeneous network, and the channel through which the encapsulated packet is transmitted is called a tunnel. A tunnel is an integral part of building a VPN, and is used to transparently transmit VPN data from one VPN node to another. Currently common tunnel types, such as label switched path (label switched path) and constraint-based routed label switched path (CR-LSP), etc., all support the tunnel load balancing function.

The load balancing function includes two modes: equal cost multiple path (ECMP) and unequal-cost multiple path (UCMP). For ECMP tunnel load balancing, when multiple tunnels participating in load balancing pass through the same path, it is easy to cause path congestion.

Contents of the invention

The present application discloses a path planning method and related equipment, which can prevent multiple load-balanced tunnels from passing through the same path, thereby alleviating network path congestion.

In a first aspect, the present application provides a path planning method, which includes:

A tunnel equivalent multipath ECMP group for traffic load balancing is configured on the first network device, wherein members of the tunnel ECMP group are composed of multiple tunnels, and the multiple tunnels include a first tunnel, and the first tunnel is based on the first tunnel. One path forwards traffic to the destination address; when the first path fails, the second path is calculated according to the path information of each path passed by each of the multiple tunnels except the first tunnel, and the second path is calculated. The second path is disjoint from each of the other paths; rerouting the first tunnel to the second path.

Optionally, the above-mentioned second path is disjoint with each of the above-mentioned other paths, and includes at least one of the following:

links between the second path and each of the other paths are disjoint;

node disjoint between the second path and each of the other paths;

the second path and each of the other paths are both link and node disjoint;

The second path and each of the other paths are best effort disjoint.

This application solves the problem of network congestion after the failure by planning a path that is disjoint with the existing path of the ECMP member of the tunnel used for load balancing after the path in the tunnel fails. In addition, the existing solution based on constraint planning path still needs to follow the constraint path after failure, and cannot reroute to other feasible paths, resulting in service interruption and reducing network reliability. This application can quickly reroute after path failure To another equal-cost path to achieve load sharing of traffic, reducing network congestion.

In a possible implementation manner, the above path information is only valid for members in the tunnel ECMP group.

In this application, the limited path information is known only during the path planning of the members in the load-balanced tunnel ECMP group, which can avoid affecting the path planning in other cases.

In a possible implementation manner, the above path information includes at least one of the following:

the link cost of each link in each of the other paths above;

the link priority of each link in each of the other paths;

A link identifier of each link in each of the other paths, where the link identifier of each link is used to identify that each link has been occupied by the tunnel ECMP group;

The device identifier of each network device in each of the other paths, where the device identifier of each network device is used to identify that each network device has been occupied by the tunnel ECMP group;

An interface identifier of each network device communication interface in each other path, where the interface identifier of each network device communication interface is used to identify that each network device communication interface has been occupied by the tunnel ECMP group.

In a possible implementation manner, the above path information includes the link cost of each link, and the above calculation of the second path includes: according to the link cost of each link, determining the multiple links.

In a possible implementation manner, after configuring the above-mentioned tunnel ECMP group, it includes: adjusting the link overhead of each link in the tunnel ECMP group, and the adjusted link overhead of each link is greater than the pre-adjusted link overhead. Link cost for each link.

In this application, by increasing the cost of each link in the path of the planned ECMP tunnel member, so that when planning the path of other ECMP tunnel members in the future, these links are bypassed due to excessive overhead, thereby achieving Plan different ECMP member tunnels on different paths.

In a possible implementation manner, the above-mentioned path information includes the link priority of each link, and the above-mentioned calculation of the second path includes: according to the link priority of each link, determining the through multiple links.

In a possible implementation manner, after configuring the tunnel ECMP group, it includes: adjusting the link priority of each link in the tunnel ECMP group, and the adjusted link priority of each link is lower than that before adjustment The link priority of each link.

In this application, by lowering the priority of each link in the path of the planned ECMP tunnel member, so that these links are bypassed when the path of other ECMP tunnel members is planned in the future because the priority is too low, thereby Implemented the planning of different ECMP member tunnels on different paths.

In a possible implementation manner, the above-mentioned path information includes a link identifier of each link, and the above-mentioned calculation of the second path includes: according to the link identifier of each link, determining the multiple links.

In a possible implementation manner, the above method further includes: after configuring the tunnel ECMP group, setting the link identifier for each link in the tunnel ECMP group.

In this application, by setting a specific link identifier for each link in the path of the planned ECMP tunnel member, so that the subsequent planning of the paths of other ECMP tunnel members bypasses these links with specific link identifiers , so that different ECMP member tunnels can be planned on different paths.

In a possible implementation manner, the path information includes a device identifier of each network device in each other path, and the calculation of the second path includes: according to the device identifier of each network device in each other path Identify, determine the multiple network devices that the second path passes through.

In a possible implementation manner, the above method further includes: after configuring the tunnel ECMP group, setting the device identifier for each network device of each path in the tunnel ECMP group.

In this application, by setting a specific device identifier for each network device in the path of the planned ECMP tunnel member, so that these network devices with specific device identifiers are bypassed when planning the paths of other ECMP tunnel members in the future, so that Implemented the planning of different ECMP member tunnels on different paths.

In a possible implementation manner, the above-mentioned path information includes an interface identifier of each network device communication interface in each other path, and the above-mentioned calculation of the second path includes: the network device communication interface is a network device in the path In the case of an incoming interface, according to the first interface identifier of each network equipment incoming interface in each of the other paths, determine a plurality of network equipment incoming interfaces that the second path passes through; In the case of the outbound interface of the network equipment, determine the multiple outbound interfaces of the network equipment that the second path passes through according to the second interface identifier of each outbound interface of the network equipment in each other path.

In a possible implementation manner, the above method further includes: when the communication interface of the network device is the inbound interface of the network device in the path, after configuring the tunnel ECMP group, for each path in the tunnel ECMP group The first interface identifier is set for each network device incoming interface; in the case that the network device communication interface is the network device outgoing interface in the path, after the tunnel ECMP group is configured, each path in the tunnel ECMP group passes through The second interface identifier is set for each outgoing interface of the network device.

In this application, by setting a specific interface identifier for each network device incoming interface (or each network device outgoing interface) in the path of the planned ECMP tunnel member, so that the subsequent planning of the path of other ECMP tunnel members bypasses the These network device incoming interfaces (or network device outgoing interfaces) with specific interface identifiers are set, so that different ECMP member tunnels can be planned on different paths.

In a second aspect, the present application provides a path planning method, which includes:

calculating a first path traversed by a first tunnel between the first network device and the second network device;

Set path information for the target object in the first path, where the target object is a link, or the target object is a network device, or the target object is a network device communication interface;

Calculating a second path passed by the second tunnel between the first network device and the second network device based on the path information, the first path and the second path are disjoint, in other words, the target object in the second path There is at least one target object in which the path information is not set, and both the first tunnel and the second tunnel are members of a tunnel equivalent cost multipath ECMP group.

This application marks the target objects in the planned path so that the path of other tunnel ECMP group members will not be planned to the same path. Compared with the existing scheme, the load balance is much more This solution not only solves the congestion problem caused by the equal-cost path planning to the same path, but also does not limit the rerouting capability of the network, and improves the reliability of the network.

In a possible implementation manner, the above-mentioned first path is disjoint to the above-mentioned second path, and includes at least one of the following:

Links between the first path and the second path are disjoint;

Node disjoint between the first path and the second path;

Neither the link nor the node intersects between the first path and the second path;

The first path and the second path are best-effort disjoint.

In a possible implementation manner, the above path information is only valid for members in the tunnel ECMP group.

In this application, the limited path information is known only during the path planning of the members in the load-balanced tunnel ECMP group, which can avoid affecting the path planning in other cases.

In a possible implementation manner, the above-mentioned target object is a link, and the above-mentioned setting of path information for the target object in the first path includes: adjusting the link cost of each link in the first path, and the adjusted The link cost of each link in the first path is greater than the link cost of each link in the first path before adjustment, and the path information includes the adjusted link cost of each link in the first path The link cost of the road.

In this application, by increasing the cost of each link in the path of the planned ECMP tunnel member, so that when planning the path of other ECMP tunnel members in the future, these links are bypassed due to excessive overhead, thereby achieving Plan different ECMP member tunnels on different paths.

In a possible implementation manner, the above-mentioned target object is a link, and the above-mentioned setting of path information for the target object in the first path includes: adjusting the link priority of each link in the first path, after adjustment The link priority of each link in the first path is less than the link priority of each link in the first path before adjustment, and the path information includes the adjusted Link priority for each link.

In this application, by lowering the priority of each link in the path of the planned ECMP tunnel member, so that these links are bypassed when the path of other ECMP tunnel members is planned in the future because the priority is too low, thereby Implemented the planning of different ECMP member tunnels on different paths.

In a possible implementation manner, the above-mentioned target object is a link, and the above-mentioned setting of path information for the target object in the first path includes: setting a link identifier for each link in the first path, and the first The link identifier of each link in the path is used to identify that each link in the first path has been occupied by the tunnel ECMP group, and the path information includes the link ID of each link in the first path road sign.

In this application, by setting a specific link identifier for each link in the path of the planned ECMP tunnel member, so that the subsequent planning of the paths of other ECMP tunnel members bypasses these links with specific link identifiers , so that different ECMP member tunnels can be planned on different paths.

In a possible implementation manner, the above-mentioned target object is a network device, and the above-mentioned setting of path information for the target object in the first path includes: setting a device identifier for each network device in the first path, and the first path The device identifier of each network device in the first path is used to identify that each network device in the first path has been occupied by the tunnel ECMP group, and the path information includes the device identifier of each network device in the first path.

In this application, by setting a specific device identifier for each network device in the path of the planned ECMP tunnel member, so that these network devices with specific device identifiers are bypassed when planning the paths of other ECMP tunnel members in the future, so that Implemented the planning of different ECMP member tunnels on different paths.

In a possible implementation manner, the above-mentioned target object is a network device communication interface, and the above-mentioned setting of path information for the target object in the first path includes:

In the case where the network device communication interface is an incoming interface of the network device in the path, a first interface identifier is set for each incoming interface of the network device in the first path, and the incoming interface of each network device in the first path The first interface identifier is used to identify that the incoming interface of each network device in the first path has been occupied by the tunnel ECMP group, and the path information includes the first interface identifier of the incoming interface of each network device in the first path ;

In the case where the network device communication interface is the outgoing interface of the network device in the path, a second interface identifier is set for each outgoing interface of the network device in the first path, and the outgoing interface of each network device in the first path The second interface identifier is used to identify that the outgoing interface of each network device in the first path has been occupied by the tunnel ECMP group, and the path information includes the second interface identifier of the outgoing interface of each network device in the first path .

In this application, by setting a specific interface identifier for each network device incoming interface (or each network device outgoing interface) in the path of the planned ECMP tunnel member, so that the subsequent planning of the path of other ECMP tunnel members bypasses the These network device incoming interfaces (or network device outgoing interfaces) with specific interface identifiers are set, so that different ECMP member tunnels can be planned on different paths.

In a third aspect, the present application provides a path planning device, which includes:

A configuration unit, configured to configure a tunnel equivalent multipath ECMP group for traffic load balancing on the first network device, wherein members of the tunnel ECMP group are composed of multiple tunnels, the multiple tunnels include the first tunnel, the The first tunnel forwards traffic to the destination address based on the first path;

A calculation unit, configured to calculate a second path according to the path information of each path passed by each tunnel of the plurality of tunnels except the first tunnel when a failure occurs on the first path, and the second path disjoint from each of the other paths;

a rerouting unit, configured to reroute the first tunnel to the second path.

In a possible implementation manner, the above-mentioned second path is disjoint with each other path, and includes at least one of the following:

links between the second path and each of the other paths are disjoint;

node disjoint between the second path and each of the other paths;

the second path and each of the other paths are both link and node disjoint;

The second path and each of the other paths are best effort disjoint.

In a possible implementation manner, the above path information is only valid for members in the tunnel ECMP group.

In a possible implementation manner, the above path information includes at least one of the following:

the link cost of each link in each of the other paths above;

the link priority of each link in each of the other paths;

A link identifier of each link in each of the other paths, where the link identifier of each link is used to identify that each link has been occupied by the tunnel ECMP group;

The device identifier of each network device in each of the other paths, where the device identifier of each network device is used to identify that each network device has been occupied by the tunnel ECMP group;

An interface identifier of each network device communication interface in each other path, where the interface identifier of each network device communication interface is used to identify that each network device communication interface has been occupied by the tunnel ECMP group.

In a possible implementation manner, the above path information includes the link cost of each link, and the above calculating unit is specifically configured to: determine the multiple paths passed by the second path according to the link cost of each link link.

In a possible implementation manner, the above-mentioned device further includes a first adjustment unit, configured to adjust the link overhead of each link in the tunnel ECMP group after the tunnel ECMP group is configured, and the adjusted The link cost of each link is greater than the link cost of each link before adjustment.

In a possible implementation manner, the above-mentioned path information includes the link priority of each link, and the above-mentioned calculation unit is specifically configured to: according to the link priority of each link, determine the multiple links.

In a possible implementation manner, the above-mentioned device further includes a second adjustment unit, configured to adjust the link priority of each link in the tunnel ECMP group after the tunnel ECMP group is configured, and the adjusted link priority of each link in the tunnel ECMP group The link priority of each link is lower than the link priority of each link before adjustment.

In a possible implementation manner, the above-mentioned path information includes a link identifier of each link, and the above-mentioned calculation unit is specifically configured to: determine a plurality of link.

In a possible implementation manner, the above device further includes a first setting unit, configured to set the link identifier for each link in the tunnel ECMP group after the tunnel ECMP group is configured.

In a possible implementation manner, the path information includes a device identifier of each network device in each other path, and the calculation unit is specifically configured to: according to the device identifier of each network device in each other path, Multiple network devices that the second path passes through are determined.

In a possible implementation manner, the above device further includes a second setting unit, configured to set the device identifier for each network device of each path in the tunnel ECMP group after the tunnel ECMP group is configured.

In a possible implementation manner, the above-mentioned path information includes an interface identifier of each network device communication interface in each other path, and the above-mentioned calculation unit is specifically used for:

In the case that the network device communication interface is an incoming interface of a network device in a path, according to the first interface identifier of each incoming interface of a network device in each other path, determine a plurality of network devices that the second path passes through Ingress interface;

In the case that the network device communication interface is an outgoing interface of the network device in the path, according to the second interface identifier of the outgoing interface of each network device in each of the other paths, determine the plurality of network devices that the second path passes through out interface.

In a possible implementation manner, the above device further includes a third setting unit, configured to:

In the case where the network device communication interface is the network device ingress interface in the path, after configuring the tunnel ECMP group, set the first interface identifier for each network device ingress interface passed by each path in the tunnel ECMP group;

In the case that the network device communication interface is the outgoing interface of the network device in the path, after configuring the tunnel ECMP group, set the second interface identifier for each outgoing interface of the network device passed by each path in the tunnel ECMP group.

In a fourth aspect, the present application provides a path planning device, which includes:

a calculation unit, configured to calculate a first path passed by the first tunnel between the first network device and the second network device;

A setting unit, configured to set path information for a target object in the first path, where the target object is a link, or the target object is a network device, or the target object is a communication interface of a network device;

The calculation unit is further configured to calculate a second path passed by the second tunnel between the first network device and the second network device based on the path information, the first path and the second path are disjoint, in other words, the second At least one of the target objects in the path does not have the path information set. Wherein, the first tunnel and the second tunnel are members of a tunnel equivalent multipath ECMP group.

In a possible implementation manner, the above-mentioned first path is disjoint to the above-mentioned second path, and includes at least one of the following:

Links between the first path and the second path are disjoint;

Node disjoint between the first path and the second path;

Neither the link nor the node intersects between the first path and the second path;

The first path and the second path are best-effort disjoint.

In a possible implementation manner, the above path information is only valid for members in the tunnel ECMP group.

In a possible implementation manner, the above-mentioned target object is a link, and the setting unit is specifically used for:

Adjusting the link cost of each link in the first path, the adjusted link cost of each link in the first path is greater than the link cost of each link in the first path before adjustment Cost, where the path information includes the adjusted link cost of each link in the first path.

In a possible implementation manner, the above-mentioned target object is a link, and the above-mentioned setting unit is specifically used for:

Adjusting the link priority of each link in the first path, the adjusted link priority of each link in the first path is less than the adjusted link priority of each link in the first path link priority, the path information includes the adjusted link priority of each link in the first path.

In a possible implementation manner, the above-mentioned target object is a link, and the above-mentioned setting unit is specifically used for:

Setting a link identifier for each link in the first path, where the link identifier of each link in the first path is used to identify that each link in the first path has been used by the tunnel ECMP group Occupied, the path information includes the link identifier of each link in the first path.

In a possible implementation manner, the above-mentioned target object is a network device, and the above-mentioned setting unit is specifically used for:

Setting a device identifier for each network device in the first path, where the device identifier of each network device in the first path is used to identify that each network device in the first path has been occupied by the tunnel ECMP group, The path information includes the device identification of each network device in the first path.

In a possible implementation manner, the above-mentioned target object is a communication interface of a network device, and the above-mentioned setting unit is specifically used for:

In the case where the network device communication interface is an incoming interface of the network device in the path, a first interface identifier is set for each incoming interface of the network device in the first path, and the incoming interface of each network device in the first path The first interface identifier is used to identify that the incoming interface of each network device in the first path has been occupied by the tunnel ECMP group, and the path information includes the first interface identifier of the incoming interface of each network device in the first path ;

In the case where the network device communication interface is the outgoing interface of the network device in the path, a second interface identifier is set for each outgoing interface of the network device in the first path, and the outgoing interface of each network device in the first path The second interface identifier is used to identify that the outgoing interface of each network device in the first path has been occupied by the tunnel ECMP group, and the path information includes the second interface identifier of the outgoing interface of each network device in the first path .

In a fifth aspect, the present application provides a path planning device, which may include a processor and a memory, configured to implement the path planning method described in the foregoing first aspect and its possible implementation manners. The memory is coupled to the processor, and when the processor executes the computer program stored in the memory, the device may implement the method described in the first aspect or any possible implementation manner of the first aspect.

The device may further include a communication interface, which is used for the device to communicate with other devices. Exemplarily, the communication interface may be a transceiver, a circuit, a bus, a module, or other types of communication interfaces. The communication interface includes a receiving interface and a sending interface, the receiving interface is used for receiving messages, and the sending interface is used for sending messages.

In one possible implementation, the device may include:

memory for storing computer programs;

A processor, configured to configure a tunnel equivalent multipath ECMP group for traffic load balancing on the first network device, wherein members of the tunnel ECMP group are composed of multiple tunnels, the multiple tunnels include the first tunnel, the The first tunnel forwards traffic to the destination address based on the first path; when the first path fails, according to the path information of each path passed by each of the tunnels except the first tunnel, calculate a second path, the second path being disjoint from each of the other paths; rerouting the first tunnel to the second path.

It should be noted that the computer program in the memory in this application can be stored in advance or can be stored after being downloaded from the Internet when using the device. This application does not specifically limit the source of the computer program in the memory. The coupling in the embodiments of the present application is an indirect coupling or connection between devices, units or modules, which may be in electrical, mechanical or other forms, and is used for information exchange between devices, units or modules.

In a sixth aspect, the present application provides a path planning device, which may include a processor and a memory, configured to implement the path planning method described in the above second aspect and its possible implementation manners. The memory is coupled to the processor, and when the processor executes the computer program stored in the memory, the device may implement the method described in the second aspect or any possible implementation manner of the second aspect.

The device may further include a communication interface, which is used for the device to communicate with other devices. Exemplarily, the communication interface may be a transceiver, a circuit, a bus, a module, or other types of communication interfaces. The communication interface includes a receiving interface and a sending interface, the receiving interface is used for receiving messages, and the sending interface is used for sending messages.

In one possible implementation, the device may include:

memory for storing computer programs;

A processor, configured to calculate a first path passed by the first tunnel between the first network device and the second network device; set path information for a target object in the first path, where the target object is a link, or the target The object is a network device, or the target object is a network device communication interface; based on the path information, a second path through which a second tunnel between the first network device and the second network device passes is calculated, and the target object in the second path At least one target object is not configured with the path information, and the first tunnel and the second tunnel are members of a tunnel equivalent cost multipath ECMP group.

It should be noted that the computer program in the memory in this application can be pre-stored or stored after being downloaded from the Internet when using the device, and the source of the computer program in the memory is not specifically limited in this application. The coupling in the embodiments of the present application is an indirect coupling or connection between devices, units or modules, which may be in electrical, mechanical or other forms, and is used for information exchange between devices, units or modules.

In a seventh aspect, the present application provides a computer-readable storage medium, the computer-readable storage medium stores a computer program, and the computer program is executed by a processor to implement any one of the above-mentioned first aspect and its possible implementation manners. described method.

In an eighth aspect, the present application provides a computer-readable storage medium, where a computer program is stored in the computer-readable storage medium, and the computer program is executed by a processor to implement any one of the above-mentioned second aspect and its possible implementation manners. described method.

In a ninth aspect, the present application provides a computer program product, which, when running on a computer, causes the computer to execute the method described in any one of the above first aspects.

In a tenth aspect, the present application provides a computer program product, which, when running on a computer, causes the computer to execute the method described in any one of the above first aspects.

Understandably, the devices described in the third to sixth aspects, the computer storage media in the seventh and eighth aspects, and the computer program products in the ninth and tenth aspects are all used to execute The method provided by any one of the first aspect and the second aspect. Therefore, the beneficial effects that it can achieve can refer to the beneficial effects in the corresponding method, and will not be repeated here.

Description of drawings

The drawings that need to be used in the embodiments of the present application will be introduced below.

FIG. 1 is a schematic diagram of tunnel load balancing between two network devices;

Figure 2 is a schematic diagram of the paths of ECMP member tunnels;

FIG. 3 is a schematic diagram of a network system architecture applicable to the present application;

FIG. 4 is a schematic flow chart of the path planning method provided by the present application;

Figure 5A and Figure 5B are schematic diagrams showing the path of the tunnel;

Figure 6A and Figure 6B are schematic diagrams showing the path of the tunnel;

Figure 7A and Figure 7B are schematic diagrams showing the path of the tunnel;

FIG. 8 is a schematic diagram of a tunnel rerouting path;

Figure 9 and Figure 10 are schematic diagrams of the logical structure of the device provided by the present application;

FIG. 11 is a schematic diagram of the hardware structure of the device provided by the present application.

detailed description

Embodiments of the present application are described below in conjunction with the accompanying drawings.

Firstly, the technical problems to be solved in this application and the applicable scenarios are introduced.

Referring to FIG. 1, FIG. 1 is a schematic diagram of tunnel load balancing between two network devices. As can be seen in Figure 1, in order to increase the transmission bandwidth of the traffic, multiple tunnels can be created between the network device 1 and the network device 2, and the multiple tunnels can realize the traffic load between the network device 1 and the network device 2 share.

In this application, the network device may be a customer edge device (customer edge, CE), a provider edge device (provider edge, PE), a provider backbone router (provider, P), and the like. Network devices may also be referred to as network nodes or nodes.

Specifically, the tunnel is an indispensable part of constructing a virtual private network (virtual private network, VPN), and is used to transparently transmit VPN data from one VPN node to another VPN node. To create a tunnel, you only need to specify the network devices at the start and end points of the tunnel, and the specific path that the tunnel passes is calculated based on the shortest path algorithm.

In a specific implementation, the above multiple tunnels belong to members of an equal cost multiple path (equal cost multiple path, ECMP) group. The ECMP means that there are multiple equal-cost paths from the same starting node to the same destination node, and the traffic is evenly distributed on these equal-cost paths, regardless of the difference in path bandwidth; A path whose path cost (cost value) is equal to the destination node. For the above-mentioned multiple tunnels, the communication path between the above-mentioned network device 1 and network device 2 can be abstracted as a link, and each tunnel of the multiple tunnels sends the traffic of the network device 1 through this link to the network device 2, therefore, the paths of the plurality of tunnels are equal-cost paths, and thus the plurality of tunnels belong to ECMP group members.

However, since the specific path of the tunnel is calculated according to the shortest path algorithm, and the member tunnels of the ECMP group are equal-cost paths, when planning the paths of the member tunnels of the ECMP group, it is easy to plan the paths of multiple members of the ECMP group In this case, the load sharing function of traffic will be weakened, which may easily cause path congestion.

For example, refer to FIG. 2, which shows a schematic diagram of a partial network structure. In FIG. 2, there are two paths from network device B to network device G, and the first path is: network device B→network device C→network device E→network device G, the second path is: network device B→network device D→network device F→network device G. Assuming that the two paths are not equal-cost paths, then there are two load-balancing tunnels created between network device B and network device G, and when it is necessary to plan paths for the two tunnels, calculate according to the shortest path algorithm, the two The path of the tunnel will be planned on the same path (for example, the first path), as shown in FIG. 2 . In this case, all the traffic between network device B and network device G will be transmitted through the first path, and load sharing of traffic cannot be realized, which may easily cause congestion of the first path.

In existing solutions, ECMP tunnel members can be planned on different paths through path constraints or bandwidth constraints, such as a constraint-based routed label switched path (CR-LSP). However, this solution limits the dynamic rerouting capability of the tunnel and reduces the reliability of the network. For example, when a constrained path fails, due to path constraints, rerouting is still routed to the constrained path of the fault, and will not be rerouted to other non-faulty paths (limiting the rerouting capability), which will cause traffic transmission If there is an interruption, the business will also be interrupted (reducing the reliability of the network).

In order to plan the paths of tunnel ECMP members to different paths without restricting the dynamic rerouting capability of the tunnel, the present application provides a path planning method. Before introducing the method, first introduce the applicable system architecture of the method, as shown in FIG. 3 . Figure 3 exemplarily shows a schematic diagram of a network system architecture applicable to this application, the system architecture includes a plurality of network devices, the plurality of network devices constitute a traffic forwarding network, these network devices include customer edge equipment CE, operating Provider edge equipment PE and carrier backbone router P and other equipment.

It should be noted that multiple links can be configured between two network devices that can communicate in the system architecture.

In a possible implementation manner, the network system architecture shown in FIG. 3 includes a controller, and the controller can obtain a topology view of the network, so as to plan a forwarding path of traffic in the network, and the like. Exemplarily, the controller may be a software defined network (software defined network, SDN) controller or an operation and maintenance center (operation and maintenance center, OMC), etc.

In another possible implementation manner, the above network system architecture does not include a controller, then, the forwarding path of the traffic may be calculated by the network device based on the shortest path algorithm.

It should be noted that the above-mentioned system architecture shown in FIG. 3 is only an example, and the applicable system architecture of the path planning method provided in the present application is not limited to the system architecture described above.

Referring to FIG. 4 , it shows the path planning method provided by the present application. If the network system architecture applied by the method includes the above-mentioned controller, and the forwarding path of the traffic in the network is calculated by the controller, then the execution subject of the method can be The controller; if the system architecture to which the method is applied does not include a controller, and the forwarding path of traffic in the network is calculated by the network device based on the shortest path algorithm, then the network device may be the subject of execution of the method. Regardless of whether the subject of execution of the method is a controller or a network device in a specific implementation, the subject of execution of the method is collectively referred to as an execution device below. The method may include, but is not limited to, the following steps:

S401. Configure a tunnel equivalent multipath ECMP group for traffic load balancing on the first network device, wherein the members of the ECMP group are composed of multiple tunnels, and the multiple tunnels include a first tunnel, and the first tunnel is based on The first path forwards traffic to the destination address.

Exemplarily, the first network device may be any network device in the above-mentioned system architecture, and the terminal network device of the plurality of tunnels configured for traffic load balancing may be another network device in the system architecture, which may be is called the second network device, then the above-mentioned destination address is the address of the second network device.

Optionally, the above multiple tunnels may be configured by a controller in the network system, that is, the execution device is the controller. Or, optionally, the multiple tunnels may be configured by the above-mentioned first network device, that is, the executing device is the first network device.

S402. When the first path fails, calculate a second path according to the path information of each path passed by each of the multiple tunnels except the first tunnel, and the second path is related to the other Each path is disjoint.

In a specific embodiment, a specific traffic transmission path is correspondingly calculated for each of the multiple member tunnels of the above ECMP group. Specifically, after the execution device calculates these transmission paths, it can set path information for the target objects in these paths, and the target objects can be links in the path, network devices in the path, or networks in the path Device communication interface. The communication interface of the network device in the path can be the input interface of the network device in the path, or the output interface of the network device in the path. It should be noted that the communication interface of the network device in the path only includes the link The interface connected to the path does not include the interfaces of other links not connected to the path in the network equipment of the path.

Optionally, the path information is only valid for members of the ECMP group. That is, when planning specific traffic transmission paths for the above multiple tunnels, these path information can be used as marks to plan different tunnels on different transmission paths as much as possible.

The above path information may include at least one of the following: the cost value of each link in the path, the link priority of each link in the path, the link identifier of each link in the path, and each network device in the path or the interface identifier of each network device communication interface in the path, etc.

In a possible implementation manner, the foregoing path information includes a cost value of each link in the path. Specifically, after the execution device calculates and obtains the traffic transmission path of one of the above multiple tunnels (for convenience of description, hereinafter referred to as the first target path), it can adjust the cost value of each link in the first target path , so that the cost value of each link after adjustment is greater than the cost value before adjustment. Exemplarily, the cost value of each link can be adjusted to a cost value that is several times, ten times, tens of times, hundreds of times, thousands of times or tens of thousands of times larger than before adjustment. The size is not limited.

Optionally, the adjusted link cost value in the first target path is only valid when planning the paths of tunnels other than the one tunnel among the above-mentioned multiple tunnels. In addition, the link cost value in the first target path The link cost value is still processed according to the link cost value before adjustment. That is, when calculating the traffic transmission path of other tunnels that are load-balanced with the certain tunnel, because the link cost value of the first destination path is relatively large, and based on the principle of the shortest path algorithm, the execution device will bypass the cost value larger link, so that the other tunnel is planned on a path disjoint with the first target path. For ease of understanding, refer to FIG. 5A and FIG. 5B by way of example.

In FIG. 5A , assuming that the cost value of each link is 10, a tunnel ECMP group including two tunnels is created between network device B and network device I for load sharing traffic between the two devices. According to the shortest path principle, the execution device calculates the specific transmission path of the first tunnel to obtain the path: network device B→network device G→network device I. After calculating the path, the execution device can adjust the cost value of the link in the path, for example, increase the cost value of each link in the path by 10000, and the adjusted link cost value can be seen in Figure 5B. After adjusting the link cost value of this path, when the execution device calculates the transmission path of the second tunnel, based on the principle of the shortest path, the link cost value in the path network device B→network device G→network device I is very large , the execution device will avoid the path, so the calculated transmission path of the second tunnel is: network device B→network device C→network device E→network device I. In this way, the transmission paths of two different member tunnels in the load-sharing ECMP group are planned on different paths.

Since the above embodiment avoids path intersecting by adjusting the cost value of the link, the disjointness of two paths realized in this embodiment actually means that the links in the two paths are disjoint. In addition, optionally, since multiple links may be configured between two network devices, in this case, although the links in the two paths do not intersect, the network devices in the two paths may intersect.

In another possible implementation manner, the foregoing path information includes a link priority of each link in the path. Specifically, after the execution device calculates and obtains the above-mentioned first target path, it may adjust the link priority of each link in the first target path, so that the link priority of each link after adjustment is lower than that before adjustment. link priority. Exemplarily, the link priority of each link can be adjusted to one level, two levels or three levels lower than before the adjustment, and this application does not make any specific adjustments to the priority levels limit.

However, optionally, the adjusted link priority is not the lowest level of link priority. If the link priority of the first target path is adjusted to the lowest level of link priority, it may make the first target path The links in the ECMP group are no longer available when calculating the paths of other tunnel members in the ECMP group. At this time, if there are links in the paths of other tunnel members in the ECMP group that overlap with the links in the first target path In this case, the paths of other tunnel members in the ECMP group cannot be successfully calculated.

Exemplarily, the above-mentioned link priority may be determined according to the bandwidth of the link. The greater the bandwidth of the link, the higher the priority of the link. Conversely, the smaller the bandwidth of the link, the higher the priority of the link. the lower the grade. For ease of understanding, refer to Table 1 as an example.

Table 1

link bandwidth link priority 200G 1 100G 2 50G 3 25G 4 10G 5 1G 6

Table 1 exemplarily shows 6 levels of link priority, level 1 is the highest link priority, level 6 is the lowest link priority, and levels from 1 to 6 represent link priorities From highest to lowest. It can be seen that the greater the link bandwidth, the higher the link priority, and the smaller the link bandwidth, the lower the link priority.

Optionally, the adjusted link priority in the first target path is only valid when planning the paths of tunnels other than the one tunnel in the above-mentioned multiple tunnels. In addition, the first target The link priority in the path is still processed according to the link priority before adjustment. That is, when calculating the traffic transmission path of other tunnels that are load-balanced with one of the above tunnels, since the link priority of the first target path is low, and based on the principle of high priority selection, the execution device will bypass this link. A link with a lower link priority, so that the other tunnel is planned on a path disjoint with the first target path. For ease of understanding, refer to FIG. 6A and FIG. 6B for example.

In FIG. 6A , assuming that the priority of each link is 2, a tunnel ECMP group including two tunnels is created between network device B and network device I for load sharing the traffic between the two devices. Assume that the execution device calculates the specific transmission path of the first tunnel to obtain the path: network device B→network device G→network device I. After the path is calculated, the execution device can adjust the priority of the links in the path, for example, increase the priority of each link in the path by 1, and the adjusted link priority can be seen in FIG. 6B . After adjusting the link priority of this path, when the execution device calculates the transmission path of the second tunnel, based on the principle of high priority selection, since the link in the path network device B→network device G→network device I The priority is low, and the execution device will avoid this path, so the calculated transmission path of the second tunnel is another path, for example, the other path is: network device B→network device C→network device E→ network equipment I. In this way, the transmission paths of two different member tunnels in the load-sharing ECMP group are planned on different paths.

Similarly, since the foregoing embodiment avoids path intersection by adjusting the priority of links, the disjointness of two paths realized in this embodiment actually means that the links in the two paths are disjoint. In addition, optionally, since multiple links may be configured between two network devices, in this case, although the links in the two paths do not intersect, the network devices in the two paths may intersect.

In another possible implementation manner, the path information includes a link identifier of each link in the path. Specifically, after the execution device calculates and obtains the first target path, a link identifier may be set for each link in the first target path. The function of the link identifier is to indicate that the link with the link identifier set is occupied by the above-mentioned ECMP group. The link identifier can be any user-defined identifier, such as a certain character, a certain number or a certain letter, etc. , this application does not limit the specific link identifier.

Optionally, the link identifier set by the link in the first target path is only valid when planning the traffic transmission path of other tunnels that are load-balanced by the above-mentioned certain tunnel. That is, when planning the traffic transmission path of the other tunnel, the execution device will bypass the link for which the link identifier is set, so as to plan the other tunnel on a path disjoint with the first target path. For ease of understanding, refer to FIG. 7A and FIG. 7B by way of example.

In FIG. 7A , it is assumed that a tunnel ECMP group including two tunnels is created between network device B and network device I for load sharing traffic between the two devices. Assume that the execution device calculates the specific transmission path of the first tunnel to obtain the path: network device B→network device G→network device I. After the path is calculated, the executing device may set an identifier for the link in the path, the identifier may be Z, for example, and refer to FIG. 7B for the link after the identifier is set. After setting the link ID, when the execution device calculates the transmission path of the second tunnel, based on the already set link ID, it knows that the link with the link ID set has been occupied by the above-mentioned ECMP group, and the execution device will avoid The identified link is set, so that the calculated transmission path of the second tunnel is another path, for example, the other path is: network device B→network device C→network device E→network device I. In this way, the transmission paths of two different member tunnels in the load-sharing ECMP group are planned on different paths.

Similarly, since the above embodiment avoids path intersection by setting link identifiers, the disjointness of two paths realized in this embodiment actually means that the links in the two paths are disjoint. In addition, optionally, since multiple links may be configured between two network devices, in this case, although the links in the two paths do not intersect, the network devices in the two paths may intersect.

In another possible implementation manner, the foregoing path information includes a device identifier of each network device in the path. Specifically, after the execution device calculates and obtains the first target path, an identifier may be set for each network device in the first target path. The role of this logo is to indicate that the network device with this logo is occupied by the above-mentioned ECMP group. This logo can be any self-defined logo, such as a certain character, a certain number or a certain letter, etc. The identification of the network device is not limited.

Optionally, the identifier set by the network device in the first target path is only valid when planning traffic transmission paths of other tunnels that are load-balanced by the above-mentioned certain tunnel. That is, when planning the traffic transmission path of the other tunnel, the execution device will bypass the network device for which the identifier is set, so as to plan the other tunnel on a path disjoint with the first target path.

Since the above-mentioned embodiment avoids path intersection by setting identifiers for network devices, the disjointness of two paths realized in this embodiment actually means that the network devices in the two paths are disjoint or the nodes in the paths are disjoint . Two paths with disjoint nodes must have disjoint links.

In another possible implementation manner, the path information includes an interface identifier of each network device communication interface in the path. In the case where the network device communication interface is an inbound interface of a network device in the path, after the execution device calculates and obtains the above-mentioned first target path, an interface identifier can be set for each inbound interface of the network device in the first target path, for convenience description, the interface identifier may be referred to as the first interface identifier. The role of the first interface identifier is to indicate that the inbound interface of the network device for which the identifier is set is occupied by the above-mentioned ECMP group. The first interface identifier can be any custom identifier, such as a certain character, a certain number or a certain letter Etc., this application does not limit the identification of specific network device ingress interfaces. The ingress interface of the network device is the ingress interface of the traffic transmitted through the first target path on the network device.

Optionally, the first interface identifier set by the inbound interface of the network device in the first target path is only valid when planning the traffic transmission path of other tunnels that are load-balanced by the above-mentioned certain tunnel. That is, when planning the traffic transmission path of the other tunnel, the execution device will bypass the inbound interface of the network device for which the first interface identifier is set, so as to plan the other tunnel on a path disjoint with the first target path.

In the case that the network device communication interface is an outgoing interface of the network device in the path, after the executing device calculates and obtains the first target path, an interface identifier may be set for each outgoing interface of the network device in the first target path. The interface identifier of the outgoing interface of the network device may be the same as or different from the first interface identifier of the incoming interface of the network device. For ease of distinction, in this application, the interface identifier of the outgoing interface of the network device may be referred to as the second interface identifier. The function of the second interface identifier is to indicate that the outbound interface of the network device with the identifier set is occupied by the above-mentioned ECMP group. The identifier can be any custom identifier, such as a certain character, a certain number or a certain letter, etc. This application does not limit the identification of the specific outgoing interface of the network device. The outbound interface of the network device is an outbound interface on the network device for traffic transmitted through the first target path.

Optionally, the second interface identifier set by the outbound interface of the network device in the first target path is only valid when planning the traffic transmission path of other tunnels that are load balanced by the above-mentioned certain tunnel. That is, when planning the traffic transmission path of the other tunnel, the execution device will bypass the outgoing interface of the network device with the second interface identifier set, so as to plan the other tunnel on a path disjoint with the first target path.

Since the above-mentioned embodiment avoids path intersection by setting interface identifiers on the communication interfaces of network devices, one communication interface is connected to one link. Therefore, the disjointness of two paths realized in this embodiment is actually the The links are disjoint. In addition, optionally, since multiple communication interfaces may be configured between two network devices, that is, there are multiple links correspondingly connected, in this case, although the links in the two paths do not intersect, the two paths Network devices in may intersect.

In a possible implementation manner, the path disjoint among the tunnel members of the above-mentioned ECMP group may be best-effort disjoint, that is, when the paths among the tunnel members of multiple ECMP groups must intersect, for example, The multiple paths can only pass through a certain link or network device to reach the destination address, and if there is no other link or network device to replace, the multiple paths can pass through the certain link or network device together, but In addition, other links or network devices in the plurality of paths are no longer intersected.

Based on the above description, the above path information is set in the specific traffic transmission paths corresponding to the multiple tunnels created between the above first network device and the second network device. Based on the description of step S401 above, the multiple tunnels include a first tunnel, and the first tunnel forwards the traffic of the first network device to the second network device based on the first path. When the first path fails, the execution device may perform rerouting calculation to recalculate a normal communication path for the first tunnel.

Specifically, the execution device may avoid each path based on the path information in each path corresponding to the tunnels except the first tunnel among the above multiple tunnels, and recalculate the traffic transmission path of the first tunnel to obtain the second tunnel. two paths, so that the second path is disjoint to each path corresponding to other tunnels in the plurality of tunnels except the first tunnel. Specifically, at least one of the target objects in the second path is not configured with the above path information.

In a possible implementation manner, the path information in each path includes the link cost of each link in each path; then, the executing device may avoid For each link, multiple links passed by the second path are obtained through calculation. For the specific implementation process, reference may be made to the foregoing description, for example, reference may be made to the description corresponding to FIG. 5A and FIG. 5B , which will not be repeated here.

In another possible implementation manner, the path information in each path includes the link priority of each link in each path; then, the execution device may base on the link priority of each link , avoiding each link, and calculating multiple links passed by the above-mentioned second path. For the specific implementation process, reference may be made to the foregoing description, for example, reference may be made to the description corresponding to FIG. 6A and FIG. 6B , which will not be repeated here.

In another possible implementation manner, the path information in each path includes a link identifier of each link in each path; then, the executing device may, based on the link identifier of each link, avoid Each link is opened, and multiple links passed by the above-mentioned second path are obtained through calculation. For the specific implementation process, reference may be made to the foregoing description, for example, reference may be made to the description corresponding to FIG. 7A and FIG. 7B , which will not be repeated here.

In another possible implementation manner, the path information in each path includes an identifier of each network device in each path; then, the executing device may, based on the identifier of each network device in each path, By avoiding each network device in each path, a plurality of network devices passed by the above-mentioned second path are obtained through calculation. For the specific implementation process, reference may be made to the foregoing description, which will not be repeated here.

In another possible implementation manner, the path information in each path includes the first interface identifier of each network device ingress interface in each path; then, the executing device may The first interface identifier of the incoming interface of the network device avoids each incoming interface of the network device in each path, and calculates a plurality of incoming interfaces of the network equipment that the second path passes through. For the specific implementation process, reference may be made to the foregoing description, which will not be repeated here.

In another possible implementation manner, the path information in each path includes the second interface identifier of the outgoing interface of each network device in each path; then, the executing device may The second interface identifier of the outgoing interface of the network device avoids the outgoing interface of each network device in each path, and calculates the multiple outgoing interfaces of the network device that the second path passes through. For the specific implementation process, reference may be made to the foregoing description, which will not be repeated here.

Optionally, the second path is disjoint to each path, which may be that the second path is disjoint to links between each path, or the second path is disjoint to nodes between each path , or, the second path is disjoint with links and nodes between each path, or, the second path is best-effort disjoint with each path. For specific disjoint descriptions, reference may be made to the previous descriptions, which will not be repeated here.

S403. Reroute the first tunnel to the second path.

In a specific embodiment, after the execution device calculates and obtains the above-mentioned second path, it reroutes the above-mentioned first tunnel to the second path, that is, continues to forward traffic through the second path, and quickly restores the smooth transmission of network traffic, and because the The second path is not intersected with the paths of other tunnels, so that the load of the network can be better shared, the network congestion can be alleviated, the speed of network traffic forwarding can be increased, and the performance of the network can be improved.

In a possible implementation manner, after the execution device calculates and obtains the above-mentioned second path, it may also set path information for the second path. For specific path information setting, refer to the foregoing description, and details are not repeated here. Such a design can make subsequent planning of a new tunnel path between the first network device and the second network device, based on the information of the second path, plan the new tunnel path to a location disjoint with the second path. on the path. For ease of understanding, refer to FIG. 8 as an example.

In the network structure shown in Figure 8, it is assumed that multiple service flows converge to node 3 first, and an ECMP group including two member tunnels for load balancing is created between node 3 and node 1. The paths of the tunnel are two links between node 3 and node 1 respectively. However, when the two links between node 3 and node 1 fail, the rerouting of the two ECMP member tunnels from node 3 to node 1 will be triggered. In the existing scheme, according to the shortest path algorithm, the After the rerouting calculation, the two tunnels are both rerouted to the same path, which is, for example, path 1: node 3 → node 5 → node 7 → node 8 → node 4 → (link c) node 2 → (link Path b) node 1, path 1 shown in FIG. 8 . In this case, the traffic of the two tunnels is forwarded through this path, which loses the load balancing function and easily causes congestion on this path. With the route planning method provided in this application, the execution device may first plan a tunnel path, assuming that the path obtained through planning is the path 1 above. Then, the execution device sets the path information for the path 1. For the specific setting, refer to the foregoing description, which will not be repeated here. Then, another tunnel path is planned, and the execution device may bypass the path 1 as much as possible based on the set path information of the path 1, and plan to obtain a path 2 as shown in FIG. 8 . The path 2 is: node 3 → node 9 → node 10 → node 6 → node 4 → (link d) node 2 → (link a) node 1 .

It should be noted that although the paths 1 and 2 in FIG. 8 above both pass through nodes 4 and 2, the specific links are different, so the paths 1 and 2 are two disjoint paths. Assume that there is only one link between node 1 and node 2. At this time, both path 1 and path 2 will pass through this link, but since the other links between path 1 and path 2 are not intersecting, it can also be said that The path 1 and the path 2 are two disjoint paths with the best effort of the link.

To sum up, the present application solves the problem of network congestion after a failure by planning a path disjoint with the existing ECMP member's path after a path failure occurs in the tunnel. In addition, compared with the existing constrained programming scheme, the constrained path still needs to be taken after a failure, and cannot be rerouted to other feasible paths, resulting in service interruption and reducing network reliability. Routing to another equal-cost path realizes load sharing of traffic and reduces network congestion.

The foregoing mainly introduces the path planning method provided by the embodiment of the present application. It can be understood that, in order to realize the above corresponding functions, each device includes a corresponding hardware structure and/or software module for performing each function. Combining the units and steps of each example described in the embodiments disclosed herein, the present application can be implemented in the form of hardware or a combination of hardware and computer software. Whether a certain function is executed by hardware or computer software drives hardware depends on the specific application and design constraints of the technical solution. Skilled artisans may use different methods to implement the described functions for each specific application, but such implementation should not be regarded as exceeding the scope of the present application.

The embodiments of the present application may divide the device into functional modules according to the above method example, for example, each functional module may be divided corresponding to each function, or two or more functions may be integrated into one module. The above-mentioned integrated modules can be implemented in the form of hardware or in the form of software function modules. It should be noted that the division of modules in this embodiment of the present application is schematic, and is only a logical function division, and there may be other division methods in actual implementation.

In the case of dividing each functional module corresponding to each function, FIG. 9 shows a schematic diagram of a possible logical structure of the device. The device may be the above-mentioned execution device, or may be a chip in the execution device, or may be the Execute the processing system in the device, etc. The apparatus 900 includes a configuration unit 901 , a calculation unit 902 and a rerouting unit 903 . in:

The configuration unit 901 is configured to configure a tunnel equivalent multipath ECMP group for traffic load balancing on the first network device, wherein members of the tunnel ECMP group are composed of multiple tunnels, and the multiple tunnels include the first tunnel, The first tunnel forwards traffic to the destination address based on the first path; the configuration unit 901 may perform the configuration operation described in step S401 shown in FIG. 4 .

The calculation unit 902 is configured to calculate a second path according to the path information of each path passed by each of the multiple tunnels except the first tunnel when the first path fails, and the second path The path is disjoint to each other path; the calculation unit 902 may perform the calculation operation described in step S402 shown in FIG. 4 .

The rerouting unit 903 is configured to reroute the first tunnel to the second path; the rerouting unit 903 may perform the rerouting operation described in step S403 shown in FIG. 4 .

In a possible implementation manner, the above-mentioned second path is disjoint with each other path, and includes at least one of the following:

links between the second path and each of the other paths are disjoint;

node disjoint between the second path and each of the other paths;

the second path and each of the other paths are both link and node disjoint;

The second path and each of the other paths are best effort disjoint.

In a possible implementation manner, the above path information is only valid for members in the tunnel ECMP group.

In a possible implementation manner, the above path information includes at least one of the following:

the link cost of each link in each of the other paths above;

the link priority of each link in each of the other paths;

A link identifier of each link in each of the other paths, where the link identifier of each link is used to identify that each link has been occupied by the tunnel ECMP group;

The device identifier of each network device in each of the other paths, where the device identifier of each network device is used to identify that each network device has been occupied by the tunnel ECMP group;

An interface identifier of each network device communication interface in each other path, where the interface identifier of each network device communication interface is used to identify that each network device communication interface has been occupied by the tunnel ECMP group.

In a possible implementation manner, the above-mentioned path information includes the link cost of each link, and the above-mentioned calculation unit 902 is specifically configured to: determine how many times the second path passes through according to the link cost of each link. links.

In a possible implementation manner, the above-mentioned device further includes a first adjustment unit, configured to adjust the link overhead of each link in the tunnel ECMP group after the tunnel ECMP group is configured, and the adjusted The link cost of each link is greater than the link cost of each link before adjustment.

In a possible implementation manner, the above-mentioned path information includes the link priority of each link, and the above-mentioned calculation unit 902 is specifically configured to: according to the link priority of each link, determine multiple links.

In a possible implementation manner, the above-mentioned device further includes a second adjustment unit, configured to adjust the link priority of each link in the tunnel ECMP group after the tunnel ECMP group is configured, and the adjusted link priority of each link in the tunnel ECMP group The link priority of each link is lower than the link priority of each link before adjustment.

In a possible implementation manner, the above-mentioned path information includes a link identifier of each link, and the above-mentioned calculation unit 902 is specifically configured to: determine how many times the second path passes through according to the link identifier of each link. links.

In a possible implementation manner, the above device further includes a first setting unit, configured to set the link identifier for each link in the tunnel ECMP group after the tunnel ECMP group is configured.

In a possible implementation manner, the path information includes the device identifier of each network device in each other path, and the calculation unit 902 is specifically configured to: according to the device identifier of each network device in each other path , to determine a plurality of network devices that the second path passes through.

In a possible implementation manner, the above device further includes a second setting unit, configured to set the device identifier for each network device of each path in the tunnel ECMP group after the tunnel ECMP group is configured.

In a possible implementation manner, the path information includes an interface identifier of each network device communication interface in each other path, and the calculation unit 902 is specifically configured to:

In the case that the network device communication interface is an incoming interface of a network device in a path, according to the first interface identifier of each incoming interface of a network device in each other path, determine a plurality of network devices that the second path passes through Ingress interface;

In the case that the network device communication interface is an outgoing interface of the network device in the path, according to the second interface identifier of the outgoing interface of each network device in each of the other paths, determine the plurality of network devices that the second path passes through out interface.

In a possible implementation manner, the above device further includes a third setting unit, configured to:

In the case where the network device communication interface is the network device ingress interface in the path, after configuring the tunnel ECMP group, set the first interface identifier for each network device ingress interface passed by each path in the tunnel ECMP group;

In the case that the network device communication interface is the outgoing interface of the network device in the path, after configuring the tunnel ECMP group, set the second interface identifier for each outgoing interface of the network device passed by each path in the tunnel ECMP group.

For specific operations and beneficial effects of each unit in the apparatus 900 shown in FIG. 9 , refer to the corresponding descriptions in FIG. 4 and its possible method embodiments above, and details are not repeated here.

In the case of dividing each functional module corresponding to each function, FIG. 10 shows a schematic diagram of a possible logical structure of the device. The device may be the above-mentioned execution device, or may be a chip in the execution device, or may be the Execute the processing system in the device, etc. The device 1000 includes a computing unit 1001 and a setting unit 1002 . in:

The calculation unit 1001 is configured to calculate the first path passed by the first tunnel between the first network device and the second network device; the calculation unit 1001 can perform the calculation of ECMP group members described in the specific description of step S402 shown in FIG. 4 The operation of the path of the tunnel.

The setting unit 1002 is configured to set path information for the target object in the first path, the target object is a link, or the target object is a network device, or the target object is a network device communication interface; the setting unit 1002 can execute the As described in the specific description of step S402 shown in 4, the operation of setting path information for the target object in the path of the ECMP group member tunnel.

The calculation unit 1001 is further configured to calculate a second path passed by the second tunnel between the first network device and the second network device based on the path information, at least one of the target objects in the second path is not set With the path information, the first tunnel and the second tunnel belong to members of a tunnel equivalent cost multipath ECMP group.

In a possible implementation manner, the above path information is only valid for members in the tunnel ECMP group.

In a possible implementation manner, the above-mentioned target object is a link, and the setting unit 1002 is specifically used for:

Adjusting the link cost of each link in the first path, the adjusted link cost of each link in the first path is greater than the link cost of each link in the first path before adjustment Cost, where the path information includes the adjusted link cost of each link in the first path.

In a possible implementation manner, the above-mentioned target object is a link, and the above-mentioned setting unit 1002 is specifically configured to:

Adjusting the link priority of each link in the first path, the adjusted link priority of each link in the first path is less than the adjusted link priority of each link in the first path link priority, the path information includes the adjusted link priority of each link in the first path.

In a possible implementation manner, the above-mentioned target object is a link, and the above-mentioned setting unit 1002 is specifically configured to:

Setting a link identifier for each link in the first path, where the link identifier of each link in the first path is used to identify that each link in the first path has been used by the tunnel ECMP group Occupied, the path information includes the link identifier of each link in the first path.

In a possible implementation manner, the above-mentioned target object is a network device, and the above-mentioned setting unit 1002 is specifically configured to:

Setting a device identifier for each network device in the first path, where the device identifier of each network device in the first path is used to identify that each network device in the first path has been occupied by the tunnel ECMP group, The path information includes the device identification of each network device in the first path.

In a possible implementation manner, the above-mentioned target object is a communication interface of a network device, and the above-mentioned setting unit 1002 is specifically used for:

In the case where the network device communication interface is an incoming interface of the network device in the path, a first interface identifier is set for each incoming interface of the network device in the first path, and the incoming interface of each network device in the first path The first interface identifier is used to identify that the incoming interface of each network device in the first path has been occupied by the tunnel ECMP group, and the path information includes the first interface identifier of the incoming interface of each network device in the first path ;

In the case where the network device communication interface is the outgoing interface of the network device in the path, a second interface identifier is set for each outgoing interface of the network device in the first path, and the outgoing interface of each network device in the first path The second interface identifier is used to identify that the outgoing interface of each network device in the first path has been occupied by the tunnel ECMP group, and the path information includes the second interface identifier of the outgoing interface of each network device in the first path .

For specific operations and beneficial effects of each unit in the apparatus 1000 shown in FIG. 10 , refer to the corresponding descriptions in FIG. 4 and its possible method embodiments above, and details are not repeated here.

Figure 11 is a schematic diagram of a possible hardware structure of the device provided by this application. The device may be the execution device described in the above embodiment, or may be a chip in the execution device, or may be a chip in the execution device. processing system, etc. The device 1100 includes: a processor 1101 , a memory 1102 and a communication interface 1103 . The processor 1101 , the communication interface 1103 and the memory 1102 may be connected to each other or through a bus 1104 .

Exemplarily, the memory 1102 is used to store computer programs and data of the device 1100, and the memory 1102 may include but not limited to random access memory (random access memory, RAM), read-only memory (read-only memory, ROM), erasable In addition to programmable read-only memory (erasable programmable read only memory, EPROM) or portable read-only memory (compact disc read-only memory, CD-ROM), etc.

The communication interface 1103 includes a sending interface and a receiving interface, and there may be multiple communication interfaces 1103, which are used to support the device 1100 to communicate, for example, to receive or send data or messages.

Exemplarily, the processor 1101 may be a central processing unit, a general processor, a digital signal processor, an application specific integrated circuit, a field programmable gate array or other programmable logic device, a transistor logic device, a hardware component or any combination thereof. The processor can also be a combination that implements computing functions, such as a combination of one or more microprocessors, a combination of a digital signal processor and a microprocessor, and the like. The processor 1101 may be configured to read the program stored in the above-mentioned memory 1102, so that the apparatus 1100 executes the operations performed by the executing device in any one of the path planning methods described above in FIG. 4 and its possible embodiments.

In a possible implementation manner, the processor 1101 may be configured to read the program stored in the above-mentioned memory 1102, and perform the following operations: configure a tunnel equivalent cost multipath ECMP group for traffic load balancing on the first network device, where , the members of the tunnel ECMP group are composed of multiple tunnels, the multiple tunnels include the first tunnel, and the first tunnel forwards traffic to the destination address based on the first path; when the first path fails, according to the multiple tunnels Except for the path information of each other path passed by each tunnel other than the first tunnel, a second path is calculated, and the second path is disjoint with each other path; rerouting the first tunnel to the second path Two paths.

In another possible implementation manner, the processor 1101 may be configured to read the program stored in the above-mentioned memory 1102, and perform the following operation: calculate the first path passed by the first tunnel between the first network device and the second network device ; Set path information for the target object in the first path, the target object is a link, or the target object is a network device, or the target object is a network device communication interface; calculate the first network device and the second network device based on the path information The second path passed by the second tunnel between the two network devices, wherein the first path and the second path are disjoint, in other words, at least one of the target objects in the second path is not configured with the path information. The first tunnel and the second tunnel belong to a tunnel ECMP group member.

For specific operations and beneficial effects of each unit in the apparatus 1100 shown in FIG. 11 , refer to the corresponding descriptions in FIG. 4 and its possible method embodiments above, and details are not repeated here.

The embodiment of the present application also provides a computer-readable storage medium, the computer-readable storage medium stores a computer program, and the computer program is executed by a processor to implement the above-mentioned any embodiment in FIG. 4 and its possible method embodiments. perform the operations performed by the device described in the method described above.

The embodiment of the present application also provides a computer program product. When the computer program product is read and executed by a computer, the execution device in the method described in any one of the above-mentioned FIG. 4 and its possible method embodiments operation will be executed.

To sum up, this application solves the problem of network congestion after a failure by planning a path that is disjoint with the existing path of the ECMP member of the tunnel used for load balancing after the path in the tunnel fails. In addition, the existing solution based on constraint planning path still needs to follow the constraint path after failure, and cannot reroute to other feasible paths, resulting in service interruption and reducing network reliability. This application can quickly reroute after path failure To another equal-cost path to achieve load sharing of traffic, reducing network congestion.

Finally, it should be noted that: the above embodiments are only used to illustrate the technical solutions of the present application, and are not intended to limit it; although the application has been described in detail with reference to the foregoing embodiments, those of ordinary skill in the art should understand that: It is still possible to modify the technical solutions described in the foregoing embodiments, or perform equivalent replacements for some or all of the technical features; and these modifications or replacements do not make the essence of the corresponding technical solutions deviate from the technical solutions of the various embodiments of the application. scope.

Claims (45)

1. A path planning method, characterized in that the method comprises: A tunnel equivalent multipath ECMP group for traffic load balancing is configured on the first network device, wherein members of the tunnel ECMP group are composed of multiple tunnels, the multiple tunnels include a first tunnel, and the first The tunnel forwards the traffic to the destination address based on the first path; When a failure occurs on the first path, a second path is calculated according to the path information of each path passed by each of the multiple tunnels except the first tunnel, and the second path is the same as each of said other paths is disjoint; rerouting the first tunnel to the second path. 2. The method of claim 1, wherein the second path is disjoint to each of the other paths, comprising at least one of the following: Links between the second path and each of the other paths are disjoint; Node disjoint between the second path and each of the other paths; Neither the link nor the node intersects between the second path and each of the other paths; The second path and each of the other paths are best effort disjoint. 3. The method according to claim 1 or 2, wherein the path information is only valid for members in the tunnel ECMP group. 4. The method according to any one of claims 1-3, wherein the path information includes at least one of the following: the link cost of each link in each of the other paths; a link priority for each link in each of said other paths; A link identifier of each link in each of the other paths, where the link identifier of each link is used to identify that each link has been occupied by the tunnel ECMP group; A device identifier of each network device in each of the other paths, where the device identifier of each network device is used to identify that each network device has been occupied by the tunnel ECMP group; An interface identifier of each network device communication interface in each of the other paths, where the interface identifier of each network device communication interface is used to identify that each network device communication interface has been occupied by the tunnel ECMP group. 5. The method according to claim 4, wherein the path information includes the link cost of each link, and the calculating the second path comprises: Determine a plurality of links passed by the second path according to the link cost of each link. 6. The method according to claim 5, characterized in that, after configuring the tunnel ECMP group, comprising: Adjusting the link overhead of each link in the tunnel ECMP group, where the adjusted link overhead of each link is greater than the link overhead of each link before adjustment. 7. The method according to claim 4, wherein the path information includes the link priority of each link, and the calculating the second path comprises: A plurality of links passed by the second path are determined according to the link priority of each link. 8. The method according to claim 7, characterized in that, after configuring the tunnel ECMP group, comprising: Adjusting the link priority of each link in the tunnel ECMP group, where the adjusted link priority of each link is smaller than the pre-adjusted link priority of each link. 9. The method according to claim 4, wherein the path information includes a link identifier of each link, and the calculating the second path comprises: A plurality of links passed by the second path are determined according to the link identifier of each link. 10. The method according to claim 9, further comprising: After the tunnel ECMP group is configured, the link identifier is set for each link in the tunnel ECMP group. 11. The method according to claim 4, wherein the path information includes a device identifier of each network device in each of the other paths, and the calculating the second path comprises: A plurality of network devices passed by the second path are determined according to the device identifier of each network device in each of the other paths. 12. The method of claim 11, further comprising: After the tunnel ECMP group is configured, the device identifier is set for each network device of each path in the tunnel ECMP group. 13. The method according to claim 4, wherein the path information includes an interface identifier of each network device communication interface in each of the other paths, and the calculating the second path comprises: In the case that the network device communication interface is an inbound interface of a network device in a path, according to the first interface identifier of each inbound interface of a network device in each of the other paths, determine how many times the second path passes through a network device ingress interface; In the case that the network device communication interface is an outgoing interface of the network device in the path, according to the second interface identifier of each outgoing interface of the network device in each of the other paths, determine how many times the second path passes through outbound interface of a network device. 14. The method of claim 13, further comprising: In the case where the network device communication interface is an ingress interface of a network device in a path, after configuring the tunnel ECMP group, set the second ingress interface for each network device that each path passes through in the tunnel ECMP group an interface identifier; In the case where the network device communication interface is an outgoing interface of a network device in a path, after configuring the tunnel ECMP group, set the first for each network device outgoing interface that each path in the tunnel ECMP group passes through. Two interface identifiers. 15. A path planning method, characterized in that the method comprises: calculating a first path passed by a first tunnel between the first network device and the second network device, the first tunnel being a member of a tunnel equivalent cost multipath ECMP group; Setting path information for a target object in the first path, where the target object is a link, or the target object is a network device, or the target object is a communication interface of a network device; Based on the path information, calculate a second path passed by a second tunnel between the first network device and the second network device, the first path is disjoint to the second path, and the second path is the Member of the tunnel ECMP group. 16. The method according to claim 15, wherein the path information is only valid for members in the tunnel ECMP group. 17. The method according to claim 15 or 16, wherein the target object is a link, and setting path information for the target object in the first path comprises: Adjusting the link overhead of each link in the first path, where the adjusted link overhead of each link in the first path is greater than the unadjusted link overhead of each link in the first path The link cost of the path information includes the adjusted link cost of each link in the first path. 18. The method according to claim 15 or 16, wherein the target object is a link, and setting path information for the target object in the first path comprises: Adjusting the link priority of each link in the first path, where the adjusted link priority of each link in the first path is smaller than that of each link in the first path before adjustment A link priority of a link, where the path information includes the adjusted link priority of each link in the first path. 19. The method according to claim 15 or 16, wherein the target object is a link, and setting path information for the target object in the first path comprises: Setting a link identifier for each link in the first path, where the link identifier of each link in the first path is used to identify that each link in the first path has been The tunnel ECMP group occupies, and the path information includes the link identifier of each link in the first path. 20. The method according to claim 15 or 16, wherein the target object is a network device, and setting path information for the target object in the first path comprises: Setting a device identifier for each network device in the first path, where the device identifier of each network device in the first path is used to identify that each network device in the first path has been identified by the Tunnel ECMP group occupation, the path information includes the device identifier of each network device in the first path. 21. The method according to claim 15 or 16, wherein the target object is a network device communication interface, and setting path information for the target object in the first path comprises: In the case where the network device communication interface is an incoming interface of a network device in a path, a first interface identifier is set for each incoming interface of a network device in the first path, and each network device in the first path The first interface identifier of the incoming interface is used to identify that the incoming interface of each network device in the first path has been occupied by the tunnel ECMP group, and the path information includes each network device in the first path The first interface identifier of the incoming interface; In the case where the network device communication interface is an outgoing interface of the network device in the path, a second interface identifier is set for each outgoing interface of the network device in the first path, and each network device in the first path The second interface identifier of the outgoing interface is used to identify that the outgoing interface of each network device in the first path has been occupied by the tunnel ECMP group, and the path information includes each network device in the first path The second interface identifier of the outbound interface. 22. A path planning device, characterized in that the device comprises: A configuration unit, configured to configure a tunnel equivalent multipath ECMP group for traffic load balancing on the first network device, wherein the members of the tunnel ECMP group are composed of multiple tunnels, and the multiple tunnels include the first tunnel , the first tunnel forwards traffic to the destination address based on the first path; A calculation unit, configured to calculate a second path according to the path information of each path passed by each of the multiple tunnels except the first tunnel when a failure occurs on the first path, so said second path is disjoint from said each other path; a rerouting unit, configured to reroute the first tunnel to the second path. 23. The device of claim 22, wherein the second path is disjoint from each of the other paths and comprises at least one of the following: Links between the second path and each of the other paths are disjoint; Node disjoint between the second path and each of the other paths; Neither the link nor the node intersects between the second path and each of the other paths; The second path and each of the other paths are best effort disjoint. 24. The device according to claim 22 or 23, wherein the path information is only valid for members in the tunnel ECMP group. 25. The device according to any one of claims 22-24, wherein the path information includes at least one of the following: the link cost of each link in each of the other paths; a link priority for each link in each of said other paths; A link identifier of each link in each of the other paths, where the link identifier of each link is used to identify that each link has been occupied by the tunnel ECMP group; A device identifier of each network device in each of the other paths, where the device identifier of each network device is used to identify that each network device has been occupied by the tunnel ECMP group; An interface identifier of each network device communication interface in each of the other paths, where the interface identifier of each network device communication interface is used to identify that each network device communication interface has been occupied by the tunnel ECMP group. 26. The device according to claim 25, wherein the path information includes the link overhead of each link, and the calculation unit is specifically used for: Determine a plurality of links passed by the second path according to the link cost of each link. 27. The device according to claim 26, characterized in that the device further comprises a first adjustment unit, configured to, after configuring the tunnel ECMP group, Adjusting the link overhead of each link in the tunnel ECMP group, where the adjusted link overhead of each link is greater than the link overhead of each link before adjustment. 28. The device according to claim 25, wherein the path information includes the link priority of each link, and the calculation unit is specifically used for: A plurality of links passed by the second path are determined according to the link priority of each link. 29. The device according to claim 28, characterized in that the device further comprises a second adjustment unit, configured to, after configuring the tunnel ECMP group, Adjusting the link priority of each link in the tunnel ECMP group, where the adjusted link priority of each link is smaller than the pre-adjusted link priority of each link. 30. The device according to claim 25, wherein the path information includes a link identifier of each link, and the calculation unit is specifically configured to: A plurality of links passed by the second path are determined according to the link identifier of each link. 31. The device according to claim 30, characterized in that the device further comprises a first setting unit configured to, after the tunnel ECMP group is configured, set the set value for each link in the tunnel ECMP group The above link ID. 32. The device according to claim 25, wherein the path information includes a device identifier of each network device in each of the other paths, and the computing unit is specifically configured to: A plurality of network devices passed by the second path are determined according to the device identifier of each network device in each of the other paths. 33. The device according to claim 32, characterized in that the device further comprises a second setting unit, configured to, after configuring the tunnel ECMP group, configure The device sets the device identifier. 34. The device according to claim 25, wherein the path information includes an interface identifier of each network device communication interface in each of the other paths, and the computing unit is specifically configured to: In the case that the network device communication interface is an inbound interface of a network device in a path, according to the first interface identifier of each inbound interface of a network device in each of the other paths, determine how many times the second path passes through a network device ingress interface; In the case that the network device communication interface is an outgoing interface of the network device in the path, according to the second interface identifier of each outgoing interface of the network device in each of the other paths, determine how many times the second path passes through outbound interface of a network device. 35. The device according to claim 34, further comprising a third setting unit, configured to: In the case where the network device communication interface is an ingress interface of a network device in a path, after configuring the tunnel ECMP group, set the second ingress interface for each network device that each path passes through in the tunnel ECMP group an interface identification; In the case where the network device communication interface is an outgoing interface of a network device in a path, after configuring the tunnel ECMP group, set the first for each network device outgoing interface that each path in the tunnel ECMP group passes through. Two interface identifiers. 36. A path planning device, characterized in that the device comprises: A calculation unit, configured to calculate a first path passed by a first tunnel between the first network device and the second network device, the first tunnel belonging to a member of the tunnel equivalent cost multipath ECMP group; A setting unit, configured to set path information for a target object in the first path, where the target object is a link, or the target object is a network device, or the target object is a communication interface of a network device; The calculation unit is further configured to calculate a second path passed by the second tunnel between the first network device and the second network device based on the path information, the first path is disjoint to the second path, and the The second tunnel is a member of the tunnel ECMP group. 37. The device according to claim 36, wherein the path information is only valid for members in the tunnel ECMP group. 38. The device according to claim 36 or 37, wherein the target object is a link, and the setting unit is specifically used for: Adjusting the link overhead of each link in the first path, where the adjusted link overhead of each link in the first path is greater than the unadjusted link overhead of each link in the first path The link cost of the path information includes the adjusted link cost of each link in the first path. 39. The device according to claim 36 or 37, wherein the target object is a link, and the setting unit is specifically used for: Adjusting the link priority of each link in the first path, where the adjusted link priority of each link in the first path is smaller than that of each link in the first path before adjustment A link priority of a link, where the path information includes the adjusted link priority of each link in the first path. 40. The device according to claim 36 or 37, wherein the target object is a link, and the setting unit is specifically used for: Setting a link identifier for each link in the first path, where the link identifier of each link in the first path is used to identify that each link in the first path has been The tunnel ECMP group occupies, and the path information includes the link identifier of each link in the first path. 41. The device according to claim 36 or 37, wherein the target object is a network device, and the setting unit is specifically used for: Setting a device identifier for each network device in the first path, where the device identifier of each network device in the first path is used to identify that each network device in the first path has been identified by the Tunnel ECMP group occupation, the path information includes the device identifier of each network device in the first path. 42. The device according to claim 36 or 37, wherein the target object is a network device communication interface, and the setting unit is specifically used for: In the case where the network device communication interface is an incoming interface of a network device in a path, a first interface identifier is set for each incoming interface of a network device in the first path, and each network device in the first path The first interface identifier of the incoming interface is used to identify that the incoming interface of each network device in the first path has been occupied by the tunnel ECMP group, and the path information includes each network device in the first path The first interface identifier of the incoming interface; In the case where the network device communication interface is an outgoing interface of the network device in the path, a second interface identifier is set for each outgoing interface of the network device in the first path, and each network device in the first path The second interface identifier of the outgoing interface is used to identify that the outgoing interface of each network device in the first path has been occupied by the tunnel ECMP group, and the path information includes each network device in the first path The second interface identifier of the outbound interface. 43. A path planning device, characterized in that it comprises a processor and a memory; wherein the memory is used to store a computer program, and the processor is used to call the computer program, so that the device executes the method according to claim 1 - the method according to any one of claims 14; or, the processor is used to call the computer program, so that the device executes the method according to any one of claims 15-21. 44. A computer-readable storage medium, wherein the computer-readable storage medium stores a computer program, and when the computer program is executed by a processor, the method according to any one of claims 1-21 is implemented. 45. A computer program product, comprising a computer program, characterized in that, when the computer program is executed by a processor, the method according to any one of claims 1-21 is implemented.

Images