(57)【要約】【課題】ネットワークにおける一部のアドレスの到達可能性情報を完全に詳細に通知し、他のアドレスの到達可能性情報を効率的に要約することを可能にする方法。【解決手段】本発明は、論理ノードによって表されるノードのグループメンバーの到達可能性情報を通知するために、論理ノードによって使用される処理の一部として実装される。一実施形態では、あるアドレスに関して、ほかの場合なら要約アドレス情報に含められるはずの詳細な到達可能アドレス情報が通知されることを可能にする「例外」命令を提供する。「例外」アドレスと共通接頭部を共有するアドレスに対して到達可能アドレス情報を要約しながら、特定のアドレスに関して詳細な到達可能性情報が通知されることを可能にする。そうすることによって、必要な場合には詳細情報が通知され、詳細情報が必要でない場合には要約アドレス情報が通知されることを可能にして、ネットワーク帯域幅を節約する。【選択図】      図７
2004282699.tif 000002
【特許請求の範囲】
【請求項１】
第１の要約アドレス接頭部を指定する第１の要約アドレス項目を提供するステップと、
前記第１の要約アドレス接頭部と合致する到達可能アドレスの要約されていない到達可能アドレス情報を伝播するステップとを含む、ネットワークにおける到達可能アドレス情報を通知する方法。
【請求項２】
前記ネットワークがＰＮＮＩネットワークを含む請求項１に記載の方法。
【請求項３】
前記ネットワークがＩＰネットワークを含む請求項１に記載の方法。
【請求項４】
前記第１の要約アドレス項目が例外要約アドレスを含む請求項１に記載の方法。
【請求項５】
前記到達可能アドレス情報が到達可能アドレスおよび関連するパラメータを含む請求項４に記載の方法。
【請求項６】
前記パラメータが適用範囲パラメータを含む請求項５に記載の方法。
【請求項７】
前記パラメータが管理上の重みパラメータを含む請求項５に記載の方法。
【請求項８】
前記パラメータが帯域幅パラメータを含む請求項５に記載の方法。
【請求項９】
ネットワークにおける到達可能アドレス情報を通知する方法であって、
それぞれが要約アドレス接頭部を指定する複数の要約アドレス項目を提供するステップと、
優先度に従って、前記要約アドレス接頭部と合致する到達可能アドレスを判定するステップと、
第１の優先度を有する要約アドレス接頭部と合致する到達可能アドレスの到達可能アドレス情報を伝播するステップと、
第２の優先度を有する要約アドレス接頭部とは合致するが、前記第１の優先度を有する前記要約アドレス接頭部とは合致しない到達可能アドレスの到達可能アドレス情報を要約するステップとを含む方法。
【請求項１０】
前記ネットワークがＰＮＮＩネットワークを含む請求項９に記載の方法。
【請求項１１】
前記第１の優先度を有する前記要約アドレス接頭部が前記第２の優先度を有する前記要約アドレス接頭部よりも長い接頭部を有する請求項９に記載の方法。
【請求項１２】
前記第１の優先度を有する前記要約アドレス接頭部が例外要約アドレス接頭部を含む請求項９に記載の方法。
【請求項１３】
前記ネットワークがＩＰネットワークを含む請求項９に記載の方法。
【請求項１４】
前記到達可能アドレス情報が到達可能アドレスおよび関連するパラメータを含む請求項９に記載の方法。
【請求項１５】
前記パラメータが適用範囲パラメータを含む請求項１４に記載の方法。
【請求項１６】
前記パラメータが管理上の重みパラメータを含む請求項１４に記載の方法。
【請求項１７】
前記パラメータが帯域幅パラメータを含む請求項１４に記載の方法。
【請求項１８】
ネットワークにおける到達可能アドレス情報を通知する方法であって、
第１のピアグループに属する第１のノードを、例外要約アドレス項目を含む第１の要約アドレス項目付きで構成するステップと、
前記例外要約アドレス項目と合致する第１の複数の到達可能アドレスの到達可能アドレス情報を、前記第１のピアグループのメンバーに通知するステップとを含む方法。
【請求項１９】
前記第１のピアグループに属する前記第１のノードを、要約する要約アドレス項目を含む第２の要約アドレス項目付きで構成するステップと、
前記要約する要約アドレス項目とは合致するが前記例外要約アドレス項目とは合致しない第２の複数の到達可能アドレスの到達可能アドレス情報を要約するステップとをさらに含む、請求項１８に記載の方法。
【請求項２０】
前記ネットワークがＰＮＮＩネットワークを含む請求項１８に記載の方法。
【請求項２１】
前記ネットワークがＩＰネットワークを含む請求項２０に記載の方法。
【請求項２２】
前記到達可能アドレス情報が到達可能アドレスおよび関連するパラメータを含む請求項１８に記載の方法。
【請求項２３】
前記パラメータが適用範囲パラメータを含む請求項２２に記載の方法。
【請求項２４】
前記パラメータが管理上の重みパラメータを含む請求項２２に記載の方法。
【請求項２５】
前記パラメータが帯域幅パラメータを含む請求項２２に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ通信ネットワークの分野に関し、より詳細には、ネットワークにおける到達可能アドレス情報を通知する方法に関する。
【背景技術】
【０００２】
交換システム（「交換ネットワーク」とも呼ばれる）は、データ通信ネットワークを介して、その間でデータを経路指定する。交換システムは、通常、データ通信ネットワークの要素の間のデータ通信経路を提供する、複数のスイッチおよびスイッチ群（「ノード」）を備える。
【０００３】
交換ネットワークの「接続形態（ｔｏｐｏｌｏｇｙ）」とは、交換ネットワークのノードの特定の配置および（物理的ならびに論理的両方の）相互接続を指す。交換ネットワークの接続形態についての知識を利用して、ネットワークを介した通信経路が計算される。
【０００４】
少数の別個のスイッチを備える交換システムの場合、接続形態はかなり単純であり、システム内の個々のノードとその間の通信リンクを識別することによって表すことができる。しかし、より大規模で複雑なネットワークの場合、ネットワークのすべてのノードの間のすべてのリンクを識別するのに必要なデータ量は、非常に多くなり得る。
【０００５】
複雑な交換ネットワークの接続形態を表すのに必要な情報量を削減するために、いくつかの手法が提案されてきた。１つの手法として、グループ内の個別ノードの特性を集約した特性を有する個別の論理ノード（「論理グループノード」）とみなされるグループ（「ピアグループ」）に、物理ノードをグループ化するものがある。このような論理グループノードは、さらに、他の物理ノードおよび／または論理ノードとグループ化して、次々に高いレベルのピアグループを形成し、それによって、ピアグループおよび論理グループノードの階層を作成することができる。
【０００６】
ＰＮＮＩプロトコル
ノードの論理グループからなるレベルに物理ノードをグループ化することを可能にするネットワークの一例は、「ＰＮＮＩ」ネットワークである。ＰＮＮＩとは、「専用ネットワークノードインターフェース（Ｐｒｉｖａｔｅ  Ｎｅｔｗｏｒｋ  Ｎｏｄｅ  Ｉｎｔｅｒｆａｃｅ）」または「専用ネットワーク間インターフェース（Ｐｒｉｖａｔｅ  Ｎｅｔｗｏｒｋ  Ｎｅｔｗｏｒｋ  Ｉｎｔｅｒｆａｃｅ）」を表し、ＡＴＭフォーラムによって開発されたプロトコルである。ＰＮＮＩプロトコルは、専用ＡＴＭ交換ネットワーク内でスイッチおよびスイッチ群の間の接続形態情報を分散させるために使用される。ＰＮＮＩプロトコルの詳細は、ＡＴＭフォーラムのウェブサイトｗｗｗ．ａｔｍｆｏｒｕｍ．ｃｏｍで入手可能な、「Ｐｒｉｖａｔｅ  Ｎｅｔｗｏｒｋ  Ｎｅｔｗｏｒｋ  Ｉｎｔｅｒｆａｃｅ  Ｓｐｅｃｉｆｉｃａｔｉｏｎ  Ｖｅｒｓｉｏｎ  １．１（ＰＮＮＩ  １．１）」、ｐｕｂｌｉｃａｔｉｏｎ  Ｎｏ．ａｆ−ｐｎｎｉ−００５５．００２など、ＡＴＭフォーラムから発行された様々な刊行物に出ている。
【０００７】
「ＰＮＮＩネットワーク」は、ＰＮＮＩプロトコルを利用するネットワークである。ＰＮＮＩネットワークのいくつかの基本的な特徴を、以下で説明する。ただし、これらの特徴は、ＰＮＮＩネットワークに限られたものではないことに留意されたい。同じまたは類似の特徴が、他のおよび／または追加のプロトコルを使用したネットワークでも利用される。
【０００８】
物理ノード
図１は、２６個の物理ノード（「最下位レベルのノード」とも呼ばれる）１０５ａ〜ｚを備える、一例としてのネットワーク１００を示す。ノード１０５ａ〜ｚは、３３本の双方向通信リンク１１０ａ〜ｇｇによって相互接続される。
【０００９】
ネットワーク１００は比較的小さいが、その接続形態を識別するのはかなり複雑である。このような識別方法の１つは、各ノードが送信ノードならびにそのノードにリンクされるもう一方のノードを識別するメッセージを周期的に同報通信する（ｂｒｏａｄｃａｓｔ）ことによるものである。たとえば、図１のネットワーク１００では、ノード１０５ａは、「こちらはノード１０５ａであり、ノード１０５ｂおよび１０５ｘに到達することができる」と知らせるメッセージを同報通信する。同様に、ノード１０５ｘは、「こちらはノード１０５ｘであり、ノード１０５ａ、１０５ｗ、１０５ｙ、１０５ｚに到達することができる」と同報通信する。ネットワーク１００の他の２４個のノードもそれぞれ、同様のメッセージを同報通信する。各ノード１０５ａ〜ｚは、他のすべてのノードのメッセージをすべて受信し、その情報をメモリに格納し、そのノードから別のノードにデータを送信する際の経路決定にその情報を使用する。
【００１０】
他のすべてのノードにその個々の接続情報を同報通信する各ノードにより、ネットワーク内の各ノードはネットワークの全体的な接続形態を推論することが可能になるが、このような大規模な同報通信は、特に大規模なネットワークにおいて、かなりの量のネットワーク帯域幅を消費する。ＰＮＮＩネットワークなどのネットワークは、「ピアグループ」と呼ばれるノードグループの階層にノードをグループ化することによって、こうしたオーバーヘッドを削減する。
【００１１】
ピアグループおよび論理ノード
ＰＮＮＩおよび他のネットワークにおいて重要な概念は、「論理ノード」である。論理ノードは、階層中のそのレベルで単一のノードとみなされるが、（最も低い階層レベルまたは単一のメンバーグループの場合は）単一の物理ノードを、または（より高い階層レベルでは）一群の物理ノードを表すこともできる。簡潔にするために、本明細書では、論理ノードを単に「ノード」と呼ぶこともある。ＰＮＮＩネットワークにおいて、論理ノードは、「論理ノードＩＤ」によって一義的に識別される。
【００１２】
ピアグループ（「ＰＧ」）は、論理ノードの集合体であり、そのそれぞれがグループの他のメンバーと情報を交換し、したがってすべてのメンバーがグループを全く同じように見ることができる。論理ノードは、ある特定のピアグループの「ピアグループＩＤ」付きで構成されることによって、そのピアグループに割り当てられる。ピアグループＩＤは、個々の物理ノードが構成される時点で指定される。隣接ノードは、「ハローパケット（Ｈｅｌｌｏ  ｐａｃｋｅｔｓ）」を使ってピアグループＩＤを交換する。ピアグループＩＤが同じであれば、同じピアグループに属する。
【００１３】
ＰＮＮＩ階層を構成するには、始めに、ネットワークの物理ノード（「最下位レベルの」ノードとも呼ばれる）をピアグループの第１レベルに編成する。図２は、７個のピアグループ２０５ａ〜ｇに編成された、図１のネットワーク１００を示す。図２で、ピアグループ２０５ａは、ピアグループ「Ａ．１」で示される。同様に、ピアグループ２０５ｂ〜ｇは、それぞれ、ピアグループ「Ａ．２」、「Ａ．３」、「Ａ．４」、「Ｂ．１」、「Ｂ．２」および「Ｃ」で示される。本明細書では、ピアグループを文字「ＰＧ」とそれに続くピアグループ番号で呼ぶこともある。たとえば、「ＰＧ（Ａ．２）」は、ピアグループＡ．２  ２０５ｂを指す。Ａ．３．２およびＡ．３などのノードおよびピアグループの番号付けは、ノードとピアグループの間の関係の説明の助けとして用いられる抽象表現である。たとえば、ノード１０５ｌを「Ａ．３．２」で示すことにより、そのノードがピアグループＡ．３  ２０５ｃに配置されていることを示す。
【００１４】
論理リンク
ＰＮＮＩプロトコルの下では、論理ノードは「論理リンク」によって接続される。最下位レベルのノードの間では、論理リンクは、物理リンク（図１のリンク１１０ａ〜ｇｇなど）、または２つの最下位レベルノードの間の仮想専用チャネル（「ＶＰＣ」）のいずれかである。ピアグループの中の論理リンクを「水平リンク」と呼び、２つのピアグループを接続するリンクを「外部リンク」と呼ぶこともある。
【００１５】
ＰＮＮＩでの情報交換
ＰＮＮＩネットワーク内の各ノードは、そのすぐ隣のノードとハローパケットを交換し、それによってそのノードのローカルな状態情報を決定する。この状態情報には、ノードのすぐ隣のノードの識別ならびにピアグループへの帰属関係、および隣のノードとのリンク状況が含まれる。各ノードは、その状態情報を「ＰＮＮＩ接続形態状態要素」（ＰＴＳＥ）にバンドルし、この要素はピアグループ中に同報通信（「フラッド」）される。ノードの接続形態データベースは、受信したすべてのＰＴＳＥの集合体から構成され、ＰＴＳＥは全体として、そのノードから見たＰＮＮＩの経路選択領域の現在の状態を表す。接続形態データベースは、所与のノードから、経路選択領域内でまたはそれを介して到達可能な任意のアドレスへの経路を計算するのに必要な情報を提供する。
【００１６】
ノード情報
どのノードも、それ自体の識別と能力、ピアグループリーダを選出するのに使用される情報、ならびにＰＮＮＩ階層を確立するのに使用される情報を記述するＰＴＳＥを生成する。これは、ノード情報と呼ばれる。ノード情報は、接続形態状態情報および到達可能性情報を含む。
【００１７】
接続形態状態情報は、論理リンクの特性を記述する「リンク状態パラメータ」、およびノードの特性を記述する「ノード状態パラメータ」を含む。到達可能性情報は、ある特定のノードを介して呼出しが経路指定される宛先を記述するアドレスおよびアドレス接頭部から構成される。
【００１８】
初期接続形態データベースの交換
ハローを交換することによって初期化されている隣接ノード同士が、それらが互いに同じピアグループであると結論すると、これらのノードは、続いて互いの「接続形態データベース」を同期させる。データベースの同期とは、隣接ノードの間での情報の交換であり、その結果、２つのノードが、同一の接続形態データベースを有するようになる。接続形態データベースには、ピアグループに関する詳細な接続形態情報が含まれ、その中には、論理ノードに加えてＰＮＮＩ経路選択領域のそれ以外の部分を表すより抽象的な接続形態情報がある。
【００１９】
フラッディング
「フラッディング」とは、ピアグループ中におけるＰＴＳＥの確実なホップごとの伝播である。フラッディングにより、ピアグループ中の各ノードが同一の接続形態データベースを確実に維持するようになる。フラッディングは、継続して行われる活動である。
【００２０】
ピアグループリーダ
ピアグループは、すぐ上の階層レベルにおいて、「論理グループノード」すなわち「ＬＧＮ」と呼ばれる単一のノードとして表される。論理グループノードの役割を実施するのに必要な機能は、「ピアグループリーダ」と呼ばれるピアグループのノードによって実行される。ピアグループごとに、多くても１つの（より正確には、分割されたピアグループの場合には、区分ごとに多くても１つの）アクティブなピアグループリーダ（ＰＧＬ）が存在する。ただし、ピアグループリーダの機能は、別のときに別のノードが実施することもできる。
【００２１】
どの時点でもピアグループリーダとして機能する特定のノードが、「ピアグループリーダ選出」処理によって決定される。ピアグループリーダの選出基準は、構成時に各物理ノードに割り当てられるパラメータである、ノードの「リーダシップ優先度」である。ピアグループにおいてリーダシップ優先度が最も高いノードが、そのピアグループのリーダになる。選出処理は、絶えず実行されるプロトコルである。現在のＰＧＬよりも高いリーダシップ優先度をもつノードがアクティブになると、選出処理によって、ピアグループのリーダシップが、新規にアクティブになったノードに移される。ＰＧＬが削除されまたは障害を起こすと、次にリーダシップ優先度が高いノードがＰＧＬになる。
【００２２】
図２のネットワークでは、現在のＰＧＬを黒丸で示してある。すなわち、ノードＡ．１．３  １０５ａはピアグループＡ．１  ２０５ａのピアグループリーダであり、ノードＡ．２．３  １０５ｘはＰＧ  Ａ．２  ２０５ｂのＰＧＬであり、ノードＡ．４．１  １０５ｆはＰＧ  Ａ．４  ２０５ｄのＰＧＬであり、ノードＡ．３．２  １０５ｌはＰＧ  Ａ．３  ２０５ｃのＰＧＬであり、ノードＢ．１．１  １０５ｏはＰＧ  Ｂ．１  ２０５ｅのＰＧＬであり、ノードＢ．２．３  １０５ｑはＰＧ  Ｂ．２  ２０５ｆのＰＧＬであり、ノードＣ．２  １０５ｖはＰＧ  Ｃ  ２０５ｇのＰＧＬである。
【００２３】
１つ上の階層レベル
ピアグループの論理グループノードは、すぐ上の（「親」）階層レベルにおいて、そのピアグループを、単一の論理ノードとして表す。図３は、１つ上の階層レベルにおいて、ピアグループ２０５ａ〜ｇがそれぞれのＬＧＮによってどのように表されるかを示す。図３では、ＰＧ（Ａ．１）２０５ａは論理グループノードＡ．１  ３０５ａで表され、ＰＧ（Ａ．２）２０５ｂは論理グループノードＡ．２  ３０５ｂで表され、ＰＧ（Ａ．３）２０５ｃは論理グループノードＡ．３  ３０５ｃで表され、ＰＧ（Ａ．４）２０５ｄは論理グループノードＡ．４  ３０５ｄで表され、ＰＧ（Ｂ．１）２０５ｅは論理グループノードＢ．１  ３０５ｅで表され、ＰＧ（Ｂ．２）２０５ｆは論理グループノードＢ．２  ３０５ｆで表され、ＰＧ（Ｃ）２０５ｇは論理グループノードＣ  ３０５ｇで表される。ピアグループおよび論理グループノードを使用することにより、図１の２６個の物理ノード１０５ａ〜ｚを図３の７個の論理ノード３０５ａ〜ｇで表すことができる。
【００２４】
図３の論理ノード３０５ａ〜ｇは、それ自体をさらにピアグループにグループ化することができる。図４は、図３では論理グループノード３０５ａ〜ｆで表してある図２のピアグループ２０５ａ〜ｆを、１つ上のレベルのピアグループ階層に編成する一方法を示す。同じレベルにあるすべてのピアグループを、１つ上のレベルの論理グループノードで表す必要はないことに留意されたい。
【００２５】
図４では、ピアグループＡ．１  ２０５ａ、Ａ．２  ２０５ｂ、Ａ．３  ２０５ｃ、およびＡ．４  ２０５ｄが、ピアグループＡ  ４１０ａにグループ化され、ピアグループＢ．１  ２０５ｅおよびＢ．２  ２０５ｆがピアグループＢ  ４１０ｂにグループ化されている。ピアグループＣ  ２０５ｇは、このレベルの論理グループノードでは表されない。ピアグループＡ  ４１０ａは、ピアグループＡ．１  ２０５ａ、Ａ．２  ２０５ｂ、Ａ．３  ２０５ｃおよびＡ．４  ２０５ｄの「親ピアグループ」と呼ばれる。反対に、ピアグループＡ．１  ２０５ａ、Ａ．２  ２０５ｂ、Ａ．３  ２０５ｃおよびＡ．４  ２０５ｄは、ピアグループＡ  ４１０ａの「子ピアグループ」と呼ばれる。
【００２６】
親ピアグループは、子ピアグループＩＤよりも短いピアグループＩＤによって識別される。ピアグループリーダになることができるどのノードも、その親ピアグループＩＤをもって構成されるべきである。ピアグループＩＤの長さは、ＰＮＮＩ階層におけるそのピアグループのレベルを示す。
【００２７】
論理グループノードの機能
論理グループノードの機能は、論理グループノードで表されるピアグループのピアグループリーダによって実行される。こうした機能には、その子ピアグループに関する情報を集約し要約し、その情報をそれ自体のピアグループにフラッディングすることなどがある。論理グループノードも、そのピアグループから受信した情報を、フラッディングのためにその子ピアグループのＰＧＬに渡す。さらに、論理グループノードは、それ自体のピアグループの潜在的なピアグループリーダになることができる。その場合、その論理グループノードは、より高い１つまたは複数のレベルでも論理グループノードとして機能することができるように構成されるべきである。
【００２８】
ピアグループをより高い階層レベルで表す方法は、ピアグループリーダのポリシーおよびアルゴリズムに依存し、これらは、ピアグループリーダとして機能する物理ノードの構成によって決まる。ピアグループが整合的な方法で表されるようにするためには、潜在的なピアグループリーダであるすべての物理ノードが整合的に構成されていなければならない。ただし、物理ノードが異なる機能能力をもつ場合は、いくつかの変形形態もあり得る。
【００２９】
ピアグループは、各階層レベルで同じように機能する。したがって、図４のより高レベルのピアグループ４１０ａ〜ｂは、より低レベルのピアグループ２０５ａ〜ｇと同じように、ピアグループである。唯一の違いは、ノードがそれぞれ、物理ノードではなく、別個のより低レベルのピアグループを表すことである。ピアグループ２０５ａ〜ｇと同様、ピアグループＡ  ４１０ａには、より低レベルのピアグループ２０５ａ〜ｇのリーダを選出するのに使用されたのと同じリーダ選出処理で選ばれたピアグループリーダ（論理グループノードＡ．２  ３０５ｂ）が存在する。論理グループノードＡ．２  ３０５ｂがＰＧ  Ａ  ４１０ａのピアグループリーダとして機能できるためには、（ピアグループＡ．２  ２０５ｂの現在のピアグループリーダである）最も低レベルの物理ノードＡ．２．３  １０５ｘの上に実装される論理ノードＡ．２  ３０５ｂに、Ａのピアグループリーダを定義する機能が提供されるべきであることに留意されたい。したがって、物理ノードＡ．２．３  １０５ｘは、ピアグループＡ．２  ２０５ｂのピアグループリーダとしてだけではなく、ピアグループＡ  ４１０ａのピアグループリーダとしても機能するように構成されるべきである。ピアグループＡ．２  ２０５ｂの他のどの潜在的ピアグループリーダについても同じである。さらに、ピアグループＡ  ４１０ａの他のノードが潜在的ピアグループリーダである場合（これが通常のケースである）、その子ピアグループの潜在的ピアグループリーダであるすべての物理ノードは、ピアグループＡ  ４１０ａのピアグループリーダとしても機能するように構成されるべきである。
【００３０】
最上位レベルのピアグループへの進歩
ＰＮＮＩ階層は、ネットワーク全体が１つの最上位レベルのピアグループに包含されるまでは、不完全である。図４の例では、それぞれピアグループＡ  ４１０ａ、Ｂ  ４１０ｂ、Ｃ  ２０５ｇを表す論理グループノードＡ  ４２０ａ、Ｂ  ４２０ｂ、Ｃ  ４２０ｃを含むもう１つのピアグループ４３０を構成することによって、階層が完成する。別の可能な構成として、ピアグループＢ  ４２０ｂおよびＣ  ２０５ｇがピアグループＢＣに集約され、次いで、ピアグループＡ  ４２０ａと集約されて最上位レベルのピアグループを形成するものがある。ネットワーク設計者は、論理ノードおよびピアグループを定義する構成パラメータによって、階層を制御する。
【００３１】
ＰＮＮＩネットワークの階層構造は、非常に柔軟である。連続する子／親関係のピアグループに対する上限は、最長１３オクテットのアドレス接頭部から導出することができる次第に短くなっていくアドレス接頭部の最大数によって与えられる。この値は１０４と同等であり、ほとんどのネットワークに適合する。というのは、国際的なネットワークでさえも、通常は１０未満のレベルの系統で、十分以上に構成することができるからである。
【００３２】
階層における再帰
ＰＮＮＩ経路指定階層の作成を、最低レベルのノードからなるネットワークで始まり、ＰＮＮＩ経路選択領域全体を包含する１つの最上位レベルのピアグループで終わるピアグループの再帰的な生成とみなすことができる。この階層構造は、ピアグループＩＤが、物理ノードの構成を介して論理グループノードにどのように関連づけられるかによって、決定される。
【００３３】
一般に、ピアグループの動作は、そのレベルには依存しない。しかし、最上位レベルのピアグループは、ピアグループリーダを必要としないという点で異なっている。というのは、ピアグループリーダによって表される必要のある親ピアグループがないからである。
【００３４】
アドレスの要約および到達可能性
アドレスの要約により、ＰＮＮＩネットワーク内に分散される必要があるアドレス指定情報の量が削減される。アドレスの要約は、１つの「到達可能アドレス接頭部」を使ってエンドシステムおよび／または所与の接頭部で始まるノードアドレスの集合体を表すことによって、達成される。到達可能アドレス接頭部は、要約アドレスでも、外来アドレスでもよい。
【００３５】
ノードに関連づけられた「要約アドレス」とは、そのノードで明示的に構成されるか、または何らかのデフォルト値をとるアドレス接頭部である。要約アドレスは、「内部」および「外側」到達可能性クラスに分類することができる。「内側」要約アドレスとは、ネットワーク内部の到達可能アドレスに関する要約アドレスである。「外側」要約アドレスとは、ネットワーク外部の到達可能アドレスに関する要約アドレスである。
【００３６】
ノードに関連づけられた「外来アドレス」とは、そのノードの要約アドレスのどれとも合致しないアドレスである。それとは対照的に、「在来アドレス」とは、ノードの要約アドレスの１つと合致するアドレスである。
【００３７】
こうした概念は、図４から導出された図５に示す例で明らかになる。ノードＡ．２．１、Ａ．２．２およびＡ．２．３に取り付けられた５０５ａ〜ｍは、エンドシステムを表す。各エンドシステムに関連づけられた英数字は、そのエンドシステムのＡＴＭアドレスを表す。たとえば、エンドシステム５０５ｂに関連づけられた＜Ａ．２．３．２＞は、ＡＴＭアドレスを表し、Ｐ＜Ａ．２．３＞、Ｐ＜Ａ．２＞、およびＰ＜Ａ＞は、それと同じＡＴＭアドレスの、次第に短くなっていく接頭部を表す。
【００３８】
図５のピアグループＡ．２内の各ノードに対して使うことができる要約アドレス情報の一例を、表１に示す。
【表１】
2004282699.tif 000003
【００３９】
表１の要約アドレス情報は、各ノードがそのノードを介して到達可能な他のノードにアドレス情報をどのように通知すべきかを示す命令を表す。たとえば、表１の第１列は、ノードＡ．２．１が、接頭部「Ａ．２．１」で始まるどのアドレスも、１つの要約されたアドレスとして通知すべきであることを示す。接頭部「Ｙ．２」で始まるどのアドレスについても同じである。
【００４０】
要約アドレスリストの作成は、ＰＮＮＩプロトコルでは規定されておらず、ネットワーク管理者の選択に関する問題である。たとえば、ノードＡ．２．２で、要約アドレスＰ＜Ｙ．１．１＞をＰ＜Ｙ．１＞の代わりに使用することもでき、またはノードＡ．２．１で、Ｐ＜Ｗ＞を含めることもできる。しかし、ノードＡ．２．１およびＡ．２．３で、Ｐ＜Ａ．２＞を、要約アドレスとして、（Ｐ＜Ａ．２．１＞またはＰ＜Ａ．２．３＞の代わりに）選ぶことはできない。というのは、経路を選択する遠隔ノードは、Ａ．２．３に接続されたエンドシステムとＡ．２．１に接続されたエンドシステム（どちらも、接頭部Ａ．２を有するエンドシステムを含む）とを区別することができないからである。Ａ．２．１で選ばれた要約アドレスリストでは、Ｐ＜Ｗ．２．１．１＞は、ノードＡ．２．１の要約アドレスのどれとも合致しないので、外来アドレスである。
【００４１】
階層の次のレベルに上がると、論理グループノードＡ．２は、要約アドレスのそれ自体のリストを必要とする。この場合も、選ばれ得る様々な選択肢がある。ＰＧ（Ａ．２）はピアグループＡ．２のＩＤなので、Ｐ＜Ａ．２＞を要約アドレスリストに含めることが合理的である（いくつかの実施形態では、ＬＧＮのピアグループＩＤを、ＬＧＮの要約アドレスリストにデフォルトとして含める）。さらに、要約アドレスＰ＜Ｙ．１＞およびＰ＜Ｙ．２＞はさらにＰ＜Ｙ＞で要約することができるので、Ｐ＜Ｙ＞を要約アドレスとして構成することにも意味がある。その結果得られる、論理グループノードＡ．２の要約アドレスリストを、表２に示す。
【表２】
2004282699.tif 000004
【００４２】
表３は、表１の要約アドレスリストに従って、ピアグループＡ．２内の各ノードによって通知される到達可能アドレスの接頭部を示す。ノードは、その要約アドレスリストにある要約アドレスと、そのノードを介して到達可能な外来アドレス（すなわち、要約アドレスリストに要約されていないアドレス）とを通知する。
【表３】
2004282699.tif 000005
【００４３】
表３の例において、ノードＡ．２．１は、ノードの要約アドレスに加えて外来アドレスをフラッドするが、ノードＡ．２．２およびＡ．２．３は、外来アドレスに指定されたエンドシステムをもたないので、ノードの要約アドレスを発行するだけである。
【００４４】
到達可能性情報、すなわち到達可能アドレス接頭部（および外来アドレス）は、ＰＮＮＩ経路指定階層の至る所に供給され、それによって、すべてのノードが、これらの接頭部で要約されたアドレスを有するエンドシステムに到達することができるようになる。ネットワークの拡張性を高めるために、さらに要約することを可能にするフィルタリングは、こうした情報の流れに関連する。たとえば、ノードＡ．２．２から発行された到達可能アドレス接頭部Ｐ＜Ｙ．１＞と、ノードＡ．２．１から発行されたＰ＜Ｙ．２＞（表３を参照）とを、ＬＧＮ  Ａ．２が（ＰＧＬ  Ａ．２．３を介して）受信すると、その構成された要約アドレスＰ＜Ｙ＞と合致することに気がつく。ＬＧＮ  Ａ．２は、Ｐ＜Ｙ．１＞とＰ＜Ｙ．２＞を別々に通知するのではなく、その１つの要約アドレスＰ＜Ｙ＞を通知することによって、さらなる要約を達成する。
【００４５】
ＬＧＮによってそれ以上要約することができない到達可能アドレス接頭部は、変更されないままで通知される。たとえば、ＬＧＮ  Ａ．２がＡ．２．２から発行された到達可能アドレス接頭部Ｐ＜Ｚ．２＞を受信するとき、そのすべての構成された要約アドレス（表２）との合致が見られず、その結果、ＬＧＮ  Ａ．２は、Ｐ＜Ｚ．２＞を変更しないで通知する。Ｐ＜Ｚ．２＞がノードＡ．２．２から見た要約アドレスの１つであるとしても、そのすべての構成された要約アドレスとの合致が見られないので、ＬＧＮ  Ａ．２は、Ｐ＜Ｚ．２＞を外来アドレスとみなすことに留意されたい。その結果得られる、ＬＧＮ  Ａ．２によって通知される到達可能性情報を表４に示す。
【表４】
2004282699.tif 000006
【００４６】
ノードＡ．２．３がピアグループＡ．２のＰＧＬであるとしても、表３に示す、ノードＡ．２．３によって通知される到達可能性情報は、表４に示す、ＬＧＮ  Ａ．２によって通知されるものとは異なることに留意されたい。ＬＧＮ  Ａ．２によって通知される到達可能性情報は、ピアグループメンバー自体によって同報通信される到達可能性情報に関わらず、ピアグループの外部で利用可能な、ピアグループＡ．２についての到達可能性情報に過ぎない。
【００４７】
ＬＧＮ  ＡとピアグループリーダＡ．２の間の関係は、ＬＧＮ  Ａ．２とピアグループリーダＡ．２．３の間の関係と同様である。ＬＧＮ  Ａは、要約アドレスなしで構成される場合は、すべての到達可能アドレス接頭部を通知し、この接頭部は、ピアグループＡを超えて（表４のリスト全体を含む）最上位のピアグループにフラッドされる。一方、ＬＧＮ  Ａは、デフォルトの要約アドレスＰ＜Ａ＞（ピアグループＡのＩＤはＰＧ（Ａ）なのでデフォルトである）付きで構成される場合は、Ｐ＜Ａ＞で始まるあらゆる到達可能アドレス接頭部を、通知する前にさらに要約しようとする。たとえば、ＬＧＮ  Ａ．２によってフラッドされるアドレス接頭部Ｐ＜Ａ．２＞（表４を参照）ではなく、要約アドレスＰ＜Ａ＞を通知する。
【００４８】
論理ノードのＡＴＭアドレスは、エンドシステムのアドレスと同じ要約規則に従う。特定のＰＮＮＩノードから発行される到達可能性情報（到達可能アドレス接頭部）は、その上の（親）ピアグループ群に、次いでその下の（子）ピアグループ群に通知されて、最後には指定されたノードの外側にあるすべてのＰＮＮＩノードに到達する。
【００４９】
抑制要約アドレス
到達可能アドレス接頭部の分散を制限するために、到達可能性情報の通知と共に使用することができる別のフィルタ機構がある。この機構は、「抑制要約アドレス」をエンドシステム（群）のアドレス（群）に関連づけることを伴い、ＬＧＮが抑制要約アドレスを通知することを禁じる。この選択肢を用いると、より低レベルのピアグループに属するアドレスの一部を、より高レベルの階層、したがって他のピアグループから隠すことができる。この特徴は、安全性の理由で実装することができ、そうすると、ある特定のエンドシステムのアドレスの存在が、ある特定のピアグループの外には知られないようになる。
【００５０】
アドレス抑制は、ＬＧＮの要約アドレスリストに「抑制要約アドレス」を含めることによって、実装される。たとえば、図５では、安全性のために、ネットワーク管理者が、ノードＡ．２．１．２  ５０５ｊの到達可能性がＬＧＮ  Ａ．２．１  １０５ｙによって通知されるのを防止したいと望み、それでもノードＡ．２．１．１およびＡ．２．１．３の到達可能性は通知したいと思っていると仮定する。
【００５１】
表１に示すように、抑制される前のＬＧＮ  Ａ．２．１  １０５ｙの要約アドレスリストは、デフォルト接頭部Ｐ＜Ａ．２．１＞を含む。このことは、接頭部がＰ＜Ａ．２．１＞と合致するＬＧＮ  Ａ．２．１の子ピアグループにノードがある限り、ＬＧＮ  Ａ．２．１はＰ＜Ａ．２．１＞を到達可能アドレスとして通知することを意味する。
【００５２】
ノードＡ．２．１．２の到達可能性を抑制するために、ネットワーク管理者は、ＬＧＮ  Ａ．２．１の要約アドレスリストに、抑制要約アドレスとしてＰ＜Ａ．２．１＞を追加して、ＬＧＮ  Ａ．２．１が、接頭部Ｐ＜Ａ．２．１＞を有するその到達可能ノード（ノードＡ．２．１．１  ５０５ｉ、Ａ．２．１．２  ５０５ｊおよびＡ．２．１．３  ５０５ｋ）のどの到達可能性も通知しないようにさせることができる。Ｐ＜Ａ．２．１．２＞を抑制要約アドレスとして追加するだけでは十分ではないことに留意されたい。ノードＡ．２．１．１  ５０５ｉおよびＡ．２．１．３  ５０５ｋが存在すると、やはりＬＧＮ  Ａ．２．１はＰ＜Ａ．２．１＞の到達可能性を通知することになる。というのは、ノードＡ．２．１．２が抑制されても、抑制されていないノードがＬＧＮ  Ａ．２．１の要約アドレスＰ＜Ａ．２．１＞と合致し、それによって、要約アドレスＰ＜Ａ．２．１＞が通知されるからである。
【００５３】
抑制要約アドレスＰ＜Ａ．２．１＞をＬＧＮ  Ａ．２．１の要約アドレスリストに追加することによって、ノードＡ．２．１．２の到達可能性の通知を抑制するという目標は達成されるが、ノードＡ．２．１．１およびＡ．２．１．３の到達可能性の通知も抑制されるという、意図しない影響が生じる。ノードＡ．２．１．１およびＡ．２．１．３の到達可能性がＬＧＮ  Ａ．２．１によって通知されるようにするために、これらのアドレスを、ＬＧＮ  Ａ．２．１の要約アドレスリストに明示的に追加することができる。表５は、ノードＡ．２．１．２の到達可能性の抑制を追加する前と後の、ＬＧＮ  Ａ．２．１の要約アドレスリストを示す。
【表５】
2004282699.tif 000007
【００５４】
子ピアグループにある１つまたは複数のノードと接頭部が最も長く合致するエントリは、合致する接頭部がより短いエントリよりも優先度が高い。したがって、ＬＧＮの要約アドレスリストにある各要約アドレスは、一義的な接頭部をもたなければならない。たとえば、要約アドレスリストは、同じ接頭部を有する要約アドレスと抑制要約アドレスを含むことはできない。要約アドレスリスト中の２つのエントリに同じ接頭部を使用することができるのは、リストが「内部」および「外側」到達可能性クラスを使用する場合のみである。その場合、２つの要約アドレスは、同じ接頭部を有することができるが、そうできるのは、一方が「内部」要約アドレス、他方が「外側」要約アドレスと指定される場合のみである。ただし、各到達可能性クラス中の接頭部は、やはり一義的なものでなければならない。
【００５５】
表５で、Ｐ＜Ａ．２．１．１＞およびＰ＜Ａ．２．１．３＞の明示的なエントリは、Ｐ＜Ａ．２．１＞の抑制要約アドレスエントリよりも長い接頭部を有する。したがって、Ｐ＜Ａ．２．１．１＞およびＰ＜Ａ．２．１．３＞の明示的なエントリは、Ｐ＜Ａ．２．１＞の抑制要約アドレスエントリより優先度が高い。その結果得られる、ＬＧＮ  Ａ．２．１によって通知されるアドレスを、表６に示す。
【表６】
2004282699.tif 000008
【００５６】
アドレスの適用範囲
論理ノードによって通知される到達可能性情報は、ノードに関連づけられた適用範囲を常に有する。適用範囲は、ＰＮＮＩ経路指定階層中のあるレベルを示し、そのレベルは、このアドレスが通知または要約され得る最上位のレベルである。アドレスの適用範囲がノードのレベルよりも低いレベルを示す場合、そのノードはそのアドレスを通知しない。適用範囲がノードのレベルと等しいかそれよりも高いレベルを示す場合、そのアドレスは、ノードのピアグループの中で通知される。
【００５７】
アドレスを要約するとき、最も高い適用範囲をもって要約されるアドレスが、その要約アドレスの適用範囲を決定する。同じ規則がグループアドレスにも当てはまる。すなわち、あるピアグループ中の２つ以上のノードが、同じグループアドレスではあるが異なる適用範囲を有するものに到達可能性を通知する場合、その親ノードは、適用範囲が最も高いグループアドレスに到達可能性を通知する。
【００５８】
アドレス抑制に関する規則は、適用範囲に対する規則よりも優先されることに留意されたい。つまり、ＬＧＮの要約アドレスリストがアドレス抑制を含む場合、アドレスに関連づけられた適用範囲がＬＧＮのレベルより高くても、そのアドレスは通知されない。
【００５９】
到達可能性の要約の影響
要約アドレスを使用することによって、伝播する必要のあるアドレス情報の量は削減されるが、特定のアドレスに関する利用可能な詳細情報の量も削減される。要約されるアドレスのパラメータを集約することにより、特定のアドレスに関する詳細が要約されたアドレス情報の中に隠される。
【００６０】
【非特許文献１】ＡＴＭフォーラム、「Ｐｒｉｖａｔｅ  Ｎｅｔｗｏｒｋ  Ｎｅｔｗｏｒｋ  Ｉｎｔｅｒｆａｃｅ  Ｓｐｅｃｉｆｉｃａｔｉｏｎ  Ｖｅｒｓｉｏｎ  １．１（ＰＮＮＩ  １．１）」、ｐｕｂｌｉｃａｔｉｏｎ  Ｎｏ．ａｆ−ｐｎｎｉ−００５５．００２
【発明の開示】
【発明が解決しようとする課題】
【００６１】
しかし、ネットワーク管理者が、要約アドレスが構成された接頭部を有するある特定のノードの詳細な到達可能性情報の提供を望むことがある。たとえば、図５のノードＹ．１．１．３  ５０５ｆが、別個の通知を保証するメディアゲートウェイへの外部接続を有すると仮定する。ＰＮＮＩプロトコルの下では、共通接頭部を有するピアグループにある到達可能ノードのアドレスは、２通りの方法で通知することができる。すなわち、１）共通接頭部を有するすべてのノードの到達可能性情報を集約する要約アドレスによる方法、または２）共通接頭部を有する各ノードに対する別々の、明示的な通知による方法である。図５のノードＹ．１．１．３  ５０５ｆの到達可能性情報を別々に通知するためには、同じピアグループにある、同じ接頭部を共有するそれ以外のノード（すなわちノードＹ．１．１．１  ５０５ｄおよびＹ．１．１．２  ５０５ｅ）の到達可能性情報も、別々に明示的に通知しなければならない。これは、実際に必要とされるよりも詳細な到達可能性情報が同報通信されるので、ネットワーク帯域幅の非効率な使用を招く。
【課題を解決するための手段】
【００６２】
本発明は、ネットワーク内の一部のアドレスの到達可能性情報を完全に詳細に通知し、他のアドレスの到達可能性情報を効率的に要約することを可能にする方法を含む。一実施形態では、本発明は、論理ノードによって表されるノードのグループメンバーの到達可能性情報を通知するために、論理ノードによって使用される処理の一部として実装される。本発明は、ノードおよびノード要素（到達可能性情報など）を論理ノードに集約することに関与するどのネットワークでも使用することができる。たとえば、ＰＮＮＩおよびＩＰプロトコルを使用するネットワークなどがあるが、それに限定されるわけではない。
【００６３】
一実施形態では、本発明は、あるアドレスに関して、ほかの場合なら要約アドレス情報に含められるはずの詳細な到達可能アドレス情報が通知されることを可能にする「例外」命令を提供する。本発明は、「例外」アドレスと共通接頭部を共有するアドレスに対して到達可能アドレス情報を要約することを可能にしながら、特定のアドレスに関して詳細な到達可能性情報が通知されることも可能にする。本発明は、そうすることによって、必要な場合には詳細情報が通知されることを可能にし、このような詳細情報が必要でない場合には要約アドレス情報が通知されることも可能にして、ネットワーク帯域幅を節約する。
【発明を実施するための最良の形態】
【００６４】
ネットワークにおける到達可能アドレス情報を要約する方法が提示される。１つまたは複数の実施形態では、本発明は、ネットワークの物理ノードにおいて実行される処理によって使用される。本発明は、たとえば、アルカテルの５６２０ネットワーク管理システムなどのネットワーク管理システムと共に使用することができる。１つまたは複数の実施形態では、本発明は、交換システム、パーソナルコンピュータ、コンピュータワークステーションおよびまたは他の計算機プラットフォームで動作するソフトウェアプログラミングによって実装される。以下の説明では、本発明を完全に説明するために、数多くの具体的な詳細について述べる。ただし、本発明は、こうした具体的な詳細なしでも実施できることが当業者には明らかであろう。他の例では、本発明をわかりにくくしないように、よく知られている特徴については詳しくは説明しない。
【００６５】
本発明は、ネットワークの物理ノードが、多重レベル階層に配置された物理ノードのグループを表す論理ノードによって表されるネットワークで使用することができる。このようなネットワークの一例を、図１〜５に示す。図１〜５のネットワークの例では、ＰＮＮＩプロトコルを使用する。ただし、本発明は、ＩＰプロトコルなど、他のプロトコルを使用するネットワークにも等しく適用可能である。
【００６６】
一部のネットワークでは、ネットワークノードは、「ピアグループ」とも呼ばれるノードのグループに論理的に配置される。ピアグループは、すぐ上の階層レベルでは「論理グループノード」と呼ばれる１つの論理ノードとして表される。論理グループノードの機能は、その論理グループノードによって表されるピアグループのメンバーノードの１つによって、どの時点でも実施される。論理グループノード機能を実施するために、論理グループノードとして働く物理ノードは、論理グループノードとして機能するのに必要な処理を物理ノードが実行することを可能にさせるコンピュータプログラム命令を用いて提供される。
【００６７】
論理グループノード（「ＬＧＮ」）の機能の１つとして、到達可能性情報をその論理ノードのピアグループのメンバーに通知することがある。ＬＧＮによって通知される到達可能性情報は、ＬＧＮを介してそのＬＧＮの子ピアグループのメンバーを介して到達可能なネットワークアドレスを示す。到達可能性情報は、たとえば、適用範囲、帯域幅、および管理上の重みなど、通知されるアドレスのそれぞれに対するパラメータを含むこともできる。
【００６８】
ＬＧＮが到達可能性情報を通知することができる一方法は、その子ピアグループの各メンバーから到達可能性情報を受信し、それ自体のピアグループに同じ情報を単に通知するものである。このタイプの通知方式は、各到達可能アドレスの詳細な到達可能性情報を提供する。ただし、この方式は、多大な量の帯域幅を必要とし、利用可能なアドレス要約の効果を利用することができない。
【００６９】
図６は、本発明のアドレス要約処理の実施形態を実装する単純なネットワークの一例を示す。図６の例は、ＰＮＮＩプロトコルに従って実装されたネットワークを含む。ただし、本発明は、ＩＰプロトコルなど追加のおよび／または他のプロトコルを使用するネットワークでも使用することができる。
【００７０】
図６は、アドレス要約命令、およびその結果として３つのピアグループのメンバーによって行われる通知を示す。３つのグループとは、ピアグループ（「ＰＧ」）Ａ．１１１  ６１０、Ａ．１１  ６２０、およびＡ．１  ６３０であり、これらは、図６に示すネットワーク階層のレベル１２、８、４、をそれぞれ占有するように構成されている。ＰＮＮＩプロトコルでは、レベル番号が低いほど、階層レベルが高くなる。したがって、図６の３つのピアグループのうち、ピアグループＡ．１１１  ６１０が最下位レベルのピアグループであり、ピアグループＡ．１  ６３０が最上位レベルのピアグループである。図６は、ピアグループＡ．１１１  ６１０、Ａ．１１  ６２０、およびＡ．１  ６３０のそれぞれのメンバーノードによって行われる、到達可能アドレスの通知を示す。
【００７１】
始めに、ＰＧ  Ａ．１１１  ６１０を参照すると、このピアグループは、３つのノード６１５ａ、６１５ｂおよび６１５ｃを含む。ノード６１５ａ〜ｃはそれぞれ、１つまたは複数の「内部登録アドレス（ｉｎｔｅｒｎａｌ  ｓｕｂｓｃｒｉｂｅｒ  ａｄｄｒｅｓｓ）」および１つまたは複数の「外側（ｅｘｔｅｒｉｏｒ）」到達可能アドレスを有する。ノードの「内部登録アドレス」とは、そのノードを介して到達可能なＰＮＮＩネットワーク内部のアドレスである。ノードの「外側」到達可能アドレスとは、そのノードを介して到達可能なＰＮＮＩネットワークの外にあるアドレスである。図６の例では、各外部到達可能アドレスは、特定の関連するパラメータ、すなわち「適用範囲」、「管理上の重み」、および「利用可能セルレート」を有する。
【００７２】
「適用範囲」とは、どれだけ上の階層までアドレスを通知すべきか指定するパラメータである。たとえば、ノード６１５ｃは、適用範囲が「１２」となるように構成されている外側到達可能アドレスＢ．４５８０３２を有する。「１２」という値は、レベル番号が１２以上のピアグループ内部でアドレスを通知できることを示す。「管理上の重み」とは、送信ノードが経路の決定に使用できる通知を行うノードを介して、通知されたアドレスに到達するための相対的な管理コストを割り当てるパラメータである。「利用可能セルレート」とは、通知されたアドレスへのリンクの帯域幅の測度であり、経路の決定にも使用することができる。
【００７３】
図６の実施形態では、関連するパラメータは外側到達可能アドレスに関してのみ示してあるが、同じまたは他のパラメータも内部到達可能アドレスに関連づけることができることに留意されたい。さらに、他の実施形態では、同じまたは他のパラメータを、内部および外側到達可能アドレスの両方に関連づけることができる。
【００７４】
図６は、各ノードの到達可能な内部および外側アドレスを示すだけでなく、各ノードのノードＩＤおよび要約アドレスリスト、さらにその結果得られる通知も示す。行うべき通知を、ノードの到達可能アドレスおよび要約アドレスリストから決定するために、ノードによって用いられる処理の一例を図７に示す。
【００７５】
図７は、ノード（物理ノードまたは論理ノードのどちらか適切な方）が、そのピアグループ内部でどのアドレスを同報通信すべきか決定するために使用する方法を示す。図７に示すステップのタイプおよび順序は例示に過ぎないことが理解されよう。他の実施形態では、本発明を実施するために、他の順序で適用される他のステップを用いることができる。
【００７６】
図７の処理では、始めにステップ７１０で、ノードは、ノードのピアグループのレベルで通知されるのに十分な適用範囲を有する（１つまたは複数の実施形態では、関連づけられた適用範囲パラメータをもたないアドレスは、適用範囲が制限されないものとみなされる）その到達可能アドレス（以下で詳細に説明するように、アドレスでもアドレス接頭部でもよい）を識別する。１つまたは複数の実施形態では、ノードは、識別された到達可能アドレスのリストを編集する。図７の実施形態では、そのリストをリスト「Ｌ１」と呼ぶ。
【００７７】
ステップ７１５で、ノードは、その構成された要約アドレスをリストに読み出す。図７の実施形態では、このリストはリスト「Ｌ２」と呼ばれる。ステップ７２０で、ノードは、要約アドレスリストＬ２中の項目を、優先度に従って並べる。１つまたは複数の実施形態では、項目はアドレス接頭部の長さの優先度に従って、最も長いものから最も短いものへ、内部または外部かによって並べられる。
【００７８】
ステップ７２５で、順序付けられた要約アドレスリストＬ２から、第１の項目が選択される。ステップ７３０で、選択された要約アドレスリスト項目は、到達可能アドレスリストＬ１中の到達可能アドレスと比較され、ステップ７３５で、選択された要約アドレス項目と合致する、リストＬ１中のすべての無標の（ｕｎｍａｒｋｅｄ）合致アドレスが識別される。「合致」アドレスとは、到達可能性クラス（内部または外側）と、要約アドレスリスト項目中で指定された接頭部またはアドレスとに合致するアドレスである。リストＬ１中の「無標の」アドレスとは、以下のステップ７５５に関連して説明するように、要約アドレスリストＬ２の項目と合致するという印がつけられていない項目である。
【００７９】
ステップ７４０で、リストＬ１にある合致アドレス（群）がステップ７３５で識別されたかどうかに関する判定が行われる。ステップ７４０で合致アドレス（群）が見つからない場合、処理はステップ７４５に進み、それ以上の（未処理の）項目が、ステップ７１５で作成された順序付けられた要約アドレスリストＬ２に残っているかどうかに関する判定が行われる。それ以上の項目が残っている場合、リストＬ２の次の項目がステップ７５０で選択され、処理はステップ７３０に戻る。
【００８０】
合致アドレス（群）がステップ７４０で見つかった場合、その合致アドレス（群）を含む（図７でリスト「Ｌ３」で示す）リストが、ステップ７５２で作成される。このアドレス（群）は、ステップ７５５で、処理済みであるとの印がリストＬ１中につけられる。「処理済みと印がつけられる」ことは、要約アドレスリストＬ２中の項目と合致し、要約アドレスリストＬ２に残っているどの項目に関しても考慮する必要がないことを示す何らかの方法で、フラグを立てられるか、または識別されることを意味する。
【００８１】
ステップ７６０で、現在処理中の要約リストＬ２項目のタイプが「例外」項目かどうか判定が行われる。「例外」項目とは、そのアドレスがより短い接頭部を指定する他の要約アドレスリストＬ２項目とも合致するかどうかに関わらず、指定された接頭部と合致するアドレスを通知すべきであることを示す。図７の処理は最も接頭部が長い要約アドレスリスト項目に最初に作用し合致アドレスは後に続く項目に関する考慮から外されるので、処理のこの時点で、現在処理中の項目よりも接頭部が長い未処理の要約アドレスリストＬ２項目は残っていない。例外アドレスと合致することは、したがって、合致したアドレスが通知されることを意味する。したがって、ステップ７５２でリストＬ３に追加されたすべてのアドレスは、ステップ７６５で、ノードによって行われる通知のリストに追加される。
【００８２】
ステップ７６０で、処理中の項目が例外項目ではないと判定された場合、処理はステップ７７０に進み、現在の項目が「抑制」項目であるかどうか判定が行われる。「抑制」要約アドレスリスト項目と合致するアドレスは、「抑制」項目に対して指定されたよりも接頭部が短い「要約」要約アドレスリスト項目とも合致するとしても、通知されない。
【００８３】
ステップ７７０で、現在処理中の要約アドレスリストＬ２項目が「抑制」項目であると判定された場合、リストＬ３にある合致アドレスは、ノードによって行われる通知のアドレスリストに追加されない。
【００８４】
ステップ７７０で、現在処理中のリストＬ２項目が抑制項目でないと判定された場合、処理はステップ７８０に進み、現在処理中の要約アドレスリストＬ２項目が「要約」項目であるかどうか判定が行われる。現在の項目が要約項目であると判定された場合、指定された要約アドレス接頭部と合致するリストＬ３にあるすべてのアドレスの到達可能性情報は、ステップ７８５で、その合致アドレスの集約到達可能性情報を作成するためにネットワークオペレータが決定するやり方で集約され、次いで、ステップ７８７で、要約アドレス接頭部が、集約された到達可能性情報と共に、通知されるアドレスのリストに追加される。例外または抑制項目以外のすべての要約アドレスリスト項目が要約項目である実施形態では、ステップ７８０は必要なく、処理はステップ７８５に直接進むことができることに留意されたい。
【００８５】
ステップ７８７から、処理はステップ７４５に戻り、順序付けられた要約アドレスリストＬ２に未処理の項目がまだ残っているかどうか判定が行われる。未処理の項目がまだ残っている場合、次の未処理の要約アドレスリストＬ２項目がステップ７５０で選択され、処理はステップ７３０に戻る。
【００８６】
未処理の項目がそれ以上リストＬ２にない場合、ステップ７５５で処理済みとの印がつけられなかった到達可能アドレスがリストＬ１に残っているかどうかに関して、ステップ７９０で判定が行われる。このようなアドレスが残っていない場合、ステップ７６５および／または７８７で識別された通知されるアドレスのリストは、ステップ７９５で、どの関連するパラメータとも一緒にノードのピアグループ内部にフラッドされる。無標の到達可能アドレスがリストＬ１に残っている場合、そのアドレスは、ステップ７９２で、通知されるアドレスのリストに追加され、ステップ７６５および／または７８７で識別されたアドレスと共に、ステップ７９５でフラッドされる。
【００８７】
図７の処理を、図６のノードが、各ノードによって行われる通知を決定するために使用することができる。
【００８８】
最初にノード６１５ａに移ると、ノード６１５ａは、２つの到達可能アドレスを有する。すなわち、外側アドレスＢ．４５８０３２、および内部アドレスＡ．１１１１４７である（図６で使用する英数字のアドレスは、通常はＡＴＭアドレスであるものを単純に表現したものである）。外側到達可能アドレスＢ．４５８０３２は、適用範囲が８であり、この数字は、レベル１２にあるノード６１５ａのピアグループのレベル番号より小さい。したがって、外側アドレスＢ．４５８０３２は、ノード６１５ａによって通知されるのに十分な適用範囲を有する（図６の実施形態では、より小さい適用範囲が指定されない限り、すべての内部到達可能アドレスは、適用範囲が無制限とみなされる）。
【００８９】
ノード６１５ａの要約アドレスリストは、１つの項目、すなわち要約アドレスＡ．１１１１を含む。要約アドレスＡ．１１１１をノード６１５ａの２つの到達可能アドレス（Ａ．１１１１４７およびＢ．４５８０３２）と比較すると、アドレスＡ．１１１１４７と合致する。したがって、接頭部Ａ．１１１１は、（関連するどの到達可能性情報、たとえば適用範囲や管理上の重みとも一緒に）ノード６１５ａによって通知されるアドレスのリストに追加される。
【００９０】
ノード６１５ａの要約アドレスリストには、それ以上は項目がない。ただし、要約アドレスリストのどの項目とも合致しなかった到達可能アドレス、すなわち外側アドレスＢ．４５８０３２が残っている。したがって、アドレスＢ．４５８０３２が、ノード６１５ａによって通知されるアドレスに追加される。したがって、その結果ノード６１５ａによって行われる通知は、Ａ．１１１１およびＢ．４５８０３２となる。
【００９１】
次にノード６１５ｂに移ると、このノードには、４つの到達可能アドレス、すなわち３つの内部アドレスＡ．１１１２０３、Ｂ．４３２１１４、Ｂ．７８８３１２、および１つの外側アドレスＢ．４５８２５５がある。外側アドレスＢ．４５８２５５の適用範囲は「０」であり、これはすべてのレベルで通知できることを意味する。
【００９２】
ノード６１５ｂの構成された要約アドレスリスト中の項目は、Ａ．１１１２、Ｂ．４３２１およびＢ．７８８３１２である。
【００９３】
接頭部が最も長い項目は、Ｂ．７８８３１２である。この項目をノード６１５ｂの４つの到達可能アドレスと比較すると、到達可能アドレスＢ．７８８３１２と合致する。したがって、アドレスＢ．７８８３１２は、ノード６１５ｂによって通知されるアドレスのリストに追加される。ノード６１５ｂの要約アドレスリスト中の次の項目は、Ｂ．４３２１である。この項目をノード６１５ｂの残り３つの到達可能アドレスと比較すると、Ｂ．４３２１１４と合致する。合致アドレスが１つしかないので、どの到達可能アドレス情報も集約する必要はない。したがって、要約アドレス接頭部Ｂ．４３２１が、アドレスＢ．４３２１１４の関連する到達可能性情報と共に、通知されるアドレスのリストに追加される。
【００９４】
ノード６１５ｂの要約アドレスリストに残っている項目は、要約アドレスＡ．１１１２である。この項目をノード６１５ｂの残り２つの到達可能アドレスと比較すると、到達可能アドレスＡ．１１１２０３と合致する。この場合も、合致するものが１つしかないので、関連する到達可能性情報を集約する必要はない。したがって、要約アドレス接頭部Ａ．１１１２が、アドレスＡ．１１１２０３の関連する到達可能性情報と共に、通知されるアドレスのリストに追加される。
【００９５】
ノード６１５ｂの要約アドレスリストには、それ以上項目がない。ただし、要約アドレスリストのどの項目とも合致しなかった到達可能アドレス、すなわち外部到達可能アドレスＢ．４５８２５５が残っている。外部到達可能アドレスＢ．４５８２５５の適用範囲は「０」（無制限）であり、これはノード６１５ｂによって通知されるのに十分な適用範囲であることを意味する。したがって、到達可能アドレスＢ．４５８２５５が、その関連する到達可能性情報とともに、ノード６１５ｂによって通知されるアドレスのリストに追加される。したがって、その結果ノード６１５ｂによって通知されるアドレスは、Ａ．１１１２、Ｂ．４３２１、Ｂ．７８８３１２、およびＢ．４５８２２５となる。
【００９６】
ノード６１５ｃには、３つの到達可能アドレスＡ．１１１３３７、Ｂ．４３２２１２およびＢ．４５８０３２がある。外部アドレスＢ．４５８０３２の適用範囲は１２であり、これはノード６１５ｃのピアグループのレベルと合致する。したがって、外部アドレスＢ．４５８０３２は、ノード６１５ｃによって通知されるのに十分な適用範囲を有する。
【００９７】
ノード６１５ｃの要約アドレスリストは、２つの項目、すなわち（到達可能アドレスＡ．１１１３３７と合致する）要約アドレスＡ．１１１３および（到達可能アドレスＢ．４３２２１２と合致する）要約アドレスＢ．４３２２を含む。残りの外部アドレスＢ．４５８０３２は、要約アドレスリストのどの項目とも合致しない。したがって、ノード６１５ｃによって通知されるアドレスは、Ａ．１１１３、Ｂ．４３２２およびＢ．４５８０３２である。
【００９８】
最下位レベルのピアグループ６１０内のノード６１５ａ〜ｃによって行われる通知のリストを、以下の表７に示す。
【表７】
2004282699.tif 000009
【００９９】
表７のアドレスは、ピアグループ６１０の通知される到達可能アドレスである。このアドレスは、ＬＧＮ６２５ａによって通知されるとみなされる到達可能アドレスを表し、ＬＧＮ６２５ａは、次のレベルのピアグループ６２０ではピアグループ６１０を表す（ＬＧＮ６２５ａの機能は、ピアグループ６１０のどのメンバーがピアグループリーダである時点でも、そのメンバーによって実行されることが思い出されよう）。これらの到達可能アドレスのうち、アドレスＢ．４５８０３２は、二度現われる。すなわち、一度はノード６１５ａで適用範囲が８、一度はノード６１５ｃで適用範囲が１２である。ピアグループ６２０はレベル８にあるので、適用範囲が８以下のアドレスだけが通知可能である。したがって、ノード６１５ｃの到達可能アドレスＢ．４５８０３２は、ＬＧＮ６２５ａの通知可能な到達可能アドレスではない。ＬＧＮ６２５ａのそれ以外の通知可能な到達可能アドレスは、以下の通りである。
Ａ．１１１１
Ａ．１１１２
Ａ．１１１３
Ｂ．４３２１
Ｂ．４３２２
Ｂ．４５８０３２（適用範囲８）
Ｂ．４５８２５５（適用範囲０）
Ｂ．７８８３１２
【０１００】
これらのアドレスは、以下の項目を含むＬＧＮ６２５ａの要約アドレスリストに従ってＬＧＮ６２５ａによって行われる到達可能アドレスの通知を決定するために、図７の方法に従って再度処理される。
Ａ．１１１
Ｂ．４３２
Ｂ．４５８
Ｂ．７８８３  抑制
Ｂ．４５８０  例外
【０１０１】
ＬＧＮ６２５ａのソートされた要約アドレスリストの第１の項目は、例外要約アドレスＢ．４５８０である。図７に関連して上で説明したように、接頭部が本発明の例外要約アドレスと最も長く合致するどのアドレスも、その別個の到達可能性情報と共に、別々に通知される。したがって、本発明の例外アドレスにより、ネットワーク管理者は、ほかの場合なら抑制されまたは要約されるはずのアドレスに関して、完全な到達可能性情報を提供することが可能になる。
【０１０２】
例外要約アドレスＢ．４５８０をＬＧＮ６２５ａの８個の到達可能アドレスと比較すると、Ｂ．４５８０３２と合致する。したがって、アドレスＢ．４５８０３２およびその関連する到達可能性情報は、ＬＧＮ６２５ａによって通知されるアドレスのリストに追加される。
【０１０３】
ＬＧＮ６２５ａの要約アドレスリストの次の項目は、抑制要約アドレスＢ．７８８３である。抑制要約アドレスと合致するどのアドレスも、通知されない。抑制要約アドレスＢ．７８８３をＬＧＮ６２５ａの残り７個の到達可能アドレスと比較すると、アドレスＢ．７８８３１２と合致する。アドレスＢ．７８８３１２は、処理済みとの印がつけられるが、ＬＧＮ６２５ａによって通知されるアドレスのリストには追加されない。
【０１０４】
ＬＧＮ６２５ａの要約アドレスリストの次の項目は、要約アドレスＢ．４５８である。Ｂ．４５８をＬＧＮ６２５ａの残り６個の到達可能アドレスと比較すると、到達可能アドレスＢ．４５８２２５と合致する（到達可能アドレスＢ．４５８０３２はすでに例外要約アドレスＢ．４５８０と合致し、したがって処理済みであり未処理の到達可能アドレスから削除されていることを思い出されたい）。合致するものは１つしかないので、アドレスＢ．４５８は、アドレスＢ．４５８２２５の到達可能な（その適用範囲０を含む）アドレス情報と共に、ＬＧＮ６２５ａによって通知されるアドレスのリストに追加される。
【０１０５】
ＬＧＮ６２５ａの要約アドレスリストの最後から２番目の項目は、要約アドレスＢ．４３２である。Ｂ．４３２をＬＧＮ６２５ａの残り５個の到達可能アドレスと比較すると、アドレスＢ．４３２１およびＢ．４３２２と合致する。したがって、この２つのアドレスの到達可能アドレス情報は集約され、アドレスＢ．４３２が、この集約された到達可能アドレス情報と共に、ＬＧＮ６２５ａによって通知されるアドレスのリストに追加される。
【０１０６】
ＬＧＮ６２５ａの要約アドレスリストの最後の項目は、要約アドレスＡ．１１１である。Ａ．１１１をＬＧＮ６２５ａの残り３つの到達可能アドレスと比較すると、残り３つのすべてのアドレスＡ．１１１１、Ａ．１１１２、およびＡ．１１１３と合致する。この３つのアドレスの到達可能アドレス情報は集約され、アドレスＡ．１１１は、アドレスＡ．１１１１、Ａ．１１１２およびＡ．１１１３のこの集約された到達可能アドレス情報と共に、ＬＧＮ６２５ａによって通知されるアドレスのリストに追加される。その結果、ＬＧＮ６２５ａによって通知されるアドレスは、以下のようになる。
Ａ．１１１
Ｂ．４３２
Ｂ．４５８（適用範囲０）
Ｂ．４５８０３２（適用範囲８）
【０１０７】
図６の例におけるピアグループ６２０の第２のＬＧＮは、ＬＧＮ６２５ｂである。ＬＧＮ６２５ｂは、その要約アドレスリスト中に項目が１つ、すなわち、要約アドレスＡ．１１２しかない。ＬＧＮ６２５ｂは、ただ１つの到達可能アドレス、すなわち適用範囲が８の外側アドレスＢ．４５８０３２と共に示されており、このアドレスは、ＬＧＮ６２５ｂの唯一の要約アドレスＡ．１１２と合致しない。外側到達可能アドレスＢ．４５８０３２は、ＬＧＮ６２５ｂの要約アドレスリストのどの項目とも合致しないので、その到達可能アドレス情報と共に、外来アドレスを構成し、ＬＧＮ６２５ｂによって通知されるアドレスのリストに追加される。その結果、ＬＧＮ６２５ｂによって通知される唯一のアドレスは、以下の通りである。
Ｂ．４５８０３２（適用範囲８）
【０１０８】
ピアグループ６２０のノード６２５ａ〜ｂによって行われる通知は、以下の表８に要約される。
【表８】
2004282699.tif 000010
【０１０９】
表８のアドレスが、ピアグループ６２０の通知される到達可能アドレスのすべてである。これらのアドレスは、ＬＧＮ６３５によって通知されるとみなされる到達可能アドレスを表し、ＬＧＮ６３５は、次のレベルのピアグループ６３０ではピアグループ６２０を表す。この到達可能アドレスのうち、アドレスＢ．４５８０３２は、二度現われる。すなわち、一度はＬＧＮ６２５ａで適用範囲が８、一度はノードＬＧＮ６２５ｂで適用範囲が８である。ピアグループ６３０はレベル４にあるので、適用範囲が４以下のアドレスだけが通知可能である。したがって、ノード６２５ａおよび６２５ｂ両方のアドレスＢ．４５８０３２は、ＬＧＮ６３５の通知可能な到達可能アドレスではない。ＬＧＮ６３５のそれ以外の通知可能な到達可能アドレスは、以下のようになる。
Ａ．１１１
Ｂ．４３２
Ｂ．４５８（適用範囲０）
【０１１０】
ＬＧＮ６３５は、その要約アドレスリスト中に要約アドレスＡ．１１だけを有している。要約アドレスＡ．１１は、ＬＧＮ６３５の到達可能アドレスの１つ、すなわちＡ．１１１と合致する。したがって、Ａ．１１は、ＬＧＮ６３５によって通知されるアドレスのリストに追加される。残りの２つの到達可能アドレスは、ＬＧＮ６３５の要約アドレスリストのどの項目とも合致しない。したがって、これらのアドレスもそれぞれ、ＬＧＮ６３５によって通知されるアドレスのリストに追加される。したがって、その結果ピアグループ６３０のＬＧＮ６３５によって通知されるアドレスは、以下のようになる。
Ａ．１１
Ｂ．４３２
Ｂ．４５８（適用範囲０）
【０１１１】
図６の例は、どのようにして本発明の例外要約アドレスを従来のＰＮＮＩ要約アドレスと共に使用して、ほかの場合なら要約の対象となるはずの例外要約アドレスと合致するより低レベルの通知をそのまま上のレベルに伝播し、その結果、その到達可能アドレス情報（たとえば、要約アドレス、帯域幅、および適用範囲）の伝播を保存することができるかを示す。本発明の例外要約アドレスによって、ネットワーク管理者が、特定の到達可能アドレスの情報が経路決定のために特に重要である場合に、そのような情報を保持し、さらに従来のアドレス要約の帯域幅保存特徴を保持することが可能になる。
【０１１２】
以上、ネットワークにおける到達可能アドレス情報を通知する方法を提示した。本発明を特定の例を用いて説明したが、本発明はこうしたいくつかの例に限定されないことが当業者には明らかであろう。たとえば、本発明をＰＮＮＩネットワークに関連して説明したが、本発明は、適切に用語を置き換えれば、他のネットワークにも適用可能である。本発明の発明性のある特徴を利用する他の実施形態が、当業者には明らかであろう。
【図面の簡単な説明】
【０１１３】
【図１】一例としてのネットワークの物理的配置を示す概略図である。
【図２】図１のネットワークのノードをピアグループに配置する方法の一例を示す概略図である。
【図３】図２のピアグループの配置の論理的な概観の一例を示す概略図である。
【図４】図２のネットワークのピアグループをより高レベルのピアグループに配置する方法の一例を示す概略図である。
【図５】図４のネットワークの一部分の、到達可能なエンドシステムのアドレスの一例を示す概略図である。
【図６】発明の実施形態をなす、一例としてのネットワークを示す概略図である。
【図７】本発明の実施形態で使用する処理を示すフロー図である。
【符号の説明】
【０１１４】
１００  ネットワーク
１０５ａ〜ｚ  物理ノード、最下位レベルノード、ノード
１１０ａ〜ｇｇ  双方向通信リンク
２０５ａ〜ｇ、４１０ａ〜ｂ、４３０、６１０、６２０、６３０  ピアグループ
３０５ａ〜ｇ  論理グループノード、論理ノード
４２０ａ〜ｂ  論理グループノード、ピアグループ
４２０ｃ  論理グループノード
５０５ａ〜ｍ  エンドシステム
６１５ａ〜ｃ  ノード
【図１】
2004282699.tif 000011
【図２】
2004282699.tif 000012
【図３】
2004282699.tif 000013
【図４】
2004282699.tif 000014
【図５】
2004282699.tif 000015
【図６】
2004282699.tif 000016
【図７】
2004282699.tif 000017
【外国語明細書】
2004282699.tif 000018
2004282699.tif 000019
2004282699.tif 000020
2004282699.tif 000021
2004282699.tif 000022
2004282699.tif 000023
2004282699.tif 000024
2004282699.tif 000025
2004282699.tif 000026
2004282699.tif 000027
2004282699.tif 000028
2004282699.tif 000029
2004282699.tif 000030
2004282699.tif 000031
2004282699.tif 000032
2004282699.tif 000033
2004282699.tif 000034
2004282699.tif 000035
2004282699.tif 000036
2004282699.tif 000037
2004282699.tif 000038
2004282699.tif 000039
2004282699.tif 000040
2004282699.tif 000041
2004282699.tif 000042
2004282699.tif 000043
2004282699.tif 000044
2004282699.tif 000045
2004282699.tif 000046
2004282699.tif 000047
2004282699.tif 000048
2004282699.tif 000049
2004282699.tif 000050
2004282699.tif 000051
2004282699.tif 000052
2004282699.tif 000053
2004282699.tif 000054
2004282699.tif 000055
2004282699.tif 000056
2004282699.tif 000057
2004282699.tif 000058
2004282699.tif 000059