(57)【要約】【課題】  障害耐性を高めるために、次数分布が故障と攻撃の両方に対して耐性のある二極次数分布に従うP2P型のネットワークを構築する。【解決手段】  本発明は、高次数ノードから１つの高次数ノードと複数の低次数ノードで構成されるグループについて、高次数ノード間で交換されるグループ間リストと、該グループ内のノード間で交換されるグループ内リストを収集し、グループ間リストの参加ノードのノードタイプが低次数ノードか高次数ノードかを判定し、高次数ノードと判定された場合には、参加ノードと他の高次数ノードとを接続し、グループ間リストを更新する。低次数ノードと判定された場合には、参加先のグループを決定し、該グループ内の高次数ノードの次数が所定の次数を満足している場合は、高次数ノードと接続し、満足していない場合は、グループ内の次数の本数を統一する処理を行い、グループ内リストを更新する。【選択図】  図５
2014027476.tif 000002
【特許請求の範囲】
【請求項１】
P2P(Peer to Peer)型のネットワークの仮想ネットワーク上でデータ転送を行うときの隣接ノード数（次数）の分布に応じてネットワークを構築するためのノード参加処理装置であって、
１つの高次数ノードと複数の低次数ノードで構成されるグループについて、高次数ノード間で交換されるグループ間リストと、該グループ内のノード間で交換されるグループ内リストを保持する高次数ノードから、該グループ間リストと該グループ内リストを収集するグループ間リスト収集手段と、
前記グループ間リストの参加ノードのノードタイプが低次数ノードか高次数ノードのいずれであるかを判定するノードタイプ決定手段と、
前記ノードタイプ決定手段で前記参加ノードが高次数ノードと判定された場合には、前記参加ノードと他の高次数ノードとを接続し、前記グループ間リストを更新する高次数ノード更新手段と、
前記ノードタイプ決定手段で前記参加ノードが低次数ノードと判定された場合には、参加先のグループを決定し、該グループ内の高次数ノードの次数が所定の次数を満足している場合は、高次数ノードと接続し、満足していない場合は、グループ内の次数の本数を統一する処理を行い、前記グループ内リストを更新する低次数ノード更新手段と、
を有することを特徴とするノード参加処理装置。
【請求項２】
前記低次数ノード更新手段は、
前記グループ内の高次数ノードの次数を満足していない場合は、前記グループ内のあるノードとそのノードの隣接ノードとの間に割り込んで接続する割り込み接続手段と、
前記参加ノードの次数が所定の次数を満足していない場合は、参加ノードの次数を満たすか接続先の候補となるノードがなくなるまで接続処理を繰り返す追加接続手段と、
を含む請求項１記載のノード参加処理装置。
【請求項３】
前記ノードタイプ決定手段は、
前記参加ノードのタイプを高次数ノード数と低次数ノード数の比率によって決定する手段を含む
請求項１記載のノード参加処理装置。
【請求項４】
P2P(Peer to Peer)型のネットワークのノードがもつリンク数（次数）の分布に応じてネットワークを構築するためのノード参加処理方法であって、
グループ間リスト収集手段、ノードタイプ決定手段、高次数ノード更新手段、低次数ノード更新手段を有する装置において、
前記グループ間リスト収集手段が、１つの高次数ノードと複数の低次数ノードで構成されるグループについて、高次数ノード間で交換されるグループ間リストと、該グループ内のノード間で交換されるグループ内リストを保持する高次数ノードから該グループ間リストと該グループ内リストを収集するグループ間リスト収集ステップと、
前記ノードタイプ決定手段が、前記グループ間リストの参加ノードのノードタイプが、低次数ノードか高次数ノードのいずれであるかを判定するノードタイプ決定ステップと、
前記高次数ノード更新手段が、前記ノードタイプ決定ステップで前記参加ノードが高次数ノードと判定された場合には、前記参加ノードと他の高次数ノードとを接続し、前記グループ間リストを更新する高次数ノード更新ステップと、
前記低次数ノード更新手段が、前記ノードタイプ決定ステップで前記参加ノードが低次数ノードと判定された場合には、参加先のグループを決定し、該グループ内の高次数ノードの次数が所定の次数を満足している場合は、高次数ノードと接続し、満足していない場合は、グループ内の次数の本数を統一する処理を行い、前記グループ内リストを更新する低次数ノード更新ステップと、
を行うことを特徴とするノード参加処理方法。
【請求項５】
前記低次数ノード更新ステップにおいて、
前記グループ内の高次数ノードの次数を満足していない場合は、前記グループ内のあるノードとそのノードの隣接ノードとの間に割り込んで接続する割り込み接続ステップと、
前記参加ノードの次数が所定の次数を満足していない場合は、参加ノードの次数を満たすか接続先の候補となるノードがなくなるまで接続処理を繰り返す追加接続ステップと、
を含む請求項４記載のノード参加処理方法。
【請求項６】
前記ノードタイプ決定ステップにおいて、
前記参加ノードのタイプを高次数ノード数と低次数ノード数の比率によって決定する
請求項４記載のノード参加処理方法。
【請求項７】
コンピュータを、
請求項１乃至３のいずれか１項に記載のノード参加処理装置の各手段として機能させるためのノード参加処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ノード参加処理装置及び方法及びプログラムに係り、特に、ネットワークの耐障害性を高めたデータ転送を行う際のノード参加処理装置及び方法及びプログラムに関する。
【背景技術】
【０００２】
従来のクライアント／サーバ型のネットワークと比較して、より低コストでインターネット資源の共有やコンテンツ配信が可能なP2P(Peer to Peer)型のネットワークが注目されている。
【０００３】
P2P型のネットワーク上では、ノードが自由に参加、離脱するためにトポロジが安定しなくなる（Churn問題）ことがある。これに対し、Churn耐性を向上させることを目的として開発された、べき分布の階層化したP2Pネットワークの一つであるGnutella ver2がある（例えば、非特許文献1参照）。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】D. Stutzbach, R. Rejaie, and S. Sen, "Characterizing unstructured overlay topologies in modern p2p file-sharing systems," IEEE/ACM Transactions on Networking, vol. 16. no. 2, pp. 267-280, Apr. 2008.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、上記非特許文献１の技術は、ランダムに接続相手を選択することによって、グループ間のリンク本数が不均等となり、攻撃によってネットワークが分断されてしまうという問題がある。これは、P2P型のネットワークは故障耐性が高い一方で攻撃耐性が極端に低いという問題がある。これは、P2P型のネットワークの次数分布が、故障耐性の高いべき分布に従うことに起因する。
【０００６】
本発明は、上記の点に鑑みなされたもので、障害耐性を高めるために、次数分布が故障と攻撃の両方に対して耐性のある二極次数分布に従うP2P型のネットワークを構築することが可能なノード参加処理装置及び方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
上記の課題を解決するため、本発明（請求項１）は、P2P(Peer to Peer)型のネットワークのノードがもつリンク数（次数）の分布に応じてネットワークを構築するためのノード参加処理装置であって、
１つの高次数ノードと複数の低次数ノードで構成されるグループについて、高次数ノード間で交換されるグループ間リストと、該グループ内のノード間で交換されるグループ内リストを保持する高次数ノードから、該グループ間リストと該グループ内リストを収集するグループ間リスト収集手段と、
前記グループ間リストの参加ノードのノードタイプが低次数ノードか高次数ノードのいずれであるかを判定するノードタイプ決定手段と、
前記ノードタイプ決定手段で前記参加ノードが高次数ノードと判定された場合には、前記参加ノードと他の高次数ノードとを接続し、前記グループ間リストを更新する高次数ノード更新手段と、
前記ノードタイプ決定手段で前記参加ノードが低次数ノードと判定された場合には、参加先のグループを決定し、該グループ内の高次数ノードの次数が所定の次数を満足している場合は、高次数ノードと接続し、満足していない場合は、グループ内の次数の本数を統一する処理を行い、前記グループ内リストを更新する低次数ノード更新手段と、
を有する。
【０００８】
また、本発明（請求項２）は、前記低次数ノード更新手段において、
前記グループ内の高次数ノードの次数を満足していない場合は、前記グループ内のあるノードとそのノードの隣接ノードとの間に割り込んで接続する割り込み接続手段と、
前記参加ノードの次数が所定の次数を満足していない場合は、参加ノードの次数を満たすか接続先の候補となるノードがなくなるまで接続処理を繰り返す追加接続手段と、を含む。
【０００９】
また、本発明（請求項３）は、前記ノードタイプ決定手段において、
前記参加ノードのタイプを高次数ノード数と低次数ノード数の比率によって決定する手段を含む。
【発明の効果】
【００１０】
上記のように本発明によれば、故障と攻撃の両方に対して耐性のある高次数ノードと低次数ノードの二極次数分布に従うP2P型のネットワークを構成し、さらに、グループ間のリンク本数を統一するように、所定の次数を満足するように、ノードの接続処理を行うことにより、耐攻撃性を向上させることが可能となる。
【図面の簡単な説明】
【００１１】
【図１】次数分布の種類を示す図である。
【図２】二極次数分布を示す図である。
【図３】本発明の一実施の形態におけるノード参加処理装置の構成図である。
【図４】本発明の一実施の形態におけるノード参加手順のフローチャートである。
【図５】本発明の一実施の形態における高次元ノード、低次元ノードで構成されるグループの例である。
【図６】参加ノードアルゴリズムである。
【図７】本発明の一実施の形態における参加ノードの所属を決定する例である。
【図８】本発明の一実施の形態における低次元ノード更新部の構成図である。
【図９】本発明の一実施の形態における割り込み接続処理の例である。
【図１０】本発明の一実施の形態における追加接続処理の例である。
【図１１】従来手法と提案手法の比較である。
【発明を実施するための形態】
【００１２】
以下、図面と共に本発明の実施の形態を説明する。
【００１３】
まず、本明細書で用いられる用語について説明する。
【００１４】
・リンク数（次数）：P2Pネットワークにおいて、仮想ネットワーク上でデータ転送を行うときの隣接ノード数である。
【００１５】
・低次数ノード・高次数ノード：次数の低いノード、次数の高いノードである。
【００１６】
・故障耐性（Churn耐性）：P2Pネットワーク上では、ノードが自由に参加、離脱するためトポロジが安定しなくなることがある（これを「Churn問題」と記す）。この問題に対するネットワークの安定性をChurn耐性と呼ぶ。本明細書では、Churnは次数に関係なくどのノードにも起きるものと仮定する。
【００１７】
・攻撃耐性（Dos攻撃耐性）：階層型P2Pネットワークでは、ネットワークの中心的な役割を担うノードに対して攻撃が行われる。つまり、高次数のノードが集中的に攻撃される現象である。その攻撃に対するネットワークの安定性をDoS(Denial of Service)耐性と呼ぶ。
【００１８】
・ネットワークの特徴量：複雑ネットワーク分野では、ネットワークの特徴量として次数分布、クラスタ計数、次数相関など様々な指標が研究されている。これらの指標を参考にしてネットワークを形成することができる。
【００１９】
・ノード除去：ネットワークからノードを消去することを指す。つまり接続しているリンクも消去されるため、ネットワーク中で孤立するノードが生じる可能性がある。
【００２０】
まず、次数分布の種類について説明する。
【００２１】
図１は、次数分布の種類を示す。
【００２２】
・正規分布（ランダムネットワーク）：ランダムにリンクを張ったときの分布であり、ネットワークにおける各ノードが持つリンク数の分布を示したものである。言い換えれば、ネットワーク上でリンク数ｘを持つノードの数ｆ（ｘ）を示す関数である。
【００２３】
・一様分布（レギュラーネットワーク）：同一の次数を持つノードだけが存在する分布である。一種類の次数のノードで構成されるため、高次数のノードがターゲットになるDoS攻撃に対して攻撃耐性の高い分布である。
【００２４】
・べき分布（スケールフリーネットワーク）：現実の多くのネットワークの分布であり、べき乗則に従う次数分布である。一様分布と比較して多数の種類の次数を持つノードが存在する。この分布では、高次数ノードが存在するため、ネットワークの接続性が高まり、Churnに対して強固であるといえる。
【００２５】
本発明では、上記のDoS攻撃耐性の高い一様分布とchurn耐性の高いべき分布との複合である二極次数分布に近似する次数分布を構築する。
【００２６】
図２は、二極次数分布を示す。
【００２７】
二極分布は、低次数ノードと高次数ノードの二極化した次数分布であり、同図（ｂ）に示すように、低次数ノード数の方が高次数ノード数より多い。ここで、高次数ノードとは、グループ内でハブとなっているノードである。二極分布は、高次数と低次数のノードが同時に存在する特徴をべき分布から、次数が限定される特徴を一様分布からそれぞれ受け継ぐため、churnは次数に関係なくどのノードにも起こると仮定すると、churn、DoS攻撃どちらに対しても強固であるといえる。
【００２８】
ネットワークに動的にノードが参加・離脱する状況下で、各ノードの次数、各次数のノード数を、各ノードで分散して制御することは困難である。そのため、動的に変化するノード総数を共有する方法が必要であり、各ノードで理想値を導出するために、ノード総数と平均次数を求める必要がある。高次数ノードと低次数ノードのノード数の最適な値は、それぞれ後述する式(3)、式(1)に示すとおりである。但し、Nはノード総数、<k>は平均次数である。
【００２９】
低次数ノード総数を、
【００３０】
【数１】
2014027476.tif 000003
低次数ノード次数を、
【００３１】
【数２】
2014027476.tif 000004
高次数ノード総数を、
【００３２】
【数３】
2014027476.tif 000005
高次数ノード次数を
【００３３】
【数４】
2014027476.tif 000006
によって求める。但し、
【００３４】
【数５】
2014027476.tif 000007
本発明では、上記の次数を決定する手法を用いて参加ノードの次数を決定する。
【００３５】
以下に、本発明のノード参加処理装置について説明する。
【００３６】
図３は、本発明の一実施の形態におけるノード参加処理装置の構成を示す。
【００３７】
同図に示すノード参加処理装置は、グループ間リスト収集部１０、ノードタイプ決定部２０、高次数ノード更新部３０、低次数ノード更新部４０から構成される。
【００３８】
図４は、本発明の一実施の形態におけるノードの参加手順のフローチャートである。
【００３９】
以下に、図３に示す構成要素の動作を図４のフローチャートに沿って説明する。
【００４０】
グループ間リスト収集部１０は、グループ間のリストとグループ内リストの整合性を管理している高次数ノードよりグループ間リストとグループ内リストを収集する(ステップ１００)。ここで、グループ間リストは、高次数ノード間で交換されるリストであり、高次数ノードのアドレス、各グループのノード数と次数を満足していないノード数を含む。またグループ内リストは、グループ内のノード間で交換されるリストであり、ノード総数、高次数ノード数、高次数ノードのアドレス、次数を満足していないノードのアドレスを含む。ここで、グループとは、図５に示すように、一つの高次数ノードと複数の低次数ノードで構成される。
【００４１】
ノードタイプ決定部２０は、グループ間リスト収集部１０からグループ間リストを取得し、図６に示すアルゴリズムに基づいて、高次数ノードのアドレスから現在の高次数ノードの数、各グループのノード数から現在の低次数ノードの数を計算し、そのノード数の比率によって、高次数、または、低次数のいずれかのノードタイプを決定する(ステップ１１０)。参加ノードは、前述の式(3)に示す高次数ノードの最適値、式(1)に示す低次数ノードの最適値と実際にネットワークに存在する高次数ノード数または低次数ノード数を比較して、差分が大きい方に属する。図７の例では、低次数ノード数の方が差分が大きいものとし、参加ノードのタイプを低次数ノードとしてグループに追加する。
【００４２】
高次数ノード更新部３０は、ノードタイプ決定部２０で「高次数」のタイプであると決定された場合に、他の高次数ノードと接続し(ステップ１２１)、グループ間リストを更新する。具体的には、自身のアドレス、自身のグループに属するノード数（この時点では０）と次数を満足していないノード数（この時点では０）を追加する (ステップ１２２)。
【００４３】
低次数ノード更新部４０は、図８に示すように、参加先グループ決定部４１、グループ内リスト収集部４２、グループ内高次数ノードの次数判定部４３、高次数ノード接続部４４、割り込み処理部４５、参加ノードの次数決定部５６、グループ内リスト更新部４７、追加接続処理部４８、候補となる追加ノード判定部４９を有する。
【００４４】
まず、ノードタイプ決定部２０においてノードタイプが低次数と判定された場合に、参加先グループ決定部４１は、グループ内リスト内の各グループに属するノード数を参照し、最もノード数が少ないグループを所属先のグループとして決定し、決定されたグループ内リストをグループ内リスト収集部４２に出力する（ステップ１３１）。
【００４５】
グループ内リスト収集部４２は、参加先グループ決定部４１から渡されたグループ内リストを取得する(ステップ１３２)。
【００４６】
グループ内高次数ノードの次数判定部４３は、グループ内リストの高次数ノードの次数が満足しているか否かを判定する。高次数ノードの次数の理論値が現在の値よりも大きいときは不満足と判定し、ステップ１３４に移行し、そうでない場合は満足していると判定し、ステップ１３５に移行する（ステップ１３３）。なお、高次数ノードの次数の理論値算出は、ノード総数が変化したときに、高次数ノード自身で行う。
【００４７】
高次数ノード接続部４４は、グループ内高次数ノードの次数判定部４３において、高次数ノードの次数が不満足であると判定された場合に、高次数ノードと接続し、割り込み処理部４５の処理に移行する(ステップ１３４)。なお、割り込み処理部４５では、他の低次数ノードの次数を変化させることなく、新規参加ノードがリンクを持つことが可能であるため、高次数ノードとの接続後、割り込み処理を行うことで、新規参加ノードは次数が満足していないノードがない場合でも次数を獲得することが可能である。
【００４８】
割り込み処理部４５は、グループ内高次数ノードの次数判定部４３において、高次数ノードの次数が満足・不満足のいずれの場合にも、図９に示すように、参加ノードをグループ内のあるノードとそのノードの隣接ノードとの間に割り込ませて接続する（ステップ１３５）。これにより各ノードにおいて均等なリンクの割り当てを保証する。
【００４９】
参加ノードの次数決定部４６は、参加ノードの次数をタイプとノード数によって決定する(ステップ１３６)。低次数ノードの次数は、
【００５０】
【数６】
2014027476.tif 000008
により決定し、高次数ノードの次数は、
【００５１】
【数７】
2014027476.tif 000009
により決定する。但し、Ｎはノード総数、<k>は予め決められた平均次数である。
【００５２】
グループ内リスト更新部４７は、参加ノードの次数決定部４６で決定された参加ノードの次数が満足する場合は、グループ内リストのノード総数、次数を満足していないノードのアドレスを更新する(ステップ１３７)。
【００５３】
追加接続処理部４８は、参加ノードの次数決定部４６で決定された参加ノードの次数が満足しない場合には、図１０に示すように、参加ノードの次数を満たすか、または、接続先の候補となるノードがなくなるまでノード間の接続処理を行う(ステップ１３８)。
【００５４】
候補となる追加ノード判定部４９は、候補となる追加ノードがグループ内リストに存在するかを判定し(ステップ１３９)、存在しない場合はグループ内リスト更新部４７にグループ内リストの更新を指示し、当該グループ内リスト更新部４７において、グループ内リストを更新する。存在する場合には、参加ノードの次数決定部４６に対して、参加ノードの次数の決定を指示する。これにより参加ノードの次数決定部４６は、上記のステップ１３６の処理を行う。
【００５５】
本発明では、階層型P2Pネットワークの攻撃耐性が低いという問題を解決するために、低次数ノード、高次数ノードの二極次数分布に従う階層型P2Pネットワークを構築した。
【００５６】
本発明と従来技術の耐障害性と耐攻撃性を比較した結果を図１１に示す。実験では、Churnでは次数に関わらないランダムなノード除去を、DoS攻撃では高次数のノードから順に除去している。比較結果からわかるように、接続先の決定法に関して、従来手法がランダムに接続相手を選択することによって、グループ間のリンク本数が不均等となり、攻撃によってネットワークが分割する問題があるのに対して、本発明は、グループ内のリンク本数を統一することにより耐攻撃性を向上させている。
【００５７】
上記の図４，５に示すノード参加処理装置の構成要素の動作をプログラムとして構築し、ノード参加処理装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００５８】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【符号の説明】
【００５９】
１０  グループ間リスト収集部
２０  ノードタイプ決定部
３０  高次数ノード更新部
４０  低次数ノード更新部
４１  参加先グループ決定部
４２  グループ内リスト収集部
４３  グループ内高次数ノードの次数判定部
４４  高次数ノード接続部
４５  割り込み処理部
４６  参加ノードの次数決定部
４７  グループリスト更新部
４８  追加接続処理部
４９  候補となる追加ノード判定部
【図１】
2014027476.tif 000010
【図２】
2014027476.tif 000011
【図３】
2014027476.tif 000012
【図４】
2014027476.tif 000013
【図５】
2014027476.tif 000014
【図６】
2014027476.tif 000015
【図７】
2014027476.tif 000016
【図８】
2014027476.tif 000017
【図９】
2014027476.tif 000018
【図１０】
2014027476.tif 000019
【図１１】
2014027476.tif 000020