A precomputation scheme for minimum interference routing: the least-critical-path-first algorithm

This paper focuses on the selection of bandwidth-guaranteed channels for communication sessions that require it. The basic idea comes from minimum interference routing: select a feasible path that puts the least possible restriction on the available transmission capacity of other communicating parties. This is achieved by circumventing some critical bottleneck links. The main contribution of the paper is a novel characterization of link criticality, the criticality threshold, which can be readily precompiled for routing dozens of subsequent calls. Based on this finding we define a generic precomputation framework for minimum interference routing, the least-critical-path-first routing algorithm. We show by means of extensive simulations that efficient route precomputation is possible even in the case, when accurate resource availability information is not immediately available.