Lecture #3 - Classless Inter-Domain Routing
But first, appreciate your history!
Class A, B & C Networks
Initially, blocks of network addresses were allocated in three common formats:
- Class A
-
The leftmost byte of the address specifies the network
number and class, with the first byte ranging from 1 to 126.
- Class B
-
The leftmost two bytes specify network the number and
class. The first byte is in the range from 128 to 191.
- Class C
-
The leftmost three bytes specify network number and class.
The first byte ranges from 192 to 223.
However, there are a number of problems associated with this scheme. Firstly,
it assumes that the organisation has a single large network, rather than
multiple smaller networks. In the days of single collision domains
(ie. prior to switched Ethernet), this meant that every host on the network
would have to receive every packet that was sent on the network. This results
in performance implications and makes network management/segregation
effectively impossible to implement.
Secondly, this scheme allows for an organisation to have up to 254 hosts
(Class C), up to 65534 hosts (Class B) or up to 16,777,214 hosts (Class A).
If you have 1000 hosts then you would have to be assigned a Class B network
and simply waste the remaining 64634 IP addresses.
Subnetting
In order to address the challenges associated with classful address allocation,
the concept of subnetting was introduced, allowing Class A and Class B
networks to be split into smaller networks. These sub-networks (or subnets for
short) could then correspond to a single LAN, allowing traffic to be isolated
to the smaller network, unless it was destined for another subnet. This reduces
the amount of traffic on the overall network, improving performance and making
network management easier.
Subnetting was implemented by the use of a subnet mask
which consists of a "string of ones" followed by a "string of zeroes":
This mask, together with the network class, allows the
IP address to be subdivided into three parts - network, subnetwork
and host - creating an additional level of hierarchy that can be used
to perform internal routing. Routers could then forward an IP packet
(addressed to the local network) to the particular subnet in which the
destination host computer can be found. Externally the organisation network is
still known by its classful allocation.
Classless Inter-Domain Routing (CIDR)
Whilst subnetting addressed some of the issues resulting from class based
allocations, a number of problems still existed, namely those relating to
wasted IP addresses. Subnetworks have to all be the same size and furthermore
the subnets numbered zero and 255 cannot be used. Additionally, allocations
still lacked granularity - in other words you cannot get an allocation that
would suit a network of 500 hosts without having significant wastage.
Even though IPv4 has a theoretical address space of 4 billion host addresses,
the wastage will eventually result in exhaustion of the IPv4 address space.
The exhaustion has been effectively been delayed via two means:
-
Encouraging the use of private address space (see
RFC1918) and
Name Address Translation (NAT) (see
RFC1631).
-
Classless Inter-Domain Routing (CIDR) - the allocation of IP addresses
based on the use of a Variable Length Subnet Mask (VLSM).
However, even with these changes we are likely to exhaust the IPv4 address
space sometime during 2012 - see Geoff Huston's IPv4 Address Report
for interesting reading. The only long term solution is arguably the
transition to IPv6 which uses 128-bit addresses. More on this later in the
semester!
Variable Length Subnet Mask (VLSM)
In the VLSM scheme, the length or number of bits in the host part of the
address is selected so that it is just large enough for the the required
number of hosts in the network. Each subnetwork can have
2n - 2 hosts
where n is the number of bits in the host part of the address.
This produces networks of 2, 6, 14, 30, 62, 126, 254, 510, 1022, etc hosts.
In general terms: 2(32 - nn) - 2
More on CIDR
CIDR allows the allocation of IP address space to be performed in blocks that
are based on the actual or projected need of an organisation, thus reducing
wastage. Additionally, CIDR encompasses the use of aggregation to convert
multiple contiguous subnets into a single supernet - more
on this soon!
CIDR addresses are still 32 bits long and are allocated from the remaining
Class A, Class B and Class C address space that is yet to be allocated.
A CIDR address is denoted using the form A.B.C.D/nn where
A.B.C.D is the traditional dotted IP address notation and /nn specifies
the length of the subnet mask (ie. how many bits are allocated to the
network part of the address.
This form of addressing is universally used by the Border Gateway Protocol
version 4 (BGP4) when routing between Autonomous Systems. Each address used by
BGP4 is accompanied by its "netmask" (to confuse matters this /nn number can
often become entangled with traditional subnet addressing).
Traditional Class A, B, C addressing fits neatly into CIDR/VLSM. All that is
needed is to use the right /nn ie. /8 for Class A, /16 for Class B and /24 for
Class C.
Obtaining an Address Allocation
- From an ISP
-
ISPs are allocated a block of addresses from the appropriate Regional
Internet Registry (RIR) such as ARIN, RIPE NCC or APNIC. As an aside,
the RIRs are allocated IP address space by the Internet Assigned
Numbers Authority or IANA). The ISP can then subdivide this block for
allocation/use by their clients.
The advantage of this approach is that the ISP can advertise the
address space for all of their customers with a single route
(to the ISP itself). Once the packets arrive at the ISP they can be
routed to the customer's network.
Disadvantages are:
- A customer must re-number their network when changing ISP.
- A multi homed customer will have two ISPs advertising the same
block of addresses (one as part of their allocated range).
- Direct from a Regional Internet Registry (RIR)
-
The addresses are now portable, but... each ISP must advertise them.
And it will generally cost a lot more (around $4,800 to $10,500)!
Subnetting CIDR
One of the main ideas with CIDR is that an organisation can subnet their
IP address allocation into many smaller networks (and we can then subnet
or subnets!). The process used is really no different to subnetting a
Class A, B or C network.
Modern classless routing protocols (RIP v2, EIGRP, OSPF, BGP4 but not
RIP v1 or IGRP) carry both the network address and the network mask,
so routers are able to determine the network and host parts of an address.
Together with "longest prefix match", a router is able to determine which
subnet a host is located in:
External to the Autonomous System (AS) the network is still known as
A.B.C.D/nn, although we could choose to advertise a smaller allocation.
Internally, the subnets are known as A.B.C.D/xx.
For example, the well known network:
149.144.0.0/16
Could be subnetted using CIDR as:
149.144.0.0/24
149.144.1.0/24
149.144.2.0/24
... ... ... ...
149.144.254.0/24
149.144.255.0/24
Some alternatives are:
149.144. 0.0/17
149.144.128.0/17
|
149.144. 0.0/18
149.144. 64.0/18
149.144.128.0/18
149.144.192.0/18
|
149.144. 0.0/19
149.144. 32.0/19
149.144. 64.0/19
149.144. 96.0/19
149.144.128.0/19
149.144.160.0/19
149.144.192.0/19
149.144.224.0/19
|
Note: Unlike classful addressing, CIDR allows the use of subnet 0.
Summarising CIDR Addresses
This is really the reverse of subnetting - we are looking to aggregate
multiple subnets into a supernet which encompasses the
smaller allocations. This allows us to reduce the number of routes that
we have to advertise.
A number of subnets (or even networks) can be represented by a single summary,
providing they fill a "nice round binary group"™.
In other words, the leading part of their network addresses are all the same
and the trailing part of the network addresses form the continuous sequence,
expressed in binary:
0000 This example summarises a group of 16
0001 subnets (or networks). If the summary
0010 included only 8 subnets (or networks)
.... then only 3 bits would be required.
1110 Or 2 bits to summarise 4 ...
1111 Or 1 bit to summarise 2 ...
For example:
179.181.128.0/24
179.181.129.0/24
179.181.130.0/24
179.181.131.0/24
Can be summarised (exactly) as:
179.181.128.0/22 This is the longest matching summary.
It is also exact.
The same networks are also included in:
179.0.0.0/8
179.181.0.0/16
179.181.128.0/16...21
Plus a lot more
But these also include a lot of other subnets that were not in the original
networks.
Routing "Black Holes"
Routers which advertised any of these latter summaries would attract traffic
for networks which were not in the original networks. For example the
179.0.0.0/8 advertisement includes:
179.001.xx.xx/24
179.002.xx.xx/24
179.003.xx.xx/24
179.004.xx.xx/24
which were not in the original groups summarised. This is widely recognised
as a "bad thing"™. Any traffic for these "extra" networks would be
dropped by the router as it would not be able to forward the packets.
Copyright © 2007 Phil Rice
Copyright © 2009 Joel Sing
