Transcript class10

Midterm Review
In class, 9:30-11 am, Tu. 2/8
Closed Book
One 8.5” by 11” sheet of paper
permitted (single side)
Lecture 1
• Internet Architecture
• Network Protocols
• Network Edge
• A taxonomy of communication networks
A Taxonomy of Communication Networks
• The fundamental question: how is data
transferred through net (including edge & core)?
• Communication networks can be classified based
on how the nodes exchange information:
Communication
Networks
Switched
Communication
Network
Circuit-Switched
Communication
Network
TDM
FDM
Broadcast
Communication
Network
Packet-Switched
Communication
Network
Datagram
Network
Virtual Circuit Network
Packet Switching: Statistical Multiplexing
10 Mbs
Ethernet
A
B
statistical multiplexing
C
1.5 Mbs
queue of packets
waiting for output
link
D
E
Sequence of A & B packets does not have fixed
pattern  statistical multiplexing.
In TDM each host gets same slot in revolving TDM
frame.
Packet Switching versus Circuit Switching
• Circuit Switching
– Network resources (e.g., bandwidth) divided into
“pieces” for allocation
– Resource piece idle if not used by owning call (no
sharing)
– NOT efficient !
• Packet Switching:
– Great for bursty data
– Excessive congestion: packet delay and loss
– protocols needed for reliable data transfer,
congestion control
Packet Switching versus Circuit Switching
Packet switching allows more users to use network!
• 1 Mbit link
• Each user:
– 100 kbps when “active”
– active 10% of time
N users
• Circuit-switching:
– 10 users
• Packet switching:
– with 35 users, probability >
10 active less than .0004
1 Mbps link
Datagram Packet Switching
• Each packet is independently switched
– Each packet header contains destination address
which determines next hop
– Routes may change during session
• No resources are pre-allocated (reserved) in
advance
• Example: IP networks
Virtual-Circuit Packet Switching
• Hybrid of circuit switching and packet
switching
– All packets from one packet stream are sent along a
pre-established path (= virtual circuit)
– Each packet carries tag (virtual circuit ID), tag
determines next hop
• Guarantees in-sequence delivery of packets
• However, packets from different virtual
circuits may be interleaved
• Q. What is the difference btw. circuit
switching and virtual-circuit packet switching?
Lecture 2
• Network access and physical media
• Internet structure and ISPs
• Delay & loss in packet-switched
networks
• Protocol layers, service models
Internet structure: network of networks
• “Tier-3” ISPs and local ISPs
– last hop (“access”) network (closest to end systems)
– Tier-3: Turkish Telecom, Minnesota Regional Network
local
ISP
Local and tier3 ISPs are
customers of
higher tier
ISPs
connecting
them to rest
of Internet
Tier 3
local
local
ISP
Tier-2 ISP
ISP
ISP
ISP
Tier-2 ISP
Tier 1 ISP
Tier 1 ISP
Tier-2 ISP
local
local
ISP
ISP
local
NAP
Tier 1 ISP
Tier-2 ISP
local
ISP
Tier-2 ISP
local
ISP
Four sources of packet delay
• 1. processing:
• 2. queueing
– check bit errors
– time waiting at output
link for transmission
– determine output link
– depends on congestion
level of router
transmission
A
propagation
B
processing
queueing
Delay in packet-switched networks
3. Transmission delay:
4. Propagation delay:
• R=link bandwidth (bps)
• d = length of physical link
• L=packet length (bits)
• s = propagation speed in
medium (~2x108 m/sec)
• time to send bits into
link = L/R
transmission
A
• propagation delay = d/s
Note: s and R are very
different quantities!
propagation
B
processing
queueing
Internet protocol stack
• application: supporting network applications
– FTP, SMTP, HTTP
• transport: host-host data transfer
– TCP, UDP
• network: routing of datagrams from source
to destination
– IP, routing protocols
• link: data transfer between neighboring
network elements
– PPP, Ethernet
• physical: bits “on the wire”
application
transport
network
link
physical
Application Layer
• Principles of app layer protocols
– Application architectures and requirements
• Web and HTTP
• FTP
• Electronic Mail: SMTP, POP3, IMAP
• DNS
• Socket Programming
Application architectures
• Client-server
• Peer-to-peer (P2P)
• Hybrid of client-server and P2P
Client-server archicture
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
Pure P2P architecture
• no always on server
• arbitrary end systems
directly communicate
• peers are intermittently
connected and change IP
addresses
• example: Gnutella
Highly scalable
But difficult to manage
Hybrid of client-server and P2P
Napster
– File transfer P2P
– File search centralized:
• Peers register content at central server
• Peers query same central server to locate content
Instant messaging
– Chatting between two users is P2P
– Presence detection/location centralized:
• User registers its IP address with central server when it
comes online
Internet transport protocols services
TCP service:
UDP service:
• connection-oriented: setup
required between client and
server processes
• unreliable data transfer
between sending and
receiving process
• reliable transport between
sending and receiving process
• does not provide:
connection setup,
reliability, flow control,
congestion control, timing,
or bandwidth guarantee
• flow control: sender won’t
overwhelm receiver
• congestion control: throttle
sender when network
overloaded
• does not provide: timing,
minimum bandwidth guarantees
Q: why bother? Why is
there a UDP?
HTTP connections
Nonpersistent HTTP
Persistent HTTP
• At most one object is
sent over a TCP
connection.
• Multiple objects can be
sent over single TCP
connection between
client and server.
• HTTP/1.0 uses
nonpersistent HTTP
• HTTP/1.1 uses
persistent connections
in default mode
• HTTP Message, Format, Response, Methods
• HTTP cookies
Response Time of HTTP
Nonpersistent HTTP issues:
Persistent without pipelining:
• requires 2 RTTs per object
• client issues new request
only when previous
response has been received
• OS must work and allocate
host resources for each TCP
connection
• but 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
are sent over connection
• 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
Web caches (proxy server)
Goal: satisfy client request without involving origin server
• user sets browser: Web
accesses via cache
• browser sends all HTTP
requests to cache
– object in cache: cache
returns object
origin
server
client
Proxy
server
– else cache requests object
from origin server, then
returns object to client
– Consistency problem
• Why web caching?
client
origin
server
Caching example (3)
Install cache
origin
servers
• suppose hit rate is .4
Consequence
• 40% requests will be satisfied
almost immediately
public
Internet
• 60% requests satisfied by origin
server
• utilization of access link reduced
to 60%, resulting in negligible
delays (say 10 msec)
• total delay = Internet delay +
access delay + LAN delay
= .6*2 sec + .6*.01 secs +
milliseconds < 1.3 secs
1.5 Mbps
access link
institutional
network
10 Mbps LAN
institutional
cache
FTP: separate control, data connections
• FTP client contacts FTP server
at port 21, specifying TCP as
transport protocol
• Client obtains authorization over FTP
control connection
client
TCP control connection
port 21
TCP data connection
port 20
FTP
server
• Client browses remote directory
• Server opens a second TCP
by sending commands over
data connection to transfer
control connection.
another file.
• When server receives a
• Control connection: “out of
command for a file transfer, the
band”
server opens a TCP data
connection to client
• FTP server maintains “state”:
current directory, earlier
• After transferring one file,
authentication
server closes connection.
Electronic Mail: mail servers
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
• Example 
– If the sending mail
server cannot deliver the
message, it is queued
user
agent
mail
server
SMTP
SMTP
mail
server
user
agent
SMTP
user
agent
user
agent
mail
server
user
agent
user
agent
DNS services
•
Hostname to IP address
translation
–
•
•
Host aliasing
–
Canonical and alias names
–
E.g., dell.com www.dell.com
Why not centralize DNS?
• single point of failure
• traffic volume
• distant centralized database
• maintenance
Mail server aliasing
–
•
E.g., www.northwestern.edu
DNS
E.g., [email protected]
Load distribution
–
Replicated Web servers: set of IP
addresses for one canonical name
–
E.g., cnn.com
doesn’t scale!
DNS example
root name server
Root name server:
• may not know
authoritative name
server
• may know
intermediate name
server: who to
contact to find
authoritative name
server
6
2
7
local name server
dns.eurecom.fr
1
8
3
intermediate name server
dns.nwu.edu
4
5
authoritative name server
dns.cs.nwu.edu
requesting host
surf.eurecom.fr
www.cs.nwu.edu
DNS: iterated queries
recursive query:
root name server
2
• puts burden of name
resolution on
contacted name
server
• heavy load?
iterated query:
• contacted server
replies with name of
server to contact
• “I don’t know this
name, but ask this
server”
iterated query
3
4
7
local name server
dns.eurecom.fr
1
8
intermediate name server
dns.umass.edu
5
6
authoritative name server
dns.cs.umass.edu
requesting host
surf.eurecom.fr
gaia.cs.umass.edu
Transport Layer
• Transport-layer services
• Multiplexing and demultiplexing
• Connectionless transport: UDP
• Principles of reliable data transfer
• TCP
– Segment structures
– Flow control
– Congestion control
Demultiplexing
• UDP socket identified
by two-tuple:
(dest IP address, dest
port number)
• When host receives
UDP segment:
– checks destination
port number in
segment
– directs UDP segment
to socket with that
port number
• 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
Rdt1.0: reliable transfer over a reliable channel
• underlying channel perfectly reliable
– no bit errors
– no loss of packets
• separate FSMs for sender, receiver:
– sender sends data into underlying channel
– receiver read data from underlying channel
Wait for
call from
above
rdt_send(data)
packet = make_pkt(data)
udt_send(packet)
sender
Wait for
call from
below
rdt_rcv(packet)
extract (packet,data)
deliver_data(data)
receiver
Rdt2.0: channel with bit errors
• underlying channel may flip bits in packet
– recall: UDP checksum to detect bit errors
• 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
• new mechanisms in rdt2.0 (beyond rdt1.0):
– error detection
– receiver feedback: control msgs (ACK,NAK) rcvr->sender
rdt2.0: FSM specification
rdt_send(data)
snkpkt = make_pkt(data, checksum)
udt_send(sndpkt)
rdt_rcv(rcvpkt) &&
isNAK(rcvpkt)
Wait for
Wait for
call from
ACK or
udt_send(sndpkt)
above
NAK
rdt_rcv(rcvpkt) && isACK(rcvpkt)
L
sender
receiver
rdt_rcv(rcvpkt) &&
corrupt(rcvpkt)
udt_send(NAK)
Wait for
call from
below
rdt_rcv(rcvpkt) &&
notcorrupt(rcvpkt)
extract(rcvpkt,data)
deliver_data(data)
udt_send(ACK)
rdt2.0 has a fatal flaw!
What happens if ACK/NAK
corrupted?
• sender doesn’t know what
happened at receiver!
• can’t just retransmit:
possible duplicate
Handling duplicates:
• sender adds sequence
number to each pkt
• sender retransmits current
pkt if ACK/NAK garbled
• receiver discards (doesn’t
deliver up) duplicate pkt
stop and wait
Sender sends one packet,
then waits for receiver
response
rdt2.2: a NAK-free protocol
• same functionality as rdt2.1, using ACKs only
• instead of NAK, receiver sends ACK for last pkt
received OK
– receiver must explicitly include seq # of pkt being ACKed
• duplicate ACK at sender results in same action as
NAK: retransmit current pkt
rdt3.0: channels with errors and loss
New assumption:
underlying channel can
also lose packets (data
or ACKs)
– checksum, seq. #, ACKs,
retransmissions will be of
help, but not enough
Approach: sender waits
“reasonable” amount of
time for ACK
• retransmits if no ACK
received in this time
• if pkt (or ACK) just delayed
(not lost):
– retransmission will be
duplicate, but use of seq.
#’s already handles this
– receiver must specify seq
# of pkt being ACKed
• requires countdown timer
Go-Back-N
Sender:
• k-bit seq # in pkt header
• “window” of up to N, consecutive unack’ed pkts allowed
• ACK(n): ACKs all pkts up to, including seq # n - “cumulative ACK”
– may deceive duplicate ACKs (see receiver)
• Single timer for all in-flight pkts
• timeout(n): retransmit pkt n and all higher seq # pkts in window
Selective repeat: sender, receiver windows
TCP segment structure
URG: urgent data
(generally not used)
ACK: ACK #
valid
PSH: push data now
(generally not used)
RST, SYN, FIN:
connection estab
(setup, teardown
commands)
Internet
checksum
(as in UDP)
32 bits
source port #
dest port #
sequence number
acknowledgement number
head not
UA P R S F
len used
checksum
Receive window
Urg data pnter
Options (variable length)
application
data
(variable length)
counting
by bytes
of data
(not segments!)
# bytes
rcvr willing
to accept
TCP Round Trip Time and Timeout
EstimatedRTT = (1- )*EstimatedRTT + *SampleRTT
• Exponential weighted moving average
• influence of past sample decreases exponentially fast
• typical value:  = 0.125
Fast Retransmit
• Time-out period often
relatively long:
– long delay before
resending lost packet
• Detect lost segments
via duplicate ACKs.
– Sender often sends many
segments back-to-back
– If segment is lost, there
will likely be many
duplicate ACKs.
• If sender receives 3
ACKs for the same
data, it supposes that
segment after ACKed
data was lost:
– fast retransmit: resend
segment before timer
expires
TCP Flow control: how it works
• Rcvr advertises spare
room by including value
of RcvWindow in
segments
(Suppose TCP receiver
discards out-of-order
segments)
• spare room in buffer
= RcvWindow
= RcvBuffer-[LastByteRcvd LastByteRead]
• Sender limits unACKed
data to RcvWindow
– guarantees receive
buffer doesn’t overflow
TCP Congestion Control
• end-end control (no network
assistance)
How does sender
perceive congestion?
• sender limits transmission:
• loss event = timeout or
3 duplicate acks
LastByteSent-LastByteAcked
 CongWin
• Roughly,
rate =
CongWin
Bytes/sec
RTT
• CongWin is dynamic, function
of perceived network
congestion
• TCP sender reduces
rate (CongWin) after
loss event
three mechanisms:
– Slow start
– AIMD
– Exponential backoff
TCP Phases
Refinement
• After 3 dup ACKs:
– CongWin is cut in half
– window then grows linearly
• But after timeout event:
Philosophy:
• 3 dup ACKs indicates
network capable of
delivering some segments
• timeout before 3 dup
ACKs is “more alarming”
– Enter “slow start”
– CongWin instead set to 1
MSS;
– window then grows
exponentially
– to a threshold, then grows
linearly
• In exponential backoff:
– RTO doubled after each
successive timeout
Why is TCP fair?
Two competing sessions:
• Additive increase gives slope of 1, as throughout increases
• multiplicative decrease decreases throughput proportionally
equal bandwidth share
R
loss: decrease window by factor of 2
congestion avoidance: additive increase
loss: decrease window by factor of 2
congestion avoidance: additive increase
Connection 1 throughput R
Delay modeling - homework
Q: How long does it take to
receive an object from a
Web server after sending
a request?
Ignoring congestion, delay is
influenced by:
• TCP connection establishment
• data transmission delay
• slow start
Notation, assumptions:
• Assume one link between
client and server of rate R
• S: MSS (bits)
• O: object size (bits)
• no retransmissions (no loss,
no corruption)
Window size:
• First assume: fixed
congestion window, W
segments
•
Then dynamic window,
modeling slow start
Fixed congestion window (1)
First case:
WS/R > RTT + S/R: ACK for
first segment in window
returns before window’s
worth of data sent
delay = 2RTT + O/R
Fixed congestion window (2)
Second case:
• WS/R < RTT + S/R:
wait for ACK after
sending window’s
worth of data sent
delay = 2RTT + O/R
+ (K-1)[S/R + RTT - WS/R]
Where K=O/WS
TCP Delay Modeling: Slow Start (1)
Now suppose window grows according to slow start
Will show that the delay for one object is:
Latency  2 RTT 
O
S
S

 P  RTT    ( 2 P  1)
R
R
R

where P is the number of times TCP idles at server:
P  min {Q, K  1}
- where Q is the number of times the server idles
if the object were of infinite size.
- and K is the number of windows that cover the object.
TCP Delay Modeling: Slow Start (2)
Delay components:
• 2 RTT for connection
estab and request
• O/R to transmit
object
• time server idles due
to slow start
initiate TCP
connection
request
object
first window
= S/R
RTT
Server idles:
P = min{K-1,Q} times
Example:
• O/S = 15 segments
• K = 4 windows
•Q=2
• P = min{K-1,Q} = 2
Server idles P=2 times
second window
= 2S/R
third window
= 4S/R
fourth window
= 8S/R
complete
transmission
object
delivered
time at
client
time at
server
TCP Delay Modeling (3)
S
 RTT  time from when server starts to send segment
R
until server receives acknowledg ement
initiate TCP
connection
2k 1
S
 time to transmit the kth window
R

request
object
S
k 1 S 

RTT

2
 idle time after the kth window
 R
R 
first window
= S/R
RTT
second window
= 2S/R
third window
= 4S/R
P
O
delay   2 RTT   idleTime p
R
p 1
P
O
S
S
  2 RTT   [  RTT  2 k 1 ]
R
R
k 1 R
O
S
S
  2 RTT  P[ RTT  ]  (2 P  1)
R
R
R
fourth window
= 8S/R
complete
transmission
object
delivered
time at
client
time at
server
TCP Delay Modeling (4)
Recall K = number of windows that cover object
How do we calculate K ?
K  min {k : 2 0 S  21 S    2 k 1 S  O}
 min {k : 2 0  21    2 k 1  O / S }
O
 min {k : 2  1  }
S
O
 min {k : k  log 2 (  1)}
S
O


 log 2 (  1)
S


k
Calculation of Q, number of idles for infinite-size object,
is similar (see HW).