idnits 2.17.1 draft-borgonovo-qos-ds-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Cannot find the required boilerplate sections (Copyright, IPR, etc.) in this document. Expected boilerplate is as follows today (2024-04-26) according to https://trustee.ietf.org/license-info : IETF Trust Legal Provisions of 28-dec-2009, Section 6.a: This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 2: Copyright (c) 2024 IETF Trust and the persons identified as the document authors. All rights reserved. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 3: This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Missing expiration date. The document expiration date should appear on the first and last page. ** The document seems to lack a 1id_guidelines paragraph about Internet-Drafts being working documents. ** The document seems to lack a 1id_guidelines paragraph about 6 months document validity. ** The document seems to lack a 1id_guidelines paragraph about the list of current Internet-Drafts. ** The document seems to lack a 1id_guidelines paragraph about the list of Shadow Directories. == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack a Security Considerations section. ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** There are 165 instances of weird spacing in the document. Is it really formatted ragged-right, rather than justified? Miscellaneous warnings: ---------------------------------------------------------------------------- == Line 6 has weird spacing: '...tecnico di Mi...' == Line 14 has weird spacing: '... This docum...' == Line 15 has weird spacing: '...cuments of th...' == Line 16 has weird spacing: '... and its wo...' == Line 17 has weird spacing: '...working docum...' == (160 more instances...) -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (29 July 1998) is 9403 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Possible downref: Non-RFC (?) normative reference: ref. '1' -- Possible downref: Non-RFC (?) normative reference: ref. '3' -- Possible downref: Non-RFC (?) normative reference: ref. '4' -- Possible downref: Non-RFC (?) normative reference: ref. '5' -- Possible downref: Non-RFC (?) normative reference: ref. '6' Summary: 10 errors (**), 0 flaws (~~), 7 warnings (==), 7 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Internet Engineering Task Force Flaminio Borgonovo 2 INTERNET-DRAFT Antonio Capone 3 Expires: February 1999 Luigi Fratta 4 Mario Marchese 5 Chiara Petrioli 6 Politecnico di Milano 7 29 July 1998 9 End-to-end QoS provisioning mechanism for Differentiated Services 10 12 Status of this Memo 14 This document is an Internet-Draft. Internet-Drafts are working 15 documents of the Internet Engineering Task Force (IETF), its areas, 16 and its working groups. Note that other groups may also distribute 17 working documents as Internet-Drafts. Internet-Drafts are draft 18 documents valid for a maximum of six months and may be updated, 19 replaced, or obsoleted by other documents at any time. It is 20 inappropriate to use Internet-Drafts as reference material or to cite 21 them other than as ``work in progress.'' 23 To view the entire list of current Internet-Draft, please check the 24 ``1id-abstracts.txt'' listing contained in the Internet-Drafts Shadow 25 Directories on ftp.is.co.za (Africa), ftp.nordu.net (Northern 26 Europe), ftp.nis.garr.it (Southern Europe), munnari.oz.au (Pacific 27 Rim), ftp.ietf.org (US East Coast), or ftp.isi.edu (US West Coast). 29 Abstract 31 This document presents an end-to-end mechanism to guarantee bandwidth 32 and delay into the Differentiated Services mechanism to constant rate 33 traffic such as voice and video. The mechanism requires network 34 routers to be able to serve packets according to three classes of 35 priority. The needed call admission control is performed by an end- 36 to-end signaling procedure that implicitly looks for the required 37 bandwidth and seizes it, if available. Short delays are guaranteed by 38 the regular structure of constant rate traffic. No entities other 39 than source and destination are involved and multicast operation 40 comes at no further cost, which makes the mechanism fully scalable 41 and integrable into the existing Internet. 43 1. Introduction 45 The transport mechanism capable of guaranteeing demanding Quality of 46 Service (QoS) requirements is under discussion in the INTERNET 47 community. The Differentiated Services architecture [1] is the 48 approach that has recently gained more credit. The goal is to offer 49 an alternative to carry voice, video and multimedia with respect to 50 classic Telephone/ISDN and ATM networks. The basic problem is how to 51 guarantee bandwidth, delay and packet dropping probability, in a 52 datagram network architecture where the only service is the Best 53 Effort packet transmission. 55 In this contribution we consider only approaches that can be 56 completely implemented at the IP level and do not assume any lower 57 level QoS guarantee capability. In this context, an existing approach 58 is represented by RSVP (Resource reSerVation Protocol) [2][3]. 60 RSVP is a signaling mechanism among routers and hosts that includes 61 support to ``flows'' of packets with different QoS and the ability to 62 dedicate end-to-end capacity to real-time traffic by means of hop-by- 63 hop resource reservation protocols. In practice, this solution 64 changes the entire network architecture by relying on the virtual 65 circuit connection mechanism, the paradigm of the telephony world, 66 today extended to the B-ISDN. During the set-up phase, needed to 67 install a virtual circuit, the network nodes cooperate, using complex 68 protocols, to determine a path within the network and to reserve 69 network resources such as bandwidth and buffers. The implementation 70 of such a signaling and its related features over the layered 71 structure of a pure datagram network will require large investments 72 because of the heavy software and hardware modifications to be 73 introduced in the already worldwide installed networks. 75 A much simpler alternative is represented by the Differentiated 76 Services approach. The basic idea is to use the IPv4 header TOS bits 77 or the IPv6 Traffic Class octet, the "DS byte" to designate the 78 "per-hop behaviors" that packets are to receive. By carefully 79 aggregating a multitude of QoS-enabled flows into a reasonable number 80 of differentiated services offered by the network it is no longer 81 necessary to recognize and store information about each individual 82 flow in the core routers. Though some signaling mechanism is needed 83 to manage the service assignment to individual flows, the network 84 mechanism still remains purely datagram and scales well. However, 85 since the control on packets is performed hop-by-hop, it is not easy 86 to design a suitable call acceptance policy that is able to guarantee 87 end-to-end QoS. 89 As the result of our research work in this field we have gained the 90 belief that if one only wants to enforce QoS control over constant- 91 rate or almost-constant-rate streams, simple procedures based on non- 92 preemptive priority mechanisms and simple end-to-end signaling 93 procedures are effective. One such procedure has been investigated in 94 the framework of deflection networks, i.e., data networks with very 95 small or no queuing at nodes [4]. 97 The Bandwidth Guaranteed Service (BGS) mechanism, presented in this 98 document, guarantees constant rate traffic bandwidth and delay 99 requirements in datagram networks such as the Internet. BGS is based 100 on three priority levels. It integrates and completes the DS approach 101 and allows a QoS control as in RSVP, without adding explicit 102 signaling protocols. No entities other than source and destination 103 which makes the mechanism fully scalable. 105 The document is organized as follows. In Section 2 we present BGS, 106 its call setup and call acceptance procedures, while Section 3 107 illustrates its behavior by means of some preliminary results 108 obtained by simulation. 110 2. The BGS mechanism 112 In the following we assume connections with constant rate packet 113 traffic. The jitter introduced by the network is eliminated at the 114 destination user by storing the packets in a play-out buffer which is 115 emptied at the constant nominal rate, starting with a delay D_b after 116 the reception of the first packet of the connection. With this 117 technique the total delivery delay experienced by packets is constant 118 and equal to 120 W = D_b+d_1 (1) 122 where d_1 is the network delay suffered by the first packet. If a 123 packet is delayed more than W, it is useless and is dropped. 124 Therefore the QoS guaranteed traffic requires, besides the bandwidth 125 B, also a maximum packet delay W and a maximum packet-dropping 126 percentage gamma. 128 The BGS mechanism requires that each packet in the network belongs to 129 one of the three following priority classes. 131 Class 0: (lowest priority) if the packet requests best effort 132 service; 134 Class 1: (intermediate priority) if the packet is a scout packet, 135 used in the set-up procedure as defined below; 137 Class 2: (highest priority) if the packet belongs to a constant ate 138 flow that has been granted guaranteed service. 140 The priority information is carried in the TOS field and is used by 141 the routers to serve all packets according to a non-preemptive head- 142 of-the-line priority scheme. Class 1 and 2 packets have the same 143 constant length. 145 The set-up procedure operates end-to-end and is activated when a new 146 connection, characterized by the bandwidth B and the maximum allowed 147 transfer delay W, is requested. 149 Upon reception of a connection request C_j addressed to NODE_B, 150 NODE_A immediately starts transmitting scout packets at the rate r_j 151 corresponding to the requested bandwidth. 153 The scout packets do not carry data traffic in the payload, since 154 network. To this purpose they only include set-up information to 155 signal to the receiving NODE_B the request for an incoming call and 156 the related service quality parameters. 158 Upon receiving the first scout packet, NODE_B starts performing 159 bandwidth measures and delay evaluations to verify whether QoS 160 requirements are met. If the outcome is positive NODE_B sends a call 161 acceptance packet to NODE_A. Otherwise, either it rejects the 162 connection or starts a bandwidth negotiation procedure with NODE_A. 164 As far as NODE_A is concerned, it keeps on transmitting scout packets 165 until either a time-out occurs or a response from NODE_B is received. 166 If the time out expires or the response is negative the call is 167 aborted, meaning that the bandwidth has not been found. If a positive 168 response is received, the connection set-up phase ends and NODE_A 169 replaces scout packets with data packets. The bandwidth is 170 automatically released when packets transmission ends. 172 The priority scheme adopted guarantees that new connections can not 173 steal bandwidth to already established ones. In fact, if some 174 constant bandwidth connections have already been admitted, as soon as 175 new connections attempt to steal bandwidth on a link, old connections 176 are delayed, a queue builds up and the priority mechanism cuts out 177 the newly arrived scout packets. 179 2.1 Call acceptance procedure 181 The call acceptance procedure is directly performed by the 182 destination node and is very simple: a new guaranteed-bandwidth 183 connection is accepted only if the connection parameters measured on 184 the N scout packets satisfy the QoS constraints. 186 First, a test of significance on the Hypothesis H0 that the bandwidth 187 requirement is satisfied is performed on the sample X_1, X_2, ..., 188 X_(N-1), where X_i is the interarrival time between scout packet i 189 and i+1. Under the hypothesis H0 we have E[X]=T, being $1/T$ the 190 packet constant rate of each flow. So, the test can be exploited on 191 the sample average 193 M_X = (X_1+X_2+...+X_(N-1))/(N-1) (2) 195 which is assumed to be normally distributed with average T and 196 variance 198 S2_x =[(X_1-T)*(X_1-T)+...+(X_(N-1)-T)*(X_(N-1)-T)]/(N-1) (3) 200 So, for a given confidence level alpha, a threshold T_alpha exists 201 such that if M_X < T_alpha the hypothesis H_0 is accepted. The 202 threshold value can be obtained as 203 where xi_alpha is the standard normal deviate that is exceeded with 204 probability 1 - alpha. The difference 206 Delta B = 1/T - 1/T_alfa (5) 208 represents the resolution power of the measure. 210 The precision of the estimate increases with the number of 211 statistically independent samples. In a network that carries periodic 212 packet streams, delay samples can be considered independent if taken 213 at a distance larger than the transmission period T_max of the 214 connection with the lowest admissible bandwidth. Thus, the set-up 215 period is determined in time rather than by the number of signaling 216 packets. By doing this we guarantee that the measure captures all the 217 existing traffics, including the slowest. 219 For example, if we assume that the lowest bandwidth corresponds to 32 220 Kb/s with 640 bit packets, the packet transmission time is 20 ms so 221 that a measure period of 1-2 seconds is needed to collect a 222 reasonable number (50-100) of samples. 224 The measure indicated above may be critical since, due to the error 225 (5), the connection could be accepted even if the required bandwidth 226 slightly exceeds the available one. In this case, more traffic than 227 the capacity is accepted and all connections would be affected. A 228 simple way to avoid this unwanted phenomenon is to scout for more 229 bandwidth than needed in the set-up phase, and to turn to the 230 required bandwidth once the call is accepted. With this modification 231 links can not be used up to their capacity, but the unused fraction 232 can be kept very small. 234 2.2 The delay issue 236 Since packets are dropped when their delay overcame the required 237 threshold, it is important, for the effectiveness of the scheme, to 238 derive some conservative peak delay estimate to be used at the set up 239 phase. To this purpose we use an nD/D/1 queuing model where the n 240 sources generate service requests at a constant inter-arrival time 241 equal to T [5][6]. 243 To obtain a conservative estimate under any network load condition, 244 we evaluate the delay suffered when the utilization factor is close 245 to one. 247 Using the approach in [5], we have considered three cases in which 248 the channel capacity is M = 25,50,100 connections of the same rate. 249 The average waiting plus transmission delay suffered by the packets 250 of a connection when all connections are active is shown in Table I. 251 The delays are expressed in transmission time units (m), in 252 interarrival time units (m'), in milliseconds (m'') assuming T=30 ms 253 (which can model 32 Kb/s voice channels and 1000 bit packets), and in 254 and 1000 bit packets). 256 Table I. 257 --------------------------------------------------------- 258 | M | m(D) | s(D) | m'(T) | m"(ms) | m"'(ms) | 259 | | | | |(T=30 ms) | (T=1 ms) | 260 ------------------------------------------------------- - 261 | 25 | 3.51 | 1.52 | 0.140 | 4.21 | 0.140 | 262 | 50 | 4.88 | 2.09 | 0.0977 | 2.93 | 0.0977 | 263 | 100 | 6.85 | 2.79 | 0.0685 | 2.05 | 0.0685 | 264 ------------------------------------------------------- - 266 Column two shows that, for any link bandwidth, absolute delays 267 decrease when the size of connections increases. For the case in 268 which sources have different, though constant, rates no general 269 solution exists. However, it is expected that the replacing of some 270 lower rate connections with an equivalent high rate connection will 271 not impair performance since the high rate connection generates a 272 more regular arrival pattern than the slower connections replaced. 273 This conjecture is substantiated by our simulation results, therefore 274 we assume that in an environment with mixed rate sources a 275 conservative delay bound is attained by assuming that all connections 276 are of the smallest allowed rate. 278 Column four shows that if delay is measured in interarrival times, 279 the delay decreases as the number of connections increases. This 280 means that if a lower bound to the capacity of the path is used for 281 delay evaluations, an upper bound is guaranteed. 283 Finally, a conservative estimate on the connection end-to-end delay 284 can be attained by assuming that delays add hop-by-hop as independent 285 random variables. Also this assumption is conservative as the 286 pipeline effect along the connection path reduces the queuing delay 287 at nodes other than the first. Thus, the peak delay evaluation of a 288 connection with k hops can be attained assuming a normal distribution 289 for the total delay. 291 Table II shows three examples of peak delay evaluations using the 292 values in Table I. The first two are based on a minimum allowed rate 293 of 33 packet/sec (e.g. voice channels at 32 kb/s with 30 ms 294 interarrival time), and assuming that at least either 100 or 25 295 connections can be accommodated along an 8 hop path. 297 The third is based on a minimum allowed rate of 1 Mb/s with 1 ms 298 interarrival time, representing the case for voice trunk channels 299 within a provider domain, and assuming that at least 25 connections 300 can be accommodated along an 8 hop path. 302 The results shown refer only to class 2 traffic. Class 1 traffic 303 (scout packets) has very little influence on the delay since it can 304 the non-preemptive priority. Class 0 packets may alter the analysis 305 shown if they are allowed a size considerably larger than the 306 constant rate packets. 308 Table II. 309 - -------------------------------------------------------------- 310 | rate | mean delay | Standard deviation | 0.999 percentile | 311 | capacity| (ms) | (ms) | (ms) | 312 - -------------------------------------------------------------- 313 | 32 kb/s | | | | 314 | (100) | 16.4 | 1.58 | 21.2 | 315 | 32 kb/s | | | | 316 | (25) | 33.7 | 5.17 | 49.3 | 317 | 1 Mb/s | | | | 318 | (25) | 1.12 | 0.172 | 1.64 | 319 ---------------------------------------------------------------- 321 The set-up procedure uses the values indicated in Table I to evaluate 322 the 0.999 percentile, which depends on the number of hops traversed, 323 and to determine whether the delay QoS is met. 325 Note, however, that due to the strong correlation among packets of 326 the same connection, the fraction 0.001 does not represent the packet 327 dropping probability suffered by any connection, but it represents 328 the fraction of connections that suffer loss of packets. 330 3. Measures 332 Preliminary simulation results have been obtained by simulating an 8 333 node network, interconnected by a unidirectional and homogeneous ring 334 structure. Equal rate traffic is generated at any nodes, and 335 destination nodes are chosen either 1 or 8 hops apart in the ratio 12 336 to 1, so that at any node a consistent fraction of traffic (about 337 60%) is renewed. With this structure the complexity of the simulation 338 environment is kept low while observing sufficiently long paths with 339 limited pipeline effect, a most critical condition. 341 Table III. 342 ------------------------------------------------------------------- 343 | connection |pck.dropping| delay thresholds (ms) | average| 344 | rate | classes | | delay | 345 | 1 Mb/s | | 1 | 1.1| 1.2| 1.3| 1.4|1.5| 1.11 | 346 | 32 Kb/s | |30 | 33 | 36 | 39 | 42 | 45| 33.3 | 347 | ----------------------------------------------------------------- 348 | | 0 - 0.001 | 0 |0.084|0.167|0.417|0.75| 1 | | 349 | |0.001-0.01 | 0 | 0 | 0 | 0 | 0 | 0 | | 350 | |0.01 - 0.1 | 0 | 0 | 0 | 0 | 0 | 0 | | 351 | | 0.1 - 1 | 1 |0.916|0.833|0.583|0.25| 0 | | 352 ----------------------------------------------------------------- 353 In our simulations the network has been loaded one connection at a 354 time, until saturation is reached, using the call set-up mechanism 355 described in the previous sections. In Table III we report, for a few 356 delay thresholds, the percentage of 8 hop connections that 357 experienced a packet dropping probability (i.e. a delay greater than 358 the threshold) within the class indicated in the first column. The 359 average delay is reported in the last column. The capacity of the 360 links is assumed 25 times the bandwidth required by each connection. 362 The bimodal behavior of the distribution in Table III confirms that a 363 connection is either good or bad. Furthermore, the delay threshold 364 with no packet dropping is within the bound given in Table II. 366 4. References 368 [1] K. Nichols, V. Jacobson, L. Zhang, ``A Two-bit Differentiated 369 Services Architecture for the Internet'', IETF Internet Draft, Nov, 370 1997. 372 [2] R. Braden, L. Zhang, S. Berson, S. Herzog, S. Jamin, ``Resource 373 ReSerVation Protocol (RSVP)-Version 1 Functional Specification''IETF 374 Request For Comments 2205, Sep. 1997. 376 [3] P.P White, ``RSVP and Integrated Services in the Internet: A 377 Tutorial'', IEEE Communication Magazine, vol. 35, no. 5, May 378 1997,pag. 100. 380 [4] F. Borgonovo and L. Fratta, `` Deflection Networks: Architectures 381 for Metropolitan and Wide Area Networks'', Computer Networks and ISDN 382 Systems, Vol. 24, No. 2, April 1992, pp.171-183. 384 [5] A. E. Eckberg, "The single server queue with periodic arrival 385 process and deterministic service time", IEEE Trans. on Comm., Vol. 386 COM-27, pp. 556-562, 1979. 388 [6] G. Ramamurthy, B. Sengupta, "Delay analysis of the packet voice 389 multiplexer by the SD_i/D/1 queue", IEEE Trans. on Comm., Vol. COM- 390 39, no. 7, July 1991. 392 5. Authors' Addresses 394 Flaminio Borgonovo 395 Dipartimento di Elettronica e Informazione 396 Politecnico di Milano 397 P.zza L. da Vinci 32, 398 20133 MILANO, Italy 399 Email: borgonov@elet.polimi.it 400 Fax: +39 02 2399 3413 401 http://www.elet.polimi.it/people/borgonov/ 403 Luigi Fratta 404 Dipartimento di Elettronica e Informazione 405 Politecnico di Milano 406 P.zza L. da Vinci 32, 407 20133 MILANO, Italy 408 Email: fratta@elet.polimi.it 409 Fax: +39 02 2399 3413 410 http://www.elet.polimi.it/people/fratta/ 412 Antonio Capone 413 Dipartimento di Elettronica e Informazione 414 Politecnico di Milano 415 P.zza L. da Vinci 32, 416 20133 MILANO, Italy 417 Email: capone@elet.polimi.it 418 Fax: +39 02 2399 3413 419 http://www.elet.polimi.it/people/capone/ 421 Mario Marchese 422 Dipartimento di Elettronica e Informazione 423 Politecnico di Milano 424 P.zza L. da Vinci 32, 425 20133 MILANO, Italy 426 Email: mmarches@elet.polimi.it 427 Fax: +39 02 2399 3413 429 Chiara Petrioli 430 Dipartimento di Elettronica e Informazione 431 Politecnico di Milano 432 P.zza L. da Vinci 32, 433 20133 MILANO, Italy 434 Email: chiara@cerbero.elet.polimi.it 435 Fax: +39 02 2399 3413