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.