I am looking for a PHP algorithm/script

[Tech Manager]

I am a professional PHP programmer experiencing brain freeze.

I am looking for a script/algorithm that I can interface with a database to create consolidated/aggregated IP blocks.

Here is the issue:

I own and run Country IP Blocks. This site provides highly accurate network information on nearly 250 countries around the world. Data is pulled from one of our several databases to produce a wide variety of ACL's, such as CIDR, dotted-decimal, .htaccess deny & allow and other lists as needed.

I've been contacted by several network administrators asking if we would begin distributing consolidated/aggregated IP Blocks to allow for easier development of specific firewall rules. In other words, aggregation of contiguous IP blocks would provide the option for shorter lists. Normally I would program this myself, but with my current heavy schedule and temporary brain freeze I thought I would ask if any of you know of a PHP solution to solve this problem.

Basically what we want to do is to pull continguous IP blocks from the database, aggregate them and present the results.

Here's an example of a few blocks from China:

58.18.0.0/16 58.18.0.0 - 58.18.255.255 974258176 - 974323711
58.19.0.0/16 58.19.0.0 - 58.19.255.255 974323712 - 974389247
58.20.0.0/16 58.20.0.0 - 58.20.255.255 974389248 - 974454783
58.21.0.0/16 58.21.0.0 - 58.21.255.255 974454784 - 974520319
58.22.0.0/15 58.22.0.0 - 58.23.255.255 974520320 - 974651391
58.24.0.0/15 58.24.0.0 - 58.25.255.255 974651392 - 974782463

58.30.0.0/15 58.30.0.0 - 58.31.255.255 975044608 - 975175679
58.32.0.0/13 58.32.0.0 - 58.39.255.255 975175680 - 975699967
58.40.0.0/15 58.40.0.0 - 58.41.255.255 975699968 - 975831039
58.42.0.0/16 58.42.0.0 - 58.42.255.255 975831040 - 975896575
58.43.0.0/16 58.43.0.0 - 58.43.255.255 975896576 - 975962111
58.44.0.0/14 58.44.0.0 - 58.47.255.255 975962112 - 976224255
58.48.0.0/13 58.48.0.0 - 58.55.255.255 976224256 - 976748543
58.56.0.0/15 58.56.0.0 - 58.57.255.255 976748544 - 976879615
58.58.0.0/16 58.58.0.0 - 58.58.255.255 976879616 - 976945151
58.59.0.0/17 58.59.0.0 - 58.59.127.255 976945152 - 976977919
58.59.128.0/17 58.59.128.0 - 58.59.255.255 976977920 - 977010687
58.60.0.0/14 58.60.0.0 - 58.63.255.255 977010688 - 977272831


The data in the tables actually appears in decimal ( the right columns) as opposed to dotted decimal.

Looking at the above info we want to produce aggregated results. So, doing some quick math the first 6 IP ranges should aggregate to 58.18.0.0/13

The second group of 12 ranges should aggregate to two IP Blocks: 58.30.0.0/11 and 58.62.0.0/15.

As you can see, this significantly reduces the output. The end result is the option of shorter lists and less memory/cpu required to run them on respective firewalls.

I am in need of a PHP script that can be modified as needed to produce similar results. If you are aware of such a script please let me know. Perhaps we could work out a suitable trade.

[kgun]

No, but the best (re)sources I can think of is:

• DNS Network Tools: Network Monitoring and DNS Monitoring from DNSstuff
• Gary Keith's Website

[Tech Manager]

Thanks for the links, but I see nothing relevant at either site.

[wige]

Just trying to work through the logic of this...

If I understand correctly, your database consists of the right column, listing the range of IP numbers for that block. What you need to do is on export convert that to the dot form (IPv4) plus calculate the proper subnet mask for the range so you are returning the left column? This should be doable with the built in converter functions long2ip and ip2long that are part of PHP.

Basically, I think you would just need to do the conversion by exploding the range into two values, min and max and converting the min to an IP address...

$min_ip = long2ip($min_num);

Then, just figure out what the difference between the min and max number is:

$range = $max_num - $min_num;

Then convert that range into the correct subnet:

$mask = <insert some math I don't remember here - sorry - anyone?>

Then concatenate the $min_ip and the mask to get the final string:

$answer = $min_ip . '/' . $mask;

[kgun]

Originally Posted by Tech Manager

I am looking for a script/algorithm that I can interface with a database to create consolidated/aggregated IP blocks.

1. Is there a unique formulae?
2. I am not an expert. A question I have asked myself is if there is an overlap for different countries?

Originally Posted by Tech Manager

Basically what we want to do is to pull continguous IP blocks from the database, aggregate them and present the results.


The data in the tables actually appears in decimal ( the right columns) as opposed to dotted decimal.

You don't imply by that that it is simple addition (modulo a number)?

Originally Posted by Tech Manager

As you can see, this significantly reduces the output. The end result is the option of shorter lists and less memory/cpu required to run them on respective firewalls.

So to repeat in other words, you are in a sense looking for least common denominators (like of prime numbers)?

Originally Posted by Tech Manager

I am in need of a PHP script that can be modified as needed to produce similar results. If you are aware of such a script please let me know. Perhaps we could work out a suitable trade.

And googling by different KW's does not give relevant hits?

The reason I mentioned the two above sites is that they are experts on IP-related problems, so they may know of such a script. DnsStuff has a forum. Gary Keith may be contacted by a simple question.

[Tech Manager]

Wige:

I appreciate the response, but the conversions are not necessary. The IP addresses are converted into decimal for several reasons, first and foremost is the ease of searching in decimal. They are converted back to dotted-decimal when results are produced.

What is really at issue is the ability to aggregate the IP Blocks, based on their respective countries. This could either be done as an algorithm off the database(s) which would tend to produce a little more overhead or as a process of populating a new database with the aggregated data. The latter reduces the CPU and Memory overhead.

The database currently contains info on 4.3 billion IP addresses. This equates to a little over 91,000 main network blocks (which can be further deconstructed to thousands of additional networks.

The goal is to offer an alternative to the current lists. They are accurate, but can become lengthy depending on how the RIR's apportioned the networks to each country.

The secondary database basically needs to reformulate the data of the first database into aggregations of country specific continguous networks.

The existing database(s) contain all the relevant data for each network range. This data includes the range in decimal form, number of hosts, CIDR, dotted-decimal netmasks, etc. Converting between decimal to dotted-decimal. binary. etc., is not at issue as all are easy to do.

I picture an algorithm that traverses an array (pulled from the database) that includes the network assignments (registrar, country, etc.) and IP range in decimal format. Continguous ranges would be those assigned to the same country where, when the database is sorted by starting IP, the ending IP would be one less number than the nest starting IP. In some case, such as thos given in the opening post, several IP blocks could be considered contiguous and the algorithm would basically use the original starting IP and locate the ending IP for the total continguous range.

Once you have the starting IP and new ending IP, the number of Hosts and the new CIDR/Netmask can be easily calculated to produce the aggregated block.

In the case of countries with large volume network assignments, like China, USA, Australia, etc., you could significantly reduce the ACL.

For example, as of September 30, 2008, China has 1,489 networks and 167,045,888 potentially available subnets. This makes for a long ACL aggregating the IP Block assignments might reduce the output by 90% thus allowing for an ACL that is only 149 lines long instead of 1,489 lines.

Does this clarify the matter?

[Tech Manager]

Originally Posted by kgun

1. Is there a unique formulae?
2. I am not an expert. A question I have asked myself is if there is an overlap for different countries?

You don't imply by that that it is simple addition (modulo a number)?


So to repeat in other words, you are in a sense looking for least common denominators (like of prime numbers)?


And googling by different KW's does not give relevant hits.

The reason I mentioned the two above sites is that they are experts on IP-related problems, so they may know of such a script. DnsStuff has a forum. Gary Keith may be contacted by a simple question.

1.) There is a unique formula. Think of it this way. The database(s) contain the complete listing of every IP address/network in the world. Each assigned network is keyed to a specific country, registrar and also has a unique key identifying the network.

When a request is made for a country or countries, the data is sorted by country first and then IP address. The formula for contiguous network is fairl simple. If country and ending IP range +1 is equal to country and starting IP range, you have a contiguous network.

[kgun]

1. If there is a unique (simple) formulae, your problem must be related to the magnitude of the problem, billions of IP's in a table column that can easily be transformed to decimal and easily back to dotted notation. Then you have some choices.
2. Computation that can be done directly in the database, using SQL calculus (aggregations?) on the table rows / columns.
3. Then there is no need for outputting data to a large array and use a PHP script to do the calculus.
4. If you have to use a scripting solution, that array may be too big to load it directly into the computers memory.
5. If it is too big you may split it into smaller manageable arrays. Once the results are there, the "results arrays" can be combined into a larger array and inserted into the database. May be the best is to use different databases for different countries / rigions with many IP tables and use the unique formula on each.
6. Streaming solutions may also be an alternative, where data are read in chunks into the computers memory, transformed and inserted into the result database / tables.
7. Personally if it is possible, I would have used 2, since you can do the math directly in the database.