FLOW THEORY

We develop a simple theory of flows to study the flow of data in real- time computing networks. Flow Theory is based on discrete and nondeter ministic mathematics, rather than the customary continuous or probabil istic mathematics. The theory features two types of flows: smooth and uniform, and eight types of flow operators. We prove that, if the inpu t flow to any of these operators is smooth or uniform, then both the i nternal buffer and delay of that operator are bounded. Linear networks of flow operators are introduced, and their internal buffers and dela ys are derived from the internal buffers and delays of their constitue nt operators. We extend Flow Theory so that it can be used in analyzin g cyclic networks and networks of multiflows. Since many rate-reservat ion protocols can be represented as linear networks of flow operators, we use Flow Theory to prove that a number of these protocols (Stop-an d-Go, Hierarchical Round-Robin, Weighted Fair Queueing, Self-Clocking Fair Queueing, and Virtual Clock) require bounded buffering and introd uce bounded delay.