Transcript Chapter 4: More on Hierarchy, DHCP, ICMP

Chapter 4
Hierarchy, DHCP, ICMP
Professor Rick Han
University of Colorado at Boulder
[email protected]
Announcements
• Homework #3 on Web, due March 12 (two
weeks), netstat portion online later today
• Programming Assignment #2 coming…
• Midterm March 14
• Last week’s lectures on Web
• Next, more on hierarchy, DHCP, ICMP, …
Prof. Rick Han, University of
Colorado at Boulder
Recap of Previous Lecture
• Link State vs. Distance Vector
•
•
•
•
•
•
Routing Update Size
Routing Update Comm. Overhead
Convergence Speed
Complexity
Space
Robustness
•
•
•
Queue Length
Delay
Normalized Hop Count
•
BGP
• Link State Cost Metric
• Hierarchical Routing
Prof. Rick Han, University of
Colorado at Boulder
Scalability in Internet Routing (2)
AS 1
Inter-Domain
Routing
Border/
RIP Gateway
Router
Border/
Gateway
Router
Intra-Domain RoutingProf. Rick Han, University of
Colorado at Boulder
AS 2
OSPF
Border Gateway Protocol (BGP)
• Interdomain Routing
• “Path” Vector similar to Distance Vector
– BGP router advertises only reachability info
in its vector, not costs/hop counts
• E.g. networks 128.96, 192.4.153, and 192.4.3 can
be reached from AS2
– BGP router advertises its path to each
destination in its vector
• Avoids loops
Prof. Rick Han, University of
Colorado at Boulder
Interior Border Gateway Protocol
• Each AS may have many border routers
– Each border routers could inject 10000 prefixes from
neighboring AS
• LSP’s too large
• Shortest path calculations too expensive
• Border routers use interior BGP (IBGP) to limit
routing info received by internal AS routers
– IBGP routers determine best route to each
destination
– Only the best interior BGP router injects info into AS
– Any router in AS learns one best border router to use
when sending a packet externally
Prof. Rick Han, University of
Colorado at Boulder
Hierarchy In Addition To BGP
• OSPF has its own hierarchy: group OSPF
routers into areas
– Hierarchy: AS –> OSPF area -> OSPF network
• Subnets:
– Fixed Classes A,B,C inefficient - Class B exhaustion
– Subdivide a Class B IP address 128.96.34.15 into
<Network ID, Subnet ID, Host ID>
• IP address is AND’ed with subnet mask to extract subnet
address:
– Subnet mask 255.255.255.0 AND’ed with IP address
128.96.34.15 gives subnet address 128.96.34
– Subnet mask 255.255.255.128 AND’ed with IP address
128.96.34.15 gives subnet address 128.96.34.0
Prof. Rick Han, University of
Colorado at Boulder
Additional Hierarchy (2)
• Subnets:
– When host 1 wants to send to host 2, AND the
subnet mask with the destination IP address
• If result is same subnet as sending host 1, then send over
local LAN subnet
• If result differs, then route to another subnet using
subnet-to-subnet routing
– Forwarding table changes from <destination IP, next
hop> to <destination subnet, subnet mask, next hop>
• For each entry, router AND’s subnet mask with dest. IP
address and looks for match with destination subnet
• Longest match breaks a tie
Prof. Rick Han, University of
Colorado at Boulder
Additional Hierarchy (3)
• CIDR (Classless Interdomain Routing) Subnets:
– When subnet mask is top N bits, then have a CIDR
network prefix,
• 192.4.16 with 20 bit prefix is written 192.4.16/20
• Approaches for fast prefix matching
• How do nodes advertise their CIDR
prefix/mask?
– IP header only has 32-bit address
• Where is subnet mask?
– BGP-4 path vectors and OSPF LSP’s carry the CIDR
prefix along with the IP address, e.g. 192.4.16/20
Prof. Rick Han, University of
Colorado at Boulder
Additional Hierarchy (4)
• How do CIDR and non-CIDR routing stay
compatible?
– OSPF and BGP support CIDR, RIP does not
– RIP builds a routing table by falling back to the old
Class A,B, C network prefixes
• makes RIP more inefficient
• Packets are still routed correctly
• CIDR Bottom line:
– Improves address assignment efficiency
– Helps aggregate routing to occur between networks
rather than nodes
Prof. Rick Han, University of
Colorado at Boulder
Fast Matching of Variable
Prefixes
• Need to match CIDR network prefix with
IP packet’s destination address
– Brute force: for each destination router in
list
• apply mask to match prefix with destination
address’s prefix
• choose longest match
Prof. Rick Han, University of
Colorado at Boulder
Fast Matching of Variable
Prefixes (2)
• Speeding it up: Organize prefixes into a
Patricia tree
– If Nth bit is zero, go left, otherwise go right
– Automatically finds longest match
– Worst case = 32 bit tests
1
0
default
0/0
0
128.2/16
Bit to test : 0 = left child,1 = right child
0
1
1
0
163.32/16
1
192.3/20
Prof. Rick Han, University of
Colorado at Boulder
252.32.150/24
Dynamic Host Configuration
Protocol (DHCP)
• RARP: A host knows a destination’s MAC
address, but not destination’s IP address.
• If destination=itself, then same goal as DHCP
• BOOTP: similar goal to RARP, devised same time
(1985)
• DHCP: a host knows its own MAC address, but
doesn’t have an IP address yet
• Due to hierarchical addressing on network, can’t have
manufacturer-preassigned IP addresses
• Manual configuration is time-consuming, inflexible to
changes, wastes addresses on disconnected nodes
Prof. Rick Han, University of
Colorado at Boulder
DHCP (2)
• Goal: Automatic configuration of a host’s IP
address
– A host queries a DHCP server to obtain an IP address
• How does a host find the address of a DHCP
server?
– Host sends a DHCPDISCOVER “limited IP broadcast
packet”, with destination address 255.255.255.255
– Routers never forward such a packet, so it stays
within LAN
IP Router
255.255.255.255
LAN1
Requesting Host
LAN2
DHCP
Server
Prof. Rick Han, University of
Colorado at Boulder
DHCP (3)
• DHCP relays enable one DHCP server per
administrative domain, rather than one server
per network
– Requires a DHCP relay on each network
– DHCP relay sends a unicast IP packet to DHCP server
when it hears a local IP broadcast packet with
DHCPDISCOVER
IP Router
255.255.255.255
LAN1
LAN2
DHCP
Relay
Requesting Host
Prof. Rick Han, University of
Colorado at Boulder
DHCP
Server
DHCP (4)
• DHCP server selects a dynamic IP addr. from pool
– maps host’s MAC address to the dynamic IP address
• Another advantage of relays: enable DHCP
responses to get back to requesting host
– Server can’t send directly back using host’s MAC
address
– DHCP server sends unicast to known IP address of
DHCP relay, which sends to host’s local MAC address
IP Router
LAN1
LAN2
DHCP
Relay
Requesting Host
Prof. Rick Han, University of
Colorado at Boulder
DHCP
Server
DHCP (5)
• Hosts cannot keep dynamic IP addresses
indefinitely
– Timeout/lease by DHCP
• 3 days for Windows NT, 8 days for Windows 2000, 1 day…
• Configurable when starting DHCP server
– Host must periodically renew lease, otherwise IP
address goes back into pool of available addresses
• DHCP is implemented as an application-level
protocol on top of UDP and IP
Prof. Rick Han, University of
Colorado at Boulder
Internet Control Message
Protocol (ICMP)
• Used for reporting errors in the Internet
– Most ICMP packets contain diagnostic info sent back
to source
• Destination unreachable
• TTL expired
• Implemented at the same level as transport
protocols, just above IP
– Nevertheless, all IP routers are expected to speak
ICMP
IP Header ICMP message
Protocol=ICMP
Prof. Rick Han, University of
Colorado at Boulder
ICMP (2)
• Already seen it in use:
– Ping
– Traceroute
– Discovery of local routers on a LAN
• Format of an ICMP message:
– Some Types:
•
•
•
•
•
•
•
Type
Code
Cksum ICMP body
Echo & Echo Reply
*Destination Unreachable : dest not in routing table, or down
*Source Quench : sent by router during congestion
Redirect
Router Advertisement
Router Solication
*Time Exceeded : TTL Expired
Prof. Rick Han, University of
Colorado at Boulder
* = most frequently used
ICMP (3)
• ICMP body often contains a copy of IP header (+
first 8 bytes of payload) of packet that
generated the ICMP message
• Ping:
– A host sends an ICMP “echo” message
– As IP packet, “echo” message gets routed to
destination
– At destination, respond by sending an ICMP “echo
reply” message
• Swap source and destination IP addresses and recompute
checksum
Prof. Rick Han, University of
Colorado at Boulder
“Smurf” Denial of Service Attack
via ICMP echo
• Ping an IP broadcast address using spoofed
source IP addr, e.g. ping 255.255.255.255
– All nodes on LAN respond to ICMP echo with ICMP
echo request, directed at source
– LAN and especially source are flooded
• Solutions:
– Patch OS to disallow ICMP echo request to ICMP
echo using IP broadcast address
– Don’t allow router to forward external IP broadcast
addresses into your LAN
Prof. Rick Han, University of
Colorado at Boulder
Traceroute and ICMP
• Trace the route of an IP packet
– A host sends a regular IP packet to destination IP
address with TTL of one
– First router in path decrements TTL to zero, and
sends back to source a “Time exceeded” ICMP
message
• Source address in ICMP message is first router on path !
– Increment TTL by one (TTL=2), next ICMP error
message sent by second router in path
– Keep incrementing TTL to find routers in path
Prof. Rick Han, University of
Colorado at Boulder
Traceroute and ICMP (2)
• Trace the route of an IP packet
Source
Router 1
Timeline:
Router 2
TTL=1
Router 1 known
Router 2 known
Destination known
TTL=2
TTL=3
Prof. Rick Han, University of
Colorado at Boulder
Destination
Traceroute and ICMP (3)
• Trace the route of an IP packet
– Upon reaching destination,
• No “Time exceeded” message generated
• How do you know when final destination is
reached?
– Traceroute sends to unused UDP port
(>30000), generating an ICMP “destination
unreachable” message
• With code “port unreachable”
Prof. Rick Han, University of
Colorado at Boulder
Router Discovery via ICMP
• Routers periodically broadcast their ICMP
router advertisement to local LAN
– About every 7 minutes
– Lifetime of 30 minutes
• New hosts can broadcast ICMP router
solicitation message, to avoid waiting 7 minutes
• ICMP Redirect
– Sent when there are two or more routers on the same
LAN
– Each router will know whether its neighbors on a LAN
are closer to a destination
• When source sends to higher cost router, that router sends
an ICMP Redirect message to the source
Prof. Rick Han, University of
Colorado at Boulder
IP Tunnelling and VPN’s
• IP router 1 builds an IP tunnel to IP router 2
– Router 1 encapsulates packets destined for
network/LAN 2 with router 2’s IP address
– Router 2 de-encapsulates
• Advantages
– Secure tunnels = Virtual Private Networks (VPNs) for
corporations
– Layered functionality = multicast/MBone
– Encapsulate non-IP protocols
LAN1
R1
Internet
Prof. Rick Han, University of
Colorado at Boulder
R2
LAN2