idnits 2.17.1 draft-ietf-diffserv-ba-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 seems to lack a 1id_guidelines paragraph about 6 months document validity -- however, there's a paragraph with a matching beginning. Boilerplate error? ** The document is more than 15 pages and seems to lack a Table of Contents. == No 'Intended status' indicated for this document; assuming Proposed Standard == The page length should not exceed 58 lines per page, but there was 17 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 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 40 instances of too long lines in the document, the longest one being 23 characters in excess of 72. Miscellaneous warnings: ---------------------------------------------------------------------------- == Line 151 has weird spacing: '...il time for p...' == Line 735 has weird spacing: '...ows the topol...' == Line 739 has weird spacing: '...various scena...' == Line 783 has weird spacing: '...he time of...' == The document seems to lack the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. (The document does seem to have the reference to RFC 2119 which the ID-Checklist requires). -- 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.) -- Couldn't find a document date in the document -- date freshness check skipped. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Unused Reference: 'RFC2474' is defined on line 311, but no explicit reference was found in the text == Unused Reference: 'RFC2597' is defined on line 317, but no explicit reference was found in the text == Unused Reference: 'RFC2638' is defined on line 325, but no explicit reference was found in the text ** Downref: Normative reference to an Informational RFC: RFC 2475 ** Obsolete normative reference: RFC 2598 (Obsoleted by RFC 3246) ** Downref: Normative reference to an Informational RFC: RFC 2638 == Outdated reference: A later version (-01) exists of draft-ietf-diffserv-ba-def-00 -- Possible downref: Normative reference to a draft: ref. 'BADEF' -- Possible downref: Non-RFC (?) normative reference: ref. 'CAIDA' -- Possible downref: Non-RFC (?) normative reference: ref. 'NS2' -- Possible downref: Non-RFC (?) normative reference: ref. 'FBK' ** Downref: Normative reference to an Informational RFC: RFC 2415 Summary: 11 errors (**), 0 flaws (~~), 11 warnings (==), 6 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Internet Engineering Task Force Van Jacobson 2 Differentiated Services Working Group Kathleen Nichols 3 Internet Draft Kedar Poduri 4 Expires Aug, 2000 Cisco Systems, Inc. 5 draft-ietf-diffserv-ba-vw-00.txt March, 2000 7 The 'Virtual Wire' Behavior Aggregate 8 10 Status of this Memo 12 This document is an Internet-Draft and is in full conformance with 13 all provisions of Section 10 of RFC2026. Internet-Drafts are 14 working documents of the Internet Engineering Task Force (IETF), 15 its areas, and its working groups. Note that other groups may also 16 distribute working documents as Internet-Drafts. 18 Internet-Drafts are draft documents valid for a maximum of six 19 months and may be updated, replaced, or obsoleted by other docu- 20 ments at any time. It is inappropriate to use Internet-Drafts as 21 reference material or to cite them other than as "work in 22 progress." 24 The list of current Internet-Drafts can be accessed at 25 http://www.ietf.org/ietf/1id-abstracts.txt. The list of Internet-Draft 26 Shadow Directories can be accessed at http://www.ietf.org/ 27 shadow.html. Distribution of this memo is unlimited. 29 Abstract 31 This document describes an edge-to-edge behavior called 'Virtual 32 Wire' (VW) that can be constructed in any domain supporting the 33 diffserv EF PHB plus appropriate domain ingress policers. The VW 34 behavior is essentially indistinquishable from a dedicated cir- 35 cuit and can be used anywhere it is desired to replace dedicated 36 circuits with IP transport. 38 A pdf version of this document is available at 39 ftp://ftp.ee.lbl.gov/papers/vw_ba.pdf 41 1.0 Introduction 43 [RFC2598] describes a diffserv PHB called expedited forwarding 44 (EF) intended for use in building a scalable, low loss, low 45 latency, low jitter, assured bandwidth, end-to-end service that 46 appears to the endpoints like an unshared, point-to-point connec- 47 tion or 'virtual wire.' For scalability, a diffserv domain sup- 48 plying this service must be completely unaware of the individual 50 Jacobson, Nichols & Poduri Expires: August, 2000 [page 1 ] 51 endpoints using it and sees instead only the aggregate EF marked 52 traffic entering and transiting the domain. This document pro- 53 vides the specifications necessary on that aggregated traffic (in 54 diffserv terminology, a behavior aggregate or BA) in order to meet 55 these requirements and thus defines a new BA, the Virtual Wire 56 behavior aggregate or VW BA. Despite the lack of per-flow state, 57 if the aggregate input rates are appropriately policed and the EF 58 service rates on interior links are appropriately configured, the 59 edge-to-edge service supplied by the domain will be indistin- 60 guishable from that supplied by dedicated wires between the end- 61 points. This note gives a quantitative definition of what is meant 62 by 'appropriately policed and configured'. 64 Loss, latency and jitter are all due to the queues traffic experi- 65 ences while transiting the network. Therefore providing low loss, 66 latency and jitter for some traffic aggregate means ensuring that 67 the packets of the aggregate see no (or very small) queues. Queues 68 arise when short-term traffic arrival rate exceeds departure rate 69 at some node(s). Thus ensuring no queues for some aggregate is 70 equivalent to bounding rates such that, at every transit node, the 71 aggregate's maximum arrival rate is less than that aggregate's 72 minimum departure rate. 74 Creating the VW BA has two parts: 76 1. Configuring nodes so that the aggregate has a well-defined 77 minimum departure rate. (`Well-defined' means independent of 78 the dynamic state of the node. In particular, independent of 79 the intensity of other traffic at the node.) 81 2. Conditioning the aggregate (via policing and shaping) so that 82 it's arrival rate at any node is always less than that node's 83 configured minimum departure rate. 85 [RFC2598] provides the first part. This document describes how 86 one configures the EF PHBs in the collection of nodes that make up 87 a DS domain and the domain's boundary traffic conditioners 88 (described in [RFC2475]) to provide the second part. This 89 description results in a diffserv behavior aggregate, as 90 described in [BADEF]. 92 The next sections describe the VW BA in detail and give examples 93 of how it might be implemented. The keywords "MUST", "MUST NOT", 94 "REQUIRED", "SHOULD", "SHOULD NOT", and "MAY" that appear in this 95 document are to be interpreted as described in [RFC2119]. 97 2.0 Description of the Virtual Wire BA 99 2.1 Applicability 101 A Virtual Wire (VW) BA is intended to send "circuit replacement" 102 traffic across a diffserv network. That is, this BA is intended to 103 mimic, from the point of view of the originating and terminating 105 Jacobson, Nichols & Poduri Expires: August, 2000 [page 2 ] 106 nodes, the behavior of a hard-wired circuit of some fixed capac- 107 ity. It does this in a scalable (aggregatable) way that doesn't 108 require 'per-circuit' state to exist anywhere but the ingress 109 router adjacent to the originator. This BA should be suitable for 110 any packetizable traffic that currently uses fixed circuits 111 (e.g., telephony, telephone trunking, broadcast video distribu- 112 tion, leased data lines) and packet traffic that has similar 113 delivery requirements (e.g., IP telephony or video conferencing). 115 2.2 Rules 117 Each node in the domain MUST implement the EF PHB as described in 118 section 2 of [RFC2598] but with the SHOULDs of that section taken 119 as MUSTs. The bandwidth limit of each output interface SHOULD be 120 configured as described in Section 2.4 of this document. In addi- 121 tion, each domain boundary input interface that can be the ingress 122 for EF marked traffic MUST strictly police that traffic as 123 described in Section 2.4. Each domain boundary output interface 124 that can be the egress for EF marked traffic MUST strictly shape 125 that traffic as described in Section 2.4. 127 2.3 Characteristics 129 "The same as a wire." As long as packets are sourced at a rate <= 130 the virtual wire's configured rate, they will be delivered with a 131 high degree of assurance and with almost no distortion of the 132 interpacket timing imposed by the source. However, any packets 133 sourced at a rate greater than the VW configured rate, measured 134 over any time scale longer than a packet time at that rate, will 135 be unconditionally discarded. 137 2.4 Parameters 139 Figure 1: Time structure of packets of a CBR stream at a high to 140 low bandwidth transition 142 Figure 1 shows a CBR stream of size S packets being sourced at 143 rate R. At the domain egress border router, the packets arrive on 144 a link of bandwidth B (= nR) and depart to their destination on a 145 link of bandwidth R. 147 Figure 2: Details of arrival / departure relationships 149 Figure 2 shows the detailed timing of events at the router. At 150 time T0 the last bit of packet 0 arrives so output is started on 151 the egress link. It will take until time for packet 0 152 to be completely output. As long as the last bit of packet 1 153 arrives at the border router before , the destination node will 154 find the traffic indistinguishable from a stream carried the 155 entire way on a dedicated wire of bandwidth R. This means that 156 packets can be jittered or displaced in time (due to queue waits) 157 as they cross the domain and that there is a jitter window at the 158 border router of duration 160 Jacobson, Nichols & Poduri Expires: August, 2000 [page 3 ] 161 (EQ 1) 163 that bounds the sum of all the queue waits seen be a packet as it 164 transits the domain. As long as this sum is less than , the des- 165 tination will see service identical to a dedicated wire. 167 Figure 3: Packet timing structure edge-to-edge 169 Figure 3 shows the edge-to-edge path from the source to the desti- 170 nation. The links from S to I and E to D run at the virtual wire 171 rate R (or the traffic is shaped to rate R if the links run at a 172 higher rate). The solid rectangles on these links indicate the 173 packet time S/R. The dotted lines carry the packet times across 174 the domain since the time boundaries of these virtual packets form 175 the jitter window boundaries of the actual packets (whose dura- 176 tion and spacing are shown by the solid rectangles below the 177 intra-domain link). Note that each packet's jitter is indepen- 178 dent. E.g., even though the two packets about to arrive at E have 179 been displaced in opposite directions so that the total time 180 between them is almost , neither has gone out of its jitter win- 181 dow so the output from E to D will be smooth and continuous. 183 Figure 4: Three VW customers forming an aggregate 185 This jitter independence is what allows multiple 'virtual wires' 186 to be transparently aggregated into a single VW BA. Figure 4 shows 187 three independent VW customers, blue, yellow and red, entering 188 the domain at I. Assume that their traffic has worst-case phasing, 189 i.e., that one packet from each stream arrives simultaneously at 190 I. Even if the output link scheduler makes a random choice of 191 which packet to send from its EF queue, no packet will get pushed 192 outside its jitter window. For example, in Figure 4 node I ships a 193 different perturbation of the 3 customer aggregate in every win- 194 dow yet this has no effect on the edge-to-edge VW properties). 196 The jitter independence means that we only have to compare the 197 jitter bound of Equation 1 to the worst case of the total queue 198 wait that can be seen by a single VW packet as it crosses the 199 domain. There are three potential sources of queue wait for a VW 200 packet: 202 1. it can queue behind non-EF packets (if any) 204 2. it can queue behind another VW packet from the same customer 206 3. it can queue behind VW packet(s) from other customers 208 For case (1), the EF 'priority queuing' model says that the VW 209 traffic will never wait while a non-EF queue is serviced so the 210 only delay it can experience from non-EF traffic is if it has to 211 wait for the finish of a packet that was being sent at the time it 212 arrived. For an output link of bandwidth B, this can impose a 214 Jacobson, Nichols & Poduri Expires: August, 2000 [page 4 ] 215 worst-case delay of S/B. Note that this implies that if the (low 216 bandwidth) links of a network are carrying both VW and other traf- 217 fic, then n in Equation 1 must be at least 2 (i.e., the EF bound 218 can be at most half the link bandwidth) in order to make the jit- 219 ter window large enough to absorb this delay. 221 Case (2) can only happen if the previous packet hasn't completely 222 departed at the time the next packet arrives. Since the incoming 223 VW stream is strictly shaped to a rate R, any two packets will be 224 separated by at least time S/R so having leftovers is equivalent 225 to saying the departure rate on some link is R over any time scale of S/R or longer so this can't hap- 228 pen for any legal VW/EF configuration. Or, to put it another way, 229 if case (2) happens, either the VW policer is set too loosely or 230 some link's EF bound is set too tight. 232 Case (3) is a simple generalization of (2). If there are a total 233 of n customers, the worst possible queue occurs if all n arrive 234 simultaneously at some output link. Since each customer is indi- 235 vidually shaped to rate R, when this happens then no new packets 236 from any stream can arrive for at least time S/R so having left- 237 overs is equivalent to a departure rate < nR over this time scale. 238 But the EF property for any link capable of handling the aggregate 239 traffic is that the departure rate be > nR over any time scale 240 longer than S/(nR) so, again, this can't happen in any legal VW/EF 241 configuration. 243 For case (1), a packet could be displaced by non-EF traffic once 244 per hop so the edge-to-edge jitter is a function of the path 245 length. But this isn't true for case (3): The strict ingress 246 policing implies that a packet from any given VW stream can meet 247 any other VW stream in a queue at most once. This means the worst 248 case jitter caused by aggregating VW customers is a linear func- 249 tion of the number of customers in the aggregate but completely 250 independent of topology. 252 2.5 Assumptions 254 The topology independence of VW service actually holds only while 255 routing is relatively stable. Since packets can be duplicated 256 while routing is converging, and since path lengths can be shorter 257 after a routing change, it is possible to violate the VW traffic 258 bounds and thus jitter stream(s) more than their jitter window for 259 a small time during and just after a routing change. 261 2.6 Example uses 263 Say an ISP wants to carry RTP encapsulated telephony traffic in 264 addition to data traffic. Assume that want to retain all the 265 robustness of IP (re-)routing which is equivalent to saying that 266 all traffic can show up on any link. This implies that the lowest 267 bandwidth backbone link constrains the total number of calls that 269 Jacobson, Nichols & Poduri Expires: August, 2000 [page 5 ] 270 can be carried. If the smallest backbone link is OC-3 and each 271 call generates at most a 200 byte packet every 20ms, then the 272 total number of VW customers that can be admitted into the back- 273 bone must be less than 275 (For comparison, an OC-3 TDM telco trunk could admit 2421 custom- 276 ers so there is a 25% bandwidth penalty paid for the ability to 277 efficiently mix voice and data.) Since this limit does not depend 278 on the topology, these call slots can be assigned to customers, 279 either statically or dynamically, in any way that doesn't violate 280 the VW/EF bound on the customer tail circuits. 282 Note that each call looks like two 'customers', one each direc- 283 tion, so this overly simple bound is actually less than half the 284 capacity of an equivalent telco system. If one adds the topologi- 285 cal assumption that none of the simplex traffic streams between 286 two endpoints will ever travel both directions over the same link, 287 then the number VW customers becomes 1938 each direction so the 288 domain has roughly the same telephony capacity as an equivalent 289 telco system. 291 2.7 Environmental concerns 293 Routing instability will generally translate directly into VW 294 service degradation. 296 The analysis in Section 2.4 would hold in a world where traffic 297 policers and link schedulers are perfect and mathematically 298 exact. When computing parameters for our world, 5-10% fudge fac- 299 tors should be used. 301 3.0 Security Considerations 303 There are no security considerations for the VW BA other than 304 those associated with the EF PHB which are described in [RFC2598]. 306 4.0 References 308 [RFC2119] "Key words for use in RFCs to Indicate Requirement Lev- 309 els", S.Bradner, www.ietf.org/rfc/rfc2119 311 [RFC2474] "Definition of the Differentiated Services Field (DS Field) in the IPv4 and IPv6 312 Headers", K.Nichols, S. Blake, F. Baker, D. Black, www.ietf.org/rfc/rfc2474.txt 314 [RFC2475] "An Architecture for Differentiated Services", S. Blake, D. Black, M.Carl- 315 son,E.Davies,Z.Wang,W.Weiss, www.ietf.org/rfc/rfc2475.txt 317 [RFC2597] "Assured Forwarding PHB Group", F. Baker, J. Heinanen, W. Weiss, J. Wroclawski, 318 ftp://ftp.isi.edu/in-notes/rfc2597.txt 320 [RFC2598] "An Expedited Forwarding PHB", V.Jacobson, K.Nichols, K.Poduri, ftp://ftp.isi.edu/ 322 Jacobson, Nichols & Poduri Expires: August, 2000 [page 6 ] 323 in-notes/rfc2598.txt 325 [RFC2638] "A Two-bit Differentiated Services Architecture for the 326 Internet", K. Nichols, V. Jacobson, and L. Zhang, 327 www.ietf.org/rfc/rfc2638.{txt,ps} 329 [BADEF] "Definition of Differentiated Services Behavior Aggregates and Rules for their Speci- 330 fication", K.Nichols, B.Carpenter, draft-ietf-diffserv-ba-def-00.[txt, pdf] 332 [CAIDA] The nature of the beast: recent traffic measurements from an Internet backbone. K 333 Claffy, Greg Miller and Kevin Thompson. http://www.caida.org/Papers/Inet98/ 334 index.html 336 [NS2] The simulator ns-2, available at: http://www-mash.cs.berkeley.edu/ns/. 338 [FBK] K. Nichols, "Improving Network Simulation with Feedback", Proceedings of 339 LCN'98, October, 1998. 341 [RFC2415] RFC 2415, K. Poduri and K. Nichols, "Simulation Studies of Increased Initial TCP 342 Window Size", September, 1998. 344 5.0 Authors' Addresses 346 Van Jacobson 347 Cisco Systems, Inc. 348 170 W. Tasman Drive 349 San Jose, CA 95134-1706 350 van@cisco.com 352 Kathleen Nichols 353 Cisco Systems, Inc. 354 170 W. Tasman Drive 355 San Jose, CA 95134-1706 356 kmn@cisco.com 358 Kedar Poduri 359 Cisco Systems, Inc. 360 170 W. Tasman Drive 361 San Jose, CA 95134-1706 362 kmn@cisco.com 364 6.0 Appendix: On Jitter for the VW BA 366 The VW BA's bounded jitter translates into the generally useful 367 properties of network bandwidth limits and buffer resource lim- 368 its. These properties make VW useful for a variety of statically 369 and dynamically provisioned services, many of which have no 370 intrinsic need for jitter bounds. IP telephony is an important 371 application for the VW BA where expected and worst-case jitter for 372 rate-controlled streams of packets is of interes; thus this 373 appendix is primarily focused on voice jitter. The appendix 375 Jacobson, Nichols & Poduri Expires: August, 2000 [page 7 ] 376 focuses on jitter for individual flows aggregated in a VW BA, 377 derives worst-case bounds on the jitter, and gives simulation 378 results for jitter. 380 6.1 Jitter and Delay 382 The VW BA is sufficiently restrictive in its rules to preserve the 383 required EF per-hop behavior under aggregation. These properties 384 also make it useful as a basis for Internet telephony, to get low 385 jitter and delay. Since a VW BA will have link arrival rates that 386 do not exceed departure rates over fairly small time scales, end- 387 to-end delay is based on the transmission time of a packet on a 388 wire and the handling time of individual network elements and thus 389 is a function of the number of hops in a path, the bandwidth of 390 the links, and the properties of the particular piece of equipment 391 used. Unless the end-to-end delay is excessive due to very slow 392 links or very slow equipment, it is usually the jitter, or varia- 393 tion of delay, of a voice stream that is more critical than the 394 delay. 396 We derive the worst case jitter for a a VW BA in a DS domain using 397 it to carry a number of rate-controlled flows. Jitter is defined 398 as the absolute value of the difference between the arrival time 399 difference of two adjacent packets and their departure time dif- 400 ference, that is: 402 (EQ 2)jitter = |(ak-aj) - (dk-dj)| 404 The maximum jitter will occur if one packet waits for no other 405 packets at any hop of its path and the adjacent packet waits for 406 the maximum amount of packets possible. There are two sources of 407 jitter, one from waiting for other EF packets that may have accu- 408 mulated in a queue due to simultaneous arrivals of EF packets on 409 several input lines feeding the same queue and another from wait- 410 ing for non-EF packets to complete. The first type is strictly 411 bounded by the properties of the VW BA and the EF PHB. The second 412 type is minimized by using a Priority Queuing mechanism to sched- 413 ule the output link and giving priority to EF packets and this 414 value can be approached by using a non-bursty weighted round- 415 robin packet scheduler and giving the EF queue a large weight. The 416 total jitter is the sum of these two. 418 Maximum jitter will be given across the domain in terms of T, the 419 virtual packet time or cyle time. It is important to recall the 420 analysis of section 3.0 showing that this jitter across the DS 421 domain is completely invisible to the end-to-end flow using the VW 422 BA if it is within the jitter window at the egress router. 424 6.1.1 Jitter from other VW packets 426 The jitter from meeting other packets of the VW aggregate comes 427 from (near) simultaneous arrival of packets at different input 428 ports all destined for the same output queue that can be com- 430 Jacobson, Nichols & Poduri Expires: August, 2000 [page 8 ] 431 pletely rearranged at the next packet arrival to that queue. This 432 jitter has a strict bound which we will show here. 434 It will be helpful to remember that, from RFC 2598, a BA using the 435 EF PHB will get its configured share of each link at all times- 436 cales above the time to send an MTU at the rate corresponding to 437 that share of that link. 439 Focus on the DS domain of figure 5. Unless otherwise stated, in 440 this section assume M Boundary Routers, each having N inputs and 441 outputs. We assume that each of the BR's ingress ports receives a 442 flow of EF-marked packets that are being policed to a peak rate R. 443 If each flow sends a fixed size packet, then it's possible to cal- 444 culate the fixed time, T, between packets of each of these MxN 445 flows that enters the DS domain, a quite reasonable assumption for 446 packets carrying voice. For example, assume a domain traversed by 447 MxN flows of 68 byte voice packets sent at 20 ms time intervals. 448 Note we assume all ingress links have some packets that will be 449 marked for the VW aggregate. Thus the total number of ingress EF- 450 marked streams to the VW aggregate is I = MxN. 452 To construct a network where the maximum jitter can occur, a sin- 453 gle flow traversing the network must be able to meet packets from 454 all the other flows marked for the EF PHB and it should be possi- 455 ble to meet them in the worst possible way. 457 Figure 5: A DS domain 459 Unless otherwise stated, assume that all the routers of the domain 460 have N inputs and outputs and that all links have the same band- 461 width B. Although there are a number of ways that the individual 462 streams from different egress ports might combine in the interior 463 of the network, in a properly configured network, the arrival rate 464 of the VW BA must not exceed the departure rate at any network 465 node. Consider a particular flow from A to Z and how to ensure 466 that packets entering the VW BA at A meet every other flow enter- 467 ing the domain from all egress points as they traverse the domain 468 to Z. Consider three cases: the first is a single bottleneck, the 469 second makes no assumptions about routing in the network and the 470 third assumes that the paths of individual flows can be completely 471 specified. 473 Assume there are H hops from A to Z and that delay is the minimum 474 time it takes for a packet to go from A to Z in the absence of 475 queuing. Both packets experience delay and thus it subtracts in 476 the jitter calculation. Recall that the packets of the flow are 477 separated in time by T, then (normalizing to a start time of 0): 479 (EQ 3)dj = 0 481 (EQ 4)dk = T 483 (EQ 5)aj = delay 485 Jacobson, Nichols & Poduri Expires: August, 2000 [page 9 ] 486 (EQ 6)ak = time spent waiting behind all other packets +delay+T 488 Then we can use: 490 (EQ 7)jitter = time spent waiting behind all other packets 492 as we explore calculating worst case jitter for different topolo- 493 gies. 495 The next step is to establish some useful relationships between 496 parameters. First, assume that some fraction, f, of a link's 497 capacity is allocated to EF-marked packets. Since we are assuming 498 that all the flows that are admitted into this DS domain's VW 499 aggregate generate packets at a spacing of T, this can be 500 expressed in time as fxT. Then the amount of time to send an EF 501 packet on each link can be written as fxT/(total number of EF- 502 marked flow crossing the link). Note that f should be less than 503 0.5 in order that an MTU-sized non-EF packet will not cause the EF 504 condition to be violated. 506 6.1.1.1 Worst case jitter in a network with a dumbbell bottleneck 508 Consider a DS domain topology shown in figure 6. In order for a 509 packet of the (A,Z) flow to arrive behind packets of all the other 510 flows, a packet from each ingress must arrive at each of the M 511 border routers at the same time and must be transmitted to the 512 interior router's queue for the bottleneck link B at the same 513 time. Further the links between the border routers and the bottle- 514 neck router must be enough larger than B that the packets are 515 still sitting in B's queue when our (A,Z) packet arrives at the 516 end of a burst of N packets, that is L > NxB. Then the 518 (EQ 8)jitterworst case = MxNx(time to send an EF packet on B) 520 Since we expressed the EF aggregate's allocation on B as fxB, the 521 time to send an EF packet on B is fxT/(MxN), so 523 (EQ 9)jitterworst case = fxT 525 Figure 6: A dumbbell bottleneck 527 This result shows that the worst case jitter will be less than 528 half a packet time for any VW-compliant allocation on this topol- 529 ogy. For the worst case to occur, all N packets must arrive simul- 530 taneously at all M border routers. By assuming independence, an 531 interested person should be able to get some insight on the like- 532 lihood of this happening. Simulation results in a later section 533 will show this. 535 6.1.1.2 Worst case jitter in an arbitrary network 537 Jacobson, Nichols & Poduri Expires: August, 2000 [page 10 ] 538 Consider the network of figure 5 and in this case, one packet of 539 the (A,Z) flow must arrive at the same time, but be queued behind 540 a packet from each of the other flows as it passes through the 541 network. This can happen at any link of the network and even at 542 the same link. In this case, assume all links have bandwidth B but 543 we don't know the path the individual EF packets or flows of the 544 aggregate will follow. Then the worst case jitter is 546 (EQ 10)jitterworst case = Ix(fxT/I) = fxT 548 the same as the bottleneck case. Note that, in allocation, if it 549 is possible to know that not all flows of the aggregate will take 550 the same path, then one could allocate each link to a smaller num- 551 ber of flows, but this would also imply that the number of flows 552 that it's possible to meet and be jittered by is smaller. Alloca- 553 tion can be kept to under 0.5 times the bandwidth of a core link, 554 while the existence of multiple paths offers both fault tolerance 555 and an expectation that the actual load on any link will be less 556 than 0.5. 558 How likely is this case to happen? One packet of the (A,Z) flow 559 must encounter and queue behind every other individual shaped 560 flow that makes up the domain's VW aggregate as it crosses the 561 domain. 563 6.1.1.3 Maximal jitter in a network with "pinned" paths per flow 565 Then at each hop the (A,Z) packet has to arrive at the same time 566 as an EF packet from the (N-1) other inputs and the (A,Z) packet 567 has to be able to end up anywhere within that burst of N packets. 568 In particular, for two adjacent packets of the (A,Z) flow, one 569 must arrive at the front of every hop's burst and the other at the 570 end of every hop's burst. This clearly requires an unrealistic 571 form of path pinning or route selection by every individual EF- 572 marked flow entering the DS domain. This unidirectional path is 573 shown in figure 7 where all routers have N inputs and at each of 574 the H routers on the path from A to Z, N-1 flows are sent to other 575 output queues, while N-1 of the shaped input flows that have not 576 yet crossed the A to Z path enter the router at the other input 577 ports. 579 Figure 7: Example path for maximal jitter across DS domain from A to Z 581 It should be noted that if the number of hops from A to Z is not 582 large enough, it won't be possible for one of its packets to meet 583 all the other shaped flows and if the number of hops is larger 584 than what's required there won't be any other shaped flows to meet 585 there. For the flow from A to B to meet every other ingress stream 586 as it traverses a path of H hops: 588 (EQ 11) Hx(N-1) = MxN - 1 590 Jacobson, Nichols & Poduri Expires: August, 2000 [page 11 ] 591 then compute the maximum jitter as: 593 (EQ 12)jitter = Hx(N-1)x(time to send an EF packet on each link) 595 If the total number of ingress streams exceeds Hx(N-1) + 1, then 596 it's not possible to meet all the other streams and the maximum 597 jitter is 599 (EQ 13)jitterworst case = H x (N-1) x fT/(number of ingress-shaped EF flows on each link) 601 Otherwise the max jitter is 603 (EQ 14)jitterworst case = (MxN - 1) x fT/(number of ingress-shaped EF flows on each link) 605 Then the maximum jitter depends on the number of hops or the num- 606 ber of border routers. In this construction, the number of 607 ingress-shaped EF flows on each link is N, thus: 609 (EQ 15)jitterworst case < smaller of (HxfT, MxfxT) 611 Dividing out T gives jitter in terms of the number of ingress 612 flow cycle times (or virtual packet times). Then, for the jitter 613 to exceed the cycle time (or 20 ms for our VoIP example), 615 (EQ 16)fxH > 1 and fxM > 1 617 If f were at its maximum of 0.5, then it appears to be easy to 618 exceed a cycle time of jitter across a domain. However, it's use- 619 ful to examine what f might typically be. Note that for this con- 620 struction: 622 (EQ 17)f= NxR/B 624 For our example voice flows, a reasonable R is 28-32 Kbps. Then, 625 for a link of 128 Kbps, f = 0.25xN; for 1.5 Mbps, f = 0.02xN; for 626 10 Mbps, f = 0.003xN; for 45 Mbps, f = 0.0007xN; and for 100 Mbps, 627 f = 0.0003xN. Then such a network of DS3 links can handle almost 628 1500 individual shaped flows at this rate. Another way to look at 629 this is that the hop count times the number of ingress ports of 630 each router must exceed the link bandwidth divided by the VoIP 631 rate in order to have a maximum jitter of a packet time at the 632 VoIP rate. 634 (EQ 18)HxN > B/R 636 For a network of all T1 links, this becomes HxN > 50 and for 637 larger bandwidth links, it increases. 639 Suppose that the ingress flows are not the same rate. If the allo- 640 cation, f, is at its maximum, then this means the number of 641 ingress flows must decrease. For example, if the A to Z flow is 642 10xR, then it will meet 9 fewer packets as it traverses the net- 643 work. Even though the assumptions behind this case are not realis- 645 Jacobson, Nichols & Poduri Expires: August, 2000 [page 12 ] 646 tic, we can see that the jitter can be kept to a reasonable 647 amount. The rules of the EF PHB and the VW BA should make it easy 648 to compute the worst case jitter for any topology and allocation. 650 6.1.1.4 Achievablility of the maximum 652 Now that we've examined how to compute the worst case jitter, we 653 look at how likely it is that this worst case happens and how it 654 relates to the jitter window. 656 In addition to the topological and allocation assumptions that 657 were made in order to allow a flow to have the opportunity of 658 meeting every other flow, events must align so that the meeting 659 actually happens at each hop. If we could assume independence of 660 the timing of each flow's arrival within an interval of T, then 661 that probability is on the order of (fT/N)N For this to happen at 662 every hop we need the joint probability of this happening at all H 663 nodes. Further we need the joint probability of that event in com- 664 bination with an adjacent packet not meeting any other packets. 665 For each additional hop, the number of ways the packets can com- 666 bine increases exponentially, thus the probability of that par- 667 ticular worst case combination decreases. 669 6.1.1.5 Jitter from non-VW packets 671 The worst case occurs when one packet of a flow waits for no other 672 packets to complete and the adjacent packet arrives at every hop 673 just as an MTU-sized non-EF packet has begun transmission. That 674 worst case jitter is the sum of the times to send MTU-sized pack- 675 ets at the link bandwidth of all the hops in the path or, for 676 equal bandwidth paths, 678 (EQ 19)jitter = HxMTU/B 680 Note that if one link has a bandwidth much smaller than the oth- 681 ers, that term will dominate the jitter. 683 If we assume that the MTU is on the order of 10-20 times the voice 684 packet size in our example, then the time to send an MTU on a link 685 is 10 or 20 times fxT/N so that our jitter bound becomes 20 x H x 686 fxT/N. 688 What has to happen in order to achieve the worst case? For jitter 689 against the default traffic, one packet waits for no default traf- 690 fic and the adjacent packet arrives just as an MTU of the default 691 type begins transmission on the link. 693 The worst case is linear in the number of hops, but since the 694 joint probability of an EF packet arriving at each queue precisely 695 at the start of a non-EF packet on the link decreases in hop 696 count, measured or simulated jitter will be seen to grow as a neg- 697 ative exponential of the number of hops in a path, even at very 698 high percentiles of probability. The reason for this is that the 700 Jacobson, Nichols & Poduri Expires: August, 2000 [page 13 ] 701 number of ways that the packets can arrive at the EF queue grows 702 as pH so the probability is on the order of p-H. When the link 703 bandwidth is small, it may be necessary to fragment non-EF packet 704 to control jitter. 706 How should we relate jitter in terms of source cycle times or vir- 707 tual packet times to the jitter window defined in section 3.0? 708 Note that we can write 710 (EQ 20)jitter window = Sx(1/R - 1/((nxR)/f) ) 712 and noting that T = S/R, we get: 714 (EQ 21)jitter window = Tx(n-f/n) 716 So that, in many cases, the jitter window can be approximated by 717 T. 719 6.2 Quantifying Jitter through Simulation 721 Section 1 derived and discussed the worst-case jitter for indi- 722 vidual flows of a diffserv behavior aggregate (BA) based on the EF 723 PHB. We showed that the worst case jitter can be bounded and cal- 724 culated these theoretical bounds. The worst case bounds represent 725 possible, but not likely, values. Thus, to get a better feel for 726 the likely worst jitter values, we used simulation. 728 We use the ns-2 network simulator; our use of this simulator has 729 been described in a number of documents [NS2,FBK,RFC2415]. The 730 following subsections describe the simulation set-up for these 731 particular experiments. 733 6.2.1 Topology 735 Figure 8 shows the topology we used in the simulations. A and Z 736 are edge routers through which traffic from various customers 737 enters and exits the Diffserv cloud. We vary the topology within 738 the Diffserv cloud to explore the worst-case jitter for EF traffic 739 in various scenarios. Jitter is measured on a flow or set of 740 flows that transit the network from A to Z. To avoid per hop syn- 741 chronizations, half the DE traffic at each hop is new to the path 742 while half of the DE traffic exits the path. For the mixed EF and 743 DE simulations, half the EF flows go from A to Z while, at each 744 hop, the other half of the 10% rate only crosses the path at that 745 hop. As discussed in section 1, this is an unlikely construction 746 but we undertake it to give a more pessimistic jitter For the EF- 747 only simulations, we emulate the case analyzed in section 1.1.3 by 748 measuring jitter on one end to end flow and having (N-1) new EF 749 flows meet that flow at every hop. Note that N is determined by 750 the maximum number of 28 kbps flows that can fit in the EF share 751 of each link, so N=share x bandwidth/28 kbps. 753 Jacobson, Nichols & Poduri Expires: August, 2000 [page 14 ] 754 Figure 8: Simulated topology 756 6.2.2 Traffic 758 Traffic is generated to emulate G.729 voice flows with packet size 759 (B) of 68 Bytes and a 20 ms packetization rate. The resultant 760 flows have a rate of 27 Kbps. As previously discussed, jitter 761 experienced by the voice flows has two main components; jitter 762 caused by meeting others flows in the EF queue, and jitter due to 763 traffic in other low prioirity classes. To analyze the first com- 764 ponent, we vary the multiplexing level of voice flows that are 765 admitted into the DS domain and for the second, we generate data 766 traffic for the default or DE PHB. Since we are interested in 767 exploring the worst case jitter, data traffic is generated as 768 long-lived TCP connections with 1500 Byte MTU segments. Current 769 measurements show real Internet traffic consists of a mixture of 770 packet sizes, over 50% of which are minimum-sized packets of 40 771 bytes and over 80% of which are much smaller than 1500 Bytes 772 [CAIDA]. Thus a realistic traffic mix would only improve the jit- 773 ter that we see in the simulations. 775 6.2.3 Schedulers and Queues 777 All the nodes(routers) in the network have the same configura- 778 tion: a simple Priority Queue (PQ) scheduler with two queues. 779 Voice traffic is queued in the high priority queue while the data 780 traffic is queued in the queue with the lower priority. The sched- 781 uler empties all the packets in the high priority queue before 782 servicing the data packets in a lower priority queue. However, if 783 the scheduler is busy servicing a data packet at the time of 784 arrival of a voice packet, the voice packet is served only after 785 the data packet is serviced completely, i.e., the scheduler is 786 non-preemptive. For priority queuing where the low priority queue 787 is kept congested, simulating two queues is adequate. 789 Figure 9: Link scheduling in the simulations 791 6.2.4 Results 793 In the following simulations, three bandwidth values were used 794 for the DS domain links: 1.5 Mbps, 10 Mbps, and 45 Mbps. Unless 795 otherwise stated, the aggregate of EF traffic was allocated 10% of 796 the link bandwidth. The hops per path was varied from 1 to 24. 797 Then, the 1.5 Mbps links can carry about 5 voice flows, the 10 798 Mbps about 36 voice flows, and 45 Mbps about 160. 800 6.2.4.1 Jitter due to other voice traffic only 802 To see the jitter that comes only from meeting other EF-marked 803 packets, we simulated voice traffic only. Figure 10 shows results 804 from 10 Mbps links with 10% of the link share assigned to the 805 voice flows. For a single bottleneck link in a dumbbell, the worst 807 Jacobson, Nichols & Poduri Expires: August, 2000 [page 15 ] 808 case jitter possible for this scenario is 2 ms. Note that the val- 809 ues in Figure 10 are far less than that. This source of jitter is 810 quite small, particularly compared to the jitter from traffic in 811 other queue(s) as we will see in the next section. (Note: Figure 812 10's results are quite preliminary. Further simulations will be 813 performed that jitter the individual sources slightly.) 815 Figure 10: Jitter from meeting other EF-marked traffic 817 6.2.4.2 Jitter in a voice flow where there is a congested default class 819 Our traffic model for the DE queue keeps it full with mostly 1500 820 byte packets. From section 1, the worst case jitter is equal to 821 the number of hops times the time to transmit a packet at the link 822 rate. The likelihood of this worst case occuring goes down expo- 823 nentially in hop count, and the simulations confirm this. Figure 824 11 shows several percentiles of the jitter for 10 Mbps links where 825 the time to transmit an MTU at link speed is 1.2 ms. 827 Figure 11: Various percentile jitter values for 10 Mbps links and 10% allocation 829 Recall that the period of the voice streams is 20 ms and note 830 that, the jitter does not even reach half a period. The median 831 jitter gets quite flat with number of hops. Although the higher 832 percentile values increase at a somewhat higher rate with number 833 of hops, it still does not approach the calculated worst case. The 834 data is also shown normalized by the MTU transmission time at 10 835 Mbps. Now the vertical axis value is the number of MTU sized pack- 836 ets of jitter that the flow experiences. This normalization is 837 presented to make it easier to relate the results to the analysis, 838 though it obscures the impact (or lack thereof) of the jitter on 839 the 20 ms flows. 841 Figure 12 shows the same results for 1.5 Mbps links and Figure 13 842 for 45 Mbps links. 844 Figure 12: Various percentiles of jitter for 1.5 Mbps links and 10% share 846 Notice that the worst case jitter for the 1.5 Mbps link is on the 847 order of two cycle times while, for 45 Mbps, it is less than 10% 848 of the cycle time. However, the behavior in terms of number of 849 MTUs is similar. 851 Figure 13: Various percentiles of jitter for 45 Mbps links and 10% share 853 The jitter in time and thus as a fraction of the virtual packet 854 time of the flow being measured clearly increases with decreasing 855 bandwidth. Even the smallest bandwidth, 1.5 Mbps can handle 856 nearly all jitter with a jitter buffer of 2 packets. The two 857 higher bandwidths don't even jiter by one virutal packet time, 858 thus staying within the jitter window. Figures 14, 15, and 16 com- 859 pare the median, 99th percentile and 99.97th percentile (essen- 860 tially the worst case). It's also interesting to normalize the 862 Jacobson, Nichols & Poduri Expires: August, 2000 [page 16 ] 863 results of each experiment by the MTU transmission time at that 864 link bandwidth. The normalized values show that all scenarios 865 experience the same behavior relative to the MTU transmission 866 time. 868 Figure 14: Median jitter for all three bandwidths by time and normalized 870 Figure 15: 99th percentile of jitter for the three bandwidths; absolute time and normalized 872 Figure 16: 99.97th percentile of jitter; absolute time and normalized by MTU transmission times 874 The simulation experiments are not yet complete, but they clearly 875 show the probability of acheiveing the worst case jitter decreas- 876 ing with hop count and show that jitter can be controlled. The 877 normalization shows that the jitter behavior is the same regard- 878 less of bandwidth. The absolute times differ by scale factors that 879 depend on the bandwith. 881 6.2.4.3 Jitter with an increased allocation 883 In the following, the experiments of the last section are 884 repeated, but using a 20% link share, rather than a 10% link share 885 Figure 17 shows the jitter percentiles for 10 Mbps links and a 20% 886 share. The values are also plotted with the 10% share results (on 887 the right hand side) to show how similar they are.. 889 Figure 17: Jitter percentiles for 10 Mbps links and 20% EF share 891 Using the previous section, we would believe that the results for 892 other bandwidths would have the same shape, but be scaled by the 893 bandwidth difference. Figure 18 shows this to indeed be the case. 894 Thus it is sufficient to simulated only a single bandwidth. 896 Figure 18: Jitter for 1.5 Mbps links (on left) and 45 Mbps links (on right) 898 In all the experiments, it can be clearly seen that the shape of 899 the jitter vs. hops curve flattens because the probability of the 900 worst case occuring at each hop decreases exponentially in hops. 901 To see if there is an allocation level at which the jitter behav- 902 ior diverges, we simulated and show results for allocations of 10, 903 20, 30, 40, and 50 percent, all for 10 Mbps links in figure 19. 905 Figure 19: Median and 99th percentile jitter for various allocations and 10 Mbps links 907 What may not be obvious from figure 19 is that the similarity 908 between the five allocation levels shows that jitter from other EF 909 traffic is negligible compared to the jitter from waiting for DE 910 packets to complete. Clearly, the probability of jitter from 911 other EF traffic goes up with increasing allocation level, but it 912 is so small compared to the DE-induced jitter that it isn't visi- 913 ble except for the highest percentiles and the largest hop count. 915 Jacobson, Nichols & Poduri Expires: August, 2000 [page 17 ]