S. Keshav
Skip Abstract Section
Abstract
This paper presents a control-theoretic approach to reactive flow control in networks that do not reserve bandwidth. We assume a round-robin-like queue service discipline in the output queues of the network's switches, and propose deterministic and stochastic models for a single conversation in a network of such switches. These models motivate the Packet-Pair rate probing technique, and a provably stable rate-based flow control scheme. A Kalman state estimator is derived from discrete-time state space analysis, but there are difficulties in using the estimator in practice. These difficulties are overcome by a novel estimation scheme based on fuzzy logic. We then present a technique to extract and use additional information from the system to develop a continuous-time system model. This is used to design a variant of the control law that is also provably stable, and, in addition, takes control action as rapidly as possible. Finally, practical issues such as correcting parameter drift and coordination with window flow control are described.
- 1. D. Ferrari, Client Requirements for Real-Time Communications Services, IEEE Communications Magazine 28, 11 (November 1990). Google Scholar
Digital Library
- 2. C.R. Kalmanek, H. Kanakia and S. Keshav, Rate Controlled Servers for Very High Speed Networks, Proc. Globecom 1990, December 1990, 300.3.1-300.3.9.Google ScholarCross Ref
- 3. D. Ferrari and D. Verma, A Scheme for Real-Time Channel Establishment in Wide-Area Networks, IEEE J. on Selected Areas in Communications, April 1990.Google ScholarDigital Library
- 4. S.J. Golestani, A Stop-and-Go Queueing Framework for Congestion Management, Proc. ACM SigComm 1990, September 1990, 8-18. Google ScholarDigital Library
- 5. L. Zhang, A New Architecture for Packet Switching Network Protocols, PhD thesis, Massachusetts Institute of Technology, July 1989.Google Scholar
- 6. S. Keshav, A. K. Agrawala and S. Singh, Design and Analysis of a Flow Control Algorithm for a Network of Rate Allocating Servers, in Protocols for High Speed Networks II, Elsevier Science Publishers/North-Holland, April 1991.Google Scholar
- 7. S. Singh, A. K. Agrawala and S. Keshav, Deterministic Analysis of Flow and Congestion Control Policies in Virtual Circuits, Tech. Rpt.-2490, University of Maryland, June 1990. Google ScholarDigital Library
- 8. S. Keshav, The Packet Pair Flow Control Protocol, Tech. Rpt. 91-028, International Comp. Sci. Institute, Berkeley, CA 94704, May 1991.Google Scholar
- 9. A. Greenberg and N. Madras, How Fair is Fair Queueing?, Proc. Performance 90, 1990.Google Scholar
- 10. A. Demers, S. Keshav and S. Shenker, Analysis and Simulation of a Fair Queueing Algorithm, Journal of Internetworking Research and Experience, September 1990, 3-26;. also Proc. ACM SigComm, Sept. 1989, pp. 1- 12. Google ScholarDigital Library
- 11. H. Zhang and S. Keshav, Comparison of Rate-Based Service Disciplines, Proc. ACM SigComm 1991, September 1991. also International Comp. Sci. Institute Tech. Rpt. 91-024, Berkeley, CA. Google ScholarDigital Library
- 12. S. Tripathi and A. Duda, Time-dependent Analysis of Queueing Systems, INFOR 24, 3 (1978), 334-346.Google Scholar
- 13. J.G. Waclawsky, Window Dynamics, PhD Thesis, University of Maryland, College Park, May 1990. Google ScholarDigital Library
- 14. J.G. Waclawsky and A. K. Agrawala, Dynamic Behavior of Data Flow within Virtual Circuits, Comp. Sci.-Tech. Rpt.-2250, University of Maryland, May 1989.Google Scholar
- 15. B.D.O. Anderson and J. B. Moore, Optimal Filtering, Prentice Hall, 1979.Google Scholar
- 16. K.K. Sabnani and A. N. Netravali, A High Speed Transport Protocol for Datagram/Virtual Circuit Networks, Proc. ACM SigComm 1989, September 1989, 146-157. Google ScholarDigital Library
- 17. B. D. O. Anderson and J. B. Moore, Linear Quadratic Methods, Prentice Hall, 1990. Google ScholarDigital Library
- 18. D. Mitra and J. B. Seery, Dynamic Adaptive Windows for High Speed Data Networks: Theory and Simulations, Proc. ACM SigComm 1990, September 1990, 30-40. Google ScholarDigital Library
- 19. D. Mitra, Asymptotically Optimal Design of Congestion Control for High Speed Data Networks, To Appear in IEEE Trans. on Communications, 1991.Google Scholar
- 20. S. Keshav, Congestion Control in Computer Networks, PhD thesis, University of California, Berkeley, August 1991. Google ScholarDigital Library
- 21. A.E. Ekberg, D. T. Luan and D. M. Lucantoni, Bandwidth Management: A Congestion Control Strategy for Broad-band Packet Networks: Characterizing the Throughput-Burstiness Filter, Proc. ITC Specialist Seminar, Adelaide, 1989, paper no. 4.4.Google Scholar
- 22. K. Ogata, Discrete Time Control Systems, Prentice Hall, 1987. Google ScholarDigital Library
- 23. G.C. Goodwin and K. S. Sin, Adaptive Filtering Prediction and Control, Prentice Hall, 1984.Google Scholar
- 24. H.J. Zimmerman, in Fuzzy Set Theory and its Applications, Kluwer Academic Publishers, 1985. Google ScholarDigital Library
- 25. L. A. Zadeh, Outline of a New Approach to the Analysis of Complex Systems and Decision Processes, IEEE Trans. on Systems, Man and Cybernetics, 1973, 28-44.Google Scholar
- 26. G. Langari, Analysis and Design of Fuzzy Control Systems, PhD thesis (in preparation), University of California, Berkeley, 1991.Google Scholar
- 27. L.A. Zadeh, Fuzzy Sets, Journal of Information and Control 8 (1965), 338-353.Google ScholarCross Ref
- 28. P.S. Khedkar and S. Keshav, Fuzzy Prediction of Time-series, Proc. IEEE Conference on Fuzzy Systems-92, March 1992.Google ScholarCross Ref
- 29. C. Agnew, Dynamic Modeling and Control of Congestion-prone Systems, Operations Research 24, 3 (1976), 400- 419.Google ScholarCross Ref
- 30. D. Tipper and M. K. Sundareshan, Numerical Methods for Modeling Computer Networks under Nonstationcal Condition, JSAC 8, 9 (December 1990).Google Scholar
- 31. J. Bolot, Dynamical Behavior of Rate-Based Flow Control Mechanisms, Comp. Sci.-Tech. Rpt. 2279.1, University of Maryland, October 1989.Google Scholar
- 32. R. Jain, Myths About Congestion Management in High-Speed Networks, Technical Report-726, Digital Equipment Corporation, October 1990.Google Scholar
- 33. E.L. Hahne, C. R. Kalmanek and S. P. Morgan, Fairness and Congestion Control on a Large ATM Data Network with Dynamically Adjustable Windows, 13th International Teletraffic Congress, Copenhagen, June 1991.Google Scholar
- 34. K. Bharath-Kumar and J. M. Jaffe, A New Approach to Performance-Oriented Flow Control, IEEE Trans. on Communication COM-29, 4 (April 1981), 427-435.Google Scholar
- 35. S. Shenker, A Theoretical Analysis of Feedback Flow Control, Proc. ACM SigComm 1990, September 1990, 156-165. Google ScholarDigital Library
- 36. C. Douligeris and R. Majumdar, User Optimal Flow Control in an Integrated Environment, Proc. of the Indo-US Workshop on Systems and Signals, January 1988. Bangalore, India.Google Scholar
- 37. A.D. Bovopoulos and A. A. Lazar, Asynchronous Algorithms for Optimal Flow Control of BCMP Networks, Tech. Rpt. WUCS-89-10, Washington University, St. Louis, MO, February 1989.Google Scholar
- 38. A.D. Bovopoulos and A. A. Lazar, Decentralized Algorithms for Optimal Flow Control, Proc. 25th Allerton Conference on Communications Control and Computing, October 1987. University of Illinois, Urbana-Champaign.Google Scholar
- 39. K.K. Ramakrishnan and R. Jain, Congestion avoidance in Computer Networks with a Connectionless Network Layer - Part II - An Explicit Binary Feedback Scheme, Technical Report-508, Digital Equipment Corporation, April 1987.Google Scholar
- 40. V. Jacobson, Congestion Avoidance and Control, Proc. ACM SigComm 1988, August 1988, 314-329. Google ScholarDigital Library
- 41. K. Ko, P. P. Mishra and S. K. Tripathi, Predictive Congestion Control in High-Speed Wide-Area Networks, in Protocols for High Speed Networks II, Elsevier Science Publishers/North-Holland, April 1991.Google Scholar
- 42. J. Filipiak, Modelling and Control of Dynamic Flows in Communication Networks, Springer-Verlag, 1988.Google Scholar
- 43. F. Vakil, M. Hsiao and A. A. Lazar, Flow Control in Integrated Local Area Networks, Vol. 7, 1987. Google ScholarDigital Library
- 44. F. Vakil and A. A. Lazar, Flow Control Protocols for Integrated Networks with Partially Observed Traffic, IEEE Transactions on Automatic Control 32, 1 (1987), 2-14.Google Scholar
- 45. T.G. Robertazzi and A. A. Lazar, On the Modeling and Optimal Flow Control of the Jacksonian Network, Performance Evaluation 5 (1985), 29-43.Google ScholarCross Ref
- 46. M. Hsiao and A. A. Lazar, Optimal Flow Control of Multi-Class Queueing Networks with Partial Information, IEEE Transactions on Automatic Control 35, 7 (July 1990), 855- 860.Google Scholar
- 47. K. K. Ramakrishnan and R. Jain, A Binary Feedback Scheme for Congestion Avoidance in Computer Networks, ACM ACM Trans. on Comp. Sys. 8, 2 (May 1990), 158- 181. Google ScholarDigital Library
- 48. L. Zhang, S. Shenker and D. D. Clark, Observations on the Dynamics of a Congestion Control Algorithm: The Effects of Two-Way Traffic, Proc. ACM SigComm 1991, September 1991. Google ScholarDigital Library
- 49. C. R. Kalmanek, Xunet 2: A Nationwide Testbed in High-Speed Networking, Comp. Sci. Tech. Rpt., March 1991, AT&T Bell Labs, 600 Mountain Ave. Murray Hill, NJ 07974.Google Scholar
Index Terms
- A control-theoretic approach to flow control
Recommendations
An Analysis of a Tandem Queueing System for Flow Control in Computer Networks
A tandem queueing system with constant slotted service times and threshold control is modeled and analyzed in this paper. The input to the first queue is controlled by the buffer occupancy of the second queue. When the second queue has more than No ...
Queueing properties of feedback flow control systems
In this paper, we consider a network with both controllable and uncontrollable flows. Uncontrollable flows are typically generated from applications with stringent QoS requirements and are given high priority. On the other hand, controllable flows are ...
Optimal control of parallel queues with impatient customers
Performance modelling and evaluation of high-performance parallel and distributed systemsWe consider a queueing system with a number of identical exponential servers. Each server has its own queue with unlimited capacity. The service discipline in each queue is first-come-first-served (FCFS). Customers arrive according to a state-dependent ...
Comments