We develop a general methodology, mainly based upon Lyapunov functions, to derive bounds on average delays, and on queue size averages and variances of complex systems of queues. We then apply this methodology to input-buffered, cell-based switch and router architectures. These architectures require a scheduling algorithm to select at each slot a subset of input-buffered cells which can be transferred towards output ports. Although the stability properties (i.e., the limit throughput) of input-buffered, cell-based switches was already studied for several classes of scheduling algorithms, no analytical results concerning cell delays or queue sizes are yet available in the technical literature. We concentrate on purely input-buffered switches that adopt a maximum weight matching scheduling algorithm, that was proved to be the scheduling algorithm providing the best performance. The derived bounds proved to be rather tight, when compared to simulation results.

Bounds on average delays and queue size averages and variances in input-queued cell-based switches / Leonardi, Emilio; Mellia, Marco; Neri, Fabio; AJMONE MARSAN, Marco Giuseppe. - 2:(2001), pp. 1095-1103. ((Intervento presentato al convegno INFOCOM 2001, 20th Annual Joint Conference of the IEEE Computer and Communications Societies tenutosi a Anchorage, AK (USA) nel April 22-26, 2001 [10.1109/INFCOM.2001.916303].

Bounds on average delays and queue size averages and variances in input-queued cell-based switches

LEONARDI, Emilio;MELLIA, Marco;NERI, Fabio;AJMONE MARSAN, Marco Giuseppe
2001

Abstract

We develop a general methodology, mainly based upon Lyapunov functions, to derive bounds on average delays, and on queue size averages and variances of complex systems of queues. We then apply this methodology to input-buffered, cell-based switch and router architectures. These architectures require a scheduling algorithm to select at each slot a subset of input-buffered cells which can be transferred towards output ports. Although the stability properties (i.e., the limit throughput) of input-buffered, cell-based switches was already studied for several classes of scheduling algorithms, no analytical results concerning cell delays or queue sizes are yet available in the technical literature. We concentrate on purely input-buffered switches that adopt a maximum weight matching scheduling algorithm, that was proved to be the scheduling algorithm providing the best performance. The derived bounds proved to be rather tight, when compared to simulation results.
File in questo prodotto:
File Dimensione Formato  
1413415.pdf

non disponibili

Tipologia: 2. Post-print / Author's Accepted Manuscript
Licenza: Non Pubblico - Accesso privato/ristretto
Dimensione 225.96 kB
Formato Adobe PDF
225.96 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

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: http://hdl.handle.net/11583/1413415
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo