Java程序辅导

Transport Layer 
Transport Layer Part 1 
Computer Networks and Applications 
Week 4 
COMP 3331/COMP 9331 
Reading Guide: Chapter 3, Sections 3.1 – 3.4 
Transport Layer         2 
Announcements 
v  Assignment 1 
§  Non-CSE students MUST seek approval for alternate assignment by 
30th March (else we assume you do the regular one) 
§  Start development ASAP 
§  Plagiarism - BE CAREFUL 
v  Are you solving sample questions? 
v  Are you reading prescribed sections from the textbook? 
v  Mid-session Exam in Week 6 (during Monday lecture) 
§  Details will be available on website soon (Location, Instructions, …) 
§  All material covered from Week 1- Week 5 (including self-study) 
§  Closed book 
§  BYO Calculators 
Transport Layer         3 
Chapter 3: 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 
§  TCP congestion control 
Transport Layer 
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 
        4 
Transport Layer 
Transport layer 
v  Moving “down” a layer 
v  Current perspective: 
§  Application is the boss…. 
§  Usually executing within the OS Kernel 
§  The network layer is ours to command !! 
        5 
Transport Layer 
Network layer (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!!) 
        6 
Transport Layer 
Transport services and protocols 
v  provide logical communication 
between app processes 
running on different hosts 
v  transport protocols run in 
end systems  
§  send side: breaks app 
messages into segments, 
passes to network layer 
§  rcv 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 
application 
transport 
network 
data link 
physical 
        7 
Transport Layer 
Transport vs. network layer 
v  network layer: logical 
communication 
between hosts 
v  transport layer: 
logical 
communication 
between processes  
§ relies on, enhances, 
network layer 
services 
12 kids in Ann’s house sending 
letters to 12 kids in Bill’s 
house: 
v  hosts = houses 
v  processes = kids 
v  app messages = letters in 
envelopes 
v  transport protocol = Ann 
and Bill who demux to in-
house siblings 
v  network-layer protocol = 
postal service 
 
household analogy: 
        8 
READ THIS IN TEXT 
Why a transport layer? 
Transport 
Network 
Datalink 
Physical 
Application 
Host A Host B 
Datalink 
Physical 
brow
ser 
telnet 
m
m
edia 
ftp 
brow
ser 
IP 
many application 
 processes 
Drivers 
+NIC 
Operating  
System 
Transport Layer         9 
Why a transport layer? 
Host A Host B 
Datalink 
Physical 
brow
ser 
telnet 
m
m
edia 
ftp 
brow
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 
Transport Layer         
10 
Transport Layer 
v  Reliable transfers 
v  Error detection 
v  Error correction 
v  Bandwidth guarantees 
 
v  Latency guarantees 
v  Encryption 
v  Message ordering 
v  Link sharing fairness 
        
11 
Quiz: Transport Layer Services 
A: 4 or fewer 
B: 5 
C: 6 
D: 7 
E: All 8 
How many of these services might we provide at the transport layer ? Which ? 
Transport Layer         
12 
Quiz: UDP 
A: It has good performance characteristics 
 
B: Sometimes all we need is error detection 
 
C: We still need to distinguish between sockets 
 
D: It basically just fills a gap in our layering model 
 
TCP sounds great ! UDP .. Meh. Why do we need it? 
Adding Features 
v  Nothing comes for free 
v  Additional headers 
§  Keeps transport state 
§  Attached by sender, decoded by receiver 
v  Establishing state (making a connection) 
§  Recall HTTP 1.0 vs HTTP 1.1 
§  Extra communication round trip 
v  Delays due to loss/reordering 
v  Playing fair might cost you ! Transport Layer 13 
Adding Features 
• Nothing comes for free 
 
• Data given by application 
 
• Apply header 
– Keeps transport state 
– Attached by sender 
– Decoded by receiver 
Payload Data 
Payload Data TCP/UDP 
Transport Layer 
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 
        
14 
Transport Layer 
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 
P2 P1 
transport 
application 
physical 
link 
network 
P4 
transport 
application 
physical 
link 
network 
P3 
        
15 
Note: The network is a shared resource. It does not care about your applications, sockets, etc.  
Transport Layer 
How demultiplexing works 
v  host receives IP datagrams 
§  each datagram has source IP 
address, destination IP 
address 
§  each datagram carries one 
transport-layer segment 
§  each segment has source, 
destination port number  
v  host uses IP addresses & 
port numbers to direct 
segment to appropriate 
socket 
source port # dest port # 
32 bits 
application 
data  
(payload) 
other header fields 
TCP/UDP segment format 
      16 
Transport Layer 
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 
      17 
Transport Layer 
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: ? 
      18 
Transport Layer 
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 
      19 
Transport Layer 
Revisiting TCP Sockets 
TCP handshake
Client
Socket
Welcoming, port X
Socket
Server Process Client Process 
Connection, port X
Socket 1pipe
Client Process 
Client
Socket
Connection, port X
Socket 2
      20 
Transport Layer 
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 
P6 P5 
P3 
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 
      21 
Transport Layer 
Connection-oriented demux: example 
transport 
application 
physical 
link 
network 
P3 
transport 
application 
physical 
link 
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 
server: IP 
address B 
network 
P3 
source IP,port: C,5775 
dest IP,port: B,80 
source IP,port: C,9157 
dest IP,port: B,80 
P4 
threaded server 
      22 
Transport Layer 
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 use 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/ 
      23 
https://www.grc.com/shieldsup 
v  Suppose 100 clients are simultaneously 
communicating with (a traditional HTTP/TCP) 
web server. How many sockets are respectively 
at the server and at each client? 
A.  1,1 
B.  2,1 
C.  200,2 
D.  100,1 
E.  101, 1 
Transport Layer       24 
Quiz: TCP Sockets 
v  Suppose 100 clients are simultaneously 
communicating with (a traditional HTTP/TCP) 
web server. Do all of the sockets at the server 
have the same server-side port number? 
A.  Yes 
B.  No 
Transport Layer       25 
Quiz: TCP Sockets 
Transport Layer 
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 
      26 
Transport Layer 
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 
      27 
Transport Layer 
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? 
      28 
Transport Layer 
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 inferference 
  
      29 
Transport Layer 
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 
 
      30 
v  If the checksum addition at the receiver 
yields all ones, can the receiver guarantee 
that the received packet is error-free? 
v  A: Yes 
v  B: No 
v  C: Schrodinger’s Cat 
Transport Layer 31 
Quiz: Checksum 
v  Let’s denote a UDP packet as (checksum, data) ignoring 
other fields for this question. Suppose a sender sends 
(0010, 1110) and the receiver receives (0011,1110). 
Which of the following is true of the receiver? 
A.  Thinks the packet is corrupted and discards the 
packet. 
B.  Thinks only the checksum is corrupted and delivers 
the correct data to the application.  
C.  Concludes that nothing is wrong with the packet. 
D.  Receiver explodes.  
Transport Layer       32 
Quiz: Checksum 
Transport Layer 33 
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 unnecessary (periodic messages) 
UDP Applications 
v  What if you want something more reliable than UDP, but 
faster/not as full featured as TCP? 
A.  Sorry, you’re out of luck. 
B.  Write your own transport protocol. 
C.  Add in the features you want at the application layer. 
Transport Layer       34 
Quiz: Reliability over UDP? 
Transport Layer 
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 
      35 
Reliable Transport 
@Sender 
§  send packets 
@Receiver 
§  wait for packets 
l  In a perfect world, reliable transport is easy 
Transport Layer       36 
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  
l  a packet is delayed (why?) 
l  packets are reordered (why?) 
l  a packet is duplicated (why?) 
 
Transport Layer       37 
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) 
Transport Layer 38 
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? 
 
Transport Layer 39 
The Two G nerals Problem 
• How to coordinate? 
– Send essenger: “Attack at dawn” 
– hat if messenger doesn’t make it? 
The Two Generals Problem 
 
v  How to be sure messenger made it? 
§  Send acknowledgement: “We received message” 
 
Transport Layer 40 
The Two G nerals Problem 
• How to be sure messenger made it? 
– Send ackno ledg ent: “I delivered message” 
v  In the “two generals problem”, can the two 
armies reliably coordinate their attack? 
§ A: Yes (explain how) 
§ B: No (explain why not) 
Transport Layer 41 
Quiz: Reliability 
v  Can’t create perfect channel out of faulty one 
v  Can only increase probability of success 
Give up ? No way ! 
v  As humans, we like to face difficult problems 
§  We live in areas prone to natural disasters 
§  We can’t control oceans, by we can build canals 
§  We jus need engineering !! 
Transport Layer 42 
Engineering 
v  Concerns 
§  Message corruption 
§  Message duplication 
§  Message loss 
§  Message reordering 
§  Performance 
v  Our toolbox 
§  Checksums 
§  Timeouts 
§  Acks and Nacks 
§  Sequence numbering 
§  Pipelining 
Transport Layer 3-43 
We will use these to build Automatic Repeat Request (ARQ) protocols 
•  Stop-and-wait 
•  Pipelining 
•  Go-back-N 
•  Selective Repeat 
Transport Layer 
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) 
      44 
Self Study 
Transport Layer 
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! 
      45 
Self Study 
Transport Layer 
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 
      46 
Self Study 
Transport Layer 
Reliable data transfer: getting started 
send 
side 
receive 
side 
rdt_send(): called from above, 
(e.g., by app.). Passed data to 
deliver to receiver upper layer 
udt_send(): called by rdt, 
to transfer packet over 
unreliable channel to receiver 
rdt_rcv(): called when packet 
arrives on rcv-side of channel 
deliver_data(): called by 
rdt to deliver data to upper 
      47 
Self Study 
Transport Layer 
we’ll: 
v  incrementally develop sender, receiver sides of 
reliable data transfer protocol (rdt) 
v  consider only unidirectional data transfer 
§  but control info will flow on both directions! 
v  use finite state machines (FSM)  to specify sender, 
receiver 
state 
1 
state 
2 
event causing state transition 
actions taken on state transition 
state: when in this 
“state” next state 
uniquely determined 
by next event 
event 
actions 
Reliable data transfer: getting started 
      48 
Transport Layer 
rdt1.0: reliable transfer over a reliable channel 
v  underlying channel perfectly reliable 
§  no bit errors 
§  no loss of packets 
v  separate FSMs for sender, receiver: 
§  sender sends data into underlying channel 
§  receiver reads data from underlying channel 
Wait for 
call from 
above packet = make_pkt(data) 
udt_send(packet) 
rdt_send(data) 
extract (packet,data) 
deliver_data(data) 
Wait for 
call from 
below 
rdt_rcv(packet) 
sender receiver 
      49 READ UP ON STATE MACHINES IN THE TEXTBOOK 
Self Study 
Transport Layer 
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? 
      50 
Transport Layer 
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 
rdt2.0: channel with bit errors 
      51 
Transport Layer 
rdt2.0: FSM specification 
Wait for 
call from 
above 
sndpkt = make_pkt(data, checksum) 
udt_send(sndpkt) 
extract(rcvpkt,data) 
deliver_data(data) 
udt_send(ACK) 
rdt_rcv(rcvpkt) &&  
   notcorrupt(rcvpkt) 
rdt_rcv(rcvpkt) && isACK(rcvpkt) 
udt_send(sndpkt) 
rdt_rcv(rcvpkt) && 
   isNAK(rcvpkt) 
udt_send(NAK) 
rdt_rcv(rcvpkt) &&  
  corrupt(rcvpkt) 
Wait for 
ACK or 
NAK 
Wait for 
call from 
below sender 
receiver 
rdt_send(data) 
Λ
      52 
Self Study 
Transport Layer 
rdt2.0: operation with no errors 
Wait for 
call from 
above 
snkpkt = make_pkt(data, checksum) 
udt_send(sndpkt) 
extract(rcvpkt,data) 
deliver_data(data) 
udt_send(ACK) 
rdt_rcv(rcvpkt) &&  
   notcorrupt(rcvpkt) 
rdt_rcv(rcvpkt) && isACK(rcvpkt) 
udt_send(sndpkt) 
rdt_rcv(rcvpkt) && 
   isNAK(rcvpkt) 
udt_send(NAK) 
rdt_rcv(rcvpkt) &&  
  corrupt(rcvpkt) 
Wait for 
ACK or 
NAK 
Wait for 
call from 
below 
rdt_send(data) 
Λ
      53 
Self Study 
Transport Layer 
rdt2.0: error scenario 
Wait for 
call from 
above 
snkpkt = make_pkt(data, checksum) 
udt_send(sndpkt) 
extract(rcvpkt,data) 
deliver_data(data) 
udt_send(ACK) 
rdt_rcv(rcvpkt) &&  
   notcorrupt(rcvpkt) 
rdt_rcv(rcvpkt) && isACK(rcvpkt) 
udt_send(sndpkt) 
rdt_rcv(rcvpkt) && 
   isNAK(rcvpkt) 
udt_send(NAK) 
rdt_rcv(rcvpkt) &&  
  corrupt(rcvpkt) 
Wait for 
ACK or 
NAK 
Wait for 
call from 
below 
rdt_send(data) 
Λ
      54 
Self Study 
Transport Layer 
Global Picture of rdt2.0 
sender receiver 
data 
NACK 
data 
ACK 
Dotted line: erroneous transmission 
Solid line: error-free transmission 
      55 
Transport Layer 
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 
      56 
Transport Layer 
rdt2.1: sender, handles garbled ACK/NAKs 
Wait for 
call 0 from 
above 
sndpkt = make_pkt(0, data, checksum) 
udt_send(sndpkt) 
rdt_send(data) 
Wait for 
ACK or 
NAK 0 udt_send(sndpkt) 
rdt_rcv(rcvpkt) &&   
( corrupt(rcvpkt) || 
isNAK(rcvpkt) ) 
sndpkt = make_pkt(1, data, checksum) 
udt_send(sndpkt) 
rdt_send(data) 
rdt_rcv(rcvpkt)    
&& notcorrupt(rcvpkt)  
&& isACK(rcvpkt)  
udt_send(sndpkt) 
rdt_rcv(rcvpkt) &&   
( corrupt(rcvpkt) || 
isNAK(rcvpkt) ) 
rdt_rcv(rcvpkt)    
&& notcorrupt(rcvpkt) 
&& isACK(rcvpkt)  
Wait for 
 call 1 from 
above 
Wait for 
ACK or 
NAK 1 
Λ
Λ
      57 
Self Study 
Transport Layer 
Wait for 
0 from 
below 
sndpkt = make_pkt(NAK, chksum) 
udt_send(sndpkt) 
rdt_rcv(rcvpkt) &&  
   not corrupt(rcvpkt) && 
   has_seq0(rcvpkt) 
 
rdt_rcv(rcvpkt) && notcorrupt(rcvpkt)  
  && has_seq1(rcvpkt)  
extract(rcvpkt,data) 
deliver_data(data) 
sndpkt = make_pkt(ACK, chksum) 
udt_send(sndpkt) 
Wait for 
1 from 
below 
rdt_rcv(rcvpkt) && notcorrupt(rcvpkt)  
  && has_seq0(rcvpkt)  
extract(rcvpkt,data) 
deliver_data(data) 
sndpkt = make_pkt(ACK, chksum) 
udt_send(sndpkt) 
rdt_rcv(rcvpkt) && (corrupt(rcvpkt) 
sndpkt = make_pkt(ACK, chksum) 
udt_send(sndpkt) 
rdt_rcv(rcvpkt) &&  
   not corrupt(rcvpkt) && 
   has_seq1(rcvpkt) 
 
rdt_rcv(rcvpkt) && (corrupt(rcvpkt) 
sndpkt = make_pkt(ACK, chksum) 
udt_send(sndpkt) 
sndpkt = make_pkt(NAK, chksum) 
udt_send(sndpkt) 
rdt2.1: receiver, handles garbled ACK/NAKs 
      58 
Self Study 
Transport Layer 
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 many states 
§  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 
      59 
Transport Layer 
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 
      60 
Transport Layer 
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 
      61 
Transport Layer 
rdt2.2: Example 
sender 
data (1) 
receiver 
ACK (0) 
(implies a
 NAK) 
data (0) 
waiting for 0 
sending # 
0 
waiting for 1 sending 
# 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 
      62 
Transport Layer 
rdt2.2: sender, receiver fragments 
Wait for 
call 0 from 
above 
sndpkt = make_pkt(0, data, checksum) 
udt_send(sndpkt) 
rdt_send(data) 
udt_send(sndpkt) 
rdt_rcv(rcvpkt) &&   
( corrupt(rcvpkt) || 
  isACK(rcvpkt,1) ) 
rdt_rcv(rcvpkt)    
&& notcorrupt(rcvpkt)  
&& isACK(rcvpkt,0)  
Wait for 
ACK 
0 
sender FSM 
fragment 
rdt_rcv(rcvpkt) && notcorrupt(rcvpkt)  
  && has_seq1(rcvpkt)  
extract(rcvpkt,data) 
deliver_data(data) 
sndpkt = make_pkt(ACK1, chksum) 
udt_send(sndpkt) 
Wait for 
0 from 
below 
rdt_rcv(rcvpkt) &&  
   (corrupt(rcvpkt) || 
     has_seq1(rcvpkt)) 
udt_send(sndpkt) 
receiver FSM 
fragment 
Λ
      63 
Self Study 
v  RDT 2.2 uses only ACKs and is robust against packet 
errors. Would it be possible to implement RDT 2.2 with 
only NACKs?  
A.  YES 
B.  NO 
Please explain your rationale 
Transport Layer       64 
Quiz: RDT 2.2 with only NACKs 
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 get stuck. 
C.  The protocol will continue making progress but may 
skip delivering some messages. 
Transport Layer       65 
Quiz: Reliable Data Transfer 
Transport Layer 
rdt3.0: channels with errors and loss 
new assumption: 
underlying channel can 
also lose 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 
      66 
Transport Layer 
rdt3.0 sender 
sndpkt = make_pkt(0, data, checksum) 
udt_send(sndpkt) 
start_timer 
rdt_send(data) 
Wait 
for 
ACK0 
rdt_rcv(rcvpkt) &&  
( corrupt(rcvpkt) || 
isACK(rcvpkt,1) ) 
Wait for 
call 1 from 
above 
sndpkt = make_pkt(1, data, checksum) 
udt_send(sndpkt) 
start_timer 
rdt_send(data) 
rdt_rcv(rcvpkt)    
&& notcorrupt(rcvpkt)  
&& isACK(rcvpkt,0)  
rdt_rcv(rcvpkt) && 
( corrupt(rcvpkt) || 
isACK(rcvpkt,0) ) 
rdt_rcv(rcvpkt)    
&& notcorrupt(rcvpkt) 
&& isACK(rcvpkt,1)  
stop_timer 
stop_timer 
udt_send(sndpkt) 
start_timer 
timeout 
udt_send(sndpkt) 
start_timer 
timeout 
rdt_rcv(rcvpkt) 
Wait for 
call 0from 
above 
Wait 
for 
ACK1 
Λ
rdt_rcv(rcvpkt) 
Λ
Λ
Λ
      67 
Self Study 
Transport Layer 
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 
      68 
Transport Layer 
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 ack0 ack0 
      69 
v  Suppose we have a modest 8 Mbps link. Our RTT is 
100ms, and we send 1024 byte (1K) segments. What is 
our link utilization with a stop-and-wait protocol such as 
RDT 3.0? 
A.  < 0.1 % 
B.  Approx. 0.1% 
C.  Approx 1% 
D.  1-10% 
E.  > 10% 
Transport Layer       70 
Quiz: RDT 3.0 Performance 
Transport Layer 
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 
      71 
Transport Layer 
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 = 
3 x 125 
100+125 
= 1.67  
3L / R 
RTT + L / R 
= 
      72 
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 
Transport Layer       73 
Quiz: Reliable Data Transfer 
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, and fries with that 
B.  Checksums, ACKs, sequence numbers 
C.  Checksums, ACKs, timeouts, pipelined protocol 
D.  Checksums, ACKs, sequence numbers, timeouts 
E.  Checksums, ACKs, NACKs, sequence numbers, timeouts 
Transport Layer       74 
Quiz: Reliable Data Transfer 
Practice Problem: RDT 
Transport Layer 
http://www-net.cs.umass.edu/kurose_ross/interactive/rdt22.php 
      75 
Self Study 
Transport Layer 
Pipelined protocols: overview 
Go-back-N: 
v  sender can have up to 
N unacked packets in 
pipeline 
v  receiver only sends 
cumulative ack 
§  doesn’t ack packet if 
there’s a gap 
v  sender has timer for 
oldest unacked packet 
§  when timer expires, 
retransmit all unacked 
packets 
Selective Repeat: 
v  sender can have up to N 
unack’ed packets in 
pipeline 
v  rcvr sends individual ack 
for each packet 
 
v  sender maintains timer 
for each unacked packet 
§  when timer expires, 
retransmit only that 
unacked packet 
      76 
Transport Layer 
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 
Applet: http://media.pearsoncmg.com/aw/aw_kurose_network_2/applets/go-back-n/go-back-n.html 
      77 
Transport Layer 
GBN: sender extended FSM 
Wait start_timer udt_send(sndpkt[base]) 
udt_send(sndpkt[base+1]) 
… 
udt_send(sndpkt[nextseqnum-1]
) 
 
timeout 
 
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 = getacknum(rcvpkt)+1 
If (base == nextseqnum) 
    stop_timer 
  else 
    start_timer 
rdt_rcv(rcvpkt) &&  
   notcorrupt(rcvpkt)  
 
base=1 
nextseqnum=1 
 
rdt_rcv(rcvpkt)  
   && corrupt(rcvpkt)  
 
Λ
      78 
Transport Layer 
ACK-only: always send ACK for correctly-received 
pkt with highest in-order seq # 
§  may generate duplicate ACKs 
§  need only remember expectedseqnum 
v  out-of-order pkt:  
§  discard (don’t buffer): no receiver buffering! 
§  re-ACK pkt with highest in-order seq # 
Wait 
udt_send(sndpkt) 
default 
 rdt_rcv(rcvpkt) 
  && notcurrupt(rcvpkt) 
  && hasseqnum(rcvpkt,expectedseqnum)  
extract(rcvpkt,data) 
deliver_data(data) 
sndpkt = make_pkt(expectedseqnum,ACK,chksum) 
udt_send(sndpkt) 
expectedseqnum++ 
expectedseqnum=1 
sndpkt =     
  make_pkt(expectedseqnum,ACK,chksum) 
 
 
Λ
GBN: receiver extended FSM 
      79 
Transport Layer 
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 ack1 rcv ack0, send pkt4 
rcv ack1, send pkt5 
 
pkt 2 timeout 
send  pkt2 
send  pkt3 
send  pkt4 
send  pkt5 
X 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  
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  
      80 
Transport Layer 
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 
      81 
Transport Layer 
Selective repeat: sender, receiver windows 
      82 
Transport Layer 
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]: 
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 
      83 
Transport Layer 
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 ack3 rcv ack0, send pkt4 
rcv ack1, send pkt5 
 
pkt 2 timeout 
send  pkt2 
X loss 
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? 
      84 
Transport Layer 
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 2 X 
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)? 
      85 
Observations 
v  With sliding windows, it is possible to fully utilize 
a link (or path), provided the window size is large 
enough.  Throughput is ~ (n/RTT) 
§  Stop & Wait is like n = 1. 
v  Sender has to buffer all unacknowledged packets, 
because they may require retransmission 
v  Receiver may be able to accept out-of-order 
packets, but only up to its buffer limits 
v  Implementation complexity depends on protocol 
details (GBN vs. SR) 
Transport Layer       86 
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 
Transport Layer       87 
v  Consider a path of bottleneck capacity C, round-trip time 
T, and maximum segment size L. What is the greatest 
throughput improvement factor that an ideal pipelined 
protocol (assuming corruptions and loss are negligible) 
can provide compared to a stop-and-wait protocol? 
A.  2L/(RT+L) 
B.  (L/R)/(T+L/R) 
C.  (RT+L)/L 
D.  (TR/L)2 
Transport Layer       88 
Quiz: Sliding Window Protocols 
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 
Transport Layer       89 
Quiz: GBN vs. SR 
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] 
B.  [24, 24], [27,28] 
C.  [27,28], [27,28] 
D.  [25], [25] 
E.  [nothing], [27, 28] 
Transport Layer       90 
Quiz: GBN vs. SR 
Transport Layer 
Transport Part 1: Summary 
v  principles behind 
transport layer services: 
§ multiplexing, 
demultiplexing 
§ reliable data transfer 
§ flow control 
§ congestion control 
v  instantiation, 
implementation in the 
Internet 
§  UDP 
v  Next Week: 
§  TCP 
•  TCP Flow Control 
•  TCF Connection 
Management 
•  TCP Congestion 
Control 
      91