We consider the problem of scheduling the transmission of packets in an input-queued switch. In order to achieve maximum throughput, scheduling algorithms usually employ the queue length as a parameter for determining the priority to serve a given queue. In this work, we propose a novel scheme to optimize the performance of a preexisting scheduler. Our main idea is to assist the scheduling decision, considering "messagesa^ rather than queue lengths. Such messages are obtained by running an iterative parallel algorithm, inspired by a rigorous belief-propagation approach. We demonstrate that belief-propagation-assisted scheduling is able to boost the performance of a given scheduler, reaching almost optimal throughput, even under critical traffic scenarios.

Belief-propagation assisted scheduling in input-queued switches

Pretti, M
2013

Abstract

We consider the problem of scheduling the transmission of packets in an input-queued switch. In order to achieve maximum throughput, scheduling algorithms usually employ the queue length as a parameter for determining the priority to serve a given queue. In this work, we propose a novel scheme to optimize the performance of a preexisting scheduler. Our main idea is to assist the scheduling decision, considering "messagesa^ rather than queue lengths. Such messages are obtained by running an iterative parallel algorithm, inspired by a rigorous belief-propagation approach. We demonstrate that belief-propagation-assisted scheduling is able to boost the performance of a given scheduler, reaching almost optimal throughput, even under critical traffic scenarios.
2013
Istituto dei Sistemi Complessi - ISC
Belief propagation; Input-queued switches; Maximum weight matching problem; Router architectures; Scheduling
File in questo prodotto:
File Dimensione Formato  
prod_198429-doc_99503.pdf

solo utenti autorizzati

Descrizione: Belief-propagation assisted scheduling in input-queued switches
Tipologia: Versione Editoriale (PDF)
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 521.64 kB
Formato Adobe PDF
521.64 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.14243/20782
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 2
social impact