In this paper, we investigate the worst case performance of Earliest Due Date algorithm when applied to packet scheduling in distributed systems. We assume that the processing elements communicate via a multistage interconnection network, and that the system is synchronous. When two Or more packets are simultaneously sent over the same input port, or received through the same output port, the packets undergo a collision and are damaged, needing to be retransmitted later. This causes a performance degradation in terms of both throughput and delay. So, collisions must be avoided. The special type of traffic to be scheduled by Earliest Due Dare is a periodic hard-real time one, and the objective is to schedule all the packets within their individual due dates. We establish that EDD is always able to produce a schedule meeting this objective, whenever the so called link utilization is no more than 1/2, showing that this Horst case performance bound is tight. Such a bound can be effectively used as a feasibility test before actually running the algorithm.

EDD Algorithm Performance Guarantee for Periodic Hard-Real-Time Scheduling in Distributed Systems

BONUCCELLI, MAURIZIO ANGELO;
1999-01-01

Abstract

In this paper, we investigate the worst case performance of Earliest Due Date algorithm when applied to packet scheduling in distributed systems. We assume that the processing elements communicate via a multistage interconnection network, and that the system is synchronous. When two Or more packets are simultaneously sent over the same input port, or received through the same output port, the packets undergo a collision and are damaged, needing to be retransmitted later. This causes a performance degradation in terms of both throughput and delay. So, collisions must be avoided. The special type of traffic to be scheduled by Earliest Due Dare is a periodic hard-real time one, and the objective is to schedule all the packets within their individual due dates. We establish that EDD is always able to produce a schedule meeting this objective, whenever the so called link utilization is no more than 1/2, showing that this Horst case performance bound is tight. Such a bound can be effectively used as a feasibility test before actually running the algorithm.
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/168340
 Attenzione

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

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