A New Hierarchical Network Coordinate Algorithm Based on Community Structure

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. In order to improve the short distance prediction accuracy of traditional network coordinate algorithm such as Vivaldi, we propose 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 show that the new hierarchical network coordinate algorithm provides more accurate short distance predictions without degrading the accuracy of long distance predictions. Internet applications such as the nearest server selection will benefit from the more accurate prediction of short distance using this new hierarchical network coordinate algorithm.