(57)【要約】【課題】  通信網上の各ノードペア間の交流トラヒックを精度よく推定する。【解決手段】  本発明は、通信網の通信リンクを上を流れる発信トラヒック量及び着信トラヒック量とリンク上のトラヒック量をトラヒック情報とし、該通信網の現用パスの経路情報をパス情報として格納したデータベースからトラヒック情報とパス情報を取得して、発信ノードと着信ノードの組み合わせであるノードペア間のトラヒック量の２乗和を、発信トラヒック量及び着信トラヒック量とリンク上のトラヒック量に関する制約条件の下で最小化し、各ノードペア間の交流トラヒック量を推定する。【選択図】  図１
2016032284.tif 000002
【特許請求の範囲】
【請求項１】
オペレーションシステム、交流トラヒック推定装置、交流トラヒック表示装置を有し、通信網内の発信ノードと着信ノードの組み合わせである各ノードペア間の交流トラヒック量を推定する交流トラヒック推定システムであって、
前記オペレーションシステムは、
前記通信網のノードに接続された通信リンク上を流れるトラヒックの発信トラヒック量及び着信トラヒック量と該通信リンク上のトラヒック量を収集し、トラヒック情報としてネットワーク情報データベースに蓄積し、該通信網の現用パスの経路情報をパス情報として該ネットワーク情報データベースに蓄積するネットワークデータ収集手段を有し、
前記交流トラヒック推定装置は、
前記オペレーションシステムの前記ネットワーク情報データベースから前記トラヒック情報及び前記パス情報を取得して、該トラヒック情報をトラヒック情報データベースに蓄積し、該パス情報をパス情報データベースに蓄積するデータ取得手段と、
前記交流トラヒック表示装置からの交流トラヒック量の取得要求を取得すると、前記トラヒック情報データベースから前記トラヒック情報を取得し、前記パス情報データベースから前記パス情報を取得し、ノードペア間のトラヒック量の２乗和を、発信トラヒック量、着信トラヒック量及び前記通信リンク上のトラヒック量に関する制約条件の下で最小化し、前記各ノードペア間の交流トラヒック量を推定する交流トラヒック推定手段と、
を有し、
前記交流トラヒック表示装置は、
前記交流トラヒック推定装置に対して、前記交流トラヒック量の取得要求を送信し、該交流トラヒック推定装置から取得したノードペア間の交流トラヒック量を表示する交流トラヒック表示手段を有する
ことを特徴とする交流トラヒック推定システム。
【請求項２】
通信網内の発信ノードと着信ノードの組み合わせである各ノードペア間の交流トラヒック量を推定する交流トラヒック推定装置であって、
前記通信網の通信リンク上を流れるトラヒックの発信トラヒック量及び着信トラヒック量と該通信リンク上のトラヒック量をトラヒック情報とし、該通信網の現用パスの経路情報をパス情報として格納するデータベースと、
前記データベースから前記トラヒック情報と前記パス情報を取得して、ノードペア間のトラヒック量の２乗和を、前記発信トラヒック量及び前記着信トラヒック量と前記通信リンク上のトラヒック量に関する制約条件の下で最小化し、前記各ノードペア間の交流トラヒック量を推定する交流トラヒック推定手段と、
を有することを特徴とする交流トラヒック推定装置。
【請求項３】
前記交流トラヒック推定手段は、
自ノード内折り返しトラヒック量が0以外の値を取りうるとする制約条件を用いて、前記各ノードペア間の交流トラヒック量を推定する手段を含む
請求項２記載の交流トラヒック推定装置。
【請求項４】
前記交流トラヒック推定手段は、
自ノード内折り返しトラヒック量が0であるという制約条件を用いて、前記各ノードペア間の交流トラヒック量を推定する手段を含む
請求項２記載の交流トラヒック推定装置。
【請求項５】
オペレーションシステム、交流トラヒック推定装置、交流トラヒック表示装置を有するシステムにおいて、通信網内の発信ノードと着信ノードの組み合わせである各ノードペア間の交流トラヒック量を推定する交流トラヒック推定方法であって、
前記オペレーションシステムが、
前記通信網のノードに接続される通信リンク上を流れるトラヒックの発信トラヒック量及び着信トラヒック量と該通信リンク上のトラヒック量を収集し、トラヒック情報としてネットワーク情報データベースに蓄積し、該通信網の現用パスの経路情報をパス情報として該ネットワーク情報データベースに蓄積するネットワークデータ収集ステップと、
前記交流トラヒック推定装置が、
前記ネットワーク情報データベースから前記トラヒック情報及び前記パス情報を取得して、該トラヒック情報をトラヒック情報データベースに蓄積し、該パス情報をパス情報データベースに蓄積するデータ取得ステップと、
前記交流トラヒック表示装置が、
前記交流トラヒック推定装置に対して、交流トラヒック量の取得要求を送信するステップと、
前記交流トラヒック推定装置が、
前記トラヒック情報データベースから前記トラヒック情報を取得し、前記パス情報データベースから前記パス情報を取得し、ノードペア間のトラヒック量の２乗和を、前記発信トラヒック量、前記着信トラヒック量及び前記通信リンク上のトラヒック量に関する制約条件の下で最小化し、前記各ノードペア間の交流トラヒック量を推定する交流トラヒック推定ステップと、
前記交流トラヒック表示装置が、
前記交流トラヒック推定装置から取得したノードペア間の交流トラヒック量を表示する交流トラヒック表示ステップと、
を行うことを特徴とする交流トラヒック推定方法。
【請求項６】
通信網内の発信ノードと着信ノードの組み合わせである各ノードペア間の交流トラヒック量を推定する方法であって、
前記通信網の通信リンク上を流れるトラヒックの発信トラヒック量及び着信トラヒック量と該通信リンク上のトラヒック量をトラヒック情報とし、該通信網の現用パスの経路情報をパス情報として格納されたデータベースから該トラヒック情報と該パス情報を取得して、前記ノードペア間のトラヒック量の２乗和を、該発信トラヒック量、該着信トラヒック量及び該通信リンク上のトラヒック量に関する制約条件の下で最小化し、前記各ノードペア間の交流トラヒック量を推定する
ことを特徴とする交流トラヒック推定方法。
【請求項７】
前記各ノードペア間の交流トラヒックを推定する際に、
自ノード内折り返しトラヒック量が0以外の値を取りうるとする制約条件を用いて、前記各ノードペア間の交流トラヒック量を推定する
請求項６記載の交流トラヒック推定方法。
【請求項８】
前記各ノードペア間の交流トラヒックを推定する際に、
自ノード内折り返しトラヒック量が0であるという制約条件を用いて、前記各ノードペア間の交流トラヒック量を推定する
請求項６記載の交流トラヒック推定方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、交流トラヒック推定システム及び装置及び方法に係り、特に、通信リンクを流れるトラヒックと通信ノードの発信トラヒック量と着信トラヒック量が観測されている状況において、各ノードペア間の交流トラヒックを推定するための交流トラヒック推定システム及び装置及び方法に関する。
【背景技術】
【０００２】
まず、交流トラヒックについて説明する。
【０００３】
以下では、複数の通信ノードとそれらの通信ノード間を結ぶ通信リンクからなるネットワークを想定する。通信ノードは、トラヒックの発信、受信、または、中継を行う。発信ノードから発信されたトラヒックが着信ノードに着信するとき、発信ノードと着信ノード間を結ぶ通信リンクが存在しない場合には、１つ以上の中継ノードがトラヒックを中継する。ネットワークに障害が無いという条件の下で、発信ノードと着信ノードの組み合わせ（以下、「ノードペア」と記す）に対し、トラヒックが流れる経路（通信リンクと中継ノードの列）を「ノードペアの現用パス」と呼ぶ。ネットワークに障害が無い場合には、各通信リンクを流れるトラヒック量は、当該通信リンクを経路に含む現用パスに対応するノードペア間のトラヒック量の総和に等しく、測定可能である。同一ノードから発信するノードペア間のトラヒック量の総和は、発信トラヒック量として測定可能であり、各通信リンクを流れるトラヒック量とネットワークトポロジから計算することも可能である。また、同一ノードに着信するノードペア間のトラヒック量の総和は、着信トラヒック量として測定可能であり、各通信リンクを流れるトラヒック量とネットワークトポロジから計算することも可能である。各通信リンクを流れるトラヒック量が観測されているとき、各ノードペア間交流トラヒックを推定する手法を「交流トラヒック推定法」と呼ぶ。
【０００４】
各通信リンクを流れるトラヒック量、各ノードにおける発信トラヒック量及び着信トラヒック量が観測されているとき、各ノードペア間交流トラヒックを推定しようとすると、制約式の数が未知変数の数に対して少ないために、解となる交流トラヒックは一意に定まらず、解を決定することができない。
【０００５】
この問題を解消するために種々の手法が考案されてきた。例えば、複数の時点における複数の制約式を同時に考慮してその共分散を考慮することによって特定の時点のノードペア間交流トラヒックを推定する手法がある（例えば、非特許文献１参照）。
【０００６】
また、距離に依存しない重力モデル解を求め、一方では、ネットワーク内の一部の通信リンク上のトラヒック量の制約式のみからなる制約条件を考慮し、距離に依存しない重力モデル解がその制約式を満たさないならば、距離に依存しない重力モデル解から制約平面に垂線を下してその足を解にするという補正処理を行う手法がある（例えば、非特許文献２参照）。 
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】Cao, J., Davis, D., Wiel, S. V., and Yu, B.: 'Time-varying Network Tomography', Journal of the American Statistical Association, 2000, 95, pp. 1063-1075.
【非特許文献２】Zhang, Y., Roughan, M., Duffield, N., and Greenberg, A.: 'Fast Accurate Computation of Large-Scale IP Traffic Matrices from Link Loads', SIGMETRICS'03, 2003,pp. 206-217.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、上記の非特許文献１の手法は、計算が複雑になるという難点があった。
【０００９】
また、非特許文献２の手法においては、交流トラヒックが距離に依存しない重力モデルに従うものとして一度解を求めて、その後で通信リンク上の制約式を満たすように修正を行う必要があった。この手法は、距離に依存しない重力モデルを強制的に通信リンク上の制約式に従わせる点に無理があった。非特許文献２の手法により交流トラヒック推定は実用的になってきたが、最初に求めた距離に依存しない重力モデル解を、制約条件を満たすように強制的に修正する点については、まだ改善の余地があると考えられる。
【００１０】
非特許文献１，２の手法は、いずれも、制約式にある自由度を減らすために止むを得ず採用した技法であった。
【００１１】
本発明は、上記の点に鑑みなされたもので、通信網上の各ノードペア間の交流トラヒックを効率よく、かつ、精度よく推定することが可能な交流トラヒック推定システム及び装置及び方法を提供することを目的とする。
【課題を解決するための手段】
【００１２】
一態様によれば、通信網内の発信ノードと着信ノードの組み合わせである各ノードペア間の交流トラヒック量を推定する交流トラヒック推定装置であって、
前記通信網の通信リンク上を流れるトラヒックの発信トラヒック量及び着信トラヒック量と該通信リンク上のトラヒック量をトラヒック情報とし、該通信網の現用パスの経路情報をパス情報として格納するデータベースと、
前記データベースから前記トラヒック情報と前記パス情報を取得して、発信ノードと着信ノードの組み合わせであるノードペア間のトラヒック量の２乗和を、前記発信トラヒック量及び前記着信トラヒック量と前記通信リンク上のトラヒック量に関する制約条件の下で最小化し、各ノードペア間の交流トラヒック量を推定する交流トラヒック推定手段と、
を有する交流トラヒック推定装置が提供される。
【発明の効果】
【００１３】
一態様によれば、観測された通信網のトラヒック量及び現用パスの経路情報を取得して、ノードペア間のトラヒック量の２乗和を、発信トラヒック量及び着信トラヒック量と通信リンク上のトラヒック量に関する制約条件の下で最小化させて交流トラヒックを得ることにより、従来技術の手法より簡易な方法で高精度な交流トラヒックを推定することが可能となる。
【図面の簡単な説明】
【００１４】
【図１】本発明の一実施の形態におけるシステム構成例。
【図２】本発明の一実施の形態における装置間のシーケンス。
【図３】本発明の一実施の形態における４ノードリング網モデルを表す図。
【図４】本発明の一実施の形態における４ノードリング網の発信トラヒック量ai(1≦i≦4)を表す図。
【図５】本発明の一実施の形態における４ノードリング網の着信トラヒック量bi(1≦i≦4)を表す図。
【図６】本発明の一実施の形態における４ノードリング網の１リンクからなるパスpijを表す図。
【図７】本発明の一実施の形態における４ノードリング網の２リンクからなるパスpijを表す図。
【図８】本発明の一実施の形態における４ノードリング網の０リンクからなるパスpijを表す図。
【図９】従来技術の２０ノードラダー網での重力モデルトラヒックにおける交流トラヒック推定結果（重力モデル解の射影）。
【図１０】本発明の２０ノードラダー網での重力モデルトラヒックにおける交流トラヒック推定結果（２次計画法）。
【発明を実施するための形態】
【００１５】
以下、図面と共に本発明の実施の形態を説明する。
【００１６】
まず、本発明の概要を説明する。
【００１７】
交流トラヒックの解の自然な条件付けとして、従来はネットワーク内の一部の通信リンク上のトラヒック量の制約式のみを制約条件としてきたが、本発明では、それに加えて、発信ノードと着信ノード上のトラヒック量の制約式も制約条件として付け加えて、この制約条件の下で最も疎通量の小さい交流トラヒックを選ぶような最適化を考える。この最適化によって求められた交流トラヒックは、与えられた制約条件の下で最小限これだけのトラヒックを疎通できるというネットワークのトラヒック疎通能力を表す。疎通量の指標は交流トラヒックの２乗和で表し、この２乗和を最小化させて、各ノードペア間の交流トラヒック量を推定する。本発明では、最適化が物理的な意味を持つと共に、与えられた制約条件の下、距離に依存しない重力モデル解が存在し、発信トラヒック及び着信トラヒックの変動が一定の範囲内であれば、この重力モデル解と交流トラヒックの２乗和最適化解を一致させるようにする。インターネットの普及と共に、重力モデルの距離依存係数は距離に依存しない係数に変わってきているが、交流トラヒック量が発信トラヒック量及び着信トラヒック量に比例するという性質は残っている。本発明の最適化を用いてこのような交流トラヒック解を求めることにより解の精度を上げることができる。交流トラヒック解として、距離に依存しない重力モデル解を求めたい場合、２乗和解が存在すれば、最適化によって２乗和解に近い解を算出できるという証明がその根拠となる。証明については後述する。
【００１８】
図１は、本発明の一実施の形態におけるシステム構成例を示す。
【００１９】
同図に示すシステムは、オペレーションシステム１００、交流トラヒック推定装置２００、交流トラヒック表示装置３００、通信網４００を有する。
【００２０】
オペレーションシステム１００は、通信網４００上のノード４１０Ａ，４１０Ｂ，４１０Ｃと通信リンク４２０１〜４２０３を管理運用する。
【００２１】
本発明の要部である交流トラヒック推定装置２００は、オペレーションシステム１００に接続され、必要なデータの取得と取得したデータを用いた交流トラヒックの推定を実施する。交流トラヒック推定装置２００は、通信網４００の運用者、または、設計者が直接操作する交流トラヒック表示装置３００からの要求を受け、算出した交流トラヒックに関する情報を交流トラヒック表示装置３００に送信する。なお、通信網４００内にノード４１０Ａ，４１０Ｂ，４１０Ｃ、通信リンク４２０１〜４２０３を有する構成としているが、これは一例であり、この構成に限定されるものではない。
【００２２】
以下に、オペレーションシステム１００、交流トラヒック推定装置２００、交流トラヒック表示装置３００の機能について説明する。
【００２３】
＜オペレーションシステム１００＞
オペレーションシステム１００は、ネットワークデータ収集部１１０とネットワーク情報データベース１２０を有する。
【００２４】
ネットワークデータ収集部１１０は、オペレーションシステム１００が管理する通信網４００上のノード４１０Ａ，４１０Ｂ，４１０Ｃ間の通信リンク４２０１〜４２０３上を流れるトラヒック量を収集し、トラヒック情報としてネットワーク情報データベース１２０に蓄積する。また、通信網４００の運用者が設定するなどした現用パスに関する経路情報もパス情報としてネットワーク情報データベース１２０に蓄積する。
【００２５】
＜交流トラヒック推定装置２００＞
交流トラヒック推定装置２００は、データ取得部２１０、交流トラヒック推定部２２０、トラヒック情報データベース２３０、パス情報データベース２４０を有する。
【００２６】
データ取得部２１０は、オペレーションシステム１００がネットワーク情報データベース１２０で管理する情報のうち、交流トラヒック推定に必要な情報としてトラヒック情報とパス情報を取得し、トラヒック情報をトラヒック情報データベース２３０に、パス情報をパス情報データベース２４０に蓄積する。
【００２７】
交流トラヒック推定部２２０は、交流トラヒック表示装置３００から交流トラヒック推定値の取得要求を受信すると、トラヒック情報データベース２３０、パス情報データベース２４０に蓄積されたトラヒック情報とパス情報を用いて、通信網４００のノードペア間のトラヒック量の２乗和を、発信トラヒック量及び着信トラヒック量と通信リンク４２０１〜４２０３上のトラヒック量に関する制約式に基づいて最小化させ、交流トラヒック表示装置３００から指定された経路を疎通するパスの交流トラヒック量を推定する。交流トラヒック量の推定方法については後述する。
【００２８】
＜交流トラヒック表示装置３００＞
交流トラヒック表示装置３００は、交流トラヒック表示部３１０を有する。
【００２９】
交流トラヒック表示部３１０は、通信網４００の運用者、または、設計者による操作に基づき、交流トラヒック推定装置２００に対して、設計、運用または管理の対象である通信網４００の交流トラヒック推定値の取得要求を送信し、交流トラヒック推定装置２００から受信した値を表示する。
【００３０】
図２は、本発明の一実施の形態における装置間のシーケンスを示す。
【００３１】
オペレーションシステム１００のネットワークデータ収集部１１０は、通信網４００上の各ノード４１０Ａ，４１０Ｂ，４１０Ｃに対して、任意のタイミングでトラヒック情報とパス情報の取得要求を送信し（ステップ１）、通信リンク上を流れるトラヒック量、発信トラヒック量及び着信トラヒック量を含むトラヒック情報とパス情報を取得して（ステップ２）、ネットワーク情報データベース１２０に蓄積する（ステップ３）。
【００３２】
交流トラヒック推定装置２００のデータ取得部２１０が、オペレーションシステム１００に対して情報要求を送信すると（ステップ４）、オペレーションシステム１００のネットワークデータ収集部１１０がネットワーク情報データベース１２０からトラヒック情報とパス情報を読み出して返却する（ステップ５）。データ取得部２１０は取得したトラヒック情報とパス情報をそれぞれ、トラヒック情報データベース２３０とパス情報データベース２４０に蓄積する（ステップ６）。
【００３３】
交流トラヒック表示装置３００が、交流トラヒック推定装置２００の交流トラヒック推定部２２０に対して、通信網４００に属するノード４１０Ａ，４１０Ｂ，４１０Ｃ、通信リンク４２０１〜４２０３から任意のノードと任意の通信リンクを指定し、それぞれノード集合、通信リンク集合として、交流トラヒック推定値の取得要求を送信する（ステップ７）。交流トラヒック推定部２２０は当該取得要求をトリガとして、トラヒック情報データベース２３０とパス情報データベース２４０からトラヒック情報とパス情報を取得して交流トラヒック推定値を求める計算を行い（ステップ８）、交流トラヒック推定値を交流トラヒック表示装置３００に送信する（ステップ９）。交流トラヒック表示装置３００の交流トラヒック表示部３１０は取得した交流トラヒック推定値を表示する（ステップ１０）。
【００３４】
次に、交流トラヒック推定装置２００の交流トラヒック推定部２２０における交流トラヒック値を求める処理について説明する。
【００３５】
対象とする通信網を有向グラフG={N，E}とする。但し、N，Eは、それぞれ通信網４００に属するノード集合、通信リンク集合とする。これらのノード集合、通信リンク集合は、交流トラヒック表示装置３００の運用者、または、設計者の操作により入力されるものとする。ノード数#N = nとし、ノードには番号を付与する。ノードi (1≦i≦n)における発信トラヒック量をai、着信トラヒック量をbiとする。これらの値は予め測定され、トラヒック情報データベース２３０に格納されているものとする（あるいは、対応する通信リンク上のトラヒック量を加算して計算してもよい）。また、通信リンクe∈Eを疎通するパス全体のトラヒック量をteとする。この値も予め測定され、トラヒック情報データベース２３０に格納されているものとする。この通信リンクeを通る現用パスの集合Seを
Se = {(i,j)| 通信リンクe∈Eが現用パスpijに含まれる}            (1)
と表現する。求めたいノードi，j間の未知の交流トラヒック量をtijとする。tijは、ノードi，ノードjをつなぐ現用パスpij1本を通じて流れるものとする。ただし、pijとpjiは必ずしも一致しなくてもよいとする。このとき、未知の交流トラヒック量tijは、以下の制約式(2)式，(3)式，(4)式，(5)式からなる制約条件を満たす。
【００３６】
【数１】
2016032284.tif 000003
これらの制約式だけでは自由度が大きすぎるため、未知の交流トラヒック量tijを一意に決めることはできない。そこで、この制約条件のもとで、(6)式の目的関数の最小化によってtijを決める。
【００３７】
【数２】
2016032284.tif 000004
この最適化は与えられた制約条件のもとでネットワークを疎通するトラヒック量の下限値を算出するものである。但し、現実に疎通できるトラヒック量はこの下限値よりも大きくなる。この最適解tijは、制約式(2)式，(3)式，(4)式，(5)式を満たす距離に依存しない重力モデル解が可能解として存在し、発信トラヒックai(1≦i≦n)，着信トラヒックbj(1≦j≦n)の変動が、一定値a,bの近傍であれば、その可能解と一致することが、以下のように証明される。
【００３８】
未知の交流トラヒック量tijに関する制約式(2)式，(3)式，(4)式，(5)式は超平面Hを構成する。超平面Hはtijの制約空間であり、この上に異なる2点
【００３９】
【数３】
2016032284.tif 000005
を考える。超平面H上のベクトル(vij)は、
【００４０】
【数４】
2016032284.tif 000006
と表すことができる。(2)式より、
【００４１】
【数５】
2016032284.tif 000007
となる。したがって、
【００４２】
【数６】
2016032284.tif 000008
と表すことができる。すなわち、
【００４３】
【数７】
2016032284.tif 000009
となる。
【００４４】
また、(3)式より、
【００４５】
【数８】
2016032284.tif 000010
となる。したがって、
【００４６】
【数９】
2016032284.tif 000011
と表すことができる。すなわち、
【００４７】
【数１０】
2016032284.tif 000012
となる。
【００４８】
制約式(2)式，(3)式，(4)式，(5)式を満たす可能解(s'ij)が存在すると仮定すると、最適化（目的関数の最小化）を行うための(6)式による最適解(sij)は同じく制約式(2)式，(3)式，(4)式，(5)式を満たすので、両者は同じ超平面H上にある。そこで、超平面H上のベクトル(vij)≠0と実パラメタtを用いて、最適解(sij)は、
【００４９】
【数１１】
2016032284.tif 000013
と表すことができる。このとき、(sij)が交流トラヒック量の2乗和を最小化した解（最適解）であることから、
【００５０】
【数１２】
2016032284.tif 000014
が成立する。(15)式を展開すると、
【００５１】
【数１３】
2016032284.tif 000015
となり、(vij)≠0であるから、
【００５２】
【数１４】
2016032284.tif 000016
となる。(17)式，(18)式より、
【００５３】
【数１５】
2016032284.tif 000017
となる。
【００５４】
可能解(s'ij)が距離に依存しない重力モデルの形で表すと、
【００５５】
【数１６】
2016032284.tif 000018
とおける。但し、kは定数係数である。さらに、発信トラヒックai，着信トラヒックbjがそれぞれ、一定値a，bの近傍にあるとすると、
【００５６】
【数１７】
2016032284.tif 000019
と表すことができる。但し、ε1i，ε2j (1≦i，j≦n)は十分小さいとする（ε1i，ε2jに対して、その積ε1i・ε2jが十分小さいとする）。なお、十分小さいとは、εの積が元のεと比べて計算上無視できるくらいεが十分小さいという意味である。このとき、
【００５７】
【数１８】
2016032284.tif 000020
とする。(23)式は、(10)式、(13)式から導ける。したがって、(19)式を考慮すると、
【００５８】
【数１９】
2016032284.tif 000021
となる。これは、制約式(2)式，(3)式，(4)式，(5)式を満たす可能解(s'ij)で距離に依存しない重力モデルに従うものが存在し、発信トラヒックai、着信トラヒックbjについて(21)式，(22)式が成り立つならば、2次計画法による最適解と距離に依存しない重力モデル解が一致することを意味する。
【００５９】
次に、制約式(2)式，(3)式，(4)式，(5)式を満たす可能解(s'ij)が距離に依存しない重力モデルには従わないがそれに近い可能解が存在する場合に、2次計画法による最適解を求める方法を考察する。
【００６０】
まず、距離に依存しない重力モデル解に近い解(s'ij)を以下のように表現する。
【００６１】
【数２０】
2016032284.tif 000022
kijは重力モデル解の係数であるが、この係数を、iを添え字とする変数とjを添え字とする変数の関数として記述できるものとする。言い換えれば、(i,j)ペアを添え字とする変数を含まないものとする。例えば、距離に依存する重力モデルのように次のような場合を想定する。
ノードi，j間の距離をr、ノードiの座標を(xi,yi)、ノードjの座標を(xj,yj)とする。このとき、
【００６２】
【数２１】
2016032284.tif 000023
となる。よって、kijは、iを添え字とするxi，yiとjを添え字とするxj，yjの関数fとして表すことができる。関数fの中には、(i,j)ペアを添え字とする変数は含まれない。このとき、kの変分ε3ijは次のように表すことができる。
【００６３】
【数２２】
2016032284.tif 000024
ここで、ε3i、ε3jを
【００６４】
【数２３】
2016032284.tif 000025
とすると、kの変分ε3ijは
【００６５】
【数２４】
2016032284.tif 000026
と表すことができる。このとき、重力モデル解の係数kijは
【００６６】
【数２５】
2016032284.tif 000027
となり、ε1i，ε2j，ε3i，ε3jに対して、それらの積は十分小さいものとする。すると、
【００６７】
【数２６】
2016032284.tif 000028
となり、したがって、(19)式より、
【００６８】
【数２７】
2016032284.tif 000029
となる。よって、距離に依存しない重力モデルに近い解が可能解として存在した場合にも、発信トラヒックai，着信トラヒックbjについて(21)式，(22)式が成り立つならば、2次計画法による最適解は、この可能解と一致する。したがって、本発明の手法は、発信トラヒックai，着信トラヒックbjが一定値の近傍内にあるとき、制約式(2)式，(3)式，(4)式，(5)式を満たす距離に依存しない重力モデルに近い解を最適解とする。これは、制約式(4)式，(5)式に(2)式，(3)式を付け加えた上で、トラヒック2乗和を最小化しているためで、従来技術の、重力モデル解を陽に求めて、それを制約式(4)式，(5)式を満たすように補正する手法と比べて簡単である。実験においても推定精度の高さが認められた。実験結果については後述する。
【００６９】
制約式(2)式，(3)式，(4)式，(5)式の下での最適化のための(6)式は2次計画法であり、市販の数理計画法パッケージを用いて解を求めることができる。あるいは、非特許文献２のように疑似逆行列を用いて計算してもよい。非特許文献２の手法との違いは、発信トラヒック量及び着信トラヒック量に関する制約式を陽に追加し、距離に依存しない重力モデル解から制約平面に対して垂線の足を下す処理を省き、原点から制約平面に対して直接垂線の足を下すように変更した点である。これによって、計算が簡易化し、解の性質を理論的に導けるようになった。
【００７０】
次に、計算例を示す。図３に示すように、通信網４００として、４ノードからなるリング網を考える。発信トラヒック量ai (1≦i≦4)は、図４に示すように、
a1=3, a2=4, a3=1, a4=2            (34)
とし、着信トラヒック量bi (1≦i≦4)は、図５に示すように
b1=1, b2=2, b3=3, b4=4            (35)
とする。また、一例として、通信網４００には、図６、図７、図８のようにパスが張られているものとする。図６は1リンクからなるパスpijを示し、図７は2リンクからなるパスpijを示し、図８は0リンクからなるパスpijを示す。このようにパスを張ることによって、任意のノードi，ノードj間に1つのパスが張られることになる。この計算例では、同一ノードi間トラヒック量tiiが必ずしも0でなくてもよいものとする。すなわち、自ノード内折り返しトラヒック量を含んだモデルを考える。これは、このモデルにおいては、発信トラヒック量と着信トラヒック量を事前に矛盾なく距離に依存しない重力モデルに従うものとして定義することが容易だからである。制約式(2)式，(3)式に従う距離に依存しない重力モデルの下でノードi，j間のトラヒック量tij (1≦i，j≦4)を計算すると以下のようになる。
t11=3*1/10=3/10=0.3            (36)
t12=3*2/10=6/10=0.6            (37)
t13=3*3/10=9/10=0.9            (38)
t14=3*4/10=12/10=1.2            (39)
t21=4*1/10=4/10=0.4            (40)
t22=4*2/10=8/10=0.8            (41)
t23=4*3/10=12/10=1.2            (42)
t24=4*4/10=16/10=1.6            (43)
t31=1*1/10=1/10=0.1            (44)
t32=1*2/10=2/10=0.2            (45)
t33=1*3/10=3/10=0.3            (46)
t34=1*4/10=4/10=0.4            (47)
t41=2*1/10=2/10=0.2            (48)
t42=2*2/10=4/10=0.4            (49)
t43=2*3/10=6/10=0.6            (50)
t44=2*4/10=8/10=0.8            (51)
ノードi，j間のトラヒック量が(36)〜(51)式を満たすとき、発信トラヒック量ai (1≦i≦4)は、
a1=t11+t12+t13+t14=0.3+0.6+0.9+1.2=3        (52)
a2=t21+t22+t23+t24=0.4+0.8+1.2+1.6=4        (53)
a3=t31+t32+t33+t34=0.1+0.2+0.3+0.4=1        (54)
a4=t41+t42+t43+t44=0.2+0.4+0.6+0.8=2        (55)
となり、トラヒック量の和の整合性がとれている。同時に、着信トラヒック量bi(1≦i≦4)も、
b1=t11+t21+t31+t41=0.3+0.4+0.1+0.2=1        (56)
b2=t12+t22+t32+t42=0.6+0.8+0.2+0.4=2        (57)
b3=t13+t23+t33+t43=0.9+1.2+0.3+0.6=3        (58)
b4=t14+t24+t34+t44=1.2+1.6+0.4+0.8=4        (59)
となり、こちらもトラヒック量の和の整合性がとれている。
【００７１】
今、ノードiとノードjをつなぐ通信リンクをlijと記述する。図６、図７、図８のパス経路が示すように、トラヒックはステップ数が短い経路を優先して疎通させることとし、ステップ数が等しい場合には時計周りの経路を優先して疎通させることにする。このとき、ノードi，j間のトラヒック量が(36)〜(51)式を満たすとすると、各通信リンク上のトラヒック量は以下のようになる。
tl12=t12=0.6                    (60)
tl21=t21+t24+t31=0.4+1.6+0.1=2.1            (61)
tl23=t23=1.2                    (62)
tl32=t32+t31+t42=0.2+0.1+0.4=0.7            (63)
tl34=t34=0.4                    (64)
tl43=t43+t42+t13=0.6+0.4+0.9=1.9            (65)
tl41=t41=0.2                    (66)
tl14=t14+t13+t24=1.2+0.9+1.6=3.7            (67)
tl11=t11=0.3                    (68)
tl22=t22=0.8                    (69)
tl33=t33=0.3                    (70)
tl44=t44=0.8                    (71)
ここまでの処理で、ノードi，j間のトラヒック量が(36)〜(51)式を満たすことを前提として、発信トラヒック量ai (1≦i≦4)について(52)〜(55)式、着信トラヒック量bi (1≦i≦4)について(56)〜(59)式、各通信リンク上のトラヒック量(60)〜(71)式を計算したが、次は逆に、発信トラヒック量ai (1≦i≦4)について(52)〜(55)式、着信トラヒック量bi (1≦i≦4)について (56)〜(59)式、各通信リンク上のトラヒック量(60)〜(71)式、及びtij≧0 (1≦i, j≦4)が与えられたとき、目的関数
【００７２】
【数２８】
2016032284.tif 000030
を最小化する2次計画法を実施して、ノードi，j間のトラヒック量(31)〜(46)式をどれだけ再現できるかを確認する。この2次計画法は数理計画法パッケージツールを用いて容易に解くことができる。
【００７３】
解tij(1≦i，j≦4)は以下のような値となる。
t11=0.3                        (73)
t12=0.6                        (74)
t13=0.9                        (75)
t14=1.2                        (76)
t21=0.4                        (77)
t22=0.8                        (78)
t23=1.2                        (79)
t24=1.6                        (80)
t31=0.1                        (81)
t32=0.2                        (82)
t33=0.3                        (83)
t34=0.4                        (84)
t41=0.2                        (85)
t42=0.4                        (86)
t43=0.6                        (87)
t44=0.8                        (88)
tij (1≦i，j≦4 )の値がどれだけ再現されているかを調べると、最初のtijと再現後のtijは完全に一致し、正確に再現されていることが分かる。この計算例では、距離に依存しない重力モデル解が可能解として存在し、制約式(60)〜(71)式により、ノードi，ノードj間にただ1本のパスが張られているとしているので、証明した通り、トラヒック量の2乗和を最小化する最適化を行うことにより完全な再現性が期待できる。
【００７４】
これまでは、自ノード内折り返しトラヒック量tiiが0以外の値を取りうるとして、交流トラヒック推定を行ったが、自ノード内折り返しトラヒック量tii=0という制約条件においてもほとんど同様にこれまでの交流トラヒック推定の議論が成り立つ。(2)式、(3)式、(4)式、(5)式からなる制約条件に条件tii=0(1≦i≦n)を追加すればよい。それ以外は全く同様の議論が成り立つ。
【００７５】
非特許文献２の手法と比べて、本発明の手法の精度がどれだけ向上したかを示す計算例を示す。20ノードラダー網上で距離に依存しない重力モデルに従うトラヒックが疎通しているとする。発信トラヒック及び着信トラヒックは一様分布に従っているとする。このときの交流トラヒック推定結果を交流トラヒック真値と交流トラヒック推定値の散布図（図９，図１０）に示した。図９、図１０は、20ノードラダー網で重力モデルトラヒックにおける交流トラヒックの推定結果を示しており、縦軸は交流トラヒック推定値を示し、横軸に交流トラヒック真値を示す。散布図の性質から、点が対角線上に乗っているほど精度が高い。本発明の手法の方が、非特許文献２の手法より対角線上に真値、推定値が乗っているため、より精度が高いことがわかる。トラヒックが多い方から、全体の75%までの対地間パスについて平均２乗相対誤差をとると、非特許文献２の手法は15.5%、本発明の手法は10.6%であり、数値的にも本発明の手法の方が高精度であることが分かる。トラヒックを多い方から全体の75%に制限したのは、トラヒック量の小さなパスについて相対誤差を計算するのはあまり意味がないためである。トラヒックが多い方から、全体の75%までの相関係数を求めると、非特許文献２の手法は0.9266、本発明の手法は0.9790であり、この数値からも本発明の手法の方が高精度であることが分かる。計算時間は双方とも0.06秒(Intel Core 3.40GHz)であった。
【００７６】
本発明の最適化は、制約条件として、従来技術の通信リンク上のトラヒック量の制約式に加えて、発信ノードと着信ノードにおける制約式があるために、距離に依存しない重力モデル解が可能解として存在し、発信トラヒック量及び着信トラヒック量に大きな変動がないならば、その可能解を最適解として算出している。もし、距離に依存しない重力モデル解が可能解として存在しない場合でも、制約条件を緩和し、その制約を満たす解を最適解として算出する。例えば、距離に依存しない重力モデル解から少しずれた解などが、この緩和された制約を満たす解に相当する。本発明では、距離に依存しない重力モデル解を含み、より緩和された制約条件を満たす解を最適解として算出するので、通信リンク上の制約式と発信ノードと着信ノードにおける制約式を自然に満たすため、解の算出において計算の簡易化と推定精度の向上に寄与する。
【００７７】
交流トラヒック推定法には、様々な応用がある。例えば、仮想化ネットワークを構築した場合、パスの経路は分かっていても、そのパスの使用帯域は直接には分からない、あるいは知るためには非常にコストが掛かることが多い。それでも、通信リンク毎の使用帯域は、安価にあるいは、比較的容易に求められることが多い。そのような場合に本発明の手法を用いればパスの経路に対して、パスの使用帯域を通信リンク毎の使用帯域だけから推定することが可能になり、今後パスの経路を変更する必要があるかどうか、どの通信リンク帯域を増設すべきかなど網設計に必要な交流トラヒック情報を手に入れることができるようになる。
【００７８】
なお、本実施の形態に係る交流トラヒック推定装置２００は、例えば、１つ又は複数のコンピュータに、本実施の形態で説明する処理内容を記述したプログラムを実行させることにより実現可能である。すなわち、交流トラヒック推定装置２００が有する機能は、当該コンピュータに内蔵されるCPUやメモリ、ハードディスクなどのハードウェア資源を用いて、交流トラヒック推定装置２００で実施される処理に対応するプログラムを実行することによって実現することが可能である。また、上記プログラムは、コンピュータが読み取り可能な記録媒体（可搬メモリ等）に記録して、保存したり、配布したりすることが可能である。また、上記プログラムをインターネットや電子メールなど、ネットワークを通して提供することも可能である。
【００７９】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【符号の説明】
【００８０】
１００  オペレーションシステム
１１０  ネットワークデータ収集部
１２０  ネットワーク情報データベース
２００  交流トラヒック推定装置
２１０  データ取得部
２２０  交流トラヒック推定部
２３０  トラヒック情報データベース
２４０  パス情報データベース
３００  交流トラヒック表示装置
３１０  交流トラヒック表示部
４００  通信網
４１０Ａ，４１０Ｂ，４１０Ｃ  ノード
４２０１，４２０２，４２０３  通信リンク
【図１】
2016032284.tif 000031
【図２】
2016032284.tif 000032
【図３】
2016032284.tif 000033
【図４】
2016032284.tif 000034
【図５】
2016032284.tif 000035
【図６】
2016032284.tif 000036
【図７】
2016032284.tif 000037
【図８】
2016032284.tif 000038
【図９】
2016032284.tif 000039
【図１０】
2016032284.tif 000040