Network bandwidth allocation via distributed auctions with time reservations

Abstract

This paper studies the problem of allocating network capacity through periodic auctions. Motivated primarily by a service overlay architecture, we impose the following conditions: fully distributed solutions over an arbitrary network topology, and the requirement that resources allocated in a given auction are reserved for the entire duration of the connection, not subject to future contention. Under these conditions, we study the problem of selling capacity to optimize revenue for the operator. 

We first study optimal revenue for a single distributed auction in a general network, writing it as an integer program and studying its convex relaxation. Next, the periodic auctions case is considered for a single link, modeling the optimal revenue problem as a Markov Decision Process (MDP); we develop a sequence of receding horizon approximations to its solution. Combining the two approaches we formulate a receding horizon optimization of revenue over a general network topology, leading to a convex program that yields a distributed implementation.  The proposal is demonstrated through simulations.