IP Address Searching Methods

This article shows two search methods that different versions of Anti DDoS Guardian uses. The two methods are sequential search and binary search. The performance of the later one is more superior than the former.

In order to search a certain IP address in the whole IP list, Anti DDoS Guardian organizes the IP list in sequential order. Once Anti DDoS Guardian application stars, it reads IP list and checks it if all IP addresses are ordered. If not, Anti DDoS Guardian application makes it in sequential order and then send it to the kernel IP filter driver. When a network packet passes through the IP filter driver, it will be matched to the whole IP list to see whether it will be blocked or not.

In the first version of Anti DDoS Guardian, each network packet just be matched from the first IP addresses of the whole IP list to the last one. This search method is called linear search or sequential search, with which each IP address of the whole IP list is checked. Linear search is easy to implemented but it spends much time especially when the IP address number of the IP list is more than 200,000.

The second version of Anti DDoS Guardian changed the search algorithm to a faster one - binary search. The idea is simple: compare the target IP address to the middle item in the IP list. If the target IP address is the same as the middle item, the target IP address is matched. If it is before the middle item, repeat this procedure on the items before the middle. If it is after the middle item, repeat on the items after the middle. In the end, the target IP address will be found out whether it is included in the whole IP list or not. From such a way, Anti DDoS Guardian gets high performance.