Proposal of New Steiner Tree Algorithm Applied to P2MP Traffic Engineering

Free registration required

Executive Summary

There are many polynomial-time heuristic Steiner tree algorithms since seeking the minimum Point To Multi Point (P2MP) tree in a network, which is known as the Steiner Problem in Networks (SPN), is nondeterministic polynomial time complete. Takahashi and Matsuyama's minimum-cost path heuristic algorithm (MPH) is widely applied to various multicast services. MPH has to run Dijkstra's algorithm m times in its algorithm process, where m is the number of end nodes of the multicast tree. By using Fibonacci heaps (F-heaps), the time complexity of MPH is O(m(l + n log n)), where l is the number of links and n is the number of nodes on the network.

  • Format: PDF
  • Size: 696.62 KB