CodeProject: Optimized IP to ISO3166 Country Code Mapping in C#. Free source code and programming help

I started the development of the GameWatch project in December 2002 with the idea of combining both my need for a free (open-source) game browser and experimenting with c# development. In abstract, GameWatch is an online game servers browser for games like Half-Life or Unreal Tournament 2003 (in other words, it's not unlike GameSpy or the All-Seeing-Eye).

One of its numerous internet-related feature is getting the country code from the IP address of a server, so that the users can filter out the servers displayed according to the country they live in (in the hope of lowering the latency to the game server).

In this short article, I'll first introduce some features of IP addresses, then discuss the algorithm and data structure used for the implementation of the GameWatch's IP-to-CountryCode converter.

What is an IP address?

So, the first interesting property we get from this, is that we can handle those IP addresses as simply as unsigned 32-bit integers.

Another interesting property is that IP addresses have a semantic: the left part of the address specifies the network number, the right part of the address represents the local address inside this network. The size of the left and right parts depends on the kind of network. In IPV4, there are three kinds of network type:

To be very precise, there are not really 8, 16, and 24 bits for the network codes, as a few bits are taken to help distinguish the network types, but you got the idea, and this is not relevant for our purpose in this article.

Well, what we learned here, is that we won't need all of the 32 bits of the IP address to get the country, as we can omit the local address, which value is always specific to its network. Thus, the significant part of an IP address for our IP-to-Country conversion can vary from 8 to 24 bits.

The standard internet database

Each of these entities manage their IP allocation database, which are publicly available on their web site in text format. Those databases contain a list of lines of the form:

As you can see, the tokens are separated by '|' characters, and the elements of particular interest for us are the country (second token) and the network address (fourth token). The other tokens represent the RIR responsible for the allocation, the version of the IP protocol used (IPv4 is described in RFC 791), the number of possible local address to be used with this network code, and the date of the initial allocation.

Now that we know how an IP address is composed, and that we have a database to find the country of an IP address, what do we do next ? Well, we must find a way to store the information and retrieve it as fast as possible.

Finding the best data structure

The Hashtable class does not fit, as it cannot match keys with part of the key entries (the Hashtable algorithm would test the IP address against each possible network code size, which is not acceptable).

The arraylist (and all the flavours of Linked List one can think about) does not fit either, as each IP address test would require at most O(N) look-ups, with N the number of entries in the database (and we have a lot of them).

If we dive in the world of the internet software programming, we can easely find a domain that has a very similar issue: IP routing table lookup. IP routing involves finding the best network mask for a given target IP address, in order to find the IP address of a connected gateway that can reach the target.

Well, we are not doing routing, but we have a similar goal: finding the network code that matches our IP address. Note that there are a number of differences as well: we are not interested in frequently updating our table (adding or removing a network mask), and we have only one possible matching network code, while IP routing usually have several ones (this adds the constraint that only the longest-matching network must be selected).

So, how are our friends from IP Routing doing ? In fact, many solutions have been proposed in hundreds of papers. It goes from the simplest binary-trees (with the space complexity drawbacks) to the most sophisticated Peano Count Trees with partitionning based on prefix length [HABIB].

However the most commonly used structures are taken in the family of the Tries (pronounced like "tree", most urban legends say the name comes from reTRIEval trees). Tries are tree-based structures where each node represents a part of the item key. For instance, a character-based trie would store the two words "eater" and "eating" as follows:

There are several variants of the Trie data structure, one of the most efficient being the PATRICIA (Practical Algorithm To Retrieve Information Coded In Alphanumeric) Trie [MORRISON68].

The main characteristic of the PATRICIA trie is the way it eliminates unnecessary nodes by grouping the sequences of tokens whenever possible.

FreeBSD for instance uses a radix trie structure (very similar to the PATRICIA one) to hold its ip routing table, and many software routers use a PATRICIA trie to hold their ip tables (FutureSoft's IPV6 Routers, for instance).

The reader can easely find a lot of descriptions on the Patricia Trie around the web. Basically, let me stress the following property of the PATRICIA Trie: it is a compact data structure that can give you the longest prefix of an entry key in O(N) steps (in the worst case), with N the length of the longest prefix (see [PACKER2000] for a good performance analysis).

Implementing a Patricia Trie to store IP Tables

The BitVectorTrie class implements a PATRICIA Trie using BitVector objects as keys for the indexing of the data. It contains mainly three methods:

The Add() method stores the "data" object using the BitVector "key". Conversely, the Get() method retrieves an object stored using a BitVector key.

GetBest() is the most interesting method for our purpose of mapping an IP address to a country code: it walks the nodes of the trie, following the path provided in the BitVector key. The method walks as much of the trie as it can, and return the value stored at the end of the path (in our case, the BitVector object describes the path to follow).

For instance, the GetBest() method used with the following BitVector {00110100101 1100} as argument retrieves the object highlighted in the figure below.

In the example above, the trie look-up stops at the 00110100101 prefix, and returns the object stored in the last node of the path. This node represents the longest prefix for the BitVector given as argument.

As the source code provided is quite simple and documented, the reader can refer to it for the details of the PATRICIA trie implementation.

The IPToCountry class

Benchmark results

The benchmark program loads a list of 25000 IP addresses that run a game server (taken from the unreal tournament 2003 and Half-Life servers lists) and performs a look-up for each of them.

The results show an average of 20'000 IP addresses processed per second with a nice space complexity, which fits perfectly our requirements.

A few notes on the provided source code

Implementation Note: In the implemented algorithm it is not taken into account the fact that the local addresses in a same network can be dispatched in several countries. Indeed, international organisations can use their network as they wish, and a company can dispatch its IP over several countries. There is unfortunately nothing we can do against it, as this is the private domain of the owner of the network code.

Bibliography