Network Working Group M. Menth Internet-Draft F. Lehrieder Expires: May 15, 2008 University of Wuerzburg November 12, 2007 Performance Evaluation of PCN-Based Algorithms draft-menth-pcn-performance-00 Status of this Memo By submitting this Internet-Draft, each author represents that any applicable patent or other IPR claims of which he or she is aware have been or will be disclosed, and any of which he or she becomes aware will be disclosed, in accordance with Section 6 of BCP 79. 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. This Internet-Draft will expire on May 15, 2008. Copyright Notice Copyright (C) The IETF Trust (2007). Menth & Lehrieder Expires May 15, 2008 [Page 1] Internet-Draft PCN Performance Evaluation November 2007 Abstract This document presents a summary of performance studies for PCN-based admission control and flow termination. The numerical results were obtained by simulation or mathematical analysis. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4 3. Comparison of Marking Algorithms for PCN-Based Admission Control . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 3.1. Definition of Simulated Entities and Simulation Setup . . 5 3.1.1. Metering and Marking Mechanisms . . . . . . . . . . . 5 3.1.2. Congestion Level Estimator . . . . . . . . . . . . . . 5 3.1.3. Simulation Setup . . . . . . . . . . . . . . . . . . . 6 3.2. Impact of the Marking Threshold T and the Queue Size S . . 7 3.3. Two Marking Strategies with Different Admission Control Policies . . . . . . . . . . . . . . . . . . . . . 7 3.3.1. Marking with Clear Decisions (MCD) . . . . . . . . . . 7 3.3.2. Marking with Early Warning (MEW) . . . . . . . . . . . 7 3.4. Impact of Ramp Marking . . . . . . . . . . . . . . . . . . 7 3.5. Impact of the Memory M of the Congestion Level Estimator . . . . . . . . . . . . . . . . . . . . . . . . 8 3.6. Impact of Traffic Characteristics . . . . . . . . . . . . 8 3.7. Response Time of the Marking to Sudden Overload . . . . . 9 3.8. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . 9 4. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 11 5. Security Considerations . . . . . . . . . . . . . . . . . . . 12 6. References . . . . . . . . . . . . . . . . . . . . . . . . . . 13 6.1. Normative References . . . . . . . . . . . . . . . . . . . 13 6.2. Informative References . . . . . . . . . . . . . . . . . . 13 6.3. Other References . . . . . . . . . . . . . . . . . . . . . 13 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 14 Intellectual Property and Copyright Statements . . . . . . . . . . 15 Menth & Lehrieder Expires May 15, 2008 [Page 2] Internet-Draft PCN Performance Evaluation November 2007 1. Introduction Pre-congestion notification (PCN) is based on the idea of marking packets when a certain load threshold on a link is exceeded by PCN traffic. Then, the marking of a packet at the PCN egress node provides information whether the rate threshold of at least one link of the path over which the packet was carried was exceeded by PCN traffic. This information can be used for admission control and flow termination. Several approaches such as Single-Marking (SM) [I-D.charny-pcn-single-marking], CL [I-D.briscoe-tsvwg-cl-architecture], 3SM [I-D.babiarz-pcn-3sm] have been proposed for that purpose. An overview of the basic concept is given in [I-D.ietf-pcn-architecture]. The University of Wuerzburg is conducting performance studies to understand basic mechanisms and to compare different approaches. This document is intended to collect and present summaries of performance results documented in more detail in technical papers that are available online. Currently, it covers the following studies. o A summary of the results of [TR437] is presented in Section 3. [TR437] studies the impact of virtual queue (token bucket) parameters on marking results for threshold and ramp marking and gives a comparison. The next section clarifies some terminology issues. Menth & Lehrieder Expires May 15, 2008 [Page 3] Internet-Draft PCN Performance Evaluation November 2007 2. Terminology The terminology used in this document conforms to the topology of [I-D.ietf-pcn-architecture]. We use the following exceptions for better readability and provide the synonyms defined in [I-D.ietf-pcn-architecture]. o Admissible rate: PCN-lower-rate o Supportable rate: PCN-upper-rate o Admission-stop marking: first encoding or PCN-lower-rate-marking o Excess-traffic marking: second encoding or PCN-upper-rate-marking Menth & Lehrieder Expires May 15, 2008 [Page 4] Internet-Draft PCN Performance Evaluation November 2007 3. Comparison of Marking Algorithms for PCN-Based Admission Control The following presents a short summary of [TR437] without the graphs and exact numerical results that are provided in the technical report. The interested reader is referred to that document. 3.1. Definition of Simulated Entities and Simulation Setup In this study, we investigate the behaviour of different metering and marking algorithms under different configuration and use a congestion level estimator to observe the packet markings. 3.1.1. Metering and Marking Mechanisms PCN requires metering and marking algorithms in the interior nodes. [TR437] defines o threshold marking and o ramp marking based on a virtual queue (VQ), but there are equivalent descriptions based on token buckets. The parameters are o the size S of the VQ, o the rate R of the VQ, o the marking threshold T for threshold marking, which is also the upper threshold for ramp marking, o the marking threshold T_ramp, which is the lower threshold for ramp marking 3.1.2. Congestion Level Estimator Furthermore, a congestion level estimator is defined that calculates a congestion level estimate (CLE) at the PCN egress node based on an exponentially weighted moving average (EWMA). Marked packets count 1 and unmarked packets count 0. The CLE is computed as CLE = w * CLE + (1 - w) * X where X is the observed packet marking and w<1 is the weight parameter. If w is large, CLE has a long memory M, if it is low, CLE has a short memory M. The time between CLE updates also influences Menth & Lehrieder Expires May 15, 2008 [Page 5] Internet-Draft PCN Performance Evaluation November 2007 the memory M. A formal definition of the memory M is given in 3.4.2 of [TR437]. The CLE is used to observe the packet markings of the simulations. 3.1.3. Simulation Setup We simulate a single link scenario. Packets from n independent, homogeneous traffic sources are multiplexed onto a single link with infinite bandwidth and pass a meter and marker. The markings are evaluated by a subsequent congestion level estimator. If not mentioned differently, we simulate around n = 100 homogeneous flows for sufficiently long time to obtain reliable results. However, we omit confidence intervals in all our graphs for the sake of clarity. We choose a Gamma distribution to generate the inter- arrival times A between consecutive packets within a flow with a mean of E[A] = 20 ms and a coefficient of variation of cvar[A] = 0.1. The packet sizes B are independent and distributed according to a deterministic phase of 30 bytes plus a negative binomial distribution. Their overall mean is E[B] = 60 bytes and their coefficient of variation is cvar[B] = 0.5. The values for E[A] and E[B] are motivated by typical voice connections that periodically send every 20 ms a packet with 20 bytes payload using a 40 bytes IP/ UDP/RTP header. However, our flow model is not periodic and has variable packet sizes. We use it for two reasons. The simulation of multiplexed, strictly periodic traffic requires special care due to the non-ergodicity of the system and is very time consuming. Therefore, we relax cvar[A] = 0.0 to cvar[A] = 0.1. Furthermore, we use cvar[B] = 0.5 instead of cvar[B] = 0.0 because realtime traffic consists of packets from different applications with and without compression which leads to different packet sizes. However, our findings are general and do not depend on special parameter settings. The rate of the virtual queue is R = 2.4 Mbit/s such that at most 100 flows can pass unmarked. The congestion level estimator implements an exponentially weighted moving average (EWMA) and counts packets with admission-stop marks as 1 and those without as 0. As mentioned previously, its memory M depends on the packet rate and the weight parameter w such that w needs to be adapted to the desired M and the packet frequency in the experiment for which we take the maximum packet rate that can pass unmarked. Thus, we set the weight parameter to w = 0.998 which corresponds to a memory of 0.1 s when 100 default flows are active. If the packet rate changes due to more bursty traffic, we adapt the weight parameter w to achieve the same memory. Menth & Lehrieder Expires May 15, 2008 [Page 6] Internet-Draft PCN Performance Evaluation November 2007 3.2. Impact of the Marking Threshold T and the Queue Size S We measure the percentage of marked packets depending on the PCN rate (number of flows n) and the queue parameters size S and marking threshold T. The ideal marker marks 1. no packets if the PCN rate is below the VQ rate R and 2. all packets if it is above. We found out that 1. is increasingly achieved with increasing threshold T and 2. is increasingly achieved with increasing remaining queue size S-T. 3.3. Two Marking Strategies with Different Admission Control Policies We construct threshold markers with two different CLE characteristics (=function describing the percentage of marked packets depending on PCN rate). 3.3.1. Marking with Clear Decisions (MCD) Marking with clear decisions (MCD) means that the above objectives (1) and (2) are well achieved. This can be obtained for threshold marking with a large marking threshold T and a large remaining queue size S - T. Then, hardly any fluctuations in marking are observed. 3.3.2. Marking with Early Warning (MEW) Marking with early warning (MEW) means that (3) the percentage of marked packets already increases when the PCN rate approaches the VQ rate and (4) is 100% when the PCN rate is above the VQ rate. This can be obtained for threshold marking with a small marking threshold T and a large remaining queue size S - T. 3.4. Impact of Ramp Marking Ramp marking already marks packets probabilistically if the virtual queue length is below the marking threshold T. Therefore, it marks more packets than threshold marking with the same marking threshold T and queue size S. In our study we always set the lower marking threshold to T_ramp = 0. We found out that ramp marking with this configuration cannot achieve MCD because it marks a small percentage of packets when the PCN rate is below the VQ rate, but it can well achieve MEW. MEW can be achieved both with threshold and ramp Menth & Lehrieder Expires May 15, 2008 [Page 7] Internet-Draft PCN Performance Evaluation November 2007 marking, but threshold marking requires a smaller threshold parameter T to get the same marking results as with ramp marking. 3.5. Impact of the Memory M of the Congestion Level Estimator The memory M of the congestion level estimator does not have an impact on the percentage of marked packets that were observed over the simulation time, but it impacts the degree to which the CLE fluctuates. If the memory is long, the fluctuation of CLE is small. If the memory M is short, the fluctuation of CLE is large. When we configure the queue for MCD, i.e., the threshold T and the remaining queue size S-T were chosen sufficiently large, the CLE is almost 0 for PCN rates smaller than the VQ rate and it is 1 for PCN rates larger than the VQ rate. This holds even for a very small memory M of the congestion level estimator. 3.6. Impact of Traffic Characteristics Traffic characteristics have a significant impact on the marking result. o Decreased variance of packet sizes: no impact on the CLE characteristics in case of MCD, slightly lower curves in case of MEW o Increased variance of packet sizes: little impact on the CLE characteristics in case of MCD, significantly higher curves in case of MEW and larger fluctuation of CLE o Increased aggregation level: no impact on the CLE characteristics in case of MCD, slightly higher curves in case of MEW and less fluctuation of CLE o Increased variance of inter-arrival times: little impact on the CLE characteristics in case of MCD, slightly higher curves in case of MEW and larger fluctuation of CLE o Increased burstiness (fewer but larger packets): little impact on the CLE characteristics in case of MCD, significantly higher curves in case of MEW and large fluctuations of CLE o On/off traffic instead of continuous flows: large impact on the CLE characteristics in case of MCD and MEW, in particular very large fluctuations of the CLE Menth & Lehrieder Expires May 15, 2008 [Page 8] Internet-Draft PCN Performance Evaluation November 2007 3.7. Response Time of the Marking to Sudden Overload Large marking thresholds T and remaining queue sizes S-T lead to stable marking results for MCD, but large parameters slow down the reaction time of the marker when the PCN rate exceeds the VQ rate. 3.8. Conclusion One option for pre-congestion notification (PCN) based admission control requires that all packets are marked if the current link rate exceeds a pre-configured admissible rate. This can be achieved by virtual queue based marking algorithms such as simple threshold marking or more complex ramp marking. The objective of [TR437] was to study how marking algorithms can support admission control in order to limit the utilization of the links of a network. We did not consider the use of marking algorithms to support admission control in order to limit the packet delay because we assume that PCN will be used in high-speed networks where packet delay caused by queuing is negligible as long as link utilizations are moderate. We investigated the influence of the parameters of the marking algorithms on their marking results which are translated into a congestion level estimate (CLE) using EWMA-based averaging. We showed that two different marking strategies can be pursued: marking such that the CLE leads to clear decisions (MCD) and marking such that the CLE yields early warning (MEW) when the rate of PCN traffic on a link approaches its admissible rate. We provided recommendations for the configuration of the marking threshold T and the size S of the virtual queue in both cases. Ramp marking increases the level of early warning compared to threshold marking, but this can be approximated by smaller marking thresholds for simple threshold marking such that there is no obvious need for ramp marking. The CLE values for MEW fluctuate, therefore, it is difficult to infer the exact, current traffic rate from the CLE values which is required to take advantage of early warning. A sensitivity study revealed that the average CLE values for MEW depend heavily on the traffic characteristics. This makes the use of early warning difficult: either the marking parameters need to be adapted to produce similar warnings for different traffic types or the mechanism taking early warning into account requires knowledge about the traffic characteristics to correctly interpret the CLE level. In contrast, CLE values for MCD show hardly any variation and are robust against different traffic types. Menth & Lehrieder Expires May 15, 2008 [Page 9] Internet-Draft PCN Performance Evaluation November 2007 For the sake of simplicity, we advocate for the use of MCD for PCN based admission control instead of MEW because the interpretation of early warning is difficult due to its high variation and dependency on traffic characteristics. Furthermore, we think that ramp marking is not needed for PCN since similar markings can be obtained by appropriately configured threshold marking and we do not see any benefit that justifies the implementation complexity of ramp marking. Menth & Lehrieder Expires May 15, 2008 [Page 10] Internet-Draft PCN Performance Evaluation November 2007 4. IANA Considerations This memo includes no request to IANA. All drafts are required to have an IANA considerations section (see the update of RFC 2434 for a guide). If the draft does not require IANA to do anything, the section contains an explicit statement that this is the case (as above). If there are no requirements for IANA, the section will be removed during conversion into an RFC by the RFC Editor. Menth & Lehrieder Expires May 15, 2008 [Page 11] Internet-Draft PCN Performance Evaluation November 2007 5. Security Considerations All drafts are required to have a security considerations section. See RFC 3552 for a guide. Menth & Lehrieder Expires May 15, 2008 [Page 12] Internet-Draft PCN Performance Evaluation November 2007 6. References 6.1. Normative References 6.2. Informative References [I-D.babiarz-pcn-3sm] Babiarz, J., "Three State PCN Marking", draft-babiarz-pcn-3sm-00 (work in progress), July 2007. [I-D.briscoe-tsvwg-cl-architecture] Briscoe, B., "An edge-to-edge Deployment Model for Pre- Congestion Notification: Admission Control over a DiffServ Region", draft-briscoe-tsvwg-cl-architecture-04 (work in progress), October 2006. [I-D.charny-pcn-single-marking] Charny, A., "Pre-Congestion Notification Using Single Marking for Admission and Termination", draft-charny-pcn-single-marking-02 (work in progress), July 2007. [I-D.ietf-pcn-architecture] Eardley, P., "Pre-Congestion Notification Architecture", draft-ietf-pcn-architecture-01 (work in progress), October 2007. 6.3. Other References [TR437] Menth, M. and F. Lehrieder, "Comparison of Marking Algorithms for PCN-Based Admission Control, Technical Report No. 437", October 2007, . Menth & Lehrieder Expires May 15, 2008 [Page 13] Internet-Draft PCN Performance Evaluation November 2007 Authors' Addresses Michael Menth University of Wuerzburg Am Hubland Wuerzburg D-97074 Germany Phone: +49-931-888-6644 Email: menth@informatik.uni-wuerzburg.de Frank Lehrieder University of Wuerzburg Am Hubland Wuerzburg D-97074 Germany Phone: +49-931-888-6634 Email: lehrieder@informatik.uni-wuerzburg.de Menth & Lehrieder Expires May 15, 2008 [Page 14] Internet-Draft PCN Performance Evaluation November 2007 Full Copyright Statement Copyright (C) The IETF Trust (2007). This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights. This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Intellectual Property The IETF takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; nor does it represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79. Copies of IPR disclosures made to the IETF Secretariat and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr. The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at ietf-ipr@ietf.org. Acknowledgment Funding for the RFC Editor function is provided by the IETF Administrative Support Activity (IASA). Menth & Lehrieder Expires May 15, 2008 [Page 15]