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 trade-offs 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.
It 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.