Transcript ppt - EECS Instructional Support Group Home Page

Midterm Review
EE 122: Intro to Communication Networks
Fall 2010 (MW 4-5:30 in 101 Barker)
Scott Shenker
TAs: Sameer Agarwal, Sara Alspaugh, Igor Ganichev, Prayag Narula
http://inst.eecs.berkeley.edu/~ee122/
Materials with thanks to Jennifer Rexford, Ion Stoica, Vern Paxson
and other colleagues at Princeton and UC Berkeley
1
Announcements
• Extended office hours after class
– As long as line lasts….
2
My General Philosophy on Tests
• I am not a sadist
• I am not a masochist
• For those of you who only read the slides at home:
– If you don’t attend lectures, then it is your own damn
fault if you missed something….
• I believe in testing your understanding of the
basics, not tripping you up on tiny details or
making you calculate pi to 15 decimal places
3
General Guidelines
• Know the basics
• Study lecture notes and problem sets
• Read text only to learn certain details
• Get plenty of sleep
• There will be a question about how to improve the
course; be thinking about it….
4
Things You Don’t Need to Know
• Sockets (you must know this, but not on midterm)
• Details of “Our Design”
• The details of how to fragment packets
• The details of any protocol header
– Know semantics, but not syntax
• Remember: you can use a crib sheet…..
5
Outline of Review
• General rules of system design
• The IP layer: Architecture, Header, Addressing
• Above the IP layer: Transport, DNS, HTTP
• Below the IP layer: Ethernet
6
General Rules of System Design
• System not scalable?
– Add hierarchy
– DNS, IP addressing
• System not flexible?
– Add layer of indirection
– DNS names (rather than using IP addresses as names)
• System not performing well?
– Add caches
– Web and DNS caching
7
IP Layer:
Architecture, Header, and Addressing
8
Internet’s Five Basic Design
Decisions
1. Packet-switching
2. Best-effort service model
3. Layering
4. A single internetworking layer
5. The end-to-end principle (and fate-sharing)
9
Why Best-Effort (BE)?
• BE means never having to say you’re sorry…
– No need to reserve bandwidth and memory
– No need to do error detection & correction
– No need to remember from one packet to next
– No need to make packets follow same path
• Which makes the Internet:
– Easier to build
– Easier to make robust
– Easier to interconnect
– Easier to deploy
10
Some Applications Want….
• No losses or corruption, packets delivered in order
– Rely on higher layers
• Minimal and predictable delays
– Tough luck
– Go redesign your application, bellhead!
11
End-to-End Principle
• Think twice before implementing functionality in
the network
• If hosts can implement functionality correctly,
implement it in a lower layer only as a performance
enhancement
• But do so only if it does not impose burden on
applications that do not require that functionality
12
Related Notion of Fate-Sharing
• Idea: when storing state in a distributed system,
keep it co-located with the entities that ultimately
rely on the state
• Fate-sharing is a technique for dealing with failure
– Only way that failure can cause loss of the critical state is
if the entity that cares about it also fails ...
– … in which case it doesn’t matter
• Often argues for keeping network state at end
hosts rather than inside routers
– In keeping with End-to-End principle
– E.g., packet-switching rather than circuit-switching
– E.g., HTTP “cookies”
13
Layer-to-Layer Communication
host
host
HTTP message
HTTP
TCP segment
TCP
router
IP
Ethernet
interface
HTTP
IP packet
Ethernet
interface
Ethernet frame
IP
TCP
router
IP packet
SONET
interface
SONET
interface
SONET frame
IP
IP packet
Ethernet
interface
IP
Ethernet
interface
Ethernet frame
14
IP Layer:
Architecture, Header, and Addressing
15
IP Packet Structure
4-bit
8-bit
4-bit
Version Header Type of Service
Length
(TOS)
3-bit
Flags
16-bit Identification
8-bit Time to
Live (TTL)
16-bit Total Length (Bytes)
8-bit Protocol
13-bit Fragment Offset
16-bit Header Checksum
32-bit Source IP Address
32-bit Destination IP Address
Options (if any)
Payload
IPv4 and IPv6 Header Comparison
IPv6
IPv4
Version
IHL
Type of Service
Identification
Time to Live
Total Length
Flags
Protocol
Fragment
Offset
Version
Traffic Class
Payload Length
Flow Label
Next
Header
Hop Limit
Header Checksum
Source Address
Source Address
Destination Address
Options
Padding
Field name kept from IPv4 to IPv6
Fields not kept in IPv6
Name & position changed in IPv6
New field in IPv6
Destination Address
IP Layer:
Architecture, Header, and Addressing
18
CIDR Addressing
Use two 32-bit numbers to represent a network.
Network number = IP address + Mask
IP Address : 12.4.0.0
Address
Mask
IP Mask: 255.254.0.0
00001100 00000100 00000000 00000000
11111111 11111110 00000000 00000000
Network Prefix
for hosts
Written as 12.4.0.0/15 or 12.4/15
19
Hierarchal Address Allocation
• Prefixes are key to Internet scalability
– Addresses allocated in contiguous chunks (prefixes)
– Routing protocols and packet forwarding based on prefixes
12.0.0.0/15
12.2.0.0/16
12.3.0.0/16
12.0.0.0/8
:
:
12.253.0.0/16
:
12.3.0.0/22
12.3.4.0/24
:
:
:
:
:
12.3.254.0/23
12.253.0.0/19
12.253.32.0/19
12.253.64.0/19
12.253.64.108/30
12.253.96.0/18
12.253.128.0/17
20
Address Assignment
• Internet Corporation for Assigned Names and
Numbers (ICANN)
– Allocates large blocks to Regional Internet Registries
• Regional Internet Registries (RIRs)
– E.g., ARIN (American Registry for Internet Numbers)
– Allocates address blocks within their regions
– Allocated to Internet Service Providers and large
institutions ($$)
• Internet Service Providers (ISPs)
– Allocate address blocks to their customers (could be
recursive)
21
Routing: Provider with 4 Customers
Link 1
Link 4
Provider
Link 2
201.143.0.0/22
201.143.4.0/24
Prefix
Link 3
201.143.5.0/24
201.143.6.0/23
Link
201.143.0.0/22
201.143.4.0.0/24
201.143.5.0.0/24
Link 1
Link 2
Link 3
201.143.6.0/23
Link 4
22
Routing: Aggregating Customers
Prefix
201.143.0.0/21
201.144.0.0/21
Link
Provider 1
Provider 2
201.143.0.0/21
201.144.0.0/21
Provider 1
Provider 2
23
201.143.0.0/22 201.143.4.0/24 201.143.5.0/24 201.143.6.0/23201.144.0.0/22 201.144.4.0/24 201.144.5.0/24 201.144.6.0/23
Routing: Complications
Forwarding table more complicated
when addressing is non-topological
201.143.0.0/21
201.144.0.0/21
Provider 1
Provider 2
24
201.143.0.0/22 201.143.4.0/24 201.143.5.0/24 201.143.6.0/23201.144.0.0/22 201.144.4.0/24 201.144.5.0/24 201.144.6.0/23
Arriving packet:
Longest
Match
11001001Prefix
10010000
00000100 01101101
00000101
Provider 1
11001001 10001111 00000−−− −−−−−−−
201.143.0.0/21
11001001 10010000 00000100 −−−−−−−
201.144.4.0/24
Provider 2
11001001 10010000 00000−−− −−−−−−−
201.144.0.0/21
11001001 10001111 00000101 −−−−−−−
201.143.5.0/24
25
Network Address Translation (NAT)
Before NAT…
– Every machine connected to Internet had unique IP address
Server
80 1001 5.6.7.8 1.2.3.4 Internet
5.6.7.8
src port
dest addr src addr
dst port
LAN
5.6.7.8 1.2.3.4 80 1001
1.2.3.4
1.2.3.5
Clients
26
NAT (cont’d)
• Independently assign addresses to machines behind
same NAT
– Usually in address block 192.168.0.0/16
• Use bogus port numbers to multiplex/demultiplex internal
addresses
Server
NAT 5.6.7.8 192.2.3.4 80 1001
80 2000 5.6.7.8 1.2.3.4
192.2.3.4
Internet
5.6.7.8
80 1001
1.2.3.4
5.6.7.8
80 2000
192.2.3.4
5.6.7.8
1.2.3.4
192.2.3.4:1001
1.2.3.4:2000
192.2.3.5
Clients
27
NAT (cont’d)
• Independently assign addresses to machines behind
same NAT
– Usually in address block 192.168.0.0/16
• Use bogus port numbers to multiplex demultiplex internal
addresses
Server
NAT
80 2001 5.6.7.8 1.2.3.4
192.2.3.4
Internet
5.6.7.8 1.2.3.4
1.2.3.4 80 2001
5.6.7.8
80 1001 5.6.7.8 192.2.3.5
192.2.3.4:1001
5.6.7.8 192.2.3.5 80 1001
192.2.3.5
1.2.3.4:2000
192.2.3.5:1001
1.2.3.4:2001
Clients 28
Problems with NAT
• What if you have a server behind a NAT?
• What address do you tell clients to contact?
• What port do you tell clients to contact?
29
Above IP:
Transport, DNS, HTTP
30
Transport Protocols
• Provide logical communication
between application processes
running on different hosts
application
transport
network
data link
physical
• Run on end hosts
– Sender: breaks application
messages into segments,
and passes to network layer
– Receiver: reassembles
segments into messages, passes
to application layer
• Multiple transport protocol available
to applications
– Internet: TCP and UDP (mainly)
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
31
Ports
• Need to decide which application gets which packets
• Solution: map each socket to a port
• Client must know server’s port
• Separate 16-bit port address space for UDP and TCP
– (src_IP, src_port, dst_IP, dst_port) identifies TCP connection
– What about UDP?
• Well known ports (0-1023): everyone agrees which
services run on these ports
– e.g., ssh:22, http:80
• Ephemeral ports (most 1024-65535): given to clients
32
TCP Support for Reliable Delivery
•
Sequence numbers
–
–
•
Checksum
–
–
–
•
Used to detect missing data
... and for putting the data back in order
Used to detect corrupted data at the receiver
…leading the receiver to drop the packet
No error signal sent - recovery via normal retransmission
Retransmission
–
–
–
Sender retransmits lost or corrupted data
Timeout based on estimates of round-trip time (RTT)
Fast retransmit algorithm for rapid retransmission
33
Sliding Window: Better Throughput
• Allow sender to get ahead of the receiver
• … though not too far ahead
Sending process
TCP
Last byte written
Last byte ACKed
Receiving process
TCP
Sender Window
Last byte can send
Last byte read
Next byte needed
Receiver Window
Last byte received
34
Sliding Window, con’t
• Sender: window advances when new data ack’d
• Receiver: window advances as receiving process
consumes data
• Receiver advertises to the sender where the
receiver window currently ends (“righthand
edge”)
35
Performance with Sliding Window
• Window required to fully utilize path:
• Bandwidth-delay product
• RTT times bandwidth
• Less than this: connection spends time waiting
• More than this: packets are buffered on path
• Or dropped!
36
Above IP:
Transport, DNS, HTTP
37
Domain Name System (DNS)
• Properties of DNS
–Hierarchical name space divided into zones
–Zones distributed over collection of DNS servers
• Hierarchy of DNS servers
–Root (hardwired into other servers)
–Top-level domain (TLD) servers
–Authoritative DNS servers
• Performing the translations
–Local DNS servers
–Resolver software
38
Distributed Hierarchical Database
unnamed root
com
edu
org
generic domains
bar
uk
ac
zw
arpa
country domains
Top-Level Domains (TLDs)
ac
west
east
cam
foo
my
usr
my.east.bar.edu
usr.cam.ac.uk
inaddr
39
DNS Root Servers
• 13 root servers (see http://www.root-servers.org/)
– Labeled A through M
• Replication via any-casting (localized routing for addresses)
E NASA Mt View, CA
F Internet Software
Consortium,
Palo Alto, CA
(and 37 other locations)
A Verisign, Dulles, VA
C Cogent, Herndon, VA (also Los Angeles, NY, Chicago)
D U Maryland College Park, MD
G US DoD Vienna, VA
K RIPE London (plus 16 other locations)
H ARL Aberdeen, MD
I Autonomica, Stockholm
J Verisign (21 locations)
(plus 29 other locations)
M WIDE Tokyo
plus Seoul, Paris,
San Francisco
B USC-ISI Marina del Rey, CA
L ICANN Los Angeles, CA
40
TLD and Authoritative DNS Servers
• Top-level domain (TLD) servers
– Generic domains (e.g., com, org, edu)
– Country domains (e.g., uk, fr, cn, jp)
– Special domains (e.g., arpa)
– Typically managed professionally
o Network Solutions maintains servers for “com”
o Educause maintains servers for “edu”
• Authoritative DNS servers
– Provide public records for hosts at an organization
– For the organization’s servers (e.g., Web and mail)
– Can be maintained locally or by a service provider
41
Using DNS
• Local DNS server (“default name server”)
–Usually near the endhosts that use it
–Local hosts configured with local server (e.g.,
/etc/resolv.conf) or learn server via DHCP
• Client application
–Extract server name (e.g., from the URL)
–Do gethostbyname() to trigger resolver code
• Server application
–Extract client IP address from socket
–Optional gethostbyaddr() to translate into name 42
Example
root DNS server
Host at cis.poly.edu
wants IP address for
gaia.cs.umass.edu
2
3
TLD DNS server
4
local DNS server
dns.poly.edu
5
1
8
requesting host
cis.poly.edu
7
6
authoritative DNS server
dns.cs.umass.edu
gaia.cs.umass.edu
43
DNS Caching
• Performing all these queries takes time
– And all this before actual communication takes place
– E.g., 1-second latency before starting Web download
• Caching can greatly reduce overhead
– The top-level servers very rarely change
– Popular sites (e.g., www.cnn.com) visited often
– Local DNS server often has the information cached
• How DNS caching works
– DNS servers cache responses to queries
– Responses include a “time to live” (TTL) field
– Server deletes cached entry after TTL expires
44
DNS Resource Records
DNS: distributed DB storing resource records (RR)
RR format: (name,
• Type=A
– name is hostname
– value is IP address
value, type, ttl)
• Type=CNAME
– name is alias name for some
“canonical” name
E.g., www.cs.mit.edu is really
• Type=NS
– name is domain (e.g. foo.com)
– value is hostname of authoritative name
server for this domain
• Type=PTR
– name is reversed IP quads
o E.g. 78.56.34.12.in-addr.arpa
– value is corresponding
hostname
eecsweb.mit.edu
– value is canonical name
• Type=MX
– value is name of mailserver
associated with name
– Also includes a weight/preference
45
Security Problem: Cache Poisoning
• Suppose you are a Bad Guy and you control the
name server for foobar.com. You receive a request
to resolve www.foobar.com and reply:
;; QUESTION SECTION:
;www.foobar.com.
IN
A
Evidence of the attack
disappears 5 seconds later!
;; ANSWER SECTION:
www.foobar.com.
300
IN
A
212.44.9.144
;; AUTHORITY SECTION:
foobar.com.
foobar.com.
600
600
IN
IN
NS
NS
dns1.foobar.com.
google.com.
5
IN
A
212.44.9.155
;; ADDITIONAL SECTION:
google.com.
A foobar.com machine, not google.com
46
Above IP:
Transport, DNS, HTTP
47
HTTP
• HyperText Transfer Protocol (HTTP)
–Client-server protocol for transferring resources
• Important properties:
–Request-response protocol
–Reliance on a global URI namespace
–Resource metadata
–Stateless
% telnet www.icir.org 80
–ASCII format
GET /jdoe/ HTTP/1.0
<blank line, i.e., CRLF>
48
Steps in HTTP Request
• HTTP Client initiates TCP connection to server
• HTTP Client sends HTTP request to server
• HTTP Server responds to request
• HTTP Client receives the request
• TCP connection terminates
How many RTTs for a single request?
49
Client-to-Server Communication
• HTTP Request Message
– Request line: method, resource, and protocol version
– Request headers: provide information or modify request
– Body: optional data (e.g., to “POST” data to the server)
• Request methods include:
– GET: Return current value of resource, run program, …
– HEAD: Return the meta-data associated with a resource
– POST: Update resource, provide input to a program, …
• Headers include:
– Useful info for the server
o e.g. desired language
50
Web Server: Generating a Response
• Return a file
– URL matches a file (e.g., /www/index.html)
– Server returns file as the response
– Server generates appropriate response header
• Generate response dynamically
– URL triggers a program on the server
– Server runs program and sends output to client
• Return meta-data with no body
– Example: Size of a resource, last modification time, etc.
51
HTTP is Stateless
• Stateless protocol
– Each request-response exchange treated independently
– Servers not required to retain state
• But some applications need state!
– Cookies!
52
Retrieving Multiple Objects
• Sequential TCP connections
– One object per connection; very slow (2 RTTs per
object)
• Concurrent TCP connections
– One object per connection, but in parallel
– Better performance, but unfair to network
• Pipelined requests
– Single connection, with multiple requests in process
– Good performance, fair to network
• Persistent TCP connections
– Allows initial TCP to be used for later requests
53
Improving HTTP Performance:
Caching
• Many clients transfer same information
– Generates redundant server and network load
– Clients experience unnecessary latency
Server
Backbone ISP
ISP-1
ISP-2
Clients
54
Improving HTTP Performance:
Caching: How
• Modifier to GET requests:
– If-modified-since – returns “not modified” if
resource not modified since specified time
• Response header:
– Expires – how long it’s safe to cache the resource
– No-cache – ignore all caches; always get resource
directly from server
55
Improving HTTP Performance:
Caching: Why
• Motive for placing content closer to client:
– User gets better response time
– Content providers get happier users
o Time is money, really!
– Network gets reduced load
• Why does caching work?
– Exploits locality of reference
• How well does caching work?
– Very well, up to a limit
– Large overlap in content
– But many unique requests
56
Improving HTTP Performance:
CDN Example – Akamai
cnn.com
“Akamaizes” its content.
akamai.net
DNS servers
a
Akamai servers store/cache
secondary content for
“Akamaized” services.
lookup
a1921.g.akamai.net
b
DNS server for
cnn.com
c
local
DNS server
“Akamaized” response object has inline
URLs for secondary content at (after
resolving CNAMEs) a1921.g.akamai.net
and other Akamai-managed DNS names.
GET http://cnn.com
1 - DNS Lookup
2 - Fetch page w/ “Akamaized”
content
3 - DNS Lookup for Akamai URLs
4 - Fetch content
57
Improving HTTP Performance:
Caching and Replication
• Caching (pull)
– Replicate content “on demand” after a request
– Store the response message locally for future use
– Challenges:
o May need to verify if the response has changed
o … and some responses are not cacheable
• Replication (push)
– Planned replication of content in multiple locations
– Update of resources handled outside of HTTP
– Can replicate scripts that create dynamic responses
58
Link Layer:
Ethernet
59
Multiple Access Algorithm
• Single shared broadcast channel
– Must avoid having multiple nodes speaking at once
– Otherwise, collisions lead to garbled data
• Multiple access mechanism
– Distributed algorithm for sharing the channel
– Algorithm determines which node can transmit
• Classes of techniques
– Channel partitioning: divide channel into pieces
– Taking turns: scheme for trading off who gets to transmit
– Random access: allow collisions, and then recover
o Optimizes for the common case of only one sender
60
Key Ideas of Random Access
• Carrier sense
– Listen before speaking, and don’t interrupt
– But cannot prevent all collisions…
• Collision detection
– If someone else starts talking at the same time, stop
– Make sure everyone knows that there was a collision
• Randomness
– Don’t start talking again right away
• Examples:
– Aloha: randomness, but no CSMA or CD
– Ethernet: all three
61
Ethernet: CSMA/CD Protocol
• Carrier sense: wait for link to be idle
• Collision detection: listen while transmitting
– No collision: transmission is complete
– Collision: abort transmission & send jam signal
• Random access: binary exponential back-off
– After collision, wait a random time before trying again
– After mth collision, choose K randomly from {0, …, 2m-1}
– … and wait for K*512 bit times before trying again
o Using min packet size as “slot”
o If transmission occurring when ready to send, wait until end of
transmission (CSMA)
62
Shuttling Data at Different Layers
• Different devices switch different things
– Physical layer: electrical signals (repeaters and hubs)
– Link layer: frames (bridges and switches)
– Network layer: packets (routers)
Transport gateway
Application
gateway
Router
Bridge, switch
Frame Packet TCP
header header header
User
data
Repeater, hub
63
Self Learning: Building the Table
• When a frame arrives
– Inspect source MAC address
– Associate address with the incoming interface
– Store mapping in the switch table
– Use time-to-live field to eventually forget the mapping
o Soft state
Switch just learned
how to reach A.
B
A
C
D
64
Self Learning: Handling Misses
• When frame arrives with unfamiliar destination
– Forward the frame out all of the interfaces (“flooding”)
o … except for the one where the frame arrived
– Hopefully, this case won’t happen very often
– When destination replies, switch learns that node, too
When in doubt,
shout!
B
A
C
D
65
Switch Filtering / Forwarding
When switch receives a frame:
index the switch table using MAC dest address
if entry found for destination {
if dest on segment from which frame arrived
then drop frame
else forward frame on interface indicated
}
else flood
Problems?
forward on all but the interface
on which the frame arrived
66
Solution: Spanning Trees
• Ensure the forwarding topology has no loops
– Avoid using some of the links when flooding
– … to prevent loop from forming
• Spanning tree (K&R pp. 411-413)
– Sub-graph that covers all vertices but contains no cycles
– Links not in the spanning tree do not forward frames
Graph Has
Cycles!
Graph Has
No Cycles!
67
Basic Idea
• Pick Root
• Construct shortest paths to root
• This forms a tree, with links included only if they
are on the shortest path to the root
– Break ties between paths with same lengths
68
Constructing a Spanning Tree
• Need a distributed algorithm
– Switches cooperate to build the spanning tree
– … and adapt automatically when failures occur
• Key ingredients of the algorithm
– Switches need to elect a root
root
o The switch w/ smallest identifier (MAC addr)
– Each switch determines if its interface
is on the shortest path from the root
o Excludes it from the tree if not
– Messages (Y, d, X)
One hop
o From node X
o Proposing Y as the root
o And the distance is d
Three hops
69
Steps in Spanning Tree Algorithm
• Initially, each switch proposes itself as the root
– Switch sends a message out every interface
– … proposing itself as the root with distance 0
– Example: switch X announces (X, 0, X)
• Switches update their view of the root
– Upon receiving message (Y, d, Z) from Z, check Y’s id
– If new id smaller, start viewing that switch as root
• Switches compute their distance from the root
– Add 1 to the distance received from a neighbor
– Identify interfaces not on shortest path to the root
– … and exclude them from the spanning tree
• If root or shortest distance to it changed, flood
updated message (Y, d+1, X)
70
Final Words
• Notes on a few things we didn’t cover:
– Promiscuous mode is a configuration of a network card
that makes the card pass all traffic it receives to the
central processing unit rather than just frames addressed
to it — a feature normally used for packet sniffing.
– Breaking ties in spanning tree: In the spanning tree
algorithm, when there are multiple shortest paths to the
root, the chosen path uses the neighbor bridge/switch
with the lower ID.
71