Networks with Deterministic Quality-of-Service Guarantees Jorg Liebeherr Department of Computer Science University of Virginia Charlottesville, VA 22903 Dallas E. Wrege IBM Corporation 3039 Cornwallis Road Research Triangle Park, NC 27709 Abstract A network that offers deterministic, i.e., worst-case, quality-of-service (QoS) guarantees to variable-bit-rate (VBR) video must provide a resource reservation mechanism that allocates bandwidth, buffer space, and other resources for each video stream. Such a resource reservation scheme must be carefully designed, otherwise network resources are wasted. A key component for the design of a resource reservation scheme is the {\m traffic characterization} method that specifies the traffic arrivals on a video stream. The traffic characterization should accurately describe the actual arrivals so that a large number of streams can be supported; but it must also map directly into efficient traffic policing mechanisms that monitor arrivals on each stream. In this study, we present a fast and accurate traffic characterization method for stored VBR video in networks with a deterministic service. We use this approximation to obtain a traffic characterization that can be efficiently policed by a small number of leaky buckets. We present a case study where we apply our characterization method to networks that employ a dynamic resource reservation scheme with renegotiation. We use traces from a set of~25-30 minute MPEG sequences to evaluate our method against other characterization schemes from the literature.