RouteBazaar: An Economic Framework for Flexible Routing

Abstract

The Internet?s routing protocol provides users a single end-to-end route that is not guaranteed to be available or to meet user requirements. Our paper addresses this rigidity using an economically grounded approach that appeals both to users and to service providers. We propose a framework called RouteBazaar in which service providers announce links connecting different parts of the Internet, along with dynamically changing prices associated with using the links. All topology information is exposed to end-users. Users simply use routes that best match their cost-performance requirements. The appeal to users is that they can always obtain a route of their choice as long as they are willing to pay for it. The appeal to providers is that our framework offers them means for monetary gains as long as they are willing to offer greater visibility into their topology and greater flexibility in user routes. We present both centralized and distributed versions of this framework. Both versions are designed to supplement, not supplant, BGP. We design a variety of algorithms to ensure robustness and stability of either framework. We study the framework using a simplified game-theoretic model and also conduct large scale simulations of its performance in practice using real and synthetic network topologies. We find that despite allowing flexibility to both users and service providers, our system operates at a stable and close-to-optimal state.