Method and apparatus for instantiating a path with the minimum number of segments

• US 10,326,688 B2
• Filed: 05/25/2017
• Issued: 06/18/2019
• Est. Priority Date: 05/25/2017
• Status: Active Grant

• Current Assignee: Alcatel-Lucent Canada Incorporated (Nokia Corporation), Nokia of America Corporation (Nokia Corporation)
• Original Assignee: Alcatel-Lucent Canada Incorporated (Nokia Corporation), Nokia of America Corporation (Nokia Corporation)
• Inventors: Hao, Fang, Kodialam, Murali, Lakshman, T. V., Rezaaifar, Ehsan
• Primary Examiner(s): Lopata, Robert J
• Application Number:
  US15/605,712
• Publication Number:
  US 20180343190A1
• Time in Patent Office: 754 Days
• Field of Search: 370392
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/14 Routing performance; Theoretical aspects
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]
• CPC Class Codes: H04Q 2213/13138 Least cost routing, LCR

Abstract

Various embodiments relate to a method and apparatus for computing a minimum segment labeling of a given path on a segment cover graph, the method including receiving a connection request for a connection between a source node and a destination node, generating a Shortest Path Directed Acyclic Graph (“SPDAG”) from the source node to the destination node by running a shortest path algorithm from the source node, determining an end node, between the source node and the destination node, at which the SPDAG deviates from the given path, determining whether the end node is the end of an Equal Cost Multipath (“ECMP”) and terminating the shortest path algorithm at a predecessor node to the end node if the end node is the end of an ECMP and making the predecessor node to the end node the source node.

Claims

1. A method for computing a minimum segment labeling of a given path on a segment cover graph, the method comprising:

receiving a connection request for a connection between a source node and a destination node;

generating a Shortest Path Directed Acyclic Graph (“

SPDAG”

) from the source node by running a shortest path algorithm;

determining an end node, between the source node and the destination node, at which the SPDAG deviates from the given path; and

determining whether the end node is the end of an Equal Cost Multipath (“

ECMP”

);

terminating the shortest path algorithm at a predecessor node to the end node, wherein a counter provides a number of predecessor nodes and determines whether a shortest path from the source node to the end node is unique, when the end node is the end of the ECMP.

2. The method of claim 1, further comprising:

terminating the shortest path algorithm at the end node when the end node is not the end of the ECMP; and

making the end node the source node.

3. The method of claim 1, further comprising:

determining whether the destination node has been reached.

4. The method of claim 1, further comprising:

storing the minimum segment labeling of the given path.

5. The method of claim 1, wherein after a number of predecessor nodes from the end node is greater than 1, then the end node is the end of the ECMP.

6. The method of claim 1, wherein determining whether the end node is the end of the ECMP is determining whether the shortest path from the source node to the end node is unique.

13. The method of claim 1, further comprising:

making the predecessor node to the end node the source node.

7. A non-transitory machine-readable storage medium encoded with instructions executable to perform a method by a processor on a router for computing a minimum segment labeling of a given path on a segment cover graph, the machine-readable storage medium comprising:

instructions for receiving a connection request for a connection between a source node and a destination node;

instructions for generating a Shortest Path Directed Acyclic Graph (“

SPDAG”

) from the source node by running a shortest path algorithm;

instructions for determining an end node, between the source node and the destination node, at which the SPDAG deviates from the given path;

instructions for determining whether the end node is the end of an Equal Cost Multipath (“

ECMP”

), and

instructions for terminating the shortest path algorithm at a predecessor node to the end node, wherein a counter provides a number of predecessor nodes and determines whether a shortest path from the source node to the end node is unique, when the end node is the end of the ECMP.

8. The non-transitory machine-readable storage medium of claim 7, further comprising:

instructions for terminating the shortest path algorithm at the end node when the end node is not the end of the ECMP and making the end node the source node.

9. The non-transitory machine-readable storage medium of claim 7, further comprising:

instructions for storing the minimum segment labeling of the given path.

10. The non-transitory machine-readable storage medium of claim 7, further comprising:

instructions for determining whether the destination node has been reached.

11. The non-transitory machine-readable storage medium of claim 7, wherein after a number of predecessor nodes from the end node is greater than 1, then the end node is the end of the ECMP.

12. The non-transitory machine-readable storage medium of claim 7, wherein determining whether the end node is the end of the ECMP is determining whether the shortest path from the source node to the end node is unique.

14. The non-transitory machine-readable storage medium of claim 7, further comprising:

instructions for making the predecessor node to the end node the source node.