(57)【要約】      （修正有）【課題】ネットワークが収束する時間を短縮するためのインターネット・ルーティング・パスを選択する方法および装置を提供する。【解決手段】次の利用可能なパスが、既存のパスより大幅に良好である場合に次の利用可能なパスを最良の利用可能なパスとして選択し、次の利用可能なパスが、既存のパスより大幅に良好でない場合に既存のパスを最良の利用可能なパスとして選択するので、新たなルーティング・パスは、既存の最良の利用可能なパスより大幅に良好である場合にだけ選択されるので、ネットワーク収束が大幅に短縮される。【選択図】図１
2006109450.tif 000002
【特許請求の範囲】
【請求項１】
インターネット・ルーティング・パスを選択するための方法であって、
パケットをルーティングするための次の利用可能なパスを既存のパスと比較するステップ、及び
前記次の利用可能なパスが、前記既存のパスより大幅に良好であるかどうかに基づき、前記次の利用可能なパスまたは前記既存のパスを最良の利用可能なパスとして選択するステップからなる方法。
【請求項２】
請求項１記載の方法であって、さらに、
前記次の利用可能なパスが、前記既存のパスより大幅に良好である場合、前記次の利用可能なパスを前記最良の利用可能なパスとして選択するステップからなる方法。
【請求項３】
請求項１記載の方法であって、さらに、
前記次の利用可能なパスが、前記既存のパスより大幅に良好ではない場合、前記既存のパスを前記最良の利用可能なパスとして選択するステップからなる方法。
【請求項４】
請求項１記載の方法であって、さらに、
前記既存のパスが、前記次の利用可能なパスを通知した近隣のノードを通るかどうかを判定するステップ、及び
前記既存のパスが、前記次の利用可能なパスを通知した近隣のノードを通ると判定された場合、前記次の利用可能なパスが、すべての既知のパスのなかで最良のパスであるという条件で、前記次の利用可能なパスを選択するステップからなる方法。
【請求項５】
請求項１記載の方法であって、さらに、
前記次の利用可能なパスが、前記最良の利用可能なパスとして選択された場合にだけ、新たなパスを通知するステップからなる方法。
【請求項６】
請求項１記載の方法であって、さらに、
前記次の利用可能なパスは、少なくとも費用、長さ、チャネル品質、および誤り率から成るグループから選択された、前記次の利用可能なパスに関連するメトリックを閾値と比較することにより、前記既存のパスより大幅に良好であると判定される方法。
【請求項７】
インターネット・ルーティング・パスを選択するための装置であって、
パケットをルーティングするための次の利用可能なパスを既存のパスと比較し、前記次の利用可能なパスが、前記既存のパスより大幅に良好であるかどうかに基づき、前記次の利用可能なパスまたは前記既存のパスを最良の利用可能なパスとして選択するように動作可能な装置。
【請求項８】
請求項７記載の装置であって、さらに、
前記既存のパスが、前記次の利用可能なパスを通知した近隣のノードを通るかどうかを判定し、前記既存のパスが、前記次の利用可能なパスを通知した近隣のノードを通ると判定された場合、前記次の利用可能なパスが、すべての既知のパスのなかで最良のパスであるという条件で、前記次の利用可能なパスを選択するように動作可能な装置。
【請求項９】
請求項７記載の装置において、
前記装置は、ボーダー・ゲートウェイ・プロトコル（ＢＧＰ）ルータからなる装置。
【請求項１０】
請求項７記載の装置であって、さらに、
前記次の利用可能なパスが、前記最良の利用可能なパスとして選択された場合にだけ、新たなパスを通知するように動作可能な装置。
【発明の詳細な説明】
【背景技術】
【０００１】
ルータとして知られている装置は、インターネット内の１つのロケーション、または１つのノードから別のロケーション、または別のノードに情報をルーティングする最良のパス、または最良のパス群を選択することを担う。例えば、情報が、１つのネットワーク内のノードから異なるネットワーク内のノードに送信される必要がある場合、ボーダー・ゲートウェイ・プロトコル（「ＢＧＰ」）を使用するルータ（以降、「ＢＧＰルータ」）に、最良のパス、または最良のパス群を特定するタスクが割り当てられる。
【０００２】
インターネットを構成するネットワークに対して、新たなノードの追加、削除などが常に行われているため、任意の所与の時点で、１つのノードから別のノードへの最良のパスは、非常に急速に変化する可能性がある。これを理解して、既存の技術は、既存の最良の利用可能なパスを、所与のネットワークに変化が生じた場合に形成される、次の利用可能なパスと比較する能力をＢＧＰルータ（ときとして、ＢＧＰスピーカ・ノードと呼ばれる）に提供する。次の利用可能なパスが、既存の最良の利用可能なパスより良好であると判定された場合、次の利用可能なパスに、「最良の利用可能なパス」のステータスが与えられる。その後、この新たなパスが、既存のパス（すなわち、古い最良の利用可能なパス）の代りに、情報をルーティングするのに使用される。
【０００３】
新たなパスが選択された場合、ＢＧＰルータが、その新たなパスに関連する転送テーブルを生成することを担う。生成されると、転送テーブルは、ＢＧＰルータ内部に格納される。パケットが、ＢＧＰルータに着信すると、パケットは、格納された転送テーブルを使用して転送される。
【０００４】
ＢＧＰルータは、既存の格納された最良の利用可能なパスを次の利用可能なパスと常に比較している。次の利用可能なパスが、既存の最良の利用可能なパスよりほんのわずかでさえ良好な場合、既存の技術は、ＢＧＰルータが、新たなパスで既存の最良の利用可能なパスを置き換えることを要求する。このため、所与のＢＧＰルータは、自らの転送テーブルを常に更新することが可能である。さらに問題を複雑にすることに、新たな最良の利用可能なパスが特定されると毎回、そのパスが、近隣のノード群（例えば、近隣のＢＧＰルータ群）に伝送（「通知」と呼ばれる）されなければならない。新たな最良の利用可能なパスを受け取ると、近隣のノード群は、自らの転送テーブルを更新することも行う。その後、これらの近隣のノード群は、自らの近隣のノード群に通知し、以下同様である。このため、１つのＢＧＰルータによるいずれの変更も、他のＢＧＰルータ群に対するカスケード効果を有する。
【０００５】
この比較、選択、通知、および更新のプロセスに付き物であるのが、時間要件である。つまり、相対的に言って、比較、選択、通知、および更新のプロセスには、相当な時間がかかる。この時間中、プロセスが完了するまで、受信されたパケットを次のノードに転送することが可能でない可能性がある。例えば、パス上のいくつかのノードにおいて、比較、選択、更新、および通知のプロセスが完了していても、このプロセスが、他のノード群において完了していない可能性がある。その結果、そのパスに沿ってパケットを転送しようとするいずれの試みも、パス上のノードのそれぞれが、そのノードの比較、選択、更新、および通知のプロセスを完了するまで、不成功である（すなわち、パケットが、宛先に到達しない）可能性がある。
【０００６】
他の場合には、パケットが、後続のノードに転送される代りに、先行するノードに向けて送り返されることをもたらす、「ループ」と呼ばれる現象が生じる。
【０００７】
ネットワーク内の各ノードが、そのノードの比較、選択、および更新（および関連する通知）のプロセスを完了して初めて、任意の所定のパスを介してパケットが正常に転送されることが可能であることが、保証されることが可能である。各ノードが、このプロセスを終了すると、ネットワークが、「収束」したという言い方がされる。これには、相対的に言って、相当な時間がかかる可能性がある。ネットワークが収束するのが迅速であるほど、パケットが迅速に転送されることが可能である。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
したがって、ネットワークが収束するのにかかる時間を短縮する方法および装置を提供することが望ましい。
【課題を解決するための手段】
【０００９】
ネットワークが収束するのにかかる時間は、ルーティング・パスを計算することに関連する遅延を短縮することにより、大幅に短縮できることを我々は認識した。本発明の一実施形態では、検出された次の利用可能なパスは、そのパスが、既存の最良の利用可能なパスより大幅に良好である場合にだけ、最良の利用可能なパスとして選択される。
【００１０】
一部の検出された次の利用可能なパスは、既存の最良の利用可能なパスより大幅に良好ではないため、検出されたパスの一部は、選択されない。パスが選択されない場合、ＢＧＰルータが、自らの転送テーブルを更新する必要は全くない。また、未選択のパスを近隣のノード群に通知する必要も全くない。これにより、ＢＧＰルータが、自らの転送テーブルを更新する必要がある回数が大幅に少なくなり、カスケードが少なくなり、ネットワークが収束するのにかかる時間が短縮されるものと、本発明者らは考える。
【発明を実施するための最良の形態】
【００１１】
次に、図１を参照すると、いくつかのルータＡ、Ｂ、Ｃ、Ｄ、Ｅ、およびＦが示されている。これらのルータは、ＢＧＰルータであることが可能である。ＢＧＰルータＡ〜Ｆのそれぞれが、転送テーブルを格納し、各テーブルは、最良の利用可能なルーティング・パスに関連している。例えば、何らかのより早期の時点で、ＢＧＰルータＢが、ＢＧＰルータＤに至るルートを比較し、ルートｉをＢＧＰルータＤへの最良の利用可能なパスとして選択しているものと想定されたい。その後、ＢＧＰルータＢは、着信パケットをＢＧＰルータＤにルーティングするために、ルートｉに関連する転送テーブルを格納するように動作可能であることが可能である。
【００１２】
次の時点で、次の利用可能なパスｉ”が検出されるものとさらに想定されたい。本発明の一実施形態では、ＢＧＰルータＢは、次の利用可能なパスｉ”を既存の最良の利用可能なパスｉと比較するように動作可能である。この比較により、次の利用可能なパスｉ”が、既存の最良の利用可能なパスｉより大幅に良好である（例えば、費用に関して、長さに関して、時間に関して、または別の形で比較的良好）という判定がもたらされた場合、ＢＧＰルータＢは、次の利用可能なパスｉ”を次の最良の利用可能なパスとして選択するようにさらに動作可能である。しかし、比較の結果により、次の利用可能なパスｉ”が、既存の最良の利用可能なパスｉより大幅に良好ではないと判定された場合、ＢＧＰルータＢは、既存の最良の利用可能なパスｉを最良の利用可能なパスとして保持するように動作可能である。
【００１３】
そのような比較は、次の利用可能なパスの長さおよび費用を既存の最良の利用可能なパスの費用または長さと比較し、次の利用可能なパスの長さ／費用が、既存の最良の利用可能なパスの長さ／費用より大幅に短い／少ない場合にだけ、次の利用可能なパスを選択するという形態をとることが可能である。代替として、１つまたは複数の既知のメトリックまたは重みを、既存の最良の利用可能なパス、および検出された次の利用可能なパスに割り当てることもできる。メトリックまたは重みが比較されると、次の利用可能なパスは、メトリックまたは重みが、既存の最良の利用可能なパスに関連するメトリックまたは重みより大幅に良好である場合にだけ、選択される。本発明のさらなる実施形態では、次の利用可能なパスに関連するメトリックまたは重みが、閾値などと比較されることが可能である。メトリックまたは重みが、閾値（次の利用可能なパスが既存の最良の利用可能なパスより大幅に良好であるというインジケータとして作用する）に等しいか、閾値を超えている場合にだけ、次の利用可能なパスが選択される。メトリックまたは重みは、長さ、費用、伝送チャネル品質、誤り率などに関連することが可能であることを理解されたい。以上は、検出された次の利用可能なパスが、既存の最良の利用可能なパスより大幅に良好であるかどうかを判定するのに使用することができる、メトリックおよび重みのいくつかに過ぎないことを理解されたい。
【００１４】
例えば、次の利用可能なパスは、所与のＢＧＰルータを運用するエンティティと提携していないエンティティによって運用されるネットワークを通るため、より高い費用に関連することが可能である。これに対して、既存の最良の利用可能なパスに関連する費用は、検出された次の利用可能なパスに関連する費用より低いことが可能である。というのは、既存の最良の利用可能なパスは、ＢＧＰルータの関連会社によって運用されるネットワークを通るからである。
【００１５】
次の利用可能なパスが、既存の最良の利用可能なパスより大幅に良好であることを要求することにより、本発明は、次の利用可能なパスが、既存の最良の利用可能なパスより大幅に良好である場合にだけ、ＢＧＰルータ群が、新たな転送テーブルを生成することを可能にする。多くの場合、次の利用可能なパスは、既存の最良の利用可能なパスより大幅に良好ではないため、本発明は、所与のＢＧＰルータが、新たな転送テーブルを生成しなければならない回数を効果的に減少させる。
【００１６】
さらに、ＢＧＰルータが、新たな最良の利用可能なパス群を近隣のノード群に通知する、または伝送するだけでよいため、これらの通知または伝送は、次の利用可能なパスが、既存の最良の利用可能なパスより大幅に良好である場合に、行われるだけでよい。上記の例では、次の利用可能なパスｉ”が検出されているものの、パスｉ”は、パスｉより大幅に良好ではない可能性がある。本発明のさらなる実施形態では、ＢＧＰルータＢは、次の利用可能なパスｉ”を選択しない。というのは、パスｉ”は、既存の最良の利用可能なパスｉより大幅に良好ではないからである。その結果、ＢＧＰルータＢは、自らの転送テーブルを更新する必要がなく、新たなパスを自らの近隣のノード群に通知する必要もない。その結果、近隣のルータＡ、Ｃ、Ｅ、およびＦも、自らのルーティング・パス、および関連する転送テーブルを変更する必要がない。反対に、ｉ”がパスｉより大幅に良好であるとＢＧＰルータＢが判定した場合、ＢＧＰルータＡ、Ｃ、Ｅ、およびＦは、自らの既存の最良の利用可能なパスを次の利用可能なパスｉ”に変更しなければならない可能性があり（ＢＧＰルータＡ、Ｃ、Ｅ、およびＦも、ｉまたはｉ”より大幅に良好な他のパスを全く知らないものと想定して）、自らの転送テーブルも変更しなければならない可能性がある。その後、ＢＧＰルータＡ、Ｃ、Ｅ、およびＦは、この新たなパスを自らの周囲のＢＧＰルータ群（図１に示さず）に通知することも行わなければならない。
【００１７】
次の利用可能なパスが、既存の最良の利用可能なパスよりわずかだけ良好な場合に、そのようなカスケード効果を回避するため、そのような次の利用可能なパスは、パケットをルーティングするのに選択されないか、または使用されない。転送テーブルを変更することに関連する遅延、およびカスケード効果が小さくされて、ネットワークが収束するのにかかる時間が短縮される。迅速に収束するネットワークにより、受信されたパケットを、以前に可能であると考えられたよりも迅速に転送することが可能である。
【００１８】
少し元に戻ると、メトリックまたは重みを既存の利用可能なパス、および次の利用可能なパスに割り当てることができることを前述した。これらのメトリックおよび重みは、ＢＧＰルータにおいてユーザ、ネットワーク事業者などによって割り当てられる、変更される、または構成される（まとめて、「構成される」）ことが可能であることを理解されたい（すなわち、メトリックおよび重みは、可変であり、固定ではない）。
【００１９】
本発明のさらに追加の諸実施形態では、いわゆる「ループ」に関連する諸問題が、本発明によって防止される。ＢＧＰルータＢは、次の利用可能なパスを新たな最良の利用可能なパスとして最初に選択すると、次の利用可能なパスにより、パケットが、ＢＧＰルータＢ、あるいは、その次の利用可能なパス上の他のいずれかのルータに送り返される（すなわち、ループして戻される）ことがもたらされるかどうかを判定する。送り返されることが生じる可能性があるとＢＧＰルータＢが判定した場合、このパスは拒否され、新たな最良の利用可能なパスとして選択されない。
【００２０】
さらに、本発明は、例えば、次の利用可能なパスｉ”が、実際に、すべての既知のパスのなかで最良のパスであることを確実にする別の比較も可能にする。例えば、ｉ”は、ｉより大幅に良好である可能性があるものの、次の利用可能なパスｉ”が利用可能になるのと同時に、別のパス、例えば、パスｋに変更が生じる可能性がある。次の利用可能なパスｉ”が、既存の最良の利用可能なパスｉより大幅に良好であるだけでなく、すべての既知のパス（パスｋが、ＢＧＰルータＢにあらかじめ知られているものと想定される場合の）のなかで最良のパスでもあることを確実にするため、次の利用可能なパスｉ”は、すべての既知のパスのなかで、実際の最良のパスである、このケースでは、パスｉ、パスｉ”、およびパスｋのなかで最良のパスであるという条件でだけ選択される。この条件は、図１に示された各ＢＧＰルータに関して成立する。
【００２１】
本発明のさらなる実施形態では、ＢＧＰルータＢが、次の利用可能なパス（例えば、ｉ”）を選択し、この新たなパスを自らの周囲の近隣ノード群に通知すると、既存の最良の利用可能なパスｉは、ＢＧＰルータＡ、その他によって、もはや使用されることが可能でないことを理解されたい。つまり、ＢＧＰルータＡは、既存の最良の利用可能なパスｉが、次の利用可能なパス（例えば、ｉ”）を通知した近隣のノード（例えば、ＢＧＰルータＢ）を通るかどうかを判定するようにさらに動作可能であることが可能である。そのような近隣のノードを通る場合、ＢＧＰルータＡは、次の利用可能なパスｉ”を選択するようにさらに動作可能である（もちろん、その次の利用可能なパスｉ”が、すべての既知のパスｉおよびｋのなかで最良のパスであると判定されているという条件で）。
【００２２】
本発明のさらなる実施形態では、本発明の各ＢＧＰルータは、異なるメトリックまたは重みをそれぞれの最良の利用可能なパスに割り当てることができる。これが理由で、各ＢＧＰルータが、独自の比較プロセスを実行した場合、各ＢＧＰルータは、異なる比較結果を生成することが可能である。
【００２３】
以上の説明は、本発明の実施例のいくつかを提示した。ただし、本発明の真の範囲は、添付の特許請求の範囲に記載する。
【図面の簡単な説明】
【００２４】
【図１】本発明の諸実施形態に従ってインターネット・ルーティング・パスを計算するように動作可能な、ＢＧＰルータ群などのノード群を示す図である。
【図１】
2006109450.tif 000003