Auction-type framework for selling inter-domain paths

In the present Internet, inter-domain routing is based on BGP-4 [1] which selects a single path per destination prefix, thereby preventing carriers and end-users to use the vast inherent path diversity [2]. Addition of multi-path capabilities to the Internet have long been advocated for both robustness and traffic engineering purposes. Some works [3], [4] propose inter-domain multipath architectures. In this paper we consider a new service where carriers offer additional routes to their customers (w.r.t. to BGP default route) as an added-value service. These alternate routes can be used by customers to help them to meet their traffic engineering objectives (better delays etc.) or just for robustness purposes (disjoint alternate routes). Announcing additional paths can lead to scalability issues [5], so one carrier will propagate only the paths that are most interesting for neighboring domains. We propose an auction-like framework adapted to this specific service, allowing one carrier to select the most interesting paths and determine the prices at which these routes can be sold. We consider the case where routes are sold as infinitely duplicable goods (assuming small demands with regards to route capacities). We design a winner determination mechanism, based on the maximization of the seller's revenue, that enforces fair allocation of goods and is loser collusion proof. We also propose a payment mechanism that is proven to be truthful when each bidder submits one (potentially combinatorial) bid.