JP4488094B2 - 通信ノードと通信方法およびコンピュータ・プログラム - Google Patents

Description

この発明は、通信ノードと通信方法およびコンピュータ・プログラムに関する。詳しくは、分散ハッシュテーブルを用いたリング状のネットワークにおいて、アクセス不能なノードが発生しても、このアクセス不能なノードを除いてネットワークを自動的に修復できるようにするものである。

近年、サーバ機能を分散することでスケーラビリティを確保できるＰ２Ｐ（Peer-to-Peer）ネットワークが重要視されてきている。Ｐ２Ｐネットワークは、コンピュータネットワーク上に構成されたコンピュータネットワークであるオーバーレイネットワークであり、ＩＰネットワークのトポロジーを意識せずに通信することができるようになされている。また、オーバーレイネットワークを構成する際に、通信したい相手(ノード)を高速に検索するため分散ハッシュ技術が用いられている。

分散ハッシュ技術を用いる代表的なプロトコルとして、Ｃｈｏｒｄが非特許文献１で開示されている。Ｃｈｏｒｄは、ＩＰアドレスなどから取ったハッシュ値がノードＩＤとされているノードによって、リング状のオーバーレイネットワーク（以下「Ｃｈｏｒｄリング」という）を構成したものである。また、Ｃｈｏｒｄリング上にあるすべてのノードは、Ｃｈｏｒｄリング上の各ノードと正しく通信経路クを確保するためのルーティング情報を保持している。ここで、時計回りで次のノードはサクセサ（successor）、反時計回りで次のノードはプレデセサ（predecessor）と呼ばれており、このサクセサおよびプレデセサを示す情報はルーティング情報として用いられる。また、各ノードにおいて、サクセサおよびプレデセサが正しいノードを示していれば、すべてのノードが正しく接続されて、Ｃｈｏｒｄリングとしての正確性（correctness）が保たれることになる。

また、特許文献１では、リング状のオーバーレイネットワークを用いてコンテンツデータの配信を行うことが開示されている。

「Chord：A Scalable Peer-to-peer Lookup Protocol for Internet Applications」Ion Stoica, Robert Morris, David Liben-Nowell, David R. Karger, M. Frans Kaashoek, Frank Dabek,Hari Balakrishnan.IEEE Transactions on Networking Vol 11, February 2003 特開２００６−１９５６９４号公報

ところで、Ｃｈｏｒｄでは、何らかの原因でＣｈｏｒｄリングを構成しているノードがアクセス不能となった場合、ルーティングを正しく行うことができなくなってしまう。このため、非特許文献１では、ノードがアクセス不能となった場合でも、ルーティングを正しく行うことができるように、ルーティング情報として記憶するノードの数を増やすことが示されている。すなわち、ノードが１つのサクセサだけをルーティング情報として記憶するだけでなく、このノードのサクセサが示すサクセサ、さらに、このサクセサが示すサクセサ等をルーティング情報として記憶する。このように、複数個のサクセサをもつ「Successor-List」をルーティング情報として記憶する場合、「Successor-List」のサイズをｒ、「Successor-List」にある各サクセサが「Node Failure」となる発生確率を１／ｎとすると、すべてのサクセサが「Failure」を起こし、システムの正確性が失われることになる確率は、１／(ｎのｒ乗)まで下がることになる。このように、ルーティング情報として記憶するノードの数を増やすことでシステムの正確性が失われる確率を下げることはできるが、根本的に上記問題を回避することはできない。

そこで、この発明では、アクセス不能なノードが生じてもネットワークを自動的に修復可能とする通信ノードと通信方法およびコンピュータ・プログラムを提供するものである。

この発明の第１の側面は、
分散ハッシュテーブルを用いたリング状のネットワーク上における次ノードと前ノードを示すノード情報を記憶するルーティング情報記憶部と、
前記ルーティング情報記憶部に記憶されているノード情報の更新を行うルーティング情報更新部を備え、
前記ルーティング情報更新部は、次ノードがアクセス不能となったとき、前記ネットワーク上で常にアクセス可能とされている所定の１つのノードから前ノードを示すノード情報の取得を行い、該取得したノード情報に基づき該ノード情報を供給したノードが次ノードとなる判定条件を満たすか否か判定して、前記次ノードとなる判定条件を満たすとき、該ノード情報を供給したノードを前記次ノードに設定し、前記次ノードとなる判定条件を満たさないとき、前記取得したノード情報で示された前ノードから前記ノード情報を取得して、該ノード情報を供給したノードが次ノードとなる判定条件を満たすか否か判定する通信ノードにある。

この発明の通信ノードにおいて、ルーティング情報記憶部では、分散ハッシュテーブルを用いたリング状のネットワーク、例えばＣｈｏｒｄプロトコルを用いたリング状のオーバーレイネットワークであるＣｈｏｒｄリングにおいて、次ノードを示すノード情報と前ノードを示すノード情報がルーティング情報として記憶される。このルーティング情報の更新を行うルーティング情報更新部は、次ノードがアクセス不能となったとき、ネットワーク上で常にアクセス可能とされている所定の１つのノードから前ノードを示すノード情報の取得を行い、取得したノード情報に基づき、このノード情報を供給したノードが次ノードとなる判定条件を満たすか否か判定する。ここで、自己がノード情報で示された前ノードからノード情報を供給元したノードまでの間に位置するとき、またはノード情報で前ノードが示されていないとき、判定条件を満たすものとして、ノード情報を供給したノードを次ノードに設定する。また、判定条件を満たさないとき、すなわち、自己がノード情報で示された前ノードからノード情報を供給元したノードまでの間に位置していないとき、取得したノード情報で示された前ノードからノード情報を取得して、このノード情報を供給したノードが次ノードとなる判定条件を満たすか否かの判定を行うことで、所定の１つのノードを起点として、前ノードの方向に順に各ノードが自己の次ノードに得るか判定されて、次ノードとなる判定条件を満たすとき、このノードが自己の新たに次ノードとされる。

この発明の第２の側面は、
分散ハッシュテーブルを用いたリング状のネットワーク上における次ノードがアクセス不能となったとき、ルーティング情報更新部によって、前記ネットワーク上で常にアクセス可能とされている所定の１つのノードから前ノードを示すノード情報を取得するステップと、
前記ルーティング情報更新部によって、取得した前記ノード情報に基づき該ノード情報を供給したノードが次ノードとなる判定条件を満たすか否か判定して、前記次ノードとなる判定条件を満たすとき、該ノード情報を供給したノードを前記次ノードに設定し、前記次ノードとなる判定条件を満たさないとき、前記取得したノード情報で示された前ノードから前記ノード情報を取得して、該ノード情報を供給したノードが次ノードとなる判定条件を満たすか否か判定するステップを有する通信方法にある。

また、この発明の第３の側面は、
分散ハッシュテーブルを用いたリング状のネットワークに接続されているコンピュータに、
前記ネットワーク上の次ノードがアクセス不能となったとき、前記ネットワーク上で常にアクセス可能とされている所定の１つのノードから前ノードを示すノード情報を取得するステップと、
取得した前記ノード情報に基づき該ノード情報を供給したノードが次ノードとなる判定条件を満たすか否か判定して、前記次ノードとなる判定条件を満たすとき、該ノード情報を供給したノードを前記次ノードに設定し、前記次ノードとなる判定条件を満たさないとき、前記取得したノード情報で示された前ノードから前記ノード情報を取得して、該ノード情報を供給したノードが次ノードとなる判定条件を満たすか否か判定するステップを実行させるコンピュータ・プログラムにある。

なお、本発明のコンピュータ・プログラムは、例えば、様々なプログラム・コードを実行可能な汎用コンピュータ・システムに対して、コンピュータ可読な形式で提供する記憶媒体、通信媒体、例えば、光ディスクや磁気ディスク、半導体メモリなどの記憶媒体、あるいは、ネットワークなどの通信媒体によって提供可能なコンピュータ・プログラムである。このようなプログラムをコンピュータ可読な形式で提供することにより、コンピュータ・システム上でプログラムに応じた処理が実現される。

この発明によれば、アクセス不能なノードが発生したとき、ネットワーク上で常にアクセス可能とされている所定の１つのノードを起点として、前ノードの方向に順に各ノードが自己の次ノードに得るか判定されて、次ノードとなる判定条件を満たすとき、このノードが自己の新たに次ノードとされる。このため、アクセス不能なノードが発生したとき、このアクセス不能なノードを除くように、ノード情報が自動的に更新されるので、ネットワークを自動的に修復することができるようになる。

以下、図を参照しながら、この発明の実施の一形態について説明する。図１は、ネットワークシステム１０の構成を示している。ネットワークシステム１０において、複数の通信ノード（以下、単に「ノード」という）２０-1〜２０-nは、ネットワーク１１に接続されている。また、ネットワーク１１上に、オーバーレイネットワーク１２が構成されて、このオーバーレイネットワーク１２を介して複数のノード間で通信が行われる。

図２は、ノードの構成を示している。なお、図２では、ノードとしてコンピュータを用いた場合を例示している。

ノード２０のＣＰＵ(Central Processing Unit)２１は、ＲＯＭ(Read Only Memory)２２または記録部２９に記録されているコンピュータ・プログラムにしたがって各種の処理を実行する。

ＲＡＭ(Random Access Memory)２３には、ＣＰＵ２１が実行するコンピュータ・プログラムやデータ等が適宜記憶される。これらのＣＰＵ２１、ＲＯＭ２２、およびＲＡＭ２３は、バス２４により相互に接続されている。また、ＣＰＵ２１には、バス２４を介して入出力インタフェース部２５が接続されている。入出力インタフェース部２５には、ユーザインタフェース部２６、入力部２７、出力部２８、記録部２９、通信部３０、ドライブ部３１等が接続されている。

ユーザインタフェース部２６は、キーボードやポインティングデバイス、リモートコントロール信号受信部等を用いて構成されており、ユーザ操作に応じた操作信号をＣＰＵ２１に供給する。入力部２７は外部機器（図示せず）から供給された情報、例えば画像や音声等のデータの処理を行い、コンピュータで処理可能なデータに変換する。出力部２８は、外部機器に出力する情報、例えば画像や音声等のデータを外部機器に対応したデータに変換して出力する。

記録部２９は、例えばハードディスクや半導体メモリ等で構成されており、ＣＰＵ２１が実行するコンピュータ・プログラムや種々の情報例えば画像や音声等のデータを記録する。通信部３０は、ノード２０をネットワークに接続するためのものであり、通信部３０を介してネットワーク上の他のノードと通信を行う。この通信部３０を介して他のノードから取得した種々のデータやコンピュータ・プログラムは、例えばＲＡＭ２３や記録部２９に記録されて、必要に応じてＣＰＵ２１によって読み出される。なお、ＲＯＭ２２が書き換え可能であるとき、通信部３０を介して取得したコンピュータ・プログラムで、ＲＯＭ２２に記憶されているコンピュータ・プログラムを更新することも行われる。

ドライブ部３１は、装着されているリムーバブルメディア４０、例えば磁気ディスク、光ディスク、光磁気ディスク、あるいは半導体メモリなどに記録されている種々のデータやコンピュータ・プログラム等の読み出しを行うためのものである。なお、読み出されたコンピュータ・プログラムは、通信部３０で取得したコンピュータ・プログラムと同様に処理される。

ＣＰＵ２１は、コンピュータ・プログラムを実行して、入力部２７を介して供給された情報や記録部２９およびドライブ部３１に装着されているリムーバブルメディア４０から読み出した情報の処理を行う。またＣＰＵ２１は、オーバーレイネットワークを介して他のノードとの通信を制御する。

ここで、ネットワークを介して他のノードと通信を行うために用いられるルーティング情報はルーティング情報記憶部に記憶しておき、例えば次ノードや前ノード等を示すノード情報をルーティング情報として書き換え可能とされたＲＯＭ２２やＲＡＭ２３に記憶しておく。また、アクセス不能なノードが生じたとき、ルーティング情報更新部は、アクセス不能なノードを経由することなくルーティングを行うことができるようにルーティング情報を更新する。例えば、ＣＰＵ２１は、アクセス不能なノードを経由することなくルーティングを行うことができるように、書き換え可能とされたＲＯＭ２２やＲＡＭ２３に記憶されているノード情報を更新してネットワークを自己修復する。

オーバーレイネットワーク１２は、例えば分散ハッシュテーブル（ＤＨＴ：Distributed Hash Table)を利用してネットワーク１１例えばＩＰネットワーク上に構成する。次に、分散ハッシュテーブルを利用したアルゴリズムについて説明する。

上述のように、ネットワークシステム１０では、ＩＰネットワーク１１上に、分散ハッシュテーブルを利用してリング状のオーバーレイネットワーク１２が構成される。このオーバーレイネットワーク１２は、ＩＰネットワーク１１を用いた仮想的なリンクを構成するネットワークである。

オーバーレイネットワーク１２に参加する各ノードは、ノード固有の識別情報であるノードＩＤを有している。このノードＩＤは、ＩＰアドレスあるいは製造番号を共通のハッシュ関数（例えば、ＳＨＡ−１(Secure Hash Algorithm 1)等）によりハッシュ化して得た一定けた数からなるハッシュ値が用いられている。この共通のハッシュ関数により求められたノードＩＤは、ＩＰアドレスあるいは製造番号が異なれば、同じ値になる確率が極めて低いものである。したがって、オーバーレイネットワーク１２、すなわち分散ハッシュテーブルを用いたネットワーク上の各ノードは、共通のハッシュ関数を用いてＩＰアドレスあるいは製造番号をハッシュ化して、ノード固有のノードＩＤを設定することができる。

分散ハッシュ技術を用いる代表的なプロトコルであるＣｈｏｒｄは、上述のようにＩＰアドレスなどを共通のハッシュ関数によりハッシュ化して得たハッシュ値をノードＩＤとしており、このノードＩＤの順に、時計回りノードを配置することでリング状のオーバーレイネットワークであるＣｈｏｒｄリングを構成したものである。また、Ｃｈｏｒｄリング上の各ノードは、時計回りで次ノードであるサクセサ（successor）と時計回りで前ノードであるプレデセサ（predecessor）と示す情報が、ルーティング情報として記憶されており、このサクセサやプレデセサの情報を利用してルーティングが行われる。なお、Ｃｈｏｒｄでは、ルーティングの効率を向上させるために、Finger Tableと呼ばれているルーティング情報も記憶されているが、この情報はノードの接続の正確性を確保するためのものではないので説明は省略する。

このように分散ハッシュテーブルを用いて構成されたネットワークを用いて通信を行う場合、アクセス不能なノードが生じてもネットワークを修復できるものとするため、このネットワーク上で常にアクセス可能な所定の１つのノード（以下「スーパーノード」という）を予め設定する。また、ネットワークに参加するすべてのノードは、スーパーノードにアクセスできるように、スーパーノードの識別情報を記憶させておくものとする。例えばスーパーノードのＩＰアドレスを記憶しておくものとする。このように、スーパーノードのＩＰアドレスを記憶しておくものとすれば、共通のハッシュ関数を用いてＩＰアドレスをハッシュ化して、スーパーノードのノードＩＤを算出できる。

次に、アクセス不能なノードが生じたときのネットワーク修復処理について説明する。アクセス不能なノードが生じたとき、すなわちアクセス可能なサクセサがなくなったノードは、修復アルゴリズムを実行することにより新たなサクセサを検出してネットワークの修復を行う。なお、アクセス可能なサクセサがなくなり、Ｃｈｏｒｄリングが破損した状態を破損リングと呼ぶものとする。

修復アルゴリズムにおいて、アクセス可能なサクセサがなくなったノードのルーティング情報更新部は、予め指定されているノード、すなわちスーパーノードを起点としてプレデセサを示す情報の取得を行い、反時計回りでノードを辿っていき、辿った先々でそのノードが自分のサクセサになり得るかを判定する。ここで、ノードが判定条件を満たすときには、ルーティング情報記憶部に記憶されているノード情報の更新を行い、このノードを新たなサクセサとする。また、ルーティング情報更新部は、新たなサクセサに対して自分がプレデセサとなることを通知して自分とサクセサとの経路を確立させる。

図３は、アクセス可能なサクセサがなくなったノードｎで行う修復アルゴリズムを示している。ノードｎは、スーパーノードをノードｎ’として、ノードｎ’からプレデセサを示すノード情報を取得する。

ノードｎは、取得したノード情報でプレデセサがないことが示された場合（ｎ’．predecessor is nil）、または、ノードｎが、取得したノード情報によって示されたプレデセサからノードｎ’の間に位置する場合（ｎ∈(ｎ’．predecessor，ｎ’))、ノードｎ’をノードｎのサクセサとする。さらに、ノードｎは、自分がノードｎ’のプレデセサとなることをノードｎ’に通知する（ｎ’．notify(ｎ)）。

また、ノードｎは、他の場合、すなわち取得したノード情報によって示されたプレデセサからノードｎ’の間にノードｎが位置していない場合、取得したノード情報によって示されたプレデセサをノードｎ’に設定して（ｎ’＝ｎ’．predecessor）、新たに設定したノードｎ’からプレデセサのノード情報を取得して、上述の処理を行う。

プレデセサとなることの通知が供給されたノードのルーティング情報更新部は、通知を供給したノードがプレデセサとなる判定条件を満たすか否か判定して、この判定条件を満たすとき、通知を供給したノードをプレデセサに設定し、判定条件を満たさないときプレデセサを示すノード情報の更新を行わないものとする。

図４は、プレデセサとなることの通知が供給されたノードｎ’で行う修復アルゴリズムを示している。ノードｎ’は、設定されていたプレデセサがアクセス不能となりプレデセサがなくなっている場合、または、「notify」の通知で示されたノードｎがノードｎ’のプレデセサからノードｎ’の間に位置する場合、ノードｎ’は「notify」の通知で示されたノードｎをプレデセサに設定する。また、他の場合、ノードｎ’はノード情報の更新を行わないものとする。

なお、アクセス可能なサクセサがなくなったノードが複数あるときは、各ノードで上述の修復アルゴリズムを行う。

次に、修復動作について具体的に説明する。図５は、Ｃｈｏｒｄリングを示しており、ノードＮＤ１〜ノードＮＤ８でオーバーレイネットワークが構成されているものとする。また、ルーティングは時計回り方向に進むものとして、例えばノードＮＤ１のサクセサはノードＮＤ２、ノードＮＤ１のプレデセサはノードＮＤ８とする。また、オーバーレイネットワークで常にオンラインでアクセス可能なノードであるスーパーノードをノードＮＤ１として以下の説明を行う。

このように構成されたＣｈｏｒｄリングにおいて、ノードＮＤ４がアクセス不能となると、修復前のＣｈｏｒｄリングは図６に示すものとなり、ノードＮＤ３は、サクセサであるノードＮＤ４に対してアクセスできないことから、図３に示す修復アルゴリズムを実行する。なお、図６および後述する図１０において、一点鎖線は、アクセス不能となった経路を示している。

ノードＮＤ３は、図７に示すように、スーパーノードＮＤ１からプレデセサのノード情報を取得する。ここで、スーパーノードＮＤ１から取得したノード情報は、プレデセサとしてノードＮＤ８を示している。ノードＮＤ３は、スーパーノードＮＤ１から取得したノード情報に基づき、スーパーノードＮＤ１がサクセサになり得るか否かの判定を行う。スーパーノードＮＤ１から取得したノード情報は、プレデセサとしてノードＮＤ８を示しており、ノードＮＤ３は、取得したノード情報で示されたプレデセサであるノードＮＤ８からノードＮＤ１の間に位置していない。したがって、ノードＮＤ３は、ノードＮＤ１がサクセサになり得ないと判定して、ノード情報の要求先である図３のノードｎ’をノードＮＤ８として、次のノードＮＤ８がサクセサになり得るか否かの判定を行う。

ノードＮＤ３は、ノードＮＤ８からプレデセサを示すノード情報を取得する。ここで、ノードＮＤ８から取得したノード情報は、プレデセサとしてノードＮＤ７を示している。ノードＮＤ３は、ノードＮＤ８から取得したノード情報に基づき、ノードＮＤ８がサクセサになり得るか否かの判定を行う。ノードＮＤ８から取得したノード情報は、プレデセサとしてノードＮＤ７を示しており、ノードＮＤ３は、取得したノード情報で示されたプレデセサであるノードＮＤ７からノードＮＤ８の間に位置していない。したがって、ノードＮＤ３は、ノードＮＤ８がサクセサになり得ないと判定して、ノード情報の要求先である図３のノードｎ’をノードＮＤ７として、次のノードＮＤ７がサクセサになり得るか否かの判定を行う。

以下、同様の処理を繰り返すことにより反時計回りでノードをたどり、辿った先々でそのノードが自分のサクセサになり得るかを判定する。

その後、図８に示すように、ノードＮＤ３は、ノードＮＤ５からプレデセサを示すノード情報を取得する。ここで、ノードＮＤ５のプレデセサであったノードＮＤ４はアクセス不能となっているので、ノードＮＤ５から取得したノード情報は、プレデセサが存在していないことを示す「ｎｉｌ」となる。

ノードＮＤ３は、ノード情報が「ｎｉｌ」であることから、ノードＮＤ５がサクセサになると判定して、ノードＮＤ５をノードＮＤ３のサクセサに設定する（ＮＤ３．successor＝ＮＤ５）。このように、ノードＮＤ３でルーティン情報を更新してノードＮＤ５をサクセサに設定すれば、時計回り方向に正しくルーティングを行うことができる。

ところで、ノードＮＤ５は、ノードＮＤ３によってサクセサに設定されているが、ノードＮＤ５のプレデセサはノードＮＤ３に変更されていないことから、ノードＮＤ５のルーティング情報は、ノードの接続を正しく示していないものとなる。そこで、ノードＮＤ３は、自分がノードＮＤ５のプレデセサとなるために、ノードＮＤ５に対してノードＮＤ３の存在を通知する(ＮＤ５．notify(ＮＤ３))。

ノードＮＤ３から「notify」の通知を受けたノードＮＤ５は、ノードＮＤ３がプレデセサとなる条件を満たすか否か判別する。ここで、ノードＮＤ５は、ノードＮＤ４がアクセス不能となっておりプレデセサが存在していないことから、図４の修復アルゴリズムにより、ノードＮＤ３をノードＮＤ５のプレデセサに設定する（ＮＤ５．predecessor＝ＮＤ３）。

このような処理を行うものとすると、ノードＮＤ４がアクセス不能となったとき、ノードＮＤ３のサクセサはノードＮＤ５、ノードＮＤ５のプレデセサはノードＮＤ３に自動的に変更されて、図９に示すようにＣｈｏｒｄリングを自動的に修復することができる。

次に、アクセス不能なノードが複数生じた場合、例えば図１０に示すように３つのノードＮＤ３，ＮＤ５，ＮＤ８がアクセス不能となった場合についての修復動作について説明する。

例えばノードＮＤ２は、サクセサであるノードＮＤ３がアクセス不能となったことから、修復アルゴリズムを実行して、図１１に示すように、スーパーノードＮＤ１からプレデセサのノード情報を取得する。ここで、スーパーノードＮＤ１のプレデセサであるノードＮＤ８はアクセス不能となっていることから、取得したノード情報は、プレデセサが存在していないことを示す「ｎｉｌ」となる。

ノードＮＤ２は、取得したノード情報で示されたプレデセサが「ｎｉｌ」であることから、スーパーノードＮＤ１がサクセサになると判定して、ノードＮＤ１をノードＮＤ２のサクセサに設定する。また、ノードＮＤ２は、自分がスーパーノードＮＤ１のプレデセサとなるために、スーパーノードＮＤ１に対してノードＮＤ２の存在を通知する(ＮＤ１．notify(ＮＤ２))。

ノードＮＤ２から「notify」の通知を受けたスーパーノードＮＤ１は、ノードＮＤ２がプレデセサとなる条件を満たすか否か判別する。ここで、スーパーノードＮＤ１は、ノードＮＤ８がアクセス不能となっておりプレデセサが存在していないことから、図４の修復アルゴリズムにより、ノードＮＤ２をスーパーノードＮＤ１のプレデセサに設定する（ＮＤ１．predecessor＝ＮＤ２）。

このような処理を行うものとすると、図１２に示すように、暫定的にスーパーノードＮＤ１とノードＮＤ２からなるＣｈｏｒｄリングが構成される。

Ｃｈｏｒｄでは、各ノードがサクセサ等を含むルーティング情報を更新するために、定期的にStabilizeが行われる。

図１３は、Stabilizeのアルゴリズムを示している。ノードｎがStabilizeを行う場合、ノードｎは、サクセサに対してプレデセサを示すノード情報の要求を行い、取得したノード情報で示されたノードをノードｘとする。さらに、ノードｎは、ノードｘが自分の新しいサクセサになり得るかどうかを判定する。ノードｎは、ノードｘがノードｎからノードｎのサクセサの間に位置するとき、ノードｘをサクセサに設定する。また、ノードｎは、ノードｘがノードｎからノードｎのサクセサの間に位置していないとき、サクセサの変更を行わないものとする。

図１２に示すようにノードＮＤ２における修復が完了したのち、例えばノードＮＤ４のサクセサであるノードＮＤ５がアクセス不能となっているため、ノードＮＤ４で修復アルゴリズムを実行すると、ノードＮＤ４は、スーパーノードＮＤ１からプレデセサのノード情報を取得する。ここで、スーパーノードＮＤ１のプレデセサは、ノードＮＤ２で修復アルゴリズムを実行したことによりノードＮＤ２となっている。ノードＮＤ４は、スーパーノードＮＤ１から取得したノード情報に基づき、スーパーノードＮＤ１がサクセサになり得るか否かの判定を行う。スーパーノードＮＤ１から取得したノード情報は、プレデセサとしてノードＮＤ２を示しており、ノードＮＤ４は、取得したノード情報で示されたプレデセサであるノードＮＤ２からスーパーノードＮＤ１の間に位置している。したがって、ノードＮＤ４は、スーパーノードＮＤ１をサクセサに設定する（ＮＤ４．successor＝ＮＤ１）。また、ノードＮＤ４は、自分がスーパーノードＮＤ１のプレデセサとなるために、スーパーノードＮＤ１に対してノードＮＤ４の存在を通知する(ＮＤ１．notify(ＮＤ４))。

ノードＮＤ４から「notify」の通知を受けたスーパーノードＮＤ１は、ノードＮＤ４がプレデセサとなる条件を満たすか否か判別する。スーパーノードＮＤ１は、ノードＮＤ４がノードＮＤ１のプレデセサであるノードＮＤ２からノードＮＤ１の間に位置していることから、ノードＮＤ４をノードＮＤ１のプレデセサに設定する（ＮＤ１．predecessor＝ＮＤ４）。

このような処理を行うものとすると、図１４に示すように、ノードＮＤ１とノードＮＤ４を結ぶ経路が形成される。また、この状態でノードＮＤ２がStabilizeを行うと、ノードＮＤ２は、サクセサであるスーパーノードＮＤ１からプレデセサを示すノード情報を取得して、この取得したノード情報で示されたノードが、ノードＮＤ２の新しいサクセサになり得るかどうかを判定する。なお、スーパーノードＮＤ１のプレデセサは、ノードＮＤ４で修復アルゴリズムが実行されたことによりノードＮＤ４に設定されている。このため、スーパーノードＮＤ１から取得したプレデセサを示すノード情報は、ノードＮＤ４を示すものとなる。

ノードＮＤ２は、スーパーノードＮＤ１のプレデセサが自分の新しいサクセサになり得るかどうかを判定する。ここで、スーパーノードＮＤ１のプレデセサはノードＮＤ４であり、ノードＮＤ４は、ノードＮＤ２からノードＮＤ２のサクセサであるスーパーノードＮＤ１の間に位置する。したがってノードＮＤ２は、ノードＮＤ４をサクセサに設定する（ＮＤ２．successor＝ＮＤ４）。また、ノードＮＤ２は、自分がノードＮＤ４のプレデセサとなるために、ノードＮＤ４に対してノードＮＤ２の存在を通知する(ＮＤ４．notify(ＮＤ２))。

ノードＮＤ２から「notify」の通知を受けたノードＮＤ４は、ノードＮＤ２がプレデセサとなる条件を満たすか否か判別する。ここで、ノードＮＤ４はノードＮＤ３がアクセス不能となっており、プレデセサが存在していないことから、図４の修復アルゴリズムにより、ノードＮＤ２をノードＮＤ４のプレデセサに設定する（ＮＤ４．predecessor＝ＮＤ２）。

このような処理を行うものとすると、図１５に示すように、スーパーノードＮＤ１とノードＮＤ２およびノードＮＤ４からなるＣｈｏｒｄリングが構成されることとなる。

ノードＮＤ２およびノードＮＤ４における修復が完了して、例えばノードＮＤ７で修復アルゴリズムが実行されると、ノードＮＤ７は、スーパーノードＮＤ１からプレデセサのノード情報を取得する。ここで、スーパーノードＮＤ１のプレデセサは、ノードＮＤ２およびノードＮＤ４で修復アルゴリズムを実行したことによりノードＮＤ４となっている。ノードＮＤ７は、スーパーノードＮＤ１から取得したノード情報に基づき、スーパーノードＮＤ１がサクセサになり得るか否かの判定を行う。スーパーノードＮＤ１から取得したノード情報は、プレデセサとしてノードＮＤ４を示しており、ノードＮＤ７は、取得したノード情報で示されたプレデセサであるノードＮＤ４からスーパーノードＮＤ１の間に位置している。したがって、ノードＮＤ７は、スーパーノードＮＤ１をサクセサに設定する（ＮＤ７．successor＝ＮＤ１）。また、ノードＮＤ７は、自分がスーパーノードＮＤ１のプレデセサとなるために、スーパーノードＮＤ１に対してノードＮＤ７の存在を通知する(ＮＤ１．notify(ＮＤ７))。

ノードＮＤ７から「notify」の通知を受けたスーパーノードＮＤ１は、ノードＮＤ７がプレデセサとなる条件を満たすか否か判別する。スーパーノードＮＤ１は、ノードＮＤ７がノードＮＤ１のプレデセサであるノードＮＤ４からノードＮＤ１の間に位置していることから、ノードＮＤ７をノードＮＤ１のプレデセサに設定する（ＮＤ１．predecessor＝ＮＤ７）。

このような処理を行うものとすると、図１６に示すように、ノードＮＤ１とノードＮＤ７を結ぶ経路が形成される。また、この状態でノードＮＤ４がStabilizeを行うと、ノードＮＤ４は、サクセサであるスーパーノードＮＤ１からプレデセサを示すノード情報を取得して、この取得したノード情報で示されたノードが、ノードＮＤ４の新しいサクセサになり得るかどうかを判定する。なお、スーパーノードＮＤ１のプレデセサは、ノードＮＤ７で修復アルゴリズムが実行されたことによりノードＮＤ７に設定されている。このため、スーパーノードＮＤ１から取得したプレデセサを示すノード情報は、ノードＮＤ７を示すものとなる。

ノードＮＤ４は、スーパーノードＮＤ１のプレデセサが自分の新しいサクセサになり得るかどうかを判定する。ここで、スーパーノードＮＤ１のプレデセサはノードＮＤ７であり、ノードＮＤ７は、ノードＮＤ４からノードＮＤ４のサクセサであるスーパーノードＮＤ１の間に位置する。したがってノードＮＤ４は、ノードＮＤ７をサクセサに設定する（ＮＤ４．successor＝ＮＤ７）。また、ノードＮＤ４は、自分がノードＮＤ７のプレデセサとなるために、ノードＮＤ７に対してノードＮＤ４の存在を通知する(ＮＤ７．notify(ＮＤ４))。

ノードＮＤ４から「notify」の通知を受けたノードＮＤ７は、ノードＮＤ４がプレデセサとなる条件を満たすか否か判別する。ここで、ノードＮＤ７のプレデセサはノードＮＤ６であり、ノードＮＤ４は、ノードＮＤ６からノードＮＤ７の間に位置していない。すなわち、ノードＮＤ７は、ノードＮＤ４がプレデセサとなる条件を満たしていないと判定して、プレデセサをノードＮＤ６からノードＮＤ４に変更しないものとする。

なお、ノードＮＤ１とノードＮＤ７を結ぶ経路が形成されたのち、他のノード例えばノードＮＤ６でStabilizeが行われても、Ｃｈｏｒｄリングのトポロジーへの影響はない。すなわち、ノードＮＤ６のサクセサであるノードＮＤ７に対して「Predecessor」を示すノード情報を要求したとき、ノード情報ではノードＮＤ６が示されることから、ノードＮＤ６のサクセサの変更が行われることがなく、トポロジーへの影響はない。

ノードＮＤ１とノードＮＤ７を結ぶ経路が形成された状態で、ノードＮＤ４が再度Stabilizeを行うと、図１７に示すように、ノードＮＤ４は、サクセサであるノードＮＤ７からプレデセサを示すノード情報を取得して、この取得したノード情報で示されたノードが、ノードＮＤ４の新しいサクセサになり得るかどうかを判定する。なお、ノードＮＤ７のプレデセサは、上述のようにノードＮＤ６に設定されている。このため、ノードＮＤ７から取得したプレデセサを示すノード情報は、ノードＮＤ６を示すものとなる。

ノードＮＤ４は、ノードＮＤ７のプレデセサが自分の新しいサクセサになり得るかどうかを判定する。ここで、ノードＮＤ７のプレデセサはノードＮＤ６であり、ノードＮＤ６は、ノードＮＤ４からノードＮＤ４のサクセサであるノードＮＤ７の間に位置する。したがってノードＮＤ４は、ノードＮＤ６をサクセサに設定する（ＮＤ４．successor＝ＮＤ６）。また、ノードＮＤ４は、自分がノードＮＤ６のプレデセサとなるために、ノードＮＤ６に対してノードＮＤ４の存在を通知する(ＮＤ６．notify(ＮＤ４))。

ノードＮＤ２から「notify」の通知を受けたノードＮＤ６は、ノードＮＤ４がプレデセサとなる条件を満たすか否か判別する。ここで、ノードＮＤ６はノードＮＤ５がアクセス不能となっており、プレデセサが存在していないことから、図４の修復アルゴリズムにより、ノードＮＤ４をノードＮＤ６のプレデセサに設定する（ＮＤ６．predecessor＝ＮＤ４）。

このような処理を行うものとすると、図１８に示すように、アクセス不能なノードＮＤ３，ＮＤ５，ＮＤ８が除かれて、スーパーノードＮＤ１とノードＮＤ２，ＮＤ４，ＮＤ６，ＮＤ７からなるＣｈｏｒｄリングを構成することができる。

以上のように、障害を検出したノードで修復アルゴリズムを実行するものとし、また、ノードでStabilizeを行うものとすると、障害の発生したノードを除いてＣｈｏｒｄリングを構成することができる。

なお、上述の説明では、ノードＮＤ２で修復アルゴリズムを行ったのち、ノードＮＤ４で修復アルゴリズムを行い、その後、ノードＮＤ７で修復アルゴリズムを行うものとした。しかし、修復アルゴリズムを行うノードの順序は、上述の場合に限られるものではなく、任意の順番で行うものとしても、障害の発生したノードを除いてＣｈｏｒｄリングを構成することができる。

図１９は、上述の修復動作を行うときのノードの動作を示すフローチャートである。ステップＳＴ１でＣＰＵ２１は、障害が発生したか否かを判別する。ＣＰＵ２１は、サクセサがアクセス不能となったことを判別したときステップＳＴ２に進み、サクセサがアクセス不能となっていないことを判別したときステップＳＴ１１に進む。

ステップＳＴ２でＣＰＵ２１は、ノード情報の要求先をスーパーノードＮＤ１に設定してステップＳＴ３に進む。

ステップＳＴ３でＣＰＵ２１は、ノード情報を取得する。ＣＰＵ２１は、ノード情報の要求先からプレデセサを示すノード情報を取得してステップＳＴ４に進む。

ステップＳＴ４でＣＰＵ２１は、取得したノード情報で示されたノードが、サクセサの判定条件を満たすか否か判別する。ＣＰＵ２１は、ノード情報で示されたノードが判定条件を満たすとき、すなわち、取得したノード情報が「ｎｉｌ」であるとき、またはノード情報で示されたノードからこのノード情報の供給元であるノードの間に自己のノードが位置するとき、ノード情報で示されたノードが判定条件を満たすものとしてステップＳＴ６に進む。また、ＣＰＵ２１は、ノード情報で示されたノードが判定条件を満たしていないときステップＳＴ５に進む。

ステップＳＴ５でＣＰＵ２１は、ノード情報の要求先をノード情報が示すプレデセサに設定する。ＣＰＵ２１は、ステップＳＴ３で取得したノード情報で示されているプレデセサをノード情報の要求先に設定してステップＳＴ３に戻る。このように、ステップＳＴ２乃至ステップＳＴ５の処理を行うものとすれば、スーパーノードを起点として、反時計回りでノードをたどっていきながら、たどった先々でノードが自己のサクセサになり得るか判別できる。

ステップＳＴ６でＣＰＵ２１は、ノード情報の供給元をサクセサに設定してステップＳＴ７に進む。

ステップＳＴ７でＣＰＵ２１は、サクセサに自己を通知する。ＣＰＵ２１は、新たに設定したサクセサに対して、自己のノードがプレデセサになることの通知「notify」を行ってステップＳＴ１に戻る。

ステップＳＴ１からステップＳＴ１１に進むと、ステップＳＴ１１でＣＰＵ２１は、Stabilizeを行うか否かを判別する。Ｃｈｏｒｄでは、上述のようにStabilizeを定期的に行う。したがって、ＣＰＵ２１は、Stabilizeを行うタイミングであるか否かを判別して、Stabilizeを行うタイミングであると判別したときステップＳＴ１２に進み、Stabilizeを行うタイミングでないと判別したときステップＳＴ１３に進む。

ステップＳＴ１２でＣＰＵ２１は、Stabilizeを行ってステップＳＴ１３に進む。

ステップＳＴ１３でＣＰＵ２１は、他のノードからノード情報の要求が行われたか否かを判別する。ＣＰＵ２１は、ノード情報の要求が行われたときステップＳＴ１４に進み、ノード情報の要求が行われていないときステップＳＴ１５に進む。

ステップＳＴ１４でＣＰＵ２１は、ノード情報の要求を行ったノードに対して、プレデセサを示すノード情報を供給してステップＳＴ１５に進む。

ステップＳＴ１５でＣＰＵ２１は、「notify」の通知を受けたか否か判別する。ＣＰＵ２１は、「notify」の通知を受けたときステップＳＴ１５に進み、「notify」の通知を受けていないときステップＳＴ１に戻る。

ステップＳＴ１６でＣＰＵ２１は、受信した「notify」の通知の供給元であるノードが、プレデセサの判定条件を満たすか否か判別する。ＣＰＵ２１は、「notify」の通知の供給元であるノードが判定条件を満たすとき、すなわち、設定されていたプレデセサがアクセス不能となって、プレデセサが設定されていない状態となっているとき、またはプレデセサが示すノードから自己のノードの間に、「notify」の通知の供給元であるノードが位置するとき、「notify」の通知の供給元であるノードが判定条件を満たすものとしてステップＳＴ１７に進む。また、ＣＰＵ２１は、「notify」の通知の供給元であるノードが判定条件を満たしていないときステップＳＴ１に戻る。

ステップＳＴ１７でＣＰＵ２１は、プレデセサの更新を行う。ＣＰＵ２１は、「notify」の通知の供給元であるノードを、新たなプレデセサに設定してステップＳＴ１に戻る。

なお、Stabilizeに関する処理と、ノード情報の要求に対応する処理、および「notify」の通知に関する処理の順序は、図１９の順序に限られるものではなく、いすれの処理を優先させてもよい。

以上のように、各ノードで上述のような修復アルゴリズムを行うものとすれば、アクセス不能なノードが生じても、アクセス不能なノードを除いて、Ｃｈｏｒｄリングを自己修復することができる。また、上述の修復アルゴリズムは、Ｃｈｏｒｄプロトコルが提供している機能（ＡＰＩ）のみを利用したものである。すなわち、新たな機能を追加する必要がないので、簡単に修復アルゴリズムを実現することが可能である。

なお、上述の実施の形態におけるノードの数やアクセス不能なノードの位置は例示的なものであり、限定的に解釈されるべきではない。本発明の要旨を逸脱しない範囲で当業者が実施の形態の修正や代用をなし得ることは自明であり、本発明の要旨を判断するためには、特許請求の範囲の欄を参酌すべきである。

この発明の通信ノードと通信方法およびコンピュータ・プログラムでは、アクセス不能なノードが発生したとき、このアクセス不能なノードを除くように次ノードや前ノードを示すノード情報が更新されて、ネットワークを自動的に修復できる。したがって、Ｐ２Ｐネットワーク等に好適である。

ネットワークシステムの構成を示す図である。 ノードの構成を示す図である。 アクセス可能なサクセサがなくなったノードで行う修復アルゴリズを示す図である。 プレデセサとなることの通知が供給されたノードで行う修復アルゴリズムを示す図である。 Ｃｈｏｒｄリングを示す図である。 修復前のＣｈｏｒｄリングを示す図である。 修復途中のＣｈｏｒｄリングを示す図である。 修復途中のＣｈｏｒｄリングを示す図である。 修復後のＣｈｏｒｄリングを示す図である。 修復前のＣｈｏｒｄリングを示す図である。 修復途中のＣｈｏｒｄリングを示す図である。 修復途中のＣｈｏｒｄリングを示す図である。 Stabilizeのアルゴリズムを示す図である。 修復途中のＣｈｏｒｄリングを示す図である。 修復途中のＣｈｏｒｄリングを示す図である。 修復途中のＣｈｏｒｄリングを示す図である。 修復途中のＣｈｏｒｄリングを示す図である。 修復後のＣｈｏｒｄリングを示す図である。 ノードの動作を示すフローチャートである。

符号の説明

１０・・・ネットワークシステム、１１・・・ＩＰネットワーク、１２・・・オーバーレイネットワーク、２０・・・ノード、２１・・・ＣＰＵ、２２・・・ＲＯＭ、２３・・・ＲＡＭ、２４・・・バス、２５・・・入出力インタフェース部、２６・・・ユーザインタフェース部、２７・・・入力部、２８・・・出力部、２９・・・記録部、３０・・・通信部、３１・・・ドライブ部、４０・・・リムーバブルメディア

Claims (8)

1. 分散ハッシュテーブルを用いたリング状のネットワークにおける次ノードと前ノードを示すノード情報をルーティング情報として記憶するルーティング情報記憶部と、
   前記ルーティング情報記憶部に記憶されているノード情報の更新を行うルーティング情報更新部を備え、
   前記ルーティング情報更新部は、次ノードがアクセス不能となったとき、前記ネットワーク上で常にアクセス可能とされている所定の１つのノードから前ノードを示すノード情報の取得を行い、該取得したノード情報に基づき該ノード情報を供給したノードが次ノードとなる判定条件を満たすか否か判定して、前記次ノードとなる判定条件を満たすとき、該ノード情報を供給したノードを前記次ノードに設定し、前記次ノードとなる判定条件を満たさないとき、前記取得したノード情報で示された前ノードから前記ノード情報を取得して、該ノード情報を供給したノードが次ノードとなる判定条件を満たすか否か判定する通信ノード。
2. 前記ルーティング情報更新部は、自己が前記ノード情報で示された前ノードから前記前ノードを示すノード情報を供給元したノードまでの間に位置するとき、または前記ノード情報で前ノードが示されていないときに、前記次ノードとなる判定条件を満たすものとする
   請求項１記載の通信ノード。
3. 前記ルーティング情報更新部は、前記ノード情報を供給したノードを前記次ノードに設定したとき、自己が前記ノード情報を供給したノードの前ノードとなる通知を、前記ノード情報を供給したノードに対して行う
   請求項２記載の通信ノード。
4. 前記ルーティング情報更新部は、前ノードとなる通知が供給されたとき、該通知を供給したノードが前ノードとなる判定条件を満たすか否か判定して、前記前ノードとなる判定条件を満たすとき、該通知を供給したノードを前記前ノードに設定し、前記前ノードとなる判定条件を満たさないとき、前記前ノードを示すノード情報の更新を行わないものとする
   請求項３記載の通信ノード。
5. 前記ルーティング情報更新部は、自己の前ノードがアクセス不能であるとき、または前記前ノードとなる通知を供給したノードが、自己の前ノードから自己までの間に位置するときに、前記前ノードとなる判定条件を満たすものとする
   請求項４記載の通信ノード。
6. 前記ルーティング情報更新部は、定期的に前記ルーティング情報記憶部に記憶されているノード情報の更新を行う
   請求項１記載の通信ノード。
7. 分散ハッシュテーブルを用いたリング状のネットワークにおける次ノードがアクセス不能となったとき、ルーティング情報更新部によって、前記ネットワーク上で常にアクセス可能とされている所定の１つのノードから前ノードを示すノード情報を取得するステップと、
   前記ルーティング情報更新部によって、取得した前記ノード情報に基づき該ノード情報を供給したノードが次ノードとなる判定条件を満たすか否か判定して、前記次ノードとなる判定条件を満たすとき、該ノード情報を供給したノードを前記次ノードに設定し、前記次ノードとなる判定条件を満たさないとき、前記取得したノード情報で示された前ノードから前記ノード情報を取得して、該ノード情報を供給したノードが次ノードとなる判定条件を満たすか否か判定するステップを有する通信方法。
8. 分散ハッシュテーブルを用いたリング状のネットワークに接続されているコンピュータに、
   前記ネットワーク上の次ノードがアクセス不能となったとき、前記ネットワーク上で常にアクセス可能とされている所定の１つのノードから前ノードを示すノード情報を取得するステップと、
   取得した前記ノード情報に基づき該ノード情報を供給したノードが次ノードとなる判定条件を満たすか否か判定して、前記次ノードとなる判定条件を満たすとき、該ノード情報を供給したノードを前記次ノードに設定し、前記次ノードとなる判定条件を満たさないとき、前記取得したノード情報で示された前ノードから前記ノード情報を取得して、該ノード情報を供給したノードが次ノードとなる判定条件を満たすか否か判定するステップを実行させるコンピュータ・プログラム。

Images