(57)【要約】  メッセージ通信バッファのサイズに依存することなくデッドロックを防止する。データ転送装置は、第１のアドレス宛のデータを受信すると、ルーティングテーブルに基づいて、該データの転送先となる他のデータ転送装置を決定し、自装置の識別子と、該他のデータ転送装置の識別子との大小関係が一方の関係である場合は、該データを該他のデータ転送装置の第１のアドレス宛に送信し、大小関係が他方の関係である場合は、該データを該他のデータ転送装置の第２のアドレス宛に送信し、自装置の第２のアドレス宛のデータを受信すると、ルーティングテーブルに基づいて、該データの転送先となる他のデータ転送装置を決定し、該データを該他のデータ転送装置の第２のアドレス宛に送信する。
2012133211.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークを介して接続された少なくとも１つの他のデータ転送装置の、識別子、第１のアドレス、及び第２のアドレスを含む、ルーティングテーブルを記憶するルーティングテーブル記憶部と、
自装置の第１のアドレス宛のデータを受信すると、該データから算出されるキーと、前記ルーティングテーブルに含まれる少なくとも１つの他のデータ転送装置の識別子との関係に基づいて、該データの転送先となる他のデータ転送装置を決定し、
自装置の識別子と、該他のデータ転送装置の識別子との大小関係が一方の関係である場合は、該データを該他のデータ転送装置の第１のアドレス宛に送信し、前記大小関係が他方の関係である場合は、該データを該他のデータ転送装置の第２のアドレス宛に送信する、
第１転送部と、
自装置の第２のアドレス宛のデータを受信すると、該データのキーと、前記ルーティングテーブルに含まれる少なくとも１つの他のデータ転送装置の識別子との関係に基づいて、該データの転送先となる他のデータ転送装置を決定し、
該データを該他のデータ転送装置の第２のアドレス宛に送信する、
第２転送部と、
を備えるデータ転送装置。
【請求項２】
請求項１に記載のデータ転送装置であって、
前記第１及び第２転送部は、
前記データのキーと自装置の識別子とが所定の関係にある場合は、該データの転送先をデータ受信装置と決定する、
データ転送装置。
【請求項３】
請求項２に記載のデータ転送装置であって、
前記第１及び第２転送部は、
自装置が前記データのキー（ｍビット）からの２ｍを法とする剰余環における距離が最も小さい識別子を有する場合、前記データ受信装置を転送先として決定する、
データ転送装置。
【請求項４】
請求項１〜３の何れか一項に記載のデータ転送装置であって、
前記第１及び第２転送部は、
前記ルーティングテーブルに含まれる少なくとも１つの他のデータ転送装置の中に、該データ転送装置の識別子から前記データのキーまでの距離が自装置の識別子からの距離よりも小さいデータ転送装置が存在する場合は、該距離が最小であるデータ転送装置を転送先として決定し、
自装置の識別子から前記データのキーまでの距離が最も小さい場合は、該データ転送装置の識別子からの距離が最も小さい識別子を有するデータ転送装置を転送先として決定する、
データ転送装置。
【請求項５】
請求項１〜４の何れか一項に記載のデータ転送装置であって、
他のデータ転送装置に対して、自装置の識別子、第１のアドレス、及び第２のアドレスを、該他のデータ転送装置のルーティングテーブルを更新するために送信し、
他のデータ転送装置から、該他のデータ転送装置の識別子、第１のアドレス、及び第２のアドレスを受信すると、ルーティングテーブル内の該他のデータ転送装置の識別子で特定されるレコードを、第１のアドレス、及び第２のアドレスを受信した第１のアドレス、及び第２のアドレスに更新する、
ルーティングテーブル管理部を
さらに備えるデータ転送装置。
【請求項６】
請求項５に記載のデータ転送装置であって、
自装置の識別子からの距離が最も大きいデータ転送装置の識別子、第１のアドレス、及び第２のアドレスを記憶するプレディセッサ記憶部をさらに備え、
前記ルーティングテーブル管理部は、
自装置の識別子からの距離が最も小さい識別子を有する他のデータ転送装置のプレディセッサ記憶部を更新するために、自装置の識別子、第１のアドレス、及び第２のアドレスを該他のデータ転送装置に送信し、
該他のデータ転送装置から、該他のデータ転送装置のプレディセッサ記憶部に記憶されている識別子、第１のアドレス、及び第２のアドレスを取得して、自装置のプレディセッサ記憶部に記憶する、
データ転送装置。
【請求項７】
請求項５または６に記載のデータ転送装置であって、
前記ルーティングテーブル管理部は、自装置の識別子からの２ｍを法とする剰余環における距離が２ｉ−１（ｉ＝１，２，・・・，ｍ）であるキー（ｍビット）を算出し、該キーからの距離が最も小さい識別子を有するデータ転送装置の識別子、第１のアドレス、及び第２のアドレスを、該キーと対応づけて、前記ルーティングテーブルに記憶する、
データ転送装置。
【請求項８】
請求項７に記載のデータ転送装置であって、
前記ルーティングテーブル管理部は、他のデータ転送装置の識別子からの距離が２ｉ−１であるキーについて、該キーからの距離が最小であるデータ転送装置が自装置である場合に、該他のデータ転送装置に対して、該他のデータ転送装置のルーティングテーブルを更新するために、自装置の識別子、第１のアドレス、及び第２のアドレスを送信する、
データ転送装置。
【請求項９】
請求項１〜８の何れか一項に記載のデータ転送装置であって、
自装置の第１のアドレス宛で受信されたデータが一時的に格納される第１の受信キューと、
自装置の第２のアドレス宛で受信されたデータが一時的に格納される第２の受信キューと、
他のデータ転送装置の第１のアドレスごとのキューを有する第１の送信キューと、
他のデータ転送装置の第２のアドレスごとのキューを有する第２の送信キューと、
をさらに備え、
前記第１転送部は、
前記第１の受信キューに格納されているデータを前記他のデータ転送装置の第１のアドレス宛に送信する際は、前記第１の送信キューの中の、該第１のアドレスに対応するキューに該データを挿入し、
前記第１の受信キューに格納されているデータを前記他のデータ転送装置の第２のアドレス宛に送信する際は、前記第２の送信キューの中の、該第２のアドレスに対応するキューに該データを挿入し、
前記第２転送部は、
前記第２の受信キューに格納されているデータを前記他のデータ転送装置の第２のアドレス宛に送信する際は、前記第２の送信キューの中の、該第２のアドレスに対応するキューに該データを挿入する、
データ転送装置。
【請求項１０】
ネットワークを介して接続される複数のデータ転送装置を含むデータ配信システムにおける各データ転送装置が、
少なくとも１つの他のデータ転送装置の、識別子、第１のアドレス、及び第２のアドレスを含む、ルーティングテーブルを記憶し、
自装置の第１のアドレス宛のデータを受信すると、
該データから算出されるキーと、前記ルーティングテーブルに含まれる少なくとも１つの他のデータ転送装置の識別子との関係に基づいて、データ受信装置または他のデータ転送装置を該データの転送先として決定し、
データ受信装置が転送先として決定されると、該データ受信装置に該データを送信し、
他のデータ転送装置が転送先として決定されると、自装置の識別子と、該他のデータ転送装置の識別子との大小関係が一方の関係である場合は、該データを該他のデータ転送装置の第１のアドレス宛に送信し、前記大小関係が他方の関係である場合は、該データを該他のデータ転送装置の第２のアドレス宛に送信し、
自装置の第２のアドレス宛のデータを受信すると、
該データから算出されるキーと、前記ルーティングテーブルに含まれる少なくとも１つの他のデータ転送装置の識別子との関係に基づいて、データ受信装置または他のデータ転送装置を該データの転送先として決定し、
データ受信装置が転送先として決定されると、該データ受信装置に該データを送信し、
他のデータ転送装置が転送先として決定されると、該データを該他のデータ転送装置の第２のアドレス宛に送信する、
データ転送方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ転送装置及びデータ転送方法に関する。
【背景技術】
【０００２】
近年、ノード間で高速にデータを転送するためのネットワークとして、構造化Ｐ２Ｐ（Peer to Peer）ネットワークが注目されている。このような構造化Ｐ２Ｐネットワークを利用したデータ配信システムでは、複数のデータ転送装置が相互に連携することにより、大量のデータの高速配信が実現されている。配信対象のデータは、データ送信装置からデータ配信システムを構成するいずれかのデータ転送装置に入力され、該データ転送装置、あるいは、別のデータ転送装置からデータ受信装置に配信される。【０００３】
このようなデータ配信システムでは、各データ転送装置は、ＬＡＮ（Local Area Network）ケーブルなどの伝送媒体によって接続されるネットワークを介して、他のデータ転送装置と通信することができる。また、複数のデータ送信装置は、ネットワークを介して、任意のデータ転送装置にデータを送信可能である。データ配信システムでは、データ転送装置同士が連携して、データ送信装置から受信したデータを、そのデータを処理すべきデータ受信装置へ配信する。そのために、データ転送装置は、他のいくつかのデータ転送装置のアドレスを記憶しておき、最終的にデータを処理すべきデータ受信装置に該データが到達するように、所定の手順に従って、記憶しているアドレス群の中から該データの転送先のアドレスを決定する。【０００４】
非特許文献１に開示されているシステムでは、各ノード（データ転送装置）のＩＤはｍビット長の値（キー）となっている。データ転送装置は、データ送信装置、あるいは他のデータ転送装置から受信したデータを、そのデータのハッシュ値（キー）のサクセッサへ転送する。ここで、キーｋのサクセッサとは、データ配信システムを構成するデータ転送装置のうち、キーｋからの距離が最も小さいキーをＩＤとするデータ転送装置のことである。【０００５】
非特許文献１では、図２６に示すように、キー（ｍビット）は２ｍを法とする剰余環で表され、任意のキーｋからの距離がｄであるキーは、（ｋ＋ｄ）  ｍｏｄ  ２mとなる。図２６の例では、ｍ＝３であり、キー７から距離が２であるキーは、（７＋２）  ｍｏｄ  ２3＝１となる。【０００６】
非特許文献１に開示されているシステムでは、データ転送装置は、データを他のデータ転送装置に転送するために、他のいくつかのデータ転送装置のアドレスを保持している。それらのアドレスは、該データ転送装置のＩＤからの距離が２i-1（ｉ＝１，２，…，ｍ）であるキーｓ（基点キー）のサクセッサのアドレスである。図２６に示す例では、ＩＤが０のデータ転送装置について、ｉ＝１の場合の基点キーは０＋２1-1＝１（ｍｏｄ  ２3）となり、そのサクセッサはＩＤが１のデータ転送装置となる。また、ｉ＝２の場合の基点キーは０＋２2-1＝２（ｍｏｄ  ２3）となり、そのサクセッサはＩＤが３のデータ転送装置となる。【０００７】
図２７は、図２６の３つのデータ転送装置の内部構成の一例とデータの流れを示したものである。データ転送装置０，１，３は、それぞれ、ＩＤが０，１，３であるデータ転送装置である。データ転送装置は、他の装置から受信したデータを一時的に保持する受信キューと、受信キューからデータを取り出して、転送先の装置を決定する転送部と、他の装置へ送信するデータを一時的に保持する送信キューとを含んでいる。図２７において、矢印はデータの流れを表している。例えば、データ転送装置０からデータ転送装置１へのデータの流れは、図２７において、データ転送装置０の送信キューｓ０−３からデータ転送装置１の受信キューｒ１−１への矢印で表されている。【０００８】
図２７の構成において、データ転送装置の送信キューや受信キューがいっぱいになった場合、その前段にある処理を一時的に停止させるなどのバックプレッシャーがかかることにより、キューからデータがあふれることが防止される。送信キューの前段は転送部であり、受信キューの前段はデータ送信装置、あるいは、他のデータ転送装置の送信キューである。また、送信キューからバックプレッシャーをかけられた転送部は、データの転送先を判定しても、そのデータをその送信キューに挿入できないため、その送信キューに空きができるまで、受信キューからデータを取りださないこととなる。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】Ion Stoica、他3名、「Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications」、ACM SIGCOMM Computer Communication Review 31(4)、米国、ACM Press、2001年、p. 149-160
【特許文献】
【００１０】
【特許文献１】特開２００７−３２８８１３号公報
【発明の概要】
【発明が解決しようとする課題】
【００１１】
ところで、図２７に示す構成では、データの流れが環状になっている部分でデッドロックとなる可能性がある。例えば、データ転送装置０の転送部から送信キューｓ０−３へのデータフロー、送信キューｓ０−３から受信キューｒ１−１へのデータフロー、受信キューｒ１−１からデータ転送装置１の転送部へのデータフロー、データ転送装置１の転送部から送信キューｓ１−１へのデータフロー、送信キューｓ１−１から受信キューｒ０−３へのデータフロー、受信キューｒ０−３からデータ転送装置０の転送部へのデータフローの６つで環が構成されている。【００１２】
デッドロックとなる例を説明する。データ送信装置からデータ転送装置０へ大量のデータが入力されているものとする。例えば、データ転送装置０の転送部は、データ送信装置から受信したデータをデータ転送装置１へ転送すると判定し、そのデータを送信キューｓ０−３へ挿入する。ここで、データ転送装置０がデータ転送装置１へデータを送信するために送信キューｓ０−３からデータを取り出す処理が、データ転送装置０の転送部から送信キューｓ０−３へ挿入する処理よりも遅く、送信キューｓ０−３がデータでいっぱいになったとする。そうすると、送信キューから転送部にバックプレッシャーがかかり、転送部は受信キューからデータを取り出さなくなる。すると、データ転送装置１から受信したデータを保持する受信キューｒ０−３がいっぱいになり、データ転送装置０からデータ転送装置１にバックプレッシャーがかかることとなる。【００１３】
一方、データ送信装置からデータ転送装置１へ大量のデータが入力されているものとする。例えば、データ転送装置１の転送部は、データ送信装置から受信したデータをデータ転送装置０へ転送すると判定し、そのデータを送信キューｓ１−１へ挿入する。その場合、データ転送装置０の場合と同様に、受信キューｒ１−１がデータでいっぱいになり、データ転送装置１からデータ転送装置０にバックプレッシャーがかかることとなる。このような状況では、データ転送装置０とデータ転送装置１とが互いにバックプレッシャーを掛け合い、両データ転送装置がデータを送信できない状態に固定されてしまう。すなわち、デッドロック状態が発生することとなる。【００１４】
このようなデッドロックを回避する手法の一例が、特許文献１に開示されている。特許文献１に開示されている手法では、データ転送装置に相当するノードが常に入力メッセージを処理可能とするために十分な大きさのメッセージ通信バッファが確保され、これにより、デッドロックを回避可能としている。これは、図２７における送信キューや受信キューのサイズを大きくすることに相当する。つまり、データがいっぱいになることがないように、送信キューや受信キューのサイズを十分に大きくすることで、その前段の処理装置、あるいは処理部に対してバックプレッシャーをかける必要がなくなり、デッドロックを回避することができる。【００１５】
しかしながら、特許文献１に開示されている手法では、メッセージ通信バッファのサイズは、未処理のまま保持する可能性のあるメッセージの個数に比例する。そのため、未処理のまま保持する可能性のあるメッセージの個数が非常に大きい場合には、メッセージ通信バッファのサイズを非常に大きくする必要があり、メモリリソース利用効率の観点から効率的でない。また、未処理のまま保持する可能性のあるメッセージの個数を特定できない場合には、メッセージ通信バッファのための領域を無限に用意する必要があり、現実的でない。【００１６】
本発明はこのような事情に鑑みてなされたものであり、構造化Ｐ２Ｐネットワークにおいて、メッセージ通信バッファのサイズに依存することなく、つまり、大きなサイズのメッセージ通信バッファを確保することなくデッドロックを防止することを目的とする。
【課題を解決するための手段】
【００１７】
本発明の一側面に係るデータ転送装置は、ネットワークを介して接続された少なくとも１つの他のデータ転送装置の、識別子、第１のアドレス、及び第２のアドレスを含む、ルーティングテーブルを記憶するルーティングテーブル記憶部と、自装置の第１のアドレス宛のデータを受信すると、該データから算出されるキーと、ルーティングテーブルに含まれる少なくとも１つの他のデータ転送装置の識別子との関係に基づいて、該データの転送先となる他のデータ転送装置を決定し、自装置の識別子と、該他のデータ転送装置の識別子との大小関係が一方の関係である場合は、該データを該他のデータ転送装置の第１のアドレス宛に送信し、大小関係が他方の関係である場合は、該データを該他のデータ転送装置の第２のアドレス宛に送信する、第１転送部と、自装置の第２のアドレス宛のデータを受信すると、該データのキーと、ルーティングテーブルに含まれる少なくとも１つの他のデータ転送装置の識別子との関係に基づいて、該データの転送先となる他のデータ転送装置を決定し、該データを該他のデータ転送装置の第２のアドレス宛に送信する、第２転送部と、を備える。【００１８】
また、本発明の一側面に係るデータ転送方法では、ネットワークを介して接続される複数のデータ転送装置を含むデータ配信システムにおける各データ転送装置が、少なくとも１つの他のデータ転送装置の、識別子、第１のアドレス、及び第２のアドレスを含む、ルーティングテーブルを記憶し、自装置の第１のアドレス宛のデータを受信すると、該データから算出されるキーと、ルーティングテーブルに含まれる少なくとも１つの他のデータ転送装置の識別子との関係に基づいて、データ受信装置または他のデータ転送装置を該データの転送先として決定し、データ受信装置が転送先として決定されると、該データ受信装置に該データを送信し、他のデータ転送装置が転送先として決定されると、自装置の識別子と、該他のデータ転送装置の識別子との大小関係が一方の関係である場合は、該データを該他のデータ転送装置の第１のアドレス宛に送信し、大小関係が他方の関係である場合は、該データを該他のデータ転送装置の第２のアドレス宛に送信し、自装置の第２のアドレス宛のデータを受信すると、該データから算出されるキーと、ルーティングテーブルに含まれる少なくとも１つの他のデータ転送装置の識別子との関係に基づいて、データ受信装置または他のデータ転送装置を該データの転送先として決定し、データ受信装置が転送先として決定されると、該データ受信装置に該データを送信し、他のデータ転送装置が転送先として決定されると、該データを該他のデータ転送装置の第２のアドレス宛に送信する。【００１９】
なお、本発明において、「部」とは、単に物理的手段を意味するものではなく、その「部」が有する機能をソフトウェアによって実現する場合も含む。また、１つの「部」や装置が有する機能が２つ以上の物理的手段や装置により実現されても、２つ以上の「部」や装置の機能が１つの物理的手段や装置により実現されても良い。
【発明の効果】
【００２０】
本発明によれば、構造化Ｐ２Ｐネットワークにおいて、メッセージ通信バッファのサイズに依存することなく、つまり、大きなサイズのメッセージ通信バッファを確保することなくデッドロックを防止することができる。
【図面の簡単な説明】
【００２１】
【図１】本発明の一実施形態であるデータ配信システムの全体構成を示す図である。
【図２】データ転送装置の構成の一例を示す図である。
【図３】ルーティングテーブルの構造の一例を示す図である。
【図４】プレディセッサ記憶部の構造の一例を示す図である。
【図５】データ転送装置の内部構成とデータの流れの一例を示す図である。
【図６】データ配信システムにおける環の構成の一例を示す図である。
【図７】データ配信システムの仮想的な構成の一例を示す図である。
【図８】第１転送部におけるデータ転送処理の一例を示すフローチャートである。
【図９】転送先データ転送装置の検索処理の一例を示すフローチャートである。
【図１０】第２転送部におけるデータ転送処理の一例を示すフローチャートである。
【図１１】ルーティングテーブルを生成・管理する処理の一例を示すフローチャートである。
【図１２】ルーティングテーブルの初期化処理の一例を示すフローチャートである。
【図１３】サクセッサ・プレディセッサの初期化処理の一例を示すフローチャートである。
【図１４】他のデータ転送装置のルーティングテーブルの更新処理の一例を示すフローチャートである。
【図１５】他のデータ転送装置において実行されるルーティングテーブル更新処理の一例を示すフローチャートである。
【図１６】データ配信システムに追加されるデータ転送装置の順序の一例を示す図である。
【図１７】ルーティングテーブルの状態の一例を示す図である。
【図１８】プレディセッサ記憶部の状態の一例を示す図である。
【図１９】ルーティングテーブルの状態の一例を示す図である。
【図２０】プレディセッサ記憶部の状態の一例を示す図である。
【図２１】プレディセッサ記憶部の状態の一例を示す図である。
【図２２】ルーティングテーブルの状態の一例を示す図である。
【図２３】ルーティングテーブルの状態の一例を示す図である。
【図２４】ルーティングテーブルの状態の一例を示す図である。
【図２５】ルーティングテーブル及びプレディセッサ記憶部の状態の一例を示す図である。
【図２６】データ配信システムにおける環の構成の一例を示す図である。
【図２７】データ転送装置の内部構成とデータの流れの一例を示す図である。
【発明を実施するための形態】
【００２２】
以下、図面を参照して本発明の一実施形態について説明する。
【００２３】
＝＝構成＝＝
図１は、本発明の一実施形態であるデータ配信システムの全体構成を示す図である。データ配信システム１０は、複数のデータ転送装置２０を含んで構成されている。各データ転送装置２０は、ＬＡＮ（Local Area Network）やインターネット等のネットワーク２２を介して相互に通信可能に接続されている。データ配信システム１０では、複数のデータ転送装置２０が連携して、データ送信装置２４から受信したデータを、そのデータを処理すべきデータ受信装置２６へ配信する。
【００２４】
図２は、データ転送装置２０の構成の一例を示す図である。データ転送装置２０は、第１及び第２受信キュー４０，４２、第１及び第２送信キュー４４，４６、第１及び第２転送部５０，５２、ルーティングテーブル管理部６０、ルーティングテーブル記憶部６２、プレディセッサ記憶部６４、及び自装置情報記憶部６６を含んで構成されている。なお、データ転送装置２０は、１台または複数台の情報処理装置を用いて実現することができる。そして、第１及び第２受信キュー４０，４２、第１及び第２送信キュー４４，４６、第１及び第２転送部５０，５２、ルーティングテーブル管理部６０、ルーティングテーブル記憶部６２、プレディセッサ記憶部６４、及び自装置情報記憶部６６は、メモリや記憶装置等の記憶領域を用いたり、該記憶領域に記憶されているプログラムをプロセッサが実行したりすることにより実現することができる。
【００２５】
第１及び第２受信キュー４０，４２は、データ送信装置や他のデータ転送装置から受信するデータを一時的に保持しておくためのメモリ領域を有する。なお、データ転送装置２０は、第１のアドレス及び第２のアドレスを有しており、第１のアドレス宛に送信されたデータが第１受信キュー４０に格納され、第２のアドレス宛に送信されたデータが第２受信キュー４２に格納される。
【００２６】
第１及び第２送信キュー４４，４６は、他のデータ転送装置やデータ受信装置へ送信するデータを一時的に保持しておくためのメモリ領域を有する。なお、第１及び第２送信キュー４４，４６に格納されたデータは、第１転送部５０または第２転送部５２により決定された転送先へと順次送信される。
【００２７】
第１転送部５０は、第１受信キュー４０からデータを取り出し、ルーティングテーブル記憶部６２に格納されているルーティングテーブルに基づいて該データの転送先となる他のデータ転送装置またはデータ受信装置を決定し、決定された転送先に該データを送信するための送信キューに該データを転送する。同様に、第２転送部５２は、第２受信キュー４２からデータを取り出して、該データの転送先をルーティングテーブルに基づいて決定し、決定された転送先に該データを送信するための送信キューに該データを転送する。なお、本実施形態では、第１及び第２転送部５０，５２は、データのハッシュ値をキーとしてルーティングテーブルを検索することにより、転送先を決定することができる。
【００２８】
ルーティングテーブル管理部６０は、データ転送装置２０がデータ配信システム１０に追加される際にルーティングテーブルを生成し、ルーティングテーブル記憶部６２に格納する。また、ルーティングテーブル管理部６０は、他のデータ転送装置がデータ配信システム１０に追加されるなど、データ配信システム１０の構成に変更があった場合に、その変更内容に応じてルーティングテーブルを更新する。図３には、ルーティングテーブルの構造の一例が示されている。図３に示すように、ルーティングテーブルは複数のレコードから構成され、各レコードは、データ転送装置を特定するための基点となるキーである基点キーと、基点キーのサクセッサのＩＤと、該サクセッサの第１及び第２のアドレスとを含んでいる。ここでのアドレスとは、ネットワークに接続される装置を特定する情報であり、例えば、ＴＣＰ／ＩＰであれば、ＩＰアドレス及びポートのペアをアドレスとして用いることができる。また、キーｋのサクセッサとは、データ配信システム１０を構成するデータ転送装置のうち、キーｋ（ｍビット）からの２ｍを法とする剰余環における距離が最も小さいキーをＩＤとするデータ転送装置のことである。なお、キーｋと同じＩＤを有するデータ転送装置が存在する場合、このデータ転送装置はキーｋからの距離が「０」となり、キーｋのサクセッサとなる。
【００２９】
また、ルーティングテーブル管理部６０は、データ転送装置２０のプレディセッサのＩＤと、該プレディセッサの第１及び第２のアドレスとを、プレディセッサ記憶部６４に格納する。ここで、プレディセッサとは、データ配信システム１０において、データ転送装置２０のＩＤからの距離が最も大きいキーをＩＤとする他のデータ転送装置である。図４には、プレディセッサ記憶部６４の構造の一例が示されている。
【００３０】
図２に戻り、自装置情報記憶部６６には、データ転送装置２０（自装置）のＩＤと、第１及び第２のアドレスとが記憶される。
【００３１】
図５は、３つのデータ転送装置の内部構成とデータの流れの一例を示す図である。本実施形態では、ＩＤが０，１，３のデータ転送装置２０を、データ転送装置０，１，３と表すこととする。本実施形態では、各データ転送装置２０は、第１及び第２のアドレスを持っており、第１のアドレスで受信したデータを第１受信キュー４０に挿入し、第２のアドレスで受信したデータを第２受信キュー４２に挿入する。
【００３２】
第１受信キュー４０でデータを受信したデータ受信装置２０は、第１転送部５０において、受信したデータの転送先を決定し、第１送信キュー４４内の該転送先に対応する送信キューにデータを挿入する。例えば、データ転送装置０の第１転送部によって決定された転送先がデータ転送装置１の場合、第１送信キュー４４内のデータ転送装置１に対応する送信キューｓ０−３に挿入される。
【００３３】
各データ転送装置２０は、自装置のＩＤを自装置情報記憶部６６に保持しており、第１受信キュー４０で受信したデータを転送するとき、例えば、転送先のデータ転送装置のＩＤが、自装置のＩＤよりも大きい（大小関係が一方の関係である）場合には、転送先の第１のアドレス宛にデータを送信する。一方、各データ転送装置２０は、例えば、転送先のデータ転送装置のＩＤが、自装置のＩＤよりも小さい（大小関係が他方の関係である）場合には、転送先の第２のアドレス宛にデータを送信する。また、各データ転送装置２０は、第２受信キュー４２で受信したデータを他のデータ転送装置に転送するときには、転送先の第２のアドレス宛にデータを送信する。
【００３４】
第１転送部５０または第２転送部５２は、決定した転送先がデータ受信装置であれば、第２送信キュー４６内の、データ受信装置に対応する送信キューにデータを挿入し、データ受信装置に該データを送信する。ただし、ＩＤが最も大きいデータ転送装置（図５の例ではデータ転送装置３）では、データ受信装置に転送するデータであっても第１送信キュー４４に挿入される。
【００３５】
上述した本実施形態のデータ配信システム１０は、構造化Ｐ２Ｐネットワークにおける、次の２つの特徴を利用したものである。１つ目の特徴は、データ転送装置が環状に順序付けられており、その順にデータが転送されることである。なお、ルーティングプロトコルによっては、順序付けられているデータ転送装置のいくつかをスキップして、データが転送される。２つ目の特徴は、データは一周以上、転送されることはないことである。
【００３６】
１つ目の特徴について、図２６の例では、データ転送装置０、データ転送装置１、データ転送装置３、データ転送装置０、・・・の順にデータ転送装置は環状に順序付けられている。データ転送装置０は、次のデータ転送装置であるデータ転送装置１に転送したり、データ転送装置１をスキップしてデータ転送装置３に転送したりする。２つ目の特徴について、データ送信装置からデータを受信したデータ転送装置０がデータ転送装置１にデータを送信した場合、データ転送装置１は受信したデータをデータ転送装置３に転送するかもしれないが、データ転送装置０に転送することはない。これは、データ転送装置０、データ転送装置１、データ転送装置３の順にデータが転送される過程で、必ずそのデータを担当するデータ転送装置に到達するためである。
【００３７】
本実施形態では、上記２つの特徴を考慮し、図２６の環を図６に示すように環２周分の線と見なすことにより、デッドロックを防止可能としている。ここで、図６に示す環２周分の線は、図７のように示すことができる。図７の各データ転送装置は仮想的なものであり、データ転送装置０’とデータ転送装置０’’の実体はデータ転送装置０、データ転送装置１’とデータ転送装置１’’の実体はデータ転送装置１、データ転送装置３’の実体はデータ転送装置３である。また、図７において、矢印はデータフローを表している。図７の構成により、データがデータ送信装置からデータ転送装置に送信されてから、データ受信装置に到達するまでのどのような経路もサポートすることができる。例えば、図６において、キーが１であるデータがデータ送信装置からデータ転送装置３に送信されると、該データは、データ転送装置０、データ転送装置１の順に転送され、データ転送装置１からデータ受信装置へ通知されることとなる。そのデータフローは、図７において、データ転送装置３’、データ転送装置０’’、データ転送装置１’’のフローとなる。図７では、データ転送装置０’，１’，３’とデータ転送装置０’’，１’’をそれぞれ第１のアドレスを持つデータ転送装置、第２のアドレスを持つデータ転送装置と見なすことができる。
【００３８】
＝＝処理＝＝
次に、データ配信システム１０における処理の一例について説明する。まず、第１及び第２転送部５０，５２におけるデータ転送処理について説明する。
【００３９】
図８は、第１転送部５０におけるデータ転送処理の一例を示すフローチャートである。まず、第１転送部５０は、第１受信キュー４０からキーｋとデータを取り出し（Ｓ０８０１）、本データ転送装置がキーｋのサクセッサであるかどうか判定する（Ｓ０８０２）。具体的には、キーｋがプレディセッサ記憶部６４に記憶されるプレディセッサのＩＤではなく、かつ、該ＩＤからキーｋまでの距離が、該ＩＤから本データ転送装置のＩＤまでの距離よりも小さい場合に、本データ転送装置がｋのサクセッサとなる。なお、第１受信キュー４０にキーｋが格納されていない場合、第１転送部５０は、第１受信キュー４０から取り出したデータを例えばハッシュ関数に代入することにより、キーｋを得ることができる。
【００４０】
本データ転送装置がキーｋのサクセッサである場合（Ｓ０８０２：Ｙｅｓ）、第１転送部５０は、データ受信装置に転送するデータを保持する、第２送信キュー４６内のキューにキーｋとデータを挿入する（Ｓ０８０３）。
【００４１】
本データ転送装置がキーｋのサクセッサではない場合（Ｓ０８０２：Ｎｏ）、第１転送部５０は、受信したキーｋとデータの転送先のデータ転送装置である転送先データ転送装置をルーティングテーブルから検索するための検索処理を実行する（Ｓ０８０４）。この検索処理により、転送先データ転送装置のＩＤを含むレコードが特定される。以降、特定された該レコードのＩＤ、第１のアドレス、及び第２のアドレスを、それぞれ、転送先データ転送装置のＩＤ、第１のアドレス、及び第２のアドレスとも呼ぶ。
【００４２】
転送先データ転送装置が検索されると、第１転送部５０は、転送先データ転送装置のＩＤが本データ転送装置のＩＤより大きいかどうか判定する（Ｓ０８０５）。転送先データ転送装置のＩＤが本データ転送装置のＩＤより大きい（大小関係が一方の関係である）場合（Ｓ０８０５：Ｙｅｓ）、第１転送部５０は、転送先データ転送装置の第１のアドレス宛のデータを保持する、第１送信キュー４４内のキューにキーｋとデータを挿入する（Ｓ０８０６）。一方、転送先データ転送装置のＩＤが本データ転送装置のＩＤより小さい（大小関係が他方の関係である）場合（Ｓ０８０５：Ｎｏ）、第１転送部５０は、転送先データ転送装置の第２のアドレス宛のデータを保持する、第１送信キュー４４内のキューにキーｋとデータを挿入する（Ｓ０８０７）。
【００４３】
図９は、転送先データ転送装置の検索処理の一例を示すフローチャートである。第１転送部５０は、ルーティングテーブルに登録されている他のデータ転送装置のうち、キーｋまでの距離が最も小さいＩＤを有するデータ転送装置を検索する（Ｓ０９０１）。この条件に合致するデータ転送装置がルーティングテーブルに登録されていない場合（Ｓ０９０２：Ｎｏ）、第１転送部５０は、本データ転送装置のサクセッサを転送先データ転送装置と決定する（Ｓ０９０３）。一方、この条件に合致するデータ転送装置がルーティングテーブルに登録されている場合（Ｓ０９０２：Ｙｅｓ）、第１転送部５０は、該データ転送装置を転送先データ転送装置と決定する（Ｓ０９０４）。
【００４４】
図１０は、第２転送部５２におけるデータ転送処理の一例を示すフローチャートである。まず、第２転送部５２は、第２受信キュー４２からキーｋとデータを取り出し（Ｓ１００１）、本データ転送装置がキーｋのサクセッサであるかどうか判定する（Ｓ１００２）。
【００４５】
本データ転送装置がキーｋのサクセッサである場合（Ｓ１００２：Ｙｅｓ）、第２転送部５２は、データ受信装置に転送するデータを保持する、第２送信キュー４６内のキューにキーｋとデータを挿入する（Ｓ１００３）。
【００４６】
本データ転送装置がキーｋのサクセッサではない場合（Ｓ１００２：Ｎｏ）、第２転送部５２は、受信したキーｋとデータの転送先のデータ転送装置である転送先データ転送装置をルーティングテーブルから検索するための検索処理を実行する（Ｓ１００４）。この検索処理は、第１転送部５０における検索処理（Ｓ０８０４）と同様である。
【００４７】
転送先データ転送装置が検索されると、第２転送部５２は、転送先データ転送装置の第２のアドレス宛のデータを保持する、第２送信キュー４６内のキューにキーｋとデータを挿入する（Ｓ１００５）。
【００４８】
次に、ルーティングテーブルの生成・管理処理について説明する。図１１は、ルーティングテーブルを生成・管理する処理の一例を示すフローチャートである。まず、ルーティングテーブル管理部６０は、本データ転送装置のＩＤ＝ｋ、第１のアドレスａ、第２のアドレスａ’を自装置情報記憶部６６から取得する（Ｓ１１０１）。また、ルーティングテーブル管理部６０は、本データ転送装置がデータ配信システム１０における最初のデータ転送装置であるかどうか判定し、最初のデータ転送装置でない場合は、データ配信システムを構成するいずれかのデータ転送装置の第１のアドレスａeを取得する（Ｓ１１０１）。
【００４９】
なお、本データ転送装置がデータ配信システム１０における最初のデータ転送装置であるかどうかの判定は、例えば、データ配信システム１０を構成するデータ転送装置に関する情報を、データ配信システム１０内の所定の記憶部に格納しておくことにより実現することができる。また、例えば、データ配信システム１０内において、他のデータ転送装置の有無を確認するための所定のメッセージを送信することによって判定することも可能である。
【００５０】
本データ転送装置がデータ配信システム１０における最初のデータ転送装置である場合（Ｓ１１０２：Ｙｅｓ）、ルーティングテーブル管理部６０は、プレディセッサ記憶部６４にｋ、ａ、ａ’を記憶する（Ｓ１１０３）。そして、ルーティングテーブル管理部６０は、ｉ＝１からｍまで、基点キー、ＩＤ、第１のアドレス、第２のアドレスを、それぞれ、ｋからの距離が２i-1であるキー、ｋ、ａ、ａ’とするレコードをルーティングテーブルに登録する（Ｓ１１０４，Ｓ１１０５）。なお、ｍはキーのビット数である。
【００５１】
本データ転送装置がデータ配信システム１０における最初のデータ転送装置ではない場合（Ｓ１１０２：Ｎｏ）、ルーティングテーブル管理部６０は、ルーティングテーブルの初期化処理を実行し（Ｓ１１０６）、他のデータ転送装置のルーティングテーブルの更新処理を実行する（Ｓ１１０７）。
【００５２】
図１２は、ルーティングテーブルの初期化処理の一例を示すフローチャートである。まず、ルーティングテーブル管理部６０は、サクセッサ・プレディセッサの初期化処理を実行する（Ｓ１２０１）。そして、ルーティングテーブル管理部６０は、ｉ＝２からｍまで、以下の処理（Ｓ１２０３〜Ｓ１２０６）を実行する（Ｓ１２０２）。
【００５３】
ルーティングテーブル管理部６０は、ｋからの距離が２i-1であるキーを基点キーｓiとし（Ｓ１２０３）、ａeで識別されるデータ転送装置にｓiのサクセッサのＩＤとアドレスを要求する（Ｓ１２０４）。なお、要求メッセージには、基点キーｓiに加えて、応答先を示すアドレスａが記述される。
【００５４】
この要求メッセージを受信した他のデータ転送装置は、図８〜図１０に示した処理によって、該要求メッセージをｓiのサクセッサに転送する。そして、該要求メッセージを受信したｓiのサクセッサは、アドレスａ宛に該サクセッサのＩＤ、第１のアドレス、第２のアドレスを送信する。
【００５５】
ルーティングテーブル管理部６０は、基点キーｓiのサクセッサから上記要求に対する応答として、該サクセッサのＩＤ＝ｋi、第１のアドレスａi、第２のアドレスａ’iを受信する（Ｓ１２０５）。そして、ルーティングテーブル管理部６０は、基点キー、ＩＤ、第１のアドレス、第２のアドレスを、それぞれ、ｓi、ｋi、ａi、ａ’iとするレコードをルーティングテーブルに登録する（Ｓ１２０６）。ただし、基点キーｓiから本データ転送装置のＩＤ＝ｋまでの距離の方が、基点キーｓiからＩＤ＝ｋiまでの距離よりも小さい場合には、ルーティングテーブル管理部６０は、基点キー、ＩＤ、第１のアドレス、第２のアドレスを、それぞれ、ｓi、ｋ、ａ、ａ’とするレコードをルーティングテーブルに登録する。
【００５６】
図１３は、サクセッサ・プレディセッサの初期化処理の一例を示すフローチャートである。ルーティングテーブル管理部６０は、ａeで識別されるデータ転送装置に、ｋのサクセッサのＩＤとアドレスを要求する（Ｓ１３０１）。なお、要求メッセージには、ｋに加えて、応答先を示すアドレスａが記述される。
【００５７】
この要求メッセージを受信した他のデータ転送装置は、図８〜図１０に示した処理によって、該要求メッセージをｋのサクセッサに転送する。そして、該要求メッセージを受信したｋのサクセッサは、アドレスａ宛に該サクセッサのＩＤ、第１のアドレス、第２のアドレスを送信する。
【００５８】
ルーティングテーブル管理部６０は、ｋのサクセッサから上記要求に対する応答として、該サクセッサのＩＤ＝ｋ1、第１のアドレスａ1、第２のアドレスａ’1を受信する（Ｓ１３０２）。そして、ルーティングテーブル管理部６０は、基点キー、ＩＤ、第１のアドレス、第２のアドレスを、それぞれ、ｋからの距離が１であるキーｋ1、ａ1、ａ’1とするレコードをルーティングテーブルに登録する（Ｓ１３０３）。
【００５９】
また、ルーティングテーブル管理部６０は、アドレスａ1で識別されるサクセッサから、該サクセッサのプレディセッサ記憶部６４に記憶されているデータ転送装置のＩＤ＝ｋp、第１のアドレスａp、第２のアドレスａ’pを取得し（Ｓ１３０４）、本データ転送装置のプレディセッサ記憶部６４に記憶する（Ｓ１３０５）。
【００６０】
さらに、ルーティングテーブル管理部６０は、アドレスａ1で識別されるサクセッサのプレディセッサ記憶部６４に記憶されている、ＩＤ、第１のアドレス、第２のアドレスを、それぞれ、ｋ、ａ、ａ’に更新する（Ｓ１３０６）。
【００６１】
図１４は、他のデータ転送装置のルーティングテーブルの更新処理の一例を示すフローチャートである。ルーティングテーブル管理部６０は、ｉ＝１からｍまで、以下の処理（Ｓ１４０２〜Ｓ１４０５）を実行する（Ｓ１４０１）。
【００６２】
ルーティングテーブル管理部６０は、ｋまでの距離が２i-1であるキーｋ-iを算出し（Ｓ１４０２）、他のデータ転送装置に、ｋ-iのプレディセッサのアドレスを要求する（Ｓ１４０３）。なお、要求メッセージには、ｋに加えて、応答先を示すアドレスａが記述される。
【００６３】
この要求メッセージを受信した他のデータ転送装置は、図８〜図１０に示した処理と同様の処理により、該要求メッセージをｋ-iのプレディセッサに転送する。そして、該要求メッセージを受信したｋ-iのプレディセッサは、アドレスａ宛に該プレディセッサのＩＤ、第１のアドレス、第２のアドレスを送信する。なお、図８〜図１０に示した処理では、キーのサクセッサが検索されたが、ここでは、キーのプレディセッサが検索される。そのため、図８に示した処理におけるステップＳ０８０２は不要となる。また、図９に示した処理におけるステップＳ０９０３の代わりに、該ステップＳ０９０３を実行しているデータ転送装置のＩＤ、第１のアドレス、第２のアドレスが、受信した要求メッセージに含まれる応答先アドレス宛に送信される。
【００６４】
ルーティングテーブル管理部６０は、ｋ-iの・BR>Vレディセッサから、上記要求に対する応答として、ｋ-iのプレディセッサの第１のアドレスａ-1を受信する（Ｓ１４０４）。そして、ルーティングテーブル管理部６０は、アドレスａ-1宛に、ｋ、ａ、ａ’、ｉを送信し、ルーティングテーブル更新を実行する（Ｓ１４０５）。
【００６５】
図１５は、他のデータ転送装置において実行されるルーティングテーブル更新処理の一例を示すフローチャートである。ルーティングテーブル管理部６０は、キーｋ、第１のアドレスａ、第２のアドレスａ’、インデックスｉを受信する（Ｓ１５０１）。
【００６６】
キーｋが本データ転送装置のＩＤである場合（Ｓ１５０２：Ｙｅｓ）、ルーティングテーブル更新処理は終了する。キーｋが本データ転送装置のＩＤではない場合（Ｓ１５０２：Ｎｏ）、ルーティングテーブル管理部６０は、ルーティングテーブルから、本データ転送装置のＩＤからの距離が２i-1であるキーを基点キーｓiとするレコードを取得する（Ｓ１５０３）。
【００６７】
ルーティングテーブル管理部６０は、ｓiからｋまでの距離の方が、ｓiから該レコードのＩＤまでの距離よりも小さいかどうか判定する（Ｓ１５０４）。ｓiからｋまでの距離の方が、ｓiから該レコードのＩＤまでの距離よりも大きい場合（Ｓ１５０４：Ｎｏ）、ルーティングテーブル更新処理は終了する。ｓiからｋまでの距離の方が、ｓiから該レコードのＩＤまでの距離よりも小さい場合（Ｓ１５０４：Ｙｅｓ）、ルーティングテーブル管理部６０は、該レコードのＩＤ、第１のアドレス、第２のアドレスを、それぞれ、ｋ、ａ、ａ’に更新する（Ｓ１５０５）。そして、ルーティングテーブル管理部６０は、プレディセッサ記憶部６４に記憶されている第１のアドレス宛に、ｋ、ａ、ａ’、ｉを送信し、ルーティングテーブル更新を実行する（Ｓ１５０６）。
【００６８】
＝＝具体例＝＝
次に、具体例を用いて、データ配信システム１０の動作を説明する。ここでは、図１６に示すように、ＩＤが０，３，１のデータ転送装置２０が順にデータ配信システム１０に追加されていくこととする。
【００６９】
まず、ＩＤが０のデータ転送装置０が起動される。データ転送装置０が起動すると、ルーティングテーブル管理部６０において、図１１に示す初期化処理が実行される。データ転送装置０がデータ配信システム１０における最初のデータ転送装置であるため、ステップＳ１１０２でＹｅｓのフローへ進む。ステップＳ１１０３からＳ１１０５までの処理により、データ転送装置０のルーティングテーブル記憶部６２とプレディセッサ記憶部６４は、それぞれ図１７と図１８に示すようになる。
【００７０】
次に、ＩＤが３のデータ転送装置３が起動される。データ転送装置３や、それ以降に起動されるデータ転送装置では、ステップＳ１１０２でＮｏのフローへ進む。ステップＳ１１０６のルーティングテーブル初期化では、まず、サクセッサ・プレディセッサ初期化Ｓ１２０１が実行される。サクセッサ・プレディセッサ初期化では、ステップＳ１３０１，Ｓ１３０２により、キー３のサクセッサとして、データ転送装置０のＩＤ、第１のアドレス、第２のアドレスが取得される。そして、ステップＳ１３０３により、データ転送装置３のルーティングテーブルは図１９に示すように更新される。
【００７１】
また、ステップＳ１３０４により、データ転送装置３は、データ転送装置０から、そのプレディセッサとして、プレディセッサ記憶部６４に記憶されているデータ転送装置０のＩＤ、第１のアドレス、第２のアドレスを取得する。そして、ステップＳ１３０５により、データ転送装置３のプレディセッサ記憶部６４は、図２０に示すようになる。また、ステップＳ１３０６により、データ転送装置０のプレディセッサ記憶部６４は、図１８から図２１に示すように更新される。以上により図１３に示すサクセッサ・プレディセッサ初期化処理が完了する。
【００７２】
その後、図１２の処理におけるステップＳ１２０２以降の処理により、データ転送装置３のルーティングテーブルは、図１９から図２２に更新される。以上によりルーティングテーブル初期化処理が完了する。
【００７３】
次に、他のデータ転送装置のルーティングテーブルの更新処理Ｓ１１０７が実行される（図１４）。ｉ＝１の場合、ステップＳ１４０２では、ｋ-1＝３−２1-1＝２となる。ステップＳ１４０３，Ｓ１４０４により、キー２のプレディセッサとしてデータ転送装置０のＩＤ、第１のアドレス、第２のアドレスが取得される。よって、ステップＳ１４０５において、データ転送装置３のＩＤ、第１のアドレス、第２のアドレス、インデックスｉ＝１が、データ転送装置０へ送信される。
【００７４】
データ転送装置０は、ルーティングテーブル更新を行う（図１５）。ステップＳ１５０２では、受信したキー＝３は、データ転送装置０のＩＤ＝０でないと判定され、ステップＳ１５０３へ進む。ステップＳ１５０３では、基点キーが０＋２i-1＝１である、データ転送装置０のＩＤが記録されるレコードがルーティングテーブルから取得される。ステップＳ１５０４では、基点キー１から、受信したキー３までの距離の方が、基点キー１から、取得したレコードのキー０までの距離よりも小さいので、ステップＳ１５０５に進む。ステップＳ１５０５により、データ転送装置０のルーティングテーブルは図１７から図２３のように変更される。ステップＳ１５０６で、データ転送装置０は、プレディセッサ記憶部６４に記憶されるデータ転送装置３に、データ転送装置３のＩＤ、第１のアドレス、第２のアドレス、インデックスｉ＝１を送信する。
【００７５】
データ転送装置０からの情報を受信したデータ転送装置３は、ステップＳ１５０２で、受信したキー３がデータ転送装置３のＩＤであると判断し、ルーティングテーブル更新処理を終了する。
【００７６】
データ転送装置３における、他のデータ転送装置のルーティングテーブルの更新処理（図１４）で、ｉ＝２の場合、ｉ＝１の場合と同様に処理が実行され、データ転送装置０のルーティングテーブルは図２３から図２４のように変更される。ｉ＝３の場合、ステップＳ１４０２からＳ１４０５までの処理により、データ転送装置０にデータ転送装置３のＩＤ、第１のアドレス、第２のアドレス、インデックスｉ＝３が送信される。データ転送装置０は、データ転送装置３からの情報を受信すると、ルーティングテーブルの更新処理（図１５）を実行する。図１５の処理のステップＳ１５０４では、基点キー４から、受信したキー３までの距離の方が、基点キー４から、取得したレコードのＩＤ＝０までの距離よりも大きいため、ルーティングテーブルの更新処理は終了する。
【００７７】
最後に、ＩＤが１のデータ転送装置１が起動される。データ転送装置１で、ルーティングテーブルの初期化処理Ｓ１１０６と、他のデータ転送装置のルーティングテーブルの更新処理Ｓ１１０７とが完了すると、各データ転送装置のルーティングテーブル記憶部６２とプレディセッサ記憶部６４は図２５に示すように更新される。
【００７８】
次に、データ送信装置２４からデータ転送装置２０へ送信されたデータがデータ受信装置２６に到達するまでのデータ配信システム１０の動作例を説明する。
【００７９】
まず、データ転送装置３が、データ送信装置２４からデータを受信したとする。データ転送装置３は、受信したデータを第１受信キュー４０に挿入する。第１転送部５０は、該データを第１受信キュー４０から取り出し、該データのハッシュ値をキーとして算出する。なお、キーの算出は、データ転送装置がデータ送信装置２４からデータを受信した場合にのみ実施される。ここでは、算出されたキーが１であったとする。
【００８０】
図８に示した処理のステップＳ０８０２において、データ転送装置３はキー＝１のサクセッサではないため、ステップＳ０８０４に進む。ステップＳ０８０４では、データ転送装置０が転送先データ転送装置として検索される。これは、データ転送装置３のルーティングテーブルに、キー＝１までの距離が最も小さいＩＤを有するデータ転送装置０が記憶されているからである。ステップＳ０８０５では、データ転送装置３のＩＤ＝３の方が、データ転送装置０のＩＤ＝０よりも大きいため、ステップＳ０８０７へ進む。ステップＳ０８０７で、第１送信キュー４４内のデータ転送装置０の第２のアドレス宛のデータを保持するキュー（図５のｓ３−１）に、キー＝１と受信したデータが挿入される。データ転送装置３は、該キューから該キーと該データを取り出し、データ転送装置０の第２のアドレス宛に送信する。
【００８１】
データ転送装置０は、第２のアドレスで受信したキー＝１とデータを第２受信キュー４２（図５のｒ０−２）に挿入する。データ転送装置０の第２転送部５２は、受信したキー＝１とデータの転送先を決定する（図１０）。図１０の処理におけるステップＳ１００２では、データ転送装置０は受信したキー＝１のサクセッサでないと判定され、ステップＳ１００４へ進む。ステップＳ１００４では、データ転送装置１が転送先データ転送装置として検索される。これは、データ転送装置０のルーティングテーブル内に、キー＝１までの距離が最も小さいＩＤを持つ他のデータ転送装置が存在せず、ステップＳ０９０３が実行されるためである。ステップＳ１００５では、第２送信キュー４６内の、データ転送装置１の第２のアドレス宛のデータを保持するキュー（図 ５のｓ０−４）にキーｋとデータが挿入される。データ転送装置０は、該キューから該キーと該データを取り出し、データ転送装置１の第２のアドレス宛に送信する。
【００８２】
データ転送装置１は、第２のアドレスで受信したキー＝１とデータを第２受信キュー４２（図５のｒ１−３）に挿入する。データ転送装置１の第２転送部５２は、受信したキー＝１とデータの転送先を決定する（図１０）。図１０のステップＳ１００２では、本データ転送装置がキー＝１のサクセッサであると判定され、ステップＳ１００３に進む。ステップＳ１００３では、第２送信キュー４６内の、データ受信装置２６に転送するデータを保持するキュー（図５のｓ１−２）に該データが挿入される。データ転送装置１は、該キューから該キーと該データを取り出し、データ受信装置２６宛に送信する。以上の処理により、データ送信装置２４からデータ受信装置２６への、データ配信システム１０を介したデータの配信が完了する。
【００８３】
以上、本実施形態について説明した。本実施形態によれば、データフローが環状とならないように構成されているため、デッドロックを防止することができる。また、本実施形態では、メッセージ通信バッファのサイズに依存することなく、つまり、大きなサイズのメッセージ通信バッファを確保することなくデッドロックを防止することができる。
【００８４】
なお、本実施形態は、本発明の理解を容易にするためのものであり、本発明を限定して解釈するためのものではない。本発明は、その趣旨を逸脱することなく、変更／改良され得るととともに、本発明にはその等価物も含まれる。
【００８５】
例えば、本実施形態では、転送先のデータ転送装置のＩＤが、自装置のＩＤよりも大きい場合に、大小関係が一方の関係であると判定し、転送先のデータ転送装置のＩＤが、自装置のＩＤよりも小さい場合に、大小関係が他方の関係であると判定したが、一方の関係と他方の関係とを本実施形態と逆にすることも可能である。
【００８６】
また、本実施形態では、データ転送装置のＩＤの昇順に環を構成することとしたが、データ転送装置のＩＤの降順に環を構成することとしてもよい。
【００８７】
この出願は、２０１１年３月２５日に出願された日本出願特願２０１１−０６８４８６を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【００８８】
以上、実施形態を参照して本願発明を説明したが、本願発明は上記実施形態に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【００８９】
本実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
（付記１）ネットワークを介して接続された少なくとも１つの他のデータ転送装置の、識別子、第１のアドレス、及び第２のアドレスを含む、ルーティングテーブルを記憶するルーティングテーブル記憶部と、自装置の第１のアドレス宛のデータを受信すると、該データから算出されるキーと、前記ルーティングテーブルに含まれる少なくとも１つの他のデータ転送装置の識別子との関係に基づいて、該データの転送先となる他のデータ転送装置を決定し、自装置の識別子と、該他のデータ転送装置の識別子との大小関係が一方の関係である場合は、該データを該他のデータ転送装置の第１のアドレス宛に送信し、前記大小関係が他方の関係である場合は、該データを該他のデータ転送装置の第２のアドレス宛に送信する、第１転送部と、自装置の第２のアドレス宛のデータを受信すると、該データのキーと、前記ルーティングテーブルに含まれる少なくとも１つの他のデータ転送装置の識別子との関係に基づいて、該データの転送先となる他のデータ転送装置を決定し、該データを該他のデータ転送装置の第２のアドレス宛に送信する、第２転送部と、を備えるデータ転送装置。
（付記２）付記１に記載のデータ転送装置であって、前記第１及び第２転送部は、前記データのキーと自装置の識別子とが所定の関係にある場合は、該データの転送先をデータ受信装置と決定する、データ転送装置。
（付記３）付記２に記載のデータ転送装置であって、前記第１及び第２転送部は、自装置が前記データのキー（ｍビット）からの２ｍを法とする剰余環における距離が最も小さい識別子を有する場合、前記データ受信装置を転送先として決定する、データ転送装置。
（付記４）付記１〜３の何れか一項に記載のデータ転送装置であって、前記第１及び第２転送部は、前記ルーティングテーブルに含まれる少なくとも１つの他のデータ転送装置の中に、該データ転送装置の識別子から前記データのキーまでの距離が自装置の識別子からの距離よりも小さいデータ転送装置が存在する場合は、該距離が最小であるデータ転送装置を転送先として決定し、自装置の識別子から前記データのキーまでの距離が最も小さい場合は、該データ転送装置の識別子からの距離が最も小さい識別子を有するデータ転送装置を転送先として決定する、データ転送装置。
（付記５）付記１〜４の何れか一項に記載のデータ転送装置であって、他のデータ転送装置に対して、自装置の識別子、第１のアドレス、及び第２のアドレスを、該他のデータ転送装置のルーティングテーブルを更新するために送信し、他のデータ転送装置から、該他のデータ転送装置の識別子、第１のアドレス、及び第２のアドレスを受信すると、他のデータ転送装置から、該他のデータ転送装置の識別子、第１のアドレス、及び第２のアドレスを受信すると、ルーティングテーブル内の該他のデータ転送装置の識別子で特定されるレコードを、第１のアドレス、及び第２のアドレスを受信した第１のアドレス、及び第２のアドレスに更新する、ルーティングテーブル管理部をさらに備えるデータ転送装置。
（付記６）付記５に記載のデータ転送装置であって、自装置の識別子からの距離が最も大きいデータ転送装置の識別子、第１のアドレス、及び第２のアドレスを記憶するプレディセッサ記憶部をさらに備え、前記ルーティングテーブル管理部は、自装置の識別子からの距離が最も小さい識別子を有する他のデータ転送装置のプレディセッサ記憶部を更新するために、自装置の識別子、第１のアドレス、及び第２のアドレスを該他のデータ転送装置に送信し、該他のデータ転送装置から、該他のデータ転送装置のプレディセッサ記憶部に記憶されている識別子、第１のアドレス、及び第２のアドレスを取得して、自装置のプレディセッサ記憶部に記憶する、データ転送装置。
（付記７）付記５または６に記載のデータ転送装置であって、前記ルーティングテーブル管理部は、自装置の初期化時に、自装置の識別子からの２ｍを法とする剰余環における距離が２ｉ−１（ｉ＝１，２，・・・，ｍ）であるキー（ｍビット）を算出し、該キーからの距離が最も小さい識別子を有するデータ転送装置の識別子、第１のアドレス、及び第２のアドレスを、該キーと対応づけて、前記ルーティングテーブルに記憶する、データ転送装置。
（付記８）付記７に記載のデータ転送装置であって、他のデータ転送装置の識別子からの距離が２ｉ−１であるキーについて、該キーからの距離が最小であるデータ転送装置が自装置である場合に、該他のデータ転送装置に対して、該他のデータ転送装置のルーティングテーブルを更新するために、自装置の識別子、第１のアドレス、及び第２のアドレスを送信する、データ転送装置。
（付記９）付記１〜８の何れか一項に記載のデータ転送装置であって、自装置の第１のアドレス宛で受信されたデータが一時的に格納される第１の受信キューと、自装置の第２のアドレス宛で受信されたデータが一時的に格納される第２の受信キューと、他のデータ転送装置の第１のアドレスごとのキューを有する第１の送信キューと、他のデータ転送装置の第２のアドレスごとのキューを有する第２の送信キューと、をさらに備え、前記第１転送部は、前記第１の受信キューに格納されているデータを前記他のデータ転送装置の第１のアドレス宛に送信する際は、前記第１の送信キューの中の、該第１のアドレスに対応するキューに該データを挿入し、前記第１の受信キューに格納されているデータを前記他のデータ転送装置の第２のアドレス宛に送信する際は、前記第２の送信キューの中の、該第２のアドレスに対応するキューに該データを挿入し、前記第２転送部は、前記第２の受信キューに格納されているデータを前記他のデータ転送装置の第２のアドレス宛に送信する際は、前記第２の送信キューの中の、該第２のアドレスに対応するキューに該データを挿入する、データ転送装置。
（付記１０）ネットワークを介して接続される複数のデータ転送装置を含むデータ配信システムにおける各データ転送装置が、少なくとも１つの他のデータ転送装置の、識別子、第１のアドレス、及び第２のアドレスを含む、ルーティングテーブルを記憶し、自装置の第１のアドレス宛のデータを受信すると、該データから算出されるキーと、前記ルーティングテーブルに含まれる少なくとも１つの他のデータ転送装置の識別子との関係に基づいて、データ受信装置または他のデータ転送装置を該データの転送先として決定し、データ受信装置が転送先として決定されると、該データ受信装置に該データを送信し、他のデータ転送装置が転送先として決定されると、自装置の識別子と、該他のデータ転送装置の識別子との大小関係が一方の関係である場合は、該データを該他のデータ転送装置の第１のアドレス宛に送信し、前記大小関係が他方の関係である場合は、該データを該他のデータ転送装置の第２のアドレス宛に送信し、自装置の第２のアドレス宛のデータを受信すると、該データから算出されるキーと、前記ルーティングテーブルに含まれる少なくとも１つの他のデータ転送装置の識別子との関係に基づいて、データ受信装置または他のデータ転送装置を該データの転送先として決定し、データ受信装置が転送先として決定されると、該データ受信装置に該データを送信し、他のデータ転送装置が転送先として決定されると、該データを該他のデータ転送装置の第２のアドレス宛に送信する、データ転送方法。
【符号の説明】
【００９０】
１０  データ配信システム
２０  データ転送装置
２２  ネットワーク
２４  データ送信装置
２６  データ受信装置
４０  第１受信キュー
４２  第２受信キュー
４４  第１送信キュー
４６  第２送信キュー
５０  第１転送部
５２  第２転送部
６０  ルーティングテーブル管理部
６２  ルーティングテーブル記憶部
６４  プレディセッサ記憶部
６６  自装置情報記憶部
【図１】
2012133211.tif 000003
【図２】
2012133211.tif 000004
【図３】
2012133211.tif 000005
【図４】
2012133211.tif 000006
【図５】
2012133211.tif 000007
【図７】
2012133211.tif 000008
【図８】
2012133211.tif 000009
【図９】
2012133211.tif 000010
【図１０】
2012133211.tif 000011
【図１１】
2012133211.tif 000012
【図１２】
2012133211.tif 000013
【図１３】
2012133211.tif 000014
【図１４】
2012133211.tif 000015
【図１５】
2012133211.tif 000016
【図１６】
2012133211.tif 000017
【図１７】
2012133211.tif 000018
【図１８】
2012133211.tif 000019
【図１９】
2012133211.tif 000020
【図２０】
2012133211.tif 000021
【図２１】
2012133211.tif 000022
【図２２】
2012133211.tif 000023
【図２３】
2012133211.tif 000024
【図２４】
2012133211.tif 000025
【図２５】
2012133211.tif 000026
【図２７】
2012133211.tif 000027
【図６】
2012133211.tif 000028
【図２６】
2012133211.tif 000029
【国際調査報告】
2012133211.tif 000030
2012133211.tif 000031