高速なコスト削減マルチキャスト経路計算法の検討(NW性能管理,品質とコスト,品質と感性,一般)  [in Japanese] Study on fast steiner tree calculation algorithm  [in Japanese]

近年、マルチキャスト通信において、トラヒック量の削減を実現すべく、経路の始点と終点を経由するシュタイナー木に沿って転送経路を設定することが注目を集めている。このとき使用される経路計算アルゴリズムにはデータ転送の開始時間を短縮するため、高速に計算できることが要求される。ただし、シュタイナー最小木計算問題はNP完全問題であり、多項式時間で計算することは困難である。KMBアルゴリズムはシュタイナー最小木計算問題を解決するアルゴリズムのうち、計算時間が短く、高いコスト削減効果をもった経路を計算するアルゴリズムである。このアルゴリズムは終点、もしくは始点と終点の間の最短経路から計算結果は構成されるため、最短経路の選ばれ方に応じて計算された経路のコストが変化するという問題がある。本稿では既存のアルゴリズムのうち、KMBアルゴリズムの問題点である計算結果の不安定性を解決し、かつ計算時間を短縮するアルゴリズムを提案する。

Heuristic algorithm for steiner tree is promissive for reduction of traffic volume, avoidance of congestion, and so on. The calculation speed of the algorithms are required to be fast for implementation of network node, such as router. But the steiner tree problem is NP complete, so it is hard to compute the complete soultion within polynominal time. KMB algorithm is fast and calculates multicast path whose cost is reduced effectively. The calculation result is composed of shortest path between egress points or ingress and egress point of route. So cost of the calculation result depends on how long shared link of two shortest path exists. We propose fast algorithm modifying KMB algorithm to solve the dependency of shortest path selection.