Reducing Dense Virtual Networks for Fast Embedding

（英文論文誌B　2020年4月号掲載）

　ネットワーク（NW）仮想化は共通の物理資源上に論理的に分離された複数の仮想NWを実現する技術であり，NWの柔軟性，多様性，安全性，管理性を向上させる．仮想NWの構築には仮想化されたノード，リンクを物理NW上へ割り当てることが必要である．割当コストが最小となる割当を資源制約下で発見する問題が仮想NW埋込問題である．

　仮想NW埋込問題の典型的な解法の計算量はNWサイズ，つまりノード数とリンク数の和，の3乗である．仮想NWは，物理NWとは違い，リンク設置に物理的な制約が課されないため，ノード間の通信量を表す交流トラヒック行列から直接仮想NWを設計すると全てのノード間にリンクが設置される．リンク数のオーダはノード数の2乗となる．このような密な仮想NWを埋め込む場合，計算量はノード数の3乗から6乗にまで増大してしまう．例えば，ノード数が100の場合，計算量は100万倍に増加する．

　そこで本論文は密な仮想NWをリンク数の少ない疎な仮想NWに変換し，疎なNWに対する埋込を高速に計算し，得られた疎なNWの埋込を密なNWの埋込に引き戻す手法を提案する．本論文はこの手法をNW簡約と呼ぶ．NW簡約は幾つかの仮想リンクを一つのリンクに併合して埋込を計算するため，計算時間は小さくなるが割当コストが大きくなる．本論文はこのトレードオフを解析した．具体的にはNW簡約の条件を整理，それを満たすNW簡約を提案し，解の精度，高速化の度合いなどを理論的に解析した．線形的な割当コストの増加で指数的な高速化が期待できることを示し，このトレードオフが成立することを数値実験評価にて確認した．

　NWは情報化社会を支える基盤である一方，トラヒックや接続機器は増大し続けている．これに対応するため事業者は仮想化技術の導入を開始しており，本論文は仮想NWの効率的かつ迅速な構築手法を提供する点でも有用なものである．