ノードの接続方法及びネットワークトポロジ構築方法及びネットワークシステム
【課題】複数のノードがネットワークで接続された分散システムにおいて接続関係の一貫性を保ちつつ非同期にノードの挿入、削除が行えるノードの接続方法を提供する。
【解決手段】第１のノードと、第１のノードの接続先である第２のノードの間に、第３のノードを挿入しようとする場合、まず第３のノードが、第１のノードが保持する、ノードの接続先が変更された際に更新される検出情報を入手し、第１のノードに、前記検出情報と、第３のノードに接続するための接続先情報とを含むリンク更新メッセージを送信する。そして、第１のノードが、リンク更新メッセージ受信時の第１のノードが保持する検出情報と、前記リンク更新メッセージに含まれる検出情報が一致するか否かを判定し、一致すると判定した場合に、前記接続先情報に基づいて第１のノードが第３のノードに接続するとともに、第１のノードが保持する検出情報を異なる検出情報に更新する。
【解決手段】第１のノードと、第１のノードの接続先である第２のノードの間に、第３のノードを挿入しようとする場合、まず第３のノードが、第１のノードが保持する、ノードの接続先が変更された際に更新される検出情報を入手し、第１のノードに、前記検出情報と、第３のノードに接続するための接続先情報とを含むリンク更新メッセージを送信する。そして、第１のノードが、リンク更新メッセージ受信時の第１のノードが保持する検出情報と、前記リンク更新メッセージに含まれる検出情報が一致するか否かを判定し、一致すると判定した場合に、前記接続先情報に基づいて第１のノードが第３のノードに接続するとともに、第１のノードが保持する検出情報を異なる検出情報に更新する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワーク内のノードを接続する際に用いられるノードの接続方法、およびその接続方法を用いたネットワークトポロジ構築方法に関する。
【背景技術】
【０００２】
ネットワーク上でサービスを提供するシステムの形態として、ピアツーピア（以下Ｐ２Ｐと表記する）システムが注目されている。Ｐ２Ｐシステムは各ノードが自律的に他のノードと協調動作することで、ノード数に応じて性能を向上させることができるシステムである。Ｐ２Ｐシステムは大きく分けてノードの接続関係（トポロジ）に制約のない非構造型Ｐ２Ｐシステムと、トポロジに一定の制約がある構造型Ｐ２Ｐシステムに分類できる。構造型Ｐ２Ｐシステムでは、トポロジを維持するコストがかかるが、ノード数やデータ数の対数オーダのコストでデータを検索できるという特徴を持つ。
【０００３】
構造化Ｐ２Ｐシステムでよく用いられるトポロジの一つに双方向リングトポロジがある。双方向リングトポロジでは、各ノードはキー値（ノードの識別子などがよく用いられる）、右方向リンク、左方向リンクを持つ。右方向リンクは自分のキー値よりも次に大きいキー値を持つノード（存在しない場合は最も小さいキーを持つノード）に接続し、左方向リンクは自分のキー値よりも次に小さいキー値を持つノード（存在しない場合は最も大きいキーを持つノード）に接続する。
【０００４】
双方向リングは、右方向リンクを用いた右方向リングと、左方向リンクを用いた左方向リングの２つの片方向リングに分解できる。
【０００５】
Ｐ２Ｐシステムでは、システム稼働中にノードが挿入（追加）・削除される場合がある。双方向リングトポロジを構成するアルゴリズムでは、ノードの挿入・削除が予測できないタイミングで発生することを想定する必要がある。またノードが故障した場合は、故障したノードをバイパスしてリングを修復することも必要である。
【０００６】
双方向リングトポロジを構成する手法を開示している文献としては、たとえば下記非特許文献１、２がある。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】IonStoica, et al. Chord: A scalable peer-to-peer lookup protocol for internetapplications. IEEE/ACM Transactions on Networking, Vol. １１, No.１, pp. １７-３２, ２００３.
【非特許文献２】NancyLynch, Dahlia Malkhi, and David Ratajczak. Atomic Data Access in ContentAddressable Networks. In Proceedings of the １st International Workshop on Peer-to-PeerSystems, pp. 295-305, ２００２.
【発明の開示】
【発明が解決しようとする課題】
【０００８】
上記非特許文献１に記載された手法では、ノードの挿入・削除時に、双方向リングは一時的に一貫性がない状態（各ノードがキーの値が最も近いノードと接続していない状態）になる。例えばノード１の右方向リンクがノード２を指している時に、ノード１とノード２の間にノード３とノード４が並行して挿入された場合、ノード３、ノード４のいずれも右方向リンクがノード２を指した状態（一貫性が崩れた状態）になる。この状態は定期的に実行する修復手続きによっていずれ解消されるが、このような状態が存在することは双方向リングを用いたアプリケーションプログラムにとって好ましいことではない。
【０００９】
また、上記非特許文献２では、ノードの挿入・削除時に隣接するノードが排他制御することでリングの一貫性を確保する手法が記述されている。しかし、この手法は排他制御しているノードが故障した場合にリングを確実に修復することが困難であるという問題がある。この理由は、ノードが故障した時の排他制御状態を他のノードが確実に知ることができないためである。
【００１０】
本発明は上記のような技術課題を解決するためになされたものであり、ノードが並行して挿入・削除された場合でも片方向リングの一貫性を保持できるノードの接続方法を提供することを目的とする。
【００１１】
また、ノードを片方向リングに挿入（あるいは片方向リングから削除）した後で、反対方向リングに効率よく挿入する（あるいは反対方向リングから削除する）方法を提供することも目的とする。
【００１２】
さらに、ノード故障やネットワーク故障が発生した場合でも安定して確実に双方向リングを修復できるノードの連結方法を提供することも目的とする。
【課題を解決するための手段】
【００１３】
本発明は、第１のノードと、第１のノードの接続先である第２のノードの間に、第３のノードを挿入しようとする場合のノードの接続方法であって、各ノードは接続先が変更された際に更新される検出情報を有している。まず入手ステップにおいて、第３のノードが第１のノードが保持する検出情報を入手する。そして、送信ステップにおいて、第３のノードが第１のノードに、前記検出情報と、第３のノードに接続するための接続先情報とを含むリンク更新メッセージを送信する。
【００１４】
次に、判定ステップにおいて、前記第１のノードが、前記リンク更新メッセージ受信時の第１のノードが保持する検出情報と、前記第１のリンク更新メッセージに含まれる検出情報が一致するか否かを判定し、一致すると判定された場合に、前記接続先情報に基づいて第１のノードが第３のノードに接続するとともに、第１のノードが保持する検出情報を異なる検出情報に更新する。
【００１５】
また、第２のノードから第１のノードへも接続している場合に、第１のノードに付与された隣接ノードのリンクバージョン情報を用いて以下のステップを有してもよい。
【００１６】
すなわち、前記第３のノードが、前記判定ステップにおいて一致していると判定された場合に、第１のノードに付与されている隣接ノードのリンクバージョン情報を更新した更新リンクバージョン情報と、第３のノードに接続するための接続先情報とを含むリンク更新メッセージを第２のノードに送信する送信ステップとを備える。
【００１７】
そして、前記リンク更新メッセージを受信した第２のノードが、第２のノードが保持する自ノードのリンクバージョン情報よりも前記リンク更新メッセージに含まれる更新リンクバージョン情報が優先するか否かを判定する判定ステップと、前記リンク更新メッセージに含まれる更新リンクバージョン情報が優先すると判定した場合に、前記接続先情報に基づいて第２のノードから第３のノードへ接続するとともに、第２のノードが保持する自ノードのリンクバージョン情報を前記リンク更新メッセージに含まれる更新リンクバージョン情報に変更する第２のリンク更新ステップを有しても良い。
【００１８】
さらに本発明は、第４のノードが第５のノードに接続し、第５のノードが第６のノードに接続している場合に、第５のノードを削除しようとする場合、各ノードが保持する他のノードから接続されている数を示す参照カウンタを用いて以下のステップを有しても良い。
【００１９】
すなわち、第６のノードがリンク更新メッセージを受信した場合に、第６のノードが前記第５のノードに参照カウンタを減少させる参照カウンタ減少メッセージを送信する参照カウンタ減少メッセージ送信ステップと、第５のノードが前記参照カウンタ減少メッセージを受信した場合に参照カウンタを減少させる参照カウンタ減少ステップと、参照カウンタの値が基準値を下回ったときに第５のノードを削除する削除実行ステップを備える。
【００２０】
さらに本発明は、上述のノードの接続方法を用いて、片方向リングトポロジあるいは双方向リングトポロジあるいは片方向連結リストトポロジあるいは双方向連結リストトポロジを構築することができる。
【００２１】
さらに本発明は、上述のノードの接続方法を用いて構築するネットワークシステムであってもよい。
【発明の効果】
【００２２】
本発明によれば、片方向リングトポロジなどにおいて、リングの一貫性を維持したままノードを挿入、あるいは削除できる。また、片方向リングに反対方向のリングを加えて双方向リングに拡張した場合、反対方向リングへのノードの挿入、削除は非常に効率的に実行できる。さらに、ノード故障やネットワーク故障時にリングを安定して修復できる。
【図面の簡単な説明】
【００２３】
【図１】ノードを挿入する場合の基本的な流れを示す図
【図２】ノードを削除する場合の基本的な流れを示す図
【図３】複数のノードを並行して挿入する場合のノードの状態を示す図
【図４】ノードの挿入と削除が並行して起こった場合のノードの状態を示す図
【発明を実施するための最良の形態】
【００２４】
（第１の実施形態）
本発明の実施形態に係るノードの接続方法について説明する。本実施形態のノードの接続方法は双方向リングについて適用しているが、これに限定されるものではない。例えば、片方向リング、片方向連結リスト、双方向連結リスト等、種々のネットワークトポロジの構築に用いることができる。
【００２５】
本実施形態では、本発明を双方向リングの構成のために用いる。各ノードは、右方向、左方向の２つのリンク（接続先）を持ち、他のノード、あるいは自分自身に接続する。双方向リングは各ノードの右方向リンクをたどることで得られる右方向リングと、左方向リンクをたどることで得られる左方向リングの２つの片方向リングに分解できる。本実施形態では、リングの要素である各ノードは，それぞれのノードが保持するキー値によってソートされている。ここでは右方向がキー値の増加する方向とし、左方向がキー値の減少する方向とする。ただし、最大値を持つノードの右ノードは最小値を持つノードであり、また最小値を持つノードの左ノードは最大値を持つノードである。
【００２６】
双方向リングにノードを挿入する場合の基本的な流れについて説明する。図１は、ノードを挿入する場合の基本的な流れを示す図である。
【００２７】
まず、本実施形態に係るプロトコルに用いるメッセージについて説明する。新たなノードを挿入するには、挿入ノードの左ノード、右ノードとなるノードを検索し、次に左ノードの右リンクと、右ノードの左リンクを、挿入ノードに向けるよう更新する必要がある。
【００２８】
このために、挿入ノードから左ノードに対し、左ノードの右リンクを更新するよう要求する右リンク更新要求メッセージ（SetRメッセージ）を送信する右リンク更新処理と、挿入ノードから右ノードに対し、右ノードの左リンクを更新するよう要求する左リンク更新要求メッセージ（SetLメッセージ）を送信する左リンク更新処理を実行する。
【００２９】
右リンク更新処理が完了すると、右リンク更新完了通知メッセージ（SetRAckメッセージ）が返信される。右リンク更新処理が失敗した場合は、右リンク更新失敗通知メッセージ（SetRNakメッセージ）が返信される。
【００３０】
また、SetL メッセージを受信して左リンクを付け替える場合には、付け替える前の左ノードに対して左リンク解放通知メッセージ（UnrefLメッセージ）を送信する。
【００３１】
次に、右リンク更新処理や左リンク更新処理を実行する際に用いられる、検出情報、リンクバージョン情報、参照カウンタについて説明する。
【００３２】
検出情報とは、ノードの挿入や削除によってノードの接続先が変更されるたびに更新される情報である。この検出情報は各ノードに付与されている。本実施形態では、ノードの右リンク先を示す接続先情報を検出情報として利用（兼用）する。
【００３３】
リンクバージョン情報とは、自ノードあるいは隣接ノードが接続先を変更した回数を示す。本実施形態では、リンクバージョン情報は整数値で表される（以下、リンク番号という）。
【００３４】
リンク番号は各ノードの左右のリンクに対して付与され、それぞれ左リンク番号、右リンク番号と呼ぶ。各ノードの左リンク番号は、自ノードの左リンク（左方向の接続先）を変更した回数を示し、右リンク番号は、右ノード（隣接ノード）が接続先を変更した回数を示す。ノードａの右ノードがノードｂで、定常状態（ａ、ｂ間で転送中のメッセージが存在しない場合）にある場合、ｂの左リンク番号とａの右リンク番号は等しい。
【００３５】
リンク番号は以下のルールで割り当てる。
１．ノードnをノードａとノードｂの間に挿入する場合、nの左リンク番号とａの右リンク番号は０とする。また、nの右リンク番号とｂの左リンク番号は、nを挿入前のａの右リンク番号+１とする。
２．ノードnを削除する場合、nの左ノードの右リンク番号とnの右ノードの左リンク番
号はnの右リンク番号+１とする。
【００３６】
なお、本実施形態では、リンクバージョン情報として整数（リンク番号）を用いているが、十分要素数の大きい全順序集合の要素ならば整数以外でもよく、例えばアルファベットなどを用いることも可能である。
【００３７】
参照カウンタは、他のノードから左リンクによって参照される数を数えるためのカウンタで、各ノードが保持する。挿入済みのノードの参照カウンタは定常状態では１である。参照カウンタはSetRメッセージを受信した場合に１加算し、UnrefLメッセージを受信したときに１減算する。
【００３８】
以下、ノードuが保持する情報を以下のように表記する。
・u.l uの左リンク
・u.r uの右リンク（uの検出情報を兼ねる）
・u.lnum uの左リンク番号
・u.rnum uの右リンク番号
・u.ref uの参照カウンタ
なお、ここではu.l、u.rはノードの位置（IPアドレスなど）と、ノードのキー値の両方を指すものとして扱っている（実際の実装では位置と値は別々の変数で保持する必要がある)。
【００３９】
（ノードの挿入方法）
以下、ノードuを挿入する場合について説明する。ノード u は何らかの方法でリングに挿入済みの任意のノード qを知っているものとする。図１は、ノードを挿入する場合の基本的な流れを示しており、以下の流れで処理を行う。
【００４０】
(１)まず，ノードuは挿入場所を求めるためにノードqからリングを辿り、uの左ノードとなるノード（aとする）、右ノードとなるノード（bとする）を検索する。uの挿入前はaの右ノードがbである。ここではaの右リンク番号とbの左リンク番号はともに整数値「d」とする（図１の状態Ｓ１）。本実施形態では、ノードaの検出情報としてaの現在の右リンク先（ここではｂ）を用いるため、uがbを入手するステップが請求項１の「入手ステップ」に相当する。
【００４１】
(２)次に、uの左リンクをaに、右リンクをbに接続する。（これをu.l:=a, u.r:=bで表す）。また、u.lnum:=０とする。
【００４２】
(３)uはａの右リンクをuに変更するために、ａにSetRメッセージを送信する（請求項１の「第１の送信ステップ」に相当）。SetRメッセージの引数は、rcur(=b)、rnew(=u)、rnewnum(=０)である。ここで、rcurは検出情報であり、uが想定するａの現在の右リンク先である。rnewは新しい右リンク先で、接続情報に相当する。rnewnumは新しい右リンク番号を示している。
【００４３】
(４)SetR メッセージを受信したノードaは、自らが保持する検出情報a.rと、SetRメッセージに含まれる検出情報rcurが一致するか否かを判定する（請求項１の「第１の判定ステップ」に相当）。また、aが削除中ではないか否かを判定する。(Ａ)a.r=rcurかつ(Ｂ)ａが削除中ではない場合、右リンク(a.r)と右リンク番号(a.rnum)をメッセージに従って変更し（a.rを変更することが請求項１の「第１のリンク更新ステップ」に相当する）、参照カウンタ(a.ref)を１加算してからSetRAckメッセージを返す（図の状態Ｓ２）。SetRAckメッセージの引数には、ａの変更前の右リンク番号を格納する。(Ａ)の条件は、検出情報が一致するかどうかのチェックに相当し、他のノードからのSetRメッセージと競合が発生したかどうかを判定するためのものである。また、(Ｂ)の条件は、削除中のノードに新たなノードを接続しないようにするためのものである。
【００４４】
(５)上記(Ａ)、(Ｂ)の条件が満たされない場合は、SetRNakメッセージを返す。
【００４５】
(６)uがSetRAckメッセージを受信した場合、メッセージに含まれる右リンク番号に１を加算したものを自身の右リンク番号(u.rnum)とし、また、参照カウンタ（u.ref）を１に設定する。次にｂの左リンクをuに変更するために、ｂにSetLメッセージを送信する（請求項５の「第３の送信ステップ」に相当）。SetLメッセージの引数はlnew(=u)、lnewnum(=u.rnum)、prevl(=u.l)である。ここで、lnewはｂの新しい左ノード、lnewnumはｂの新しい左リンク番号、prevlはｂがUnrefLメッセージを送信する相手ノードを示している。
【００４６】
(７)uがSetRNak メッセージを受信した場合、しばらく待ってステップ（１）からやり直す。
【００４７】
(８)SetLメッセージを受信したbは、メッセージに含まれるlnewnum と現在のbの左リンク番号(b.lnum)の大小関係によりいずれを優先するかを比較判定する（請求項５の「第３の判定ステップ」に相当）。前者の方が大きければ前者の方が優先すると判断し、bの左リンク(b.l)と左リンク番号(b.lnum)を更新する（請求項５の「第３のリンク更新ステップ」に相当。図の状態Ｓ３）。また、比較の結果にかかわらずbはメッセージに含まれるprevlが示すノードに対してUnrefLメッセージを送信する。これは、bの左リンクがprevlを指していないことを示す。
【００４８】
(９)UnrefLメッセージを受け取ったノード（ここではa）は、参照カウンタ(a.ref)を１減算する。
【００４９】
（ノードの削除方法）
次に、ノードuを削除する場合の基本的な流れについて説明する。図２は、ノードを削除する場合の基本的な流れを示す図である。ノードの削除は以下のように行う。
【００５０】
（１)以下、u.lの指すノードをaとし、u.rの指すノードをbとする。また、aの右リンク番号とuの左リンク番号は０，uの右リンク番号とbの左リンク番号は「d+1」とする（図2の状態Ｓ１）。ノードuは、aの右リンクをu.rに変更するためにaにSetRメッセージを送信する（請求項２の「第２の送信ステップ」に相当）。SetRメッセージの引数は、rcur(=u)、rnew(=u.r)、rnewnum(=u.rnum+１)である。
【００５１】
(２)SetRメッセージを受信したノードは、メッセージをノード挿入時と同じ方法で処理する。すなわち、SetR メッセージを受信したノードaは、自らが保持する検出情報a.rと、SetRメッセージに含まれる検出情報rcurが一致するか否かを判定する（請求項２の「第２の判定ステップ」に相当）。また、ノードaが削除中ではないか否かを判定する。(Ａ)a.r=rcurかつ(Ｂ)ａが削除中ではない場合、右リンク(a.r)と右リンク番号(a.rnum)をメッセージに従って変更し（a.rを変更することが請求項２の「第２のリンク更新ステップ」に相当する）、参照カウンタ(a.ref)を１加算してからSetRAckメッセージを返す（図の状態Ｓ２）。
【００５２】
(３)uはSetRAckメッセージを受信したら、ノードbの左リンクをaに変更するために、bにSetLメッセージを送信する（請求項５の「第３の送信ステップ」に相当）。SetLメッセージの引数は、lnew(=a)、lnewnum(=u.rnum+１)、prevl(=u)である。
【００５３】
(４)uがSetRNakメッセージを受信した場合はしばらく待ってステップ（１）からやり直す。
【００５４】
(５)SetLメッセージを受信したノードbは、メッセージをノード挿入時と同じ方法で処理する。すなわち、bは、メッセージに含まれるlnewnumと現在のbの左リンク番号(b.lnum)の大小関係によりいずれを優先するかを比較判定する（請求項６の「第４の判定ステップ」に相当）。前者の方が大きければ前者の方が優先すると判断し、bの左リンク(b.l)と左リンク番号(b.lnum)を更新する（請求項６の「第４のリンク更新ステップ」に相当。図の状態Ｓ３）。また、比較の結果にかかわらずbはメッセージに含まれるprevlが示すノードに対してUnrefLメッセージを送信する(請求項８の「減少メッセージ送信ステップ」に相当)。
【００５５】
(６)uがu.rからUnrefLメッセージを受信すると、uの参照カウンタを１減少させる（請求項８の「参照カウンタ減少ステップ」に相当）。uの参照カウンタが基準値０になった時点で、uは左ノードu.lにUnrefLメッセージを送信してから、削除処理を完了する（請求項８の「削除実行ステップ」に相当）。このようにuの参照カウンタが０になることを待つことで、左リンクによりuを指しているノードが存在する間はuの削除完了を遅延させる。
【００５６】
左リンクは右リンクよりも遅れて更新されるため、ステップ（１）でuが削除のためにSetRメッセージを送信した時点でu.lの値は正しいとは限らないが（u.lとuの間に別のノードvが挿入されている可能性がある）、この場合ノードu.lの右リンクはuではなくvになっているため、uが送信したSetRメッセージに対してSetRNakメッセージが返される。この場合、しばらく待ってステップ(１)からやりなおす（ステップ（４））。そのうちuはvからのSetLメッセージを受信して左リンクが書き換わるため、いずれ右リンク変更処理は成功する。
【００５７】
（複数ノード挿入の例）
上で述べた方式を用いて、複数のノードを並行して挿入する場合の例について説明する。
【００５８】
図３はノードＡとＤが隣接し、Ａの右リンク番号、Ｄの左リンク番号ともdという状態(状態S１)から、ノードＢとＣがＡとＤの間に同時に挿入しようとする場合のトポロジの変化とメッセージのやりとりを示したものである。
【００５９】
ＢとＣはＡにSetRメッセージを送信するが、引数のrcurはどちらもＤである。図３ではＡはＢからのSetRメッセージを先に受信する場合を想定している。ＡがＢからのSetRメッセージを受信すると右リンクはＢに変更する(状態S２)。ＡがＣからのSetRメッセージを受信したときには、Ａの右ノードとrcurが一致しないため（検出情報が不一致）、SetRNakメッセージを返している(状態S３）。このように、検出情報を用いることで、複数のノード挿入が競合したことを検出できる。Ｃは再度挿入位置を求めて挿入をやり直す（状態Ｓ４）。
【００６０】
SetRAckメッセージを受信したＢとＣはSetLメッセージをＤに送信するが、図では（SetRの順序と異なり）Ｃからのメッセージを先に受信した場合を想定している(状態S５)。このとき、Ｄは左リンクをＣに、左リンク番号をd+２に設定する。その後ＢからのSetLメッセージを受信するが、Ｂからのメッセージに含まれる左リンク番号(d+１)は現在の左リンク番号(d+２)よりも小さいため、左リンクは変更しない。このように、リンク番号を用いることで、SetLメッセージの到着順序が入れ替わっても問題なくＤは正しい左ノードを指す。すなわち、左リンクの更新はSetLメッセージを１つ転送するだけでよい。
【００６１】
（ノードの挿入と削除が並行して起こる場合の例）
次に、ノードの挿入と削除が並行して起こった場合の例を説明する。
【００６２】
図４は、ＣがＢとＤの間に挿入され、並行してＢが削除される場合のトポロジの変化とメッセージのやりとりを示したものである。図では、ノードＣの挿入開始の方がノードＢの削除開始よりも早い場合を想定している。状態Ｓ１でのＡとＢとの間、ＢとＤと間の左右のリンク番号はそれぞれ「ｂ」、「ｄ」である。
【００６３】
ノードＣは、Ｂに対して、右リンクを更新するよう要求するSetRメッセージを送信する。SetRメッセージを受信したＢは、参照カウンタを１増加して「２」にする（状態Ｓ２）。そして、ＢはＣに対して、左リンクをＡに更新するようSetLメッセージを送信する。Ｃからの左リンクが外され、ＣからのUnrefLメッセージを受信したＢは、参照カウンタを「２」から「１」に減少させる。この時点でＢの参照カウンタは所定の基準値「０」になっていないため、Ｂはまだ削除を完了できない。
【００６４】
ＤがＣからのSetLメッセージを受信すると、Ｄは左リンクをＣに変更するとともにUnrefLメッセージをＢに送信する（状態S４）。ノードＢがUnrefLメッセージを受信すると、参照カウンタを「１」から「０」に減少させる。参照カウンタが基準値「０」になったため、Ｂは自身の削除処理を完了する。
【００６５】
このように、ノードＢは、ノードＤの左リンクがノードＢを指している間は削除を完了できず、ノードＤの左リンクがノードＣを指すようになってから削除を完了できる。UnrefLメッセージと参照カウンタにより、各ノードの左リンクは削除済みのノードを指すことがないため、左方向リングは途切れることはなく、常に左方向へのデータ転送が可能であるという利点がある。
【００６６】
（第２の実施形態）
次に、本発明に係るノードの接続方法の第２の実施形態について説明する。本実施形態では、第１の実施形態を拡張し、ノードが故障した場合に、故障したノードをバイパスするようにリンクを修復する機能を追加する。以下、リンク修復の方式について説明する。
【００６７】
第１の実施形態では、各ノードの左リンク番号が単調に増加することを利用して左リンク更新処理を簡潔に行っていた。リンク修復の際にも右ノードの左リンク番号を単調に増加させるために、リンク修復は故障したノードの右ノードが主体となって行う必要がある（故障したノードの左ノードは、故障したノードの右ノードの左リンク番号を知らないため）。
【００６８】
挿入済みの各ノードは、左ノードの状態を調べるために定期的に左ノードに状態要求メッセージ(getStat)を送信する。getStatメッセージを受信したノードは状態メッセージ(Stat)を返す。
【００６９】
ノードuが左ノードu.lにgetStatメッセージを送信し、一定時間以内にu.lからStatメッセージを受信できなかった場合、左ノードは故障したと判断し、以下に述べるリンク修復処理を行う。
【００７０】
ノードuは、リンクを修復するためにuの左側で最も近い、故障していないノードvと、vの右ノードv.rを得る必要がある（v.rは、vに対してSetRメッセージを送信するときの引数rcurとして用いる）。
【００７１】
本実施形態では、何らかの手段でvとv.rが得られるものと想定する。そのための方法は任意であるが、例えば双方向リングを使用している上位のデータ構造を利用して発見する、あるいは各ノードが左方向の一定数のノードを記憶しておく、といった方法が考えられる。
【００７２】
uは、vとv.rを得たら、vに対してSetRメッセージを送信し、vの右リンクをuに書き換える。このときv-u間のリンクに対する左右のリンク番号に設定するべき値を考える。ノードＡ、Ｂ、Ｃがこの順に並んでいるものとする。また、Ｂ-Ｃ間のリンクに対するリンク番号をｃとする。ここでＢ-Ｃ間のネットワークが一時的に切断された場合を考える。ＣからはＢが故障したようにみえるため、ＢをバイパスしてＡ、Ｃを繋ごうとする。このとき、Ａ-Ｃ間の左右のリンク番号はｃ+１にするというのが単純な方式だが、この間にＢ-Ｃ間に別のノードＸか挿入される場合(ＸがＢと通信できれば可能性がある)、Ｘの右リンク番号(これはＣの左リンク番号でもある)もｃ+１になってしまい、リンク番号の一意性が保てなくなる。これはＸとＣが通信可能な場合問題となる。
【００７３】
このため、本実施形態では、リンク番号を(g,s)という形式に拡張する。sは上述のリンク番号に対応する。gはリンクを修復した回数を表し、初期状態では０である。以下、ノードの左右のリンク番号は(g,
s)形式とし、ノードuの左リンク番号のgの値をu.lnum.gのように表記する。（自ノードのリンク番号のgが請求項９の「隣接ノード故障カウンタ」に対応）。
【００７４】
また、リンク番号xとyに対し、以下の規則により等値関係、大小関係を定義する。
・x=y iff(x.g=y.g)∧(x.s=y.s)
・x<y iff(x.g<y.g)∨(x.g=y.g∧x.s<y.s)
さらに、リンク番号xに対して次の関数を定義する。
・x.gnext()=(x.g+１,０)
・x.next()=(x.g,x.s+１)
【００７５】
uが左リンクを修復する際は、u.lnum:=u.lnum.gnext()としてからvにSetRメッセージを送信する。これによりリンク番号の一意性を保つことが可能である。例えば上の例で、初期状態でＢ−Ｃ間のリンク番号を(cg, cs)とすると、Ｘの右リンク番号は(cg, cs+１)となるが、リンク修復後のＣの左リンク番号は(cg+１, ０)となる。その後ＸからのSetLメッセージをＣが受信した場合、リンク番号の大小関係からメッセージは無視される(このように、左リンクが修復される前の情報に基づく古いSetLメッセージは無視される)。（リンク番号の大小関係の定義から、リンク番号のgの大きい方が優先されるが、これが請求項１０に対応する）。
【００７６】
uはノードvと、vの右ノードv.rを得ると、以下のようにして左リンクを修復する。
【００７７】
(１)uはu.l:=v、u.lnum:=u.lnum.gnext()としてからvに対してSetRメッセージを送信する。SetRメッセージの引数は、rcur(=v.r)、rnew(=u)、rnewnum(=u.lnum)である。
【００７８】
(２)SetRメッセージを受信したv は、メッセージを実施形態１と同じ方法で処理する（ただしリンク番号は(g, s)形式に拡張されている）。
【００７９】
(３)uがSetRAckを受信すれば修復が完了する。SetRNakメッセージを受信した場合は
しばらく待ってgetStatメッセージの送信からやりなおす。
【００８０】
以上、本発明によれば、ノード故障がない場合、常に右リンクは正しいノードを指し、左リンクはいずれ正しいノードを指す。また左リンクは常に生きているノードを指すため、リングに挿入されているノードを検索した場合、必ず発見できる。
【００８１】
また、右方向リングに挿入（または削除）した後、左方向リングに挿入（または削除）するためにはSetLメッセージを１つ転送するだけでよいため、多数のノードが並行して挿入・削除するような状況でも効率的に挿入・削除操作を実行できる。
【００８２】
さらに、本発明では排他制御を行うノードは存在しないため、ノード障害が発生した場合にも安全にリング構造を修復可能である。
【技術分野】
【０００１】
本発明は、ネットワーク内のノードを接続する際に用いられるノードの接続方法、およびその接続方法を用いたネットワークトポロジ構築方法に関する。
【背景技術】
【０００２】
ネットワーク上でサービスを提供するシステムの形態として、ピアツーピア（以下Ｐ２Ｐと表記する）システムが注目されている。Ｐ２Ｐシステムは各ノードが自律的に他のノードと協調動作することで、ノード数に応じて性能を向上させることができるシステムである。Ｐ２Ｐシステムは大きく分けてノードの接続関係（トポロジ）に制約のない非構造型Ｐ２Ｐシステムと、トポロジに一定の制約がある構造型Ｐ２Ｐシステムに分類できる。構造型Ｐ２Ｐシステムでは、トポロジを維持するコストがかかるが、ノード数やデータ数の対数オーダのコストでデータを検索できるという特徴を持つ。
【０００３】
構造化Ｐ２Ｐシステムでよく用いられるトポロジの一つに双方向リングトポロジがある。双方向リングトポロジでは、各ノードはキー値（ノードの識別子などがよく用いられる）、右方向リンク、左方向リンクを持つ。右方向リンクは自分のキー値よりも次に大きいキー値を持つノード（存在しない場合は最も小さいキーを持つノード）に接続し、左方向リンクは自分のキー値よりも次に小さいキー値を持つノード（存在しない場合は最も大きいキーを持つノード）に接続する。
【０００４】
双方向リングは、右方向リンクを用いた右方向リングと、左方向リンクを用いた左方向リングの２つの片方向リングに分解できる。
【０００５】
Ｐ２Ｐシステムでは、システム稼働中にノードが挿入（追加）・削除される場合がある。双方向リングトポロジを構成するアルゴリズムでは、ノードの挿入・削除が予測できないタイミングで発生することを想定する必要がある。またノードが故障した場合は、故障したノードをバイパスしてリングを修復することも必要である。
【０００６】
双方向リングトポロジを構成する手法を開示している文献としては、たとえば下記非特許文献１、２がある。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】IonStoica, et al. Chord: A scalable peer-to-peer lookup protocol for internetapplications. IEEE/ACM Transactions on Networking, Vol. １１, No.１, pp. １７-３２, ２００３.
【非特許文献２】NancyLynch, Dahlia Malkhi, and David Ratajczak. Atomic Data Access in ContentAddressable Networks. In Proceedings of the １st International Workshop on Peer-to-PeerSystems, pp. 295-305, ２００２.
【発明の開示】
【発明が解決しようとする課題】
【０００８】
上記非特許文献１に記載された手法では、ノードの挿入・削除時に、双方向リングは一時的に一貫性がない状態（各ノードがキーの値が最も近いノードと接続していない状態）になる。例えばノード１の右方向リンクがノード２を指している時に、ノード１とノード２の間にノード３とノード４が並行して挿入された場合、ノード３、ノード４のいずれも右方向リンクがノード２を指した状態（一貫性が崩れた状態）になる。この状態は定期的に実行する修復手続きによっていずれ解消されるが、このような状態が存在することは双方向リングを用いたアプリケーションプログラムにとって好ましいことではない。
【０００９】
また、上記非特許文献２では、ノードの挿入・削除時に隣接するノードが排他制御することでリングの一貫性を確保する手法が記述されている。しかし、この手法は排他制御しているノードが故障した場合にリングを確実に修復することが困難であるという問題がある。この理由は、ノードが故障した時の排他制御状態を他のノードが確実に知ることができないためである。
【００１０】
本発明は上記のような技術課題を解決するためになされたものであり、ノードが並行して挿入・削除された場合でも片方向リングの一貫性を保持できるノードの接続方法を提供することを目的とする。
【００１１】
また、ノードを片方向リングに挿入（あるいは片方向リングから削除）した後で、反対方向リングに効率よく挿入する（あるいは反対方向リングから削除する）方法を提供することも目的とする。
【００１２】
さらに、ノード故障やネットワーク故障が発生した場合でも安定して確実に双方向リングを修復できるノードの連結方法を提供することも目的とする。
【課題を解決するための手段】
【００１３】
本発明は、第１のノードと、第１のノードの接続先である第２のノードの間に、第３のノードを挿入しようとする場合のノードの接続方法であって、各ノードは接続先が変更された際に更新される検出情報を有している。まず入手ステップにおいて、第３のノードが第１のノードが保持する検出情報を入手する。そして、送信ステップにおいて、第３のノードが第１のノードに、前記検出情報と、第３のノードに接続するための接続先情報とを含むリンク更新メッセージを送信する。
【００１４】
次に、判定ステップにおいて、前記第１のノードが、前記リンク更新メッセージ受信時の第１のノードが保持する検出情報と、前記第１のリンク更新メッセージに含まれる検出情報が一致するか否かを判定し、一致すると判定された場合に、前記接続先情報に基づいて第１のノードが第３のノードに接続するとともに、第１のノードが保持する検出情報を異なる検出情報に更新する。
【００１５】
また、第２のノードから第１のノードへも接続している場合に、第１のノードに付与された隣接ノードのリンクバージョン情報を用いて以下のステップを有してもよい。
【００１６】
すなわち、前記第３のノードが、前記判定ステップにおいて一致していると判定された場合に、第１のノードに付与されている隣接ノードのリンクバージョン情報を更新した更新リンクバージョン情報と、第３のノードに接続するための接続先情報とを含むリンク更新メッセージを第２のノードに送信する送信ステップとを備える。
【００１７】
そして、前記リンク更新メッセージを受信した第２のノードが、第２のノードが保持する自ノードのリンクバージョン情報よりも前記リンク更新メッセージに含まれる更新リンクバージョン情報が優先するか否かを判定する判定ステップと、前記リンク更新メッセージに含まれる更新リンクバージョン情報が優先すると判定した場合に、前記接続先情報に基づいて第２のノードから第３のノードへ接続するとともに、第２のノードが保持する自ノードのリンクバージョン情報を前記リンク更新メッセージに含まれる更新リンクバージョン情報に変更する第２のリンク更新ステップを有しても良い。
【００１８】
さらに本発明は、第４のノードが第５のノードに接続し、第５のノードが第６のノードに接続している場合に、第５のノードを削除しようとする場合、各ノードが保持する他のノードから接続されている数を示す参照カウンタを用いて以下のステップを有しても良い。
【００１９】
すなわち、第６のノードがリンク更新メッセージを受信した場合に、第６のノードが前記第５のノードに参照カウンタを減少させる参照カウンタ減少メッセージを送信する参照カウンタ減少メッセージ送信ステップと、第５のノードが前記参照カウンタ減少メッセージを受信した場合に参照カウンタを減少させる参照カウンタ減少ステップと、参照カウンタの値が基準値を下回ったときに第５のノードを削除する削除実行ステップを備える。
【００２０】
さらに本発明は、上述のノードの接続方法を用いて、片方向リングトポロジあるいは双方向リングトポロジあるいは片方向連結リストトポロジあるいは双方向連結リストトポロジを構築することができる。
【００２１】
さらに本発明は、上述のノードの接続方法を用いて構築するネットワークシステムであってもよい。
【発明の効果】
【００２２】
本発明によれば、片方向リングトポロジなどにおいて、リングの一貫性を維持したままノードを挿入、あるいは削除できる。また、片方向リングに反対方向のリングを加えて双方向リングに拡張した場合、反対方向リングへのノードの挿入、削除は非常に効率的に実行できる。さらに、ノード故障やネットワーク故障時にリングを安定して修復できる。
【図面の簡単な説明】
【００２３】
【図１】ノードを挿入する場合の基本的な流れを示す図
【図２】ノードを削除する場合の基本的な流れを示す図
【図３】複数のノードを並行して挿入する場合のノードの状態を示す図
【図４】ノードの挿入と削除が並行して起こった場合のノードの状態を示す図
【発明を実施するための最良の形態】
【００２４】
（第１の実施形態）
本発明の実施形態に係るノードの接続方法について説明する。本実施形態のノードの接続方法は双方向リングについて適用しているが、これに限定されるものではない。例えば、片方向リング、片方向連結リスト、双方向連結リスト等、種々のネットワークトポロジの構築に用いることができる。
【００２５】
本実施形態では、本発明を双方向リングの構成のために用いる。各ノードは、右方向、左方向の２つのリンク（接続先）を持ち、他のノード、あるいは自分自身に接続する。双方向リングは各ノードの右方向リンクをたどることで得られる右方向リングと、左方向リンクをたどることで得られる左方向リングの２つの片方向リングに分解できる。本実施形態では、リングの要素である各ノードは，それぞれのノードが保持するキー値によってソートされている。ここでは右方向がキー値の増加する方向とし、左方向がキー値の減少する方向とする。ただし、最大値を持つノードの右ノードは最小値を持つノードであり、また最小値を持つノードの左ノードは最大値を持つノードである。
【００２６】
双方向リングにノードを挿入する場合の基本的な流れについて説明する。図１は、ノードを挿入する場合の基本的な流れを示す図である。
【００２７】
まず、本実施形態に係るプロトコルに用いるメッセージについて説明する。新たなノードを挿入するには、挿入ノードの左ノード、右ノードとなるノードを検索し、次に左ノードの右リンクと、右ノードの左リンクを、挿入ノードに向けるよう更新する必要がある。
【００２８】
このために、挿入ノードから左ノードに対し、左ノードの右リンクを更新するよう要求する右リンク更新要求メッセージ（SetRメッセージ）を送信する右リンク更新処理と、挿入ノードから右ノードに対し、右ノードの左リンクを更新するよう要求する左リンク更新要求メッセージ（SetLメッセージ）を送信する左リンク更新処理を実行する。
【００２９】
右リンク更新処理が完了すると、右リンク更新完了通知メッセージ（SetRAckメッセージ）が返信される。右リンク更新処理が失敗した場合は、右リンク更新失敗通知メッセージ（SetRNakメッセージ）が返信される。
【００３０】
また、SetL メッセージを受信して左リンクを付け替える場合には、付け替える前の左ノードに対して左リンク解放通知メッセージ（UnrefLメッセージ）を送信する。
【００３１】
次に、右リンク更新処理や左リンク更新処理を実行する際に用いられる、検出情報、リンクバージョン情報、参照カウンタについて説明する。
【００３２】
検出情報とは、ノードの挿入や削除によってノードの接続先が変更されるたびに更新される情報である。この検出情報は各ノードに付与されている。本実施形態では、ノードの右リンク先を示す接続先情報を検出情報として利用（兼用）する。
【００３３】
リンクバージョン情報とは、自ノードあるいは隣接ノードが接続先を変更した回数を示す。本実施形態では、リンクバージョン情報は整数値で表される（以下、リンク番号という）。
【００３４】
リンク番号は各ノードの左右のリンクに対して付与され、それぞれ左リンク番号、右リンク番号と呼ぶ。各ノードの左リンク番号は、自ノードの左リンク（左方向の接続先）を変更した回数を示し、右リンク番号は、右ノード（隣接ノード）が接続先を変更した回数を示す。ノードａの右ノードがノードｂで、定常状態（ａ、ｂ間で転送中のメッセージが存在しない場合）にある場合、ｂの左リンク番号とａの右リンク番号は等しい。
【００３５】
リンク番号は以下のルールで割り当てる。
１．ノードnをノードａとノードｂの間に挿入する場合、nの左リンク番号とａの右リンク番号は０とする。また、nの右リンク番号とｂの左リンク番号は、nを挿入前のａの右リンク番号+１とする。
２．ノードnを削除する場合、nの左ノードの右リンク番号とnの右ノードの左リンク番
号はnの右リンク番号+１とする。
【００３６】
なお、本実施形態では、リンクバージョン情報として整数（リンク番号）を用いているが、十分要素数の大きい全順序集合の要素ならば整数以外でもよく、例えばアルファベットなどを用いることも可能である。
【００３７】
参照カウンタは、他のノードから左リンクによって参照される数を数えるためのカウンタで、各ノードが保持する。挿入済みのノードの参照カウンタは定常状態では１である。参照カウンタはSetRメッセージを受信した場合に１加算し、UnrefLメッセージを受信したときに１減算する。
【００３８】
以下、ノードuが保持する情報を以下のように表記する。
・u.l uの左リンク
・u.r uの右リンク（uの検出情報を兼ねる）
・u.lnum uの左リンク番号
・u.rnum uの右リンク番号
・u.ref uの参照カウンタ
なお、ここではu.l、u.rはノードの位置（IPアドレスなど）と、ノードのキー値の両方を指すものとして扱っている（実際の実装では位置と値は別々の変数で保持する必要がある)。
【００３９】
（ノードの挿入方法）
以下、ノードuを挿入する場合について説明する。ノード u は何らかの方法でリングに挿入済みの任意のノード qを知っているものとする。図１は、ノードを挿入する場合の基本的な流れを示しており、以下の流れで処理を行う。
【００４０】
(１)まず，ノードuは挿入場所を求めるためにノードqからリングを辿り、uの左ノードとなるノード（aとする）、右ノードとなるノード（bとする）を検索する。uの挿入前はaの右ノードがbである。ここではaの右リンク番号とbの左リンク番号はともに整数値「d」とする（図１の状態Ｓ１）。本実施形態では、ノードaの検出情報としてaの現在の右リンク先（ここではｂ）を用いるため、uがbを入手するステップが請求項１の「入手ステップ」に相当する。
【００４１】
(２)次に、uの左リンクをaに、右リンクをbに接続する。（これをu.l:=a, u.r:=bで表す）。また、u.lnum:=０とする。
【００４２】
(３)uはａの右リンクをuに変更するために、ａにSetRメッセージを送信する（請求項１の「第１の送信ステップ」に相当）。SetRメッセージの引数は、rcur(=b)、rnew(=u)、rnewnum(=０)である。ここで、rcurは検出情報であり、uが想定するａの現在の右リンク先である。rnewは新しい右リンク先で、接続情報に相当する。rnewnumは新しい右リンク番号を示している。
【００４３】
(４)SetR メッセージを受信したノードaは、自らが保持する検出情報a.rと、SetRメッセージに含まれる検出情報rcurが一致するか否かを判定する（請求項１の「第１の判定ステップ」に相当）。また、aが削除中ではないか否かを判定する。(Ａ)a.r=rcurかつ(Ｂ)ａが削除中ではない場合、右リンク(a.r)と右リンク番号(a.rnum)をメッセージに従って変更し（a.rを変更することが請求項１の「第１のリンク更新ステップ」に相当する）、参照カウンタ(a.ref)を１加算してからSetRAckメッセージを返す（図の状態Ｓ２）。SetRAckメッセージの引数には、ａの変更前の右リンク番号を格納する。(Ａ)の条件は、検出情報が一致するかどうかのチェックに相当し、他のノードからのSetRメッセージと競合が発生したかどうかを判定するためのものである。また、(Ｂ)の条件は、削除中のノードに新たなノードを接続しないようにするためのものである。
【００４４】
(５)上記(Ａ)、(Ｂ)の条件が満たされない場合は、SetRNakメッセージを返す。
【００４５】
(６)uがSetRAckメッセージを受信した場合、メッセージに含まれる右リンク番号に１を加算したものを自身の右リンク番号(u.rnum)とし、また、参照カウンタ（u.ref）を１に設定する。次にｂの左リンクをuに変更するために、ｂにSetLメッセージを送信する（請求項５の「第３の送信ステップ」に相当）。SetLメッセージの引数はlnew(=u)、lnewnum(=u.rnum)、prevl(=u.l)である。ここで、lnewはｂの新しい左ノード、lnewnumはｂの新しい左リンク番号、prevlはｂがUnrefLメッセージを送信する相手ノードを示している。
【００４６】
(７)uがSetRNak メッセージを受信した場合、しばらく待ってステップ（１）からやり直す。
【００４７】
(８)SetLメッセージを受信したbは、メッセージに含まれるlnewnum と現在のbの左リンク番号(b.lnum)の大小関係によりいずれを優先するかを比較判定する（請求項５の「第３の判定ステップ」に相当）。前者の方が大きければ前者の方が優先すると判断し、bの左リンク(b.l)と左リンク番号(b.lnum)を更新する（請求項５の「第３のリンク更新ステップ」に相当。図の状態Ｓ３）。また、比較の結果にかかわらずbはメッセージに含まれるprevlが示すノードに対してUnrefLメッセージを送信する。これは、bの左リンクがprevlを指していないことを示す。
【００４８】
(９)UnrefLメッセージを受け取ったノード（ここではa）は、参照カウンタ(a.ref)を１減算する。
【００４９】
（ノードの削除方法）
次に、ノードuを削除する場合の基本的な流れについて説明する。図２は、ノードを削除する場合の基本的な流れを示す図である。ノードの削除は以下のように行う。
【００５０】
（１)以下、u.lの指すノードをaとし、u.rの指すノードをbとする。また、aの右リンク番号とuの左リンク番号は０，uの右リンク番号とbの左リンク番号は「d+1」とする（図2の状態Ｓ１）。ノードuは、aの右リンクをu.rに変更するためにaにSetRメッセージを送信する（請求項２の「第２の送信ステップ」に相当）。SetRメッセージの引数は、rcur(=u)、rnew(=u.r)、rnewnum(=u.rnum+１)である。
【００５１】
(２)SetRメッセージを受信したノードは、メッセージをノード挿入時と同じ方法で処理する。すなわち、SetR メッセージを受信したノードaは、自らが保持する検出情報a.rと、SetRメッセージに含まれる検出情報rcurが一致するか否かを判定する（請求項２の「第２の判定ステップ」に相当）。また、ノードaが削除中ではないか否かを判定する。(Ａ)a.r=rcurかつ(Ｂ)ａが削除中ではない場合、右リンク(a.r)と右リンク番号(a.rnum)をメッセージに従って変更し（a.rを変更することが請求項２の「第２のリンク更新ステップ」に相当する）、参照カウンタ(a.ref)を１加算してからSetRAckメッセージを返す（図の状態Ｓ２）。
【００５２】
(３)uはSetRAckメッセージを受信したら、ノードbの左リンクをaに変更するために、bにSetLメッセージを送信する（請求項５の「第３の送信ステップ」に相当）。SetLメッセージの引数は、lnew(=a)、lnewnum(=u.rnum+１)、prevl(=u)である。
【００５３】
(４)uがSetRNakメッセージを受信した場合はしばらく待ってステップ（１）からやり直す。
【００５４】
(５)SetLメッセージを受信したノードbは、メッセージをノード挿入時と同じ方法で処理する。すなわち、bは、メッセージに含まれるlnewnumと現在のbの左リンク番号(b.lnum)の大小関係によりいずれを優先するかを比較判定する（請求項６の「第４の判定ステップ」に相当）。前者の方が大きければ前者の方が優先すると判断し、bの左リンク(b.l)と左リンク番号(b.lnum)を更新する（請求項６の「第４のリンク更新ステップ」に相当。図の状態Ｓ３）。また、比較の結果にかかわらずbはメッセージに含まれるprevlが示すノードに対してUnrefLメッセージを送信する(請求項８の「減少メッセージ送信ステップ」に相当)。
【００５５】
(６)uがu.rからUnrefLメッセージを受信すると、uの参照カウンタを１減少させる（請求項８の「参照カウンタ減少ステップ」に相当）。uの参照カウンタが基準値０になった時点で、uは左ノードu.lにUnrefLメッセージを送信してから、削除処理を完了する（請求項８の「削除実行ステップ」に相当）。このようにuの参照カウンタが０になることを待つことで、左リンクによりuを指しているノードが存在する間はuの削除完了を遅延させる。
【００５６】
左リンクは右リンクよりも遅れて更新されるため、ステップ（１）でuが削除のためにSetRメッセージを送信した時点でu.lの値は正しいとは限らないが（u.lとuの間に別のノードvが挿入されている可能性がある）、この場合ノードu.lの右リンクはuではなくvになっているため、uが送信したSetRメッセージに対してSetRNakメッセージが返される。この場合、しばらく待ってステップ(１)からやりなおす（ステップ（４））。そのうちuはvからのSetLメッセージを受信して左リンクが書き換わるため、いずれ右リンク変更処理は成功する。
【００５７】
（複数ノード挿入の例）
上で述べた方式を用いて、複数のノードを並行して挿入する場合の例について説明する。
【００５８】
図３はノードＡとＤが隣接し、Ａの右リンク番号、Ｄの左リンク番号ともdという状態(状態S１)から、ノードＢとＣがＡとＤの間に同時に挿入しようとする場合のトポロジの変化とメッセージのやりとりを示したものである。
【００５９】
ＢとＣはＡにSetRメッセージを送信するが、引数のrcurはどちらもＤである。図３ではＡはＢからのSetRメッセージを先に受信する場合を想定している。ＡがＢからのSetRメッセージを受信すると右リンクはＢに変更する(状態S２)。ＡがＣからのSetRメッセージを受信したときには、Ａの右ノードとrcurが一致しないため（検出情報が不一致）、SetRNakメッセージを返している(状態S３）。このように、検出情報を用いることで、複数のノード挿入が競合したことを検出できる。Ｃは再度挿入位置を求めて挿入をやり直す（状態Ｓ４）。
【００６０】
SetRAckメッセージを受信したＢとＣはSetLメッセージをＤに送信するが、図では（SetRの順序と異なり）Ｃからのメッセージを先に受信した場合を想定している(状態S５)。このとき、Ｄは左リンクをＣに、左リンク番号をd+２に設定する。その後ＢからのSetLメッセージを受信するが、Ｂからのメッセージに含まれる左リンク番号(d+１)は現在の左リンク番号(d+２)よりも小さいため、左リンクは変更しない。このように、リンク番号を用いることで、SetLメッセージの到着順序が入れ替わっても問題なくＤは正しい左ノードを指す。すなわち、左リンクの更新はSetLメッセージを１つ転送するだけでよい。
【００６１】
（ノードの挿入と削除が並行して起こる場合の例）
次に、ノードの挿入と削除が並行して起こった場合の例を説明する。
【００６２】
図４は、ＣがＢとＤの間に挿入され、並行してＢが削除される場合のトポロジの変化とメッセージのやりとりを示したものである。図では、ノードＣの挿入開始の方がノードＢの削除開始よりも早い場合を想定している。状態Ｓ１でのＡとＢとの間、ＢとＤと間の左右のリンク番号はそれぞれ「ｂ」、「ｄ」である。
【００６３】
ノードＣは、Ｂに対して、右リンクを更新するよう要求するSetRメッセージを送信する。SetRメッセージを受信したＢは、参照カウンタを１増加して「２」にする（状態Ｓ２）。そして、ＢはＣに対して、左リンクをＡに更新するようSetLメッセージを送信する。Ｃからの左リンクが外され、ＣからのUnrefLメッセージを受信したＢは、参照カウンタを「２」から「１」に減少させる。この時点でＢの参照カウンタは所定の基準値「０」になっていないため、Ｂはまだ削除を完了できない。
【００６４】
ＤがＣからのSetLメッセージを受信すると、Ｄは左リンクをＣに変更するとともにUnrefLメッセージをＢに送信する（状態S４）。ノードＢがUnrefLメッセージを受信すると、参照カウンタを「１」から「０」に減少させる。参照カウンタが基準値「０」になったため、Ｂは自身の削除処理を完了する。
【００６５】
このように、ノードＢは、ノードＤの左リンクがノードＢを指している間は削除を完了できず、ノードＤの左リンクがノードＣを指すようになってから削除を完了できる。UnrefLメッセージと参照カウンタにより、各ノードの左リンクは削除済みのノードを指すことがないため、左方向リングは途切れることはなく、常に左方向へのデータ転送が可能であるという利点がある。
【００６６】
（第２の実施形態）
次に、本発明に係るノードの接続方法の第２の実施形態について説明する。本実施形態では、第１の実施形態を拡張し、ノードが故障した場合に、故障したノードをバイパスするようにリンクを修復する機能を追加する。以下、リンク修復の方式について説明する。
【００６７】
第１の実施形態では、各ノードの左リンク番号が単調に増加することを利用して左リンク更新処理を簡潔に行っていた。リンク修復の際にも右ノードの左リンク番号を単調に増加させるために、リンク修復は故障したノードの右ノードが主体となって行う必要がある（故障したノードの左ノードは、故障したノードの右ノードの左リンク番号を知らないため）。
【００６８】
挿入済みの各ノードは、左ノードの状態を調べるために定期的に左ノードに状態要求メッセージ(getStat)を送信する。getStatメッセージを受信したノードは状態メッセージ(Stat)を返す。
【００６９】
ノードuが左ノードu.lにgetStatメッセージを送信し、一定時間以内にu.lからStatメッセージを受信できなかった場合、左ノードは故障したと判断し、以下に述べるリンク修復処理を行う。
【００７０】
ノードuは、リンクを修復するためにuの左側で最も近い、故障していないノードvと、vの右ノードv.rを得る必要がある（v.rは、vに対してSetRメッセージを送信するときの引数rcurとして用いる）。
【００７１】
本実施形態では、何らかの手段でvとv.rが得られるものと想定する。そのための方法は任意であるが、例えば双方向リングを使用している上位のデータ構造を利用して発見する、あるいは各ノードが左方向の一定数のノードを記憶しておく、といった方法が考えられる。
【００７２】
uは、vとv.rを得たら、vに対してSetRメッセージを送信し、vの右リンクをuに書き換える。このときv-u間のリンクに対する左右のリンク番号に設定するべき値を考える。ノードＡ、Ｂ、Ｃがこの順に並んでいるものとする。また、Ｂ-Ｃ間のリンクに対するリンク番号をｃとする。ここでＢ-Ｃ間のネットワークが一時的に切断された場合を考える。ＣからはＢが故障したようにみえるため、ＢをバイパスしてＡ、Ｃを繋ごうとする。このとき、Ａ-Ｃ間の左右のリンク番号はｃ+１にするというのが単純な方式だが、この間にＢ-Ｃ間に別のノードＸか挿入される場合(ＸがＢと通信できれば可能性がある)、Ｘの右リンク番号(これはＣの左リンク番号でもある)もｃ+１になってしまい、リンク番号の一意性が保てなくなる。これはＸとＣが通信可能な場合問題となる。
【００７３】
このため、本実施形態では、リンク番号を(g,s)という形式に拡張する。sは上述のリンク番号に対応する。gはリンクを修復した回数を表し、初期状態では０である。以下、ノードの左右のリンク番号は(g,
s)形式とし、ノードuの左リンク番号のgの値をu.lnum.gのように表記する。（自ノードのリンク番号のgが請求項９の「隣接ノード故障カウンタ」に対応）。
【００７４】
また、リンク番号xとyに対し、以下の規則により等値関係、大小関係を定義する。
・x=y iff(x.g=y.g)∧(x.s=y.s)
・x<y iff(x.g<y.g)∨(x.g=y.g∧x.s<y.s)
さらに、リンク番号xに対して次の関数を定義する。
・x.gnext()=(x.g+１,０)
・x.next()=(x.g,x.s+１)
【００７５】
uが左リンクを修復する際は、u.lnum:=u.lnum.gnext()としてからvにSetRメッセージを送信する。これによりリンク番号の一意性を保つことが可能である。例えば上の例で、初期状態でＢ−Ｃ間のリンク番号を(cg, cs)とすると、Ｘの右リンク番号は(cg, cs+１)となるが、リンク修復後のＣの左リンク番号は(cg+１, ０)となる。その後ＸからのSetLメッセージをＣが受信した場合、リンク番号の大小関係からメッセージは無視される(このように、左リンクが修復される前の情報に基づく古いSetLメッセージは無視される)。（リンク番号の大小関係の定義から、リンク番号のgの大きい方が優先されるが、これが請求項１０に対応する）。
【００７６】
uはノードvと、vの右ノードv.rを得ると、以下のようにして左リンクを修復する。
【００７７】
(１)uはu.l:=v、u.lnum:=u.lnum.gnext()としてからvに対してSetRメッセージを送信する。SetRメッセージの引数は、rcur(=v.r)、rnew(=u)、rnewnum(=u.lnum)である。
【００７８】
(２)SetRメッセージを受信したv は、メッセージを実施形態１と同じ方法で処理する（ただしリンク番号は(g, s)形式に拡張されている）。
【００７９】
(３)uがSetRAckを受信すれば修復が完了する。SetRNakメッセージを受信した場合は
しばらく待ってgetStatメッセージの送信からやりなおす。
【００８０】
以上、本発明によれば、ノード故障がない場合、常に右リンクは正しいノードを指し、左リンクはいずれ正しいノードを指す。また左リンクは常に生きているノードを指すため、リングに挿入されているノードを検索した場合、必ず発見できる。
【００８１】
また、右方向リングに挿入（または削除）した後、左方向リングに挿入（または削除）するためにはSetLメッセージを１つ転送するだけでよいため、多数のノードが並行して挿入・削除するような状況でも効率的に挿入・削除操作を実行できる。
【００８２】
さらに、本発明では排他制御を行うノードは存在しないため、ノード障害が発生した場合にも安全にリング構造を修復可能である。
【特許請求の範囲】
【請求項１】
複数のノードを有するネットワークにおいて、第１のノードと、第１のノードの接続先である第２のノードの間に、第３のノードを挿入しようとする場合のノードの接続方法であって、
各ノードは接続先が変更された際に更新される検出情報を有し、
第３のノードが第１のノードが保持する検出情報を入手する入手ステップと、
第３のノードが第１のノードに、前記入手ステップで入手した検出情報と、第３のノードに接続するための接続先情報とを含む第１のリンク更新メッセージを送信する第１の送信ステップと、
前記第１のノードが、第１のリンク更新メッセージ受信時の第１のノードが保持する検出情報と、前記第１のリンク更新メッセージに含まれる検出情報とが一致するか否かを判定する第１の判定ステップと、
前記第１の判定ステップで一致すると判定された場合に、前記接続先情報に基づいて第１のノードが第３のノードに接続するとともに、第１のノードが保持する検出情報を異なる検出情報に更新する第１のリンク更新ステップと、
を有することを特徴とするノードの接続方法。
【請求項２】
複数のノードを有するネットワークにおいて、第４のノードが第５のノードに接続し、第５のノードが第６のノードに接続している場合に、第５のノードを削除しようとする場合のノードの接続方法であって、
各ノードは接続先が変更された際に更新される検出情報を有し、
第５のノードが第４のノードに、第４のノードが保持する検出情報と、第６のノードに接続するための接続先情報とを含む第２のリンク更新メッセージを送信する第２の送信ステップと、
前記第４のノードが、第２のリンク更新メッセージ受信時の第４のノードが保持する検出情報と、前記第２のリンク更新メッセージに含まれる検出情報とが一致するか否かを判定する第２の判定ステップと、
前記第２の判定ステップで一致すると判定された場合に、前記接続先情報に基づいて第４のノードが第６のノードに接続するとともに、第４のノードが保持する検出情報を異なる検出情報に更新する第２のリンク更新ステップと、
を有することを特徴とするノードの接続方法。
【請求項３】
第１のノードが保持する検出情報として、第１のノードの接続先を識別する接続先情報を用い、
前記第１のリンク更新ステップにおいて、第１のノードが保持する検出情報を第３のノードを識別する接続先情報に更新することを特徴とする、請求項１に記載のノードの接続方法。
【請求項４】
第４のノードが保持する検出情報として、第４のノードの接続先を識別する接続先情報を用い、
前記第２のリンク更新ステップにおいて、第４のノードが保持する検出情報を第６のノードを識別する接続先情報に更新することを特徴とする、請求項２に記載のノードの接続方法。
【請求項５】
第２のノードから第１のノードへも接続している場合において、
各ノードには、自ノード及び隣接ノードが接続先を変更した回数を示す２つのリンクバージョン情報が付与されており、
第３のノードが、第１の判定ステップにおいて一致していると判定された場合に、第１のノードに付与されている隣接ノードのリンクバージョン情報を更新した第１の更新リンクバージョン情報と、第３のノードを識別する接続先情報とを含む第３のリンク更新メッセージを第２のノードに送信する第３の送信ステップと、
第３のリンク更新メッセージを受信した第２のノードが、第２のノードが保持する自ノードのリンクバージョン情報よりも第３のリンク更新メッセージに含まれる第１の更新リンクバージョン情報が優先するか否かを判定する第３の判定ステップと、
第３のリンク更新メッセージに含まれる第１の更新リンクバージョン情報が優先すると判定した場合に、前記接続先情報に基づいて第２のノードから第３のノードへ接続するとともに、第２のノードが保持する自ノードのリンクバージョン情報を第３のリンク更新メッセージに含まれる第１の更新リンクバージョン情報に変更する第３のリンク更新ステップと、
を備える請求項１または３に記載のノードの接続方法。
【請求項６】
第６のノードから第５のノードへも接続し、第５のノードから第４のノードへも接続している場合において、
各ノードには、自ノード及び隣接ノードが接続先を変更した回数を示す２つのリンクバージョン情報が付与されており、
第５のノードが、第２の判定ステップにおいて一致していると判定された場合に、第５のノードに付与されている隣接ノードのリンクバージョン情報を更新した第２の更新リンクバージョン情報と、第４のノードを識別する接続先情報とを含む第４のリンク更新メッセージを第６のノードに送信する第４の送信ステップと、
第４のリンク更新メッセージを受信した第６のノードが、第６のノードが保持する自ノードのリンクバージョン情報よりも第４のリンク更新メッセージに含まれる第２の更新リンクバージョン情報が優先するか否かを判定する第４の判定ステップと、
第４のリンク更新メッセージに含まれる第２の更新リンクバージョン情報が優先すると判定した場合に、前記接続先情報に基づいて第６のノードから第４のノードへ接続するとともに、第６のノードが保持する自ノードのリンクバージョン情報を第４のリンク更新メッセージに含まれる第２の更新リンクバージョン情報に変更する第４のリンク更新ステップと、
を備える請求項２又は４に記載のノードの接続方法。
【請求項７】
リンクバージョン情報が数値で表される場合に、
第３及び／又は第４の判定ステップにおいて、前記数値の大小関係によりいずれを優先するかを判定する、
請求項５又は６に記載のノードの接続方法。
【請求項８】
第４と第５のノードには、他のノードから接続されている数を示す参照カウンタが付与されており、
第６のノードが第４のリンク更新メッセージを受信した場合に、第６のノードが前記第５のノードに参照カウンタを減少させる参照カウンタ減少メッセージを送信する減少メッセージ送信ステップと、
第５のノードが前記参照カウンタ減少メッセージを受信した場合に参照カウンタを減少させる参照カウンタ減少ステップと、
参照カウンタの値が基準値になったときに第５のノードを削除する削除実行ステップと、
を備えることを特徴とする請求項２、４、６、７のいずれかに記載のノードの接続方法。
【請求項９】
各ノードは接続するノードが故障した回数をカウントする隣接ノード故障カウンタを保持していて、第３のリンク更新メッセージに隣接ノード故障カウンタを含めることを特徴とする請求項５又は７に記載のノードの接続方法。
【請求項１０】
第３の判定ステップにおいて、第２のノードが保持する隣接ノード故障カウンタの値と第３のリンク更新メッセージに含まれる隣接ノード故障カウンタの値の大きい方を優先することを特徴とする請求項９に記載のノードの接続方法。
【請求項１１】
請求項１から１０のいずれかに記載のノードの接続方法を用いて、片方向リングトポロジあるいは双方向リングトポロジあるいは片方向連結リストトポロジあるいは双方向連結リストトポロジを構築することを特徴とするネットワークトポロジ構築方法。
【請求項１２】
請求項１から１０のいずれかに記載のノードの接続方法を用いて構築したネットワークシステム。
【請求項１】
複数のノードを有するネットワークにおいて、第１のノードと、第１のノードの接続先である第２のノードの間に、第３のノードを挿入しようとする場合のノードの接続方法であって、
各ノードは接続先が変更された際に更新される検出情報を有し、
第３のノードが第１のノードが保持する検出情報を入手する入手ステップと、
第３のノードが第１のノードに、前記入手ステップで入手した検出情報と、第３のノードに接続するための接続先情報とを含む第１のリンク更新メッセージを送信する第１の送信ステップと、
前記第１のノードが、第１のリンク更新メッセージ受信時の第１のノードが保持する検出情報と、前記第１のリンク更新メッセージに含まれる検出情報とが一致するか否かを判定する第１の判定ステップと、
前記第１の判定ステップで一致すると判定された場合に、前記接続先情報に基づいて第１のノードが第３のノードに接続するとともに、第１のノードが保持する検出情報を異なる検出情報に更新する第１のリンク更新ステップと、
を有することを特徴とするノードの接続方法。
【請求項２】
複数のノードを有するネットワークにおいて、第４のノードが第５のノードに接続し、第５のノードが第６のノードに接続している場合に、第５のノードを削除しようとする場合のノードの接続方法であって、
各ノードは接続先が変更された際に更新される検出情報を有し、
第５のノードが第４のノードに、第４のノードが保持する検出情報と、第６のノードに接続するための接続先情報とを含む第２のリンク更新メッセージを送信する第２の送信ステップと、
前記第４のノードが、第２のリンク更新メッセージ受信時の第４のノードが保持する検出情報と、前記第２のリンク更新メッセージに含まれる検出情報とが一致するか否かを判定する第２の判定ステップと、
前記第２の判定ステップで一致すると判定された場合に、前記接続先情報に基づいて第４のノードが第６のノードに接続するとともに、第４のノードが保持する検出情報を異なる検出情報に更新する第２のリンク更新ステップと、
を有することを特徴とするノードの接続方法。
【請求項３】
第１のノードが保持する検出情報として、第１のノードの接続先を識別する接続先情報を用い、
前記第１のリンク更新ステップにおいて、第１のノードが保持する検出情報を第３のノードを識別する接続先情報に更新することを特徴とする、請求項１に記載のノードの接続方法。
【請求項４】
第４のノードが保持する検出情報として、第４のノードの接続先を識別する接続先情報を用い、
前記第２のリンク更新ステップにおいて、第４のノードが保持する検出情報を第６のノードを識別する接続先情報に更新することを特徴とする、請求項２に記載のノードの接続方法。
【請求項５】
第２のノードから第１のノードへも接続している場合において、
各ノードには、自ノード及び隣接ノードが接続先を変更した回数を示す２つのリンクバージョン情報が付与されており、
第３のノードが、第１の判定ステップにおいて一致していると判定された場合に、第１のノードに付与されている隣接ノードのリンクバージョン情報を更新した第１の更新リンクバージョン情報と、第３のノードを識別する接続先情報とを含む第３のリンク更新メッセージを第２のノードに送信する第３の送信ステップと、
第３のリンク更新メッセージを受信した第２のノードが、第２のノードが保持する自ノードのリンクバージョン情報よりも第３のリンク更新メッセージに含まれる第１の更新リンクバージョン情報が優先するか否かを判定する第３の判定ステップと、
第３のリンク更新メッセージに含まれる第１の更新リンクバージョン情報が優先すると判定した場合に、前記接続先情報に基づいて第２のノードから第３のノードへ接続するとともに、第２のノードが保持する自ノードのリンクバージョン情報を第３のリンク更新メッセージに含まれる第１の更新リンクバージョン情報に変更する第３のリンク更新ステップと、
を備える請求項１または３に記載のノードの接続方法。
【請求項６】
第６のノードから第５のノードへも接続し、第５のノードから第４のノードへも接続している場合において、
各ノードには、自ノード及び隣接ノードが接続先を変更した回数を示す２つのリンクバージョン情報が付与されており、
第５のノードが、第２の判定ステップにおいて一致していると判定された場合に、第５のノードに付与されている隣接ノードのリンクバージョン情報を更新した第２の更新リンクバージョン情報と、第４のノードを識別する接続先情報とを含む第４のリンク更新メッセージを第６のノードに送信する第４の送信ステップと、
第４のリンク更新メッセージを受信した第６のノードが、第６のノードが保持する自ノードのリンクバージョン情報よりも第４のリンク更新メッセージに含まれる第２の更新リンクバージョン情報が優先するか否かを判定する第４の判定ステップと、
第４のリンク更新メッセージに含まれる第２の更新リンクバージョン情報が優先すると判定した場合に、前記接続先情報に基づいて第６のノードから第４のノードへ接続するとともに、第６のノードが保持する自ノードのリンクバージョン情報を第４のリンク更新メッセージに含まれる第２の更新リンクバージョン情報に変更する第４のリンク更新ステップと、
を備える請求項２又は４に記載のノードの接続方法。
【請求項７】
リンクバージョン情報が数値で表される場合に、
第３及び／又は第４の判定ステップにおいて、前記数値の大小関係によりいずれを優先するかを判定する、
請求項５又は６に記載のノードの接続方法。
【請求項８】
第４と第５のノードには、他のノードから接続されている数を示す参照カウンタが付与されており、
第６のノードが第４のリンク更新メッセージを受信した場合に、第６のノードが前記第５のノードに参照カウンタを減少させる参照カウンタ減少メッセージを送信する減少メッセージ送信ステップと、
第５のノードが前記参照カウンタ減少メッセージを受信した場合に参照カウンタを減少させる参照カウンタ減少ステップと、
参照カウンタの値が基準値になったときに第５のノードを削除する削除実行ステップと、
を備えることを特徴とする請求項２、４、６、７のいずれかに記載のノードの接続方法。
【請求項９】
各ノードは接続するノードが故障した回数をカウントする隣接ノード故障カウンタを保持していて、第３のリンク更新メッセージに隣接ノード故障カウンタを含めることを特徴とする請求項５又は７に記載のノードの接続方法。
【請求項１０】
第３の判定ステップにおいて、第２のノードが保持する隣接ノード故障カウンタの値と第３のリンク更新メッセージに含まれる隣接ノード故障カウンタの値の大きい方を優先することを特徴とする請求項９に記載のノードの接続方法。
【請求項１１】
請求項１から１０のいずれかに記載のノードの接続方法を用いて、片方向リングトポロジあるいは双方向リングトポロジあるいは片方向連結リストトポロジあるいは双方向連結リストトポロジを構築することを特徴とするネットワークトポロジ構築方法。
【請求項１２】
請求項１から１０のいずれかに記載のノードの接続方法を用いて構築したネットワークシステム。
【図１】
【図３】
【図４】
【図２】
【図３】
【図４】
【図２】
【公開番号】特開２０１２−４４２９５（Ｐ２０１２−４４２９５Ａ）
【公開日】平成２４年３月１日（２０１２．３．１）
【国際特許分類】
【出願番号】特願２０１０−１８１５８４（Ｐ２０１０−１８１５８４）
【出願日】平成２２年８月１６日（２０１０．８．１６）
【出願人】（５０６１２２３２７）公立大学法人大阪市立大学 (122)
【出願人】（５１０２２２４５３）株式会社 ビービーアール (1)
【Ｆターム（参考）】
【公開日】平成２４年３月１日（２０１２．３．１）
【国際特許分類】
【出願日】平成２２年８月１６日（２０１０．８．１６）
【出願人】（５０６１２２３２７）公立大学法人大阪市立大学 (122)
【出願人】（５１０２２２４５３）株式会社 ビービーアール (1)
【Ｆターム（参考）】
[ Back to top ]