Prioritized Selfish Routing
Date Issued
2008
Date
2008
Author(s)
Lin, Shih-Peng
Abstract
In this work, we introduce and study a prioritized model of selfish routing. In the original model, there is a network in which the latency experienced by the users in the network on an edge is a function of the edge congestion, and each user will route itself on a minimum latency path without coordination. It is well known that the outcome of the selfish routing does not optimize the system performance. However, the performance can be improved by prioritizing the users. That is, some users are given high priority, and the remaining are given low priority. While the high users are traveling through the network, they will not be inflenced by the low priority ones. But when the low priority users are routing, they will be effected by both kinds of users.e show that such a prioritized model performs better than the nonprioritized one. While comparing to the optimal solution, we show that the performance of the prioritized model will not be worse. We also study the maximum possible benefit achievable by the prioritized model, which is 1/4 times the nonprioritized one in networks with linear latency functions, and could be arbitrarily small in the general case. The latter results show the coincidence between the best achievable performance of the prioritized model and the optimal solution in the original model.
Subjects
selfish routing
Nash equilibrium
algorithmic game theory
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-97-R94922145-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):23587279e4fb9b76479df44cb8caea4b