Precomputing high quality routes for bandwidth guaranteed traffic

We investigate the problem of precomputing bandwidth guaranteed paths as a cheaper replacement for on-demand routing. The focus in the prior precomputation literature has been on minimizing storage and computational overhead of the precomputation process. This paper instead explores the 'quality' of precomputed paths and attempts to answer the following question: given a traffic ingress-egress node pair and storage for k routes, what paths should be materialized for good routing performance? We argue that the min-hop formulation typically assumed in prior precomputation work is a poor offline strategy. We instead propose an efficient maxflow based algorithm called MobiFlow. We show via simulations that it outperforms min-hop algorithms such as K-shortest path on several metrics including number of requests rejected and the fraction of the bandwidth routed. Furthermore, the algorithm has a low computational complexity and degrades gracefully on network failures, making it very attractive to implement in practice.