(57)【要約】      （修正有）【課題】コンテンツセントリックネットワークにおけるデバイス同士の間のマニフェストの同期化に基づいてサービスディスカバリを容易にするシステムを提供する。【解決手段】局所デバイスは、遠隔デバイスの遠隔マニフェストに対応しているアドバタイズメントを受信する。マニフェストはサービスレコードのコレクションを表しており、アドバタイズメントは遠隔デバイスに対応しているサービスレコードを含む。局所デバイスは、局所マニフェストと遠隔マニフェストが同じネームスペースに対応しているとの判断に応答して、アドバタイズされたサービスレコードを局所マニフェストへ挿入することによって、その局所マニフェストを更新する。【選択図】図１
2015201179.tif 000002
【特許請求の範囲】
【請求項１】
プロセッサと、
前記プロセッサに連結されかつコンピュータ実行時に前記コンピュータに方法を実行させる命令を格納する記憶装置と、
を含む、
異常を検出するためのコンピュータシステムであって、
前記方法が、
局所デバイスにより、遠隔デバイスの遠隔マニフェストに対応している第１のアドバタイズメントを受信するステップであって、前記第１のアドバタイズメントが前記遠隔デバイスに対応しているサービスレコードを含むステップと、
局所マニフェストと遠隔マニフェストが同じネームスペースに対応しているとの判断に応答して、前記第１のアドバタイズメントのサービスレコードを前記局所マニフェストへ挿入することにより、局所デバイスの局所マニフェストを更新するステップと、
を含む、コンピュータシステム。
【請求項２】
前記方法が、遠隔デバイスの遠隔マニフェストに対応している第２のアドバタイズメントに対してクエリを送信するステップを更に含む、請求項１に記載のコンピュータシステム。
【請求項３】
前記方法が、前記局所デバイスの局所マニフェストに対応している第２のアドバタイズメントを送信するステップを更に含み、前記第２のアドバタイズメントが前記局所デバイスに対応しているサービスレコードを含む、請求項１に記載のコンピュータシステム。
【請求項４】
前記局所デバイスによって送受信されるパケットが、前記マニフェストを識別する経路指定可能なプレフィックス、前記パケットがデータの転送に対応していることを判断する識別子、前記パケットがデータのアドバタイズメントに対応していることを判断する識別子、前記マニフェストのルートハッシュ値、前記マニフェストにおけるサービスレコードのネーム、およびサービスレコードの一以上を示す請求項１に記載のコンピュータシステム。
【請求項５】
前記局所マニフェストを更新するステップが、前記第１のアドバタイズメントのサービスレコードのシリアル番号が前記第１のアドバタイズメントのサービスレコードと同じネームを有する局所マニフェストのサービスレコードのシリアル番号より大であるとの判断に応答して、前記局所マニフェストのサービスレコードの値を前記第１のアドバタイズメントのサービスレコードの値で更新するステップを更に含む請求項１に記載のコンピュータシステム。
【請求項６】
前記方法が、前記局所デバイスがマニフェストを含まないネットワーク上で初期し、前記局所デバイスに対応しているサービスレコードを作成し、前記サービスレコードから成る局所デバイスに対してマニフェストを作成するステップ、を更に含む請求項１に記載のコンピュータシステム。
【請求項７】
前記局所マニフェストのサービスレコードの活動時間（ＴＴＬ）が発生し次第、前記局所マニフェストからサービスレコードを削除することにより、前記局所マニフェストを更新するステップと、前記更新された局所マニフェストに対応している第２のアドバタイズメントを送信するステップと、を更に含む請求項１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、一般に、データの同期に係り、より詳細には、完全に一致するネームを使用してネットワーク上のピア間でコレクションの同期を実行することによるサービスディスカバリに関する。
【背景技術】
【０００２】
数多くのコンピューティングアプリケーションにおいて、多くの場合、ネットワーク上のピアが各々のデータのコレクションを同期させることは重要である。ディジタルコンテンツの肥大化は、調整を必要とするぼう大な数のコレクションを作り出している。このようなディジタルコンテンツへのアクセスやプロセッシングを容易にするためにコンテンツセントリックネットワーク（ＣＣＮ）アーキテクチャが設計されている。ＣＣＮは、様々なコンテンツアイテムに対する「興味関心（インタレスト）」パケットを送信し、引き換えに、「コンテンツオブジェクト」パケットを受信することによって互いに通信する、ネットワーククライアント、フォワーダ（例えば、ルータ）、コンテンツプロデューサなどのエンティティ、またはノードを含む。ＣＣＮのインタレストおよびコンテンツオブジェクトは一意名に基づいて識別され、一意名は、通常、最も一般的なレベルから最も特定のレベルまで順序付けられる連続的なネームを含む階層的に構造化された可変長の識別子（ＨＳＶＬＩ）である。
【０００３】
現在のＣＣＮ同期プロトコルは最長プレフィックスマッチング法を使用しており、この方法において、“／ｐａｒｃ／ｅｖｅｎｔｓ／”のインタレストは“／ｐａｒｃ／ｅｖｅｎｔｓ／ｃａｌｅｎｄａｒ．ｔｘｔ”と“／ｐａｒｃ／ｅｖｅｎｔｓ／ｃｏｎｆｅｒｅｎｃｅ．ｔｘｔ．”の両方に一致している。この既存の同期プロトコルは、インタレストのあるネームを拡張する応答に基づいて作成される。この同期プロトコルは、以下の出願、即ち、２０１２年１２月１９日付けで出願された、発明者、Ｖａｎ  Ｌ．  Ｊａｃｏｂｓｏｎ（ヴァン、エル、ヤコブソン）とＭａｒｃ  Ｅ．  Ｍｏｓｋｏ（マルク、イー、モスコ）による「ＤＹＮＡＭＩＣ  ＲＯＵＴＩＮＧ  ＰＲＯＴＯＣＯＬＳ  ＵＳＩＮＧ  ＤＡＴＡＢＡＳＥ  ＳＹＮＣＨＲＯＮＩＺＡＴＩＯＮ（データベース同期を使用したダイナミックルーティングプロトコル）」と題された米国特許出願第１３／７２０，７３６号（代理人整理番号ＰＡＲＣ−２０１１１３９７−ＵＳ−ＮＰ）（以下、米国特許出願第１３／７２０，７３６号）、および、２０１２年１１月１９日付けで出願された、発明者、Ｖａｎ  Ｌ．  Ｊａｃｏｂｓｏｎ（ヴァン、エル、ヤコブソン）とＭａｒｃ  Ｅ．  Ｍｏｓｋｏ（マルク、イー、モスコ）による「ＤＡＴＡ  ＴＲＡＮＳＰＯＲＴ  ＢＹ  ＮＡＭＥＤ  ＣＯＮＴＥＮＴ  ＳＹＮＣＨＲＯＮＩＺＡＴＩＯＮ（名付けられたコンテンツ同期によるデータトランスポート）」と題された米国特許出願第１３／６８１，３０６号（代理人整理番号ＰＡＲＣ−２０１１１３１７−ＵＳ−ＮＰ）（以下、米国特許出願第１３／６８１，３０６号）に、記載されている。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ＣＣＮアーキテクチャが進化するにつれて、既存の最長プレフィックスの一致よりむしろ、完全に一致するネームの使用を可能にする同期プロトコルに基づいてこれらのデバイスによって提供されるデバイスおよびサービスを発見する必要がある。このような新しいアーキテクチャにおいて、現在のＣＣＮ同期プロトコルは機能しない。
【課題を解決するための手段】
【０００５】
一実施形態は、完全に一致するネームに基づいた同期プロトコルを使用することによってコンテンツセントリックネットワークにおけるデバイス同士の間のマニフェストの同期化に基づいてサービスディスカバリを容易にするシステムを提供する。動作中、局所デバイスは、遠隔デバイスの遠隔マニフェストに対応しているアドバタイズメントを受信する。マニフェストはサービスレコードのコレクションを表しており、アドバタイズメントは遠隔デバイスに対応しているサービスレコードを含む。局所デバイスは、局所マニフェストと遠隔マニフェストが同じネームスペースに対応しているとの判断に応答して、アドバタイズされたサービスレコードを局所マニフェストへ挿入することによって、その局所マニフェストを更新する。
【０００６】
一部の実施形態において、局所デバイスは遠隔デバイスの遠隔マニフェストに対応しているアドバタイズメントに対してクエリを送信する。
【０００７】
一部の実施形態において、局所デバイスは局所デバイスの局所マニフェストに対応しているアドバタイズメントを送信し、アドバタイズメントが局所デバイスに対応しているサービスレコードを含む。
【０００８】
一部の実施形態において、局所デバイスが局所マニフェストに対応しているアドバタイズメントに対するクエリを遠隔デバイスから受信し、アドバタイズメントが局所デバイスに対応しているサービスレコードを含む。
【０００９】
一部の実施形態において、局所デバイスによって送受信されるパケットが、マニフェストを識別する経路指定可能なプレフィックス、パケットがデータの転送に対応していることを判断する識別子、パケットがデータのアドバタイズメントに対応していることを判断する識別子、マニフェストのルートハッシュ値、マニフェストにおけるサービスレコードのネーム、およびサービスレコードの一以上を示している。
【００１０】
一部の実施形態において、アドバタイズメントのサービスレコードのシリアル番号がアドバタイズメントのサービスレコードと同じネームを有する局所マニフェストのサービスレコードのシリアル番号より大であるとの判断に応答して、局所デバイスは、局所マニフェストのサービスレコードの値をアドバタイズメントのサービスレコードの値で更新する。
【００１１】
一部の実施形態において、局所デバイスは、マニフェストなしで、ネットワーク上で初期化される。局所デバイスは、局所デバイスに対応しているサービスレコードを作成し、サービスレコードから成る局所デバイスに対してマニフェストを作成する。
【００１２】
一部の実施形態において、局所デバイスは、局所マニフェストのルートハッシュ値がアドバタイズされた遠隔マニフェストのルートハッシュ値とは異なっているとの判断に応答して、遠隔マニフェストに対してリクエストを送信し、ルートハッシュ値は、マニフェストのサービスレコードを識別する。受信した遠隔マニフェストに基づいて、局所デバイスは、遠隔マニフェストに表されたサービスレコードのどのサービスレコードが局所マニフェストに表されたサービスレコードとは異なっているかを判断する。局所デバイスは異なっているサービスレコードに対してインタレストの集合を送信する。
【００１３】
一部の実施形態において、局所マニフェストのサービスレコードの活動時間（ＴＴＬ）が発生し次第、局所デバイスは、局所マニフェストから期限切れのサービスレコードを削除することによって局所マニフェストを更新する。局所デバイスは更新された局所マニフェストに対応するアドバタイズメントを送信する。
【図面の簡単な説明】
【００１４】
【図１】図１は、本発明の一実施形態によるコンテンツセントリックネットワークにおけるノード間のマニフェストの同期を容易にする例示的なコンピュータシステムを示す図である。
【図２】図２は、本発明の一実施形態による局所ノードと遠隔ノードの間の例示的な通信を示す図である。
【図３】図３は、本発明の一実施形態による遠隔マニフェストと局所マニフェストに関連付けられたコンテンツを同期させる方法を示す流れ図である。
【図４】図４は、本発明の一実施形態による、変更時間に基づいて、遠隔マニフェストと局所マニフェストに関連付けられたコンテンツを同期させる方法を示す流れ図である。
【図５】図５は、本発明の一実施形態による、マニフェストに対応しているアドバタイズメントを送信するための方法を示す流れ図である。
【図６Ａ】図６Ａは、本発明の一実施形態による、マニフェストのフォーマットおよびコレクションにおいて表されたコンテンツオブジェクトを示す表である。
【図６Ｂ】図６Ｂは、本発明の一実施形態による、局所マニフェストが遠隔マニフェストからのコンテンツオブジェクトを欠いている同期中の二つのマニフェストのフォーマットを示す表である。
【図６Ｃ】図６Ｃは、本発明の一実施形態による、局所マニフェストにおける同じネームのコンテンツオブジェクトのダイジェストが遠隔マニフェストにおけるダイジェストとは異なっており、かつ、遠隔ノードがそのマニフェストをアドバタイズする、同期中の二つのマニフェストのフォーマットを示す表である。
【図６Ｄ】図６Ｄは、本発明の一実施形態による、局所マニフェストにおける同じネームのコンテンツオブジェクトのダイジェストが遠隔マニフェストにおけるダイジェストとは異なっており、かつ、局所ノードがそのマニフェストをアドバタイズする、同期中の二つのマニフェストのフォーマットを示す表である。
【図６Ｅ】図６Ｅは、本発明の一実施形態による、局所マニフェストにおける同じネームのコンテンツオブジェクトのダイジェストおよび変更時間が遠隔マニフェストにおけるダイジェストとは異なっている、同期中の二つのマニフェストのフォーマットを示す表である。
【図７】図７は、本発明の一実施形態による、コンテンツセントリックネットワークにおけるデバイス同士の間のマニフェストの同期に基づいてサービスディスカバリを容易にする例示的なコンピュータシステムを示す図である。
【図８】図８は、本発明の一実施形態による、二つのデバイス同士の間の例示的な通信を示す図である。
【図９Ａ】図９Ａは、本発明の一実施形態による、ネットワークにおける二つのデバイスのマニフェストの同期に基づいてサービスディスカバリを容易にする方法を示す流れ図である。
【図９Ｂ】図９Ｂは、本発明の一実施形態による、ネットワークにおける二つのデバイスのマニフェストの同期に基づいてサービスディスカバリを容易にする方法を示す流れ図である。
【図１０Ａ】図１０Ａは、本発明の一実施形態による、コレクションに表されたマニフェストのフォーマットとサービスレコードを示す表である。
【図１０Ｂ】図１０Ｂは、本発明の一実施形態による、局所デバイスが遠隔マニフェストの検索を必要としない、同期プロトコルを使用したサービスディスカバリ中の二つのマニフェストのフォーマットを示す表である。
【図１０Ｃ】図１０Ｃは、本発明の一実施形態による、局所デバイスが遠隔デバイスから更新されたサービスレコードを受信する、同期プロトコルを使用したサービスディスカバリ中の二つのマニフェストのフォーマットを示す表である。
【図１０Ｄ】図１０Ｄは、本発明の一実施形態による、局所デバイスが初期化され、サービスディスカバリを実行し、遠隔マニフェストを検索する、同期プロトコルを使用したサービスディスカバリ中の二つのマニフェストのフォーマットを示す表である。
【図１１】図１１は、本発明の一実施形態による、コンテンツセントリックネットワークにおけるデバイス同士の間のマニフェストの同期に基づいてサービスディスカバリを容易にする例示的なコンピュータおよび通信システムを示す図である。
【発明を実施するための形態】
【００１５】
図中、同様の図形要素には同様の参照番号を付す。
【００１６】
以下の説明は当業者が実施形態を作成し利用することを可能にするために提示され、特定の出願やその要件に関して提供される。本開示の実施形態への様々な改変は、当業者にとって容易に理解され、本明細書中に定義された一般的な原理は本開示の精神および範囲を逸脱しない限り、他の実施形態および用途に適用可能である。よって、本発明は、図示されている実施形態に限定されないが、本明細書に開示されている原理および特性に符合する最も広い範囲で付与される。
【００１７】
本発明の実施形態は、完全一致ネームを使用して、ネットワーク上のノード間のマニフェストの同期に基づいて、コンテンツセントリックネットワーク（ＣＣＮ）におけるデバイスによって提供されるデバイスおよびサービスの発見（ディスカバリ）を容易にするシステムを提供する。本発明の実施形態の以下の説明において、関連するＣＣＮエンティティは局所ノードと遠隔ノードであり、その役割は逆でもよい。一部の実施形態において、関連するＣＣＮエンティティは局所ノードにおけるデバイスであり（「局所デバイス」）および遠隔ノードにおけるデバイス（「遠隔ノード」）である。局所および遠隔ノードの各々はノードにおけるコンテンツオブジェクトのコレクションを表すマニフェストに関連付けられる。マニフェストは特定のプレフィックスで識別され、よって、同じプレフィックスを有する二つのマニフェストが同じコンテンツオブジェクトの同じコレクションに対応する。
【００１８】
一部の実施形態において、マニフェストはコンテンツオブジェクトのコレクションを識別する順序付けられたリストである。コレクション中の各コンテンツオブジェクトはそのネームと対応するダイジェストによって識別され、このダイジェストはコンテンツオブジェクトのハッシュ値である。一部の実施形態において、各コンテンツオブジェクトはコンテンツが変更された時間を表す変更時間によっても識別される。この説明のために、マニフェストは、順序付けられたリストとして記載されているが、他の実施形態は、コンテンツオブジェクトだけでなく入れ子状のコンテンツオブジェクトのコレクションを含む同期ツリーとして構造化されたマニフェストを含む。システムはマニフェストに対するルートハッシュ値を生成する。ルートハッシュ値はコレクションの個々のコンテンツオブジェクトのハッシュ値に基づいた相加的ハッシュ値である。マニフェストのルートハッシュ値はマニフェストの一意の識別子である。
【００１９】
システムは、完全一致ネームを使用して、局所マニフェスト内のコンテンツに局所マニフェストのコレクションを同期させることができる。遠隔ノードはそのマニフェストのハッシュを公示（アドバタイズ）する。局所ノードは、アドバタイズメントを受信し、アドバタイズされた遠隔マニフェストが局所マニフェストに対応すると判断し、これによって、遠隔マニフェストおよび局所マニフェストが同じコンテンツオブジェクトのコレクションに対応する。局所ノードは、局所マニフェストのルートハッシュ値を遠隔マニフェストのルートハッシュ値と比較することにより、局所マニフェストのコンテンツが遠隔マニフェストのコンテンツに同期するかどうかを判断する。これらのコンテンツが一致しない場合、局所ノードは、遠隔ノードへ遠隔マニフェストに対するリクエストを送信することによって遠隔マニフェストを検索する。一部の実施形態において、局所ノードは、チャンキングプロトコルに基づくインタレストの集合を送信し、各インタレストは、マニフェストの番号付きチャンクに対応している。一部の実施形態において、遠隔ノードは、そのマニフェストに対応するチャンクの数をアドバタイズすることができる。局所ノードは、遠隔マニフェストを所有して、遠隔マニフェストに示されたコンテンツオブジェクトのどのコンテンツオブジェクトが局所マニフェストに示されたコンテンツオブジェクトとは異なっているかを判断する。次に、局所ノードは、（インタレストがリクエストされたコンテンツオブジェクトのネームを含む）異なっているコンテンツオブジェクトに対するインタレストの集合を送信する。一部の実施態様において、インタレストはリクエストされたコンテンツオブジェクトに対応しているハッシュ値も含む。このように、システムはリクエストに完全に一致するネームを使用し、様々なコンテンツオブジェクトの集合を受信する。
【００２０】
一部の実施形態において、マニフェストは、完成したマニフェストを送ることよりもむしろ、ｒｓｙｎｃプロトコルにおいてロールハッシュ技術などの構造化された技術を使用して送信される。
【００２１】
一部の実施形態において、コレクション内のコンテンツオブジェクトは、コンテンツオブジェクトが変更された時間を示す、対応する変更時間によって更に識別される。異なっていると判断されたコンテンツオブジェクト毎に、局所ノードは、遠隔マニフェストにおけるコンテンツオブジェクトの変更時間が局所マニフェストにおける対応するコンテンツオブジェクトより後なのかまたはより前なのかを判断する。遠隔コンテンツオブジェクトがより新しいバージョンに対応する場合、局所ノードは、局所マニフェストにおけるコンテンツオブジェクトの値を遠隔マニフェストからのコンテンツオブジェクトの値で更新する。データコレクションからのコンテンツアイテムを取り去る方法、または「ホワイトアウトする」方法は、米国特許出願第１３／６８１，３０６号に記載されている。
【００２２】
一部の実施形態において、コンテンツオブジェクトのネームは、階層的に構造化された可変長の識別子（ＨＳＶＬＩ）であり、最新バージョンのコンテンツオブジェクトを判断するためにマニフェストにおける変更された時間の代わりに使用されるバージョン番号、タイムスタンプ、または暗黙的仕分け順序を示している。
【００２３】
一部の実施形態において、遠隔コンテンツオブジェクトが新しくないバージョンに対応している場合、システムは、遠隔マニフェストからのコンテンツオブジェクトの値を局所マニフェストにおいて対応するコンテンツオブジェクトの履歴フィールドへ挿入することによって、この履歴を保持すべきかを判断することができる。これに応じて、システムは、異なっていると判断されたコンテンツオブジェクト毎に値を更新する。このように、システムは、局所ノードにおけるマニフェストを遠隔ノードにおけるマニフェストに同期させる。
【００２４】
一部の実施形態において、ネットワーククライアント、ネットワークノード（例えば、ルータなどのフォワーダ）および配信者は、情報セントリックネットワーク（ＩＣＮ）を介して通信する。ＩＣＮにおいて、コンテンツの各部分は、個別に名付けられ、データの各部分は他のバージョンの同じデータまたは他のソースからのデータなどのデータの任意の他の部分からデータを区別する一意名に結合される。この一意名は、ネットワークデバイスに、リクエストまたはこの一意名を示すインタレストを展開することによって、データをリクエストさせるとともに、データの格納場所やネットワークの場所やアプリケーションや交通手段とは無関係のデータを取得することができる。ネーム付きデータネットワーク（ＮＤＮ）またはコンテンツセントリックネットワーク（ＣＣＮ）は、ＩＣＮアーキテクチャの例であり、以下の用語はＮＤＮまたはＣＣＮアーキテクチャのエレメントを説明している：
【００２５】
コンテンツオブジェクト：一意名に結合されたネーム付きデータの一部分。コンテンツオブジェクトは、コンテンツオブジェクトが、コンピューティングデバイス内または複数のコンピューティングデバイスを介してあちこち動き回ることができるが変化することはないという意味で「永続的」である。コンテンツオブジェクトの任意のコンポーネントが変化する場合、その変化したエンティティは更新されたコンテンツを含む新しいコンテンツオブジェクトを作成しかつ新しい一意名に新しいコンテンツオブジェクトを結び付ける。
【００２６】
一意名：ＩＣＮ内のネームは、通常、独立した場所であり、コンテンツオブジェクトを一意に識別する。データ転送デバイスは、コンテンツオブジェクトに対するネットワークアドレスまたは物理的場所とは無関係に、コンテンツオブジェクトを生成または格納するネットワークノードに向けてパケットを転送するためにネームまたはネームプレフィックスを使用することができる。一部の実施形態において、ネームは、階層的に構造化された可変長識別子（ＨＳＶＬＩ）であってよい。ＨＳＶＬＩは、様々な方法で構造化することができるいくつかの階層的コンポーネントに分割され得る。例えば、個々のネームのコンポーネントのｐａｒｃ，  ｈｏｍｅ，  ｎｄｎ，  およびｔｅｓｔ．ｔｘｔは、ネーム“／ｐａｒｃ／ｈｏｍｅ／ｎｄｎ／ｔｅｓｔ．ｔｘｔ”を形成するために左配向プレフィックス主要方法において構成され得る。よって、ネーム“／ｐａｒｃ／ｈｏｍｅ／ｎｄｎ”は、“／ｐａｒｃ／ｈｏｍｅ／ｎｄｎ／ｔｅｓｔ．ｔｘｔ”の「親」または「プレフィックス」であり得る。共同ドキュメントなどの様々なバージョンのコンテンツアイテムを互いから区別するために更なるコンポーネントを使用することができる。
【００２７】
一部の実施形態において、ネームは、コンテンツオブジェクトのデータ（例えば、チェックサム値）および／またはコンテンツオブジェクトのネームのエレメントから導出されたハッシュ値などの非階層的識別子を含むことができる。ハッシュベースのネームの説明は、（発明者イグナシオ、ソリス（Ｉｇｎａｃｉｏ  Ｓｏｌｉｓ）による「ネームベースのパケット転送のための順序付けされたエレメントネーミング（“ＯＲＤＥＲＥＤ−ＥＬＥＭＥＮＴ  ＮＡＭＩＮＧ  ＦＯＲ  ＮＡＭＥ−ＢＡＳＥＤ  ＰＡＣＫＥＴ  ＦＯＲＷＡＲＤＩＮＧ”）」と題された２０１３年３月２０日出願された）米国特許出願第１３／８４７，８１４号に記載されている。ネームもフラットラベル化され得る。以下では、「ネーム」は、階層的ネームまたはネームプレフィックス、フラットネーム、固定長ネーム、任意長ネーム、またはラベル（例えば、マルチプロトコルラベルスイッチング（ＭＰＬＳ）ラベル）などのネームデータネットワークにおけるデータの一部に代わる任意のネームに言及するために使用される。
【００２８】
インタレスト：データの一部分に対するリクエストを示し、データの一部分に対するネーム（またはネームプレフィックス）を含むパケット。データ消費者が情報セントリックネットワークを介してリクエストまたはインタレストを展開することにて、ＣＣＮ／ＮＤＮルータは、記憶装置（例えば、キャッシュサーバ）またはリクエストやインタレストを満たすためにリクエストされたデータを提供することができるデータプロデューサへ向かって伝搬することができる。
【００２９】
一部の実施形態において、ＩＣＮシステムはコンテンツセントリックネットワーキング（ＣＣＮ）アーキテクチャを含むことができる。しかしながら、本明細書に開示された方法は他のＩＣＮアーキテクチャに適用することも可能である。ＣＣＮアーキテクチャの記載は、発明者ヴァン、エル、ヤコブソン（Ｖａｎ  Ｌ．  Ｊａｃｏｂｓｏｎ）およびダイアナ、ケー、スメッター（Ｄｉａｎａ  Ｋ．  Ｓｍｅｔｔｅｒｓ）により、２００８年１２月１８日に出願され、「コンテンツセントリックネットワークにおけるインタレストとコンテンツの拡散コントロール（“ＣＯＮＴＲＯＬＬＩＮＧ  ＴＨＥ  ＳＰＲＥＡＤ  ＯＦ  ＩＮＴＥＲＥＳＴＳ  ＡＮＤ  ＣＯＮＴＥＮＴ  ＩＮ  Ａ  ＣＯＮＴＥＮＴ  ＣＥＮＴＲＩＣ  ＮＥＴＷＯＲＫ”）」と題された米国特許出願第１２／３３８，１７５号に記載されている。
【００３０】
図１は、本発明の一実施形態による、コンテンツセントリックネットワーク（ＣＣＮ）におけるノード間のマニフェストの同期を容易にする例示的なネットワーク１００を示している。ネットワーク１００は、クライアントデバイス１１６、コンテンツ生成デバイス１１８、およびノード１０２、１０４、１０６、１０８、１１０、１１２および１１４におけるルータまたは他のフォワーダを含むことができる。ノード１０２〜１１４は各々、一以上のマニフェストを含む。例えば、ノード１１２は、マニフェスト１２０を含む。マニフェスト１２０は、コレクションネーム１２４と、以下のコンテンツオブジェクトネーム１３０．１−１３０．ｎ、ダイジェスト１３２．１−１３２．ｎ、および変更時間１３４．１−１３４．ｎの一以上によって識別されるコンテンツオブジェクトの順序付けされたリストと、を含む。ダイジェスト１３２．１−１３２．ｎは、ネーム１３０．１−１３０．ｎによって各々識別されるコンテンツオブジェクトのハッシュ値を含む。ダイジェストは、（二つの異なるコンテンツオブジェクトの一方向ハッシュから同じ値が得られる）ハッシュ衝突の尤度が十分に低いことにてダイジェストはコンテンツオブジェクトに対する一意の識別子である、コンテンツオブジェクトのＳＨＡ−２５６ハッシュであり得る。マニフェスト１２０は、コレクションの個別のコンテンツオブジェクトのハッシュ値１３２．１−１３２．ｎに基づいた相加的ハッシュ値であるルートハッシュ１２２も含む。ルートハッシュ１２２は、マニフェスト１２０の一意の識別子であり、コレクションにおいてコンテンツオブジェクトを表す。
【００３１】
一部の実施形態において、マニフェストは、ネームと、対応するダイジェストと、を示すが、変更時間は示さない。このようなシステムは、その前のバージョンのテキストファイルが重要でありよってこのシステムによって保持される、例えば、ファイルサーバを含むことができる。他の実施形態において、マニフェストは、ネーム、対応するダイジェスト、および変更時間を示す。システムは、どのバージョンのコンテンツアイテムを保持すべきかを判断するために変更時間を使用することができる。例えば、コンテンツアイテムがリンク状態を示す場合、システムはその前のバージョンに関連する情報を必要としない。この場合、最新の更新時間を有するコンテンツオブジェクトのみが保持される。
【００３２】
ネットワーク内の任意の二つのノードは、同じデータのコレクションを表すマニフェストを含むことができ、よって、マニフェストは本明細書に記載された方法を使って同期され得る。用語「局所ノード」と「遠隔ノード」は、コンテンツセントリックネットワーク（ＣＣＮ）における任意のノードに適用可能であり、本開示においてＣＣＮ内の二つのノードを差別化するために使用される。
【００３３】
二つのノード間の同じデータのコレクションを表しているマニフェストの同期は、三つの部分名に基づいている。第１の部分は“／ａ／ｂ”などのコレクションを識別する経路指定可能なプレフィックスである。第２の部分は関連するネームスペースの識別を含み、アドバタイズメントの“／ａｄｖ”、または、データ転送の“／ｄａｔａ”のいずれかである。第３の部分は、アドバタイズまたは転送されているハッシュ値またはコンテンツである。よって、ＣＣＮネームはフォーム：
／ｃｏｌｌｅｃｔｉｏｎ＿ｐｒｅｆｉｘ／ａｄｖ＿ｏｒ＿ｄａｔａ／ｐｒｏｔｏｃｏｌ＿ｄａｔａ
で表される。
例えば、ハッシュアドバタイズメントを送信するインタレストの例は、
／ａ／ｂ／ａｄｖ／＜ｒｏｏｔｈａｓｈ＞
で表される。
このアドバタイズメントを受信しかつ同じ経路指定可能なプレフィックス“／ａ／ｂ”を有する局所マニフェストを含む局所ノードは、チャンキングプロトコルに基づいたチャンク０，１．．．．．最終チャンクｍ個においてアドバタイズされたマニフェストを検索する。このようなインタレストは、
／ａ／ｂ／ｄａｔａ／＜ｒｏｏｔｈａｓｈ＞／＜ｃｈｕｎｋ  ｎｕｍｂｅｒ＞
と表される。
【００３４】
検索されたマニフェストのエントリに基づいて、システムは検索されたマニフェストにおいて識別されたどのコンテンツオブジェクトが局所マニフェストで識別されたコンテンツオブジェクトとは異なっているかを判断する。システムはコンテンツオブジェクトのネームに基づいて異なるコンテンツオブジェクトを検索する：
／ａ／ｂ／ｄａｔａ／＜ｎａｍｅ  ｏｆ  ｃｏｎｔｅｎｔ  ｏｂｊｅｃｔ＞
一部の実施形態において、システムはリクエストされたコンテンツオブジェクトのハッシュ値に基づいて異なるコンテンツオブジェクトを検索する：
／ａ／ｂ／ｄａｔａ／＜ｈａｓｈ（ｃｏｎｔｅｎｔ  ｏｂｊｅｃｔ）＞
一部の実施形態において、システムはマニフェストのネームに基づいて異なるコンテンツオブジェクトを検索する。この技術はシステムにコレクションのネームスペースの下のコンテンツのネームを使うよりむしろオブジェクトのキャッシュされたコピーを検索させる。例えば、図６Ｂにおけるマニフェスト１４０から第１のアイテムを検索するために、システムはネームおよびダイジェストに対するインタレストを送信する：
／ｃｈｅｆ／ｅｖｅｎｔｓ／ｃａｌｅｎｄａｒ．ｔｘｔ，  ｄｉｇｅｓｔ  ＝  ｛１｝
【００３５】
図２は、本発明の一実施形態による、ノード２０２（遠隔ノード）とノード２０６（局所ノード）との間の例示的な通信２００を示している。ノード２０２とノード２０６は各々、同じルーティングプレフィックスまたはコレクションネーム“／ａ／ｂ”を有するマニフェストを含む。遠隔ノード２０２は、コレクションネーム“／ａ／ｂ”によって識別されたそのマニフェストのルートハッシュ値を含むハッシュアドバタイズメントである、ｓｅｎｄ＿ａｄｖｅｒｔｉｓｅｍｅｎｔ（アドバタイズメント送信）インタレスト２２０を送信する。インタレストは、“／ａ／ｂ／ａｄｖ／＜ｒｏｏｔｈａｓｈ＞”のフォームをとっている。局所ノード２０６はアドバタイズされたインタレストを受信し、同じコレクションプレフィックス（“／ａ／ｂ”）に基づいて、ノード２０６がアドバタイズされたマニフェストと同じコレクションを示すマニフェストを含むかどうかを判断するために、ｃｈｅｃｋ＿ａｄｖｅｒｔｉｓｅｄ＿ｃｏｌｌｅｃｔｉｏｎ（アドバタイズされたコレクションチェック）手順２２２を実行する。その後、局所ノード２０６は、その局所マニフェストのルートハッシュが遠隔マニフェストのルートハッシュと異なっているかどうかを判断する。ハッシュ値が異なることはコレクションが互いに同期化される必要があることを示す。その後、局所ノード２０６は、マニフェストに対するインタレストの集合を送ることにより、ｒｅｔｒｉｅｖｅ＿ｍａｎｉｆｅｓｔ（マニフェスト検索）手順２２４を実行する。インタレストの集合はチャンキングプロトコルに基づいて複数のチャンクへ分割される。インタレストは、ｒｅｑｕｅｓｔ＿ｍａｎｉｆｅｓｔ＿ｉｎ＿ｃｈｕｎｋｓ  ｍｅｓｓａｇｅ（チャンクマニフェスト要求）メッセージ２２６において送信され、“／ａ／ｂ／ｄａｔａ／＜ｒｏｏｔｈａｓｈ＞／Ｃ０”、“／ａ／ｂ／ｄａｔａ／＜ｒｏｏｔｈａｓｈ＞／Ｃ１”、“／ａ／ｂ／ｄａｔａ／＜ｒｏｏｔｈａｓｈ＞／Ｃ２，”などのフォームをとっており、ここで、“Ｃ０”はマニフェストの第１のチャンク（以下同様）を示している。一部の実施形態において、アドバタイズメントノードはそのマニフェストを転送するために必要とされるだけのチャンクの数を含むことができる。ｓｅｎｄ＿ｍａｎｉｆｅｓｔ＿ｉｎ＿ｃｈｕｎｋｓ（チャンクマニフェスト送信）メッセージ２２８において、遠隔ノード２０２は、インタレスト集合に応答して、リクエストされたマニフェストを送り返す。リクエストされたコンテンツオブジェクトは、“／ａ／ｂ／ｄａｔａ／＜ｒｏｏｔｈａｓｈ＞／Ｃ０＋ｐａｙｌｏａｄ”のフォームをとり、ペイロードはマニフェストのリクエストされたチャンクを含む。
【００３６】
局所ノード２０６は、遠隔マニフェストを所有して、ｄｅｔｅｒｍｉｎｅ＿ｓｅｔ＿ｄｉｆｆｅｒｅｎｃｅ（差集合を求める）手順２３０を実行する。一部の実施形態において、この手順の結果は、ネームによって識別されたコンテンツオブジェクトのリストである。他の実施形態において、この結果は、対応するダイジェストによって識別されたコンテンツオブジェクトのリストである。その後、局所ノード２０６は、異なっていると判断されたコンテンツオブジェクト毎に、ｒｅｑｕｅｓｔ＿ｓｅｔ＿ｄｉｆｆｅｒｅｎｃｅ  ｉｎｔｅｒｅｓｔ（差集合インタレスト要求）２３４を送信する。インタレストは、例えば、“／ａ／ｂ／ｄａｔａ／ｎａｍｅ  １３０．３”のフォームをとる。局所ノード２０６は、遠隔ノード２０２がｓｅｎｄ＿ｓｅｔ＿ｄｉｆｆｅｒｅｎｃｅ（差集合送信）コンテンツオブジェクト２３６を送信したときにリクエストされたコンテンツオブジェクトを受信するが、その際、リクエストされたコンテンツオブジェクトは“／ａ／ｂ／ｄａｔａ／ｎａｍｅ  １３０．３＋ｐａｙｌｏａｄ”のフォームをとる。従って、局所ノード２０６は、異なっていると判断された全てのコンテンツオブジェクトをリクエストしこれを受信することによって、局所マニフェストのコンテンツが遠隔マニフェストのコンテンツに同期される。一部の実施形態において、局所ノード２０６は、図４に関連して以下に説明される、ｓｙｎｃ＿ｂａｓｅｄ＿ｏｎ＿ｍｏｄ＿ｔｉｍｅ（変更時間に基づく同期）手順２４０を実行する。
【００３７】
図３は、本発明の一実施形態による、遠隔マニフェストと局所マニフェストに関連付けられたコンテンツを同期させるための方法を示す流れ図３００である。以下の説明において、局所ノードは、図２では、ノード１０６として示され、遠隔ノードは、図２では、ノード１０２として示される。局所ノードは遠隔ノードにおいて遠隔マニフェストに対応しているアドバタイズメントを受信する（動作３０２）。マニフェストはノードにおけるコンテンツオブジェクトのコレクションを表している。局所ノードは、遠隔マニフェストと局所マニフェストが同じコンテンツオブジェクトのコレクションを示していると判断する（図２におけるｃｈｅｃｋ＿ａｄｖｅｒｔｉｓｅｄ＿ｃｏｌｌｅｃｔｉｏｎ（アドバタイズされたコレクションチェック）手順２２２に対応している動作３０４）。一部の実施形態において、局所ノードは、マニフェストのコレクションネームまたはルーティングプレフィックスを比較することにより、マニフェストが同じコレクションを示すかどうかを判断する。その後、局所ノードは、その局所マニフェストのルートハッシュ値が遠隔マニフェストのルートハッシュ値とは異なっているかどうかを判断する（動作３０６）。マニフェストのルートハッシュ値は、マニフェストに対する一意の識別子であり、マニフェストにおいて表されたコンテンツオブジェクトのダイジェストの相加的ハッシュ値を含む。局所マニフェストのルートハッシュ値が同じ場合（判断３０８）、手順は戻る。
【００３８】
局所マニフェストのルートハッシュ値が遠隔マニフェストのルートハッシュ値と同じではない場合（判断３０８）、同じコレクションを表す局所および遠隔マニフェストが同期されず再調整する必要があることを示している。局所ノードは遠隔マニフェストに対するリクエストを送信しこのリクエストに応答して遠隔マニフェストを受信することによって遠隔マニフェストをダウンロードまたは転送する（図２のｒｅｔｒｉｅｖｅ＿ｍａｎｉｆｅｓｔ（マニフェスト検索）手順２２４に対応する動作３１０）。
【００３９】
局所ノードは、遠隔マニフェストにおいて識別されたどのコンテンツオブジェクトが局所マニフェストで識別されたコンテンツオブジェクトと異なっているかを判断する（図２のｄｅｔｅｒｍｉｎｅ＿ｓｅｔ＿ｄｉｆｆｅｒｅｎｃｅ（差集合を求める）動作２３０に対応する動作３１２）。一部の実施形態において、局所ノードは局所マニフェストで識別されたコンテンツオブジェクトのダイジェストを遠隔マニフェストで識別された同じネームのコンテンツオブジェクトのダイジェストと比較することによって差集合を求める。局所ノードは、コンテンツオブジェクトの求められた差集合に対応しているインタレストの集合を送信し（動作３１４）、引き換えに、リクエストされたコンテンツオブジェクトを受信する（動作３１６）。これは、図２に示したｒｅｓｏｌｖｅ＿ｓｅｔ＿ｄｉｆｆｅｒｅｎｃｅ（差集合を解く）動作２３２に対応している。よって、局所マニフェストのコンテンツが遠隔マニフェストのコンテンツに同期される。
【００４０】
局所ノードが変化を有する場合、局所ノードは新しいルートハッシュ値をアドバタイズする。局所ノードはこれをすぐに行うか、または、ネットワークまたは他のタイミング検討に基づいて次のアドバタイズメントをスケジューリングすることができる。例えば、局所システムは毎秒少なくとも一回そのルートハッシュをアドバタイズすることができるが、その回数は４回までとされる。よって、調整中、更新によりルートハッシュが変化する際、システムは毎秒４回までアドバタイズできる。そうでない定常状態では、システムは毎秒一回アドバタイズできる。
【００４１】
図４は、本発明の実施形態による、変更された時間に基づいて、遠隔マニフェストと局所マニフェストに関連付けられたコンテンツを同期させるための方法を示す流れ図４００である。コンテンツの同期化がコンテンツオブジェクトに関連付けられたシーケンス番号に基づくことができ、より大なるシーケンス番号がより新しいバージョンのコンテンツオブジェクトを指していることに留意されたい。コンテンツの同期化はコンテンツオブジェクトのネームの順序に基づくことができ、暗黙的な仕分け順序はより新しいバージョンのコンテンツオブジェクトを示している。流れ図４００は、図２におけるｓｙｎｃ＿ｂａｓｅｄ＿ｏｎ＿ｍｏｄ＿ｔｉｍｅ動作２４０として示される、コンテンツオブジェクトの変更時間に基づく例示的な方法を示している。先に求められた差集合に基づいて、局所ノードは、対応するコンテンツオブジェクトが変更された時間を示す変更時間を含むリクエストされた集合のコンテンツオブジェクトを受信する（動作４０２）。コンテンツオブジェクト毎に、局所ノードは、遠隔マニフェストのコンテンツオブジェクトの変更時間が局所マニフェストの対応するコンテンツオブジェクトより後なのかまたは前なのかを判断する（動作４０４）。遠隔マニフェストからのコンテンツオブジェクトの変更時間が新しい場合（動作４０６）、システムは、局所マニフェストのコンテンツオブジェクトの値を遠隔マニフェストからのコンテンツオブジェクトの値で更新する（動作４０８）。一部の実施形態において、局所ノードは、局所マニフェストのコンテンツオブジェクトの値を更新する前に局所マニフェストの履歴フィールドへ（新しくない）コンテンツオブジェクトの対応する値および変更時間を挿入することによって、局所マニフェストのその（新しくない）コンテンツオブジェクトの値を保持するかどうかを判断することができる。集合内でもっとコンテンツオブジェクトを検索する必要がある場合（判断４１０）、システムは動作４０４へ戻る。そうでない場合、システムは必要なコンテンツオブジェクトの検索を終了する。
【００４２】
遠隔マニフェストからのコンテンツオブジェクトの変更時間が局所マニフェストにおける対応するコンテンツオブジェクトより新しくない場合（動作４０６）、システムは、局所マニフェストの履歴フィールドへ（新しくない）コンテンツオブジェクトの対応する値および変更時間を挿入することによって（動作４１４）、遠隔マニフェストからの（新しくない）コンテンツオブジェクトの値を保存するか否かを判断する（判断４１２）。集合内にコンテンツオブジェクトをもっと検索する必要がある場合（判断４１０）、システムは動作４０４に戻る。そうでない場合、システムは必要なコンテンツオブジェクトの検索を終了する。よって、異なっていると判断されたコンテンツオブジェクトが全て更新され、恐らくは、局所マニフェストの履歴フィールドに保持または保存され、これによって、局所マニフェストのコンテンツが遠隔マニフェストのコンテンツに同期される。
【００４３】
図５は、本発明の一実施形態による、マニフェストに対応するアドバタイズメントを送信するための方法を示す流れ図５００である。図５におけるノードは、パケットを遠隔ノードへ送信するので、局所ノードとして記述される。図５における局所ノードが、その前は遠隔ノード２０２と呼ばれていた図２のノード２０２に対応していることに留意されたい。コンテンツセントリックネットワーク（ＣＣＮ）などのネットワークにおける任意のノードは遠隔ノードまたは局所ノードと称され得ることを想起されたい。
【００４４】
局所ノードは、ノードにおけるコンテンツオブジェクトのコレクションを表すマニフェストに対応するアドバタイズメントを送信する（図２のｓｅｎｄ＿ａｄｖｅｒｔｉｓｅｍｅｎｔ（アドバタイズメント送信）メッセージ２２０に対応する動作５０２）。このアドバタイズメントは、ビーコンに類似し、使用される“／ａｄｖ”ネームスペースに基づくインタレストであり、返信コンテンツをリクエストしない。遠隔ノードからマニフェストに対するリクエストを受信し次第、局所ノードは、遠隔ノードへマニフェストを送信する（図２のｒｅｑｕｅｓｔ＿ｍａｎｉｆｅｓｔ＿ｉｎ＿ｃｈｕｎｋｓ  ｉｎｔｅｒｅｓｔ（チャンクインタレストのマニフェスト要求）２２６およびｓｅｎｄ＿ｍａｎｉｆｅｓｔ＿ｉｎ＿ｃｈｕｎｋｓ（チャンクのマニフェスト送信）メッセージ２２８の受信に対応する動作５０４）。局所マニフェストにおいて識別されたコンテンツオブジェクトに対する遠隔ノードからリクエストを受信し次第、局所ノードは、リクエスト側の遠隔ノードへリクエストされたコンテンツオブジェクトを送信する（図２のｒｅｑｕｅｓｔ＿ｓｅｔ＿ｄｉｆｆｅｒｅｎｃｅ  ｉｎｔｅｒｅｓｔ（差集合要求）インタレスト２３４およびｓｅｎｄ＿ｓｅｔ＿ｄｉｆｆｅｒｅｎｔ（差集合送信）メッセージ２３６を受信することに対応する動作５０６）。
【００４５】
図６Ａは、本発明の一実施形態による、マニフェスト１２０のフォーマット、およびコレクションにおいて表されるコンテンツオブジェクトを示す表である。マニフェスト１２０は、コレクションネーム１２４と、以下のコンテンツオブジェクトネーム１３０．１−１３０．ｎ、ダイジェスト１３２．１−１３２．ｎ、および変更時間１３４．１−１３４．ｎの一以上と、によって識別されるコンテンツオブジェクトの順序付けされたリストを含む。ダイジェスト１３２．１−１３２．ｎは、ネーム１３０．１−１３０．ｎによって各々識別されたコンテンツオブジェクトのハッシュ値を含む。マニフェスト１２０はまた、コレクションの個別のコンテンツオブジェクトのハッシュ値１３２．１−１３２．ｎに基づいた相加的ハッシュ値であるルートハッシュ１２２も含む。マニフェスト１２０のルートハッシュ１２２は、マニフェスト１２０に対する一意の識別子である。
【００４６】
図１に関して記載したように、マニフェスト１２０はコレクションにおいて表されたコンテンツオブジェクト毎にネームおよび対応するダイジェストを示すことができる。一部の実施形態において、マニフェスト１２０は、コレクションにおいて表されたコンテンツオブジェクト毎に変更時間も含むことができる。変更された時間フィールドの使用は、実行されている基礎となるアプリケーションやサービスに依存する。マニフェスト１２０がコレクションネーム１２４を示していることに留意されたい。図６Ｂ〜６Ｅに示されるマニフェストは、コレクションネームも含むが、例示的なマニフェストが同じデータのコレクションを含むので、図６Ｂ〜６Ｅにはコレクションネームが含まれていない。
【００４７】
図６Ｂ〜６Ｅは、各々がマニフェストを含む二つのノード、ノード１０２およびノード１０６を示している。この実施例において、ノード１０２は遠隔ノードであり、ノード１０６は局所ノードである。局所ノード１０６はマニフェスト１６０を含み、遠隔ノード１０２はマニフェスト１４０を含む。マニフェスト１４０および１６０は、同じコレクションネーム、またはルーティングプレフィックスを含むことにて、コンテンツオブジェクトまたは同じデータのコレクションを表している。時間は、ラベルＴ１、Ｔ２などによって示され、マニフェスト１４０および１６０のコンテンツはこれらの時間ラベルに対して示される。
【００４８】
マニフェストが、（コレクションの個別のコンテンツオブジェクトのダイジェストに基づいた相加的ハッシュ値である、）図６Ａにおいてルートハッシュ１２２として例示されたルートハッシュ値によって更に識別されることを想起されたい。以下の実施例において、ルートハッシュ値およびダイジェストは、これよりはるかに大なる場合があるが、例えば、“｛９９９｝”などのカッコ内の数値として示される。更に、経時的に変化するマニフェスト１４０とマニフェスト１６０のコンテンツオブジェクトのダイジェストおよび例示的なルートハッシュ値の両方が相加的ハッシュ値のサンプル表現としてのみ示される。
【００４９】
図６Ｂは、本発明の一実施形態による、局所マニフェストが遠隔マニフェストからのコンテンツオブジェクトを欠いている、同期中の二つマニフェストのフォーマットを示す表である。時間Ｔ１において、局所ノード１０６は、マニフェスト１４０の遠隔ノード１０２から、ルートハッシュ値｛９９９｝を有するハッシュアドバタイズメントを受信する。局所ノード１０６は、そのマニフェスト１６０が遠隔マニフェスト１４０と同じデータのコレクションを表し、マニフェスト１４０を検索すると判断する。局所ノード１０６は、ルートハッシュ値｛６０｝を有する局所マニフェスト１６０がルートハッシュ値｛９９９｝を有している遠隔マニフェスト１４０に同期していないと判断する。その後、局所ノード１０６は、その局所マニフェスト１６０と遠隔マニフェスト１４０の差集合を求める。この実施例において、マニフェスト１６０は、ネーム“／ｆｒｕｉｔ／ｌｙｃｈｅｅ／ｐｅｅｌ”によって識別されたコンテンツオブジェクトを欠いていることにて、局所ノード１０６は遠隔ノード１０２へそのネームによってコンテンツオブジェクトに対するインタレストを送信する。遠隔ノード１０２はリクエストされたコンテンツオブジェクトを戻す。時間Ｔ２において、局所ノード１０６はそのマニフェスト１６０を欠落しているコンテンツオブジェクトで更新する。時間Ｔ２におけるマニフェスト１６０のコンテンツに基づいて、システムは、マニフェスト１６０に対して、この時点で、遠隔マニフェストのルートハッシュ値に等しい新しいルートハッシュ値を生成する。これは、時間Ｔ２におけるマニフェスト１６０のルートハッシュ値によって示される：｛６０｝→｛９９９｝。よって、局所マニフェストと遠隔マニフェストがこれらのコレクションを同期させ、両マニフェストが同じルートハッシュ値｛９９９｝を含む。
【００５０】
図６Ｃは、本発明の一実施形態による、局所マニフェストの同じネームのコンテンツオブジェクトのダイジェストが遠隔マニフェストのダイジェストとは異なっており、かつ、遠隔ノードがアドバタイズメントを送信し局所ノードが遠隔マニフェストを検索する、同期中の二つのマニフェストのフォーマットを示す表である。時間Ｔ３において、局所ノード１０６は、マニフェスト１４０の遠隔ノード１０２から、ルートハッシュ値｛９９９｝を有するハッシュアドバタイズメントを受信する。局所ノード１０６は、そのマニフェスト１６０が遠隔マニフェスト１４０と同じデータのコレクションを表しており、マニフェスト１４０を検索すると判断する。局所ノード１０６は、ルートハッシュ値｛５３｝を有する局所マニフェスト１６０が、ルートハッシュ値｛９９９｝を有している遠隔マニフェスト１４０に同期していないと判断する。その後、局所ノード１０６は、その局所マニフェスト１６０と遠隔マニフェスト１４０の差集合を求める。この実施例において、マニフェスト１６０がダイジェスト｛２７９｝を有するネーム“／ｆｒｕｉｔ／ｌｙｃｈｅｅ／ｐｅｅｌ”によって識別されたコンテンツオブジェクトを欠いていることにて、局所ノード１０６は、遠隔ノード１０２へ、ネームおよびダイジェストに基づいたコンテンツオブジェクトに対するインタレストを送信する。遠隔ノード１０２はリクエストされたコンテンツオブジェクトを戻す。時間Ｔ４．ａにおいて、局所ノード１０６は、そのマニフェスト１６０を欠落しているコンテンツオブジェクトで更新する。時間Ｔ４．ａにおけるマニフェスト１６０のコンテンツに基づいて、システムはマニフェスト１６０に対して新しいルートハッシュ値を生成する。これは、時間Ｔ４．ａにおけるマニフェスト１６０のルートハッシュ値によって示される：｛５３｝→｛７７２｝。しかしながら、そのオリジナルのルートハッシュ値｛９９９｝を有するマニフェスト１４０は、この時点で、新しいルートハッシュ値｛７７２｝を有しているマニフェスト１６０に同期していない。
【００５１】
次に、遠隔ノード１０２は、マニフェスト１６０の局所ノード１０６から、新しいルートハッシュ値｛７７２｝を有するハッシュアドバタイズメントを受信する。遠隔ノード１０２は、そのマニフェスト１４０がマニフェスト１６０と同じデータのコレクションを表しており、マニフェスト１６０を検索すると判断する。遠隔ノード１０２は、ルートハッシュ値｛９９９｝を有するマニフェスト１４０がルートハッシュ値｛７７２｝を有するマニフェスト１６０に同期していないと判断する。その後、遠隔ノード１０２は、そのマニフェスト１４０とマニフェスト１６０の差集合を求める。この実施例において、マニフェスト１４０は、ダイジェスト｛４１｝を有するネーム“／ｆｒｕｉｔ／ｌｙｃｈｅｅ／ｐｅｅｌ”によって識別されたコンテンツオブジェクトを欠いており、よって、遠隔ノード１０２はこのネームとダイジェストに基づいてコンテンツオブジェクトに対するインタレストを局所ノード１０６へ送信する。局所ノード１０６は、リクエストされたコンテンツオブジェクトを戻す。時間Ｔ５．ａにおいて、遠隔ノード１０２は、そのマニフェスト１４０を欠落しているコンテンツオブジェクトで更新する。時間Ｔ５．ａにおけるマニフェスト１４０のコンテンツに基づいて、システムは、マニフェスト１４０に対して新しいルートハッシュ値を生成する。これは、時間Ｔ５．ａにおけるマニフェスト１４０のルートハッシュ値によって示される：｛９９９｝→｛７７２｝。よって、時間Ｔ５．ａにおいて、ノード１０２におけるマニフェスト１４０はノード１０６におけるマニフェスト１６０に同期している。ノード１０２および１０６は、それらのコレクションを同期させ、両ノードは同じルートハッシュ値｛７７２｝を含む。
【００５２】
図６Ｄは、本発明の一実施形態による、局所マニフェストの同じネームのコンテンツオブジェクトのダイジェストが遠隔マニフェストのダイジェストとは異なっており、かつ、局所ノードがアドバタイズメントを送信し遠隔ノードが局所マニフェストを検索する、同期中の二つのマニフェストのフォーマットを示す表である。時間Ｔ３において、遠隔ノード１０２は、マニフェスト１６０の局所ノード１０６から、ルートハッシュ値｛５３｝有するハッシュアドバタイズメントを受信する。遠隔ノード１０２は、そのマニフェスト１４０がマニフェスト１６０と同じデータのコレクションを表しており、マニフェスト１６０を検索すると判断する。遠隔ノード１０２は、ルートハッシュ値｛９９９｝を有するそのマニフェスト１４０がルートハッシュ値｛５３｝を有するマニフェスト１６０に同期していないと判断する。その後、遠隔ノード１０２は、そのマニフェスト１４０とマニフェスト１６０の差集合を求める。この実施例では、マニフェスト１４０は、ダイジェスト｛４１｝を有するネーム“／ｆｒｕｉｔ／ｌｙｃｈｅｅ／ｐｅｅｌ”によって識別されたコンテンツオブジェクトを欠いていることにて、遠隔ノード１０２は、そのネームおよびダイジェストに基づいてコンテンツオブジェクトに対するインタレストを局所ノード１０６へ送信する。局所ノード１０６はリクエストされたコンテンツオブジェクトを戻す。時間Ｔ４．ｂにおいて、遠隔ノード１０２は、そのマニフェスト１４０を、欠落しているコンテンツオブジェクトで更新する。時間Ｔ４．ｂにおけるマニフェスト１４０のコンテンツに基づいて、システムはマニフェスト１４０に対して新しいルートハッシュ値を生成する。これは、時間Ｔ４．ｂにおけるマニフェスト１４０のルートハッシュ値によって示される：｛９９９｝→｛７７２｝。しかしながら、そのオリジナルのルートハッシュ値｛５３｝を有するマニフェスト１６０は、この時点で、新しいルートハッシュ値｛７７２｝を有するマニフェスト１４０に同期していない。
【００５３】
次に、局所ノード１０６は、マニフェスト１４０の遠隔ノード１０２から、新しいルートハッシュ値｛７７２｝を有するハッシュアドバタイズメントを受信する。局所ノード１０６は、そのマニフェスト１６０がマニフェスト１４０と同じデータのコレクションを表しており、マニフェスト１４０を検索すると判断する。局所ノード１０６は、ルートハッシュ値｛５３｝を有するマニフェスト１６０がルートハッシュ値｛７７２｝を有するマニフェスト１４０に同期していないと判断する。その後、局所ノード１０６は、その局所マニフェスト１６０と遠隔マニフェスト１４０の差集合を求める。この実施例では、マニフェスト１６０がダイジェスト｛４１｝を有するネーム“／ｆｒｕｉｔ／ｌｙｃｈｅｅ／ｐｅｅｌ”によって識別されたコンテンツオブジェクトを欠いていることにて、局所ノード１０６はそのネームとダイジェストに基づいてコンテンツオブジェクトに対するインタレストを遠隔ノード１０２へ送信する。遠隔ノード１０２はリクエストされたコンテンツオブジェクトを戻す。時間Ｔ５．ｂにおいて、局所ノード１０６は、そのマニフェスト１６０を、欠落しているコンテンツオブジェクトで更新する。時間Ｔ５．ｂにおけるマニフェスト１６０のコンテンツに基づいて、システムはマニフェスト１６０に対して新しいルートハッシュ値を生成する。これは、時間Ｔ５．ｂにおけるマニフェスト１６０のルートハッシュ値によって示される：｛５３｝→｛７７２｝。従って、時間Ｔ５．ｂにおいて、ノード１０２におけるマニフェスト１４０は、ノード１０６におけるマニフェスト１６０に同期している。ノード１０２および１０６は、それらのコレクションを同期させ、両ノードは同じルートハッシュ値｛７７２｝を含む。
【００５４】
図６Ｃおよび図６Ｄは、任意のノードが遠隔または局所ノードであってよく、ハッシュアドバタイズメントと、マニフェストと、マニフェストに関連付けられ、異なっていると判断されたコンテンツオブジェクトと、を送受信する順序が、所定時間におけるコレクションのコンテンツ、例えば、時間［Ｔ３，Ｔ４．ａ，Ｔ５．ａ］および時間［Ｔ３，Ｔ４．ｂ，Ｔ５．ｂ］のマニフェスト１４０および１６０のコンテンツに応じて変化することがあることを示す。つまり、どのノードも、ハッシュアドバタイズメントを送受信し、マニフェストを転送し、本開示に記載されている方法を使ってノードにおけるマニフェストのコンテンツを同期させ、これによって、二つのノードにおけるデータコレクションの同期が得られ得る。
【００５５】
図６Ｅは、本発明の一実施形態による、局所マニフェストの同じネームのコンテンツオブジェクトのダイジェストと変更時間が遠隔マニフェストのダイジェストと変更時間とは異なっている、同期中の二つのマニフェストのフォーマットを示す表である。
【００５６】
時間Ｔ６において、局所ノード１０６は、マニフェスト１４０の遠隔ノード１０２から、ルートハッシュ値｛９９９｝を有するハッシュアドバタイズメントを受信する。局所ノード１０６は、そのマニフェスト１６０が、遠隔マニフェスト１４０と同じデータのコレクションを表しており、マニフェスト１４０を検索すると判断する。局所ノード１０６は、ルートハッシュ値｛８０｝を有する局所マニフェスト１６０が、ルートハッシュ値｛９９９｝を有する遠隔マニフェスト１４０に同期していないと判断する。その後、局所ノード１０６は、その局所マニフェスト１６０と遠隔マニフェスト１４０の差集合を求める。この実施例では、マニフェスト１４０とマニフェスト１６０の両方はそのコレクションにおいて表される各コンテンツオブジェクトに対応している変更時間１３４を示す。システムは、マニフェスト１４０およびマニフェスト１６０において同じネームを有するコンテンツオブジェクトが異なるダイジェストおよび異なる変更時間を有していると判断する。変更時間が、対応するコンテンツオブジェクトが変更された秒、分、時、日、月および年についての情報を含むことができることに留意されたい。便宜上、図６Ｅに例示したマニフェストは一日のある時間のみを含む。マニフェスト１４０は、ダイジェスト値｛１｝と変更時間８：０５ａｍを有するネーム“／ｃｈｅｆ／ｅｖｅｎｔｓ／ｃａｌｅｎｄａｒ．ｔｘｔ”によって識別されたコンテンツオブジェクトを含む。マニフェスト１６０は、異なるダイジェスト｛３２０｝および異なる変更時間７：３０ａｍを有する同じネームによって識別されたコンテンツオブジェクトを含む。その後、局所ノード１０６は、異なるコンテンツオブジェクトのネームとダイジェストに基づいてコンテンツオブジェクトに対するインタレストを遠隔ノード１０２へ送信する。遠隔ノード１０２はリクエストされたコンテンツオブジェクトを戻す。
【００５７】
局所ノードは、変更時間８：０５ａｍを有する遠隔マニフェスト１４０からのコンテンツオブジェクトが変更時間７：３０ａｍを有するその局所マニフェスト１６０からのコンテンツオブジェクトより新しいと判断する。よって、時間Ｔ７において、局所ノード１０６は、そのマニフェスト１６０を、異なっておりかつより新しいコンテンツオブジェクトで更新する。時間Ｔ７におけるマニフェスト１６０のコンテンツに基づいて、システムはマニフェスト１６０に対して新しいルートハッシュ値を生成する。これは、時間Ｔ７におけるマニフェスト１６０のルートハッシュ値によって示される：｛８０｝→｛９９９｝。従って、時間Ｔ７において、局所ノード１０６におけるマニフェスト１６０は遠隔ノード１０２におけるマニフェスト１４０に同期している。ノード１０２および１０６はそれらのコレクションを同期させ、両ノードは同じルートハッシュ値｛９９９｝を含む。
【００５８】
一部の実施形態において、システムは、マニフェスト１６０の履歴フィールドにおいてその前のバージョンの変更されたコンテンツオブジェクト（例えば、ダイジェスト｛３２０｝と変更時間７：３０ａｍを有するネーム“／ｃｈｅｆ／ｅｖｅｎｔｓ／ｃａｌｅｎｄａｒ．ｔｘｔ”によって識別されたコンテンツオブジェクト）を保持する。他の実施形態において、遠隔ノード１０２が、マニフェスト１６０の局所ノード１０６から、ルートハッシュ値｛８０｝を有するハッシュアドバタイズメントを受信し、局所マニフェスト１６０をダウンロードするとき、遠隔ノード１０２は、ダイジェスト｛３２０｝と変更時間７：３０ａｍを有するネーム“／ｃｈｅｆ／ｅｖｅｎｔｓ／ｃａｌｅｎｄａｒ．ｔｘｔ”によって識別された受信コンテンツオブジェクトのバージョンがそれ自体のマニフェストのバージョンより新しくないと判断する。この場合、遠隔ノード１０２におけるマニフェスト１４０は局所ノード１０６におけるマニフェスト１６０に同期しないままである。これらのマニフェストが同期を受けるのは、後になって、局所ノード１０６が、マニフェスト１４０の遠隔ノード１０２から、上記したように、より新しく更新されたコンテンツオブジェクトを含むハッシュアドバタイズメントを受信した時である。
【００５９】
一部の実施形態において、システムは、コンテンツセントリックネットワーク（ＣＣＮ）のデバイスによって提供されるデバイスおよびサービスディスカバリを容易にする。ＣＣＮネームスペースは、サービスの種類、例えば、プリンタ、ファイルサーバ、またはミュージックライブラリによって分割される。特定のタイプのデバイスはこれらのネームスペース内で、本開示に記載の同期プロトコルを実行する。例えば、このようなサービスのためのコレクションプレフィックスは以下のフォームをとる：
／ｐａｒｃ／ｓｅｒｖｉｃｅｓ／ｐｒｉｎｔｅｒｓ／…
／ｐａｒｃ／ｓｅｒｖｉｃｅｓ／ｓｅｒｖｅｒｓ／…
／ｐａｒｃ／ｓｅｒｖｉｃｅｓ／ｍｕｓｉｃ／…
【００６０】
このようなサービスディスカバリシステムにおいて、ノードにおける（“／ｐａｒｃ／ｍａｒｖｉｎ”と名付けられたプリンタなどの）デバイスは、空のマニフェストとともにブートアップされる（立ち上げられる）。デバイスは、“／ｐａｒｃ／ｍａｒｖｉｎ／ｓｅｒｖｉｃｅ”のネームを有するコンテンツオブジェクトであるサービスレコードをデバイス自体のために作成する。一部の実施形態において、このサービスレコードは、ジャバスクリプトオブジェクトノーテーション（ＪａｖａＳｃｒｉｐｔ（登録商標）  Ｏｂｊｅｃｔ  Ｎｏｔａｔｉｏｎ（ＪＳＯＮ））のフォーマットのものであり、以下のフィールド：サービスレコードのネーム；サービスの記述；サービスレコードのバージョンを示すシリアル番号；秒単位で測定され、サービスをアドバタイズするデバイスによって周期的にリフレッシュされなければ、サービスレコードの有効期限が切れる活動時間（ＴＴＬ）；およびサービスレコードのハッシュ値であるサービスレコードに対するダイジェスト、の一以上を含むことができる。サービスレコードのサイズは比較的小さいため、一部の実施形態において、サービスレコードはインタレストにおけるペイロードとして含むことができる。更に、より大きなシリアル番号を有するサービスレコードはより新しいサービスレコードを示し、レコードをより若いシリアル番号で置き換える。より古いサービスレコードはマニフェストにおいて保護されない。
【００６１】
デバイスは、デバイスのサービスレコードとこのサービスレコードの対応しているハッシュ値とを含むマニフェストを作成する。システムは、コレクション内のコンテンツオブジェクトのダイジェストに基づいた相加的ハッシュ値であるルートハッシュ値を生成する。デバイスのマニフェストのルートハッシュ値は、最初、マニフェストに示された一つのサービスレコードに基づいている。その後、デバイスは、デバイスが、同じサービスネームスペース（“ｐａｒｃ／ｓｅｒｖｉｃｅｓ／ｐｒｉｎｔｅｒｓ”）内で他のデバイスのマニフェストを検索し、差集合を求め、差集合を解く動作を実行できるように、フォーム“／ｐａｒｃ／ｓｅｒｖｉｃｅｓ／ｐｒｉｎｔｅｒｓ／ａｄｖ／ｑｕｅｒｙ”のクエリアドバタイズメントを送信する。このように、このノードにおけるデバイスは、そのマニフェストを他のノードにおける他のデバイスのマニフェストに同期させる。
【００６２】
一部の実施形態において、サービスレコードは、サービスレコードのＴＴＬフィールドに示された時間に基づいて有効期限が切れるように設定されている。この有効期間満了時前のある時期において、デバイスは順次大きくなる連続番号を有する新しいサービスレコードを作成し、その前のサービスレコードを置き換えることができる。データコレクションからコンテンツアイテムを取り去る方法、または「ホワイトアウトする」方法は、米国特許出願第１３／６８１，３０６号に記載されている。システムは新しいサービスレコードに基づいてデバイスに関連付けられたマニフェストに対して新しいルートハッシュ値を生成する。その後、デバイスは新しく生成されたルートハッシュ値を使って新しいサービスレコードで更新されたマニフェストをアドバタイズし、上記プロセスが反復される。更に、サービスレコードの有効期限満了時、例えば、ＴＴＬが経過した時、全てのデバイスは、それらのマニフェストから期限切れのサービスレコードを取り除き、期限切れのサービスレコードを含まない新しいハッシュアドバタイズメントを生成する。
【００６３】
一部の実施形態において、デバイスをシャットダウンした時、デバイスは０に設定されたＴＴＬおよびより大きなシリアル番号を有する新しいサービスレコードを作成することができる。デバイスはその更新されたサービスレコードに基づいてそのマニフェストをアドバタイズしこのアドバタイズメント送信直後にそれ自体の有効期限が切れるように設定することができる、これによって、このアドバタイズメントを受信する他のデバイスは、このマニフェストがより大きなシリアル番号に基づく最新のサービスレコードを含むことを認識する。
【００６４】
一部の実施形態において、アドバタイズされたインタレストは、その全体が、以下のフォーム
“／ｐａｒｃ／ｓｅｒｖｉｃｅｓ／ｐｒｉｎｔｅｒｓ／ａｄｖ／＜ｒｏｏｔｈａｓｈ＞／＜ｐａｙｌｏａｄ＞”
のサービスレコードを含むペイロードを含むことができる。
【００６５】
図７は、本発明の一実施形態による、コンテンツセントリックネットワークにおけるデバイス同士の間のマニフェストの同期に基づいてサービスディスカバリを容易にする例示的なネットワーク７００を示す。ネットワーク７００は、クライアントデバイス７１６、コンテンツ生成デバイス７１８、および、ノード７０２、７０４、７０６、７０８、７１０、７１２および７１４において、ルータまたは（プリンタなどの）他のデバイスを含むことができる。ノード７０２〜７１４は各々、一以上のマニフェストを含むことができる。例えば、ノード７１２はマニフェスト７２０を含む。マニフェスト７２０は、プレフィックスまたはネームスペース７２４と、以下の、サービスレコードネーム７３０．１−７３０．ｎ、シリアル番号７３２．１−７３２．ｎ、活動時間（ＴＴＬ）７３４．１−７３４．ｎ、およびダイジェスト７３６．１−７３６．ｎの一以上によって識別されるサービスレコードの順序付けされたリストと、を含む。ダイジェスト７３６．１−７３６．ｎは、ネーム７３０．１−７３０．ｎによって各々識別されるサービスレコードのハッシュ値を含む。ダイジェストは、ダイジェストがサービスレコードに対する一意の識別子であるように、（二つの異なるコンテンツオブジェクトの一方向ハッシュから同じ値が得られる）ハッシュ衝突の尤度が十分に低いサービスレコードのＳＨＡ−２５６ハッシュであってよい。マニフェスト７２０は、コレクションの個別のサービスレコードのハッシュ値７３６．１−７３６．ｎに基づいた相加的ハッシュ値である、ルートハッシュ７２２も含む。ルートハッシュ７２２はマニフェスト７２０の一意の識別子であり、コレクション内でサービスレコードを表している。
【００６６】
デバイスは、各デバイスがサービスレコードのコレクションを表しているマニフェストをキャリーするネットワーク上の任意のノードにおいて存在し得る。任意の二つのデバイスは、同じデータのコレクション、例えば、同じネームスペースに対するサービスレコードを表しているマニフェストをキャリーすることができ、マニフェストは、本明細書に記載されている方法を使用して同期され得る。用語「局所ノード」と「遠隔ノード」は、コンテンツセントリックネットワーク（ＣＣＮ）の任意のノードに適用可能であり、本開示においてＣＣＮ内の二つのノードを差別化するために使用される。同様に、用語「局所デバイス」および「遠隔デバイス」はＣＣＮの任意のノードのデバイスに適用可能であり、本開示では、例示目的として使用される。
【００６７】
一部の実施形態において、インタレストは、その対応するダイジェストを含む一つのサービスレコードをペイロードとして含むことができる。ＣＣＮのノードにおける任意のノードやデバイス（例えば、デバイス７１６、デバイス７１８、およびノード７０２〜７１４）は、送信デバイスのマニフェストのルートハッシュ値と送信デバイスに対応しているサービスレコードの両方を含むアドバタイズメントであるインタレストを送受信することができる。更に、任意のノードまたはデバイスは、例えば、送信デバイスのマニフェストのルートハッシュ値とペイロードとして含まれる送信デバイスのサービスレコードの両方を含むようなアドバタイズメントに対するクエリまたはリクエストであるインタレストを送受信することができる。
【００６８】
図８は、本発明の一実施形態による、デバイス７０２（遠隔デバイス「ラリー」）とデバイス７０６（局所デバイス「ナンシー」）との間の例示的な通信８００を示す。デバイス７０２とデバイス７０６は各々、同じルーティングプレフィックス、または、ネームスペース“／ｐ／ｐｒｎ／”を有するマニフェストを含む。遠隔デバイス７０２がネットワーク上で既に初期化され、少なくともそれ自体のサービスレコード“Ｌ−ＳＲ”からなるマニフェスト（“Ｌ”）を含むことを想定されたい。局所デバイス７０６は、ｉｎｉｔｉａｌｉｚｅ＿ｄｅｖｉｃｅ（デバイス初期化）手順８２０において初期化される。局所デバイス７０６は、それ自体のためにサービスレコード“Ｎ−ＳＲ”を作成し、その後、それ自体のサービスレコードから成るそれ自体に対する局所マニフェスト（“Ｎ”）を作成する。局所デバイスはまた、それ自体のマニフェストに対するルートハッシュ値“＜ｒｏｏｔｈａｓｈ（Ｎ）＞”も生成する。局所デバイス７０６は、遠隔デバイス７０２へ、フォーム“／ｐ／ｐｒｎ／ａｄｖ／ｑｕｅｒｙ”のｓｅｎｄ＿ｑｕｅｒｙ＿ｆｏｒ＿ａｄｖｅｒｔｉｓｅｍｅｎｔ（アドバタイズメントに対するクエリ送信）インタレスト８２２を送信する。ネットワーク上の任意のデバイスがアドバタイズメントに対するクエリを含むインタレストを受信できることに留意されたい。局所デバイス７０６はまた、ｓｅｎｄ＿ａｄｖｅｒｔｉｓｅｍｅｎｔ（アドバタイズメント送信）インタレスト８２４を送信することによって、それ自体のマニフェストとサービスレコードもアドバタイズする。このアドバタイズメントは、そのマニフェスト（“Ｎ”）のルートハッシュ値を含み、かつ、ペイロードとして局所デバイスのサービスレコード：“ｐ／ｐｒｎ／ａｄｖ／＜ｒｏｏｔｈａｓｈ（Ｎ）＞／＜ｐａｙｌｏａｄ＝（Ｎ−ＳＲ）＞”を含むハッシュアドバタイズメントである。（破線で示された）ｓｅｎｄ＿ａｄｖｅｒｔｉｓｅｍｅｎｔ（アドバタイズメント送信）８２４は局所デバイス７０６によって繰返し送信され得ることにて、初期化直後は発生しない。ノードまたはデバイスは、セグメントが多数回の反復で過剰飽和されるのを回避するためにゴシッププロトコルを使用することができる。例えば、ノードは、ランダムなバックオフを選ぶことができ、その際、第１のノードはそのルートハッシュをアドバタイズし、同じルートハッシュを有する第２のノードもそのルートハッシュをアドバタイズする。同じルートハッシュを有する第３またはそれ以降のノードはそのルートハッシュ送信を抑えることができる。
【００６９】
局所デバイス７０６は、インタレスト８２４と同様のフォーマットであり、遠隔デバイスのマニフェストのルートハッシュと、ペイロードとして遠隔デバイスのサービスレコード“／ｐ／ｐｒｎ／ａｄｖ／＜ｒｏｏｔｈａｓｈ（Ｌ）＞／＜ｐａｙｌｏａｄ＝（Ｌ−ＳＲ）＞”と、の両方を含む、ｒｅｃｅｉｖｅ＿ａｄｖｅｒｔｉｓｅｍｅｎｔ（アドバタイズメント受信）インタレスト８２６を受信することができる。局所デバイスは、ｕｐｄａｔｅ＿ｍａｎｉｆｅｓｔ（マニフェスト更新）手順８２８を実行する。局所デバイス７０６は、同じコレクションプレフィックスまたはネームスペース（“／ｐ／ｐｒｎ／”）に基づいて、そのマニフェストがアドバタイズインタレストのマニフェストと同じネームスペースを示しているかどうかを判断する。局所デバイス７０６は、含まれたサービスレコードが、局所デバイス７０２が既に所有しているものより新しい場合、その局所マニフェストにインタレスト８２６にペイロードとして含まれたアドバタイズされたサービスレコードを挿入することによって、その局所マニフェストを更新する。その後、局所デバイス７０６はその局所マニフェストに対して新しいルートハッシュ値を生成する。新しいルートハッシュ値がインタレスト８２６からアドバタイズされたインタレストのルートハッシュ値に等しい場合、局所デバイス７０６および遠隔デバイス７０２のマニフェストのサービスレコードのコレクションが同期される。よって、インタレストが遠隔デバイスのサービスレコードをペイロードとして含むので、遠隔および局所マニフェストは、ネットワークを介したマニフェスト転送を必要せずに、同期される。
【００７０】
局所デバイス７０６の新しいルートハッシュ値がアドバタイズされたインタレスト８２６のルートハッシュ値に等しくない場合、局所デバイス７０６は、図１〜６に関して記載された方法を用いて、集合の調整を実行する。局所デバイス７０６は、（フォーム“／ｐ／ｐｒｎ／ｄａｔａ／＜ｒｏｏｔｈａｓｈ（Ｌ）＞”の）ｒｅｑｕｅｓｔ＿ｒｅｍｏｔｅ＿ｍａｎｉｆｅｓｔ（遠隔マニフェスト要求）インタレスト８４２を送信し、（フォーム“／ｐ／ｐｒｎ／ｄａｔａ／＜ｒｏｏｔｈａｓｈ（Ｌ）＞”の）ｒｅｃｅｉｖｅ＿ｒｅｍｏｔｅ＿ｍａｎｉｆｅｓｔ（遠隔マニフェスト受信）メッセージ８４４を受信することによって、ｒｅｔｒｉｅｖｅ＿ｍａｎｉｆｅｓｔ（マニフェスト検索）手順８４０を実行する。局所デバイス７０６は、遠隔マニフェストに示されるサービスレコードのどのサービスレコードが、その局所マニフェストに示されるサービスレコードと異なっているかを判断するために、ｄｅｔｅｒｍｉｎｅ＿ｓｅｔ＿ｄｉｆｆｅｒｅｎｃｅ（差集合を求める）手順８４６を実行する。局所デバイス７０６は、（フォーム“／ｐ／ｐｒｎ／ｄａｔａ／ｎａｍｅ  ７３０．３＞”のｒｅｑｕｅｓｔ＿ｓｅｔ＿ｄｉｆｆｅｒｅｎｃｅ（差集合要求）インタレスト８５０を送信し、（フォーム“／ｐ／ｐｒｎ／ｄａｔａ／ｎａｍｅ  ７３０．３＋ｐａｙｌｏａｄ”の）ｒｅｃｅｉｖｅ＿ｓｅｔ＿ｄｉｆｆｅｒｅｎｃｅ（差集合受信）メッセージ８５２を受信することによって、ｒｅｓｏｌｖｅ＿ｓｅｔ＿ｄｉｆｆｅｒｅｎｃｅ（差集合を解く）手順８４８を実行する。
【００７１】
図９Ａは、本発明の一実施形態による、ネットワークにおける二つのデバイスのマニフェストの同期に基づいてサービスディスカバリを容易にする方法を示す流れ図である。局所デバイスは、ネットワークにおいて初期化される（動作９０２）。局所デバイスは、サービスレコードのネーム、シリアル番号、活動時間（ＴＴＬ）、およびダイジェストを含むサービスレコードをそれ自体のために作成する（動作９０４）。局所デバイスは、局所デバイスのサービスレコードから成る局所マニフェストを作成し（動作９０６）、マニフェストに含まれたサービスレコードのダイジェストに基づいて局所マニフェストに対してルートハッシュ値を生成する（動作９０８）。局所デバイスは同じネームスペース内の他のデバイスのマニフェストのルートハッシュ値を検索するためにクエリアドバタイズメントを送信する（動作９１０）。局所デバイスは、その局所マニフェストに対応しているアドバタイズメントを送信し、アドバタイズメントは局所マニフェストのルートハッシュ値を含み、ペイロードとして局所サービスレコードをキャリーしている（動作９１２）。局所デバイスは遠隔マニフェストに対応しているアドバタイズメントを受信し、アドバタイズメントは遠隔マニフェストのルートハッシュ値を含み、ペイロードとして遠隔サービスレコードをキャリーしている（動作９１４）。
【００７２】
局所デバイスは、その局所マニフェストと遠隔マニフェストが同じネームスペースに対応していると判断する（動作９１６）。一部の実施形態において、局所デバイスは、局所マニフェストがアドバタイズされたサービスレコードのネームと同じネームを有するサービスレコードを含むかどうかを判断する（動作９１８）。局所マニフェストがこのようなサービスレコードを含まない場合（判断９２０）、局所デバイスはペイロードからアドバタイズされたサービスレコードを局所マニフェストへ挿入することによって局所マニフェストを更新する（動作９２６）。局所マニフェストがこのようなサービスレコードを含む場合（判断９２０）、局所デバイスは、アドバタイズされたサービスレコードのシリアル番号が局所マニフェストの同じネームのサービスレコードのシリアル番号より大きいかどうかを判断する（動作９２２）。アドバタイズされたサービスレコードのシリアル番号が局所マニフェストの同じネームのサービスレコードのシリアル番号より大きくない場合（判断９２４）、局所デバイスに含まれるバージョンがより新しいので、方法は戻る。
【００７３】
アドバタイズされたサービスレコードのシリアル番号が局所マニフェストの同じネームのサービスレコードのシリアル番号より大きい場合（判断９２４）、局所デバイスは、現在のシリアル番号がネットワークに現在知られているシリアル番号より大きくなるように局所サービスレコードを更新する（動作９２６）。一部の実施形態において、デバイスがリブート（再立ち上げ）され、そのメモリを失った場合も、この条件は存在することができ、これによって、そのシリアル番号は、サービスレコードが故障前に最後にアドバタイズした番号未満に初期化される。その後、局所デバイスは、更新されたサービスレコードを局所マニフェストへ挿入することによって局所マニフェストを更新する（動作９２７）。データコレクションからコンテンツアイテムを取り去る方法または「ホワイトアウトする」方法は米国特許出願第１３／６８１，３０６号に記載されている。
【００７４】
図９Ｂは、図９Ａの流れ図９００に示した方法の続きを示した流れ図９５０である。その局所マニフェストを更新した後（動作９２６）、局所デバイスは局所マニフェストに対して新しいルートハッシュ値を生成する（動作９２８）。局所デバイスは、新しいルートハッシュ値がアドバタイズインタレストに含まれる遠隔マニフェストのルートハッシュ値と異なっているかどうかを判断する（動作９３０）。ハッシュ値が異なっていない場合（判断９３２）、遠隔マニフェストと局所マニフェストが同期しているので、方法は戻る。ハッシュ値が異なっている場合（判断９３２）、局所デバイスは、図１〜６に関して上記した集合調整とマニフェスト転送を実行する。局所デバイスは、アドバタイズされたインタレストのルートハッシュ値に基づいて遠隔マニフェストに対してリクエストを送信しこれを受信する（動作９３４）。局所デバイスは、遠隔マニフェストに示されたサービスレコードのどのサービスレコードが局所マニフェストに示されたサービスレコードとは異なっているかを判断する（動作９３６）。この差の判断に応答して、局所デバイスは異なっているサービスレコードに対してインタレスト集合を送信し（動作９３８）、リクエストされたサービスレコードの集合を受信する（動作９４０）。
【００７５】
図１０Ａは、本発明の一実施形態による、コレクションに表されたマニフェスト７２０のフォーマットとサービスレコードを示す表である。マニフェスト７２０は、プレフィックスまたはネームスペース７２４と、以下の、サービスレコードネーム７３０．１−７３０．ｎ、シリアル番号７３２．１−７３２．ｎ、活動時間（ＴＴＬ）７３４．１−７３４．ｎおよびダイジェスト７３６．１−７３６．ｎの一以上によって識別されるサービスレコードの順序付けされたリストと、を含む。ダイジェスト７３６．１−７３６．ｎは、ネーム７３０．１−７３０．ｎによって各々識別されるサービスレコードのハッシュ値を含む。ダイジェストは、ダイジェストがコンテンツオブジェクトに対して一意の識別子であるように（二つの異なるコンテンツオブジェクトの一方向ハッシュから同じ値が得られる）ハッシュ衝突の尤度が十分に低いサービスレコードのＳＨＡ−２５６ハッシュであってよい。マニフェスト７２０は、コレクションの個別のサービスレコードのハッシュ値７３６．１−７３６．ｎに基づいた相加的ハッシュ値である、ルートハッシュ７２２も含む。ルートハッシュ７２２はマニフェスト７２０に対して一意の識別子であり、コレクション内のサービスレコードを表している。以下の実施例において、ルートハッシュ値およびダイジェストは、これよりはるかに大なる場合があるが、例えば、“｛２２２｝”などのカッコ内の数値として示される。更に、サービスレコードのダイジェストと、経時的に変化する図１０Ｂ〜１０Ｄに示したマニフェスト７４０、７６０、および７８０の例示的なルートハッシュ値と、は共に、相加的ハッシュ値のサンプル表現として表示されているにすぎない。
【００７６】
図１０Ｂは、本発明の一実施形態による、局所デバイスが遠隔マニフェストを検索する必要がない、同期プロトコルを使ったサービスディスカバリ中の二つのマニフェストのフォーマットを示す表である。時間Ｔ１において、“／ｐａｒｃ／ｌａｒｒｙ”（ラリー）と名付けられたプリンタはノード７０２において動作可能であり、“／ｐａｒｃ／ｍａｒｖｉｎ”（マーヴィン）と名付けられたプリンタはノード７０４において動作可能である。プリンタ「ラリー」と「マーヴィン」は共にネームスペース“／ｐａｒｃ／ｓｅｒｖｉｃｅｓ／ｐｒｉｎｔｅｒ”に属し、よって、各々が同じネームスペースにおける他のマニフェストの全てに同期することを必要とするマニフェストを含む。「ラリー」と名付けられたプリンタまたはデバイスに関連付けられるマニフェスト７４０は、デバイス「ラリー」に対応している一つのサービスレコードを含む。「ラリー」に対応しているサービスレコードには、ネーム“Ｌ−ＳＲ”、シリアル番号１、および対応するダイジェスト｛２２｝が付される。マニフェスト７４０のルートハッシュ値は｛２２２｝である。「マーヴィン」と名付けられたプリンタまたはデバイスに関連付けられたマニフェスト７８０は、デバイス「マーヴィン」に対応している一つのサービスレコードを含む。「マーヴィン」に対応しているサービスレコードには、ネーム“Ｍ−ＳＲ”、シリアル番号７、および対応しているダイジェスト｛１１｝が付される。マニフェスト７８０のルートハッシュ値は｛１１１｝である。
【００７７】
動作中、時間Ｔ１において、ラリーはフォーム“／ｐａｒｃ／ｓｅｒｖｉｃｅｓ／ｐｒｉｎｔｅｒ／ａｄｖ／＜ｒｏｏｔｈａｓｈ＝｛２２２｝＞／＜ｐａｙｌｏａｄ＝（Ｌ−ＳＲ）＞”のアドバタイズメントを送信する。マーヴィンは、このアドバタイズメントを受信し、そのマニフェス７４０がアドバタイズメントにおいてペイロードとして含まれるサービスレコード“Ｌ−ＳＲ”を欠いていると判断する。時間Ｔ２において、マーヴィンは、そのマニフェスト７８０へサービスレコード“Ｌ−ＳＲ”を挿入し、マニフェスト（“Ｍ−ＳＲ”および“Ｌ−ＳＲ”）に示されている既存のサービスレコードのハッシュ値に基づいてマニフェスト７８０に対して新しいルートハッシュ値を生成する。これは｛１１１｝→｛３３｝で示される。
【００７８】
時間Ｔ２において、新しいルートハッシュ｛３３｝を有するマニフェスト７８０は、ルートハッシュ｛２２２｝を有しているアドバタイズされたマニフェスト７４０に同期していない。マーヴィンは、フォーム“／ｐａｒｃ／ｓｅｒｖｉｃｅｓ／ｐｒｉｎｔｅｒ／ａｄｖ／＜ｒｏｏｔｈａｓｈ＝｛３３｝＞／＜ｐａｙｌｏａｄ＝（Ｍ−ＳＲ）＞”のアドバタイズメントを送信する。ラリーはこのアドバタイズメントを受信し、そのマニフェスト７４０がアドバタイズメントにおいてペイロードとして含まれるサービスレコード“Ｍ−ＳＲ”を欠いていると判断する。時間Ｔ３において、ラリーは、そのマニフェスト７４０へサービスレコード“Ｍ−ＳＲ”を挿入し、その後、マニフェスト７８０（“Ｌ−ＳＲ”および“Ｍ−ＳＲ”）に示されている既存のサービスレコードのハッシュ値に基づいてマニフェスト７４０に対して新しいルートハッシュ値を生成する。これは｛２２２｝→｛３３｝で示される。このように、ノード７０２および７０４におけるデバイス「ラリー」と「マーヴィン」は、いずれのデバイスも他のデバイスから完全なマニフェストをダウンロードすることを必要とせずに、それぞれのマニフェスト７４０と７８０を互いに対して同期させた。
【００７９】
図１０Ｃは、本発明の一実施形態による、局所デバイスが遠隔デバイスから更新されたサービスレコードを受信する、同期プロトコルを使用したサービスディスカバリ中の二つのマニフェストのフォーマットを示す表である。時間Ｔ４において、マニフェスト７４０および７８０は、互いに同期しており、共にルートハッシュ｛３３｝を含む。時間Ｔ５において、ラリーはそれ自体のサービスレコード“Ｌ−ＳＲ”を更新し、シリアル番号２と新しいダイジェスト｛７２｝を割り当てる。ラリーは、マニフェスト７４０に示されている既存のサービスレコードのハッシュ値に基づいてマニフェスト７４０に対して新しいルートハッシュ値を生成する（更新された“Ｌ−ＳＲ”と“Ｍ−ＳＲ”）。これは｛３３｝→｛１０５｝で示される。ラリーは、フォーム“／ｐａｒｃ／ｓｅｒｖｉｃｅｓ／ｐｒｉｎｔｅｒ／ａｄｖ／＜ｒｏｏｔｈａｓｈ＝｛１０５｝＞／＜ｐａｙｌｏａｄ＝（Ｌ−ＳＲ）＞”のアドバタイズメントを送信する。マーヴィンは、アドバタイズメントとダイジェスト｛７２｝で更新されたラリーのサービスレコードを受信し、そのマニフェスト７８０が、アドバタイズメント（“２”）に含まれるサービスレコードのシリアル番号より少ないシリアル番号（“１”）を有するバージョン（“Ｌ−ＳＲ”）を含んでいることを判断する。時間Ｔ６において、マーヴィンは、マニフェスト７８０においてネーム“Ｌ−ＳＲ”とシリアル番号１を有するサービスレコードを、シリアル番号２とダイジェスト｛７２｝を有するマニフェスト７４０のアドバタイズされたサービスレコードで、更新することによって、マニフェスト７８０を更新する。マーヴィンは、｛３３｝→｛１０５｝で示されるマニフェスト７８０に対して新しいルートハッシュ値を生成する。このように、ノード７０２および７０４におけるデバイス「ラリー」と「マーヴィン」は、どのデバイスも他のデバイスから完全なマニフェストをダウンロードする必要がなくても、それぞれのマニフェスト７４０と７８０を互いに対して同期させた。
【００８０】
図１０Ｄは、本発明の一実施形態による、同期プロトコルを使用したサービスディスカバリ中の二つのマニフェストのフォーマットを示す表であり、局所デバイスは初期化され、サービスディスカバリを実行し、遠隔マニフェストを検索する。
【００８１】
図１０Ｃに示した時間Ｔ６において、ノード７０２および７０４で各々のマニフェスト７４０および７８０を有する「ラリー」と「マーヴィン」と名付けられたデバイスが動作可能である。マニフェスト７４０および７８０は同期しており、各々が、シリアル番号２とダイジェスト｛７２｝を有するラリーのサービスレコード（“Ｌ−ＳＲ”）と、シリアル番号７とダイジェスト｛１１｝を有するマーヴィンのサービスレコード（“Ｍ−ＳＲ”）と、を含む。マニフェスト７４０および７８０のルートハッシュは｛１０５｝である。
【００８２】
図１０Ｄに示した時間時間Ｔ７において、デバイス「ラリー」は、二つのサービスレコード：ネーム“Ｌ−ＳＲ”、シリアル番号２、およびダイジェスト｛７２｝を有するラリーに対するサービスレコードと、ネーム“Ｍ−ＳＲ”、シリアル番号７、およびダイジェスト｛１１｝を有するマーヴィンに対するサービスレコードと、を含むマニフェスト７４０を有するノード７０２において動作可能である。マニフェスト７４０のルートハッシュ値は｛１０５｝である。時間Ｔ７において、マーヴィンのマニフェスト（図１０には示されていない）がラリーのマニフェスト７４０に同期していることに留意されたい。時間Ｔ７において、ネーム“／ｐａｒｃ／ｎａｎｃｙ”を有するプリンタ（「ナンシー」）は、ブートアップされ（立ち上げられ）、ノード７０６において動作可能である。デバイス「ナンシー」はラリーおよびマーヴィンと同じネームスペース“ｐａｒｃ／ｓｅｒｖｉｃｅｓ／ｐｒｉｎｔｅｒｓ”に属している。ナンシーは、ネーム“Ｎ−ＳＲ”、シリアル番号１、および対応しているダイジェスト｛６５｝を有するサービスレコードであるサービスレコードをそれ自体のために作成する。ナンシーは、新しく作成されたサービスレコードを含むマニフェスト７６０を作成し、マニフェスト｛１６５｝に対してルートハッシュ値を生成する。その後、ナンシーは、ネットワークへ、フォーム“／ｐａｒｃ／ｓｅｒｖｉｃｅｓ／ｐｒｉｎｔｅｒｓ／ａｄｖ／ｑｕｅｒｙ”のネームスペース“ｐａｒｃ／ｓｅｒｖｉｃｅｓ／ｐｒｉｎｔｅｒｓ”に対するアドバタイズメントクエリを送信する。ナンシーは、ラリーからフォーム“／ｐａｒｃ／ｐｒｉｎｔｅｒｓ／ａｄｖ／＜ｒｏｏｔｈａｓｈ＝｛１０５｝＞／＜ｐａｙｌｏａｄ＝（Ｌ−ＳＲ）＞”のアドバタイズメントを受信する。ナンシーはこのアドバタイズメントを受信し、そのマニフェスト７６０がアドバタイズされたハッシュにおいてペイロードとして含まれるサービスレコード“Ｌ−ＳＲ”を欠いていると判断する。時間Ｔ８において、ナンシーは、そのマニフェスト７６０へサービスレコード“Ｌ−ＳＲ”を挿入し、マニフェストに示された既存のサービスレコード（“Ｎ−ＳＲ”および“Ｌ−ＳＲ”）のハッシュ値に基づいて、マニフェスト７６０に対して新しいルートハッシュ値を生成する。これは｛１６５｝→｛２００｝で示される。ナンシーはそのマニフェスト７６０のルートハッシュ｛２００｝がアドバタイズされたインタレストのルートハッシュ｛１０５｝と同じではないと判断し、よって、ナンシーは、本明細書に記載の方法を用いて完全な集合調整を実行する。
【００８３】
ナンシーは、チャンクキングプロトコルに基づいて、フォーム
“ｐａｒｃ／ｓｅｒｖｉｃｅｓ／ｐｒｉｎｔｅｒｓ／ｄａｔａ／＜ｒｏｏｔｈａｓｈ＝｛１０５｝＞／Ｓ０”，
“ｐａｒｃ／ｓｅｒｖｉｃｅｓ／ｐｒｉｎｔｅｒｓ／ｄａｔａ／＜ｒｏｏｔｈａｓｈ＝｛１０５｝＞／Ｓ１”，
“ｐａｒｃ／ｓｅｒｖｉｃｅｓ／ｐｒｉｎｔｅｒｓ／ｄａｔａ／＜ｒｏｏｔｈａｓｈ＝｛１０５｝＞／Ｓ２”
などのインタレストの集合を送信することによって、ルートハッシュ値｛１０５｝を有するマニフェストを検索し、その後、フォーム“ｐａｒｃ／ｓｅｒｖｉｃｅｓ／ｐｒｉｎｔｅｒｓ／ｄａｔａ／＜ｒｏｏｔｈａｓｈ＝｛１０５｝＞／Ｓ０＋ｐａｙｌｏａｄ”などのリクエストされたコンテンツオブジェクトを受信する。その後、ナンシーは、異なっているサービスレコードを判断し、異なっていると判断されたサービスレコードに対してインタレストの集合を送信する。この実施例において、ナンシーは、欠落しているサービスレコードが、シリアル番号７および対応するダイジェスト｛１１｝を有する“Ｍ−ＳＲ”と名付けられたマーヴィンに対応しているものであると判断する。ナンシーは、フォーム“／ｐａｒｃ／ｓｅｒｖｉｃｅｓ／ｐｒｉｎｔｅｒｓ／ｄａｔａ／Ｍ−ＳＲ”のインタレストを送信し、引き換えに、フォーム“／ｐａｒｃ／ｓｅｒｖｉｃｅｓ／ｐｒｉｎｔｅｒｓ／ｄａｔａ／＜ｐａｙｌｏａｄ＝（Ｍ−ＳＲ）＞のコンテンツオブジェクトを受信する。時間Ｔ９において、ナンシーはそのマニフェスト７６０へサービスレコード“Ｍ−ＳＲ”を挿入し、マニフェストに示された既存のサービスレコード（“Ｌ−ＳＲ”，“Ｍ−ＳＲ”および“Ｎ−ＳＲ”）のハッシュ値に基づいてマニフェスト７６０に対して新しいルートハッシュ値を生成する。これは｛２００｝→｛４２０｝によって示される。しかしながら、デバイス「ナンシー」のルートハッシュ｛４２０｝を有するマニフェスト７４０は、ルートハッシュ｛１０５｝を有するラリーのマニフェスト７４０（および恐らくは、図１０Ｃの時間Ｔ６に示されたマーヴィンのマニフェスト７８０などの他のマニフェスト）と同期しない。その後、ナンシーはフォーム“／ｐａｒｃ／ｓｅｒｖｉｃｅｓ／ｐｒｉｎｔｅｒｓ／ａｄｖ／＜ｒｏｏｔｈａｓｈ＝｛４２０｝＞／＜ｐａｙｌｏａｄ＝（Ｎ−ＳＲ）＞”のアドバタイズメントを送信し、ラリー（およびマーヴィンや他のネットワーク上のデバイス）はこのアドバタイズメントを受信し、その各々のマニフェストを、このアドバタイズメントにペイロードとして含まれるナンシーのサービスレコード（“Ｎ−ＳＲ”）で、更新する。時間Ｔ１０において、ラリーは、ダイジェスト｛６５｝を有するナンシー「Ｎ−ＳＲ」のサービスレコードをマニフェスト７４０へ挿入し、同じ新しいルートハッシュ値｛４２０｝を生成する。これは｛１０５｝→｛４２０｝で示される。また、マーヴィンがダイジェスト｛６５｝を有するＮ−ＳＲをマニフェスト７６０へ挿入し、同じ新しいルートハッシュ値｛４２０｝を生成できることに留意されたい。よって、ノード７０６における新たなデバイス「ナンシー」とノード７０２と７０４における既存のデバイス「ラリー」と「マーヴィン」は、マニフェストの転送を不要にするサービスレコードを含むアドバタイズメントを使用することによって、更には、図１〜６に関して説明したマニフェストの転送に基づいたコレクション同期プロトコルを使用することによって、それらのマニフェストを互いに同期させた。
【００８４】
図１１は、本発明の一実施形態による、コンテンツセントリックネットワークにおけるデバイス同士の間のマニフェストの同期化に基づいてサービスディスカバリを容易にする例示的なコンピュータおよび通信システムを示している。コンピュータおよび通信システム１１０２は、プロセッサ１１０４、メモリ１１０６、および記憶装置１１０８を含む。メモリ１１０６は、管理メモリとして作用する揮発性メモリ（例えば、ＲＡＭ）を含み、一以上のメモリプールを格納するために使用され得る。更に、コンピュータおよび通信システム１１０２は、ディスプレイデバイス１１１０、キーボード１１１２、およびポインティングデバイス１１１４に連結され得る。記憶装置１１０８は、オペレーティングシステム１１１６、コンテンツプロセッシングシステム１１１８、およびデータ１１３２を格納することができる。
【００８５】
コンテンツプロセッシングシステム１１１８は、コンピュータおよび通信システム１１０２による実行時に、コンピュータおよび通信システム１１０２に本開示に記載されている方法および／またはプロセスを実行させることができる命令を含むことができる。具体的には、コンテンツプロセッシングシステム１１１８は、遠隔ノードの遠隔マニフェストに対応しているアドバタイズメントを受信するための命令を含むことができ、アドバタイズメントは遠隔デバイスに対応しているサービスレコードを含む（アドバタイズメントメカニズム１１２２）。コンテンツプロセッシングシステム１１１８はまた、局所デバイスの局所マニフェストに対応しているアドバタイズメントを送信するための命令も含むことができ、アドバタイズメントは局所デバイスに対応しているサービスレコードも含む（アドバタイズメントメカニズム１１２２）。コンテンツプロセッシングシステム１１１８は、更新された局所マニフェストに対応しているアドバタイズメントを送信するための命令も含むことができ、その際、マニフェストはマニフェストのサービスレコードの活動時間（ＴＬＬ）が発生した時点で削除されるサービスレコードに基づいて更新されている（アドバタイズメントメカニズム１１２２）。
【００８６】
コンテンツプロセッシングシステム１１１８はまた、局所マニフェストと遠隔マニフェストが同じネームスペースに対応していることの判断に応答して、遠隔マニフェストのアドバタイズされたサービスレコードを局所マニフェストに挿入することによって、局所デバイスの局所マニフェストを更新するための命令も含むことができる（マニフェスト更新メカニズム１１２４）。コンテンツプロセッシングシステム１１１８は、遠隔デバイスからのアドバタイズされたサービスレコードのシリアル番号が局所マニフェストにおける同じネームのサービスレコードのシリアル番号より大きいとの判断に応答して、局所マニフェストのサービスレコードの値を、遠隔デバイスからのアドバタイズされたサービスレコードの値で、更新するための命令を含むことができる（マニフェスト更新メカニズム１１２４）。コンテンツプロセッシングシステム１１１８は、局所マニフェストのサービスレコードの活動時間（ＴＬＬ）が発生し次第、局所マニフェストからサービスレコードを削除することにより、局所マニフェストを更新するための命令を含むことができる（マニフェスト更新メカニズム１１２４）。
【００８７】
コンテンツプロセッシングシステム１１１８は、遠隔デバイスの遠隔マニフェストに対応しているアドバタイズメントに対してクエリを送信し、遠隔デバイスから、局所マニフェストに対応しているアドバタイズメントに対するクエリを受信するための命令を更に含むことができ、これらのアドバタイズメントはデバイスに対応しているサービスレコードを含む（クエリメカニズム１１２６）。
【００８８】
コンテンツプロセッシングシステム１１１８は、局所デバイスにより、ネットワーク上で初期化され、局所デバイスに対応しているサービスレコードを作成し、サービスレコードから成る局所デバイスに対するマニフェストを作成するための命令も含むことができる（初期化メカニズム１１２８）。
【００８９】
コンテンツプロセッシングシステム１１１８は、遠隔マニフェストに対してリクエストを送信し、遠隔マニフェストを受信し、遠隔マニフェストに関連付けられるコンテンツオブジェクトまたはサービスレコードに対するリクエストを送信し、遠隔マニフェストに関連付けられたリクエストされたコンテンツオブジェクトまたはサービスレコードを受信するための命令を含むことができる（通信メカニズム１１２０）。また、コンテンツプロセッシングシステム１１１８は、チャンキングプロトコルに基づいて、遠隔マニフェストを検索するためにインタレストの集合を送信するための命令も含むことができることにて、各インタレストがマニフェストの番号付きチャンクに対応する（通信メカニズム１１２０）。コンテンツプロセッシングシステム１１１８は、マニフェストに対応するアドバタイズメントを送信し、マニフェストに対するリクエストを受信し次第、マニフェストを遠隔ノードへ送信し、マニフェストに関連付けられたリクエストされたコンテンツオブジェクトまたはサービスレコードを遠隔ノードへ送信し、チャンキングプロトコルに基づいてインタレストの集合を受信する命令も含むことができることにて、各インタレストがマニフェストの番号付きチャンクに対応する（通信メカニズム１１２０）。
【００９０】
コンテンツプロセッシングシステム１１１８は、受信した遠隔マニフェストに基づいて、遠隔マニフェストに示されたサービスレコードのどのサービスレコードが局所マニフェストに示されたサービスレコードとは異なっているかを判断するための命令も更に含むことができる（差の判断メカニズム１１３０）。
【００９１】
データ１１３２は、本開示に記載された方法および／またはプロセスによって入力として必要とされるかまたは出力として生成される任意のデータを含むことができる。具体的には、データ１１３２は、サービスレコードのコレクションを表すマニフェスト；サービスレコード；サービスレコードのネーム；サービスの記述；シリアル番号；活動時間（ＴＴＬ）（秒）；サービスレコードの対応するダイジェスト；マニフェストによって表されるサービスレコードのダイジェストに基づいた相加的ハッシュ値であるマニフェストのルートハッシュ値；マニフェストを識別するマニフェストのネームスペースまたはルーティングプレフィックス；パケットがデータのアドバタイズメントに対応していることを判断する識別子；パケットがデータの転送に対応していることを判断する識別子；チャンキングプロトコルに基づいたマニフェストの番号付きチャンクに対応している番号、を少なくとも格納することができる。
【００９２】
本発明の詳細な説明において記載されたデータストラクチャおよびコードは、通常、コンピュータシステムによって使用するためにコードおよび／またはデータを格納することができる任意のデバイスまたは媒体であってよいコンピュータ可読記憶媒体に格納される。コンピュータ可読記憶媒体は、これらに限定されないが、揮発性メモリ、不揮発性メモリ、ディスクドライブ、磁気テープ、ＣＤ（コンパクトディスク）、ＤＶＤ（ディジタル多用途ディスクまたはディジタルビデオディスク）などの磁気または光記憶素子、または、現在知られておりまたは今後開発されるコンピュータ可読媒体を格納することが可能な他の媒体を含む。
【００９３】
本発明の詳細な説明の部分に記載された方法およびプロセスは、上述したコンピュータ可読記憶媒体に格納され得るコードおよび／またはデータとして具体化され得る。コンピュータシステムがコンピュータ可読記憶媒体に格納されたコードおよび／またはデータを読み出し実行する際、コンピュータシステムは、データストラクチャおよびコードとして具体化され、コンピュータ可読記憶媒体に格納される方法およびプロセスを実行する。
【００９４】
更に、上述した方法およびプロセスは、ハードウェアモジュールまたは装置に含まれ得る。ハードウェアモジュールまたは装置は、これらに限定されないが、特定用途向け集積回路（ＡＳＩＣ）チップ、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、特定の時間に特定のソフトウェアモジュールまたはコードの一部を実行する専用または共有プロセッサ、および現在知られておりまたは今後開発される他のプログラマブル論理素子を含むことができる。ハードウェアモジュールまたは装置は、起動されると、内部に含まれる方法やプロセスを実行する。
【図１】
2015201179.tif 000003
【図２】
2015201179.tif 000004
【図３】
2015201179.tif 000005
【図４】
2015201179.tif 000006
【図５】
2015201179.tif 000007
【図６Ａ】
2015201179.tif 000008
【図６Ｂ】
2015201179.tif 000009
【図６Ｃ】
2015201179.tif 000010
【図６Ｄ】
2015201179.tif 000011
【図６Ｅ】
2015201179.tif 000012
【図７】
2015201179.tif 000013
【図８】
2015201179.tif 000014
【図９Ａ】
2015201179.tif 000015
【図９Ｂ】
2015201179.tif 000016
【図１０Ａ】
2015201179.tif 000017
【図１０Ｂ】
2015201179.tif 000018
【図１０Ｃ】
2015201179.tif 000019
【図１０Ｄ】
2015201179.tif 000020
【図１１】
2015201179.tif 000021