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
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;
Conference_Titel :
INFOCOM, 2011 Proceedings IEEE
Conference_Location :
Shanghai
Print_ISBN :
978-1-4244-9919-9
DOI :
10.1109/INFCOM.2011.5935098