On the Dependencies between Source Neighbors in Optimally DoS-stable P2P Streaming Topologies

We study tree-based peer-to-peer streaming topologies that minimize the maximum damage that can be caused by the failure of any number of peers. These optimally stable topologies can be characterized by a distinctive damage sequence. Although checking whether a given topology is optimally stable is a co-NP-complete problem, a large subclass of these topologies can be constructed by applying a simple set of rules. One of these rules states that every optimally stable topology must have optimally stable inter-dependencies between the nodes directly adjacent to the streaming source (called heads). However, until now, only a single stable head topology was known. In this article, we first give a short outline to previous results about optimally stable topologies. Then, we identify necessary and sufficient requirements for the optimal stability of head topologies, thereby largely increasing the number of known representatives from this class. All requirements can be checked in polynomial time. Furthermore, we show how to efficiently decide stability for head topologies with at most four stripes and give a procedure that, given a stable topology, produces a stable topology with an arbitrary number of stripes. Reversing this procedure can also speed up stability testing. Finally, we describe strategies how stable head topologies can be constructed in real-world streaming systems.