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]