基于网络拓扑的端到端时延估测架构与算法的研究

发布时间：2019-01-12 09:25

【摘要】：网络时延测量是网络性能监测、网络行为分析、网络应用设计的基础，，也是测量时延抖动、网络带宽等网络性能指标的基础。但是现有的网络时延估算中还存在估算精度不高和检测点部署不合理的情况。因此如何准确、快速地进行网络时延估测已经成为网络时延估算领域的研究热点，具有重要的研究价值和现实意义。目前针对网络时延估算的研究主要包括基于网络结构和基于网络坐标的时延估算技术的研究。基于网络结构的估算技术由于充分考虑了网络的路由拓扑和路径选择等网络内部特性，具有较高的估测精度。本文主要对基于网络拓扑的时延估算进行研究，取得了如下研究成果：首先提出基于网络拓扑的三层时延估测架构。目前的基于网络拓扑的时延估算方法中没有考虑两个具有公有路径的RTT序列之间的关系。为了研究这种关系，本文引入RTT相似度的概念。在NS2网络仿真中通过改变网络拓扑中路径长度，分析了不同的路径长度与RTT相似度的关系，得到公有路径长度和RTT相似度的关系：公有路径越长，RTT相似度越大。然后，针对每种拓扑场景通过线性回归分析得到时延估算公式的参数和估算精度。在时延估测架构和仿真分析的基础上，本文提出一种从检测点集合中选择最优的时延检测点的时延估算模型。该模型首先通过网络的测量节点集合中选择所形成拓扑场景中估算精度最大的检测点，并利用对应拓扑场景的线性回归参数得到时延估算方程及估算精度。然后根据这些数据给出动态时延估算方法，该方法可以根据不同的估算精度要求动态地选取检测点进行时延估算，从而使时延估测系统更加灵活和高效。本文最后研究了针对不同的估测精度要求，确定尽可能小的检测点集合的问题。将时延检测点的选择问题在多项式时间内可以转化成最小顶点覆盖问题，证明该问题是NP完全问题。然后提出一种基于可估算路径最多的贪婪选择原则的贪婪算法，得到近似最优的检测点集合。
[Abstract]:Network delay measurement is the basis of network performance monitoring, network behavior analysis, network application design, and measurement of delay jitter, network bandwidth and other network performance indicators. However, in the existing network delay estimation, the estimation accuracy is not high and the detection point deployment is unreasonable. Therefore, how to estimate the network delay accurately and quickly has become a research hotspot in the field of network delay estimation, which has important research value and practical significance. At present, the research of network delay estimation mainly includes network structure and network coordinate based delay estimation technology. The estimation technology based on network structure has high estimation accuracy due to the full consideration of the network internal characteristics such as routing topology and path selection. In this paper, the time delay estimation based on network topology is studied, and the research results are as follows: firstly, a three-layer time-delay estimation architecture based on network topology is proposed. The relationship between two RTT sequences with public paths is not considered in the current network topology based delay estimation method. In order to study this relationship, this paper introduces the concept of RTT similarity. In NS2 network simulation, by changing the path length in network topology, the relationship between different path length and RTT similarity is analyzed, and the relationship between public path length and RTT similarity is obtained: the longer the public path, the greater the RTT similarity. Then, the parameters and accuracy of the time delay estimation formula are obtained by linear regression analysis for each topological scenario. On the basis of time delay estimation architecture and simulation analysis, this paper presents a time delay estimation model for selecting the best time delay detection points from the set of detection points. The model firstly selects the detection points with the highest estimation accuracy from the set of measurement nodes of the network and obtains the time delay estimation equation and the estimation accuracy by using the linear regression parameters of the corresponding topological scene. Then the dynamic time delay estimation method is given according to these data. The method can dynamically select the detection points to estimate the time delay according to different estimation accuracy requirements, thus making the time delay estimation system more flexible and efficient. Finally, the problem of determining the set of detection points as small as possible for different estimation accuracy requirements is studied. The problem of time delay detection point selection can be transformed into a minimum vertex covering problem in polynomial time. It is proved that the problem is a NP complete problem. Then a greedy algorithm based on the principle of greedy selection with the most estimable paths is proposed to obtain an approximate optimal set of detection points.
【学位授予单位】：北京工业大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP393.02

【参考文献】