An Improved Topology Design Algorithm for Network Coding-Based Multicast Networks

Future communication networks should be designed with the consideration of efficiently supporting intensive multicast applications. Network coding technique proposed recently is promising for implementing multicast transmissions with low bandwidth requirement. This paper concerns the novel topology design problem of network coding-based multicast networks, and proposes an improved heuristic algorithm for it by adopting a new cost efficiency (CE) metric for link removal and introducing a local optimization in the design process. The effectiveness of the new heuristic is demonstrated through extensive simulations and comparisons with both the available heuristic and the exhaustive search method. The results in this paper also clearly indicate that applying the novel network coding technique in a multicast network can significantly reduce the overall topology cost.