Performance evaluation of K shortest path algorithms in MPLS traffic engineering

A number of on-line and off-line algorithms for load balancing on multiple paths for MPLS (MultiProtocol Label Switching) traffic engineering have now been proposed, in which it is always assumed that sets of LSPs (Label Switched Path) have already been established between node pairs. While how to choose these paths is an important issue in traffic engineering, it has not been well studied yet. In this paper, we attempt to fill in this gap. As the shortest paths are always preferred in routing problems, we evaluate several k shortest path algorithms from the viewpoint of bandwidth use efficiency and the number of the found paths. Extensive simulations have been performed in different kinds of topologies to factor out effects of network characteristics on these algorithms' path calculation performances. It is found out that the performances of the evaluated algorithms are limited in some cases and the design of new algorithms for the path calculation problem is worth studying in the future.