The Research Of Domestic Host Location Based On The Improved Vivaldi Algorithm

Determining the geographical location of the host is an important network application service. At present, to get the host location is mainly by querying the mapping database from the IP to the actual geographical location. IP address database is not easy to build and maintain, because it is not update in time, its low coverage, its big particle size and other reasons, the position of the node provided by it is inaccurate. The existing geographical coordinates information system of hosts based on the network coordinates is build on the foundation of building a virtual network coordinate system, due to the impact of the reference node, coordinate dimension,"distortion delay" and triangle inequality violation an error generated between the predicted delay and the measured delay. Finally, when positioning the host location, in addition to the errors produced when minimizing the error function, due to the use of the delayed prediction of the virtual network coordinate system, the extended error is accumulated enlarge.This paper is mainly directed against the influence that the "distortion delay" and triangle inequality violation put on the performance of the virtual network coordinates system, and the problem that the error is accumulated enlarge when positioning the geographical position of the host. The content and outcome of the study include the following three aspects:(1) Due to the changes of the network status, network delay is changing at any time, and sometimes has a significant fluctuation or even a jump. If directly using the "distortion delay" value as the input delay, the coordinates position of the node location is misplaced and the delay predicted a poor performance, thus filtering the normal delay value from the round-trip time delay sample as the input delay is the basis of raising the prediction performance of the delay. This article describes and analyses the existing delay preprocessing algorithm and further puts forward the recursive point estimation delay filter (PRE-filter) algorithm.(2) Due to the network itself, especially the routing strategy, the network inevitably existing the triangle inequality violation phenomenon. The traditional algorithm to build a network coordinate system default strictly fulfill the constraints of the triangle inequality, resulting a low accuracy and stability of the system. By introducing triangular coefficient, this paper improves the Vivaldi algorithm to have a function of detecting and suppressing the triangle inequality violation.(3) Drawn from the previous study, the geographical distance has a proportional relationship with the network distance, so can choose a spherical geographical coordinates space as the geometric space which the network coordinate space embedded in, can use the delay information directly to build the host location positioning system, omit the intermediate step of constructing the network coordinates system, avoid the error is accumulated two times.PRE-filter algorithm derives from the experimental simulation, which is possible to suppress random noise pollution, to smooth the fluctuations of the time delay and to reflect the changes of the network topology in time. Its absolute error accumulation is less than the current widely used two delay pretreatment algorithms. PRE-filter algorithm improves the accuracy of the prediction of the virtual network coordinate system. The improved Vivaldi algorithm takes use of the reference node and the triangular coefficient to detect and judge the triangle inequality violation edges, and shorts the violation edges according to the value of the triangular coefficient when embedding, while stretches the violation edges when predicting. Finally, through the experimental simulations, we can conclude that the improved Vivaldi algorithm is more accurate than original Vivaldi algorithm. In this paper the range of experiment verifies the accuracy of the host location, and analyses the reasons of error and their corresponding solutions.