基于PLE的有确定解的端到端网络链路时延推测方法

网络时延是重要的网络性能指标,端到端网络时延推测能够克服传统的基于路由器或者路由器协作的网络测量技术的弊端。在网络拓扑已知且稳定和链路性能时空独立性的假设前提下,给出了网络链路时延推测模型,提出了一种基于伪似然估计(PLE)的有确定解的端到端网络链路时延推测方法。在应用期望最大化算法的伪似然估计的基础上,控制背靠背发包方式,确定可以求解的探测单元,解决了不满足有确定解拓扑下的求解问题,且有效降低了计算复杂度。最后利用基于模型的计算验证了该方法的准确性和有效性。     

主动端到端离散式时延分布估计方法研究

对于网络质量评估链路性能推测无疑是至关重要的,然而现有的估计方法通常只能推测层次数有限的简单网络,无法应用于大规模网络。提出了一种基于不完整数据极大似然估计算法,估计网络内部链路时延分布,该方法通过不同的发包策略将树状网络拓扑划分成不同的两层三链子树,针对每个子树估计每条＂链＂的时延,随后通过移植算法将路径时延划分到各链路中,逐一对每个子树使用该方法计算从而得到整个网络链路时延情况。利用NS2仿真实验验证了该算法的可行性和准确性。     

一种基于多播推测丢包率的算法

网络层析是近年新兴的一个网络研究领域,它利用端到端的性能测试结果推导网络内部性能特征或拓扑结构,克服了传统网络测量技术的一些缺陷.丢包率层析的主要方法是利用最大似然估计(MLE),但是计算复杂度高且计算时间较长;基于伪似然估计(PMLE)方法可以较快估计各链路丢包率,但是在非叶节点链路的误差较大.为了克服以上缺点,本文基于多播网络的端对端测量,结合MLE和PMLE提出一种推算网络内部各链路的丢包率算法.通过仿真证实该算法估测的结果能真实地反应网络内部丢包趋势,在推测精度较好的情况下,计算量减少,计算复杂度降低.     

网络链路时延分布估计方法研究

网络内部链路性能推测对网络操作与评估至关重要,现有估计方法通常针对固定拓扑网络,无法应用于动态路由情形下的未知拓扑网络。提出了一种基于伪似然估计（PLE）和遗传程序设计（GP）的网络延迟断层扫描方法估计网络内部链路延迟分布,并利用重要抽样（IS）技术进一步改进链路延迟分布估计。最后利用仿真实验验证了该方法的有效性和准确性。     

一种自底向上的推测链路延迟分布的快速算法*

网络层析技术用端到端的测量结果来推测网络中的链路延迟分布。这方面已有的大部分工作都基于最大似然估计式 (MLE)和期望最大化（EM）算法,它们在求解过程中需要不断迭代,对于大规模网络需要消耗很长的时间。为了克服这方面的不足,提出了一种快速算法FBA,该算法自底向上估计出每层链路的延迟分布。定性的分析和实验仿真结果表明FBA大大减小了计算的复杂度,而且在发包数目足够多的情况下,它的估计结果的精确度接近EM算法。     

一种基于端到端测量构造网络性能拓扑的方法*

分析了分布式应用与网络性能拓扑结构的关系,以及利用端到端测量进行拓扑划分的可行性和实用性;然后通过测量瓶颈链路的方法对节点进行分组划分以缩小集合节点个数,再具体分析利用性能相关性探测节点集合的树型拓扑结构;最后通过实验模拟检验了这一拓扑探测方法.     

基于因子图—和积算法的故障链路诊断

为求得网络内部链路的先验故障概率,提出一种估计链路状态分布的新方法。采用因子图模型描述链路状态和路径状态间的联合概率分布,并使用和积算法求得各链路状态的最大后验估计,然后利用估计出的链路故障概率和当前测量数据推断链路的当前状态。仿真结果表明,当网络规模达到400个节点时,所提方法的计算时间比联立方程组求解法低两个数量级以上,具有更好的可扩展性。     

基于包对推测丢包率的简化算法

在进行网络测量时，有时只能获得端到端的数据，然而得到网络内部的信息对网络性能的认识是非常重要的，因此就需要从网络端到端测量得到的数据推测网络内部链路的数据。本算法是基于单播网络的端到端测量的，利用包对进行统计，运用最大似然估计和EM算法进行计算，从而推算网络内部节点的丢包率。我们在文中给出了算法的逻辑分析和仿真结果。     

基于路由数目的通信链路重要性分析

为了分析通信网络中通信链路对端到端通信的重要程度,提出一种基于路由数目的链路重要性计算方法。该方法采用一种快速算法,寻找出端到端的所有通信路由,再通过比较不同通信链路的损坏使端到端之间传输路由减少的数目,判断不同通信链路对端到端通信的重要性,如果某通信链路损坏导致路由减少越多,则该链路越重要。计算实例表明,该方法计算简单,易于编程实现,具有一定的实用性和有效性。     

改进的基于最大似然的快速拓扑估计方法

基于最大似然的网络拓扑估计方法能够获得全局最优的估计结果,优于一般局部最优化和节点对融合方法,但在网络规模较大时存在计算复杂度较高的缺点。首先证明了网络拓扑估计似然函数是单峰的（即只有一个极值）且峰值为最大值;然后利用单峰特征,改进了现有基于最大似然的拓扑估计方法,在最大似然树搜索过程中无需返回到似然值小的状态,降低了计算复杂度。最后,Matlab和ns-2仿真结果证明在不降低拓扑估计准确率的情况下,改进的算法将计算复杂度减少了30%~46%.     

基于生成树算法的链路层拓扑发现研究

随着大规模交换网络的发展,网络拓扑发现的研究由网络层拓展到数据链路层。链路层的拓扑发现能够发现网络层拓扑发现无法发现的局域网内部的详细的物理连接情况,对网络配置管理具有重要意义。研究了目前基于地址转发表（AFT）的方法,针对现有算法的不足作了一定分析,提出了一种基于生成树算法（STA）的链路层网络拓扑发现算法,利用SNMP获得网桥MIB中的生成树信息,通过分析这些信息计算出链路层的网络拓扑。该算法相比其它算法更简单、高效,有应用价值。     

基于XML的完全频繁查询模式挖掘算法

使用树结构建模对XML查询进行研究,提出了一种基于树同构的查询包含检测方法。采用最右分枝扩展方法,系统地枚举查询模式树的同根子树。在枚举过程中,采用Diffset结构记录包含同根子树的事务集的查询事务标识,并给出挖掘算法DiffFRSTMiner。实验结果证实了该算法合理、高效,并可以减少一定的内存开销。     

Opportunity-Based Topology Control in Wireless Sensor Networks

Topology control is an effective method to improve the energy efficiency of wireless sensor networks (WSNs). Traditional approaches are based on the assumption that a pair of nodes is either "connected” or "disconnected.” These approaches are called connectivity-based topology control. In real environments, however, there are many intermittently connected wireless links called lossy links. Taking a succeeded lossy link as an advantage, we are able to construct more energy-efficient topologies. Toward this end, we propose a novel opportunity-based topology control. We show that opportunity-based topology control is a problem of NP-hard. To address this problem in a practical way, we design a fully distributed algorithm called CONREAP based on reliability theory. We prove that CONREAP has a guaranteed performance. The worst running time is O(vert Evert ), where E is the link set of the original topology, and the space requirement for individual nodes is O(d), where d is the node degree. To evaluate the performance of CONREAP, we design and implement a prototype system consisting of 50 Berkeley Mica2 motes. We also conducted comprehensive simulations. Experimental results show that compared with the connectivity-based topology control algorithms, CONREAP can improve the energy efficiency of a network up to six times.     

Identifying lossy links in wired/wireless networks by exploiting sparse characteristics

In this paper, we consider the problem of estimating link loss rates based on end-to-end path loss rates in order to identify lossy links on the network. We first derive a maximum likelihood estimate for the problem and show that the problem boils down to the matrix inversion problem for an under-determined system of linear equations. Without any prior knowledge of the statistics of packet loss rates, most of the existing work uses the minimum norm solution for the under-determined linear system. We devise, under the assumption that link failures are abnormal events in real networks and lossy links are sparse among all the internal links, an iterative algorithm to identify non-lossy links and to remove the corresponding terms from the under-determined linear system. To identify non-lossy links, we propose to use three different criteria (and a combination thereof): the criterion determined by a basis selection technique, that obtained by sorting path loss rates, and that determined by the minimum norm least square solution. We show via simulation and empirical studies on the MIT Roofnet traces that the computational complexity of the iterative algorithm is comparable to that of the minimum norm least square approach, and that the solution obtained under the iterative algorithm achieves high coverage of lossy links, while incurring only a small number of false positives in various network scenarios.     

一种新的频繁子树挖掘算法研究与实现

为提高频繁子树挖掘算法效率,结合原有频繁子树挖掘算法FSubtreeM的相关技术提出了新的全局树引导结构及其相关引理,并证明了其正确性.最后提出了新的频繁子树挖掘算法FSM_CGTG,并通过实验证明了该算法在现实数据集上的有效性且比现有频繁子树挖掘算法FSubtreeM性能优越.     

基于生成树的链路层拓扑发现算法

随着大规模交换网络的发展，网络拓扑发现的研究由网络层拓展到数据链路层。链路层的拓扑发现能够发现网络层拓扑发现无法发现的局域网内部的详细的物理连接情况。该文提出了一种基于生成树算法的链路层网络拓扑发现算法，利用SNMP获得网桥MIB中的生成树信息，通过分析这些信息计算出链路层的网络拓扑，该算法相比其它算法更简单、高效，有应用价值。     

动态数据库中的频繁子树挖掘算法

针对动态数据库随时间发生改变的特性,提出了一种新的在动态数据库中挖掘频繁子树的算法,引入树的转变概率、子树期望支持度和子树动态支持度等概念,提出了动态数据库中的支持度计算方法和子树搜索空间,从而解决了数据动态变化的频繁子树挖掘问题。随着子树搜索的进行,算法定义裁剪公式和混合数据结构,能有效地减少子树搜索空间和提高频繁子树的同构速度。实验结果表明,新算法有效可行,且具有较好的运行效率。     

Finding a k-tree core and a k-tree center of a tree network inparallel

A k-tree core of a tree network is a subtree with exactly k leaves that minimizes the total distance from vertices to the subtree. A k-tree center of a tree network is a subtree with exactly k leaves that minimizes the distance from the farthest vertex to the subtree. In this paper, two efficient parallel algorithms are proposed for finding a k-tree core and a k-tree center of a tree network, respectively. Both the proposed algorithms perform on the EREW PRAM in O(log n log n) time using O(n) work (time-processor product). Besides being efficient on the EREW PRAM, in the sequential case, our algorithm for finding a k-tree core of a tree network improves the two algorithms previously proposed     

Mining rooted ordered trees under subtree homeomorphism

Mining frequent tree patterns has many applications in different areas such as XML data, bioinformatics and World Wide Web. The crucial step in frequent pattern mining is frequency counting, which involves a matching operator to find occurrences (instances) of a tree pattern in a given collection of trees. A widely used matching operator for tree-structured data is subtree homeomorphism, where an edge in the tree pattern is mapped onto an ancestor-descendant relationship in the given tree. Tree patterns that are frequent under subtree homeomorphism are usually called embedded patterns. In this paper, we present an efficient algorithm for subtree homeomorphism with application to frequent pattern mining. We propose a compact data-structure, called occ, which stores only information about the rightmost paths of occurrences and hence can encode and represent several occurrences of a tree pattern. We then define efficient join operations on the occ data-structure, which help us count occurrences of tree patterns according to occurrences of their proper subtrees. Based on the proposed subtree homeomorphism method, we develop an effective pattern mining algorithm, called TPMiner. We evaluate the efficiency of TPMiner on several real-world and synthetic datasets. Our extensive experiments confirm that TPMiner always outperforms well-known existing algorithms, and in several cases the improvement with respect to existing algorithms is significant.