文献

J-GLOBAL ID：201502288298839981   整理番号：15A0592608

リンクメトリック変更によるトラフィック制御に対する多項式時間アルゴリズム

Polynomial-time Algorithm for Traffic Engineering by Link Metric Update

著者 (2件)： 栗本進矢 (関西学院大 理工) ,  巳波弘佳 (関西学院大 大学院理工学研究科)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 114  号： 477(NS2014 176-279)  ページ： 53-58  発行年： 2015年02月23日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： インターネットにおける通信経路としては,一般的に最短経路が選ばれる。実際,インターネットサービスプロバイダ(ISP)が提供するネットワークで代表的なプロトコルにOpen Shortest Path First(OSPF)があり,これを用いるネットワークでは,リンクにメトリックという数値が付与されており,これを辺コストとしたときの最小コスト経路(最短経路)がノード間のデータ転送経路に決定される。しかし,OSPFのような最短経路ルーティングでは,小さいメトリックが割り当てられたリンクに最短経路が集中しやすくなり,輻輳が発生する危険性が高い。そのため,最短経路ルーティングを用いるネットワークにおいては,輻輳抑制や負荷分散のために適切なメトリック設定方法が必要である。本稿では特に,限られた本数のリンクのメトリック更新によってネットワークの負荷分散を図るリンクメトリック制御問題を扱う。まず,この問題を無向グラフにおける負荷分散辺コスト決定問題として定式化し,メトリックを変更できるリンクの本数及び通信需要のあるノード対の組数を定数に限定した場合は多項式オーダの計算量で解けることを示す。(著者抄録)

シソーラス用語： *インターネット ,  *プロトコル ,  リンク ,  数 ,  経路 ,  *最短路問題 ,  NP完全問題 ,  *負荷分散 ,  *無向グラフ ,  *アルゴリズム ,  計算量
準シソーラス用語： トラヒック制御 ,  メトリック ,  *OSPF ,  *最短経路問題 ,  *多項式時間アルゴリズム ,  通信リンク

分類 (1件)： 計算機網  (JC03000K)

引用文献 (4件)：

• B. Fortz and M. Thorup, “Internet Traffic Engineering by Optimizing OSPF Weights,“ Proc. IEEE INFOCOM, pp. 519-528, Tel Aviv, Israel, Mar., 2000.
• I. M. Kamrul and E. Oki, “PSO: Preventive Start-Time Optimization of OSPF Link Weights to Counter Network Failure,“ IEEE Communications Letters, Vol. 14, No. 6, pp. 581-583, Jun., 2010.
• 野口,藤村,巳波,“限定されたリンク集合におけるメトリック更新によるトラピック制御,“電子情報通信学会論文誌 A, Vol.J94-a, No.2, pp.112-115, Feb.,2011.
• 野口,巳波,“輻輳抑制を考慮した省電力ネットワーク制御法,“電子情報通信学会技術研究報告NS, Vol 111, No.468, pp.23-28, Mar.,2012.

タイトルに関連する用語 (4件)： リンク ,  メトリック ,  トラフィック制御 ,  多項式時間アルゴリズム