- Author
- Year
- 2014
- Title
- Concave switching in single and multihop networks
- Event
- ACM SIGMETRICS 2014 (Austin, Texas, USA)
- Book/source title
- SIGMETRICS '14: proceedings of the 2014 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems: June 16-20, 2014, Austin, Texas, USA
- Pages (from-to)
- 139-151
- Publisher
- New York: Association for Computing Machinery
- ISBN
- 9781450327893
- Document type
- Conference contribution
- Faculty
- Faculty of Science (FNWI)
- Institute
- Korteweg-de Vries Institute for Mathematics (KdVI)
- Abstract
-
Switched queueing networks model wireless networks, input queued switches and numerous other networked communications systems. For single-hop networks, we consider a (α,g)-switch policy} which combines the MaxWeight policies with bandwidth sharing networks -- a further well studied model of Internet congestion. We prove the maximum stability property for this class of randomized policies. Thus these policies have the same first order behavior as the MaxWeight policies. However, for multihop networks some of these generalized polices address a number of critical weakness of the MaxWeight/BackPressure policies.
For multihop networks with fixed routing, we consider the Proportional Scheduler (or (1,log)-policy). In this setting, the BackPressure policy is maximum stable, but must maintain a queue for every route-destination, which typically grows rapidly with a network's size. However, this proportionally fair policy only needs to maintain a queue for each outgoing link, which is typically bounded in number. As is common with Internet routing, by maintaining per-link queueing each node only needs to know the next hop for each packet and not its entire route. Further, in contrast to BackPressure, the Proportional Scheduler does not compare downstream queue lengths to determine weights, only local link information is required. This leads to greater potential for decomposed implementations of the policy. Through a reduction argument and an entropy argument, we demonstrate that, whilst maintaining substantially less queueing overhead, the Proportional Scheduler achieves maximum throughput stability.
- URL
- go to publisher's site
- Language
- English
- Permalink
- http://hdl.handle.net/11245/1.440934
Disclaimer/Complaints regulations
If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let the Library know, stating your reasons. In case of a legitimate complaint, the Library will make the material inaccessible and/or remove it from the website. Please Ask the Library, or send a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam, The Netherlands. You will be contacted as soon as possible.