Transcript IP - Florida State University

IP
Classless Inter-Domain Routing
• Classful addressing scheme wasteful
– IP address space exhaustion
– A class B net allocated enough for 65K hosts
• Even if only 2K hosts in that network
• Solution: CIDR
– Eliminate class distinction
• No A,B,C
– Keep multicast class D
Classless Addressing
• Addresses allocated in blocks
– Number of addresses assigned always power of 2, and
always on the boundary. That is, if 2048 addresses, it
will start with some address with all lower 11 bits being
0.
• Network portion of address is of arbitrary length
• Address format: a.b.c.d/x
– x is number of bits in network portion of address
network
part
11001000 00010111 00010000 00000000
200.23.16.0/23
host
part
Allocating Addresses
• Assume abundant addresses are available starting at
194.24.0.0.
• Cambridge university needs 2038 addresses, it is given
194.24.0.0 to 194.24.7.255. Mask 255.255.248.0.
• Oxford need 4096 addresses. Because the requirement
is that must be on the boundary, it is given 194.24.16.0
to 194.24.31.255. Mask 255.255.240.0.
• Edinburg needs 1024 addresses, is given 194.24.8.0 to
194.24.11.255. Mask 255.255.252.0.
CIDR
• A router keeps routing table with entries
– IP address, 32-bit mask, outgoing line
• When an IP packet arrives, the router checks
its routing table to find the longest match.
CIDR
• Example.
–
–
–
–
Cambridge 194.24.0.0/21
Edinburgh 194.24.8.0/22
(Available) 194.24.12.0/22
Oxford
194.24.16.0/20
194.24.0.0 -- 194.24.7.255
194.24.8.0 -- 194.24.11.255
194.24.12.0 -- 194.24.15.255
194.24.16.0 -- 194.24.31.255
• When a packet addressing to 194.24.17.4
arrives, where should it be sent to?
• And with all masks, find one that matches the
longest.
CIDR – Entry aggregation
• How does a router
in Tallahassee route
packet to C,E and
O, assuming that
he has only two
outgoing links?
• All to New York.
• Can he reduce the
size of his routing
table?
C
E
N
O
H
T
CIDR Entry Aggregation
• From 194.24.0.0 to
194.24.31.255, all to
N.
• So aggregate the three
entries into one
194.24.0.0/19.
• The N router can do
the same thing.
C
E
N
O
H
T
CIDR
• If later the free
address space
194.24.12.0/22
194.24.12.0 -194.24.15.255 is
assigned to Pittsburgh
and has to go through
Houston, what should
the router at
Tallahassee do?
C
P
E
N
O
H
T
CIDR
• When a packet arrives addressing 194.24.15.8,
the router checks the routing table and there
will be two matches: 194.24.12.0/22 and
194.24.0.0/19. Pick the longest match.
NAT – Network Address Translation
• IP address is a scarce resource.
• So, give a company only one or a few IP
addresses used by the gateway router.
• Within the company, each machine has an unique
IP address, chosen from
–
–
–
–
10.0.0.0/8
172.16.0.0/12
192.168.0.0/16
These addresses can only appear within a company
but never on the outside Internet
NAT
• Whenever a machine wants to send a packet to the
outside, the packet will be sent to the NAT box.
• The NAT box will convert the internal IP address to the
real IP address of the company, and pass the packet to
the gateway router.
• When there is a packet destined for an internal
machine arrived at the router, what should the router
and NAT box do?
• For IP packets carrying TCP or UDP, use port number.
Other protocols are much more complicated.
NAT
• For IP packets carrying TCP or UDP, use port
number.
• When an outgoing packet arrives at the NAT box,
– The IP address is replaced
– The source port number is replaced
– Header checksum is recomputed
• When a reply came for this process, use the
replaced source port number as index to find the
correct IP address and original port number.
ICMP
• ICMP – Internet Control Message Protocol
• Each ICMP message is encapsulated in an IP
packet
– Treated like any other datagram, but no error message
sent if ICMP message causes error
• Some interesting messages:
– Time exceeded: When an IP packet arrived at a router
is dropped because the TTL field becomes 0, the
router will send an ICMP TIME EXCEEDED message
back to the source. Used in traceroute.
– Echo and Echo reply: ping.
Address Resolution
• IP address is virtual
– Not understood by underlying the hardware of physical networks
• IP packets need to be transmitted by the
underlying physical network
• Address resolution
– Translating IP address to physical address
– Address Resolution Protocol (ARP)
Computer Science, FSU
15
ARP Example
Computer Science, FSU
16
ARP Cache
• Each computer maintains a cache table
– IP address  hardware address mapping
– Only about computers on the same network
• Exchanges ARP messages
– To resolve IP addresses with unknown hardware
addresses
Computer Science, FSU
17
ARP Protocol
• When a node sends an IP packet
– To another node on the same physical network
• Look up destination address in the ARP table
• If not found
– Broadcast a request to the local network
– Whose IP address is this?
Computer Science, FSU
18
ARP Response
• The target node responds to sender (unicast?)
– With its physical address
– Adds the requester into its ARP table (why?)
• On receiving the response
– Requester updates its table
• Other nodes upon receiving the request
– Refresh the requester entry if already there
– No action otherwise (why?)
• Table entries deleted if not refreshed for a while
Computer Science, FSU
19
DHCP
• DHCP – Dynamic Host Configuration Protocol
• A new machine asks for an IP address
– Broadcast DHCP DISCOVER packet
– A DHCP relay agent got this packet and relay it to
the DHCP server
– The DHCP server assigns an IP address
– Periodically renew
Hierarchical Routing
• aggregate routers into regions,
“autonomous systems” (AS)
• routers in same AS run same
routing protocol
– “intra-AS” routing protocol
– routers in different AS can run
different intra-AS routing
protocol
gateway routers
• special routers in AS
• run intra-AS routing
protocol with all other
routers in AS
• also responsible for routing
to destinations outside AS
– run inter-AS routing
protocol with other
gateway routers
Intra-AS and Inter-AS routing
C.b
Gateways:
B.a
A.a
a
b
A.c
C
B
a
d
A
b
c
a
c
b
•perform inter-AS
routing amongst
themselves
•perform intra-AS
routing with other
routers in their AS
network layer
inter-AS, intra-AS routing
in
gateway A.c
link layer
Intra-AS and Inter-AS routing
C.b
A.a
a
Host
h1
b
C
Inter-AS
routing
between
A and B
A.c
c
b
A
Intra-AS routing
within AS A
Host
h2
c
a
B
a
d
B.a
b
Intra-AS routing
within AS B
Why different Intra- and Inter-AS
routing ?
Policy:
• Inter-AS: admin wants control over how its traffic
routed, who routes through its net.
• Intra-AS: single admin, so no policy decisions needed
Scale:
• hierarchical routing saves table size, reduced update
traffic
Performance:
• Intra-AS: can focus on performance
• Inter-AS: policy may dominate over performance
Intra-AS Routing
• Also known as Interior Gateway Protocols (IGP)
• Most common IGPs:
– RIP: Routing Information Protocol
– OSPF: Open Shortest Path First
– IGRP: Interior Gateway Routing Protocol (Cisco
proprietary)
OSPF
• Represents the network as a graph, and runs
the shortest path algorithm to find the path to
any router.
• Divide the network into areas for scalability.
– The backbone area is called area 0
– Within one area, a router has the same link state
database as all other routers.
– Route: local area  backbone  local area
OSPF
• Each router knows the shortest path to reach
routers within his area.
• Backbone routers also accept information
from area border routers to compute the
shortest path to reach other routers. Then
advertise this information to the border
routers, who tells routers inside the area. – To
be able to select the best exit router in an area
OSPF
• To learn the link state, use flooding
– select a designated router and let it to be adjacent
to all other routers in the same area. Only
exchange link state between the adjacent routers
• Messages include
– HELLO, LINK STATE UPDATE, LINK STATE ACK,
DATABASE DESCRIPTION, LINK STATE REQUEST
Inter-AS routing
Internet Inter-AS routing: BGP
• BGP (Border Gateway Protocol): the de facto standard
• Path Vector protocol:
– similar to Distance Vector protocol
– each Border Gateway broadcast to neighbors
(peers) entire path (I.e, sequence of ASs) to
destination
– E.g., Gateway X may send its path to dest. Z:
Path (X,Z) = X,Y1,Y2,Y3,…,Z
Internet Inter-AS routing: BGP
• BGP messages exchanged using TCP.
• BGP messages:
– OPEN: opens TCP connection to peer and
authenticates sender
– UPDATE: advertises new path (or withdraws old)
– KEEPALIVE keeps connection alive in absence of
UPDATES; also ACKs OPEN request
– NOTIFICATION: reports errors in previous msg;
also used to close connection
Internet Inter-AS routing: BGP
Suppose: gateway X send its path to peer gateway W
• W may or may not select path offered by X
– cost, policy (don’t route via competitors AS), loop
prevention reasons.
•
•
If W selects path advertised by X, then:
Path (W,Z) = W, Path (X,Z)
Note: X can control incoming traffic by controlling its route advertisements to peers:
– e.g., don’t want to route traffic to Z  don’t advertise any
routes to Z
BGP: an example
NLRI=128.186.0.0/16
NLRI=128.186.0.0/16
ASPATH=[10]
ASPATH=[0]
128.186.0.0/16
NLRI=128.186.0.0/16
ASPATH=[10]
NLRI=128.186.0.0/16
ASPATH=[210] NLRI=128.186.0.0/16
ASPATH=[3210]
NLRI=128.186.0.0/16
NLRI=128.186.0.0/16
ASPATH=[4210]
ASPATH=[210]
NLRI=128.186.0.0/16
ASPATH=[7610]
NLRI=128.186.0.0/16
ASPATH=[610]
NLRI=128.186.0.0/16
ASPATH=[610]
[3210]*
[4210]
[7610]