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

Versions: 00 01

Network Working Group                                         J. Babiarz
Internet-Draft                                                  X-G. Liu
Intended status: Informational                                   K. Chan
Expires: December 31, 2007                                        Nortel
                                                                M. Menth
                                                 University of Wuerzburg
                                                           June 29, 2007


                        Three State PCN Marking
                        draft-babiarz-pcn-3sm-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 December 31, 2007.

Copyright Notice

   Copyright (C) The IETF Trust (2007).

Abstract

   This document proposes metering and marking mechanisms for PCN-
   enabled nodes to label packets with pre-congestion information.  The
   marker marks all PCN packets with an admission-stop (AS) codepoint if
   the PCN traffic rate on a link exceeds its admissible rate (AR) and
   when it exceeds its supportable rate (SR), it marks some of those



Babiarz, et al.         Expires December 31, 2007               [Page 1]


Internet-Draft           Three State PCN Marking               June 2007


   packets exceeding SR with an excess-traffic (ET) codepoint.  The
   flows with ET-marked packets will be terminated until the aggregate
   PCN traffic on the path decreases below its SR.  This document
   proposes metering and marking mechanisms for these objectives.


Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  3
     1.1.  Requirements Notation  . . . . . . . . . . . . . . . . . .  4
     1.2.  Overview of PCN  . . . . . . . . . . . . . . . . . . . . .  4
     1.3.  Terminology used in this Document  . . . . . . . . . . . .  6
   2.  Three State PCN Marker with Marking Frequency Reduction
       for Marked Flow Termination  . . . . . . . . . . . . . . . . .  8
     2.1.  SR-Meter and ET-Marker . . . . . . . . . . . . . . . . . .  9
       2.1.1.  Mechanism for SR-Metering and ET-Marking . . . . . . .  9
       2.1.2.  Pseudo Code for the SR-Meter and ET-Marker . . . . . .  9
       2.1.3.  Configuration of the SR-Meter and ET-Marker  . . . . . 10
       2.1.4.  Characteristics of the Proposed  SR-Meter and
               ET-Marker Behaviour  . . . . . . . . . . . . . . . . . 10
     2.2.  AR-Meter and AS-Marker . . . . . . . . . . . . . . . . . . 11
       2.2.1.  Mechanism for AR-Metering and AS-Marking . . . . . . . 11
       2.2.2.  Pseudo Code for AR-Meter and AS-Marker . . . . . . . . 12
       2.2.3.  Configuration of the AR-Meter and AS-Marker  . . . . . 12
       2.2.4.  Characteristics of the Proposed AR-Metering and
               AS-Marking Behaviour . . . . . . . . . . . . . . . . . 12
     2.3.  Marking Codepoints . . . . . . . . . . . . . . . . . . . . 13
   3.  Security Considerations  . . . . . . . . . . . . . . . . . . . 13
   4.  Changes from Previous Revision . . . . . . . . . . . . . . . . 14
     4.1.  Acknowledgements . . . . . . . . . . . . . . . . . . . . . 14
   5.  Informative References . . . . . . . . . . . . . . . . . . . . 14
   Appendix A.  Overview of Token Bucket (TB) and Virtual Queue
                (VQ)  . . . . . . . . . . . . . . . . . . . . . . . . 15
     A.1.  Virtual Queue (VQ) . . . . . . . . . . . . . . . . . . . . 15
     A.2.  Token Bucket (TB)  . . . . . . . . . . . . . . . . . . . . 16
     A.3.  Tail Marking . . . . . . . . . . . . . . . . . . . . . . . 16
     A.4.  Tail Marking with Marking Frequency Reduction  . . . . . . 17
     A.5.  Threshold Marking  . . . . . . . . . . . . . . . . . . . . 18
     A.6.  Related Work . . . . . . . . . . . . . . . . . . . . . . . 19
   Appendix B.  Discussion of PCN Characteristics . . . . . . . . . . 20
   Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 22
   Intellectual Property and Copyright Statements . . . . . . . . . . 24









Babiarz, et al.         Expires December 31, 2007               [Page 2]


Internet-Draft           Three State PCN Marking               June 2007


1.  Introduction

   Pre-Congestion Notification (PCN) builds on the concepts of
   [RFC3168], "The addition of Explicit Congestion Notification (ECN) to
   IP".  It is used to implement admission control and flow termination
   for real-time flows (such as voice, video and multimedia streaming)
   in DiffServ [RFC2474], [RFC2475] enabled networks.  Flow admission
   control determines whether a new flow can be added into the network
   without overloading any of its links, whereas flow termination
   reduces the current PCN traffic load by terminating marked flows when
   at least one link in the network is overloaded for some reason.

   For each link in a PCN-enabled network an admissible rate (AR) is
   configured.  When the current PCN traffic rate on a link exceeds its
   AR, the link is said AR-overloaded.  Then, the corresponding PCN node
   re-marks all PCN packets on this link with an "admission-stop" (AS)
   codepoint.  The PCN egress nodes analyze the packet markings and if
   sufficiently many packets are AS-marked within an ingress-egress
   aggregate, the PCN egress nodes signal "admission-stop" for this
   aggregate to the appropriate admission control entity.  The objective
   is to avoid that the admitted PCN traffic on the links exceeds their
   ARs.  When the PCN egress nodes stop receiving AS-marked packets,
   they signal "admission-continue" after some time.

   Similarly, a supportable rate (SR) is configured for each link in a
   PCN-enabled network.  When the current PCN traffic rate on a link
   exceeds its SR, the link is said SR-overloaded.  Then, the
   corresponding PCN node re-marks some of the PCN packets on this link
   with an "excess-traffic" (ET) codepoint.  The PCN egress nodes pass
   the marking information to the appropriate flow termination entity
   (e.g. at the respective PCN ingress nodes) to terminate flows in
   order to reduce the PCN traffic rate of the SR-overloaded link below
   its SR.  The reader is referred to [PCN Architecture draft] for
   details.

   A simple and intuitive approach for flow termination works as
   follows.  When every packet exceeding the SR is re-marked to ET, the
   excess traffic rate can be determined at the PCN egress node by
   measuring the rate of ET-marked packets.  This rate is signalled to
   the appropriate flow termination entity to choose a suitable set of
   flows for termination.  However, this method has two major drawbacks.

   1.  A trustworthy measurement result takes time and delays the flow
       termination.

   2.  In case of multipath routing, the flows of a single ingress-
       egress aggregate may take different paths.  Terminating arbitrary
       flows of an ingress-egress aggregate may result in the



Babiarz, et al.         Expires December 31, 2007               [Page 3]


Internet-Draft           Three State PCN Marking               June 2007


       termination of flows that do not contribute to the SR-overload of
       the bottlenecked link.

   This document proposes "marked flow termination" with "marking
   frequency reduction" to solve these problems.  In order to terminate
   only flows that really contribute to the experienced SR-overload,
   only ET-marked flows must be terminated (marked flow termination).
   Terminating all ET-marked flows leads to a very fast reaction because
   no rate measurement at the PCN egress is required.  However, if all
   PCN packets exceeding SR are ET-marked, this terminates more flows
   than necessary.  Therefore, we propose to reduce the marking
   frequency by a slow-down parameter "s" to control the speed of the
   flow termination in order to avoid that more flows than necessary are
   terminated.  Thus, the objective of "marked flow termination" with
   marking frequency reduction is to quickly terminate the right flows
   and the right number of flows in case of SR-overload.

   This document defines metering behaviours to quickly detect whether
   the PCN traffic rate on a link has exceeded its admissible or
   supportable rate and marking behaviours to label packets with
   admission-stop and excess-traffic information accordingly.  In
   particular, marking frequency reduction is supported by the proposed
   ET-marker.  This yields "three state PCN marking" because packets are
   labelled either with "no pre-congestion" (NP), "admission-stop" (AS),
   or "excess-traffic" (ET).

   The document is structured as follows.  After a short introduction to
   PCN and the used terminology, we explain the admission control and
   "marked flow termination" functions.  Then, "three state PCN marking
   with marking frequency reduction" is described which is suitable to
   support "marked flow termination".  The appendix summarizes
   background information about token bucket (TB) and virtual queue (VQ)
   metering and marking as they are the base for the proposed metering
   and marking mechanisms, and it discusses the behaviour of the
   proposed three state PCN marking with marking frequency reduction for
   "marked flow termination".

1.1.  Requirements Notation

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in [RFC2119].

1.2.  Overview of PCN

   PCN traffic can be classified by DSCP or group of DSCPs and is
   forwarded by an appropriated PHB.  PCN configures for each link an
   admissible and a supportable rate (AR, SR).  PCN traffic enters the



Babiarz, et al.         Expires December 31, 2007               [Page 4]


Internet-Draft           Three State PCN Marking               June 2007


   network with a "no-precongestion" (NP) mark.  PCN nodes meter the PCN
   traffic on every link.  When the PCN traffic rate on a link exceeds
   the corresponding AR, the PCN node re-marks all NP-marked PCN packets
   to "admission-stop" (AS).

   Similarly, they re-mark some non-ET-marked PCN packets to "excess-
   traffic" (ET) when the PCN traffic rate on a link exceeds the
   corresponding SR.  Figure 1 summarizes the relation between the AR
   and SR thresholds and the marking behaviour.  The SR normally is at
   least a delta above the AR and a delta below the maximum service rate
   for PCN traffic for the sake of stability of the measurement-based
   reactive system.  If the PCN traffic rate is below AR, no packets are
   re-marked; if it is between AR and SR, all NP-marked PCN packets are
   re-marked to AS; and if it is above SR, some non-ET-marked PCN
   packets are re-marked to ET and all other NP-marked PCN packets are
   re-marked to AS.  Hence, the meters and markers operate in a marking-
   aware mode: NP-marked packets can be remarked to AS or ET, AS-marked
   packets can be remarked to ET but not to NP, and ET-marked packets
   cannot be remarked at all.

              PCN traffic rate
                100%^
                    |   AR- and SR-overload:
                    |   re-mark SOME non-ET-marked
                    |   packets to ET and the remaining to AS,
                    |   indicating that AR and SR are exceeded
    Supportable rate|----------------------------------------------
                    |   AR-overload:
                    |   re-mark ALL NP-marked packets to AS,
                    |   indicating admissible rate is exceeded
    Admissible rate |----------------------------------------------
                    |
                    |   No overload: do not re-mark any packets
                    |
                  0%+------------------------------------------------->

                 Figure 1: Packet re-marking by PCN nodes.

   PCN egress nodes monitor the PCN traffic per ingress-egress
   aggregate.  If they detect sufficiently many AS-marked packets, they
   relay this information to the appropriate admission control entities.

   More specifically, if most of the packets are AS-marked, the PCN
   traffic rate of at least one of the links in the ingress-egress path
   has exceeded its admissible rate, i.e. it is AR-overloaded.
   Therefore, the PCN egress signals "admission-stop" to the admission
   control entity for the corresponding ingress-egress aggregate such
   that no further flows are admitted.  As an alternative, probing may



Babiarz, et al.         Expires December 31, 2007               [Page 5]


Internet-Draft           Three State PCN Marking               June 2007


   be used for admission control.  The PCN ingress node generates and
   sends probe packets to test and verify the pre-congestion level on
   the ingress-egress path.  The PCN egress intercepts these probe
   packets.  If they are AS- or ET-marked, the requesting flows are not
   admitted (blocked).  Probing is useful or even essential under the
   following conditions:

   o  when an ingress-egress aggregate carries no traffic,

   o  in the presence of multipath routing, when some paths are already
      AR-overloaded, but others are not, and further flows should be
      admitted if they use a non-overloaded path.

   Although flows are admitted only if the PCN traffic rate does not
   exceed the AR on any link of their paths, it is possible that the PCN
   traffic rate on a link exceeds the SR, e.g., due to changed sending
   behaviour of admitted flows or due to route changes after a failure.
   PCN egress nodes monitor the PCN traffic and if they observe ET-
   marked packets, they send the information about the corresponding
   flows to the flow termination entity (e.g. the appropriate PCN
   ingress node) for possible termination.  If several ET-marked packets
   arrive at the PCN egress node within a short interval, the PCN egress
   node may collect the information of several ET-marked flows and send
   them in a single message to the appropriate flow termination entity
   to reduce the signalling rate.  As a consequence of the ongoing flow
   termination process, the PCN traffic rate decreases on the SR-
   overloaded link until it drops below the SR such that no further PCN
   packets are ET-marked.  It is important to terminate only ET-marked
   flows because other flows of the same ingress-egress aggregate may
   take different paths such that they do not contribute to the observed
   SR-overload.

   This description of flow termination is just one possible approach
   and other methods are possible with the marking proposed in this
   document.

1.3.  Terminology used in this Document

   We provide a brief definition of the terminology used in this
   document.

   o  PCN - Pre-Congestion Notification meters traffic rates per service
      class on a link and notifies the PCN egress nodes using packet
      marking whether a certain rate threshold is exceeded on any link
      of the path through the PCN-enabled network taken by the packet.
      The rate thresholds may be significantly lower than the line rates
      such that PCN egress nodes are notified long before queues build
      up in the buffers and real congestion occurs.  PCN is intended for



Babiarz, et al.         Expires December 31, 2007               [Page 6]


Internet-Draft           Three State PCN Marking               June 2007


      the implementation of measurement-based admission control and flow
      termination for real-time inelastic traffic, e.g., voice.  The PCN
      marking in the packet headers need to be standardized.

   o  ECN Field - Refers to the use of the standardized two bit field in
      the IP header that is used for signalling Explicit Congestion
      Notification [RFC3168].  In the PCN framework the ECN field maybe
      reused to signal two levels of Pre-Congestion Notification
      Marking.

   o  Service class - By service class we mean a grouping of packets
      belonging to one or more applications or services that generated
      traffic with similar characteristics and requiring similar QoS
      treatment.  See [RFC4594] for details.

   o  Admissible Rate - A rate threshold configured for links in the
      network; if it is exceeded by PCN traffic, the link is said to be
      AR-overloaded and no further flows using the AR-overloaded link
      should be admitted.  AR-overload is a type of pre-congestion.

   o  Supportable Rate - A rate threshold configured for links in the
      network; if it is exceeded by PCN traffic, the link is said to be
      SR-overloaded and some flows using the SR-overloaded link should
      be terminated.  SR-overload is a type of pre-congestion.

   o  Admission Control - It is the function of admitting or blocking
      requests of new flows or sessions for access to the network to
      prevent AR-overload.

   o  Flow Termination - It is the function of terminating already
      admitted flows in the sense that they cannot continue to send PCN
      traffic.  Only flows contributing to SR-overload are terminated to
      reduce SR-overload.

   o  No pre-congestion (NP) - Default marking for PCN packets that have
      not been carried over links with any type of pre-congestion (AR-
      overload or SR-overload).

   o  Admission-stop (AS) - Marking for packets to indicate that they
      have been carried over at least a single link with AR-overload.

   o  Excess-traffic (ET) - Marking for packets to indicate that they
      have been carried over at least a single link with SR-overload.








Babiarz, et al.         Expires December 31, 2007               [Page 7]


Internet-Draft           Three State PCN Marking               June 2007


2.  Three State PCN Marker with Marking Frequency Reduction for Marked
    Flow Termination

   The three state PCN marker (3sM) meters PCN packet streams per link
   and performs packet re-marking according to Figure 1.  As a
   consequence the following three marking states are required:

   o  no pre-congestion (NP),

   o  admission-stop (AS), and

   o  excess-traffic (ET).

   In theory, the meter meters each packet and passes the packet and the
   metering result to the marker and the marker marks packets according
   to the results of the meter according to Figure 2.  However, the two
   functions are described by integrated algorithms.

                         +------------+
                         |   Result   |
                         |            V
                     +-------+    +--------+
                     |       |    |        |
   Packet stream ===>| Meter |===>| Marker |===> Marked packet stream
                     |       |    |        |
                     +-------+    +--------+

           Figure 2: Block diagram of meter and marker function.

   The meter and marker controlling AR and marking packets with AS are
   called AR-meter and AS-marker and the meter and marker controlling SR
   and marking packets with ET are called SR-meter and ET-marker.  The
   marking may be coded in the ECN field [RFC3168] of the packet for a
   specified PHB in a specific manner.

   In the following, we choose to explain the behaviour of both meters
   and markers based on a token bucket (TB).  Similar metering and
   marking algorithms have been used (srTCM) [RFC2697] and are readily
   available in today's routers.  However, our description does not
   mandate TB-based implementations.  The same behaviour can be achieved
   from a similar implementation based on a virtual queue (VQ) or by any
   other approach.  The concepts of TB and VQ together with tail and
   threshold marking as well as reduced marking frequency are explained
   in the Appendix A.  The packet sizes counted by the meters and
   markers pertain to the size of the IP packet including its header
   bytes.





Babiarz, et al.         Expires December 31, 2007               [Page 8]


Internet-Draft           Three State PCN Marking               June 2007


2.1.  SR-Meter and ET-Marker

   We explain the mechanism for SR-metering and ET-marking, give pseudo
   code, explain its configuration, and discuss its behaviour.  We use
   object-oriented notation for most variables.

2.1.1.  Mechanism for SR-Metering and ET-Marking

   We propose an SR-meter and ET-marker based on a token bucket with
   tail marking and marking frequency reduction (see Appendix A for
   explanation).  The TB has a bucket of size TB.size which is
   continuously filled with tokens at rate TB.rate.  When a non-ET-
   labelled PCN packet arrives, it is re-marked with "ET" if the fill
   state of the bucket (TB.fill) in tokens is smaller than its size
   (packet.size) in bytes and "s" additional tokens are added to the
   bucket; otherwise, the fill state is reduced by packet.size tokens.
   The slow-down parameter "s" reduces the marking frequency of the
   mechanism.  If an ET-marked packet arrives, the TB's fill state is
   also incremented by "s" (this is an option and needs further
   discussion see Section 2.1.4).

2.1.2.  Pseudo Code for the SR-Meter and ET-Marker

   The behaviour of the token bucket with tail marking and marking
   frequency reduction for SR-metering and ET-marking is expressed by
   the following pseudo code using object-oriented notation.  It
   requires the time TB.lastUpdate at which the fill state of TB was
   last updated and a global variable "now" providing the current time.
   A PCN packet has the variables packet.mark showing its marking (NP,
   AS, ET) and packet.size showing its size.

   Input: pcn packet

    TB.fill = min(TB.size, TB.fill + TB.rate * (now - TB.lastUpdate));
    if (packet.mark<> ET)   / / if packet is not ET-marked
           if (TB.fill < packet.size)
                   packet.mark = ET;
                   TB.fill = min(TB.size, TB.fill + s);
           else
                   TB.fill = TB.fill - packet.size;
           endif
    else
           TB.fill = min(TB.size, TB.fill + s); // optional, see 2.1.4
   endif
   TB.lastUpdate = now;

   Output: void




Babiarz, et al.         Expires December 31, 2007               [Page 9]


Internet-Draft           Three State PCN Marking               June 2007


   According to the comment at the end of Section 2.1.4 the algorithm
   may be simplified by omitting the statement commented with "for the
   sake of fairness".  Further simulations need to evaluate its impact.

2.1.3.  Configuration of the SR-Meter and ET-Marker

   The following parameters must be configured:

   o  TB.rate: supportable rate (SR)

   o  TB.size: supportable burst size (SBS), needs to be set
      appropriately (-> simulations)

   o  Slow-down parameter "s": needs to be set appropriately (->
      simulations)

2.1.4.  Characteristics of the Proposed  SR-Meter and ET-Marker
        Behaviour

   The proposed mechanism can be applied with and without marking
   frequency reduction, i.e., s>0 and s=0, respectively.

   a) No marking frequency reduction (s=0)

   If the slow-down parameter is set to s=0, marking frequency reduction
   is switched off.  As an alternative, a simplified version of the
   given algorithm can be used.  If the PCN traffic rate on a link
   constantly exceeds its SR, the fill state of the TB decreases.
   Arriving packets for which the number of tokens in the bucket does
   not suffice are ET-marked.  The size of the token bucket (supportable
   burst size (SBS)) controls how fast the marker reacts to a traffic
   rate above SR: if it is set to a low value, packets are already
   marked at a rate lower than SR in the presence of bursts, if it set
   to a high value, marking starts delayed if the PCN traffic rate
   exceeds SR.  A nice property of this option is that the rate of the
   ET-marked packets is exactly the rate of the excess traffic rate
   under the assumption that there was no significant packet loss.

   Its drawback in conjunction with "marked flow termination" is that
   too many flows are terminated if all flows with ET-marked packets are
   selected for termination.  With marking approach where s=0, the
   egress node needs to perform rate measurements to determine how much
   traffic needs to be terminated.

   b) Marking frequency reduction (s>0)

   If the slow-down parameter is set to a value s>0, marking frequency
   reduction is achieved because for each marked packet up to additional



Babiarz, et al.         Expires December 31, 2007              [Page 10]


Internet-Draft           Three State PCN Marking               June 2007


   "s" bytes can pass the SR-meter and ET-marker without being re-marked
   to ET.  Thus, increasing the slow-down parameter "s" decreases the
   number of ET-marked packets.  In combination with "marked flow
   termination", a suitable "s" is required to achieve a fast
   termination of sufficiently many flows without terminating more flows
   than necessary.

   Its drawback in conjunction with the measurement of the excess
   traffic rate at the PCN nodes is that this rate cannot be determined
   directly.  For each ET-marked packet, up to "s" additional bytes can
   pass without ET-marked.  Therefore, an upper bound for the excess
   traffic rate is obtained by the rate of ET-marked packets at the PCN
   egress node plus the rate of ET-marked packets multiplied by "s"
   bytes per ET-marked packet.  If "s" is significantly larger than the
   maximum packet size, a CPU-saving approximation may be used: the rate
   of ET-marked packets multiplied by "s" bytes/packet.  Hence, it is
   possible to infer an upper bound for the excess traffic rate when
   marking frequency reduction is applied.

   ET-marked packets arriving at the SR-meter and ET-marker signify that
   a flow on the link will be terminated soon.  Therefore, the same fill
   state increment is performed by the SR-meter and ET-marker as if it
   had ET-marked the packet itself.  This is a matter of fairness and
   streamlining, but possibly has no visible impact under overload
   conditions.  Therefore, the algorithm may be simplified by ignoring
   packets that are already ET-marked.  This is subject to future
   research.

2.2.  AR-Meter and AS-Marker

   We explain the mechanism for AR-metering and AS-marking, give pseudo
   code for this mechanism, explain its configuration, and discuss its
   behaviour.

2.2.1.  Mechanism for AR-Metering and AS-Marking

   We propose an AR-meter and AS-marker based on a token bucket with
   threshold marking (see Appendix A for explanation).  The TB has a
   bucket of size TB.size which is continuously filled with tokens at
   rate TB.rate.  The AR-meter and AS-marker consider only packets that
   are not ET-marked.  When a non-ET-marked PCN packet arrives, it is
   re-marked to "AS" if the fill state of the bucket (TB.fill) in tokens
   is smaller than its size (packet.size) in bytes; otherwise, the fill
   state is reduced by packet.size tokens and if the fill state is then
   smaller than the marking threshold (TB.threshold), the packet is also
   re-marked to "AS" while if the fill state is then larger than or
   equal to the marking threshold, the packet is not re-marked.




Babiarz, et al.         Expires December 31, 2007              [Page 11]


Internet-Draft           Three State PCN Marking               June 2007


   The AR-meter an AS-marker is sensitive to ET-markings in the sense
   that only non-ET-marked packets are considered.  Therefore, packets
   should be first SR-metered and ET-marked by a PCN node before being
   AR-metered and AS-marked.  However, this requirement may be relaxed.

2.2.2.  Pseudo Code for AR-Meter and AS-Marker

   The behaviour of the token bucket with threshold marking for AR-
   metering and AS-marking is expressed by the following pseudo code
   using the same nomenclature like above.

   Input: pcn packet

   if (packet.mark <> ET) //consider only non-ET-marked packets
     TB.fill = min(TB.size, TB.fill+TB.rate*(now-TB.lastUpdate));
     if (TB.fill < packet.size)
         packet.mark = AS;
     else
         TB.fill = TB.fill - packet.size;
         if (TB.fill < TB.threshold)
             packet.mark = AS;
         endif
     endif
     TB.lastUpdate = now
   endif

   Output: void

   Note: The above algorithm may be simplified by considering all PCN
   packets (NP-marked, AS-marked and ET-marked).  This needs further
   analysis and simulations to evaluate its impact.

2.2.3.  Configuration of the AR-Meter and AS-Marker

   The following parameters must be configured:

   o  TB.rate: admissible rate (AR)

   o  TB.size (TBS): needs to be set appropriately (-> simulations)

   o  TB.threshold: TBS-ABS with ABS being the admissible burst size,
      needs to be set appropriately (-> simulations)

2.2.4.  Characteristics of the Proposed AR-Metering and AS-Marking
        Behaviour

   If the AR is exceeded, the TB fill state continuously decreases, it
   eventually falls below its marking threshold TB.threshold and only



Babiarz, et al.         Expires December 31, 2007              [Page 12]


Internet-Draft           Three State PCN Marking               June 2007


   increases if the PCN traffic rate on the link falls below AR.  As a
   consequence, all packets are AS-marked during that time and admission
   of further flows is stopped until the PCN traffic rate drops below
   AR.  In particular, also all probe packets are AS-marked.
   TB.threshold controls how fast the marker reacts to a PCN traffic
   rate that exceeds AR: if it is set to a high value (close to
   TB.size), packets are marked in the presence of burst at a PCN
   traffic rate lower than AR, if it set to a low value, AS-marking is
   delayed when the PCN traffic exceeds AR.  As well, the parameter
   TB.threshold controls how long the marker continues marking packets
   after the PCN traffic rate falls below AR.

   ET-marked packets are not subject to AR-metering and AS-marking
   because they belong to flows that are terminated soon.  In
   conjunction with marking frequency reduction, every ET-marked packet
   stands for up to "s" additional bytes that were ET-marked without
   marking frequency reduction, and as a consequence, not subject to AR-
   metering and AS-marking.  Therefore, the fill state of the TB for the
   AR-metering and AS-marking algorithm may be incremented by the slow-
   down parameter "s" whenever an ET-marked packet is observed.
   However, this makes the AR-metering and AS-marking algorithm more
   complex and this issue probably has only minor effect in practice.
   Therefore, this is not reflected in the pseudo code.  However, the
   impact of this difference is subject to future simulations.

2.3.  Marking Codepoints

   PCN metering and marking requires classification of traffic which is
   subject to PCN metering and PCN marking (PCN-capable).  Furthermore,
   PCN-aware flows that are subject to PCN-marking require at least the
   following codepoints:

   o  "no-precongestion" (NP),

   o  "admission-stop" (AS), and

   o  "excess-traffic" (ET).

   These signals may be encoded by re-using the two-bit ECN field or by
   different DS codepoints.  The actual encoding is out of the scope of
   this document.


3.  Security Considerations

   The Three State PCN Marker has no known security concerns.





Babiarz, et al.         Expires December 31, 2007              [Page 13]


Internet-Draft           Three State PCN Marking               June 2007


4.  Changes from Previous Revision

   The 00 version of this draft defines PCN metering and marking for
   both admission control and flow termination.  This draft incorporates
   the metering and marking approach for flow termination that was
   defined in draft-babiarz-pcn-explicit-marking-00.  Simulation results
   for the proposed "AR-metering and AS-re-marking" and "SR-metering and
   ET-re-marking" will be published in a separate draft.

4.1.  Acknowledgements

   The authors would like to thank the following people for reviewing
   this draft or earlier versions thereof and for their suggestions to
   make this document more complete: Dave McDysan, Nicolas Chevrollier
   and Frank Lehrieder.


5.  Informative References

   [Maglaris-88]
              Maglaris et al, "Performance Models of Statistical
              Multiplexing in Packet Video Communications, IEEE
              Transactions on Communications 36, pp. 834-844", July
               1988.

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119, March 1997.

   [RFC2474]  Nichols, K., Blake, S., Baker, F., and D. Black,
              "Definition of the Differentiated Services Field (DS
              Field) in the IPv4 and IPv6 Headers", RFC 2474,
              December 1998.

   [RFC2475]  Blake, S., Black, D., Carlson, M., Davies, E., Wang, Z.,
              and W. Weiss, "An Architecture for Differentiated
              Services", RFC 2475, December 1998.

   [RFC2697]  Heinanen, J. and R. Guerin, "A Single Rate Three Color
              Marker", RFC 2697, September 1999.

   [RFC2698]  Heinanen, J. and R. Guerin, "A Two Rate Three Color
              Marker", RFC 2698, September 1999.

   [RFC3168]  Ramakrishnan, K., Floyd, S., and D. Black, "The Addition
              of Explicit Congestion Notification (ECN) to IP",
              RFC 3168, September 2001.

   [RFC3246]  Davie, B., Charny, A., Bennet, J., Benson, K., Le Boudec,



Babiarz, et al.         Expires December 31, 2007              [Page 14]


Internet-Draft           Three State PCN Marking               June 2007


              J., Courtney, W., Davari, S., Firoiu, V., and D.
              Stiliadis, "An Expedited Forwarding PHB (Per-Hop
              Behavior)", RFC 3246, March 2002.

   [RFC4594]  Babiarz, J., Chan, K., and F. Baker, "Configuration
              Guidelines for DiffServ Service Classes", RFC 4594,
              August 2006.

   [SIM-07]   Liu, X-G. and J. Babiarz, "Simulation Results for Explicit
              PCN Marking and Flow Termination
              (http://standards.nortel.com/pcn/Simulation_EPCN.pdf)",
              February 2007.


Appendix A.  Overview of Token Bucket (TB) and Virtual Queue (VQ)

   Token buckets (TB) and virtual queues (VQ) serve to control whether a
   packet is conform to its flow's indicated rate R and burst size S.
   Therefore, TB parameters are frequently used as traffic descriptors.
   TBs and VQs are dual approaches: while packets are TB-conform as long
   as sufficient tokens are in the bucket at their arrival times, they
   are VQ-conform as long as sufficient free space is available in the
   queue at their arrival times.  Therefore, TBs and VQs can be used
   interchangeably and, in particular, algorithms given based on a TB
   description can be implemented by a VQ and vice-versa.

   In the following, we explain the basic VQ and TB mechanisms
   (Appendix A.1 and Appendix A.2).  Packets are marked depending on the
   state of the VQ or TB at their arrival time.  There are different
   marking options.  Only those packets that are not conform to its flow
   description may be marked (tail marking, Appendix A.3), or only some
   non-conforming packets may be marked (tail marking with marking
   frequency reduction, Appendix A.4), or all packets may be marked
   until the flow again reaches conformity (threshold marking,
   Appendix A.5).  Appendix A.6 gives an overview of where and how VQ
   and TB descriptions are used.

A.1.  Virtual Queue (VQ)

   We use an object-oriented notation for a more intuitive readability
   of the algorithms.  The VQ has a VQ rate (VQ.rate) and a queue which
   is capable to store up to VQ.size bytes.  The current length of the
   queue is denoted by VQ.length.  This length is reduced over time at
   rate VQ.rate.  When a packet arrives, it is "accepted" by the VQ and
   increments VQ.length by its size (packet.size) if there is still
   enough free space in the queue to accommodate it; otherwise it is
   "rejected".  As the queue size is decreased continuously over time,
   the behaviour of a VQ is best described by a fluid model.  However,



Babiarz, et al.         Expires December 31, 2007              [Page 15]


Internet-Draft           Three State PCN Marking               June 2007


   the state of the VQ shortly after packet arrivals can be calculated
   based on the current time "now" and the length of the VQ at the last
   update time of the VQ (VQ.lastUpdate) using the following algorithm:

   VQ.length = max(0, VQ.length - (now - VQ.lastUpdate) * VQ.rate);
   if (VQ.length + packet.size <= VQ.size)
           VQ.length = VQ.length + packet.size;
   endif
   VQ.lastUpdate = now;

A.2.  Token Bucket (TB)

   The TB is basically the same mechanism, but it looks at the problem
   from a different angle.  The TB has a TB rate (TB.rate) and a bucket
   which is capable to store up to TB.size tokens.  A token is the
   permission to send one byte.  The current fill state of the bucket is
   denoted by TB.fill.  This fill state is increased over time at rate
   TB.rate.  When a packet arrives, it is "accepted" and decrements
   TB.fill by its size (packet.size) if there are enough tokens in the
   bucket to send the entire packet; otherwise it is "rejected".  As the
   fill state is increased continuously over time, the behaviour of a TB
   is best described by a fluid model.  However, the state of the TB
   shortly after packet arrival can be calculated based on the current
   time "now" and the fill state of the TB at the last update time of
   the TB (TB.lastUpdate) using the following algorithm:

   TB.fill = min(TB.size, TB.fill + (now - TB.lastUpdate) * TB.rate);
   if (TB.fill >= packet.size)
           TB.fill = TB.fill - packet.size;
   endif
   TB.lastUpdate = now;

A.3.  Tail Marking

   To control whether packets of a stream with rate R and maximum burst
   size MBS are conform to the description R and MBS, the stream is
   metered either by a VQ with rate R and size MBS, or by a token bucket
   with rate R and bucket size MBS.  If a packet is accepted by the VQ
   or by the TB, it is marked in-profile.  If it is rejected, it is
   marked out-of-profile.

   The corresponding pseudo codes are for the VQ:









Babiarz, et al.         Expires December 31, 2007              [Page 16]


Internet-Draft           Three State PCN Marking               June 2007


   VQ.length = max(0, VQ.length - (now - VQ.lastUpdate) * VQ.rate);
   if (VQ.length + packet.size <= VQ.size)
           VQ.length = VQ.length + packet.size;
           packet.mark = in-profile;
   else
           packet.mark = out-of-profile;
   endif
   VQ.lastUpdate = now;

   and for the TB:

   TB.fill = min(TB.size, TB.fill + (now - TB.lastUpdate) * TB.rate);
   if (TB.fill >= packet.size)
           TB.fill = TB.fill - packet.size;
           packet.mark = in-profile;
   else
           packet.mark = out-of-profile;
   endif
   TB.lastUpdate = now;

A.4.  Tail Marking with Marking Frequency Reduction

   The objective of tail marking with marking frequency reduction is to
   mark only some of the packets that are out-of-profile.  The strength
   of the reduction can be controlled by the slow-down parameter "s".
   When a packet is classified out-of-profile, the VQ length is
   decremented by "s" bytes and the TB fill state is incremented by "s"
   tokens, respectively.  As a consequence, the VQ and the TB are not
   likely to mark consecutive packets as out-of-profile which reduces
   their marking frequency.

   The corresponding pseudo codes are for the VQ:

   VQ.length = max(0, VQ.length - (now - VQ.lastUpdate) * VQ.rate);
   if (VQ.length + packet.size <= VQ.size)
           VQ.length = VQ.length + packet.size;
           packet.mark = in-profile;
   else
      VQ.length = max(0, VQ.length-s); //marking frequency reduction
           packet.mark = out-of-profile;
   endif
   VQ.lastUpdate = now;

   and for the TB:







Babiarz, et al.         Expires December 31, 2007              [Page 17]


Internet-Draft           Three State PCN Marking               June 2007


   TB.fill = min(TB.size, TB.fill + (now - TB.lastUpdate) * TB.rate);
   if (TB.fill >= packet.size)
           TB.fill = TB.fill - packet.size;
           packet.mark = in-profile;
   else
     TB.fill = min(TB.size, TB.fill+s) //marking frequency reduction
      packet.mark = out-of-profile;
   endif
   TB.lastUpdate = now;

   If the slow-down parameter is set to s=0, the marking algorithm
   behaves like pure tail marking.

A.5.  Threshold Marking

   The objective of threshold marking is to mark all packets with, e.g.,
   "rate-exceeded" as long as some packets are out-of-profile with
   respect to flow parameters R and MBS.  We achieve that by setting the
   VQ or TB size larger than MBS, but by marking packets if the VQ
   length exceeds MBS or if the fill state of the TB falls below
   TB.size-MBS.  Thus, marking thresholds need to be configured
   differently for VQ and TB to obtain the same behavior:

   o  VQ.threshold = MBS;

   o  TB.threshold = TB.size - MBS.

   The corresponding pseudo codes are for the VQ:

   VQ.length = max(0, VQ.length - (now - VQ.lastUpdate) * VQ.rate);
   if (VQ.length + packet.size <= VQ.size) // packet in-profile
           VQ.length = VQ.length + packet.size;
        if (VQ.length > VQ.threshold)
                   packet.mark = "rate-exceeded";
           endif
   else                               // packet out-of-profile
           packet.mark = "rate-exceeded";
   endif
   VQ.lastUpdate = now;

   and for the TB:










Babiarz, et al.         Expires December 31, 2007              [Page 18]


Internet-Draft           Three State PCN Marking               June 2007


   TB.fill = min(TB.size, TB.fill + (now - TB.lastUpdate) * TB.rate);
   if (TB.fill >= packet.size) )          // packet in-profile
           TB.fill = TB.fill - packet.size;
           if (TB.fill < TB.threshold)
                   packet.mark = "rate-exceeded";
        endif
   else                                   // packet out-of-profile
           packet.mark = "rate-exceeded";
   endif
   TB.lastUpdate = now;

A.6.  Related Work

   The single rate three color marker (srTCM) [RFC2697] meters an IP
   packet stream and marks its packets green, yellow, or red.  The
   traffic is described by a committed information rate (CIR), a
   committed burst size (CBS), and an excess burst size (EBS).  If a
   packet is conform to a token bucket with parameters (CIR, CBS), it is
   colored green.  If it is conform to (CIR, EBS), it is colored yellow.
   Otherwise, it is colored red.  The implementation given in [RFC2697]
   is slightly different from an exact TB implementation, but it behaves
   similarly. srTCM is implemented in most of today's routers and can be
   used to perform threshold marking using the following mapping:

      green = non-AS;

      yellow = AS;

      red = AS;

      CIR = rate;

      CBS = MBS;

      EBS = TB.size or VQ.size

   Therefore, the proposed behavior for admission-stop marking can be
   obtained with today's technology.

   In contrast to the srTCM, the two rate three color marker (trTCM)
   [RFC2698] meters an IP packet stream based on a committed and a peak
   information rate (CIR, PIR) and marks its packets either green,
   yellow, or red.  The traffic is described by a CIR, a committed burst
   size (CBS), a PIR, and a peak burst size (PBS).  If a packet is
   conform to both (PIR, PBS) and (CIR, CBS), it is marked green.  If a
   packet is conform to (CIR, CBS) only, it is marked yellow.
   Otherwise, it is marked red.




Babiarz, et al.         Expires December 31, 2007              [Page 19]


Internet-Draft           Three State PCN Marking               June 2007


   Both srTCM [RFC2697] and trTCM [RFC2698] offer a color-aware and a
   color-blind operation mode where the packet marking is dependent or
   independent of already existing packet markings.  This is required
   for PCN marking in a similar way.  They are useful, for example, for
   ingress policing of traffic streams in a DiffServ environment.

   Policers drop out-of-profile packets instead of marking them.

   Shapers delay out-of-profile packets until they become in-profile.

   The leaky bucket shapes a traffic stream to a maximum rate R and
   drops all packets that exceed a maximum burst size MBS.
   [http://en.wikipedia.org/wiki/Leaky_bucket]


Appendix B.  Discussion of PCN Characteristics

   The Three State PCN marking behaviour can be realized through the use
   of a normal token bucket arrangement such as that is used for
   coloring packets in trTCM [RFC2698] with the following changes.  By
   redefining Peak Information Rate (PIR) to be supportable rate (SR)
   and Committed Information Rate (CIR) be admissible rate (AR).  When
   the PIR or SR token bucket runs out of tokens, the non-conforming
   packet is marked red or excess-traffic (ET).  The delta functionality
   is that each time a packet is ET marked, "s" tokens are added to the
   SR token bucket.  As well, the trTCM and the Three State PCN Marker
   has a lower rate that packets are measured against CIR or AR.  The
   delta functionality for the AR token bucket is a packet is marked as
   admission-stop (AS) when the token bucket reaches a "k" level, versus
   empty.  This delta function can be added to many of the routers that
   are in use today.

   Here we highlight some of the characteristics and benefits that
   excess-traffic (ET) marking approach has:

   1.   This marking approach works with Equal Cost Multipath (ECMP)
        routing in the network.  The router that has its traffic above
        supportable rate ET-marks packets.  The egress node detects ET-
        marked packets and signals flow termination to ingress node.

   2.   Works reasonable well in presence of low and high packet loss.
        (See simulation results details).  Packet loss only intrudes
        small delta delay for excess load reduction through flow
        termination to be completed.  If a marked packet is lost and the
        overload is still presented, the congested router will mark
        another packet.





Babiarz, et al.         Expires December 31, 2007              [Page 20]


Internet-Draft           Three State PCN Marking               June 2007


   3.   This approach is not that sensitive to the different number of
        flow, works well with small and large number of flows, constant
        bit rate, variable rate (on-off voice) and variable rate MPEG-4
        like traffic.  To date simulation results [SIM-07] indicate that
        this marking approach is not that sensitive to different flow
        counts and traffic characteristics.

   4.   It is believed that this marking approach will work reasonably
        well in presence of multiple congestion points in the path.  The
        ET marking approach has an exponential decay marking property,
        whereby the marking frequency decreases as the excess traffic
        load decreases and as traffic drops below supportable rate, ET
        marking stops.  In other words, flow termination slows down as
        the excess load approaches that supportable rate traffic level.
        This behaviour reduces traffic to just below supportable rate on
        all the routers in the path.

   5.   Simulations show that with mixed traffic of different rates and
        packet sizes, ET-marking approach marks higher bandwidth flows
        more aggressively.  Therefore after link failure condition the
        result is that more flows as total can be supported with the
        aggregate traffic being below the supportable rate.

   6.   Also it is believed that the ET marking approach and its
        exponential decay property should work well with bidirectional
        flows.  When a bidirectional flows is terminated, excess load is
        removed from the pre-congested router(s), therefore reducing the
        frequency of marking.

   7.   Simulations show that it works well over a wide range of round-
        trip times (RTTs) that are reasonable for real-time traffic.
        See [SIM-07] simulation results with different RTTs.  The "s"
        value should be configured so that it is greater than the number
        of octets transmitted by a flow in RTT.  For aggregation of
        voice flows that have various rates, using the mean rate should
        produce reasonable results.  More work is required before any
        guidelines for "s" can be stated.

   8.   Stable behaviour under most operating conditions.  Simulations
        show very good accuracy both for constant rate and variable rate
        traffic with small and large number of overload conditions.

   9.   This approach works well in gateway-to-gateway and host-to-host
        deployment models.

   10.  The ET marking behaviour is friendly to behaviour in [RFC3168]
        and should PCN flow encounter a router that performs [RFC3168]
        marking, it would provide some protection against congestion.  A



Babiarz, et al.         Expires December 31, 2007              [Page 21]


Internet-Draft           Three State PCN Marking               June 2007


        packet belonging to a PCN flow that is CE marked would be
        terminated.

   11.  If the egress edge node (gateway) reports which flows that need
        to be removed (terminated) versus bandwidth, than any reasonable
        value for "s" can be used.  The value for "s" and the algorithm
        do not need to be standardized, but only the metering and
        marking behaviour.  Different algorithms may be used to obtain
        the described metering and marking behaviour.


Authors' Addresses

   Jozef Z. Babiarz
   Nortel
   3500 Carling Avenue
   Ottawa, Ont.  K2H 8E9
   Canada

   Phone: +1-613-763-6098
   Email: babiarz@nortel.com


   Xiao-Gao Liu
   Nortel
   3500 Carling Avenue
   Ottawa, Ont.  K2H 8E9
   Canada

   Phone: +1-613-763-7516
   Email: xgliu@nortel.com


   Kwok Ho Chan
   Nortel
   600 Technology Park Drive
   Billerica, MA  01821
   USA

   Phone: +1-978-288-8175
   Email: khchan@nortel.com










Babiarz, et al.         Expires December 31, 2007              [Page 22]


Internet-Draft           Three State PCN Marking               June 2007


   Dr. Michael Menth
   University of Wuerzburg
   Institute of Computer Science
   Am Hubland, D-97074 Wuerzburg,  Room B206
   Germany

   Phone: (+49)-931/888-6644
   Email: menth@informatik.uni-wuerzburg.de











































Babiarz, et al.         Expires December 31, 2007              [Page 23]


Internet-Draft           Three State PCN Marking               June 2007


Full Copyright Statement

   Copyright (C) The IETF Trust (2007).

   This document is subject to the rights, licenses and restrictions
   contained in BCP 78, and except as set forth therein, the authors
   retain all their rights.

   This document and the information contained herein are provided on an
   "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
   OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND
   THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS
   OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF
   THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
   WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.


Intellectual Property

   The IETF takes no position regarding the validity or scope of any
   Intellectual Property Rights or other rights that might be claimed to
   pertain to the implementation or use of the technology described in
   this document or the extent to which any license under such rights
   might or might not be available; nor does it represent that it has
   made any independent effort to identify any such rights.  Information
   on the procedures with respect to rights in RFC documents can be
   found in BCP 78 and BCP 79.

   Copies of IPR disclosures made to the IETF Secretariat and any
   assurances of licenses to be made available, or the result of an
   attempt made to obtain a general license or permission for the use of
   such proprietary rights by implementers or users of this
   specification can be obtained from the IETF on-line IPR repository at
   http://www.ietf.org/ipr.

   The IETF invites any interested party to bring to its attention any
   copyrights, patents or patent applications, or other proprietary
   rights that may cover technology that may be required to implement
   this standard.  Please address the information to the IETF at
   ietf-ipr@ietf.org.


Acknowledgment

   Funding for the RFC Editor function is provided by the IETF
   Administrative Support Activity (IASA).





Babiarz, et al.         Expires December 31, 2007              [Page 24]


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