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

In this paper, we introduce a new scheduling policy which provides guarante ed service for a session based on a flexible service specification called t he Service Curve. This policy, referred to as the Service Curve based Earli est Deadline first policy (SCED), is a generalized policy to which well-kno wn policies such as VirtualClock and the Earliest Deadline First (EDF) can be mapped as special cases, by appropriate specification of the service cur ves. Rather than characterizing service by a single number, such as minimum bandwidth or maximum delay, service curves provide a wide spectrum of serv ice characterization by specifying the service using a function. The flexib ility in service specification allows a user, or the network, to specify a service that best matches the quality-of-service required by the user, prev enting an over-allocation of network resources to the user. For a single se rver, we show that the SCED policy is optimal in the sense of supporting th e largest possible schedulability region, given a set of delay-bound requir ements and traffic burstiness specifications, For the case of a network of servers. we show that the SCED policy has a greater capability to support e nd-to-end delay-bound requirements than other known scheduling policies. Th e key to this capability is the ability of SCED to allocate and guarantee s ervice curves with arbitrary shapes.