情報処理装置および情報処理方法
【課題】ネットワークを構成するリンクを流れるトラフィック量の推定を行うに際して、ネットワークにかかる負荷を低減させることが可能な技術を提供する。
【解決手段】情報処理装置１００は、リンク情報と各トラフィック処理量とに基づいて、各ノードペア間を流れるパケット量に対するパケットのうちでノードを流れるパケット量の割合を各要素に有する行列を、そのノードに対応する各寄与行列として計算する寄与行列計算部１２３と、各ノードに対応する各寄与行列に基づいて、各ノードに対応する各トラフィック処理量を各ノードペアに割り振ることによってトラフィック量を推定する推定部１２４と、を備える。
【解決手段】情報処理装置１００は、リンク情報と各トラフィック処理量とに基づいて、各ノードペア間を流れるパケット量に対するパケットのうちでノードを流れるパケット量の割合を各要素に有する行列を、そのノードに対応する各寄与行列として計算する寄与行列計算部１２３と、各ノードに対応する各寄与行列に基づいて、各ノードに対応する各トラフィック処理量を各ノードペアに割り振ることによってトラフィック量を推定する推定部１２４と、を備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置および情報処理方法に関するものである。より詳細には、ネットワークのリンクを流れるトラフィック量を推定する技術に関するものである。
【背景技術】
【０００２】
ネットワークの各リンク伝送時間を推定し、任意の経路でパケットが通過するのに要する時間を推定する技術がある（例えば、特許文献１または特許文献２参照）。これらの技術によれば、ホストが探索用パケットを送出し、そのパケットがネットワーク内の複数ルータを経由してホストに戻ってくるまでの往復時間を得る処理を行う。ホストは、この処理を繰り返し実行することによってネットワークの種々の経路についての往復時間を求めることができる。また、ホストは、この往復時間から、各リンクにおける伝送時間を変数とした連立１次方程式を立て、学習されたニューラルネットによって近似解を求めることができる。近似解は、任意の経路のパケットの通過時間として算出される。これらの技術を用いれば、ネットワークの各リンクの伝送時間が求められているので、トラフィック伝送量の多いリンクを推定し、そのリンクを避けることによって伝送遅延の少ないルーティングを行うことが可能となる。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２０００−３２０３８号公報
【特許文献２】特開２０００−４９８６３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、これらの技術を用いてルーティングを行うこととした場合には、少なくとも、以下の４点が問題となる。
【０００５】
第１に、ホストがネットワーク内に複数の（あるいは多数の）探索用パケットを流すことによって、ネットワークにかかる負荷を増大させる可能性があるという問題がある。
【０００６】
第２に、ホストがリンクの伝送時間を算出するためのデータを揃えるまでに時間がかかるという問題がある。ホストが経路の往復時間を求めるために多数の探索用パケットを流し、その探索用パケットが戻ってくるまで待機する必要があるからである。この問題は、ネットワークが大きく、かつ、複雑になるほど顕著になる。
【０００７】
第３に、ネットワークが大きくなるほど、連立１次方程式によって求められる近似解の現実の値からの誤差が大きくなるという問題がある。ホストがネットワーク内に複数の探索用パケットを流すことにより、ネットワーク内の各ルータにかかる負荷が増大し、接続されているリンク数の多いルータには特に大きな負荷がかかることになる。ルータに対する負荷が増大し、ルータによるパケットに対する処理に時間がかかれば、パケットの往復時間が、厳密にはリンクの伝送時間だけからなるとは言えなくなる。これに加えて、リンクの伝送時間は時々刻々変化するものであり、例えば、ネットワークが大きく複雑であるほど、探索用パケットが多く必要になる。よって、それぞれの探索用パケットが処理される時刻は異なってくる。
【０００８】
第４に、ネットワークの構造変化に対して速やかに対応できないという問題がある。ルータ数またはリンク数の増減やリンクの付け替えなどによってネットワークの構造が変わった場合には、ホストは、連立１次方程式を立てるために必要十分な経路を改めて求めなければならない。
【０００９】
そこで、本発明は、上記問題に鑑みてなされたものであり、本発明の目的とするところは、主として、ネットワークを構成するリンクを流れるトラフィック量の推定を行うに際して、ネットワークにかかる負荷を低減させることが可能な技術を提供することにある。
【課題を解決するための手段】
【００１０】
上記問題を解決するために、本発明のある観点によれば、複数のノード間がリンクによって相互に接続されることによって構成されるネットワークに接続され、複数のノードから任意に２つのノードを選択して得られる各ノードペア間のリンクを流れるパケット量であるトラフィック量を推定する情報処理装置であって、リンクによる各ノード間の接続関係を示すリンク情報を取得するリンク情報取得部と、同一期間内に各ノードを流れたパケット量を当該ノードに対応する各トラフィック処理量として計算する処理量計算部と、リンク情報と各トラフィック処理量とに基づいて、各ノードペア間を流れるパケット量に対する当該パケットのうちでノードを流れるパケット量の割合を各要素に有する行列を、当該ノードに対応する各寄与行列として計算する寄与行列計算部と、各ノードに対応する各寄与行列に基づいて、各ノードに対応する各トラフィック処理量を各ノードペアに割り振ることによってトラフィック量を推定する推定部と、を備えることを特徴とする、情報処理装置が提供される。
【００１１】
推定部は、各ノードペアに割り振る各トラフィック処理量として寄与行列の各要素値に比例する値を使用することとしてもよい。
【００１２】
推定部は、寄与行列の要素値の総和が大きいノードから順に、当該ノードに対応するトラフィック処理量を各ノードペアに割り振ることとしてもよい。
【００１３】
推定部は、寄与行列の非零の要素数が大きいノードから順に、当該ノードに対応するトラフィック処理量を各ノードペアに割り振ることとしてもよい。
【００１４】
推定部は、推定したトラフィック量から各ノードを流れたパケット量であるトラフィック処理量を計算し、計算したトラフィック処理量と処理量計算部によって計算されたトラフィック処理量との大小関係を判断し、計算したトラフィック処理量のほうが大きいと判断した場合には、当該ノードを含むノードペアに対して割り振るトラフィック処理量を減少させ、計算したトラフィック処理量のほうが小さいと判断した場合には、当該ノードを含むノードペアに対して割り振るトラフィック処理量を増加させることによって、再度トラフィック量の割り振りを行うこととしてもよい。
【発明の効果】
【００１５】
以上説明したように本発明によれば、主として、ネットワークを構成するリンクを流れるトラフィック量の推定を行うに際して、ネットワークにかかる負荷を低減させることが可能となる。
【図面の簡単な説明】
【００１６】
【図１】ネットワークの構成を説明するための図である。
【図２】本実施形態に係る情報処理装置の機能構成を示す図である。
【図３】ネットワークと情報処理装置との構成例を示す図である。
【図４】情報処理装置が実行する経路情報の取得から寄与行列の計算までの処理の流れを示すフローチャートである。
【図５】ルータごとのトラフィック処理量のデータ例を示す図である。
【図６】ルーティングテーブルのデータ例を示す図である。
【図７】情報処理装置が実行するトラフィック量推定処理の流れを示すフローチャートである。
【発明を実施するための形態】
【００１７】
以下に添付図面を参照しながら、本発明の好適な実施の形態について詳細に説明する。なお、本明細書及び図面において、実質的に同一の機能構成を有する構成要素については、同一の符号を付することにより重複説明を省略する。
【００１８】
＜第１本実施形態＞
［概要の説明］
図１は、ネットワークの構成を説明するための図である。図１に示すように、ネットワーク２００’は、各ノード（ノードＮ１〜Ｎ５）が連携して送信元から送信先にパケットの送信を行うものである。パケットとは、送信元から送信先に送信されるデータの単位として使用する。また、ここでは、ネットワーク２００’は、５つのノードによって構成されることとしているが、ノードの数は特に限定されるものではない。また、ノードの一例としては、ルータを使用することができるが、ノードは特にルータに限定されるものではなく、ネットワーク２００’を構成する装置であってパケットの送受信を行うものを適宜使用することができる。
【００１９】
ノードペアとは、任意のノードの組を示すものであり、直接的にリンクによって接続されているノード同士のみを意味するものではない。例えば、ノードＮ１とノードＮ２との組、ノードＮ３とノードＮ４との組のみではなく、例えば、ノードＮ１とノードＮ４との組、ノードＮ３とノードＮ５との組などもノードペアと称する。ノードの一例としてルータを使用する場合には、上記したノードペアを特にルータペアと称する。本実施形態では、ノードのトラフィック処理量と寄与行列とを用いてノードペアごとのトラフィック量を推定する。ノードのトラフィック処理量とは、例えば、ノードが処理するパケットの量であり、例えば、ノードが処理する単位時間あたりのパケットの量を意味するものとする。寄与行列については後述する。ノードペアごとのトラフィック量とは、例えば、ノードペア間において送受信されるパケットの量であり、例えば、ノードペア間において送受信される単位時間あたりのパケットの量を意味するものとする。
【００２０】
ところが、このノードのトラフィック処理量と寄与行列との情報からだけでは何通りもの推定量の候補が計算される。そこで、「ノードペアごとのトラフィック量が可能な限り均等になるようにノードのトラフィック処理量を割り当てる」という条件を満たすようにトラフィック量を推定することによって推定量の候補を絞ることにする。この条件は、ネットワーク２００’が大きくなるほどノードペアごとのトラフィック量は均一になるという考え方に基づいている。
【００２１】
［寄与行列の説明］
寄与行列は、ルータごとに作成される行列であり、例えば、ノードｋの寄与行列と言った場合には、その｛ｉ，ｊ｝要素は、ノードｉから始まりノードｊで終端するトラフィック量に対するｋを通るトラフィック量の割合を示すものである。ノードｉから始まりノードｊで終端するパケットがすべてノードｋを通る場合には、｛ｉ，ｊ｝要素は、「１」となり、ノードｋが関与しない（ノードｉから始まりノードｊで終端するパケットがノードｋを通らない）場合には、「０」となる。ネットワーク２００内のルーティング方法が決まれば、ネットワーク２００内の全寄与行列も一意に定まる。例えば、図１に示したノードＮ５の寄与行列Δ５は、次のように示される。
【００２２】
【数１】
【００２３】
ここで、経路選択には、最短経路法を採用し、経路が複数存在する場合には分岐点において経路ごとに等分配することとしている。また、ノードＮ２とノードＮ４との間のトラフィック量は、経路（ノードＮ２、ノードＮ３およびノードＮ４の順に通過する経路）と経路（ノードＮ２、ノードＮ５およびノードＮ４の順に通過する経路）とに二分されるので、｛２，４｝および｛４，２｝要素は、それぞれ「０．５」となる。一方、ノードＮ１およびノードＮ４との間で送受信されるパケットは、必ずノードＮ５を通るので、｛１，４｝および｛４，１｝要素は、「１」となる。｛ｉ，ｊ｝要素は、Δ５ｉ，ｊと表すこととする。
【００２４】
また、ノードｉから始まりノードｊで終端するトラフィック量を｛ｉ，ｊ｝要素とする行列をＴｉ，ｊと表せば、ノードｋを通るトラフィック処理量ｔｋは、次のように、要素ごとの積の和という形式で示される。
【００２５】
【数２】
【００２６】
以下においては、ノードによって構成されるネットワーク２００’の一例として、ルータによって構成されるネットワーク２００（例えば、図２または図３参照）を使用する場合について説明する。
【００２７】
［構成の説明］
図２は、本実施形態に係る情報処理装置の機能構成を示す図である。図２を参照して、本実施形態に係る情報処理装置の機能構成について説明する。
【００２８】
図２に示すように、情報処理装置１００は、ネットワーク２００に接続されている。ネットワーク２００は、複数のルータ間がリンクによって相互に接続されることによって構成されている（図３参照）。情報処理装置１００は、複数のルータから任意に２つのルータを選択して得られる各ルータペア間のリンクを流れるパケット量であるトラフィック量を推定する。情報処理装置１００は、記憶部１１０と制御部１２０と通信部１３０とを備えるものである。パケット量としては、パケットの数を使用することとしてもよいし、パケットのデータ量を使用することとしてもよい。
【００２９】
記憶部１１０は、例えば、ＨＤＤ（Ｈａｒｄ Ｄｉｓｋ Ｄｒｉｖｅ）等の記憶装置などによって構成される。記憶部１１０は、制御部１２０によって実行されるプログラムを記憶する機能や、プログラムが使用するデータを記憶する機能を有するものである。
【００３０】
制御部１２０は、例えば、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）などによって構成され、ＣＰＵによって、記憶部１１０が記憶するプログラムがＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）などに展開され、展開されたプログラムが実行されることによってその機能が実現される。制御部１２０は、経路情報取得制御部１２１、リンク情報取得部１２２、寄与行列計算部１２３、推定部１２４、処理量計算部１２５などを備える。
【００３１】
通信部１３０は、例えば、通信装置等によって構成され、ネットワーク２００内のルータと通信を行うことが可能である。通信部１３０は、経路情報送信要求送信部１３１、経路情報受信部１３２、トラフィックデータ送信要求送信部１３３、トラフィックデータ受信部１３４などを備えるものである。
【００３２】
トラフィックデータ受信部１３４は、ＳＮＭＰ（Ｓｉｍｐｌｅ Ｎｅｔｗｏｒｋ Ｍａｎａｇｅｍｅｎｔ Ｐｒｏｔｏｃｏｌ）のＭＩＢ（Ｍａｎａｇｅｍｅｎｔ Ｉｎｆｏｒｍａｔｉｏｎ Ｂａｓｅ）情報のうちトラフィック処理量をネットワーク２００内のすべてのルータから定期的に受信する。トラフィックデータ受信部１３４は、受信したトラフィック処理量を処理量計算部１２５に出力する。
【００３３】
処理量計算部１２５は、トラフィックデータ受信部１３４から出力されたトラフィック処理量から同一期間内に各ルータを流れたパケット量をそのルータに対応する各トラフィック処理量として計算する。同一期間は、その開始時刻も同一であることが好ましいが、期間の長さは、例えば、１０秒間、５分間、１時間など、どのような長さであってもよい。処理量計算部１２５は、計算したトラフィック処理量を推定部１２４に出力する。
【００３４】
経路情報受信部１３２は、ネットワーク２００内のすべてのルータからルーティングテーブル（経路情報）を受信し、受信したルーティングテーブルをリンク情報取得部１２２に出力する。
【００３５】
リンク情報取得部１２２は、経路情報受信部１３２から出力されたルーティングテーブルに基づいて、ネットワーク２００内の各ルータ間のリンクによる接続関係を示すリンク情報を取得して、取得したリンク情報を寄与行列計算部１２３に出力する。リンク情報取得部１２２は、必要となるリンク情報が取得できない場合には、経路情報取得制御部１２１に対してルーティングテーブルの送信を求めるルータを識別するための識別情報を出力する。
【００３６】
経路情報取得制御部１２１は、ネットワーク２００内のルータからルーティングテーブルを取得するための制御を行うものである。経路情報取得制御部１２１は、例えば、リンク情報取得部１２２から出力された識別情報によって識別されるルータに対して経路情報送信要求を送信するように経路情報送信要求送信部１３１を指示する。
【００３７】
経路情報送信要求送信部１３１は、経路情報取得制御部１２１からの指示に従って、経路情報送信要求を送信する。経路情報送信要求を受信したルータは、ルーティングテーブルを送信し、送信されたルーティングテーブルが、経路情報受信部１３２によって受信される。
【００３８】
寄与行列計算部１２３は、リンク情報と各トラフィック処理量とに基づいて、各ルータペア間を流れるパケット量に対するそのパケットのうちでルータを流れるパケット量の割合を各要素に有する行列を、そのルータに対応する各寄与行列として計算する。寄与行列計算部１２３は、計算した寄与行列を推定部１２４に出力する。
【００３９】
推定部１２４は、各ルータに対応する各寄与行列に基づいて、各ルータに対応する各トラフィック処理量を各ルータペアに割り振ることによってトラフィック量を推定する。推定部１２４は、推定するルータペアのトラフィック量を、ルータペアごとのトラフィック量が可能な限り均等になるように割り振る（※１）ことが好ましい。これは、ネットワーク２００の規模が大きくなればなるほどルータペアごとのトラフィック量は均一になるという考えに基づくものである。また、これを実現するために、例えば、推定部１２４は、各ルータペアに割り振る各トラフィック処理量として寄与行列の各要素値に比例する値を使用することができる。
【００４０】
これは、条件（※１）に反するようにも受け取れる。しかし、ルータペア間｛ｉ，ｊ｝のトラフィック（ルータペア間｛ｉ，ｊ｝を流れるパケット）が複数の経路を通ってルーティングされる場合、分岐した経路上にあるルータｋについての寄与行列Δｋｉ，ｊは、１より小さい。したがって、ルータｋについてのトラフィック処理量の割り振りは、ルータペア間｛ｉ，ｊ｝のトラフィックに対するルータｋによる関与が、他の成分「１」に相当するルータペア間のトラフィックに対するルータｋによる関与よりも小さい分少なくなる。これは、トラフィック処理量を可能な限り均等に割り振った結果であり、別経路のルータについてのトラフィック処理量がルータペア｛ｉ，ｊ｝に割り振られるので、ルータペア｛ｉ，ｊ｝に対して割り振られるトラフィック処理量が少ないということにはならない。
【００４１】
また、推定部１２４は、寄与行列の要素値の総和が大きいルータから順に、そのルータに対応するトラフィック処理量を各ルータペアに割り振ることとしてもよい。あるいは、推定部１２４は、寄与行列の非零の要素数（S）が大きいルータから順に、そのルータに対応するトラフィック処理量を各ルータペアに割り振ることとしてもよい。これは、ネットワーク２００の規模が大きくなるほどルータペアごとのトラフィック量は均一になると一応は考えられるものの、ネットワーク２００全体に流れるトラフィック量のうちＳの小さいルータ同士をルータペアとするトラフィック量は相対的に小さいという仮定（※２）に基づくものである。Ｓの小さいルータに対する割り振りを劣位に置くことで、Ｓの小さいルータ同士をルータペアとするトラフィック量が小さくなるという効果が得られる。
【００４２】
推定部１２４は、推定したトラフィック量から各ルータを流れたパケット量であるトラフィック処理量を計算し、計算したトラフィック処理量と処理量計算部１２５によって計算されたトラフィック処理量との大小関係を判断してもよい。推定部１２４は、計算したトラフィック処理量のほうが大きいと判断した場合には、そのルータを含むルータペアに対して割り振るトラフィック処理量を減少させ、計算したトラフィック処理量のほうが小さいと判断した場合には、そのルータを含むルータペアに対して割り振るトラフィック処理量を増加させることとしてもよい。このようにして、再度トラフィック量の割り振りを行うこととしてもよい。そうすれば、計算したトラフィック処理量と処理量計算部１２５によって計算されたトラフィック処理量との差が小さくすることができ、再度のトラフィック量の割り振りを繰り返せば、さらにその差を小さくしていくことができる。
【００４３】
推定部１２４は、推定したトラフィック量を推定データとして出力する。推定部１２４は、処理量計算部１２５から出力されていないトラフィック処理量があれば、そのトラフィック処理量に対応するルータにトラフィックデータ送信要求を送信するための指示をトラフィックデータ送信要求送信部１３３に出力することができる。
【００４４】
トラフィックデータ送信要求送信部１３３は、推定部１２４から出力された指示に従って、トラフィックデータ送信要求をルータに送信する。トラフィックデータ送信要求を受信したルータは、トラフィック処理量を送信し、送信されたトラフィック処理量はトラフィックデータ受信部１３４によって受信される。
【００４５】
図３は、ネットワークと情報処理装置との構成例を示す図である。図４は、情報処理装置が実行する経路情報の取得から寄与行列の計算までの処理の流れを示すフローチャートである。図５は、ルータごとのトラフィック処理量のデータ例を示す図である。図６は、ルーティングテーブルのデータ例を示す図である。
【００４６】
［動作の説明］
図２〜図７を参照して、情報処理装置１００が実行するトラフィック量推定処理の動作例について説明する。説明の都合上、ネットワーク２００内のルータ数をＮとする。また、経路情報の一例として、ルータが持つルーティングテーブルを使用することとする。図４は、経路情報の取得から寄与行列の計算までの処理の流れを示すフローチャートである。まず、図４を参照して、情報処理装置１００による経路情報の取得から寄与行列の計算までの処理について説明する。
【００４７】
以下のステップＳ１０１〜ステップＳ１０４は、ネットワーク２００内の各ルータの寄与行列Δの計算に関連するものである。まず、経路情報受信部１３２は、各ルータの持つルーティングテーブルを取得する（ステップＳ１０１）。リンク情報取得部１２２は、経路情報受信部１３２によって受信されたルーティングテーブルに基づいて、各ルータのリンク情報を取得する（ステップＳ１０２）。このリンク情報とは、各ルータがどのルータに対してリンクを持っているか、すなわち、各ルータがどのルータに対してパケットを送信できるかを示すものである。
【００４８】
経路情報取得制御部１２１は、データが揃っているか否か、すなわち、各ルータのリンク情報が取得されているか否かを判断する（ステップＳ１０３）。経路情報取得制御部１２１は、データが揃っていないと判断した場合には（ステップＳ１０３で「Ｎｏ」）、ステップＳ１０１に戻る。ステップＳ１０１に戻った場合には、経路情報送信要求送信部１３１は、リンク情報取得部１２２で必要となるルーティングテーブルを持つルータに対して経路情報送信要求パケットを送信し、経路情報受信部１３２は、経路情報送信要求パケットに対する応答として、そのルータから経路情報を受信する。
【００４９】
経路情報取得制御部１２１は、データが揃っていると判断した場合には（ステップＳ１０３で「Ｙｅｓ」）、寄与行列計算部１２３は、各ルータの寄与行列｛Δα：α∈１，・・・，Ｎ｝を計算する。ステップＳ１０１〜ステップＳ１０３は、例えば、ルーティングテーブルに変化がある度に実行されるものである。
【００５０】
図７は、トラフィックデータと寄与行列との取得からトラフィック量の推定までの処理の流れを示すフローチャートである。まず、図７を参照して、情報処理装置１００によるトラフィックデータと寄与行列との取得からトラフィック量の推定までの処理について説明する。
【００５１】
推定部１２４は、処理量計算部１２５が計算したトラフィック処理量を取得する（ステップＳ２０１）。ここでいうトラフィック処理量は、各ルータが同一期間に処理したパケットの量、すなわち、各ルータの同一期間におけるトラフィック処理量｛ｔα：α∈１，・・・，Ｎ｝を意味するものである。各ルータの同一期間におけるトラフィック処理量をトラフィック処理量として使用することとするが、上記の同一期間とは、厳密に同一の期間である必要はなく、略同一の期間であればよい。続いて、推定部１２４は、寄与行列計算部１２３が計算した寄与行列Δを取得する（ステップＳ２０２）。
【００５２】
推定部１２４は、ステップＳ２０１およびステップＳ２０２において取得されるデータが揃っているか否かを判断する（ステップＳ２０３）。推定部１２４は、データが揃っていないと判断した場合には（ステップＳ２０３で「Ｎｏ」）、ステップＳ２０１に戻る。推定部１２４が、トラフィック処理量が揃っていないと判断した場合には、トラフィックデータ送信要求送信部１３３は、揃っていないトラフィック処理量のもとになるトラフィックデータを持つルータに対してトラフィックデータ送信要求を送信する。トラフィックデータ受信部１３４は、そのトラフィックデータ送信要求に対する応答として、トラフィックデータを受信して処理量計算部１２５に出力する。処理量計算部１２５は、トラフィックデータからトラフィック処理量を計算して推定部１２４に出力する。
【００５３】
推定部１２４は、寄与行列が揃っていないと判断した場合には、寄与行列計算部１２３から寄与行列が出力されるのを待つ。
【００５４】
推定部１２４は、データが揃っていると判断した場合には（ステップＳ２０３で「Ｙｅｓ」）、ステップＳ２０４以降においてルータペアのトラフィック量の推定を行う。推定部１２４は、各ルータのトラフィック処理量を割り振るために用いる、Δαのコピー｛Δｆα：１≦α≦Ｎ｝をルータごとに用意する。Δｆαの要素値が、ルータαのトラフィック処理量をルータペアのトラフィック量に割り振る際に使用される係数となる。この要素値は、ステップＳ２１０において適宜修正される。
【００５５】
推定部１２４は、各ルータの寄与行列Δについての非零の要素数Ｓを計算し、計算したＳに基づいてルータの順番ａ［１］＝ｋ１、ａ［２］＝ｋ２、・・・、ａ［Ｎ］＝ｋＮを決める。ここで、ａ［１］〜ａ［Ｎ］は、例えば、値を設定できる配列であり、ｋ１〜ｋＮは、ルータを識別するための値である。推定部１２４は、例えば、Ｓの大きいルータから順にｋ１、ｋ２、・・・、ｋＮとし、そのＳをそれぞれＳｋ１、Ｓｋ２、・・・、ＳｋＮと表現する。推定部１２４は、このｋ１、ｋ２、・・・、ｋＮの順にトラフィック処理量を割り振る。
【００５６】
推定部１２４は、ルータｋ１のトラフィック処理量ｔｋ１をΔｆｋ１の分布に従って割り振る（ステップＳ２０５）。推定部１２４は、例えば、ルータｋ１のトラフィック処理量ｔｋ１をΔｆｋ１の分布に従ってΔｆｋ１ｉ，ｊに比例した割合で割り振る。トラフィック処理量が割り振られることによって得られるトラフィック量は、式（１）のＴのように行列で表される。ここでは、トラフィック処理量ｔｋ１を割り振ることによって得られるトラフィック量は、Ｎ×Ｎの行列Ｔｋ１と表現することとする。
【００５７】
ステップＳ２０６の繰り返し処理では、推定部１２４は、残りのルータｋ２、ｋ３、・・・、ｋＮのトラフィック処理量を割り振ることとなる。ここで、ａ［２］＝ｋ２、ａ［３］＝ｋ３、・・・、ａ［Ｎ］＝ｋＮとし、ステップＳ２０６が開始される際に実行される初期処理はｎ＝２（ｎに２を代入）、ステップＳ２０６を継続するための継続条件はｎ≦Ｎ、ステップＳ２０６が繰り返されるたびに実行される終端処理はｎ＝ｎ＋１（ｎを１増加）とする。
【００５８】
推定部１２４は、ステップＳ２０６の繰り返し処理の中で、ａ［ｎ］で指定されるルータについて割り振るトラフィック処理量ｔａ［ｎ］’を計算する（ステップＳ２０７）。計算式は、例えば、次に示すようになる。
【００５９】
【数３】
【００６０】
式（２）の右辺第２項は、ルータａ［ｎ−１］についてまで割り振ったトラフィック量Ｔｎ−１のうちルータａ［ｎ］において処理する量を示し、これをｔｎから差し引いた量がルータａ［ｎ］について割り振れるトラフィック処理量ｔａ［ｎ］’となる。
【００６１】
推定部１２４は、ステップＳ２０５における割り振り処理と同様の手法によって、トラフィック処理量ｔａ［ｎ］’をΔｆａ［ｎ］の分布に従って割り振る（ステップＳ２０８）。推定部１２４は、例えば、トラフィック処理量ｔａ［ｎ］’をΔｆａ［ｎ］の分布に従ってΔｆａ［ｎ］ｉ，ｊに比例した割合で割り振る。推定部１２４は、トラフィック処理量ｔａ［ｎ］’が割り振られることによって得られた各値をＴｎ−１の各要素に追加する。このようにして更新した後のトラフィック量はＴｎとなる。
【００６２】
推定部１２４は、ステップＳ２０６の繰り返し処理によって得られたＴＮから計算される各ルータのトラフィック処理量とｔαとの差が所定の範囲に収まっているか否かを判断する（ステップＳ２０９）。そのために、まず、推定部１２４は、例えば、ＴＮから各ルータのトラフィック量｛ｕα：１≦α≦Ｎ｝を次のように計算する。
【００６３】
【数４】
【００６４】
推定部１２４は、例えば、計算したｕαとトラフィック処理量ｔαとの差（あるいは差の２乗によって得られるｄ）が所定の範囲内に収まっているか否かを判断する。推定部１２４は、例えば、計算したｕαとトラフィック処理量ｔαとの差の２乗によって得られるｄとして次の式を使用することができる。
【００６５】
【数５】
【００６６】
推定部１２４は、ＴＮから計算される各ルータのトラフィック処理量とｔαとの差が所定の範囲に収まっていると判断した場合には、このＴＮを推定量（推定データ）として出力する。推定部１２４は、ＴＮから計算される各ルータのトラフィック処理量とｔαとの差が所定の範囲に収まっていないと判断した場合には、ステップＳ２１０に進む。推定部１２４は、各ノードペアへのトラフィック処理量の割り振り量を修正するために、Δｆを更新すると（ステップＳ２１０）、ステップＳ２０５に戻って処理を継続する。
【００６７】
［動作の具体例の説明］
図４〜図７を参照して、情報処理装置１００が実行するトラフィック量推定処理の動作の具体例について説明する。ネットワーク２００は、図３に示したように、ルータＲ１〜ルータＲ６によって構成されるものとして説明するが、ネットワーク２００の構成はこれに限定されるものではない。図３に示した情報処理装置１００は、図２に示した情報処理装置１００に相当するものである。パケットは、ルータＲ１〜ルータＲ６の外側には送出されない状況を想定し、ルータＲ１〜ルータＲ６のそれぞれに接続しているリンクを通じてパケットの送受信を行うものとする。また、以下の推定で用いるルータペア間のトラフィック量の候補を６×６行列Ｔと表現する。
【００６８】
情報処理装置１００において、ルータＲ１〜ルータＲ６が処理したトラフィック処理量からルータペア間のトラフィック量を推定する。情報処理装置１００は、トラフィックデータ受信部１３４においてＳＮＭＰのＭＩＢ情報のうちトラフィック処理量をルータＲ１〜ルータＲ６から定期的に受信している。トラフィックデータ受信部１３４によって受信された処理量計算部１２５に出力され、処理量計算部１２５によって同一期間内におけるトラフィック処理量が取得される。
【００６９】
いま、例えば、処理量計算部１２５によって、ある時刻に観測された各ルータのトラフィック処理量｛ｔα：１≦α≦６｝が図５に示すような情報として取得されたとする。ただし、ルータαから始まりルータαで終端するパケットによるトラフィック処理量は含まれないこととする。したがって、Ｔの対角成分は「０」となり、すなわち、｛Ｔｉ，ｉ＝０：１≦i≦６｝となる。処理量計算部１２５によって取得されたトラフィック処理量は、推定部１２４に出力される。
【００７０】
次に、寄与行列計算部１２３が寄与行列を計算する過程について説明する。ステップＳ１０１において、経路情報受信部１３２が、ルータＲ１〜ルータＲ６からそれぞれのルーティングテーブルを受信し、リンク情報取得部１２２は、経路情報受信部１３２によって受信されたルーティングテーブルに基づいて、リンク情報を取得する。ここでは、リンク情報取得部１２２は、最短経路法に基づいて経路選択を行うこととし、最短経路が複数存在する場合には、ノードペアごとに１つの経路を選択することとする。一例として、リンク情報取得部１２２がルータＲ５のリンク情報を取得する場合について説明する。ルータＲ５が持つルーティングテーブルが、図６に示すようなものであった場合、リンク情報取得部１２２は、Ｎｅｘｔ Ｈｏｐ Ｎｏｄｅに基づいて、ルータＲ５がルータＲ４およびルータＲ６の２つのルータに対してリンクを張っていると判断することができる。つまり、リンク情報取得部１２２は、ルータＲ５のリンク情報として、ルータＲ４およびルータＲ６を識別するための情報をルーティングテーブルから取得することができる。
【００７１】
リンク情報取得部１２２が各ルータについて同様にしてリンク情報を取得することができると、ステップＳ１０３の条件が満たされ、寄与行列計算部１２３は、ステップＳ１０４においてΔαを計算する。経路選択方法が最短経路法によるものであれば、ルータＲ１〜ルータＲ６の寄与行列｛Δα：１≦α≦６｝としては、次に示すような行列を挙げることができる。
【００７２】
【数６】
【００７３】
以下の説明においても、Δ１〜Δ６をそれぞれルータＲ１〜ルータＲ６の寄与行列とする。そして、寄与行列計算部１２３によって計算された寄与行列Δ１〜Δ６が推定部１２４に出力される。
【００７４】
続いて、推定部１２４の動作の具体例について図７を参照して（適宜他の図参照）、説明する。上記したように、ステップＳ２０１において処理量計算部１２５によってルータＲ１〜ルータＲ６のトラフィック処理量ｔ１〜ｔ６が取得され、ステップＳ２０２において寄与行列計算部１２３によって寄与行列Δ１〜Δ６が取得されたとすると、ステップＳ２０３の条件を満たす。
【００７５】
ここで、どの寄与行列Δαも対称行列、すなわち、｛Δαｉ，ｊ＝Δαｊ，ｉ：１≦i≦６, 1≦j≦6｝であるから、簡単のために、以下で推定するルータペアのトラフィック量は、ルータペアの方向を区別しないこととする。よって、推定すべきＴは、次のように示すことができる。
【００７６】
【数７】
【００７７】
推定すべきＴが（５）式のように示される場合、推定部１２４は、Ｔ１，２，・・・Ｔ５，６の計１５成分を推定することになる。
【００７８】
ステップＳ２０４において、推定部１２４は、各ルータについてＳを求める。例えば、ルータＲ１についてのΔ１の非零（例えば、「１」）の要素数は「１０」であるから、推定部１２４は、ルータＲ１についての各ＳであるＳ１の値を「１０」と求める。同様にして、推定部１２４は、ルータＲ２〜ルータＲ６についての各ＳであるＳ２〜Ｓ６の値を「１０」「１２」「１２」「１４」「２２」と求める。したがって、推定部１２４は、トラフィック処理量を割り振る順番として、ルータＲ６、ルータＲ５、ルータＲ３、ルータＲ４、ルータＲ１、ルータＲ２と決定する。ここで、Ｓ１＝Ｓ２であり、Ｓ３＝Ｓ４であるので、ルータＲ１とルータＲ２とのうち、または、ルータＲ３とルータＲ４とのうち、どちらの順番を早めるかを決定する必要があるが、決定の仕方は特に限定されるものではない。
【００７９】
推定部１２４は、ステップＳ２０５において、トラフィック処理量ｔ６＝６１を割り振る（図５参照）。推定部１２４は、Δαのコピー｛Δｆα：１≦α≦Ｎ｝をルータごとに用意すると、Δｆ６は、次に示す通りとなる。
【００８０】
【数８】
【００８１】
式（６）に示すように、Δｆ６の要素値はすべて「１」となっている。また、いまは、Ｔ１，２〜Ｔ５，６の１５成分についてのみ考えているので、推定部１２４は、その成分に相当する非零の要素数、すなわち、割り振るべき要素値を「１１」と決定する。したがって、推定部１２４は、ｔ６／（割り振るべき要素値）＝６１／１１＝５．５５を割り振ると、次に示すＴ６のようになる。
【００８２】
【数９】
【００８３】
次に、推定部１２４は、ステップＳ２０６において、トラフィック処理量ｔ５，ｔ３，ｔ４，ｔ１，ｔ２を順次に割り振る。
【００８４】
推定部１２４は、ステップＳ２０７において、ルータＲ５について割り振るトラフィック処理量ｔ５’を計算する。式（２）により、推定部１２４は、ｔ５’＝ｔ５−Σ６ｉ＝１Σ６ｊ＝１（Δｆ５ｉ，ｊＴ６ｉ，ｊ）＝３４−２７．７３＝６．２７と計算する。
【００８５】
推定部１２４は、ステップＳ２０８において、ステップＳ２０７で算出したｔ５’＝６．２７をルータＲ６についてのトラフィック処理量ｔ６’と同様に割り振る。Δｆ５ｉ，ｊの各要素の非零の値はすべて「１」であり、割り振るべき要素数は、Δｆ５１，５，Δｆ５２，４，Δｆ５２，５，Δｆ５３，５，Δｆ５４，５，Δｆ５４，６，Δｆ５４，７の７つであるから、推定部１２４は、ｔ５’／（割り振るべき要素値）＝６．２７／７＝０．９０をＴ６１，５，Ｔ６２，４，Ｔ６２，５，Ｔ６３，５，Ｔ６４，５，Ｔ６４，６，Ｔ６４，７に追加する。その結果は、Ｔ５は、次に示すようになる。
【００８６】
【数１０】
【００８７】
同様にして、推定部１２４は、ルータＲ３、ルータＲ４、ルータＲ１、ルータＲ２についてのトラフィック処理量を振り分ける。振り分けた結果、推定部１２４は、次に示すような推定値Ｔを取得することができる。
【００８８】
【数１１】
【００８９】
推定値Ｔを得たところでステップＳ２０６の繰り返し処理が終了したことになる。推定部１２４は、ステップＳ２０９において、式（３）からｕαを計算し、ｕαとｔαとの差ｄを式（４）によって計算する。ここでは、推定部１２４は、次の式を満たす場合に、Ｔをルータペアのトラフィック量と推定することにする。
【００９０】
【数１２】
【００９１】
推定部１２４は、式（３）によって求めたｕαを計算し、ｕαから式（４）により、ｄ＝１．１と求めることができる。このｄ＝１．１は、ルータペアのトラフィック量としての条件（例えば、式（１０））を満たさないので、推定部１２４は、ステップＳ２１０に進む。
【００９２】
推定部１２４は、ステップＳ２１０において、式（９）のＴよりΔｆを修正する。ここでは、推定部１２４は、式（１１）から｜ｃα｜が最大となるルータｋを求め、すべてのΔｆのｋ行目あるいはｋ列目のすべての要素に式（１２）で示される値を乗じてΔｆを更新する。これにより、次のルータについてのトラフィック処理量の割り振りのサイクルにおいて、次のルータについてのトラフィック処理量が多く割り振られていた場合には少なく、逆に、少なく割り振られていた場合には多く割り振ることができるようになる。
【００９３】
【数１３】
【００９４】
【数１４】
【００９５】
推定部１２４は、このようにして、ステップＳ２０５〜ステップＳ２１０を１５３回繰り返した結果、ルータペアのトラフィック量の推定値Ｔとして次に示すような結果が得られた。
【００９６】
【数１５】
【００９７】
推定部１２４は、推定値Ｔが式（１３）に示されるような値である場合には、式（３）と式（４）とからｄ＝０．００００９６５と求めることができる。推定部１２４は、ｄ＝０．００００９６５の場合には、ステップＳ２０９において、式（１０）を満たすと判断し、式（１３）で示されるＴを、ルータペアのトラフィック量の推定値として出力する。
【００９８】
ここで、ルータペアのトラフィック量の推定値Ｔは、Ｔ１，２＝０．４５からＴ２，５＝８．４６まで幅がある。これは、寄与行列Δに合致するようにトラフィック処理量を割り振るとともに、上記した仮定（※２）に基づいてトラフィック処理量を割り振ったことが原因である。Ｓの大きいルータ、例えば、最初に割り振りを行ったルータＲ６についてのトラフィック処理量は、Δ６の要素値に従って割り当てられている。そのために、Δ６の非零の要素間においてはＴの当該要素値の幅は小さい。しかし、Ｓの小さいルータ同士、例えば、ルータＲ１とルータＲ２との間のトラフィック量は、仮定（※２）からＴ１，２＝０．４５と小さな値に留まっている。
【００９９】
［効果の説明］
以上のように、第１実施形態によれば、同一期間内における各ルータのトラフィック処理量からルータペアのトラフィック量がなるべく均等になるようにしてルータペアのトラフィック量の推定値を求めることができる。これにより、リンクを流れるトラフィック量を知り、トラフィック量の多いリンクへのルーティングを避け、逆にトラフィック量が少ないリンクへのルーティングを促すことによって輻輳を避け、遅延の少ないルーティングを行うことが可能になる。
【０１００】
また、トラフィック量を推定するのに必要となるデータは、各ルータのトラフィック処理量と寄与行列とである。トラフィック処理量と寄与行列とは、各ルータから所定量ずつパケットを受け取ることによって取得することができる。探索用パケットの寿命を１つずつ増やして送出し、経路の往復時間を求める技術に比べれば、トラフィック量の推定に必要となるデータを得るためにネットワーク内に流すパケットの量を低減させることができる。
【０１０１】
さらに、トラフィック処理量と寄与行列とが揃えば、推定作業に移ることができるために、トラフィック量を推定するまでに要する時間も低減することができる。
【０１０２】
各ルータの同一期間内におけるトラフィック処理量を用いているので、推定したノードペアのトラフィック量には矛盾のない値で推定することができる。
【０１０３】
ルーティングプロトコルによってルーティングテーブルを取得することができ、ルーティングテーブルと各ルータによるルーティングルール（例えば、同一メトリックの経路には等分配するなど）から寄与行列を一意に定めることができる。よって、ルーティングテーブルが完成した時点で、ネットワーク構造の変化にも対応することが可能となる。
【０１０４】
［変形例］
上記では、添付図面を参照しながら本発明の好適な実施形態について説明したが、本発明は係る例に限定されないことは言うまでもない。当業者であれば、特許請求の範囲に記載された範疇内において、各種の変更例または修正例に想到し得ることは明らかであり、それらについても当然に本発明の技術的範囲に属するものと了解される。
【０１０５】
例えば、本実施形態に係る情報処理装置は、各ノードによって構成されるあらゆるネットワークに接続して利用することが可能である。例えば、Ｐ２Ｐの仮想ネットワークの構造や無線アドホックネットワークに接続してトラフィック量を推定することができる。また、本実施形態に係る情報処理装置は、推定値から各リンクの輻輳具合を知ることができるので、リンクの伝送時間を推定することも可能である。
【符号の説明】
【０１０６】
１００ 情報処理装置
１１０ 記憶部
１２０ 制御部
１２１ 経路情報取得制御部
１２２ リンク情報取得部
１２３ 寄与行列計算部
１２４ 推定部
１２５ 処理量計算部
１３０ 通信部
１３１ 経路情報送信要求送信部
１３２ 経路情報受信部
１３３ トラフィックデータ送信要求送信部
１３４ トラフィックデータ受信部
２００ ネットワーク
【技術分野】
【０００１】
本発明は、情報処理装置および情報処理方法に関するものである。より詳細には、ネットワークのリンクを流れるトラフィック量を推定する技術に関するものである。
【背景技術】
【０００２】
ネットワークの各リンク伝送時間を推定し、任意の経路でパケットが通過するのに要する時間を推定する技術がある（例えば、特許文献１または特許文献２参照）。これらの技術によれば、ホストが探索用パケットを送出し、そのパケットがネットワーク内の複数ルータを経由してホストに戻ってくるまでの往復時間を得る処理を行う。ホストは、この処理を繰り返し実行することによってネットワークの種々の経路についての往復時間を求めることができる。また、ホストは、この往復時間から、各リンクにおける伝送時間を変数とした連立１次方程式を立て、学習されたニューラルネットによって近似解を求めることができる。近似解は、任意の経路のパケットの通過時間として算出される。これらの技術を用いれば、ネットワークの各リンクの伝送時間が求められているので、トラフィック伝送量の多いリンクを推定し、そのリンクを避けることによって伝送遅延の少ないルーティングを行うことが可能となる。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２０００−３２０３８号公報
【特許文献２】特開２０００−４９８６３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、これらの技術を用いてルーティングを行うこととした場合には、少なくとも、以下の４点が問題となる。
【０００５】
第１に、ホストがネットワーク内に複数の（あるいは多数の）探索用パケットを流すことによって、ネットワークにかかる負荷を増大させる可能性があるという問題がある。
【０００６】
第２に、ホストがリンクの伝送時間を算出するためのデータを揃えるまでに時間がかかるという問題がある。ホストが経路の往復時間を求めるために多数の探索用パケットを流し、その探索用パケットが戻ってくるまで待機する必要があるからである。この問題は、ネットワークが大きく、かつ、複雑になるほど顕著になる。
【０００７】
第３に、ネットワークが大きくなるほど、連立１次方程式によって求められる近似解の現実の値からの誤差が大きくなるという問題がある。ホストがネットワーク内に複数の探索用パケットを流すことにより、ネットワーク内の各ルータにかかる負荷が増大し、接続されているリンク数の多いルータには特に大きな負荷がかかることになる。ルータに対する負荷が増大し、ルータによるパケットに対する処理に時間がかかれば、パケットの往復時間が、厳密にはリンクの伝送時間だけからなるとは言えなくなる。これに加えて、リンクの伝送時間は時々刻々変化するものであり、例えば、ネットワークが大きく複雑であるほど、探索用パケットが多く必要になる。よって、それぞれの探索用パケットが処理される時刻は異なってくる。
【０００８】
第４に、ネットワークの構造変化に対して速やかに対応できないという問題がある。ルータ数またはリンク数の増減やリンクの付け替えなどによってネットワークの構造が変わった場合には、ホストは、連立１次方程式を立てるために必要十分な経路を改めて求めなければならない。
【０００９】
そこで、本発明は、上記問題に鑑みてなされたものであり、本発明の目的とするところは、主として、ネットワークを構成するリンクを流れるトラフィック量の推定を行うに際して、ネットワークにかかる負荷を低減させることが可能な技術を提供することにある。
【課題を解決するための手段】
【００１０】
上記問題を解決するために、本発明のある観点によれば、複数のノード間がリンクによって相互に接続されることによって構成されるネットワークに接続され、複数のノードから任意に２つのノードを選択して得られる各ノードペア間のリンクを流れるパケット量であるトラフィック量を推定する情報処理装置であって、リンクによる各ノード間の接続関係を示すリンク情報を取得するリンク情報取得部と、同一期間内に各ノードを流れたパケット量を当該ノードに対応する各トラフィック処理量として計算する処理量計算部と、リンク情報と各トラフィック処理量とに基づいて、各ノードペア間を流れるパケット量に対する当該パケットのうちでノードを流れるパケット量の割合を各要素に有する行列を、当該ノードに対応する各寄与行列として計算する寄与行列計算部と、各ノードに対応する各寄与行列に基づいて、各ノードに対応する各トラフィック処理量を各ノードペアに割り振ることによってトラフィック量を推定する推定部と、を備えることを特徴とする、情報処理装置が提供される。
【００１１】
推定部は、各ノードペアに割り振る各トラフィック処理量として寄与行列の各要素値に比例する値を使用することとしてもよい。
【００１２】
推定部は、寄与行列の要素値の総和が大きいノードから順に、当該ノードに対応するトラフィック処理量を各ノードペアに割り振ることとしてもよい。
【００１３】
推定部は、寄与行列の非零の要素数が大きいノードから順に、当該ノードに対応するトラフィック処理量を各ノードペアに割り振ることとしてもよい。
【００１４】
推定部は、推定したトラフィック量から各ノードを流れたパケット量であるトラフィック処理量を計算し、計算したトラフィック処理量と処理量計算部によって計算されたトラフィック処理量との大小関係を判断し、計算したトラフィック処理量のほうが大きいと判断した場合には、当該ノードを含むノードペアに対して割り振るトラフィック処理量を減少させ、計算したトラフィック処理量のほうが小さいと判断した場合には、当該ノードを含むノードペアに対して割り振るトラフィック処理量を増加させることによって、再度トラフィック量の割り振りを行うこととしてもよい。
【発明の効果】
【００１５】
以上説明したように本発明によれば、主として、ネットワークを構成するリンクを流れるトラフィック量の推定を行うに際して、ネットワークにかかる負荷を低減させることが可能となる。
【図面の簡単な説明】
【００１６】
【図１】ネットワークの構成を説明するための図である。
【図２】本実施形態に係る情報処理装置の機能構成を示す図である。
【図３】ネットワークと情報処理装置との構成例を示す図である。
【図４】情報処理装置が実行する経路情報の取得から寄与行列の計算までの処理の流れを示すフローチャートである。
【図５】ルータごとのトラフィック処理量のデータ例を示す図である。
【図６】ルーティングテーブルのデータ例を示す図である。
【図７】情報処理装置が実行するトラフィック量推定処理の流れを示すフローチャートである。
【発明を実施するための形態】
【００１７】
以下に添付図面を参照しながら、本発明の好適な実施の形態について詳細に説明する。なお、本明細書及び図面において、実質的に同一の機能構成を有する構成要素については、同一の符号を付することにより重複説明を省略する。
【００１８】
＜第１本実施形態＞
［概要の説明］
図１は、ネットワークの構成を説明するための図である。図１に示すように、ネットワーク２００’は、各ノード（ノードＮ１〜Ｎ５）が連携して送信元から送信先にパケットの送信を行うものである。パケットとは、送信元から送信先に送信されるデータの単位として使用する。また、ここでは、ネットワーク２００’は、５つのノードによって構成されることとしているが、ノードの数は特に限定されるものではない。また、ノードの一例としては、ルータを使用することができるが、ノードは特にルータに限定されるものではなく、ネットワーク２００’を構成する装置であってパケットの送受信を行うものを適宜使用することができる。
【００１９】
ノードペアとは、任意のノードの組を示すものであり、直接的にリンクによって接続されているノード同士のみを意味するものではない。例えば、ノードＮ１とノードＮ２との組、ノードＮ３とノードＮ４との組のみではなく、例えば、ノードＮ１とノードＮ４との組、ノードＮ３とノードＮ５との組などもノードペアと称する。ノードの一例としてルータを使用する場合には、上記したノードペアを特にルータペアと称する。本実施形態では、ノードのトラフィック処理量と寄与行列とを用いてノードペアごとのトラフィック量を推定する。ノードのトラフィック処理量とは、例えば、ノードが処理するパケットの量であり、例えば、ノードが処理する単位時間あたりのパケットの量を意味するものとする。寄与行列については後述する。ノードペアごとのトラフィック量とは、例えば、ノードペア間において送受信されるパケットの量であり、例えば、ノードペア間において送受信される単位時間あたりのパケットの量を意味するものとする。
【００２０】
ところが、このノードのトラフィック処理量と寄与行列との情報からだけでは何通りもの推定量の候補が計算される。そこで、「ノードペアごとのトラフィック量が可能な限り均等になるようにノードのトラフィック処理量を割り当てる」という条件を満たすようにトラフィック量を推定することによって推定量の候補を絞ることにする。この条件は、ネットワーク２００’が大きくなるほどノードペアごとのトラフィック量は均一になるという考え方に基づいている。
【００２１】
［寄与行列の説明］
寄与行列は、ルータごとに作成される行列であり、例えば、ノードｋの寄与行列と言った場合には、その｛ｉ，ｊ｝要素は、ノードｉから始まりノードｊで終端するトラフィック量に対するｋを通るトラフィック量の割合を示すものである。ノードｉから始まりノードｊで終端するパケットがすべてノードｋを通る場合には、｛ｉ，ｊ｝要素は、「１」となり、ノードｋが関与しない（ノードｉから始まりノードｊで終端するパケットがノードｋを通らない）場合には、「０」となる。ネットワーク２００内のルーティング方法が決まれば、ネットワーク２００内の全寄与行列も一意に定まる。例えば、図１に示したノードＮ５の寄与行列Δ５は、次のように示される。
【００２２】
【数１】
【００２３】
ここで、経路選択には、最短経路法を採用し、経路が複数存在する場合には分岐点において経路ごとに等分配することとしている。また、ノードＮ２とノードＮ４との間のトラフィック量は、経路（ノードＮ２、ノードＮ３およびノードＮ４の順に通過する経路）と経路（ノードＮ２、ノードＮ５およびノードＮ４の順に通過する経路）とに二分されるので、｛２，４｝および｛４，２｝要素は、それぞれ「０．５」となる。一方、ノードＮ１およびノードＮ４との間で送受信されるパケットは、必ずノードＮ５を通るので、｛１，４｝および｛４，１｝要素は、「１」となる。｛ｉ，ｊ｝要素は、Δ５ｉ，ｊと表すこととする。
【００２４】
また、ノードｉから始まりノードｊで終端するトラフィック量を｛ｉ，ｊ｝要素とする行列をＴｉ，ｊと表せば、ノードｋを通るトラフィック処理量ｔｋは、次のように、要素ごとの積の和という形式で示される。
【００２５】
【数２】
【００２６】
以下においては、ノードによって構成されるネットワーク２００’の一例として、ルータによって構成されるネットワーク２００（例えば、図２または図３参照）を使用する場合について説明する。
【００２７】
［構成の説明］
図２は、本実施形態に係る情報処理装置の機能構成を示す図である。図２を参照して、本実施形態に係る情報処理装置の機能構成について説明する。
【００２８】
図２に示すように、情報処理装置１００は、ネットワーク２００に接続されている。ネットワーク２００は、複数のルータ間がリンクによって相互に接続されることによって構成されている（図３参照）。情報処理装置１００は、複数のルータから任意に２つのルータを選択して得られる各ルータペア間のリンクを流れるパケット量であるトラフィック量を推定する。情報処理装置１００は、記憶部１１０と制御部１２０と通信部１３０とを備えるものである。パケット量としては、パケットの数を使用することとしてもよいし、パケットのデータ量を使用することとしてもよい。
【００２９】
記憶部１１０は、例えば、ＨＤＤ（Ｈａｒｄ Ｄｉｓｋ Ｄｒｉｖｅ）等の記憶装置などによって構成される。記憶部１１０は、制御部１２０によって実行されるプログラムを記憶する機能や、プログラムが使用するデータを記憶する機能を有するものである。
【００３０】
制御部１２０は、例えば、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）などによって構成され、ＣＰＵによって、記憶部１１０が記憶するプログラムがＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）などに展開され、展開されたプログラムが実行されることによってその機能が実現される。制御部１２０は、経路情報取得制御部１２１、リンク情報取得部１２２、寄与行列計算部１２３、推定部１２４、処理量計算部１２５などを備える。
【００３１】
通信部１３０は、例えば、通信装置等によって構成され、ネットワーク２００内のルータと通信を行うことが可能である。通信部１３０は、経路情報送信要求送信部１３１、経路情報受信部１３２、トラフィックデータ送信要求送信部１３３、トラフィックデータ受信部１３４などを備えるものである。
【００３２】
トラフィックデータ受信部１３４は、ＳＮＭＰ（Ｓｉｍｐｌｅ Ｎｅｔｗｏｒｋ Ｍａｎａｇｅｍｅｎｔ Ｐｒｏｔｏｃｏｌ）のＭＩＢ（Ｍａｎａｇｅｍｅｎｔ Ｉｎｆｏｒｍａｔｉｏｎ Ｂａｓｅ）情報のうちトラフィック処理量をネットワーク２００内のすべてのルータから定期的に受信する。トラフィックデータ受信部１３４は、受信したトラフィック処理量を処理量計算部１２５に出力する。
【００３３】
処理量計算部１２５は、トラフィックデータ受信部１３４から出力されたトラフィック処理量から同一期間内に各ルータを流れたパケット量をそのルータに対応する各トラフィック処理量として計算する。同一期間は、その開始時刻も同一であることが好ましいが、期間の長さは、例えば、１０秒間、５分間、１時間など、どのような長さであってもよい。処理量計算部１２５は、計算したトラフィック処理量を推定部１２４に出力する。
【００３４】
経路情報受信部１３２は、ネットワーク２００内のすべてのルータからルーティングテーブル（経路情報）を受信し、受信したルーティングテーブルをリンク情報取得部１２２に出力する。
【００３５】
リンク情報取得部１２２は、経路情報受信部１３２から出力されたルーティングテーブルに基づいて、ネットワーク２００内の各ルータ間のリンクによる接続関係を示すリンク情報を取得して、取得したリンク情報を寄与行列計算部１２３に出力する。リンク情報取得部１２２は、必要となるリンク情報が取得できない場合には、経路情報取得制御部１２１に対してルーティングテーブルの送信を求めるルータを識別するための識別情報を出力する。
【００３６】
経路情報取得制御部１２１は、ネットワーク２００内のルータからルーティングテーブルを取得するための制御を行うものである。経路情報取得制御部１２１は、例えば、リンク情報取得部１２２から出力された識別情報によって識別されるルータに対して経路情報送信要求を送信するように経路情報送信要求送信部１３１を指示する。
【００３７】
経路情報送信要求送信部１３１は、経路情報取得制御部１２１からの指示に従って、経路情報送信要求を送信する。経路情報送信要求を受信したルータは、ルーティングテーブルを送信し、送信されたルーティングテーブルが、経路情報受信部１３２によって受信される。
【００３８】
寄与行列計算部１２３は、リンク情報と各トラフィック処理量とに基づいて、各ルータペア間を流れるパケット量に対するそのパケットのうちでルータを流れるパケット量の割合を各要素に有する行列を、そのルータに対応する各寄与行列として計算する。寄与行列計算部１２３は、計算した寄与行列を推定部１２４に出力する。
【００３９】
推定部１２４は、各ルータに対応する各寄与行列に基づいて、各ルータに対応する各トラフィック処理量を各ルータペアに割り振ることによってトラフィック量を推定する。推定部１２４は、推定するルータペアのトラフィック量を、ルータペアごとのトラフィック量が可能な限り均等になるように割り振る（※１）ことが好ましい。これは、ネットワーク２００の規模が大きくなればなるほどルータペアごとのトラフィック量は均一になるという考えに基づくものである。また、これを実現するために、例えば、推定部１２４は、各ルータペアに割り振る各トラフィック処理量として寄与行列の各要素値に比例する値を使用することができる。
【００４０】
これは、条件（※１）に反するようにも受け取れる。しかし、ルータペア間｛ｉ，ｊ｝のトラフィック（ルータペア間｛ｉ，ｊ｝を流れるパケット）が複数の経路を通ってルーティングされる場合、分岐した経路上にあるルータｋについての寄与行列Δｋｉ，ｊは、１より小さい。したがって、ルータｋについてのトラフィック処理量の割り振りは、ルータペア間｛ｉ，ｊ｝のトラフィックに対するルータｋによる関与が、他の成分「１」に相当するルータペア間のトラフィックに対するルータｋによる関与よりも小さい分少なくなる。これは、トラフィック処理量を可能な限り均等に割り振った結果であり、別経路のルータについてのトラフィック処理量がルータペア｛ｉ，ｊ｝に割り振られるので、ルータペア｛ｉ，ｊ｝に対して割り振られるトラフィック処理量が少ないということにはならない。
【００４１】
また、推定部１２４は、寄与行列の要素値の総和が大きいルータから順に、そのルータに対応するトラフィック処理量を各ルータペアに割り振ることとしてもよい。あるいは、推定部１２４は、寄与行列の非零の要素数（S）が大きいルータから順に、そのルータに対応するトラフィック処理量を各ルータペアに割り振ることとしてもよい。これは、ネットワーク２００の規模が大きくなるほどルータペアごとのトラフィック量は均一になると一応は考えられるものの、ネットワーク２００全体に流れるトラフィック量のうちＳの小さいルータ同士をルータペアとするトラフィック量は相対的に小さいという仮定（※２）に基づくものである。Ｓの小さいルータに対する割り振りを劣位に置くことで、Ｓの小さいルータ同士をルータペアとするトラフィック量が小さくなるという効果が得られる。
【００４２】
推定部１２４は、推定したトラフィック量から各ルータを流れたパケット量であるトラフィック処理量を計算し、計算したトラフィック処理量と処理量計算部１２５によって計算されたトラフィック処理量との大小関係を判断してもよい。推定部１２４は、計算したトラフィック処理量のほうが大きいと判断した場合には、そのルータを含むルータペアに対して割り振るトラフィック処理量を減少させ、計算したトラフィック処理量のほうが小さいと判断した場合には、そのルータを含むルータペアに対して割り振るトラフィック処理量を増加させることとしてもよい。このようにして、再度トラフィック量の割り振りを行うこととしてもよい。そうすれば、計算したトラフィック処理量と処理量計算部１２５によって計算されたトラフィック処理量との差が小さくすることができ、再度のトラフィック量の割り振りを繰り返せば、さらにその差を小さくしていくことができる。
【００４３】
推定部１２４は、推定したトラフィック量を推定データとして出力する。推定部１２４は、処理量計算部１２５から出力されていないトラフィック処理量があれば、そのトラフィック処理量に対応するルータにトラフィックデータ送信要求を送信するための指示をトラフィックデータ送信要求送信部１３３に出力することができる。
【００４４】
トラフィックデータ送信要求送信部１３３は、推定部１２４から出力された指示に従って、トラフィックデータ送信要求をルータに送信する。トラフィックデータ送信要求を受信したルータは、トラフィック処理量を送信し、送信されたトラフィック処理量はトラフィックデータ受信部１３４によって受信される。
【００４５】
図３は、ネットワークと情報処理装置との構成例を示す図である。図４は、情報処理装置が実行する経路情報の取得から寄与行列の計算までの処理の流れを示すフローチャートである。図５は、ルータごとのトラフィック処理量のデータ例を示す図である。図６は、ルーティングテーブルのデータ例を示す図である。
【００４６】
［動作の説明］
図２〜図７を参照して、情報処理装置１００が実行するトラフィック量推定処理の動作例について説明する。説明の都合上、ネットワーク２００内のルータ数をＮとする。また、経路情報の一例として、ルータが持つルーティングテーブルを使用することとする。図４は、経路情報の取得から寄与行列の計算までの処理の流れを示すフローチャートである。まず、図４を参照して、情報処理装置１００による経路情報の取得から寄与行列の計算までの処理について説明する。
【００４７】
以下のステップＳ１０１〜ステップＳ１０４は、ネットワーク２００内の各ルータの寄与行列Δの計算に関連するものである。まず、経路情報受信部１３２は、各ルータの持つルーティングテーブルを取得する（ステップＳ１０１）。リンク情報取得部１２２は、経路情報受信部１３２によって受信されたルーティングテーブルに基づいて、各ルータのリンク情報を取得する（ステップＳ１０２）。このリンク情報とは、各ルータがどのルータに対してリンクを持っているか、すなわち、各ルータがどのルータに対してパケットを送信できるかを示すものである。
【００４８】
経路情報取得制御部１２１は、データが揃っているか否か、すなわち、各ルータのリンク情報が取得されているか否かを判断する（ステップＳ１０３）。経路情報取得制御部１２１は、データが揃っていないと判断した場合には（ステップＳ１０３で「Ｎｏ」）、ステップＳ１０１に戻る。ステップＳ１０１に戻った場合には、経路情報送信要求送信部１３１は、リンク情報取得部１２２で必要となるルーティングテーブルを持つルータに対して経路情報送信要求パケットを送信し、経路情報受信部１３２は、経路情報送信要求パケットに対する応答として、そのルータから経路情報を受信する。
【００４９】
経路情報取得制御部１２１は、データが揃っていると判断した場合には（ステップＳ１０３で「Ｙｅｓ」）、寄与行列計算部１２３は、各ルータの寄与行列｛Δα：α∈１，・・・，Ｎ｝を計算する。ステップＳ１０１〜ステップＳ１０３は、例えば、ルーティングテーブルに変化がある度に実行されるものである。
【００５０】
図７は、トラフィックデータと寄与行列との取得からトラフィック量の推定までの処理の流れを示すフローチャートである。まず、図７を参照して、情報処理装置１００によるトラフィックデータと寄与行列との取得からトラフィック量の推定までの処理について説明する。
【００５１】
推定部１２４は、処理量計算部１２５が計算したトラフィック処理量を取得する（ステップＳ２０１）。ここでいうトラフィック処理量は、各ルータが同一期間に処理したパケットの量、すなわち、各ルータの同一期間におけるトラフィック処理量｛ｔα：α∈１，・・・，Ｎ｝を意味するものである。各ルータの同一期間におけるトラフィック処理量をトラフィック処理量として使用することとするが、上記の同一期間とは、厳密に同一の期間である必要はなく、略同一の期間であればよい。続いて、推定部１２４は、寄与行列計算部１２３が計算した寄与行列Δを取得する（ステップＳ２０２）。
【００５２】
推定部１２４は、ステップＳ２０１およびステップＳ２０２において取得されるデータが揃っているか否かを判断する（ステップＳ２０３）。推定部１２４は、データが揃っていないと判断した場合には（ステップＳ２０３で「Ｎｏ」）、ステップＳ２０１に戻る。推定部１２４が、トラフィック処理量が揃っていないと判断した場合には、トラフィックデータ送信要求送信部１３３は、揃っていないトラフィック処理量のもとになるトラフィックデータを持つルータに対してトラフィックデータ送信要求を送信する。トラフィックデータ受信部１３４は、そのトラフィックデータ送信要求に対する応答として、トラフィックデータを受信して処理量計算部１２５に出力する。処理量計算部１２５は、トラフィックデータからトラフィック処理量を計算して推定部１２４に出力する。
【００５３】
推定部１２４は、寄与行列が揃っていないと判断した場合には、寄与行列計算部１２３から寄与行列が出力されるのを待つ。
【００５４】
推定部１２４は、データが揃っていると判断した場合には（ステップＳ２０３で「Ｙｅｓ」）、ステップＳ２０４以降においてルータペアのトラフィック量の推定を行う。推定部１２４は、各ルータのトラフィック処理量を割り振るために用いる、Δαのコピー｛Δｆα：１≦α≦Ｎ｝をルータごとに用意する。Δｆαの要素値が、ルータαのトラフィック処理量をルータペアのトラフィック量に割り振る際に使用される係数となる。この要素値は、ステップＳ２１０において適宜修正される。
【００５５】
推定部１２４は、各ルータの寄与行列Δについての非零の要素数Ｓを計算し、計算したＳに基づいてルータの順番ａ［１］＝ｋ１、ａ［２］＝ｋ２、・・・、ａ［Ｎ］＝ｋＮを決める。ここで、ａ［１］〜ａ［Ｎ］は、例えば、値を設定できる配列であり、ｋ１〜ｋＮは、ルータを識別するための値である。推定部１２４は、例えば、Ｓの大きいルータから順にｋ１、ｋ２、・・・、ｋＮとし、そのＳをそれぞれＳｋ１、Ｓｋ２、・・・、ＳｋＮと表現する。推定部１２４は、このｋ１、ｋ２、・・・、ｋＮの順にトラフィック処理量を割り振る。
【００５６】
推定部１２４は、ルータｋ１のトラフィック処理量ｔｋ１をΔｆｋ１の分布に従って割り振る（ステップＳ２０５）。推定部１２４は、例えば、ルータｋ１のトラフィック処理量ｔｋ１をΔｆｋ１の分布に従ってΔｆｋ１ｉ，ｊに比例した割合で割り振る。トラフィック処理量が割り振られることによって得られるトラフィック量は、式（１）のＴのように行列で表される。ここでは、トラフィック処理量ｔｋ１を割り振ることによって得られるトラフィック量は、Ｎ×Ｎの行列Ｔｋ１と表現することとする。
【００５７】
ステップＳ２０６の繰り返し処理では、推定部１２４は、残りのルータｋ２、ｋ３、・・・、ｋＮのトラフィック処理量を割り振ることとなる。ここで、ａ［２］＝ｋ２、ａ［３］＝ｋ３、・・・、ａ［Ｎ］＝ｋＮとし、ステップＳ２０６が開始される際に実行される初期処理はｎ＝２（ｎに２を代入）、ステップＳ２０６を継続するための継続条件はｎ≦Ｎ、ステップＳ２０６が繰り返されるたびに実行される終端処理はｎ＝ｎ＋１（ｎを１増加）とする。
【００５８】
推定部１２４は、ステップＳ２０６の繰り返し処理の中で、ａ［ｎ］で指定されるルータについて割り振るトラフィック処理量ｔａ［ｎ］’を計算する（ステップＳ２０７）。計算式は、例えば、次に示すようになる。
【００５９】
【数３】
【００６０】
式（２）の右辺第２項は、ルータａ［ｎ−１］についてまで割り振ったトラフィック量Ｔｎ−１のうちルータａ［ｎ］において処理する量を示し、これをｔｎから差し引いた量がルータａ［ｎ］について割り振れるトラフィック処理量ｔａ［ｎ］’となる。
【００６１】
推定部１２４は、ステップＳ２０５における割り振り処理と同様の手法によって、トラフィック処理量ｔａ［ｎ］’をΔｆａ［ｎ］の分布に従って割り振る（ステップＳ２０８）。推定部１２４は、例えば、トラフィック処理量ｔａ［ｎ］’をΔｆａ［ｎ］の分布に従ってΔｆａ［ｎ］ｉ，ｊに比例した割合で割り振る。推定部１２４は、トラフィック処理量ｔａ［ｎ］’が割り振られることによって得られた各値をＴｎ−１の各要素に追加する。このようにして更新した後のトラフィック量はＴｎとなる。
【００６２】
推定部１２４は、ステップＳ２０６の繰り返し処理によって得られたＴＮから計算される各ルータのトラフィック処理量とｔαとの差が所定の範囲に収まっているか否かを判断する（ステップＳ２０９）。そのために、まず、推定部１２４は、例えば、ＴＮから各ルータのトラフィック量｛ｕα：１≦α≦Ｎ｝を次のように計算する。
【００６３】
【数４】
【００６４】
推定部１２４は、例えば、計算したｕαとトラフィック処理量ｔαとの差（あるいは差の２乗によって得られるｄ）が所定の範囲内に収まっているか否かを判断する。推定部１２４は、例えば、計算したｕαとトラフィック処理量ｔαとの差の２乗によって得られるｄとして次の式を使用することができる。
【００６５】
【数５】
【００６６】
推定部１２４は、ＴＮから計算される各ルータのトラフィック処理量とｔαとの差が所定の範囲に収まっていると判断した場合には、このＴＮを推定量（推定データ）として出力する。推定部１２４は、ＴＮから計算される各ルータのトラフィック処理量とｔαとの差が所定の範囲に収まっていないと判断した場合には、ステップＳ２１０に進む。推定部１２４は、各ノードペアへのトラフィック処理量の割り振り量を修正するために、Δｆを更新すると（ステップＳ２１０）、ステップＳ２０５に戻って処理を継続する。
【００６７】
［動作の具体例の説明］
図４〜図７を参照して、情報処理装置１００が実行するトラフィック量推定処理の動作の具体例について説明する。ネットワーク２００は、図３に示したように、ルータＲ１〜ルータＲ６によって構成されるものとして説明するが、ネットワーク２００の構成はこれに限定されるものではない。図３に示した情報処理装置１００は、図２に示した情報処理装置１００に相当するものである。パケットは、ルータＲ１〜ルータＲ６の外側には送出されない状況を想定し、ルータＲ１〜ルータＲ６のそれぞれに接続しているリンクを通じてパケットの送受信を行うものとする。また、以下の推定で用いるルータペア間のトラフィック量の候補を６×６行列Ｔと表現する。
【００６８】
情報処理装置１００において、ルータＲ１〜ルータＲ６が処理したトラフィック処理量からルータペア間のトラフィック量を推定する。情報処理装置１００は、トラフィックデータ受信部１３４においてＳＮＭＰのＭＩＢ情報のうちトラフィック処理量をルータＲ１〜ルータＲ６から定期的に受信している。トラフィックデータ受信部１３４によって受信された処理量計算部１２５に出力され、処理量計算部１２５によって同一期間内におけるトラフィック処理量が取得される。
【００６９】
いま、例えば、処理量計算部１２５によって、ある時刻に観測された各ルータのトラフィック処理量｛ｔα：１≦α≦６｝が図５に示すような情報として取得されたとする。ただし、ルータαから始まりルータαで終端するパケットによるトラフィック処理量は含まれないこととする。したがって、Ｔの対角成分は「０」となり、すなわち、｛Ｔｉ，ｉ＝０：１≦i≦６｝となる。処理量計算部１２５によって取得されたトラフィック処理量は、推定部１２４に出力される。
【００７０】
次に、寄与行列計算部１２３が寄与行列を計算する過程について説明する。ステップＳ１０１において、経路情報受信部１３２が、ルータＲ１〜ルータＲ６からそれぞれのルーティングテーブルを受信し、リンク情報取得部１２２は、経路情報受信部１３２によって受信されたルーティングテーブルに基づいて、リンク情報を取得する。ここでは、リンク情報取得部１２２は、最短経路法に基づいて経路選択を行うこととし、最短経路が複数存在する場合には、ノードペアごとに１つの経路を選択することとする。一例として、リンク情報取得部１２２がルータＲ５のリンク情報を取得する場合について説明する。ルータＲ５が持つルーティングテーブルが、図６に示すようなものであった場合、リンク情報取得部１２２は、Ｎｅｘｔ Ｈｏｐ Ｎｏｄｅに基づいて、ルータＲ５がルータＲ４およびルータＲ６の２つのルータに対してリンクを張っていると判断することができる。つまり、リンク情報取得部１２２は、ルータＲ５のリンク情報として、ルータＲ４およびルータＲ６を識別するための情報をルーティングテーブルから取得することができる。
【００７１】
リンク情報取得部１２２が各ルータについて同様にしてリンク情報を取得することができると、ステップＳ１０３の条件が満たされ、寄与行列計算部１２３は、ステップＳ１０４においてΔαを計算する。経路選択方法が最短経路法によるものであれば、ルータＲ１〜ルータＲ６の寄与行列｛Δα：１≦α≦６｝としては、次に示すような行列を挙げることができる。
【００７２】
【数６】
【００７３】
以下の説明においても、Δ１〜Δ６をそれぞれルータＲ１〜ルータＲ６の寄与行列とする。そして、寄与行列計算部１２３によって計算された寄与行列Δ１〜Δ６が推定部１２４に出力される。
【００７４】
続いて、推定部１２４の動作の具体例について図７を参照して（適宜他の図参照）、説明する。上記したように、ステップＳ２０１において処理量計算部１２５によってルータＲ１〜ルータＲ６のトラフィック処理量ｔ１〜ｔ６が取得され、ステップＳ２０２において寄与行列計算部１２３によって寄与行列Δ１〜Δ６が取得されたとすると、ステップＳ２０３の条件を満たす。
【００７５】
ここで、どの寄与行列Δαも対称行列、すなわち、｛Δαｉ，ｊ＝Δαｊ，ｉ：１≦i≦６, 1≦j≦6｝であるから、簡単のために、以下で推定するルータペアのトラフィック量は、ルータペアの方向を区別しないこととする。よって、推定すべきＴは、次のように示すことができる。
【００７６】
【数７】
【００７７】
推定すべきＴが（５）式のように示される場合、推定部１２４は、Ｔ１，２，・・・Ｔ５，６の計１５成分を推定することになる。
【００７８】
ステップＳ２０４において、推定部１２４は、各ルータについてＳを求める。例えば、ルータＲ１についてのΔ１の非零（例えば、「１」）の要素数は「１０」であるから、推定部１２４は、ルータＲ１についての各ＳであるＳ１の値を「１０」と求める。同様にして、推定部１２４は、ルータＲ２〜ルータＲ６についての各ＳであるＳ２〜Ｓ６の値を「１０」「１２」「１２」「１４」「２２」と求める。したがって、推定部１２４は、トラフィック処理量を割り振る順番として、ルータＲ６、ルータＲ５、ルータＲ３、ルータＲ４、ルータＲ１、ルータＲ２と決定する。ここで、Ｓ１＝Ｓ２であり、Ｓ３＝Ｓ４であるので、ルータＲ１とルータＲ２とのうち、または、ルータＲ３とルータＲ４とのうち、どちらの順番を早めるかを決定する必要があるが、決定の仕方は特に限定されるものではない。
【００７９】
推定部１２４は、ステップＳ２０５において、トラフィック処理量ｔ６＝６１を割り振る（図５参照）。推定部１２４は、Δαのコピー｛Δｆα：１≦α≦Ｎ｝をルータごとに用意すると、Δｆ６は、次に示す通りとなる。
【００８０】
【数８】
【００８１】
式（６）に示すように、Δｆ６の要素値はすべて「１」となっている。また、いまは、Ｔ１，２〜Ｔ５，６の１５成分についてのみ考えているので、推定部１２４は、その成分に相当する非零の要素数、すなわち、割り振るべき要素値を「１１」と決定する。したがって、推定部１２４は、ｔ６／（割り振るべき要素値）＝６１／１１＝５．５５を割り振ると、次に示すＴ６のようになる。
【００８２】
【数９】
【００８３】
次に、推定部１２４は、ステップＳ２０６において、トラフィック処理量ｔ５，ｔ３，ｔ４，ｔ１，ｔ２を順次に割り振る。
【００８４】
推定部１２４は、ステップＳ２０７において、ルータＲ５について割り振るトラフィック処理量ｔ５’を計算する。式（２）により、推定部１２４は、ｔ５’＝ｔ５−Σ６ｉ＝１Σ６ｊ＝１（Δｆ５ｉ，ｊＴ６ｉ，ｊ）＝３４−２７．７３＝６．２７と計算する。
【００８５】
推定部１２４は、ステップＳ２０８において、ステップＳ２０７で算出したｔ５’＝６．２７をルータＲ６についてのトラフィック処理量ｔ６’と同様に割り振る。Δｆ５ｉ，ｊの各要素の非零の値はすべて「１」であり、割り振るべき要素数は、Δｆ５１，５，Δｆ５２，４，Δｆ５２，５，Δｆ５３，５，Δｆ５４，５，Δｆ５４，６，Δｆ５４，７の７つであるから、推定部１２４は、ｔ５’／（割り振るべき要素値）＝６．２７／７＝０．９０をＴ６１，５，Ｔ６２，４，Ｔ６２，５，Ｔ６３，５，Ｔ６４，５，Ｔ６４，６，Ｔ６４，７に追加する。その結果は、Ｔ５は、次に示すようになる。
【００８６】
【数１０】
【００８７】
同様にして、推定部１２４は、ルータＲ３、ルータＲ４、ルータＲ１、ルータＲ２についてのトラフィック処理量を振り分ける。振り分けた結果、推定部１２４は、次に示すような推定値Ｔを取得することができる。
【００８８】
【数１１】
【００８９】
推定値Ｔを得たところでステップＳ２０６の繰り返し処理が終了したことになる。推定部１２４は、ステップＳ２０９において、式（３）からｕαを計算し、ｕαとｔαとの差ｄを式（４）によって計算する。ここでは、推定部１２４は、次の式を満たす場合に、Ｔをルータペアのトラフィック量と推定することにする。
【００９０】
【数１２】
【００９１】
推定部１２４は、式（３）によって求めたｕαを計算し、ｕαから式（４）により、ｄ＝１．１と求めることができる。このｄ＝１．１は、ルータペアのトラフィック量としての条件（例えば、式（１０））を満たさないので、推定部１２４は、ステップＳ２１０に進む。
【００９２】
推定部１２４は、ステップＳ２１０において、式（９）のＴよりΔｆを修正する。ここでは、推定部１２４は、式（１１）から｜ｃα｜が最大となるルータｋを求め、すべてのΔｆのｋ行目あるいはｋ列目のすべての要素に式（１２）で示される値を乗じてΔｆを更新する。これにより、次のルータについてのトラフィック処理量の割り振りのサイクルにおいて、次のルータについてのトラフィック処理量が多く割り振られていた場合には少なく、逆に、少なく割り振られていた場合には多く割り振ることができるようになる。
【００９３】
【数１３】
【００９４】
【数１４】
【００９５】
推定部１２４は、このようにして、ステップＳ２０５〜ステップＳ２１０を１５３回繰り返した結果、ルータペアのトラフィック量の推定値Ｔとして次に示すような結果が得られた。
【００９６】
【数１５】
【００９７】
推定部１２４は、推定値Ｔが式（１３）に示されるような値である場合には、式（３）と式（４）とからｄ＝０．００００９６５と求めることができる。推定部１２４は、ｄ＝０．００００９６５の場合には、ステップＳ２０９において、式（１０）を満たすと判断し、式（１３）で示されるＴを、ルータペアのトラフィック量の推定値として出力する。
【００９８】
ここで、ルータペアのトラフィック量の推定値Ｔは、Ｔ１，２＝０．４５からＴ２，５＝８．４６まで幅がある。これは、寄与行列Δに合致するようにトラフィック処理量を割り振るとともに、上記した仮定（※２）に基づいてトラフィック処理量を割り振ったことが原因である。Ｓの大きいルータ、例えば、最初に割り振りを行ったルータＲ６についてのトラフィック処理量は、Δ６の要素値に従って割り当てられている。そのために、Δ６の非零の要素間においてはＴの当該要素値の幅は小さい。しかし、Ｓの小さいルータ同士、例えば、ルータＲ１とルータＲ２との間のトラフィック量は、仮定（※２）からＴ１，２＝０．４５と小さな値に留まっている。
【００９９】
［効果の説明］
以上のように、第１実施形態によれば、同一期間内における各ルータのトラフィック処理量からルータペアのトラフィック量がなるべく均等になるようにしてルータペアのトラフィック量の推定値を求めることができる。これにより、リンクを流れるトラフィック量を知り、トラフィック量の多いリンクへのルーティングを避け、逆にトラフィック量が少ないリンクへのルーティングを促すことによって輻輳を避け、遅延の少ないルーティングを行うことが可能になる。
【０１００】
また、トラフィック量を推定するのに必要となるデータは、各ルータのトラフィック処理量と寄与行列とである。トラフィック処理量と寄与行列とは、各ルータから所定量ずつパケットを受け取ることによって取得することができる。探索用パケットの寿命を１つずつ増やして送出し、経路の往復時間を求める技術に比べれば、トラフィック量の推定に必要となるデータを得るためにネットワーク内に流すパケットの量を低減させることができる。
【０１０１】
さらに、トラフィック処理量と寄与行列とが揃えば、推定作業に移ることができるために、トラフィック量を推定するまでに要する時間も低減することができる。
【０１０２】
各ルータの同一期間内におけるトラフィック処理量を用いているので、推定したノードペアのトラフィック量には矛盾のない値で推定することができる。
【０１０３】
ルーティングプロトコルによってルーティングテーブルを取得することができ、ルーティングテーブルと各ルータによるルーティングルール（例えば、同一メトリックの経路には等分配するなど）から寄与行列を一意に定めることができる。よって、ルーティングテーブルが完成した時点で、ネットワーク構造の変化にも対応することが可能となる。
【０１０４】
［変形例］
上記では、添付図面を参照しながら本発明の好適な実施形態について説明したが、本発明は係る例に限定されないことは言うまでもない。当業者であれば、特許請求の範囲に記載された範疇内において、各種の変更例または修正例に想到し得ることは明らかであり、それらについても当然に本発明の技術的範囲に属するものと了解される。
【０１０５】
例えば、本実施形態に係る情報処理装置は、各ノードによって構成されるあらゆるネットワークに接続して利用することが可能である。例えば、Ｐ２Ｐの仮想ネットワークの構造や無線アドホックネットワークに接続してトラフィック量を推定することができる。また、本実施形態に係る情報処理装置は、推定値から各リンクの輻輳具合を知ることができるので、リンクの伝送時間を推定することも可能である。
【符号の説明】
【０１０６】
１００ 情報処理装置
１１０ 記憶部
１２０ 制御部
１２１ 経路情報取得制御部
１２２ リンク情報取得部
１２３ 寄与行列計算部
１２４ 推定部
１２５ 処理量計算部
１３０ 通信部
１３１ 経路情報送信要求送信部
１３２ 経路情報受信部
１３３ トラフィックデータ送信要求送信部
１３４ トラフィックデータ受信部
２００ ネットワーク
【特許請求の範囲】
【請求項１】
複数のノード間がリンクによって相互に接続されることによって構成されるネットワークに接続され、前記複数のノードから任意に２つのノードを選択して得られる各ノードペア間のリンクを流れるパケット量であるトラフィック量を推定する情報処理装置であって、
前記リンクによる前記各ノード間の接続関係を示すリンク情報を取得するリンク情報取得部と、
同一期間内に各ノードを流れたパケット量を当該ノードに対応する各トラフィック処理量として計算する処理量計算部と、
前記リンク情報と前記各トラフィック処理量とに基づいて、各ノードペア間を流れるパケット量に対する当該パケットのうちでノードを流れるパケット量の割合を各要素に有する行列を、当該ノードに対応する各寄与行列として計算する寄与行列計算部と、
前記各ノードに対応する前記各寄与行列に基づいて、前記各ノードに対応する前記各トラフィック処理量を前記各ノードペアに割り振ることによって前記トラフィック量を推定する推定部と、
を備えることを特徴とする、情報処理装置。
【請求項２】
前記推定部は、
前記各ノードペアに割り振る前記各トラフィック処理量として前記寄与行列の各要素値に比例する値を使用する、
ことを特徴とする、請求項１に記載の情報処理装置。
【請求項３】
前記推定部は、
前記寄与行列の要素値の総和が大きいノードから順に、当該ノードに対応する前記トラフィック処理量を前記各ノードペアに割り振る、
ことを特徴とする、請求項２に記載の情報処理装置。
【請求項４】
前記推定部は、
前記寄与行列の非零の要素数が大きいノードから順に、当該ノードに対応する前記トラフィック処理量を前記各ノードペアに割り振る、
ことを特徴とする、請求項２に記載の情報処理装置。
【請求項５】
前記推定部は、
推定した前記トラフィック量から前記各ノードを流れたパケット量であるトラフィック処理量を計算し、計算した前記トラフィック処理量と前記処理量計算部によって計算された前記トラフィック処理量との大小関係を判断し、計算した前記トラフィック処理量のほうが大きいと判断した場合には、当該ノードを含むノードペアに対して割り振る前記トラフィック処理量を減少させ、計算した前記トラフィック処理量のほうが小さいと判断した場合には、当該ノードを含むノードペアに対して割り振る前記トラフィック処理量を増加させることによって、再度前記トラフィック量の割り振りを行う、
ことを特徴とする、請求項２に記載の情報処理装置。
【請求項６】
複数のノード間がリンクによって相互に接続されることによって構成されるネットワークに接続され、前記複数のノードから任意に２つのノードを選択して得られる各ノードペア間のリンクを流れるパケット量であるトラフィック量を推定する情報処理装置による情報処理方法であって、
前記リンクによる前記各ノード間の接続関係を示すリンク情報を取得するステップと、
同一期間内に各ノードを流れたパケット量を当該ノードに対応する各トラフィック処理量として計算するステップと、
前記リンク情報と前記各トラフィック処理量とに基づいて、各ノードペア間を流れるパケット量に対する当該パケットのうちでノードを流れるパケット量の割合を各要素に有する行列を、当該ノードに対応する各寄与行列として計算するステップと、
前記各ノードに対応する前記各寄与行列に基づいて、前記各ノードに対応する前記各トラフィック処理量を前記各ノードペアに割り振ることによって前記トラフィック量を推定するステップと、
を含むことを特徴とする、情報処理方法。
【請求項１】
複数のノード間がリンクによって相互に接続されることによって構成されるネットワークに接続され、前記複数のノードから任意に２つのノードを選択して得られる各ノードペア間のリンクを流れるパケット量であるトラフィック量を推定する情報処理装置であって、
前記リンクによる前記各ノード間の接続関係を示すリンク情報を取得するリンク情報取得部と、
同一期間内に各ノードを流れたパケット量を当該ノードに対応する各トラフィック処理量として計算する処理量計算部と、
前記リンク情報と前記各トラフィック処理量とに基づいて、各ノードペア間を流れるパケット量に対する当該パケットのうちでノードを流れるパケット量の割合を各要素に有する行列を、当該ノードに対応する各寄与行列として計算する寄与行列計算部と、
前記各ノードに対応する前記各寄与行列に基づいて、前記各ノードに対応する前記各トラフィック処理量を前記各ノードペアに割り振ることによって前記トラフィック量を推定する推定部と、
を備えることを特徴とする、情報処理装置。
【請求項２】
前記推定部は、
前記各ノードペアに割り振る前記各トラフィック処理量として前記寄与行列の各要素値に比例する値を使用する、
ことを特徴とする、請求項１に記載の情報処理装置。
【請求項３】
前記推定部は、
前記寄与行列の要素値の総和が大きいノードから順に、当該ノードに対応する前記トラフィック処理量を前記各ノードペアに割り振る、
ことを特徴とする、請求項２に記載の情報処理装置。
【請求項４】
前記推定部は、
前記寄与行列の非零の要素数が大きいノードから順に、当該ノードに対応する前記トラフィック処理量を前記各ノードペアに割り振る、
ことを特徴とする、請求項２に記載の情報処理装置。
【請求項５】
前記推定部は、
推定した前記トラフィック量から前記各ノードを流れたパケット量であるトラフィック処理量を計算し、計算した前記トラフィック処理量と前記処理量計算部によって計算された前記トラフィック処理量との大小関係を判断し、計算した前記トラフィック処理量のほうが大きいと判断した場合には、当該ノードを含むノードペアに対して割り振る前記トラフィック処理量を減少させ、計算した前記トラフィック処理量のほうが小さいと判断した場合には、当該ノードを含むノードペアに対して割り振る前記トラフィック処理量を増加させることによって、再度前記トラフィック量の割り振りを行う、
ことを特徴とする、請求項２に記載の情報処理装置。
【請求項６】
複数のノード間がリンクによって相互に接続されることによって構成されるネットワークに接続され、前記複数のノードから任意に２つのノードを選択して得られる各ノードペア間のリンクを流れるパケット量であるトラフィック量を推定する情報処理装置による情報処理方法であって、
前記リンクによる前記各ノード間の接続関係を示すリンク情報を取得するステップと、
同一期間内に各ノードを流れたパケット量を当該ノードに対応する各トラフィック処理量として計算するステップと、
前記リンク情報と前記各トラフィック処理量とに基づいて、各ノードペア間を流れるパケット量に対する当該パケットのうちでノードを流れるパケット量の割合を各要素に有する行列を、当該ノードに対応する各寄与行列として計算するステップと、
前記各ノードに対応する前記各寄与行列に基づいて、前記各ノードに対応する前記各トラフィック処理量を前記各ノードペアに割り振ることによって前記トラフィック量を推定するステップと、
を含むことを特徴とする、情報処理方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公開番号】特開２０１１−４５０３７（Ｐ２０１１−４５０３７Ａ）
【公開日】平成２３年３月３日（２０１１．３．３）
【国際特許分類】
【出願番号】特願２００９−１９３６２６（Ｐ２００９−１９３６２６）
【出願日】平成２１年８月２４日（２００９．８．２４）
【国等の委託研究の成果に係る記載事項】（出願人による申告）国等の委託研究の成果に係る特許出願（平成１９年度独立行政法人情報通信研究機構「ダイナミックネットワーク技術の研究開発」委託研究、産業技術力強化法第１９条の適用を受けるもの）
【出願人】（００００００２９５）沖電気工業株式会社 (6,645)
【Ｆターム（参考）】
【公開日】平成２３年３月３日（２０１１．３．３）
【国際特許分類】
【出願日】平成２１年８月２４日（２００９．８．２４）
【国等の委託研究の成果に係る記載事項】（出願人による申告）国等の委託研究の成果に係る特許出願（平成１９年度独立行政法人情報通信研究機構「ダイナミックネットワーク技術の研究開発」委託研究、産業技術力強化法第１９条の適用を受けるもの）
【出願人】（００００００２９５）沖電気工業株式会社 (6,645)
【Ｆターム（参考）】
[ Back to top ]