Internet Engineering Task Force Van Jacobson Differentiated Services Working Group Kathleen Nichols Internet Draft Kedar Poduri Expires Aug, 2000 Cisco Systems, Inc. draft-ietf-diffserv-ba-vw-00.txt March, 2000 The 'Virtual Wire' Behavior Aggregate 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 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 indistinquishable from a dedicated cir- cuit and can be used anywhere it is desired to replace dedicated circuits with IP transport. A pdf version of this document is available at ftp://ftp.ee.lbl.gov/papers/vw_ba.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- tion or 'virtual wire.' For scalability, a diffserv domain sup- plying this service must be completely unaware of the individual Jacobson, Nichols & Poduri Expires: August, 2000 [page 1 ] INTERNET DRAFT draft-ietf-diffserv-vw-ba-00.txt March, 2000 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 behavior aggregate or BA) in order to meet these requirements and thus defines a new BA, the Virtual Wire behavior aggregate or VW BA. 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 configured, the edge-to-edge service supplied by the domain will be indistin- guishable from that supplied by dedicated wires between the end- points. This note gives a quantitative definition of what is meant by 'appropriately policed and configured'. Loss, latency and jitter are all due to the queues traffic experi- ences while transiting the network. Therefore providing low loss, latency and jitter for some 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 ensuring no queues for some 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 departure rate. Creating the VW BA has two parts: 1. Configuring 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 aggregate (via policing and shaping) so that it's 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 behavior aggregate, as described in [BADEF]. The next sections describe the VW BA 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 BA 2.1 Applicability A Virtual Wire (VW) BA is intended to send "circuit replacement" traffic across a diffserv network. That is, this BA is intended to mimic, from the point of view of the originating and terminating Jacobson, Nichols & Poduri Expires: August, 2000 [page 2 ] INTERNET DRAFT draft-ietf-diffserv-vw-ba-00.txt March, 2000 nodes, the behavior of a hard-wired circuit of some fixed capac- ity. 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 BA should be suitable for any packetizable traffic that currently uses fixed circuits (e.g., telephony, telephone trunking, broadcast video distribu- tion, leased data lines) and packet traffic that has similar delivery requirements (e.g., IP telephony or video conferencing). 2.2 Rules 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. The bandwidth limit of each output interface SHOULD be configured as described in Section 2.4 of this document. In addi- tion, 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 Characteristics "The same as a wire." 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 configured rate, measured over any time scale longer than a packet time at that rate, will be unconditionally discarded. 2.4 Parameters Figure 1: Time structure of packets of a CBR stream at a high to low bandwidth transition Figure 1 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 2: Details of arrival / departure relationships Figure 2 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 Jacobson, Nichols & Poduri Expires: August, 2000 [page 3 ] INTERNET DRAFT draft-ietf-diffserv-vw-ba-00.txt March, 2000 (EQ 1) that bounds 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 des- tination will see service identical to a dedicated wire. Figure 3: Packet timing structure edge-to-edge Figure 3 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 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. Figure 4: Three VW customers forming an aggregate This jitter independence is what allows multiple 'virtual wires' to be transparently aggregated into a single VW BA. Figure 4 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 simultaneously 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 4 node I ships a different perturbation of the 3 customer aggregate in every win- dow yet this has no effect on the edge-to-edge VW properties). The jitter independence means that we only have to compare the jitter bound 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 & Poduri Expires: August, 2000 [page 4 ] INTERNET DRAFT draft-ietf-diffserv-vw-ba-00.txt March, 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 the incoming 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 so having left- overs is equivalent to a departure rate < nR over this time scale. But the EF property for any link capable of handling the aggregate traffic is that the departure rate be > nR over any time scale longer than S/(nR) so, again, this can't happen 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.5 Assumptions The topology independence of VW service actually holds only while routing is relatively stable. Since packets can be duplicated while routing 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. 2.6 Example uses Say an ISP wants to carry RTP encapsulated telephony traffic in addition to data traffic. Assume that want to retain all the robustness of IP (re-)routing which is equivalent to saying that all traffic can show up on any link. This implies that the lowest bandwidth backbone link constrains the total number of calls that Jacobson, Nichols & Poduri Expires: August, 2000 [page 5 ] INTERNET DRAFT draft-ietf-diffserv-vw-ba-00.txt March, 2000 can be carried. If the smallest backbone link is OC-3 and each call generates at most a 200 byte packet every 20ms, then the total number of VW customers that can be admitted into the back- bone must be less than (For comparison, an OC-3 TDM telco trunk could admit 2421 custom- ers so there is a 25% bandwidth penalty paid for the ability to efficiently mix voice and data.) Since this limit does not depend on the topology, these call slots can be assigned to customers, either statically or dynamically, in any way that doesn't violate the VW/EF bound on the customer tail circuits. Note that each call looks like two 'customers', one each direc- tion, so this overly simple bound is actually less than half the capacity of an equivalent telco system. If one adds the topologi- cal assumption that none of the simplex traffic streams between two endpoints will ever travel both directions over the same link, then the number VW customers becomes 1938 each direction so the domain has roughly the same telephony capacity as an equivalent telco system. 2.7 Environmental concerns Routing instability will generally translate directly into VW service degradation. 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 BA 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.Carl- son,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/ Jacobson, Nichols & Poduri Expires: August, 2000 [page 6 ] INTERNET DRAFT draft-ietf-diffserv-vw-ba-00.txt March, 2000 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} [BADEF] "Definition of Differentiated Services Behavior Aggregates and Rules for their Speci- fication", K.Nichols, B.Carpenter, draft-ietf-diffserv-ba-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 [NS2] The simulator ns-2, available at: http://www-mash.cs.berkeley.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 Cisco Systems, Inc. 170 W. Tasman Drive San Jose, CA 95134-1706 van@cisco.com Kathleen Nichols Cisco Systems, Inc. 170 W. Tasman Drive San Jose, CA 95134-1706 kmn@cisco.com Kedar Poduri Cisco Systems, Inc. 170 W. Tasman Drive San Jose, CA 95134-1706 kmn@cisco.com 6.0 Appendix: On Jitter for the VW BA The VW BA'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 BA where expected and worst-case jitter for rate-controlled streams of packets is of interes; thus this appendix is primarily focused on voice jitter. The appendix Jacobson, Nichols & Poduri Expires: August, 2000 [page 7 ] INTERNET DRAFT draft-ietf-diffserv-vw-ba-00.txt March, 2000 focuses on jitter for individual flows aggregated in a VW BA, derives worst-case bounds on the jitter, and gives simulation results for jitter. 6.1 Jitter and Delay The VW BA is sufficiently restrictive in its rules to preserve the required EF per-hop behavior under aggregation. These properties also make it useful as a basis for Internet telephony, to get low jitter and delay. Since a VW BA 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 equipment used. Unless the end-to-end delay is excessive due to very slow links or very slow equipment, it is usually the jitter, or varia- tion of delay, of a voice stream that is more critical than the delay. We derive the worst case jitter for a a VW BA in a DS domain using it to carry a number of rate-controlled flows. Jitter is defined as the absolute value of the difference between the arrival time difference of two adjacent packets and their departure time dif- ference, that is: (EQ 2)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 BA 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 cyle time. It is important to recall the analysis of section 3.0 showing that this jitter across the DS domain is completely invisible to the end-to-end flow using the VW BA 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- Jacobson, Nichols & Poduri Expires: August, 2000 [page 8 ] INTERNET DRAFT draft-ietf-diffserv-vw-ba-00.txt March, 2000 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 BA using the EF PHB will get its configured share of each link at all times- cales above the time to send an MTU at the rate corresponding to that share of that link. Focus on the DS domain of figure 5. 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 5: 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 BA 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 BA 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 3)dj = 0 (EQ 4)dk = T (EQ 5)aj = delay Jacobson, Nichols & Poduri Expires: August, 2000 [page 9 ] INTERNET DRAFT draft-ietf-diffserv-vw-ba-00.txt March, 2000 (EQ 6)ak = time spent waiting behind all other packets +delay+T Then we can use: (EQ 7)jitter = time spent waiting behind all other packets as we explore calculating worst case jitter for different topolo- gies. 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. 6.1.1.1 Worst case jitter in a network with a dumbbell bottleneck Consider a DS domain topology shown in figure 6. In order for a packet of the (A,Z) flow to arrive behind packets of all the other flows, a packet from each ingress must arrive at each of the M border routers at the same time and must be transmitted to the interior router's queue for the bottleneck link B at the same time. Further the links between the border routers and the bottle- neck router must be enough larger than B that the packets are still sitting in B's queue when our (A,Z) packet arrives at the end of a burst of N packets, that is L > NxB. Then the (EQ 8)jitterworst case = MxNx(time to send an EF packet on B) Since we expressed the EF aggregate's allocation on B as fxB, the time to send an EF packet on B is fxT/(MxN), so (EQ 9)jitterworst case = fxT Figure 6: 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 simul- taneously at all M border routers. By assuming independence, an interested person should be able to get some insight on the like- lihood of this happening. Simulation results in a later section will show this. 6.1.1.2 Worst case jitter in an arbitrary network Jacobson, Nichols & Poduri Expires: August, 2000 [page 10 ] INTERNET DRAFT draft-ietf-diffserv-vw-ba-00.txt March, 2000 Consider the network of figure 5 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. In this case, assume all links have bandwidth B but we don't know the path the individual EF packets or flows of the aggregate will follow. Then the worst case jitter is (EQ 10)jitterworst case = Ix(fxT/I) = fxT the same as the bottleneck case. Note that, in allocation, if it is possible to know that not all flows of the aggregate will take the same path, then one could allocate each link to a smaller num- ber of flows, but this would also imply that the number of flows that it's possible to meet and be jittered by is smaller. Alloca- tion can be kept to under 0.5 times the bandwidth 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 7 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 7: 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 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 11) Hx(N-1) = MxN - 1 Jacobson, Nichols & Poduri Expires: August, 2000 [page 11 ] INTERNET DRAFT draft-ietf-diffserv-vw-ba-00.txt March, 2000 then compute the maximum jitter as: (EQ 12)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 13)jitterworst case = H x (N-1) x fT/(number of ingress-shaped EF flows on each link) Otherwise the max jitter is (EQ 14)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 15)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 16)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 17)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. (EQ 18)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- Jacobson, Nichols & Poduri Expires: August, 2000 [page 12 ] INTERNET DRAFT draft-ietf-diffserv-vw-ba-00.txt March, 2000 tic, we can see that the jitter can be kept to a reasonable amount. The rules of the EF PHB and the VW BA should make it easy to compute the worst case jitter for any topology and allocation. 6.1.1.4 Achievablility 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 19)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 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 Jacobson, Nichols & Poduri Expires: August, 2000 [page 13 ] INTERNET DRAFT draft-ietf-diffserv-vw-ba-00.txt March, 2000 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 3.0? Note that we can write (EQ 20)jitter window = Sx(1/R - 1/((nxR)/f) ) and noting that T = S/R, we get: (EQ 21)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 behavior aggregate (BA) based on the EF PHB. We showed that the worst case jitter can be bounded and cal- culated these theoretical bounds. The worst case bounds represent 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 8 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 syn- chronizations, 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, 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 measuring 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 maximum number of 28 kbps flows that can fit in the EF share of each link, so N=share x bandwidth/28 kbps. Jacobson, Nichols & Poduri Expires: August, 2000 [page 14 ] INTERNET DRAFT draft-ietf-diffserv-vw-ba-00.txt March, 2000 Figure 8: 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 prioirity classes. To analyze the first com- ponent, 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 9: 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 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. Figure 10 shows results from 10 Mbps links with 10% of the link share assigned to the voice flows. For a single bottleneck link in a dumbbell, the worst Jacobson, Nichols & Poduri Expires: August, 2000 [page 15 ] INTERNET DRAFT draft-ietf-diffserv-vw-ba-00.txt March, 2000 case jitter possible for this scenario is 2 ms. Note that the val- ues in Figure 10 are far less than that. This source of jitter is quite small, particularly compared to the jitter from traffic in other queue(s) as we will see in the next section. (Note: Figure 10's results are quite preliminary. Further simulations will be performed that jitter the individual sources slightly.) Figure 10: Jitter from meeting other EF-marked traffic 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 occuring goes down expo- nentially in hop count, and the simulations confirm this. Figure 11 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 11: 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 12 shows the same results for 1.5 Mbps links and Figure 13 for 45 Mbps links. Figure 12: 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 13: Various percentiles of jitter for 45 Mbps links and 10% share 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 jiter by one virutal packet time, thus staying within the jitter window. Figures 14, 15, and 16 com- pare the median, 99th percentile and 99.97th percentile (essen- tially the worst case). It's also interesting to normalize the Jacobson, Nichols & Poduri Expires: August, 2000 [page 16 ] INTERNET DRAFT draft-ietf-diffserv-vw-ba-00.txt March, 2000 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 14: Median jitter for all three bandwidths by time and normalized Figure 15: 99th percentile of jitter for the three bandwidths; absolute time and normalized Figure 16: 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 acheiveing 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 bandwith. 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 17 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 17: 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 18 shows this to indeed be the case. Thus it is sufficient to simulated only a single bandwidth. Figure 18: 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 occuring 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, 20, 30, 40, and 50 percent, all for 10 Mbps links in figure 19. Figure 19: 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. Jacobson, Nichols & Poduri Expires: August, 2000 [page 17 ] INTERNET DRAFT draft-ietf-diffserv-vw-ba-00.txt March, 2000