| 講演名 | 2015-03-02 リンクメトリック変更によるトラフィック制御に対する多項式時間アルゴリズム 栗本 進矢, 巳波 弘佳, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | インターネットにおける通信経路としては,一般的に最短経路が選ばれる.実際,インターネットサービスプロバイダ(ISP)が提供するネットワークで代表的なプロトコルにOpen Shortest Path First(OSPF)があり,これを用いるネットワークでは,リンクにメトリックという数値が付与されており,これを辺コストとしたときの最小コスト経路(最短経路)がノード間のデータ転送経路に決定される.しかし,OSPFのような最短経路ルーティングでは,小さいメトリックが割り当てられたリンクに最短経路が集中しやすくなり,輻輳が発生する危険性が高い.そのため,最短経路ルーティングを用いるネットワークにおいては,輻輳抑制や負荷分散のために適切なメトリック設定方法が必要である.本稿では特に,限られた本数のリンクのメトリック更新によってネットワークの負荷分散を図るリンクメトリック制御問題を扱う.まず,この問題を無向グラフにおける負荷分散辺コスト決定問題として定式化し,メトリックを変更できるリンクの本数及び通信需要のあるノード対の組数を定数に限定した場合は多項式オーダの計算量で解けることを示す. |
| 抄録(英) | In general, a route determined by an internet routing protocol such as OSPF and BGP is the shortest path that the sum of the metrics of the links contained in the path is the minimum. If a link has small metrics, many routes may pass the link, and it may cause the congestion of the link. Therefore, the number of the routes in a link must be restricted to avoid a congestion. The link metric decision problem to determine the link metrics so as to limit the number of the paths in a link was denned and analyzed by an author before. It was proved that this problem is NP-hard and that the problem can be solved in polynomial time when the metric of only a link must be determined. In this paper, we present a polynomial-time algorithm to this problem when the number of links whose metrics must be determined is restricted and the number of node pairs whose routes must be determined is restricted. |
| キーワード(和) | リンクメトリック / OSPF / トラフィック制御 / 多項式時間アルゴリズム / NP完全性 / 最適化理論 |
| キーワード(英) | Link Metric / OSPF / Traffic Control / Polynomial-time Algorithm / NP-complete / Optimization problem |
| 資料番号 | NS2014-185 |
| 発行日 |
| 研究会情報 | |
| 研究会 | NS |
|---|---|
| 開催期間 | 2015/2/23(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Network Systems(NS) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | リンクメトリック変更によるトラフィック制御に対する多項式時間アルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | Polynomial-time Algorithm for Traffic Engineering by Link Metric Update |
| サブタイトル（和） | |
| キーワード(1)（和/英） | リンクメトリック / Link Metric |
| キーワード(2)（和/英） | OSPF / OSPF |
| キーワード(3)（和/英） | トラフィック制御 / Traffic Control |
| キーワード(4)（和/英） | 多項式時間アルゴリズム / Polynomial-time Algorithm |
| キーワード(5)（和/英） | NP完全性 / NP-complete |
| キーワード(6)（和/英） | 最適化理論 / Optimization problem |
| 第 1 著者 氏名（和/英） | 栗本 進矢 / Shinya KURIMOTO |
| 第 1 著者 所属（和/英） | 関西学院大学理工学部情報科学科 Kwansei Gakuin University |
| 第 2 著者 氏名（和/英） | 巳波 弘佳 / Hiroyoshi MIWA |
| 第 2 著者 所属（和/英） | 関西学院大学大学院理工学研究科情報科学専攻 Graduate School of Science and Technology, Kwansei Gakuin University |
| 発表年月日 | 2015-03-02 |
| 資料番号 | NS2014-185 |
| 巻番号（vol） | vol.114 |
| 号番号（no） | 477 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |