Internet Engineering Task Force Flaminio Borgonovo INTERNET-DRAFT Antonio Capone Expires: February 1999 Luigi Fratta Mario Marchese Chiara Petrioli Politecnico di Milano 29 July 1998 End-to-end QoS provisioning mechanism for Differentiated Services Status of this Memo This document is an Internet-Draft. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as ``work in progress.'' To view the entire list of current Internet-Draft, please check the ``1id-abstracts.txt'' listing contained in the Internet-Drafts Shadow Directories on ftp.is.co.za (Africa), ftp.nordu.net (Northern Europe), ftp.nis.garr.it (Southern Europe), munnari.oz.au (Pacific Rim), ftp.ietf.org (US East Coast), or ftp.isi.edu (US West Coast). Abstract This document presents an end-to-end mechanism to guarantee bandwidth and delay into the Differentiated Services mechanism to constant rate traffic such as voice and video. The mechanism requires network routers to be able to serve packets according to three classes of priority. The needed call admission control is performed by an end- to-end signaling procedure that implicitly looks for the required bandwidth and seizes it, if available. Short delays are guaranteed by the regular structure of constant rate traffic. No entities other than source and destination are involved and multicast operation comes at no further cost, which makes the mechanism fully scalable and integrable into the existing Internet. 1. Introduction The transport mechanism capable of guaranteeing demanding Quality of Service (QoS) requirements is under discussion in the INTERNET community. The Differentiated Services architecture [1] is the approach that has recently gained more credit. The goal is to offer an alternative to carry voice, video and multimedia with respect to classic Telephone/ISDN and ATM networks. The basic problem is how to guarantee bandwidth, delay and packet dropping probability, in a Borgonovo Expires:02/99 [Page 1] INTERNET-DRAFT 29 July 1998 datagram network architecture where the only service is the Best Effort packet transmission. In this contribution we consider only approaches that can be completely implemented at the IP level and do not assume any lower level QoS guarantee capability. In this context, an existing approach is represented by RSVP (Resource reSerVation Protocol) [2][3]. RSVP is a signaling mechanism among routers and hosts that includes support to ``flows'' of packets with different QoS and the ability to dedicate end-to-end capacity to real-time traffic by means of hop-by- hop resource reservation protocols. In practice, this solution changes the entire network architecture by relying on the virtual circuit connection mechanism, the paradigm of the telephony world, today extended to the B-ISDN. During the set-up phase, needed to install a virtual circuit, the network nodes cooperate, using complex protocols, to determine a path within the network and to reserve network resources such as bandwidth and buffers. The implementation of such a signaling and its related features over the layered structure of a pure datagram network will require large investments because of the heavy software and hardware modifications to be introduced in the already worldwide installed networks. A much simpler alternative is represented by the Differentiated Services approach. The basic idea is to use the IPv4 header TOS bits or the IPv6 Traffic Class octet, the "DS byte" to designate the "per-hop behaviors" that packets are to receive. By carefully aggregating a multitude of QoS-enabled flows into a reasonable number of differentiated services offered by the network it is no longer necessary to recognize and store information about each individual flow in the core routers. Though some signaling mechanism is needed to manage the service assignment to individual flows, the network mechanism still remains purely datagram and scales well. However, since the control on packets is performed hop-by-hop, it is not easy to design a suitable call acceptance policy that is able to guarantee end-to-end QoS. As the result of our research work in this field we have gained the belief that if one only wants to enforce QoS control over constant- rate or almost-constant-rate streams, simple procedures based on non- preemptive priority mechanisms and simple end-to-end signaling procedures are effective. One such procedure has been investigated in the framework of deflection networks, i.e., data networks with very small or no queuing at nodes [4]. The Bandwidth Guaranteed Service (BGS) mechanism, presented in this document, guarantees constant rate traffic bandwidth and delay requirements in datagram networks such as the Internet. BGS is based on three priority levels. It integrates and completes the DS approach and allows a QoS control as in RSVP, without adding explicit signaling protocols. No entities other than source and destination are involved and multicast operation is obtained at no further cost, Borgonovo Expires:02/99 [Page 2] INTERNET-DRAFT 29 July 1998 which makes the mechanism fully scalable. The document is organized as follows. In Section 2 we present BGS, its call setup and call acceptance procedures, while Section 3 illustrates its behavior by means of some preliminary results obtained by simulation. 2. The BGS mechanism In the following we assume connections with constant rate packet traffic. The jitter introduced by the network is eliminated at the destination user by storing the packets in a play-out buffer which is emptied at the constant nominal rate, starting with a delay D_b after the reception of the first packet of the connection. With this technique the total delivery delay experienced by packets is constant and equal to W = D_b+d_1 (1) where d_1 is the network delay suffered by the first packet. If a packet is delayed more than W, it is useless and is dropped. Therefore the QoS guaranteed traffic requires, besides the bandwidth B, also a maximum packet delay W and a maximum packet-dropping percentage gamma. The BGS mechanism requires that each packet in the network belongs to one of the three following priority classes. Class 0: (lowest priority) if the packet requests best effort service; Class 1: (intermediate priority) if the packet is a scout packet, used in the set-up procedure as defined below; Class 2: (highest priority) if the packet belongs to a constant ate flow that has been granted guaranteed service. The priority information is carried in the TOS field and is used by the routers to serve all packets according to a non-preemptive head- of-the-line priority scheme. Class 1 and 2 packets have the same constant length. The set-up procedure operates end-to-end and is activated when a new connection, characterized by the bandwidth B and the maximum allowed transfer delay W, is requested. Upon reception of a connection request C_j addressed to NODE_B, NODE_A immediately starts transmitting scout packets at the rate r_j corresponding to the requested bandwidth. The scout packets do not carry data traffic in the payload, since they are used to perform "bandwidth scouting and seizing" within the Borgonovo Expires:02/99 [Page 3] INTERNET-DRAFT 29 July 1998 network. To this purpose they only include set-up information to signal to the receiving NODE_B the request for an incoming call and the related service quality parameters. Upon receiving the first scout packet, NODE_B starts performing bandwidth measures and delay evaluations to verify whether QoS requirements are met. If the outcome is positive NODE_B sends a call acceptance packet to NODE_A. Otherwise, either it rejects the connection or starts a bandwidth negotiation procedure with NODE_A. As far as NODE_A is concerned, it keeps on transmitting scout packets until either a time-out occurs or a response from NODE_B is received. If the time out expires or the response is negative the call is aborted, meaning that the bandwidth has not been found. If a positive response is received, the connection set-up phase ends and NODE_A replaces scout packets with data packets. The bandwidth is automatically released when packets transmission ends. The priority scheme adopted guarantees that new connections can not steal bandwidth to already established ones. In fact, if some constant bandwidth connections have already been admitted, as soon as new connections attempt to steal bandwidth on a link, old connections are delayed, a queue builds up and the priority mechanism cuts out the newly arrived scout packets. 2.1 Call acceptance procedure The call acceptance procedure is directly performed by the destination node and is very simple: a new guaranteed-bandwidth connection is accepted only if the connection parameters measured on the N scout packets satisfy the QoS constraints. First, a test of significance on the Hypothesis H0 that the bandwidth requirement is satisfied is performed on the sample X_1, X_2, ..., X_(N-1), where X_i is the interarrival time between scout packet i and i+1. Under the hypothesis H0 we have E[X]=T, being $1/T$ the packet constant rate of each flow. So, the test can be exploited on the sample average M_X = (X_1+X_2+...+X_(N-1))/(N-1) (2) which is assumed to be normally distributed with average T and variance S2_x =[(X_1-T)*(X_1-T)+...+(X_(N-1)-T)*(X_(N-1)-T)]/(N-1) (3) So, for a given confidence level alpha, a threshold T_alpha exists such that if M_X < T_alpha the hypothesis H_0 is accepted. The threshold value can be obtained as T_alpha = T + xi_alpha * sqrt(S2_x/(N-1)) (4) Borgonovo Expires:02/99 [Page 4] INTERNET-DRAFT 29 July 1998 where xi_alpha is the standard normal deviate that is exceeded with probability 1 - alpha. The difference Delta B = 1/T - 1/T_alfa (5) represents the resolution power of the measure. The precision of the estimate increases with the number of statistically independent samples. In a network that carries periodic packet streams, delay samples can be considered independent if taken at a distance larger than the transmission period T_max of the connection with the lowest admissible bandwidth. Thus, the set-up period is determined in time rather than by the number of signaling packets. By doing this we guarantee that the measure captures all the existing traffics, including the slowest. For example, if we assume that the lowest bandwidth corresponds to 32 Kb/s with 640 bit packets, the packet transmission time is 20 ms so that a measure period of 1-2 seconds is needed to collect a reasonable number (50-100) of samples. The measure indicated above may be critical since, due to the error (5), the connection could be accepted even if the required bandwidth slightly exceeds the available one. In this case, more traffic than the capacity is accepted and all connections would be affected. A simple way to avoid this unwanted phenomenon is to scout for more bandwidth than needed in the set-up phase, and to turn to the required bandwidth once the call is accepted. With this modification links can not be used up to their capacity, but the unused fraction can be kept very small. 2.2 The delay issue Since packets are dropped when their delay overcame the required threshold, it is important, for the effectiveness of the scheme, to derive some conservative peak delay estimate to be used at the set up phase. To this purpose we use an nD/D/1 queuing model where the n sources generate service requests at a constant inter-arrival time equal to T [5][6]. To obtain a conservative estimate under any network load condition, we evaluate the delay suffered when the utilization factor is close to one. Using the approach in [5], we have considered three cases in which the channel capacity is M = 25,50,100 connections of the same rate. The average waiting plus transmission delay suffered by the packets of a connection when all connections are active is shown in Table I. The delays are expressed in transmission time units (m), in interarrival time units (m'), in milliseconds (m'') assuming T=30 ms (which can model 32 Kb/s voice channels and 1000 bit packets), and in milliseconds (m''') assuming T=1 ms (which can model 1 Mb/s channels Borgonovo Expires:02/99 [Page 5] INTERNET-DRAFT 29 July 1998 and 1000 bit packets). Table I. --------------------------------------------------------- | M | m(D) | s(D) | m'(T) | m"(ms) | m"'(ms) | | | | | |(T=30 ms) | (T=1 ms) | ------------------------------------------------------- - | 25 | 3.51 | 1.52 | 0.140 | 4.21 | 0.140 | | 50 | 4.88 | 2.09 | 0.0977 | 2.93 | 0.0977 | | 100 | 6.85 | 2.79 | 0.0685 | 2.05 | 0.0685 | ------------------------------------------------------- - Column two shows that, for any link bandwidth, absolute delays decrease when the size of connections increases. For the case in which sources have different, though constant, rates no general solution exists. However, it is expected that the replacing of some lower rate connections with an equivalent high rate connection will not impair performance since the high rate connection generates a more regular arrival pattern than the slower connections replaced. This conjecture is substantiated by our simulation results, therefore we assume that in an environment with mixed rate sources a conservative delay bound is attained by assuming that all connections are of the smallest allowed rate. Column four shows that if delay is measured in interarrival times, the delay decreases as the number of connections increases. This means that if a lower bound to the capacity of the path is used for delay evaluations, an upper bound is guaranteed. Finally, a conservative estimate on the connection end-to-end delay can be attained by assuming that delays add hop-by-hop as independent random variables. Also this assumption is conservative as the pipeline effect along the connection path reduces the queuing delay at nodes other than the first. Thus, the peak delay evaluation of a connection with k hops can be attained assuming a normal distribution for the total delay. Table II shows three examples of peak delay evaluations using the values in Table I. The first two are based on a minimum allowed rate of 33 packet/sec (e.g. voice channels at 32 kb/s with 30 ms interarrival time), and assuming that at least either 100 or 25 connections can be accommodated along an 8 hop path. The third is based on a minimum allowed rate of 1 Mb/s with 1 ms interarrival time, representing the case for voice trunk channels within a provider domain, and assuming that at least 25 connections can be accommodated along an 8 hop path. The results shown refer only to class 2 traffic. Class 1 traffic (scout packets) has very little influence on the delay since it can delay class 2 packets for at most one transmission time, because of Borgonovo Expires:02/99 [Page 6] INTERNET-DRAFT 29 July 1998 the non-preemptive priority. Class 0 packets may alter the analysis shown if they are allowed a size considerably larger than the constant rate packets. Table II. - -------------------------------------------------------------- | rate | mean delay | Standard deviation | 0.999 percentile | | capacity| (ms) | (ms) | (ms) | - -------------------------------------------------------------- | 32 kb/s | | | | | (100) | 16.4 | 1.58 | 21.2 | | 32 kb/s | | | | | (25) | 33.7 | 5.17 | 49.3 | | 1 Mb/s | | | | | (25) | 1.12 | 0.172 | 1.64 | ---------------------------------------------------------------- The set-up procedure uses the values indicated in Table I to evaluate the 0.999 percentile, which depends on the number of hops traversed, and to determine whether the delay QoS is met. Note, however, that due to the strong correlation among packets of the same connection, the fraction 0.001 does not represent the packet dropping probability suffered by any connection, but it represents the fraction of connections that suffer loss of packets. 3. Measures Preliminary simulation results have been obtained by simulating an 8 node network, interconnected by a unidirectional and homogeneous ring structure. Equal rate traffic is generated at any nodes, and destination nodes are chosen either 1 or 8 hops apart in the ratio 12 to 1, so that at any node a consistent fraction of traffic (about 60%) is renewed. With this structure the complexity of the simulation environment is kept low while observing sufficiently long paths with limited pipeline effect, a most critical condition. Table III. ------------------------------------------------------------------- | connection |pck.dropping| delay thresholds (ms) | average| | rate | classes | | delay | | 1 Mb/s | | 1 | 1.1| 1.2| 1.3| 1.4|1.5| 1.11 | | 32 Kb/s | |30 | 33 | 36 | 39 | 42 | 45| 33.3 | | ----------------------------------------------------------------- | | 0 - 0.001 | 0 |0.084|0.167|0.417|0.75| 1 | | | |0.001-0.01 | 0 | 0 | 0 | 0 | 0 | 0 | | | |0.01 - 0.1 | 0 | 0 | 0 | 0 | 0 | 0 | | | | 0.1 - 1 | 1 |0.916|0.833|0.583|0.25| 0 | | ----------------------------------------------------------------- Borgonovo Expires:02/99 [Page 7] INTERNET-DRAFT 29 July 1998 In our simulations the network has been loaded one connection at a time, until saturation is reached, using the call set-up mechanism described in the previous sections. In Table III we report, for a few delay thresholds, the percentage of 8 hop connections that experienced a packet dropping probability (i.e. a delay greater than the threshold) within the class indicated in the first column. The average delay is reported in the last column. The capacity of the links is assumed 25 times the bandwidth required by each connection. The bimodal behavior of the distribution in Table III confirms that a connection is either good or bad. Furthermore, the delay threshold with no packet dropping is within the bound given in Table II. 4. References [1] K. Nichols, V. Jacobson, L. Zhang, ``A Two-bit Differentiated Services Architecture for the Internet'', IETF Internet Draft, Nov, 1997. [2] R. Braden, L. Zhang, S. Berson, S. Herzog, S. Jamin, ``Resource ReSerVation Protocol (RSVP)-Version 1 Functional Specification''IETF Request For Comments 2205, Sep. 1997. [3] P.P White, ``RSVP and Integrated Services in the Internet: A Tutorial'', IEEE Communication Magazine, vol. 35, no. 5, May 1997,pag. 100. [4] F. Borgonovo and L. Fratta, `` Deflection Networks: Architectures for Metropolitan and Wide Area Networks'', Computer Networks and ISDN Systems, Vol. 24, No. 2, April 1992, pp.171-183. [5] A. E. Eckberg, "The single server queue with periodic arrival process and deterministic service time", IEEE Trans. on Comm., Vol. COM-27, pp. 556-562, 1979. [6] G. Ramamurthy, B. Sengupta, "Delay analysis of the packet voice multiplexer by the SD_i/D/1 queue", IEEE Trans. on Comm., Vol. COM- 39, no. 7, July 1991. Borgonovo Expires:02/99 [Page 8] INTERNET-DRAFT 29 July 1998 5. Authors' Addresses Flaminio Borgonovo Dipartimento di Elettronica e Informazione Politecnico di Milano P.zza L. da Vinci 32, 20133 MILANO, Italy Email: borgonov@elet.polimi.it Fax: +39 02 2399 3413 http://www.elet.polimi.it/people/borgonov/ Luigi Fratta Dipartimento di Elettronica e Informazione Politecnico di Milano P.zza L. da Vinci 32, 20133 MILANO, Italy Email: fratta@elet.polimi.it Fax: +39 02 2399 3413 http://www.elet.polimi.it/people/fratta/ Antonio Capone Dipartimento di Elettronica e Informazione Politecnico di Milano P.zza L. da Vinci 32, 20133 MILANO, Italy Email: capone@elet.polimi.it Fax: +39 02 2399 3413 http://www.elet.polimi.it/people/capone/ Mario Marchese Dipartimento di Elettronica e Informazione Politecnico di Milano P.zza L. da Vinci 32, 20133 MILANO, Italy Email: mmarches@elet.polimi.it Fax: +39 02 2399 3413 Chiara Petrioli Dipartimento di Elettronica e Informazione Politecnico di Milano P.zza L. da Vinci 32, 20133 MILANO, Italy Email: chiara@cerbero.elet.polimi.it Fax: +39 02 2399 3413