Transcript Recitation_ECN

Internet Networking
recitation #10
Explicit Congestion Notification
(RFC 3168)
Limited Transmit (RFC 3042)
Spring Semester 2009, Dept. of Computer Science, Technion
1
2
Network Congestion Indication by
Active Queue Management - AQM

Main Idea – router can detect congestion before its queue
overflows, and provide an indication of this congestion to the end
nodes. This mechanism is called Active Queue Management.




TCP does not have to relay on buffer overflow as the only indication
of congestion.
May use several methods for indicating congestion to end-nodes:
• Use packet drops, as is currently done.
• Use specific field in a packet header as an indication of congestion.
This has the potential of reducing the impact of loss on latencysensitive flows.
AQM drops/indicates packets based on the average queue length
exceeding a threshold, rather than only when the queue
overflows.
Internet Networking
3
AQM Example: Random Early Detection(RED)

Drops packets when the buffer is full

(average queue size) < ( minimal threshold )
=> no packets are dropped.

(average queue size) > ( maximal threshold)
=> every arriving packet is dropped.

(minimal threshold)<(average queue size)<(maximal threshold)
=> each arriving packet is dropped with a probability that is a
function of the average queue size.
Internet Networking
4
General Principles


Co-existence

cooperation with existing TCP mechanisms for adapting to congestion

cooperation with routers' current practice of dropping packets in periods
of congestion.
Congestion persistence


Long-time flow


congestion events that may last longer than a round-trip time.
managing flows that are still active when network feedback reaches
them.
Asymmetric routing

Data packets path may be different from acknowledgment path.
Internet Networking
5
Congestion Scenario
Sender
Receiver
Data packet
AQM router
ACK
Reduce
congestion
window
Internet Networking
6
Congestion Notification in IP





Two bits from the IP header used for Explicit Congestion Notification.
Bits 6 and 7 in the TOS (Type of Service) octet  ECN field:
00
– Not ECN-Capable Transport
01
– ECN-Capable Transport (ECT(0))
10
– ECN-Capable Transport (ECT(1))
11
– Congestion Experienced (CE)
’00’ - not-ECT code  packet that is not using ECN.
’01’ and ’10’ - ECT(0) and ECT(1)  set by the sender

Indicate that the end-points of the transport protocol are ECN-capable.

Routers treat the ECT(0) and ECT(1) as equivalent.
’11’ – CE  set by a router to indicate congestion to the end nodes.

Routers that have a packet arriving at a full queue drop the packet, just
as they do in the absence of ECN.
Internet Networking
7
Congestion Notification in IP (end nodes)

Upon the receipt of a single CE packet,

The congestion control algorithm must be the same as a response to
a single dropped packet.

E.g., ECN-capable TCP source halve its congestion window for either
a packet drop or an ECN indication.
•

If there were different congestion control responses to a CE code point
than to a packet drop, this could result in unfair treatment for different
flows.
End-systems react to congestion at most once per window of data
•
to avoid reacting multiple times to multiple indications of congestion within
a round-trip time.
Internet Networking
8
Congestion Notification in IP (routers)



Router set the CE code point of an ECN-Capable packet only if it
would otherwise drop the packet as an indication of congestion to
the end nodes.
When a CE packet is received by a router, the CE code point is
left unchanged, and the packet is transmitted as usual.
Additional treatment should be done for fragmented and
encapsulated packets.

Don’t Fragment bit may be set.
Internet Networking
9
AQM router behavior
Congested router
ECT(0)
Not congested router
CE
ECT(0)
ECT(0)
CE
CE
May also
drop the
packet
CE
not-ECT
CE
Drops the
packet
not-ECT
Internet Networking
not-ECT
10
Congestion Notification in TCP

Negotiation between endpoints during connection setup to
determine if both support ECN

ECN-Echo flag in the TCP header
•

Congestion Window Reduced flag in the TCP header
•



For a receiver to inform the sender when a CE packet has been received
For the sender to inform the receiver that the congestion window has been
reduced
Two last bits of the Reserved field in the TCP header are designated
as ECN-Echo (ECE) and Congestion Window Reduced (CWR)
flags.
ECN uses the ECT and CE flags in the IP header for signaling
between routers and connection endpoints
ECN uses the ECN-Echo and CWR flags in the TCP header for
TCP-endpoint to TCP-endpoint signaling.
Internet Networking
Congestion Notification in TCP (sequence of events )

ECT is set in packets transmitted by the sender




When an ECN-capable router detects:

Congestion

and an ECT code set in the packet it is about to drop
Instead of dropping the packet, it may choose to set the CE code point in the
IP header and forwards the packet.
The receiver receives the packet with the CE code point set


indicate that ECN is supported by the transport entities for these packets.
sets the ECN-Echo flag in its next TCP ACK sent to the sender.
The sender receives the TCP ACK with ECN-Echo set

reacts as if a packet had been dropped (changes sstresh and cwnd in
accordance).

sets the CWR flag in the TCP header of the next packet sent to the receiver
•
to acknowledge its receipt of and reaction to the ECN-Echo flag.
Internet Networking
11
12
TCP Initialization



In the TCP connection setup phase, the source and destination
TCPs exchange information about their willingness to use ECN.
Host A sends an ECN-setup SYN packet (ECE and CWR are set)
Host B sends an ECN-setup SYN-ACK (ECE set, CWR unset)
packet.


This asymmetry is necessary for the robust negotiation of ECN-capability
with some deployed TCP implementations which simply copy the
Reserved field from the received data packet to the ACK packet.
Afterwards the TCP sender sets an ECT code point in the IP header
of data packets to indicate to the network that the transport is
capable and willing to participate in ECN for this packet.
Internet Networking
13
TCP Initialization (cont.)
Host B
Host A
Internet Networking
14
TCP Sender

If the sender receives an ACK packet with the ECN-Echo flag set in the TCP
header


The indication of congestion should be treated just as a congestion loss in
non-ECN-Capable TCP



it knows that congestion was encountered in the network on the path from the
sender to the receiver.
the TCP source halves the congestion window "cwnd" and reduces the slow start
threshold "sstresh".
TCP should not react to congestion indications more than once every
window of data.
When an ECN-Capable TCP sender reduces its congestion window for any
reason (because of a retransmit timeout, a Fast Retransmit, or in response
to an ECN Notification)

the TCP sender sets the CWR flag in the TCP header of the first new data packet
sent after the window reduction.
Internet Networking
15
TCP Receiver

When TCP receives a CE data packet at the destination end-system


To provide robustness against the possibility of a dropped ACK
packet carrying an ECN-Echo flag


It sets the ECN-Echo flag in the TCP header of the subsequent ACK
packet.
The TCP receiver sets the ECN-Echo flag in a series of ACK packets
sent subsequently (whether they acknowledge CE data packets or nonCE data packets).
The TCP receiver uses the CWR flag received from the TCP sender
to determine when to stop setting the ECN-Echo flag.
Internet Networking
16
Sender
Router
Receiver
Congestion
Data packets
ACKs with
ECN-Echo
flag set
Reduce
congestion
window
Stop set
ECN-Echo flag
cwnd
doesn’t
reduced
Internet Networking
17
TCP/IP changes summary

IP changes:





Two bits in the IP header to be used for ECN.
The not-ECT code point indicates that the transport protocol will ignore
the CE code point. This is the default value for the ECN code point.
The ECT code points indicate that the transport protocol is willing and
able to participate in ECN.
The router sets the CE code point to indicate congestion to the end
nodes. The CE code point in a packet header must not be reset by a
router.
TCP changes:




Two bits in the TCP header.
Setup phase.
The ECN-Echo flag is used by the data receiver to inform the data sender
of a received CE packet.
The Congestion Window Reduced (CWR) flag is used by the data sender
to inform the data receiver that the congestion window has been reduced.
Internet Networking
18
Limited Transmit



cwnd can be smaller than 4.
Due to a large number of packet loss, less than 3 dup acks will
arrive.
This causes a timeout rather than a Fast Retransmit.
Internet Networking
19
TCP modification




The sender will send a new segment for each dup-Ack it
receives.
The amount of data is limited to cwnd+2
cwnd does NOT change due to a dup-ack.
Follows the "conservation of packets“ congestion control
principle since each of the first two duplicate ACKs indicate that
a segment has left the network.
Internet Networking
20
Example
3
cwnd=3
4
5
ACK(3)
ACK(3)
6
7
Congestion avoidance
ACK(3)
ACK(3)
---- 3
Fast retransmit
X
ACK(8)
Sstresh = 3/2 = 2
Cwnd = sstresh+3=2+3=5
Internet Networking
21
Example #2
cwnd=3
-------
3
4
5
ACK(3)
ACK(3)
ACK(6)
6
cwnd=4
-------
7
8
9
Internet Networking
22
ECN and Limited Transmit



ECN can inform of congestion without dropping the packet,
thus allowing TCP with small cwnd to be aware of congestion
while avoiding timeouts.
ECN requires the co-operation of the network, while Limited
Transmit does not.
Can be simultaneously used.
Internet Networking