Transcript EE 122: Computer Networks

期末复习
罗忠文
http://xgxy.cug.edu.cn/rjgcx/lzw
内容取自UCB的教程
[email protected]
1
Announcements
• Ground Rules for Final
– Closed book, with single 8.5x11 (both sides) crib sheet
– Accommodations? Email me….
• Exam covers entire semester
• This review only covers post-midterm material
– See midterm review for earlier material
• Everything in review slides is fair game
– But so is everything else except material from
o Designing in 90 minutes
o Advanced routing (except what’s in final review)
o P2P (except what’s in final review)
2
This Review
• 60 slides!
• I won’t try to get through all of them
• But should serve as a useful study guide
– Along with midterm review
• Evaluations at end of class…..
3
DHCP and ARP
4
What Does a Host Need to Know?
• What IP address the host should use?
• What local DNS server to use?
• How to tell which destinations are local?
• How do we address them using local network?
• How to send packets to remote destinations?
??? 1.2.3.7 1.2.3.156
host
host ...
DNS
host
host ...
DNS
5.6.7.0/24
1.2.3.0/23
1.2.3.19
router
router
router
5
Avoiding Manual Configuration
• L3: Dynamic Host Configuration Protocol (DHCP)
– End host learns how to send packets
– Learn IP address, DNS servers, “gateway”, what’s local
• L2: Address Resolution Protocol (ARP)
– For local destinations, learn mapping between IP
address and MAC address
1.2.3.48 1.2.3.7 1.2.3.156
host
host ...
1.2.3.0/23
255.255.254.0
DNS 1A-2F-BB-76-09-AD
host
host ...
DNS
5.6.7.0/24
1.2.3.19
router
router
router
6
Address Resolution Protocol
• Every node maintains an ARP table
– <IP address, MAC address> pair
• Consult the table when sending a packet
– Map destination IP address to destination MAC address
– Encapsulate and transmit the data packet
• But: what if IP address not in the table?
– Sender broadcasts: “Who has IP address 1.2.3.156?”
– Receiver responds: “MAC address 58-23-D7-FA-20-B0”
– Sender caches result in its ARP table
• Link-layer protocol (RFC 826)
– Because necessary to bootstrap IP connectivity
7
Bootstrapping Problem
• Host doesn’t have an IP address yet
– So, host doesn’t know what source address to use
• Host doesn’t know who to ask for an IP address
– So, host doesn’t know what destination address to use
• Solution: IP-level discovery protocol to find server
– Broadcast a server-discovery message (255.255.255.255)
– Server(s) sends a reply offering an address
host
host ...
host
DHCP server
8
Dynamic Host Configuration Protocol
arriving
client
DHCP server
203.1.2.5
Why all the
broadcasts?
9
Where to send packets
• Determine if destination is local using the netmask
– If netmask of destination address is same as netmask of
source, then destination is local
• If destination is on the local network
– Need to find out its MAC address using ARP
• If destination is not local (“remote”)
– Need to send to gateway router (as specified by DHCP)
– Use ARP to determine MAC address of gateway router
10
Network Control Messages
(and how to use them for
discovery)
11
Internet Control Message Protocol
• ICMP runs on top of IP
– Same level as TCP and UDP
– Though viewed as an integral part of IP (not transport)
• Diagnostics (network “print” statement)
– Triggered when an IP packet encounters a problem
• ICMP packet sent back to the source IP address
– Includes the error information (e.g., type and code)
– IP header plus 8+ byte excerpt from original packet
• Source host receives the ICMP packet
– Inspects excerpt to identify socket
• Exception: ICMP not sent if problem is ICMP
– And just for fragment 0 of a group of fragments
12
Types of Control Messages
• Need Fragmentation
– IP packet too large for link layer, DF set
• TTL Expired
– Decremented at each hop; generated if  0
• Unreachable
– Subtypes: network / host / port
• Source Quench
– Old-style signal asking sender to slow down
• Redirect
– Tells source to use a different local router
13
Discovering Network Path Properties
• ICMP provides way for routers to talk to end hosts
• Can be used in clever ways to probe the network
to discover things about its internals:
–PMTU Discovery:
o What is largest packet that can be sent completely
through the network w/o needing fragmentation?
–Traceroute:
o What is the series of routers that a packet traverses
as it travels through the network?
14
Path MTU Discovery
• MTU = Maximum Transmission Unit
– Largest IP packet that a link supports
• Path MTU (PMTU) = minimum end-to-end MTU
– Sender must keep datagrams no larger to avoid
fragmentation
• How does the sender know the PMTU is?
• Strategy (RFC 1191):
– Try a desired value
– Set DF to prevent fragmentation
– Upon receiving Need Fragmentation ICMP …
o … oops, that didn’t work, try a smaller value
15
Discovering Routing via Time Exceeded
• Host sends an IP packet
– Each router decrements the time-to-live field
• If TTL reaches 0
– Router sends Time Exceeded ICMP back to the source
– Message identifies router sending it
o Since ICMP is sent using IP, it’s just the IP source address
5.6.7.156
1.2.3.7
host
host ...
DNS
host ...
host
DNS
8.9.10.11
Time exceeded
router
router
router
16
Traceroute: Exploiting Time Exceeded
• Time-To-Live field in IP packet header
– Source sends a packet with TTL ranging from 1 to n
– Each router along the path decrements the TTL
– “TTL exceeded” sent when TTL reaches 0
• Traceroute tool exploits this TTL behavior
TTL=1
source
Time
exceeded
destination
TTL=2
Send packets with TTL=1, 2, …
and record source of Time Exceeded message
17
Routing
18
Three levels in routing hierarchy
• Networks: reaches individual hosts
– Link-layer routing (self-learning)
• Intradomain: routes between networks
– Lowest-cost routing (link-state, distance-vector)
• Interdomain: routes between ASes
– BGP (path vector)
19
Lowest Cost Routing
20
Link State: Control Traffic
• Each node floods its local information
• Each node then knows the entire network topology
Host C
Host D
Host A
N1
N2
N3
N5
Host B
Host E
N4
N6
N7
21
Local Computation of Routes
C
A
Host C
D
C
A
C
A
D
D
Host D
Host A
B
B
E
B
N2
N1
E
E
C
A
D
N3
C
A
D
B
E
N5
B
Host B
C
A
D
C
E
A
D
B
N4
N6
B
E
Host E E
N7
Each node independently calculates shortest paths
22
(using Dijkstra’s algorithm)
Distance Vector Routing
• Each router knows the links to its neighbors
– Does not flood this information to the whole network
• Each router has provisional “shortest path”
– E.g.: Router A: “I can get to router B with cost 11 via
next hop router D”
• Routers exchange this information with their
neighboring routers
– Again, no flooding the whole network
• Routers update their idea of the best path using
info from neighbors
• This iterative process converges with set of
shortest paths
23
Bellman-Ford Algorithm
• INPUT:
–Link costs to each neighbor
–Not full topology
• OUTPUT:
–Next hop to each destination and the
corresponding cost
–Does not give the complete path to the
destination
24
Bellman-Ford – Overview
• Each router maintains a table
– Row for each possible destination
– Column for each directly-attached
neighbor to node
– Entry in row Y and column Z of node X
 best known distance from X to Y, via
Z as next hop = DZ(X,Y)
Neighbor
(next-hop)
Node A
2
A
B
7
3
1
C
D
1
B
C
B
2
8
C
3
7
D
4
8
Destinations
DC(A, D)
Bellman-Ford
• Know the Bellman-Ford algorithm, count-to-infinity,
and poisoned reverse….
• No need to know Dijkstra’s Algorithm
26
Interdomain Routing
27
BGP Basics
• If domains A and B have an interdomain link:
– Their border routers announce routes to each other
o One route for each reachable prefix
– Routes announced whenever changed or withdrawn
o Route withdrawn when domain no longer offering path to prefix
o It usually has a path itself, but is choosing to not export that path
• Policies:
– Import policy: which routes the domain will use
o Chooses among routes advertised by neighbors
– Export policy: which routes the domain lets other use
o Purely a filtering policy
• Route computation: path vector
– Loop detection, which enables flexible policies
28
Joining BGP and IGP Information
• Border Gateway Protocol (BGP)
–Announces reachability to external destinations
–Maps a destination prefix to an egress point
o 128.112.0.0/16 reached via 192.0.2.1
• Interior Gateway Protocol (IGP)
–Used to compute paths within the AS
–Maps an egress point to an outgoing link
o 192.0.2.1 reached via 10.1.1.1
10.1.1.1
192.0.2.1
29
IGP, eBGP, iBGP,….
6
2
3
4
3
9
2
1
Border router
Internal router
1.
2.
3.
4.
Provide internal reachability (IGP)
Learn routes to external destinations (eBGP)
Distribute externally learned routes internally (iBGP)
Select closest egress (IGP)
30
Routing Follows the Money!
traffic allowed
traffic not allowed
• Peers provide transit between their customers
• Peers do not provide transit to each other
31
Examples of Standard Policies
• Transit network:
– Selection: prefer customer to peer to provider
– Export:
o Let customers use any of your routes
o Let anyone route through you to your customer
o Block everything else
• Multihomed (nontransit) network:
– Export: Don’t export routes for other domains
– Selection: pick primary over backup
32
Advanced Routing
34
Basic Routing Techniques
• Self-learning
• Link-state
• Distance-vector
• Path-vector
35
Self-Learning
• Requirements:
– Plug-and-play (no management needed)
– Flat address space
• Forwarding rules:
– Watch which port MAC addresses come from
– When in doubt, flood to all other ports
• Spanning tree needed for flooding
– Does not use shortest data paths
– Network unusable while spanning tree recomputed
36
Intradomain (L3)
• Link-state:
– Global state, local computation
– Flood local topology information
– Each router computes shortest paths on graph
– Requires routers to have globally consistent state
• Distance-vector:
– Local state, global computation
– Routers participate in distributed computation
– Exchange current views on “shortest paths”
– Hard to prevent loops while responding to failures
o E.g., count-to-infinity
37
Interdomain: Path-vector
• Path-vector enables:
– General policy autonomy for import and export
– Easy detection of loops (which allows policy freedom!)
• Disadvantages of path-vector
– High churn rate (many updates)
– Convergence after failure can be slow
– Policy oscillations possible
o Even limited degrees of autonomy can result in policy oscillations
38
Three Routing Challenges
• Resilience
– Slow convergence after failures, worse as networks grow
– Network not reliable during convergence
– Most important barrier to a more reliable Internet
o Goal is 99.999% availability, now 99.9% at best
o Gaming, media, VoIP, finance (trading) make this more important
• Traffic engineering
– Current traffic engineering mechanisms cumbersome
– Must find more adaptive methods
• Policy oscillations in interdomain routing
39
Meeting These Challenges
• Augmenting all approaches with multipath
– Routing computes more than one path
– Allows hosts to use alternate paths when failure occurs
• Augmenting LS with Failure-Carrying Packets
– No packet drops during convergence
– Requires change to packet header
• Augmenting DV with Routing Along DAGs
– Local adaptation prevents packet drops, spreads load
– No need for header changes, applies to L2 and L3
• Augmenting PV with Policy Dispute Resolution
– Only invoked when oscillation is in progress
40
TCP
41
TCP Service Model
•
Reliable, in-order, duplex byte-stream delivery
–
•
Hopefully with good performance
Challenges - the network can
–
drop packets
o
–
delay packets
o
–
Follows from possibility of arbitrary delay
replicate packets
o
–
Even perhaps for many seconds
deliver packets out-of-order
o
–
Even perhaps a large number
Weird, but it does sometimes happen
corrupt packets
42
Timing Diagram: 3-Way Handshaking
Passive
Open
Active
Open
Client (initiator)
Server
listen()
connect()
accept()
43
Normal Termination, Both Together
B
A
time
Timeout:
Avoid reincarnation
Can retransmit
FIN ACK if ACK lost
Connection
now closed
44
Abrupt Termination
B
A
time
• A sends a RESET (RST) to B
– E.g., because app. process on A crashed
• That’s it
–
–
–
–
B does not ack the RST
Thus, RST is not delivered reliably
And: any data in flight is lost
But: if B sends anything more, will elicit another RST
45
TCP Support for Reliable Delivery
•
Checksum
–
–
•
Sequence numbers
–
–
•
Used to detect corrupted data at the receiver
…leading the receiver to drop the packet
Used to detect missing data
... and for putting the data back in order
Retransmission
–
–
–
Sender retransmits lost or corrupted data
Timeout based on estimates of round-trip time
Fast retransmit algorithm for rapid retransmission
46
ACKing and Sequence Numbers
•
Sender sends packet
–
–
Data starts with sequence number X
Packet contains B bytes
o
•
X, X+1, X+2, ….X+B-1
Upon receipt of packet, receiver sends an ACK
–
If all data prior to X already received:
o
–
ACK acknowledges X+B (because that is next expected byte)
If highest byte already received is some smaller value Y
o
o
ACK acknowledges Y+1
Even if this has been ACKed before
47
Flow Control
•
Advertised Window: W
–
•
Can send W bytes beyond the next expected byte
Receiver uses W to prevent sender from
overflowing buffer
48
Reliability: TCP Retransmission
49
Packet lost
Timeout
Timeout
Timeout
Timeout
Timeout
Timeout
Reasons for Retransmission
ACK lost
DUPLICATE
PACKET
Early timeout
DUPLICATE
PACKETS 50
How Long Should Sender Wait?
• Sender sets a timeout to wait for an ACK
– Too short: wasted retransmissions
– Too long: excessive delays when packet lost
• RTO = EstimatedRTT + 4 x EstimatedDeviation
• Estimated RTT: exponential average of RTT
– Only sample packets that are not retransmitted
• Deviation = | SampleRTT – EstimatedRTT |
• EstimatedDeviation: exp. average of Deviation
51
Alternative to Timeouts
• Triple duplicate ACK (“three dups”)
– Packet n is lost, but packets n+1, n+2, …, arrive
• On each arrival of a packet not in sequence,
receiver generates an ACK
– So as n+1, n+2, … arrive, receiver generates repeated
ACKs for seq.no. n
– “duplicate” acknowledgments since they all look the
same
– Sender sees 3 of these (four ACKs in total) and
immediately retransmits packet n (and only n)
• Termed Fast Retransmission
52
Congestion Control Overview
53
Basics of TCP Congestion Control
• Each source determines the available capacity
– … so it knows how many packets to have in flight
• Congestion window (CWND)
– Maximum # of unacknowledged bytes to have in flight
– Congestion-control equivalent of receiver window
– MaxWindow = min{congestion window, receiver window}
– Send at the rate of the slowest component
• Adapting the congestion window
– Decrease upon detecting congestion
– Increase upon lack of congestion: optimistic exploration
• Packet losses used as sign of congestion
54
Summary of Increase
• “Slow-start”: increase cwnd by MSS for each ack
• Leave slow-start regime when either:
– cwnd > SSThresh
– Packet drop
• Enter AIMD regime
– Increase by MSS for each window’s worth of acked data
– Increment per ACK:
CWND += MSS * (MSS / CWND)
55
Summary of Decrease
• Cut CWND half on loss detected by NACK
– “fast retransmit”
• Cut CWND all the way to 1 MSS on timeout
– Set ssthresh to cwnd/2
• Never drop CWND below 1 MSS
56
TCP Dynamics
Window
Fast
Retransmission
Slow start in operation until
it reaches half of previous
CWND, I.e., SSTHRESH
Timeout
SSThresh
Set to Here
t
Slow-start restart: Go back to CWND of 1 MSS, but take
advantage of knowing the previous value of CWND.
57
Additional Congestion Control Topics
• Equation-based congestion control
– rate ~ MSS/[RTT*sqrt(loss rate)] (know this equation)
• Extending TCP to higher speeds
– Change CWND adjustment at higher speeds
• Signaling congestion without packet drops
– Explicit congestion notification (ECN)
58
Security
59
Basic Requirements for Secure Communication
• Availability: Will the network deliver data?
– Infrastructure compromise, DDoS
• Authentication: Who is this actor?
– Spoofing, phishing
• Integrity: Do messages arrive in original form?
• Confidentiality: Can adversary read the data?
– Sniffing, man-in-the-middle
• Provenance: Who is responsible for this data?
– Forging responses, denying responsibility
– Not who sent the data, but who created it
60