Proportional Switching in First-in, First-out Networks

Maury Bramson (), Bernardo D’Auria () and Neil Walton ()
Additional contact information
Maury Bramson: School of Mathematics, University of Minnesota, Minneapolis, Minnesota 55455
Bernardo D’Auria: Departmento de Estadística, Universidad Carlos III de Madrid, 28903 Getafe, Madrid, Spain; UC3M-BS Institute of Financial Big Data, Calle Madrid 135, 28903 Getafe, Madrid, Spain
Neil Walton: Alan Turing Building, University of Manchester, Manchester M13 9PL, United Kingdom

Operations Research, 2017, vol. 65, issue 2, 496-513

Abstract: We consider a family of discrete time multihop switched queueing networks where each packet moves along a fixed route. In this setting, BackPressure is the canonical choice of scheduling policy; this policy has the virtues of possessing a maximal stability region and not requiring explicit knowledge of traffic arrival rates. BackPressure has certain structural weaknesses because implementation requires information about each route, and queueing delays can grow super-linearly with route length. For large networks, where packets over many routes are processed by a queue, or where packets over a route are processed by many queues, these limitations can be prohibitive. In this article, we introduce a scheduling policy for first-in, first-out networks, the ProportionalScheduler, which is based on the proportional fairness criterion. We show that, like BackPressure, the ProportionalScheduler has a maximal stability region and does not require explicit knowledge of traffic arrival rates. The ProportionalScheduler has the advantage that information about the network’s route structure is not required for scheduling, which substantially improves the policy’s performance for large networks. For instance, packets can be routed with only next-hop information and new nodes can be added to the network with only knowledge of the scheduling constraints.

Keywords: ProportionalScheduler; BackPressure; Kelly networks; bandwidth sharing networks; Massoulié networks; switch networks; proportional fairness (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1287/opre.2016.1565 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:65:y:2017:i:2:p:496-513

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().