Today's Contents

Part1: TCP Issues and Solutions

Part2: Congestion Control
Part3: Simulating TCP
TCP and Congestion Control (Day 2)

Yoshifumi Nishida
nishida@csl.sony.co.jp
Sony Computer Science Labs, Inc

1 2

Part 1: TCP Issues and Solutions Long Fat Network (1)

Long Fat Networks What are "Long Fat Networks"?
° A network with large bandwidth and long delay.
Ambiguity of Acknowledgment • ex. High-capacity satellite channels
Connection Setup Overhead TCP performance
° TCP performance is calculated by Window Size and RTT.
Security Vulnerabilities

° Required windowsize for networks.

Required Windowsize = Round -Trip Time X Maximum Transfer Rate of the network.

° But Maximum window size is limited to 65,535 bytes.

• The window size in TCP header has only 16 bits.

3 4

Long Fat Network (2) Long Fat Network (3)

65,535 bytes window size is not enough for Window Scale Option
° Extension to specify large window size
Long Fat Networks! • defined in RFC1323: TCP Extensions for High Performance.
° Option Format:

° Example of Long Fat Networks.

Transfer rate RTT(msec) Required Window Size (bytes)
1.54Mbps (T1) 500 95,500 ° The window size is treated as:
45Mbps (T3) 60 337,500

° Max value of shift count is limited to 14.

• Maximum window size is 1,073,725,440 (65535 * 2^14) bytes with
this option.
5 6

1
 Long Fat Network (4) Ambiguity of the Acknowledgment (1)
Sequence Number Wrap Around
Cumulative ACK style is ambiguous, when multiple packets are lost.
° Another issue for Long Fat Networks.
° TCP cannot identify which packets are lost exactly.
° 32-bit sequence number space may wrap around in LFNs .
• Causes poor performance over lossy networks (ex. wireless networks)

Time Stamp Option

° Provides transmit time information.
• TCP can identify each packet with Time Stamp and Sequence Number.

7 8

Ambiguity of the Acknowledgment (2) Ambiguity of the Acknowledgment (3)

Selective Acknowledgment Options SACK Permitted Option
° Provides precise information about packet arrivals.
° Two options are defined in RFC2018.
SACK Permitted Option
SACK Option
° Used in a SYN packet to indicate that SACK option
can be used.
SACK Option
° Used in an ACK packet to indicate which packets
were received precisely.

9 10

Ambiguity of the Acknowledgment (4) Connection Setup Overhead (1)

Example of the SACK option TCP is not suitable for a transaction service.
° TCP requires 3 packets for connection setup.
° TCP requires 4 packets for connection termination.

11 12

2
 Connection Setup Overhead (2) Security Vulnerabilities (1)
T/TCP option Sequence Number Attack
° TCP extension for transactions ° If someone can guess Sequence Number used in your TCP
• Exchange data with 3 packets. connections...
• Use Connection Count (CC) to bypass 3 way handshake • He can "hijack" your TCP connection.
• Defined in RFC1644. – TCP checks IP address and Port Number and Sequence number.
° But most of current implementations use cryptic algorithms to
generate ISN (Initial Sequence Number).

13 14

Security Vulnerabilities (2) Security Vulnerabilities (3)

SYN Flood Attack Protection against SYN Flood Attacks
° Denial of Service Attack ° IP level solution
° Send a large number of SYN packets with Random source IP
• Use IPsec
address
– Allows TCP connection only to authenticated hosts
° Cause memory overflow on the victim
• Use IP filter
• TCP allocates memory when it receives SYN packets.
– Filters out IP addresses that do not look legitimate

15 16

Security Vulnerabilities (4) Part 2: Congestion Control

Protection against SYN Flood Attacks How does congestion happen?
° TCP level solution
• SYN Cache
Why congestion is difficult?
– Reduces the memory size allocated after receiving SYN packets Congestion Control by TCP
• SYN Cookie
– Sends back ACK with Special Sequence Number in response to SYN
packets.
– Does not allocate memory at all after receiving SYN.

17 18

3
 How does congestion happen? Congestion Tends To Get Worse
Congestion occurs when there is too much traffic in the ° If congestion occurs..
networks • Packet transfers are delayed
Routers have queuing capability. • Packets are discarded
° If a router cannot transmit packets at a given instance, it stor es
packets in the queue and waits for the next chance to transmit. • Some protocols/applications try to retransmit data
° Queue has limited size • Users try to retransmit the data or request the same data
° If queue data exceeds limit, packet will be discarded. again and again

° The ratio of valid data is decreasing...

° Congestion Collapse
• We cannot use network!

19 20

Why is congestion control difficult? (1) Why is congestion control difficult? (2)
Internet is designed to be autonomous. The status of the Internet is hard to grasp
° No central control. ° It is difficult to determine how many user/application share the
° There is no way to control each user's behavior. network exactly.
° It is difficult to determine the source of the congestion exactl y.
Internet is very huge and still expanding.
° It is difficult to determine the capacity of the networks exactl y.
° It is difficult to determine how much networks are congested
exactly.
° It is difficult to determine why packets are lost exactly.

21 22

Congestion Control by TCP TCP Congestion Control Concept (1)

Autonomous control by end-nodes. Primary concept
° There is no way for TCP to determine the network condition
° No central control exactly.
Simple estimation algorithms for network ° TCP regards ALL packet losses as congestion.

conditions. Transmission control with simple algorithms.

° If packets are NOT lost..
° Selects appropriate transfer rate for each network. • TCP assumes network is NOT congested $B"* (B Increases
• Avoid congestion as much as possible. transfer rate.
° If packets are lost..
° Detects congestion
• TCP assumes network is congested $B"* (B Decreases transfer
• Avoid congestion collapse as much as possible. rate.

° TCP increases transfer rate until packet loss occurs.

• TCP tries to estimate the limit of the network by causing packet loss.

23 24

4
TCP Congestion Control Concept (2) TCP Congestion Control Concept (3)
How to control transfer rate? Self-Clocking
° Uses an arrival of ACK as a trigger of new packet transmission.
° Introduces new variable "congestion window (cwnd)"
• Packet arrval interval will change according to the characteristics of
in sliding window scheme. the transit networks.
° Adjusts the amount of data being injected into the ° Adjusts transfer rate to the network capacity automatically.
networks • No need for complex mechanism for controlling transfer rate!

How to determination Window Size?

° Window Size = min(advertised window, congestion
window)
• Advertised Window is used for flow control, which is sent
from receiver side.
• Congestion Window is used for congestion control, which is
decided on sender side.

25 26

History of TCP Congestion Control Tahoe TCP

3 major versions of TCP congestion control Two major congestion control schemes
° TCP congestion control scheme has been deployed with BSD ° Slow-Start and Congestion Avoidance
Unix.
• Increases Window Size
° Tahoe
• Implemented in 4.3BSD Tahoe, Net/1 (around 1988) ° Fast Retransmit
• Slow Start and Congestion Avoidance • Detects congestion
• Fast Retransmit
° Reno
• Implemented in 4.3BSD Reno, Net/2 (around 1990)
• Fast Recovery after Fast Retransmit
° NewReno
• No reference implementation (around 1996)
• New Fast Recovery Algorithm

27 28

Slow-Start and Congestion Avoidance (1) Slow-Start and Congestion Avoidance (2)
Two communication phases for increasing congestion Transition from Slow-start to Congestion Avoidance
window TCP keeps a variable "ssthresh" to determine which
Slow Start algorithms are used.
° Used at the beginning of a transfer, or after timeout. ° If cwnd < ssthresh then do slow-start
° Starts from minimum window size ° If cwnd > ssthresh then do congestion avoidance
° Increases congestion window size by MSS bytes for each ACK Algorithms for "ssthresh"
received.
° Initial value: arbitrarily high value (ex. advertised window siz e)
° Increases window size exponentially ° When TCP detects packet loss, it will be set to cwnd/2.
Congestion Avoidance
° Increases congestion window size by MSS / cwnd bytes for each
ACK received.
° Increases window size linearly

29 30

5
Slow-Start and Congestion Avoidance (3) Slow-Start and Congestion Avoidance (4)
cwnd variation of Tahoe TCP Goal of slow -start and congestion avoidance
° Keep window size around optimal size as much as
possible.
° Slow-Start
• Increase window size rapidly to reach maximum safety
transfer rate as fast as possible.
• Maximum safety transfer rate:
– Half of the transfer rate that caused packet loss

° Congestion Avoidance
• Increase window size slowly to avoid packet losses as long
as possible

31 32

Fast Retransmit (1) Fast Retransmit (2)

Retransmit packets without waiting for retransmission ° TCP cannot determine whether duplicate ACK is generated by
packet loss or packet disorder.
timeout
° But TCP assumes that 3 successive duplicate ACKs are caused
Fast retransmit uses "duplicate ACK" to trigger by packet loss.
retransmission packets.
° Duplicate ACK:
• ACKs that are the same as previous ACK
• Duplicate ACKs are generated by packet loss or packet disorder.

33 34

Reno TCP Fast Recovery (1)

Performance improvement for Tahoe TCP. Problem of Tahoe TCP
° Window Size is set to minimum value after packet loss.
° Tahoe TCP is very sensitive to packet loss.
° 1% packet loss rate may cause 50-75% decrease in
throughput
Introduced the "Fast Recovery" algorithm.
° Recovers transfer rate quickly after packet loss

Congestion estimation by Tahoe TCP

° Every packet loss is assumed to be serious congestion.
35 36

6
 Fast Recovery (2) Fast Recovery (3)
Congestion estimation by Reno TCP Example of cwnd variation of Reno TCP
° If packet loss was found by Retransmit Timeout,
• Congestion is serious.
– Windowsize should be set to minimum value and do Slow-start.

° If packet loss was found by Duplicate ACK,

• Congestion is not serious.
• Because..
– At least 3 packets could arrive at the receiver after packet loss.
– At least 3 packets have left the network, so there may be a
chance to transmit a packet
• So, Window Size is set to half of the current value and
transits to Congestion Avoidance phase. ° After packet loss, TCP halves congestion window and enters
Congestion Avoidance phase.

37 38

Problem of Reno TCP NewReno TCP

If two or more segments are lost in the current Performance improvement for Reno TCP.
window, Fast Recovery algorithm cannot ° Improves performance against multiple packet loss in
retransmit all lost packets. the window.
° TCP has to wait for retransmit timeout. ° Does not need Selective ACK.
Selective ACK option can solve this problem, but ° Requires modification to only data sender.
it has not been widely implemented yet. NewReno is a bit more aggressive scheme than
° Selective ACK requires a modification to both data Reno.
sender and receiver. ° Reno retransmit packets in response to either
retransmit timeout or 3 duplicate ACKs.

39 40

Congestion Control with routers ICMP Source Quench

Advantage for using routers If router finds that network is congested, router sends back "ICMP
Source Quench" message to the data sender.
° End nodes can only determine congestion by sensing packet
losses. ° Data sender should set window size to minimum after receiving Source
Quench.
° Router knows more about congestion than end nodes ° Cons.
• If queue length in the router exceeds a certain threshold, we can
• More traffic is generated in times of congestion.
assume network is becoming congested.
° Pros.
• But, how do the routers tell the end nodes?
• Can tell occurrence of congestion quickly.
ICMP source quench
Explicit Congestion Notification (ECN)

41 42

7
Explicit Congestion Notification (ECN) Part 3: Simulating TCP
If router finds that network is congested, router marks "ECN bit" in Why simulation is necessary?
the IP header.
° Data receiver sends back "ECN echo" after receiving ECN packets. ° Analyze theoretical aspects
° Data sender should set window size to minimum after receiving ECN ° Can perform experiments easily rather than
echo.
configuring real networks.
• Cons.
– ECN is a bit slower than Source Quench. ° Easy to implement new functions
• Pros. • Does not require the knowledge of kernel coding
– Can find congestion before packet loss occurs
– Does not add any traffic in the networks

43 44

Network Simulator (1) Network Simulator (2)

ns: Network Simulator nam: Network Animator
° http:// www.isi.edu/nsnam/ns/ ° http://www.isi.edu/nsnam/nam/
° Can be used on major OSs (Linux, FreeBSD, NetBSD ,
Windows...) ° Can visualize output of ns simulator
° Supports lots of networking technologies
• Application-level protocols
– HTTP, telnet, FTP
• Transport protocols
– UDP, TCP, RTP, SRM
– Supports various TCP versions: Tahoe, Reno, NewReno..
• Router Mechanisms
– Various queuing mechanism: CBQ, RED, ECN
• Link-layer mechanisms
– CSMA/CD
° High extensibility
• Lots of protocol functions are provided as C++ object class 45 46

Summary
TCP provides a reliable service between end-nodes.
° Packet Retransmission based on Acknowledgment
TCP plays an important role in congestion control in the
Internet.
° Autonomous Control by end-node
• Simple estimation for network condition

Congestion Control is one of the important topics for the

future of the Internet.
° TCP is NOT the perfect solution, but provides some essential
hints.

47