講演抄録/キーワード |
講演名 |
2010-03-05 10:20
リンクメトリック最適化によるネットワーク負荷分散制御 ○野口 烈・藤村武史・巳波弘佳(関西学院大) NS2009-229 |
抄録 |
(和) |
インターネットサービスプロバイダが提供するネットワークで代表的なプロトコルにOpen Shortest Path First(OSPF)がある.OSPF を用いるネットワークにおいては,小さいメトリックを割り当てられたリンクに最短経路が集中する傾向がある.この問題に対して,リンクの容量の逆数をメトリックとして割り当てる方法が広く用いられている.この方法では,容量が大きく設定されることの多いリンクに経路が集中するため,輻輳が発生した場合の影響が大きい.したがって,リンクを通過する経路数が容量以下になるように,限定されたリンクのみのメトリックを更新してネットワークの負荷分散を図る必要がある.本稿では,これを負荷分散辺長決定問題として定式化し,NP完全であることを証明した.さらに,メトリックを変更できるリンクを1つに限定した場合における多項式時間アルゴリズムを設計した.また,本アルゴリズムを現実の様々なネットワークへ適用し,アルゴリズムの有効性を評価した. |
(英) |
Open Shortest Path First (OSPF) is the most commonly used intra-domain internet routing protocol. As the routes of paths are determined by basically only the link metrics, many paths may pass a link with small metric; therefore, there is high possibility that it causes the congestion of the link. It is essential that the number of the paths with large traffic in a link is limited to avoid a congestion; therefore, it is important to determine the link metrics so as to limit the number of the paths in a link. In this paper, we define this link metric decision problem, and we prove that it is NP-complete. In addition, when we restricted this problem to determine the metric of only a link, we show that it can be solved in polynomial time. |
キーワード |
(和) |
OSPF / NP 完全性 / 多項式時間アルゴリズム / 最適化理論 / / / / |
(英) |
OSPF / NP-complete / polynomial-time algorithm / optimization problem / / / / |
文献情報 |
信学技報, vol. 109, no. 448, NS2009-229, pp. 375-380, 2010年3月. |
資料番号 |
NS2009-229 |
発行日 |
2010-02-25 (NS) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
NS2009-229 |