
We consider the problem of selfish routing in a congested data network, such as the Internet. While previous analyses have discussed the possibility of large losses due to selfish routing, we present several reasons why one could expect typical losses to be small. The first is based on a "generic analysis" where we consider worst case topologies and latency functions, but ignore a small set of "transmission demands." We show that one can bound these "generic losses" by the log of the network's "criticality factor," a reasonable parameter. Our second reason is based on the near universal use of TCP or some other congestion control mechanism in networks. We show that for a specific model of TCP, the losses due to selfish routing are quite small and suggest that this is true in general. Both of these results are also shown to hold for the (nonlinear) latency functions which commonly arise on the Internet. Lastly, we provide some non-game-theoretic justifications for this analysis, which may be applicable to current networks, in which routing is not selfish. We show that in certain cases, common routing algorithms generate the same routes as selfish routing.
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 14 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
