5.Transport_Part1
Transport Layer Part 1
Computer Networks and Applications
Week 4
COMP 3331/COMP 9331
Reading Guide:
Chapter 3, Sections 3.1 – 3.4
2
Transport Layer
our goals:
v understand
principles behind
transport layer
services:
§ multiplexing,
demultiplexing
§ reliable data transfer
§ flow control
§ congestion control
v learn about Internet
transport layer protocols:
§ UDP: connectionless
transport
§ TCP: connection-oriented
reliable transport
Transport Layer 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
Transport layer
v Moving “down” a layer
v Current perspective:
§ Application layer is the boss….
§ Transport layer usually executing within the
OS Kernel
§ The network layer is ours to command !!
4
Network layer (some context)
v What it does: finds paths through network
§ Routing from one end host to another
v What it doesn’t:
§ Reliable transfer: “best effort delivery”
§ Guarantee paths
§ Arbitrate transfer rates
v For now, think of the network layer as
giving us an “API” with one function:
sendtohost(data, host)
§ Promise: the data will go to that (usually!!)
5
Transport services and protocols
v provide logical communication
between app processes
running on different hosts
v transport protocols run in
end systems
§ sender side: breaks app
messages into segments,
passes to network layer
§ receiver side: reassembles
segments into messages,
passes to app layer
§ Exports services to
application that network
layer does not provide
application
transport
network
data link
physical
logical end-end transport
application
transport
network
data link
physical
6
Why a transport layer?
Transport
Network
Datalink
Physical
Application
Host A Host B
Datalink
Physical
bro
w
ser
telnet
m
m
edia
ftp
bro
w
ser
IP
many application
processes
Drivers
+NIC
Operating
System
7
Why a transport layer?
Host A Host B
Datalink
Physical
bro
w
ser
telnet
m
m
edia
ftp
bro
w
ser
IP
many application
processes
Datalink
Physical
telnet
ftp
IP
H
T
T
P
server
Transport Transport
Communication
between hosts
(128.4.5.6 ßà162.99.7.56)
Communication
between processes
at hosts
8
Transport Layer 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
9
Multiplexing/demultiplexing
process
socket
use header info to deliver
received segments to correct
socket
demultiplexing at receiver:handle data from multiple
sockets, add transport header
(later used for demultiplexing)
multiplexing at sender:
transport
application
physical
link
network
P2P1
transport
application
physical
link
network
P4
transport
application
physical
link
network
P3
10
Note: The network is a shared resource. It does not care about your applications, sockets, etc.
Connectionless demultiplexing
v recall: created socket has
host-local port #:
DatagramSocket mySocket1
= new DatagramSocket(12534);
v when host receives UDP
segment:
§ checks destination port #
in segment
§ directs UDP segment to
socket with that port #
v recall: when creating
datagram to send into
UDP socket, must specify
§ destination IP address
§ destination port #
IP datagrams with same
dest. port #, but different
source IP addresses
and/or source port
numbers will be directed
to same socket at dest
11
Connectionless demux: example
DatagramSocket
serverSocket = new
DatagramSocket
(6428);
transport
application
physical
link
network
P3
transport
application
physical
link
network
P1
transport
application
physical
link
network
P4
DatagramSocket
mySocket1 = new
DatagramSocket
(5775);
DatagramSocket
mySocket2 = new
DatagramSocket
(9157);
source port: 9157
dest port: 6428
source port: 6428
dest port: 9157
source port: ?
dest port: ?
source port: ?
dest port: ?
12
P2
(5775)
Connection-oriented demux
v TCP socket identified
by 4-tuple:
§ source IP address
§ source port number
§ dest IP address
§ dest port number
v demux: receiver uses
all four values to direct
segment to appropriate
socket
v server host may support
many simultaneous TCP
sockets:
§ each socket identified by
its own 4-tuple
v web servers have
different sockets for
each connecting client
§ non-persistent HTTP will
have different socket for
each request
13
Revisiting TCP Sockets
TCP handshake
Client
Socket
Welcoming, port X
Socket
Server ProcessClient Process
Connection, port X
Socket 1pipe
Client Process
Client
Socket
Connection, port X
Socket 2
pip
e
14
Connection-oriented demux: example
transport
application
physical
link
network
P3
transport
application
physical
link
P4
transport
application
physical
link
network
P2
source IP,port: A,9157
dest IP, port: B,80
source IP,port: B,80
dest IP,port: A,9157
host: IP
address A
host: IP
address C
network
P6P5
P1
source IP,port: C,5775
dest IP,port: B,80
source IP,port: C,9157
dest IP,port: B,80
three segments, all destined to IP address: B,
dest port: 80 are demultiplexed to different sockets
server: IP
address B
15
(9157) (5775) (9157)
Could also be a single process with multiple threads
May I scan your ports?
v Servers wait at open ports for client requests
v Hackers often perform port scans to determine open,
closed and unreachable ports on candidate victims
v Several ports are well-known
§ <1024 are reserved for well-known apps § Other apps also use known ports • MS SQL server uses port 1434 (udp) • Sun Network File System (NFS) 2049 (tcp/udp) v Hackers can exploit known flaws with these known apps § Example: Slammer worm exploited buffer overflow flaw in the SQL server v How do you scan ports? § Nmap, Superscan, etc http://netsecurity.about.com/cs/hackertools/a/aa121303.htm http://www.auditmypc.com/ 16 https://www.grc.com/shieldsup v Suppose we use UDP instead of TCP for communicating with a web server where all requests and responses fit in a single UDP segment. Suppose 100 clients are simultaneously communicating with this web server. How many sockets are respectively active at the server and each client? a) 1, 1 b) 2, 1 c) 200, 2 d) 100, 1 e) 101, 1 17 Quiz: UDP Sockets www.zeetings.com/salil ANSWER: a) v Suppose 100 clients are simultaneously communicating with a traditional HTTP/TCP web server. How many sockets are active respectively at the server and each client? a) 1, 1 b) 2, 1 c) 200, 2 d) 100, 1 e) 101, 1 18 Quiz: TCP Sockets www.zeetings.com/salil ANSWER: d) or e) depending on whether a welcoming socket is counted as a socket v Suppose 100 clients are simultaneously communicating with a traditional HTTP/TCP web server. Do all the TCP sockets at the server have the same server-side port number? a) Yes b) No 19 Quiz: TCP Sockets www.zeetings.com/salil ANSWER: a) Transport Layer 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 20 UDP: User Datagram Protocol [RFC 768] v “no frills,” “bare bones” Internet transport protocol v “best effort” service, UDP segments may be: § lost § delivered out-of-order to app v connectionless: § no handshaking between UDP sender, receiver § each UDP segment handled independently of others 21 UDP: segment header source port # dest port # 32 bits application data (payload) UDP segment format length checksum length, in bytes of UDP segment, including header v no connection establishment (which can add delay) v simple: no connection state at sender, receiver v small header size v no congestion control: UDP can blast away as fast as desired why is there a UDP? 22 2 bytes Optional Checksum UDP checksum sender: v treat segment contents, including header fields, as sequence of 16-bit integers v checksum: addition (one’s complement sum) of segment contents v sender puts checksum value into UDP checksum field receiver: v Add all the received together as 16-bit integers v Add that to the checksum v If the result is not 1111 1111 1111 1111, there are errors ! • Goal: detect “errors” (e.g., flipped bits) in transmitted segment • Router memory errors • Driver bugs • Electromagnetic interference 23 Internet checksum: example example: add two 16-bit integers 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1 wraparound sum checksum Note: when adding numbers, a carryout from the most significant bit needs to be added to the result 24 25 UDP: Checksum Ø Checksum is the 16-bit one's complement of the one's complement sum of a pseudo header of information from the IP header, the UDP header, and the data, padded with zero octets at the end (if necessary) to make a multiple of two octets. Ø Checksum header, data and pre-pended IP pseudo-header (some fields from the IP header) Ø But the header contains the checksum itself? IP pseduo-header UDP payload UDP header Checksum: example 26 Note: TCP Checksum computation is exactly similar 27 v Latency sensitive/time critical v Quick request/response (DNS, DHCP) v Network management (SNMP) v Routing updates (RIP) v Voice/video chat v Gaming (especially FPS) v Error correction managed by periodic messages UDP Applications QUIC: Quick UDP Internet Connections v Core idea: HTTP/2 over UDP § Faster connection establishment § Overcomes HoL blocking due to lost packets § Improved congestion control § Forward error correction § Connection migration 28https://www.chromium.org/quic Not on Exam Transport Layer 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 29 Reliable Transport l In a perfect world, reliable transport is easy l All the bad things best-effort can do l a packet is corrupted (bit errors) l a packet is lost (why?) l a packet is delayed (why?) l packets are reordered (why?) l a packet is duplicated (why?) 30 The Two Generals Problem v Two army divisions (blue) surround enemy (red) § Each division led by a general § Both must agree when to simultaneously attack § If either side attacks alone, defeat v Generals can only communicate via messengers § Messengers may get captured (unreliable channel) 31 The Two Generals Problem • Two army divisions (blue) surround enemy (red) – Each division led by a general – Both must agree when to simultaneously attack – If either side attacks alone, defeat • Generals can only communicate via messengers – Messengers may get captured (unreliable channel) The Two Generals Problem v How to coordinate? § Send messenger: “Attack at dawn” § What if messenger doesn’t make it? 32 The Two Generals Problem • How to coordinate? – Send messenger: “Attack at dawn” – What if messenger doesn’t make it? The Two Generals Problem v How to be sure messenger made it? § Send acknowledgement: “We received message” 33 The Two Generals Problem • How to be sure messenger made it? – Send acknowledgment: “I delivered message” Principles of reliable data transfer v important in application, transport, link layers § top-10 list of important networking topics! v characteristics of unreliable channel will determine complexity of reliable data transfer protocol (rdt) 34 No bits are corrupted, lost or arrive out-of-order at the receiver v characteristics of unreliable channel will determine complexity of reliable data transfer protocol (rdt) Principles of reliable data transfer v important in application, transport, link layers § top-10 list of important networking topics! 35 No bits are corrupted, lost or arrive out-of-order at the receiver v characteristics of unreliable channel will determine complexity of reliable data transfer protocol (rdt) v important in application, transport, link layers § top-10 list of important networking topics! Principles of reliable data transfer 36 37 We’ll: Ø Incrementally develop sender, receiver sides of reliable data transfer protocol (rdt) Ø Consider only unidirectional data transfer § but control info will flow on both directions! Ø Channel will not re-order packets Reliable data transfer: getting started stop and wait sender sends one packet, then waits for receiver response rdt1.0: reliable transfer over a reliable channel Ø Underlying channel perfectly reliable • no bit errors • no loss of packets Ø Transport layer does nothing ! 38 Global Picture of rdt1.0 sender receiver data data Solid line: error-free transmission 39 v underlying channel may flip bits in packet § checksum to detect bit errors v the question: how to recover from errors: § acknowledgements (ACKs): receiver explicitly tells sender that pkt received OK § negative acknowledgements (NAKs): receiver explicitly tells sender that pkt had errors § sender retransmits pkt on receipt of NAK v new mechanisms in rdt2.0 (beyond rdt1.0): § error detection § receiver feedback: control msgs (ACK,NAK) rcvr- >sender
rdt2.0: channel with bit errors
How do humans recover from “errors”
during conversation?
40
v underlying channel may flip bits in packet
§ checksum to detect bit errors
v the question: how to recover from errors:
§ acknowledgements (ACKs): receiver explicitly tells sender
that pkt received OK
§ negative acknowledgements (NAKs): receiver explicitly tells
sender that pkt had errors
§ sender retransmits pkt on receipt of NAK
v new mechanisms in rdt2.0 (beyond rdt1.0):
§ error detection
§ feedback: control msgs (ACK,NAK) from receiver to
sender
§ retransmission
rdt2.0: channel with bit errors
41
Global Picture of rdt2.0
sender receiver
data
NACK
data
ACK
Dotted line: erroneous transmission
Solid line: error-free transmission
42
rdt2.0 has a fatal flaw!
what happens if
ACK/NAK corrupted?
v sender doesn’t know
what happened at
receiver!
v can’t just retransmit:
possible duplicate
handling duplicates:
v sender retransmits
current pkt if ACK/NAK
corrupted
v sender adds sequence
number to each pkt
v receiver discards (doesn’t
deliver up) duplicate pkt
stop and wait
sender sends one packet,
then waits for receiver
response
43
rdt2.1: discussion
sender:
v seq # added to pkt
v two seq. #’s (0,1) will
suffice. Why?
v must check if received
ACK/NAK corrupted
v twice as much state
§ state must
“remember” whether
“expected” pkt should
have seq # of 0 or 1
receiver:
v must check if received
packet is duplicate
§ state indicates whether
0 or 1 is expected pkt
seq #
v note: receiver can not
know if its last
ACK/NAK received
OK at sender
44
New Measures: Sequence Numbers, Checksum for ACK/NACK,
Duplicate detection
Another Look at rdt2.1
sender
data (0)
receiver
ACK
data (1)
waiting for 0
sending #
0
waiting for 1
sending
# 1
waiting for 0
NACK
data (0)
data (0)
ACK
Duplicate Packet
Discard !!
Dotted line: erroneous transmission
Solid line: error-free transmission
45
rdt2.2: a NAK-free protocol
v same functionality as rdt2.1, using ACKs only
v instead of NAK, receiver sends ACK for last pkt
received OK
§ receiver must explicitly include seq # of pkt being ACKed
v duplicate ACK at sender results in same action as
NAK: retransmit current pkt
46
rdt2.2: Example
sender
data (1)
receiver
ACK (0)
(implies
a NAK)
data (0)
waiting for 0
sending #
0
waiting for 1sending
# 1
waiting for 0
ACK (0)
data (0)
data (1)
ACK (1)
sending #
0
Duplicate ACK
Resend old
packet
Dotted line: erroneous transmission
Solid line: error-free transmission
47
rdt3.0: channels with errors and loss
new assumption:
underlying channel can
also loose packets
(data, ACKs)
§ checksum, seq. #,
ACKs, retransmissions
will be of help … but
not enough
approach: sender waits
“reasonable” amount of
time for ACK
v retransmits if no ACK
received in this time
v if pkt (or ACK) just delayed
(not lost):
§ retransmission will be
duplicate, but seq. #’s
already handles this
§ receiver must specify seq
# of pkt being ACKed
v requires countdown timer
v No retransmission on
duplicate ACKs
48
sender receiver
rcv pkt1
rcv pkt0
send ack0
send ack1
send ack0
rcv ack0
send pkt0
send pkt1
rcv ack1
send pkt0
rcv pkt0
pkt0
pkt0
pkt1
ack1
ack0
ack0
(a) no loss
sender receiver
rcv pkt1
rcv pkt0
send ack0
send ack1
send ack0
rcv ack0
send pkt0
send pkt1
rcv ack1
send pkt0
rcv pkt0
pkt0
pkt0
ack1
ack0
ack0
(b) packet loss
pkt1
X
loss
pkt1
timeout
resend pkt1
rdt3.0 in action
49
rdt3.0 in action
rcv pkt1
send ack1
(detect duplicate)
pkt1
sender receiver
rcv pkt1
rcv pkt0
send ack0
send ack1
send ack0
rcv ack0
send pkt0
send pkt1
rcv ack1
send pkt0
rcv pkt0
pkt0
pkt0
ack1
ack0
ack0
(c) ACK loss
ack1
X
loss
pkt1
timeout
resend pkt1
rcv pkt1
send ack1
(detect duplicate)
pkt1
sender receiver
rcv pkt1
send ack0
rcv ack0
send pkt1
send pkt0
rcv pkt0
pkt0
ack0
(d) premature timeout/ delayed ACK
pkt1
timeout
resend pkt1
ack1
send ack1
(do nothing)
rcv ack1
ack1
send pkt0
rcv ack1 pkt0
rcv pkt0
send ack0ack0
50
v Which of the following are needed for reliable
data transfer with only packet corruption (and no
loss or reordering)? Use only as much as is strictly
needed.
a) Checksums
b) Checksums, ACKs, NACKs
c) Checksums, ACKs
d) Checksums, ACKs, sequence numbers
e) Checksums, ACKs, NACKs, sequence numbers
www.zeetings.com/salil
51
Quiz: Reliable Data Transfer
ANSWER: d)
v If packets (and ACKs and NACKs) could be lost
which of the following is true of RDT 2.1 (or
2.2)?
a) Reliable in-order delivery is still achieved
b) The protocol will get stuck
c) The protocol will continue making progress but may
skip delivering some messages
52
Quiz: Reliable Data Transfer
www.zeetings.com/salil
ANSWER: b)
v Which of the following are needed for reliable
data transfer to handle packet corruption and loss?
Use only as much as is strictly needed.
a) Checksums, timeouts
b) Checksums, ACKs, sequence numbers
c) Checksums, ACKs, timeouts
d) Checksums, ACKs, timeouts, sequence numbers
e) Checksums, ACKs, NACKs, timeouts, sequence
numbers
53
Quiz: Reliable Data Transfer
www.zeetings.com/salil ANSWER: d)
54
rdt3.0: stop-and-wait operation
first packet bit transmitted, t = 0
sender receiver
RTT
last packet bit transmitted, t = L / R
first packet bit arrives
last packet bit arrives, send ACK
ACK arrives, send next
packet, t = RTT + L / R
U sender =
L / R
RTT + L / R
55
Performance of rdt3.0
Ø rdt3.0 is correct, but performance stinks
Ø e.g.: 1 Gbps link, 8000 bit packet and 30msec RTT:
• U sender: utilization – fraction of time sender busy sending
U
sender =
.008
30.008
= 0.00027
L / R
RTT + L / R
=
• RTT=30 msec, 1KB pkt every 30.008 msec: 33kB/sec
thruput over 1 Gbps link
Ø Network protocol limits use of physical resources!
Dtrans =
L
R
8000 bits
109 bits/sec= = 8 microsecs
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
v two generic forms of pipelined (sliding window)
protocols: go-Back-N, selective repeat
56
Pipelining: increased utilization
first packet bit transmitted, t = 0
sender receiver
RTT
last bit transmitted, t = L / R
first packet bit arrives
last packet bit arrives, send ACK
ACK arrives, send next
packet, t = RTT + L / R
last bit of 2nd packet arrives, send ACK
last bit of 3rd packet arrives, send ACK
3-packet pipelining increases
utilization by a factor of 3!
U sender =
3L / R
RTT + L / R
57
58
Pipelined protocols: overview
Go-Back-N: Selective Repeat:
Ø Sender can have up to N
unacked packets in pipeline
Ø Sender can have up to N
unacked packets in pipeline
Ø Sender has single timer for
oldest unacked packet, when
timer expires, retransmit all
unacked packets
Ø Sender maintains timer for
each unacked packet, when
timer expires, retransmit
only that unacked packet
Ø Receiver only sends
cumulative ack, doesn’t ack new
packet if there’s a gap
Ø Receiver sends individual
ack for each packet
ØThere is no buffer available
at Receiver, out of order
packets are discarded
Ø Receiver has buffer, can
accept out of order packets
Go-Back-N: sender
v k-bit seq # in pkt header
v “window” of up to N, consecutive unack’ed pkts allowed
v ACK(n): ACKs all pkts up to, including seq # n – “cumulative ACK”
§ may receive duplicate ACKs (see receiver)
v timer for oldest in-flight pkt
v timeout(n): retransmit packet n and all higher seq # pkts in
window
Applets: http://media.pearsoncmg.com/aw/aw_kurose_network_2/applets/go-back-n/go-back-n.html
http://www.ccs-labs.org/teaching/rn/animations/gbn_sr/
59
GBN in action
send pkt0
send pkt1
send pkt2
send pkt3
(wait)
sender receiver
receive pkt0, send ack0
receive pkt1, send ack1
receive pkt3, discard,
(re)send ack1rcv ack0, send pkt4
rcv ack1, send pkt5
pkt 2 timeout
send pkt2
send pkt3
send pkt4
send pkt5
Xloss
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
0 1 2 3 4 5 6 7 8
0 1 2 3 4 5 6 7 8
0 1 2 3 4 5 6 7 8
0 1 2 3 4 5 6 7 8
0 1 2 3 4 5 6 7 8
0 1 2 3 4 5 6 7 8
0 1 2 3 4 5 6 7 8
0 1 2 3 4 5 6 7 8
60
Selective repeat
v receiver individually acknowledges all correctly
received pkts
§ buffers pkts, as needed, for eventual in-order delivery
to upper layer
v sender only resends pkts for which ACK not
received
§ sender timer for each unACKed pkt
v sender window
§ N consecutive seq #’s
§ limits seq #s of sent, unACKed pkts
Applet: http://media.pearsoncmg.com/aw/aw_kurose_network_3/applets/SelectRepeat/SR.html
61http://www.ccs-labs.org/teaching/rn/animations/gbn_sr/
Selective repeat: sender, receiver windows
62
Selective repeat
data from above:
v if next available seq # in
window, send pkt
timeout(n):
v resend pkt n, restart timer
ACK(n) in [sendbase,sendbase+N-1]:
v mark pkt n as received
v if n smallest unACKed pkt,
advance window base to next
unACKed seq #
sender
pkt n in [rcvbase, rcvbase+N-1]
v send ACK(n)
v out-of-order: buffer
v in-order: deliver (also
deliver buffered, in-order
pkts), advance window to
next not-yet-received pkt
pkt n in [rcvbase-N,rcvbase-1]
v ACK(n)
otherwise:
v ignore
receiver
63
Selective repeat in action
send pkt0
send pkt1
send pkt2
send pkt3
(wait)
sender receiver
receive pkt0, send ack0
receive pkt1, send ack1
receive pkt3, buffer,
send ack3rcv ack0, send pkt4
rcv ack1, send pkt5
pkt 2 timeout
send pkt2
Xloss
receive pkt4, buffer,
send ack4
receive pkt5, buffer,
send ack5
rcv pkt2; deliver pkt2,
pkt3, pkt4, pkt5; send ack2
record ack3 arrived
0 1 2 3 4 5 6 7 8
sender window (N=4)
0 1 2 3 4 5 6 7 8
0 1 2 3 4 5 6 7 8
0 1 2 3 4 5 6 7 8
0 1 2 3 4 5 6 7 8
0 1 2 3 4 5 6 7 8
0 1 2 3 4 5 6 7 8
0 1 2 3 4 5 6 7 8
0 1 2 3 4 5 6 7 8
0 1 2 3 4 5 6 7 8
record ack4 arrived
record ack5 arrived
Q: what happens when ack2 arrives?
64
Selective repeat:
dilemma
example:
v seq #’s: 0, 1, 2, 3
v window size=3
receiver window
(after receipt)
sender window
(after receipt)
0 1 2 3 0 1 2
0 1 2 3 0 1 2
0 1 2 3 0 1 2
pkt0
pkt1
pkt2
0 1 2 3 0 1 2 pkt0
timeout
retransmit pkt0
0 1 2 3 0 1 2
0 1 2 3 0 1 2
0 1 2 3 0 1 2X
X
X
will accept packet
with seq number 0(b) oops!
0 1 2 3 0 1 2
0 1 2 3 0 1 2
0 1 2 3 0 1 2
pkt0
pkt1
pkt2
0 1 2 3 0 1 2
pkt0
0 1 2 3 0 1 2
0 1 2 3 0 1 2
0 1 2 3 0 1 2
X
will accept packet
with seq number 0
0 1 2 3 0 1 2 pkt3
(a) no problem
receiver can’t see sender side.
receiver behavior identical in both cases!
something’s (very) wrong!
v receiver sees no
difference in two
scenarios!
v duplicate data
accepted as new in
(b)
Q: what relationship
between seq # size
and window size to
avoid problem in (b)?
65
A: Sender window size <= ½ of Sequence number space Recap: components of a solution v Checksums (for error detection) v Timers (for loss detection) v Acknowledgments § cumulative § selective v Sequence numbers (duplicates, windows) v Sliding Windows (for efficiency) v Reliability protocols use the above to decide when and what to retransmit or acknowledge 66 v Which of the following is not true? a) GBN uses cumulative ACKs, SR uses individual ACKs b) Both GBN and SR use timeouts to address packet loss c) GBN maintains a separate timer for each outstanding packet d) SR maintains a separate timer for each outstanding packet e) Neither GBN nor SR use NACKs 67 Quiz: GBN, SR www.zeetings.com/salil ANSWER: c) v Suppose a receiver that has received all packets up to and including sequence number 24 and next receives packet 27 and 28. In response, what are the sequence numbers in the ACK(s) sent out by the GBN and SR receiver, respectively? a) [27, 28], [28, 28] b) [24, 24], [27, 28] c) [27, 28], [27, 28] d) [25, 25], [25, 25] e) [nothing], [27, 28] 68 Quiz: GBN, SR www.zeetings.com/salil ANSWER: b) Summary v Multiplexing/Demultimplexing v UDP v Reliable Data Transfer § Stop-and-wait protocols § Sliding winding protocols v Up Next: § TCP §Congestion Control 69