Announcements

SUBNETS, CIDR, AND CLASSLESS ADDRESSING

Internet Protocols
CSC / ECE 573 Fall, 2005 N. C. State University

No office hours tomorrow (Wednesday) out of town No class on Thursday Fall break! Midterm exam next Tuesday! Study guide is online, as well as old exams HW3 Part 1 solutions will be online today

copyright 2005 Douglas S. Reeves

Todays Lecture
I. II. Problems with Classful Addresses Subnetting

III. Supernetting IV. CIDR V. IP Routing example

CLASSFUL ADDRESS PROBLEMS

copyright 2005 Douglas S. Reeves

Classful Addresses (Review)

Class A B C
1 7 24

Classful Addressing Issues

1. Three Bears problem
class A (16M hosts) too large for most organizations, and there arent very many of them (128) class C (254 hosts) too small for most class B (65,534 hosts) is just right, but there arent enough of them (16,384)

0 Network ID Host ID
2

10 Network ID
3

1 4

16

Host ID
2 1 8

110 Network ID Class A B C

Host ID

Potential Number Potential Number of of Networks Hosts Per Network 27 (128) 224 (16M) 14 (16K) 2 216 (64K) 221 (2M) 28 (256)
copyright 2005 Douglas S. Reeves

Flat host ID part of the address means very large routing tables within an organization
e.g., one network with 50,000 hosts each router has to know 50,000 routes?!

copyright 2005 Douglas S. Reeves

A Hypothetical Solution: Redefine Class C

E.g., use 19 bits for network ID, 10 bits for host ID
result: 512K such networks, each with 1022 host addresses

An Actual Solution: Assign Multiple Networks

Assign one organization multiple class C networks
E.g., an organization having 1000 hosts would get 4 class C networks (4 * 254 host addresses = 1016 > 1000)

Problem: not backwards compatible with original addressing scheme

i.e., old class B and C address space allocations would have to be reclaimed and reassigned

Problem: no longer have one network address for one organization

increases routing table sizes for routing between organizations is that serious?

Doesnt fix massive size of class A networks

copyright 2005 Douglas S. Reeves

copyright 2005 Douglas S. Reeves

Requirements for Address Modifications

solution should be backwards compatible Any with the original addressing scheme Each organization should be free to interpret the host ID part of its addresses any way it wishes
only the network ID part of addresses is used by other organizations

SUBNETTING

there is a new interpretation of the host ID If

all hosts and routers in the organizations network must use the new addressing scheme the internal routing protocol must support this new scheme
copyright 2005 Douglas S. Reeves

Subnet Addressing (RFCs 950, 1122)

Particularly useful for class B sized networks Example
0

Subnet Addressing (contd)

Result: large organizations may have many separate LANs, sharing a single network address
network administrators must decide how many bits to allocate to the subnet ID and host ID

16

local (internal) part 24

31

10

Network ID
Internet (external) part

Subnet IDHost ID Host ID

Hosts must support this capability Does not change classful addressing
only affects interpretation of local (internal) part of address

Address of the physical network

Result: three-level hierarchical addressing

good for routing inside an organization (reduces the size of internal routing tables) network structure not revealed to outsiders, since structure of local part only locally known
copyright 2005 Douglas S. Reeves

11

copyright 2005 Douglas S. Reeves

12

Example: Without Subnetting

Example: With Subnetting

Host Host
[Link] [Link]

Host Host
[Link]

Host Host
[Link] [Link]

Host
[Link]

[Link]

Host
[Link]

Host Host
[Link] [Link]

subnet [Link] Router R1 subnet [Link]

Router R1

Network [Link]
[Link] [Link] [Link]

subnet [Link]
[Link]

[Link]

Host

Host

Host to network [Link]

13

[Link]

[Link] [Link]

Host

Host

Host

Host
copyright 2005 Douglas S. Reeves

Host
copyright 2005 Douglas S. Reeves

14

How Long is the Subnet ID?

Masking: the process of extracting a portion of the IP address
subnet masking: extracting the subnet ID masks are 32 bits long for IPv4 addresses

Masking (Bitwise-AND Operation)

If a bit in a subnet mask =

1 this bit position is part of the physical network ID (network ID + subnet ID) 0 this bit position is part of the host ID

without subnetting

How split physical network ID into network and subnet parts?

copyright 2005 Douglas S. Reeves

with subnetting
copyright 2005 Douglas S. Reeves

15

16

Example
Step 1: determine network ID
IP Address = [Link] Use first 2 bits to determine its a Class B address

Questions
How can you tell if a destination IP address is
Network ID = 141.14

1. On the same subnet as you??? 2. On the same network as you???

Step 2: determine physical network address

IP Address = [Link] Mask with subnet mask [Link]

Physical Network = 141.14.2

Step 3: determine subnet ID

Physical Network = 141.14.2, Class B address = 141.14

Subnet ID = 2

copyright 2005 Douglas S. Reeves

17

copyright 2005 Douglas S. Reeves

18

Special Addresses (Subnetting)

Possible Subnet Sizes for a Class B Network

# of bits for subnet ID 0 (i.e., subnetting not used) # of subnets possible 1 2 22 23 . . . 213 214 # of hosts / subnet 216 - 2 215 - 2 214 - 2 213 - 2 . . . 23 2 = 4 22 2 = 2

Net ID (normal)

Subnet ID (normal)

Host ID All 1s

Description Broadcast to a specific subnet

1 2 3 . . .

What happened to 15 bits for subnet ID??? What happened to 16 bits for subnet ID???

13 14

copyright 2005 Douglas S. Reeves

19

copyright 2005 Douglas S. Reeves

20

Subnet Routing Recommendations

1. Use simple subnet masks (sequence of all 1s followed by string of all 0s)
e.g., 11111111111111111111000011110000 is not OK

Forwarding Decisions with Subnetting

Reminder: a forwarding table consists of <key, next IP address> entries key in forwarding table entries needs to consist of
1. a mask 2. a network identifier

Use the same mask for all subnets of the network 3. All subnets should be physically contiguous (connected)
drawbacks?
copyright 2005 Douglas S. Reeves

Examples
for network [Link] mask = [Link], identifier = [Link] for subnet [Link] mask = [Link], identifier = [Link]
21
copyright 2005 Douglas S. Reeves

22

Forwarding Decisions (contd)

Steps in determining a forwarding table match (in order of the table entries)
1. AND the packets destination IP address with the mask 2. compare the result to the identifier to see if there is a match 3. use the first match found

Forwarding Table Example

Mask [Link] [Link] [Link] Destination Identifier [Link] [Link] [Link] Next hop IP address

Which entry does [Link] match? Which entry does [Link] match? Which entry does [Link] match? Which entry does [Link] match? Why choose this ordering of the routing table entries?
copyright 2005 Douglas S. Reeves

23

copyright 2005 Douglas S. Reeves

24

Remember This Algorithm?

Extract destination address Hd, compute network part N if (N matches any directly connected networks) deliver to Hd directly else if (there is a host-specific route for Hd) forward datagram to specified next hop else if (there is a route for network N) forward datagram to specified next hop else if (there is a default route) forward datagram to default router else /* Hd is not directly connected and we */
/* dont know how to get to it
copyright 2005 Douglas S. Reeves

The New Forwarding Algorithm

extract destination address Hd for forwarding table entries i=1..n { if (Hd AND mask[i]) == destination[i] { forward datagram to specified next_hop[i] exit } }
/* we dont know how to get to Hd */

discard the datagram and declare routing error

*/
25
copyright 2005 Douglas S. Reeves

discard the datagram and declare routing error

26

Variable-Length Subnetting
Site with a Class C address [Link], needs five subnets with 60, 60, 60, 30, and 30 hosts Problems
cannot use subnet mask [Link], since it allows only 4 subnets, each with (28/ 4) - 2 = 62 hosts cannot use subnet mask [Link], since it allows 8 subnets, each with only (28 / 8) - 2 = 30 hosts

SUPERNETTING

Solution: use two masks of different lengths

router requirements RFC requires support for this however, not all routing protocols provide the subnet mask along with the destination network ID
copyright 2005 Douglas S. Reeves

27

Supernet Addressing
Possible solution to exhaustion of Class B addresses use multiple Class C addresses instead Assign organizations blocks of 2n contiguous Class C addresses
ex.: if 2000 addresses (hosts) are needed, allocate a block of 2048 addresses ( = 8 contiguous Class C networks)

Supernetting Example

(Note: subnets not shown for simplicity; subnets and supernets can be used together)

Problem: no longer have one network address for each organization

inter-organization routing tables will be larger
copyright 2005 Douglas S. Reeves

29

Classless InterDomain Routing (CIDR) (RFC1519)

Idea: allocate IP addresses in a block of size 2n, for n=2,3,.
In a block means IP addresses must be allocated contiguously (i.e., share the same high-order bits)

CLASSLESS INTERDOMAIN ROUTING (CIDR)

A block is summarized by a single routing table key of the form <network_address, CIDR_mask>
network_address: the smallest (first) address in the block CIDR_mask: the size of the address block

No longer need classful addresses; the network size is now explicit

but, backwards compatible with classful addresses
copyright 2005 Douglas S. Reeves

32

Classless InterDomain Routing (CIDR) (RFC1519) (contd)

CIDR_mask: number of 0s indicates value of n
11111111 11111111 11111000 00000000: n = 11 11111111 00000000 00000000 00000000: n = 24

CIDR Masking + Subnet Masking

IP address: 11000011 11001100 00110011 01000010

(i.e., class A address)

More conveniently for people: /32-n to indicate number of 1s in the mask

11111111 11111111 11111000 00000000: /21 11111111 00000000 00000000 00000000: /8

CIDR Mask: 11111111 11111111 11111100 00000000 Network ID: 11000011 11001100 00110000 00000000 Subnet Mask: 11111111 11111111 11111111 11000000 Network + Subnet ID: 11000011 11001100 00110011 01000000

copyright 2005 Douglas S. Reeves

33

copyright 2005 Douglas S. Reeves

34

Address Allocation and Masks

Ex.: allocate a block of 223 (= 8M) addresses, starting at address [Link]
Addre ss Lowest Highest Mask Dotted Decimal
[Link] [Link] [Link] ( /9 )

Regional Aggregation of Class C Addresses

All sites in a region (e.g., Europe) have a common prefix
Lowest [Link] [Link] [Link] [Link] Highest [Link] [Link] [Link] [Link] Region Europe North America Central and South America Asia and the Pacific

Binary
11000010 00000000 00000000 00000000 11000010 01111111 11111111 11111111 11111111 10000000 00000000 00000000

How can you tell what the mask should be

knowing the number of addresses? knowing the lowest and highest addresses?
copyright 2005 Douglas S. Reeves

35

copyright 2005 Douglas S. Reeves

36

Regional Allocation of Class C Addresses (contd)

CIDR summarizes these 32M addresses into one entry
i.e., only a single entry needed in most U.S. routers for all European destinations

Example: Allocating Classless Addresses

Three sites X, Y, and Z in Europe ask for 2048, 1024, and 4096 addresses, in that order, starting from [Link]. Result:
Site X Y Z # of Addresses 2048 = 211 1024 = 4096 = 210 212 Lowest [Link] [Link] [Link] Highest [Link] [Link] [Link] Mask [Link] (/21) [Link] (/22) [Link] (/20)

Once the packet gets to Europe, more detailed routing tables are needed to reach the specific network / host

Why is there a gap between site Ys allocation and site Zs allocation???

copyright 2005 Douglas S. Reeves

37

copyright 2005 Douglas S. Reeves

38

Allocating Classless Addresses (contd)

Result: routers all over Europe have the following 3 entries added to their routing tables
Network Address Mask 11000010 00011000 00000000 00000000 ([Link]) 11111111 11111111 11111000 00000000 ([Link], or /21) 11000010 00011000 00001000 00000000 ([Link]) 11111111 11111111 11111100 00000000 ([Link], or /22) 11000010 00011000 00010000 00000000 ([Link]) 11111111 11111111 11110000 00000000 ([Link], or /20)
copyright 2005 Douglas S. Reeves

Example: CIDR Forwarding

A packet arrives at a router with destination IP address = [Link]; where should it be forwarded?
11000010 00011000 00010001 00000100 ANDed with Site 1 mask = 11000010 00011000 00010000 00000000 match site 1 address? ANDed with Site 2 mask = 11000010 00011000 00010000 00000000 match site 2 address? ANDed with Site 3 mask = 11000010 00011000 00010000 00000000 match site 3 address?

Network Address Mask

Network Address Mask

39

copyright 2005 Douglas S. Reeves

40

Longest Prefix Matching

A forwarding table entry with a longer mask (i.e, more 1s) is called more specific than another entry with a shorter mask There is a dilemma in classless network masking: address matching ambiguity
X = 10110000 00000000 00000000 00000000 (/4) Y = 10110100 00000000 00000000 00000000 (/6) destination IP address
10110100 00000000 00000000 00110000

The CIDR Forwarding Algorithm

Extract destination address Hd Use mask to find longest matching prefix if (match found) forward datagram to specified next hop else /* we dont know how to get to Hd */ discard the datagram and declare routing error

Unified routing table lookup! Questions

How deal with default addresses? How deal with host-specific addresses?
copyright 2005 Douglas S. Reeves

will match both of these entries!

For forwarding purposes, the longest prefix (most specific match) wins! Ordering doesnt matter
copyright 2005 Douglas S. Reeves

41

42

CIDR Blocks Reserved for Private Networks

Useful for intranets, testing, etc. Should never see one of these addresses in IP packets in the public Internet
Prefix 10 /8 169.254 /16 172.16 /12 192.168 /16 Lowest Address Highest Address [Link] [Link] [Link] [Link] [Link] [Link] [Link] [Link]

FORWARDING EXAMPLE

copyright 2005 Douglas S. Reeves

43

Example Network Configuration

Routing Table for Router R1

copyright 2005 Douglas S. Reeves

46

Summary
What happens when R1 receives a packet with destination:
[Link]? [Link]? [Link]?

1. Classful addressing is simple, but too restrictive

Supernetting is a cheap (but not very clean) fix

2. Subnetting creates a third level of address hierarchy

useful for routing inside an organization requires the use of a mask

3. CIDR decreases routing table sizes, and increases flexibility in allocating addresses 4. Both subnetting and CIDR require the use of masks
copyright 2005 Douglas S. Reeves

47

copyright 2005 Douglas S. Reeves

48

Next Lecture
Routing, Part I

copyright 2005 Douglas S. Reeves

49