Optimization and Systems Theory Seminar
This seminar is organized jointly by Optimization and Systems Theory,
Automatic Control and Communication Networks.

Monday, February 16 2009, 14.15, Room Himmelriket, Osquldas väg 10

Gianluca Antonio Rizzo, EPFL, Switzerland

Stability in networks of aggregate schedulers

Abstract:
Some among the most widespread applications of the Internet (real-time streaming multimedia applications) are based on packet exchanges that assume a very low packet delay. In order to offer some form of better service to this kind of traffic some architectural frameworks have been proposed, in which traffic sources obey some form of constraints on the maximum number of packets sent in every time interval, in which traffic is subdivided into classes, and where at any node all packets are served taking only into account the class to which they belong to.

For these networks an open issue is their stability, that is the possibility to derive finite bounds to packet delay and queue size at each node.

Existing results either imply very restricting assumptions on network settings (i.e. on topology, or packet size), or require an unacceptably low bound on maximum node load.

The focus of our research is on the derivation of good sufficient conditions for the stability of these networks, with very general assumptions on network settings. Using a deterministic approach based on the analysis of worst case behavior, we first elaborated a general method to derive sufficient conditions for stability. We show how, with a proper choice of the observed parameters of the network and with the use of network calculus results, for these parameters it is possible to derive some upper bounds, whose properties are associated to the stability of the network. Exploiting our method, we derive a generalization of the "RIN result" (a well known existing result, based on strong assumptions on the network) to heterogeneous settings and to leaky bucket constrained flows. Through some realistic examples, we show that the new sufficient conditions for stability in the generalized "RIN result"

allow networks to achieve a level of utilization which is far larger than the best existing result. Finally, by applying our general method to three different variable classes, we derive some new sufficient conditions for stability which can be tested in polynomial time, and which perform largely better than all the known results. We show how all the main existing results can be derived from our new sufficient conditions.

Calendar of seminars