A Hierarchical Network Coordinate Algorithm Based On Community Structure Detection

Network coordinate algorithm provides an efficient way to predict communication latency between hosts with limited measurements. Hosts are embedded into a coordinate space and assigned a set of coordinates which reflect their positions in the geometric space. The distance between the coordinates of two hosts can be a predictor of the actual communication latency between them.How to improve the prediction accuracy is a problem which challenges the practical applications of network coordinate algorithm. Large-scale distributed systems, such as peer-to-peer content distribution systems, will benefit from the more accurate prediction of communication latency.The dissertation analyzed two main categories of network coordinate algorithms, centralized network coordinate algorithms and distributed network coordinate algorithms, and discussed the factors that affect the accuracy of distance prediction. The main contributions of this dissertation are as follows:1. Proposed a new hierarchical network coordinate algorithm based on community structure detection. The whole network is organized into N-level hierarchies without any requirement of fixed nodes as infrastructure. Each host is assigned multiple coordinates corresponding to the N-level hierarchies so that different sets of coordinates satisfy different ranges of distance prediction. Simulation results showed that the new hierarchical network coordinate algorithm provides more accurate short distance predictions without degrading the accuracy of long distance predictions.2. Used Visual C# to design a simulator for network coordinate algorithms based on .NET platform. Embedded the network coordinate algorithms, which are implemented in C, into the simulator by calling the DLL of the C programs. Used hybrid programming of C# and Matlab to visually implement the simulation results in the coordinate space. Used this simulator to analyze the communication data from Planetlab and King blog.