Software-Defined Networking (SDN) enables flexible network resource
allocations for traffic engineering, but at the same time the scalability
problem becomes more serious since traffic is more difficult to be aggregated.
Those crucial issues in SDN have been studied for unicast but have not been
explored for multicast traffic, and addressing those issues for multicast is
more challenging since the identities and the number of members in a multicast
group can be arbitrary. In this paper, therefore, we propose a new multicast
tree for SDN, named Branch-aware Steiner Tree (BST). The BST problem is
difficult since it needs to jointly minimize the numbers of the edges and the
branch nodes in a tree, and we prove that it is NP-Hard and inapproximable
within $k$, which denotes the number of group members. We further design an
approximation algorithm, called Branch Aware Edge Reduction Algorithm (BAERA),
to solve the problem. Simulation results demonstrate that the trees obtained by
BAERA are more bandwidth-efficient and scalable than the shortest-path trees
and traditional Steiner trees. Most importantly, BAERA is computation-efficient
to be deployed in SDN since it can generate a tree on massive networks in small
time.

本文针对 SDN 中多播流的可扩展性问题，提出一种新的多播树 ——BST，并设计了近似算法 BAERA 用于解决该不可解问题，仿真结果表明 BAERA 生成的树比最短路径树和传统的 Steiner 树更具带宽效率和可扩展性，并且可以在 SDN 中部署，适用于大规模网络。