TCP Session Example #1

	Data	TCP A(Re-ECT)	IP A	IP B	TCP B(Re-ECT)	Data
	Byte	SEQ  ACK CTL	EECN	EECN	SEQ  ACK CTL	Byte
--	----	-------------	-----	-----	-------------	----
1		0100      SYN    CWR,ECE,NS	FNE	-->	R.ECC=0
2		R.ECC=0	<--	FNE	0300 0101   SYN,ACK,CWR
3		0101 0301 ACK	RECT	-->	R.ECC=0
4	1000	0101 0301 ACK	FNE	-->	R.ECC=0
5		R.ECC=0	<--	FNE	0301 1102 ACK	1460
6		R.ECC=0	<--	RECT	1762 1102 ACK	1460
7		R.ECC=0	<--	FNE	3222 1102 ACK	1460
8		1102 1762 ACK	RECT	-->	R.ECC=0
9		R.ECC=0	<--	RECT	4682 1102 ACK	1460
10		R.ECC=0	<--	RECT	6142 1102 ACK	1460
11		1102 3222 ACK	RECT	-->	R.ECC=0
12		R.ECC=0	<--	RECT	7602 1102 ACK	1460
13		R.ECC=1	<*-	RECT	9062 1102 ACK	1460
		...

Table 6 shows an example TCP session, where the server B sets FNE on its first and third data packets (lines 5 & 7) as well as on the initial SYN ACK as previously described. The left hand half of the table shows the relevant settings of headers sent by client A in three layers: the TCP payload size; TCP settings; then IP settings. The right hand half gives equivalent columns for server B. The only TCP settings shown are the sequence number (SEQ), acknowledgement number (ACK) and the relevant control (CTL) flags that the relevant sending host sets in the TCP header. The IP columns show the setting of the extended ECN (EECN) field.

Also shown on the receiving side of the table is the value of the receiver's echo congestion counter (R.ECC) after processing the incoming EECN header. Note that, once a host sets a half-connection into RECN mode, it MUST initialise its local value of ECC to zero.

The intuition that Appendix D gives for why a sender should set FNE on the first and third data packets is as follows. At line 13, a packet sent by B is shown with an '*', which means it has been congestion marked by an intermediate queue from RECT to CE(-1). On receiving this CE marked packet, client A increments its ECC counter to 1 as shown. This was the 7th data packet B sent, but before feedback about this event returns to B, it might well have sent many more packets. Indeed, during exponential slow start, about as many packets will be in flight (unacknowledged) as have been acknowledged. So, when the feedback from the congestion event on B's 7th segment returns, B will have sent about 7 further packets that will still be in flight. At that stage, B's best estimate of the network's packet marking fraction will be 1/7. So, as B will have sent about 14 packets, it should have already marked 2 of them as FNE in order to have marked 1/7; hence the need to have set the first and third data packets to FNE.

Client A's behaviour in Table 6 also shows FNE being set on the first SYN and the first data packet (lines 1 & 4), but in this case it sends no more data packets, so of course, it cannot, and does not need to, set FNE again. Note that in the A-B direction there is no need to set FNE on the third part of the three-way hand-shake (line 3---the ACK).

Note that in this section we have used the word SHOULD rather than MUST when specifying how to set FNE on data segments before positive congestion feedback arrives (but note that the word MUST was used for FNE on the SYN and SYN ACK). FNE is only RECOMMENDED for the first and third data segments to entertain the possibility that the TCP transport has the benefit of other knowledge of the path, which it re-uses from one flow for the benefit of a newly starting flow. For instance, one flow can re-use knowledge of other flows between the same hosts if using a Congestion Manager [RFC3124] or when a proxy host aggregates congestion information for large numbers of flows.

{ToDo: There is probably scope for re-writing the above in a different way so that it says MUST unless some other knowledge of the path is available. See earlier note pointing out FNE on 1st & 3rd is too few.}

After an idle period of more than 1 second, a re-ECN sender transport MUST set the EECN field of the packet that resumes the connection to FNE. Note that this next packet may be sent a very long time later, a packet does NOT have to be sent after 1 second of idling. In order that the design of network policers can be deterministic, this specification deliberately puts an absolute lower limit on how long a connection can be idle before the packet that resumes the connection must be set to FNE, rather than relating it to the connection round trip time. We use the lower bound of the retransmission timeout (RTO) [RFC6298], which is commonly used as the idle period before TCP must reduce to the restart window [RFC5681]. Note our specification of re-ECN's idle period is NOT intended to change the idle period for TCP's restart, nor indeed for any other purposes.

{ToDo: Describe how the sender falls back to RFC3168 modes if packets don't appear to be getting through (to work round firewalls discarding packets they consider unusual).}

{ToDo: Possible future capabilities for changing Slow Start}

6.1.7. Pure ACKS, Retransmissions, Window Probes and Partial ACKs

A re-ECN sender MUST clear the RE flag to 0 and set the ECN field to Not-ECT in pure ACKs, retransmissions and window probes, as specified in  [RFC3168]. Our eventual goal is for all packets to be sent with re-ECN enabled, and we believe the semantics of the ECI field go a long way towards being able to achieve this. However, we have not completed a full security analysis for these cases, therefore, currently we merely re-state current practice.

We must also reconcile the facts that congestion marking is applied to packets but acknowledgements cover octet ranges and acknowledged octet boundaries need not match the transmitted boundaries. The general principle we work to is to remain compatible with TCP's congestion control which is driven by congestion events at packet granularity while at the same time aiming to blank the RE flag on at least as many octets in a flow as have been marked CE.

Therefore, a re-ECN TCP receiver MUST increment its ECC value as many times as CE marked packets have been received. And that value MUST be echoed to the sender in the first available ACK using the ECI field. This ensures the TCP sender's congestion control receives timely feedback on congestion events at the same packet granularity that they were generated on congested queues.

Then, a re-ECN sender stores the difference D between its own ECC value and the incoming ECI field by incrementing a counter R. Then, R is decremented by 1 each subsequent packet that is sent with the RE flag blanked, until R is no longer positive. Using this technique, whenever a re-ECN transport sends a not re-ECN capable packet (e.g. a retransmission), the remaining packets required to have the RE flag blanked will be automatically carried over to subsequent packets, through the variable R.

This does not ensure precisely the same number of octets have RE blanked as were CE marked. But we believe positive errors will cancel negative over a long enough period. {ToDo: However, more research is needed to prove whether this is so. If it is not, it may be necessary to increment and decrement R in octets rather than packets, by incrementing R as the product of D and the size in octets of packets being sent (typically the MSS).}

6.2. Other Transports

6.2.1. General Guidelines for Adding Re-ECN to Other Transports

As a general rule, Re-ECT sender transports that have established the receiver transport is at least ECN-capable (not necessarily re-ECN capable) MUST blank the RE codepoint for at least as many octets as arrive at receiver with the CE codepoint set. Re-ECN-capable sender transports should always initialise the ECN field to the ECT(1) codepoint once a flow is established.

If the sender transport does not have sufficient feedback to even estimate the path's CE rate, it SHOULD set FNE continuously. If the sender transport has some, perhaps stale, feedback to estimate that the path's CE rate is nearly definitely less than E%, the transport MAY blank RE in packets for E% of sent octets, and set the RECT codepoint for the remainder.

The following sections give guidelines on how re-ECN support could be added to RSVP or NSIS, to DCCP, and to SCTP - although separate Internet drafts will be necessary to document the exact mechanics of re-ECN in each of these protocols.

{ToDo: Give a brief outline of what would be expected for each of the following:

• UDP fire and forget (e.g. DNS)
• UDP streaming with no feedback
• UDP streaming with feedback

}

6.2.2. Guidelines for adding Re-ECN to RSVP or NSIS

A separate I-D has been submitted [I-D.re-pcn-border-cheat] describing how re-ECN can be used in an edge-to-edge rather than end-to-end scenario. It can then be used by downstream networks to police whether upstream networks are blocking new flow reservations when downstream congestion is too high, even though the congestion is in other operators' downstream networks. This relates to current IETF work on Admission Control over Diffserv using Pre-Congestion Notification (PCN)  [RFC5559].

6.2.3. Guidelines for adding Re-ECN to DCCP

Beside adjusting the initial features negotiation sequence, operating re-ECN in DCCP [RFC4340] could be achieved by defining a new option to be added to acknowledgments, that would include a multibit field where the destination could copy its ECC.

6.2.4. Guidelines for adding Re-ECN to SCTP

Appendix A in [RFC4960] gives the specifications for SCTP to support ECN. Similar steps should be taken to support re-ECN. Beside adjusting the initial features negotiation sequence, operating re-ECN in SCTP could be achieved by defining a new control chunk, that would include a multibit field where the destination could copy its ECC

7. Incremental Deployment

The design of the re-ECN protocol started from the fact that the current ECN marking behaviour of queues was sufficient and that re-feedback could be introduced around these queues by changing the sender behaviour but not the routers. Otherwise, if we had required routers to be changed, the chance of encountering a path that had every router upgraded would be vanishingly small during early deployment, giving no incentive to start deployment. Also, as there is no new forwarding behaviour, routers and hosts do not have to signal or negotiate anything.

However, networks that choose to protect themselves using re-ECN do have to add new security functions at their trust boundaries with others. They distinguish legacy traffic by its ECN field. Traffic from Not-ECT transports is distinguishable by its Not-ECT marking. Traffic from RFC3168 compliant ECN transports is distinguished from re-ECN by which of ECT(0) or ECT(1) is used. We chose to use ECT(1) for re-ECN traffic deliberately. Existing ECN sources set ECT(0) on either 50% (the nonce) or 100% (the default) of packets, whereas re-ECN does not use ECT(0) at all. We can use this distinguishing feature of RFC3168 compliant ECN traffic to separate it out for different treatment at the various border security functions: egress dropping, ingress policing and border policing.

The general principle we adopt is that an egress dropper will not drop any legacy traffic, but ingress and border policers will limit the bulk rate of legacy traffic (Not-ECT, ECT(0) and those marked with the unused codepoint) that can enter each network. Then, during early re-ECN deployment, operators can set very permissive (or non-existent) rate-limits on legacy traffic, but once re-ECN implementations are generally available, legacy traffic can be rate-limited increasingly harshly. Ultimately, an operator might choose to block all legacy traffic entering its network, or at least only allow through a trickle.

Then, as the limits are set more strictly, the more RFC3168 ECN sources will gain by upgrading to re-ECN. Thus, towards the end of the voluntary incremental deployment period, RFC3168 compliant transports can be given progressively stronger encouragement to upgrade.

The following list of minor changes, brings together all the points where re-ECN semantics for use of the two-bit ECN field are different compared to RFC3168:

• A re-ECN sender sets ECT(1) by default, whereas an RFC3168 sender sets ECT(0) by default (Section 4.3);
• No provision is necessary for a re-ECN capable source transport to use the ECN nonce (Section 6.1.4.1);
• Routers MAY preferentially drop different extended ECN codepoints (Section 5.3);
• Packets carrying the feedback not established (FNE) codepoint MAY optionally be marked rather than dropped by routers, even though their ECN field is Not-ECT (with the important caveat in Section 5.3);
• Packets may be dropped by policing nodes because of apparent misbehaviour, not just because of congestion ;
• Tunnel entry behaviour is still to be defined, but may have to be different from RFC3168 (Section 5.6).

None of these changes REQUIRE any modifications to routers. Also none of these changes affect anything about end to end congestion control; they are all to do with allowing networks to police that end to end congestion control is well-behaved.

8. Related Work

8.1. Congestion Notification Integrity

The choice of two ECT code-points in the ECN field [RFC3168] permitted future flexibility, optionally allowing the sender to encode the experimental ECN nonce [RFC3540] in the packet stream. This mechanism has since been included in the specifications of DCCP [RFC4340].

{ToDo: DCCP provides nonce support - how does this affect the RFC?}

The ECN nonce is an elegant scheme that allows the sender to detect if someone in the feedback loop - the receiver especially - tries to claim no congestion was experienced when in fact congestion led to packet drops or ECN marks. For each packet it sends, the sender chooses between the two ECT codepoints in a pseudo-random sequence. Then, whenever the network marks a packet with CE, if the receiver wants to deny congestion happened, she has to guess which ECT codepoint was overwritten. She has only a 50:50 chance of being correct each time she denies a congestion mark or a drop, which ultimately will give her away.

The purpose of a network-layer nonce should primarily be protection of the network, while a transport-layer nonce would be better used to protect the sender from cheating receivers. Now, the assumption behind the ECN nonce is that a sender will want to detect whether a receiver is suppressing congestion feedback. This is only true if the sender's interests are aligned with the network's, or with the community of users as a whole. This may be true for certain large senders, who are under close scrutiny and have a reputation to maintain. But we have to deal with a more hostile world, where traffic may be dominated by peer-to-peer transfers, rather than downloads from a few popular sites. Often the `natural' self-interest of a sender is not aligned with the interests of other users. It often wishes to transfer data quickly to the receiver as much as the receiver wants the data quickly.

In contrast, the re-ECN protocol enables policing of an agreed rate-response to congestion (e.g. TCP-friendliness) at the sender's interface with the internetwork. It also ensures downstream networks can police their upstream neighbours, to encourage them to police their users in turn. But most importantly, it requires the sender to declare path congestion to the network and it can remove traffic at the egress if this declaration is dishonest. So it can police correctly, irrespective of whether the receiver tries to suppress congestion feedback or whether the sender ignores genuine congestion feedback. Therefore the re-ECN protocol addresses a much wider range of cheating problems, which includes the one addressed by the ECN nonce.

{ToDo: Ensure we address the early ACK problem.}

9. Security Considerations

{ToDo: Describe attacks by networks on flows and by spoofing sources.} {ToDo: Re-ECN & DNS servers}

This whole memo concerns the deployment of a secure congestion control framework. However, below we list some specific security issues that we are still working on:

• Malicious users have ability to launch dynamically changing attacks, exploiting the time it takes to detect an attack, given ECN marking is binary. We are concentrating on subtle interactions between the ingress policer and the egress dropper in an effort to make it impossible to game the system.
• There is an inherent need for at least some flow state at the egress dropper given the binary marking environment, which leads to an apparent vulnerability to state exhaustion attacks. An egress dropper design with bounded flow state is in write-up.
• A malicious source can spoof another user's address and send negative traffic to the same destination in order to fool the dropper into sanctioning the other user's flow. To prevent or mitigate these two different kinds of DoS attack, against the dropper and against given flows, we are considering various protection mechanisms.
• A malicious client can send requests using a spoofed source address to a server (such as a DNS server) that tends to respond with single packet responses. This server will then be tricked into having to set FNE on the first (and only) packet of all these wasted responses. Given packets marked FNE are worth +1, this will cause such servers to consume more of their allowance to cause congestion than they would wish to. In general, re-ECN is deliberately designed so that single packet flows have to bear the cost of not discovering the congestion state of their path. One of the reasons for introducing re-ECN is to encourage short flows to make use of previous path knowledge by moving the cost of this lack of knowledge to sources that create short flows. Therefore, we in the long run we might expect services like DNS to aggregate single packet flows into connections where it brings benefits. However, this attack where DNS requests are made from spoofed addresses genuinely forces the server to waste its resources. The only mitigating feature is that the attacker has to set FNE on each of its requests if they are to get through an egress dropper to a DNS server. The attacker therefore has to consume as many resources as the victim, which at least implies re-ECN does not unwittingly amplify this attack.

Having highlighted outstanding security issues, we now explain the design decisions that were taken based on a security-related rationale. It may seem that the six codepoints of the eight made available by extending the ECN field with the RE flag have been used rather wastefully to encode just five states. In effect the RE flag has been used as an orthogonal single bit, using up four codepoints to encode the three states of positive, neutral and negative worth. The mapping of the codepoints in an earlier version of this proposal used the codepoint space more efficiently, but the scheme became vulnerable to network operators bypassing congestion penalties by focusing congestion marking on positive packets. Appendix B explains why fixing that problem while allowing for incremental deployment, would have used another codepoint anyway. So it was better to use this orthogonal encoding scheme, which greatly simplified the whole protocol and brought with it some subtle security benefits (see the last paragraph of Appendix B).

With the scheme as now proposed, once the RE flag is set or cleared by the sender or its proxy, it should not be written by the network, only read. So the endpoints can detect if any network maliciously alters the RE flag. IPsec AH integrity checking does not cover the IPv4 option flags (they were considered mutable---even the one we propose using for the RE flag that was `currently unused' when IPsec was defined). But it would be sufficient for a pair of endpoints to make random checks on whether the RE flag was the same when it reached the egress as when it left the ingress. Indeed, if IPsec AH had covered the RE flag, any network intending to alter sufficient RE flags to make a gain would have focused its alterations on packets without authenticating headers (AHs).

The security of re-ECN has been deliberately designed to not rely on cryptography.

10. IANA Considerations

This memo includes no request to IANA (yet).

If this memo was to progress to standards track, it would list:

• The new RE flag in IPv4 (Section 5.1) and its extension with the ECN field to create a new set of extended ECN (EECN) codepoints;
• The definition of the EECN codepoints for default Diffserv PHBs (Section 4.2)
• The Hop-by-Hop option ID for the new extension header for IPv6 (Section 5.2);
• The new combinations of flags in the TCP header for capability negotiation (Section 6.1.5);

11. Conclusions

{ToDo:}

12. Acknowledgements

Sébastien Cazalet and Andrea Soppera contributed to the idea of re-feedback. All the following have given helpful comments: Andrea Soppera, David Songhurst, Peter Hovell, Louise Burness, Phil Eardley, Steve Rudkin, Marc Wennink, Fabrice Saffre, Cefn Hoile, Steve Wright, John Davey, Martin Koyabe, Carla Di Cairano-Gilfedder, Alexandru Murgu, Nigel Geffen, Pete Willis, John Adams (BT), Sally Floyd (ICIR), Joe Babiarz, Kwok Ho-Chan (Nortel), Stephen Hailes, Mark Handley (who developed the attack with canceled packets), Adam Greenhalgh (who developed the attack on DNS) (UCL), Jon Crowcroft (Uni Cam), David Clark, Bill Lehr, Sharon Gillett, Steve Bauer (who complemented our own dummy traffic attacks with others), Liz Maida (MIT), Meral Shirazipour (Ericsson) and comments from participants in the CRN/CFP Broadband and DoS-resistant Internet working groups.A special thank you to Alessandro Salvatori for coming up with fiendish attacks on re-ECN.

13. Comments Solicited

Comments and questions are encouraged and very welcome. They can be addressed to the IETF Congestion Exposure (ConEx) working group's mailing list <conex@ietf.org>, and/or to the authors.

14. References

14.1. Normative References

[RFC2119]	Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997.
[RFC2581]	Allman, M., Paxson, V. and W. Stevens, "TCP Congestion Control", RFC 2581, April 1999.
[RFC3168]	Ramakrishnan, K., Floyd, S. and D. Black, "The Addition of Explicit Congestion Notification (ECN) to IP", RFC 3168, September 2001.
[RFC3390]	Allman, M., Floyd, S. and C. Partridge, "Increasing TCP's Initial Window", RFC 3390, October 2002.
[RFC4302]	Kent, S., "IP Authentication Header", RFC 4302, December 2005.
[RFC4340]	Kohler, E., Handley, M. and S. Floyd, "Datagram Congestion Control Protocol (DCCP)", RFC 4340, March 2006.
[RFC4341]	Floyd, S. and E. Kohler, "Profile for Datagram Congestion Control Protocol (DCCP) Congestion Control ID 2: TCP-like Congestion Control", RFC 4341, March 2006.
[RFC4342]	Floyd, S., Kohler, E. and J. Padhye, "Profile for Datagram Congestion Control Protocol (DCCP) Congestion Control ID 3: TCP-Friendly Rate Control (TFRC)", RFC 4342, March 2006.
[RFC4835]	Manral, V., "Cryptographic Algorithm Implementation Requirements for Encapsulating Security Payload (ESP) and Authentication Header (AH)", RFC 4835, April 2007.
[RFC4960]	Stewart, R., "Stream Control Transmission Protocol", RFC 4960, September 2007.
[RFC5562]	Kuzmanovic, A., Mondal, A., Floyd, S. and K. Ramakrishnan, "Adding Explicit Congestion Notification (ECN) Capability to TCP's SYN/ACK Packets", RFC 5562, June 2009.
[RFC5681]	Allman, M., Paxson, V. and E. Blanton, "TCP Congestion Control", RFC 5681, September 2009.
[RFC6040]	Briscoe, B., "Tunnelling of Explicit Congestion Notification", RFC 6040, November 2010.

14.2. Informative References

[ARI05]	Adams, J., Roberts, L. and A. IJsselmuiden, "Changing the Internet to Support Real-Time Content Supply from a Large Fraction of Broadband Residential Users", BT Technology Journal (BTTJ) 23(2), April 2005.
[I-D.conex-tcp-mods]	Kuehlewind, M. and R. Scheffenegger, "TCP modifications for Congestion Exposure", Internet-Draft draft-ietf-conex-tcp-modifications-05, February 2014.
[I-D.re-ecn-motiv]	Briscoe, B., Jacquet, A., Moncaster, T. and A. Smith, "Re-ECN: A Framework for adding Congestion Accountability to TCP/IP", Internet-Draft draft-briscoe-conex-re-ecn-motiv-03, March 2014.
[I-D.re-pcn-border-cheat]	Briscoe, B., "Emulating Border Flow Policing using Re-PCN on Bulk Data", Internet-Draft draft-briscoe-re-pcn-border-cheat-03, October 2009.
[RFC2309]	Braden, B., Clark, D., Crowcroft, J., Davie, B., Deering, S., Estrin, D., Floyd, S., Jacobson, V., Minshall, G., Partridge, C., Peterson, L., Ramakrishnan, K., Shenker, S., Wroclawski, J. and L. Zhang, "Recommendations on Queue Management and Congestion Avoidance in the Internet", RFC 2309, April 1998.
[RFC2475]	Blake, S., Black, D., Carlson, M., Davies, E., Wang, Z. and W. Weiss, "An Architecture for Differentiated Services", RFC 2475, December 1998.
[RFC3124]	Balakrishnan, H. and S. Seshan, "The Congestion Manager", RFC 3124, June 2001.
[RFC3514]	Bellovin, S., "The Security Flag in the IPv4 Header", RFC 3514, April 1 2003.
[RFC3540]	Spring, N., Wetherall, D. and D. Ely, "Robust Explicit Congestion Notification (ECN) Signaling with Nonces", RFC 3540, June 2003.
[RFC4301]	Kent, S. and K. Seo, "Security Architecture for the Internet Protocol", RFC 4301, December 2005.
[RFC5129]	Davie, B., Briscoe, B. and J. Tay, "Explicit Congestion Marking in MPLS", RFC 5129, January 2008.
[RFC5559]	Eardley, P., "Pre-Congestion Notification (PCN) Architecture", RFC 5559, June 2009.
[RFC6298]	Paxson, V., Allman, M., Chu, J. and M. Sargent, "Computing TCP's Retransmission Timer", RFC 6298, June 2011.
[Re-fb]	Briscoe, B., Jacquet, A., Di Cairano-Gilfedder, C., Salvatori, A., Soppera, A. and M. Koyabe, "Policing Congestion Response in an Internetwork Using Re-Feedback", ACM SIGCOMM CCR 35(4)277--288, August 2005.
[Savage99]	Savage, S., Cardwell, N., Wetherall, D. and T. Anderson, "TCP congestion control with a misbehaving receiver", ACM SIGCOMM CCR 29(5), October 1999.
[Steps_DoS]	Handley, M. and A. Greenhalgh, "Steps towards a DoS-resistant Internet Architecture", Proc. ACM SIGCOMM workshop on Future directions in network architecture (FDNA'04) pp 49--56, August 2004.
[tcp-rcv-cheat]	Moncaster, T., Briscoe, B. and A. Jacquet, "A TCP Test to Allow Senders to Identify Receiver Non-Compliance", Internet-Draft draft-moncaster-tcpm-rcv-cheat-03, July 2014.

Appendix A. Precise Re-ECN Protocol Operation

The protocol operation in Section 4.3 was described as an approximation. In fact, standard ECN marking at a queue combines 1% and 2% marking into slightly less than 3% whole-path marking, because queues deliberately mark CE whether or not it has already been marked by another queue upstream. So the combined marking fraction would actually be 100% - (100% - 1%)(100% - 2%) = 2.98%.

To generalise this we will need some notation.

• j represents the index of each resource (typically queues) along a path, ranging from 0 at the first queue to n-1 at the last.
• m_j represents the fraction of octets to be |*m|arked CE by a particular queue (whether or not they are already marked) because of congestion of resource j.
• u_j represents congestion signals arriving from |*u|pstream of resource j, being the fraction of CE marking in arriving packet headers (before marking).
• p_j represents |*p|ath congestion, being the fraction of packets arriving at resource j with the RE flag blanked (excluding Not-RECT packets).
• v_j denotes expected congestion downstream of resource j, which can be thought of as a |*v|irtual marking fraction, being derived from two other marking fractions.

Observed fractions of each particular codepoint (u, p and v) and queue marking rate m are dimensionless fractions, being the ratio of two data volumes (marked and total) over a monitoring period. All measurements are in terms of octets, not packets, assuming that line resources are more congestible than packet processing.

The path congestion (RE blanking fraction) set by the sender should reflect upstream congestion (CE marking fraction) from the viewpoint of the destination, which it feeds back to the sender. Therefore in the steady state

   p_0  = u_n 
        = 1 - (1 - m_1)(1 - m_2)...

Similarly, at some point j in the middle of the network, given p = 1 - (1 - u_j)(1 - v_j), then

   v_j  = 1 - (1 - p)/(1 - u_j)

       ~= p - u_j;                      if u_j << 100%

So, between the two routers in the example in Section 4.3, congestion downstream is

   v_1  = 100.00% - (100% - 2.98%) / (100% - 1.00%)
        = 2.00%,

or a useful approximation of downstream congestion is

   v_1 ~= 2.98% - 1.00%
       ~= 1.98%.

Appendix B. Justification for Two Codepoints Signifying Zero Worth Packets

It may seem a waste of a codepoint to set aside two codepoints of the Extended ECN field to signify zero worth (RECT and CE(0) are both worth zero). The justification is subtle, but worth recording.

The original version of Re-ECN ([Re-fb] and draft-00 of this memo) used three codepoints for neutral (ECT(1)), positive (ECT(0)) and negative (CE) packets. The sender set packets to neutral unless re-echoing congestion, when it set them positive, in much the same way that it blanks the RE flag in the current protocol. However, routers were meant to mark congestion by setting packets negative (CE) irrespective of whether they had previously been neutral or positive.

However, we did not arrange for senders to remember which packet had been sent with which codepoint, or for feedback to say exactly which packets arrived with which codepoints. The transport was meant to inflate the number of positive packets it sent to allow for a few being wiped out by congestion marking. We (wrongly) assumed that routers would congestion mark packets indiscriminately, so the transport could infer how many positive packets had been marked and compensate accordingly by re-echoing. But this created a perverse incentive for routers to preferentially congestion mark positive packets rather than neutral ones.

We could have removed this perverse incentive by requiring Re-ECN senders to remember which packets they had sent with which codepoint. And for feedback from the receiver to identify which packets arrived as which. Then, if a positive packet was congestion marked to negative, the sender could have re-echoed twice to maintain the balance between positive and negative at the receiver.

Instead, we chose to make re-echoing congestion (blanking RE) orthogonal to congestion notification (marking CE), which required a second neutral codepoint. Then the receiver would be able to detect and echo a congestion event even if it arrived on a packet that had originally been positive.

If we had added extra complexity to the sender and receiver transports to track changes to individual packets, we could have made it work, but then routers would have had an incentive to mark positive packets with half the probability of neutral packets. That in turn would have led router algorithms to become more complex. Then senders wouldn't know whether a mark had been introduced by a simple or a complex router algorithm. That in turn would have required another codepoint to distinguish between RFC3168 ECN and new Re-ECN router marking.

Once the cost of IP header codepoint real-estate was the same for both schemes, there was no doubt that the simpler option for endpoints and for routers should be chosen. The resulting protocol also no longer needed the tricky inflation/deflation complexity of the original (broken) scheme. It was also much simpler to understand conceptually.

A further advantage of the new orthogonal four-codepoint scheme was that senders owned sole rights to change the RE flag and routers owned sole rights to change the ECN field. Although we still arrange the incentives so neither party strays outside their dominion, these clear lines of authority simplify the matter.

Finally, a little redundancy can be very powerful in a scheme such as this. In one flow, the proportion of packets changed to CE should be the same as the proportion of RECT packets changed to CE(-1) and the proportion of Re-Echo packets changed to CE(0). Double checking using such redundant relationships can improve the security of a scheme (cf. double-entry book-keeping or the ECN Nonce). Alternatively, it might be necessary to exploit the redundancy in the future to encode an extra information channel.

Appendix C. ECN Compatibility

The rationale for choosing the particular combinations of SYN and SYN ACK flags in Section 6.1.5 is as follows.

Choice of SYN flags:

A Re-ECN sender can work with RFC3168 compliant ECN receivers so we wanted to use the same flags as would be used in an ECN-setup SYN [RFC3168] (CWR=1, ECE=1). But at the same time, we wanted a server (host B) that is Re-ECT to be able to recognise that the client (A) is also Re-ECT. We believe also setting NS=1 in the initial SYN achieves both these objectives, as it should be ignored by RFC3168 compliant ECT receivers and by ECT-Nonce receivers. But senders that are not Re-ECT should not set NS=1. At the time ECN was defined, the NS flag was not defined, so setting NS=1 should be ignored by existing ECT receivers (but testing against implementations may yet prove otherwise). The ECN Nonce RFC [RFC3540] is silent on what the NS field might be set to in the TCP SYN, but we believe the intent was for a nonce client to set NS=0 in the initial SYN (again only testing will tell). Therefore we define a Re-ECN-setup SYN as one with NS=1, CWR=1 & ECE=1

Choice of SYN ACK flags:

Choice of SYN ACK: The client (A) needs to be able to determine whether the server (B) is Re-ECT. The original ECN specification required an ECT server to respond to an ECN-setup SYN with an ECN-setup SYN ACK of CWR=0 and ECE=1. There is no room to modify this by setting the NS flag, as that is already set in the SYN ACK of an ECT-Nonce server. So we used the only combination of CWR and ECE that would not be used by existing TCP receivers: CWR=1 and ECE=0. The original ECN specification defines this combination as a non-ECN-setup SYN ACK, which remains true for RFC3168 compliant and Nonce ECTs. But for Re-ECN we define it as a Re-ECN-setup SYN ACK. We didn't use a SYN ACK with both CWR and ECE cleared to 0 because that would be the likely response from most Not-ECT receivers. And we didn't use a SYN ACK with both CWR and ECE set to 1 either, as at least one broken receiver implementation echoes whatever flags were in the SYN into its SYN ACK. Therefore we define a Re-ECN-setup SYN ACK as one with CWR=1 & ECE=0.

Choice of two alternative SYN ACKs:

the NS flag may take either value in a Re-ECN-setup SYN ACK. Section 5.4 REQUIRES that a Re-ECT server MUST set the NS flag to 1 in a Re-ECN-setup SYN ACK to echo congestion experienced (CE) on the initial SYN. Otherwise a Re-ECN-setup SYN ACK MUST be returned with NS=0. The only current known use of the NS flag in a SYN ACK is to indicate support for the ECN nonce, which will be negotiated by setting CWR=0 & ECE=1. Given the ECN nonce MUST NOT be used for a RECN mode connection, a Re-ECN-setup SYN ACK can use either setting of the NS flag without any risk of confusion, because the CWR & ECE flags will be reversed relative to those used by an ECN nonce SYN ACK.

{ToDo: include the text below, either here, or in the algorithm sections} At an egress dropper, well-behaved RFC3168 compliant flows will appear to consist mostly of ECT(0) packets, with a few CE(0) packet. And, if the legacy source is setting the ECN nonce, the majority of packets will be an equal mix of ECT(0) and ECT(1) packets (the latter appearing to be Re-Echo packets in Re-ECN terms). None of these three packet markings is negative, so an egress dropper can handle all legacy flows in bulk and, as long as they don't send any packets using Re-ECN markings, it need not drop any legacy packets. So, as soon as an ECT(0) packet is seen, its flow ID can be added to the set of known legacy flows (a single Bloom filter would suffice). But, if any packets in flows classified as RFC3168 compliant are marked with any other marking than the three expected, the flow can be removed from the RFC3168 set, to be treated in bulk with mis-behaving Re-ECN flows---the remainder of flow IDs that require no flow state to be held.

To an ingress Re-ECN policer, legacy ECN flows will appear as very highly congested paths. When policers are first deployed they can be configured permissively, allowing through both `RFC3168' ECN and misbehaving Re-ECN flows. Then, as the threshold is set more strictly, the more RFC3168 ECN sources will gain by upgrading to Re-ECN. Thus, towards the end of the voluntary incremental deployment period, RFC3168 transports can be given progressively stronger encouragement to upgrade.

Appendix D. Packet Marking with FNE During Flow Start

FNE (feedback not established) packets have two functions. Their main role is to announce the start of a new flow when feedback has not yet been established. However they also have the role of balancing the expected feedback and can be used where there are sudden changes in the rate of transmission. Whilst this should not happen under TCP their use as speculative marking is used in building the following argument as to why the first and third packets should be set to FNE.

The proportion of FNE packets in each round-trip should be a high estimate of the potential error in the balance of number of congestion marked packets versus number of re-echo packets already issued.

Let's call:

• S: the number of the TCP segments sent so far
• F: the number of FNE packets sent so far
• R: the number of Re-Echo packets sent so far
• A: the number of acknowledgments received so far
• C: the number of acknowledgments echoing a CE packet

In normal operation, when we want to send packet S+1, we first need to check that enough Re-Echo packets have been issued:

If R<C, then S+1 will be a Re-echo packet

Next we need to estimate the amount of congestion observed so far. If congestion was stationary, it could be estimated as C/A. A pessimistic bound is (C+1)/(A+1) which assumes that the next acknowledgment will echo a CE packet; we'll use that more pessimistic estimate to drive the generation of FNE packets.

The number of CE packets expected when (S+1) will be acknowledged is therefore (S+1)*(C+1)/(A+1). Packet S+1 should be set to FNE if that expected value exceeds the sum of FNE and Re-Echo packets sent so far.

   If  (F+R)<(S+1)*(C+1)/(A+1), 
     then S+1 will be set to FNE 
     else S+1 will be set to RECT 
     

So the full test should be:

   When packet (S+1) is about to be sent...  
     If R<C, 
        then S+1 will be set to Re-Echo 
     Else if  (F+R)<(S+1)*(C+1)/(A+1), 
       then S+1 will be set to FNE 
     Else S+1 will be set to RECT 
     

This means that at any point, given A, R, F, C, the source could send another k RECT packets, so that k < (F+R)*(A+1)/(C+1)-S

The above scheme is independent of the actions of both the dropper and policer and doesn't depend on the rate adaptation discipline of the source. It only defines Re-Echo packets as notification of effective end-to-end congestion (as witnessed at the previous round-trip), and FNE packets as notification of speculative end-to-end congestion based on a high estimate of congestion

In practice, for any source:

• for the first packet, A=R=F=C=S=0 ==> 1 FNE
• if the acknowledgment doesn't echo a mark
  • for the second packet, A=F=S=1 R=C=0 ==> 1 RECT
  • for the third packet, S=2 A=F=1 R=C=0 ==> 1 FNE
• if no acknowledgement for these two packets echoes a congestion mark, then {A=S=3 F=2 R=C=0} which gives k<2*4/1-3, so the source
• if no acknowledgement for these four packets echoes a congestion mark, then {A=S=7 F=2 R=C=0} which gives k<2*8/1-7, so the source could send another 8 RECT packets. ==> 8 RECT

This behaviour happens to match TCP's congestion window control in slow start, which is why for TCP sources, only the first and third packet need be FNE packets.

A source that would open the congestion window any quicker would have to insert more FNE packets. As another example a UDP source sending VBR traffic might need to send several FNE packets ahead of the traffic peaks it generates.

Appendix E. Argument for holding back the ECN nonce

The ECN nonce is a mechanism that allows a /sending/ transport to detect if drop or ECN marking at a congested router has been suppressed by a node somewhere in the feedback loop---another router or the receiver.

Space for the ECN nonce was set aside in [RFC3168] (currently proposed standard) while the full nonce mechanism is specified in [RFC3540] (currently experimental). The specifications for [RFC4340] (currently proposed standard) requires that "Each DCCP sender SHOULD set ECN Nonces on its packets...". It also mandates as a requirement for all CCID profiles that "Any newly defined acknowledgement mechanism MUST include a way to transmit ECN Nonce Echoes back to the sender.", therefore:

• The CCID profile for TCP-like Congestion Control [RFC4341] (currently proposed standard) says "The sender will use the ECN Nonce for data packets, and the receiver will echo those nonces in its Ack Vectors."
• The CCID profile for TCP-Friendly Rate Control (TFRC) [RFC4342] recommends that "The sender [use] Loss Intervals options' ECN Nonce Echoes (and possibly any Ack Vectors' ECN Nonce Echoes) to probabilistically verify that the receiver is correctly reporting all dropped or marked packets."

The primary function of the ECN nonce is to protect the integrity of the information about congestion: ECN marks and packet drops. However, when the nonce is used to protect the integrity of information about packet drops, rather than ECN marks, a transport layer nonce will always be sufficient (because a drop loses the transport header as well as the ECN field in the network header), which would avoid using scarce IP header codepoint space. Similarly, a transport layer nonce would protect against a receiver sending early acknowledgements [Savage99].

If the ECN nonce reveals integrity problems with the information about congestion, the sending transport can use that knowledge for two functions:

• to protect its own resources, by allocating them in proportion to the rates that each network path can sustain, based on congestion control,
• and to protect congested routers in the network, by slowing down drastically its connection to the destination with corrupt congestion information.

If the sending transport chooses to act in the interests of congested routers, it can reduce its rate if it detects some malicious party in the feedback loop may be suppressing ECN feedback. But it would only be useful to congested routers when /all/ senders using them are trusted to act in interest of the congested routers.

In the end, the only essential use of a network layer nonce is when sending transports (e.g. large servers) want to allocate their /own/ resources in proportion to the rates that each network path can sustain, based on congestion control. In that case, the nonce allows senders to be assured that they aren't being duped into giving more of their own resources to a particular flow. And if congestion suppression is detected, the sending transport can rate limit the offending connection to protect its own resources. Certainly, this is a useful function, but the IETF should carefully decide whether such a single, very specific case warrants IP header space.

In contrast, Re-ECN allows all routers to fully protect themselves from such attacks, without having to trust anyone - senders, receivers, neighbouring networks. Re-ECN is therefore proposed in preference to the ECN nonce on the basis that it addresses the generic problem of accountability for congestion of a network's resources at the IP layer.

Delaying the ECN nonce is justified because the applicability of the ECN nonce seems too limited for it to consume a two-bit codepoint in the IP header. It therefore seems prudent to give time for an alternative way to be found to do the one function the nonce is essential for.

Moreover, while we have re-designed the Re-ECN codepoints so that they do not prevent the ECN nonce progressing, the same is not true the other way round. If the ECN nonce started to see some deployment (perhaps because it was blessed with proposed standard status), incremental deployment of Re-ECN would effectively be impossible, because Re-ECN marking fractions at inter-domain borders would be polluted by unknown levels of nonce traffic.

The authors are aware that Re-ECN must prove it has the potential it claims if it is to displace the nonce. Therefore, every effort has been made to complete a comprehensive specification of Re-ECN so that its potential can be assessed. We therefore seek the opinion of the Internet community on whether the Re-ECN protocol is sufficiently useful to warrant standards action.

Appendix F. Alternative Terminology Used in Other Documents

A number of alternative terms have been used in various documents describing re-feedback and re-ECN. These are set out in the following table