Mar
17

Overview

In this short blog post we are going to present a simple procedure for IPv4 prefix summarization. The procedure is based on the one found in “Optimal Routing Design” book by Russ White, Don Slice and Alvaro Retana, but differs in some respects. The process is three step, and require the use of Windows calculator for ease of computation. No binary breakdowns are involved, just some basic arithmetic. For the sake of simplicity, we skip all proofs, as those are trivial. The same approach could be adopted for use with IPv6 prefixes, provided that decimal arithmetic is replaced with hexadecimal.

Scenario

We are going to use an example to demonstrate the method. Here is the task: find the optimal (longest prefix length) summary prefix for the following set of subnets:

192.168.100.0/22
192.168.101.0/24
192.168.99.0/24
192.168.102.0/24
192.168.105.0/24
192.168.98.0/23

This example is taken from the wikipedia article: http://en.wikipedia.org/wiki/Supernet that illustrates the use of binary breakdown for the purpose of address summarization.

Preparations

It does not matter if the subnets have different prefix lengths – you may simply ignore these, as the resulting summary will use its own prefix length. Sort the prefixes in ascending order, starting with lowest and to the highest 32-bit number. Find the octet where the prefixes differ (we would call it “changing octet” from here on). In our case this is the 3rd octet (98, 99 etc):

192.168.98.0/23
192.168.99.0/24
192.168.100.0/22
192.168.101.0/24
192.168.102.0/24
192.168.105.0/24

You only need to sort the prefixes to find the lowest and the highest changing octet values. The changing octet position also gives us the corresponding “positional prefix length”. If this octet is the first in the prefix, the positional prefix length is 8, if it’s the second then the positional prefix length is 16, next 24 for third and 32 for fourth position in the dotted-decimal form.

Step 1:

Take the highest and lowest changing octets and perform XOR operation on them. You may use Windows calculator or any other utility that allows for logical operations on decimal numbers: “98 XOR 105 = 11″. Next, take the lowest power of “2” that is strictly greater than the resulting number (even if the result is a power of two itself). In our case it is 16. Let’s call this number as “y”. After that, find the number z, so that “2^z=y” (here “^” means power, not XOR like in C), i.e. take Log2 of “y”: “z = Log2(y) = Log2(16) = 4″. You may use a short table of powers of 2 ranging from 2^0 to 2^8 – you don’t need more as you deal with just a single octet. It’s easy to memorize these numbers too. Notice that dealing with IPv6 would require the table of 16 elements (2^0 through 2^16).

Note The original method found in “Optimal Routing Design” uses subtraction operation instead of XOR at this step. It could be shown that subtraction does not work in all cases. For example, it does not reveal the correct highest mismatching bit position in the case of: 10.1.66.0 and 10.1.69.0 as “69-66=3″ (incorrectly approximated by 2^2) while “69 XOR 66 = 7″ (correctly approximated by 2^3). The reason being are “arithmetic underflows” that happen with subtraction.

Step 2:

Take the any changing octet value, e.g. the lowest one, and divide it by “y” then drop the remainder: “98/16 = 6.125″ rounded to 6 (“floor” function). Now multiply 6 by “y” again to yield 96 – this is the base octet of the summary address. The summary prefix now looks like: 192.168.96.0. Effectively, these two operations represent logical binary shift right and left to mask the changing bits. Yes, you may take ANY octect from the set of prefixes – the result will be the same.

Step 3:

The final step is finding the summary prefix length. Take the positional prefix length corresponding to the changing octet, as described previously. In our case it’s the third octet, and thus the positional prefix length is 24. Now subtract “z” from this number to get “x” – the summary prefix length: “x=24-z=24-4=20″. The summary prefix is: 192.168.y.0/x = 192.168.96.0/20

Step 4 (Optional):

Convert prefix length into network mask, if needed. To accomplish this, take 256 and subtract “y”: 256-16=240. This is the netmask component that corresponds to the summary base octet: 192.168.96.0 255.255.240.0

Example 1

Take the following subnets:

10.1.57.0/24
10.1.59.0/24
10.1.61.0/24

Changing octet – 3rd, positional prefix length = 24. Next step: “61 XOR 57 = 4″ thus “y = 8, z=3; 57/y = 57/8 = 7.125″ and the base octet is “7*8=56″. The prefix length is “24-3=21″. Summary prefix is: 10.1.56.0/21 or 10.1.56.0 255.255.248.0

Example 2

Take the following subnets:

192.168.97.0/23
192.168.100.0/22

Changing octet – 3rd, positional prefix length = 24. Next step: “100 XOR 97 = 5″, “y = 8, z = 3 97/8 = 12.125″, base = “12*8=96″. The prefix length = “24-3=21″. Summary Prefix: 192.168.96.0/21 or 192.168.96.0 255.255.248.0

Example 3

Take the following subnets:

172.16.14.0/24
172.16.17.0/24
172.16.25.0/24

Changing Octet – 3rd, positional prefix length = 24. Next Step: “25 XOR 14 = 23, y = 32, z = 5; 14/32 = 0.43″, base octet = 0. Summary length: “24-5=19″. Summary prefix: 172.16.0.0/19 or 172.16.0.0 255.255.224.0. Notice that this summary address could be too exhaustive in terms of overlapped address space. You may want to summarize just two prefixes: 172.16.17.0 and 172.16.25.0 and leak 172.16.14.0: summary of 172.16.17.0 and 172.16.25.0 = 172.16.16.0/20 and 172.16.14.0/24 is left un-summarized.

Conclusions

The procedure presented in this article could be useful when dealing with large-scale networks and configuring manual IPv4 prefix summarization. You may avoid complicated binary conversions and simply use the calculator to find the resulting prefix.

About Petr Lapukhov, 4xCCIE/CCDE:

Petr Lapukhov's career in IT begain in 1988 with a focus on computer programming, and progressed into networking with his first exposure to Novell NetWare in 1991. Initially involved with Kazan State University's campus network support and UNIX system administration, he went through the path of becoming a networking consultant, taking part in many network deployment projects. Petr currently has over 12 years of experience working in the Cisco networking field, and is the only person in the world to have obtained four CCIEs in under two years, passing each on his first attempt. Petr is an exceptional case in that he has been working with all of the technologies covered in his four CCIE tracks (R&S, Security, SP, and Voice) on a daily basis for many years. When not actively teaching classes, developing self-paced products, studying for the CCDE Practical & the CCIE Storage Lab Exam, and completing his PhD in Applied Mathematics.

Find all posts by Petr Lapukhov, 4xCCIE/CCDE | Visit Website


You can leave a response, or trackback from your own site.

26 Responses to “A Simple IPv4 Prefix Summarization Procedure”

 
  1. John Zhang says:

    Great shortcut. Thanks

  2. [...] Core Knowledge Is Priceless – Test Your’s Today: Q: What is the the optimal (longest prefix length) summary for the following set of subnets 192.168.100.0/22; 192.168.101.0/24; 192.168.99.0/24; 192.168.102.0/24; 192.168.105.0/24; 192.168.98.0/23? A: 192.168.96.0/20 More Info: http://blog.ine.com/2010/03/17/a-simple-ipv4-prefix-summarization-procedure/ [...]

  3. Dana says:

    I love the way this was explained. A nice resource for many. Great work Petr!

  4. [...] 192.168.105.0/24; 192.168.98.0/23? > A: 192.168.96.0/20 > More Info: > > http://blog.ine.com/2010/03/17/a-simple-ipv4-prefix-summarization-procedure/ > > On Mar 17, 2010, at 4:27 PM, Mark Anthony wrote: > > > Hello GS, > > > [...]

  5. [...] 192.168.98.0/23? > > A: 192.168.96.0/20 > > More Info: > > > > > http://blog.ine.com/2010/03/17/a-simple-ipv4-prefix-summarization-procedure/ > > > > On Mar 17, 2010, at 4:27 PM, Mark Anthony wrote: > > > > > Hello [...]

  6. Carlos Farinha says:

    Hi Petr,

    Thanks for your post, as usual really well explained and very useful.

    Please just correct the typo on example 3, just to avoid confusing anyone reading the post, it should be 14/32(y) not 14/23.

    Thanks once again!
    Carlos

  7. Deepak Arora says:

    Hey Petr can you write some good detailed article on Prefix Lists from binary prospective. I know most people feel that it’s very easy though. But there are many out there like me who still want to
    understand it from binary point of view specially when someone asks something like : Construct a prefix list that denies any prefix for which the most-significant four bits are “0110″, and permits everything else.

    Thanks!
    Deepak Arora

  8. [...] 192.168.98.0/23? > > A: 192.168.96.0/20 > > More Info: > > > > http://blog.ine.com/2010/03/17/a-simple-ipv4-prefix-summarization-procedure/ > > > > On Mar 17, 2010, at 4:27 PM, Mark Anthony wrote: > > > > > Hello [...]

  9. Bilal Hansrod says:

    Hi Petr,

    How did you derive y? I still can’t get my head around:)

    Regards,

    Bilal

  10. Bilal,

    A Xor B = C
    2^D = E

    E is a power of 2 which is greater than C, where D is the power you are using.

    In his case,
    A = 98
    B = 105
    Hence C = 11 (98 Xor 105)
    So…
    2^D > 11 and that is E
    2^4 = 16 = E (In the Example it is Y)

  11. shivlu jain says:

    Thanks by doing I get rid from the binary and it saves lot of time.

  12. Bilal Hansrod says:

    Thanks Nish-

    It looks like E Or Y is always greater than C value. so if Xor value is 32 than it would be 2^6 and E or Y becomes 64.

    Am I right?

  13. Bilal, that is correct.

    The Value of Y needs to be…

    “lowest power of “2” that is strictly greater than the resulting number”

    2^5 = 32 is the same value so you need to go one one more power which is 2^6 = 64, which is correct.

  14. Bilal Hansrod says:

    Thanks Nish

  15. Dev13 says:

    Guys,

    In case of

    222.222.221.1/24
    222.222.222.1/24
    222.222.223.1/24

    What will be the summary address I can use?

  16. Dev13 says:

    so Petr in my case y=4 as 221XOR223=2 so I have to take Y strictly greater than the XOR result right? so it will be 4. Then I will do Log2(4) which will give me result of 2 and that is 24-2=22 and that will be my mask. and for 3rd octet 221/4=55.25 and I will take 55 by leaving reminder and again 55×4=220, so that way 222.222.220.0/22 is the result right?

    So for Y it has to be “greater than”, it is “not equal” to the XOR result….

    • @Devin13:

      Quote from the blog post:

      “Take the highest and lowest changing octets and perform XOR operation on them. You may use Windows calculator or any other utility that allows for logical operations on decimal numbers: “98 XOR 105 = 11″. Next, take the lowest power of “2” that is strictly greater than the resulting number (even if the result is a power of two itself)”

  17. Jaesonv says:

    Dev13

    “In case of

    222.222.221.1/24
    222.222.222.1/24
    222.222.223.1/24

    What will be the summary address I can use?”

    Hi Dev13:

    Your summary addresses are as follows:
    222.222.221.0/24
    222.222.222.0/23

    It cannot be 222.222.221.0/22 as that also included 222.222.221.0/24. You only originally wanted to block 222.222.221.0/24, 222.222.222.0/24, and 222.222.223.0/24.

    Proof:

    An Access-list that will block off 222.222.220.0/22 will make users in the 222.222.220.0/24 CRY because they cannot access resources

    OR

    It will make those people extremely happy as they were expecting to be blocked but that wasn’t the case.

  18. Jaesonv says:

    First off, I’m not agreeing with the example Wikipedia gave.

    Address First Octet Second Octet Third Octet Fourth Octet
    192.168.98.0 11000000 10101000 01100010 00000000
    192.168.99.0 11000000 10101000 01100011 00000000
    192.168.100.0 11000000 10101000 01100100 00000000
    192.168.101.0 11000000 10101000 01100101 00000000
    192.168.102.0 11000000 10101000 01100110 00000000
    192.168.105.0 11000000 10101000 01101001 00000000

    The above, as Wikipedia mentions says the answer is a 192.168.96.0/20. It in itself is wrong because a /20 encompasses 16 /24 networks. We’re only asked to summarize for the above 6 /24 networks in the example to ONE block, if possible.

    1. What if the above subnets were to be BLOCKED via an ACL? The subnet 192.168.97.0/24 is included in the 92.168.96.0/20 Supernet. To me that is an invalid summarization as it included a network that shouldn’t be part of the blocked networks.

    If I was to summarize the above, assuming each of them are /24’s as suggested by some of the contiguous subnets 192.168.98.0 through 192.168.102.0, the summary address should be

    192.168.98.0/23
    192.168.100.0/23
    192.168.102.0/24
    192.168.105.0/24

    If converted into an ACL, the above summary addresses will only permit networks within 192.168.98.0 through 192.168.102.255 and 192.168.105.0-192.168.105.255. Networks 192.168.96.0/24, 192.168.97.0/24, and 192.168.103.0/24 up to 192.168.111.0/24 are not specified to be included in the summary route.

    To contrast, see another example below for summarization and only the networks specified.

    193.168.3.0/24
    193.168.4.0/26
    193.168.4.64/26
    193.168.4.128/26
    193.168.4.192/26
    193.168.5.0/25
    193.168.5.128/25

    A summary address of 193.168.3.0/24 and 193.168.4.0/23 (WCM 193.168.3.0 0.0.0.255 and 193.168.4.0 0.0.1.255) will suffice.

  19. [...] A Simple IPv4 Prefix Summarization Procedure [...]

  20. [...] so that they don’t overlap any unnecessary address space? Look at the example presented in A Simple IPv4 Prefix Summarization Procedure. The example calls for summarizing the following [...]

  21. [...] version   4 (IPv4) addressing, subnetting, and variable-length subnet masking (VLSM) [2] [3] (a) Calculating the Optimum Summary Address (b) Binary Math Manipulation (1) Matching multiple networks with a single access list line (2) [...]

  22. Praveen says:

    hi petr

    just awesome trick would you just tell me the summary address for below network

    192.168.60.0/24
    192.168.70.0/24
    192.168.80.0/24
    192.168.90.0/24
    192.168.100.0/24
    192.168.101.0/24
    192.168.105.0/24

    as per your trick i did it as per me it would be 192.168.0.0 255.255.128.0
    is it right .pls pls reply me and how to avoid overlapping by your method

  23. Danish Khan says:

    Excellent formula …

  24. [...] version   4 (IPv4) addressing, subnetting, and variable-length subnet masking (VLSM) [2] [3] (a) Calculating the Optimum Summary Address (b) Binary Math Manipulation (1) Matching multiple networks with a single access list line (2) [...]

 

Leave a Reply

Categories

CCIE Bloggers