Transport
layer emphasizing TCP and UDP
Transport
layer provides, minimally, process-to-process (e.g. client
application-to-server application) communication.
For
Internet communication, this involves:
(a)
getting the PDU from the sender’s machine to the receiver’s machine –IP, the
network layer, does this.
(b)
once PDU arrives at receiver, delivering it to the correct process – TCP and
UDP both do this.
·
Recall
that PDU is Protocol Data Unit.
·
IP
provides unreliable service: its PDU is the datagram.
·
Transport
layer PDU is the segment.
·
The
only “value added” by UDP is delivery to the process if the IP datagram arrives
at receiver.
·
TCP,
in addition to delivery, provides a substantial added value: reliable transport
service.
For
Internet, this is provided by TCP, because IP does not provide it.
Complexity
of protocol for reliable delivery depends on underlying assumptions. The fewer the assumptions, the more
complex. Several are explained in
detail below.
Both
TCP and UDP provide this service
Header
contains two 16-bit fields:
(a) source port #
(b) destination port #
Scenario
1: simple exchange between client and server.
1.
server
is up and running and listening on port X.
2.
client
initiates contact, sends segment with destination port X, source port Y
(selected automatically from pool of unused ports)
3.
segment
arrives at server machine, destination port is read, and delivered to the process running on port X (the server
process).
4.
server
formulates response, sends segment with destination port Y, source port X.
5.
segment
arrives at client machine, destination port is read, and delivered to the process running on port Y (the client
process).
6.
client
formulates response, sends segment with destination port X, source port Y.
7.
etc.
Scenario
2: two clients on same machine to same server
(e.g. two browser windows).
1.
server
is up and running and listening on port X.
2.
client1
initiates contact, sends segment with destination port X, source port Y1
(selected automatically from pool of unused ports).
3.
client2
initiates contact, sends segment with destination port X, source port Y2
(selected automatically from pool of unused ports).
4.
segment
arrives at server machine, destination port is read, and delivered to the
process running on port X (the server process). Segment could be from either client1 or client2.
5.
server
formulates response, sends segment with destination port Y1 or Y2 (depending on
source port of incoming segment), source port X.
6.
segment
arrives at client machine, destination port is read, and delivered to the
process running on whichever port is specified in source port field.
7.
etc.
Scenario
3: two
clients on different machines to same server.
1.
server
is up and running and listening on port X.
2.
client1
initiates contact, sends segment with destination port X, source port Y
(selected automatically from pool of unused ports).
3.
client2
initiates contact, sends segment with destination port X, source port Y
(selects same port number as client1!).
4.
segment
arrives at server machine, destination port is read, and delivered to the
process running on port X (the server process). Segment could be from either client1 or client2. Q: How does server know which one,
since both have source port Y? A:
looks at IP address.
5.
server
formulates response, sends segment with destination port Y, source port X.
6.
etc.
The
lesson for delivering to correct process:
Combination
of destination and source port #s will be unique, except if two clients connect
to same server from different IP addresses through same source port#. In this case, differentiate based on IP
address.
Note
that position of source and destination port #’s in segment header is same for
both UDP and TCP (e.g. 0 and 2 byte displacement, respectively).
Datagram
service. Used by DNS, SNMP, some A/V
protocols, and a few others.
Motivation:
if best-effort delivery is good enough, then UDP is fast (no connection setup)
and cheap. Also helps if sender and
receiver operate at similar rates (to avoid flooding).
Segment
Structure:
1.
source
port (16 bits)
2.
destination
port(16 bits)
3.
segment
length(16 bits)
4.
checksum(16
bits)
5.
payload
(variable length)
Fields
1 and 2 already covered.
Field
3 is segment length, including header, in bytes.
Field
4 checksum is used so receiver can determine if segment was received
error-free.
The
16-bit checksum is calculated by taking the sum of all 16-bit portions of the
segment, then computing the one’s complement of that result (e.g. flip the
bits). It is actually a little more
complicated than that, see RFC
768 for details. If checksum field
is all zero’s, receiver assumes checksum is not being used.
If
checksum is being used, receiver calculates sum of all 16-bit portions of
segment, including the checksum itself.
The result will be all 1’s (think about it*), unless an error occurred.
*
Since original checksum is complement of sum of the rest, including it into the
sum will produce a 1 in each bit position.
To use a 4-bit example, if sum of rest is 0101, checksum will be 1010. Receiver calculates sum of the rest plus
checksum, or 0101 + 1010 = 1111.
Simple
protocol:
assumes reliable channel and fast receiver
(textbook “rdt1.0”)
Sender:
when application supplies data, put into packets and send
Receiver:
when packet arrives, pass data up to application layer.
This
family of protocols drops assumption that receiver infinitely fast. Sender must avoid flooding slow
receiver. Must implement flow
control.
Stop-and-wait: assumes reliable
channel (no textbook equivlanent)
Sender:
when application supplies data, send data packet and wait for ACK
(acknowledgement) packet to arrive.
After ACK arrives, send next packet.
Receiver:
when data packet arrives, send ACK packet to sender. Pass data up to application layer as appropriate.
Stop-and-wait
with corrupt channel: unreliable
channel which can corrupt bits (but not lose them) and slow receiver (textbook
“rdt2.x”)
The
following protocol (rdt2.0) will work in all cases except one:
Sender:
when application supplies data, send data packet and wait for ACK or NAK
(negative acknowledgement) packet to arrive.
If ACK, send next packet. If
NAK, resend same packet.
Receiver:
when data packet arrives, check for error.
If none, send ACK packet to sender else send NAK packet. Pass data up to application layer as
appropriate.
When
will this not work? (hint: errors are not exclusive
to data packets)
Problem:
what if ACK/NAK is corrupted?
Solution: Add sequence number to data packet. 0 or 1 will do.
Sender:
toggle sequence number before sending new data packet.
Receiver:
If arriving packet has same sequence number as last one, it is duplicate soACK
it (since sender didn’t know it was received) then discard it.
Total
solution
requires all the functionality listed above for sender and receiver.
Sender:
when application supplies data, toggle sequence number, send data packet and
wait for ACK or NAK packet to arrive.
If ACK, send next packet. If NAK
or garbled, resend same packet.
Receiver:
when data packet arrives, check for garbled.
If garbled, send NAK packet to sender. If duplicate, send ACK then
discard data. If correct packet, send
ACK packet. Pass data up to application
layer as appropriate.
NOTE:
textbook shows version 2.2, that uses ACK with sequence number and no NAK. TCP uses a version of this.
1. Receiver always responds with ACK containing
sequence number of last correct packet.
2. Sender must recognize when ACK really means
NAK!
Stop-and-wait
with lossy channel: unreliable
channel which can corrupt bits and lose packets and maybe slow receiver
(textbook “rdt3.0”)
Given
version 2.1 or 2.2, you need only add timer to sender.
Propagation
delay is major factor:
Improve
performance by providing pipelining.
Two
flavors are:
·
Go-Back-N
(retransmit all packets since last confirmed ACK)
·
Selective
Repeat (retransmit only packets w/o confirmed ACK)
Study
TCP sliding window protocol later (it is combo).
Go-Back-N.
·
Sender
has window (range) of packet “slots”:
-
packets
transmitted but no ACK received yet
-
packets
slots usable but no data received yet from app layer
·
Sender
window has length N.
·
If
sender window full, new data from app layer is “rejected”
(may use semaphore as in producer-consumer problem to prevent)
·
Requires
sequence number
·
Textbook
uses only ACKs (can also define using ACK/NAK)
·
ACKs
cumulative (one ACK can cover more than one packet)
·
Textbook
receiver accepts only in-order packets (window size 1).
Can also implement to accept out-of-order packets (window size > 1)
Sender
action:
·
Transmit
data packets until:
-
ACK
received –or-
-
Timer
times out –or-
-
window
full –or-
-
waiting
for data from app layer
·
When
ACK x received
-
slide
window’s “left edge” to slot x+1
-
slide
window’s “right edge” by similar amount to keep size N
-
(re)start
timer unless window is now empty
·
When
timer times out
-
Resend
all packets in the window!
Receiver
action:
·
If
received packet is non-corrupt and in-order
-
deliver
data to app layer
-
ACK
with sequence number of that packet
·
else
(corrupt or out-of-order)
-
ACK
with sequence number of last accepted packet
NOTE:
It appears that ACK covers only one packet instead of being cumulative. But
suppose:
·
sender
sends seq# 0,1,2,3
·
receiver
sends ACK 0,1,2,3
·
receiver’s
ACK 0, ACK 1, and ACK 2 are lost
·
sender
will get ACK 3 first and acknowledge all four.
Consider
performance:
-
pipelined, so much better than stop-and-wait
- due
to corrupted/lost ACKs, correctly transmitted packets may be retransmitted
Selective Repeat.
·
Address
performance issue: Go-Back-N can result in many correct data packets being
retransmitted.
·
Receiver
buffers out-of-order packets, so now has window
·
ACKs
are individual (not cumulative)
·
Each
packet has individual timer
Sender
action:
·
Transmit
until… (same as Go-Back-N).
·
When
ACK x received,
o
If
ACK duplicate or outside window, ignore.
Otherwise……
o
Delete
timer for slot x
o
Mark
slot x as ACKed
o
If
all slots less than x are ACKed (e.g. slot x is “left edge”),
§
slide
“left edge” of window to first unACKed slot
§
slide
“right edge” of window by same amount
§
send
packets that come into window as a result of slide.
·
When
slot times out, resend that packet only.
Receiver
Action:
·
When
packet x received and x is within receiver window,
o
Send
ACK x.
o
If
duplicate, ignore. Otherwise…….
o
Store
data in buffer slot x.
o
If
all slots less than x have been delivered to app layer,
§
Slide
“left edge” of window to first undelivered slot y.
§
Slide
“right edge” of window by same amount.
§
Deliver
buffer slots x through y-1 to app layer.
·
When
packet x is received and x is “behind” current window,
o
Send
ACK x.
·
Otherwise,
ignore the packet.
Example
to illustrate two things.
Example:
(window size N = 4)
1.
Sender
sends 0, 1, 2 and 3.
2.
Receiver
ACKs 0, 1, 2, and 3. And slides left edge up to slot 4.
3.
ACK
0 is lost.
4.
Sender
gets ACK 1, 2 and 3. Cannot slide left
edge; no ACK 0.
5.
Sender
slot 0 times out and resends.
6.
Receiver
gets duplicate slot 0. What should it
do? Slot 0 is now behind its window.
Illustrates
that sender and receiver windows need not coincide.
Illustrates
that range of sequence numbers must be
at least twice the window size.
Suppose:
·
sequence
numbers range from 0 to N-1 (01230123…).
·
After
step 2, what is receiver’s left edge?
Slot 0. Right edge? Slot 3.
·
At
step 6, receiver gets packet for slot 0.
It thinks “slot 0 within window”, which is wrong!
Suppose:
·
sequence
numbers range from 0 to 2N-2 (01234560123456…).
·
After
step 2, what is receiver’s left edge?
Slot 4. Right edge? Slot 0.
·
At
step 6, receiver gets packet for slot 0.
It thinks “slot 0 within window”, which is wrong!
Suppose:
·
sequence
numbers range from 0 to 2N-1 (0123456701234567…).
·
After
step 2, what is receiver’s left edge?
Slot 4. Right edge? Slot 7.
·
At
step 6, receiver gets packet for slot 0.
It thinks “slot 0 behind window”, which is right!
END OF MATERIAL
FOR EXAM 1.
TCP
provides connection-oriented service.
TCP
provides flow and congestion control.
TCP
provides connection management
a.
3
way handshake to establish connection
b.
full
duplex communication (both ways at same time)
c.
send
and receive buffers established during handshake
d.
maximum
segment size (MSS), actually max payload size
e.
sliding
window for pipelined stream service
f.
double
exchange sequence to terminate connnection
Highlights
(for specific structure, see e.g. my spring
2000 notes)
Selected
field notes:
·
Header
length is 4 byte field, count of header length in 4-byte words
·
Sequence
and ack numbers are 32 bits, and represent byte counts
·
Receiver
window size field is 16 bits, and represents the number of bytes that receiver
is willing to receive (e.g. has available in receive buffer)
·
For
each of the above, correlate field lengths with allowable value range
·
The
“6 flags” are:
o
URG
: payload contains high priority info, there is 16 bit field elsewhere
containing its byte offset in payload.
o
ACK
: this segment contains acknowledgement
o
PSH
: deliver directly, w/o going through receive buffer
o
RST,
SYN, FIN : used for connection maintenance
Variable
length sliding window with per-segment timers and retransmission, and
cumulative ACKs
Receiver
can either accept or reject out-of-order segment
Sequence
and ACK numbers are handled thusly:
a.
seq#
and ack# are byte counts in transmission stream
b.
initial
seq# selected at random (what is probability of 0?)
c.
sender
and receiver exchange initial seq# during 3-way handshake
d.
for
a given segment, seq# = byte offset for first byte of payload, e.g. (init seq# + stream byte offset) mod 2**16
e.
for
a given segment, ack# = seq# of next byte expected from sender
Note
this handles full duplex. For further
info, see discussion below of flow and congestion control.
Example:
·
A
sends 3600 bytes to B
·
MSS
= 1500
·
Error-free
·
A’s
initial seq# is 26
·
Assume
connection already established
·
DC
means “don’t care” it is not relevant
to this example
One
possible sequence (essentially a stop-and-wait)
1.
A à B :
seq# 26, ack# DC, data 1500 bytes
2.
B à A :
seq# DC, ack# 1526
3.
A à B :
seq# 1526, ack# DC, data 1500 bytes
4.
B à A :
seq# DC, ack# 3026
5.
A à B :
seq# 3026, ack# DC, data 600 bytes
6.
B à A :
seq# DC, ack# 3626
Could
rearrange to pipeline all three, e.g.
1.
A à B :
seq# 26, ack# DC, data 1500 bytes
2.
A à B : seq#
1526, ack# DC, data 1500 bytes
3.
A à B :
seq# 3026, ack# DC, data 600 bytes
4.
B à A :
seq# DC, ack# 1526
5.
B à A :
seq# DC, ack# 3026
6.
B à A :
seq# DC, ack# 3626
Example:
·
Full
Duplex transmit
·
A
transmits 1111 bytes to B
·
B
transmits 666 bytes to A
·
MSS
= 512
·
Error-free
·
A’s
initial seq# is 451
·
B’s
initial seq# is 103
·
Assume
connection already established
·
DC
means “don’t care” it is not relevant
to this example
One
possible sequence
1.
A à B :
seq# 451, ack# 103, data 512 bytes
2.
B à A :
seq# 103, ack# 963, data 512 bytes
3.
A à B :
seq# 963, ack# 615, data 512 bytes
4.
B à A :
seq# 615, ack# 1475, data 154 bytes
5.
A à B :
seq# 1475, ack# 769, data 87 bytes
6.
B à A :
seq# DC, ack# 1562
Three-way
handshake to establish connection : 3 segments exchanged
1.
client-to-server connection request :
2.
server-to-client response:
(allocates
TCP buffer space and variables before responding)
3.
client-to-server confirmation:
(allocates
TCP buffer space and variables)
Double
exchange to terminate connection
Think
of it as one exchange to cut off one direction of duplex and second exchange to
cut off other direction.
(we’ll
show client initiating the sequence; could be either party)
1.
A is finished, sends B a segment with FIN bit set.
2.
B sends acknowledgement to A, and deallocates its buffers
A-to-B
direction is now closed.
3.
B sends A a segment with FIN bit set
4. A
sends acknowledgement to B, waits awhile, then deallocates its buffers
B-to-A
direction is now closed.
HOW
ABOUT RESET PROTOCOL?
·
Note
that receiver gives sender “receiver window size” in each return segment.
·
Thus
sender knows how much receive buffer space sender has
·
Sender
maintains sending window no larger than that.
·
Sending
window is Last-Byte-Sent - Last-Byte-Acked
·
Special
case:
o
receiver
window fills, thus “receiver window size” is 0.
o
sender
stops sending
o
receiver
window empties as data moved to application layer
o
how
does receiver tell sender it now has space?
Since it is receiving nothing, it is not sending ACKs. Unless it is also sending data the other
direction, it has no way to give its updated “receiver window size” to sender.
o
solution
is: sender continues to send segments with one data byte, which trigger ACKs
from receiver.
Distinguish
flow control from congestion control
TCP,
as a transport layer protocol, has only indirect knowledge of congestion (from
ACK behaviors, sender notices that segments are being delayed and dropped)
A
given TCP sender contributes to congestion by transmitting a wider send window
(called its “congestion window”), and does its part to relieve congestion by
narrowing its window (throttle).
A
typical scenario for a large transmission follows these phases (see RFC 2581 for details):
o
congestion window variable set to MSS (or 2 * MSS),
o
threshold variable set to arbitrary value (max. at receiver’s advertised window
size?)
o
sender
transmits congestion window (e.g 1 or 2 segments).
o
For
each ACK received on time, congestion window increased by MSS.
o
Results
in exponential growth.
o
entered
when congestion window exceeds threshold.
o
Congestion
window is increased by MSS only when an entire window’s worth of ACKs is
received on time.
o
Results
in linear growth.
o
timeout
·
reset
the threshold to half the congestion window size,
·
reset
congestion window size to MSS, and
·
go
back into slow start phase
o
3
consecutive ACKs for same #
·
fast retransmit, e.g. retransmit before timeout
·
set
congestion window to threshold
·
go
back into congestion avoidance phase (“fast recovery”)
Algorithm described as Additive-Increase, Multiplicative-Decrease (AIMD), which applies only if you ignore the slow start phase.
[notes
| CSC 465 | Peter
Sanderson | Computer Science | SMSU ]