IP地址地理位置映射技术

—102— IP地址地理位置映射技术 聂 荣 1，余建国 1，张洪欣 2，吕英华 2 (1. 郑州航空工业管理学院计算机科学与应用系，郑州 450015；2. 北京邮电大学电子工程学院，北京 100876) 摘 要：针对 P2P 网络流量的空间分布和传输模式研究，分析并验证 IP 地址地理位置映射技术。介绍并比较多种网络位置获取技术，分 析 IP地址地理位置映射技术的优势和基本原理。采用简单随机抽样方法对使用最广泛的 IP地址地理位置映射数据库进行抽样和评估。抽 样分析结果显示其数据准确率在省级区域位置上为 100%，在城市级区域位置可达 98.40%，验证了其可靠性。 关键词：对等网络；网络测量；位置知晓性；地理位置映射 IP Address Geomapping Technique NIE Rong1, YU Jian-guo1, ZHANG Hong-xin2, LV Ying-hua2 (1. Department of Computer Science and Application, Zhengzhou Institute of Aeronautical Industry Management, Zhengzhou 450015; 2. School of Electronic Engineering, Beijing University of Posts and Telecommunications, Beijing 100876) 【Abstract】To study the space distribution and the transmission mode of network traffic in P2P network, this paper analyzes and evaluates the IP address geomapping technique. The advantages and the principle of the technique are present with comparing different network location acquirement techniques. A simple random sampling method is implemented to evaluated the most popular IP address geomapping data-base. Results show that the accuracy rate of province-level locations is 100%, and the accuracy rate of city-level locations can achieve 98.40%. It proves the reliability of the technique. 【Key words】Peer-to-Peer(P2P); network measurement; location awareness; geomapping 计 算 机 工 程 Computer Engineering 第 34卷 第 15期 Vol.34 No.15 2008年 8月 August 2008 ·网络与通信· 文章编号：1000—3428(2008)15—0102—03 文献标识码：A 中图分类号：TP393.03 P2P 网络的使用模式和流量模式不同于传统电信服务和 网络业务。节点的地理位置分布直接决定了其物理网络位置、 流量的空间分布和传输模式。现有 P2P网络不考虑节点间的 实际网络位置关系和拓扑结构，导致大量网际间冗余流量， 降低了网络效率[1]。根据节点的 IP地址获得对应地理位置的 技术称为 IP 地址地理位置映射技术 (geomapping 或 geotargetting)。目前没有关于该技术的系统描述，其可靠性 和准确性未经分析或评估。相关研究获得的节点地理位置只 具体到国家。因此，本文深入研究 P2P网络的节点和流量分 布，获得的节点地理位置可具体到省和城市。 1 研究背景 P2P网络流量上下行对称地分散在约 106个客户端之间。 要对其进行研究，必须知道节点的物理网络位置或地理位置。 目前有如下 3种位置获取/识别方法： (1)探测节点的相关路由信息。使用此方法进行地理位置 区分的原理是根据节点间网络往返时延值划分网络拓扑结 构。比如，节点测量自己与一系列相对稳定的知名地标节点 (如固定互联网服务器)的时延值大小，将这些地标按时延值 大小进行排序，认为相同地标排列顺序的节点位于同一网络 区域。这种方法测量误差大、精度低，不适用于大规模网络 流量的研究。 (2)匹配 DNS/IP 地址。此方法较可靠，可以将同样拥有 n bit IP地址的节点归为同一网络区域，但因为 IP地址的网 络前缀长度通常不固定，所以误差较大。也可将使用相同 DNS服务器的节点划分为同一个网络区域。文献[2]同时使用 IP 地址网络前缀和 BGP 网络掩码信息来识别节点位置。但 DNS 服务器和 BGP 网络的相关信息难以被直接获得，且其 区分精度不高。 (3)IP地址地理位置映射。此方法是最成熟的地理位置识 别技术，适合大规模网络流量研究，区分精度可以达到具体 的地理位置。其原理是 IP地址在一定时间和一定网络范围内 会被分配给特定地理位置。文献[3]使用类似技术对 BitTorrent 网络中的节点地理位置分布进行了识别和统计，但只具体到 国家范围。文献[4]使用一个商业 IP地址地理位置映射数据库 对 Gnutella 网络中节点的地理位置分布进行了 ZIP 级别的研 究，根据 IP地址识别网络节点的地理位置，从而获知各个城 域网之间的流量状况。除网络流量研究外，该技术还应用于 顾客服务、SLA管理和即时通信等领域。 2 IP地址地理位置映射技术原理 IP地址地理位置映射技术使用简单的数据库技术建立 IP 地址与实际地理位置的对应关系。IP地址和分配组织结构如 图 1 所示。IP 地址先由 IANA 机构进行分配，再由 ICANN 统一负责。IANA把 IP地址分配给 5个地域性的 IP地址管理 机构 RIR，即 ARIN(北美地区)、LACNIC(拉丁美洲)、RIPE NCC(欧洲地区)、APNIC(亚太地区)、AFRINIC(非洲地区)。 在 RIR 之下是国家级注册机构(NIR)、本地区注册机构(LIR) 基金项目：国家自然科学基金资助项目(60671055)；河南省教育厅自 然科学研究基金资助项目(2008B510022) 作者简介：聂 荣(1977－)，男，讲师、博士，主研方向：P2P网络， 机器人网络；余建国，讲师；张洪欣，副教授；吕英华，教授、博 士生导师 收稿日期：2008-05-12 E-mail：bluebluff@gmail.com —103— 和网络运营商(ISP)，中国的国家级注册机构是中国互联网络 信息中心。经过上述处理后，IP地址与网络位置和地理位置 具有了一定对应关系。现有 IP地址地理位置映射数据库主要 来源于 IP地址管理机构、商业组织、民间机构。管理机构提 供的地理位置信息只具体到国家且更新较慢，商业组织提供 的地理位置信息虽然较具体，但不公开源代码。 IANA/ICANN ARIN LACNIC APNIC RIPE NCC AFRINIC LIR ISP NIR ISP ISP LIR ISP 用户 用户 用户 用户 用户 用户 图 1 IP地址分配的组织结构 IP 地址地理位置映射目前最广泛的应用是将纯真版 IP 数据库[5]集成到即时聊天程序中，实时显示通信方的地理位 置。该数据库的数据来源于中国电信、中国网通、长城宽带、 网通宽带、聚友宽带等 ISP的最新准确 IP地址地理位置数据， 记录了约 3×105条数据。其地理位置信息能精确到区/县级， 是目前地理位置映射记录数最多、最完善的 IP数据库。该数 据库只有一个 QQWry.dat文件，可方便地嵌入到网络测量程 序中，操作简单、快速，并可以通过网络随时更新记录。 以纯真版 IP 数据库[5]为例说明 IP 地址地理位置映射数 据库的基本原理，其他数据库的原理与此类似。QQWry.dat 文件的结构如图 2 所示，分为文件头、索引区和记录区。文 件头共 8 B。索引区存放与各条地理位置记录相对应的索引 值。起始 IP是指一条地理位置记录对应的 IP范围的起始点。 记录区用于存放地理位置记录。输入 IP地址使用数据库查询 其对应的地理位置，先在索引区查找索引记录，然后到记录 区读出相应的地理位置信息。 第1条索引偏移： 0xXXXXXXXX 最后1条索引偏移： 0xXXXXXXXX 起始IP, 4 B 更多索引 IP记录偏移, 3 B 起始IP, 4 B IP记录偏移, 3 B 第1条IP记录 更多IP记录 最后1条IP记录 0 4 8 文件头 索引区 记录区 图 2 QQWry.dat文件结构 IP地址的分配会在一定范围、一定时间内发生变更。而 IP地址地理位置映射数据库不能及时更新，将导致数据错误， 这对研究造成的影响可能很巨大。在使用了 IP地址地理位置 数据库的相关研究中，未对数据库的准确率进行验证，降低 了可信度。 3 抽样分析和评估 抽样分析的数据库为纯真版 QQ IP数据库 Build 0505[5]， 共有 300 826条记录。每条记录是一个 IP地址范围，IP地址 通常以这个范围为基本单位进行分配。抽样分析一条记录中 的一个 IP地址，就可以认为对整条记录进行了验证。 参与抽样分析的 20个人员使用即时通信工具，选择通信 工具里在线的同学、亲戚和现实中认识的可靠朋友通信，获 取对方的 IP地址和真实准确的地理位置。限定通信方可防止 获得虚假信息。抽样方法采用不考虑抽样顺序的简单随机重 复抽样。 3.1 样本容量的确定 数学计算抽样所需的样本容量。根据统计学中的基础知 识，IP地址地理位置映射数据库的数据准确率属于随机现象， 理论上服从正态分布。设数据库数据记录总数为总体 X。X 的平均数为μ，方差为 σ2。可认为容量为 n的样本平均数 x 服 从正态分布 2( , )xN µ σ ，因为 X为有限总体重复抽样，所以 2 2 /x nσ σ= (1) 根据正态分布的性质， / xZ x µ σ= −（ ） 服从正态 分布。 根据 Z的定义，有 0( ) 1xP x Zµ σ α− = −≤ (2) 设置信度 1-α = 0.95，代入式(2)，确定 Z0＝2。 令标志为是非标志，样本中地理位置信息正确的记录总 数为 n1，错误的记录总数为 n2。总体中地理位置信息正确的 记录总数为 N1，错误的记录总数为 N2。设 p为数据库的样本 准确率，P为数据库的总体准确率。当样本容量大于 30时， Z可用标准正态分布近似计算。 1 2 1 2( ) / /nx x x x n n n p= + + + = =L (3) 2 2 2 2 1 2 1 1 1( ) [(1 ) (0 ) ] (1 ) N i i X P N P N P P N N σ µ = = − = − + − = −∑ (4) 令抽样极限误差 xxZ ∆=σ0 (5) 将式(1)、式(3)～式(4)代入式(5)，可得 2 2 2 0 0/ (1 ) /p pn Z Z P Pσ= ∆ = − ∆ (6) 设 P＝90%， 90% 5% 0.045p∆ = × = ，代入式(6)，则样本 容量应达到 2 2 2 0 (1 ) / 2 0.9 0.1/ 0.045 178Pn Z P P= − ∆ = × × = (7) 3.2 数据分析 抽样获得一个容量 n=200的样本，符合式(7)。仅对中国 的 IP 地址进行抽样调查，如 1 所示。样本覆盖了中国 32个省/直辖市中的 30个，较全面地覆盖了总体。 表 1 抽取样本分布 省/直辖市 样本个数 省/直辖市 样本个数 省/直辖市 样本个数 北京 6 江苏 7 新疆 3 上海 10 浙江 11 广西 6 天津 8 安徽 6 海南 2 重庆 4 宁夏 1 四川 11 河北 8 福建 8 贵州 2 山西 2 江西 5 云南 4 青海 0 山东 9 西藏 0 内蒙古 2 河南 36 陕西 3 辽宁 7 湖北 10 甘肃 4 吉林 1 湖南 9 黑龙江 3 广东 12 统计地理位置在省级和县/市级范围的正确率，部分结果 如表 2所示。 表 2 IP地址测试记录统计 测得 IP 地址 数据库地理位置 实际地理位置 状态 (省级) 状态 (市级) 221.222.173.17 北京市海淀区网通 ADSL 北京市海淀区 正确 正确 60.208.155.106 山东省济南市网通 山东省济南市 正确 正确 58.40.2.231 山东省网通 山东省济南市 正确 错误 由抽样统计结果可知，IP 记录的省级正确率为 100%， 这是因为这一层次的 IP 地址由 CNNIC 统一分配给各省，比 较固定。具体到市级，共有 9个 IP地址对应的地理位置出现 了偏差，此时样本平均数为 —104— 1 1 2 1 ( 1 0) 95.50%ix nx p n n n n n ∑= = = × + × = = (8) 样本方差为 2 2 1 1 (1 )( ) 0.955 0.045 200/199 0.043 19 1 1 n i i np ps x x n n= −= − = = × × =∑− − (9) 3.3 置信区间 计算当置信度为 95%时的 IP 地址地理位置映射数据库 的准确率可信区间α =5%，查表知 0 1.96Z = ，且 ~ (0,1) p p PZ Nσ −= 所以有 2 2 20.043 19 / 200 0.000 22 (0.014 8)p s nσ = = = ≈／ (10) 因为 n=200是大样本，所以可认为样本平均数 p近似服 从正态分布，有 2 2 2~ ( , ) ( , / ) ( , 0.014 8 ) x p N N s n N Pµ σ µ= = 0 0p pp Z P p Zσ σ− +≤ ≤ (11) 0.926 0 0.984 0P ≤ ≤ 置信度为 95%时，纯真版 IP数据库的准确率置信区间为 [92.60%, 98.40%]，准确率较高，根据其获取的测量结果可靠。 4 BitTorrent网络节点地理分布规律 BitTorrent(BT)网络是应用最广泛的 P2P网络。对欧洲顶 级 ISP 骨干网的流量统计显示 BT 网络产生的流量占全部网 络流量的 1/3。本文对一个 381.7 MB的视频共享文件进行监 测，该文件在测量期间下载的用户量具有代表性。 在 2007 年 3 月 7 日～2007 年 3 月 22 日为期 15 天的测 量中，共获得 11 292个节点的信息。对节点的地理位置按省 级范围划分，结果如图 3所示。 12% 14% 14% 14% 20%8% 6% 4% 4% 4% 广东上海 北京江苏 天津 河北 辽宁 河南 浙江 其 他 图 3 BT网络中节点的实际网络位置分布 节点分布较多的省/市为广东省、上海市、北京市和江苏 省，4个省市的节点占全部节点的 54%。这和 CNNIC调查中 统计到的网民地理分布基本相同，说明在经济较发达地区使 用网络的人数更多。 由图 3可知，处于同省的节点最高只有 14%，大部分节 点分散在不同地域中。这种地理分布表明，如果节点不能优 先选择处于同一地域的节点进行文件的传输，就会出现网络 试验中出现的情况[1]，导致过多网络传输跨越城域网，产生 大量网际间冗余流量。 5 结束语 IP地址地理位置映射技术具有简单、准确和成熟的优点， 为 P2P网络的流量和网络架构研究提供了重要支撑。对于市 级区域，在置信度为 95%时，其准确率置信区间为[92.60%, 98.407%]，数据准确度高。笔者使用该技术研究 BitTorrent 网络的节点地理位置分布规律，发现网络使用率高的地区拥 有更多节点，且大部分节点分散在不同省份。 参考文献 [1] Nie Rong, Lei Zhenming. Measurement Study of the Location Awareness in P2P Systems[C]//Proceedings of the Int’l Conference on Communication and Information. Beijing, China: [s. n.], 2005. [2] Krishnamurthy B, Wang Jia. On Network-aware Clustering of Web Clients[C]//Proc. of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication. New York, USA: ACM Press, 2000. [3] Izal M, Urvoy K G, Biersack E W, et al. Dissecting BitTorrent: Five Months in a Torrent’s lifetime[C]//Proceedings of the 5th Passive and Active Measurement Workshop. Heidelberg, Germany: [s. n.], 2004. [4] Hamada T, Chujo K, Chujo T, et al. Peer-to-Peer Traffic in Metro Networks: Analysis, Modeling, and Policies[C]//Proceedings of the IEEE Symposium on Network Operations and Management. [S. l.]: IEEE Press, 2004. [5] 金狐软件公司. 纯真版QQ IP数据库Build 0505[Z]. (2007-08-06). http://www.haoz.cn/Soft/sort60/81/28449.html. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ （上接第 101页） 5 结束语 本文对 CPNSS算法进行了改进，提出了在高密度环境下 能量均衡的覆盖控制算法。仿真实验表明，新算法能更充分 地利用节点能量，因此，延长了网络生命期，基本解决了 CPNSS算法效率低、能量不均衡的问题。 参考文献 [1] Tian Di, Georganas N D. A Coverage-preserving Node Scheduling Scheme for Large Wireless Sensor Networks[C]//Proc. of ACM WSNA’02. [S. l.]: ACM Press, 2002. [2] Slijepcevic S, Potkonjak M. Power Efficient Organization of Wireless Sensor Networks[C]//Proc. of IEEE International Conference on Communications. [S. l.]: IEEE Press, 2001. [3] Cheng Xiuzhen. Strong Minimum Energy Topology in Wireless Sensor Networks: NP-Completeness and Heuristics[J]. IEEE Transactions on Mobile Computing, 2003, 2(3): 248-256. [4] Mao Yingchi. A Distributed Energy-efficient Location-independent Coverage Protocol in Wireless Sensor Networks[J]. Journal of Computer Research and Development, 2006, 43(2): 187-195. [5] Tian Di, Georganas N D. A Node Scheduling Scheme for Energy Conservation in Large Wireless Sensor Networks[J]. Wireless Communications and Mobile Computing, 2003, 3(2): 271-290. [6] Cardei M, Du Dingzhu. Improving Wireless Sensor Network Lifetime Through Power Aware Organization[J]. Wireless Networks, 2005, 11(3): 333-340. [7] Ye Fan, Zhong G, Lu Songwu, et al. PEAS: A Robust Energy Conserving Protocol for Long-lived Sensor Networks[C]//Proc. of the Int’l Conf. on Distributed Computing Systems. [S. l.]: IEEE Press, 2003.