PCN Working Group D. Satoh
Internet-Draft H. Ueno
Intended status: Informational Y. Maeda
Expires: March 14, 2010 O. Phanachet
NTT-AT
September 10, 2009
Single PCN Threshold Marking by using PCN baseline encoding for both
admission and termination controls
draft-satoh-pcn-st-marking-02
Status of this Memo
This Internet-Draft is submitted to IETF in full conformance with the
provisions of BCP 78 and 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 March 14, 2010.
Copyright Notice
Copyright (c) 2009 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents in effect on the date of
publication of this document (http://trustee.ietf.org/license-info).
Please review these documents carefully, as they describe your rights
and restrictions with respect to this document.
Satoh, et al. Expires March 14, 2010 [Page 1]
Internet-Draft ST Marking September 2009
Abstract
Pre-congestion notification (PCN) gives early warning of congestion
by metering and marking packets in order to protect the quality of
service of inelastic flows. PCN traffic load is divide into three
pre-congestion states by two rates that [I-D.ietf.pcn.architecture]
defines per link: PCN-admissible- and PCN-supportable-rates. PCN
admission control and flow termination mechanisms operate in
accordance with these three states. [I-D.ietf.pcn.baseline.encoding]
defines two PCN encoding states. This document proposes an algorithm
for marking and metering by using PCN baseline encoding for both flow
admission and flow termination. The ratio of marked packets
determines the three link states: no packets marked, some packets
marked, and all packets marked. To achieve this marking behaviour,
we use two token buckets. One is not used for marking but for a
marking switch; the other is used for marking. The token bucket for
marking has two thresholds. One is TBthreshold.threshold, already
defined in [I-D.ietf-pcn-marking-behaviour], and the other is a new
threshold, which is set to be the number of bits of a metered-packet
smaller than the token bucket size. Therefore, the new threshold is
larger than TBthreshold.threshold. If the amount of tokens is less
than TBthreshold.threshold, all the packets are marked as defined in
[I-D.ietf-pcn-marking-behaviour]. If the amount of tokens is less
than the new threshold and greater than TBthreshold.threshold, one-
Nth packets are marked. We evaluated the performance of admission
control and flow termination using a simulation. For admission
control, the results show that the performance of the algorithm was
almost the same as, but slightly inferior to, that of CL
[draft-briscoe-tsvwg-cl-phb-03]. For flow termination, the
performance of the algorithm was almost the same as CL when the load
was 1.2 times the supportable rate, but it was superior to CL when
the load was high (two times the supportable rate). Furthermore, in
the algorithm, over termination percentages of all the bottleneck
links are almost the same in the case of multi-bottleneck. In CL,
the over termination percentages of all the bottleneck links are
different and those at upstream bottleneck links are higher than
those at downstream bottleneck links because of accumulation of
marked packets.
Satoh, et al. Expires March 14, 2010 [Page 2]
Internet-Draft ST Marking September 2009
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 5
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 5
3. Single Threshold-Marking . . . . . . . . . . . . . . . . . . . 5
3.1. Operation at PCN-interior-node . . . . . . . . . . . . . . 6
3.2. Operation at PCN-egress-node . . . . . . . . . . . . . . . 10
3.2.1. Operation for Admission Decision . . . . . . . . . . . 10
3.2.2. Operation for Flow Termination Decision . . . . . . . 10
3.3. Operation at the PCN-ingress-node . . . . . . . . . . . . 10
3.3.1. Admission Decision . . . . . . . . . . . . . . . . . . 10
3.3.2. Flow Termination Decision . . . . . . . . . . . . . . 11
4. Admission Issues . . . . . . . . . . . . . . . . . . . . . . . 11
4.1. Effect of Synchronization . . . . . . . . . . . . . . . . 11
5. Termination Issues . . . . . . . . . . . . . . . . . . . . . . 12
5.1. Effect of dropping packets to Termination . . . . . . . . 12
5.2. Effect of multi-bottleneck . . . . . . . . . . . . . . . . 12
5.3. Speed and Accuracy of Termination . . . . . . . . . . . . 12
6. Performance evaluation . . . . . . . . . . . . . . . . . . . . 13
7. Impact on PCN marking behaviour . . . . . . . . . . . . . . . 13
8. Changes from -01 version . . . . . . . . . . . . . . . . . . . 13
9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 14
10. Appendix A: Simulation Setup and Environment . . . . . . . . . 14
10.1. Network and Signaling Models . . . . . . . . . . . . . . . 14
10.2. Traffic Models . . . . . . . . . . . . . . . . . . . . . . 16
10.3. Performance Metrics . . . . . . . . . . . . . . . . . . . 17
10.4. Parameter Settings for STM . . . . . . . . . . . . . . . . 18
10.5. Parameter Settings for CL . . . . . . . . . . . . . . . . 19
10.6. Simulation Environment . . . . . . . . . . . . . . . . . . 19
11. Appendix B: Admission Control Simulation . . . . . . . . . . . 19
11.1. Parameter Settings for Admission Control . . . . . . . . . 19
11.2. Sensitivity to EWMA Weight and CLE Threshold . . . . . . . 20
11.3. Basic Evaluation . . . . . . . . . . . . . . . . . . . . . 21
11.4. Effect of Ingress-Egress Aggregation . . . . . . . . . . . 22
11.4.1. CBR . . . . . . . . . . . . . . . . . . . . . . . . . 22
11.4.2. VBR . . . . . . . . . . . . . . . . . . . . . . . . . 23
11.4.3. SVD . . . . . . . . . . . . . . . . . . . . . . . . . 24
11.5. Effect of Multi-bottleneck . . . . . . . . . . . . . . . . 25
11.6. Fairness among Different Ingress-Egress Pairs . . . . . . 25
12. Appendix C: Flow termination . . . . . . . . . . . . . . . . . 26
12.1. Basic evaluation . . . . . . . . . . . . . . . . . . . . . 27
12.2. Effect of Ingress-Egress Aggregation . . . . . . . . . . . 28
12.2.1. CBR . . . . . . . . . . . . . . . . . . . . . . . . . 28
12.2.2. VBR . . . . . . . . . . . . . . . . . . . . . . . . . 28
12.2.3. SVD . . . . . . . . . . . . . . . . . . . . . . . . . 29
12.3. Effect of Multi-bottleneck . . . . . . . . . . . . . . . . 30
13. Appendix D: Why is TBthreshold.shallow.threshold set to be
smaller than the token bucket size by the bit-size of a
Satoh, et al. Expires March 14, 2010 [Page 3]
Internet-Draft ST Marking September 2009
metered packet? . . . . . . . . . . . . . . . . . . . . . . . 32
14. Appendix E: Admission control using fractional marking . . . . 34
15. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 36
16. Security Considerations . . . . . . . . . . . . . . . . . . . 36
17. Informative References . . . . . . . . . . . . . . . . . . . . 36
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 37
Satoh, et al. Expires March 14, 2010 [Page 4]
Internet-Draft ST Marking September 2009
1. Introduction
Pre-congestion notification (PCN) provides information to support
admission control and flow termination in order to protect the
quality of service (QoS) of inelastic flows. Although several
algorithms (e.g., [I-D.briscoe-tsvwg-cl-phb], [I-D.charny-pcn-single-
marking], and [I-D.babiarz-pcn-3sm]) have been proposed to achieve
PCN, only the single marking algorithm (SM) [I-D.charny-pcnsingle-
marking] meets the requirement of baseline encoding.
This document proposes an algorithm for marking and metering by using
PCN baseline encoding for both flow admission and flow termination.
Our algorithm uses PCN-threshold marking while SM uses PCN-excess-
traffic marking. Although our algorithm uses an elaborate mechanism,
it chooses PCN-admissible- and PCN-supportable-rates independently,
and it explicitly detects whether PCN traffic is greater than the
PCN-supportable-rate. Furthermore, our algorithm is little affected
by synchronization. Therefore, it can avoid degradation of admission
accuracy caused by synchronization.
2. Terminology
The terminology used in this document conforms to the terminology of
[ID.ietf-pcn-architecture] and [I-D.ietf-pcn-marking-behaviour].
3. Single Threshold-Marking
We describe an algorithm of marking and metering by using PCN
baseline encoding for both flow admission and flow termination. This
algorithm uses only the PCN-threshold-rate as the PCN-supportable-
rate and does not use the PCN-excess-rate. We show a schematic of
how the PCN admission control and flow termination mechanisms operate
as the rate of PCN-traffic increases for a PCN-domain with three
types of ratios of PCN-threshold-marked packets and three states of
marking ratio in Fig. 1. Only two encoding states:un-marked and
marked can be used for marking when PCN baseline encoding is used.
We use two encoding state marking for the marking ratio to
distinguish the three states. As shown in Fig. 1, no packets are
PCN-marked at a rate less than the PCN-admissible-rate, some packets
are PCN-marked at rates between the PCN-admissible- and PCN-
supportable-rates, and all the packets are PCN-marked at rates
greater than the PCN-supportable-rate. Admission control using this
marking stops traffic from being admitted when the fraction of marked
traffic for an ingress-egress aggregate (IEA) exceeds a configured
threshold: the congestion level estimate (CLE). When the egress
receives a certain sequential marked packets, it sends a message of
Satoh, et al. Expires March 14, 2010 [Page 5]
Internet-Draft ST Marking September 2009
the receiving rate to an ingress. Then the ingress terminates flows
based on the information of the sending and receiving rates.
The remainder of this section describes the possible operation of the
system.
PCN traffic rate
100%
| Terminate some
|All the packets admitted flows
|PCN-threshold-marked & Marking.frequency: 1
PCN- | Block new flows
supportable|
rate +-------------------------------------------------------
(PCN- |
threshold- |
rate) | Some packets Block Marking.frequency: 1/N
| PCN-threshold-marked new flows
PCN- |
admissible |
rate +-------------------------------------------------------
|
| No packets Admit new flows Not defined
| PCN-marked
|
0% +-------------------------------------------------------
Figure 1: Ratio of PCN-threshold-marked packets, control operations,
and Marking.frequency
3.1. Operation at PCN-interior-node
We explain here how to distinguish the three link states. The single
threshold-marking algorithm (STM) uses two token buckets. One is not
used for marking but as a marking switch, which we call the switch
token bucket (SwTB). The other is used for marking, which we call
the marking token bucket (MkTB). We also explain how to mark by
using two token buckets in cooperation.
SwTB can be used when the traffic is below the admissible rate so
that no packets are marked. Metering and marking using SwTB is
similar to threshold metering and marking, although there is a
difference between actual marking and having the marking switch ON.
SwTB has one threshold, which is termed the SwTB threshold. Tokens
of SwTB are added at the PCN-admissible-rate. Tokens are removed
equal to the bit-size of the metered packet. These additions and
Satoh, et al. Expires March 14, 2010 [Page 6]
Internet-Draft ST Marking September 2009
removals are independent of MkTB. If the metered traffic is
sustained at a level greater than the PCN-admissible-rate, the tokens
are less than the SwTB threshold. When the tokens are less than the
SwTB threshold, the marking switch of SwTB is set to ON and the
metered packet is threshold-marked in accordance with the meter based
on MkTB. Otherwise, the marking switch of SwTB is OFF. When the
marking switch is OFF, no packet is marked regardless of the meter of
MkTB. Thus, the state of admitting new flows (seen in Fig. 1) is
achieved.
MkTB can be used to mark packets in accordance with traffic rates.
Metering and marking using MkTB is modified threshold metering and
marking. MkTB has two thresholds. One, termed
TBthreshold.shallow.threshold, is set to be smaller than the token
bucket size by the bit-size of a metered packet. The other is
TBthreshold.threshold in [I-D. pcn-marking-behaviour]. Regardless of
the marking switch being ON or OFF, tokens of MkTB are added at the
PCN-supportable-rate and tokens are removed equal to the bit-size of
the metered packet. These additions and removals are independent of
SwTB.
If the metered traffic is sustained at a level greater than the PCN-
supportable-rate, the tokens are less than the TBthreshold.threshold.
When the tokens are less than TBthreshold.threshold, all the metered
packets are threshold-marked. The marking.frequency in this state is
1 because all the metered packets are marked. Relations among
marking.frequency, marking behaviour, and PCN mechanisms are shown in
Fig. 1. Thus, the state of terminating certain admitted flows and
blocking new flows (seen in Fig. 1) is achieved.
If the metered traffic is between the PCN-admissible-rate and PCN-
supportable-rate, the tokens are greater than the
TBthreshold.threshold. If the metered traffic has rate fluctuations,
the tokens are often less than TBthreshold.shallow.threshold. Note
that the probability that the tokens are less than
TBthreshold.shallow.threshold is approximately the ratio between the
rate of the metered traffic and the PCN-supportable-rate [see
Appendix D]. If the tokens are less than
TBthreshold.shallow.threshold (the tokens are less than MkTB.size
before the tokens of the arrived packet.size are removed), a metered
packet is PCN-threshold-marked for every one-Nth. Note that one-Nth
arrived packets are not marked. The marking.frequency in this state
is 1/N. This marking with marking.frequency 1/N avoids accommodating
marking through multi-bottleneck links to distinguish partial marking
from marking of all packets.
This marking is expressed by the following pseudo code:
Satoh, et al. Expires March 14, 2010 [Page 7]
Internet-Draft ST Marking September 2009
Input: pcn packet
//add tokens to the two token buckets
SwTB.fill = min(SwTB.size, SwTB.fill + SwTB.rate*(now - lastUpdate));
MkTB.fill = min(MkTB.size, MkTB.fill + MkTB.rate*(now - lastUpdate));
//remove tokens from the two token buckets
SwTB.fill = max( 0 , SwTB.fill - packet.size);
MkTB.fill = max( 0 , MkTB.fill - packet.size);
IF (SwTB.fill <= SwTB.threshold) THEN //marking switch is ON
IF (MkTB.fill < MkTBthreshold.shallow.threshold) THEN
IF (MkTB.fill > MkTBthreshold.threshold) THEN
markCnt++;
IF mod(markCnt, N) == 0 THEN //Marking.frequency = 1/N
markCnt = 0;
packet.mark = TM;
ENDIF
ELSE
markCnt = 0;
packet.mark = TM;
ENDIF
ENDIF
ELSE //marking switch is OFF
ENDIF
output: void
It can be rewritten as follows.
Input: pcn packet
//add tokens to the two token buckets
SwTB.fill = min(SwTB.size, SwTB.fill + SwTB.rate*(now - lastUpdate));
MkTB.fill = min(MkTB.size, MkTB.fill + MkTB.rate*(now - lastUpdate));
lastUpdate = now;
markOpe = ((SwTB.fill - packet.size) >= SwTB.Threshold) ? false:true;
IF (markOpe) THEN
IF (MkTB.fill < MkTB.size) THEN
markCnt ++;
IF (MkTB.fill < MkTB.Threshold) THEN
packet.mark = TM;
markCnt = 0;
ELSE IF (markCnt == N) THEN
packet.mark = TM;
markCnt = 0;
ENDIF
ENDIF
ENDIF
//remove tokens from each token bucket
SwTB.fill = max( 0 , SwTB.fill - packet.size);
Satoh, et al. Expires March 14, 2010 [Page 8]
Internet-Draft ST Marking September 2009
MkTB.fill = max( 0 , MkTB.fill - packet.size);
Output: void
Here, SwTB.fill and MkTB.fill (TBthreshold.fill in [I-D.pcn-marking-
behaviour]) represent the amount of tokens in the SwTB and MkTB,
SwTB.size and MkTB.size (TBthreshold.max in [I-D.pcn-marking-
behaviour]) represent the maximum values of SwTB.fill and MkTB.fill,
and SwTB.threshold and MkTB.threshold represent the SwTB threshold
and MkTB threshold (TBthreshold.threshold), respectively. Tokens of
SwTB are added at the SwTB.rate whose value is the PCN-admissible-
rate. Tokens of MkTB are added at the MkTB.rate whose value is the
PCN-supportable-rate (PCN-threshold-rate). The time variables now
and lastUpdate are the current time and the time when the fill state
of TB was last updated, respectively. The byte of an arrived packet
is packet.size. TM represents the state of the threshold-marked
packet, packet.mark represents the state of the mark of a packet, and
markCnt represents the number of marked packets.
The relation between PCN traffic rate and marking ratio is shown Fig.
2, where AR and SR represent PCN-admissible- and PCN-supportable-
rates.
^
marking ratio |
1 + +----------------
| |
| |
| |
| |
| |
1/N + _|
| _-
| _-
| _-
| _-
| _-
| _-
AR/(N*SR) + _-
| |
| |
| |
| |
---------------------+-----------------+-------------->
0 AR SR PCN traffic
rate
Satoh, et al. Expires March 14, 2010 [Page 9]
Internet-Draft ST Marking September 2009
Figure 2: Relation between PCN traffic rate and marking ratio
3.2. Operation at PCN-egress-node
3.2.1. Operation for Admission Decision
A PCN-egress-node measures the ratio of PCN-threshold-marked packets
on a per-ingress basis and reports to the PCN-ingress-node the
congestion level estimate (CLE), which is the fraction of the marked
traffic received from the ingress node and is exactly the same as
that of CL, SM, and three state PCN marking algorithms (3sM).
3.2.2. Operation for Flow Termination Decision
The PCN-egress-node always measures the receiving rate per PCN-
ingress-node regardless of whether receiving marked packets or not.
When the PCN-egress-node receives L-sequential marked packets from a
PCN-ingress-node, it sends a packet of information about the
receiving rate to the PCN-ingress-node at an interval that is shorter
than the measuring interval of the PCN-ingress-node. If the PCN-
egress-node receives M-sequential unmarked packets, it sends a packet
for canceling termination to the PCN-ingress-node.
3.3. Operation at the PCN-ingress-node
3.3.1. Admission Decision
Just as in CL and SM, the admission decision is based on the CLE.
The ingress node stops admitting new flows if the CLE is greater than
a predefined threshold (CLE threshold). The CLE threshold is chosen
under the following maximum value. The maximum of the CLE threshold
MUST be
CLE threshold = (1/N)*rho , (1)
where rho represents the minimum ratio between the PCN-admissible-
rate and PCN-supportable-rate via all the links between the PCN-
ingress and egress nodes and N is the denominator of
marking.frequency 1/N. Note that the marking ratio approaches the
maximum CLE threshold described above when the load is the PCN-
admissible-rate at a bottleneck link via all the links between the
PCN-ingress and egress nodes as the number of superposition of flows
approaches infinity, as described in Appendix D.
Satoh, et al. Expires March 14, 2010 [Page 10]
Internet-Draft ST Marking September 2009
3.3.2. Flow Termination Decision
As soon as a PCN-ingress-node receives a packet with information
about a receiving rate from a PCN-egress-node, it starts measuring
the sending rate to the PCN-egress-node. It receives the packet
multiple times during the measuring interval and maintains the
minimum value of the receiving rate. At the end of the measurement
interval, it terminates flows whose bandwidths are the same as the
sending rate - (1-y)* min(receiving rate, sending rate). Because
flow termination affects the receiving rate after transmission delay,
the receiving rate can be larger than the sending rate. Therefore,
min(receiving rate, sending rate) is used. The value of y is small
enough to tolerate. It stops terminating flows or measuring the
sending rate as soon as it receives the packet for canceling
termination from the PCN-egress-node. This termination takes more
time when the PCN-supportable-rate is much lower than the physical
rate because the sending rate is almost the same as the receiving
rate even under a congested situation.
4. Admission Issues
4.1. Effect of Synchronization
CL and SM suffer from synchronization [I-D.zhang-pcn-performance-
evaluation, I-D.charny-pcn-single-marking]. Synchronization is
defined in [I-D.zhang-pcn-performance-evaluation] as the phenomenon
of some flows having all their packets marked, while other flows have
none of their packets marked. This phenomenon easily occurs in the
case of CBR flows. If the duration time of flows is infinity, a
superposition of homogeneous CBR flows shows periodic behaviour for
every interval between two sequential packets of a CBR flow. Even if
the duration time is limited, the superposition of homogeneous CBR
flows shows periodic behaviour when the number of flows is not
changed. When excess-traffic-marking is applied, the periodic
behaviour of the packets leads to periodic marking behaviour because
the periodic behaviour of the packets leads to the periodic behaviour
of tokens, which causes periodic marking behaviour. The period of
marking behaviour is the same as that of the behaviour of the
packets. The periodic marking behaviour lasts as long as the
periodic behaviour of packets. Synchronization makes the admission
and termination of CL and SM less accurate [I-D.zhang-pcn-
performance-evaluation, I-D.charny-pcn-single-marking].
Although STM uses partial marking for admission control, the marking
is not excess-traffic-marking but a kind of threshold-marking. It is
true that the periodic behaviour of packets leads to the periodic
behaviour of tokens, but the period of the marking behaviour is
Satoh, et al. Expires March 14, 2010 [Page 11]
Internet-Draft ST Marking September 2009
different from that of behaviour of packets when the
marking.frequency is not 1. The period of marking behaviour is
longer than the periodic behaviour of packets. Thus, no flows have
all their packets marked. Because the marking of STM is threshold
marking, more marking occurs for metered packets when 1 is chosen as
N at the marking of STM than when excess-traffic-marking is applied.
The ratio of marked packets to all the packets is approximately the
same as that of traffic load to the PCN-supportable-rate as shown in
Appendix D. Thus, the ratio of flows that have no packets marked in
STM is smaller than that in the excess-traffic-marking although some
flows have no packets marked at all. Furthermore, when PCN traffic
is close to the admissible rate, no packets are marked in a short
interval because of traffic fluctuations. A metered packet is not
marked when the rate of the PCN traffic is less than the admissible
rate in the marking of STM. This breaks the periodic marking
behaviour. Almost the same performance results were achieved with
and without randomized traffic, which supports the description above.
Therefore, STM is little affected by synchronization.
5. Termination Issues
5.1. Effect of dropping packets to Termination
When the PCN traffic is greater than the PCN-supportable-rate, all
the packets are threshold-marked in STM. Dropping packets themselves
does not influence the performance of STM termination. Therefore, a
node can drop any packets. Preferential dropping packets is not
necessary.
5.2. Effect of multi-bottleneck
In the case of multi-bottleneck links, over termination percentages
of STM are almost the same among all the bottleneck links although CL
makes over termination percentages of upstream bottleneck links worse
because CL is affected by accumulation of marking.
5.3. Speed and Accuracy of Termination
Because a PCN-ingress-node terminates flows every measurement
interval, the amount of termination can be roughly evaluated.
Therefore, by using the ratio between the physical link speed and the
PCN-supportable-rate, the value of y is estimated roughly in order to
finish termination within a certain interval. However, this
termination has a trade-off between termination speed and accuracy.
Satoh, et al. Expires March 14, 2010 [Page 12]
Internet-Draft ST Marking September 2009
6. Performance evaluation
We compared the performance of STM with that of CL. For admission,
an over admission percentage was chosen, and for flow termination,
over termination and termination time were chosen as performance
metrics.
For admission control, the performance of STM was almost the same as
that of CL, although STM was slightly inferior to CL.
For flow termination, when the load was slightly larger than the PCN-
supportable-rate and the traffic type was CBR, the over termination
percentages of STM were inferior to those of CL. However, when the
traffic type was VBR or SVD, the over termination percentages of STM
were almost the same as those of CL. When the load was much larger
than the PCN-supportable-rate, our simulation showed that the over
termination percentages of STM were superior to those of CL. STM
took more termination time than CL because STM terminates flows
little by little. In the multi-bottleneck case, over termination
percentages of STM are almost the same among all the bottleneck liks
because STM is not affected by accumulation of marking.
7. Impact on PCN marking behaviour
The goal of this section is to propose two minor changes to the PCN-
marking-behaviour framework as currently described in [I-D.ietf-pcn-
marking-behaviour] in order to enable the single threshold-marking
approach. We propose additions of a threshold meter function with
two thresholds and a combination of the meter functions. A new
threshold of the threshold meter function is larger than
TBthreshold.threshold. If the amount of tokens is less than the new
threshold of the threshold meter function, the metered packets are
partially marked and not all marked. This marking function includes
the ramp-marking in [I-D.briscoe-tsvwg-cl-phb]. The combination of
SwTB and MkTB is an example of the combination of the meter
functions.
8. Changes from -01 version
o Added simulation results of redifined termination time (Appendix
C)
o Added admission control using fractional marking (Appendix E)
o Other minor edits
Satoh, et al. Expires March 14, 2010 [Page 13]
Internet-Draft ST Marking September 2009
9. Acknowledgements
This research was partially supported by the National Institute of
Information and Communications Technology (NICT), Tokyo, Japan.
We thank Mr. Takayuki Uchida at U-software Corporation for helping
with the simulations and Professor Shigeo Shioda at Chiba University
for fruitful discussions. We also thank Assistant Professor Michael
Menth at the University of Wuerzburg for his careful reading of this
draft and fruitful discussions.
10. Appendix A: Simulation Setup and Environment
10.1. Network and Signaling Models
We used the three types of network topologies shown in the figures
below for simulations. They are the same as those in [I-D.charny-
pcn-single-marking] and [I-D.zhang-pcn-performance-evaluation], and
the first two figures are the same as those in [I-D. briscoe-tsvwg-
cl-phb]. The first type of network topology is single link (Fig.
A.1). The second type is a multi-link network with a single
bottleneck (termed "RTT") (Fig. A.2). The third type is a range of
multi-bottleneck topologies (termed "Parking Lot") (Fig. A.3).
A single link between an ingress and an egress node is shown in Fig.
A.1, where all flows enter at node A and depart from node B. This
topology is used to basically verify the behaviour of the algorithms
with respect to a single ingress-egress aggregate (IEA) in isolation.
A --- B
Figure A.1: Simulated single-link network.
A
\
B - D - F
/
C
Figure A.2: Simulated multi-link network.
Satoh, et al. Expires March 14, 2010 [Page 14]
Internet-Draft ST Marking September 2009
A--B--C A--B--C--D A--B--C--D--E--F
| | | | | | | | | | | | |
| | | | | | | | | | | | |
D E F E F G H G H I J K L
(a) (b) (c)
Figure A.3: Simulated multi-link network.
As shown in Fig. A.2, a set of ingresses (A, B, and C) are connected
to an interior node in the network (D). This topology is used to
study the behaviour of the algorithm where many IEAs share a single
bottleneck link. The number of ingresses varied in different
simulation experiments from 2 - 1800. All links generally have
different propagation delays. Thus, these propagation delays were
chosen randomly in the range of 1 - 100 ms. This node D in turn is
connected to the egress (F). In this topology, different sets of
flows between each ingress and the egress converge on a single link
D-F, where the PCN algorithm is enabled. The capacities of the
ingress links are not limiting, and hence no PCN is enabled on them.
The bottleneck link D-F was modeled with a 10-ms propagation delay in
all simulations. Therefore, the range of round-trip delays in the
experiments was from 22 - 220 ms.
Another type of network of interest is that with a parking lot (PLT)
topology, which has multi-bottleneck links. The simplest PLT with
two bottlenecks is illustrated in Fig. A.3(a). A traffic matrix with
this network on this topology is as follows.
o an aggregate of "2-hop" flows entering the network at A and
leaving at C (via the two links A-B-C)
o an aggregate of "1-hop" flows entering the network at D and
leaving at E (via A-B)
o an aggregate of "1-hop" flows entering the network at E and
leaving at F (via B-C)
In the 2-hop PLT shown in Fig. A.3(a), the points of congestion are
links A-B and B-C. The capacities of all the other links are not
limited. We also experimented with larger PLT topologies with three
bottlenecks (Fig. A.3(b)) and five bottlenecks (Fig. A.3(c)). In all
cases, we simulated one ingress-egress pair that carried the
aggregate of "long" flows traversing all N bottlenecks (where N is
the number of bottleneck links in the PLT topology) and N ingress-
egress pairs that carried flows traversing a single bottleneck link
and exited at the next "hop". In all cases, only the "horizontal"
links in Fig. A.3 were the bottlenecks, with non-limited capacities
Satoh, et al. Expires March 14, 2010 [Page 15]
Internet-Draft ST Marking September 2009
of all "vertical" links. We named the bottleneck IDs in the order of
lowest (upstream) to highest (downstream), e.g., bottleneck ID 1 is
the upstream link between nodes A and B and bottleneck ID 2 is the
downstream link between nodes B and C in Fig. A.3 (a). The
propagation delays for all links in all PLT topologies were set to 1
ms.
Our simulations concentrated primarily on the range of capacities of
"bottleneck" links with sufficient aggregation - above 128 Mbps for
voice and 2.4 Gbps for SVD. Higher link speeds will generally result
in higher levels of aggregation and hence generally better
performance of measurement-based algorithms. Therefore, it seems
reasonable to believe that the studied link speeds do provide
meaningful evaluation targets.
In the simulation model, a call request arrives at the ingress, which
immediately sends a message to the egress. The message arrives at
the egress after the propagation time plus link processing time (but
no queuing delay). When the egress receives this message, it
immediately responds to the ingress with the current CLE. If the CLE
is below the specified CLE threshold, the call is admitted. If
otherwise, it is rejected. An admitted call sends packets in
accordance with one of the chosen traffic models for the duration of
the call (see next section). The propagation delay from the source
to the ingress and from the destination to the egress is assumed to
be negligible and is not modeled.
In the admission control simulation, the PCN-admissible- and PCN-
supportable-rates were half the link speed and 90% of the link speed,
respectively, and in the flow termination simulation, the PCN-
admission-rate and PCN-supportable-rate were 20% and 40% of the link
speed in all the links. The actual queue size was 80,000 packets,
which was not the byte size because queue size was set by only the
number of packets in the NS2 simulator.
10.2. Traffic Models
We use the same types of traffic as those of [I-D.briscoe-tsvwg-cl-
phb], [I-D.charny-pcn-single-marking], and [I-D.zhang-pcn-
performance-evaluation]. These are CBR voice, on-off traffic
approximating voice with silence compression (termed "VBR"), and on-
off traffic with higher peak and mean rates (we termed the latter
"synthetic video" (SVD)). On-off traffic (VBR and SVD) is described
with a two-state Markov chain, and on and off periods were
exponentially distributed with the specified mean.
Each flow arrives according to the Poisson process. The distribution
of flow duration was chosen to be exponentially distributed with a
Satoh, et al. Expires March 14, 2010 [Page 16]
Internet-Draft ST Marking September 2009
mean of 1 min, regardless of the traffic type, which is the same as
that in [I-D.briscoe-tsvwg-cl-phb] and [I-D.charny-pcn-single-
marking] in admission simulation. The flow duration was infinity in
termination simulation in order to observe the effect by only flow
termination.
Traffic parameters for each type are summarized below.
CBR voice
o Packet length: 160 bytes
o Packet inter-arrival time: 20ms ((160*8)/(64*1000) s)
o Average rate: 64 Kbps
On-off traffic approximating voice with silence compression
o Packet length: 160 bytes
o Packet inter-arrival time during on period: 20 ms
o Long-term average rate: 21.76 Kbps
o On period mean duration: 340ms; during the on period traffic is
sent with the CBR voice parameters described above
o Off period mean duration: 660 ms; no traffic is sent for the
duration of the off period
SVD
o Packet length: 1500 bytes
o Packet inter-arrival time during on period: 1 ms
o Long term average rate: 4 Mbps
o On period mean duration: 340 ms
o Off period mean duration: 660 ms
10.3. Performance Metrics
In our experiments, we used the percent deviation of the mean rate of
the expected load level as a performance metric. We term these
"over-admission" and "over-termination" percentages, depending on the
type of experiment.
Satoh, et al. Expires March 14, 2010 [Page 17]
Internet-Draft ST Marking September 2009
In our experiments of admission control, we compared the actual
achieved average throughput to the desired traffic load (PCN-
admissible-rate). The desired traffic load is not the exact
admissible rate because a signal packet for a new flow is sent for
admission. Therefore, the desired traffic load is the admissible
rate minus the amount of signal packets for non-admitted flows.
In our experiments of flow termination, we compared the actual
achieved average throughput to the desired traffic load (PCN-
supportable-rate) and measured termination time. As termination
time, we measured time between the first termination and the
termination by which the PCN rate is less than the PCN-supportable-
rate. The actual termination time takes more time to measure rates
at an ingress and egress nodes (200 ms for CL and 100 ms for STM) and
latency one-way time from the PCN-egress-node to PCN-ingress-node.
10.4. Parameter Settings for STM
All the simulations were run with the following values.
o SwTB.size = 20 ms at PCN-admissible-rate
o SwTB.threshold = 10 ms at PCN-admissible-rate
o MkTB.size = 10 ms at PCN-supportable-rate
o MkTB.threshold = 8 ms at PCN-supportable-rate
o Marking.frequency = 1/3 and 1
o CLE threshold is varied in Table B.1
o EWMA weight is varied in Table B.1
o Number of sequential marked packets for termination = 100
o Number of sequential unmarked packets for stopping termination =
20
o Extra percentage of receiving or sending rate more than the
difference between sending and receiving rates for termination at
one time = 5.0
o Interval between sending the receiving rate = 33.3 ms
o Interval for measuring sending rate = 100 ms
Satoh, et al. Expires March 14, 2010 [Page 18]
Internet-Draft ST Marking September 2009
10.5. Parameter Settings for CL
All the simulations were run with 5 ms at the PCN-supportable-rate as
the token bucket size for termination and with the following virtual
queue thresholds.
o Min-marking-threshold: 5 ms at the PCN-admissible-rate
o Max-marking-threshold: 15 ms at the PCN-admissible-rate
o Virtual-queue-upper-limit: 20 ms at the PCN-admissible-rate
The virtual-queue-upper-limit puts an upper bound on how much the
virtual queue can grow. In the admission control simulation, the CLE
threshold and EWMA weight were set as 0.05 and 0.3, respectively.
All of the parameters of the virtual queue were the same as those in
[I-D.briscoe-tsvwg-cl-phb], [I-D.charny-pcn-single-marking], and
[I-D.zhang-pcn-performance-evaluation]. The value of 5 ms at the
PCN-supportable-rate as the token bucket size corresponds to 500
packets in the case of CBR, 170 packets in the case of VBR, and 666
packets in the cases of SVD. The token bucket depth was set to 64
packets for CBR, and for on-off traffic, to 128 or higher (in
[I-D.briscoe-tsvwg-cl-phb]) and to 256 packets (in [I-D.zhang-pcn-
performance-evaluation]).
10.6. Simulation Environment
We used NS2 for our simulation experiments. Simulations were run on
a Dell Power Edge 1950, Intel Quad-core Xeon 2.66GHz, 32GB RAM
computer running Red Hat Enterprise Linux (64bit).
11. Appendix B: Admission Control Simulation
11.1. Parameter Settings for Admission Control
We evaluated over-admission percentages when the load of the
bottleneck was five times the admissible rate, i.e., 2.5 times the
link speed. The simulation time was 300 s, and simulation results
during the time interval between 200 and 300 s were used for
performance metrics to obtain the results in the steady state.
Egress measurement parameters for STM: In our simulations, CLE
threshold was varied in Table B.1. The CLE was computed as an
exponential weighted moving average (EWMA). The weight was varied in
Table B.1. The CLE was computed on a per-packet basis.
Egress measurement parameters for CL: In our simulations, the chosen
Satoh, et al. Expires March 14, 2010 [Page 19]
Internet-Draft ST Marking September 2009
CLE threshold was 0.05. The CLE was computed as an exponential
weighted moving average (EWMA) with a weight of 0.3. The CLE was
computed on a per-packet basis. These values were the same as those
in Sect. 8.2.3 in [I-D.charny-pcn-single-marking].
11.2. Sensitivity to EWMA Weight and CLE Threshold
We simulated admission control of STM when the CLE threshold and EWMA
weight were the six cases shown in Table B.1. The results of case 1
were shown in the previous draft. We simulated the admission control
five times for each case. The smallest and largest over-admission
percentage values of the averages of the five simulations are shown
in Table B.2. The smallest and largest values of all five links are
shown when the topology was PLT(c). The smallest and largest values
can be over-admission percentages in a different link. Case 1, whose
results were shown in the previous draft, was the worst case of the
six in all of the simulations from the viewpoint of absolute
deviation from no over- and under-admission. The results of case 6
are shown in the following sections because that case was the best.
------------------------------------
Case | CLE threshold | EWMA weight
------------------------------------
1 | 0.05 | 0.0005
------------------------------------
2 | 0.05 | 0.01
------------------------------------
3 | 0.05 | 0.03
------------------------------------
4 | 0.05 | 0.3
------------------------------------
5 | 0.00001 | 0.3
------------------------------------
6 | 0.000001 | 0.3
------------------------------------
Table B.1: CLE thresholds and EWMA weights in our simulation
Satoh, et al. Expires March 14, 2010 [Page 20]
Internet-Draft ST Marking September 2009
------------------------------------
Traffic| Topo. | Smallest | Largest
------------------------------------
|S.Link | 0.028 | 0.285
|----------------------------
|RTT10 | 0.585 | 0.844
|----------------------------
CBR |RTT70 | -1.656 | 0.942
|----------------------------
|RTT600 | -5.218 | 0.234
|----------------------------
|RTT1000| -6.030 | -0.179
|----------------------------
|PLT(c) | 0.005 | 0.103
------------------------------------
|S.Link | 0.979 | 1.300
|----------------------------
|RTT10 | -0.753 | 1.562
|----------------------------
VBR |RTT70 | -3.249 | 1.462
|----------------------------
|RTT600 | -5.427 | 0.699
|----------------------------
|RTT1800| -5.870 | -0.077
|----------------------------
|PLT(c) | 0.408 | 0.752
------------------------------------
|S.Link | 4.308 | 4.741
|----------------------------
|RTT10 | 1.593 | 4.982
|----------------------------
SVD |RTT35 | -1.981 | 5.999
|----------------------------
|RTT140 | -5.502 | 4.679
|----------------------------
|RTT300 | -7.192 | 1.302
|----------------------------
|PLT(c) | 0.993 | 2.382
------------------------------------
Table B.2:Smallest and largest values of over-admission percentages
of all pairs of CLE threshold and EWMA weight
11.3. Basic Evaluation
Over-admission percentage statistics were evaluated using the single
link topology. Table B.3 gives results of an admission control
Satoh, et al. Expires March 14, 2010 [Page 21]
Internet-Draft ST Marking September 2009
simulation when the load was five times the admissible rate. When
the traffic type is CBR, the link speed is 128 Mbps and the load is
the rate of 5000 flows. The call interval per ingress-egress
aggregate (IEA) is 0.012 sec. When the traffic type is VBR, the link
speed is 78.3 Mbps and the load is the rate of 9000 flows. The call
interval per IEA is 0.0067 sec. When the traffic type is SVD, the
link speed is 2.45 Gbps and the load is the rate of 1500 flows. The
call interval per IEA is 0.04 sec. We show the average of the
results of five simulations with different random seeds for each
traffic type. The performance of STM was very good although it was
inferior to that of CL.
-------------------------
Type | Over Admission %
|-------------------
| STM | CL
-------------------------
CBR | 0.065 | 0.028
-------------------------
VBR | 1.249 | 0.979
-------------------------
SVD | 4.678 | 4.476
-------------------------
Table B.3: Over-admission percentage statistics obtained with single
link
11.4. Effect of Ingress-Egress Aggregation
We evaluated the effect of ingress-egress aggregation (IEA) using RTT
topology. As with the simulations in [I-D.charny-pcn-single-
marking], the aggregate load on the bottleneck was the same across
each traffic type with the aggregate load being evenly divided among
all ingresses.
11.4.1. CBR
Simulation results with traffic load conditions when the traffic type
was CBR are shown in Table B.4. The link speed of the bottleneck was
128 Mbps for all the cases with varying numbers of ingresses. It
corresponded to 2000 CBR flows. Thus, the PCN-admissible-rate
corresponded to 1000 CBR flows. The load corresponded to 5000 flows.
The second column in Table B.4 and the following tables is the
expected admitted number of connections per IEA. STM(r) in Table B.4
represents the results of STM with randomized CBR traffic. Each
packet of the randomized CBR traffic has an added delay distributed
Satoh, et al. Expires March 14, 2010 [Page 22]
Internet-Draft ST Marking September 2009
uniformly from 0 to 50 ms. The results of both CBR traffic and
randomized CBR traffic were almost the same, as shown in Table B.4.
These simulation results show that the accuracy of STM was little
affected by synchronization because synchronization effects are
largest in the case of CBR with low IEA [I-D.charny-pcn-single-
marking].
----------------------------------------------
No. of |Expected | Over Admission
ingresses|No. of | (%)
|connections|------------------------
|per IE pair| STM |STM (r)| CL
----------------------------------------------
10 | 100 | 0.750 | 0.786 | 0.761
----------------------------------------------
70 | 14.3 | 0.890 | 0.867 | 0.727
----------------------------------------------
600 | 1.6 | 0.122 |-0.085 | 0.038
----------------------------------------------
1000 | 1 |-0.241 |-0.433 |-0.179
----------------------------------------------
Table B.4: Over admission percentage statistics with CBR, RTT
11.4.2. VBR
Simulation results with traffic load conditions when the traffic type
was VBR are shown in Table B.5. The link speed of the bottleneck was
78 Mbps for all the cases with varying numbers of ingresses. This
link speed was 1800 times higher than the average rate of a VBR flow.
Thus, the PCN-admissible-rate was 900 times higher than the average
rate of a VBR flow. The load was 2.5 times higher than the link
speed. The result of STM is almost the same as that of CL.
Satoh, et al. Expires March 14, 2010 [Page 23]
Internet-Draft ST Marking September 2009
----------------------------------------
No. of |Expected |Over Admission
ingresses|No. of | (%)
|connections|------------------
|per IE pair| STM | CL
----------------------------------------
10 | 180 | 1.562 | 1.345
----------------------------------------
70 | 25.7 | 1.334 | 1.462
----------------------------------------
600 | 3 | -0.483 | 0.699
----------------------------------------
1800 | 1 | -1.822 | -0.077
----------------------------------------
Table B.5: Over-admission percentage statistics with VBR and RTT
11.4.3. SVD
Simulation results with traffic load conditions when the traffic type
was SVD are shown in Table B.6. The link speed of the bottleneck was
2448 Mbps for all the cases with varying numbers of ingresses. This
link speed was 600 times higher than the average rate of a SVD flow.
Thus, the PCN-admissible-rate was 300 times higher than the average
rate of a SVD flow. The load was 2.5 times higher than the link
speed. Although the result of STM is almost the same as that of CL,
CL is slightly superior to STM.
----------------------------------------
No. of |Expected |Over Admission
ingresses|No. of | (%)
|connections|------------------
|per IE pair| STM | CL
----------------------------------------
10 | 30 | 4.982 | 4.870
----------------------------------------
35 | 8.4 | 5.261 | 4.898
----------------------------------------
140 | 2 | 3.595 | 2.597
----------------------------------------
300 | 1 | -0.033 | 0.221
----------------------------------------
Table B.6: Over-admission percentage statistics with SVD and RTT
Satoh, et al. Expires March 14, 2010 [Page 24]
Internet-Draft ST Marking September 2009
11.5. Effect of Multi-bottleneck
We evaluated the effect of a multi-bottleneck with PLT topology. The
over- admission-percentage of each bottleneck ID is shown in Table
B.7. The bottleneck IDs are named in the order of lowest (upstream)
to highest (downstream). The alphabets in Table B.7 shows nodes in
Fig. A.3(c). When CBR was used as the traffic type, the link speed
of all the bottlenecks was 128 Mbps and the call-interval per IEA was
0.024 s. When VBR was used as the traffic type, the link speed of
all the bottlenecks was 78 Mbps and the call-interval per IEA was
0.01 s. When SVD was used as the traffic type, the link speed of all
the bottlenecks was 2448 Mbps and the call-interval per IEA was 0.08
s. Both show good performance. In the cases of CBR and VBR, CL is
slightly superior to STM. In the case of SVD, STM is slightly
superior to CL.
-------------------------------------------------------------
Traffic |Algorithm| Bottleneck ID
Type | | 1(A-B)| 2(B-C)| 3(C-D)| 4(D-E)| 5(E-F)
-------------------------------------------------------------
CBR | STM | 0.060 | 0.043 | 0.038 | 0.062 | 0.056
| CL | 0.019 | 0.025 | 0.015 | 0.005 | 0.009
-------------------------------------------------------------
VBR | STM | 0.690 | 0.684 | 0.708 | 0.749 | 0.752
| CL | 0.560 | 0.540 | 0.585 | 0.614 | 0.620
-------------------------------------------------------------
SVD | STM | 1.441 | 1.910 | 1.348 | 1.602 | 1.551
| CL | 1.887 | 1.908 | 1.952 | 2.123 | 2.382
-------------------------------------------------------------
Table B.7: Over admission percentage with multi-bottleneck
11.6. Fairness among Different Ingress-Egress Pairs
In [I-D.charny-pcn-single-marking], fairness is illustrated using the
ratio between the bandwidth of the long-haul aggregates and the
short-haul aggregates. We used CBR traffic with the load of each
bottleneck being five times the PCN-admissible-rate. The fairness
results for different topologies are shown in Table B.9. We measured
the ratios of the average throughput of short-haul aggregates to that
of long-haul aggregates during the simulation time at the first
bottleneck. The average of five simulations is displayed. The link
speed and call interval conditions in Table B.7 were used in this
experiment. Both show good performance.
Satoh, et al. Expires March 14, 2010 [Page 25]
Internet-Draft ST Marking September 2009
-----------------------------------------------------------------
|Topo| Simulation Time (s)
| | 10 | 20 | 30 | 40 | 50 | 60 | 70 | 80
-----------------------------------------------------------------
STM |PLT2| 0.98 | 1.00 | 1.05 | 1.11 | 1.18 | 1.25 | 1.32 | 1.39
CL | | 1.02 | 1.04 | 1.08 | 1.15 | 1.22 | 1.30 | 1.38 | 1.46
-----------------------------------------------------------------
STM |PLT3| 0.98 | 1.04 | 1.13 | 1.24 | 1.35 | 1.46 | 1.57 | 1.67
CL | | 0.98 | 1.00 | 1.05 | 1.12 | 1.21 | 1.30 | 1.41 | 1.52
-----------------------------------------------------------------
STM |PLT5| 1.02 | 1.06 | 1.17 | 1.31 | 1.46 | 1.62 | 1.79 | 1.97
CL | | 1.02 | 1.05 | 1.14 | 1.28 | 1.43 | 1.59 | 1.75 | 1.93
-----------------------------------------------------------------
Table B.8: Fairness performance
12. Appendix C: Flow termination
We evaluated over-termination percentages and the time to terminate
the necessary amount of traffic (termination time) when the load of
the bottleneck was 1.25 and 2.0 times the PCN-supportable-rate.
Over-termination percentages are defined as (PCN-supportable-rate -
the rate after termination)/PCN-supportable-rate) expressed as a
percentage. The PCN-admissible-rate and PCN-supportable-rate were
20% and 40% of the link speed, respectively, in all the links. The
load was lower than the PCN-admissible-rate at the beginning of the
simulation. The simulation time was 100 s. The duration of all the
flows was infinity. One IE-pair was generated at half the simulation
time (50 s). Each flow of the IE-pair arrived in accordance with
uniform distribution within the average of the packet interval in a
flow. This simulated the change of a route when there was a failure.
Over-termination percentages were calculated using the average rate
during the time interval between 80 and 100 s. In all the tables,
termination time is shown as the time between the first termination
and the termination by which the PCN traffic rate is less than PCN-
supportable-rate. We detected that the PCN traffic rate was less
than PCN-supportable-rate by comparing the result of multiplication
of the number of micro flows and the average rate of a micro flow
with the PCN-supportable-rate. The CL needs time for measuring SAR
and the sending rate and latency one-way time from the PCN-egress-
node to PCN-ingress-node. The STM needs time for measuring the
sending rate and the same latency as the CL.
When the traffic type was CBR, the link speed was 320 Mbps and the
load was the rate of 2500 and 4000 flows. When the traffic type was
VBR, the link speed was 109 Mbps and the load was the rate of 2500
Satoh, et al. Expires March 14, 2010 [Page 26]
Internet-Draft ST Marking September 2009
and 4000 flows. When the traffic type was SVD, the link speed was 4
Gbps and the load was the rate of 500 and 800 flows. We used
randomized CBR, VBR, and SVD in termination simulations. Each packet
of the randomized CBR, VBR, and SVD traffic has an added delay
distributed uniformly from 0 to 50 ms. We show the average of the
results of five simulations with different random seeds for each
traffic type.
12.1. Basic evaluation
The results of a termination control simulation with the single link
topology are shown in Table C.1. When the load was 1.25 times the
PCN-supportable-rate (SR in Table), the accuracy of the proposed
control was almost the same as that of the CL control in the cases of
VBR and SVD, although the proposed control was inferior to the CL
control in the case of CBR. However, when the load was 2.0 times the
PCN-supportable-rate, the proposed control was more accurate than the
CL control. We show the average of results of five simulations with
different random seeds for each traffic type. Termination times in
Table C.1 are include measuring time for SAR and the sending rate in
CL and measuring time for the sending rate in STM. The acutual
termination time is the sum of the value of Table C.1 and latency
one-way time from the PCN-egress-node to PCN-ingress-node.
Termination time in the following tables also include measuring time
for SAR and the sending rate in CL and measuring time for the sending
rate in STM.
-------------------------------------------------------------
Traffic | Load | Over termination(%)| Termination time (s)
Type |(x SR) |------------------------------------------
| | STM | CL | STM | CL
-------------------------------------------------------------
CBR | | 3.260 | 0.531 | 0.400 | 0.201
VBR | 1.25 | 13.201 | 13.785 | 0.381 | 0.250
SVD | | 12.367 | 14.552 | 0.400 | 0.707
-------------------------------------------------------------
CBR | | 3.461 | 12.441 | 1.300 | 0.224
VBR | 2.0 | 4.910 | 25.833 | 1.202 | 0.243
SVD | | 12.527 | 24.503 | 1.220 | 0.659
-------------------------------------------------------------
Table C.1: Over-termination percentage statistics and termination
time obtained with single link
Satoh, et al. Expires March 14, 2010 [Page 27]
Internet-Draft ST Marking September 2009
12.2. Effect of Ingress-Egress Aggregation
We evaluated the effect of ingress-egress aggregation (IEA) with RTT
topology. As with the simulations in [I-D.charny-pcn-single-
marking], the aggregate load on the bottleneck was the same across
each traffic type, with the aggregate load being evenly divided among
all ingresses.
12.2.1. CBR
Simulation results obtained with traffic load conditions when the
traffic type was CBR are shown in Table C.2. SR in the second column
represents the PCN-supportable-rate. The link speed of the
bottleneck was 320 Mbps and the propagation delay between the ingress
and egress nodes was 1 ms for all the cases of varying numbers of
ingresses. When the load is 1.25 times of PCN-supportable-rate, over
termination percentages of STM are larger than those of CL and
termination times of STM are slightly larger than those of CL. When
the load is 2.0 times of PCN-supportable-rate, over termination
percentages of STM are smaller than those of CL and termination times
of STM are over one second larger than those of CL.
-------------------------------------------------------------------
No. of |Load | Over termination (%) | Termination time (s)
Ingress |(x SR) |-----------------------------------------------
| | STM | CL | STM | CL
-------------------------------------------------------------------
2 | | 6.310 | 2.810 | 0.514 | 0.277
10 | 1.25 | 6.070 | 3.270 | 0.486 | 0.345
35 | | 7.451 | 4.170 | 0.500 | 0.405
70 | | 6.341 | 4.780 | 0.541 | 0.431
-------------------------------------------------------------------
2 | | 7.211 | 12.960 | 1.461 | 0.298
10 | 2.0 | 6.560 | 12.560 | 1.463 | 0.392
35 | | 6.171 | 13.370 | 1.491 | 0.451
70 | | 5.851 | 14.300 | 1.582 | 0.400
-------------------------------------------------------------------
Table C.2: Over-termination percentage statistics and termination
time obtained with CBR and RTT
12.2.2. VBR
Simulation results obtained with traffic load conditions when the
traffic type was VBR are shown in Table C.3. The link speed of the
bottleneck was 108.8 Mbps and the propagation delay between the
ingress and egress nodes was 1 ms for all the cases of varying
Satoh, et al. Expires March 14, 2010 [Page 28]
Internet-Draft ST Marking September 2009
numbers of ingresses. When the load is 1.25 times of PCN-
supportable-rate, over termination percentages of STM are smaller
than those of CL except the case of the number of ingress 10and
termination times of STM are slightly larger than those of CL. When
the load is 2.0 times of PCN-supportable-rate, over termination
percentages of STM are much smaller than those of CL and termination
times of STM are over one second larger than those of CL.
-------------------------------------------------------------------
No. of |Load | Over termination (%) | Termination time (s)
Ingress |(x SR) |-----------------------------------------------
| | STM | CL | STM | CL
-------------------------------------------------------------------
2 | | 9.696 | 11.320 | 0.591 | 0.316
10 | 1.25 | 11.226 | 10.564 | 0.487 | 0.368
35 | | 9.971 | 12.857 | 0.511 | 0.407
100 | | 8.112 | 15.422 | 0.679 | 0.379
-------------------------------------------------------------------
2 | | 5.377 | 20.768 | 1.480 | 0.322
10 | 2.0 | 5.536 | 22.791 | 1.461 | 0.364
35 | | 5.271 | 22.670 | 1.418 | 0.409
100 | | 4.534 | 25.033 | 1.644 | 0.418
-------------------------------------------------------------------
Table C.3: Over-termination percentage statistics and termination
time obtained with VBR and RTT
12.2.3. SVD
Simulation results obtained with traffic load conditions when the
traffic type was SVD are shown in Table C.4. The link speed of the
bottleneck was 4.00 Gbps and the propagation delay between the
ingress and egress nodes was 1 ms for all the cases of varying
numbers of ingresses. When the load is 1.25 times of PCN-
supportable-rate, over termination percentages of STM are smaller
than those of CL and termination times of STM are over one second
larger than those of CL. When the load is 2.0 times of PCN-
supportable-rate, over termination percentages of STM are much
smaller than those of CL and termination times of STM are over 1.5
second larger than those of CL.
Satoh, et al. Expires March 14, 2010 [Page 29]
Internet-Draft ST Marking September 2009
-------------------------------------------------------------------
No. of |Load | Over termination (%) | Termination time (s)
Ingress |(x SR) |-----------------------------------------------
| | STM | CL | STM | CL
-------------------------------------------------------------------
2 | | 12.078 | 15.748 | 0.469 | 0.452
10 | 1.25 | 12.906 | 16.016 | 0.340 | 0.367
35 | | 12.616 | 20.396 | 0.274 | 0.339
-------------------------------------------------------------------
2 | | 12.214 | 24.970 | 1.369 | 0.584
10 | 2.0 | 11.592 | 26.763 | 1.181 | 0.409
35 | | 13.390 | 31.583 | 1.072 | 0.398
-------------------------------------------------------------------
Table C.4: Over-termination percentage statistics and termination
time obtained with SVD and RTT
12.3. Effect of Multi-bottleneck
We evaluated the effect of multi-bottlenecks using PLT(c) topology.
The over-termination-percentage of each bottleneck ID and termination
time of the long-haul IEA are shown in Table C.5. These bottleneck
IDs are the same as those in Table B.7. The link speed of each
traffic type was the same as that in simulations of the effect of
IEA. The propagation delay between the ingress and egress nodes was
1 ms. Over termination percentages of STM are almost the same among
all the bottleneck links although those of CL worsen as the
bottleneck IDs decrease (upstream). CL is affected by accumulation
of marking. STM is not affected by it because all the packets are
marked in termination.
The results of termination time show in Table C.6. When the load is
1.25 times of PCN-supportable-rate, termination times of STM are
almost the same as those of CL. When the load is 2.0 times of PCN-
supportable-rate, termination times of STM are over one second larger
than those of CL.
Satoh, et al. Expires March 14, 2010 [Page 30]
Internet-Draft ST Marking September 2009
------------------------------------------------------------------
| | | Over termination (%)
Load |Traffic|Alg.|--------------------------------------------
(x SR) |Type | | Bottleneck ID
| | | 1(A-B) | 2(B-C) | 3(C-D) | 4(D-E) | 5(E-F)
------------------------------------------------------------------
|CBR |STM | 4.491 | 4.551 | 4.321 | 4.311 | 4.370
| |CL | 6.351 | 2.742 | 1.341 | 0.882 | 0.672
|---------------------------------------------------------
1.25 |VBR |STM | 15.443 | 15.893 | 15.729 | 15.134 | 15.741
| |CL | 17.321 | 13.343 | 12.459 | 11.201 | 11.127
|---------------------------------------------------------
|SVD |STM | 15.941 | 15.489 | 15.219 | 15.877 | 15.229
| |CL | 18.467 | 15.535 | 14.487 | 13.950 | 14.536
------------------------------------------------------------------
|CBR |STM | 4.371 | 4.552 | 4.301 | 4.241 | 4.741
| |CL | 20.291 | 12.601 | 9.571 | 8.050 | 7.550
|---------------------------------------------------------
2.0 |VBR |STM | 8.941 | 6.447 | 6.619 | 6.486 | 6.332
| |CL | 27.015 | 14.756 | 14.408 | 14.510 | 14.242
|---------------------------------------------------------
|SVD |STM | 18.019 | 15.547 | 16.355 | 16.334 | 15.983
| |CL | 27.115 | 15.151 | 14.097 | 14.263 | 13.472
------------------------------------------------------------------
Table C.5: Over-termination percentage statistics and termination
time obtained with multi-bottleneck
Satoh, et al. Expires March 14, 2010 [Page 31]
Internet-Draft ST Marking September 2009
-------------------------------------------------------------
Load (x SR) |Traffic Type|Algorithm | Termination time (s)
-------------------------------------------------------------
|CBR | STM | 0.402
| | CL | 0.212
|---------------------------------------------
1.25 |VBR | STM | 0.402
| | CL | 0.226
|---------------------------------------------
|SVD | STM | 0.408
| | CL | 0.430
-------------------------------------------------------------
|CBR | STM | 1.302
| | CL | 0.209
|---------------------------------------------
2.0 |VBR | STM | 1.221
| | CL | 0.581
|---------------------------------------------
|SVD | STM | 1.325
| | CL | 0.459
-------------------------------------------------------------
Table C.6: Termination time obtained with multi-bottleneck
13. Appendix D: Why is TBthreshold.shallow.threshold set to be smaller
than the token bucket size by the bit-size of a metered packet?
The origin of the threshold marking is a virtual queue [I-D.briscoe-
tsvwg-cl-phb]. Therefore queueing theory is applied to marking.
Little's formulas are one of the most powerful relationship for G/G/1
in queueing theory where G/G/1 is described using Kendall's notation.
Both arrival process and service time distribution of G/G/1 is
described as a general distribution and 1 represents the number of
servers. Furthermore, Little's formulas are valid for any queue
discipline such as (first-in, first-out) FIFO, (Last-in, first-out)
LIFO, and (service in random order) SIRO.
TBthreshold.shallow.threshold is introduced to apply the Little's
formulas to marking.
At first, we explain Little's formulas in queueing theory [see Gross
and Harris]. Little's formulas are
L = lambda W (D.1)
and
Satoh, et al. Expires March 14, 2010 [Page 32]
Internet-Draft ST Marking September 2009
L_q = lambda W_q, (D.2)
where L represents the mean number of customers in the system and L_q
represents the expected number of customers in queue, lambda
represents the average rate of customers entering the queueing
system, W_q represents the expected time a customer spends waiting in
the queue prior to entering service, and W represents the expected
total time a customer spends in the queueing system. In queueing
theory, the term customer is used in a general sense and does not
imply necessarily a human customer.
From eqs. (D.1) and (D.2), the following equation is derived,
L - L_q = lambda(W-W_q) = lambda/mu = rho (D.3)
where mu represents the mean service rate, that is, 1/mu is the mean
service time and rho is traffic intensity. The left-hand side of
eq.(D.3) is the expected number of customers in service in the steady
state. Furthermore,
L = 1*p_1 + 2*p_2 + 3*p_3 + ...... (D.4)
and
L_q = 0*p_1 + 1*p_2 + 2*p_3 + ...... (D.5)
where p_n represents the probability that the number of customers in
the system is n in the steady state. From eqs. (D.4) and (D.5),
L - L_q = p_1 + p_2 + p_3 + ...... = 1 - p_0 = p_b (D.5)
where p_b is the probability that the server is busy in the steady
state.
If we get p_b, we get the traffic intensity. Marking by using
TBthreshold.shallow.threshold is a way to get p_b. The marking makes
each packet marked when the previous packet is in service. Each
packet is not marked only when no packet is in a virtual queue at the
packet's arrived time. The marking ratio gives an approximation of
p_b. Both are different generally because the time average and the
customer average are different, and p_b is the time average when the
server is busy and the marking ratio is the customer average.
However, both are the same when the arrival proces is a Poisson
Satoh, et al. Expires March 14, 2010 [Page 33]
Internet-Draft ST Marking September 2009
process. This property is called PASTA, which is abbreviation that
Poisson arrivals see time averages. Furthermore, if an arrival
process is described as a renewal process, an infinite superposition
of them is the Poisson process {Cox]. The renewal process is a large
class of stochastic processes. The inter-arrival time is independent
and identically distributed (IID). Therefore the marking ratio by
using TBthreshold.shallow.threshold is expected to give a good
approximation of the traffic intensity.
14. Appendix E: Admission control using fractional marking
We show another option of operation at PCN-interior-node. The
relation between PCN traffic rate and marking ratio is shown in Fig.
E.1, where AR and SR represent PCN-admissible- and PCN-supportable-
rates. If the PCN traffic rate is less than AR, no traffic is
marked. If the PCN traffic rate is between AR and SR, 1/N of the
traffic is marked. If the PCN traffic rate is greater than SR, all
the traffic is marked.
^
marking ratio |
1 + +----------------
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
1/N + +----------------+
| |
| |
| |
| |
---------------------+-----------------+-------------->
0 AR SR PCN traffic
rate
Figure E.1: Relation between PCN traffic rate and marking ratio
To achieve this marking behavior, we use two token buckets for a
Satoh, et al. Expires March 14, 2010 [Page 34]
Internet-Draft ST Marking September 2009
modified threshold marking called fractional marking
[MichaelPCNSurvey] and the threshold marking. The fractional marking
marks 1/N of the PCN traffic when the PCN traffic rate is greater
than a configured bit rate although the threshold marking marks all
PCN packets if the PCN traffic rate is greater than a configured bit
rate. The fractional metering and marking is applied to one token
bucket whose tokens are added at the PCN-admissible-rate. The
threshold metering and marking is applied to the other token bucket
whose tokens are added at the PCN-supportable-rate. Tokens in both
buckets are removed equal to the size in bits of the metered-packet.
The additions and removals in one token bucket are independent of the
other token bucket.
The marking explained above is expressed by the pseudo code of the
following algorithm, where FrTB.fill and ThTB.fill represent the fill
states of the token bucket for the fractional marking and threshold
marking, respectively. FrTB.size and ThTB.size (TBthreshold.max in
[I-D.pcn-marking-behaviour]) represent the token bucket sizes and
packet.size represents the size of the measured packet. lastUpdate
represents the time when both token buckets were last updated and now
represents the current time. FrTB.threshold and ThTB.threshold
represent configured thresholds. Cnt is a byte counter for marking
1/N of the measured traffic. M represents the marked state, and
packet.mark represents the state of the mark of a packet. A two-step
function, as shown in Fig. E.1 is achieved by this marking algorithm.
This algorithm enables us to distinguish AR- and SR- pre-congestion
states using two encoding states.
Input: pcn packet
//add tokens to the two token buckets
FrTB.fill = min(FrTB.size, FrTB.fill + FrTB.rate*(now - lastUpdate));
ThTB.fill = min(ThTB.size, ThTB.fill + ThTB.rate*(now - lastUpdate));
lastUpdate = now;
IF(FrTB.fill < FrTB.threshold) THEN
IF(Cnt < 0) THEN
packet.mark = M;
Cnt=Cnt+N*packet.size;
ENDIF
Cnt=Cnt-packet.size;
ENDIF
IF(ThTB.fill < ThTB.threshold)
packet.mark = M;
ENDIF
//remove tokens from each token bucket
FrTB.fill = max(0, FrTB.fill - packet.size);
ThTB.fill = max(0, ThTB.fill - packet.size);
Output: void
Satoh, et al. Expires March 14, 2010 [Page 35]
Internet-Draft ST Marking September 2009
15. IANA Considerations
TBD
16. Security Considerations
TBD
17. Informative References
[Cox] Cox, D., "Renewal Theory", 1962.
[Gross and Harris]
Gross, D. and C. Harris, "Fundamentals of Queueing
Theory", 1998.
[I-D.babiarz-pcn-3sm]
Babiarz, J., Liu, X-G., Chan, K., and M. Menth, "Three
State PCN Marking", November 2007.
[I-D.briscoe-tsvwg-cl-phb]
Briscoe, B., Eardley, P., Songhurst, D., Le Faucheur, F.,
Charny, A., Liatsos, V., Babiarz, J., Chan, K., Dudley,
S., Karagiannis, G., Bader, A., and L. Westberg, "Pre-
Congestion Notification Marking", October 2006.
[I-D.charny-pcn-single-marking]
Charny, A., Zhang, J., Le Faucheur, F., and V. Liatsos,
"Pre-Congestion Notification Using Single Marking for
Admission and Termination", November 2007.
[I-D.ietf-pcn-architecture]
Eardley, P., "Pre-Congestion Notification Architecture",
January 2009.
[I-D.ietf-pcn-baseline-encoding]
Moncaster, T., Briscoe, B., and M. Menth, "Baseline
Encoding and Transport of Pre-Congestion Information",
Feburary 2009.
[I-D.ietf-pcn-marking-behaviour]
Eardley, P., "Marking behaviour of PCN-nodes",
October 2008.
[I-D.westberg-pcn-load-control]
Westberg, L., "LC-PCN: The Load Control PCN Solution",
Satoh, et al. Expires March 14, 2010 [Page 36]
Internet-Draft ST Marking September 2009
November 2008.
[I-D.zhang-pcn-performance-evaluation]
Zhang, J., Charny, A., Liatsos, V., and F. Le Faucheur,
"Performance Evaluation of CL-PHB Admission and
Termination Algorithms", July 2007.
[MichaelPCNSurvey]
Menth, M., Lehrieder, F., Briscoe, B., Eardley, P.,
Moncaster, T., Babiarz, J., Charny, A., Zhang, J., Taylor,
T., Chan, K., Satoh, D., Geib, R., and G. Karagiannis, "A
Survey of PCN-Based Admission Control and Flow
Termination", 2010.
Authors' Addresses
Daisuke Satoh
NTT Advanced Technology Corporation
1-19-18, Nakacho
Musashino-shi, Tokyo 180-0006
Japan
Email: daisuke.satoh@ntt-at.co.jp
Harutaka Ueno
NTT Advanced Technology Corporation
Email: harutaka.ueno@ntt-at.co.jp
Yukari Maeda
NTT Advanced Technology Corporation
Email: yukari.maeda@ntt-at.co.jp
Oratai Phanachet
NTT Advanced Technology Corporation
Email: oratai.phanachet@ntt-at.co.jp
Satoh, et al. Expires March 14, 2010 [Page 37]