リンクメトリック変更によるトラフィック制御におけるメトリック変更リンクを限定した場合の多項式時間アルゴリズム

摘要

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