idnits 2.17.1 draft-mercankosk-diffserv-pdb-vw-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** The document seems to lack a 1id_guidelines paragraph about Internet-Drafts being working documents. ** The document is more than 15 pages and seems to lack a Table of Contents. == The page length should not exceed 58 lines per page, but there was 27 longer pages, the longest (page 1) being 59 lines 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. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year == The document doesn't use any RFC 2119 keywords, yet seems to have RFC 2119 boilerplate text. -- 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 (July 2000) is 8679 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- ** Obsolete normative reference: RFC 2598 (ref. '3') (Obsoleted by RFC 3246) Summary: 7 errors (**), 0 flaws (~~), 3 warnings (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Differentiated Services Working Group G. Mercankosk 3 Internet Draft Australian 4 Expires January 2001 Telecommunications 5 CRC 6 Document: draft-mercankosk-diffserv-pdb-vw-00.txt July 2000 7 Category: Informational 9 The Virtual Wire Per Domain behavior _ Analysis and Extensions 10 draft-mercankosk-diffserv-pdb-vw-00.txt 12 Status of this Memo 14 This document is an Internet-Draft and is in full conformance with 15 all provisions of Section 10 of RFC2026 [1]. Internet-Drafts are 16 working documents of the Internet Engineering Task Force (IETF), its 17 areas, and its working groups. Note that other groups may also 18 distribute working documents as Internet-Drafts. 20 Internet-Drafts are draft documents valid for a maximum of six 21 months and may be updated, replaced, or obsoleted by other documents 22 at any time. It is inappropriate to use Internet-Drafts as reference 23 material or to cite them other than as "work in progress." 25 The list of current Internet-Drafts can be accessed at 26 http://www.ietf.org/ietf/1id-abstracts.txt 27 The list of Internet-Draft Shadow Directories can be accessed at 28 http://www.ietf.org/shadow.html. 30 Distribution of this memo is unlimited. 32 Abstract 34 This document provides an analysis of the Virtual Wire Per Domain 35 Behavior with limited extensions. 37 The draft formalizes a model for the PDB by explicitly identifying 38 key timing and decision variables and associated design parameters. 39 It derives the necessary and sufficient conditions for creating and 40 establishing a Virtual Wire flow. It provides methods for 41 quantifying design parameters and setting decision parameters and 42 discusses their extensions to incorporate variations in traffic 43 characteristics. 45 A pdf version of this document is available at 46 http://www.ee.uwa.edu.au/~guven/vwpdb.pdf 48 Mercankosk Informational - Jan 2001 1 49 1. Introduction 51 The document [3] describes a Differentiated Services (diffserv or 52 DS) Per Hop Behavior (PHB) called Expedited Forwarding (EF) intended 53 for use in building a scalable edge-to-edge service that appears to 54 the end points like an un-shared, point-to-point connection or 55 `Virtual Wire.' For scalability, a DS-domain supplying this service 56 must be completely unaware of the individual end points using it, 57 except for routing purposes, and sees only the aggregate EF marked 58 traffic entering and traversing the domain. 60 The document [4] provides a set of specifications necessary on the 61 aggregate traffic (in DS terminology, a Per Domain Behavior or PDB) 62 in order to meet these requirements and thus defines a new PDB, the 63 `Virtual Wire' PDB of some fixed capacity. It does not require `per- 64 flow' state to exist anywhere other than the ingress and egress 65 routers. Despite the lack of per-flow state, if the aggregate input 66 rates are appropriately policed and the EF service rates on interior 67 links are appropriately configured, the edge-to-edge service 68 supplied by the DS-domain will be indistinguishable from that 69 supplied by a dedicated wire between the end points. 71 This document provides an analysis of `Virtual Wire' PDB with 72 limited extensions. "The same as a dedicated wire," means that as 73 long as packets are sourced at a rate less than or equal to the 74 virtual wire's configured rate, they will be delivered with a high 75 degree of assurance and with no distortion (apart from line clock 76 jitter) of the inter-packet timing imposed by the source. However, 77 any packet sourced at a rate greater than the virtual wire's 78 configured rate will either be unconditionally discarded or spaced 79 to conform with the configured rate. In the latter case, the packets 80 will be delivered with inter-packet timing imposed by the spacer. 82 This draft formalizes a model for the `Virtual Wire' PDB by 83 explicitly identifying key timing and decision variables and 84 associated design parameters. It derives the necessary and 85 sufficient conditions for creating and establishing a `Virtual Wire' 86 flow. It provides methods for quantifying design parameters and 87 setting decision parameters and discusses their extensions to 88 incorporate variations in traffic characteristics. 90 In this document, we distinguish between the transfer delay over a 91 DS-domain and edge-to-edge service delay. We provide a 92 characterization of the transfer delay bound based on established 93 results. We argue that the issue of non-EF traffic starvation does 94 not exist even when priority queueing is deployed. We point out that 95 the presence of non-EF micro flows does not necessitate additional 96 bandwidth resources. We determine a conservative expected time to 97 the first failure of a `Virtual Wire.' We discuss the impact of 98 heterogeneous packet lengths on the transfer delay bound. 100 This document provides a synthesis of various methods in delivering 101 a particular but versatile solution. The issue of scalability, the 103 Mercankosk Informational - Jan 2001 2 104 edge-to-edge service characteristics and a simple management of DS- 105 domain provide the basis for the presented solution. 107 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 108 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in 109 this document are to be interpreted as described in RFC-2119 [2]. 111 2. Description of Virtual Wire PDB with extensions 113 Figure 1: An illustration of virtual wire transfer over a DS-domain 115 An illustration of the model of a Virtual Wire transfer over a DS- 116 domain is given in Figure 1. At the ingress end of the micro flow, 117 the model contains an ingress link (S to I) and a DS-domain ingress 118 border router (at I). Over the DS-domain (I to E), the packets from 119 the micro flow are subject to random delays, according to EF-PHB 120 service. At the egress end of the flow, the remaining components of 121 the model are a DS-domain egress border router (at E) and an egress 122 link (E to D). The ingress link and the egress link are assumed to 123 run at the same constant rate as the virtual wire rate R with 124 negligible line clock jitter. 126 2.1 Ingress edge of DS-domain 128 A periodic flow of packets of size S is sourced at a rate R on the 129 ingress link. Accordingly, one packet is presented at the DS-domain 130 ingress border router in every T=S/R time units. The number of 131 complete packets that are in transit in the DS-domain at time t is 132 denoted by N_DS(t). Without loss of generality, we choose the time 133 origin such that the last bit of the first packet presented at the 134 ingress border router is at time T. Let t_k represent the time at 135 which the last bit of the kth packet is presented to the DS-domain 136 at the ingress border router, then 138 (1) t_k = kT. 140 2.2 Over the DS-domain 142 Once a packet that belongs to a micro flow is presented at the 143 ingress border router, it hops from one EF router to another along 144 its path over the DS-domain before reaching the egress border 145 router. There are two main components for the delay experienced by a 146 packet over the DS-domain, namely the propagation delay and the 147 queueing delay. The propagation delay refers to the time it would 148 take for a packet to traverse through the DS-domain if the packet 149 experienced no queueing delay along its path. Accordingly, the 150 propagation delay, d_p, is fixed and includes the time necessary to 151 process a packet at routers. Let d_k denote the total queueing delay 152 experienced by the kth packet along its path. It is assumed that the 153 queueing delay experienced by each packet of a micro flow over the 154 DS-domain is statistically bounded by a known value, D, that is 156 (2) 0 <= d_k < D 158 Mercankosk Informational - Jan 2001 3 159 The value, D, can be obtained by some (1-alpha) quantile of the 160 total queueing delay. Note that the value D refers to the difference 161 between the best and the worst case expectation of the packet 162 transfer delay. The best case is equal to d_p and the worst case is 163 equal to d_p + D, a value likely to be exceeded with a probability 164 less than alpha. Therefore, the value D is a measure of variation of 165 the delay distribution and may be referred to as expected maximum 166 jitter. 168 At a given EF-router, let C generically denote the capacity of the 169 output link associated with the micro flow. The transmission time 170 delta of a size S packet onto the output link is given by S/C time 171 units. Finally, let f denote the fraction of the output link 172 capacity C as the target operating point for the aggregate EF flow 173 at a given node. 175 Also let tau_k denote the time at which the last bit of the kth 176 packet reaches the egress border router. So we have 178 (3) tau_k = t_k + d_k + d_p 180 2.3 Egress edge of DS-domain 182 The packets that arrive at the egress border router are placed in a 183 micro flow specific buffer of size B_E. The number of complete 184 packets in the egress buffer at time t is denoted by N_E(t). Similar 185 to the ingress link, one packet is transmitted onto the egress link 186 in every T time units. It is clear that the timing structure of the 187 sequence {tau_k} is not necessarily the same as that of the sequence 188 {t_k}. A commonly used strategy for recovering the initial timing 189 structure is to delay the transmission of the first packet onto the 190 egress link by a fixed amount of time, say D_xi, and set the size of 191 the egress buffer B_E such that the continuity of the data flow is 192 maintained when packets are transmitted onto the egress link using 193 the very same timing structure {t_k}. We note that a micro flow 194 specific buffer at the egress border router is required even for the 195 original Virtual Wire [4]. Let xi_k denote the time at which the 196 first bit of the kth packet is transmitted onto the egress link. 197 Accordingly, we have 199 (4) xi_k = T + d_1 + d_p + D_xi + (k-1)T 201 3. Establishing a virtual wire 203 In Appendix B, we list a number of micro flow properties over a 204 virtual wire and express key micro flow quantities in terms of the 205 virtual wire rate R and the equalization delay D_xi. We observe that 206 the end-to-end delay experienced by each packet of the micro flow is 207 constant as it would be over a dedicated wire and given by 209 (5) xi_k - t_k = d_1 + d_p + D_xi 211 Mercankosk Informational - Jan 2001 4 212 We note that the end-to-end delay depends on the queueing delay d_1 213 experienced by the first packet, the propagation delay d_p over the 214 virtual wire, and the equalization delay D_xi at the egress border 215 router. We will later observe that, in establishing a virtual wire, 216 no explicit knowledge of d_1 and d_p is required. 218 In expressing the key micro flow quantities, we assume that buffers 219 over the DS-domain and at the egress border are sufficiently large 220 that they do not overflow. We also assume that the equalization 221 delay is made sufficiently large so that when the transmission of a 222 packet onto the egress link is completed, there is always another 223 packet in the egress buffer ready for transmission. 225 Continuity of micro flow requires that every packet presented to the 226 DS-domain at the ingress router at fixed intervals has to be 227 transmitted onto the egress link after a fixed delay but again at 228 the same fixed intervals, without being subject to packet loss or 229 interruption during the life time of the flow. Packet loss occurs if 230 a packet has to be discarded due to lack of storing capacity upon 231 arrival at the egress border router. On the other hand, the flow is 232 interrupted if a transmission cannot be started due to 233 unavailability of a packet at the egress border buffer. 235 In Appendix C, we show that having a bounded queueing delay over the 236 DS-domain, as indicated by (2), is sufficient to have maximum and 237 minimum limits on the egress border buffer fill N_E(t). Accordingly, 238 the egress buffer fill N_E(t) is bounded above by 239 ceiling((D+D_xi)/T) and below by floor((D_xi-D)/T) (definitions for 240 floor(x) and ceiling(x) are given in Appendix A). We then use these 241 limits to derive the necessary and sufficient conditions to maintain 242 the continuity of flow. In relation to avoiding egress link 243 starvation, we consider the situation where the first packet of the 244 flow experiences no queueing delay and some other packet experiences 245 a queueing delay arbitrarily close to the maximum D to obtain 247 (6) floor((D_xi-D)/T) >= 0 249 In relation to avoiding egress border buffer overflow however, we 250 consider the situation where the first packet experiences a queueing 251 delay arbitrarily close to the maximum D and some other packet 252 experiences no queueing delay to obtain 254 (7) ceiling((D+D_xi)/T) <= B_E 256 As indicated earlier, in determining the maximum queueing delay D, 257 the rarity of events has been taken into account. Accordingly, some 258 level of loss is allowed in case events considered rare do occur. 259 The conditions given in (6) and (7) ensure that there would be no 260 further losses. 262 The smallest value for D_xi that satisfies (6) is D. Setting the 263 initial delay as 265 (8) D_xi = D 267 Mercankosk Informational - Jan 2001 5 268 also minimizes the end-to-end delay over the DS-domain. The 269 resulting end-to-end delay is 271 (9) xi_k - t_k = xi_1 - T = d_1 + d_p + D 273 Now substituting (8) into (7), we have 275 (10) ceiling(2D/T) <= B_E 277 Consequently, the left hand side of the inequality in (10) 278 determines the minimum buffer size for egress border buffer as 280 (11) B_E = ceiling(2D/T) 282 4. Characterization of the delay bound 284 In Appendix D, we outline a general queueing model that forms the 285 basis for quantifying the transfer delay bound. We observe that, for 286 all practical purposes, the transfer delay bound is only a function 287 of aggregate traffic intensity and independent of individual micro 288 flow rates. We point out that strict ingress policing and resource 289 reservation ensure the delivery of rate guarantees to individual 290 micro flows. We also emphasize the non-ergodic nature of the problem 291 which is critical in determining the measure of interest. 293 In this section, we first look at the delay due to phase 294 coincidences with other micro flows. We next consider heterogeneous 295 micro flow rates in relation to the delay due to packets from the 296 same micro flow. We then summarize the methods of determining the 297 delay bound across the DS-domain. We finally consider servers taking 298 vacations upon becoming idle to examine the delay due to non-EF 299 micro flows. 301 4.1 Delay due to phase coincidences with other micro flows 303 The queueing model outlined in Appendix D is based on the 304 superposition of periodic micro flows. Given the strict ingress 305 policing to ensure a micro flow behavior given by (1), a nD/D/1 306 queue naturally arises provided that all contributing micro flows 307 have just joined in. Due to phase coincidences at a given router, a 308 micro flow cannot maintain the behavior given by (1) into the 309 successive routers along its path. However, we note that the work 310 associated with the micro flow remains unchanged. The deviation from 311 the nominal behavior, after a number of multiplexing stages, results 312 in the delay experienced by each packet of a micro flow being 313 additionally affected by the previous packets of that flow [10]. 314 Such an impact can be taken into account by considering an 315 additional flow into the queueing system. 317 As a limiting case, we observe that the delay distribution through 318 an (M+D)/D/1 queueing system always provides an upper bound for the 319 delay distribution through any nD/D/1 queue of the same aggregate 321 Mercankosk Informational - Jan 2001 6 322 intensity. We note, however, that the use of a conservative upper 323 bound does not alter the non-ergodic nature of the problem. 325 4.2 Delay due to packets from the same micro flow 327 In Appendix D, when the aggregate consists of micro flows of the 328 same rate, we note that a packet cannot be further delayed due to 329 packets from the micro flow that it belongs to. Yet, when the 330 aggregate consists of micro flows of different rates, this is not 331 necessarily correct. In particular, a packet from a high rate flow 332 may find itself queued behind packets from the same micro flow even 333 when all micro flows are perfectly periodic. 335 Referring to the numerical examples given in Appendix D, the 336 following observation can be made: The delay distribution for an 337 arbitrary aggregate traffic mix is always upper bounded by that of 338 an aggregate which consists of micro flows of the smallest rate only 339 and totalling to the same intensity. This means that for a given 340 fraction f, the number of possible minimum rate micro flows 341 determines an upper bound distribution function for any aggregate 342 traffic mix. 344 Note that, through conservative upper bounding, we have the same 345 delay bound for all micro flows in an aggregate irrespective of 346 individual rates which in turn greatly simplifies the management of 347 a DS-domain. Take, for example, the case where the transmission is 348 over an OC-3 link (C=148.61 Mbps, sonet user rate) with aggregate EF 349 traffic intensity 0.90C on the link, then the delay bound per hop is 350 of the order of 1.02 ms (delta=10.77 micro seconds, S=200 bytes, M - 351 > infinity, D=95delta, alpha=10^-9). 353 4.3 Delay across a DS-domain 355 If a DS-domain is designed such that the lowest capacity domain link 356 constrains the total number of micro flows that can be transferred 357 over the DS-domain [4] then the Appendix F establishes that the 358 bound on the delay can be determined from one count of an equivalent 359 stand alone nD/D/1 queue or (M+D)/D/1 queue. 361 Alternatively, consider the case where each micro flow follows a 362 fixed routing path from ingress to egress over a fixed number of 363 hops, say H. We note that a micro flow may traverse portions of DS- 364 domain together with other micro flows. However, a conservative 365 delay bound across the domain can be determined by assuming that the 366 micro flow meets a new set of micro flows at each hop. The delay 367 across the DS-domain can then be considered as the sum of H 368 independent random delay components. Consequently, the bound on the 369 delay can be determined from H counts of nD/D/1 queue or (M+D)/D/1 370 queue. The study given in [11] provides an accurate closed-form 371 formula to calculate the transfer delay bound under similar 372 assumptions. 374 Since the use of conservative assumptions result in small delay 375 bounds (e.g. 1.02 ms), over provisioning of bandwidth resources is 377 Mercankosk Informational - Jan 2001 7 378 not required. Rather, moderate amounts of additional storage 379 resources have been traded for lowering the probability of data flow 380 discontinuity. Also, the simplicity in management of a DS-domain has 381 been an underlying guideline. 383 4.4 Delay due to non-EF micro flows 385 In the case of non-preemptive priority queueing, it is possible that 386 an EF micro flow packet arriving to an empty EF queue may find the 387 server busy transmitting a non-EF packet and has to wait for the end 388 of transmission. The worst case occurs when there is always a non-EF 389 packet waiting to be transmitted. The situation is then equivalent 390 to a queueing system where a server can take vacations if no 391 customer is waiting upon completion of a service. Appendix E 392 provides relevant references for quantifying the additional delay an 393 EF-packet experiences due to non-EF micro flows. 395 Figure 2: Residual rest periods due to non-EF flows 397 Given the properties of queueing models with rest periods stated in 398 Appendix E, the problem of determining the delay due to non-EF micro 399 flows reduces to that of calculating the distribution of residual 400 rest periods. Let S_N-EF denotes the size of a non-EF packet. Then 401 the transmission time delta_N-EF onto the output link is given by 402 S_N-EF/C. There are three cases to consider as illustrated in Figure 403 2. If the size of a non-EF packet is also equal to S, i.e. delta_N- 404 EF = delta, then the study in [5] readily provides the solution. If 405 the size of a non-EF packet is, and normally would be, larger than S 406 but requires less than T time units for transmission, i.e. T >= 407 delta_N-EF > delta, we can use the property shown in [8] with 408 uniformly distributed residual rest period to quantify the delay due 409 to non-EF micro flows. Finally, if the time required to transmit a 410 non-EF packet is larger than T time units, i.e. delta_N-EF > T, then 411 the residual rest period is equal to delta_N-EF - T which is a 412 constant plus a uniformly distributed random variable over (0,T]. If 413 the packet lengths from non-EF micro flows are not fixed but drawn 414 from a known distribution then the residual rest period distribution 415 has to be determined accordingly. 417 5. Other issues 419 We finally look at other issues such as the issue of non-EF traffic 420 starvation, the expected time to the first failure and heterogeneous 421 packet lengths. Unless otherwise stated, we assume non-preemptive 422 priority queueing with equal size EF micro flow packets. 424 5.1 The choice of scheduling mechanism 426 Recall that f denotes the fraction of the output link capacity C 427 that is allocated to the aggregate EF flow at a given node. The 428 maximum amount of EF work presented to the node is then worth fT 429 time units in any interval of T time units. Equivalently, the output 430 link either remains idle or is used to serve non-EF work for T-fT 432 Mercankosk Informational - Jan 2001 8 433 time units. We note that these proportions remain valid under any 434 scheduling mechanism. However, the delay experienced by the members 435 of the aggregate flow depends on the mechanism under consideration. 436 Clearly, the use of priority queueing minimizes the delay for EF 437 traffic and there is no issue of starvation for non-EF traffic 438 provided that T-fT>0. 440 We note, with non-preemptive priority queueing, that the possibility 441 of an additional delay due to non-EF micro flows does not 442 necessitate an additional bandwidth for EF aggregate provided that 443 the aggregate input rate does not exceed the minimum departure rate 444 which happens to be the output link capacity. This observation is 445 based on the fact that the EF traffic never waits while a non-EF 446 queue is serviced except under the circumstances described earlier. 447 This situation is distinctly different under weighted round robin 448 scheduling where the EF queue is forced to relinquish control every 449 now and then as its scheduling parameters require. 451 We acknowledge that the particular way EF PHB is defined may result 452 in EF bandwidth allocation restrictions. We note, however, that it 453 is not a technical requirement, either. 455 It is correct that one could clear the EF traffic backlog by using a 456 scheduling mechanism such as weighted round robin that guarantees a 457 minimum departure rate of (f+deltaf)C with deltaf>0. Such a 458 departure rate, instead of C, can then be used in the analysis above 459 to determine the corresponding delay bounds. As a matter of fact, 460 the minimum departure rate is actually the maximum rate that a 461 scheduler can guarantee to clear the EF traffic backlog. Depending 462 on the dynamic state of the node, the scheduler may clear the EF 463 traffic backlog at a higher rate. However, for the purposes of 464 creating a Virtual Wire PDB, the situation is not considered well 465 defined [4]. 467 5.2 Expected time to the first failure 469 We noted earlier that the delay bound, D, is obtained by the (1- 470 alpha) quantile of the queuing delay for some alpha, say alpha=10^- 471 9. Accordingly, if a VW micro flow lasts long enough then there is a 472 distinct possibility that the data flow continuity could break down. 473 We now establish a crude but conservative expected time to the first 474 failure. A similar approximation has been given in [5]. Recall that 475 an activity change means that either one micro flow drops out or 476 another one joins in. Although activity changes occur due to one 477 micro flow at a time, we assume an entirely new and independent 478 arrival pattern at each activity change. We further assume that 479 there will be an activity change for each packet of a tagged micro 480 flow which is not normally the case. The probability that a packet 481 from the tagged micro flow experiences very small or no queueing 482 delay is a function of target operating loading (indicated by 483 fraction f of each link along the path), and it is generally very 484 high. Therefore, if the first packet of the tagged micro flow 485 experiences a queueing delay greater than D, a break 487 Mercankosk Informational - Jan 2001 9 488 down in data flow continuity would immediately follow due to the 489 reasoning that led to the condition in (6). However, this will 490 happen only once per 1/alpha micro flow starts. For the more likely 491 case of the first packet experiencing no queueing delay, the time 492 until the first break down (expressed in number of activity changes) 493 due to the reasoning that led to the condition in (7), is 494 geometrically distributed with mean 1/alpha. For a micro flow that 495 generates one packet every 20 ms, and given alpha=10^-9, the 496 expected time to the first failure is conservatively 230 days which 497 can be considered reasonably long for all practical purposes. These 498 numbers further put the choice for parameter alpha into a context. 500 5.3 Heterogeneous packet lengths 502 Finally, we look at the issue of heterogeneous packet lengths. We 503 first consider the case where fixed size packets are in use within 504 the same flow, but the size of packets may differ from one micro 505 flow to another. We then lift any restrictions on the packet 506 lengths. 508 We note that, given the virtual wire rate R, large packets mean 509 longer periods and short packets mean shorter periods. However, the 510 amount of work presented to an output link, in its nature, does not 511 differ from the case when we have fixed size packets. Because of the 512 strict ingress policing, the size of a packet can be considered as a 513 quantum of service request over a short time scale. At one extreme, 514 consider a micro flow with a smaller packet size competing with 515 micro flows that use larger packets. Given the uniformly distributed 516 packet arrival epochs in the analysis above, it should be clear that 517 the distribution of the number of packets that form the unfinished 518 work does not change. However, we note that, given the number of 519 packets in the queue, the unfinished work and hence the queueing 520 delay is larger due to larger packet lengths. Under the 521 circumstances, we can relate the difference in queueing delays to 522 the service quanta represented by different packet sizes. Although 523 the arguments given in this paragraph requires further study, the 524 impact of heterogeneous packet sizes should not be significant 525 provided that packet sizes, in use for EF micro flows, do not vary 526 wildly. 528 With variable length packets allowed within the same micro flow, its 529 impact on the queueing delay can be determined when we observe that 530 the unfinished work is now a random sum of random variables that 531 represent packet lengths. 533 Variable length packets within a given micro flow has also an impact 534 on the packet transmission times for the micro flow. With fixed size 535 packets, there is no variation due to packet transmissions and as 536 such the transmission delay is considered as a component of the 537 fixed propagation delay d_p. With variable packet lengths, the 538 variation in packet transmission times is bounded by the difference 539 between the transmission time of a maximum length packet and that of 540 a minimum length packet. We note that the variation in transmission 542 Mercankosk Informational - Jan 2001 10 543 time can be incorporated into the earlier analysis as a modification 544 on the propagation delay without any effect on the queueing delay. 546 6. Assumptions 548 In this document, we have derived the necessary and sufficient 549 conditions for realizing a `Virtual Wire' PDB under the assumption 550 that a periodic flow of packets of fixed size is presented to the 551 DS-domain. It is further assumed that each flow is fully and 552 isochronously used. However, the use of `Virtual Wire' PDB is not 553 limited to periodic flows of fixed size packets. As a matter of 554 fact, pointers for incorporating any variations in traffic 555 characteristics are given. Possible extensions include multi- 556 priority EF queueing and periodic flows with on-off periods. These 557 extensions and possibly some others are left for future discussions. 559 References 561 [1] Bradner, S., "The Internet Standards Process -- Revision 3", 562 BCP 9, RFC 2026, October 1996. 563 [2] Bradner, S., "Key words for use in RFCs to Indicate 564 Requirement Levels", BCP 14, RFC 2119, March 1997 565 [3] V. Jacobson, K. Nichols, K. Poduri, "An Expedited forwarding 566 PHB," ftp://ftp.isi.edu/in-notes/rfc2598.txt. 567 [4] V. Jacobson, K. Nichols, K. Poduri, "The `Virtual Wire' 568 Behavior Aggregate," draft-ietf-diffserv-ba-vw-00.txt, March 2000. 569 [5] P.A. Humblet, A. Bhargava, M.G. Hluchyj, "Ballot Theorems 570 Applied to the Transient Analysis of nD/D/1 Queues," IEEE/ACM 571 Transactions on Networking, Vol 1, No 1, pp 81-95, February 1993. 572 [6] J.W. Roberts, J.T. Virtamo, "The Superposition of Periodic 573 Cell Arrival Streams in an ATM Multiplexer," IEEE Transactions on 574 Communications, Vol 39, No 2, pp 298-303, February 1991. 575 [7] M. Scholl, L. Kleinrock, "On the M/G/1 with Rest Periods and 576 certain Service Independent Queueing Disciplines," Operations 577 Research, Vol 31, pp 705-719, 1983. 578 [8] G. Mercankosk, "Mathematical Preliminaries of Rate Enforced 579 ATM Access," Australian Telecommunications Research Institute, NRL- 580 TM-071, July 1995. 581 [9] R.L. Graham, D.E. Knuth, O. Patashnik, "Concrete Mathematics," 582 Addison Wesley Publishing Company, 1994. 583 [10] Commission of the European Communities, "COST 224, Performance 584 evaluation and design of multiservice networks," Edited by J.W. 585 Roberts, October 1991. 586 [11] D. De Vleeschauwer, G.H. Petit, B. Steyaert, S. Wittevrongel, 587 H. Bruneel, "An accurate Closed-Form Formula to calculate the 588 Dejittering Delay in Packetized Voice Transport," Proceedings of the 589 IFIP-TC6, International Conference on Networking 2000, pp 374-385, 590 Paris, May 2000. 592 Mercankosk Informational - Jan 2001 11 593 Acknowledgments 595 This document is based on and inspired by an earlier joint work with 596 Professor Cantoni. Numerous discussions on related topics with 597 Professor Budrikis have found their way into the arguments presented 598 in this document. Dr. Siliquini has provided a constant 599 encouragement, and has shared the excitement for the preparation of 600 this document. I would also like to acknowledge the context provided 601 by Van Jacobson and his team. 603 Author's Address 605 Guven Mercankosk 606 Australian Telecommunications CRC 607 University of Western Australia 608 TEN Research Group (EE) 609 Nedlands WA 6907 610 Australia 611 Phone: +61 8 9380 7260 612 Email: guven@ee.uwa.edu.au 614 Full Copyright Statement 616 "Copyright (C) The Internet Society (2000). All Rights Reserved. 617 This document and translations of it may be copied and furnished to 618 others, and derivative works that comment on or otherwise explain it 619 or assist in its implmentation may be prepared, copied, published 620 and distributed, in whole or in part, without restriction of any 621 kind, provided that the above copyright notice and this paragraph 622 are included on all such copies and derivative works. However, this 623 document itself may not be modified in any way, such as by removing 624 the copyright notice or references to the Internet Society or other 625 Internet organizations, except as needed for the purpose of 626 developing Internet standards in which case the procedures for 627 copyrights defined in the Internet Standards process must be 628 followed, or as required to translate it into 630 Mercankosk Informational - Jan 2001 12 631 A. Some number theoretic results 633 We first note that, for all real x, floor(x) denotes the largest 634 integer less than or equal to x and ceiling(x) denotes the smallest 635 integer greater than or equal to x. Also note that R and Z denote 636 the set of real and integer numbers, respectively. 638 The following rules can be found in [9]. 640 (12) for all x in R, -floor(x) = ceiling(-x) 642 (13) for all x in R, n in Z, n = ceiling(x) if and only if x <= n < 643 x+1 645 (14) for all x in R, n in Z, n < x if and only if n < ceiling(x) 647 (15) for all x in R, n in Z, n > x if and only if n > floor(x) 649 Mercankosk Informational - Jan 2001 13 650 B. Micro flow relations 652 In this appendix, we express key system quantities in terms of the 653 virtual wire rate R and the equalization delay D_xi. We assume that 654 buffers over the DS-domain and at the egress border are sufficiently 655 large that they do not overflow. We also assume that the initial 656 delay is made sufficiently large so that when the transmission of a 657 packet onto the egress link is completed, there is always another 658 packet in the egress buffer ready for transmission. Subsequently in 659 the Appendix C, we determine the bounds on the buffer sizes and the 660 initial delay. 662 B.1 Packets presented and delivered 664 The number of packets presented to the DS-domain at the ingress 665 border in the interval (0,t] is given by the expression 667 (16) floor(t/T) 669 and illustrated in Figure 3. 671 Figure 3: Packet presentation instants at the ingress 673 Similarly, the number of packets transmitted onto the egress link in 674 the interval (d_1+d_p+D_xi,t] is given by the expression 676 (17) floor((t-(d_1+d_p+D_xi))/T) 678 and illustrated in Figure 4. 680 Figure 4: Packet departure instants at egress 682 B.2 Egress router buffer fill 684 The arrival instants at the egress border buffer partition the time 685 axis into contiguous intervals of variable length. That is, for a 686 given time t, there exists an integer n such that 688 (18) tau_n <= t < tau_(n+1) 690 where tau_n is defined as in (3) and illustrated in Figure 5. 692 Figure 5: Arrivals at egress border buffer 694 The fill level of the egress border buffer at time t is equal to a 695 difference between the total number of packets that have arrived at 696 the egress buffer and the number of packets transmitted onto the 697 egress link. Equivalently, 699 (19) N_E(t) = n - floor((t-(d_1+d_p+D_xi))/T) 701 which follows from (17) and (18). 703 Mercankosk Informational - Jan 2001 14 704 The fill level N_E(t) is a non-increasing function of t between the 705 two successive arrivals at the egress border buffer or over the 706 interval [tau_n,tau_(n+1)) as illustrated in Figure 6. 708 Figure 6: Fill level between successive arrivals 710 B.3 Packets in transit 712 Packets in transit are the packets that have been presented to the 713 DS-domain at the ingress router but have not yet reached the egress 714 border buffer. So, the number of packets in transit at a given time 715 t is given by 717 (20) N_DS(t) = floor(t/T) - n 719 which follows from (16) and (18). 721 B.4 End-to-end delay 723 The initial fill for a particular flow is the number of packets 724 presented to the DS-domain just ahead of the transmission of the 725 first packet onto the egress link minus the first packet. Noting 726 that N_DS(xi_1) is the number of packets in transit at time xi_1 and 727 N_E(xi_1) is the egress border buffer fill at the same time xi_1, we 728 have 730 (21) N_DS(xi_1) + N_E(xi_1) = floor(xi_1/T) - 1 = 731 floor((d_1+d_p+D_xi)/T). 733 Next, we derive an expression for the end-to-end delay over the VW. 734 The end-to-end delay experienced by the kth packet is the time from 735 when the last bit of the kth packet is presented to the DS-domain to 736 when the first bit is transmitted onto the egress link. It can be 737 found by rearranging (4) and substituting t_k for kT as 739 (22) xi_k - t_k = xi_1 - T = d_1 + d_p + D_xi 741 which shows that the end-to-end delay is constant as it would be 742 over a dedicated wire. Adding and subtracting floor(xi_1/T)T and 743 rearranging terms lead to 745 (23) xi_k - t_k = (xi_1 - floor(xi_1/T)T) + (N_DS(xi_1) + 746 N_E(xi_1))T 748 where we also make use of (4) for k=1 and (21). Since the packet 749 presentation to the DS-domain and packet transmission onto the 750 egress link are periodic with period T, the first term on the right 751 hand side of the (23) can be considered as the phase difference 752 phi_R of the egress link relative to the ingress link which is 754 (24) 0 <= phi_R = xi_1 - floor(xi_1/T)T < T. 756 B.5 An invariance property 758 Mercankosk Informational - Jan 2001 15 759 Adding equations (19) and (20) leads to 761 (25) N_DS(t) + N_E(t) 762 = floor(t/T) - floor((t-(d_1+d_p+D_xi))/T) 763 = (floor(xi_1/T) - 1) + (floor(t/T) - floor((t-phi_R)/T)) 764 = N_DS(xi_1) + N_E(xi_1) + (floor(t/T) - floor((t-phi_R)/T)) 766 where we make use of (21) and (24). (25) indicates that the total 767 number of packets for a periodic flow over a virtual wire remains 768 constant to within one packet, once the egress link is initialized 769 and the transmission starts. This is expected as packets flow in at 770 the same rate that they flow out. This represents an invariance 771 property of the total fill, including the packets in transit. 773 Figure 7: Invariance property of the total fill 775 As illustrated in Figure 7, the last term on the right hand side of 776 (25) takes only the values 0 and 1. If we observe the term over the 777 time, the term switches from 0 to 1 just after a packet is presented 778 at the ingress. It stays at that value until the next packet is 779 transmitted onto the egress link. Then it switches back to 0. 781 Mercankosk Informational - Jan 2001 16 782 C. Continuity of flow 784 In Appendix B, we assume sufficiently large buffers and initial 785 total fill so that the data flow continuity could be maintained. In 786 this section, we derive the necessary and sufficient conditions for 787 data flow continuity. 789 Continuity of data flow requires that every packet presented to the 790 DS-domain at the ingress router at fixed intervals has to be 791 transmitted onto the egress link after a fixed delay but again at 792 the same fixed intervals, without being subject to packet loss or 793 interruption during the life time of the flow. Packet loss occurs if 794 a packet has to be discarded due to lack of storing capacity upon 795 arrival at the egress border router. On the other hand, the flow is 796 interrupted if a transmission cannot be started due to 797 unavailability of a packet at the egress border buffer. In the 798 latter case, the buffer is said to be underflowing. 800 In what follows, we show that having a bounded queueing delay over 801 the DS-domain is sufficient to have limits on the maximum fill level 802 that the egress buffer could reach and the minimum fill level that 803 it could fall. These limits can then be used to derive the necessary 804 and sufficient conditions to avoid both overflows and underflows of 805 the egress buffer, i.e. to maintain the continuity of flow. 807 C.1 Egress buffer overflow 809 As the fill level N_E(t) is a non-increasing function of t over the 810 interval [tau_n,tau_(n+1)), it has its peak level at the start of 811 the interval, when the nth packet arrives. Substituting tau_n for t 812 in (19), we have 814 (26) N_E(t) <= n - floor((t_n+d_n+d_p-(d_1+d_p+D_xi))/T) 816 where we make use of (3). Again from the identity given in (1), we 817 see that t_n/T is an integer. This leads to 819 (27) N_E(t) <= - floor((d_n-d_1-D_xi)/T) 820 <= ceiling((d_1+D_xi-d_n)/T) 821 < (d_1+D_xi-d_n)/T + 1 823 where we make use of (12) and (13). An upper bound for N_E(t) can be 824 found by considering a packet which experiences no queueing delay 825 over the DS-domain and the case where the first packet experiences a 826 queueing delay arbitrarily close to the maximum. That is, 828 (28) N_E(t) < (D+D_xi)/T + 1 829 <= ceiling((D+D_xi)/T) 831 where we make use of (14). Therefore, the maximum value N_E,max that 832 the fill level N_E(t) of the egress buffer can reach satisfies the 833 relation 835 (29) N_E(t) <= N_E,max = ceiling((D+D_xi)/T). 837 Mercankosk Informational - Jan 2001 17 838 So if we choose the size of the egress buffer B_E greater than or 839 equal to N_E,max, then the egress buffer never overflows. Otherwise 840 whenever the fill level N_E(t) reaches N_E,max, that is 842 (30) N_E(t_max) = N_E,max > B_E 844 the egress buffer overflows. This leads us to our first dimensioning 845 rule 847 (31) ceiling((D+D_xi)/T) <= B_E 849 which is necessary and sufficient to avoid egress buffer overflow. 851 C.2 Egress link starvation 853 Since the fill level N_E(t) is a non-increasing function of t over 854 the interval [tau_n,tau_(n+1)), it falls to its minimum level after 855 the last, say the kth, packet is transmitted onto the egress link 856 but before the (n+1)st packet arrives. Substituting tau_(n+1) for t 857 in (19), we obtain 859 (32) N_E(t) >= n - floor((t_(n+1)+d_(n+1)+d_p-(d_1+d_p+D_xi))/T) 861 where we again make use of (3). Using the fact that t_(n+1)/T is an 862 integer and the identity (1), we are led to 864 (33) N_E(t) >= -1 - floor((d_(n+1)-d_1-D_xi)/T) 865 >= ceiling((d_1+D_xi-d_(n+1))/T) - 1 866 >= (d_1+D_xi-d_(n+1))/T - 1 868 where we again make use of (12) and (13). Over all packet transfers, 869 a lower bound for N_E(t) can be found this time by considering a 870 packet which experiences a queueing delay arbitrarily close to the 871 maximum and the case where the first packet experiences no queueing 872 delay over the DS-domain. That is, 874 (34) N_E(t) > (D_xi-D)/T - 1 875 >= floor((D_xi-D)/T) 877 where we make use of (15). Therefore, the minimum value N_E,min that 878 the fill level N_E(t) of the egress buffer can fall satisfies the 879 relation 881 (35) N_E(t) >= N_E,min = floor((D_xi-D)/T). 883 Note that the minimum value N_E,min is determined at a time instant 884 such that there will be at least one packet arrival ahead of the 885 next scheduled transmission onto the egress link. So if we delay the 886 transmission of the first packet onto the egress link longer than 887 the maximum queueing delay possible over the DS-domain, then the 888 fill level of the egress buffer never falls below zero. Otherwise, 889 whenever circumstances occur for the fill level N_E(t) to fall down 890 to N_E,min, that is 892 Mercankosk Informational - Jan 2001 18 893 (36) N_E(t_min) = N_E,min < 0 895 the transmission is interrupted. This leads us to our second 896 dimensioning rule 898 (37) floor((D_xi-D)/T) >= 0 900 which is necessary and sufficient to avoid egress link starvation. 902 Mercankosk Informational - Jan 2001 19 903 D. Superposition of periodic flows 905 In this appendix, we outline a queueing model that forms the basis 906 for quantifying the transfer delay bound over a DS-domain. We first 907 describe the queueing model in terms of periodic micro flows to 908 establish the relevance. We then summarize the studies in the 909 literature to quantify the delay due to phase coincidences among 910 micro flows and the delay due to packets within the same micro flow. 911 We finally provide a set of numerical examples. 913 D.1 Queueing model 915 Consider M independent and identical EF-micro flows arriving at a 916 DS-domain router such that all M are bound for the same output link. 917 With the use of priority queueing, the output link capacity provides 918 a well-defined minimum departure rate for EF-traffic. Let C denote 919 the output link capacity. The transmission time delta of a size S 920 packet onto the output link is given by S/C time units. Assuming 921 that the micro flow behavior is strictly determined by (1), each 922 micro flow presents one packet in every T time units to the DS- 923 domain router. Accordingly, the aggregate is a superposition of 924 periodic flows. Limiting the number M of micro flows such that M 925 delta < T, we ensure that the aggregate input rate is less than the 926 minimum departure rate. Consequently, at the output link of the DS- 927 domain router, there is no issue of rate guarantees to individual 928 micro flows. That is, whatever is presented to the DS-domain router, 929 as specified by (1), will be transmitted onto the output link of the 930 router in finite time with probability one, irrespective of the 931 scheduling mechanism being deployed provided that the mechanism is 932 work conserving. 934 Figure 8: An illustration of an arrival pattern 936 The aggregate behavior is completely specified by a set of arrival 937 epochs in any interval of length T. Each set consists of one arrival 938 per micro flow. An illustration of a possible arrival pattern is 939 given in Figure 8. The worst case phasing occurs when all M arrival 940 epochs coincide. However, it should be clear that the likelihood of 941 such occurrence is very small. Nonetheless, phase coincidences give 942 rise to an inevitable multiplexing delay. Assuming a deterministic 943 scheduler, we note that during an interval of no activity change, 944 there is no change in the delay for individual micro flows. An 945 activity change means that either one micro flow drops out or 946 another one joins in. 948 In determining the likelihood of exceeding a specified delay bound, 949 we can safely ignore the repetitive arrival patterns (which is the 950 case over an interval of no activity change) and only consider 951 distinct arrival patterns. In other words, we look at the percentage 952 of arrival patterns that result in a delay exceeding a specified 953 bound. Given the non-ergodic character of the behavior aggregate, we 954 note that the measure of interest is the likelihood of exceeding a 955 specified delay bound (ensemble average) rather than the percentage 956 of time a specified delay bound is exceeded (time average). 958 Mercankosk Informational - Jan 2001 20 959 D.2 Delay due to phase coincidences with other micro flows 961 At a multiplexing stage, the delay due to phase coincidences has 962 been studied in [5] and [6]. The method involves tagging a micro 963 flow and considering an arbitrary arrival pattern of other micro 964 flows for determining the probability of delay exceeding a specified 965 value for the tagged micro flow. Given that each micro flow is 966 strictly shaped to rate R, each packet arrives at a time when it is 967 supposed to arrive. Consequently, FCFS scheduling becomes a natural 968 choice for arbitration of EF micro flows. We note that any other 969 sophisticated arbitration method would require per micro flow state 970 information. 972 Without loss of generality, a packet from the tagged micro flow is 973 assumed to arrive at time t. The waiting time of the packet is then 974 given by the unfinished work in the queue (referred to as nD/D/1 975 queue) at time t, due to M-1 packet arrivals, one per every other 976 micro flow, which are distributed uniformly and independently over 977 the interval [t-T,t) provided that M delta < T. In [5], the 978 associated distribution is given as 980 (38) Pr{ delay > D } = SUM D(j) over [j,ceiling(D/delta),M-1] 982 where D(j) = A(j) C(M-1,j) B(j)^j (1-B(j))^(M-1-j) 983 A(j) = (T+D-(M-1)delta)/(T+D-j delta) 984 C(M-1,j) denotes M-1 choose j 985 B(j) = (j delta - D) / T. 987 The result given in (38) can be normalized, in a straight forward 988 manner, to the transmission time delta. Consequently, the result is 989 not specific to any network architecture. Furthermore, since the 990 choice of tagged micro flow is arbitrary, the delay distribution 991 applies to all micro flows. The issue of heterogeneous packet sizes 992 is addressed elsewhere. It is also a common practice in the 993 literature to normalize the delay to the period T which we have 994 avoided. The normalization naturally takes place in deriving 995 necessary and sufficient conditions given by (6) and (7). 997 D.3 Delay due to packets from the same micro flow 999 The study given in [6] provides a method of determining the delay 1000 distribution for an individual micro flow where the aggregate 1001 consists of micro flows with heterogeneous rates. Let M_i denote the 1002 number of type-i micro flows with period T_i. Then, we ensure that 1003 the aggregate input rate does not exceed the minimum departure rate 1004 by satisfying the condition SUM (M_i delta) / T_i < 1 where the 1005 summation is taken over the set of possible micro flow types. In 1006 determining the unfinished work in the queue at time t, the method 1007 makes the observation, as illustrated in Figure 9, that the number 1008 of packet arrivals from a given type of micro flow in an interval 1009 [t-s,t) of length s consists of a deterministic part and a random 1010 part. Note that in the former case, we only have the random part and 1011 that the intervals of size greater than T need not be considered. 1013 Mercankosk Informational - Jan 2001 21 1014 Figure 9: The number of packet arrivals in [t-s,t) 1016 The study [6] develops tight upper bounds for delay distribution 1017 functions as the exact distributions are, in general, difficult, if 1018 not impossible, to determine. Fortunately though, the study [6] also 1019 concludes that the delay distribution for an arbitrary traffic mix 1020 is always upper bounded by that of an aggregate which consists of 1021 micro flows of the smallest rate only and totalling to the same 1022 intensity. 1024 In the case of homogeneous micro flows in a single multiplexing 1025 stage, it is always correct that the delay bound for an individual 1026 micro flow never exceeds its period T and in general is much smaller 1027 than the period by a couple of orders of magnitude. As a result, a 1028 packet cannot be further delayed due to packets from the micro flow 1029 that it belongs to. We note however that when the aggregate consists 1030 of micro flows with different rates, this is not necessarily 1031 correct. In particular, a packet from a high rate micro flow may 1032 find itself queued behind packets from the same micro flow. Despite 1033 this fact, the method that we refer above already incorporates the 1034 situation in its derivations. 1036 D.4 Numerical results 1038 Figure 10: Delay distribution for nD/D/1 queues, aggregate intensity 1039 0.90C 1041 First, we consider multiplexing homogenous micro flows at an 1042 aggregate intensity of 0.90C. The number M of micro flows varies 1043 between 50 to 900. The corresponding delay distributions, obtained 1044 by using (38), are plotted in Figure 10. Clearly, as the number M 1045 increases higher delays are observed. But even for 900 micro flows, 1046 the probability of delay exceeding 62 delta time units is 10^-9. 1047 This value of delay is smaller than the worst case, which is 899 1048 delta time units, by an order of magnitude. We note that the 1049 corresponding distribution for an (M+D)/D/1 system represents the 1050 limiting case as M->infinity. 1052 Next, we keep the aggregate traffic intensity at 0.90C but consider 1053 different aggregate traffic compositions. The upper bounds for delay 1054 distribution functions, obtained by using the formulation given in 1055 [6], are plotted in Figure 11 where each composition is labelled by 1056 a triple (M_1,M_2,M_3) and M_i indicates the number of type-i micro 1057 flows. In the first composition, we have few high rate flows. Then 1058 we replace some high rate flows with many low rate flows. This 1059 results in an increase in the delay experienced, but again to some 1060 moderate values. For example, in the third composition where we have 1061 461 micro flows, the probability of delay exceeding 40 delta time 1062 units is 10^-9. The delay bound is again 10 times less than the 1063 worst case figure. 1065 Figure 11: Upper bound distribution functions, 1066 T_1=1000delta,T_2=33.33delta,T_3=6.67delta 1068 Mercankosk Informational - Jan 2001 22 1069 Comparing these two sets of experiments, the following observations 1070 can be made. First, the upper bound for a distribution function 1071 yields the same result as (38) does, if there is only one type of 1072 micro flow. Second, any aggregate traffic composition would result 1073 in a better delay performance than the case where enough number of 1074 lowest rate micro flows making up the same aggregate intensity. This 1075 means that for a given fraction f, the number of possible minimum 1076 rate micro flows determines the limiting distribution for any 1077 aggregate traffic mix. 1079 Mercankosk Informational - Jan 2001 23 1080 E. Queueing models with rest periods 1082 Queueing models with rest periods are used in the analysis of 1083 slotted queueing systems. This appendix provides relevant references 1084 for studying the delay due to non-EF traffic. 1086 In [7], the study shows that, for a slotted M/G/1 system, the 1087 waiting time is the sum of two independent random variables 1088 representing the waiting time when there are no rest periods and an 1089 additional delay distributed as the residual life of the rest 1090 period. 1092 In [5], the study provides not only the delay distribution as given 1093 in (38) when there is no slotting but also the delay distribution 1094 when the transmission is restricted to start at a slot boundary 1095 where each slot is of fixed length equal to delta. Since packet 1096 arrival epochs are assumed to be uniformly distributed over an 1097 interval of length T, the residual slot period until the start of 1098 the next transmission opportunity (following the arrival of a packet 1099 from the tagged micro flow) is uniformly distributed over (0,delta]. 1101 In [8], based on the results given in [5], we show that a slotted 1102 nD/D/1 queue exhibits the same property, given in [7], as a slotted 1103 M/G/1 system does. 1105 Mercankosk Informational - Jan 2001 24 1106 F. A network of routers in tandem 1108 In this appendix, we consider two simulation scenarios. In the first 1109 scenario, we have a network of routers in tandem where micro flows 1110 with a common destination are incrementally introduced at each hop. 1111 In the second scenario, the same set of micro flows compete for 1112 access onto the same output link of a stand-alone router. The latter 1113 is equivalent to having infinite capacity links between the 1114 intermediate routers in tandem except at the last hop. 1116 An illustration of a network of routers in tandem is given in Figure 1117 12. The network is comprised of a specified number of routers. The 1118 background flows in groups are attached to specified routers and 1119 join the aggregate flow. We focus on a single tagged or test flow 1120 and study its delay characteristics through the network. The test 1121 flow can be attached to any router and runs from the router it is 1122 attached (the ingress router) to the egress router. 1124 Figure 12: A network with 4 hops, all flows through the same egress 1125 router 1127 Figure 13: A stand-alone router 1129 With the use of infinite capacity links between the routers, the 1130 network of routers in tandem can be represented with a stand-alone 1131 router as illustrated in Figure 13. To facilitate the comparison, 1132 the flow arrival patterns used for the routers in tandem are exactly 1133 regenerated and presented to the stand-alone router. 1135 F.1 Traffic model 1137 In quantifying the delay due to phase coincidences, we maintain a 1138 periodic test flow. Once the activity of the test flow starts, it 1139 presents packets to the network continuously at the specified rate 1140 until the end of simulation run. 1142 In determining ensemble averages, we use a specified number of 1143 background micro flows with identical period. After an uniformly 1144 distributed transient delay, each background flow determines a 1145 random phase within its period to start its activity. After 1146 periodically generating a specified number packets at a given phase, 1147 the background flow stops for a geometrically distributed number of 1148 periods. At the end of the silence interval, it repeats its activity 1149 with a different phase. 1151 The use of Markovian background traffic can be considered as a 1152 limiting case. As a matter of fact, considering a background traffic 1153 comprised of M independent periodic flows each with period T, it is 1154 true that the number of arrivals over an interval (t-s,t] is 1155 distributed according to the binomial distribution where sinfinity while keeping the 1157 aggregate intensity fixed at fC=N delta/T, we obtain Poisson arrival 1158 process with parameter fC. In other words, the Markovian noise is 1160 Mercankosk Informational - Jan 2001 25 1161 comprised of infinitely many periodic flows each with period 1162 infinity while the aggregate intensity is fC. 1164 Accordingly, the background traffic either is comprised of a 1165 specified number of periodic flows with randomly changing phases or 1166 is generated by a Markovian process of equivalent intensity. 1167 Although it is assumed that priority queueing is deployed at each 1168 router, the non-EF traffic is not considered. The ingress-to-egress 1169 total queuing delay experienced by each test packet is recorded to 1170 obtain a delay histogram. 1172 F.2 Numerical results 1174 In the first set of experiments, we use a test flow that 1175 periodically generates one packet in every 100 delta time units, 1176 i.e. with intensity 0.01C. In the background, we use 100 micro flows 1177 and 10 hops, i.e. 10 micro flows per hop. Each flow generates 20 1178 packets with period 100 delta time units at a random phase. After 1179 each phase activity, a flow remains silent for geometrically 1180 distributed number of 100 delta time units with a mean value of 1181 1.053. Accordingly, the intensity of background flows joining the 1182 aggregate at each hop is 0.095C. In the second set of experiments, 1183 the set of periodic flows at each router is replaced with a Poisson 1184 source of the same intensity. 1186 In both set of experiments, the location of the test flow is varied 1187 from nearest to the egress router to furthest. The associated delay 1188 distributions are plotted in Figure 14. Despite the fact that the 1189 aggregate intensity remains fixed, we observe that a test flow 1190 closer to the egress router experiences a better delay performance. 1191 We also note that, in the case of periodic background flows, after 5 1192 hops the difference becomes unnoticeable. In the case of Markovian 1193 flows, the difference is marginal altogether. 1195 Figure 14: Delay distribution versus test flow position, aggregate 1196 intensity 1198 In Figure 15, the tail distribution of the delay experienced by the 1199 packets of test flow when located at both extremes are plotted 1200 against that of the packets of test flow when the aggregate flow is 1201 fed into a stand-alone router. The delay experienced through the 1202 routers in tandem is depicted by dashed lines whereas that of 1203 through the stand-alone router is depicted by solid lines. 1205 Figure 15: Delay distribution, tandem versus stand-alone, aggregate 1206 intensity 1208 As the curves indicate, when the test flow is located furthest from 1209 the egress router, the performance is inferior to that of stand- 1210 alone router. However, in practical terms, it is insignificant. The 1211 difference can be attributed to arrival pattern transformations. A 1212 pattern transformation results due to the possibility of packets 1213 from micro flows joining the aggregate at a nearer router overtaking 1214 packets from the test flow until the latter packets reach the router 1216 Mercankosk Informational - Jan 2001 26 1217 in question. The simulation results show that the effect of such 1218 transformations are minimal. 1220 When the test flow is located nearest to the egress router, it is in 1221 the most advantageous position. As indicated earlier, the stand- 1222 alone router represents the situation of having infinite capacity 1223 links between the intermediate routers in tandem except at the last 1224 hop. A consequence of such a situation is that packets arriving at 1225 the intermediate routers appear at the last hop in no time. In the 1226 case of finite but relatively higher rate links, each packet appears 1227 at the last hop shortly following its arrival. Under the 1228 circumstances, the test flow located nearest loses its advantage but 1229 not beyond the delay due to originating phase coincidences. 1231 Mercankosk Informational - Jan 2001 27