Constrained virtual path routing algorithms in packet networks

Abstract

We presented a new algorithm for on-line routing of Virtual Paths in a packet network. The main application of the algorithm is in explicit routing o f LSPs in MPLS networks. We modeled the routing problem as a mixed integer linear programming problem. We proposed an optimization objective that maximizes the minimum flow that we can put between all other ingress-egress pairs simultaneously. The on-line phase of our algorithm is quite simple and computationally as efficient as Min-Hop routing, and substantially faster than the Minimum Interference Routing Algorithm [22]. We proposed a novel link-weight assignment scheme where a link weight takes into account the residual capacity o f the link, as well as the number of source-destination pairs that could potentially use the link. We simulated the algorithm on three networks and found that our algorithm performs very well in terms o f LSP acceptance in comparison to Min-Hop and M IRA for RINGnet and NSFnet, and as well as M IRA for MIRAnet. Finally we studied the routing problem in which we want to maximize the revenue. The problem is formulated for off-line case. An approximation algorithm for the off-line revenue optimization problem is given.