网络实体地理位置定位研究

1、网络实体地理位置定位研究第33卷Vo1.33第9期No.9计算机工程ComputerEngineering2007年5月May2007?博士论文?文章编号:10oo一3428(2I7)09_0037o3文献标识码:A网络实体地理位置定位研究刘璜,谢峰,罗军勇(解放军信息工程大学信息工程学院网络工程系,郑州450002)摘要:在建立定位实现模型的基础上,从定位,验证和聚类3个主要步骤分析Intemet实体地理位置定位的核心技术,提出了可行的目标定位算法和验证算法,并借助对定位结果的聚类分析优化结果集.与现有的实体定位技术相比,该模型提出了可信等级的概念,并围绕可信等级在验证和聚类方面进一步修正,

2、对结果的可靠性有较深入的考虑.关健词:地理位置定位;验证;IP地址ResearchonGeographicMappingforInternetEntitiesLIUYan,XIEFeng,LUOJunyong(Dept.ofNetworkEngineering,InstituteofInformationEngineering,PLAInformationEngineeringUniversity,Zhengzhou450002)Abstract|AmodelofgeographicmappingforIntemetentitiesisproposed.Consideringtheunreli

3、ableIntemetinformationandtheexpensivetimeusing,threekeytechniquesarediscussedtOachievebetterresult,whicharemappingIPtOgeolocation,validatingtheoriginalresult,andclusteringtheneighborIP paredwiththepresenttechniques,themodelemphasizesonaccuratesolutionandgivesaconceptoftrustleveltOcombinemanystreamso

4、finformation.Itdoesmuchanalysisonthetrustlevelinvalidatingandclustering.Keywords|Geographicmapping;Validation;IPaddress地理位置信息在现实社会中广泛用于定义法律准则和国家边界,而目前,在互联网上IP地址,自治系统号或主机名称都是逻辑层次上的概念,不包含地理位置信息,并且没有一个权威的数据库可以将网络实体定位到其地理位置.现有可查询的网络信息资源有时候会彼此冲突或不完整,面对如此庞大,复杂且凌乱的数据,需进一步探讨地理位置定位的相关技术.1相关研究针对网络实体地理位置定位,早期使

5、用的方法是通过收集用户信息(如注册到某个网站的个人信息,存储在cookie中的用户信息等)找到与地理位置相关的结果.但这种方法存在很多弊端,如增大用户的操作负担,依赖于上网机器,无法避免虚假信息等.因此,单方面靠某个网站对网络实体地理位置信息的收集存在很大局限,需找到新的方法来解决,目前已有的方法有:(1)DNSLOC方法:利用保存在DNS记录中的地理信息;(2)Whois方法:利用IP地址,域名在Whois服务器中的注册信息;(3)规则主机名解析法:运用traceroute原理,解析路径上规则的主机名,从中分析主机所在的地理位置.基于DNS记录的方法依赖于主机是否支持DNS.LOC,即允许将

6、主机的地理位置记录在DNS记录中,这种扩展功能在RFC1876中定义,但由于其并没有说明使用位置和粒度,很多域名中都不支持该信息,要找到一个使用了DNSLOC记录的域名可能需要查询多次,因此单纯通过该方法获取结点的地理位置只是一种理想的方法,实用性不强.利用Whois服务器的注册信息定位地理位置是目前常用的方法之一.NetGeo21是一个比较成型的工具,可实现从IP地址,域名或AS号到地理位置(经纬度)的定位.但是这种方法存在以下问题:(1)Whois数据库中的信息记录有可能不准确或陈旧或不一致.(2)Whois数据库可能会将分散在不同地区的IP地址统一描述,造成定位结果错误.在tracero

7、ute基础上通过解析规则主机名获取地理位置信息是另一种常用的方法.比较有代表性的开发工具如:GTrace31和VisualRoute2006_4J.GTrace具有对路径信息进行图形化显示和地理位置定位功能;VisualRoute有分布在全球的多个服务器,可从多个服务器对一个IP地址寻径,并图形化显示路径信息.2定位实现模型对网络实体的地理位置定位不仅是一个定位的过程,由于信息来源的不可靠性,需对定位结果进一步验证以排除虚假或过时信息对定位结果的影响,同时允许猜测地理位置的近似值以满足应用的需要.定位思想:信任度决定结果的可靠性,不同定位方法得到的定位结果的可信等级不同,对已得结果给出较高可信

8、等级的描述,通过验证算法判定结果的可靠性,如果能够找到证据证明其不可靠,则降低其信任度.2.1数据集数据集是地理定位实现模型的数据基础,地理定位即是根据特定的需求对数据集的参考和更新过程.数据集包含以下几部分:(1)BGP数据:BGP路径信息由RouteViews51项目提供,BGP路径信息包含路由器连接的网络前缀和AS路径.基金项目:国家"863"计划基金资助项目(2003AA146010)作者筒介:刘琰(1979-),女,助教,博士生,主研方向:网络信息安全和数据挖掘;谢峰,讲师,博士生;罗军勇,副教授收稿日期:20060611E-mail:liuyan_helloya

9、hoo 一37(2)地理组:从3个途径收集部分IP对应地理位置的信息,以(网络地址,网络前缀,地域名称,经度,纬度,可信等级)的形式存储.这3个途径包括:1)部分网站用户信息的收集;2)手工向提供地理位置信息服务的机构提交查询得到的信息;3)开放软件中公开的部分信息.(3)路径信息:在验证阶段保存traceroute的路径信息,以路径结点为单位记录其前驱和后继的网络地址,IT,地理信息,可信等级等.(4)编码信息:地理信息经常以编码形式被嵌入在一些以城市,州,国家名缩写为DNS名的路由器中.对这些路由器名称的分析结果表明,有3种基本类型的编码暗示位置:1)城市编码:许多ISP用无特征的城市编码

10、或州编码定义主机名称,可以给出一些地理信息的线索;2)机场编码:一些ISP以他们所在城市的机场编码为基础命名DNS.由于机场编码是世界范围的,这样的命名习惯可以暗示部分路由器的位置;3)国家编码:国家编码是基于ISO3166中定义的国家代码,国家信息对于判别依靠国家或机场编码定位结果的正确性非常必要.2.2地理位置定位实现的主要阶段地理位置定位需要从以下几个阶段来考虑:定位,验证和聚类.各阶段描述如图1.图1地理定位实现模型和数据漉定位模块根据定位请求,参考数据源已有信息,通过定位算法确定目标的基本位置.在验证阶段,利用traceroute原理和传输延迟判断结果的可靠性,并对不可靠的结果给出可

11、能的猜测,同时更新数据源中地理组信息.在聚类阶段,进一步调整合理的网络地址前缀与地理位置的关系.2.3运行参数在现实情况下,定位结果的准确性受到各方面因素的影响,比如参考信息的不可靠,网络流量变化等,因此提出可信等级,可信阈值和地址前缀利用度3个参数来帮助调整地理位置定位的实现和对结果的评价.可信等级(trustleve1):按等级(1)(6)标识数据源中的已有定位结果的可靠性.可信等级由定位算法中得出结论的具体步骤决定,并受验证算法的影响.等级越高可靠性越高.可信阖值(trustthreshold):在定位模块中决定何种可信等级的结果为可靠结果.本文假定可信阈值为2,则trust_level

12、>2的结果认为是可靠的结果.地址前缀利用度(prefixthreshold):是判定已有结果是否可用的经验值,在定位模块中用于决定何时启用定位算法.比如如果数据源中存在结果(,8,WoburnMAUS,42n29,71w09,3),但通常这仅仅是该地址段的中心机构所在地址,并不能说明地址段中所有主机都位于Woburn.假定定位请求内容是,prefixdegree为l6,表明只有地址前缀大于l6的结果才有效,此时仍需调用定位算法.383定位算法本节将用集合描述数据源中的参考数据,即部分定位结果,并提出一种地理位置定位算法,其基本思想如下:根据对信息来源的

13、可靠性对地理位置定位的各种策略排序,依次调用不同的方法定位目标实体,直到找到地理位置结果.尽管地理位置定位的方法很多,但是每种方法都不能保证其结果的正确性,根据各种方法实现的机制,首先给出数据的可信等级假设.Fl,F2,F3分别代表利用规则主机名解析方法,查询DNSLOC方法和查询Whois服务器方法.假设1FI.trustlevel>F2.trustlevel假设2F2.trustlevel>F3.trustlevel在本算法中,单个网络描述为:二元组C=(N,P);其中:N是网络地址;P是网络地址前缀;单个保存在数据源中的定位结果描述为:五元组M=(C,A,La

14、,Lo,T).其中:C是网络地址段;A是该网络地址段所在的地域名称;La是地域名称的纬度;Lo是地域名称的经度;T是该条信息的可信等级.数据源中的BGP数据用集合Q表示:集合Q:为BGP数据中的网络前缀信息集合,定义如下:Q:nitni是二元组C=(N,prefix)的一个实例数据源中的参考数据用集合P表示:集合P:为已知网络地址前缀的地理组信息集合,定义如下:P:milmi是五元组M=(c,A,La,Lo,T)的一个实例对于每一种方法,地理位置定位由3步完成:(1)找到单个IP地址所在的网络,即根据单个定位请求在集合O中确定其所在的一个大致的地理组(得到五元组M中的C).(2)定位网络地址到

15、其所在的地域名称(得到五元组M中的A),本文用到Fl,F2,F33种方法,并用不同的信任等级标识结果.(3)定位地域名称到其地理中心位置的经纬度(得到五元组M中的La和Lo).经纬度信息可以通过向GettyThesaurusofGeographicNamesOnLinel6等提供地理信息查询的网站提交查询请求得到.算法描述:MLocate(Nni)/ni是定位请求,以IP地址的形式描述if(3miP,且niGmi.C)/定位结果已经存在于地理信息组中,且可信等级>可信阈值if(mi.P>prefixthreshold且mi.T>trustthresho

16、ld)returnmi;if(存在与查询目标相应的主机名)使用方法F1;填充mi的相关信息(mi.T=6)并返回;if(F1失败)(主机名属于某个国家域)fmi.A=国家代码;填充mi的相关信息(mi.T=3)并返回;使用方法F2;改填充mi的相关信息(mi.T=5)并返回;if(F2失败)使用方法F3;填充mi的相关信息(mi.T=4)并返回;)算法基本按照位置信息可靠性降序进行,可信等级高则结果更接近真实,在下一步的验证算法中将参考已有结果的可信等级进一步完善定位结果.4验证算法验证算法验证单个结点的地理位置是否合理,尝试给出建议值并调整结果的可信等级.使用的原理:IP包的传输速度不可能大

17、于光速.光速在真空中是3.0108m/s,在铜线或光纤中速度大约降低到该速度的2/3,即2.3108m/s.实际中使用2.3108m/s足以满足验证的需要.算法思想:参考路径信息,考虑3种情况:(1)如果待验证结点只处于路径的终点,如图2所示.其中:/1RTT=(RTTmrRTTRn_,)/2;/1RTT锕=R一,与mi的直线距离1/2.310);地理路径长度为mi为验证结点,计算ARTT铜和ARTT,如果ARTT<ARTT铜,此时,或者R一.位置错误,或者mi位置错误,或者两结点的地理位置都错了,如果RT>m.T,则修改mi位置为Rni的位置,降低mi的可信等级m

18、.T=1.O/.O."j图2路径验证情况1(2)lJ果待验证结点在路径中有后继结点,如图3所示,如果ARTT1(/1RTT1铜,且ARTT2<ARTT2铜,说明mi的地理结果不正确,如果RT>ARTT3铜(其中ARTT3:ARTT1十ARTT2),选择与mi路径ARTT最小者,更改mi的地理位置为该结点的地理位置,可信等级mi.T=1.R1+图3路径验证情况2(3)对于定位算法没有得到的结点,由于traceroute相邻两跳在地理上一般也相邻,由此猜测mi的地理位置为图3中与mi路径RTT最小者的位置,可信等级mi.T=1.验证算法:MVerify(Mmi

19、,Nni)/mi为待验证的网络结点地理位置,ni为定位请求从本地tracerouten,得到网络路径RI,Rn;/其中Rn=m综合路径信息;定位第ni个结点的地理位置;lffmi没有后继)根据情况1),验证mi,修改miT;Returnml:1Ir(mi有后继)根据情况2),验证mi,修改mi.T;returnmi)if(mi的地理位置为空)根据情况3),得到mi的地理位置,mi.T=1;returnmi;)影响两结点问RTT有4个主要因素:光传播的延迟,传输单元数据所需的时间,网络拥塞和目的结点产生ICMP超时响应时间.在理想情况下,我们希望使用的RTT仅代表传播延迟,但由于数据包在网络中传

20、输的拥塞和处理延迟无法避免,实际得到的RTT上限无法给出,因此验证算法使用traceroute返回的最小RTT值,该值代表了最佳情况的传输延迟.5聚类分析在模型最后一步引入聚类分析模块进一步整理定位结果.引入地理组(GP)的概念:地理上位于同一个地域范围的连续IP地址段.IP地址通常是以地址前缀为尺度分配,通常一段连续的IP地址在地理上也相邻,从BGP数据和Whois数据中可以得到部分以选路为目的的IP地址前缀信息,这些IP地址前缀可作为初始地理组,对于包含IP地址数量较大的地理组,其内部地址存在按区域划分的可能,需进一步细分.聚类思想:将IP地址空间分成小组,一组中所有IP地址可被相关定位.

21、当知道了一组中少数主机的相关位置(假定这些位置大部分是确定的),就可以推演出整组中的位置.对任何一个从BGP数据或Whois数据获取的原始GP,运用已有IP地理位置信息确定它们在其地理位置上是否有效.如果有效,则申明这个GP为地理组.反之,将GP平分为两部分,再次测试各个部分,如此递归,直到子集包含着太少的IP地理位置信息而不能确定可靠的地理组.假设一个ISP的地址空间是/16,其中(/17)是纽约的用户,1/4是达拉斯的用户(/18),1/4是旧金山的用户(/18).假定部分信息显示纽约的5O个I

22、P地址在/17之中,达拉斯的2O个地址在l/18之中,旧金山的10个地址在/18之中.初始时/16被看作是地理组,但该组位置不一致,将组平分为:/17和/17.前者地址前缀是有效的,可作为一个在纽约的地理组.但/17仍然缺乏一致,继续分为/18和/18.聚类分析以IP地址成组分配的现状为基础,通过对地理组的整理完成了组内IP地址的相关定位,作为对网络实体地理位置定位的辅助方法,

23、进一步优化结果集,提高已有结果的利用率.6结语本文在建立定位实现模型的基础上,从定位,验证和聚类3个主要步骤分析网络实体地理位置定位的核心技术.在下一步的工作中,定位结果的可靠性验证仍是研究的重点;另外,针对代理服务器和防火墙对结果的影响,需进一步优化算法的实现,并结合大量的实验数据测试地理位置定位方法在不同网络环境中的实施.(下转第42页)例如,假设物种i的DNA序列SI1,_=5'一ggtctctctggttagaccagatctgagcctgggagctctc一3',这里=40,取的宽度k=4,则该DNA序列经哈希函数映射成为多重关键字集K为:f244,209,68,17

24、,68,17,71,31,125,245,214,91,l10,184,224,130,l1,46,185,228,145,71,30,123,236,176,193,7,31,127,254,251,236,177,196,17,68,构造5阶B树如图2所示.图25阶B树结构外部计数算法思想与内部计数算法思想类似,简要描述如下:B=;/创建一棵空B树/将滑动窗口w.置于序列S【I.L.】起始5'端.j=0;WhileJLkDoBeginm=h(S【+1.+k;IfmBthen/在B树中查找关键字m/Begin插入关键字m,并=1;检查是否分裂节点;如果是则分裂;Endelse相应关键

25、字m的频数,:,+1;j+1End;采用宽度或深度优先遍历B树,输出出现频数集F;4.2算法性能分析构建B树的过程主要涉及关键字的查找,插入和节点分裂;关键字查找又分两步:(1)根据待查找关键字定位节点;(2)在该节点内部进行二分查找.在这些操作中,只有节点定位是需要访问磁盘的,而其它所有操作都是在内存中进行的,故只考虑最费时的节点定位操作的时间复杂度.实际上B树中最多包含L个关键字,根据定义,m阶B树的高度hlog(L+1)/2)+1.则算法最多访问L(1ogLJ(+1)/2)+1)次磁盘,这个和式不会超过=IL(1og,2J(,_+1)/2)+1).4.3外部计数算法改进改善外部计数算法性

26、能的关键是提高磁盘访问的效率,尽可能减少无谓的磁盘访问次数.分析外部计数算法可知,B树是一次性批量插入关键字生成的,不涉及关键字的删除和修改等问题.针对这一特点,提出下面3种改进措施以提高算法效率.(1)溢出思想:Bayer和McCreight提出的溢出思想能够尽可能地避免频繁地分裂节点,从而提高插入效率.(2)采用B树:Knuth在1973年提出的B树是B树的变形】.B树至少利用了每个节点中2/3的可用空间,而不像B树那样只利用了节点一半的空间,使得树的高度降低,查找过程加快.(3)磁盘缓冲:虽然磁盘缓冲策略是解决磁盘扇区频繁读写的有效方法,但其效率取决于磁盘读写的局部性.由于DNA序列的随

27、机性,因此磁盘读写的局部性不一定能满足.但是如果采取分批预读措施,把预读的部分DNA序列映射为关键字序列后存储在数组中再排序,后再批量插入到B树中,从而增加了磁盘读写的局部性,因而能够提高计数算法的效率.当查找或插入算法发出"虚拟读"命令后,仅当需要的页不在内存中时,它才被翻译成真正的读磁盘命令.缓冲区的页替换策略可以采用最近最少使用方案.5结束语由于DNA序列在长期的进化过程中形成了其独特的生命元件之间复杂的相互作用关系以及DNA序列数据量的异常庞大,致使生物信息学中的许多问题都是对目前计算机处理能力的挑战,需要针对生物序列的特点设计性能卓越的算法来解决.本文设计并实现了

28、k一长DNA子序列在DNA全序列中出现频数的内部和外部计数算法,较好地解决了k一长DNA子序列出现频数的计数问题.对这个问题的研究能解决许多生物信息学问题,为生物学家分析DNA子序列分布,研究序列进化提供重要帮助.我们利用这个算法研究了k一长DNA子序列的频数分布,k一长DNA子序列的最大出现频数与k值的关系等生物信息学问题,发现了一些新的规律.参考文献1HaoBailin.FractalsfromGenOmesExactSolutionsofaBiologyinspiredProblemZ.2000. :/power.itp.ac /hao/scitlist.htm.2HaoBailin,LeeHC,ZhangShuyu.FractalsRelatedtoLongDNASequencesandCompleteGenomesZ2000. :/r_,ower.itp.ac /hao/scitlist.htm.3FerraginaP-GrossiR.TheStringBtre