2 of 24

Chapter 3 outline

3.1 Transport-layer services

3.2 Multiplexing and � demultiplexing

3.3 Connectionless � transport: UDP

3.4 Principles of reliable data� transfer

3.5 Connection-oriented � transport: TCP

segment structure
reliable data transfer
flow control
connection management

3.6 Principles of congestion� control

3.7 TCP congestion control

3 of 24

Principles of Reliable data transfer

Reliable data transfer service by Transport layer, over unreliable Network layer

4 of 24

If underlying channel is perfectly reliable…

no bit errors
no loss of packets
no out of order delivery

Channel with NO bit errors/loss etc

Sender & receiver just send/receive data…

sender sends data into underlying channel
receiver reads data from underlying channel

5 of 24

underlying channel may flip bits in pkts

use checksum to detect bit errors - recall UDP checksum
if in error, drop pkt

now how to recover from errors..? need feedback..!

Acknowledgement (ACK):

receiver tells sender – pkt received OK – transmit next

Negative Acknowledgement (NAK):

receiver tells sender – pkt had errors – retransmit

new mechanisms…

error detection thru checksum
receiver feedback thru control msgs (ACK, NAK) from rcvr -> sender

Channel with bit errors

6 of 24

What happens if ACK/NAK corrupted?

sender doesn’t know if pkt recvd correctly or incorrectly at �receiver…

can’t transmit new pkt

can’t re-transmit old pkt

stuck..!

Just retransmit old pkt…

might cause re-transmission of correctly received pkt..!
how to handle Duplicates..!

Handling duplicates:

sender adds Sequence Number to each pkt
if ACK/NAK garbled, sender re-transmits current pkt
receiver discards duplicate pkt due to Seq Num �(doesn’t deliver up)

Sender sends one packet,

then waits for receiver

response

Stop and Wait protocol

A fatal flaw

7 of 24

Sender receiver actions

Sender:

adds seq# to pkt
two seq# (0,1) will suffice... Why?
must “remember” whether “current” pkt has �seq# 0 or 1

Receiver:

must check if received pkt is duplicate

must know whether �expected pkt seq# is 0 or 1
duplicate not delivered up

Note: receiver can not know if its last ACK/NAK was received OK at sender

8 of 24

NAK-free protocol

Same functionality as earlier, but using ACKs only
Instead of NAK,

receiver sends…

“ACK for last pkt received OK”

receiver must explicitly include…

“seq# of pkt being ACKed”

Duplicate ACK at sender results in same action as NAK; retransmit current pkt
TCP uses NAK-free approach

9 of 24

Channel with bit errors & pkt loss

New assumption:

underlying channel can also �“lose“ packets (Data or ACKs)

checksum, ACKs, Seq#, retransmissions will be of help, �but not enough

Q: how to deal with loss?

sender waits if certain data �or ACK lost, then re-transmits

Use Countdown timer…

sender waits “reasonable” amount of time for ACK

if no ACK received in this time, retransmit
if pkt (or ACK) just delayed (not lost)…

re-transmission will be duplicate
but use of Seq# already �handles this

What is the “right value” for timer…? depends on network conditions…!

10 of 24

Protocol in action

11 of 24

Protocol in action

12 of 24

Stop-and-wait operation

13 of 24

Stop-and-wait performance

Protocol is correct, but performance poor…
e.g, 1 Gbps link, 15 ms prop delay, 8000 bits pkt

U _sender: utilization – fraction of time sender busy sending data

if RTT = 30 msec, 1KB pkt every 30 msec
Thruput = data/time = 267 kbps ….(too less)

network protocol may limit use of physical resources..!

D_trans =

8000 bits

10⁹bits/sec

8 microsec

14 of 24

Pipelined protocols

Pipelining: sender allows multiple, “in-flight”, yet-to-be-Acknowledged pkts

increases transmission efficiency
range of sequence numbers must be increased
buffering at sender and/or receiver

15 of 24

Pipelining: increased utilization

16 of 24

Pipelined protocols

Go-back-N:

when pkt is lost, �sender retransmits all the pkts, starting from the one lost

Selective Repeat:

when pkt is lost, �sender retransmits only the lost pkt

Sender & Receiver agree upon a Widow size

sender sends upto N pkts at a time, without receiving an ACK

“up to N unACKed packets in pipeline”

Two generic forms of pipelined protocols:

Go-Back-N and Selective Repeat

17 of 24

Go-Back-N Protocol

send pkt0

send pkt1

send pkt2

send pkt3

(wait)

sender

receiver

receive pkt0, send ack0

receive pkt1, send ack1

receive pkt3, discard,

(re)send ack1

rcv ack0, send pkt4

rcv ack1, send pkt5

pkt 2 timeout

send pkt2

send pkt3

send pkt4

send pkt5

loss

receive pkt4, discard,

(re)send ack1

receive pkt5, discard,

(re)send ack1

rcv pkt2, deliver, send ack2

rcv pkt3, deliver, send ack3

rcv pkt4, deliver, send ack4

rcv pkt5, deliver, send ack5

ignore duplicate ACK

0 1 2 3 4 5 6 7 8

sender window (N=4)

0 1 2 3 4 5 6 7 8

18 of 24

Go-Back-N: sender

Sender assumes “window” size of N packets…

(upto N consecutive unACK’ed pkts can be sent)

ACK(n): ACKs all pkts up to & including Seq# n - “cumulative ACK”

may receive duplicate ACKs

Timer: for oldest in-flight pkt
timeout(n): retransmit pkt n and all higher Seq# pkts in window

19 of 24

GBN: receiver

ACK-only:

always send ACK for correctly-received pkt, �with highest, in-order Seq#
may generate duplicate ACKs

Out-of-order pkt:

discard (don’t buffer): no receiver buffering!
re-ACK pkt with highest, in-order Seq#

20 of 24

Selective repeat in action (N=4)

Under GBN, this pkt will be dropped

21 of 24

Selective Repeat (improvement of the GBN Protocol)

Receiver individually ACKs all correctly received pkts
Buffers pkts, as needed, for in-order delivery to upper layer

e.g, Sender sends pkt 1, 2, 3, 4,…., 10 � Receiver got 2, 4, 6, 8, 10 � Sender resends 1, 3, 5, 7, 9 only

Sender only resends pkts for which ACK not received

sender timer for EACH unACKed pkt

Sender window

N consecutive Seq#
again limits Seq# of sent, unACKed pkts

22 of 24

Selective repeat: sender, receiver windows

23 of 24

Selective repeat:� dilemma

Example:

Seq#: 0, 1, 2, 3
if window size (N)=3
issue: receiver sees no difference in two scenarios!

wrongly receives duplicate data as new (in lower fig)

Q: what relationship between Seq# size and window size?

N ≤ 2^k/2

In real life, we use k bits to implement Seq# �A practical issue…!

24 of 24

Pipelined protocols: overview

Go-back-N:

sender can have up to N unACKed packets in pipeline
receiver sends �cumulative acks
sender has timer for oldest unACKed packet

when timer expires, retransmit all packets in the window, starting from unACKed packet

Selective Repeat:

sender can have up to N unACKed packets in pipeline
rcvr sends individual ACK for �each packet
sender has timer for each �unACKed packet

when timer expires, �retransmit only the �unACKed packet