Method for routing of label switched paths (LSPS) through an internet supporting multi-protocol label switching (MPLS) technology

• US 20030214938A1
• Filed: 03/17/2003
• Published: 11/20/2003
• Est. Priority Date: 03/21/2002
• Status: Abandoned Application

• Current Assignee: Himachal Futuristic Communications Limited
• Original Assignee: Himachal Futuristic Communications Limited
• Inventors: Jindal, Deepak Kumar, Kumar, Anurag, Kuri, Joy
• Application Number:
  US10/388,765
• Publication Number:
  US 20030214938A1
• Time in Patent Office: Days
• US Class Current: 370/351
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/38 Flow based routing
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]

Abstract

The Internet has evolved to a stage where it is expected to support transfer of not only elastic traffic but also real-time traffic with delay, jitter and loss guarantees. Upon the arrival of a request it is necessary to find a path through the network that has sufficient capacity—this is referred to as ‘routing’. It is essential to set up Virtual Paths through a network of routers. Such Virtual Paths are called Label switched Paths (LPs) in MPLS terminology. The arrived request for ingress-egress pair (S,D)₁ must be routed along a single (unsplit) path in such a way that the minimum unsplit flow between all other ingress-egress pairs is maximized; here all other ingress-egress pairs have traffic flowing simultaneously. Thus explaining the name Maximum Minimum Additional Flow Routing Algorithm (MMAFRA).

MMAFRA has 2 phases:

1. Off Line Phase

a) Enumerate all paths for all ingress-egress pairs.

b) For each pair obtain the set of links utilized by one or more paths by that pair. This set is called the ‘link set’ for that pair.

c) For each link, obtain its ‘weight’ as the number of all ingress-egress pairs whose link sets contain that link.

2. On Line Phase

It begins with the arrival of a bandwidth demand for the ingress-egress pair (j) with a bandwidth demand of D (say). Then

a) Eliminate all links, which have residual capacities less than D units and obtain a reduced network.

b) Update the weight of each link in the reduced network by considering the residual capacity of the link; the weight should increase as the residual capacity decreases.

c) Use the updated weights and apply Dijkstra'"'"'s algorithm to compute the least—weight path for the ingress-egress pair (j).

d) The route for the LSP request is given by the least-weight path above. Finally, the residual capacities of links in the least-weight path are also up-dated.

Claims

1. ) A routing method that routes an arrived bandwidth-demand in an unsplit way so as to explicitly maximise the smallest unsplit flow that can be routed in future between all other ingress-egress pairs simultaneously.

2. ) The routing method of claim 1 further including a method of assigning weights to links for efficient implementation of method in claim 1.