Techreport,
Stability and Delay Bounds in Heterogeneous Networks of Aggregate Schedulers
(2007)
Abstract
Aggregate scheduling is one of the most promising
solutions to the issue of scalability in networks, like
DiffServ networks and high speed switches, where hard QoS
guarantees are required. For networks of FIFO aggregate
schedulers, the main existing sufficient conditions for
stability (the possibility to derive bounds to delay and
backlog at each node) are of little practical utility, as
they are either relative to specific topologies, or based
on strong ATM-like assumptions on the network (the
so-called ?RIN? result), or they imply an extremely low
node utilization. We use a deterministic approach to this
problem. We identify a non linear operator on a vector
space of finite (but large) dimension, and we derive a
first sufficient condition for stability, based on the
super-additive closure of this operator. Second, we use
different upper bounds of this operator to obtain
practical results. We find new sufficient conditions for
stability, valid in an heterogeneous environment and
without any of the restrictions of existing results. We
present a polynomial time algorithm to test our
sufficient conditions for stability. We show that with
leaky-bucket constrained flows, the inner bound to the
stability region derived with our algorithm is always
larger than the one determined by all existing results.
We prove that all the main existing results can be
derived as special cases of our results. We also present
a method to compute delay bounds in practical cases.
