Transcript Chapter 5: End-to

CSS432 End-to-End Protocols
Textbook Ch5.1 – 5.2
Instructor: Joe McCarthy
(based on Prof. Fukuda’s slides)
CSS432: End-to-End Protocols
1
Overview
Utilize host-to-host packet delivery service (network layer) to provide a
process-to-process communication channel (transport layer)
segments
packets
frames
bits
CSS432: Internetworking
2
http://www.tcpipguide.com/free/t_TCPDataHandlingandProcessingStreamsSegmentsandSequ-2.htm
CSS432: Internetworking
3
IP Protocol

Underlying “best-effort” network






May drop messages
May re-order messages
May deliver duplicate copies of a given message
May deliver messages after an arbitrarily long delay
Limits messages to a finite size
IP addresses (globally unique)
Request a retransmission of M3 and M5
M5, and M3
M5, M5, M3
M5, M4, M3, M2, M1
M5
M5, M2, M1
M4, M3
M2, M1, M4
M4
M3
CSS432: End-to-End Protocols
4
End-to-End Protocols

Common end-to-end services







support multiple application processes on each host
guarantee message delivery
deliver messages in FIFO order
deliver at most one copy of each message
support arbitrarily large messages
support synchronization
allow the receiver to flow control the sender
P1
P2
P3
P4
M5, M4, M3, M2, M1
Network
m5, m4, m3, m2, m1
CSS432: End-to-End Protocols
5
Simple Demultiplexor (UDP)






User Datagram Protocol
Adds multiplexing
Unreliable & unordered
No flow control
Endpoints identified by ports
 servers have well-known ports
 see /etc/services on Unix
Optional checksum
 UDP header + data +
pseudoheader
(Src & Dst IP addrs, protocol #)
CSS432: End-to-End Protocols
6
TCP Overview


Connection-oriented
Byte-stream
 app writes bytes
 TCP assembles &
sends segments
 app reads bytes



Full duplex
Flow control: keep sender from
overrunning receiver
Congestion control: keep sender
from overrunning network
CSS432: End-to-End Protocols
7
Transport vs. Data Link Layer
CSS432: End-to-End Protocols
8
Transport vs. Data Link Layer





Potentially connects many different hosts
 need explicit connection establishment and
termination
Potentially long delay in network
 need to be prepared for arrival of very old packets
 need to set MSL (Maximum Segment Lifetime)
Potentially high variation in RTT (Round Trip Time)
 need adaptive timeout mechanism
Potentially different capacity at destination
 need to accommodate different node capacity
Potentially different network capacities
 need to be prepared for network congestion
CSS432: End-to-End Protocols
9
TCP Segment Format

0
10
4
16
31
SrcPort

DstPort
Each connection identified with 4-tuple:
 (SrcPort, SrcIPAddr,
DstPort, DstIPAddr)
Sliding window + flow control
 Acknowledgment, SequenceNum,
AdvertisedWinow
SequenceNum
Data(SequenceNum)
Acknowledgment
HdrLen
0
Flags
Sender
Receiver
Adv ertisedWindow

Checksum
UrgPtr
Flags


Options (v ariable)


Data



CSS432: End-to-End Protocols
Acknowledgment +
AdvertisedWindow
SYN: Establish a connection
FIN: terminate a connection
RESET: Confused, terminate
PUSH: Section 5.2.7
URG: Sending urgent data
ACK: Validating
acknowledgment field
SequenceNum is incremented in
all cases other than ACK.
10
TCP Connection Establishment

3-Way Handshake

Client



Server




Acknowledge the server
request with ACK=y+1
x and y are chosen at
random

CSS432: End-to-End Protocols
Acknowledge the client
request with ACK=x+1
Initiate a reverse
connection with SeqNum=y
Set a timer and retransmit
the request upon an
expiration
Client


Initiate a connection to a
server with SeqNum=x
Set a timer and retransmit
the request upon an
expiration
Protect against two
incarnations of the same
connection using the same
sequence number.
11
TCP Connection Tear-Down

3-Way Handshake




Initiator: FIN
Receiver: ACK/FIN
Initiator: ACK
“Half-open” connection





Receiver (of FIN) may still
have data to send
Acknowledges FIN
Keeps sending data
Sends its own FIN
Receiver acknowledges
http://en.wikipedia.org/wiki/Transmission_Control_Protocol
CSS432: End-to-End Protocols
12
State Transition Diagram
CLOSED

Active open/SYN
Passive open
Close
Open
 Active open
Close


LISTEN

SYN_RCVD
ACK

SYN_SENT
SYN + ACK/ACK


Close/FIN
Passive open

SYN/SYN + ACK
Send/SYN
SYN/SYN + ACK
ESTABLISHED
FIN/ACK
FIN_WAIT_1

CLOSE_WAIT

FIN/ACK
ACK
Close/FIN
FIN_WAIT_2
CLOSING
FIN/ACK
LAST_ACK
ACK Timeout after two
segment lifetimes
TIME_WAIT (2 * MSL)
ACK
CLOSED
CSS432: End-to-End Protocols
A server
listen()
Can change active
Close
 Active close

Close/FIN
A client
connect()

A client or a server
First close()
Both side can be
active
Passive close


A client or server
close() in response to
the first close()
13
Client
Server
( connect( ) ) SYN_SENT
LISTEN ( listen( ) )
SYN_RCVD
ESTABLISHED
Establishment
Timing Chart
ESTABLISHED
( read( ) )
Data
Transfer
( write( ) )
CLOSE_WAIT
FIN_WAIT_2
LAST_ACK( close( ) )
TIME_WAIT
You may see this with tcpdump in assignment 3.
CSS432: End-to-End Protocols
Termination
( close( ) ) FIN_WAIT_1
14
CSS432: Internetworking
15
http://www.tcpipguide.com/free/t_TCPOperationalOverviewandtheTCPFiniteStateMachineF-2.htm
CSS432: Internetworking
16
http://www.tcpipguide.com/free/t_TCPConnectionTermination-2.htm
CSS432: Internetworking
17
http://www.tcpipguide.com/free/t_TCPConnectionTermination-2.htm
CSS432: Internetworking
18
http://www.tcpipguide.com/free/t_TCPConnectionTermination-4.htm
CSS432: Internetworking
19
http://www.tcpipguide.com/free/t_TCPConnectionTermination-4.htm
CSS432: Internetworking
20
Sliding Window Revisited
Sending application
Receiving application
TCP
TCP
LastByteWritten
LastByteAcked

Sending side
LastByteRead
LastByteSent
NextByteExpected

LastByteRcvd
Receiving side

LastByteAcked
≤
LastByteSent
≤
LastByteWritten

buffer bytes between
 buffer bytes between
[LastByteAcked, LastByteWritten]
[LastByteRead, LastByteRcvd]

LastByteRead
<
NextByteExpected
≤
LastByteRcvd + 1
CSS432: End-to-End Protocols
21
http://www.tcpipguide.com/free/t_TCPSlidingWindowAcknowledgmentSystemForDataTranspo-6.htm
CSS432: Internetworking
22
Flow Control
0
10
4
16
31
SrcPort
DstPort
SequenceNum
Acknowledgment
Receiving application
Sending application
0
HdrLen
Flags
Adv ertisedWindow
Checksum
UrgPtr
Options (v ariable)
TCP
TCP
LastByteWritten
Data
LastByteRead
y
LastByteSent
LastByteAcked
NextByteExpected LastByteRcvd
LastByteRcvd
– LastByteRead ≤ MaxRcvbuffer
LastByteSent – LastByteAcked
≤
AdvertisedWindow
EffectiveWindow
= AdvertisedWindow
– (LastByteSent
– LastByteAcked)
LastByteWritten
– LastByteAcked ≤ MaxSendBuffer
block sender if
(LastByteWritten - LastByteAcked) + y > MaxSendBuffer
AdvertisedWindow
= MaxRcvBuffer
– ( (NextByteExpected – 1)
– LastByteRead )
Send ACK with an advertise window
in response to arriving data segments
• as long as all the preceding bytes have
also arrived and
• until the advertised window reaches 0.
(ACK returned at the first time when it reaches 0)
CSS432: End-to-End Protocols
23
Flow Control with a Slower Receiver
Receiving application
Sending application
Read slow.
TCP
TCP
LastByteWritten
LastByteRead
y
LastByteAcked
y
LastByteSent
LastByteRcvd =
NextByteExpected - 1
LastByteSent – LastByteAcked
LastByteRcvd – LastByteRead ≤ MaxRcvbuffer
0
EffectiveWindow
= AdvertisedWindow
– (LastByteSent
– LastByteAcked)
AdvertisedWindow
= MaxRcvBuffer
– ( (NextByteExpected – 1)
– LastByteRead )
=0
LastByteWritten
– LastByteAcked ≤ MaxSendBuffer
No more send, no more ack, thus it stays
In the same value
CSS432: End-to-End Protocols
24
Flow Control
AdvertisedWindow = 0: sender won’t send
any more data.
 Receiver only responds to sender

 Will
not initiate update when
AdvertisedWindow > 0

How can the sender find out when the
receiver can receive more data?
CSS432: End-to-End Protocols
25
Flow Control
AdvertisedWindow = 0: sender won’t send
any more data.
 Receiver only responds to sender

 Will
not initiate update when
AdvertisedWindow > 0

How can the sender find out when the
receiver can receive more data?
 Periodically

send a byte
“Smart sender / dumb receiver”
CSS432: End-to-End Protocols
26
0
Wraparound
16
31
SrcPort
DstPort
SequenceNum
Acknowledgment
HdrLen

10
4
32-bit SequenceNum
0
Flags
Checksum
UrgPtr
Options (v ariable)
 Maximum
Segment Lifetime
(MSL) = 120 seconds
 SequenceNum should not wrap around
within MSL time period
Bandwidth
Time Until Wrap Around
T1 (1.5 Mbps)
Ethernet (10 Mbps)
T3 (45 Mbps)
FDDI (100 Mbps)
STS-3 (155 Mbps)
STS-12 (622 Mbps)
STS-24 (1.2 Gbps)
6.4 hours
57 minutes
13 minutes
6 minutes
4 minutes
55 seconds
28 seconds
CSS432: End-to-End Protocols
Adv ertisedWindow
Data
27
0
Keeping the Pipe Full

16-bit AdvertisedWindow = 64KB
Assuming that RTT = 100msec,
the advertised window’s capacity
x Network bandwidth
16
31
SrcPort
DstPort
SequenceNum
Acknowledgment
HdrLen

10
4
0
Flags
Adv ertisedWindow
Checksum
UrgPtr
Options (v ariable)
Data
Bandwidth
RTT(100msec) x Bandwidth Product
T1 (1.5 Mbps)
Ethernet (10 Mbps)
T3 (45 Mbps)
FDDI (100 Mbps)
STS-3 (155 Mbps)
STS-12 (622 Mbps)
STS-24 (1.2 Gbps)
18KB
122KB
549KB
1.2MB
1.8MB
7.4MB
14.8MB
CSS432: End-to-End Protocols
28
Segment Transmission
Segments are buffered until send triggered:
1.
2.
3.
Buffer reaches Maximum Segment Size (MSS)
= Maximum Transfer Unit (MTU)
– ( TCP header size + IP header size )
TCP invokes a push operation that flushes the
unsent data
When a timer expires
 May precipitate silly window syndrome
CSS432: End-to-End Protocols
29
Silly Window Syndrome
small
MMS 2
MMS 1
Sender
Receiver
Ad Window
Ad Window

Sender aggressively takes advantage of any available window,



The receiver empties every window regardless of its size and thus small
windows will never disappear.
The problem occurs only when

Sender transmits a small segment

Receiver opens the AdvertisedWindow a small amount
What should be done? And who should do it?
CSS432: End-to-End Protocols
30
Silly Window Syndrome
small
MMS 2
MMS 1
Sender
Receiver
Ad Window
Ad Window

Sender aggressively takes advantage of any available window,



The problem occurs only when

Sender transmits a small segment

Receiver opens the AdvertisedWindow a small amount
The receiver could delay ACKs to make a larger window


The receiver empties every window regardless of its size and thus small
windows will never disappear.
How long does it wait?
The sender should make a decision (“smart sender/dumb receiver”)

Nagle’s Algorithm (Programming assignment 3)
CSS432: End-to-End Protocols
31
http://www.tcpipguide.com/free/t_TCPSillyWindowSyndromeandChangesTotheSlidingWindow.htm
CSS432: Internetworking
32

The client's send window is 360, and it has lots of data to send. It
immediately sends a 360 byte segment to the server. This uses up its
entire send window.

When the server gets this segment it acknowledges it. However, it can
only remove 120 bytes so the server reduces the window size from
360 to 120. It sends this in the Window field of the acknowledgment.

The client receives an acknowledgment of 360 bytes, and sees that the
window size has been reduced to 120. It wants to send its data as
soon as possible, so it sends off a 120 byte segment.

The server has removed 40 more bytes from the buffer by the time the
120-byte segment arrives. The buffer thus contains 200 bytes (240
from the first segment, less the 40 removed). The server is able to
immediately process one-third of those 120 bytes, or 40 bytes. This
means 80 bytes are added to the 200 that already remain in the buffer,
so 280 bytes are used up. The server must reduce the window size to
80 bytes.

The client will see this reduced window size and send an 80-byte
segment.

The server started with 280 bytes and removed 40 to yield 240 bytes
left. It receives 80 bytes from the client, removes one third, so 53 are
added to the buffer, which becomes 293 bytes. It reduces the window
size to 67 bytes (360-293).
http://www.tcpipguide.com/free/t_TCPSillyWindowSyndromeandChangesTotheSlidingWindow.htm
CSS432: Internetworking
33
Nagle’s Algorithm
When the application produces new data to send
if both the new data & available window ≥ MSS
send a full segment
// send MSS bytes right now
else if there is unAcked data in transit
buffer new data until an ACK arrives // wait for empty MSS segment
else
send all the new data now
// Can’t avoid silly window syndrome


Ack works as a timer to fire a new segment transmission.
The algorithm may not respond to interactive or real-time
applications

TCP_NODELAY Option: Transmit data as soon as possible

setsockopt(sockfd, SOL_TCP, TCP_NODELAY, &intFlag, sizeof(intFlag))
CSS432: End-to-End Protocols
34
Timeouts

Why timeout?
CSS432: End-to-End Protocols
35
Timeouts & Retransmissions

Timeout required for reliable transmission
 Retransmit
a lost packet
 Detect congestion / invoke congestion control
 But: RTT can vary widely

When to timeout (how long to wait)?
CSS432: End-to-End Protocols
36
Adaptive Retransmission

Timeout required for reliable transmission
 Retransmit
a lost packet
 Detect congestion / invoke congestion control
 But: RTT can vary widely

Timeout using RTT estimation algorithms
 Original
Algorithm
 Karn/Partridge Algorithm
 Jacobson/Karels Algorithm
CSS432: End-to-End Protocols
37
Original Algorithm

Measure SampleRTT for each segment / ACK pair
CSS432: End-to-End Protocols
38
Original Algorithm


Measure SampleRTT for each segment / ACK pair
Compute weighted average of RTT
EstRTT = a x EstRTT + b x SampleRTT
 where a + b = 1
1. a between 0.8 and 0.9 (smoothing function)
2. b between 0.1 and 0.2

CSS432: End-to-End Protocols
39
Original Algorithm


Measure SampleRTT for each segment / ACK pair
Compute weighted average of RTT
EstRTT = a x EstRTT + b x SampleRTT
 where a + b = 1
1. a between 0.8 and 0.9 (smoothing function)
2. b between 0.1 and 0.2


Set timeout based on EstRTT


TimeOut = 2 x EstRTT
Conservative: EstRTT cannot respond quickly to
deviations in SampleRTT
CSS432: End-to-End Protocols
40
Karn / Partridge Algorithm (1987)
CSS432: End-to-End Protocols
41
Karn / Partridge Algorithm (1987)


Do not sample RTT when retransmitting
 Can’t figure out which transmission the latest ACK corresponds to.
Double timeout (vs. EstRTT) after each retransmission
 Exponential backoff
 Congestion most likely cause of lost segments
CSS432: End-to-End Protocols
42
Jacobson / Karels Algorithm (1988)

Original Algorithm
 EstRTT
= a x EstRTT + b x SampleRTT
0.8 and 0.9


0.1 and 0.2
TimeOut = EstRTT * 2
New Algorithm that takes into account
large variations among SampleRTTs

EstRTT = EstRTT + d(SampleRTT – EstRTT)
0.125

Diff
Dev = Dev + d(|SampleRTT – EstRTT| – Dev)
Diff

TimeOut =
m
1
x EstRTT +
f
x Dev
4
CSS432: End-to-End Protocols
43

Reviews
 UDP
 TCP:
three-way handshake and state transition
 Sliding window and flow control
 Segment transmission: silly window syndrome and
Nagle’s algorithm
 Adaptive retransmission: original, Karn/Partridge, and
Jacobson/Karels

Exercises in Chapter 5
 Ex.
5, 14, 22, and 39 (TCP state transition)
 Ex. 9(a) (Sliding window)
 Ex. 20 (Nagle’s algorithm)
CSS432: End-to-End Protocols
44
Exercise 5

When closing a TCP
connection, why is
the two-segment
lifetime timeout not
necessary on the
transition from
LAST_ACK to
CLOSED?
CSS432: Internetworking
45
Exercise 14



If host A receives two SYN packets from the same port
from remote host B, the second may be either a
retransmission of the original or, if B has crashed and
rebooted, an entirely new connection request.
(a) Describe the difference as seen by host A between
these two cases.
(b) Give an algorithmic description of what the TCP
layer needs to do upon receiving a SYN packet.
Consider the duplicate/new cases above and the
possibility that nothing is listening to the destination
port
CSS432: Internetworking
46
Exercise 9(a)


You are hired to design a reliable byte-stream
protocol that uses a sliding window (like
TCP). This protocol will run over a 1-Gbps
network. The RTT of the network is 100 ms,
and the maximum segment lifetime is 30
seconds.
(a) How many bits would you include in the
AdvertisedWindow and SequenceNum fields
of your protocol header?
CSS432: Internetworking
47
Exercise 20




The Nagle algorithm, built into most TCP implementations, requires
the sender to hold a partial segment’s worth of data (even if
PUSHed) until either a full segment accumulates or the most recent
outstanding ACK arrives.
(a) Suppose the letters abcdefghi are sent, one per second, over a
TCP connection with an RTT of 4.1 seconds. Draw a timeline
indicating when each packet is sent and what it contains.
(b) If the above were typed over a full-duplex Telnet connection,
what would the user see?
(c) Suppose that mouse position changes are being sent over the
connection. Assuming that multiple position changes are sent each
RTT, how would a user perceive the mouse motion with and without
the Nagle algorithm?
CSS432: Internetworking
48
Exercise 22

Explain why
TIME_WAIT is a
somewhat more
serious problem if
the server initiates
the close than if the
client does. Describe
a situation in which
this might
reasonably happen.
CSS432: Internetworking
49
Exercise 39

When TCP sends a
SYN, SequenceNum = x or
FIN, SequenceNum = x,
the consequent ACK has
Acknowledgement =
x + 1, i.e., SYNs and FINs each
take up one unit in sequence
number space.
Is this necessary? If so give an
example of an ambiguity that
would arise if the corresponding
Acknowledgement were x
instead of x + 1; if not, explain
why.
CSS432: Internetworking
50
[not used]
CSS432: Internetworking
51
State Transition Diagram

In what condition can the state transit from
FIN_WAIT_1 to TIME_WAIT?

What is the purpose of the TIME_WAIT
state?
CSS432: End-to-End Protocols
52
Jacobson/ Karels Algorithm
EstimatedRTT = 8 EstRTT
Deviation = 8 Dev
SampleRTT = (SampleRTT – 8 EstRTT) / 8
= SampleRTT – EstRTT)
SampleRTT –= (EstimatedRTT >> 3)
EstimatedRTT += SampleRTT;
If (SampleRTT < 0)
diff
SampleRTT = – SampelRTT;
8 EstRTT = 8EstRTT + SampleRTT
= 8EstRTT + (SampleRTT – EstRTT)
EstRTT = EstRTT + 1/8 (SampleRTT – EstRTT)
SampleRTT –= (Deviation >> 3);
Deviation += SampleRTT;
diff
TimeOut = (EstimatedRTT >> 3) + (Deviation >> 1)
|SampleRTT – EstRTT| – 8Dev/8
|diff|

Notes
 Algorithm does not work accurately
with a large granularity of clock
(500ms on Unix)
 Accurate timeout mechanism
important to congestion control
8 Dev = 8 Dev + |SampleRTT – EsRTT| - Dev
Dev = Dev + 1/8( |SampleRTT – EstRTT| - Dev )
TimeOut = 8 EstRTT / 8 + 8 Dev / 2
TimeOut = EstRTT + 4 Dev
CSS432: End-to-End Protocols
53
UDP: Simple Demultiplexer
int sd;
sd = socket(AF_INET, SOCK_DGRAM, 0);
socket()
socket()
struct sockaddr_in server;
struct hostent *hp, *gethostbyname( );
Server.sin_family = AF_INET;
hp = gethostbyname( );
bcopy( hp->h_addr, &( server.sin_addr.s_addr ),
sizeof( hp->h_length) );
server.sin_port = htons( 13579
12345 );
sendto( sd, buf, sizeof( buf ), 0,
(struct sockaddr *)&server,
sizeof( server ) );
socket()
struct sockaddr_in server;
server.sin_family =AF_INET;
server.sin_addr.s_addr = htonl( INADDR_ANY)
13579 );
server.sin_port = htons( 12345
bind( sd, (struct sockaddr *)&server,
sizeof( server ) );
bind()
bind()
Port:12345
Port: 13579
recv( sd, buf, sizeof( buf ), 0 );
recv()
recv()
sendto()
Packets
demultiplexed
UDP
M5, M4, M3, M2, M1
CSS432: End-to-End Protocols
54
Sockets (Code Example)
int sd = socket(AF_INET, SOCK_STREAM, 0);
socket()
int sd, newSd;
sd = socket(AF_INET, SOCK_STREAM, 0);
socket()
socket()
sockaddr_in server;
bzero( (char *)&server, sizeof( server ) );
struct hostent *host = gethostbyname( arg[0] );
server.sin_family =AF_INET;
sockaddr_in server;
server.sin_addr.s_addr = htonl( INADDR_ANY )
bzero( (char *)&server, sizeof( server ) );
server.sin_port = htons( 12345 );
server.sin_family = AF_INET;
bind( sd, (sockaddr *)&server,
server.s_addr =
sizeof( server ) );
inet_addr( inet_ntoa(
*(struct in_addr*)*host->h_addr_list ) ); bind()
server.sin_port = htons( 12345 );
listen( sd, 5 );
connect( sd, (sockaddr *)&server,
listen()
sizeof( server ) );
sockaddr_in client; socklen_t len=sizeof(client);
connect()
connect()
while( true ) {
newSd = accept(sd, (sockaddr *)&client, &len);
accept()
write( sd, buf1, sizeof( buf ) );
write( sd, buf2, sizeof( buf ) );
write()
write()
buf2, buf1
if ( fork( ) == 0 ) {
close( sd );
read( newSd, buf1, sizeof( buf1 ) );
read( newSd, buf2, sizeof( buf2 ) );
buf2, buf1
close( newsd);read()
exit( 0 );
read()
}
close( newSd );
}
CSS432: End-to-End Protocols
55