Systems and Network Management CIDR, Route Summarisation and Routing — Solutions 1 Examples 1. Aggregate the following set of 4 24-bit network addresses to the highest degree possible. 172.47.30.0/24 172.47.31.0/24 172.47.32.0/24 172.47.33.0/24 Here is how to do it: List each address in binary format and determine the common prefix for all of the addresses: ← . . . . . . first prefix . . . . . . → 172.47.30.0/24 10101100.00101111.0001111 172.47.31.0/24 10101100.00101111.0001111 172.47.32.0/24 10101100.00101111.0010000 172.47.33.0/24 10101100.00101111.0010000 ← . . . . second prefix . . . . → Note that this set of 4 24-bit blocks cannot be summarised as a single 22-bit block. 172.47.30.0/23 10101100.00101111.00011110.00000000 172.47.32.0/23 10101100.00101111.00100000.00000000 So the two 23-bit blocks are: 172.47.30.0/23 172.47.32.0/23 Note: it looks as if there could be an 18-bit prefix in common; is it possible to choose 172.47.30.0/18? No, because this includes 232−18=14 = 16384, while there are only 28 × 4 = 1024 addresses in the original four blocks. The aim is to include only our addresses, not those that belong to others. General Approach: (a) Determine which octet the prefix will end in. Here, we have 28 × 4 = 1024 addresses, so we have the prefix ending in the third octet. (b) Convert that octet only from the first and last address, to binary. So here, we convert 3010 → 000111102 and 3310 → 001000012 . 0.00000000 1.00000000 0.00000000 1.00000000 Nick Urbanik nicku(at)vtc.edu.hk ver. 1.11 Solutions CIDR, Route Summarisation and Routing Systems and Network Management 2 (c) Do these binary numbers have a common prefix, to the right of which all bits count from 000. . . 000 to 111. . . 111? Well, in this case, no, so. . . (d) Find the power of two over which the third octet counts. Here, the power of 2 is 32 = 25 . Convert the value before and after the power of 2 to binary: 25 − 1 = 000111112 , and 25 = 001000002 . (e) Now compare the first 3010 → 000111102 with 25 − 1 = 000111112 , and see if we have a common prefix, to the right of which all bits count from 000. . . 000 to 111. . . 111. Well, yes we do! It is 0001111 x. (f ) Now compare 25 = 001000002 with 3310 → 001000012 . Can we see a common prefix, with bits to the right counting from all 0’s to all 1’s? Yes! It is 0010000 x. 2. Aggregate the following set of (64) 24-bit network addresses to the highest degree possible. 202.1.96.0/24 202.1.97.0/24 202.1.98.0/24 . . . 202.1.126.0/24 202.1.127.0/24 202.1.128.0/24 202.1.129.0/24 . . . 202.1.158.0/24 202.1.159.0/24 Here is how to do it: List each address in binary format and determine the common prefix for all of the addresses: ← . . . first prefix . . . → 202.1.96.0/24 202.1.97.0/24 202.1.98.0/24 . . . 11001010.00000001.01100000.00000000 11001010.00000001.01100001.00000000 11001010.00000001.01100010.00000000 . . . 202.1.126.0/24 11001010.00000001.01111110.00000000 202.1.127.0/24 11001010.00000001.01111111.00000000 202.1.128.0/24 11001010.00000001.10000000.00000000 202.1.129.0/24 . . . 11001010.00000001.10000001.00000000 . . . 202.1.158.0/24 11001010.00000001.10011110.00000000 202.1.159.0/24 11001010.00000001.10011111.00000000 ← . . second prefix . . → Nick Urbanik nicku(at)vtc.edu.hk ver. 1.11 Solutions CIDR, Route Summarisation and Routing Systems and Network Management 3 Note that this set of 64 24-bit blocks cannot be summarised as a single 18-bit block 202.1.96.0/19 11001010.00000001.01100000.00000000 202.1.128.0/19 11001010.00000001.10000000.00000000 So the two 19-bit blocks are: 202.1.96.0/19 202.1.128.0/19 Could the answer be 202.1.96.0/16? No, because that includes 216 = 65536 different addresses, not just the 28 × 64 = 16384 addresses that we are taking care of. General Approach Applied to This Problem: 1. Determine which octet the prefix will end in. Here, we have 28 × 64 = 16,384 addresses, so we have the prefix ending in the third octet. 2. Convert that octet only from the first and last address, to binary. So here, we convert 9610 → 0110 00002 and 15910 → 1001 11112 . 3. Do these binary numbers have a common prefix, to the right of which all bits count from 000. . . 000 to 111. . . 111? Well, in this case, no, so. . . 4. Find the power of two over which the third octet counts. Here, the power of 2 is 128 = 75 . Convert the value before and after the power of 2 to binary: 27 − 1 = 0111 11112 , and 27 = 1000 00002 . 5. Now compare the third octet from the first address block, 9610 → 0110 00002 with 27 − 1 = 0111 11112 , and see if we have a common prefix, to the right of which all bits count from 000. . . 000 to 111. . . 111. Well, yes we do! It is 011 xxxxx. 6. Now compare 27 = 1000 00002 with 15910 → 1001 11112 . Can we see a common prefix, with bits to the right counting from all 0’s to all 1’s? Yes! It is 100 xxxxx. Some Other Points: • The prefixes do not all have to be the same size. • In the two examples given here, we only needed to convert four eight-bit numbers to binary, not sixty-four 32-bit numbers. • You may have to continue to divide these groups of addresses until you find a single address block. In other words, you may need to apply the above steps recursively until you find all the address blocks. • If you want to see a computer algorithm for doing this, see the compact() method in the Perl module NetAddr::IP, from cpan. • You can always make a simple sanity check by calculating the number of host addresses in the input, and making sure that it matches the number in the summarised output. Nick Urbanik nicku(at)vtc.edu.hk ver. 1.11 Solutions CIDR, Route Summarisation and Routing Systems and Network Management 4 2 Questions 1. (a) How many 24-bit network blocks are available within the cidr block 200.56.168.0/21? (Hint: how many times does 232−24 divide into 232−21 ? Hmm, 232−21−(32−24) = i i 224−21 ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . (b) List them. 8 The last three bits of the third byte select each of the eight subnets. We just count these bits from 0 to 7, giving us each of the 24-bit network blocks: 11001000.00111000.10101xxx.xxxxxxxx 200.56.168.0/21 which can give us: 11001000.00111000.10101000 .xxxxxxxx 11001000.00111000.10101001 .xxxxxxxx 11001000.00111000.10101010 .xxxxxxxx 11001000.00111000.10101011 .xxxxxxxx 11001000.00111000.10101100 .xxxxxxxx 11001000.00111000.10101101 .xxxxxxxx 11001000.00111000.10101110 .xxxxxxxx 11001000.00111000.10101111 .xxxxxxxx 200.56.168.0/24 200.56.169.0/24 200.56.170.0/24 200.56.171.0/24 200.56.172.0/24 200.56.173.0/24 200.56.174.0/24 200.56.175.0/24 2. Aggregate the following 24-bit blocks into as few blocks as possible: 212.56.132.0/24 212.56.133.0/24 212.56.134.0/24 212.56.135.0/24 (Hint: determine the prefix common to them all). i 212.56.132.0/22 So how did I get that answer? All the action happens in the third byte. Let’s look at the binary value of it: 132 10000100 133 10000101 134 10000110 135 10000111 You notice that the first 22 bits (first two bytes + the first 6 bits of the third byte) are all the same, while the bits to the right of the prefix go through all possible values of all zeros to all ones. 3. Aggregate the following 24-bit blocks into as few blocks as possible: Nick Urbanik nicku(at)vtc.edu.hk ver. 1.11 Solutions CIDR, Route Summarisation and Routing Systems and Network Management 5 212.56.146.0/24 212.56.147.0/24 212.56.148.0/24 212.56.149.0/24 i 212.56.146.0/23 and 212.56.148.0/23 To aggregate into one block, the last two bits in the third octet must count from 00 to 11. Let’s see what the third octet is in binary: 146 10010010 147 10010011 148 10010100 149 10010101 So we see that we cannot find a common /22 prefix that includes all possible values; we can only have two /23 prefixes here: 212.56.146.0/24 212.56.147.0/24 212.56.148.0/24 212.56.149.0/24 11010100.00111000.10010010 .00000000 11010100.00111000.10010011 .00000000 11010100.00111000.10010100 .00000000 11010100.00111000.10010101 .00000000 ← . . . . . . . . prefix . . . . . . . . → The prefixes are 212.56.146.0/23 and 212.56.148.0/23 Nick Urbanik nicku(at)vtc.edu.hk ver. 1.11 Solutions CIDR, Route Summarisation and Routing Systems and Network Management 6 4. Here is a quote from an email: I’m thinking if we allocate, say 48 groups of 8-bit address space to you, let’s say, from 172.19.16.x – 172.19.63.x, would it solve your problem ? The point is, if you agree on such an arrangement, we don’t have to ask for outside help than CC/IVE(TY) as 172.x.x.x are solely allocated to us. What’s your opinion ? Aggregate the following 24-bit blocks into as few blocks as possible: 172.19.16.0/24 172.19.17.0/24 172.19.18.0/24 . . . 172.19.62.0/24 172.19.63.0/24 i There are many ways of looking at this problem. Consider the number of addresses there are: (63 − 16 + 1) × 28 = 48 × 256 = 12288. Now what power of two can include those addresses? log2 12288 ≈ 13.58, i.e., no power of two can include all those addresses without including other addresses that are not part of this block. A single cidr address block always contains a number of addresses that is exactly a power of 2. Okay, let’s look at the third octet. ← . . . . first prefix . . . . → 172.19.16.0/24 10101100.00010011.00010000 .xxxxxxxx 172.19.17.0/24 10101100.00010011.00010001 .xxxxxxxx . . . . . . 172.19.31.0/24 10101100.00010011.00011111 .xxxxxxxx 172.19.32.0/24 10101100.00010011.00100000 .xxxxxxxx . . . . . . 172.19.63.0/24 10101100.00010011.00111111 .xxxxxxxx ← . . second prefix . . → Note that the prefix is the bits that are shown before the small vertical bar on each address. The bits to the right of the prefix must include the entire possible range of bits; the bits shown in bold italic must range from all zeros to all ones, otherwise if we use this prefix, we would be including other addresses that we may not own. Of course, within one cidr address block, the prefix is common. The 16 address blocks above the horizontal line can be aggregated into the cidr address block 172.19.16.0/20, while the 32 address blocks below the hoizontal line can be aggregated into the cidr address block 172.19.32.0/19. Note that I use the terms “agreggate” and “summarise” to mean the same thing. 2.1 Routers and Address Allocation 1. In the example problem given in the lecture (see figure 1 on the following page), the addresses were allocated, but the routes advertised by each router were not Nick Urbanik nicku(at)vtc.edu.hk ver. 1.11 Solutions CIDR, Route Summarisation and Routing Systems and Network Management subnet 1 subnet 2 subnet 3 subnet 4 subnet 5 Y Router A X Router C Z Router B 7 subnet 6 subnet 7 subnet 8 Figure 1: The routing problem from the lecture. determined. Using the addresses given in the lecture, what routes does Router A advertise at X, and Router B advertise at Y, and Router C advertise at Z? i Since Router A has 5 subnets: subnet subnet subnet subnet subnet subnet 1 2 3 4 5 network 172.19.0.0/24 172.19.1.0/24 172.19.2.0/24 172.19.3.0/24 172.19.4.0/24 we summarise these into the following routes router A advertises at X: 172.19.0.0/22 172.19.4.0/24 The subnets behind Router B summarise from subnet network subnet 6 172.19.5.0/24 subnet 7 172.19.6.0/24 subnet 8 172.19.7.0/24 to the following routes router B advertises at Y: 172.19.6.0/23 172.19.5.0/24 Router C aggregates all these together with the routers for the small subnets for the two links, and advertises this at Z: 172.19.0.0/21 172.19.128.0/29 2. Figure 2 on the next page shows a network with 5 routers and 14 subnets. You may select ip addresses from the two blocks of addresses 172.12.0.0/19 and 192.168.0.0/27. You must leave at least one quarter of these addresses available for other purposes. The requirements are that each of subnets 1, 2,. . . , 8 must support up to 128 computers, while subnets 9 and 10 must each support up to 520 computers. Nick Urbanik nicku(at)vtc.edu.hk ver. 1.11 Solutions CIDR, Route Summarisation and Routing Systems and Network Management subnet 1 subnet 2 subnet 3 subnet 4 subnet 5 W Router A X Router D Y Router E Z 8 subnet 6 subnet 7 subnet 8 Router B V subnet 9 subnet 10 Router C Figure 2: A network with five routers and fourteen subnets. (a) Allocate a suitable block of addresses to each of the fourteen subnets that will Nick Urbanik nicku(at)vtc.edu.hk ver. 1.11 Solutions CIDR, Route Summarisation and Routing Systems and Network Management 9 allow maximum route aggregation. (Do not include link Z). i General strategy: determine the lower and upper limits on each subnet. Let’s start with the serial links between the routers, which each need only two addresses in each link. These should come from the smaller address block 192.168.0.0/27. The minimum size of the required subnets is 4 addresses, since the first address is the network address, and the last is the broadcast address. So the lowest power of two that includes these addresses is 2, since 22 = 2 + 2, so we need a 32 − 2 = 30 bit netmask for the links. Let’s allocate these addresses so that the routes from the links X and W can be aggregated by router D. So here is our allocation of addresses: subnet subnet subnet subnet subnet network X 192.168.0.0/30 W 192.168.0.4/30 V 192.168.0.8/30 Y 192.168.0.12/30 The minimum size of each of the first 8 subnets is 256, i.e., a /24 subnet, as 28 is the lowest power of 2 that contains 128 + 2. Let us allocate the lowest 8 /24 blocks: subnet subnet subnet subnet subnet subnet subnet subnet subnet 1 2 3 4 5 6 7 8 network 172.12.0.0/24 172.12.1.0/24 172.12.2.0/24 172.12.3.0/24 172.12.4.0/24 172.12.5.0/24 172.12.6.0/24 172.12.7.0/24 log2 520 The minimum size of subnets 9 and 10 is 210 = 1024, since 2 giving a subnet size of /22. Let us allocate the next lowest 2 /22 blocks: subnet subnet 9 subnet 10 network 172.12.8.0/22 172.12.12.0/22 = 210 , This would use only half of the available addresses. (b) Given your selection in the previous part, with route summarisation disabled on all the routers, list the routes that would be advertised by router A at X, Nick Urbanik nicku(at)vtc.edu.hk ver. 1.11 Solutions CIDR, Route Summarisation and Routing Systems and Network Management 10 i by router B at W, by router C at V, by router D at Y, and by router E at Z. Without route summarisation, router A will advertise one route for each of its five subnets: 172.12.0.0/24 172.12.1.0/24 172.12.2.0/24 172.12.3.0/24 172.12.4.0/24 and router B will advertise one route for each of its three subnets: 172.12.5.0/24 172.12.6.0/24 172.12.7.0/24 Router C will advertise one route for each of its two subnets: 172.12.8.0/22 172.12.12.0/22 Router D will advertise one route for each of the eight subnets behind routers A and B, and the one each for each of the links X and W: 172.12.0.0/24 172.12.1.0/24 172.12.2.0/24 172.12.3.0/24 172.12.4.0/24 172.12.5.0/24 172.12.6.0/24 172.12.7.0/24 192.168.0.0/30 192.168.0.4/30 Finally router E will advertise one route for each of the ten subnets behind routers A, B and C, and one route for each of the subnets V, W, X, Y: 172.12.0.0/24 172.12.7.0/24 172.12.1.0/24 172.12.8.0/22 172.12.2.0/24 172.12.12.0/22 172.12.3.0/24 192.168.0.0/30 172.12.4.0/24 192.168.0.4/30 172.12.5.0/24 192.168.0.8/30 172.12.6.0/24 192.168.0.12/30 (c) What would be a necessary requirement for the routers to support route summarisation? The routers should be running a classless routing protocol, such as ospf, rip2 or bgp. (d) Repeat part 2b, but for the case where route summarisation is enabled on all i Nick Urbanik nicku(at)vtc.edu.hk ver. 1.11 Solutions CIDR, Route Summarisation and Routing Systems and Network Management 11 i routers. For router A, the first four routes will be aggregated (summarised), so there will be two routes advertised: 172.12.0.0/22 172.12.4.0/24 Router B will summarise the last two routes: 172.12.5.0/24 172.12.6.0/23 Router C will summarise both routes into one: 172.12.8.0/21 Router D will summarise the two routes from router A and the two routes from router B into one route, and will sumarise the routes to links W and X into one route: 172.12.0.0/21 192.168.0.0/29 Router E will aggregate the route from router C with the two routes from router D, and the routes to links V and Y into two routes: 172.12.0.0/20 192.168.0.0/28 Nick Urbanik nicku(at)vtc.edu.hk ver. 1.11