University of AmsterdamUniversity of AmsterdamUvA

  • Terms of use
  • Contact

UvA-DARE (Digital Academic Repository)

  • Home
  • Advanced Search
  • Browse
  • My selection

Search UvA-DARE

Author
N. Walton
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.

PrintPrint this pageShareShare via emailShare on facebookShare on linkedinShare on twitter
  • University library
  • About UvA-DARE
  • Disclaimer
Copyright UvA 2014