大規模なマルチレイヤネットワーク設計問題における計算時間の高速化手法

摘要

光パスレベルのネットワークとIPトラヒックレベルのネットワークからなるマルチレイヤネットワークの最適化を，線形計画問題を解くことで行い，ネットワーク資源の有効利用を図る研究が行われている．しかし，ネットワーク規模が増大するに従い，線形計画問題の変数が膨大になり，現実的な時間で線形計画問題を解くことが不可能となる．この問題に対処するため，従来の近似解析手法では，光パスレベルの変数削減を行うとともに，線形計画問題を小さな部分問題に分割し，部分問題を繰返し解くことで，近似解を求めている．しかし，この近似解析手法では，最適解との誤差が大きくなる問題がある．本稿では，波長レイヤとIPレイヤの両レイヤで，ホップ数の大きな経路を最適化の候補から除外することで，変数を削減する手法を提案し，数値計算実験により提案方式の有効性を示す．