IP Address Searching
article shows two search methods that different versions of Anti DDoS Guardian
adopt. The two methods are sequential
search and binary
search. The performance of the later one is more superior than
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.
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.
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.