Network-coding Based Topology Design for Multicast Networks

The future communication networks should have a good capability to support the rapidly growing multicast applications. It is notable, however, that the conventional algorithms for network design are mainly unicast-oriented, and they can not be adopted directly for the efficient topology design of multicast-capable networks by simply treating each multicast as multiple unicasts. The network coding technique proposed recently has the potential to efficiently support multicast transmissions with lower bandwidth requirement. In this paper we study the network-coding based network topology design problem with the consideration of efficiently supporting multicast traffic. Based on the characteristics of multicast and network coding, we first formulate this problem as a nonlinear integer programming problem, which is NP-hard. We then propose a heuristic algorithm for it. The efficiency of our algorithm is demonstrated by extensive simulation results under different traffic patterns. We conclude that our network-coding based topology design algorithm can be used to design multicast-capable networks with significantly lower cost than that of conventional unicast-oriented algorithms.