单向延迟测量中时钟动态性检测算法

延迟是评价网络性能的重要指标,也是进行其他网络性能指标测量的基础.基于全球定位系统(GPS)的端到端(end-to-end)时钟同步是测量网络单向指标的常用方法,但是其代价昂贵且缺乏灵活性.在无端到端时钟同步机制下进行网络单向延迟指标测量的关键是消除时钟偏差效应的影响.基于对时间序列分段技术的分析,提出了一种新的时间序列分段标准与改进的分段算法,实现序列的自动聚类,其时间复杂度为O(N²).将该算法应用于检测端到端时钟的动态性,识别测量过程中时钟跳变和时钟频率调整位置,实现对网络单向延迟的测量,弱化了同类工作中对时钟动态性的严格假设.同时提出了基于滑动窗的在线实时时钟动态性检测算法.实际测试实验表明,该算法是行之有效的.     

基于分段过滤时间同步算法研究

随着通信及计算机网络的发展,越来越多的网络设备和网络应用对同步时间提出了越来越高的要求。但迄今为止端系统间的时间同步并没有得到很好的解决。首先系统描述了端系统时钟动态性的数学模型,然后提出了一种基于分段过滤的时间同步算法(SFTS算法)。该算法包含服务器主动式时钟同步算法,基于分段估算的频率差补偿算法,排队与频率跳变过滤算法三个部分。最后在实验网上对该算法进行了验证,并与NTP协议进行了对比。实验结果表明该算法确实能够实现大规模计算机间的高精度时间同步。     

基于Internet的实时机器人系统时延预测研究及算法

针对基于Internet实时机器人系统，提出了多尺度的时延预测算法，该算法是在线和实时的。基于网络结构分析了网络时延的主要组成及其时延特性。不同于传统的网络往返时延的预测，该算法预测的是能真实反映端对端数据包传递的单程时延，而且还提出了预测单向时延所需的时钟同步算法。理论分析和多点之间的网络实验验证了该算法的高效性。     

单向时延测量的时钟同步技术及测量方法

单向时延测量是分析和评价网络端到端性能的重要参数,主机之间的时钟偏移和时钟频差会给单向时延测量引入不可忽视的误差.针对传统消除时钟频差中线性规划法对误差判别和处理数据量的不足,提出了极限类比的方法来估计时钟频差系数,并采用类PTP技术构造时钟同步来消除时钟偏移对测量结果的影响,本方法相比传统线性规划法有计算复杂度小、计算快捷的优点,在网络时延固定变化时,该方法更能准确反映网络时延变化,最后针对实际的网络时延测量结果进行了分析,验证了该方法的通用性和可行性.     

Internet网络时延测量中的时钟同步算法

针对单向网络性能测量过程中存在的时钟同步问题，提出了基于法向距离最小的优化目标。该文根据优化目标推导了时钟同步优化算法，从而提高单向网络时延测量的精确性。并针对一个实际的网络时延测量结果进行了分析，验证了该算法的有效性。     

时延测量中估算时钟时滞的方法

时延测量是分析网络性能的一个重要因素。在实际测量中,由于终端系统的时钟不能完全同步,尤其是存在时钟时滞,将导致时延测量的不精确性,严重的会误导对网络性能的分析。本文通过对时延测量,特别是对单向时延的具体研究,提出了一种行之有效的且较为简单的时钟时滞的估算算法,并验证了算法的可行性和总结了它的优点。     

基于高精度性能计数器的网络单向时延研究

区别于常规的消除时钟偏差和时钟频差的网络单向时延测量方法,提出一种新的单向时延测量方法.利用两主机的高精度性能计数器的相对关系,推导出基于高精度性能计数器的网络单向时延表达式,为了估算表达式中的待定项,在两主机之间建立TCP连接,周期性双方向交换性能计数器信息,通过包对理论,定时更新时延表达式中的待定项.结果显示,该方法完全不需要主机之间的时钟同步,具有精度高、可在线测量的优点,同时,它提供了一种非对称网络环境下单向时延测量的手段.     

基于航电总线的分布式实时监控系统同步算法

随着航空技术、计算机软硬件技术的高速发展,航电综合系统的高精度时钟同步越来越重要,针对多总线分布式实时监控系统要求各设备高度时间同步的问题,本文在分析国内外已有时钟同步算法的基础之上综合考虑了传输时延、时钟偏移误差及网络排队时延,并将实时监控流量带来的网络抖动现象作为重要因素引入到同步算法中,设计了基于TSC的高精度软时钟服务机制,提出一种基于航电总线的分布式实时监控系统时钟同步算法CSA-RTMS,并详细分析了误差范围等性能.实验结果表明,与传统的NTP同步协议相比,该同步方法精度更高,同步效率快,而且受网络抖动影响小.     

风电场SCADA系统时间同步技术研究

为了实现风电场SCADA系统的时钟同步,提出了基于物理层物理介质无关接口的时钟同步方法.详细分析了分布式网络主从节点间实现时间同步的过程,提出了基于介质无关接口准确获取网络数据帧离开和到达时刻的时间同步方法,通过对各从节点相对主节点的频率偏差修正、往返法测量链路时延以及实时计算交换时延补偿交换时延的不确定性,实现了主节点到从节点的高精度时间同步.试验证明,基于介质无关接口的开环时间传递能够实现25ns的高精度时钟同步.     

一种海量实时序列数据指数平滑预测分割算法*

时间序列分割是时间序列挖掘的重要任务之一。实时数据快速变化,数据量巨大,所以如何对实时数据进行快速而准确的分割很具有挑战性。本文提出基于指数平滑预测的滑动时间窗分割算法可以快速有效的分割在线实时数据,该算法基于滑动窗口和平滑指数算法,分析实时数据的统计特性,推导出序列的预测误差和压缩率之间的关系,通过序列预测的误差来判断分割点。加入校验环节提高算法的健壮性。通过本课题所使用的数据集以及公共数据集验证算法结果说明,该算法能够有效地在线检测出实时数据的分割点,并且时间复杂度较低。     

Clock synchronization for Internet measurements: a clustering algorithm

Clock synchronization is a crucial issue for scalable and accurate network performance measurements, especially when no external time sources are introduced. The paper presents a clustering based efficient and robust algorithm Optimized Top-Down Time series Segmentation (OTDTS) for clock synchronization between end-to-end systems. The computational complexity of OTDTS is of order O(KN²). Based on the one-way probe delay traces, the algorithm segments the delay time series at proper points, at which clock dynamics occur. End systems could achieve relative clock synchronization by estimating and removing the clock skew of each segment. Simulations on artificial data set and practical Internet measurement illustrate the availability and efficiency of OTDTS.     

IEEE 1588v2基于透明时钟的误差分析与修正

针对时间同步过程中出现积聚性错误,导致同步精度降低的问题,通过对误差来源和透明时钟工作原理的分析,结合IEEE 1588v2时间同步协议的延时请求应答机制和对等延时机制,归纳了一整套基于透明时钟的频率补偿和误差修正方法。测试结果表明,经过频率和相位的双重调节,主从时钟的同步精度可以达到亚微秒级别,完全满足高精度同步系统的要求。     

基于通用PC架构的高精度网络时延测量方法

时延是准确测量时延抖动、带宽等网络性能指标的基础.目前的时延测量方法由于存在时钟误差和位置误差因而精度较差.提出一种改进的时延测量方法,以TSC(time stamp counter)寄存器取代系统时钟计时来消除测量的时钟误差,将时间戳记录位置由应用程序转移到网卡驱动来消除位置误差,极大地提高了时延测量精度.实验结果表明,与传统方法相比,不同包长度下,所提出的方法可降低测量误差21%～150%,且测量结果稳定,对系统吞吐量基本无影响.该方法基于通用PC架构,测量成本低,适于普遍采用.     

VOIP动态缓出时延算法研究分析

在以包为单位进行数据传输合、语音应用程序(VOIP,Voice Over Internet Protocol)中,为了补偿数据包在网络传输中不可预知的网络传输延迟,在接收端首先必须把接收到的数据包缓存起来,缓存一定的时间再播放出来,以减少通话的抖动,得到比较满意的通话质量。文章主要研究动态缓出时延算法,力求使这个缓出时延尽可能小,同时尽可能减少包的丢失率。文章提出了一个有效动态缓出时延算法,该算法主要跟踪最近到达的数据包的网络传输时延求出其近似分布函数,并利用这些信息和延迟峰的侦测算法预测下一个语音峰的缓出时延。实验结果表明利用该算法可以在缓出时延和包丢失率之间达到最佳平衡,是一种理想、有效的算法。     

Packet audio playout delay adjustment: performance bounds and algorithms

In packet audio applications, packets are buffered at a receiving site and their playout delayed in order to compensate for variable network delays. In this paper, we consider the problem of adaptively adjusting the playout delay in order to keep this delay as small as possible, while at the same time avoiding excessive “loss” due to the arrival of packets at the receiver after their playout time has already passed. The contributions of this paper are twofold. First, given a trace of packet audio receptions at a receiver, we present efficient algorithms for computing a bound on the achievable performance of any playout delay adjustment algorithm. More precisely, we compute upper and lower bounds (which are shown to be tight for the range of loss and delay values of interest) on the optimum (minimum) average playout delay for a given number of packet losses (due to late arrivals) at the receiver for that trace. Second, we present a new adaptive delay adjustment algorithm that tracks the network delay of recently received packets and efficiently maintains delay percentile information. This information, together with a “delay spike” detection algorithm based on (but extending) our earlier work, is used to dynamically adjust talkspurt playout delay. We show that this algorithm outperforms existing delay adjustment algorithms over a number of measured audio delay traces and performs close to the theoretical optimum over a range of parameter values of interest.     

A fuzzy-based approach to remove clock skew and reset from one-way delay measurement

One-way delay (OWD) traces are important measurements for analyzing end-to-end performance on the Internet. It is still a great challenge to provide a scalable solution for large-scale OWD measurement. Because the clocks at end systems are usually not synchronized, the OWD measurements are often inaccurate. For the more challenging case with clock resets to some reference times during the measurement, the OWD measurements are more inaccurate. Furthermore, the measurement data often exhibit considerable network-induced noise when the network is heavily loaded. All the existing OWD measurement techniques, such as linear programming and convex-hull approach (CHA), try to solve this problem by deterministic mathematics model. However, they often fail to distinguish clock resets from temporary Internet congestion. Based on the fuzzy-clustering analysis, this paper proposes a new algorithm to estimate and remove the clock skews and resets from measurement results. This algorithm has been implemented as a tool called fuzzy-based OWD corrector (FOC). The paper then presents OWD measurements of several Internet paths using FOC. Numerical experiments demonstrate that FOC is more accurate and robust than the existing techniques. FOCs computation complexity O(N) is similar to that of CHA and its computing time is much less than that of convex-hull technique.     

Heuristics for search sequencing under time-dependent probabilities of existence

We consider the problem of determining a route of a search resource to search visually multiple areas in which targets are expected to be located. It is assumed that the probability a target exists in each area is given as a result of target detection operations and that the probability decreases as time passes. It is necessary to search the areas using a search resource, and identify the exact locations of the targets. We propose heuristic algorithms including a simulated annealing (SA) algorithm for the search sequencing problem. Since the search sequence must be determined as quickly as possible not to delay the search, heuristics for search sequencing should not take too much time. We introduce a new neighborhood generation method and a new parameter for an easier control of the overall computation time in the SA algorithm. A series of computational experiments is performed for evaluating the suggested algorithms, and results are reported.     

Performing event detection in time series with SwiftEvent: an algorithm with supervised learning of detection criteria

The automated detection of points in a time series with a special meaning to a user, commonly referred to as the detection of events, is an important aspect of temporal data mining. These events often are points in a time series that can be peaks, level changes, sudden changes of spectral characteristics, etc. Fast algorithms are needed for event detection for online applications or applications with huge time series data sets. In this article, we present a very fast algorithm for event detection that learns detection criteria from labeled sample time series (i.e., time series where events are marked). This algorithm is based on fast transformations of time series into low-dimensional feature spaces and probabilistic modeling techniques to identify criteria in a supervised manner. Events are then found in one, single fast pass over the signal (therefore, the algorithm is called SwiftEvent) by evaluating learned thresholds on Mahalanobis distances in the feature space. We analyze the run-time complexity of SwiftEvent and demonstrate its application in some use cases with artificial and real-world data sets in comparison with other state-of-the-art techniques.     

基于分组转发状况的车载自组织网络路由算法研究

路由协议算法是车载自组织网络的一个重要研究方向.目前多数车载自组织网络路由协议算法根据一些间接表征因素(如源到目的节点的最短距离、车流量密度等)来判断最优转发路径,但是这些表征因素还都停留在理论假设阶段,能否反应真实的路况、表示实事上最优的路径并无定论.提出一种基于分组转发状况的车载自组织网络路由协议算法,旨在根据分组...