（计算机软件与理论专业论文）网络时间协议自动配置机制及相关问题的研究和实现.pdf

摘要计算机时钟的准确性对于大多数网络操作和应用都非常重要。n t p ( n e t w o r kt i m ep r o t o c 0 1 ) 协议是现今应用最为广泛的一种分布式网络时间同步协议，它主要用于网络中计算机设备的时间同步，保证时间信息的传播精度和有效性。但由于当前的n t p 协议缺乏灵活有效的自动配置机制，这使得基于n t p 构建的同步网的稳定性和扩展性都难令人满意。本文致力于设计一个同步网目动配置协议以实现n t p 同步网的自组织。同步源发现是自动配置的关键，由于n t i ，同步网的工作模式类似于共享资源的对等网络，如果将时间同步服务抽象成资源的话，我们就可以使用对等网中的资源发现技术来实现同步源发现。以邻居的层级信息作为同步源的定位信息、以b x p a n d i n gr i n g作为搜索范围控制机制，本文基于资源定位信息的搜索算法的框架实现了同步源发现算法，该算法在提高搜索效率的同时也大大减小了搜索的开销。此外，本文提出了种以同步网的性能优化为目标同步源选择算法，通过度量同步源以及节点自身的性能和工作方式，令好节点分布到同步网上层以提供稳定的时间同步服务给其它节点，从而实现同步网的性能优化。在给出同步网自动配置i 办议的实现的同时，本文还进行了一系列的仿真实验，并对实验结果进行分析，验证了同步网自动配置协议的性能、开销以及由该协议实现的同步网的稳定性。关键词时间同步；网络时间忉、议；自动配置；资源发现a b s t r a c tt h ea c c u r a c yo fc o m p u t e r sc l o c kisv e r yi m p o r t a n tt ot h em o s tn e t w o r ko p e r a t i o na n da p p l i c a t i o n s n t p ( n e t w o r kt i m ep r o t o c o i ) i sad i s t r i b u t e dt i m e k e e p i n gp r o t o c 0 1w h i c hh a sb e e nu s e dw i d e l y i ti su s e df o r t h es y n c h r o n i z a t i o no fc o m p u t e r s c l o c ki nn e t w o r ka n de n s u r i n gt h a tt i m e k e e p i n gm e s s a g e sa r et r a n s m i t t e dp r e c i s e l ya n de f f i c i e n t l y b e c a u s eo fl a c k i n sf l e x i b l ea n de f f i c l e n ta u t o c o n f i g u r a t i o nm e c h a n i s m ，h o w e v e r ，t h es t a b i l i t ya n ds c a l a b i l i t yo ft i m e k e e p i n gn e t w o r k sw h i c h b u i i tu p o nn t pa r en o ts a t i s f y i n g r h i sp a p e rc o n c e n t r a t e so nd e s i g n i n ga na u t o c o n f i g u r a t i o np r o t o c o lt oi m p l e m e n tt h ea u t o n o m yo ft i m e k e e p i n gn e t w o r k s y n e h r o n i z a t i o n s o u r c ed is c o v e r yi st h em o s ti m p o r t a n tp a r to fa u t o c o n f i g u r a t i o n b e c a u s et h ew o r k i n g so ft i m e k e e p i n gn e t w o r ki ss i m i l a rt op e e r t o p e e rn e t w o r k s ，w ec a nm a k eu s eo fr e s o u r c ed i s c o v e r yt e c h n e l o g yt oi m p l e m e n ts y n e h r o n i z a t i o n s o u r c ed i s c o v e r yi nt i m e k e e p i n gn e t w o r ki fw er e g a r dt h es y n c h r o n i z a t i o n s o u r c ea sr e s o u r c ei np e e r t o p e e rn e t w o r kw i t hr e i g h b o r ss t r a t u mb e i n gt h eo r i e n t a t i o ni n f o r m a t i o nf o rs y n c h r o n i z a t i o n s o u r c e ，a n da s i n ge x p a n d i n gr i n gf o rc o n t r 0 1 1 i n gt h es e a r c hr a d i o s ，w ed e s i g nas y n c h r e n i z a t i o n s o u r c ed is c o v e r ya l g o r i t h mo nt h eb a s i so fi n f o r m e d s e a r c ha l g o r i t h mi nt h i sp a p e r t h ea l g o r i t h mn o to n l yi n c r e a s e st h es p e e do fs e a r c hb u ta ls or e d u c e si t sc o s t i na d d i t i o n ，w ea l s od e s i g nas y n c h r o n i z a t i o n s o u r c es e l e c t i o na l g e r i t h ma i m i n ga to p t i m i z i n gt h ep e r f o r m a n c eo ft i m e k e e p i n gn e t w o r k m a k i n gg o o dn o d e sd i s t r i b u t eo nt h et o po ft i m e k e e p i n gn e t w o r kt op r o v i d es t e a d yt i m e k e e p i n gs e r v i c e st oo t h e rn o d e sv i am e a s u r i n ga 1 1n o d e s p e r f o r m a n c e sa n di tsw o r k i n g s ，w ec a na c h i e v et h eg o a lo fo p t i m i z i n gt h ep e r f o r m a n c eo ft j m e k e e p i n gn e t w o r k s i nt h i sp a p e r ，w ep r e y i d ea ni m p l e m e n t a t i o no ft h ea u t o c o n f i g u r a t i o np r o t o c 0 1 t h e n ，w ep e r f o r mas e r i e so fs i m u l a t e dt e s t sa n da n a l y z et h er e s u l to ft e s t st ov e r i f yt h ea u t o c o n f i g u r a t i o np r o t o c o l sp e z f o r m a n c ea n dc o s ta sw e l la st h es t a b i l i t yo ft i m e k e e p i n gn e t w o r k sb u i l tu p o nt h a tp r o t o c o k e y w o r d st i m e k e e p i n g ；n t p ；a u t o c o n f i g u r a t i o n ；r e s o u r c ed i s c o v e r y独创性声明本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示了谢意。签名： 蠹盛i 惑日期：兰丝g ：，鲁关于论文使用授权的说明本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。( 保密的论文在解密后应遵守此规定)签名： 蚕趔剑导师签名_ 孟圣暨，日期：竺竺丝莎f第1 章绪论随着计算机网络的迅猛发展，网络应用已经非常普遍，很多领域的网络系统，如金融业、广电业、交通业等需要在大范围内保持计算机的时间同步和时间准确。但是目前计算机网络中各主机和服务器等网络设备中存在一个比较严重的问题，即它们的时间其本上处于无序状态。网络时代的今天，计算机的时间同步问题已成为我们必须去面对并解决的问题。为了避免产生本机的时间错误，可以从网络上获取时间，比如使用命令r d a t e ，这样系统时钟可与公共源同步。但是一旦这一公共时r 司源出现差错，就会产生连锁反应，与其同步的所有计算机的时间因此全都错误。为了实现时间信息的传播，并保证传播精度，就需要分布式网络时间协议。这些协议能够保证时间同步网元设备正确读取服务器的时间，将读数传送给一个或更多的客户，并且根据需要调整每个客户的时间。将通信网上各种通信设备或计算机堤各的时间信息( 年月日时分秒) 基于u t c ( 协调世界时) 的时间偏差限定在足够小的范围内( 如1 0 0 m s ) ，这种同步过程叫做时r a j 同步。一般来说，时间同步应用最广泛的是在i n t e r n e 上的计算机“。计算机时钟用于记录事件的时间信息，如e - m a i l 信息、文件创建和访问时间、数据库处理时间等。时钟还被用于控制备份的操作、为设计自动构造编译器检查文件是否变动过以及其他应用。如果计算机时钟不精确，那么这些应用中很多将无法正常工作。对时r 司敏感的计算机系统，如金融业界服务器、e d i ( 电子数据交换) 、大型分布式商业数据库、航天航空控制计算机等，更需要高精度的时间信息。交通运输业的时间显示系统，如地铁时刻表显示系统、机场时刻表显示系统，如果偏差较大，可能会影响旅客的旅行。此外，网管系统的告警和f 志同样需要准确记录事件和告警的准确时间，以便进行故障和性能分析。譬如，当网管中心采用多点日志记录时，如果网络各个节点时间不同步，将造成日志记录的混乱。因此，有必要建立准确、稳定并且健壮的时间同步协议来构建同步网，同步网络中的计算机时钟。同时，解决n t p 协议中的自动配置问题，提高协议实现系统的执行精度，提高相应系统的安全性也是非常重要的。本课题来源于国家某大型专用计算机网络的同步网构建项目。1 1 国内外相关研究现状及分析1 1 1 国外研究现状为了解决网络中机器时钟同步的问题，出现了一些同步协议，这些协议包括：n t p ( n e t w o r kt i m ep r o t o c 0 1 ) “，d t s s ( d i g i t a lt i m es y n c h r 。n i z a t i o ns e r v i c e )”1 等。其中，d t s s 协议主要适用于局域网或分布式系统中各个计算机的时间同步，而n t p 协议则更适用于同步像因特网这样的大型网络中计算机的时间。网络时间协议( n t p ) 是特拉华州大学计算机系的d a v e l m i l i s 教授于1 9 8 5 年所设计的用于同步互联网中各主机时钟的一个基于u d p 之上的协议“”“7 “，其目的是在无序的全球因特网的环境下使得运行该协议的主机能获得精确和稳定的时间源用以同步，从而获得较高的时钟精度。由m i l l s 教授领导的科研小组，经过近二十年对n t p 协议的不断研究和改善，至今已经发布了3 个正式版本。现在的版本3 “3 协议在广域网中同步时钟的精度可达到几百毫秒以内，而在局域网中，同步精度则可达到数毫秒。“”1 。随着计算机网络的发展，n t p 仂、议逐渐成为t c p i p 协议家族的一员。目前i n t e r n e t 网上安装了n t p 软件的时间服务器向其客户端计算机提供时间服务基准，一级时间服务器几乎都是从o p $ 接收机获得u t c 的基准时间信息( 采用r s- - 2 3 2 接口) ，低级别的时间服务器通过基于t c p i p 的网路从上级服务器获得u t c时间。所有需要时间的客户端计算机通过安装n t p 的客户端程序，从指定的时间服务器上获得u t c 时间信息，用于校准自身的当前时间信息。1 9 9 8 年，i n t e r n e t中n t p 协议就拥有超过2 3 0 个通过：无线、卫星和m o d e m 同步的一级时间服务器，以及远远超过i 0 0 ，0 0 0 个二级服务器和客户机。另外，在政府，社团和机构中还有数以千计的专网。n t p 协议的体系结构、协议和算法，经过近2 0 年的研究到今天，已发展到了n t p 版本3 ，有着适用于u n i x 、v l v l $ 和w i n d o w s 操作系统的软件实现，现在正在进行版本4 的研究。以前的研究主要集中于协议和支持算法的准确性和可靠性上，并取得了巨大的成果。使用n t p 协议所构建的同步网是层次性结构“1 ，作为时间服务器的计算机处于高层，而用时间服务器作为同步源的计算机则处于低层。而在n t p 版本3 的现有实现中，没有提供同步源的发现的机制“”3 。也就是说，要想实现n t p 网络的多层级配置，无法靠程序自动完成，而必须由管理员事先进行手工配置，而且对每台机器都要进行配置。通过这种手段实现的同步网的拓扑是静态的，所以基于其上的时钟同步操作必然会受到网络环境变化的制约和影响。当某机器时钟源弟l 苹绪诧发生异常情况时，有可能会导致同步于它的单个计算机甚或整个子网都无法正常工作。这与n t p 协议所提出的实现一个稳定、健壮的时间服务的设计目标是不相符的。现在，m i l l s 的研究组正致力于n t p 协议中的自动配置机制的实现“”1 ，就是让网络中的计算机自动找到同步源，进行动态配置。此外，该工作组也致力于对协议安全性的研究，在协议中加入了加密，认证的机制“2 “1 。1 i 2 国内研究现状国内对同步技术的研究迄今为止也取得了不少成果”“7 “”3 。我国的氢钟制造技术已位于世界先进水平。我国已经研制成功第一代导航卫星系统“北斗一号”，其定位方法采用双程测距；现正在研究发展第二代导航卫星系统，其定位方法改用单程测距，用户机直接接收卫星辐射的单程测距信号自己定位，测距精度要由星载高稳定度的原子钟来保证。此外，国内对时间同步的研究则多集中于分布式系统之上”。对于n t p 协议，除北京邮电大学、西安交通大学等少数几个科研单位对其进行过一定的研究外，国内现在主要是对该协议的工程应用“2 。”。国内各电信企业目前纷纷构建自己的数字同步网，华为公司在这项技术上较为领先。”，它已经为中国电信，联通等多个计算机网络构建同步网，使用的同步协议均为n t p协议。此外：北京邮电大学也已经运用n t p 协议组建了同步网，并向外部机器提供时间同步服务。国内的一些大网站，比如万网等，也提供n t p 时间服务。1 2 网络时间协议简介1 2 in t p 的基本模型n t p 协议使用层次式时间分布模型“1 ，并通过使用这种模型提供了同步子网的无限可扩展性。顶层是s t r a t u ml 时钟，它们是直接与真实的时钟源( 通常为g p s 或w w v b 接收机) 同步的计算机，我们称之为主时间服务器。网络中其他以主时间服务其作为时间源的计算机则为s t r a t u m2 层时钟，成为二级时间服务器。以此类推，从而构成了n t p 同步网的层次结构。每个位于同步网中的主机只能与比自己层级更小或与自己层级相同的时间源同步。在正常情形下，由主时间服务器、二级的服务器组成的同步子网形成了一种多层次主从配置( h i e r a r c h i c a l m a s t e r s l a v e ) ，在该配置中，主服务器位于根部，而随着向叶子的延伸，时钟准确度逐渐降低。其工作方式如图卜l 所示。北京工业大学硕士学位论文图l 一1n t p 的工作方式f i g u r e 】一1w o r k i n g so fn t pn t p 协议最典型的操作模式是由数个直接连结到标准时钟源的专用服务器作为主时间服务器( s t r a t u m1 ) 运行，这些主时间服务器之间互为冗余，并交叉检查时钟以减轻由于设备或传播失败引起的错误。一些本地网的主机或网关，则充当第二级时间服务器( s t r a t u m2 ) ，运行n t p 与一个或多个主时间服务器交互a为了减少协议开销，第二级的服务器经由n t p 传播时间信息到剩余的本地主机上。出于对可靠性的要求，被选择的主机也可配备不太精确也不太昂贵的无线电钟作为备份，在它与主或第二级的服务器的通讯路径失败的情况下使用。n t p 的同步方式有三种：客户机服务器方式，对等方式和广播方式”。一般在不同层级之间的同步都采用客户机服务器方式( 这也是最常用的同步方式) ，层级高的客户机向层级低的一个或多个服务器发送查询时间请求包，被请求的主机则作为服务器将自己的列词信息发回给客户机，客户机接收并处理这些应答包，然后选取精度较高的时间信息来更新本地时钟。而对等方式则一般用于同层级的机器之间相互发送n t p 时间信息。相互对等的机器可以相互同步，这样则更增强了同步网的稳定性和健壮性，使得从根部向下的同步的误差不会迅速地沿子树扩散。广播方式则是指层级低的机器向网络中广播本地的时间信息，而层级高的主机则接收并处理该时间包，用以修正自己的本地时钟。但是由于在广播方式中，n t p 包的传输时延无法估算，故该方式只能用于对时钟精度要求不是很高的子网中。1 z 2n t p 的标准时间源n t p 将互联网中的主机时钟同步到世界标准时间，因此，物理时间源的选取第1 苹绪论直接影响着整个网络中时钟同步效果的好坏。在对精度要求严格，对稳定性和可靠性也有特殊要求的网络中，使用像原子钟这样的昂贵设备作为标准时钟源是较好的做法；但在一般的网络中，使用美国全球卫星定位系统( o p s ) 所提供的时间信号作为时钟源3 ，则是一种较好的选择。使用g p s 接收器来接收时钟信号，并传给主时间服务器，其精度可达到纳秒级，且g p s 接收器也比原子钟经济的多。1 2 3n t p 协议的当前状况和需要完善的地方当前使用的n t p 协议仍然存在着许多不足”。“，尤其是在协议的健壮性和可靠性上。使用n t p 协议所构建的同步网是层次性结构，作为时间服务器的计算机处于高层，而用时间服务器作为时间源的计算机则处于低层。可是这种层次性并不是动态形成的，而是要管理人员预先进行手工配置，n t p 本身则不具备自动配置的能力。此外，n t p 是构建在t c p i p 之上的一层应用，很容易受到伪装的n t p 消息的攻击( 比如用错误的时间信息来欺骗某计算机) 。这些都是必须要解决的问题，它直接关系到同步网中时间同步操作的成败。只有这些问题解决了，n t p 同步网的健壮性和可靠性才能得以保证，它才能被真正广泛应用到各个政府、企业、金融机构等重要领域的计算机网络中，发挥出重要的作用。目前，m i l i s 的研究组正在致力于n t p 协议中的自动配置机制的实现，他们希望通过使用组播来发现周围的主机”6 “2 7 2 “。因此，同步网中各主机，路由器对组播是否支持就成了问题的关键，也成了一个瓶颈。此外，该工作组同时也致力于对协议安全性的研究，在协议中加入了加密，认证的机制。”。1 3 对等网技术简介p 2 p 是p e e rt op e e r 的缩写，p e e r 在英语里有“地位、能力同等者”、“同事”和“伙伴”等意义。p 2 p 就是“伙伴对伙伴”的意思，技术上称为对等联网【2 叫01 3 1 对等网技术的主要应用p 2 p 技术引导网络计算模式从集中式向分散式偏移，也就是说网络应用的核心从中央服务器向网络边缘的终端设备扩散。对等网的应用主要体现在如下几个方面“3 ”2 ”1 ：( 1 ) 对等计算对等计算研究的是如何充分地把网络中多台计算机暂时不用的计算能力结合起来，使用积累的能力执行超级计算机的任务。就其本质而言，对等计算就是网络上c p u 资源的共享。应用实例有：d i s t r i b u t e n e t 和s e t i h o m e北京工业大学硕士学位论文等。( 2 ) 协同工作协同工作是指多个用户之间利用网络中的协同计算平台来共同完成某项任务，共享信息资源等。采用p 2 p 技术，可以去掉目前协同工作系统中的中央服务器，参与协同工作的计算机直接建立连接。应用实例有：i n t e l 的n e t b a t c h 软件，上海鹰腾公司的p a s pe s c h o o l 等。( 3 ) 搜索引擎p 2 p 技术使用户能够深度搜索文档，而且无需通过w e b 服务器，也可以不受信息文档格式和宿主设备的限制，达到传统目录式搜索引擎( 只能搜索到2 0 一3 0 的网络资源) 无可比拟的深度( 理论上将包括网络上的所有开放的信息资源) 。应用实例有：i n f r a s e a r c h 、p o i n t e r a 等。( 4 ) 文件交换传统的w e b 方式中，要实现文件交换需要w e b 服务器的大力参与，通过将文件上传到某个特定的网站，用户再到该网站搜索需要的文件，然后下载。这就要求w e b 服务器能够对大量用户的访问提供有效的服务，因而经常成为w e b 方式这类应用的瓶颈之一。而p 2 p 技术可以使用户利用基于p 2 p 网络协议的客户端软件脱离服务器，直接从含有所需文件的对等节点机下载该文件。应用实例有n a p s t e r “”、g n u t e l l a 3 、l n r e e n e t 嵋2 等。此外，还有诸如边缘服务、智能代理、实时通信技术和广域网络存储系统等其他几种应用方式。1 3 2 对等网资源发现算法简介p 2 p 系统中，一个用户要共享另一个用户计算机上的资源，不论是文件、存储空间或是计算资源，一个关键的问题是要找到资源所在的目的主机，因此，资源发现是很多p 2 p 系统的核心。从目前的研究现状来看，以下几种资源发现算法较为常见啪m 4 0 1 “：( 1 ) 集中索引算法以n a p s t e i “”系统为代表。在n a p s t e r 系统中，用户都与一个中央服务器相连接，中央服务器上保存了共享文件的索引。由中央服务器对收到的用户请求进行匹配查找，直到找到保存了所需文件的目的用户。然后，由发起请求的用户与目的用户直接进行文件交换。( 2 ) 洪水消息算法代表系统为g n u t e l l a “。每一个用户消息都将被广播给与该用户直接相连的若干其他用户，这些用户收到消息后，也同样地将消息广播给各自连接的用户，以此类推，直到请求被应答，消息的t t l 值减少为0 或超过了最大的广播次数( 通常在5 p 9 之间) 。( 3 ) 文件路由算法代表系统为f r e e n e t 5 “。算法的特点是采用基于哈希函数的映射。系统中的每一个用户都有一个随机的i d 序列号：系统中的每一个文件也有一个i d 序列号，这个序列号是根据文件的内容和他的名字，经过哈希函数映弟1 荤绪论射得来的。文件发布时，每一个用户都把文件转发到拥有与文件的i d 最相近的i d 值的用户上去，直到最接近文件i d 的用户就是该用户本身。转发过程中每经过的一个用户都将保持该文件的副本。索取文件时，每个用户都将请求消息转发给一个拥有与所需文件i d 最相近的i d 的用户，直到文件或文件的一个拷贝被发现为止。我们将在第二章对对等网资源发现算法进行更为详细的讨论。1 3 主要研究内容及研究方案本课题的主要研究内容就是探索在基于n t p 协议的时间同步网中如何实现同步网的自组织机制。我们总体的解决办法是通过在n t p 协议的基础上添加我们自己所设计的同步网自动配置协议，与n t p 协同工作，从而构建出具有自组织能力的时间同步网。实现同步源自动配置的关键在于能够在同步网中自动发现同步源。时间同步可以看成是由同步源提供给被同步节点的一种服务，在n t p 同步网中，一个节点既接受同步源节点提供的时间同步服务，同时它也可以给其它节点提供时间同步服务，这种结构类似于对等网。如果我们把时间同步服务也抽象成一种资源的话，那么同步源发现也可以看成是对等网中的资源发现，我们可以利用对等网的资源发现技术来实现时间同步网中的同步源发现。”。资源发现算法的优劣主要体现在搜索效率和搜索开销上。搜索效率高、开销低是我们同步源发现算法设计的总体目标。对于自组织同步网来说，网络性能会影响时间同步的整体效果，因此我们针对如何优化同步网性能这一问题也进行了研究，并提出了一些解决的方法。我们优化同步网性能的目标是：( 1 ) 区分结点的能力( 质量) ，使“好“节点在自组织过程中获得较高的同步精度，同时作为主要的同步源；( 2 ) 均衡n t p 服务负荷，控制节点度数，防止个别节点度数过高，影响同步网的健壮性以及占用单个节点过多的计算资源同步源自动配置协议主要有三部分。“：同步源监测、同步源发现、同步源选择。同步源监测模块负责检查同步源的运行状况，当发现同步源失效时就启动同步源发现过程；同步源发现模块负责搜索同步网中的符合条件的正常同步源，并将搜索的结果传递给同步源选择模块：同步源选择模块从找到的同步源中找到最好的一个或多个同步源作为本节点的同步源，到此一个同步源自动配置过程完成。同步源自动配置协议的工作过程如图卜2 所示。因为n t p 时间同步是周期性操作，被同步节点会定期从同步源那里获取时间图卜2 同步源自动配置协议工作过程f i g u r e1 2w o r k i n g so fa u t o c o n f l g u r a t i o np r o t o c o l信息来同步自己的时钟，所以被同步节点能够自动发现同步源是否有效。因此，我们主要的工作就是结合前面所提到的设计目标来完成同步源发现和同步源选择模块的设计。在本文中我们将进行同步网自动配置协议的设计及实现，并通过仿真实验来验证我们所设计的自动配置协议的性能。第2 章同步源发现算法设计2 1 概述第2 章同步源发现算法设计所谓同步源，是指同步网中能够提供时间同步服务的节点，我们也可以称之为时间源。在以后的讨论中，我们将视上下文具体情况来使用这两个词( 虽然它们指代的是同一对象，但在不同的上下文中分别使用它们会使论述更为直观贴切) 。时间同步可以是长时间的、连续的、以获得高精度的同步效果为目的的操作过程，也可以是短期的、快速的对时间同步精度要求不高的操作过程。每个节点可以在任意时刻加入或离开同步网。对于以短期同步操作为目的的节点，它的同步过程包括加入同步网、修正本地时钟、退出同步网三个步骤，我们称这样的节点为临时节点。而以长期同步为目的的节点，其同步过程包括加入同步网、粗修正本地时钟、时钟修正求精等，同时该节点还可以向其它节点提供时间同步服务，我们称这样的节点为固定节点。对于固定节点来说，当它以非正常状态退出同步网时( 可能是由于同步源失效，或者是网路故障等原因) ，它会重新启动自动配置机制以重新加入同步网。同步源发现是所有节点加入同步网过程的第一步，同时它也是同步网自组织过程中最为重要的步骤之一，它的主要任务就是搜索网络中可达的时间源服务器，向其发送时间信息请求，以期获得符合自身要求的时间同步服务。把时间同步服务抽象成一种资源，我们可以使用对等网的资源发现技术来实现在时间同步网中的同步源发现。在第一章里我们已经对当前对等网技术中所使用的主要资源发现算法有过粗略的介绍，本章将对这些算法进行更进一步的分析，通过比较这些算法各自的优缺点、适用范围、局限性以及影响这些算法性能的主要因素，从而提出适用于自组织时间同步网的同步源发现算法。2 2 对等网的资源发现算法对等网的资源发现算法按照其工作方式可分为集中式搜索、非集中式搜索两类。下面将依次对这两类算法进行分析和讨论。2 2 1 集中式资源发现算法集中式搜索算法最先出现于一个取得了巨大商业成功的对等网应用n a p s t e r“1 中。n a p s t e r 是- - 个用于互联网上的用户们相互交换m p 3 音频文件的软件平台，北京工业大学硕士学位论文它使得人们能够从接入互联网的任意主机上下载其所需的音频文件( 前提是该主机同意共享这些文件) 。每台主机既可以从其它的主机下载文件，也能够提供文件供他人下载。图2 1n a p s t e r 的 _ 作方式f i g u r e2 - 1w o r k i n g so f n a p s t c rn a p s t e r 的工作方式如图2 1 所示。n a p s t e r 提供一台或数台中心目录服务器。当一个节点想要登录到n a p s t e r网络中时，该节点首先要向中心目录服务器注册，注册内容包括自身的网络地址、以及提供共享的文件的目录列表。中心目录服务器保存了所有在线节点的索引以及每个节点的共享文件目录列表，每当有新的节点登录或现有的节点离开时，目录服务器都会更新自己的目录列表。当n a p s t e r 中的某个节点需要下载文件时，他向目录服务器提交查询请求，该请求只说明需要何种资源。服务器在自己的目录列表中查询能够提供该资源的在线节点的地址信息，并将找到的节点列表返回给请求者。请求者可以从返回的节点列表中任意选择一个或数个节点，与其建立直接的会话连接，从而下载自己所需要的文件。从上述的n a p s t e r 工作方式中我们可以看到，目录服务器并不存储和传送文件资源，它只提供对资源位置的查询服务，文件实际的传送工作直接在n a p s t e r中的各个节点之间进行。也就是说，在n a p s t e r 中，文件交换采用的是p e e r t o p e e r ( 对等) 方式，而资源的搜索( 发现) 采用的却是c l i e n t s e r v e r第2 章同步源发现算法设计( 客户机朋匣务器) 方式，该方式需要中心服务器来完成维护资源信息、处理查询请求和向客户端返回查询结果等工作。显而易见，n a p s t e r 的资源发现机制在继承了c l i e n t s e r v e r 模式的优点的同时，也不可避免的继承了其固有的缺陷。使用该资源发现机制能够获得很高的效率。请求资源的节点只需向目录服务器发送一条请求就可以定位所要的资源；共享资源的节点也只需在登录时向目录服务器发送一次自己的资源信息就可以达到其资源发布的目的。这使得网络中的节点无需进行点对点的查询，极大地提高了资源发现的效率，同时也使节点的负担大为减轻。集中式资源发现机制的缺点也很明显，当大量节点同时发送查询请求时，目录服务器的处理能力就成为了瓶颈。目录照务器不光要独立的处理各个节点所发出的资源查询请求，同时还要不断地维护和更新节点和资源列表，当它的处理能力无法满足当前状况下的需求时，整个网络的运行会随着服务器的变慢而变的十分低效，甚至瘫痪。从网络安全性的角度来考虑，该机制的缺陷就表现得更为明显。整个网络的资源定位都完全依赖于中心目录服务器，如果目录服务器遭到恶意的攻击，比如说拒绝服务攻击或者其它形式的阻断攻击等，此时即使其他所有节点都处于正常状态，但由于这些节点无法再定位资源的位置，从而也就不能进行相互间的交互，整个网络将陷入瘫痪状态，无法在继续工作。此外，其它类型的恶意攻击还可能会导致更为严重的结果。由于网络所有的节点的地址信息和资源信息都存储在目录服务器上，攻击者可能会篡改这些信息，使得所有的资源地址都指向攻击者所指定的节点，当其他节点从该节点下载文件时，它们得到的可能并不是想要的东西，而是病毒、木马或其他的有害信息，从而导致网络中的节点都受到了攻击。还有很多的方式来威胁这样一个网络的安全，而这些威胁就来自于集中式目录服务器的使用。从以上的讨论中，我们可以看到，使用中心目录服务器的资源发现机制，在中心服务器正常工作的前提下，资源发现的效率很高；但是在实际情况中，由于受到这种集中式工作方式国有缺陷的影响，其灵活性、安全性和可扩展性都不理想。因而，在n a p s t e r 之后的对等网应用中，这种机制很少被采用。2 2 2 非集中式资源发现算法非集中式资源发现算法，简单来说，就是利用周围的邻居节点来转发资源请求，通过这种扩散请求的方式来搜索所要的资源。根据扩散资源请求的方式的不同，当前已有的非集中式资源发现算法大致可北京 = 业大学硕士学位论文划分成四类：( 1 ) 洪水消息算法( f i o o d in gr e q u e s t s ) 每一个节点的资源请求都将被广播给与该节点直接相连的若干其他节点( 邻居节点) ，这些节点收到请求消息后，也同样地将该消息广播给各自连接的节点，以此类推，直到请求被应答，消息的t t l 值( 生存期) 减少为0 或超过了最大的广播次数( 通常在5 和9 之间) 。应用该算法的代表性系统为o n u t e l l a “。( 2 ) 随机选路转发算法( r a n d o mw aik )与洪水( f l o o d i n g ) 算法稍有不同，当一个节点收到资源请求消息后，不是向所有的直接相连的节点转发，只是随机的向若干个节点转发该消息，该算法也被称为k - r a n d o mw a l k ，其中k 是指转发的节点个数，它可以是一个固定值，也可以是一个随机值( 但通常使用固定值) 。g n u t e l l a 系统经过的改进的转发算法( m o d i f i e d b f s “”) 就使用了随机选路转发。( 3 ) 基于资源定位信息的搜索算法( in f or m e ds e a r c h ) ”2 1 资源的定位信息，可以是资源的确定的位置，也可以是通过某条连接转发请求能够成功搜索的资源的概率，还可以是某个连接的节点的转发范围的大小等等。可以看到，定位信息是任何能够提高搜索成功率的启发信息。使用带定位信息的转发算法，可以有效地提高资源的搜索效率，同时也减少了冗余的开销，节约了网络带宽。由于定位信息的形式多种多样，所以这样的算法有很多。其代表算法有a p s ( a d a p t i v ep r o b a b i l i s t i cs e a r c h ) 、i n t e l l i g e n t b f s 4 ”、l i ( l o c a li n d i c e s ) 4 ”、g i a 、r i ( r o u t i n gi n d i c e s ) 侧、d r l p ( d i s t r i b u t e dr e s o u r c el o c a t i o np r o t o c 0 1 ) ”o 。、g s ( g n u t e l l aw i t hs h o r t c u t s ) ”“等等。( 4 ) 文件路由转发算法( d o c u m e n tr o u tin g ) 该算法的特点是采用基于哈希函数的映射。系统中的每一个节点都有一个随机的i d 序列号：系统中的每一种资源( 比如文件) 也有一个i d 序列号，这个序列号是根据资源的内容和它的名字，经过哈希函数映射得来的。资源发布时，每一个用户都把资源转发到拥有与资源的工d 最相近的i d 值的节点上去，直到最接近资源i d 的节点就是该节点本身。转发过程中每经过的一个节点都将保持该资源的副本。搜索资源时，每个节点都将请求消息转发给一个拥有与所需资源i d 最相近的i d 的节点，直到该资源或资源的一个拷贝被发现为止。应用该算法的代表性系统为f r e e n e t “。t a p e s t r y 。，p a s t r y ，c h o r d5 ，c a n ”也都是采用这种方法的p 2 p 系统。使用非集中式算法来进行资源发现，将不再依赖于集中式的结构，它是一种分布式的搜索结构，每一次的资源搜索过程都是网络中多个节点协同工作的过程，“单点瓶颈”的问题在这里不会出现。2 2 2 1 洪水消息算法( f 】o o d in gr e q u e s t s ) f o o d i n g 算法最初被应用于共享文件的p 2 p 系统g n u t e l l a “8 中。第2 章同步源发现算法设计一节点间的逻辑连接转发资源请求图2 - 2f l o o d i n g 的工作方式f i g u r e2 - 2w o r k i n g so ff l o o d i n g基于f l o o d i n g 算法的资源搜索方式如图2 2 所示。在这样的网络中，每个节点都保存有周围与自己直接相连接的节点( 邻居)的地址信息。当一个节点想要从网络中搜索资源时，它会向周围所有与自己有直接连接的邻居发送资源搜索请求。接收到资源请求的节点首先会检查自己是否拥有该资源，如果有，就发送应答；如果没有，则向其所有的邻居转发资源搜索请求。于是，对等网一个节点的资源请求就这样像洪水一样被扩散转发出去，直到找到所需的资源或所有资源请求消息的生存期t t l 值( t i m e t o l i v e ) 递减到零为止( 当资源请求每被转发一次，也就是一跳，i t l 的值会减一) 。f l o o d i n g 和r a n d o mw a l k 算法都适用于对被请求资源的位置的信息量非常少或根本就没有资源位置信息的对等网搜索中。在这样的网络中，每个节点都不知道资源的位置信息( 拥有该资源的节点除外) ，因此在转发资源搜索请求的过程中，只能是盲目的向周围转发，至于搜索的效果，则取决于网络具体的拓扑结构和被请求资源的分布情况。如果被请求的资源所在的节点在搜索半径t t l 之内，使用f l o o d i n g 这种类似于广播方式的搜索算法将很快就能找到所需要的资源。同时，这种算法的实现也是非常简单的。f l o o d i n g 使用t t l 来控制一个资源搜索请求被传播的距离( 跳数h o p ) 。但是对于t t l 的值的选择并不是一件简单的事情。如果t t l 过大，会对网络产生不必要的过重的负载：但如果t t l 太小，即使某个资源就在网络中，可能也无法找到。此外，使用f 1 0 0 d i n g 会引入大量的冗余请求消息的拷贝。这里的冗余请求消息拷贝指的是一个节点收到并处理了多个不同邻居节点转发来的资源请求消息，而这些消息实际上则来自于一个相同的源请求节点。特别是在连通度较高的北京 业大学硕士学位论文网络中，这种现象就更为突出。冗余请求消息拷贝是纯粹的无效载荷，它们浪费大量的网络带宽和节点的处理时间，却对提高搜索效率毫无帮助。因为f l o o d i n g 的消息扩散范围要比r a n d o mw a l k 大很多，所以如果不考虑网络带宽的开销，显然f l o o d i n g 算法比r a n d o mw a l k 的搜索速度更快。但这也恰恰表明了f l o o d i n g 最大的缺陷：资源搜索的瞬时冗余开销过大，消耗了大量的网络带宽。每个节点都必须处理在一定半径t t l 内的所有节点的资源搜索请求，如果某个节点想要搜索固定比例的网络区域( 比如说5 0 ) ，那么当网络规模增长时，网络中的节点和节点间的线路将会承担与网络节点总数成正比的搜索开销。在c l i p 2 于2 0 0 0 年发布的一个关于g e n u t e l l a 的研究报告“7 1 中表明，当搜索资源的开销随着网络规模呈线性增长趋势时，网络中的节点将变得负载过重而无法继续工作。5 6 i ( 的调制解调器每秒只能处理约2 0 个以内的资源搜索请求，在一个大约1 0 0 0 个节点的网络中，这个上限很容易被超出。这时网络中带宽为5 6 k 的节点都会失效，网络会变得支离破碎，只能为用户在很小的范围内提供资源搜索服务。虽然现在宽带网络的使用逐渐成为主流，但是随着网络节点的增加，有限的网络带宽和节点的处理能力仍有可能无法满足大量的资源需求。关于安全性，由于不存在集中式的中心节点，对等网中的任何节点都可以随时离开或加入，因此基于对单点的攻击方式在这里将不会影响到其它节点，而其它的攻击方式一般所波及到的范吲也不会很大。但在这样的对等网中添加各节点间的加密认证机制还是很必要的，它保证当你上传和下载资源时能够识别正常节点和恶意节点。2 2 2 2 随机选路转发算法( r a n d o mw ajk ) f i o o d i n g 和r a n d o mw a l k 算法都适用于对被请求资源的位置的信息量非常少或根本就没有资源位置信息的对等网搜索中。由于这样的网络中节点和其资源的分布都是随机的、没有任何规律可言，因此我们称这种网络为非结构化网络( u n s t r u c t u r e dn e t w o r k ) 。相对于非结构化网络而言，同样也存在结构化网络( s t r u c t u r e dn e t w o r k ) 。结构化网络是指这样种网络；