IP Address Searching
Methods
This
article shows two search methods that different versions of BeeThink
IP Blocker adopt. 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, BeeThink IP
Blocker organizes the IP list in sequential order. Once BeeThink IP
Blocker application stars, it reads IP list and checks it if all IP
addresses are ordered. If not, BeeThink IP blocker 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 BeeThink
IP Blocker, 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 BeeThink
IP Blocker 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, BeeThink IP
Blocker gets high performance.
|
