xixitalk's snippet

Post Longer Than 140 Characters Tweets

Mar 11, 2013 - Comments

算法:判断是否是中国IP?

世界上有五个区域互联网注册管理机构,负责亚洲和太平洋地区的是亚太网络信息中心(APNIC)。点击这里可以获得亚太地址各个国家或地区申请到的IP地址区域。 中国共申请到42亿中的330026496个IPv4地址(约3.3亿),分布在3579块不同的区域。
IPv4地址格式是addr1.addr2.addr3.addr4,为了减少查找次数,考虑用空间换时间思路。所有2的32次方的IP,分布在256x256的区域内,每个区域表述addr1.addr2.*.*表述的IP(65536个IP)。 判断一个IP首先由addr1和addr2直接找到addr1.addr2.*.*的区域块,在块内进行搜索判断,这样查询的次数将大大降低。

Raspberry Pi代理原理图

每一个区域块有三种情况:
1、区域块为空
如果区域块为空,则表示此区域块无中国IP分布。
2、区域块有一个IP区域,则表示此区域有一个中国IP分布,查询一次是否匹配,如果匹配就是中国IP,如果不匹配就是外国IP。
3、区域块有多个IP区域,则表示此区域块有多个中国IP分布,遍历查询,如果匹配就是中国IP,如果不匹配就是外国IP。
情况2为理想情况,查询一次。情况3为恶劣情况,经过实际测试,202.14.*.*区域最恶劣,有40个区域块,202.14.*.*的IP要查询40次。虽然202.14.*.*区域的IP给中国分配了40次,但是不同次申请的区域是可以连续起来的,所以区域块内还可以优化。

下面是用python实现的一个测试代码:
用法:从http://ftp.apnic.net/apnic/stats/apnic/delegated-apnic-latest下载亚太IP分配表,保存为delegated-apnic-latest文本文件,将下面代码保存为isChinaIP.py,并运行之。

#/usr/bin/python
#coding: utf-8
global_ip_dict = [[[] for col in range(256)] for row in range(256)]
#input:apnic|CN|ipv4|112.0.0.0|4194304|20081215|allocated
#output:addr1,addr2,addr3,addr4,ip_num
def analyseLine(ip_line):
ip_str_list = ip_line.split('|')
if len(ip_str_list) < 7:
return 0,0,0,0,0
ip_nation,ip_version,ip_str,ip_num = ip_str_list[1],ip_str_list[2],ip_str_list[3],int(ip_str_list[4])
if ip_nation!='CN' or ip_version!='ipv4':
return 0,0,0,0,0
ip_addr = ip_str.split('.')
if len(ip_addr) < 4:
return 0,0,0,0,0
addr1,addr2,addr3,addr4 = int(ip_addr[0]),int(ip_addr[1]),int(ip_addr[2]),int(ip_addr[3])
return addr1,addr2,addr3,addr4,ip_num
#input:file delegated-apnic-latest
#output:True,init ip dict success;False,init ip dict fail.
def init_ip_dict(frome_file):
global global_ip_dict
try:
filedes = open(frome_file, 'r')
except:
return False
lines = filedes.readlines()
for line in lines:
addr1,addr2,addr3,addr4,number_sum = analyseLine(line)
if number_sum == 0:
continue
offset = 0
while number_sum > 0:
if number_sum >= 65536:
start,end,number = 0,65535,65536
else:
start = addr3*256 + addr4
end = start + number_sum -1
number = number_sum
global_ip_dict[addr1][addr2+offset].append({'start':start,'end':end,'number':number})
number_sum -= 65536
offset += 1
filedes.close()
return True
#input:ip string,*.*.*.*
#output:True,is china IP;False,is not china IP
def isChinaIP(ip):
global global_ip_dict
ip_addr = ip.split('.')
if len(ip_addr) < 4:
return False
addr1,addr2,addr3,addr4 = int(ip_addr[0]),int(ip_addr[1]),int(ip_addr[2]),int(ip_addr[3])
if len(global_ip_dict[addr1][addr2]) == 0:
return False
addr_value = addr3*256+addr4
for item in global_ip_dict[addr1][addr2]:
if addr_value >= item['start'] and addr_value <= item['end']:
return True
return False
if __name__=="__main__":
ret = init_ip_dict('delegated-apnic-latest')
if not ret:
print 'open file(delegated-apnic-latest) failed'
exit(-1)
for addr1 in range(100,256):
for addr2 in range(100,256):
ip_str = '%s.%s.5.5' % (addr1,addr2)
if isChinaIP(ip_str):
print '%s :china ip' % ip_str
else:
print '%s :not china ip' % ip_str
view raw isChinaIP.py hosted with ❤ by GitHub


知识共享许可协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

Tags: network

android上支持HTTP proxy代理的浏览器 stunnel原理