SCED: a generalized scheduling policy for guaranteeing quality-of-service

Abstract

We introduce a new scheduling policy which provides guaranteed service for a session based on a flexible service specification called the service curve. This policy, referred to as the service curve based earliest deadline first policy (SCED), is a generalized policy to which well-known policies such as virtual clock and the earliest deadline first (EDF) can be mapped as special cases, by appropriate specification of the service curves. Rather than characterizing service by a single number, such as minimum bandwidth or maximum delay, service curves provide a wide spectrum of service characterization by specifying the service using a function. The flexibility in service specification allows a user, or the network, to specify a service that best matches the quality-of-service required by the user, preventing an over-allocation of network resources to the user. For a single server, we show that the SCED policy is optimal in the sense of supporting the largest possible schedulability region, given a set of delay-bound requirements and traffic burstiness specifications. For the case of a network of servers, we show that the SCED policy has a greater capability to support end-to-end delay-bound requirements than other known scheduling policies. The key to this capability is the ability of SCED to allocate and guarantee service curves with arbitrary shapes.