JP5625121B2 - ルーティング情報更新の優先順位付け - Google Patents

Description

本明細書において開示されるさまざまな例示的な実施形態は、一般に、ネットワークトラフィックのルーティングに関する。

パケット交換ネットワークは、今日のさまざまな形態の常に増加する通信量を可能にするために使用される。インターネットのようなネットワークを介するコンピュータ間の通信に加えて、パケット交換ネットワークは、テレビジョン、電話、およびラジオのような他のアプリケーションに関連付けられている情報の通信を可能にする。それらのアプリケーションおよび他のアプリケーションを通じて、エンドユーザは、遠く離れた距離にわたって多数の情報タイプを伝送および受信することができる。

そのような情報をその送信元からその宛先まで移動させるために、パケット交換ネットワークは、複数の相互接続されたルーティングデバイスを採用する。１つのルータがデータのパケットを受信すると、ルータは、パケットの宛先がどこに位置するかを決定して、パケットを次に最も近いルータに転送する。この次のルータは同様の手順に従い、このようにして、さながら「バケツリレー」のように、パケットは最終的にその宛先に配信される。

パケット交換ネットワークにおける１つの重大な問題は、各ネットワークに、各パケットが伝送されるべき「ネクストホップ（ｎｅｘｔ ｈｏｐ）」ルータを決定するために必要な情報を提供することである。理論的には、この情報はルータに手動でプログラムされてもよいが、ネットワークトポロジのサイズおよび動的な特性が、通常、この方法を実行不可能なものにしている。代わりに、ルータごとに各宛先への最善パスを自動的に決定するために、さまざまなプロトコルが開発されてきた。たとえば、オープンショーテストパスファースト（Ｏｐｅｎ Ｓｈｏｒｔｅｓｔ Ｐａｔｈ Ｆｉｒｓｔ）規格は、自律システム内のルータがシステム内のリンクの状態に関する情報を共有することを規定する。この情報を使用して、各ルータは、受信した各パケットが送信されるべき場所を決定する際に使用する転送テーブルを独立して作成することができる。ネットワーク状態が変化すると、各ルータは、それぞれの宛先が引き続き到達可能であり、選択されるそれぞれのパスが最適であるように、その転送テーブルを更新する。

オープンショーテストパスファーストのような規格は、ルーティング情報を生成することの問題に実用的な解決策をもたらすが、それらの規格は機能するまでに時間を要する。たとえば、ネットワークの変化が生じた直後、各ノードにおけるルーティング情報は、ある程度、古いものになっており不正確である。各ノードが変化の指示を受信して、ネットワークの新しい状態を決定し、最適なルーティングパスを決定して、転送テーブルを更新するまで、情報は古い状態のままである。ノードがネットワークに追加される、ノードがネットワークから除去される、ノードが障害状態に入る、ノードが障害状態から回復する、および他のネットワーク変化のイベントが頻発する可能性があるので、ルータの動作時間の相当の部分が、古いルーティング情報に従ってトラフィックを転送すること、または最新のルーティング情報を待つことに費やされる場合もある。

転送テーブルを更新するステップは、ルーティング情報を更新する際に特に大幅な遅延をもたらすことがある。自律システム内の他のノードに関連付けられているルーティング情報に加えて、各テーブルは、ネットワークの変化に応答して更新される必要のある自律システムの外部の他のノードおよび／またはサブネットの数千ものエントリを含む場合もある。しかし、さまざまな他のルーティングプロトコルは、他のルーティング情報を更新するために、最新の転送テーブルに依存する場合がある。たとえば、ラベル配布プロトコル（ＬＤＰ：ｌａｂｅｌ ｄｉｓｔｒｉｂｕｔｉｏｎ ｐｒｏｔｏｃｏｌ）またはリソース予約プロトコル−トラフィックエンジニアリング（ＲＳＶＰ−ＴＥ）のような、マルチプロトコルラベルスイッチング（ＭＰＬＳ：ｍｕｌｔｉ−ｐｒｏｔｏｃｏｌ−ｌａｂｅｌ−ｓｗｉｔｃｈｉｎｇ）関連のプロトコルは、ＭＰＬＳパスを確立するために転送テーブル内のルートを使用することができる。さらなる例として、レイヤ２トンネリングプロトコル（Ｌ２ＴＰ：ｌａｙｅｒ ２ ｔｕｎｎｅｌｉｎｇ ｐｒｏｔｏｃｏｌ）もまた、同様に転送テーブルを使用することができる。

したがって、ネットワーク変化イベントと複数のルーティングプロトコル間のネットワークルーティング情報のコンバージェンスとの間の時間を短縮する方法が必要とされている。特に、１つのプロトコルのルーティング情報を、別のプロトコルが他のルーティング情報を更新する前に、更新することに費やされる時間を短縮する方法およびネットワークノードを提供することが望ましいと考えられる。

ネットワークコンバージェンス時間を短縮する方法に対する現在の必要性を踏まえて、さまざまな例示的な実施形態の概要が提示される。以下の要約において、簡略化および省略が一部行なわれることがあるが、それは、本発明の範囲を限定するためではなく、さまざまな例示的な実施形態の一部の態様を強調し導入することが意図されている。当業者が本発明の概念を実施して使用できるようにするために十分な、好ましい例示的な実施形態の詳細な説明は、後段において続いて行なわれる。

さまざまな例示的な実施形態は、特定の転送テーブルのエントリに対する更新を優先順位付けするネットワークルータを提供する。そのような重要な更新が実行されると、残りの転送テーブルの更新が実行されている間に、他のルーティング情報は他のプロトコルに従って更新されてもよい。さまざまな例示的な実施形態において、ＯＳＰＦ自律システム内のノードのルーティング情報は、転送テーブルへの残りの更新が適用されている間に情報が使用されてＭＰＬＳパスを更新できるように、優先順位付けされてもよい。

さまざまな例示的な実施形態は、ノードにおいて、ネットワーク状態更新メッセージを受信するステップと、ネットワーク状態更新メッセージに基づいてルーティング情報の第１のセットの第１の部分を更新するステップと、ルーティング情報の第１のセットの第１の部分を更新した後、ルーティング情報の第２のセットの更新を開始するステップと、ルーティング情報の第２のセットの更新を開始した後、第１のセットの第２の部分を更新するステップのうちの１つまたは複数を含む方法および関連するネットワークノードに関する。さまざまな代替的な実施形態において、第１の部分を更新するステップは、ルーティング情報の第２のセットを更新するためにルーティング情報が使用されるべきネットワーク内の少なくとも１つの他のノードを決定するステップと、ルーティング情報の第１のセットの少なくとも１つの他のノードに関連付けられているルーティング情報を更新するステップのうちの１つまたは複数を含む。

さまざまな例示的な実施形態は、別のノードからパケットを受信する第１のインターフェイスと、パケットがネットワーク状態更新メッセージであることを決定するネットワーク状態更新メッセージ識別子と、ルーティング情報の第１のセットを格納する第１のルーティング情報ストレージと、ルーティング情報の第２のセットを格納する第２のルーティング情報ストレージと、ネットワーク状態更新メッセージに基づいてルーティング情報の第１のセットの第１の部分を更新し、第１の部分を更新した後、第１の部分が更新されたことを指示し、第１の部分が更新されたことを指示した後、ネットワーク状態更新メッセージに基づいてルーティング情報の第１のセットの第２の部分を更新する第１のルーティング情報生成器と、第１の部分が更新されたという指示に応答して、ルーティング情報の第１のセットの第１の部分に基づいて第２のルーティング情報を更新する第２のルーティング情報生成器のうちの１つまたは複数を含むネットワークノードに関する。

このようにして、さまざまな例示的な実施形態は、ネットワークコンバージェンス時間の短縮を可能にすることが明らかとなろう。特に、最初に特定のルーティング情報を選択的に更新して、第２のルーティング情報生成器をトリガすることにより、ネットワークノードは、ネットワーク内のすべてのノードが共通のルーティング状態に収束するまでに要する時間を短縮することができる。

さまざまな例示的な実施形態をより深く理解するため、添付の図面に参照が行なわれる。

データパケットをルーティングするための例示的なネットワークを示す図である。 １つのノードから複数の他のとりうるノードへの最適パスを決定するための例示的な最短パスツリーを示す図である。 パケット宛先に基づいてパケットが伝送されるべきネクストホップを決定するための例示的な転送テーブルを示す図である。 パケットをルーティングして、ルーティング情報の複数セットにわたるネットワークコンバージェンス時間を短縮するための例示的なネットワークノードを示す図である。 ルーティング情報の複数セットにわたるネットワークコンバージェンス時間を短縮するための例示的な方法を示す図である。 ルーティング情報の複数セットにわたるネットワークコンバージェンス時間を短縮するための代替的な方法を示す図である。

これ以降、類似する番号が類似するコンポーネントまたはステップを示す図面を参照して、さまざまな例示的な実施形態の広範な態様が開示される。本明細書において使用されるように、「ルーティング情報」は概して、最短パスツリー、転送テーブル、ルーティングテーブル、ＭＰＬＳパス、および／またはＬ２ＴＰパスを含む（ただし、これらに限定されることはない）、パケットのルーティングに有用な任意のデータおよび／またはデータ構造を示す。

図１は、データパケットをルーティングするための例示的なネットワーク１００を示す。例示的なネットワークは、さまざまなアプリケーションにデータ転送を行なうためのパケット交換通信ネットワークであってもよい。例示的なネットワーク１００はさらに、ネットワーク内の変化に応答してルーティング情報を自動更新するための規格を実施することができる。たとえば、グループ分け１０１は、オープンショーテストパスファースト（ＯＳＰＦ）規格を実施する自律システムを構成することができる。

例示的なネットワークは、複数のノードＡ−Ｇ １１０−１７０を含むことができる。各ノードＡ−Ｇ １１０−１７０は、ルータ、スイッチ、またはデータパケットを受信してパケットのそれぞれの宛先に向けて転送するように構成された他のネットワーク機器であってもよい。各ノードＡ−Ｇ １１０−１７０はさらに、インターネットプロトコル（ＩＰ）アドレスおよび／またはメディアアクセスコントローラ（ＭＡＣ）アドレスのような、１つまたは複数のネットワークアドレスに関連付けられてもよい。各ノードの各ポートは独立したアドレスに関連付けられてもよいが、例示的なネットワーク１００の各ノードは、簡潔にするため、単一のアドレスに関連付けられているものとして示される。１つまたは複数のノードＡ−Ｇ １１０−１７０はまた、たとえば、マルチプロトコルラベルスイッチング（ＭＰＬＳ）、ラベル配布プロトコル（ＬＤＰ）、リソース予約プロトコル−トラフィックエンジニアリング（ＲＳＶＰ−ＴＥ）、および／またはレイヤ２トンネリングプロトコル（Ｌ２ＴＰ）のような、さまざまなプロトコルを実施するラベルスイッチルータであってもよい。

各ノードはまた、追加のネットワークデバイスおよびエンドユーザ機器のような、複数の追加のデバイスに接続されてもよい。たとえば、ノードＡ１１０は、それぞれ１つまたは複数のネットワークアドレスに関連付けられている、少なくとも２つの他のデバイス１１２、１１４に接続される。さまざまな実施態様において、デバイス１１２、１１４は、類似するサブネットに属すことができる。たとえば、デバイス１１２、１１４はいずれも、ＩＰプレフィックス１３５．２４．０．０／１６によって識別されるサブネットに属すことができる。同様に、ノードＧ１７０は、１８７．５０．１４４．０／２４サブネットに属すことができる少なくとも２つの他のデバイス１７２、１７４に接続されてもよい。各ノードＡ−Ｇ １１０−１７０は、多数の他のデバイス（図示せず）に同様に接続されてもよい。

ノードＡ−Ｇ １１０−１７０は各々、１つまたは複数のリンクを介して１つまたは複数の他のノードＡ−Ｇ １１０−１７０に接続されてもよい。各リンクは、リンクコストに関連付けられてもよい。たとえば、ノードＣ１３０は、コスト２を有するリンクを介してノードＤ１４０に接続されてもよい。このリンクコストは、たとえば、ノード間の地理的距離、ノード間の中間デバイスの数、リンクに関連付けられているビットレート、および／またはリンクの現在の負荷のようなさまざまな要因に基づいて割り当てられてもよい。ノードＢ１２０とノードＧ１７０の間のリンクの場合のように、一部のリンクは、障害が生じているため、パケットの転送には望ましくないこともある。そのようなリンクは、それに応じて、使用を妨げるように、非常に高いかまたは無限のリンクコストを割り当てられてもよい。

各ノードＡ−Ｇ １１０−１７０は、例示的なネットワーク１００のローカル表現を格納することができる。そのようなローカル表現は、ＯＳＰＦに従って他のノードＡ−Ｇ １１０−１７０によって伝送されたリンク状態アドバタイズメント（ＬＳＡ）メッセージで搬送された情報からローカルに構築されてもよい。たとえば、各ノードは、リンク状態データベース（ＬＳＤＢ：Ｌｉｎｋ Ｓｔａｔｅ Ｄａｔａｂａｓｅ）のすべてのノードおよびエッジの指示を格納することができる。そのような表現は、最短パスツリーを構築するため、および最終的に、パケットをそれぞれの宛先に転送する際に使用する転送テーブルを構築するため、各ノードＡ−Ｇ １１０−１７０によって使用されてもよい。

図２は、１つのノードから複数の他のとりうるノードへの最適パスを決定するための例示的な最短パスツリー（ＳＰＴ）２００を示す。ＳＰＴ２００は、当業者に知られている任意の方法を使用して、例示的なネットワーク１００のようなネットワークの現在の状態の表現を使用するノードＣ１３０のパースペクティブから構築されてもよい。たとえば、ノードはダイクストラの最短経路ツリー（Ｄｊｉｋｓｔｒａ’ｓ Ｓｈｏｒｔｅｓｔ Ｐａｔｈ Ｔｒｅｅ）アルゴリズムを使用してＳＰＴを構築することができる。

ＳＰＴ２００は、例示的なネットワーク１００を考慮すると、ノードＣ１３０によって構築されたＳＰＴであってもよい。ＳＰＴ２００は、ノードＡ−Ｇ １１０−１７０に対応する複数のノード表現Ａ−Ｇ ２１０−２７０を含むことができる。ＳＰＴ２００は、ノードＣ１３０からネットワーク内の各ノードへの最適パスを指示することができる。たとえば、ＳＰＴ２００は、ノードＣ１３０からノードＧ１７０への最短パスが、ノードＢ１２０または他のパス経由ではなく、ノードＤ１４０を経由することを指示する。したがって、ノードＧ１７０に宛てられた、ノードＣ１３０によって受信されたパケットは、ＳＰＴ２００に従ってノードＤ１４０に転送される必要がある。次に、ノードＤ１４０は、パケットをノードＧ１７０に転送できるようにする自身のルーティング情報を含むことができる。

ＳＰＴ２００を計算した後、ノードＣ１３０は、例示的なネットワーク１００の状態を反映するように、その転送テーブルを更新することができる。特に、ノードＣ１３０は、ＳＰＴ２００を分析して、考えられる宛先ノードごとに使用されるべきネクストホップノードを決定することができる。次いで、この情報は、パケットを転送するときに迅速にアクセスできるよう転送テーブルに格納されてもよい。

図３は、パケット宛先に基づいてパケットが伝送されるべきネクストホップを決定するための例示的な転送テーブル３００を示す。転送テーブル３００は、たとえば、ノードＣ１３０に格納されているデータベース内のテーブルであってもよい。あるいは、転送テーブル３００は、一連のリンクされたリスト、アレイ、または類似するデータ構造であってもよい。したがって、転送テーブル３００は、基礎をなすデータの抽象化であり、基礎をなすデータの格納に適した任意のデータ構造が使用されてもよいことが明らかとなろう。

転送テーブル３００は、宛先フィールド３０２、およびネクストホップフィールド３０４を含むことができる。宛先フィールド３０２は、各エントリが関連付けられている宛先デバイスを指示することができ、ネクストホップフィールド３０４は、関連する宛先デバイスに適切なネクストホップデバイスを指示することができる。転送テーブル３００が、いくつかの点で、簡略化されたものであることは明らかとなろう。たとえば、転送テーブルは、発信ポート番号、宛先ＭＡＣアドレス、および／または代替ネクストホップのような、追加のフィールドを含むことができる。さまざまな変形が、当業者には明らかとなろう。

転送テーブルは、複数のエントリ３１０−３７０を含むことができる。エントリ３１０は、ＩＰアドレス１３５．２４．３６．１１０に宛てられたパケットが、ノードＢ１２０に転送される必要があることを指示することができる。サブネットまたは他のグループ分けもまた、完全アドレスの代わりに宛先フィールドで使用されてもよい。たとえば、エントリ３１５は、１３５．２４．０．０／１６サブネットに宛てられたパケットが、ノードＢ１２０に転送される必要があることを指示することができる。このエントリを使用して、デバイス１１２またはデバイス１１４に宛てられたパケットは適正にルーティングされてもよい。追加のエントリ３２０−３７５は、例示的なネットワーク１００内の各デバイスに対するネクストホップルータを指示することができる。テーブル３００は、追加のノードおよび／またはサブネットのルーティング情報を提供する多数の追加のエントリ（図示せず）を含むことができる。

例示的なネットワーク１００のコンポーネントを説明してきたが、例示的なネットワーク１００の動作の概要が説明されることになる。後段の説明は例示的なネットワーク１００の動作の概要を提供することを意図しており、したがって若干簡略化されたものであることは明らかである。例示的なネットワーク１００の詳細な動作は、図４−図６に関連して以下でさらに詳細に説明される。

ノードＣ１３０は、ネットワークにおける変化を指示するＬＳＡを受信することができる。たとえば、ＬＳＡは、ノードＡ１１０とノードＢ１２０の間のリンクがダウンしていることを指示することができる。次いで、ノードＣ１３０は、ノードＡ１１０に到達するための新しい最適パスを提供する、新しいＳＰＴを計算することができる。次いで、ノード１３０は、その転送テーブル３００の更新を開始することができる。

転送テーブル３００を更新する際、ノードＣ１３０は特定の更新を優先順位付けすることができる。たとえば、ノードＣ１３０は、エントリ３２０、３４０が隣接ノードに関連付けられているので、これらのエントリを最初に更新することができる。次いで、ノードＣ１３０は、エントリ３１０、３５０、３６０、３７０の更新を進めることができ、その後転送テーブルは、グループ１０１内のノードに関して最新の状態になる。最後に、ノードＣ１３０は、エントリ３１５、３７５を更新して、グループ１０１の外部のデバイスにパスを提供することができる。

ノードＣ１３０が転送テーブル３００の更新を終了する前のある時点において、ノードＣはまた、たとえば、ＭＰＬＳパスまたはＬ２ＴＰパスのようなルーティング情報の第２のセットの更新を開始することもできる。ノードＣ１３０は、たとえば、エントリ３２０、３４０だけが更新された後、またはグループ１０１内のすべてのノードのエントリが更新された後に、この第２の更新処理を開始することができる。第２の更新処理は、テーブル３００の更新済み情報を使用することができる。したがって、ルーティング情報更新処理の一部は並行して実行されてもよく、ネットワーク変化イベントの後にルータが引き続き古い状態にある時間を短縮することができる。

図４は、パケットをルーティングして、ルーティング情報の複数セットにわたるネットワークコンバージェンス時間を短縮するための例示的なネットワークノード４００を示す。ネットワークノード４００は、例示的なネットワーク１００の１つまたは複数のノードＡ−Ｇ １１０−１７０に対応することができる。ネットワークノード４００は、パケット受信機４０５、リンク状態アドバタイズメント識別子４１０、ルーティングプロセッサ４２０、パケット送信機４２５、転送テーブルストレージ４３０、リンク状態データベース４４０、最短パスツリー生成器４５０、転送テーブル生成器４６０、ＭＰＬＳパス生成器４７０およびＭＰＬＳパスストレージ４８０を含むことができる。

パケット受信機４０５は、他のネットワークデバイスからパケットを受信するように構成されたハードウェア、および／または機械可読ストレージ媒体上の符号化された実行可能命令を備えるインターフェイスであってもよい。パケット受信機４０５は、複数のポートを含むことができ、複数のネットワークデバイスからパケットを受信することができる。たとえば、パケット受信機４０５は、リンク状態アドバタイズメントパケット、および通常のネットワークトラフィックに関連するパケットを受信することができる。

リンク状態アドバタイズメント（ＬＳＡ）識別子４１０は、受信したパケットがノード４００の処理すべきＬＳＡであるかどうかを決定するように構成されたハードウェア、および／または機械可読ストレージ媒体上の実行可能命令を含むことができる。パケットがＬＳＡである場合、ＬＳＡ識別子４１０は、ＬＳＡを解釈し、さらなる処理のために指示されたネットワーク変化をリンク状態データベース４４０に格納することができる。それ以外の場合、ＬＳＡ識別子は、パケットを、さらにルーティングするためにルーティングプロセッサ４２０に渡すことができる。

本明細書において説明されるさまざまな実施形態は、ＯＳＰＦに従って構築されたリンク状態アドバタイズメントを使用するシステムに関するが、さまざまな実施形態が代替のネットワーク更新メッセージを使用する他の規格と共に機能できることに留意されたい。したがって、ＬＳＡ識別子４１０は、汎用ネットワーク更新メッセージ識別子と見なされてもよい。そのような他の規格を伴う実施態様に有用な変更が、当業者には明らかとなろう。

ルーティングプロセッサ４２０は、パケットをそれぞれの宛先にルーティングするように構成されたハードウェア、および／または機械可読ストレージ媒体上の実行可能命令を含むことができる。ルーティングプロセッサ４２０は、受信した各パケットから宛先を抽出し、転送テーブルストレージ４３０に格納されている転送テーブルを使用してその宛先のネクストホップを決定することができる。次いで、ルーティングプロセッサ４２０は、パケットを、送信機４２５を介して適切なネクストホップに転送することができる。ルーティングプロセッサ４２０はさらに、ＭＰＬＳパスストレージ４８０に格納されているルーティング情報に従って、ＭＰＬＳパケットを処理および転送するように構成されてもよい。

パケット送信機４２５は、他のネットワークデバイスにパケットを送信するように構成されたハードウェア、および／または機械可読ストレージ媒体上の符号化された実行可能命令を備えるインターフェイスであってもよい。パケット送信機４２５は、複数のポートを含むことができ、複数のネットワークデバイスに複数種のパケットを送信することができる。たとえば、パケット送信機４２５は、リンク状態アドバタイズメントパケット、および通常のネットワークトラフィックに関連するパケットを送信することができる。

転送テーブルストレージ４３０は、転送テーブルを格納することができる任意の機械可読媒体であってもよい。したがって、転送テーブルストレージ４３０は、読み取り専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、磁気ディスクストレージ媒体、光ストレージ媒体、フラッシュメモリデバイス、および／または類似するストレージ媒体のような機械可読ストレージ媒体を含むことができる。

リンク状態データベース（ＬＳＤＢ）４４０は、現在のネットワーク状態の表現を格納することができる任意の機械可読媒体であってもよい。ＬＳＤＢ４４０は、たとえば、自律システム内のあらゆるノードおよびリンクの指示を格納することができる。したがって、ＬＳＤＢ４４０は、読み取り専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、磁気ディスクストレージ媒体、光ストレージ媒体、フラッシュメモリデバイス、および／または類似するストレージ媒体のような機械可読ストレージ媒体を含むことができる。ＬＳＤＢ４４０は、ノード４００内の独立したストレージデバイスであってもよいか、または転送テーブルストレージ４３０と同じものであってもよい。

最短パスツリー（ＳＰＴ）生成器４５０は、ネットワークの表現から最短パスツリーを生成するように構成されたハードウェア、および／または機械可読ストレージ媒体上の実行可能命令を含むことができる。たとえば、ＳＰＴ生成器４５０は、ダイクストラのアルゴリズムまたは当業者に知られている任意の他の方法を使用して、ＬＳＤＢ４４０に格納されているデータから最短パスツリーを生成することができる。ＳＰＴを生成した後、ＳＰＴ生成器４５０は、ＳＰＴを転送テーブル生成器４６０に伝送することができる。あるいは、ＳＰＴ生成器４５０は、各ノードがＳＰＴに追加される際に、転送テーブル生成器４６０に情報を伝送して、ＳＰＴが完成する前に転送テーブル生成器４６０が転送テーブルの更新を開始できるようにすることができる。

転送テーブル生成器４６０は、ＳＰＴに基づいて転送テーブルを生成するかまたは更新するように構成されたハードウェア、および／または機械可読ストレージ媒体上の実行可能命令を含むことができる。たとえば、転送テーブル生成器４６０は、ネットワークノード４００の現在のＳＰＴに基づいて、転送テーブルストレージ４３０の任意のエントリが追加または変更されるべきであるかどうかを決定することができる。次いで、転送テーブル生成器４６０は、そのような更新を、たとえば、エントリを追加または除去するか、もしくは１つまたは複数のエントリのネクストホップを変更することによって実行することができる。

転送テーブル生成器４６０はさらに、転送テーブルを更新する順序を優先順位付けするように構成されてもよい。たとえば、転送テーブル生成器４６０は、自律システム内にあるノードに関連付けられているエントリを重要であると見なして、そのようなエントリの更新を最初に実行することができる。そのようなエントリは、たとえば、ＳＰＴを検査する、ＬＳＡが受信されるルータ識別子のリストを使用する、および／または完全３２ビットプレフィックスに関連するエントリを検索するなどのような、当業者に知られている任意の方法に従って識別されてもよい。そのような重要な更新を完了した後、転送テーブル生成器４６０は、重要な更新が完了したことをＭＰＬＳパス生成器４７０に通知することができる。次いで、ＭＰＬＳパス生成器４６０は、そのコンポーネントを参照してさらに詳細に説明されるように、追加のルーティング情報の更新を開始することができる。この間に、転送テーブル生成器４６０は、転送テーブルへの重要ではない更新を完了することができる。

さまざまな代替的な実施形態によれば、転送テーブル生成器４６０はさらに、重要な更新を優先順位付けすることができる。たとえば、転送テーブル生成器４６０は、現在のＳＰＴを使用して隣接ノードを識別し、対応する転送テーブルのエントリを最初に更新することができる。次いで、転送テーブル生成器４６０は、２ホップ離れたノードに関連する更新を実行するように進むことができる。転送テーブル生成器４６０は、すべての重要な更新が実行されてしまうまで、このように続行することができる。そのような各段階を終えるごとに、転送テーブル生成器４６０は、一部の重要な更新が完了したことをＭＰＬＳパス生成器４７０に指示して、ＭＰＬＳパス生成器４７０がＭＰＬＳルーティング情報の更新を開始できるようにすることができる。

追加の代替的な実施形態によれば、転送テーブル生成器４６０は、特定のタイプのデバイスに関連する更新を優先順位付けすることができる。たとえば、転送テーブル生成器４６０は、直近の隣接ノードのエントリが更新されると直ちに、エリア境界ルータおよび／またはエリアサマリー境界ルータのような自律システムへのゲートウェイルータを処理することができる。次いで、転送テーブル生成器４６０は、膨張波で１ホップずつ残りの更新の処理を進めてゆくことができる。

ノード４００はＯＳＰＦのさまざまな態様に従って機能するように説明されるが、本明細書において説明される方法が他の規格に適用可能な場合があることに留意されたい。他の規格に準拠するための適切な変更が、当業者には明らかとなろう。したがって、ＳＰＴ生成器４５０および転送テーブル生成器４６０は、単独または全体として、汎用「ルーティング情報生成器」と見なされてもよい。

ＭＰＬＳパス生成器４７０は、ＭＰＬＳルーティング情報を生成または更新するように構成されたハードウェア、および／または機械可読ストレージ媒体上の実行可能命令を含むことができる。ＭＰＬＳパス生成器４７０は、転送テーブルストレージ４３０からの情報を使用して、最適ＭＰＬＳパスを確立または変更し、そのようなルーティング情報をＭＰＬＳパスストレージ４８０に格納することができる。ＭＰＬＳパス生成器４７０は、ネットワーク変化が発生したこと、および／または少なくとも一部の重要な更新が転送テーブルで行なわれたことの指示を転送テーブル生成器４６０から受信した後、そのような更新手順を開始するように構成されてもよい。

ノード４００はＭＰＬＳのさまざまな態様に従って機能するように説明されるが、本明細書において説明される方法が他の規格に適用可能であることに留意されたい。他の規格に準拠するための適切な変更が、当業者には明らかとなろう。たとえば、ＭＰＬＳパス生成器４７０は、Ｌ２ＴＰに従ってパスを生成するＬ２ＴＰパス生成器（図示せず）に置き換えられてもよい。したがって、ＭＰＬＳパス生成器４７０は、第２の汎用「ルーティング情報生成器」と見なされてもよい。

ＭＰＬＳパスストレージ４８０は、ＭＰＬＳルーティング情報を格納することができる任意の機械可読媒体であってもよい。ＭＰＬＳパスストレージ４８０は、たとえば、着信ラベル、発信ラベル、着信インターフェイス、および／または発信インターフェイスを指定する多数のレコードを格納することができる。したがって、ＭＰＬＳパスストレージ４８０は、読み取り専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、磁気ディスクストレージ媒体、光ストレージ媒体、フラッシュメモリデバイス、および／または類似するストレージ媒体のような機械可読ストレージ媒体を含むことができる。ＭＰＬＳパスストレージ４８０は、ノード４００内の独立したストレージデバイスであってもよいか、または転送テーブルストレージ４３０および／またはＬＳＤＢ４４０と同じものであってもよい。

図５は、ルーティング情報の複数セットにわたるネットワークコンバージェンス時間を短縮するための例示的な方法５００を示す。方法５００は、たとえば、ＬＳＡ識別子４１０、ＳＰＴ生成器４５０、転送テーブル生成器４６０、および／またはＭＰＬＳパス生成器４７０のような、ネットワークノード４００のさまざまなコンポーネントによって実行されてもよい。

方法５００は、ステップ５０５で開始して、ステップ５１０に進むことができ、ここでノード４００がネットワーク状態の変化を指示するＬＳＡを受信することができる。次いで、ステップ５１５において、ノード４００は新しいＳＰＴを計算することができる。次に、ステップ５２０において、ノード４００は、重要ノードのリストを決定することができる。たとえば、ノード４００は、ＯＳＰＦ自律システム内の各ノードが重要ノードであることを決定することができる。次いで、方法５００はステップ５２５に進むことができ、ここでノード４００が処理すべき第１の重要ノードを見つけることができる。

ステップ５３０において、ノード４００は、新しく計算されたＳＰＴに従って、重要ノードに関連付けられている１つまたは複数のエントリを更新することができる。たとえば、ノード４００は、重要ノードの３２ビットプレフィックスアドレスを含む転送テーブル内のエントリを見つけて、ネクストホップ識別を変更することができる。次いで、方法５００はステップ５３５に進むことができ、ここでノード４００が処理すべき追加の重要ノードがあるかどうかを決定することができる。処理すべき追加の重要ノードがある場合、方法５００はステップ５４０に進むことができ、ここでノード４００が処理すべき次の重要ノードを見つけて、ステップ５３０にループバックすることができる。

すべての重要ノードが処理されてしまうと、方法５００はステップ５４５に進むことができ、ここでノード５４５が転送テーブルに基づいてＭＰＬＳルーティング情報を更新する処理を開始することができる。方法５００はステップ５５０に進むことができ、ここでノード４００が重要ではないエントリを処理することによって転送テーブルの更新を終了することができる。このステップが、ＭＰＬＳルーティング情報の再計算の際に、別個のプロセッサで並行して、または単一のプロセッサで処理時間を共有することにより、同時に実行されてもよいことに留意されたい。ＭＰＬＳルーティング情報の再計算の後または再計算中に、ノード４００は、たとえば、ＬＤＰまたはＲＳＶＰ−ＴＥプロトコルに従って、１つまたは複数のＭＰＬＳ更新メッセージを他のノードに伝送することができる。あるいは、ノード４００は、ＭＰＬＳ更新メッセージを送信する前に、転送テーブルの更新が完了するまで待機することができる。次いで、方法５００は、ステップ５６０で終了する。

図６は、ルーティング情報の複数セットにわたるネットワークコンバージェンス時間を短縮するための代替的な方法６００を示す。方法６００は、たとえば、ＬＳＡ識別子４１０、ＳＰＴ生成器４５０、転送テーブル生成器４６０、および／またはＭＰＬＳパス生成器４７０のような、ネットワークノード４００のさまざまなコンポーネントによって実行されてもよい。方法６００は、方法５００と類似していてもよいが、転送テーブルへの更新をさらに優先順位付けする。

方法６００は、ステップ６０５で開始し、方法５００と同様に、ステップ６１０においてＬＳＡを受信して、ステップ６１５において新しいＳＰＴを計算することができる。ステップ６２０において、ノード４００は、システム内で最も重要なノードのセットを決定することができる。たとえば、ノード４００は、ＳＰＴのルートを下回る第１のレベルのノードが最も重要であると見なすことができる。それらのノードは、隣接ノードと称することができる。次いで、方法６００はステップ６２５に進むことができ、ここでノード４００が最も重要なノードのこのセットから処理すべき第１のノードを決定することができる。

ステップ６３０において、方法５００のステップ５３０と同様に、ノード４００は、新しいＳＰＴを考慮して重要ノードに関連付けられている１つまたは複数のエントリを更新することができる。次いで、方法６００はステップ６３５に進むことができ、ここでノード４００が現在のレベルに処理すべき追加の重要ノードがあるかどうかを決定することができる。処理すべき追加の重要ノードがある場合、ステップ６４０において、ノード４００は現在のレベルに次の重要ノードを見つけることができ、方法６００はステップ６３０にループバックすることができる。

レベル内のすべての重要ノードが処理されてしまうと、方法６００はステップ６４５に進むことができ、ここでノード４００が転送テーブルへの最新の更新に基づいてＭＰＬＳルーティング情報の更新手順の少なくとも一部を実行することができる。この処理が実行される際、方法６００はステップ６４７に進むことができ、ここでノード４００がまだ処理されていない追加の重要なレベルがあるかどうかを決定することができる。追加の重要なレベルがある場合、方法６００はステップ６４９に進むことができ、ここでノード６００が重要ノードの次のグループを取り出すことができる。たとえば、ノード４００は、直前に処理されたレベルからＳＰＴで次に下のレベルにあるノードのグループを取り出すことができる。このようにして、ノード４００は、「１ホップ」、「２ホップ」というように先のノードへと順次処理することができる。次いで、方法６００は、ステップ６２５にループバックして、新しい重要なレベルを処理することができる。

すべての重要な更新が実行されてしまうと、方法６００はステップ６５０に進むことができる。方法５００において、ノードは、すべての重要ではない更新を処理することによって転送テーブルの更新を終了することができる。次いで、ノード４００は、ステップ６５５において、１つまたは複数のＭＰＬＳ更新メッセージを伝送することができ、方法６００はステップ６６０で終了することができる。

前述の説明により、さまざまな例示的な実施形態は、ネットワークコンバージェンス時間を短縮することができる。特に、最初に特定のルーティング情報を選択的に更新して、第２のルーティング情報生成器をトリガすることにより、ネットワークノードは、ネットワーク内のすべてのノードが共通のルーティング状態に収束するまでに要する時間を短縮することができる。

本発明のさまざまな例示的な実施形態が、ハードウェアおよび／またはファームウェアにおいて実施されうることが、上記の説明から明らかとなろう。さらに、さまざまな例示的な実施形態は、本明細書において詳細に説明される動作を実行するために少なくとも１つのプロセッサによって読み込まれ実行されうる、機械可読ストレージ媒体に格納された命令として実施されてもよい。機械可読ストレージ媒体は、パーソナルまたはラップトップコンピュータ、サーバ、または他のコンピューティングデバイスのような、機械によって読み取り可能な形態で情報を格納するための任意のメカニズムを含むことができる。したがって、機械可読ストレージ媒体は、読み取り専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、磁気ディスクストレージ媒体、光ストレージ媒体、フラッシュメモリデバイス、および類似するストレージ媒体を含むことができる。

「プロセッサ」と称される任意の機能ブロックを含む、図面に示されるさまざまな要素の機能は、専用ハードウェア、および適切なソフトウェアと関連して処理ステップを実行することができるハードウェアの使用を通じて提供されてもよい。プロセッサにより提供される場合、機能は、単一の専用プロセッサ、単一の共有プロセッサ、または一部が共有されうる複数の個々のプロセッサによって提供されてもよい。さらに、「プロセッサ」または「コントローラ」という用語の明示的な使用は、ソフトウェアを実行することができるハードウェアのみを参照するものと解釈されるべきではなく、デジタル信号プロセッサ（ＤＳＰ）ハードウェア、ネットワークプロセッサ、特定用途向け集積回路（ＡＳＩＣ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、ソフトウェアを格納するための読み取り専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、および不揮発性ストレージを、限定することなく暗黙的に含むことができる。標準および／またはカスタムの他のハードウェアが含まれてもよい。同様に、図面に示される任意のスイッチは、概念的なものに過ぎない。それらの機能は、プログラム論理の動作を通じて、専用論理を通じて、プログラム制御および専用論理の相互作用を通じて、または手動によっても実行されてもよく、特定の技法は、コンテキストからさらに具体的に理解されるように実施者により選択可能である。

当業者には、本明細書における任意のブロック図が、本発明の原理を具現する例示的な回路の概念的な図を表すことが理解されるであろう。同様に、任意の流れ図、フローダイアグラム、状態遷移図、擬似コードなどは、機械可読媒体において概ね表されてもよく、コンピュータまたはプロセッサにより（そのようなコンピュータまたはプロセッサが明示的に示されているかどうかにかかわらず）実行されてもよいさまざまな処理を表すことが理解されよう。

さまざまな例示的な実施形態が、その特定の例示的な態様を特に参照して詳細に説明されてきたが、本発明は他の実施形態が可能であり、その詳細はさまざまな明白な点において変更が可能であることを理解されたい。当業者には容易に明らかなように、本発明の趣旨および範囲を逸脱することなく変形および変更が行なわれてもよい。したがって、前述の開示、説明、および図面は、例示のみを目的としており、本発明を何ら限定するものではなく、本発明は特許請求の範囲によってのみ定義される。

Claims (9)

1. ネットワークノードによって実行されるネットワークにおけるルーティング情報の更新時間を短縮する方法であって、
   ネットワークノードにおいて、ネットワーク状態更新メッセージを受信するステップと、
   ネットワーク内の重要ノードのセットを識別するステップと、
   ネットワーク状態更新メッセージに基づいてルーティング情報の第１のセットの第１の部分を更新するステップと、
   ルーティング情報の第１のセットの第１の部分を更新した後、ルーティング情報の第２のセットの第１の更新を開始するステップと、
   ルーティング情報の第２のセットの更新を開始した後、ルーティング情報の第１のセットの第２の部分とルーティング情報の第２のセットとを同時に更新するステップと
   を備え、
   ルーティング情報の第１のセットの第１の部分は、重要ノードのセットに関連付けられており、
   ルーティング情報の第１のセットの第２の部分は、重要ノードのセット以外の、ネットワーク内のノードに関連付けられている、方法。
2. ルーティング情報の第２のセットの更新を開始した後、ルーティング情報の第１のセットの第１の部分に基づいてルーティング情報の第２のセットを更新するステップをさらに備える、請求項１に記載の方法。
3. ネットワーク内の重要ノードのセットを識別するステップが、
   ルーティング情報の第２のセットを更新するためにルーティング情報が使用されるべきネットワーク内の少なくとも１つの他のノードを決定するステップを備え、
   ルーティング情報の第１のセットの第１の部分を更新するステップが、
   ルーティング情報の第１のセットの少なくとも１つの他のノードに関連付けられているルーティング情報を更新するステップを備える、請求項１に記載の方法。
4. ルーティング情報の第１のセットの第１の部分が、ネットワークノードが属する自律ルーティングシステム内の他のノードに対応するルーティング情報のみを含む、請求項１に記載の方法。
5. ルーティング情報の第１のセットの第１の部分が、ネットワークノードの隣接ノードに対応するルーティング情報のみを含み、ルーティング情報の第１のセットの第２の部分が、ネットワークノードから２ホップ離れたノードに対応するルーティング情報のみを含み、
   ルーティング情報の第１のセットの第２の部分を更新した後、ルーティング情報の第２のセットの第２の更新を開始するステップと、
   ルーティング情報の第２のセットの第２の更新を開始した後、ルーティング情報の第１のセットの第３の部分を更新するステップと
   をさらに備える、請求項１に記載の方法。
6. 第１の部分および第２の部分のうちの少なくとも１つが、特定のタイプのデバイスであるノードに対応するルーティング情報のみを含む、請求項１に記載の方法。
7. ルーティング情報の第２のセットの少なくとも一部が更新された後、ルーティング情報の第２のセットに基づいてルーティング情報更新メッセージを構築するステップと、
   ルーティング情報更新メッセージを少なくとも１つの他のノードに伝送するステップと
   をさらに備える、請求項１に記載の方法。
8. ルーティング情報の第１のセットがＩＰルーティング情報を含み、ルーティング情報の第２のセットが、ＭＰＬＳパス情報およびレイヤ２トンネリングプロトコル（Ｌ２ＴＰ）パス情報のうちの少なくとも１つを含む、請求項１に記載の方法。
9. ネットワークにおけるルーティング情報の更新時間を短縮するためのネットワークノードであって、
   別のノードからパケットを受信する第１のインターフェイスと、
   パケットがネットワーク状態更新メッセージであることを決定するネットワーク状態更新メッセージ識別子と、
   ルーティング情報の第１のセットを格納する第１のルーティング情報ストレージと、
   ルーティング情報の第２のセットを格納する第２のルーティング情報ストレージと、
   ネットワーク内の重要ノードのセットを識別し、
   ネットワーク状態更新メッセージに基づいてルーティング情報の第１のセットの第１の部分を更新し、
   第１の部分を更新した後、第１の部分が更新されたことを指示し、
   第１の部分が更新されたことを指示した後、ネットワーク状態更新メッセージに基づいてルーティング情報の第１のセットの第２の部分を更新する第１のルーティング情報生成器と、
   第１の部分が更新されたという指示に応答して、第１のルーティング情報生成器がルーティング情報の第１のセットの第２の部分を更新するのと同時に、ルーティング情報の第１のセットの第１の部分に基づいて第２のルーティング情報を更新する第２のルーティング情報生成器と
   を備え、
   ルーティング情報の第１のセットの第１の部分は、重要ノードのセットに関連付けられており、
   ルーティング情報の第１のセットの第２の部分は、重要ノードのセット以外の、ネットワーク内のノードに関連付けられている、ネットワークノード。

Images