网络时间同步算法中时间延时优化方案

网络时间同步算法中时间延时优化方案赵斌1,贺鹏1,2,易娜1(1.三峡大学电气信息学院，湖北宜昌443002；2.三峡大学信息技术中心，湖北宜昌443002)([e-mail])摘要：针对NTP技术中的对网络时间延时测量的不足，本文提出了在网络支持下的高精度时间同步方法。该方法是采用数据包丢失技术，通过比较传送的数据报文中的特殊队列值和所经过的路由器中数据包的排队队列长度值来决定是否对当前数据报文丢弃。仿真实验表明：这种技术具有很好的可行性。关键词：时间延时；自我丢包；时间同步；中图分类号：TP391文献标识码：AOptimizationofdelayinnetworktimesynchronizationalgorithmZHAOBin1,HEPeng1,2,YINa1(1.CollegeofElectricalEngineering&InformationScience,ChinaThreeGorgesUniv.,YichangHubei44300,China2.InformationTechnologyCenter,ChinaThreeGorgesUniv.,YichangHubei44300,China)Abstract:Inordertoimprovemeasuredprecisionoftimedelay,ahighlyprecisetimesynchronizationtechniqueswasproposed.Itistheself-discardingpackettechniquewhichisameansofdeterminingtransferbycomparingthequeuelengthofthetransitingrouterwithaspecifiedqueuevalueonthepacket.Simulationresultsshowithasaneffectivefeasibility.Keywords:timedelay;self-discardingpacket;timesynchronization0引言随着计算机网络的高速发展，各种涉及时间戳相关的应用和服务，如：实时的网上交易、制造过程控制、网络安全性设计、分布式的网络计算和处理以及数据库文件管理等对时间精度提出了更高的要求。传统的基于NTP协议的时间同步算法，是建立在客户机和服务器进行通信中，请求数据包和应答数据包的往返延时相等的前提下，达到时间同步的目的[1][2]。往往由于网络阻塞的原因，单向传递延时和接收延时是不能视为相等。因此，由于单向延时的影响，导致NTP时间同步算法有数十毫秒的时延误差。而当前比较成熟的高精度GPS时间同步技术精确度在1毫秒之内，但是需要安装户外天线，被限制了使用范围[3]。在网络仿真环境支持的前提下，本文提出了在时间同步算法中处理单向延时的方法，降低网络抖动，提高时间同步的精确度。1时间同步技术1.1NTP技术网络时间协议NTP（NetworkTimeProtocol）是用于互联网中时间同步的标准互联网协议。NTP协议利用层次式时间分布模型把计算机客户端的时间同步到某些外部时间源的时间标准。目前常采用的时间标准是来自一级时间服务器的世界协调时UTC（UniversalTimeCoordinated）。NTP时间戳以64bit无符号的定点数表示，整数部分以高32bit表示，相对于基准1990.01.0100:00:00记录当前的秒累积数；小数部分以低32bit表示，其精确度可达200皮秒[4]。NTP时间同步算法根据服务器和客户端的往返报文来确定两地时钟的差值和报文在网络中传输的延迟，在往返延时假设相等的条件下，获得精确的时间同步。图1中，T1和T4是客户端时钟记录的发送NTP报文和接收NTP报文的时间，T2和T3是服务器端时钟记录的接收和发送NTP报文的时间。这里可以设定服务器的时钟是准确的，服务器和客户端时钟的时间偏差是∆，从客户端发送报文到服务器端的网络延时是d1，从服务器到客户端的网络延时是d2，可以列出三个方程式：T2-T1=∆+d1T4-T3=d2-∆∆=((T1-T2)-(T4-T3)-(d1-d2))/2NTP算法是在网络延时d1和d2对称（d1-d2=0）的条件下，计算出时间偏差∆。但是在网络发生抖动时，这种测量方式就会产生大的误差，降低了同步效果。1.2NTP时间延时的精确测量NTP算法试图通过上述静态方法来提高时间同步的精确度，却不能消除报文单向延时的抖动造成的影响，而使服务器客户机t2t3t1t4图1网络延迟和时钟偏差测量图头NTP算法变得更加复杂[5]。报文在网络传输过程中，经过路由器的排队等待转发的时间延时是造成网络时延的主要方面，为了使网络的传输延时会直接反映在时间差的测量中，实验采用一个高精度时钟（具有一级或二级时间服务器精度）的PC机，并能够在微秒级精度以下处理时间，作为客户端来接收来自外部的高精度时钟信号，用一个带有铯原子钟信号的高精度PC机作为服务器端。图2和图3是客户端和服务器9天内对时间延时偏差测量数据，前者是在报文没有经过路由器转发的情况下，对时间延时的统计。后者是在网络阻塞的情况下，数据报文经过一个路由器转发时，对时间延时的统计。从测量结果可以看出，数据报文延时的波动是被网络阻塞造成的，经过路由器转发引起的时延变化在100微秒左右，这是在没有路由器转发情况下时延的5倍。下面我们讨论数据报文通过一个路由器转发的时钟同步情况，提出了数据报文通过路由器转发和不经过路由器转发获得相同时钟精度的方法。图2时间延时测量数据-100-75-50-25025507510012345678910测量时间（天）时间延时（微秒）图3时间延时测量数据-100-75-50-25025507510012345678910测量时间（天）时间延时（微秒）3网络支持下的时间同步根据上文的分析我们已知，数据报文经过路由器转发所引起的时间延迟对NTP时间同步算法的精度的影响是很大的。我们采用数据报文在动态网络中经过路由器转发时自我处理的方法，来降低网络抖动造成的时间延时对NTP时间同步算法的影响。动态网络是指支持网络中路由器有权对排队等待转发的数据报文进行动态的处理，决定其流向。这种动态网络的基本构成包括一个可编程的数据交换方法和一个数据封装方法。前者是指预先在网络中的动态路由器中建立一个可执行的处理程序，后者是指活动路由器对传递报文进行相应处理后，对相应处理参数可封装在报文中。相比较而言，前者要比后者的处理过程更复杂，我们称这种方法为报文自我丢包技术。该技术是指数据报文在传递过程中根据相应字段的特殊队列值和所经过的路由器中数据包的排队队列长度进行比较决定是否丢包。Pql用来描述数据报文在路由器转发时允许的最大值。当一个数据包到达路由器转发时，如路由器中等待转发的数据包的队列长度比该数据包中所设的Pql的值大，则就丢弃该包。也就是说，当网络延时超过一定时限时，丢弃时间报文来加强同步算法的稳定性，提高算法的精确度。另外，这种方法也不会影响到别的数据包的传送，因为数据报是在活动节点被丢失的。我们采用MQL方法和QTL方法来实现对数据报文的操作。3.1MQL方法（MaximumQueueLength）在数据包中设定Pql的值，当Pql的值比当前路由器中的排队队列长度的值大时，该包就在当前结点丢失，不被发送出去，否则就通过该路由器转发出去。在这个过程中Pql的值保持不变。图4显示这种方法的工作机制。但是采用这种方法，仅仅是Pql的值和当前路由器中的排队队列长度进行比较；因此，当数据包经过转发的路由器数量增加时，总的时间延时也就会增加，在这种情况下，采用MQL方法来处理时间延迟是不理想的。3.2QTL方法（QueueToLive）另外一种方法是QTL方法，在数据报中设定Pql为足够大的值，当数据报经过路由器转发时，Pql的值就变为Pql与该包在当前路由器中的排队队列长度之差。当Pql的值为0时，该包就会被丢弃。图5显示这种方法的工作机制。当数据包传到客户端时，根据Pql的值来判断该数据包是否有效。这种方法类似TTL（TimeToLive）机制。这样，通过PacketPql=2路由器PqlRql(路由器排队等待队列长度)Rql=1通过PacketPql=2图4MQL方法的工作机制Pql=Rql(路由器排队等待队列长度)PacketPql=2路由器丢弃Rql=3PacketPql=2所设定的Pql的值把数据包在网络传递的时间延迟控制在一定时间段内。和MQL方法相比较，QTL方法在减少时间延时波动，提高同步算法精确度方面有更好的效果。4仿真实验及结果分析利用网络仿真软件（NS2）验证了报文在经过路由器转发时的自我丢包技术在处理时间延时的有效性，确定数据报经过路由器转发时时延的概率，来估算路由器对网络延时的影响[6]。本方法对时间延时的测量过程中，采用在客户端和服务器之间FTP数据流量来影响数据报文在路由器中的转发时间延迟。通过改变FTP数据流来比较时间延时的变化。设定网络带宽是100Mbps，路由器缓冲器中能够最大存放等待转发的数据报文是300，图6是网络仿真结构图。首先，在1000FTP数据访问流量情况下，数据报文经过一个路由器转发和经过二个路由器转发造成的网络时间延迟分布情况如图7和图8所示。两图表明：增加一台路由器将会影响数据报文转发时间延迟增加近100微秒的概率。因此我们得出结论，当MTU（最大传输单元）长度的数据报以120微秒的流速通过高速以太网（100Mbps）时，增加一个路由器转发过程，此时队列延时的概率就增加一倍。图9表明在FTP数据流量发生变化的情况下，数据报在路由器转发过程中网络时延的概率变化。从这些数据我们可以看出，仿真网络中两个路由器在1000FTP数据流量情况下，数据报文无时延转发的概率要比只有一台路由器时降低45%。图7数据报文经过一个路由器时网络时延概率分布01234502004006008001000网络时延（微秒）时延概率（%）图8数据报文经过二个路由器时网络延时概率分布01234502004006008001000网络时延（微秒）时延概率（%）图9在FTP数据流量变化下无延时概率统计4050607080901001002003004005006007008009001000FTP数据流量无延时概率（%）通过一个路由器通过二个路由器实验结果表明：数据包不经过路由器转发时，网络时延为0的机率是很大的，采用MQL和QTL方法对今后同步算法中处理网络时延是有效的。由于数据报在网络中经过转发的路由器数量的不确定性，把MOL和QTL方法结合在一起在同步算法中使用是必要的。5结语本文采用高精度PC机分析了NTP算法中路由器对报文时间延迟的影响，数据报经过一个路由器转发比没有经过路由器转发所产生的时延是100微秒的范围变化。并提出了数据报文自我丢包技术来提高同步算法处理时延的精确度，通过仿真实验表明这种方法是有效和可行的，今后的工作是把PacketPql=10路由器Pql0Rql=1通过PacketPql=9Pql=0PacketPql=3路由器丢弃Rql=4PacketPql=-1图5QTL方法的工作机制Rql表示路由器排队等待队列长度路由器2路由器1FTP数据流FTP数据流图6网络仿真结构时间报文100Mbps这种技术应用到现有的和将来的IPv6网络时间同步算法中去。参考文献：[1]D.LMills,“NetworkTimeProtocol(Version3)Specification,Implementation”,RFC1305,March1992.[2]贺鹏，李菁，吴海涛.网络时间同步算法研究与实现[J].计算机应用，2003，23（2）：15－17.[3]T.Nakashima;s.Ihara.AnExperimentalEvaluationoftheTotalCostofNTPTopology[J].IOIN152001,1