Deterministic Delay Bounds for VBR Video in Packet-Switching 
            Networks: Fundamental Limits and Practical Tradeoffs


	                      D. Wrege
	     Department of Computer Science, U. of Virginia

	                     E. Knightly
		    EECS Department, UC Berkeley
		 
	                      H. Zhang
		      Carnegie Mellon University

	                    J. Liebeherr
	     Department of Computer Science, U. of Virginia



Compressed digital video is one of the most important traffic types in
future integrated services networks.  However, a network service that
supports delay-sensitive video imposes many problems since compressed
video sources are variable bit rate (VBR) with a high degree of
burstiness.  In this paper, we consider a network service that can
provide deterministic guarantees on the minimum throughput and the
maximum delay of VBR video traffic.  A common belief is that due to the
burstiness of VBR traffic, such a service will not be efficient and
will necessarily result in low network utilization.  We investigate the
fundamental limits and tradeoffs in providing deterministic performance
guarantees to video and use a set of 10 to 30 minute long
MPEG-compressed video traces for evaluation.  Contrary to conventional
wisdom, we are able to show that, in many cases, a deterministic
service can be provided to video traffic while maintaining a reasonable
level of network utilization.  We first consider an ideal network
environment that employs the most accurate deterministic,
time-invariant video traffic characterizations, the optimal
Earliest-Deadline-First packet schedulers, and exact admission control
conditions.  The utilization achievable in this situation provides the
fundamental limits of a deterministic service.  We then investigate the
utilization limits in a network environment that takes into account
practical constraints, such as the need for simple and efficient
policing mechanisms, packet scheduling algorithms, and admission
control tests.