(57)【特許請求の範囲】
【請求項１】
フロー測定を行う複数の測定装置の測定負荷を分散させる負荷分散方法であって、
各測定装置において、
情報収集手段が、経路情報記憶手段を参照して、パス上の自装置ｉに隣接する全隣接測定装置ｊから測定フロー数ｕｊを取得する情報収集ステップと、
サンプルレート算出手段が、自装置のフロー数ｕiと隣接装置ｊのフロー数ｕｊとが平準化するように各パスｐに対するサンプルレートを算出し、該隣接装置ｊに通知すると共に、該サンプルレートを実現するサンプリングのハッシュ範囲を算出し、ハッシュ範囲記憶手段に格納するサンプルレート算出ステップと、
フローサンプリング手段が、到着したパケットのフローキーから得られるハッシュ値が前記ハッシュ範囲記憶手段のハッシュ範囲内である場合には、該フロー情報を測定情報記憶手段に格納するフローサンプリングステップ、
とを行うことを特徴とする負荷分散方法。
【請求項２】
前記サンプルレート算出ステップにおいて、
前記隣接測定装置ｊの測定フロー数ujと自装置のフロー数uiの差異を低減させ、かつ、自装置iの測定フロー数ｕiを隣接測定装置の平均測定フロー数ｕi*に近づくように、自装置iと隣接装置ｊとのフローサンプルレートを設定するレート設定ステップを含み、
前記レート設定ステップは、
隣接測定装置間で測定対象を移動させることで、前記uiが全隣接測定装置の前記ujの平均値ｕi*に更新できる場合には、ｕi*に、できない場合には、最も該ｕi*に近い値に該uiを更新し、かつ、各隣接測定装置の該ujと該uiとの差異が最小化するよう各ujを更新する
請求項１記載の負荷分散方法。
【請求項３】
前記サンプルレート算出ステップにおいて、
前記サンプリングのハッシュ範囲を、自装置とパスｐの経路上で隣接する測定装置間で連続した範囲となるようにハッシュ値の範囲を設定する
請求項１または、２記載の負荷分散方法。
【請求項４】
前記サンプルレート算出ステップにおいて、
一定間隔Ｔの制御周期を設け、各制御周期の開始時点における各パスｐの構成フロー数ｄｐを用いて測定対象フロー数ｕiを算出する処理を、［０：２τ］の一様分布に従うランダムな間隔で反復する
請求項１乃至３のいずれか１項に記載の負荷分散方法。
【請求項５】
フロー測定を行う複数の測定装置の測定負荷を分散させる負荷分散システムであって、
各測定装置は、
経路情報を格納した経路情報記憶手段と、
サンプリングのハッシュ範囲を格納するハッシュ範囲記憶手段と、
前記経路情報記憶手段を参照して、パス上の自装置ｉに隣接する全隣接測定装置ｊから測定フロー数ｕｊを取得する情報収集手段と、
自装置のフロー数ｕiと隣接装置ｊのフロー数ｕｊとが平準化するように各パスｐに対するサンプルレートを算出し、該隣接装置ｊに通知すると共に、該サンプルレートを実現するサンプリングのハッシュ範囲を算出し、前記ハッシュ範囲記憶手段に格納するサンプルレート算出手段と、
到着したパケットのフローキーから得られるハッシュ値が前記ハッシュ範囲記憶手段のハッシュ範囲内である場合には、該フロー情報を測定情報記憶手段に格納するフローサンプリング手段と、
を有することを特徴とする負荷分散システム。
【請求項６】
前記サンプルレート算出手段は、
前記隣接測定装置ｊの測定フロー数ujと自装置のフロー数uiの差異を低減させ、かつ、自装置iの測定フロー数ｕiを隣接測定装置の平均測定フロー数ｕi*に近づくように、自装置iと隣接装置ｊとのフローサンプルレートを設定するレート設定手段を含み、
前記レート設定手段は、
隣接測定装置間で測定対象を移動させることで、前記uiが全隣接測定装置の前記ujの平均値ｕi*に更新できる場合には、ｕi*に、できない場合には、最も該ｕi*に近い値に該uiを更新し、かつ、各隣接測定装置の該ujと該uiとの差異が最小化するよう各ujを更新する
請求項５記載の負荷分散システム。
【請求項７】
前記サンプルレート算出手段は、
前記サンプリングのハッシュ範囲を、自装置とパスｐの経路上で隣接する測定装置間で連続した範囲となるようにハッシュ値の範囲を設定する手段を含む
請求項５または、６記載の負荷分散システム。
【請求項８】
前記サンプルレート算出手段は、
一定間隔Ｔの制御周期を設け、各制御周期の開始時点における各パスｐの構成フロー数ｄｐを用いて測定対象フロー数ｕiを算出する処理を、［０：２τ］の一様分布に従うランダムな間隔で反復する手段を含む
請求項５乃至７のいずれか１項に記載の負荷分散システム。
【請求項９】
請求項５乃至８のいずれか１項に記載の負荷分散システムの測定装置を構成する各手段としてコンピュータを機能させるための負荷分散プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、負荷分散方法及びシステム及びプログラムに係り、特に、フロー分析やDPI(Deep Packet Inspection)等のためにルータにおいてフロー測定を行う際に、各フローが経路上のただ一つの測定装置において測定され、かつ測定装置間の測定負荷が均等化するよう、各測定装置のフローサンプルレートを設定するフロー測定のための負荷分散法及びシステム及びプログラムに関する。
【背景技術】
【０００２】
ISP(Internet Service Protocol)が高い通信品質を維持しつつネットワーク(NW)資源を効率的に運用し、NW設備コストやNW運用コストを低減するためには、NWを流れるトラヒックフローの、サイズ分布、レート分布、交流対地間比率、アプリケーション比率、等の各種統計情報をフロー測定によって得ることで、NWの利用状態をリアルタイムに分析することが重要である。
【０００３】
また近年、トラヒックのアプリケーション識別、ターゲティング広告、異常トラヒックの分別、等の目的で、パケットのペイロードをルータにおいて分析する技術としてDPIが注目されている。フロー測定やDPI等のフロー分析は、集中的に分析を行う集中分析装置に加え、ルータにフローの測定装置を設置し、ルータを流れるフローを測定し得られた情報を定期的に集中分析装置に送信することで実現される。
【０００４】
リンクの回線容量が大容量化するにつれ、各測定装置において全てのフロー状態を管理することが困難になるため、パケット流からパケットを一定周期もしくはランダムに抜き出すパケットサンプリングが、一部のフロー状態のみを管理し各種フロー統計値を得るための方法として有用であり、シスコのNetFlow等、実用化も進んでいる。しかし小サイズのフローが測定されにくく、各ホストが生成するフロー数の分布の分析やDPI等、小サイズのフローに対する測定も必要な場合には、フローを単位にサンプリングを行うフローサンプリングが必要となる。
【０００５】
しかし、フローサンプリングはルータの入力ポートに到着する各パケットのフローIDからハッシュ値を算出することで行われるため、測定装置は回線レートでフロー情報を更新する必要がある。そのためSRAM等の高速で高価なメモリが用いられるため、各測定装置は測定対象を少数のフローに限定する必要がある。ところで測定装置は測定情報を集中分析装置に送るため、各フローは経路上の任意の一つの測定装置において測定されれば十分であり、複数の測定装置で重複して測定することは無駄となる。測定装置の限られたメモリ資源を効率的に活用し、NW全体の総測定フロー数を最大化するには、各測定装置の測定対象フローを適切に選定することが重要である。すなわち各フローが経路上の唯一つの測定装置によってのみ測定され、かつNW全体の総測定フロー数を最大化するには、各測定装置の負荷が最大限、測定装置間で分散されるよう測定対象を選択することが重要である。
【０００６】
これまでにルータにおいてフローを測定する場合の負荷分散法が検討されている。これらの方式は、測定箇所を設計するもの、フローの経路を設定するもの、各測定装置の測定対象フローを設定するもの、に分類できる。
【０００７】
NWトポロジと各トラヒックフローの要求帯域と経路が与えられ、全ノードに測定装置が設置可能である場合に、全てのフローが一つ以上の測定装置を経由することを条件に設置測定装置数が最小となる問題は集合被覆問題(minimum set cover problem)として知られている。測定箇所を設計するアプローチでは、全トラヒックの中で任意に定めた比率ｋのトラヒックが測定されることを条件に、設置測定装置数を最小とする集合被覆問題を解く近似アルゴリズムを提案している。また同様の集合被覆問題を、さらに各フローの測定割合から定まる効用関数と、各ノードに測定装置を設置するコストとが与えられた場合に、総コストもしくは総効用の一方を制約条件として他方を最適化するよう、測定装置の設置個所と各測定装置の各フローに対するサンプルレートとを最適設計する近似アルゴリズムを提案している。また同様の入力条件に対して、NW全体の総サンプルパケット量が制約上限を超えない範囲で、測定効用の総和を最大化するよう測定装置の設置個所と各測定装置の各フローに対するサンプルレートとを最適設計する問題を、非線形計画問題として定式化している。
【０００８】
一方、フローの経路を設定するアプローチでは、測定装置の負荷を平準化するフローの経路設定法を提案している。NWトポロジ、測定装置の設置個所と各々におけるサンプルレート、フローの集合、各フローを測定することで得られる効用、各発着ノード間のトラヒックエンジニアリング(TE)のポリシィが与えられている時に、TEポリシィを維持することを条件に、測定によって得られる効用の総和を最大化するよう、各発着ノード間の一部のトラヒックに対する経路を設定する。
【０００９】
また、各測定装置の測定対象フローを設定するアプローチでは、全てのルータに測定装置が設置され経路が与えられている場合に、各測定装置が測定対象とするフローを適切に設定することで測定装置の負荷分散を図る方法が検討されている。ある方式では、各ルータにおいて到着パケットが測定対象フローか否かの判断をCounting Bloom filter(CBF)を用いて行い、NW上の全てのルータ間でCBFの情報を交換し、パケットが到着するごとにNW上の全ルータのCBFをチェックすることで、到着パケットがどのルータでも未測定の新規のフローに属している場合には新たに測定対象とする。
【００１０】
また、ある方式では、NW上に複数の制御装置(RP: rendez-vous point)を設置し、各測定装置は新しいフローを検出するごとにフローIDから一意に決まるRPにフロー検出を通知し、RPは最初に通知を受けた測定装置、もしくは通知を受けた測定装置の中で負荷が最小の測定装置に対して測定を指示することで、測定の重複を避けることを提案している。
【００１１】
また、ある方式では、全対地間の交流トラヒック行列、経路、各測定装置の処理容量Ｌ、各フローの測定割合の下限値αが与えられたときに、Ｌとαの制約を考慮しつつ、NW全体での測定フロー数を最大化する問題を線形計画問題として定式化し、集中制御的に各測定装置の各対地間フローに対するサンプルレートを最適設計することを提案している（例えば、非特許文献1参照）。
【先行技術文献】
【非特許文献】
【００１２】
【非特許文献１】V. Sekar, M. Reiter, W. Willinger, H. Zhang, R. Kompella, and D. Andersen, "cSamp: A System foro Network-Wide Flow Monitoring," USENIX NSDI 2008.
【発明の概要】
【発明が解決しようとする課題】
【００１３】
測定箇所を設計するアプローチは、いずれも測定装置の設置場所の設計を目的としており、常に変化するトラヒックフローに対してリアルタイムな最適化を図ることができない。フローの経路を設定するアプローチは、各ノードに対して、同一対地間に明示的な複数のパスを設定する機能が必要となる。さらに最適化問題を解く必要があり、大規模NWに対するスケール性が問題である。
【００１４】
各測定装置の測定対象フローを設定するアプローチのうち、CBFを用いて各ルータが自律的な制御を行うものは、全ルータ間でCBFの情報を交換する必要があり、またパケット到着ごとに全CBFをチェックする必要があり、処理負荷が大きい。また測定の重複は避けられるものの、測定装置負荷の分散化については考慮されておらず、負荷分散に関して最適化が図られない。
【００１５】
また、RPを用いるものは、任意の測定装置の測定対象が変化するごとに測定装置とRPとの間で制御パケットを交換する必要があり、そのための処理コストが問題である。また一旦、割当てた測定装置を変えることができないため、十分な負荷分散効果が期待できない。
【００１６】
また、集中制御的にサンプルレートを最適化するものは、常に変化する交流トラヒック行列に対応するためには短時間周期で集中的に最適化問題を解く必要があるため、NW規模の増大に伴い処理時間が急激に増加しスケール性に問題がある。また交流トラヒック行列を推定するコストも問題である。
【００１７】
本発明は、上記の点に鑑みなされたもので、あるフローが一つの測定装置で測定されることを可能とし、全体の測定装置間の測定負荷が均等化するよう制御することが可能な負荷分散方法及びシステム及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１８】
上記の課題を解決するため、本発明は、フロー測定を行う複数の測定装置の測定負荷を分散させる負荷分散方法であって、
各測定装置において、
情報収集手段が、経路情報記憶手段を参照して、パス上の自装置ｉに隣接する全隣接測定装置ｊから測定フロー数ｕｊを取得する情報収集ステップと、
サンプルレート算出手段が、自装置のフロー数ｕiと隣接装置ｊのフロー数ｕｊとが平準化するように各パスｐに対するサンプルレートを算出し、該隣接装置ｊに通知すると共に、該サンプルレートを実現するサンプリングのハッシュ範囲を算出し、ハッシュ範囲記憶手段に格納するサンプルレート算出ステップと、
フローサンプリング手段が、到着したパケットのフローキーから得られるハッシュ値が前記ハッシュ範囲記憶手段のハッシュ範囲内である場合には、該フロー情報を測定情報記憶手段に格納するフローサンプリングステップ、とを行う。
【発明の効果】
【００１９】
以上説明したように、本発明によれば、フロー分析やDPI等のためにルータにおいてフロー測定を行う際に、各フローが経路上のただ一つの測定装置において測定され、かつ測定装置間の測定負荷が均等化するよう、各測定装置のフローサンプルレートを設定することができる効果がある。なお、詳細な評価については後述する。
【図面の簡単な説明】
【００２０】
【図１】本発明の一実施の形態における測定装置の構成図である。
【図２】本発明の一実施の形態における各測定装置の制御シーケンスである。
【図３】本発明の一実施の形態におけるαgとαsの設定値とｕ'iをプロットした例である。
【図４】トポロジの例である。
【図５】評価結果を示す図（その１）である。
【図６】評価結果を示す図（その２）である。
【図７】評価結果を示す図（その３）である。
【図８】評価結果を示す図（その４）である。
【図９】評価結果を示す図（その５）である。
【図１０】評価結果を示す図（その６）である。
【図１１】評価結果を示す図（その７）である。
【発明を実施するための形態】
【００２１】
以下図面と共に、本発明の実施の形態を説明する。
【００２２】
図１は、本発明の一実施の形態における測定装置の構成を示す。
【００２３】
同図に示す測定装置ｉは、サンプルレート算出部１０１、経路情報記憶部１０２、隣接測定装置との間で通信を行う通信部１０３、サンプリングのハッシュ範囲を格納するハッシュ範囲記憶部１０４、フローサンプリング部１０５、フローサンプリング部１０５により抽出されたフロー情報を格納する測定情報記憶部１０６から構成される。
【００２４】
サンプルレート算出部１０１は、OSPF（Open Shortest Path First）等のリンク状態型プロトコルにより生成及び管理される経路情報記憶部１０２を参照し、各隣接測定装置ｊと測定装置ｉの両方を経由するパスに対するサンプルレートを算出する。そのために、まず通信部１０３を介して、各隣接測定装置ｊに対して、測定フロー数ujの通知を依頼する。本通知を受けた隣接測定装置ｊは、ujに関する情報を測定装置ｉに通知する。このようにしてサンプルレート算出部１０１は全隣接測定装置のujを収集し、これと自身のuｉとが平準化するよう各パスｐに対するサンプルレートを算出する。さらに算出したサンプルレートを実現するサンプリングのハッシュ範囲を算出し、サンプリングのハッシュ範囲記憶部１０４に記憶する。このような処理を測定装置ｉは、［０：２τ］の範囲のランダムな時間間隔で実行する。一方、測定装置ｉが設置されたルータｉにパケットが到着する度に、到着パケットのフローキーから得られるハッシュ値が、サンプリングのハッシュ範囲記憶部１０４に記憶された範囲である場合には、フローサンプリング部１０５において、該当パケットが属するフローの情報を測定情記憶部１０６に記憶する。
【００２５】
図２は、本発明の一実施の形態における各測定装置の制御シーケンスである。
【００２６】
一定間隔Ｔの制御周期を設け、サンプルレート算出部１０１において、各制御周期の開始時点における各パスｐの構成フロー数ｄｐを用いて算出される測定対象フロー数uｉを、NW上のＮの全測定装置間で、各測定周期内で均等化する。各測定装置ｉは、[０：２τ]の一様分布に従うランダムな間隔で、負荷調整処理を反復し、事前に決められた回数Ｋだけ反復した時点で、その制御周期内の負荷調整処理を終了する。そして新しい制御周期が始まった時点で、同様の処理を反復する。
【００２７】
［１］重複を回避した測定対象選択法
まず、フローサンプリングにおいて、同一のフローが複数の測定装置で測定されることを回避する方法について述べる。
【００２８】
ここでは、単一のISPが運用する全ルータに測定装置が設置されたＮ個のルータ(ノード)から構成されるNWを考える。またパケットの転送経路としてOSPFやIS-IS(Intermediate System to Intermediate System)のリンク状態型ルーティングプロトコルを想定し、各発着ノード間を流れるパケットの集合をパスｐ、発着IPアドレスと発着ポート番号が同一のパケットの集合をフローと呼ぶ。各パスｐは複数のフローから構成され、同一のパスｐに属するフローは全て同一の経路を通ることを想定する。
【００２９】
任意の長さｋビットのハッシュ空間を有するハッシュ関数ｈをハッシュ範囲記憶部１０４に用意し、フローサンプリング部１０５において、ルータに到着したパケットが属するフローのフローキーｘから得られるハッシュ値ｈ（ｘ）が閾値ａ*未満である場合にのみ新規フロー判定処理を行えば、フローを単位としたサンプリングが実現できる。但し、フローサンプルレートをｒとすると、閾値はa*=r2kである。同一フローに属するパケットは全て同一のフローキーを持ち同一のハッシュ値が得られるため、フローのサイズやレートとは無関係に、全てのフローは一様に確率ｒでサンプルされる。
【００３０】
ルータｎに設置された測定装置ｎに対してハッシュ値の下限LL(n,p)と上限UL(n,p)を定め  パスｐのフローに対して、フローキーｘのハッシュ値が［LL(n,p)：UL(n,p)］の区間に入る場合にのみ測定対象とする。測定装置ｎのパスｐに対するフローサンプルレートｒｎ（ｐ）は、
ｒn(p)=[UL(n,p)−LL(n,p)]／2k
となる。パスｐの発着ノードを含めた経由ルータ数をｈｐ、パスｐの経由ルータを
【００３１】
【数１】
0005436474.tif 000002
とするとき、これらhp個の測定装置nの間でハッシュ区間が重複しないよう、LL(n,p)とUL(n,p)を設定することで、パスｐに属するフローを重複することなく測定できる。さらにこれら測定装置のハッシュ区間の総和がハッシュ値の全領域に一致するようハッシュ区間を定めることで、パスｐの全てのフローを測定できる。
【００３２】
全てのフローを重複することなく測定する各測定装置のハッシュ区間の簡易な設定法として、
(i)  INM(ingress node measurement)，
(ii)EDM(equally divided measurement)
の二つの方法が考えられる。
【００３３】
(i)  発ノード測定法：INM(ingress node measurement)
パスｐの発ノードＲp,1においてｐに属する全てのフローを測定する。すなわち測定装置Rp,1に対しては、
LL(R p,1,p)＝０，
UL(R p,1,p)=2k
に設定し、他の測定装置R（２≦i≦ｈｐ）に対しては、
LL(R p,1,p)＝UL(R p,1,p)=０
に設定する。
【００３４】
(ii)均等分割測定法：EDM(equally divided measurement)
パスｐ経由する全ての測定装置間で均等にハッシュ区間を分割する。すなわち１≦ｉ≦hpの各測定装置Ｒp,1に対して、
LL(Rp,1，p)＝(i-1)2ｋ／hp，  UL(R p,1，p)＝i2ｋ／hp
に設定する。パスｐの経路上の各測定装置ｎのパスｐに対するフローサンプルレートは、
ｒn (p)=1/hp
となる。
【００３５】
［２］測定装置の自律的負荷分散法：
上記の［１］で述べたINMやEDMを用いることで全フローを重複なく測定できるが、測定負荷分散は図られない。つまり、従来の課題を解決することができない。各ルータを経由するフロー数が均一で、かつ、各ルータを経由するパスの平均ホップ長が同一である場合には、EDMは測定装置間の負荷を均一化するが、実際にはこのような状況は生じ得ない。
【００３６】
以下に、本発明のフロー測定のための自律的負荷分散法について述べる。
【００３７】
１．制御の概念
ノードｉに設置された測定装置ｉは，最大でＣi本のフローを測定可能とする。さらに、当明細書中ではＮの全測定装置の処理容量は同一でＣi＝Ｃとする。ノードｉの測定フロー数をｕi、ノードｉの隣接ノードの集合Ａi、測定装置Ａiの測定フロー数の平均をｕi
【００３８】
【数２】
0005436474.tif 000003
とする。本明細書では、以下に示すような各測定装置ｉの自律的な負荷調整を考える。
【００３９】
＜測定装置ｉの自律的な負荷調整＞
測定装置ｉのサンプルレート算出部１０１は、全ての隣接測定装置ｊ（ｊ∈Ａi）のみから測定フロー数ujの情報を収集し、測定装置ｉと隣接測定装置ｊの両方を経由する任意のパスｐに対する測定装置ｉの測定対象の一部を測定装置ｊに移すか、もしくは測定装置ｊの測定対象の一部を測定装置ｉに移すよう、これら測定装置のパスｐに対する測定ハッシュ区間を更新し、通信部１０３を介して隣接測定装置ｊに通知する。
【００４０】
上記の自律的負荷調整を、以下のポリシィに基づき各測定装置において自律的に反復実施することで、NW全体での測定装置の負荷分散を図る。
【００４１】
（１）隣接測定装置ｊの測定フロー数ｕjと測定装置ｉの測定フロー数ｕiとの差異を可能な限り低減：
（２）測定装置ｉの測定フロー数ｕiを，隣接測定装置の平均測定フロー数
【００４２】
【数３】
0005436474.tif 000004
に可能な限り誘導：
次に本制御ポリシィを実現する具体的方法を述べる。
【００４３】
＜移動測定対象量の算出法＞
測定装置ｉの隣接測定装置ｊの中で、ｕj＞ｕiの集合を
【００４４】
【数４】
0005436474.tif 000005
ｕj＜ｕiの集合
【００４５】
【数５】
0005436474.tif 000006
と定義する。制御ポリシィ(１)を実現するため、
【００４６】
【数６】
0005436474.tif 000007
の隣接測定装置ｊの測定対象フローの中でｘij本のフローを測定装置ｉの測定対象に移す。反対に測定装置ｉの測定対象フローの中でｘij本のフローを、
【００４７】
【数７】
0005436474.tif 000008
の隣接測定装置ｊの測定対象に移す。但し、ｘij≦ｕj−ｕi，ｘij≦ｕi−ｕjを満たす範囲でｘji とｘijを設定する。
【００４８】
ノードｉとｊの両方を経由するパスｐの集合をＢij、パスｐを構成するフロー数をｄｐとする。このとき、測定装置ｉ（ｊ）から測定装置ｊ（ｉ）に移すことが可能な測定対象フロー数ｙij（ｙji）は次式で得られる。
【００４９】
【数８】
0005436474.tif 000009
リンク状態型ルーティングプロトコルによりNW全体の経路情報が各ルータで管理されるため、測定装置ｉは自身を経由するパスの経由ノードを把握でき、他の測定装置と情報を新たに交換することなくＢijを得ることが可能である。
【００５０】
ｘjiとｘijの取りえる最大値をzij、ｚjiとすると、
ｚji＝min{uj−ｕi}，ｚij＝min{u i−ｕｊ}
となる。ここで0から1の範囲の値をとる実数パラメタαｇとαｓを導入し、
【００５１】
【数９】
0005436474.tif 000010
の隣接測定装置ｊに対してはｘij＝αｇｚjiに、
【００５２】
【数１０】
0005436474.tif 000011
の隣接測定装置ｊに対してはｘij＝αｓｚijに設定する。
【００５３】
ZｇとZｓを各々
【００５４】
【数１１】
0005436474.tif 000012
と定義すると、測定装置ｉの自律的負荷調整処理後の、測定装置ｉの測定フロー数ｕi'は、
ｕi'＝ ｕi＋αｇZｇ−αｓZｓ
となるが、
【００５５】
【数１２】
0005436474.tif 000013
となる場合には、
【００５６】
【数１３】
0005436474.tif 000014
が得られる、但し、
【００５７】
【数１４】
0005436474.tif 000015
である。０≦αｓ≦１と（２）より、
【００５８】
【数１５】
0005436474.tif 000016
が成立するためには、αｓは
−δ／Zｇαｓ≦（Zｓ−δ）／Zｇ
を満たす必要がある。さらに、０≦αｇ≦１であるため、
【００５９】
【数１６】
0005436474.tif 000017
が成立するための条件は、
−Zｇ≦δ≦Zｓ                                        （３）
となる。この条件が満たされるとき、αｇとαｓの設定可能な上限値
【００６０】
【数１７】
0005436474.tif 000018
は、（２）（１）より、
【００６１】
【数１８】
0005436474.tif 000019
となる。制御ポリシィ(1)よりαｇとαｓは大きなことが望ましいので、
【００６２】
【数１９】
0005436474.tif 000020
に設定する。
【００６３】
次に（３）が満たされない場合について考える。まず、δ＜−Zｇの場合、ｕiが
【００６４】
【数２０】
0005436474.tif 000021
と比較して小さく、測定装置ｉの測定対象を
【００６５】
【数２１】
0005436474.tif 000022
の隣接測定装置ｊに移すことができないため、αｓ＝０に設定し、制御ポリシィ(２)より
αｇ＝１に設定する。このとき、
【００６６】
【数２２】
0005436474.tif 000023
となる。一方、δ＞Zｓの場合、ｕiが
【００６７】
【数２３】
0005436474.tif 000024
と比較して大きく、
【００６８】
【数２４】
0005436474.tif 000025
の隣接測定装置jの測定対象を測定装置iに移すことができないためαｇ＝０に設定し、制御ポリシィよりαｓ＝１に設定する。このとき、
【００６９】
【数２５】
0005436474.tif 000026
となる。
【００７０】
図３に、uに対して、αｇとαｓの設定値とｕi'を各々プロットした例を示す。
【００７１】
＜フローサンプリングのハッシュ範囲の算出法＞
次に、サンプルレート算出部１０１におけるフローサンプリングのハッシュ範囲を求める方法について説明する。
【００７２】
測定装置iとその隣接測定装置ｊ間でxjiもしくはｘijの測定対象フローの移動は、フローサンプリングのハッシュ範囲LL（i，p），UL(i，p)，LL(ｊ，p)，UL(ｊ，p)を更新することで実現される。ここでは、これらのハッシュ範囲の更新法について述べる。
【００７３】
まず、
【００７４】
【数２６】
0005436474.tif 000027
の測定装置ｊから測定装置ｉにｘjiの測定対象フローを移す場合を考える。ｙji≦uｊ−ｕｉの場合には、測定装置ｊにおけるｐ∈Ｂijの各パスｐのフローに対するサンプルレートを（１−αｇ）倍にして、減少分であるαｇｒｊ（ｐ）の比率のフローを測定装置ｉで測定すればよいので、測定装置ｉとｊの更新後のサンプルレートｒ'i（ｐ）とｒ'ｊ（ｐ）を各々
【００７５】
【数２７】
0005436474.tif 000028
とすればよい。よって各々の測定装置のハッシュ範囲を、測定装置ｊが測定装置ｉよりもパスｐの上流に存在する場合には、
【００７６】
【数２８】
0005436474.tif 000029
に更新し、下流に存在する場合には、
【００７７】
【数２９】
0005436474.tif 000030
に更新する。このように隣接測定装置で同一パスに対して連続したハッシュ区間を割り当てることで、パスｐの経路上の測定装置ｉからみて２ホップ以上離れた測定装置のハッシュ範囲に影響を与えることなく、測定装置ｉとｊのハッシュ範囲の変更が可能である。
【００７８】
一方、ｙij＞uｊ−ｕｉの場合には、βｇ(j)=αｇ（ｕｊ−ｕｉ）/ｙji定義すると、
【００７９】
【数３０】
0005436474.tif 000031
に更新すればよい。各々の測定装置のハッシュ範囲の更新は、αｇをβｇ（ｊ）に置き換えた上記更新式（８）、（９）を用いる。
【００８０】
また、
【００８１】
【数３１】
0005436474.tif 000032
の測定装置ｊに測定装置ｉからｘijの測定対象フローを移す場合についても同様に、ｙij≦ｕｉ−ｕｊの場合には、
【００８２】
【数３２】
0005436474.tif 000033
に更新すればよく、測定装置ｊが測定装置ｉよりもパスｐの上流に存在する場合には、
【００８３】
【数３３】
0005436474.tif 000034
に更新し、下流に存在する場合には、
【００８４】
【数３４】
0005436474.tif 000035
に更新する。
【００８５】
ｙij＞ｕｉ−ｕｊの場合には、βs(j)=αs（ui-uj）/yijを用いて
【００８６】
【数３５】
0005436474.tif 000036
に更新すればよく、やはりハッシュ範囲の更新はαｓをβｓ（ｊ）に置き換えた上記の更新式(１２)、（１３）を用いる。
【００８７】
＜処理シーケンス＞
一定間隔Ｔの制御周期を設け、各制御周期の開始時点における各パスｐの構成フロー数ｄｐを用いて、
【００８８】
【数３６】
0005436474.tif 000037
より算出される測定対象フロー数uｉを、ＮＷ上のＮの全測定装置間で、各測定周期内で均等化する。但し、Pｉはノードｉを経由するパスの集合である。各測定装置ｉは、［0．2：τ］の一様分布に従うランダムな間隔で、以下の処理シーケンスに従う自律的な負荷調整処理を、予め決められた回数Ｋだけ反復する。
【００８９】
図４は、本発明の一実施の形態における自律的負荷分散装置の動作のフローチャートである。
【００９０】
ステップ１０１）  隣接測定装置の測定フロー数情報の収集：
各隣接測定装置ｊ（ｊ∈Ａi）に対して、測定装置ｉのサンプルレート算出部１０１は、測定フロー数ｕｊに関する情報を得るため、通信部１０３を介して、クエリパケットを送付する。クエリパケットを受信した各隣接測定装置ｊは、現在のサンプルレートｒｊ(p)と現在の制御周期の開始時点の構成フロー数ｄｐを用いて式（１４）より算出される測定フロー数uｊを、測定装置ｉに通知する。
【００９１】
ステップ１０２）  フローサンプリングのハッシュ区間の算出：
測定装置ｉのサンプルレート算出部１０１は、前述の＜移動測定対象量の算出法＞＜フローサンプリングのハッシュ範囲の算出法＞に記載した方法を用いて、各隣接測定装置ｊ、とのＢijに含まれる全てのパスｐに対する測定装置ｉとｊのハッシュ区間を算出する。
【００９２】
ステップ１０３）  ハッシュ区間の通知と更新：
測定装置ｉは各隣接測定装置ｊに算出したハッシュ区間を通知する。また、測定装置ｉのサンプルレート算出部１０１は、ハッシュ範囲記憶部１０４のハッシュ区間を更新する。
【００９３】
［測定負荷の安定性］
各測定装置が自律的に隣接測定装置間と負荷を調整した場合、各測定装置の測定負荷が増減を繰り返し、各測定装置の測定負荷が不安定となる可能性がある。しかし本発明においては，測定負荷の安定性に関して以下の定理が成立するため、時間の経過に伴い測定装置間の測定負荷の差異は減少し、不安定となることはない。
【００９４】
・定理： 最大・最小負荷の単調性
全ての測定装置の測定負荷の最大値をｕmax，最小値をuminとすると、定装置の自律的な負荷調整の結果、ｕmaxは非増加、uminは非減少となる。
【００９５】
（証明）
測定装置ｉか、その隣接測定装置ｊ∈Ａi（測定装置ｘとする）の負荷がｕmaxである場合，測定装置ｉの負荷調整の結果u'x≦ｕxとなるが、測定装置ｘの負荷が新しい最大負荷ｕ'maxとなるか、もしくは他の測定装置ｙの負荷がｕ'maxとなる。前者の場合、明らかにｕ'max≦ｕmaxであり、また後者の場合も更新前の状態においてuy<uxであるため、ｕ'max≦ｕmaxとなる。同様に測定装置ｉか、その隣接測定装置ｊ∈Ａi（測定装置ｘ）の負荷がuminである場合、測定装置ｉの負荷調整の結果、ｕ'min≧ｕminとなる。
【００９６】
一方、測定装置ｉもしくはその隣接測定装置Ａｉの全ての負荷がｕmaxやｕminでない場合、測定装置ｉの負荷調整の結果、ｕmaxとuminは変化しない。以上のことから、任意の測定装置の自律的な負荷調整の結果、ｕmaxは非増加、uminは非減少となる。
【００９７】
［性能評価］
以下に本発明の性能評価を示す。
米国の学術バックボーンNWであるInternet2のPoPレベルのNWトポロジを対象に性能評価を行う。図５にトポロジを示す。11の各ノードペアi j間の5分間の各測定区間ｔ内の転送トラヒック量νij,t(bits)に関しても公開されているが、ここでは2004年3月1日から一週間にわたる5分間ごとの交流トラヒック行列を評価に用いる。
【００９８】
図６（ａ）に、5分間の各測定区間tにおける全ノード間の交流トラヒック量の総和Vt（bit）を7×24×12=2016個の全ての測定区間にわたるVtの平均値V(bits)で除して正規化した値εt＝Vt/Vの時系列をプロットする。ただしVtにおいては同一ノードを発着とするトラヒックは除いた。総トラヒック量は一日を周期に大きく変動していることが確認できる。ただし最後の二日間は週末に当たり、平日と比較してトラヒック量が少ない。また一日目の9時〜二日目の1時の間、三日目の9時〜四日目の1時の間、5日目の9時ごろに、突発的なトラヒックの増加が見られる。
【００９９】
また図６（ｂ）に、七日間の総トラヒック量が大きい上位三つの発着ノード間のトラヒック量の時系列を同様にプロットする。第三位の発着ノード間のトラヒック量には、図６(a)で突発的な増加が観測された時点のいくつかと同じ時点で、やはり突発的にトラヒック量が増加している。
【０１００】
各パスの経路としては、公開されているリンク重みを用いた最小コスト経路を想定する。図６（ｃ），（ｄ）に、11の各ノードを経由する各測定区間tにおけるトラヒック量をVtで除して正規化した値の時系列をプロットする。各ノードの経由トラヒック量比率は細かく変動しているものの大きくは変化せず、各ノードの経由トラヒック量の順位は全期間を通してほぼ一定である。ただし図６（ａ）において突発的なトラヒック量が観測された時点においては、一部のノードで経由トラヒック量が突発的に増加している。
【０１０１】
Internet2における各測定区間tにおける各パスpの実測交流トラヒック行列νp,tの相対値をψp,tとし(ψp,t=νp,t/Vt)、全てのパスｐの平均フローサイズと平均フローレートは同一であり、各測定区間tにおける各パスｐの平均同時フロー数はψp,tに比例すると仮定する。そして任意に与えた実数パラメタφを用いて、各測定区間tにおけるパスｐの構成フロー数ｄp,tを
【０１０２】
【数３７】
0005436474.tif 000038
で与える。φはNW全体のトラヒック量のスケールを規定するパラメタで、NW全体の5分間のトラヒック量が一週間の平均値Vとなるときの全フロー数の、各測定装置の最大測定可能フロー数Cに対する倍率に相当する。以後、特に断らない限りφ＝Nに設定する。
【０１０３】
提案方式(ALB: autonomic load balancing)を各測定区間に対して適用し、KN回の負荷調整を実行させる。各測定装置は平均K回の負荷調整を各測定区間内で行う。また、負荷調整終了時点のサンプルレートｒi(p)の値を次の測定区間の開始時点のｒi(p)として用いる。ただし最初の測定区間の開始時点においては、EDMによって算出したｒi(p)を用いる。
【０１０４】
・本発明の最大負荷低減効果：
図７に各測定区間ｔの、(a)開始時点、(b)10Nの負荷調整終了時点、(c)100Nの負荷調整終了時点、(d)1000Nの負荷調整終了時点、の測定装置の測定負荷の最大値ｕmaxを平均測定負荷
【０１０５】
【数３８】
0005436474.tif 000039
で除した値(正規化最大負荷)を各々、時系列としてプロットする。多くの測定区間において最大負荷の平均負荷に対する倍率は初期時点では1.05〜1.4倍であるのに対して、各測定装置が平均K=10回の負荷調整を行った時点で大きく低下し、多くの測定区間において平均負荷と近くなる。さらにK=100の時点では、ほぼ全ての測定区間において最大負荷は平均負荷と一致し、K=1000の状態との差異は小さい。しかしいくつかの測定区間においては、K=1000時点も最大負荷が平均負荷と比較して依然として大きい。
【０１０６】
図８（a）に、各測定区間の開始時点と10N、100N、1000Nの負荷調整終了時点における正規化最大負荷の累積補分布(CCD)をプロットする。多数の測定区間において、各測定装置がK=10の負荷調整を行った時点で最大負荷は大きく低減し、効果的な負荷分散が実現される。しかしK=1000、1000となった時点においても、さらなる負荷分散効果の向上は小さいが、約96%測定区間において最大負荷は平均負荷に一致し、完全な負荷分散が実現される。また図８（ｂ）に、各測定区間においてK=1000の時点の最大負荷の100.1％の大きさまで最大負荷が低減するのに必要なKの値をプロットする。多くの測定区間において、各測定装置は10回程度未満の負荷調整で、1000回反復したときの99.9％の最大負荷低減効果が得られる。
【０１０７】
ところで図７，８で確認されるように、少数の測定区間においてはALBの効果が小さく、最大負荷が平均負荷と比較して依然と大きい。その理由を調べるため図９（a）に、各測定区間tにおけるK=1000の正規化最大負荷を、隣接ノードij間の交流トラヒック量νij,tの最大値をVt_で除した値に対してプロットする。7つの測定区間において、ALB適用後の正規化最大負荷が1.1以上と大きくALBの効果が見られないが、これらの測定区間においてはいずれも最大隣接ノード間トラヒック量比率が大きい。評価に用いたInternet2のトポロジとリンクコストにおいては、隣接ノードij間のトラヒックはノードij間のリンクを経由して直接転送されるため、ノードijを発着とするトラヒックは測定装置iかjのいずれかにおいてのみ測定可能となる。そのため隣接ノードij間のトラヒック量比率が高い場合、測定装置ｉとｊの測定負荷を低減できない。隣接ノード間トラヒック量比率が0.15以上の10のいずれの測定区間においても、ノード7(New York)とノード10(Washington DC)間のトラヒック量比率が最大であり、これらノードの測定負荷を低減することができず、ALBの効果が小さい。
【０１０８】
また図９（ｂ）に、各測定区間tにおけるK=1000の正規化最大負荷を、測定区間ｔ−１の各対地間の相対トラヒック量と測定区間tの各対地間の相対トラヒック量との相関係数に対してプロットする。連続する測定区間でトラヒック交流パタンが大きく変化し、対地間の相対トラヒック量の前測定区間との相関係数が小さい測定区間においても、ALBの負荷分散効果は高い。負荷の平準化が不可能な、隣接ノード間のトラヒック量比率が大きな場合を除き、ALBは少数の負荷調整処理の反復で効果的に最大負荷を低減でき、全ての測定装置の負荷が均等化した完全な負荷分散状態を実現できる。
【０１０９】
・他方式との性能比較：
ALBを用いたK=20における正規化最大負荷と各測定装置の負荷の標準偏差を、上記の[重複を回避した測定対象選択法]で述べた二つの方式EDM、INMと比較する。ただし[本発明の最大負荷低減効果：]で述べたように、ALBは少数の負荷調整処理で効果的な負荷均等化効果が得られることからK=20に設定する。三つの各方式の、各測定区間の正規化最大負荷と測定装置間の測定負荷の標準偏差(SD)の時系列を、図１０（ａ），（ｂ）に各々プロットする。[本発明の最大負荷低減効果：]でも確認したようにALBの正規化最大負荷はほとんどの測定区間において1であるのに対して、EDMは1.5〜1.8程度、INMは2〜3程度となる。また測定負荷の標準偏差はALBがほとんどの測定区間で0であるのに対して、EDMは0.025〜0.05、INMは0.05〜0.08程度となる。EDMやINMを用いた場合、特定の測定装置への負荷集中が避けられない。
【０１１０】
ところで各測定装置iは最大容量Cを超える数のフローを測定することができず、測定フロー数uｉはC上限が抑えられる。そのため各パスPフロー数dp,t与えられたとき、測定区間tにおいてNW全体で測定されるフロー数Wtはri(p)に依存する。そこでWtを測定区間ｔのNW全体の総フロー数εtφCで除した値を測定フロー数比率ζｔと定義し、ζｔを用いて測定負荷の均等化効果を評価する。
【０１１１】
ALB、EDM、INMを用いた場合、測定区間t内で測定装置iにおいて測定されるフロー数は
【０１１２】
【数３９】
0005436474.tif 000040
となる。よってζｔは次式で得られる。
【０１１３】
【数４０】
0005436474.tif 000041
また測定装置間で測定対象の調整を行わず、各測定装置において、経由フロー数がC以下である場合には全ての経由フローを測定し、Cを超える場合にはC本のフローをランダムに測定対象として選択した場合(NSM: naive sampled measurement)と比較する。NSMのζｔはPを全てのパス集合、Rpをパスｐが経由するノード集合とすると、次式で得られる。
【０１１４】
【数４１】
0005436474.tif 000042
図１１（ａ）に4つの各方式におけるεtの時系列をプロットする。φ＝Nに設定しているため、εｔ＝１の測定区間において完全な負荷分散が実現されたときに（ｕmax ＝uav）、ζｔ＝１となる。εｔ＜１の測定区間においては、負荷分散が不完全であっても（ｕmax ＝uav）、全測定装置において測定負荷がC以下となりζｔ＝１となる可能性がある。ALBにおいてはεｔ＜１の多数の測定区間においてζｔ＝１となるのに対して、EDMではごく一部の測定区間においてのみζｔ＝１となっており、INMとNSMでは全ての測定区間においてζｔ＜１となる。ALBを用いることで平均して、NSMに対して50％程度、INMに対して20％程度、EDMに対して15％程度、ζｔを向上可能である。
【０１１５】
また図１１（ｂ）にφを変化させたときの、2016の全測定区間に亘る各方式のζｔの平均値を、φ/Nの値に対してプロットする。φの増加に伴いNW全体のフロー数が増加するためζｔが減少するが、φ＝N付近で急激に減少する。またNSMは他の三つの方式と比較してζｔの劣化度合いが大きい。ALBはφの全領域において他の方式と比較して有効であるが、特にφ＝Nの近辺において有効性が高い。
【０１１６】
なお、上記の自律負荷分散装置（測定装置）の図２に示す構成要素の動作をプログラムとして構築し、自律負荷分散装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【０１１７】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【符号の説明】
【０１１８】
１０１  サンプルレート算出部
１０２  経路情報記憶部
１０３  通信部
１０４  ハッシュ範囲記憶部
１０５  フローサンプリング部
１０６  測定情報記憶部
【図１】
0005436474.tif 000043
【図２】
0005436474.tif 000044
【図３】
0005436474.tif 000045
【図４】
0005436474.tif 000046
【図５】
0005436474.tif 000047
【図６】
0005436474.tif 000048
【図７】
0005436474.tif 000049
【図８】
0005436474.tif 000050
【図９】
0005436474.tif 000051
【図１０】
0005436474.tif 000052
【図１１】
0005436474.tif 000053