(57)【要約】【課題】トラヒック需要の経路を時系列に配置する場合の経路の再配置のための計算時間を短縮すること。【解決手段】ネットワークを構成するノード間のリンクの容量を示す情報と、時系列に発生するトラヒック需要ごとに、トラヒック量、始点ノード、及び終点ノードを示す情報と、を参照して、前記各トラヒック需要を前記時系列の順番で、当該トラヒック需要のトラヒック量以上の容量を有するリンクを使用して、当該トラヒック需要の始点ノードから終点ノードまでの最短経路を配置すると共に、当該最短経路を構成する各リンクの容量を当該トラヒック量で消費する過程において、いずれかのトラヒック需要に関して最短経路を配置することができない場合には、既に最短経路が配置された一部又は全部のトラヒック需要について、前記リンクの残余容量の逆数に基づく重みの合計が最小となる経路を前記ネットワークに配置する。【選択図】図１
2017143496.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークを構成するノード間のリンクの容量を示す情報と、
時系列に発生するトラヒック需要ごとに、トラヒック量、始点ノード、及び終点ノードを示す情報と、
を参照して、
前記各トラヒック需要を前記時系列の順番で、当該トラヒック需要のトラヒック量以上の容量を有するリンクを使用して、当該トラヒック需要の始点ノードから終点ノードまでの最短経路を配置すると共に、当該最短経路を構成する各リンクの容量を当該トラヒック量で消費する過程において、いずれかのトラヒック需要に関して最短経路を配置することができない場合には、既に最短経路が配置された一部又は全部のトラヒック需要について、経路の再配置を行う配置部を有し、
前記配置部は、
再配置の対象とされた各トラヒック需要について、前記リンクの残余容量の逆数に基づく重みの合計が最小となる経路を前記ネットワークに配置する、
ことを特徴とする経路配置装置。
【請求項２】
前記重みは、前記逆数又は前記逆数のα乗（α＞１）である、
ことを特徴とする請求項１記載の経路配置装置。
【請求項３】
前記重みは、前記残余容量を前記トラヒック需要のトラヒック量で除した値、又は当該値のα乗（α＞１）である、
ことを特徴とする請求項１記載の経路配置装置。
【請求項４】
ネットワークを構成するノード間のリンクの容量を示す情報と、
時系列に発生するトラヒック需要ごとに、トラヒック量、始点ノード、及び終点ノードを示す情報と、
を参照して、
前記各トラヒック需要を前記時系列の順番で、当該トラヒック需要のトラヒック量以上の容量を有するリンクを使用して、当該トラヒック需要の始点ノードから終点ノードまでの最短経路を配置すると共に、当該最短経路を構成する各リンクの容量を当該トラヒック量で消費する過程において、いずれかのトラヒック需要に関して最短経路を配置することができない場合には、既に最短経路が配置された一部又は全部のトラヒック需要について、経路の再配置を行う配置手順をコンピュータが実行し、
前記配置手順は、
再配置の対象とされた各トラヒック需要について、前記リンクの残余容量の逆数に基づく重みの合計が最小となる経路を前記ネットワークに配置する、
ことを特徴とする経路配置方法。
【請求項５】
前記重みは、前記逆数又は前記逆数のα乗（α＞１）である、
ことを特徴とする請求項４記載の経路配置方法。
【請求項６】
前記重みは、前記残余容量を前記トラヒック需要のトラヒック量で除した値、又は当該値のα乗（α＞１）である、
ことを特徴とする請求項４記載の経路配置方法。
【請求項７】
請求項１乃至３いずれか一項記載の配置部としてコンピュータを機能させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路配置方法、経路配置装置、及びプログラムに関する。
【背景技術】
【０００２】
ネットワークを構成する各リンクとのリンク容量と、ネットワーク上の特定対地間の時系列のトラヒック需要が与えられている状態において、この時系列のトラヒック需要を疎通するためのパスを、各時点での空き帯域に最短経路で埋め込むことを考える。リンク容量は有限なため、ある時点でネットワークにパスは埋め込めなくなる。このとき、これまでに埋め込んだ全てのパスの再配置によって、新たにパスを埋め込める可能性が出てくる。新たなパスを埋め込めた場合には、そのまま次の時点のトラヒック需要を最短経路で埋め込んでいく。新たなパスを埋め込めなかった場合には、そのトラヒック需要を廃棄して、次のトラヒック需要を最短経路で埋め込んでいく。これが、パス埋め込み問題におけるパス再配置問題である。
【０００３】
このように、リンク容量制約のあるネットワークにパスを１本ずつ埋め込んでいき、埋め込めなくなったときに、これまで埋め込んだパス全体の再配置を行う技術は、０−１整数計画法として定式化でき、分枝限定法によって厳密解を求める手法又はＷＣＳＰ法によってヒューリスティックに解く手法が知られていた。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】K. Nonobe and T. Ibaraki, A tabu search approach for the constraint satisfaction problem as a general problem solver, European Journal of Operational Research 106, 599-623, 1998.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、上記の手法は、計算に非常に時間がかかるという問題があった。
【０００６】
本発明は、上記の点に鑑みてなされたものであって、トラヒック需要の経路を時系列に配置する場合の経路の再配置のための計算時間を短縮することを目的とする。
【課題を解決するための手段】
【０００７】
そこで上記課題を解決するため、経路配置装置は、ネットワークを構成するノード間のリンクの容量を示す情報と、時系列に発生するトラヒック需要ごとに、トラヒック量、始点ノード、及び終点ノードを示す情報と、を参照して、前記各トラヒック需要を前記時系列の順番で、当該トラヒック需要のトラヒック量以上の容量を有するリンクを使用して、当該トラヒック需要の始点ノードから終点ノードまでの最短経路を配置すると共に、当該最短経路を構成する各リンクの容量を当該トラヒック量で消費する過程において、いずれかのトラヒック需要に関して最短経路を配置することができない場合には、既に最短経路が配置された一部又は全部のトラヒック需要について、経路の再配置を行う配置部を有し、前記配置部は、再配置の対象とされた各トラヒック需要について、前記リンクの残余容量の逆数に基づく重みの合計が最小となる経路を前記ネットワークに配置する。
【発明の効果】
【０００８】
トラヒック需要の経路を時系列に配置する場合の経路の再配置のための計算時間を短縮することができる。
【図面の簡単な説明】
【０００９】
【図１】本発明の実施の形態におけるシステム構成例を示す図である。
【図２】本発明の実施の形態におけるパス埋め込み算出装置のハードウェア構成例を示す図である。
【図３】パス埋め込み算出装置が実行する処理手順の一例を説明するためのフローチャートである。
【図４】パスの再配置処理の処理手順の一例を説明するためのフローチャートである。
【発明を実施するための形態】
【００１０】
以下、図面に基づいて本発明の実施の形態を説明する。図１は、本発明の実施の形態におけるシステム構成例を示す図である。図１において、パス埋め込み算出装置１０は、オペレーションシステム２０及び操作端末３０等に、ＬＡＮ（Local Area Network）又はインターネット等のネットワークを介して通信可能に接続される。
【００１１】
オペレーションシステム２０は、ネットワーク４０（通信網）上のノード及びノード間のリンク等を管理する１以上のコンピュータである。図１において、オペレーションシステム２０は、ネットワーク情報収集部２１を有する。ネットワーク情報収集部２１は、オペレーションシステム２０にインストールされたプログラムが、オペレーションシステム２０のＣＰＵに実行させる処理により実現される。オペレーションシステム２０は、また、ネットワーク情報記憶部２２を利用する。ネットワーク情報記憶部２２は、オペレーションシステム２０が有する補助記憶装置等を用いて実現可能である。
【００１２】
ネットワーク情報収集部２１は、例えば、ネットワーク４０のトポロジー情報や、各リンクの容量情報、及びネットワーク４０で発生した各トラヒック需要に関する情報等をネットワーク４０から収集し、ネットワーク情報記憶部２２に記憶する。
【００１３】
パス埋め込み算出装置１０は、オペレーションシステム２０によってネットワーク４０から収集された情報に基づいて、ネットワーク４０において発生した各トラヒック需要のパスを、時系列順に、ネットワーク４０を表現する無向グラフに最短経路で埋め込む（配置する）処理を実行する。図１において、パス埋め込み算出装置１０は、情報取得部１１及びパス埋め込み算出部１２等を有する。これら各部は、パス埋め込み算出装置１０にインストールされたプログラムが、パス埋め込み算出装置１０のＣＰＵ（図２のＣＰＵ１０４）に実行させる処理により実現される。パス埋め込み算出装置１０は、また、トラヒック情報記憶部１３及びグラフ情報記憶部１４等を有する。これら各記憶部は、パス埋め込み算出装置１０の補助記憶装置（図２の補助記憶装置１０２）、又はパス埋め込み算出装置１０にネットワークを介して接続可能な記憶装置等を用いて実現可能である。
【００１４】
情報取得部１１は、オペレーションシステム２０のネットワーク情報記憶部２２に記憶されている情報を取得し、取得された情報に基づくグラフ情報及びトラヒック情報のそれぞれを、グラフ情報記憶部１４又はトラヒック情報記憶部１３に記憶する。グラフ情報は、ネットワーク４０の構成を表現する無向グラフを示す情報である。当該無向グラフを構成するノード間のリンク（枝）には、当該リンクに対応する、ネットワーク４０におけるリンクの容量が付与される。グラフ情報は、例えば、ネットワーク情報記憶部２２に記憶されているトポロジー情報や各リンクの容量情報等から導出される。トラヒック情報は、ネットワーク４０において発生したトラヒック需要が時系列に配列された情報である。トラヒック情報は、ネットワーク情報記憶部２２に記憶されている、各トラヒック需要に関する情報から導出可能である。トラヒック情報において、各トラヒック需要は、トラヒックのソースノード（始点ノード）点及びデスティネーションノード（終点ノード）を示す情報と、トラヒック量とを含む。
【００１５】
パス埋め込み算出部１２は、トラヒック情報記憶部１３及びグラフ情報記憶部１４に記憶されたトラヒック情報及びグラフ情報を用いて、各トラヒック需要を疎通させるパスの最短経路を算出する。
【００１６】
操作端末３０は、ネットワーク４０の運用者、または、設計者が直接操作する端末である。操作端末３０は、結果表示部３１を有する。結果表示部３１は、ネットワーク４０の運用者又は設計者による操作に応じ、パス埋め込み算出装置１０に対して、設計、運用、又は管理の対象であるネットワーク４０に関して埋め込まれたパスに関する情報の取得を要求し、パス埋め込み算出装置１０から返信される情報を表示する。
【００１７】
図２は、本発明の実施の形態におけるパス埋め込み算出装置のハードウェア構成例を示す図である。図２のパス埋め込み算出装置１０は、それぞれバスＢで相互に接続されているドライブ装置１００、補助記憶装置１０２、メモリ装置１０３、ＣＰＵ１０４、及びインタフェース装置１０５等を有する。
【００１８】
パス埋め込み算出装置１０での処理を実現するプログラムは、ＣＤ−ＲＯＭ等の記録媒体１０１によって提供される。プログラムを記憶した記録媒体１０１がドライブ装置１００にセットされると、プログラムが記録媒体１０１からドライブ装置１００を介して補助記憶装置１０２にインストールされる。但し、プログラムのインストールは必ずしも記録媒体１０１より行う必要はなく、ネットワークを介して他のコンピュータよりダウンロードするようにしてもよい。補助記憶装置１０２は、インストールされたプログラムを格納すると共に、必要なファイルやデータ等を格納する。
【００１９】
メモリ装置１０３は、プログラムの起動指示があった場合に、補助記憶装置１０２からプログラムを読み出して格納する。ＣＰＵ１０４は、メモリ装置１０３に格納されたプログラムに従ってパス埋め込み算出装置１０に係る機能を実行する。インタフェース装置１０５は、ネットワークに接続するためのインタフェースとして用いられる。
【００２０】
以下、パス埋め込み算出装置１０が実行する処理手順について説明する。図３は、パス埋め込み算出装置が実行する処理手順の一例を説明するためのフローチャートである。
【００２１】
ステップＳ１０１において、パス埋め込み算出部１２は、グラフ情報記憶部１４に記憶されているグラフ情報を取得して、無向グラフＧを特定する。ここで、無向グラフＧ＝｛Ｎ、Ｅ｝とする。但し、Ｎ、Ｅは、それぞれネットワーク４０に属するノード、リンクの集合とする。ノード数＃Ｎ＝ｎとする。ノードには番号が付与される。リンクｅ∈Ｅにはリンク容量ｙ（ｅ）が付与されている。
【００２２】
続いて、パス埋め込み算出部１２は、トラヒック情報記憶部１３に記憶されているトラヒック需要を、時系列順に一つ取得する（Ｓ１０２）。トラヒック情報記憶部１３には、時系列ｍの順に、各トラヒック需要ｕ（ｍ）について、ソースノードｓ（ｍ）、デスティネーションノードｔ（ｍ）、及びトラヒック量が記憶されている（但し、１≦ｓ（ｍ）、ｔ（ｍ）≦ｎ））。以下、取得されたトラヒック需要を、「対象トラヒック需要」という。
【００２３】
続いて、パス埋め込み算出部１２は、無向グラフＧに対して、対象トラヒック需要を最短経路で疎通可能なパスを埋め込む（配置する）（Ｓ１０３）。すなわち、対象トラヒック需要のトラヒック量以上の容量ｙ（ｅ）を有するリンクｅを使用して、対象トラヒック需要のソースノードｓ（ｍ）からデスティネーションノードｔ（ｍ）へ最短経路で到達可能なパスが、無向グラフＧに埋め込まれる。ここで、ｕ（ｍ）を疎通するパスｐ（ｍ）は、次の容量制約（１）を満たすものとする。
Ｓｅ＝｛ｍ｜ｐ（ｍ）はリンクｅを疎通する。｝と置く。
Σｍ∈Ｓ＿ｅｕ（ｍ）≦ｙ（ｅ），ｅ∈Ｅ        （１）
なお、（１）において、ｕ（ｍ）は、トラヒック需要ｕ（ｍ）のトラヒック量を示す。
【００２４】
各パスｐ（ｍ）は（１）を満たしつつ、経路長（経路に含まれるリンクの数）を最小化するように最短経路が選択される。
【００２５】
なお、対象トラヒック需要のパスが配置されたリンクｅの容量ｙ（ｅ）は、対象トラヒック需要のトラヒック量によって消費される。すなわち、容量ｙ（ｅ）は、ｙ（ｅ）から対象トラヒック需要を差し引いた値によって更新される。
【００２６】
対象トラヒック需要のパスを埋め込めた場合（Ｓ１０４でＹｅｓ）、パス埋め込み算出部１２は、トラヒック情報記憶部１３に未処理のトラヒック需要（時系列順において対象トラヒック需要の次のトラヒック需要）が記憶されているか否かを判定する（Ｓ１０５）。該当するトラヒック需要が記憶されている場合（Ｓ１０５でＮｏ）、対象トラヒック需要の次のトラヒック需要に関してステップＳ１０２以降が実行される。すなわち、ｍ＝１から順に、パスｐ（ｍ）が無向グラフＧに埋め込まれていく。
【００２７】
パスｐ（ｍ）が埋め込まれていく過程において、例えば、ｍ＝ｍ１において、どのように経路をとってもパスｐ（ｍ１）を、容量制約（１）を満たすように無向グラフＧに埋め込むことができなくなると（Ｓ１０４でＮｏ）、パス埋め込み算出部１２は、既にパスが埋め込まれた全てのトラヒック需要と、トラヒック需要ｕ（ｍ１）とについて、パスの再配置処理を実行する（Ｓ１０６）。パスｐ（１）、ｐ（２）、…、ｐ（ｍ１）の経路をすべて見直して経路の全体最適を行えば、容量制約（１）を満たすようにｐ（ｍ１）をネットワーク上に埋め込める可能性が有るからである。
【００２８】
続いて、ステップＳ１０６の詳細について説明する。図４は、パスの再配置処理の処理手順の一例を説明するためのフローチャートである。
【００２９】
ステップＳ２０１において、パス埋め込み算出部１２は、グラフ情報記憶部１４に記憶されているグラフ情報を取得して、無向グラフＧ'＝｛Ｎ，Ｅ｝を生成する。すなわち、無向グラフＧの初期状態と同じ無向グラフが生成される。
【００３０】
続いて、パス埋め込み算出部１２は、変数ｍに１を代入する（Ｓ２０２）。続いて、パス埋め込み算出部１２は、トラヒック需要ｕ（ｍ）が、集合Ｕ'の要素であるか否かを判定する（Ｓ２０３）。集合Ｕ'は、過去において失敗した再配置処理において、対象トラヒック需要（ｕ（ｍ１））であったトラヒック需要の集合である。
【００３１】
トラヒック需要ｕ（ｍ）が、集合Ｕ'の要素である場合（Ｓ２０３でＹｅｓ）、ステップＳ２０７に進む。トラヒック需要ｕ（ｍ）が、集合Ｕ'の要素でない場合（Ｓ２０３でＮｏ）、パス埋め込み算出部１２は、トラヒック需要ｕ（ｍ）に関して、無向グラフＧ'の各リンクの重みを計算する（Ｓ２０４）。ノード（ｉ、ｊ）ペア（ノードｉとノードｊとのペア）にリンクが存在する場合に、その残余帯域をｃ（ｉ、ｊ）とすると、トラヒック需要ｕ（ｍ）に関する当該リンクの重みｄ（ｉ、ｊ）は、以下のように計算される。
ｄ（ｉ、ｊ）＝ｕ（ｍ）／ｃ（ｉ、ｊ）
すなわち、パス要求帯域ｕ（ｍ）を、残余帯域ｃ（ｉ、ｊ）で除することで、リンクの重みが計算される。この重みは、より空いているリンクを優先して選ぶようにするために、α＞１として、
ｄ（ｉ、ｊ）＝（ｕ（ｍ）／ｃ（ｉ、ｊ））α
によって計算されてもよい。
【００３２】
又は、ｄ（ｉ、ｊ）＝１／ｃ（ｉ、ｊ）、若しくは、ｄ（ｉ、ｊ）＝（１／ｃ（ｉ、ｊ））αとして、リンクの重みが計算されてもよい。すなわち、残余帯域ｃ（ｉ、ｊ）の逆数がそのまま重みとされてもよいし、当該逆数のα乗が重みとされてもよい。
【００３３】
続いて、パス埋め込み算出部１２は、トラヒック需要ｕ（ｍ）を、この重みづけでの最短経路で、制約（１）を満たして疎通可能なパスを埋め込むことで、最短経路ｓｐ（ｍ）を求め、その長さ（重みの合計）をｄ（ｓｐ（ｍ））とする（Ｓ２０５）。なお、重みづけでの最短経路とは、重みの合計が最小となる経路をいう。また、ステップＳ２０５では、無向グラフＧ'に関して、ｕ（ｍ）のパスが配置されたリンクｅの容量ｙ（ｅ）は、トラヒック需要ｕ（ｍ）のトラヒック量によって消費される。すなわち、容量ｙ（ｅ）（残余帯域ｃ（ｉ、ｊ））は、ｙ（ｅ）からトラヒック需要ｕ（ｍ）のトラヒック量を差し引いた値によって更新される。
【００３４】
埋め込みに成功した場合（Ｓ２０６でＹｅｓ）、パス埋め込み算出部１２は、ｍ＝ｍ１であるか否かを判定する（Ｓ２０７）。ここで、ｕ（ｍ１）は、図３のステップＳ１０３において、埋め込みに失敗したトラヒック需要である。
【００３５】
ｍ＝ｍ１でない場合（Ｓ２０７でＮｏ）、パス埋め込み算出部１２は、ｍに１を加算して（Ｓ２０８）、ステップＳ２０３以降を繰り返す。
【００３６】
ｍ＝ｍ１である場合（Ｓ２０８でＹｅｓ）、すなわち、再配置処理の結果、ｕ（ｍ１）の埋め込み（パス疎通）に成功した場合、パス埋め込み算出部１２は、無向グラフＧを、無向グラフＧ'によって上書きする（Ｓ２０９）。すなわち、再配置の結果が、無向グラフＧに反映される。
【００３７】
一方、ステップＳ２０５における埋め込みが失敗した場合（Ｓ２０６でＮｏ）、パス埋め込み算出部１２は、集合Ｕ'にｕ（ｍ１）を追加して（Ｓ２１０）、再配置処理を終了する。この場合、無向グラフＧには、再配置処理は反映されない。また、トラヒック需要ｕ（ｍ１）のパスの埋め込みは断念される。
【００３８】
なお、上記では、再配置処理において、既に埋め込んだ全てのトラヒック需要ｕ（ｍ）（１≦ｍ≦ｍ１−１）のパスｐ（ｍ）について再配置が行われる例について説明したが、再配置の対象が、一部のパス（ｍ）に限定されてもよい。
【００３９】
例えば、直近に埋め込んだｋ本のパスが再配置の対象とされてもよい。また、トラヒック量の大きなパスからｋ本のパスが再配置の対象とされてもよい。また、経路長の大きなパスからｋ本のパスが再配置の対象とされてもよい。また、トラヒック量×経路長の大きなパスからｋ本のパスが再配置の対象とされてもよい。また、パス再配置によって埋め込もうとするトラヒック需要のソースノードをｓ０、デスティネーションノードをｔ０とし、それ以外のトラヒック需要のソースノードをｓ、デスティネーションノードをｔとし、ｓ０、ｓ間のリンク長をｄ（ｓ０、ｓ）、ｔ０、ｔ間のリンク長をｄ（ｔ０、ｔ）とした場合に、ｄ（ｓ０、ｓ）＋ｄ（ｔ０、ｔ）の値の小さなパスからｋ本のパスがパスの再配置の対象とされてもよい。
【００４０】
このように、一部のパスが再配置の対象とされる場合、図４において処理対象とされるトラヒック需要が一部のトラヒック需要に限定される点を除いて、他の処理手順は、上記した通りでよい。
【００４１】
上述したように、本実施の形態によれば、図４に示した手順で再配置処理が実行されることにより、トラヒック需要の経路を時系列に配置する場合の経路の再配置のための計算時間を短縮することができる。また、本実施の形態では、最短路探索によって、空いている経路を優先して疎通させていくので、パスが疎通できなく可能性を低下させることができる。
【００４２】
なお、本実施の形態において、パス埋め込み算出装置１０は、経路配置装置の一例である。パス埋め込み算出部１２は、配置部の一例である。残余帯域は、残余容量の一例である。
【００４３】
以上、本発明の実施例について詳述したが、本発明は斯かる特定の実施形態に限定されるものではなく、特許請求の範囲に記載された本発明の要旨の範囲内において、種々の変形・変更が可能である。
【符号の説明】
【００４４】
１０          パス埋め込み算出装置
１１          情報取得部
１２          パス埋め込み算出部
１３          トラヒック情報記憶部
１４          グラフ情報記憶部
２０          オペレーションシステム
２１          ネットワーク情報収集部
２２          ネットワーク情報記憶部
３０          操作端末
３１          結果表示部
４０          ネットワーク
１００        ドライブ装置
１０１        記録媒体
１０２        補助記憶装置
１０３        メモリ装置
１０４        ＣＰＵ
１０５        インタフェース装置
Ｂ            バス
【図１】
2017143496.tif 000003
【図２】
2017143496.tif 000004
【図３】
2017143496.tif 000005
【図４】
2017143496.tif 000006