(57)【要約】【課題】ルータの制御エンティティをその転送コンポーネントから分離することによりルータを  分解し、それらの間の動的バインディングを可能にするＳｏｆｔＲｏｕｔｅｒアーキテクチャを提供すること。【解決手段】ＳｏｆｔＲｏｕｔｅｒアーキテクチャでは、制御プレーン機能は、数ネットワーク・ホップだけ離れている転送要素を制御する少数のスマート・サーバ上に集約され、実装される。動的バインディング・プロトコルにより、ネットワーク規模の制御プレーンのフェイルオーバーを実行する。ネットワーク安定性は、ルーティング・プロトコルを集約し、リモートでホスティングすることにより改善される。この結果、収束が高速化され、処理されるプロトコル・メッセージが少なくなり、障害発生後のルート変更回数が減る。ＳｏｆｔＲｏｕｔｅｒアーキテクチャは、多数の転送要素４０６を管理し、ネットワーク規模の制御のサポートを強化するスマート制御エンティティ４０２、４０４を備える。【選択図】図１
2006135975.tif 000002
【特許請求の範囲】
【請求項１】
ネットワーク・アーキテクチャであって、
複数の転送要素（ＦＥ）を含む第１のＦＥ集合と、
第１のＦＥを制御する第１の制御要素（ＣＥ）であって、前記第１のＦＥ集合内のそれぞれのＦＥの代わりに１つの第１のプロトコル・プロセスを提供し、前記第１のＦＥ集合内の前記複数のＦＥから物理的に遠い位置にあり、前記第１のＦＥ集合内のそれぞれのＦＥに動的にバインドされる第１の制御要素（ＣＥ）と、
前記第１のＣＥおよび前記第１のＦＥ集合を含む第１のネットワーク要素（ＮＥ）とを含むネットワーク・アーキテクチャ。
【請求項２】
複数ＣＥは、前記第１のＮＥ内の前記第１のＦＥ集合を制御する請求項１に記載のネットワーク・アーキテクチャ。
【請求項３】
さらに、
前記第１のＦＥ集合内の複数のＦＥと異なる複数のＦＥを含む第２のＦＥ集合と、
前記第２のＦＥ集合を制御し、前記第２のＦＥ集合の代わりに１つの第２のプロトコル・プロセスを実行し、前記第２のＦＥ集合から物理的に遠い位置にある第２のＣＥと、
前記第２のＣＥおよび前記第２のＦＥ集合を含む第２のＮＥとを含む請求項１に記載のネットワーク・アーキテクチャ。
【請求項４】
前記単一プロトコル・プロセスは、前記第１のＮＥの前記複数のＦＥを管理し、前記第１のＮＥの前記複数のＦＥについてドメイン内ルートを計算する請求項３に記載のネットワーク・アーキテクチャ。
【請求項５】
前記内部リンクおよび前記内部リンクの重みは、近隣要素に広告される請求項４に記載のネットワーク・アーキテクチャ。
【請求項６】
ネットワーク・アーキテクチャであって、
複数の転送要素（ＦＥ）と、
複数の制御要素（ＣＥ）であって、それぞれのＣＥは前記他のＣＥと異なる、前記ＦＥの集合を制御し、前記複数のＦＥから物理的に遠い位置にある複数のＣＥと、
前記複数のＣＥの間の完全内部境界ゲートウェイ・プロトコル（Ｉ−ＢＧＰ）メッシュとを含み、
それぞれのＣＥは、プロトコルを使用してその制御される複数のＦＥと通信するネットワーク・アーキテクチャ。
【請求項７】
さらに、ドメイン内ルーティングおよびドメイン間ルーティングを含む請求項６に記載のネットワーク・アーキテクチャ。
【請求項８】
ネットワーク・アーキテクチャであって、
複数のコア・ルータと、
前記コア・ルータに接続されるコア・ネットワークと、
複数の転送要素（ＦＥ）と、
複数の制御要素（ＣＥ）であって、それぞれのＣＥは前記複数のＦＥのうちの複数を制御し、それぞれのＣＥはその制御される複数のＦＥに動的にバインドされ、それぞれのＣＥはその制御される複数のＦＥから物理的に遠い位置にあり、それぞれのＣＥは標準プロトコルを介してその制御される複数のＦＥと通信する複数のＣＥと、
前記コア・ルータにより前記複数のコア・ネットワークに接続され、前記複数のＣＥに接続され、前記複数のＦＥに接続されるＰｏｉｎｔ−Ｏｆ−Ｐｒｅｓｅｎｃｅ（ＰＯＰ）（登録商標）ネットワークとを含むネットワーク・アーキテクチャ。
【請求項９】
ネットワーク・アーキテクチャであって、
複数のＦＥであって、それぞれのＦＥはそのＦＥの代わりにプロトコル・プロセスを提供する少なくとも１つのＣＥにより制御可能である複数のＦＥを含み、
それぞれのＦＥは、前記ＣＥから物理的に遠い位置にあり、
それぞれのＦＥは、前記ＣＥに動的にバインドされるネットワーク・アーキテクチャ。
【請求項１０】
ネットワーク・アーキテクチャであって、
複数のＦＥを制御する、それぞれのＦＥの代わりにプロトコル・プロセスを提供するＣＥと、
それぞれのＦＥに前記ＣＥを動的にバインドする動的バインディング・プロトコルとを含み、
前記ＣＥは、前記ＦＥから物理的に遠い位置にあるネットワーク・アーキテクチャ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、２００４年１１月１日出願された「ＳｏｆｔＲｏｕｔｅｒ：Ｒｏｕｔｅｒ  Ｄｉｓａｇｇｒｅｇａｔｉｏｎ」という表題の仮出願第６０／６２３，８８５号（整理番号Ｌａｋｓｈｍａｎ  ３５−２−２３−６２−３１）の利益を主張するものである。さらに、本出願は、本出願と同じ日に出願された同時係属出願「ＳｏｆｔＲｏｕｔｅｒ」（整理番号Ｌａｋｓｈｍａｎ  ３５−２−２３−６２−３１（ＬＣＮＴ／１２６７７０））、「ＳｏｆｔＲｏｕｔｅｒ  Ｐｒｏｔｏｃｏｌ  Ｆａｉｌｏｖｅｒｓ」（整理番号Ａｎｓａｒｉ  ３−４２−４−２５−３５（ＬＣＮＴ／１２７３０６））、「ＳｏｆｔＲｏｕｔｅｒ  Ｓｅｐａｒａｔｅ  Ｃｏｎｔｒｏｌ  Ｎｅｔｗｏｒｋ」（整理番号Ｌａｋｓｈｍａｎ  ４３−６４−３６（ＬＣＮＴ／１２７３０７））、「ＳｏｆｔＲｏｕｔｅｒ  Ｆｅａｔｕｒｅ  Ｓｅｒｖｅｒ」（整理番号Ｌａｋｓｈｍａｎ  ４４−６５−３７（ＬＣＮＴ／１２７３０８））、「ＳｏｆｔＲｏｕｔｅｒ  Ｄｙｎａｍｉｃ  Ｂｉｎｄｉｎｇ  Ｐｒｏｔｏｃｏｌ」（整理番号Ａｎｓａｒｉ  ４−３−４５−５−２６−３８（ＬＣＮＴ／１２７３０９））に関係する。仮出願および関連出願は、すべて参照により本明細書に組み込まれる。
【０００２】
本発明は、一般に、ネットワーキングの分野に関するものであり、特に、 分解ルータ・ネットワークにおけるルーティング・プロトコルに関するものである。
【背景技術】
【０００３】
インターネットが非常に大きな成功を収めたことで、新しい機能およびサービスの開発および展開がひっきりなしに続き、次第にその技術的基盤では間に合わなくなってきた。これは、ＩＰネットワークにおける機能の現在の配分のアーキテクチャリングを変更すれば、ネットワークの安定性、ネットワーク運用の簡素化、および新しいネットワーク・プロトコルおよびサービスの柔軟な導入にとって著しく有益であろうとの考えに信憑性を与えた。
【０００４】
従来のルータ・アーキテクチャは複雑になりつつある。従来のルータ・アーキテクチャは、単純なコア・ネットワークを目指すエンドツーエンド・アーキテクチャ設計原理にもかかわらず、今日では、次第に複雑化してきている。新しい機能がＲＦＣ（Ｒｅｑｕｅｓｔｓ  Ｆｏｒ  Ｃｏｍｍｅｎｔｓ）で定義されるとともに、ルータには制御プレーンの複雑さがますます加わる。これらの機能は、ルーティング（例えば、ＢＧＰベースのＭＰＬＳ−ＶＰＮ）、トラフィック・エンジニアリング（例えば、ＯＳＰＦ−ＴＥ）、セキュリティなどを含む。実際、ＩＰルータのコード複雑度は、現在では、電話交換機のコード複雑度に匹敵している。それとは対照的に、大規模なハードウェア集積化（例えば、ＡＳＩＣ）が急速に進み、市販チップが入手しやすくなるにつれ、徐々に、転送パスの実装が容易になってきた。
【０００５】
従来のＩＰネットワークは、比較的自律的に動作するルータを使用して構築される。ネットワークのいたる所の多くの点に潜在的に管理しにくい複雑度が存在する。これは、多くの望ましくない帰結を導く。第１に、制御点が複数あると、運用の複雑さ（例えば、構成間違い設定）が著しく高まる。第２に、いくつかの特定の状況において、これらの自律的ルータの非協調アクションのため、せいぜい部分的に最適なパフォーマンス（例えば、回復時間が長い）にしかならず、最悪の場合にはネットワークが不安定になる可能性がある。最後に、新しい機能を導入するには、多数のルータへのアップグレードを必要とする場合があり、この作業は複雑であり、また間違いを犯しがちである。
【０００６】
ルーティング・ポリシー実施およびトラフィック・エンジニアリングなどの多くの高度なネットワーク管理タスクであれば、ネットワーク規模のビューを利用できることで著しい恩恵を受けるであろう。例えば、ＢＧＰによってネットワークの安定性および運用のいくつかの共通の問題が引き起こされる場合、それらの問題は、ＢＧＰを個々のルータから自律的システム（ＡＳ）規模のスコープを持つ単一エンティティに移動することにより解決されるであろう。同様に、多くの管理機能は、ネットワーク規模のビューを必要とし、それなしでは、ネットワークは振動と安定性の悪さを露呈しうる。しかし、ネットワーク規模の制御は、自律的で複雑なルータからなる今日のネットワークでは実行が困難であり、また厄介でもある。
【０００７】
従来のルータ・アーキテクチャでは、制御と転送を統合している。制御プレーン機能を実装する制御プロセッサは、転送機能を実装し、同じルータ・バックプレーンを共有することが多いライン・カードと同じ場所に配置される。制御プロセッサは、同じ場所に配置されているライン・カードにのみ制御機能を提供し、またその逆も同様であり、同じ場所に配置されている（複数の）コントローラに故障が生じた場合に、ライン・カードを管理できないようなシナリオに至る。
【０００８】
従来のルータ・アーキテクチャでは、基礎となるテーマは、現在のルータ制御および転送機能の深い相互の絡み合いである。これらの機能を縮小して、ごく少数の標準パケット転送機能のみをサポートし、すべての制御プロトコルおよび非転送関係状態および制御処理をネットワーク規模の制御の一次機能を持つ少数の高機能なネットワーク・ベースの制御エンティティに移行することにより、ルータの 分解を行いネットワーク・エンティティの大半をできる限り黙らせる必要がある。
【特許文献１】仮出願第６０／６２３，８８５号
【特許文献２】同時係属出願「ＳｏｆｔＲｏｕｔｅｒ」（整理番号Ｌａｋｓｈｍａｎ  ３５−２−２３−６２−３１（ＬＣＮＴ／１２６７７０））
【特許文献３】同時係属出願「ＳｏｆｔＲｏｕｔｅｒ  Ｐｒｏｔｏｃｏｌ  Ｆａｉｌｏｖｅｒｓ」（整理番号Ａｎｓａｒｉ  ３−４２−４−２５−３５（ＬＣＮＴ／１２７３０６））
【特許文献４】同時係属出願「ＳｏｆｔＲｏｕｔｅｒ  Ｓｅｐａｒａｔｅ  Ｃｏｎｔｒｏｌ  Ｎｅｔｗｏｒｋ」（整理番号Ｌａｋｓｈｍａｎ  ４３−６４−３６（ＬＣＮＴ／１２７３０７））
【特許文献５】同時係属出願「ＳｏｆｔＲｏｕｔｅｒ  Ｆｅａｔｕｒｅ  Ｓｅｒｖｅｒ」（整理番号Ｌａｋｓｈｍａｎ  ４４−６５−３７（ＬＣＮＴ／１２７３０８））
【特許文献６】同時係属出願「ＳｏｆｔＲｏｕｔｅｒ  Ｄｙｎａｍｉｃ  Ｂｉｎｄｉｎｇ  Ｐｒｏｔｏｃｏｌ」（整理番号Ａｎｓａｒｉ  ４−３−４５−５−２６−３８（ＬＣＮＴ／１２７３０９））
【発明の開示】
【発明が解決しようとする課題】
【０００９】
従来技術のさまざまな欠点は、多くの実施形態を持つＳｏｆｔＲｏｕｔｅｒプロトコル分離の本発明により解決される。
【課題を解決するための手段】
【００１０】
一実施形態は、第１の転送要素（ＦＥ）集合、第１の制御要素（ＣＥ）、および第１のネットワーク要素（ＮＥ）を含むネットワーク・アーキテクチャである。第１のＦＥ集合は、多数のＦＥである。第１のＣＥは、第１のＦＥ集合を制御し、第１のＦＥ集合内のそれぞれのＦＥの代わりに一方の第１のプロトコル・プロセスを実行する。第１のＣＥは、第１のＦＥ集合内のＦＥから物理的に遠い位置にある。第１のＣＥは、第１のＦＥ集合内のそれぞれのＦＥに動的にバインドされる。第１のＮＥは、第１のＣＥおよび第１のＦＥ集合を含む。
【００１１】
他の実施形態は、多数のＦＥ、多数のＣＥ、およびＣＥ間の内部境界ゲートウェイ・プロトコル（Ｉ−ＢＧＰ）完全メッシュを含むネットワーク・アーキテクチャである。それぞれのＣＥは、他のＣＥ異なる、ＦＥの集合を制御する。ＣＥは、ＦＥから物理的に遠い位置にある。それぞれのＣＥは、標準プロトコルを使用してその制御されたＦＥと通信する。
【００１２】
さらに他の実施形態は、コア・ルータ、コア・ルータに接続されたコア・ネットワーク、転送要素（ＦＥ）、ＣＥ、およびＰＯＰ（Ｐｏｉｎｔ  Ｏｆ  Ｐｒｅｓｅｎｃｅ）Ｅｔｈｅｒｎｅｔ（登録商標）ネットワークを含む、ネットワーク・アーキテクチャである。それぞれのＣＥは、複数のＦＥを制御する。それぞれのＣＥは、制御されるＦＥに動的にバインドされる。それぞれのＣＥは、制御されるＦＥから物理的に遠い位置にある。それぞれのＣＥは、標準プロトコルを介してその制御されたＦＥと通信する。ＰＯＰ  Ｅｔｈｅｒｎｅｔ（登録商標）ネットワークは、コア・ルータによりコア・ネットワークに接続され、ＣＥに接続され、さらにＦＥに接続される。
【００１３】
本発明の教示は、付属の図面とともに以下の説明を考察することによりよく理解できる。
【発明を実施するための最良の形態】
【００１４】
理解しやすくするために、できる限り、これらの図に共通の同一の要素を示すために同一の参照番号を使用した。
本発明は、主に、ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例の実施形態の一般的背景状況の範囲内において説明されるが、ただし、当業者および本明細書の教示による情報を得た者であれば、分離概念を使用して、ネットワーク・アーキテクチャの他のさまざまな実施形態を生み出すことができること、および本発明は、ローカル・エリア・ネットワーク（ＬＡＮ）、メトロポリタン・エリア・ネットワーク（ＭＡＮ）、ワイド・エリア・ネットワーク（ＷＡＮ）、および他のネットワーク、多くの開放型システム間相互接続（ＯＳＩ）層、ゲートウェイ・プロトコル、シリアル回線プロトコル、プロトコル・スタック・ルーティングおよびブリッジング・プロトコル、多くの他のプロトコル、トラフィック管理、光学、エッジ／コア・ルーティング、無線、ケーブル、データ・センター、補助信号経路（ＡＳＰ）、故障管理、構成管理、アカウンティング管理、パフォーマンス管理、セキュリティ管理、その他のネットワーク管理、企業、政府、軍事アプリケーション、およびその他の多くの異なる種類のネットワーキング特性およびアプリケーションに適用可能であることを理解するであろう。
【００１５】
インターネットワーキングにオープンな標準ベースのプロトコルを使用してルータのハードウェアをルータのソフトウェアから分離することには、多くの利点がある。分離概念は、各コンポーネントのサプライヤを分断することで、ハードウェア・ベンダの参入を阻害している壁を低くし、新規ハードウェア市場参入者に供給するキャリア・クラス・ルーティング・ソフトウェアの開発に独立系ソフトウェア・ベンダ（ＩＳＶ）が投資する意欲を高める。この分離概念を利用することにより、それぞれのコンポーネントがそれ独自の革新曲線から逸れることなく辿れるようにできる。ハードウェア・メーカーは、最低のコストで最高の単位密度当たり速度を達成することに集中して、資本支出を低減することができ、またソフトウェア・メーカーは、新しいアプリケーションおよびマネジャビリティに集中して、経常経費を下げつつ収益を高めることができる。
【００１６】
アーキテクチャの概要
ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例の一実施形態では、制御プレーン機能の実装とパケット転送機能とを分けることによりルータの 分解を行う。この 分解を実現するネットワーク・アーキテクチャの他の実施形態も、本発明の範囲内にある。本発明は、この 分解の概念およびネットワーク・アーキテクチャに対するその密接な関係を対象とする。ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例では、すべての制御プレーン機能は、転送エンジンと同じ場所に配置される必要のない別の制御エンティティ上に実装される。協調構成変更は少数のスマート・ネットワーク要素のみで行えばよく、ＡＳ内のすべてのネットワーク要素で行う必要がないため、すべての非転送関係状態および制御処理を少数のネットワーク・ベースの制御エンティティに移行することにより、ネットワーク規模の目標を単純化することが可能になる。さらに、コントローラと転送エンジンとの関連は動的であり、制御を行うことができる制御エンティティによる転送エンジンの柔軟な制御が可能である。
【００１７】
ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例は、ネットワーク内の転送エンティティと制御エンティティとの間の動的バインディングを確立し、維持するための動的バインディング・プロトコルを含む。ドメイン内およびドメイン間ルーティングは、ドメイン内プロトコルＯＳＰＦのパフォーマンス改善を含む、パフォーマンスが改善されたＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例において適合される。
【００１８】
インターネットワーキングにオープンな標準ベースのプロトコルを使用してルータのハードウェアをルータのソフトウェアから分離することには、多くの利点がある。分離概念は、各コンポーネントのサプライヤを分断することで、ハードウェア・ベンダの参入を阻害している壁を低くし、新規ハードウェア市場参入者に供給するキャリア・クラス・ルーティング・ソフトウェアの開発に独立系ソフトウェア・ベンダ（ＩＳＶ）が投資する意欲を高める。この分離概念を利用することにより、それぞれのコンポーネントがそれ独自の革新曲線から逸れることなく辿れるようにできる。ハードウェア・メーカーは、最低のコストで最高の単位密度当たり速度を達成することに集中して、資本支出を低減することができ、またソフトウェア・メーカーは、新しいアプリケーションおよびマネジャビリティに集中して、経常経費を下げつつ収益を高めることができる。
【００１９】
ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例の一実施形態は、新しく出てくるアプリケーションにより要求される複雑なＩＰ機能を分離する１つのアプローチである。ＳｏｆｔＲｏｕｔｅｒは、複雑さの共有を中央に集中し、複雑さの共有を可能にする。ＳｏｆｔＲｏｕｔｅｒでは、ＩＰ転送機能を過度に妨げることなく新機能のスケーラブルな導入を果たせる。
【００２０】
図１は、集積化された制御およびトランスポート・プレーンを備える従来のルータ１００を示している。従来のルータ１００は、ソフトウェア１０２およびハードウェア１０４を備え、専用インターフェイス１０６を通じて通信する。
【００２１】
それとは対照的に、図２は、標準プロトコルを使用して通信する別々のハードウェア内の制御プレーンとトランスポート・プレーンを分離するＳｏｆｔＲｏｕｔｅｒアーキテクチャ２００の実施例の高水準抽象化を示している。ＳｏｆｔＲｏｕｔｅｒアーキテクチャ２００は、制御要素およびフィーチャ・サーバ・コンポーネント２０２、および標準ベースのプロトコル２０６を使用して通信するパケット転送要素コンポーネント２０４を備える。
【００２２】
図３は、相互接続された多数のルータ３００を備える従来のルータ・アーキテクチャを示す。
【００２３】
図４は、ＳｏｆｔＲｏｕｔｅｒアーキテクチャ４００の実施例の一実施形態を示している。ＳｏｆｔＲｏｕｔｅｒアーキテクチャ４００のこの実施形態では、ソフトウェア・サーバは、制御要素（ＣＥ）４０２およびフィーチャ・サーバ（ＦＳ）４０４を含む。ＣＥ  ４０２は、従来のルーティング、例えば、内部ゲートウェイ・プロトコル（ＩＧＰ）（例えば、開放型最短経路優先（ＯＳＰＦ））および外部ゲートウェイ・プロトコル（ＥＧＰ）（例えば、境界ゲートウェイ・プロトコル（ＢＧＰ））の両方に関与する。ＦＳ  ４０４は、付加価値機能およびネットワーク・ベース・アプリケーション、例えば、ＱｏＳ、ＶＰＮ、およびモバイルＩＰに関与する。ＣＥ  ４０２およびＦＳ  ４０４は、両方とも、転送要素（ＦＥ）４０６とインターフェイスする。ＣＥ  ４０２およびＦＳ  ４０４は、それぞれ相手との追加インターフェイスを備えることができる。ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例は、ソフトウェア・ベースのルート・コントローラ（ＳｏｆｔＲｏｕｔｅｒ）をハードウェア・ベースのトランスポートおよびパケット転送から分離して、中央に集中させる。
【００２４】
ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例におけるルータの 分解により、制御機能と転送機能とが分離される。この分離は、論理的に行われるだけでなく（例えば、モジュール型アプリケーション・プログラミング・インターフェイス（ＡＰＩ）で正しく定義されたインターフェイスの使用）、実際、制御は、転送が実行される場所から数ホップ分だけ物理的に隔てられている（つまり、別のネットワーク要素内で実行される）。
【００２５】
ネットワーク・エンティティ
ＦＥ  ４０６は、トラフィックの実際の転送およびスイッチングを実行するネットワーク要素である。構造上、ＦＥ  ４０６は、それぞれ次々に複数のポートの終端となる複数のライン・カード、および一方のライン・カードから他方のライン・カードへデータ・トラフィックを往復するスイッチ・ファブリックを備えることができるという点で従来のルータと類似している。しかし、ローカルで実行される高度な制御ロジック（例えば、ＯＳＰＦまたはＢＧＰのようなルーティング・プロセス）がないため、ＦＥ  ４０６は従来のルータと異なる。その代わりに、制御ロジックはリモートでホスティングされる。
【００２６】
ＣＥ  ４０２は、サーバなどの汎用コンピューティング要素である。これは、エンド・ホストと同様にネットワークに接続するが、ただし、通常、複数のＦＥ  ４０６を介してネットワークにマルチホーミングで接続されるため、単一のリンクに障害が発生してもネットワークから切断されることはない。ＣＥ  ４０２は、ＦＥ  ４０６の代わりに、制御ロジックを実行し、したがって、それらを制御する。従来のルータに通常存在する制御ロジックは、ＯＳＰＦおよびＢＧＰのようなルーティング・プロトコルだけでなく資源予約プロトコル（ＲＳＶＰ）、ラベル配布プロトコル（ＬＤＰ）、モバイルＩＰなどのプロトコルをも含めて、ＣＥ  ４０２に移行することができる。
【００２７】
ＦＥ  ４０６は、リンク間でデータ・トラフィックを転送する機能を実行する。この機能は、特にパケット転送、ラベル・スイッチング、および光スイッチングなど、さまざまな形態を取りうる。パケット転送は、レイヤ２（媒体アクセス制御（ＭＡＣ）ベースのスイッチング）およびレイヤ３（最長プレフィックス一致）転送の両方を含む。ラベル・スイッチングは、例えば、ＭＰＬＳ転送を含む。データ・パス転送機能は、ラベル・スワッピング、プッシング、およびポッピングを含むことができる。光スイッチングでは、トラフィックは、リンク間で、時間スイッチング、波長スイッチング、または空間スイッチングが可能である。これらの場合のそれぞれにおいて、スイッチング機能は、ネットワーク内のＣＥ  ４０２により計算され、インストールされる単純ローカル・テーブルにより駆動される。そこで、ＦＥ  ４０６がローカル・データ構造にのみ基づいてその作業を遂行できることは、ＦＥ  ４０６は低機能であるが高速であるように設計され、より複雑なロジックはリモートにあるそれでありながら高機能なＣＥ  ４０２に委ねられていることを意味している。
【００２８】
ＦＥ  ４０６およびＣＥ  ４０２は、両方とも、物理ネットワーク要素であることに加えて論理エンティティと理解される。特に、ＦＥ  ４０６は、トラフィックを相互に切り換えられるポートの集合体として論理的に定義される。例えば、ＦＥ  ４０６は、単一のライン・カード上のすべてのポートを含むことができるが、この場合、物理パケット・スイッチ全体は複数の論理ＦＥ  ４０６で構成される。ＦＥ  ４０６は、さらに、複数の物理スイッチにまたがってもよいが、ＣＥは複数のＦＥを制御することができる。同様に、ＣＥ  ４０２は、ＦＥの代わりに制御を行うためにインスタンス化された論理プロセスとして理解することができ、また実際にそれを実行するサーバ・マシンから区別することができる。特に、物理ＣＥサーバ・マシン（ＰＣＥ）は、それぞれ複数のＦＥ  ４０６からなる異なる集合体にサービスを提供する、複数のＣＥ  ４０２プロセスをホスティングすることができる。その逆に、同じＦＥ  ４０６にサービスを提供する複数のＣＥ  ４０２プロセス（それぞれ、内部ゲートウェイ・プロトコル（ＩＧＰ）および外部ゲートウェイ・プロトコル（ＥＧＰ）などの異なる制御目的に合わせてインスタンス化される）を異なるＰＣＥ上でホスティングすることも可能である。ＦＥ  ４０６およびＣＥ  ４０２の物理的および論理的定義は、入れ換えて使用できる。
【００２９】
図５は、ネットワーク要素５００を例示するＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例の一実施形態を示している。ルータという概念は、ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例では厳密には必要とされないが、ネットワークのルーティングに関する面を理解するために、何らかの同等の概念を用意することが有用である。この目的のために、ネットワーク要素（ＮＥ）５００の概念は、ＦＥ  ４０６およびそれらのＦＥ  ４０６を制御するそれぞれのＣＥ  ４０２からなる論理グループとして高水準の定義が行われる。特定のＮＥ  ５００グループは、暗黙のうちに、ＦＥ間の各リンクを内部（またはＮＥ内）または外部（またはＮＥ間）のいずれかとして分類する。内部リンクは、同じＮＥ  ５００に属する２つのポートを接続し、外部リンクは、異なるＮＥ  ５００に属する２つのポートを接続する。ＮＥ  ５００の概念は、ＮＥ内およびＮＥ間ルーティングが異なるアプローチに従う場合に有用である。
【００３０】
制約を加えることなく、ＮＥ  ５００の上記の定義は柔軟に対応できる。例えば、この定義では、ネットワークの非連結部分の中の２つのＦＥ  ４０６が同じＮＥ  ５００に属すようにできる。また、これにより、ＦＥ  ４０６が物理要素内の完全にすべてのポートを含み、（複数の）制御ＣＥ  ４０２が同じ要素上の同じ場所に配置される従来のルータ・モデルが可能になる。
【００３１】
クラスタ化されたルーティングでは、ＮＥ  ５００を構成するＦＥ  ４０６は、切れ目のないクラウドの一部である。つまり、ＮＥ  ５００のすべてのポートは、ＮＥ  ５００の内部のリンクを介してお互いから到達可能であるということである。物理的に、これは、隣接する物理ＦＥ  ４０６の単一のＮＥ  ５００内へのクラスタ化を表す。本社では複数のルータが背中合わせで接続されているというのが通常のシナリオである。ルーティングの観点からは、ＮＥ  ５００に対するこのクラスタ化ベースの定義は、著しい簡素化をもたらしうる。ルーティングの面でＮＥ  ５００の個数が減ることにより、ＮＥ間のルーティングの複雑さが減じ、異なる、場合によっては複雑さの少ないルーティング・プロトコルをＮＥ内ルーティングに採用することができる。
【００３２】
ＦＥ  ４０６とＣＥ  ４０２との制御関係は、バインディングと正式に呼ばれる。より正確には、ＦＥ  ４０６とＣＥ  ４０２との間バインディングは、ＣＥ  ４０２がＦＥ  ４０６の代わりに特定の制御機能を実行していることを意味する。複数のプロトコル（例えば、ＩＧＰおよびＥＧＰ、またはさらには１つのプロトコルの複数のインスタンス）がＦＥ  ４０６の動作に必要になる場合があるため、ＦＥ  ４０６は複数のＣＥ  ４０２バインディングを持ちうる。
【００３３】
プロトコル
ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例は、さまざまなプロトコルを含む。ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例に従って設計されたネットワークの運用には、動的バインディング・プロトコルおよびＦＥ／ＣＥトランスポート・プロトコルを含む、さまざまな多数のプロトコルが使用される。ＦＥ  ４０６とＣＥ  ４０２との間のバインディングは、ＣＥ  ４０２およびＦＥ  ４０６を発見するプロトコルを介して確立され、さらに、ネットワークの接続途絶に直面したときもこれらのバインディングを維持する。動的バインディング・プロトコルの最も一般的な場合には、ＦＥ  ４０６は、利用可能な任意のＣＥ  ４０２にバインドすることができ、ＣＥ  ４０２は、任意のＦＥ  ４０６に対する制御機能を実行し、それによって、回復力を最大限発揮し、構成オーバーヘッドを最小限にとどめることができる。この動的バインディング機能は、制御機能と転送機能とが独立している 分解ルータ群の概念の１つの特徴である。ＦＥ／ＣＥトランスポート・プロトコルは、２つの部分、つまりデータおよび制御を持つ。データ部については、ＦＥ／ＣＥトランスポート・プロトコルは、ＦＥ  ４０６とＣＥ  ４０２との間のルーティング・プロトコル・パケットのトンネリングをサポートしており、そのため、ＦＥ  ４０６により受信されたルーティング・プロトコル・パケットをＣＥ  ４０２に送信して処理させることができる。制御部については、バインディングが確立されると、ＦＥ  ４０６およびＣＥ  ４０２は、ＦＥ／ＣＥトランスポート・プロトコルを使用して、状態情報を伝達し、制御を実行する。アップリンク（ＦＥ  ４０６からＣＥ  ４０２）方向では、この制御部は、リンクおよび転送状態情報（例えば、リンク・アップ／ダウン信号）をＣＥ  ４０２に供給する。ダウンリンク方向では、ＦＥ／ＣＥトランスポート・プロトコルは、構成および制御情報を伝送する（例えば、リンク、転送情報ベース（ＦＩＢ）の有効／無効を設定する）。転送および制御要素の分離などの知られているプロトコル（ＦｏｒＣＥＳ）を、ＦＥ／ＣＥトランスポート・プロトコルに使用することができる。
【００３４】
いくつかの特徴
ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例は、動的バインディング、および分散制御の度合いを変えられること、という２つの特徴を持つ。ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例では、ＦＥ  ４０６は、いつでもネットワーク上のＣＥ  ４０２に動的にバインドすることができ、またその逆も可能である。このため、制御プレーンの設計および配備の自由度が向上し、その結果、弾力性、運用の複雑さ、スケーラビリティ、管理、およびセキュリティが改善される。それと対照的に、従来のモデルにおける静的バインディングでは、インターネット制御プレーンの再設計に関して信頼性が低く、また柔軟性も低い。分散制御には、弾力性などの利点があるが、これもまた、何らかのネットワークの不安定性を生じる可能性がある。例えば、ＢＧＰのルート・リフレクタを使用することには、振動問題が伴い、ＯＳＰＦなどのフラッディング・ベースのリンク状態プロトコルでは、複数の障害が生じると、更新の嵐が吹きまくる可能性がある。ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例では、さまざまな程度の分散制御が可能である。特に、ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例の複数の実施形態では、ＦＥ  ４０６のクラスタ化の仕方、およびＣＥ  ４０２上での制御の集約の仕方を変えることにより、さまざまな程度の分散制御を実装する。制御ポイントが少ないということは、ネットワークの分割などの障害条件に対する脆弱性が高いが、ネットワーク安定性は潜在的によい可能性があることを意味する。従来の完全分散ルーティングおよび完全集中ルーティングは両方とも、ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例の可能な数多くの実施形態のうちの２つの極端な実装にすぎない。
【００３５】
動的制御バインディング
ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例の動的バインディング機能では、ＦＥ  ４０６をＣＥ  ４０２から数ホップ分だけ隔てることができる。このような柔軟性は、転送要素の初期構成の複雑度が高まることと引き換えに実現される。ＳｏｆｔＲｏｕｔｅｒモデルでは、ブートアップ後に、ＦＥ  ４０６は、サーバ上に常駐するリモートＣＥ  ４０２からインターフェイスのＩＰアドレスを含む、構成情報を取得する。これは、パラドックスを引き起こす可能性がある、つまり、ＣＥ  ４０２を発見し、それにパケットを送信するために、ＦＥ  ４０６はルーティング情報を必要とするが、ルーティング情報は、ＣＥ  ４０２から発せられると想定されている。このパラドックスは、ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例の一部である発見プロトコルを使用して解決される。この発見プロトコルにより、ＦＥ  ４０６およびＣＥ  ４０２はお互いを発見し合い、ＩＰルーティングに基づかない、それらのエンティティの間のルーティング可能な経路を維持する。動的バインディング・プロセスは、さらに、ＣＥ  ４０２負荷分散、ＣＥ−ＦＥバインディング回復性を改善する制約クラスタ化アルゴリズム、およびフェイルオーバーなどの強化された機能をサポートし、ネットワークの可用性を向上させる。また、これらの機能を使用することにより、ネットワーク計画を改善し、ネットワーク規模の制御を適切に行うことができる。
【００３６】
動的バインディング・プロトコル
動的バインディング・プロトコルの実施形態は、ＦＥ  ４０６用のバインディング・サービスおよびＦＥ−ＣＥメッセージ用のルーティング・サービスを提供する。動的バインディング・プロトコルは、ネットワーク内で動作する他のプロトコルとは無関係に、独立したプロトコルとしてネットワークの存続期間中、すべての要素（ＦＥ  ４０６およびＣＥ  ４０２）上で連続実行される。最低でも、それぞれのＦＥ  ４０６およびＣＥ  ４０２は、一意的な識別子として働く事前構成された８進数文字列（ＦＥＩＤ／ＣＥＩＤ）を持つ。動的バインディング・プロトコルは、トランスポート独立であり、レイヤ２またはレイヤ３のネットワーク上で動作可能である。例えば、これは、ループ回避のため高速スパニング・ツリー・プロトコルとのレイヤ２ブリッジングを使用して、Ｅｔｈｅｒｎｅｔ（登録商標）ネットワークまたはＦＥ  ４０６およびＣＥ  ４０２内で実行することができる。異機種ネットワークでは、発見プロトコルは、ソース・ルーティングまたはブリッジングとともにレイヤ３アドレス指定を使用することができる。動的バインディング・プロトコルは、発見、関連付け、フェイルオーバーによる障害検出、およびトランスポート・トンネルの４つのコンポーネントを持つ。
【００３７】
発見
動的バインディング・プロトコルの発見コンポーネントを使用することにより、ＦＥ  ４０６はそれを管理できるＣＥ  ４０２を発見することができる。このＣＥ  ４０２は、そのＦＥ  ４０６用の管理側ＣＥと呼ばれる。発見コンポーネントが構成プロセスの高速な発見を行えるようにするために、ＣＥ  ４０２到達可能性情報がそれぞれのＦＥ  ４０６に配信される。新しくブートされるＦＥ  ４０６は、ただ、ネットワーク内のすべてのＣＥ  ４０２への到達可能性情報を取得するために近隣要素に問い合わせを行うだけである。ＣＥ  ４０２到達可能性情報を配信するために、ＦＥ  ４０６は、要請メッセージを近隣要素に、定期的にブロードキャストする。近隣要素がＣＥ  ４０２の場合、これは、そのＩＤを広告することにより応答する。近隣要素がＦＥ  ４０６の場合、これは、すべてのすでに学習されているＣＥ  ４０２への到達可能性情報で応答する。ソース・ルーティングについては、到達可能性情報は、ＣＥ  ４０２のＩＤのほかに、ＣＥ  ４０２に到達するソース経路、および情報の新鮮さを示す有効期間パラメータを含む。
【００３８】
ソース・ルーティングの場合、ＦＥ  ４０６は、その近隣要素を知っている必要がある。ＣＥ  ４０２の広告またはＦＥ  ４０６到達可能性メッセージを近隣要素から受信すると、ＦＥ  ４０６５は近隣ＦＥＩＤまたはＣＥＩＤを受信されたソース経路に追加する。ＣＥ  ４０２は、受信されたパケット内でソース・ルートを逆転することにより、ＦＥ  ４０６へのソース経路を導く。（ＦＥ  ４０６は、常に、ＣＥ  ４０２と一番最初のパケット交換を開始する。）近隣要素は、すべての発見プロトコル対応インターフェイス上でｈｅｌｌｏメッセージを定期的に送信することによりそれ自体を広告する。そこで、それぞれのノード（ＦＥ／ＣＥ）は、ｈｅｌｌｏメッセージがもはや受信されなくなった場合、近隣要素のリストを保持する。
【００３９】
ＩＰアドレス指定を使用する発見プロセスでは、ブートアップ時に、それぞれのＦＥ  ４０６は、そのインターフェイス用のランダムに選ばれた一時ＩＰアドレスをＦＥＩＤとともに使用して、事前構成ソース・ルーティングを実行する。これらのＩＰアドレスは、制御されるアドレス空間、例えば、１０．ｘ．ｘ．ｘのようなプライベート・サブネット・アドレス・プールから選択される。ＣＥ  ４０２は、事前構成されており、したがって、有効なＩＰアドレスを持つ。すべてのメッセージは、ＩＰ制限ブロードキャストまたはマルチキャストを使用し、未構成のＦＥ  ４０６および構成済みのＦＥ  ４０６またはＣＥ  ４０２のピアリングを行う遷移フェーズにおいて共通である異なるサブネットのＩＰアドレス間でのパケット交換を行えるようにする。ＩＰアドレス指定は、直接の近隣要素とのパケットの交換にしか使用されない。したがって、一時ＩＰアドレスは、リンク毎に一意であればよい。
【００４０】
それぞれのＦＥ  ４０６は、ネットワーク計画時にネットワーク管理者により１つの一次ＣＥおよび少なくとも１つのバックアップＣＥを割り当てられる。この情報は、ＣＥ  ４０２で構成され、任意選択により、ＦＥ  ４０６でも構成される。通常、この割当は、ＣＥ  ４０２に対する負荷、ＣＥ  ４０２とＦＥ  ４０６との間の距離、およびそれらの間のリンクの信頼性などのファクタを考慮して、先験的に行われる。
【００４１】
この関連付けプロセスでは、ＦＥ  ４０６とその一次ＣＥおよびバックアップＣＥとの間のアクティブな関連付けを確立し、維持するよう努める。管理側ＣＥは、関連付けられたＣＥ  ４０２のリストからＦＥ  ４０６により選択され、一次ＣＥは常に他のＣＥ  ４０２よりも好まれる。ＦＥ  ４０６は、ネットワーク管理者により事前に構成されるか、または分散クラスタ化アルゴリズムを使用して得られたバインディングを使用して最良のＣＥ  ４０２と動的に関連付けされる。ＦＥ  ４０６は、関連付けメッセージを送信することによりＣＥ  ４０２と関連付けされる。ＣＥ  ４０２は、ＦＥ  ４０６を管理できる場合にＦＥ  ４０６を受け入れ、そうでなければ拒絶する。ＣＥ  ４０２に知られている場合、その拒絶は、任意選択により、ＦＥ  ４０６に対する一次ＣＥおよびバックアップＣＥのＩＤを含むことができる。受け入れられた場合、ＦＥ  ４０６は、その一次ＣＥまたはバックアップＣＥとの接触に進むか、または他のＣＥ  ４０２との接触による探索を継続する。
【００４２】
障害検出および修復
動的バインディング・プロトコルは、ＣＥ  ４０２の障害を検出し、修復するメカニズムを備える。ＦＥ  ４０６とＣＥ  ４０２との間で関連付けが行われた後、その関連付けが有効かどうか、ＦＥ  ４０６により開始されたハートビート・メッセージを通じて定期的に調査が行われる。ハートビート・メッセージがＣＥ  ４０２からどのような応答も引き出さない場合、ＣＥ  ４０２への経路はもはや有効でない、またはＣＥ  ４０２はもはや生きていないことを意味する。その後、ＦＥ  ４０６は、アクティベート・メッセージを送信することによりバックアップＣＥの１つにフェイルオーバーする。バックアップＣＥは、アクティベート・メッセージの受信を確認し、その後管理側ＣＥとなる。ＣＥ  ４０２は、変更を受け入れたＦＥからの受信確認なしではＣＥ  ４０２との関連付けを解除できない。このことは、現在の管理側ＣＥがまだ生きている限り、管理側ＣＥを変更することを望んでいるＦＥ  ４０６についても当てはまる。
【００４３】
トランスポート・トンネル
動的バインディング・プロトコルは、スロー・パス（つまり、必ずしも最短経路ではない、ソースでルーティングまたはブリッジングされた経路）と呼ばれる、ＦＥ  ４０６とその関連付けられたＣＥ  ４０２との間の基本的なトランスポート・トンネルをセットアップし、他のすべての通信手段が失敗した場合に上位レイヤ・プロトコル（例えば、ＯＳＰＦ）のＣＥ−ＦＥ通信を行えるようにする。これらのトンネルは、信頼性がなく、順序通りの配信は保証されない。これらのスロー・パス・トンネルは、ＦＥ  ４０６に有効なルーティング・テーブルがインストールされていない場合、例えば、ＦＥ  ４０６が初期化中であるか、またはＦＥ  ４０６が異なる管理側ＣＥに切り換え中である場合など、ごくまれにしか使用されない。
【００４４】
これら４つのコンポーネントの組み合わせにより、動的バインディング・プロトコルでネットワーク内のＦＥ  ４０６とＣＥ  ４０２との間の動的バインディングをアクティブに発見し、維持することができる。
【００４５】
負荷分散、クラスタ化、およびフェイルオーバー
動的バインディング・プロトコルでは、数ホップ分だけ隔てられているＣＥ  ４０２とＦＥ  ４０６の間の動的バインディングに対応できる。このため、ＦＥ  ４０６およびＣＥ  ４０２では、管理側ＣＥおよび被管理ＦＥ集合をそれぞれ決定する際にさまざまな選択肢を利用できる。さまざまな設計の選択は、それらの選択に構造を課すことにメリットがあるかどうか、およびもしあれば使用すべき基準に応じて行うことができる。これらの選択を調整することにより、ネットワーク内の決定論的挙動、ネットワーク管理者の管理下での制御範囲の拡大、およびネットワーク計画の改善が可能になる。これらの利点があれば、所定のＣＥ  ４０２により管理されるＦＥ  ４０６を割り当てるために、管理されるＦＥ  ４０６の個数に関する所定のＣＥ  ４０２上の負荷、ＦＥ  ４０６とその管理側ＣＥとの間の平均距離（ホップ数を単位とする）、およびＣＥ  ４０２上の負荷に悪影響を及ぼすことなくフェイルオーバーをどのように素早く実行できるかといった基準を使用する。これらの基準は、所定の数のＣＥ  ４０２が配置されている場所を設計者が選択する、ネットワーク計画の背景状況において扱われる。
【００４６】
ＣＥの配置
ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例の実施形態を設計するために、（１）ｋ個のＣＥ  ４０２間に負荷を分散し、（２）それぞれのＦＥ  ４０６とその関連付けられたＣＥ  ４０２との間の平均距離が最小になるように、ＦＥ  ４０６のネットワーク内にｋ個のＣＥ  ４０２を配置することが望ましい。ｋ個のＣＥ  ４０２を配置する場所に制約はない、およびＦＥ  ４０６は任意のＣＥにより管理されるように割り当てることができるという初期仮定が置かれる。一次ＣＥの集合にわたるＦＥ  ４０５の負荷は、分散され、それと同時に、ＦＥ  ４０６とその一次ＣＥとの間の平均距離が最小にされる。リンクは、異なる遅延またはフェイルオーバー特性を持つことがあり、ＣＥ  ４０２の位置は、選択される。どのようなＣＥサーバもできる限り過負荷にならないようにするのが望ましい。また、ＦＥ  ４０６とその一次ＣＥとの間の平均距離を最小にし、通信待ち時間を短縮し、ＣＥ  ４０２上で実行するルーティング・プロトコルに障害発生を素早く通知できるようにすることが望ましい。さらに、ＦＥ  ４０６がその一次ＣＥに近いほど、発見プロセスは速く収束する。そのため、すべてのＣＥ  ４０２の能力が等しければ、ＦＥネットワークをほぼ等しいサイズの複数のクラスタに分割することで、負荷分散することと、管理側ＣＥとＦＥ  ４０６との間の平均距離を最小にすることというこれらの二重の目標が達成される。
【００４７】
このｋ辺均等分配問題では、目標は、グラフを等しいサイズの複数のクラスタに分割する場合に、各クラスタ内の辺の重みを最小にすることである。この最適化問題は、ＮＰ完全と呼ばれる。多項式時間内に、ただし近似に対する厳密な限界なしで、完了する実現に基づけば、この問題に対するほぼ最適な解が得られる。再帰的グラフ２分割法では、グラフを２つのサブグラフに再帰的に分割することによりｋ辺分割が得られ、それらのサブグラフの一方は、サイズ［ｎ／ｋ］に設定される。再帰的グラフ２分割法は、ネットワークが適切に連結している場合には、十分うまく働く。
【００４８】
図６は、２０ノードおよび４４リンクを持つ典型的なＴｉｅｒ  １  ＰＯＰレベルＩＳＰトポロジ上で使用されるような再帰的２分割法を示している。このネットワークの直径は４である。ＣＥ  ４０２の個数は、２から７までの範囲であり、それらの結果は、ＣＥクラスタ１つ当たりのＦＥ  ４０６の個数および管理側ＣＥからＦＥ  ４０６までの距離に基づく図７の表にまとめられている。ＣＥは、単一のＦＥ  ４０６に接続される。ＣＥ  ４０２が複数のＦＥ  ４０６との直接リンクを持つ場合、距離測定基準はさらに小さくなる。
【００４９】
フェイルオーバー
ＣＥ  ４０２フェイルオーバーは、ＦＥ  ４０６とその管理側ＣＥとの間の関連付けがタイムアウトになった場合に発生する。これは、管理側ＣＥがダウンしたという理由で、またはＦＥ  ４０６がハートビート交換のため管理側ＣＥへの有効な経路を発見できない場合に発生しうる。その後、ＣＥフェイルオーバーが実行され、ＦＥは、他の関連付けられたＣＥ  ４０２があればそれに切り換わる。その後、新しいＣＥ  ４０２は新しい管理側ＣＥになる。
【００５０】
フェイルオーバーは、最小の遅延で発生する必要がある。したがって、所定のＦＥ  ４０６についてどのＣＥ  ４０２がバックアップＣＥとして指定されるかが決定される。ＦＥ  ５０６は、複数のバックアップＣＥを、それらの間の優先順位順で持ちうる。ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例の実施形態では、バックアップＣＥを選択する基準は、最短フェイルオーバー時間を含む。
【００５１】
バックアップＣＥは、各バックアップＣＥと前のバックアップＣＥおよび一次ＣＥとの経路重なり量が最小となるように選択される。一次ＣＥからＦＥ  ４０６への経路は、ＦＥ  ４０６から選択されたバックアップＣＥへの経路との重なりが最小であるのが好ましい。同様に、第２のバックアップＣＥは、ＦＥ  ４０６への経路とＦＥ  ４０６から一次ＣＥおよび第１のバックアップＣＥの両方への最短経路との重なりが最小になるように選択される。複数のリンクまたはＣＥ／ＦＥ障害が存在しても、接続性が確実に維持されるようにすることが１つの目標である。
【００５２】
バックアップＣＥを使用しているＦＥ  ４０６は、条件が許せば、常に、その一次ＣＥに再関連付けをしてそれに切り換えようとする。このため、負荷分散アルゴリズムにより決定されるように、すべてのＣＥ  ４０２上の負荷はほとんど等しいことが保証される。
プロトタイプの実装
【００５３】
図７は、プロトタイプ・テストベッドの実施例のブロック図である。ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例の実現可能性を検証するために、ＦＥ  ４０６およびＣＥ  ４０２として動作する市販のルータとＰＣとの混合を使用するテストベッドでプロトタイプの実装を行った。このテストベッドは、６個のＮＥ  ５００（それぞれのＮＥは、図８において同じ形状を持つコンポーネントにより示されている）、Ｃｉｓｃｏ（商標）７２００ルータ７００、Ｊｕｎｉｐｅｒ（商標）Ｍ−２０ルータ７０２、ホストＰＣ  ７０４、サーバＰＣ  ７０５、およびネットワーク・モニタＰＣ（図に示されていない）を含み、すべてＥｔｈｅｒｎｅｔ（登録商標）を介して相互接続されている。それぞれのＮＥ  ５００は、一次ＣＥおよびバックアップＣＥに接続された少なくとも１つまたは複数のＦＥ  ４０６を含む。ＦＥ  ４０６は、特定の一次ＣＥおよびバックアップＣＥを選択するように事前構成されている。通常動作時には、一次ＣＥは管理側ＣＥとして選択される。ＮＥ  ５００の一次ＣＥおよびバックアップＣＥは、２つの異なるＰＣＥ、ＰＣＥ１  ７０６、およびＰＣＥ２  ７０８上でホスティングされる。それぞれのＰＣＥは、高性能制御サーバからなるクラスタを表しているが、簡単のためテストベッドでは単一サーバとして実装されている。
【００５４】
一次ＣＥ（つまり、ＣＥ１ｐ  ７１０、ＣＥ２ｐ  ７１２、ＣＥ６ｐ  ７１４）は、ＰＣＥ２  ７０８および制御ＦＥ１  ７１６｛ＦＥ２ａ  ７１８、ＦＥ２ｂ  ７２０｝およびＦＥ６  ７２２上でそれぞれホスティングされる。対応するバックアップＣＥ（つまり、ＣＥ１ｂ  ７２４、ＣＥ２ｂ  ７２６、ＣＥ６ｂ  ７２８）は、ＰＣＥ１  ７０６上でホスティングされる。一次ＣＥ（つまり、ＣＥ３ｐ  ７３０、ＣＥ４ｐ  ７３２、ＣＥ５ｐ  ７３４）は、ＰＣＥ１  ７０６および制御ＦＥ  ４０６｛ＦＥ３ａ  ７３６、ＦＥ３ｂ  ７３８、ＦＥ３ｃ  ７４０｝、ＦＥ４  ７４２、およびＦＥ５  ７４４上でそれぞれホスティングされる。対応するバックアップＣＥ（つまり、ＣＥ３ｂ  ７４６、ＣＥ４ｂ  ７４８、ＣＥ５ｂ  ７５０）は、ＰＣＥ２  ７０８上でホスティングされる。
【００５５】
テストベッド・トポロジは、３種類のＮＥ  ５００、つまり（１）少なくとも１つの直接リンクを持つＮＥ  ５００のＣＥ  ４０２およびＦＥ  ４０６（つまり、ＮＥ１、ＮＥ２、ＮＥ３）、（２）ＣＥ  ４０２とＦＥ  ４０６との間で数ホップ分だけ隔てられているＮＥ  ５００のＣＥ  ４０２およびＦＥ  ４０６（ＮＥ４、ＮＥ５、ＮＥ６）を受け入れる。
【００５６】
このプロトタイプの動的バインディング・プロトコルの挙動を評価するために３つの実験が計画された。実験１では、ネットワーク規模のブートの場合に、すべてのＣＥ  ４０２情報がネットワーク全体に伝播するまでの継続時間を決定する。実験２では、リンクおよびノードに障害が発生した場合に、ソース・ルート収束時間を測定する。実験３では、管理側ＣＥに障害が発生した場合にバックアップＣＥへのフェイルオーバー時間を測定する。ネットワーク・イベントは、ＦＥ  ４０６のローカル上でタイム・スタンプが記録され、ネットワーク・モニタＰＣ（図に示されていない）に送信される。すべてのＦＥ  ４０６は、ネットワーク・イベントを相互に関連付けるためネットワーク・タイム・プロトコル（ＮＴＰ）を介して時間同期がとられる。実験毎に、３回測定を行い、その結果の平均をとった。すべての測定時間は秒単位である。
【００５７】
実験１
実験１では、動的バインディング・プロトコルは、すべてのＣＥ  ４０２およびＦＥ  ４０６上で同時に起動された。ＣＥ  ４０２伝播時間は、すべてのＣＥ  ４０２に関して最後のＦＥ  ４０６が学習するのに要した時間であり、表１に示されている。
【表１】
2006135975.tif 000003
【００５８】
これらの結果から、ＰＣＥ１  ７０６およびＰＣＥ２  ７０８から出たＣＥ  ４０２情報は最終的に、すべてのＦＥ  ４０６に到達し、２つの重なり合う波で伝播することがわかる。ＦＥ１  ７１６、ＦＥ３ａ  ７３６、およびＦＥ４  ７４２は、両方の波が交差する最初のノードであり、したがって、それらのノードは、ネットワーク内のすべてのＣＥ  ４０２に気づく最初のノードになる。
【００５９】
実験２
実験２では、リンクおよびノードの障害が動的バインディング・プロトコルの収束時間に及ぼす影響について調べる。リンクＦＥ２ｂ−ＦＥ４  ７５２が、最初に切断され、再び接続された。切断後、ＦＥ４  ７４２は、リンク障害を発見し、ＦＥ３ｂ  ７３８により伝播された情報によりソース・ルートを調整した。その後、この情報は、ＦＥ６  ７２２に受け渡された。再接続の後、ＦＥ４  ７４２はＦＥ２ｂ  ７２０からＰＣＥ２  ７０８上のＣＥ  ４０２へのより短いルートの情報を受け取り、それをＦＥ６  ７２２に伝播した。表２は、ソース・ルート収束時間を示している。
【表２】
2006135975.tif 000004
【００６０】
ノード障害では、ノードＦＥ１  ７１６が停止される。ノード障害の後、ＦＥ２ａ  ７１８およびＦＥ３ａ  ７３６は、最初に、ＦＥ１  ７１６がダウンしていることを発見する。これらは、ＦＥ１  ７１６を伴うすべてのソース・ルートを除去し、そのような情報の伝播を停止する。その近隣要素は、次の伝播サイクルで無効なルートを発見し、それらをソース・ルート・テーブルから除去する。並行して、ＰＣＥ１  ７０６およびＰＣＥ２  ７０８上の一次ＣＥおよびバックアップＣＥへのより長い代替えルートが選択される。ＦＥ４  ７４２が蒔いた情報のみを通じてバックアップＣＥへの新しいルートに関して学習するので、ＦＥ３ａ  ７３６、ＦＥ３ｃ  ７４０、およびＦＥ５  ７４４は、収束する最後のノードである。ノードＦＥ１  ７１６が再起動されると、同様のパターンが観察され、その際に、ノードＦＥ１  ７１６、ＦＥ２ａ  ７１８、およびＦＥ３ａ  ７３６が最初に収束し、ＦＥ１  ７１６から２および３ホップだけ離れているＦＥ３ｂ  ７３８、ＦＥ３ｃ  ７４０、およびＦＥ５  ７４４が続く。収束時間は、ネットワーク内のすべてのＣＥ  ４０２について学習するのに要する時間を示す。
【００６１】
実験３
実験３では、フェイルオーバーのシナリオでは、ＣＥ３ｐ  ７３０プロセスが終了し、これは、ＦＥ３ａ  ７３６、ＦＥ３ｂ  ７３８、およびＦＥ３ｃ  ７４０にハートビート・タイムアウトを引き起こす。それぞれのＦＥ  ４０６は、独立にタイムアウトを検出し、ＣＥ３ｂ  ７４６に切り替わる。タイムアウトとバックアップＣＥのアクティベーションとの間の平均時間は、ＦＥ３ａ  ７３６では０．８秒、ＦＥ３ｂ  ７３８では１秒、ＦＥ３ｃ  ７４０では１．１秒である。
【００６２】
動的バインディングがリンクまたはＣＥ／ＦＥ障害発生後バックグラウンドで実行されている間、対応する管理側ＣＥによりインストールされたＦＩＢに基づいてネットワーク内で転送が続いている。ＯＳＰＦなどの上位レイヤのルーティング・プロトコルによる障害検出が瞬間的でなければ、動的バインディング・プロトコルにより達成される収束時間は、上位レイヤのルーティング・プロトコルの収束時間よりも短い。したがって、動的バインディング・プロトコルは、ほとんどの場合、ネットワーク・ルーティングの挙動の残り部分に対し有害な影響を及ぼさない。
【００６３】
本発明のさまざまな実施形態では、プロトコル集約、高信頼性、およびブートストラッピングのパラドックスといった技術的難題に取り組む。ＣＥサーバでの単一プロトコル・インスタンス化で複数のＦＥを管理する場合にＯＳＰＦ／ＢＧＰのようなプロトコルを動作させる方法、ＣＥサーバを配置すべき場所を決定する方法、どのＣＥサーバがどのＦＥを管理するかを決定する方法がある。ブートストラッピングのパラドックスは、ＦＥがＣＥサーバへのパケットのルーティングのため更新された転送テーブルを必要とするという点で一種の鶏が先か卵が先かの問題であるが、ＣＥサーバのみが転送テーブルを更新できる。
【００６４】
ルーティング・プロトコル
ルーティング・プロトコルは、ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例の一実施形態などの 分解ルータ・ネットワーク内で動作する。ルーティング・プロトコルは、ＣＥ  ４０２でリモート動作し、転送テーブルおよびその他の情報をＦＥ  ４０６にダウンロードすることにより１つまたは複数のＦＥ  ４０６を制御する。ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例は、ドメイン内ルーティングおよびドメイン間ルーティングの両方のプロトコル実現を含む。
【００６５】
ドメイン内ルーティング
ＯＳＰＦなどのドメイン内ルーティング・プロトコルは、ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例に移行される。ＯＳＰＦは、リンク状態広告（ＬＳＡ）を高い信頼度で近隣ルータにフラッディングすることにより、ＯＳＰＦを実行しているそれぞれのルータがネットワーク全体のトポロジを記述している同一のリンク状態データベースを維持できるようにするリンク状態プロトコルである。図９および１０は、従来のルータ・アーキテクチャおよびＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例におけるＯＳＰＦプロトコル実行の差を強調して示している。
【００６６】
図８は、それぞれのルータ３００が、自リンク状態データベース（ＬＳＤＢ）を保持するＯＳＰＦインスタンス８００を実行する、従来技術のネットワークを示す。Ｎノード・ネットワークでは、Ｎ個のＬＳＤＢは同期をとられなければならない。この従来のアーキテクチャでは、ネットワーク内のすべてのルータがＯＳＰＦインスタンス８００の自コピーを実行するが、図１０に示されているＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例では、ＣＥのみがＯＳＰＦインスタンス８００を実行する。
【００６７】
図９は、それぞれのＣＥ  ４０２が複数のＦＥ  ４０６の代わりにＯＳＰＦインスタンス８００を実行するＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例の一実施形態を示す。Ｎノード・ネットワークでは、それぞれのＣＥが１０個のＦＥ  ４０６を管理する場合、Ｎ／１０個のＣＥのみがある。したがって、Ｎ／１０個のＬＳＤＢの同期をとるだけでよく、そのため収束が高速化される。ＣＥは、それが制御する複数のＦＥ  ４０６の代わりに、リモートでＯＳＰＦインスタンス８００を実行する。図１０に示されているＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例および図８に示されている従来のアーキテクチャにおけるＦＥ  ４０６の総数は同じである。しかし、ＣＥ  ４０２の総数は、図８に示されている従来のアーキテクチャよりも図９に示されているＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例のほうが少ない。さらに、ネットワーク間のＯＳＰＦインスタンス８００の総数は、図８に示されている従来のアーキテクチャよりも図９に示されているＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例のほうが少ない。
【００６８】
ＯＳＰＦインスタンス８００は、複数のＦＥ  ４０６を管理し、ネットワーク全体に対するルートを計算する。１つのＯＳＰＦインスタンス８００で複数のＦＥ  ４０６を管理できるようにする際に１つの問題が生じるが、それは、内部リンク、つまり、単一のＯＳＰＦインスタンス８００により管理されるＦＥ  ４０６を接続するリンクを管理することである。内部リンクは、図９中に二重線で示されている。ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例の複数の実施形態は、内部リンクを管理するために、（１）内部リンクおよび重みを他のＯＳＰＦ近隣要素に広告する、（２）それぞれのＮＥ  ５００をＯＳＰＦ領域として構成し、その結果内部リンクに関する要約広告を出力する、または（３）別々の内部リンク・ルーティング・プロトコルを使用し、その結果内部リンクについての広告を行わない、という３つのアプローチを含む。
【００６９】
第１のアプローチは、計算されるルートは、従来の分散ＯＳＰＦを使用して計算されるルートと同一であるという点で従来の分散ＯＳＰＦ実装（１つのＦＥ  ４０６について１つのＯＳＰＦインスタンス）に最も近い近似である。つまり、内部リンクは、外部リンクと同一のものとして取り扱われる。この第１のアプローチでは、従来のアーキテクチャに比べてＯＳＰＦプロセスの数が少なく、メッセージ処理のオーバーヘッドが低いため、ネットワーク内で交換されるＯＳＰＦプロトコル・メッセージはそれでも少ない。
【００７０】
第２のアプローチでは、ＯＳＰＦ領域の構成に固有の自然な階層をＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例内のＮＥ  ５００の定義を表す階層と一致させようとする。この第２のアプローチでは、それぞれのＮＥ  ５００は、ＯＳＰＦ領域として定義され、１領域につき単一のＯＳＰＦプロセスが１つある。この結果、内部リンクが他のＯＳＰＦプロセスに要約広告の形で広告される。この第２のアプローチでは、内部リンクの障害／振動のため、ネットワーク全体のルート変更の形で比較的わずかの摂動が生じる。しかし、この第２のアプローチでは、ルーティングはＯＳＰＦ領域にまたがって最適であることを保証されないため、現在のアーキテクチャに存在する最適なルーティングを犠牲にする。これは、元の配備で構成されたＯＳＰＦ領域はなかったと仮定している。
【００７１】
第３のアプローチは、３つのアプローチのうち最も積極的な最適化である。第３のアプローチでは、内部リンクと外部リンクの定義の間の厳密な境界を維持する従来の挙動は保持され、内部リンクはＯＳＰＦ近隣要素に広告されない（例えば、内部リンクは筐体内のバックプレーン／スイッチ・ファブリックであってよいし、ＦＥ  ４０６を接続する非常に高速なリンクであってもよい）。ある意味で、第３のアプローチは、ＮＥ  ５００を構築する際に採用される戦略をそっくりまねている。３つのアプローチのうち、第３のアプローチを使用した場合、交換されるメッセージが最少となり、障害を原因とするルート変更が最少になり、収束時間が最短となる。しかし、最適なルーティングは、従来のルータ内のバックプレーン／スイッチ・ファブリックについて仮定されているように、内部リンクが本当にゼロ・コストの場合にのみ達成される。
【００７２】
最後に、３つのアプローチすべてに共通なのは、ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例における異なるＯＳＰＦプロトコル・インスタンス化８００の間でＯＳＰＦプロトコル・メッセージをどのように交換するかという問題である。少なくとも２つの可能性があり、ＯＳＰＦプロトコル・メッセージをＣＥ  ４０２からＦＥ  ４０６にトンネリングして、ＦＥ  ４０６がＯＳＰＦプロトコル・メッセージを発しているかのようにすべての近隣要素に見せるか、またはＯＳＰＦプロトコル・メッセージをＣＥ  ４０２同士の間で直接交換する。前者のオプションでは、ＮＥ  ５００と従来のルータとの相互運用性が可能になるが、後者のオプションは、２つのＣＥ  ４０２間で重複するメッセージ交換（つまり、２つのＮＥ  ５００が複数のリンクにより接続されている場合）がなくなるためより効率的である。
【００７３】
実装
上で説明されたこれら３つのアプローチのうち好ましいのは、最も積極的な最適化を行う３番目である。さらに、従来のルータとの相互運用性のため、ＣＥ  ４０２からＦＥ  ４０６にプロトコル・メッセージをトンネリングし、その後、通常のＯＳＰＦメッセージとしてＦＥ近隣要素に送信する戦略が採用される。つまり、ＣＥ  ４０２とＦＥ  ４０６との間のすべての制御プロトコルおよび管理メッセージは、ＦＥ／ＣＥトランスポート・プロトコルを使用してトンネリングされるということである。
【００７４】
ＯＳＰＦプロトコルについて実験を実行、実施するテストベッドのセットアップは、図７に示されているものと同じである。ＯＳＰＦは、動的バインディング・プロトコルが収束し、初期ＣＥ／ＦＥバインディングが実行された後にのみ起動される。上述のように、ＣＥ  ４０２毎に１つのＯＳＰＦインスタンス８００が実行され、１つまたは複数のＦＥ  ４０６を制御することができる。例えば、図７のＣＥ３ｐ  ７３０は、ＦＥ３ａ  ７３６、ＦＥ３ｂ  ７３８、およびＦＥ３ｃ  ７４０を制御し、単一エンティティ（ＮＥ３）を形成する役割を持つが、ＣＥ４ｐ  ７３２およびＣＥ５ｐ  ７３４は、それぞれＦＥ４  ７４２およびＦＥ５  ７４４を制御する役割を持つ。ＯＳＰＦの観点から、それぞれのＣＥ  ４０２は、ネットワーク内のノードとして見られ、ＯＳＰＦ近隣要素は、基礎となる物理的ＦＥ  ４０６近隣要素に基づいて確定される。
【００７５】
ＯＳＰＦ近隣要素が確定され、ネットワーク内のすべてのノードがそのリンク状態データベースを収束させた後、ＯＳＰＦはダイクストラの最短経路優先（ＳＰＦ）アルゴリズムを実行してルーティング・テーブルを決定する。ルーティング情報が、他のすべてのルーティング・プロトコル（例えば、ＢＧＰ、静的）からルート情報を集約し、ＦＩＢにダウンロードされる必要がある所定のデスティネーションに対し可能な最良のルートを選択するルーティング・テーブル・マネージャ（ＲＴＭ）に注入される。ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例における転送エンジンはリモート・デバイス上に配置されているため、ルート入力情報は、ルート更新メッセージ上でＦＥ／ＣＥトランスポート・プロトコルを使用してＣＥ  ４０２からＦＥ  ４０６に伝送される。ＦＥ  ４０６は、このメッセージを受信して、情報を転送エンジンにダウンロードし、更新の成功に関してＣＥ  ４０２に応答を返す。ルートを更新できなかった場合、ＣＥ  ４０２は、この更新メッセージを再びＦＥ  ４０６に送信する作業を再試行する。
【００７６】
実験結果および測定基準
図７に示されているテストベッドで実験が行われた。ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例におけるＯＳＰＦルーティング・プロトコルのパフォーマンスが評価され、従来のアーキテクチャのものと比較される。すべての結果は、１０回の実験から得られた値を平均することにより計算された。（１）ネットワーク収束時間、（２）プロトコル・メッセージ・カウント、および（３）ルート変更カウントの３つの測定基準が評価された。ネットワーク収束時間は、イベント変更が検出されてからネットワーク内のすべてのルータが更新されたルーティング・テーブル・エントリとともに定常状態に到達するまでに実行される結合として定義される。イベントは、リンクまたはノードの障害もしくは回復とすることが可能である。収束時間が小さい場合、ネットワークが変更を受けた後に素早く安定になるとロバストなネットワークであることを示す。検出時間は両方のアーキテクチャで共通であり、知られている方法により最適化することができるため、イベント検出はこの測定基準の一部として含まれない。プロトコル・メッセージ・カウントは、ネットワークが安定するまで障害イベントに続いてネットワーク内のルータにより処理されるＯＳＰＦプロトコル・メッセージの個数として定義される。これは、障害の結果としての処理負荷のスパイクの測定である。短時間のうちにメッセージ・カウントが高い場合、輻輳が発生している可能性があり、パケットの喪失、プロトコル状態マシン内のタイムアウト、およびネットワーク不安定が生じることになる。ルート変更カウントは、ネットワークが安定するまで障害イベントに続いてネットワーク内のルータにおいて変更されたルートの個数として定義される。これもまた、短時間のうちに何回もルート変更があると、ネットワーク安定性にマイナス影響を及ぼす可能性がある。
【００７７】
収束時間
従来のルータ・アーキテクチャとＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例の間の異なるパフォーマンス測定基準を比較するために、（１）単一のリンクおよび（２）単一のノード（複数リンク）に対する障害およびその後の回復という２つの事例が評価される。これらの実験で、ＦＥ５ａとＦＥ６ａとの間のリンクは、単一のリンク障害シナリオに使用され、ノードＦＥ６ａは、単一のノード障害シナリオに使用された。同じコアＯＳＰＦ実装および既定の構成値は、従来のアーキテクチャとＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例との比較に使用された。ＳＰＦホールド・タイマーおよびＳＰＦ遅延タイマーは、障害／定常状態への回復の間の時間であるＯＳＰＦ収束時間を決定する際に重要な役割を果たす。ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例では、ＳＰＦホールド時間（つまり、連続するＳＰＦ実行の間に待つ時間）は、既定値である１０秒に設定され、ＳＰＦ遅延時間（つまり、データベース変更を受け取った後でさえもＳＰＦを実行するまでに待つ時間）は５秒に設定される。これらのタイマーは、あまりに頻繁なＳＰＦ計算を行わないようにすることによりルーティングの不安定さを防いだ。
【００７８】
実施された実験に対する障害／定常状態への回復の後の平均ＯＳＰＦ収束時間は、従来のアーキテクチャおよびＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例について以下の表３にまとめられている。以下の表に示されているように、ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例に対する結果は、従来のアプローチに対する結果よりもわずかによい。ＳｏｆｔＲｏｕｔｅｒアーキテクチャのＯＳＰＦ近隣要素の総数は従来のアーキテクチャに比べて少ない（ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例では単一ＮＥ  ５００として振る舞う複数のデバイスを集約できるため）のでＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例は、一般に、よいと期待されるが、収束時間はリンク状態データベース同期処理に関わるさまざまなＯＳＰＦタイマーにより決定されるため（また、要素の個数の全体的低減はあまり大きくない、つまり、１１ノードから８ノードにすぎないという事実から）、差は小さい。
【表３】
2006135975.tif 000005
【００７９】
メッセージおよびルート変更カウント
ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例と従来のアーキテクチャの間で他の２つのパフォーマンス測定基準の結果を比較した。ＯＳＰＦメッセージの総数をルート更新／変更の総数と比較した。リンクまたはノードが故障するか、または回復する（または、新しく現れる）と、ＯＳＰＦは、ネットワーク全体を通してフラッディングされるリンク更新メッセージをトリガする。すべてのノードに関するリンク状態データベースが同期し、定常状態に到達すると、ダイクストラのＳＰＦアルゴリズムを使用して、それぞれのデスティネーションの最短経路が計算され、それに応じて、ルートが更新される。表４は、従来のアーキテクチャ（ＴＲ）およびＳｏｆｔＲｏｕｔｅｒアーキテクチャ（ＳＲ）の実施例に対する結果をまとめたものである。表４は、両方の測定基準において、ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例が最後には得することを示している。またもや、これは、全ノードおよびＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例における対応する近接要素の個数が少ないからである。そのため、ＯＳＰＦは収束が速かっただけでなく、ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例ではフラッディングされたメッセージも少なく、引き起こされたルート変更の回数も少ない。
【表４】
2006135975.tif 000006
【００８０】
シミュレーション結果
より大きなトポロジの場合にこれらの測定基準に対する障害の影響について、シミュレーションで調べた。ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例で可能な最適化を評価するために、シミュレータを使用した。シミュレータは、シミュレートされるネットワーク内の各ルータについて実際のソフトウェア・プログラム（ｏｓｐｆｄ）のコピーを実行し、これにより、従来のアーキテクチャに合わせて最適化されているＯＳＰＦ実装を使用し高忠実度の評価を行えた。このシミュレータは、以下のようにＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例においてＯＳＰＦパフォーマンスを評価するために拡張された。転送および制御プレーンは分離された。ソフトウェア・プログラムは、ＣＥ  ４０２上でリモートから実行された。複数ルータ（ＦＥ  ４０６）という概念がソフトウェア・プログラムに導入された。外部および内部リンクという概念もソフトウェア・プログラムに導入された。単一のリンク状態データベースが、ソフトウェア・プログラム内で維持され、実行されたが、それぞれのＦＥ  ４０６の観点からダイクストラのＳＰＦアルゴリズムを実行することにより導かれるＦＥ  ４０６毎に一意的なルーティング・テーブルに対応するように修正された。ＯＳＰＦのアプローチ１および３のシミュレーションを行い、従来のアーキテクチャと対比して、ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例における性能向上の範囲を例示した。
【００８１】
評価では、Ｎノード・リングおよび完全メッシュ・トポロジが、標準的なＩＳＰポップ・レベル・トポロジ（２０ノード、４４リンクのＴｉｅｒ  １  ＩＳＰトポロジ、図６を参照）とともに考察された。リンク伝播遅延は、すべてのリンクについて１０ミリ秒に設定された。この３つのパフォーマンス測定基準は、これらのトポロジが、リンクまたはノード障害／回復などの変更を受けたときに評価された。
【００８２】
収束時間
単一リンク障害の後の収束時間測定基準に対する結果を得た。ＳＰＦ計算の実行回数を決定する、ＳＰＦ遅延タイマーは、１秒に設定された。従来のルータ・アーキテクチャ（ＴＲ）のパフォーマンスを、１ノードにつき１つのＯＳＰＦプロセスで、ＳｏｆｔＲｏｕｔｅｒアーキテクチャ（ＳＲ）の実施例におけるＯＳＰＦ最適化アプローチ１のパフォーマンスと比較した。アプローチ１では、ＴＲとＳＲの両方の結果として、収束後、ルーティング変更の回数は同じであり、ルーティング・テーブルは同一になった。ネットワーク全体を管理する１つのＣＥ  ４０２および２つのＣＥ  ４０２の事例を考察した。すべてのＣＥ  ４０２は、制御されるすべてのＦＥから高々、Ｎ／１０ホップだけ離れている。（この条件で感度分析も実行した。）ネットワーク全体を管理する１つのＣＥ  ４０２の事例は、ＯＳＰＦプロトコル・メッセージ交換が実行されないことを意味する。ＣＥ  ４０２は、リンク障害イベントを通知されると、すべてのＦＥ  ４０６に対するすべてのペアＳＰＦ計算を単純に実行し、更新されたＦＩＢをＦＥ  ４０６にダウンロードした。ネットワーク全体に対し１つのＣＥ  ４０２を用意することは大きなネットワークについてはスケーラブルでない場合があるが、小規模から中規模までのネットワークについては非常に効率的であると考えられる。さらに、１つの論理ＣＥ  ４０２があるとしても、ＣＥ  ４０２は、ホット・フェイルオーバーを採用し、リンク接続性の高い、丈夫なマルチブレード・ラック・サーバ上に実装することができ、その結果可用性を高められる。
【００８３】
図１０は、実験により得られた平均収束時間とリング・トポロジ内のノードの個数とを対比したグラフである。それぞれのデータ点は、１００回の実験から得られた収束時間の平均である。すべての場合において、収束時間は、一般に、ノードの個数が増えるとともに増大した。しかし、従来のアーキテクチャでは、収束時間の増大率は、ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例における増大率に比べてかなり高い。これは、Ｎ個のＯＳＰＦプロセスを実行するオーバーヘッドが高く、その結果、従来のアーキテクチャではメッセージ処理負荷が高くなるからである。最後に、ネットワーク全体に対する１つのＣＥ  ４０２のＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例のインスタンス化の結果として収束時間は最低となるが、それは、ＯＳＰＦプロトコル処理オーバーヘッドが非常に小さいからである。
【００８４】
図１１は、実験により得られた平均収束時間と異なる２０ノード・トポロジとを対比したグラフである（つまり、リング、ＩＳＰ、およびメッシュ）。従来のアーキテクチャでは、ノード次数がリンクからＩＳＰへ増えると、収束時間は、１６４０ｍｓから１４８１ｍｓに改善した。しかし、トポロジが完全接続メッシュになると、収束時間はわずかに増大した（１４８１ｍｓから１５１１ｍｓに）。これは、複数の経路に到着するＯＳＰＦメッセージが増え、それらを処理する負荷がかかったためである。ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例の場合、収束時間値は、すべてのアーキテクチャについて低かった。さらに、ＣＥ  ４０２とＦＥ  ４０６との間の最悪の距離（両方の場合においてＮ／１０ホップに設定）で収束時間が決まるので、リング・トポロジとＩＳＰトポロジとの収束時間値の差はごくわずかしかない
【００８５】
図１２は、実験により得られた平均収束時間と１００ノード・リング・トポロジのＳＰＦ遅延タイマー値とを対比したグラフである。あるＯＳＰＦベンダの実装ではＳＰＦ遅延タイマーの標準値は５秒である。ＳＰＦ遅延タイマー値を小さくすることにより収束時間を積極的に短縮できるかどうかを調べるために、ＳＰＦ遅延タイマーを５０ミリ秒から５秒までの範囲で変えた。ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例の場合のＣＥ  ４０２は、すべてのＦＥ  ４０６から高々１０ホップだけ離れており、ネットワーク全体を管理するＣＥ  ４０２が１つ存在した。図１２から、ＳＰＦ遅延タイマーは、収束時間を決定するうえで大きな役割を果たすことは明らかである。ＳＰＦの計算はコンピュータを集中的に使用するが、それでも数ミリ秒程度要するだけである。そのため、ＳＰＦ遅延値（特に、数秒程度の場合）および伝播遅延（リングなどの直径の大きなネットワークの場合）は支配的になる傾向があった。
【００８６】
図１３は、１つのＣＥ  ４０２がＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例を管理する、実験により得られた平均収束時間とリング・トポロジ内のノードの個数とを対比したグラフである。ＣＥ  ４０２の配置に対する感度は、ＣＥ  ４０２がこのＦＥ  ４０６から離れている距離である最悪の場合のホップ数を変えることにより評価された。ＣＥ  ４０２でＯＳＰＦ計算が実行されたため、ＦＥ  ４０６とＣＥ  ４０２との間にメッセージ待ち時間があるため、ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例のオーバーヘッドは高かった。ＳＰＦ遅延タイマーは、収束時間の積極的短縮を考慮して５０ミリ秒に設定された。
【００８７】
ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例における最悪の場合の収束時間は、ＣＥ  ４０２がＦＥ  ４０６からＮ／２ホップだけ離れている場合に対応していた（Ｎ／２はリングに対するネットワーク直径である）。この場合、ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例および従来のルータ・アーキテクチャの収束時間はほとんど同じであった（図１３ではラインは重なっている）。これは、従来のルータ・アーキテクチャの最悪の場合の伝播遅延（ネットワーク直径）がＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例における最悪の場合の伝播遅延（ＣＥ−ＦＥ距離）と同じだからである。
【００８８】
そのため、リンク障害後の収束時間は、ＳＰＦ遅延タイマーが任意に小さくされた場合に伝播遅延により決まった。しかし、ＳＰＦ遅延タイマーはネットワークの不安定性を防ぐので、ＳＰＦ遅延タイマーに対する非常に小さな値は、１００個のＯＳＰＦプロセスを使用する従来のルータ・アーキテクチャのネットワークの不安定を引き起こし、したがって、１〜３個のＯＳＰＦプロセスを使用するＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例のネットワークの不安定を引き起こす可能性がかなり高い。
【００８９】
図１４は、実験により得られた障害回復時間とノードの個数とを対比したグラフである。ｍｓ単位の平均障害回復時間を縦軸に、ノード数（０、１０、．．．、１００）を横軸に示す。図７に示されているデータは、Ｎノード・リング・ネットワーク上のシミュレーションから得られたデータである。このシミュレーションでは、イベントは単一リンク障害であり、最短経路優先（ＳＰＦ）遅延タイマーは１秒に設定され、これがＳＰＦ計算の実行回数を決定する。このシミュレーションでのＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例では、ＣＥはそのＦＥから高々Ｎ／１０ホップだけ離れていると仮定される。ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例では、ＯＳＰＦプロセスは数桁少なく、障害回復が速くなる。このシミュレーションでは、ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例に対する最低障害回復時間はネットワーク全体に対するルーティング計算を実行する１つのＣＥ／ＯＳＰＦプロセス分である。
【００９０】
図１５は、実験により得られた障害回復時間と５０ｍｓのＳＰＦ遅延時間についてのノードの個数との対比を示すグラフである。５０ｍｓのＳＰＦ遅延タイマーは、わずかのＯＳＰＦインスタンスを使用するＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例の場合には現実的であるが、この設定だと、数百個のＯＳＰＦインスタンスを使用する従来アーキテクチャではネットワークの不安定性が生じる可能性がある。５０ｍｓの障害回復時間は、ＳｏｆｔＲｏｕｔｅｒネットワークの実施例が１つまたは２つの一次ＣＥ／ＯＳＰＦプロセスにより管理される場合に実現可能であり、ＣＥからそのＦＥまでの伝播遅延は小さい。ＣＥを慎重に配置することは、ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例の実施形態を設計する作業の一部である。
【００９１】
メッセージおよびルート変更カウント
２０ノードのリング、メッシュ、およびＩＳＰトポロジを使用して、ネットワークの変更に続いて発生するＯＳＰＦメッセージおよびルート変更の数を決定する一連の実験を実施した。ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例の場合、１つのＣＥ  ４０２にネットワーク全体を管理させることは、交換されるプロトコル・メッセージは０個であろうから、メッセージングのオーバーヘッドに関して最適であろう。上述のように、ネットワークが地理的に分散している場合、ネットワークを管理する２つまたは３つのＣＥ  ４０２は、ＦＥ  ４０６とＣＥ  ４０２との間の伝播待ち時間を短縮し、その結果、収束が高速化される。そこで、ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例を管理する３つのＣＥ  ４０２の場合に対する控えめな結果が提示されている。
【００９２】
従来の分散ＯＳＰＦ実装（ＴＲ）は、シミュレートされ、ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例のアプローチ１および３は、ＳＲ１およびＳＲ３として識別される。ＳＲ１は、すべての内部リンクを広告するので、ＴＲと比較してルート変更回数が減るが、ネットワーク内のＯＳＰＦインスタンス８００が少ないため、ＳＲ１は交換されるＯＳＰＦメッセージの数を大幅に減らす。ＳＲ３は、さらに、内部リンクを広告しないことによりＳＲ１を最適化し、その結果、ルート変更はＳＲ１よりも少なくなる。
【表５】
2006135975.tif 000007
【００９３】
表６に、結果が示されている。まず、ネットワークの平均ノード次数が増えると、変更イベントの後のＯＳＰＦメッセージおよびルート変更の数が増大することが観察された。そこで、メッシュ・トポロジは最高のメッセージ・カウント数およびルート変更回数を示し、その後にＩＳＰトポロジが続き、最後に、リング・トポロジが続いた。
【００９４】
第２に、ＳＲ１は、ＴＲと比較してネットワーク内で処理される全ＯＳＰＦメッセージの数を大幅に減らし、リングおよびＩＳＰトポロジの場合に、単一のＣＥ  ４０２により処理される最大ＯＳＰＦメッセージを大幅に減らすことが観察された。メッセージ削減の利得割合は、リング・トポロジについては最高、メッシュ・トポロジについては最低であった。これは、リング（メッシュ）トポロジは最低数（最高数）の外部リンクを持つためであり、ＳＲ１はすべての外部リンク上で近隣要素を確立した。ＳＲ１は、さらに、２つのＮＥ  ５００間の並列外部リンク上で近隣要素を確立しないことにより最適化することが可能であり、その結果、交換されるメッセージがさらに削減される。
【００９５】
第３に、ＳＲ１は、ＴＲと比較してルート変更測定基準に関する低減を行わないことが観察されたが、それは、ＳＲ１が、同一のルーティング・パフォーマンスをＴＲとして達成するためにすべてのリンクを広告するからである。ＳＲ３は、内部リンクを広告しないので、ＴＲ／ＳＲ１と比較してルート変更回数を大幅に減らすことができた。内部リンクが、互いに近いＦＥ  ４０６を接続する高帯域幅リンクであった場合、内部リンクは、ゼロ・コスト・リンクとみなすことが可能であり、したがって、ＳＲ３は、そのようなネットワークに適しているであろう。ここでもまた、前のように、ネットワーク内の全ルート変更の割合削減は、リング・トポロジからメッシュ・トポロジへと外部リンクの割合が増大するとともに減った。
【００９６】
最後に、ＩＳＰトポロジに対する結果を考察した。ＳＲ１は、ノード障害の後に処理されるメッセージの総数を５５３から２２に減らし、任意のノードにより処理されるメッセージの最大数を６４から１０（８４％の削減）に減らすことができた。従来のルータ・アーキテクチャでは、ＩＳＰトポロジ内のすべてのノードは、障害の後のわずかの時間内に最大メッセージ・カウントを処理できなければならない。それとは対照的に、ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例のＣＥ  ４０２は、最速のプロセッサを備えるサーバであり、低速の制御用プロセッサを備える従来のルータ・アーキテクチャよりも少ないメッセージを処理する。さらに、ＳＲ３では、ネットワーク内のルート変更回数も、１０９５から４０９に減らされた。したがって、アプローチＳＲ１／ＳＲ３を使用するＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例は、ネットワーク障害の結果として生じる過負荷シナリオを処理できる装備を持ち、そのため、ネットワークの安定性が向上する。
結果のまとめ
【００９７】
障害の後のＯＳＰＦ収束は、信頼できるフラッディング・メカニズムのおかげで現在の分散ネットワークではきわめて効率的である。現在のネットワーク内の収束時間の支配的部分は、ＳＰＦ遅延タイマーによるものである。数百個のＯＳＰＦプロセスが含まれる現在のネットワークのネットワーク不安定性を軽減するために既定のＳＰＦ遅延タイマー値である５秒が必要であるが、ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例においてＯＳＰＦ最適化を行えば、ＳＰＦ遅延タイマー設定を積極的な設定にすることにより収束時間を約１０ｍｓ以下に下げることができるが、それはネットワーク全体を管理するために２つまたは３つのＯＳＰＦのみがあればよいからである。最後に、ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例におけるＣＥ  ４０２とＦＥ  ４０６との間の待ち時間は、収束時間に関して大きな役割を果たし、したがって、上述のような慎重な計画を行うことで、ＣＥ  ４０２をそのＦＥ  ４０６に近づけることができる。
【００９８】
ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例におけるＯＳＰＦ最適化は、現在のネットワークと比較して、メッセージ処理およびルート変更のおかげで過負荷の低減にさらに劇的な影響を持つ。より少ないＯＳＰＦプロセスでネットワーク内のすべてのルータを管理できるようにすることにより、３つのＣＥ  ４０２がネットワークを管理する場合であっても、メッセージ・カウントを最大約８０％まで削減できる。メッセージ・カウント削減は、１つのＣＥ  ４０２の場合には１００％となる。さらに、ＮＥ  ５００の内部リンクがＯＳＰＦメッセージで広告されない場合、ルート変更回数も、著しく減らせる。したがって、ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例の実施形態では、ネットワーク安定性は、収束時間、メッセージ・カウント、およびルート変更回数により測定されるが、より少ないＣＥ  ４０２にネットワーク内のすべてのＦＥ  ４０６を管理させることにより著しく改善できる。
【００９９】
ドメイン間ルーティング
ドメイン間ルーティング・プロトコル、特にＢＧＰは、ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例において配備され、その結果多くの利点が得られる。
【０１００】
図１６は、ルート・リフレクタを持つ従来技術のネットワークを示している。このネットワークは、ルート・リフレクタを備えるＢＧＰの標準的な配備である。外部ＢＧＰ（Ｅ−ＢＧＰ）１６０６を使用する大きなＡＳネットワーク１６０４内には複数のルート・リフレクタ・クライアント１６００およびリフレクタ１６０２がある。この配備には、２つの主要な欠点がある。特に、特定の条件の下では、ネットワーク１６０４は、ルータの部分集合が安定したルーティング状態に到達しなくてもルーティング情報を交換することができる永続的なルート振動状態に入る可能性がある。ルート・リフレクタ・アーキテクチャに関する他の問題は、内部ＢＧＰ（Ｉ−ＢＧＰ）の信頼性である。１つのＩ−ＢＧＰセッションの障害は完全メッシュＩ−ＢＧＰアーキテクチャの場合の２つのルータのみに影響するが、２つのルート・リフレクタ１６０２の間のセッションの同じ障害により、ネットワーク１６０４が分割され、その結果、信頼性が著しく低下する可能性がある。
【０１０１】
図１７は、ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例の一実施形態を示している。ＢＧＰ  ＡＳネットワーク１７０６内には、ＦＥ／ＣＥプロトコル・クライアント１７００、ｌ−ＢＧＰメッシュ１７０２があり、より小さなＥ−ＢＧＰ  １７０４通信が実行される。図１７には、ＣＥ  ４０２間で維持できる完全Ｉ−ＢＧＰメッシュ１７０２が示されている。これは、図１６に示されている従来技術のＢＧＰ  ＡＳネットワーク１６０４でのようにルート・リフレクタ１６００を使用して発生しうるネットワーク不安定性を排除する。ＣＥ  ４０２は、１：Ｎ冗長性を採用して信頼性を高めることができる。ＦＥ  ４０６は、単純なＦＥ／ＣＥプロトコルを実行するだけでよい。ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例におけるＢＧＰ配備の場合では、ＢＧＰを実行するＣＥ  ４０２の個数は、通常、ルータの個数よりも少なくとも１桁小さい。そのため、完全Ｉ−ＢＧＰメッシュは、ＣＥ  ４０２間で容易に維持できる。ＣＥ  ４０２は、標準プロトコルを使用して適切な転送テーブルをすべてのＦＥ  ４０６にダウンロードする。したがって、永続的なルート振動問題は、ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例では自明な形で解決され（ルート・リフレクタがないため）、その結果、ネットワークの可用性が高まる。さらに、ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例では、Ｉ−ＢＧＰメッシュは、ルータの制御用プロセッサでの１：１冗長性に比べて、１：Ｎ（Ｎ＞１）などのより高い冗長度を採用するサーバ間に置かれる。そのため、ＣＥ  ４０２がマルチホーミングで接続され、フェイルオーバーのためネットワーク内に複数のＣＥ  ４０２があると仮定すれば、ＢＧＰの安定性および信頼性は、ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例では大幅に改善することができる。ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例のＢＧＰの実装では、ＩＧＰおよびＩ−ＢＧＰではなく標準プロトコルを使用してＦＥ  ４０６と通信するので、ＦＥ  ４０６上のソフトウェアが簡素化され、またＩ−ＢＧＰメッシュが単一のＡＳ内のＣＥ  ４０２サーバ間で使用される。
【０１０２】
ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例では、プロトコル集約、ネットワーク設計、およびブートストラッピングのパラドックスなどの多くの技術的難題を克服している。ＣＥ  ４０２の単一のプロトコル・インスタンス化では複数のＦＥ  ４０６を管理する場合に、ＯＳＰＦ／ＢＧＰのようなプロトコルがどのように動作するかが決定された。ＯＳＰＦの場合、予備段階の結果から、ＳｏｆｔＲｏｕｔｅｒネットワークの実施例が１つまたは２つの一次ＣＥ／ＯＳＰＦプロセスにより管理される場合に約５０ｍｓの障害回復時間が実現可能であり、ＣＥ４０２からそのＦＥ  ４０６までの伝播遅延は小さいことがわかる。ＢＧＰの場合、完全ＢＧＰメッシュは、少数のＣＥ  ４０６間で維持され、ルート／リフレクタ・アーキテクチャの場合に発生しうるネットワークの不安定性をなくすことができる。ＣＥ  ４０２をネットワーク設計にどのように入れ、どのＣＥ  ４０２でどのＦＥ  ４０６を管理すべきかが決定された。再帰的グラフ２分割法に基づく方法の実施例では、ＣＥ  ４０２をどこに入れ、それぞれのＣＥ  ４０２でＦＥ  ４０６のどの集合を管理すべきかを識別している。ブートストラッピングのパラドックス（つまり、ＦＥ  ４０６は、パケットをＣＥ  ４０２にルーティングするために更新された転送テーブルを必要とするが、ＣＥ  ４０２のみが転送テーブルを更新できる）は、この循環性を破る発見プロトコルの実施例により解決された。このプロトコルを使用すると、それぞれのＦＥ  ４０６はＣＥ  ４０２にバインドすることができ、それらの間に単純なルーティング機能を提供する。
【０１０３】
ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例の一応用例では、微分機能をＥｔｈｅｒｎｅｔ（登録商標）に付加する。Ｍｅｔｒｏ  Ｅｔｈｅｒｎｅｔ（登録商標）の配備は急速に拡大中である。仮想パス・リンク（ＶＰＬ）は、広域配備の重要な機能であるが、純粋なＥｔｈｅｒｎｅｔ（登録商標）スイッチングからは逸脱している。ＭＰＬＳ転送ハードウェアおよびＩＰ制御プレーンが必要である。新しいチップでは、転送サポート機能を集積化している。ＶＰＬに対する制御プレーンの必要条件には、複雑なソフトウェアを実行するためのＥｔｈｅｒｎｅｔ（登録商標）スイッチが含まれる。ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例は、すべてのＥｔｈｅｒｎｅｔ（登録商標）スイッチ上で複雑なＩＰソフトウェアを必要としないことによりネットワークを簡素化するＣＥ  ４０２を含む。カスタマイズされた経路計算を有効にすると、微分機能を持つＣＥ  ４０２を使用できる。
【０１０４】
ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例の他の応用例では、ＰＯＰでのルーティングを統合する。ＰＯＰに対する総コストは、ＳｏｆｔＲｏｕｔｅｒアーキテクチャを使用することで著しく低減できるが、それは、専用ハードウェアではない市販のハードウェア、複数のベンダによる標準ベースのＦＥ  ４０６を使用しており、またルータ・インターフェイスに対するＥｔｈｅｒｎｅｔ（登録商標）のような価格決定力を持つからである。オープン・ソース・ベースのルーティング・ソフトウェアでは、多数のコントリビュータからなる大規模なコミュニティ間に分散している開発能力を活用する。必要なコントローラは比較的少なくて済む。今日、１５個のルータがあるＰＯＰは、３０個のコントローラを持つが（１：１の冗長性）、ＳｏｆｔＲｏｕｔｅｒネットワークでは、２つから４つ程度のＣＥ  ４０２しか必要でない。
【０１０５】
図１８は、ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例の一実施形態によるＰＯＰ（Ｐｏｉｎｔ  Ｏｆ  Ｐｒｅｓｅｎｃｅ）における統合ルーティングを示す。ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例のさらに他の応用例では、ＰＯＰでのルーティングを統合する。ＰＯＰ  Ｅｔｈｅｒｎｅｔ（登録商標）ネットワーク１８０２は、コア・ルータ１８０４によりコア・ネットワーク１８０６に接続される。ＰＯＰ  Ｅｔｈｅｒｎｅｔ（登録商標）ネットワーク１８０２は、さらに、ＳｏｆｔＲｏｕｔｅｒサーバ（ＣＥ）４０２、認証、許可、およびアカウンティング（ＡＡＡ）サーバ１８０８に接続される。デジタル加入者回線多重化装置（ＤＳＬＡＭ）１８１０およびエッジ・ルータ１８１２（例えば、  ＩＰ／ＡＴＭ／ＦｒａｍｅＲｅｌａｙ）は、ＦＥ  ４０６に接続され、これらは、ＰＯＰ  Ｅｔｈｅｒｎｅｔ（登録商標）ネットワーク１８０２に接続される。ＰＯＰに対する総コストは、ＳｏｆｔＲｏｕｔｅｒを使用することで著しく低減できるが、それは、専用ハードウェアではない市販のハードウェア、複数のベンダによる標準ベースのＦＥ  ４０６を使用しており、またルータ・インターフェイスに対するＥｔｈｅｒｎｅｔ（登録商標）のような価格決定力を持つからである。オープン・ソース・ベースのルーティング・ソフトウェアでは、多数のコントリビュータからなる大規模なコミュニティ間に分散している開発能力を活用する。必要なコントローラは比較的少なくて済む。今日、１５個のルータがあるＰＯＰは、３０個のコントローラを持つが（１：１の冗長性）、ＳｏｆｔＲｏｕｔｅｒネットワークでは、２つから４つ程度のＣＥ  ４０２しか必要でない。
【０１０６】
要約すると、ルータ・ネットワークは、次第に複雑化してきているということである。新しいアプリケーションおよびパフォーマンス要件が出現することで、より多くの機能がＩＰに付加される。ルータにあまりも多くのＩＰ機能が組み込まれる結果、ネットワークの複数のルータ内で複雑な機能が重複することになる。ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例ではルータのハードウェアをソフトウェアから分離する方法で、この問題に対処し、またこの方法は、他の主要な利点についても有望である。ＳｏｆｔＲｏｕｔｅｒアーキテクチャの一実施例では、ルータの制御およびトランスポート・プレーンは、トランスポート・プレーンがパケット転送要素を含み、制御プレーンが制御要素サーバおよびフィーチャ・サーバを含むように分離される。制御プレーンおよびトランスポート・プレーンは、標準プロトコルを使用して通信する。この概念のいくつかの利点として、複雑な機能の集中化、コスト低減、オープンＡＰＩおよびインクリメンタルな配備による新しいアプリケーションの導入の高速化および低コスト化、およびとりわけ、スケーラビリティ、信頼性、およびセキュリティの向上が挙げられる。
【０１０７】
図１９は、コンピュータを示す高水準のブロック図である。コンピュータ１９００を採用して、本発明のいくつかの実施形態を実装できる。コンピュータ１９００は、プロセッサ１９３０とともに、さまざまなプログラム１９４４およびデータ１９４６を格納するためのメモリ１９４０を備える。メモリ１９４０は、さらに、プログラム１９４４をサポートするオペレーティング・システム１９４２を格納することもできる。
【０１０８】
プロセッサ１９３０は、電源、クロック回路、キャッシュ・メモリなどの従来のサポート回路とともに、メモリ１９４０に格納されているソフトウェア・ルーチンの実行を補助する回路と連携する。したがって、本明細書でソフトウェア方法として説明される工程のいくつかは、ハードウェア内に、例えば、プロセッサ１９３０と連携してさまざまな方法工程を実行する回路として実装することができる。コンピュータ１９００は、さらに、コンピュータ１９００と通信するさまざまな機能要素間のインターフェイスを形成する入出力（Ｉ／Ｏ）回路も備える。
【０１０９】
コンピュータ１９００は、本発明によりさまざま機能を実行するようにプログラムされた汎用コンピュータとして示されているが、本発明は、ハードウェアで、例えば、特定用途向け集積回路（ＡＳＩＣ）またはフィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）として実装することができる。したがって、本明細書で説明されている工程段階は、ソフトウェア、ハードウェア、またはそれらの組み合わせにより等しく実行されるものとして広く解釈することを意図されている。
【０１１０】
本発明は、コンピュータ命令がコンピュータにより処理されると、本発明に方法および／または技術が呼び出されるか、または何らかの方法により提供されるようにコンピュータの動作を適合させるコンピュータ・プログラム製品として実装することができる。本発明の方法を呼び出す命令は、固定または取り外し可能媒体に格納するか、放送媒体または他の信号伝送媒体でデータストリームを介して送信するか、および／または命令に従って動作するコンピューティング・デバイス内の作業用メモリ内に格納することができる。
【０１１１】
本発明は、コスト低減、新しい収益機会、スケーラビリティの増大、信頼性の付加、およびセキュリティの向上を含む、顧客向けに多くの利点を有する。コスト低減は、資本支出が低く、専用制御プレーン・サーバを備える商品化された標準ベースのハードウェアのおかげであり、これは管理点が少ないこと、また運用費用が少ないことを意味する。オープン・アプリケーション・プログラミング・インターフェイス（ＡＰＩ）およびインクリメンタルな配備を利用して容易に追加される新しいサービスをサポートするネットワーク・ベースのアプリケーションは、集中化された管理を通じて簡素化されるので新しい収益機会ができる。集中化された制御プレーン・サーバはきちんと確立されているサーバ・スケーリング技術を使用して容易に拡張できるため、スケーラビリティが高い。転送要素は、縮小されたソフトウェアおよびサーバ・ベースの制御プレーン内に容易に実装できる他の信頼性増強メカニズム（例えば、フェイルオーバーおよび過負荷制御）の利用によりロバスト性を高められるため、信頼性がさらに向上する。集中化された制御プレーン・サーバは、境界線防御システム、例えば、ファイヤウォールを使用することで容易にセキュリティ保護できるため、セキュリティが向上する。
【０１１２】
資本支出および運用支出が少ない。ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例では、制御要素と転送要素の革新曲線を分ける。ハードウェアのベンダは、高速化および高密度化に力を注ぐことができる。新しいソフトウェア・ベンダが市場に参入し、アプリケーションおよび扱いやすい管理機能の実現に集中できる。参入した競争力のある企業は低価格化をもたらすであろう。ＣＥは、高価なルータ制御基板の代わりに安価な汎用コンピューティング・ブレードで構成される。制御サーバは、多数のルータにより共有され、その結果、効率が向上する。複数のＣＥを備えることで、サーバ・プラットフォームの中央演算処理装置（ＣＰＵ）価格対性能比曲線を利用する。ＦＥは、ほとんどの場合、ハードウェア・ベースであり、ほとんど管理を要せず、レイヤ２デバイスに類似している。制御プレーン・サーバが少ないということは、管理点が少ないということである。構成設定を間違える可能性も少なくなる。
【０１１３】
ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例は、従来のネットワークよりも信頼性が高くなるように設計されている。ＦＥソフトウェアは、ＣＥソフトウェアよりも１桁単純であり、ＦＥはよりロバストである。これらの要素の間のＣＥおよびフェイルオーバーの戦略的配置により、ＣＥに接続できず複数の転送要素の島が立ち往生する重大なネットワーク分割の場合を除き、ネットワーク側で事前に指定された数の障害を処理することができる。
【０１１４】
制御点は比較的少なく、ルータの収束が高速化され、ネットワーク安定性が向上する。障害発生後に同期するＯＳＰＦリンク状態データベースの数が少ない。障害検出時間が変わらないと仮定すると、収束はより速い。これらのサーバ間の完全メッシュＩ−ＢＧＰが実現可能である。ＢＧＰルート・リフレクタ・アーキテクチャに関するいくつかのネットワーク不安定性問題を解消できる。
【０１１５】
セキュリティは、従来モデルと比較してＳｏｆｔＲｏｕｔｅｒアーキテクチャでは改善されている。専用ルータ・オペレーティング・システム（ＯＳ）は、Ｌｉｎｕｘなどのオープン・ソースの制御用ソフトウェアほどは広くテストされていない。ルータＯＳへの攻撃が、最近増えてきている。制御ブレードは、１、２台よりも多数あったほうがよい。悪意あるトラフィックにより生じる過負荷は、ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例のサーバ内の多数の制御ブレードに分散させることができる。さらに、侵入検出を行うため、複数のＳｏｆｔＲｏｕｔｅｒブレード・サーバ内で高度な統計分析を実行することもできる。制御ブレードを保護するファイヤウォールを別に用意することは何もないよりもましである。ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例の複数の実施形態で使用する制御プレーン・サーバが少ないほど、専用ファイヤウォールを使用するセキュリティ対策が容易に行える。独立信号ネットワークは、共有信号ネットワークよりもよい。ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例の複数の実施形態では、独立の信号ネットワークが制御サーバを接続することが可能である。
【０１１６】
ルータを転送および制御要素に 分解することは、上述のＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例の複数の実施形態の基盤である。転送要素は、パケット・フィルタリング、ＩＰパケット・ヘッダ上の最長プレフィックス照合、トラフィック管理、およびスイッチングなどの、ほとんど繰り返しのハードウェア集約パケットの処理タスクを実行する。これらの転送要素は、すべてのトラフィックをトランスポートし、またネットワーク全体に分散される。制御要素は、少なく、ネットワーク内の戦略的な位置に配置され、現在のルータのすべての制御ロジックを具現化する。その結果、転送要素に比べていっそうソフトウェア集約的で複雑なものとなっている。従来のルータは、高々２つの制御要素と同じ場所に配置された（静的に関連付けられた）転送要素の集合からなる。本発明では、制御要素を特定の転送要素から数ネットワーク・ホップだけ離すことができ、転送要素と制御要素との間のバインディングが動的である新しいパラダイムを導入する。ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例のいくつかの実施形態には、安定性改善および信頼性向上を含む多数の技術上の利点がある。シミュレーションおよびテストベッドの結果を基に、これらの利点を定量化した。少数の制御要素が多数の転送要素に対するルート計算を実行するアーキテクチャは、ルータを簡素化するだけでなく、制御プレーン状態のネットワーク規模のビューにアクセスしやすくする潜在的能力を持つ。
【０１１７】
前記の説明は本発明のさまざまな実施形態を対象としているが、本発明の基本的範囲から逸脱することなく本発明の他の実施形態およびさらなる実施形態を考案することができる。したがって、本発明の適切な範囲は、請求項により決定されるものとする。
【図面の簡単な説明】
【０１１８】
【図１】従来のルータを示すブロック図である。
【図２】ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例の高水準抽象化を示すブロック図である。
【図３】従来のルータ・アーキテクチャを示すブロック図である。
【図４】ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例の実施形態を示すブロック図である。
【図５】ネットワーク要素を例示するＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例の実施形態を示すブロック図である。
【図６】２０ノードおよび４４リンクの標準的なＴｉｅｒ  １  ＰＯＰ（Ｐｏｉｎｔ  Ｏｆ  Ｐｒｅｓｅｎｃｅ）レベルのインターネット・サービス・プロバイダ（ＩＳＰ）トポロジ上で使用されるような再帰的二分法を示すブロック図である。
【図７】プロトタイプ・テストベッドの実施例のブロック図である。
【図８】それぞれのルータが自リンク状態データベース（ＬＳＤＢ）を保持する開放型最短経路優先（ＯＳＰＦ）インスタンスを実行する、従来技術のネットワークを示すブロック図である。
【図９】それぞれの制御要素（ＣＥ）が複数の転送要素（ＦＥ）の代わりにＯＳＰＦインスタンスを実行するＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例の実施形態を示すブロック図である。
【図１０】実験により得られた平均収束時間とリング・トポロジ内のノードの個数とを対比したグラフである。
【図１１】実験により得られた平均収束時間と異なる２０ノード・トポロジとを対比したグラフである。
【図１２】実験により得られた平均収束時間と１００ノード・リング・トポロジのＳＰＦ遅延タイマー値とを対比したグラフである。
【図１３】実験により得られた平均収束時間とリング・トポロジ内のノードの個数とを対比したグラフである。
【図１４】実験により得られた障害回復時間とノードの個数とを対比したグラフである。
【図１５】実験により得られた障害回復時間と５０ｍｓの最短経路優先（ＳＰＦ）遅延時間についてのノードの個数との対比を示すグラフである。
【図１６】ルート・リフレクタを備える従来技術のネットワークを示すブロック図である。
【図１７】ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例の実施形態を示すブロック図である。
【図１８】ＳｏｆｔＲｏｕｔｅｒアーキテクチャの実施例の一実施形態によるＰＯＰ（Ｐｏｉｎｔ  Ｏｆ  Ｐｒｅｓｅｎｃｅ）における統合ルーティングを示すブロック図である。
【図１９】ＰＯＰにおけるＳｏｆｔＲｏｕｔｅｒネットワークの実施形態を示すブロック図である。
【図１】
2006135975.tif 000008
【図２】
2006135975.tif 000009
【図３】
2006135975.tif 000010
【図４】
2006135975.tif 000011
【図５】
2006135975.tif 000012
【図６】
2006135975.tif 000013
【図７】
2006135975.tif 000014
【図８】
2006135975.tif 000015
【図９】
2006135975.tif 000016
【図１０】
2006135975.tif 000017
【図１１】
2006135975.tif 000018
【図１２】
2006135975.tif 000019
【図１３】
2006135975.tif 000020
【図１４】
2006135975.tif 000021
【図１５】
2006135975.tif 000022
【図１６】
2006135975.tif 000023
【図１７】
2006135975.tif 000024
【図１８】
2006135975.tif 000025
【図１９】
2006135975.tif 000026