Generalization of the RIN result to heterogeneous networks of aggregate schedulers and leaky bucket constrained flows

We consider networks of FIFO aggregate schedulers. Quite surprisingly, the natural condition (node utilization inferior to one) in general is not sufficient in these networks to ensure stability (boundedness of delay and backlog at each node). Deriving good sufficient conditions for stability and delay bounds for these networks is of fundamental importance if we want to offer quality of service guarantees in such networks as Diffserv networks, high speed switches and network-on-chips. The main existing sufficient conditions for stability in these networks are the "DiffServ bound" [1] and the Route Interference Number (RIN) result [2]. We use an algebraic approach. First, we develop a model of the network as a dynamical system, and we show how the problem can be reduced to properties of the state transition function. Second, we obtain new sufficient conditions for stability valid without any of the restrictions of the "RIN result". We show that in practical cases, when flows are leaky bucket constrained, the new sufficient conditions perform better than existing results. We also prove that the "RIN result" can be derived as a special case from our approach. We finally derive an expression for a bound to delay at all nodes.


Published in:
2007 15Th Ieee International Conference On Networks, 419-424
Presented at:
15th IEEE International Conference on Networks, Adelaide, AUSTRALIA, Nov 19-21, 2007
Year:
2007
Publisher:
Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa
ISBN:
978-1-4244-1229-7
Keywords:
Laboratories:




 Record created 2012-07-04, last modified 2018-09-13

n/a:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)