Over-Provisioning and Atomic Selfish Routing
Lists
Only you see this
Abstract
Last lecture proved generic tight bounds on the price of anarchy (POA) of selfish routing, parameterized by the edge cost functions. One particular instantiation of these bounds gives a rigorous justification for the common strategy of over-provisioning a communication network to achieve good performance (Section 12.1). A different result in the same vein states that a modest technology upgrade improves network performance more than implementing dictatorial control (Sections 12.2-12.3). Applications in which network users control a non-negligible fraction of the traffic are best modeled via an “atomic” variant of selfish routing (Section 12.4). The POA of atomic selfish routing is larger than in the “nonatomic” model, but remains bounded provided the network cost functions are affine (Sections 12.4-12.5), or more generally “not too nonlinear.”
BibTeX
@inproceedings{roughgarden2016over,
author = {Tim Roughgarden},
title = {{Over-Provisioning and Atomic Selfish Routing}},
booktitle = {Cambridge},
year = {2016},
doi = {10.1017/cbo9781316779309.013},
}Loading related content...