Subject: [re-ECN] Abstract specification of ConEx

From: Matt Mathis <[email-masked]>
Date: Sun, 28 Mar 2010 20:39:16 -0400

While Bob and I were working on our ICCRG presentation I generated a
slide that described an abstract (coding independent) representation
of ConEx.  This slide did not make it into the final presentation, but
I thought I would describe it here, with one enhancement that came up
during the week.

Congestion indications (ECN marks) propagate from the network to the
transport receiver.  To avoid ambiguity these must be three state
marking:  Not supported, not marked, and congestion detected (ECN).
For shorthand ECN marked is referred to as "RED" or "debit" marks.

The transport ACKs carry this information and loss information (e.g.
TCP SACKS) from the receiver to the sender.  The details are not
specified in the abstract model, but full marking information must be
preserved (The sender has to be able to construct cumulative counts of
ECN marked and not marked.  The "Not supported" indication MUST be all
or none).

The sender is required to adjust its window size or data rate
according to existing congestion control standards.    If it supports
ConEx, the sender needs to be able to send three different "credit"
markings:
BLACK_ECN - in exact agreement with the number of ECN marks seen at
the receiver (but implicitly delayed by one RTT).
BLACK_Loss - In exact agreement with the number of losses signaled.
For reliable protocols should be in exact agreement with
retransmissions.
GREEN - Pre-credits to used to assure that even though the BLACK marks
are delayed by one RTT count(RED)<count(BLACK_ECN)+count(GREEN).

Depending on the deployment scenario and other coding constraints the
sender marking might be three separate ternary values (unsupported,
not marked or marked) or one supported indication plus 3 binary
values.    Note that as a practical matter it might be reasonable to
assume one 5 valued signal, but this representation can not model
situations where transport might carry both loss and ECN information
on the same ACK.

The point of the abstract specification is to permit us to list some
of the algorithms that ConEx might support, such that when it comes
time to choose a particular encoding, it is easy to understand what
features we might forfeit when using it.

For example, if a flow is observed to violate
count(RED)<count(BLACK_ECN)+count(GREEN), then it can be identified as
cheating.   If I have to encode all of the sender marks into 2 bits (4
code points) then would be better not to conflate BLACK_Loss with
either BLACK_ECN or GREEN, because doing so will either weaken or
break the cheating test.   It looks as though it might be ok to use a
single code point for GREEN and BLACK_ECN marks.

My notation is not particularly good.  Perhaps somebody can suggest
something better....

Thanks,
--MM--
-------------------------------------------
Matt Mathis      http://staff.psc.edu/mathis
Work:412.268.3319   Home/Cell:412.654.7529
-------------------------------------------
Evil is defined by mortals who think they know
"The Truth" and use force to apply it to others.

---

From: Bob Briscoe <[email-masked]>
Date: Mon, 29 Mar 2010 08:06:56 +0100

Matt,

At 01:39 29/03/2010, Matt Mathis wrote:
>If it supports

For an unconstrained abstract encoding, I see this differently (as I 
tried to describe in my earlier posting on this subject):

The ECN field already shows whether it supports drop (Not-ECT) or ECN 
(the other three codepoints). So, if an orthoginal re-feedback field 
supports the following four codepoints:
- re-feedback not supported
- re-feedback unmarked
- re-feedback marked
- re-feedback pre-credit

Then, combined with Not-ECT in the ECN field, these can re-echo losses.
Or, combined with the other ECN codepoints, they can be used to re-echo ECN.

>My notation is not particularly good.  Perhaps somebody can suggest

I tried in my first posting of this thread.
Did you see it and think it was not useful? Or did you miss it?

Bob

>--MM--

________________________________________________________________
Bob Briscoe,                                BT Innovate & Design

---

From: Matt Mathis <[email-masked]>
Date: Tue, 30 Mar 2010 23:55:05 -0400

I don't think your encoding works for hybrid encoding for both loss
based and ECN based RE-Feedback.   The problem is that if a flow is
getting both losses and ECN marks (different bottlenecks) you need to
used different techniques to enforce each.   ECN cheating can be
detected by counting the red, black and green marks near to the
receiver, as mentioned before.   Loss cheating requires reconstructing
the TCP state from the sequence numbers, which is hard a high rate and
most robust when you are close to the sender.

Furthermore these are orthogonal signals in the transport ACKs: a
single TCP ACK might carry both SACK blocks indicating losses and ECT
marks.  Choosing four code points rather than three independent bits
obscures a lot of information and the concurrency in other parts of
the system.

In order to make sure that the abstract model isn't coloring our
thinking, we really want to preserve all of this information in the
model even though we think it is clear which credit marks we want to
conflate.    That means the abstract model will not be the same as the
IPv6 encoding....

Thanks,
--MM--

On Mon, Mar 29, 2010 at 3:06 AM, Bob Briscoe <[email-masked]> wrote:
> For an unconstrained abstract encoding, I see this differently (as I tried
> to describe in my earlier posting on this subject):
>
> The ECN field already shows whether it supports drop (Not-ECT) or ECN (the
> other three codepoints). So, if an orthoginal re-feedback field supports the
> following four codepoints: