"複数の入力ポートと出力ポートを有するノードを複数、任意の形状に接続したネットワークNWにおけるパケット転送システムであって、任意のノード発ノードから任意のノード着ノードへのパケット転送を行う場合に、経由ノードは、着ノードのアドレスを用いずに、予め設定された論理に基づいて、転送すべき次ノードのリンクを確率的に選択してパケットの転送を行う転送処理手段を有することを特徴とするパケット転送システム。前記転送処理手段は、隣接ノードとの間で隣接ノードに関する情報の交換を繰り返すことで、NW全体の接続構造以下、トポロジと記すを把握し、任意のノード間の最短ホップ距離から定まる許容ホップ長上限値を算出し、許容ホップ上限記憶手段に格納する最短ホップ経路算出手段と、パケットの転送を行うパケット転送手段と、を有し、前記パケット転送手段は、自身を発ノードとし、任意のノードを着ノードとするパケットに対して、自身と該着ノードの組に対して前記許容ホップ上限記憶手段の許容ホップ長上限値を残余許容ホップ長とし、該着ノードのIDをパケットのヘッダに挿入して送出する手段と、任意の入力ポートからパケットが到着した際は、ヘッダに記入された着ノードIDと合致するかを確認する確認手段と、前記確認手段で合致すると判定された場合は、到着した当該パケットの転送は行わず、合致しない場合は、前記残余許容ホップ長を1だけ減少させ、該残余許容ホップ長が2以上の場合は、パケットが転送されてきた隣接ノードを除く他の出力ポートに転送する手段と、を有する手段を含む請求項1記載のパケット転送システム。前記転送処理手段は、予め定められたパケットの転送確率rijとRjを格納する転送確率記憶手段を更に有し、前記パケット転送手段は、前記rijと前記Rjを用いて、ノードnは隣接ノードiからの到着パケットを該確率rijで隣接ノードjに転送し、また、該ノードnを発ノードとするパケットを確率Rjでノードnから隣接ノードjに転送する手段を含む請求項2記載のパケット転送システム。前記ノードnから前記隣接ノードjに繋がるリンクを流れるトラヒック量が、事前に定めた目標値Bnj以下となる条件の下で、該隣接ノードj以外の全ての隣接ノードiからの到着パケットに対する該隣接ノードjへの転送確率rijと、該ノードnを発ノードとするパケットの該隣接ノードjへの転送確率Rjを同一の値に自律的にランダムな時間間隔で求め、前記転送確率記憶手段に格納する転送確率算出手段を含む請求項3記載のパケット転送システム。前記転送確率算出手段は、をノードsを発ノード、ノードdを着ノードとするパケット以下、パケットsdと記すで、該ノードdに一つ以上到達する確率とし、また、前記ノードnにおいて、前記隣接ノードiからの到着パケットsdを前記隣接ノードjに対して転送した場合と転送しない場合のの差分をとし、さらに、が最小となるノードsとノードdのペアをs,dとし、同様に該ノードnを発ノードとするパケットに対しても、i=0として定義し、rij>0を満たす隣接ノードiの中で、が最大の隣接ノードiをk2とし、rij<1、を満たす隣接ノードiの中で、が最小の隣接ノードiをk1とするとき、該隣接ノードk2からのk2の場合はノードnを発ノードとするトラヒックの該隣接ノードjへの転送量を減少させ、逆に隣接ノードk1からのk1=の場合はノードnを発ノードとするトラヒックの隣接ノードjへの転送量を増加させることで、該ノードnから該ノードjへのリンク上を流れるトラヒック量を前記目標値Bnjに維持したまま、となるようもしくはRjともしくはRjとを、ノードnにおいてランダムな時間で更新する手段を含む請求項4記載のパケット転送システム。複数の入力ポートと出力ポートを有するノードを複数、任意の形状に接続したネットワークNWにおけるパケット転送方法であって、隣接ノード間に位置し、任意のノード発ノードから任意ノード着ノードへパケット転送するノード装置において、最短ホップ経路算出手段が、隣接ノードとの間で隣接ノードに関する情報の交換を繰り返すことで、NW全体の接続構造以下、トポロジと記すを把握し、任意のノード間の最短ホップ距離から定まる許容ホップ長上限値を算出し、許容ホップ上限記憶手段に格納する最短ホップ経路算出ステップと、転送確率算出手段が、各入力ポートiから到着したパケットを各出力ポートjに転送する確率rijと、ノードnを発とするパケットを各出力ポートjに転送する確率Rjとを算出し、転送確率記憶手段に格納する転送確率算出ステップと、パケット転送手段が、前記許容ホップ上限記憶手段に格納された前記許容ホップ長上限値をパケットのヘッダに記入し、前記転送確率記憶手段の前記確率に従って各出力ポートにパケットを転送するパケット転送ステップと、からなり、前記転送確率算出ステップにおいて、前記ノードnから前記隣接ノードjに繋がるリンクを流れるトラヒック量が、事前に定めた目標値Bnj以下となる条件の下で、該隣接ノードj以外の全ての隣接ノードiからの到着パケットに対する該隣接ノードjへの転送確率rijと、該ノードnを発ノードとするパケットの該隣接ノードjへの転送確率Rjを同一の値に自律的にランダムな時間間隔で求め、前記転送確率記憶手段に格納し、前記パケット転送ステップにおいて、前記rijと前記Rjを用いて、ノードnは隣接ノードiからの到着パケットを該確率rijで隣接ノードjに転送し、また、該ノードnを発ノードとするパケットを確率Rjでノードnから隣接ノードjに転送することを特徴とするパケット転送方法。複数の入力ポートと出力ポートを有するノードを複数、任意の形状に接続したネットワークNWにおけるパケット転送システムにおいて、隣接ノード間に位置し、任意のノード発ノードから任意ノード着ノードへパケット転送するノード装置であって、隣接ノードとの間で隣接ノードに関する情報の交換を繰り返すことで、NW全体の接続構造以下、トポロジと記すを把握し、任意のノード間の最短ホップ距離から定まる許容ホップ長上限値を算出し、許容ホップ上限記憶手段に格納する最短ホップ経路算出手段と、各入力ポートiから到着したパケットを各出力ポートjに転送する確率rijと、ノードnを発とするパケットを各出力ポートjに転送する確率Rjとを算出し、転送確率記憶手段に格納する転送確率算出手段と、前記許容ホップ上限記憶手段に格納された前記許容ホップ長上限値をパケットのヘッダに記入し、前記転送確率記憶手段の前記確率に従って各出力ポートにパケットを転送するパケット転送手段と、を有し、前記転送確率算出手段は、前記ノードnから前記隣接ノードjに繋がるリンクを流れるトラヒック量が、事前に定めた目標値Bnj以下となる条件の下で、該隣接ノードj以外の全ての隣接ノードiからの到着パケットに対する該隣接ノードjへの転送確率rijと、該ノードnを発ノードとするパケットの該隣接ノードjへの転送確率Rjを同一の値に自律的にランダムな時間間隔で求め、前記転送確率記憶手段に格納する手段を含み、前記パケット転送手段は、前記rijと前記Rjを用いて、ノードnは隣接ノードiからの到着パケットを該確率rijで隣接ノードjに転送し、また、該ノードnを発ノードとするパケットを確率Rjでノードnから隣接ノードjに転送する手段を含むと、含むことを特徴とするノード装置。しかしながら、上記のルータが到着パケットの目的アドレスに最も多く合致するルーティングテーブル内のエントリを探し出す方法として広く用いられている方法は、目的アドレスをキーにして得られるハッシュ値を用いる方法であるが、ハッシュ値が衝突した際には別途、他のアドレスを用意する等の方策を用いる必要がある。また、Bloomfilterを用いて、アドレスルックアップに要する処理負荷を低減する検討も行われている。しかし、これらの方法は全て、目的アドレスに基づきパケットを転送すべき出力ポートを決めているため、NW規模目的アドレス数や、NWを流れるトラヒック量の増加に伴い、パケットのルーティング処理に要する負荷が増加する問題がある。本発明は、上記の点に鑑みなされたもので、パケットに記述された目的アドレスを用いたルーティング処理を行わずにルータにおいてパケットの転送を確率的に行うことが可能なパケット転送システム及び方法及びノード装を提供することを目的とする。上記の課題を解決するため、本発明請求項1は、複数の入力ポートと出力ポートを有するノードを複数、任意の形状に接続したネットワークNWにおけるパケット転送システムであって、任意のノード発ノードから任意のノード着ノードへのパケット転送を行う場合に、経由ノードは、着ノードのアドレスを用いずに、予め設定された論理に基づいて、転送すべき次ノードのリンクを確率的に選択してパケットの転送を行う転送処理手段を有する。また、本発明請求項2は、前記転送処理手段において、隣接ノードとの間で隣接ノードに関する情報の交換を繰り返すことで、NW全体の接続構造以下、トポロジと記すを把握し、任意のノード間の最短ホップ距離から定まる許容ホップ長上限値を算出し、許容ホップ上限記憶手段に格納する最短ホップ経路算出手段と、パケットの転送を行うパケット転送手段と、を有し、前記パケット転送手段は、自身を発ノードとし、任意のノードを着ノードとするパケットに対して、自身と該着ノードの組に対して前記許容ホップ上限記憶手段の許容ホップ長上限値を残余許容ホップ長とし、該着ノードのIDをパケットのヘッダに挿入して送出する手段と、任意の入力ポートからパケットが到着した際は、ヘッダに記入された着ノードIDと合致するかを確認する確認手段と、前記確認手段で合致すると判定された場合は、到着した当該パケットの転送は行わず、合致しない場合は、前記残余許容ホップ長を1だけ減少させ、該残余許容ホップ長が2以上の場合は、パケットが転送されてきた隣接ノードを除く他の出力ポートに転送する手段と、を有する手段を含む。また、本発明請求項3は、前記転送処理手段において、予め定められたパケットの転送確率rijとRjを格納する転送確率記憶手段を更に有し、前記パケット転送手段において、前記rijと前記Rjを用いて、ノードnは隣接ノードiからの到着パケットを該確率rijで隣接ノードjに転送し、また、該ノードnを発ノードとするパケットを確率Rjでノードnから隣接ノードjに転送する手段を含む。また、本発明請求項4は、前記ノードnから前記隣接ノードjに繋がるリンクを流れるトラヒック量が、事前に定めた目標値Bnj以下となる条件の下で、該隣接ノードj以外の全ての隣接ノードiからの到着パケットに対する該隣接ノードjへの転送確率rijと、該ノードnを発ノードとするパケットの該隣接ノードjへの転送確率Rjを同一の値に自律的にランダムな時間間隔で求め、前記転送確率記憶手段に格納する転送確率算出手段を含む。また、本発明請求項5は、請求項4の前記転送確率算出手段において、をノードsを発ノード、ノードdを着ノードとするパケット以下、パケットsdと記すで、該ノードdに一つ以上到達する確率とし、また、前記ノードnにおいて、前記隣接ノードiからの到着パケットsdを前記隣接ノードjに対して転送した場合と転送しない場合のの差分をとし、さらに、が最小となるノードsとノードdのペアをs,dとし、同様に該ノードnを発ノードとするパケットに対しても、i=0として定義し、rij>0を満たす隣接ノードiの中で、が最大の隣接ノードiをk2とし、rij<1、を満たす隣接ノードiの中で、が最小の隣接ノードiをk1とするとき、該隣接ノードk2からのk2の場合はノードnを発ノードとするトラヒックの該隣接ノードjへの転送量を減少させ、逆に隣接ノードk1からのk1=の場合はノードnを発ノードとするトラヒックの隣接ノードjへの転送量を増加させることで、該ノードnから該ノードjへのリンク上を流れるトラヒック量を前記目標値Bnjに維持したまま、となるようもしくはRjともしくはRjとを、ノードnにおいてランダムな時間で更新する手段を含む。本発明によれば、複数の入力ポートと出力ポートを有するノードを複数、任意の形状に接続したネットワークにおいて、任意のノード発ノードから任意のノード着ノードへのパケット転送を行う場合に、経由ノードにおいて着ノードのアドレスを用いずに、ある論理に基づいて転送すべき次ノードのリンクを確率的に選択して転送することにより、パケットの転送を確率的に行うことができる。以下図面と共に、本発明の実施の形態を説明する。本発明は、複数の入力ポートと出力ポートを有するノードを複数、任意の形状に接続したネットワークにおいて、任意のノード発ノードから任意のノード着ノードへのパケット転送を行う場合に、経由ノードにおいて着ノードのアドレスを用いないでパケットの転送を、ある論理に基づいて転送すべき次のノードのリンクを確率的に選択して行う。図1は、本発明の一実施の形態におけるシステム構成を示す。同図に示す確率的ルーティングフリーパケット転送システムは、隣接ノード情報交換部101、トポロジ情報記憶部102、最短ポップ経路算出部103、許容ホップ上限記憶部104、転送確率算出部105、転送確率記憶部106、パケット転送処理部107から構成される。トポロジ情報記憶部102、許容ホップ上限記憶部104、転送確率記憶部106は、ハードディスク等の記憶媒体である。隣接ノード情報処理部101は、自身が接続するノードに関する情報と、隣接ノードから通知された同様の情報を、隣接ノードに対して通知する。このような隣接ノード間での情報交換を反復することでNW全体のトポロジを把握し、トポロジ情報記憶部102に格納する。最短ホップ経路算出部103は、各発着ノード間の最短ホップ経路を、トポロジ情報記憶部102のトポロジ情報を用いて算出し、各発着ノードペアに対して最短ホップ長から許容できるホップ数上限値を算出し、許容ホップ上限記憶部104に格納する。転送確率算出部105は、各入力ポートiから到着したパケットを各出力ポートjに転送する確率rijと、ノードnを発とするパケットを各出力ポートjに転送する確率Rjとを算出し、転送確率記憶部106に格納する。パケット転送処理部107は、パケットがノードnに到着する毎に、転送確率記憶部106に格納された転送確率Rjに従い、各出力ポートにパケットを転送する。また、ノードnを発とするパケットの転送を行う際には、パケット転送処理部107は、許容ホップ上限記憶部104に格納されているホップ上限値をパケットのヘッダに記入し、転送確率記憶部106に収容された転送確率に従い、各出力ポートにパケットを転送する。図2は、本発明の一実施の形態における確率的ルーティングフリーパケット転送方式のシーケンス図を示す。サービス運用の開始に先立ち、各ノードの隣接ノード情報交換部101は隣接ノードとの間で接続ノードに関する情報を交換しステップ1、最短ホップ経路算出部103は、各発着ノードペアに対する許容ホップ長上限を許容ホップ情報記憶部104に設定するステップ2。そして、転送確率算出部105においてパケット転送確率を設定するステップ3。サービス運用中ステップ4は、入力ポートからパケットが到着するか、自身を発ノードとするパケットを生成するごとに、パケット転送処理部107は、転送確率記憶部106の予め定めたパケット転送確率に従い、各出力ポートにパケットを転送するステップ5。転送確率算出部105は、更にランダムな時間間隔で自立的に、転送確率記憶部106のパケット転送確率を更新するステップ6。次に、本発明の確率的ルーティングフリーパケット転送方式について詳細に説明する。パケット転送方法ノードnの隣接ノード集合をAn、隣接ノード数をAn、ノードsを発ノード、ノードdを着ノードとするパケット以下、パケットsdと記すの転送に対して許容されるホップ長の上限をMsdとする。なお、An、An、ノードsdのトポロジ情報はトポロジ情報記憶部102に格納され、Msdは許容ホップ上限記憶部104に格納されているものとし、転送確率Rjが転送確率記憶部106に格納されているものとする。パケットのヘッダには、現在のインターネットで用いられているのと同様に、発着アドレス、発着オート番号、許容残余ホップ長値TTLtimetoliveが記述される。ノードnに収容された下位のNWや端末から生成された、任意の他のノードjを着ノードとするパケットの転送要求に対して、ノードnのパケット転送処理部107は、Mndの値をパケットのTTLに記述し、j∈Anの各出力ポートjに対してRjの確率で転送する。そのため二つ以上の出力ポートに対して同一のパケットが出力される可能性や、どの出力ポートにもパケットが出力されない可能性がある。また、パケット転送処理部107は、i∈Anの入力ポートiからノードnにパケットが到着した際には、パケットのヘッダに記述された着アドレスdがノードnか否かをチェックし、dnの場合には、パケットの転送を行わない。一方、d≠nの場合には、TTLをチェックして1である場合には、やはりパケットの転送を行わない。2以上である場合には、TTLの値を1だけ減少させた後、j∈Anでj≠iの各出力ポートjに対してrijの確率で転送する。そのため、やはり2つ以上の出力ポートに対して同一のパケットが出力される可能性や、どの出力ポートにもパケットが出力されない可能性がある。各ノードnの転送確率算出部105は自律的にランダムな時間間隔で、以下に述べる二つの方法i均等割当法、ii最大最小到達率法、のいずれかを用いて、パケット転送確率Rj,rijを設定する。i均等割当法:ノードnからj∈Anの隣接ノードjに繋がるリンクを流れるトラヒック量が、事前に定めた目標値Bnj以下となる条件の下で、j以外の全ての隣接ノードiからの到着パケットに対するノードjへの転送確率rijと、ノードnを発ノードとするパケットのノードjへの転送確率Rjを同一の値に設定する。パケットsdの中で、ノードsを出発してからkホップ目に、ノードiから隣接ノードnに到着するものの個数の期待値をとすると、k=1に対しては、が成立する。また2≦k≦Msdの各kに対して、以下の漸近式が成立する。上記の式2の漸近式をk=2から順に解くことで、1≦k≦Msdの各kに対してを得ることができる。また、パケットsdの中で、ノードiがノードnに単位時間当たりに到着するものの個数をとすると、より得られる。但し、vsdはノードsを発ノード、ノードdを着ノードとするトラヒック量単位時間あたりに発生するパケット数である。さらにノードiからノードnに単位時間あたりに到着するパケット数をwinとする。今、任意のj∈Anに対して、i∈An、i≠jの全てのiに対するrijと、Rjを同一の値rに設定することを考える。ノードnを発ノードとするパケットの単位時間当たりの発生数をVnとすると、リンクn,jに流れるトラヒック量単位時間あたりのパケット数は、となり、これが目標値Bnj以下となるようrを設定すればよい。またrは明らかにr∈1を満たすため、rを次式で設定する。最大最小到達率法ノードsを発ノード、ノードdを着ノードとするパケットは、経由ノードにおける確率的な転送を反復する結果、目的ノードdに複数のパケットが到着する可能性もあれば、全く到着しない可能性もある。一つ以上のパケットがノードdに到着した場合に、このパケット転送が成功したものとみなせるため、パケットsdの到達確率yをその確率と定義すると、となる。均等割当法を用いた場合、特定のsdペア間においてパケット到達確率yが低くなる可能性がある。パケット到達確率が低いと、パケットが正しく目的ノードに届くまでに、何度も再送を繰り返す必要があり、データ転送の完了までに要する時間が長くなり、実用上、問題となる。そこで、均等割当法を用いてノードnにおける隣接ノードjに対するパケット転送確率Rj、rijを設定した状態において、さらにRj,rijを調整することで、NW上の最小パケット到達確率の向上を図る。以下に、ノードnにおいて、隣接ノードjへの出力ポートへのパケット転送確率rij、i∈An、Rjの調整方法について説明する。ノードiとjがノードnに隣接している場合に、ノードnにノードiから到着したパケットsdをノードjに転送した場合の、パケットsdの到達確率をとする。同様に、ノードnにノードiから到着したパケットsdをノードjに転送しない場合の、パケットsdの到達確率をとする。を、ノードiからノードnに到達したパケットをノードjに転送する確率がrijのときの、パケットsdの到達確率とすると、は、ノードnを経由しないでノードdに到達する場合の貢献成分と、ノードnを経由してノードdに到達する場合の貢献成分との和となるため、で与えられる。同様にノードnを発ノードとするパケットに対しても、ノードnにおいて隣接ノードjに転送した場合と転送しない場合の到達確率を各々、とすると、到達確率は、となる。パケットが転送されてきたノードiにパケットを再度転送するとループバックとなるため、riin0に設定する。の各々において、これらの値が最小となるsdペアを、各々とするとき、ak,bk,rkを以下のように定義する。また、0≦k≦An,k≠jの各kに対して、ykをyk=bkrkで定義する。そして、bk>0、rk<1を満たすkの中で、ykが最小のkをk1とする。また、rk0k≠k1を満たすkの中でykが最大のkをk2とする。入力リンクk2からのk2=0の場合はノードnを発とするパケットの出力リンクjへの転送量を減少させ、代わりに入力リンクk1からのk1=0の場合はノードnを発とするパケットの出力リンクjへの転送量を増加させることで、出力リンクjのトラヒック量をBnj以下に維持したまま、となるよう次式のように、更新前の確率と、更新後の確率を更新する。但し、w0nVnとする。但し、更新後のが更新前のを下回る場合には、更新は行わず、次の候補をk1に設定して同様に更新を試みる処理を、更新対象が見つかるまで反復する。[性能評価]評価には、CAIDACooperativeAssociationforInternetDataAnalysisのWebページでトポロジが公開されている商用ISPバックボーンNWの中から、ノード数Nが40以下の27のNWを用いる。NW全体の総トラヒックデマンド量単位時間あたりに各ノードにおいて生成されるパケット転送要求数のNの全ノードについての総計Vに対して、交流トラヒックデマンド量を、両端ノードの人口比の積で比例配分する。パケット転送確率の初期値は全て05に設定する。各sdペアに対して、経由ホップ数上限Msdを、以下のように実数パラメータβを用いてsd間の最短ホップ長Hsdのβ倍に設定する。また、ノードij間に設置されたリンクを流れるトラヒック量の目標上限値βijを、全てのリンクにおいて同一の値αVに設定する。但し、αは実数パラメータである。図3に、均等割当法を用いた場合の27の各NWにおける最小パケット到達確率yminをαに対してプロットした結果を示す。但し、βを11と15に設定した場合の結果を各々示しており、また見やすくするために9つのNWごとにグラフを分けて示している。ランダムに選択したノードにおいて転送レートを更新する処理を、10N回反復した。殆どのNWは、例えばymin09を達成するためにはNW全体の総デマンド量の2~10倍程度のリンク容量が必要となる。また、フルメッシュNWはホップ長がMsd以下となる経路が多いため、リンク容量が総デマンド量の01~05倍程度であってもymin09を達成できる。小規模NW1517は、リンク負荷が低く抑えられるためα=09程度でymin=09を達成することが可能である。βの増加に伴い、経路の候補の多様性が増し、パケット到達確率が向上する効果がある反面、リンク負荷が増加するためパケット転送確率を低く抑える必要があり、パケット到達確率が低下する効果がある。後者の影響の方がより大きいため、βの増加に伴い、yminは全体的に低下する。また、図4に、最大最小到達率法を用いた場合の各NWにおける最小パケット到達確率yminを、均等割当法を用いた場合のyminで除した値をαに対してプロットする。α<1の領域では、最小パケット到達確率yminは数倍程度改善するが、α>1の領域では改善効果は小さい。このことは、αが小さくリンク容量が小さく条件が厳しいほど、最大最小到達率法を用いて転送確率を調整することで最小パケット到達確率yminを改善できることを意味する。また、βが小さい方が、最大最小到達率法による改善効果は大きい。図5に、最大最小到達率法を用いた場合の各NWにおける最小パケット到達確率yminをαに対してプロットする。依然として多くのNWでは、ymin=09を達成するにはNW全体の総デマンド量の2~10倍程度のリンク容量が必要となる。しかし、01<α<1の領域では最小パケット到達確率yminの改善効果は大きく、多くのNWで03~08程度となる。各sdペアの到達確率ysdにsdペアのトラヒックデマンド量比率を乗じて足し合わせたものを平均到達確率と定義する。図6に、最大最小到達率法を用いた場合の各NWにおける平均到達確率をαに対してプロットする。多くのNWにおいて、NW全体のトラヒックデマンド量に相当するリンク容量があれば、平均到達確率は1に近い。また、βの増加に伴い平均到達確率は僅かに低下する。上記のように本発明では、目的アドレスに基づいてパケットを転送すべき出力ポートを決めているため、NW規模目的アドレス数やNWを流れるトラヒック量の増加に伴い、パケットのルーティング処理に要する負荷が増加するという、従来技術の課題を解決することができる。なお、本発明では、上記の図1に示すノードの各構成要素の動作をプログラムとして構築し、パケットの転送を行う各ノード装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更応用が可能である。"