(57)【特許請求の範囲】
【請求項１】
第１のホストと第２のホストとの通信経路上に、複数のノードが存在するネットワーク内の所定のリンクの帯域使用率を推定する情報処理装置において、
前記複数のノードまたは前記第２のホストのうち、前記帯域使用率を推定したいリンクの両端に位置するノードのそれぞれを宛先ノードに設定し、前記第１のホストから前記宛先ノードに対して第１のパケットを送信し、前記第１のパケットに対する前記宛先ノードからの第２のパケットを前記第１のホストで受信し、前記送信から前記受信までの時間を前記両端に位置するノード毎にそれぞれ計測する計測手段と、
前記計測を、複数回、前記宛先ノードに対して行うことで、前記送信から前記受信までの時間の確率密度関数を前記両端に位置するノード毎にそれぞれ算出する第１の算出手段と、
前記第１の算出手段により前記両端に位置するノード毎にそれぞれ算出された前記確率密度関数を用いて逆畳み込み演算を行うことで、所定のリンクの確率分布を算出する第２の算出手段と、
前記第２の算出手段により算出された前記所定のリンクの確率分布から前記所定のリンクにおける帯域使用率を推定する推定手段と
を備える情報処理装置。
【請求項２】
前記第１のパケットには、前記第２のパケットを各ノードにおいて優先的に処理するか否かを示すフラグが含まれる
請求項１に記載の情報処理装置。
【請求項３】
第１のホストと第２のホストとの通信経路上に、複数のノードが存在するネットワーク内の所定のリンクの帯域使用率を推定する情報処理装置の情報処理方法において、
前記複数のノードまたは前記第２のホストのうち、前記帯域使用率を推定したいリンクの両端に位置するノードのそれぞれを宛先ノードに設定し、前記第１のホストから前記宛先ノードに対して第１のパケットを送信し、前記第１のパケットに対する前記宛先ノードからの第２のパケットを前記第１のホストで受信し、前記送信から前記受信までの時間を前記両端に位置するノード毎にそれぞれ計測し、
前記計測を、複数回、前記宛先ノードに対して行うことで、前記送信から前記受信までの時間の確率密度関数を前記両端に位置するノード毎にそれぞれ算出し、
前記両端に位置するノード毎にそれぞれ算出された前記確率密度関数を用いて逆畳み込み演算を行うことで、所定のリンクの確率分布を算出し、
算出された前記所定のリンクの確率分布から前記所定のリンクにおける帯域使用率を推定する
ステップを含む情報処理方法。
【請求項４】
第１のホストと第２のホストとの通信経路上に、複数のノードが存在するネットワーク内の所定のリンクの帯域使用率を推定する情報処理装置に、
前記複数のノードまたは前記第２のホストのうち、前記帯域使用率を推定したいリンクの両端に位置するノードのそれぞれを宛先ノードに設定し、前記第１のホストから前記宛先ノードに対して第１のパケットを送信し、前記第１のパケットに対する前記宛先ノードからの第２のパケットを前記第１のホストで受信し、前記送信から前記受信までの時間を前記両端に位置するノード毎にそれぞれ計測し、
前記計測を、複数回、前記宛先ノードに対して行うことで、前記送信から前記受信までの時間の確率密度関数を前記両端に位置するノード毎にそれぞれ算出し、
前記両端に位置するノード毎にそれぞれ算出された前記確率密度関数を用いて逆畳み込み演算を行うことで、所定のリンクの確率分布を算出し、
算出された前記所定のリンクの確率分布から前記所定のリンクにおける帯域使用率を推定する
ステップを含む処理を実行させるためのコンピュータ読み取り可能なプログラム。
【請求項５】
第１のホストと第２のホストとの通信経路上に、複数のノードが存在するネットワーク内の所定のリンクの帯域使用率を推定する情報処理装置において、
前記第２のホストを宛先ノードに設定し、前記宛先ノードに対して、ＴＴＬ（Time To Live）を含む第１のパケットを送信し、その第１のパケットに対する前記ノードからの第２のパケットを受信し、前記送信から前記受信までの時間を計測する計測手段と、
前記計測を、複数回、同一のＴＴＬを含む前記第１のパケットを前記宛先ノードに対して送信することで行い、また前記ＴＴＬの値を増やすことで、前記複数のノードの全てに対して行うことで、前記送信から前記受信までの時間の確率密度関数を算出する第１の算出手段と、
前記第１の算出手段により算出された前記確率密度関数に対して逆畳み込み演算を行うことで、所定のリンクの確率分布を算出する第２の算出手段と、
前記第２の算出手段により算出された前記所定のリンクの確率分布から前記所定のリンクにおける帯域使用率を推定する推定手段と
を備える情報処理装置。
【請求項６】
第１のホストと第２のホストとの通信経路上に、複数のノードが存在するネットワーク内の所定のリンクの帯域使用率を推定する情報処理装置の情報処理方法において、
前記第２のホストを宛先ノードに設定し、前記宛先ノードに対して、ＴＴＬ（Time To Live）を含む第１のパケットを送信し、その第１のパケットに対する前記ノードからの第２のパケットを受信し、前記送信から前記受信までの時間を計測し、
前記計測を、複数回、同一のＴＴＬを含む前記第１のパケットを前記宛先ノードに対して送信することで行い、また前記ＴＴＬの値を増やすことで、前記複数のノードの全てに対して行うことで、前記送信から前記受信までの時間の確率密度関数を算出し、
算出された前記確率密度関数に対して逆畳み込み演算を行うことで、所定のリンクの確率分布を算出し、
算出された前記所定のリンクの確率分布から前記所定のリンクにおける帯域使用率を推定する
ステップを含む情報処理方法。
【請求項７】
第１のホストと第２のホストとの通信経路上に、複数のノードが存在するネットワーク内の所定のリンクの帯域使用率を推定する情報処理装置に、
前記第２のホストを宛先ノードに設定し、前記宛先ノードに対して、ＴＴＬ（Time To Live）を含む第１のパケットを送信し、その第１のパケットに対する前記ノードからの第２のパケットを受信し、前記送信から前記受信までの時間を計測し、
前記計測を、複数回、同一のＴＴＬを含む前記第１のパケットを前記宛先ノードに対して送信することで行い、また前記ＴＴＬの値を増やすことで、前記複数のノードの全てに対して行うことで、前記送信から前記受信までの時間の確率密度関数を算出し、
算出された前記確率密度関数に対して逆畳み込み演算を行うことで、所定のリンクの確率分布を算出し、
算出された前記所定のリンクの確率分布から前記所定のリンクにおける帯域使用率を推定する
ステップを含む処理を実行させるためのコンピュータ読み取り可能なプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は情報処理装置および方法、並びにプログラムに関し、特に、ネットワークの帯域使用率を推定する際に用いて好適な情報処理装置および方法、並びにプログラムに関する。
【背景技術】
【０００２】
近年、ネットワークのトラヒックが増大し、通信効率の維持を目的として、ネットワークの通信制御が行われつつある。ネットワークの通信制御を行うためには、ネットワークの性能評価が必要である。ネットワークの性能評価の手法として、エンドホスト間の通信経路のリンクの帯域使用率を測定する手法がある。リンクの帯域使用率とは、そのリンクの物理帯域のうち、どれくらいの帯域が使用されているかの割合を示す値である。このリンク帯域使用率が大きいほど、そのリンクには負荷が掛かっていることになる。
【０００３】
負荷が掛かっているリンクがネットワーク内に存在すると、ネットワーク自体の性能が低下してしまう。ネットワーク内のエンドホスト間において通信経路の候補が複数ある場合、もっとも負荷が小さい経路を選択することで、負荷が掛かっているリンクを避けて通信を行うことが可能となる。このようなことを可能とするために、上記したように、リンク帯域使用率を測定するといったネットワークの性能評価が行われている。（非特許文献１乃至５参照）
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】滝田英勝， 杉崎義雄， 山口実靖， 浅谷耕一，“RTT を用いたボトルネックリンクの帯域使用率推定法”，信学技報，IA2008-15，pp.13-18．
【非特許文献２】M. Jain and C. Dovrolis, “End-to-End Available Bandwidth: Measurement Methodology, Dynamics, and Relation with TCP Through-put”， In Proceedings of the 2002 SIGCOMM conference, 2002.
【非特許文献３】Vinay Ribeiro, Rudolf Riedi, Richard Bara-niuk, Jiri Navratil, and Les Cottrell “pathChirp:EfficientAvailable Bandwidth Estimation for Network Paths, ”，Passive and Active Measurement Workshop，2003.
【非特許文献４】Ningning Hu and Peter Steenkiste，“Estimating Available Bandwidth Using Packet PairProbing ”，2002．
【非特許文献５】“ Tobi Oetiker's MRTG - TheMulti Router Traffic Grapher ”，http://oss.oetiker.ch/mrtg/
【発明の概要】
【発明が解決しようとする課題】
【０００５】
提案されている従来のエンドホスト間の帯域使用率を求める手法として、通信経路中の各ノードに測定用のソフトウェアを組み込み、各ノードが、トラフィックの流量を監視し、解析する手法がある。この手法によれば、帯域使用率を正確に測れる利点があるが、各ノードに測定用のソフトウェアを組み込まなくてはならず、その手間がかかる、費用がかかるといった問題があった。また、各ノードがトラフィックの流量を監視し、解析するために、各ノードに、そのような処理を行うための負荷を与えてしまうことになる。
【０００６】
また提案されている従来の手法として、Pingを用いた方式がある。Pingは、ネットワーク中のノードに通じるかを判定するものであり、相手のノードにRequest を送り、相手はReply は送り手にReplyを返すものである。このPingを、通信経路のエンドホストからもう一方のエンドホストに送ることで、ＲＴＴ（Round-Trip-Time）の最小値の出現頻度を得て、帯域使用率を推定する方式が提案されている。この方式によれば、Ping を送るという簡易な方法で、帯域使用率を測定することができるが、１ホップの通信経路でしか、帯域使用率を測定することができない。
【０００７】
本発明は、このような状況に鑑みてなされたものであり、簡便な手法で、帯域使用率を求め、ネットワークの効率的な利用を促すことができるようにするものである。
【課題を解決するための手段】
【０００８】
本発明の一側面の第１の情報処理装置は、第１のホストと第２のホストとの通信経路上に、複数のノードが存在するネットワーク内の所定のリンクの帯域使用率を推定する情報処理装置において、前記複数のノードまたは前記第２のホストのうち、前記帯域使用率を推定したいリンクの両端に位置するノードのそれぞれを宛先ノードに設定し、前記第１のホストから前記宛先ノードに対して第１のパケットを送信し、前記第１のパケットに対する前記宛先ノードからの第２のパケットを前記第１のホストで受信し、前記送信から前記受信までの時間を前記両端に位置するノード毎にそれぞれ計測する計測手段と、前記計測を、複数回、前記宛先ノードに対して行うことで、前記送信から前記受信までの時間の確率密度関数を前記両端に位置するノード毎にそれぞれ算出する第１の算出手段と、前記第１の算出手段により前記両端に位置するノード毎にそれぞれ算出された前記確率密度関数を用いて逆畳み込み演算を行うことで、所定のリンクの確率分布を算出する第２の算出手段と、前記第２の算出手段により算出された前記所定のリンクの確率分布から前記所定のリンクにおける帯域使用率を推定する推定手段とを備える。
【０００９】
前記第１のパケットには、前記第２のパケットを各ノードにおいて優先的に処理するか否かを示すフラグが含まれるようにすることができる。
【００１０】
本発明の一側面の第１の情報処理方法は、第１のホストと第２のホストとの通信経路上に、複数のノードが存在するネットワーク内の所定のリンクの帯域使用率を推定する情報処理装置の情報処理方法において、前記複数のノードまたは前記第２のホストのうち、前記帯域使用率を推定したいリンクの両端に位置するノードのそれぞれを宛先ノードに設定し、前記第１のホストから前記宛先ノードに対して第１のパケットを送信し、前記第１のパケットに対する前記宛先ノードからの第２のパケットを前記第１のホストで受信し、前記送信から前記受信までの時間を前記両端に位置するノード毎にそれぞれ計測し、前記計測を、複数回、前記宛先ノードに対して行うことで、前記送信から前記受信までの時間の確率密度関数を前記両端に位置するノード毎にそれぞれ算出し、前記両端に位置するノード毎にそれぞれ算出された前記確率密度関数を用いて逆畳み込み演算を行うことで、所定のリンクの確率分布を算出し、算出された前記所定のリンクの確率分布から前記所定のリンクにおける帯域使用率を推定するステップを含む。
【００１１】
本発明の一側面の第１のプログラムは、第１のホストと第２のホストとの通信経路上に、複数のノードが存在するネットワーク内の所定のリンクの帯域使用率を推定する情報処理装置に、前記複数のノードまたは前記第２のホストのうち、前記帯域使用率を推定したいリンクの両端に位置するノードのそれぞれを宛先ノードに設定し、前記第１のホストから前記宛先ノードに対して第１のパケットを送信し、前記第１のパケットに対する前記宛先ノードからの第２のパケットを前記第１のホストで受信し、前記送信から前記受信までの時間を前記両端に位置するノード毎にそれぞれ計測し、前記計測を、複数回、前記宛先ノードに対して行うことで、前記送信から前記受信までの時間の確率密度関数を前記両端に位置するノード毎にそれぞれ算出し、前記両端に位置するノード毎にそれぞれ算出された前記確率密度関数を用いて逆畳み込み演算を行うことで、所定のリンクの確率分布を算出し、算出された前記所定のリンクの確率分布から前記所定のリンクにおける帯域使用率を推定するステップを含む処理を実行させるためのコンピュータ読み取り可能なプログラムである。
【００１２】
本発明の一側面の第１の情報処理装置および方法、並びにプログラムにおいては、設定された宛先ノードに対して、第１のパケットが送信され、その第１のパケットに対する宛先ノードからの第２のパケットが受信され、送信から受信までの時間が計測される。その計測が、複数回、同一の宛先ノードに対して行われ、送信から受信までの時間の確率密度関数が算出される。複数のノードにおける確率密度関数に対して逆畳み込み演算が行われ、所定のリンクの確率分布が算出される。そして、その所定のリンクの確率分布から所定のリンクにおける帯域使用率が推定される。
【００１３】
本発明の一側面の第２の情報処理装置は、第１のホストと第２のホストとの通信経路上に、複数のノードが存在するネットワーク内の所定のリンクの帯域使用率を推定する情報処理装置において、前記第２のホストを宛先ノードに設定し、前記宛先ノードに対して、ＴＴＬ（Time To Live）を含む第１のパケットを送信し、その第１のパケットに対する前記ノードからの第２のパケットを受信し、前記送信から前記受信までの時間を計測する計測手段と、前記計測を、複数回、同一のＴＴＬを含む前記第１のパケットを前記宛先ノードに対して送信することで行い、また前記ＴＴＬの値を増やすことで、前記複数のノードの全てに対して行うことで、前記送信から前記受信までの時間の確率密度関数を算出する第１の算出手段と、前記第１の算出手段により算出された前記確率密度関数に対して逆畳み込み演算を行うことで、所定のリンクの確率分布を算出する第２の算出手段と、前記第２の算出手段により算出された前記所定のリンクの確率分布から前記所定のリンクにおける帯域使用率を推定する推定手段とを備える。
【００１４】
本発明の一側面の第２の情報処理方法は、第１のホストと第２のホストとの通信経路上に、複数のノードが存在するネットワーク内の所定のリンクの帯域使用率を推定する情報処理装置の情報処理方法において、前記第２のホストを宛先ノードに設定し、前記宛先ノードに対して、ＴＴＬ（Time To Live）を含む第１のパケットを送信し、その第１のパケットに対する前記ノードからの第２のパケットを受信し、前記送信から前記受信までの時間を計測し、前記計測を、複数回、同一のＴＴＬを含む前記第１のパケットを前記宛先ノードに対して送信することで行い、また前記ＴＴＬの値を増やすことで、前記複数のノードの全てに対して行うことで、前記送信から前記受信までの時間の確率密度関数を算出し、算出された前記確率密度関数に対して逆畳み込み演算を行うことで、所定のリンクの確率分布を算出し、算出された前記所定のリンクの確率分布から前記所定のリンクにおける帯域使用率を推定するステップを含む。
【００１５】
本発明の一側面の第２のプログラムは、コンピュータに、第１のホストと第２のホストとの通信経路上に、複数のノードが存在するネットワーク内の所定のリンクの帯域使用率を推定する情報処理装置に、前記第２のホストを宛先ノードに設定し、前記宛先ノードに対して、ＴＴＬ（Time To Live）を含む第１のパケットを送信し、その第１のパケットに対する前記ノードからの第２のパケットを受信し、前記送信から前記受信までの時間を計測し、前記計測を、複数回、同一のＴＴＬを含む前記第１のパケットを前記宛先ノードに対して送信することで行い、また前記ＴＴＬの値を増やすことで、前記複数のノードの全てに対して行うことで、前記送信から前記受信までの時間の確率密度関数を算出し、算出された前記確率密度関数に対して逆畳み込み演算を行うことで、所定のリンクの確率分布を算出し、算出された前記所定のリンクの確率分布から前記所定のリンクにおける帯域使用率を推定するステップを含む処理を実行させるためのコンピュータ読み取り可能なプログラムである。
【００１６】
本発明の一側面の第２の情報処理装置および方法、並びにプログラムにおいては、設定された宛先ノードに対して、ＴＴＬを含む第１のパケットが送信され、その第１のパケットに対するノードからの第２のパケットが受信され、送信から受信までの時間が計測される。そのような計測が、複数回、同一のＴＴＬを含む第１のパケットを宛先ノードに対して行うことで行われ、送信から受信までの時間の確率密度関数が算出される。確率密度関数は、ＴＴＬの値が増やされることで、複数のノードの全てにおいて算出され、複数の確率密度関数に対して逆畳み込み演算が行われることで、所定のリンクの確率分布が算出される。そして算出された所定のリンクの確率分布から所定のリンクにおける帯域使用率が推定される。
【発明の効果】
【００１７】
本発明の一側面によれば、ネットワーク内の所定のリンク間の帯域使用率を推定することが可能となる。
【図面の簡単な説明】
【００１８】
【図１】１ホップのネットワークについて説明するための図である。
【図２】複数ホップのネットワークについて説明するための図である。
【図３】リンク間の帯域使用率の算出について説明するための図である。
【図４】エンドホスト、ノードの機能について説明するための図である。
【図５】送信元ホストの送信処理について説明するためのフローチャートである。
【図６】送信元ホストの受信処理について説明するためのフローチャートである。
【図７】中継ノードの処理について説明するためのフローチャートである。
【図８】宛先ノードの処理について説明するためのフローチャートである。
【図９】送信元ホストの他の処理について説明するためのフローチャートである。
【図１０】中継ノードの他の処理について説明するためのフローチャートである。
【図１１】記録媒体について説明するための図である。
【発明を実施するための形態】
【００１９】
以下に、本発明の実施の形態について図面を参照して説明する。
【００２０】
本発明は、ネットワークのリンクの帯域使用率を測定するのに適用できる。以下に説明する本発明は、通信経路中のエンドホストと各ノード間でPing を送り、エンドホストと各ノード間のＲＴＴの遅延時間の確率密度関数を得て、逆畳みこみを利用することで、リンクの帯域使用率を推定する。
【００２１】
Pingとは、ネットワーク上の所定のノードに対する応答要求（Request パケット）を送り、要求に対して当該ノードが応答確認（Replyパケット）を返す一連の動作のことである。以下の説明においては、Pingを用いた方式を例にあげて説明するが、所定のノードに対して、パケットを送信し、その送信に対応した応答を受信する仕組みであれば、本発明に適用できるため、本発明の適用範囲が、ＩＰ ネットワークにおけるPing に限定されることを意味するわけではない。
【００２２】
パケットとは、２点間のホストで通信を行うためのデータの転送単位のことであるとする。ここでは、パケットとの記載をするが、本発明に適用できるのは、ネットワークにおけるパケットだけではなく、そのようなパケットだけに限定されることを意味する記載ではない。ＲＴＴは、送信側のエンドホストが、Request パケットを送ってから、Replyパケットを受信するまでの時間である。
【００２３】
ネットワークのリンクの帯域使用率について説明する。まず、ネットワークとして、図１に示したようなネットワークを例にあげて説明する。図１に示したネットワークは、エンドホスト１１がノード１２と接続され、ノード１２がエンドホスト１３と接続されている。ノード１２は、キュー２１を備える。このようなネットワークにおいて、エンドホスト１１からエンドホスト１３に至る通信経路には、１つのノード１２しか存在しておらず、このようなネットワークを１ホップからなる通信経路と称する。
【００２４】
１ホップからなる通信経路においては、ＲＴＴの遅延時間は、ノード１２で起こることになる。すなわち、ＲＴＴは、次式（１）で表すことができる。
ＲＴＴ＝Const＋Ｔque    ・・・（１）
式（１）において、Constは、次式（２）で表される値であり、Ｔqueは、キュー２１におけるキューイング遅延である。このキューイング遅延とは、出力インタフェースであるキュー２１に、パケットが格納されている時間である。
Const＝Ｔtrs＋Ｔfw＋Ｔprop    ・・・（２）
式（２）において、Ｔtrsは処理遅延を表し、Ｔfwは転送遅延を表し、Ｔpropは伝搬遅延を表す。これらのＴtrs、Ｔfw、Ｔpropは、ノード１２の処理能力などに依存し、ノード固有の値となる。よって、Const、すなわち、constant（一定値）は、通信経路固有の値となる。
【００２５】
式（１）において、Constが一定値であるとすると、ＲＴＴの変動に係わってくるのは、Ｔqueということになる。このＴqueは、上記したように、キュー２１におけるキューイング遅延である。ＲＴＴが小さくなるのは、キューイング遅延が小さいときであり、ＲＴＴが大きくなるのは、キューイング遅延が大きいときである。すなわち、ＲＴＴの最小値ＲＴＴminは、ノード１２のキュー２１にパケットがないときに観測され、このとき、リンクの使用率は０となる。また、ＲＴＴの最小値ＲＴＴmin以外のＲＴＴotherは、ノード１２のキュー２１にパケットがあるときであり、このときのリンクの使用率は１である。
【００２６】
所定の時刻におけるＲＴＴminとＲＴＴotherが測定された回数を、それぞれＮminとＮotherとした場合、帯域使用率Ｕは、次式（３）で表される。
帯域使用率Ｕ＝Ｎother／（Ｎmin＋Ｎother）    ・・・（３）
遅延時間の確率密度関数における、最小値の出現確率が、そのリンクの使用できる帯域率Ａとなる。すなわち、使用できる帯域率Ａと帯域使用率Ｕの関係は次式（４）となる。
Ｕ＝１−Ａ    ・・・（４）
【００２７】
図１に示したように、１ホップの通信経路の場合、エンドホスト１１とエンドホスト１３の２点間の通信経路における帯域使用率は、１ホップ、すなわち、ノード１２の影響のみを考慮すれば良く、上記したようにして、帯域使用率Ｕなどを求めることができる。しかしながら、通常、図２に示すように、エンドホストからエンドホストまでの間には、複数のノードが存在し、複数のリンクが存在することになる。
【００２８】
図２に示したネットワークには、エンドホスト１１１とエンドホスト１１３との２点間を結ぶ通信経路上に、ノード１１２−１乃至１１２−Ｎが存在している。また、ノード１１２−１とノード１１２−２は、直接接続されているととともに、ノード１３１−１を介しても接続されている。また各ノードは、キュー１２１−１乃至１２１−Ｎ，１４１−１を備えている。以下の説明において、ノード１１２−１乃至１１２−Ｎを個々に区別する必要がない場合、単にノード１１２（ノード１３１−１も含む）と記載する。他の記載も同様に記載する。
【００２９】
図２に示したネットワークには、複数のノード１１２が存在し、複数のリンクが存在する。このような場合、ＲＴＴは、各ノード１１２のキューイング遅延の影響を受けることになる。そして、エンドホスト１１１とエンドホスト１１３との２点間のＲＴＴ、すなわち通信経路全体の遅延時間の確率密度関数の最小値の出現頻度は、各リンクにおける遅延時間の確率密度関数の最小値の出現頻度の積となる。エンドホスト１１１とエンドホスト１１３との２点間のＲＴＴは求めることができ、帯域使用率を推定することはできるが、個々のリンクの帯域使用率を推定することができない。
【００３０】
個々のリンクの帯域使用率を推定できないと効率の良い通信経路を推定することができない。例えば、ノード１１２−１とノード１１２−２の間のリンク（リンクＡとする）の帯域使用率が高く、ノード１１２−１からノード１３１−１を介してノード１１２−２へ行く経路のリンク（リンクＢとする）の帯域使用率が低いような場合を考える。このような場合、リンクＡが選択されて通信が行われるよりも、リンクＢが選択されて通信が行われる方が、効率的に通信を行えるが、リンクＡとリンクＢの帯域使用率をそれぞれ別個に推定できないため、リンクＡが選択されて通信が行われる可能性がある。効率的に通信が行われるようにするためには、個々のリンクの帯域使用率を推定できることが好ましい。
【００３１】
そこで、以下に説明するように帯域使用率を推定することで、個々のリンクの帯域使用率を推定することを可能とする。ここでは、図２に示したネットワークモデルのうち、図３に示したネットワークモデルを例にあげ、個々のリンクの帯域使用率の推定について説明を加える。図３に示したネットワークモデルは、エンドホスト１１１、ノード１１２−１乃至１１２−３から構成されている。
【００３２】
図３に示したネットワークモデルにおいては、エンドホスト１１１からノード１１２−１を介してノード１１２−２へのリンクと、ノード１１２−２からノード１１２−３へのリンクが存在している。エンドホスト１１１とノード１１２−２のリンクの遅延時間の確率密度関数をｆ（ｘ）とし、ノード１１２−２とノード１１２−３のリンクの遅延時間の確率密度関数をｇ（ｘ）とした場合、この２つのリンクを通過するエンドホスト１１１とノード１１２−３における遅延時間の確率密度関数は、ｈ（ｘ）となり、このｈ（ｘ）は、次式（５）で表すことができる。
【数１】
0005665048.tif 000002
【００３３】
式（５）より、確率密度関数ｈ（ｘ）は、確率密度関数ｆ（ｘ）と確率密度関数ｇ（ｘ）との畳み込み演算により算出できることがわかる。さらに、離散値定義される関数の場合、式（５）のように積分ではなく、次式（６）に示すような総和で定義することができる。
【数２】
0005665048.tif 000003
【００３４】
式（６）を、具体的に記載すると、以下のようになる。
h(0) = f(0)g(0)    ・・・（７−１）
h(1) = f(0)g(1) + f(1)g(0)    ・・・（７−２）
h(2) = f(0)g(2) + f(1)g(1) + f(2)g(0)    ・・・（７−３）
h(3) = f(0)g(3) + f(1)g(2) + f(2)g(1) + f(3)g(0)    ・・・（７−４）
・・・・・
h(n) = f(0)g(n) + f(1)g(n-1) +・・・+ f(n-1)g(1) + f(n)g(0)    ・・・（７―ｎ）
【００３５】
ここで、再度図３を参照する。エンドホスト１１１が、図３に示したネットワークの帯域使用率を推定する場合を考える。確率密度関数ｆ（ｘ）は、エンドホスト１１１を一方のエンドホストとし、ノード１１２-２を他方のエンドホストとし、エンドホスト１１１からノード１１２-２に対してPingを送る（ＲＴＴを測定する）ことで求めることができる。また同様に、確率密度関数ｈ（ｘ）は、エンドホスト１１１を一方のエンドホストとし、ノード１１２-３を他方のエンドホストとし、エンドホスト１１１からノード１１２-２に対してPingを送る（ＲＴＴを測定する）ことで求めることができる。
【００３６】
しかしながら、ノード１１２-２を一方のエンドホストとし、ノード１１２-３を他方のエンドホストとし、ノード１１２−２とノード１１２−３とのリンクの確率密度関数ｇ（ｘ）を、エンドホスト１１１が求めることはできない。このことは、例えば、図２に示したネットワークモデルにおいて、エンドホスト１１１とエンドホスト１１３との２点間の通信経路上に存在するノード１１２のうちの所定の２台のノード１１２のリンクにおける確率密度関数をエンドホスト１１１が求めることはできないことを示している。
【００３７】
ここで、式（７）を再度参照する。式（７−１）を変形すると、次式（８−１）になる。
ｇ（０）＝ｈ（０）／ｆ（０）    ・・・（８−１）
（但し、ｆ（０）は、０ではない。他の式においても同様とする）
また、同様に、式（７−２）を変形すると、次式（８−２）になる。
ｇ（１）＝（ｈ（１）―ｆ（１）ｇ（０））／ｆ（０）    ・・・（８−２）
【００３８】
式（８−１）から、ｇ（０）を求めることができる。上記したように、確率密度関数ｆ（ｘ）と確率密度関数ｈ（ｘ）は、エンドホスト１１１からPingを送信することで推定することができるため、確率密度関数ｆ（０）と確率密度関数ｈ（０）は求めることができ、その求められる確率密度関数ｆ（０）と確率密度関数ｈ（０）を式（８−１）に代入すれば、確率密度関数ｇ（０）を求めることができる。
【００３９】
また、同様に、式（８−２）から、確率密度関数ｇ（１）を求めることができる。式（８−２）において、確率密度関数ｈ（１）、確率密度関数ｆ（１）、確率密度関数ｆ（０）は、測定により求めることが可能であり、確率密度関数ｇ（０）は、式（８−１）から求めることが可能であるため、確率密度関数ｇ（１）も、式（８−２）から求めることが可能である。
【００４０】
このように、逆畳み込み演算を行うことで、所定のノード１１２間の確率密度関数ｇ（ｘ）を、エンドホスト１１１が求めることができる。すなわち、エンドホスト１１１にて、ネットワーク内の各リンクの確率密度関数ｇ（ｘ）を、個別に求めることができる。式（７−ｎ）を変形することで、次式（８−ｎ）を求めることができ、この式（８−ｎ）から、ネットワーク内の所定のリンクｎの確率密度関数ｇ（ｎ）を求めることができる。
【数３】
0005665048.tif 000004
【００４１】
このようにして、逆畳みこみ演算を行うことで推定された遅延時間の確率密度関数g(x) の最小値の統計をとることで、そのリンクで使用できる帯域率Ａを推定することができる。すなわち、エンドホスト１１１が直接求められない遅延時間の確率密度関数g(x) は、直接求めることができる確率密度関数ｈ（ｘ）と確率密度関数f(x) を観測し、逆畳みこみ演算を行うことで求めることができる。このような逆畳みこみ演算を、通信経路中の全リンクに対して行うことで、全リンクの帯域使用率Ｕ（帯域率Ａ）を推定することができ、通信経路の性能を推定することが可能となる。
【００４２】
ここで再度図３を参照する。エンドホスト１１１が、ノード１１２−２に対してPingを送信し、ＲＴＴを測定した場合、エンドホスト１１１から、ノード１１２−１を介してノード１１２−２にRequestパケットが送信される。そして、ノード１１２−２からノード１１２−１を介して、エンドホスト１１１にReplyパケットが送信される。ＲＴＴは、エンドホスト１１１において、Requestパケットを送信してからReplyパケットを受信するまでの時間である。よって、ＲＴＴには、ノード１１２−１において、Requestパケットが処理される時間（往路のキューイング遅延と称する）と、Replyパケットが処理される時間（復路のキューイング遅延と称する）が含まれる。
【００４３】
所定のノード間の確率密度関数ｇ（ｘ）を推定する際、往路のキューイング遅延と、復路のキューイング遅延を考慮する必要がある。例えば、往路のキューイング遅延と復路のキューイング遅延が異なるときがあるからである。ここでは特に復路のキューイング遅延を考慮した場合を説明する。
【００４４】
第１の実施の形態として、復路のキューイング遅延がないネットワークを考える。復路のキューイング遅延がないネットワークは、上記したようにして、確率密度関数ｇ（ｘ）を推定し、使用率などを推定するのに、最良の形態のネットワークである。復路のキューイング遅延がない場合、往路のキューイング遅延だけを考慮すればよいため、逆畳みこみ演算によって、復元したリンクの遅延時間の確率密度関数は往路のみのものであると仮定して処理することが可能である。よって、復元した確率密度関数の最小値の出現頻度から、そのリンクの帯域使用率を一意に推定できる。
【００４５】
第２の実施の形態として、復路のキューイング遅延が発生することを想定し、その復路のキューイング遅延ができるだけ発生しないように制御されることにより、復路のキューイング遅延がないネットワークと仮定して処理できるようにすることを考える。例えば、ICMP（Internet Control Message Protocol）のReplyパケットが、各ノードにおいて優先的に処理されるようにすることで実現する。通常、ノード１１２に受信されたパケットは、宛先アドレスに基づき次のノードの転送先が決定される。そして、そのパケットは出力インタフェースのキュー１２１（一時的な記憶領域）に格納される。受信されたパケットは、順次キュー１２１に格納されていく。
【００４６】
そして、電気信号もしく光信号に変換され送信されるまで、その領域に格納された状態とされる。これを通常処理もしくは通常制御と称する。仮に、パケットが大量に受信されると、このキューバッファ（キュー１２１）に大量のパケットが格納され、送信されるまでの遅延が生ずる。これが、上記してきたキューイング遅延となる。
【００４７】
一方、通常処理に対し優先処理と称する処理は、パケットヘッダに優先制御フラグが存在するパケットに対し、キュー１２１に格納せず、ただちに送信処理を行う処理のことである。キュー１２１にバッファリングされているパケットが存在しようとも、優先制御フラグがあるパケットは、ただちに送信処理されるため、キューイング遅延は発生しない状況を作り出すことができる。例えば、Replyパケットに、このような優先制御フラグを立てることで、Replyパケットは、受信されたノード１１２で優先的に処理されるため、復路でのキューイング遅延は発生しないことになる。
【００４８】
このReply パケットが優先処理に対応している状態を、ここではReply 優先モードと記述する。そして例えば、この優先制御を実現する手段としては、ＩＰパケットヘッダにTOS（Type Of Service、優先制御するか否かのフラグを記録する領域）フィールドにフラグを立てるといったことで実現できる。または、他の手段を用いても良い。
【００４９】
このようなReply優先モードを設け、処理されるようにすることで、仮に、Replyパケットを受信したノード１１２のキュー１２１に、パケットが既に格納されていても、それらの格納されているパケットよりも先に処理される制御することができ、結果として、復路のキューイング遅延が無い状態にすることができる。復路のキューイング遅延が無い状態と仮定して処理することができれば、第１の実施の形態と同じく、逆畳みこみ演算によって、復元したリンクの遅延時間の確率密度関数は往路のみのものであると仮定して処理することが可能となる。よって、この場合も、復元した確率密度関数の最小値の出現頻度から、そのリンクの帯域使用率を一意に推定できる。
【００５０】
第３の実施の形態として、往路と復路の経路が一致し、復路にもキューイング遅延がある場合を考える。往路と復路の経路が一致するとは、例えば、図２を参照するに、エンドホスト１１１から、ノード１１２−１、ノード１１２−２、・・・、ノード１１２−Ｎを介して、エンドホスト１１３に到達する往路の経路と、エンドホスト１１３から、ノード１１２−Ｎ、・・・、ノード１１２−２、ノード１１２−１を介して、エンドホスト１１１に到達する復路の経路が一致している場合である。
【００５１】
往路と復路の経路が一致し、復路にもキューイング遅延がある場合、逆畳みこみ演算することで復元されたリンクの遅延時間の確率密度関数は、そのリンクの往路と復路の遅延時間の確率密度関数が畳み込まれたものとなる。よって、復元された遅延時間の確率密度関数の最小値の出現頻度から、リンクの帯域使用率は特定することはできない。そこで、復元された遅延時間の確率密度関数ｈ（ｘ）(h(x) = (f＊g)(x))とし、その最小値の出現頻度ｈ（０）＝Ａとする。
【００５２】
帯域使用率Ｕは、０≦ Ｕ ≦ １ を満たすので、往路と復路における、確率密度関数の最小値の出現頻度は、
Ａ ≦ ｆ（０） ≦ １
Ａ ≦ ｇ（０） ≦ １
ｆ（０）ｇ（０）＝Ａ
の条件が満たされる。これらの条件から、往路、復路のいずれかの使用できる帯域率の最低値はＡであることになる。すなわち、往路または復路の帯域使用率は、１−Ａ を越えないということがわかる．帯域使用率は一意に推定できないが、往復路の最高の帯域使用率がわかるので、そのリンクの負荷の状況を推定することができる。
【００５３】
第４の実施の形態として、往路と復路の経路が一致せず、復路にもキューイング遅延がある場合を考える。往路と復路の経路が一致していない場合とは、図２に示したネットワークにおいて、往路は、ノード１１２−１からノード１１２−２にパケットが渡されたが、復路は、ノード１１２−２からノード１３１−１を介してノード１１２−１にパケットが渡されたような場合であり、このような経路のときには、往路と復路の経路が一致していないことになる。
【００５４】
第４の実施の形態においては、第３の実施の形態と同じく、特定のリンクの帯域使用率を一意に推定することは困難である。しかしながら、帯域使用率Ｕは、０≦ Ｕ ≦ １ を満たし、リンクのいずれも帯域使用率Ｕは、１−Ａ を越えることがない。よって、ネットワークに負荷が掛かっている箇所の特定はできるため、その負荷が掛かっている箇所を避けて通信を行うなどの制御を行うことが可能となる。
【００５５】
第５の実施の形態として、途中ノードのＩＰアドレスが不明なネットワークである場合を考える。途中ノードのＩＰアドレスが不明なネットワークに対して、ICMPのTrace Routeを用いることで、経路上に存在するノードのＩＰアドレスを特定することができる。Trace Route とは、送信元ホスト（たとえば、エンドホスト１１１）から指定した宛先ノード（たとえば、エンドホスト１１３）までの通信経路を調査することを意味する。まず送信元ホストは指定した宛先ノードまで、ＴＴＬが１のRequest パケットを送信する。ＴＴＬとは、パケットがノードを何回通過できるかの回数を表す。中継ノードにパケットが到着すると、その中継ノードにより、ＴＴＬの値が１だけ減算された値とされる。その結果、ＴＴＬの値が０になった場合、その中継ノードにより、送信元ホストに向かって宛先到達不能通知が送信されるとともに、当該パケットは破棄される。
【００５６】
宛先到達不能通知には、パケットを破棄した中継ノードのＩＰアドレスが記載されているため、そのパケットを受信した送信元ホストは、パケットを破棄した中継ノードのＩＰアドレスを取得することができる。このような宛先到達不能通知が受信されると、送信元ホストは、ＴＴＬを１だけ増やした値のパケットを送信する。このようにパケットを送信することで、パケットを破棄した中継ノードの次の中継ノードのＩＰアドレスを取得することができる。通信経路上の各中継ノードから、このような宛先到達不能通知を順次受信することで、送信元ホストは、経路上の各中継ノードのＩＰアドレスを取得する。なお、ここでは、Trace Routeを例にあげて説明を続けるが、通信経路上の中継ノードのＩＰアドレスを取得する方法が、Trace Routeに限定されることを示す記載ではなく、他の方法により、通信経路上の中継ノードのＩＰアドレスが取得されるような場合であっても、本発明を適用することはできる。
【００５７】
このように、通信経路のエンドホスト（送信元ホスト）は、もう一方のエンドホスト（宛先ノード）に向かって、ＴＴＬ（初期値１）が小さいRequest パケットを複数回送信する。そして、ＴＴＬの値を１ずつ増加させるたびに複数回パケットが送信され、順次中継ノードのＩＰアドレスが取得される。このような処理が、宛先ノードからReply パケットが届くまで繰り返される。この処理によれば、ＩＰアドレスの不明なネットワークにおいて、通信経路上の中継ノードのＩＰアドレスが取得できるだけでなく、途中ノードから、順々にＴＴＬ切れの宛先到達不能通知が送信元ホストに届くので、送信元ホストと各中継ノード間のＲＴＴの遅延時間の確率密度関数も同時に取得できることになる。確率密度関数が取得できるので、第１の実施の形態乃至第４の実施の形態と同じく、逆畳み込み演算により、リンクの帯域使用率や負荷の状況を推定することができる。
【００５８】
次に、エンドホストや各中継ノードにおける処理について説明する。図４に示したネットワークモデルを用いて説明する。図４において、エンドホスト１１１を送信側のホスト（帯域使用率を算出するホスト）とし、エンドホスト１１３を最終的な宛先ノードとし、ノード１１２を中継ノードとする。ここで、エンドホスト１１３を最終的な宛先ノードと記載したのは、以下に説明するように、中継ノードが順次宛先ノードに設定されて処理され、最終的な宛先ノードがエンドホスト１１３であるからである。エンドホスト１１１は、送信処理部１５１と受信処理部１５２を備える。ノード１１２は、送受信処理部１６１を備える。エンドホスト１１３は、送受信処理部１７１を備える。
【００５９】
まず、図５のフローチャートを参照し、エンドホスト１１１が行う処理について説明する。図５のフローチャートを参照して説明するエンドホスト１１１が行う処理は、宛先ノードまでの通信経路上の中継ノードのＩＰアドレスがわかっている状態のときに行われる処理である。換言すれば、Trace Routeを用いないときの、送信側のホストが行う送信時の処理である。さらに換言すれば、第１乃至第４の実施の形態に該当するときの送信元ホストが実行する処理である。
【００６０】
ステップＳ１１において、送信処理部１１１は、中継ノードのうち、所定のノード１１２を宛先ノードに設定し、そのノードのアドレスをセットする。送信側のホストであるエンドホスト１１１は、エンドホスト１１３までの通信経路上に存在するノードのアドレスを認識している。そして、その通信経路上に存在し、帯域使用率を推定したいリンクの両端のノードの全てを、順次宛先ノードに設定し、Requestパケットを送信する。そのような処理を行うため、ステップＳ１１においては、まだRequestパケットを送信していない通信経路上のノードのうち、１つのノードが選択され、宛先ノードに設定されるという処理が行われる。また、同一の宛先ノードに複数回Requestパケットを送信するため、アドレスがセットされる。
【００６１】
ステップＳ１２において、Replyパケット優先モードにするか否かが判断される。Replyパケット優先モードとは、上記したように、Replyパケットを中継ノードにおいて、他のパケットよりも優先して処理するように指示するためのモードであり、復路のキューイング遅延を考慮しなくても処理できるようにしたときなどに設定されるモードである。ステップＳ１２において、Replyパケット優先モードにすると判断された場合、ステップＳ１３に処理が進められ、Replyパケット優先モードにはしないと判断された場合、ステップＳ１３の処理はスキップされ、ステップＳ１４の処理に進められる。
【００６２】
ステップＳ１３において、Requestパケットヘッダに優先制御フラグが立てられる。Requestパケットヘッダに優先制御フラグが立てられた場合、上記したように、そのRequestパケットに対するReplyパケットは、各ノードにおいて優先的に処理される。ステップＳ１３において、Requestパケットヘッダに優先制御フラグが立てられた場合、または、ステップＳ１２において、Replyパケット優先モードにしないと判断された場合、ステップＳ１４に処理が進められる。ステップＳ１４において、Requestパケットが、セットされているアドレスを有する宛先ノードに対して送信され、その送信時刻が記録される。エンドホスト１１１は、記憶部（不図示）を有し、送信時刻を記憶する。記憶部としては、メモリ、ハードディスクなどを用いることが可能である。
【００６３】
ステップＳ１５において、所定の回数、同一の宛先ノードにRequestパケットを送信したか否かが判断される。所定の回数は、その宛先ノードに関するＲＴＴの遅延時間の確率分布を得るのに十分な回数とされる。この所定の回数は、Ｎ回などと予め設定された固定値であっても良いし、確率分布を得るのに十分な結果が得られたと判断された時点までの回数とする可変値であっても良い。ステップＳ１５において、所定の回数、同一の宛先ノードにRequestパケットを送信はしていないと判断された場合、ステップＳ１２に処理が戻され、それ以降の処理が実行される。
【００６４】
なお、ここでは、ステップＳ１２に処理が戻されるとして説明を続けるが、ステップＳ１３またはステップＳ１４に処理が戻されるようにしても良い。ステップＳ１２に処理が戻されることで、同一の宛先ノードに対して、Requestパケット優先モードでパケットを送信したり、Requestパケット優先モードでない状態でパケットを送信したりすることができるため、例えば、ｘ回、Requestパケット優先モードで送信し、ｙ回、Requestパケット優先モードではないモードで送信するといった使い分けを行うことが可能となる。また、モードを変えることで、復路の影響を計測することも可能となり、計測される復路の影響を、何らかの推測に用いるといったことも可能となる。
【００６５】
ステップＳ１３またはステップＳ１４に処理が戻されるようにした場合、同一の宛先ノードには、同一のモードでRequestパケットが送信されることになる。よって、Requestパケット優先モードに設定された場合には、ステップＳ１３に処理が戻され、Requestパケット優先モードに設定されていない場合には、ステップＳ１４に処理が戻される。
【００６６】
一方、ステップＳ１５において、所定の回数、同一の宛先ノード（中継ノード）にRequestパケットを送信したと判断された場合、ステップＳ１６に処理が進められる。ステップＳ１６において、通信経路上の宛先として設定したい全ノードに対して、Requestパケットを送信したか否かが判断される。宛先として設定したい全ノードとは、帯域使用率を推定したい全リンクの両端に位置するノードのことである。ステップＳ１６において、通信経路上の宛先として設定したい全ノードに対して、Requestパケットを送信していないと判断された場合、ステップＳ１７に処理が進められる。ステップＳ１７において、通信経路上の中継ノードのうち、宛先ノードに設定していない中継ノードのうちの１つが選択され、その選択されたノードが新たな宛先ノードとして設定される処理が実行される。そして、新たに設定された宛先ノードに対して、ステップＳ１２以降の処理が繰り返される。
【００６７】
このようにして、通信経路上の宛先として設定したい全ノードに対して、Requestパケットが、複数回送信される。エンドホスト１１１は、Requestパケットを送信することにより、宛先ノードからReplyパケットを受信する。この受信に関する処理および受信後に行われる処理に関して、図６のフローチャートを参照して説明する。
【００６８】
図６のフローチャートは、エンドホスト１１１（送信側のホストであり、リンクの帯域使用率などを測定するホスト）の受信処理部１５２が行う処理である。ステップＳ３１において、宛先ノードに設定されているノードからReplyパケットが受信される。ステップＳ３２において、Replyパケットの受信時刻が記録される。そして、ステップＳ３３において、ＲＴＴが算出され、記録される。ＲＴＴが算出され、記憶されると、ステップＳ３４において、宛先ノードが変更されたか否かが判断される。この判断は、例えば、ステップＳ１５（図５）において、所定の回数、同一の宛先ノードにRequestパケットを送信したと判断され、ステップＳ１６に処理が進められたとき、ステップＳ３４において宛先ノードが変更されたと判断される。
【００６９】
エンドホスト１１１は、図５のステップＳ１４における処理で、宛先ノードにRequestパケットを送信するため、そのRequestパケットを受信した宛先ノードから、Replyパケットを受信する。またエンドホスト１１１は、Requestパケットを送信した送信時刻と、そのRequestパケットに対応するReplyパケットの受信時刻を記録しているため、その送信時刻と受信時刻の差分を計算することで、ＲＴＴを算出することができる。また、同一の宛先ノードに、所定の回数、Requestパケットを送信しているため、所定の回数分だけ、同一の宛先ノードに対するＲＴＴが算出される。複数のＲＴＴが算出されることで、ＲＴＴの確率分布を算出することが可能な状態となる。
【００７０】
ステップＳ３４において、宛先ノードが変更されたと判断された場合、ステップＳ３５に処理が進められる。ステップＳ３５において、ＲＴＴの遅延時間の確率分布が算出され、記録される。この処理は、その時点で処理対象とされている１つの宛先ノードに対して行われる。すなわち、ステップＳ３１乃至Ｓ３４の処理が繰り返されることで、１つの宛先ノードに対する複数のＲＴＴが算出される。そして、その複数のＲＴＴの度数分布が取られることで、その宛先ノードに関するＲＴＴの遅延時間の確率分布が算出される。
【００７１】
ステップＳ３６において、宛先として設定した全ての中継ノードに対するＲＴＴの遅延時間の確率分布が算出されたか否かが判断される。通信経路上に存在する、帯域使用率を推定したいリンクの両端の全中継ノードに対して、Requestパケットが複数回送信されているため、通信経路上に存在する、帯域使用率を推定したいリンクの両端の中継ノード毎に、ＲＴＴの遅延時間の確率分布が算出される。よって、指定した全ての中継ノードのＲＴＴの遅延時間の確率分布が算出されたか否かが、ステップＳ３６において判断される。なお、ステップＳ３１乃至３４の処理と、ステップＳ３５，Ｓ３６の処理は、並列処理される。すなわち、ステップＳ３１乃至Ｓ３４の処理が実行されることで、所定の中継ノードに関するＲＴＴが収集され、ステップＳ３５，Ｓ３６の処理が実行されることで、中継ノード毎のＲＴＴの遅延時間の確率分布が算出される。
【００７２】
ステップＳ３６において、指定した全ての中継ノードに対するＲＴＴの遅延時間の確率分布が算出されたと判断された場合、ステップＳ３７に処理が進められる。ステップＳ３７において、逆畳み込み演算が実行され、リンク間の遅延時間の確率分布が復元される。ステップＳ３６までの処理で、上述した確率密度関数ｆ（ｘ）、確率密度関数ｈ（ｘ）が求められているため、ステップＳ３７においては、式（８）に基づき、確率密度関数ｇ（ｘ）が求められる。そして、ステップＳ３８において、帯域使用率が推定され、記録される。そして、ステップＳ３９において、帯域資料率を推定したい全てのリンクに対して帯域使用率が推定されたか否かが判断され、推定されていないと判断された場合、ステップＳ３７に処理が戻され、それ以降の処理が繰り返され、推定されたと判断された場合、処理は終了される。
【００７３】
帯域使用率は、上記したように、帯域使用率Ｕ＝１−Ａで算出することができる。またＡは、使用できるリンクの割合であり、ＲＴＴminから算出できる値である。所定のリンクのＲＴＴminは、所定のリンクの確率密度関数ｇ（ｘ）が求められた時点で算出されており、その算出されている値を用いることができる。よって、所定のリンクにおける確率密度関数ｇ（ｘ）が算出されることで、所定のリンクにおける帯域使用率を算出することができる。このようにして、本発明によれば、所定のリンクの帯域使用率などを、その所定のリンク外のホストが推定することができる。
【００７４】
次に、中継ノードの処理について、図７のフローチャートを参照して説明する。中継ノードは、エンドホスト１１１とエンドホスト１１３との間の通信経路上に存在するノード１１２であり、順次、エンドホスト１１１により宛先ノードに設定されるノードとの間に存在するノードである。例えば、図２において、宛先ノードがノード１１２−Ｎに設定されている場合、中継ノードは、ノード１１２−１乃至１１２−Ｎ−１の各ノードとなる。ここでは、中継ノードは、ノード１１２（図５）であり、図７のフローチャートの処理は、ノード１１２の送受信処理部１６１が行うとして説明を続ける。また、図７のフローチャートの処理は、Trace Routeが用いられていないときの処理である。
【００７５】
ステップＳ５１において、パケットを受信する。ステップＳ５１において受信されるパケットは、RequestパケットまたはReplyパケットである。ステップＳ５２において、受信されたパケットのパケットヘッダに、優先制御フラグがあるか否かが判断される。受信されたパケットが、Replyパケットである場合、そのReplyパケットのパケットヘッダに、Replyパケット優先モードであるときには、優先制御フラグが立てられている。よって、そのようなフラグが立てられているか否かが、ステップＳ５２において判断される。
【００７６】
ステップＳ５２において、パケットヘッダに優先制御フラグが立てられていないと判断された場合、ステップＳ５３に処理が進められ、その受信されたパケットは、通常処理される。一方、ステップＳ５２において、パケットヘッダに優先制御フラグが立てられていると判断された場合、ステップＳ５４に処理が進められ、その受信されたパケットは、優先処理される。通常処理、または優先処理されたパケットは、次のノード１１２に対して転送される。このように、中継ノードの基本的な処理は、受信されたパケットを次のノードに転送する処理である。
【００７７】
次に、図８のフローチャートを参照して、宛先ノードにおける処理について説明する。宛先ノードは、エンドホスト１１１と宛先ノードとの間の通信経路上に存在するノード１１２と、エンドホスト１１３のうちのいずれか１つが設定される。図８のフローチャートの処理は、ノード１１２が宛先ノードとして設定されているときには、ノード１１２の送受信処理部１６１が実行する処理であり、エンドホスト１１３が宛先ノードとして設定されているときには、エンドホスト１１３の送受信処理部１７１が実行する処理である。
【００７８】
ステップＳ７１において、Requestパケットが受信される。ステップＳ７２において、受信されたRequestパケットのパケットヘッダに、優先制御フラグが立てられているか否かが判断される。ステップＳ７２において、Requestパケットのパケットヘッダに、優先制御フラグが立てられていると判断された場合、ステップＳ７３に処理が進められる。ステップＳ７３において、送信されるReplyパケットのパケットヘッダに、優先制御フラグが立てられる。
【００７９】
ステップＳ７３において優先制御フラグが立てられたReplyパケットは、ステップＳ７４において、送信元ホスト、この場合、エンドホスト１１１に対して送信される。一方、ステップＳ７２において、Requestパケットのパケットヘッダに、優先制御フラグは立てられていないと判断された場合、優先フラグが立てられていないReplyパケットが生成され、ステップＳ７４において、送信元ホストに対して送信される。
【００８０】
このように、宛先ノードに設定されているノード１１２（エンドホスト１１３）は、受信されたRequestパケットに、優先制御フラグが立てられているときには、優先制御フラグを立てたReplyパケットを生成し、送信し、優先制御フラグが立てられていないときには、優先制御フラグを立てないReplyパケットを生成し、送信する処理を、Requestパケットを受信する毎に実行する。
【００８１】
上記した処理は、Trace Routeを用いていないときの送信元ホストの処理、中継ノードの処理、および宛先ノードの処理であった。次に、Trace Routeを用いていないときの送信元ホストの処理、中継ノードの処理、および宛先ノードの処理について説明する。まず、図９のフローチャートを参照し、送信元ホスト（エンドホスト１１１）における送信時の処理について説明する。
【００８２】
Trace Route が用いられる場合、通信経路中の各ノードのアドレスはわからない状態であり、一方のエンドホスト１１３（宛先ホスト）のアドレスはわかっている状態である。そして、そのような状態のときに、送信元ホストは、宛先ホスト（エンドホスト１１３）に対して，Trace Route を実行する。Trace Route が用いられない送信処理（図５のフローチャートを参照して説明した処理）では通信経路上の各ノードのアドレスが順次指定されてRequestパケットが送信されたが、Trace Routeが用いられた処理では宛先ホストのアドレスは固定され、その宛先ホストはエンドホスト１１３とされ、アドレスが変更されない状態でRequestパケットが送信される点が異なる。図５のフローチャートを参照して説明した処理と同一の処理については、適宜説明を省略する。
【００８３】
まずステップＳ９１において、ＴＴＬの値が１に設定（初期設定）される。ステップＳ９２において、宛先ノードのアドレスが設定される。この場合、エンドホスト１１３のアドレスが設定される。設定されたアドレスは、処理が終了するまで、Requestパケットの送信先のアドレスとされる。ステップＳ９３において、Replyパケット優先モードにするか否かが判断され、優先モードにすると判断された場合、ステップＳ９４に処理が進められ、パケットヘッダに、優先制御フラグが立てられたRequestパケットが生成され、ステップＳ９５に処理が進められる。
【００８４】
一方ステップＳ９３において、Replyパケット優先モードにしないと判断された場合、ステップＳ９４の処理はスキップされ、ステップＳ９５に処理が進められる。ステップＳ９５において、Requestパケットが生成される。その生成されるRequestパケットのパケットヘッダにセットされるＴＴＬは、その時点で設定されている値とされる。ステップＳ９１から処理が来た場合、ＴＴＬ＝１に設定されているため、ＴＴＬが１に設定されたRequestパケットが生成される。
【００８５】
ステップＳ９６において、生成されたRequestパケットが宛先ノードに送信され、その送信した時刻が記録される。そして、ステップＳ９７において、所定の回数、同一のノードに対して、Requestパケットが送信されたか否かが判断される。この場合、宛先ノードは、エンドホスト１１３であり、固定とされているため、エンドホスト１１３に対してRequestパケットが送信されることになるが、ＴＴＬとして設定されている値が同一の値とされている間、エンドホスト１１１とエンドホスト１１３との２点間の通信経路上にある所定のノード１１２に対してRequestパケットが送信されることになる。よって、所定の回数、同一のノードに対して、Requestパケットを送信することができる。
【００８６】
ステップＳ９７において、所定の回数、同一のノードに対して、Requestパケットが送信されてはいないと判断された場合、ステップＳ９３に処理が戻され、それ以降の処理が繰り返され、送信されたと判断された場合、ステップＳ９８に処理が進められる。ステップＳ９３乃至Ｓ９７の処理が繰り返されることにより、同一のノードに複数回、Requestパケットが送信されることになる。
【００８７】
ステップＳ９８において、宛先ノードからのReplyパケットを受信したか否かが判断される。この場合、宛先ノードは、エンドホスト１１３であるため、エンドホスト１１３からのReplyパケットが受信されたか否かが判断される。なお、エンドホスト１１３以外のノードからのReplyパケットは、宛先到達不能通知パケットであるため、そのような宛先到達不能通知パケットではないか否かを判断することで、ステップＳ１６の処理が行われるようにしても良い。宛先ノードからのReplyパケットは受信していないと判断されるのは、エンドホスト１１３にRequestパケットが到達していないときである。
【００８８】
ステップＳ９８において、宛先ノードからのReplyパケットは受信していないと判断された場合、ステップＳ９９に処理が進められ、ＴＴＬの値が１だけ増加される。ステップＳ９９において、ＴＴＬの値が１だけ増加されると、ステップＳ９３に処理が戻され、それ以降の処理が繰り返される。ステップＳ９３乃至９９の処理が繰り返されることにより、エンドホスト１１１に近い側のノードから順次、Requestパケットが複数回送信されることになる。
【００８９】
このようなTrace Routeが用いられて送信元ホスト（エンドホスト１１１）の送信に係わる処理が実行された場合、受信に係わる処理は、図６のフローチャートの処理に基づき行われる。すなわち、Trace Routeが用いられた場合と、Trace Routeが用いられていない場合とでは、送信時の処理は異なるが、受信時の処理は同一の処理とされる。すなわち、Trace Routeが用いられた場合であっても、同一のノードから、複数回、Replyパケット（宛先到達不能通知パケット）受信されるため、各ノードにおけるＲＴＴの遅延時間に関する確率密度関数を算出することができる。よって、受信時の処理として、同一の処理を行えば、所定のリンクの帯域使用率を推定することができる。
【００９０】
Trace Routeが用いられた場合、中継ノードにおける処理が、Trace Routeが用いられていない場合と比較して異なる処理を含むため、次に、図１０を参照して、Trace Routeが用いられたときの中継ノードの処理について説明する。中継ノードは、図４において、ノード１１２であり、図１０のフローチャートの処理は、ノード１１２の送受信処理部１６１が行う。
【００９１】
ステップＳ１１１において、Requestパケットが受信される。ステップＳ１１２において、受信されたRequestパケットに含まれるＴＴＬの値が１だけ減算された値とされる。その結果、ＴＴＬが０になったか否かがステップＳ１１３において判断される。ステップＳ１１３において、ＴＴＬが０にはなっていないと判断された場合、ステップＳ１１４に処理が進められ、受信されたパケットは、通常処理される。すなわち、ステップＳ１１５において、次ノードに転送される処理が実行される。
【００９２】
一方、ステップＳ１１３において、ＴＴＬは０になったと判断された場合、ステップＳ１１６に処理が進められる。ステップＳ１１６において、宛先到達不能通知パケットが生成される。ステップＳ１１７において、受信されたRequestパケットのパケットヘッダに優先制御フラグが立っているか否かが判断される。ステップＳ１１７において、優先制御フラグが立っていると判断された場合、ステップＳ１１８に処理が進められる。ステップＳ１１８において、宛先到達不能通知パケットのパケットヘッダに、優先制御フラグが立てられる。
【００９３】
ステップＳ１１８において、優先フラグが立てられた宛先到達不能通知パケットが生成された場合、または、ステップＳ１１７において、優先制御フラグは立てられていないと判断された場合、ステップＳ１１９において、送信元ホストに対して、宛先到達不能通知パケットが送信される。そして、宛先到達不能通知パケットが送信されたときには、受信されたRequestパケットはステップＳ１２０において破棄される。
【００９４】
このように、Trace Routeが適用されているときに、Requestパケットを受信した中継ノードは、ＴＴＬの値が０になったときに、宛先到達不能通知パケットを生成し、送信元ホストに送信するといった処理を行う。宛先到達不能通知パケットには、宛先到達不能通知パケットを生成した中継ノードのＩＰアドレスが含まれるため、そのような宛先到達不能通知パケットを受信した送信元ホストにおいては、中継ノードのＩＰアドレスを知ることができる。よって、宛先ノードまでの通信経路上に存在する中継ノードのＩＰアドレスを調べながら、ＲＴＴを得ることができ、リンク毎の帯域使用率などを推定することが可能となる。
【００９５】
なお、上述した説明においては、通信経路上のノードのアドレスが不明なネットワークに対して、ＴＴＬの値を順次増やすことで、ＩＰアドレスを順次調べ、同一の値のＴＴＬを複数回送信することで、ＲＴＴの確率密度関数を求め、所定のリンクの帯域使用率を求めるとして説明した。
【００９６】
他の実施の形態として、通信経路上のノードのＩＰアドレスが不明なネットワークに対して、上記したようにＴＴＬの値を順次増やすことで、中継ノードのＩＰアドレスを順次調べ、経路上の全てのノードのＩＰアドレスを調べ終わった後に、その調べ上げたＩＰアドレスを用いて、ＩＰアドレスがわかっているネットワークに対する処理、すなわち、図５乃至図８のフローチャートの処理がホストやノードにおいて行われることで、ＲＴＴの確率密度関数が求められ、所定のリンクの帯域使用率が求められるようにしても良い。
【００９７】
本発明を適用することで、Ping をエンドホストや通信経路上に存在する各ノードに送るという簡便な処理だけで、各ノードに対するＲＴＴの遅延時間の確率密度関数が取得でき、それを逆畳み込み演算することで、通信経路中の各リンクの帯域使用率を推定することができる。すなわち、本発明によれば、Pingという簡便なものを用いて、通信経路中の各リンクの帯域使用率を推定することができる。
【００９８】
［記録媒体について］
上述した一連の処理は、ハードウエアにより実行することもできるし、ソフトウエアにより実行することもできる。一連の処理をソフトウエアにより実行する場合には、そのソフトウエアを構成するプログラムが、コンピュータにインストールされる。ここで、コンピュータには、専用のハードウエアに組み込まれているコンピュータや、各種のプログラムをインストールすることで、各種の機能を実行することが可能な、例えば汎用のパーソナルコンピュータなどが含まれる。
【００９９】
図１１は、上述した一連の処理をプログラムにより実行するコンピュータのハードウエアの構成例を示すブロック図である。コンピュータにおいて、ＣＰＵ（Central Processing Unit）２０１、ＲＯＭ（Read Only Memory）２０２、ＲＡＭ（Random Access Memory）２０３は、バス２０４により相互に接続されている。バス２０４には、さらに、入出力インタフェース２０５が接続されている。入出力インタフェース２０５には、入力部２０６、出力部２０７、記憶部２０８、通信部２０９、およびドライブ２１０が接続されている。
【０１００】
入力部２０６は、キーボード、マウス、マイクロフォンなどよりなる。出力部２０７は、ディスプレイ、スピーカなどよりなる。記憶部２０８は、ハードディスクや不揮発性のメモリなどよりなる。通信部２０９は、ネットワークインタフェースなどよりなる。ドライブ２１０は、磁気ディスク、光ディスク、光磁気ディスク、または半導体メモリなどのリムーバブルメディア２１１を駆動する。
【０１０１】
以上のように構成されるコンピュータでは、ＣＰＵ２０１が、例えば、記憶部２０８に記憶されているプログラムを、入出力インタフェース２０５およびバス２０４を介して、ＲＡＭ２０３にロードして実行することにより、上述した一連の処理が行われる。
【０１０２】
コンピュータ（ＣＰＵ２０１）が実行するプログラムは、例えば、パッケージメディア等としてのリムーバブルメディア２１１に記録して提供することができる。また、プログラムは、ローカルエリアネットワーク、インターネット、デジタル衛星放送といった、有線または無線の伝送媒体を介して提供することができる。
【０１０３】
コンピュータでは、プログラムは、リムーバブルメディア２１１をドライブ２１０に装着することにより、入出力インタフェース２０５を介して、記憶部２０８にインストールすることができる。また、プログラムは、有線または無線の伝送媒体を介して、通信部２０９で受信し、記憶部２０８にインストールすることができる。その他、プログラムは、ＲＯＭ２０２や記憶部２０８に、予めインストールしておくことができる。
【０１０４】
なお、コンピュータが実行するプログラムは、本明細書で説明する順序に沿って時系列に処理が行われるプログラムであっても良いし、並列に、あるいは呼び出しが行われたとき等の必要なタイミングで処理が行われるプログラムであっても良い。
【０１０５】
また、本明細書において、システムとは、複数の装置により構成される装置全体を表すものである。
【０１０６】
なお、本発明の実施の形態は、上述した実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲において種々の変更が可能である。
【符号の説明】
【０１０７】
１１１  エンドホスト、  １１２  ノード、  １１３  エンドホスト、  １２１  キュー、  １３１  ノード、  １４１  キュー、  １５１  送信処理部、  １５２  受信処理部、  １６１  送受信処理部、  １７１  送受信処理部
【図１】
0005665048.tif 000005
【図２】
0005665048.tif 000006
【図３】
0005665048.tif 000007
【図４】
0005665048.tif 000008
【図５】
0005665048.tif 000009
【図６】
0005665048.tif 000010
【図７】
0005665048.tif 000011
【図８】
0005665048.tif 000012
【図９】
0005665048.tif 000013
【図１０】
0005665048.tif 000014
【図１１】
0005665048.tif 000015