(57)【要約】本発明は、ルータを有するパケット指向のネットワークにおけるラベル・スイッチ・パス、殊にＭＰＬＳパスを適応させる装置及び方法に関する。ルータの少なくとも一部は隣接するルータとネットワークの状態、殊に負荷変動、アベイラビリティの変化及び帯域幅に関する情報をプロトコルを介して交換して起こりうるボトルネック及び改善を識別し、ボトルネックが隣接する場合にはこのボトルネックを介して案内される経路を部分代替経路を用いてこのボトルネックを迂回するように局所的に変更し、改善が隣接する場合にはこの改善を迂回する経路を経路内に改善が含まれるように変更する。
2005505198.tif 000002
【特許請求の範囲】
【請求項１】
ルータを有するパケット指向のネットワークにおけるラベル・スイッチ・パス、例えばＭＰＬＳパスを適応させる方法において、
ルータの少なくとも一部が、隣接するルータとプロトコルによってネットワークの状態、例えば負荷の変動、アベイラビリティの変化及び帯域幅に関する情報を交換し、起こりうるボトルネックまたは改善を識別し、
ボトルネックが隣接する場合には、該ボトルネックを介して案内される経路を、部分代替経路を用いて該ボトルネックを迂回するよう局所的に変更し、及び／又は、
改善が隣接する場合には、該改善を迂回する経路を、該改善が経路内に包含されるよう局所的に変更することを特徴とする、ラベル・スイッチ・パスを適応させる方法。
【請求項２】
隣接するルータの集合をマニュアルで対応付ける、または所定の距離をおいて配置し、該距離に関してメトリックを規定する、請求項１記載の方法。
【請求項３】
情報交換をルータにおいて規則的なデータトラフィックにおけるピギーパックとして実施するか、別個のコネクションによって行う、請求項１または２または１及び２記載の方法。
【請求項４】
ＲＳＶＰ、ＬＤＰを処理する、請求項１から３までのいずれか１項または複数項記載の方法。
【請求項５】
ルータは該ルータが管理する各経路に、該経路内に存在する隣接するルータを対応付け、所定のルータまたはルータから出発する隣接するネットワークセグメントが性能推移を示す場合には経路を適応させる、請求項１から４までのいずれか１項または複数項記載の方法。
【請求項６】
隣接するルータまたは隣接するネットワークセグメントの性能の劣化に関して、部分代替経路を既存の経路に統合することにより該ルータないし該ネットワークセグメントを迂回するよう構成されている用意された部分代替経路を管理し、
隣接するルータまたは隣接するネットワークセグメントの性能の改善に関して、部分代替経路を既存の経路に統合することにより前記ルータないし前記ネットワークセグメントが経路内に存在するよう構成されている用意された部分代替経路を管理する、請求項１から５までのいずれか１項または複数項記載の方法。
【請求項７】
隣接するルータまたはネットワークセグメントにおいて性能の推移が生じると、
隣接するルータまたは隣接するネットワークセグメントの性能が改善された場合には、該ルータまたは該ネットワークセグメントが部分代替経路の統合後に経路内に存在するよう部分代替経路を形成し、
隣接するルータまたは隣接するネットワークセグメントの性能が劣化した場合には、該ルータまたは該ネットワークセグメントが部分代替経路の統合後に経路外に存在するよう部分代替経路を形成する、請求項１から６までのいずれか１項または複数項記載の方法。
【請求項８】
前記部分代替経路をルートアルゴリズムに基づき計算し、該ルートアルゴリズムはルーティングテーブルにアクセスし、前記ルートアルゴリズムにはどのルータないしどのネットワークセグメントをルート選択の際に考慮できるか、ないし考慮できないかをパラメータとして引き渡す、請求項１から７までのいずれか１項または複数項記載の方法。
【請求項９】
前記経路を表すプロトコルとしてＭＰＬＳを使用し、前記部分代替経路をトンネル、明示的な経路の挿入、等価クラスの変更及び該変更に続く該等価クラスの伝播によって実現する、請求項１から８までのいずれか１項または複数項記載の方法。
【請求項１０】
パケット指向のネットワークにおけるラベル・スイッチ・パス、例えばＭＰＬＳ経路を制御する、例えばルータである装置において、
請求項１から９までのいずれか１項または複数項記載の方法を実現する、手段及び該手段の制御部が設けられていることを特徴とする、装置。
【請求項１１】
隣接するネットワークの状態、例えば負荷変動、アベイラビリティの変化及び帯域幅を検査する分析手段と、情報を交換するインタフェースとが設けられている、請求項１０記載の装置。
【請求項１２】
メモリ領域に他のルータ及び直近には隣接していないネットワークに関するネットワーク状態が記憶され、情報に基づき経過時間が改善される経路が検出される、請求項１０及び１１記載の装置。
【請求項１３】
経路及び記憶されたネットワーク状態を相互に比較する手段、例えばマイクロプロセッサが設けられており、
ネットワーク経路の変更によって関係している経路を算出し、
ボトルネックが隣接する場合には該ボトルネックを迂回する部分代替経路が算出されまたは発生され、改善が隣接する場合には該改善を介して案内される部分代替経路が算出されまたは発生され、
該算出された部分代替経路はルータ機能の適応により前記経路に統合される、請求項１０から１２までのいずれか１項または複数項記載の装置。
【請求項１４】
可能な限り短い部分代替経路を算出する選択手段が設けられている、請求項１０から１３までのいずれか１項または複数項記載の装置。
【請求項１５】
前記部分代替経路は、メモリ領域に格納されているルーティングテーブルの使用により算出されるか、隣接するルータにルーティング問合せを送信することにより算出され、前記経路の目的地として、データフロー方向において性能変化によって関係しているネットワークセグメントの直ぐ後ろに配置されている、ネットワークセグメントまたはルータが選択される、請求項１４記載の装置。
【請求項１６】
ルータの公知の要素は相応のプログラミングによってソフトウェアを用いて、本方法の機能が達成されるよう拡張される、請求項１０から１５までのいずれか１項または複数項記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
ＵＭＴＳ及びＧＰＲＳのようなパケット指向の技術が導入されることによって、将来におけるデータ伝送がますます無線で行われることが期待される。データ伝送は音声情報の伝送だけに限定されるのではなく、例えばインターネットにおいて提供される他のサービスもますます無線で使用される。端末装置における高められた帯域幅をさらに使用できるようにするために、情報の配布に使用されるコアネットワークも同様に確立する必要がある。例えばインターネットのような他のネットワークにおいても、帯域幅に対する需要が増し続けていることが認められる。帯域幅の大部分は情報のルーティングの際に失われる。このことは、パケットの転送に関係する決定の大部分が比較的高いプロトコルレベルにおいてなされることに起因する。通常このプロトコルレベルはＩＰレベルである。しかしながら最近ではラベル指向のルーティングないしスイッチングがますます使用されている。ここで文献においてルーティングとスイッチングは異なる表現として存在するが、以下ではこれらを区別しないことに言及しておく。ラベル指向のルーティングの利点は、決定に関して考慮すべき情報量が比較的少なく、この比較的少ない情報及び所定のクラスの使用に基づき比較的容易に決定を下せることである。
【０００２】
最も頻繁に使用される経路指向の方法のうちの１つにＭＰＬＳがある。
【０００３】
構造が簡潔でありまた性能が高いために、マルチプロトコル・ラベル・スイッチング（ＭＰＬＳ、ＩＥＴＦの提案する規格、［ＲＦＣ  ３０３１並びに他のＲＦＣ］）をトンネル技術としての利点と共に使用することができる。
【０００４】
ＭＰＬＳネットワークではパケットがあるルータから次のルータへと運ばれる。各ルータは転送に関する独自の決定を行う。すなわち、各ルータはパケットのヘッダを分析し、また各ルータはルータアルゴリズムを用いてプログラムを実行する。各ルータはルータアルゴリズムの結果に依存して新たなルータを選択する。つまり後続のルータの選択は２つのステップで行われる。第１のステップは考えられる全体のパケットを等価クラス（ＦＥＣ、Forwarding Equivalence Class）に分割する。等価クラスは通常、マスクによって求められるＩＰアドレスまたは所定のＩＰアドレスパターンから構成されている。第２のステップは各ＦＥＣをルートにマッピングする。何が転送の決定にかかわるかは、同一のＦＥＣに属するパケットには関係ない。同一のＦＥＣに属する種々のパケットは区別されない。
【０００５】
ＭＰＬＳネットワークにおいてはＦＥＣについての対応付けは一度だけ、すなわちパケットがＭＰＬＳネットワークに進入する時に行われる。パケットが対応付けられているＦＥＣは短い値として符号化されており、この短い値はラベルと称される。パケットが次のルータに転送されると、ラベルも一緒に送信される。後続のルータにおいてはパケットのさらなる内容の分析は行われない。単にラベルのみが検査される。ラベルはテーブルについてのインデクスとして使用され、このテーブルから次のルート及び次のラベルを得ることができる。古いラベルは新たなラベルに置換されて、パケットが次のルータへと転送される。ＭＰＬＳネットワークでは転送がラベルだけで制御される。このことは一連の利点を有する。つまりルータの性能は僅かなもので良い。ルータは古いラベルを新たなラベルに置換するために、ラベルを分析して、テーブルにおいてどのルートがこのラベルに対応付けられているかを検査することさえできればよい。さらにこの簡単なタスクによって高いスループットを実現することができる。さらなる利点はＲＦＣ  ３０３０１から得ることができる。
【０００６】
以下では幾つかの原則を説明する。ラベルは局所的に有意である短い識別子であり、ＦＥＣを識別するために固定の長さを有する。ラベルはパケットが対応付けられているＦＥＣを表すために使用される。ＦＥＣの基本的な使用ではＦＥＣはネットワーク層の目的アドレスに基づき対応付けられる。
【０００７】
ルータがパケットを同一の等価クラスに対応付けることを保証するために、ルータは規則的に、どのパケットがラベルに対応付けられるかを明らかにする情報を交換する必要がある。さらには同一でないラベルが異なるルータによって使用されることは重要であり、その限りではこれによって先行のルータの一義的な識別が不可能である。さらには、アップストリームとダウンストリームとでは異なる処理がされることを示唆しておく。このアップストリームとダウンストリームは必ずしも同一のラベルを有するわけではない。ＭＰＬＳアーキテクチャにおいて所定のラベルを所定の等価クラスに結合する決定は、この結合に関してダウンストリームであるルータによって行われる。ダウンストリームであるルータはアップストリームであるルータにこの結合に関する情報を付与する。この情報を他のパケットにおける例えばピギーバック（Huckepack）情報として伝送することができるか、専用の情報伝送によって伝送することができる［ＲＦＣ  ３０３１、３０３５、３０３６、３０３７、３０３８、２２０５−２２１０、２３７９、２３８０、２７４６、２７５０、２８１４、２７０２］。
【０００８】
別の実施形態においてはＭＰＬＳは階層を支援し、ここではラベルが設けられているパケットの処理は階層レベルから完全に独立している。ラベルを有さないパケットはスタックが空であるラベルとみなすことができる。スタックの使用はパケットのトンネルを言及する際に明らかにする。そのようなトンネルは文献ＲＦＣ  ３０３１から引用することができる。パケットが２つのルータ間のネットワーク経路を通過し案内される場合にはパケットは常にトンネリングされ、ここでこのネットワーク経路はやはり多数のルータを包含することができる。例えばルータＲ１からＲ４を包含する明示的な経路が予め設定されており、ルータＲ１とＲ２との間にルータＲ１．１、Ｒ１．２、Ｒ１．３を包含する経路が存在する場合には、別のラベルがルータＲ１によってスタックにプッシュされる。ルータＲ１．１、Ｒ１．２、Ｒ１．３はこの新たな第２の要素に基づき動作する。パケットがルータＲ２に到着するやいなや一番上の要素がスタックからポップされる。ラベルがスタックに無い場合には問題となる。通常のＭＰＬＳアーキテクチャでは等価クラスを検出するためにネットワークアドレス（通常の場合はＩＰアドレス）が分析される。
【０００９】
ＭＰＬＳは２種類のルート選択を提供する。ルート選択のうちの一方では出発点において既にルートが確定される。通過しなければならない個々のルータが決定される。ここでのルートは明示的なルートである。ホップ・バイ・ホップルートの場合ルータは明示的に確定されないので、各ルータはテーブルに基づきどのルータが次のルータであるべきかを確定する。本発明はこれら２つのルート選択の可能性を用いて動作することができる。
【００１０】
パケットをルーティングするために必要とされる情報量、すなわちヘッダを考慮するならば、経路指向のプロトコルでは大幅に削減できる可能性を持っていることは明らかである。ＩＰｖ６ヘッダでは、トランスポートデータ量が平均して６０バイト（ルーティングヘッダを包含するＩＰｖ６）の場合には４０バイト以上のヘッダオーバヘッドが惹起され、つまり有効データはやはり約２０バイト（ＶｏＩＰ）しか包含されていない［ＲＦＣ３０３１、ＲＦＣ２４６０］。シムヘッダないし例えばＭＰＬＳのＭＰＬＳヘッダを用いてその都度４バイトのみが誘導される。シムヘッダ、またＭＰＬＳヘッダは約２０バイトからなるラベルの他に別の状態情報及び管理情報を包含する。基本的には例えばサービスの品質（ＱｏＳ、Quality of Service）のような特性を用いるポイント・ツー・ポイントリンクの一義的な識別、また勿論それぞれのベアラの一義的な識別が必要である。
【００１１】
最長プレフィックス一致（Longest-Prefix-Match）よりも繁雑なレイヤ３ヘッダ評価の代わりにレイヤ２ラベル評価によってパケット転送を高速化する他に、パケット経路を明示的に設定することができ（ソースルーティング）、これによって全ての経路に対して同一の経路が強制される。これによって殊にＱｏＳの観点からのより多くの制御を達成することができる。
【００１２】
トンネルを使用することによって、プロバイダの場所的に分離された（またトランスポートネットワークによって接続された）部分ネットワーク間のレイヤ３ルーティング行程及びレイヤ３ルーティング決定を回避することができる。このアプローチはバーチャルプライベートネットワークが実現されるべき場合には常に重要である。
【００１３】
別のポイントはモバイルＩＰアーキテクチャにおける場所的に分離されたフォワーディングユニット間のレイヤ３ルーティング行程及びレイヤ３ルーティング決定を回避することである（「階層モバイルＩＰ」、インターネットにおけるwww.itef.orgの相応の草稿を参照されたい）。
【００１４】
前述の利点に基づき、ルーティングの簡略化として（例えばＭＰＬＳ、マルチプロトコル・ラベル・スイッチングを用いる）パケットネットワークにおけるラベル・スイッチ・パス（Label Switched Path）の使用はますます重要になっている。
【００１５】
しかしながらラベル・スイッチ・パスの使用は幾つかの欠点も有する。経路を最初に固定的に設定することによって、例えばＭＰＬＳは非動的で局所的に、負荷の変動、アベイラビリティの変化及びネットワーク要素の帯域幅のような時事的な展開に対して制限的にしか反応できない。
【００１６】
これらの事例に対する従来の解決手段は外部から継続的にネットワークを考察し、必要に応じて標準ＭＰＬＳシグナリングによって経路をその都度最初から最後まで新たに確立することである。この際完全な経路は、経路が変化した条件及び接続設定を考慮するように再編成される。しかしながらここで中央ユニットによって継続的にネットワーク全体、殊にルータ及びルータと接続されているネットワークセグメントが監視されなければならない。
【００１７】
この監視はサービスプロバイダのもとでの動作中の著しい手間を要求し、コストの主たる負担をなす。
【００１８】
本発明の課題は、ネットワークの最適な監視を実現する方法を提供することである。
【００１９】
本発明の課題は独立請求項に記載されている特徴を備えた方法及び装置によって解決される。別の構成は従属請求項に記載されている。
【００２０】
基本的なアプローチはラベル・スイッチ・ルーティングにおけるラベル・スイッチ・ルータ（ＬＳＲ）の限定的且つ自律的な決定を可能にすることである。
【００２１】
ラベル・スイッチ・ルータ（ＬＳＲ）は、例えばＬＤＰ［ＲＦＣ  ３０３１、３０３５、３０３７、３０３８」またはＲＳＶＰ［２２０５−２２１０、２３７９、２３８０、２４７６、２７５０、２８１４］のシグナリングプロトコルの拡張により、経路を自律的に他の隣接ノードに迂回させることができる。前述のプロトコルは標準プロトコルであって、このプロトコルを用いてネットワーク要素は管理情報を交換する。しかしながら標準化されていない他の考えられるプロトコルを使用することも可能である。通常はルータである個々のネットワーク要素はこのために直ぐ近くの周囲の（負荷及びアベイラビリティに関する）目下のルーティング状況を観察し、この状況を拡張されたシグナリングプロトコルにより経路を考慮して相互に補償調整し、必要に応じてラベル・スイッチ・パスを相応に局所的に適応させる。
【００２２】
ここでルータは有利には規則的な間隔で、殊に負荷の変動、アベイラビリティの変化及び帯域幅に関するネットワークのステータスを交換し、起こりうるボトルネックまたは改善状況を識別する。周期的で同期された交換を使用することによって、所定のルータが完全に損傷しているか否かも確認することができる。情報を交換することによって、ボトルネックが隣接する場合にはこのボトルネックを介して案内される経路を、部分代替経路を用いてボトルネックを迂回するように局所的に変更することができる。
【００２３】
この部分代替経路は、所定の要素またはセグメントの損傷に対処できるようにするために、既に前方の領域に設置されていた事前に用意された経路で良い。この経路の用意は特に繁雑なものではない。何故ならば監視される隣接のルータないしセグメントは僅かなものにすぎないからである。これらのルータないしセグメントに関してのみ部分代替経路が記憶されればよい。
【００２４】
さらには殊にＭＰＬＳ経路ではデータフロー方向においてのみ経路の操作が行われることを示唆しておく。したがって生じる管理すべきデータはむしろ僅かである。
【００２５】
択一的な実施形態においては、必要とされる部分代替経路を動的に発生させることもできる。この択一的な実施形態においては部分代替経路は有利には、ルーティングテーブルにアクセスするルートアルゴリズムを基礎として計算される。ここでルートアルゴリズムには、どのルータないしどのネットワークセグメントをルート選択の際に考慮できるか、ないし考慮できないかをパラメータとして引き渡すことができる。このアルゴリズムは殊にＩＰネットワークにおいて使用される公知の方法を基礎としている。
【００２６】
隣接するルータが所定のセグメントに問題が生じていることを通知すると、データフローにおいて手前にあるルータは、このネットワークセグメントを介して案内される経路を管理するか否かを検査する。そのような分析は通常、比較操作を用いて行われ、この際経路はこの問題のあるネットワークセグメントを介して案内されるか否かが検査される。
【００２７】
部分代替経路の動的な発見は変化の種類に依存している。例えば負荷状況が終了した時に生じる可能性のある改善が隣接する場合には、最初に負荷状況を迂回した経路を選択することができる。
【００２８】
考えられる実施形態においては、最初に迂回された経路がマーキングされ、負荷状況が改善されると、この経路は再び古いネットワークセグメントを介して案内される。このマーキングによって考えられる変化候補にアクセスすることがより簡単になる。ここでルーティングアルゴリズムは、必要に応じて改善されたネットワークセグメントを介して案内されるルートを選択できるように適応される。しかしながらここでは重み付けが行われ、その結果賢明にもこの改善されたネットワークセグメントを介さずに案内される経路は不必要に迂回されない。この重み付けは例えば前述のマーキングによって決定することができる。重み付けは所定の優先順位、または所定のＱｏＳ要求の優先順位でも良い。
【００２９】
特別な実施形態においてはデータフロー方向において改善されたネットワークセグメントの直ぐ後ろに案内される経路が選択されるが、この改善されたネットワークセグメントは経路の構成要素ではない。この場合には改善されたネットワークセグメントを介する経路を簡潔に迂回することによって、データトラフィックの高速化が達成される。
【００３０】
他の実施形態では単に、改善されたネットワークセグメントの前後にあるノードないしルータが選択され、どの経路がこれら２つのルータ／ノードを介して案内されるかが検査される。次いでこの経路に関してそのようにして求められた部分代替経路が統合される。
【００３１】
別の実施形態においては、改善されたネットワークセグメントの周囲に存在する別のルータ／ノードを考慮することができ、比較的長い距離で迂回される経路が求められる。この経路に関しても相応の部分代替経路を統合することができる。
【００３２】
これに対して伝送状況が劣化すると、相応に劣化したネットワークセグメントを介して案内される経路が検出され、可能な限り、データフロー方向において劣化したネットワークセグメントの後ろに配置されている目的地としての最初のノードないしルータを有するルートが動的に発見される。これに関してルートが発見されない場合には、データフロー方向において劣化したネットワークセグメントの後ろに存在する次の次のノードないしルータが選択される。これに対してこの方式により成果が得られない場合には、データフロー方向で見れば先にあるノードないしルータに同一の方法を適用することによって部分代替経路を発見することが試みられる。アルゴリズムは欠陥のあるネットワークセグメントが考慮されないように変更されている。直ぐ近くの周辺において成果が得られない場合には、ルートを発見するための方法は中断される。最適化された実施形態おいては既に、簡単な構造、殊にハッシュ構造によって隣接するルータにこれらのルータを介して走る経路が割り当てられている。
【００３３】
ここでは引用していない別の公知のアルゴリズムも同様に考えられる。
【００３４】
局所的な通信の集合（Kommunikationsmenge）に属するルータを検出するために、自動的な方法またはマニュアルの方法を使用することができる。どちらのアプローチにおいてもこれらの集合が部分的に重複することは勿論有効である。マニュアルでコンフィギュレーションする場合には、ネットワークの負荷状況に関する情報を交換すべき隣接するルータが管理者によって選択されて対応付けられる。自動的な対応付けの場合にはメトリックを使用し、このメトリックを用いて隣接するルータないしノードが検出される。閾値を設定することによって、この閾値によって検出される範囲の内部に存在するルータないしノードが選択される。つまりメトリック、例えば複数のノードを基準として考慮することができる。さらにネットワークセグメントの長さを計算に導入することができる。
【００３５】
情報を交換するために有利には公知のプロトコルが使用され、このプロトコルは情報を情報パケットに情報を背負わせて（huckepack）トランスポートするか、通常はＴＣＰ−ＩＰを基礎とする別個のコネクションを介してトランスポートする。これは通常ＲＳＶＰかＬＤＰである（相応のＲＦＣを参照されたい）。しかしながらこれらのプロトコルが直ぐ近くの周辺においてのみ適用されることは顧慮すべきである。したがって専用のアドレスによるノードないしルータの応答は有利である。
【００３６】
有利な実施形態においてはＭＰＬＳは経路を表すために使用される。ＭＰＬＳを用いることにより、部分代替経路を既存の経路に統合する種々の可能性が存在する。第１の実施形態においては部分代替経路がトンネルのために使用される。ＭＰＬＳにおけるトンネルはＭＰＬＳパケットのスタックに別のラベルが設けられることによって達成される。詳細な例は上述してある。別の実施形態においては明示的な経路がパケットに統合される。明示的な経路では個々のルータないしノードがリストに記載され、個々のルータがパケットの転送に関する決定を行う場合にはリストと結びつけられている。これに関しても詳細な実施形態は上述した。第３の択一形態においては等価クラスが変更されて、隣接するルータへとさらに送信される。通常の場合、ネットワークの限定的な領域にわたり拡がる一度だけの雪崩的なプロセスが生じる。この方法に関する詳細な説明は上述のＲＦＣに見出せる。
【００３７】
本発明の別の構成部分はパケット指向ネットワークにおけるラベル・スイッチ・パス、殊にＭＰＬＳパスを制御するための装置、殊にルータである。この装置は本発明による方法を実現する手段およびこの手段の制御部によって傑出している。装置は通常の場合、既にルータにおいて標準的に使用される公知の構成要素であるが、付加的なソフトウェアモジュールによって機能が拡張されている。
【００３８】
別の実施形態では記憶領域にアクセスできる付加的なプロセッサでも良く、ここでプロセッサはルータのポートを介するデータ交換を実現するためにインタフェースを介して入力／出力機器にアクセスすることができる。
【００３９】
さらには装置は分析手段を有し、この分析手段は有利には値を用いて統計的に表せるようにするためのセンサ、カウンタまたはタイマとして構成されている。分析手段が表す別の視点は、消失したパケットまたは隣接するルータの状態通知の誤りである。既述の手段を用いて、負荷変動の状態、アベイラビリティの変化及び帯域幅を求めることが容易に可能である。有利にはＩＰアドレスによって応答することができるインタフェースを介して、そのようにして求められた情報が隣接する装置、殊にルータと交換される。インタフェースは通常の場合、ネットワークの種類（グラスファイバ、銅）を伴い、またこれらの情報を交換するインタフェースが設けられているよう構成されている。
【００４０】
そのようにして伝送される状態情報は各装置によって固有の記憶領域に記憶される。この記憶領域には通常の場合、ハッシュ表のような高速アルゴリズムによってアクセスすることができる。個々のルータに対応付けられているこれらの情報との関係において、これらのルータを介して案内される経路が記憶される。さらには過去においてこれらのルータを介して案内されたが、後の時点では部分代替経路が使用されることにより迂回された経路が記憶される。これらの情報に基づいて簡単に経路を検出することができ、経路の経過時間を改善することができる。
【００４１】
装置の別の構成要素は、ネットワーク状態の変化によって関係している経路を算出するマイクロプロセッサである。つまりこの算出を、例えば変化によって関係している経路を算出することができるハッシュ表によって一義的に識別できる場合には殊に高速に行うことができる。この行程は劣化が問題になる場合には常に簡単に実現することができる。これに対してネットワーク状態の改善状況が存在する場合には、このネットワークセグメントを迂回する全ての経路を考慮する必要がある。これに関しても別個のハッシュ表を作成することができる。検索またはアクセスを高速化する他のアルゴリズムを択一形態として使用することができる。しかしながら、改善されたセグメントに関して前後に配置されているノードが存在するか否かが検査されることによってセグメントを迂回する経路を求めることも考えられる。このようなノードが存在する場合であれば、経路は改善されたセグメントを迂回し、セグメントを介する部分代替経路を用いるコネクションは有利である。
【００４２】
部分代替経路の探索に関して、ルートを求めるために公知のアルゴリズムを実現する公知の手段が使用される。複数のルータアルゴリズムが文献から公知である。必要であればこれらのアルゴリズムはパラメータを考慮して補完され、ここでパラメータは経路における包含すべきセグメントまたは包含すべきでないセグメントを表す。
【００４３】
広く知れ渡ったアルゴリズムは部分代替経路を発見するために、記憶領域に格納されているルーティングテーブルを使用する。そのような情報が欠如している場合には、ルーティングの問合せが隣接するルータへと相応の入力／出力インタフェースを介して送信され、テーブルがリフレッシュされる。
【００４４】
部分代替経路の検出においては優先的な目的地として、性能の変化により関係しているネットワークセグメントの後方にアクセス可能に配置されている次のノードが示される。
【００４５】
前述の機能を達成するために、有利な実施形態においては既存のハードウェア要素が適合されたソフトウェアによって制御される。
【００４６】
以下では唯一の図面を参照する。図１は複数のルータから構成されるネットワークを示し、ここで本来的にノードＲ５を介して案内された経路が別の経路を介して迂回される。
【００４７】
唯一の図面はＲ１からＲ８のルータ１１から成るネットワークを示し、これらのルータは実線によって表されているネットワークセグメントによって接続されている。破線で表されている本来的なルート１２はＲ１からＲ２、Ｒ５、Ｒ７を介してＲ８まで案内されたものである。ルータＲ５とＲ７の間の過負荷１４に基づきルータＲ２には、セグメントは十分な性能を発揮しないという通知が送信される。この送信はルータＲ５に由来する。ここでルータＲ２はこのセグメントを迂回するために最短の迂回路１３を選択する。この場合における最短の迂回路は部分代替経路Ｒ２、Ｒ４、Ｒ７である。この部分代替経路は本来の経路に包含されており、その結果ここで経路はＲ１、Ｒ２、Ｒ４、Ｒ７、Ｒ８となる。同様に、部分代替経路を形成するために他の考察も行えることを示唆しておく。つまりノードＲ５、Ｒ４、Ｒ７を介する迂回も同様に実施することができる。このことは使用される発見的方法及び目下の負荷状況に常に依存する。
【図面の簡単な説明】
【００４８】
【図１】複数のルータから構成されるネットワークである。
【図１】
2005505198.tif 000003
【国際公開パンフレット】
2005505198.tif 000004
2005505198.tif 000005
2005505198.tif 000006
2005505198.tif 000007
2005505198.tif 000008
2005505198.tif 000009
2005505198.tif 000010
2005505198.tif 000011
2005505198.tif 000012
2005505198.tif 000013
2005505198.tif 000014
2005505198.tif 000015
2005505198.tif 000016
2005505198.tif 000017
2005505198.tif 000018
2005505198.tif 000019
2005505198.tif 000020
2005505198.tif 000021
2005505198.tif 000022
2005505198.tif 000023
2005505198.tif 000024
【国際公開パンフレット（コレクトバージョン）】
2005505198.tif 000025
2005505198.tif 000026
【手続補正書】
【提出日】平成16年1月12日(2004.1.12)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ルータを有するパケット指向のネットワークにおけるラベル・スイッチ・パスを適応する方法において、
ルータの少なくとも一部が、隣接するルータとプロトコルによってネットワークの状態、例えば負荷の変動、アベイラビリティの変化及び帯域幅に関する情報を交換し、起こりうるボトルネックまたは改善を識別し、
ボトルネックが隣接する場合には部分代替経路を発生させ、該部分代替経路を用いて該ボトルネックを介して案内される経路を該ボトルネックを迂回するよう局所的に変更し、及び／又は、改善が隣接する場合には部分代替経路を発生させ、該部分代替経路を用いて該改善を迂回する経路を該改善が経路内に包含されているよう局所的に変更することを特徴とする、ラベル・スイッチ・パスを適応する方法。
【請求項２】
隣接するルータの集合をマニュアルで対応付ける、または所定の距離をおいて配置し、該距離に関してメトリックを規定する、請求項１記載の方法。
【請求項３】
情報交換をルータにおいて規則的なデータトラフィックにおけるピギーパックとして実施するか、別個のコネクションによって行う、請求項１または２または１及び２記載の方法。
【請求項４】
ＲＳＶＰ、ＬＤＰを処理する、請求項１から３までのいずれか１項または複数項記載の方法。
【請求項５】
ルータは該ルータが監視する各経路に、該経路内に存在する隣接するルータを対応付け、所定のルータまたはルータから出発する隣接するネットワークセグメントが性能推移を示す場合には経路を適応させる、請求項１から４までのいずれか１項または複数項記載の方法。
【請求項６】
隣接するルータまたは隣接するネットワークセグメントの性能の劣化に関して、部分代替経路を既存の経路に統合することにより該ルータないし該ネットワークセグメントを迂回するよう構成されている用意された部分代替経路を管理し、
隣接するルータまたは隣接するネットワークセグメントの性能の改善に関して、部分代替経路を既存の経路に統合することにより前記ルータないし前記ネットワークセグメントが経路内に存在するよう構成されている用意された部分代替経路を管理する、請求項１から５までのいずれか１項または複数項記載の方法。
【請求項７】
隣接するルータまたはネットワークセグメントにおいて性能の推移が生じると、
隣接するルータまたは隣接するネットワークセグメントの性能が改善された場合には、該ルータまたは該ネットワークセグメントが部分代替経路の統合後に経路内に存在するよう部分代替経路を形成し、
隣接するルータまたは隣接するネットワークセグメントの性能が劣化した場合には、該ルータまたは該ネットワークセグメントが部分代替経路の統合後に経路外に存在するよう部分代替経路を形成する、請求項１から６までのいずれか１項または複数項記載の方法。
【請求項８】
前記部分代替経路をルートアルゴリズムに基づき計算し、該ルートアルゴリズムはルーティングテーブルにアクセスし、前記ルートアルゴリズムにはどのルータないしどのネットワークセグメントをルート選択の際に考慮できるか、ないし考慮できないかをパラメータとして引き渡す、請求項１から７までのいずれか１項または複数項記載の方法。
【請求項９】
前記部分代替経路をルートアルゴリズムに基づき計算し、該ルートアルゴリズムはルーティングテーブルにアクセスし、前記ルートアルゴリズムにはどのルータないしどのネットワークセグメントをルート選択の際に考慮できるか、ないし考慮できないかがパラメータとして引き渡す、請求項１から７までのいずれか１項または複数項記載の方法。
【請求項１０】
パケット指向のネットワークにおけるラベル・スイッチ・パス、例えばＭＰＬＳ経路を制御する、例えばルータである装置において、
請求項１から９までのいずれか１項または複数項記載の方法を実現する、手段及び該手段の制御部が設けられていることを特徴とする、装置。
【請求項１１】
隣接するネットワークの状態、例えば負荷変動、アベイラビリティの変化及び帯域幅を検査する分析手段と、情報を交換するインタフェースとが設けられている、請求項１０記載の装置。
【請求項１２】
メモリ領域に他のルータ及び直近には隣接していないネットワークに関するネットワーク状態が記憶され、情報に基づき経過時間が改善される経路が検出される、請求項１０及び１１記載の装置。
【請求項１３】
経路及び記憶されたネットワーク状態を相互に比較する手段、例えばマイクロプロセッサが設けられており、
ネットワーク経路の変更によって関係している経路を算出し、
ボトルネックが隣接する場合には該ボトルネックを迂回する部分代替経路がまたは発生され、改善が隣接する場合には該改善を介して案内される部分代替経路が発生され、
該算出された部分代替経路はルータ機能の適応により前記経路に統合される、請求項１０から１２までのいずれか１項または複数項記載の装置。
【請求項１４】
可能な限り短い部分代替経路を発生させる選択手段が設けられている、請求項１０から１３までのいずれか１項または複数項記載の装置。
【請求項１５】
前記部分代替経路は、メモリ領域に格納されているルーティングテーブルの使用により算出されるか、隣接するルータにルーティング問合せを送信することにより算出され、前記経路の目的地として、データフロー方向において性能変化によって関係しているネットワークセグメントの直ぐ後ろに配置されている、ネットワークセグメントまたはルータが選択される、請求項１４記載の装置。
【請求項１６】
ルータの公知の要素は相応のプログラミングによってソフトウェアを用いて、本方法の機能が達成されるよう拡張される、請求項１０から１５までのいずれか１項または複数項記載の装置。
【国際調査報告】
2005505198.tif 000027
2005505198.tif 000028
2005505198.tif 000029
2005505198.tif 000030
2005505198.tif 000031
2005505198.tif 000032