基于网络编码的双路径组播树生成算法

An Algorithm of Establishing Network Coding-Based Two-Disjoint Path Multicast Tree

为了将网络编码技术引入到全光组播网络中,提出了能够在多项式时间完成的基于网络编码的双路径组播树生成算法.该算法主要包括两大步骤:首先,从给定的组播网络中根据节点间度平衡的原则为源节点和每个目的节点之间确定一条有向路径,从而建立一棵传统有向树并保证有向树中任意节点的出度尽可能小,减少节点之间的关联性;其次,在所建立的传统有向树的基础上,从每一个目的节点到源节点根据冲突回溯原则建立源节点和每个目的节点之间的第二条路径,并保证源节点到任意目的节点间的两条路径为分离路径.算法中包含的约束原则能够保证所建立的双路径组播树包含最少的编码节点,从而使得所建立的组播树支持光域网络编码高效率实现,实现基于网络编码的全光组播并提升全光组播的性能.

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.