IEEE/ACM Transactions on Networking · 2011 · 15 citations · 22 references
ComputingComputer EngineeringComputer ScienceDistributed SystemsGrid ComputingParallel ComputingBroadcast CommunicationCollective CommunicationCommunication NetworksDistributed ComputingNetwork ReliabilityReliable Distributed SystemsBroadcast AlgorithmsDistributed Database ManagementGreedy ApproximationInteger Linear ProgrammingNetwork Reliability AlgorithmsReliable BroadcastSpanning Tree ConstructionSpanning Tree Protocol
In this paper, we study the problem of reliable collective communication (broadcast or gossip) with the objective of maximizing the reliability of the collective communication. The need for collective communication arises in many problems of parallel and distributed computing, including Grid or cloud computing and database management. We describe the network model, formulate the reliable collective communication problem, prove that the maximum reliable collective communication problem is NP-hard, and provide an integer linear program (ILP) formulation for the problem. We then provide a greedy approximation algorithm to construct collective communication (through a spanning tree) that achieves an approximation ratio of 1 + ln(| <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">V</i> |+α| <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">E</i> |-1) , where α is the average number of shared link risk groups (SRLGs) along links, and | <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">V</i> | and | <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">E</i> | are the total number of vertices and edges of the network, respectively. Simulations demonstrate that our approximation algorithm achieves good performance in both small and large networks and that, in almost 95% of total cases, our algorithm outperforms the modified minimum spanning tree algorithms.
22
New and Improved Approaches for Shared-Path Protection in WDM Mesh Networks
Canhui Ou, Jing Zhang, Hui Zang et al. · Journal of Lightwave Technology · 2004 · 234 citations
Ring routing and wavelength translation
Gordon Wilfong, Peter Winkler · 1998 · 146 citations