(57)【要約】【課題】      動的に変動するネットワークにおいて、任意のエージェント等の間での通信経路長を小さく押さえ、さらに、通信経路の修復や維持管理を低コストで行うことを可能とするネットワークシステム等を提供する。【解決手段】  一つ又は複数のエージェント等が動作するエージェント・コミュニティ・ゾーン（ＡＣＺ）は、エージェント等により構成される論理ネットワークと実際に通信を行う物理ネットワークとの間のインタフェースを提供し、ＡＣＺネットワークの経路管理を行う。ＡＣＺ間のリンクは、環状房付き順序木の構造に基づくＯＴＴリンクのような構造に基づくリンクと、その他のバイパスリンクに分類される。各ＡＣＺは、構造に基づくリンクを利用し、さらに、バイパスリンクをも利用して、通信経路長を小さく押さえ、通信経路の修復や維持管理を行う。【選択図】  図４
2008187386.tif 000002
【特許請求の範囲】
【請求項１】
複数の情報処理装置が接続され、情報処理装置間の通信がパケット転送方式により行われるネットワークシステムにおいて、
前記各情報処理装置は一つ又は複数の通信母体を管理する管理手段を一つ又は複数備え、前記各管理手段は他の管理手段に対して通信経路の探索要求を行う通信経路探索処理手段を有し、
前記各管理手段は他の管理手段に対して識別を可能とする識別情報が与えられ、前記識別情報に基づいて所定の計算式により計算される計算値が同じ管理手段のうち少なくとも１つを節管理手段とし、他の管理手段を環状房管理手段とし、
同じ計算値の節管理手段及び環状房管理手段は環状に接続され、
前記節管理手段は、異なる計算値の節管理手段の一つ又は複数と接続関係にあり、
前記節管理手段の通信経路探索処理手段は、管理対象の通信母体から他の管理手段により管理される通信母体への通信経路の確立要求がなされ、前記他の管理手段に対する通信経路が確立されていない場合に、前記他の管理手段に関して保持する情報に応じて、
同じ計算値の環状房管理手段に対して通信経路の探索要求を行うか、
接続する異なる計算値の節管理手段の一部若しくは全部に対して通信経路の探索要求を行うか、又は、
同じ計算値の環状房管理手段及び接続する異なる計算値の節管理手段に対して通信経路の探索要求を行う、
ネットワークシステム。
【請求項２】
前記節管理手段は同じ計算値の管理手段ごとに一つであり、前記節管理手段は識別情報に基づいて所定の計算式により計算される計算値による順序木を構成し、
節管理手段の通信経路探索処理手段は、前記他の管理手段の識別情報を保持する場合に、前記他の管理手段の識別情報に基づいて所定の計算式により計算される計算値が自分自身の識別情報に基づいて所定の計算式により計算される計算値と同じ場合には環状房管理手段に対して通信経路の探索要求を行い、異なる場合には順序木の構成に応じて接続する異なる計算値の節管理手段の一部又は全部に通信経路の探索要求を行う、
請求項１記載のネットワークシステム。
【請求項３】
前記管理手段は、接続する他の管理手段が接続関係から離脱する場合に、離脱する管理手段と環状の接続関係にあるときは、前記離脱する管理手段と環状の接続関係にある他方の管理手段との間に環状の接続関係を生じさせ、前記離脱する管理手段が環状房管理手段を有する節管理手段であるときは、環状房管理手段の一つを前記離脱する節管理手段の順序木上の位置とする接続関係を生じさせ、有しないときは、前記離脱する管理手段の順序木における子孫に位置する管理手段のうち前記離脱する管理手段の計算値に近いものの一つを前記離脱する管理手段の順序木上の位置とする接続関係を生じさせる接続関係管理手段を有する、請求項２記載のネットワークシステム。
【請求項４】
前記管理手段は、環状房付き順序木を構成する接続関係以外にも他の管理手段と接続関係を有し、
前記通信経路探索処理手段は、環状房付き順序木を構成する接続関係以外の接続関係にある管理手段に対しても通信経路の探索要求を行い、
前記管理手段は、通信経路の探索要求を受けた場合に、重複して通信経路の探索要求を受けたか否かを判定して重複していない場合にのみ通信経路の探索処理を行わせる重複探索排除手段を有する、
請求項２又は３に記載のネットワークシステム。
【請求項５】
前記通信母体間には親子関係があり、
前記通信経路探索処理手段は、通信経路確立の対象となる通信母体を管理する管理手段に到達できず、通信経路確立の対象となる通信母体の尊属関係にある通信母体を管理する管理手段に到達可能なときには、前記他の通信母体に直近の尊属関係にある通信母体を管理する管理手段に対して通信経路の探索要求を行う、
請求項１から４のいずれかに記載のネットワークシステム。
【請求項６】
他の情報処理装置との通信がパケット転送方式により行われる情報処理装置であって、
一つ又は複数の通信管理手段を備え、
前記各通信管理手段は他の通信管理手段に対して通信経路の探索要求を行う通信経路探索処理手段を有し、
前記各通信管理手段は他の通信管理手段に対して識別を可能とする識別情報が与えられ、前記識別情報に基づいて所定の計算式により計算される計算値が同じ通信管理手段は直接又は同じ計算値の通信管理手段を介して間接に接続関係にあり、同じ計算値の通信管理手段の少なくとも一つは異なる計算値の通信管理手段と直接接続関係にあり、
前記通信管理手段は、他の通信管理手段に対する通信経路の確立要求がなされ、前記他の通信管理手段に対する通信経路が確立されていない場合に、前記他の通信管理手段に関して保持する情報に応じて、
同じ計算値の通信管理手段に対して通信経路の探索要求を行うか、
異なる計算値の通信管理手段の一部若しくは全部に対して通信経路の探索要求を行うか、又は、
同じ計算値の通信管理手段及び異なる計算値の通信管理手段に対して通信経路の探索要求を行う、
情報処理装置。
【請求項７】
他の情報処理装置との通信がパケット転送方式により行われる情報処理装置における情報転送方法であって、
前記情報処理装置は一つ又は複数の通信管理手段を備え、前記各通信管理手段は他の通信管理手段に対して通信経路の探索要求を行う通信経路探索処理手段を有し、
前記各通信管理手段は他の通信管理手段に対して識別を可能とする識別情報が与えられ、前記識別情報に基づいて所定の計算式により計算される計算値が同じ通信管理手段は直接又は同じ計算値の通信管理手段を介して間接に接続関係にあり、同じ計算値の通信管理手段の少なくとも一つは異なる計算値の通信管理手段と直接接続関係にあり、
前記通信管理手段が、他の通信管理手段に対する通信経路の確立要求がなされ、前記他の通信管理手段に対する通信経路が確立されていない場合に、前記他の通信管理手段に関して保持する情報に応じて、同じ計算値の通信管理手段に対して通信経路の探索要求を行うか、異なる計算値の通信管理手段の一部若しくは全部に対して通信経路の探索要求を行うか、又は、同じ計算値の通信管理手段及び異なる計算値の通信管理手段に対して通信経路の探索要求を行うステップを含む、情報転送方法。
【請求項８】
コンピュータに、請求項７記載の情報転送方法を実現させるためのプログラム。
【請求項９】
請求項８記載のプログラムを記録した記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はネットワークシステム、情報処理装置、情報転送方法、プログラム及び記録媒体に関し、特に、複数の情報処理装置が接続され、情報処理装置間の通信がパケット転送方式により行われるネットワークシステム等に関する。
【背景技術】
【０００２】
隣接プラットフォームを介したパケット転送（バケツリレー方式）により行われるプラットフォームマシン間Peer-to-Peer通信や分散ファイルへのアクセスのネットワーク管理に関しては、既存の技術は大きく２つに大別できる。
【０００３】
一つは、特にネットワークに構造を持たせず、隣接ノード間で探索メッセージを伝播させていく方法である（Flooding  Search、非特許文献１、非特許文献２参照）。
【０００４】
もう一つは、ネットワークに構造を与えておいて、その構造による分散ハッシュテーブル（Distributed  Hash  Table）管理に基づいて、探索、経路維持、情報転送を行うものである（例えば、Chordの方法につき非特許文献３参照、Pastryの方法につき非特許文献４参照、Tapestryの方法につき非特許文献５参照。）。
【０００５】
【非特許文献１】Gnutella 2003, The Gnutella web site: http://gnutella.wego.com.
【非特許文献２】Ripeanu,M. and Foster,I. 2002, Mapping the Gnutellanetwork:  Macroscopic properties of large-scale peer-to-peer systems, InProceedings of the 1st International Workshop on Peer-to-PeerSystems (IPTPS’02).
【非特許文献３】Stoica,I. et.al, 2001, Chord: A scalablepeer-to-peer look-up service for internet application, In Proceedings ofSIGCOMM 2001.
【非特許文献４】Rowstron,A and Druschell,P. 2001, Pastry:Scalable distributed object location and routing for large-scale peer-to-peersystems, In proceeding of IFIP/ACM Middleware, Heidelberg, Germany.
【非特許文献５】Zhao,B. et.al, 2001, Tapestry: Aninfrastructure for fault-torelant wide-area location and routing, Tech. Rep.UCB/CSD-01-1141, Computer Science Division, University California, Berkerey.
【発明の開示】
【発明が解決しようとする課題】
【０００６】
ネットワーク管理におけるコストとしては、代表的なものとして、プラットフォームマシンの離脱等による経路維持のコスト（送信先探索コスト、経路保持コストなど。情報転送のコストも含める。）と、新規参入者の繋ぎ込みのコスト（挿入箇所探索コスト、挿入コスト、挿入後経路構成コストなど）がある。
【０００７】
しかしながら、Flooding  Searchでは、探索メッセージが無秩序にネットワーク全体に広がることとなる。そのため、経路再構成に要するコストやノードの探索コストは、最悪の場合、ネットワークノード数に比例し、経路長も、最悪の場合、ノード数に比例する。また、通信量も増大し、大規模化には適さない。
【０００８】
また、木状ネットワークを利用するChordの方法では、例えば新規ノードの参入等で最悪木の高さに依存する個数の隣接ノード修復を行う必要がある。そのため、処理が複雑となり、修復メッセージがノード間に伝搬して通信量が増大してネットワークの負荷を増大させる。Pastryの方法についても、木構造化と同様のものであり、ネットワーク管理にあたり、複雑な処理が必要でメッセージの伝搬による通信量増大が生じることとなる。Tapestryの方法についても、同様である。
【０００９】
そこで、本発明は、動的に変動するネットワークにおいて、任意の情報処理単位の間での通信経路長を小さく押さえ、さらに、通信経路の修復や維持管理を低コストで行うことを可能とするネットワークシステム等を提供することを目的とする。
【課題を解決するための手段】
【００１０】
請求項１に係る発明は、複数の情報処理装置が接続され、情報処理装置間の通信がパケット転送方式により行われるネットワークシステムにおいて、前記各情報処理装置は一つ又は複数の通信母体を管理する管理手段を一つ又は複数備え、前記各管理手段は他の管理手段に対して通信経路の探索要求を行う通信経路探索処理手段を有し、前記各管理手段は他の管理手段に対して識別を可能とする識別情報が与えられ、前記識別情報に基づいて所定の計算式により計算される計算値が同じ管理手段のうち少なくとも１つを節管理手段とし、他の管理手段を環状房管理手段とし、同じ計算値の節管理手段及び環状房管理手段は環状に接続され、節管理手段は、異なる計算値の節管理手段の一つ又は複数と接続関係にあり、節管理手段の通信経路探索処理手段は、管理対象の通信母体から他の管理手段により管理される通信母体への通信経路の確立要求がなされ、前記他の管理手段に対する通信経路が確立されていない場合に、前記他の管理手段に関して保持する情報に応じて、同じ計算値の環状房管理手段に対して通信経路の探索要求を行うか、接続する異なる計算値の節管理手段の一部若しくは全部に対して通信経路の探索要求を行うか、又は、環状房管理手段及び接続する異なる計算値の節管理手段に対して通信経路の探索要求を行う、ネットワークシステムである。
【００１１】
請求項２に係る発明は、請求項１記載のネットワークシステムであって、前記節管理手段は同じ計算値の管理手段においてそれぞれ一つであり、前記節管理手段は識別情報に基づいて所定の計算式により計算される計算値による順序木を構成し、節管理手段の通信経路探索処理手段は、前記他の管理手段の識別情報を保持する場合に、前記他の管理手段の識別情報に基づいて所定の計算式により計算される計算値が自分自身の識別情報に基づいて所定の計算式により計算される計算値と同じ場合には環状房管理手段に対して通信経路の探索要求を行い、異なる場合には順序木の構成に応じて接続する異なる計算値の節管理手段の一部又は全部に通信経路の探索要求を行うものである。
【００１２】
請求項３に係る発明は、請求項２記載のネットワークシステムであって、前記管理手段が、接続する他の管理手段が接続関係から離脱する場合に、離脱する管理手段と環状の接続関係にあるときは、前記離脱する管理手段と環状の接続関係にある他方の管理手段との間に環状の接続関係を生じさせ、前記離脱する管理手段が環状房管理手段を有する節管理手段であるときは、環状房管理手段の一つを前記離脱する節管理手段の順序木上の位置とする接続関係を生じさせ、有しないときは、前記離脱する管理手段の順序木における子孫に位置する管理手段のうち前記離脱する管理手段の計算値に近いものの一つを前記離脱する管理手段の順序木上の位置とする接続関係を生じさせる接続関係管理手段を有するものである。
【００１３】
請求項２や請求項３に係る発明にあるように、節管理手段が順序木を構成することにより、例えば、探索空間を絞り込むことが可能となり、また、新たな管理手段の繋ぎ込みや離脱に際してその影響を局所的に留め、また、ノード数nに対してO(log n)にて新たなノードの繋ぎ込みを実現可能なように、運用に適したシステムが設計可能となる。
【００１４】
請求項４に係る発明は、請求項２又は３に記載のネットワークシステムであって、前記管理手段は、環状房付き順序木を構成する接続関係以外にも他の管理手段と接続関係を有し、前記通信経路探索処理手段が、環状房付き順序木を構成する接続関係以外の接続関係にある管理手段に対しても通信経路の探索要求を行い、前記管理手段が、通信経路の探索要求を受けた場合に、重複して通信経路の探索要求を受けたか否かを判定して重複していない場合にのみ通信経路の探索処理を行わせる重複探索排除手段を有するものである。
【００１５】
環状房付き順序木上の探索では、順序木の構造から、全ノードに対して葉ノードの占める割合は50％、さらに葉ノードの親ノードまでを含めると75％である。請求項４に係る発明によれば、通信経路探索処理手段が環状房付き順序木を構成する接続関係以外の接続関係も利用することにより、葉ノードに近い節ノードから葉ノードに近い探索対象ノードへの経路が形成される可能性が高くなり、経路長を短縮することが可能となる。そして、重複探索排除手段が同一探索を排除することにより、探索経路の多重化による無駄な探索を防止する。
【００１６】
なお、請求項４に係る発明において、通信経路の探索要求の転送は、順序木を構成する接続関係による場合は転送回数が制限されず、順序木を構成する接続関係以外の接続関係による場合は転送回数が制限されているものであってもよい。
【００１７】
請求項５に係る発明は、請求項１から４のいずれかに記載のネットワークシステムであって、前記通信母体間には親子関係があり、前記通信経路探索処理手段が、通信経路確立の対象となる通信母体を管理する管理手段に到達できず、通信経路確立の対象となる通信母体の尊属関係にある通信母体を管理する管理手段に到達可能なときには、前記他の通信母体に直近の尊属関係にある通信母体を管理する管理手段に対して通信経路の探索要求を行うものである。
【００１８】
請求項５に係る発明によれば、探索すべき通信母体の上位コミュニティのうち、最下層のものを基準として通信経路の探索を実現することが可能となり、探索空間を小さいものにすることが期待可能となる。
【００１９】
請求項６に係る発明は、他の情報処理装置との通信がパケット転送方式により行われる情報処理装置であって、一つ又は複数の通信管理手段を備え、前記各通信管理手段は他の通信管理手段に対して通信経路の探索要求を行う通信経路探索処理手段を有し、前記各通信管理手段は他の通信管理手段に対して識別を可能とする識別情報が与えられ、前記識別情報に基づいて所定の計算式により計算される計算値が同じ通信管理手段は直接又は同じ計算値の通信管理手段を介して間接に接続関係にあり、同じ計算値の通信管理手段の少なくとも一つは異なる計算値の通信管理手段と直接接続関係にあり、前記通信管理手段は、他の通信管理手段に対する通信経路の確立要求がなされ、前記他の通信管理手段に対する通信経路が確立されていない場合に、前記他の通信管理手段に関して保持する情報に応じて、同じ計算値の通信管理手段に対して通信経路の探索要求を行うか、異なる計算値の通信管理手段の一部若しくは全部に対して通信経路の探索要求を行うか、又は、同じ計算値の通信管理手段及び異なる計算値の通信管理手段に対して通信経路の探索要求を行う、情報処理装置である。
【００２０】
請求項７に係る発明は、他の情報処理装置との通信がパケット転送方式により行われる情報処理装置における情報転送方法であって、前記情報処理装置は一つ又は複数の通信管理手段を備え、前記各通信管理手段は他の通信管理手段に対して通信経路の探索要求を行う通信経路探索処理手段を有し、前記各通信管理手段は他の通信管理手段に対して識別を可能とする識別情報が与えられ、前記識別情報に基づいて所定の計算式により計算される計算値が同じ通信管理手段は直接又は同じ計算値の通信管理手段を介して間接に接続関係にあり、同じ計算値の通信管理手段の少なくとも一つは異なる計算値の通信管理手段と直接接続関係にあり、前記通信管理手段が、他の通信管理手段に対する通信経路の確立要求がなされ、前記他の通信管理手段に対する通信経路が確立されていない場合に、前記他の通信管理手段に関して保持する情報に応じて、同じ計算値の通信管理手段に対して通信経路の探索要求を行うか、異なる計算値の通信管理手段の一部若しくは全部に対して通信経路の探索要求を行うか、又は、同じ計算値の通信管理手段及び異なる計算値の通信管理手段に対して通信経路の探索要求を行うステップを含む、情報転送方法である。
【００２１】
請求項８に係る発明は、コンピュータに、請求項７記載の情報転送方法を実現させるためのプログラムである。
【００２２】
請求項９に係る発明は、請求項８記載のプログラムを記録した記録媒体である。
【００２３】
なお、請求項１に係る発明において、所定の計算式はハッシュ関数であり、同じハッシュ値の管理手段は別のハッシュ関数により計算されるハッシュ値により区別可能であるものであってもよい。このような２項組みハッシュ値と環状房付き順序木の構造を利用することにより、探索のコストは、順序木の節数N（第１ハッシュ値で区別される個数）と環状房の個数M（第２ハッシュ値で区別される個数）に対して、最悪log(N)+Mとなる。
【発明の効果】
【００２４】
本願発明によれば、通信母体を管理する管理手段等の間の通信経路長を小さく押さえることが可能となり、さらに、通信経路の修復や維持管理を局所的なものとして低コストで行うことが可能となる。
【発明を実施するための最良の形態】
【００２５】
本実施例では、本願発明の「通信母体」の一例としてエージェントを用いて説明する。ここで、エージェントはＷＳやＰＣなどのプラットフォームマシンに置かれ、メッセージなどにより他のエージェントあるいはマシンから要求を受けて、その要求の処理を独立並行して行うソフトウェアである。
【００２６】
本実施例におけるエージェントは多階層の構造をもつネットワーク（以下、「論理ネットワーク」という。）を構成している。また、エージェントが置かれるプラットフォームマシンは、互いにＴＣＰ／ＩＰなどの既存のネットワーク（以下、「物理ネットワーク」という。）で接続されている。
【００２７】
図１は、本実施例におけるエージェントが構成する論理ネットワークの多階層構造を示す図である。各エージェントには、例えば郵便システムにおけるアドレスのように、論理ネットワークの階層構造に沿ってより上位（広域）から下位（局所）へ多段のアドレス付けによって論理ネットワーク上のアドレス（以下、「論理アドレス」という。）が付されている。例えば、図１を参照して、エージェントaはコミュニティB及びさらに上位のコミュニティAに属していることから、エージェントaにはA.B.aというアドレスが付与される。また、同様にエージェントBにはA.Bというアドレスが付与される。ここで、エージェントBは、他のコミュニティ又はエージェントに対して、コミュニティBがあたかも一つのエージェントであるかのように振る舞うものである。エージェントBのような振る舞いをするエージェントを、コミュニティの窓口という意味でポータルエージェントと呼ぶ。
【００２８】
論理ネットワークは物理ネットワークとは独立であり、エージェント間通信には論理アドレスが用いられ、物理ネットワークの構造は隠蔽される。
【００２９】
しかし、実際には、論理ネットワーク上でのエージェント間通信は物理ネットワーク上で行われる。本実施例においては、プラットフォームマシンにエージェント・コミュニケーション・ゾーン（Agent  Communication  Zone、以下「ACZ」という。）が設けられ、このACZが論理ネットワークと物理ネットワークのインタフェース（エージェントの論理アドレスからACZの物理アドレス及び当該ACZ内エージェントアドレスへの変換）を提供し、物理ネットワーク上での経路管理を行う。
【００３０】
ACZは一つのプラットフォームマシンに複数存在してもよい。エージェントは、新たに論理ネットワークに加入するとき、論理アドレス（以下では、名前、IDともいう。）が付与され、同時にそのエージェントが動作するACZが割り付けられる。そのため、正確には、各エージェントはそれぞれ特定のACZ上で動作していることになる。このことを考慮して、本実施例では、エージェントが動作するプラットフォームをACZと呼び、ACZにより構成される物理ネットワークをACZネットワークと呼ぶこととする。
【００３１】
図２は、図１に示される論理ネットワークがマップされたACZネットワークの一例を示す図である。図２において、ポータルエージェントにつき、エージェントAはACZ01上で、エージェントA.BはACZ03上で、エージェントA.B.CはACZ07上で、エージェントA.DはACZ09上で、エージェントEはACZ12上で、エージェントFはACZ13上でエージェントF.GはACZ10上で、エージェントF.G.HはACZ15上で、F.G.IはプラットフォームACZ16上で動作している。また、エージェントA.B.aはACZ04上で、エージェントA.B.C.bはACZ05上で、エージェントA.B.c、A.D.cはACZ06上で、エージェントA.B.C.d、A.D.dはACZ06上で、エージェントA.eはACZ03上で、エージェントA.fはACZ02上で、エージェントA.D.gはACZ01上で、エージェントE.hはACZ12上で、エージェントE.iはACZ02上で、エージェントE.jはACZ04上で、エージェントF.G.H.kはACZ14上で、エージェントF.G.H.lはACZ15上で、エージェントG.I.mはACZ13上で、エージェントF.nはACZ11上で、エージェントF.oはACZ07上で動作している。
【００３２】
図２を参照して、ACZネットワークの構造について説明する。ACZネットワークの基本構造は、順序木のノードに環状の房が繋ぎ込まれた環状房付き順序木（Ordered  Tree  with  Ringed  Tuft、以下「OTT」という。）である。図２では、この基本構造の接続関係（以下、「OTTリンク」という。）を実線で示し、他の接続関係（以下、「バイパスリンク」という。）を破線で示している。
【００３３】
図３は、図２のACZネットワークの基本構造であるOTTの概念図である。このOTTは、各ACZに与えられる物理アドレス（以下、「ACZアドレス」という。）をハッシュし、その値を用いて構成される。このとき採用されるハッシュ関数は２項組み(u,v)であり、異なるACZアドレスのハッシュ値は異なるものである。
【００３４】
順序木の構成は、各ノード（以下では、順序木を構成するノードを「節ノード」という。）並びにその左及び右の子節ノードに対応するACZのACZアドレスのハッシュ値を、それぞれ、(u,v)並びに(u1,v1)及び(u2,v2)とするとき、u1<u<u2となるものである。各節ノードの環状房には、第１ハッシュ値uが等しく第２ハッシュ値vが異なるノードが繋ぎ込まれる。なお、環状房に繋ぎ込まれるノード（以下、「環状房ノード」という。）の配置については、その対応するACZのACZアドレスの第２ハッシュ値vについての順序性はない。
【００３５】
図４は、図２のACZネットワークを、その基本構造であるOTTに基づいて表現し直した図である。図４で、例えば「ACZ01(8,3)」という記載はACZ01のハッシュ値が(8,3)であることを意味し、他の記載についても同様である。節ノードはACZ01、ACZ02、ACZ04、ACZ07、ACZ09、ACZ10、ACZ12、ACZ17であり、ACZ01には環状房ノードACZ05、ACZ06、ACZ08が、ACZ02には環状房ノードACZ03が、ACZ04には環状房ノードACZ11が、ACZ12には環状房ノードACZ14、ACZ15、ACZ16が、ACZ17には環状房ノードACZ13が繋ぎ込まれている。
【００３６】
OTTのノード間には、さらにACZ間のバイパスリンクが付加されているものもある。バイパスリンクは、エージェント間（又はACZ間）のPeer-to-Peer通信が生じたときにACZ間に張られるものである。
【００３７】
図５は、プラットフォームマシン１上で動作するＡＣＺ５を示すブロック図である。ＡＣＺ５上では、エージェント３ａ〜３ｉが動作する。また、ＡＣＺ５は、エージェント３ａ〜３ｉによる他のエージェントとの通信経路確立要求に基づいて通信経路の探索処理を行う通信経路探索処理部７と、他のＡＣＺから通信経路の探索要求が重複して行われたかを判断する重複探索排除部９と、他のＡＣＺとの接続関係を管理する接続関係管理部１１を備える。
【００３８】
ACZネットワーク上の情報転送はACZ間のパケット転送（バケツリレー方式）により行われる。各ACZは、OTTリンクとバイパスリンクにより接続された隣接ACZを求め、送信元ACZから送信先ACZへ隣接ACZを辿って情報を転送していく。この経路を制御するために、各ACZの接続関係管理部１１は４種類のテーブルを管理している。
【００３９】
第１のテーブルは局所エージェントテーブル１３（Local  Agent  Address  Table、以下「LAT」という。）である。LATは、自ACZ内に存在するエージェントの名前（ID）と当該エージェントの物理アドレスの組を一つのエントリとする。自ACZ内に存在するエージェントの物理アドレスを保持するものである。
【００４０】
第２のテーブルは遠隔エージェントテーブル１５（Remote  Agent  Address  Table、以下「RAT」という。）である。RATは、他ACZに存在するエージェントの論理アドレス（ID）と当該エージェントの存在するACZアドレスの組を一つのエントリとする。他のACZに存在するエージェントが動作するACZのアドレスを保持するものである。
【００４１】
第３のテーブルは、隣接テーブル１７（ACZ  Link  Table、以下「LT」という。）である。LTは、送信先ACZのアドレスと到達可能な隣接ACZのアドレスの組を一つのエントリとし、情報送信先ACZへ至る経路上の隣接ACZのアドレスを保持する。
【００４２】
第４のテーブルは、OTT上の親、左子、右子、環状房左隣、環状房右隣の各リンクを保持するOTT隣接リンクテーブル１９（Adjacent  AT  Table  on  OTT、以下「AT」という。）である。ATは、親ACZアドレス、左子ACZアドレス、右子ACZアドレス、環状房左隣ACZアドレス、及び、環状房右隣ACZアドレスの組を一つのエントリとする。なお、これらのリンクは隣接リンクなのでLT中にも保持されており、実装上はLTとATをまとめて一つのテーブルで管理する方法がとられるが、ここでは説明を分かりやすくするために、概念的にLTと区別してATを設ける。
【００４３】
図６は、ACZ01の持つテーブルの内容の一例を示す図であり、（ａ）はLATの例、（ｂ）はRATの例、（ｃ）はLTの例、（ｄ）はATの例である。実際には、これらの各テーブルは有限のサイズであり、ネットワークの接続情報を全て完全に保持することは不可能である。各テーブルのサイズがある有限値に設定されているため、新たなACZが登録されようとするとき、そのサイズを超える場合には優先度の低いACZがテーブルから追い出されることになる（優先度の設定には、例えば最近一定期間の通信回数が考えられる（Least  Recently  Used）。）。このため、一度テーブルに登録されたリンク情報が常にテーブル上に存在しているとは限らない。本実施例は、このことをも考慮した頑健なネットワーク経路管理方式を提供するものである。
【００４４】
続いて、ACZ間通信及びACZ間経路管理について説明する。本実施例では、通信を行うACZの間ではAckのやり取りを行い、互いに相手の存在を確認しあうこととする。
【００４５】
ACZ間の情報転送は、送信元ACZから送信先ACZへの通信経路上にある各ACZの隣接ACZリンクを辿り、パケット転送により行われる。なお、LTにはOTTリンク及びバイパスリンクが登録されており、隣接ACZへのリンクはOTTリンク及びバイパスリンクにより与えられるとする。この通信経路の探索処理は、図５の通信経路探索処理部７により行われる。
【００４６】
あるエージェントから他のエージェントへの情報転送に際して、送信先エージェントが同一ACZ上にあれば（LATに登録されていれば）そのエージェントに渡される。送信先エージェントが他のACZ上にあれば（LATになくRATに登録されていれば）送信先ACZに転送されたのち、転送先ACZ上のLATを見て転送先エージェントに渡される。LATにもRATにも登録されていなければ、ACZは送信先エージェント及びそのACZへの経路を探索し、両エージェント間の通信経路を作り出す。
【００４７】
まず、すでに通信経路が形成されている場合の転送法について説明する。転送パケットの構造は、［送信先エージェント名、送信先ACZアドレス、送信情報コンテンツ］である。このパケットを受け取ったACZは、自分が送信先ACZであるかを判断し、そうならば送信先エージェントは自ACZ上に存在しているのでLATによりその物理アドレスを知る。自分が送信先ACZでなければ、LTを見て送信先ACZへの経路上にある隣接ACZを取り出して、その隣接ACZへパケットを転送する。
【００４８】
このLTを用いたメッセージ転送について、図７を参照して説明する。図７は、LTを用いた、ACZ04上のエージェントA.B.aからACZ12上のエージェントE.h及びACZ13上のエージェントF.G.I.mへの情報転送の一例を示す図である。
【００４９】
まず、ACZ04上のエージェントA.B.aからACZ12上のエージェントE.hへの情報転送について説明する。エージェントA.B.aはACZ04上にあり、ACZ04でメッセージを発信する。ACZ04はRATを見てエージェントE.hがACZ12上にあることを知る。そこで、ACZ04はLTを調べ、ACZ12が隣接していることを知り、ACZ12にメッセージを転送する。ACZ12はLATを見てエージェントE.hが自分のところにあるのを確認し、その物理アドレスにメッセージを届ける。
【００５０】
次に、ACZ04上のエージェントA.B.aからACZ13上のエージェントF.G.I.mへの情報転送について説明する。ACZ04はRATを見て、エージェントF.G.I.mがACZ13上にあることを知る。次に、ACZ04はLTを見てACZ13に至る経路上にある隣接ACZがACZ08、ACZ11、ACZ12であることを知る。ここでは、まず、ACZ08が選ばれ、ACZ04はACZ08にメッセージを転送するとする。転送メッセージを受け取ったACZ08はACZ04と同様にして、LTより隣接するACZ06にメッセージを転送する。ACZ06も同様にしてメッセージをACZ13に転送する。ACZ13は自分がメッセージの送信先であることを知り、LATよりエージェントF.G.I.mが自分のところにあることを確認して、その物理アドレスにメッセージを届ける。この場合の転送経路は３ホップACZ04→ACZ08→ACZ06→ACZ13である。
【００５１】
何らかの原因でACZ08がOTTから離脱している（ACZ08からACZ04にAckシグナルが返されない）とすると、隣接ACZとしてACZ11が選ばれることになり、この場合の転送経路はACZ04→ACZ11→ACZ06→ACZ13となる。このように、隣接ACZを複数登録して、冗長な転送経路を保持しておくことによって、新たな経路探索を行う確率を下げることができる。
【００５２】
送信先エージェントが送信元ACZのLAT、RATに登録されていない場合は、エージェントの探索を行い、その送信先ACZへの経路を構成し、送信先エージェントとそのACZアドレスを送信元ACZのRATに登録する。
【００５３】
エージェントの探索は以下の方法で行う。図５の通信経路探索処理部７は、まず探索対象エージェントあるいはそのエージェントが属している上位コミュニティのポータルエージェントが動作しているACZがRATに登録されているかを調べる。ここで、エージェントの名前は論理ネットワークのアドレス構造を反映していることから、RATの検索はエージェントの名前のプレフィックス最長一致で行う。プレフィックス最長一致をとる理由は、一致したエージェントは探索すべきエージェントがメンバーとなっている上位コミュニティのうち一致が取れる最下層のものであり、探索すべきエージェントのACZアドレスの探索空間が最小のものに絞れることを期待できるからである。
【００５４】
エージェント名に完全一致する場合には、そのエージェントが動作しているACZが分かる。
【００５５】
エージェント名の最長プレフィックス部分が一致する場合には、そのプレフィックス部分を名前とするエージェントが動作しているACZのアドレスが分かる。このACZ（以下、「探索中継ACZ」という。）に対して探索エージェントの探索を依頼する。依頼を受けた探索中継ACZは探索すべきエージェントの探索手がかりが自RATに登録されているかどうかを調べる。以下同様にして探索中継ACZを介して目的エージェントのACZを探索する。
【００５６】
プレフィックスが一致しない場合には、RATには探索手がかりが登録されていない。そのため、OTT全域にわたってエージェントの探索を行う。各ACZは全隣接ACZに対してエージェント探索メッセージを転送する。探索メッセージを受けた隣接ACZは、同様にして探索対象エージェントの探索を行う。
【００５７】
例として、今、ACZ01で動作しているエージェントA.D.gが他のエージェントを探索する場合を考える（図６（ｂ）に示すACZ01のRATを参照。）。
【００５８】
エージェントA.D.dを探索する場合、ACZ01のRATにA.D.dが登録されており、このエージェントはACZ06にあることが分かる。
【００５９】
エージェントA.B.cを探索する場合、プレフィックス最長一致によりエージェントA.BがACZ03で動作していることを知る。そして、ACZ03を探索中継ACZとして探索を依頼する。
【００６０】
エージェントF.G.H.kを探索する場合、このエージェント及びその上位コミュニティのポータルエージェントが動作するACZはRATに登録されていない。そこで、LT及びATに登録されている全隣接ACZ（ACZ02、ACZ04、ACZ05、ACZ08、ACZ12）に対して探索メッセージを発信する。（今の場合、ACZ01はOTTの根ノードであるので親は存在しない。）またLTに登録されているもののうちATに登録されていないもの（ACZ12）がバイパスリンクACZである。ACZ02、ACZ04、ACZ05、ACZ08、ACZ12はそれぞれ同様のエージェントの探索処理を行う。
【００６１】
子ノードから探索メッセージを受け取ったとき、探索すべきエージェントが自分であるかを調べる。自分でなければ環状房上を左（又は右）向きに探索メッセージを流し、環状房中に該当エージェントが存在するかを調べる。環状房中にあれば探索を終了する。
【００６２】
環状房中にない場合、右（又は左）子ノードからのメッセージ受け取りであれば、左（又は右）子ノードを根ノードとするOTT部分木を下向きに探索する。同時に、OTTの親ノード及びバイパスリンク隣接ノードに対して探索メッセージを転送する。親、左右子以外のバイパスリンクによる受け取りであれば、左右両子ノードを根ノードとするOTT部分木を探索する。
【００６３】
探索メッセージは全ての隣接ACZに対して送出されるので、探索は接続リンクを通して広がっていく。探索経路長は、OTTの節数n、環状房のリング周長mに対して高々2*log(n）+mであるが、実際にはバイパスリンクを利用することによって経路長が短縮できる。バイパスリンクを併用すれば、バイパスリンクを通して探索対象エージェントを短い探索経路で早く見つける可能性が高くなるが、探索経路が多重化し無駄な探索が生じることになる。この無駄をなくすために、探索メッセージは探索が終了するまで各ノードに保持され、各ACZの重複探索排除部９は同一探索メッセージの多重受け取りのチェックを行う。
【００６４】
また、探索メッセージは探索経路スタックを持ち、経路探索過程で経由してきたACZの系列がスタックされる。さらに、探索メッセージには探索ホップ数に上限が設けられて探索空間の広がりを抑える。ただし、探索の完全性を保証するためにOTTの上向き及び下向きの探索ではホップ数の上限は無視する。
【００６５】
経路探索の結果、探索すべきエージェントの存在するACZのアドレスが得られたとき、送信先ACZはLTに送信元ACZのアドレスを登録し、探索で得られた経路上の各ACZはLTに両隣ACZのアドレスを登録し、送信元ACZは返された送信先ACZのアドレスをLTに登録することにより、送信元ACZと送信先ACZを繋ぐ双方向経路及び送信元ACZと送信先ACZ間の双方向バイパスリンクが形成される。
【００６６】
この探索メッセージによる探索について、具体的に説明する。探索メッセージの構造は、［探索対象エージェント名、探索経路スタック、探索送信元エージェント＋ACZ、探索ホップ数］である。送信元ACZは探索メッセージに初期値を設定して全ての隣接ACZに送出する。探索メッセージの初期値として、探索対象エージェント名として探索すべきエージェント名が、探索経路スタックとしてｎｉｌが、探索送信元エージェント＋ACZとして自エージェント名及び自ACZアドレスが、探索ホップ数として０が設定される。
【００６７】
探索メッセージを受けた各ACZの重複探索排除部９は、同一探索メッセージをすでに受け取っているかをチェックし、すでに受け取っていればこの探索メッセージを破棄して終了する。
【００６８】
当該ACZ探索メッセージの初めての受け取りならば、転送元の隣接ACZアドレスを探索メッセージの探索経路スタックに積む。そして、LATを見て、探索対象エージェントが自ACZにあるかを調べる。存在すれば探索を終了する。LATになければRATを見て探索対象エージェントの名前とプレフィックス最長一致がとれるものがあるか調べ、あればこれを探索中継ACZとする探索を行う。RATにも探索対象エージェントが存在しなければ、LTを見てその隣接ACZへ探索メッセージを送出する。
【００６９】
探索対象エージェントの存在するACZに到達したら、そのACZアドレスを探索発信元ACZ宛に返信する。返信メッセージは探索経路スタックに積まれているACZ経路系列を逆順に辿り、探索発信元に転送される。
【００７０】
返信メッセージの構造は、［探索対象エージェント名＋ACZ、探索経路スタック、探索発信元エージェント＋ACZ］である。返信メッセージの転送過程で、経路上の各ACZは隣接ACZアドレスをLTに登録し、双方向リンクを張ることによって、探索元ACZと探索対象ACZの間の双方向経路情報を生成する。
【００７１】
まず、探索対象ACZは、探索元エージェント名とそのACZアドレスをRATに登録し、探索経路スタックの先頭にある隣接ACZアドレスと探索元ACZをLTに登録する。
【００７２】
経路上の各ACZは、返信メッセージを受け取ったとき、探索経路スタックの先頭にある隣接ACZアドレス及び探索対象ACZアドレスをLTに登録し、探索経路スタックをポップアップし、探索元ACZアドレス及び探索経路スタックの先頭にある隣接ACZアドレスをLTに登録し、探索経路スタックの先頭にある隣接ACZに返信メッセージを送信し、保持していた探索メッセージを破棄する。
【００７３】
返信メッセージが探索元ACZに到達したら、探索元ACZは、返信元ACZ（探索対象ACZ）アドレスと探索経路スタックの先頭にある隣接ACZアドレスとをLTに登録し、探索経路スタックをポップアップし、探索対象エージェント名とそのACZアドレスをRATに登録し、保持していた探索メッセージを破棄する。
【００７４】
続いて、ACZ間の経路がシステム運用中に切れたりするような場合に、送信先ACZの探索とACZ間転送経路の構築について説明する。送信先へ至る隣接ACZは、例えば、送信先ACZへの転送経路上のACZの離脱（プラットフォームマシンの電源切れやシステムダウン、エージェントやACZの意図的なネットワークからの離脱など）や隣接ACZへのリンクの消滅（RATあるいはLTのオーバフローによる隣接ACZアドレスの消滅など）により失われる。その場合、送信先へ至る隣接ACZを失ったACZを新たな探索元ACZとして送信先ACZを探索し、転送経路を再構成する。また、各ACZは定期的にLTに登録されている送信先へ至る隣接ACZが存在しているか否かをチェックし、隣接ACZが失われていれば送信先ACZを探索して新たな転送経路を再構成する。
【００７５】
ACZの探索においては探索先ACZのアドレスのハッシュ値(u，v)を求め、このハッシュ値を用いて送信先ACZへ至る経路を探索する。探索手順は、エージェント探索においてはRATからエージェントIDのプレフィックス最長一致によって論理ネットワーク上の探索空間を絞り込んだのに対して、ACZ探索ではハッシュ値を用いてOTT探索空間の絞り込みを行う点を除いてエージェント探索の場合とほとんど同じである。
【００７６】
まず、送信元ACZに隣接しているACZに対して探索メッセージを転送する。探索メッセージの構造は、［探索対象ACZのハッシュ値(u，v)、探索経路スタック、探索元ACZ、探索ホップ数］である。経路探索にはOTTリンク及びバイパスリンクを併用して行う。OTTリンク上での探索は、探索対象ACZのハッシュ値の2項組みを(u,v)とすると、まずハッシュ値uに等しいOTT節ノードを探索し、次に探索された節ノードの環状房に対してハッシュ値vに等しいノードを探すことにより行われる。この探索では、探索対象が存在するかどうかが分かり、存在すれば必ず成功する（探索の完全性が保証されている）。
【００７７】
OTT上の経路探索では、順序木の構造から、全ノードに対して葉ノードの占める割合は50%、さらに葉ノードの親ノードまでを含めると75%（さらにその親までも含めると87.5%）である。バイパスリンクを利用せずに単純にOTTの経路探索を行って経路を形成した場合、葉ノードに近い節ノードから根ノードに近いノードに上がり、次に葉ノードに近い探索対象ノードへ下がって行く経路が形成される確率が高く、ほとんどの経路の長さはlog(n)となり、無視できない長さである。そこで、以下に説明するように、OTT上の経路探索に部分木における第１ハッシュ値の最小値及び最大値を用いて、経路長の短縮を図ってもよい。
【００７８】
各ACZは、自分の第１ハッシュ値、並びに、自分を根ノードとするOTT部分木における第１ハッシュ値の最小値及び最大値を保持しておく。また、LTに登録されている隣接ACZの第１ハッシュ値、並びに、そのノード（ACZ）を根ノードとするOTT部分木の第１ハッシュ値の最小値及び最大値をLTに保持しておく。（LTの各エントリを、送信先ACZのアドレス及び到達可能な隣接ACZのアドレスに加えて、隣接ACZの第１ハッシュ値、並びに、部分木の第１ハッシュ値の最小値及び最大値の組を保持するように拡張する。）
【００７９】
図８を参照して、探索元あるいは探索メッセージを受信したノード（ACZ）n0の動作について説明する。図８は、探索メッセージの送信先ノードを説明する図である。図８において、ノードに付された記号n(u,umin,umax)は、ノードnについて、第１ハッシュ値がu、これを根ノードとするOTTにおける最小第１ハッシュ値がumin、最大第１ハッシュ値がumaxであることを示す。
【００８０】
探索対象ACZの第１ハッシュ値をuとし、探索元あるいは探索メッセージを受信したACZ n0の第１ハッシュ値をu0、自身を根ノードとするOTT部分木の第１ハッシュ値の最小値をu0min、最大値をu0maxとする。u=u0ならば、節ノードn0の環状房中のv=v0であるノードを見つける。
【００８１】
u≠u0かつu0min≦u≦u0maxならば、自分を根ノードとするOTT部分木の下方探索を行う（図８の（ａ）参照）。下方探索では、バイパスリンク先がもつOTT部分木の第１ハッシュ値の最小値をuk-min、最大値をuk-maxとして、u0min＜uk-min≦uk＜u≦uk-max＜u0maxまたはu0min＜uk-min≦u＜uk≦uk-max＜u0maxを満たすもののうち、uk-max−uk-minが最小のノードnkへ探索メッセージを送る。ノードnkはさらに下方探索を行う。そのようなnkがなければ、u<u0ならば左子へ、u0<uならば右子へ、探索メッセージを送る。メッセージを受け取った左（右）子ノードは下方探索を行う。
【００８２】
u<u0minあるいはu0max<uならば（すなわち、上記の２つの場合以外のとき）、部分木探索を行わず、現ホップ数がホップ数上限値以下ならばホップ数を＋１して現ACZのLTに登録されている全ての隣接ACZに探索メッセージを送り（図８の（ｂ）参照）、現ホップ数がホップ数上限値を超えていれば探索を終了する。
【００８３】
なお、このOTT探索はノード数nに対して高々O(log n)であるが、実際には、O(log n)をかなり下回ることが期待される。
【００８４】
経路探索により送信先ACZのアドレスが得られたとき、送信元ACZと送信先ACZを繋ぐ双方向経路及び送信元ACZと送信先ACZ間の双方向バイパスリンクは、送信先ACZはLTに送信元ACZのアドレスを登録し、経路上にある各ACZのLTに両隣のACZのアドレスを登録し、送信元ACZは返された送信先ACZのアドレスをLTに登録することにより形成される。
【００８５】
OTTリンク及びバイパスリンクによる探索操作を具体的に説明する。
【００８６】
まず、送信元ACZは、探索メッセージ[探索対象ACZ、探索経路スタック、探索元Agent＋ACZ、 探索ホップ数]の初期値を設定して（探索ACZとして探索対象ACZアドレスが、探索経路スタックとしてnilが、探索発信元ACZとして自ACZアドレスが、探索ホップ数として探索ホップ数の上限値が設定される。）、これを全ての隣接ACZに送出する。
【００８７】
探索メッセージを受け取ったACZは、まず、同一探索メッセージをすでに受け取っているかをチェックし、すでに受け取っていればこの探索メッセージを破棄して終了する。当該探索メッセージの初めての受け取りならば、送り元隣接ACZアドレスを探索メッセージの探索経路スタックに積み、LTを見て、その隣接ACZへ探索メッセージを送出する。（OTT上の探索は図８を用いて説明したアルゴリズムに従う。）
【００８８】
探索すべきACZに到達したら、そのACZアドレスを探索元ACZ宛に返信する。返信メッセージは探索経路スタックに積まれたACZ経路を逆順に辿り探索元に転送していく。返信メッセージの構造は［探索対象ACZ、探索経路、探索元Agent＋ACZ、（自分の第１ハッシュ値、OTT部分木の最小第１ハッシュ値、OTT部分木の最大第１ハッシュ値）］である。
【００８９】
返送メッセージの転送過程で、経路上の各ACZは、隣接ACZアドレス並びにその第１ハッシュ値、OTT部分木の最小第１ハッシュ値及びOTT部分木の最大第１ハッシュ値をLTに登録し、双方向リンクを張ることによって探索元ACZと探索対象ACZの間の双方向経路情報を生成する。探索対象ACZは、発信元Agent名とACZアドレスをRATに登録し、探索経路スタックの先頭にある隣接ACZアドレスとその（自分の第１ハッシュ値、OTT部分木の最小第１ハッシュ値、OTT部分木の最大第１ハッシュ値）、および探索発信元ACZをLTに登録する。経路上の各ACZは、返信メッセージを受け取ると、探索経路スタックの先頭にある隣接ACZアドレスと返信元ACZ（すなわち探索対象ACZ）アドレスをLTに登録し、探索経路スタックをポップアップし、探索経路スタックの先頭にある隣接ACZアドレスとその（自分の第１ハッシュ値、OTT部分木の最小第１ハッシュ値、OTT部分木の最大第１ハッシュ値）、および探索発信元ACZアドレスをLTに登録し、保持していた探索メッセージを破棄する。これを返信メッセージが返信先（探索元）ACZに届くまで繰り返す。返信メッセージが探索元ACZに到達すると、探索元ACZは、探索経路スタックの先頭にある隣接ACZアドレス並びに返信元ACZ（探索対象ACZ）のアドレス、その第１ハッシュ値、OTT部分木の最小第１ハッシュ値及びOTT部分木の最大第１ハッシュ値をLTに登録し、探索経路スタックをポップアップし、探索対象エージェント名とそのACZアドレスをRATに登録し、保持していた探索メッセージを破棄する。
【００９０】
次に、エージェントが新規に加入する場合の接続関係管理部１１によるOTTリンクの形成について説明する。エージェントがコミュニティに加入するとき、そのエージェントが動作するACZがすでにOTTに存在しているか否かを調べ（これは探索過程と同様の方法）、存在していなければそのACZを新規ノードとしてOTTに繋ぎ込む。新規ノードの追加並びに各ノードにおける第１ハッシュ値の最大値及び最小値の維持管理は以下のように行われる。
【００９１】
追加される新規ノードの第１ハッシュ値をuとし、上記と同様にして第１ハッシュ値がuであるOTT節ノードnを探す。第１ハッシュ値がuであるOTT節ノードnが存在すれば、その環状房に新規ノードを追加する。
【００９２】
第１ハッシュ値がuであるOTT節ノードnが存在しない場合、新規ノード追加メッセージを受け取った節ノードをn0とし、このノードのもつOTT部分木の第１ハッシュ値の最小値と最大値をu0min、u0maxとする。このとき、u0min≦u≦u0maxならば新規ノードはこのOTT部分木の中に追加されることになるので、バイパスリンク先がもつOTT部分木の第１ハッシュ値の最小値をuk-min、最大値をuk-maxとして、u0min＜uk-min≦uk＜u≦uk-max＜u0maxまたはu0min＜uk-min≦u＜uk≦uk-max＜u0maxを満たすもののうち，uk-max−uk-minが最小であるnkへ新規ノード追加メッセージを送る。
【００９３】
u<u0minならば、新規ノードは最左の葉ノードとなるので、n0のもつ第１ハッシュ最小値をuに置き換え（u0minをuとし）、左子に新規ノード追加メッセージを送る。このメッセージを受け取ったノードが葉ノードならば新規ノードを左子の葉ノードとして生成する。また、u0max<uならば、新規ノードは最右の葉ノードとなるので、n0のもつ第１ハッシュ最大値をuに置き換え（u0maxをuとし）、右子に新規ノード追加メッセージを送る。n0が葉ノードの場合は新規ノードを右子の葉ノードとして生成する。
【００９４】
図９は新規ノードを追加する場合の一例を示す図である。図９（ａ）は左子の葉ノードとして追加する場合であり、ACZ0のuk-minが更新される。図９（ｂ）は右子の葉ノードとして追加する場合の一例を示す図であり、ACZ0のuk-maxが更新される。
【００９５】
新規葉ノードの追加によってその親が持つ部分木最大（あるいは最小）第１ハッシュ値が変化するので、その更新を行う。この変更によってさらにその親ノードの最大（あるいは最小）第１ハッシュ値の変更が必要な場合はその変更を行う。祖先ノードについて必要な限りこの操作を繰り返す。
【００９６】
なお、このOTT探索と新規ノードの生成はノード数nに対して高々O(log n)であるが、実際には、O(log n)をかなり下回ることが期待される。
【００９７】
次に、図１０を参照して、ACZがネットワークから離脱して隣接リンクが切断した場合に、接続関係管理部１１による隣接リンクの張り直しについて説明する。図１０は、ACZの離脱時の動作の一例を示す図である。
【００９８】
隣接リンクの切断がACZのネットワークからの自発的な離脱により生じる場合、離脱するACZが隣接ACZに対して離脱する旨の通知を行うので、離脱通知を受けた隣接ACZは隣接リンクの張り直しを行う。しかし、予期せぬ原因によって離脱が生じる場合がある。そのため、各ACZは隣接ACZへの接続リンクが有効かを定期的にチェックし、もし隣接リンクが切れていたら隣接リンクの張り直しを行う。この隣接リンクの張り直しについて、以下説明する。なお、リンクの張り直しが行われる前に送信先への情報転送要求が起こる場合もあるが、この場合は、上述のように送信先の探索と経路再構成を行う。
【００９９】
離脱するノードが環状房ノードの場合（図１０（ａ）参照）、離脱ノードnの環状左隣ノードm1、環状右隣ノードm2のリンクを張り直す。これは、環状房左右隣接ノードm1、m2のATのアドレスを更新することにより行われる。
【０１００】
環状房ノードが存在する順序木の節ノードが離脱する場合（図１０（ｂ）参照）、離脱節ノードnの環状房右隣のノードmを節ノードnの位置に移動する。ノードm，環状左隣ノードm1，左子ノードn1，右子ノードn2及び親ノードn0のATを更新して隣接リンクを張り直す。
【０１０１】
環状房ノードが存在しない順序木の節ノードが離脱する場合（図１０（ｃ）参照）、離脱節ノードｎの左子節ノードの最右子孫葉ノードm1あるいは右子節ノードの最左子孫葉ノードｍ２をｎの位置に移動する。特に、右子節ノードがない場合はm1（左子節ノードがない場合はm2）をnの位置に移動する。親ノードn0，左子ノードn1，右子ノードn2（m1あるいはm2）のATを更新して隣接リンクを張り直す
【０１０２】
なお、ノードの離脱が生じた場合、その祖先である各節ノードが持つOTT部分木の第１ハッシュ最大値、最小値が変化する。このとき、最大値がそれより小さな値に変化、あるいは最小値がそれより大きな値に変化する場合はこの変化を各ノードに反映させなくても探索の安全性は保証されるので、各ノードのもつ最大値、最小値の変更は行わない。最大値がより大きな値に変化、あるいは最小値がより小さな値に変化する場合は、親ノードの持つ最大（最小）第１ハッシュ値の更新を行う。
【０１０３】
なお、本実施例において、各エージェントはファイル管理を行い、分散ファイルシステムを構築するものであってもよい。
【図面の簡単な説明】
【０１０４】
【図１】本実施例におけるエージェントが構成する論理ネットワークの多階層構造を示す図である。
【図２】図１に示される論理ネットワークがマップされたACZネットワークの一例を示す図である。
【図３】図２のACZネットワークの基本構造である環状房付き順序木（OTT）の概念図である。
【図４】図２のACZネットワークを、その基本構造であるOTTに基づいて表現し直した図である。
【図５】プラットフォームマシン１上で動作するＡＣＺ５を示すブロック図である。
【図６】ACZ01の持つテーブルの内容の一例を示す図であり、（ａ）はLATの例、（ｂ）はRATの例、（ｃ）はLTの例、（ｄ）はATの例である。
【図７】LTを用いた、ACZ04上のエージェントA.B.aからACZ12上のエージェントE.h及びACZ13上のエージェントF.G.I.mへの情報転送の一例を示す図である。
【図８】探索メッセージの送信先ノードを説明する図である。
【図９】新規ノードを追加する場合の一例を示す図である。
【図１０】ACZの離脱時の動作の一例を示す図である。
【符号の説明】
【０１０５】
１  プラットフォームマシン、３ａ〜３ｉ  エージェント、５  エージェント・コミュニティ・ゾーン（ＡＣＺ）、７  通信経路探索処理部、９  重複探索排除部、１１  接続関係管理部
【図１】
2008187386.tif 000003
【図３】
2008187386.tif 000004
【図５】
2008187386.tif 000005
【図６】
2008187386.tif 000006
【図７】
2008187386.tif 000007
【図８】
2008187386.tif 000008
【図９】
2008187386.tif 000009
【図１０】
2008187386.tif 000010
【図２】
2008187386.tif 000011
【図４】
2008187386.tif 000012