Monthly Archives: January 2012

Calculating IPv4 Summary Prefixes

Posted on by

6

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