(57)【要約】通信ネットワークにおいてパケットがたどる可能性のあるパスのネットワークにわたる集合が、ネットワークの相互接続と、それと他のネットワークとの相互接続とを表わす情報を納めたパケットを収集することによって識別される。収集されたパケットの内容を利用して、ネットワーク内の通信情報がやりとりされる、ルータとサブネットワークとそれらの相互接続とのネットワークにわたる集合が識別される。ルータとサブネットワークとそれらの相互接続とのネットワークにわたる集合の任意の選択された部分を表わす出力が送り出される。
2005535174.tif 000002
【特許請求の範囲】
【請求項１】
通信ネットワークにおいてパケットがたどる可能性のあるパスのネットワークにわたる集合の識別方法であって、
前記ネットワークの相互接続と、該ネットワークと他のネットワークとの相互接続とを表わす情報を含むパケットを収集するステップと、
選択されたパケットの内容を検出するステップと、
前記検出された内容を利用して、前記ネットワーク内において通信情報がやりとりされる、ルータとサブネットワークとそれらの相互接続との前記ネットワークにわたる集合を識別するステップと、
前記ルータと前記サブネットワークとそれらの相互接続との前記ネットワークにわたる集合の任意の選択部分を表わす出力を送り出すステップと
を含んでなる方法。
【請求項２】
前記検出された内容を利用して、前記識別されたルータ及びサブネットワークに関連する機能と、前記ネットワーク内の通信情報がやりとりされる前記識別された相互接続のコスト基準値とを確認するステップを含む請求項１に記載の方法。
【請求項３】
前記検出された内容を利用して、前記ネットワークを通り、前記ネットワークと他のネットワークを接続する、前記ネットワーク内の通信情報がやりとりされる前記ネットワークにわたる可能性のあるパスの集合を割り出すステップを含む請求項２に記載の方法。
【請求項４】
前記検出された内容を利用して、コスト基準値に基づいて決まる、前記ネットワーク内の通信情報がやりとりされるデフォルトパスの集合を決定するステップを含む請求項３に記載の方法。
【請求項５】
それらの所定の機能に基づいて、前記ルータ同士を照会するステップと、
前記照会結果を利用して、ネットワーク入口ルータにおいて、パケット分類が生じているか否かと、前記ネットワーク内の通信情報が、前記デフォルトパスに対する任意の代替論理パスでやりとりされるか否かを判定するステップと
を含む請求項３に記載の方法。
【請求項６】
前記検出された内容を利用して、前記ネットワーク内の通信情報のやりとりが可能な代替論理パスを決定するステップを含む請求項３に記載の方法。
【請求項７】
前記決定されたパス間の比較結果を生成するステップを含む請求項４から６のいずれかに記載の方法。
【請求項８】
前記パスの所定の経路選択目標を表わした、前記決定されたパスに関連する特性について前記ルータに照会するステップを含む請求項５に記載の方法。
【請求項９】
前記比較結果を利用して、前記所定の経路選択目標を達成するであろう、現在用いられている論理パスに対する代替論理パスを突き止めるステップを含む請求項７または８に記載の方法。
【請求項１０】
前記所定の経路選択目標を達成する代替の集合をなす論理パスを推奨するステップを含む請求項９に記載の方法。
【請求項１１】
前記ネットワークにおける少なくとも１つのリンクを伝搬するパケットをモニタすることによって、パケットが収集されるものである請求項１から１１のいずれかに記載の方法。
【請求項１２】
通信ネットワークにおいてパケットがたどる可能性のあるネットワークにわたるパスの集合の識別装置であって、
ネットワークの相互接続と、該ネットワークと他のネットワークとの相互接続とを表わす情報を含むパケットを収集するためのコレクタと、
選択された該パケットの内容を検出するための検出器と、
前記検出された内容を利用して、前記ネットワーク内において通信情報がやりとりされる、ルータとサブネットワークとそれらの相互接続との前記ネットワークにわたる集合を識別するための識別器と、
前記ルータとサブネットワークとそれらの相互接続との前記ネットワークにわたる集合の任意の選択部分を表示するための出力器と
を含んでなる装置。
【請求項１３】
前記識別器が、前記検出された内容を利用して、前記識別されたルータ及びサブネットワークに関連した機能と、前記ネットワーク内で通信情報がやりとりされる前記識別された相互接続のコスト基準値とを確認するものである請求項１２に記載の装置。
【請求項１４】
前記識別器が、前記検出された内容を利用して、前記ネットワークを通り、前記ネットワークと他のネットワークを接続する、前記ネットワーク内の通信情報がやりとりされる前記ネットワークにわたる可能性のあるパスの集合を割り出すものである請求項１３に記載の装置。
【請求項１５】
前記識別器が、前記検出された内容を利用して、コスト基準値に基づいて決まる、前記ネットワーク内の通信情報がやりとりされるデフォルトパスの集合を決定するものである請求項１４に記載の装置。
【請求項１６】
それらの所定の機能に基づいて、前記ルータ同士を照会するための照会生成器を含むことと、前記識別器が、前記照会結果を利用して、ネットワーク入口ルータにおいて、パケット分類が生じているか否かと、前記ネットワーク内の通信情報が、前記デフォルトパスに対する任意の代替論理パスでやりとりされるか否かを判定するものである請求項１４に記載の装置。
【請求項１７】
前記識別器が、前記検出された内容を利用して、前記ネットワーク内の通信情報のやりとりが可能な代替論理パスを決定するものである請求項１４に記載の装置。
【請求項１８】
前記識別器が、前記決定されたパス間の比較結果を生成するものである請求項１５から１７のいずれかに記載の装置。
【請求項１９】
前記照会生成器が、前記パスの所定の経路選択目標を表わした、前記決定されたパスに関連する特性について前記ルータに照会するものである請求項１６に記載の装置。
【請求項２０】
前記識別器が、前記比較結果を利用して、前記所定の経路選択目標を達成するであろう、現在用いられている論理パスに対する代替論理パスを突き止めるものである請求項１８または１９に記載の装置。
【請求項２１】
前記識別器が、前記所定の経路選択目標を達成する代替の集合をなす論理パスを推奨するものである請求項２０に記載の装置。
【請求項２２】
前記ネットワークにおける少なくとも１つのリンクを伝搬するパケットをモニタするためのモニタを含む請求項１２から２１のいずれかに記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、インターネット・プロトコル（ＩＰ）を利用するパケット・ネットワーク等の通信ネットワークにおいて、ルータと、その関連する相互接続通信リンクと、リンクを伝搬するパケットがたどるパスとを識別するための方法及び装置に関する。本発明は、特に、Ｏｐｅｎ  Ｓｈｏｒｔｅｓｔ  Ｐａｔｈ  Ｆｉｒｓｔ（以下、「ＯＳＰＦ」とよぶ）プロトコルもしくは中間システム間（ＩＳ−ＩＳ）プロトコル、または、その任意の同等物等のリンク状態経路選択プロトコルを利用するネットワークに適用することができる。
【背景技術】
【０００２】
インターネット・サービス・プロバイダ（ＩＳＰ）は、それ自体とその競争業者との違いを明らかにし、既存のコスト構造または資本予算を危機に陥れることなく、顧客に対するサービス水準を向上させるため、ますます、コスト最適化、サービス強化、または、サービス差別化のメカニズムを用いて、そのネットワーク内における「トラフィック管理（traffic management）」を実施するようになっている。これらのメカニズムは、（後述する）トラフィック・エンジニアリングと、サービス品質（ＱｏＳ）測定と、サービス水準の一致（ＳＬＡ）とを含む。オペレータによるこれらの「トラフィック管理」ネットワークの実現を助けることができるさまざまなテクノロジが存在する。ＩＰネットワークの場合には、これらは、（例えば、インターネット技術特別調査会のＲｅｑｕｅｓｔ  ｆｏｒ  Ｃｏｍｍｅｎｔｓ（ＲＦＣ）３０３１参照の）マルチプロトコル・ラベル・スイッチング（ＭＰＬＳ）と、（例えば、ＲＦＣ２４７４及び２４７５参照の）差別化サービスとを含む。
【０００３】
これらのテクノロジ間における共通テーマは、データ・パケットが（一般に、インターネット用語で自律システムと呼ばれる）個別ネットワークに最初に入る入口ポイントにおけるパケット分類の利用である。逆に、そのネットワークの出口ポイントでは、同じパケットが分類解除される場合が多いので、そのパケットを受信する次のネットワーク／自律システムは、それが望むなら、それ自体のやり方でパケットを再分類することができる。この分類によって、各パケットが、ネットワークを通って送られる際に、適切な処理を受けるという保証が得られる。パケットがネットワークの通過時に受けることになる処理は、入口ルータでパケットに施される分類のタイプに応じて異なることになる。
【０００４】
中間ルータは、分類された各パケットについて、パケットが分類されなかった場合にそれが通常たどることになるであろう所定のデフォルトパス（default path）から離れた、ネットワークを通る異なる論理パスへと強制的にパケットを送り込む。少なくとも１つのデフォルトパスが、ネットワーク内の各送信元及び各宛先に指定されている。このデフォルトパスは、一般に、各相互接続について内部ゲートウェイ・プロトコル（ＩＧＰ）・コスト基準値に基づいて指定される最小コスト・パスである（図４〜図７を参照して、ＯＳＰＦとの関連において後述する）。
【０００５】
従って、論理パスは、異なる経路指定（パケット送り）処理を受ける任意のパケットがたどる、代替非デフォルトパスである。論理パスは、例えば、選択されなかった場合には、一般にパケットがたどることになるパスとは別個の物理パスとすることができる。同様に、論理パスは、中間ルータにおける異なる待ち行列処理によって指定することができる。いずれの例においても、分類されたパケットは、施される分類に応じて、異なる処理の集合を受け、デフォルトパスで送られる場合の同じパケットに比べて、異なる伝送特性の集合がパケットに付与されることになる。各論理パスは、その論理パスのために取っておかれる物理的相互接続における帯域幅の量、サービス水準（「銅」、「銀」、または、「金」）、最大許容ジッタ、または、論理パスが通過しなければならない任意の特定ルータ等の、パスを伝搬するパケットに関する伝送特性を決める割り当て特性の集合を有している。
【０００６】
例えば、トラフィック・エンジニアリングを用いるネットワーク・オペレータは、そのＭＰＬＳ使用可能ネットワークを通る専用論理パスを介して、ジッタに影響されやすいテレビ会議トラフィックを送るように決断することができる。そのパスは、非テレビ会議トラフィックがたどることになる他のデフォルトパスとは異なる。潜在的により多くのルータ・ホップがあるにもかかわらず、専用パス（ここでは、別個の物理パス）は、他のトラフィックを伝送せず、従って、望ましくないジッタを導入することなく、音声及びビデオ組み合わせ負荷に容易に適応することができる。他の全てのトラフィックは、例えば、ＩＧＰによって指定される最低総コスト基準の経路であるデフォルトパスをたどる。どちらの経路をたどるにせよ、全てのトラフィックは最終的に出口ルータに到達し、そして、パケットを分類解除して次のネットワークに渡す準備が整うことになる。この負荷平衡がとられなければ、全てのネットワーク・パケットが、デフォルトパスを利用して送られることになるので、ピーク時には、このために、ネットワークが過負荷になって、パケットを廃棄するか、遅延させ、テレビ会議が使用できなくなり、他のデータ・トラフィック・ユーザにとって問題を生じることになる。
【０００７】
トラフィック・エンジニアリング・プロセスは、例えば、異なる顧客、異なるサービス、または、その両方の組み合わせに関して、多くの異なるレベルで適用することができる。同様に、経営目標の異なるＱｏＳ及びＳＬＡメカニズムのような他のトラフィック管理ツールを用いることもできる。ＱｏＳ及びＳＬＡは、両方とも、入口ポイント及び出口ポイントにおけるパケット分類を必要とし、両方とも、結果として、他の経路選択ポリシーをとり、（通常、最小コストである）デフォルトパスとは異なる論理パスを利用して、ネットワーク内において同時にトラフィックを送ることになる。
【０００８】
多くのトラフィック・エンジニアリング技法では、ネットワークの動作をモニタして、例えば、合意のＱｏＳまたはＳＬＡ基準の遵守を監査し、基準に達しなければ、改善措置または（あまり望ましくないが）補正を適宜加えることが必要になる。トラフィック管理ネットワークのこのようなモニタを試みるネットワーク管理システムに関する問題点は、パケットがネットワークに入り、ネットワークから出て行く場所を突き止めることと、パケットの分類及び後続処理の是非を確かめることである。ネットワーク管理システムは、いずれの場合にも、結果として、パケットが遅延するか、廃棄され、おそらく、ＳＬＡが守れなくなる、トラフィックの誤った経路指定を生じさせる可能性のある間違ったパケット分類、または、分類に関係なく、全てのトラフィックに同じパスをたどらせる可能性のある内部ルータの障害を検出すべきである。
【０００９】
インターネット全体が多くの管理ドメインに分割される。例えば、インターネット・サービス・プロバイダは、単一の管理ドメインを構成することができる。各管理ドメインは、近傍ドメイン（他のＩＳＰ等）と協定を結んで、互いのトラフィックを伝送し、ユーザが期待する接続性を与える同位または通過関係を確立することにより、インターネットの一部を形成する。管理ドメインは、１つ以上の自律システム（autonomous system：以下、「ＡＳ」とよぶ）を含む。ＡＳは、一般に（例えば、ＩＳＰなどの）単一技術管理組織下にあるルータの集合であり、
−  外部からは、単一の首尾一貫した内部経路選択プランを備えているように見える（１つ以上の内部ゲートウェイ・プロトコルと、１つ以上の共通基準値とを用いて、ＡＳ内におけるパケットの経路選択を行う）、
−  それを介して、どのような宛先に到達可能であるかについて、筋の通った説明を行う、
−  外部ゲートウェイ・プロトコルを利用して、他のＡＳにパケットを送る。
今後、「ネットワーク」という用語は、インターネットに関連して、このような自律システムを表わすために用いられる。他の種類の通信システムとの関連においては、ネットワークという用語は、それにシステム全体が含まれているか、または、システムの一部だけしか含まれていないかにかかわらず、概念及び機能がインターネットＡＳに類似した運用要素の集合を意味するものと理解すべきである。
【００１０】
インターネットは、多くの管理ドメインにおける多くのＡＳから構成されている。各ＡＳ間の各コネクションには、「エッジ（edge）」・ルータが設けられており、各エッジ・ルータは、何らかの形態のトラフィック管理を実施する潜在能力を有している。大規模ＩＳＰは、他の多くのＩＳＰと対話する入口及び出口ルータを有し、多くの異なるエンド・カスタマを抱えることができる。各入口及び出口ルータは、多くの異なるポリシーを用いてトラフィックの分類及び経路選択を実施している可能性がある。トラフィックを分配し、モニタし、管理する管理テクノロジに伴う多くの問題点については、すぐに明らかになる。
【００１１】
（例えば、アクティブ・エッジ・ルータ及びネットワークを伝搬するパケットを扱う中間ルータを識別して）ネットワークのトポロジ全体を知ることは、これらの問題点に対処する上においてかなりの助けとなる。しかし、既存のパケット・ネットワーク・テクノロジでは、この知識が、トラフィック管理の促進に利用可能な外部ツールに簡単にアクセスできる明示形式によって提供されることはない。上述の問題点に関して助けとなる可能性のある、ネットワーク自体の補助システムは、極めて大規模な可能性のあるネットワークから、リアルタイムに、そして、理想的には、既存のネットワーク及びルータの性能に認識できる影響を及ぼすことなく、トポロジ情報を送り出すことが必要になる。ルータには、ネットワークにおけるルータ及びリンク状況の完全なデータベースが納められている。この情報は、リンク状態データベースとして知られており、各ルータ内において、その最終宛先に向かってデータ・パケットを送るのに最適な近傍ルータを判定するための経路選択テーブルの生成に利用される。この経路選択テーブルは、例えば、ＲＦＣ２３２８に解説のＯＳＰＦリンク状態プロトコル（今後は、ＯＳＰＦプロトコルと呼ばれる）によって生成される。ルータのリンク状態データベース内に納められた情報は、そのルータの動作要件に十分な程度までトポロジについて明らかにする。このようなデータは、原則的に、ルータから少しずつ抽出して、活用し、完全なトポロジの記述が得られるようにすることができる。あいにく、現行のテクノロジを利用しても、スケールと正確性と適時性とについて必要とされる要件を満たし、同時に、ネットワーク保全性が保たれることを保証するやり方で、必要なデータにアクセスすることはできない。
【００１２】
例えば、理論上は、簡易型ネットワーク管理プロトコル（simple network management protocol：ＳＮＭＰ）を利用した照会を利用して、必要な情報を集めることができるが、このアプローチは、複数ルータを含む大規模ネットワークに利用するのにはあまり適していない。ネットワークの完全なトポロジを確認する際に必要とされる、大規模な集合をなすＳＮＭＰ照会によって、ルータに重い処理負担がかかり、かなりの量のネットワーク・トラフィックが生じることになる。さらに、その大部分が、パーソナル・コンピュータまたはワークステーションのような端末ということになる、ネットワークの各アドレスについて照会しなくても済むようにするには、ルータ・アドレスが、前もって分っていることが必要とされるので、かなりの管理上の負担をかけることになり、ネットワーク・トポロジの自律的発見または検証の利点を損なうことになる。同様の問題が、オペレーション・サポート・システム（ＯＳＳ）または他の外部データ源からの情報抽出にも当てはまる。この情報は、利用不可能か、供給されないか、または、あまりにも影響されやすくて直接アクセスによる検索を許可できないと判断される可能性がある。さらに、情報が利用可能であったとしても、別途検証しなければ、情報が正確であるという保証は得られない。
【発明の開示】
【発明が解決しようとする課題】
【００１３】
本発明の目的は、ネットワーク・トポロジに関する記述の作成を助けることによって、トラフィック管理のモニタを容易にすることにある。例えば、本発明を利用して得られるネットワーク・トポロジの記述は、ネットワーク・オペレータが、ＭＰＬＳ及び差別化サービスのようなトラフィック管理技法を実施して、ネットワークを管理するのを手助けすることもできるか、または、中核的ＭＰＬＳ使用可能ＩＰネットワーク（ＲＦＣ２９１７を参照されたい）と、（インターネット電話としても知られる）ＩＰ上での音声通信サービスと、ＳＬＡと、ＱｏＳメカニズムとの実施に利用することもできる。すなわち、本発明は、ネットワークに存在するさまざまな物理相互接続と、ルータ及びサブネットワークによって実現される異なる論理パスと任意の関連伝送特性とのモニタを容易にする。
【課題を解決するための手段】
【００１４】
本発明の一態様によれば、通信ネットワークにおいてパケットがたどる可能性のあるパスのネットワークにわたる集合を識別する方法が得られる。この方法は、
ネットワークの相互接続と、そのネットワークと他のネットワークとの相互接続とを表わす情報を含むパケットを収集するステップと、
収集パケットの内容を検出するステップと、
検出した内容を利用して、ネットワーク内において通信情報がやりとりされる、ルータとサブネットワークとそれらの相互接続とのネットワークにわたる集合を識別するステップと、
ルータとサブネットワークとその相互接続とのネットワークにわたる集合の任意の選択部分を表わす出力を送り出すステップとを含んでなる。
【００１５】
この文脈における「ネットワークにわたる（network-wide）」とは、作成されるネットワークの記述が、ネットワークにおける任意の特定のルータまたは他のノードに焦点を絞ったものではないことを表わしており、ネットワーク全体を意味することもある。例えば、ＯＳＰＦは、概念的には、各ルータについて、所望の経路選択テーブルの生成に向かう過渡的段階として、ツリーのルートとしてそのルータを備えた、ネットワークを通るパスのツリー記述を生成する。このツリーは、この「ルート」・ルータからパケットを送り出す必要のないルータ間のパスを含んでいない。対照的に、本発明では、全てのルータが等しく重要なネットワーク・トポロジの記述が生成され、典型的な実施例では、デフォルトパスだけではなく、全てのルータ間における全てのパスの包括的なビューが示される。
【００１６】
本発明のもう１つの態様によれば、通信ネットワークにおいてパケットがたどる可能性のあるパスのネットワークにわたる集合を識別するための装置が得られる。この装置は、
ネットワークの相互接続と、そのネットワークと他のネットワークとの相互接続とを表わす情報を含むパケットを収集するためのコレクタと、
選択されたパケットの内容を検出するための検出器と、
検出した内容を利用して、ネットワーク内において通信情報がやりとりされる、ルータとサブネットワークとそれらの相互接続とのネットワークにわたる集合を識別するための識別器と、
ルータとサブネットワークとそれらの相互接続とのネットワークにわたる集合の任意の選択部分の表示を行うための出力器と
を含んでなる。
【発明を実施するための最良の形態】
【００１７】
通信ネットワークにおいて通信リンクによって相互接続されたルータの機能を識別するための本発明による方法及び装置については、例証のため、添付の図面に関連して解説することにする。
【００１８】
図１を参照すると、自律システムＡＳ１と、それに接続された他の２つの自律システムＡＳ２及びＡＳ３の一部を含む、インターネットの概念上の一部が示されている。システムＡＳ１は、システムＡＳ２及びＡＳ３との外部接続を施す２つのエッジ・ルータ１０及び１２と、それら自体のＡＳ内において他のルータだけに接続される３つの内部ルータ１４と１６と１８とをそれぞれ含んでいる。システムＡＳ２及びＡＳ３は、同様に、システムＡＳ１に対する接続を施すエッジ・ルータ２０及び３０と、内部ルータ２２と２４と３０と３４とを含んでいる。
【００１９】
各ＡＳは、そのＡＳにとって局所的であり、ＡＳ間において大域的な情報を送る必要があるので、データ・パケットは、ノードまたはルータを介して、正しい宛先に送ることができる。ＡＳ間において、ルータ（及び経路）は、例えば、ＲＦＣ１７７１に解説のある境界ゲートウェイ・プロトコル（ＢＧＰ）のような、外部ゲートウェイ・プロトコルと呼ばれるクラスのプロトコルを用いて、静的または動的に構成される。ＡＳ内において、ルータ（及び経路）は、ＯＳＰＦ、ＩＳ−ＩＳ、または、経路選択情報プロトコル（ＲＩＰ）のような内部ゲートウェイ・プロトコル（ＩＧＰ）と呼ばれるクラスのプロトコルを用いて、静的または動的に構成される。便宜上、以下の解説では、ＯＳＰＦが用いられるものと仮定するが、本発明は、ＩＳ−ＩＳを含む、ＯＳＰＦと類似の概念及び機能を具現化する他のプロトコルに関して用いることもできる。
【００２０】
ＯＳＰＦのようなリンク状態経路選択プロトコルの場合には、各ルータは、そのルータを含むＡＳの全体または一部を形成する領域またはゾーンのトポロジを記述したデータベースを分配及び保守する責務を担う。このデータベースは、リンク状態データベースとして知られている。起動時に、ルータは、ルータの管理者によってあらかじめ構成された情報に基づいた、それ自体の局所的状態と、それが接続されているインターフェイスと、ネットワークとについてしか認識しない。接続性のようなその他のネットワーク状態情報の学習及び分配プロセスは、ＯＳＰＦプロトコルによって規定された特殊データ・パケットをＡＳ内の他のルータと交換することによって行えるようになる。
【００２１】
当初は、例えば、パケット・マルチキャスト技法を用いて、近傍ルータとの「隣接関係（adjacency）」が形成される。隣接関係は、経路選択情報を交換するため、あるルータが近傍のアクティブ・ルータのそれぞれと形成する関係である。隣接関係が形成されると、ルータは、ＯＳＰＦプロトコルに従ってフォーマットされたＯＳＰＦリンク状態記述パケットを利用して、それらの状態に関する情報を交換する。このプロセスは、ルータがＡＳのそれらのゾーンのトポロジに関して共通認識を持ち、その結果、各ルータについてのリンク状態データベースが構築されることになるまで続行される。
【００２２】
ＡＳ全体にわたる隣接関係形成プロセスが完了すると、ＡＳ内の各ルータは、リンク状態データベースのそれ自体のコピーに関して同じアルゴリズムを実行し、ルートとしてのそれ自体から各宛先まで、ＩＧＰ基準値に従って指定される最小コスト・パスのツリーを含む固有の経路選択テーブルを作成する。結果として得られる最小コスト・パスは、ネットワークを伝搬する全ての非分類パケットがたどるデフォルト経路になる。
【００２３】
上述のように、ＡＳ内においてペアをなすネットワークを経路選択領域またはゾーンにグループ化することができる。あるゾーンのトポロジは、そのゾーンを含むＡＳの残りのゾーンと共有されないので、経路選択トラフィックが大幅に減少する。ゾーン間において、ゾーン間の接続性を確認するため、要約パケットが交換される。
【００２４】
そのリンク状態データベースと経路選択テーブルの初期生成後に、そのネットワーク・ゾーンに変化が生じると、各ルータは、情報交換及び経路計算を繰り返す。変化には、リンクまたはルータの追加または除去、あるいは、リンクのコスト変化が含まれる。リンク状態データベースが古くなる可能性をなくすため、新たな更新がなければ、周期的に、通常は３０分毎に、パケットの同報通信が繰り返される。
【００２５】
本発明では、ＯＳＰＦまたはＩＳ−ＩＳのようなリンク状態ＩＧＰを利用して、ＡＳ内のネットワーク・トポロジの強引ではない発見と、そのトポロジの注釈付き表現の生成を実施することにより、そのネットワークを通るネットワークにわたるパスの集合の後続発見とを容易にする。注釈付き表現は、頂点がルータまたはネットワークを表わし、エッジがルータに接続されたリンクを表す、有効グラフを用いてＡＳを記述する。注釈は、各頂点によって表わされたルータまたはネットワークについて発見されたデータを示す。ルータの場合には、注釈は、関連するＩＰアドレスと、ＩＰアドレスによって示されるインターフェイスの集合と、（ゾーン内、ゾーン間、または、自律システム間の）タイプまたは機能とを表わす。ネットワークの場合には、ＩＰアドレスによって示される関連ネットワーク・アドレス及びネットマスクと、（スタブ、中継、または、外部などの）ネットワーク・タイプとが示される。中継ネットワークは、局所的に発信されたものではなく、宛先が局所的でもないデータ・トラフィックの搬送が可能なネットワークである。スタブ・ネットワークは、行き止まりに似ており、外部ネットワークは、ＡＳ外の他のネットワークが宛先である。
【００２６】
図２には、本発明に従って作成されるグラフ例の視覚表現が示されている。グラフのエッジは、個々の頂点をつないでいる。１つのエッジによって２つのルータがつながっているのは、それらのルータが、物理的な二地点間リンクによって接続されている場合であり、一方、１つのエッジによって１つのルータと１つのネットワークが接続されているのは、そのルータがそのネットワーク上に１つのインターフェイスを備えていることを表わしている。各エッジについてＩＧＰによって決められた、パケット送信にそのインターフェイスを利用するコストに関する注釈が施されている。ＯＳＰＦの場合には、これはリンク基準値として知られている。
【００２７】
本発明の目的の１つは、ネットワークまたはルータの通常動作に対する影響が制限された、トポロジを生成することにある。トポロジ発見プロセスは、必要な情報が、ルータまたは他のネットワーク要素との能動的対話が制限された状態で、あまりネットワーク・トラフィックの増加が生じないようにして得られるという意味において、強引ではない。このため、図１に示すように、少なくとも１つのプローブまたはモニタ４０が、ＯＳＰＦパケットの存在するポイントにおいて、ＡＳに接続されている。プローブは、例えば、専用ソフトウェア・プログラムを実行する、イーサネット（登録商標）・カードを介してＡＳに接続された、「パーソナル・コンピュータ」などの低コスト・コンピュータでありうる。ネットワークに対する「論理的」コネクション・ポイントは、ルータによって同報通信されるＯＳＰＦパケットを確実に収集できるように選択される。物理的には、このコネクション・ポイントは、例えば、ルータ上のポート、または、ハブまたはスイッチを介した、サブネットワークから２つのルータ間のリンクへのタップとすることができる。ＯＳＰＦに関して、コネクションは、ＯＳＰＦパケットが伝搬するネットワークの任意のポイントにおいて必要とされる。これら物理的コネクションの場合、プローブ４０のソフトウェア・プログラムによって、「無差別モード」のコネクションが選択されたネットワーク・ゾーンのネットワーク・リンクまたはセグメントに開放される。無差別モードによって、プローブは、ＬＡＮ宛先アドレスに関係なく、必要なＯＳＰＦパケットを受信することができる。受信パケットは、（受信されて、ネットワークから除去されるのではなく）引き続き、妨害されることなく、ネットワークを伝搬することが許される。あるいはまた、ＯＳＰＦ及び他のＩＧＰ経路選択パケットは、さらに、ルータ自体によって、それら自体のＬＳＤＢに記憶され、生バイト・フォーマット（raw byte format）の形式で、ＳＮＭＰ  ＭＩＢによるデバッギングに利用することができる。最初に、及び、トポロジにおける各後続変化について、ネットワークの影響及びオーバヘッドを制限して、ＯＳＰＦ  ＭＩＢからパケットを収集することもできる。ＭＩＢからの生パケットの収集に必要とされるのは、ＳＮＭＰを利用する既存の方法の特徴である多数のＳＮＭＰ呼び出しではなく、極めて少数のＳＮＭＰの呼び出しである。ＭＩＢデータへの変化は、ＳＮＭＰトラップを用いて監視することができる。ＳＮＭＰトラップは、いったん設定されると、目標ＭＩＢデータの外部から加えられる変化を報告することになる。
【００２８】
プローブ４０は、プローブがＯＳＰＦ経路選択プロトコルにおける能動的な関与要素になることを要求されるので、任意のルータとの隣接関係の確立にＲＦＣ２３２８に記載の状態マシンを導入しないが、そのため、そのゾーンの他のルータにおいて擬似リンク状態データベース項目が生成されることになる。リンクをモニタしてパケットを収集する場合、プローブ４０は、受動的な状態のままであり、ゾーンまたはＡＳのルータによるＯＳＰＦパケットのフラッディング・プロセスに依存する。プローブ４０は、通常のＯＳＰＦメカニズムを利用してＯＳＰＦパケットを要求するのではなく、ＯＳＰＦパケットがモニタされているインターフェイスに到着するのを待つ。ＯＳＰＦパケットを受信すると、（後述される、図８〜図１３に例示された）トポロジ導出手順が実行され、所望のトポロジ記述がインクリメンタルに作成される。起動手順には、完全なトポロジ記述が確定する前に、通常は３０分のデフォルトリンク状態リフレッシュ時間間隔の経過が必要になる。ＯＳＰＦプロトコルへの能動的な関与要素になると、パケットの収集が加速され、完全な発見プロセスの時間が短縮される可能性があるが、この場合の副作用は、明らかに、ネットワーク及びルータに対する影響の増大である。あるいはまた、プローブ４０が、ＭＩＢ内に納められた生パケットからＯＳＰＦ経路選択データを収集する場合には、起動期間を必要とすることなく、完全な最新のトポロジを得ることができる。この方法では、ルータまたはネットワークに対する影響も制限される。そして、引き続きＯＳＰＦパケットを監視することによって、プローブは、トポロジ記述とネットワークの状態との調和がとれるようにすることができる。
【００２９】
ＡＳに必要なプローブ数は、ＡＳのサイズ及びその構成方法によって決まる。単一プローブによって、それが接続されるゾーンに関する完全な注釈付きのトポロジを生成することができる。ＯＳＰＦネットワークは、必ず、バックボーンとして知られる、少なくとも１つのゾーンを有する。このバックボーンに対するコネクションが望ましい。経験上明らかなように、多くのネットワークは、設計が階層的であり、バックボーンに接続された単一プローブによって、極めて有用な注釈付きトポロジが得られることになる。ミニゾーンＡＳに関する完全な注釈付きトポロジを発見するため、各アクティブ・ゾーンに対するコネクションが必要になる。しかし、単一コネクションであっても、選択ゾーンの完全な注釈付きトポロジ以外に、ＡＳの他のゾーンにおけるネットワーク、さらに、ＡＳのエッジ・ルータを介した外部ネットワークへの任意のコネクションに関する要約情報も得られる。
【００３０】
各プローブ４０は、パケットを収集し、後述の選択されたタイプのパケットをコピーする。そして、各プローブは、これらのコピーからデータを抽出して、データに処理を加え、注釈付きトポロジに関する情報を生成する。
【００３１】
下記の表に示すように、ＯＳＰＦプロトコルでは、５つのタイプのパケットが規定されている。本発明の目的からして、これらのＯＳＰＦパケット・タイプのうちの１つ、すなわち、タイプ４のリンク状態更新パケットが利用される。
タイプ    記述
１        ハロー
２        データベース記述
３        ンク状態要求
４        リンク状態更新
５        リンク状態確認応答
【００３２】
ハロー・パケットは、ＯＳＰＦネットワーク、例えば、イーサネット（登録商標）のような同報通信媒体にも生じ、最も頻繁に伝送されて、一定間隔で、ある特定のネットワーク・セグメントに現れる。ハロー・パケットは、従って、プローブ４０にネットワーク時間の正確な表示を供給するために利用可能である。プローブへの到達時に、ハロー・パケットに正確なタイム・スタンプが施される。例えば、パーソナル・コンピュータをベースにしたプローブは、その内部クロック、または、ネットワーク時間プロトコル（ＮＴＰ）に関連した全地球測位システム（ＧＰＳ）受信機から正確な時間表示を得ることができる。経験から明らかなように、ほとんどのネットワーク・オペレータは、この目的に利用可能な正確な時間サービスを提供する。ハロー・パケットのインターバル間の時間を測定し、その結果を記憶することによって、通常のＯＳＰＦパケット・シーケンスによって費やされる時間経過の正確な内部表示を確立することができる。この形態のタイマ・メカニズムは、古くなった情報がプローブ４０から確実に消去されるようにするためのタイムベースを提供する簡便な方法である。しかし、時間経過正確に表示することができる他の任意の形態のタイマ・メカニズムでも十分であろう。
【００３３】
リンク状態更新パケット（ＯＳＰＦタイプ４）は、ルータの状態（ルータのインターフェイス及び隣接関係を含む）またはネットワークの状態を記述した、１つ以上のリンク状態公示（ＬＳＡ）を含む。あるゾーンに関するＬＳＡの集合は、リンク状態データベースを構成する。下記に示すように、いくつかのタイプのＬＳＡが存在し、各ＬＳＡタイプは、ＡＳまたはネットワーク・ゾーン内における異なる要素について記述する。
ＬＳタイプ    記述
１            ルータＬＳＡ
２            ネットワークＬＳＡ
３            要約ＬＳＡ（ＩＰネットワーク）
４            要約ＬＳＡ（ＡＳＢＲ）
５            ＡＳ外部ＬＳＡ
【００３４】
ネットワーク構成に変化が生じると、必ず、ネットワークに古い情報が存在しないことを保証するため、ＬＳＡの同報通信がある一定間隔で行われる。各ＬＳＡは、ＡＳ内のＬＳＡに対する一意性の識別情報を与える、（ヘッダにおけるフィールドの組み合わせを含む）キー及びエージ情報の両方を含むヘッダ部分（図３に示す）を有する。あるＬＳＡをリンク状態データベースに受け入れるべきか否かの判定プロセスが、ＲＦＣ２３２８と、セクション１３．１及び１３．２とに記載されており、プローブ４０によって、プローブが受信するＬＳＡが、それが既に得ている既存のＬＳＡより新しいか否かと、そのＬＳＡをそれ自体のリンク状態データベースに受け入れるべきか否かとの判定に利用される。
【００３５】
プローブの内部クロックが更新されると、新しい時間値を利用して、リンク状態データベースの全てのＬＳＡのエージ・フィールドがインクリメントされる。従って、あるＬＳＡのエージ値が、通常、１時間に設定される、ＯＳＰＦ標準アーキテクチャ定数である最大エージより大きくなると、（図８に示すように）そのＬＳＡはリンク状態データベースから除去される。このプロセスによれば、プローブのリンク状態データベースから古いＬＳＡが確実に除去されるようにする防護対策が施されるので、プローブが更新ＬＳＡを入手し損なったり、または、リンク障害等のために更新ＬＳＡの損失が生じた場合に、プローブ４０によって作成されるトポロジ記述がひどく汚染されることはない。
【００３６】
プローブが、最初にそのリンク状態データベースを構築した時と、（例えば、新しいまたは更新ＬＳＡの受信後などの）プローブのリンク状態データベースに後続変化の発生が検出された後に、現在のネットワーク・トポロジのプローブによる注釈付き記述を生成または更新しなければならない。そして、これを実施する手順については、図８〜図１３に関連して解説することにする。関与するステップの大部分については正確なシーケンスが不可欠というわけではないが、ステップ６は、最後に実施しなければならない。同様に、トポロジは、リンク状態データベースが変化する毎に完全に再計算することもでき、または、処理される最新のＬＳＡ変化に関して、ただインクリメンタルに処理することもできる。両アプローチとも、等しく有効であるが、より実施が容易であるか、または、特定の実施により適合することが判明している方法を選択することができる。後述する実施例では、まず、トポロジの頂点の識別が、好都合であり、通常のグラフ作成技法に適合する。
【００３７】
ステップ１（図９）：ゾーン内のアクティブ・サブネットワークと、それらのサブネットワーク内のアクティブ・ルータとを識別する。これは、現在のゾーン内のネットワーク要素、特に、タイプ２ネットワークＬＳＡ及びタイプ１ルータＬＳＡの部分集合に関する情報を納めたＬＳＡを用いて実施される。ネットワークＬＳＡは、２つ以上のルータをサポートするサブネットワークに接続されたルータを指定する。ネットワークＬＳＡにおけるネットワーク・マスク・フィールド（図５を参照されたい）は、サブネットワークのアドレス空間のサイズすなわち範囲について記述しており、ＬＳＡのヘッダのリンク状態識別子フィールドにおけるＩＰアドレス（図３）は、サブネットワークにおける第１のＩＰアドレスを識別する。そのサブネットワークにおけるアクティブ・ルータのリストも提供されるが、ルータは、接続ルータ・フィールドのＩＰアドレス（図５）によって表示される。各ＬＳＡには、サブネットワークのあらゆるアクティブ・ルータについて１つずつの項目が納められている。
【００３８】
ルータＬＳＡは、記述のリンク・タイプに応じて、細分することができ、各ルータＬＳＡについて、異なるタイプのいくつかのリンクについて記述することもできる。コネクションのタイプは、下記のように識別される。
タイプ    記述
１        別のルータとの二地点間コネクション
２        中継ネットワークとのコネクション
３        スタブ・ネットワークとのコネクション
４        バーチャル・リンク
このステップでは、スタブ・ネットワークに対するタイプ３リンクに関する情報を納めたルータＬＳＡだけが検討される。スタブ・ネットワークに対するコネクションを記述した各ルータＬＳＡに、各リンク識別子フィールド（図４）及び後続するリンク・データ・フィールドによって、ＬＳＡのヘッダの公示ルータ・フィールドで識別されるルータについて、スタブ・ネットワークへのコネクションに関するＩＰアドレス及びネットワーク・マスクが得られる。サブネットワークにおける最後から２番目のルータが障害を生じて、サブネットワークにもはや２つ以上のルータがないという場合、リンク状態データベースから対応するネットワークＬＳＡを能動的に取り除くことはできない。この状況では、そのネットワークＬＳＡはまだ存在するが、スタブ・ネットワークとのコネクションを記述した項目を納めている新しいタイプ３ルータＬＳＡに取り替えられる。従って、このステップでは、アクティブ・サブネットワークにおけるアクティブ・ルータだけしか絶対に考慮しないようにするため、これら２つのタイプのＬＳＡに納められた情報は、タイプ３ルータＬＳＡの項目によって指定されるルータが、ネットワークＬＳＡにおいて指定される同じルータに関する情報に優先するように組み合わせられる。
【００３９】
ステップ２（図９）：トポロジの内部ネットワークの頂点を指定する。頂点は、ステップ１において得られたアクティブ・サブネットワークのリストにおける各アクティブ・ネットワークについて生成される。頂点には、ＩＰアドレス及びネットワーク・マスクの注釈つきであり、これによって、頂点によって表わされたサブネットワークの識別情報及びアドレス範囲が指定される。これらの頂点は、タイプ「内部ネットワーク」の注釈をつけることもできる。
【００４０】
ステップ３（図９）：トポロジのルータ頂点及び関連インターフェイスを指定する。
ステップ３．１：中継ネットワークに対するコネクションを記述した項目を納めているタイプ２ルータＬＳＡが分析される。これらのＬＳＡは、２つ以上の入口／出口ポイントが設けられたサブネットワークへのコネクションを有するルータについて記述している。各ＬＳＡについて、ＬＳＡのヘッダの公示ルータ・フィールドによって識別されるルータのＩＰアドレスが頂点のリストに追加される。リンク・データ・フィールドのＩＰアドレスによって識別されるアクティブ・ルータ・インターフェイスのリストは、頂点項目と対応付けられている。これに関して、ルータのインターフェイスは、ネットワーク・コネクションまたはリンクが行われるポートの同義語である。
【００４１】
ステップ３．２：二地点間コネクションであるリンクについて記述する項目を納めたタイプ１ルータＬＳＡが分析される。前述のように、ルータのＩＰアドレスが、頂点リストに追加され、リンク・データ・フィールドによって識別されるルータのインターフェイスのＩＰアドレスも追加される。
【００４２】
ステップ３．３：同様のプロセスが、バーチャル・リンクについて記述する項目を納めたタイプ４ルータＬＳＡにも用いられる（バーチャル・リンクについては、ＲＦＣ２３２８、セクション３．１及び１５に記載がある）。
【００４３】
ステップ３．４：次に、スタブ・ネットワークへのコネクションに関する情報を納めたタイプ３ルータＬＳＡが分析される。このプロセスは、中継ネットワークへのコネクションについて記述する項目を納めたタイプ２ルータＬＳＡに関するものと同じである。しかし、この場合には、ルータ・アドレス自体は、関連ルータ・インターフェイスとして追加される。このタイプのルータＬＳＡ項目に関するリンク・データ・フィールドは、ルータのインターフェイスを記述せず、接続されるスタブ・ネットワークのネットワーク・マスクについて記述する。従って、ルータのインターフェイスに関するＩＰアドレス・インターフェイスを決定することはできない。後述するように、コネクションを指定するため、このタイプのリンクの開始点は、ルータ自体とみなされる。
【００４４】
ステップ３．５（図１０）：指定のルータ頂点に、関連タイプの注釈がつけられる。ルータ・タイプは、ルータＬＳＡのＶＥＢフィールド（図４）におけるＥ及びＢフラグに従って表示される。Ｂフラグが設定されると、ルータは領域間として表示され、Ｅフラグが設定されると、ルータは、ＡＳ間またはネットワーク間として表示される。そうでなければ、頂点は、領域内として表示される。Ｖフラグが設定されると、頂点は、１つ以上のバーチャル・リンクのエンド・ポイントになる。
【００４５】
ステップ３．６（図１１）：各ＡＳ外部ＬＳＡに、ＬＳＡヘッダの公示ルータ・フィールドによって識別されるあるルータ頂点が存在しなければ、そのルータ頂点が、「送りアドレス」・フィールド（図７）のＩＰアドレスによって識別される関連インターフェイスと共に追加される。その頂点は、「ＡＳ間ルータ」の注釈がつけられる。同様に、各要約ＬＳＡに、公示ルータ・フィールドのＩＰアドレスによって識別されるルータに関する頂点が存在するかの確認と、それに「領域内ルータ」という注釈がついているかの確認とが行われる。このステップには、２つの目的、すなわち、完全なトポロジがまだ収集されていない期間中に、データの完全性を確認する目的と、プローブ起動時における発見プロセスの速度を増す目的とがある。
【００４６】
ステップ４．１（図１２）：トポロジの領域内ネットワーク頂点を指定する。このため、タイプ３及びタイプ４の要約ＬＳＡが考慮される。これらのＬＳＡは、ネットワーク（タイプ３要約ＬＳＡの場合）または領域間ルータ（タイプ４要約ＬＳＡの場合）を含む領域間宛先へのコネクションについて記述している。どちらのタイプでも、各要約ＬＳＡに、公示ルータ・フィールド及びネットワーク・マスク・フィールド（図６）のＩＰアドレスによって識別されるネットワーク頂点が、頂点リストに追加される。これらの頂点は、タイプ「要約ネットワーク」の注釈がつけられる。
【００４７】
ステップ４．２（図１２）：トポロジのＡＳ間ネットワーク頂点を指定する。タイプ５ＡＳ外部ＬＳＡを用いて、プローブ４０を含むネットワークの外部のネットワークに対する経路を表わす外部頂点の集合が指定される。これらは、その存在が、事前に作成された静的記述によって、または、ＢＧＰ−４のような外部ゲートウェイ・プロトコルによって知られることになった経路である。これら外部経路のそれぞれについて、ＯＳＰＦルータは、ＡＳ外部ＬＳＡを送り出すことになる。各ＬＳＡについて、ＬＳＡのヘッダのリンク状態識別子フィールド及びネットワーク・マスク（図７）のＩＰアドレスによって識別されるネットワークに関する頂点リストに頂点が追加される。頂点には、タイプ「外部ネットワーク」の注釈がつけられる。
【００４８】
ステップ５（図１２及び図１３）：ネットワークにおけるエッジを指定する。
ステップ５．１：通過エッジを指定する。中継ネットワークとのコネクションについて記述する項目を納めたタイプ２ルータＬＳＡを用いて、スルーまたは通過サービスを提供するネットワークに相当する任意の頂点に対してルータに相当する頂点を相互接続する、グラフ内のエッジが指定される。（中継ネットワークは、２つ以上の独立した入口／出口ポイントを備えるネットワークである。）ネットワークとの通過コネクションについて記述する項目を納めた各ルータＬＳＡに、エッジは、リンク識別子フィールド（図４）において指定されるルータ・インターフェイスからリンク・データ・フィールドによって指定されるサブネットワークへと発展するトポロジ記述において指定される。（ＲＦＣ２３２８によれば、「やはり、ＬＳＡを生じるオブジェクト（すなわち、もう１つのルータまたは中継ネットワーク）に接続する場合、リンク識別子は、近傍のＬＳＡのリンク状態識別子に等しくなる」。）従って、対応するネットワークＬＳＡの「リンク状態識別子」を備えたサブネットワークを用いて、指定されるエッジのエンド・ポイントが決定される。エッジには、基準値／コスト・フィールドにおいて定められたリンクを伝搬するコストの注釈が付けられる。重要なのは、サブネットワークの頂点には、３つ以上のエッジが接続される可能性があるという点に留意することである。
【００４９】
ステップ５．２：スタブエッジを指定する。スタブ・ネットワークとのコネクションについて記述する項目を納めたルータＬＳＡを用いて関連ルータ頂点と、入口ポイント及び出口ポイントが１つだけしかないネットワーク頂点との間のエッジが指定される。スタブ・ネットワークとのコネクションについて記述する項目を納めた各タイプ３ルータＬＳＡに、ルータのインターフェイスから始めて、エッジが追加されるが、この場合、インターフェイスは、ルータ自体と同じアドレス（実際、ルータを直接アドレス指定する）を備えており、サブネットワークで終了する。エッジの開始は、公示ルータ・フィールドによって表わされ、宛先は、リンク識別子及びリンク・データ・フィールドによって指定されるサブネットワークである。サブネットワーク・アドレスは、リンク・データによるリンク識別子フィールド及びネットワーク・マスクのＩＰアドレスによって表わされる。エッジには、基準値／コスト・フィールドにおいて定められたリンクを伝搬するコストの注釈が付けられる。
【００５０】
ステップ５．３：２地点間エッジを指定する。二地点間リンク及びバーチャル・リンクについて記述するルータＬＳＡを用いて、ルータ頂点を直接相互接続するエッジが指定される。バーチャル・リンクについては、ＲＦＣ２３２８セクション３．１及び１５において、二地点間リンクと同じやり方で取り扱うことができるトポロジを生成するために解説されている。もう１つのルータとの二地点間コネクション（タイプ１）、または、バーチャルリンク（タイプ４）について記述する項目を納めた各ルータＬＳＡについて、発展するトポロジにエッジが追加される。エッジは、リンク・データ・フィールドのＩＰアドレスによって示されるルータ・インターフェイスから始まり、リンク識別子フィールドのＩＰアドレスによって示される宛先ルータに至る。エッジには、基準値／コスト・フィールドにおいて定められたリンクを伝搬するコストの注釈が付けられる。
【００５１】
ステップ５．４：領域間のエッジを指定する。要約ＬＳＡを用いて、ルータ頂点を任意の領域間宛先について記述する頂点に接続するエッジが指定される。２つのタイプ、すなわち、ＩＰネットワークである宛先について記述するタイプ３と、他の領域間ルータである宛先について記述するタイプ４とが存在する。各タイプ３要約ＬＳＡに、ルータのインターフェイス（この場合、ルータ自体と同じアドレスを備え、実際に、ルータに直接アドレス指定する）からリンク状態識別子フィールド及びネットワーク・マスク・フィールドによって指定される領域間サブネットワークへのエッジが追加される。タイプ４要約ＬＳＡの場合には、ネットワーク・マスク・フィールドは無意味であるので、ゼロにしなければならず、リンク状態識別子は、ＡＳ間ルータのＩＰアドレスである。両方の場合とも、エッジには、基準値／コスト・フィールド（図６）において定められたリンクを伝搬するコストの注釈が付けられる。
【００５２】
ステップ５．５：ＡＳ間のエッジを指定する。ＡＳ外部ＬＳＡを用いて、ルータ頂点をＡＳ外の任意の外部宛先について記述する頂点に接続するエッジが指定される。各ＡＳ外部ＬＳＡについて、送りアドレスフィールド（図７）によって示されるルータ・インターフェイスから、ＬＳＡのヘッダにおけるリンク状態識別子フィールド、及び、ネットワーク・マスク・フィールド（図７）によって指定される外部ネットワークへのエッジが追加される。このエッジには、Ｅビット・フィールド及び基準値／コスト・フィールドにおいて定められたリンクを伝搬するコストの注釈が付けられる。Ｅビットが設定されていなければ、基準値すなわちコストは、他のエッジの他の内部リンク基準値と同じ単位で規定される。Ｅビットが設定されている場合には、リンクのコストは、他のどの内部リンク状態経路よりも大きいとみなされる。
【００５３】
ステップ６（図１３）：存続可能な経路のグラフを維持する。プローブ４０は、古くなった情報を除去しなければならないので、トポロジ情報を利用して、トラフィック管理または他のアプリケーションに対して、存続可能な経路だけしか決して報告されないようにする。例えば、プローブのリンク状態データベースには、ネットワークに分断を生じさせたネットワークの動作不良または障害以前に到着したＬＳＡを納められているかも知れないという可能性がある。ネットワークの分断障害点の向こう側にあるルータからの新たなＬＳＡ更新は、いずれも、それらを利用して、古い情報が除去されることになる、プローブ４０に到達することができなかったであろう。正確なトポロジ記述を維持するため、プローブ４０は、影響のあるルータと、ネットワークと、リンクに相当する頂点及びエッジとを除去しなければならない。
【００５４】
例えば、図１のシナリオでは、ルータ１６及び１８は、電源異常のために故障する可能性がある。図１４には、結果生じるネットワーク構成が示されている。プローブ４０は、その障害または「ネットワーク分断」側のルータ１０及び１４から更新を受信し続けることになる。しかし、その分断箇所の向こう側にあるルータ１２は、ルータ１０及び１４のいずれに対しても変化を伝えることができない。従って、ルータ１０及び１４、及び、プローブ４０のリンク状態データベースは、ルータ１２から送られたＬＳＡを含んでいることになる。しかし、これらのＬＳＡの情報は、プローブに現在分っている経路選択ゾーン外からのものであるため、もはや信頼できるものとみなすことはできない。プローブ４０の目的は、全ての可能性のある、存続し得るネットワーク・パスの記述を生成することにあり、従って、この記述には、障害のあるルータ１６及び１８が位置するポイントの向こうにあるネットワーク部分が含まれるべきではない。
【００５５】
グラフにおける各頂点の到達可能性は、プローブ４０がネットワークに接続されているポイントに相当する頂点から始めて、再帰的手順を利用して、全ての頂点を系統的に検査することによって推定される。例えば、「横型探索」及び「縦型探索」アルゴリズムに基づいて、グラフにおける到達可能性を求めるための周知の手順がいくつか存在する。これらのアルゴリズムでは、各頂点に接続されたエッジだけしか考慮されないので、グラフの切断された部分、この例の場合、ルータ１６及び１８は、取り除かれることになり、その結果は、ルータ１２からルータ３０まで、及び、それより先のパスを結果から除去した、「接続グラフ」である。
【００５６】
再帰的アルゴリズムの開始頂点が、プローブ４０に論理的に最も近い要素がどれかによって決まる、ルータまたはネットワークであるという点に留意することが重要である。例えば、プローブが、タップによって二地点間コネクションに直接接続される場合、開始点は、論理的に最も近いルータである。あるいは、プローブが中継サブネットワークに接続される場合には、サブネットワークを利用すべきである。プローブがルータのＭＩＢに接続される場合には、ルータを利用すべきである。中継サブネットワークによれば、それが接続されたルータのそれぞれを介して、ネットワーク・ワイドな複数の到達可能コネクションが得られ、到達可能性の計算中、これら複数コネクションを考慮しなければならない。結果得られるグラフは、外部アプリケーション（例えば、トラフィック管理のための）にエクスポートすることができ、プローブ４０に現在分っているアクティブな相互接続頂点だけを含んでいる。
【００５７】
このグラフは、プローブ４０によって、適合する形態のプロセス間通信を介して１つ以上の外部アプリケーションにエクスポートすることができる。例えば、既知の遠隔手順呼び出しメカニズム（ＲＰＣ）、または、共通オブジェクト・リクエスト・ブローカ・アーキテクチャ（ＣＯＲＢＡ）またはＪａｖａ（登録商標）遠隔メソッド呼び出し（ＲＭＩ）に関する標準に記載のメカニズムを利用することもできる。プローブ４０のソフトウェアをアプリケーション・ソフトウェアに直接組み込んで、オペレータが、必要に応じてネットワークのあちこちに運ぶことができ、単純で小型で軽量の携帯用システムを創り出すこともできる。
【００５８】
各変化の発生時に、アプリケーションにそれを気づかせるため、注釈付きグラフ・データを利用できるようにすることができる。これは、「公示及び承認」メカニズムと呼ばれる場合もあり、これにより、アプリケーションは、変化が公示されると、その変化を承認することになる。代わりに、より単純に、要求があり次第、新しいトポロジをアプリケーションに送ることもできる。
【００５９】
エクスポートされるトポロジ情報は、いくつかの形態をとることができるが、あるタイプのアクティブ頂点とアクティブエッジのリストとを含むことになる。アクティブ頂点のリストは、一般に、ＩＰアドレス及びネットワーク・マスクまたは接頭語長によって表わされる頂点識別情報、例えば、ネットワークやＡＳ間やゾーン間やゾーン内等の頂点によって表わされるネットワーク要素のタイプと、それらが属するゾーン内及びゾーンを含む。また、ＩＰアドレスによって表わされるインターフェイスのリストを含みうる。エッジのリストは、一般に、ＩＰアドレス及びネットワーク接頭語によって表わされる、それらが接続される頂点と、エッジによって表わされるリンクを利用するコストまたは基準値とを含む。また、エッジのリストは、やはりＩＰアドレスによって表わされる、ルータにおいて用いられるインターフェイスを含みうる。
【００６０】
アプリケーションが、「公示及び承認メカニズム」を用いて、変化の発生時に、それらの変化を要求する場合には、ＩＰアドレス及びネットワーク接頭語によって頂点を指定することによって、イナクティブになるエッジ及び頂点、または、ネットワークの変化をトポロジ記述から除去することができる。同様に、除去すべきエッジは、２つの接続されている頂点によって識別することができる。アプリケーションに対して、エッジまたは頂点がもはやアクティブではないことを知らせる場合には、エッジ基準値または頂点タイプのような注釈情報を供給することもできるが、厳密に言えば必要ではない。
【００６１】
アプリケーションは、注釈付きグラフ・データを利用して、例えば、任意のＡＳ間接続性をもたらす頂点のリストを抽出することにより、現在のアクティブ論理パスの集合が求められる。このタイプの頂点には、ネットワークの入口点及び出口点が含まれており、トラフィック分類が上述のように適用されることになる可能性が最も高い場所である。アプリケーションは、頂点によって表わされるルータに直接照会して、実際にトラフィック分類が存在するか否かを確認することができ、このような照会に利用可能な共通メカニズムの１つが、ＳＮＭＰ（ＲＦＣ１１５７）である。ＳＮＭＰ及び選択されたトラフィック管理システムに関する関連管理情報ベース（ＭＩＢ）は、大部分のルータにおいて利用可能であり、このタイプのネットワーク管理データにアクセスするための広く受け入れられているメカニズムを提供する。ネットワークに内部トラフィック分類が存在する可能性があれば、内部ルータ頂点を探索することもできる。これは、それほど可能性が高くないが、状況によっては、生じることもあり得る。
【００６２】
トラフィック分類が、例えば、ＭＰＬＳラベル・スイッチト・パス（ＬＰＳ）を通じて、デフォルト最小コスト・パス以外のパスに沿ったある特定のプロバイダからのトラフィックの経路選択に利用されている場合、外部アプリケーションは、ルータが現在用いられている実際の非最短パスに関する情報を返信するように要求することができる。やはり、ＳＮＭＰを用いて、例えば、その論理パスに割り当てられた、予約帯域幅のような任意の伝送特性を含む、このパスの情報を検索することができる。
【００６３】
見つかったトポロジ・データを利用して、トポロジに関するデフォルトパスの集合を含む、ネットワークにわたるパスの集合を決定することができる。異なる送信元ルータからの複数論理パスが単一相互接続を通る潜在的可能性があるという点に留意することが重要である。従って、代替論理パスを決定する場合には、ネットワークにわたるパスの集合を検討しなければならない。ネットワークにわたるパスの集合の検討に失敗すると、異なる送信元／入口ルータからの複数論理パスにサービスするルータ、サブネットワーク、または、相互接続に過剰規制及び輻輳を生じさせる可能性がある。ネットワークにわたるパスの集合は、これらの計算の妥当性を保証するために必要とされる。このパスの集合を決定するため、「横型探索」または「縦型探索」及びダイクストラのアルゴリズム（ＲＦＣ２３２８に記載のある）に基づくグラフの探査を実施するための、再帰手順が利用される。これらによって、入口／送信元ルータと出口／宛先ルータとの各組合せについて、最短パスを含むネットワークにわたるパスの集合が得られる。アルゴリズムに対する入力は、ＩＧＰコスト基準値と、ルータ、サブネットワーク、及び、相互接続について発見されたグラフ・データとである。
【００６４】
ネットワーク・オペレータは、例えば、オーバレイされた、要求されるトラフィック管理情報（ＬＳＰに関する）に関して、ネットワークにわたるパスの集合と、ＡＳを用いる関連コスト／基準値を含む組み合わせ情報とを利用して、論理非デフォルトパスの配置をモニタする。この組み合わせ情報は、例えば、ネットワーク・オペレータが、新しいパスを設計し、ＬＳＰを整備し、ネットワークが設計仕様どおりに機能しているか確認する上において大いに役立つことになる。
【００６５】
例えば、ネットワークにわたるパスと、デフォルトパスと、アクティブ論理パスと、アクティブ論理パスに関連した経路選択目標とを比較することによって、アクティブ論理パスに関連した経路選択目標に適合する代替論理パスの集合を生成することができる。図１を参照すると（また、この例では、単純化のため、ＩＧＰパス・コストが通過するルータ数に類似しており、全てのリンクの最大キャパシティが等しいものと仮定すると）、アプリケーションは、ルータ１０からルータ１２へのデフォルトパスがルータ１８を経由することを確認する。アクティブＭＰＬＳ  ＬＳＰが、リンク最大キャパシティの７５％を活用するまで、予約帯域幅が等しいことを必要とするルータ１０と１８との間で発見される。このＬＳＰは、ＡＳ２へのコネクションのために保証された帯域幅レベルを必要とするＡＳ３のマネージャの要求に従って導入される。別の目的に利用されている第２のパスが、ルータ１４と１６を経由したルータ１０と１２の間において発見されるが、このパスは、それらのリンクにおける帯域幅の２０％を必要とする。アプリケーションは、第１のＬＳＰがデフォルトパス上にあり、第１及び第２のＬＳＰの組み合わせ負荷が、利用可能な最大キャパシティを超える値と等しくはならないことを確認する。従って、アプリケーションの推奨するところによれば、第１のＬＳＰの代替パスは、ルータ１８を通るデフォルトパスではなく、ルータ１４及びルータ１６を経由するパスということになる。
【００６６】
例えば、リンク障害による内部中継ネットワークの損失によって生じる、ＬＳＰに外部から加えられる変化を知らせるメカニズムの活用は、ＬＳＰの変化をすぐに警告することによって、オペレータがこうした障害の影響を軽減するのに役立つ可能性がある。ルータがフィードバックを行えるようにするこうしたメカニズムの１つに、ＳＮＭＰトラップ・メカニズムがある。ＳＮＭＰトラップは、いったん設定されると、外部から加えられる目標ＭＩＢデータの変化を知らせることになる。次に、もう一度、変化したトポロジに対して、新しいＬＳＰ、または、ＬＳＰの特性に対する変化をオーバレイし、ＬＳＰ挙動のリアルタイムに近いフィードバックを行えるようにすることができる。
【００６７】
プローブ４０によって得られる注釈付きトポロジは、従って、上述のものを含むさまざまなネットワーク管理タスクにおいてオペレータを助けることができる。解説のプロセスは、制限するわけではないが、差別化サービスや仮想私設ネットワーク（ＶＰＮ）やＩＰ上での音声通信やＳＬＡやＱｏＳメカニズム等の典型的な最小コスト経路選択の代替方法として、入口ルータ及び出口ルータにおけるパケット分類による個別論理パスの経路選択を用いる、他の形態のトラフィック管理及び他のテクノロジにも適用することができる。
【図面の簡単な説明】
【００６８】
【図１】インターネットの概念的断片を示す図である。
【図２】例証となるネットワーク・トポロジ記述を示す図である。
【図３】ＯＳＰＦプロトコルに規定されたリンク状態公示のフォーマットを示す図である。
【図４】ＯＳＰＦプロトコルに規定されたリンク状態公示のフォーマットを示す図である。
【図５】ＯＳＰＦプロトコルに規定されたリンク状態公示のフォーマットを示す図である。
【図６】ＯＳＰＦプロトコルに規定されたリンク状態公示のフォーマットを示す図である。
【図７】ＯＳＰＦプロトコルに規定されたリンク状態公示のフォーマットを示す図である。
【図８】ネットワーク・トポロジ記述を導き出すための手順を示す図である。
【図９】ネットワーク・トポロジ記述を導き出すための手順を示す図である。
【図１０】ネットワーク・トポロジ記述を導き出すための手順を示す図である。
【図１１】ネットワーク・トポロジ記述を導き出すための手順を示す図である。
【図１２】ネットワーク・トポロジ記述を導き出すための手順を示す図である。
【図１３】ネットワーク・トポロジ記述を導き出すための手順を示す図である。
【図１４】その内部の２つのルータの故障後における、図１の概念的断片を示す図である。
【符号の説明】
【００６９】
１０、１２、１４、１６、１８、２０、２２、２４、３０  ルータ
４０  プローブ
【図１】
2005535174.tif 000003
【図２】
2005535174.tif 000004
【図３】
2005535174.tif 000005
【図４】
2005535174.tif 000006
【図５】
2005535174.tif 000007
【図６】
2005535174.tif 000008
【図７】
2005535174.tif 000009
【図８】
2005535174.tif 000010
【図９】
2005535174.tif 000011
【図１０】
2005535174.tif 000012
【図１１】
2005535174.tif 000013
【図１２】
2005535174.tif 000014
【図１３】
2005535174.tif 000015
【図１４】
2005535174.tif 000016
【国際調査報告】
2005535174.tif 000017
2005535174.tif 000018
2005535174.tif 000019