(57)【要約】【課題】並列に実行される、発見、関連付け、および運用の３つのタスクを備える動的バインディング・プロトコルを提供すること。【解決手段】発見では、複数の制御要素（ＣＥ）５０２および転送要素（ＦＥ）５０６は、制御プレーンとデータ・プレーンとを分けたＳｏｆｔＲｏｕｔｅｒ内の直近の近隣要素および複数のＣＥ  ５０２について学習する。関連付けでは、複数のＦＥ  ５０６は複数のＣＥ  ５０２と関連付けられ、ＩＰインターフェイス・アドレス、ホスト名などの基本パラメータにより構成される。運用では、複数のＣＥ  ５０２と複数のＦＥ  ５０６との間のフェイルオーバーおよびパケット・トンネリングが処理される。【選択図】図１
2006135970.tif 000002
【特許請求の範囲】
【請求項１】
動的バインディング・プロトコル・プロセスであって、
転送要素（ＦＥ）から制御要素（ＣＥ）への通信路を動的に確立することと、
ネットワークのトラフィック・トランスポートを制御し、前記ネットワークは物理的および論理的に隔てられているデータ・プレーンおよび制御プレーンを備え、前記データ・プレーンはパケット転送用の複数のＦＥを備え、前記制御プレーンはルーティング情報を構成し、制御し、プロトコルを介して前記複数のＦＥに供給するための複数のＣＥを備えることとを含む動的バインディング・プロトコル・プロセス。
【請求項２】
ＦＥからＣＥへの通信路を動的に確立することは、
複数のＦＥにより、ＣＥ広告を通じて前記複数のＦＥを制御するため複数の一次およびバックアップＣＥを発見することと、
前記複数のＦＥからＣＥへの通信路を監視することと、
複数の一次ＣＥに障害が発生した場合にバックアップ複数のＣＥに切り換えることとを含む請求項１に記載の動的バインディング・プロトコル・プロセス。
【請求項３】
ネットワーク・アーキテクチャであって、
パケット転送のため複数の転送要素（ＦＥ）を含むデータ・プレーンと、
標準プロトコルを介して、ルーティング情報を構成し、制御し、前記複数のＦＥに供給するための少なくとも１つの制御要素（ＣＥ）と、
ＦＥ−ＣＥ間通信路を確立し、トラフィック・トランスポートを制御するための、発見タスク、関連付けタスク、および運用タスクを持つ動的バインディング・プロトコルと、
前記データ・プレーンから物理的および論理的に隔てられている、前記ＣＥを含む制御プレーンとを備えるネットワーク・アーキテクチャ。
【請求項４】
前記動的バインディング・プロトコルは、トランスポートから独立しているプロトコル・メッセージを持つ請求項３に記載のネットワーク・アーキテクチャ。
【請求項５】
動的バインディング・プロトコル・プロセスであって、
複数の転送要素（ＦＥ）および制御要素（ＣＥ）により、定期的ｈｅｌｌｏ近隣要素メッセージを送信することと、
複数のＦＥおよびＣＥにより、定期的要請メッセージを送信することと、
複数のＣＥにより、前記要請メッセージに対する応答として広告メッセージを送信することと、
複数のＦＥにより、前記要請メッセージに対する応答として到達可能性メッセージを送信することと、
複数のＦＥにより、前記広告および到達可能性メッセージを集約して伝播することと、
それぞれのＦＥが、ＦＥを制御する関連付けられた複数のＣＥを持つように複数のＦＥと複数のＣＥの関連付けを行うことと、
複数のＣＥにより、前記複数の制御されるＦＥを構成することとを含む動的バインディング・プロトコル・プロセス。
【請求項６】
さらに、
特定のＦＥについて一方のＣＥから他方のＣＥへのプロトコル・フェイルオーバーを実行することを含む請求項５に記載の動的バインディング・プロトコル・プロセス。
【請求項７】
動的バインディング・プロトコル・プロセスであって、
制御要素（ＣＥ）をブートしてダウン状態からアップ状態にすることと、
前記ＣＥにより、要請メッセージを受信することと、
前記ＣＥにより、そのＩＤを広告メッセージを通じて伝播することと、
前記ＣＥが任意の複数の転送要素（ＦＥ）に関連付けられているか判別することと、
前記ＣＥにより、前記複数の関連付けられているＦＥを制御することとを含む動的バインディング・プロトコル・プロセス。
【請求項８】
動的バインディング・プロトコル・プロセスであって、
要請メッセージを受信することと、
ＣＥの集合を収集した後、到達可能性メッセージで複数のＣＥを伝播し、関連付けを要求することにより、前記要請メッセージに応答することと、
ＣＥから関連付け受理を受信し、前記ＣＥにより制御されることと、
アクティベーションを要求することにより前記関連付け受理に応答することと、
前記ＣＥからアクティベーション応答を受信することと、
前記関連付けられたＣＥの障害発生後、アクティベーション要求をバックアップＣＥに送信することと、
前記バックアップＣＥからアクティベーション受信確認を受信し、前記バックアップＣＥにより制御されることとを含む動的バインディング・プロトコル・プロセス。
【請求項９】
動的バインディング・プロトコル・プロセスを実行する命令を格納する記憶媒体であって、前記プロセスは、
転送要素（ＦＥ）から制御要素（ＣＥ）への通信路を動的に確立することと、
ネットワークのトラフィック・トランスポートを制御し、前記ネットワークは物理的および論理的に隔てられているデータ・プレーンおよび制御プレーンを備え、前記データ・プレーンはパケット転送用の複数のＦＥを備え、前記制御プレーンはルーティング情報を構成し、制御し、標準プロトコルを介して前記複数のＦＥに供給するための複数のＣＥを備えることとを含む動的バインディング・プロトコル・プロセスを実行する命令を格納する記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、ネットワーキングの分野に関するものであり、特に、ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例における動的バインディング・プロトコルに関するものである。
【背景技術】
【０００２】
本発明は、２００４年１１月１日に出願された「ＳｏｆｔＲｏｕｔｅｒ：  Ｒｏｕｔｅｒ  Ｄｉｓａｇｇｒｅｇａｔｉｏｎ」という表題の仮出願第６０／６２３，８８５号（整理番号Ｌａｋｓｈｍａｎ  ３５−２−２３−６２−３１）の利益を主張するものである。さらに、本出願は、本出願と同じ日に出願された同時係属出願「ＳｏｆｔＲｏｕｔｅｒ」（整理番号Ｌａｋｓｈｍａｎ  ３５−２−２３−６２−３１（ＬＣＮＴ／１２６７７０））、「ＳｏｆｔＲｏｕｔｅｒ  Ｐｒｏｔｏｃｏｌ  Ｄｉｓａｇｇｒｅｇａｔｉｏｎ」（整理番号Ａｎｓａｒｉ  ２−２−４１−３−２４−３４（ＬＣＮＴ／１２７３０５））、「ＳｏｆｔＲｏｕｔｅｒ  Ｐｒｏｔｏｃｏｌ  Ｆａｉｌｏｖｅｒｓ」（整理番号Ａｎｓａｒｉ  ３−４２−４−２５−３５（ＬＣＮＴ／１２７３０６））、「ＳｏｆｔＲｏｕｔｅｒ  Ｓｅｐａｒａｔｅ  Ｃｏｎｔｒｏｌ  Ｎｅｔｗｏｒｋ」（整理番号Ｌａｋｓｈｍａｎ  ４３−６４−３６（ＬＣＮＴ／１２７３０７））、「ＳｏｆｔＲｏｕｔｅｒ  Ｆｅａｔｕｒｅ  Ｓｅｒｖｅｒ」（整理番号Ｌａｋｓｈｍａｎ  ４４−６５−３７（ＬＣＮＴ／１２７３０８））に関係する。仮出願および関連出願は、すべて参照により本明細書に組み込まれる。
【０００３】
今日では、インターネット制御プレーンに多数の機能が付加されて行くとともに、従来のルータ・アーキテクチャは次第に複雑になりつつある。ルーティング・ポリシー実施およびトラフィック・エンジニアリングなどの多くの運用タスクは、自律的で複雑なルータからなるネットワークでは実行が困難であり、また厄介でもあるネットワーク規模の制御を必要とする。さらに、現在のルータでは、ルート・コントローラは転送エンジンに密結合されており、この静的バインディングのため障害が共有されることになる。
【０００４】
従来のルータ・アーキテクチャは、単純なコア・ネットワークを目指すエンドツーエンド・アーキテクチャ設計原理にもかかわらず、今日では、次第に複雑化してきている。新しい機能はインターネット・エンジニアリング・タスク・フォース（ＩＥＴＦ）によりＲＦＣ（Ｒｅｑｕｅｓｔｓ  Ｆｏｒ  Ｃｏｍｍｅｎｔｓ）の形で定義され、ルータ側には制御プレーンの複雑さがますます加わる。これらの機能は、ルーティング（例えば、ＢＧＰベースのＭＰＬＳ−ＶＰＮ）、トラフィック・エンジニアリング（例えば、ＯＳＰＦ−ＴＥ）、セキュリティなどを含む。実際、ＩＰルータのコード複雑度は、現在では、電話交換機のコード複雑度に匹敵している。それとは対照的に、大規模なハードウェア集積化（例えば、ＡＳＩＣ）が急速に進み、市販チップが入手しやすくなるにつれ、徐々に、転送パスの実装が容易になってきた。
【０００５】
従来のＩＰネットワークは、比較的自律的に動作するルータを使用して構築される。ネットワークのいたる所の多くの点に潜在的に管理しにくい複雑度が存在する。これは、多くの望ましくない帰結を導く。第１に、制御点が複数あると、運用の複雑さ（例えば、構成間違い設定）が著しく高まる。第２に、いくつかの特定の状況において、これらの自律的ルータの非協調アクションのため、せいぜい部分的に最適なパフォーマンス（例えば、回復時間が長い）にしかならず、最悪の場合にはネットワークが不安定になる可能性がある。最後に、新しい機能を導入するには、多数のルータへのアップグレードを必要とする場合があり、この作業は複雑であり、また間違いを犯しがちである。
【０００６】
従来のルータ・アーキテクチャでは、制御と転送を統合している。制御プレーン機能を実装する制御プロセッサは、転送機能を実装し、同じルータ・バックプレーンを共有することが多いライン・カードと同じ場所に配置される。制御プロセッサは、同じ場所に配置されているライン・カードにのみ制御機能を提供し、またその逆も同様であり、同じ場所に配置されている（複数の）コントローラに故障が生じた場合に、ライン・カードを管理できないようなシナリオに至る。
【特許文献１】仮出願第６０／６２３，８８５号
【特許文献２】同時係属出願「ＳｏｆｔＲｏｕｔｅｒ」（整理番号Ｌａｋｓｈｍａｎ  ３５−２−２３−６２−３１（ＬＣＮＴ／１２６７７０））
【特許文献３】「ＳｏｆｔＲｏｕｔｅｒ  Ｐｒｏｔｏｃｏｌ  Ｄｉｓａｇｇｒｅｇａｔｉｏｎ」（整理番号Ａｎｓａｒｉ  ２−２−４１−３−２４−３４（ＬＣＮＴ／１２７３０５））、
【特許文献４】同時係属出願「ＳｏｆｔＲｏｕｔｅｒ  Ｐｒｏｔｏｃｏｌ  Ｆａｉｌｏｖｅｒｓ」（整理番号Ａｎｓａｒｉ  ３−４２−４−２５−３５（ＬＣＮＴ／１２７３０６））
【特許文献５】同時係属出願「ＳｏｆｔＲｏｕｔｅｒ  Ｓｅｐａｒａｔｅ  Ｃｏｎｔｒｏｌ  Ｎｅｔｗｏｒｋ」（整理番号Ｌａｋｓｈｍａｎ  ４３−６４−３６（ＬＣＮＴ／１２７３０７））
【特許文献６】同時係属出願「ＳｏｆｔＲｏｕｔｅｒ  Ｆｅａｔｕｒｅ  Ｓｅｒｖｅｒ」（整理番号Ｌａｋｓｈｍａｎ  ４４−６５−３７（ＬＣＮＴ／１２７３０８））
【発明の開示】
【発明が解決しようとする課題】
【０００７】
従来技術のさまざまな欠点は、多くの実施形態を持つＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例に対する動的バインディング・プロトコルの本発明により対処される。
【課題を解決するための手段】
【０００８】
一実施形態は、転送要素（ＦＥ）から制御要素（ＣＥ）への通信路が動的に確立され、トラフィック・トランスポートはネットワークに合わせて構成される、動的バインディング・プロトコルである。ネットワークは、物理的および論理的に隔てられているデータ・プレーンおよび制御プレーンを含む。データ・プレーンは、パケット転送のため複数のＦＥを含む。制御プレーンは、標準プロトコルを介して、ルーティング情報を構成し、制御し、それを複数のＦＥに供給するため複数のＣＥを含む。他の態様は、この方法を実行するための命令を格納する記憶媒体である。
【０００９】
さらに他の実施形態は、物理的および論理的に隔てられているデータ・プレーンおよび制御プレーンを含む、ネットワーク・アーキテクチャである。データ・プレーンは、パケット転送のため複数のＦＥを含む。制御プレーンは、標準プロトコルを介して、ルーティング情報を構成し、制御し、それを複数のＦＥに供給するため少なくとも１つのＣＥを含む。ＦＥ−ＣＥ間通信路を確立し、トラフィック・トランスポートを制御するための動的バインディング・プロトコルがある。動的バインディング・プロトコルは、発見タスク、関連付けタスク、および運用タスクを持つ。
【００１０】
さらに他の実施形態は、動的バインディング・プロトコル・プロセスである。ＦＥおよびＣＥは、定期的なｈｅｌｌｏ近隣要素メッセージを送信する。ＦＥおよびＣＥは、定期的な要請メッセージを送信する。ＣＥは、要請メッセージに対する応答として広告メッセージを送信する。ＦＥは、要請メッセージに対する応答として到達可能性メッセージを送信する。ＦＥは、広告および到達可能性メッセージを集約して伝播する。それぞれのＦＥが、それを制御する関連付けられたＣＥを持つように複数のＦＥと複数のＣＥの関連付けが行われる。ＣＥは、制御されるＦＥを構成する。
【００１１】
さらに他の実施形態は、制御要素（ＣＥ）をブートしてダウン状態からアップ状態にすることを含む動的バインディング・プロトコル・プロセスである。ＣＥは、要請メッセージを受信する。ＣＥは、そのＩＤを広告メッセージを通じて伝播する。ＣＥが転送要素（ＦＥ）に関連付けられているかどうかを判別し、関連付けられていれば、ＣＥはそれらを制御する。
【００１２】
さらに他の実施形態は、転送要素（ＦＥ）をブートしてダウン状態からアップ状態にすることを含む動的バインディング・プロトコル・プロセスである。ＦＥは、制御要素（ＣＥ）またはＦＥ要請メッセージを受信し、到達可能性メッセージでＣＥを伝播することによりＣＥまたはＦＥ要請メッセージに応答する。ＦＥは、ＣＥの集合を集めた後、関連付けを要求することにより応答する。ＦＥは、ＣＥから関連付け受理を受信する。ＦＥは、ハートビート・メッセージを関連付けられたＣＥに送信し、関連付けられたＣＥからハートビート受信確認メッセージを受信する。
【００１３】
さらに他の実施形態は、要請メッセージを受信し、到達可能性メッセージでＣＥを伝播し、ＣＥの集合を集めた後、関連付けを要求することにより、要請メッセージに応答することを含む動的バインディング・プロトコル・プロセスである。ＦＥは、ＣＥから関連付け受理を受け取り、そのＣＥにより制御される。ＦＥは、アクティベーションを要求することにより関連付け受理に応答し、ＣＥからアクティベーション応答を受信する。ＦＥは、関連付けられたＣＥの障害発生後、バックアップＣＥにアクティベーション要求を送信し、バックアップＣＥからアクティベーション受信確認を受信し、その後、バックアップＣＥにより制御される。
本発明の教示は、付属の図面とともに以下の説明を考察することによりよく理解できる。
【発明を実施するための最良の形態】
【００１４】
理解しやすくするために、同一の参照番号を使用し、これらの図に共通の同一の要素を出来る限り指定する。
本発明は、主に、ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例の実施形態の一般的背景状況の範囲内において説明されるが、ただし、当業者および本明細書の教示による情報を得た者であれば、分離概念を使用して、ネットワーク・アーキテクチャの他のさまざまな実施形態を生み出すことができること、および本発明は、ローカル・エリア・ネットワーク（ＬＡＮ）、メトロポリタン・エリア・ネットワーク（ＭＡＮ）、ワイド・エリア・ネットワーク（ＷＡＮ）、および他のネットワーク、多くの開放型システム間相互接続（ＯＳＩ）層、ゲートウェイ・プロトコル、シリアル回線プロトコル、プロトコル・スタック・ルーティングおよびブリッジング・プロトコル、多くの他のプロトコル、トラフィック管理、光学、エッジ／コア・ルーティング、無線、ケーブル、データ・センター、補助信号経路（ＡＳＰ）、故障管理、構成管理、アカウンティング管理、パフォーマンス管理、セキュリティ管理、その他のネットワーク管理、企業、政府、軍事アプリケーション、およびその他の多くの異なる種類のネットワーキング特性およびアプリケーションに適用可能であることを理解するであろう。
【００１５】
インターネット・プロトコル（ＩＰ）は、プロトコルおよびアプリケーションにエンドツーエンドのデータグラム配信サービスを提供し、さまざまなリンク層技術を使用してパケットを配信することができる。図１は、図の砂時計の中央部分を拡大する、ＩＰ層のさらに多くの機能を必要とする新たに出現するアプリケーションの問題を例示している。これら新しいアプリケーションは、電子メール、ｗｗｗ電話、簡易メール転送プロトコル（ＳＭＴＰ）、ハイパーテキスト転送プロトコル（ＨＴＴＰ）、ルーティング・テーブル・プロトコル（ＲＴＰ）、伝送制御プロトコル（ＴＣＰ）、ユーザ・データグラム・プロトコル（ＵＤＰ）、および、サービスの品質（ＱｏＳ）、マルチキャスト、モビリティ、仮想プライベート・ネットワーク（ＶＰＮ）、およびその他の機能を伴い、銅線、ファイバ、無線、およびその他の物理的トランスポート手段を介してＥｔｈｅｒｎｅｔ（登録商標）、ポイント・ツー・ポイント・プロトコル（ＰＰＰ）、キャリア検知多重アクセス（ＣＳＭＡ）、ＡＳＹＮＣ（テレタイプライター（ＴＴＹ）の部分集合）、同期光ネットワーク（ＳＯＮＥＴ）、およびその他のプロトコルを使用してトランスポートされるその他のプロトコルを含む。従来のルータ・アーキテクチャでは、新しいＩＰ機能をすべてルータに組み込もうとし、その結果、ネットワークの複数のルータ内で複雑な機能が重複することになる。これは、資本支出および運用費用も増大させる。一般に、複数のルータからなるネットワークを運用することの複雑さおよび費用を低減する必要がある。
【００１６】
多くの新しい機能、例えば、境界ゲートウェイ・プロトコル（ＢＧＰ）、マルチプロトコル・ラベル・スイッチング（ＭＰＬＳ）ベースのＶＰＮ、およびトラフィック・エンジニアリング（ＴＥ）がルータに追加される。従来のルータ・アーキテクチャでは、５００万から１０００万行のコードを持ち、ネットワーク全体に複雑さが拡散される。トラフィック・エンジニアリングなどのオペレータのネットワーク規模の目的を達成するために、大域的目標を多数の個別ルータ内の構成情報に翻訳する複雑な作業を必要とする。構成設定間違いまたは非協調構成のため、パフォーマンスの低下またはネットワーク不安定性が生じる可能性がある。
【００１７】
インターネットが非常に大きな成功を収めたことで、新しい機能およびサービスの開発および展開がひっきりなしに続き、次第にその技術的基盤では間に合わなくなってきた。これは、ＩＰネットワークにおける機能の現在の配分のアーキテクチャリングを変更すれば、ネットワークの安定性、ネットワーク運用の簡素化、および新しいネットワーク・プロトコルおよびサービスの柔軟な導入にとって著しく有益であろうとの考えに信憑性を与えた。
【００１８】
ルーティング・ポリシー実施およびトラフィック・エンジニアリングなどの多くの高度なネットワーク管理タスクであれば、ネットワーク規模のビューを利用できることで著しい恩恵を受けるであろう。例えば、ＢＧＰによってネットワークの安定性および運用のいくつかの共通の問題が引き起こされる場合、それらの問題は、ＢＧＰを個々のルータのグループから自律的システム（ＡＳ）規模のスコープを持つ単一エンティティに移動することにより解決されるであろう。同様に、多くの管理機能は、ネットワーク規模のビューを必要とし、それなしでは、ネットワークは振動と安定性の悪さを露呈しうる。しかし、ネットワーク規模の制御は、自律的で複雑なルータからなる今日のネットワークでは実行が困難であり、また厄介でもある。
【００１９】
従来のルータ・アーキテクチャでは、基礎となるテーマは、現在のルータ制御および転送機能の深い相互の絡み合いである。これらの機能を縮小して、ごく少数の標準パケット転送機能のみをサポートし、すべての制御プロトコルおよび非転送関係状態および制御処理をネットワーク規模の制御の一次機能を持つ少数の高機能なネットワークベースの制御エンティティに移行することにより、ルータの脱構築を行いネットワーク・エンティティの大半をできる限り黙らせる必要がある。このような脱構築ルータでは、動的バインディング・プロトコルを利用して、制御要素および転送要素のバインドを行う。
定義
Ｔｄｉｓｃｏｖｅｒは、ＦＥまたはＣＥからのｈｅｌｌｏ近隣要素メッセージ間の予め定められている時間間隔である。
Ｔｃｏｌｌｅｃｔは、ＦＥが複数のＣＥを発見して、収集する予め定められている時間である。
Ｔｓｏｌｉｃｉｔは、ＦＥまたはＣＥからの要請メッセージ間の予め定められている時間間隔である。
Ｔｅｘｐｉｒｙは、ＣＥテーブル内のエントリに対する予め定められている有効期間である。
Ｔａｓｓｏｃｉａｔｅは、関連付け要求メッセージに対する予め定められているタイムアウト値である。
Ｔｃｏｎｆｌｇｕｒｅは、構成メッセージに対する予め定められているタイムアウト値である。
Ｔａｃｔｉｖａｔｅは、アクティベーション・メッセージに対する予め定められているタイムアウト値である。
Ｔｈｅａｒｔｂｅａｔは、ＦＥとＣＥとの間のハートビート・メッセージ間の予め定められている時間間隔である。
Ｗｐａｔｈは、ＣＥへの経路がダウンしていると宣言されるまでのｔｈｅａｄｂｅａｔの待機期間の予め定められた数である。
Ｗｄｉｓｃｏｖｅｒは、近隣ＦＥへのリンクがダウンしていると宣言されるまでのｔｄｉｓｃｏｖｅｒの待機期間の予め定められた数である。
Ｒａｓｓｏｃｉａｔｅは、次のＣＥに切り換える前にＣＥに行う関連付けの予め定められている再試行回数である。
Ｒｃｏｎｆｉｇｕｒｅは、次のＣＥに切り換える前にＣＥから構成を取得する予め定められている再試行回数である。
Ｒａｃｔｉｖａｔｅは、バックアップＣＥをアクティベートする予め定められている再試行回数である。
【００２０】
インターネットワーキングにオープンな標準ベースのプロトコルを使用してルータのハードウェアをルータのソフトウェアから分離することには、多くの利点がある。分離概念は、各コンポーネントのサプライヤを分断することで、ハードウェア・ベンダの参入を阻害している壁を低くし、新規ハードウェア市場参入者に供給するキャリア・クラス・ルーティング・ソフトウェアの開発に独立系ソフトウェア・ベンダ（ＩＳＶ）が投資する意欲を高める。この分離概念を利用することにより、それぞれのコンポーネントがそれ独自の革新曲線から逸れることなく辿れるようにできる。ハードウェア・メーカーは、最低のコストで最高の単位密度当たり速度を達成することに集中して、資本支出を低減することができ、またソフトウェア・メーカーは、新しいアプリケーションおよびマネジャビリティに集中して、経常経費を下げつつ収益を高めることができる。
【００２１】
ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例の一実施形態では、制御プレーン機能の実装とパケット転送機能とを分けることによりルータの脱構築を行う。この脱構築を実現するネットワーク・アーキテクチャの他の実施形態も、本発明の範囲内にある。本発明は、この脱構築の概念およびネットワーク・アーキテクチャに対するその密接な関係を対象とする。ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例では、すべての制御プレーン機能は、転送エンジンと同じ場所に配置される必要のない別の制御エンティティ上に実装される。協調構成変更は少数のスマート・ネットワーク要素のみで行えばよく、ＡＳ内のすべてのネットワーク要素で行う必要がないため、すべての非転送関係状態および制御処理を少数のネットワークベースの制御エンティティに移行することにより、ネットワーク規模の目標を単純化することが可能になる。さらに、コントローラと転送エンジンとの関連は動的であり、制御を行うことができる制御エンティティによる転送エンジンの柔軟な制御が可能である。
【００２２】
ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例は、ネットワーク内の転送エンティティと制御エンティティとの間の動的バインディングを確立し、維持するための動的バインディング・プロトコルを含む。ドメイン内およびドメイン間ルーティングは、ドメイン内プロトコルＯＳＰＦのパフォーマンス改善を含む、パフォーマンスが改善されたＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例において適合される。
【００２３】
インターネットワーキングにオープンな標準ベースのプロトコルを使用してルータのハードウェアをルータのソフトウェアから分離することには、多くの利点がある。分離概念は、各コンポーネントのサプライヤを分断することで、ハードウェア・ベンダの参入を阻害している壁を低くし、新規ハードウェア市場参入者に供給するキャリア・クラス・ルーティング・ソフトウェアの開発に独立系ソフトウェア・ベンダ（ＩＳＶ）が投資する意欲を高める。この分離概念を利用することにより、それぞれのコンポーネントがそれ独自の革新曲線から逸れることなく辿れるようにできる。ハードウェア・メーカーは、最低のコストで最高の単位密度当たり速度を達成することに集中して、資本支出を低減することができ、またソフトウェア・メーカーは、新しいアプリケーションおよびマネジャビリティに集中して、経常経費を下げつつ収益を高めることができる。
【００２４】
ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例の一実施形態は、新しく出てくるアプリケーションにより要求される複雑なルータ機能を分離する１つのアプローチである。ＳｏｆｔＲｏｕｔｅｒは、複雑さの共有を中央に集中し、複雑さの共有を可能にする。ＳｏｆｔＲｏｕｔｅｒでは、ＩＰ転送機能を過度に妨げることなく新機能のスケーラブルな導入を果たせる。
【００２５】
図２は、集積化された制御およびトランスポート・プレーンを備える従来のルータ２００を示している。従来のルータ２００は、ハードウェアを共有し、専用インターフェイス２０６を通じて通信する制御２０２および転送２０４を備える。
【００２６】
それとは対照的に、図３は、標準プロトコルを使用して通信する別々のハードウェア内の制御プレーンとトランスポート・プレーンを分離するＳｏｆｔＲｏｕｔｅｒアーキテクチャ３００の実施例の高水準抽象化を示している。ＳｏｆｔＲｏｕｔｅｒアーキテクチャ３００は、制御要素およびフィーチャ・サーバ・コンポーネント３０２、および標準ベースのプロトコル３０６を使用して通信するパケット転送要素コンポーネント３０４を備える。
【００２７】
図４は、相互接続された多数のルータ４００を備える従来のルータ・アーキテクチャを示す。
図５は、ＳｏｆｔＲｏｕｔｅｒアーキテクチャ５００の実施例の一実施形態を示している。ＳｏｆｔＲｏｕｔｅｒアーキテクチャ５００のこの実施形態では、ソフトウェア・サーバは、制御要素（ＣＥ）５０２およびフィーチャ・サーバ（ＦＳ）５０４を含む。ＣＥ  ５０２は、従来のルーティング、例えば、内部ゲートウェイ・プロトコル（ＩＧＰ）（例えば、開放型最短経路優先（ＯＳＰＦ））および外部ゲートウェイ・プロトコル（ＥＧＰ）（例えば、境界ゲートウェイ・プロトコル（ＢＧＰ））の両方に関与する。ＦＳ  ５０４は、付加価値機能およびネットワーク・ベース・アプリケーション、例えば、ＱｏＳ、ＶＰＮ、およびモバイルＩＰに関与する。ＣＥ  ５０２およびＦＳ  ５０４は、両方とも、転送要素（ＦＥ）５０６とインターフェイスする。ＣＥ  ５０２およびＦＳ  ５０４は、それぞれ相手との追加インターフェイスを備えることができる。ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例は、ソフトウェア・ベースのルート・コントローラ（ＳｏｆｔＲｏｕｔｅｒ）をハードウェア・ベースのトランスポートおよびパケット転送から分離して、中央に集中させる。
【００２８】
ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例におけるルータの脱構築により、制御機能と転送機能とが分離される。この分離は、論理的に行われるだけでなく（例えば、モジュール型アプリケーション・プログラミング・インターフェイス（ＡＰＩ）で正しく定義されたインターフェイスの使用）、実際、制御は、転送が実行される場所から数ホップ分だけ物理的に隔てられている（つまり、別のネットワーク要素内で実行される）。
【００２９】
ＦＥ  ５０６は、トラフィックの実際の転送およびスイッチングを実行するネットワーク要素である。構造上、ＦＥ  ５０６は、それぞれ次々に複数のポートの終端となる複数のライン・カード、および一方のライン・カードから他方のライン・カードへデータ・トラフィックを往復するスイッチ・ファブリックを備えることができるという点で従来のルータと類似している。しかし、ローカルで実行される高度な制御ロジック（例えば、ＯＳＰＦまたはＢＧＰのようなルーティング・プロセス）がないため、ＦＥ  ５０６は従来のルータと異なる。その代わりに、制御ロジックはリモートでホスティングされる。
【００３０】
ＣＥ  ５０２は、サーバなどの汎用コンピューティング要素である。これは、エンド・ホストと同様にネットワークに接続するが、ただし、通常、複数のＦＥ  ５０６を介してネットワークにマルチホーミングで接続されるため、単一のリンクに障害が発生してもネットワークから切断されることはない。ＣＥ  ５０２は、ＦＥ  ５０６の代わりに、制御ロジックを実行し、したがって、それらを制御する。従来のルータに通常存在する制御ロジックは、ＯＳＰＦおよびＢＧＰのようなルーティング・プロトコルだけでなく資源予約プロトコル（ＲＳＶＰ）、ラベル配布プロトコル（ＬＤＰ）、モバイルＩＰなどのプロトコルをも含めて、ＣＥ  ５０２に移行することができる。
【００３１】
ＦＥ  ５０６は、リンク間でデータ・トラフィックを転送する機能を実行する。この機能は、特にパケット転送、ラベル・スイッチング、および光スイッチングなど、さまざまな形態を取りうる。パケット転送は、レイヤ２（媒体アクセス制御（ＭＡＣ）ベースのスイッチング）およびレイヤ３（最長プレフィックス一致）転送の両方を含む。ラベル・スイッチングは、例えば、ＭＰＬＳ転送を含む。データ・パス転送機能は、ラベル・スワッピング、プッシング、およびポッピングを含むことができる。光スイッチングでは、トラフィックは、リンク間で、時間スイッチング、波長スイッチング、または空間スイッチングが可能である。これらの場合のそれぞれにおいて、スイッチング機能は、ネットワーク内のＣＥ  ５０２により計算され、インストールされる単純ローカル・テーブルにより駆動される。そのため、ＦＥ  ５０６がローカル・データ構造にのみ基づいてその作業を遂行できることは、ＦＥ  ５０６は低機能であるが高速であるように設計され、より複雑なロジックはリモートにありながら高機能なＣＥ  ５０２に委ねられていることを意味している。
【００３２】
ＦＥ  ５０６およびＣＥ  ５０２は、両方とも、物理ネットワーク要素であることに加えて論理エンティティと理解される。特に、ＦＥ  ５０６は、トラフィックを相互に切り換えられるポートの集合体として論理的に定義される。例えば、ＦＥ  ５０６は、単一のライン・カード上のポートを含むことができるが、この場合、物理パケット・スイッチ全体は複数の論理ＦＥ  ５０６で構成される。ＦＥ  ５０６は、さらに、複数の物理スイッチにまたがってもよいが、ＣＥは複数のＦＥを制御することができる。同様に、ＣＥ  ５０２は、ＦＥの代わりに制御を行うためにインスタンス化された論理プロセスとして理解することができ、また実際にそれを実行するサーバ・マシンから区別することができる。特に、物理ＣＥサーバ・マシン（ＰＣＥ）は、それぞれ複数のＦＥ  ５０６からなる異なる集合体にサービスを提供する、複数のＣＥ  ５０２プロセスをホスティングすることができる。その逆に、同じＦＥ  ５０６にサービスを提供する複数のＣＥ  ５０２プロセス（それぞれ、内部ゲートウェイ・プロトコル（ＩＧＰ）および外部ゲートウェイ・プロトコル（ＥＧＰ）などの異なる制御目的に合わせてインスタンス化される）を異なるＰＣＥ上でホスティングすることも可能である。ＦＥ  ５０６およびＣＥ  ５０２の物理的および論理的定義は、入れ換えて使用できる。
【００３３】
図６は、ネットワーク要素６００を例示するＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例の一実施形態を示している。ルータという概念は、ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例では厳密には必要とされないが、ネットワークのルーティングに関する面を理解するために、何らかの同等の概念を用意することが有用である。この目的のために、ネットワーク要素（ＮＥ）６００の概念は、ＦＥ  ５０６およびそれらのＦＥ  ５０６を制御するそれぞれのＣＥ  ５０２からなる論理グループとして高水準の定義が行われる。特定のＮＥ  ６００グループは、暗黙のうちに、ＦＥ間の各リンクを内部（またはＮＥ内）または外部（またはＮＥ間）のいずれかとして分類する。内部リンクは、同じＮＥ  ６００に属する２つのポートを接続し、外部リンクは、異なるＮＥ  ６００に属する２つのポートを接続する。ＮＥ  ６００の概念は、ＮＥ内およびＮＥ間ルーティングが異なるアプローチに従う場合に有用である。
【００３４】
制約を加えることなく、ＮＥ  ６００の上記の定義は柔軟に対応できる。例えば、この定義では、ネットワークの非連結部分の中の２つのＦＥ  ５０６が同じＮＥ  ６００に属すようにできる。また、これにより、ＦＥ  ５０６が物理要素内の完全にすべてポートポートを含み、（複数の）制御ＣＥ  ５０２が同じ要素上の同じ場所に配置される従来のルータ・モデルが可能になる。
【００３５】
クラスタ化されたルーティングでは、ＮＥ  ６００を構成するＦＥ  ５０６は、切れ目のないクラウドの一部である。つまり、ＮＥ  ６００のすべてのポートは、ＮＥ  ６００の内部のリンクを介してお互いから到達可能であるということである。物理的に、これは、隣接する物理ＦＥ  ５０６の単一のＮＥ  ６００内へのクラスタ化を表す。本社では複数のルータが背中合わせで接続されているというのが通常のシナリオである。ルーティングの観点からは、ＮＥ  ６００に対するこのクラスタ化ベースの定義は、著しい簡素化をもたらしうる。ルーティングの面でＮＥ  ６００の個数が減ることにより、ＮＥ間のルーティングの複雑さが減じ、異なる、場合によっては複雑さの少ないルーティング・プロトコルをＮＥ内ルーティングに採用することができる。
【００３６】
ＦＥ  ５０６とＣＥ  ５０２との制御関係は、バインディングと正式に呼ばれる。より正確には、ＦＥ  ５０６とＣＥ  ５０２との間バインディングは、ＣＥ  ５０２がＦＥ  ５０６の代わりに特定の制御機能を実行していることを意味する。複数のプロトコル（例えば、ＩＧＰおよびＥＧＰ、またはさらには１つのプロトコルの複数のインスタンス）がＦＥ  ５０６の動作に必要になる場合があるため、ＦＥ  ５０６は複数のＣＥ  ５０２バインディングを持ちうる。
【００３７】
ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例は、さまざまなプロトコルを含む。ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例に従って設計されたネットワークの運用には、動的バインディング・プロトコルおよびＦＥ／ＣＥトランスポート・プロトコルを含む、さまざまな多数のプロトコルが使用される。ＦＥ  ５０６とＣＥ  ５０２との間のバインディングは、ＣＥ  ５０２およびＦＥ  ５０６を発見するプロトコルを介して確立され、さらに、ネットワークの接続途絶に直面したときもこれらのバインディングを維持する。動的バインディング・プロトコルの最も一般的な場合には、ＦＥ  ５０６は、利用可能な任意のＣＥ  ５０２にバインドすることができ、ＣＥ  ５０２は、任意のＦＥ  ５０６に対する制御機能を実行し、それによって、回復力を最大限発揮し、構成オーバーヘッドを最小限にとどめることができる。この動的バインディング機能は、制御機能と転送機能とが独立している脱構築ルータ群の概念の１つの特徴である。ＦＥ／ＣＥトランスポート・プロトコルは、２つの部分、つまりデータおよび制御を持つ。データ部については、ＦＥ／ＣＥトランスポート・プロトコルは、ＦＥ  ５０６とＣＥ  ５０２との間のルーティング・プロトコル・パケットのトンネリングをサポートしており、そのため、ＦＥ  ５０６により受信されたルーティング・プロトコル・パケットをＣＥ  ５０２に送信して処理させることができる。制御部については、バインディングが確立されると、ＦＥ  ５０６およびＣＥ  ５０２は、ＦＥ／ＣＥトランスポート・プロトコルを使用して、状態情報を伝達し、制御を実行する。アップリンク（ＦＥ  ５０６からＣＥ  ５０２）方向では、この制御部は、リンクおよび転送状態情報（例えば、リンク・アップ／ダウン信号）をＣＥ  ５０２に供給する。ダウンリンク方向では、ＦＥ／ＣＥトランスポート・プロトコルは、構成および制御情報を伝送する（例えば、リンク、転送情報ベース（ＦＩＢ）の有効／無効を設定する）。転送および制御要素の分離などの知られているプロトコル（ＦｏｒＣＥＳ）を、ＦＥ／ＣＥトランスポート・プロトコルに使用することができる。
【００３８】
動的バインディング・プロトコルの一実施例は、転送要素（ＦＥ）から制御要素（ＣＥ）通信への通信路を確立し、トラフィック・トランスポートを制御する。ＦＥがブートすると、ルーティングは使用できなくなり、ＦＥは、一意的な識別子（ＦＥＩＤ）でしか構成されない。それぞれのＦＥは、そのＣＥを発見し、開放型最短経路優先（ＯＳＰＦ）などの上層アプリケーションにルートをインストールさせるため通信を開始する。ＦＥ−ＣＥ通信路は、監視されており、障害が発生した場合にバックアップＣＥに切り換えられる。それぞれのＣＥは、その一意的識別子（ＣＥＩＤ）を通じて識別される。動的バインディング・プロトコルのこの実施例は、インターネット・プロトコル（ＩＰ）ルーティング独立である。動的バインディング・プロトコルのこの実施例は、さらに、フォールバック・プロトコルとして動作し、例えば、通常のルーティング障害でＦＥが到達不可能なままになっている場合に、ＣＥ−ＦＥ間制御通信を行えるようにできる。
【００３９】
図７は、発見７０２、関連付け７０４、および運用７０６の並列実行される３つのタスクを持つ、動的バインディング・プロトコル７００の実施例の一実施形態を示す。発見７０２では、複数のＣＥまたはＦＥがネットワーク内の直近の近隣要素およびＣＥに関して学習する。関連付け７０４では、複数のＦＥは複数のＣＥと関連付けられ、ＩＰインターフェイス・アドレス、ホスト名などの基本パラメータにより構成される。運用７０６では、ＣＥとＦＥとの間のフェイルオーバーおよびパケット・トンネリングが処理される。
【００４０】
図８は、動的バインディング構造８００の実施例の一実施形態を示している。動的バインディング構造８００は、トランスポート８０４から独立しているプロトコル・メッセージ８０２を含む。可能なトランスポートとしては、限定はしないが、ソース・ルーティング、ベクトル距離ルーティング、単純リンク状態ルーティング、およびスパニング・ツリーとのブリッジングがある。
【００４１】
図９は、動的バインディング・プロトコルの実施例の一実施形態による、近隣要素発見の発見タスクを示す。近隣要素の発見では、ＣＥおよびＦＥは、定期的ｈｅｌｌｏメッセージを送信し、リンク状態を監視する。図９に示されている実施例では、４つのＦＥ、つまりＦＥ１  ９００、ＦＥ２  ９０２、ＦＥ３  ９０４、およびＦＥ４  ９０６、および２つのＣＥ、つまりＣＥ１  ９０８およびＣＥ２  ９１０がある。例えば、ＦＥ１  ９００は、ｈｅｌｌｏメッセージ９１２をその近隣要素ＣＥ１  ９０８、ＦＥ３  ９０６、およびＦＥ２  ９０２に送信する。
【００４２】
図１０は、動的バインディング・プロトコルの実施例の一実施形態による、ＣＥ広告の発見タスクを示している。発見では、ＣＥは自分自身を伝播し、ＦＥはＣＥ伝播を集約して、転送する。ソース・ルーティングがトランスポートとして使用される場合、ソース・ルートが記録される。図１０に示されている実施例では、ＦＥ１  ９００がそのすべてのインターフェイス上で要請メッセージを送信した後、ＣＥ１  ９０８が、広告メッセージ１０００をＦＥ１  ９００に送信することにより自分自身を広告する。広告メッセージ１０００は、ＣＥ１  ９０８を識別するＣＥＩＤおよびＦＥ１  ９００からＣＥ１  ９０８への経路を含む。ここで、この経路は、ＦＥ１  ９００からＣＥ１  ９０８までの１ホップの距離である。ＦＥ２  ９０２が要請を送信した場合、ＦＥ１  ９００は、ＣＥ１  ９０８を識別するＣＥＩＤおよびＦＥ２  ９０２からＣＥ１  ９０８への経路を含む他のメッセージ１００２をＦＥ２  ９０２に送信することにより、ＣＥ１  ９０８から受信した広告メッセージ１０００の内容を近隣要素ＦＥ２  ９０２に転送し、ＦＥ１  ９００は、ＦＥ１  ９００からＦＥ２  ９０２への経路をＣＥ１  ９０８からＦＥ１  ９００への経路上に付加することによりそれを知る。ＦＥ２  ９０２は、さらに、ＣＥ２  ９１０から広告メッセージ１００４を受信し、ＦＥ２  ９０２はそれを他のメッセージ１００６でＦＥ４  ９０４に転送したが、ＦＥ４  ９０４は、すでに、ＣＥ２  ９１０から直接、広告メッセージ１００８を受信している。
【００４３】
図１１は、動的バインディング・プロトコルの実施例の一実施形態による、関連付けタスクを示している。関連付けでは、通信路を確立するためＦＥとＣＥとの関連付けが行われる。ＣＥは、ＦＥを拒絶するか、またはＦＥを他のＣＥへルート変更できる。図１１に示されている実施例では、ＦＥ１  ９００は、関連付け要求メッセージ１１００をＣＥ１  ９０８に送信する。それに対する応答として、ＣＥ１  ９０８は、関連付け受理メッセージ１１０２を送信する。ＦＥ３  ９０６は、さらに、関連付け要求メッセージ１１００をＣＥ１  ９０８に送信するが、ＣＥ１  ９０８は、否定的応答１１０２を、ＣＥ２  ９１０を試す提案とともに送り返す。したがって、ＦＥ３  ９０６は、関連付け要求メッセージ１１００をＣＥ２  ９１０に送信する。
【００４４】
図１２は、動的バインディング・プロトコルの実施例の一実施形態による、構成タスクを示している。構成では、関連付けられたＣＥは、ＩＰアドレス、ホスト名などの基本的ＦＥ構成を規定する。図１２に示されている実施例では、ＦＥ１  ９００は、関連付けられたＣＥ、ＣＥ１  ９０８に構成を要求する、メッセージ１２００を送信する。ＣＥ１  ９０８は、構成情報１２０２をＦＥ１  ９００に送信することにより応答する。同様に、ＦＥ３  ９０６は、関連付けられたＣＥ、ＣＥ２  ９１０に構成を要求する、メッセージ１２００を送信する。ＣＥ２  ９１０は、構成情報１２０２をＦＥ３  ９０６に送信することにより応答する。
【００４５】
図１３は、動的バインディング・プロトコルの実施例の一実施形態による、フェイルオーバーの運用タスクを示している。運用では、ＦＥは、一次ＣＥとバックアップＣＥの集合とに関連付けられる。ＦＥは、経路監視のためその一次およびバックアップＣＥとハートビート・メッセージを交換する。経路途絶後、メッセージ・タイマーが終了し、ＦＥは、そのバックアップＣＥのうちの１つをアクティベートし、その後、ルーティングなどの上層プロトコルまたはアプリケーションに通知する。図１３に示されている実施例では、ＦＥ１  ９００は、一次ＣＥ、ＣＥ１  ９０８および二次またはバックアップＣＥ、ＣＥ２  ９１０と関連付けられる。ＦＥ１  ９００は、ハートビート・メッセージ１３００を送信するが、経路途絶１３０２があり、ＣＥ１  ９０８から受信確認メッセージ１３０４を受信する前にタイマーがＦＥ１  ９００でタイムアウトになる。ＦＥ１  ９００は、メッセージ１３０６をＣＥ２  ９１０に送信し、ＣＥ２  ９１０をそのＦＥの管理側ＣＥとしてアクティベートする。
【００４６】
図１４は、動的バインディング・プロトコルの実施例の一実施形態による、トランスポートの運用タスクを示している。ルート・テーブル・マネージャ（ＲＴＭ）は、さまざまなルーティング・プロトコルのルート更新を収集し、通常のＩＰを通じて転送情報ベース（ＦＩＢ）を更新する。通常のＣＥからＦＥへの通信路（例えば、ＩＰルーティング）が利用不可の場合、動的バインディング・プロトコルのこの実施例がＦＥ  ＦＩＢ更新に使用される。図１４では、ＣＥ１  ９０８は、ＯＳＰＦ  １４００、ＢＧＰ  １４０２、ＲＴＭ  １４０４、ＩＰ  １４０６、および動的バインディング・プロトコル１４０８プロセスを含む。ＦＥ１  ９００は、ＦＩＢ管理、ＲＴＭプロキシ１４１０、動的バインディング・プロトコル１４０８、ＩＰ  １４０６、およびＦＩＢ  １４１２プロセスを含む。トンネル１４１４は、ＣＥ１  ９０８およびＦＥ１  ９００で動的バインディング・プロトコル１４０８を接続する。通常のＩＰルーティングでは、ＣＥ１  ９０８およびＦＥ１  ９００のＩＰ  １４０６を接続する。
【００４７】
動的バインディング・プロトコルの一実施例（ａ／ｋ／ａ  Ｄｙｎａ−ＢＩＮＤ）は、さまざまなプロトコル指定、メッセージ型、状態機械、およびメッセージ形式を含む。Ｄｙｎａ−ＢＩＮＤプロトコルは、ＦＥをＮＥ内のＣＥに関連付けるために使用される。Ｄｙｎａ−ＢＩＮＤプロトコルは、ＦＥ／ＣＥのブートアップ段階で使用され、ＦＥがＣＥを発見するのを助ける。Ｄｙｎａ−ＢＩＮＤプロトコルは、常に、ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例の複数の要素において実行され、複数のＦＥとそれらの対応する複数のＣＥとの間の関連付けを管理し、維持する。Ｄｙｎａ−ＢＩＮＤプロトコルでは、ＮＥ内のＦＥ間トポロジの発見または維持をサポートする。データ経路転送トポロジの発見および維持は、ＮＥ内の別のプロトコルにより処理される。
Ｄｙｎａ−ＢＩＮＤプロトコルの概要
【００４８】
Ｄｙｎａ−ＢＩＮＤプロトコルのこの実施例は、プル・モデルに基づいており、そこでは、ＦＥはローカルの近隣要素を発見し、ＣＥとの関連付けを発見、維持し、ＣＥから基本構成情報を取得する役割を持つ。これは、別のプロトコルおよびＮＥルーティング・プロトコルにおける後の段階のＦＥの運用に関するプッシュ・モデルとは異なる。
【００４９】
Ｄｙｎａ−ＢＩＮＤプロトコルのこの実施例では、複数のＦＥおよび複数のＣＥが、ネットワーク内のすべてのＣＥへの経路を連続的に知ろうとする。これらは、近隣要素発見を行えるようにそのすべてのインターフェイス上でｈｅｌｌｏメッセージを定期的に（ｔｄｉｓｃｏｖｅｒ）ブロードキャストする。さらに、それらのインターフェイスのすべてで要請メッセージをブロードキャストすることによりＣＥ情報を定期的に（ｔｓｏｌｉｃｉｔ）要請する。要請メッセージを受信した後、複数のＦＥは到達可能性メッセージで応答し、複数のＣＥは広告メッセージで応答する。到達可能性または広告メッセージを受信した後、ＦＥまたはＣＥは、近隣要素テーブル内に近接エントリを作成するが、これらのテーブルは、近隣要素ＣＥＩＤまたはＦＥＩＤをインターフェイスおよび経過時間パラメータｗｄｉｓｃｏｖｅｒ＊ｔｓｏｌｉｃｉｔとともに格納する。到達可能性または広告メッセージがｗｄｉｓｃｏｖｅｒ期間内に受信されない場合、近接は無効であると宣言される。広告メッセージは、発行側ＣＥのＣＥＩＤを単一ホップ・ソース・ルートとともにＣＥに伝播する。到達可能性メッセージは、近隣ＦＥに集約されたＣＥＩＤおよび対応するソース・ルートを伝播する。複数のＦＥは、広告または到達可能性メッセージから複数のＣＥへのソース・ルートを導き出すが、複数のＣＥは、最後に受信したメッセージからＦＥへのソース・ルートを導き出す。
【００５０】
ＦＥは、ＣＥＩＤおよび対応するソース・ルートをそのＣＥテーブルに格納する。それぞれのテーブル・エントリは、エントリがテーブルから削除されるまでの存在期間の秒数を規定する寿命パラメータに関連付けられる。受信された到達可能性または広告メッセージのＣＥＩＤが知られていない場合、新しいエントリが追加され、対応するメッセージ・エントリから初期寿命値が取り出される。ＣＥＩＤがすでにテーブル・エントリを持っている場合、寿命は更新される。ＣＥは、複数のＦＥＩＤおよび対応するソース・ルートを、ＦＥへのソース・ルートが無効であると宣言されるまでの存在期間の秒数を規定する寿命パラメータ（ｗｐａｔｈ＊ｔｓｏｌｉｃｉｔ）とともにＦＥテーブル内に格納する。ＦＥテーブル内の要素は、構成を通じて予め定義され、ＣＥが一次またはバックアップとして制御できる複数のＦＥを識別する。
【００５１】
Ｄｙｎａ−ＢＩＮＤプロトコルのこの実施例では、ＣＥに関連付けられていないＦＥは、ＣＥテーブルを埋めるｔｃｏｌｌｅｃｔ時間か、または少なくとも１つのＣＥを見つけるのに要する時間か、いずれか長い方の時間の間待つ。この時間が経過すると、ＦＥは、ＣＥテーブルから１つのＣＥを選び、ＣＥテーブル内のソース・ルートを使用して関連付け要求メッセージを使用してそのＣＥと接触する。ＣＥが進んでこのＦＥを受け入れる場合には、関連付け受理メッセージでＦＥに応答する。ＣＥからＦＥへのルートは、要求メッセージ内のソース・ルートを逆にすることにより得られる。ＣＥが、関連付けを要求するＦＥを構成するつもりがない／構成することを許されていない場合、どのＣＥがその特定のＦＥを管理できるかを知ることができるであろう。もしそうならば、この情報は、オプションの関連付け拒絶メッセージでＦＥに報告される。ＦＥがｔａｓｓｏｃｉａｔｅ以内に関連付け受理または関連付け拒絶を受け取らない場合、関連付け要求が再送される。ｒａｓｓｏｃｉａｔｅ回の再試行の後、ＦＥはテーブル内の次のＣＥを選択する。すべてのＣＥが試されると、ＦＥは最初から開始する。このループは、関連付けが得られるまで無限に実行される。
【００５２】
関連付け受理を受信した後、ＦＥは、ＣＥがＦＥを適宜構成することを許す、ＣＥへの構成要求メッセージで応答する。構成は、ＣＥとＦＥとの間で何らかの方法により実行され、ＣＥは、構成応答メッセージで構成をＦＥに伝達する。ＦＥがｔｃｏｎｆｉｇｕｒｅ以内に構成応答を受信しない場合、構成要求が再送される。ｒｃｏｎｆｉｇｕｒｅ回の再試行の後、ＦＥはテーブル内の次のＣＥを選択する。すべてのＣＥが試されると、ＦＥはテーブルの先頭から開始する。
【００５３】
構成応答メッセージを受信した後、ＦＥは、ＦＥが動作可能状態にあることを示す、ＣＥへのアクティベーション要求メッセージで応答する。ＣＥは、アクティベーション応答で受信確認する。ｔａｃｔｉｖａｔｅ回の再試行の後、ＦＥはテーブル内の次のＣＥを選択する。すべてのＣＥが試されると、ＦＥはテーブルの先頭から開始する。前のＣＥのＦＥ関連付けは、ｔｅｘｐｉｒｙが過ぎると期限切れとなる。ＣＥテーブルは、前述の到達可能性メッセージに基づいて、この期間中も書き込みが続けられることに注意されたい。アクティベーションの後、ＦＥは、ＣＥテーブルの循環操作および関連付け要求メッセージの送信によりバックアップＣＥを関連付けることを試みる。一次ＣＥテーブル・エントリは、バックアップの対象とはみなされない。すべてのＦＥは対応するＣＥに直接的にまたは間接的に接続されると想定されているため、それぞれＦＥは、最終的に、ＦＥを管理できるＣＥについて知ることになる。このため、それぞれのＦＥは、最終的に、一次管理側ＣＥに到達し、したがって、構成されることになる。ＦＥ毎に、１つの一次ＣＥおよび少なくとも１つのバックアップＣＥが存在する。現在アクティブなＣＥは、管理側ＣＥであり、これは、一次ＣＥまたはバックアップＣＥのいずれかである。
【００５４】
ＦＥがＣＥに関連付けられた後、ＦＥは、ＣＥとハートビート・メッセージを定期的に（ｔｈｅａｒｔｂｅａｔ）交換する。ＦＥは、ＣＥとの関連付けを維持する役割を持つ。ＣＥは、ＦＥによって送信されたすべてのハートビート・メッセージの受信確認を送る。ＦＥがｗｐａｔｈを超える期間の間にこの受信確認メッセージを受信しない場合、その関連付けは無効であると宣言され、ＦＥはＣＥとの再関連付けを試みる。ＣＥがｔｈｅａｒｔｂｅａｔのｗｐａｔｈ期間にハートビート・メッセージを受信しない場合、その関連付けは無効であると宣言される。
【００５５】
ＦＥ−ＣＥ関連付けの後、ペイロード・メッセージにより、上層プロトコルに通信路が与えられる。上層プロトコルは、ペイロード・メッセージ内にカプセル化され、関連付けられたＦＥとＣＥとの間で交換される。シーケンス配信での信頼性についてはいっさい保証されない。上層パケット交換は、関連付けられた複数のＣＥとＦＥとの間でしか可能でない。
【００５６】
メッセージの型および形式
Ｄｙｎａ−ＢＩＮＤプロトコルのこの実施例は、常にブロードキャストされるさまざまなメッセージを含む。レイヤ３インターフェイス・アドレスがトランスポートに使用される場合、ブロードキャストまたはマルチキャスト・アドレス指定を制限することで、リモート・ピアが異なるサブネットに属すＩＰアドレスを選択した場合でも、メッセージ配信が確実に行われるようにできる。メッセージ形式の実施例は、２１６＝６５５３６バイトなどの所定の最大メッセージ・サイズよりも小さいバイト単位のメッセージ長を含む。チェックサムは、通常、長さ２バイトであり、０（チェックサムなし）または１の補数の和の１６ビットの１の補数のいずれかである。このＤｙｎａ−ＢＩＮＤプロトコルの実施例では、シーケンス番号に対する初期値は、ランダムに選択され、その後、送信されるメッセージ毎に１だけ増分され、最大値に達するとロール・オーバーされる。メッセージ型および形式の実施例が与えられるが、Ｄｙｎａ−ＢＩＮＤプロトコルの他の実施形態も考えられる（例えば、ソース・ルーティングの代わりにスパニング・ツリーとのブリッジングの使用）。
【００５７】
ＦＥ発信メッセージ
図１５は、近隣要素ｈｅｌｌｏメッセージのレイアウト実施例を示している。近隣要素ｈｅｌｌｏメッセージは、すべてのインターフェイス上で定期的に、ｔｄｉｓｃｏｖｅｒ秒に１回、それぞれのＦＥおよびＣＥによりブロードキャストされる。それぞれのメッセージは、ＦＥＩＤまたはＣＥＩＤを含む。このメッセージは、Ｄｙｎａ−ＢＩＮＤプロトコルのこの実施例では必須であり、リンク／インターフェイス・ステータスをチェックするために使用される。ｔｄｉｓｃｏｖｅｒ＜ｔｓｏｌｉｃｉｔ秒であることが推奨される。近隣要素ｈｅｌｌｏメッセージのこのレイアウト実施例では、バージョン・フィールド１５００は０ｘ０１を保持し、型フィールド１５０２は０ｘ００を保持し、長さフィールド１５０４はメッセージ全体のバイト単位の長さ（１６ビット）を保持し、チェックサム・フィールド１５０６は０または１の補数の和の１６ビットの１の補数（１６ビット）を保持し、予約フィールド１５０８は将来使用するフィールド（１６ビット）であり、ソースＦＥＩＤまたはＣＥＩＤフィールド１５１０はメッセージ発信ＦＥまたはＣＥを識別する一意的文字列（１２８ビット）を保持する。
【００５８】
図１６は、要請メッセージのレイアウト実施例を示している。要請メッセージは、すべてのインターフェイス上でそれぞれのＦＥにより、定期的に、ｔｓｏｌｉｃｉｔ秒毎に１回、送信される。要請の目的は、選択されたＣＥへの少なくとも１つのルートを見つけることである。それぞれのメッセージは、ＦＥを識別するのを手助けするオプションのレイヤ２またはレイヤ３識別子とともにＦＥＩＤを含む。さらに、ＦＥは、任意選択により、発見しようとするルートの終点である特定のＣＥまたはＣＥのグループを指定することができる。要請メッセージのこのレイアウト実施例では、バージョン・フィールド１６００は０ｘ０１を保持し、型フィールド１６０２は０ｘ０１を保持し、長さフィールド１６０４はメッセージ全体のバイト単位の長さ（１６ビット）を保持し、チェックサム・フィールド１６０６は０、または１の補数の和の１６ビットの１の補数（１６ビット）を保持し、予約フィールド１６０８は将来使用するフィールド（１６ビット）であり、要請ＦＥＩＤまたはＣＥＩＤフィールド  １６１０はメッセージ発信ＦＥを識別する一意的文字列（１２８ビット）を保持し、オプション長さフィールド１６１２は長さフィールドを含むオプションの長さ（１６ビット）を含み、オプション型フィールド１６１４は図６で定義され（８ビット）、オプション予約フィールドは将来使用するフィールド（８ビット）である。
【００５９】
図１７は、オプション型フィールド１６１４に対する型、長さ、値（ＴＬＶ）定義を示す。ＦＥがＴＬＶオプション値内にリストされているＣＥの集合に関連付けようとすることを意味する、型１の複数のＴＬＶがありうる。
【００６０】
要請メッセージは、さらに、異なるＣＥを発見するか、または所望のＣＥへの別ルートを発見するために関連付けを一時的に途絶する場合にも使用される。このオプションが使用される場合、メッセージは、ＦＥに最後に関連付けられたＣＥに関連する識別子およびそのＣＥと接触するために使用されるソース・ルートを含む。
【００６１】
図１８は、到達可能性メッセージのレイアウト実施例を示している。到達可能性メッセージは、近隣ＦＥからの要請メッセージに対する応答としてＦＥにより送出される。到達可能性メッセージは、既定により、ＦＥのＣＥテーブルを含む。要請メッセージのこのレイアウト実施例では、バージョン・フィールド１８００は０ｘ０１を保持し、型フィールド１８０２は０ｘ０２を保持し、長さフィールド１８０４はメッセージ全体のバイト単位の長さ（１６ビット）を保持し、チェックサム・フィールド１８０６は０、または１の補数の和の１６ビットの１の補数（１６ビット）を保持し、予約フィールド１８０８は１６ビットであり、ソースＦＥＩＤ  １８１０はメッセージ発信ＦＥを識別する一意的文字列（１２８ビット）を保持し、エントリ長さフィールド１８１２はバイト単位の長さフィールドを含むエントリの長さ（１６ビット）を保持し、エントリ寿命フィールド１８１４はエントリが期限切れになるまでの秒数（１６ビット）を保持し、エントリＣＥＩＤフィールド１８１６はこのエントリがソース・ルートを伝播するＣＥＩＤ（１２８ビット）を保持し、エントリ・ソース・ルート要素フィールド１８１８はソース・リスト内の要素の個数（３２ビット）を保持し、エントリ・ソース・ルート・フィールド１８２０はエントリＣＥから近隣ＦＥまでの経路を識別するＦＥＩＤのリスト（１２８ビットの倍数）を保持し、このリスト内の最初のＦＥＩＤはＣＥの次のホップである。
【００６２】
図１９は、関連付け要求メッセージのレイアウト実施例を示している。関連付け要求メッセージは、与えられたＣＥとの関連付けを要求するためにＦＥにより送信される。メッセージは、ターゲットＣＥＩＤ、ＦＥＩＤ、およびＦＥからＣＥへのメッセージの経路を指定するソース・ルートを含む。ソース・ルートは、発信ＦＥＩＤから始まる、ＦＥＩＤのシーケンスとして指定される。要求を送信してからｔａｓｓｏｃｉａｔｅ秒以内に応答が受信されない場合、ＦＥは、ｒａｓｓｏｃｉａｔｅ回再試行し、その後、ＣＥをＣＥテーブルから消去し、ＣＥテーブル内の次のＣＥとの接触を試みる。テーブルの終わりに達した場合、ＦＥは再びＣＥテーブルの先頭から開始する。このレイアウト実施例では、バージョン・フィールド１９００は０ｘ０１を保持し、型フィールド１９０２は０ｘ０４を保持し、長さフィールド１９０４はメッセージ全体のバイト単位のメッセージ長（１６ビット）を保持し、チェックサム・フィールド１９０６は０、または１の補数の和の１６ビットの１の補数（１６ビット）を保持し、シーケンス番号フィールド１９０８はシーケンス番号（１６ビット）を保持し、ソースＦＥＩＤフィールド１９１０はメッセージ発信ＦＥを識別する一意的文字列（１２８ビット）を保持し、デスティネーションＣＥＩＤフィールド１９１２はＦＥが関連付けたいＣＥＩＤ（１２８ビット）を保持し、ソース・ルート要素フィールド１９１４はソース・ルート・リスト内の要素の個数（３２ビット）を保持し、ソース・ルート・フィールド１９１６はＦＥからＣＥへの経路を識別するＦＥＩＤのリスト（１２８ビットの倍数）を保持し、リスト内の最初のＦＥＩＤは送信側ＦＥの次のホップであり、アドレス型フィールド１９１８はＩＰなどのレイヤ３プロトコル型を保持し、アドレス値フィールド１９２０はＣＥの上層プロトコルで発見プロトコルを介してＦＥとのメッセージ交換に使用できるＦＥレイヤ３アドレスを保持する。
【００６３】
図２０は、構成要求メッセージのレイアウト実施例を示している。構成要求メッセージは、ＣＥからの関連付け受理メッセージを正常に受信したことに対する応答としてＦＥにより送信される。構成要求は、ＦＥからＣＥへのローカル構成および機能について記述する。要求を送信してからｔａｓｓｏｃｉａｔｅ秒以内に応答が受信されない場合、ＦＥはタイムアウトになり、ｒｃｏｎｆｉｇｕｒｅ回再試行し、その後、関連付け要求メッセージを次のＣＥに送信する。ＣＥテーブルの終わりに達した場合、ＦＥは再びＣＥテーブルの先頭から開始する。このレイアウト実施例では、バージョン・フィールド２０００は０ｘ０１を保持し、型フィールド２００２は０ｘ０７を保持し、長さフィールド２００４はメッセージ全体のバイト単位のメッセージ長（１６ビット）を保持し、チェックサム・フィールド２００６は０、または１の補数の和の１６ビットの１の補数（１６ビット）を保持し、シーケンス番号フィールド２００８はシーケンス番号（１６ビット）を保持し、ソースＦＥＩＤフィールド２０１０はメッセージ発信ＦＥを識別する一意的文字列（１２８ビット）を保持し、デスティネーションＣＥＩＤフィールド２０１２はＦＥが関連付けたいＣＥＩＤ（１２８ビット）を保持し、ソース・ルート要素フィールド２０１４はソース・ルート・リスト内の要素の個数（３２ビット）を保持し、ソース・ルート・フィールド２０１６はＦＥからＣＥへの経路を識別するＦＥＩＤのリスト（１２８ビットの倍数）を保持し、リスト内の最初のＦＥＩＤは送信側ＦＥの次のホップである。機能データ・フィールド２０１８は、将来使用されるフィールドである。
【００６４】
図２１は、ハートビート・メッセージのレイアウト実施例を示している。ハートビート・メッセージは、ＦＥにより送信され、管理側ＣＥにより受信確認される定期的メッセージである。メッセージは、ｔｈｅａｒｔｂｅａｔ秒毎に１回送出される。ＦＥからのハートビート・メッセージは、増加するシーケンス番号を持つ。このレイアウト実施例では、バージョン・フィールド２１００は０ｘ０１を保持し、型フィールド２１０２は０ｘ０Ａを保持し、長さフィールド２１０４はメッセージ全体のバイト単位のメッセージ長（１６ビット）を保持し、チェックサム・フィールド２１０６は０、または１の補数の和の１６ビットの１の補数（１６ビット）を保持し、シーケンス番号フィールド２１０８はシーケンス番号（１６ビット）を保持し、ソースＣＥＩＤフィールド２１１０はメッセージ発信ＣＥを識別する一意的文字列（１２８ビット）を保持し、デスティネーションＦＥＩＤフィールド２１１２はＣＥが関連付けたいＦＥＩＤ（１２８ビット）を保持し、ソース・ルータ・フィールド２１１４はＣＥからＦＥへの経路を識別するＦＥＩＤのリスト（１２８ビットの倍数）を保持し、リスト内の最初のＦＥＩＤは送信側ＣＥの次のホップである。
【００６５】
ＣＥ発信メッセージ
ＣＥ発信メッセージには、ＣＥ広告、関連付け受理、ＣＥ関連付け再ルーティング、構成応答、およびハートビート受信確認の５つがある。
図２２は、広告メッセージのレイアウト実施例を示している。広告メッセージは、近隣要素からの要請メッセージに対する応答としてＣＥにより送信される。広告メッセージは、ＣＥのＣＥＩＤを含む。このレイアウト実施例では、バージョン・フィールド２２００は０ｘ０１を保持し、型フィールド２２０２は０ｘ０３を保持し、長さフィールド２２０４はメッセージ全体のバイト単位のメッセージ長（１６ビット）を保持し、チェックサム・フィールド２２０６は０、または１の補数の和の１６ビット補数（１６ビット）を保持し、予約フィールド２２０８は将来使用するフィールド（１６ビット）であり、ソースＣＥＩＤフィールド２２１０はＣＥを識別する一意的文字列（１２８ビット）を保持し、エントリ長さフィールド２２１２は長さフィールドを含むエントリの長さ（１６ビット）を保持し、エントリ寿命フィールド２２１４はエントリが期限切れになるまでの秒数単位の時間（１６ビット）を保持し、エントリＣＥＩＤフィールド２２１６は広告されたＣＥのＣＥＩＤ（１２８ビット）を保持する。広告メッセージは、到達可能メッセージに類似しているが、ただし、ＣＥテーブルはエントリを１つしか持たず、ソース・ルートが存在しない（つまり、長さ０のソース・ルート）。
【００６６】
図２３は、関連付け受理メッセージのレイアウト実施例を示している。関連付け受理メッセージは、ときには、ＦＥからの関連付け要求メッセージに対する応答としてＣＥにより送信される。ＣＥが要求側ＦＥを構成することを許可されているか、または構成できる場合、ＣＥは、ＦＥからの関連付け要求メッセージ内のソース・ルートを逆にすることにより決定されるソース・ルートを使用してこのメッセージを送信することにより要求を受理する。このレイアウト実施例では、バージョン・フィールド２３００は０ｘ０１を保持し、型フィールド２３０２は０ｘ０５を保持し、長さフィールド２３０４はメッセージ全体のバイト単位のメッセージ長（１６ビット）を保持し、チェックサム・フィールド２３０６は０、または１の補数の和の１の補数（１６ビット）を保持し、シーケンス番号フィールド２３０８はシーケンス番号（１６ビット）を保持し、ソースＣＥＩＤフィールド２３１０はメッセージ発信ＣＥを識別する一意的文字列（１２８ビット）を保持し、デスティネーションＦＥＩＤフィールド２３１２はこのメッセージのアドレス指定先のＦＥのＦＥＩＤ（１２８ビット）を保持し、ソース・ルート要素フィールド２３１４はソース・ルート・リスト内の要素の個数（３２ビット）を保持し、ソース・ルート・フィールド２３１６はＣＥからＦＥへの経路を識別するＦＥＩＤのリスト（１２８ビットの倍数）を保持し、リスト内の最初のＦＥＩＤは送信側ＣＥの次のホップであり、アドレス型フィールド２３１８はＩＰなどのレイヤ３プロトコル型を保持し、アドレス値フィールド２３２０はＣＥの上層プロトコルで発見プロトコルを介してＦＥとのメッセージ交換に使用できるＣＥレイヤ３アドレスを保持する。
【００６７】
図２４は、関連付け拒絶メッセージのレイアウト実施例を示している。関連付け拒絶メッセージは、ＦＥからの関連付け要求メッセージに対する応答としてＣＥにより送信される。ＣＥがＦＥを構成することができないか、または構成するつもりがない場合、このメッセージを送信できる。このメッセージは、任意選択により、ＦＥを構成することができる代替えＣＥのＣＥＩＤを指定する。このレイアウト実施例では、バージョン・フィールド２４００は０ｘ０１を保持し、型フィールド２４０２は０ｘ０６を保持し、長さフィールド２４０４はメッセージ全体のバイト単位のメッセージ長（１６ビット）を保持し、チェックサム・フィールド２４０６は０、または１の補数の和の１６ビットの１の補数（１６ビット）を保持し、シーケンス番号フィールド２４０８はシーケンス番号（１６ビット）を保持し、ソースＦＥＩＤフィールド２４１０はメッセージ発信ＣＥを識別する一意的文字列（１２８ビット）を保持し、デスティネーションＣＥＩＤフィールド２４１２はこのメッセージのアドレス指定先であるＦＥのＣＥＩＤ（１２８ビット）を保持し、ＣＥＩＤリスト要素フィールド２４１８はＣＥＩＤリスト内の要素の個数（３２ビット）を保持し、ＣＥＩＤリスト・フィールド２４２０は要求側ＦＥを管理する代替えＣＥを定義するＣＥＩＤのリスト（１２８ビットの倍数）を保持し、ソース・ルート要素フィールド２４１４はソース・ルート・リスト内の要素の個数（３２ビット）を保持し、ソース・ルート・フィールド２４１６はＣＥからＦＥへの経路を識別するＦＥＩＤのリスト（１２８ビットの倍数）を保持し、リスト内の最初のＦＥＩＤは送信側ＣＥの次のホップである。
【００６８】
図２５は、構成応答メッセージのレイアウト実施例を示している。構成応答メッセージは、ＦＥからの有効な構成要求メッセージに対する応答として送信される。このメッセージは、ＦＥを構成するための情報を供給する。このレイアウト実施例では、バージョン・フィールド２５００は０ｘ０１を保持し、型フィールド２５０２は０ｘ０８を保持し、長さフィールド２５０４はメッセージ全体のバイト単位のメッセージ長（１６ビット）を保持し、チェックサム・フィールド２５０６は０、または１の補数の和の１６ビットの１の補数（１６ビット）を保持し、シーケンス番号フィールド２５０８はシーケンス番号（１６ビット）を保持し、ソースＣＥＩＤフィールド２５１０はメッセージ発信ＣＥを識別する一意的文字列（１２８ビット）を保持し、デスティネーションＦＥＩＤフィールド２５１２はこのメッセージのアドレス指定先であるＦＥのＦＥＩＤ（１２８ビット）を保持し、ソース・ルート要素フィールド２５１４はソース・ルート・リスト内の要素の個数（３２ビット）を保持し、ソース・ルート・フィールド２５１６はＣＥからＦＥへの経路を識別するＦＥＩＤのリスト（１２８ビットの倍数）を保持し、リスト内の最初のＦＥＩＤは送信側ＣＥの次のホップである。
【００６９】
図２６は、ハートビート受信確認メッセージのレイアウト実施例を示している。ハートビート受信確認メッセージは、ハートビート・メッセージの受信確認をし、管理側ＣＥにより送信される。メッセージは、受信確認されるハートビート・メッセージのシーケンス番号を含む。このレイアウト実施例では、バージョン・フィールド２６００は０ｘ０１を保持し、型フィールド２６０２は０ｘ０Ａを保持し、長さフィールド２６０４はメッセージ全体のバイト単位のメッセージ長（１６ビット）を保持し、チェックサム・フィールド２６０６は０、または１の補数の和の１６ビットの１の補数（１６ビット）を保持し、シーケンス番号フィールド２６０８はシーケンス番号（１６ビット）を保持し、ソースＣＥＩＤフィールド２６１０はメッセージ発信ＣＥを識別する一意的文字列（１２８ビット）を保持し、デスティネーションＦＥＩＤフィールド２６１２はＣＥ側で受信確認したいＦＥＩＤ（１２８ビット）を保持し、ソース・ルート・フィールド２６１４はＦＥからＣＥへの経路を識別するＦＥＩＤのリスト（１２８ビットの倍数）を保持し、リスト内の最初のＦＥＩＤは送信側ＦＥの次のホップである。
【００７０】
Ｄｙｎａ−ＢＩＮＤプロトコルの状態機械
Ｄｙｎａ−ＢＩＮＤプロトコル用の状態機械の実施例の一実施形態がある。この状態機械は、さまざまな状態、保持される変数およびテーブル、およびＤｙｎａ−ＢＩＮＤプロトコルの一実施形態を実行するネットワークの要素に関連付けられた状態遷移を含む。
【００７１】
図２７は、ＦＥ状態遷移の例を示している。状態機械の実施例のこの実施形態でＦＥに関連付けられている状態は、１）収集２７００、２）一次の関連付け試行２７０２、３）一次の構成試行２７０４、４）一次のアクティベート試行２７０６、５）一次アップ（図に示されていない）、６）一次アクティブ２７０８、７）バックアップのアクティベート試行２７１０、８）バックアップ・アップ（図に示されていない）、９）バックアップ・アクティブ２７１２の９つある。
【００７２】
ブートした後、ＦＥは、近隣要素の近接を確立し、ＣＥおよびそのソース・ルートについて近隣要素に要請しながら、ｔｃｏｌｌｅｃｔ秒間、収集状態２７００のままである。
一次の関連付け試行状態２７０２で、ＦＥは、ＣＥテーブルを反復し、一次ＣＥの関連付けを試行し、応答を待つ。タイムアウト・イベント（つまり、期間ｔａｓｓｏｃｉａｔｅ以内に、およびｒａｓｓｏｃｉａｔｅ回の再試行後に応答がない）が発生した場合、ＦＥはＣＥテーブル内の次のＣＥとの関連付けを試行する。
【００７３】
一次構成の試行状態２７０４で、ＦＥは、構成要求メッセージを送信し、応答を待つ。イベント・タイムアウト（つまり、期間ｔｃｏｎｆｉｇｕｒｅ以内に応答がない）または一次無効（つまり、ハートビートが失敗）が発生した場合、ＦＥはＣＥテーブル内の次のＣＥとの関連付けを試行する。
【００７４】
一次アクティベートの試行状態２７０６で、ＦＥは、アクティベート要求メッセージを送信し、応答を待つ。イベント・タイムアウト（つまり、期間ｔａｃｔｉｖａｔｅ以内に、およびｒａｓｓｏｃｉａｔｅ回の再試行後に応答がない）、または一次無効（ハートビートが失敗した）が発生した場合、ＦＥはＣＥテーブル内の次のＣＥとの関連付けを試行する。
【００７５】
一次アップ状態では、ＦＥは、バックアップＣＥを関連付ける関連付け要求メッセージを送信し、応答を待つ。イベント・タイムアウト（つまり、期間ｔａｓｓｏｃｉａｔｅ以内に、およびｒａｓｓｏｃｉａｔｅ回の再試行後に応答がない）が発生した場合、ＦＥは一次アップ状態のままである。イベントＣＥ学習が発生した場合、新しい関連付け要求メッセージが送信される。一次無効イベントが発生した場合、ＦＥは、ＣＥテーブル内の次のＣＥとの関連付けを試行する。
【００７６】
一次アクティブ状態２７０８で、一次およびバックアップＣＥは関連付けられ、一次ＣＥは管理側ＣＥ（アクティベートされている）である。イベント・バックアップ無効（つまり、バックアップＣＥへのハートビート・タイムアウト）が受信されると、ＦＥは、新しいバックアップＣＥとの関連付けを試行する。イベント一次無効（つまり、一次ＣＥへのハートビート・タイムアウト）が発生した場合、ＦＥは、バックアップＣＥをアクティベートし、新しい一次ＣＥとの関連付けを試行する。
【００７７】
バックアップ・アクティベートの試行状態２７１０で、ＦＥは、アクティベート要求メッセージを送信し、応答を待つ。イベント・タイムアウト（つまり、期間ｔａｃｔｉｖａｔｅ以内に、およびｒａｃｔｉｖａｔｅ回の再試行後に応答がない）、またはバックアップ無効（つまり、ハートビートが失敗する）が発生した場合、ＦＥはＣＥテーブル内の次のＣＥとの関連付けを試行する。
【００７８】
バックアップ・アップ状態では、ＦＥは、一次ＣＥを関連付ける関連付け要求メッセージを送信し、応答を待つ。イベント・タイムアウト（つまり、期間ｔａｓｓｏｃｉａｔｅ以内に、およびｒａｓｓｏｃｉａｔｅ回の再試行後に応答がない）が発生した場合、ＦＥはこの状態のままである。イベントＣＥ学習が発生した場合、新しい関連付け要求メッセージが送信される。バックアップ無効イベントが発生した場合、ＦＥは、ＣＥテーブル内の次のＣＥとの関連付けを試行する。
【００７９】
バックアップ・アクティブ状態２７１２で、一次およびバックアップＣＥは関連付けられ、バックアップＣＥは管理側ＣＥ（アクティベートされている）である。イベント一次無効（つまり、一次ＣＥへのハートビート・タイムアウト）が受信されると、ＦＥは、新しい一次ＣＥとの関連付けを試行する。イベント・バックアップ無効（つまり、バックアップＣＥへのハートビート・タイムアウト）が発生した場合、ＦＥは、一次ＣＥをアクティベートし、新しいバックアップＣＥとの関連付けを試行する。
【００８０】
状態機械の実施例のこの実施形態でＦＥに関連付けられているイベントは、１）収集期限切れ２７１４、２）一次無効２７１６、３）バックアップ無効２７１８、４）タイムアウト２７２０、５）ＣＥ学習（図に示されていない）、６）関連付け応答受信２７２２、７）構成応答受信２７２４、および８）アクティベート応答受信２７２６の８つある。収集期限切れ２７１４は、収集状態でのＣＥ収集期間ｗｃｏｌｌｅｃｔの終わりを示す。一次無効２７１６は、一次ＣＥへのハートビートがタイムアウトになったことを示す。バックアップ無効２７１８は、バックアップＣＥへのハートビートがタイムアウトになったことを示す。タイムアウト２７２０は、送信された要求への応答が受信されなかったことを示す。ＣＥ学習は、新しいＣＥがＣＥテーブルに追加されたことを示す。関連付け応答受信２７２２は、関連付け応答メッセージが受信されたことを示す。構成応答受信２７２４は、構成応答メッセージが受信されたことを示す。アクティベート応答受信２７２６は、アクティベート応答メッセージが受信されたことを示す。
【００８１】
状態機械の実施例のこの実施形態ではＦＥに関連付けられている変数として、近隣要素テーブルおよびＣＥテーブルの２つがある。近隣要素テーブルは、ＦＥおよびＣＥで保持されるローカルの近傍データベースである。近隣要素テーブルには、隣接するＦＥおよびＣＥに関する情報が格納され、ローカル・インターフェイスではこれを使用してＦＥおよびＣＥに到達する。近隣要素は、送信者側のＣＥＩＤまたはＦＥＩＤを供給する、ｈｅｌｌｏメッセージの受信を通じて発見される。ｈｅｌｌｏメッセージは、すべてのＤｙｎａ−ＢＩＮＤ対応インターフェイス上で、ｔｄｉｓｃｏｖｅｒ秒毎に定期的に、ＣＥおよびＦＥによりブロードキャストされる。それぞれの近隣要素テーブル・エントリは、要請メッセージが受信されると必ずリセットされる寿命値を持つ。ｗｄｉｓｃｏｖｅｒ＊ｔｄｉｓｃｏｖｅｒ秒以内にｈｅｌｌｏメッセージが受信されない場合、近接が削除される。ＣＥテーブルは、ＦＥ側に保持され、ＣＥの集合およびＦＥからそれらのＣＥへのルートを含む。ＦＥが広告または到達可能性メッセージのいずれかを受信すると、ＣＥテーブルが書き込まれる。ＣＥテーブル内のそれぞれのエントリは、（＜ＣＥＩＤ＞，＜寿命＞，＜ソース・ルート＞）の形を取る。広告メッセージからのエントリは、（＜ＣＥｌＤ＞，ｔｅｘｐｉｒｙ，ＦＥＩＤ→ＣＥＩＤ）として入力される。
【００８２】
図２８は、関連づけを試みるそれぞれのＦＥについてトラバースされる、ＣＥ状態遷移図の実施例である。状態機械の実施例のこの実施形態では、ＣＥに関連付けられる状態は、１）関連付け待機２８００、２）構成待機２８０２、３）アクティベーション待機２８０４、および４）アップ２８０６の４つがある。
【００８３】
関連付け待機状態２８００では、ＣＥはアイドル状態である。ＦＥ構成データは、知られているが、接触は確立されない。関連付け要求メッセージが受信された場合、応答が送信され、状態は構成待機に遷移する。
【００８４】
構成待機状態２８０２では、ＦＥは関連付けられる。構成要求メッセージが受信された場合、応答が送信され、状態はアクティベーション待機状態に進む。構成待機状態は、スキップすることができる。アクティベーション要求イベントが受信された場合、状態は受信されたアクティベーション・イベントとともにアクティベーション待機に遷移する。関連付け要求イベントが受信された場合、ＦＥはＣＥにより気づかれないままリブートしており（ハートビート・タイムアウト）、状態は関連付け要求イベントとともに関連付け待機状態に遷移して戻る。イベント・ハートビート・タイムアウトが発生した場合、ＦＥへの経路またはＦＥ自体が失敗しており、状態は関連付け待機状態に遷移して戻る。
【００８５】
アクティベーション待機状態２８０４では、アクティベーション要求イベントが受信された場合、応答が送信され、状態はアップ状態に進む。関連付け要求イベントが受信された場合、ＦＥはＣＥにより気づかれないままリブートしており（ハートビート・タイムアウト）、状態は関連付け要求イベントとともに関連付け待機状態に遷移して戻る。イベント・ハートビート・タイムアウトが発生した場合、ＦＥへの経路またはＦＥ自体が失敗しており、状態は関連付け待機状態に遷移して戻る。
【００８６】
アップ状態２８０６では、ＦＥはアップ、運用状態であり、ＣＥにより管理されている。関連付け要求イベントが受信された場合、ＦＥはＣＥにより気づかれないままリブートしており（ハートビート・タイムアウト）、状態は関連付け要求イベントとともに関連付け待機状態に遷移して戻る。イベント・ハートビート・タイムアウトが発生した場合、ＦＥへの経路またはＦＥ自体が失敗しており、状態は関連付け待機状態に遷移して戻る。
【００８７】
状態機械の実施例のこの実施形態では、ＣＥに関連付けられているイベントは、１）関連付け要求受信２８０８、２）関連付け応答送信２８１０、３）構成要求受信（図に示されていない）、４）構成応答送信２８１２、５）アクティベーション要求受信２８１４、６）アクティベーション応答送信２８１６、および７）ハートビート・タイムアウト２８１８の７つがある。関連付け要求受信２８０８は、関連付け要求メッセージが受信されたことを示す。関連付け応答送信２８１０は、関連付け応答メッセージが送信されたことを示す。構成要求受信は、構成要求メッセージが受信されたことを示す。構成応答送信２８１２は、構成応答メッセージが送信されたことを示す。アクティベーション要求受信２８１４は、アクティベーション要求メッセージが受信されたことを示す。アクティベーション応答送信２８１６は、アクティベーション応答メッセージが送信されたことを示す。ハートビート・タイムアウト２８１８は、ハートビート要求メッセージが時間内に受信されなかったため、ハートビート・タイムアウトが発生したことを示す。
【００８８】
状態機械の実施例のこの実施形態ではＣＥに関連付けられている変数として、近隣要素テーブルおよびＦＥテーブルの２つがある。近隣要素テーブルについては上で説明されている。ＦＥテーブルは、ＣＥ側に保持され、ＣＥが制御することができるＦＥのリストとなっている。ＦＥテーブルは、構成データを通じて値を入れられる。テーブル・エントリは、対応するＦＥがＣＥに関連付けられている場合に関連付けられた状態に到達する。テーブル・エントリは、対応するＦＥがＣＥをアクティベートした場合にアクティベート状態に到達する。テーブル・エントリは、ｔｈｅａｒｔｂｅａｔ秒おきに受信されたすべてのハートビート・メッセージで更新される、関連付けられ、アクティベートされた状態で有効なソース・ルートを持つ。ハートビート・メッセージがｗｐａｔｈ＊ｔｈｅａｒｔｂｅａｔ秒の間受信されなかった場合、そのテーブル・エントリは無効ソース・ルート表示とともに非関連付け状態に移行される。
【００８９】
図２９は、コンピュータを示す高水準のブロック図である。コンピュータ２９００を採用して、本発明のいくつかの実施形態を実装できる。コンピュータ２９００は、プロセッサ２９３０とともに、さまざまなプログラム２９４４およびデータ２９４６を格納するためのメモリ２９４０を備える。メモリ２９４０は、さらに、プログラム２９４４をサポートするオペレーティング・システム２９４２を格納することもできる。
【００９０】
プロセッサ２９３０は、電源、クロック回路、キャッシュ・メモリなどの従来のサポート回路とともに、メモリ２９４０に格納されているソフトウェア・ルーチンの実行を補助する回路と連携する。したがって、本明細書でソフトウェア方法として説明される工程のいくつかは、ハードウェア内に、例えば、プロセッサ２９３０と連携してさまざまな方法工程を実行する回路として実装することができる。コンピュータ２９００は、さらに、コンピュータ２９００と通信するさまざまな機能要素間のインターフェイスを形成する入出力（Ｉ／Ｏ）回路も備える。
【００９１】
コンピュータ２９００は、本発明によりさまざま機能を実行するようにプログラムされた汎用コンピュータとして示されているが、本発明は、ハードウェアで、例えば、特定用途向け集積回路（ＡＳＩＣ）またはフィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）として実装することができる。したがって、本明細書で説明されている工程段階は、ソフトウェア、ハードウェア、またはそれらの組み合わせにより等しく実行されるものとして広く解釈することを意図されている。
【００９２】
本発明は、コンピュータ命令がコンピュータにより処理されると、本発明に方法および／または技術が呼び出されるか、または何らかの方法により提供されるようにコンピュータの動作を適合させるコンピュータ・プログラム製品として実装することができる。本発明の方法を呼び出す命令は、固定または取り外し可能媒体に格納するか、放送媒体または他の信号伝送媒体でデータストリームを介して送信するか、および／または命令に従って動作するコンピューティング・デバイス内の作業用メモリ内に格納することができる。
【００９３】
前記の説明は本発明のさまざまな実施形態を対象としているが、本発明の基本的範囲から逸脱することなく本発明の他の実施形態およびさらなる実施形態を考案することができる。したがって、本発明の適切な範囲は、請求項により決定されるものとする。
【図面の簡単な説明】
【００９４】
【図１】さらに多くの機能をＩＰに追いやる新たに出現するアプリケーションの問題を例示する図である。
【図２】従来のルータを示すブロック図である。
【図３】ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例の高水準抽象化を示すブロック図である。
【図４】従来のルータ・アーキテクチャを示すブロック図である。
【図５】ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例の実施形態を示すブロック図である。
【図６】ネットワーク要素を例示するＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例の実施形態を示すブロック図である。
【図７】発見、関連付け、および運用の並列実行される３つのタスクを持つ、動的バインディング・プロトコルの実施例の一実施形態を示す図である。
【図８】動的バインディング構造例の一実施形態を示す図である。
【図９】動的バインディング・プロトコルの実施例の一実施形態による、近隣要素発見の発見タスクを示す図である。
【図１０】動的バインディング・プロトコルの実施例の一実施形態による、ＣＥ広告の発見タスクを示す図である。
【図１１】動的バインディング・プロトコルの実施例の一実施形態による、関連付けタスクを示す図である。
【図１２】動的バインディング・プロトコルの実施例の一実施形態による、構成タスクを示す図である。
【図１３】動的バインディング・プロトコルの実施例の一実施形態による、フェイルオーバーの運用タスクを示す図である。
【図１４】動的バインディング・プロトコルの実施例の一実施形態による、トランスポートの運用タスクを示す図である。
【図１５】近隣要素ｈｅｌｌｏメッセージのレイアウト実施例を示す図である。
【図１６】要請メッセージのレイアウト実施例を示す図である。
【図１７】オプション型フィールドに対する型、長さ、値（ＴＬＶ）定義を示す表である。
【図１８】到達可能性メッセージのレイアウト実施例を示す図である。
【図１９】関連付け要求メッセージのレイアウト実施例を示す図である。
【図２０】構成要求メッセージのレイアウト実施例を示す図である。
【図２１】ハートビート・メッセージのレイアウト実施例を示す図である。
【図２２】広告メッセージのレイアウト実施例を示す図である。
【図２３】関連付け受理メッセージのレイアウト実施例を示す図である。
【図２４】関連付け拒絶メッセージのレイアウト実施例を示す図である。
【図２５】構成応答メッセージのレイアウト実施例を示す図である。
【図２６】ハートビート受信確認メッセージのレイアウト実施例を示す図である。
【図２７】ＦＥ状態遷移の例を示す図である。
【図２８】ＦＥ毎のＣＥ状態遷移の例を示す図である。
【図２９】コンピュータを示す高水準のブロック図である。
【図１】
2006135970.tif 000003
【図２】
2006135970.tif 000004
【図３】
2006135970.tif 000005
【図４】
2006135970.tif 000006
【図５】
2006135970.tif 000007
【図６】
2006135970.tif 000008
【図７】
2006135970.tif 000009
【図８】
2006135970.tif 000010
【図９】
2006135970.tif 000011
【図１０】
2006135970.tif 000012
【図１１】
2006135970.tif 000013
【図１２】
2006135970.tif 000014
【図１３】
2006135970.tif 000015
【図１４】
2006135970.tif 000016
【図１５】
2006135970.tif 000017
【図１６】
2006135970.tif 000018
【図１７】
2006135970.tif 000019
【図１８】
2006135970.tif 000020
【図１９】
2006135970.tif 000021
【図２０】
2006135970.tif 000022
【図２１】
2006135970.tif 000023
【図２２】
2006135970.tif 000024
【図２３】
2006135970.tif 000025
【図２４】
2006135970.tif 000026
【図２５】
2006135970.tif 000027
【図２６】
2006135970.tif 000028
【図２７】
2006135970.tif 000029
【図２８】
2006135970.tif 000030
【図２９】
2006135970.tif 000031