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

Versions: 00

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]


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