Paper Info
Title
Combined Single-Path Routing And Flow Control In Many-User Region: A Case For Nash Efficiency
Abstract
We consider the problem of combined singlepath routing and flow control, which is nonconvex and NP-hard to solve exactly. We focus on the "many-user" region, i.e. large networks that have far more users than bottleneck links, which is close to real network scenarios. We first show that by allowing a proportionally small number of users to use multipath routing, while keeping the remaining majority using single-path routing, results in a solution that achieves multipath optimality. Therefore it is conceptually plausible that in the many-user region a local algorithm can achieve solutions arbitrarily close to the optimal solution. To show this is indeed correct, we focus on the solutions brought out by the simplest local algorithm, the Nash algorithm. We first examine a special type of network and show that the Nash equilibrium exists and the Nash algorithm always converges. It is then shown that the 'price of anarchy', that is the gap between the worst Nash equilibrium and the social optimum, is bounded when the number of users goes to infinity. For general networks, it is not known whether there exists a Nash equilibrium. We introduce the concept of approximate Nash equilibrium, show its existence, and prove that it will be arbitrary close to the social optimum when the number of users is sufficiently large.
Year
DOI
Venue
2007
10.1109/CDC.2007.4434551
PROCEEDINGS OF THE 46TH IEEE CONFERENCE ON DECISION AND CONTROL, VOLS 1-14
Keywords
Field
DocType
nash equilibrium,multipath routing,flow control
Multipath routing,Mathematical optimization,Link-state routing protocol,Path vector protocol,Computer science,Static routing,Destination-Sequenced Distance Vector routing,Routing domain,Price of anarchy,Nash equilibrium
Conference
ISSN
Citations 
PageRank 
0743-1546
0
0.34
References 
Authors
7
2
Name
Order
Citations
PageRank
Huigang Chen100.34
John S. Baras21953257.50