Calculating IPv4 Summary Prefixes

Given a list of IPv4 prefixes of the same length, how do you find the summary address (or addresses) for them? This post describes a method and uses some worked examples to illustrate. The post draws deeply from the CCIE Routing and Switching Exam Certification Guide by Wendel Odom, with lots additions of mine for clarity as well as some procedures that are not described in the text. I assume that you already understand the standard terminology associated with IPv4 addressing in general.

Definitions

• Block (B): Different subnet numbers are multiples of the block (B).
• The block for prefix length (P) is given by: $B(P) = 2^{8-P\%8}$.
• The modulo (MOD or %) operation simply finds the remainder of dividing one number by another. We are dividing by 8 here because each octet of an IPv4 address is 8 bits in length.
• Inclusive summary address: A summary that includes prefixes outside the range of prefixes you are summarizing.
• Exclusive summary address: A summary address (or addresses in some cases) that only includes prefixes within the range you are summarizing.
• Interesting Octet: the octet within the IPv4 address in which the prefix length falls. To find this, simply divide the prefix length by 8 and round to the next whole integer.

General procedure

The general procedure to find the exclusive summary address(es) is as follows:

1. Find the inclusive summary route and use this as the first candidate exclusive address.
2. Determine the range of addresses of the candidate exclusive address. If it totally encompasses all the component prefixes, then this candidate is the exclusive summary address. If not, split the component candidate address into two with a new prefix length P’ = P + 1
3. Repeat step #2 for each half of the candidate summary address. As you do this several times, you will eliminate prefixes from the bottom and top of the range till you are left with just the exact prefixes that encompass all the candidate prefixes.

Calculating the inclusive summary route

You should know (from your routing table) or from the problem set in an exam the following information

• A list of prefixes to summarize i.e. the component prefixes.
• The prefix length of the prefixes (P). This is the same for all component prefixes.

You use the given prefixes to find the inclusive summary route as follows:

1. Let the number of component prefixes be ‘s’
2. The number of bits required to give ‘s’ prefixes is given by ‘y’ where: $2^{y}$ ≧ s (take the next whole integer)
3. Calculate a new prefix length P’ = P – y
4. Calculate S0 – the subnet number when you take the lowest numeric subnet (e.g 192.168.20.0 is less than 192.168.25.0) in the list as an IP address with prefix length P’.
5. Calculate S1 – the subnet number when you take the highest numeric subnet in the list as an IP address with prefix length P’
6. If S0=S1 then this is the best summary route.
7. If S0≠S1, then repeat steps #4 and #5 with a new (shorter) prefix length P’= P’ – 1

Calculating the exclusive summary route

1. Find the inclusive summary prefix and use it as a candidate exclusive summary prefix
2. Determine the range of the candidate summary, if all candidates prefixes fall within the range, then this is the exclusive summary prefix and you are done.
3. If the range of the candidate prefixes includes prefixes outside the component prefixes, split the candidate into two parts with length P’ = P +1 and repeat step #2 with each half.

How to split a prefix into two parts

1. Find the new prefix length: P’ = P + 1
2. Calculate the block that corresponds to this new prefix length B(P’)
3. First part = candidate prefix
4. Second part = candidate prefix + B(P’) on the interesting subnet

Worked Example #1 : Inclusive summary route

Find the inclusive summary prefix for: 172.31.20.0/24, 172.31.21.0/24, 172.31.22.0/24, 172.31.23.0/24

• Number of prefixes s = 4
• Prefix length of components P = 24
• Bits required y: 2^y >= s => 2^y >=4 thus y = 2
• New prefix length P’ = P – y = 24 – 2 = 22

Taking smallest component prefix as an address with new prefix length, we have 172.31.20.0/22

• Block B(22) = 2^(8-22%8) = 2^2 = 4
• Thus subnet number are multiples of 4 i.e. 4 , 8 , 12, 16, 20 , 24, etc
• Interesting octet is 3rd octet (22/8 = 2R6 = 3)
• This address belongs to subnet 172.31.20.0/22 = S0

Taking the highest component prefix as an address with new length, we have 172.31.23.0/22

• Block B(22) = 2^(8-23%8) = 2^2 = 4
• Thus subnet number are multiples of 4 i.e. 4 , 8 , 12, 16, 20 , 24, etc
• Interesting octet is 3rd octet (22/8 = 2R6 = 3)
• This address belongs to subnet 172.31.20.0/22 = S1

S0 = S1 thus the inclusive summary prefix is 172.31.20.0/22

Worked Example #2 : exclusive summary route

Find the exclusive summary of 172.31.20.0/24, 172.31.21.0/24, 172.31.22.0/24, 172.31.23.0/24 ,172.31.24.0/24

We start of by finding the inclusive summary prefix first and using it as a candidate exclusive summary prefix.

• Number of prefixes s = 5
• Prefix length of components P = 24
• Bits required y: 2^y >= s => 2^y >=5 thus y = 3
• New prefix length P’ = P – y = 24 – 3 = 21
• Block B(21) = 2^(8-21%8) = 2^3 = 8
• Thus subnet number are multiples of 8 i.e. 8 , 16 , 24, 32 etc
• Interesting octet is 3rd octet (21/8 = 2R5 = 3)

Taking smallest component prefix as an address with new prefix length, we have 172.31.20.0/21 which belongs to subnet 172.31.16.0/21 = S0

Taking the highest component prefix as an address with new length, we have 172.31.24.0/21, which belongs to subnet 172.31.24.0/21 = S1

S0 ≠ S1 we repeat with prefix length decremented by 1

• New prefix length P’ = P’ – 1 = 21 – 1 = 20
• Block B(20) = 2^(8-20%8) = 2^4 = 16
• Thus subnet number are multiples of 16 , 32 , 48 etc
• Interesting octet is 3rd octet (20/8 = 2R4 = 3)

Taking smallest component prefix as an address with new prefix length, we have 172.31.20.0/20 which belongs to subnet 172.31.16.0/20 = S0

Taking the highest component prefix as an address with new length, we have 172.31.24.0/20 which belongs to subnet 172.31.16.0/20 = S1

S0 = S1 = 172.31.16.0/20 is the inclusive summary prefix

Now that we have the inclusive summary prefix, we can proceed to find the exclusive prefix using this as our first candidate.

First we establish the range of 172.31.16.0/20

• We know block is B(20) = 16 and the third octet is the interesting one
• The next subnet higher than 172.31.16.0/20 is 172.31.32.0/20
• Therefore range of 172.31.16.0/20 is 172.31.16.1 – 172.31.31.255 (this being the last address before 172.31.32.0/20)
• This range includes more prefixes than are in the component list (e.g .16.0/24 and .28.0/24)

We split 172.31.16.0/20 into two parts

• New prefix length P’= P’ + 1 = 20 + 1 = 21
• B(21) = 8
• Thus 172.31.16.0/20 = 172.31.16.0/21 & 172.31.24.0/21
 Split #1 172.31.16.0/21 172.31.24.0/21 Range 172.31.[16.1 – 23.255] 172.31.[24.1 – 31.255] Comments Includes .16.0/24 so we’ll need to split this again Only 24.0/24 is within range Thus 172.31.24.0/24 is one of the exclusive summary prefixes

Note: We use the block (B) to determine the component subnets and thus know what prefixes are included that shouldn’t be.

We split 172.31.16.0/21 into two parts

• New prefix length P’= P’ + 1 = 21 + 1 = 22
• B(22) = 4
• Thus 172.31.16.0/21 = 172.31.16.0/22 & 172.31.20.0/22
 Split #1 172.31.16.0/22 72.31.20.0/22 Range 172.31.[16.1 – 19.255] 172.31.[20.1 – 23.255] Comments Totally out of range, so we discard this Includes the remaining component prefixes apart from .24.0/24

Therefore, the exclusive summary prefixes for 172.31.[20-24].0/24 are 172.31.20.0/22 AND 172.31.24.0/24

Worked Example #3 : Exclusive summary route

Find the exclusive summary prefix for 10.22.12.0/23, 10.22.14.0/23, 10.22.16.0/23 10.22.18.0/23

We start of by finding the inclusive summary prefix first and using it as a candidate exclusive summary prefix.

• Number of prefixes s = 4
• Prefix length of components P = 23
• Bits required y: 2^y >= s => 2^y >=4 thus y = 2
• New prefix length P’ = P – y = 23 – 2 = 21
• Block B(21) = 2^(8-21%8) = 2^3 = 8
• Thus subnet number are multiples of 8 i.e. 8 , 16 , 24, 32 etc
• Interesting octet is 3rd octet (21/8 = 2R5 = 3)

Taking smallest component prefix as an address with new prefix length, we have 10.22.12.0/21 which belongs  to subnet 10.22.8.0/21 = S0

Taking the highest component prefix as an address with new length, we have 10.22.18.0/21 which belongs to subnet 10.22.16.0/21 = S1

S0 ≠ S1 we repeat with prefix length decremented by 1

• New prefix length P’ = P’ – 1 = 21 – 1 = 20
• Block B(20) = 2^(8-20%8) = 2^4 = 16
• Thus subnet number are multiples of 16 , 32 , 48 etc
• Interesting octet is 3rd octet (20/8 = 2R4 = 3)

Taking smallest component prefix as an address with new prefix length, we have 10.22.12.0/20 which belongs to subnet 10.22.0.0.0/20 = S0

Taking the highest component prefix as an address with new length, we have 10.22.18.0/20 which belongs to subnet 10.22.16.0.0/20 = S1

Still, S0 ≠ S1 we repeat with prefix length decremented by 1

• New prefix length P’ = P’ – 1 = 20 – 1 = 19
• Block B(19) = 2^(8-19%8) = 2^4 = 32
• Thus subnet number are multiples of 32 , 64, etc
• Interesting octet is 3rd octet (19/8 = 2R4 = 3)

Taking smallest component prefix as an address with new prefix length, we have 10.22.12.0/19 which belongs to subnet 10.22.0.0.0/19 = S0

Taking the highest component prefix as an address with new length, we have 10.22.18.0/19 which belongs to subnet 10.22.0.0.0/20 = S1

S0 = S1 = 10.22.0.0/19 is the inclusive summary prefix

Now that we have the inclusive summary prefix, we can proceed to find the exclusive prefix using this as our first candidate.

First we establish the range of 10.22.0.0/19

• We know block is B(19) = 32 and the third octet is the interesting one
• The next subnet higher than 10.22.0.0/19 is 10.22.32.0/19
• Therefore range of 10.22.0.0/19 is 10.22.0.1 – 10.22.31.255 (this being the last address before 10.22.32.0/19)
• This range obviously includes more prefixes than are in the component list so we split it

We split 10.22.0.0/19 into two parts

• New prefix length P’ = P’ + 1 = 19 + 1 = 20
• B(20) = 16
• Thus 10.22.0.0/19 —> 10.22.0.0/20 & 10.22.16.0/20
 Split #1 10.22.0.0/20 10.22.16.0/20 Range 10.22.[0.1 – 15.255] 10.22.[16.1 – 31.255] Comments Includes ranges below 10.22.12.0/24 Includes ranges above 10.22.18.0/24 We’ll need to split this to trim the range from above

We split 10.22.0.0/20 into two parts

• New prefix length P’= P’ + 1 = 20 + 1 = 21
• B(21) = 8
• Thus 10.22.0.0/20 –> 10.22.0.0/21 & 10.22.8.0/21
 Split #2 10.22.0.0/21 10.22.8.0/21 Range 10.22.[0.1 – 7.255] 10.22.[8.1 – 15.255] Comments Totally out of range Includes the .12.0, 14.0 and 16.0 prefixes Still includes the prefixes below .12.0 and so needs to be split this prefix to trim it from the bottom

We split 10.22.8.0/21 into two parts

• New prefix length P’= P’ + 1 = 21 + 1 = 22
• B(22) = 4
• Thus 10.22.8.0/21 –> 10.22.8.0/22 & 10.22.12.0/22
 Split #3 10.22.8.0/22 10.22.12.0/22 Range 10.22.[8.1 – 11.255] 10.22.[12.1 – 15.255] Comments Totally out of range Contains the .12, .14 prefixes and nothing else

We split 10.22.16.0/20 from split #1 into two parts

• New prefix length P’= P’ + 1 = 20 + 1 = 21
• B(21) = 8
• Thus 10.22.16.0/20 –> 10.22.16.0/21 & 10.22.24.0/21
 Split #4 10.22.16.0/21 10.22.24.0/21 Range 10.22.[16.1 – 23.255] 10.22.[24.1 – 31.255] Comments Contains .16.0 and .18.0 but also .20 which we don’t want Split this again Totally out of range – discard

We split 10.22.16.0/21 from split #4 into two parts

• New prefix length P’= P’ + 1 = 21 + 1 = 22
• B(22) = 4
• Thus 10.22.16.0/21 –> 10.22.16.0/22 & 10.22.20.0/22
 Split #5 10.22.16.0/22 10.22.20.0/22 Range 10.22.[16.1 – 19.255] 10.22.[20.1 – 23.255] Comments Contains only .16.0 and .18.0 Totally out of range – discard

Therefore, the exclusive summary prefixes for 10.22.[12, 14 , 16, 18].0 /23 are 10.22.12.0/22 AND 10.22.16.0/22

Conclusion

1. Be aware that when you summarize to certain prefix lengths, some operators might not accept them. Inefficient summary routes lead to bigger BGP tables.
2. Most ISPs and Regional Internet Registries (RIRs) will allocate you address space along boundaries that can easily be summarized neatly
3. The Block (B) will always increase in the progression: 2 , 4, 8, 16 , 32 , 64 , 128

Ubuntu Idyll Cisco Study Environment

I have written a few posts in which I mentioned the amazing GNS3/Dynamips/Dynagen set of tools that enable you emulate a Cisco network …. also a great too used to prepare for the Cisco CCIE lab exam [Professor of Internetworking]

Here are a couple of things I have used that make creating and using labs a nirvana experience in Ubuntu … [constant flow for those who understand Emotional Intelligence]

1. Because I hate having multiple console windows open, one for each router which is the default behaviour of GNS3, I wrote the script [tamonet.sh] in the previous post that essentially takes as an arguement your topology (.net) file and then opens each router console in a separate tab in gnome-terminal.
2. I modified my gnome-terminal profile so that my background is translucent. That way, I can have a document (e.g a workbook) I refer to in the background and read instructions or make references without having to switch windows.
3. Initially, to launch my lab with my tamonet.sh script, I would open up either a terminal or the RUN application box [Alt-F2] and issue the command …. that is until I discovered awn-terminal. Boy! …. first of all, AWN is a cool dock application for Ubuntu and one of its applets is a nifty cool terminal that you just click and it pops up a next-gen-like translucent terminal. You just type in your command and as soon as u move focus from it, it automatically closes … no clutter on your desktop!!
4. And finally … when I am doing such work, I play music. Mozart is ideal for me but I generally prefer any kind of music without vocals. It is the vocals I find distracting. So for me, to complete the ensemble, it is Mozart, Beethoven, Tchaikovsky or soundtrack music [Prison Break, Stargate etc]

Given what I mostly do these days [putting in my 10000 hours to master my craft as a network engineer] and my passion for Ubuntu … I enjoy every single moment I spend building and executing scenarios and everyday, I say thank you to the guys who selflessly make all this possible …and it reminds me to keep sharing what little I know. Happy Valentines day guys and babes … do spend vals with someone real … far away from your laptop ok?

Open GNS3 Router Consoles in Multiple Tabs in a Single Window [GNOME]

As a follow up to my previous post of the above topic, I finally put together a script. I have two scripts, one specifically written for the Internetworkexpert Dynamips topology. The second one can will log into any topology – it takes the name of the .net file as an argument for example:

\$./tamonet.sh BGPlab.net

Just copy this code, put them in a file with the .sh extension and  make then run them from a command line AFTER you have started your routers in GNS3.

```
#!/bin/bash

# The purpose of this scrip is to launch all running Dynamips router consoles in such a way that all consoles exist
# as tabs in a single terminal windows, rather than the
#default behavior to open multiple windows that just clutters the desktop.
#Script written by Mukom Akong TAMON [mukom to tamon at gmail dot com] .....
#Use and distribute freely .... just give me credit for creating it ok? ... ;-)
#Save this with an sh extension, make it executable and then you can run either from
#inside an existing terminal or you press ALT+F2 and then run it. You must pass it the name of the .net file of your current lab
#e.g ./tamonet.sh BGP-Lab01.net
#It is best if you copy the script so it is in the same directory as the directory in which the .net file is.
#Obviously, this script only works for Linux distributions that are using GNOME eg Ubuntu.

PORTS=/Users/mukom/tmp/ports
NAMES=/Users/mukom/tmp/devicenames
TELNETCMDS=/Users/mukom/tmp/telnetcmds
TELNETTABNAME1=/Users/mukom/tmp/telnettabname1	#Initial set of command arguments for gnome terminal
TELNETTABNAME2=/Users/mukom/tmp/telnettabname2	#Strip away the tab from the commands -- just in case
TELNETTABNAME=/Users/mukom/tmp/telnettabname		#the commands sorted so we have things sequentially
LASTCMD=/Users/mukom/tmp/lastcmd.sh

#First delete the files if they exit
rm -f  \$PORTS
rm -f  \$NAMES
rm -f \$TELNETTABNAME
rm -f \$TELNETCMDS
rm -f \$TELNETTABNAME1
rm -f \$TELNETTABNAME2
rm -f \$LASTCMD

#Xtract the ports from .net file and put them into ports file in /tmp
grep -E console  \$1 | sed s/console\ =\ // | tr -d [] | tr -s '[:blank:]' >> \$PORTS

#Create corresponding file that containts the names
#grep -E ROUTER  \$1 | sed s/ROUTER\ // | tr -d [] | tr -s '[:blank:]' >> \$NAMES
grep -E '\[\[ROUTER'  \$1 | sed s/ROUTER\ // | tr -d [] | tr -s '[:blank:]' >> \$NAMES

#This block constructs the telnet commands for each router and writes them to \$TELNETTABNAME
#inst=0
for i in \$( cat \$PORTS ); do
#	let inst=inst+1
#echo >> \$TELNETCMDS "telnet localhost \$i -t"
#	echo >> \$TELNETCMDS "\"telnet localhost \$i\" -t"
echo >> \$TELNETCMDS "\"telnet localhost" "\$i\"" ' -t'

done

#Combine the telnet command with the device name on same line
paste \$TELNETCMDS \$NAMES>>\$TELNETTABNAME1

#replace all tabs with a single space.
expand -t 1 \$TELNETTABNAME1>>\$TELNETTABNAME2
#cat \$TELNETTABNAME #| tr '\t' '" -t "'

#Now sort the file
sort \$TELNETTABNAME2>>\$TELNETTABNAME

#how many lines [routers] in the file?
routers=`wc -l \$TELNETTABNAME`	#count lines in the file and set result as variable routers.
routers=\${routers%\$TELNETTABNAME}  #Make the routers variable an integer?
echo "There are \$routers Routers in this topology"
let "routers = \$routers+1"
#declare -i routers    #This seems not to serve any useful purpose that I know of

#This block reads in the commands from a file and assign each line to a dimensioned variable R[x]
{
counter=0
while [ "\$counter" -lt "\$routers" ]
do
let "counter=\$counter+1"
done
}  < \$TELNETTABNAME

#This block just prints out the contents of the dimension - I want to be sure I read the right things into the variables
counter=0
while [ "\$counter" -lt "\$routers" ]
do
echo \${R[\$counter]}
let "counter=\$counter+1"
done

#Build the gnome-terminal command and options from the contents of the R[x] dimension
counter=0
let "routers=\$routers-2"  #One main window and then the -2 so we cover just the right number of tabbed auxilliary windows
command="gnome-terminal --window --maximize -e \${R[\$counter]}"
while [ "\$counter" -lt "\$routers" ]
do
let "counter=\$counter+1"
command="\$command --tab -e \${R[\$counter]}"
#echo \$command
done
echo >>\$LASTCMD \$command
chmod 777 \$LASTCMD
#I can delete these files now, since I no longer need them --- just house cleaning
rm -f  \$PORTS
rm -f  \$NAMES
rm -f \$TELNETTABNAME
rm -f \$TELNETCMDS
rm -f \$TELNETTABNAME1
rm -f \$TELNETTABNAME2
\$LASTCMD

```

I appreciate any modifications …. and this works for me … so I don’t have to get KDEbase libararies just for konsole4KDE. I hope u enjoy it.

Making GNS3 Routers Open in Tabs in Ubuntu

If you use GNS3 network emulator with a significant number or routers, each usually opens up in its own terminal window which just makes your workspace a mess.

While I know I can install konsole-for-KDE4 in Ubuntu to sort out the clutter, I don´t like to have to download more than 30MB extra software [KDE base libraries and other dependencies] so I opt to create this scrip which I can easily edit.

Just download the script, make it executable and after running the your lab from GNS3, rather than use the toolbar button to log into to all consoles, instead press ALT+F2 and type in the path to the script [do remember to make it executable] and voila!!!

On Vista, I use Teraterm for my console and so the above problem does not exist. If you use the default Vista command prompt you will run into the same problem. I read a nice GNS3 tutorial that suggested a free Windows utililty called Wintabber to tame those multiple windows.

If your Linux distribution uses KDE, install konsole-for-KDE4 and use it as your terminal program in GNS3 to get the same results.

I am working on some scripts to automate the process for Ubuntu and gnome-terminal — I don’t want to install all the KDE base packages just to get konsole-for-KDE … will post the scripts [bash] when I am done.

Saving Router Configurations Across GNS3 Sessions

For those who use GNS3 to emulate Cisco networks, sooner you get to a point where you would love to save the configuration and pick off from where you left. Uptill recently, I used the crude method of exporting my configuration files and then manually setting them as the startup config for each router. I however found a better way of recent … just save your lab as a GNS3 Project. Here is the procedure:
1. Lay out your lab: U know, place devices, connect them, configure switches and even default router configs (if you have a default config you typically use eg aliases, idlepcs and logging synchronous)
2. Run your lab (click Start/Resume all IOS)
3. Telnet into each of the routers and configure it to your heart´s desire. Make sure you do a copy run start or a write terminal after you finish configuring each router.
4. With your lab still running, switch back to the GNS3 window and click File->New Project. Type in a name for the project and be sure to check the ¨Export router configuration files¨ option.

5.
Click Ok and GNS3 will ask whether you want to apply the project settings to which you say yes.
6. GNS3 will extract the config from your routers and save them for you and automatically set them as startup config for the next time.
If you look in the directory where you saved the project, you will find that GNS3 creates the following:

• A project file eg lab.net
• A directory to store config files with the same name as the .net file of your project eg lab01_configs. In it you will find files with the name of your routers and the .cfg extension eg (R1.cfg, R2.cfg etc)
• If you selected the option in the New Project dialog box, a working directory folder is also created eg lab01_working.

Next time, you can just open your lab, launch right in and start having fun.

Simulating a Host in Dynamips/GNS3

For those who don’t know what Dynamips is …. aaaaaaaahhh … it is a very cool piece of software that allows us to emulate any Cisco router and even the PIX. It is a very useful tool for experimenting with Cisco-based networks and one of the cheapest ways to prepare for the CCIE lab. I use it for the later purpose and also to get some hands-on practice with various networking technologies. GNS3 is a very cute graphical front-end to Dynamips which is more suited for adhoc experimentation due to the simply way you can create any topology by dropping devices and connecting them. I was watching a video class on IPv6 when something the instructor said hit me “… without the ipv6 unicast-routing command, this router will not function as a router”! …. immediately I fired up my copy of GNS3 and to simulate a host, I added a router and proceded thus to make it a ‘host’ 1. Disabled routing [no ip routing in global config mode] 2. Configured and IP address and subnet mask on an interface and enabled the interface. 3. Gave the router a default gateway by typing ip default network a.b.c.d where a.b.c.d is the IP address of the router to which this ‘host’ is connected. An viola! I had a host I could ping from. This enables me to simulate a LAN connected to the router … definitely a more elegant way that using loopback addresses which is what I was using until now. So experiment away and drop me any suggestions.