(57)【要約】【課題】ネットワーク使用率を向上させること。【解決手段】記憶部には、使用帯域幅情報及び割当帯域幅情報が格納される。最大帯域幅予測部は、割当帯域幅の制約が無い場合の使用帯域幅の最大値である予測最大帯域幅をフロー毎に予測する。具体的には、最大帯域幅予測部は、少なくとも使用帯域幅情報を参照して、使用帯域幅と閾値との比較結果に基づいて予測最大帯域幅を算出する。割当帯域幅決定部は、フロー毎の割当帯域幅を動的に決定して割当帯域幅情報を更新する。具体的には、割当帯域幅決定部は、予測最大帯域幅に応じて割当帯域幅を決定する。【選択図】図４
2011049891.tif 000002
【特許請求の範囲】
【請求項１】
記憶部と、
最大帯域幅予測部と、
割当帯域幅決定部と
を備え、
前記記憶部には、
フロー毎の使用帯域幅を示す使用帯域幅情報と、
フロー毎の割当帯域幅を示す割当帯域幅情報と
が格納され、
前記最大帯域幅予測部は、前記割当帯域幅の制約が無い場合の前記使用帯域幅の最大値である予測最大帯域幅をフロー毎に予測する予測処理を実施し、
前記予測処理において、前記最大帯域幅予測部は、少なくとも前記使用帯域幅情報を参照して、前記使用帯域幅と閾値との比較結果に基づいて前記予測最大帯域幅を算出し、
前記割当帯域幅決定部は、フロー毎の前記割当帯域幅を動的に決定して前記割当帯域幅情報を更新する割当処理を実施し、
前記割当処理において、前記割当帯域幅決定部は、前記予測最大帯域幅に応じて前記割当帯域幅を決定する
帯域幅割当装置。
【請求項２】
請求項１に記載の帯域幅割当装置であって、
前記予測処理において、前記最大帯域幅予測部は、前記使用帯域幅情報及び前記割当帯域幅情報を参照して、前記割当帯域幅の使用状況に応じて前記予測最大帯域幅を算出する
帯域幅割当装置。
【請求項３】
請求項２に記載の帯域幅割当装置であって、
前記予測処理において、前記最大帯域幅予測部は、前記使用状況に応じて調整量を決定し、前記使用帯域幅に前記調整量を加えることによって前記予測最大帯域幅を算出する
帯域幅割当装置。
【請求項４】
請求項３に記載の帯域幅割当装置であって、
前記予測処理において、前記閾値は前記割当帯域幅より小さい値であり、
前記使用帯域幅が前記閾値以上の場合、前記最大帯域幅予測部は、前記調整量を第１調整量に設定し、
前記使用帯域幅が前記閾値未満の場合、前記最大帯域幅予測部は、前記調整量を前記第１調整量よりも小さい第２調整量に設定する
帯域幅割当装置。
【請求項５】
請求項４に記載の帯域幅割当装置であって、
前記閾値は、前記割当帯域幅から前記使用帯域幅の測定誤差を差し引いた値である
帯域幅割当装置。
【請求項６】
請求項３に記載の帯域幅割当装置であって、
前記予測処理において、前記閾値は前記割当帯域幅であり、
前記使用帯域幅が前記閾値と同じ場合、前記最大帯域幅予測部は、前記調整量を第１調整量に設定し、
前記使用帯域幅が前記閾値より少ない場合、前記最大帯域幅予測部は、前記調整量を前記第１調整量よりも小さい第２調整量に設定する
帯域幅割当装置。
【請求項７】
請求項３に記載の帯域幅割当装置であって、
前記予測処理において、前記閾値は１時刻前の前記使用帯域幅であり、
前記使用帯域幅が前記閾値より大きい場合、前記最大帯域幅予測部は、前記調整量を第１調整量に設定し、
前記使用帯域幅が前記閾値以下の場合、前記最大帯域幅予測部は、前記調整量を前記第１調整量よりも小さい第２調整量に設定する
帯域幅割当装置。
【請求項８】
請求項４乃至７のいずれか一項に記載の帯域幅割当装置であって、
前記第１調整量は、前回の前記予測処理で決定された前記調整量より大きく、
前記第２調整量は、前回の前記予測処理で決定された前記調整量より小さい
帯域幅割当装置。
【請求項９】
請求項４乃至７のいずれか一項に記載の帯域幅割当装置であって、
前記第１調整量は、前回の前記予測処理で決定された前記調整量より大きく、
前記第２調整量は、ゼロである
帯域幅割当装置。
【請求項１０】
請求項１乃至９のいずれか一項に記載の帯域幅割当装置であって、
前記記憶部には、更に、
フロー毎の経路を示す経路情報と、
リンク毎のリンク容量を示すリンク容量情報と
が格納され、
前記割当処理において、前記割当帯域幅決定部は、前記経路情報、前記リンク容量情報、及び前記予測最大帯域幅を参照して、前記リンク容量を超えない範囲内で前記予測最大帯域幅を前記割当帯域幅として決定する
帯域幅割当装置。
【請求項１１】
請求項１０に記載の帯域幅割当装置であって、
少なくとも１つのリンクにおいて帯域幅が飽和する前記割当帯域幅は、飽和帯域幅であり、
前記割当処理において、前記割当帯域幅決定部は、前記経路情報及び前記リンク容量情報を参照して、スケジューリングポリシに従ってフロー毎の前記飽和帯域幅を算出し、
あるフローに関して前記飽和帯域幅よりも前記予測最大帯域幅の方が少ない場合、前記割当帯域幅決定部は、当該フローの前記割当帯域幅を前記予測最大帯域幅に決定する
帯域幅割当装置。
【請求項１２】
請求項１１に記載の帯域幅割当装置であって、
あるリンクの前記リンク容量から、当該リンクを通過する全フローの仮割当帯域幅の合計を差し引いた量は、残余帯域幅であり、
ループ処理において、前記割当帯域幅決定部は、前記残余帯域幅をフロー間で分配することによって前記飽和帯域幅を算出し、更に、前記飽和帯域幅と前記予測最大帯域幅のうちより少ない方を新たな前記仮割当帯域幅として選択し、
前記割当帯域幅決定部は、前記仮割当帯域幅を初期設定した後、所定の条件が満たされるまで前記ループ処理を繰り返し、前記所定の条件が満たされたときの前記仮割当帯域幅を前記割当帯域幅として決定する
帯域幅割当装置。
【請求項１３】
請求項１２に記載の帯域幅割当装置であって、
前記所定の条件は、全フローに前記予測最大帯域幅が割り当てられた場合、あるいは、前記残余帯域幅が無くなった場合である
帯域幅割当装置。
【請求項１４】
請求項１乃至１３のいずれか一項に記載の帯域幅割当装置であって、
計測装置から送られた計測情報に基づいて各フローの前記使用帯域幅を取得し、前記使用帯域幅情報を作成する使用帯域幅取得部と、
前記計測装置において前記割当帯域幅に応じたフロー制御を実現するための制御情報を前記計測装置に送信する制御情報通知部と
を更に備える
帯域幅割当装置。
【請求項１５】
フロー毎の使用帯域幅を示す使用帯域幅情報と、フロー毎の割当帯域幅を示す割当帯域幅情報と、を記憶装置に格納するステップと、
前記割当帯幅の制約が無い場合の前記使用帯域幅の最大値である予測最大帯域幅をフロー毎に予測する予測処理を実施するステップと、
フロー毎の前記割当帯域幅を動的に決定して前記割当帯域幅情報を更新する割当処理を実施するステップと
を含み、
前記予測処理は、少なくとも前記使用帯域幅情報を参照して、前記使用帯域幅と閾値との比較結果に基づいて前記予測最大帯域幅を算出するステップを含み、
前記割当処理は、前記予測最大帯域幅に応じて前記割当帯域幅を決定するステップを含む
帯域幅割当方法。
【請求項１６】
ネットワーク中のフローに帯域幅を割り当てる動的割当処理をコンピュータに実行させるための帯域幅割当プログラムであって、
前記動的割当処理は、
フロー毎の使用帯域幅を示す使用帯域幅情報と、フロー毎の割当帯域幅を示す割当帯域幅情報と、を記憶装置に格納するステップと、
前記割当帯域幅の制約が無い場合の前記使用帯域幅の最大値である予測最大帯域幅をフロー毎に予測する予測処理を実施するステップと、
フロー毎の前記割当帯域幅を動的に決定して前記割当帯域幅情報を更新する割当処理を実施するステップと
を含み、
前記予測処理は、少なくとも前記使用帯域幅情報を参照して、前記使用帯域幅と閾値との比較結果に基づいて前記予測最大帯域幅を算出するステップを含み、
前記割当処理は、前記予測最大帯域幅に応じて前記割当帯域幅を決定するステップを含む
帯域幅割当プログラム。
【請求項１７】
ネットワーク中の複数の計測装置と、
前記複数の計測装置と通信可能に接続された帯域幅割当装置と
を具備し、
前記複数の計測装置の各々は、自身を通過するフローの状態を計測し、前記計測された状態を示す計測情報を前記帯域幅割当装置に送信し、
前記帯域幅割当装置は、
記憶部と、
使用帯域幅取得部と、
最大帯域幅予測部と、
割当帯域幅決定部と、
制御情報通知部と
を備え、
前記記憶部には、
フロー毎の使用帯域幅を示す使用帯域幅情報と、
フロー毎の割当帯域幅を示す割当帯域幅情報と
が格納され、
前記使用帯域幅取得部は、前記各計測装置から送られた前記計測情報に基づいて各フローの前記使用帯域幅を取得して、前記使用帯域幅情報を作成し、
前記最大帯域幅予測部は、前記割当帯域幅の制約が無い場合の前記使用帯域幅の最大値である予測最大帯域幅をフロー毎に予測する予測処理を実施し、
前記予測処理において、前記最大帯域幅予測部は、少なくとも前記使用帯域幅情報を参照して、前記使用帯域幅と閾値との比較結果に基づいて前記予測最大帯域幅を算出し、
前記割当帯域幅決定部は、フロー毎の前記割当帯域幅を動的に決定して前記割当帯域幅情報を更新する割当処理を実施し、
前記割当処理において、前記割当帯域幅決定部は、前記予測最大帯域幅に応じて前記割当帯域幅を決定し、
前記制御情報通知部は、前記各計測装置において前記割当帯域幅情報で示される前記割当帯域幅を実現するための制御情報を前記各計測装置に送信する
ネットワークシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信ネットワーク中のフローに対して帯域幅を割り当てる技術に関する。
【背景技術】
【０００２】
通信のサービス品質を保証するための技術として、「プロビジョニング」が知られている。まず、ユーザは、通信を開始する前に、自身が使用したい帯域幅を通信事業者に要求する。その要求を受けた通信事業者は、ネットワークの使用状況を鑑み、ユーザに割り当てる帯域幅を計算する。そして、通信事業者は、ユーザの使用帯域幅が割り当てた帯域幅となるように、ネットワーク内の機器を制御する。ユーザは、その割り当てられた帯域幅内で通信を行うことができる。このようなプロビジョニング技術は、非特許文献１や非特許文献２に記載されている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Ａ．  Ｋｏｎａｍｉ  ｅｔ  ａｌ．，  “Ａ  ｐｒｏｖｉｓｉｏｎｉｎｇ  ａｌｇｏｒｉｔｈｍ  ｆｏｒ  ＶＰＮ  ｈｏｓｅ  ｂａｎｄｗｉｄｔｈ  ａｌｌｏｃａｔｉｏｎ  ｍｅｔｈｏｄ”，  ２００６年電子情報通信学会  技術研究報告ネットワークシステム研究会，  ２００６．
【非特許文献２】Ｎ．  Ｇ．  Ｄｕｆｆｉｅｌｄ  ｅｔ  ａｌ．，  “Ｒｅｓｏｕｒｃｅ  Ｍａｎａｇｅｍｅｎｔ  Ｗｉｔｈ  Ｈｏｓｅｓ：  Ｐｏｉｎｔ−ｔｏ−Ｃｌｏｕｄ  Ｓｅｒｖｉｃｅｓ  ｆｏｒ  Ｖｉｒｔｕａｌ  Ｐｒｉｖａｔｅ  Ｎｅｔｗｏｒｋｓ”，  ＩＥＥＥ／ＡＣＭ  Ｔｒａｎｓ．  Ｎｅｔｗｏｒｋｉｎｇ，  １０（５），  ｐｐ．  ６７９−６９２，  ２００２．
【発明の概要】
【発明が解決しようとする課題】
【０００４】
上述のプロビジョニング技術によれば、通信開始前に、要求に応じた帯域幅が予め割り当てられる。しかしながら、フローが実際に使用する使用帯域幅は、必ずしも一定とは限らない。すなわち、フローの使用帯域幅は、時間に依存して変動する可能性がある。例えば、ＴＣＰ（Ｔｒａｎｓｍｉｓｓｉｏｎ  Ｃｏｎｔｒｏｌ  Ｐｒｏｔｏｃｏｌ）、ＸＣＰ（ｅＸｐｌｉｃｉｔ  Ｃｏｎｔｒｏｌ  Ｐｒｏｔｏｃｏｌ）、ＤＣＣＰ（Ｄａｔａｇｒａｍ  Ｃｏｎｇｅｓｔｉｏｎ  Ｃｏｎｔｒｏｌ  Ｐｒｏｔｏｃｏｌ）などのプロトコルの場合、フローの使用帯域幅は時間に依存して変動する。このような場合に、帯域幅が予め固定的に割り当てられると、次のような問題が発生する。
【０００５】
例として、同じリンクを通過する２つのフロー（第１フローと第２フロー）に関して、次のような帯域幅割当を考える。当該リンクのリンク容量が１５Ｍｂｐｓであるのに対し、第１フローと第２フローが共に１０Ｍｂｐｓの帯域幅を要求する。プロビジョニング技術により、第１フローと第２フローのそれぞれに対し、５Ｍｂｐｓ、１０Ｍｂｐｓの帯域幅が割り当てられる。第１フローの使用帯域幅は割当帯域幅（＝５Ｍｂｐｓ）以下に制限され、第２フローの使用帯域幅は割当帯域幅（＝１０Ｍｂｐｓ）以下に制限される。
【０００６】
ここで、ある時刻において、第１フローの使用帯域幅が５Ｍｂｐｓになり、第２フローの使用帯域幅が７Ｍｂｐｓになったとする。この場合、第２フローに関して未使用の帯域幅（＝割当帯域幅−使用帯域幅＝１０Ｍｂｐｓ−７Ｍｂｐｓ）が発生し、リンクに残余帯域幅（＝リンク容量−使用帯域幅の総和＝１５Ｍｂｐｓ−５Ｍｂｐｓ−７Ｍｂｐｓ）が発生する。一方、第１フローに関しては、上限（割当帯域幅＝５Ｍｂｐｓ）いっぱいまで帯域幅が使用されている。本来、第１フローは１０Ｍｂｐｓの帯域幅を要求していたため、第１フローが上述の残余帯域幅を使用できれば好適である。しかしながら、それはできない。何故なら、割当帯域幅は固定されており、第１フローの使用帯域幅はその割当帯域幅以下に制限されるからである。このように、残余帯域幅があるにもかかわらず、その残余帯域幅を有効に活用できないという事態が発生する。このことは、ネットワーク使用率の低下を意味する。
【０００７】
本発明の１つの目的は、ネットワーク使用率を向上させることができる技術を提供することにある。
【課題を解決するための手段】
【０００８】
本発明の１つの観点において、帯域幅割当装置が提供される。その帯域幅割当装置は、記憶部と、最大帯域幅予測部と、割当帯域幅決定部と、を備える。記憶部には、フロー毎の使用帯域幅を示す使用帯域幅情報と、フロー毎の割当帯域幅を示す割当帯域幅情報と、が格納される。最大帯域幅予測部は、割当帯域幅の制約が無い場合の使用帯域幅の最大値である予測最大帯域幅をフロー毎に予測する予測処理を実施する。その予測処理において、最大帯域幅予測部は、少なくとも使用帯域幅情報を参照して、使用帯域幅と閾値との比較結果に基づいて予測最大帯域幅を算出する。割当帯域幅決定部は、フロー毎の割当帯域幅を動的に決定して割当帯域幅情報を更新する割当処理を実施する。その割当処理において、割当帯域幅決定部は、予測最大帯域幅に応じて割当帯域幅を決定する。
【０００９】
本発明の他の観点において、帯域幅割当方法が提供される。その帯域幅割当方法は、（Ａ）フロー毎の使用帯域幅を示す使用帯域幅情報と、フロー毎の割当帯域幅を示す割当帯域幅情報と、を記憶装置から読み出すステップと、（Ｂ）割当帯域幅の制約が無い場合の使用帯域幅の最大値である予測最大帯域幅をフロー毎に予測する予測処理を実施するステップと、（Ｃ）フロー毎の割当帯域幅を動的に決定して割当帯域幅情報を更新する割当処理を実施するステップと、を含む。上記予測処理は、少なくとも使用帯域幅情報を参照して、使用帯域幅と閾値との比較結果に基づいて予測最大帯域幅を算出するステップを含む。上記割当処理は、予測最大帯域幅に応じて割当帯域幅を決定するステップを含む。
【００１０】
本発明の更に他の観点において、ネットワーク中のフローに帯域幅を割り当てる「動的割当処理」をコンピュータに実行させるための帯域幅割当プログラムが提供される。その動的割当処理は、（Ａ）フロー毎の使用帯域幅を示す使用帯域幅情報と、フロー毎の割当帯域幅を示す割当帯域幅情報と、を記憶装置から読み出すステップと、（Ｂ）割当帯域幅の制約が無い場合の使用帯域幅の最大値である予測最大帯域幅をフロー毎に予測する予測処理を実施するステップと、（Ｃ）フロー毎の割当帯域幅を動的に決定して割当帯域幅情報を更新する割当処理を実施するステップと、を含む。上記予測処理は、少なくとも使用帯域幅情報を参照して、使用帯域幅と閾値との比較結果に基づいて予測最大帯域幅を算出するステップを含む。上記割当処理は、予測最大帯域幅に応じて割当帯域幅を決定するステップを含む。
【００１１】
本発明の更に他の観点において、ネットワークシステムが提供される。そのネットワークシステムは、ネットワーク中の複数の計測装置と、複数の計測装置と通信可能に接続された帯域幅割当装置と、を備える。複数の計測装置の各々は、自身を通過するフローの状態を計測し、計測された状態を示す計測情報を帯域幅割当装置に送信する。
【００１２】
帯域幅割当装置は、記憶部と、使用帯域幅取得部と、最大帯域幅予測部と、割当帯域幅決定部と、制御情報通知部と、を備える。記憶部には、フロー毎の使用帯域幅を示す使用帯域幅情報と、フロー毎の割当帯域幅を示す割当帯域幅情報と、が格納される。使用帯域幅取得部は、各計測装置から送られた計測情報に基づいて使用帯域幅を取得して、使用帯域幅情報を作成する。最大帯域幅予測部は、割当帯域幅の制約が無い場合の使用帯域幅の最大値である予測最大帯域幅をフロー毎に予測する予測処理を実施する。その予測処理において、最大帯域幅予測部は、少なくとも使用帯域幅情報を参照して、使用帯域幅と閾値との比較結果に基づいて予測最大帯域幅を算出する。割当帯域幅決定部は、フロー毎の割当帯域幅を動的に決定して割当帯域幅情報を更新する割当処理を実施する。その割当処理において、割当帯域幅決定部は、予測最大帯域幅に応じて割当帯域幅を決定する。制御情報通知部は、各計測装置において割当帯域幅情報で示される割当帯域幅を実現するための制御情報を各計測装置に送信する。
【発明の効果】
【００１３】
本発明によれば、ネットワーク使用率が向上する。
【図面の簡単な説明】
【００１４】
【図１】図１は、本発明の実施の形態に係るネットワークシステムを概略的に示している。
【図２】図２は、本発明の実施の形態に係るネットワークシステムにおける処理を示すフローチャートである。
【図３】図３は、本発明の実施の形態に係る計測装置の構成を示すブロック図である。
【図４】図４は、本発明の実施の形態に係る帯域幅割当装置の構成を示すブロック図である。
【図５】図５は、本発明の実施の形態における経路情報を概念的に示している。
【図６】図６は、本発明の実施の形態におけるリンク容量情報を概念的に示している。
【図７】図７は、本発明の実施の形態における割当帯域幅情報を概念的に示している。
【図８】図８は、本発明の実施の形態に係る動的割当処理を示すフローチャートである。
【図９】図９は、本発明の実施の形態に係る動的割当処理を示す概念図である。
【図１０】図１０は、本発明の実施の形態における使用帯域幅情報の一例を概念的に示している。
【図１１】図１１は、本発明の実施の形態における使用帯域幅情報の他の例を概念的に示している。
【図１２】図１２は、ステップＳ２３０における処理を示すフローチャートである。
【図１３】図１３は、ステップＳ２３０における処理を説明するための概念図である。
【図１４】図１４は、ステップＳ２３０における処理を説明するための概念図である。
【図１５】図１５は、ステップＳ２４０における処理を示すフローチャートである。
【図１６】図１６は、ステップＳ２４０における処理の一例を説明するための概念図である。
【図１７】図１７は、あるフローに関する割当帯域幅及び使用帯域幅の遷移の一例を示している。
【図１８】図１８は、第１の変形例に係るステップＳ２３０を示すフローチャートである。
【図１９】図１９は、第２の変形例に係るステップＳ２３０を示すフローチャートである。
【図２０】図２０は、第３の変形例に係るステップＳ２３０を示すフローチャートである。
【図２１】図２１は、アウターフローとインナーフローを説明するための概念図である。
【発明を実施するための形態】
【００１５】
添付図面を参照して、本発明の実施の形態を説明する。
【００１６】
図１は、本実施の形態に係るネットワークシステム１を概略的に示している。ネットワークシステム１は、ネットワークＮＥＴとそのネットワークＮＥＴ中に配置された複数の計測装置１００を備えている。ネットワークＮＥＴ中には複数のフローが流れる。計測装置１００は、フローの計測を行う機能を有している。例えば、計測装置１００は、フローの計測を行う機能を有するルータである。
【００１７】
各フローは、送信ＩＰアドレス、受信ＩＰアドレス、送信ポート番号、受信ポート番号、送信ＭＡＣアドレス、受信ＭＡＣアドレス、プロトコルＩＤ（プロトコルの識別情報）といったパラメータで規定される。２つのフローが同一か否かは、それら複数のパラメータのうち１以上のパラメータが同一であるか否かによって判定される。つまり、複数のパラメータのうち１以上のパラメータが、フロー識別子として用いられる。以下の説明では、例として、「送信側のＩＰアドレスと受信側のＩＰアドレスの組」がフロー識別子として用いられる。つまり、送信側の装置（送信端末あるいは計測装置１００）のＩＰアドレスと受信側の装置（受信端末あるいは計測装置１００）のＩＰアドレスを用いて、フローの識別が行われる。
【００１８】
ネットワークシステム１は更に、帯域幅割当装置２００を備えている。帯域幅割当装置２００は、例えばサーバであり、複数の計測装置１００と通信可能に接続されている。この帯域幅割当装置２００は、各フローに帯域幅を動的に割り当てる機能を有している。
【００１９】
あるフローｐに割り当てられる帯域幅は、以下、「割当帯域幅Ａｐ」と参照される。当該フローｐは、実際には、ある帯域幅を使用する。フローｐにより実際に使用される帯域幅は、以下、「使用帯域幅Ｘｐ」と参照される。使用帯域幅Ｘｐは、時間に依存して変動する。また、使用帯域幅Ｘｐは、割当帯域幅Ａｐ以下に制限される。あるフローに関する割当帯域幅Ａｐと使用帯域幅Ｘｐとの差分（＝Ａｐ−Ｘｐ）は、以下、「未使用帯域幅」と参照される。また、あるリンクのリンク容量とそのリンクを通過するフローの使用帯域幅Ｘｐの総和との差分は、「残余帯域幅」と参照される。
【００２０】
フローｐの使用帯域幅Ｘｐは割当帯域幅Ａｐ以下に制限されるが、当該フローｐは、その割当帯域幅Ａｐよりも多くの帯域幅を使用したいかもしれない。その使いたい帯域幅は、以下、「最大帯域幅」と参照される。つまり、最大帯域幅とは、割当帯域幅Ａｐの制約が無い場合の使用帯域幅Ｘｐの最大値である。後に詳しく説明されるように、本実施の形態では、フロー毎に最大帯域幅の予測が行われる。フローｐに関して予測された最大帯域幅は、以下、「予測最大帯域幅Ｔｐ」と参照される。
【００２１】
図２は、本実施の形態に係るネットワークシステム１における処理を示すフローチャートである。図１及び図２を参照して、本実施の形態に係る処理の概要を説明する。
【００２２】
ステップＳ１００：
各計測装置１００は、自身を通過するフローの状態（流量等）を計測し、その計測結果を示す「計測情報ＭＳＲ」を作成する。計測情報ＭＳＲは、計測されたフローの使用帯域幅Ｘｐに関連する情報であり、計測パケット数やサンプリング率等を含んでいる。計測情報ＭＳＲは、使用帯域幅Ｘｐそのものを示していてもよい。各計測装置１００は、作成した計測情報ＭＳＲを周期的に帯域幅割当装置２００に送信する。
【００２３】
ステップＳ２００：
帯域幅割当装置２００は、各フローの割当帯域幅Ａｐを動的に変更する。より詳細には、帯域幅割当装置２００は、各計測装置１００から計測情報ＭＳＲを受け取り、受け取った計測情報ＭＳＲから各フローの使用帯域幅Ｘｐを取得する。更に、帯域幅割当装置２００は、使用帯域幅Ｘｐに基づいて、各フローの予測最大帯域幅Ｔｐを算出する。例えば、帯域幅割当装置２００は、使用帯域幅Ｘｐと現在の割当帯域幅Ａｐとを比較することによって、各フローの割当帯域幅Ａｐの使用状況を調べることができる。そして、帯域幅割当装置２００は、割当帯域幅Ａｐの使用状況に応じて最大帯域幅を予測し、各フローの予測最大帯域幅Ｔｐを算出する。
【００２４】
例えば、使用帯域幅Ｘｐがほぼ割当帯域幅Ａｐと等しい場合、そのフローは割当帯域幅Ａｐを使い切っていると考えられる。この場合、当該フローの最大帯域幅は、現在の使用帯域幅Ｘｐよりももっと多いと予測される。一方、使用帯域幅Ｘｐが割当帯域幅Ａｐよりもはるかに少ない場合、そのフローは割当帯域幅Ａｐを使い切らないと考えられる。この場合、当該フローの最大帯域幅は、現在の使用帯域幅Ｘｐの近傍と予測される。このように、帯域幅割当装置２００は、割当帯域幅Ａｐの使用状況に応じて、フロー毎に予測最大帯域幅Ｔｐを算出する。
【００２５】
続いて、帯域幅割当装置２００は、予測最大帯域幅Ｔｐに応じて新たな割当帯域幅Ａｐを決定する。例えば、帯域幅割当装置２００は、基本的に上述の予測最大帯域幅Ｔｐを該当フローに新たに割り当てる、すなわち、割当帯域幅Ａｐを予測最大帯域幅Ｔｐに更新する。但し、全てのフローにそれぞれ予測最大帯域幅Ｔｐを割り当てると、あるリンクを通過するフローの割当帯域幅Ａｐの総和が当該リンクのリンク容量を超えてしまう可能性がある。そのため、帯域幅割当装置２００は、各フローの経路及びその経路上の各リンクのリンク容量を考慮にいれて、それぞれのフローの割当帯域幅Ａｐを決定する。具体的には、帯域幅割当装置２００は、リンク容量を超えない範囲でなるべく多くのフローに予測最大帯域幅Ｔｐを割り当てる。このようにして、帯域幅割当装置２００は、各フローの割当帯域幅Ａｐを決定（更新）する。
【００２６】
その後、帯域幅割当装置２００は、各計測装置１００において新たな割当帯域幅Ａｐに応じたフロー制御を実現するための「制御情報ＣＯＮ」を作成する。例えば、パケットを廃棄することでフロー制御が行われる場合には、制御情報ＣＯＮは廃棄確率を示す。あるいは、パケットの送信順序をスケジューリングすることでフロー制御が行われる場合には、制御情報ＣＯＮは制御パラメータ（重み値等）を示す。あるいは、制御情報ＣＯＮは、フロー毎の割当帯域幅Ａｐそのものを示していてもよい。更に、制御情報ＣＯＮは、制御対象のフローの識別子も含んでいる。帯域幅割当装置２００は、そのような制御情報ＣＯＮを各計測装置１００に送信する。
【００２７】
ステップＳ３００：
各計測装置１００は、帯域幅割当装置２００から制御情報ＣＯＮを受け取る。各計測装置１００は、受け取った制御情報ＣＯＮに従って、フロー制御を行う。
【００２８】
以上に説明されたように、本実施の形態によれば、各フローに割り当てられる割当帯域幅Ａｐが動的に制御される。その結果、フローの未使用帯域幅やリンクの残余帯域幅の発生が抑制される。また、残余帯域幅があるにもかかわらずその残余帯域幅を有効に活用できないといった事態が防止される。従って、ネットワーク使用率が向上する。
【００２９】
以下、各装置の構成例及び動作例を詳しく説明する。
【００３０】
１．計測装置１００
図３は、本実施の形態に係る計測装置１００の構成を示すブロック図である。計測装置１００は、例えば、フローの計測を行う機能を有するルータである。詳細には、計測装置１００は、処理装置１０１と記憶装置１０２を備えている。処理装置１０１は、キャプチャ部１１０、計測部１２０及びフロー制御部１３０を有している。これらキャプチャ部１１０、計測部１２０及びフロー制御部１３０は、処理装置１０１がコンピュータプログラムを実行することにより実現される。記憶装置１０２には、計測情報ＭＳＲや制御情報ＣＯＮが格納される。
【００３１】
ステップＳ１００：
キャプチャ部１１０は、自装置を通過するパケットのヘッダをキャプチャし、ヘッダ情報を収集する。例えば、キャプチャ部１１０がＩＰヘッダをキャプチャする場合、そのＩＰヘッダには、パケットの全長、プロトコル、送信元ＩＰアドレス、宛先ＩＰアドレス、サービスタイプ等が記載されている。キャプチャ部１１０は、ＴＣＰヘッダあるいはＭＡＣヘッダをキャプチャしてもよい。更に、キャプチャ部１１０は、キャプチャしたヘッダの数も管理する。尚、キャプチャ部１１０は、通過する全てのパケットのヘッダをキャプチャする必要は無い。キャプチャ部１１０は、周期的にあるいはランダムにヘッダをキャプチャし、サンプリング率を算出してもよい。
【００３２】
計測部１２０は、キャプチャ部１１０で収集されたヘッダ情報に基づいて、フローの識別を行い、計測情報ＭＳＲを作成する。計測情報ＭＳＲは、所定の期間における各フローの総パケット数あるいは総バイト数を含む。それら総パケット数あるいは総バイト数は、キャプチャ部１１０が取得した各フローのヘッダ数を参照すれば算出することができる。キャプチャ部１１０にてサンプリング技術が用いられた場合、そのサンプリング率とヘッダ数から、総パケット数あるいは総バイト数が算出される。
【００３３】
計測情報ＭＳＲは、上述のヘッダ情報やサンプリング率を含んでいてもよい。その場合、その計測情報ＭＳＲを受け取る帯域幅割当装置２００において、フロー毎の総パケット数、総バイト数、使用帯域幅Ｘｐを算出することができる。
【００３４】
また、計測部１２０は、フロー毎の使用帯域幅Ｘｐを算出してもよい。その場合、計測情報ＭＳＲは、算出されたフロー毎の使用帯域幅Ｘｐをも含む。あるいは、使用帯域幅Ｘｐは、帯域幅割当装置２００において算出されてもよい。
【００３５】
各計測装置１００は、作成した計測情報ＭＳＲを周期的に帯域幅割当装置２００に送信する。計測情報ＭＳＲの送信には、ＩＰＦＩＸ（ＩＰ  Ｆｌｏｗ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｅｘｐｏｒｔ）、ＮｅｔＦｌｏｗ、ｓＦｌｏｗ等の技術を用いればよい。本実施の形態では、例えばＩＰＦＩＸが利用される。
【００３６】
ステップＳ３００：
フロー制御部１３０は、帯域幅割当装置２００から制御情報ＣＯＮを受け取る。制御情報ＣＯＮは、計測装置１００において割当帯域幅Ａｐに応じたフロー制御を実現するための情報である。フロー制御部１３０は、受け取った制御情報ＣＯＮに従って、フロー制御を行う。例えば、パケットを廃棄することでフロー制御が行われる場合には、制御情報ＣＯＮは廃棄確率を示す。あるいは、パケットの送信順序をスケジューリングすることでフロー制御が行われる場合には、制御情報ＣＯＮは制御パラメータ（重み値等）を示す。あるいは、制御情報ＣＯＮは、フロー毎の割当帯域幅Ａｐそのものを示していてもよい。その場合、フロー制御部１３０は、割当帯域幅Ａｐを、廃棄確率や制御パラメータに変換する。
【００３７】
尚、フロー計測機能（キャプチャ部１１０、計測部１２０）とフロー制御機能（フロー制御部１３０）は、一台の装置で実現されている必要はなく、それぞれ別の装置で実現されていてもよい。例えば、フロー計測機能がプローブで実現され、フロー制御機能がルータで実現されてもよい。その場合は、プローブとルータをまとめたものが計測装置１００に相等する。
【００３８】
２．帯域幅割当装置２００
２−１．構成
図４は、本実施の形態に係る帯域幅割当装置２００の構成を示すブロック図である。帯域幅割当装置２００は、例えばサーバである。詳細には、帯域幅割当装置２００は、処理装置２０１と記憶装置２０２を備えている。処理装置２０１は、ＣＰＵを含んでいる。記憶装置２０２は、ＲＡＭやＨＤＤを含んでいる。記憶装置２０２（記憶部）には、経路情報ＰＡＴ、リンク容量情報ＣＡＰ、割当帯域幅情報ＡＬＣ、計測情報ＭＳＲ、使用帯域幅情報ＵＳＢ、調整量情報ＩＮＣ、予測最大帯域幅情報ＰＲＥ、帯域幅割当プログラムＰＲＯＧなどが格納される。
【００３９】
経路情報ＰＡＴは、フロー毎の経路を示す。図５は、経路情報ＰＡＴの一例を概念的に示している。図５の例では、経路情報ＰＡＴは、フローが経由する経由リンクをフロー毎に示している。フローは、送信側のＩＰアドレスと受信側のＩＰアドレスの組により規定されている。各フローに関して、通過するリンクは「１」で示されており、通過しないリンクは「０」で示されている。フローの経路が変更された場合、経路情報ＰＡＴも更新される。
【００４０】
リンク容量情報ＣＡＰは、リンク毎のリンク容量を示す。図６は、リンク容量情報ＣＡＰの一例を概念的に示している。リンク容量情報ＣＡＰは、リンク（Ｌ１〜ＬＮ）とリンク容量との対応関係を示している。
【００４１】
割当帯域幅情報ＡＬＣは、帯域幅割当装置２００により決定されるフロー毎の割当帯域幅Ａｐを示す。図７は、割当帯域幅情報ＡＬＣの一例を概念的に示している。割当帯域幅情報ＡＬＣは、フローと割当帯域幅Ａｐとの対応関係を示している。フローは、送信側のＩＰアドレスと受信側のＩＰアドレスの組により規定されている。最初、各フローの割当帯域幅Ａｐは適切な初期値に初期設定される。その後、帯域幅割当装置２００によって、各フローの割当帯域幅Ａｐは動的に変更される。割当帯域幅Ａｐが更新されるたびに、割当帯域幅情報ＡＬＣも更新される。古い割当帯域幅Ａｐは新しいもので上書きされてもよいし、新しい割当帯域幅Ａｐが追記されてもよい。割当帯域幅情報ＡＬＣは、所定期間における割当帯域幅Ａｐの履歴を示していてもよい。
【００４２】
使用帯域幅情報ＵＳＢ、調整量情報ＩＮＣ、予測最大帯域幅情報ＰＲＥについては後述される。
【００４３】
帯域幅割当プログラムＰＲＯＧは、処理装置２０１によって実行されるコンピュータプログラムである。帯域幅割当プログラムＰＲＯＧは、コンピュータ読み取り可能な記録媒体に記録されていてもよい。
【００４４】
処理装置２０１は、帯域幅割当プログラムＰＲＯＧを実行することによって、フローに帯域幅を動的に割り当てる「動的割当処理」を行う。より詳細には、処理装置２０１は、受信部２１０、使用帯域幅取得部２２０、最大帯域幅予測部２３０、割当帯域幅決定部２４０、制御情報通知部２５０といった機能ブロックを有する。これら機能ブロックは、処理装置２０１が帯域幅割当プログラムＰＲＯＧを実行することによって実現され、動的割当処理を行う。これら機能ブロックは、必要に応じて、記憶装置２０２から情報を読み出し、また、記憶装置２０２に情報を書き込む。以下、本実施の形態に係る処理を詳しく説明する。
【００４５】
２−２．動的割当処理
図８は、本実施の形態に係る動的割当処理（ステップＳ２００）を示すフローチャートである。図９は、本実施の形態に係る動的割当処理を示す概念図である。
【００４６】
＜ステップＳ２１０＞
受信部２１０は、各計測装置１００から送られる計測情報ＭＳＲを受け取り、受け取った計測情報ＭＳＲを記憶装置２０２に格納する。上述の通り、計測情報ＭＳＲは、各計測装置１００において計測されたフローの使用帯域幅Ｘｐに関連する情報（ヘッダ情報、パケット数、バイト数、サンプリング率、等）を含んでいる。
【００４７】
＜ステップＳ２２０＞
使用帯域幅取得部２２０は、計測情報ＭＳＲ（及び必要に応じて経路情報ＰＡＴ）に基づいて、各フローの使用帯域幅Ｘｐを取得（算出）する。そして、使用帯域幅取得部２２０は、フロー毎の使用帯域幅Ｘｐを示す使用帯域幅情報ＵＳＢを作成し、作成した使用帯域幅上方ＵＳＢを記憶装置２０２に格納する。
【００４８】
図１０は、使用帯域幅情報ＵＳＢの一例を概念的に示している。図１０の例では、送信側のＩＰアドレスと受信側のＩＰアドレスとの組により規定されるフロー毎に、使用帯域幅Ｘｐが示されている。図１０に示されるような情報は、トラヒック行列（ＴＭ：Ｔｒａｆｆｉｃ  Ｍａｔｒｉｘ）とも呼ばれる。
【００４９】
図１１は、使用帯域幅情報ＵＳＢの他の例を概念的に示している。図１１の例では、フロー毎に、使用帯域幅Ｘｐと経由リンクが示されている。更に、リンク毎に、使用帯域幅Ｘｐの総和が示されている。図１１で示される使用帯域幅情報ＵＳＢは、図１０で示されたＴＭと図５で示された経路情報ＰＡＴとを組み合わせることによって得られ、相関行列（ＣＭ：Ｃｏｒｒｅｌａｔｉｏｎ  Ｍａｔｒｉｘ）とも呼ばれる。
【００５０】
尚、使用帯域幅取得部２２０は、同一経路を通る複数のフローを集約（aggregate）してもよい。その場合、使用帯域幅取得部２２０は、経路情報ＰＡＴを参照することによってフローを集約し、集約後のフロー毎に使用帯域幅Ｘｐを算出する。フロー集約は、後の第５節において例示される。
【００５１】
＜ステップＳ２３０＞
最大帯域幅予測部２３０は、フロー毎に最大帯域幅を予測し、予測最大帯域幅Ｔｐを算出する（予測処理）。より詳細には、最大帯域幅予測部２３０は、割当帯域幅情報ＡＬＣと使用帯域幅情報ＵＳＢを参照して、各フローに関する割当帯域幅Ａｐの使用状況を調べる。そして、最大帯域幅予測部２３０は、その使用状況に応じて各フローの最大帯域幅を予測する。
【００５２】
例えば、使用帯域幅Ｘｐがほぼ割当帯域幅Ａｐと等しい場合、そのフローは割当帯域幅Ａｐを使い切っていると考えられる。この場合、当該フローの最大帯域幅は、現在の使用帯域幅Ｘｐよりももっと多いと予測される。一方、使用帯域幅Ｘｐが割当帯域幅Ａｐよりもはるかに少ない場合、そのフローは割当帯域幅Ａｐを使い切らないと考えられる。この場合、当該フローの最大帯域幅は、現在の使用帯域幅Ｘｐの近傍と予測される。このようなことから、本実施の形態では、予測最大帯域幅Ｔｐは、現在の使用帯域幅Ｘｐと調整量ΔＸｐとを用いて、次の式（１）で表される。
【００５３】
【数１】
2011049891.tif 000003
【００５４】
最大帯域幅予測部２３０は、割当帯域幅Ａｐの使用状況に応じて、この調整量ΔＸｐを決定する。すなわち、フローが割当帯域幅Ａｐを使い切っている場合、調整量ΔＸｐは大きな値（第１調整量）に設定される。一方、フローが割当帯域幅Ａｐを使い切っていない場合、調整量ΔＸｐは小さな値（第２調整量）に設定される。第２調整量は、第１調整量よりも小さい。そして、最大帯域幅予測部２３０は、このようにして得られた調整量ΔＸｐを使用帯域幅Ｘｐに加えることによって、予測最大帯域幅Ｔｐを算出する。
【００５５】
記憶装置２０２に格納される調整量情報ＩＮＣは、フロー毎の調整量ΔＸｐを示す情報である。最初、調整量ΔＸｐは適切な初期値に初期設定される。その後、新たに調整量ΔＸｐが算出されるたびに、調整量情報ＩＮＣは更新される。古い調整量ΔＸｐは新しいもので上書きされてもよいし、新しい調整量ΔＸｐが追記されてもよい。調整量情報ＩＮＣは、所定期間における調整量ΔＸｐの履歴を示していてもよい。
【００５６】
以下、図１２で示されるフローチャートを参照して、本実施の形態におけるステップＳ２３０をより詳細に説明する。
【００５７】
ステップＳ２３１：
割当帯域幅Ａｐの使用状況を調べるために、使用帯域幅Ｘｐを割当帯域幅Ａｐと比較することが考えられる。但し、本実施の形態では、パケットサンプリングの誤差率が考慮に入れられ、使用帯域幅Ｘｐの比較対象は、割当帯域幅Ａｐよりも小さい閾値Ａｐ’に設定される。ステップＳ２３１では、最大帯域幅予測部２３０は、使用帯域幅Ｘｐの比較対象となる閾値Ａｐ’を算出する。例えば、閾値Ａｐ’は次の式（２）で与えられる。
【００５８】
【数２】
2011049891.tif 000004
【００５９】
上記式（２）において、Ａｐは現在の割当帯域幅であり、割当帯域幅情報ＡＬＣから得られる。ｓは計測装置１００において計測されたパケット数であり、計測情報ＭＳＲから得られる。αは０より大きく１以下の整数であり、例えば０．９５である。βは信頼区間に関連するパラメータである。信頼区間を９０％、９５％、９９％に設定したい場合、βはそれぞれ１６５、１９６、２５８に設定される。割当帯域幅Ａｐと閾値Ａｐ’との差分は、使用帯域幅Ｘｐの測定誤差に相等する。
【００６０】
ステップＳ２３２：
最大帯域幅予測部２３０は、使用帯域幅Ｘｐを閾値Ａｐ’と比較する。使用帯域幅Ｘｐは、使用帯域幅情報ＵＳＢから得られる。使用帯域幅Ｘｐが閾値Ａｐ’以上である場合（ステップＳ２３２；Ｙｅｓ）、次にステップＳ２３３が実施される。一方、使用帯域幅Ｘｐが閾値Ａｐ’未満である場合（ステップＳ２３２；Ｎｏ）、次にステップＳ２３４が実施される。
【００６１】
ステップＳ２３３：
図１３は、ステップＳ２３３の場合を示している。使用帯域幅Ｘｐは閾値Ａｐ’以上である。この場合、最大帯域幅予測部２３０は、調整量ΔＸｐを比較的大きな値（第１調整量）に設定する。例えば、第１調整量は、次の式（３）で与えられる。
【００６２】
【数３】
2011049891.tif 000005
【００６３】
左辺のΔＸｐ（ｔ）は、今回算出される第１調整量である。右辺のΔＸｐ（ｔ−１）は、前回決定された調整量ΔＸｐであり、調整量情報ＩＮＣから得られる。式（３）で示されるように、第１調整量ΔＸｐ（ｔ）は、前回の調整量ΔＸｐ（ｔ−１）の２倍に増やされている。
【００６４】
ステップＳ２３４：
図１４は、ステップＳ２３４の場合を示している。使用帯域幅Ｘｐは閾値Ａｐ’未満である。この場合、最大帯域幅予測部２３０は、調整量ΔＸｐを比較的小さな値（第２調整量）に設定する。例えば、第２調整量は、次の式（４）で与えられる。
【００６５】
【数４】
2011049891.tif 000006
【００６６】
左辺のΔＸｐ（ｔ）は、今回算出される第２調整量である。右辺のΔＸｐ（ｔ−１）は、前回決定された調整量ΔＸｐであり、調整量情報ＩＮＣから得られる。式（４）で示されるように、第２調整量ΔＸｐ（ｔ）は、前回の調整量ΔＸｐ（ｔ−１）の半分に減らされている。
【００６７】
尚、調整量ΔＸｐは、上記式（３）、（４）で表されたものに限られない。調整量ΔＸｐは、線形関数、指数関数、あるいは固定値で与えられてもよい。第２調整量は、ゼロあるいは負値であってもよい。
【００６８】
ステップＳ２３５：
調整量ΔＸｐが決定されると、最大帯域幅予測部２３０は、決定された調整量ΔＸｐを調整量情報ＩＮＣに記録する。
【００６９】
ステップＳ２３６：
最大帯域幅予測部２３０は、上記式（１）に従って、予測最大帯域幅Ｔｐを算出する。記憶装置２０２に格納される予測最大帯域幅情報ＰＲＥは、フロー毎の予測最大帯域幅Ｔｐを示す情報である。新たに予測最大帯域幅Ｔｐが算出されるたびに、予測最大帯域幅情報ＰＲＥは更新される。古い予測最大帯域幅Ｔｐは新しいもので上書きされてもよいし、新しい予測最大帯域幅Ｔｐが追記されてもよい。予測最大帯域幅情報ＰＲＥは、所定期間における予測最大帯域幅Ｔｐの履歴を示していてもよい。
【００７０】
＜ステップＳ２４０＞
割当帯域幅決定部２４０は、フロー毎に割当帯域幅Ａｐを決定し、割当帯域幅情報ＡＬＣを更新する（割当処理）。そのために、割当帯域幅決定部２４０は、予測最大帯域幅情報ＰＲＥ、経路情報ＰＡＴ、及びリンク容量情報ＣＡＰを参照する。
【００７１】
本実施の形態では、割当帯域幅決定部２４０は、基本的に、ステップＳ２３０で得られた予測最大帯域幅Ｔｐを該当フローに割り当てる、すなわち、割当帯域幅Ａｐを予測最大帯域幅Ｔｐに更新する。但し、全てのフローにそれぞれ予測最大帯域幅Ｔｐを割り当てると、あるリンクを通過するフローの割当帯域幅Ａｐの総和が当該リンクのリンク容量を超えてしまう可能性がある。そのため、割当帯域幅決定部２４０は、各フローの経路及びその経路上の各リンクのリンク容量を考慮にいれて、それぞれのフローの割当帯域幅Ａｐを決定する。具体的には、割当帯域幅決定部２４０は、リンク容量を超えない範囲でなるべく多くのフローに予測最大帯域幅Ｔｐを割り当てる。
【００７２】
以下、図１５で示されるフローチャートを参照して、本実施の形態におけるステップＳ２４０をより詳細に説明する。
【００７３】
［初期設定］
まず、初期設定が行われる（ステップＳ２４１）。初期設定において、パラメータｋと仮割当帯域幅ａｐｋが定義される。パラメータｋは、次に説明されるループ処理の繰り返し回数を示す。このパラメータｋの初期値は０である。仮割当帯域幅ａｐｋは、ループ処理において各フローの割当帯域幅Ａｐを調整するために用いられる。仮割当帯域幅ａｐｋの初期値は０である。あるいは、仮割当帯域幅ａｐｋの初期値は、現在の割当帯域幅Ａｐに設定されてもよい。
【００７４】
［ループ処理］
パラメータｋが１だけインクリメントされる（ステップＳ２４２）。続いて、割当帯域幅決定部２４０は、「飽和帯域幅Ｓｐｋ」を算出する（ステップＳ２４３）。飽和帯域幅Ｓｐｋとは、少なくとも１つのリンクにおいて帯域幅が飽和するような割当帯域幅Ａｐである。言い換えれば、飽和帯域幅Ｓｐｋとは、リンク容量の範囲内で各フローに分配され得る帯域幅である。割当帯域幅決定部２４０は、リンク容量情報ＣＡＰ及び経路情報ＰＡＴを参照することによって、飽和帯域幅Ｓｐｋを算出することができる。
【００７５】
より詳細には、割当帯域幅決定部２４０は、スケジューリングポリシに従って飽和帯域幅Ｓｐｋを算出する。例えば、スケジューリングポリシは、“ｍａｘ−ｍｉｎ  ｆａｉｒ”である。この場合、割当帯域幅決定部２４０はまず、次の式（５）に従って、分配量ｂｋを算出する（ステップＳ２４４）。
【００７６】
【数５】
2011049891.tif 000007
【００７７】
上記式（５）において、Ｃｌはリンクｌ（＝Ｌ１〜ＬＮ）のリンク容量であり、リンク容量情報ＣＡＰから得られる。Ｆｌｋ−１は、リンクｌを通過する全フローの仮割当帯域幅ａｐｋ−１の合計であり、経路情報ＰＡＴと各フローの仮割当帯域幅ａｐｋ−１から算出される。それらの差分（Ｃｌ−Ｆｌｋ−１）は、残余帯域幅である。ｎｌｋ−１は、次の３つの条件を満たすフローの数である：（１）リンクｌを通る、（２）仮割当帯域幅ａｐｋ−１が予測最大帯域幅Ｔｐではない、（３）飽和リンクを通過しない。ここでの飽和リンクとは、残余帯域幅（Ｃｌ−Ｆｌｋ−１）が無くなったリンクである。ｎｌｋ−１は、予測最大帯域幅情報ＰＲＥ、リンク容量情報ＣＡＰ、経路情報ＰＡＴ及び各フローの仮割当帯域幅ａｐｋ−１を参照することによって算出される。分配量ｂｋは、リンクＬ１〜ＬＮのそれぞれに関して残余帯域幅（Ｃｌ−Ｆｌｋ−１）をフロー数ｎｌｋ−１で割ることにより得られるＮ個の値のうち、最小のものである。
【００７８】
続いて、割当帯域幅決定部２４０は、ステップＳ２４４で得られた分配量ｂｋを用いて、飽和帯域幅Ｓｐｋを算出する（ステップＳ２４５）。具体的には、割当帯域幅決定部２４０は、次の式（６）で示されるように、仮割当帯域幅ａｐｋ−１に分配量ｂｋを加えることによって飽和帯域幅Ｓｐｋを算出する。
【００７９】
【数６】
2011049891.tif 000008
【００８０】
次に、割当帯域幅決定部２４０は、飽和帯域幅Ｓｐｋと予測最大帯域幅Ｔｐとの比較を行い、より少ない一方を新たな仮割当帯域幅ａｐｋとして選択する（ステップＳ２４６）。これにより、リンク容量を超えて帯域幅が割り当てられることが防止される。また、予測最大帯域幅Ｔｐを超えて過剰に帯域幅が割り当てられることが防止される。
【００８１】
【数７】
2011049891.tif 000009
【００８２】
次に、全てのフローに関して仮割当帯域幅ａｐｋが予測最大帯域幅Ｔｐとなったか否かがチェックされる（ステップＳ２４７）。全フローに関して仮割当帯域幅ａｐｋが予測最大帯域幅Ｔｐとなった場合（ステップＳ２４７；Ｙｅｓ）、それは、全フローに関して予測最大帯域幅Ｔｐが確保されたことを意味する。この場合、仮割当帯域幅ａｐｋをこれ以上増やす必要はないため、ループ処理は終了する。
【００８３】
一方、少なくとも１つのフローに関して仮割当帯域幅ａｐｋが予測最大帯域幅Ｔｐではない場合（ステップＳ２４７；Ｎｏ）、当該フローが飽和リンクを通過しているか否かがチェックされる（ステップＳ２４８）。ここでの飽和リンクとは、残余帯域幅（Ｃｌ−Ｆｌｋ）が無くなったリンクである。当該フローが飽和リンクを経由している場合（ステップＳ２４８；Ｙｅｓ）、仮割当帯域幅ａｐｋをこれ以上増やすことはできない。従って、ループ処理は終了する。
【００８４】
一方、当該フローが飽和リンクを通過していない場合（ステップＳ２４８；Ｎｏ）、当該フローの仮割当帯域幅ａｐｋを増やすことができる可能性がある。従って、処理はステップＳ２４２に戻り、新たな仮割当帯域幅ａｐｋに基づいてループ処理が再度実行される。その結果、飽和帯域幅Ｓｐｋ及び仮割当帯域幅ａｐｋが更新される。このように、割当帯域幅決定部２４０は、ステップＳ２４７、Ｓ２４８の条件が満たされるまで、ループ処理を繰り返す。尚、ステップＳ２４７、Ｓ２４８の条件が満たされることは、全リンク（Ｌ１〜ＬＮ）に関するｎｌｋが全て０になることに相当する。
【００８５】
［割当帯域幅Ａｐの決定］
ステップＳ２４７、Ｓ２４８の条件が満たされた場合（ステップＳ２４７；Ｙｅｓ、ステップＳ２４８；Ｙｅｓ）、割当帯域幅決定部２４０は、現在の仮割当帯域幅ａｐｋを新たな割当帯域幅Ａｐとして決定する（ステップＳ２４９）。割当帯域幅決定部２４０は、決定された新たな割当帯域幅Ａｐを割当帯域情報ＡＬＣに書き込み、割当帯域幅情報ＡＬＣを更新する。
【００８６】
【数８】
2011049891.tif 000010
【００８７】
次に、図１６で示される場合を例に挙げて、ステップＳ２４０の処理の具体例を説明する。リンクＬ１〜Ｌ１２の各々のリンク容量は１０である。フローＦＡ、ＦＢ、ＦＣ、ＦＤの使用帯域幅Ｘｐはそれぞれ３、２、２、５である。ステップＳ２３０において、フローＦＡ、ＦＢ、ＦＣ、ＦＤの予測最大帯域幅Ｔｐは、それぞれ１６／５、１１／５、１１／５、２６／５と予測されたとする。
【００８８】
［ｋ＝０］
ステップＳ２４１において初期設定が行われる。フローＦＡ、ＦＢ、ＦＣ、ＦＤの仮割当帯域幅ａｐ０は全て０である。ｎｌ０は、次の式（９）で表される。
【００８９】
【数９】
2011049891.tif 000011
【００９０】
［ｋ＝１］
式（５）に従って、分配量ｂ１は１０／３（＝（１０−０）／３）と算出される。式（６）、式（７）に従って、フローＦＡ、ＦＢ、ＦＣ、ＦＤのそれぞれの仮割当帯域幅ａｐ１は、次の通り算出される。
ａ（ＦＡ）１＝ｍｉｎ（０＋１０／３，１６／５）＝１６／５
ａ（ＦＢ）１＝ｍｉｎ（０＋１０／３，１１／５）＝１１／５
ａ（ＦＣ）１＝ｍｉｎ（０＋１０／３，１１／５）＝１１／５
ａ（ＦＤ）１＝ｍｉｎ（０＋１０／３，２６／５）＝１０／３
【００９１】
フローＦＤに関して、ステップＳ２４７の条件が満たされていない（ステップＳ２４７；Ｎｏ）。また、フローＦＤは、リンクＬ３、Ｌ１２、Ｌ１０、Ｌ９及びＬ８を通過している。リンクＬ３の現在の残余帯域幅は、１０−（ａ（ＦＡ）１＋ａ（ＦＤ）１）＝５２／１５である。すなわち、リンクＬ３は飽和リンクではない。同様に、他のリンクＬ１２、Ｌ１０、Ｌ９及びＬ８も飽和リンクではない。従って、ステップＳ２４８の条件も満たされていない（ステップＳ２４８；Ｎｏ）。ｎｌ１は、次の式（１０）で表される。
【００９２】
【数１０】
2011049891.tif 000012
【００９３】
［ｋ＝２］
式（５）に従って、分配量ｂ２は１９／１５（＝（１０−１６／５−１１／５−１０／３）／１）と算出される。式（６）、式（７）に従って、フローＦＡ、ＦＢ、ＦＣ、ＦＤのそれぞれの仮割当帯域幅ａｐ２は、次の通り算出される。
ａ（ＦＡ）２＝ｍｉｎ（１６／５＋１９／１５，１６／５）＝１６／５
ａ（ＦＢ）２＝ｍｉｎ（１１／５＋１９／１５，１１／５）＝１１／５
ａ（ＦＣ）２＝ｍｉｎ（１１／５＋１９／１５，１１／５）＝１１／５
ａ（ＦＤ）２＝ｍｉｎ（１０／３＋１９／１５，２６／５）＝６９／１５
【００９４】
フローＦＤに関して、ステップＳ２４７の条件が満たされていない（ステップＳ２４７；Ｎｏ）。しかしながら、フローＦＤが通過するＬ１２及びＬ１０の現在の残余帯域幅は、１０−（ａ（ＦＡ）２＋ａ（ＦＣ）２＋ａ（ＦＤ）２）＝０である。すなわち、リンクＬ１２、Ｌ１０は飽和リンクであり、ステップＳ２４８の条件が満たされる（ステップＳ２４８；Ｙｅｓ）。ｎｌ２は、次の式（１１）で表される。
【００９５】
【数１１】
2011049891.tif 000013
【００９６】
結果として、フローＦＡ、ＦＢ、ＦＣ、ＦＤの割当帯域幅Ａｐは、それぞれ１６／５、１１／５、１１／５、６９／１５と決定される。
【００９７】
＜ステップＳ２５０＞
制御情報通知部２５０は、割当帯域幅情報ＡＬＣを参照して、割当帯域幅Ａｐに応じた制御情報ＣＯＮを作成する。制御情報ＣＯＮは、各計測装置１００において割当帯域幅Ａｐに応じたフロー制御を実現するための情報である。
【００９８】
例えば、パケットを廃棄することでフロー制御が行われる場合には、制御情報ＣＯＮは廃棄確率を示す。あるいは、パケットの送信順序をスケジューリングすることでフロー制御が行われる場合には、制御情報ＣＯＮは制御パラメータ（重み値等）を示す。例えば、計測装置１００（ルータ）においてＷＦＱ（Ｗｅｉｇｈｔｅｄ  Ｆａｉｒ  Ｑｕｅｕｉｎｇ）やＷＲＲ（Ｗｅｉｇｈｔｅｄ  Ｒｏｕｎｄ  Ｒｏｂｉｎ）に基づく制御が行われる場合、割当帯域幅Ａｐは、ＷＦＱやＷＲＲで用いられる重み値に変換される。
【００９９】
あるいは、制御情報ＣＯＮは、フロー毎の割当帯域幅Ａｐそのものを示していてもよい。その場合、各計測装置１００のフロー制御部１３０が、割当帯域幅Ａｐを、廃棄確率や制御パラメータに変換する。
【０１００】
更に、制御情報ＣＯＮは、制御対象のフローの識別子も含んでいる。制御情報通知部２５０は、そのような制御情報ＣＯＮを各計測装置１００に送信する。制御情報ＣＯＮの送信には、既存のプロトコル（例：ＴＣＰ、ＵＤＰ）が使用される。
【０１０１】
３．効果
本実施の形態では、帯域幅の使用状況に連動して、割当帯域幅Ａｐが動的に変化する。図１７は、あるフローに関する割当帯域幅Ａｐ及び使用帯域幅Ｘｐの遷移の一例を示している。割当帯域幅Ａｐの初期値は５であり、調整量ΔＸｐの初期値は１であるとする。また、簡単のため、ステップＳ２４０において、飽和帯域幅Ｓｐｋよりも予測最大帯域幅Ｔｐの方が少なくなるとする。
【０１０２】
［時刻ｔ１］
割当帯域幅Ａｐは５であり、使用帯域幅Ｘｐは４．５であり、閾値Ａｐ’は３である。使用帯域幅Ｘｐが閾値Ａｐ’以上であるため、式（３）に従って、調整量ΔＸｐは、２（＝２×１）と決定される。予測最大帯域幅Ｔｐは、６．５（＝４．５＋２）と予測される。割当帯域幅Ａｐは６．５に更新される。
【０１０３】
［時刻ｔ２］
割当帯域幅Ａｐは６．５であり、使用帯域幅Ｘｐは５．５であり、閾値Ａｐ’は５である。使用帯域幅Ｘｐが閾値Ａｐ’以上であるため、式（３）に従って、調整量ΔＸｐは、４（＝２×２）と決定される。予測最大帯域幅Ｔｐは、９．５（＝５．５＋４）と予測される。割当帯域幅Ａｐは９．５に更新される。
【０１０４】
［時刻ｔ３］
割当帯域幅Ａｐは９．５であり、使用帯域幅Ｘｐは６であり、閾値Ａｐ’は７である。使用帯域幅Ｘｐが閾値Ａｐ’未満であるため、式（４）に従って、調整量ΔＸｐは、２（＝０．５×４）と決定される。予測最大帯域幅Ｔｐは、８（＝６＋２）と予測される。割当帯域幅Ａｐは８に更新される。
【０１０５】
［時刻ｔ４］
割当帯域幅Ａｐは８であり、使用帯域幅Ｘｐは５であり、閾値Ａｐ’は６である。使用帯域幅Ｘｐが閾値Ａｐ’未満であるため、式（４）に従って、調整量ΔＸｐは、１（＝０．５×２）と決定される。予測最大帯域幅Ｔｐは、６（＝５＋１）と予測される。割当帯域幅Ａｐは６に更新される。
【０１０６】
このように、本実施の形態によれば、各フローに割り当てられる割当帯域幅Ａｐが動的に制御される。その結果、フローの未使用帯域幅やリンクの残余帯域幅の発生が抑制される。また、残余帯域幅があるにもかかわらずその残余帯域幅を有効に活用できないといった事態が防止される。従って、ネットワーク使用率が向上する。
【０１０７】
４．変形例
４−１．第１の変形例
図１８は、第１の変形例に係るステップＳ２３０を示すフローチャートである。重複する説明は適宜省略される。
【０１０８】
本変形例では、閾値Ａｐ’を算出するステップＳ２３１（図１２参照）が省かれる。そして、ステップＳ２３２の代わりに、ステップＳ２３２ａが行われる。ステップＳ２３２ａにおいて、最大帯域幅予測部２３０は、使用帯域幅Ｘｐを割当帯域幅Ａｐと比較する。すなわち、本変形例では、割当帯域幅Ａｐが閾値に相当する。使用帯域幅Ｘｐが割当帯域幅Ａｐと同じである場合（ステップＳ２３２ａ；Ｙｅｓ）、ステップＳ２３３が実施される。一方、使用帯域幅Ｘｐが割当帯域幅Ａｐ未満である場合（ステップＳ２３２ａ；Ｎｏ）、ステップＳ２３４が実施される。
【０１０９】
本変形例によれば、計算量が削減され、帯域幅割当装置２００（サーバ）にかかる負荷が軽減される。
【０１１０】
４−２．第２の変形例
図１９は、第２の変形例に係るステップＳ２３０を示すフローチャートである。重複する説明は適宜省略される。
【０１１１】
本変形例では、閾値Ａｐ’を算出するステップＳ２３１（図１２参照）が省かれる。そして、ステップＳ２３２の代わりに、ステップＳ２３２ｂが行われる。ステップＳ２３２ｂにおいて、最大帯域幅予測部２３０は、現在の使用帯域幅Ｘｐ（ｔ）を１時刻前の使用帯域幅Ｘｐ（ｔ−１）と比較する。すなわち、本変形例では、１時刻前の使用帯域幅Ｘｐ（ｔ−１）が閾値に相当する。現在の使用帯域幅Ｘｐ（ｔ）が１時刻前の使用帯域幅Ｘｐ（ｔ−１）より大きい場合（ステップＳ２３２ｂ；Ｙｅｓ）、ステップＳ２３３が実施される。一方、現在の使用帯域幅Ｘｐ（ｔ）が１時刻前の使用帯域幅Ｘｐ（ｔ−１）以下の場合（ステップＳ２３２ｂ；Ｎｏ）、ステップＳ２３４が実施される。
【０１１２】
本変形例によれば、計算量が削減され、帯域幅割当装置２００（サーバ）にかかる負荷が軽減される。
【０１１３】
４−３．第３の変形例
図２０は、第３の変形例に係るステップＳ２３０を示すフローチャートである。重複する説明は適宜省略される。
【０１１４】
本変形例によれば、使用帯域幅Ｘｐが閾値Ａｐ’未満である場合（ステップＳ２３２；Ｎｏ）、ステップＳ２３４の代わりにステップＳ２３７が実施される。ステップＳ２３７において、最大帯域幅予測部２３０は、現在の使用帯域幅Ｘｐを当該フローの最大帯域幅とみなす。すなわち、最大帯域幅予測部２３０は、調整量ΔＸｐ（第２調整量）を０に設定し、予測最大帯域幅Ｔｐを現在の使用帯域幅Ｘｐに確定する。そして、最大帯域幅予測部２３０は、確定した予測最大帯域幅Ｔｐを、予測最大帯域幅情報ＰＲＥに登録する。
【０１１５】
確定した予測最大帯域幅Ｔｐは、所定の周期でリフレッシュされてもよい。そのために、ステップＳ２３０が開始すると、まず、ステップＳ２３８が実行される。ステップＳ２３８では、予測最大帯域幅Ｔｐを新たに算出する必要があるかどうか判定される。必要な場合とは、（Ａ）予測最大帯域幅Ｔｐが未だ確定していないフローがある場合と、（Ｂ）所定の周期が経過し、予測最大帯域幅Ｔｐをリフレッシュする場合である。必要な場合（ステップＳ２３８；Ｙｅｓ）、ステップＳ２３１〜の処理が実施される。それ以外の場合（ステップＳ２３８；Ｎｏ）、最大帯域幅予測部２３０は、予測最大帯域幅情報ＰＲＥに登録されている確定した予測最大帯域幅Ｔｐを読み出す（ステップＳ２３９）。その後、処理はステップ２４０へ進む。
【０１１６】
本変形例によれば、計算量が削減され、帯域幅割当装置２００（サーバ）にかかる負荷が軽減される。
【０１１７】
また、上述の変形例同士を組み合わせることも可能である。その場合、計算量が更に削減され、帯域幅割当装置２００（サーバ）にかかる負荷が更に軽減される。
【０１１８】
５．インナーフローとアウターフロー
図２１を参照して、「インナーフロー」と「アウターフロー」を説明する。図２１には、端末１１〜１５及びルータ１００−１〜１００−９が示されている。端末１１〜１５は、パケットを送受信し、フロー通信を行う。ルータ１００−１〜１００−９の各々は、本実施の形態に係る計測装置１００である。また、ネットワークの境界に位置するルータは、以下、「エッジルータ」と参照される。図２１の例において、ルータ１００−１〜１００−４は、ネットワークＮＥＴ１のエッジルータである。
【０１１９】
「アウターフロー」とは、ネットワークＮＥＴ１の外側で定義されるフローである。一方、「インナーフロー」とは、ネットワークＮＥＴ１の内側で定義されるフローである。フロー識別子が送信側のＩＰアドレスと受信側のＩＰアドレスの組である場合、「アウターフロー」は、送信端末のＩＰアドレスと受信端末のＩＰアドレスの組で識別される。一方、「インナーフロー」は、送信端末が接続しているエッジルータのＩＰアドレスと受信端末が接続しているエッジルータのＩＰアドレスの組で識別される。
【０１２０】
図２１の例では、フローＦＡは、送信端末１１と受信端末１２のＩＰアドレスの組で識別されるアウターフローであり、送信側エッジルータ１００−１と受信側エッジルータ１００−２のＩＰアドレスの組で識別されるインナーフローである。フローＦＢは、送信端末１５と受信端末１２のＩＰアドレスの組で識別されるアウターフローであり、送信側エッジルータ１００−１と受信側エッジルータ１００−２のＩＰアドレスの組で識別されるインナーフローである。フローＦＣは、送信端末１３と受信端末１４のＩＰアドレスの組で識別されるアウターフローであり、送信側エッジルータ１００−３と受信側エッジルータ１００−４のＩＰアドレスの組で識別されるインナーフローである。
【０１２１】
この場合、ネットワークＮＥＴ１にとって、フローＦＡとフローＦＢは、異なるアウターフローではあるが、同一のインナーフローである。このように複数のフローが同一のインナーフローである場合、本実施の形態の処理を実行するに際してそれら複数のフローを集約（aggregate）して考えることができる。フローを集約する場合の処理は、次の通りである。
【０１２２】
各計測装置１００は、自身を通過する各アウターフローを計測し、計測したアウターフローに関する計測情報ＣＯＮを帯域幅割当装置２００に送信する。帯域幅割当装置２００が有する経路情報ＰＡＴは、アウターフロー毎の経路とインナーフロー毎の経路の両方を示す。従って、使用帯域幅取得部２２０は、その経路情報ＰＡＴと計測装置１００から受け取ったアウターフローに関する計測情報ＣＯＮとを参照することによって、「インナーフロー毎の使用帯域幅Ｘｐ」を算出することができる。すなわち、複数のフローが同一のインナーフローである場合、それら複数のフローが集約される。
【０１２３】
尚、送信側エッジルータと受信側エッジルータのＩＰアドレスは、次の方法で取得することができる。送信側エッジルータのＩＰアドレスは、計測装置１００−１のＩＰアドレスを参照することでわかる。受信側エッジルータのＩＰアドレスは、ＩＰＦＩＸのメッセージ内のＢＧＰ（Ｂｏｒｄｅｒ  Ｇａｔｅｗａｙ  Ｐｒｏｔｏｃｏｌ）  ｎｅｘｔ  ｈｏｐ  ＩＰアドレスを参照することでわかる。あるいは、アウターフローの送信ＩＰアドレス及び受信ＩＰアドレスとそのアウターフローの経路情報を用いることにより、送信側エッジルータと受信側エッジルータのＩＰアドレスを取得することができる。
【０１２４】
アウターフローとインナーフローをサブネット単位で定義することも可能である。
【０１２５】
上記例では、アウターフローを送信端末と受信端末のＩＰアドレスで識別し、インナーフローを送信側エッジルータと受信側エッジルータのＩＰアドレスで識別したが、その他の形態も可能である。例えば、アウターフローを７ｔｕｐｌｅ（ｓｒｃＭＡＣ，ｄｓｔＭＡＣ，ｓｒｃＩＰ，ｄｓｔＩＰ，ｓｒｃＰｏｒt，ｄｓｔＰｏｒｔ，Ｐｒｏｔｏｃｏｌ）で識別し、インナーフローを５ｔｕｐｌｅ（ｓｒｃＩＰ，ｄｓｔＩＰ，ｓｒｃＰｏｒt，ｄｓｔＰｏｒｔ，Ｐｒｏｔｏｃｏｌ）で識別してもよい。ここで、ｓｒｃは送信端末を、ｄｓｔは受信端末を、Ｐｒｏｔｏｃｏｌはプロトコル番号をそれぞれ意味する。
【０１２６】
以上、本発明の実施の形態が添付の図面を参照することにより説明された。但し、本発明は、上述の実施の形態に限定されず、要旨を逸脱しない範囲で当業者により適宜変更され得る。
【符号の説明】
【０１２７】
１  ネットワークシステム
１１〜１５  端末
１００  計測装置
１０１  処理装置
１０２  記憶装置
１１０  キャプチャ部
１２０  計測部
１３０  フロー制御部
２００  帯域幅割当装置
２０１  処理装置
２０２  記憶装置
２１０  受信部
２２０  使用帯域幅取得部
２３０  最大帯域幅予測部
２４０  割当帯域幅決定部
２５０  制御情報通知部
ＮＥＴ  ネットワーク
ＭＳＲ  計測情報
ＣＯＮ  制御情報
ＰＡＴ  経路情報
ＣＡＰ  リンク容量情報
ＡＬＣ  割当帯域幅情報
ＵＳＢ  使用帯域幅情報
ＩＮＣ  調整量情報
ＰＲＥ  予測最大帯域幅情報
ＰＲＯＧ  帯域幅割当プログラム
【図１】
2011049891.tif 000014
【図２】
2011049891.tif 000015
【図３】
2011049891.tif 000016
【図４】
2011049891.tif 000017
【図５】
2011049891.tif 000018
【図６】
2011049891.tif 000019
【図７】
2011049891.tif 000020
【図８】
2011049891.tif 000021
【図９】
2011049891.tif 000022
【図１０】
2011049891.tif 000023
【図１１】
2011049891.tif 000024
【図１２】
2011049891.tif 000025
【図１３】
2011049891.tif 000026
【図１４】
2011049891.tif 000027
【図１５】
2011049891.tif 000028
【図１６】
2011049891.tif 000029
【図１７】
2011049891.tif 000030
【図１８】
2011049891.tif 000031
【図１９】
2011049891.tif 000032
【図２０】
2011049891.tif 000033
【図２１】
2011049891.tif 000034