| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2010-03-05 10:20 リンクメトリック最適化によるネットワーク負荷分散制御 ○野口 烈・藤村武史・巳波弘佳（関西学院大）  NS2009-229 |
|
| 抄録 | （和） | インターネットサービスプロバイダが提供するネットワークで代表的なプロトコルにOpen Shortest Path First（OSPF）がある．OSPF を用いるネットワークにおいては，小さいメトリックを割り当てられたリンクに最短経路が集中する傾向がある．この問題に対して，リンクの容量の逆数をメトリックとして割り当てる方法が広く用いられている．この方法では，容量が大きく設定されることの多いリンクに経路が集中するため，輻輳が発生した場合の影響が大きい．したがって，リンクを通過する経路数が容量以下になるように，限定されたリンクのみのメトリックを更新してネットワークの負荷分散を図る必要がある．本稿では，これを負荷分散辺長決定問題として定式化し，NP完全であることを証明した．さらに，メトリックを変更できるリンクを１つに限定した場合における多項式時間アルゴリズムを設計した．また，本アルゴリズムを現実の様々なネットワークへ適用し，アルゴリズムの有効性を評価した． |
| （英） | 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 |
|
| 研究会情報 | |
| 研究会 | NS IN |
| 開催期間 | 2010-03-04 - 2010-03-05 |
| 開催地（和） | 宮崎シーガイア |
| 開催地（英） | Miyazaki Phoenix Seagaia Resort (Miyazaki) |
| テーマ（和） | 一般 |
| テーマ（英） | General, NS+IN workshop (March 4-5) |
| 講演論文情報の詳細 | |
| 申込み研究会 | NS |
| 会議コード | 2010-03-NS-IN |
| 本文の言語 | 日本語 |
| タイトル（和） | リンクメトリック最適化によるネットワーク負荷分散制御 |
| サブタイトル（和） | |
| タイトル（英） | Traffic Engineering by Polynomially Solvable Link Metric Optimization |
| サブタイトル（英） | |
| キーワード(1)（和/英） | OSPF / OSPF |
| キーワード(2)（和/英） | NP 完全性 / NP-complete |
| キーワード(3)（和/英） | 多項式時間アルゴリズム / polynomial-time algorithm |
| キーワード(4)（和/英） | 最適化理論 / optimization problem |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 野口 烈 / Akira Noguchi / ノグチ アキラ |
| 第1著者 所属（和/英） | 関西学院大学 (略称： 関西学院大) Kwansei Gakuin University (略称： Kwansei Gakuin Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 藤村 武史 / Takeshi Fujimura / フジムラ タケシ |
| 第2著者 所属（和/英） | 関西学院大学 (略称： 関西学院大) Kwansei Gakuin University (略称： Kwansei Gakuin Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 巳波 弘佳 / Hiroyoshi Miwa / ミワ ヒロヨシ |
| 第3著者 所属（和/英） | 関西学院大学 (略称： 関西学院大) Kwansei Gakuin University (略称： Kwansei Gakuin Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2010-03-05 10:20:00 |
| 発表時間 | 20分 |
| 申込先研究会 | NS |
| 資料番号 | NS2009-229 |
| 巻番号（vol） | vol.109 |
| 号番号（no） | no.448 |
| ページ範囲 | pp.375-380 |
| ページ数 | 6 |
| 発行日 | 2010-02-25 (NS) |
[研究会発表申込システムのトップページに戻る]