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

摘要

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.