高速なコスト削減マルチキャスト経路計算法の検討(NW性能管理,品質とコスト,品質と感性,一般)

スポンサーリンク

概要

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

著者

関連論文

もっと見る

スポンサーリンク