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

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)1 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.

Dependencies are inferred from the claim text.