Abstract: We propose a new scheduling policy, called SCED (service curve-based earliest deadline first), which provides guarantees to virtual circuits in packet-switched networks. This scheduling policy is developed for a general framework for service provisioning based on service curves proposed by Cruz (1992). Instead of explicitly guaranteeing a specific quality of service measure, such as maximum delay, SCED guarantees the service curve for a connection. Quality of service guarantees for the connection can then be expressed as simple functions of the service curve guarantee and the traffic burstiness constraint of the connection. A simple and convenient condition under which SCED can simultaneously guarantee a set of service curves is proved. The service curve specification gives greater flexibility to a server in allocating its resources to meet diverse delay and throughput requirements. We demonstrate by an example that SCED provides a larger schedulability region than scheduling policies such as virtual-clock and PGPS with rate proportional assignment.