Reliability Calculation of P2P Streaming Systems with Bottleneck Links

摘要

Let G be a network with node set V and link set E, where each link e in E is associated with capacity c(e) and failure probability p(e). Let D=(s, t, d) be a flow demand on G which requests that a video stream of bit rate d should be delivered from source node s to sink node t through network G. The reliability of network G with respect to flow demand D is the probability of surviving a subgraph of G which admits D under the probabilistic link failures determined by function p. This paper shows that if G contains a constant number of bottleneck links and if the given video stream is divided into constant number of sub-streams, we can calculate the reliability of G in O(2|||V||E|) time, where α|E| is the number of links in the maximum connected component obtained by removing bottleneck links. This is a significant improvement of a naive method which takes O(2|E||V||E|) time.