Network Working Group M. Menth
Internet-Draft F. Lehrieder
Expires: August 21, 2008 University of Wuerzburg
P. Eardley
BT
A. Charny
Cisco Systems, Inc.
J. Babiarz
Nortel
February 18, 2008
Edge-Assisted Marked Flow Termination
draft-menth-pcn-emft-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 August 21, 2008.
Copyright Notice
Copyright (C) The IETF Trust (2008).
Menth, et al. Expires August 21, 2008 [Page 1]
Internet-Draft Edge-Assisted Marked Flow Termination February 2008
Abstract
This document presents edge-assisted marked flow termination (EMFT)
for PCN. It assumes packet-size independent excess marking, i.e.
packets exceeding the supportable rate (SR) of a link are marked as
"excess-traffic" (ET). EMFT terminates only flows with at least one
ET-marked packet. The problem is to avoid that all flows with ET-
marked packets are terminated. This draft proposes two solutions.
Flow-based EMFT (F-EMFT) considers single flows separately and
terminates them when sufficiently many packets of them have been
received by the PCN egress node with an ET-mark. Aggregate-based
EMFT (A-EMFT) considers ingress-egress-aggregates and terminates
flows thereof sufficiently many ET-marked packets have been received
for that aggregate.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 5
3. Required Marking Behavior . . . . . . . . . . . . . . . . . . 7
3.1. Conventional Excess Marking . . . . . . . . . . . . . . . 7
3.2. Packet Size Independent Excess Marking (PSIEM) . . . . . . 7
4. Flow-Based Edge-Assisted Marked Flow Termination (F-EMFT) . . 8
5. Aggregate-Based Edge-Assisted Marked Flow Termination
(A-EMFT) . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
6. References . . . . . . . . . . . . . . . . . . . . . . . . . . 10
6.1. Normative References . . . . . . . . . . . . . . . . . . . 10
6.2. Informative References . . . . . . . . . . . . . . . . . . 10
6.3. Other References . . . . . . . . . . . . . . . . . . . . . 10
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 11
Intellectual Property and Copyright Statements . . . . . . . . . . 13
Menth, et al. Expires August 21, 2008 [Page 2]
Internet-Draft Edge-Assisted Marked Flow Termination February 2008
1. Introduction
PCN defines a new PCN traffic class that receives preferred treatment
by PCN nodes. It provides information to support admission control
(AC) and flow termination (FT) for this traffic type. PCN introduces
an admissible and a supportable rate threshold (AR(l), SR(l)) for
each link l of the network which imply three different link states.
If the PCN traffic rate r(l) is below AR(l), there is no pre-
congestion and further flows may be admitted. If the PCN traffic
rate r(l) is above AR(l), the link is AR-pre-congested and the rate
above AR(l) is AR-overload. In this state, no further flows should
be admitted. If the PCN traffic rate r(l) is above SR(l), the link
is SR-pre-congested and the rate above SR(l) is SR-overload. In this
state, some already admitted flows should be terminated. PCN nodes
monitor the PCN rate on their links and they remark packets depending
on their pre-congestion states. The PCN egress nodes evaluate the
packet markings and their essence is reported to the AC and FT
entities of the network such that they can take appropriate actions.
Therefore, this concept is called pre-congestion notification. This
draft proposes a new FT method.
The CL draft [I-D.briscoe-tsvwg-cl-architecture] proposes that all
packets above SR are marked with "excess-traffic" (ET). Packets of
the same ingress-egress aggregate (IEA) are grouped together for a
joint evaluation of their markings by the PCN egress node. If
packets are ET-marked, the PCN egress node signals the rate of
unmarked packets to the PCN ingress node which terminates so many
flows that their rate corresponds to the difference of the sent rate
per IEA and the rate that was received non-ET-marked by the PCN
egress node. We call this solution measured rate termination (MRT).
This solution has two major drawbacks:
o At low aggregation it is hard for the ingress node to determine an
appropriate set of flows to be terminated. Example: only a single
flow with 1 Mbit/s in the IEA, and 500 kbit/s should be
terminated. When many ingress nodes face the same problem and
solve it with the same algorithm, either overtermination or
undertermination occurs.
o In case of multipath routing, flows of a single IEA may take
different routes. The ingress node chooses the set of flows for
termination, but does not know which flows are carried over a pre-
congested link. Therefore, the wrong flows are possibly
terminated.
The 3sm draft [I-D.babiarz-pcn-3sm] proposes marked flow termination.
If a PCN node receives an ET-marked packet, it notifies the FT entity
to terminate the flow. To avoid overtermination, only a subset of
Menth, et al. Expires August 21, 2008 [Page 3]
Internet-Draft Edge-Assisted Marked Flow Termination February 2008
the packets above SR are ET-marked. The concept of IEA is not
needed. This method is called core-assisted marked flow termination
(CMFT) as only marked flows are terminated and core nodes help to
identify the flows that should be terminated. This method has one
major drawback:
o It requires packet size independent excess marking with marking
frequency reduction (MFR) which is not yet available in today's
routers.
Given the two approaches with their drawbacks, a FT method is
desirable where conventional excess marking can be used by PCN nodes,
that terminates only marked flows, and that is able to cope with IEAs
having only a small number of flows. We present such a solution in
this draft and call it edge-assisted marked flow termination (EMFT).
The motivating idea for EMFT is to roll a dice at the edges to decide
whether a marked packet is to be terminated instead of letting the
core nodes decide. The actual solution is slightly different and
saves the generation of random numbers per packet.
The next section clarifies some terminology issues. We then describe
the required marking behaviour. We present flow-based and aggregate-
based EMFT as new FT mechanisms and discuss security issues.
Menth, et al. Expires August 21, 2008 [Page 4]
Internet-Draft Edge-Assisted Marked Flow Termination February 2008
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
New terminology
o Flow termination (FT): function to terminate flows in case of SR-
pre-congestion
o No-pre-congestion (NP) marking: marking for packets that have not
yet experience any form of pre-congestion
o Packet size independent marking (PSIM): marks all packets
exceeding a certain rate, but the marking probability of a packet
is independent of its size. This is in contrast to pure excess
marking. May be implemented by a threshold marking algorithm.
o MFT: marked flow termination terminates only flows with at least
one ET-marked packet; guarantees that terminated flow traverses an
AR-pre-congested link.
o CMFT: core-assisted MFT: core nodes apply marking frequency
reduction to control termination speed of MFT
o EMFT: edge-assisted MFT: egde nodes control the termination speed
of MFT
o F-EMFT: flow-based EMFT
o A-EMFT: aggregate-based EMFT
o IEA: ingress-egress aggregate
o Flow termination delay D_T: duration of the interval between the
decision for the termination of a flow at the PCN egress node and
the time the PCN egress node does not receive packets of that flow
Menth, et al. Expires August 21, 2008 [Page 5]
Internet-Draft Edge-Assisted Marked Flow Termination February 2008
anymore.
Menth, et al. Expires August 21, 2008 [Page 6]
Internet-Draft Edge-Assisted Marked Flow Termination February 2008
3. Required Marking Behavior
EMFT works with conventional excess marking, but for the sake of
fairness, packet-size independent excess marking is preferred. We
describe both marking behaviours in the following.
3.1. Conventional Excess Marking
Conventional excess marking is based on a token bucket with size S
and Rate R. When a packet arrives, and the number of tokens in the
bucket is at least the packet size, the number of tokens is reduced
by the packet size. If the number of tokens in the bucket is smaller
than the packet size, the packet is marked.
Larger packets have a higher probability to be marked. Therefore,
marked flow termination (MFT) algorithms terminate flows sending
larger packets with a higher probability than flows sending small
packets.
3.2. Packet Size Independent Excess Marking (PSIEM)
PSIEM addresses the above problem and makes the marking probability
independent of the packet size. To that end, a marking threshold T
is introduced which is set to the maximum transfer unit (MTU). If a
packet arrives and the number of tokens in the bucket is T or larger,
the number of tokens in the bucket is reduced by the packet size. If
the number of tokens in the bucket is smaller than the threshold T,
it remains unchanged, but the packet is marked.
Menth, et al. Expires August 21, 2008 [Page 7]
Internet-Draft Edge-Assisted Marked Flow Termination February 2008
4. Flow-Based Edge-Assisted Marked Flow Termination (F-EMFT)
The PCN egress node keeps a credit counter C for each flow. When an
ET-marked packet arrives for a flow, the corresponding credit counter
is reduced by the size of that packet. If the credit counter is non-
positive at the arrival of a marked packet, the flow is terminated.
The difficulty is the suitable initialization of the credit counter
when a reservation is set up for a new flow. In [Menth08-PCN-MFT] we
have shown that the initial counter size should be exponentially
distributed with mean 2*R_f*E[DT]/alpha where R_f is the rate of the
flow f, E[DT] is a global average value for the flow termination
delay, and alpha is a knob to control the termination speed. The
parameter alpha should be set at most 1 to avoid that flows are
terminated too fast such that overtermination occurs. Smaller alpha
results in a longer time to reduce SR-overload. The impact of these
parameters is also studied in [Menth08-PCN-MFT].
Statistical flow termination priorities can be implemented by
granting larger initial credit counters to more important flows.
We give an example for a potential technical implementation of the
exponentially distributed credit counter size distribution. The end
system generates a random number x between 0 and 1. Then it
determines the initial size of the credit counter by
C=-ln(x)*2*R_f*E[D_T]/alpha.
Menth, et al. Expires August 21, 2008 [Page 8]
Internet-Draft Edge-Assisted Marked Flow Termination February 2008
5. Aggregate-Based Edge-Assisted Marked Flow Termination (A-EMFT)
If it is easy for the PCN egress node to identify all packets of the
same PCN ingress node, the packet markings can be evaluated on an
aggregate basis. Then, the following algorithm may be used. A
credit counter is associated with each IEA and initialized similarly
as for F-EMFT, i.e. by an exponential distribution with average value
2*E[R]*E[DT]/alpha where E[R] is the average rate of the current
flows in the IEA. Usually, E[R] is the rate R_f of the first flow
when the system starts with a single flow.
When ET-marked packets arrive and the credit counter is positive, the
size of the credit counter C is reduced by the packet size. If the
credit counter C is not positive, a flow f of the aggregate is
terminated and a deterministic increment of I=2*R_f*E[DT]/alpha is
added to the credit counter, i.e., the increment is proportional to
the rate of the terminated flow f. With this configuration, F-EMFT
and A-EMFT lead to the same termination behaviour.
Note that the flow f to be terminated can be the flow to which the
last ET-marked packet belongs to, but it may also be any other flow
for which an ET-marked packet recently arrived. This allows the
enforcement of termination policies. For instance, high priority
flows may be later terminated than low priority flows.
Menth, et al. Expires August 21, 2008 [Page 9]
Internet-Draft Edge-Assisted Marked Flow Termination February 2008
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.ietf-pcn-architecture]
Eardley, P., "Pre-Congestion Notification Architecture",
draft-ietf-pcn-architecture-01 (work in progress),
October 2007.
6.3. Other References
[Menth08-PCN-MFT]
Menth, M. and F. Lehrieder, "Termination Methods for End-
to-End PCN-Based Flow Control", February 2008, <http://
www3.informatik.uni-wuerzburg.de/staff/menth/Publications/
Menth08-PCN-MFT.pdf>.
Menth, et al. Expires August 21, 2008 [Page 10]
Internet-Draft Edge-Assisted Marked Flow Termination February 2008
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
Philip Eardley
BT
B54/77, Sirius House Adastral Park Martlesham Heath
Ipswich, Suffolk IP5 3RE
United Kingdom
Email: philip.eardley@bt.com
Anna Charny
Cisco Systems, Inc.
1414 Mass. Ave.
Boxborough, MA 01719
USA
Email: acharny@cisco.com
Menth, et al. Expires August 21, 2008 [Page 11]
Internet-Draft Edge-Assisted Marked Flow Termination February 2008
Jozef Z. Babiarz
Nortel
3500 Carling Avenue
Ottawa, Ont. K2H 8E9
Canada
Phone: +1-613-763-6098
Email: babiarz@nortel.com
Menth, et al. Expires August 21, 2008 [Page 12]
Internet-Draft Edge-Assisted Marked Flow Termination February 2008
Full Copyright Statement
Copyright (C) The IETF Trust (2008).
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, et al. Expires August 21, 2008 [Page 13]