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

Authors:
Publisher website
Google Scholar
Abstract
In this paper, 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 VirtualClock 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 optima1 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. Abstract--In this paper, 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 @icy (SCED), is a generalized policy to which well-known policies such as VirtualClock 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.

This publication has 23 references indexed in Scilit: