（计算机系统结构专业论文）基于延迟和环状拓扑的网络时钟同步系统.pdf

基于延迟和环状拓扑的网络时钟同步系统 摘要 基于延迟和环状拓扑的网络时钟同步系统 为了评价端到端体系中的网络性能，网络单向延迟等性能参数的测量至关重要。但由于 网络中各主机的时钟不同步，使得单向延迟测度值难于准确测量。为此，本论文研究并没计 实现了一个分布在网络各主机上的面向单向延迟测量的多主机时钟同步系统，该系统基于环 状拓扑模型。即：对在一个逻辑环状拓扑上的各主机的时戳报文数据进行测量和统计，建立 时钟同步模型，并利用环状拓扑结构再进一步协同各结点同步。 首先，本系统所研究的结点间的同步模型的建立参考了p “s o n ，m o o n 和l z h a n g 等人 提山的时钟同步方法，在此基础上进行改进设计，提出a v 同步方法，为用户提供准确高 精度的同步时间戳。 其次，基于现有的树型，星型或是p 2 p 网状同步拓扑系统的研究基础，提出环状同步 拓扑f 的同步系统设计。本系统在结点问的同步模型建立之后，利用逻辑的环状同步拓扑， 计算该同步环上的时钟累积误差，对环上各结点的同步模型进行协同修正以进一步提高同 步精度。 最后，系统提供动态环状逻辑拓扑的建立、解除及自维护。系统能够以较短的收敛时间 自主建立、解除其环状逻辑拓扑。此外，还提供同步拓扑环的自维护能力，即后续结点可以 加入己建立的同步环，环上的结点可以主动撤离当前同步环，同步环在同步中若判断环上有 失效结点将使该同步结点被动撤离当前同步环。 综上所述，本系统可以对在同一逻辑环状拓扑中的若干主机结点进行时钟同步，以此为 测量各主机间的网络单向延迟值提供准确的时戳数据。 【关键词】时钟同步环状拓扑单向延迟相对时钟偏移 i i i 基于延迟和环状拓扑的网络时钟同步系统 a b s t r a c t n e t 、v o r kc l o c ks ”c i l r o n i z a t i o nb a s e do no n e w a yd e l ”a i l dr i n g e d1 b p o l o g y t om e a s u r et 1 1 en e t w o r kp e r f b r n l a n c eb c e e ne n d 柚de n d ，s o m em e m c sa r er e a i l yi m p o n a l l t ， s u c h 觞0 n e - w a yd e l a y h o w e v e i ti sd i m c u l tt dm e a u s r et h i sm e 啊cd u et ot l l ea s ”c l l r o n i s m 锄仰gh o s t s n l i sd i s s e r t a t j o nd e s i 即e d 柚dw o r k e do u tan e t 、v o r kc 1 0 c ks ”c h r o n i z a t i o nw h i c hi s b 粥e do no n e w a yd e l a ym e 嬲u r e m e n ta n dr i n g e dt o p o l o g yi nd e t a i l ，i tc o l l e c 乜廿1 et i m es t a l l l p d a t ao nh o s t sw h i c ha r eo 唱a n i z ei n 1 0 9 i c a l l yr i n g e dt o p o l o g y t 1 1 e ne s t a b l i s h st 1 旧c l o c k s ”c h r o n i o u sm o d e lb a s eo n 也et i m es t a m pd a t a ，a n d 五n i a l l ym a k e sa l lt h eh o s t sc 0 0 r p e r a t ew i t l l e a c ha t l l e rt o 叩t i m i z et h es y n c h 划n i o u sm o d e ld a t a f i r s t l y ，t h er e s e a r c ho nm ee s t a b l s h m e n to fc l o c ks y n c h r o n o u sm o d e li sb a s e do nt 1 1 ep r e s e n t c l o c ks ) ，1 1 c h r o i l o u sm e a m o dm a d eb yp a x s o i l ，m d 0 n ，“z h a n ga l l ds o m eo t l l e rp e r s o n a f t e rs o m e i m p r o v e m e n td e s i g n ，t h i sd i s s e r t a t i o np r c s e n ta vs y n c i l m n o u sm e a t h o dw h i c hc a np r o v i d e s y n c l 】t o n i z e dt i m es t a m p sw i t l lb e n e rp r e c i s i o nf b rt h eh o s t s s e c o n d l y t l l es y n c h l d n i z a t i o nb a s e do nr i n g e dt 叩o l o g yi sd e s i g n e d ，w h i c hi st o t u a l l yd i f l b r e n t 如mt 1 1 ep r e s e n tm e 抽0 db a s e do nt l l et r e e ，s t a r0 rp 2 pm o d e l b e n e m 劬mt h i sl o g i c a i l y t o p o l o g 托t 1 1 es ”t e mc a ng e tt l l ei m 他r i ts y n c h r o r l o u se 丌o rw h i c hc a nh e i pm eh o s tt oi m p r o v et h e p f e c j s i o n t h i r d l y ，t h es ) m c | l r o n o u ss y s t o mp r o “d et l l ed y n 锄j cm a i n t e n a n c ef b ri t sl o g i c a l l yt o p o l o g y s u c h a se s t a _ b l i s h m e n t d i s m i s s i o n ，i n s e n i o l l 柚de t c i tm e a n s 协a tt h j ss v s t e mc a nb ee s t a b l i s h e d0 r d i s m i s s e db yi t s e l fw i t l l i i las h o nt i m e a n o t l l e r 廿l i r 培t om e n t i o ni si 协s e l f m a i n t e n 锄c ea b i l i 吼 也a ti st h ea b i l 姆f o r 出eo t h e rh o s tt oj o i ni m o 如ee s t a b l i s h e ds y n c h r o n o u sr i n g ，o f 岛rt h eh 。s t w h i c hi sa l r d yi nt 1 1 es ”c l l r o n o l l sr i n gb u tw h ow 柚tt ol e a v e i na d d i t i o n ，i tc a np a s s i v e l y w i t i l d i 洲t l l eh o s tw h c hc 柚n o tb ec o n t a c t c df o ral o n gt i m e a l lm a 1 1 ，t l l i ss y s t e mc a ns y n c l l l d n i z es e v e r a lh o s t si l laj o g i c a l l yr i n gt o p o l o g y a 1 1 dp m v i d et 1 1 e p r c i s e 血n es t a m pd a t at om e a s u r et h eo n e - w a yd e l a yb e t w e e nh o s t s 【k c yw o r d s 】c l o c ks y l l c h m n i z a t i 咖，刚n g e dt 0 p o l o 卧o t l e - w a yd e l a y ，r e l a t i v ec 1 0 c ko 凰e t i v 基于延远和环状拓扑的网络日j 钟同步系统 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 研究生签名：盐! 叁鏖日期：翌坚j 。 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位 论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人 电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论 文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公稚( 包 括刊登) 授权东南大学研究生院办理。 研究生签名：拯整盘聊躲百书日 i 导师签名：r日 1 耐、5 口 期： i i 基于延迟和王_ f 、状拓扑的恻络时钟同步系统 第一章引言 为了评价端到端体系中的网络性能，网络单向延迟及丢包率等性能参数的准确测量至关 重要。然而在钡量中，时间的微小偏差就可能给这些参数的测量带来极大的误差甚至是错误 【1 1 。因此，只有高精度的时钟同步技术才能解决这一问题。近年来，许多研究者对面向延 迟的时钟同步问题展开了全面的研究。另外，在环状逻辑拓扑的自主动态维护方面，局域网 上的令牌环网 2 ，3 的构建方式对本文的环拓扑建立具有一定的参考价值p 2 p 的c h o r d 路 由表操作提供了高扩展性的自维护算法4 ，为多主机时钟同步中环结构的搭建起到了很好 的示范作用。 在本章中将主要进行相关背景知识的介绍，包括现有时钟同步技术，令牌环网的构建工 作方法以及c h o r d 环自维护算法等，并给出论文的研究目标、主要研究内容和论文的组织结 构。 1 1 研究的意义 计算机时钟一般以振荡电路或石英钟为基础，每天的误差可达数秒，经过一段时间的累 积就会出现较大的误差。随着分步式计算和网络技术的发展，不准确的计算机时钟对于网络 结构以及其中应用程序的安全性会产生较大的影响，尤其是那些对时钟和同步比较敏感的网 络指令或应用程序。依靠系统管理员手工使用d d c e 命令来调节各个系统的时钟支持同步是 不可能在精度上达到要求的。目前晟常采用的方法是使用网络时间协议n t p 5 。 随着网络技术和规模的不断发展，许多应用，尤其是与网络测量有关的应用，对时钟同 步精确度的要求变得更高了，i p p m 框架r f c2 3 3 0 【6 指出：“时间测量处于许多测量指标的 核心地位”，如单向延迟【7 ，8 】的测量等。 i c e m 武的服务质量由i m e m e t 的性能直接决定，反映i n t e m e t 服务质量的参数很多，性 能参数【6 】量化了终端用户对i n t e m e t 服务质量的直观感受。最普通的性能标准有：往返延时、 丢包率；随着实时多媒体应用的发展( 如、b i p ) ，抖动和单向延迟也显得愈加重要。单向延 迟 9 】( 0 n e - w a y d e l a y ) 的概念为：源端发出包的时刻到目的端收到该包的时刻2 间的时间 就是源端到目的端的单向延迟。不同的网络应用对各种性能关心的程度有所不同。w 曲服 务对时延的要求较低。而在v 0 1 p 应用中，当单向延迟超过2 5 0 m s 时，其性能将大打折扣。 对单向延时的测定就要涉及时间同步。 除了网络单向延迟之外，对许多度量参数来说，时间的测量都是一个核心问题。因为这 一点，在设计测量某参数的方法时弄清由不完善的系统时钟引起的不同类型错误和不确定性 至关紧要。 但由于不同主机的时钟振荡频率不一，即使采用n t p 同步协议也很难在一段相对较长 的时间里在精度上满足同步的要求。测试实验发现5 分钟内两台主机之间的不同步大约为 3 0 毫秒【l 】，显然，它无法满足需要毫秒级的同步精度要求的单向延迟的测量。为满足网络 测量的精度要求，面向单向延迟的网络时钟同步成为研究的一个重要方面。 基于延迟和环状拓扑的网络时钟同步系统 1 2 时钟同步研究现状 时钟同步问题由来己久。可以说自网络出现后，随即便有了同步网的概念。准同步数字 系列( p l e s i o c l l r o n o u sd i g i t a lh i e r a r c h y ，简称p d h ) 系统、同步数字系列( s y l l c h m n o u sd i g i t a l h i e r a r c h v ，简称s d h ) 在数字通信网的每个节点上都分别设置高精度的时钟，使时钟的信 号都具有统一的标准速率。正是这样的同步网为电信网内所有电信设备的时钟( 或载波) 提 供了同步控制信号，提供了工作频率在共同速率( 或频率) 上的支撑网。 随着网络技术的发展及虚拟主机和局域网的出现，主机之间的时钟同步精度的要求也越 来越高。网络时间协议( n t p ) 的出现能够很好地解决这一问题。n r p 能调整时间抖动率， 建立一个即时缓和、调整时间变化，并用一群受托服务器提供准确、稳定时间的时间管理。 但面对单向延迟等端到端测量的精度需求，n t p 技术也不能适用，因而又产生了一系列针 对更高精度时钟同步技术的研究与实现。 1 2 1 硬件实现的时钟同步 使用硬件进行时钟同步的技术主要有：g p s ( g i o b a lp o s i t i o n i n gs y s t e m s ) 和无线电信号 两种。 g p s 利用的是卫星信号提供精确的时钟同步，其最高分辨精度可以达到1 0 0 i l s 。当g p s 信号转换为计算机系统内核的时钟脉冲时会损失一定的精度，但其仍可将延迟范围控制在微 秒以内，这种精度对于绝大多数的需求来说是足够的。使用g p s 进行时钟同步测量的缺点 在于：g p s 接收器需要直接对准卫星，对每个需同步的机器都要安装，价格较为昂贵；另 外，g p s 接收器需安装在室外，它也不适用于一些对数据有安全要求的应用使用。此外该 该技术存在三个问题：第一，g p s 系统受美国军方控制，其p 码仅对美国军方和授权用户 开放。民用c a 码的时间同步精度比p 码低两个数量级，而且其安全性没有保障；第二， g p s 信号通过无线方式传输，易受外界干扰；第三，g p s 接收机的时刻信号是通过标准接 口( 如r s 一2 3 2 接口) 输出的，很多网上在用设备( 如交换机) 并没有这种专用接口。【1 0 】 使用无线电信号进行的时钟同步可以提供微秒级的同步精度，但不能保证任何地方都能 正确接受到无线信号，同时，空气也会对信号产生干扰。 1 2 2 软件实现的时钟同步 网络时间协议n t p ( n e m o r k t i m e p r o t o c 0 1 ) 是由美国德拉瓦大学的d a v i d lm i l l s 教授 于1 9 8 5 年提出，除了可以估算封装在网络 上的往返延迟外，还可估算计算机时钟偏 差，从而实现在网络上的主机校时。 网络时间协议( n t p ) 以合适的算法 以增强时钟的准确性，并且减轻由于多个 同步源而产生的差错，实现了精确度为毫 秒级的时间服务，以满足i n t e m e t 中各种 应用的需要。其基本思想为通过u d p 报 名 r 铯h t i + t t 2t 3 图1 1n t p 同步体系原理图 文的传送，计算机器间的时钟偏差；以此为基础根据当前机器所处的层次关系，决定和调整 时钟值。表1 1 所示为使用n t p 同步中，所涉及的四个关键参数。图1 1 说明了这四个参数 基于延迟和环状拓扑的嘲络时钟同步系统 的意义及它们之间的关系。在报文传送中，首先由客户端发起同步请求，在请求报文中记录 下当前机器的时间戳t l 。当服务器端接收到此报文时，立即记录下接收时的时间戳t 2 。服 务器端接收到报文后，向客户端发送一个应答报文，并记录当前时间戳t 3 。客户端收到此 应答报文，也立即记录该时间戳t 4 。 t i m e s t a m pn a m e i dw h e ng e n e r a t e d o r i 西n a t et i m e s t a m p t 1t i m er e q u e s ts e n tb yc l i e n t r e c e i v et j m e s t a m pt 2虹m er e q u e s tr e c e i v e da ts e r v e r 1 h n s m i tt i m e s t a i l l p t 3 t i m er e p l ys e mb ys e r v e r d e s t i n a t i o nt i m e s t a m p t 4 t i m er e p l yr e c e i v e da tc l i e n t 表1 1n t p 同步机制参数表 设：t 为服务器和客户端之间的时钟偏差；d 为两者之间的往返时间。因为t 2 = t 1 + t + d 2 ： t 2 t 1 = t + d ，2 ：t 4 = t 3 t + d ，2 ；t 3 t 4 = c d ，2 ；所以d _ ( t 4 一t 1 ) - ( t 3 t 2 ) ；故最终得到时钟偏差 卢( ( t 2 一t 1 ) + ( t 3 - t 4 ) ) 2 n t p 可以提供一定精确度的时间校正，在l n 上约小于l 毫秒，在，a n 上几十毫秒 左右。但随着技术的不断发展，这种精度的同步已逐渐不能满足网络研究方面的需求。尤其 是在测量单向延迟等对网络时钟同步要求十分严格的情况下。考虑以一分钟为间隔测得的两 互联网主机间的单向延迟样本时，对一横穿网络的路径，主机间的真实传输延迟应该是5 0 毫秒左右。由于不同主机之问的时钟频率振荡不一，导致同步一段时间以后又会产生不同步。 通过测量发现：1 秒钟主机之间的不同步约为0 1 毫秒。那么在观测1 0 分钟之后引入测量中 的错误将约为6 0 毫秒。这种错误是不能容忍的。作者曾对n r p 同步后的时间进行进一步同 步的实验，以使其能够符合单向延迟测量的需要 1 】。另外n t p 的同步精度还依赖于运行n t p 服务的结点之问的稳定性和对称性是否良好。另一方面，在网络中，并不是所有的主机都支 持n t p 服务。 在面向单向延迟的时钟同步技术研究方面，主要的研究结果包括如下几个方面。 分段线性最小法将测得的时钟偏移分为若干段，然后统计其变化情况，其同步结果很不 理想。p “s o n 提出了一种对往返两个方向上的单向延迟经处理后再使用线性规划方法测量 时钟偏移以同步时钟的方法 11 ，但这种方法在网络状况变化频繁的情况下性能很差。m o o n 方法提出使用一种标准线性算法 1 2 】逼近测量得到的延迟值，从而消除其中的延迟偏移。“ z h a n g 方法基于m o o n 等人的研究提出类似凸包【1 3 计算的修正算法 1 4 ，然而应用该方法时 会发现，凸包集合的点十分不均匀，给修正带来不可避免的误差。国内的 1 5 】中，通过对网 络延迟进行精确测量，建立了网络延迟的对数正态分布统计模型，然后基丁该模型实现了概 率同步算法。该概率同步算法以一种新的思路实现了同步计算，精度可以达到毫秒级。但为 测得单向延迟值，需要一个公共的远程服务器节点。 与此同时，为将时钟同步系统应用于i n t e m e t ，许多研究者又开始探讨对存在时钟重置 及频率调整的情况下进行时钟同步的解决办法。由于i n t e m e t 上的测量主机对于本地测量器 而言无法得知其时钟是否存在重置或是频率调整，故需对时钟的重置及频率变化做测量。这 方面的研究主要包括：“z h g 的m a r c h i n g 算法 1 4 ，r y g e r 的f i x c l o c k 1 6 】，【1 7 中提出 的基于时间序列分段技术的算法以及国内的文献 1 8 中提出的时钟动态性检测算法。“ z h g 的m a r c h i l l g 算法在网络高负载情况下，会把由于网络拥塞造成的相对较大的时延抖 动误认为是时钟重置。同时，m a r c h j n g 算法和r y g e r 的f i x c l o c k 方法由于需要同时得到两 基于延迟和环状拓扑的网络时钟同步系统 个方向上单向时延数据而使得在许多只能得到一个方向上的单向时延数据的环境中的应用 受到极大的局限性。基于时间序列分段技术的同步算法的优点是能只利用一个方向上的单向 延迟值在线实时检测时钟重置，但其中的分段数量的估计算法缺乏准确性，而且会把有较长 拥塞误认为是时钟调整。时钟动态性检测算法在稳建性上仍须改进。 1 2 3 多主机问的时钟同步 在多主机的时钟同步方面，n r p 协议采用的是层次性同步方式，时间按n t p 服务器的 等级传播【1 9 】。n t p 按照离外部u t c 源的远近将所有服务器归入不同的s h 锄n ( 层) 中。 s 订a t i l m 1 在顶层，由外部u r c 接入，而s t r a m m 2 则从s t r a m m 一1 获取时间，s n 曲l m 3 从 s t r 咖m 2 获取时间，以此类推，但s t r a t u m 层的总数限制在1 5 以内。所有这些服务器在逻 辑上形成阶梯式的架构相互连接，而s t r a t u m 1 的时间服务器是整个系统的基础。图1 2 表 示了n t p 网络时间服务器的层次结构。 图1 2n t p 时间服务器的层次结构 计算机主机一般同多个时间服务器连接，n t p 利用统计学的算法过滤来自不同服务器 的时间，以选择最佳的路径和来源来校正主机时间。即使主机在& 时间内无法与某一时间服 务器相联系，n t p 服务依然有效运转。 此外，文献【2 0 硝 出了一种根据同步精度进行自适应的一对多同步的星形结构模型 s a c s ( s e l f _ a d a p t i v ec l o c ks y n c h m n i z a t i o n ) 设计。【2 1 中讨论了分布式系统中时钟同步的 系统模型、远端时钟读取方法阻及取向通信传输过程的设计思路，利用其提出一种基丁统计 平均的时钟同步算法，以星型模型实现多主机同步。但这些同步方法的同步精度只适用于一 般异步环境的分步式系统。文献【2 2 】提出一种c t p ( c l s l e s st i m ep r o t 0 1 ) 设计，所谓c 1 s l e s s 4 基于延迟和环状拓扑的网络时钟同步系统 就是指所有的同步主机都是平等的关系，其构建的是一种以所有同步主机的同步精度之和最 高为目的的网状拓扑结构的多主机同步模型。该系统在精度也无法满足单向延迟测量等有高 精度同步要求的应用。 由此，本论文考虑了在多主机同步中使用环状拓扑结构实现的同步操作。使用环状的逻 辑拓扑同步，当各同步结点依照环的逻辑结构依次同步一圈后，同步误差可以在该环上得到 累积，利用这个累积误差则可以降低同步操作中可能的系统误差。为构建这样一个环型的同 步系统，本论文首先需要搭建一个环状逻辑拓扑系统，其相关背景介绍在下一节中给出。 1 3 环状逻辑拓扑的相关技术 本论文提出在环状逻辑拓扑下进行同步，为构建山环状逻辑拓扑，并使该拓扑能够白主 工作，自主维护，以保证同步的正常准确进行，本论文参考了如f 两种具有环拓扑特征的网 络的构建方法。 1 3 1 令牌环网简介 对于环状逻辑拓扑而言，可能最容易想到的是应用比较广泛的环型局域网令牌环网 的构建【2 ，3 。 令牌环网的工作方式是使用具有特定格式的令牌帧绕环行驶，将访问媒体的权利从一个 结点传递到物理连接的另外一个结点。m a c 实体将网络上层的数据组成m a c 帧，等待令 牌；并仅在获得令牌之后才能进行发送动作。每个结点均执行环内数据的再生和转发；只有 接收结点进行数据帧的复制和接收。发送数据的结点在收到绕环一周的帧后，撤出该帧并释 放令牌。为进一步提高网络性能，令牌环网还提供一种优先级预定和处理机制。 令牌环的t 作状态由监控器进行控制。环路中可以设置专门的监控器，也可以由环中任 一结点临时起着监控器的作用，此时该结点称为活动着的监控器，它同时具有监控和一般结 点的功能。当环路上没有专门的监控器时，环上其他结点以备用监控器方式工作，一旦活动 着的监控器故障或者退出环路，则采用令牌要求的方式产生新的活动监控器。 与其他的局域网构建方式( 如c s m a c d 网或者令牌总线网) 相比较而言，令牌环网可 咀估算出最人的发送延迟，因此较为适合对实时性具有一定要求的应用环境。此外，由于可 以具有优先级机制，因此可以为高优先级的信息发送保留一定的带宽。其缺点是需要最小的 发送延迟以等待令牌。而其中为监控令牌环的工作状态而设的监控器也增加了维护工作的复 杂性。并且，随着令牌环上结点数目的增加，结点的发送延迟将会加大，令牌环的性能会有 所下降。为了既可以支持更多结点之间的通信，又不降低网络的性能，i b m 采用子网划分 的方法组建网络，子网之间采用桥接器进行互连。 1 3 2c h o r d 系统简介 计算机对等网络( p e e r _ 珏p e e r ，p 2 p ) 的研究是目前新一代互联网技术研究的热点之 一。p 2 p 网络【2 3 】是一种具有较高扩展性的分布式系统结构，其对等概念是指网络中的物理 节点在逻辑上具有相同的地位。 迄今为止，p 2 p 网络已出现了四种不同的网络模型。以n a p s t e r 2 4 为典型代表的集中 基于延迟和环状拓扑的网络时钟同步系统 目录式p 2 p 结构，以g n u t e l l a 2 5 为代表的纯p 2 p 模式也被称作广播式的p 2 p 模型，以 k a z a a 2 6 模型为代表的p 2 p 混合模型，以及采用分布式哈希表( d h t ) 技术为主流方法的结构 化p 2 p 模式。麻省理工学院的c h o r d 项目 4 是目前基于d h t 的代表性的研究项目之一。其 系统采用动态哈希表( d i s t r i b u t e dh a s ht a b l e ，d h t ) 作为资源定位方式。其d h t 算法决 定了c h o r d 的逻辑拓扑是一个环形拓扑。文件按照p 2 p 拓扑中的逻辑地址精确的分布在网络 中。 c h o r d 系统是一个完全的分布式系统，它的每一个节点都是平等的。它提供了一个可扩 展的查找协议来满足经常有节点加入退出的动态p 2 p 系统。c h o r d 系统可以自动调整其中的 路由表来反映新节点的加入和节点的失效，确保只要f 层网络不发生错误的情况下，管理某 个k e v 值的节点总能被找到。即使系统的状态在频繁的变化中，这种有效性也能够得到保证。 在c h o r d 系统中，k e y 值和节点i d 分布在2 大小的c h o r d 环上，每个k e y 值在大于等_ 丁：其i d 的节点上。这个节点称为k 的后继节点，记为：s u c c e s s o r ( k ) 。为提供高效率的查找，c h o r d 环上的每个节点上都记录了额外的路由信息在f i n g e r 表里。f i n g e r 表的路由信息如表1 2 所 不。 表1 2c h o r d 环上节点的路由表结构 域名定义 f i n g e r k s t a r t( n + 2 h ) m o d 2 m1 七州 f i n g e r k n o d ef i n g e r k s t a r t 的后继节点 f i n g e r k i n t e r v a l( f i n g e r k s t a r t ，f i n g e r k + 1 s t a r t ) successor 本节点后继，即f i n g e r 1 n o d e p r e d e c e s s o r 本节点前继 图1 3 所示为含有f i n g e r 表的c h o r d 环示例。 当一个节点加入c h o r d 环时，必须借助于一个己知节点进行引导，并对其他节点进行更 新。该算法分成三大步：节点加入( 退出) 许可认证( p e r m is s i o nq u a l i f y ) 过程，路由表 初始化( i n i t i a l i z e ) 过程，更新其他节点f i n g e r 表( u p d a t e ) 过程。节点正常退出的过程 类似于加入的过程。 节点加入( 退出) 许可认证( p e r m i s s i o nq u a l i f y ) 过程如下： ( 1 ) 向已知节点发送要求加入消息通过返回消息判断此系统是否允许加入，如果允许 则转向下一步。 ( 2 ) 调用i n i t i a l i z e 过程初始化自身f i n g e r 表，调用u p d a t e 更新其他节点f i n g e r 表。 路由表初始化( i n i t i a l i z e ) 过程如下： ( 1 ) 初始化自身f i n g e r 表中s t a r t 域( 使用f i n g e r 表中定义) 。 ( 2 ) 向己知节点发送定位消息，定位f i n g e r 1 s t a r t 后继符点，这个后继节点也同样 是新加入节点的后继。 ( 3 ) 通过向后继发消息得到其f i n g e r 表的前继域值并更新自身的f i n g e r 袭中的前继域， 然后用新加入节点值更新后继的f i n g e r 表中的前继域。 ( 4 ) 新加入的节点向后继发送定位消息，初始化f i n g e r 表中的其他n o d e 域。设过程正 在更新f i n g e r 表中的第i + 1 项( i 1 ) ，如果f i n g e r i + 1 s t a r t 人于本身节点值小于 f i n g e r i n o d e 则f i n g e r i + 1 n o d e = f i n g e r i n o d e 。如果这个条件不成立，则向后继发 消息定位f i n g e r i + 1 s t a r t 的后继节点初始化第i + 1 项的n o d e 域。 更新其他节点f i n g e r 表( u p d a t e ) 过程如下：( 该过程的是按照f i n g e r 表从1 到m 的顺序 来进新更新的，假设过程正在更新f i n g e r 表的第i 项。) 6 基于延迟和环状拓扑的网络时钟同步系统 ( 1 ) 新加入的节点( 设节点值为n ) 调用定位过程定位n 2 1 的前继节点，并向这个前 继节点发送更新f i n g e r 表消息。 ( 2 ) 当一个节点接受到要更新f i n g e r 表第i 项的消息后，首先检查f i n g e r i n o d e 是否 大于本身节点值，如果大于则转向第三步，否则就转向第四步。 ( 3 ) 检查f i n g e r i n o d e 是否大于n ，如果小于则向n 发送更新完毕消息，进行i + 1 步的 更新，否则则检查n 是否大于本身节点，如果大于则把n 赋给f i n g e r i n o d e 并向前继发送更 新f i n g e r 表第i 项的消息。如果小于则只向前继发送更新f i n g e r 表第i 项的消息。 ( 4 ) 检查n 是否是环中的最后一个节点如果是则转向第五步，否则转向第( 6 ) 步。 ( 5 ) 检查是否f i n g e r i n o d e 加上2 人于发起更新的节点。小于则向n 发送更新完毕 消息，进行i + 1 步的更新，大于则检查n 否大于被更新的本身节点如果大于则把n 赋给 f i n g e r i n o d e 并向前继发送更新f i n g e r 表的消息，否则只向前继发送更新f i n g e r 表的消 息。 ( 6 ) 检查是否f i n g e r i n o d e 大于发起更新的节点，小于则向n 发送更新完毕消息，进 行i + 1 步的更新，大于则检查n 是否大于2 1 减去被更新的本身节点值如果大于则把n 赋给 f i n g e r i n o d e 并向前继发送更新f i n g e r 表的消息，如果小于则只向前继发送更新f i n g e r 表的消息。 n 1 鞫3 2 图1 3 c h o r d 环f j r l g e r 表示例 1 4 论文的研究目标和主要内容 本论文的研究目标可总结为：为研究解决网络中的时钟同步问题，本设计对主机间的单 向延迟和时钟偏移展开实验研究，以改进两主机时钟同步算法为核心。设计一个能够稳定运 行在网络环境中，面向单向延迟测量的，基于环状拓扑且具有自主维护拓扑能力的多主机时 钟同步系统，为分布式网络环境下的各主机提供准确时间戳。并在此基础上，对时钟同步系 统的性能参数给予测试分析，以评估该时钟同步系统的各方面性能状况。 7 基于延迟和环状拓扑的州络时钟同步系统 围绕上述目标，研究_ _ 【_ = 作土要分成以f 五个方面展开： 主机间时钟同步算法的改进和实现。分析现有各算法的优缺点和网络应用环境特征，通 过实验和数学手段相结合，提出对现有算法的改进和优化，完成主机问同步算法的实现。 环状拓扑下多主机时钟同步体系模型的建立。目前的高精度同步系统研究大多局限在两 主机问的研究阶段，已实现的个别时钟同步系统精度都无法满足测量要求，而且在稳定性等 方面也存在问题。其中n t p 采用的是层次化的树形同步模式，c t p 采用的是全局最优的网状模 式，s a c s 呈星型同步模型，而本设计采取构建环形拓扑同步模型方法。本论文将研究如何在 保证准确及高精度的前提下构建环状拓扑下的多主机同步体系。 动态环状拓扑的实现。环状拓扑体系结构的实现包括环状拓扑的初始化建立，同步环上 结点的动态加入、撤离以及结束同步时对同步环上所有结点的同步关系的解除和各结点的退 出。在动态调整同步环中，需考虑同步结点的主动加入，主动撤离及被动撤离三种情况下对 原环状拓扑结构的维护和这种维护对环上结点的时钟同步产生的影响。 时钟同步系统的设计和实现。详细设计时钟同步系统的基本结构和所需的基本功能模 块。测量中涉及到的数据包括：时戳报文数据，由此统计得到的时钟同步模型，同步环上测 量到的累积同步误差，以及最终时钟测量结果等。并据此制定系统的数据流程及相应系统运 行流程，规范系统各部分的具体功能。 时钟同步系统的性能评价参数的测试和分析。本论文总结和归纳时钟同步系统的性能指 标，合理地给出本时钟同步系统评价参数的测试，以及该系统与其他时钟同步系统的性能比 较。 本论文剩余部分的组织结构如下： 第二章归纳现有的面向延迟测量的时钟同步模型设计和其中的不足，介绍本论文提出的 a l t a i r v e g a 同步方法以及基于环状拓扑的时钟同步模型及算法设计分析，并给出给方法 的理论精度分析。 第三章描述动态同步环拓扑的设计，包括：环状拓扑的初始化、动态自维护以及同步环 的解除等。 第四章介绍系统的体系结构设计，功能模块划分，数据流分析以及系统的详细设计与实 现。 第五章给出系统测试的测试指标，以及对测试结果的分析与讨论。 第六章总结全文，并展望未来研究的方向。 8 基于延迟和环状拓扑的网络时钟同步系统 第二章面向延迟的时钟同步研究 面向单向延迟的时钟同步研究方法都是建立在对含有时钟偏移的单向延迟的溯量基础 上，对其中的时钟偏移进行计算分析从而实现网络时钟的同步。各种方法的不同主要是由于 同步方法所采用的逼近延迟直线的方式不同而产生的。本文基于m o o n 方法和l iz h a l l g 方 法的基础，在本章中提出a l t a i r & v e g a 同步方法，并由此引申出环拓扑下的多主机时钟同 步系统。 2 1 相关术语 下： 网络时钟同步算法中涉及到各种关于时钟的基本概念，现将其中主要的概念定义概括如 1 时钟( c l o c k ) ：时钟c 被视为分段连续的函数，且除去一个有限个数的点的集合后 二次可微。即： c ：月r 其中，c ( f ) s 犯( ，) 办，并且c 。( r ) sd 2 c 0 ) 西2 存在( 除了有限i p l 中的 f p c r 处) 。 2 真实时钟( t m ec l o c k ) ：在描叙时钟c 这一术语时，“真实时间”的概念由系统时钟 所报告的时间来表示。我们通常所指的“时钟”是指系统时钟所报告的时间，而不 是此“真实时钟”。真实时钟g 定义为 e ( ，) 2 且只= 设：e 、c 6 为两时钟。 式( 2 1 ) 3 偏移( 。镌e t ) ：指系统报告的时间与真实时间的差。e 的偏移为巴( ，) 一，。f o 时，( 乙相对于( 乙的偏移为c 。( r ) 一c 6 ( f l 。 4 频率( 舶q u e n c y ) ：指时钟增长的比率。在t 时刻，时钟巴的频率为c ：( f ) 。 5 偏差( s k e w ) ：指时钟的频率与真实时钟频率之差。在t 时刻，时钟c a 相对于c 6 的 偏差为e ( ，) 一q ( 。 6 漂移( d r i r ) ：时钟c a 的漂移为。，0 时，时钟c a 相对于g 的漂移为 c ：( f ) 一q ( ，) 9 基于延迟和环状拓扑的网络时钟同步系统 7 时钟同步( s y n c h r o n i z e d ) ：对于两时钟而言，由于偏移和偏差都不是真实时钟的， 故以相对偏移和相对偏差为标准来讨论。在某一时刻时钟同步是指：时钟间相对的 偏移和偏差都为o 。在同步分析研究中，多数比较和讨论偏移，也有研究中认为讨 论频率的比率更为方便。因而有了下面这个定义。 8 时钟比率( c 1 0 c kr 鲥o ) ：时钟与真实时钟的频率比。c a 的时钟比率为c ：( n 。在t 时刻，巴相对于g 的时钟比率为c ：( ，) c ；( n 。 2 2 同步模型研究基础 现有的时钟同步研究都是通过对单向延迟的估计来修正其中时钟的偏移量从而实现时 钟的准确同步的。通过实验，人们发现单向延迟的测量值基本是呈线性模型的，所以在单向 延迟的估计计算中首先想到的必然是线性回归方法，因为线性回归方法是拟和直线图形的最 基本的方法。如果单向延迟呈现良好的线性模型时，线性回归的拟和是较理想的做法。但遗 憾的是，单向延迟的测量中常常会遇到偏离拟和直线较远的点，因此线性回归算法不能很好 地修正时钟偏差。在后来的实验研究中，p “s o n 提出一种基于“降噪”的o t l i 值估计计算。 厅 所谓邳 噪”的o t t s 值是将测得的单向延迟分为“断，从每段中被选出的最小的延迟值。 但既便是“降噪”的o t l b 值，简单的线性回归方法仍是不适用的。m 0 0 n 和“z h a n e 等人 在此基础上提出了各自的同步方法。本文基于以上研究结果进一步提出a l t a i r v e g a 同步 方法。 2 2 1m o o n 同步方法 m o o n 方法 1 2 的测量基于单向的延迟测量体系，并提出了新的单向延迟直线处理思路。 图2 1 所示为该方法的测量体系。图中a 主机为服务器端( 即发送方) ，b 主机为客户 端( 即接收方) 。m o o n 方法以接收方b 的时钟为真实时钟进行同步。通过这一测量体系， 可以得到的量有：从第1 个报文离开a 主机到 第i 个报文离开a 主机的时钟间隔5 ；从第1 个报文到达b 主机到第i 个报文到达b 主机的 时钟间隔矿。由3 和r 7 可计算得到延迟值z 。 设a 主机与b 主机间的实际的端至端单向 延迟值表示为d 。m o o n 方法研究发现： 虿= z 一( 口一1 ) 百5 + z 。令：舀和声分别为口和 d 的估计值，则延迟值中所需要去除的偏差d 为 时戳报文 一 a 图2 1m 0 0 n 方法测量体系图 b 1 0 皋于延迟和环状拓扑的网络时钟同步系统 童= 互一( 舀一1 ) i 5 + 声 m 0 0 n 方法使用一种新的线性算法逼近测量得到的延迟值 中的延迟偏差。即：满足如下两个约束条件的要求的直线： 孑一( 舀一1 ) i 。+ 夕o ， 1 f 椭僖c 珀疗确 m i n ( z 一( 西一1 ) 百5 + 声) l l _ 1j 2 2 2 “z h a n g 同步方法 以估算口的值，从而消除其 式( 2 2 )