单向延迟测量的在线实时时钟调整检测算法

在网络单向性能指标分析中,使用软件方法对单向延迟时间序列进行分析,在线检测时钟调整位置,消除端系统间的时钟偏差,实现在线时钟同步是提供准确网络单向测量的前提保证.根据端系统间单向时延的结构特征,分析时延在大扰动的情况下,使用滑动窗和自底向上算法进行在线实时时间序列分段来检测时钟调整,存在的分段不准确问题.提出一种基于离线分段和在线检测的时钟调整检测算法,其时间复杂度为O（w）,解决了对单向延迟的时间序列进行实时分段准确性低的问题.仿真及实际测试实验表明,该算法是行之有效的.     

一种高效频繁子图挖掘算法

由于在频繁项集和频繁序列上取得的成功,数据挖掘技术正在着手解决结构化模式挖掘问题--频繁子图挖掘.诸如化学、生物学、计算机网络和WWW等应用技术都需要挖掘此类模式.提出了一种频繁子图挖掘的新算法.该算法通过对频繁子树的扩展,避免了图挖掘过程中高代价的计算过程.目前最好的频繁子图挖掘算法的时间复杂性是O(n³·2ⁿ),其中,n是图集中的频繁边数.提出算法的时间复杂性是O〔2ⁿ·n^2.5／logn〕,性能提高了O(√n·logn)倍.实验结果也证实了这一理论分析.     

基于分形技术的数据流突变检测算法

数据流上的突变检测技术由于其在风险分析、网络监测、趋势分析等领域广阔的应用前景而受到学术界和工业界越来越多的关注.为了在数据流上检测多个滑动窗口上的单调聚集函数值和非单调聚集函数值的突变,提出了基于分形技术的构建单调搜索空间的突变检测算法.首先给出了数据流上的分段分形模型,进而基于该模型设计了突变检测算法.该算法能够将突变检测处理时间复杂度从O(m)降为O(logm)(m为需要被检测的滑动窗口数目).提出的两种新颖的分段分形模型能够准确     

一种基于拓扑势的网络社区发现方法

从数据场思想出发,提出了一种基于拓扑势的社区发现算法.该方法引入拓扑势描述网络节点间的相互作用,将每个社区视为拓扑势场的局部高势区,通过寻找被低势区域所分割的连通高势区域实现网络的社区划分.理论分析与实验结果表明,该方法无须用户指定社区个数等算法参数,能够揭示网络内在的社区结构及社区间具有不确定性的重叠节点现象.算法的时间复杂度为O(m+n^3/γ)～O(n²),n为网络节点数,m为边数,2<γ<3为一个常数.     

RNA二级结构预测中动态规划的优化和有效并行

基于最小自由能模型的方法是计算生物学中RNA二级结构预测的主要方法,而计算最小自由能的动态规划算法需要O(n⁴)的时间,其中n是RNA序列的长度.目前有两种降低时间复杂度的策略:限制二级结构中内部环的大小不超过k,得到O(n²×k²)算法;Lyngso方法根据环的能量规则,不限制环的大小,在O(n3)的时间内获得近似最优解.通过使用额外的O(n)的空间,计算内部环中的冗余计算大为减少,从而在同样不限制环大小的情况下,在O(n³)的时间内能够获得最优解.然而,优化后的算法仍然非常耗时,通过有效的负载平衡方法,在机群系统上实现并行程序.实验结果表明,并行程序获得了很好的加速比.     

具有O(n)消息复杂度的协调检查点设置算法

协调检查点设置及回卷恢复技术作为一种有效的容错手段,已广泛地运用在集群等并行/分布计算机系统中.为了进一步降低协调检查点设置的时间和空间开销,提出了一种基于消息计数的协调检查点设置算法.该算法无须对底层消息通道的FIFO特性进行假设,并使同步阶段引入的控制消息复杂度由通常的O(n²)降低到O(n),有效地提高了系统的效率和扩展性.     

光RP(k)网络上Hypercube通信模式的波长指派算法

波长指派是光网络设计的基本问题,设计波长指派算法是洞察光网络通信能力的基本方法.基于光RP(k)网络,讨论了其波长指派问题. 含有N=2ⁿ个节点的Hypercube通信模式,构造了节点间的一种排列次序Xn,并设计了RP(k)网络上的波长指派算法.在构造该算法的过程中,得到了在环网络上实现n维Hypercube通信模式的波长指派算法.这两个算法具有较高的嵌入效率.在RP(k)网络上,实现Hypercube通信模式需要max{2,「5(2^n-5/3」}个波长.而在环网络上,实现该通信模式需要复用(N/3+N/12(个波长,比已有算法需要复用「N/3+N/4」个波长有较大的改进.这两个算法对于光网络的设计具有较大的指导价值.     

复杂网络大数据中重叠社区检测算法

大数据时代互联网用户数量呈爆炸性增长,社交网络、电商交易网络等复杂网络规模快速发展,准确有效地检测复杂网络大数据中重叠社区结构对用户兴趣点推荐和热点传播具有重要意义。提出一种新的面向复杂网络大数据的重叠社区检测算法DOC（Detecting Overlapping Communities over complex network big data）,时间复杂度为O（nlog²（n））,算法基于模块度聚类和图计算思想应用新的节点和边的更新方法,利用平衡二叉树对模块度增量建立索引,基于模块度最优的思想设计一种新的重叠社区检测算法。相对于传统重叠节点检测算法,对每个节点分析的频率大大降低,可以在较低的算法运行时间下获得较高的识别准确率。复杂网络大数据集上的算法测试结果表明：DOC算法能够有效地检测出网络重叠社区,社区识别准确率较高,在大规模LFR基准数据集上其重叠社区检测标准化互信息指标NMI最高能达到0.97,重叠节点检测指标F-score的平均值在0.91以上,且复杂网络大数据下的运行时间明显优于传统算法。     

背包问题的最优并行算法

利用分治策略,提出一种基于SIMD共享存储计算机模型的并行背包问题求解算法.算法允许使用O(2^n/4)^1-ε个并行处理机单元,0≤ε≤1,O(2^n/2)个存储单元,在O(2^n/4(2^n/4)^ε)时间内求解n维背包问题,算法的成本为O(2^n/2).将提出的算法与已有文献结论进行对比表明,该算法改进了已有文献的相应结果,是求解背包问题的成本最优并行算法.同时还指出了相关文献主要结论的错误.     

半动态矩形交查询算法

本文讨论了动态矩形交查询算法.文中介绍了两个半动态矩形查询的新算法，它们分别基于一维数据结构和二维数据结构.一维查询算法的查询时间复杂度是O（logM＋k′），更新时间复杂度是O（logMlogn），空间复杂度是O（nlogM/）.二维查询算法的查询时间复杂度是O（log²M＋k），更新时间复杂度是O（log²Mlogn），空间复杂度是O（nlog²M）.本文分别实现了这两个算法，通过对它们的性能进行比较，发现一维查询算法是一种高效、实用的算法.     

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.     

网络主机时钟相对漂移模型研究

时钟同步是网络测量、管理的要求,由于时钟漂移现象的存在,难以实现精确的时钟同步。论文采用相对时钟代替绝对时钟,分析主机时钟相对漂移,建立了主机时钟相对漂移的线性模型,并由此推导出单向延迟修正模型。通过局域网范围内的主机时钟相对漂移和东南大学和瑞士之间的国际信道两端主机时钟漂移建立模型发现,相对漂移线性模型能很好地反映时钟漂移现象,并能够对两主机间的单向延迟进行修正。以相对时钟代替绝对时钟大大提高了时钟测量精度,减少了时钟同步的次数,降低了网络带宽的负担和主机资源的利用。     

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

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

面向单向延迟测量的时钟同步技术研究

为测量网络传输中的单向延迟等性能参数以准确提供和分析网络的性能状况,时钟同步的精度要求已非时钟同步协议(NTP)所能完成。该文对近年来出现的各种针对此问题的时钟同步技术研究和实现展开综述性陈述,并在此基础上提出Altair&Vega(A&V)方法。该方法修正了Moon方法中理论推导的欠妥之处,建立两主机之间同步模型,能提供高精度的相对时钟偏移修正。     

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

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

Low-complexity time synchronization for energy-constrained wireless sensor networks: Dual-Clock delayed-message approach

Due to the ability of sensor nodes to collaborate, time synchronization is essential for many sensor network operations. With the aid of hardware capabilities, this work presents a novel time synchronization method, which employs a dual-clock delayed-message approach, for energy-constrained wireless sensor networks (WSNs). To conserve WSN energy, this study adopts the flooding time synchronization scheme based on one-way timing messages. Via the proposed approach, the maximum-likelihood (ML) estimation of time parameters, such as clock skew and clock offset, can be obtained for time synchronization. Additionally, with the proposed scheme, the clock skew and offset estimation problem will be transformed into a problem independent of random delay and propagation delay. The ML estimation of link propagation delay, which can be used for localization systems in the proposed scenario, is also obtained. In addition to good performance, the proposed method has low complexity.     

BOND:一种双向的单路网络延时测量方法

用软件的方法进行单路网络延时的精确测量，需要解决两个端系统的时钟异步问题．现有的测量算法(如Ping和LPA)在测量精度和实时性方面存在着明显的不足，针对这些问题，本文提出一种双向的单路网络延时测量方法，新的延时测量算法对LPA算法进行了改进．实验结果表明，双向单路网络延时测量方法是一种十分有效的延时测量算法，特别适合于工程应用。     

一种用于估计测量设备之间时间偏差的算法

该文分析了单向时延测量的必要性,并指出测量设备之间存在的时间偏差给时延测量带来了误差;该文提出一种算法用来估计测量设备间存在的时间偏差,利用算法估计的时间偏差来校正测量结果,达到准确测量单向时延的目的。仿真验证了估计算法的准确性。     

Wait-Free Clock Synchronization

Multiprocessor computer systems are becoming increasingly important as vehicles for solving computationally expensive problems. Synchronization among the processors is achieved with a variety of clock configurations. A new notion of fault-tolerance for clock synchronization algorithms is defined, tailored to the requirements and failure patterns of shared memory multiprocessors. Algorithms in this class can tolerate any number of napping processors, where a napping processor can fail by repeatedly ceasing operation for an arbitrary time interval and then resume operation without necessarily recognizing that a fault has occurred. These algorithms guarantee that, for some fixed k, once a processor P has been working correctly for at least k time, then as long as P continues to work correctly, (1) P does not adjust its clock, and (2) P's clock agrees with the clock of every other processor that has also been working correctly for at least k time. Because a working processor must synchronize in a fixed amount of time regardless of the actions of the other processors, these algorithms are called wait-free. Another useful type of fault-tolerance is called self-stabilization: starting with an arbitrary state of the system, a self-stabilizing algorithm eventually reaches a point after which it correctly performs its task. Two wait-free clock synchronization algorithms are presented for a model with global clock pulses. The first one is self-stabilizing; the second one is not but it converges more quickly than the first one. The self-stabilizing algorithm requires each processor's communication register contents to be a part of the processor's state. This last requirement is proven necessary. A wait-free clock synchronization algorithm is also presented for a model with local clock pulses. This algorithm is not self-stabilizing. Received December 20, 1993; revised January 1995.