Network Working Group                                          D. Wagner
Internet-Draft                                   University of Stuttgart
Intended status: Informational                             M. Kuehlewind
Expires: October 10, 2016                                     ETH Zurich
                                                           April 8, 2016


            Auditing of Congestion Exposure (ConEx) signals
                      draft-wagner-conex-audit-02

Abstract

   Congestion Exposure (ConEx) is a mechanism by which senders inform
   the network about the congestion encountered by previous packets on
   the same flow.  Reliable auditing is necessary to provide a strong
   incentive to declare ConEx information honestly.  This document
   defines how the signals are handled by an audit and lists
   requirements for an audit implementation.  This document does not
   mandate a particular design but identifies state and functions that
   any auditor element must provide to fulfill the requirements stated
   in [draft-ietf-conex-abstract-mech].

Status of This Memo

   This Internet-Draft is submitted in full conformance with the
   provisions of BCP 78 and BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF).  Note that other groups may also distribute
   working documents as Internet-Drafts.  The list of current Internet-
   Drafts is at http://datatracker.ietf.org/drafts/current/.

   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."

   This Internet-Draft will expire on October 10, 2016.

Copyright Notice

   Copyright (c) 2016 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
   (http://trustee.ietf.org/license-info) in effect on the date of
   publication of this document.  Please review these documents



Wagner & Kuehlewind     Expires October 10, 2016                [Page 1]


Internet-Draft               ConEx Auditing                   April 2016


   carefully, as they describe your rights and restrictions with respect
   to this document.  Code Components extracted from this document must
   include Simplified BSD License text as described in Section 4.e of
   the Trust Legal Provisions and are provided without warranty as
   described in the Simplified BSD License.

Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   2
     1.1.  Meaning of the Re-Echo Signals  . . . . . . . . . . . . .   2
     1.2.  Meaning of Credit Signal  . . . . . . . . . . . . . . . .   3
     1.3.  Definitions . . . . . . . . . . . . . . . . . . . . . . .   3
   2.  Audit Implementation  . . . . . . . . . . . . . . . . . . . .   3
     2.1.  Placing an Audit Element  . . . . . . . . . . . . . . . .   4
     2.2.  Per Flow State  . . . . . . . . . . . . . . . . . . . . .   4
     2.3.  Penalty Criteria  . . . . . . . . . . . . . . . . . . . .   6
     2.4.  Appropriately Penalizing Misbehaving Flows  . . . . . . .   7
     2.5.  Audit start for existing connections  . . . . . . . . . .   7
     2.6.  Handling Loss of ConEx-marked Packets . . . . . . . . . .   8
   3.  Acknowledgements  . . . . . . . . . . . . . . . . . . . . . .   8
   4.  Security Considerations . . . . . . . . . . . . . . . . . . .   8
   5.  IANA Considerations . . . . . . . . . . . . . . . . . . . . .   8
   6.  References  . . . . . . . . . . . . . . . . . . . . . . . . .   8
     6.1.  Normative References  . . . . . . . . . . . . . . . . . .   8
     6.2.  Informative References  . . . . . . . . . . . . . . . . .   9
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .   9

1.  Introduction

   In order to make ConEx information useful, reliable auditing is
   necessary to provide a strong incentive to declare ConEx information
   honestly.  However, there is always a delay between congestion events
   and the respective ConEx signal at the audit.  In
   [draft-ietf-conex-abstract-mech] it is proposed to use credit signals
   sent in advance to cover potential congestion in the next feedback
   delay duration.

   The ConEx signal is based on loss or Explicit Congestion Notification
   (ECN) marks [RFC3168] as a congestion indication.  Following
   [draft-ietf-conex-abstract-mech] (Section 4.4), ConEx signaling has
   to encode ConEx capability, Re-Echo-Loss (L), Re-Echo-ECN (E) and
   credit (C).

1.1.  Meaning of the Re-Echo Signals

   By the Re-Echo-Loss signal a sender exposes to the network that this
   transport has experienced loss very recently.  By the Re-Echo-ECN
   signal a sender exposes to the network that this transport has



Wagner & Kuehlewind     Expires October 10, 2016                [Page 2]


Internet-Draft               ConEx Auditing                   April 2016


   experienced an ECN-CE mark very recently.  For the audit this means,
   that if it detects a loss or an ECN-CE mark for a ConEx-enabled flow,
   for a compliant sender the corresponding Re-Echo-Loss or Re-Echo-ECN
   signals must be observed in the near future.

1.2.  Meaning of Credit Signal

   The Credit signal represents potential for congestion.  A ConEx-
   enabled sender should signal sufficient credit in advance to any
   congestion event.  If a congestion event occurs, a corresponding
   amount of credit is consumed.  If the sender intends to take the same
   risk again, it just must replace this consumed credit as non-consumed
   credit does not expire.

1.3.  Definitions

   Congestion signal
   The occurrence of a packet loss or ECN-CE mark.  We do not consider
   other signs such as increased delay as congestion signals.

   Congestion event
   One or more congestion signals within one RTT.  For today's
   congestion control algorithms all these signals trigger just one
   reaction regardless of their number.

   Connection
   A connection between transport layer endpoints that allows
   bidirectional signalling, e.g. a TCP connection.

   Flow
   The flow of packets of a connection in one direction.  Therefore for
   a flow sender and receiver are well defined.  With regard to ConEx
   auditing, only one flow of any observed connection is audited, see
   Section 2.1.

2.  Audit Implementation

   An audit element shall be a shadow device, i.e. its presence should
   not be detectable for well-behaving senders.  The objective of an
   audit is to verify that senders signal the ConEx information
   correctly and to penalize cheaters.  For this, the audit element has
   to maintain state for any active ConEx-enabled flow.  It may maintain
   appropriate timers to remove flows that have been idle for too long.
   Flows can be audited independently, there are no dependencies.  There
   are two aspects the auditor has to check for each flow:

   o  if the congestion reported using the ConEx mechanism matches the
      congestion actually observed by the receivers and



Wagner & Kuehlewind     Expires October 10, 2016                [Page 3]


Internet-Draft               ConEx Auditing                   April 2016


   o  if sufficient credit marks have been sent to signal the congestion
      risk in advance.

   The audit penalizes a flow if it fails either of these two criteria.

   This document does not mandate a particular design but identifies
   state and functions that any auditor element must provide to fulfill
   the requirements stated in [draft-ietf-conex-abstract-mech].

2.1.  Placing an Audit Element

   An audit element should be placed so that it can observe all
   congestion signals of audited flows.  If both congestion signals, ECN
   and loss, are detected directly, all auditing should take place
   beyond any potential source of congestion, i.e. any potential
   bottleneck, towards the receiver of that flow.  In that case it must
   be placed beyond any potential multi path routing in order to be able
   to identify all packet losses.  For unencrypted TCP and maybe other
   protocols, losses can be easily detected indirectly by monitoring the
   sender's retransmissions, making loss auditing simple and reliable at
   the same time.  Such ConEx-loss audit function must be placed close
   to the sender before any bottleneck where retransmissions might get
   lost.  Therefore it might make sense to have ConEx-loss auditing and
   ConEx-ECN auditing separated.  Nevertheless, this applies for certain
   deployment scenarios only.  Therefore we describe a combined loss and
   ECN ConEx auditor in the following which must be placed close to the
   receiver, beyond any potential bottleneck.

2.2.  Per Flow State

   ConEx auditing must be performed per incoming ConEx-enabled flow, so
   all monitoring, assessment and penalizing is per flow.

   An audit maintains state for each active connection that is updated
   on every packet of that flow.  Such state entry is created when the
   first packet of an unknown flow is observed.  It is deleted when
   either the corresponding connection is closed conforming to its
   transport layer protocol or a timeout expired.  This timeout should
   be chosen to keep false negatives low, i.e. avoiding timing out still
   active flows.  In contrast, false positives, recognizing two flows as
   one, are expected typically being a smaller issue since in most cases
   the sender is the same host and either complies to the protocol or
   not.  We recommend setting this timeout to 60 seconds, a value also
   common e.g. in NAT middle boxes.

   An audit should maintain an RTT_MAX estimation per flow.  This value
   should be as close to the maximum RTT observed by the sender as




Wagner & Kuehlewind     Expires October 10, 2016                [Page 4]


Internet-Draft               ConEx Auditing                   April 2016


   possible.  RTT_MAX must not be chosen smaller than the RTT observed
   by the sender.
   An audit maintains the following variables per flow:

   o  ECN-CE counter (ECN-CE codepoint set)
      When an ECN-CE-marked packet is observed, the counter is increased
      by the number of IP payload bytes.

   o  Loss counter (to be detected by the audit element, see also
      Section 5.5 in [draft-ietf-conex-abstract-mech])
      When a loss is observed, the counter is increased by the number of
      IP payload bytes.

   o  Re-Echo-ECN counter (ConEx signal E)
      When Re-Echo-ECN-marked packet is seen, the counter is increased
      by the number of IP payload bytes.

   o  Re-Echo-Loss counter (ConEx signal L)
      When Re-Echo-Loss-marked packet is seen, the counter is increased
      by the number of IP payload bytes.

   o  Credit state
      Whenever a ConEx-marked packet (Re-Echo-Loss or Re-Echo-ECN) is
      seen and Credit state is greater than zero, the counter is
      decreased by the number of IP payload bytes.  When a Credit-marked
      packet is seen, the counter is increased by the number of IP
      payload bytes.
      Please note that the meaning of the Credit variable differs from
      the other variables: While all other variables are life-time
      counters for the flow and thus grow monotonously, the credit
      buffer just reflects the current signaled credit.  It shrinks and
      grows as congestion is experienced and credit is sent.

   o  RTT_MAX

   o  is_in_penalty_state

   o  p, an EWMA of the congestion rate (loss and/or ECN-CE marks)

   o  x, an EWMA of the rate of Re-Echo-Loss and/or Re-Echo-ECN marks.
      If a packet carries both flags, it must be counted twice.

   o  current drop probability

   If the flow is part of a bidirectional connection, an auditor may use
   information from the return flow in order to define RTT_MAX and to
   detect packet losses.




Wagner & Kuehlewind     Expires October 10, 2016                [Page 5]


Internet-Draft               ConEx Auditing                   April 2016


2.3.  Penalty Criteria

   Generally, a connection is judged on three criteria, one concerning
   exposure of loss, one on exposure of ECN-based congestion signaling
   and one on announcing potential congestion by credit.  A flow is
   considered misbehaving if at least one of the three conditions is
   met.

   A connection is assumed behaving abusive if

   o  the Credit state is zero,

   o  losses observed in the last 2x RTT_MAX period are not exposed by
      Re-Echo-Loss signals, and

   o  ECN-CE signals received in the last 2x RTT_MAX period are not
      exposed by Re-Echo-Loss signals.

   The first criterion should be checked each time a packet of that flow
   towards the destination is observed.  If Credit state is zero,
   is_in_penalty_state is set to true, else set to false.

   The other two criteria shall be checked periodically based on
   timeouts.  The timeout t must be equal or bigger than 2x RTT_MAX.
   There are n timers used and n should be equal or bigger than 2.  To
   do the check, an audit element must store n snapshots of the ECN-CE
   and loss counter.  When the timeout fires, the oldest set of values
   is compared with the current values of Re-echo-Loss and Re-Echo-ECN,
   respectively.  If the saved loss counter is greater than the current
   Re-Echo-Loss counter, or saved ECN-CE counter is greater than the
   current Re-Echo-ECN counter, is_in_penalty_state is set to true, else
   set to false.

   A flow may have not enough data at a time where it needs to send
   ConEx markings and by this fall into misbehaving state
   (is_in_penalty_state is true) during a phase of inactivity.  If the
   sender then restarts sending packets carrying markings for all failed
   criteria, the sender is assumed being well-behaving (in dubio pro
   reo).  Therefore the auditor shall not drop packets which carry all
   required flags, but use the normal penalty on all others.

   For example, if credit is zero and the losses experienced in the
   2xRTT_MAX period are not compensated by sufficient Re-Echo-Loss
   signals, packets carrying both the C and the L flag will not be
   subject of the penalty function.  Nevertheless, packets carrying only
   the C-flag or only the L-flag will.





Wagner & Kuehlewind     Expires October 10, 2016                [Page 6]


Internet-Draft               ConEx Auditing                   April 2016


2.4.  Appropriately Penalizing Misbehaving Flows

   If a flow is detected to misbehave, the audit must start penalizing
   immediately.  The only actually possible penalty is dropping packets
   (with a certain probability).  In order to not incentivize senders to
   simply start new flows when detecting being penalized by an audit
   element, the penalty of a misbehaving flow should be proportional to
   the misbehavior.

   Please note that we require the sender to make sure that any ConEx
   mark will reach the receiver, so it is responsible for timely
   retransmission of any lost ConEx signal.

   The actual drop rate must provide a tangible disadvantage to the
   sender but should not make the connection unusable.  An auditor
   should aim at forwarding not more packets than would have been
   successfully sent with the exposed congestion rate.  Since the
   congestion rate may vary over time, the auditor should use an
   exponentially-weighted moving average (EWMA) for each flow to define
   the congestion rate p.  An auditor should also maintain a EWMA for
   the rate of ConEx-signals (Re-Echo-Loss and Re-Echo-ECN) x.

   TODO: what are appropriate weighting factors alpha in EWMA?

   Assume the packet rate is r and congestion rate is p, but only p-x
   congestion is signaled by the sender using ConEx (c < p).  The audit
   should aim at giving the flow just a rate of r*(x/p).  In other
   words, it should drop (p-x)/p of the traffic, so its drop probability
   should be (p-x)/p.  Therefore the audit just keeps updated x and p,
   and derives the drop probability as (p-x)/p.

2.5.  Audit start for existing connections

   An audit may be started with zero state information on existing
   flows, e.g. due to (re-)started audit or re-routing of flows.  As
   credits will have been sent in advance of congestion events, it is
   possible that no valid credit state is available at the audit when a
   congestion event occurs.  An audit implementation should take this
   into account by ignoring the first criterion for some time.  We
   recommend starting to take credit into account after one minute.

   TODO: is this the right way? this should be enough for the first
   congestion epoch, but disregards credit build up in slow start.  Or
   give some credit on Credit for the start? how much?







Wagner & Kuehlewind     Expires October 10, 2016                [Page 7]


Internet-Draft               ConEx Auditing                   April 2016


2.6.  Handling Loss of ConEx-marked Packets

   ConEx-marked packets will be sent just after the sender noticed a
   congestion signal, so often this sender will just have reduced its
   sending rate.  Thus the loss probability for ConEx-marked packets is
   expected to be lower than for the average flow.  Nevertheless, ConEx-
   marked packets can be lost.  The sender should re-send the ConEx-
   signal.  This induces additional delay for that ConEx-signal but this
   is taken into account by using 2xRTT_MAX as threshold for penalties.
   By that false positives of the auditor misbehavior detection are
   avoided.  Only if two ConEx-marked packets are lost in subsequent
   RTTs, the auditor will penalize a flow of a well-behaving sender.  To
   avoid even these rare cases at least for long-lasting connections,
   the audit may use the fraction of lost packets of that connection to
   allow for the same fraction of loss for each ConEx-mark (E, L and C)
   for a time longer than 2xRTT_MAX.  Nevertheless, the rare event of
   loss of ConEx-marked packets will often cause the audit to penalize
   the flow for one RTT.  We deem this price being acceptable for the
   clean and robust auditor design made possible by making the sender
   responsible for successful delivery of ConEx signals.

3.  Acknowledgements

   We would like to thank Bob Briscoe for his input (based on research
   work of his PhD thesis).

4.  Security Considerations

   Here known / identified attacks will be discussed.  Bob Briscoe's
   dissertation provides good material here. big TODO.

5.  IANA Considerations

   This document has no IANA considerations.

6.  References

6.1.  Normative References

   [draft-ietf-conex-abstract-mech]
              Mathis, M. and B. Briscoe, "Congestion Exposure (ConEx)
              Concepts and Abstract Mechanism", draft-ietf-conex-
              abstract-mech-08 (work in progress), October 2013.

   [draft-ietf-conex-destopt]
              Krishnan, S., Kuehlewind, M., and C. Ucendo, "IPv6
              Destination Option for ConEx", draft-ietf-conex-destopt-05
              (work in progress), March 2013.



Wagner & Kuehlewind     Expires October 10, 2016                [Page 8]


Internet-Draft               ConEx Auditing                   April 2016


   [RFC3168]  Ramakrishnan, K., Floyd, S., and D. Black, "The Addition
              of Explicit Congestion Notification (ECN) to IP",
              RFC 3168, DOI 10.17487/RFC3168, September 2001,
              <http://www.rfc-editor.org/info/rfc3168>.

6.2.  Informative References

   [RFC5681]  Allman, M., Paxson, V., and E. Blanton, "TCP Congestion
              Control", RFC 5681, DOI 10.17487/RFC5681, September 2009,
              <http://www.rfc-editor.org/info/rfc5681>.

Authors' Addresses

   David Wagner
   University of Stuttgart
   Pfaffenwaldring 47
   70569 Stuttgart
   Germany

   Email: david.wagner@ikr.uni-stuttgart.de


   Mirja Kuehlewind
   ETH Zurich
   Gloriastrasse 35
   8092 Zurich
   Switzerland

   Email: mirja.kuehlewind@tik.ee.ethz.ch






















Wagner & Kuehlewind     Expires October 10, 2016                [Page 9]