Tackling the Delay-Cost and Time-Cost Trade-Offs in Computation of Node-Protected Multicast Tree Pairs

摘要

While there are many algorithms for finding a node-protected pair of multicast trees in a graph, all of the existing algorithms suffer from two flaws: Firstly, existing algorithms either have a long running time or produce high-cost tree pairs (Time-Cost Trade-Off). Secondly, existing algorithms aim to produce a low-cost tree pair, but do not take delay constraints into account (Delay-Cost Trade-Off). We tackle these tradeoffs by introducing an iterative algorithm, which finds a low-delay tree pair very quickly and then iteratively seeks lower-cost pairs. We present a sequential version of our algorithm; as well as an architecture for implementing it in a computing cluster, along with the corresponding master-and slave-algorithms.rnIt turns out that the success percentage of our algorithm drops as the average node degree decreases, and as the share of multicast destination nodes increases. Fortunately, in these cases performance of the existing algorithms improves, which means that our algorithm complements the existing algorithms. Two additional benefits or our algorithm are: (1) it can be used in multi-homing scenarios with almost no modifications, and (2) it can be used in both directed and undirected graphs.