(57)【要約】  メッセージパケットに関連するアドレス照合の回数を減少させるための、全範囲の保護を提供するＩＰ高速リルートの方式が開示される。この、全範囲の保護を提供するＩＰ高速リルート方式は、転送情報記憶装置に格納されている伝送情報表の中の、宛先ノードに関連する第１のポインタおよび第２のポインタのうち１つに従って、到着パケットをネクストホップ隣接ノードに転送するよう構成されているルータを備える。第１のポインタは、そのネットワークノードから宛先ノードまでの最短経路上にある第１のネクストホップ隣接ノードを指し、第２のポインタは第１のネクストホップ隣接ノードとは異なる第２のネクストホップ隣接ノードを指し、第２のネクストホップ隣接ノードは、そのネットワークノードおよび宛先ノードの両方を含む、宛先ノードを根とするシンクツリーとの重なりが最も大きい候補サイクル上にある。全範囲の保護を提供するＩＰ高速リルート方式は、特に、パケットを修正する必要のない簡潔な手法で、単一のリンク故障およびノード故障からの全範囲の保護を提供するために有用である。
2014534776.tif 000002
【特許請求の範囲】
【請求項１】
宛先ノードをもつ到着パケットをルーティングするための、ネットワークノード上にあるネットワーク要素であって、
転送情報記憶装置に格納されている転送情報表の中の、前記宛先ノードに関連する第１のポインタおよび第２のポインタのうち１つに従って、前記到着パケットをネクストホップ隣接ノードに転送する（４０９、４１０、４１５、５０５、５０９）よう構成されたルータを備え、
前記第１のポインタが、前記ネットワークノードから前記宛先ノードまでの最短経路上にある第１のネクストホップ隣接ノードを指しており、
前記第２のポインタが、前記第１のネクストホップ隣接ノードとは異なる第２のネクストホップ隣接ノードを指しており、前記第２のネクストホップ隣接ノードが、前記ネットワークノードおよび前記宛先ノードの両方を含むサイクルのうち、前記宛先ノードを根とするシンクツリーとの重なりが最も大きい候補サイクル上にある、
ネットワーク要素。
【請求項２】
前記第１のポインタに指示されるネクストホップ隣接ノード以外の隣接するノードから前記到着パケットが到着した場合（４０３、５０４）に、前記第１のポインタに従って前記到着パケットを転送する（４１０、５０５）よう前記ルータが構成されている、
請求項１に記載のネットワーク要素。
【請求項３】
前記第１のポインタに指示されるネクストホップ隣接ノードから前記到着パケットが到着した場合（４０３、５０４）に、前記第２のポインタに従って前記到着パケットを転送する（４１５、５０９）よう前記ルータが構成されている、
請求項１または２のいずれかに記載のネットワーク要素。
【請求項４】
前記第１のポインタに指示されるネクストホップ隣接ノードがパケットを転送できない場合（４０４、５０４）に、前記第２のポインタに従って前記到着パケットを転送する（４０８、５０９）よう前記ルータが構成されている、
請求項１から３のいずれかに記載のネットワーク要素。
【請求項５】
前記第１のポインタに指示されるネクストホップ隣接ノードへのリンクがパケットを転送できない場合（４０４、５０４）に、前記第２のポインタに従って前記到着パケットを転送する（４０８、５０９）よう前記ルータが構成されている、
請求項１から４のいずれかに記載のネットワーク要素。
【請求項６】
転送情報記憶装置に格納された前記転送情報表の中に、前記宛先ノードに関連する第１のフラグおよび第２のフラグをさらに含み、
前記第１のフラグが、前記ネットワークノードから前記宛先ノードまでの最短経路の稼働状態を示しており、
前記第２のフラグが、前記ネットワークノードから前記第２のネクストホップノードまでのリンクが、前記宛先ノードを根とする前記シンクツリーの要素であるかどうかを示しており、
前記第１のフラグが非稼働状態を示し、かつ前記第２のフラグが、前記ネットワークノードから前記第２のネクストホップノードまでは前記宛先ノードを根とする前記シンクツリーの要素であることを示し、かつ前記到着パケットが、前記第１のポインタに指示されるネクストホップ隣接ノードから到着した場合（５０３）に、前記到着パケットを破棄する（５１３）よう前記ルータが構成されている、
請求項１から５のいずれかに記載のネットワーク要素。
【請求項７】
前記第１のポインタに指示されるネクストホップ隣接ノード以外の隣接するノードから前記到着パケットが到着した場合（５０４）に、前記第１のポインタに従って前記到着パケットを転送する（５０５）よう前記ルータが構成されている、
請求項６に記載のネットワーク要素。
【請求項８】
前記第１のポインタに指示されるネクストホップ隣接ノードから前記到着パケットが到着した場合（５０４）に、前記第２のポインタに従って前記到着パケットを転送する（５０９）よう前記ルータが構成されている、
請求項６または７のいずれかに記載のネットワーク要素。
【請求項９】
前記第１のポインタに指示されるネクストホップ隣接ノードがパケットを転送できない場合（５０４）に、前記第２のポインタに従って前記到着パケットを転送する（５０９）よう前記ルータが構成されている、
請求項６から８のいずれかに記載のネットワーク要素。
【請求項１０】
前記第１のポインタに指示されるネクストホップ隣接ノードへのリンクがパケットを転送できない場合（５０４）に、前記第２のポインタに従って前記到着パケットを転送する（５０９）よう前記ルータが構成されている、
請求項６から１０のいずれかに記載のネットワーク要素。
【請求項１１】
前記ネットワーク要素がノードとして含まれているネットワークの新しいネットワークコンフィギュレーションを示すネットワークコンフィギュレーション情報が到着した場合に、
新しいネットワークコンフィギュレーションに相当するシンクツリー上の、前記ネットワークノードの先祖ノードの再構成が完了した期間に続く時点で、前記転送情報表が更新される、
請求項１から１０のいずれかに記載のネットワーク要素。
【請求項１２】
記憶装置に格納されたネットワークコンフィギュレーションをもつネットワークの第１のネットワークノード内の転送情報記憶装置に格納されている転送情報表の中の、宛先ノードに関連するバックアップポインタおよびプライマリポインタを自動的に計算する方法であって、
前記ネットワークの前記ネットワークコンフィギュレーションを使用して、前記宛先ノードを根とするシンクツリーを計算するステップ（３０３）と、
前記ネットワークの前記ネットワークコンフィギュレーションを使用して、前記第１のネットワークノードから前記宛先ノードまでの最短経路を計算するステップ（３０９）と、
前記第１のネットワークノードから前記宛先ノードまでの最短経路上にある第１のネクストホップ隣接ノードを指すように前記プライマリポインタを方向付けるステップ（３１０）と、
前記第１のネクストホップ隣接ノードとは異なる第２のネクストホップ隣接ノードを指すように前記バックアップポインタを方向付け、前記第２のネクストホップ隣接ノードが、前記第１のネットワークノードおよび前記宛先ノードの両方を含む、前記宛先ノードを根とするシンクツリーとの重なりが最も大きい候補サイクル上にあるステップ（３１０）と
を含む方法。
【請求項１３】
前記ネットワークノードおよび前記宛先ノード以外の、前記ネットワークのすべてのノードについて前記第２の計算ステップおよび前記方向付けステップを繰り返すステップ（３０２）
をさらに含む、請求項１２に記載の方法。
【請求項１４】
前記ネットワークコンフィギュレーションへの更新を受け取るステップと、
前記更新を前記記憶装置に格納するステップと、
前記ネットワークの前記更新済みネットワークコンフィギュレーションを使用して、前記宛先ノードを根とする新しいシンクツリーを計算するステップ（３０３）と、
新しいネットワークコンフィギュレーションに相当するシンクツリー上の、前記ネットワークノードの先祖ノードの再構成が完了した期間に続く時点で、前記ネットワークノード以外の、前記ネットワークのすべてのノードについて第２の計算ステップおよび前記方向付けステップを繰り返すことによって、前記転送情報表を更新するステップとをさらに含む、
請求項１２または１３のいずれかに記載の方法。
【請求項１５】
前記新しいシンクツリー内で最も近い先祖から、前記新しいシンクツリー内の前記最も近い先祖から前記宛先ノードへの経路が変更されていない前記ネットワークノードまでのホップカウント距離に従って、前記期間が計算される、
請求項１４に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、２０１１年１１月１日に出願した米国特許仮出願第６１／５５４，３４１号を参照により組み込み、この仮出願に基づく優先権を主張する。
【０００２】
本発明は、主としてネットワーク内で故障が発生した場合のパケットリルーティングに関し、特に、ネットワーク全体を保護範囲としながら収束時間を短縮させるパケットリルーティングの方法に関係する。
【背景技術】
【０００３】
現代のＩＰ（インターネットプロトコル）ネットワークは、テレビ会議や対話式マルチプレイヤーゲームなどの、非常に多くの時間依存性アプリケーションのトラフィックデータを伝送する。したがって、ネットワークは、非常に高水準のサービス品質（ＱｏＳ）および可用性を提供する必要がある。それゆえ、ネットワークがこれらの点において満足に性能を発揮することを保証するために、サービスプロバイダがあらゆる努力を行うのは当然である。それにも関わらず、予定された保守手順のみならず予期せぬ構成要素故障によっても、ネットワーク性能が劣化している期間がしばしば生じる。
【０００４】
このようなネットワーク性能が低下している期間のうちの１つは収束期間と呼ばれる。その理由は、この期間は、例えばオープンショーテストパスファースト（ＯＳＰＦ）などのネットワークの内部ゲートウェイプロトコル（ＩＧＰ）が、トポロジの変化が起こった後に収束するために必要とする時間に相当するからである。より詳細には、これらの期間のそれぞれの中で、トポロジ変化に関する情報がネットワークの中で伝播されるのにつれて、すべてのルータが個別に転送情報ベース（ＦＩＢ）表を更新する。その結果、別々のルータの転送表が、一時的に相互に一貫性を失うことがあり、トラフィックが転送ループに陥ること、および／または破棄されることにつながることがある。
【０００５】
収束期間は通常、数１００ミリ秒間続き、数秒間に及ぶこともある。残念なことに、このような長い回復時間は、ほとんどの実時間アプリケーションでは許容されない。逆に、消費者がどんな悪影響にもほとんど気付かないことを確実にするには、ＳＯＮＥＴ／ＳＤＨおよびＭＰＬＳネットワークの回復時間のような、５０ミリ秒未満の回復時間が望ましいであろう。
【０００６】
関連した話では、最近、サービスプロバイダにとってエネルギー効率が重要な関心事になってきている。エネルギー消費を縮小するためによく使われる１つの技法は、例えば、不要なリンクおよびルータを一時的にオフに切り替えることなどによって、その時点のトラフィック需要に合わせてネットワークの大きさを動的に変えることを伴う。しかし、他のあらゆるトポロジ変化と同様に、これらの操作はネットワーク性能に悪影響を及ぼしやすく、また、かなり頻繁に発生することがある。したがって、そのような事象からの回復時間を短くすることは、より重要な意味をもつ。短い回復時間なくしては、上記のエネルギー節約手段が広く採用される見込みがないからである。
【０００７】
関連する研究
トポロジ変化が存在する中でもＩＰネットワークのＱｏＳおよび可用性を高水準に維持することが必要であるため、収束期間中のネットワークサービスの中断を最小限に抑えるための取り組みが求められる。ＭＰＬＳネットワークでは、これは高速リルート（ＦＲＲ）により遂行される。つまり、起こり得る構成要素故障のそれぞれについて、それを迂回する専用の迂回経路が準備される。そのような故障が実際に発生した場合、トラフィックは、適切な迂回経路に自動的に進路変更される。このように、ＭＰＬＳ−ＦＲＲでは、パケット損失をほとんど無視できるものとしながら、５０ｍｓの故障回復時間が有効に保証される。
【０００８】
ＩＰネットワークのための類似したソリューションは、ＩＰ高速リルート（ＩＰ  ＦＲＲ）と呼ばれる。ＩＰ  ＦＲＲでは、故障した構成要素を越えて送信できないパケットは代替ルータに進路変更され、次に、この代替ルータがこのパケットをその宛先に転送する。しかし、専用のＭＰＬＳトンネルとして迂回経路が準備されているＭＰＬＳ−ＦＲＲとは異なり、ＩＰネットワークでは各ルータが独自のローカルなルーティング決定を行う。この、宛先ベースの転送パラダイムは、下記に説明するように、ＩＰ  ＦＲＲの実装において深刻な問題を提起する。
【０００９】
故障が発生して検出された直後は、ローカルリペアルータ（ＬＲＲ）と呼ばれる隣接のルータのみがその事実を知っている。したがって、ＬＲＲによってＬＲＲ以外の代替ネクストホップに経路変更されたパケットは、直接的または間接的に同じＬＲＲに戻されることがあるので、転送ループに入ってしまう可能性がある。等コストマルチパス（ＥＣＭＰ）方式およびループフリーオルタネート（ＬＦＡ）方式などのような、いくつかのＩＰ  ＦＲＲ提案では、ループフリーな配信を保証する一定の簡潔な特性を満たす代替隣接ノードのみにパケットが転送されるよう規定することによって、この問題を回避する。例えば、図１Ａに示される、ノード１０７が故障した後のネットワークを考える。ＬＦＡ方式では、１１０に宛てられたトラフィックを、ループフリーな代替ノードであるノード１０９に進路変更させることにより、この故障からノード１０５が回復することができる。
【００１０】
Ｕターン方式と呼ばれる、もう１つの方式は、ＬＲＲが上流の隣接ノードにパケットを戻すことを許可することによってＬＦＡを拡張するものである。この隣接ルータは次に、自身の隣接ルータのうち、ループフリーな代替ノードである１つにパケットを転送する。その結果、図１Ａのネットワーク内のリンク１０７−１０８が故障した場合、ノード１０７は、１１０に宛てられたパケットをノード１０５に送ることができ、ノード１０５がパケットをノード１０９に転送することによって、故障を回避することができる。
【００１１】
上記の方式は簡単に実装できるが、起こり得るすべての故障に対してループフリーな回復が保証されるわけではない。この問題は、ＬＲＲに、その方式によって規定された特性を満たす隣接ノードがない場合に発生し、特に、平均ノード次数が低いネットワークでよく発生する。評価研究によれば、ＬＦＡはＥＣＭＰよりも多くの故障からの保護を提供し、ＵターンはＬＦＡよりも多くの故障からの保護を提供するが、Ｕターンでさえも、通常は、起こり得るすべてのリンク故障の約９０％、ノード故障の７５％未満からの保護しか提供しないことも明らかになっている。例えば、図１Ａのネットワーク内のノード１０８が故障した場合、これらの方式のどちらでも、ＬＲＲ１０７から宛先１１０へのパケットのルーティングに成功できないが、図１Ｂを見ると、２重線で示すとおり、１０７から１１０への経路がまだ利用できることがわかる。
【００１２】
その他のＩＰ  ＦＲＲ方式では、迂回路上のパケットに目印をつけるために、さまざまな技法を使用する。例えば、トンネルを使用すること、故障した構成要素のリストをＩＰヘッダに追加すること、ｎｏｔ−ｖｉａアドレスと呼ばれる禁止アドレスを指定することなどである。ＳａｆｅＧｕａｒｄなどの方式では、故障した構成要素を間接的に識別するためにＩＰヘッダを修正することを提唱している。さらに、ＩＥＥＥ  ＩＮＦＯＣＯＭ議事録、「ＩＰ  ｆａｓｔ  ｒｅｒｏｕｔｅ：  Ｌｉｇｈｔｗｅｉｇｈｔ  ｎｏｔ−ｖｉａ  ｗｉｔｈｏｕｔ  ａｄｄｉｔｉｏｎａｌ  ａｄｄｒｅｓｓｅｓ」、２００９年、Ｇ．Ｅｎｙｅｄｉ、Ｐ．Ｓｚｉｌａｇｙｉ、Ｇ．ＲｅｔｖａｒｉおよびＡ．Ｃｓａｓｚａｒ、２７７１−２７７５頁に記載されている方式では、各宛先について代替ルーティングツリーをあらかじめ計算し、ＩＰヘッダのいくつかのビットを使用して望ましい転送経路を識別する。これらのソリューションでは、ほとんどの起こり得る故障に対して迅速な回復ができるが、重大な欠点がある。すなわち、進路変更されたパケットは、遅い経路のルータでのみ行われ得る余分な処理を経る必要があり、また場合によっては、追加の埋め込み情報によってパケットがＭＴＵサイズを超える場合には、パケットを分割する必要が生じることがある。
【００１３】
さらに、ＩＥＥＥ／ＡＣＭ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｎｅｔｗｏｒｋｉｎｇ、「Ｆａｓｔ  ｌｏｃａｌ  ｒｅｒｏｕｔｉｎｇ  ｆｏｒ  ｈａｎｄｌｉｎｇ  ｔｒａｎｓｉｅｎｔ  ｌｉｎｋ  ｆａｉｌｕｒｅｓ」、Ｓ．Ｎｅｌａｋｕｄｉｔｉ、Ｓ．Ｌｅｅ、Ｙ．Ｙｕ、Ｚ．−Ｌ．ＺｈａｎｇおよびＣ．−Ｎ．Ｃｈｕａｈ、２００７年、１５（２）：３５９−３７２頁で紹介されているインタフェース固有の転送方式では、ルータは、パケットの入力インタフェースに基づいて、ネットワーク上に故障が存在するかどうかを推定することができる。次に、パケットの宛先および入力インタフェースの両方を考慮して、パケットのネクストホップが決定される。著者らは、この方式では、あらゆる構成要素故障についてループフリーな迂回路が得られることを示しているが、これを達成するためには多大な費用を要するとともに、各ルータインタフェースのための専用の転送表を維持するという問題が伴う。
【００１４】
簡潔なＩＰ  ＦＲＲソリューションがないことが明らかなことから、代替のルーティングパラダイムについて多数の提案が提起された。それらは概してネットワークの経路多様性を利用するものである。これらの取り組みの１つは複数ルーティングコンフィギュレーション（ＭＲＣ）機構であり、バックアップのルーティングトポロジ（コンフィギュレーションと呼ばれる）を構築して、個々のリンクおよびノードが、少なくとも１つのバックアップトポロジ内に分離されるようにする。故障が発生した後、パケットは、故障した構成要素がその中に分離されている、あるコンフィギュレーションに沿ってルーティングされる。ＭＣＲでは迅速な回復に関する問題を解決することはできるが、各構成要素を分離するコンフィギュレーションを設計することおよび、ルーティングのために適切なコンフィギュレーションを選択することなどの、実装に関する問題がある。その他の研究では、所与の各宛先についてあらかじめ計算された無閉路有向グラフ（ＤＡＧ）に沿ってパケットをルーティングすることにより、経路の多様性を利用する。このルーティングパラダイムでは、パケットは必ずしも最短経路に沿ってルーティングされるわけではなく、さらに、起こり得るすべての故障からの保護をＤＡＧが提供するという保証はない。最後に大事なことを付け加えておくと、Ｇ．Ｒｅｔｖａｒｉ、Ｊ．Ｔａｐｏｌｃａｉ、Ｇ．ＥｎｙｅｄｉおよびＡ．Ｃｓａｓｚａｒ、「ＩＰ  ｆａｓｔ  ｒｅｒｏｕｔｅ：  Ｌｏｏｐｆｒｅｅ  ａｌｔｅｒｎａｔｅｓ  ｒｅｖｉｓｉｔｅｄ」、ＩＥＥＥ  ＩＮＦＯＣＯＭ議事録、２０１１年、では、ＬＦＡ方式で、起こり得るすべての故障について確実に回復が得られるようにするため、追加リンクを使用してネットワークを補強することが提案されている。
【００１５】
したがって、ネットワーク収束時間内に、パケットが、最短経路に沿って、または、最短経路上のリンク／ルータの１つが故障した場合は代替経路を通じて、宛先に確実に到達することを可能にできる方法または装置があることが望ましく、これによって、従来技術の欠点および複雑さが最小限に抑えられる。
【先行技術文献】
【非特許文献】
【００１６】
【非特許文献１】ＩＥＥＥ  ＩＮＦＯＣＯＭ議事録、「ＩＰ  ｆａｓｔ  ｒｅｒｏｕｔｅ：  Ｌｉｇｈｔｗｅｉｇｈｔ  ｎｏｔ−ｖｉａ  ｗｉｔｈｏｕｔ  ａｄｄｉｔｉｏｎａｌ  ａｄｄｒｅｓｓｅｓ」、２００９年、Ｇ．Ｅｎｙｅｄｉ、Ｐ．Ｓｚｉｌａｇｙｉ、Ｇ．ＲｅｔｖａｒｉおよびＡ．Ｃｓａｓｚａｒ、２７７１−２７７５頁
【非特許文献２】ＩＥＥＥ／ＡＣＭ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｎｅｔｗｏｒｋｉｎｇ、「Ｆａｓｔ  ｌｏｃａｌ  ｒｅｒｏｕｔｉｎｇ  ｆｏｒ  ｈａｎｄｌｉｎｇ  ｔｒａｎｓｉｅｎｔ  ｌｉｎｋ  ｆａｉｌｕｒｅｓ」、Ｓ．Ｎｅｌａｋｕｄｉｔｉ、Ｓ．Ｌｅｅ、Ｙ．Ｙｕ、Ｚ．−Ｌ．ＺｈａｎｇおよびＣ．−Ｎ．Ｃｈｕａｈ、２００７年、１５（２）：３５９−３７２頁
【非特許文献３】Ｇ．Ｒｅｔｖａｒｉ、Ｊ．Ｔａｐｏｌｃａｉ、Ｇ．ＥｎｙｅｄｉおよびＡ．Ｃｓａｓｚａｒ、「ＩＰ  ｆａｓｔ  ｒｅｒｏｕｔｅ：  Ｌｏｏｐｆｒｅｅ  ａｌｔｅｒｎａｔｅｓ  ｒｅｖｉｓｉｔｅｄ」、ＩＥＥＥ  ＩＮＦＯＣＯＭ議事録、２０１１年
【非特許文献４】Ｋ．Ｔｓｅ、「ＡＴ＆Ｔｓ  ｐｈｏｔｏｎｉｃ  ｎｅｔｗｏｒｋ」、ＯＦＣ／ＮＦＯＥＣ  ２００８、２００８年３月
【非特許文献５】Ｋ．Ｗａｎｇ、Ｍ．ＡｌｉおよびＪ．Ｄｅｏｇｕｎ、「Ｍｕｌｔｉｃａｓｔ  ｒｏｕｔｉｎｇ  ｉｎ  ４０  Ｇｂ／ｓ  ｈｅｔｅｒｏｇｅｎｅｏｕｓ  ｏｐｔｉｃａｌ  ｎｅｔｗｏｒｋｓ」、ＩＥＥＥ  ＩＣＣ、第３巻、１６２０−１６２４頁、２００５年５月
【非特許文献６】Ｙ．ＸｉｏｎｇおよびＬ．Ｍａｓｏｎ、「Ｒｅｓｔｏｒａｔｉｏｎ  ｓｔｒａｔｅｇｉｅｓ  ａｎｄ  ｓｐａｒｅ  ｃａｐａｃｉｔｙ  ｒｅｑｕｉｒｅｍｅｎｔｓ  ｉｎ  ｓｅｌｆ−ｈｅａｌｉｎｇ  ＡＴＭ  ｎｅｔｗｏｒｋｓ」、ＩＥＥＥ／ＡＣＭ  Ｔｒａｎｓ．Ｎｅｔｗ．、７（１）：９８−１１０頁、１９９９年
【非特許文献７】Ｅ．Ｂ．Ｂａｓｃｈ、Ｒ．Ｅｇｏｒｏｖ、Ｓ．ＧｒｉｎｇｅｒｉおよびＳ．Ｅｌｂｙ、「Ａｒｃｈｉｔｅｃｔｕｒａｌ  ｔｒａｄｅｏｆｆｓ  ｆｏｒ  ｒｅｃｏｎｆｉｇｕｒａｂｌｅ  ｄｅｎｓｅ  ｗａｖｅｌｅｎｇｔｈ−ｄｉｖｉｓｉｏｎ  ｍｕｌｔｉｐｌｅｘｉｎｇ  ｓｙｓｔｅｍｓ」、ＩＥＥＥ  Ｓｅｌｅｃｔｅｄ  Ｔｏｐｉｃｓ  ｉｎ  Ｑｕａｎｔｕｍ  Ｅｌｅｃｔｒｏｎｉｃｓ、１２（４）：６１５−６２６頁、２００６年
【非特許文献８】ｈｔｔｐ：／／ｗｗｗ．ｃｓ．ｗａｓｈｉｎｇｔｏｎ．ｅｄｕ／ｒｅｓｅａｒｃｈ／ｎｅｔｗｏｒｋｉｎｇ／ｒｏｃｋｅｔｆｕｅｌ／、「Ｒｏｃｋｅｔｆｕｅｌ：Ａｎ  ＩＳＰ  ｔｏｐｏｌｏｇｙ  ｍａｐｐｉｎｇ  ｅｎｇｉｎｅ」
【非特許文献９】Ｍ．Ｇｊｏｋａ、Ｖ．ＲａｍおよびＸ．Ｙａｎｇ、ＩＥＥＥ  ＣＯＭＳＷＡＲＥ議事録、２００７年、「Ｅｖａｌｕａｔｉｏｎ  ｏｆ  ＩＰ  ｆａｓｔ  ｒｅｒｏｕｔｅ  ｐｒｏｐｏｓａｌｓ」
【非特許文献１０】Ｍ．Ｇｏｙａｌ、Ｍ．Ｓｏｐｅｒｉ、Ｅ．Ｂａｃｃｅｌｌｉ、Ｇ．Ｃｈｏｕｄｈｕｒｙ、Ａ．Ｓｈａｉｋｈ、Ｈ．ＨｏｓｓｅｉｎｉおよびＫ．Ｔｒｉｖｅｄｉ、ＩＥＥＥ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  Ｓｕｒｖｅｙｓ  ａｎｄ  Ｔｕｔｏｒｉａｌｓ、２０１１年、「Ｉｍｐｒｏｖｉｎｇ  ｃｏｎｖｅｒｇｅｎｃｅ  ｓｐｅｅｄ  ａｎｄ  ｓｃａｌａｂｉｌｉｔｙ  ｉｎ  ＯＳＰＦ：Ａ  ｓｕｒｖｅｙ」
【発明の概要】
【発明が解決しようとする課題】
【００１７】
本発明の１つの目的は、ネットワーク収束時間内に、ネットワークの最短経路または代替経路のどちらかに沿って、パケットが確実に宛先に到達できるようにする、パケット分類の方法および装置を提供することである。
【課題を解決するための手段】
【００１８】
前節で言及したすべてのソリューションは、起こり得るすべての故障からは保護ができないか、または実装が困難であるか、またはその両方である。本明細書では、ディスジョイントパスリカバリ（ＤｉｓＰａｔｈ）と呼ぶ、簡潔で効率的な、新規のＩＰ  ＦＲＲ方式を開示し、この方式は下記の長所をもつ：
１）  ＤｉｓＰａｔｈでは、従来の宛先ベースのＩＰルーティングパラダイムが保たれ、安定したネットワーク状態においては、パケットは最短経路に沿って宛先まで転送される。
【００１９】
２）  パケットは決して修正されない（ただし、ＴＴＬのデクリメントおよび新しいヘッダチェックサムの計算などの適切な標準的処理は除く）。
【００２０】
３）  ＤｉｓＰａｔｈが各ルータの転送表に維持する宛先ノードごとのポインタは、わずか２つである。１つはプライマリの、もう１つは代替のネクストホップ隣接ノードへのポインタである。この数は、明らかに、回復方式を実装するために必要な最小のポインタ数である。
【００２１】
４）  回復経路が存在する場合は、ＤｉｓＰａｔｈでは全範囲の保護が提供される。つまり、ネットワークトポロジに関わりなく、起こり得る単一構成要素の故障のすべてから保護される。
【００２２】
５）  ＤｉｓＰａｔｈ方式は、複数の故障が存在する場合でも、円滑に、一時的なルーティングループを回避する。
【００２３】
これらの長所２および３により、このソリューションは現在のルータ技術を使用して比較的簡単に実装可能になることに留意されたい。また、冗長ルータおよびリンクの動的非アクティブ化によって平均ノード次数が非常に低いことのある、エネルギー効率の良いネットワークでは、長所４が非常に望ましいことにも留意されたい。
【００２４】
さらに、代表的なネットワークインスタンスにおけるシミュレーションにより、ＤｉｓＰａｔｈは、性能の尺度としてよく使われているストレッチ、つまり、故障したネットワーク要素を避ける最短経路の長さに対するリルートされたパケットの軌跡の長さの比に関して、非常に高性能であることが示されている。このことは、上記の長所と相まって、ＤｉｓＰａｔｈが、全範囲を確実に保護する簡潔で実用的なＩＰ  ＦＲＲ方式の設計という目標を満たすことを示唆する。
【００２５】
したがって、本発明の１つの態様によれば、宛先ノードをもつ到着パケットをルーティングするためのネットワーク要素がネットワークノードにおいて提供され、このネットワーク要素は、転送情報記憶装置に格納されている転送情報表の中の、宛先ノードに関連する第１および第２のポインタにのうちの１つに従って、到着パケットをネクストホップ隣接ノードに転送するよう構成されているルータを備える。第１のポインタは、そのネットワークノードから宛先ノードまでの最短経路上にある第１のネクストホップ隣接ノードを指し、第２のポインタは第１のネクストホップ隣接ノードとは異なる第２のネクストホップ隣接ノードを指す。第２のネクストホップ隣接ノードは、そのネットワークノードおよび宛先ノードの両方を含む、宛先ノードを根とするシンクツリーとの重なりが最も大きい候補サイクル上にある。
【００２６】
本発明のいくつかの実施形態では、ルータは、第１のポインタに指示されるネクストホップ隣接ノード以外の隣接するノードから到着パケットが到着した場合は、第１のポインタに従って到着パケットを転送するよう構成されている。これらの実施形態のいくつかでは、ルータは、第１のポインタに指示されるネクストホップ隣接ノードから到着パケットが到着した場合は、第２のポインタに従って到着パケットを転送するよう構成されている。これらの実施形態のいくつかでは、ルータは、第１のポインタに指示されるネクストホップ隣接ノードがパケットを転送できない場合には、第２のポインタに従って到着パケットを転送するよう構成されている。これらの実施形態のいくつかでは、ルータは、第１のポインタに指示されるネクストホップ隣接ノードへのリンクがパケットを転送できない場合には、第２のポインタに従って到着パケットを転送するよう構成されている。
【００２７】
本発明のこの態様の他の実施形態では、ネットワーク要素はさらに、転送情報記憶装置に格納されている転送情報表の中に、宛先ノードに関連する第１のフラグおよび第２のフラグをもつ。第１のフラグは、そのネットワークノードから宛先ノードまでの最短経路の稼働状態を示し、第２のフラグは、そのネットワークノードから第２のネクストホップノードまでのリンクが、宛先ノードを根とするシンクツリーの要素であるかどうかを示す。また、ルータは、第１のフラグが非稼働状態を示し、かつ第２のフラグがそのネットワークノードから第２のネクストホップノードまでが宛先ノードを根とするシンクツリーの要素であることを示し、かつ到着パケットが第１のポインタに指示されるネクストホップ隣接ノードから到着した場合には、到着パケットを破棄するよう構成されている。
【００２８】
これらの実施形態のいくつかでは、ルータは、到着パケットが、第１のポインタに指示されるネクストホップ隣接ノード以外の隣接するノードから到着した場合は、第１のポインタに従って到着パケットを転送するよう構成されている。これらの実施形態のうち他のものでは、ルータは、第１のポインタに指示されるネクストホップ隣接ノードから到着パケットが到着した場合は、第２のポインタに従って到着パケットを転送するよう構成されている。これらの実施形態のうち他のものでは、ネットワーク要素には、第１のポインタに指示されるネクストホップ隣接ノードがパケットを転送できない場合には、第２のポインタに従って到着パケットを転送するよう構成されたルータが備わる。これらの実施形態のさらに他のものでは、ルータは、第１のポインタに指示されるネクストホップ隣接ノードへのリンクがパケットを転送できない場合には、第２のポインタに従って到着パケットを転送する。
【００２９】
本発明のこの態様の他の実施形態では、ネットワーク要素は、そのネットワーク要素がノードとして含まれているネットワークの新しいネットワークコンフィギュレーションを示すネットワークコンフィギュレーション情報が到着した場合には、新しいネットワークコンフィギュレーションに相当するシンクツリー上の、そのネットワークノードの先祖ノードの再構成が完了した期間に続く時点で、転送情報表が更新されるよう構成されている。
【００３０】
本発明の別の様態によれば、記憶装置に格納されたネットワークコンフィギュレーションをもつネットワークの第１のネットワークノード内の転送情報記憶装置に格納されている転送情報表の中の、宛先ノードに関連するプライマリポインタおよびバックアップポインタを自動的に計算する方法が開示される。この方法には、そのネットワークのネットワークコンフィギュレーションを使用して、宛先ノードを根とするシンクツリーを計算するステップ、そのネットワークのネットワークコンフィギュレーションを使用して、第１のネットワークノードから宛先ノードまでの最短経路を計算するステップ、第１のネットワークノードから宛先ノードまでの最短経路上にある第１のネクストホップ隣接ノードを指すようにプライマリポインタを方向付けるステップ、第１のネクストホップ隣接ノードとは異なる第２のネクストホップ隣接ノードを指すようにバックアップポインタを方向付けるステップがあり、第２のネクストホップ隣接ノードは、第１のネットワークノードおよび宛先ノードの両方を含む、宛先ノードを根とするシンクツリーとの重なりが最も大きい候補サイクル上にある。
【００３１】
これらの実施形態のいくつかには、さらに、そのネットワークノードおよび宛先ノード以外のネットワークのすべてのノードについて、第２の計算ステップおよび方向付けステップを繰り返すステップがある。これらの実施形態のいくつかには、さらに、ネットワークコンフィギュレーションへの更新を受け取るステップ、その更新を記憶装置に格納するステップ、そのネットワークの更新済みネットワークコンフィギュレーションを使用して、宛先ノードを根とする新しいシンクツリーを計算するステップ、新しいネットワークコンフィギュレーションに相当するシンクツリー上の、そのネットワークノードの先祖ノードの再構成が完了した期間に続く時点で、そのネットワークノード以外の、ネットワークのすべてのノードについて第２の計算ステップおよび方向付けステップを繰り返すことによって、転送情報表を更新するステップがある。これらの実施形態のいくつかでは、期間は、新しいシンクツリー内で最も近くにある先祖から、新しいシンクツリー内の最も近い先祖から宛先ノードへの経路が変更されていないネットワークノードまでのホップカウント距離に従って計算される。
【００３２】
本発明のさらに別の態様によれば、記憶装置に格納されたネットワークコンフィギュレーションをもつネットワークの第１のネットワークノード内の転送情報記憶装置に格納されている転送情報表の中の、宛先ノードに関連するバックアップポインタを自動的に計算する方法が開示される。この方法には、そのネットワークのネットワークコンフィギュレーションを使用して、宛先ノードを根とするシンクツリーを計算するステップ、そのネットワークのコンフィギュレーションを使用して、第１のネットワークノードおよび宛先ノードの両方を含むサイクルのうち、宛先ノードを根とするシンクツリーとの重なりが最も大きい候補サイクルについての判定基準（ｔｉｅ−ｂｒｅａｋｉｎｇ  ｃｒｉｔｅｒｉｏｎ）を含む最短の候補サイクルを計算するステップ、そのネットワークのネットワークコンフィギュレーションを使用して、第１のネットワークノードから宛先ノードまでの最短経路を計算するステップ、第１のネットワークノードから宛先ノードまでの最短経路上にある第１のネクストホップ隣接ノードを決定するステップ、および、第１のネクストホップ隣接ノードとは異なる第２のネクストホップ隣接ノードを指すようにバックアップポインタを方向付けるステップがある。
【００３３】
本発明のこの態様の実施形態のいくつかには、さらに、そのネットワークノードおよび宛先ノード以外のネットワークのすべてのノードについて、計算ステップ、決定ステップおよび、方向付けステップを繰り返すステップがさらにある。
【００３４】
注：下記の記載および図は、本発明の原理のみを説明している。したがって、本明細書に明示的に記載または図示されてはいないが、本発明の原理を具体化し、かつ本発明の趣旨および範囲に含まれる、さまざまな装置を当業者は考案できるということが理解されよう。さらに、本発明に記載されるすべての例は、主として、発明者が提案する本発明の原理および概念の理解において読者を助け、技術を促進するための教示のみを明確に意図しており、そのような具体的に記載された例および条件に限定されないとみなされることを意図している。さらに、本発明の原理、様態および実施形態を記載する、本明細書のすべての記述は、それらについての具体例とともに、それらについての等価物を含むよう意図されている。
【００３５】
本発明は、図を参照することにより、下記の本発明の実施形態の詳細な説明から、さらに理解されるであろう。図では、同じ参照番号を使用して同じ要素を表す。
【図面の簡単な説明】
【００３６】
【図１Ａ】従来技術による連結リンクをもつノードのネットワークを示す図である。
【図１Ｂ】従来技術による連結リンクをもつノードのネットワークを示す図である。
【図２Ａ】本発明による連結リンクをもつノードのネットワークの、稼働中の様子を示す図である。
【図２Ｂ】本発明による連結リンクをもつノードのネットワークの、稼働中の様子を示す図である。
【図３】本発明の一実施形態による、プライマリ転送ノードおよびバックアップ転送ノードを計算する方法の構造図を示す図である。
【図４】本発明の一実施形態による、パケットをプライマリ転送ノードおよびバックアップ転送ノードにルーティングする方法の構造図を示す図である。
【図５】本発明の他の実施形態による、パケットをプライマリ転送ノードおよびバックアップ転送ノードにルーティングする方法の構造図を示す図である。
【図６Ａ】本発明の一実施形態による連結リンクをもつノードのネットワークの、稼働中の様子を示す図である。
【図６Ｂ】本発明の一実施形態による連結リンクをもつノードの、ネットワークの稼働中の様子を示す図である。
【発明を実施するための形態】
【００３７】
下記の記載には、多数の具体的な詳細が述べられている。ただし、本発明の実施形態は、これらの具体的詳細なしで実施してもよいことは理解されよう。他の例では、この記載の理解が不明瞭にならないように、よく知られている回路、構造、および技法は詳細には示されていない。しかし、そのような具体的詳細がなくても、本発明は当業者によって実施できることが理解されよう。その他の例では、本発明が不明瞭にならないように、制御構造、ゲートレベル回路、および完全なソフトウェア命令シーケンスは詳細には示されていない。当業者は、ここに含まれる記載を使用して、必要以上の実験を行うことなく適切な機能を実装することができるであろう。
【００３８】
本明細書における「１つの実施形態」、「一実施形態」、「例示的実施形態」などの言及は、説明された実施形態に特定の特徴、構造、または特性が含まれ得ることを示すが、すべての実施形態がその特定の特徴、構造、または特性を必ずしも含まなくてもよい。さらに、これらの句は必ずしも同一の実施形態を言及していなくてもよい。また、ある特定の特徴、構造、または特性が１つの実施形態に関して記載されている場合は、明示的に記載されているかどうかに関わらず、そのような特定の特徴、構造、または特性を他の実施形態に関して実施することは当業者の知識の範囲内であると考えられる。
【００３９】
下記の記載および請求項において、「結合」および「連結」という用語およびそれらの派生語が使用されることがある。これらの用語は相互の同義語とは意図されていないことを理解されたい。「結合」は、複数の要素が、直接物理的に、または電気的に互いに接触していても接触していなくても、互いに協働または相互作用することを示すために使用される。「連結」は、互いに結合している複数の要素の間に通信が確立していることを示すために使用される。
【００４０】
図に示される技法は、１つまたは複数の電子装置（例えば、ネットワーク要素）上で格納および実行されるコードおよびデータを使用して実装することができる。このような電子装置は、機械記憶媒体（例えば、磁気ディスク、光ディスク、ランダムアクセスメモリ、リードオンリーメモリ、フラッシュメモリ装置など）および機械通信媒体（例えば、搬送波、赤外線信号、デジタル信号などのような、電気的、光学的、音響的またはその他の形式の伝播信号など）のような機械読み取り可能な媒体を使用して、コードおよびデータを格納ならびに（内部的におよびネットワークを通じて他の電子装置との間で）通信する。さらに、このような電子装置は通常、記憶装置など、１つまたは複数の他の構成要素に結合された１つまたは複数のプロセッサのセットと、１つまたは複数のユーザ入出力装置（例えば、キーボードおよび／またはディスプレイ）と、ネットワーク連結とを備える。プロセッサのセットと他の構成要素との結合は通常、１つまたは複数のバスおよびブリッジ（バスコントローラとも呼ばれる）を通じて行われる。記憶装置および、ネットワークトラフィックを搬送する信号は、それぞれ、１つまたは複数の機械記憶媒体および機械通信媒体を表す。したがって、ある電子装置の記憶装置は通常、その電子装置の１つまたは複数のプロセッサのセットで実行するためのコードおよび／またはデータを格納する。当然ながら、本発明の実施形態の１つまたは複数の部分を、異なる組み合わせのソフトウェア、ファームウェア、および／またはハードウェアを使用して実装してもよい。
【００４１】
本明細書では、１つのネットワーク要素（例えば、ルータ、スイッチ、ブリッジなど）は１つのネットワーク機器であり、ネットワーク上の他の機器（例えば、他のネットワーク要素、コンピュータ端末ステーションなど）と通信可能に相互連結するハードウェアおよびソフトウェアが含まれる。カスタマーコンピュータ端末ステーション（例えば、ワークステーション、ラップトップ、パームトップ、携帯電話など）は、インターネットを介して提供されるコンテンツ／サービス、および／または、インターネットなどの関連ネットワーク上で提供されるコンテンツ／サービスにアクセスする。コンテンツおよび／またはサービスは通常、サービスまたはコンテンツのプロバイダに所属する、１つまたは複数のサーバコンピューティング端末ステーションによって提供され、公開ウェブページ（無料コンテンツ、ストアフロント、検索サービスなど）、非公開ウェブページ（例えば、ユーザ名／パスワードを使用してアクセスする、電子メールサービスを提供するウェブページなど）、ＶＰＮを介した企業ネットワークなどを含んでよい。通常、顧客のコンピューティング端末ステーションは（例えば、無線でアクセスネットワークに結合された顧客の構内設備を通じて）エッジネットワーク要素に結合されており、このエッジネットワーク要素はインターネットのコアネットワーク要素を通じてサーバコンピューティング端末ステーションに結合されている。
【００４２】
下記の図において、同じ参照番号は、同じ要素を表すために使用される。
【００４３】
ネットワークモデル
下記の、本発明の実施形態は、ＩＰネットワークに関して記載される。単一のルーティングエリアを成すＩＰネットワークを考える。すべてのルータはリンク状態情報を維持し、この情報によってルータはネットワークトポロジを計算することができ、その結果、ネットワーク内の他のすべてのルータへの最短経路を計算することができる。ルータは、この情報を使用して、転送情報ベース（ＦＩＢ）表に値を入力する。ＩＰパケットがルータに到着すると、ルータはパケットの宛先アドレスをＦＩＢで照合して、ネクストホップ隣接ノード、すなわちその宛先への最短経路上の次のルータを決定し、それに従ってパケットを転送する。簡単にするために、ある宛先への最短経路が複数ある場合には、ルータは、知られている一貫した判定基準に従って、唯一のネクストホップ隣接ノードを選択すると仮定する。
【００４４】
ネットワークは、すべてのルータから見たネットワークトポロジが同じであるときに、安定状態にあると考えられる。トポロジが変化した場合は、追加または削除された構成要素（ルータまたはリンクのどちらか）に隣接するルータは、変化を検出し、リンク状態アドバタイズメント（ＬＳＡ）メッセージを作成して、トポロジが変化したことを他のルータに通知する。この情報はフラッディングによってネットワーク内で伝播され、すべてのルータがこれを使用してＦＩＢを更新する。収束時間とは、最初にトポロジ変化が検出されてから、すべてのルータがＦＩＢを更新し終わる時点までの時間間隔を指し、この時間の後にネットワークは再び安定状態になる。
【００４５】
以降の節では、ネットワークは無向グラフＧ（Ｖ；Ｅ）としてモデル化され、ここでＶはルータ（ノードとも呼ぶ）のセットを示し、Ｅはリンク（エッジとも呼ぶ）のセットを表す。各リンクｅ∈Ｅは双方向性であり、また、ルーティングの目的で、関連する整数の重みｗ（ｅ）を有する。さらに、Ｇは２重連結されていると仮定される。つまり、Ｇは、単一のリンク故障またはノード故障が起こった場合には連結されたままである。上記の仮定のいくつかは説明をより明確にするだけのためのものであるという点に留意されたい。開示されているように、本発明の方式の方法を、非２重連結グラフおよび、リンクがもつ重みが各方向で異なるグラフに適応させることは容易に可能である。
【００４６】
方式の概要
ＤｉｓＰａｔｈは、メンガーの定理による、「２重連結されたネットワークでは、すべてのノードｖは所与の宛先ｔまでの２本のノード素な（ｎｏｄｅ−ｄｉｓｊｏｉｎｔ）経路をもつ」という事実に基づく。したがって、ｖからｔまでの最短経路上で１つの故障が発生した場合でも、なお代替経路が利用可能である。
【００４７】
ｐｖ（ｔ）は宛先ｔについてのｖのプライマリ隣接ノード、つまりｔへの最短経路上のｖのネクストホップ隣接ノードを示すとする。故障が発生した場合、ノードｖはパケットを代替経路に進路変更させる。また、ｂｖ（ｔ）はバックアップ隣接ノード、つまり代替経路上のｖのネクストホップ隣接ノードを示すとする。
【００４８】
本発明の実施形態によると、ノードｖが、ｔへのプライマリ経路上で故障が発生したかどうかを知る場合は２つある。標準的な場合は、故障にｖが隣接しており、故障を直接検出するというものである。もう１つは、ｔに宛てられたパケットをｖがｐｖ（ｔ）から受け取る場合で、これは安定状態では起こらないと考えられる。どちらの場合も、ｖはパケットをバックアップ隣接ノードｂｖ（ｔ）に転送する。この方法は、パケット自体に修正を加えることなく実装できることに留意されたい。
【００４９】
例として、図１Ｂのネットワークで、ノード１３０に宛てられたパケットがノード１２７に到着したが、ノード１２８が故障している場合を考える。ノード１２８が故障した後、ノード１２７には、ノード１２５、１２３および１２１を介したノード１３０への代替経路がある。ノード１２５がノード１２７から、ノード１３０に宛てられたパケットを受け取ると、ノード１２５は故障を検出し、そのパケットを自身のバックアップ隣接ノード（ノード１２３）に送る。ノード１２３も故障を検出し、パケットを自身のバックアップ隣接ノード（ノード１２１）に送る。次にノード１２１はパケットを宛先ノード１３０に送る。
【００５０】
ＤｉｓＰａｔｈがループフリーな回復の提供に成功するかどうかは、各ノードがすべての宛先についてプライマリおよびバックアップの隣接ノードを適切に選択するかどうかにかかっている。この目的のために、各ノードｖは、ｖおよび宛先ｔの両方を含む簡潔な最短サイクルＣｖ；ｔを計算する。Ｃｖ；ｔの中でｖに隣接する２つのノードが、プライマリおよびバックアップの隣接ノードとなる。ネットワークは２重連結されているので、このようなサイクルは必ず存在するが、１つだけとは限らない。次の例で説明するとおり、どの最短サイクルでも正しく機能するわけではないので、このことは、深刻な問題を提起する。
【００５１】
図２のネットワークを考える。ここには、ノード２０６および宛先ノード２１２を含む最短サイクルが複数存在することに注目されたい。また、ノード２０１および２１２などについても同様である。ノード２０６および２０３は点線で表された左側のサイクルを選び、ノード２０１および２０４は破線で表された右側のサイクルを選ぶと仮定する。リンク（２０６；２０８）が故障した場合、ノード２０６には、２１２に宛てられたパケットを２０３に転送する以外に選択肢はなく、次に、２０３はこのパケットを２０１に送らなければならない。しかし、２０３はノード２０１のプライマリ隣接ノード（ノード２０１をノード２０４に連結する太い矢印で示される）ではなく、バックアップ隣接ノードでもない（ノード２０１は破線で表された右側のサイクルを使用しているので、バックアップ隣接ノードは２０２である）ので、ノード２０１はパケットをノード２０４（ノード２１２に近い方）に転送し、ノード２０４はパケットを前方のノード２０６に送るが、ノード２０６は、リンク（２０６；２０８）の故障に起因してパケットがサイクルを開始したノードである。したがって、パケットは転送ループに入るが、これは望ましいことではない。
【００５２】
しかし、本発明の一実施形態によれば、適切なサイクルの選択という問題を解決する簡潔で洗練されたソリューションがあり、下記にこれを開示する。Ｔ（ｔ）がｔのシンクツリー、つまり、他のすべてのノードからｔまでの最短経路の連合体により形成された、ｔを根とするツリーを示すとする。文献において、シンクツリーは、リバース最短経路ツリー（ｒＳＰＴ）と呼ばれることもある。ネットワークが安定状態にあるときは、すべてのノードが同一の判定基準を適用する限り、各ノードは独自にＴ（ｔ）を決定することができる。
【００５３】
次に、本発明を実施する方法によれば、最短サイクルの計算において、シンクツリー自体が判定基準として使用される。詳細には、ノードｖは、ｖおよびｔを含む最短サイクルを計算するとき、Ｔ（ｔ）との重なりがより大きいサイクルを優先して判定を行う。これは、リンクの重みを適切に操作することにより達成される。
【００５４】
このようにしてノードｖにより計算されたサイクルＣｖ；ｔは、「Ｃｖ；ｔ内のｖの２つの隣接ノードのうち１つは、ｔへの最短経路上の次のノードなので、当然それがプライマリ隣接ノードｐｖ（ｔ）になる」という特性をもつことがわかる。また、この特質によって、下記の非常に有益な結果が得られることもわかる：
これにより、ネットワークが安定状態にあるときは、パケットはその宛先までの最短経路に沿って確実にルーティングされる。
【００５５】
これにより、単一のリンク故障またはノード故障の場合は、転送ループのない迅速な回復が保証される。
【００５６】
本発明の実施形態には２つの協調する様態がある。１つ目は一連のステップであり、下記に擬似コードの形で示され、さらにステップの構造図である図３と関連付けて記載される。この一連のステップは、ネットワークが安定状態にあるときに、各ノードｖがそのＦＩＢ表に値を入力するために、つまり、各宛先ノードｔについてのプライマリ隣接ノードおよびバックアップ隣接ノードを決定するために実行される。
【００５７】
この方法には、３つの大まかなステップがある：
ステップ１：シンクツリーの計算。ノードｖは、すべてのノードに共通する既定の基準による判定結果（ｔｉｅ  ｒｅｓｏｌｖｅｄ）を使って、ｔのシンクツリーＴ（ｔ）を計算する。Ｔ（ｔ）内でのｖの親は、直ちにプライマリ隣接ノードｐｖ（ｔ）として指定される。
【００５８】
ステップ２：重み操作。Ｔ（ｔ）に所属するリンクの重みは、この後の最短サイクルの計算において、Ｔ（ｔ）との重なりがより大きいサイクルを優先して決定が行われる（ｔｉｅｓ  ａｒｅ  ｂｒｏａｋｅｎ）ように、わずかに減じられる。すべてのリンクｅ∈Ｅについて、一時的な実数値の重みｗｔ（ｅ）が下記のとおり定義されている：
【００５９】
【数１】
2014534776.tif 000003
ここで、εは
【００６０】
【数２】
2014534776.tif 000004
などの正の定数である。
【００６１】
ステップ３：最短サイクルの計算。ノードｖは、ｖおよびｔを含む最短サイクルＣｖ；ｔを、重みｗｔ（・）に関して、任意の適切な方法を用いて計算する。後で説明するとおり、Ｃｖ；ｔ内のｖの２つの隣接ノードのうち１つはｐｖ（ｔ）なので、もう１つの隣接ノードはバックアップ隣接ノードｂｖ（ｔ）として選択される。
【００６２】
所与のノードｖにおけるＦＩＢ表の作成方法の擬似コード表現
１：ｆｏｒ  すべてのノードｔ≠ｖについて  ｄｏ
２：重みｗ（・）に関して、ｔのシンクツリーＴ（ｔ）を計算する｛Ｔ（ｔ）はｔを根とする｝
３：ｐｖ（ｔ）＝Ｔ（ｔ）内のｖの親
４：ｆｏｒ  すべてのリンクｅについて  ｄｏ
５：ｉｆ  ｅ∈Ｔ（ｔ）  ｔｈｅｎ
６：    ｗｔ（ｅ）＝（１−ε）・ｗ（ｅ）
７：ｅｌｓｅ
８：    ｗｔ（ｅ）＝ｗ（ｅ）
９：重みｗｔ（・）に関して、ｖおよびｔの両方を含む最短の簡潔なサイクルＣｖ；ｔを計算する｛ｖはＣｖ；ｔ内に２つの隣接ノードをもつ。うち１つはｐｖ（ｔ）｝
１０：ｂｖ（ｔ）＝Ｃｖ；ｔ内のｖのもう１つの隣接ノード
【００６３】
次に、図３を参照すると、この方法の一実施形態による構造図表現が見て取れる。この方法は、ネットワークが安定状態にあるときに、ノードｖについてステップ３０１で開始する。ステップ３０２で条件ステップに入り、ノードｖ自体ではない、ネットワークＶ内のすべての宛先ノードｔについて後続の計算を実行する。ステップ３０３で、リンクの重みに関するネットワークコンフィギュレーション情報Ｗ（・）を使用して、宛先ノードｔを根とするシンクツリーＴ（ｔ）が決定される。ステップ３０４で、シンクツリーＴ（ｔ）を使用して、Ｔ（ｔ）内でのｖの親をノードｐｖ（ｔ）として割り当てる。次に、ステップ３０５で、ネットワーク内のすべてのリンクを調査する条件ループに入り、ステップ３０６で、個々のエッジがシンクツリーＴ（ｔ）の中のエッジであるかどうかを判定する。それぞれのエッジがＴ（ｔ）内のエッジでない場合は、ステップ３０７で、その個別のエッジについての修正済みの重みがその初期の重みとして設定される。そのそれぞれのエッジがシンクツリーＴ（ｔ）内のエッジである場合は、ステップ３０８で、そのエッジについての修正済みの重みが、その初期の重みより増分値分だけ小さい値として設定される。前述したとおり、条件ループ３０５内のステップの最終的な効果は、シンクツリーＴ（ｔ）のエッジが簡潔なサイクル間での優先的判定基準（ｔｉｅ−ｂｒｅａｋｅｒ）となるように、それらのエッジの重みを減少させることである。
【００６４】
次に、ステップ３０９で、修正済みの重みＷｔ（・）を使用して、ｖおよびｔを含む最も簡潔なサイクルＣｖ；ｔが計算される。ステップ３１０で、Ｃｖ；ｔ内のノードｖの２つの隣接ノードは、ノードｖの望ましいプライマリ隣接ノードｐｖ（ｔ）およびバックアップ隣接ノードｂｖ（ｔ）である。プライマリ隣接ノードｐｖ（ｔ）はステップ３０４ですでに知られているので、Ｃｖ；ｔ内の２つの隣接ノードのうちの他方が、バックアップ隣接ノードｂｖ（ｔ）として割り当てられる。ステップ３１１で、特定のノードｖについてのループが終わり、制御はステップ３０２に戻る。ステップ３０２が完了すると、この方法は、ステップ３１２で終了する。
【００６５】
本発明の第２の態様は、各ノードｖがパケットを受け取るたびにｖにより実行されて、パケットをどのようにルーティングするかを決定する、一連のステップである。この一連のステップは、下記に擬似コードの形で示され、さらにステップの構造図である図４と関連付けて記載される。ノードが故障すると、そのノードに付随するすべてのリンクも利用不可能になるので、この第２の一連のステップでは、リンク故障とノード故障を区別する必要はなく、その振る舞いはいずれの場合も同一である。
【００６６】
ノードｖにおけるパケットのルーティング方法の擬似コード表現
１：ｔ＝パケットの宛先  ｛ｔ≠ｖと仮定する｝
２：ｉｆ  リンク（ｖ，ｐｖ（ｔ））が利用不可能であるか、またはパケットが直接ｐｖ（ｔ）から到着した  ｔｈｅｎ
３：    ｉｆ  リンク（ｖ，ｂｖ（ｔ））が利用不可能  ｔｈｅｎ
４：        パケットを破棄する
５：    ｅｌｓｅ
６：        パケットをｂｖ（ｔ）に転送する  ｛バックアップ隣接ノード｝
７：ｅｌｓｅ
８：    パケットをｐｖ（ｔ）に転送する  ｛プライマリ隣接ノード｝
【００６７】
次に図４を参照すると、この方法の一実施形態による構造図表現が見て取れる。この方法は、ステップ４０１で開始する。ステップ４０２で、ノードｖにおいて、ノードｔに宛てられたパケットが受け取られる。ステップ４０３で、そのパケットがプライマリ隣接ノードｐｖ（ｔ）から到着したのかどうか問われる。答えが「ＮＯ」の場合は、ステップ４０４で、隣接ノードｐｖ（ｔ）が利用可能かどうか問われる。答えが「ＮＯ」の場合は、ステップ４０５で、リンクｂｖ（ｔ）が利用可能かどうか問われる。この問いの答えが「ＮＯ」の場合は、プライマリおよびバックアップのどちらの隣接ノードも利用可能ではないので、ステップ４０６でパケットは破棄される。この方法は次にステップ４０７で終了する。ステップ４０５での判定が「ＹＥＳ」であった場合、つまり、バックアップ隣接ノードが利用可能な場合は、ステップ４０８で、パケットはバックアップ隣接ノードｂｖ（ｔ）に転送され、この方法は次にステップ４０９で終了する。ステップ４０４での問いが「ＹＥＳ」である場合、つまり、プライマリ隣接ノードが利用可能な場合は、ステップ４１０で、パケットはプライマリ隣接ノードｐｖ（ｔ）に転送され、この方法は次にステップ４１１で終了する。
【００６８】
ステップ４０３での問いが「ＹＥＳ」であった場合、つまり、パケットが実際に隣接ノードｐｖ（ｔ）から到着したものであった場合は、ステップ４１２で、隣接ノードｂｖ（ｔ）が利用可能かどうか問われる。答えが「ＮＯ」の場合は、ステップ４１３でパケットは破棄され、この方法はステップ４１４で終了する。ステップ４１２での問いが「ＹＥＳ」であった場合、つまり隣接ノードｂｖ（ｔ）が利用可能な場合は、ステップ４１５で、パケットは隣接ノードｂｖ（ｔ）に転送され、この方法はステップ４１６で終了する。
【００６９】
もう１つの例として、図２Ｂに示すネットワークを考え、ノード２２８が故障したと仮定する。本発明の実施形態において、ノード２２６で、ノード２３２に宛てられたパケットは、ノード２２４に転送され、次にノード２２１に転送され、その次にノード２２２に転送されることになる。
【００７０】
しかし、ノード２２１はノード２２２のプライマリ隣接ノードではないので、パケットは次にノード２２５にルーティングされ、続いてノード２２７にルーティングされる。サイクルＣ２２７；２３２はＣ２２６；２３２より短いので、パケットの送信は「はかどっている」といえる。ノード２２７で、パケットは再びリルートされる必要があり、ノード２０５、２０２、および２１０を通ってから、最終的にノード２１２に到達する。
【００７１】
上記の例では、リルートされたパケットは各ノードを最大で２回訪れることに留意してよい。この特性は、本発明の実施形態には概してあてはまる。
【００７２】
さらに拡張された実施形態
Ａ．宛先ノードの故障および複数の故障
前述した本発明の実施形態では、失われたリンクおよびノードを補償することはできるが、故障したノードに宛てられたパケットは、明らかに配送が不可能なので、これらはパケット配送には含まれない。しかし、このようなパケットはネットワーク内に残って転送ループに入ることがあり、これによって、これらのループ上にあるリンクおよびノードのトラフィック負荷が不必要に増大する。例えば、図１Ａのネットワークでノード１１０が故障した場合、ノード１１０に宛てられたパケットは、結局、ノード１０１；１０３；１０５；１０７；１０８の経路上で行ったり来たりすることになる。理想的には、これらのパケットは、できる限りすみやかに破棄されるべきである。
【００７３】
ネットワーク内で同時に複数の故障が発生した場合、特に、ある故障に起因してリルートされたパケットが、それらの代替経路上で別の故障に遭遇した場合にも、類似した問題が発生することがある。宛先ｔに向かう代替経路はどれも、シンクツリーＴ（ｔ）の中にないリンクを少なくとも１つ含まなければならず、このようなリンクの最初のものを
【００７４】
【数３】
2014534776.tif 000005
とする。代替パス内で、
【００７５】
【数４】
2014534776.tif 000006
より前で故障が発生した場合は、これらのパケットは破棄されることになり（前述した、パケットのルーティングの擬似コードの４行目を参照）、それ以外の場合は、転送ループに入る。
【００７６】
上記のシナリオでは、本発明の実施形態に対する以下の修正によって、ループを予防することができる。すべてのノードｖおよび各宛先ｔについて、ｔについてのｖのＦＩＢエントリには、すでにポインタｐｖ（ｔ）およびｂｖ（ｔ）が含まれているが、ここに、２つのブールフラグｆｖ（ｔ）およびｑｖ（ｔ）が追加される。フラグｆｖ（ｔ）は、ｖがｖからｔまでの最短経路上で故障を検出済みであるかどうかを示し、ｑｖ（ｔ）は、リンク（ｖ；ｂｖ（ｔ））がシンクツリーＴ（ｔ）に所属しているかどうかを示す。さらに、第１の態様による一連のステップは、このステップがＴ（ｔ）およびｂｖ（ｔ）を計算した後にｑｖ（ｔ）を適切な値に設定し、かつｆｖ（ｔ）をＦＡＬＳＥに設定するよう修正される。最後に重要なこととして、第１のルーティング方法は下記のルーティング方法に置き換えられ、その方法は、故障に起因して、ノードｖが、ノードｔに宛てられたパケットをリルートしなければならない場合は、ｆｖ（ｔ）をＴＲＵＥに設定する。
【００７７】
故障が検出済み（つまり、ｆｖ（ｔ）がＴＲＵＥ）で、かつ（ｖ；ｂｖ（ｔ））∈Ｔ（ｔ）（つまり、ｑｖ（ｔ）がＦＡＬＳＥ）のときに、ｔに宛てられたパケットがｂｖ（ｔ）から到着すると、この方法は、ｔへの代替経路上で別の故障が発生したことを認識し、ループが作成されることを防ぐために、パケットを破棄する。このようにして、この実施形態では、複数の故障が存在する場合でも、円滑に、過渡的なルーティングループを防ぐことができる。
【００７８】
Ｂ．非対称のリンク重み
ときに、双方向リンクでは、各方向でルーティングの重みが異なることがある。このような場合、ネットワークは、無向グラフではなく有向グラフによって、それぞれの双方向リンクが、異なる重みをもつ逆平行に向けられた２つのエッジによって表現されるように、より適切にモデリングされる。
【００７９】
さらに、
【００８０】
【数５】
2014534776.tif 000007
は、あるエッジｅ∈Ｅの逆平行エッジを示すとする。本発明の実施形態は、ＦＩＢ表の作成方法を表現する擬似コードのステップ２での一時的重みの定義を下記のとおり修正することにより、そのようなネットワークで機能するよう適応させることができる：
【００８１】
【数６】
2014534776.tif 000008
【００８２】
【数７】
2014534776.tif 000009
であることに留意されたい。すでに述べたように、この割り当てでは、Ｔ（ｔ）との重なりがより大きいサイクルを優先して決定を行い（ｂｒｅａｋｓ−ｔｉｅｓ）、Ｔ（ｔ）そのものには影響しない。したがって、安定状態においては、このようなネットワークでも、パケットは宛先への最短経路上を転送される。
【００８３】
Ｃ．非２重連結ネットワーク
ここまでは、ネットワークは２重結合されていると仮定してきた。それ以外の場合は、ネットワークには必ず切れたノードまたは切れたリンクが含まれている。したがって、これらのいずれかが故障すると、他の経路が存在しないので、回復は不可能である。しかし、そのような場合においても、下記に示すように、他の構成要素故障からの確実な保護が可能である。
【００８４】
ネットワークに切れたノードがあるが切れたリンクはない場合は、まず、このネットワークは、例えば、深さ優先探索法などを使用して、２重連結された構成要素に分割される。次に、各構成要素について、個別にＦＩＢ表の作成方法が実行される。
【００８５】
最後に、次のようにして残りのＦＩＢエントリが書き込まれる。ノードｖおよび宛先ノードｔが異なる構成要素の中にある場合は、ｖからｔまでの最短経路上の最初の切れたノード（たとえばｙ）を特定する。ノードｙは必ずノードｖと同じ構成要素に属していることに注目されたい。したがって、ノードｖのＦＩＢエントリの、宛先ｙについてのすべての値が、宛先ノードｔについてのノードｖのＦＩＢエントリにコピーされる。
【００８６】
Ｄ．ループフリーなＦＩＢ更新
収束時間中の過渡的転送ループの主な原因は、異なるネットワークノードにおいてネットワークトポロジの見え方が一貫していないことである。例えば、図６に示される、ノード６１１が故障した後のネットワークを考える。ノード６０６およびノード６０３は、すでにそれらのＦＩＢ表を更新して、図６Ａで実線の矢印で示される、ノード６１２の新しいシンクツリーを反映しているが、ノード６０１および６０４は、まだ更新を行っていないと仮定する。このような状況では、６０１から６１２に送られたパケットは、ノード６０１；６０４；６０６および６０３から成る過渡的転送ループに入る。
【００８７】
本発明の代替実施形態によれば、このＦＩＢ更新方法により、すべてのルータｖは、ｔの新しいシンクツリー内でｖの先祖であるすべてのルータから後の宛先ｔについてのＦＩＢ表エントリを確実に更新する。これは、新しいシンクツリー内でのｖの深さ（つまり、ｔからのホップカウント距離）に従ってこの更新をスケジューリングすることにより達成される。
【００８８】
例として、時刻τにノードｖがＬＳＡメッセージを受け取り、このメッセージをその隣接ノード（複数）に転送し、また、これを使用して各宛先ｔの新しいシンクツリーＴ’（ｔ）を計算すると仮定する。Ｔ’（ｔ）内で、ｔへの経路がトポロジ変化に影響されないｖの最も近い先祖をｕとし、Ｔ’（ｔ）内でのｖからｕへのホップカウント距離を、ｄ（ｖ；ｕ）で表すものとする。すると、ｖは、時刻τ＋Δｄ（ｖ；ｕ）にｔについてのＦＩＢ表のエントリを更新するはずである。ここで、ΔはＬＳＡメッセージのリンク上の最長伝播時間であり、新しいシンクツリーを計算するのに必要な時間を含む。
【００８９】
さらに具体的な例として、図６Ａに示す、ノード６１１が故障した後のネットワークを考え、Δ＝１と仮定する。各ノードの隣の数字は、Ｔ’（ｔ）内で影響を受けない最も近いノード（ここではノード６１０）へのホップカウント距離である。ノード６０９が時刻０に故障を検出すると、ノード６０９は直ちにＬＳＡメッセージをノード６０６および６０７に送信し、ノード６０６および６０７はそれぞれの隣接ノードにこのメッセージを転送し、以降同様である。したがって、ノード６０２は時刻Δ＝３に故障を通知され、時刻τ＋Δｄ（６０２；６０１）＝３＋１＝４に、ｔについてのＦＩＢエントリを更新する。
【００９０】
同様に、ノード６０１；６０４；６０６および６０３はすべて、時刻５に、ｔについてのＦＩＢエントリを更新する。他も同様である。
【００９１】
シミュレーション結果
ネットワークインスタンス
本発明の実施形態をサービスプロバイダネットワーク上に配備することの適性を評価するために、下記の参考文献に公開されている多数の現実的なトポロジにおいてシミュレーションを実施した：
ＡＰＮネットワークインスタンス：Ｋ．Ｔｓｅ、「ＡＴ＆Ｔｓ  ｐｈｏｔｏｎｉｃ  ｎｅｔｗｏｒｋ」、ＯＦＣ／ＮＦＯＥＣ  ２００８、２００８年３月
ＩＴＡＬＹネットワークインスタンス：Ｋ．Ｗａｎｇ、Ｍ．ＡｌｉおよびＪ．Ｄｅｏｇｕｎ、「Ｍｕｌｔｉｃａｓｔ  ｒｏｕｔｉｎｇ  ｉｎ  ４０  Ｇｂ／ｓ  ｈｅｔｅｒｏｇｅｎｅｏｕｓ  ｏｐｔｉｃａｌ  ｎｅｔｗｏｒｋｓ」、ＩＥＥＥ  ＩＣＣ、第３巻、１６２０−１６２４頁、２００５年５月
ＴＯＲＯＮＴＯ、ＵＳＬＤおよびＮＪＬＡＴＡネットワークインスタンス：Ｙ．ＸｉｏｎｇおよびＬ．Ｍａｓｏｎ、「Ｒｅｓｔｏｒａｔｉｏｎ  ｓｔｒａｔｅｇｉｅｓ  ａｎｄ  ｓｐａｒｅ  ｃａｐａｃｉｔｙ  ｒｅｑｕｉｒｅｍｅｎｔｓ  ｉｎ  ｓｅｌｆ−ｈｅａｌｉｎｇ  ＡＴＭ  ｎｅｔｗｏｒｋｓ」、ＩＥＥＥ／ＡＣＭ  Ｔｒａｎｓ．Ｎｅｔｗ．、７（１）：９８−１１０頁、１９９９年
ＭＡＮネットワークインスタンス：Ｅ．Ｂ．Ｂａｓｃｈ、Ｒ．Ｅｇｏｒｏｖ、Ｓ．ＧｒｉｎｇｅｒｉおよびＳ．Ｅｌｂｙ、「Ａｒｃｈｉｔｅｃｔｕｒａｌ  ｔｒａｄｅｏｆｆｓ  ｆｏｒ  ｒｅｃｏｎｆｉｇｕｒａｂｌｅ  ｄｅｎｓｅ  ｗａｖｅｌｅｎｇｔｈ−ｄｉｖｉｓｉｏｎ  ｍｕｌｔｉｐｌｅｘｉｎｇ  ｓｙｓｔｅｍｓ」、ＩＥＥＥ  Ｓｅｌｅｃｔｅｄ  Ｔｏｐｉｃｓ  ｉｎ  Ｑｕａｎｔｕｍ  Ｅｌｅｃｔｒｏｎｉｃｓ、１２（４）：６１５−６２６頁、２００６年
ＡＳ３６９７ネットワークインスタンス：「Ｒｏｃｋｅｔｆｕｅｌ：  Ａｎ  ＩＳＰ  ｔｏｐｏｌｏｇｙ  ｍａｐｐｉｎｇ  ｅｎｇｉｎｅ」、ｈｔｔｐ：／／ｗｗｗ．ｃｓ．ｗａｓｈｉｎｇｔｏｎ．ｅｄｕ／ｒｅｓｅａｒｃｈ／ｎｅｔｗｏｒｋｉｎｇ／ｒｏｃｋｅｔｆｕｅｌ／にて入手可能
シミュレーション対象のトポロジのサイズは、１１ノード、２３エッジ（ＮＪＬＡＴＡ）から、１４８ノード、３７０エッジ（ＡＳ  ３９６７）までの範囲であり、それらの平均ノード次数を表１に記載する。
【００９２】
【表１】
2014534776.tif 000010
【００９３】
評価対象の方式：
ＤｉｓＰａｔｈの性能を、類似した特性、特に、（ａ）ＩＰパケットが変更されない、（ｂ）安定状態では、パケットは宛先までの最短経路にルーティングされる、（ｃ）どのルータも、１つの宛先について維持するポインタは、プライマリおよびバックアップの隣接ノードへの２つのみである、という特性をもつ方式と比較した。文献に提案されているさまざまなソリューションの中で、ＬＦＡおよびＵターンのみが上記の基準すべてに適合した。これらの方式はＤｉｓＰａｔｈと同様に、複雑度が低く、業界で広く考慮対象となっている。実際、これらの方式は、Ｍ．Ｇｊｏｋａ、Ｖ．ＲａｍおよびＸ．Ｙａｎｇ、ＩＥＥＥ  ＣＯＭＳＷＡＲＥ議事録、２００７年、「Ｅｖａｌｕａｔｉｏｎ  ｏｆ  ＩＰ  ｆａｓｔ  ｒｅｒｏｕｔｅ  ｐｒｏｐｏｓａｌｓ」ならびに、Ｍ．Ｇｏｙａｌ、Ｍ．Ｓｏｐｅｒｉ、Ｅ．Ｂａｃｃｅｌｌｉ、Ｇ．Ｃｈｏｕｄｈｕｒｙ、Ａ．Ｓｈａｉｋｈ、Ｈ．ＨｏｓｓｅｉｎｉおよびＫ．Ｔｒｉｖｅｄｉ、ＩＥＥＥ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  Ｓｕｒｖｅｙｓ  ａｎｄ  Ｔｕｔｏｒｉａｌｓ、２０１１年、「Ｉｍｐｒｏｖｉｎｇ  ｃｏｎｖｅｒｇｅｎｃｅ  ｓｐｅｅｄ  ａｎｄ  ｓｃａｌａｂｉｌｉｔｙ  ｉｎ  ＯＳＰＦ：Ａ  ｓｕｒｖｅｙ」などの論文に記載されているとおり、他のＩＰ  ＦＲＲ方式の性能を評価するためのベンチマークとして一般的に使用されている。
【００９４】
性能測定基準：
評価対象の方式の性能を、２つの性能基準に関して比較した：
保護範囲：リンク故障からの保護範囲とは、あらゆる単一のリンク故障から保護される発信元−宛先ペアのパーセンテージであり、ノード故障からの保護範囲とは、宛先の故障を除く、あらゆる単一のノード故障から保護されるペアのパーセンテージである。他の評価対象方式と異なり、ＤｉｓＰａｔｈでは、リンクおよびノードの両方の故障に対して、１００％の保護範囲が得られることを想起されたい。
【００９５】
ストレッチ：ある発信元−宛先ペアおよび、その最短経路上で故障した構成要素を前提として、ストレッチとは、代替経路の長さと、故障したネットワーク要素を除く最短の発信元−宛先経路の長さとの比率である。
【００９６】
各ネットワークインスタンスについて、すべての発信元−宛先経路上の平均ストレッチおよび最大ストレッチの両方を、すべてのリンク故障およびすべてのノード故障について別々に記録した。
【００９７】
評価結果：
シミュレーション結果を表１および表２に示す。表１では、ＤｉｓＰａｔｈの平均ストレッチは、複数のテストインスタンスの中で、許容できる程度に低い値のままであることが示唆される。
【００９８】
【表２】
2014534776.tif 000011
【００９９】
表２は、比較テストの結果を示す。ＬＦＡ（およびＵターンのそれぞれ）の平均および最大ストレッチは、その方式でループフリーな代替経路が提供される発信元−宛先ペアのみを考慮して計算されていることに留意されたい。これらの値は、比較対照できるよう、それらと同じペアについてのＤｉｓＰａｔｈの「相当する」平均および最大ストレッチに並べて記載されている。
【０１００】
明らかに、ほぼすべてのテストインスタンスにおいて、ＬＦＡとＵターンのどちらも、すべての故障からの保護は提供できない。ただし、Ｕターン方式では、ネットワークの平均ノード次数が低くない限りは、ほぼ満足な結果が得られることが多い。さらに、ＤｉｓＰａｔｈでは、常に１００％の保護範囲が保証されることに加え、ストレッチに関して、通常は他の２つの方式より性能で勝り、劣る場合でも、ごくわずかである。結果として、これらの実験結果は、ＤｉｓＰａｔｈがＬＦＡおよびＵターンのどちらよりも総合的に好ましいことの強力な証明になる。
【０１０１】
ゆえに、ここまでに開示されたものは、２重連結グラフとしてモデリングされたネットワーク内のあらゆる単一のリンク故障またはノード故障について全範囲の保護を提供する、新規なＩＰ高速リルート方式である。
【０１０２】
文献に述べられているいくつかの方式とは異なり、本発明の実施形態では、ＩＰパケットフォーマットに一切の変更が必要ない。ＬＦＡに規定されるものと同じ転送表についての基本要件および、Ｕターンに採用されるものと同一の簡明な故障検出方法によって、本発明の実施形態では、単一のリンク故障またはノード故障に対する１００％の保護範囲が提供される。ここまでに実施形態の重要な特性をいくつか示し、また、いくつかの現実的なネットワークインスタンスを使用したシミュレーション結果を通じて、本初面の実施形態がストレッチに関しても高い競争力をもつことも示した。
【０１０３】
簡潔性、単一のリンクならびにノード故障に対する全範囲の保護、および、魅力的なストレッチ率に支えられ、本発明の実施形態は、ＩＩＰ  ＦＲＲのための有望で実践的なソリューションとして強力な候補であると確信される。
【０１０４】
前述した論考において、当業者は、前述のさまざまな方法のステップが、適切に構成されたネットワークプロセッサにより実行可能であることを容易に認識できるであろうことに留意されたい。本明細書において、いくつかの実施形態ではまた、機械読み取りまたはコンピュータ読み取りが可能で、機械実行またはコンピュータ実行が可能な命令プログラムをエンコードし、当該の命令が前述の方法のステップの一部またはすべてを実行するプログラム記憶装置（例えばデジタルデータ記憶媒体など）を含めることも意図されている。このプログラム記憶装置はすべて、一時的でない有形の記憶媒体であり、例えばデジタルメモリ、磁気ディスクおよび磁気テープなどの磁気記憶媒体、ハードドライブ、または光学的に読み取り可能なデジタルデータ記憶媒体でもよい。これらの実施形態ではまた、前述の方法の前記ステップを実行するようプログラムされたネットワーク要素プロセッサを対象範囲に含めることも意図されている。
【０１０５】
請求項に定義された本発明の要旨を逸脱しない範囲で、前述された本発明の実施形態に 、多数の修正、変更および適合を行うことができる。
【図１Ａ】
2014534776.tif 000012
【図１Ｂ】
2014534776.tif 000013
【図２Ａ】
2014534776.tif 000014
【図２Ｂ】
2014534776.tif 000015
【図３】
2014534776.tif 000016
【図４】
2014534776.tif 000017
【図５】
2014534776.tif 000018
【図６Ａ】
2014534776.tif 000019
【図６Ｂ】
2014534776.tif 000020
【国際調査報告】
2014534776.tif 000021
2014534776.tif 000022