Acta Metallurgica Sinica(English letters) ›› 2012, Vol. 19 ›› Issue (3): 114-121.doi: 10.1016/S1005-8885(11)60273-2

• Others • 上一篇    下一篇

Minimum Coding Nodes Multicast Tree for Two-channel All-optical Network Coding Scheme

曲志坚1,sup>1,柏琳2,ZHANG Li-kun1,   

  1. 1. Shandong University of Technology
    2. Beijing University of Posts and Telecommunications
  • 收稿日期:2011-11-11 修回日期:2012-03-20 出版日期:2012-06-30 发布日期:2012-06-08
  • 通讯作者: 曲志坚 E-mail:handuhandu@163.com
  • 基金资助:

    国家自然科学基金

Minimum Coding Nodes Multicast Tree for Two-channel All-optical Network Coding Scheme

  • Received:2011-11-11 Revised:2012-03-20 Online:2012-06-30 Published:2012-06-08
  • Contact: Zhi-Jian QU E-mail:handuhandu@163.com

摘要:

提出一种能够支持光组播网络中双路径网络编码机制的最小编码节点组播建树启发式算法。算法包含两个主要步骤,首先根据给定的有向图的最小出度和出度平衡的原则建立传统的单路径组播树;然后,在所建立的单路径组播树的基础上根据链路可用性和冲突回溯原则分别从目的节点到源节点进行启发式搜索,从而建立所需要的最少编码节点双路径组播树。最后对算法进行了测试,并且分析比较了不同组播模型的组播性能,从另一个角度对编码节点对组播性能的影响进行了分析。结果表明,网络编码能够在付出一定代价的基础上提升光组播性能,并且编码节点数量对组播性能的影响较为明显。

关键词:

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

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