Theory And Method Of Network Delay Estimation Based On RTT Similarity

Network distance estimation algorithms and technology have been one of the hotresearch areas in network measurement and become more and more important withthe development of distributed systems. Network distance estimation makes distanceestimation between every two nodes based on some limit distance information, suchthat it can bring down the overhead of direct measurement made by independent hostsrespectively. According to specific application, network distance can be defined indifferent ways, such as delay, bandwidth, packets loss rate and so on. Among them,delay is mostly selected as the network distance for its multipurpose and easy tomeasure.Based on the technology related to delay estimation, we define the new conceptof RTT similarity and propose a new theory and method to estimate delay accordingto this definition. From the point of RTT similarity, study the characteristics of RTTsimilarity and design the method of delay estimation. At the same time, we study theaccuracy of the estimation based on RTT similarity and get the relationship betweenaccuracy and similarity, according to which we design the algorithms to fix up threeproblems in real delay estimation. The whole process and the three algorithms are allcheck by real and experimental data and all the results are satisfying.The main contributions are including the followings:1Based on the variance analysis theory, propose the method to analysis therelationship between RTT similarity and path length and get that the relationshipbetween them can be deduced as the relationship between RTT similarity and pathlength ratio and have the same changing trends with each other.Data analysis shows that RTT similarity is correlated with the overlap of the twopath as well as their different paths and define length ratio as the ratio of the commonpaths to the longer private paths. Based on variance analysis, through constructing thedifferent array, it can be verified that when fix the common and longer private pathlength, the changing of the length of short private path length will have no significanteffects on the similarity. And then, we further to verify that when the path lengthcombinations belong to the same length ratio, their similarities have no significantdifference among each other and have the mutational trends with length ratio.2Propose the method to calculate the RTT similarity based on length ratio andload ratio. With this method, we analyze the effects of the length and load on the RTTsimilarity and construct the corresponding values relationship among RTT similarityand length ratio as well as representative loads. We get the characteristics of RTT similarity according to loads through the studyof load effects on similarity. Based on the data analysis, we get that with the sametopology, similarity will get larger with the heavier of the common path load and willget smaller with the heavier of the private path loads. When the load is not beyond60%, similarities with the same load ratio have no significant difference among eachother and have the same change trends with load ratio. Making a compulsive analysisof the effects of path length and load, we get that the similarities have no significantdifference among each other with the same length ratio when the load ratio is1andthe similarity with the two private path lengths the same long is the minimal. And theloads of which the load ratios are1are the most representative ones according to thefactor analysis. So, using the load with load ratio of1as the network loads and thelength ratio as the path length and the minimal similarity of every length ratio as thesimilarity, we establish the relationship among similarity and path length as well asload condition, such that we can get the similarity when we know the lengths andloads. In this manner, we complete the conversion of RTT similarity from essence toexpression.3propose the method to estimate the RTT based on RTT similarity and use theRTT of one path to estimate the other one according the RTT similarity between themThe two RTT sequences exhibit a more obvious liner relationship with the largerof their similarity, so we model them as the linear relationship as a whole. Based onthis relationship, we can get the slop and interception of the linear regression equation.Through the study of the relationship between the coefficients and similarity, we getthat the conversion between them. So, using the similarity as a media, we make thecoefficients corresponding to the lengths and loads, so that we can get the linearregression equation for different topology and load conditions. Using realmeasurement data, we verify the estimation method and the results show it has highaccuracy.4propose the method to calculate the estimation accuracy based on RTTsimilarity and get that the estimation accuracy can be decided by the RTT similarity,and then according to the relationship between RTT similarity and estimationaccuracy, we design the dynamic delay estimation algorithm.Accuracy is calculated as the relative difference between estimation values andmeasurement values. We make the accuracy related to similarity through formulatransformation and call the accuracy calculated through the transform formula theestimation accuracy. First, we study the correlation between estimation accuracy and similarity and get that the two can be modeled as the linear relationship. So, based onthe relationship between similarity and length as well as load, we get the relationshipbetween estimation accuracy and length as well load through the linear relationshipbetween similarity and estimation accuracy. In this manner, we can get the estimationaccuracy when we know the network topology and load conditions. Based on therelationship, we design dynamic delay estimation algorithm to solve the problem ofthe dynamic monitor selection according to different estimation accuracy requirement.At last, we make a new experiment to verify the three algorithms and the results showthem are correct.