,----- RL1 = 6 ------>  ,--- RL2=4 -->
a)      0   0   0   0   0   C   0   0   0   0   1
       SP  SP  SP  SP  SP  MK1 SP  SP  SP  SP  MK2

       ,--- RL1=4 -->       (RL2 = 0)
b)      C   C   C   0   0
       SP  SP  SP  MK1 MK2

       ,--------- RL1 = 7 ------>  ,--------- RL2 = 7 ------>
c)      0   0   0   0   0   0   0   0   0   0   0   0   0   0   0
       SP  SP  SP  SP  SP  SP  MK1 SP  SP  SP  SP  SP  SP  SP  MK2

 RL1=1 ,>  ,--- RL2=4 -->
d)      C   0   0   0   0   C
       MK1 SP  SP  SP  SP  MK2

 RL2=1 ,>                  (RL1 = 0)
e)      N   N
       SP  MK2

Figure 8: Examples Encodings of Sequences of ECN Codepoints in the ESQ Field

The examples should be self-explanatory, but the following points might help:

• The term 'mark' does not have to mean an 'ECN mark'. In (a) the 'spaces' are defined as ECT(0) and the first 'mark' is defined as CE. However, in (b) it is more efficient to define CE as the 'space' and ECT(0) as the first 'mark';
• A mark is defined to mean just one codepoint, so two marks in a row have to be encoded as two different marks, even if they are the same codepoint (b). The first and second marks can be defined as different (a) or the same (b or c);
• For a long run of the same codepoint, the first mark can be defined to be the same as a space, and if necessary the second mark can be the same as well (c);
• The first run (if non-zero length) always ends in one mark. So, if its run-length is 1, it contains a mark but no spaces (d);
• Either run-length might be zero (b & e), but MK2 will always be present. If the first run-length is zero, the definition of MK1 is redundant (e). If both run-lengths are zero, the definition of SP would be redundant as well.

The following normative statements govern an implementation of an AccECN Data Receiver when it defers an ACK:

• The Outgoing Protocol Handler MUST NOT encode the last packet to be acknowledged into the ESQ field;
• If the Outgoing Protocol Handler cannot encode the last ECN codepoint to arrive in the ESQ field, it MUST send an ACK immediately;
• The Outgoing Protocol Handler MUST NOT include a codepoint in the sequence of codepoints in an ACK that is from any packet already reported in another ACK;
• If RL1=0, the Outgoing Protocol Handler MUST set MK1 = ECT(0) = 0b10, even though the value of MK1 seems redundant.
• If RL2=0 and RL1=<1, the Outgoing Protocol Handler MUST set SP = ECT(0) = 0b10, even though the value of SP seems redundant.

The last two rules ensure that the value of ESQ as a whole is never all-zeros, which allows the Incoming Protocol Handler to detect interference by middleboxes (see Section 3.6).

The following normative statements govern an implementation of an AccECN Data Sender:

• The Incoming AccECN Protocol Handler MUST increment the congestion codepoint counters (other than the one associated with the ACE field) by counting the codepoints as it decodes the ESQ field;
• If the Incoming AccECN Protocol Handler finds that the value of a congestion counter calculated using ESQ would be more than that calculated using Top-ACE/ACE, it SHOULD use the higher of the two calculations.
• If the Incoming AccECN Protocol Handler finds that the value of a congestion counter calculated using ESQ would be less than that calculated using Top-ACE/ACE, it SHOULD use the higher of the two calculations. An example of an exception to this rule would be where the Incoming Protocol Handler had previously conservatively assumed counter wrap, but then missing ACKs arriving later filled the gap in the sequence feedback.
• While the Incoming AccECN Protocol Handler is calculating the value of a congestion counter using Top-ACE/ACE, if it finds that the value calculated using ESQ in a previous segment is already higher, it SHOULD use the lower value calculated using ACE/Top-ACE. It SHOULD also consider the SupAccECN field in subsequent segments as suspect {ToDo: suggest what concrete action this implies}.

Forward Compatibility:

• if RL1=0:
  • the Incoming Protocol Handler MUST ignore the value in MK1;
  • middleboxes MUST forward the value in MK1 unaltered (whether or not it is 0b10 as it ought to be).

• if RL2=0 and RL1=<1:
  • the Incoming Protocol Handler MUST ignore the value in SP;
  • middleboxes MUST forward the value in SP unaltered (whether or not it is 0b10 as it ought to be).

3.3.5. AccECN Feedback Integrity

The ECN Nonce [RFC3540] is an experimental IETF specification intended to allow a sender to test whether ECN CE markings (or losses) are being suppressed by the receiver (or anywhere else in the feedback loop, such as another network or a middlebox). The ECN nonce has not been deployed as far as can be ascertained. The nonce would now be nearly impossible to deploy retrospectively, because to catch a misbehaving receiver it relies on the receiver volunteering feedback information to incriminate itself. A receiver that has been modified to misbehave can simply claim that it does not support nonce feedback, which will seem unremarkable given so many other hosts do not support it either.

With minor changes AccECN could be optimised for the possibility that the ECT(1) codepoint might be used as a nonce. However, given the nonce is now probably undeployable, the AccECN design has been generalised so that it ought to be able to support other possible uses of the ECT(1) codepoint, such as a lower severity or a more instant congestion signal than CE.

Three alternative mechanisms are available to assure the integrity of ECN and/or loss signals. AccECN is compatible with any of these approaches:

• The Data Sender can test the integrity of the receiver's ECN (or loss) feedback by occasionally setting the IP-ECN field to a value normally only set by the network (and/or deliberately leaving a sequence number gap). Then it can test whether the Data Receiver's feedback faithfully reports what it expects [I-D.moncaster-tcpm-rcv-cheat]. Unlike the ECN Nonce, this approach does not waste the ECT(1) codepoint in the IP header, it does not require standardisation and it does not rely on misbehaving receivers volunteering to reveal feedback information that allows them to be detected.
• Networks generate congestion signals when they are becoming congested, so they are more likely than Data Senders to be concerned about the integrity of the receiver's feedback of these signals. A network can enforce a congestion response to its ECN markings (or packet losses) using congestion exposure (ConEx) audit [I-D.ietf-conex-abstract-mech]. Whether the receiver or a downstream network is suppressing congestion feedback or the sender is unresponsive to the feedback, or both, ConEx audit can neutralise any advantage that any of these three parties would otherwise gain.
  
  ConEx is a change to the Data Sender that is most useful when combined with AccECN. Without AccECN, the ConEx behaviour of a Data Sender would have to be more conservative than would be necessary if it had the accurate feedback of AccECN.
• The TCP authentication option (TCP-AO [RFC5925]) can be used to detect any tampering with AccECN feedback between the Data Receiver and the Data Sender. Although this section of the feedback loop is the least likely to come under malicious attack, it is increasingly likely to be tampered with accidentally by middleboxes intervening at layer 4. The AccECN fields are immutable end-to-end, so whether placed in the Non-Urgent field or a TCP option, they are amenable to default TCP-AO protection (but not if TCP-AO protection of TCP options is turned off, which is non-default but might be necessary for other reasons).

3.4. Accurate ECN Receiver Operation

A TCP receiver MUST only feedback ECN information arriving in a segment that it deems is part of the flow, by using regular TCP techniques based on sequence numbers.

{ToDo: It might be useful to describe receiver end of the feedback process, including special cases, e.g. pure ACKs, retransmissions, window probes, partial ACKs, etc. Does AccECN feed back each ECN codepoint when a data packet is duplicated?}

3.5. Accurate ECN Sender Operation

A TCP sender MUST only accept ECN feedback on ACKs that it deems is part of the flow, by using regular TCP techniques based on sequence numbers.

{ToDo: It might be useful to describe the sender end of the feedback process, including special cases, e.g. pure ACKs, retransmissions, window probes, partial ACKs, etc.}

3.6. Detection of Legacy Middlebox Interference

The definition of the SupAccECN field has been contrived so that the value all-zeros is undefined. Therefore, an Outgoing AccECN Protocol Handler MUST NOT ever set the value of SupAccECN to all-zeros.

Therefore, the Incoming AccECN Protocol Handler MUST check that the value of ESQ is non-zero (on a segment with SYN=0). If the Incoming Protocol Handler detects all-zeros in either of these fields on any segment, it MUST ignore the whole SupAccECN field on that segment, and it SHOULD ignore the SupAccECN field on all subsequent segments in the same half-connection or at least treat each with greater suspicion.

If a Data Sender ignores the incoming SupAccECN field, it MUST revert to the conservative behaviour needed when only the essential part of the AccECN protocol is available, as described in Section 3.2.2. Nonetheless, the Outgoing AccECN Protocol Handler of the same Data Sender MUST continue to set the SupAccECN field as normal (Section 3.3), because any interference might be only in one direction. The AccECN protocol does not include any requirement for a Data Sender that detects interference to notify the other end, because the complexity required to assure message integrity in the face of interference is not warranted.

3.7. Correct Middlebox Operation

A large class of middleboxes split TCP connections, acting as the receiver for one connection and the sender for another, passing data between the two, usually via a buffer. Network interface hardware to offload certain TCP processing represents another large class of middleboxes, even though it is rarely in its own 'box'.

To comply with this specification, each side of such a middlebox MUST comply with the AccECN requirements applicable to a responding host or an originating host during capability negotiation (Section 3.1) and the required AccECN behaviours as a Data Receiver or as a Data Sender throughout this specification.

Another class of middleboxes attempts to 'normalise' the TCP wire protocol by checking that all values in header fields comply with a rather narrow interpretation of the TCP specifications. To comply with this specification, such middleboxes MUST be updated to recognise and forward values in fields that comply with the newly defined semantics of AccECN. This includes the explicitly stated requirements to forward Reserved (Rsvd) and Currently Unused (CU) values unaltered. An 'ideal' TCP normaliser would not have to change to accommodate AccECN, because AccECN does not directly contravene any existing TCP specifications, even though it uses existing TCP fields in unorthodox ways.

4. Interaction with Other TCP Variants

4.1. Compatibility with SYN Cookies

A server can use SYN Cookies (see Appendix A of [RFC4987]) to protect itself from SYN flooding attacks. It places minimal commonly used connection state in the SYN/ACK, and deliberately does not hold any additional state while waiting for the subsequent ACK. Therefore it cannot record the fact that it entered AccECN mode for both half-connections. Indeed, it cannot even remember whether it negotiated the use of classic ECN [RFC3168].

If the server (host B) receives the final ACK of the 3-way handshake with a SupAccECN TCP option, it can infer that the originating host (A) supports AccECN. If host B supports AccECN itself, it can further infer that it would have entered AccECN mode before sending the SYN/ACK.

If, on the other hand, the originating host (A) sends the final ACK of the 3-way handshake with the SupAccECN field in the Non-Urgent field, responding host B can still infer that host A originally negotiated AccECN, by checking the fourteen least significant bits of the Non-Urgent field and the ACE field, as follows:

• Host B knows that host A would not defer the final ACK of the 3-way handshake, because TCP never delays this.
• Therefore, if host B sends the SYN/ACK with its IP-ECN field set to ECT(0) [RFC5562], then checks the fourteen least significant bits of the Non-Urgent field of the final ACK of the 3-way handshake, it can make the following inferences:
  1. lsb(Non-Urgent) == 000010100000 && ACE == 000 implies host A is AccECN and the SYN/ACK arrived unchanged as ECT(0);
  2. lsb(Non-Urgent) == 000010100000 && ACE == 001 implies host A is AccECN and the SYN-ACK was CE-marked;
  3. lsb(Non-Urgent) == 000010100001 && ACE == 111 implies host A is AccECN and the IP-ECN field of the SYN/ACK was zeroed;
  4. lsb(Non-Urgent) == 000000000000 or any value other than those above implies host A is Not AccECN or a middlebox is interfering with the Non-Urgent field.
• If, on the other hand, host B sends the SYN/ACK with its IP-ECN field set to Not-ECT, then checks the fourteen least significant bits of the Non-Urgent field of the final ACK of the 3-way handshake, it can make the following inferences:
  1. lsb(Non-Urgent) == 000010100001 && ACE == 111 implies host A is AccECN;
  2. lsb(Non-Urgent) == 000000000000 or any value other than that above implies host A is Not AccECN or a middlebox is interfering with the Non-Urgent field.

4.2. Compatibility with Other Options and Experiments

AccECN is compatible (at least on paper) with the most commonly used TCP options: MSS, time-stamp, window scaling, SACK and TCP-AO. It is also compatible with the recent promising experimental TCP options TCP Fast Open (TFO [I-D.ietf-tcpm-fastopen]) and Multipath TCP (MPTCP [RFC6824]). AccECN is particularly friendly to all these protocols, because space for TCP options is particularly scarce on the SYN, where AccECN consumes zero additional header space.

5. Protocol Properties

This section is informative not normative. It describes how well the protocol satisfies the agreed requirements for a more accurate ECN feedback protocol [I-D.ietf-tcpm-accecn-reqs].

Accuracy:

From each ACK, the Data Sender can infer the number of new Not-ECT, ECT(0), ECT(1) and CE markings since the previous ACK.

Accuracy:

The Data Receiver can feed back to the Data Sender a list of the order of the IP-ECN markings covered by each delayed ACK.

Overhead:

The AccECN scheme is divided into two parts. The essential part reuses the 3 flags already assigned to ECN in the IP header. The supplementary part requires fifteen bits.

Overhead:

Two alternative locations for the supplementary protocol field are proposed:

1. In the 16-bit Urgent Pointer when URG=0. This specification reserves 15 bits of this space, but while the specification is only experimental it refrains from using this space in the main TCP header. If AccECN progresses to the standards track and uses these 15b, it will require zero additional overhead, because it will overload fields that already takes up space in every TCP header
2. In a TCP option. This takes up 4B; the fifteen bits have to be rounded up to 2B, plus 2B for the TCP option Kind and Length.

Timeliness:

In the absence of lost ACKs, no feedback is deferred to a future ACK, which is intended to enable latency-sensitive uses of ECN feedback.

Timeliness:

{ToDo: Add improved timeliness if the Delayed ACK Control (DAC) feature is included.}

Resilience:

Each ACK includes a counter of one of the ECN congestion signals. If ACKs are lost, the counter on the first ACK following the losses allows the Data Sender to immediately recover the number of one of the ECN markings that it missed.

Resilience:

Subsequent ACKs will allow it to recover the number of other ECN markings that it missed.

Resilience against Bias:

Undetected ACK loss is as likely to decrease as increase congestion signals detected by the Data Sender.

Resilience against Bias:

However, if the supplementary part is unavailable, the required conservative decoding of feedback during ACK loss is more likely to increase perceived congestion signals, which would otherwise be more likely to be under-reported.

Timeliness vs Overhead:

For efficiency, each delayed ACK only includes one of the counters at a time, therefore recovery of the count of the other signals might not be immediate if an ACK is lost that covers more than one signal. The receiver cannot predict which ACKs might get lost, if any. Therefore it repeats the count of each signal roughly in proportion to how often each signal changes.

Ordering:

The order of arriving ECN codepoints is communicated in a 10-bit field in the supplementary part;

Resilience vs. Ordering:

Following an ACK loss, only a count of the lost ECN signals is recovered, not their order of arrival over the sequence covered by the loss.

Ordering vs. Overhead:

The encoding is tailored for sequences of ECN codepoints expected to be typical. It can encode sequences of up to 15 segments but, if the pattern of arrivals becomes too complex, the protocol forces the Data Receiver to emit an ACK. The protocol can always encode any sequence of 3 segments in one delayed ACK;

Ordering, Timeliness and Resilience:

If one delayed ACK covers changes to more than one congestion counter the supplementary sequence information provides more timely congestion feedback than waiting for the other congestion counters on future ACKs, and it provides resilience against the possibility of those future ACKs going missing;

Complexity:

{ToDo: Once implemented, quantify the code complexity}

Integrity:

AccECN is compatible with complementary protocols that assure the integrity of ECN feedback.

Backward Compatibility:

If only one endpoint supports the AccECN scheme, it will fall-back to the most advanced ECN feedback scheme supported by the other end.

Backward Compatibility:

Each endpoint can detect normalisation of the Supplementary AccECN field by middleboxes at any time during a connection. It could then fall-back to the essential part using only the fewer but safer bits in the TCP header.

Forward Compatibility:

The behaviour of endpoints and middleboxes is carefully defined for all reserved or currently unused codepoints in the scheme, to ensure that any blocking of anomalous values is always at least under reversible policy control.

6. IANA Considerations

6.1. SupAccECN TCP Option Allocation

This specification requires IANA to allocate one value from the TCP option Kind name-space, against the name "Supplementary Accurate ECN" (SupAccECN).

Early implementation before the IANA allocation MUST follow [RFC6994] and use experimental option 254 and magic number 0xACCE (16 bits) {ToDo register this with IANA}, then migrate to the new option after the allocation.

6.2. Non-Urgent Field Registry

This specification requests that IANA sets up a new TCP parameters registry in accordance with [RFC5226]. This registry enables future standards track RFCs to assign values to sub-fields of the TCP Non-Urgent field defined in Section 3.3.1.2.

Name of registry:

Non-Urgent field.

Information required for assignments:

• Width and position of sub-field or sub-fields,
• Assignment of values to sub-field(s),
• Confirmation of compliance with additional conditions 1 & 2 below.

Review Process:

Standards Action - Values to be assigned for Standards Track RFCs approved by the IESG. At the IESG's discretion, values MAY be assigned for Standards Track RFCs still in the process of approval, in order to resolve the catch-22 where the assignment needs deployment testing but deployment testing needs the assignment.

Size, format and syntax of registry entries:

Binary values of sub-fields.

Initial assignments and reservations:

This specification reserves the 15 least significant bits of the Non-Urgent field for use by a potential future standards action that might define the AccECN scheme for the standards track.

Additional conditions for assignment:

1. Assignments within the Non-Urgent field MUST be used by a protocol that is robust to the field being unavailable occasionally. This is because the Non-Urgent field is unusable and undefined on segments with URG = 1 in the TCP header [RFC0793]. The Non-Urgent field overloads the meaning of the 16-bit Urgent Pointer only when URG = 0.
2. The value zero, i.e. all 16 bits of the Non-Urgent field cleared to zero, SHOULD be undefined, because it is known that certain 'normalising' middleboxes overzealously zero the urgent pointer when URG = 0. An undefined zero value can be achieved by requiring that the value all-zeros is undefined for at least one sub-field of the Non-Urgent field. Then even if the value all-zeros is defined and used in other sub-fields, the value all-zeros for the whole field will be undefined.

7. Security Considerations

If ever the supplementary part of AccECN is unusable (due for example to middlebox interference) the essential part of AccECN's congestion feedback offers only limited resilience to long runs of ACK loss (see Section 3.2.2). These problems are unlikely to be due to malicious intervention (because if an attacker could discard a long run of ACKs it could wreak other arbitrary havoc). However, it would be of concern if AccECN's resilience could be indirectly compromised during a flooding attack. AccECN is still considered safe though, because an AccECN Data Sender can detect when the supplementary part is unusable, and it is then required to switch to more conservative assumptions about wrap of congestion indication counters (see Section 3.2.2 and Appendix A.1).

AccECN does not signal the ordering of ECN codepoints covered by a delayed ACK reliably, i.e. if one delayed ACK is lost, the ECN sequence information in that ACK is not retransmitted. The design of AccECN assumes gaps in this information will not be critical, and that this information is unlikely to be security-sensitive. However, this point is mentioned for completeness.

The SYN cookie method for mitigating SYN flooding attacks is not generally compatible with enhancements to the TCP 3-way handshake. Nonetheless, Section 4.1 describes how a server can negotiate AccECN and use SYN cookies.

AccECN is compatible with all the known schemes that ensure the integrity of ECN feedback (see Section 3.3.5 for details). Given the experimental ECN nonce is now probably undeployable, AccECN has been generalised for other possible uses of the ECT(1) codepoint to avoid any risk of obsolescence.

8. Acknowledgements

We want to thank Michael Welzl for his input and discussion. The idea of using the three ECN-related TCP flags as one field for more accurate TCP-ECN feedback was first introduced in the re-ECN protocol that was the ancestor of ConEx.

Bob Briscoe was part-funded by the European Community under its Seventh Framework Programme through the Reducing Internet Transport Latency (RITE) project (ICT-317700) and through the Trilogy 2 project (ICT-317756). The views expressed here are solely those of the authors.

9. Comments Solicited

Comments and questions are encouraged and very welcome. They can be addressed to the IETF TCP maintenance and minor modifications working group mailing list <tcpm@ietf.org>, and/or to the authors.

10. References

10.1. Normative References

10.2. Informative References

Appendix A. Example Algorithms

This appendix is informative, not normative. It gives examples in pseudocode for the various algorithms used by AccECN.

A.1. Example Algorithm for Safety Against Long Sequences of ACK Loss

This appendix gives an example algorithm that a Data Sender can use to heuristically detect a long enough unbroken string of ACK losses that could have concealed wrap of the congestion counter in the ACE field of the next ACK to arrive. The Data Sender is unlikely to need to run an algorithm like this unless it detects that supplementary AccECN feedback is not available (see Section 3.2.2 and Section 3.6).

It is assumed that the focus is solely safety not complete protocol precision. Therefore, this example solely detects possible wrap of the congestion indication (CI) counter, not E1 or NI. This is on the assumption that, even if ECT(1) is redefined to indicate congestion in some way, then ECN CE markings will always indicate more severe congestion. It is also assumed that numerous Not-ECT markings imply middlebox tampering, which only needs to be detected, not quantified perfectly.

If the supplementary Top-ACE field cannot be used, there is only room for 4 values of the congestion indication (CI) counter in the ACE field. The CI counter in an arriving ACK could have wrapped and become ambiguous to the Data Sender if a row of ACKs goes missing that covers a stream of data long enough to contain 4 or more CE marks. We use the word missing rather than lost, because some or all the missing ACKs might arrive eventually, but out of order. Even if some of the lost ACKs are piggy-backed on data (i.e. not pure ACKs) retransmissions will not repair the lost AccECN information, because AccECN requires retransmissions to carry the latest AccECN counters, not the original ones (Section 3.2.3).

If the CE marking probability were p on the forward data path, ambiguity would arise if 100% of ACKs went missing from the reverse path in a row was at least 4/p long. For example, if p was 5% on the forward path, ambiguity would ensue if simultaneously on the reverse path a sequence of ACKs covering 4/0.05 = 80 packets all went missing. With a delayed ACK ratio of 2 that translates to missing 40 ACKs in a row. Obviously, missing ACKs would be far less likely if pure ACKs were allowed to be ECN-capable. However, because RFC 3168 currently precludes this, we will assume that pure ACKs are not ECN-capable.

To protect against such an unlikely event, Section 3.2.2 requires the Incoming Protocol Handler to assume that the CI field did wrap if it could have wrapped under prevailing conditions. It could be extremely conservative and assume that ECN marking suddenly jumped to 100% on the forward path just when there were no ACKs on the reverse path to detect it.

    D' = L - ((L-D) % 4),

Specifically, if the Incoming Protocol Handler receives an ACK with an acknowledgement number that acknowledges L full-sized segments since the previous ACK, it could conservatively assume that the CI field incremented by

For example, imagine an ACK acknowledges 5 more full-size segments than any previous ACK, and that it apparently increases CI by 2. The above formula works out that a safe increment of CI would still be 2 (because 5 - ((5-2) % 4) = 2). However, if CI apparently increases by 2 but acknowledges 11 more full-sized segments, then CI should be assumed to have increased by 10 (because 11 - ((11-2) % 4) = 10).

Implementers could build in more heuristics to estimate prevailing segment sizes and prevailing ECN marking. For instance, L in the above formula could be replaced with L' = L*p*M/s, where M is the MSS, s is the prevailing segment size and p is the prevailing ECN marking probability. However, ultimately, if TCP's ECN feedback becomes inaccurate it still has loss detection to fall back on. Therefore, it would seem safe to implement a simple algorithm like that given initially, rather than a perfect one.

If missing acknowledgement numbers arrive later (due to reordering), Section 3.2.2 says "the Data Sender MAY attempt to neutralise the effect of any action it took based on a conservative assumption that it later found to be incorrect". To do this, the Data Sender would have to store the values of all the relevant variables whenever it made assumptions, so that it could re-evaluate them later. Given this could become complex and it is not required, we do not attempt to provide an example of how to do this.

A.2. Example Counter Selection Algorithms

When the Data Receiver sends an ACK, if the last IP-ECN field that arrived was ECT(0), Section 3.2.3 says, "...the Data Receiver can signal either the CI or the E1 counter. The choice of which to signal SHOULD be based on the principle that the more one counter has changed recently the more it SHOULD be signalled." A couple of alternative algorithms are suggested below that would satisfy this requirement.

A.2.1. Counter Selection Algorithm Alt#1

Counter selection algorithm Alt#1 repeats whichever counter has been repeated proportionately less often, relative to how often it has changed, with preference for CI if they tie. Or in pseudocode:

if ( (e1 / r_e1) > (ci / r_ci) )
    send_ack(e1)
else
    send_ack(ci)

where r_e1 and r_ci are counts of how often E1 and CI were already repeated when ECT(0) was signalled. The algorithm below implements this comparison between two divisions using only integer addition. It is a little terse, so it is explained afterwards.

ci   = 0    // CE counter
w_ci = 0    // internal 'weight' variable for CI
r_ci = 0    // internal count of how often CI has been repeated
e1   = 0    // ECT(1) counter
w_e1 = 0    // internal 'weight' variable for E1
r_e1 = 0    // internal count of how often E1 has been repeated
ni   = 0    // Not-ECT counter

dack_to_be_sent()    // shorthand for test if a delayed ACK is needed

switch (read(pkt.ip.ecn)) {
    case CE :
        ci++
        w_ci += r_e1
        if (dack_to_be_sent()) send_ack(ci)
    case ECT1 :
        e1++
        w_e1 += r_ci
        if (dack_to_be_sent()) send_ack(e1)
    case Not-ECT :
        ni++
        if (dack_to_be_sent()) send_ack(ni)
    case ECT0 :
        if (dack_to_be_sent()) {
            /* Choice between E1 and CI */
            if (w_e1 > w_ci) {      // Preference to CI if they tie
                send_ack(e1)
                r_e1++
                w_ci += ci
            } else {
                send_ack(ci)
                r_ci++
                w_e1 += e1
            }
        }
}

{ToDo: Handle wrap of the weights (see my notebook?).}

Explanation: The algorithm ensures that the weights always equal the following products:

    w_ci = ci * r_e1,
    w_e1 = e1 * r_ci.

It does this by incremental addition rather than multiplication:

• every time r_e1 increments by 1, w_ci is incremented by 1 * ci;
• every time ci increments by 1, w_ci is incremented by 1 * r_e1;

and the same for w_e1 and the pair of variables it consists of.

This ensures that the condition

    w_e1 > w_ci

used in the algorithm is equivalent to:

    e1 * r_ci > ci * r_e1,

or rearranging:

    (e1 / r_e1) > (ci / r_ci),

which is the required proportionality condition.

A.2.2. Counter Selection Algorithm Alt#2

Counter selection algorithm Alt#2 implements the policy "Send each recently changed codepoint twice, unless the other one has also changed, and alternate sending CI, E1 if no counter changes."

{ToDo: Alt#2 has the disadvantage that it can repeat E1 a lot, even if E1 has never been signalled, which unnecessarily reduces the resilience of CI.

ci   = 0        // CE counter
q_ci = 0        // queue of CI's to repeat
nxt_ci = TRUE   // Signal E1 next if FALSE
e1   = 0        // ECT(1) counter
q_e1 = 0        // queue of E1's to repeat
ni   = 0        // Not-ECT counter

dack_to_be_sent()    // shorthand for test if a delayed ACK is needed

switch (read(pkt.ip.ecn)) {
    case CE :
        ci++
        q_ci = 2
        if (dack_to_be_sent()) send_ack(ci)
    case ECT1 :
        e1++
        q_e1 = 2
        if (dack_to_be_sent()) send_ack(e1)
    case Not-ECT :
        ni++
        if (dack_to_be_sent()) send_ack(ni)
    case ECT0 :
        if (dack_to_be_sent()) {
            /* Choice between E1 and CI */
            if (q_ci || q_e1) {     // If either queue is non-zero
                if (q_e1 > q_ci) {  // Preference to CI if they tie
                    send_ack(e1)
                    q_e1 = max(0, q_e1 - 1)
                } else {
                    send_ack(ci)
                    q_ci = max(0, q_ci - 1)
                }
            } else {            // Both queues are zero
                if (nxt_ci)
                    send_ack(ci)
                else
                    send_ack(e1)
                nxt_ci = !nxt_ci    // Toggle the next signal
            }
        }
}

A.3. Example Encodings and Decodings of Top-ACE and ACE

This appendix gives formulae for encoding and decoding the counters CI, E1 or NI with higher resilience to ACK loss by supplementing the ACE field with the Top-ACE field, as required in Section 3.3.3.

A.3.1. Encoding Top-ACE and ACE by the Data Receiver

The values associated with codepoints in ACE for CI and E1 are respectively base 4 and base 3 numbers (see Table 3). Although there is only space for one value of NI, mathematically, NI can still be treated as a base 1 counter. Then the following general formulae allow a Data Receiver to encode any of the counters CI, E1 or NI, by calling them all cntr, and defining ACE_base as their respective number base:

     Top-ACE = Int(cntr / ACE_base) % 16,
    ACE_cntr = cntr % ACE_base.

Then the Data Receiver looks up the codepoint to put in the ACE field by looking up ACE_cntr in Table 3 in the column of the relevant counter (CI, E1 or NI). Int() means round down to an integer and '%' is the modulo operator.

To implement this without a costly division operation, two counters can be maintained while processing the header information for the ACK. The first counter can be mapped into the ACE field via Table 3. A wrap every 4 increments of the counter could be implemented as a single conditional check, and when it wraps, a secondary, high-order counter could be incremented. This secondary counter could then be mapped directly into the Top ACE field. For instance, the two counters for CE markings would be implemented as follows:

if (read(pkt.ip.ecn) == CE) {
    if (ACE_cntr.ci == 4) {
        ACE_cntr.ci = 0
        if (Top-ACE.ci == 16) {
            Top-ACE.ci = 0
        } else
            Top-ACE.ci++
    } else
       ACE_cntr.ci++
}

The three examples below explain how the algorithm determines which codepoints to place in Top-ACE and ACE, for each counter in turn. For brevity, they use the first mathematical formula above, rather than the second conditional logic variant.

Example #1: if the Data Receiver has determined that it will signal its CI counter next and its local value is 73, it encodes this as:

    Top-ACE = INT(73 / 4) % 16
            = 2
            = 0b0010
    ACE_cntr = 73 % 4
             = 1

Looking up the codepoint for CI = 1 in Table 3 gives:

    ACE = 0b001.

Example #2: if the Data Receiver has determined that it will signal its E1 counter next and its local value is 75, it encodes this as:

    Top-ACE = INT(75 / 3) % 16
            = 9
            = 0b1001
    ACE_cntr = 75 % 3
             = 0

Looking up the codepoint for E1 = 0 in Table 3 gives:

    ACE = 0b100.

Example #3: if the Data Receiver has determined that it will signal its NI counter next and its local value is 43, it encodes this as:

    Top-ACE = INT(43 / 1) % 16
            = 11
            = 0b1011
    ACE_cntr = 43 % 1
             = 0               // Anything modulo 1 is 0

Looking up the codepoint for NI = 0 in Table 3 gives:

    ACE = 0b111.

A.3.2. Decoding Top-ACE and ACE by the Data Sender

An AccECN Data Sender decodes the incoming combination of Top-ACE and ACE by looking up the ACE codepoint in Table 3 to get ACE_cntr and ACE_base, then:

    cntr = Top-ACE * ACE_base + ACE_cntr.

For example, if ACE = 0b101 and Top-ACE = 0b0111 = 7, the Data Sender looks up ACE = 0b101 in Table 3 to see that this is the E1 counter and that ACE_cntr = 1 base 3. Therefore,

    E1 = cntr = 7 * 3 + 1
              = 22

The Data Sender is likely to be primarily interested in the increment in this counter relative to the previous ACK. In the case of E1, it will have to use modulo 48 arithmetic for the difference, because the encoding wraps at 48 (see Table 4). Specifically, if the Data Sender's local counter is snd_e1, then the difference,

    delta_e1 = (E1 + 48 - snd_e1 % 48) % 48

{ToDo: Provide algorithms that decode correctly with ACK reordering}

A.4. Example ECN Sequence (ESQ) Encoding Algorithms

This appendix gives an example algorithm for the Data Receiver to encode the arriving sequence of IP-ECN codepoints in the ECN Sequence (ESQ) field of a delayed ACK, as required in Section 3.3.4.

/* Algorithm to encode the arrival sequence of IP-ECN codepoints
 */
DEFAULT = ECT0      // Any ECN codepoint except Not-ECT
DACK_T_MAX = 500    // Max time to delay an ACK [ms]
RL_MAX = 7          // Max run-length that can fit in 3-bit field
DACK_SEG_MAX = 2    // Max full-sized delayed ACK segments:
MSS = 1500          // Example max segment size [B]
DACK_B_MAX = DACK_SEG_MAX * MSS     // Max deferred bytes

sp = mk1 = DEFAULT  // 2-bit ECN codepoints: space and mark
mk2                 // second mark (fed back in ACE, not ESQ)
rl1 = rl2 = 0       // 3-bit run-lengths
dack_b = 0          // deferred bytes

/* Strategy: in readiness for a packet arrival, hold the variables
 *  necessary to build the ECN sequence field (ESQ) of the next ACK.
 * If a packet arrives, and it can be added to the held sequence,
 *  do so and return.
 * If it can't be added to the held sequence, send the ACK
 *  with the most recent packet as the second mark.
 * If the delayed ack timer expires, unwind the last packet in the 
 * held sequence to use as the second mark, and send the ACK
 */

foreach pkt {
    tmp = read(pkt.ip.ecn)      // Store incoming ECN field
    dack_b += read(pkt.ip.size) // Add to deferred bytes

    if (dack_b >= DACK_B_MAX) { // Test deferred bytes threshold
        mk2 = tmp               // Assign incoming ECN to mk2
        send_ack(rl1,rl2,sp,mk1,mk2)     // Encode ESQ and send ACK
    } elif ((rl1 + rl2) =< 0) { // Is the held sequence empty?
        sp = tmp                // Initialise with a space in run2
        rl2++
        init_timer(dack_expire, DACK_T_MAX) // Arm delayed ACK timer
    } elif (tmp == sp) {        // Is the incoming ECN another space?
        if (rl2 < RL_MAX) {     // Is there room in run2?
            rl2++               // Extend run2
        } elif (rl1 =< 0) {     // Otherwise, is run1 empty?
            mk1 = sp            // Shift run2 to run1, making mk1=sp
            rl1 = rl2
            rl2 = 1
        }
    /* If got to here, incoming ECN is assigned as a mark */
    } elif (rl1 =< 0) {     // If there's room in run1, switch to it
        mk1 = tmp
        rl1 = rl2
        rl2 = 0
    } elif ( (tmp == mk1)   // Is incoming ECN a mark already seen
          && (rl1 = 2)      //  with only one space before it?
          && (rl2 = 0) ) {
        mk1 = sp            // If so, swap marks with spaces
        sp = tmp
        rl1 = 1
        rl2 = 2
    } else {                // Cannot extend sequence
        mk2 = tmp           // Assign the incoming ECN to mk2
        send_ack(rl1,rl2,sp,mk1,mk2)    // Encode ESQ and send ACK
    }
}

/* dack_expire()
 * Routine called when the delayed ACK timer expires.
 * There is no incoming packet to fill mk2, 
 *  so the last value from the held sequence has to be used instead
 *  (there will always be a held sequence because the timer is only
 *  armed once the sequence is non-empty).
 */
dack_expire() {
    if (rl2 > 0) {  // run2 contains a value
        rl2--
        mk2 = sp    // copy it into mk2
    } else {        // run2 is empty, therefore run1 is not
        mk2 = mk1   // copy mk1 into mk2
        rl2 = rl1-- // shift run1 into run2 without mk1
        rl1 = 0
    }               // Last value extraction is complete
    send_ack(rl1,rl2,sp,mk1,mk2)    // Encode ESQ and send ACK
}

/* send_ack()
 * Algorithm to encode the arrival sequence of IP-ECN codepoints
 *  into the ECN sequence (ESQ) field of a TCP ACK, then send it.
 */
send_ack(rl1,rl2,sp,mk1,mk2) {
    del_timer(dack)         // Remove any pending delayed ACK timer
    /* Marshall the ECN Sequence field (esq) */
    pkt.tcp.esq = lsb(2,sp) & lsb(2,mk1) & lsb(3,rl1) & lsb(3,rl2)
    /* lsb(n,x): pseudocode for the lowest n significant bits of x */
    /* x & y   : pseudocode for concatenate x and y */
    /*
     * Insert code to send ACK here, with mk2 in pkt.tcp.ace
     */
    /* Reset all variables ready for next packet arrival */
    sp = mk1 = DEFAULT
    rl1 = rl2 = 0
}

Appendix B. Alternative Design Choices (To Be Removed Before Publication)

This appendix is informative, not normative. It records alternative designs that the authors chose not to include in the normative specification, but which the IETF might wish to consider for inclusion.

B.1. Supplementary AccECN Field on the SYN/ACK

{ToDo: The tcpm working group is recommended to consider including this in an AccECN RFC from the start. The AccECN protocol defined in the body of this specification currently gives no ECN feedback on the SYN/ACK on the assumption that the SYN is not ECN-capable. If it is required for the protocol to be future-proofed against the possibility that SYNs might one-day be ECN-capable, the following definition of the SupAccECN field for the SYN/ACK would need to be added to Section 3.3.1 and Section 3.3.2. The text below is written as if it is normative, but it is only informative while it is demoted to this appendix.}

B.1.1. Placement of the Supplementary AccECN Field in a SYN/ACK

To include the SupAccECN field on a SYN/ACK, the Data Receiver MUST use the SupAccECN TCP Option with TCP option Kind 0x<KK> (TBA) and set the Length field to 3 [octets], as illustrated in Figure 9. .

 0                   1                   2
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  Kind = 0xKK  |  Length = 3   |0 0 0 0|  Sup- |
|               |               |       | AccECN|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

      0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
    +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
    | X   X   X   X   X   X   X   X   X   X   X   X |   SupAccECN   |
    +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

             0   1   2   3
           +---+---+---+---+
           | D-ECN | E-ECN |
           +---+---+---+---+