[Docs] [txt|pdf] [Tracker] [Email] [Nits]

Versions: 00 01 02 03

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, <http://
              www-info3.informatik.uni-wuerzburg.de/TR/tr437.pdf>.


















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]


Html markup produced by rfcmarkup 1.129d, available from https://tools.ietf.org/tools/rfcmarkup/