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