RED-VBR: A Renegotiation-Based Approach to
    		   Support Delay-Sensitive VBR Video

                              Hui Zhang
                      Carnegie Mellon University

                          Edward Knightly
                          EECS Department
                  University of California, Berkeley




Previous approaches to supporting video on packet-switched networks
include deterministic service, statistical service, predicted service,
and feedback-based schemes. These schemes represent different tradeoffs
in quality of service (QOS), achievable network utilization, and method
of dealing with overload.  In this paper, we propose a new service
called REnegotiated Deterministic Variable Bit Rate Service (RED-VBR)
that attempts to strike an efficient balance with the above tradeoffs.
The approach is based on deterministic guarantees with client
controlled renegotiation of traffic and QOS parameters and graceful
adaptation during overload periods.  We introduce a connection
admission control algorithm for RED-VBR which bounds the renegotiation
failure probability.  We evaluate the scheme using two traces of
MPEG-compressed video and show that, even with simple renegotiation
polices and relatively low renegotiation frequencies, high network
utilization in the range of 50% to 80% can be achieved. For traffic
that is bursty over long intervals, this represents a 100% to 150%
improvement in network utilization compared to deterministic service.
Compared to statistical and predicted service, our approach allows more
graceful and client-controlled QOS degradation during overload