An Algorithm of Establishing Network Coding-Based Two-Disjoint Path Multicast Tree
Huanlai Xing · Dianzi xuebao · 2010
To introduce network coding into all-optical multicast networks,a polynomial time algorithm of establishing network coding-based two-disjoint path multicast tree is presented in the paper.There are two major steps in the algorithm:firstly,determining a directed path between the source node and each destination node in the given multicast network according to the degree balance principle of the intermediated nodes.The traditional directed multicast tree is obtained by determining the directed paths between the source node and all destination nodes,and the out-degree of each intermediated nodes are reduced as small as possible.Secondly,confirming the second path between the source node and the destination nodes from each destination node to the source node according to the conflict-backtracking principle and keep the two paths are disjoint paths in the traditional directed multicast tree.The multicast tree which is established by the algorithm contains minimum number of coding nodes,and can well support the all-optical network coding in photonic domain.