ネットワークトラフィック経路最適化問題への量子アニーリング適用例

ビジネス開発本部 第1応用技術部
第1チーム
知念 紀昭

連載インデックス

はじめに

前回は、次世代計算機として注目されている量子コンピュータの方式の一つである量子アニーリングと、D-Wave社で実現される量子アニーリングマシンについてご説明しました。今回は、D-Wave社の量子アニーリングマシンを用いた適用例をご紹介します。

活用され始めているD-Wave社の量子アニーリングマシン

様々な産業分野において組み合わせ最適化問題が存在していますが、総当たりで最適解を求める場合には高速なコンピュータを用いたとしても組み合わせ爆発により膨大な時間が要されます。それに対して量子アニーリングは組み合わせ最適化問題を一瞬で解くことが出来るため、今後様々な分野での活用を期待されています。D-Wave社の量子アニーリングマシンは、既にアメリカ合衆国のいくつかの連邦機関や研究機関などを始め、日本でも製造業などでの使用例が報告され始めています。

D-Wave社の量子アニーリングマシンで最適化問題を解く

D-Wave社の量子アニーリングマシンを用いて組み合わせ最適化問題を解く場合、実際問題のイジングモデルへの当てはめが肝要となります。適用手順例は以下のようになります。

(1) 解きたい問題を組み合わせ最適化問題として定義する
(2) 最適化問題をイジングモデルに当てはめる
(3) 作成したイジングモデルをD-Wave社の量子アニーリングマシンで実装される量子ビットトポロジー(現時点での量子ビットトポロジーは「キメラグラフ」と呼ばれる特殊な結合)に変換して表現する
(4) 作成した最適化問題をWeb GUIもしくはREST APIを用いてD-Wave社の量子アニーリングマシンに送信する


fig1-1

図:キメラグラフ

 

IPネットワークトラフィック経路の最適化問題

今回は組み合わせ最適化問題の一例として、IPネットワークトラフィック経路の組み合わせ問題について取り上げます。既存のIPネットワークのルーティングプロトコルはメトリック情報に基づいて経路を決定する仕組みのため、ある経路上のトラフィック集中が回避出来ないという問題を抱えています。また冗長経路を活用してトラフィックを分散させたい場合でも、経路計算の範囲や規模によっては計算量が膨大となりリアルタイム性が求められるサービスに適用するには懸念がありました。


fig1-1

図:ネットワークトラフィック集中の様子

 

量子アニーリングを用いたネットワークトラフィック経路最適化

D-Wave社の量子アニーリングマシンを用いれば、常に変化するネットワークトラフィック量に対して、一瞬で最適解を求めてダイナミックに経路を分割・平滑化する「ネットワークトラフィック経路最適化」の実現が期待できます。また帯域の狭い経路や極力使用したくない経路に対しては、ペナルティをかけて回避させることも可能です。


fig1-1

図:ネットワークトラフィック経路が最適化され分散される様子

前回の量子アニーリング記事では、イジングモデル全体のエネルギー最小状態を求められることを述べました。今回のIPネットワークトラフィック経路最適化問題においては以下のように最適化前と最適化後のエネルギー状態を算出します。


fig1-1

図:ネットワークトラフィック経路最適化問題のエネルギー算出

更に帯域の狭い経路や極力使用したくない経路に対しては、追加コストを課すことによってエネルギー算出します。


fig1-1

図:追加コストを考慮したエネルギー算出

 

ネットワークトラフィック経路最適化の自律システムの実装

実際に、D-Wave社の量子アニーリングマシンを活用して自律的にネットワークトラフィック経路最適化を行うシステムを実装しました。このシステムでは、経路を最適化したいネットワークからトラフィック情報(流量)を受け取り、その情報に基づいてD-Wave社の量子アニーリングマシンで最適化計算を行い、その結果をネットワーク経路に反映させています。各コンポーネントの動作順序は以下のようになります。

① 経路最適化したいネットワークからトラフィック情報(流量)をD-Wave操作用サーバが受け取る
② D-Wave操作用サーバ上のNode-red Dashboardで作成したGUIでトラフィック情報を画面表示し、さらに最適化開始トリガーを発信する
③ D-Wave操作用サーバのJupyter Kernel GatewayがD-Wave社の量子アニーリングマシンにQBSolvを投げ、最適化計算を実施させる
④ D-Wave社の量子アニーリングマシンが求めた最適化経路の計算結果を、D-Wave操作用サーバのJupyter Kernel Gatewayが受け取る
⑤ D-Wave操作用サーバ上のNode-red Dashboardで作成したGUIで最適化された経路を表示し、さらに経路設定をCisco DNA Centerに送る
⑥ Cisco DNA Centerは最適化された経路情報を基にネットワーク機器へConfigを設定する


fig1-1

図:ネットワークトラフィック経路の自律最適化システムの構成図

このシステムでは、Cisco DNA Centerからネットワーク機器へのConfigはSSH経由で行われ、それ以外のコンポーネント間はREST APIで連携しています。D-Wave社の量子アニーリングマシンによる最適化に要した時間は0.2秒以内でした。

システムのGUI画面では、ネットワークトラフィックのヒートマップやVLANごとのトラフィックの設定や系全体のコストならびに各種操作ボタンを配置しています。


fig1-1

図:ネットワークトラフィック経路の自律最適化システムのGUI画面

実際に刻々と変化するネットワークトラフィックを、D-Wave社の量子アニーリングマシンを用いて自律的に経路最適化する様子が確認できました。

 

おわりに

前回の量子アニーリングのご紹介に続き、今回は量子アニーリングの適用事例とシステムの実装例をご紹介致しました。実際のビジネス課題を最適化問題として定義し、最適化問題を量子ビットに当てはめることが出来れば、D-Wave社のサービスを使って量子アニーリングマシンを活用することが出来ます。今後も量子コンピュータの活用事例ができましたら、ご紹介したいと考えています。

今回ご紹介しました、「量子コンピュータを用いたネットワーク経路最適化」は、2019年に開催されました「第5回シスコテクノロジーコンテスト」において審査員特別賞を受賞致しました。内容を説明した動画資料が掲載されますので、併せてご覧ください。

https://www.cisco.com/c/m/ja_jp/partners/technology-contests/5th-technology-contest.html

関連記事

  • 次世代の計算機を考える
  • 次世代コンピュータとして注目を集める量子アニーリング
  •  

    執筆者プロフィール

    知念 紀昭
    ネットワンシステムズ株式会社 ビジネス開発本部
    第1応用技術部 第1チーム
    所属

    仮想化ハードウェア・ソフトウェアの評価・検証業務、クラウドソリューション業務などを経て、現在は機械学習ビジネスを担当している。

    イベント/レポート

    pagetop