Path calculation method, apparatus, and device

Patent metadata

Field	Value
Publication number	US-11929915-B2
Application number	US-202117401101-A
Country	US
Kind code	B2
Filing date	Aug 12, 2021
Priority date	Feb 13, 2019
Publication date	Mar 12, 2024
Grant date	Mar 12, 2024

Abstract

A path calculation method, apparatus, and device, to implement network slicing. The path calculation method includes: obtaining an algorithm constraint supported by each of a plurality of network devices, where the algorithm constraint is a constraint of a forwarding path algorithm, and the forwarding path algorithm is used to calculate, for the network device, a forwarding path that meets the algorithm constraint; performing network topology division on the plurality of network devices, where network devices in a same network topology support a same algorithm constraint; and calculating a forwarding path between network devices in each network topology based on the algorithm constraint, of the forwarding path algorithm, corresponding to the network topology.

First claim

What is claimed is:

1. A method comprising:
obtaining an algorithm constraint supported by each of a plurality of network devices, wherein the algorithm constraint is a constraint of a forwarding path algorithm, wherein the algorithm constraint comprises a flexible algorithm (Flex Algo);
performing network topology division on the plurality of network devices to form a network topology, wherein network devices in a same network topology support a same Flex Algo, wherein each network device in the network topology has a sub-interface corresponding to the same Flex Algo; and
calculating a forwarding path between network devices in one network topology based on the same Flex Algo supported by the network devices in the one network topology.

2. The method according to claim 1 , wherein the method further comprises:
receiving a request message for establishing a packet path from an ingress node, wherein the request message comprises a flow identifier of a packet;
determining, based on the flow identifier, the network topology for forwarding the packet using a forwarding path of the network topology;
generating a label stack corresponding to the forwarding path, wherein the label stack comprises an adjacency segment identifier and/or a node segment identifier of a network device on the forwarding path; and
sending the label stack to the ingress node.

3. The method according to claim 1 , wherein the algorithm constraint comprises an identifier of the Flex Algo and/or a link attribute comprised in the forwarding path algorithm.

4. The method according to claim 1 , wherein the method further comprises:
establishing, a first mapping relationship for each sub-interface corresponding to the same Flex Algo, wherein the first mapping relationship comprises a sub-interface information and the same Flex Algo or a sub-interface information and a color corresponding to the same Flex Algo; and
sending, to the plurality of network devices, the first mapping relationship, wherein the first mapping relationship is used by the corresponding network device to forward a packet.

5. The method according to claim 1 , wherein the sub-interface has a color as link attribute, and the Flex Algo has the color as a constraint.

6. A method applied to a first network device, comprising:
obtaining a first algorithm constraint supported by the first network device, wherein the first algorithm constraint is a constraint of a forwarding path algorithm, wherein the first algorithm constraint comprises a flexible algorithm (Flex Ago);
determining a second network device supporting a same Flex Algo as the Flex Algo supported by the first network device, and determining that the first network device and the second network device that support the same Flex Algo belong to one network topology, wherein the first network device has a first sub-interface corresponding to the Flex Algo, the second network device has a second sub-interface corresponding to the Flex Algo, wherein the first sub-interface and the second sub-interface belong to the network topology; and
calculating a first forwarding path from the first network device to the second network device in the one network topology based on the Flex Algo supported by the first network device and the second network device, wherein the first forwarding path comprises the first network device and the second network device.

7. The method according to claim 6 , wherein the first algorithm constraint comprises an identifier of the forwarding path algorithm and/or a link attribute comprised in the forwarding path algorithm.

8. The method according to claim 6 , wherein the method further comprises:
obtaining a forwarding entry for the first network device, wherein the forwarding entry comprises a segment identifier (SID) and the first sub-interface;
obtaining a packet, determining the forwarding entry based on the packet; and
forwarding the packet by the first sub-interface in the forwarding entry.

9. The method according to claim 6 , wherein the first sub-interface has a color as link attribute, the second sub-interface has the color as link attribute, and the Flex Algo has the color as a constraint.

10. An apparatus comprising:
a non-transitory memory storage comprising instructions; and
one or more processors in communication with the memory storage, wherein the instructions, when executed by the one or more processors, cause the apparatus to:
obtain an algorithm constraint supported by each of a plurality of network devices, wherein the algorithm constraint is a constraint of a forwarding path algorithm, wherein the algorithm constraint comprises a flexible algorithm (Flex Algo);
perform network topology division on the plurality of network devices to form network topology, wherein network devices in a same network topology support a same Flex Algo, wherein each network device in the network topology has a sub-interface corresponding to the same Flex Algo; and
calculate a forwarding path between network devices in one network topology based on the same Flex Algo.

11. The apparatus according to claim 10 , wherein the algorithm constraint comprises an identifier of the forwarding path algorithm and/or a link attribute comprised in the forwarding path algorithm.

12. The apparatus according to claim 10 , wherein the instructions, when executed by the one or more processors, cause the apparatus further to:
establish, a first mapping relationship for each sub-interface corresponding to the same Flex Algo, wherein the first mapping relationship comprises a sub-interface information and the same Flex Algo or a sub-interface information and a color corresponding to the same Flex Algo; and
send, to the plurality of network devices, the first mapping relationship, wherein the first mapping relationship is used by the corresponding network device to forward a packet.

13. The apparatus according to claim 10 , wherein the sub-interface has a color as link attribute, and the Flex Algo has the color as a constraint.

14. An apparatus, wherein the apparatus is applied to a first network device, and the apparatus comprises:
a non-transitory memory storage comprising instructions; and
one or more processors in communication with the memory storage, wherein the instructions, when executed by the one or more processors, cause the apparatus to:
obtain a first algorithm constraint supported by the first network device, wherein the first algorithm constraint is a constraint of a forwarding path algorithm, wherein the first algorithm constraint comprises a flexible algorithm (Flex Algo);
determine a second network device supporting a same FlexAlgo as the Flex Algo supported by the first network device, and determine that the first network device and the second network device that support the same Flex Algo are in one network topology, wherein the first network device has a first sub-interface corresponding to the Flex Algo, the second network device has a second sub-interface corresponding to the Flex Algo, wherein the first sub-interfaces and the second sub-interfaces belong to the network topology; and
calculate a first forwarding path from the first network device to the second network device in the one network topology based on the Flex Algo supported by the first network device and the second network device, wherein the first forwarding path comprises the first network device and the second network device.

15. The apparatus according to claim 14 , wherein first the algorithm constraint comprises an identifier of the Flex Algo and/or a link attribute comprised in the forwarding path algorithm.

Assignees

• Huawei Tech Co Ltd

Inventors

• Chen Chuang
• Hu Zhibo
• Dong Jie
• Yao Junda

Classifications

• H04L45/02 Primary

  Topology update or discovery · CPC title

• H04L41/122

  of virtualised topologies, e.g. software-defined networks [SDN] or network function virtualisation [NFV] · CPC title

• H04L45/16 Primary

  Multipoint routing · CPC title

• H04L45/124

  using a combination of metrics · CPC title

• H04L45/127

  based on intermediate node capabilities · CPC title