Optimizing overlay topology by reducing cut vertices
Xiaomei Liu, Li Xiao, Andrew Kreling, Yunhao Liu · 2006
Overlay networks provide base infrastructures for many areas including multimedia streaming and content distributions. Since most overlay networks are highly decentralized and self-organized, cut vertices may exist in such systems due to the lack of centralized management. A cut vertex is defined as a network node whose removal increases the number of network components. Failure of these nodes can break an overlay into a large number of disconnected components and greatly downgrade the upper layer services like media streaming. We propose here a distributed mechanism, CAM, which efficiently detects the cut vertices before they fail and neutralizes them into normal overlay nodes with slight overhead so that the possibility of network decomposition is minimized after they fail. We prove the correctness of this algorithm and evaluate the performance of our design through trace driven simulations.