Flow theory
- 1 October 1997
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking
- Vol. 5 (5), 661-674
- https://doi.org/10.1109/90.649567
Abstract
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 nondeterministic mathematics, rather than the customary continuous or probabilistic mathematics. The theory features two types of flows: smooth and uniform, and eight types of flow operators. We prove that, if the input flow to any of these operators is smooth or uniform, then both the internal buffer and delay of that operator are bounded. Linear networks of flow operators are introduced, and their internal buffers and delays are derived from the internal buffers and delays of their constituent operators. We extend flow theory so that it can be used in analyzing cyclic networks and networks of multiflows. Since many rate-reservation protocols can be represented as linear networks of flow operators, we use flow theory to prove that a number of these protocols (stop-and-go, hierarchical round-robin, weighted fair queueing, self-clocking fair queueing, and virtual clock) require bounded buffering and introduce bounded delay.Keywords
This publication has 15 references indexed in Scilit:
- Time-shift scheduling: fair scheduling of flows in high speed networksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- A self-clocked fair queueing scheme for broadband applicationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- A service oriented approach to continuous media synchronizationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Rate controlled servers for very high-speed networksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Delay guarantee of virtual clock serverIEEE/ACM Transactions on Networking, 1995
- An upper bound delay for the virtual-clock service disciplineIEEE/ACM Transactions on Networking, 1995
- Dispersity routing in high-speed networksComputer Networks and ISDN Systems, 1993
- A framing strategy for congestion managementIEEE Journal on Selected Areas in Communications, 1991
- A calculus for network delay. I. Network elements in isolationIEEE Transactions on Information Theory, 1991
- A Proof for the Queuing Formula: L = λWOperations Research, 1961