SCED+: efficient management of quality of service guarantees

Abstract

Proposals for the provision of deterministic quality of service guarantees in integrated services networks require per-session management of traffic flowing in network switches, raising scalability questions for practical implementation of high speed packet switching in large scale networks. At the same time, the end-to-end delay bounds associated with current proposals can be overly conservative, limiting the utility of the bounds to guide efficient resource allocation. In this paper, we introduce SCED+ (surface curve earliest deadline+), a network scheduling algorithm that yields scalable provision of tight deterministic end-to-end delay bounds. These features are achieved through the use of aggregation and efficient statistical multiplexing between best-effort and guaranteed traffic. The SCEDS+ algorithm also supports statistical multiplexing between "guaranteed" traffic streams, providing tight end-to-end delay bounds for traffic streams which can tolerate non-zero packet loss rates. In order to facilitate the analysis of SCED+, we refine the so-called "network calculus" to address delay jitter, and introduce a simple and unified approach to the analysis of output burstiness of traffic departing from a general network element.