throbber
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

This document is available on Docket Alarm but you must sign up to view it.


Or .

Accessing this document will incur an additional charge of $.

After purchase, you can access this document again without charge.

Accept $ Charge
throbber

Still Working On It

This document is taking longer than usual to download. This can happen if we need to contact the court directly to obtain the document and their servers are running slowly.

Give it another minute or two to complete, and then try the refresh button.

throbber

A few More Minutes ... Still Working

It can take up to 5 minutes for us to download a document if the court servers are running slowly.

Thank you for your continued patience.

This document could not be displayed.

We could not find this document within its docket. Please go back to the docket page and check the link. If that does not work, go back to the docket and refresh it to pull the newest information.

Your account does not support viewing this document.

You need a Paid Account to view this document. Click here to change your account type.

Your account does not support viewing this document.

Set your membership status to view this document.

With a Docket Alarm membership, you'll get a whole lot more, including:

  • Up-to-date information for this case.
  • Email alerts whenever there is an update.
  • Full text search for other cases.
  • Get email alerts whenever a new case matches your search.

Become a Member

One Moment Please

The filing “” is large (MB) and is being downloaded.

Please refresh this page in a few minutes to see if the filing has been downloaded. The filing will also be emailed to you when the download completes.

Your document is on its way!

If you do not receive the document in five minutes, contact support at support@docketalarm.com.

Sealed Document

We are unable to display this document, it may be under a court ordered seal.

If you have proper credentials to access the file, you may proceed directly to the court's system using your government issued username and password.


Access Government Site

We are redirecting you
to a mobile optimized page.





Document Unreadable or Corrupt

Refresh this Document
Go to the Docket

We are unable to display this document.

Refresh this Document
Go to the Docket