Improved steiner tree algorithm applied to P2MP traffic engineering
Hiroshi Matsuura, Naotaka Morita, Kazumasa Takami · 2010
Steiner tree algorithms have been investigated for multicast services. The traffic on a multicast service is streamed from a server to multiple terminals, thus a directed Steiner tree should be used. Our proposed algorithm of this type, multiplex-aware route selection (MARS), produces the same tree as minimum-cost path heuristics (MPH). However, the computational complexity of MARS is O(mnlog(m)) compared with the O(m2n) of MPH, where m indicates the number of end nodes of the tree and n indicates the number of nodes on the network. We implemented the MARS algorithm and compared it with MPH and selective closest terminal first algorithm, which is an improvement of MPH, and also demonstrated the efficiency of MARS in terms of processing time and multicast tree cost.