リンクメトリック変更によるトラフィック制御問題
に関する研究
著者
栗本 進矢
2016
年度 修士論文要旨
リンクメトリック変更による
トラフィック制御問題に関する研究
関西学院大学大学院理工学研究科
情報科学専攻 巳波研究室 栗本 進矢
インターネットにおける通信経路としては，一般的に最短経路が選ばれる．実際，イン ターネットサービスプロバイダ（ISP）が提供するネットワークで代表的なプロトコルにOpen Shortest Path First（OSPF）があり，これを用いるネットワークでは，リンクにメト リックという数値が付与されており，これを辺コストとしたときの最小コスト経路（最短 経路）がノード間のデータ転送経路に決定される．しかし，OSPFのような最短経路ルー ティングでは，小さいメトリックが割り当てられたリンクに最短経路が集中しやすくな り，輻輳が発生する危険性が高い．そのため，最短経路ルーティングを用いるネットワー クにおいては，輻輳抑制や負荷分散のために適切なメトリック設定方法が必要である． 本研究では特に，限定された数のリンクのメトリックを変更してネットワークの負荷分 散を図る，リンクメトリック制御を扱った．これは，負荷分散辺コスト決定問題として定 式化され，一般にはNP完全である．一方，メトリックが変更可能なリンク数が1の場合 は，多項式オーダの計算量で解けることがわかっていた．しかし，他の場合についてはほ とんど未解決であった．本研究では，メトリックを変更できるリンクの本数及び通信需要 のあるノード対の組数を定数に限定した場合，多項式オーダの計算量で解けることを証明 した．また，通信需要のあるノード対の組数を定数から変数に緩和してもなお，多項式 オーダの計算量で解けることを証明した．さらに，すべてのリンクのメトリックを変更で きる場合に，通信需要のあるノード対の組数が2組以下のときでは，多項式オーダの計算 量で解けることを証明した．
