Research On Architecture And Algorithm Of End-to-end Delay Estimation Based On Topology

Network end-to-end delay measurement is the foundation of network performance monitoring, network behavior analysis, network application design, and measurement of delay jitter, network bandwidth and other performance indicators. But some problems exist in the present estimating techniques, such as the low estimation accuracy and the unreasonable deployment of checkpoint. Therefore, the research on accurate and quick delay estimation algorithm has become a hot research area, and it has significant research value.The current studies for delay estimation are mainly based on network structure and network coordinate. Since the methods based on network structure give adequate consideration in the network topology, routing and other internal network features, it has higher estimation accuracy.This paper firstly proposes three-layer delay estimation architecture based on network topology. The current delay algorithms based on network topology do not take into account the relationship between two RTT sequences which have common path to the same destination node. In order to study this relationship, the paper introduces the concept of RTT similarity. We simulate many different topology scenarios by changing the public and private path lengths in NS2network simulator, and obtain the relationship between path lengths and the RTT similarity. The results of simulations show that RTT similarity increases with the public path length. Then for each topology scenario, the parameters and of the delay estimation formula and estimation accuracy are obtained by linear regression analysis.Based on delay estimation architecture and the above analysis results, the paper puts forward an optimal selection algorithm of delay checkpoint. Firstly, we choose the checkpoint which can get the best estimation accuracy based on the simulation results. Secondly, we compute the estimated delay using slope and intercept of delay estimation in the corresponding topology scenario. In the end, we get the formula of delay estimation and the corresponding estimation accuracy. On this basis and according to different delay estimation accuracy, dynamic delay estimation algorithm is proposed.In the last part, the paper transforms the problem of selecting the smallest possible checkpoint set with the constraint of estimation accuracy to minimum vertex cover problem in polynomial time. And then we prove selection problem of delay checkpoint is a NP-complete problem. Finally, the approximate optimal algorithm is proposed based on greedy selection principles to estimate as many as paths every time, so we can obtain the approximate optimal checkpoint set.