To Appear: Proc. IEEE Infocom'95, Boston, April 1995. jorg/archive/papers/Infocom95.pdf · To Appear:…

  • Published on

  • View

  • Download

Embed Size (px)


<ul><li><p>To Appear: Proc. IEEE Infocom'95, Boston, April 1995.</p><p>A Service with Bounded Degradation in Quality-of-Service</p><p>Networks </p><p>Jorg Liebeherr Dongwei Liao</p><p>Department of Computer Science</p><p>University of Virginia</p><p>Charlottesville, VA 22903</p><p>Abstract</p><p>Many network applications that require Quality-of-</p><p>Service (QoS) support, such as transmission of digital</p><p>voice and video, tolerate a certain level of service degra-</p><p>dation. In this study, a novel network service, referred</p><p>to as service with bounded degradation (BD service),</p><p>is presented that can take advantage of the delay tol-</p><p>erance of applications. Dierent from previous propos-</p><p>als for similar services, the BD service can guarantee</p><p>hard lower bounds of the service degradation. This is</p><p>achieved by strictly limiting the amount of trac that</p><p>is subject to service degradation. To implement a BD</p><p>service, network trac is partitioned into components</p><p>with dierent delay requirements. Policing of the traf-</p><p>c components is achieved by multi-level leaky buckets.</p><p>A novel scheduler, referred to as EDD-BD (Earliest</p><p>Deadline Due - Bounded Degradation) scheduler, per-</p><p>forms switching of packets. Properties of the EDD-BD</p><p>scheduler are presented and analyzed.</p><p>1 Introduction</p><p>Current computer network technology can provide veryhigh bandwidth up to several hundred megabits persecond. The dramatic increase in the capacity of com-munication links enables the design of packet-switchingnetworks which provide performance guarantees totrac that is carried by the network. The set of perfor-mance guarantees given to a network connection is re-ferred to as quality-of-service (QoS). Performance guar-antees are specied in terms of network bandwidth,network delay, network delay jitter, and loss probabil-ity. We refer to a packet-switching network that canprovide quality-of-service to connections as QoS net-work.</p><p>In recent years, several researchers have proposedarchitectures for connection-oriented QoS networks</p><p>This work is supported in part by the National Science Foun-</p><p>dation under Grant No. NCR-9309224.</p><p>[1, 2, 3]. In all proposals the concept of quality-of-service is quite similar. When requesting a new con-nection a client submits to the network a specicationof its trac and the requested QoS. The network ver-ies if the requested QoS can be guaranteed. If thenetwork is not able to support the QoS requirements itrejects the establishment of the connection, otherwisethe connection is established. After connection estab-lishment the network must support the admitted QoSuntil the connection is released.</p><p>Since many network clients do not require that ser-vice commitments be guaranteed for all packets of aconnection, a QoS network architecture oers severallevels of service commitments. At the highest level, aso-called deterministic service [2] guarantees that per-formance requirements are met for all packets at alltimes. Since this type of service commitment mustsupport the requested QoS even during possibly rareperiods of congestion, the amount of network resourcesthat must be allocated for a deterministic service typi-cally exceeds by far the average resource requirements.At the lowest level of service commitments, the networkdoes not guarantee any QoS requirements at all. Thislevel of service is commonly referred to as best-eortservice. The network does not reserve any resourcesfor a connection with a best-eort commitment.1 Also,best-eort trac can be subject to any form of servicedegradation, that is, packet delays can be arbitrarilylong or packets may be dropped.</p><p>Most network clients which require performanceguarantees can tolerate a certain level of service degra-dation. As an example, transmission of digitized voicedoes not need reliable delivery, but can tolerate a lim-ited number of packet losses. However, the amountof lost voice packets must be within application spe-cic bounds; otherwise, the voice stream will be notintelligible at the receiver [4]. Therefore, for voice ap-plications neither the highest nor the lowest level of</p><p>1Note that the network may, however, reserve certain re-</p><p>sources, e.g., link bandwidth, for the class of all best-eort</p><p>connections.</p></li><li><p>performance guarantees is ideal. The highest level ofperformance guarantees does not permit any packetlosses at all, and thus, does not allow the network totake advantage of the loss tolerance of voice applica-tions. On the other hand, a best-eort service is notable to support the minimal service requirement forpacket voice applications, that is, intelligibility of voiceat the receiver.</p><p>All architectures for QoS networks proposed in theliterature oer a service with commitments that areweaker than a deterministic service, but stronger thana best eort service. The statistical channel in theTenet protocol suite [2] permits network clients to spec-ify probabilistic bounds on the percentage of delayedor lost packets. Probabilistically bounded QoS guaran-tees, similar to the statistical channel, have been stud-ied in [3, 5]. The architecture proposed in [1] proposesa so-called predictive service which adapts QoS guar-antees to the load conditions in the network.</p><p>A drawback of all existing proposals for QoS ser-vice commitments which are neither deterministic, norbest-eort, is that they cannot guarantee hard lowerbounds on the degree of service degradation as com-pared to a deterministic service. Note that any prob-abilistic service guarantees are by denition not veri-able in a nite time interval. Therefore, a probabilisticQoS guarantee can be satised even if the QoS guaran-tee is violated in a time interval of nite, but otherwisearbitrary, length. On the other hand, a service whichadapts the QoS guarantees to the currently prevailingnetwork load may degrade to a best eort service with-out violating any service commitments.</p><p>In this study, we propose a new network service thatenables a specication of degraded quality-of-servicecommitments for a xed portion of trac from a con-nection. The advantage of our scheme over previousproposals for similar services is that the degree of ser-vice degradation can be veried at all times. Sinceservice degradation is bounded to a specied portionof the trac we refer to our scheme as service withbounded degradation (BD service). For the implemen-tation of the new service we require network clients tocharacterize the amount of trac which can receive alower grade of service. Also, a network client must ex-plicitly specify the performance bounds for the portionof trac that can be subject to service degradation.</p><p>There are a number of problems that must be solvedto make a service with bounded degradation feasible.One problem is illustrated in the following example.Assume a connection wishes to transmit packetizedvoice over a QoS network. The voice connection mayrequest a delay bound of 100 ms for 90% of its traf-</p><p>c, and a delay bound of 200 ms for 10% of its trac.Naively, the network could separate the trac streaminto two components, and provide delay bounds of 100ms and 200 ms to the respective components. In thiscase, it is feasible that packets from the high delay com-ponent will catch up with, and possibly pass, packetsfrom the low delay component. As a result, packetsmay arrive at the receiver in a dierent order than theywere transmitted. To overcome this out-of-sequenceproblem we propose an extension to traditional packetscheduling mechanisms which guarantees in sequencedelivery of packets, yet, maintains dierent levels ofperformance commitments to dierent portions of thetrac.</p><p>The remaining paper is structured as follows. Westate our assumptions on the network trac in Sec-tion 2. In Section 3 we present a modied packet sched-uler which provides dierent delay bounds to dierentportions of the trac from a single connection, yet,maintains the sequence of the packet stream. In Sec-tion 4 we investigate properties of the modied packetscheduler. These properties are used in Section 5 wherewe obtain analytical results on the BD service. Theseresults are applied in an example in Section 6. In Sec-tion 7 we conclude our results.</p><p>2 Trac Model</p><p>In a QoS architecture, a network client submits witha request for a new connection (a) a set of parameterswhich characterize the trac of the connection, and(b) the required QoS guarantees. Once the connec-tion is established, that is, admission control functionshave determined that the performance guarantees canbe maintained for the trac as characterized by thenetwork client, so-called policing functions at the en-trance to the network enforce that all trac conformsto the specied characterization.</p><p>Throughout this study, we assume that trac froma connection is characterized by two parameters (b; T )where b denotes the maximum number of packets sub-mitted to the network at any point in time (burst fac-tor), and 1=T denotes the maximum average rate atwhich packets are generated (rate factor). We assumethat packets are xed-sized.</p><p>If a network client requests the establishment of aconnection with bounded service degradation (BD con-nection) we require that the client characterizes theportion of trac which may be subject to service degra-dation. That is, a client characterizes the connectiontrac with two sets of parameters (bp; Tp) and (bs; Ts).The sets describe the primary component and the sec-</p></li><li><p>ondary component of the trac, respectively. 2 Thesecondary component species the portion of tracthat may be subject to service degradation. We as-sume that a multi-level leaky bucket [8] is used forpolicing the two trac components. In Figure 1 weillustrate the operations of the policing function. Fig-ure 1 shows two token pools, one for primary tokens(p-tokens) and one for secondary tokens (s-tokens); p-tokens and s-tokens are added to the respective poolat a rate of 1=Tp and 1=Ts, respectively. If the p-tokenpool contains bp tokens, no more tokens are added.Likewise, tokens are added to the s-token pool onlyif it contains less than bs tokens. Packets waiting fortransmission are stored in a packet output queue. Be-fore a packet is admitted to the network it has to drawa token from one of the token pools. 3 If both tokenpools are empty no packet is admitted to the network.If a packet enters the network by drawing a p-token,the packet is tagged as a p-packet. If the packet en-ters the network by drawing an s-token, the packet istagged as an s-packet. Note, that we do not permit aclient to control the tagging of particular packets.</p><p>The maximum trac that can enter the networkfrom the two trac components in any time intervalof length can be described by the following two rate-controlling functions Ap and A</p><p>s :</p><p>Ap( ) = bp +</p><p>Tp</p><p>As( ) = bs +</p><p>Ts</p><p>(1)</p><p>where As( ) denotes the maximum amount of tracwhich may receive degraded services in a time intervalof length . The total number of packets that mayenter the network in any time interval of length isthen bounded by A( ) = Ap( ) + A</p><p>s( ).Let us assume that a network client requests BD ser-</p><p>vice for a connection by specifying the trac parameterset (Tp; Ts; bp; bs). With the trac characterization theconnection will also specify two delay bounds dp and ds(dp &lt; ds) which denote the maximum tolerable delayat a node for the respective trac components. Ad-mission control tests in the network must verify thatthe specied delay bounds can be supported [2, 7].That is, the network must be able to determine if itcan guarantee a maximumdelay of dp for packets fromthe primary component, and a maximum delay of dsfor packets from the secondary component. Also, thenetwork must verify that the new connection will not</p><p>2In principle, one could dene an arbitrary number of com-</p><p>ponents. Here, we assume that BD connections only specify two</p><p>components.3One could impose a rule that a packet only attempts to draw</p><p>an s-token if the p-token pool is empty. In this study, we assume</p><p>that the selection is arbitrary.</p><p>GeneratorToken</p><p>b</p><p>Network</p><p>Packet Output Queue</p><p>Pools-Token</p><p>Pools-Token</p><p>bp</p><p>p</p><p>p</p><p>s</p><p>s</p><p>p</p><p>1 / T 1 / T</p><p>sp</p><p>sp</p><p>Figure 1: Two-Level Leaky Bucket.</p><p>result in violations of delay guarantees for previouslyadmitted connections. Note that the admission controltests for a BD connection are performed separately foreach component. In the following, we will assume thatall connections that are present in the network havepassed the admission control tests.</p><p>3 Packet Schedulers for a BD</p><p>Service</p><p>Here we show the operation of a packet scheduler in anetwork node that supports BD connections. We rstillustrate that a straightforward implementation of abounded degradation scheme will result in an out-of-sequence delivery of packets from the same connection.Then we show the design of a packet scheduler thatovercomes the misordering problem.</p><p>Network trac from a connection is assumed to tra-verse a xed number of nodes on its way from thesource to the destination. For each outgoing link eachnode has a packet scheduler which selects the nextpacket for transmission. The scheduling discipline ofthe packet scheduler determines the order in whichpackets are transmitted. In our study we will assumethat the scheduling discipline of packets is Earliest-Deadline-Due (EDD), i.e., each packet is assigned adeadline and the scheduler always selects the packetwith the lowest deadline for transmission. For the restof this study we assume that there is only one node onthe route from the source to the destination.</p><p>Packets arrive to the scheduler as p-packets or s-packets. Since p-packets have a shorter delay boundthan s-packets, i.e., dp &lt; ds, the EDD scheduler maycause packets to depart from the node in a dierentsequence than they arrived in. Consider the examplein Figure 2 where we depict the arrival and departuretimes of three packets from a BD connection at an</p></li><li><p>d</p><p>Pp</p><p>1 P2s</p><p>Pp</p><p>3</p><p>Pp</p><p>1</p><p>t + dp1</p><p>1t</p><p>time</p><p>timePacket Departure</p><p>Packet Arrival</p><p>Pp</p><p>Ps</p><p>d</p><p>dp</p><p>s</p><p>p</p><p>t + dp t + d3 2 s</p><p>t t2 3</p><p>23</p><p>Figure 2: Misordering of Packets in an (ordinary) EDDscheduler.</p><p>EDD scheduler. The packets have arrival times t1, t2,and t3. We assume that the rst and the third packet,denoted by P p1 and P</p><p>p3 , are tagged as p-packets, and</p><p>the second packet, P s2 , is tagged as s-packet. Assumingdelay bounds of dp for p-packets and ds for s-packets,packet P p1 obtains a deadline of t1 + dp, packet P</p><p>s2 a</p><p>deadline of t2+ds, and packet Pp2 a deadline of t3+dp.</p><p>If each packet experiences the maximum tolerable de-lay, all packets will depart at their deadlines. As shownin Figure 2, if t3 + dp &lt; t2 + ds, packet P</p><p>p3 will depart</p><p>from the scheduler before packet P s2 . As a result, thescheduler has misordered the packet sequence.</p><p>Note that an out-of-sequence delivery of packetsmay result in violations of QoS guarantees for a BDconnection even though individual p-packets and s-packets fulll the delay requirements. In our example,the receiving host of the packets shown in Figure 2must wait for the arrival of packet P s2 before packetP</p><p>p3 can be submitted to the receiving application. If</p><p>this reordering delay is considered, packet P p3 incurs adelay of ds (t3 t2) which may violate the speci...</p></li></ul>