Search code examples
algorithmsubnetopenflowspace-efficiencysdn

Get a set of subnets/adresses from IP range

I'm looking for a good algorithm (or code if you speak it better than English) to do the following:

For a given IP range (e.g. 1.1.1.1 - 1.1.2.247), find the smallest combination of subnets/addresses that includes all the IPs in the specified range. Ignore broadcast, subnet 0 restrictions, and network class.

Examples:

  • For 1.1.1.1 - 1.1.2.1 you'd get {1.1.1.1/24, 1.1.2.1} which is better/smaller than {1.1.1.1, 1.1.1.2, ..., 1.1.1.255, 1.1.2.1}
  • For 1.1.1.12 - 1.1.1.31 you'd get {1.1.1.12/30, 1.1.1.16/28} which is better/smaller than {1.1.1.12, 1.1.1.13, 1.1.1.14, 1.1.1.15, 1.1.1.16/28}

For the curious, the use case is matching network traffic on an arbitrary range of source/destination IPs with the smallest number of flows, using the Openflow protocol. The need for this optimization arises from the fact that hardware switches/routers have limited space for these flow configurations, and it takes a relatively long time to program/modify.

Solution

  • If you think of the IP addresses as 32-bit numbers, this is the problem of finding a set of intervals whose union is the range of IP addresses you need to fill. Looking at your first example, I am going to assume that when you say .1 you allow the interval to include .0, because 1.1.1.1/24 is the set of addresses as 1.1.1.0/24.

    Treating the IP addresses as numbers, I would start with the smallest number and look for the largest subnet starting at this number which does not go further than the end IP address. Accept this as your first subnet and work out the IP address just off the end of the range you have just covered. Then start again to find the largest subnet starting at that IP address which doesn't go too far - and so on.

    This is optimal because the subnets available are all lined up on powers of two. To get to use a large subnet that covers 2^n addresses you must move to a starting address which has the lower n bits clear. If you have less than n bits clear the way to do this is to choose the largest step possible at each stage, and each step clears the lowest set bit in the current address.