(57)【要約】セキュリティと、インターオペラビリティと、モビリティと、優先順位およびサービス品質（ＱＯＳ）を含むリソース管理とに対処するように構成された構造およびアーキテクチャを有するユニファイイングネットワークモデルを提供する。このネットワークモデルのネットワークは、動的に生成されるルーティングテーブル（１８）を有する階層メッシュネットワークとして構成される。このネットワークモデルの構成は、ルーティングを最適化し、通信負荷を分散させる。ネットワーク上のすべてのデバイスが、通信のエンドポイントおよびフォワーダの両方になることができる。このネットワークモデルに、２つのモデルすなわちリンクモデルまたはスターモデルの１つを用いて表される基礎になるネットワークを含めることができる。ノードは、スループットを最適化するために階層関係構造で編成される。このモデルに、ローカルネットワークアドレスを動的に割り当てる暗号方法を含めることができる。
2006517077.tif 000002
【特許請求の範囲】
【請求項１】
当事者がリソースを安全に共用でき、期待されるサービス品質で通信できるようにするために、中央管理なしで信頼しない当事者を編成する方法。
【請求項２】
２つのノードの間の最短ルートを提供するために階層パシングおよびノード間階層関係を使用することによってスループットを最適化する形で効率的なインター通信を行うために階層関係構造でネットワーク上の複数のノードを編成するシステムであって、前記ネットワークが前記階層のすべてのレベルで前記同一の構造を有するシステム。
【請求項３】
動的副分割およびリソース制御の委任を可能にしながら継承集約および階層権利実施を介するリソース割振りを制御するシステム。
【請求項４】
署名された文書の前記交換を介してノード対話を制御するネットワーク通信の方法。
【請求項５】
パス再ルーティングおよび再組合せを介してリソース保証（サービス品質、ＱＯＳ）を動的に維持する非集中システム。
【請求項６】
単一ソースブロードキャストを、複数の異なる時間枠グループ化で個別に再ブロードキャストできるようにするブロードキャスト通信システム。
【請求項７】
ホストに要求をしている前記クライアントに認証要求自体の諸部分を安全に処理するように要求する高度にスケーラブルな認証方法。
【請求項８】
各独立エンティティに鍵配布の制御を与え、必要な時にインター鍵協力を可能にする形での公開鍵および秘密鍵を配布する方法。
【請求項９】
プロトコルレベルでの動的ルーティングを保護し、制御するのに暗号プリミティブ（アルゴリズム）の組を使用する処理。
【請求項１０】
ネットワークを含む前記ノードの階層関係に基づいて動的に通信ルートを選択する処理。
【請求項１１】
前記確立を要求しているノードに前記鍵交換を実施するのに必要な計算より複雑な計算を実行することを要求することによりＤＯＳを減らすノード間のリンクを確立する方法。
【請求項１２】
前記２つのノードの前記アイデンティティが前記リンクを介して外部から可視にならないように、暗号認証処理を介して２つのノードの間の通信リンクを確立する方法。
【請求項１３】
自己認証式である、アイデンティティ継承の非集中方法。
【請求項１４】
ルーティングを最適化し通信負荷を分散させる、ネットワーク内のノードパスの集約リソース可用性を定量化する非集中方法。
【請求項１５】
前記ネットワーク内の前記関連ノードに自動的分配される、暗号的に署名された文書を介する許可ベースネットワークポリシ制御を可能にする処理。
【請求項１６】
使用および委任のためにリソースを副分割できるようにするネットワークリソースに所有権および優先順位を割り当てる方法。
【請求項１７】
許可の集約継承を暗号的に検証し、集約された継承優先順位によるリソース割振りを実施する方法。
【請求項１８】
最適化されたクラスタリングにより、シミュレーテッドアニーリングを介してネットワークを副分割する非集中自律方法。
【請求項１９】
その定義または実装においてＱＯＳをサポートしないプロトコルを使用するネットワークノードの間のリンクでリソース割振りレベルを実施する方法であって、前記方法は、相対ＱＯＳを提供する既存ネットワークプロトコルとの旧版互換性を可能にするネットワークブリッジを使用する、方法。
【請求項２０】
前記所期の受信側の前記階層関係に依存して、必要に応じて、前記通信を再分配するネットワークのノードの間の通信をブロードキャストする方法。
【請求項２１】
非集中動的ルーティングネットワーク内で環状ルートを防ぐ技法。
【請求項２２】
ネットワークリソースの前記現在の使用率および接続に関して要求されたリソースの前記量に基づいてルートを最適に選択する非集中ルーティングの方法。
【請求項２３】
ローカルネットワークアドレスを動的に割り当てる暗号方法。
【請求項２４】
文書通信を行うことができる前記レートを制限することによって文書の前記通信をＤＯＳ（サービス拒否攻撃）から保護する方法。
【請求項２５】
できる限り少ないノード間通信を用いて、前記ネットワークを含むすべてのリンクの前記現行リソース可用性について前記ネットワークの各ノードが知らされる処理であって、前記ネットワークは、フル階層フラッディング技法および部分的階層フラッディング技法を使用して知らされる、処理。
【請求項２６】
信頼しないノードからなるネットワーク上で選挙の管理制御を可能にする、参加者、候補、選挙実施の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本願は、参照によってその全体を本明細書に組み込まれている、２００３年１月２４日出願の米国特許仮出願第６０／４４２，３２８号の利益を主張するものである。
【背景技術】
【０００２】
現在の通信の必要は、現在のシステムの容量を追い越している。音声通信とデータ通信の両方でよりよいセキュリティの必要があり、伝送ストリームを保護する必要が高まっている。同じことが、ラジオメッシュネットワークにあてはまるが、このラジオメッシュネットワークは、フェーズドアレイアンテナなどのラジオ技術の進歩と、無線８０２．１１アクセスポイントの消費者および企業による採用を介して可能になった。そのような非集中公衆メッシュネットワークは、信頼しない当事者が、中央管理の必要なしにネットワークリソースを共用し、制御する能力次第で定まる。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
改善された可用性および信頼性に関する必要と結合されたこの高まった要求が、ネットワークインターオペラビリティおよびユニフィケーションを最前部に持ってきた（たとえば、一部の通信モデルおよびネットワークモデルは、これらの必要の一部を満足するのを助けるためにアプリケーションおよびオペレーティングシステム（ＯＳ）レベルでパッチを使用してきた）が、そのような手段だけでは、必要なレベルのセキュリティおよびサービス品質をもたらすのに十分でない。
【発明を実施するための最良の形態】
【０００４】
本発明を、これからさまざまな実施形態に関して説明する。次の説明は、本発明のこれらの実施形態の完全な理解のためおよびその説明を可能にするための特定の詳細を提供する。しかし、当業者は、これらの詳細なしで本発明を実践できることを理解するであろう。他の場合に、本発明の実施形態の説明を不必要に不明瞭にしないようにするために、周知の構造および機能は詳細に図示せず、説明しない。
【０００５】
本説明で使用される用語が、本発明のある特定の実施形態の詳細な説明と共に使用されてはいるが、最も広義の穏当な形で解釈されることが意図されている。しかし、ある用語は以下で強調する場合があるが、制限的な形で解釈されることを意図されたすべての用語は、この詳細な説明のセクションでそのようなものとして具体的に定義される。
【０００６】
さらに、本発明は、下で説明する特徴の副組合せにも存する。もちろん、一実施形態で説明する要素または特徴を、他の実施形態でも使用することができる。
１．概要
次の説明は、セキュリティと、インターオペラビリティ（相互運用性）と、モビリティ（ｍｏｂｉｌｉｔｙ）と、優先順位およびサービス品質（ＱＯＳ）を含むリソース管理とに対処するように構成された構造およびアーキテクチャを有するユニファイイングネットワークモデルを対象とする。このネットワークモデルのネットワークは、動的に生成されるルーティングテーブルを有する階層メッシュネットワークとして構成される。このネットワーク上のすべてのデバイスが、通信のエンドポイントとフォワーダ（ｆｏｒｗａｒｄｅｒ）の両方になることができる。このネットワークモデルに、リンクモデルまたはスターモデルという２つのモデルの１つを用いて表される基礎になるネットワークを含めることができる。
【０００７】
用語「ノード」は、ネットワークのアクティブコンポーネントを指すのに使用される。ノードは、機能において異なる場合があるが、すべてのノードが、ネットワークモデルの基本ルーティングプロトコルに従う。ノードは、任意の個数の基礎になるネットワークプロトコルを介して接続される。ネットワークモデルは、ノードのグループを単一のグループと見ることを可能にし、動的ルーティング機構を任意のサイズにスケーリングできるようにする、階層的なネットワークの概念をサポートする。
【０００８】
このネットワークモデルでは、機構ベースの回路を使用して、直接に接続されていないノードの間のエンドツーエンド接続を作成する。この機構は、非同期転送モード（ＡＴＭ）に似ている。通信を望む２つのノードの一方が、回路確立要求を送信する。この要求は、ルーティングテーブルおよび回路の要件に基づいてネットワークを介して渡され、回路が、この要求の結果として作成される。回路が確立されたならば、その回路を移動するすべてのパケットが、同一のパスをたどる。
【０００９】
この回路機構は、ノードに、上位レベルエンドツーエンド接続のある認識を与える。これによって、ＱＯＳレベルを所与のデータフローに添付できるようになる。ＱＯＳポリシに関する決断は、回路構成時に行うことができる。これらの決断は、回路の存在の間に実施される。さらに、ルーティングは、回路ごとに静的であり、したがって、回路が作成されたならば、パケットルーティングは、単純で効率的である。
【００１０】
ノード間接続性およびリンクサービス品質データを含む、回路をセットアップするのに必要な情報は、階層動的ルーティングプロトコルを介してネットワークを介して転送される。したがって、各ノードは、その名前とローカル接続性だけを知っている。この情報は、各ノードで維持される必要があるデータの量を減らすと同時に適度によい回路構成ルーティング選択に十分な情報を提供する形で、ネットワークを介して伝搬される。
【００１１】
暗号方法が、プロトコル全体を通じて使用されて、ノード間を移動する制御データの安全性、信憑性、および正しさが保証される。これによって、エンドツーエンドユーザデータ転送を保護でき、動的ルーティングを耐タンパにすることができ、ＱＯＳを暗号的に制御でき、一般に、多数のサービス拒否（ＤＯＳ）攻撃を含むほとんどすべてのネットワークでの攻撃を防ぐことができるようになる。信頼の前提は、非常に悲観的であるが、多数の信頼されないノードとの間で有用な作業を行うことを可能にする。
【００１２】
このネットワークモデルのもう１つの重要な概念が、「文書」の概念である。文書は、判断を行うためにネットワークによって理解され、使用される、自己完結型の暗号的に署名されたデータの塊である。回路確立および動的ルーティングなどの上位プロトコルのほとんどで、文書の交換が用いられる。公開鍵配布機構は、文書の上で動作する。
【００１３】
さらに、文書は、ポリシを定義するのに使用される。これには、ユーザおよびグループ、ならびにリソース使用ポリシおよび権力の委任が含まれる。ポリシ文書は名前を有し、その名前によってポリシを参照することができる。多数のノードが、同一のポリシを共用することができ、ポリシ更新を追跡することができる。
【００１４】
文書の使用は、ネットワーク全体を通じて文書を編成し、配布する機構を必要とし、実際に、このネットワークモデルにそれを行うプロトコルがある。さらに、ルーティング更新など、一部の文書は、文書転送プロトコルに頼らずにネットワークを介してそれ自体を移動する追加の形を有する。
１．１  プロトコルスタック
図を参照すると、このネットワークモデルのプロトコルスタック１０は、Ｏｐｅｎ  Ｓｙｓｔｅｍ  Ｉｎｔｅｒｃｏｎｎｅｃｔｉｏｎ（ＯＳＩ）の７層ネットワークモデルに完全にはおさまらない。これは、少なくとも部分的に、ノードが上位レベルエンドツーエンド接続のある認識を有する能力と、ホップバイホップルーティング選択の能力の間の意図的な相互依存に起因する。この相互依存によって、詳細なＱＯＳを実施できるようになる。さらに、セキュリティは、やはりさらなる機能性および統合を得ることを試みて、下位の層で実施される。
【００１５】
プロトコルスタック１０に、インターフェースプロトコル１２が含まれ、これが、ノード間通信に使用される、基礎になるプロトコルである。インターフェースプロトコル１２は、ネットワーク全体を通じて一貫する必要がなく、実際に、ノードごとまたはリンクごとの基礎で変更することができ、同一のノードを接続する複数の異なるインターフェースプロトコルを設けることもできる。
【００１６】
プロトコルスタック１０に、インターフェースプロトコル１２の上位のリンクプロトコル１４が含まれる。リンクプロトコル１４は、隣との通信を開始し、隣の名前を判定し、基本的なリンク暗号通信を確立するなどの責任を負う。さらに、リンクプロトコル１４は、ＱＯＳ機構の基礎である。
【００１７】
プロトコルスタック１０に、信頼性のないパケットトラフィックを介する信頼性のあるシーケンス付きストリームを可能にする、軽量の信頼性プロトコル１６も含めることができる。信頼性プロトコル１６は、システムレベルプロトコルとユーザレベルプロトコルの両方によって使用され、プロトコルスタック１０内の複数の位置で使用される。
【００１８】
プロトコルスタック１０に、ネットワークを介するルーティングデータの移動を処理するルーティングプロトコル１８が含まれる。ルーティングプロトコル１８は、ネットワークが、現在の相互接続性状況ならびに現在のＱＯＳ状況を知っているようにする責任を負う。ルーティングプロトコル１８は、ノード、ネットワーク、ネットワークのネットワークなどの階層システムとしてネットワークを扱う。
【００１９】
プロトコルスタック１０の回路プロトコル（２０および２２）は、エンドツーエンド接続の確立およびデータの長距離転送を処理する。回路プロトコル（２０および２２）は、回路をセットアップする回路確立プロトコル２０と、回路を介してデータを移動する回路データプロトコル２２に分割されている。すべてのユーザデータが、回路データプロトコル２２を介して、生パケット（信頼性のない回路２４）または信頼性プロトコルの使用による信頼性のあるストリーム（信頼性のある回路２６）のいずれかとして転送される。
【００２０】
プロトコルスタック１０の文書転送プロトコル２８は、「文書」（下で詳細に説明する）と称するユーザが署名したデータコンポーネントを利用する。時々、ノードが、何らかの理由で、それが必要とする文書を追跡する必要がある場合がある。文書転送プロトコル２８は、名前によって文書を見つけ、その文書を要求元ノードに移動する処理を処理する。
１．２  ノードの諸概念
このネットワークモデルのプロトコルを話すデバイスのすべてが、エンドポイントおよび中間ポイントの両方を含むノードである。各ノードは、単一の一意のネットワークアドレスを有する。これは、階層名の形をとる。ノードの命名は、ルーティング構造および動的ルーティングデータの伝搬を決定するのを助けるのに使用される。各名前は、識別子のドットで区切られたリストとして表され、ノード名の最も詳細な部分が最初にあり、最も一般的な部分が最後になっている。
【００２１】
たとえば、名前ｍａｃｈｉｎｅ１．ｆｌｏｏｒ２．ｓｅａｔｔｌｅＯｆｆｉｃｅ．ｉｂｍに関して、この名前の最上位部分は、ｂｏｒｄｅｒ  ｇａｔｅｗａｙ  ｐｒｏｔｏｃｏｌ（ＢＧＰ）の匿名システム番号に類似するレベルにある。この命名フォーマットは、本明細書では「ドットパス命名フォーマット」と称するが、ユーザ、グループ、ネットワーク、文書、ポリシ、またはこの場合のノードを含む、ネットワークの多数の態様に命名するのに使用される。どの場合でも、階層は、明確に定義された意味を有する。
１．２．１  ノード間接続性
このネットワークモデルの各ノードは、１つまたは複数の他のノードと直接に通信することができる。これらのノードを、隣または時々直接ノードと称する。隣り合うノードによって通信に使用される基礎になるプロトコルは、ほとんどの部分で、ネットワーク層に重要でない。次のガイドラインによって、基礎になるトランスポートプロトコルのどれが適当であるかが決定される。
【００２２】
・コネクション指向またはコネクションレスとすることができる
・信頼性がないものまたは信頼性があるものとすることができる
・下で説明するリンクモデルまたはスターモデルのどちらかにあてはまる
・何らかの形でデータをパケット化する
・５１２バイト以上のパケット最大伝送単位（ＭＴＵ）（実際のまたは仮想の）を有する
・ノードＡがノードＢに送信できる場合に、ノードＢがノードＡに送信できるという点で両方向である
・パケットの複製または再順序付けを行うことができる
各ノードは、その隣を判定し、基礎になるコネクション指向プロトコルの物理接続を開始し、パケットを交換する方法を有する。物理／論理隣を見つけることは、あるディスカバリプロトコルを介して行うことができ、あるいは、所望の隣のリストを、ユーザまたは他の構成によって判定することができる。
【００２３】
このネットワークモデルは、２つの基本的なタイプのノード接続性すなわち、エッジおよびスターをサポートする。
単語エッジは、グラフ理論の用語に由来するものである。エッジは、単純なポイント・ツー・ポイント接続を表す、ノード間の接続である。これは、たとえば、無線近接内のノード、またはプライベートＴ１の他端のノードとすることができる。ノードＡが、２つの異なるノードＢおよびＣへのエッジを有するという事実は、ＢおよびＣがそれらを接続するエッジを有するか否かに無関係である。エッジの要件に、両方向性と、ある形のパケットベースのトランスポートが含まれるが、非パケット化物理リンクの場合に、パケットを、ある種のフレーミング機構を介して簡単に導入することができる。
【００２４】
スターは、接続性の過渡的なプロパティがその間で保たれる形で複数のノードを接続する、ある形の共用トランスポート機構を表すのに使用される。スターの例が、イーサネット（登録商標）スイッチに接続された複数のノードである。ノードＡが、イーサネット（登録商標）スイッチを介してノードＢならびにノードＣにパケットを送信できる場合に、ＢおよびＣの両方が、同一のイーサネット（登録商標）スイッチを介して両方向でパケットを送信することができる。したがって、スターは、通信するノードのグループの中心と考えることができる。ラジオネットワークは、通常はスターでない。スターを考えるもう１つの形が、接続性の分類された同等性である。
１．２．２  階層構造
ノードの命名によって、ノードのネットワークが組み合わされてネットワークのネットワーク、さらにはネットワークのネットワークのネットワークなどが形成されるという点で、ネットワークに階層構造が導入される。同一のネットワークグループの一部であるノードのグループ、または一緒にグループ化されるネットワークのグループを、しばしば、メタノードと呼ぶ。これは、ノードのネットワーク全体を単一のノードとみなすことができ、ネットワーク間接続性をこれらのメタノードの間のエッジとみなすことができるからである。
【００２５】
最上位メタノードは、グローバルネットワークまたはルートレベルネットワークを形成する。インターネットモデルでは、これらが、ＡＳＮを割り当てられたネットワークになる。これらのルートレベルネットワークまたはメタノードのそれぞれに、内部構造を含めることができる。実際の物理ノードに出会う前の構造の深さは、ネットワーク全体を通じて一貫する必要がない。すなわち、３つのより小さいノードからなるメタノードおよび単一の個々のノードを、ネットワーク内のピアとすることができる。ドットパスノード名に関して、ａ．ｂ．ｃとｘ．ｃの両方をノードとすることができ、ｂ．ｃ（メタノード）とｘ．ｃ（実際のノード）が、ネットワークｃ内のピアである。
【００２６】
ノードをメタノードにグループ化する時に、グループ内のすべてのノードが、完全に接続される。すなわち、グループ内の任意の２つの選択されたノードについて、それらを接続する、そのグループ内の他のノードだけからなるパスがある。明らかに、同一のスターにあるノードによって、大きいグループ化が作られる。いくつかの場合に、あるリンクの障害がメタノードのコンポーネントをもやは完全に接続された状態でなくするという点で、メタノードが「分割」することができる。ネットワークは、この状況を扱うことを試みるが、いくつかの障害モードが可能であり、１つまたは２つの主要なリンクがグループを分割できる形でノードをグループ化することは、避けなければならない。
１．２．３  動的ルート
動的ルーティングプロトコル１８は、ネットワーク全体を通じてノード接続性データおよびＱＯＳデータを伝搬させる責任を負う。ネットワークの階層的な性質および完全な接続性の前提が、ルートメッセージのフラッディング（ｆｌｏｏｄ）を制限するのに使用され、生成されるルートテーブルのサイズを最小にし、したがって、動的ルーティングがスケーリングされることが保証される。
１．３  文書の諸概念
このネットワークモデルの中心にあるのが、文書の概念である。このネットワークモデルの文書は、判断を行うためにネットワークによって理解され、使用される、自己完結型の署名されたデータの塊である。たとえば、公開鍵配布機構は、文書を介して動作する。動的ルーティングに、ルート関連文書の交換が含まれる。ＱＯＳ機構は、文書を使用して、ネットワーク使用に関する権利および権利の委任を定義する。ユーザによって送信される実際の回路構成要求は、文書である。
１．３．１  文書全般
１．３．１．１  署名
文書は、しばしば署名される。この署名は、公開鍵署名機構を使用する。興味深いことに、文書は、鍵の配布にも使用される。この機構ならびに周知のルート公開鍵が働けるようにするために、信頼のチェーンがある。文書に署名することによって、署名者がその文書を「サポートする」ことが示される。「サポート」の意味は、当の文書に依存する。たとえば、文書が、アイデンティティ文書である場合に、サポートは、当のアイデンティティが正当であることを署名者が保証することを意味する。文書が回路要求である場合に、サポートは、署名者がその回路を要求するユーザであることを示す。
１．３．１．２  命名と型付け
文書は、型を関連付けられ、多くの文書が、名前も関連付けられる。型は、型の事前定義のリストのうちの１つであり、各型が、異なる内部フォーマットを有する。新しい文書型を、プロトコルの代替バージョンで追加することができる。未知の文書型は、存在する時に無視される。文書は、名前も有することができる。この名前は、「ドットパス」の形をとる。ドットパスは、ドットによって区切られた識別子のリストである。ドットパスの例が、ｔｈｉｓ．ｉｓ．ａ．ｔｅｓｔである。所与の型およびドットパスは、通常は、単一の一意の文書に対応し、文書転送プロトコル２８は、その文書を見つけるように設計されている。しかし、回路要求または動的ルーティング更新を含めて、すべての文書が長期文書であるのではない。これらの文書は、名前を持たず、他の手段を介して伝搬され、短期文書と呼ばれる。
１．３．１．３  時間スコープ
文書は、時間スコープも有する。これに、作成時刻および満了時刻を含めることができる。満了時刻は、その後に文書がもはや意味がないと考えられる時刻である。たとえば、モバイルラジオデバイスからの動的ルート情報は、かなり素早い満了を有し、これは、それが有用である時間が限られていることを意味する。ノードの間に、かなり普遍的な時間同期化があると仮定する。しかし、所与のノードからのデータが、非常に信頼性のある形で時間順序付けされると同時に、ノード間時間が数秒から１分ずれる場合があるとも仮定する。１時間のタイムスキューは、許容不能と考えられる。
１．３．２  文書型
文書概念は、複数の異なる文書型および文書型クラスをサポートする。アイデンティティ文書など、そのうちの一部は、多数の他の文書が有用であるためにアイデンティティ文書に頼るという点で、他の文書とあいまって使用される。さらに、文書転送プロトコル２８に用いられる複数の文書型があり、言い換えると、文書の移動および保管に関する文書がある。文書型の素早い概要を、次のセクションで提供する。所与の文書型に関する文書フォーマットのより詳細な説明を、文書の使用に関係するセクションで与え、基本文書型に関するセクション４で少数の非常に基本的な文書を示す。
１．３．２．１  アイデンティティ文書
非常に柔軟な許可機構を可能にするために、ユーザ、ノード、およびアクティビティの他の論理単位を識別する形が必要である。さらに、エンティティのクラス全体に単一のルールを適用できるようにするために、これらのエンティティをグループ化できることが貴重である。このために、階層アイデンティティ命名機構を定義する。この命名機構は、単一の人間のユーザが複数の役割に対応するために複数のアイデンティティを有することができることを認識することができる。たとえば、ユーザが、会社の従業員としての１つのアイデンティティと、社会的グループのメンバとしてのもう１つのアイデンティティを有することができる。さらに、そのユーザの会社内であっても、ユーザがメンバであるさまざまな部署の複数の役割が存在する場合がある。また、人間以外のネットワークのコンポーネントが、アイデンティティを有することができ、たとえば、すべてのノードが、アイデンティティを有し、このアイデンティティは、実際にはネットワークアドレスである。
【００２７】
各アイデンティティは、ドットパスを介して命名される。‘ａ．ｂ．ｃ’および‘ｂ．ｃ’の両方が、同時に有効なアイデンティティであることが可能であり、‘ｂ．ｃ’はグループを表し、‘ａ．ｂ．ｃ’は個人またはサブグループを表す。各アイデンティティは、公開鍵および秘密鍵を関連付けられる。秘密鍵は、アイデンティティが表す人または機器と共にあり、公開鍵は、配布される。
【００２８】
アイデンティティ文書は、アイデンティティとその公開鍵を接続する文書である。アイデンティティ名は、文書転送プロトコル２８の目的に関して文書名である。各アイデンティティ文書は、階層内で上位のアイデンティティの公開鍵によって署名される。したがって、グループは、そのユーザおよびサブグループを選択することができ、このサブグループが、それ自体のサブグループを選択することができる。さらに、アイデンティティが葉アイデンティティすなわちサブアイデンティティを有することができないアイデンティティであるかどうかに関する、アイデンティティ文書に関連付けられるフラグがある。ａ．ｂ．ｃのｃに署名するのに必要な公開鍵であるルートアイデンティティ文書が、すべてのノードに存在すると仮定する。アイデンティティ文書に関する追加の詳細は、下のセクション４で提供する。
１．３．２．２  保管位置文書
文書転送プロトコル２８は、ネットワーク上で名前によって文書を見つけるのに使用される。文書転送プロトコル２８は、名前を実際のノードにリンクする文書に頼る。保管位置文書が、このプロセスを容易にする。保管位置文書は、文書名の所与のサブツリーに関する情報を含むノードのノード名を与える。たとえば、ＩＢＭ社の文書保管サーバの１つであるノードを指すｉｂｍ．ｃｏｒｐ．ｕｓの保管位置を設けることができる。
【００２９】
保管位置文書の名前は、それが権威を有するツリーである。この文書がポイントするノードに、そのツリー内のすべての文書が含まれるか、それが保管しない文書に関するより詳細なサブツリーの保管位置レコードが含まれる。同一の名前について複数の保管位置レコードを設けることができ、複数の文書保管サーバが可能になる。文書保管位置は、有効であるために、アイデンティティによって署名され、このアイデンティティは、それが保管するサブツリーと同等または上位である。保管位置文書に関する追加の詳細を、下のセクション１１で提供する。
１．３．２．３  論理名文書
論理名文書は、他の型の文書に、より人間が受け入れやすい、または組織的に構造化された世界のビューを与えるのに使用することができる。論理名文書は、リダイレクション戦略を実施するのに使用することもできる。論理名文書は、論理ドットパス（ルックアップ用のキー）、実際のドットパス、および文書型である。論理名文書は、論理ドットパスと同等または上位のアイデンティティによって署名される。論理名文書は、その実際のドットパスにリダイレクトする。論理名文書に関する追加の詳細を、下のセクション１１で提供する。
１．３．２．４  ルート更新文書
ルーティングデータを移動する処理中にノードの間で渡される複数のルーティング関連文書がある。これらの文書のすべてが、名前なしであり、文書転送プロトコル２８を介してルックアップすることができない。ルート更新文書に関する追加の詳細を、下のセクション９で提供する。
１．３．２．５  メトリックポリシ文書
メトリックポリシ文書は、回路確立判断およびデータ移動判断に使用される許可および委任を決定するのに使用される情報をノードに与える。基本的に、これらは、ＱＯＳポリシを保管する。これらのそれぞれが、ドットパス名を有し、これによって、ポリシ型のポリシを参照できるようになり、古いポリシの満了日付が経過した時に新しいポリシをルックアップできるようになる。この文書は、その名前と同等または上位のアイデンティティによって署名される。メトリックポリシ文書に関する追加の詳細を、下のセクション１０で提供する。
１．３．２．６  回路要求文書
これらは、名前なしの文書である（ドットパスを持たず、文書保管サーバに保管されないという点で）。これらには、回路構成に関する実際の要求が含まれる。そのような名前なし文書は、構成される回路を所望するアイデンティティによって署名される。回路要求文書に関する追加の詳細を、下のセクション１０で提供する。
１．３．２．７  リンクセットアップ文書
これらは、名前なしの文書である（ドットパスを持たず、文書保管サーバに保管されないという点で）。これらは、リンクをセットアップし、リンクを保護するのに使用されるキーイング情報を交換するのに使用される。そのような名前なしの文書は、リンクセットアップを開始するノードによって署名される。リンクセットアップ文書に関する追加の詳細を、下のセクション８で提供する。
２．規約と基本型
次の説明で、上で述べたプロトコルを記述するのに使用される規約を提示する。さらに、次の説明では、より複雑なデータ型を作成するのに使用される基本的な基礎データ型を提示する。
２．１  規約
２．１．１  型付け
ネットワークにまたがって移動されるさまざまなデータのインメモリ状態ならびに論理形の両方を記述するために、単純で半形式的な型付けシステムを導入する。データの所与の部分が、さまざまなデータ型を介して表され、単純型をより複合型に組み合わせる複数の形がある。実際の実装で使用されるインメモリ表現の詳細は、重要でなく、実際に、使用される型は、セマンティクスが保たれる限り、同一である必要がない。
２．１．２  エンコーディング
型の論理形の他に、一部の型は、エンコーディングも有する。このエンコーディングは、ネットワークを介する移動のために型をバイトのシーケンスにする形を表す。プロトコルの複数の実装がインターオペレートするのを容易にするために、エンコーディングは、記述と完全に一致させることができる。
２．１．３  プロトコルデータユニット
プロトコルデータユニット（またはＰＤＵ）は、名前付きの型であり、プロトコルの基本会話単位でもある。最も低いレベルで、プロトコルを、ＰＤＵの交換と見ることができ、さまざまなノードの状態の関連する変化が伴う。これらの物理的ＰＤＵのほかに、論理ＰＤＵ記述が、実装のより下位の態様にアプリケーションプログラマインターフェース（ＡＰＩ）を表すのに使用される場合もある。ＰＤＵ様記述は、プロトコルがエクスポートする上位ＡＰＩを表すのにも使用される。したがって、システムの他のコンポーネントとのインターフェースは、他のノードとのデータの送受信に似ている。実際の実装は、このメタファを使用する必要がないが、すべての記述が、このメタファを使用する。
２．２  基本型
２．２．１  型：整数型Ｕ＃およびＳ＃
整数型は、Ｕ８、Ｕ１６、Ｕ３２、Ｕ６４、Ｓ８、Ｓ１６、Ｓ３２、およびＳ６４であり、さまざまなサイズ範囲の符号なし整数および符号付き整数を表す。Ｕ（またはＳ）は、それぞれ、符号なしおよび符号付きを表し、この文字に続く数は、その数を表すのに使用されるビット数を表す。したがって、Ｕ８は、０から２５５までの数を保管することができ、Ｓ１６は、−３２７６８から３２７６７までの数を保管することができる。一般に、ビット数ｎを与えられれば、符号なし数は０から２ｎ−１まで、符号付き数は−２ｎ−１から２ｎ−１−１までになる。
【００３０】
バイトシーケンスとしての整数型のエンコーディングは、基本的な２の補数２進表現である。複数バイト整数について、ネットワークバイト順序（ビッグエンディアン）表現が使用される。
２．２．２  型：ＶａｒＩｎｔｅｇｅｒ
可変整数型は、符号なし整数を表すのに使用される。論理的に、０と２Ｎ−１の間の数を保管することができる。可変という性質は、エンコーディングに由来し、Ｎは、自動サイジング変数サイズであり、小さい数はより少ないスペースを占める。
【００３１】
数の値が、０と１２７（２７−１）の間である場合に、値のエンコーディングは、１バイトの標準２進整数表現である。値が１２８と２１４−１の間である場合に、この値は２バイトに保管される。これは、第１バイトの最上位ビットに１がセットされることを除いて、標準ネットワーク順２バイト整数である。値が２１４−１より大きい場合に、その数は、第１バイトの最上位２ビットの両方に１がセットされることを除いて、標準ネットワーク順４バイト整数として保管される。
２．２．３  型：ＴｉｍｅＬｏｃａｔｉｏｎ
時位置型は、ある時点を表す。すなわち、特定の瞬間である。たとえば、２００２年１月１日午後７時３０分時が、位置を表す１つの形である。時位置は、ウォールタイムではなく実際の絶対時刻を表し、したがって、タイムゾーンに影響されない。
【００３２】
時位置は、ＵＴＣ２００１年１月１日からのナノ秒数を表すＳ６４としてエンコードされる。
２．２．４  型：ＴｉｍｅＤｕｒａｔｉｏｎ
時持続期間型は、２つの時位置の間の相対的な差または言い換えれば持続時間を定義する。
【００３３】
時持続期間は、その持続時間を構成するナノ秒数を表すＳ６４として表される。
２．３  暗号型
２．３．１  型：Ｈａｓｈ
ハッシュ型は、バイトシーケンスの暗号ハッシュを表す。論理構造のハッシュは、記述された論理構造のエンコーディングであるバイトシーケンスのハッシュを指す。ハッシュが、複数の論理コンポーネントに対するのものして参照される時に、そのハッシュは、ハッシングされるものの記述で述べられる順序での各コンポーネントのエンコーディングの連結によって形成されるバイトシーケンスのハッシュと仮定される。
【００３４】
さらに、ハッシュは、ある値によって「キーイング」することができる。これは、キーが、ハッシングされるオブジェクトのエンコーディングの前および後の両方でエンコードされ、置かれ、ハッシュ値が、この新しいシーケンスの結果であることを意味する。このキーイングによって、同一のハッシュキーを知っているならば、キーイングされた領地内でハッシュ化されたデータの送信者を検証できるという点で、対称鍵署名が可能になる。
【００３５】
このプロトコルの代替実施形態で、複数の折衝可能な暗号ハッシュアルゴリズム選択をサポートすることができるが、本明細書で示される実施形態では、ＭＤ５暗号ハッシュを使用する。バイトのシーケンスをハッシュにすることの詳細および結果の１２８ビットハッシュの１６バイトのシーケンスとしての表現は、米国マサチューセッツ州ベッドフォードのＲＳＡ  Ｓｅｃｕｒｉｔｙ，Ｉｎｃ．（「ＲＳＡ」）社から入手可能な文書に記載されている。
２．３．２  型：Ｓｉｇｎａｔｕｒｅ
署名型は、あるデータの公開鍵署名を表す。一般に、署名が行われるデータのサイズに対する制約に起因して、この署名は、暗号ハッシュであり、この暗号ハッシュは、データのあるセクションのハッシュである。暗号ハッシュが信頼される限り、公開鍵署名は、ハッシュに入力されたデータブロック全体に対するものと考えることができる。
【００３６】
このプロトコルの代替実施形態で、複数の折衝可能な公開鍵署名アルゴリズム選択をサポートすることができるが、現行バージョンでは、ＲＳＡ公開鍵署名アルゴリズムを使用する。このアルゴリズムの詳細および結果の署名の表現は、ＲＳＡ文書に記載されている。
２．３．３  型：ＰｕｂｌｉｃＫｅｙ
公開鍵型は、ある公開鍵暗号化および署名機構を用いるエンコーディングおよび署名検証に使用できる公開鍵を表す。暗号化および署名が、同一の鍵を使用しない場合に、公開鍵型に両方の鍵が含まれる。
【００３７】
このプロトコルの代替実施形態で、複数の折衝可能な公開鍵署名暗号化アルゴリズム選択をサポートすることができるが、本明細書で示される実施形態では、ＲＳＡ公開鍵アルゴリズムを使用する。鍵は、２０４８ビットＲＳＡ鍵であり、適当な従来技術のＲＳＡ文書に記載されているようにエンコードされる。
２．３．４  型：ＳｙｍｍｅｔｒｉｃＫｅｙ
対称鍵は、対称暗号を使用する暗号化および暗号化解除に使用できる鍵を表す。
【００３８】
このプロトコルの代替実施形態で、複数の折衝可能な対称鍵暗号をサポートすることができるが、本明細書で示される実施形態では、その鍵フォーマットがＲＳＡによって開発され、文書化されているＤＥＳを使用する。
２．３．５  型：ＰｕｂｌｉｃＥｎｃｏｄｅｄ
公開エンコード型は、あるデータの公開鍵エンコーディングを表す。一般に、エンコーディングが行われるデータのサイズに対する制約に起因して、このエンコーディングは、対称鍵であり、この対称鍵は、他のデータのエンコードに使用される。
【００３９】
このプロトコルの代替実施形態で、複数の折衝可能な公開鍵エンコーディングアルゴリズム選択をサポートすることができるが、本明細書で示される実施形態では、ＲＳＡ公開鍵エンコーディングアルゴリズムを使用する。このアルゴリズムの詳細および結果のエンコーディングの表現は、ＲＳＡ文書に記載されている。
２．３．６  型：ＰｒｅＳｙｍｍｅｔｒｉｃ
前対称型は、対称暗号をある攻撃に対して安全にするのに必要な、初期化ベクトルまたは他のプリアンブルを表す。
【００４０】
このプロトコルの代替実施形態で、複数の折衝可能な対称鍵暗号をサポートすることができるが、本明細書で示される実施形態では、そのＩＶフォーマットがあるＲＳＡ文書に記載されているＤＥＳを使用する。
２．４  型の組合せ
型を組み合わせるか変更するさまざまな機構を、適所に置いて、単純な型から複合型を作るのを容易にすることができる。このセクションでは、そのような機構を説明する。３の主要な複合型に、シーケンス型、セット型、および構造型が含まれる。これらの型のすべてが、明確に定義されたエンコードの方法を有し、この方法は、その基本型をエンコードする方法に関連する。
２．４．１  シーケンス
シーケンスは、すべてが同一の型の要素の順序付きリストである。これは、ｓｅｑｕｅｎｃｅ＜Ｔｙｐｅ＞によって表され、Ｔｙｐｅは、すべてのシーケンス要素の型である。シーケンスに対する通常の動作に、要素の挿入および除去、その位置に基づく要素の発見、順序通りに要素を通る反復などを含めることができる。シーケンス内のオフセットを記述する時には、０ベースのインデックスを使用する。
【００４１】
シーケンスのインメモリ表現は、実装依存であり、同一の型のシーケンスであっても、それが操作される形に基づいて、コンテキストごとに異なる場合がある。
バイトのシーケンスとしてのシーケンスのエンコーディングは、ＶａｒＩｎｔｅｇｅｒとして表された複数の要素の連結であり、その要素のそれぞれが順序通りにエンコードされる。
２．４．２  セット
セットは、すべてが同一の型の要素の順序なしコレクションである。これは、Ｓｅｔ＜Ｔｙｐｅ＞によって表され、Ｔｙｐｅは、すべてのセット要素の型である。セットに対する通常の動作に、ある要件を満たす要素の発見、セットの和集合および交わり、ある要素の変更（オリジナル要素の除去および変更された要素の挿入と同等である）を含めることができる。もう１つの動作を、ランダムな順序または要素に対する比較関数に基づく特定の順序でのセットのトラバースとすることができる。数学的集合と同様に、セット内に同一の要素の２つの「コピー」が存在することはできない。この文書で説明するセットのすべての使用において、このケースが回避される。
【００４２】
セットのインメモリ表現は、しばしば、非常に複雑である。セットは、単に要素のコレクションとすることができるが、あるプロパティに基づいて要素を素早く見つける必要が、しばしば、ある形のインデクシングを必要とする。実際に、この詳細な説明では、セットが、セットに鍵／値対を挿入することによって、ある要素を別の要素に関連させるマップとして、しばしば使用される。さらに、ある特定の順序でセットをトラバースする必要が、しばしば、ある複雑さを導入する。
【００４３】
バイトのシーケンスとしてのセットのエンコーディングは、ＶａｒＩｎｔｅｇｅｒとして表された複数の要素の連結であり、セットのすべての要素のエンコーディングが、特定の順序ではない。
２．４．３  構造
構造は、それぞれがそれ自体の型を有する要素のシーケンシャルな名前付きリストからなる。これは、さまざまな異なる部分を組み合わせて単一の全体を形成するのに使用される。下の表１に、構造の通常の定義を示す。
【００４４】
【表１】
2006517077.tif 000003
【００４５】
表１の例には、型の２つの部分すなわちＴｙｐｅＯｎｅおよびＴｙｐｅＴｗｏがある。実際の構造の場合の名前は、構造の意味を説明するのを助け、要素を参照する形を与える。
【００４６】
構造のエンコーディングは、単に、所与の順序での構造のすべての部分のエンコーディングの連結である。
３．  文書エンコーディング
文書カプセル化は、信頼性プロトコル１６または、リンクプロトコル１４の場合の特殊なフラグメント化機構のいずれかのネットワークプロトコルを介する転送のための、文書の論理形のバイトのシーケンスへの変換の処理のための名前である。この章では、文書の論理形と「物理」形（オクテットストリームと称する）の間の関係を説明する。
３．１  コンポーネント型
まず、文書の一般的なサブコンポーネントを導入し、これらをバイトのシーケンスにする形を説明する。
３．１．１  型：ＤｏｔＰａｔｈ
ドットパスは、ドットによって区切られた識別子のリストである。これは、プロトコル内の複数の位置で使用される。各識別子は、区切り文字である「．」を含まない限り、印刷可能なグリフの任意のテキストシーケンスとすることができる。シーケンスは、識別子で始まり、識別子で終わり、ドットは、内部にのみ現れる。したがって、「ａ．ｂ．ｃ．」は、ドットで終わり、これに続く識別子がないので、不正である。
【００４７】
一実施形態では、ドットパスは、ＵＴＦ−８表現でのバイト数を表すＶａｒＩｎｔｅｇｅｒと、それに続く、テキストの形の実際のドットパスのＵｎｉｃｏｄｅ  ＵＴＦ−８としてエンコードされる。
３．１．２  型：ＤｏｃｕｍｅｎｔＴｙｐｅ
文書型は、列挙型である。その定義を、下の表２に示す。
【００４８】
【表２】
2006517077.tif 000004
【００４９】
文書型は、列挙番号を表すＶａｒＩｎｔｅｇｅｒとしてエンコードされる。
３．１．３  型：ＳｉｇｎａｔｕｒｅＢｌｏｃｋ
署名ブロックは、特定のアイデンティティによる、通常は暗号ハッシュを使用する、あるものの署名を表す。その構造を、下の表３に示す。
【００５０】
【表３】
2006517077.tif 000005
【００５１】
ここで、ＳｉｇｎｅｒＩｄｅｎｔは、署名するアイデンティティであり、ＳｉｇｎｅｒＳｉｇは、特定の署名者の暗号署名である。
３．２  基本的な文書の構造
３．２．１  型：Ｄｏｃｕｍｅｎｔ
文書型は、文書の全般的なフォーマットと、関連するエンコーディングを表す。文書本体と称する文書の部分は、文書の型依存部分である。文書型構造の例を、下の表４に示す。
【００５２】
【表４】
2006517077.tif 000006
【００５３】
表４を参照すると：
Ｔｙｐｅは、文書の型であり、以前に与えた列挙の要素である。
Ｎａｍｅは、文書の名前である。たとえば、所与のアイデンティティの公開鍵を含むアイデンティティ文書は、それを定義したアイデンティティの名前を付けられる。これは、文書転送プロトコル２８のルックアップキーでもある。名前なし文書型の場合に、このフィールドは、この構造から省略される。
【００５４】
Ｅｘｐｉｒａｔｉｏｎは、その後にこの文書がもはや有効でなくなる時である。
ＤｏｃｕｍｅｎｔＢｏｄｙは、文書の主題であり、その意味は、前に与えられたＴｙｐｅに依存する。各文書型が、本体のエンコーディングを記述することと、このエンコーディングが、自動サイズ指定であり、したがって、主文書デコード論理が、文書本体が終わった時を知ることが仮定されている。
【００５５】
ＤｏｃｕｍｅｎｔＨａｓｈは、要素Ｔｙｐｅ、Ｎａｍｅ（存在する場合に）、Ｅｘｐｉｒａｔｉｏｎ、およびＤｏｃｕｍｅｎｔＢｏｄｙのこの順序での暗号ハッシュである。
Ｓｉｇｎａｔｕｒｅｓは、さまざまな当事者によるこの文書の署名のリストである。各署名は、ＤｏｃｕｍｅｎｔＨａｓｈのハッシュの公開鍵署名である。
【００５６】
名前なし文書型についてＮａｍｅが省略されることを除く標準構造エンコーディング。
４．基本的な文書型
詳細な説明のこのセクションでは、複数のサブシステムによって使用される基本的な文書型を説明する。例示的実施形態には、１つのそのような文書型、アイデンティティ文書だけがある。
４．１  アイデンティティ文書
アイデンティティ文書は、アイデンティティ名をアイデンティティ公開鍵に接続するのに使用される。アイデンティティ文書は、有効になるために、署名ツリーで上位のアイデンティティによって署名される。すなわち、署名するアイデンティティのドットパスは、署名されるアイデンティティ文書のドットパスの正しいサフィックスである。たとえば、ａ．ｂ．ｃには、ｂ．ｃが署名できるが、ｄ．ｃまたはｘ．ａ．ｂ．ｃなどは署名することができない。
４．１．１  型：ＩｄｅｎｔｉｔｙＤｏｃｕｍｅｎｔＢｏｄｙ
アイデンティティ文書は、ＰｕｂｌｉｃＫｅｙからなる本体部分を有することができ、このＰｕｂｌｉｃＫｅｙは、文書名で名前を指定されたアイデンティティの公開鍵である。
５．リンクおよび回路メトリックパラメータ
リンクプロトコル１４およびルーティングプロトコル１８は、あるパスに沿ったＱＯＳ機能を判定するためにデータを収集する。回路を構成するユーザが、あるＱＯＳプロパティを要求する。さらに、セキュリティクリアランスレベルなど、ユーザが回路ルーティングに影響することを求める可能性がある他の要因、または他の類似する抽象的態様がある場合がある。
【００５７】
一般的な機構をそのようなデータの伝搬および操作に使用できるようにするために、「メトリックパラメータ」という概念を導入する。これは、回路ルーティングの判断処理の穏当な部分とすることができる、回路またはリンクの態様である。すべてのＱＯＳパラメータならびに複数のより抽象的なものが、メトリックパラメータというアイデアに含まれる。
【００５８】
したがって、各メトリックパラメータは、ある種の単一の測定可能な量を表す。たとえば、帯域幅は、待ち時間と同様にメトリックパラメータである。各メトリックパラメータは、それ自体の測定単位を有する。たとえば、ｂｐｓを帯域幅に、マイクロ秒を待ち時間に使用することができる。
【００５９】
さらに、２つの基本的なタイプのメトリックパラメータ値すなわち数値およびシンボルのサポートがある。シンボリックパラメータは、「ｄｉｖｉｓｉｏｎ」（会社の内部使用用）または「ＩＳＰ」（インターネット用）など、ユーザが気にする可能性があるネットワークのある論理的態様を表す。これらの態様も、ルーティング選択に影響する可能性がある。
【００６０】
ネゴシエーションに、さまざまなパラメータの必要な量および望ましい量（たとえば、ＸＹＺが、６４ｋｂｐｓを必要とするが、１００ｋｂｐｓを望む）を要求することが含まれるので、どの方向が「望ましい」かの理解がある。帯域幅の場合に、大きい数が望ましく、待ち時間の場合に、小さい数が望ましい。ＤｏｔＰａｔｈ命名を使用して与えられるシンボリックパラメータの場合に、より特定のものまたはより少なく特定のものが、望ましさを増やす可能性がある。
５．１  型：ＭｅｔｒｉｃＰａｒａｍｅｔｅｒ
メトリックパラメータ型は、どのパラメータが議論されているかを指定するのに使用される。このために、各パラメータに番号が与えられ、したがって、この型は列挙である。さらに、メトリックパラメータを、４つのカテゴリ、ＮｕｍｅｒｉｃＬｏｗ、ＮｕｍｅｒｉｃＨｉｇｈ、ＳｙｍｂｏｌｉｃＳｐｅｃ、およびＳｙｍｂｏｌｉｃＧｅｎに分類することができ、ここで、最初の部分は基本型の名前を指定し、第２の部分はどの方向が望ましいかを指定する。数値型の型は、ＶａｒＩｎｔｅｇｅｒである。パラメータ型は、Ｕ１６であり、最初の２ビットによってカテゴリが決定される。初期リストを、下の表５に示す。
【００６１】
【表５】
2006517077.tif 000007
【００６２】
説明している実施形態で、メトリックパラメータ型は、標準的なＵ１６エンコーディングを使用する。
５．１  使用
メトリック測定のアイデアは、下記を含む複数の使用に使用することができる。
【００６３】
・回路ごとの基礎および累積基礎の両方での総使用可能容量／メトリックおよび現行使用可能容量／メトリックの測定（ルーティングプロトコル１８）
・リソース割振りポリシの指定（ポリシ管理）
・回路要件／望みの指定（回路構成）
これらのすべてに関する型を、次のセクションで説明する
５．１．１  型：ＣｕｒｒｅｎｔＭｅｔｒｉｃＤａｔａ
現行メトリックデータ型は、エッジの総メトリックデータおよび現行メトリックデータを与える。含まれているのは、単一のパスが受け取れる最良の総量および現行量、ならびにすべてのパスにわたる総累積量および現行累積量である。この型の構造を、下の表６に示す。
【００６４】
【表６】
2006517077.tif 000008
【００６５】
シンボリック型の場合の構造の例を、下の表７に示す。
【００６６】
【表７】
2006517077.tif 000009
【００６７】
説明している実施形態で、現行メトリックデータは、標準的な構造エンコーディングを使用し、構造の選択は、第１要素によって決定される。
５．２  メトリックポリシ
メトリックポリシ文書は、異なる使用、特定のノードおよびユーザ、ならびにサブポリシへのリソースの分割を決定する。各ポリシは、名前を有し、この名前が、文書転送プロトコル２８を介するポリシ文書の鍵として働く。ポリシは、リソースをグループに分割し、グループのそれぞれをユーザ、ノードまたはメタノード、あるいはサブポリシに割り当てる。所与のノードは、単一のマスタポリシを割り当てられ、このマスタポリシは、それに出入りするリソースを分割するのに使用される。
５．２．１  型：ＳｕｂｈｏｌｄｅｒＴｙｐｅ
サブホルダ型は、３つのタイプのサブホルダのどれが使用されているかを定義するのに使用される。これは、下の表８に示されているように、単純な列挙である。
【００６８】
【表８】
2006517077.tif 000010
【００６９】
５．２．２  型：ＭｅｔｒｉｃＰｏｌｉｃｙＣｏｍｐｏｎｅｎｔ
ポリシは、数値メトリックパラメータだけに適用される。メトリックポリシ型は、所与のメトリックパラメータによって定義されるリソースへの絶対アクセスおよび相対アクセスに関する情報を表し、ポリシ文書型付けの一部である。メトリックポリシ型の例の構造を、下の表９に示す。
【００７０】
【表９】
2006517077.tif 000011
【００７１】
５．２．３  型：ＭｅｔｒｉｃＰｏｌｉｃｙＰａｒｔ
説明
ポリシパートは、ポリシに許可されたリソースの最終的なサブホルダの１つを表す。ポリシパートは、サブホルダの絶対特権および相対特権を記述する。ポリシパートの例の構造を、下の表１０に示す。
【００７２】
【表１０】
2006517077.tif 000012
【００７３】
５．２．４  型：ＭｅｔｒｉｃＰｏｌｉｃｙＢｏｄｙ
ポリシ本体は、メトリックポリシ文書の本体である。メトリックポリシ文書への鍵は、ポリシの名前である。ポリシは、ポリシ名より一般的なアイデンティティによって署名される。ポリシ本体の例の構造を、下の表１１に示す。
【００７４】
【表１１】
2006517077.tif 000013
【００７５】
５．３  メトリック要件
メトリックシステムの第３の用途は、回路構成中に要件を指定することである。これは、単一要件型およびメトリック要件を使用して行われ、これを、下の表１２〜１４に示す。
５．３．１  型：ＳｉｎｇｌｅＲｅｑｕｉｒｅｍｅｎｔ
【００７６】
【表１２】
2006517077.tif 000014
【００７７】
【表１３】
2006517077.tif 000015
【００７８】
５．３．２  型：ＭｅｔｒｉｃＲｅｑｕｉｒｅｍｅｎｔｓ
【００７９】
【表１４】
2006517077.tif 000016
【００８０】
６．インターフェースＡＰＩ要件
６．１  概論
ネットワークモデルのノードは、インターフェースＡＰＩのメソッドを呼び出し、このメソッドは、基礎になるインターフェースのネイティブプロトコルを使用して、パケットを送信するか要求された動作を実行する。ネイティブプロトコルを介してこのインターフェースに入るパケットおよびイベントは、インターフェースプロトコル１２内のコールバックに変換され、プロトコルスタック１０に送られる。したがって、インターフェースＡＰＩは、物理ネットワークの多数の型を同等の形で扱えるようにする、抽象化の層である。ＡＰＩを呼び出し、コールバックを受け取る処理は、パケットの送信および受信に非常に似ている。
【００８１】
この基礎になるプロトコルが、複数のノードへのリンクに同一の物理／論理インターフェースを介して到達できるようにするアドレッシング機構を有することができると仮定されるが、これを、単純なポイント・ツー・ポイントリンクにすることもできる。これらのリモートアドレスは、インターフェース固有であり、上位プロトコルに不透明である。基礎になるプロトコルを、コネクション指向にすることができ、その場合に、アドレスは、接続すべき位置を定義するが、そうでない場合に、アドレスは、パケットごとの宛先を定義する。基礎になるプロトコルは、パケットベースであり、各インターフェースは、パケットのデータ部分に関する明確に定義されたＭＴＵを与えられる。
【００８２】
さらに、一部のインターフェース（ラジオなど）は、新たに発見されたリモートノードについてネットワーク層に警告することを望む場合がある。また、一部のインターフェース（イーサネット（登録商標）など）は、ＡＲＰに似た、ノード解決の方法を可能にするためのある形のブロードキャストをサポートする。このＡＰＩは、これらの機構の両方をサポートする。
６．２  インターフェースプロトコル基本型
ここでは、インターフェースＡＰＩとの通信に使用される基本データ型を導入する。
６．２．１  型：ＲｅｍｏｔｅＡｄｄｒｅｓｓ
リモートアドレス型は、このインターフェースによって理解されるリモートアドレスの不透明な表現を提供する。この型は、多分インターフェース自体による場合を除いて、ネットワークを介して送信されず、したがって、エンコーディングを有しない。したがって、これを含むすべての構造が、エンコーディングを有しない。
６．２．２  型：ＳｅｅｋＲｅｑｕｅｓｔＩＤ
シーク要求ＩＤ型は、要求を応答に関連付けるのに上位プロトコルによって使用される数を提供する。インメモリ形は、Ｕ３２と同一である。この型は、多分インターフェース自体による場合を除いて、ネットワークを介して送信されず、したがって、エンコーディングを有しない。したがって、これを含むすべての構造が、エンコーディングを有しない。
６．３  読取および書込
６．３．１  ＡＰＩ：ＳｅｎｄＰａｃｋｅｔ
パケット送信機能は、パケットを、送信すべきインターフェースに送る。パケット送信機能のパラメータの例を、下の表１５に示す。
【００８３】
【表１５】
2006517077.tif 000017
【００８４】
表１５では、Ａｄｄｒｅｓｓが、パケットが送信されるリモートアドレスであり、ＰａｃｋｅｔＤａｔａが、パケットデータであり、これは、インターフェースのＭＴＵより小さい。
６．３．２  ＡＰＩ：ＲｅｃｅｉｖｅＰａｃｋｅｔ
パケット受信機能は、インターフェースがパケットを受信した時にインターフェースによって呼び出される。パケット受信機能のパラメータの例を、下の表１６に示す。
【００８５】
【表１６】
2006517077.tif 000018
【００８６】
表１６を参照すると、Ａｄｄｒｅｓｓは、パケットがそこから到着したリモートアドレスであり、ＰａｃｋｅｔＤａｔａは、パケットデータであり、これは、インターフェースのＭＴＵより小さい。
６．４  シーク
６．４．１  ＡＰＩ：ＳｅｅｋＮｏｄｅ
ノードシーク機能は、パケットを、送信すべきインターフェースに送る。ノードシーク機能のパラメータの例を、下の表１７に示す。
【００８７】
【表１７】
2006517077.tif 000019
【００８８】
表１７を参照すると、ＲｅｑｕｅｓｔＮｕｍｂｅｒは、結果のコールバックを呼び出しに関連付けるのに使用されたＵ３２であり、ＮｏｄｅＮａｍｅは、探されるノードのノード番号であり、Ｔｉｍｅｏｕｔは、探されるノードが見つかるのをノードシークが待つつもりがある時間の長さである。
６．４．２  ＡＰＩ：ＳｅｅｋＦｏｕｎｄ
シーク発見機能は、インターフェースが未解決の要求と一致するノードを見つけた時にインターフェースによって呼び出される。シーク発見機能のパラメータの例を、下の表１８に示す。シーク発見の後に、要求ＩＤは、もはや使用されず、再利用することができる。
【００８９】
【表１８】
2006517077.tif 000020
【００９０】
表１８を参照すると、ＲｅｑｕｅｓｔＮｕｍｂｅｒは、この応答が関連する要求であり、Ａｄｄｒｅｓｓは、見つかったノードのリモートアドレスである。このリモートアドレスは、現行である（パケットをそれに送信することができる）。
６．４．３  ＡＰＩ：ＳｅｅｋＦａｉｌｕｒｅ
シーク失敗機能は、インターフェースが、呼出し元の代わりにノードを探すことを試みてタイムアウトした時に、インターフェースによって呼び出される。シーク失敗機能のパラメータの例を、表１９に示す。シーク失敗の後に、要求ＩＤは、もはや使用されず、再利用することができる。
【００９１】
【表１９】
2006517077.tif 000021
【００９２】
表１９を参照すると、ＲｅｑｕｅｓｔＮｕｍｂｅｒは、この応答が関連する要求である。
６．５  検出およびアドレスダウン
６．５．１  ＡＰＩ：ＤｅｔｅｃｔＮｏｄｅ
ノード検出機能は、インターフェースがネットワーク上で別のノードを検出した時に呼び出される。ノード検出機能のパラメータの例を、表２０に示す。これは、ノードがラジオ範囲に入った時、または、たとえば、ブロードキャストネットワークの別のノードがローカルノード名を有するシークを送信した時に行われる可能性がある。
【００９３】
【表２０】
2006517077.tif 000022
【００９４】
表２０を参照すると、Ａｄｄｒｅｓｓは、検出されたノードのアドレスであり、ＮｏｄｅＮａｍｅは、ノードのありそうな名前である。この呼び出しを受け取った後に、Ａｄｄｒｅｓｓが現行である（パケットを書き込まれることができる）。ＲｅｍｏｔｅＡｃｔｉｖｅは、リモートノードの一部でのイニシアティブのレベルを示すフラグであり、リモート側がそれを意図する時にリンクネゴシエーションを開始しないようにするヒントである。
６．５．２  ＡＰＩ：ＡｄｄｒｅｓｓＤｏｗｎ
アドレスダウン機能は、アドレスがもはや現行でないことと、ノードがもやはそれにパケットを送信しないことをノードに警告するために呼び出される。アドレスダウン機能のパラメータの例を、表２１に示す。
【００９５】
【表２１】
2006517077.tif 000023
【００９６】
表２１を参照すると、Ａｄｄｒｅｓｓは、もはや現行でないアドレスである。
７．信頼性プロトコル
７．１  概論
信頼性などのＴＣＰストリームを特定の層に作り込むのではなく、軽量信頼性プロトコル１６を、設計全体で使用することができる。このプロトコルは、３つのフラグビット、および２つの３２ビット数（シーケンスおよび肯定応答）の余地を必要とする。このプロトコルは、信頼性のない両方向パケット伝送機構を信頼性のあるものに変える。この機構は、ＴＣＰによって使用されるものと同一である。１つの相違は、チャネル（ＩＰおよびポート）の概念が、信頼性態様から分離されており、同時に接続の２つの方向をオープンすることを必要とする理由がなく、したがって、１方向の信頼性のある接続が許容されるからである。
【００９７】
下位２方向接続ごとに、いずれかの方向の１つのストリームだけが許容される。前の接続のクローズの確認を受信する前に新しい接続を開始することを試みることは、許容されない。信頼性層の仮想ＰＤＵ定義を、下で与えるが、実際のコンポーネントは、望みの領地内で基礎になるパケットに置くことができる。
【００９８】
信頼性プロトコル１６の詳細は、この説明では説明しない。というのは、これらが、意味論的にＴＣＰによって使用される信頼性機構と同一またはこれに類似するからである。
８．リンクプロトコル
８．１  概論
リンクプロトコル１４は、ノード間の通信の最下位である。これは、防御の最前線であり、すべてのノード間データの安全性および管理を扱うと同時に、ＱＯＳがそこから導出される基礎構成である。リンクプロトコル１４は、下記に使用される。
【００９９】
・リモートノードのアイデンティティを検証する
・リンクを介して移動するデータの読取および／または変更を防ぐ
・ＣＰＵオーバーロード、テーブルオーバーフローに基づくサービス拒否攻撃を防ぎ、パケット挿入が他の未変更のパケットの伝送を損なることができないことを保証する
・上位プロトコルによって使用される基礎ＱＯＳ測定値を定義する
・一貫性のあるノード間伝送機構を作成する
・上位プロトコルが制御パケットに使用する信頼性のあるサブチャネルを作成する
リンクプロトコル１４は、両サイドのアイデンティティを確立し、暗号化およびパケットごとの検証に使用される対称鍵を交換する。リンク確立中に使用される必要な公開鍵機構の計算的な複雑さおよびＣＰＵ停止に基づくＤＯＳ攻撃の危険性のゆえに、ノードは、そのＣＰＵ時間のごく一部だけをリンク確立に費やす。正当な試みを追い返すことをなくすために、ＤＯＳ攻撃者が適度な割合で「正しい」要求を送信できる可能性を低くするための計算的チャレンジが、実施される。正しさをテストする方法が、ペナルティ内で十分に素早く検査されると仮定する。
【０１００】
さらに、状態が、チャレンジ要求について保持されず、成功裡のチャレンジ応答についてのみ保持され、したがって、インメモリテーブルに対するＤＯＳ攻撃も回避することができる。また、暗号方法が、誤った応答を防ぐことなどに使用される。
【０１０１】
この複雑さのすべてが、リンクセットアップ文書と称する単一の文書の転送に使用され、このリンクセットアップ文書には、公開暗号化され署名された対称鍵が含まれる。１つのこの文書が処理され、リンクが確立されたと考えられ、応答が返される。次に、このリンクが、ＱＯＳ情報と共に、対称暗号化され、暗号的にチェックサムをとられたパケットを転送するのに使用され、このＱＯＳ情報は、リンクプロトコル１４の「アクティブ化された」部分を構成する。
８．２  リンク文書
８．２．１  型：ＬｉｎｋＳｅｔｕｐＢｏｄｙ
上で導入したリンクセットアップ文書は、初期リンク鍵交換に使用される。これは、名前なしの文書である。これは、開始ノードによって署名される。リンクセットアップ文書の構造は、宛先ノードに対して公開エンコードされた単一の対称鍵である。
８．３  リンク文書のパケット化
８．３．１  型：ＬｉｎｋＤｏｃｕｍｅｎｔＰａｒｔ
リンク文書パートは、開始ノードの完全に識別する文書化と組み合わされたリンクセットアップ文書からなり、このすべてが、リンクセットアップ文書から一緒に連結される。このバイトのストリングは、リンクＭＴＵに収めるには大きすぎる可能性が非常に高く、したがって、パートに分割される。これらのパートが、暗号的にハッシュ化される。最初の要求に、パートのそれぞれのハッシュが含まれ、鍵が交換される前に、間に入った攻撃者がデータを偽造できるようにすることなく、主要求の受け入れが、パートへの道を開くことができる。
【０１０２】
リンク文書パートの構造の例を、下の表２２に示す。
【０１０３】
【表２２】
2006517077.tif 000024
【０１０４】
表２２を参照すると、ＰａｒｔＮｕｍｂｅｒは、現行パートの整数パート番号であり、０ベースインデックスであり、ＰａｒｔＯｆｆｓｅｔは、リンク文書化セット全体に対するこのパートのデータ部分のバイト単位のオフセットであり、ＰａｒｔＳｉｚｅは、データ部分のバイト単位のサイズであり、Ｄａｔａは、そのパートの実際のデータである。データの暗号ハッシュは、下で詳細に説明するように、リンク開始要求と共に送信される。
８．４  リンク要求型
８．４．１  型：ＬｉｎｋＲｅｑｕｅｓｔ
リンク要求型には、要求元に関する情報および後に続く文書のハッシュが含まれる。要求は、次のセクションで説明するようにチャレンジをもたらし、受信側は、チャレンジの複雑さを判断する。リンク要求のフォーマットの例を、下の表２３に示す。
【０１０５】
【表２３】
2006517077.tif 000025
【０１０６】
表２３を参照すると、ＲｅｍｏｔｅＮｏｄｅは、要求するノードのノード名であり、ＮｕｍｂｅｒＯｆＰａｒｔｓは、前のセクションで説明した、文書を形成する実際のデータパートの個数であり、ＲｅｑｕｅｓｔＤｏｃＳｉｚｅは、これらのパートのすべての総サイズであり、ＰａｒｔＨａｓｈｅｓは、パート番号の順の、各パートのハッシュのリストである。
８．５  リンクチャレンジ交換
リンクチャレンジ機構の目的は、リンクがリンク文書の妥当性を検査する前に、要求元が作業を行えるようにすることである。というのは、リンク文書の保管、再組立、および暗号検証が、自明な処理ではなく、検証されないノードが、検査するノードにそのような作業を行うことを強制することを可能にすることが、リソースの長時間の停止状態をもたらす可能性があるからである。
【０１０７】
このために、ノードは、それとのリンクを確立することが望まれるノードに「チャレンジ」を要求することができる。この要求を受信したノードは、ＣＰＵによって制約された暗号タスクである新しいチャレンジを作成し、チャレンジに署名する。プロトコルを継続するために、要求元ノードは、署名されたチャレンジを、解と共に返す。注：解を受け取るまで、受信ノードは、状態を保管する必要がなく、大きい計算機能を実行する必要がない。明白な解を受け取った時に、解を検査する処理は、適度に速い。
【０１０８】
このプロトコルのこのバージョンについて選択されたチャレンジは、特定の暗号ハッシュをもたらすデータの欠けている部分を探すことである。ハッシュが強い限り、これは、未知のデータ部分のブルートフォース検索をもたらす。したがって、受信側ノードは、未知のビット数を変更することによって、望み通りにチャレンジを難しくまたは簡単にすることができる。
【０１０９】
チャレンジが真に受信側ノードによって選択されたことを確かめ、チャレンジに関連する要求が、チャレンジがそれに応答して送信された要求と同一であることを確かめるために、チャレンジおよび要求データが、受信側ノードだけに既知の鍵を用いて暗号的にハッシュ化される。
８．５．１  型：ＬｉｎｋＣｈａｌｌｅｎｇｅ
リンクチャレンジ型は、実際の暗号チャレンジを表すのに使用される。その構造の例を、表２４に示す。
【０１１０】
【表２４】
2006517077.tif 000026
【０１１１】
表２４を参照すると、ＰｒｅＰａｒｔは、ハッシュＲｅｓｕｌｔを作るのに使用されたデータの第１部分であり、ＮｕｍｂｅｒＯｆＢｉｔｓは、ハッシュプリイメージ内の追加ビット数である。ビット数が８で割り切れない場合には、最後のバイトの下位ビットが０を有すると仮定する。
８．５．２  型：ＬｉｎｋＣｈａｌｌｅｎｇｅＡｎｓｗｅｒ
この型は、Ｌｉｎｋｃｈａｌｌｅｎｇｅへの回答を表す。これは、Ｓｅｑｕｅｎｃｅ＜Ｕ８＞と同等の型を有し、これは、ＬｉｎｋＣｈａｌｌｅｎｇｅのＰｒｅＰａｒｔと組み合わされた時に正しいハッシュを作る残りのバイトである。
８．６  リンクパケット型
複数のリンクパケット型がある。リンクプロトコル１４は、インターフェースプロトコル１２の真上に存在するので、到着するすべてのインターフェースパケットが、リンクプロトコルパケットであると仮定される。第１バイトによって、リンクパケットの型が決定される。各リンクパケット型の名前および関連する番号の例を、表２５に示す。
【０１１２】
【表２５】
2006517077.tif 000027
【０１１３】
８．７  初期リンクセットアッププロトコル
初期リンクセットアッププロトコルでは、チャレンジレスポンス機構を使用して、受信側ノードがリンクセットアップ文書をそれに転送させるように準備すると同時に、開始ノードにある計算作業を行うことを強制する。これには、リンク初期要求、リンク要求ＮＡＫ、リンク要求チャレンジ、リンクチャレンジレスポンス、リンク初期ＡＣＫ、リンク初期ＮＡＫを含む複数のＰＤＵの１つが用いられる可能性がある。
９．ルーティングプロトコル
９．１  概論
ルーティングプロトコル１８は、回路確立要求をその最終的な宛先のより近くに正しく移動するのに必要な情報をノードに与えるように設計されている。ルーティングプロトコル１８は、ノードが、さまざまなリンクのメトリックパラメータおよび回路要求の要件に基づいて、使用されるパスに関するインテリジェントな選択を行うことを可能にすることもできる。
【０１１４】
ルーティングプロトコル１８をスケーリングできるようにするために、ネットワークが、編成において階層的であると仮定する。各ノードは、ノード名を有し、ルーティングは、まず、ノード名の最も一般的な部分への回路要求を得、次に、ノードが最も一般的なネットワークに達する時に、ルーティング情報が、より具体的になり、ノード名の次の部分を検査できるようになる。この処理は、ノードがその最終的な宛先に達するまで継続される。
【０１１５】
ノードのネットワークを、集合的にメタノードと呼ぶ。２つの異なるメタノードのノードが、エッジを介して接続される場合に、この２つのメタノードは、メタエッジ（ｍｅｔａ−ｅｄｇｅ）を介して接続される。メタノードの間の複数のリンクを単一のメタエッジに組み合わせる機構がある。エッジおよびメタエッジの情報は、データを関係する区域に制限するルールを用いて、ネットワークにフラッディングされる。最上位メタエッジデータは、すべての場所にフラッディングされる。
【０１１６】
メタエッジデータは、特殊なメタノードコントローラノードによって生成される。これらのノードは、メタノード鍵ならびにそのノード鍵を有する。複数のメタノードコントローラがある場合があり、これらのすべてが同一の結果に達しなければならず、フラッディングレートが各ノードを介して制御されるので、追加のメタノードコントローラは、単に、過剰である場合に無視される余分な更新を送信する。
【０１１７】
メタノードコントローラを有しないことが可能であるが、これは、すべてのノードがメタノード鍵を含む（不良）ことを必要とするか、メタリンクデータのセキュリティがメタリンクの各メタノード内の１つのノードの署名だけを必要とすることを必要とし、これは、おそらく、許容可能であるが、メタノードコントローラ機構よりも危険にさらされやすい。というのは、これが、各メタノード内のコントローラの妥協を必要とするからである。
【０１１８】
さらに、メタノードコントローラ機構は、ルーティング計算の多くを多少集中化することを可能にすると同時に、完全な障害処理を可能にする。というのは、理論的に、任意の個数のメタノードコントローラを設けられるからである。
【０１１９】
スターネットワークは、説明している実施形態でメタノードに関連する。しかし、代替実施形態に、この関係を含めないことができる。さらに、説明している実施形態のスターネットワーク内のノードは、ローカルネットワークに関するネットワークルーティング情報を交換するのではなく、メタノードコントローラだけと通信して、接続性情報を交換する。
９．２  ルーティング状態
ルーティング情報を移動するのに使用されるプロトコルを説明する前に、ノードの状態ならびにメタノードコントローラを説明する。ノードは、任意のネットワークレベルのメタノードコントローラになることができ、多分同時に複数のレベルでメタノードコントローラになることができる。あるノードが、所与のレベルのメタノードコントローラである場合に、そのノードは、そのレベルの完全なルーティング情報を有する。そうでない場合に、ノードは、所与のレベルの部分的なルーティング情報を有する。すべてのノードが、ローカルネットワークセグメントに関する完全なルーティング情報を有する。
【０１２０】
部分的ルーティング情報は、実際には、完全なルーティング情報から導出される。部分的なルーティング情報は、回路要求を実際にルーティングするのに使用される唯一の情報である。下のテキストで、まず完全なルーティング情報の形を説明し、次に部分的なルーティング情報、次に完全な情報から部分的情報を生成するアルゴリズムを説明する。
９．２．１  完全なルーティング状態情報
完全なルーティング情報は、ネットワークの一部であるエッジまたはメタエッジのすべてと各エッジのメトリックパラメータ、ならびにネットワークの一部であるノードまたはメタノードのすべてとノード相互接続のメトリックパラメータからなる。この説明において、単語ノードおよびエッジは、おそらく、メタノードまたはメタエッジを意味することができる。
９．２．２  型：ＥｄｇｅＩｎｆｏｒｍａｔｉｏｎ
エッジ情報型は、単一のエッジに関する情報を有する。下の表２６に、エッジ情報の例のフォーマットを示す。
【０１２１】
【表２６】
2006517077.tif 000028
【０１２２】
表２６を参照すると、ＮｏｄｅＡおよびＮｏｄｅＢは、接続される２つのノードである。このノードの少なくとも１つが、完全なルーティング情報が保管されているネットワーク内にある。ＭｅｔｒｉｃＤａｔａに、このエッジによって追跡されるメトリックの最新の総空き値および現行空き値のすべてが含まれる。
９．２．３  型：ＮｏｄｅＩｎｆｏｒｍａｔｉｏｎ
ノード情報型は、単一のノードに関する情報を有する。下の表２７に、ノード情報の例のフォーマットを示す。
【０１２３】
【表２７】
2006517077.tif 000029
【０１２４】
表２７を参照すると、Ｎｏｄｅは、当のノードである。ＭｅｔｒｉｃＤａｔａは、このノードの内部容量および現在の空き容量を記述する。これは、メタノードにより関連する。というのは、メタノードのあるサイドから別のサイドにデータを移動する能力が制限される場合があるからである。容量は、最悪リンク間ケースに関して与えられる。すなわち、あるメタノードが、３つの他のメタノードＡ、Ｂ、およびＣに接続される場合に、これらの数は、ＡからＢ、ＢからＣ、およびＡからＣにデータを移動するメタノードの能力のワーストケースである。
９．２．４  型：ＦｕｌｌＲｏｕｔｅＴａｂｌｅ
フルルートテーブルに、所与のネットワークの所与のレベルの完全なルーティングデータが含まれる。フルルートテーブルのフォーマットの例を、下の表２８に示す。
【０１２５】
【表２８】
2006517077.tif 000030
【０１２６】
表２８を参照すると、Ｅｄｇｅｓは、ネットワーク内のすべてのエッジに関するすべてのエッジ情報のセットであり、Ｎｏｄｅｓは、ネットワーク内のすべてのノードに関するすべてのノード情報のセットである。
９．２．５  部分的なルーティング状態の概論
部分的なルーティング状態は、ネットワーク内の所与の視点に固有の計算された次ホップルーティング情報である。最終的な宛先（ルーティングされるネットワークの解決に対する）を与えられれば、現在位置と、次ホップ可能性のそれぞれの総パスメトリックに関するメトリック情報から、１ホップの宛先のリストがもたらされる。さらに、メタルーティングデータの場合に、すべての隣メタノード、隣メタノードへの接続を有する１レベル下位のエッジノード、およびその特定の下位エッジのメトリックデータを与えるもう１つのテーブルがある。
９．２．６  型：ＮｅｘｔＨｏｐＥｎｔｒｙ
次ホップエントリは、ある最終的な宛先に達する特定の可能な次ホップと、関連する完全パスの計算されたメトリック情報である。
９．２．７  型：ＩｎｔｅｒｃｏｎｎｅｃｔｉｏｎＥｎｔｒｙ
相互接続エントリには、２つのメタノードの間のメタエッジとして働く下位ノードまたは下位メタノードに関する情報、ならびにそれらのメタノードを接続する実際のエッジの関連するメトリックデータが含まれる。
９．２．８  型：ＰａｒｔｉａｌＲｏｕｔｅＴａｂｌｅ
部分的ルートテーブルには、所与のネットワークの所与のレベルの部分的なルーティングデータが含まれる。部分的ルートテーブルの構造の例を、表２９に示す。
【０１２７】
【表２９】
2006517077.tif 000031
【０１２８】
表２９を参照すると、ＮｅｘｔＨｏｐｓは、計算された次ホップ情報のすべてのセットである。このセットが、ＮｅｘｔＨｏｐＥｎｔｒｙ構造のＦｉｎａｌＤｅｓｔｉｎａｔｉｏｎ変数によってインデクシングされると仮定する。同一の最終的な宛先につながる複数のエントリがある場合がある。同様に、Ｉｎｔｅｒｃｏｎｎｅｃｔｓ変数は、ＩｎｔｅｒｃｏｎｎｅｃｔｉｏｎＥｎｔｒｙ型のＮｅｉｇｈｂｏｒＭｅｔａＮｏｄｅ変数によってインデクシングされ、やはり、複数のエントリがある場合がある。
９．２．９  変換アルゴリズム
変換アルゴリズムは、完全なルートを部分的ルートに変換する責任を負う。これを行うために、並列および直列の配置ＱＯＳメトリックを組み合わせる方法が必要である。各ＱＯＳメトリックは、並列組合せアルゴリズム（点の間の２つの並列ルートのＱＯＳに基づく２つの点の間の総ＱＯＳ）ならびに直列組合せアルゴリズム（最初の点から中間点までのＱＯＳと、中間点から最後の点までのＱＯＳに基づく２点間の総ＱＯＳ）を有する。たとえば、帯域幅に関する並列アルゴリズムは、２つの帯域幅の和であり、直列アルゴリズムは、２つの帯域幅の最小値である。
【０１２９】
変換アルゴリズムは、最終的な宛先ノードごとに、次ホップごとに、その次ホップを介する最終的なノードへのすべてのパスを判定する。変換アルゴリズムは、ＱＯＳ組合せ機構を使用して、ＱＯＳの非循環グラフを単一のＱＯＳ値に変換し、これを次ホップに関連付ける。
９．３  データ移動の概論
ルーティングプロトコル１８への４つの基本的な部分がある。第１は、メタノードのすべてのノードがノードコントローラについて知るようにする、メタノードコントローラフラッディングプロトコルである。第２は、二重署名プロトコルである。これは、エッジまたはメタエッジの半分が、部分的に署名されたエッジを、検査および連署のために他方に送信する方法である。第３は、エッジ、メタエッジ、ノード、およびメタノードのデータが、知る必要があるすべてのものにフラッディングされる、ベースデータフラッディングプロトコルである。第４は、ベースデータを使用して計算した後に、メタデータコントローラノードが計算された部分的データをローカルネットワークにフラッディングする方法である。
【０１３０】
ノードによって交換されるすべてのルーティングパケットが、言い分によって実際にはパケットでなく、リンクの信頼できる部分を介して送信される文書である。上で述べたように、これらの文書のほとんど（連署要求を除く）が、フラッディングによって転送される。フラッディングは、ネットワーク上の知る必要があるすべてのものにデータをブロードキャストする処理である。
【０１３１】
フラッディング機構は、次のように働く：各ノードは、その隣から文書を受信した時に、その文書がそのノードに関連するかどうかを検査する。そうでない場合に、その文書を無視する。次に、そのノードは、同一の文書を最近に見たかどうかを検査する。これは、前文書テーブルを介して行われる。テーブルへのオーバーフローを防ぐために、ノードが、所与の時間のうちにあまりに多くの文書を隣から受信する場合に、そのノードは、時折パケットを捨てる。いずれにせよ、ノードは、前にその文書を見たことがある場合に、その文書を捨てる。その文書が、新規の関連する文書である場合に、ノードは、署名を検査する。署名が不正である場合に、ノードは、それが受信された隣からの許容データレートを下げる。というのは、隣が、不良文書を送信してはならず、その隣が、危険にさらされている可能性があるからである。すべてがよい場合に、ノードは、どの隣がその文書に関連するかを検査し、関連する可能性があるすべてのものにその文書を送信する。
９．４  コントローラフラッドプロトコル
９．４．１  型：ＣｏｎｔｒｏｌｌｅｒＦｌｏｏｄＢｏｄｙ
コントローラアラートプロトコルは、ノードが、メタノードコントローラについて知るようにする。関連性判断基準は、ノードが、コントローラがそれのためのメタノードコントローラであるメタノードに属するか否かである。制御アラート文書本体に、コントローラがそれのためのコントローラであるメタノードのネットワークネットワーク名と、コントローラノードのフルノード名を含めることができる。明らかに、Ｃｏｎｔｒｏｌｌｅｒは、ＭｅｔａＮｏｄｅのより特定のドット名である。この文書は、当のメタノードのメタノード鍵によって署名される。所与のノードは、それが属するメタノードの各レベルの少なくとも少数のコントローラを記憶する。所与のノードは、ホップカウントに基づいて、最も近いコントローラを保持し、より遠いコントローラを捨てる。
９．５  連署プロトコル
９．５．１  型：ＣｏｓｉｇｎＲｅｑｕｅｓｔＢｏｄｙ
連署プロトコルは、他の当事者にエッジ更新を署名させるのに使用される。これには、ＣｏｓｉｇｎＲｅｑｕｅｓｔ文書と称する文書の転送が用いられる。これには、一方のノードから他方のノードに送信される、連署されるエッジ情報が含まれる。これは、ＥｄｇｅＩｎｆｏのＮｏｄｅＡパラメータによって署名される。
【０１３２】
連署要求文書は、ＥｄｇｅＩｎｆｏエントリのＮｏｄｅＢ部分で名前を指定された、ネットワークのより近いところに向けられる。要求が、名前を指定されたネットワークに既に入っている場合に、ノードは、コントローラに関する情報を使用して、この文書を最も近い既知のコントローラの近くに送信する。
９．６  ベースフラッディング
９．６．１  型：ＮｏｄｅＦｌｏｏｄＢｏｄｙ
フラッド本体ノードは、その第１要素を除去されたノードの名前が現在のノードのノード名の一般化である場合に関連する、ＮｏｄｅＩｎｆｏで記述されたノードまたはメタノードによって署名される。
９．６．２  型：ＥｄｇｅＦｌｏｏｄＢｏｄｙ
フラッド本体エッジは、その第１要素を除去されたいずれかのノード名が現在のノードのノード名の一般化である場合に関連する、ＥｄｇｅＩｎｆｏに記述された両方のノードまたはメタノードによって署名される。
９．７  計算されたフラッディング
９．７．１  型：ＮｅｘｔＨｏｐＦｌｏｏｄＢｏｄｙ
フラッド本体次ホップは、署名するメタノードが現在のノードのメタノードである場合に関連する、それが記述するネットワーク層のメタノードによって署名される。
９．７．２  型：ＩｎｔｅｒｃｏｎｎｅｃｔｉｏｎＦｌｏｏｄＢｏｄｙ
フラッド本体相互接続は、署名するメタノードが現在のノードのメタノードである場合に関連する、それが記述するネットワーク層のメタノードによって署名される。
１０．回路プロトコル
この章では、回路の構成および回路を介するデータの移動に使用されるプロトコルを定義する。この章は、回路状態テーブルの定義から始まり、この回路状態テーブルは、回路データ移動によって使用され、回路確立処理によって変更される。
１０．１  回路ルーティングテーブル
回路ルーティングテーブルには、ノードを通る現在の回路が保管される。各回路は、あるインターフェースのリモートノードを、多分別のインターフェースのリモートノードに接続する。任意の２つのノードの間に複数の回路がある場合があるので、これらを区別するのに使用されるＣｉｒｃｕｉｔＩＤがある。このＣｉｒｃｕｉｔＩＤは、２つのノードにローカルである、すなわち、２つのノードの間の複数の回路を分離することだけに使用される。
１０．１．１  型：ＣｉｒｃｕｉｔＩＤ
回路ＩＤ識別子を用いると、同一のノードの間の複数の回路の分離が可能になる。
【０１３３】
ルートテーブルに、回路の２つのサイドの間の関係が保管され、多分ＱＯＳアカウンティングおよび制御に関する内部データが保管される。回路サイド型は、回路の１つのサイドを表し、ＲｅｍｏｔｅＩｎｔｅｒｆａｃｅは、回路のこのサイドが出てゆく特定のインターフェースを表し、ＲｅｍｏｔｅＮｏｄｅは、他方のノードのインターフェース固有ＲｅｍｏｔｅＡｄｄｒｅｓｓである。ＩＤは、ノード間接続に関する回路ＩＤに対応する。
【０１３４】
「Ｌｏｃａｌ」と称する特殊なインターフェースがある。これは、回路の１サイドがローカルである場合に使用されるインターフェースである。
１０．１．３  型：ＣｉｒｃｕｉｔＬｉｎｋ
回路リンクは、２つの回路端の間の関係を、ＱＯＳを管理する実装固有データなどと共に定義する。回路リンクは、通信する２つのサイドと、余分の実装固有データを有することができる。
１０．１．４  型：ＣｉｒｃｕｉｔＲｏｕｔｅＴａｂｌｅ
回路ルートテーブルは、オープン回路の現行セットである、回路リンクのセットである。
１０．２  回路データプロトコル
前のセクションで述べたように、回路データプロトコル２２は、信頼されないリンクプロトコル１４の上にある唯一のプロトコルである。そのフレーミングは、信頼されないリンクのデータセクションで即座に開始される。回路データプロトコル２２は、基本的に、回路のＣｉｒｃｕｉｔＩＤと、それに続く、回路を介して送信される実際のデータからなる。公式の定義に、回路ＩＤとバイトシーケンスが含まれる。
【０１３５】
パケットの受信時に、回路が、ＩＤおよび着信アドレスによってルックアップされて、回路ルートテーブル内のエントリが見つけられる。そのようなエントリがない場合には、パケットは、静かに捨てられる。エントリがある場合に、パケットは、エントリのもう１つのサイドにリダイレクトされる、すなわち、パケットがＳｉｄｅＡを介して到着した場合にＳｉｄｅＢに送られ、ＳｉｄｅＢに到着した場合にＳｉｄｅＡに送られる。このパケットは、非ローカルのインターフェースの場合には信頼されないリンクプロトコル１４を介して送られ、あるいは、インターフェースが特殊なローカルインターフェースである場合に、ユーザに送られる。
【０１３６】
所与の時に回路を介してデータが移動しない場合に、ノードは、回路ルートテーブル内のエントリを捨てる。キープアライブを、空（０データ長）パケットを送信することによって送信することができる。これらは、ユーザに配送されない。
１０．３  確立プロトコル
確立プロトコル２０は、回路のセットアップに使用される。確立プロトコル２０では、ネットワークを介し、信頼できるリンクプロトコル１４を介する回路要求文書の移動が用いられる。回路要求が移動する時に、これによって回路が確立される。他のサイドに達した時に、データを両方向で送信することができる。受信サイドが、送るべき最初のデータを有しない場合に、受信サイドは、キープアライブを送信して、回路を両方向で検証する。
１０．３．１  型：ＣｉｒｃｕｉｔＲｅｑｕｅｓｔＢｏｄｙ
回路要求本体に、実際の回路要求が含まれる。これは、回路の確立を要求するユーザによって署名され、回路の最終的な宛先である宛先ノードと、他方のサイドで望まれるサービスの名前であるサービス名（ポート番号に類似し、実装固有である）と、回路のＱＯＳ要件および他のメトリック要件である要件と、回路のフラグであるフラグ（たとえば、定義されているのは、暗号化のビット０（最下位ビット）および信頼性のビット１（最下位から２番目）である）と、暗号化のフラグがセットされている場合に限ってこの構造の一部になる回路鍵とが含まれる。暗号化のフラグがセットされている場合に、回路鍵は、受信側に対して公開鍵暗号化された対称暗号鍵である。
【０１３７】
信頼できるリンクで要求文書にすぐに続くのが、前のホップからの符号なし部分的メトリックデータを最後のホップからのＣｉｒｃｕｉｔＩＤと共に表す構造である。たとえば、最大所望帯域幅は、前のホップが理論的にオリジナル帯域幅をサポートできない場合により低くなる可能性があり、必要な待ち時間が、既に使用されている待ち時間に基づいてより少なくなる可能性がある。
１０．４  暗号化および信頼性
暗号化層および信頼性層は、回路パケットに追加ヘッダを追加する。暗号化は、信頼性の前に来る。
１１．文書転送プロトコル
文書転送プロトコル２８は、その名前および型に基づいて文書を取り出すのに使用される機構である。使用される機構は、ＤＮＳに似ている。ＤＴＰは、回路を介して実行され、そのサービス名は、単に「ＤＴＰ」である。ＤＴＰは、回路プロトコル（２０および２２）上の信頼性プロトコル１６を使用して、信頼性のあるストリームサービスを提供する。ＤＴＰは、暗号化されてまたは暗号化されずに動作することができるが、要求された接続をＤＴＰが受け入れることは、ＤＴＰサーバの判断である。
【０１３８】
ＤＴＰリンクを介して、文書要求が送信され、文書が返される。リダイレクション処理があり、これが、ユーザが別のＤＴＰサーバにポイントされることを引き起こす。その代わりに、主ＤＴＰサーバが、追加のルックアップ自体を再帰的に実行し、結果を直接に返すこともできる。この判断は、実装者に委ねられ、ユーザ要求、発信ノードなどに基づくものとすることができる。
【０１３９】
文書要求の例を、表３０に示す。
【０１４０】
【表３０】
2006517077.tif 000032
【０１４１】
文書要求は、上で示したように信頼できるリンクを介して到着する。ＤＴＰサーバは、現在の文書の値を知っている場合に、それを返し、これは、単に、信頼できるリンクを介して文書を送信することを意味する。
【０１４２】
そうでない場合に、リダイレクトに使用できる２つの特殊な型の文書がある。第１は、論理名文書である。
１１．０．１  型：ＬｏｇｉｃａｌＮａｍｅＢｏｄｙ
論理名文書は、異なる鍵を有する同一の型の別の文書に文書をリダイレクトする（たとえば、その鍵および本体に記載された型）。論理名文書は、その鍵と同一のまたはより一般的なアイデンティティによって署名される。
【０１４３】
注：ほとんどの文書と異なって、異なる型の文書をリダイレクトする限り、同一の鍵を有する複数のリダイレクション文書がありえる。
他方の、より重要なリダイレクションの機構が、文書位置機構である。文書位置機構は、ドットパスツリーのある部分をあるＤＴＰサーバに関係させることを可能にする。サーバがその文書を知らない場合に、そのサーバは、知っているサーバにリダイレクトすることができる。最悪でも、ルートＤＴＰサーバは、サブツリーのより一般的な部分に関する権威がある計算機のアイデンティティを知っている。サブツリーノードのそれぞれが、文書が解決されるまで、その文書を知っているか別のより具体的なソースを知っている。
１１．０．２  型：ＤｏｃｕｍｅｎｔＬｏｃａｔｉｏｎＢｏｄｙ
これは、文書サーバへのドットパスツリーの所与の部分に関するポインタである。ルックアップするレコードより一般的な複数のレコードがある場合に、最も具体的なレコードが使用される。すべてのＤＴＰサーバが、１つまたは複数のルートサーバの位置を有する。所与のサブツリーに関する権威があるすべてのサーバが、その中にすべての文書を有し、あるいは、それに関する完全なデータを保持していない、サブツリーのすべてのサブツリーに関するより具体的な位置文書を有する。
【０１４４】
文書位置文書のキーは、サービスされるサブツリーである。この文書は、そのキーと同一またはより一般的なアイデンティティによって署名される。同一のキーに関する複数の文書位置文書が存在することもできる。というのは、複数の冗長な完全に権威があるサーバがありえるからである。
１２．オプションの拡張
１２．１  マルチキャスト拡張
この拡張は、単一のノードがデータの同一のストリームを複数のノードに効率的な形でブロードキャストできるようにするのに使用される。これを可能にするために、回路のフォーマットが、マルチキャスト回路用にわずかに変更される（普通の回路と別々のテーブルに保持される）。各ノードで、回路は、単一のＣｉｒｃｕｉｔＳｉｄｅを別の単一のＣｉｒｃｕｉｔＳｉｄｅに接続するのではなく、ある「ルート」サイドを１つまたは複数の「枝」サイドに接続する。
【０１４５】
さらに、送信側ノードに一意であり、組合せのためにマルチキャストフローをキーイングするために送信側ノードと共に使用されるＣｈａｎｎｅｌがある。
１２．１．１  データフロー
回路データは、ルートサイドで受信された時に、複製され、枝サイドのそれぞれに送信される。実際のデータは、逆方向（枝からルート）に流れないが、回路をオープン状態に保つための空のキープアライブがある場合がある。キープアライブは、枝を介して受信された時に、回路タイムアウト値の半分の間にその枝からのキープアライブがなかった場合にはルートに転送され、そうでない場合には捨てられる。あるノードが、タイムアウト時間の間に所与の枝からキープアライブを受信していない時に、そのノードは、その枝を捨てる。枝がなくなった場合には、マルチキャストテーブルのエントリを除去する。
１２．１．２  回路確立
マルチキャスト回路は、ルートから外にルーティングされる。したがって、あるノードが、マルチキャストに参加することを望む場合に、そのノードは、マルチキャストに参加することを要求するマルチキャスト事前要求文書（下で定義する）をマルチキャスト送信元に送信する。これが行われたならば、またはマルチキャスト送信側が開始する場合に、マルチキャスト送信側は、マルチキャスト要求文書を送信し、これが外向きに移動する。これは、次の２つの例外を除いて、回路要求と同様にルーティングされる。
【０１４６】
１．同一の初期送信側から同一のサイドを介してマルチキャスト要求を受信した時に、新しい回路ではなく、枝が、宛先に向かって作られる。
２．既存の枝と同一のパスに向かってデータを送ることに対する追加のルーティングプリファレンスを設けることができる。
１２．１．３  型：ＭｕｌｔｉｃａｓｔＰｒｅＲｅｑｕｅｓｔＢｏｄｙ
マルチキャスト事前要求本体文書は、外に向かう方向での回路確立を行うことを要求するために、非送信側に送信される。これは、ＳｅｎｄｉｎｇＮｏｄｅに向かって転送され、要求するユーザによって署名される。この文書に関連する構造の例を、表３１に示す。
【０１４７】
【表３１】
2006517077.tif 000033
【０１４８】
表３１を参照すると、ＤｅｓｔｉｎａｔｉｏｎＮｏｄｅは、回路の最終的な宛先である。
ＳｅｎｄｉｎｇＮｏｄｅは、マルチキャストを行うノードであり、この事前要求の宛先である。Ｃｈａｎｎｅｌは、他のサイドで望まれるチャネルの名前である。
【０１４９】
Ｒｅｑｕｉｒｅｍｅｎｔｓは、回路のＱＯＳ要件および他のメトリック要件である。Ｆｌａｇｓは、回路のフラグであり、現在定義されているのは、暗号化のビット０（最下位ビット）である。ＣｉｒｃｕｉｔＫｅｙは、暗号化のフラグがセットされている場合にのみこの構造の一部になる。そうである場合に、ＣｉｒｃｕｉｔＫｅｙは、受信側に対して公開鍵暗号化された対称暗号鍵である。
１２．１．４  型：ＭｕｌｔｉｃａｓｔＲｅｑｕｅｓｔＢｏｄｙ
マルチキャスト要求本体は、送信側を介して送信されて、回路を確立する。送信側ノードによって署名される。この要求に頭文字を付けるために送信されたものまたは送信側によって作られたもののいずれかのＰｒｅＲｅｑｕｅｓｔが続く。
１２．１．５  破壊
枝の１つから回路終了要求を受信した時に、その回路終了要求が転送され、１つの枝だけがある場合には回路が破壊される。複数の枝がある場合に、当の枝が単純に除去される。ルートからの回路終了要求は、すべての枝に転送され、回路が除去される。
１２．２  自動分割
自動分割は、より大きいメタノードをさまざまなより小さいメタノードに分割できる処理である。これは、大きいネットワークに有用である。この機構を達成するために、「論理」メタノードと称する、新しい型のメタノードを作る。これは、帯域外鍵交換によって確立される標準的な「管理」メタノードと異なる。論理メタノードは、論理メタノード内の複数のノードから権限を得る。これには、申請（ｐｅｔｉｔｉｏｎ）文書と称する新しい文書が用いられ、申請文書は、論理メタノードを確立し、論理メタノードがその一部である同一の管理メタノードの多数のメンバによって署名される。さらに、これらの同一のノード（署名者）は、論理メタノード鍵によって署名された新しいアイデンティティを与えられる。
【０１５０】
これによって、論理ネットワークコントローラの作成が可能になるが、論理ネットワークコントローラは、そのピアによって上記に従ってその鍵に署名されることによってネットワークコントローラ状況に昇格したノードである。この論理ネットワークコントローラは、非効率的になる可能性があるが、破壊的ではない。その理由は、ネットワークコントローラの２つの目的すなわちルートの集約およびメタノード間リンクへの署名の両方を、外部で検証できることである。ルート集約の場合に、各ノードは、それ自体でルート集約を行うことができ、時々それを行って、現在の論理ネットワークコントローラを検査し、将来のＮＣのさらなるサポートを拒否する（現在の署名をタイムアウトさせる）ことができる。メタノード間接続性に関する情報は、メタノードリンクの他方のサイドが連署しない限り伝搬されず、これは、結果が不正の場合に行われない。
【０１５１】
ノードが、論理ＮＣが不正に振る舞っていると判定する場合に、ノードは、別のＮＣを作成することができる。メタノード内に少なくもも１つの機能するＮＣがある限り、すべてが正しく働かなければならず、誤動作している（または悪意のある）ＮＣは影響しない。
【０１５２】
分割の実際のステップに、（１）ノード（最下レベル）から直接に構成される管理メタノードまたは論理メタノードを、主メタノードを形成する複数のより小さいメタノードにすること（レベリング）と、（２）現在の論理メタノードを複数の論理メタノードに分割すること（分割）が含まれる。
【０１５３】
この両方の事例で、ＮＣは、分割が望ましいと判断する。第１の事例で、そのＮＣは、上位ＮＣであり、第２の事例で、副分割を行うＮＣである。これには、分割要求メッセージが用いられる。このメッセージ（ＮＣによって署名された文書）は、最も近い管理ＮＣ（現在のＮＣが論理ＮＣである場合）に連署のために送信され、次に、メタノードを介してフラッディングされ、そのメタノードに現在含まれるノードの再割り当てに関する情報（どのノードをどのサブグループに再割り当てするか）と、各サブグループの提案されるＮＣの管理名、ならびにネットワーク名が含まれる。分割要求は、分割が行われる時刻を指定する。ノードが複数の分割要求を受信する場合に、最も早く行われるものが選択され、正確に同一の時刻は、送信側ＮＣのノード名の辞書順で曖昧さを解消される。
【０１５４】
分割を行うようにセットする前に、ノードは、新しい論理ＮＣ申請文書に署名すると同時に、論理ＮＣから新しいアイデンティティキーを受け取る。これらのキーは、ノードの慣例的に割り当てられたローカル部分であり、新しいネットワークフルネームが続き、ＮＣの申請鍵によって署名される。
【０１５５】
この処理の例は、次の通りである。
１．分割するメタノードのネットワークコントロールが、最も近い管理ネットワークコントローラ（それが最も近いＡＮＣでない限り）に分割要求を直接に送信する。
【０１５６】
２．ＡＮＣが、要求に連署し、フラッディングする。
３．新たに選択されたＬＮＣならびにそれを望む保証されないノードが、ノードの公開鍵を含む「ネットワークコントローラ申請」メッセージを、関係するすべてのノードに送信する。
【０１５７】
４．各ノードが、１つまたは複数の候補を選択し、申請に署名する。
５．署名を受信した時に、当のメタノードが、その申請鍵を用いてノードの新しいアイデンティティに署名し、当のノードに返す。
【０１５８】
６．最小の必要な投票を受信した時に、候補ノードが、それが署名した申請を最も近いＡＮＣに送信する。
７．ＡＮＣが、新たに指定された候補のＬＮＣ鍵に署名し、送り返す。
【０１５９】
８．新しいＬＮＣが、その署名されたＬＮＣ鍵文書をローカルネットワークにフラッディングし、論理ノードコントローラになる。
９．ノードの候補のどれもが、選挙の終り（分割の開始）が行われるようにセットされた時刻までに十分に高い投票カウントを達成しない場合に、ノードは、十分に高い投票カウントを有する候補の１つまたは複数を選択し、その申請に署名し、それからアイデンティティを受け取る。
【０１６０】
１０．候補のどれもが、指定された時刻の前に最小の必要な投票を達成しない場合に、分割は取り消される。
１２．２．１  分割選択機能
分割を最初に決断したネットワークコントロールは、分割の編成（どのノードがどちらのサイドになるかという意味で）を判断する任意の方法を選択することができるが、これは、要件および／最適化判断基準によって制限される可能性がある。たとえば、各サブグループは、内部で完全に接続されることができる、すなわち、サブグループの各メンバが、そのサブグループから出ないですべての他のメンバに達することができる。さらに、あるブレークダウンをより望ましくする複数の判断基準がある場合がある。
【０１６１】
よいブレークダウンを見つけるために、シミュレーテッドアニーリングの変更された方法を提案する。第１に、各可能なブレークダウンに値を与える適応度を選択する。その例は、次の通りである。
【０１６２】
ｗ１（Ｎａ−Ｎｂ）２＋ｗ２（Ａｖｇ（Ｂａｎｄｗｉｄｔｈ（ｘ）：∈Ｉｎｔｅｒ）／Ａｖｇ（Ｂａｎｄｗｉｄｔｈ（ｘ）：ｘ∈Ｉｎｔｒａ）
ここで、集合Ｉｎｔｅｒは、グループ間接続の集合であり、Ｉｎｔｒａは、グループ内接続の集合であり、Ｂａｎｄｗｉｄｔｈ（Ｘ）は、帯域幅を測定する関数であり、ｗ１およびｗ２は、重みであり、ＮａおよびＮｂは、各サブグループのノード数である。目標は、この適応度関数の値を最小にすることである。この関数は、０（最善）と１（最悪）間の値に正規化される。
【０１６３】
アニーリング方法の例は、次の通りである。
１．オリジナルグループのエッジのランダムに選択された１つのノードがサブグループＢに置かれることを除いて、すべてのノードを、まずサブグループＡに置く。
【０１６４】
２．温度Ｔを１に初期化する。
３．ランダムエッジノード（サブグループのエッジにあるノード）を、評価のために選択する。
【０１６５】
４．グループＡからＢに切り替えられた時に、エッジノードが、結果のブレークダウンを正当な状態にする（各グループが内部で完全に接続され、各グループに少なくとも１つのエッジがある）場合に、Ｆｏｒｉｇと称するオリジナルの適応度を評価し、選択されたノードが切り替えられたネットワークの適応度Ｆｎｅｗも評価する。
【０１６６】
５．ノードを、確率
【０１６７】
【数１】
2006517077.tif 000034
【０１６８】
で切り替える。
６．連続して低下する温度を用いてステップ３から５を繰り返す。
７．最終的な温度を０で固定し、システムが安定するまで、すべてのエッジノードを評価する。
１２．２．２  分割文書の詳細
１２．２．３  型：ＳｐｌｉｔＲｅｑｕｅｓｔＢｏｄｙ
分割要求本体文書は、ネットワークの分割を求めるＮＣを介して、その制御の下で送信される。これは、必要な場合にＡＮＣへのトリップについてＮＣによって署名され、フラッディングされる前にＡＮＣによって連署される。この文書の構造の例を、下の表３２に示す。
【０１６９】
【表３２】
2006517077.tif 000035
【０１７０】
１２．２．４  型：ＣｏｎｔｒｏｌｌｅｒＰｅｔｉｔｉｏｎＢｏｄｙ
コントローラ申請本体文書は、分割（この文書に従う）に関する所与のノードの立候補を表す。この文書は、候補によって署名され、候補が十分な投票を受け取ったならば、ＡＮＣに送信される（署名として必要な個数の投票と共に）。また、この文書は、単一のノードによる投票を表すためにそのノードによって署名されて送信される。この文書の構造の例を、下の表３３に示す。
【０１７１】
【表３３】
2006517077.tif 000036
【０１７２】
１２．２．５  型：ＬｏｇｉｃａｌＫｅｙＡｓｓｉｇｎｍｅｎｔ
論理鍵割当文書は、候補によって、その候補に投票したノードに送信される、その論理鍵によって署名された文書である。この文書の構造の例を、下の表３４に示す。
【０１７３】
【表３４】
2006517077.tif 000037
【０１７４】
１２．２．６  型：ＬｏｇｉｃａｌＮｅｔｗｏｒｋＣｏｎｔｒｏｌＡｕｔｈｏｒｉｚａｔｉｏｎ
論理ネットワークコントロール許可文書は、ＡＮＣが正しい数のノードによって署名されたコントローラ申請を与えられたならば、そのＡＮＣによって送信される。この文書の構造の例を、下の表３５に示す。
【０１７５】
【表３５】
2006517077.tif 000038
【０１７６】
結論
本発明の実施形態の上の詳細な説明は、網羅的であることまたは本発明を上で開示された正確な形態に制限することを意図されたものではない。本発明の特定の実施形態および本発明の例を、例示のために上で説明したが、当業者が理解するように、さまざまな同等の修正形態が、本発明の範囲内で可能である。たとえば、ステップまたはコンポーネントを、所与の順序で提示したが、代替実施形態は、異なる順序のステップまたはコンポーネントを有するルーチンを実行することができる。本明細書で提供される本発明の教示は、必ずしも本明細書に記載のネットワークモデルではない他のシステムに適用することができる。上で説明したさまざまな実施形態の要素および動作を組み合わせて、さらなる実施形態を提供することができ、一部のステップまたはコンポーネントを、削除し、移動し、追加し、副分割し、組み合わせ、かつ／または変更することができる。これらのステップのそれぞれを、さまざまな異なる形で実施することができる。また、これらのステップを、直列に実行されるものとして示したが、これらのステップを、その代わりに、並列に実行することができ、あるいは、異なる時に実行することができる。
【０１７７】
文脈が他の形であることを明確に要求しない限り、この説明および請求項の全体を通じて、単語「ｃｏｍｐｒｉｓｅ」、「ｃｏｍｐｒｉｓｉｎｇ」、および類似物は、排他的または網羅的な意味ではなく、包含的な意味ですなわち「ｉｎｃｌｕｄｉｎｇ，  ｂｕｔ  ｎｏｔ  ｌｉｍｉｔｅｄ  ｔｏ」の意味で解釈されなければならない。単数形または複数形を使用した上の詳細な説明の単語も、それぞれ、複数または単数を含むことができる。さらに、単語「ｈｅｒｅｉｎ」、「ａｂｏｖｅ」、「ｂｅｌｏｗ」、および類似する趣旨の単語は、本明細書で使用される時に、本明細書の全体を指し、本明細書の特定の部分を指さない。請求項は、複数の項目のリストを指すのに単語「ｏｒ」を使用するが、この単語は、リスト内の項目のどれか、リスト内の項目のすべて、およびリスト内の項目の任意の組合せというこの単語の解釈のすべてを含む。
【０１７８】
本明細書で提供される本発明の教示は、必ずしも本明細書に記載されたシステムではない他のシステムに適用することができる。これらおよび他の変更は、この詳細な説明に鑑みて本発明に対して行うことができる。上で説明したさまざまな実施形態の要素および動作を組み合わせて、さらなる実施形態を提供することができる。
【０１７９】
添付閉じこみ書類にリストされたものを含む、上の特許、特許出願、および他の参考文献のすべてが、参照によって本明細書に組み込まれる。必要な場合に、本発明の諸態様を変更して、上に記載のさまざまな参考文献のシステム、機能、および概念を使用して、本発明のさらなる実施形態を提供することができる。
【０１８０】
上記および他の変更は、上の詳細な説明に鑑みて本発明に対して行うことができる。上の説明は、本発明のある実施形態を詳細に示し、企図された最善の態様を説明するが、上がテキストにおいてどれほど詳細に見えても、本発明を多数の形で実行することができる。ネットワークモデルの詳細およびその実施形態は、その実装詳細においてかなり変更することができると同時に、本明細書で開示される発明に含まれる。上で注記したように、本発明のある特徴または態様を説明する時に使用された特定の用語は、その用語が関連する本発明の特定の特性、特徴、または態様に制限されるように本明細書で再定義されていることを暗示すると解釈してはならない。一般に、請求項で使用される用語は、上の詳細な説明セクションでそのような用語が明示的に定義されていない限り、本明細書で開示される特定の実施形態に本発明を制限するものと解釈してはならない。したがって、本発明の実際の範囲は、開示された実施形態だけではなく、請求項の下で本発明を実践または実施するすべての同等な形をも含む。
【０１８１】
本発明のある態様を、請求項の形で提示するが、本発明人は、任意の個数の請求項の形で本発明のさまざまな態様を企図している。たとえば、本発明の１つの態様だけが、コンピュータ可読媒体で実施されるものとして記載されているが、他の態様を、同様にコンピュータ可読媒体で実施することができる。したがって、本発明人は、本発明の他の態様に関するそのような追加請求項を追求するために、本願の出願後に追加請求項を追加する権利を留保する。
【図面の簡単な説明】
【０１８２】
【図１】図１は本発明一実施形態のスタック編成を示す図。
【図１】
2006517077.tif 000039
【手続補正書】
【提出日】平成17年9月27日(2005.9.27)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
前記コンピューティングデバイスが期待されるサービス品質でネットワークリソースを安全に共用し、通信するようにするために、集中管理なしで、信頼しないコンピューティングデバイスのネットワークを編成するシステムであって、
受信側コンピューティングデバイスと、
回路確立要求を送信して、これにより、中央管理コンピューティングデバイスに相談せずに前記送信側コンピューティングデバイスから前記受信側コンピューティングデバイスへの中間コンピューティングデバイスの組を介するルートが動的に計算されるように、前記送信側コンピューティングデバイスと前記受信側コンピューティングデバイスとの間に通信回路を確立させる送信側コンピューティングデバイスであって、前記回路確立要求は、中間コンピューティングデバイスの前記組の各コンピューティングデバイスによって実施される所望のサービス品質の表示を有する、該送信側コンピューティングデバイスと
を含むシステム。
【請求項２】
前記送信側コンピューティングデバイスは、階層動的ルーティングプロトコルを使用して、前記受信側コンピューティングデバイスにパケットを送信する、請求項１に記載のシステム。
【請求項３】
前記動的ルーティングプロトコルは、各中間コンピューティングデバイスにサービス品質情報を伝搬させる、請求項２に記載のシステム。
【請求項４】
前記階層動的ルーティングプロトコルは、通信を暗号化するために暗号方法を使用する、請求項２に記載のシステム。
【請求項５】
前記送信するコンピューティングデバイスは、前記中間コンピューティングデバイスによって判断を行うのに使用される文書を送信する、請求項２に記載のシステム。
【請求項６】
前記文書は、サービス品質を記述する、請求項５に記載のシステム。
【請求項７】
前記文書は、さらに、前記ネットワークの使用に関する権利および権利の委任を記述する、請求項６に記載のシステム。
【請求項８】
前記文書は、許可の委任を記述する、請求項５に記載のシステム。
【請求項９】
前記許可の前記委任は、コンピューティングデバイスがデータ移動判断を行うことを可能にする、請求項８に記載のシステム。
【請求項１０】
前記階層動的ルーティングプロトコルは、信頼性のある基礎になる通信プロトコルまたは信頼性のない基礎になる通信プロトコルのいずれかを使用することができる、請求項２に記載のシステム。
【請求項１１】
前記ネットワークは、階層メッシュネットワークとして編成される、請求項１に記載のシステム。
【請求項１２】
前記階層メッシュネットワークの各コンピューティングデバイスは、セパレータによって分離された識別子の組を含む名前によって識別される、請求項１１に記載のシステム。
【請求項１３】
前記識別子は、前記名前内で特定なものから全般的なものへと編成される、請求項１２に記載のシステム。
【請求項１４】
前記階層メッシュネットワークは、メタノードを含む、請求項１１に記載のシステム。
【請求項１５】
前記メタノードは、コンピューティングデバイスおよびコンピューティングデバイスのネットワークを示し、前記示されたコンピューティングデバイスおよびコンピューティングデバイスのネットワークは、階層内のピアを表す、請求項１４に記載のシステム。
【国際調査報告】
2006517077.tif 000040
2006517077.tif 000041
2006517077.tif 000042
2006517077.tif 000043