CAN201 – Week 5

Introduction to Networking Module Leader: Dr. Wenjun Fan & Dr. Fei Cheng
0
Lecture 5 – Transport Layer (2)

• Roadmap
1. Pipelined communication
2. TCP: connection-oriented transport
3. Principles of congestion control

1
rdt3.0: stop-and-wait operation
sender receiver
first packet bit transmitted, t = 0
last packet bit transmitted, t = L / R

first packet bit arrives

RTT last packet bit arrives, send ACK

ACK arrives, send next

packet, t = RTT + L / R

U L/R .008
sender = = = 0.00027
RTT + L / R 30.008

2
Question
• How to increase utilization?

3
 km

Urumqi

Shanghai

4
Pipelined protocols
• Pipelining: sender allows multiple, “in-flight”, yet-to-be-
acknowledged pkts
• Range of sequence numbers must be increased
• Buffering at sender and/or receiver

data pkgs
data pkg

ACK pkgs

a stop-and-wait protocol in operation a pipelined protocol in operation 5

Pipelining: increased utilization
sender receiver
first packet bit transmitted, t = 0
last bit transmitted, t = L / R

first packet bit arrives

RTT last packet bit arrives, send ACK
last bit of 2nd packet arrives, send ACK
last bit of 3rd packet arrives, send ACK
ACK arrives, send next
packet, t = RTT + L / R
3-packet pipelining increases
utilization by a factor of 3!

U 3L / R .024
sender
= = = 0.0008
RTT + 3L / R 30.024
6
Two forms: Go-Back-N and Selective repeat
Go-back-N (GBN): Selective Repeat (SR):
• Sender can have up to • Sender can have up to N
N unacked packets in unacked packets in
pipeline pipeline
• Receiver only sends • Rcvr sends individual
cumulative ack ack for each packet
• Doesn’t ack packet if
there’s a gap
• Sender has timer for • Sender maintains timer
oldest unacked packet for each unacked packet
• When timer expires, • When timer expires,
retransmit all unacked retransmit only that
packets unacked packet
7
Go-Back-N: sender
• k-bit seq # in pkt header
• “window” of up to N, consecutive unacked pkts allowed

• ACK(n): ACKs all pkts up to, including seq # n - “cumulative ACK”

• may receive duplicate ACKs (see receiver)
• Timer for oldest in-flight pkt
• Timeout(n): retransmit packet n and all higher seq # pkts in window

8
GBN: sender extended FSM
rdt_send(data)
if (nextseqnum < base+N) {
sndpkt[nextseqnum] = make_pkt(nextseqnum,data,chksum)
udt_send(sndpkt[nextseqnum])
if (base == nextseqnum)
start_timer
nextseqnum++
}
 else
refuse_data(data)
base=1
nextseqnum=1
timeout
start_timer
Wait
udt_send(sndpkt[base])
rdt_rcv(rcvpkt) udt_send(sndpkt[base+1])
&& corrupt(rcvpkt) …
udt_send(sndpkt[nextseqnum-1])
rdt_rcv(rcvpkt) &&
notcorrupt(rcvpkt)
base = getacknum(rcvpkt)+1
If (base == nextseqnum)
stop_timer
else 9
start_timer
GBN: receiver extended FSM
default
udt_send(sndpkt) rdt_rcv(rcvpkt)
&& notcurrupt(rcvpkt)
 && hasseqnum(rcvpkt,expectedseqnum)
expectedseqnum=1 Wait extract(rcvpkt,data)
sndpkt = deliver_data(data)
make_pkt(expectedseqnum,ACK,chksum) sndpkt = make_pkt(expectedseqnum,ACK,chksum)
udt_send(sndpkt)
expectedseqnum++

ACK-only: always send ACK for correctly-received pkt with highest in-order
seq #
• may generate duplicate ACKs
• need only remember expectedseqnum
• out-of-order pkt:
• discard (don’t buffer): no receiver buffering!
• re-ACK pkt with highest in-order seq # 10
GBN in action
sender window (N=4) sender receiver
012345678 send pkt0
012345678 send pkt1
012345678 send pkt2 receive pkt0, send ack0
012345678 send pkt3 Xloss receive pkt1, send ack1
(wait)
receive pkt3, discard,
012345678 rcv ack0, send pkt4 (re)send ack1
012345678 rcv ack1, send pkt5 receive pkt4, discard,
(re)send ack1
ignore duplicate ACK receive pkt5, discard,
(re)send ack1
pkt 2 timeout
012345678 send pkt2
012345678 send pkt3
012345678 send pkt4 rcv pkt2, deliver, send ack2
012345678 send pkt5 rcv pkt3, deliver, send ack3
rcv pkt4, deliver, send ack4
rcv pkt5, deliver, send ack5
11
Selective repeat
• Receiver individually acknowledges all correctly received
pkts
• buffers pkts, as needed, for eventual in-order delivery to upper
layer
• Sender only resends pkts for which ACK not received
• sender timer for each unACKed pkt
• Sender window
• N consecutive seq #’s
• limits seq #s of sent, unACKed pkts
12
 Selective repeat: sender, receiver windows
next_seq_num

send_base

sender
view
Window size
N

rcv_base

receiver
view
Window size
N Received

13
 Selective repeat: sender, receiver windows
next_seq_num

send_base

sender
view
Window size
N

rcv_base

receiver
view
Window size
N Received

14
 Selective repeat: sender, receiver windows
next_seq_num

send_base

sender
view
Window size
N

rcv_base

receiver
view
Window size
N Received

15
 Selective repeat: sender, receiver windows
next_seq_num

send_base

sender
view
Window size
N

rcv_base

receiver
view
Window size
N Received

16
 Selective repeat: sender, receiver windows
next_seq_num

send_base

sender
view
Window size
N

rcv_base

receiver
view
Window size
N Received

17
 Selective repeat: sender, receiver windows
next_seq_num

send_base

sender
view
Window size
N

rcv_base

receiver
view
Window size
N Received

18
 Selective repeat: sender, receiver windows
next_seq_num

send_base

sender
view
Window size
N

rcv_base

receiver
view
Window size
N Received

19
 Selective repeat: sender, receiver windows
next_seq_num

send_base

sender
view
Window size
N

rcv_base

receiver
view
Window size
N Received

20
 Selective repeat: sender, receiver windows
next_seq_num

send_base

sender
view
Window size
N

rcv_base

receiver
view
Window size
N Received

21
 Selective repeat: sender, receiver windows
next_seq_num

send_base

sender
view
Window size
N

rcv_base

receiver
view
Window size
N Received

22
 Selective repeat: sender, receiver windows
next_seq_num

send_base

sender
view
Window size
N

rcv_base

receiver
view
Window size
N Received

23
 Selective repeat: sender, receiver windows
next_seq_num

send_base

sender
view
Window size
N

rcv_base

receiver
view
Window size
N Received

24
Selective repeat
Sender Receiver
pkt n in [rcvbase, rcvbase+N-1]
data from above:
• Send ACK(n)
• If next available seq # in
window, send pkt • Out-of-order: buffer
• In-order: deliver (also
timeout(n): deliver buffered, in-order
• Resend pkt n, restart timer pkts), advance window to
next not-yet-received pkt
ACK(n) in [sendbase,sendbase+N]:
pkt n in [rcvbase-N,rcvbase-1]
• Mark pkt n as received
• ACK(n)
• If n smallest unACKed pkt,
advance window base to otherwise:
next unACKed seq # • Ignore
25
Selective repeat in action
sender window (N=4) sender receiver
012345678 send pkt0
012345678 send pkt1
012345678 send pkt2 receive pkt0, send ack0
012345678 send pkt3 Xloss receive pkt1, send ack1
(wait)
receive pkt3, buffer,
012345678 rcv ack0, send pkt4 send ack3
012345678 rcv ack1, send pkt5 receive pkt4, buffer,
send ack4
record ack3 arrived receive pkt5, buffer,
send ack5
pkt 2 timeout
012345678 send pkt2
012345678 record ack4 arrived
012345678 rcv pkt2; deliver pkt2,
record ack5 arrived
012345678 pkt3, pkt4, pkt5; send ack2

Q: what happens when ack2 arrives?

26
 sender window receiver window
(after receipt) (after receipt)

Selective repeat: dilemma 0123012 pkt0

0123012 pkt1 0123012
0123012 pkt2 0123012
Example: 0123012
pkt3
• Seq #’s: 0, 1, 2, 3
0123012
X
0123012
pkt0
• Window size=3 (a) no problem
will accept packet
with seq number 0

• Receiver sees no difference in receiver can’t see sender side.

two scenarios! receiver behavior identical in both cases!
something’s (very) wrong!
• Duplicate data accepted as pkt0
new in (b) 0123012
0123012 pkt1 0123012
0123012 pkt2 0123012
X
• Q: what relationship between
0123012
X
timeout
seq # size and window size to retransmit pkt0 X
pkt0
avoid problem in (b)? 0123012
will accept packet
with seq number 0
(b) oops!
27
Lecture 5 – Transport Layer (1)

• Roadmap
1. Pipelined communication
2. TCP: connection-oriented transport
3. Principles of congestion control

28
TCP: Overview RFCs: 793,1122,1323, 2018, 2581

• Point-to-point: • Full duplex data:

• one sender, one receiver • bi-directional data flow in
same connection
• Reliable, in-order byte stream :
• Connection-oriented:
• no “message boundaries” • handshaking (exchange of
• Pipelined: control msgs) inits sender,
• TCP congestion and flow control receiver state before data
exchange
set window size
• Flow controlled:
• sender will not overwhelm
receiver
29
TCP segment structure
32 bits
URG: urgent data counting
(generally not used) source port # dest port #
by bytes
sequence number of data
ACK: ACK #
valid acknowledgement number (not segments!)
head not
PSH: push data now len used
UAP R S F receive window
(generally not used) # bytes
checksum Urg data pointer
rcvr willing
RST, SYN, FIN: to accept
options (variable length)
connection estab
(setup, teardown
commands)
application
Internet data
checksum (variable length)
(as in UDP)

30
vs UDP structure
32 bits
source port # dest port #
length checksum

application
data
(payload)

UDP segment format

31
TCP segment structure
32 bits
URG: urgent data Counting by bytes of
(generally not used) source port # dest port #
data (not segments!)
sequence number
ACK: ACK #
valid acknowledgement number
head not
PSH: push data now len used
UAP R S F receive window
(generally not used) # bytes
checksum Urg data pointer
rcvr willing
RST, SYN, FIN: to accept
options (variable length)
connection estab
(setup, teardown
commands)
application
Internet data
checksum (variable length)
(as in UDP)

32
TCP seq. numbers, ACKs outgoing segment from sender
source port # dest port #
sequence number
Sequence numbers: acknowledgement number
rwnd
• Byte stream “number” of first byte checksum urg pointer

in segment’s data window size

N
Acknowledgements:
• Seq # of next byte expected from
sender sequence number space
other side
• Cumulative ACK sent sent, not- usable not
ACKed yet ACKed but not usable
Q: How receiver handles out-of- (“in-
flight”)
yet sent

order segments incoming segment to sender

• A: TCP spec doesn’t say, up to source port # dest port #

implementor. (Buffer…) sequence number

acknowledgement number
A rwnd
checksum urg pointer
33
TCP seq. numbers, ACKs
Host A Host B

User
types
‘C’
Seq=42, ACK=79, data = ‘C’
host ACKs
receipt of
‘C’, echoes
Seq=79, ACK=43, data = ‘C’ back ‘C’
host ACKs
receipt
of echoed
‘C’ Seq=43, ACK=80

simple telnet scenario

34
Send from client
35
ACK from server
36
Send from server
37
TCP round trip time, timeout
Q: How to set TCP timeout Q: How to estimate RTT?
value? • SampleRTT: measured time
• Longer than RTT from segment transmission
• But RTT varies until ACK receipt
• Ignore retransmissions
• Too short: premature • SampleRTT will vary, want
timeout, unnecessary estimated RTT “smoother”
retransmissions • Average several recent
• Too long: slow reaction to measurements, not just current
SampleRTT
segment loss
38
TCP round trip time, timeout
EstimatedRTTn = (1- )*EstimatedRTTn-1 + *SampleRTT

• Exponential weighted moving average

• Influence of past sample decreases exponentially fast
• Typical value:  = 0.125 RTT: gaia.cs.umass.edu to fantasia.eurecom.fr

350

RTT: gaia.cs.umass.edu to fantasia.eurecom.fr

RTT (milliseconds)

300

250
RTT (milliseconds)

200

sampleRTT
150

EstimatedRTT

100
1 8 15 22 29 36 43 50 57 64 71 78 85 92 99 106

time (seconds)
time (seconnds)

SampleRTT Estimated RTT

TCP round trip time, timeout
• Timeout interval: EstimatedRTT plus “safety margin”
• large variation in EstimatedRTT -> larger safety margin

• Estimate SampleRTT deviation from EstimatedRTT:

DevRTT = (1-)*DevRTT +
*|SampleRTT-EstimatedRTT|
(typically,  = 0.25)

TimeoutInterval = EstimatedRTT + 4*DevRTT

estimated RTT “safety margin”

(Dev = Deviation) 40
TCP reliable data transfer
• TCP creates rdt service on top
of IP’s unreliable service
• pipelined segments let’s initially consider
• cumulative acks simplified TCP sender:
• ignore duplicate acks
• single retransmission timer
• ignore flow control,
• Retransmissions triggered by: congestion control
• timeout events
• duplicate acks

41
Crystal oscillator

42
TCP sender events:
Data rcvd from app: Timeout:
• Create segment with seq # • Retransmit segment that caused
• Seq # is byte-stream timeout
number of first data byte • Restart timer
in segment Ack rcvd:
• Start timer if not already • If ack acknowledges previously
running unacked segments
• Think of timer as for oldest • Update what is known to be ACKed
unacked segment • Start timer if there are still unacked
• Expiration interval: segments
TimeOutInterval

43
TCP sender (simplified)
data received from application above
create segment, seq. #: NextSeqNum
pass segment to IP (i.e., “send”)
NextSeqNum = NextSeqNum + length(data)
if (timer currently not running)
 start timer
NextSeqNum = InitialSeqNum wait
SendBase = InitialSeqNum for
event timeout
retransmit not-yet-acked segment
with smallest seq. #
start timer
ACK received, with ACK field value y
if (y > SendBase) {
SendBase = y
/* SendBase–1: last cumulatively ACKed byte */
if (there are currently not-yet-acked segments)
start timer
else stop timer
} 44
TCP: retransmission scenarios
Host A Host B Host A Host B

SendBase=92
Seq=92, 8 bytes of data Seq=92, 8 bytes of data

Seq=100, 20 bytes of data

timeout

timeout
ACK=100
X
ACK=100
ACK=120

Seq=92, 8 bytes of data Seq=92, 8

SendBase=100 bytes of data
SendBase=120
ACK=100
ACK=120

SendBase=120

lost ACK scenario premature timeout

45
TCP: retransmission scenarios
Host A Host B

Seq=92, 8 bytes of data

Seq=100, 20 bytes of data

timeout

ACK=100
X
ACK=120

Seq=120, 15 bytes of data

cumulative ACK
46
TCP ACK generation [RFC 1122, RFC 2581]
Event at receiver TCP receiver action
arrival of in-order segment with delayed ACK. Wait up to 500ms
expected seq #. All data up to for next segment. If no next segment,
expected seq # already ACKed send ACK

arrival of in-order segment with immediately send single cumulative

expected seq #. One delayed ACK, ACKing both in-order segments
segment has ACK pending

arrival of out-of-order segment immediately send duplicate ACK,

higher-than-expect seq. # . indicating seq. # of next expected byte
Gap detected

arrival of segment that immediate send ACK, provided that

partially or completely fills gap segment starts at lower end of gap

47
TCP fast retransmit
• Time-out period often
TCP fast retransmit
relatively long: if sender receives 3
• Long delay before ACKs for same data
resending lost packet (“triple duplicate ACKs”),
• Detect lost segments via resend unacked
duplicate ACKs. segment with smallest
seq #
• Sender often sends many
• likely that unacked
segments back-to-back segment lost, so don’t
• If segment is lost, there wait for timeout
will likely be many
duplicate ACKs.
48
TCP fast retransmit
Host A Host B

Seq=92, 8 bytes of data

Seq=100, 20 bytes of data
X

ACK=100

timeout
ACK=100
ACK=100
ACK=100
Seq=100, 20 bytes of data

fast retransmit after sender

receipt of triple duplicate ACK 49
 TCP flow control application
application may process
remove data from application
TCP socket buffers ….
TCP socket OS
Flow control … slower than TCP
receiver buffers
Receiver controls sender, so
receiver is delivering
sender won’t overflow (sender is sending)
TCP
Receiver’s buffer by transmitting code
too much, too fast

IP
code

from sender

receiver protocol stack

50
TCP flow control
• Receiver “advertises” free buffer space to application process
by including rwnd value in TCP header
of receiver-to-sender segments RcvBuffer buffered data
• RcvBuffer size set via socket options
(typical default is 4096 bytes)
• many operating systems auto-adjust
rwnd free buffer space
RcvBuffer
• Sender limits amount of unacked (“in- TCP segment payloads
flight”) data to receiver’s rwnd value
• Guarantees receive buffer will not receiver-side buffering
overflow

51
TCP segment structure
32 bits
URG: urgent data counting
(generally not used) source port # dest port #
by bytes
sequence number of data
ACK: ACK #
valid acknowledgement number (not segments!)
head not
PSH: push data now len used
UAP R S F receive window
(generally not used) # bytes
checksum Urg data pointer
rcvr willing
RST, SYN, FIN: to accept
options (variable length)
connection estab
(setup, teardown
commands)
application
Internet data
checksum (variable length)
(as in UDP)

52
SYN: Window Scale factor
53
Calculated Window Size = 6379 x 64 = 408256
54
Connection Management
Before exchanging data, sender/receiver “handshake”:
• Agree to establish connection (each knowing the other willing to
establish connection) Agree on connection parameters

application application

connection state: ESTAB connection state: ESTAB

connection variables: connection Variables:
seq # client-to-server seq # client-to-server
server-to-client server-to-client
rcvBuffer size rcvBuffer size
at server,client at server,client

network network

Socket clientSocket = Socket connectionSocket =

newSocket("hostname","port welcomeSocket.accept();
number");
55
Agreeing to establish a connection
2-way handshake: Q: Will 2-way handshake always
work in network?
• Variable delays
Let’s talk • Retransmitted messages (e.g.
ESTAB req_conn(x)) due to message loss
OK
ESTAB • Message reordering
• Can’t “see” other side

choose x
req_conn(x)
ESTAB
acc_conn(x)
ESTAB

56
Agreeing to establish a connection
2-way handshake failure scenarios:

choose x choose x
req_conn(x) req_conn(x)
ESTAB ESTAB
retransmit acc_conn(x) retransmit acc_conn(x)
req_conn(x) req_conn(x)

ESTAB ESTAB
data(x+1) accept
req_conn(x)
retransmit data(x+1)
data(x+1)
connection connection
client x completes server x completes server
client
terminates forgets x terminates forgets x
req_conn(x)

ESTAB ESTAB
data(x+1) accept
half open connection!
data(x+1)
(no client!) 57
TCP 3-way handshake
client state server state
LISTEN LISTEN
choose init seq num, x
send TCP SYN msg
SYNSENT SYNbit=1, Seq=x
choose init seq num, y
send TCP SYNACK
msg, acking SYN SYN RCVD
SYNbit=1, Seq=y
ACKbit=1; ACKnum=x+1
received SYNACK(x)
ESTAB indicates server is live;
send ACK for SYNACK;
this segment may contain ACKbit=1, ACKnum=y+1
client-to-server data
received ACK(y)
indicates client is live
ESTAB

58
3-way handshake

59
TCP 3-way handshake: FSM
closed

Socket connectionSocket =
welcomeSocket.accept();

 Socket clientSocket =
SYN(x) newSocket("hostname","port
number");
SYNACK(seq=y,ACKnum=x+1)
create new socket for SYN(seq=x)
communication back to client listen

SYN SYN
rcvd sent

SYNACK(seq=y,ACKnum=x+1)
ESTAB ACK(ACKnum=y+1)
ACK(ACKnum=y+1)

60
TCP: closing a connection
• Client, server each close their side of connection
• Send TCP segment with FIN bit = 1
• Respond to received FIN with ACK
• On receiving FIN, ACK can be combined with own FIN
• Simultaneous FIN exchanges can be handled

61
TCP: closing a connection
client state server state
ESTAB ESTAB
clientSocket.close()
FIN_WAIT_1 can no longer FINbit=1, seq=x
send but can
receive data CLOSE_WAIT
ACKbit=1; ACKnum=x+1
can still
FIN_WAIT_2 wait for server send data
close

LAST_ACK
FINbit=1, seq=y
TIMED_WAIT can no longer
send data
ACKbit=1; ACKnum=y+1
timed wait
for 2*max CLOSED
segment lifetime

CLOSED
62
3-way for connection

4-way for closing a connection

Data from client to server

63
Lecture 5 – Transport Layer (1)

• Roadmap
1. Pipelined communication
2. TCP: connection-oriented transport
3. Principles of congestion control

64
Principles of congestion control
Congestion:
• Informally: “too many sources sending too much data too
fast for network to handle”
• Different from flow control!
• Manifestations:
• lost packets (buffer overflow at routers)
• long delays (queueing in router buffers)
• A top-10 problem!
65
Causes/costs of congestion: scenario 1
• Two senders, two original data: in throughput: out
receivers
• One router, infinite
Host A

buffers unlimited shared

output link buffers
• Output link capacity: R
• no retransmission
Host B

R/2

delay
out

in R/2 in R/2

▪ maximum per-connection ❖ large delays as arrival rate, in,
throughput: R/2 approaches capacity 66
Causes/costs of congestion: scenario 2
• One router, finite buffers
• Sender retransmission of timed-out packet
• application-layer input = application-layer output: in = out
• transport-layer input includes retransmissions : 'in in
in : original data
'in: original data, plus out
retransmitted data

Host A

finite shared output

Host B
link buffers 67
Causes/costs of congestion: scenario 2
R/2
Idealization: perfect knowledge
• Sender sends only when router

out
buffers available
in R/2

in : original data

copy 'in: original data, plus out
retransmitted data

A free buffer space!

finite shared output

Host B
link buffers
Transport Layer 68
Causes/costs of congestion: scenario 2
Idealization: known loss
packets can be lost, dropped at router due
to full buffers
• Sender only resends if packet known to be lost

in : original data

copy 'in: original data, plus out
retransmitted data

A
no buffer space!

Host B
69
Causes/costs of congestion: scenario 2
R/2
Idealization: known loss
packets can be lost, dropped at router due

out
to full buffers
• Sender only resends if packet known to be lost
in R/2

in : original data

'in: original data, plus out
retransmitted data

A
free buffer space!

Host B
70
Causes/costs of congestion: scenario 2
Realistic: duplicates R/2

• Packets can be lost, dropped at router when sending at R/2,

some packets are
due to full buffers

out
retransmissions
including duplicated
• Sender times out prematurely, sending that are delivered!
two copies, both of which are delivered in R/2

in
timeout
copy 'in out

A
free buffer space!

Host B 71
Causes/costs of congestion: scenario 2
Realistic: duplicates R/2

• Packets can be lost, dropped at router when sending at R/2,

some packets are
due to full buffers

out
retransmissions
including duplicated
• Sender times out prematurely, sending that are delivered!
two copies, both of which are delivered in R/2

“costs” of congestion:
• More work (retrans) for given “goodput”
• Unneeded retransmissions: link carries multiple copies of pkt
• decreasing goodput

72
Causes/costs of congestion: scenario 3
Q: what happens as in and in’
• Four senders increase ?
• Multi-hop paths A: as red in’ increases, all arriving
• Timeout/retransmit blue pkts at upper queue are
dropped, blue throughput -> 0
Host A
in : original data out
Host B
'in: original data, plus
retransmitted data
finite shared output
link buffers

R1
Host D
R4 Host C
R2
R3

73
Causes/costs of congestion: scenario 3

Another “cost” of congestion:

• When packet dropped, any “upstream transmission capacity
used for that packet was wasted!
74
Approaches to Congestion Control

• End-to-end congestion control

• Network layer does not provide support for congestion control
• Trans layer has to infer from network behavior
• TCP will control the size of window
• Network-assisted congestion control
• Routers provide feedback to sender and/or receiver (a single one bit)

75
Thanks.

76