Internet Enginieering Task Force Olivier Bonaventure INTERNET DRAFT FUNDP Stefaan De Cnodder Alcatel June, 1999 Expires December, 1999 A rate adaptive shaper for differentiated services 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 documents 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. Abstract This memo describes two rate adaptive shapers (RAS) that can be used in combination with the Three Color Markers (srTCM and trTCM) proposed in [Heinanen1]. These RAS improve the performance of TCP when a TCM is used at the ingress of a diffserv network by reducing the burstiness of the traffic and thus increasing the proportion of packets marked as green by the TCM. Simulation results showing the improved performance are briefly discussed in the appendix. 1. Introduction In DiffServ networks, the incoming data traffic, with the AF PHB in particular, could be subject to marking where the purpose of this marking is to provide a low drop probability to a minimum part of the Bonaventure & De Cnodder A rate adaptive shaper [Page 1] Internet Draft draft-bonaventure-diffserv-rashaper-00.txt June 1999 traffic whereas the excess will have a larger drop probability. Such markers are mainly token bucket based such as the single rate three color marker (srTCM) described in [Heinanen1] and the two rates three color marker (trTCM) in [Heinanen2]. Similar markers were proposed for ATM networks and simulations have shown that their performance with TCP traffic was not always perfect and several researchers have shown that these performance problems could be solved in two ways : 1. increasing the burst size, i.e. increasing CBS and PBS, or 2. shaping the incoming traffic such that a part of the burstiness is removed. The first solution has as major disadvantage that the traffic sent to the network can be very bursty and thus providing a low packet loss ratio can become difficult. To efficiently support bursty traffic, additional resources such as buffer space are needed. The major disadvantage of shaping is that the traffic encounters some delay in the shaper's buffers. In this document, we propose two shapers that can reduce the burstiness of the traffic upstream of a srTCM or trTCM. By reducing the burstiness of the traffic, the shapers increase the percentage of packets marked as greens by the TCMs and thus the overall goodput of the users using such a shaper. A few simulation results showing the usefulness of the proposed shapers may be found in the appendix. The structure of this document follows the structure proposed in [Nichols]. 2. Description of the rate adaptive shapers. 2.1. Rate adaptive shaper The rate adaptive shaper is based on a similar shaper proposed in [Bonaventure] to improve the performance of TCP with the Guaranteed Frame Rate [Guerin] [TM41] service category in ATM networks. Another type of rate adaptive shaper suitable for differentiated services was briefly discussed in [Azeem]. A RAS will typically be used as shown in figure 1 where the meter and the marker are the TCMs proposed in [Heinanen1] and [Heinanen2]. Bonaventure & De Cnodder A rate adaptive shaper [Page 2] Internet Draft draft-bonaventure-diffserv-rashaper-00.txt June 1999 Result +----------+ | | | V +--------+ +-------+ +--------+ Incoming | | | | | | Outgoing Packet ==>| RAS |==>| Meter |==>| Marker |==>Packet Stream | | | | | | Stream +--------+ +-------+ +--------+ Figure 1. Rate adaptive shaper The rate adaptive shapers are thus different from the shapers described in [RFC2475] since they shape the traffic before the traffic is metered. The main objective of the shaper is to produce at its output a traffic that is less bursty than the input traffic, but the shaper should avoid to discard packets in contrast with classical leaky-bucket based shapers. The shaper itself consists of a tail-drop FIFO queue which is emptied at a variable rate. The shaping rate, i.e. the rate at which the queue is emptied, is a function of the occupancy of the FIFO queue. If the queue occupancy increases, the shaping rate will also increase in order to prevent loss and too large delays at the shaper. The shaping rate is also a function of the average rate of the incoming traffic. The shaper was designed to be used in conjunction with meters such as the TCMs proposed in [Heinanen1] and [Heinanen2]. There are two types of rate adaptive shapers. The single rate rate adaptive shaper (srRAS) will typically be used upstream of a srTCM while the two rates rate adaptive shaper (trRAS) will usually be used upstream of a trTCM. 2.2 Configuration of the srRAS The srRAS is configured by specifying four parameters : the Committed Information Rate (CIR), the Maximum Information Rate (MIR) and two buffer thresholds : CIR_th (Committed Information Rate threshold) and MIR_th (Maximum Information Rate threshold). The CIR shall be specified in bytes per second and MUST be configurable. The MIR shall be specified in the same unit as the MIR and SHOULD be configurable. To achieve a good performance, the CIR of a srRAS will usually be set at the same value as the CIR of the downstream srTCM. A typical value for the MIR would be the line rate of the output link of the shaper. When the CIR and optionally the MIR are configured, the srRAS MUST ensure that the following relation is verified : CIR <= MIR <= line rate Bonaventure & De Cnodder A rate adaptive shaper [Page 3] Internet Draft draft-bonaventure-diffserv-rashaper-00.txt June 1999 The two buffer thresholds, CIR_th and MIR_th shall be specified in bytes or packets and SHOULD be configurable. If these thresholds are configured, then the srRAS MUST ensure that the following relation holds : CIR_th <= MIR_th <= buffer size of the shaper The CIR_th and MIR_th may depend on the values chosen for the CBS and the PBS in the downstream srTCM. However, this dependency does not need to be standardized. 2.3 Behavior of the srRAS The output rate of the shaper is based on two factors. The first one is the (long term) average rate of the incoming traffic. This average rate can be computed by several means. For example, the function proposed in [Stoica] can be used (i.e. EARnew = [(1-exp(- T/K))*L/T]+exp(-T/K)*EARold where EARold is the previous value of the Estimated Average Rate, EARnew is the updated value, K a constant, L the size of the arriving packet and T the amount of time since the arrival of the previous packet). Other averaging functions can be used. The second factor is the instantaneous occupancy of the FIFO buffer of the shaper. When the buffer occupancy is below CIR_th, the output rate of the shaper is set to the maximum of the estimated average rate (EAR(t)) and the CIR. This ensures that the shaper will always send traffic at least at the CIR. When the buffer occupancy increases above CIR_th, the output rate of the shaper is computed as the maximum of the EAR(t) and a linear function F of the buffer occupancy for which F(CIR_th)=CIR and F(MIR_th)=MIR. When the buffer occupancy reaches the MIR_th threshold, the output rate of the shaper is set to the maximum information rate. The computation of the shaping rate is illustrated in figure 2. Bonaventure & De Cnodder A rate adaptive shaper [Page 4] Internet Draft draft-bonaventure-diffserv-rashaper-00.txt June 1999 ^ Shaping rate | | | MIR | ========= | // | // EAR(t) |----------------// | // | // CIR |============ | | | |------------+---------+--------------------------------> CIR_th MIR_th Buffer occupancy Figure 2 Computation of shaping rate for srRAS 2.4 Configuration of the trRAS The trRAS is configured by specifying six parameters : the Committed Information Rate (CIR), the Peak Information Rate (PIR), the Maximum Information Rate (MIR) and three buffer thresholds : CIR_th, PIR_th and MIR_th. The CIR shall be specified in bytes per second and MUST be configurable. To achieve a good performance, the CIR of a srRAS will usually be set at the same value as the CIR of the downstream trTCM. The PIR shall be specified in the same unit as the CIR and MUST be configurable. To achieve a good performance, the PIR of a trRAS will usually be set at the same value as the PIR of the downstream srTCM. The MIR SHOULD be configurable and shall be specified in the same unit as the CIR. A typical value for the MIR will be the line rate of the output link of the shaper. When the values for CIR, PIR and optionally MIR are configured, the trRAS MUST ensure that the following relation is verified : CIR <= PIR <= MIR <= line rate The three buffer thresholds, CIR_th, PIR_th and MIR_th shall be specified in bytes or packets and SHOULD be configurable. If these thresholds are configured, then the trRAS MUST ensure that the following relation is verified: CIR_th <= PIR_th <= MIR_th <= buffer size of the shaper The CIR_th, PIR_th and MIR_th may depend on the values chosen for the CBS and the PBS in the downstream trTCM. However, this dependency does not need to be standardized. Bonaventure & De Cnodder A rate adaptive shaper [Page 5] Internet Draft draft-bonaventure-diffserv-rashaper-00.txt June 1999 2.5 Behavior of the trRAS The output rate of the trRAS is also based on two factors. The first one is the (long term) average rate of the incoming traffic. This average rate can be computed as for the srRAS. The second factor is the instantaneous occupancy of the FIFO buffer of the shaper. When the buffer occupancy is below CIR_th, the output rate of the shaper is set to the maximum of the estimated average rate (EAR(t)) and the CIR. This ensures that the shaper will always send traffic at least at the CIR. When the buffer occupancy increases above CIR_th, the output rate of the shaper is computed as the maximum of the EAR(t) and a piecewise linear function BF of the buffer occupancy. This piecewise function can be defined as follows. The first piece is between zero and CIR_th where Bf() is equal to CIR. This means that when the buffer occupancy is below a certain threshold CIR_th, the shaping rate is at least CIR. The second piece is between CIR_th and PIR_th where Bf() increases linearly from CIR to PIR. The third part is from PIR_th to MIR_th where Bf is increased from PIR to the MIR and finally when the buffer occupancy is above MIR_th, the shaping rate remains constant at the MIR. The computation of the shaping rate is illustrated in figure 3. ^ Shaping rate | | | MIR | ====== | /// | /// PIR | /// | // | // EAR(t) |----------------// | // | // CIR |============ | | | |------------+---------+--------+------------------------> CIR_th PIR_th MIR_th Buffer occupancy Figure 2.b Computation of shaping rate for trRAS Bonaventure & De Cnodder A rate adaptive shaper [Page 6] Internet Draft draft-bonaventure-diffserv-rashaper-00.txt June 1999 3. Assumption The two shapers discussed in this document assume that the Internet traffic is dominated by protocols such as TCP that react appropriately to congestion by decreasing their transmission rate. These shapers reduce the burstiness of the traffic. 4. Example services The two shapers discussed in this document can be used in most situations where the TCMs proposed in [Heinanen1] and [Heinanen2] are used. In fact, simulations briefly discussed in Appendix A show that the performance of TCP can be improved when the trTCM is used in conjunction with one of the shapers described in this document than when the trTCM is used alone. We expect that similar simulations results would be found with the srTCM. 5. Security Issues The two shapers described in this document have no known security concerns. 6. References [Azeem] Feroz Azeem, Amit Rao,Xiuping Lu and Shiv Kalyanaraman, TCP- Friendly Traffic Conditioners for Differentiated Services, draft-azeem-tcpfriendly-diffserv-00.txt, March 1999, Work in progress. [Bonaventure] Olivier Bonaventure, "Integration of ATM under TCP/IP to provide services with a guaranteed minimum bandwidth", Ph. D. thesis, University of Liege, September 1998. [Clark] David D. Clark, and Wenjia Fang, "Explicit Allocation of Best- Effort Packet Delivery Service", IEEE/ACM Trans. on Networking, Vol. 6, No. 4, August 1998. [Guerin]R. Guerin and J. Heinanen, UBR+ service category definition, ATM Forum contribution ATM96-1598, December 1996. Bonaventure & De Cnodder A rate adaptive shaper [Page 7] Internet Draft draft-bonaventure-diffserv-rashaper-00.txt June 1999 [Heinanen1] Juha Heinanen, and Roch Guerin, "A Single Rate Three Color Marker", Internet draft, IETF, draft-heinanen-diffserv-srtcm- 01.txt. Work in progress. [Heinanen2] Juha Heinanen, and Roch Guerin, "A Two Rate Three Color Marker", Internet draft, IETF, draft-heinanen-diffserv-trtcm-01.txt. Work in progress. [Floyd1]Sally Floyd, and Van Jacobson, "Random Early Detection Gateways for Congestion Avoidance", IEEE/ACM Transactions on Networking, August 1993. [Floyd2]Sally Floyd, "RED : Optimum functions for computing the drop probability", email available at http://www- nrg.ee.lbl.gov/floyd/REDfunc.txt, October 1997. [Nichols]K. Nichols and B. Carpenter, Format for Diffserv Working Group Traffic Conditioner Drafts. Internet draft draft-ietf-diffserv- traffcon-format-00.txt, February 1999, work in progress [RFC2475]S. Blake, et al., An Architecture for Differentiated Services. RFC 2475, December 1998. [Stoica]I. Stoica and S. Shenker and H. Zhang, Core-stateless fair queueuing : achieving approxiamtely fair bandwidth allocations in high speed networks", ACM SIGCOMM98, pp. 118-130, Sept. 1998 [TM41] ATM Forum, Traffic Management Specification, verion 4.1, 1999 Appendix A. Simulation results A.1 description of the model To evaluate the rate adaptive shaper through simulations, we use the network model depicted in Figure A.1. In this network, we consider that a backbone network is used to provide a LAN Inter- connection service to ten pairs of LANs. Each LAN corresponds to Bonaventure & De Cnodder A rate adaptive shaper [Page 8] Internet Draft draft-bonaventure-diffserv-rashaper-00.txt June 1999 an uncongested switched 10 Mbps LAN with ten workstations attached to a customer router (C1-C10 in figure A.1). The delay on the LAN links is set to 1 msec. The MSS size of the worksta- tions is set to 1460 bytes. The workstations on the left hand side of the figure send traffic to companion workstations located on the right hand side of the figure. All traffic from the LAN attached to customer router C1 is sent to the LAN attached to customer router C1'. There are ten workstations on each LAN and each workstation implements SACK-TCP with a maximum window size of 64 KBytes. 2.5 msec, 34 Mbps 2.5 msec, 34 Mbps <--------------> <--------------> \+---+ +---+/ -| C1|--------------+ +--------------|C1'|- /+---+ | | +---+\ \+---+ | | +---+/ -| C2|------------+ | | +------------|C2'|- /+---+ | | | | +---+\ \+---+ | | | | +---+/ -| C3|----------+ | | | | +----------|C3'|- /+---+ | | | | | | +---+\ \+---+ | | | | | | +---+/ -| C4|--------+ +-+----------+ +----------+-+ +--------|C4'|- /+---+ | | | | | | +---+\ \+---+ +---| | | |---+ +---+/ -| C5|------------| ER1 |-----| ER2 |------------|C5'|- /+---+ +---| | | |---+ +---+\ \+---+ | | | | | | +---+/ -| C6|--------+ +----------+ +----------+ +--------|C6'|- /+---+ |||| |||| +---+\ \+---+ |||| <-------> |||| +---+/ -| C7|------------+||| 60 Mbps |||+------------|C7'|- /+---+ ||| 10 msec ||| +---+\ \+---+ ||| ||| +---+/ -| C8|-------------+|| ||+-------------|C8'|- /+---+ || || +---+\ \+---+ || || +---+/ -| C9|--------------+| |+--------------|C9'|- /+---+ | | +---+\ \+---+ | | +----+/ -|C10|---------------+ +---------------|C10'|- /+---+ +----+\ Figure A.1: the simulation model. The customer routers are connected with 34 Mbps links to the backbone network which is, in our case, composed of a single Bonaventure & De Cnodder A rate adaptive shaper [Page 9] Internet Draft draft-bonaventure-diffserv-rashaper-00.txt June 1999 bottleneck 34 Mbps link between the edge routers ER1 and ER2. The delay on all the customer-edge 34 Mbps links has been set to 2.5 msec to model a MAN or small WAN environment. These links and the customer routers are not a bottleneck in our environment and no losses occurs inside the edge routers. The customer routers are equipped with a trTCM [Heinanen2] and mark the incoming traffic. The parameters of the trTCM are shown in table A.1. Table A.1: configurations of the trTCMs Router CIR PIR Line Rate C1 2 Mbps 4 Mbps 34 Mbps C2 4 Mbps 8 Mbps 34 Mbps C3 6 Mbps 12 Mbps 34 Mbps C4 8 Mbps 16 Mbps 34 Mbps C5 10 Mbps 20 Mbps 34 Mbps C6 2 Mbps 4 Mbps 34 Mbps C7 4 Mbps 8 Mbps 34 Mbps C8 6 Mbps 12 Mbps 34 Mbps C9 8 Mbps 16 Mbps 34 Mbps C10 10 Mbps 20 Mbps 34 Mbps All customer routers are equipped with a trTCM where the CIR are 2 Mbps for router C1 and C6, 4 Mbps for C2 and C7, 6 Mbps for C3 and C8, 8 Mbps for C4 and C9 and 10 Mbps for C5 and C10. Routers C6-C10 also contain a trRAS in addition to the trTCM while routers C1-C5 only contain a trTCM. In all simulations, the PIR is always twice as large as the CIR. Also the PBS is the dou- ble of the CBS. The CBS will be varied in the different simula- tion runs. The edge routers, ER1 and ER2, are connected with a 60 Mbps link which is the bottleneck link in our environment. These two routers implement the RIO algorithm [Clark] that we have extended to support three drop preferences instead of two. The thresholds of the parameters are 100 and 200 packets (minimum and maximum threshold, respectively) for the red packets, 200 and 400 packets for the yellow packets and 400 and 800 for the green packets. The parameter maxp of RIO was set to 0.02 and we used as drop function the function proposed in [Floyd2] such that when the average queue length exceeds the maximum thres- hold, the drop probability does not suddenly jumps to 1. The weight to calculate the average queue length which is used by Bonaventure & De Cnodder A rate adaptive shaper [Page 10] Internet Draft draft-bonaventure-diffserv-rashaper-00.txt June 1999 RED or RIO is set to 0.002 [Floyd1]. The simulated time is set to 102 seconds where the first two seconds are not used to gather TCP statistics (the so-called warm-up time) such as goodput. A.2 Simulation results For our first simulations, we consider that routers C1-C5 only utilize a trTCM while routers C6-C10 utilize a rate adaptive shaper in conjunction with a trTCM. All routers use a CBS of 3 KBytes. In table A.2, we show the total goodput achieved by the workstations attached to each LAN as a function of the CIR of the trTCM used on the customer router attached to this LAN. In table A.3, we show the total goodput achieved by the worksta- tions attached to customer routers with a rate adaptive shaper. Table A.2: throughput in Mbps for the unshaped traffic. green yellow total 2Mbps [C1] 1.09 0.83 1.92 4Mbps [C2] 2.30 1.39 3.69 6Mbps [C3] 3.70 1.60 5.30 8Mbps [C4] 5.47 1.66 7.13 10Mbps [C5] 7.08 1.66 8.74 Table A.3: throughput in Mbps for the shaped traffic. green yellow total 2Mbps [C6] 2.00 0.81 2.81 4Mbps [C7] 3.98 1.08 5.06 6Mbps [C8] 5.86 0.74 6.60 8Mbps [C9] 7.76 0.58 8.34 10Mbps [C10] 9.79 0.52 10.3 This first simulation shows clearly that the workstations attached to an edge router with a rate adaptive shaper havea clear advantage, from a performance point of view, over worksta- tions attached to an edge router with only a trTCM. The perfor- mance improvement is the result of the higher proportion of packets marked as green by the edge routers when the rate adap- tive shaper is used. Table A.4 shows the total goodput for workstations attached to routers C1 (trTCM - 2_Mbps_unsh), C5 (trTCM - 10_Mbps_unsh), C6 (trRAS and trTCM 2_Mbps_sh), and C10 (trRAS and trTCM 10_Mbps_sh) for various values for the maximum burst size when the rate adaptive shaper is used. It is clear that routers with the rate adaptive shaper perform better if the CBS is small. Bonaventure & De Cnodder A rate adaptive shaper [Page 11] Internet Draft draft-bonaventure-diffserv-rashaper-00.txt June 1999 However, a CBS of a few hundred KBytes is probably too large in many environments. Table A.4: goodput in Mbps (rate adaptive shaper, link rate is 60 Mbps) versus CBS in KBytes. CBS 2_Mbps_unsh 2_Mbps_sh 10_Mbps_unsh 10_Mbps_sh 3 1.84 2.71 8.37 9.98 10 2.62 2.40 8.09 9.68 25 2.49 2.26 8.33 9.49 50 2.37 2.15 8.69 9.40 75 2.32 2.10 8.77 9.22 100 2.35 2.11 8.88 9.17 150 2.36 2.12 8.95 9.12 200 2.33 2.10 9.10 9.06 300 2.33 2.10 9.24 8.69 400 2.33 2.04 9.32 8.77 Authors Addresses Olivier Bonaventure Institut d'Informatique (CS Dept) Facultes Universitaires Notre-Dame de la Paix Rue Grandgagnage 21, B-5000 Namur, Belgium. E-mail: Olivier.Bonaventure@info.fundp.ac.be URL : http://www.info.fundp.ac.be/~obo Stefaan De Cnodder Alcatel Corporate Research Center Fr. Wellesplein 1, B-2018 Antwerpen, Belgium. Phone : 32-3-240-8515 Fax : 32-3-240-9932 E-mail: stefaan.de_cnodder@alcatel.be Bonaventure & De Cnodder A rate adaptive shaper [Page 12]