3rd International ICST Conference on Broadband Communications, Networks, and Systems

Research Article

Network-coding Based Topology Design for Multicast Networks

  • @INPROCEEDINGS{10.1109/BROADNETS.2006.4374359,
        author={Kaikai Chi and Xiaohong Jiang and Susumu Horiguchi},
        title={Network-coding Based Topology Design for Multicast Networks},
        proceedings={3rd International ICST Conference on Broadband Communications, Networks, and Systems},
  • Kaikai Chi
    Xiaohong Jiang
    Susumu Horiguchi
    Year: 2006
    Network-coding Based Topology Design for Multicast Networks
    DOI: 10.1109/BROADNETS.2006.4374359
Kaikai Chi1,*, Xiaohong Jiang1,*, Susumu Horiguchi1,*
  • 1: Graduate School of Information Sciences,Tohoku University, Sendai, Japan, 980-8579
*Contact email: kai-chi@ecei.tohoku.ac.jp, jiang@ecei.tohoku.ac.jp, susumu@ecei.tohoku.ac.jp


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.