Transcript LOOKUPS AND CLASSIFICATION

IP Addressing
and CIDR
High Performance
Switching and Routing
Telecom Center Workshop: Sept 4, 1997.
COMP680E by M. Hamdi
1
IP Addresses
32 bits
version
(4 bits)
header
length
Type of Service/TOS
(8 bits)
flags
(3 bits)
Identification (16 bits)
TTL Time-to-Live
(8 bits)
Total Length (in bytes)
(16 bits)
Protocol
(8 bits)
Fragment Offset (13 bits)
Header Checksum (16 bits)
Source IP address (32 bits)
Destination IP address (32 bits)
Ethernet Header
IP Header
TCP Header
Application data
Ethernet Trailer
Ethernet frame
COMP680E by M. Hamdi
2
IP Addresses
32 bits
0x4
0x5
0x00
9d08
12810
4410
0102
00000000000002
0x06
8bff
128.143.137.144
128.143.71.21
Ethernet Header
IP Header
TCP Header
Application data
Ethernet Trailer
Ethernet frame
COMP680E by M. Hamdi
3
What is an IP Address?
• An IP address is a unique global address for a
network interface
• Exceptions:
– Dynamically assigned IP addresses ( DHCP)
– IP addresses in private networks ( NAT)
• An IP address:
-
is a 32 bit long identifier
- encodes a network number (network prefix) and a
host number
COMP680E by M. Hamdi
4
Hosts, Networks, and Routers
Host 7
Host 1
Network A
Host 2
Host 1
Router
Network B
Network C
Unique IP Address =
Network Number + Host Number
Host 12
Host 2
COMP680E by M. Hamdi
5
IP Addresses come in two parts
11111111 00010001 10000111 00000000
Network Number
Host Number
Where is this dividing line?
Well, that depends ....
COMP680E by M. Hamdi
6
Actually, IP addresses Identify Interfaces
Host 7
Host 1
Network A
Network C,
Host 3
Host 2
Network A,
Host 1
Host 3
Network B
Host 12
Network B,
Host 77
Host 2COMP680E by M. Hamdi
Network C
Machines can have more
than one IP address.
All routers do!
7
IP Forwarding Table
Destination
Net A
Net B
Net C, Host 3
Net C
A destination is usually
a network. May also be
a host, or a “gateway
of last resort” (default)
Next Hop
Router 1
Direct
Router 2
Router 1
The next hop is
either a directly
connected network or a
router on a directly
connected network
COMP680E by M. Hamdi
Interface
INT 7
INT 4
INT 3
INT 7
A physical interface
8
IP Forwarding Process
1. Remove a packet
from an input
queue
2. Check for correctness
decrement TTL
field
4. Place packet on
correct output
queue
Forwarding Process
If queues
get full, just
drop packets!
3. Match packet’s
destination to
a table entry
If queues
get full, just
drop packets!
IP Forwarding Table
Router
COMP680E by M. Hamdi
9
Architecture of Routing Protocols
Interior Gateway
Protocols (IGP) :
inside autonomous
systems
AS 701
Exterior Gateway
Protocols (EGP) :
between autonomous
systems
UUNet
OSPF, IS-IS,
RIP, EIGRP, ...
BGP
IGP
Policy Based
Metric Based
IGP
IGP
EGP
Sprint
AS 6431
AT&T
Common Backbone
AS 7018
COMP680E by M. Hamdi
10
The Most Common Routing Protocols
BGP
RIP
Cisco proprietary
TCP
UDP
IP
OSPF IS-IS EIGRP
(and ICMP)
Routing protocols exchange network
reachability information between routers.
COMP680E by M. Hamdi
11
What is a Routing Process?
Manual configuration
import
information
from other
routers
Routing
Process
Protocol-Specific
Routing Table
export
information
to other
routers
OS kernel
IP Forwarding Table
Router
COMP680E by M. Hamdi
12
Many routing processes can run on a single router
BGP
RIP Process
BGP Process
RIP Routing tables
BGP Routing tables
OSPF Process
OSPF Routing tables
RIP
Domain
OS kernel
OSPF
Domain
IP Forwarding Table
COMP680E by M. Hamdi
13
Basic Architectural Components
of an IP Router
Routing
Protocols
Routing
Table
Control Plane
Forwarding
Switching
Table
COMP680E by M. Hamdi
Datapath
per-packet
processing
14
Two components of routing
• Control component
– Decides where the packets will
go
– Use a set of routing protocols
(e.g. OSPF, BGP) to collect
information and produce a
“forwarding table”
– “Control plane”
routes
Routing “daemon”
collect routing info
and maintain
routing DB
kernel
Forwarding
table
• Forwarding component
– Moving packets from input to
output ports according to
forwarding table and packet
header
– “Forwarding plane”
packets Forwarding
COMP680E by M. Hamdi
algorithm and
mechanism
15
IP Addresses come in two parts
11111111 00010001 10000111 00000000
Network Number
Host Number
Where is this dividing line?
Well, that depends ....
COMP680E by M. Hamdi
16
Classful Addresses
Class A
0nnnnnnn hhhhhhhh hhhhhhhh hhhhhhhh
Class B
10nnnnnn nnnnnnnn hhhhhhhh hhhhhhhh
Class C
110nnnnn nnnnnnnn nnnnnnnn hhhhhhhh
n = network address bit
COMP680E by M. Hamdi
h = host identifier bit
17
The Classful Address Space
Class
Networks Hosts
Share of IP
address space
16,777,214 1/2
A
127
B
C
16,384
65,534
2,097,152 254
1/4
1/8
Leads to very inefficient allocation of addresses …
COMP680E by M. Hamdi
18
Problems with Classful IP Addresses
• By the early 1990s, the original classfull address scheme
had a number of problems
– Flat address space. Routing tables on the backbone Internet
need to have an entry for each network address. By the 1993,
the size of the routing tables started to outgrow the capacity of
routers (C networks).
Other problems:
– Too few network addresses for large networks
• Class A and Class B addresses were gone
– Limited flexibility for network addresses:
• Class A and B addresses are overkill (>64,000 addresses)
• Class C address is insufficient (requires 40 Class C addresses)
COMP680E by M. Hamdi
19
Allocation of Classful Addresses
COMP680E by M. Hamdi
20
Flat Network Addressing
P
Y
T
W
X
S
Exports at least 12
network addresses
This router needs
at least
12 table entries
R
N
V
Q
U
Z
COMP680E by M. Hamdi
21
Limitations of Classful IP Addressing
Wastes
Adds
Multiple
IP Addresses
Entries to Routing Tables
Class C
B
Network
Network
ID
ID
255
w
255
x
Company Network IDs
192.168.1.0
255
0
y
Host IDHost ID
0
z
Internet
192.168.2.0
192.168.3.0
Network of 2000 Computers
Assigned
192.168.4.065,534 IP Addresses
192.168.5.0
192.168.6.0
192.168.7.0
192.168.8.0
63,534
Wasted
Portion of Internet Routing Tables
192.168.1.0 255.255.255.0
192.168.2.0 255.255.255.0
192.168.3.0 255.255.255.0
192.168.4.0
2000255.255.255.0
192.168.5.0 255.255.255.0
Allocated
192.168.6.0
255.255.255.0
192.168.7.0 255.255.255.0
192.168.8.0 255.255.255.0
COMP680E by M. Hamdi
192.168.1.1
192.168.2.1
192.168.3.1
192.168.4.1
192.168.5.1
192.168.6.1
192.168.7.1
192.168.8.1
22
Subnets
• The idea is to share the same IP network
number among multiple subnets
• Subnets of a network should reside in the
same general locale (e.g., college campus,
corporate location, …)
• Routers on an IP network know their local
subnets
• Remote routers need to know only the network
address
COMP680E by M. Hamdi
23
Subnetting
• Problem: Organizations
have multiple networks
which are independently
managed
– Solution 1: Allocate a
separate network address
for each network
University Network
Engineering
School
• Difficult to manage
• From the outside of the
organization, each
network must be
addressable.
– Solution 2: Add another
level of hierarchy to the
IP addressing structure
COMP680E by M. Hamdi
Medical
School
Library
Subnetting
24
Address assignment with subnetting
• Each part of the organization is allocated a range of IP
addresses (subnets or subnetworks)
• Addresses in each subnet can be administered locally
128.143.0.0/16
University Network
128.143.71.0/24
128.143.136.0/24
Engineering
School
Medical
School
128.143.56.0/24
Library
128.143.121.0/24
COMP680E by M. Hamdi
25
Basic Idea of Subnetting
• Split the host number portion of an IP address into a
subnet number and a (smaller) host number.
• Result is a 3-layer hierarchy
network prefix
network prefix
host number
subnet number
host number
• Then:
extended network prefix
• Subnets can be freely assigned within the organization
• Internally, subnets are treated as separate networks
• Subnet structure is not visible outside the organization
COMP680E by M. Hamdi
26
Subnetmask
• Routers and hosts use an extended network prefix
(subnetmask) to identify the start of the host numbers
128.143
137.144
network prefix
host number
128.143
137
144
network prefix
subnet
number
host number
extended network prefix
1111111111111111 1111111100000000
subnetmask
COMP680E by M. Hamdi
27
Advantages of Subnetting
• With subnetting, IP addresses use a 3-layer
hierarchy:
» Network
» Subnet
» Host
• Reduces router complexity. Since external routers
do not know about subnetting, the complexity of
routing tables at external routers is reduced.
• Note: Length of the subnet mask need not be
identical at all subnetworks.
COMP680E by M. Hamdi
28
Example: Subnetmask
• 128.143.0.0/16 is the IP address of the network
• 128.143.137.0/24 is the IP address of the subnet
• 128.143.137.144 is the IP address of the host
• 255.255.255.0 (or ffffff00) is the subnetmask of
the host
• Use of subnetting or length of the subnetmask is
decided by the network administrator
• Consistency of subnetmasks is the responsibility
of administrator
COMP680E by M. Hamdi
29
No Subnetting
• All hosts think that the other hosts
are on the same network
128.143.137.32/16
subnetmask: 255.255.0.0
128.143.137.144/16
subnetmask: 255.255.0.0
128.143.71.21/16
subnetmask: 255.255.0.0
128.143.71.201/16
subnetmask: 255.255.0.0
128.143.70.0/16
COMP680E by M. Hamdi
30
With Subnetting
• Hosts with same extended network
prefix belong to the same network
128.143.137.32/24
128.143.137.144/24
128.143.71.21/24
128.143.71.201/24
subnetmask: 255.255.255.0
subnetmask: 255.255.255.0
subnetmask: 255.255.255.0
subnetmask: 255.255.255.0
128.143.137.0/24
Subnet
128.143.71.0/24
Subnet
128.143.0.0/16
COMP680E by M. Hamdi
31
Variable Length Subnet Masks
• With only a single subnet mask across a network
prefix, an organization was locked into a fixed
number of fixed size subnets
• When a network is assigned more than one subnet
mask, it is considered a network with “variable
length subnet masks” since extended-networkprefixes have different lengths
• VLSM permits slicing and dicing subnets into
different sizes and therefore numbers of hosts in
subnets under a single Network ID, thereby
minimizing, if not eliminating, wasted addresses.
COMP680E by M. Hamdi
32
With Subnetting
• Different subnetmasks lead to different
views of the size of the scope of the
network
128.143.137.32/26
128.143.137.144/26
subnetmask: 255.255.255.192 subnetmask: 255.255.255.192
128.143.137.0/26
Subnet
128.143.71.21/24
128.143.71.201/16
subnetmask: 255.255.255.0
subnetmask: 255.255.0.0
128.143.137.128/26
Subnet
128.143.71.0/24
Subnet
128.143.0.0/16
COMP680E by M. Hamdi
33
Mask may vary with location
12.0.0.0/16
12.1.0.0/16
12.2.0.0/16
12.3.0.0/16
12.0.0.0/8
This allows
all of these
(sub)networks
to be aggregated
into one entry in
an IP forwarding
table
:
:
:
12.253.0.0/16
12.254.0.0/16
12.3.0.0/24
12.3.1.0/24
:
:
:
:
:
12.3.254.0/24
12.253.0.0/19
12.253.32.0/19
12.253.64.0/19
12.253.96.0/19
12.253.128.0/19
12.253.160.0/19
12.253.192.0/19
COMP680E by M. Hamdi
34
Hierarchical Network Addressing
(Subnetting and Supernetting)
Network Z-T
M
Q
Z
M
K
Network Z
T
P
This is called
Aggregation
W
S
This Router needs
only 3 table entries
for networks Z-T,
Z-S, and Z-U
P
F
J
Exports only
one Address
W
U
S
X
Network Z-U-X
COMP680E by M. Hamdi
35
Optimizing the Allocation of IP
Addresses
After Subnetting
Before
After
Supernetting:
Supernetting:
220.78.168.0
220.78.168.64
220.78.168.128
220.78.168.0
220.78.168.192
220.78.169.0
220.78.169.0
220.78.170.0
220.78.169.64
220.78.171.0
220.78.168.0
220.78.169.128
220.78.172.0
220.78.169.192
220.78.173.0
220.78.170.0
Router
A
Router
RouteA
rA
Routing
RoutingTable
TableforforRouter
RouterB B
220.78.168.0
220.78.168.0
220.78.169.0
220.78.170.0
220.78.171.0
220.78.172.0
220.78.173.0
220.78.174.0
220.78.175.0
255.255.255.0
255.255.255.0
255.255.255.0
255.255.255.0
255.255.255.0
255.255.255.0
255.255.255.0
255.255.255.0
255.255.255.0
220.78.168.1
220.78.168.1
220.78.168.1
220.78.168.1
220.78.168.1
220.78.168.1
220.78.168.1
220.78.168.1
220.78.168.1
Router B
Router B
220.78.174.0
220.78.170.64
220.78.175.0
COMP680E by M. Hamdi
36
CIDR - Classless Interdomain Routing
• IP backbone routers have one routing table entry for
each network address:
– With subnetting, a backbone router only needs to know one
entry for each Class A, B, or C networks
– This is acceptable for Class A and Class B networks
• 27 = 128 Class A networks
• 214 = 16,384 Class B networks
– But this is not acceptable for Class C networks
• 221 = 2,097,152 Class C networks
• In 1993, the size of the routing tables started to
outgrow the capacity of routers
• Consequence: The Class-based assignment of IP
addresses had to be abandoned
COMP680E by M. Hamdi
37
CIDR - Classless Interdomain Routing
• Goals:
– New interpretation of the IP address space
– Restructure IP address assignments to increase
efficiency
– Permits route aggregation to minimize route table
entries
• CIDR (Classless Interdomain routing)
– abandons the notion of classes
– Key Concept: The length of the network prefix in
the IP addresses is kept arbitrary
– Consequence: Size of the network prefix must be
provided with an IP address
COMP680E by M. Hamdi
38
CIDR Notation
• CIDR notation of an IP address:
192.0.2.0/18
• "18" is the prefix length. It states that the first 18 bits are
the network prefix of the address (and 14 bits are available
for specific host addresses)
• CIDR notation can replace the use of subnetmasks (but
is more general)
– IP address 128.143.137.144 and subnetmask 255.255.255.0
becomes 128.143.137.144/24
• CIDR notation allows to drop trailing zeros of network
addresses:
192.0.2.0/18 can be written as 192.0.2/18
COMP680E by M. Hamdi
39
Why do people still talk about
• CIDR eliminates the concept of class A, B, and
C networks and replaces it with a network
prefix
• Existing classfull network addresses are
converted to CIDR addresses:
128.143.0.0
 128.143.0.0/16
• The change has not affected many (previously
existing) enterprise networks
– Many network administrators (especially on
university campuses) have not noticed the change
COMP680E by M. Hamdi
40
CIDR address blocks
• CIDR notation can nicely express blocks of addresses
• Blocks are used when allocating IP addresses for a
company and for routing tables (route aggregation)
CIDR Block Prefix
/27
/26
/25
/24
/23
/22
/21
/20
/19
/18
/17
/16
/15
/14
/13
# of Host Addresses
32
64
128
256
512
1,024
2,048
4,096
8,192
16,384
32,768
65,536
131,072
262,144
524,288
COMP680E by M. Hamdi
41
CIDR and Address assignments
• Backbone ISPs obtain large block of IP addresses space
and then reallocate portions of their address blocks to
their customers.
Example:
• Assume that an ISP owns the address block 206.0.64.0/18,
which represents 16,384 (214) IP addresses
• Suppose a client requires 800 host addresses
• With classful addresses: need to assign a class B address
(and waste ~64,700 addresses) or four individual Class Cs
(and introducing 4 new routes into the global Internet
routing tables)
• With CIDR: Assign a /22 block, e.g., 206.0.68.0/22, and
allocated a block of 1,024 (210) IP addresses.
COMP680E by M. Hamdi
42
Where do IP addresses come from?
IETF
Delegate
IANA
Allocate
RIR / NIR
Allocate
Network
Assign
User
COMP680E by M. Hamdi
43
IPv4 Address Allocation
IANA: Internet Assigned Numbers Authority
ARIN: American Registry for Internet Numbers
Source: iana.org
Total Addresses: 4,295m.
US Commercial
369m.
Reserved (IANA)
1,896m.
US Government 201m.
ARIN (N. America) 268m.
Asia/Pacific 151m.
Europe 218m.
International
COMP680E by M. Hamdi1,191m.
44
CIDR and Routing
• Aggregation of routing table entries:
– 128.143.0.0/16 and 128.142.0.0/16 are represented
as 128.142.0.0/15
• Longest prefix match: Routing table lookup finds the
routing entry that matches the longest prefix
What is the outgoing
interface for 128.143.137.0/24 ?
Route aggregation can be exploited
when IP address blocks are assigned
in an hierarchical fashion
Prefix
Interface
128.0.0.0/4
interface #5
128.128.0.0/9
interface #2
128.143.128.0/17 interface #1
Routing table
COMP680E by M. Hamdi
45
CIDR and Routing Information
Company X :
ISP X owns:
Internet
Backbone
206.0.68.0/22
206.0.64.0/18
204.188.0.0/15
209.88.232.0/21
ISP y :
209.88.237.0/24
Organization z1 :
Organization z2 :
209.88.237.192/26
209.88.237.0/26
COMP680E by M. Hamdi
46
CIDR and Routing Information
Backbone routers do not know
anything about Company X, ISP
Y, or Organizations z1, z2.
Company X :
ISP X does not know about
Organizations z1, z2.
Internet
ISP X sends everything which
Backbone
matches the prefix:
206.0.68.0/22
ISPISP
y sends
everything which matches
X owns:
the prefix:
206.0.64.0/18
209.88.237.192/26 to Organizations z1
204.188.0.0/15
209.88.237.0/26 to Organizations z2
209.88.232.0/21
ISP y :
206.0.68.0/22 to Company X,
209.88.237.0/24 to ISP y
Backbone sends everything
which matches the prefixes
206.0.64.0/18, 204.188.0.0/15,
209.88.232.0/21 to ISP X.
209.88.237.0/24
Organization z1 :
Organization z2 :
209.88.237.192/26
209.88.237.0/26
COMP680E by M. Hamdi
47
Classless Addressing (and CIDR)
• Eliminated class boundaries
• Introduced the notion of a variable length
prefix between 0 and 32 bits long
• Prefixes represented by P/l: e.g., 122/8,
212.128/13, 34.43.32/22, 10.32.32.2/32
etc.
• An l-bit prefix represents an aggregation
of 232-l IP addresses
COMP680E by M. Hamdi
48
IPv6 - IP Version 6
• IP Version 6
– Is the successor to the currently used IPv4
– Specification completed in 1994
– Makes improvements to IPv4 (no revolutionary changes)
• One (not the only !) feature of IPv6 is a
significant increase in of the IP address to 128
bits (16 bytes)
• IPv6 will solve – for the foreseeable future – the
problems with IP addressing
• 1024 addresses per square inch on the surface of the
Earth.
COMP680E by M. Hamdi
49
IPv6 Header
32 bits
version
(4 bits)
Traffic Class
(8 bits)
Payload Length (16 bits)
Flow Label
(24 bits)
Next Header
(8 bits)
Hop Limits (8 bits)
Source IP address (128 bits)
Destination IP address (128 bits)
Ethernet Header
IPv6 Header
TCP Header
Application data
Ethernet Trailer
Ethernet frame
COMP680E by M. Hamdi
50
IPv6 vs. IPv4: Address Comparison
• IPv4 has a maximum of
232  4 billion addresses
• IPv6 has a maximum of
2128 = (232)4  4 billion x 4 billion x 4 billion x 4
billion
addresses
COMP680E by M. Hamdi
51