Supporting Real-Time Applications in an Integrated Services Packet Network:
`Architecture and Mechanism
`
`David D. Clark1
`Laboratory for Computer Science
`Massachusetts Institute of Technology
`ddc@lcs.m.it.edu
`
`Scott Shenker Lixla Zhang
`Palo Alto Research Center
`Xerox Corporation
`shenker, lixia@parc.xerox.com
`
`Abstract
`
`This paper considers the support of real-time applications
`in a.n Integrated Services Packet Network (JSPN). We first
`review the characteristics of real-time applications. We ob(cid:173)
`serve that, contrary to the popular view that real-time ap(cid:173)
`plica~ions lll!Ct:ssarily require a fixed delay bound, some real(cid:173)
`time applications a.re more flexible a.nd can a.da.pt to current
`network conditions. We then propose an ISPN architec(cid:173)
`ture tha.t supports two distinct kinds of real-time service:
`guaranteed service, which is the traditional form of real(cid:173)
`time service discussed in most of the literature a.nd involves
`pre-computed worst-case delay bounds, and predicted service
`which uses the measured performance of the network in com(cid:173)
`puting delay bounds. We then propose a packet scheduling
`mechanism that can support both of these real-time services
`a.s well a.s accommodate datagram traffic. We also discuss
`two other aspects of an overall ISPN architecture: the ser(cid:173)
`vice interface and the admission control criteria..
`
`1
`
`Introduction
`
`The current generation of telephone networks and the cur(cid:173)
`rent generation of computer networks were each designed to
`carry specific and very different kinds of traffic: analog voice
`and digital data.. However, with the digitizing of telephony
`in ISDN and the increasing use of multi-media in computer
`applications, this distinction is rapidly disappearing. Merg(cid:173)
`ing these sorts of services into a. single network, which we re(cid:173)
`fer to here as an Integrated Services Packet Network (ISPN),
`would yield a single telecommunications infrastructure offer(cid:173)
`ing a multitude of advantages, including vast economies of
`scale, ubiquity of access, and improved statistical multiplex(cid:173)
`ing. There is a broad consensus, a.t lea.st in the computer
`networlcing community, that an ISPN is both a worthy a.nd
`an achievable goal. However, there are many political, ad(cid:173)
`ministrative, and technical hurdles to overcome before this
`vision can become a. reality.
`
`1 Research at MIT was supported by DARPA through NASA Grant
`NAG 2-582, by NSF grant NCR-8814187, and by DARPA and NSF
`through Cooperative Agreement NCR-8919038 with the Corporation
`for National Research Initiatives.
`Permission to copy without fee all or part of this material is
`granted provided that the copies are not made or distributed for
`direct commercial advantage, the ACM copyright notice and the
`title of the publication and its date appear, and notice is given
`that copying is by permission of the Association for Computing
`Machinery. To copy otherwise, or to republish, requires e fee
`and/or specific permission.
`COMM'92-8/92/MD, USA
`c, 1992 ACM 0-89791-526-7 /92/0008/0014 ... $1.50
`
`One of the most vexing technical problems that blocks
`the pa.th towards an ISPN is that of supporting real-time
`applications in a. packet network. Real-time applications
`are quite different from standard data applications, and re(cid:173)
`quire service that cannot be delivered within the typical data
`service architecture. In Section 2 we discuss the nature of
`rea.1-time a.pplica.tions at length; here, however, it suffices
`to observe that one salient characteristic of the real-time
`applications we consider is that they require a bound on
`the delivery delay of ea.ch packet2 . While this bound ma.y
`be statistical, in the sense that some small fraction of the
`packets ma.y fa.ii to arrive by this bound, the bound itself
`must be known a priori. The traditional data service archi(cid:173)
`tecture underlying computer networks has no facilities for
`prescheduling resources or denying service upon overload,
`and thus is unable to meet this real-time requirement.
`Therefore, in order to handle real-time traffic, an en(cid:173)
`hanced architecture is needed for an ISPN. We identify four
`key components to this architecture. The first piece of the
`architecture is the nature of the commitments made by the
`network when it promises to deliver a. certain quality of ser(cid:173)
`vice. We identify two sorts of commitments, guaranteed a.nd
`predicted. Predicted service is a major aspect of our paper.
`While the idea of predicted service has been considered be(cid:173)
`fore, the issues that surround it have not, to our knowledge,
`been carefully explored.
`The second piece of the architecture is the service inter(cid:173)
`face, i.e., the set of para.meters passed between t he source
`and the network. The service interface must include both
`the characterization of the quality of service the network will
`deliver, fulfilling the need of applications to know when their
`packets will arrive, and the characterization of the source's
`traffic, thereby allowing the network to knowledgeably al(cid:173)
`locate resources. In this paper we attempt to identify the
`critical aspects o{ the service interfo.ce, a.nd offer a. particular
`interface as an example. We address in passing the need for
`enforcement of these characterizations.
`The third piece of the architecture is the packet schedul(cid:173)
`ing behavior of network switches needed to meet these ser(cid:173)
`vice commitments. We discuss both the actual sclteduling
`algorithms to be used in the switches, as well as the schedul(cid:173)
`ing information that must be carried in packet headers. This
`2Since the term bound is tossed around with great abandon in the
`rest of the paper, we need to identify several different meanings to
`the term. An o pnon bound on delay is a statement that none of
`the future delays will exceed that amount. A post facto bound is the
`maximal value of a set of observed delays. Statistical bounds allow
`for a certain percentage of violations of the bound; absolute bounds
`allow none.
`
`14
`
`

`

`part of the architecture must be carefully considered; since it
`must be executed for every packet it must not be so complex
`as to effect overall network performance.
`The final part of the architecture is the means by which
`the traffic and service commitments get established. Clearly,
`the ability of the network to meet its service commitments is
`related to the criteria the network uses to decide whether to
`accept another request for service. While we do not present
`a specific algorithm to regulate the admission of new sources,
`we show the relation between the other parts of our proposal
`and a general approach to the admission control problem.
`There are also many architectural issues not directly re(cid:173)
`lated to the nature of real-time traffic; for instance, the is(cid:173)
`sues of routing, datagram congestion control, and the inter(cid:173)
`action of administrative domains all pose interesting chal(cid:173)
`lenges. We do not address these issues in this paper, and
`any final architectural proposal for an ISPN must solve these
`longstanding problems. It is important to note, however,
`that we do not believe that the architectural choices we ad(cid:173)
`,·ocate here for real-time traffic unnecessarily restxict the
`scope of solutions to these other problems.
`This paper has 12 Sections and an Appendix. In Section
`2 we begin with a discussion of the nature of real-time traffic.
`In particular, we note that some real-time applications can
`adapt to current network conditions. This leads us to pro(cid:173)
`pose, in Section 3, that an ISPN support two kinds of real(cid:173)
`time service commitments: guaranteed service and predicted
`service. In Section 4 we present a time-stamp based schedul(cid:173)
`ing algorithm which is a nonuniformly weighted version of
`the Fair Queueing algoritl1m discussed in Reference [4], and
`then refer to a recent result due to Parekh and Gallager (see
`References (19, 20]) which states that, under certain condi(cid:173)
`tions, this algorithm delivers guaranteed service in a network
`of arbitrary topology. We then turn, in Sections 5 and 6,
`to the scheduling algorithms best suited for providing pre(cid:173)
`dicted service. The predicted service scheduling algorithm
`incorporates two novel ideas; that of using FIFO service in a
`real-time context, and that of correlating the queueing delay
`of a packet at successive nodes in its path to reduce delay jit(cid:173)
`ter. We combine these two scheduling algorithms in Section
`7, presenting a unified scheduling algorithm which provides
`both guaranteed and predicted service. Given the current
`frenzy of activity in the design of real-time scheduling algo(cid:173)
`rithms, we do not expect that the algorithm presented here
`will be the final word on the matter; however, we do hope
`that the insight embodied therein will be of lasting value.
`In particular, we think that the insight underlying our de(cid:173)
`sign, that it is necessary to distinguish between the two basic
`principles of isolation and sharing, is both fundamental and
`novel.
`In Section 8 we return to the issue of the service interface.
`Since the service interface will be invoked by applications,
`we expect that a real-time service interface will outlive any
`particular underlying network mechanism. Thus, we have
`attempted in our proposal to produce an interface which is
`flexible enough to accommodate a wide variety of supporting
`mechanisms. Admission control policies are discussed briefly
`in Section 9, and the support of other service qualities is
`covered in Section 10.
`In order to build up sufficient context to meaningfully
`compare our work to previously published work, we de(cid:173)
`lay the detailed discussion of related work until Seclion 11.
`However, we wish to note here that our work borrows heav(cid:173)
`ily from the rapidly growing literature on providing real(cid:173)
`time service in packet networks. In particular, the works of
`
`Parekh and Gallager ((19, 201), Jacobson and Floyd ((14]),
`and Lazar, Hyman, and Pacifici ((12, 13]) have all con(cid:173)
`tributed to our design.
`Finally, in Section 12, we conclude our paper with a re(cid:173)
`view of our results and a brief discussion of related economic
`issues. The Appendix contains details relating to the simu(cid:173)
`lation results that are presented in Sections 5-7.
`
`2 Properties of Real-Time Traffic
`
`2.1 A Class of Real-Time Applications
`
`In the discussion that follows, we focus on a particular class
`of real-time applications which we dub play-back applica(cid:173)
`tions. In a play-back application, the source takes some
`signal, packetizes it, and then transmits it over the network.
`The network inevitably introduces some variation in the de(cid:173)
`lay of each delivered packet. This variation has traditionally
`been called jitter. The receiver depacketizes the data and
`then attempts to faithfully play back the signal. This is done
`by buffering the incoming data to remove the network in(cid:173)
`duced jitter and then replaying the signal a.t some designated
`play-back point. Any data that arrives before its associated
`play-back point can be used to reconstruct the signal; data
`arriving after the play-back point is useless in reconstructing
`the real-time signal. For the purposes of this paper, we as(cid:173)
`sume that all such applications have sufficient buffering to
`store all packets which arrive before the play-back point; we
`return to this point in Section 10.
`Not all real-time applications are play-back applications
`(for example, one might imagine a visualization application
`which merely displayed the image encoded in each packet
`whenever it arrived). However, we believe the vast majority
`of future real-time applications, including most video and
`audio applications, will fit this paradigm. Furthermore, non(cid:173)
`play-back applications can still use the real- time network
`service provided by our architecture, although Lhis service
`is not specifically tailored to their needs.
`Play-back real-time applications have several service re(cid:173)
`quirements that inform our design proposal. First, since
`there is often real-time interaction between the two ends
`of an application, as in a voice conversation, the application
`performance is sensitive to the data delivery delay; in general
`lower delay is much preferable. Second, in order to set the
`play-back point, the application needs to have some infor(cid:173)
`mation (preferably an absolute or statistical bound) about
`the delays that each packet will experience. Third, since all
`data is buffered until the play-back point, the application is
`indifferent as to when data is delivered as long as it arrives
`before t he play-back point3. This turns out to be a crucial
`point, as it allows us to delay certain packets which are in no
`danger of missing their play-back point in favor of packets
`which are. Fourth, these play-back applications can often
`tolerate the loss of a certain fraction of packets with only a
`minimal distortion in the signal. Therefore, the play-back
`point need not be so delayed that absolutely every packet
`arrives beforehand.
`
`2.2 The Nature of Delay
`
`The delay in the network derives from several causes. There
`is in practice a large fixed component to the delay, ca.used
`3This is where we invoke the assumption, mentioned previously,
`that the receiver has sufficient buffers.
`
`15
`
`

`

`by the propagation of the packet at the speed of light, and
`the delay in transmission at each switch point waiting for
`the entire packet to arrive before commencing the next stage
`of transmission. ( Cut-through networks avoid this delay by
`starting transmission before receipt is complete; most packet
`networks are not cut-through.) Added to this fixed delay is a
`variable amount of delay related to the time that each packet
`spends in service queues in the switches. This variation, or
`jitter, is what must be bounded and minimized if adequate
`real-time service is to be achleved.
`Queueing is a fundamental consequence of the statistical
`sharing that occurs in packet networks. One way to reduce
`jitter might be to eliminate the statistical behavior of the
`sources. Indeed, one misconception is that real-time sources
`cannot be bursty (variable in their transmission rate), but
`must transmit at a fixed invariant rate to achieve a real-time
`service. We reject this idea; allowing sources to have bursty
`transmission rates and to take advantage of statistical shar(cid:173)
`ing is a major advantage of packet networks. Our approach
`is thus to bound and characterize the burstiness, rather than
`eliminate it.
`The idea of statistical sharing implies that there are in(cid:173)
`deed several sources using the bandwidth; one cannot share
`alone. Our approach to real-time traffic thus looks at the
`aggregation of traffic as fundamental; the network must be
`shared in such a way that clients (1) get better service than
`if there were no sharing (as in a circuit switched or TDM
`network) and (2) are protected from the potentially negative
`effects of sharing (most obviously the disruption of service
`caused by sharing with a mis-behaving source that overloads
`the resource).
`
`2.3 Dealing with Delay
`
`An application, in order to set its play-back point knowl(cid:173)
`edgeably, needs to know some bound on the delay, plus an
`estimate of the fraction of packets missing t hat bound. This
`information forms the nucleus of the network's service spec(cid:173)
`ification in the service interface ( to be discussed more fully
`in Section 8).
`Some real-time applications will use an a priori delay
`bound advertised by the network to set the play-back point
`and will keep the play-back point fixed regardless of the
`actual delays experienced. These we dub rigid applications.
`For other applications, the receiver will measure the network
`delay experienced by arriving packets and then adaptively
`move the play-back point to the minimal delay that still pro(cid:173)
`duces a sufficiently low loss rate. We call such applications
`adaptive. Notice tha.t adaptive applications will typically
`have an earlier play-bad, poi_nt tltan rigid applications, and
`thus will suffer less performance degradation due to delay.
`This is because the client's estimate of the post facto bound
`on actual delay will likely be less than the a priori bound
`pre-computed by the network. On the other hand, since
`the adaptation process is not perfect and may occasionally
`set the play-back point too early, adaptive applications will
`likely experience a higher loss rate.
`The idea of adaptive applications is not relevant to cir(cid:173)
`cuit switched networks, which do not have jitter due to
`queueing. Thus most real-time devices today, like voice and
`video codecs, are not adaptive. Lack of widespread experi(cid:173)
`ence may raise the concern that adaptive applications will be
`difficult to build. However, early experiments suggest that
`it is actually rather easy. Video can be made to adapt by
`dropping or replaying a frame as necessary, and voice can
`
`In fact,
`adapt imperceptibly by adjusting silent periods.
`such adaptive approaches have been employed in packetized
`voice applications since the early 70's {[23)); the VT ([2))
`and VAT ([15]) packet voice protocols, which are currently
`used to transmit voice on the Internet, are living examples
`of such adaptive applications•. It is important to note that
`while adaptive applications can adjust to the delivered de(cid:173)
`lays over some range, there are typically limits to this adapt(cid:173)
`ability; for instance, once the delay reaches a certain level,
`it becomes difficult to carry out interactive conversations.
`Another useful distinction between network clients is how
`tolerant they are to brief interruptions in service. This level
`of tolerance is not just a function of the application, but
`also of the end users involved. For instance, a video confer(cid:173)
`ence allowing one surgeon to remotely assist another during
`an operation will not be tolerant of any service interrup(cid:173)
`tion, whereas a video conference-based family reunion might
`happily tolerate interruptions in service ( as long as it was
`reflected in a cheaper service rate).
`We can thus characterize network clients along two axes:
`adaptive or rigid, and tolerant or intolerant. It is unlikely
`that an intolerant network client is adaptive, since the adap(cid:173)
`tive process will likely lead, in the event of rapidly changing
`network conditions, to a brief interruption in service while
`the play-back point is re-adjusting. Furthermore, a tolerant
`client that is rigid is merely losing the chance to improve its
`delay. Such a combination of tolerance and rigidity would
`probably reflect the lack of adaptive hardware and software,
`whlch we believe will soon be cheap and standard enough to
`become fairly ubiquitous. We a.re thus led to the prediction
`that there will be two dominant classes of traffic in the net(cid:173)
`work: intolerant and rigid clients, and tolerant and adaptive
`clients. We predict that these two classes will likely request
`very different service commitments from the network. Thus,
`these basic considerations about delay and how clients deal
`with it have produced a taxonomy of network clients that
`guides the goals of our architecture.
`Before turning to the issue of service commitments, let
`us note that one of the key differences between real-time
`applications and the traditional datagram applications lies
`in the nature of the offered traffic. Data traffic is typically
`In contrast, real-time appli(cid:173)
`sporadic and unpredictable.
`cations often have some intrinsic packet generation process
`which is long lasting compared to the end-to-end delays of
`the individual packets. This process is a consequence of the
`specifics of the application; for example the coding algorithm
`for video, along with the nature of the image, will determine
`the packet generation process. Furthermore, this generation
`process can often be characterized as conforming to some
`traffic filter or bound (such as the token bucket filter which
`we describe in Section 4). For instance, the traffic gener(cid:173)
`ated by certain video codecs can often be characterized by
`some peak rate of packet generation. When a network has
`some knowledge of the traffic load it will have to carry, it
`can allocate its resources in a much more efficient manner.
`
`3 Service Commitments
`
`Clearly, for a network to make a service commitment to a
`particular client, it must know beforehand some characteri(cid:173)
`zation of the traffic that will be offered by that client. For
`the network to reliably meet its service commitment, the
`
`~ Yet another example of an early adaptive packet voice appl.ication
`1s described in Reference [5].
`
`16
`
`

`

`client must meet its traffic commitment (i.e., its traffic must
`conform to the characterization it has passed to the net(cid:173)
`work). Thus, the service commitment made to a particular
`client is predicated on the traffic commitment of that client.
`The question is, what else is the service commitment predi(cid:173)
`cated on (besides the obvious requirement that the network
`hardware function properly)?
`One kind of service commitment, which we will call guar(cid:173)
`anteed service, depends on no other assumptions. That is,
`if the network hardware is functioning and the client is con(cid:173)
`forming to its traffic characterization, then the service com(cid:173)
`mitment will be met. Notice that this level of commitment
`does not require that any other network clients conform to
`their traffic commitments. Guaranteed service is appropri(cid:173)
`ate for intolerant and rigid clients, since they need absolute
`assurances about the service they receive.
`However, guaranteed service is not necessarily appropri(cid:173)
`ate for tolerant and adaptive clients. Adaptive clients, by
`adjusting their play-back point to reflect the delays their
`packets are currently receiving, are gambling that the net(cid:173)
`work service in the near future will be similar to that deliv(cid:173)
`ered in the recent past. Any violation of that assumption in
`the direction of increased delays will result in a brief degra(cid:173)
`dation in the application's performance as packets begin
`missing the play-back point. The client will then readjust
`the play-back point upward to reflect the change in service,
`but there will necessarily be some momentary disruption
`in service. This will occur even if the network is meeting
`its nominal service commitments (based on the bounds on
`the service), because an adaplive application is typically ig(cid:173)
`noring those a priori bounds on delay and adapting to the
`current delivered service.
`Thus, as long as the application is gambling that the re(cid:173)
`cent past is a guide to the near future, one might as well
`define a class of service commitment that makes the same
`gamble. Our second kind of service commitment is called
`predicted service. This level of commitment has two com(cid:173)
`ponents. First, as stated above, the network commits that
`if the past is a guide to the future, then the network will
`meet its service characterization. This component embod(cid:173)
`ies the fact that the network can take into account recent
`measurements of the traffic load in estimating what kind of
`service it can deliver reliably. This is in marked contrast
`to the worst-case analysis that underlies the guaranteed ser(cid:173)
`vice commitment. Second, the network attempts to deliver
`service that will allow the adaptive algorithms to minimize
`their play-back points. (This is the same as saying that the
`service will attempt to minimize the post facto delay bound.)
`Obviously, when the overall network conditions change, the
`quality of service must also change; the intent of the second
`component of the commitment is that when network con(cid:173)
`ditions are relatively static, the network schedules packets
`so that the cunent postfactodelay bounds (which are typi(cid:173)
`cally well under the long-term a priori bounds that are part
`of the service commitment) are small.
`Notice that predicted service has built into it very strong
`implicit assumptions about the behavior of other network
`clients by assuming that the network conditions will remain
`relatively unchanged, but involves very few explicit assump(cid:173)
`tions about these other network clients; i.e., their current
`behavior need not be explicitly characterized in any precise
`manner. Thus, for predicted service, the network takes steps
`to deliver consistent performance to the client; it avoids the
`hard problem, which must be faced with guaranteed service,
`of trying to compute a priori what t hat level of delivered
`
`service will be.
`We have thus defined two sorts of real time traffic, which
`differ in terms of the service commitment they receive. There
`is a third class of traffic that we call datagram traffic, to
`which the network makes no service commitments at all,
`except to promise not to delay or drop packets unnecessar(cid:173)
`ily (this is sometimes called best effort service).
`We now have the first component of our archltecture,
`the nature of the service commitment. The challenge, now,
`is to schedule the packet departures at each switch so that
`these commitments a.re met. For the sake of clarity, we first
`consider, in Section 4, how to schedule guaranteed traffic
`in a network carrying only guaranteed traffic. In Sections
`5 and 6 we then consider how to schedule predicted traffic
`in a network carrying only predicted traffic. After we have
`assembled the necessary components of our scheduling algo(cid:173)
`rithm we then, in Section 7, present our unified scheduling
`algorithm which simultaneously handles all three levels of
`service commitment.
`As we present these scheduling schemes, we also lay the
`groundwork for the other key pieces of the architecture, the
`specincs of the service interface ( which must relate closely
`to the details of the service commitment) and the method
`to control the admission of new sources.
`
`4 Scheduling Algorithms for Guaranteed Traffic
`
`In this section we first describe a traffic filter and then a
`scheduling algorithm that together provide guaranteed ser(cid:173)
`vice.
`As discussed briefly in Section 3, a network client must
`characterize its traffic load to the network, so that the net(cid:173)
`work can commit bandwidth and manage queues in a way
`that realizes the service commitment. We use a particular
`form of traffic characterization called a token bucket filter.
`A token bucket filter is characterized by two parameters, a
`rate r and a depth b. One can think of the token bucket
`as filling up with tokens continuously at a rate r, with b
`being its maximal depth. Every time a packet is generated
`p tokens are removed from the bucket, where p is the size
`of the packet. A traffic source conforms to a token bucket
`filter (r,b) if there are always enough tokens in the bucket
`whenever a packet is generated.
`More precisely, consider a packet generation process with
`t, and p; denoting the generation time and size, respectively,
`of the i'th packet. We say that this traffic source conforms
`to a token bucket filter (r, b) of rate r and depth b if the
`sequence n ; defined by no = b and n; = MI N[b, n,-1 +
`t;- 1)r - p,] obeys the constraint that n; ;:: 0 for all
`(t; -
`i. The quantities n;, if nonnegative, represent the number
`of tokens residing in the bucket after the i'th packet leaves.
`For a given traffic generation process, we can define the non(cid:173)
`increasing function b(r) as the minimal value such that the
`process conforms to a (r, b(r)) filter.
`In recent years, several time-stamp based algorithms have
`been developed. These algorithms take as input some preas(cid:173)
`signed apportionment of the link expressed as a set of rates
`r 0 (where a, labels the flows); the resulting delays depend
`on the bucket sizes b0 (r 0
`One of the first such time-stamp algorithms was the Fair
`Queueing algorithm introduced in Reference (4). This al(cid:173)
`gorithm was targeted a.t the traditional data. service archi(cid:173)
`tecture, and so involved no preallocation of resources (and
`thus had each r 0 = µ where µ denotes the link speed).
`
`).
`
`17
`
`

`

`In addition, a weighted version of the Fair Queueing algo(cid:173)
`rithm (which we refer to as WFQ), in which the r"' need
`not all be equal, was also briefly described in Reference [4]5.
`The VirtualClockalgorithm, described in References [25, 26],
`involves an extremely similai underlying packet scheduling
`algorithm, but was expressly designed for a context where
`resources were preapportioned and thus had as a fundamen(cid:173)
`tal part of its architecture the assumption that the shares r 0
`were arbitrary. Parekh and Gallager, in Reference [19], rein(cid:173)
`troduce the WFQ algorithm under the name of packetizcd
`generalized processor sharing(PGPS). They have proven the
`important result that this algorithm, under certain condi(cid:173)
`tions, can deliver a guaranteed quality of service ((20]). We
`present a brief summary of the WFQ algorithm below, since
`we make use of it in our overall scheduling algorithm; see
`References (4, 20] for more details.
`First, consider some set of flows and a set of clock rates
`r"'. The clock rate of a flow represents the relative share of
`the link bandwidth this flow is entitled to; more properly, it
`represents the proportion of the total link bandwidth which
`this flow will receive when it is active. By assigning it a
`clock rate r 0
`the network commits to provide to this flow
`an effective throughput rate no worse than (µr 0 )/(L,11 rtl)
`where the sum in the denominator is over all currently active
`flows.
`This formulation can be ma.de precise in the context of a
`fluid flow model of the network, where the bits drain contin(cid:173)
`uously out of the queue. Let tf and pf denote the generation
`time and size, respectively, of the i'th packet arriving in the
`a'th flow. We define the set of functions m"'(t), which char(cid:173)
`acterize at any time the backlog of bits which each source
`has to send, and set ma(0) = 0. We say that a flow is active
`at time t if m"'(t) > O; let A(t) denote the set of active flows.
`Then the dynamics of the system are determined as follows.
`Whenever a packet arrives, m must discontinuously increase
`by the packet size: m 0 (t+) = m 0 (t-) + p, if t = t~, where
`m 0 (t+) and m 0 (t- ) refer to right hand and left hand limits
`of m"' at t. At all other times, we know that the bits are
`draining out of the queues of the active flows in proportion
`to the clock rates of the respective flows:
`.
`8m" (t)
`8m" (t)
`.
`µr"
`_a_t _ ="'
`,11 if a E A(t), -a- = 0 if a IC A(t)
`t
`L..,peA(t) r
`
`This completely characterizes the dynamics of the fluid
`flow model. Parekh and Gallager have shown the remark(cid:173)
`able res1tlt that, in a network with arbitrary topology, if a
`flow gets the same clock rate at every switch and the sum of
`the clock rates of all the flows at every switch is no greater
`than the link speed, then the queueing delay of that flow is
`bounded above by b0 (r0 )/r". Intuitively, this bound is the
`delay that would result from an instantaneous packet burst
`of the token bucket size being serviced by a single link of
`rate r 0
`; the queueing delays are no worse than if the entire
`network were replaced by a single link with a speed equal
`to the flow's clock rate r 0
`• This result can be motivated
`by noting that if flow a's traffic were put throufh a leaky
`bucket filter of rate r" at the edge of the network , then the
`How would not suffer any further queueing delays within the
`network since the instantaneous service rate given to this
`
`5 The weighted version of Fair Queueing is mentioned on page 24
`of Reference (4), though not referred to by the name Weighted Fair
`Queueing.
`6 in a fluid flow version of a leaky bucket of rate ,. , the bits drain
`out at a constant rate r and any excess is queued.
`
`flow at every switch along the path would be at least r".
`Thus, all of the queueing delay would occur in the leaky
`, b0 (r0
`bucket filter and, since the ftow obeys an (r0
`) ) token
`bucket filter, the delay in the leaky bucket filter would be
`bounded by b"(r0 )/r0
`• Notice that the delay bound of a
`particular flow is independent of the other flows' character(cid:173)
`istics; they can be arbitrarily badly behaved and the bound
`sti