Internet Engineering Task Force Van Jacobson Differentiated Services Working Group Kathleen Nichols Packet Design, Inc. Internet Draft Kedar Poduri Expires Jan., 2001 Cisco Systems, Inc. draft-ietf-diffserv-pdb-vw-00.txt July, 2000 The `Virtual Wire' Per-Domain Behavior Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC2026. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other docu- ments at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http:// www.ietf.org/ietf/1id-abstracts.txt. The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/ shadow.html. Distribution of this memo is unlimited. Abstract This document describes an edge-to-edge behavior, in diffserv terminology a per-domain behavior, called `Virtual Wire' (VW) that can be constructed in any domain supporting the diffserv EF PHB plus appropriate domain ingress policers. The VW behavior is essentially indistinguishable from a dedicated circuit and can be used anywhere it is desired to replace dedicated circuits with IP transport. Although one attribute of VW is the delivery of a peak rate, in VW this is explicitly coupled with a bounded jitter attribute. The document is a edited version of the earlier draft-ietf-diff- serv-ba-vw-00.txt with a new name to reflect a change in Diffserv WG terminology. A pdf version of this document is available at ftp://ftp.packet- design.com/ietf/vw_pdb_0.pdf 1.0 Introduction [RFC2598] describes a diffserv PHB called expedited forwarding (EF) intended for use in building a scalable, low loss, low latency, low jitter, assured bandwidth, end-to-end service that appears to the endpoints like an unshared, point-to-point connec- Jacobson, Nichols and Poduri Expires: January, 2001 [page 1 ] INTERNET DRAFT draft-ietf-diffserv-pdb-vw-00.txt July, 2000 tion or `virtual wire.' For scalability, a diffserv domain sup- plying this service must be completely unaware of the individual endpoints using it and sees instead only the aggregate EF marked traffic entering and transiting the domain. This document pro- vides the specifications necessary on that aggregated traffic (in diffserv terminology, a per-domain behavior or PDB) in order to meet these requirements and thus defines a new pdb, the Virtual Wire per-domain behavior or VW PDB. Despite the lack of per-flow state, if the aggregate input rates are appropriately policed and the EF service rates on interior links are appropriately config- ured, the edge-to-edge service supplied by the domain will be indistinguishable from that supplied by dedicated wires between the endpoints. This note gives a quantitative definition of what is meant by `appropriately policed and configured'. Network hardware has become sufficiently reliable that the over- whelming majority of network loss, latency and jitter are due to the queues traffic experiences while transiting the network. Therefore providing low loss, latency and jitter to a traffic aggregate means ensuring that the packets of the aggregate see no (or very small) queues. Queues arise when short-term traffic arrival rate exceeds departure rate at some node(s). Thus ensur- ing no queues for a particular traffic aggregate is equivalent to bounding rates such that, at every transit node, the aggregate's maximum arrival rate is less than that aggregate's minimum depar- ture rate. These attributes can be ensured for a traffic aggregate by using the VW PDB. Creating the VW PDB has two parts: 1. Configuring individual nodes so that the aggregate has a well-defined minimum departure rate. (`Well-defined' means independent of the dynamic state of the node. In particular, independent of the intensity of other traffic at the node.) 2. Conditioning the entire DS domain's aggregate (via policing and shaping) so that its arrival rate at any node is always less than that node's configured minimum departure rate. [RFC2598] provides the first part. This document describes how one configures the EF PHBs in the collection of nodes that make up a DS domain and the domain's boundary traffic conditioners (described in [RFC2475]) to provide the second part. This description results in a diffserv per-domain behavior, as described in [PDBDEF]. This document introduces and describes VW informally via pictures and examples rather than by derivation and formal proof. The intended audience is ISPs and router builders and the authors feel this community is best served by aids to developing a strong intu- ition for how and why VW works. However, VW has a simple, formal description and its properties can and have been derived quite rigorously. Such papers may prove interesting, but are outside Jacobson, Nichols and Poduri Expires: January, 2001 [page 2 ] INTERNET DRAFT draft-ietf-diffserv-pdb-vw-00.txt July, 2000 the intent of this document. The VW PDB has two major attributes: an assured peak rate and a bounded jitter. It is possible to define a different PDB with only the first of these, a "constant bit-rate" PDB, but this is not the objective of this document. The next sections describe the VW PDB in detail and give examples of how it might be implemented. The keywords "MUST", "MUST NOT", "REQUIRED", "SHOULD", "SHOULD NOT", and "MAY" that appear in this document are to be interpreted as described in [RFC2119]. 2.0 Description of the Virtual Wire PDB 2.1 Applicability A Virtual Wire (VW) PDB is intended to send "circuit replacement" traffic across a diffserv network. That is, this PDB is intended to mimic, from the point of view of the originating and terminat- ing nodes, the behavior of a hard-wired circuit of some fixed capacity. It does this in a scalable (aggregatable) way that doesn't require `per-circuit' state to exist anywhere but the ingress router adjacent to the originator. This PDB should be suitable for any packetizable traffic that currently uses fixed circuits (e.g., telephony, telephone trunking, broadcast video distribution, leased data lines) and packet traffic that has sim- ilar delivery requirements (e.g., IP telephony or video confer- encing). Thus the conceptual model of the VW PDB is as shown in Figure 1: some portion (possibly all) of a physical wire between a sender and receiver is replaced by a (higher bandwidth) DS domain implementing VW in a way that is invisible to S, R or the circuit infrastructure outside of the cloud. Figure 1: VW conceptual model 2.2 Rules The VW PDB uses the EF PHB to implement a transit behavior with the required attributes. Each node in the domain MUST implement the EF PHB as described in section 2 of [RFC2598] but with the SHOULDs of that section taken as MUSTs. Specifically, RFC2598 states "The EF PHB is defined as a forwarding treatment for a par- ticular diffserv aggregate where the departure rate of the aggre- gate's packets from any diffserv node must equal or exceed a configurable rate." The EF traffic SHOULD receive this rate inde- pendent of the intensity of any other traffic attempting to tran- sit the node. It SHOULD average at least the configured rate when measured over any time interval equal to or longer than the time it takes to send an output link MTU sized packet at the configured rate." This leads to an "EF bound" on the delay that EF-marked packets can experience at each node that is inversely propor- tional to the configured EF rate for that link. Jacobson, Nichols and Poduri Expires: January, 2001 [page 3 ] INTERNET DRAFT draft-ietf-diffserv-pdb-vw-00.txt July, 2000 The bandwidth limit of each output interface SHOULD be configured as described in Section 2.4 of this document. In addition, each domain boundary input interface that can be the ingress for EF marked traffic MUST strictly police that traffic as described in Section 2.4. Each domain boundary output interface that can be the egress for EF marked traffic MUST strictly shape that traffic as described in Section 2.4. 2.3 Attributes Colloquially, "the same as a wire." That is, as long as packets are sourced at a rate <= the virtual wire's configured rate, they will be delivered with a high degree of assurance and with almost no distortion of the interpacket timing imposed by the source. However, any packets sourced at a rate greater than the VW config- ured rate, measured over any time scale longer than a packet time at that rate, will be unconditionally discarded. 2.4 Parameters This section develops a parameterization of VW in terms of measur- able properties of the traffic (i.e., the packet size and physical wire bandwidth) and domain (the link bandwidths and EF transit bound of each of the domain's routers). We will show that: 1. There is a simple formula relating the circuit bandwidth, domain link bandwidths, packet size and maximum tolerable `jit- ter' across the domain, and this jitter bound holds for each packet individually - there is no interpacket dependence. 2. This formula and the EF bound described in [RFC2598] deter- mine the maximum VW bandwidth that can be allocated between some ingress and egress of the domain. (This is because the EF bound is essentially a bound on the worst-case jitter that will be seen by EF marked packets transiting some router and the formula says that any three parameters from the set determine the fourth.) 3. When the ingress VW flows are allocated and policed so as to ensure that this maximum VW bandwidth is not exceeded at any node of the domain, the EF BA on a link exiting a node can con- sist of an arbitrary aggregate of VW flows (i.e., no per-flow state is needed) because there is no perturbation of the aggre- gate's service order that will cause any of the constituent flows to exceed its domain transit jitter bound. 2.4.1 The Jitter bound and `Jitter Window' for a single VW circuit (flow) Figure 2: Time structure of packets of a CBR stream at a high to low bandwidth transition Jacobson, Nichols and Poduri Expires: January, 2001 [page 4 ] INTERNET DRAFT draft-ietf-diffserv-pdb-vw-00.txt July, 2000 Figure 2 shows a CBR stream of size S packets being sourced at rate R. At the domain egress border router, the packets arrive on a link of bandwidth B (= nR) and depart to their destination on a link of bandwidth R. Figure 3: Details of arrival / departure relationships Figure 3 shows the detailed timing of events at the router. At time T0 the last bit of packet 0 arrives so output is started on the egress link. It will take until time for packet 0 to be completely output. As long as the last bit of packet 1 arrives at the border router before , the destination node will find the traffic indistinguishable from a stream carried the entire way on a dedicated wire of bandwidth R. This means that packets can be jittered or displaced in time (due to queue waits) as they cross the domain and that there is a jitter window at the border router of duration (EQ 1) that must bound the sum of all the queue waits seen be a packet as it transits the domain. As long as this sum is less than , the destination will see service identical to a dedicated wire. Note that the jitter window is (implicitly) computed relative to the first packet of the flight of packets departing the boundary router and, thus, can only include variable delays. Any transit delay experienced by all the packets, be it propagation time, router forwarding latency, or even average queue waits, is removed by the relative measure so the sum described in this para- graph is not sensitive to delay but only to delay variation. Also note that when packets enter the domain they are already separated by so, effectively, everything is pushed to the left edge of the jitter window and there's no slack time to absorb delay vari- ation in the domain. However by simply delaying the output of the first packet to arrive at E by one packet time (S/R), the phase reference for all the traffic is reset so that all subsequent packets enter at the right of their jitter window and have maximum slack time during transit. Figure 4: Packet timing structure edge-to-edge Figure 4 shows the edge-to-edge path from the source to the desti- nation. The links from S to I and E to D run at the virtual wire rate R (or the traffic is shaped to rate R if the links run at a higher rate). The solid rectangles on these links indicate the packet time S/R. The dotted lines carry the packet times across the domain since the time boundaries of these virtual packets form the jitter window boundaries of the actual packets (whose dura- tion and spacing are shown by the solid rectangles below the intra-domain link). Note that each packet's jitter is indepen- dent. E.g., even though the two packets about to arrive at E have been displaced in opposite directions so that the total time Jacobson, Nichols and Poduri Expires: January, 2001 [page 5 ] INTERNET DRAFT draft-ietf-diffserv-pdb-vw-00.txt July, 2000 between them is almost , neither has gone out of its jitter win- dow so the output from E to D will be smooth and continuous. The preceding derives the jitter window in terms of the bandwidths of the ingress circuit and intra-domain links. In practice, the `givens' are more likely to be the intradomain link bandwidths and the jitter window (which can be no less than the EF bound associ- ated with each output link that might be traversed by some VW flow(s)). Rearranging Equation 1 based on this gives R, the maxi- mum amount of bandwidth that can be allocated to the aggregate of all VW circuits, as a function of the EF bound (= jitter window = ): (EQ 2) Note that the upper bound on VW traffic that can be handled by any output link is simply the MTU divided by the link's EF bound. 2.4.2 Jitter independence under aggregation Figure 5: Three VW customers forming an aggregate This jitter independence is what allows multiple `virtual wires' to be transparently aggregated into a single VW PDB. Figure 5 shows three independent VW customers, blue, yellow and red, entering the domain at I. Assume that their traffic has worst-case phasing, i.e., that one packet from each stream arrives simulta- neously at I. Even if the output link scheduler makes a random choice of which packet to send from its EF queue, no packet will get pushed outside its jitter window. For example, in Figure 5 node I ships a different perturbation of the 3 customer aggregate in every window yet this has no effect on the edge-to-edge VW properties). The jitter independence means that we only have to compare the jitter window of Equation 1 to the worst case of the total queue wait that can be seen by a single VW packet as it crosses the domain. There are three potential sources of queue wait for a VW packet: 1. it can queue behind non-EF packets (if any) 2. it can queue behind another VW packet from the same customer 3. it can queue behind VW packet(s) from other customers For case (1), the EF `priority queuing' model says that the VW traffic will never wait while a non-EF queue is serviced so the only delay it can experience from non-EF traffic is if it has to wait for the finish of a packet that was being sent at the time it arrived. For an output link of bandwidth B, this can impose a Jacobson, Nichols and Poduri Expires: January, 2001 [page 6 ] INTERNET DRAFT draft-ietf-diffserv-pdb-vw-00.txt July, 2000 worst-case delay of S/B. Note that this implies that if the (low bandwidth) links of a network are carrying both VW and other traf- fic, then n in Equation 1 must be at least 2 (i.e., the EF bound can be at most half the link bandwidth) in order to make the jit- ter window large enough to absorb this delay. Case (2) can only happen if the previous packet hasn't completely departed at the time the next packet arrives. Since each ingress VW stream is strictly shaped to a rate R, any two packets will be separated by at least time S/R so having leftovers is equivalent to saying the departure rate on some link is R over any time scale of S/R or longer so this can't hap- pen for any legal VW/EF configuration. Or, to put it another way, if case (2) happens, either the VW policer is set too loosely or some link's EF bound is set too tight. Case (3) is a simple generalization of (2). If there are a total of n customers, the worst possible queue occurs if all n arrive simultaneously at some output link. Since each customer is indi- vidually shaped to rate R, when this happens then no new packets from any stream can arrive for at least time S/R. At the end of this time, there can only be leftover packets in the queue if the departure rate < nR over this time scale. Conforming to the EF property (restated in section 2.2) means that any link capable of handling the aggregate traffic must have a departure rate > nR over any time scale longer than S/(nR) so, again, this can't hap- pen in any legal VW/EF configuration. For case (1), a packet could be displaced by non-EF traffic once per hop so the edge-to-edge jitter is a function of the path length. But this isn't true for case (3): The strict ingress policing implies that a packet from any given VW stream can meet any other VW stream in a queue at most once. This means the worst case jitter caused by aggregating VW customers is a linear func- tion of the number of customers in the aggregate but completely independent of topology. 2.4.3 Topological effects on allocation Although the jitter caused by aggregating VW customers is inde- pendent of topology, the number of customers and/or bandwidth per customer is very sensitive to topology and the topological effects may be subtle. Equation 2 gives the aggregate VW that can traverse any link but if there are n customers, the topology and their (possible) paths through it determine how this bandwidth divided among them. Figure 6: Cumulative jitter from spatially distinct flows The first thought is to simply divide the aggregate bandwidth by the customer in-degree at some link. E.g., in Figure 5 there are three customers aggregated into the I>E link so each should get a Jacobson, Nichols and Poduri Expires: January, 2001 [page 7 ] INTERNET DRAFT draft-ietf-diffserv-pdb-vw-00.txt July, 2000 third of the available VW bandwidth. But Figure 6 shows that this is too optimistic. Note that the yellow flow (I>E) gets jittered one packet time when it meets the blue flow (I>2) then an addi- tional packet time when it meets the red flow (3>4). So even though the maximum in-degree is two and the largest possible aggregate has only two components, the combined interactions require that each customer get at most 1/3 of the available VW bandwidth rather than 1/2. In general, if nj is the total number of other customers encountered (or potentially encountered) by customer j as it traverses the domain, then the bandwidth shares can be at most . It is possible to `tune' the topology to trade off total VW band- width vs. reliability. For example in Figure 7, if the SF>NY VW traffic is constrained (via route pinning or tunneling) to only follow the northern path and LA>DC to only follow the southern path, then each customer gets the entire VW bandwidth on their path but at the expense of neither being able to use the alternate path in the event of a link failure. If they want to take advan- tage of the redundancy, only half the bandwidth can be allocated to each even though the full bandwidth will be available most of the time. Mixed strategies are also possible. For example the SF>NY customer could get an expensive SLA that guaranteed the full VW bandwidth even under a link failure and LA>DC could get a cheap SLA that gave full bandwidth unless there was a link failure in which case it gave nothing. Figure 7: bandwidth vs. redundancy trade-off 2.4.4 Per-customer bandwidth and/or packet size variation Figure 8: Aggregating VW flows with different bandwidth shares In the last example, customers could get different VW shares because their traffic was engineered to be disjoint. But when cus- tomers with different shares transit the same link(s), there can be problems. For example, Figure 8 shows blue and red customers allocated 1/4 share each while yellow gets a 1/2 share. Since yel- low's share is larger, its jitter window is smaller (the dotted yellow line). Since the packets from a customer can appear any- where in the jitter window, it's perfectly possible for packets from red, blue and yellow to arrive simultaneously at I. Since I has no per-customer state, the serving order for the three is ran- dom and it's entirely possible that blue and red will be served before yellow. But since yellow's jitter window is only two link packet times wide, this results in no packets in its first window and two in its second so its jitter bound is violated. There are at least three different ways to deal with this: 1. Make all customers use the smallest jitter window. This is equivalent to provisioning based on the number of customers times the max customer rate rather than on the sum of the cus- tomer rates. In bandwidth rich regions of the cloud this is Jacobson, Nichols and Poduri Expires: January, 2001 [page 8 ] INTERNET DRAFT draft-ietf-diffserv-pdb-vw-00.txt July, 2000 probably the simplest solution but in bandwidth poor regions it can result in denying customers that there is capacity to accept. 2. Utilize a set of LU DSCPs to create an EF-like code point per rate and service them in rate magnitude order. For a small set of customer rates this makes full use of the capacity at the expense of additional router queues (one per code point). 3. Separate rate and jitter bounds in the SLA. I.e., base the jitter bound on the packet time of the minimum customer rate (which is equivalent to making all customers use the largest jitter window). This effectively treats the larger customers as if their traffic were an aggregate of min rate flows which may be the appropriate choice if the flow is indeed an aggregate, e.g., a trunk containing many voice calls. 2.5 Assumptions The topology independence of the VW PDB holds only while routing is relatively stable. Since packets can be duplicated while rout- ing is converging, and since path lengths can be shorter after a routing change, it is possible to violate the VW traffic bounds and thus jitter stream(s) more than their jitter window for a small time during and just after a routing change. The derivation in the preceding section assumed that the VW PDB was the only user of EF in the domain. If this is not true, the provisioning and allocation calculations must be modified to account for the other users of EF. 2.6 Example uses An enterprise could use VW to provision a large scale, internal VoIP telephony system. Say for example that the internal links are all Fast Ethernet (100Mb/s) or faster and arranged in a 3 level hierarchy (switching/aggregation/routing) so the network diameter is 5 hops. Typical telephone audio codecs deliver a packet every 20ms. At this codec rate, RTP encapsulated G.711 voice is 200 byte packets & G.729 voice is 60 byte packets. 20ms at 100 Mb/s is 250 Kbytes (~150 MTUs, ~1200 G.711 calls or ~4,000 G.729 calls) which would be the capacity if the net were carrying only VW telephony traffic. Worse case jitter from other traffic through a diameter 5 enterprise is 5 MTU times or 0.6 ms leaving between 19 ms (optimistic) to 10 ms (ultra conservative - see scaling notes in the appendix) for VW. 10ms at 100Mb/s is 125Kbytes so using the most conservative assumptions we can admit ~600 G.711 or ~2000 G.729 calls if the ingress can simultaneously police both packet & bit rate. If the ingress can police only one of these, we can only admit ~75 calls because each packet might be as long as an MTU. Jacobson, Nichols and Poduri Expires: January, 2001 [page 9 ] INTERNET DRAFT draft-ietf-diffserv-pdb-vw-00.txt July, 2000 2.7 Environmental concerns Routing instability will generally translate directly into VW service degradation. Multipath routing of VW will, in general, increase the jitter and degrade the service unless either the paths are exactly the same length (so there is no effect on jitter) and/or the routing deci- sion is such that it always sends any particular customer down the same path. The analysis in Section 2.4 would hold in a world where traffic policers and link schedulers are perfect and mathematically exact. When computing parameters for our world, 5-10% fudge fac- tors should be used. 3.0 Security Considerations There are no security considerations for the VW PDB other than those associated with the EF PHB which are described in [RFC2598]. 4.0 References [RFC2119] "Key words for use in RFCs to Indicate Requirement Lev- els", S.Bradner, www.ietf.org/rfc/rfc2119 [RFC2474] "Definition of the Differentiated Services Field (DS Field) in the IPv4 and IPv6 Headers", K.Nichols, S. Blake, F. Baker, D. Black, www.ietf.org/rfc/rfc2474.txt [RFC2475] "An Architecture for Differentiated Services", S. Blake, D. Black, M.Carlson,E.Davies,Z.Wang,W.Weiss, www.ietf.org/rfc/rfc2475.txt [RFC2597] "Assured Forwarding PHB Group", F. Baker, J. Heinanen, W. Weiss, J. Wroclawski, ftp://ftp.isi.edu/in-notes/ rfc2597.txt [RFC2598] "An Expedited Forwarding PHB", V.Jacobson, K.Nichols, K.Poduri, ftp://ftp.isi.edu/in-notes/rfc2598.txt [RFC2638] "A Two-bit Differentiated Services Architecture for the Internet", K. Nichols, V. Jacobson, and L. Zhang, www.ietf.org/rfc/rfc2638.{txt,ps} [PDBDEF] "Definition of Differentiated Services Per-domain Behav- iors and Rules for their Specification", K.Nichols, B.Carpenter, draft-ietf-diffserv-pdb-def-00.[txt, pdf] [CAIDA] The nature of the beast: recent traffic measurements from an Internet backbone. K Claffy, Greg Miller and Kevin Thompson. http://www.caida.org/Papers/Inet98/index.html Jacobson, Nichols and Poduri Expires: January, 2001 [page 10 ] INTERNET DRAFT draft-ietf-diffserv-pdb-vw-00.txt July, 2000 [NS2] The simulator ns-2, available at: http://www-mash.cs.ber- keley.edu/ns/. [FBK] K. Nichols, "Improving Network Simulation with Feedback", Proceedings of LCN'98, October, 1998. [RFC2415] RFC 2415, K. Poduri and K. Nichols, "Simulation Studies of Increased Initial TCP Window Size", September, 1998. 5.0 Authors' Addresses Van Jacobson Packet Design, Inc. 66 Willow Place Menlo Park, CA 94025 van@packetdesign.com Kathleen Nichols Packet Design, Inc. 66 Willow Place Menlo Park, CA 94025 nichols@packetdesign.com Kedar Poduri Cisco Systems, Inc. 170 W. Tasman Drive San Jose, CA 95134-1706 poduri@cisco.com 6.0 Appendix: On Jitter for the VW PDB The VW PDB's bounded jitter translates into the generally useful properties of network bandwidth limits and buffer resource lim- its. These properties make VW useful for a variety of statically and dynamically provisioned services, many of which have no intrinsic need for jitter bounds. IP telephony is an important application for the VW PDB where expected and worst-case jitter for rate-controlled streams of packets is of interest; thus this appendix is primarily focused on voice jitter. Rather than the "phase jitter" used in the body of this document, this appendix used "interpacket jitter" for a variety of reasons. This might be changed in a future version. Note that, as shown in section 2.4.1, the phase jitter can correct for a larger inter- packet jitter. The appendix focuses on jitter for individual flows aggregated in a VW PDB, derives worst-case bounds on the jitter, and gives sim- ulation results for jitter. 6.1 Jitter and Delay Jacobson, Nichols and Poduri Expires: January, 2001 [page 11 ] INTERNET DRAFT draft-ietf-diffserv-pdb-vw-00.txt July, 2000 The VW PDB is sufficiently restrictive in its rules to preserve the required EF per-hop behavior under aggregation. These proper- ties also make it useful as a basis for Internet telephony, to get low jitter and delay. Since a VW PDB will have link arrival rates that do not exceed departure rates over fairly small time scales, end-to-end delay is based on the transmission time of a packet on a wire and the handling time of individual network elements and thus is a function of the number of hops in a path, the bandwidth of the links, and the properties of the particular piece of equip- ment used. Unless the end-to-end delay is excessive due to very slow links or very slow equipment, it is usually the jitter, or variation of delay, of a voice stream that is more critical than the delay. We derive the worst case jitter for a a VW PDB in a DS domain using it to carry a number of rate-controlled flows. For this we use inter-packet jitter, defined as the absolute value of the dif- ference between the arrival time difference of two adjacent pack- ets and their departure time difference, that is: (EQ 3)jitter = |(ak-aj) - (dk-dj)| The maximum jitter will occur if one packet waits for no other packets at any hop of its path and the adjacent packet waits for the maximum amount of packets possible. There are two sources of jitter, one from waiting for other EF packets that may have accu- mulated in a queue due to simultaneous arrivals of EF packets on several input lines feeding the same queue and another from wait- ing for non-EF packets to complete. The first type is strictly bounded by the properties of the VW PDB and the EF PHB. The second type is minimized by using a Priority Queuing mechanism to sched- ule the output link and giving priority to EF packets and this value can be approached by using a non-bursty weighted round- robin packet scheduler and giving the EF queue a large weight. The total jitter is the sum of these two. Maximum jitter will be given across the domain in terms of T, the virtual packet time or cycle time. It is important to recall the analysis of section 2.0 showing that this jitter across the DS domain is completely invisible to the end-to-end flow using the VW PDB if it is within the jitter window at the egress router. 6.1.1 Jitter from other VW packets The jitter from meeting other packets of the VW aggregate comes from (near) simultaneous arrival of packets at different input ports all destined for the same output queue that can be com- pletely rearranged at the next packet arrival to that queue. This jitter has a strict bound which we will show here. It will be helpful to remember that, from RFC 2598, a PDB using the EF PHB will get its configured share of each link at all time scales above the time to send an MTU at the rate corresponding to Jacobson, Nichols and Poduri Expires: January, 2001 [page 12 ] INTERNET DRAFT draft-ietf-diffserv-pdb-vw-00.txt July, 2000 that share of that link. Focus on the DS domain of Figure 9. Unless otherwise stated, in this section assume M Boundary Routers, each having N inputs and outputs. We assume that each of the BR's ingress ports receives a flow of EF-marked packets that are being policed to a peak rate R. If each flow sends a fixed size packet, then it's possible to cal- culate the fixed time, T, between packets of each of these MxN flows that enters the DS domain, a quite reasonable assumption for packets carrying voice. For example, assume a domain traversed by MxN flows of 68 byte voice packets sent at 20 ms time intervals. Note we assume all ingress links have some packets that will be marked for the VW aggregate. Thus the total number of ingress EF- marked streams to the VW aggregate is I = MxN. To construct a network where the maximum jitter can occur, a sin- gle flow traversing the network must be able to meet packets from all the other flows marked for the EF PHB and it should be possi- ble to meet them in the worst possible way. Figure 9: A DS domain Unless otherwise stated, assume that all the routers of the domain have N inputs and outputs and that all links have the same band- width B. Although there are a number of ways that the individual streams from different egress ports might combine in the interior of the network, in a properly configured network, the arrival rate of the VW PDB must not exceed the departure rate at any network node. Consider a particular flow from A to Z and how to ensure that packets entering the VW PDB at A meet every other flow enter- ing the domain from all egress points as they traverse the domain to Z. Consider three cases: the first is a single bottleneck, the second makes no assumptions about routing in the network and the third assumes that the paths of individual flows can be completely specified. Assume there are H hops from A to Z and that delay is the minimum time it takes for a packet to go from A to Z in the absence of queuing. Both packets experience delay and thus it subtracts in the jitter calculation. Recall that the packets of the flow are separated in time by T, then (normalizing to a start time of 0): (EQ 4)dj = 0 (EQ 5)dk = T (EQ 6)aj = delay (EQ 7)ak = time spent waiting behind all other packets +delay+T Then we can use: (EQ 8)jitter = time spent waiting behind all other packets Jacobson, Nichols and Poduri Expires: January, 2001 [page 13 ] INTERNET DRAFT draft-ietf-diffserv-pdb-vw-00.txt July, 2000 as we explore calculating worst case jitter for different topolo- gies. That is, the worst case queueing delay can be used to bound the jitter. The next step is to establish some useful relationships between parameters. First, assume that some fraction, f, of a link's capacity is allocated to EF-marked packets. Since we are assuming that all the flows that are admitted into this DS domain's VW aggregate generate packets at a spacing of T, this can be expressed in time as fxT. Then the amount of time to send an EF packet on each link can be written as fxT/(total number of EF- marked flow crossing the link). Note that f should be less than 0.5 in order that an MTU-sized non-EF packet will not cause the EF condition to be violated. In the subsequent analysis, we will, in general, assume that the entire fraction f of EF traffic is present in order to calculate worst case bounds. 6.1.1.1 Worst case jitter in a network with a dumbbell bottleneck Consider a DS domain topology shown in Figure 10. In order for a packet of the (A,Z) flow to wait behind packets of all the other MxN - 1 flows, packets from each of these flows must be sitting in the router queue for the bottleneck link L when the (A,Z) packet arrives. Since N flows arrive on each of the M links, the lowest bound on the bandwidth B occurs when the N packets arrive in bursts. In this case, B must be large enough (relative to L) so that the packets are still sitting in L's queue when our (A,Z) packet arrives at the end of a burst of N packets, that is B > NxL. Then the (EQ 9)jitterworst case = MxNx(time to send an EF packet on L) Since we expressed the EF aggregate's allocation on L as fxL, the time to send an EF packet on L is (at most) fxT/(MxN), so (EQ 10)jitterworst case = fxT Figure 10: A dumbbell bottleneck This result shows that the worst case jitter will be less than half a packet time for any VW-compliant allocation on this topol- ogy. For the worst case to occur, all N packets must arrive at each of the M border routers within the time it takes to transmit them all on B (from above, this is bounded by fxT/N). By assuming independence, an interested person should be able to get some insight on the likelihood of this happening. Simulation results are included in a later section. 6.1.1.2 Worst case jitter in an arbitrary network Jacobson, Nichols and Poduri Expires: January, 2001 [page 14 ] INTERNET DRAFT draft-ietf-diffserv-pdb-vw-00.txt July, 2000 Consider the network of Figure 9 and in this case, one packet of the (A,Z) flow must arrive at the same time, but be queued behind a packet from each of the other flows as it passes through the network. This can happen at any link of the network and even at the same link. Assume all links have bandwidth B and that we don't know the path the individual EF packets or flows of the aggregate will follow. Then the worst case jitter is (EQ 11)jitterworst case = Ix(fxT/I) = fxT the same as the bottleneck case. In a somewhat pathological con- struct where two flows pass through the same link more than once, but take different paths between those links, we assume the pack- ets are serialized when they first meet and are not retimed by the disjoint paths to meet again. Although one could construct a case where the a particular packet queues behind another multiple times, a bit of thought should show that this is unlikely in the realm of applicability of the VW PDB. If the allocation can have knowledge that not all flows of the aggregate will take the same path, then one could allocate each link to a smaller number of flows, but this would also imply that the number of flows that it's possible to meet and be jittered by is smaller. Allocation can be kept to under 0.5 times the band- width of a core link, while the existence of multiple paths offers both fault tolerance and an expectation that the actual load on any link will be less than 0.5. How likely is this case to happen? One packet of the (A,Z) flow must encounter and queue behind every other individual shaped flow that makes up the domain's VW aggregate as it crosses the domain. 6.1.1.3 Maximal jitter in a network with "pinned" paths per flow Then at each hop the (A,Z) packet has to arrive at the same time as an EF packet from the (N-1) other inputs and the (A,Z) packet has to be able to end up anywhere within that burst of N packets. In particular, for two adjacent packets of the (A,Z) flow, one must arrive at the front of every hop's burst and the other at the end of every hop's burst. This clearly requires an unrealistic form of path pinning or route selection by every individual EF- marked flow entering the DS domain. This unidirectional path is shown in Figure 11 where all routers have N inputs and at each of the H routers on the path from A to Z, N-1 flows are sent to other output queues, while N-1 of the shaped input flows that have not yet crossed the A to Z path enter the router at the other input ports. Figure 11: Example path for maximal jitter across DS domain from A to Z It should be noted that if the number of hops from A to Z is not Jacobson, Nichols and Poduri Expires: January, 2001 [page 15 ] INTERNET DRAFT draft-ietf-diffserv-pdb-vw-00.txt July, 2000 large enough, it won't be possible for one of its packets to meet all the other shaped flows and if the number of hops is larger than what's required there won't be any other shaped flows to meet there. For the flow from A to B to meet every other ingress stream as it traverses a path of H hops: (EQ 12) Hx(N-1) = MxN - 1 then compute the maximum jitter as: (EQ 13)jitter = Hx(N-1)x(time to send an EF packet on each link) If the total number of ingress streams exceeds Hx(N-1) + 1, then it's not possible to meet all the other streams and the maximum jitter is (EQ 14)jitterworst case = H x (N-1) x fT/(number of ingress-shaped EF flows on each link) Otherwise the max jitter is (EQ 15)jitterworst case = (MxN - 1) x fT/(number of ingress-shaped EF flows on each link) Then the maximum jitter depends on the number of hops or the num- ber of border routers. In this construction, the number of ingress-shaped EF flows on each link is N, thus: (EQ 16)jitterworst case < smaller of (HxfT, MxfxT) Dividing out T gives jitter in terms of the number of ingress flow cycle times (or virtual packet times). Then, for the jitter to exceed the cycle time (or 20 ms for our VoIP example), (EQ 17)fxH > 1 and fxM > 1 If f were at its maximum of 0.5, then it appears to be easy to exceed a cycle time of jitter across a domain. However, it's use- ful to examine what f might typically be. Note that for this con- struction: (EQ 18)f= NxR/B For our example voice flows, a reasonable R is 28-32 Kbps. Then, for a link of 128 Kbps, f = 0.25xN; for 1.5 Mbps, f = 0.02xN; for 10 Mbps, f = 0.003xN; for 45 Mbps, f = 0.0007xN; and for 100 Mbps, f = 0.0003xN. Then such a network of DS3 links can handle almost 1500 individual shaped flows at this rate. Another way to look at this is that the hop count times the number of ingress ports of each router must exceed the link bandwidth divided by the VoIP rate in order to have a maximum jitter of a packet time at the VoIP rate. Jacobson, Nichols and Poduri Expires: January, 2001 [page 16 ] INTERNET DRAFT draft-ietf-diffserv-pdb-vw-00.txt July, 2000 (EQ 19)HxN > B/R For a network of all T1 links, this becomes HxN > 50 and for larger bandwidth links, it increases. Suppose that the ingress flows are not the same rate. If the allo- cation, f, is at its maximum, then this means the number of ingress flows must decrease. For example, if the A to Z flow is 10xR, then it will meet 9 fewer packets as it traverses the net- work. Even though the assumptions behind this case are not realis- tic, we can see that the jitter can be kept to a reasonable amount. The rules of the EF PHB and the VW PDB should make it easy to compute the worst case jitter for any topology and allocation. 6.1.1.4 Achievability of the maximum Now that we've examined how to compute the worst case jitter, we look at how likely it is that this worst case happens and how it relates to the jitter window. In addition to the topological and allocation assumptions that were made in order to allow a flow to have the opportunity of meeting every other flow, events must align so that the meeting actually happens at each hop. If we could assume independence of the timing of each flow's arrival within an interval of T, then that probability is on the order of (fT/N)N For this to happen at every hop we need the joint probability of this happening at all H nodes. Further we need the joint probability of that event in com- bination with an adjacent packet not meeting any other packets. For each additional hop, the number of ways the packets can com- bine increases exponentially, thus the probability of that par- ticular worst case combination decreases. 6.1.1.5 Jitter from non-VW packets The worst case occurs when one packet of a flow waits for no other packets to complete and the adjacent packet arrives at every hop just as an MTU-sized non-EF packet has begun transmission. That worst case jitter is the sum of the times to send MTU-sized pack- ets at the link bandwidth of all the hops in the path or, for equal bandwidth paths, (EQ 20)jitter = HxMTU/B Note that if one link has a bandwidth much smaller than the oth- ers, that term will dominate the jitter. If we assume that the MTU is on the order of 10-20 times the voice packet size in our example, then the time to send an MTU on a link is 10 or 20 times fxT/N so that our jitter bound becomes 20 x H x fxT/N. What has to happen in order to achieve the worst case? For jitter Jacobson, Nichols and Poduri Expires: January, 2001 [page 17 ] INTERNET DRAFT draft-ietf-diffserv-pdb-vw-00.txt July, 2000 against the default traffic, one packet waits for no default traf- fic and the adjacent packet arrives just as an MTU of the default type begins transmission on the link. The worst case is linear in the number of hops, but since the joint probability of an EF packet arriving at each queue precisely at the start of a non-EF packet on the link decreases in hop count, measured or simulated jitter will be seen to grow as a neg- ative exponential of the number of hops in a path, even at very high percentiles of probability. The reason for this is that the number of ways that the packets can arrive at the EF queue grows as pH so the probability is on the order of p-H. When the link bandwidth is small, it may be necessary to fragment non-EF packet to control jitter. How should we relate jitter in terms of source cycle times or vir- tual packet times to the jitter window defined in section 2.0? Note that we can write (EQ 21)jitter window = Sx(1/R - 1/((nxR)/f)) and noting that T = S/R, we get: (EQ 22)jitter window = Tx(n-f/n) So that, in many cases, the jitter window can be approximated by T. 6.2 Quantifying Jitter through Simulation Section 1 derived and discussed the worst-case jitter for indi- vidual flows of a diffserv per-domain behavior (PDB) based on the EF PHB. We showed that the worst case jitter can be bounded and calculated these theoretical bounds. The worst case bounds repre- sent possible, but not likely, values. Thus, to get a better feel for the likely worst jitter values, we used simulation. We use the ns-2 network simulator; our use of this simulator has been described in a number of documents [NS2,FBK,RFC2415]. The following subsections describe the simulation set-up for these particular experiments. 6.2.1 Topology Figure 12 shows the topology we used in the simulations. A and Z are edge routers through which traffic from various customers enters and exits the Diffserv cloud. We vary the topology within the Diffserv cloud to explore the worst-case jitter for EF traffic in various scenarios. Jitter is measured on a flow or set of flows that transit the network from A to Z. To avoid per hop synchroni- zations, half the DE traffic at each hop is new to the path while half of the DE traffic exits the path. For the mixed EF and DE simulations, half the EF flows go from A to Z while, at each hop, Jacobson, Nichols and Poduri Expires: January, 2001 [page 18 ] INTERNET DRAFT draft-ietf-diffserv-pdb-vw-00.txt July, 2000 the other half of the 10% rate only crosses the path at that hop. As discussed in section 1, this is an unlikely construction but we undertake it to give a more pessimistic jitter For the EF-only simulations, we emulate the case analyzed in section 1.1.3 by mea- suring jitter on one end to end flow and having (N-1) new EF flows meet that flow at every hop. Note that N is determined by the max- imum number of 28 kbps flows that can fit in the EF share of each link, so N=share x bandwidth/28 kbps. Figure 12: Simulated topology 6.2.2 Traffic Traffic is generated to emulate G.729 voice flows with packet size (B) of 68 Bytes and a 20 ms packetization rate. The resultant flows have a rate of 27 Kbps. As previously discussed, jitter experienced by the voice flows has two main components; jitter caused by meeting others flows in the EF queue, and jitter due to traffic in other low priority classes. To analyze the first compo- nent, we vary the multiplexing level of voice flows that are admitted into the DS domain and for the second, we generate data traffic for the default or DE PHB. Since we are interested in exploring the worst case jitter, data traffic is generated as long-lived TCP connections with 1500 Byte MTU segments. Current measurements show real Internet traffic consists of a mixture of packet sizes, over 50% of which are minimum-sized packets of 40 bytes and over 80% of which are much smaller than 1500 Bytes [CAIDA]. Thus a realistic traffic mix would only improve the jit- ter that we see in the simulations. 6.2.3 Schedulers and Queues All the nodes(routers) in the network have the same configura- tion: a simple Priority Queue (PQ) scheduler with two queues. Voice traffic is queued in the high priority queue while the data traffic is queued in the queue with the lower priority. The sched- uler empties all the packets in the high priority queue before servicing the data packets in a lower priority queue. However, if the scheduler is busy servicing a data packet at the time of arrival of a voice packet, the voice packet is served only after the data packet is serviced completely, i.e., the scheduler is non-preemptive. For priority queuing where the low priority queue is kept congested, simulating two queues is adequate. Figure 13: Link scheduling in the simulations 6.2.4 Results In the following simulations, three bandwidth values were used for the DS domain links: 1.5 Mbps, 10 Mbps, and 45 Mbps. Unless otherwise stated, the aggregate of EF traffic was allocated 10% of the link bandwidth. The hops per path was varied from 1 to 24. Then, the 1.5 Mbps links can carry about 5 voice flows, the 10 Jacobson, Nichols and Poduri Expires: January, 2001 [page 19 ] INTERNET DRAFT draft-ietf-diffserv-pdb-vw-00.txt July, 2000 Mbps about 36 voice flows, and 45 Mbps about 160. 6.2.4.1 Jitter due to other voice traffic only To see the jitter that comes only from meeting other EF-marked packets, we simulated voice traffic only and found this to be quite negligible. For example, with a 10 Mbps link and 10% of the link share assigned to the voice flows, a single bottleneck link in a dumbbell has a worst case jitter of 2 ms. In simulation the 99.97th percentile jitter for one to 25 hops never exceeds a third of a millisecond. This source of jitter is quite small, particu- larly compared to the jitter from traffic in other queue(s) as we will see in the next section. 6.2.4.2 Jitter in a voice flow where there is a congested default class Our traffic model for the DE queue keeps it full with mostly 1500 byte packets. From section 1, the worst case jitter is equal to the number of hops times the time to transmit a packet at the link rate. The likelihood of this worst case occurring goes down expo- nentially in hop count, and the simulations confirm this. Figure 15 shows several percentiles of the jitter for 10 Mbps links where the time to transmit an MTU at link speed is 1.2 ms. Figure 14: Various percentile jitter values for 10 Mbps links and 10% allocation Recall that the period of the voice streams is 20 ms and note that, the jitter does not even reach half a period. The median jitter gets quite flat with number of hops. Although the higher percentile values increase at a somewhat higher rate with number of hops, it still does not approach the calculated worst case. The data is also shown normalized by the MTU transmission time at 10 Mbps. Now the vertical axis value is the number of MTU sized pack- ets of jitter that the flow experiences. This normalization is presented to make it easier to relate the results to the analysis, though it obscures the impact (or lack thereof) of the jitter on the 20 ms flows. Figure 16 shows the same results for 1.5 Mbps links and Figure 17 for 45 Mbps links. Figure 15: Various percentiles of jitter for 1.5 Mbps links and 10% share Notice that the worst case jitter for the 1.5 Mbps link is on the order of two cycle times while, for 45 Mbps, it is less than 10% of the cycle time. However, the behavior in terms of number of MTUs is similar. Figure 16: Various percentiles of jitter for 45 Mbps links and 10% share Jacobson, Nichols and Poduri Expires: January, 2001 [page 20 ] INTERNET DRAFT draft-ietf-diffserv-pdb-vw-00.txt July, 2000 The jitter in time and thus as a fraction of the virtual packet time of the flow being measured clearly increases with decreasing bandwidth. Even the smallest bandwidth, 1.5 Mbps can handle nearly all jitter with a jitter buffer of 2 packets. The two higher bandwidths don't even jitter by one virtual packet time, thus staying within the jitter window. Figures 18, 19, and 20 com- pare the median, 99th percentile and 99.97th percentile (essen- tially the worst case). It's also interesting to normalize the results of each experiment by the MTU transmission time at that link bandwidth. The normalized values show that all scenarios experience the same behavior relative to the MTU transmission time. Figure 17: Median jitter for all three bandwidths by time and normalized Figure 18: 99th percentile of jitter for the three bandwidths; absolute time and normalized Figure 19: 99.97th percentile of jitter; absolute time and normalized by MTU transmission times The simulation experiments are not yet complete, but they clearly show the probability of achieving the worst case jitter decreas- ing with hop count and show that jitter can be controlled. The normalization shows that the jitter behavior is the same regard- less of bandwidth. The absolute times differ by scale factors that depend on the bandwidth. 6.2.4.3 Jitter with an increased allocation In the following, the experiments of the last section are repeated, but using a 20% link share, rather than a 10% link share Figure 21 shows the jitter percentiles for 10 Mbps links and a 20% share. The values are also plotted with the 10% share results (on the right hand side) to show how similar they are. Figure 20: Jitter percentiles for 10 Mbps links and 20% EF share Using the previous section, we would believe that the results for other bandwidths would have the same shape, but be scaled by the bandwidth difference. Figure 22 shows this to indeed be the case. Thus it is sufficient to simulated only a single bandwidth. Figure 21: Jitter for 1.5 Mbps links (on left) and 45 Mbps links (on right) In all the experiments, it can be clearly seen that the shape of the jitter vs. hops curve flattens because the probability of the worst case occurring at each hop decreases exponentially in hops. To see if there is an allocation level at which the jitter behav- ior diverges, we simulated and show results for allocations of 10, Jacobson, Nichols and Poduri Expires: January, 2001 [page 21 ] INTERNET DRAFT draft-ietf-diffserv-pdb-vw-00.txt July, 2000 20, 30, 40, and 50 percent, all for 10 Mbps links in Figure 23. Figure 22: Median and 99th percentile jitter for various allocations and 10 Mbps links What may not be obvious from figure 19 is that the similarity between the five allocation levels shows that jitter from other EF traffic is negligible compared to the jitter from waiting for DE packets to complete. Clearly, the probability of jitter from other EF traffic goes up with increasing allocation level, but it is so small compared to the DE-induced jitter that it isn't visi- ble except for the highest percentiles and the largest hop count.