Concave Switching in Single and Multihop networks

Neil Walton

    Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review


    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.
    Original languageEnglish
    Title of host publicationSIGMETRICS '14 The 2014 ACM international conference on Measurement and modeling of computer systems
    Pages 139-151
    Number of pages13
    ISBN (Electronic)9781450327893
    Publication statusPublished - 1 Jun 2014


    Dive into the research topics of 'Concave Switching in Single and Multihop networks'. Together they form a unique fingerprint.

    Cite this