Auctioning for Bandwidth in Communication Networks

by Bruno Tuffin and Patrick Maillé

Pricing has become a topic of great interest in the networking community. Among the different pricing schemes, auctioning for bandwidth seems a relevant possibility. Researchers from INRIA and GET/ENST Bretagne, all members of the ARMOR project-team are looking at pricing telecommunication networks; game theory is the main tool of the auctioning scheme they are developing.

The Internet is experiencing a steady increase in traffic due both to the growing number of subscribers and to applications becoming more and more demanding in terms of bandwidth. An increase in network capacity is not always a viable solution, since the expansion has to be predicted, and because of the potential cost (especially at the access networks) if not the difficulty (eg for radio access). It will also be necessary to have service differentiation, as the Internet deals with applications having very different quality of service (QoS) requirements. For instance, telephony tolerates few losses but no delay, whereas the opposite is true for e-mail. Finally, the current flat-rate pricing scheme that has been adopted by most countries is unfair, since big users pay as much as small ones.

To cope with these problems, usage-based and/or congestion-based pricing schemes have been designed. Non-cooperative game theory is a major tool in representing the selfish behaviour of Internet users, who try to maximise their own utilisation at the expense of the community as a whole. By associating a pricing scheme with the architecture to be developed, the designer can provide incentives to encourage fair use of the network and to optimise the service provider's revenue or the social welfare. On the other hand, designers need to be aware of the trade-off between engineering efficiency and economic efficiency. For example, traffic measurement helps in improving the management of a network but is a costly option.

Auctioning is a possible solution to differentiating services among users. The authors have developed a so-called multi-bid auction scheme that can be seen as an extension of the progressive second-price auction designed at Columbia University, with the advantage of reducing the signalling overhead since there is no need to send the bid-profile to all users anymore. Briefly, the scheme works as follows. Consider a single link of the network. When users start their applications, they submit a bid representing how much they would be willing to pay for a given amount of bandwidth. Thanks to this bidding process, the demand is known, the market-clearing price can be computed and bandwidth can be allocated. The total cost charged to each user/player follows the exclusion-compensation principle that lies behind all second-price mechanisms: each user/player pays for the loss of utility he imposes on other users. Important properties such as individual rationality (users pay no more than the amount they have bid for the allocated bandwidth), incentive compatibility (players should better reveal their true valuation of the bandwidth), and efficiency (in terms of benefits to the community), can be proved. Moreover, adjusting the number of bids that players can make allows the trade-off between complexity and efficiency to be controlled. The authors are currently working on extending this scheme to a whole network and to the case of inter-provider peering.

This research is a sub-activity of INRIA's ARMOR project-team at IRISA (Rennes, France), with five people from both INRIA and GET/ENST Bretagne involved in pricing issues, and the two authors dealing with auctioning. ARMOR is more generally interested in the identification, conception or selection of the most appropriate architectures for the implementation of communication services, as well as the development of mathematical tools to perform these tasks. The group is also coordinating an INRIA ARC (cooperative research action) called PRIXNET, focusing on pricing in collaboration with INRIA's MAESTRO project-team, the University of Versailles-St Quentin, France Telecom and IBM.

Links:
http://www.irisa.fr/armor/
http://www.irisa.fr/armor/lesmembres/Tuffin/proposition_pricing.html
http://www.irisa.fr/armor/Armor-Ext/RA/prixnet/ARC.htm

Please Contact:
Bruno Tuffin, INRIA
Tel: +33 2 99 84 74 94
E-mail: Bruno.Tuffinirisa.fr