(57)【要約】ファイル共有システムにおいてピアのスウォームにおいてピアが費やす平均時間を制御する方法が、ピアの前記スウォームにおける動作の自律モードを確立する段階を含む。自律モードでは、ピアは、所望されるファイルの片へのアクセスを得るために、自分のスウォームにおける他のピアとのみ通信する。スウォーム・サイズが閾値サイズを満たす場合、ファイル共有システムはユニバーサル・モードに切り替わる。ユニバーサル・モードでは、あるスウォームからのピアは、他のスウォームにおける他のピアと所望されるファイル片を交換することが許される。スウォーム内のピアによって保持される所望されるファイル片が閾値数を満たす場合には、ファイル共有システムは動作の自律モードに戻る遷移をする。
2015517698.tif 000002
【特許請求の範囲】
【請求項１】
ファイル共有システムにおけるピアのスウォームにおいてピアが費やす平均時間を制御する方法であって：
前記スウォームにおける動作の自律モードを確立する段階と；
第一の閾値において前記自律モードから動作のユニバーサル・モードに変わる段階と；
第二の閾値において前記ユニバーサル・モードから前記自律モードに戻る段階とを含む、
方法。
【請求項２】
前記自律モードが、ピアの前記スウォーム内のピアの間でファイルを共有することを含む、請求項１記載の方法。
【請求項３】
前記ユニバーサル・モードが、異なるスウォームの束の間でファイルを共有するピアを含む、請求項１記載の方法。
【請求項４】
前記第一の閾値が前記スウォームが閾値サイズまで増大することを含む、請求項１記載の方法。
【請求項５】
前記第一の閾値サイズが通常の動作サイズの三倍である、請求項４記載の方法。
【請求項６】
前記第一の閾値サイズが通常の動作サイズと臨界サイズの和である、請求項４記載の方法。
【請求項７】
前記第二の閾値が、欠けているファイル片が前記スウォーム中のピアの少なくとも10パーセントによって保持されている状況を含む、請求項１記載の方法。
【請求項８】
ファイル共有システムをモニタリングおよび制御する装置であって：
前記ファイル共有システム上の一つまたは複数のピア装置と通信するためのネットワーク・インターフェースと；
ピアのスウォームのサイズおよび前記スウォームによって要求されるファイル片を有するピアの数を決定するプログラムを実行するプロセッサと；
前記プログラムを記憶するために前記プロセッサにとって利用可能であるメモリとを有しており、
前記プログラムが前記プロセッサによって実行されたとき、前記プログラムは、前記スウォームにおける動作の自律モードを確立し、第一の閾値に際して自律モードからユニバーサル・モードに変わり、その後、第二の閾値に際して前記ユニバーサル・モードから前記自律モードに戻る、
装置。
【請求項９】
前記プロセッサは、前記スウォームのサイズが前記第一の閾値を満たすときに、前記自律モードから前記ユニバーサル・モードに変化する、請求項８記載の装置。
【請求項１０】
前記プロセッサは、前記スウォームによって要求されるファイル片を有するピアの数が前記第二の閾値を満たすときに前記ユニバーサル・モードから前記自律モードに戻る、請求項８記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願への相互参照
本願は、2012年5月4日に出願された「Stable  and  Scalable  Universal  Swarms」と題する米国仮出願第61/687,965号への優先権を主張するものであり、同出願の内容はここに参照によって、あらゆる目的についてその全体において組み込まれる。
【０００２】
分野
本発明は、ファイル共有システムの効率的な運用に関する。詳細には、本発明は、ファイル共有システムにおけいてピアが費やす時間の短縮に関する。
【背景技術】
【０００３】
ビットトレント（BitTorrent）は、オンラインでファイルを共有するために何百万ものインターネットユーザーによって使用される、最も人気のあるピアツーピア・プロトコルの一つである。簡単にいうと、シードと称される区別される（distinguished）ユーザーから単一のファイルをダウンロードすることに関心のある諸ピアが、いうところのスウォーム（swarm）をなす。区別されるシード・ユーザーは完全なファイルのコピーをもつ。ピアは、所望されるファイルの諸片〔ピース〕を区別されるシード・ユーザーからダウンロードする。スウォーム内のピアは自分たちがアップロードおよびダウンロードするファイル片（またはチャンク）を互いと交換する。それにより、各ピアはクライアントおよびサーバーの両方の作用をし、スウォームの総合的なアップロード容量に寄与する。
【０００４】
シードのアップロード容量が毎秒U片であるとすると、スウォームが無限大まで増大することなくサポートされることのできるピアの最も大きな最大到来レート（arrival  rate）λがある。直観的には、はいってくるピアがあるたびにスウォームの総合的なアップロード容量が増すので、ビットトレントは高い到来レートをサポートするものと期待される。
【０００５】
ビットトレントの安定性領域を決定することは、長い間未解決の問題であった。スウォームが安定なままであるのは、λ＜Uのときかつそのときのみであることが知られている。すなわち、ピアの到来レートはシードのアップロード容量を超えることはできない。ピアがリーチャー（leecher）として作用し、ファイルをダウンロードした後すぐに離脱するセットアップを考える。その場合、λ＞Uならば、単一の片がきわめてまれになることがありうる。この場合、すべての到来するピアはこの欠けている片以外のすべての片を迅速にダウンロードするが、この欠けている片はシードからしか取得できない。ピアは非常に長時間待ってそれを取得し、システムを抜け、結果として、スウォーム・サイズは無限大に増大する。
【０００６】
この現象は欠損片シンドロームとして知られており、ビットトレントのスケーラビリティーを損なう。ビットトレント・スウォームの総合的なアップロード容量は新たなピアが到来するにつれて増大するものの、欠損片シンドロームのため、この容量は極端に不十分にしか活用されない。実際に、このシンドロームが発生すると、シードのアップリンクがシステム・ボトルネックとなる。
【発明の概要】
【発明が解決しようとする課題】
【０００７】
これに鑑み、ビットトレントの安定性領域を増すための一つの手法は、複数の自律的スウォームを一緒に束ねてユニバーサル・スウォームにすることである。このセットアップでは、ピアはやはり関心のあるファイルを取得すると離脱するが、システムにいる間に、片を記憶し、異なるスウォームに属するピアと交換する。
【０００８】
直観的には、そのようなスウォーム間交換は、普通ならアイドルのままとなるところのスウォーム帯域幅を活用する。欠けている片を位置特定することのできないピアは自分の利用可能な帯域幅を他のスウォームを支援するために寄与することができる。よって、単一のシードをもつユニバーサル・スウォームは、自律的なスウォームに比べ、増大した安定性領域を示す。しかしながら、異なるスウォームと片を共有することは、安定性と平均滞留時間、すなわち、ピアがシステムにおいて費やす時間との間のトレードオフを導入しうる。帯域幅の一部を関心のない片のために消費することにより、ピアは自分が所望するファイルを取得するためにより長い時間ががかることになりうるのである。このように、ユニバーサル・スウォームの増大した安定性領域には、増大した遅延という代償が伴い、その遅延は束ねられるスウォームの総数とともにスケーリングされる。すなわち、スウォームの数が多いほど、遅延が大きくなる。
【０００９】
この概要は、下記で詳細な説明においてさらに説明される概念のセレクションを単純化した形で紹介するために与えられている。この概要は、特許請求される主題のキーとなる特徴または本質的な特徴を同定するために意図されたものではなく、特許請求される主題の範囲を制限するために使われることも意図されていない。
【課題を解決するための手段】
【００１０】
欠損片シンドロームを回避するためにユニバーサル・スウォームを確立することにおいて経験される増大した滞留時間に対処するために、本発明は、証明可能な形で安定性領域を拡大し、遅延に影響しない、修正されたファイル共有システム設計を含む。具体的には、スウォームの数がファイル中の片の数のオーダーである限り、ピアは最小限の滞留時間、すなわちスウォームが一緒に束ねられなかったとした場合と同じオーダーの滞留時間を経験する。ファイル片は実際上、典型的には数千を数えるので、これはかなりの数のスウォームを、改善された安定性および低い遅延の両方をもってサポートすることを許容する。さらに、ピアが自分のファイルを取得する際に増大した遅延を経験しないように設計されることができる。
【００１１】
本発明のある側面では、システムが自律的スウォーム・モード挙動とユニバーサル・スウォーム・モード挙動との間で入れ替わることを許容する複数の閾値片選択ポリシーが作成される。具体的には、システム・サイズが小さいときは常に、各スウォームが自律的に行動し、シードはそのアップロード容量を異なるスウォームに均等に分配し、その間、各スウォームにおけるピアは同じスウォーム内の他のピアにのみ接触し、自分が関心のある片のみを受信する。しかしながら、システム・サイズが大きくなると（すなわち、欠損片シンドロームが起こると）、システムはユニバーサル・モードに切り換えられ、ピアは他のスウォームのピアに接触し、互いおよびシードから当該ファイルの任意の片を受信する。ユニバーサル・モードへの切り換えにより、システムが安定化され、結果的に自律モードに導き戻されることが保証される。
【００１２】
本発明の追加的な特徴および利点は、付属の図面を参照しつつ進められる例示的な実施形態の以下の詳細な説明から明白になるであろう。
【図面の簡単な説明】
【００１３】
本発明の上記の概要および例示的な実施形態の以下の詳細な説明は、付属の図面との関連で読まれるときによりよく理解される。付属の図面は、特許請求される発明に関する限定としてではなく、例として含められている。
【図１】本発明のための環境のはたらきをするピア・コンピュータの実施形態を示す図である。
【図２Ａ】自律モードの動作のパフォーマンスを示す図である。
【図２Ｂ】ランダム新規（RN:  random  novel）ポリシーを使うユニバーサル・モードの動作のパフォーマンスを示す図である。
【図２Ｃ】最もまれなものが先（RF:  rarest  first）ポリシーを使うユニバーサル・モードの動作のパフォーマンスを示す図である。
【図３Ａ】種々の片選択ポリシーについての自律モードにおける平均滞留時間を示す図である。
【図３Ｂ】各スウォームがk片のファイルを要求するピアを含むユニバーサル・モードにおいて、平均滞留時間をスウォーム・サイズに対して示す図である。
【図３Ｃ】各スウォームがk片のファイルを要求するピアを含む本発明の原理を使っての平均滞留時間を示す図である。
【図４】本発明の諸側面に基づく使用の例示的な流れ図である。
【図５】本発明の諸側面に基づく例示的なファイル・システム・スウォーム追跡器を示す図である。
【発明を実施するための形態】
【００１４】
さまざまな例示的な実施形態の以下の記述において、付属の図面に参照がなされる。付属の図面は詳細な説明の一部をなし、例解として、本発明が実施されうるさまざまな実施形態が示されている。本発明の範囲から外れることなく、他の実施形態が利用されてもよく、構造的および機能的修正がなされてもよいことは理解しておくものとする。
【００１５】
図１は、本発明の実装のための環境としてのはたらきができるファイル共有システム１００を描いている。図１は、ビットトレント様のファイル共有システムを示しており、ここでは四つのピアが示されている。当業者は、任意の数のピア装置が相互接続されていることができることを認識する。ピアA  １０２は、ピアB  １０４、ピアC  １０６、ピアD  １０８およびスウォーム追跡器１２０と同様に、ネットワーク１３０に接続されている。ネットワーク１３０は、イントラネットまたはインターネットなど、複数のネットワーク装置をサポートするいかなる形の私設または公共ネットワークであってもよい。もう一つの実施形態では、ネットワーク１３０は、複数の無線装置をサポートする無線ネットワークであってもよい。ピアA、B、CおよびDは、ネットワーク１３０を通じて他のネットワーク装置に情報を転送する機能をもつ例示的なネットワーク装置である。そのようなネットワーク装置の例は、リモート端末、パーソナル・デスクトップ・コンピュータ、ラップトップ・コンピュータまたはネットワーク・インターフェースをもつ任意の型のコンピューティング装置を含む。ピアA、B、CおよびDはネットワーク１３０に有線接続されるかまたはネットワーク１３０に無線接続されることができ、またはその両方の組み合わせができる。スウォーム追跡器１２０は、区別されたユーザーまたはシードとして行動できるネットワーク接続された装置である。スウォーム追跡器は、ピアがスウォームに応答する仕方に影響することによって、システム１００の動作を決定する機能を含む。スウォーム追跡器は、システム１００のパフォーマンスをモニタリングすることによっておよびシステム１００の動作のモードを制御することによってファイル共有システム１００のための中央集中されたコントロールのはたらきをする。
【００１６】
図１におけるようなあるビットトレント様システムでは、あるファイルを集めようとしている諸ピアが群がって単一のスウォームを形成する。これは自律モードと呼ばれる。しかしながら、本稿で説明しているように、欠けている片を持っているピアがスウォームを抜けてしまうと、スウォーム内の残りのピアはその欠けているファイル片を取得できなくなり、スウォームは制御不能に増大することがある。複数のスウォームからなる別のビットトレント様ファイル共有システムでは、各スウォーム中のピアが同じファイルをダウンロードすることを希望し、すべてのファイルは単一のシードによって記憶される。異なる複数のスウォーム中のピアが協働し、それによりユニバーサル・スウォームをなす。これは、ユニバーサル動作モードと呼ばれる。ファイル片はすべてのスウォームを横断して共有される。各ピアは異なるスウォームからの他のピアに接触し、該他のピアに自分が担持している片を転送する。さらに、シードはピアが明示的に要求していない片をアップロードしてもよい。にもかわらず、ピアは、関心のあるファイルのすべての片を受信したらすぐに離脱する。下記では、ユニバーサル・モードにおけるこのピアおよびシード挙動について詳細に述べる。
【００１７】
区別されるピア、つまりシードは、常に存在し、すべての要求されるファイルのコピーを保持していることを想起されたい。ファイルは等しいサイズの片に分割される。
【００１８】
【数１】
2015517698.tif 000003
によってシードが保持しているすべての片の集合を定義する。ファイルCをこの集合Fの空でない部分集合として定義する。すなわち、
【数２】
2015517698.tif 000004
（ここで、2FはFの冪集合）。ファイルCをダウンロードすることに関心のあるピアの集合をファイルCのスウォームという。このスウォーム内のピアは、レートλCをもつポワソン過程に従って到来し、到来は異なるスウォーム間では独立である。Cによって、その到来レートが0でないファイルの集合を表わす。すなわち、
【数３】
2015517698.tif 000005
また、
【数４】
2015517698.tif 000006
によって、システムにおける総到来レートを表わす。C中の諸集合が共通部分をもたないことは必須ではない。よって、我々のモデルは自然に、到来するピアが複数のファイルに関心をもつシナリオをも捉える。
【００１９】
各ピアはキャッシュを維持しており、該キャッシュ内にダウンロードした片を記憶する。ピアは空のキャッシュをもって到来し、各ピアのキャッシュはF中のK個の片すべてを保持するのに十分な大きさであるとする。ピアは、自分が関心のあるファイルのすべての片を取得したらすぐに離脱する。ピアを、（ａ）それが属するスウォームおよび（ｂ）そのキャッシュ内の片の集合に従って型に区分する。ここで、片の集合Sを保持しているスウォームCのピアは型〈C,S〉であると表わされる。これらの想定によれば、システムには型〈C,S〉∈Tのピアしか存在しない。ここで、Tは次のように定義される。
【００２０】
【数５】
2015517698.tif 000007
システムから永遠に不在の何らかの片
【数６】
2015517698.tif 000008
について、シードを
【数７】
2015517698.tif 000009
の型であると設定し、
【数８】
2015517698.tif 000010
によって、シードを含めた、型の拡張された集合を表わす。
【００２１】
〈C,S〉∈Tとして、n〈C,S〉によって、現在のシステムにおける型〈C,S〉のピアの数を表わす。するとピアの総数はn:＝Σ〈C,S〉∈T  n〈C,S〉によって与えられる。システムの状態を、各型におけるピアの数のベクトル
【数９】
2015517698.tif 000011
によって表わし、
【数１０】
2015517698.tif 000012
があらゆる可能なベクトルnの集合を表わすとする。さらに、
【数１１】
2015517698.tif 000013
によって、そのキャッシュ内に片の集合Sをもつピアの数を表わす。
【００２２】
【数１２】
2015517698.tif 000014
すると、システムの発展は状態空間Dをもつマルコフ過程
【数１３】
2015517698.tif 000015
によって記述される。この過程の遷移レートは、シードおよびピアによって片がどのようにアップロードされるかに依存する。これらの遷移レートを形式的に定義する前に、まずどのように片のアップロードが行なわれるかを述べる。
【００２３】
シードは、レートUのポワソン過程の諸時点において片をアップロードする。そのような時点において、シードは、（すべてのスウォームを横断して）システム内に存在するすべてのピアのうちでランダムに一様に選択されるピアに接触し、F内のある片をこのピアに対して複製する。同様に、レートμ＞0のポワソン過程に従う諸時点において、各ピアは別のピア（やはりすべてのピアのうちでランダムに一様に選択される）に接触し、そのキャッシュから片を複製する。
【００２４】
源（ピアまたはシードのいずれか）が受信ピアに接触するときに複製される片は、源の片選択ポリシーによって決定される。形式的には、型
【数１４】
2015517698.tif 000016
の源についての片選択ポリシーは
【数１５】
2015517698.tif 000017
によって表わされる。これはF×T×Dから[0,1]への関数である。関数h〈C,S〉(i,〈C',S'〉,n)は、（ａ）片受信者が型〈C',S'〉であり、（ｂ）システム状態が接触時においてnであるとしたときの、複製される片がiである確率である。
【００２５】
ポリシーについて以下の自然な想定がなされる：（ａ）受信者が源のキャッシュの全部の片を所有している場合には、片の複製はされない、そうでない場合には、（ｂ）源のキャッシュにおいて、受信者のキャッシュにおいて不在であるちょうど一つの片が複製される。これらの想定は、ポリシーh〈C,S〉が次式を満たさなければならないことを含意する。
【００２６】
【数１６】
2015517698.tif 000018
式(4a)および(4b)によって定義されるポリシーの族はきわめて広いことを注意しておく。型
【数１７】
2015517698.tif 000019
の源および型〈C',S'〉∈Tの受信者を考える。その際、次のものがこの族のポリシーの例である：
・ランダム新規［RN:  Random  Novel］：
【数１８】
2015517698.tif 000020
であれば、源は集合
【数１９】
2015517698.tif 000021
からランダムに一様に選ばれた片を複製する。
・最もまれなものが先［RF:  Rarest  First］：まず片i∈Fの利用可能性を、それを保持しているピアの数、すなわちΣS:i∈S  nsとして定義する。源は、
【数２０】
2015517698.tif 000022
内の、最も小さな利用可能性をもつ片を複製する。利用可能性が同じなものについてはランダムに一様に決める。
・優先度最もまれなものが先［PRF:  Priority  Rarest  First］：源は、受信者のスウォーム内の片に次のように優先順位付けする。
【００２７】
【数２１】
2015517698.tif 000023
であれば、源は
【数２２】
2015517698.tif 000024
内の最も小さな利用可能性をもつ片を複製する。
【００２８】
【数２３】
2015517698.tif 000025
が空だが
【数２４】
2015517698.tif 000026
は空でない場合には、源は、最もまれなものが先と同様にする。
・優先度ランダム新規［PRN:  Priority  Random  Novel］は同様に定義できる。
【００２９】
同じ型の源は同じポリシーを適用するとする。システムの片選択ポリシーは、各
【数２５】
2015517698.tif 000027
をインデックスとするh〈C,S〉のタプルによって表わされる。ここで、型〈C,S〉内のすべての源はタプル内のポリシーh〈C,S〉を適用する。型を横断して異なるポリシーhが共存することができる。たとえば、ピアが「優先度最もまれなものが先」を実装する一方、シードは「ランダム新規」ポリシーを実装してもよい。ランダム新規とは対照的に、RFおよびPRFポリシーはシステム状態nに依存し、グローバル属性（つまり、
【数２６】
2015517698.tif 000028
における片の利用可能性）の知識を必要とし、よって分散式に実装するのがより困難である。たいていの現在のビットトレント実装を含む中央集中式のセッティングでは、利用可能性はスウォーム追跡器と呼ばれる区別されるピアによってモニタリングされる。あるいはまた、おしゃべり（gossiping）またはサンプリング（sampling）のような分散式の技法が、利用可能性の推定値を得るために使用されることができる。本発明の主たる安定性結果は、シードはランダム新規［RN］ポリシーを適用し、一方、型〈C,S〉のピアは式(4a)および(4b)を満たす任意の片選択ポリシーh〈C,S〉を選びうることを想定する。
【００３０】
n(t)∈Dが時刻tにおけるシステムの状態を表わし、
【数２７】
2015517698.tif 000029
がマルコフ過程であることを想起されたい。片選択ポリシーについての上記の記法を使うと、その遷移レートは形式的に以下のように定義できる。シードがランダム新規片選択ポリシーを実装し、一方、任意の〈C,S〉∈Tについて、型〈C,S〉のピアが式(4a)および(4b)を満たす任意のポリシーh〈C,S〉を実装するとする。状態nを与えられたとして、Tc(n)は新たなピアがスウォームCに到来することから帰結する新たな状態であるとする。
【００３１】
【数２８】
2015517698.tif 000030
であるような〈C,S〉∈Tおよびn〈C,S〉≧1であるような状態nが与えられたとして、T〈C,S〉,i(n)は型〈C,S〉のピアが片iをダウンロードすることから帰結する新たな状態を表わすとする。生成子行列
【数２９】
2015517698.tif 000031
の正の要素は次式によって与えられる。
【００３２】
【数３０】
2015517698.tif 000032
マルコフ過程としてモデル化されるシステムについての安定性および不安定性の以下の標準的な定義を使う。システムが一時的（transient）でありかつピアの数が確率１で無限大に収束する場合、そのシステムは不安定である。システムが正再帰的（positive  recurrent）でありかつ有限の平均ピア数をもつ場合、そのシステムは安定である。
【００３３】
上記のシステムについて、単一の自律的スウォームの場合、すなわち、すべてのピアがファイルC＝Fをダウンロードすることに関心のあるシステムの場合、そのようなシステムの安定性領域がランダム新規［RN］ポリシーのもとで次のように決定されることが知られている：
定理１：F内のすべての片を要求するピアの単一のスウォームであって、シードおよびピアの両方がランダム新規片選択ポリシーに従うものを考える。システムは、λF＜Uの場合に安定であり、λF＞Uの場合に不安定である。
【００３４】
また、λF＞Uのとき、いわゆる欠損片シンドロームが不安定の理由であることも知られている。上記で論じたように、このシンドロームは、システム内に、一つの欠けている片のほかはF内のすべての片を記憶している多数のピアがある（すべてのピアが同じ片を欠いている）ときに生じる。一クラブ（one-club）と称されるピアのこの集合が十分大きいときは、システムに到来する新たなピアの接触の大半はそのようなピアとなされることになる。よって、新たなピアは、迅速に、欠けている片以外のすべての片を取得し、こうして一クラブ集合に加わる。欠けている片を保持しているピアはほとんどないので、一クラブからの離脱はほとんどがシードによるアップロードのためである。結果として、一クラブの離脱レートはシードのアップロード・レートUに近い。λF＞Uなので、一クラブにおけるピアの増殖レートは正であり、この集合のサイズを無限大まで増大させ、不安定につながる。
【００３５】
上記の定理１は、複数スウォーム・システムの場合における直接的な系をもつ。具体的には、各スウォームが独立に、他のスウォームとは隔絶されて、自律モードで動作するとする。より具体的には、スウォーム
【数３１】
2015517698.tif 000033
内のピアは、同じスウォーム内の他のピアとのみ接触し、片を交換する。加えて、シードはそのアップロード容量を異なるスウォームにまたがって（可能性としては不均等に）分割し、各スウォームにその全容量の適切な割合をもってサービスする。最後に、スウォームCにおいて記憶され交換される片が集合C内の片である。定理１は、そのようなスウォームのそれぞれに対して直接当てはまり、よって各個別のスウォームの安定性を記述する。よって、次の系を検証するのは容易である：
系１：自律モードで動作している複数スウォーム・システムを考え、シードおよびピアの両方がランダム新規ポリシーに従って片をアップロードするとする。すると、
【数３２】
2015517698.tif 000034
の場合には、シードはシステムが安定であるようそのアップロード容量を割り当てることができる。さらに、
【数３３】
2015517698.tif 000035
の場合には、シードのアップロード容量のあらゆる割り当てについて、システムは不安定である。
【００３６】
異なる言い方をすると、自律モードで動作するとき、システムは、一定の到来レートをもつ有限個のスウォームをサポートできるだけである。最終的には、シードのアップロード容量が枯渇して、システムは不安定になる。上記の系は、シードのレートの各スウォームへの静的な割り当てを想定していることを注意しておく。本発明者らは、シミュレーションを通じて、各スウォームのサイズに比例する割り当ては欠損片シンドロームを防止しないことを観察した（図２ａ参照）。
【００３７】
複数スウォーム・システムは、ピアがスウォームを横断して他のピアに接触することを許容するよう動作し、該他のピアとファイル片を交換しうるシステムである。この型のシステム動作を単一スウォームのみにおいて動作するピアの場合と区別するために、複数スウォーム動作は、ユニバーサル・モードでの動作またはユニバーサル・スウォームと称される。
【００３８】
本発明者らは、式(5)のマルコフ過程の安定性領域が、ユニバーサル・スウォームが本当に改善された安定性を呈することを示した。
【００３９】
定理２：シードがランダム新規ポリシーを実装し、型〈C,S〉のピアが式(4a)および(4b)を満たす任意のポリシーh〈C,S〉を実装するユニバーサル・スウォームを考える。すると、（ｉ）
【数３４】
2015517698.tif 000036
であればシステムは不安定であり、（ｉｉ）
【数３５】
2015517698.tif 000037
であればシステムは安定である。
【００４０】
ユニバーサル・スウォームを考えるだけでなく、定理２は、定理１を、ピアが式(4a)および(4b)のもとで任意の片選択ポリシーを実装する場合に拡張する。単一スウォーム・セットアップに適用される定理２の直接的な系は、定理１の安定性領域がそのようなポリシーにも拡張されるということである。また、この定理はシードが「ランダム新規」ポリシーを使うことを想定していることも注意しておく。本発明者は、シードにおいて「最もまれなものが先」ポリシーを使うことも同じ安定性領域を呈することを判別した。
【００４１】
この定理が、スウォームを一緒に束ねることが安定性領域の有意な増大を与えることを含意していることを注意しておく。このことを見るために、諸ファイル
【数３６】
2015517698.tif 000038
が共通部分をもたないとき、式(7)は
【数３７】
2015517698.tif 000039
となることに注目されたい。これは、系１によって与えられる、自律モードで動作するシステムによって達成されるものより大きな安定性領域を定義する。具体的には、スウォームを一緒に束ねることによって、本発明者らは、スウォームの数が増すにつれて安定性領域が著しくよくスケーリングすることを見出した。単一のシードが、一定の到来レートをもつ無制限の数のスウォームをサポートでき、安定性領域には影響はない。しかしながら、スウォームを一緒に束ねることは、遅延が増大するという代償を伴う。よって、スウォームの数は実際上は好きなだけ大きくするわけにはいかない。
【００４２】
よって、本発明は、ユニバーサル・モードと自律モードの間で入れ替わることによって、多数のスウォームについての小さな遅延を保証しつつユニバーサル・スウォームと同じ安定性領域を維持するハイブリッド・システムを含む。本発明は、システムが自律およびユニバーサルのスウォーム挙動の間で入れ替わることを許容する、複数の閾値片選択ポリシーを実装する。具体的には、システム・サイズが小さいときは常に、各スウォームが自律的に行動し、シードはそのアップロード容量を異なるスウォームに均等に分配し、その間、各スウォームにおけるピアは同じスウォーム内の他のピアにのみ接触し、自分が関心のある片のみを受信する。しかしながら、システム・サイズが大きくなると（すなわち、欠損片シンドロームが起こると）、ユニバーサル・モードに切り換わり、ピアは他のスウォームのピアに接触し、互いおよびシードからF内の任意の片を受信する。ユニバーサル・モードへの切り換えによって、システムが安定化され、結果的に自律モードに導き戻されることが保証される。本発明者らは、ハイブリッド・システムの安定性領域が、どの片選択ポリシーが諸ピアにおいて実装されているか（たとえば、「ランダム新規」、「最もまれなものが先」または「優先度最もまれなものが先」またはそれらの組み合わせ）に関わりなく同じままであることを観察した。
【００４３】
ハイブリッド・システムは、種々の片選択ポリシーについてまたスウォーム・パラメータにおける滞留時間の依存性についてスウォーム挙動を調べたシミュレーションを使って、ユニバーサル・スウォームのパフォーマンスに関して評価された。上記と同様に、用語RF、RN、PRNおよびPRFはそれぞれ、「最もまれなものが先」、「ランダム新規」、「優先度ランダム新規」および「優先度最もまれなものが先」の片選択ポリシーに対応する。PRFおよびPRNは、システムが自律モードで動作するときにはRFおよびRNに帰着することを注意しておく。
【００４４】
定理１および定理２は、それぞれが異なる3片の集合を要求する3つのスウォームを含むシステムについて、自律およびユニバーサル・モードにおいてシステム・サイズnの発展を調べることによって検証できる。シード・レートはU＝3.1であり、各スウォームにおける到来レートはλ＝3.0である。定理１および定理２は、この領域では、ユニバーサル・システムは安定であるが、自律モードは不安定であることを含意することを注意しておく。
【００４５】
図２ａは、シードおよびピアにおけるポリシーの種々の組み合わせについて、シードが統計的にそのアップロード・レートの1/3を各スウォームに割り当てるときの、自律モードにおけるシステム・サイズの発展を示している。すべてのシミュレーションは空のシステムから始まる。シードおよびピアの両方において「最もまれなものが先」ポリシーを適用することがやや小さなシステム・サイズにつながるものの、欠損片シンドロームは四つすべての場合において起こる。各スウォームがそのサイズに比例するレートで片を受け取るようシードがそのレートを動的に割り当てるようにしてこれらの実験を繰り返すと、図２ａの挿入図のプロットになる。これは、このセットアップでも不安定が残ることを示している。
【００４６】
これらの実験はユニバーサル・モードにおいて繰り返される。今回はシステムを、一クラブをなす8500個のピアを含む初期状態から出発させる。該一クラブでは、すべてのピアは単一のスウォームに属し、同じファイルを要求し、要求している一つの片以外の9個の片すべてをそのキャッシュに記憶している（みな同じ片を欠いている）。図２ｂは、シードが「ランダム新規」ポリシーを適用するときのシステム発展を示している。たしかにシステムは105時間単位後に安定化しており、定理２を確証している。図２ｃに示されるように、シードが「最もまれなものが先」ポリシーを適用するときは、システムはより速く（104時間ユニットのオーダーで）安定化する。ここで、シードおよびピアの両方で「最もまれなものが先」の場合がシステムを最も速く（ほぼ3・104時間ユニットで）安定化させる。興味深いことに、（PRNまたはPRFを通じて）ピアにおいて片を優先順位付けすることは、より遅い安定化につながる。これはまさに、これらのポリシーがシステム内の片の多様性を減らすからである。
【００４７】
シード・レートU=2.9での上記の同じ実験を考える。各スウォームにおける到来レートはλ＝3なので、定理２は、シードがランダム新規ポリシーを適用するときはシステムが不安定であることを述べる。一つの問題は、シードまたはピアにおいてどの片選択ポリシーが使われるかに依存して、この場合、どのくらい迅速に欠損片シンドロームが現われるかである。ランダム新規（RN）または最もまれなものが先（RF）ポリシーを適用するシードについて、以下の実験が実施された。シミュレーションは、初期システム・サイズn0をもって始まる。ここで、初期状態は一クラブをなす（すなわち、一つを除いてすべての片を記憶している）すべてのピアを含む。シミュレーションは、システム・サイズが閾値である最大（2000＋n0,2n0）に到達するか、シミュレーション時間が107時間単位に達するかのいずれか先に起こるほうのときに終了させられる。ピアにおける四つのポリシー（RN,RF,PRN,PRF）のそれぞれについて、この実験はまず空の初期状態n0＝0をもって実施された。実験が107単位内に閾値に達しない場合には、n0を100増やして実験が繰り返される。このようにして、臨界的な一クラブのサイズが特定される。システムがそのサイズの一クラブをもつ状態に達する場合には、システムは不安定になる。
【００４８】
シードがRNポリシーを使う場合についてのシミュレーション結果が表１の上半分にまとめられている。欠損片シンドロームは実際に、一クラブが終了時刻におけるピア集合の90%より多くを含む臨界的な初期条件において現われている。ピアがRF以外のいずれかのポリシーを使うときには、臨界的な一クラブのサイズは0である。対照的に、ピアがRFポリシーを使うときは、シンドロームはn0＝500のときにのみ現われる。実際、「最もまれなものが先」ポリシーを使うとシステムにおける片の多様性が改善され、その結果、臨界的な一クラブ・サイズに達するのがより難しくなる。この挙動は、シードがRNポリシーではなくRFポリシーを使うときには一層顕著になる。表１の下半分に示されるように、シードにおいてRFポリシーを使うことは、片の多様性が十分高く、臨界的な一クラブ・サイズが2000ないし8000個のピアの間にあることを保証する。
【００４９】
決定的なことに、臨界値より小さな初期サイズから出発するすべてのシミュレーションにおいて、次の非常に興味深い挙動が観察される：システム・サイズは実際に200より下のあるサイズまで減少し、107時間単位全体の間この値の付近に留まる。これは、システムは表１の場合のいずれにおいても明らかに安定ではないが、シードまたはピアのいずれかでRFポリシーを適用することは、準安定性を与えることを含意している。臨界的な一クラブ・サイズが存在するものの、その値は十分大きく、システムがたいていの時に動作する「典型的な」サイズ（上記の諸シミュレーションでは〜200個のピア）からその値に到達するのはきわめて困難となる。
【００５０】
【表１】
2015517698.tif 000040
滞留時間（sojourn  time）は、ピアが所望されるファイルを取得するのにファイル共有システムにおいて費やす時間である。それぞれ3個の片をもつ3つのスウォームを含むユニバーサル・システムについての平均滞留時間を決定できる。シード・アップロード・レートはU=3.0に設定され、到来レートλは各スウォームにおいてi＝1,…,10についてλ＝U(1−1/2i)のように変えられることができ、安定性領域内に留まるが下からUに接近する。図３ａは、種々の片選択ポリシーについてユニバーサル・モードにおける平均滞留時間を、1/(U−λ)（この値が大きいほどよりUに近いλに対応する）の関数としてプロットしている。λがUに近づくにつれ、シードにおけるRNポリシーのもとでの滞留時間はかなり増大するが、RN-RFの場合、すなわちピアが「最もまれなものが先」ポリシーを使うときは例外となっている。シードがRFポリシーを使う四つすべての場合について、滞留時間は実際上、到来レートがUに近づくにつれて一定のままである。これは、準安定性により、シードがRFポリシーを使うときには、たとえλ＞Uであっても、システム・サイズがたいていの時に小さいままであるという事実と整合する。よって、到来レートが下からUに近づく際の滞留時間の鋭い上昇がないのである。
【００５１】
図３ｂは、k∈{10,30,60}について各スウォームがk片のファイルを要求するピアを含む場合について、ユニバーサル・モードにおける平均滞留時間をスウォーム・サイズLに対してプロットしたものである。各シミュレーションにおける片の総数はK＝kLであることを注意しておく。まず、kのすべての値にわたって、平均滞留時間はスウォームの数が増すにつれて線形に増大することに注目されたい。同様に、滞留時間は、スウォーム当たりの片の数kにも比例して増大する。ピアが経験する遅延はK＝kLのオーダーであり、よってスウォームの数Lとともにうまくスケーリングしない。換言すれば、ユニバーサル・モードにおいてスウォームを一緒に束ねることによってもたらされる向上した安定性は、遅延の増大という代償を伴う。本発明を使うと、遅延は、ユニバーサル・モードと自律モードの間で交互する本発明のハイブリッド・アプローチを使うことによって、実際にはLの幅広い範囲の値について抑制されることができる。
【００５２】
上記のシミュレーション結果の解釈は、準安定なスウォームにおいては、二つの重要なシステム・サイズがあることが示唆される：システムがたいていの時にその近辺に留まるサイズである動作サイズnopと、いったん到達するとシステムを不安定性へと導く一クラブのサイズである臨界サイズn0である。これら二つのサイズが互いから十分遠く離れている場合には、システムは準安定性を示す。動作サイズに近いとき、システムが、欠損片シンドロームが現われはじめる臨界状態に達するのには長い時間がかかる。
【００５３】
本発明者らは、（ａ）システムが単一のスウォームを含み、（ｂ）到来レートがλ＞Uであり、（ｃ）シードおよびピアの両方がRFポリシーを使うときに、nopおよびn0のいくつかの簡単な推定を導出した。具体的には、そのような単一スウォーム・システムの動作サイズは
【数３８】
2015517698.tif 000041
によって推定できる。一方、いったん到達すると不安定性に導く臨界システム・サイズは
【数３９】
2015517698.tif 000042
によって近似できる。
【００５４】
これら二つの推定を使って、幅広い範囲のスウォーム数Lについて滞留時間が小さいままであることを保証しつつ、ユニバーサル・スウォームの増大した安定性領域を達成する発明的なハイブリッド・システムが達成できる。ハイブリッド・システムは、諸スウォームがシードのアップリンク容量のU/Lの部分を分有しつつ孤立して動作する自律モードと諸スウォームが一緒に束ねられるユニバーサル・モードとの間で交互する。具体的には、それぞれがk＝K/L個の片のファイルを要求するL個のスウォームをもつ複数スウォーム・システムを考える。システムは、次の規則に従って上記二つのモードの間で切り替わる：
（ａ）自律モードにある場合、いずれかの単一のスウォームがnop＋max(n0,2nop)より大きなサイズをもつ場合に、システムはユニバーサル・モードに切り替わる。すなわち、いずれかの単一のスウォームが(n0＋nop)または3nopのいずれよりも大きなサイズをもつ場合に、ユニバーサル・モードに切り替わる。
（ｂ）ユニバーサル・モードにある場合、スウォームによって要求される各片が該スウォーム内の少なくともmax(nop/10,1)個のピアによって保持されている場合に、システムは自律モードに切り替わる。すなわち、いずれかの単一のスウォームが(nop/10)または1のいずれよりも大きなサイズをもつ場合に、システムは自律モードに戻る切り替えをする。
ここで、nop、n0は、アップロード・レートU/Lおよび片の数kを想定して、それぞれ式(8)および(9)によって計算される。
【００５５】
直観的には、スウォーム・サイズがnop＋n0より大きくなるなど、欠損片シンドロームが現われているという強い証拠があるときにユニバーサル・モードが適用される。各スウォームにおいて十分な多様性があるとき、すなわち、各片が少なくとも動作状態におけるピア集合の少なくとも10パーセント（10分の1）によって保持されるときに、システムは自律モードに復帰する。
【００５６】
このハイブリッド・システムの片選択ポリシーは式(4a)および(4b)を満たすので、ユニバーサル・スウォームの増大した安定性領域を呈する。図３ｃは、スウォームの数が増すときのこのハイブリッド・システムの滞留時間を示している。図３ｂとは対照的に、f＝30およびk＝60について、滞留時間はL＝1のときに達成される値（それぞれ〜33および〜64時間単位）に近いままである。k＝10については、滞留時間はやはりL＝1のときに達成される値（〜12時間単位）に近いが、L＝12よりあとでは線形に増大し始める。
【００５７】
これらの改善された滞留時間が現われるのは、まさにシステムの準安定性のためである。実際、諸スウォームは、たいていの時には、他のスウォームの介入なしにうまく機能する。これがL＝1である場合と同じ遅延を経験するゆえんである。U/L＜λなので、自律モードは不安定であるが、欠損片シンドロームが起こる数少ない（まれな）機会においては、スウォームを一緒に束ねることにより、システムが迅速に安定化し、その動作サイズに復帰することが保証される。
【００５８】
図３ｃのk＝10について観察される曲線の屈曲部（knee）は、この挙動が任意に大きなLについて維持できるわけではないことを示唆している。式(8)および(9)は、Lがどのくらい大きくなれるかについて近似的な答えを与える助けとなる。実際、システムが準安定であるためには、臨界的な一クラブ・サイズが動作サイズより有意に大きくなければならない。欠損片シンドロームがめったに起こらないようn0＞2nopを要求し、k/(K−1)〜1とすると、L＝1のときの準安定性について次の経験式が得られる：KU/λ−U＞6。ここで自律モードにおける、それぞれがk＝K/L個の片を要求するL＞1個のスウォームを考えると、各スウォームは自律モードにおけるU/Lのアップロート・レートを得る。すると、上記の条件は
L＜U/6(λ−U/L)k〜kU/λ6
となる。換言すれば、ハイブリッド・システムは、Lが各スウォーム中の片の数kのオーダーである限り、小さな遅延でスウォームの数Lをサポートできる。ファイル中の片の数は典型的には数千の数になるので、これは上記のシステムが実際上、多数のスウォームについては短い滞留時間を維持できることを含意する。
【００５９】
図４は、本発明の諸側面に基づく例示的な流れ図４００を描いている。プロセス４００は、図１のスウォーム追跡器装置１２０のようなネットワーク装置によってモニタリングされ、制御される。最初、該装置は、ファイル共有システム構成設定においてピア・ネットワーク装置のスウォームを確立する。スウォームは、区別されるユーザー、シード装置またはピアによって供与される所望されるファイルの諸片を分かち合うよう動作する。ある実施形態では、シードはスウォーム追跡器装置１２０であってもよい。ステップ４０５では、スウォームは、一つまたは複数のスウォームが孤立して動作する自律モードで動作するよう確立され、諸ピアからなるスウォームにおける各ピアは、所望されたファイルの片を転送するために自分自身のスウォームのピアとのみ通信する。
【００６０】
ステップ４１０では、スウォーム追跡器は、自律モードに留まっている間にスウォーム・サイズをモニタリングおよび検出する。ファイル共有システムのモニタリングは、スウォーム追跡器のファイル共有ネットワーク・インターフェースを使って生起できる。ある実施形態では、スウォーム追跡器は、スウォーム・サイズを決定できるようネットワーク動作およびトランザクションをモニタリングおよび解析する処理機能を有する。ステップ４１５では、スウォーム・サイズが第一の閾値に比較される。ある実施形態では、第一の閾値は、nop＋「n0または2nopのいずれかの最大」より大きいサイズをもつスウォームとして定義される。すなわち、第一の閾値はnop＋n0または3nopの大きいほうとして定義される。ここで、上記で論じたように、nopは動作サイズであり、n0は臨界サイズである。スウォーム・サイズが第一の閾値より小さければ、プロセス４００はステップ４１０に戻り、スウォーム・サイズがモニタリングされ続ける。スウォーム・サイズが第一の閾値を満たす場合には、プロセス４００はステップ４２０に進む。
【００６１】
ステップ４２０では、システムは、複数のスウォームが一緒に束ねられ、一つのスウォームからのピアが所望されるファイルの片をあるスウォームにおけるピアから別のスウォームにおけるピアに転送しうるユニバーサル・モードに移行する。ある実施形態では、ユニバーサル・モードへの移行は、進行をモニタリングし、ピアがファイル共有システムにおいて動作する規則を制御するスウォーム追跡器を介して達成される。第一の閾値が満たされているステップ４２０の場合、スウォーム追跡器はピアが、種々のスウォームから所望されるファイル片を探求することを許容する。
【００６２】
ステップ４２５では、システム４００がユニバーサル・モードで動作させられる間に、スウォーム内のピアによって保持される片が検出される。ファイル共有システムのモニタリングは、スウォーム追跡器のファイル共有ネットワーク・インターフェースを使って生起できる。ある実施形態では、スウォーム追跡器は、あるスウォームにおける所望されるファイルの片をいくつのピアが保持しているかを検出できるようネットワーク動作およびトランザクションをモニタリングおよび解析する処理機能を有する。ステップ４３０では、第二の閾値が決定される。第二の閾値は、スウォームによって要求される各所望されるファイル片がスウォーム中の少なくともnop/10または１のいずれか大きいほうの数のピアによって保持されることが見出される場合に到達される。スウォーム内で所望されるファイル片を保持しているピアの数が第二の閾値より小さければ、プロセス４００はステップ４２５に戻って、スウォーム内のピアによって保持される所望されるファイル片がモニタリングされ続ける。スウォーム内のピアによって保持される所望されるファイル片が第二の閾値を満たす場合には、プロセス４００はステップ４３５に進む。
【００６３】
ステップ４３５では、システム４００は自律モードに遷移して戻る。この自律モードへ戻る切り換えは、ユニバーサル・モードでの動作はもはや必要とされないので、有利である。すなわち、欠損片シンドロームを回避するために、所望されるファイル片を含んでいる十分なピアがスウォーム内にある。これは、過剰な滞留時間を被ることなくすべてのピアについて自律モード動作が成功することを許容する。ステップ４３５から、システムは、自律モードにおける動作をモニタリングするためにスウォーム・サイズが検出されるステップ４１０に戻ってもよい。
【００６４】
図５は、ファイル共有に好適なネットワーク上で動作する例示的な装置５００を描いている。装置５００は、ファイル共有環境を制御し、モニタリングする。ある実施形態では、装置５００は図１のスウォーム追跡器１２０である。図５では、装置５００は典型的にはローカル・ユーザー・インターフェース５１０を含んでいてもよい。ローカル・ユーザー・インターフェースは、キーボード、マウス、ディスプレイ、USB接続などといった、ユーザーがプログラミングおよび装置動作制御を実施するための、当業者に知られている人間および電子インターフェースを含んでいてもよい。装置５００は、当業者に既知のように、ユーザー・インターフェース５１０を内部バス５１５のようなデバイスの内部回路と結合するためのインターフェース回路５２０を含んでいてもよい。プロセッサ５２５は装置５００のためにさまざまなインターフェースおよび資源を制御することにおいて支援する。これらの資源は、プログラムおよび／またはデータ記憶のために使われるローカル・メモリ５３５およびネットワーク・インターフェース５３０を含む。ネットワーク・インターフェース５３０は、装置５００がネットワークと通信できるようにするために使われる。ネットワークは装置５００がファイル共有システム上のピアとデータを交換することを許容する。たとえば、ネットワーク・インターフェース５３０は、図１のピア装置AないしDについて記述された機能のための有線または無線のインターフェースであることができる。装置５００は、図４の例示的な流れ図において記述したようなファイル共有ネットワークのモニタリングおよび制御を実施するために、プロセッサ５２５、メモリ５３５およびネットワーク・インターフェース５３０を利用する。
【００６５】
図１および図５においてスウォーム追跡器の実装について個別的な構成が示されているが、当業者は、諸コンポーネントの分散した機能、諸コンポーネントの統合およびピア装置とスウォーム追跡器との間の分散したプログラミングの使用といった実装オプションが存在することを認識するであろう。そのようなオプションは、図示され、記述されている構成の機能および構造と等価である。
【図１】
2015517698.tif 000043
【図２Ａ】
2015517698.tif 000044
【図２Ｂ】
2015517698.tif 000045
【図２Ｃ】
2015517698.tif 000046
【図３Ａ】
2015517698.tif 000047
【図３Ｂ】
2015517698.tif 000048
【図３Ｃ】
2015517698.tif 000049
【図４】
2015517698.tif 000050
【図５】
2015517698.tif 000051
【国際調査報告】
2015517698.tif 000052
2015517698.tif 000053
2015517698.tif 000054