Exact Admission Control in Networks with Bounded Delay Services.pdf

Exact Admission Control for Networks with Bounded Delay Services  Jorg Liebeherr y Dallas E. Wrege y Domenico Ferrari yy yDepartment of Computer Science University of Virginia Charlottesville, VA 22903 yyUniversity of California at Berkeley and International Computer Science Institute 1947 Center St., Suite 600 Berkeley, CA 94704-1105 Abstract To support the requirements for the transmission of continuous media, such as audio and video, multiservice packet switching networks must provide service guarantees to connections, including guarantees on throughput, network delays, and network delay variations. For the most demanding applications, the network must oer a service which can provide deterministic guarantees for the maximum delay of packets from all connections, referred to as bounded delay service. The admission control functions in a network with a bounded delay service must have available schedulability conditions that detect violations of delay guarantees in a network switch. In this study, exact schedulability conditions are presented for packet switches which transmit packets based on an Earliest-Deadline-First (EDF) or a Static-Priority (SP) algorithm. The schedulability conditions are given in terms of a general trac model, making the conditions applicable to a large class of trac specications. A comparison of the new schedulability conditions with existing, less accurate, conditions show the eciency gain obtained by using exact conditions. Examples are presented that show how the selection of a particular trac specication and a schedulability condition impact the eciency of a bounded delay service. Key Words: Multiservice Networks, Real-time Networks, Bounded Delay Service, Multiplexing, Quality of Service, Packet Scheduling, Admission Control, Static-Priority, Earliest-Deadline-First. This work is supported in part by the National Science Foundation under Grant No. NCR-9309224. 1 Introduction Recent technology trends have dramatically advance