Network Calculus viewed as a Min-plus System Theory

We analyze some queueing problems arising in guaranteed service and controlled load networks using min-plus algebra. We find an explicit representation for the sub-additive closure of the minimum of two operators, and we introduce a new, useful family of idempotent, time-varying, and min-plus linear operators. We model queueing systems arising in networks networks as non-linear min-plus systems that can be bounded by linear systems, and apply our concepts to: the optimal shaper studied by Anantharam and Konstantopoulos, the window flow control problem previously studied by: Cruz and Okino, Chang, Agrawal and Rajan. In all these cases we explain the existing bounds and in the latter case derive another bound. We then show how the same method enables us to give a representation for the losses in a shaper with finite buffer constraints or with delay constraints. We apply the result to bound the losses in a variable bit rate (VBR) trunk system by the losses in simpler, constant bit rate trunk systems (CBR) systems. Finally, as a by-product of the concepts proposed in the paper, we show how it provides an explicit solution to the deterministic Skorokhod reflection mapping problem with two boundaries.