Proportional switching in FIFO networks

Bramson, Maury; D'Auria, Bernardo; Walton, Neil

Publication:
Proportional switching in FIFO networks

dc.affiliation.dpto	UC3M. Departamento de Estadística	es
dc.contributor.author	Bramson, Maury
dc.contributor.author	D'Auria, Bernardo
dc.contributor.author	Walton, Neil
dc.contributor.other		es
dc.date.accessioned	2015-10-14T14:20:25Z
dc.date.available	2015-10-14T14:20:25Z
dc.date.issued	2015-09-01	es
dc.description.abstract	We consider a family of discrete time multihop switched queueing networks where each packet movesalong a xed route. In this setting, BackPressure is the canonical choice of scheduling policy; this policy hasthe virtues of possessing a maximal stability region and not requiring explicit knowledge of tra c 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 manyroutes are processed by a queue, or where packets over a route are processed by many queues, these limitationscan be prohibitive.In this article, we introduce a scheduling policy for FIFO networks, the Proportional Scheduler, which isbased on the proportional fairness criterion. We show that, like BackPressure, the Proportional Scheduler hasa maximal stability region and does not require explicit knowledge of tra c 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 routedwith only next-hop information and new nodes can be added to the network with only knowledge of thescheduling constraints	en
dc.description.sponsorship	The research of the rst author was partially supported by NSF grants DMS-1105668 and DMS-1203201. The research of the second author was partially supported by the Spanish Ministry of Economy and Competitiveness Grants MTM2013-42104-P via FEDER funds; he thanks the ICMAT (Madrid, Spain) Research Institute that kindly hosted him while developing this project.	en
dc.format.mimetype	application/pdf
dc.identifier.issn		es
dc.identifier.uri	https://hdl.handle.net/10016/21734
dc.identifier.uxxi	DT/0000001406
dc.language.iso	eng	en
dc.relation.projectID	Gobierno de España. MTM2013-42104-P	es
dc.rights	Atribución-NoComercial-SinDerivadas 3.0 España	*
dc.rights.uri	http://creativecommons.org/licenses/by-nc-nd/3.0/es/	*
dc.subject.other	Proportional Scheduler	en
dc.subject.other	BackPressure	en
dc.subject.other	Kelly networks	en
dc.subject.other	Bandwidth sharing networks	en
dc.subject.other	Massouli e networks	en
dc.subject.other	Switch networks	en
dc.subject.other	Proportional fairness	en
dc.title	Proportional switching in FIFO networks	en
dc.type	working paper	*
dspace.entity.type	Publication