JP4586710B2

JP4586710B2 - 計測端末及びネットワーク輻輳区間推定システム

Info

Publication number: JP4586710B2
Application number: JP2005323450A
Authority: JP
Inventors: 敦士田上; 輝之長谷川; 茂浩阿野
Original assignee: KDDI R&D Laboratories Inc
Current assignee: KDDI Research Inc
Priority date: 2005-07-27
Filing date: 2005-11-08
Publication date: 2010-11-24
Anticipated expiration: 2025-11-08
Also published as: JP2007060611A

Description

本発明は、トラフィックを直接計測することが困難なネットワークの輻輳区間の推定に関する。

ネットワークのトラフィックを、直接計測することが困難な環境において、ネットワークの輻輳箇所を推定するためには、複数のパスに対して、アクティブ計測により、遅延又は損失等のパス品質を計測し、前記計測結果からネットワーク内部の輻輳箇所を推定する手法が必要となる。ここで、パスとは、ネットワークに接続された端末から、他の端末にパケットを送信した場合に、前記パケットが通るルートを意味し、前記ルート上には、ルータ等の中継ノードが複数存在する。また。アクティブ計測とは、ネットワークに接続している端末から試験用パケットを他の端末に送出し、他の端末で受信される前記試験用パケットの遅延及び／又は損失等から、パスの品質を計測する方法をいう。アクティブ計測において試験用パケットを送出する端末をソース、試験用パケットを受信する端末をデスティネーションと呼ぶ。

輻輳区間の推定方法としては、例えば、ネットワークに接続している複数の計測端末間のパスに対してアクティブ計測を行って品質の計測を行うと共に、パス上に存在する中継ノードを探索して、輻輳区間の推定を行う方法が提案されている（例えば、非特許文献１参照。）。

一方、非特許文献２には、ピア・ツー・ピア（Ｐ２Ｐ）型ファイル共有システム等に適用可能である分散ハッシュテーブルを用いたルックアッププロトコルについて記載がされている。

図６は、非特許文献２に記載の構成を説明する図である。図６において、実線の円は、実在する通信ノードと、そのノードＩＤを表している。ここでノードＩＤは、通信ノードのＩＰアドレスをＳＨＡ−１等のハッシュ関数により変換したｎビット長ハッシュ値（ｎは２以上の自然数）であり、図６においてはｎ＝６としている。また、実線で示す円以外のノードＩＤを有する通信ノードは実在しないものとする。また、以下に説明する総ての演算は、２^ｎを法として、即ち、ｍｏｄ２^ｎ上で行われる。

非特許文献２のプロトコルをファイル共有システムに適用する場合、ファイルは、例えばそのファイル名のハッシュ関数によるｎビット長ハッシュ値より大きく、かつ、そのファイル名のｎビット長ハッシュ値に一番近い値をノードＩＤとする通信ノードに保存される。図６において、ファイル名のｎビット長ハッシュ値が２５〜３４のいずれかとなるファイルは、ノードＩＤ＝３５である通信ノードに保存される。

また、各通信ノードは、自身のノードＩＤに２^ｍ（ｍ＝０、１、・・・、ｎ−１）を足した値以上であり、かつ、その値に一番近い値をノードＩＤとする通信ノードを、隣接ノードとし、隣接ノードと通信するために必要な情報、例えば、ＩＰアドレスを保持する。また、各通信ノードが保持する隣接ノードの表をＦｉｎｇｅｒＴａｂｌｅと呼ぶ。図６に示す様に、ノードＩＤ＝３５である通信ノードの隣接ノードは、ノードＩＤ＝３７、４２、４８、５６及び８の合計５つの通信ノードとなる。一般的に、実在する通信ノード数がＮである場合には、ＦｉｎｇｅｒＴａｂｌｅのサイズの期待値はｌｏｇ２Ｎとなる。

所望のファイルを取得する場合、通信ノードは、ファイル名からハッシュ値を求め、求めたハッシュ値を宛先として、求めたハッシュ値以下で、かつ、一番近い値をノードＩＤとする隣接ノードにファイル取得要求を送信する。ファイル取得要求を受信した通信ノードは、要求されたファイルの保存先通信ノードが自身であるか否かを判定し、自身でない場合は、同様の方法で、転送先の通信ノードを決定し、決定した通信ノードにファイル取得要求を転送し、最終的に、ファイル取得要求は、要求されたファイルを保存している通信ノードに転送される。

立花、阿野、長谷川、鶴、尾家、"複数パス上のアクティブ計測に基づく輻輳セグメント推定法"、信学技報Ｖｏｌ．１０４ｎｏ．３０９ＣＱ２００４−７６、ｐｐ．４３−４８、２００４年９月Ｉ．Ｓｔｏｃｉａ、Ｒ．Ｍｏｒｒｉｓ、Ｄ．Ｋａｒｇｅｒ、Ｍ．Ｆ．Ｋａａｓｈｏｅｋ、Ｈ．Ｂａｌａｋｒｉｓｈｎａｎ、"Ｃｈｏｒｄ：ＡＳｃａｌａｂｌｅＰｅｅｒ−ｔｏ−ｐｅｅｒＬｏｏｋｕｐＳｅｒｖｉｃｅｆｏｒＩｎｔｅｒｎｅｔＡｐｐｌｉｃａｔｉｏｎｓ"、ＡＣＭＳＩＧＣＯＭＭ２００１、２００１年

大規模ネットワークの輻輳箇所を計測又は推定するために、多数の計測端末、例えば、１０，０００台の計測端末により、非特許文献１に記載の方法を実行する場合を考える。大規模ネットワークの輻輳箇所の計測又は推定を可能とするためには、できるだけネットワーク上で分散した計測相手を決定する必要がある。更に、非特許文献１には計測結果をどの様に集めて、どの装置にて推定処理を行うのかについての記載はないが、例えば、多数の計測端末が計測した計測結果を１台のサーバに蓄積して推定処理を行わせる構成とした場合、計測端末数の増大に伴い、蓄積されるデータも膨大なものとなり、輻輳箇所の特定に必要な計測結果を即座に参照することが困難になるという問題が生ずる。

従って、本発明は、ネットワークの規模に係わらず、また、各計測端末が計測した計測結果を一括して保存処理するサーバ装置を必要ともせず、効率的に輻輳箇所の推定を可能とする計測端末及びシステムを提供することを目的とする。

本発明による計測端末によると、
端末を識別できる値のｎビット長ハッシュ値をノードＩＤとし、０以上２^ｎ−１以下で、他の計測端末とは重複しない値の範囲である保存範囲を有する計測端末であって、２^ｎを法として、自端末のノードＩＤに所定数を足した値以上であり、かつ、前記所定数を足した値に一番近い値をノードＩＤとする計測端末を隣接端末とし、１つ以上の所定数に基づき１つ以上の隣接端末を決定する決定手段と、隣接端末とのパス上の中継ノードのリストを取得する取得手段と、隣接端末とのパスの品質を計測する計測手段と、隣接端末と品質計測を行ったパスを、該パス上の隣接する中継ノードで特定される１つ以上の区間に分割し、各区間を識別する値のｎビット長ハッシュ値を計算するパス分割手段と、計測結果を保存する保存手段と、品質計測を行ったパスの各区間について、パス分割手段が計算したｎビット長ハッシュ値が、前記保存範囲内にある場合は計測結果を保存手段に保存し、保存範囲外にある場合は計測結果を、該ｎビット長ハッシュ値を宛先として、宛先の値から決定される隣接端末に送信する送信手段と、受信した計測結果の宛先の値が、自端末の保存範囲内にある場合は、受信した計測結果を保存手段に保存し、保存範囲外にある場合は、宛先の値から決定される隣接端末に転送する計測結果転送手段と、輻輳推定を行うパスを区間に分割し、各区間について、区間を識別する値のｎビット長ハッシュ値が自端末の保存範囲外にある場合は、計測結果要求を、該ｎビット長ハッシュ値を宛先として、該ｎビット長ハッシュ値から決定される隣接端末に送信し、保存範囲内にある場合は、自端末の保存手段から計測結果を読み出す結果取得手段と、受信した計測結果要求の宛先の値が、自端末の保存範囲内にある場合は、保存手段に保存している計測結果を、計測結果要求送信元の計測端末に送信し、保存範囲外にある場合は、宛先の値から決定される隣接端末に転送する計測結果要求転送手段と、輻輳推定を行うパスの各区間のうち、少なくとも１つの区間を含む他のパスの計測結果に基づき、輻輳区間の推定を行う輻輳区間推定手段とを有することを特徴とする。

更に、本発明による計測端末の他の実施形態によると、
計測手段は、送信手段が隣接端末に送信する計測結果により、該隣接端末との品質計測を行うことも好ましい。

更に、本発明による計測端末の他の実施形態によると、
各隣接端末とのパスを構成する区間について、区間を通過するパスの数を探索し、区間を通過するパス数に基づきパスの評価値を算出するパス評価値算出手段を有し、計測手段は、上限値を有し、パスの評価値に基づき、上限値以内の隣接端末とのみパスの計測を行うことも好ましい。

更に、本発明による計測端末の他の実施形態によると、
計測手段は、上限値を有し、送信手段及び計測結果転送手段が隣接端末に送信する計測結果のデータ量の多い順に、上限値以内の隣接端末とのみパスの計測を行うことも好ましい。

更に、本発明による計測端末の他の実施形態によると、
前記保存範囲は、２^ｎを法として、実在する他の計測端末のノードＩＤのうち、自端末のノードＩＤより小さく、かつ、一番近いノードＩＤから、自端末のノードＩＤより大きく、かつ、一番近いノードＩＤまでの範囲内にあることも好ましい。

更に、本発明による計測端末の他の実施形態によると、
前記所定数は、２^ｎを法として、２^ｍ＋ｋ（ｍは０以上ｎ−１以下の整数）（ｋは０以上２^ｎ−１以下の整数）であることも好ましい。

本発明によるシステムによれば、
ネットワークと、ネットワークに接続する複数の前記計測端末からなることを特徴とする。

端末を識別できる値を、ハッシュ関数によりｎビット長ハッシュ値に変換してノードＩＤとし、各計測端末の計測相手を、ノードＩＤに所定数を足した値として求めることで、ネットワーク上に多数の計測相手が存在する場合においても、偏りなく分散した計測相手を選択することができる。また、品質計測を行ったパスの各区間のｎビット長ハッシュ値を求め、区間のｎビット長ハッシュ値に対応する計測端末に計測結果を分散配置、即ち、分散ハッシュテーブルにより計測結果を管理することで、計測結果を一括して保存するサーバ装置を要することなく計測結果が管理でき、計測端末数に係わらず、効率的に輻輳箇所の推定に必要な計測結果を参照することができる。

計測結果の送信は、直接保存先の計測端末に送信するのではなく、隣接端末に送信及び／又は転送することにより行う。これにより、計測端末は隣接端末との通信に必要な情報のみを保存して分散ハッシュテーブルを構成し、更に、計測結果の隣接端末への送信を利用して、隣接端末との品質計測を行うことができる。これにより品質計測のためにネットワークへ与える負荷を軽減することができる。

測定するパスの上限値を設け、パスを構成する区間を通過するパス数や、送信手段及び計測結果転送手段が送信する計測結果のデータ量に基づき計測するパスを上限値以内とすることで、測定及び計測結果の送信によりネットワークに与える負荷を低減することができる。

本発明を実施するための最良の形態について、以下では図面を用いて詳細に説明する。

図１は、本発明による輻輳箇所推定システムの構成図である。図１によると、ネットワーク２に複数の計測端末１が接続されている。ネットワーク２の内部には、ルータ等の中継ノード２１が複数存在する。

計測端末は、自身に付与されているＩＰアドレス又名前といった、計測端末を一意に識別できる値をＳＨＡ−１等のハッシュ関数で変換したｎビット長ハッシュ値をノードＩＤとし、２^ｎを法として、自身のノードＩＤに所定数を足した値以上であり、かつ、所定数を足した値に一番近い値をノードＩＤとする計測端末を計測相手として決定する。所定数は、１つ以上とし、例えば、２^ｍ（ｍ＝０、１、・・・、ｎ−１）又は２^ｍ（ｍ＝０、１、・・・、ｎ−１）に２^ｎ−１以下の任意の値を足したものとすることができる。尚、ｎは、２^ｎが、配置する計測端末数以上となるように選択する。これにより、計測端末数が多い場合でも、ネットワーク上から偏りなくｎ以下の計測相手を選択することができる。以後、計測相手となる計測端末のことを隣接端末と呼ぶ。

図２は、各計測端末での処理フロー図である。計測端末は、上記隣接端末との間の複数のパスから、計測を行うパスを１つ選択する（Ｓ２１）。計測パス上に存在する中継ノードリストの調査は、ネットワークへの負荷が大きいため、アクティブ計測の実行ごとには行わない（Ｓ２２）。中継ノードリストの調査を行う場合には、例えば、ＩＰパケットのＴＴＬ（ＴｉｍｅＴｏＬｉｖｅ）フィールドを利用した“Ｔｒａｃｅｒｏｕｔｅ”コマンド等により、計測パス上に存在する中継ノードのリストを取得する（Ｓ２３）。続いて、アクティブ計測を実行して、例えば、図３（ａ）に示す計測結果を取得する。図３（ａ）において、計測経路のアルファベットはパス上に存在する中継ノード、即ち、計測パスの中継ノードリストを表している。

続いて、上記得られた計測結果の保存先となる計測端末を求め、求めた計測端末に計測結果を送信する（Ｓ２５）。図３（ｂ）は、図３（ａ）の計測結果の保存先計測端末を示す図である。ここでは、図６の実線の円に示すノードＩＤを持つ計測端末が配置されているものとしている。計測端末は、計測経路、即ち、中継ノードのリストである、中継ノードＡ−Ｂ−Ｃ−Ｄ−Ｅ−Ｆを区間に分割する。ここで、区間とは、隣り合う中継ノードにより特定されるパスの一部分をいう。続いて、この区間に、システムで共通の方法で区間を特定する値を付与する。区間を特定する値の付与方法としては、例えば、中継ノードＡのＩＰアドレスが１０．０．０．１で、中継ノードＢのＩＰアドレスが１９２．１６８．０．１の場合に、中継ノードＡからＢ方向の区間を、１０.０．０．１.１９２．１６８．０．１、中継ノードＢからＡ方向の区間を、１９２．１６８．０．１．１０.０．０．１とする方法等がある。続いて、区間を特定する値のｎビット長ハッシュ値を求める。図３（ｂ）においては、区間Ａ：Ｂ、区間Ｂ：Ｃ、区間Ｃ：Ｄ、区間Ｄ：Ｅ及び区間Ｅ：Ｆを特定する値のｎビット長ハッシュ値は、それぞれ、６、４３、２４、５１及び１８である。

求めたｎビット長ハッシュ値をノードＩＤとする計測端末が常に実在するわけではないため、求めたｎビット長ハッシュ値に基づき計測結果を保存する計測端末を求める。図３（ｂ）の例においては、２^ｎを法として、求めたｎビット長ハッシュ値より大きく、かつ、求めたｎビット長ハッシュ値に一番近い値をノードＩＤとする計測端末に保存している。即ち、区間を特定する値のｎビット長ハッシュ値である６、４３、２４、５１及び１８に対応して、ノードＩＤが８、４８、２５、５６及び１９である計測端末に、図３（ａ）に示す計測結果を保存している。尚、中継ノードがｋ個あるパスを計測した場合、ｋ−１個の計測端末が保存先計測端末となり、これらｋ−１個の保存先計測端末は、同じ計測結果を保存する。

また、計測端末は、２^ｎを法として、自端末のノードＩＤより小さく、かつ、一番近い値をノードＩＤとする計測端末を認識しており、計測結果を保存すべき計測端末が自身ではない場合、区間を特定する値のｎビット長ハッシュ値を宛先として、宛先のノードＩＤ以下で一番近い値の隣接端末に送信する。計測結果を受信した隣接端末は、宛先に示されたノードＩＤから自身が保存すべき計測結果であるか否かを判断して、自身が保存すべき計測結果ではない場合は、上記方法で求めた隣接端末に更に転送する。

上述したように、計測端末は、自装置が結果を保存すべき値の範囲を有しており、パスの区間のｎビット長ハッシュ値がこの範囲内であれば、計測結果を保存し、範囲外であれば隣接端末に送信又は転送する。この計測結果を保存する値の範囲は、各計測端末で範囲の重複がない限り、前記範囲、即ち、自端末のノードＩＤより小さく、かつ、一番近い実在する計測端末のノードＩＤから、自端末のノードＩＤより１小さい数までの範囲以外であってもよい。例えば、自端末のノードＩＤより小さく、かつ、一番近い実在する計測端末のノードＩＤより１大きい値から、自端末のノードＩＤまでの範囲や、自端末のノードＩＤから、自端末のノードＩＤより大きく、かつ、一番近い実在する計測端末のノードＩＤより１小さい値までの範囲であってもよい。しかしながら、各計測端末で範囲の重複がないことを確実にするために、この範囲は、自端末のノードＩＤより小さく、かつ、一番近い実在する計測端末のノードＩＤから、自端末のノードＩＤより大きく、かつ、一番近い実在する計測端末のノードＩＤまでの範囲内で決定することが好ましい。また、計測結果の送信方法についても、上記方法に限定されない。

計測結果を保存先計測端末に送信後、全パスの計測が終了したか否かを判定し、未計測のパスがある場合には、一定時間経過後に次のパスの計測を行い、全パスについて計測している場合には、次の計測まで待機する（Ｓ２６）。

尚、Ｔｒａｃｅｒｏｕｔｅコマンドにより中継ノードのリストは、ソースである計測端末が取得し、アクティブ計測によりパス品質の計測結果は、デスティネーションである計測端末が取得するが、ソースである計測端末が中継ノードのリストをデスティネーションの計測端末に送信して、デスティネーションである計測端末が、計測結果を保存先計測端末に送信する構成とすることも、逆に、デスティネーションである計測端末が、計測結果をソースである計測端末に送信して、ソースである計測端末が、計測結果を保存先計測端末に送信する構成とすることも可能である。

図４は、本発明による輻輳箇所の推定方法のフロー図である。
（Ｓ４１）推定を行いたいパスに接続されている計測端末は、まず、推定対象パスの中継ノードリストを取得する。
（Ｓ４２）取得した推定対象パスの中継ノードリストに基づき、推定対象パスを区間に分割する。
（Ｓ４３）分割した区間から、計測結果を取得する区間を１つ選択する。
（Ｓ４４）選択した区間を特定する値のｎビット長ハッシュ値を求め、選択した区間を含むパスの計測結果が保存されている計測端末から、所定時間内の計測結果を取得する。他の計測端末が計測結果を保存している場合、計測結果の取得は、計測結果の保存と同様、選択した区間を特定する値のｎビット長ハッシュ値を宛先として、宛先のノードＩＤ以下で一番近い値の隣接端末に、計測結果の取得要求を送信する。計測結果の取得要求を受信した隣接端末は、自身が計測結果を保存している計測端末である場合は、計測結果を、計測結果の取得要求の送信元に送信し、計測結果を保存している計測端末ではない場合には、同様の方法で転送先の隣接端末を決定して計測結果の取得要求を転送する。尚、所定の時間内の計測結果のみを取得するのは、輻輳は時間により変化するからである。
（Ｓ４５）推定対象パスの全区間について計測結果を取得していない場合は、Ｓ４３〜Ｓ４４の処理を繰り返す。その後、取得した計測結果に基づき輻輳箇所の推定を行う。

上記処理を、図５を用いて具体的に説明する。図５に示す表は、パス１〜パス８についての計測結果を示している。図５に示す表のうち、０又はアルファベットが表示されている区間は、そのパスを構成する区間を示している。例えば、パス１は、区間１、２、３、４から構成され、パス６は、区間１、２、７、１０より構成されている。また、表の０は計測の結果、パケットロスが発生しなかったことを、ａ〜ｄのアルファベットは、発生したパケットロスの値、又はパケットロスの値から算出したパケットロスのランクを表している。例えば、パス１の計測では、パケットロスは発生せず、パス３の計測では、ａ％のパケットロス、又はランクａのパケットロスが発生したことを示している。

パス１〜８の計測結果は、上述した様に、分散ハッシュテーブルに分散配置されている。即ち、パスの各区間のｎビット長ハッシュ値から決定される計測端末に、それぞれ保存されている。よって、区間１を特定する値のｎビット長ハッシュ値で決定される計測端末には、パス１、２、６及び８の計測結果が保存され、区間３を特定する値のｎビット長ハッシュ値で決定される計測端末には、パス１及び４の計測結果が保存されている。

ここで、区間７、８、９及び１０から構成されるパス１０の推定を行うものとする。計測端末１は、まず区間７を選択し、区間７の計測結果を保存している計測端末から計測結果を取得する。この場合、パス２、３及び６の計測結果を取得することになる。

続いて、区間８を選択して、パス２及び５の計測結果を取得する。同様に、区間９の選択によりパス２、５及び８の計測結果を取得し、区間１０の選択によりパス３、５及び６の計測結果を取得する。

計測端末１は、取得した各パスの計測結果及びそのパスを構成する区間に基づき輻輳区間の推定を行う。その際に計測時間等も考慮する。本説明例では、計測端末１は、パス２、３、５、６及び８の計測結果を取得し、例えば、パケットロスなしとの計測結果が得られていない区間１０を輻輳区間と推定する。

パスが平均的にｐの区間から構成され、計測端末数がＮとすると、１つの計測端末が１回の計測で取得する計測結果の平均は、ｐｌｏｇ２Ｎである。また、計測結果取得に要する時間は、Ｏ（ｌｏｇＮ）、即ちｌｏｇＮのオーダとなり、輻輳区間推定において必要なデータを即座に参照できることになる。

各計測端末は、計測端末固有の値をＳＨＡ−１等のハッシュ関数で変換したｎビット長ハッシュ値であるノードＩＤに基づき隣接端末を決定する。そして、計測結果の送信又は取得は、計測結果のパスを構成する区間、或いは、計測結果を取得したい区間のｎビット長ハッシュ値を宛先とし、宛先ノードＩＤ以下で、かつ、一番近い値をノードＩＤとする隣接端末に計測結果又は取得要求を送信することにより行ない、アクティブ計測は、隣接端末に対して試験のためのパケットを送信することにより行う。したがって、アクティブ計測で隣接端末に送信するパケットに計測結果を含めることで、計測結果の送信等のためにネットワークに与える負荷を軽減することができる。

更に、ネットワークに与える負荷を軽減することを考える。まず、ネットワーク内部は、ある種の階層構造により構成されるため、上位階層に位置する中継ノードにより構成される区間程、通過する計測対象のパス数が多くなることに着目する。

図７は、上位階層の中継ノードにより構成される区間を通過する計測対象のパス数が多くなることを説明する図である。図７において円で表現されているのは中継ノードであり、そのうち符号２２、２３、２４は最上位の階層に位置する中継ノードである。また、中継ノード２２から２３への区間を区間Ａとし、中継ノード２３から２４への区間を区間Ｂとする。尚、四角で表現されているものは計測端末である。ここで、中継ノード２２の配下にある計測端末が、中継ノード２３の配下にある計測端末と構成されるパスを計測する場合、これらパスには総て区間Ａが含まれ、中継ノード２２の配下にある計測端末が、中継ノード２４の配下にある計測端末と構成されるパスを計測する場合、これらパスには総て区間Ａ及びＢが含まれるため、区間Ａ及び区間Ｂは多くの計測パスが通過することになる。

計測結果は、区間のｎビット長ハッシュ値を宛先として、宛先ノードＩＤ以下で、かつ、一番近い値をノードＩＤとする隣接端末に送信するため、例えば、図７の区間Ａや区間Ｂのｎビット長ハッシュ値を宛先として送信される計測結果の量は多くなり、これら区間Ａや区間Ｂを通過するパスの一部を計測対象パスから除外することで、計測精度には影響を与えずにネットワークに与える負荷を軽減することができる。

このため、隣接端末とのパスの総てを計測対象とするのではなく、計測対象のパス数に上限を設け、隣接端末数が上限を超えている場合には、上限を超えた部分については計測を行わないこととする。隣接端末数が上限を超えている場合には、計測を行う隣接端末、即ち、計測対象のパスを決定する必要があるが、その方法としては、多数の計測対象パスが通過する区間を含まない計測対象パスを選択する。例えば、計測端末において、各隣接端末との間にある中継ノードリストを取得して、隣接端末とのパスを構成する区間を認識し、各区間を通るパス数の逆数をその区間の値として、各パスの評価値を、そのパスを構成する区間の値の和として算出し、評価値が大きいパスから順に、上限として規定した数のパスだけを計測対象とする。また、計測端末間で各区間を通過するパスの情報を交換し、各区間を通るパスの絶対数に基づき上記計算を行っても良い。

一方、アクティブ計測を行うパケットに乗せる計測結果が少ないことは、計測結果をアクティブ計測に乗せることによる負荷の軽減効果が少ないことを意味する。したがって、隣接端末ごとに、送信する計測結果のデータ量を求め、データ量の多い順に上限として規定した数だけの隣接端末とのみ計測を行なうことで、ネットワークに与える負荷を軽減することができる。ここで、計測結果のデータ量は、自端末での計測結果により発生するデータのみならず、他の計測端末から受信し、転送を行う必要がある計測結果のデータを含んだものとする。

本発明の計測端末は、以上説明した各機能を実行するコンピュータプログラムを、コンピュータ上で動作させることでも実現できる。

本発明による輻輳箇所推定システムの構成図である。各計測端末での処理フロー図である。計測結果と、計測結果の保存先計測端末の例を示す図である。本発明による輻輳箇所の推定方法のフロー図である。本発明による輻輳箇所の推定方法を説明する図である。従来技術によるルックアッププロトコルを説明する図である。上位階層の中継ノードにより構成される区間を通過する計測対象のパス数が多くなることを説明する図である。

符号の説明

１計測端末
２ネットワーク
２１、２２、２３、２４中継ノード

Claims

端末を識別できる値のｎビット長ハッシュ値をノードＩＤとし、０以上２^ｎ−１以下で、他の計測端末とは重複しない値の範囲である保存範囲を有する計測端末であって、
２^ｎを法として、自端末のノードＩＤに所定数を足した値以上であり、かつ、前記所定数を足した値に一番近い値をノードＩＤとする計測端末を隣接端末とし、１つ以上の所定数に基づき１つ以上の隣接端末を決定する決定手段と、
隣接端末とのパス上の中継ノードのリストを取得する取得手段と、
隣接端末とのパスの品質を計測する計測手段と、
隣接端末と品質計測を行ったパスを、該パス上の隣接する中継ノードで特定される１つ以上の区間に分割し、各区間を識別する値のｎビット長ハッシュ値を計算するパス分割手段と、
計測結果を保存する保存手段と、
品質計測を行ったパスの各区間について、パス分割手段が計算したｎビット長ハッシュ値が、前記保存範囲内にある場合は計測結果を保存手段に保存し、保存範囲外にある場合は計測結果を、該ｎビット長ハッシュ値を宛先として、宛先の値から決定される隣接端末に送信する送信手段と、
受信した計測結果の宛先の値が、自端末の保存範囲内にある場合は、受信した計測結果を保存手段に保存し、保存範囲外にある場合は、宛先の値から決定される隣接端末に転送する計測結果転送手段と、
輻輳推定を行うパスを区間に分割し、各区間について、区間を識別する値のｎビット長ハッシュ値が自端末の保存範囲外にある場合は、計測結果要求を、該ｎビット長ハッシュ値を宛先として、該ｎビット長ハッシュ値から決定される隣接端末に送信し、保存範囲内にある場合は、自端末の保存手段から計測結果を読み出す結果取得手段と、
受信した計測結果要求の宛先の値が、自端末の保存範囲内にある場合は、保存手段に保存している計測結果を、計測結果要求送信元の計測端末に送信し、保存範囲外にある場合は、宛先の値から決定される隣接端末に転送する計測結果要求転送手段と、
輻輳推定を行うパスの各区間のうち、少なくとも１つの区間を含む他のパスの計測結果に基づき、輻輳区間の推定を行う輻輳区間推定手段と、
を有することを特徴とする計測端末。
計測手段は、送信手段が隣接端末に送信する計測結果により、該隣接端末との品質計測を行うことを特徴とする請求項１に記載の計測端末。
各隣接端末とのパスを構成する区間について、区間を通過するパスの数を探索し、区間を通過するパス数に基づきパスの評価値を算出するパス評価値算出手段を有し、
計測手段は、上限値を有し、パスの評価値に基づき、上限値以内の隣接端末とのみパスの計測を行うこと、
を特徴とする請求項１又は２に記載の計測端末。
計測手段は、上限値を有し、送信手段及び計測結果転送手段が隣接端末に送信する計測結果のデータ量の多い順に、上限値以内の隣接端末とのみパスの計測を行うこと、
を特徴とする請求項２に記載の計測端末。
前記保存範囲は、２^ｎを法として、実在する他の計測端末のノードＩＤのうち、自端末のノードＩＤより小さく、かつ、一番近いノードＩＤから、自端末のノードＩＤより大きく、かつ、一番近いノードＩＤまでの範囲内にあることを特徴とする請求項１から４のいずれか１項に記載の計測端末。
前記所定数は、２^ｎを法として、２^ｍ＋ｋ（ｍは０以上ｎ−１以下の整数）（ｋは０以上２^ｎ−１以下の整数）であることを特徴とする請求項１から５のいずれか１項に記載の計測端末。
ネットワークと、ネットワークに接続する複数の計測端末からなるシステムであって、
計測端末は、請求項１から６のいずれか１項に記載の計測端末であることを特徴とするシステム。