Auctions for resource allocation in overlay networks

Abstract. The paper studies the problem of allocating bandwidth re-sources of a Service Overlay Network, to optimize revenue. Clients bid for network capacity in periodically held auctions, under the condition that resources allocated in an auction are reserved for the entire duration of the connection, not subject to future contention. This makes the optimal allocation coupled over time, which we formulate as a Markov Decision Process (MDP). Studying first the single resource case, we develop a re-ceding horizon approximation to the optimal MDP policy, using current revenue and the expected revenue in the next step to make bandwidth assignments. A second approximation is then found, suitable for gener-alization to the network case, where bids for different routes compete for shared resources. In that case we develop a distributed implementation of the auction, and demonstrate its performance through simulations.