DocumentCode :
1943253
Title :
A packet dropping-based incentive mechanism for M/M/1 queues with selfish users
Author :
Gai, Yi ; Liu, Hua ; Krishnamachari, Bhaskar
Author_Institution :
Dept. of Electr. Eng., Univ. of Southern California, Los Angeles, CA, USA
fYear :
2011
fDate :
10-15 April 2011
Firstpage :
2687
Lastpage :
2695
Abstract :
We study a novel game theoretic incentive mechanism design problem for network congestion control in the context of selfish users sending data through a single store-and-forward router (a.k.a. “server” in this work). The scenario is modeled as an M/M/1 queueing game with each user (a.k.a. “player”) aiming to optimize a tradeoff between throughput and delay in a selfish distributed manner. We first show that the original game has an inefficient unique Nash Equilibrium (NE). In order to improve the outcome efficiency, we propose an incentivizing packet dropping scheme that can be easily implemented at the server. We then show that if the packet dropping scheme is a function of the sum of arrival rates, we have a modified M/M/1 queueing game that is an ordinal potential game with a unique NE. In particular, for a linear packet dropping scheme, which is similar to the Random Early Detection (RED) algorithm used with TCP, we show that there exists a unique Nash Equilibrium. For this scheme, the social welfare (expressed either as the summation of utilities of all players or log summation of utilities of all players) at the equilibrium point can be arbitrarily close to the social welfare at the global optimal point. Finally, we show that the simple best response dynamic converges to this unique efficient Nash Equilibrium.
Keywords :
game theory; incentive schemes; network servers; queueing theory; telecommunication congestion control; M/M/1 queues; Nash equilibrium; TCP; equilibrium point; game theoretic incentive mechanism design; global optimal point; linear packet dropping scheme; network congestion control; packet dropping-based incentive mechanism; random early detection; selfish users; social welfare; store-and-forward router; sum of arrival rates; Context; Delay; Games; Nash equilibrium; Optimization; Servers; Throughput;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
INFOCOM, 2011 Proceedings IEEE
Conference_Location :
Shanghai
ISSN :
0743-166X
Print_ISBN :
978-1-4244-9919-9
Type :
conf
DOI :
10.1109/INFCOM.2011.5935098
Filename :
5935098
Link To Document :
بازگشت