Research On Backup Path Selection Approaches Based On Grid Quorum In Large Scale Distributed Systems

Recent years, the problem of communication performance and reliability in large scale distributed systems has drawn worldwide interest of researchers, in the computer networks domain. More and more works have demonstrated that the path diversity is an effective way for improving the end-to-end performance of network applications. If there are multiple paths between both sides of arbitrary communicating nodes pair, the path with the optimal performance would be selected as the default communicating path, while another one, which might be with similar performance or even better than the default one in some certain occasions, would be selected as the backup path. When the default path fails or occurs to performance degradation, such nodes pair could communicate through the backup path, in order to provide persistent, reliable, effective and rapid recovered communicating ability to the large scale distributed systems. Especially in military context,some critical operations has extremely strict demand on latency, such as situation information sharing in real time, corresponding among command and combat units, simulation training and counterwork, etc. The technology of backup path selection does help in military operations and activities.This Paper analyzed the three main challenges, including the accuracy of selected backup path, scalability and communication overhead, when migrating backup path selection mechanism in large scale distributed systems to the military context. Aiming to conquer these three challenges, this paper presents a family of new approaches for efficiently identifying an acceptable candidate path for every node pair in a full-mesh network with n nodes, hence considerably scaling the network. In prior techniques, every node frequently incurs . traffic overhead to probe all other nodes and broadcast its link state table to a small set of nodes. In contrast, in our approaches each node measures its links to only O√other nodes and transmits its measuring results to O√other nodes, where the two node sets are determined by the partial sampling schemes presented in this paper.Mathematic analysis and comprehensive simulations show that our approaches dramatically reduce the cost of per-node probing and communication to O while maintaining an acceptable candidate path, with the similar even better performance than the direct path, for every node pair with high probability. More precisely, our approaches based on the enhanced and rotational partial sampling schemes would be capable to increase such probability to about 65% and 85%, respectively. For many network applications, this is sufficiently high such that the increased scalability outweighs this drawback. In addition, it is not desirable to absolutely identify an outstanding candidate path for every node pair in reality, due to the variable link quality.