A Control-Theoretic Approach to Flow ControlSrinivasan KeshavComputer Science Division, Department of EECS,University of Cali~mi& Berkeley,International Computer ScienceInstitoteBerkeley, CA 94720, USA.keshav@tenet. Berkeley. EDUAbstractThis paper presents a control-theoretic approach to reactive flowcontrol in networks that do not reserve bandwidth. We assumearound-robin-like queue service discipline in the output queues ofthe network’s switches, and propose deterministic and stochasticmodels 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 Kal-man state estimator is derived from d~crete-time state spaceanalysis, but there are difficulties in using the estimator in prac-tice. These difficulties are overcome by a novel estimationscheme based on fuzzy logic. We then present a technique toextract and use additional information horn the system todevelop a continuous-time system model. This is used to designa wuisnt of the control law that is also provably stable, and, inaddition, takes control action as rapidly as possible. Finally,practical issues such as correcting parameter drift and cmmlina-tion with window flow control are described.1. IntroductionAs networks move towards integrated service, there is aneed for network control mechanisms that can provide userswith different qualities of service in terms of throughput, delayand delay jitter [1]. Recent work has shown that these guaran-tees can be provided if the network makes bandwidth reserva-This research wns supported by the Natiossl Ssimce Forrsdation and theDefense Advanced Reseerch Pmjacts Agency (DARPA) under CoopsrativsAgreement NCR-8919038 with the Coqreration for National Ressarch Ini-tiatives, by AT&T Brdt Lab-storks, HitscirL Ltd., the Usivsrsity of Cati-fonria ssder a MICRO grant, and the fnternationst Computsr Ssimce Issti-tute. Tbe views and cmclusions mmsimrt is this drmrrmnt am those of theauthors, and shostd not bs interpmtd as rsprssredng ofticist policies, si-thsr expressed or implied, of rhe U.S. Govennnmt or asy of the spomorisgorganizations. Cunmt addres.w AT&T Belt Laboratmirs, (XKI Mtn. Ave.MuxTay Hitt NJ 07974.Permission to copy without fee all or part of this material isgranted provided that the copies are not made or distributed fordiract commercial advantage, the ACM copyright notice and thetitla of the publication and its date appear, and notice is giventhat copying is by permission of the Association for ComputingMachinery. To copy otherwise, or to republish, raquires a feeand/or specific permission.~ 1991 ACM 0-89791 -444-91911000810003 ...$1 .50tions on behalf of each conversation (also called channel, circuitor virtual circuit we use ‘conversation’ throughout) [2-5].How-ever, such reservations canreduce the statistical multiplexing inthe network making the system expensive.An interesting problem arises in the control of converaa-tiona that donot reserve bandwidth, and hence are not given anyperformance guarantees by the network. These conversationsmust adapt to changing network conditions in order to achievetheir data transfer goals. In this paper we present a control-theoretic approach to detetmine how a conversation can satisfyits throughput and queueing delay requirements by adaptittg itsdata transfer rate to changes in network state, and to prove thatsuch adaptations do not lead to instability. This approach can Be.used to control both transport connections in reservationless net-works, and so-called ‘best-effort’ connections in reservation-oriented networks [2].A control theoretic approach to flow control requires thatchanges in the netsvork state be observable. In recent work, wehave shown that it is possible to measure network state easily ifthe servers at the output queues of the switches are of a typecalled a Rate Allocating Server and the transport protowl usesthe Packet-Pair probing technique (described below) [6-8].Thus, in this paper, we will make the assumption that the queueservice discipline isof the RAS type and that sources implementPacket-Pair. Our approach does not extend to Fmt-Come-First-Served (FCFS) networka, where there is no simple way to probethe network state.The paper is laid out as follows. We first describe rateallocating servers ($2), and present deterministic and stochasticmodels for networks of such servers ($3). Nex~ we describe thePacket-Pair state probing technique ($4). This is used as thebaais for the design of a stable rate-based flow control scheme($5). A problem with non-linearity in the system is discussed in$6. We present a Kalmau state estimator in $7. However, thisestimator is impractical, and so we have designed a novel esti-mation scheme baaed on fuzzy logic ($8). A technique toincrease the frequency of control baaed on additional informa-tion horn the system is presented in $9, and this serves as thebasis for a new control law. Practical implementation issues arediscussed in $10, and these include correcting for parameterdrift, and interaction with window flow control. We concludewith some remarks on the limitations of the approach ($11) anda review of related work ($ 12).32. Rate Allocathtg Servers3. Choice of network modelIn this sectio% we deseribe the notion of a Rate Allocat-ing Server. Consider the queue service dscipline in the outputqueues of the routers of a communication network. If packetsare scheduled in strict Time-Division-Multiplexing (TDM)order, then whenever a conversation’s time slot comes aroundand it has no data to send, the output trunk is kept idle and somebandwidth is wasted. Suppose packets are stamped with a prior-ity index that corresponds to the time of service of the packetwere the server actually to do TDM. It can be shown that ser-vice in order of increasing priority index has the effect ofapproximatelyemulatingTDM without its attendantinefficiencies [9]. This idea lies behind the Fair Queueing ser-vice discipline [10]. In recent work it has been shown that FairQwsueing is quite similar to the Virtual Clock [5] discipline [11].Thus, we will refer to both as Rate Allocating Servers (RASS}the reason for this name will shortly become clear.While the Virtual Clock scheduling discipline was origi-nally presented in the context of a reservation-oriented networklayer, we study its behavior in reservationless networks. Thisraises an important point. In reservation-oriented networks, dur-ing
View Full Document
Unlocking...