Date:     Oct. 1, 3:30 pm in 3355 Engr. Hall

Title:    Worst Case and Probabilistic Analysis of Integrated Services Networks

Speaker:  Rajeev Agrawal, ECE Department

Abstract:

We consider a network model in which the basic queueing elements are
regulators and schedulers. Regulators reshape the arrival process to a
burstiness constraint, while schedulers ensure a certain level of service
to individual flows (through some scheduling mechanism).  We introduce a
unified queueing model for these elements that may be viewed as a linear
system with a time-varying impulse response in the (min,+) algebra.  We
then consider fork-join networks of such elements that allow us to model
end-to-end or hop-by-hop window flow control mechanisms as well as both
unicast and multicast session topologies.  These networks may be viewed
as parallel, series, and feedback interconnections in the (min,+) algebra.

We obtain a number of pathwise, worst case, and probabilistic results for
this queueing model. We show how the departure processes from such networks
may be explicitly obtained in terms of the exogenous arrival and service
processes. We obtain worst case bounds on the queue lengths, delay and
burstiness of departure processes. We use these bounds to show how regulation
may be used inside the network to reduce buffering requirements without
affecting the worst case delay. When the arrival and service processes are
stationary ergodic we obtain the throughputs in terms of the arrival and
service rates, and we also obtain necessary and sufficient conditions
for the stability of the system.

These results may be used to investigate the support of different types
of service classes for integrated services networks. In particular, we may
consider three distinct classes. The first and second provide worst case
and probabilistic guarantees, respectively, on the loss and delay received
in return for imposing constraints on the traffic.  The third provides no
guarantees but uses feedback flow control to ensure that the traffic utilizes
the available bandwidth without causing congestion. Hybrid service categories
that combine these may also be designed. These service classes may be viewed
as ways of realizing the guaranteed, controlled load, and best effort service
categories defined by the integrated services working group of the Internet
Engineering Task Force.
 
(This is joint work with Francois Baccelli and Rajendran Rajan)