Transcript Review for Quiz-1 - Communications Systems Center (CSC)

Review for Quiz-1
ECE3600 - Fall 2015
Prof. John Copeland
These slides include material from
Computer Networking: A Top Down Approach Featuring the Internet,
5th edition.
Jim Kurose, Keith Ross
Addison-Wesley.
Base material copyright 1996-2006
J.F Kurose and K.W. Ross, All Rights Reserved
Q1-1
Chapter 1 - Introduction
What’s the Internet: “nuts and bolts” view
• protocols control sending, receiving
of msgs
– e.g., TCP, IP, HTTP, FTP, PPP
• Internet: “network of networks”
– loosely hierarchical
– public Internet versus private
intranet
• Internet standards and assignments
– RFC: Request for comments
– IETF: Internet Engineering Task
Force
– IANA: assigns IP (32-bit)
addresses
– Registrars: assign domain names.
router
server
workstation
mobile
local ISP
regional ISP
company
network
Q1-2
Network edge: connectionless service
Goal: data transfer
between end systems
– same as before!
• UDP - User Datagram
Protocol [RFC 768]:
– connectionless
– unreliable data
transfer
– no flow control
– no congestion control
App’s using TCP:
• HTTP (Web), FTP (file
transfer), Telnet
(remote login), SMTP
(email)
App’s using UDP:
• streaming media,
teleconferencing, DNS,
Internet telephony
Q1-3
Network Core: Circuit Switching
End-end resources
reserved for “call”
• link bandwidth, switch
capacity
• dedicated resources: no
sharing
• circuit-like (guaranteed)
performance
• call setup required
Used by telephone system. Expensive
because unused channel capacity was
wasted.
Q1-4
Packet Switching: Statistical Multiplexing
100 Mb/s
Ethernet
A
B
statistical multiplexing
C
1.5 Mb/s
queue of packets
waiting for output
link
D
E
Sequence of A & B packets does not have fixed pattern,
shared on demand statistical multiplexing.
Contrast with TDM each host gets same slot in a repeating
TDM frame.
Q1-5
Company access: local area networks
• company/university local
area network (LAN)
connects end system to
edge router
• Ethernet:
– shared or dedicated
link connects end
system and router
– 10 Mbs, 100Mbps,
Gigabit Ethernet
• LANs: chapter 5
Q1-6
Wireless access networks
• shared wireless access network
connects end system to router
– via base station aka “access
point”
• wireless LANs:
– 802.11b/g (WiFi): 11 or 54
Mbps
• wider-area wireless access
– provided by telco operator
– 3G ~ 384 kbps
• Will it happen??
– GPRS in Europe/US
router
base
station
mobile
hosts
Q1-7
Physical Media
• Bit: propagates between
Twisted Pair (TP)
transmitter/rcvr pairs
• two insulated copper
• physical link: what lies
wires
between transmitter &
receiver
– Category 5:
• guided media:
100Mbps Ethernet
– signals propagate in
Coaxial cable:
solid media: copper,
• two concentric copper
fiber, coax
conductors
• unguided media:
– signals propagate freely, Fiber optic cable:
• glass fiber carrying light
e.g., radio
pulses, each pulse a bit
• 10’s-100’s Gbps
Q1-8
Internet structure: network of networks
• “Tier-3” ISPs and local ISPs
– last hop (“access”) network (closest to end systems)
Individual
Users
Local and tier3 ISPs are
customers of
higher tier
ISPs
connecting
them to rest
of Internet
local
ISP
Tier 3
ISP
Tier-2 ISP
local
ISP
local
ISP
local
ISP
Tier-2 ISP
Tier 1 ISP
Tier 1 ISP
Tier-2 ISP
local
local
ISP
ISP
NAP
Tier 1 ISP
Tier-2 ISP
local
ISP
Large
Organization
(Autonomous
System)
Smaller
Organization
(Autonomous
System)
Tier-2 ISP
local
ISP
Q1-9
How do loss and delay occur?
packets queue in router buffers
• packet arrival rate to link exceeds output link capacity
• packets queue, wait for turn
• Delay = (bits ahead in buffer)/(bit-rate)
packet being transmitted (delay)
A
B
packets queueing (delay)
free (available) buffers: arriving packets
dropped (loss) if no free buffers
Q1-10
Four sources of packet delay
• 1. nodal processing:
• 2. queueing
– check bit errors
– determine output link
transmission
A
– time waiting at output
link for transmission
– depends on
congestion level of
router
propagation
B
nodal
processing
queueing
Q1-11
Delay in packet-switched
networks
3. Transmission delay:
• R=link bandwidth (bps)
• L=packet length (bits)
• time to send bits into
link = L/R
transmission
A
4. Propagation delay:
• d = length of physical link
• s = propagation speed in
medium (~2x108 m/sec)
• propagation delay = d/s
Note: s and R are very
different quantities!
propagation
B
nodal
processing
queueing
Q1-12
Nodal delay
d nodal = d proc + dqueue + d trans + d prop
• dproc = processing delay
– typically a few microsecs or less
• dqueue = queuing delay (bits-in-queue/rate)
– depends on congestion
• dtrans = transmission delay (bits-in-packet/rate)
– = L/R, significant for low-speed links (dialup modems)
• dprop = propagation delay
– a few microsecs to hundreds of msecs (15 ms to Los Angeles)
Q1-13
Internet protocol stack
Ethernet
TCP/IP
• application: supporting network
applications
application
– FTP, SMTP, HTTP
• transport: process-process data
transport
transfer
– TCP, UDP
network
• network: routing of datagrams from
LLC
source to destination
link MAC
– IP, routing protocols
• link: data transfer between neighboring
physical
network elements
– PPP, Ethernet
• physical: bits “on the wire” (voltage, photons, bits/s, media, …)
Q1-14
source
message
segment
M
Ht
M
datagram Hn Ht
M
frame Hl Hn Ht
M
Encapsulation
application
transport
network
link
physical
link
physical
Ethernet LAN
switch
PPP
destination
M
Ht
M
Hn Ht
Hl Hn Ht
M
M
application
transport
network
link
physical
Hn Ht
Hl Hn Ht
M
M
network
link
physical
Hn Ht
M
router
SONET Fiber
Q1-15
Chapter 2
Applications,
Application Layer,
Application Layer Headers
Q1-16
Creating a network app
Write programs that
– run on different end systems
and
– communicate over a network.
– e.g., Web: Web server
software communicates with
browser software
little software written for devices in
network core
– network core devices do not
run user application code
– application on end systems
allows for rapid app
development, propagation
application
transport
network
data link
physical
application
transport
network
data link
physical
application
transport
network
data link
physical
Q1-17
Client-server architecture
server:
– always-on host
– permanent IP address
– server farms for
scaling
clients:
– communicate with
server
– may be intermittently
connected
– may have dynamic IP
addresses
– do not communicate
directly with each
other
Q1-18
Processes communicating
Process: program running
within a host.
• within same host, two
processes communicate
using inter-process
communication (defined
by OS).
• processes in different
hosts communicate by
exchanging messages
Client process: process
that initiates
communication
Server process: process
that waits to be
contacted
• Note: applications with
P2P architectures have
both client processes and
server processes
Q1-19
Addressing processes
• to receive messages,
process must have
identifier
• host device has
unique32-bit IP address
• Q: does IP address of
host on which process
runs suffice for
identifying the process?
– Answer: NO, many
processes can be
running on same host
• identifier includes both IP
address and port numbers
associated with process
on host.
• Example port numbers:
– HTTP server: 80
– Mail server: 25
• to send HTTP message to
gaia.cs.umass.edu web
server:
– IP address:
128.119.245.12
– Port number: 80
Q1-20
Application Layer
HTTP overview
HTTP: hypertext transfer
protocol
• Web’s application layer
protocol
• client/server model
– client: browser that
requests, receives,
“displays” Web
objects
– server: Web server
sends objects in
response to requests
• HTTP 1.0: RFC 1945
• HTTP 1.1: RFC 2068
PC running
Explorer
Server
running
Apache Web
server
Mac running
Navigator
Q1-21
Persistent HTTP
Nonpersistent HTTP issues:
• requires 2 RTTs per object
• OS overhead for each TCP
connection
• browsers often open parallel
TCP connections to fetch
referenced objects
Persistent HTTP
• server leaves connection
open after sending response
• subsequent HTTP messages
between same client/server
sent over open connection
Persistent without pipelining:
• client issues new request
only when previous
response has been received
• one RTT for each referenced
object
Persistent with pipelining:
• default in HTTP/1.1
• client sends requests as
soon as it encounters a
referenced object
• as little as one RTT for all
the referenced objects [plus
the sum of transfer times]
Q1-22
FTP: the file transfer protocol
user
at host
FTP
FTP
user
client
interface
local file
system
file transfer
FTP
server
remote file
system
• transfer file to/from remote host
• client/server model
– client: side that initiates transfer (either to/from remote)
– server: remote host
• ftp: RFC 959
• ftp server: port 21
Q1-23
FTP: separate control, data
connectionsTCP control connection
port 21
• FTP client contacts FTP server
at port 21, specifying TCP as
transport protocol
TCP data connection
FTP
FTP
2 Modes
• Client obtains authorization
client Active : Server port 20 -> server
over control connection
Client listening high port
• Client browses remote
Passive : Client -> Server,
directory by sending
high-high ports
commands over control
• Server opens another TCP
connection.
data connection to transfer
• When server receives file
another file.
transfer command, server
• Control connection: “out of
opens 2nd TCP connection (for
band”
file) to client
• After transferring one file,
• FTP server maintains “state”:
server closes data connection.
current directory, earlier
authentication
Q1-24
Electronic Mail: mail servers
user
agent
Mail Servers
• mailbox contains incoming
messages for user
• message queue of outgoing
(to be sent) mail messages
• SMTP protocol between mail
servers to send email
messages
– client: sending mail server
– “server”: receiving mail
server
Recently, Enhanced SMTP (ESMTP)
is used to provide authentication,
and encryption for privacy.
mail
server
SMTP
SMTP
mail
server
user
agent
SMTP
user
agent
mail
server
user
agent
user
agent
user
agent
Q1-25
Mail message format
SMTP: protocol for
exchanging email msgs
RFC 822: standard for text
message format:
• header lines, e.g.,
– To:
– From:
– Subject:
different from SMTP
commands!
header
blank
line
body
• body
– the “message”, ASCII
characters only
Q1-26
Mail access protocols
user
agent
SMTP
SMTP
sender’s mail
server
access
protocol
user
agent
receiver’s mail
server
• SMTP: delivery/storage to receiver’s server
• Mail access protocol: retrieval from server
– POP: Post Office Protocol [RFC 1939]
• authorization (agent <-->server) and download
– IMAP: Internet Mail Access Protocol [RFC 1730]
• more features (more complex)
• manipulation of stored msgs on server
– HTTP: Hotmail , Yahoo! Mail, etc.
Transport Layer Security (TLS), like SSL for HTTP > HTTPS]
Q1-27
POP3 and IMAP
More about POP3
• Previous example uses
“download and delete”
mode.
• Bob cannot re-read email if he changes client
• “Download-and-keep”:
copies of messages on
different clients
• POP3 is stateless
across sessions
IMAP
• Keep all messages in
one place: the server
• Allows user to organize
messages in folders
• IMAP keeps user state
across sessions:
– names of folders and
mappings between
message IDs and
folder name
Q1-28
DNS: Domain Name System
People: many identifiers:
– SSN, name, passport #
Internet hosts, routers:
– IP address (32 bit) - used
for addressing datagrams
– “name”, e.g.,
www.yahoo.com - used
by humans
Q: map between IP
addresses and name ?
Domain Name System:
• distributed database
implemented in hierarchy of
many name servers
• application-layer protocol
host, routers, name servers
to communicate to resolve
names (address/name
translation)
– note: core Internet
function, implemented as
application-layer protocol
– complexity at network’s
“edge”
Q1-29
Distributed, Hierarchical Database
Root DNS Servers
.com DNS servers
yahoo.com
amazon.com
DNS servers DNS servers
.org DNS servers
pbs.org
DNS servers
.edu DNS servers
poly.edu
umass.edu
DNS serversDNS servers
Client wants IP for www.amazon.com; 1st approx:
• Client* queries a root server to find com DNS server
• Client* queries com DNS server to get amazon.com DNS
server
• Client* queries amazon.com DNS server to get IP
address for www.amazon.com
– * This is usually your local DNS server, that does this "recursive"
search for you.
Q1-30
TLD and Authoritative Servers
• Top-level domain (TLD) servers: responsible for com, org, net, edu,
etc, and all top-level country domains uk, fr, ca, jp.
– Network solutions maintains servers for com TLD
– Educause for edu TLD
– [2007 - TLD servers share responsibilities]
• Authoritative DNS servers: organization’s DNS servers, providing
authoritative hostname to IP mappings for organization’s servers
(e.g., Web and mail).
– Can be maintained by organization or service provider
• Local DNS servers: organization’s DNS servers located on various
subnets to provide DNS lookups for hosts on the subnet. May not
be accessible from outside the subnet. Their IP addresses are part
of the host's network configuration (manual setup or DHCP*).
* DHCP - dynamic host configuration protocol (automatic network configuration)
Q1-31
Example
root DNS server
• Host at cis.poly.edu
2
wants IP address for
3
gaia.cs.umass.edu
• Host sends a "recursionrequested" query
request to dns.poly.edu. local DNS server
dns.poly.edu
• [Host is doing a nonrecursive search]
1
8
• Local DNS server does a
"recursive" search. This
requires contacting
requesting host
several other DNS
cis.poly.edu
servers before the final
answer is given to host.
TLD DNS server
4
5
7
6
authoritative DNS server
dns.cs.umass.edu
gaia.cs.umass.edu
Q1-32
DNS records
DNS: distributed db storing resource records
(RR) RR format: (name, value, type, ttl)
• Type=A
– name is hostname
– value is IP address
• Type=CNAME
– name is alias name for some
“canonical” (the real) name
www.ibm.com is really
• Type=NS
servereast.backup2.ibm.com
– name is domain (e.g.
– value is canonical name
gatech.com) {assigned by
a “registrar”}
• Type=MX
– value is hostname of
– value is name of mailserver
authoritative name server
associated with name
for this domain
Q1-33
P2P file sharing
Example
• Alice runs P2P client
application on her
notebook computer
• Intermittently connects
to Internet; gets new IP
address for each
connection
• Asks for “Hey Jude”
• Application displays
other peers that have
copy of Hey Jude.
• Alice chooses one of
the peers, Bob.
• File is copied from
Bob’s PC to Alice’s
notebook: HTTP
• While Alice downloads,
other users uploading
from Alice.
• Alice’s peer is both a
Web client and a
transient Web server.
All peers are servers =
highly scalable!
Highly insecure!
Q1-34
Transport Layer
Internet transport protocols (2 of many)
TCP services:
UDP service:
• connection-oriented: setup
required between client and
server processes
• reliable transport between
sending and receiving process
• flow control: sender won’t
overwhelm receiver
• congestion control: throttle
sender when network
overloaded
• does not provide: timing,
minimum bandwidth
guarantees
• unreliable data transfer
between sending and
receiving process
• does not provide:
connection setup,
reliability, flow control,
congestion control,
timing, or bandwidth
guarantee
Q: why bother? Why is
there a UDP?
Q1-35
Socket-programming using TCP
Socket: a door between application process and endend-transport protocol (UCP or TCP)
TCP service: reliable transfer of bytes from one
process to another
controlled by
application
developer
controlled by
operating
system
process
process
socket
TCP with
buffers,
variables
host or
server
internet
socket
TCP with
buffers,
variables
controlled by
application
developer
controlled by
operating
system
host or
server
Q1-36
Socket programming with TCP
Client must contact server
• server process must first be
running
• server must have created
socket that welcomes client’s
contact (Listening Socket)
Client contacts server by:
• creating client-local TCP
socket
• specifying IP address, port
number of server process
• When client creates socket:
client TCP establishes
connection to server TCP
• When contacted by client,
server TCP creates new
socket for server process to
communicate with client
– allows server to talk with
multiple clients
– source port numbers used
to distinguish clients (more
in Chap 3)
application viewpoint
TCP provides reliable, in-order
transfer of bytes (“pipe”)
between client and server
Q1-37
Chapter 3 - Transport Layer
TCP and UDP, Ports and Sockets
Covered on Quiz 2 (Fall 2014)
TCP Flow and Congestion Control
TCP Flags, Sequence and Ack. No.s
IP Subnets, Routers, Address Blocks
IP Subnets
Q1-38
Transport services and protocols
• provide logical communication
between app processes
running on different hosts
• 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
• more than one transport
protocol available to apps
– Internet: TCP and UDP
application
transport
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
application
transport
network
data link
physical
Q1-39
Internet transport-layer protocols
• reliable, in-order
delivery (TCP)
– congestion control
– flow control
– connection setup
• unreliable, unordered
delivery: UDP
– no-frills extension of
“best-effort” IP
• services not available:
application
transport
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
application
transport
network
data link
physical
– delay guarantees
– bandwidth guarantees
Q1-40
TCP Multiplexing / Demultiplexing
Multiplexing at send host:
gathering data from multiple
sockets, enveloping data with
header (later used for
demultiplexing)
Demultiplexing at rcv host:
delivering received segments to
correct socket (Listening Port
not shown)
= socket
application
transport
network
link
= process
P3
P1
P1
application
transport
network
P2
P4
application
transport
network
link
link
physical
host 1
physical
host 2
physical
host 3
Q1-41
Connection-oriented demux
• TCP socket identified
by 4-tuple:
–
–
–
–
source IP address
source port number
dest IP address
dest port number
• recv host uses all
four values to direct
segment to
appropriate socket
• Server host may
support many
simultaneous TCP
sockets:
– each socket identified by
its own 4-tuple
• Web servers have
different sockets for
each connecting client
– non-persistent HTTP will
have different socket for
each request
Q1-42
UDP - Connectionless demux
DatagramSocket serverSocket = new DatagramSocket(6428);
P2
SP: 6428
SP: 6428
DP: 9157
DP: 5775
SP: 9157
client
IP: A
P1
P1
P3
DP: 6428
SP: 5775
server
IP: C
DP: 6428
Client
IP:B
Source Port, SP, (and Source IP) provides “return address”
Only one socket per local UDP Port Number.
Q1-43
UDP: User Datagram Protocol [RFC 768]
• “no frills,” “bare bones”
Internet transport protocol
• “best effort” service, UDP
segments may be:
– lost
– delivered out of order to
app
• connectionless:
– no handshaking between
UDP sender, receiver
– each UDP segment
handled independently of
others
Why is there a UDP?
• no connection establishment
(which can add delay)
• simple: no connection state
at sender, receiver
• small segment header
• no congestion control: UDP
can blast away as fast as
desired
• Single thread and socket for
each local server port
number.
Q1-44
UDP: more
• often used for streaming
multimedia apps
– loss tolerant
Length, in
bytes of UDP
– rate sensitive
• other UDP uses
– DNS
– SNMP
• reliable transfer over UDP:
add reliability at application
layer
– application-specific error
recovery!
segment,
including
header
32 bits
source port #
dest port #
length
checksum
Application
data
(message)
UDP segment format
Q1-45
UDP checksum
Goal: detect “errors” (e.g., flipped bits) in
transmitted segment
Receiver:
Sender:
• treat segment contents as •
sequence of 16-bit integers
• checksum: addition (1’s
complement sum) of
header and some parts of •
the IP header)
• sender puts bit-wise
complement (-checksum)
value into UDP checksum
field
compute checksum of
received segment,
included checksum
field.
check if computed
checksum equals zero :
– NO - error detected
– YES - no error detected.
But maybe errors
nonetheless? More later ….
Q1-46
Internet Checksum Example
• Note
– When adding numbers, a carry out from the most
significant bit needs to be shifted (>>16) and
added to the result
• Example: add two 16-bit integers (1's compliment)
BINARY ADD 1
1
1
1
1
1
1
0
0
1
0
0
1
1
1
0
0
1
0
0
1
1
1
0
0
1
0
0
1
1
1
0
0
1
1
1
0
1
1
1
0
1
1
1
0
1
1
1
0
1
1
sum
bit-invert
checksum
1
0
1
1
1
0
1
1
1
0
1
1
1
1
0
1
1
0
0
1
0
0
0
1
0
0
0
1
0
0
0
0
1
1
wraparound
Q1-47
Reliable Data Transport
Problem
Solution
Packet may arrive with errors.
Add checksum, CRC, or hash.
Packet may not arrive.
Receiver sends “ACK” back. If
ACK not received, packet re-sent.
Sender may wait forever for ACK.
Timeout timer added to sender.
ACK may not arrive, dup. sent.
Add sequence no.s to detect dups.
Packets may arrive out-of-order.
Buffer packets to rearrange order.
Inefficient to send one pkt per RT
Have a “window” to send before ACK
(pipelining).
Missing packet early in window.
“Go-Back-N” to last in-order packet.
“Go-Back-N” inefficient.
“Selective Repeat” to fill in gaps only.
---- Also in TCP ---
----
Packets may be different sizes.
Sequence number for each byte.
Slow down when network
“Slow-Start”, or "Multiplicative
congested (as detected by RTO or
Decrease" to reduce transmit window.
triple duplicate ACKs.
Receiver includes “space left” in every
Know when receiver buffer will be
ACK.
full.
Transport Layer
Q1-48
TCP: Overview
RFCs: 793, 1122, 1323,
2018, 2581
• full duplex data:
• point-to-point:
– bi-directional data flow in
– one sender, one receiver
same connection
• reliable, in-order byte steam:
– MSS: maximum segment
size
– no “message boundaries”
• connection-oriented:
• pipelined:
– handshaking (exchange of
– TCP congestion and flow
control msgs) init’s sender,
receiver state before data
control set window size
exchange
• send & receive buffers
socket
door
application
writes data
application
reads data
• flow controlled:
– sender will not overwhelm
receiver
socket
door
TCP
send buffer
TCP
receive buffer
segment
Q1-49
TCP segment structure
32 bits
URG: urgent data
(generally not used)
ACK: ACK #
valid
PSH: push data now
(end of block)
RST, SYN, FIN:
connection estab
(setup, teardown
commands)
Internet
checksum
(as in UDP)
source port #
dest port #
sequence number
counting
by bytes
of data
(not segments!)
acknowledgement number
head not
UA P R S F
len used
checksum
Receive window
Urg data pointer
Options (variable length, MSS)
# bytes
rcvr willing
to accept
application
data
(variable length)
Q1-50
TCP seq. #’s and ACKs
Seq. #’s:
– byte stream
“number” of first
byte in segment’s
data
ACKs:
– seq # of next byte
expected from other
side
– cumulative ACK
Q: how receiver handles
out-of-order segments
– A: TCP spec
doesn’t say, - up to
implementor
Host A
User
types
‘C’
Host B
host ACKs
receipt of
‘C’, echoes
back ‘C’
host ACKs
receipt
of echoed
‘C’
simple telnet scenario
time
Q1-51
Maximum Segment Size (MSS), in bytes
The initial segments (the SYN and SYN-ACK) contain the MSS in an option
field. It stays constant after this.
This tells the other host the maximum size of a segment that can be
handled by their local network (without fragmentation).
Examples, one host may say it's MSS value is 1400, the other may say it's
MSS value is 1420.
Since segments have to transverse both local networks, the smaller MSS
value is used for the connection.
TCP rules involving Window sizes are in units of MSS (bytes), not number of
segments.
For simplification, examples may say "the host is sending maximum size
segments," so that 1 MSS = 1 segment. Sometimes this is implied without
being stated in problems.
MSS includes the TCP header bytes (40 to 64) and data bytes, but not the IP
header bytes (20). Since Ethernet and WiFi limit datagram size to 1500
bytes, MSS is never larger than 1480 bytes when either host is on a LAN.
Q1-52
TCP Round Trip Time and Timeout
EstimatedRTT[new] = (1-)* EstimatedRTT[old]
+  * SampleRTT[new]
• Exponential weighted moving average
• influence of past sample decreases exponentially fast
• typical value:  = 0.125
Setting the timeout
EstimtedRTT plus “safety margin”
large
variation in EstimatedRTT -> larger safety margin
first estimate how much SampleRTT deviates from EstimatedRTT:
DevRTT[new] = (1-) * DevRTT[old] +
 * |SampleRTT[new] - EstimatedRTT[old]|
(typically,  = 0.25, note absolute value bars, ||)
Also note: Old value of EstimatedRTT is used.
TimeoutInterval: RTO = EstimatedRTT + 4 * DevRTT
Q1-53
Running Average for Calculating the Retransmit Time Out, RTO
Round results up to 1 ms. Alpha = 1/8 (0.125) and Beta = 1/4 (0.250)
SampleRTT[new]
- EstimatedRTT[old]
SampleRTT
EstimatedRTT
DevRTT
TimeOut
Measured
Round-Trip
Time = M
40
90
A=Average
RTT
Alpha = 1/8
60
64
Deviation
(+/-)
(M - old-A)
15
+30
D = Average
Deviation
Beta = 1/4
10
15
RTO =
A + 4D
30
60
-34
-34
20
140
100
128
124
A = 0.875 * 60 + 0.125 * 90 = 63.75 -> 64
D = 0.75 * 10 + 0.25 * | 30 | = 15
A = 0.875 * 64 + 0.125 * 30 = 59.75 -> 60
D = 0.75 * 15 + 0.25 * | -34 | = 19.75 -> 20
Q1-54
TCP Flow control
LastByte
InBuffer
LastByte
ACKed
<- Byte No.s
Receiver-Window =
• spare room in buffer
= LastByteInBuffer LastByteACKed
• Receiver advertises
spare room by including
value of RcvWindow in
every segment (TCP
header "Window" field)
• Sender limits data to
RcvWindow
– guarantees receive
buffer doesn’t
overflow
flow control
sender won’t overflow
receiver’s buffer by
transmitting too much,
too fast
Q1-55
Causes / costs of congestion
Each host sends in data (average bits per second).
Buffer output is out (maximum rate is C)
Host A
• two senders,
two receivers
• one router,
infinite buffers
• no
retransmission
Host B
lout
lin : original data
unlimited shared
output link buffers
• large delays
when congested
• maximum
achievable
throughput
Q1-56
TCP Congestion Control
• sender limits transmission:
LastByteSent-LastByteAcked
 CongWin
• Roughly*,
rate =
CongWin
Bytes/sec
RTT
• CongWin is dynamic, function of
perceived network congestion.
• The sender uses the smaller
value of CongWin and or
Window (receiver's Window)
* This is true when this window-limited
rate is less that the media bandwidth
in bytes per second.
How does sender
perceive congestion?
• loss event = timeout or
3 duplicate ACKs
• TCP sender reduces rate
(CongWin) after loss event
three mechanisms:
– AIMD (additive increase,
multiplicative decrease)
– slow start initially
(exponential growth until
threshold reached)
– conservative after
timeout events (slowstart up to CongWin)
Q1-57
TCP Slow Start
– double CongWin every
RTT
– done by adding a byte to
CongWin for every new
byte ACK'ed.
Host A
Host B
RTT
• When connection
begins*, increase rate
exponentially until first
loss event:
SYN and SYN-ACK: TCP headers contain MSS
values (in option field) and initial Segment
Numbers.
• Summary: initial rate is
slow but data rate
ramps up exponentially
fast (until the Receiver
Window is reached)
time
*Also done after a Time Out, but changes to Additive Increase when the
Threshold is reached.
Q1-58
TCP congestion control:
sender congestion window: "CongWin"
Saw tooth
behavior: probing
for bandwidth
congestion window size
• Approach: increase transmission rate (window size),
probing for usable bandwidth, until loss occurs
– multiplicative decrease: cut CongWin in half after loss
indicated by 3 duplicate ACKs (to MSS after Time Out*).
– additive increase: increase CongWin by 1 MSS every
RTT until loss detected by 3 duplicate ACKs (or Time
Out*)
congestion
window
24 Kbytes
16 Kbytes
8 Kbytes
time
time
*After a Time Out, CongWin increases by doubling every RTT until 1/2 old CongWin reached
Q1-59
Refinement
Time-Out
(CongWin = 16)
CongWin (MSS)
Q: When should the
exponential
increase switch to
linear (after RTO)?
A: When CongWin
gets to 1/2 of its
value before
timeout.
Implementation:
• Variable Threshold
• At loss event, Threshold is
set to 1/2 of CongWin value
just before loss event.
Fast Recovery (3 dups)
(Fast Retransmission
replaced missing segment)
TCP Reno
Time-Out (dt>RTO)
(Time/RTT)
If a Fast Retransmit fixes the
gap in ACKs before a timeout,
TCP can skip the Slow-Start and
immediately use Additive
Increase, starting at half the
previous CongWin.
Q1-60
Fast Retransmit (to avoid Timeout)
• Time-out period often
• If sender receives 4
relatively long:
ACKs for the same data
– long delay before
(3 dups), it supposes that
resending lost packet
segment after ACKed
• Detect lost segments
data was lost:
via duplicate ACKs.
– Fast Retransmit:
– Sender often sends
resend segment
many segments
before timer expires.
back-to-back
– If segment is lost, When resent packet is ACKed before a
there will likely be timeout, go to Fast Recovery Mode:
- Halve Sender-Window, "CongWin"
many duplicate
- Increase CongWin by 1 MSS per
ACKs.
CongWin bytes sent and Acked.
Q1-61
CongWin <= Threshold: Doubles each RTT (add MSS for each ACK)
CongWin > Threshold: Adds MSS each RTT
Time Out: Threshold = 1/2 CongWin, CongWin = 1 (Slow-Start)
3-Dup Ack: Threshold = 1/2 CongWin, CongWin = Threshold (Fast Recovery)
CongWin / mss
Time Out
Threshold = 20
3 Dup. ACKs
12
6
Q1-62
Fairness
Fairness and UDP
• Multimedia apps often do not
use TCP
– do not want rate throttled by
congestion control
• Instead use UDP:
– pump audio/video at
constant rate, tolerate
packet loss
• Research area: make UDP
more TCP friendly
– Solution: reserve 50% of
router buffer space for TCP
segments (excess UDP
segments dropped).
Fairness and parallel TCP
connections
• nothing prevents app from
opening parallel
connections between 2
hosts.
• Web browsers do this
• Example: link of rate R
supporting 9 connections;
– new app starts 1 TCP, gets
rate R/10
– new app starts 9 TCPs, gets
R/2 !
Q1-63