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:

Network Classes
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":

Subnetting

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:

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.

VLSM

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:
 
  1. A customer must re-number their network when changing ISP.
  2. 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.

References

The IPv4 Address Report

RFC1918 - Address Allocation for Private Internets

RFC1631 - The IP Network Address Translator (NAT)

Asia Pacific Network Information Centre (APNIC)