Precomputing High Quality Routes for Bandwidth Guaranteed Traffic

We investigate the problem of precomputing good quality bandwidth guaranteed paths as a cheaper replacement for routing on-demand. The literature on precomputation has traditionally focused on minimizing the storage and computational overhead of the precomputation process. In this paper, we instead study the ``quality'' of precomputed paths and attempt to answer the following question: given a source-destination node pair and a limited amount of storage (e.g., k routes), what paths should be materialized for good routing performance? Unlike an online algorithm, the routing options for a precomputation system is limited to its k materialized paths. The prior work has assumed a min-hop formulation appropriate for the online routing is equally valid in the precomputation setting. We argue that choosing the shortest path oblivious of link capacities increases network bottlenecks and is a poor offline strategy. We instead propose an efficient max-flow based algorithm called Mobiflow that aims to achieve a high routable flow for its precomputed paths. Our simulation results show that Mobiflow outperforms hop minimization algorithms such as K-shortest path (KSP) for several metrics such as number of requests rejected, the fraction of bandwidth routed and total flow captured in the precomputed paths. We also provide significantly better performance over offline variants of recently proposed maxflow-based online algorithms. Furthermore, Mobiflow is storage efficient and can preserve the route quality even if the paths are precomputed incrementally, making it extremely attractive to implement in practice.