A control-theoretic approach to flow control
Published 1 August 1991Open access
Srinivasan Keshav
Citations752
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A control-theoretic approach to reactive flow control in networks that do not reserve bandwidth is presented, and a technique to extract and use additional information from the system to develop a continuous-time system model is presented.
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 d~crete-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 horn the system to develop a continuous-time system model.This is used to design a wuisnt 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 cmmlination with window flow control are described.
Keywords
Computer ScienceEngineering
IEEE Transactions on Systems Man and CyberneticsOutline of a New Approach to the Analysis of Complex Systems and Decision Processes
8,667 Citations1973Lotfi A. Zadeh
By relying on the use of linguistic variables and fuzzy algorithms, the approach provides an approximate and yet effective means of describing the behavior of systems which are too complex or too ill-defined to admit of precise mathematical analysis.
ACM SIGCOMM Computer Communication ReviewCongestion avoidance and control
5,337 Citations1995Van Jacobson
The measurements and the reports of beta testers suggest that the final product is fairly good at dealing with congested conditions on the Internet, and an algorithm recently developed by Phil Karn of Bell Communications Research is described in a soon-to-be-published RFC.
Adaptive filtering prediction and control
3,364 Citations1984Graham C. Goodwin, Kwai Sin
This unified survey focuses on linear discrete-time systems and explores the natural extensions to nonlinear systems and summarizes the theoretical and practical aspects of a large class of adaptive algorithms.
Congestion avoidance and control
2,447 Citations1988Van Jacobson
In October of '86, the Internet had the first of what became a series of 'congestion collapses' during this period, the data throughput from LBL to UC Berkeley dropped from 32 Kbps to 40 bps.
Analysis and simulation of a fair queueing algorithm
1,725 Citations1989Alan Demers, Srinivasan Keshav +1 more
It is found that fair queueing provides several important advantages over the usual first-come-first-serve queueing algorithm: fair allocation of bandwidth, lower delay for sources using less than their full share of bandwidth and protection from ill-behaved sources.
IEEE Journal on Selected Areas in CommunicationsA scheme for real-time channel establishment in wide-area networks
1,037 Citations1990D. Ferrari, D.C. Verma
The results are judged encouraging: the approach satisfies the guarantees even in worst case situations, uses the network's resources to a fair extent, and efficiently handles channels with a variety of offered load and burstiness characteristics.
Observations on the dynamics of a congestion control algorithm
377 Citations1991Lixia Zhang, Scott Shenker +1 more
This paper uses simulation to study the dynamics of the congestion cent rol algorithm embedded in the BSD 4.3-Tahoe TCP implementation and finds that the one-way traffic clustering and loss-synchronization phenomena persist in this new situation, albeit in a slightly modified form.
ACM Transactions on Computer SystemsA binary feedback scheme for congestion avoidance in computer networks
367 Citations1990K. K. Ramakrishnan, Raj Jain
The scheme is distributed, adapts to the dynamic state of the network, converges to the optimal operating point, is quite simple to implement, and has low overhead.
IEEE Communications MagazineClient requirements for real-time communication services
358 Citations1990D. Ferrari
Rate controlled servers for very high-speed networks
324 Citations2002Charles Kalmanek, Hemant Kanakia +1 more
Two queue service disciplines, rate-based scheduling and hierarchical round robin scheduling, are described, designed for fast packet networks and suitable for use in networks based on the asynchronous transfer mode (ATM) being defined in CCITT.
Comparison of rate-based service disciplines
281 Citations1991Hui Zhang, Srinivasan Keshav
This paper compares six new queue service disciplines that can be implemented at the output queues of switches in a connection-oriented packet switched data network and shows why each discipline can or cannot provide bandwidth, delay and delay jitter guarantees.
A stop-and-go queueing framework for congestion management
200 Citations1990S. Jamaloddin Golestani
A framework for congestion management in integrated services packet networks based on a particular service discipline, called stop-and-go queueing, is proposed, providing the necessary flexibility in accommodating throughput and end-to-end delay requirements of different connections on an as-needed basis.
DSpace@MIT (Massachusetts Institute of Technology)A new architecture for packet switching network protocols
152 Citations1989Lixia Zhang
A new channel scheduling method called the Virtual Clock mechanism is developed to regulate packet flows in the Flow Network, and provides firewalls among flows, as in a TDM system, but with the statistical multiplexing advantages of packet switching.
IEEE Journal on Selected Areas in CommunicationsNumerical methods for modeling computer networks under nonstationary conditions
129 Citations1990David Tipper, Malur K. Sundareshan
Numerical techniques for modeling computer networks under nonstationary conditions are discussed, and two distinct approaches are presented which allow multiple classes of traffic to be modeled and establishes a framework for the use of optimal control techniques in the design of network control strategies.
Operations ResearchDynamic Modeling and Control of Congestion-Prone Systems
126 Citations1976Carson E. Agnew
The model is used to study the stability and transient behavior of a congestion-prone system and to analyze policies for the control of congestion in a simple optimal control model.
Congestion control in computer networks
124 Citations1991Srinivasan Keshav
This thesis examines the problem of congestion control in reservationless packet switched wide area data networks by modeling a conversation as a linear system in a simple control-theoretic approach, which is used to synthesize a robust and provably stable flow control protocol.
ACM SIGCOMM Computer Communication ReviewDynamical behavior of rate-based flow control mechanisms
104 Citations1990Jean-Chrysostome Bolot, A. Udaya Shankar
This work presents a model in which a network with connections subject to rate-based flow control is considered as a dynamical system, i.e., a set of coupled differential equations, and obtains closed-form solutions for the dynamical model in both transient and steady state regimes.
IEEE Transactions on CommunicationsA new approach to performance-oriented flow control
99 Citations1981K. Bharath-Kumar, Jeffrey M. Jaffe
Flow control is proposed as a means of obtaining an "optimal tradeoff" between low delay and high throughput in computer networks and a class of algorithms which attempt to optimize network performance are investigated.
A theoretical analysis of feedback flow control
95 Citations1990Scott Shenker
A simple model of feedback flow control is introduced, in which sources make synchronous rate adjustments based on the congestion signals and other local information, and apply it to a network of Poisson sources and exponential servers.
Dynamic adaptive windows for high speed data networks: theory and simulations
90 Citations1990Debasis Mitra, J.B. Seery
The algorithms proposed here require each virtual circuit's source to measure the round trip response times of its packets and to use these measurements to dynamically adjust its window, and give stable, efficient performance when these exist.
Computer Networks and ISDN SystemsBandwidth management: A congestion control strategy for broadband packet networks — characterizing the throughput-burstiness filter
71 Citations1990A.E. Eckberg, D.T. Luan +1 more
A particular module, that quantitatively characterizes a “throughput-burstiness filter” associated with BWM, is studied through an analytically tractable traffic model, and results of analysis of this model are used to illustrate the operation of the BWM controls.
arXiv (Cornell University)Myths about Congestion Management in High Speed Networks
70 Citations1998Raj Jain
The circumstances under which backpressure is useful or not are discussed, and it is argued that a single congestion scheme is not sufficient, but that a combination of several schemes is required for complete congestion management in a network.
IEEE Transactions on CommunicationsAsymptotically optimal design of congestion control for high speed data networks
68 Citations1992Debasis Mitra
The basic mechanism of sliding windows for the congestion control of virtual circuits is examined, and formulas for basic quantities of interest, such as throughput, delay and moments of packet queues, in the optimal operating regime as well as in other regimes are obtained.
Xunet 2: a nationwide testbed in high-speed networking
43 Citations1992Alistair Fraser, Charles Kalmanek +3 more
The authors provide an overview of the architecture of the Xunet 2 testbed, which has three principal components: routers, switches and network management systems.
Fuzzy prediction of time series
37 Citations2003P.S. Khedkar, Srinivasan Keshav
An approach to time series extrapolation based on fuzzy control and a modification to the scheme where the control parameter of the averaging scheme is dynamically adjusted by a simple fuzzy logic controller is presented.
A high speed transport protocol for datagram/virtual circuit networks
36 Citations1989Krishan Sabnani, Arun N. Netravali
A design and preliminary analysis of an end-to-end transport protocol that is capable of high throughput consistent with the evolving wideband physical networks based on fiber optic transmission lines and high capacity switches and an efficient implementation of selective repeat method of error control used in this protocol are presented.
IEEE Transactions on Automatic ControlFlow control protocols for integrated networks with partially observed voice traffic
26 Citations1987F. Vakil, Aurel A. Lazar
It is shown that the optimum control law is bang-bang and the conditional mean estimate of the state of the voice traffic is a sufficient statistic for the optimal control strategy and a suboptimum and easily implementable adaptive window flow control mechanism is proposed.
INFOR Information Systems and Operational ResearchTime-Dependent Analysis Of Queueing Systems
21 Citations1986Satish K. Tripathi, Andrzej Duda
A survey of results available for time-dependent analysis of queueing systems and results and computational methods for single-server queues and results on queueing networks are surveyed.
IEEE Transactions on Automatic ControlOptimal flow control of multiclass queueing networks with partial information
13 Citations1990M.-T.T. Hsiao, Aurel A. Lazar
Structural results and explicit solutions for the optimal flow control problem of multiclass queueing networks with decentralized information are given and the structure of the optimal control is shown to be of a window type in both cases.
Performance EvaluationFlow control in integrated local area networks
10 Citations1987F. Vakil, Man-Tung T. Hsiao +1 more
It is shown that an adaptive window flow control mechanism maximizes the average throughput under an average system time delay constraint and aFlow control mechanism is proposed for implementation that is asymptotically optimum.
Open Scholarship Institutional Repository (Washington University in St. Louis)Asynchronous Algorithms for Optimal Flow Control of BCMP Networks
8 Citations1989Andreas D. Bovopoulos
It is shown that that optimal arrival rates correspond to the unique Nash equilibrium point of a noncooperative game problem.
Deterministic analysis of flow and congestion control policies in virtual circuits
7 Citations1990Samar Singh, Ashok K. Agrawala +1 more
This work analyzes some existing window and rate based flow control schemes, and proposes a new protocol, 2P, that exploits the deterministic nature of a VC to provide optimal performance.
Window dynamics
6 Citations1989John Waclawsky, Ashok K. Agrawala
An analysis technique is presented that allows a precise description of the dynamic behavior of window protocols and the application of the deterministic analysis technique to a current virtual circuit flow control implementation by allowing a control function to influence the window size.