Abstract:

A heuristic algorithm of establishing a minimum coding nodes multicast tree which supports two-channel all-optical network coding scheme is presented. To minimize the coding nodes, the heuristic graph-search control strategies are investigated. Firstly, a minimum relatedness principle is proposed to balance and minimize the out-degrees of the conventionally directed multicast tree; secondly, a set of rules about bottom-up path search is presented to recover another path in the conventionally directed multicast tree, and the conflict-backtracking principle is given to minimize the coding nodes in this process. To evaluate the algorithm, some results are given. The results indicate that the algorithm can perform the expected function. Moreover, to further test and verify the algorithm, performances of different multicast modes are also compared and analyzed. The results show that the multicast performance will be impaired if the multicast tree contains redundant coding nodes.

Key words:

network coding, multicast tree, heuristic algorithm, all-optical multicast