Research On Distributed Network Latency Measurement For The Internet Environment

With the development of Internet techniques, many Internet applications need tooptimize the time of the data transmission, in order to improve the Quality ofExperiences (QoE) of Internet users. As a result, measuring the network latencies withhigh efficiency between nodes participating in the data transmission process becomes animportant question. Distributed network-latency measurement techniques obtainpairwise latencies through the distributed collaboration of participating nodes, whichscales well. Existing distributed network-latency measurement techniques arecategorized into distributed network coordinate techniques and distributed networkproximity estimation techniques, and the latter can further be categorized intodistributed clustering techniques, distributed nearest-node-search techniques anddistributed K-nearest-node-search techniques. The large-scale and capacity-limitedInternet nodes and the dynamics of network latencies raise three basic requirements:(1)the ability of accurately measuring network latencies;(2) the ability of scalablymeasuring network latencies for different scales of nodes;(3) the ability of measuringnetwork latencies with low overhead. However, existing distributed network-latencymeasurement techniques fail to satisfy the requirements of the accuracy, scalability andlow overhead. According to the characteristics of the Internet environment, thisdissertation deeply studies distributed network coordinate techniques and distributednetwork proximity estimation techniques in the Internet environment. The mainresearch progress is as follows:Existing distributed network coordinate methods are impaired by the mutualinfluence of the coordinate errors of different nodes during the coordinate updateprocess, which causes the effect of the cumulative reinforcement of coordinate errors.According to the problem of lacking of the accuracy for existing methods, thisdissertation presents a distributed relative-coordinate matrix factorization methodnamed RMF for estimating pairwise network latencies in a distributed manner. Eachnode randomly initializes its own coordinate position, later periodically samples a groupof neighbors, and incrementally updates its own coordinate based on neighbors’ relativecoordinates. RMF improves the estimation accuracy with the advantage of eliminatingthe estimation errors by relative coordinates. Besides, RMF scales well based on adistributed coordinate updating process and decreases the bandwidth costs withlow-dimensional coordinates and a modest number of neighbors. Simulations andPlanetLab based experiments show that, compared to existing methods, RMF reducesthe estimation errors, scales well with increasing number of nodes and is stably accuratewhen nodes fail.For existing distributed clustering methods, the cluster-head nodes easily cause performance bottlenecks, and the clustering structure hardly represent the pairwiseproximity because of the heuristic rules for constructing clusters. According to theproblem of lacking of the scalability and accuracy, this dissertation proposes adistributed hierarchical matrix factorization method named HPM, for estimating thehierarchical clustering structure of Internet nodes with network coordinates in adistributed manner. Each node randomly initializes a coordinate position when joiningthe system, later periodically samples a group of neighbors, measures the layer numberin the hierarchical cluster with each neighbor, and incrementally updates its owncoordinate based on the coordinates of neighbors. HPM maps coordinate distances intooptimized layer numbers based on a distributed maximum margin matrix factorizationmethod, which improves the accuracy of computing the hierarchical clusters. Besides,HPM scales well with a distributed coordinate updating process, and incurs lowoverhead with low dimensional coordinates and modest neighborhood sets. Simulationsand PlanetLab based experiments show that, compared to existing hierarchicalclustering methods, HPM improves the clustering accuracy in two to nine times withlow bandwidth costs, scales well with increasing number of nodes and keeps to bestably accurate when nodes fail.Existing distributed nearest-node-search methods have a quite narrow coveragescope for the neighborhood and can hardly find the nearest neighbor to the target. As aresult, the search processes are trapped at the local minimum. Besides, the searchaccuracy degrades quickly with increasing number of targets. According to the problemof lacking of the accuracy and scalability for existing methods, this dissertationproposes a single-target distributed nearest-node-search method named HybridNN forlocating a node nearest to a single target, and a multi-target distributednearest-node-search method named DEB, for searching a node nearest to multipletargets. HybridNN recursively searches nodes nearer to a target with the inframetricmodel that helps accurately locate the nearest neighbor and scales well by thedistributed greedy search processes. DEB recursively search nodes that have shorteraverage RTTs to multiple targets with the proposed multi-target inframetric model thatscalably locates the neighbor nearest to the targets for different number of targets.Besides, this dissertation proposes a neighbor-sampling method that suits the clusteringcharacteristics of the network latency space. As a result, the coverage of the neighbors isimproved. This dissertation also uses network coordinates to reduce the search overheadof HybridNN and DEB. Simulations and PlanetLab based experiments show that,compared to existing methods, HybridNN significantly improves the single-targetsearch accuracy, reduces the search overhead and shortens the search time. DEBimproves the multi-target search accuracy, lowers the search overhead and the searchtime and keeps to be stably accurate with increasing number of targets.Existing distributed K-nearest-node-search methods have a quite narrow coverage scope for the neighborhood and are therefore easily trapped at the local minimum.Besides, the search accuracy degrades significantly with increasing number of nearestnodes. According to the problem of lacking of the accuracy and scalability for existingmethods, this dissertation proposes a single-target distributed K-nearest-node-searchmethod named DKNNS, and a multi-target distributed K-nearest-node-search methodcalled KDEB. DKNNS selects a node far away from the target based on thesingle-target farthest search, as the one starting the single-target distributednearest-node-search process. After obtaining each node nearest to the target, DKNNSbacktracks to the last-hop node of the search path and continues to search the rest nodesnearest to the target. DKNNS improves the possibility of locating a node closer to thesingle target after the backtracking process and improves the search scalability based onthe backtracking process. KDEB selects a node with large average latency to the targetsbased on the multi-target farthest search, as the one beginning the multi-targetdistributed nearest-node-search process. After finding a node nearest to the targets,KDEB backtracks to the last-hop node of the search path and continues to search theremaining nearest nodes. KDEB increases the possibility of locating a node with a loweraverage latency to the targets after backtracking and improves the search scalability bythe backtracking process. Simulations and PlanetLab based experiments show that,compared to existing methods, DKNNS significantly reduces the single-targetK-nearest-node-search errors, lowers the search overhead and shortens the search time;KDEB reduces the multi-target K-nearest-node-search errors, search overhead and thesearch time; besides, DKNNS and KDEB have stable search accuracy with increasingnumber of required nearest nodes.