Method and apparatus for minimum label bandwidth guaranteed path for segment routing

Patent metadata

Field	Value
Publication number	US-10348610-B2
Application number	US-201715605749-A
Country	US
Kind code	B2
Filing date	May 25, 2017
Priority date	May 25, 2017
Publication date	Jul 9, 2019
Grant date	Jul 9, 2019

Abstract

Various embodiments relate to a non-transitory computer readable medium and method thereof for finding a minimum hop path in a segment graph traversing the least number of links in a physical topology, the method including receiving a connection request for a connection between a source node and a destination node, computing the segment graph, the segment graph having a plurality of links, computing a bandwidth for each of the plurality of links in the segment graph, computing the number of links for a shortest path (“N(q)”) for each of the plurality of links, eliminating each of the plurality of link with a bandwidth less than the minimum bandwidth and selecting the shortest path in the physical topology between the plurality of links.

First claim

What is claimed is:

1. A method for finding a minimum hop path in a segment graph traversing a least number of links in a physical topology, the method comprising:
receiving a connection request for a connection between a source node and a destination node;
computing the segment graph, wherein the segment graph has a plurality of links;
computing a bandwidth (“c(q)”) for each of the plurality of links in the segment graph;
computing a number of links for a shortest path (“N(q)”) for each of the plurality of links;
eliminating each of the plurality of links with a bandwidth less than a minimum bandwidth to define a subset of the plurality of links, and
selecting the shortest path in the segment graph between the source node and the destination node using the subset of the plurality of links based, for each node between the source node and the destination node, upon a number of hops in the segment graph from the source node and a number of links in the physical topology from the source node.

2. The method of claim 1 , further comprising:
storing the shortest path in an optimum path set.

3. The method of claim 1 , further comprising:
calculating the bandwidth for each of the plurality of links in the segment graph by

c
⁡

(
q
)

=

min

e
∈

SP
⁡

(
q
)

⁢

c
⁡

(
e
)

⁢

∀

q
∈

G
s

.

4. The method of claim 1 , further comprising:
calculating the number of links for the shortest path for each of the plurality of links by N(q)=|SP(q)|∀q∈G s .

5. The method of claim 1 , wherein when the sum of the number of hops in the segment graph from the source node to a node v (“D(v)”) and one is less than the number of hops from the source node to a node w (“D(w)”), then D(w) is equal to D(v)+1 and the number of links in the physical topology from the source node to the node w (“L(w)”) is equal to the sum of the number of links in the physical topology from the source node to the node v (“L(v)”) and the number of links for a shortest path for link q (“N(q)”), which is one of the plurality of links.

6. The method of claim 5 , wherein when a sum of D(v) and one is equal to D(w) and a sum of L(v) and N(q) is less than L(w), then L(w)=L(v).

7. A non-transitory machine-readable storage medium encoded with instructions executable to perform a method by a processor on a router, the non-transitory machine-readable storage medium comprising:
instructions for receiving a connection request for a connection between a source node and a destination node;
instructions for computing a segment graph, the segment graph having a plurality of links;
instructions for computing a bandwidth (“c(q)”) for each of the plurality of links in the segment graph;
instructions for computing a number of links for a shortest path (“N(q)”) for each of the plurality of links;
instructions for eliminating each of the plurality of links with a bandwidth less than a minimum bandwidth, and
instructions for selecting the shortest path in the segment graph between the source node and the destination node using a subset of the plurality of links based, for each node between the source node and the destination node, upon a number of hops in the segment graph from the source node and a number of links in the physical topology from the source node.

8. The non-transitory machine-readable storage medium of claim 7 , further comprising:
instructions for storing the shortest path in an optimum path set.

9. The non-transitory machine-readable storage medium of claim 7 , further comprising:
instructions for calculating the bandwidth for each of the plurality of links in the segment graph by

c
⁡

(
q
)

=

min

e
∈

SP
⁡

(
q
)

⁢

c
⁡

(
e
)

⁢

∀

q
∈

G
s

.

10. The non-transitory machine-readable storage medium of claim 7 , further comprising:
instructions for calculating the number of links for the shortest path for each of the plurality of links by N(q)=|SP(q)|∀q∈G s .

11. The non-transitory machine-readable storage medium of claim 7 , wherein when the sum of a number of hops in the segment graph from the source node to a node v (“D(v)”) and one is less than the number of hops from the source node to a node w (“D(w)”), then D(w) is equal to D(v)+1 and the number of links in the physical topology from the source node to the node w (“L(w)”) is equal to the sum of the number of links from in the physical topology from the source node to the node v (“L(v)”) and the number of links for a shortest path for link q (“N(q)”), which is one of the plurality of links.

12. The non-transitory machine-readable storage medium of claim 11 , wherein when a sum of D(v) and one is equal to D(w) and a sum of L(v) and N(q) is less than L(w), then L(w)=L(v).

Assignees

• Hao Fang
• Kodialam Murali
• Lakshman T V
• Rezaaifar Ehsan
• Alcatel Lucent
• Nokia America Corp

Inventors

• Hao Fang
• Kodialam Murali
• Lakshman T V
• Rezaaifar Ehsan

Classifications

• H04L45/745

  Address table lookup; Address filtering · CPC title

• H04L45/50

  using label swapping, e.g. multi-protocol label switch [MPLS] · CPC title

• H04L45/20

  Hop count for routing purposes, e.g. TTL · CPC title

• H04L45/125 Primary

  based on throughput or bandwidth · CPC title

• H04L45/34 Primary

  Source routing · CPC title