In this paper, we study the problem of on demand minimum length packet scheduling in single-hop multichannel systems. Examples of these systems are those centered around switching networks, like crossbar switches, and WDM optical fiber networks. On demand scheduling require that packets are scheduled upon receipt, and without changing the schedule of earlier packets. On demand scheduling is performed by on-line algorithms. In this paper we show that a large group of on-line scheduling algorithms, called maximal algorithms, are asymptotically optimal (in the worst case sense). This result is established by first giving the competitive ratio of these algorithms (nearly 3), and then by showing that no on-line algorithm can (asymptotically) perform better in the worst case. Then, we run a simulation experiment on randomly generated problem instances, whose outcome indicates an average increase of the schedule length of maximal algorithms, of 5% with respect to the lower bound.

Optimal On Demand Packet Scheduling in Single Hop Multichannel Communication Systems

BONUCCELLI, MAURIZIO ANGELO;PELAGATTI, SUSANNA
2000

Abstract

In this paper, we study the problem of on demand minimum length packet scheduling in single-hop multichannel systems. Examples of these systems are those centered around switching networks, like crossbar switches, and WDM optical fiber networks. On demand scheduling require that packets are scheduled upon receipt, and without changing the schedule of earlier packets. On demand scheduling is performed by on-line algorithms. In this paper we show that a large group of on-line scheduling algorithms, called maximal algorithms, are asymptotically optimal (in the worst case sense). This result is established by first giving the competitive ratio of these algorithms (nearly 3), and then by showing that no on-line algorithm can (asymptotically) perform better in the worst case. Then, we run a simulation experiment on randomly generated problem instances, whose outcome indicates an average increase of the schedule length of maximal algorithms, of 5% with respect to the lower bound.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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/11568/203348
 Attenzione

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

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
social impact