单向延迟测量中时钟动态性检测算法(英文)  

Detecting Clock Dynamics in One-Way Delay Measurement

作　　者：王俊峰[1] 杨建华[2] 周虹霞[3] 谢高岗[2] 周明天[1] 

机构地区：[1]电子科技大学计算机科学与工程学院,四川成都610054 [2]中国科学院计算技术研究所信息网络研究室,北京100080 [3]电子科技大学电子工程学院,四川成都610054

出　　处：《软件学报》2004年第4期584-593,共10页Journal of Software

基　　金：国家高技术研究发展计划(863);计算技术研究所青年基金~~

摘　　要：延迟是评价网络性能的重要指标,也是进行其他网络性能指标测量的基础.基于全球定位系统(GPS)的端到端(end-to-end)时钟同步是测量网络单向指标的常用方法,但是其代价昂贵且缺乏灵活性.在无端到端时钟同步机制下进行网络单向延迟指标测量的关键是消除时钟偏差效应的影响.基于对时间序列分段技术的分析,提出了一种新的时间序列分段标准与改进的分段算法,实现序列的自动聚类,其时间复杂度为O(N2).将该算法应用于检测端到端时钟的动态性,识别测量过程中时钟跳变和时钟频率调整位置,实现对网络单向延迟的测量,弱化了同类工作中对时钟动态性的严格假设.同时提出了基于滑动窗的在线实时时钟动态性检测算法.实际测试实验表明,该算法是行之有效的.A key issue in one-way delay measurement is the removal of relative clock offset in the situation of without external clock synchronization mechanisms for the end-to-end hosts. Most researches are based on the assumption that the clock skew retains constant and without clock adjustments and drifts during measurement. But in fact, it is found that end system clock might be subject to gradual or instantaneous clock adjustments and frequency adjustments in operation. With the time series segmentation technology, we discuss the detection of clock dynamics in one-way delay measurement. Two algorithms are proposed to estimate the relative clock offset in post facto and on-line mode respectively, while with only unidirectional probe packets. The computational complexity of the post facto algorithm is of order O(N2). Experiments show that these algorithms can provide reasonable clock dynamics detection and informative one-way delay estimation.

关 键 词：单向指标 时钟动态性 网络测量 时间序列分段 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]