| 講演名 | 2003/11/13 高速なコスト削減マルチキャスト経路計算法の検討(NW性能管理,品質とコスト,品質と感性,一般) 杉園 幸司, 志賀 靖夫, 安川 正祥, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 近年、マルチキャスト通信において、トラヒック量の削減を実現すべく、経路の始点と終点を経由するシュタイナー木に沿って転送経路を設定することが注目を集めている。このとき使用される経路計算アルゴリズムにはデータ転送の開始時間を短縮するため、高速に計算できることが要求される。ただし、シュタイナー最小木計算問題は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. |
| キーワード(和) | マルチキャスト / 経路計算 / シュタイナー最小木 |
| キーワード(英) | Multicast / Route Calculation / Steiner Tree |
| 資料番号 | NS2003-156,CQ2003-73,TM2003-34 |
| 発行日 |
| 研究会情報 | |
| 研究会 | CQ |
|---|---|
| 開催期間 | 2003/11/13(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Communication Quality (CQ) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 高速なコスト削減マルチキャスト経路計算法の検討(NW性能管理,品質とコスト,品質と感性,一般) |
| サブタイトル（和） | |
| タイトル（英） | Study on fast steiner tree calculation algorithm |
| サブタイトル（和） | |
| キーワード(1)（和/英） | マルチキャスト / Multicast |
| キーワード(2)（和/英） | 経路計算 / Route Calculation |
| キーワード(3)（和/英） | シュタイナー最小木 / Steiner Tree |
| 第 1 著者 氏名（和/英） | 杉園 幸司 / Koji SUGISONO |
| 第 1 著者 所属（和/英） | NTTネットワークサービスシステム研究所 NTT Network Service Systems Laboratories |
| 第 2 著者 氏名（和/英） | 志賀 靖夫 / Yasuo SHIGA |
| 第 2 著者 所属（和/英） | NTTネットワークサービスシステム研究所 NTT Network Service Systems Laboratories |
| 第 3 著者 氏名（和/英） | 安川 正祥 / Seisho YASUKAWA |
| 第 3 著者 所属（和/英） | NTTネットワークサービスシステム研究所 NTT Network Service Systems Laboratories |
| 発表年月日 | 2003/11/13 |
| 資料番号 | NS2003-156,CQ2003-73,TM2003-34 |
| 巻番号（vol） | vol.103 |
| 号番号（no） | 444 |
| ページ範囲 | pp.- |
| ページ数 | 4 |
| 発行日 | |