Slide 1
1
CMPT 471
Networking II
Addressing
assigning networks and sub-networks
© Janice Regan, 2012-2018
© Janice Regan, 2012-2018
2
Internet addresses: IPv4
32 bit global internet (IP) address is used to uniquely identify a particular network interface connected to a particular host as a destination for communication
Globally applicable and globally unique
Expressed a series of 32 binary digits
10000000 00001011 00000011 00011111
Also expressed in dotted decimal notation
Binary digits are separated into four groups of eight digits
Each group of 8 digits are translated to a decimal number
The decimal number are separated by dots (periods)
Example address above becomes 128.11.3.31
© Janice Regan, 2012-2018
3
Structure of an IP address
Each IP address is split into two parts (netid, hostid) to identify the host and the network to which the host is connected
The netid (network address or prefix) identifies the network to which the host belongs.
The number of bits dedicated to the netid will determine the number of possible networks.
The hostid identifies the particular host (network interface for a multi homed host)
The number of bits dedicated to the hostid will determine the possible number of hosts on the network
© Janice Regan, 2012-2018
4
Allocating addresses to networks
Have considered some addresses reserved for particular purposes.
How are the remainder of the addresses in the IP address space allocated to networks?
Originally, the IPv4 protocol originally separated addresses into different classes, allowing for particular numbers of networks in each class. The addressing was know as classful addressing
Later, when the number of networks began to exceed the available network addresses an extended solution was needed. The solutions implemented were
Long term solution: new version of the IP protocol IPv6
Short term solution classless addressing or CIDR
© Janice Regan, 2012-2018
5
Classful addressing
© Janice Regan, 2012-2018
6
IP Addresses – Class A
First digit a 0
Small netid (7 bits) ⇨ 27-5 available networks
Large hostid (24 bits) ⇨ 224-2 hosts per network
Unicast address range, 0.0.0.0 to 127.255.255.255 does not include the following reserved addresses
0.0.0.0/8 ‘this’ network
10.0.0.0/8 private internets
14.0.0.0/8 Public data networks
24.0.0.0/8 IP over cable
127.0.0.0/8 loopback
Few networks each with many hosts.
© Janice Regan, 2012-2018
7
IP Addresses – Class B
First digits 10
medium netid (14 bits) ⇨ 214 available networks
medium hostid (16 bits) ⇨ 216-2 available hosts/network
Unicast address range 128.0.0.0 to 191.255.255.255 does not include the following reserved addresses
169.254.0.0/16 ‘local’ autoconfiguration
(for example when no DHCP server found)
172.16.0.0/12 reserved for private internets
moderate number of networks and hosts
© Janice Regan, 2012-2018
8
IP Addresses – Class C
First digits 110
large netid (21 bits) ⇨ 221 available networks
small hostid (8 bits) ⇨ 28-2 available hosts/network
Address range 192.0.0.0 to 223.255.255 does not include the following reserved addresses
192.168.0.0 – 192.168.255.0 reserved for private internets.
Large number of networks each with a small number of hosts (<256)
© Janice Regan, 2012-2018
9
Classful Addressing: forwarding
The original routing algorithms depended on each network having a network address that was either a Class A, B, C, D, or E address.
Each network would have one entry in the routing table of each router.
The entry would indicate the network address of the destination network and the interface on the present router through which the packet should be sent to reach that destination network.
The network portion of the incoming packets destination address would be compared to all entries of the correct class in the routing table to determine the interface through which the packet should be forwarded
© Janice Regan, 2012-2018
10
Problems with classful
Large networks were difficult to administer and needed some internal structure to simplify their administration. (solution sub-netting)
With the explosive growth of the Internet Class B networks were in short supply.
Many organizations wanted more addresses than a class C address could supply but not as many as a class B address would give.
Giving multiple class C addresses was one solution but it had its own problems, increasing the load on the network due to routing (one table entry for each class C network)
Short term solution CIDR, long term solution IPv6
Subnetting
To manage the addresses within a large network, the network manager will likely divide the network into smaller sub-networks
For classful addressing this consisted of dividing a class B network into networks the size of a class C network (or an A into B’s and C’s). Then using internal routing between sub networks
For CIDR, there is more flexibility in subnet size
© Janice Regan, 2012-2018
11
© Janice Regan, 2012-2018
12
Classless InterDomain Routing
CIDR (also called supernetting) Permits allocation of the remaining IP addresses in blocks more closely matched to user needs
Makes routing algorithms more complex (cannot sort by class to simplify forwarding)
Addresses are allocated based on a base address and a subnet mask or prefix, for 202.25.8.0/22
202.25.8.0 is the first allocated address or base address. The base address is the network address
The netmask is 11111111 11111111 11111100 00000000, 22 1’s followed by 0’s to make up the rest of the 32 bits
© Janice Regan, 2012-2018
13
CIDR: Using masks, prefixes
Consider a 1024 address block, a 2048 address block, and a 4096 address block of addresses.
These addresses are to be allocated in what would have been the class C portion of the address space.
The allocated addresses are
202.35.8.0 to 202.35.11.255 (202.35.8.0/22)
1024 addresses with netmask 255.255.252.0 (22 1 bits)
202.35.24.0 to 202.35.31.255 (202.35.16.0/21)
2048 addresses with netmask 255.255.248.0 (21 1 bits)
202.35.32.0 to 202.35.47.255 (202.35.32.0/20)
4096 addresses with netmask 255.255.240.0 (20 1 bits)
13
© Janice Regan, 2012-2018
14
CIDR addressing
1024
00
0
0
4
8
12
16
20
24
28
32
36
40
44
48
00
0
2048
0
8
16
24
32
40
48
4096
0
16
32
48
Blue bars show all possible addresses, we will group consecutive addresses to make networks. The numbers on axes show particular addresses for reference: 16 means 202.35.16.0, 28 means 202.35.28.0 … The red portions show the networks listed on the previous slide.
202.35.8.0/22 is shown in red in the top illustration,
contains 2(32-22) addresses starting with 202.35.8.0 and ending with 202.35.11.255
2
14
© Janice Regan, 2012-2018
15
CIDR: Assigning networks
If K host addresses are desired and (2N-1)-2 < K < (2N)-2 the netmask will have 32-N bits
The base address will fall on a 2N boundary, that is the binary form of the base address will be an even multiple of 2N.
The base address will have all zero bits for the bits that are zero in the netmask. If an address within the allocated range is ANDed with the netmask the result will be the base address of the allocated range
© Janice Regan, 2012-2018
16
CIDR: Routing
A router will have a list of networks to which it connects
A destination address will be ANDed with the netmask for each network, and the result will be compared with the base address of the network
If the ANDed destination address gives the network base address the router knows it has found a candidate for the correct network to forward the package to. The candidate with the longest match is chosen
In order to reduce the size of router tables aggregation is used. Networks in a given region/location are aggregated into a larger network for the purpose of forwarding.
© Janice Regan, 2012-2018
17
A sample routing table
Destination Gateway Genmask Metric Iface
196.74.0.0 * 255.255.240.0 0 Eth0
196.74.16.0 * 255.255.248.0 0 Eth1
196.74.24.0 * 255.255.248.0 0 Eth2
196.74.32.0 * 255.255.252.0 0 Eth3
196.74.36.0 * 255.255.252.0 0 Eth4
196.74.48.0 * 255.255.240.0 0 Eth5
© Janice Regan, 2012-2018
18
CIDR: Using net masks
Given an address in one of these ranges, ANDing the address with the appropriate netmask should give the base address of that network
For example test to see if 196.74.35.57 is in the fourth block or addresses 196.74.32.0/22
11000100 01001010 00100011 00111001 addresss
11111111 11111111 11111100 00000000 netmask
11000100 01001010 00100000 00000000
address AND netmask
196.74.32.0 the base address of the fourth block, therefore, the address is a member of the fourth block of addresses
© Janice Regan, 2012-2018
19
Hierarchical addressing: 1
CIDR is a hierarchical addressing approach
Groups of networks can be aggregated to appear as a single network to more distant routers
Entries that appear to be a single network to a particular router may in fact be aggregations of many smaller networks
© Janice Regan, 2012-2018
20
Hierarchical addressing: 2
CIDR (RFC 1518, 1519)
Points out that CIDR replaces both sub and super netting, so long as addresses are assigned in blocks with size equal to an integer power of 2 network and host portions are readily separated with a mask
IANA (the organization in charge of administering distribution of IP addresses) has three regional registries
ARIN: North America
RIPE: Europe
APNIC: Asia
LACNIC: South America
Each of these registries was given a large block of addresses
© Janice Regan, 2012-2018
21
Hierarchical addressing: 3
Each of the regional registries grants blocks of addresses to each country in its region
Each country may grant addresses on a regional basis within the country
Each country or region of a country will grant addresses to large IP providers and or companies for their networks
These providers or companies apportion addresses to their users
Hierarchical addressing: 3
Caveat
CIDR was introduced after many addresses had already been allocated using the classful system.
Some blocks of addresses are not within their “assigned” areas because they were assigned before CIDR was introduced.
The CIDR routing algorithm will still get the packets to the right place, as explained in the following example
© Janice Regan, 2012-2018
22
© Janice Regan, 2012-2018
23
CIDR example problem
You are a administrator for ABC EngCo. Your company has been assigned the CIDR address block 196.74.0.0/17
Your predecessor has assigned three project groups to sub networks 196.74.16.0/21, 196.74.32.0/22, and 196.74.48.0/20
You have been asked to allocate networks for three additional groups with the following numbers of hosts needing addresses 2000, 512, and 3500
© Janice Regan, 2012-2018
24
Available addresses?
Your block of addresses 196.74.0.0/17, has 2(32-17)=32768 addresses,
196.74.0.0 to 196.74.127.255
Networks already allocated
196.74.16.0 to 196.74.23.255 (196.74.16.0/21)
2048 addresses
196.74.32.0 to 196.74.35.255 (196.74.32.0/22)
1024 addresses
196.74.48.0 to 196.74.63.255 (196.74.48.0/20)
4096 addresses
© Janice Regan, 2012-2018
25
Allocated / available space
1024
0
0
4
8
12
16
20
24
28
32
36
40
44
48
0
2048
4096
1024
00
0
52
56
60
64
4096
196.74.16.0/21
196.74.32.0/22
196.74. 48.0/20
00
0
0
4
8
12
16
20
24
28
32
36
40
44
48
52
56
60
64
00
0
0
4
8
12
16
20
24
28
32
36
40
44
48
00
0
52
56
60
64
Available space
Remaining portions of your address allocation
196.74.0.0/20 (4096 addresses)
196.74.0.0/21 and 196.74.8.0.0/21 (2 x 2048)
196.74.0.0/22, 196.74.4.0/22, 196.24.8.0/22, 196.74.12.0.0/22
196.74.24.0/21 (2048 addresses)
196.74.36.0/22 (1024 addresses)
196.74.40.0/21 (2048 addresses)
196.74.64.0/18 (16384 addresses)
© Janice Regan, 2012-2018
26
How big are our new networks?
You have been asked to allocate networks with 2000, 512, and 3500 hosts
If K host addresses are desired and (2N-1)-2 < K < (2N)-2 the netid will have 32-N bits
So we need
N=11 2048 addressed for the net with 2000 hosts
N=10 1024 addresses for the net with 512 hosts (note N=9 only provides 510 addresses for hosts)
N=12 4096 addresses for the net with 3500 hosts
© Janice Regan, 2012-2018
27
© Janice Regan, 2012-2018
28
Allocating new networks
Start with the largest as it will be the most difficult to find space for. There is a block starting at 196.74.0.0 (a 4096 boundary) that is large enough to hold this network.
Also at 196.74.64.0, 196.74.80.0 … 196.74.112.0 (4 possible)
Next consider the 2048 block, there are two possible locations starting on a 2048 boundary that have enough available space 196.74.24.0 and 196.74.40.0
Also at 196.74.64.0, 196.74.82.0, … 196.74.120.0 (8 possible)
Finally consider the 1024 block. Place the block on a 1024 boundary (preferably one that is not also a 2048 or 4096 boundary) say 196.74.36.0.
Also at 176.74.64.0, 196.74.78.0 … 196.74.124.0 (16 possible
Why choose these networks
These networks were chosen to leave the maximum possible flexibility to add further networks in the future.
Decisions might be different if it were necessary to leave room for significant room for growth of these networks in the future. (For example you might want to leave room to double network size)
© Janice Regan, 2012-2018
29
© Janice Regan, 2012-2018
30
Allocated / available space
0 indicates address 196.74.0.0
12 indicates address 196.74.12.0
00
0
0
4
8
12
16
20
24
28
32
36
40
44
48
0
00
0
52
56
60
64
4096
196.74.0.0/20
196.74.24.0/21
196.74.36.0/22
00
0
0
4
8
12
16
20
24
28
32
36
40
44
48
00
0
52
56
60
64
00
0
0
4
8
12
16
20
24
28
32
36
40
44
48
00
0
52
56
60
64
© Janice Regan, 2012-2018
31
Our example network
To Internet
To Internet
Router0
196.74.0.0/20
196.74.16.0/21
196.74.24.0/21
196.74.32.0/22
196.74.36./22
196.74.48.0/20
196.74.0.0/18
196.72.0.111
© Janice Regan, 2012-2018
32
Aggregation for our example
If the six networks in our example were all in the same distant city we would to refer to them with one router table entry with network address/mask 196.74.0.0/18
Alternately we could aggregate including the unused address space (64 to 128) using one router table entry for network address/mask 196.74.0.0/17.
The networks shown above (or the whole address space assigned to ABC EngCo) can be aggregated into one entry for routing tables outside ABC EngCo
4096
4096
196.74.36.0/22
00
0
0
4
8
12
16
20
24
28
32
36
40
44
48
00
0
0
52
56
60
64
© Janice Regan, 2012-2018
33
A sample routing table: Router 0
Inside ABC EngCo
Destination Gateway Genmask Metric Iface
196.74.0.0 * 255.255.240.0 0 Eth0
196.74.16.0 * 255.255.248.0 0 Eth1
196.74.24.0 * 255.255.248.0 0 Eth2
196.74.32.0 * 255.255.252.0 0 Eth3
196.74.36.0 * 255.255.252.0 0 Eth4
196.74.48.0 * 255.255.240.0 0 Eth5
IPv4 Router table for router at ABC ENGCO’s site
© Janice Regan, 2012-2018
34
A sample routing table: Router 0
Routers at the Internet provider for ABC EngCo will see the networks there as a single network.
To reach ABC EngCo these routers will have a single entry for Destination 196.74.0.0/17 with netmask 255.255.128.0 and gateway set to the address of the router that sits between ABC EngCo’s networks and the internet. (196.72.0.111)
© Janice Regan, 2012-2018
35
Expanding our example: Regional
The Internet provider in the city where ABC EngCo is located allocated the block of addresses you have been working with from its block of 196.72.0.0/14
For arguments sake assume this block is from a Canadian allocation (see if you can find where it really is)
Routing tables: outside provider
Users who are not using ABC EngCo’s internet provider use a single entry in their routing table for that internet provider (that entry includes ABC EngCo).
The entry in other router tables outside ABC EngCo’s Internet provider would be for network 196.72.0.0/14. This entry includes ABC EngCo and all the other customers of that Internet provider
© Janice Regan, 2012-2018
36
Routing Tables: outside Canada
Continuing the generalization, the routing tables outside Canada could have a single entry for all of Canada
That single entry might include the addresses administered by ABC EngCo’s internet provider
© Janice Regan, 2012-2018
37
© Janice Regan, 2012-2018
38
Return to our example
The aggregated address for ABC EngCo,
196.74.0.0/17, includes all ABC EngCo’s addresses
Let us consider an additional complication
What if the network196.74.44/22 belongs to ARTSCO?
ARTSCO owned these addresses before ABC EngCo received their address block.
How does this change the entries to the routing tables we just discussed?
196.74.44.0/22
4096
00
0
0
4
8
12
16
20
24
28
32
36
40
44
48
00
0
52
56
60
64
© Janice Regan, 2012-2018
39
Additions to routing tables
What if the network196.74.44/22 belongs to ARTSCO?
ARTSCO owned these addresses before ABC EngCo received their address block.
Then an additional entry would be added to each the external routing tables discussed for 196.74.44.0/22.
When the routing algorithm checked for matches for an address within 196.74.44.0/22 two matches would be found ABC EngCo (or aggregate) and 196.74.44.0/22,
The longest match, has the most matching higher order bits. The length of the netid is the number of matching bits. For 196.74.44.0/22 there are 22 matching bits. For 196.72.0.0/14 there are 14 matching bits.
The routing table entry with the most matching bits would be for ARTSCO so the packets would be delivered to the correct location
00
0
00
0
© Janice Regan, 2012-2018
40
A new European Sales office
ABC EngCo is opening a new European sales office and wishes to use some of its remaining IP addresses 196.74.40.0/23 to service the European office
Now the European routers will need an additional entry for 196.74.40.0/23 routing it to the correct European location
© Janice Regan, 2012-2018
41
Return to our example
The aggregated address for ABC EngCo,
196.74.0.0/17, includes all ABC EngCo’s addresses
Let us consider an additional complication
What if the network196.74.40/23 is for the European office?
How does this change the entries to the routing tables we just discussed?
196.74.40.0/23
4096
00
0
0
4
8
12
16
20
24
28
32
36
40
44
48
00
0
52
56
60
64
© Janice Regan, 2012-2018
42
A new European Sales office
Consider any routing table outside ABC EngCo
What happens with two entries in the routing table both match the destination address 196.74.40.37
196.72.0.0/14 14 bit network address matches
196.74.0.0/17 17 bit network address matches
196.74.40.0/23 23 bit network address matches
The longest match is selected, so the packet will go directly to the European office
© Janice Regan, 2012-2018
43
Sending packets from Europe
Consider sending a packet with address 196.74.18.23
In Europe the router may have a routing table entry for 196.0.0.0/8 routed through a gateway to North America
That gateway may have a routing table entry for the regional provider 196.72.0.0/14 using the providers router as a gateway
The providers router will have an entry for 196.74.0.0/17 to send the packet to ABC EngCo through ABC EngCo’s router
/docProps/thumbnail.jpeg