(57)【特許請求の範囲】
【請求項１】
少なくとも１つのノードを有する複数のシステムがネットワークを介して分散配置される環境において、発信元ノードから送信先ノードに送信されるデータのネットワーク上の経路、及び送信先ノードから発信元ノードに返信されるデータのネットワーク上の経路を選択する経路選択システムにおいて、該送信先ノードのサービスを要求するために、該発信元ノードから該送信先ノードに対してサービス要求メッセージを送信する場合に、該発信元ノードと該送信先ノードとの間を接続可能な各経路について、予測情報を用いて、それぞれ予測応答時間を求め、該予測応答時間が最小となる経路を使用して、該サービス要求メッセージを送信する経路算出手段と、該経路算出手段の該サービス要求メッセージの送信に応じて、少なくとも該送信を行った経路、及び該サービス要求メッセージの要求データ長を含む、そのサービス要求メッセージの送信に関する情報を応答情報として記憶し、該送信先ノードから、該発信元ノードに該サービス要求メッセージに対する応答を受信する場合に、少なくともその応答の応答データ長、及び該サービス要求メッセージの送信時からの応答時間に関する値を含む、その応答の受信に関する情報を更に該応答情報として記憶する応答情報管理手段と、該応答情報管理手段の該応答の受信に応じて、該応答情報に基づいて、該予測情報の内容を更新する予測情報管理手段と、を有することを特徴とする経路選択システム。
【請求項２】
前記応答時間に関する値が、単位データ長あたりの応答時間を示す実応答時間であり、該実応答時間が計算式：実応答時間＝（２・応答時間）／（要求データ長＋応答データ長）
により求められることを特徴とする請求項１に記載の経路選択システム。
【請求項３】
少なくとも１つのノードを有する前記システムが、該システムごとに、前記予測情報を有し、該予測情報が少なくとも１つの応答時間予測オブジェクトを有し、該応答時間予測オブジェクトがそれぞれ、染色体、及び適合度を意味するビット列を有し、該染色体が応答時間予測関数のパラメータに対応する少なくとも１つの遺伝子ブロックを有し、前記予測情報管理手段が、前記サービス要求メッセージに対する応答を受信した際に、該染色体を世代交代させる世代交代手段を有し、該世代交代手段が、該応答時間予測オブジェクト内の各遺伝子ブロックからなる該応答時間予測関数のパラメータを用いて予測応答時間を計算し、最適な応答時間の予測を行った応答時間予測オブジェクトほど前記適合度を大きい値に設定し、前記適合度の値が大きいほど前記応答時間予測オブジェクトの寿命の値を長く設定する適合度計算手段と、寿命に達した応答時間予測オブジェクトを判定し、その応答時間予測オブジェクトを削除する応答時間予測オブジェクト削除手段と、該応答時間予測オブジェクト削除手段によって削除された応答時間予測オブジェクトを補完すべく新たな応答時間予測オブジェクトを生成するために、既存の応答時間予測オブジェクトを、適合度の高いものほど高い確率で選択されるようにして複数選択し、その中の応答時間予測オブジェクトの染色体に対して所定の確率で、遺伝的オペレータを行う応答時間予測オブジェクト生成手段とを有し、該世代交代手段による世代交代処理を繰り返すことによって、動的に最適な応答時間の予測を行うことができるように該応答時間予測オブジェクトを進化させ、最適な経路の予測を自律的に行わせることを特徴とする請求項１に記載の経路選択システム。
【請求項４】
前記予測情報、及び前記応答情報を含む複数のスクールのそれぞれが、少なくとも１つの前記予測情報管理手段に対応づけられ、該予測情報管理手段内の前記世代交代手段において、前記適合度計算手段が、該予測応答時間の計算の際に、他のスクール内の該応答情報を使用することができ、前記応答時間予測オブジェクト生成手段が、対応する前記スクールに対して、新たな応答時間予測オブジェクトを生成において、既存の応答時間予測オブジェクトを選択する際に、他のスクール内の応答時間予測オブジェクトを選択することができ、他のスクールが対応づけられている予測情報管理手段の属するシステムとの間で協調的に通信負荷を分散して経路を予測することを特徴とする請求項３に記載の経路選択システム。
【請求項５】
前記予測応答時間が、複数の応答の受信によって得られた複数の応答情報内の実応答時間及びその実応答時間が計測された時刻と、前記応答時間予測オブジェクト内の各遺伝子ブロックに記憶された、実応答時間が計測された時刻の新しさに関する係数、予測対象経路と実応答時間の計測された経路の距離に関する係数、及び予測対象経路と実応答時間の計測された経路のそれぞれの経路上の各ノードに関するアドレス情報の部分的な、距離に関する重み付けを表す係数と、実応答時間が計測された時刻の新しさに関する定数、及び予測対象経路と実応答時間の計測された経路の距離に関する定数を基に計算されることを特徴とする請求項３または４に記載の経路選択システム。
【請求項６】
前記適合度が、前記予測応答時間と、複数の応答の受信によって得られた複数の応答情報内の実応答時間及びその実応答時間が計測された時刻と、前記応答時間予測オブジェクト内の各遺伝子ブロックに記憶された、実応答時間が計測された時刻の新しさに関する係数と、実応答時間が計測された時刻の新しさに関する定数を基に計算されることを特徴とする請求項５に記載の経路選択システム。
【請求項７】
前記予測応答時間が、複数の応答の受信によって得られた複数の応答情報内の実応答時間ＲＴｉ（ｉ＝１〜Ｎ）及びその実応答時間が計測された時刻、並びに前記応答時間予測オブジェクト内の各遺伝子ブロックに記憶された、最新性影響係数(cnew)、距離影響係数(cdist) 、４つのサブネットワーク間距離影響係数(csnet1,csnet2,csnet3,csnet4) を用いて、
【数１】
0003665460.tif 000011
によって求められ、ここでＲＩＲi ＝ｅ(-C1・ cnew ・ TAi)（Ｃ１は正の定数、ＴＡi は該予測応答時間計算時刻からｉ番目の実応答時間が計測された時刻を差し引いた値である）、ＤＩＲi ＝１／(C2 ・ｅ-C3 ・ cdist ・ＤＥi+1)（Ｃ２及びＣ３は正の定数である）
【数２】
0003665460.tif 000012
（ｉ番目の該応答情報の経路上の各ノードの番号をｊとし、発信元ノード、送信先ノードを含む該経路上のノード数をＭとし、予測対象の経路上のｊ番目のノードのＩＰアドレスをＴ１ｊ．Ｔ２ｊ．Ｔ３ｊ．Ｔ４ｊとし、該応答情報の経路上の各ノードのｊ番目のＩＰアドレスをＲ１ｉｊ．Ｒ２ｉｊ．Ｒ３ｉｊ．Ｒ４ｉｊとする））
Ｃｋ＝ｅ-C4 ・ csnetk（Ｃ４は正の定数）
であることを特徴とする請求項５に記載の経路選択システム。
【請求項８】
前記適合度が、複数の応答の受信によって得られた複数の応答情報内の実応答時間ＲＴｉ（ｉ＝１〜Ｎ）及びその実応答時間が計測された時刻、並びに前記応答時間予測オブジェクト内の各遺伝子ブロックに記憶された、最新性影響係数(cnew)を用いて、
【数３】
0003665460.tif 000013
を用いて求められ、ここでＲＩＲi ＝ｅ(-C1・ cnew ・ TAi)（Ｃ１は正の定数、ＴＡi は該予測応答時間計算時刻からｉ番目の実応答時間ＲＴi が計測された時刻を差し引いた値である）、ｄＲＴi は、ｉ番目の実応答時間ＲＴi が計測された時点での予測応答時間と、該実応答時間ＲＴi の差の絶対値であることを特徴とする請求項６に記載の経路選択システム。
【請求項９】
前記寿命の値が、寿命＝（（前記予測情報の適合度−適合度の最小値）／（１−適合度の最小値））・寿命の最大値の式により求められることを特徴とする請求項３または４に記載の経路選択システム。
【請求項１０】
前記発信元ノードが前記サービス要求メッセージを、代表サーバ宛に送信する際に、その代表サーバの名称に対応する少なくとも１つのミラーサーバ名を提供し、該発信元ノードがＰＲＯＸＹサーバを経由して該サービス要求メッセージを送信する際に、該発信元ノードに関連する少なくとも１つのＰＲＯＸＹサーバ名を提供する経路情報管理手段を有することを特徴とする請求項１に記載の経路選択システム。
【請求項１１】
少なくとも１つのノードを有する複数のシステムがネットワークを介して分散配置される環境において、発信元ノードから送信先ノードに送信されるデータのネットワーク上の経路、及び送信先ノードから発信元ノードに返信されるデータのネットワーク上の経路を選択する経路選択方法において、該送信先ノードのサービスを要求するために、該発信元ノードから該送信先ノードに対してサービス要求メッセージを送信する場合に、該発信元ノードと該送信先ノードとの間を接続可能な各経路について、予測情報を用いて、それぞれ予測応答時間を求め、該予測応答時間が最小となる経路を使用して、該サービス要求メッセージを送信する経路算出ステップと、該経路算出ステップの該サービス要求メッセージの送信に応じて、少なくとも該送信を行った経路、及び該サービス要求メッセージの要求データ長を含む、そのサービス要求メッセージの送信に関する情報を応答情報として記憶し、該送信先ノードから、該発信元ノードに該サービス要求メッセージに対する応答を受信する場合に、少なくともその応答の応答データ長、及び該サービス要求メッセージの送信時からの応答時間に関する値を含む、その応答の受信に関する情報を更に該応答情報として記憶する応答情報管理ステップと、該応答情報管理ステップの該応答の受信に応じて、該応答情報に基づいて、該予測情報の内容を更新する予測情報管理ステップと、を有することを特徴とする経路選択方法。
【請求項１２】
前記応答時間に関する値が、単位データ長あたりの応答時間を示す実応答時間であり、該実応答時間が計算式：実応答時間＝（２・応答時間）／（要求データ長＋応答データ長）
により求められることを特徴とする請求項１１に記載の経路選択方法。
【請求項１３】
少なくとも１つのノードを有する前記システムが、該システムごとに、前記予測情報を有し、該予測情報が少なくとも１つの応答時間予測オブジェクトを有し、該応答時間予測オブジェクトがそれぞれ、染色体、及び適合度を意味するビット列を有し、該染色体が応答時間予測関数のパラメータに対応する少なくとも１つの遺伝子ブロックを有し、前記予測情報管理ステップが、前記サービス要求メッセージに対する応答を受信した際に、該染色体を世代交代させる世代交代ステップを有し、該世代交代ステップが、該応答時間予測オブジェクト内の各遺伝子ブロックからなる該応答時間予測関数のパラメータを用いて予測応答時間を計算し、最適な応答時間の予測を行った応答時間予測オブジェクトほど前記応答時間予測オブジェクトの適合度を大きい値に設定し、前記適合度の値が大きいほど前記寿命の値を長く設定する適合度計算ステップと、寿命に達した応答時間予測オブジェクトを判定し、その応答時間予測オブジェクトを削除する応答時間予測オブジェクト削除ステップと、該応答時間予測オブジェクト削除ステップによって削除された応答時間予測オブジェクトを補完すべく新たな応答時間予測オブジェクトを生成するために、既存の応答時間予測オブジェクトを、適合度の高いものほど高い確率で選択されるようにして複数選択し、その中の応答時間予測オブジェクトの染色体に対して所定の確率で、遺伝的オペレータを行う応答時間予測オブジェクト生成ステップとを有し、該世代交代ステップによる世代交代処理を繰り返すことによって、動的に最適な応答時間の予測を行うことができるように該応答時間予測オブジェクトを進化させ、最適な経路の予測を自律的に行わせることを特徴とする請求項１１に記載の経路選択方法。
【請求項１４】
前記予測情報、及び前記応答情報を含む複数のスクールのそれぞれが、少なくとも１つの前記予測情報管理ステップに対応づけられ、該予測情報管理ステップ内の前記世代交代ステップにおいて、前記適合度計算手段が、該予測応答時間の計算の際に、他のスクール内の該応答情報を使用することができ、前記応答時間予測オブジェクト生成手段が、対応する前記スクールに対して、新たな応答時間予測オブジェクトを生成において、既存の応答時間予測オブジェクトを選択する際に、他のスクール内の応答時間予測オブジェクトを選択することができ、他のスクールが対応づけられている予測情報管理ステップの属するシステムとの間で協調的に通信負荷を分散して経路を予測することを特徴とする請求項１３に記載の経路選択方法。
【請求項１５】
前記予測応答時間が、複数の応答の受信によって得られた複数の応答情報内の実応答時間及びその実応答時間が計測された時刻と、前記応答時間予測オブジェクト内の各遺伝子ブロックに記憶された、実応答時間が計測された時刻の新しさに関する係数、予測対象経路と実応答時間の計測された経路の距離に関する係数、及び予測対象経路と実応答時間の計測された経路のそれぞれの経路上の各ノードに関するアドレス情報の部分的な、距離に関する重み付けを表す係数と、実応答時間が計測された時刻の新しさに関する定数、及び予測対象経路と実応答時間の計測された経路の距離に関する定数を基に計算されることを特徴とする請求項１３または１４に記載の経路選択方法。
【請求項１６】
前記適合度が、前記予測応答時間と、複数の応答の受信によって得られた複数の応答情報内の実応答時間及びその実応答時間が計測された時刻と、前記応答時間予測オブジェクト内の各遺伝子ブロックに記憶された、実応答時間が計測された時刻の新しさに関する係数と、実応答時間が計測された時刻の新しさに関する定数を基に計算されることを特徴とする請求項１５に記載の経路選択システム。
【請求項１７】
前記予測応答時間が、複数の応答の受信によって得られた複数の応答情報内の実応答時間ＲＴｉ（ｉ＝１〜Ｎ）及びその実応答時間が計測された時刻、並びに前記応答時間予測オブジェクト内の各遺伝子ブロックに記憶された、最新性影響係数(cnew)、距離影響係数(cdist) 、４つのサブネットワーク間距離影響係数(csnet1,csnet2,csnet3,csnet4) を用いて、
【数４】
0003665460.tif 000014
によって求められ、ここでＲＩＲi ＝ｅ(-C1・ cnew ・ TAi)（Ｃ１は正の定数、ＴＡi は該予測応答時間計算時刻からｉ番目の実応答時間が計測された時刻を差し引いた値である）、ＤＩＲi ＝１／(C2 ・ｅ-C3 ・ cdist ・ＤＥi+1)（Ｃ２及びＣ３は正の定数である）
【数５】
0003665460.tif 000015
（ｉ番目の該応答情報の経路上の各ノードの番号をｊとし、発信元ノード、送信先ノードを含む該経路上のノード数をＭとし、予測対象の経路上のｊ番目のノードのＩＰアドレスをＴ１ｊ．Ｔ２ｊ．Ｔ３ｊ．Ｔ４ｊとし、該応答情報の経路上の各ノードのｊ番目のＩＰアドレスをＲ１ｉｊ．Ｒ２ｉｊ．Ｒ３ｉｊ．Ｒ４ｉｊとする））
Ｃｋ＝ｅ-C4 ・ csnetk（Ｃ４は正の定数）
であることを特徴とする請求項１５に記載の経路選択方法。
【請求項１８】
前記適合度が、複数の応答の受信によって得られた複数の応答情報内の実応答時間ＲＴｉ（ｉ＝１〜Ｎ）及びその実応答時間が計測された時刻、並びに前記応答時間予測オブジェクト内の各遺伝子ブロックに記憶された、最新性影響係数(cnew)を用いて、
【数６】
0003665460.tif 000016
を用いて求められ、ここでＲＩＲi ＝ｅ(-C1・ cnew ・ TAi)（Ｃ１は正の定数、ＴＡi は該予測応答時間計算時刻からｉ番目の実応答時間ＲＴi が計測された時刻を差し引いた値である）、ｄＲＴi は、ｉ番目の実応答時間ＲＴi が計測された時点での予測応答時間と、該実応答時間ＲＴi の差の絶対値であることを特徴とする請求項１６に記載の経路選択方法。
【請求項１９】
前記寿命の値が、寿命＝（（前記予測情報の適合度−適合度の最小値）／（１−適合度の最小値））・寿命の最大値の式により求められることを特徴とする請求項１３または１４に記載の経路選択方法。
【請求項２０】
前記発信元ノードが前記サービス要求メッセージを、代表サーバ宛に送信する際に、その代表サーバの名称に対応する少なくとも１つのミラーサーバ名を提供し、該発信元ノードがＰＲＯＸＹサーバを経由して該サービス要求メッセージを送信する際に、該発信元ノードに関連する少なくとも１つのＰＲＯＸＹサーバ名を提供する経路情報管理ステップを有することを特徴とする請求項１１に記載の経路選択方法。
【請求項２１】
少なくとも１つのノードを有する複数のシステムがネットワークを介して分散配置される環境において、発信元ノードから送信先ノードに送信されるデータのネットワーク上の経路、及び送信先ノードから発信元ノードに返信されるデータのネットワーク上の経路を選択する経路選択方法を実現するプログラムを記録した記録媒体であって、該送信先ノードのサービスを要求するために、該発信元ノードから該送信先ノードに対してサービス要求メッセージを送信する場合に、該発信元ノードと該送信先ノードとの間を接続可能な各経路について、予測情報を用いて、それぞれ予測応答時間を求め、該予測応答時間が最小となる経路を使用して、該サービス要求メッセージを送信する経路算出ステップと、該経路算出ステップの該サービス要求メッセージの送信に応じて、少なくとも該送信を行った経路、及び該サービス要求メッセージの要求データ長を含む、そのサービス要求メッセージの送信に関する情報を応答情報として記憶し、該送信先ノードから、該発信元ノードに該サービス要求メッセージに対する応答を受信する場合に、少なくともその応答の応答データ長、及び該サービス要求メッセージの送信時からの応答時間に関する値を含む、その応答の受信に関する情報を更に、該応答情報として記憶する応答情報管理ステップと、該応答情報管理ステップの該応答の受信に応じて、該応答情報に基づいて、該予測情報の内容を更新する予測情報管理ステップを、コンピュータに実行させるプログラムを記録した該コンピュータが読み取り可能な記録媒体。
【請求項２２】
前記発信元ノードがサービス要求メッセージを、代表サーバ宛に送信する際に、その代表サーバの名称に対応する少なくとも１つのミラーサーバ名を提供し、該発信元ノードがＰＲＯＸＹサーバを経由して該サービス要求メッセージを送信する際に、該発信元ノードに関連する少なくとも１つのＰＲＯＸＹサーバ名を提供する経路情報管理ステップを、さらにコンピュータに実行させる請求項２１記載のプログラムを記録した該コンピュータが読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、複数のシステムが分散して配置されたネットワーク環境において、最適な経路を選択するための方式に関し、より詳しくは、それらの複数のシステムのうち、あるシステムから他のシステムにサービスの要求データが送信され、該送信データに対する応答データが、その要求データの送信先システムから要求データの送信元システムに返信された場合に、その送信データ及び応答データの単位データ長あたりの応答時間をもとに、それらのデータの送信と応答に用いられる最適経路を予測し、選択する方式に関する。
【０００２】
【従来の技術】
近年のインターネットの急速な普及に伴い、インターネット上で送受信されるデータ量は著しく増加してきている。インターネット上で送受信されるデータは、ＷＷＷサーバからダウンロードされるホームページのデータ、ＦＴＰサーバからの各種ソフトウエアのデータ、企業や個人間のメール等、その種類や用途は多岐にわたる。
【０００３】
このような状況において、インターネットのユーザは、要求したホームページに関するデータのダウンロード、すなわちホームページの表示に長時間を要したり、複数のミラーサーバが提供されているにもかかわらず、最も効率的なサーバがどれか分からないために、ファイルのダウンロードに長時間を要したりすることをしばしば経験する。
【０００４】
一方、ネットワークのトポロジが複雑化することで、最適なネットワークの経路が動的に大きく変化し、ネットワーク管理者またはネットワーク技術者にとっては、最適な経路選択を行うことがより困難なものとなってきている。
【０００５】
しかし、従来の経路選択に関するルーティング・プロトコルは、ルータなどの各中継装置において、発信元アドレスから送信先アドレスまでの間に介在するルータ数（ホップ数）、帯域（データ最大流量）、及びトラフィック（データの実際の流量）等の情報を収集し、これらを指標として経路の計算を行っている。これらの技術においては、あるノードから他のノードに対してサービスを要求するデータが送信され、他のノードからその送信データに対する応答データが返信された場合の、その送信データ及び応答データの単位データ長あたりの応答時間は、経路選択の計算には使用されていない。
【０００６】
従来のルーティング・プロトコルの代表的な例として、ＲＩＰとＯＳＰＦがある。
ＲＩＰ(Routing  Infomation  Protocol、ＲＦＣ1058）は、自律システム内のルータ間あるいはルータとホスト間の動的ルーティング情報交換プロトコルである。ＲＩＰは距離ベクトル・アルゴリズムを採用し、多くのＵＮＩＸシステムやルータに実装されている。また、ＲＩＰでは、それぞれのルータが隣接するルータとの間で、一定周期ごとに、データが送信先に到達するまでに経由するルータの数（ホップ数）を交換し、そのホップ数を最小にするように通信経路を選択する。ただし、管理可能な最大のホップ数は１５である。
【０００７】
ＯＳＰＦ（Open  Shortest  Path  First 、ＲＦＣ１５８３）は、リンク・ステート・アルゴリズムを採用し、ルータ間でネットワークの接続情報（リンク・ステート）を交換し、それらを基に、各ルータが最適な通信経路を選択する。ＯＳＰＦは、ネットワークの負荷、回線コスト／速度、遅延などを考慮した最適なコストの経路を選択することができ、また更にコストが同じ複数の経路を確保して負荷分散を行う。
【０００８】
また、上記ＲＩＰに遺伝的アルゴリズムを適用した例が、1997年、Masaharu  Munetomo、Yoshiaki  Takai 、Yoshiharu  Sato により、論文「An  Adaptive  Network  Routing  Algorithm  Employing  Path  Genetic  Operators（Seventh  International  Conference  on  Genetic  Algorithms(ICGA'97)」として発表されている。
【０００９】
遺伝的アルゴリズム（ＧＡ）とは、生物の遺伝の機構を工学的に模倣・応用した技術である。生物の進化の過程では、既存の個体（親）から新たなる個体（子）が生まれる際に、個体の持つ染色体同士の交叉、染色体上の遺伝子の突然変異などが起こる。そして、環境に適応しない個体は淘汰され、より適応した個体が生き延びて新たな親となり、さらに新たな子孫を作っていく。このようにして、環境に適応した個体の集団が生き延びていく。各個体がどの程度環境に適応するかは、染色体あるいはゲノムによって決定される。
【００１０】
遺伝的アルゴリズムでは、組合せ最適化問題の解候補を、遺伝子の１次元ストリングである染色体に対応させて文字列として表現し、解候補（これを個体と呼ぶ）の集団に対して、選択および自己複製による淘汰、交叉、突然変異等の遺伝子操作を繰り返し行うことにより最適解の探索を行う。なお、上述の文字列とは、例えば０と１を使って表されるような数列等も含むものとする。
【００１１】
ここでは、生物進化は、解候補に対する目的関数（解候補の適性度を評価する関数）の値が最適値に近づくことに相当し、目的関数を最適にするものほど大きい値を取るような適応度関数が文字列（染色体）に対して定義される。淘汰とは、適応度関数により各文字列の評価値を算出し、解候補の集団の中で評価値の高い文字列を持つ解候補を、より高い確率で選択して次世代の解候補集団とする操作である。突然変異とは、文字列（ビット列）の一部のビット（遺伝子の一部）をランダムに反転した値（もとが１なら０、もとが０なら１）に置き換える操作である。交叉とは、２つの文字列の一部を相互に入れ換える操作である。
【００１２】
これらの操作を繰り返すことによって評価値のより高い文字列、すなわち目的関数をより最適化する解候補を得ることができる。遺伝的アルゴリズムは、大規模で多峰性を有する離散変数の最適化問題を解くのに適しているといわれており、しかも容易に適用可能であることから、広く一般的に使われている。
【００１３】
上記論文においては、各ルータがＲＩＰに基づいてホップ数を最小にするようにして作成されたルーティング・テーブル内の「デフォルト・ルート」の他に、突然変異及び交叉を用いる遺伝的アルゴリズムを使用して代替ルートを生成する。こうして生成された複数の経路は、それらの経路を使用した際の通信待ち時間に応じて、採用される確率（頻度）が決定され、その待ち時間に基づく評価が一定値を下回った場合に、この遺伝的アルゴリズムが適用され、新たな別の経路が生成される。
【００１４】
ここでは、突然変異は、例えば、基の経路を構成するルータのうち、あるルータを隣接する別のルータに変更し、そのルータと発信元のノードとの最短経路、及びそのルータと送信先のノードとの最短経路を接続して新しい経路とする操作を表す。交叉は、例えば、基の１対の経路に関して、それらの経路を構成するルータのうち、両方の経路に含まれるルータの組を選択し、更にその組の中からルータを１つ選択し、そのルータと送信先ノードの間にあるルータを全て入れ替えて、新たな経路を生成する操作を表す。
【００１５】
また、トランザクションの応答時間に基づいて、最適な処理を行うトランザクション処理サーバにそのトランザクションと同じ階級のトランザクションを割り当てる機構が特願平５−８７５７９「トランザクション処理サーバの経路指定機構」に開示されている。
【００１６】
上記機構では、トランザクションが複数の階級に区分され、その階級ごとに、トランザクション処理に関する平均応答時間が計算される。更に、各階級ごとに目標応答時間が設定されており、これらから階級ごとに性能指標を求める。
【００１７】
ここで上記機構は、トランザクションの１つを着信すると、その処理を行う可能性のあるトランザクション処理サーバのそれぞれについて、前記トランザクションが処理された場合の予測性能指標を求め、全階級に亘る全体の予測性能指標を最良にするトランザクション処理サーバに前記トランザクションの処理を割り当てる。
【００１８】
この機構では、トランザクションの処理をどのサーバに行わせるかを、過去のトランザクション処理に関する応答時間を基に決定するものであり、トランザクション処理に用いられるデータ長、データ量及び単位データ長あたりの応答時間を考慮するものではない。また、この機構は、トランザクション処理を行うサーバに対して、そのトランザクション処理に必要なデータを送信するネットワーク上の経路を制御するものでもない。更に、トランザクション処理を行うサーバに対するネットワーク上の経路中のノード数や帯域の違いなどの考慮も当然なされてはいない。
【００１９】
【発明が解決しようとする課題】
従来の経路選択方式では、任意の隣接する経路の組み合わせにおける応答時間の予測をするためには、その組み合わせに含まれる全経路の全ノード間の応答時間の予測が必要であり、そのためには、経路上の全ノードについて出入り口のデータ通過量を計測し、一カ所で収集する必要がある。ところが、ノードによっては、データ通過量を計測できないものもあり、たとえ計測できても計測データの通知形式が異なると、これを応答時間の予測には使用できなかった。
【００２０】
また、たとえデータ通過量を通知する能力をノードが持っていても、そのソードの運用者によっては、セキュリティ上の理由などにより、データ通過量を通知しないことも多い。このため、従来の経路選択技法では、特定のノードのリアルタイムなデータ通過量が欠けていることが多く、応答時間の予測ができなかった。
【００２１】
また、従来の経路選択に関するルーティング・プロトコルは、ルータなどの各中継装置において、発信元アドレスから送信先アドレスまでの間に介在するルータ数（ホップ数）、帯域（データ最大流量）、及びトラフィック（データの実際の流量）等の情報を収集し、これらを指標として経路を決定していたが、これらの決定は、そのルータ及び隣接するルータからの情報によって局所的に行われるものであり、中継するスイッチング・ルータなどのネットワーク中継装置、クライアント、及びサーバの性能をも含んだ、発信元アドレスから送信先アドレスまでの経路の全体の性能を評価して経路選択するわけではない。従って、従来の経路選択方式では、例えば、ルータのスイッチング性能やＷＷＷ／ＰＲＯＸＹサーバのキャッシュ分散効果は、性能情報として考慮されず、クライアントを利用するユーザにとって最適な経路、即ち実際のリクエストに対する応答時間の短い経路が必ずしも選択されるとは限らなかった。従来、ノード内の処理時間が回線通過時間に比してオーダーが低い場合が多く、応答時間の予測にはほとんど影響しなかったが、近年、計算機の内部バスの処理速度をはるかに凌駕したＬＡＮ（ギガビットイーサネットなど）やＷＡＮ（ＡＴＭによるＢ−ＩＳＤＮなど）さらにはギガビット・ルータが登場し、ノード内処理時間が全体の応答時間に大きな影響を及ぼすようになってきている。
【００２２】
更に、従来の経路選択方式では、クライアントに隣接した中継ノードの選択は静的にのみ可能で、中継性能が動的に変化する各中継ノードをその変化に適合させて動的に経路選択を行うことができなかった。
【００２３】
また更に、従来の経路選択方式では、各経路選択システム間での協調的ふるまいが得られなかった。例えば、キャッシュの種類により利用する中継ノードを決めておき、同じキャッシュの内容が複数の中継ノードに重複して存在しないように制御することができなかった。
【００２４】
また更に、従来の経路選択方式では、同様のルーティング・アルゴリズムが用いられると、各クライアントが同じデータから同じ予測を行ってしまう可能性があり、全てのクライアントが同じノードを経路として選択してしまい、結果として、応答時間が極端に悪化する結果を生んでしまっていた。
【００２５】
本発明は、前記課題を解決するために、発信元ノードから他の送信先ノードに対してサービスを要求するデータが送信された場合に、その送信データと、送信先ノードから発信元ノードに返信された応答データの単位データ長あたりの応答時間を記録して、その情報を使用して経路ごとの応答時間を予測し、自律的に最適な経路を選択するシステムを提供することを目的とする。
【００２６】
更に、本発明は、ノード間の経路の性能のみならず、経路上の全ての中継ノードの性能をも加味して得られる、単位データ長あたりの実応答時間を利用して経路選択を行うことができるシステムを提供することを目的とする。
【００２７】
【課題を解決するための手段】
上記本発明の課題を解決するための請求項１に記載の経路選択システムは、少なくとも１つのノードを有する複数のシステムがネットワークを介して分散配置される環境において、発信元ノードから送信先ノードに送信されるデータのネットワーク上の経路、及び送信先ノードから発信元ノードに返信されるデータのネットワーク上の経路を選択する経路選択システムであって、該送信先ノードのサービスを要求するために、該発信元ノードから該送信先ノードに対してサービス要求メッセージを送信する場合に、該発信元ノードと該送信先ノードとの間を接続可能な各経路について、予測情報を用いて、それぞれ予測応答時間を求め、該予測応答時間が最小となる経路を使用して、該サービス要求メッセージを送信する経路算出手段と、該経路算出手段の該サービス要求メッセージの送信に応じて、少なくとも該送信を行った経路、及び該サービス要求メッセージの要求データ長を含む、そのサービス要求メッセージの送信に関する情報を応答情報として記憶し、該送信先ノードから、該発信元ノードに該サービス要求メッセージに対する応答を受信する場合に、少なくともその応答の応答データ長、及び該サービス要求メッセージの送信時からの応答時間に関する値を含む、その応答の受信に関する情報を更に該応答情報として記憶する応答情報管理手段と、該応答情報管理手段の該応答の受信に応じて、該応答情報に基づいて、該予測情報の内容を更新する予測情報管理手段を有するよう構成される。これによって、前記経路の一部の情報が入手できなくてもその経路の応答時間を予測でき、ネットワーク中継装置、クライアント、サーバ等の性能をも含んだ前記経路の全体的な応答性能を基に応答時間が予想可能となる。
【００２８】
請求項２に記載の経路選択システムは、請求項１において、前記応答時間に関する値が、単位データ長あたりの応答時間を示す実応答時間であり、該実応答時間が計算式：実応答時間＝（２・応答時間）／（要求データ長＋応答データ長）により求められるよう構成される。これによって、前記経路の応答時間の予測が、ネットワーク中継装置、クライアント、サーバ等の性能をも含んだ前記経路の全体的な応答性能を基に得られる。
【００２９】
請求項３に記載の経路選択システムは、請求項１において、少なくとも１つのノードを有する前記システムが、該システムごとに、前記予測情報を有し、該予測情報が少なくとも１つの応答時間予測オブジェクトを有し、該応答時間予測オブジェクトがそれぞれ、染色体、及び適合度を意味するビット列を有し、該染色体が応答時間予測関数のパラメータに対応する少なくとも１つの遺伝子ブロックを有し、前記予測情報管理手段が、前記サービス要求メッセージに対する応答を受信した際に、該染色体を世代交代させる世代交代手段を有し、該世代交代手段が、該応答時間予測オブジェクト内の各遺伝子ブロックからなる該応答時間予測関数のパラメータを用いて予測応答時間を計算し、最適な応答時間の予測を行った応答時間予測オブジェクトほど前記適合度を大きい値に設定し、前記適合度の値が大きいほど前記応答時間予測オブジェクトの寿命の値を長く設定する適合度計算手段と、寿命に達した応答時間予測オブジェクトを判定し、その応答時間予測オブジェクトを削除する応答時間予測オブジェクト削除手段と、該応答時間予測オブジェクト削除手段によって削除された応答時間予測オブジェクトを補完すべく新たな応答時間予測オブジェクトを生成するために、既存の応答時間予測オブジェクトを、適合度の高いものほど高い確率で選択されるようにして複数選択し、その中の応答時間予測オブジェクトの染色体に対して所定の確率で、遺伝的オペレータを行う応答時間予測オブジェクト生成手段とを有し、該世代交代手段による世代交代処理を繰り返すことによって、動的に最適な応答時間の予測を行うことができるように該応答時間予測オブジェクトを進化させ、最適な経路の予測を自律的に行わせるよう構成される。これによって、前記最適な経路の予測を、中継ノード等の動的な性能の変化に応じて、動的かつ自律的に行うことができる。
【００３０】
請求項４に記載の経路選択システムは、請求項３において、前記予測情報、及び前記応答情報を含む複数のスクールのそれぞれが、少なくとも１つの前記予測情報管理手段に対応づけられ、該予測情報管理手段内の前記世代交代手段において、前記適合度計算手段が、該予測応答時間の計算の際に、他のスクール内の該応答情報を使用することができ、前記応答時間予測オブジェクト生成手段が、対応する前記スクールに対して、新たな応答時間予測オブジェクトを生成において、既存の応答時間予測オブジェクトを選択する際に、他のスクール内の応答時間予測オブジェクトを選択することができ、他のスクールが対応づけられている予測情報管理手段の属するシステムとの間で協調的に通信負荷を分散して経路を予測するよう構成される。これによって、新しい予測個体の生成に、他のスクールの情報を反映させ、全体システムとして協調するように最適経路を求めることができる。
【００３１】
請求項５に記載の経路選択システムは、請求項３または４において、前記予測応答時間が、複数の応答の受信によって得られた複数の応答情報内の実応答時間及びその実応答時間が計測された時刻と、前記応答時間予測オブジェクト内の各遺伝子ブロックに記憶された、実応答時間が計測された時刻の新しさに関する係数、予測対象経路と実応答時間の計測された経路の距離に関する係数、及び予測対象経路と実応答時間の計測された経路のそれぞれの経路上の各ノードに関するアドレス情報の部分的な、距離に関する重み付けを表す係数と、  実応答時間が計測された時刻の新しさに関する定数、及び予測対象経路と実応答時間の計測された経路の距離に関する定数を基に計算されるよう構成される。これによって、前記経路の一部の情報が入手できなくてもその経路の応答時間を予測でき、ネットワーク中継装置、クライアント、サーバ等の性能をも含んだ前記経路の全体的な応答性能を基に応答時間が予想可能となる。
【００３２】
請求項６に記載の経路選択システムは、請求項５において、前記適合度が、前記予測応答時間と、複数の応答の受信によって得られた複数の応答情報内の実応答時間及びその実応答時間が計測された時刻と、前記応答時間予測オブジェクト内の各遺伝子ブロックに記憶された、実応答時間が計測された時刻の新しさに関する係数と、実応答時間が計測された時刻の新しさに関する定数を基に計算されるよう構成される。これによって、前記最適な経路の予測を、中継ノード等の動的な性能の変化に応じて、動的かつ自律的に行うことができる。
【００３３】
請求項７に記載の経路選択システムは、請求項５において、前記予測応答時間が、複数の応答の受信によって得られた複数の応答情報内の実応答時間ＲＴｉ（ｉ＝１〜Ｎ）及びその実応答時間が計測された時刻、並びに前記応答時間予測オブジェクト内の各遺伝子ブロックに記憶された、最新性影響係数(cnew)、距離影響係数(cdist) 、４つのサブネットワーク間距離影響係数(csnet1,csnet2,csnet3,csnet4) を用いて、
【００３４】
【数７】
0003665460.tif 000002
【００３５】
によって求められ、ここでＲＩＲi ＝ｅ(-C1・ cnew ・ TAi) （Ｃ１は正の定数、ＴＡi は該予測応答時間計算時刻からｉ番目の実応答時間が計測された時刻を差し引いた値である）、ＤＩＲi ＝１／(C2 ・ｅ-C3 ・ cdist ・ＤＥi+1)（Ｃ２及びＣ３は正の定数である）、
【００３６】
【数８】
0003665460.tif 000003
【００３７】
（ｉ番目の該応答情報の経路上の各ノードの番号をｊとし、発信元ノード、送信先ノードを含む該経路上のノード数をＭとし、予測対象の経路上のｊ番目のノードのＩＰアドレスをＴ１ｊ．Ｔ２ｊ．Ｔ３ｊ．Ｔ４ｊとし、該応答情報の経路上の各ノードのｊ番目のＩＰアドレスをＲ１ｉｊ．Ｒ２ｉｊ．Ｒ３ｉｊ．Ｒ４ｉｊとする））、Ｃｋ＝ｅ-C4 ・ csnetk（Ｃ４は正の定数）であるよう構成される。これによって、前記経路の一部の情報が入手できなくてもその経路の応答時間を予測でき、ネットワーク中継装置、クライアント、サーバ等の性能をも含んだ前記経路の全体的な応答性能を基に応答時間が予想可能となる。
【００３８】
請求項８に記載の経路選択システムは、請求項６において、前記適合度が、複数の応答の受信によって得られた複数の応答情報内の実応答時間ＲＴｉ（ｉ＝１〜Ｎ）及びその実応答時間が計測された時刻、並びに前記応答時間予測オブジェクト内の各遺伝子ブロックに記憶された、最新性影響係数(cnew)を用いて、
【００３９】
【数９】
0003665460.tif 000004
【００４０】
を用いて求められ、ここでＲＩＲi ＝ｅ(-C1・ cnew ・ TAi) （Ｃ１は正の定数、ＴＡi は該予測応答時間計算時刻からｉ番目の実応答時間ＲＴi が計測された時刻を差し引いた値である）、ｄＲＴi は、ｉ番目の実応答時間ＲＴi が計測された時点での予測応答時間と、該実応答時間ＲＴi の差の絶対値であるよう構成される。これによって、前記最適な経路の予測を、中継ノード等の動的な性能の変化に応じて、動的かつ自律的に行うことができる。
【００４１】
請求項９に記載の経路選択システムは、請求項３または４において、前記寿命の値が、寿命＝（（前記予測情報の適合度−適合度の最小値）／（１−適合度の最小値））・寿命の最大値、の式により求められるよう構成される。これによって、前記最適な経路の予測を、中継ノード等の動的な性能の変化に応じて、動的かつ自律的に行うことができる。
【００４２】
請求項１０に記載の経路選択システムは、請求項１において、前記発信元ノードが前記サービス要求メッセージを、代表サーバ宛に送信する際に、その代表サーバの名称に対応する少なくとも１つのミラーサーバ名を提供し、該発信元ノードがＰＲＯＸＹサーバを経由して該サービス要求メッセージを送信する際に、該発信元ノードに関連する少なくとも１つのＰＲＯＸＹサーバ名を提供する経路情報管理手段を有するよう構成される。これによって、クライアントは、ＰＲＯＸＹサーバを経由したミラーサーバに対する経路の応答時間を予測でき、経路の選択を適切に行うことができる。
【００４３】
請求項１１に記載の経路選択システムは、過去に行われたサービス要求について、該サービス要求に使用した経路情報と、該サービスの応答時間の情報と、データ量の情報を管理する応答情報管理手段と、前記応答情報管理手段が管理する情報に基づいて、経路の選択を行う手段を備えるよう構成される。これによって、前記経路情報の一部が入手できなくてもその経路の応答時間を予測でき、ネットワーク中継装置、クライアント、サーバ等の性能をも含んだ前記経路の全体的な応答性能を基に応答時間が予想可能となる。
【００４４】
請求項１２に記載の経路選択方法は、少なくとも１つのノードを有する複数のシステムがネットワークを介して分散配置される環境において、発信元ノードから送信先ノードに送信されるデータのネットワーク上の経路、及び送信先ノードから発信元ノードに返信されるデータのネットワーク上の経路を選択する経路選択方法であって、該送信先ノードのサービスを要求するために、該発信元ノードから該送信先ノードに対してサービス要求メッセージを送信する場合に、該発信元ノードと該送信先ノードとの間を接続可能な各経路について、予測情報を用いて、それぞれ予測応答時間を求め、該予測応答時間が最小となる経路を使用して、該サービス要求メッセージを送信する経路算出ステップと、該経路算出ステップの該サービス要求メッセージの送信に応じて、少なくとも該送信を行った経路、及び該サービス要求メッセージの要求データ長を含む、そのサービス要求メッセージの送信に関する情報を応答情報として記憶し、該送信先ノードから、該発信元ノードに該サービス要求メッセージに対する応答を受信する場合に、少なくともその応答の応答データ長、及び該サービス要求メッセージの送信時からの応答時間に関する値を含む、その応答の受信に関する情報を更に該応答情報として記憶する応答情報管理ステップと、該応答情報管理ステップの該応答の受信に応じて、該応答情報に基づいて、該予測情報の内容を更新する予測情報管理ステップを有するよう構成される。これによって、前記経路の一部の情報が入手できなくてもその経路の応答時間を予測でき、ネットワーク中継装置、クライアント、サーバ等の性能をも含んだ前記経路の全体的な応答性能を基に応答時間が予想可能となる。
【００４５】
請求項１３に記載の経路選択方法は、請求項１２において、前記応答時間に関する値が、単位データ長あたりの応答時間を示す実応答時間であり、該実応答時間が計算式：実応答時間＝（２・応答時間）／（要求データ長＋応答データ長）により求められるよう構成される。これによって、前記経路の応答時間の予測が、ネットワーク中継装置、クライアント、サーバ等の性能をも含んだ前記経路の全体的な応答性能を基に得られる。
【００４６】
請求項１４に記載の経路選択方法は、請求項１２において、少なくとも１つのノードを有する前記システムが、該システムごとに、前記予測情報を有し、該予測情報が少なくとも１つの応答時間予測オブジェクトを有し、該応答時間予測オブジェクトがそれぞれ、染色体、及び適合度を意味するビット列を有し、該染色体が応答時間予測関数のパラメータに対応する少なくとも１つの遺伝子ブロックを有し、前記予測情報管理ステップが、前記サービス要求メッセージに対する応答を受信した際に、該染色体を世代交代させる世代交代ステップを有し、該世代交代ステップが、該応答時間予測オブジェクト内の各遺伝子ブロックからなる該応答時間予測関数のパラメータを用いて予測応答時間を計算し、最適な応答時間の予測を行った応答時間予測オブジェクトほど前記応答時間予測オブジェクトの適合度を大きい値に設定し、前記適合度の値が大きいほど前記寿命の値を長く設定する適合度計算ステップと、寿命に達した応答時間予測オブジェクトを判定し、その応答時間予測オブジェクトを削除する応答時間予測オブジェクト削除ステップと、該応答時間予測オブジェクト削除ステップによって削除された応答時間予測オブジェクトを補完すべく新たな応答時間予測オブジェクトを生成するために、既存の応答時間予測オブジェクトを、適合度の高いものほど高い確率で選択されるようにして複数選択し、その中の応答時間予測オブジェクトの染色体に対して所定の確率で、遺伝的オペレータを行う応答時間予測オブジェクト生成ステップとを有し、該世代交代ステップによる世代交代処理を繰り返すことによって、動的に最適な応答時間の予測を行うことができるように該応答時間予測オブジェクトを進化させ、最適な経路の予測を自律的に行わせるよう構成される。これによって、前記最適な経路の予測を、中継ノード等の動的な性能の変化に応じて、動的かつ自律的に行うことができる。
【００４７】
請求項１５に記載の経路選択方法は、請求項１４において、前記予測情報、及び前記応答情報を含む複数のスクールのそれぞれが、少なくとも１つの前記予測情報管理ステップに対応づけられ、該予測情報管理ステップ内の前記世代交代ステップにおいて、前記適合度計算手段が、該予測応答時間の計算の際に、他のスクール内の該応答情報を使用することができ、前記応答時間予測オブジェクト生成手段が、対応する前記スクールに対して、新たな応答時間予測オブジェクトを生成において、既存の応答時間予測オブジェクトを選択する際に、他のスクール内の応答時間予測オブジェクトを選択することができ、他のスクールが対応づけられている予測情報管理ステップの属するシステムとの間で協調的に通信負荷を分散して経路を予測するよう構成される。これによって、新しい予測個体の生成に、他のスクールの情報を反映させ、全体システムとして協調するように最適経路を求めることができる。
【００４８】
請求項１６に記載の経路選択方法は、請求項１４または１５において、前記予測応答時間が、複数の応答の受信によって得られた複数の応答情報内の実応答時間及びその実応答時間が計測された時刻と、前記応答時間予測オブジェクト内の各遺伝子ブロックに記憶された、実応答時間が計測された時刻の新しさに関する係数、予測対象経路と実応答時間の計測された経路の距離に関する係数、及び予測対象経路と実応答時間の計測された経路のそれぞれの経路上の各ノードに関するアドレス情報の部分的な、距離に関する重み付けを表す係数と、実応答時間が計測された時刻の新しさに関する定数、及び予測対象経路と実応答時間の計測された経路の距離に関する定数を基に計算されるよう構成される。これによって、前記経路の一部の情報が入手できなくてもその経路の応答時間を予測でき、ネットワーク中継装置、クライアント、サーバ等の性能をも含んだ前記経路の全体的な応答性能を基に応答時間が予想可能となる。
【００４９】
請求項１７に記載の経路選択方法は、請求項１６において、前記適合度が、前記予測応答時間と、複数の応答の受信によって得られた複数の応答情報内の実応答時間及びその実応答時間が計測された時刻と、前記応答時間予測オブジェクト内の各遺伝子ブロックに記憶された、実応答時間が計測された時刻の新しさに関する係数と、実応答時間が計測された時刻の新しさに関する定数を基に計算されるよう構成される。これによって、前記最適な経路の予測を、中継ノード等の動的な性能の変化に応じて、動的かつ自律的に行うことができる。
【００５０】
請求項１８に記載の経路選択方法は、請求項１６において、前記予測応答時間が、複数の応答の受信によって得られた複数の応答情報内の実応答時間ＲＴｉ（ｉ＝１〜Ｎ）及びその実応答時間が計測された時刻、並びに前記応答時間予測オブジェクト内の各遺伝子ブロックに記憶された、最新性影響係数(cnew)、距離影響係数(cdist) 、４つのサブネットワーク間距離影響係数(csnet1,csnet2,csnet3,csnet4) を用いて、
【００５１】
【数１０】
0003665460.tif 000005
【００５２】
によって求められ、ここでＲＩＲi ＝ｅ(-C1・ cnew ・ TAi) （Ｃ１は正の定数、ＴＡi は該予測応答時間計算時刻からｉ番目の実応答時間が計測された時刻を差し引いた値である）、ＤＩＲi ＝１／(C2 ・ｅ-C3 ・ cdist ・ＤＥi+1)（Ｃ２及びＣ３は正の定数である）、
【００５３】
【数１１】
0003665460.tif 000006
【００５４】
（ｉ番目の該応答情報の経路上の各ノードの番号をｊとし、発信元ノード、送信先ノードを含む該経路上のノード数をＭとし、予測対象の経路上のｊ番目のノードのＩＰアドレスをＴ１ｊ．Ｔ２ｊ．Ｔ３ｊ．Ｔ４ｊとし、該応答情報の経路上の各ノードのｊ番目のＩＰアドレスをＲ１ｉｊ．Ｒ２ｉｊ．Ｒ３ｉｊ．Ｒ４ｉｊとする））、Ｃｋ＝ｅ-C4 ・ csnetk（Ｃ４は正の定数）であるよう構成される。これによって、前記経路の一部の情報が入手できなくてもその経路の応答時間を予測でき、ネットワーク中継装置、クライアント、サーバ等の性能をも含んだ前記経路の全体的な応答性能を基に応答時間が予想可能となる。
【００５５】
請求項１９に記載の経路選択方法は、請求項１７において、前記適合度が、複数の応答の受信によって得られた複数の応答情報内の実応答時間ＲＴｉ（ｉ＝１〜Ｎ）及びその実応答時間が計測された時刻、並びに前記応答時間予測オブジェクト内の各遺伝子ブロックに記憶された、最新性影響係数(cnew)  を用いて、
【００５６】
【数１２】
0003665460.tif 000007
【００５７】
を用いて求められ、ここでＲＩＲi ＝ｅ(-C1・ cnew ・ TAi) （Ｃ１は正の定数、ＴＡi は該予測応答時間計算時刻からｉ番目の実応答時間ＲＴi が計測された時刻を差し引いた値である）、ｄＲＴi は、ｉ番目の実応答時間ＲＴi が計測された時点での予測応答時間と、該実応答時間ＲＴi の差の絶対値であるよう構成される。これによって、前記最適な経路の予測を、中継ノード等の動的な性能の変化に応じて、動的かつ自律的に行うことができる。
【００５８】
請求項２０に記載の経路選択方法は、請求項１４または１５において、前記寿命の値が、寿命＝（（前記予測情報の適合度−適合度の最小値）／（１−適合度の最小値））・寿命の最大値、の式により求められるよう構成される。これによって、前記最適な経路の予測を、中継ノード等の動的な性能の変化に応じて、動的かつ自律的に行うことができる。
【００５９】
請求項２１に記載の経路選択方法は、請求項１２において、前記発信元ノードが前記サービス要求メッセージを、代表サーバ宛に送信する際に、その代表サーバの名称に対応する少なくとも１つのミラーサーバ名を提供し、該発信元ノードがＰＲＯＸＹサーバを経由して該サービス要求メッセージを送信する際に、該発信元ノードに関連する少なくとも１つのＰＲＯＸＹサーバ名を提供する経路情報管理ステップを有するよう構成される。これによって、クライアントは、ＰＲＯＸＹサーバを経由したミラーサーバに対する経路の応答時間を予測でき、経路の選択を適切に行うことができる。
【００６０】
請求項２２に記載の経路選択方法を実現するプログラムを記録した記録媒体は、少なくとも１つのノードを有する複数のシステムがネットワークを介して分散配置される環境において、発信元ノードから送信先ノードに送信されるデータのネットワーク上の経路、及び送信先ノードから発信元ノードに返信されるデータのネットワーク上の経路を選択する経路選択方法を実現するプログラムを記録した記録媒体であって、該送信先ノードのサービスを要求するために、該発信元ノードから該送信先ノードに対してサービス要求メッセージを送信する場合に、該発信元ノードと該送信先ノードとの間を接続可能な各経路について、予測情報を用いて、それぞれ予測応答時間を求め、該予測応答時間が最小となる経路を使用して、該サービス要求メッセージを送信する経路算出ステップと、該経路算出ステップの該サービス要求メッセージの送信に応じて、少なくとも該送信を行った経路、及び該サービス要求メッセージの要求データ長を含む、そのサービス要求メッセージの送信に関する情報を応答情報として記憶し、該送信先ノードから、該発信元ノードに該サービス要求メッセージに対する応答を受信する場合に、少なくともその応答の応答データ長、及び該サービス要求メッセージの送信時からの応答時間に関する値を含む、その応答の受信に関する情報を更に、該応答情報として記憶する応答情報管理ステップと、該応答情報管理ステップの該応答の受信に応じて、該応答情報に基づいて、該予測情報の内容を更新する予測情報管理ステップを有するよう構成される。これによって、前記経路の一部の情報が入手できなくてもその経路の応答時間を予測でき、ネットワーク中継装置、クライアント、サーバ等の性能をも含んだ前記経路の全体的な応答性能を基に応答時間が予想可能となる。
【００６１】
請求項２３に記載の経路選択方法を実現するプログラムを記録した記録媒体は、少なくとも１つのノードを有する複数のシステムがネットワークを介して分散配置される環境において、発信元ノードから送信先ノードに送信されるデータのネットワーク上の経路、及び送信先ノードから発信元ノードに返信されるデータのネットワーク上の経路を選択する経路選択方法を実現するプログラムを記録した記録媒体であって、前記発信元ノードがサービス要求メッセージを、代表サーバ宛に送信する際に、その代表サーバの名称に対応する少なくとも１つのミラーサーバ名を提供し、該発信元ノードがＰＲＯＸＹサーバを経由して該サービス要求メッセージを送信する際に、該発信元ノードに関連する少なくとも１つのＰＲＯＸＹサーバ名を提供する経路情報管理ステップを有するよう構成される。これによって、クライアントは、ＰＲＯＸＹサーバを経由したミラーサーバに対する経路の応答時間を予測でき、経路の選択を適切に行うことができる。
【００６２】
【発明の実施の形態】
以下に、本発明の実施の形態の例について、図面を参照して説明する。尚、各図において、同一または類似のものには同一の参照番号または、記号を付与して説明する。
【００６３】
図１は、本発明の第１の実施例である、経路選択システム１００のシステム構成を示すブロック図である。経路選択システム１００は、サービス提供サーバ群１１０、ＰＲＯＸＹサーバ群１２０、クライアント群１３０、インターネットなどの多数のネットワーク中継装置を含む広域ネットワーク１４０、及びＬＡＮ１５０を含む。前記サービス提供サーバ群１１０、及びＰＲＯＸＹサーバ群１２０は、それぞれ前記ネットワーク１４０に接続されている。前記クライアント群１３０は、ここでは前記複数のＰＲＯＸＹサーバ群１２０を選択的に使用可能なように、ＬＡＮ１５０を介してＰＲＯＸＹサーバ群１２０に接続されている。しかし、クライアント群１３０はＰＲＯＸＹサーバ群１２０を介さずに直接ネットワーク１４０に接続することもできる。
【００６４】
サービス提供サーバ群１１０は、複数のサーバ１１１、１１２、１１３、・・・からなり、それぞれのサーバがネットワーク１４０に接続される。また、前記サービス提供サーバ群１１０はミラーサーバとしても提供され、例えばサーバ１１１は２つのミラーサーバを含み、サーバ１１２は１つのミラーサーバを含む。ミラーサーバとは、あるサーバが保有しているデータを、そっくりそのままコピーした形で記憶しているサーバのことであり、例えば、インターネット上に、同一のデータを収めた複数のサイトが配置される。同時に多くのクライアント群１３０から要求されるサーバへのアクセスを分散させて、ネットワークの負荷を軽減するとともに、人気の高いＷＷＷサイトやＦＴＰサイトのサーバに対するアクセスの集中を回避する目的で設置しているケースが多い。
【００６５】
ＰＲＯＸＹサーバ群１２０は、複数のサーバ１２１、１２２、・・・からなり、それぞれのサーバがネットワーク１４０に接続される。企業内ネットワークのような内部ネットワーク内の情報資産を、インターネットなどの誰でもアクセス可能な外部ネットワークから守るために設置されている「ファイアーウォール」と呼ばれるゲートウェイは、同時に内部ネットワークのユーザーが外部ネットワークへアクセスする際の障壁になってしまうという問題がある。ＰＲＯＸＹサーバは、これを解消するために内部ネットワーク内のクライアントからの外部ネットワークに対するサービス要求を受け付けてその作業を代行する役割を果たす。内部ネットワーク内にあるクライアントはファイアーウォールの存在を意識せずにＰＲＯＸＹサーバ越しに外部ネットワークにアクセスし、様々な外部ネットワーク上のサーバ等が提供するサービスを要求することができる。また、ＰＲＯＸＹサーバは、最近アクセスの行われたデータ、又は頻度の高いアクセスが行われるデータをキャッシュする機能も有しており、クライアント群１３０がそのデータのアクセスを行うと、実際にネットワーク１４０上のサービス提供サーバ群１１０にアクセスすることなく、ＰＲＯＸＹサーバ群１２０から、所望のデータを取得でき、ネットワーク上の全体トラフィックを低減させることができる。
【００６６】
クライアント群１３０は、複数のクライアント１３１、１３２、・・・からなり、ユーザはそのクライアント群１３０から前記サービス提供サーバ群１１０に対して、前記ＰＲＯＸＹサーバ群１２０及び前記ネットワーク１４０を介してサービス要求を行う。最も一般的な例として、クライアント群１３０上で稼働するＷＷＷブラウザから、サービス提供サーバ群１１０内にあるＨＴＭＬファイル等をダウンロードし、所望のホームページをクライアント群１３０上に表示するといった処理があげられる。この場合、前記サービス提供サーバ群１１０は、ＷＷＷサーバとして機能する。ＷＷＷサーバは、ウェブサーバーとも呼ばれる。ＷＷＷサーバでは、クライアントのＷＷＷブラウザからｈｔｔｐプロトコルを用いて送られてくる要求に応じて、「ｈｔｔｐｄ」と呼ばれるデーモンプロセスが稼働し、このデーモン・プロセスによって、ホームページを記述するＨＴＭＬファイルやパーツとなる画像ファイルなど、要求されたデータがクライアントのＷＷＷブラウザに送信される。
【００６７】
また、クライアント群１３０は、図１に示すようにＰＲＯＸＹサーバ群１２０を経由して前記サービス提供サーバ群１１０にアクセスすることが多いが、前記ＰＲＯＸＹサーバ群１２０を経由せずに行うこともできる。
【００６８】
更に、各クライアント、例えばクライアント１３１は、経路算出機能１３１Ａ、応答情報管理機能１３１Ｂ、予測情報管理機能１３１Ｃ、及び経路情報管理機能１３１Ｄを含む。図１には詳細に示されていないが、クライアント１３２もクライアント１３１と同様の機能群（経路算出機能１３２Ａ、応答情報管理機能１３２Ｂ、予測情報管理機能１３２Ｃ、及び経路情報管理機能１３２Ｄ）を有しており、その他のクライアントも同様の機能群を有する。
【００６９】
ここでは、クライアント群１３０の有する各機能をクライアント１３１を例にとって説明する。経路算出機能１３１Ａは、予測情報管理機能１３１Ｃが提供する予測情報と実応答時間、及び経路情報管理機能１３１Ｄが提供するミラーサーバ名とＰＲＯＸＹサーバ名を用いて、クライアント１３１から送信先（ミラーサーバ）までの最適な通信経路を決定し、その経路に沿って所望のサービス要求を送信する。
【００７０】
応答情報管理機能１３１Ｂは、前記経路算出機能１３１Ａによって送信されたサービス要求に対する応答を受信すると、実応答時間等の応答に関する情報を記憶し、その情報を予測情報管理機能１３１Ｃに提供する。
【００７１】
予測情報管理機能１３１Ｃは、前記経路算出機能１３１Ａの要求に応じて最新の予測情報を提供し、応答情報管理機能１３１Ｂから実応答時間等の情報を受信すると、その情報を基に予測情報を更新する。
【００７２】
経路情報管理機能１３１Ｄは、ミラーサーバ名やＰＲＯＸＹサーバ名などの情報を有し、前記経路算出機能１３１Ａの要求に応じてそれらの情報を提供する。ここで考慮する経路は、原則的にクライアント群１３０からサービス提供サーバ群１１０に向かう経路と、逆にサービス提供サーバ群１１０からクライアント群１３０に戻る経路が連結されたものであり、通常その経路の開始アドレスと最終アドレスが一致する。しかし、クライアント群１３０がサービス要求を送信するプロセスと、応答を受信するプロセスが別個に独立しており、または別のクライアント群１３０でサービス要求処理と受信処理が行われるような場合、それぞれのアドレスが異なる場合が考えられる。そのような場合には、前記経路は、実質的に往復の経路を構成しているにも関わらず、その開始アドレスと最終アドレスが一致しないことに注意すべきである。
【００７３】
また、ＷＷＷサーバに対するサービスの要求では、通常メッセージの往復の経路は同じであり、クライアント群１３０からサービス提供サーバ群１１０に向かった経路を逆にたどって応答が返される。しかし、前記経路は、往復の経路が異なる場合もあり、上述のように、経路を往復の経路が連結されたものとして扱うことが好ましい。
【００７４】
次に、図２のクライアント１３１における処理フローを参照して、クライアント１３１に関する全体の処理フローを説明する。本発明は、最適な経路の予測に遺伝的アルゴリズム（ＧＡ）を用いている。ＧＡを用いることによって、従来、経路選択の度に全ての環境データから計算を行う必要のあった経路選択が、ネットワーク環境の変化による予測個体（予測パラメータ）のズレを少しずつ計算していくだけでよくなる。
【００７５】
ＧＡによって、ネットワーク環境変化情報（例えば、新たに計測した応答時間データ）の入手ごとに、前記予測個体を世代交代することにより、刻々と変化するネットワーク環境（回線の切断、回線の拡張、利用者の増減、サービスの流行の変化など）に対応した予測個体を準備していくことになる。
【００７６】
また、新たに生成される予測個体のそれぞれに対し、さまざまな環境の変化の方向に適応可能なものとして遺伝子（染色体）が設定される。即ち、ＧＡにより、未来のあらゆる変化のパターンを随時予測しながら、周囲の環境の変換に追従して適応していくことができる。ただし、あらゆる変化を予測するためには、充分な交叉及び突然変異の操作が必要である。
【００７７】
図２は、各処理ステップが、そのステップを行う前述の各機能（経路算出機能１３１Ａ、応答情報管理機能１３１Ｂ、予測情報管理機能１３１Ｃ、及び経路情報管理機能１３１Ｄ）毎に、列を分けて記述されている。例えば、最も左の列に記述された処理ステップ（Ｓ１００、Ｓ１０１等）は、前記経路算出機能１３１Ａによって行われ、最も右の列に記述された処理ステップ（Ｓ１０２）は、前記経路情報管理機能１３１Ｄによって行われることを表している。また、クライアント１１０は、サービス提供サーバ群１１０にサービスを要求するために複数のＰＲＯＸＹサーバのうち１つを経由することができ、サービス提供サーバ群１１０は、ここでは複数のミラーサーバによって構成されているものと仮定する。
【００７８】
最初に、クライアント１３１が、例えばＷＷＷブラウザ等で所望のホームページを見ようとそのホームページのアドレスを指定すると、経路算出機能１３１Ａにおいて、そのアドレスのあるサーバの代表サーバ名に対してサービスの要求、即ち、この場合指定されたホームページを記述するＨＴＭＬファイルとそれに関連するデータのダウンロードの要求が行われる（ステップＳ１００）。
【００７９】
次に、経路算出機能１３１Ａは、前記代表サーバ名に対応するミラーサーバ名のリストとＰＲＯＸＹサーバ名のリストをクライアント１３１内の経路情報管理機能１３１Ｄに要求する（ステップＳ１０１）。図３（Ａ）にはＰＲＯＸＹテーブル１６０内の複数のレコードの例が示されており、このＰＲＯＸＹテーブル１６０内には、このクライアント１３１が関連するＰＲＯＸＹサーバ名が記憶されている。図３（Ｂ）にはＷＷＷサーバ・テーブル１７０内の複数のレコードの例が示されており、このＷＷＷサーバ・テーブル１７０内には、ＷＷＷサーバの代表名と、そのサーバに対応するミラーサーバ名が記憶されている。この図の例では、www.BBB.com というサーバがあり、これに対応するミラーサーバとしてwww1.BBB.com、www2.BBB.com、及びwww3.BBB.comが存在することを示しており、サービス要求は、これらの４つのサーバのうち１つに対して行われうる。これらのテーブルは全て、各クライアント内のメモリに展開されているのが好ましいが、クライアント内の外部記憶装置上に配置されていても良いし、本システム内の適当なデータベース・サーバ内に共有可能に配置されていても良い。
【００８０】
経路算出機能１３１Ａから、前記代表サーバ名に対応するミラーサーバ名のリストとＰＲＯＸＹサーバ名のリストを要求された経路情報管理機能１３１Ｄは、この要求に応じて、そのサービスの要求を達成可能なミラーサーバ名のリストとＰＲＯＸＹサーバ名のリストを、経路算出機能１３１Ａに送信する（ステップＳ１０２）。サービス要求を送信するサービス提供サーバがミラーサーバを有していなかったり、クライアントがＰＲＯＸＹサーバ経由でない場合は、上記ＰＲＯＸＹテーブル１６０やＷＷＷサーバ・テーブル１７０へのアクセスは必要ではない。
【００８１】
次に、経路算出機能１３１Ａは、最適な予測個体と実応答時間を予測情報管理機能１３１Ｃに対して要求する（ステップＳ１０３）。経路算出機能１３１Ａは、通信負荷等の観点から、寿命や適合度に応じて、予測個体を予測情報管理機能１３１Ｃに要求するタイミングを調整可能であり、必ずしもステップＳ１０３で行われる必要はない。予測情報管理機能１３１Ｃは、前記要求を受け取ると、予測個体デーブル１８０及び実応答時間テーブル１９０を検索し、必要なレコードを経路算出機能１３１Ａに送信する（ステップＳ１０４）。
【００８２】
図４（Ａ）には予測個体テーブル１８０内の予測個体のレコードのフォーマットが示されており、図４（Ｂ）には実応答時間テーブル１９０内のレコードのフォーマットが示されている。これらのテーブルは通常、システム内のデータベース・サーバに配置され、各クライアントから参照及び更新が可能なようになっている。
【００８３】
図４（Ａ）に示すように、予測個体テーブル１８０内の各予測個体のレコードは、識別番号、アドレス位置、適合度、寿命、生成日時、染色体の長さ、及び染色体を構成する各遺伝子（０〜７の計８ブロック）を含んでいる。
【００８４】
識別番号は、その予測個体を識別するために採番されたユニークな番号である。
アドレス位置は、この予測個体のレコードが予測個体テーブル１８０内のどの位置から始まるのかを示すアドレスを有している。
【００８５】
適合度とは、ここでは、予測個体がクライアント群１３０のサービス提供サーバ群１１０に対するサービス要求の応答時間をどれだけ的確に予想できるかを判断する尺度である。遺伝的アルゴリズムにおいては、より適合度の高い予測個体が高い確率で生き残ることになり、その適合度の高い予測個体を中心に次の世代の予測個体群が形成されていく。
【００８６】
この実施例で適合度は、以下の式で示される。
【００８７】
【数１３】
0003665460.tif 000008
【００８８】
ここでＲＩＲ(Recency Influence Rate)は、最新性影響率を示している。ＲＩＲi は、ｉ番目の実応答時間が計測された時間が適合度の計算時とどれだけ隔たりがあるかを示す指標であり、以下の式で示される。
【００８９】
ＲＩＲi ＝ｅ(-C1・ cnew ・ TAi) 
ここでＣ１は正の定数であり、ＴＡi はｉ番目の実応答時間が計測された時刻をＲＩＲの利用された時刻から差し引いた値である。cnewについては後述する。また、ｄＲＴi は、ｉ番目の実応答時間が計測された時点での予測応答時間と、該実応答時間の差の絶対値である。
【００９０】
上記適合度は、ｄＲＴi が全て０の場合、即ち各計測時刻において実応答時間と予測応答時間が一致した場合、１であり、最も適合度が高い。多くのｄＲＴi が０に近く、即ち各計測時刻において実応答時間と予測応答時間の差が小さいケースが多い場合ほど、上記適合度は１に近い値となる。上記適合度の高い予測個体が優秀な遺伝子を持っていることになり、上記のことから、適合度が１に近い予測個体ほど優秀な遺伝子を持っていることを意味する。
【００９１】
寿命は、以下の式で表される。
寿命＝（（その予測個体の適合度−スクール内における適合度の最小値）／（１−スクール内における適合度の最小値））・スクール内における寿命の最大値ここで、スクールとは、全予測個体の集合（これを人口ドメインと呼ぶ）の部分集合であり、このスクールの単位で世代交代が行われ、適合度の低い予測個体が淘汰されていく。これに対し、予測個体全ての集合、即ち人口ドメインは、遺伝子の交換が行われる範囲である。このスクールの数は、世代交代処理の規模による成長の達成度や、その処理負荷等の観点から任意に選択することができる。
【００９２】
前述したように、０＜適合度≦１であり、その予測個体の適合度が、スクール内における適合度の最小値となる場合、その予測個体の寿命の値は０になり、予測個体の適合度がスクール内における適合度の最大値に近づくほど、その予測個体の寿命の値は大きくなる。従って、前記予測個体の適合度が１に近づくほど、寿命は大きな値をとることになる。予測個体は、予測個体の生成日時＋寿命＜現在の日時を満たす場合に、寿命が過ぎたものとして削除されるので、寿命の値が大きい予測個体程、長い期間に亘ってそのスクール内にとどまることになる。
【００９３】
また、その予測個体にとって、寿命が過ぎているかどうかは、即時に判断されるため、本来的には寿命の値を予測個体テーブル１８０に記憶する必要はない。しかし、この実施例においては、予測個体のレコードを明示するために、上記予測個体テーブル１８０に記憶されるものとして示した。
【００９４】
生成日時は、その予測個体が生成された日時を示すものである。
染色体長は、複数の遺伝子ブロック（スキーマ）から構成される染色体の長さを示している。本発明では、各遺伝子ブロックを以下で詳述するようないくつかの係数としているが、将来的に他の係数を付加、あるいは他の係数と交換する場合もあり得る。このような場合に染色体長は、その染色体全体の長さを示すことによって、アプリケーション等が遺伝子の操作を容易に行えるようにしている。
【００９５】
染色体は、０〜７の計８個の遺伝子ブロック（スキーマ）で構成され、それぞれが、例えばJavaのint 型で定義されるようなデータ形式を有する。本実施例で使用されているのは遺伝子ブロック０、１、及び４〜７であるが、これらの遺伝子ブロック及び未使用のその他の遺伝子ブロックには、好適に予測個体が成長するように、様々な任意の値を設定することができる。
【００９６】
この例では、遺伝子ブロック０、１、及び４〜７には以下の値が設定される。
遺伝子ブロック０：最新性影響係数(cnew)
最新性影響係数は、前記最新性影響率ＲＩＲの計算に用いられ、実応答時間が計測された時刻とＲＩＲの計算された時刻との差が適合度に関してどのように影響するかを示す指標である。
【００９７】
遺伝子ブロック１：距離影響係数(cdist)
距離影響係数は、距離影響率ＤＩＲの計算に用いられ、クライアント群１３０とサービス提供サーバ群１１０との距離が適合度に関してどのように影響するかを示す指標である。ＤＩＲは、後述する予測応答時間の計算の際に用いられる。
【００９８】
遺伝子ブロック４〜７：距離影響係数(csnet1 〜csnet4)
ＩＰアドレスは終止符で８ビット単位に４つのグループに区切られており、遺伝子ブロック４〜７は、各グループごとに、クライアント群１３０とサービス提供サーバ群１１０との距離の影響の程度を示す指標である。遺伝子ブロック４の距離影響係数(csnet1)はＩＰアドレスの先頭の８ビットのグループに関する距離の影響を示し、遺伝子ブロック５の距離影響係数(csnet2)はＩＰアドレスの左から２番目の８ビットのグループに関する距離の影響を示し、遺伝子ブロック６の距離影響係数(csnet3)はＩＰアドレスの左から３番目の８ビットのグループに関する距離の影響を示し、遺伝子ブロック７の距離影響係数(csnet4)はＩＰアドレスの最後の８ビットのグループに関する距離の影響を示している。
【００９９】
これらの各遺伝子ブロックの距離影響係数は、サブネット間距離影響係数ＤＥの計算に用いられ、ＤＥはＤＩＲの計算に用いられる。
これまで説明してきた染色体を構成する各スキーマである遺伝子ブロック０〜７は、最初はＲａｎｄｏｍ関数等によってランダムに設定されるが、その後遺伝的アルゴリズムによって成長し、最適なビット列に収束していくことが期待される。
【０１００】
図４（Ｂ）に示すように、実応答時間テーブル１９０内のレコードは、識別番号、発信元アドレス、送信先アドレス、経路、実応答時間、要求データ長、応答データ長、及び要求日時を含んでいる。
【０１０１】
識別番号は、その実応答時間の記録を有するレコードを識別するために採番されたユニークな番号である。
発信元アドレスは、サービスの要求が行われた、クライアント群１３０のアドレスである。
【０１０２】
送信先アドレスは、クライアント群１３０によって行われたサービスの要求の送信先、即ちサービス提供サーバ群１１０のアドレスである。
経路は、前記クライアント群１３０から前記サービス提供サーバ群１１０に送信された、クライアント群１３０からのサービスを要求するメッセージの経路と、前記サービス提供サーバ群１１０から前記クライアント群１３０に送信された、サービス提供サーバ群１１０からの、その要求に応答するメッセージの経路を示しており、ルータやサーバなどの、全ての経由したノードの識別情報が記憶されている。本明細書では、単に経路といった場合はその両端、即ち発信元アドレスと送信先アドレスを含むものとして扱われるが、このテーブル１９０内の経路は、既にレコード内に発信元アドレスと送信先アドレスを有しているので、前述のように、発信元ノードのアドレスと応答を受信するノードのアドレスが一致する場合は、それらの情報を有していなくてもよい。
【０１０３】
実応答時間は、クライアント群１３０がサービスの要求をサービス提供サーバ群１１０に行ってから、そのサービス提供サーバ群１１０からそのサービスの要求に対する応答がクライアント群１３０に送信されるまでに実際に要した、単位データ長あたりの時間である。この実応答時間（ＲＴ）は、以下の式で表される。
【０１０４】
ＲＴ＝（２・ＲＴraw ）／（Ｌreq ＋Ｌres ）
ここで、ＲＴraw は、クライアント群１３０がサービスの要求をサービス提供サーバ群１１０に行ってから、そのサービス提供サーバ群１１０からそのサービスの要求に対する応答がクライアント群１３０に送信されるまでに実際に要した時間である。Ｌreq は要求データ長であり、Ｌres は応答データ長である。
【０１０５】
要求データ長（Ｌreq ）は、クライアント群１３０からサービス提供サーバ群１１０に送信されるサービスの要求を行うメッセージの長さである。このメッセージの長さは、ホームページの表示を指示したり、ＦＴＰでファイルのダウンロードの指示をしたりするような要求では、短いことが多い。
【０１０６】
応答データ長（Ｌres ）は、クライアント群１３０からのサービスの要求に応答して、サービス提供サーバ群１１０がクライアント群１３０に対して返信するメッセージの長さである。このメッセージの長さは、ホームページの表示を指示したり、ファイルのダウンロードの指示の際には、そのホームページやファイルのサイズによって大きく変化する。特に、ファイルのダウンロードなどでは、数メガバイトの返信データ長となることもある。
【０１０７】
実応答時間ＲＴには、既に要求データ長と応答データ長の情報が含まれているので、このテーブル１９０内にこれらの情報を保持する必然性はないが、ここでは将来の拡張性等に備え保持するものとする。また、データ容量の観点等から好ましくなければ、テーブル１９０からこの２つの項目、即ち要求データ長と応答データ長を除外することもできる。
【０１０８】
要求日時は、クライアント群１３０がサービス提供サーバ群１１０にサービスを要求した日時である。前記適合度や予測応答時間の計算においては、実応答時間のデータが用いられるが、そのデータが取得された時刻が計算時に対して最近のものか、過去のものかによって、その実応答時間のデータの意味が変化するため、本発明の実施例において重要な要素となっている。
【０１０９】
再び図２のステップＳ１０５に戻ると、ここで、経路算出機能１３１Ａがミラーサーバ名及びＰＲＯＸＹサーバ名を基に、それらのＩＰアドレスを取得する。この処理は、典型的には、クライアント群１３０にとって、そのミラーサーバまたはＰＲＯＸＹサーバが既知の場合、そのＩＰアドレスの情報がメモリ等に記憶されているので、ＩＰアドレスはそこから得られ、クライアント群１３０にとって新規（未知）である場合は、所定のドメイン内のＤＮＳ(Domain Name Server)サーバ内のテーブルをアクセスすることによって、そのミラーサーバまたはＰＲＯＸＹサーバに対応するＩＰアドレスが取得される。
【０１１０】
次に、このミラーサーバとＰＲＯＸＹ間の可能な経路を展開し、予測情報管理機能１３１Ｄから取得した予測個体と実応答時間から、その各経路に対して予測応答時間を求め、予測応答時間が最小となる経路を選択する（ステップＳ１０６）。求められた経路はミラーサーバ、及びＰＲＯＸＹサーバを含む経路である。また、経路算出機能１３１Ａは、ミラーサーバとＰＲＯＸＹ間の可能な経路を少なくとも１つ、あらかじめ知っていなければならないが、この機能は、従来のルーティングプロトコルで行われている方法で収集しておくことが可能である。
【０１１１】
ここで、経路算出機能１３１Ａは、求めたミラーサーバ、ＰＲＯＸＹサーバを含む経路を使用して、サービス提供サーバ群１１０にサービスを要求し（ステップＳ１０７）、制御を応答情報管理機能１３１Ｂに渡す。そこで応答制御情報機能１３１Ｂは、クライアント群１３０がサービスを要求した要求日時、要求データ長、発信元アドレス、送信先アドレス、及びステップＳ１０６で選択された経路を前記実応答時間テーブル１９０内に新しいレコードとして記憶する（ステップＳ１０８）。
【０１１２】
次に応答情報管理機能１３１Ｂは、サービス提供サーバ群１１０からサービスの応答を受信する（ステップＳ１０９）。このとき、図示していないが、サービスの応答を受信すると同時に、そのサービスをユーザに提供するために必要な処理を所定のアプリケーション等が実行する。例えば、ホームページの表示を指示する要求に対する応答を受信した場合には、ＷＷＷブラウザ等が、受信したデータに応じてホームページを段階的に表示し、ＦＴＰなどでファイルのダウンロードを指示した場合には、ＦＴＰプログラムが、該ダウンロードを実行すると共に応答データの受信状況をリアルタイムで表示したりする。
【０１１３】
次に応答情報管理機能１３１Ｂは、サービス提供サーバ群１１０からサービスの応答を全て受信すると、ステップＳ１０８で新たに作成された前記実応答時間テーブル１９０内のレコードに、該サービスにおける実応答時間、及び応答データ長を記憶する（ステップＳ１１０）。その後、応答情報管理機能１３１Ｂは、前記実応答時間とステップＳ１０８で記憶された経路を予測情報更新管理機能１３１Ｃに送信する（ステップＳ１１１）。
【０１１４】
予測情報管理機能１３１Ｃは、応答情報管理機能１３１Ｂから実応答時間と経路を受信すると、その情報に基づいて予測個体を更新する（ステップＳ１１２）。
【０１１５】
図５は、最小の予測応答時間の経路を求める処理フローであり、図２のステップＳ１０６を更に詳細に展開した図である。ステップＳ１０６では、複数のミラーサーバとＰＲＯＸＹサーバ間の可能な経路を展開し、予測情報管理機能１３１Ｄから取得した予測個体と実応答時間からそれらの各経路に対して予測応答時間を求め、予測応答時間が最小となる経路を選択する。
【０１１６】
最初に、経路算出機能１３１Ａは、ミラーサーバ名のリストとＰＲＯＸＹサーバ名のリストから可能な経路の一覧を取得する（ステップＳ２００）。次に、これらの経路一覧の中から先頭の経路を１つ選択する（ステップＳ２０１）。次に、予測情報管理機能１３１Ｃから取得した予測個体と実応答時間を用いて、ステップＳ２００で得られた各経路の予測応答時間を求める（ステップＳ２０２）。ここでの実応答時間は通常、実応答時間テーブル１９０内の同一の経路を有する複数のレコードから得られる複数の実応答時間である。選択された経路と同一の実応答時間のデータ数が十分でない場合、即ち実応答時間テーブル内に前記選択された経路と同じ経路の実応答時間のレコードが少ししかない場合もあるが、そのような場合には、選択された経路と似た経路の実応答時間のレコードや、最新の実応答時間のレコード等を、同一の経路を用いる場合より多く用いて予測応答時間を求めることができる。
【０１１７】
例えば、選択された経路と同一の経路で過去に実応答時間が測定されていればそのデータを５つ使用して予測応答時間を計算し、選択された経路と同一の経路で過去に１つも実応答時間が測定されていなければ、経路を問わず最新の実応答時間のデータを１０使用して、予測応答時間を計算するといった方法である。
【０１１８】
予測応答時間を求める式は以下に示すとおりである。
【０１１９】
【数１４】
0003665460.tif 000009
【０１２０】
ここで、ＲＩＲi は、i 番目に取り出された経路についての最新性影響率であり、内容は前述した通りである。ＤＩＲi は、i 番目に取り出された経路についての距離影響率であり、以下の式で表される。
【０１２１】
ＤＩＲi ＝１／(C2 ・ｅ-C3 ・ cdist ・ＤＥi+1)
ここで、C2及びC3は正の定数で、ＤＥi はＩＰアドレスによって評価される距離の影響度を示しており、サブネットワーク間距離影響係数という。前記取り出された経路において、その経路上の各ノードの番号をｊとして、クライアント群１３０、ＰＲＯＸＹサーバ群１２０などの経路サーバ、及びサービス提供サーバ群１１０を含んだその経路上のノード数をＭとする。また、前記予測応答時間を求める対象の経路上の各ノードのＩＰアドレスの８ビットごとのグループを左からそれぞれT1j 、T2j 、T3j 、T4j とし、予測のために利用する実応答時間で実際に使用された経路上の各ノードのＩＰアドレスの８ビットごとのグループを左からそれぞれR1ij、R2ij、R3ij、R4ijとする。このとき、ＤＥi は以下の式（３）で表すことができる。
【０１２２】
【数１５】
0003665460.tif 000010
【０１２３】
ここで、Ｃｋ＝ｅ-C4 ・ csnetk
但し、Ｃ４は正の定数である。また、csnetkは、ｋの値によって、csnet1〜csnet4が適用され、これらの値は前述の通り、ＩＰアドレスの８ビットごとの４つのグループに関する、距離上の重みを意味する。上の式（３）で、２つのＩＰアドレスを、前記８ビットごとの４つのグループ単位でそれぞれ比較した場合、右側のグループにおける差に比べて、左側のグループにおける差ほど、距離的な意味が大きい（即ち、同じ差でも左側のグループほど離れている）と考えられる。その意味から、通常csnet4、csnet3、csnet2、csnet1の順に大きな値をとることができる。
【０１２４】
また、比較する２つの経路の中継ノード数が異なるといった状況も考えられるが、上記式（３）は、中継ノード数の少ない方の経路中の適切な箇所に、適当なアドレスを仮に設定して、両経路の中継ノード数を一致させること等によって、そうした場合にも対応することができる。
【０１２５】
ＲＴiは、ｉ番目に取り出された前記経路の実応答時間である。
次に、前述のように求められた予測応答時間が、予測応答時間最小値より小さいかどうかが判定される（ステップＳ２０３）。予測応答時間最小値の初期値は無限大等の大きな値である。予測応答時間が予測応答時間最小値より小さい場合（ステップＳ２０３、Ｙｅｓ）、現在選択されている経路を予測応答時間が最小の経路であるとして設定する（ステップＳ２０４）。通常は、その経路を識別する情報が所定の領域に格納される。次に、予測応答時間最小値に、求められた予測応答時間を設定し（ステップＳ２０５）、ステップＳ２０６の判定に進む。予測応答時間最小値の初期値は非常に大きな値なので、最初の予測応答時間の計算は、必ずこれらのステップを通る。
【０１２６】
予測応答時間が予測応答時間最小値以上である場合（ステップＳ２０３、Ｎｏ）、判定処理ステップＳ２０６に進む。ステップＳ２０６においては、ステップＳ２０２で取得した経路一覧に未処理の経路が残っているかどうか判定する。残っていれば（ステップＳ２０６、Ｙｅｓ）、経路一覧から次の経路を選択して（ステップＳ２０８）、ステップＳ２０２に戻る。残りの経路がない場合は（ステップＳ２０７）、最適な経路が決定され（ステップＳ２０７）、処理が終了する。即ち、この時点で予測応答時間が最小の経路として設定されている経路が予測応答時間が最小の経路であり、予測応答時間最小値がその経路の予測応答時間である。
【０１２７】
図６は、予測個体の更新処理フローを示す図であり、図２のステップＳ１１２を更に詳細に展開した図である。ここで、予測情報管理機能１３１Ｃは、応答情報管理機能１３１Ｂから実応答時間とその経路を受信すると、それらの情報に基づいて予測個体を更新する。
【０１２８】
最初に、予測情報管理機能１３１Ｃは、応答情報管理機能１３１Ｂから実応答時間と経路が送信されたかを判定し（ステップＳ３００）、送信がない場合（ステップＳ３００、Ｎｏ）、この判定を繰り返す。送信が行われると（ステップＳ３００、Ｙｅｓ）、そのクライアント群１３０に関連するスクール内の先頭の予測個体を取得する（ステップＳ３０１）。ここでは、処理が行われているクライアント群１３０に対応する１つのスクールを対象としている。
【０１２９】
次に、予測情報管理機能１３１Ｃは、受信した経路に対応する予測応答時間を、前記取得されたスクール内の予測個体について求める（ステップＳ３０２）。この時、受信した経路と同一の実応答時間のデータ数が十分でない場合、即ち実応答時間テーブル内に前記受信した経路と同じ経路の実応答時間のレコードが少ししかない場合がある。そのような場合には、ステップＳ２０２で説明したように、前記受信した経路と似た経路の実応答時間のレコードや、最新の実応答時間のレコードを、同一の経路を用いる場合より多く用いて予測を行うこともできる。
【０１３０】
この処理は、スクール内の全ての予測個体に対して繰り返される。
予測応答時間を求める式は前述したとおりである。
更に、各予測個体ごとに前記ステップＳ３０２で求められた予測応答時間と、応答情報管理機能１３１Ｂから得られた実応答時間及び前記実応答時間テーブル１９０内の任意のレコードに記憶された実応答時間等から、適合度と寿命を求め、予測個体テーブルの該当レコードの該当項目を更新する（ステップＳ３０３）。
【０１３１】
次に、スクール内にまだ予測個体が残っているかの判定がされ（ステップＳ３０４）、残っていれば（ステップＳ３０４、Ｙｅｓ）、スクール内の次の予測個体を取得してステップＳ３０２以降を行う（ステップＳ３０６）。スクール内に予測個体が残っていなければ（ステップＳ３０４、Ｎｏ）、世代交代処理を行い（ステップＳ３０５）、その後ステップＳ３００の判定に戻る。
【０１３２】
図７は、世代交代の処理フローを示すものであり、図６のステップＳ３０５を詳細に展開した図である。この処理は、図６に示す処理フローにより更新されたスクール内の予測個体に対して、他のスクールにある予測個体をも含んで世代交代処理を行う。
【０１３３】
予測情報管理機能１３１Ｃは、自己のクライアントに関するスクール内の予測個体で、寿命が過ぎている予測個体の数を求める（ステップＳ４００）。予測個体の生成日時＋寿命＜現在の日時を満たす場合に、寿命が過ぎたものとして判定される。
寿命の過ぎた予測個体が１つもなかった場合は（ステップＳ４０１、Ｎｏ）、世代交代の処理を終了する。寿命の過ぎた予測個体が１つでもあった場合は（ステップＳ４０１、Ｙｅｓ）、他のスクールに関連づけられたクライアント群１３０の予測情報管理機能１３１Ｃから、予測個体を取得する（ステップＳ４０２）。この処理は、他のスクールの予測個体を取得することによって、ステップＳ４０３で行われる新しい予測個体の生成に、他のスクールの情報を反映させ、全体システムとして協調する最適経路を求めるためになされる。
【０１３４】
次に、予測情報管理機能１３１Ｃは、自己のクライアントに関するスクール内の予測個体と他のスクールの予測個体から、前記寿命が過ぎた予測個体の分だけ新しい予測個体を生成する（ステップＳ４０３）。新しい予測個体が生成された後、寿命が過ぎた自己のスクール内の予測個体を削除し（ステップＳ４０４）処理を終了する。
【０１３５】
図８は、スクール内の予測個体生成フローを示すものであり、図７のステップＳ４０３を更に詳細に展開した図である。この処理は、遺伝的アルゴリズムに基づいて、自己のクライアントに関するスクール内の予測個体またはその他のスクール内の予測個体から、交叉及び突然変異を行い、新しい予測個体を生成する。
【０１３６】
最初に予測情報管理機能１３１Ｃは、自己のクライアントに関するスクール内の予測個体、又はその他のスクール内の予測個体から、前記ステップＳ４０１で寿命の過ぎた予測個体の数と等しい数だけ父親を選択する（ステップＳ５００）。同様に、ステップＳ５０１で、自己のクライアントに関するスクール内の予測個体、又はその他のスクール内の予測個体から、前記ステップＳ４０１で寿命の過ぎた予測個体の数と等しい数だけ母親を選択する。これらの予測個体は、原則として適合度の高い予測個体ほど高い確率で選択される。その結果、予測個体は自己のスクールかそうでないかを問わず選択されることになるが、生物学的には、自己の環境への適合度を高めるため、ある程度自己のスクール内からの予測個体を残すことも必要である。
【０１３７】
次に、この２つの予測個体間で交叉(crossover) を行う（ステップＳ５０２）。この例では、この交叉によって、前記ステップＳ４０１で寿命の過ぎた予測個体の数と等しい数の父親と母親の予測個体（即ち、その合計は、前記寿命の過ぎた予測個体の数の２倍）から、半数の予測個体（即ち、前記寿命の過ぎた予測個体の数）が生成される。その後突然変異(mutation)を行い（ステップＳ５０３）、最終的に前記寿命の過ぎた予測個体の数と等しい数の予測個体が生成される。
【０１３８】
この結果生成された予測個体を、予測個体テーブルに新しいレコードとして追加する（ステップＳ５０４）。前記交叉及び突然変異の方法、例えば交叉に関して交叉点をどこに、いくつ設定するか、また、突然変異に関して反転させるビットの位置及び数をどうするかなどについては、多くのバリエーションが考えられ、ここでは好適な予測応答時間を得られるように、どのような方法も採用しうる。ただし、これらの選択は、世代交代の行き詰まりを避けるために、できるだけランダムに行われることが望ましい。
【０１３９】
図９は、本発明の第２の実施例である、経路選択システム２００のシステム構成を示すブロック図である。経路選択システム２００は、サービス提供サーバ群２１０、ＰＲＯＸＹサーバ群２２０、クライアント群２３０、サーバ群２６０、インターネットなどの多数のネットワーク中継装置を含む広域ネットワーク２４０、及びＬＡＮ２５０を含む。前記サービス提供サーバ群２１０、及びＰＲＯＸＹサーバ群２２０は、それぞれ前記ネットワーク２４０に接続されている。前記クライアント群２３０及びサーバ群２６０は、前記ＬＡＮ２５０、及び前記ＰＲＯＸＹサーバ群２２０を経由してネットワーク２４０に接続される。サーバ群２６０は、ここでは、複数のクライアント群２３０に対して共有資源及びサーバ機能を提供するサーバであり、ＷＷＷサーバなどのより広い範囲で使用されるサービス提供サーバ群２１０とは区別される。また、サーバ群２６０は、図９ではＬＡＮ２５０を介してクライアント群２３０と相互に接続されているが、任意の接続形態をとることができる。
【０１４０】
また、クライアント群２３０及びサーバ群２６０は、前記ＬＡＮ２５０及びＰＲＯＸＹサーバ群２２０を介さずに、ネットワーク２４０に直接接続することもできる。
【０１４１】
図１で示した経路選択システム１００と同様に、サービス提供サーバ群２１０は、複数のサーバ２１１、２１２、２１３、・・・からなり、それぞれのサーバがネットワーク２４０に接続される。また、前記サービス提供サーバ群２１０はミラーサーバとしても提供され、例えばサーバ２１１は３つのミラーサーバからなり、サーバ２１２は２つのミラーサーバからなる。
【０１４２】
ＰＲＯＸＹサーバ群２２０は、複数のサーバ２２１、２２２、・・・からなり、それぞれのサーバがネットワーク２４０に接続される。
クライアント群２３０は、複数のクライアント２３１、２３２、・・・からなり、ユーザはそれらのクライアントから前記サービス提供サーバ群２１０に対して、前記ＰＲＯＸＹサーバ群２２０及び前記ネットワーク２４０を介してサービス要求を行う。
【０１４３】
また、クライアント群２３０は、図９に示すようにＰＲＯＸＹサーバ群２２０を経由して前記サービス提供サーバ群２１０にアクセスすることが多いが、前記ＰＲＯＸＹサーバ群２２０を経由せずに行うこともできる。また、図９に示すような構成においては、ＬＡＮ２５０で接続されたサーバ群２６０を経由して前記サービス提供サーバ群２１０にアクセスすることもできる。
【０１４４】
更に、各クライアント、例えばクライアント２３１は、経路算出機能２３１Ａ、及び応答情報管理機能２３１Ｂを含む。図９には詳細に示されていないが、クライアント２３２もクライアント２３１と同様の機能群を有しており、その他のクライアントも同様である。
【０１４５】
前記経路算出機能２３１Ａ、及び応答情報管理機能２３１Ｂは、図１の経路選択システム１００のクライアント１３１内にある経路算出機能１３１Ａ、及び応答情報管理機能１３１Ｂと同様の機能を有する。
【０１４６】
サーバ群２６０は、複数のサーバ２６１、２６２、・・・からなる。
図９に示す第２の実施例は、予測情報管理機能２６１Ａ、及び経路情報管理機能２６１Ｂをサーバ群２６０内に有している。前記予測情報管理機能２６１Ａ、及び経路情報管理機能２６１Ｂは、実質的には、予測情報管理機能１３１Ｃ、及び経路情報管理機能１３１Ｄの機能に対応する。この実施例では、クライアント群２３０とサーバ群２６０内の各機能間のデータのやりとりが、ＬＡＮ２５０を介して行われる場合がある点をのぞいては、機能面で第１の実施例と変わるものではない。
【０１４７】
しかし、前記予測情報管理機能２６１Ａ、及び経路情報管理機能２６１Ｂをサーバ群２６０によって行うことにより、クライアント群２３０の導入時の負担及びネットワーク構成変更時の負担を軽減したり、サーバ群２６０に記憶されうる予測個体テーブルや実応答時間テーブルなどのデータの集中管理を行うことができる。
【０１４８】
また、本発明の第１及び第２の実施例に示したシステム構成は単なる例示に過ぎず、任意の接続方法による接続形態が数多く考えられる。しかし、それらの全ての接続形態についても、本発明の意図及び範囲を逸脱することなく本発明の適用を行うことが可能であることは、当業者には明らかである。
【０１４９】
更に、本明細書ではここまで、本発明が、クライアントとサービス提供サーバ間の最適経路の選択をクライアントのみ、またはクライアントとサーバの協調作業により実現する例を示してきたが、こうした機能をルータで行うこともでき、またパケット交換網において交換機により行うことも可能である。
【０１５０】
図１０は、上述した経路選択システム１００におけるクライアント群１３０の機能を実施するクライアント・コンピュータ１０００のハードウエア構成の一例を示している。また、図９に示す、本発明の第２の実施例のような接続形態におけるクライアント群２３０、及びサーバ群２６０も同様の構成を有する。
【０１５１】
該コンピュータ１０００は、それぞれバス１００８に接続されたＣＰＵ１００１、記憶部１００２、メモリ部１００３、表示部１００４、入力部１００５、印刷部１００６、およびネットワーク・インタフェース部１００７からなる。ＣＰＵ１００１は、図１に示された各機能１３１Ａ〜１３１Ｄを実行する。記憶部１００２は、ＣＰＵ１００１によって実行される前記各機能を実現するプログラム、及び予測個体テーブル等の本発明の経路選択システムに必要なデータを格納する。
【０１５２】
メモリ部１００３には、ＣＰＵ１００１によって実行される前記各機能を実現するプログラムがロードされ、予測個体テーブル等のデータが必要に応じて展開される。本発明の経路選択システム１００は、動的に各経路の予測応答時間を比較し、予測応答時間の最も短い経路を選択する必要があるため、これらの動的な処理に必要なデータは常時、アクセス時間の短いメモり部１００３に展開されていることが望ましい。
【０１５３】
表示部１００４は、ネットワーク・アドレスの指定やシステムの初期設定等の入力をガイドするための表示を行うために必要な場合がある。通常はＣＲＴ等のディスプレイ装置である。
【０１５４】
入力部１００５は、前記表示装置に表示された入力ガイドにそって入力や指示を行うものであり、キーボード、マウス等から成る入力装置で構成される。
印刷部１００６は、ユーザの指示に従って、記憶部１００２等に格納されているデータ等を印刷する、レーザプリンタ等の印刷装置である。
【０１５５】
ネットワーク・インタフェース部１００７は、クライアント群１３０をＬＡＮ１５０を介してＰＲＯＸＹサーバ群１２０に接続するよう機能する。この接続を公衆回線網又は専用回線を介して行う場合は、モデム、ＤＳＵ、ルータなどのネットワーク通信装置が必要であり、この場合、ネットワーク・インタフェース部１００７は、これらを含む通信インタフェース装置である。図９に示す第２の実施例における接続形態においては、サーバ群２６０との間のＬＡＮインタフェース、及び、ＬＡＮ２５０を経由したＰＲＯＸＹサーバ群２２０との接続機能をも含む。
【０１５６】
バス１００８は、前記各構成要素１００１〜１００７間でデータ、指令等の送受信を行うための共通伝送経路である。
【０１５７】
【発明の効果】
本発明の経路選択方式によれば、任意の隣接する経路の組み合わせにおける応答時間を予測する際に、ある経路内のいくつかの中継ノードに関する応答データを収集することができなくても、応答時間の予測を行うことができる。即ち、本発明では、単位データ長あたりの実応答時間（ＲＴ）を利用することにより、各ノードからのデータ通過量を示す情報が一部欠けている場合でも、予測したい経路による過去の、単位データ長あたりの実応答時間を記憶しており、その情報を元に、その予測対象の経路の応答時間を予測することができる。予測したい経路と同じ経路による単位データ長あたりの実応答時間を記憶していない場合でも、予測したい経路に近い経路の過去の単位データ長あたりの実応答時間を必要数だけ選択し、それらの重み付け後の平均値を計算する等の処理によって、その予測対象の経路の応答時間の予測が可能である。
【０１５８】
また、本発明の単位データ長あたりの実応答時間を利用する経路選択方式によって、ネットワーク中継装置、クライアント、及びサーバの性能をも含んだ、発信元アドレスから送信先アドレスまでの経路の全体的な応答性能が評価され、その情報を元に最適な経路が選択される。
【０１５９】
更に、本発明の経路選択方式によって、クライアントに隣接した中継ノードの選択を、その中継性能の動的変化に応じて動的に行うことができる。
また更に、本発明の経路選択方式によって、各経路選択システム間での協調的ふるまいが得られる。例えば、キャッシュの種類により利用する中継ノードを決めておき、同じキャッシュの内容が複数の中継ノードに重複して存在しないように制御することができる。
【０１６０】
また更に、本発明の経路選択方式によって、トランザクションの途中経路が帯域の異なる選択可能な多重経路網である場合にも、応答時間の予測が可能である。
【０１６１】
加えて、本発明の経路選択方式によれば、ＧＡを利用することによって、以下のような効果が得られる。
ノードが増加し、選択すべき経路パターンが増加すると、最適な経路を予測するための計算量が飛躍的に増大する。しかし、このようなネットワークの複雑化に対しても、ＧＡを利用することにより、比較的小さな計算量で短時間に最適経路を予測することが可能となる。
【０１６２】
ＧＡを用いると、ネットワーク環境の変化による予測個体（予測パラメータ）のズレを少しずつ計算していくだけでよく、従来の経路選択方式のように、経路選択の度に全ての環境データから計算を行う必要はない。
【０１６３】
更に、ＧＡを用いると、結果的に応答時間が極端に悪化する経路または経路上のノードに関する一極集中を動的に回避することができる。各クライアントごとに全く異なる予測個体（染色体）を持つため、同じ予測をすることはあり得ず、協調的な予測をするようになる。例えば、クライアントＡがノードＣを専属で利用し、クライアントＢがノードＤを専属で利用する状況が自動的に生じる。
【０１６４】
以上の本発明の効果から、所定のネットワーク環境においては、従来方式の約２倍の性能向上が図られている。
【図面の簡単な説明】
【図１】経路選択システム１００のシステム構成を示すブロック図である。
【図２】クライアントにおける処理フローを示す図である。
【図３】ＰＲＯＸＹテーブル及びＷＷＷサーバ・テーブル内のレコードの例を示す図である。
【図４】予測個体テーブル及び実応答時間テーブル内のレコードのフォーマットを示す図である。
【図５】最小の予測応答時間の経路を求める処理フローを示す図である。
【図６】予測個体の更新処理フローを示す図である。
【図７】世代交代の処理フローを示す図である。
【図８】スクール内の予測個体生成フローを示す図である。
【図９】経路選択システム２００のシステム構成を示すブロック図である。
【図１０】クライアント・コンピュータ１０００のハードウエア構成の一例を示す図である。
【符号の説明】
１００  経路選択システム
１１０、１１１、１１２、１１３  サービス提供サーバ
１２０、１２１、１２２  ＰＲＯＸＹサーバ
１３０、１３１、１３２  クライアント
１３１Ａ  経路算出機能
１３１Ｂ  応答時間情報機能
１３１Ｃ  予測情報管理機能
１３１Ｄ  経路情報管理機能
１４０  ネットワーク
１５０  ＬＡＮ
２００  経路選択システム
２１０、２１１、２１２、２１３  サービス提供サーバ
２２０、２２１、２２２  ＰＲＯＸＹサーバ
２３０、２３１、２３２  クライアント
２３１Ａ  経路算出機能
２３１Ｂ  応答時間情報機能
２４０  ネットワーク
２５０  ＬＡＮ
２６０、２６１、２６２  サーバ
２６１Ａ  予測情報管理機能
２６１Ｂ  経路情報管理機能
１０００  クライアント・コンピュータ
１００１  ＣＰＵ
１００２  記憶部
１００３  メモリ部
１００４  表示部
１００５  入力部
１００６  印刷部
１００７  ネットワーク・インタフェース部
１００８  バス
【図１】
0003665460.tif 000017
【図２】
0003665460.tif 000018
【図３】
0003665460.tif 000019
【図４】
0003665460.tif 000020
【図５】
0003665460.tif 000021
【図６】
0003665460.tif 000022
【図７】
0003665460.tif 000023
【図８】
0003665460.tif 000024
【図９】
0003665460.tif 000025
【図１０】
0003665460.tif 000026