Slide 1
Structure of a TCP segment
1
Comer 2000: fig 13.7
SOURCE PORT
DESTINATION PORT
CHECKSUM
CMPT 471
Networking II
Review of TCP
The transport layer
2
© Janice Regan, 2012
The pseudo header: UDP, TCP
The pseudo header is not transmitted, it is independently constructed at the original source and the final destination.
3
© Janice Regan, 2012
The pseudo header: UDP, TCP
The constructed pseudo header is prepended to the TCP segment or UDP packet before the checksum is calculated
The pseudo header is used to check that the segment has arrived at the correct address on the correct connection
Protocol can be TCP (6) or UDP (17)
Length is the length of the TCP segment including the TCP header or the UDP packet including header
4
© Janice Regan, 2012
Header + Pseudoheader
The TCP or UDP Header is transmitted with the datagram. The Pseudoheader is not transmitted.
The checksum is the ones complement sum of all the 16 bit words in the datagram (data header and pseudoheader)
Information in the pseudoheader is calculated from information in the header, and from the IP address of the source and receiver from the IP layer (encapsulation?)
5
© Janice Regan, 2012
CheckSum
The checksum for a TCP segment is calculated in the same manner as the checksum for a UDP packet
The fields in the TCP or UDP header and pseudo header are divided into 16 bit words. These 16 bit words start on all 16 bit boundaries in the pseudo header the header and the data
A ones complement sum of all the 16 bit words in the packet header, the data, and the packet pseudo header is calculated
While this sum is being calculated the contents of the checksum field in the TCP header is set to 0
The ones complement of the ones complement sum is inserted into the checksum field
6
© Janice Regan, 2012
CheckSum
The checksum for a TCP segment is calculated in the same manner as the checksum for a UDP packet
The fields in the TCP or UDP header and pseudo header are divided into 16 bit words. These 16 bit words start on all 16 bit boundaries in the pseudo header the header and the data
A ones complement sum of all the 16 bit words in the packet header, the data, and the packet pseudo header is calculated
While this sum is being calculated the contents of the checksum field in the TCP header is set to 0
The ones complement of the ones complement sum is inserted into the checksum field
7
© Janice Regan, 2012
the ones complement sum (1)
To find the ones complement sum of a series of binary numbers
Do a binary addition 1110001110001110
0101010101010101
10011100011100011
Shift the sum 16 places to the right (gives 1 for this example)
8
© Janice Regan, 2012
© Janice Regan, 2013
9
Reliable underlying network: 1
Allow each end to know the other exists
Negotiate of optional parameters (segment size, window size, QoS)
Allocation of transport entity resources (buffer space, entry in connection table)
Need ESTABLISHED (open), CLOSED, and ‘half open’ states. Process must be ‘listening’ to accept a connection
Need two types of messages (socket subroutine calls)
SYN: specifies initial sequence numbers for synchronization
FIN: indicates no more data to send, requesting termination
© Janice Regan, 2013
10
Reliable underlying network (2)
‘half open’ states occur when opening or closing a connection
connection requested and not yet established (SYN SENT) (waiting for response SYN)
ready to accept connections no request received yet (LISTEN) (waiting for initiating SYN, will immediately respond with response SYN)
Close requested, data flow from requesting endpoint is complete (FIN WAIT) (waiting for response to sent FIN)
Close request received, data flow from endpoint receiving close request continues until completion (CLOSE WAIT) (waiting to respond to close request, FIN)
© Janice Regan, 2013
11
Connection State Diagram
Stallings 2003: Figure 20.3
© Janice Regan, 2013
12
Connection Establishment
Stallings 2003: Figure 20.4
© Janice Regan, 2013
13
Unreliable Network Service
PROBLEMS
Solved by using sliding windows and credit scheme already discussed
Segments may get lost, need retransmission strategy
Duplication detection
Flow control
Segments may arrive out of order, transport layer must deliver in order to application (solution unique sequence numbers)
Connection establishment / termination (replace two way handshake with three way handshake to deal with losses, duplications)
© Janice Regan, 2013
14
Unreliable underlying network
Must add additional states to the diagram
When opening need a SYN RECEIVED state to be in while waiting for the ACK of the SYN sent in response to the SYN sent by the initiating station
When closing in passive mode need a LAST ACK state to be in while waiting for the ACK of the FIN sent in response to the received FIN
© Janice Regan, 2013
15
Connection Establishment
Lost or delayed data segments can cause connection problems if the previously discussed 2-way handshake is used
Cannot assume sent SYN or FIN reaches destination
Arriving SYN or FIN could be from an old connection attempt
Solve by using a three way handshake (must ACK receipt of FIN or SYN) and start segment numbers (SYNi, ACKi, FINi) far removed from those used by previous connections
© Janice Regan, 2013
16
Unreliable underlying network
Must add additional states to the diagram
When opening need a SYN RECEIVED state to be in while waiting for the ACK of the SYN sent in response to the SYN sent by the initiating station
When closing in passive mode need a LAST ACK state to be in while waiting for the ACK of the FIN sent in response to the received FIN
© Janice Regan, 2013
17
Unreliable underlying network
When closing in active mode need
FIN WAIT2 state to be in while waiting for the station receiving the close request (the first FIN) to complete transmission and send response FIN. The ACK of the first FIN is received before entering this state
CLOSING state to be in while waiting for the ACK to the response FIN. The response FIN has already been received before entering this state
© Janice Regan, 2013
18
Three Way Handshake
Stallings 2003: Figure 20.3
© Janice Regan, 2013
19
Three Way Handshake:
Stallings 2003: Figure 20.3
the ones complement sum (2)
Add the shifted value (1 in this case) to the binary sum
10011100011100011 + 1 = 10011100011100100
Take the least significant 16 digits to give the ones complement sum
0011100011100100
The ones complement of this ones complement sum is the checksum 1100011100011011
20
© Janice Regan, 2012
Flow control + Error control
Flow Control
Control flow of data from source to receiver
Source sends at a particular rate (frames/sec)
Receiver must be able to receive and process data at that rate (rate must be controlled)
Error control
How to recover when a frame is damaged or lost in transmission
21
© Janice Regan, 2012
Stop and Wait: Error free
Packets arrive at destination in the same order they are sent
22
Error free transmission
Send F2
Send F3
Send F1
Send F0
Send ACK1
Send ACK2
Send ACK3
RTT
T
I
M
E
© Janice Regan, 2012
Stop and Wait Flow Control
Source entity (sender) transmits frame and starts a timer
Destination entity (receiver) receives frame
Destination entity sends ACK
Source entity receives ACK and stops timer
Source entity is now ready to start the cycle again for a new frame
If timer expires first four steps above are repeated for the same frame
23
© Janice Regan, 2012
TCP and Flow Control
For a point to point a physical connection
Know the approximate round trip delivery time through that connection
All packets travel on the same link, packets will arrive in order unless lost, damaged or retransmitted due to errors
How are these methods different when applied to reliable end to end transmission in the transport layer
Difficult to estimate round trip travel time
Packets may take many different paths through the network
Packets may arrive in a different order from the order they were sent even in a error free network
24
© Janice Regan, 2012
Choosing timer durations
A good estimate of round trip travel time (RTT) can be measured in the data link layer (direct link)
The duration of the timer (RTO) will be set a value larger than the RTT,
RTO = RTT + Δ
The duration, Δ, is long enough to include any extra delays due to queuing delays at the source or receiver and waits for processing or transmission due to load of host at endpoint of connection
25
© Janice Regan, 2012
Choosing timer durations
Determining a good estimate for RTT for TCP packets traveling through an internet is more difficult
RTTs have larger variations due to path differences between different packets, network congestion, …
Δ values are a problem, large values lead to extra waiting time (and more retransmission) in case of a lost packet, small values lead to retransmissions of packets that have not be lost
26
© Janice Regan, 2012
Determining RTT
Round trip travel time of a TCP segment through the internet can vary widely due to changes in network topology and load
A fixed RTT is not adequate
Must determine an estimate of RTT that is adaptive to network conditions
Use Jacobson’s technique with Karn’s algorithm (discussed in 371)
27
© Janice Regan, 2012
round trip travel time
Predict future RTTs by sampling past RTTs
Average the samples into a “smoothed” round-trip time estimate SRTT (an exponential average):
SRTT(i+1) = α * SRTT(i) + ( 1-α ) RTT(i+1)
= (1-α) * SRTT(i+1) + α( 1-α ) SRTT(i)+… +
αK(1-α ) SRTT(1)
α is a constant between 0 and 1 that controls how rapidly the SRTT adapts to changes.
α large indicates the old value dominates the estimate of SRTT, short term changes are filtered out
α small indicates the new value dominates the estimate of SRTT
28
© Janice Regan, 2012
When does retransmission occur
What causes retransmission
Changes in network state
If RTT increases due to congestion, using old RTT leads to expiry of timer and retransmission.
If RTT decreases when congestion abates, using old RTT leads to long waiting times for retransmission (reduced by fast retransmit)
Frames or acknowledgements Lost / damaged due to transmission errors
29
© Janice Regan, 2012
Stop and Wait
Possible problems caused by errors
Damaged frame (corrupted data)
Lost frame (not received)
Damaged / Lost ACK
Reception of duplicate frames
Reception of duplicate ACKs
30
Transmission with losses and errors
Send F1
Send F0
Send F0
Send F1
Send F1
Send F0
Send ACK0
Send ACK0
delayed
Send ACK1
Send ACK1
*
Send ACK0
Send F1
*
Send ACK1
© Janice Regan, 2012
Measuring RTT
Subtract the time the packet was sent from the time the ACK was received
When do problems occur
For retransmitted packets, measure from first of second transmission of packet? ambiguous
Measuring from original transmission RTT too large
Measuring from second transmission RTT too small
Just don’t use the packets in the average (Karn)
31
© Janice Regan, 2012
Determine timeout duration
The retransmission timeout RTO is the amount of time the sender will wait for the ACK of the TCP segment sent
Early implementations multiplied the duration of the SRTT by a factor β to give the timeout
RTO(i) = β * SRTT(i) (smoothed RTT)
For systems with small variation in RTT measurements this worked well with β=2
For systems with larger variation in RTT β needed to be larger
Most up to date implementation use an approach know as Jacobsen’s technique, which works even estimates the RTO in systems with higher variation between RTTs (without making β large)
32
© Janice Regan, 2012
Next?
With a ‘reasonable’ estimate of round trip travel time it is time to consider flow control (and error control) in more detail
Simple stop and wait flow control is not efficient.
How does TCP/IP deal more efficiently with flow control
Sliding windows (with credit allocation) to deal with lost / damaged frames and ACKs
Congestion control (congestion window)
33
© Janice Regan, 2012
More Efficient Flow Control
For stop and wait flow control much of the capacity of the link is wasted
The link would be 100% utilized if the source transmitted continuously
If the source transmits a short packet and then waits for an ACK, the portion of the RTT spent waiting for the ACK after transmission is complete is “wasted”
We can minimize the “wasted” time by transmitting more data during each RTT
Larger packets
More packets
34
© Janice Regan, 2012
Larger Packets /More Packets
The disadvantages of larger packets are
More data to be retransmitted when a packet is retransmitted due to an error
Higher probability that a packet will contain an error (more bits that may be in error)
Less “fair” other users must wait longer from their packets to be transmitted because yours are longer. All users wait longer for their own turn
The disadvantage of smaller packets
More overhead, same header and trailer added to every packet
Smaller packets seem to win, so choose more packets rather than larger packets
35
© Janice Regan, 2012
What is a sliding window
The length of the sliding window indicates how much data can be received (at receiver) or sent (at source) before an ACK is received by the source from the receiver
Consider that we have a buffer that can hold a particular amount of data (number of packets or octets)
The senders buffer holds the amount of data that can be sent before an acknowledgement from the receiver is received
The receivers buffer holds the same amount of data. As packets arrive they are inserted into the correct part of the buffer (remember they may arrive out of order)
Think of the buffer as a window on the data stream, this window can slide along the data stream as receipt of data is acknowledged. The data we see through the window is waiting to be sent and/or acknowledged
36
© Janice Regan, 2012
Sliding Window Flow Control
37
F0
F1
F2
F4
F5
ACK1
ACK4
ACK6
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
F3
ACK2
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
ACK5
© Janice Regan, 2012
When to send an ACK
The receiver has to choose when to send an ACK for a particular packet
Send as soon as packet has been received, anticipating availability of buffer space
If data must be processed and receiving host is busy it is possible that additional data will arrive before the present data can be processed and removed from buffer
Send after received data is processed and buffer space is actually available
If receiving host is busy ACK may arrive at host after retransmission timer has expired
The choice is more difficult when there is a large variation in RTT (transport layer).
Variation of travel time adds to variations caused by processing time
38
© Janice Regan, 2012
Credit allocation mechanism
The choice of when to ACK a packet can be addressed by using a credit allocation mechanism which separates acknowledgement of receipt from moving the sliding window
Each ACK contains two values
One indicates the next packet expected
One indicates the amount the sliding window can be moved
An ACK can be sent immediately after receipt of a packet, the sliding window need not be moved at the same time.
When the receiver can handle additional data, an additional ACK can be sent to move the window
39
© Janice Regan, 2012
Sliding window:
Send/receive ACKm without credit allocation
After the receipt of ACKm
the start of source window slides to the right to the beginning of packet m. All packets up to packet m-1 have been successfully received and need not be kept in source buffer
After sending ACKm the receiver location of window is unchanged
The received data has not been processed, there is not room for an additional frame in the receiver buffer
40
© Janice Regan, 2012
Sliding window:
ACKm with credit allocation of n packets
After the receipt of the ACKm the right end of source window slides to the right n packets, the left end slides to the beginning of packet m
If an ACKm without credit allocation has already been received then the left end of the source window need not be moved
After sending the ACK the receiver window (both ends) slides to the right n packets
41
© Janice Regan, 2012
Sliding window: credit allocation
Changes to the source window happen after ACK is received, changes to the receiver window happen after the ACK is sent
An ACK can combine acknowledgement of any number of packets ending with packet m with granting credit for n packets (for any n>=0)
All frames of data in transit must be buffered in the sliding window at the source until their ACK from the receiving station arrives at the sending station.
42
© Janice Regan, 2012
Sliding Window with credit allocation
43
F0
F2
F3
F4
F5
ACK1
CRED0
ACK6
CRED2
ACK3
CRED0
F6
F7
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
F1
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
ACK2
CRED1
ACK4
CRED0
ACK5
CRED3
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
ACK7
CRED2
© Janice Regan, 2012
Fast Retransmit
For sliding windows flow control we waited for a timer to expire before beginning retransmission of a packet
TCP uses an additional mechanism based on cumulative acknowledgement to reduce the wait time for retransmission
This fast retransmit mechanism keeps track of the retransmitted cumulative ACKs arriving at the source.
If the same cumulative ACK arrives four times (three retransmissions), indicating that there is missing data at the destination then the source automatically retransmits the packet starting with the next octet expected by the receiver.
44
© Janice Regan, 2012
Sliding Window: fast retransmit
45
F0
F2
F3
F4
F5
ACK1
CRED1
ACK1
CRED0
ACK1
CRED0
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
F1
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
ACK1
CRED0
ACK1
CRED0
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
ACK1
CRED0
F6
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
F1
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
5
6
7
0
1
2
3
4
5
6
0
1
2
3
4
7
0
ACK7
CRED6
© Janice Regan, 2012
What next?
Now we know how flow control deals with segments lost/damaged in transit.
How do we identify a TCP segment as an ACK or a ‘packet’ carrying data?
TCP segments can have variable sizes. How do we manage the sliding window when segments (packets) vary in size?
46
© Janice Regan, 2012
Structure of a TCP packet
47
Comer 2000: fig 13.7
HLEN
OPTIONS (IF ANY)
CODE BITS
TCP Header Length (HLEN)
The header length (measured in 4 octet blocks) is required because the header length is variable, depending on the length of the options field
The options field contains option information
Controls options setup when the connection is made
specification of maximum segment size (MSS)
window scale (increase advertised window size)
Timestamp used when sequence numbers may wrap around during the lifetime of a connection or in measurement or round trip travel times
If the length of the options information is not a multiple of 32 bits the padding field is used to extend it to a multiple of 32 bits. Maximum length is 60 octets
48
© Janice Regan, 2012