Realization of earliest-due-date scheduling discipline for ATM switches

Abstract

Asynchronous Transfer Mode (ATM) networks are expected to support a diverse mix of traffic sources requiring different Quality Of Service (QOS) guarantees. This paper initially examines several existing scheduling disciplines which offer delay guarantees in ATM switches. Among them, the Earliest-Due-Date (EDD) discipline has been regarded as one of the most promising scheduling disciplines. The EDD discipline schedules the departure of a cell belonging to a call based on the delay priority assigned for that call during the call set-up. Supporting n delay-based service classes through the use of n respective urgency numbers D-0 to Dn-1 (D-0 less than or equal to D-1 less than or equal to...less than or equal to Dn-1), EDD allows a class-i cell to precede any class-j (j>i) cell arriving not prior to (D-j - D-i)-slot time. The main goal of the paper is to determine the urgency numbers (D-i's), based on an in-depth queueing analysis, in an attempt to offer ninety-nine percentile delay guarantees for higher priority calls under various traffic loads. In the analysis, we derive system-time distributions for both high-and low-priority cells based on a discrete-time, single-server queueing model assuming renewal and non-renewal arrival processes. The validity of the analysis is justified via simulation. With the urgency numbers (D-i's) determined, we further propose a feasible efficient VLSI implementation architecture for the EDD scheduling discipline, furnishing the realization of QOS guarantees in ATM switches.