(57)【要約】【課題】他の通信装置から影響を受けることなく、また他の通信装置に影響を与えることなく、フォワーディングテーブル容量よりも多くの経路エントリを扱うことが可能な通信装置を提供する。【解決手段】パケットの転送先を選択するためのルーティングテーブルとフォワーディングテーブルを備えた通信装置において、ルーティングテーブル上の経路エントリを加工し、フォワーディングテーブルへ登録する経路エントリ数を削減する。【選択図】図７
2010226340.tif 000002
【特許請求の範囲】
【請求項１】
通信回線を介して隣接する他の通信装置と接続される通信装置であって、
構成情報により静的に設定された経路情報、または経路制御プロトコルを使用し動的に学習された経路情報を、宛先毎に、１つ以上の経路エントリとして保持するルーティングテーブルと、
前記ルーティングテーブル内に保持された宛先毎の１つ以上の経路エントリから、宛先毎に、第一優先の経路エントリを選定する登録制御部と、
フォワーディングテーブルと、
前記登録制御部によって選定された前記経路エントリを前記フォワーディングテーブルに登録する経路登録部と、
隣接する第１の通信装置からパケットを受信し、前記フォワーディングテーブルを参照することにより前記パケットの転送先を選択し、選択した転送先に基づいて、前記パケットを隣接する第２の通信装置に転送するパケット転送部と、
を備え、
前記登録制御部は、
前記パケットの転送先として、前記第一優先の経路エントリのすべてを前記フォワーディングテーブルに登録した場合と同じ転送先が選択されるように、前記第一優先の経路エントリを加工して、前記第一優先の経路エントリの一部を、前記フォワーディングテーブルに登録する前記経路エントリとして選定することを特徴とする通信装置。
【請求項２】
請求項１に記載の通信装置において、
前記登録制御部は、
前記第一優先の経路エントリのうち、ある経路エントリの宛先が、他の経路エントリの宛先によって包含され、かつ、前記ある経路エントリの転送条件が、前記他の経路エントリの転送条件と同一である場合、前記ある経路エントリを、前記フォワーディングテーブルに登録する前記経路エントリとして選定しないことを特徴とする通信装置。
【請求項３】
請求項１に記載の通信装置において、
前記登録制御部は、
前記第一優先の経路エントリのうち、ある経路エントリの宛先が、他の複数の経路エントリの宛先を組み合わせたものと同等となる場合、前記ある経路エントリを、前記フォワーディングテーブルに登録する前記経路エントリとして選定しないことを特徴とする通信装置。
【請求項４】
請求項１に記載の通信装置において、
前記登録制御部は、
集約された経路エントリとして、前記第一優先の経路エントリのうち、複数の経路エントリを組み合わせたものと同等となる経路エントリを生成し、生成した前記集約経路エントリを、前記フォワーディングテーブルに登録する前記経路エントリとして選定し、集約される側の前記複数の経路エントリを、前記フォワーディングテーブルに登録する前記経路エントリとして選定しないことを特徴とする通信装置。
【請求項５】
請求項１に記載の通信装置において、
前記登録制御部は、
集約された経路エントリとして、前記第一優先の経路エントリのうち、複数の経路エントリを組み合わせたものと同等となる経路エントリを生成する場合において、集約される側の前記複数の経路エントリのうち、一部の経路エントリが不足している場合に、不足している部分を補完する経路エントリを生成すると共に、前記集約経路エントリを生成し、生成した前記集約経路エントリ及び前記補完経路エントリを、前記フォワーディングテーブルに登録する前記経路エントリとして選定し、集約される側の前記複数の経路エントリを、前記フォワーディングテーブルに登録する前記経路エントリとして選定しないことを特徴とする通信装置。
【請求項６】
請求項１に記載の通信装置において、
前記登録制御部は、
集約された経路エントリとして、前記第一優先の経路エントリのうち、複数の経路エントリを組み合わせたものと同等となる経路エントリを生成する場合において、集約される側の前記複数の経路エントリのうち、一部の経路エントリが不足している場合に、不足している部分を補完する経路エントリを生成すると共に、前記集約経路エントリを生成し、生成した前記集約経路エントリを、前記フォワーディングテーブルに登録する前記経路エントリとして選定し、生成した前記補完経路エントリ及び集約される側の前記複数の経路エントリを、前記フォワーディングテーブルに登録する前記経路エントリとして選定しないことを特徴とする通信装置。
【請求項７】
請求項１に記載の通信装置において、
前記登録制御部は、前記第一優先の経路エントリの一部を、前記フォワーディングテーブルに登録する前記経路エントリとして選定するための経路エントリ設定方式として、
前記第一優先の経路エントリのうち、ある経路エントリの宛先が、他の経路エントリの宛先によって包含され、かつ、前記ある経路エントリの転送条件が、前記他の経路エントリの転送条件と同一である場合、前記ある経路エントリを、前記フォワーディングテーブルに登録する前記経路エントリとして選定しない第１の経路エントリ設定方式と、
前記第一優先の経路エントリのうち、ある経路エントリの宛先が、他の複数の経路エントリの宛先を組み合わせたものと同等となる場合、前記ある経路エントリを、前記フォワーディングテーブルに登録する前記経路エントリとして選定しない第２の経路エントリ設定方式と、
集約された経路エントリとして、前記第一優先の経路エントリのうち、複数の経路エントリを組み合わせたものと同等となる経路エントリを生成し、生成した前記集約経路エントリを、前記フォワーディングテーブルに登録する前記経路エントリとして選定し、集約される側の前記複数の経路エントリを、前記フォワーディングテーブルに登録する前記経路エントリとして選定しない第３の経路エントリ設定方式と、
集約された経路エントリとして、前記第一優先の経路エントリのうち、複数の経路エントリを組み合わせたものと同等となる経路エントリを生成する場合において、集約される側の前記複数の経路エントリのうち、一部の経路エントリが不足している場合に、不足している部分を補完する経路エントリを生成すると共に、前記集約経路エントリを生成し、生成した前記集約経路エントリ及び前記補完経路エントリを、前記フォワーディングテーブルに登録する前記経路エントリとして選定し、集約される側の前記複数の経路エントリを、前記フォワーディングテーブルに登録する前記経路エントリとして選定しない第４の経路エントリ設定方式と、
集約された経路エントリとして、前記第一優先の経路エントリのうち、複数の経路エントリを組み合わせたものと同等となる経路エントリを生成する場合において、集約される側の前記複数の経路エントリのうち、一部の経路エントリが不足している場合に、不足している部分を補完する経路エントリを生成すると共に、前記集約経路エントリを生成し、生成した前記集約経路エントリを、前記フォワーディングテーブルに登録する前記経路エントリとして選定し、生成した前記補完経路エントリ及び集約される側の前記複数の経路エントリを、前記フォワーディングテーブルに登録する前記経路エントリとして選定しない第５の経路エントリ設定方式と、
のうち、少なくとも２つの経路エントリ設定方式の適用が可能であることを特徴とする通信装置。
【請求項８】
請求項７に記載の通信装置において、
適用可能な前記少なくとも２つの経路エントリ設定方式の中から、適用する経路エントリ設定方式の組み合わせが、予め設定されていることを特徴とする通信装置。
【請求項９】
請求項７に記載の通信装置において、
前記登録制御部は、適用可能な前記少なくとも２つの経路エントリ設定方式の中から、適用する経路エントリ設定方式の組み合わせを、前記構成情報により静的に決定することを特徴とする通信装置。
【請求項１０】
請求項７に記載の通信装置において、
前記登録制御部は、適用可能な前記少なくとも２つの経路エントリ設定方式の中から、適用する経路エントリ設定方式の組み合わせを、保持する前記経路情報の状況により動的に決定することを特徴とする通信装置。
【請求項１１】
請求項１ないし請求項１０のうちの任意の一つに記載の通信装置において、
前記フォワーディングテーブルへの登録状況または前記ルーティングテーブルの保持状況を参照し得ることを特徴とする通信装置。
【請求項１２】
請求項１ないし請求項１０のうちの任意の一つに記載の通信装置において、
前記フォワーディングテーブルへの登録状況に応じて、運用者にアラームを通知し得ることを特徴とする通信装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信装置に関するものである。
【背景技術】
【０００２】
インターネットやイントラネットは、ネットワークを利用するユーザが使用する端末やサーバー、およびルータやレイヤ３スイッチと呼ばれる通信装置を、ローカル・エリア・ネットワーク（ＬＡＮ：Local Area Network）回線やワイド・エリア・ネットワーク（ＷＡＮ：Wide Area Network）回線と呼ばれる通信回線で相互接続し、インターネット・プロトコル（ＩＰ：Internet Protocol）と呼ばれる通信プロトコルを使用し相互通信が行なわれる。ＩＰにはＩＰｖ４（IP version 4）とＩＰｖ６（IP version 6）がある。
【０００３】
ＩＰでは、パケットと呼ばれる通信単位に通信データを分割し転送する。パケットは数十バイトから数十キロバイト（キロは１０の３乗、すなわち１０００を示す）程度の可変長のサイズを持つ。パケットにはＩＰヘッダと呼ばれるヘッダが付与される。ＩＰヘッダには送信先のＩＰアドレス（以降、“送信先アドレス”と記す）、送信元のＩＰアドレス（以降、“送信元アドレス”と記す）などのパケットの転送に必要なデータが含まれる。また、ＩＰｖ４のＩＰヘッダには、サービス種別が含まれる。サービス種別には２種類の形式が存在する。１つは、８段階（３ビット）からなるパケットの優先度ビット、パケットを送信先に低遅延で到達させることを求める遅延度ビット、パケットを送信先に多く到達させることを求める転送量ビット、パケットを送信先に低損失で到達させることを求める信頼性ビットから構成される形式であり、ＴＯＳ（Type Of Service）と呼ばれる。もう１つは、６４段階（６ビット）からなるパケットの優先度で構成される形式であり、ＤＳＣＰ（Diff-Serv Code Point）と呼ばれる。また、ＩＰｖ６のＩＰヘッダには、トラヒッククラスが含まれる。トラヒッククラスにはパケットの転送クラスや優先度が含まれる。サービス種別やトラヒッククラスはトラヒック・エンジニアリングを考慮したパケット転送で使用される場合もある。
【０００４】
ＩＰｖ４のＩＰアドレスは３２ビットからなり、８ビット単位で分割したビット列の１０進数表現を“.”（ドット）の連結した文字列で表現される。ＩＰｖ６のＩＰアドレスは１２８ビットからなり、１６ビット単位で分割したビット列の１６進数表現を“:”（コロン）で連結した文字列で表現される。ＩＰアドレスは、ネットワークアドレスとホストアドレスで構成される。ネットワークアドレスは最上位ビットから始まる可変長の連続したビット列であり、残りのビット列がホストアドレスとなる。ネットワークアドレスのビット幅はネットワークマスク長として１０進数で表現される。たとえば、ＩＰｖ４のＩＰアドレス“10.0.0.1/8”では、ネットワークアドレスは”10.0.0.0”であり、ネットワークマスク長は“8”であり、ホストアドレスは”0.0.0.1”である。また、ＩＰｖ６のＩＰアドレス”3FFE:1000:2000::1/48”では、ネットワークアドレスは“3FFE:1000:2000::”であり、ネットワークマスク長は“48”であり、ホストアドレスは“::1”である。なお、ＩＰｖ６のＩＰアドレスでは、１６進数表現“0000”が連続する場合、そのＩＰアドレス内で１箇所のみ“::”として省略して表現することができる。
【０００５】
ルータやレイヤ３スイッチは、構成情報により静的に設定された経路情報（「静的経路」と呼ばれる）、または経路制御プロトコルにより動的に学習された経路情報（「動的経路」と呼ばれる）を、プロセッサ（ＣＰＵやＭＰＵなど）から直接アクセス可能なメモリ（ＲＡＭ：Random Access Memory）上の経路表（ルーティングテーブル：「ＲＩＢ」（Routing Information Base）とも呼ばれる）に保持し、ルーティングテーブル内に保持した宛先毎の１つ以上の経路エントリから、宛先毎に第一優先の経路エントリを選択し、受信したパケットの転送先（ネクストホップアドレス）を選択するために利用する経路表（フォワーディングテーブル：「ＦＩＢ」（Forwarding Information Base）とも呼ばれる）に登録する。経路エントリには、送信先のネットワークアドレス（「プレフィックス」とも呼ばれる）、ネットワークマスク長（「プレフィックス長」とも呼ばれる）、ネクストホップアドレス（パケットを転送する次の通信装置のＩＰアドレス）、経路フラグ（受信したパケットを廃棄することを示すブラックホールフラグや、受信したパケットを廃棄し、かつパケットが転送エラーとなったことをパケットの送信元に通知するＩＣＭＰ（Internet Control Message Protocol）パケットを返送することを示すリジェクトフラグなどの経路の属性が含まれる）などが含まれる。
【０００６】
経路制御プロトコルには、ＩＰｖ４の経路制御プロトコルとして、ＲＩＰ（Routing Information Protocol）、ＯＳＰＦ（Open Shortest Path First）、ＢＧＰ（Border Gateway Protocol）などがある。また、ＩＰｖ６の経路制御プロトコルとして、ＲＩＰｎｇ（Routing Information Protocol next generation）、ＯＳＰＦｖ３（Open Shortest Path First version 3）、ＢＧＰ４＋（Border Gateway Protocol version 4 +）などがある。
【０００７】
ルータやレイヤ３スイッチは、フォワーディングテーブルに基づいてパケットの転送先を選択する。すなわち、ルータやレイヤ３スイッチは、パケットを受信すると、パケットのＩＰヘッダに設定された送信先アドレスに対応する経路エントリを、フォワーディングテーブルから検索し、その経路エントリに設定されたネクストホップアドレスを持つ通信装置にパケットを転送する。
【０００８】
また、パケット上の送信先アドレスにはネットワークマスク長は存在しない。そのため、ルータやレイヤ３スイッチは、パケットの送信先アドレスに対応する経路エントリを検索する場合に、最長一致検索（ロンゲストマッチ検索）と呼ばれる特殊な検索方法を使用する。最長一致検索とは、パケットの送信先アドレスとフォワーディングテーブル内の各経路エントリのネットワークアドレスとの比較で、各経路エントリのネットワークマスク長までのビットが一致する経路エントリの中で、ネットワークマスク長が最も長い経路エントリをフォワーディングテーブルから検索する方法である。
【０００９】
フォワーディングテーブルの構成方法には、ＲＡＭ上に経路エントリをツリー構造で構成し、プログラム（ソフトウェア論理）により、受信したパケットの送信先アドレスに最長一致する経路エントリを、ツリーを辿って検索する方式（「ツリー検索（Ｓ／Ｗ）方式」と呼ぶ）と、ＣＡＭ（Content Addressable Memory）と呼ばれる比較回路付きの専用メモリに経路エントリを登録し、ハードウェア論理により、受信したパケットの送信先アドレスに最長一致する経路エントリを高速に検索する方式（「ＣＡＭ検索方式」と呼ぶ）がある。また、ＲＡＭ上に経路エントリをツリー構造で構成し、ハードウェア論理により、受信したパケットの送信先アドレスに最長一致する経路エントリを、ツリーを辿って検索する方式（「ツリー検索（Ｈ／Ｗ）方式」と呼ぶ）などもある。さらに、特許文献１に記載されているような「ツリー検索（Ｓ／Ｗ）方式」と「ＣＡＭ検索方式」を併用して使用する方式（「ＣＡＭ・ツリー検索（Ｓ／Ｗ）併用方式」と呼ぶ）も提案されている。ＣＡＭ・ツリー検索（Ｓ／Ｗ）併用方式は、ネットワークマスク長の短い経路エントリをＣＡＭに登録し、ネットワークマスク長の長い経路エントリをＲＡＭ上にツリー構造で登録し、受信したパケットの送信先アドレスに最長一致する経路エントリをＣＡＭの経路エントリ、ＲＡＭの経路エントリの順に検索するものである。また、受信したパケットの送信先アドレスに最長一致する経路エントリがＲＡＭに登録された経路エントリである場合に、ＣＡＭに登録されたネットワークマスク長までの検索をＣＡＭで実施し、残りのネットワークマスク長部分をＲＡＭ上のツリーを辿って検索する方式である。
【００１０】
ＲＡＭは随時アクセスメモリとも呼ばれ、アドレス信号によってアドレス情報を与えることにより、任意のアドレスのメモリセルに対して、読み出しや書き込みができる記憶回路をチップ化したものである。
【００１１】
ＣＡＭは連想メモリとも呼ばれ、ＣＡＭ内に登録した全データワードから指定データワードを、ＣＡＭ内に実装した比較回路により高速に検索し、そのデータワードの登録位置を返す、比較回路付き記憶回路をチップ化したものである。ＣＡＭは、全データワードを一度に検索するために、メモリ内の各データワードのビット毎に、入力データワードの各ビットとの比較回路を実装する。また、データワード全体の一致を検知するために、前記比較回路の結果を纏めるための回路も実装する。これらの追加回路によってチップサイズは増大し、チップコストも増大する。また、比較回路はデータが入力される度に全体が動作するため、消費電力も増大する。
【００１２】
このため、同等のフォワーディングテーブル容量を持つ場合に、パケットの送信先アドレスに最長一致するフォワーディングテーブル上の経路エントリの検索性能は、ＣＡＭ検索方式、ツリー検索（Ｈ／Ｗ）方式またはＣＡＭ・ツリー検索（Ｓ／Ｗ）併用方式、ツリー検索（Ｓ／Ｗ）方式の順に悪くなる。また、ハードウェアの実装面積、消費電力、コストは、ツリー検索（Ｓ／Ｗ）方式、ツリー検索（Ｈ／Ｗ）方式、ＣＡＭ・ツリー検索（Ｓ／Ｗ）併用方式、ＣＡＭ検索方式の順に大きくなる。
【００１３】
次に、経路情報の学習方法について説明する。構成情報により静的に設定される経路情報（静的経路）は、構築するネットワーク構成にあわせ、ネットワークアドレス、ネットワークマスク長、ネクストホップアドレスを、構成情報により静的に設定するものである。図４３は、静的経路の設定例を説明するための説明図である。通信装置Ｃは、ネットワーク“10.2.0.0/16”（ネットワークアドレスとネットワークマスク長を組み合わせたものをネットワークと呼ぶ）を持ち、通信装置Ｄはネットワーク“10.3.0.0/16”を持っている。通信装置Ｂにおいて、ネットワーク“10.2.0.0/16”宛の静的経路を設定する場合は、ネットワークアドレス“10.2.0.0”、ネットワークマスク長“16”、ネクストホップアドレス“Ｃ”（通信装置Ｂと通信装置Ｃを接続する回線（インタフェース）の通信装置Ｃ側に設定されたＩＰアドレス）で設定する。また、ネットワーク“10.3.0.0/16”宛の静的経路を設定する場合は、ネットワークアドレス“10.3.0.0”、ネットワークマスク長“16”、ネクストホップアドレス“Ｄ”で設定する。また、静的経路では、集約した経路情報で構成情報を設定することにより、自通信装置に設定する経路情報量を削減することができる。例えば、通信装置Ａにおいて、ネットワーク“10.2.0.0/16”、“10.3.0.0/16”の静的経路を設定する場合は、通信装置Ｂのように個々のネットワーク宛の静的経路を設定するのではなく、個々のネットワークの静的経路（「集約元経路」と呼ぶ）を集約した形でネットワークアドレス“10.2.0.0”、ネットワークマスク長“15”、ネクストホップアドレス“Ｂ”（「集約経路」と呼ぶ）のように設定してもよい。このように、経路集約できるように予めネットワーク構成を設計し、集約したネットワークで静的経路を設定することにより、経路情報量を削減することができる。
【００１４】
経路制御プロトコルにより動的に学習される経路情報（動的経路）は、他の通信装置との間で経路制御プロトコルを動作させ、経路情報を交換することにより、動的に学習するものである。図４４は、動的経路の学習例を説明するための説明図である。通信装置Ｃは、ネットワーク“10.2.0.0/16”を持ち、通信装置Ｄはネットワーク“10.3.0.0/16”を持っている。通信装置Ｂにおいて、通信装置Ｃ、および通信装置Ｄとの間で経路制御プロトコルを動作させることにより、通信装置Ｃ配下のネットワーク“10.2.0.0/16”、および通信装置Ｄ配下のネットワーク“10.3.0.0/16”の動的経路を学習することができる。また、動的経路では、集約する経路情報を構成情報に設定することにより、他の通信装置に配布する経路情報量を削減することができる。例えば、通信装置Ｂにおいて、ネットワーク“10.2.0.0/15”に包含される経路情報を学習した場合に、ネットワーク“10.2.0.0/15”の集約経路を生成するように構成情報を設定する。これにより、通信措置Ｂにおいて、通信装置Ｃからネットワーク“10.2.0.0/16”の経路情報を学習した場合、または通信装置Ｄからネットワーク“10.3.0.0/16”の経路情報を学習した場合に、ネットワーク“10.2.0.0/15”の集約経路が生成される。その集約経路のみの情報を通信装置Ａに配布することにより、通信装置Ａの経路情報量を削減することができる。
【００１５】
静的経路と動的経路での経路集約の共通点は、経路集約できるように予めネットワークを設計し、構成情報により、集約経路を設定することである。また、静的経路と動的経路での経路集約の相違点は、静的経路では、集約経路を設定したその通信装置の経路情報量を削減することができるが、動的経路では、集約経路を設定したその通信装置が経路情報を配布する配布先の通信装置の経路情報量を削減することができる。また、静的経路では、集約経路のネクストホップアドレスと集約元経路のネクストホップアドレスが同一である必要があるが、動的経路では、集約経路のネクストホップアドレスと集約元経路のネクストホップアドレスは同一である必要は無い。また、静的経路では、集約元経路のネットワークの組み合わせが集約経路のネットワークと同等である必要があるが、動的経路では、集約経路のネットワークに包含される一部のネットワークの集約元経路が存在すれば、集約経路は生成される。
【００１６】
次に、経路集約時の問題点を説明する。図４５は、経路集約時の問題点を説明するための説明図であって、図４４に示す構成に、通信装置Ｅ、通信装置Ｆを加えたものである。通信装置Ｅと通信装置Ｆでは、構成情報に経路集約を設定していないものとする。その場合、ネットワーク“10.2.0.0/16”、“10.3.0.0/16”の経路情報は通信装置Ｅ、通信装置Ｆを経由し、通信装置Ａに配布される。これにより、通信装置Ａからネットワーク“10.2.0.0/16”、”10.3.0.0/16”宛のパケットは最長一致検索により、最短ルートである通信装置Ｂ経由の通信ルートではなく、通信装置Ｆ−通信装置Ｅ経由の通信ルートとなる。このように、経路集約は、通信パスの最短ルートを選択できなくなるという弊害を引き起こす場合がある。
【００１７】
さらに、経路集約時の他の問題点を説明する。図４６は、経路集約対象のネットワークが異なる通信装置の配下に接続された場合の問題点を説明するための説明図である。通信装置Ｃは、ネットワーク“10.2.0.0/16”を持ち、通信装置Ｄはネットワーク“10.3.0.0/16”を持っている。通信装置Ｂにおいて、通信装置Ｃとの間で経路制御プロトコルを動作させることにより、通信装置Ｃ配下のネットワーク“10.2.0.0/16を動的に学習することができる。また、通信装置Ｅにおいて、通信装置Ｄとの間で経路制御プロトコルを動作させることにより、通信装置Ｄ配下のネットワーク“10.3.0.0/16”を動的に学習することができる。通信装置Ｂ、通信装置Ｅにおいて、ネットワーク“10.2.0.0/15”の経路集約を各々設定している場合、ネットワーク“10.2.0.0/15”の集約経路が生成され、通信装置Ａ、通信装置Ｆに各々配信される。この状態で、通信装置Ａからネットワーク“10.3.0.0/16”宛のパケットを転送した場合、そのパケットは通信装置Ｂに転送され、通信装置Ｂにおいて廃棄される。また、通信装置Ｆからネットワーク“10.2.0.0/16”宛のパケットを転送した場合、そのパケットは通信装置Ｅに転送され、通信装置Ｅにおいて廃棄される。このように、経路集約対象のネットワークが異なる通信装置の配下に接続された場合、宛先に到達可能な通信パスの選択ができなくなり、パケット廃棄を引き起こす場合がある。
【先行技術文献】
【特許文献】
【００１８】
【特許文献１】特開２００２−２０８９４５号公報
【特許文献２】特開２００５−０５１７３６号公報
【発明の概要】
【発明が解決しようとする課題】
【００１９】
インターネット・エクスチェンジ（ＩＸ）やインターネット・サービス・プロバイダ（ＩＳＰ）によって使用されるルータやレイヤ３スイッチでは、インターネットで取り扱われる経路情報（「フルルート」と呼ばれる）を超える経路エントリをフォワーディングテーブル上で取り扱える必要がある。フルルートは、２００８年時点で２８万経路エントリを超えており、毎年２万経路エントリ程度の割合で増加している。そのため、経路エントリの収容能力として、通信装置当り、５０万から１００万程度の経路エントリが収容できることが要求されている。また、インターネットにおけるパケット通信量も年々増加しており、通信装置当り、数十ギガｂｐｓ（ギガは１０の９乗、すなわち１０億を示す。また、ｂｐｓは“Bit Per Second”の略であり、１秒当りのビット数を示す）から数百ギガｂｐｓ程度の転送性能が要求されており、通信回線当り、十ギガｂｐｓから百ギガｂｐｓ程度の転送性能が要求されている。この転送性能は６４バイトのパケット換算で、通信装置当り、数十メガｐｐｓから数百メガｐｐｓ（メガは１０の６乗、すなわち１００万を示す。また、ｐｐｓは“Packet Per Second”の略であり、１秒当りのパケット数を示す）であり、通信回線当り、十メガｐｐｓから百メガｐｐｓとなる。このため、このような大容量の経路エントリを取り扱うことが可能であり、かつ高速に検索できる技術が従来から要求されている。
【００２０】
ＣＡＭ検索方式における検索性能は、搭載するＣＡＭの検索性能に依存し、１チップで数十メガｐｐｓから百数十メガｐｐｓ程度である。ツリー検索（Ｈ／Ｗ）方式の検索性能は、フルルートにおけるツリーの検索段数（ツリーのノードを辿る回数：平均１０回程度）に依存し、ＣＡＭ検索方式での検索に比べ１０分の１程度の、数メガｐｐｓから十数メガｐｐｓ程度となる。また、ツリー検索（Ｓ／Ｗ）方式では、プログラムの実行時間が加わり、数百キロｐｐｓ（キロは１０の３乗、すなわち１０００を示す）から１メガｐｐｓ程度となる。同様に、ＣＡＭ・ツリー検索（Ｓ／Ｗ）方式では、受信したパケットの送信先アドレスがＣＡＭ上の経路エントリにヒットする場合と、ツリー上の経路エントリにヒットする場合があり、１メガｐｐｓから百数十メガｐｐｓ程度となる。
【００２１】
一方、収容能力では、ツリー検索で使用するＲＡＭは集積度高く、１チップで２５６メガバイト程度の容量を持ち、フルルートを十分に収容可能な容量を持つ（１つの経路エントリ当り、１００バイト程度）。ＣＡＭ検索方式におけるＣＡＭは、現在、１チップで４メガバイト程度の容量を持ち、１チップで２５６キロ程度の経路エントリを収容できる。
【００２２】
上述した通り、ＩＸやＩＳＰで要求される通信装置では、通信装置当り、数十メガｐｐｓから数百メガｐｐｓの転送性能（通信回線当り、十メガｐｐｓから百メガｐｐｓの転送性能）と、５００キロから１メガ程度の経路エントリを収容できる必要がある。従って、ＣＡＭ検索方式では要求される転送性能を満たすことはできる（高速の通信回線では、通信回線毎にＣＡＭを搭載する）が、フルルートを収容するためには複数のチップを搭載する必要があり、実装面積、消費電力、製造コストを増加させるという問題がある。ツリー検索方式を使用するツリー検索（Ｓ／Ｗ）方式、ツリー検索（Ｈ／Ｗ）方式、ＣＡＭ・ツリー検索（Ｓ／Ｗ）併用方式では、要求される経路エントリの収容能力は満たすことができるが、転送性能を満たすことはできない状況にある。
【００２３】
また、「背景技術」の欄で説明した通り、経路エントリ数を削減する１つの方法として、経路集約という技術がある。従来技術の経路集約は、経路集約しても矛盾が発生しないようにネットワークを設計し、構成情報により個々の集約経路を設定する必要がある。また、「背景技術」の欄で説明したように、経路集約しても矛盾が発生しないようにネットワークを設計していないネットワークにおいて、経路集約を行うと、最短の通信パスを選択できない場合や到達可能な通信パスを選択できない場合など、パケットの通信パスに矛盾が発生する場合がある。インターネットのようなネットワークでは、インターネットを構成する各ネットワークは個々の管理者（例えば、ＩＳＰ単位の管理者）によって設計、構築されており、インターネット全体のネットワーク構成を、経路集約できるように設計することはできず、また、個々の集約経路を構成情報により設定することも困難である。このような状況では、従来技術である、構成情報により静的に設定する静的経路の経路集約や経路制御プロトコルにより動的に学習する動的経路の経路集約は、適用が困難である。
【００２４】
また、従来技術の経路制御プロトコルにより動的に学習する動的経路の経路集約では、経路集約を行った通信装置が、配布する経路情報量を削減して、配布先の通信装置の経路情報量を削減することはできるが、経路集約を行った通信装置の経路情報量を削減することはできない。インターネットのようなネットワークでは、インターネットを構成する各ネットワークの通信装置は個々の管理者によって管理されており、管理者が異なる通信装置間では、経路集約を設定することはできない。
【００２５】
従って、本発明の目的は、インターネットのような、個々のネットワークを管理する管理者が異なることにより、経路集約できるように予めネットワークを設計することはできないような環境、または、構成情報などにより予め経路集約を設定できないような環境において、パケットの通信パスに矛盾を発生させること無く、フォワーディングテーブル容量よりも多くの経路エントリを取り扱うことができ、かつ高速にフォワーディングテーブルの経路エントリを検索することができる通信装置を提供することにある。
【課題を解決するための手段】
【００２６】
本発明は、上述の課題の少なくとも一部を解決するためになされたものであり、以下の形態又は適用例として実現することが可能である。
【００２７】
［適用例１］
通信回線を介して隣接する他の通信装置と接続される通信装置であって、構成情報により静的に設定された経路情報、または経路制御プロトコルを使用し動的に学習された経路情報を、宛先毎に、１つ以上の経路エントリとして保持するルーティングテーブルと、前記ルーティングテーブル内に保持された宛先毎の１つ以上の経路エントリから、宛先毎に、第一優先の経路エントリを選定する登録制御部と、フォワーディングテーブルと、前記登録制御部によって選定された前記経路エントリを前記フォワーディングテーブルに登録する経路登録部と、隣接する第１の通信装置からパケットを受信し、前記フォワーディングテーブルを参照することにより前記パケットの転送先を選択し、選択した転送先に基づいて、前記パケットを隣接する第２の通信装置に転送するパケット転送部と、を備え、前記登録制御部は、前記パケットの転送先として、前記第一優先の経路エントリのすべてを前記フォワーディングテーブルに登録した場合と同じ転送先が選択されるように、前記第一優先の経路エントリを加工して、前記第一優先の経路エントリの一部を、前記フォワーディングテーブルに登録する前記経路エントリとして選定することを特徴とする通信装置。
【００２８】
従来においては、ルーティングテーブル内に保持された宛先毎の１つ以上の経路エントリから、宛先毎に第一優先の経路エントリを選択し、その経路エントリのすべてをフォワーディングテーブルに登録していたのに対し、適用例１では、従来におけるフォワーディングテーブルに登録した場合と同じ転送先が選択されるように、第一優先の経路エントリを加工して、第一優先の経路エントリの一部を、フォワーディングテーブルに登録するようにしているため、適用例１によれば、フォワーディングテーブルに登録する経路エントリ数を削減することができ、フォワーディングテーブル容量よりも多くの経路エントリを取り扱うことが可能となる。また、適用例１は、従来における経路集約と異なり、他の通信装置に影響を与えることなく、また他の通信装置から影響を受けることなく、通信装置単体で実現することができる。これにより、個々の通信装置を管理する管理者が異なるために、経路集約できるように予めネットワークを設計できない環境、または構成情報により予め経路集約を設定できない環境においても、フォワーディングテーブルに登録する経路エントリ数の削減が可能となる。また、適用例１は、加工される経路エントリに識別情報を持つことにより、経路制御プロトコルを使用し、他の通信装置に経路情報を配布する場合において、本発明を適用しない場合と同じ経路情報の配布を可能とする。これにより、従来における経路集約で発生するような経路集約時におけるパケットの通信パスの矛盾を防止することができる。
【００２９】
また、適用例１では、上記した通り、ネットワークを構成する他の通信装置から影響を受けることなく、また他の通信装置に影響を与えることなく、フォワーディングテーブルで取り扱うことができる経路エントリ数よりも多くの経路エントリを取り扱うことができる。また、適用例１は、フォワーディングテーブルで取り扱うことができる経路エントリ数よりも多くの経路エントリを取り扱うことができることにより、一定量の経路エントリを取り扱うために必要なハードウェアの部品数を削減可能であり、ハードウェアの実装面積、消費電力、および通信装置の製造コストを低減できる。さらに、適用例１は、フォワーディングテーブルに登録する経路エントリ数を削減することにより、経路情報の収束性能を向上させることができる。
【００３０】
［適用例２］
適用例１に記載の通信装置において、前記登録制御部は、前記第一優先の経路エントリのうち、ある経路エントリの宛先が、他の経路エントリの宛先によって包含され、かつ、前記ある経路エントリの転送条件が、前記他の経路エントリの転送条件と同一である場合、前記ある経路エントリを、前記フォワーディングテーブルに登録する前記経路エントリとして選定しないことを特徴とする通信装置。
【００３１】
適用例２は、他の経路エントリによって包含され、かつ同じ転送条件を持つ経路エントリをフォワーディングテーブルに登録しないことで、フォワーディングテーブルに登録する経路エントリを削減し、フォワーディングテーブル容量を越える経路エントリを扱うことを可能とする。
【００３２】
［適用例３］
適用例１に記載の通信装置において、前記登録制御部は、前記第一優先の経路エントリのうち、ある経路エントリの宛先が、他の複数の経路エントリの宛先を組み合わせたものと同等となる場合、前記ある経路エントリを、前記フォワーディングテーブルに登録する前記経路エントリとして選定しないことを特徴とする通信装置。
【００３３】
適用例３は、経路エントリの宛先が現存する経路エントリを組み合わせたものと同等となる経路エントリが存在する場合に、その同等となる経路エントリをフォワーディングテーブルに登録しないことで、フォワーディングテーブルに登録する経路エントリを削減し、フォワーディングテーブル容量を越える経路エントリを扱うことを可能とする。
【００３４】
［適用例４］
適用例１に記載の通信装置において、前記登録制御部は、集約された経路エントリとして、前記第一優先の経路エントリのうち、複数の経路エントリを組み合わせたものと同等となる経路エントリを生成し、生成した前記集約経路エントリを、前記フォワーディングテーブルに登録する前記経路エントリとして選定し、集約される側の前記複数の経路エントリを、前記フォワーディングテーブルに登録する前記経路エントリとして選定しないことを特徴とする通信装置。
【００３５】
適用例４は、現存する経路エントリを組み合わせたものと同等となる集約経路を生成できる場合に、集約経路エントリを生成・登録し、集約元の経路エントリをフォワーディングテーブルに登録しないことで、フォワーディングテーブルに登録する経路エントリを削減し、フォワーディングテーブルを越える経路エントリを扱うことを可能とする。
【００３６】
［適用例５］
適用例１に記載の通信装置において、前記登録制御部は、集約された経路エントリとして、前記第一優先の経路エントリのうち、複数の経路エントリを組み合わせたものと同等となる経路エントリを生成する場合において、集約される側の前記複数の経路エントリのうち、一部の経路エントリが不足している場合に、不足している部分を補完する経路エントリを生成すると共に、前記集約経路エントリを生成し、生成した前記集約経路エントリ及び前記補完経路エントリを、前記フォワーディングテーブルに登録する前記経路エントリとして選定し、集約される側の前記複数の経路エントリを、前記フォワーディングテーブルに登録する前記経路エントリとして選定しないことを特徴とする通信装置。
【００３７】
適用例５は、現存する経路エントリの組み合わせでは同等となる代替の集約経路は生成できないが、補完する経路エントリを追加することで、同等の集約経路エントリを生成できる場合に、集約経路エントリと補完経路エントリを生成・登録し、集約元の経路エントリをフォワーディングテーブルに登録しないことで、フォワーディングテーブルに登録する経路エントリを削減し、フォワーディングテーブルを越える経路エントリを扱うことを可能とする。
【００３８】
［適用例６］
適用例１に記載の通信装置において、前記登録制御部は、集約された経路エントリとして、前記第一優先の経路エントリのうち、複数の経路エントリを組み合わせたものと同等となる経路エントリを生成する場合において、集約される側の前記複数の経路エントリのうち、一部の経路エントリが不足している場合に、不足している部分を補完する経路エントリを生成すると共に、前記集約経路エントリを生成し、生成した前記集約経路エントリを、前記フォワーディングテーブルに登録する前記経路エントリとして選定し、生成した前記補完経路エントリ及び集約される側の前記複数の経路エントリを、前記フォワーディングテーブルに登録する前記経路エントリとして選定しないことを特徴とする通信装置。
【００３９】
適用例６は、現存する経路エントリの組み合わせでは同等となる代替の集約経路エントリは生成できないが、補完する経路エントリを追加することで、同等の集約経路エントリを生成できる場合に、集約経路エントリを生成・登録し、補完経路エントリ、集約元の経路エントリをフォワーディングテーブルに登録しないことで、フォワーディングテーブルに登録する経路エントリを削減し、フォワーディングテーブルを越える経路エントリを扱うことを可能とする。なお、補完経路エントリ宛のパケットについては、集約経路エントリのネクストホップアドレスに対応する隣接する通信装置に転送されることにより、その隣接する通信装置において、廃棄されることになる。
【００４０】
［適用例７］
適用例１に記載の通信装置において、前記登録制御部は、前記第一優先の経路エントリの一部を、前記フォワーディングテーブルに登録する前記経路エントリとして選定するための経路エントリ設定方式として、前記第一優先の経路エントリのうち、ある経路エントリの宛先が、他の経路エントリの宛先によって包含され、かつ、前記ある経路エントリの転送条件が、前記他の経路エントリの転送条件と同一である場合、前記ある経路エントリを、前記フォワーディングテーブルに登録する前記経路エントリとして選定しない第１の経路エントリ設定方式と、前記第一優先の経路エントリのうち、ある経路エントリの宛先が、他の複数の経路エントリの宛先を組み合わせたものと同等となる場合、前記ある経路エントリを、前記フォワーディングテーブルに登録する前記経路エントリとして選定しない第２の経路エントリ設定方式と、集約された経路エントリとして、前記第一優先の経路エントリのうち、複数の経路エントリを組み合わせたものと同等となる経路エントリを生成し、生成した前記集約経路エントリを、前記フォワーディングテーブルに登録する前記経路エントリとして選定し、集約される側の前記複数の経路エントリを、前記フォワーディングテーブルに登録する前記経路エントリとして選定しない第３の経路エントリ設定方式と、集約された経路エントリとして、前記第一優先の経路エントリのうち、複数の経路エントリを組み合わせたものと同等となる経路エントリを生成する場合において、集約される側の前記複数の経路エントリのうち、一部の経路エントリが不足している場合に、不足している部分を補完する経路エントリを生成すると共に、前記集約経路エントリを生成し、生成した前記集約経路エントリ及び前記補完経路エントリを、前記フォワーディングテーブルに登録する前記経路エントリとして選定し、集約される側の前記複数の経路エントリを、前記フォワーディングテーブルに登録する前記経路エントリとして選定しない第４の経路エントリ設定方式と、集約された経路エントリとして、前記第一優先の経路エントリのうち、複数の経路エントリを組み合わせたものと同等となる経路エントリを生成する場合において、集約される側の前記複数の経路エントリのうち、一部の経路エントリが不足している場合に、不足している部分を補完する経路エントリを生成すると共に、前記集約経路エントリを生成し、生成した前記集約経路エントリを、前記フォワーディングテーブルに登録する前記経路エントリとして選定し、生成した前記補完経路エントリ及び集約される側の前記複数の経路エントリを、前記フォワーディングテーブルに登録する前記経路エントリとして選定しない第５の経路エントリ設定方式と、のうち、少なくとも２つの経路エントリ設定方式の適用が可能であることを特徴とする通信装置。
【００４１】
［適用例８］
適用例７に記載の通信装置において、適用可能な前記少なくとも２つの経路エントリ設定方式の中から、適用する経路エントリ設定方式の組み合わせが、予め設定されていることを特徴とする通信装置。
【００４２】
［適用例９］
適用例７に記載の通信装置において、前記登録制御部は、適用可能な前記少なくとも２つの経路エントリ設定方式の中から、適用する経路エントリ設定方式の組み合わせを、前記構成情報により静的に決定することを特徴とする通信装置。
【００４３】
［適用例１０］
適用例７に記載の通信装置において、前記登録制御部は、適用可能な前記少なくとも２つの経路エントリ設定方式の中から、適用する経路エントリ設定方式の組み合わせを、保持する前記経路情報の状況により動的に決定することを特徴とする通信装置。
【００４４】
フォワーディングテーブルに登録する経路エントリ数の削減で、より効果的な結果を生むために、適用例７に記載された、５つの経路エントリ設定方式のうちの適用可能な経路エントリ設定方式について、適用例８のように、適用する経路エントリ設定方式の組み合わせが、予め設定されていてもよい。また、適用例９のように、適用する経路エントリ設定方式の組み合わせを、構成情報により静的に決定するようにしてもよい。さらに、適用例１０のように、適用する経路エントリ設定方式の組み合わせを、保持する経路情報の状況により動的に決定するようにしてもよい。
【００４５】
［適用例１１］
適用例１ないし適用例１０のうちの任意の一つに記載の通信装置において、前記フォワーディングテーブルへの登録状況または前記ルーティングテーブルの保持状況を参照し得ることを特徴とする通信装置。
【００４６】
このように、例えば、ルーティングテーブルやフォワーディングテーブルの経路エントリの内容、およびフォワーディングテーブルへ登録された経路エントリ数、フォワーディングテーブルへの登録が抑止された経路エントリ数などを、運用者が参照できるようにしてもよい。
【００４７】
［適用例１２］
適用例１ないし適用例１０のうちの任意の一つに記載の通信装置において、前記フォワーディングテーブルへの登録状況に応じて運用者にアラームを通知し得ることを特徴とする通信装置。
【００４８】
このように、例えば、フォワーディングテーブルに登録された経路エントリ数が任意の閾値を超えた場合、または閾値を下回った場合などに、運用者にアラームを通知することができるようにしてもよい。
【００４９】
なお、本発明は、上記した通信装置などの装置発明の態様に限ることなく、経路エントリ設定方法などの方法発明としての態様で実現することも可能である。さらには、それら方法や装置を構築するためのコンピュータプログラムとしての態様や、そのようなコンピュータプログラムを記録した記録媒体としての態様など、種々の態様で実現することも可能である。
【図面の簡単な説明】
【００５０】
【図１】本発明の一実施例としての通信装置の構成を示すブロック図である。
【図２】図１におけるルーティング機構１１及びフォワーディング機構１２のハードウェア構成を示すブロック図である。
【図３】一般的なＲａｄｉｘツリーのノード、およびノードに接続される経路エントリの構造を示す構造図である。
【図４】一般的なＲａｄｉｘツリーの構造の一例を示す構造図である。
【図５】Ｒａｄｉｘツリーに経路エントリを追加する一般的な動作を説明するための説明図である。
【図６】経路エントリ設定方式の１つである包含経路エントリ設定方式を説明するための説明図である。
【図７】包含経路エントリ設定方式において、新たに経路エントリを追加した場合に、Ｒａｄｉｘツリーがどのように変化するかを説明するための説明図である。
【図８】包含経路エントリ設定方式において、新たに経路エントリを追加した場合の処理を示すフローチャートである。
【図９】包含経路エントリ設定方式において、新たに経路エントリを削除した場合の処理を示すフローチャートである。
【図１０】包含経路エントリ設定方式において、新たに経路エントリを変更した場合、Ｒａｄｉｘツリーがどのように変化するかを説明するための説明図である。
【図１１】包含経路エントリ設定方式において、新たに経路エントリを変更した場合の処理を示すフローチャートである。
【図１２】経路エントリ設定方式の１つである最長経路エントリ設定方式を説明するための説明図である。
【図１３】最長経路エントリ設定方式において、新たに経路エントリを追加した場合に、Ｒａｄｉｘツリーがどのように変化するかを説明するための説明図である。
【図１４】最長経路エントリ設定方式において、新たに経路エントリを追加した場合の処理を示すフローチャートである。
【図１５】最長経路エントリ設定方式において、新たに経路エントリを削除した場合の処理を示すフローチャートである。
【図１６】最長経路エントリ設定方式において、新たに経路エントリを変更した場合、Ｒａｄｉｘツリーがどのように変化するかを説明するための説明図である。
【図１７】最長経路エントリ設定方式において、新たに経路エントリを変更した場合の処理を示すフローチャートである。
【図１８】経路エントリ設定方式の１つである集約経路エントリ設定方式を説明するための説明図である。
【図１９】集約経路エントリ設定方式において、新たに経路エントリを追加した場合に、Ｒａｄｉｘツリーがどのように変化するかを説明するための説明図である。
【図２０】集約経路エントリ設定方式において、新たに経路エントリを追加した場合の処理を示すフローチャートである。
【図２１】集約経路エントリ設定方式において、新たに経路エントリを削除した場合の処理を示すフローチャートである。
【図２２】集約経路エントリ設定方式において、新たに経路エントリを変更した場合、Ｒａｄｉｘツリーがどのように変化するかを説明するための説明図である。
【図２３】集約経路エントリ設定方式において、新たに経路エントリを変更した場合の処理を示すフローチャートである。
【図２４】経路エントリ設定方式の１つである補完経路エントリ設定方式を説明するための説明図である。
【図２５】補完経路エントリ設定方式において、新たに経路エントリを追加した場合に、Ｒａｄｉｘツリーがどのように変化するかを説明するための説明図である。
【図２６】補完経路エントリ設定方式において、新たに経路エントリを追加した場合の動作を示すフローチャートである。
【図２７】補完経路エントリ設定方式において、新たに経路エントリを削除した場合の動作を示すフローチャートである。
【図２８】補完経路エントリ設定方式において、新たに経路エントリを変更した場合、Ｒａｄｉｘツリーがどのように変化するかを説明するための説明図である。
【図２９】補完経路エントリ設定方式において、新たに経路エントリを変更した場合の動作を示すフローチャートである。
【図３０】経路エントリ設定方式の１つである未登録補完経路エントリ設定方式を説明するための説明図である。
【図３１】適用する経路エントリ設定方式が予め設定されている場合において、経路エントリを追加した場合の処理フローを示すフローチャートである。
【図３２】適用する経路エントリ設定方式が予め設定されている場合において、経路エントリを削除した場合の処理フローを示すフローチャートである。
【図３３】適用する経路エントリ設定方式が予め設定されている場合において、経路エントリを変更した場合の処理フローを示すフローチャートである。
【図３４】適用する経路エントリ設定方式を構成情報により静的に決定する方法を説明するための説明図である。
【図３５】適用する経路エントリ設定方式を構成情報により静的に決定するための処理フローを示すフローチャートである。
【図３６】図３５における各経路エントリ設定方式の静的適用更新処理のフローを示すフローチャートである。
【図３７】適用する経路エントリ設定方式をフォワーディングテーブルの登録状況により動的に決定するための処理フローを示すフローチャートである。
【図３８】図３７における各経路エントリ設定方式の動的適用更新処理のフローを示すフローチャートである。
【図３９】包括経路エントリ設定方式の一括更新処理のフローを示すフローチャートである。
【図４０】最長経路エントリ設定方式の一括更新処理のフローを示すフローチャートである。
【図４１】集約経路エントリ設定方式の一括更新処理のフローを示すフローチャートである。
【図４２】補完経路エントリ設定方式の一括更新処理のフローを示すフローチャートである。
【図４３】静的経路の設定例を説明するための説明図である。
【図４４】動的経路の学習例を説明するための説明図である。
【図４５】経路集約時の問題点を説明するための説明図である。
【図４６】経路集約対象のネットワークが異なる通信装置の配下に接続された場合の問題点を説明するための説明図である。
【発明を実施するための形態】
【００５１】
以下、本発明の実施形態を、図を用いて説明する。なお、本発明は、構成情報により静的に設定された経路情報、または経路制御プロトコルを使用し動的に学習された経路情報を、ルーティングテーブルに保持し、宛先情報を管理する任意の通信装置において適用可能なものであり、実施形態の構成に限定するものではない。任意の通信装置とは、例えば、単一のルーティングテーブル、フォワーディングテーブルを持ち、パケットの転送を制御するルータやレイヤ３スイッチ、またはＩＰｖ４パケットのサービス種別やＩＰｖ６パケットのトラフィッククラス毎にルーティングテーブル、フォワーディングテーブルを持ち、サービス種別やトラフィッククラス毎にパケットの転送を制御するルータやレイヤ３スイッチ、または仮想プライベートネットワーク（ＶＰＮ：Virtual Private Network）毎にルーティングテーブル、フォワーディングテーブルを持ち、ＶＰＮ毎にパケットの転送を制御するＶＰＮ多重化機能を備えたルータやレイヤ３スイッチ、またはネットワークの経路情報を一括管理し、各通信装置に経路情報を配布するルートサーバーなどである。
【００５２】
本発明の実施例について以下の順序で説明する。
Ａ．通信装置の構成：
Ｂ．Ｒａｄｉｘツリー
Ｃ．経路エントリ設定方式
Ｃ−１．包含経路エントリ設定方式
Ｃ−２．最長経路エントリ設定方式
Ｃ−３．集約経路エントリ設定方式
Ｃ−４．補完経路エントリ設定方式
Ｃ−５．未登録補完経路エントリ設定方式
Ｄ．経路エントリ設定方式の適用方法
Ｄ−１．適用する経路エントリ設定方式が予め設定されている場合
Ｄ−２．適用する経路エントリ設定方式を構成情報により静的に決定する場合
Ｄ−３．適用する経路エントリ設定方式を登録状況により動的に決定する場合
Ｅ．経路エントリ設定方式を適用した通信装置における運用面での考慮点
【００５３】
Ａ．通信装置の構成：
図１は、本発明の一実施例としての通信装置の構成を示すブロック図である。通信装置１０は、物理層（レイヤ１）とデータリンク層（レイヤ２）に関する制御を行うＮＩＣ１３（ネットワーク・インタフェース・カード）と、ネットワーク層（レイヤ３）に関する転送処理を行うフォワーディング機構１２と、構成情報により静的に設定された経路情報や、経路制御プロトコルにより動的に学習された経路情報の管理を行うルーティング機構１１と、を備えている。
【００５４】
図２は、図１におけるルーティング機構１１及びフォワーディング機構１２のハードウェア構成を示すブロック図である。図２に示すように、ルーティング機構１１及びフォワーディング機構１２は、主として、ＣＰＵ５１２と、ＲＡＭ５１４と、ＣＡＭ５１６などによって構成される。なお、ＮＩＣ１３は、通信装置１０に複数搭載され、隣接する通信装置（図示せず）とＬＡＮ回線やＷＡＮ回線を通じて接続される。
【００５５】
始めに、経路情報を学習し、パケットの転送先を選定するために利用するフォワーディングテーブルの生成を行うルーティング機構１１について説明する。ルーティング機構１１は、経路制御プロトコルなどを使用し経路情報を学習する経路学習部１４と、経路制御プロトコルなどを使用して学習した経路情報をルーティングテーブルに登録する経路表作成部１５と、登録されたルーティングテーブルの経路エントリを加工し、フォワーディングテーブルに登録する経路エントリを選定する登録制御部１６と、登録制御部１６でフォワーディングテーブルに登録することが選定された経路エントリをフォワーディングテーブルに登録する経路登録部１７と、経路表作成部１５で登録された経路エントリ、および登録制御部１６で加工された経路エントリを保持するルーティングテーブル１８と、を備えている。これらのうち、経路学習部１４，経路表作成部１５，登録制御部１６及び経路登録部１７は、図２に示すＣＰＵ５１２が通信処理プログラムを実行することよって、実現される。また、ルーティングテーブル１８は、ＲＡＭ５１４上に構成される。なお、登録制御部１６が、本実施例の特徴部分である経路エントリ設定方式を処理する部位であり、この登録制御部１６を備えた通信装置が、請求項に記載の通信装置に相当する。
【００５６】
経路学習部１４は、ＩＰｖ４用のＲＩＰ、ＯＳＰＦ、ＢＧＰや、ＩＰｖ６用のＲＩＰｎｇ、ＯＳＰＦｖ３、ＢＧＰ４＋などの経路制御プロトコルを使用し、他の通信装置との間で経路情報の交換を行ない、経路情報を動的に学習する。また、構成情報などにより静的に設定された経路情報の学習なども行う。経路学習部１４は、各経路制御プロトコル毎に、それぞれ、その経路制御プロトコルを使用して学習した経路情報を元に、その経路制御プロトコルの経路選択基準に従い、宛先毎に最適な経路エントリを生成し、経路表作成部１５に引き渡す。
【００５７】
経路表作成部１５は、経路学習部１４から引き渡された経路エントリを、Ｒａｄｉｘツリーで形成されたルーティングテーブル１８に登録する。一般的に経路エントリの管理に使用されるツリー構造にはＲａｄｉｘツリー、Ｒａｄｉｓｈツリーなど様々なツリー構造が知られているが、本発明では、これらツリー構造を限定するものではない。
【００５８】
登録制御部１６は、上記の通り、本実施例の特徴部分である経路エントリ設定方式を処理する部位であり、経路表作成部１５で作成されるルーティングテーブル１８内の経路エントリに対して、上記経路エントリ設定方式を適用し、フォワーディングテーブル２２に登録する経路エントリを選定する。なお、かかる経路エントリ設定方式については、後ほど詳しく説明する。
【００５９】
経路登録部１７は、登録制御部１６でフォワーディングテーブル２２に登録することが選定された経路エントリを、フォワーディングテーブル２２に登録する。
【００６０】
次に、受信したパケットを隣接の通信装置などに転送するフォワーディング機構１２について説明する。フォワーディング機構１２は、パケットの受信処理を行う受信処理部１９と、パケットの転送先を選択する経路検索部２０と、選択された転送先にパケットの送信を行う送信処理部２１と、パケットの転送先を選択するために利用されるフォワーディングテーブル２２と、を備えている。これらのうち、受信処理部１９，経路検索部２０及び送信処理部２１は、パケット転送部２１Ａを構成しており、図２に示すＣＰＵ５１２が通信処理プログラムを実行することよって、実現される。また、フォワーディングテーブル２２は、ＣＡＭ５１６上に構成される。
【００６１】
図１の左側に位置するＮＩＣ１３は、隣接する通信装置からパケットを受信し、ＭＡＣ層などのデータリンク層に関する処理を実行した後、受信したパケットをフォワーディング機構１２内の受信処理部１９に引き渡す。
【００６２】
受信処理部１９は、そのＮＩＣ１３から引き渡されたパケットについて、正常性のチェックを行う。正常なパケットである場合は、経路検索部２０にそのパケットを引き渡す。また、異常なパケットである場合は、そのパケットを廃棄する。
【００６３】
経路検索部２０は、引き渡されたパケットからそのＩＰヘッダ内に設定されている送信先アドレスを取得し、その送信先アドレスに最長一致する経路エントリをフォワーディングテーブルから検索し、検索により得られた経路エントリのネクストホップアドレスを選択して、そのネクストホップアドレスとともに、パケットを送信処理部２１に引き渡す。
【００６４】
送信処理部２１は、経路検索部２０により選択されたネクストホップアドレスを元に、ＡＲＰ（Address Resolution  Protocol）情報と呼ばれる転送先のＩＰアドレスとＭＡＣアドレスとの対のテーブルから、転送先のＭＡＣアドレスを決定し、上記選択されたネクストホップアドレスに対応する通信装置と接続されるＮＩＣ１３、すなわち、図１の右側に位置するＮＩＣ１３に、決定したＭＡＣアドレスとともに、パケットを引き渡す。
【００６５】
パケットを引き渡されたＮＩＣ１３は、データリンク層に関する処理（ＭＡＣヘッダの生成など）を行ない、上記選択されたネクストホップアドレスに対応する隣接の通信装置に、パケットを転送する。
【００６６】
Ｂ．Ｒａｄｉｘツリー
図３は、一般的なＲａｄｉｘツリーのノード、およびノードに接続される経路エントリの構造を示す構造図である。Ｒａｄｉｘツリーは、ノードと呼ばれるエントリのツリー構造で構築される。ノード２３は、ネットワークアドレス、ネットワークマスク長、０側ポインタ、１側ポインタ、および経路エントリへのポインタから構成される。経路エントリ２４は、ネットワークアドレス、ネットワークマスク長、経路フラグ、ネクストホップアドレスのリストから構成される。ネクストホップアドレスのリストは、複数のネクストホップアドレスを登録することを可能とし、通信トラフィックを負荷分散するために使用される。経路エントリ２４はノード２３の経路エントリへのポインタで接続される。また、ある宛先への経路エントリが複数存在する場合は、経路エントリ２４の経路エントリへのポインタが次の経路エントリを接続する。
【００６７】
図４は、一般的なＲａｄｉｘツリーの構造の一例を示す構造図である。Ｒａｄｉｘツリーは、ノードをネットワークマスク長の短い順にツリー構造で構成される。この構造を実現するために、Ｒａｄｉｘツリーでは、各ノードをネットワークマスク長の短い順に０側ポインタ、１側ポインタを使用して接続する。
【００６８】
以降では、図４の凡例３０の形式を使用し、経路エントリを含むノードを表現する。凡例３０の左上フィールドの１番目（左側）の値Ａはネットワークアドレスを示し、２番目（右側）の値Ｍはネットワークマスク長を示す。凡例３０の左下フィールドの値Ｎは、ネクストホップアドレス、および経路フラグを示す。右上フィールドは０側ポインタを示し、右下フィールドは１側ポインタを示す。
【００６９】
一般的に、ＩＰｖ４のＩＰアドレスは３２ビット、ＩＰｖ６のＩＰアドレスは１２８ビットで表現されるが、ここでは、説明をわかりやすくするために、ネットワークアドレスを２進数４ビットで表現し、ネットワークマスク長を１０進数で表現する。ネットワークアドレスの“ｘ”は０または１の任意の値を示す。ネットワークアドレスとネットワークマスク長を合わせたものをネットワークと呼ぶ。ネクストホップアドレスはアルファベットで表現され、経路フラグのブラックホールビット（ブラックホールフラグ）やリジェクトビット（リジェクトフラグ）が設定されている場合は“−”として表現される。経路エントリが接続されたノードを実体ノードと呼び、実線で表現し、経路エントリが接続されないノードを分岐ノードと呼び、破線で表現する。あるノードの上位（ネットワークマスク長の短い方向）に接続された直近のノードを上位ノードと呼び、あるノードの上位に接続された直近の実体ノードを上位実体ノードと呼ぶ。また、あるノードの下位（ネットワークマスク長の長い方向）に接続された直近のノードを下位ノードと呼び、あるノードの下位に接続された直近の実体ノードを下位実体ノードと呼ぶ。さらに、あるノードを接続する上位ノードの他方のポインタ（０側ポインタ、または１側ポインタ）に接続されたノードを隣接ノードと呼び、あるノードを接続する上位ノードの他方のポインタに接続された実体ノードを隣接実体ノードと呼ぶ。
【００７０】
図４にはネットワーク“001x/3”、“0000/4”、“0001/4”、“0100/4”、“0110/4”、“1000/4”、“1001/4”、“1100/4”の実体ノードがあり、それら実体ノードをＲａｄｉｘツリーでのツリー構造をなすために、ネットワーク“xxxx/0”、“0xxx/1”、“1xxx/1”、“00xx/2”、“01xx/2”、“000x/3”、“100x/3”の分岐ノードがある。ノード３１はネットワーク“xxxx/0”を持つ分岐ノードである。また、ノード３１はネットワークマスク長の最も短いノードであり、ルートノードとも呼ばれる。ノードの０側ポインタ配下には、ネットワークアドレスの、ネットワークマスク長に一致するビットが０であるノードが、ネットワークマスク長の短い順に接続される。ノードの１側ポインタ配下には、ネットワークアドレスの、ネットワークマスク長に一致するビットが１であるノードが、ネットワークマスク長の短い順に接続される。すなわち、ノード３１の０側ポインタにはネットワークアドレスの第０ビット目（最上位ビットを０とした連番で表現する）が０であるネットワーク“0xxx/1”を持つノード３２が接続される。ノード３１の１側ポインタにはネットワークアドレスの第０ビット目が１であるネットワーク“1xxx/1”を持つノード３３が接続される。同様に、ノード３２の０側ポインタにはネットワークアドレスの第１ビット目が０であるネットワーク“00xx/2”を持つノード３４が接続される。ノード３２の１側ポインタにはネットワークアドレスの第１ビット目が１であるネットワーク“01xx/2”を持つノード３５が接続される。以下同様に、必要に応じて分岐ノードが接続され、ネットワーク“001x/3”、“0000/4”、“0001/4”、“0100/4”、“0110/4”、“1000/4”、“1001/4”、“1100/4”の実体ノードを持つＲａｄｉｘツリーが構成される。
【００７１】
図５は、Ｒａｄｉｘツリーに経路エントリを追加する一般的な動作を説明するための説明図である。Ｒａｄｉｘツリーに経路エントリを追加するための一般的な動作パターンとしては、図５（ａ）〜（ｄ）に示す４種類がある。
【００７２】
１番目のパターンは、図５（ａ）に示すように、追加する経路エントリのネットワークが、既存の分岐ノードのネットワークに一致する場合である。その際は、その経路エントリを既存の分岐ノードに追加する。すなわち、図５（ａ）に示すように、分岐ノードであるノード４１に、追加する経路エントリを接続し、そのノード４１を、経路エントリが接続された実体ノードとする。
【００７３】
２番目のパターンは、図５（ｂ）に示すように、追加する経路エントリのネットワークに一致する分岐ノードが存在せず、その経路エントリを持つ実体ノードを接続すべき上位ノードのポインタにノードが存在しない場合である。その際は、その経路エントリを既存のノードの子ノードして追加する。すなわち、図５（ｂ）に示すように、経路エントリを持つ実体ノード４１を生成して、上位ノード４０のポインタに、その実体ノード４１を接続する。
【００７４】
３番目のパターンは、図５（ｃ）に示すように、追加する経路エントリのネットワークに一致するノードが存在せず、その経路エントリを持つ実体ノードを接続すべき上位ノードのポインタに、ノードが存在する場合である。その際は、その経路エントリを既存のノードの中間ノードとして追加する。すなわち、図５（ｃ）に示すように、経路エントリを持つ実体ノード４１を生成し、上位ノード４０と子ノード４２の間に、その実体ノード４１を接続する。
【００７５】
４番目のパターンは、図５（ｄ）に示すように、追加するネットワークに一致するノードが存在せず、その経路エントリを持つ実体ノードを接続すべき上位ノードのポインタに、その実体ノードに従属しないノードが存在する場合である。その際は、その経路エントリを分岐ノードとともに追加する。すなわち、図５（ｄ）に示すように、上位ノード４０に接続される分岐ノード４１を生成するとともに、経路エントリを持つ実体ノード４３を生成し、分岐ノード４１に、生成した実体ノード４３と既存の下位のノード４２を接続する。
【００７６】
なお、Ｒａｄｉｘツリーから経路エントリを削除する一般的な動作は、上記において、説明した追加する動作と逆の動作により行われる。
【００７７】
次に、図４のＲａｄｉｘツリーを利用して、パケットの送信先アドレスに最長一致する経路エントリの一般的な検索方法を説明する。パケットの送信先アドレスが“0011”である場合、まず、送信先アドレスとネットワークマスク長の最も短いノード３１のネットワークアドレスが一致するかを判定する。送信先アドレス“0011”とノード３１のネットワークアドレス“xxxx”は一致するため、次に、ノード３１のネットワークマスク長に一致する送信先アドレスのビット（第０ビット）が０か１か判定される。このとき、そのビットは０により、０側ポインタに接続されたノード３２に進む。同様に、送信先アドレスとノード３２のネットワークアドレスが一致するかを判定する。送信先アドレス“0011”とノード３２のネットワークアドレス“0xxx”は一致するため、ノード３２のネットワークマスク長に一致する送信先アドレスのビット（第１ビット）が０か１か判定される。このとき、そのビットは０により、０側ポインタに接続されるノード３４に進む。同様に、送信先アドレスとノード３４のネットワークアドレスが一致するかを判定する。送信先アドレス“0011”とノード３４のネットワークアドレス“00xx”は一致するため、ノード３４のネットワークマスク長に一致する送信先アドレスのビット（第２ビット）が０か１か判定される。このとき、そのビットは１により、１側ポインタに接続されるノード３６に進む。最後に、送信先アドレスとノード３６のネットワークアドレスが一致するかを判定する。送信先アドレス“0011”とノード３６のネットワークアドレス“001x”は一致するため、ノード３６のネットワークマスク長に一致するビット（第３ビット）が０か１か判定される。このとき、そのビットは１であるが、１側ポインタに接続されたノードが存在しないことにより、ノード３６が、最長一致の経路エントリとして、選択される。
【００７８】
Ｃ．経路エントリ設定方式
次に、本実施例の特徴部分である経路エントリ設定方式について説明する。前述したとおり、登録制御部１６は、ルーティングテーブル１８内の経路エントリに対して、この経路エントリ設定方式を適用して、フォワーディングテーブル２２に登録する経路エントリを選定する。本実施例において、かかる経路エントリ設定方式は、フォワーディングテーブル２２に登録する経路エントリ数の削減を実現することが可能であり、包含経路エントリ設定方式、最長経路エントリ設定方式、集約経路エントリ設定方式、補完経路エントリ設定方式、未登録補完経路エントリ設定方式の５種類の設定方式を含んでいる。以下、各経路エントリ設定方式について、順に説明する。
【００７９】
Ｃ−１．包含経路エントリ設定方式
図６は、経路エントリ設定方式の１つである包含経路エントリ設定方式を説明するための説明図である。図６において、（ａ）は一般的なＲａｄｉｘツリーを示し、（ｂ）は、包含経路エントリ設定方式を適用した場合のＲａｄｉｘツリーを示す。
【００８０】
包含経路エントリ設定方式では、Ｒａｄｉｘツリーのノードにフォワーディングテーブル２２への登録要否を示す情報を持つ。以降の説明で使用するノードの表記は、図４の凡例３０で示した表記に加え、左下フィールドの２番目の値が、登録要否の情報を示す。この値が“０”の場合は登録対象であることを示し、“１”（“０”以外）の場合は登録対象外であることを示す。また、分岐ノードは、常にフォワーディングテーブル２２に登録することは無く“−”で示す。
【００８１】
包含経路エントリ設定方式は、ある経路エントリの宛先が他の経路エントリの宛先によって包含され、かつ同一転送条件である場合に、包含される側の経路エントリをフォワーディングテーブル２２に登録しないことにより、フォワーディングテーブル２２に登録される経路エントリ数を削減し、フォワーディングテーブル容量以上の経路エントリを取り扱うことを可能とするものである。
【００８２】
図６のＲａｄｉｘツリーにおいて、送信先アドレス”000x”（ｘは０または１の任意値）宛のパケットは、ネットワーク“000x/3”を持つ実体ノード５１の経路エントリに基づき、ネクストホップＡに転送される。しかしながら、実体ノード５１のネットワーク”000x/3”は、実体ノード５０のネットワーク”00xx/2”に包含され、かつ同一転送条件を持っている。このため、実体ノード５１の経路エントリがフォワーディングテーブル２２に存在していなくても、上記の送信先アドレス宛のパケットは実体ノード５０の経路エントリに基づき、ネクストホップＡに転送される。このように、宛先が上位の実体ノードによって包含され、かつ同一の転送条件を持つ場合、その経路エントリはフォワーディングテーブルに登録しなくても同等の転送先を得ることができる。これにより、包含経路エントリ設定方式を適用した場合、図６（ｂ）に示すように、実体ノード５１はフォワーディングテーブル２２への登録が抑止され、フォワーディングテーブル２２に登録される経路エントリ数が削減される。なお、転送条件とは、ネクストホップアドレスと経路フラグを指す。
【００８３】
図８は、包含経路エントリ設定方式において、新たに経路エントリを追加した場合の処理を示すフローチャートである。このフローチャートは、経路表作成部１５において、Ｒａｄｉｘツリーに経路エントリを追加した後に実行される。なお、図８を含む、後述するフローチャートにおいて、“Ｙ“はイエスを示し、“Ｎ“はノーを示す。
【００８４】
新たに経路エントリが追加された場合、追加実体ノードと上位実体ノードの転送条件が同一かをチェックする（Ｓ７０）。追加実体ノードとは、追加する経路エントリを持つ実体ノードを指す。そのチェック結果が同一である場合、追加実体ノードは上位実体ノードに包含され、かつ同一の転送条件を持つことを意味する。これにより、追加実体ノードの経路エントリはフォワーディングテーブル２２に登録する必要は無く、追加実体ノードを登録対象外に設定する（Ｓ７１）。また、追加実体ノードの下位実体ノードは同一の転送条件を持つ上位実体ノードによって既に登録抑止されているため、経路エントリ追加に伴う処理は必要ない。次に、上記のチェック結果が同一でない場合、追加実体ノードの各下位実体ノードに対し、Ｓ７３−Ｓ７５間の処理を行う（Ｓ７２）。追加実体ノードと下位実体ノードの転送条件が同一かをチェックし（Ｓ７３）、同一である場合、下位実体ノードは追加実体ノードに包含され、かつ同一の転送条件であるため、フォワーディングテーブル２２に登録する必要は無く、下位実体ノードを登録対象外に設定する（Ｓ７４）。同一でない場合、転送条件が異なるため、フォワーディングテーブル２２への登録が必要であり、下位実体ノードを登録対象に設定する（Ｓ７５）。このような処理の後、経路登録部１７において、登録要否の情報が変化した経路エントリに対し、フォワーディングテーブル２２の更新を行う。なお、フォワーディングテーブル２２の更新順序は、フォワーディングテーブル更新処理中の一時的な経路エントリ未登録状態によるパケット廃棄を防止するために、登録抑止解除された経路エントリ、登録抑止された経路エントリの順で行う。
【００８５】
図７は、包含経路エントリ設定方式において、新たに経路エントリを追加した場合に、Ｒａｄｉｘツリーがどのように変化するかを説明するための説明図である。図７において、（ａ）が経路エントリ追加前の状態を示し、（ｂ）が経路エントリ追加後の状態を示している。包含経路エントリ設定方式において、図７（ａ）に示すＲａｄｉｘツリーに、新たにネットワーク“00xx/2”、“01xx/2”の経路エントリを追加した場合、図７（ｂ）に示すように、実体ノード６４が、宛先を包含し、かつ同一転送条件を持つ実体ノード６１によって、登録抑止され、実体ノード６５が、宛先を包含し、かつ同一転送条件を持つ実体ノード６２によって、登録抑止され、実体ノード６２が、宛先を包含し、かつ同一転送条件を持つ実体ノード６０によって、登録抑止されている。
【００８６】
図７に示すＲａｄｉｘツリーを用いて、図８のフローチャートの動作を説明する。図７（ａ）において、新たにネットワーク“00xx/2”を持つ経路エントリが追加された場合、追加実体ノード６１と上位実体ノード６０の転送条件が同一かをチェックする（Ｓ７０）。ここでは、同一でないため、次に、追加実体ノード６１の各下位実体ノード６３、６４に対し、Ｓ７３−Ｓ７５間の処理を行う（Ｓ７２）。追加実体ノード６１と下位実体ノード６３、６４の転送条件が同一かをチェックする（Ｓ７３）。ここでは、同一である下位実体ノード６４を登録対象外に設定し（Ｓ７４）、同一でない下位実体ノード６３を登録対象に設定する（Ｓ７５）。また、新たにネットワーク“01xx/2”を持つ経路エントリが追加された場合、追加実体ノード６２と上位実体ノード６０の転送条件が同一かをチェックする（Ｓ７０）。ここでは、同一であるため、追加実体ノード６２を登録対象外に設定する（Ｓ７１）。以上により、図７（ｂ）に示すようなＲａｄｉｘツリーが形成される。
【００８７】
図９は、包含経路エントリ設定方式において、新たに経路エントリを削除した場合の処理を示すフローチャートである。このフローチャートは、経路表作成部１５において、Ｒａｄｉｘツリーから経路エントリを削除する前に実行される。
【００８８】
新たに経路エントリが削除された場合、削除実体ノードと上位実体ノードの転送条件が同一かをチェックする（Ｓ８０）。ここで、削除実体ノードとは、削除する経路エントリを持つ実体ノードを指す。上記のチェック結果が同一である場合、下位実体ノードに対する上位実体ノードの転送条件に変化は発生しないため、下位実体ノードに対する処理は必要ない。上記のチェック結果が同一でない場合、削除実体ノードの各下位実体ノードに対し、Ｓ８２−Ｓ８４間の処理を行う（Ｓ８１）。上位実体ノードと下位実体ノードの転送条件が同一かをチェックする（Ｓ８２）。同一である場合に、下位実体ノードは上位実体ノードに包含され、同一転送条件であるため、フォワーディングテーブル２２に登録する必要は無く、下位実体ノードを登録対象外に設定する（Ｓ８３）。同一でない場合に、下位実体ノードは上位実体ノードと転送条件が異なるため、フォワーディングテーブル２２に登録する必要があり、下位実体ノードを登録対象に設定する（Ｓ８４）。このような処理の後、経路登録部１７において、登録要否の情報が変化した経路エントリに対し、登録抑止解除された経路エントリ、登録抑止された経路エントリの順で、フォワーディングテーブル２２の更新を行う。
【００８９】
図７に示すＲａｄｉｘツリーを用いて、図９のフローチャートの動作を説明する。図７（ｂ）において、新たにネットワーク“00xx/2”を持つ経路エントリが削除された場合、削除実体ノード６１と上位実体ノード６０の転送条件が同一かをチェックする（Ｓ８０）。ここでは、同一でないため、削除実体ノード６１の各下位実体ノード６３、６４に対し、Ｓ８２−Ｓ８４間の処理を行う（Ｓ８１）。上位実体ノード６０と下位実体ノード６３、６４の転送条件が同一かをチェックする（Ｓ８２）。ここでは、同一である下位実体ノード６３を登録対象外に設定し（Ｓ８３）、同一でない下位実体ノード６４を登録対象に設定する（Ｓ８４）。また、新たにネットワーク“01xx/2”を持つ経路エントリが削除された場合、同様に削除実体ノード６２と上位実体ノード６０の転送条件が同一かをチェックする（Ｓ８０）。ここでは、同一であるため、以降の処理はない。以上により、図７（ｂ）に示すＲａｄｉｘツリーから、ネットワーク“00xx/2”と“01xx/2”を持つ経路エントリが追加される前と同一の、図７（ａ）に示すＲａｄｉｘツリーに戻される。
【００９０】
図１１は、包含経路エントリ設定方式において、新たに経路エントリを変更した場合の処理を示すフローチャートである。このフローチャートは、経路表作成部１５において、Ｒａｄｉｘツリーの経路エントリを変更した後に実行される。
【００９１】
新たに経路エントリが変更された場合、変更実体ノードと上位実体ノードの転送条件が同一かをチェックする（Ｓ１００）。変更実体ノードとは、変更する経路エントリを持つ実体ノードを指す。上記のチェック結果が同一である場合、変更実体ノードは上位実体ノードに包含され、同一転送条件であるため、フォワーディングテーブル２２に登録する必要は無く、変更実体ノードを登録対象外に設定する（Ｓ１０１）。上記のチェック結果が同一でない場合、変更実体ノードは上位実体ノードと異なる転送条件であるため、フォワーディングテーブル２２に登録する必要があり、変更実体ノードを登録対象に設定する（Ｓ１０２）。次に、変更実体ノードの各下位実体ノードに対し、Ｓ１０４−Ｓ１０６間の処理を行う（Ｓ１０３）。変更実体ノードと下位実体ノードの転送条件が同一かをチェックする（Ｓ１０４）。同一である場合は、下位実体ノードは変更実体ノードに包含され、かつ同一転送条件であるため、フォワーディングテーブル２２に登録する必要は無く、下位実体ノードを登録対象外に設定する（Ｓ１０５）。同一でない場合は、下位実体ノードは変更実体ノードと異なる転送条件であるため、フォワーディングテーブル２２に登録する必要があり、下位実体ノードを登録対象に設定する（Ｓ１０６）。このような処理の後、経路登録部１７において、登録要否の情報が変化した経路エントリに対し、登録抑止解除された経路エントリ、登録抑止された経路エントリの順で、フォワーディングテーブル２２の更新を行う。
【００９２】
図１０は、包含経路エントリ設定方式において、新たに経路エントリを変更した場合、Ｒａｄｉｘツリーがどのように変化するかを説明するための説明図である。図１０において、（ａ）が経路エントリ変更前の状態を示し、（ｂ）が経路エントリ変更後の状態を示している。包含経路エントリ設定方式において、図１０（ａ）に示すＲａｄｉｘツリーにて、ネットワーク“00xx/2”を持つ経路エントリの転送条件を変更した場合、図１０（ｂ）に示すように、実体ノード９３が、宛先を包含し、かつ同一転送条件を持つ実体ノード９１によって、登録抑止されている。
【００９３】
図１０に示すＲａｄｉｘツリーを用いて、図１１のフローチャートの動作を説明する。図１０（ａ）において、新たにネットワーク“00xx/2”を持つ経路エントリの転送条件が変更（ネクストホップＡからＢに変更）された場合、変更実体ノード９１と上位実体ノード９０の転送条件が同一かをチェックする（Ｓ１００）。ここでは、同一でないため、変更実体ノード９１を登録対象に設定する（Ｓ１０２）。次に、変更実体ノード９１の各下位実体ノード９２、９３に対し、Ｓ１０４−Ｓ１０６間の処理を行う（Ｓ１０３）。変更実体ノード９１と下位実体ノード９２，９３の転送条件が同一かをチェックする（Ｓ１０４）。同一である下位実体ノード９３を登録対象外に設定し（Ｓ１０５）、同一転送条件でない下位実体ノード９２を登録対象に設定する（Ｓ１０６）。以上により、図１０（ｂ）に示すようなＲａｄｉｘツリーが形成される。
【００９４】
また、図１０（ｂ）において、新たにネットワーク“00xx/2”を持つ経路エントリの転送条件が変更（ネクストホップＢからＡに変更）された場合、変更実体ノード９１と上位実体ノード９０の転送条件は同一かをチェックする（Ｓ１００）。ここでは、同一であるため、変更実体ノード９１を登録対象外に設定する（Ｓ１０１）。次に、変更実体ノード９１の各下位実体ノード９２、９３に対し、Ｓ１０４−Ｓ１０６間の処理を行う（Ｓ１０３）。変更実体ノード９１と下位実体ノード９２，９３の転送条件は同一かをチェックする（Ｓ１０４）。同一である下位実体ノード９２を登録対象外に設定し（Ｓ１０５）、同一でない下位実体ノード９３を登録対象に設定する（Ｓ１０６）。以上により、図１０（ｂ）に示すＲａｄｉｘツリーから、ネットワーク“00xx/2”を持つ経路エントリが変更される前と同一の、図１０（ａ）に示すＲａｄｉｘツリーに戻される。
【００９５】
Ｃ−２．最長経路エントリ設定方式
図１２は、経路エントリ設定方式の１つである最長経路エントリ設定方式を説明するための説明図である。図１２において、（ａ）は一般的なＲａｄｉｘツリーを示し、（ｂ）は、最長経路エントリ設定方式を適用した場合のＲａｄｉｘツリーを示す。
【００９６】
最長経路エントリ設定方式では、図６で説明した包含経路エントリ設定方式の場合と同様に、Ｒａｄｉｘツリーのノードにフォワーディングテーブル２２への登録要否を示す情報を持つ。以降の説明で使用するノードの表記は、図６で示したノードの表記と同様に、左下フィールドの２番目の値が登録要否の情報を示す。この値が“０”の場合は登録対象であることを示し、“２”（“０”以外）の場合は登録対象外であることを示す。すなわち、左下フィールドの２番目の値として、図６で説明した包含経路エントリ設定方式により登録抑止されたノードでは“１”が設定され、この最長経路エントリ設定方式により登録抑止されたノードでは“２”が設定され、複数の経路エントリ設定方式で登録抑止されたノードでは各経路エントリ設定方式での設定値の合計値が設定される。また、分岐ノードは、常にフォワーディングテーブル２２に登録することは無く“−”で示す。
【００９７】
最長経路エントリ設定方式は、ある経路エントリの宛先が任意の複数の経路エントリの宛先を組み合わせたものと同等となる場合に、そのある経路エントリをフォワーディングテーブル２２に登録しないことにより、フォワーディングテーブル２２に登録する経路エントリ数を削減し、フォワーディングテーブル容量以上の経路エントリを取り扱うことを可能とするものである。
【００９８】
図１２のＲａｄｉｘツリーにおいて、送信先アドレス“000x”（ｘは０または１の任意値）宛のパケットは、ネットワーク“000x/3”を持つ実体ノード１１１の経路エントリに基づき、ネクストホップＢに転送される。送信先アドレス“001x”（ｘは０または１の任意値）宛のパケットは、ネットワーク“001x/3”を持つ実体ノード１１２の経路エントリに基づき、ネクストホップＣに転送される。このため、実体ノード１１１と実体ノード１１２の経路エントリの宛先を組み合わせたものと同等のネットワーク“00xx/2”を持つ実体ノード１１０の経路エントリが、パケットの転送に使用されることはなく、実体ノード１１１と実体ノード１１２の経路エントリがフォワーディングテーブル２２に存在すれば、実体ノード１１０の経路エントリはフォワーディングテーブル２２に存在していなくても、上記の送信先アドレス宛のパケットは実体ノード１１１、１１２の経路エントリに基づき、適切なネクストホップに転送される。このように、下位実体ノードの宛先の組み合わせが上位実体ノードの宛先と同等となる場合に、上位実体ノードの経路エントリをフォワーディングテーブル２２に登録しなくても同等の転送先を得ることができる。これにより、最長経路エントリ設定方式を適用した場合、図１２（ｂ）に示すように、実体ノード１１０はフォワーディングテーブル２２への登録が抑止され、フォワーディングテーブル２２に登録される経路エントリ数が削減される。
【００９９】
図１４は、最長経路エントリ設定方式において、新たに経路エントリを追加した場合の処理を示すフローチャートである。このフローチャートは、経路表作成部１５において、Ｒａｄｉｘツリーに経路エントリを追加した後に実行される。
【０１００】
新たに経路エントリが追加された場合、隣接ノード、上位ノードが実体ノードであり、かつ追加実体ノード、隣接実体ノード、上位実体ノードの転送条件が同一でなく、かつ追加実体ノードと隣接実体ノードのネットワークマスク長が同一であり、かつ上位実体ノードと追加実体ノードのネットワークマスク長の差分が１であるかをチェックする（Ｓ１３０）。このチェック条件は、上位実体ノードの宛先が、追加実体ノードと隣接実体ノードの宛先を組み合わせたものと同等となることを意味する。また、このチェック条件のうち、「追加実体ノード、隣接実体ノード、上位実体ノードの転送条件が同一でなく」という条件は、最長経路エントリ設定方式を他の経路エントリ設定方式（包含経路エントリ設定方式、集約経路エントリ設定方式）と併用する場合において、相互抑止対象とならないための条件であり、最長経路エントリ設定方式を単独で適用する場合には必要ない。従って、上記のチェック条件を満足する場合は、上位実体ノードの経路エントリはフォワーディングテーブル２２に登録する必要は無く、上位実体ノードを登録対象外に設定する（Ｓ１３１）。次に、下位ノードが実体ノードであり、かつ追加実体ノード、下位実体ノードの転送条件が同一でなく、かつ下位実体ノードのネットワークマスク長が同一であり、かつ、追加実体ノードと下位実体ノードのネットワークマスク長の差分が１であるかをチェックする（Ｓ１３２）。このチェック条件は、追加実体ノードの宛先が、下位実体ノードの宛先を組み合わせたものと同等となることを意味する。また、このチェック条件のうち、「追加実体ノード、下位実体ノードの転送条件が同一でなく」という条件は、上記と同様、相互抑止対象とならないための条件であり、最長経路エントリ設定方式を単独で適用する場合には必要ない。これにより、上記のチェック条件を満足する場合、追加実体ノードの経路エントリはフォワーディングテーブル２２に登録する必要は無く、追加実体ノードを登録対象外に設定する（Ｓ１３３）。このような処理の後、経路登録部１７において、登録要否の情報が変化した経路エントリに対し、登録抑止解除された経路エントリ、登録抑止された経路エントリの順で、フォワーディングテーブルの更新を行う。
【０１０１】
図１３は、最長経路エントリ設定方式において、新たに経路エントリを追加した場合に、Ｒａｄｉｘツリーがどのように変化するかを説明するための説明図である。図１３において、（ａ）が経路エントリ追加前の状態を示し、（ｂ）が経路エントリ追加後の状態を示している。最長経路エントリ設定方式において、図１３（ａ）に示すＲａｄｉｘツリーに、ネットワーク“000x/3”を持つ経路エントリを追加した場合、図１３（ｂ）に示すように、実体ノード１２０が、同一の宛先を持ち、かつ異なる転送条件を持つ実体ノード１２１と１２２によって、登録抑止され、実体ノード１２１が、同一の宛先を持ち、かつ異なる転送条件を持つ実体ノード１２３と１２４によって、登録抑止されている。
【０１０２】
図１３に示すＲａｄｉｘツリーを用いて、図１４のフローチャートの動作を説明する。図１３（ａ）において、新たにネットワーク“000x/3”を持つ経路エントリが追加された場合、隣接ノード１２２、上位ノード１２０が実体ノードであり、かつ追加実体ノード１２１、隣接実体ノード１２２、上位実体ノード１２０の転送条件が同一でなく、かつ追加実体ノード１２１と隣接実体ノード１２２のネットワークマスク長が同一であり、かつ、上位実体ノード１２０と追加実体ノード１２１のネットワークマスク長の差分が１であるかをチェックする（Ｓ１３０）。ここでは、このチェック条件を満足するため、上位実体ノード１２０を登録対象外に設定する（Ｓ１３１）。次に、下位ノード１２３、１２４が実体ノードであり、かつ追加実体ノード１２１、下位実体ノード１２３、１２４の転送条件が同一でなく、かつ下位実体ノード１２３、１２４のネットワークマスク長が同一であり、かつ追加実体ノード１２１と下位実体ノード１２３、１２４のネットワークマスク長の差分が１であるかをチェックする（Ｓ１３２）。ここでは、このチェック条件を満足するため、追加実体ノード１２１を登録対象外に設定する（Ｓ１３３）。以上により、図１３（ｂ）に示すようなＲａｄｉｘツリーが形成される。
【０１０３】
図１５は、最長経路エントリ設定方式において、新たに経路エントリを削除した場合の処理を示すフローチャートである。このフローチャートは、経路表作成部１５において、Ｒａｄｉｘツリーから経路エントリを削除する前に実行される。
【０１０４】
新たに経路エントリが削除された場合、上位ノードが実体ノードであり、かつ上位実体ノードが最長経路エントリ設定方式で登録抑止された実体ノードかをチェックする（Ｓ１４０）。このチェック条件を満足する場合、経路エントリの削除に伴い、登録抑止条件（Ｓ１３０）を満足しなくなるため、上位実体ノードを登録対象に設定する（Ｓ１４１）。このような処理の後、経路登録部１７において、登録要否が変化した経路エントリに対し、登録抑止が解除された経路エントリ、登録抑止された経路エントリの順で、フォワーディングテーブル２２の更新を行う。
【０１０５】
図１３に示すＲａｄｉｘツリーを用いて、図１５のフローチャートの動作を説明する。図１３（ｂ）において、新たにネットワーク“000x/3”を持つ経路エントリが削除された場合、上位ノード１２０が実体ノードであり、かつ上位実体ノード１２０が最長経路エントリ設定方式で登録抑止された実体ノードかをチェックする（Ｓ１４０）。ここでは、このチェック条件を満足するため、上位実体ノード１２０を登録対象に設定する（Ｓ１４１）。以上により、図１３（ｂ）に示すＲａｄｉｘツリーから、ネットワーク“000x/3”持つ経路エントリが追加される前の同一の、図１３（ａ）に示すＲａｄｉｘツリーに戻される。
【０１０６】
図１７は、最長経路エントリ設定方式において、新たに経路エントリを変更した場合の処理を示すフローチャートである。このフローチャートは、経路表作成部１５において、Ｒａｄｉｘツリーの経路エントリを変更した後に実行される。
【０１０７】
新たに経路エントリが変更された場合、隣接ノード、上位ノードが実体ノードであり、かつ変更実体ノード、隣接実体ノード、上位実体ノードの転送条件が同一でなく、かつ変更実体ノードと隣接実体ノードのネットワークマスク長が同一であり、かつ変更実体ノードと上位実体ノードのネットワークマスク長の差分が１であるかをチェックする（Ｓ１６０）。このチェック条件を満足する場合、上位実体ノードを登録対象外に設定する（Ｓ１６１）。満足しない場合、上位実体ノードを登録対象に設定する（Ｓ１６２）。このような処理の後、経路登録部１７において、登録要否が変化した経路エントリに対し、登録抑止解除された経路エントリ、登録抑止された経路エントリの順で、フォワーディングテーブル２２の更新を行う。
【０１０８】
図１６は、最長経路エントリ設定方式において、新たに経路エントリを変更した場合、Ｒａｄｉｘツリーがどのように変化するかを説明するための説明図である。図１６において、（ａ）が経路エントリ変更前の状態を示し、（ｂ）が経路エントリ変更後の状態を示している。最長経路エントリ設定方式において、図１６（ａ）に示すＲａｄｉｘツリーにて、ネットワーク“000x/3”を持つ経路エントリの転送条件を変更した場合、図１６（ｂ）に示すように、実体ノード１５０が、同一の宛先を持ち、かつ異なる転送条件を持つ実体ノード１５１、１５２によって、登録抑止されている。
【０１０９】
図１６に示すＲａｄｉｘツリーを用いて、図１７のフローチャートの動作を説明する。図１６（ａ）において、新たにネットワーク“000x/3”を持つ経路エントリの転送条件が変更（ネクストホップをＡからＢに変更）された場合、隣接ノード１５２、上位ノード１５０が実体ノードであり、かつ変更実体ノード１５１、隣接実体ノード１５２、上位実体ノード１５０の転送条件が同一でなく、かつ変更実体ノード１５１と隣接実体ノード１５２のネットワークマスク長が同一であり、かつ変更実体ノード１５１と上位実体ノード１５０のネットワークマスク長の差分が１であるかをチェックする（Ｓ１６０）。ここでは、このチェック条件を満足するため、上位実体ノード１５０を登録対象外に設定する（Ｓ１６１）。以上により、図１６（ｂ）に示すようなＲａｄｉｘツリーが形成される。
【０１１０】
また、図１６（ｂ）において、新たにネットワーク“000x/3”を持つ経路エントリの転送条件が変更（ネクストホップをＢからＡに変更）された場合、同様に、隣接ノード１５２、上位ノード１５０が実体ノードであり、かつ変更実体ノード１５１、隣接実体ノード１５２、上位実体ノード１５０の転送条件が同一でなく、かつ変更実体ノード１５１と隣接実体ノード１５２のネットワークマスク長が同一であり、かつ変更実体ノード１５１と上位実体ノード１５０のネットワークマスク長の差分が１であるかをチェックする（Ｓ１６０）。ここでは、このチェック条件を満足しないため、上位実体ノード１５０を登録対象に設定する（Ｓ１６２）。以上により、図１６（ｂ）に示すＲａｄｉｘツリーから、ネットワーク“000x/3”を持つ経路エントリが変更される前と同一の、図１６（ａ）に示すＲａｄｉｘツリーに戻される。
【０１１１】
Ｃ−３．集約経路エントリ設定方式
図１８は、経路エントリ設定方式の１つである集約経路エントリ設定方式を説明するための説明図である。図１８において、（ａ）は一般的なＲａｄｉｘツリーを示し、（ｂ）は、集約経路エントリ設定方式を適用した場合のＲａｄｉｘツリーを示す。
【０１１２】
集約経路エントリ設定方式では、図６や図１２で説明した経路エントリ設定方式の場合と同様に、Ｒａｄｉｘツリーのノードにフォワーディングテーブル２２への登録要否を示す情報を持つ。以降の説明で使用するノードの表記は、図６や図１２で示したノードの表記と同様に、左下フィールドの２番目の値が登録要否の情報を示す。この値が“０”の場合は登録対象であることを示し、“４”（“０”以外）の場合は登録対象外であることを示す。すなわち、左下フィールドの２番目の値として、図６で説明した包含経路エントリ設定方式により登録抑止されたノードでは“１”が設定され、図１２で説明した最長経路エントリ設定方式により登録抑止されたノードでは“２”が設定され、この集約経路エントリ設定方式により登録抑止されたノードでは“４”が設定され、複数の経路エントリ設定方式で登録抑止されたノードでは各エントリ設定方式での設定値の合計値が設定される。なお、分岐ノードは、常にフォワーディングテーブル２２に登録することは無く“−”で示す。
【０１１３】
また、集約経路エントリ設定方式では、Ｒａｄｉｘツリーのノードに、自動生成した経路エントリを持つ実体ノードであることを示す情報を持つ。以降の説明で使用するノードの表記は、図６や図１２で示したノードの表記に加え、左下フィールドの３番目の値が自動生成の情報を示す。この値が“１”の場合は、集約経路エントリ設定方式により自動生成した集約経路エントリを持つ実体ノードであることを示し、“−”の場合はそれ以外であることを示す。
【０１１４】
集約経路エントリ設定方式は、任意の複数の経路エントリを組み合わせたものと同等の経路エントリとなる集約された経路エントリを生成し、集約された経路エントリをフォワーディングテーブル２２に登録し、集約される側の経路エントリをフォワーディングテーブル２２に登録しないことにより、フォワーディングテーブル２２に登録する経路エントリ数を削減し、フォワーディングテーブル容量以上の経路エントリを取り扱うことを可能とするものである。
【０１１５】
図１８のＲａｄｉｘツリーにおいて、送信先アドレス“000x”（ｘは０または１の任意値）宛のパケットは、ネットワーク“000x/3”を持つ実体ノード１７１の経路エントリに基づき、ネクストホップＡに転送される。送信先アドレス“001x”（ｘは０または１の任意値）宛のパケットは、ネットワーク“001x/3”を持つ実体ノード１７２の経路エントリに基づき、ネクストホップＡに転送される。しかしながら、実体ノード１７１と実体ノード１７２の経路エントリは、同一転送条件を持ち、それらを組み合わせたものと同等のネットワーク“00xx/2”を持つ実体ノード１７０の経路エントリが、フォワーディングテーブル２２に存在すれば、実体ノード１７１と実体ノード１７２の経路エントリはフォワーディングテーブル２２に存在していなくても、上記の送信先アドレス宛のパケットは、実体ノード１７０の経路エントリに基づき、ネクストホップＡに転送される。このように、下位実体ノードを組み合わせたものと同等となる集約する経路エントリを生成することにより、下位実体ノードの経路エントリはフォワーディングテーブル２２に登録しなくても、同等の転送先を得ることができる。これにより、集約経路エントリ設定方式を適用した場合、図１８（ｂ）に示すように、実体ノード１７１と実体ノード１７２は、実体ノード１７０を生成することにより、フォワーディングテーブル２２への登録が抑止され、フォワーディングテーブル２２に登録される経路エントリ数が削減される。
【０１１６】
図２０は、集約経路エントリ設定方式において、新たに経路エントリを追加した場合の処理を示すフローチャートである。このフローチャートは、経路表作成部１５において、Ｒａｄｉｘツリーに経路エントリを追加した後に実行される。
【０１１７】
新たに経路エントリが追加された場合、隣接ノードが実体ノードであり、かつ追加実体ノードと隣接実体ノードの転送条件が同一であり、かつネットワークマスク長が同一であるかをチェックする（Ｓ１９０）。このチェック条件を満足する場合、追加実体ノードと隣接実体ノードは、１つ短いネットワークマスク長の集約経路に集約でき、かつ同一の転送条件を持つことを意味する。これにより、集約経路エントリを追加し（Ｓ１９１）、追加実体ノードと隣接実体ノードを登録対象外に設定する（Ｓ１９２）。また、集約経路エントリの追加に伴い、集約経路エントリを基にした新たな集約経路エントリを生成できる場合がある。従って、集約経路エントリを追加の際に、集約経路エントリを追加経路エントリとし、上記と同様の処理を行う。このような処理の後、経路登録部１７において、登録要否の情報が変化した経路エントリに対し、登録抑止解除された経路エントリ、登録抑止された経路エントリの順で、フォワーディングテーブル２２の更新を行う。なお、集約経路エントリ設定方式で生成する集約経路エントリは、その宛先に対する最高優先の経路エントリとして生成する。これは、集約経路エントリ設定方式で生成する集約経路エントリは、その集約経路エントリよりネットワークマスク長の長い経路エントリを集約するものであり、最長一致論理により、その集約経路エントリが優先されるためである。
【０１１８】
図１９は、集約経路エントリ設定方式において、新たに経路エントリを追加した場合に、Ｒａｄｉｘツリーがどのように変化するかを説明するための説明図である。図１９において、（ａ）が経路エントリ追加前の状態を示し、（ｂ）が経路エントリ追加後の状態を示している。集約経路エントリ設定方式において、図１９（ａ）に示すＲａｄｉｘツリーに、ネットワーク“000x/3”、“011x/3”を持つ経路エントリを追加した場合、図１９（ｂ）に示すように、実体ノード１８３と実体ノード１８４が、集約したネットワークを持ち、かつ同一転送条件を持つ実体ノード１８１によって、登録抑止されている。
【０１１９】
図１９に示すＲａｄｉｘツリーを用いて、図２０のフローチャートの動作を説明する。図１９（ａ）において、新たにネットワーク“000x/3”を持つ経路エントリが追加された場合、隣接ノード１８４が実体ノードであり、かつ追加実体ノード１８３と隣接実体ノード１８４の転送条件が同一であり、かつネットワークマスク長が同一であるかをチェックする（Ｓ１９０）。ここでは、このチェック条件を満足するため、集約経路エントリ１８１を追加し（Ｓ１９１）、追加実体ノード１８３、隣接実体ノード１８４を登録対象外に設定する（Ｓ１９２）。また、生成された集約経路エントリを追加経路エントリとし、同様に処理する。次に、ネットワーク“011x/3”を持つ経路エントリが追加された場合、同様に、隣接ノード１８５が実体ノードであり、かつ追加実体ノード１８６と隣接実体ノード１８５の転送条件が同一であり、かつネットワークマスク長が同一であるかをチェックする（Ｓ１９０）。ここでは、このチェック条件を満足しないため、何も行わない。以上により、図１９（ｂ）に示すようなＲａｄｉｘツリーが形成される。
【０１２０】
図２１は、集約経路エントリ設定方式において、新たに経路エントリを削除した場合の処理を示すフローチャートである。このフローチャートは、経路表作成部１５において、Ｒａｄｉｘツリーから経路エントリを削除する前に実行される。
【０１２１】
新たに経路エントリが削除された場合、上位ノードが実体ノードであり、かつ上位実体ノードが集約経路エントリ設定方式で生成した集約経路エントリを持つ実体ノードかをチェックする（Ｓ２００）。このチェック条件を満足する場合、経路エントリの削除に伴い、登録抑止条件（Ｓ１９０）を満足しなくなるため、集約経路エントリを削除し（Ｓ２０１）、隣接実体ノードを登録対象に設定する（Ｓ２０２）。また、集約経路エントリの削除に伴い、集約経路エントリを基にして生成された集約経路エントリが削除される場合がある。従って、集約経路エントリの削除の際に、集約経路エントリを削除経路エントリとし、上記と同様の処理を行う。このような処理の後、経路登録部１７において、登録要否が変化した経路エントリに対し、登録抑止が解除された経路エントリ、登録抑止された経路エントリの順で、フォワーディングテーブル２２の更新を行う。
【０１２２】
図１９のＲａｄｉｘツリーを用いて、図２１のフローチャートの動作を説明する。図１９（ｂ）において、新たにネットワーク“000x/3”を持つ経路エントリが削除された場合、上位ノード１８１が実体ノードであり、上位実体ノード１８１が集約経路エントリ設定方式で生成された集約経路エントリを持つ実体ノードかをチェックする（Ｓ２００）。ここでは、このチェック条件を満足するため、集約経路エントリ１８１を削除し（Ｓ２０１）、隣接実体ノード１８４を登録対象に設定する（Ｓ２０２）。また、削除された集約経路エントリを削除経路エントリとし、同様に処理する。次に、ネットワーク“011x/3”を持つ経路エントリが削除された場合、同様に、上位ノード１８２が実体ノードであり、かつ上位実体ノードが本経路エントリ設定方式で生成された集約経路エントリを持つ実体ノードかをチェックする（Ｓ２００）。ここでは、このチェック条件を満足しないため、以降の処理は無い。以上により、図１９（ｂ）に示すＲａｄｉｘツリーから、ネットワーク“000x/3”と“011x/3”を持つ経路エントリが追加される前と同一の、図１９（ａ）に示すＲａｄｉｘツリーに戻される。
【０１２３】
図２３は、集約経路エントリ設定方式において、新たに経路エントリを変更した場合の処理を示すフローチャートである。このフローチャートは、経路表作成部１５において、Ｒａｄｉｘツリーの経路エントリを変更した後に実行される。
【０１２４】
新たに経路エントリが変更された場合、隣接ノードが実体ノードであり、かつ変更実体ノードと隣接実体ノードの転送条件が同一であり、かつネットワークマスク長が同一であるかをチェックする（Ｓ２２０）。このチェック条件を満足する場合、集約経路エントリを追加し（Ｓ２２１）、変更実体ノード、隣接実体ノードを登録対象外に設定する（Ｓ２２２）。満足しない場合、集約経路エントリを削除し（Ｓ２２３）、隣接実体ノードを登録対象に設定する（Ｓ２２４）。また、集約経路エントリの追加に伴い、集約経路エントリを基にした新たな集約経路エントリを生成できる場合があり、また、集約経路エントリの削除に伴い、集約経路エントリを基にして生成された集約経路エントリが削除される場合がある。従って、集約経路エントリの追加、または削除の際に、集約経路エントリを追加経路エントリ、または削除経路エントリとし、上記と同様の処理を行う。このような処理の後、経路登録部１７において、登録要否が変化した経路エントリに対し、登録抑止解除された経路エントリ、登録抑止された経路エントリの順で、フォワーディングテーブル２２の更新を行う。
【０１２５】
図２２は、集約経路エントリ設定方式において、新たに経路エントリを変更した場合、Ｒａｄｉｘツリーがどのように変化するかを説明するための説明図である。図２２において、（ａ）が経路エントリ変更前の状態を示し、（ｂ）が経路エントリ変更後の状態を示している。集約経路エントリ設定方式において、図２２（ａ）に示すＲａｄｉｘツリーにて、ネットワーク“000x/3”を持つ経路エントリの転送条件を変更した場合、図２２（ｂ）に示すように、実体ノード２１１と実体ノード２１２が、集約したネットワークを持ち、かつ同一転送条件を持つ実体ノード２１０によって、登録抑止されている。
【０１２６】
図２２に示すＲａｄｉｘツリーを用いて、図２３のフローチャートの動作を説明する。図２２（ａ）において、新たにネットワーク“000x/3”を持つ経路エントリの転送条件が変更（ネクストホップをＡからＢに変更）された場合、隣接ノード２１２が実体ノードであり、かつ変更実体ノード２１１と隣接実体ノード２１２の転送条件が同一であり、かつネットワークマスク長が同一であるかをチェックする（Ｓ２２０）。ここでは、このチェック条件を満足するため、集約経路エントリ２１０を追加し（Ｓ２２１）、変更実体ノード２１１、隣接実体ノード２１２を登録対象外に設定する（Ｓ２２２）。以上により、図２２（ｂ）に示すようなＲａｄｉｘツリーが形成される。
【０１２７】
次に、ネットワーク“011x/3”を持つ経路エントリの転送条件が変更（ネクストホップをＢからＡに変更）された場合、同様に、隣接ノード２１２が実体ノードであり、かつ変更実体ノード２１１と隣接実体ノード２１２の転送条件が同一であり、かつネットワークマスク長が同一であるかをチェックする（Ｓ２２０）。ここでは、このチェック条件を満足しないため、集約経路エントリ２１０を削除し（Ｓ２２３）、変更実体ノード２１１、隣接実体ノード２１２を登録対象に設定する（Ｓ２２４）。以上により、図２２（ｂ）に示すＲａｄｉｘツリーから、ネットワーク“011x/3”を持つ経路エントリが変更される前と同一の、図２２（ａ）に示すＲａｄｉｘツリーに戻される。
【０１２８】
Ｃ−４．補完経路エントリ設定方式
図２４は、経路エントリ設定方式の１つである補完経路エントリ設定方式を説明するための説明図である。図２４において、（ａ）は一般的なＲａｄｉｘツリーを示し、（ｂ）は、補完経路エントリ設定方式を適用した場合のＲａｄｉｘツリーを示す。
【０１２９】
補完経路エントリ設定方式では、図６，図１２，図１８で説明した経路エントリ設定方式の場合と同様に、Ｒａｄｉｘツリーのノードにフォワーディングテーブル２２への登録要否を示す情報を持つ。以降の説明で使用するノードの表記は、図６，図１２，図１８で示したノードの表記と同様に、左下フィールドの２番目の値が登録要否の情報を示す。この値が“０”の場合は登録対象であることを示し、“８”（“０”以外）の場合は登録対象外であることを示す。すなわち、図６で説明した包含経路エントリ設定方式により登録抑止されたノードでは“１”が設定され、図１２で説明した最長経路エントリ設定方式により登録抑止されたノードでは“２”が設定され、図１８で説明した集約経路エントリ設定方式により登録抑止されたノードでは“４”が設定され、この補完経路エントリ設定方式により登録抑止されたノードでは“８”が設定され、複数の経路エントリ設定方式で登録抑止されたノードでは各経路エントリ設定方式での設定値の合計値が設定される。なお、分岐ノードは、常にフォワーディングテーブルに登録することは無く“−”で示す。
【０１３０】
また、補完経路エントリ設定方式では、Ｒａｄｉｘツリーのノードに、自動生成した集約経路エントリ、または自動生成した補完経路エントリを持つ実体ノードであることを示す情報を持つ。以降の説明で使用するノードの表記は、図１８で示したノードの表記に加え、左下フィールドの３番目の値が自動生成の情報を示す。この値が“２”の場合は、補完経路エントリ設定方式により自動生成した集約経路エントリを持つ実体ノードであることを示し、この値が“３”の場合は、補完経路エントリ設定方式により自動生成した補完経路エントリを持つ実体ノードであることを示し、“−”の場合はそれ以外であることを示す。
【０１３１】
補完経路エントリ設定方式は、任意の複数の経路エントリを組み合わせたものと同等の経路エントリとなる集約された経路エントリを生成する場合において、集約される側の一部の経路エントリが不足している場合に、不足部分を補完する経路エントリを生成し、集約された経路エントリと補完する経路エントリをフォワーディングテーブル２２に登録し、集約される側の経路エントリをフォワーディングテーブル２２に登録しないことにより、フォワーディングテーブル２２に登録する経路エントリ数を削減し、フォワーディングテーブル容量以上の経路エントリを取り扱うことを可能とするものである。
【０１３２】
図２４のＲａｄｉｘツリーにおいて、送信先アドレス“000x”（ｘは０または１の任意値）宛のパケットは、ネットワーク“000x/3”を持つ実体ノード２３１の経路エントリに基づき、ネクストホップＡに転送される。送信先アドレス“0010”宛のパケットは、ネットワーク“0010/4”を持つ実体ノード２３３の経路エントリに基づき、ネクストホップＡに転送される。また、送信先アドレス“0011”宛のパケットは、最長一致する経路エントリが存在しないため廃棄される。しかしながら、実体ノード２３１と実体ノード２３３の経路エントリは、同一転送条件を持ち、それらを組み合わせたものと同等のネットワーク“00xx/2”を持つ実体ノード２３０の経路エントリがフォワーディングテーブル２２に存在すれば、実体ノード２３１と２３３の経路エントリがフォワーディングテーブル２２に存在していなくても、上記の送信先アドレス宛のパケットは、実体ノード２３０の経路エントリに基づき、ネクストホップＡに転送される。また、送信先アドレス“0011”宛のパケットは、リジェクトフラグが設定（左下フィールドの１番目の値が“−”に設定）されたネットワーク“0011/4”を持つ実体ノード２３４の経路エントリが、フォワーディングテーブル２２に存在すれば、この経路エントリに基づき、廃棄される。このように、下位実体ノードを組み合わせたものと同等となる集約する経路エントリ、および補完する経路エントリを生成することにより、下位実体ノードの経路エントリは、フォワーディングテーブル２２に登録しなくても、同等の転送先を得ることができる。これにより、補完経路エントリ設定方式を適用した場合、図２４（ｂ）に示すように、実体ノード２３１と実体ノード２３３は、実体ノード２３０と実体ノード２３４を生成することにより、フォワーディングテーブル２２への登録が抑止され、フォワーディングテーブル２２に登録される経路エントリ数が削減される。
【０１３３】
図２６は、補完経路エントリ設定方式において、新たに経路エントリを追加した場合の動作を示すフローチャートである。このフローチャートは、経路表作成部１５において、Ｒａｄｉｘツリーに経路エントリを追加した後に実行される。
【０１３４】
新たに経路エントリが追加された場合、上位または下位実体ノードに、補完経路エントリ設定方式で生成した集約経路エントリを持つ実体ノードが存在するかをチェックする（Ｓ２５０）。存在する場合、集約経路エントリを持つ実体ノードの下位実体ノードを登録対象に設定し（Ｓ２５１）、集約経路エントリ、補完経路エントリを削除する（Ｓ２５２）。次に、上位実体ノード（集約経路エントリを持つ実体ノードを除く）が存在せず、かつ隣接ノードが実体ノードであり、かつ追加実体ノードと隣接実体ノードの転送条件が同一であり、かつネットワークマスク長の差分が１であるかをチェックする（Ｓ２５３）。このチェック条件を満足する場合は、集約経路エントリ、補完経路エントリを追加し（Ｓ２５４）、追加実体ノード、隣接実体ノードを登録対象外に設定する（Ｓ２５５）。また、集約経路エントリの追加に伴い、集約経路エントリを基にした新たな集約経路エントリを生成できる場合があり、また、集約経路エントリの削除に伴い、集約経路エントリを基にして生成された集約経路エントリが削除される場合がある。従って、集約経路エントリの追加、または削除の際に、集約経路エントリを追加経路エントリ、または削除経路エントリとし、上記と同様の処理を行う。このような処理の後、経路登録部１７において、登録要否が変化した経路エントリに対し、登録抑止解除された経路エントリ、登録抑止された経路エントリの順で、フォワーディングテーブル２２の更新を行う。なお、補完経路エントリ設定方式で生成する集約経路エントリ、補完経路エントリは、その宛先に対する最低優先の経路エントリとして生成する。これは、補完経路エントリ設定方式で生成する集約経路エントリ、補完経路エントリは、経路情報上に存在しない宛先への経路エントリを補完するものであり、宛先への経路エントリが存在する場合、その経路エントリを優先させるためである。
【０１３５】
図２５は、補完経路エントリ設定方式において、新たに経路エントリを追加した場合に、Ｒａｄｉｘツリーがどのように変化するかを説明するための説明図である。図２５において、（ａ）が経路エントリ追加前の状態を示し、（ｂ）が経路エントリ追加後の状態を示している。補完経路エントリ設定方式において、図２５（ａ）に示すＲａｄｉｘツリーに、新たにネットワーク“0xxx/1”を持つ経路エントリを追加した場合、図２５（ｂ）に示すように、集約経路エントリが接続された実体ノード２４３と補完経路エントリが接続された実体ノード２４９が削除され、実体ノード２４６と実体ノード２４８が登録抑止解除されている。また、集約経路エントリが接続された実体ノード２４０と補完経路エントリが接続された実体ノード２４５が追加され、実体ノード２４１と実体ノード２４４が登録抑止されている。
【０１３６】
図２５に示すＲａｄｉｘツリーを用いて、図２６のフローチャートの動作を説明する。図２５（ａ）において、新たにネットワーク“0xxx/1”を持つ経路エントリが追加された場合、上位または下位実体ノードに、補完経路エントリ設定方式で生成した集約経路エントリを持つ実体ノード２４３が存在するかをチェックする（Ｓ２５０）。ここでは、このチェック条件を満足するため、集約経路エントリを持つ実体ノード２４３の下位実体ノード２４６、２４８、２４９を登録対象に設定し（Ｓ２５１）、集約経路エントリ２４３、補完経路エントリ２４９を削除する（Ｓ２５２）。次に、上位実体ノード（集約経路エントリを持つ実体ノードを除く）が存在せず、かつ隣接ノード２４４が実体ノードであり、かつ追加実体ノード２４１と隣接実体ノード２４４の転送条件が同一であり、かつネットワークマスク長の差分が１であるかをチェックする（Ｓ２５３）。ここでは、このチェック条件を満足するため、集約経路エントリ２４０、補完経路エントリ２４５を追加し（Ｓ２５４）、追加実体ノード２４１、隣接実体ノード２４４を登録対象外に設定する（Ｓ２５５）。以上により、図２５（ｂ）に示すようなＲａｄｉｘツリーが形成される。
【０１３７】
図２７は、補完経路エントリ設定方式において、新たに経路エントリを削除した場合の動作を示すフローチャートである。このフローチャートは、経路表作成部１５において、Ｒａｄｉｘツリーから経路エントリを削除する前に実行される。
【０１３８】
新たに経路エントリが削除された場合、上位実体ノードは、補完経路エントリ設定方式で生成した集約経路エントリを持つ実体ノードかをチェックする（Ｓ２６０）。このチェック条件を満足する場合、集約経路エントリを持つ実体ノードの下位実体ノードを登録対象に設定し（Ｓ２６１）、集約経路エントリ、補完経路エントリを削除する（Ｓ２６２）。次に、上位実体ノード（集約経路エントリを持つ実体ノードを除く）が存在せず、かつ下位実体ノードの隣接ノードが実体ノードであり、かつ下位実体ノードと下位実体ノードの隣接実体ノードの転送条件が同一であり、かつネットワークマスク長が１のみ差分があるかをチェックする（Ｓ２６３）。このチェック条件を満足する場合、下位実体ノードに対する集約経路エントリ、補完経路エントリを追加し（Ｓ２６４）、下位実体ノード、下位実体ノードの隣接実体ノードを登録対象外に設定する（Ｓ２６５）。また、集約経路エントリの追加に伴い、集約経路エントリを基にした新たな集約経路エントリを生成できる場合があり、また、集約経路エントリの削除に伴い、集約経路エントリを基にして生成された集約経路エントリが削除される場合がある。従って、集約経路エントリの追加、または削除の際に、集約経路エントリを追加経路エントリ、または削除経路エントリとし、上記と同様の処理を行う。このような処理の後、経路登録部１７において、登録要否が変化した経路エントリに対し、登録抑止解除された経路エントリ、登録抑止された経路エントリの順で、フォワーディングテーブル２２の更新を行う。
【０１３９】
図２５のＲａｄｉｘツリーを用いて、図２７のフローチャートの動作を説明する。図２５（ｂ）において、新たにネットワーク“0xxx/1”を持つ経路エントリが削除された場合、上位実体ノード２４０は、補完経路エントリ設定方式で生成した集約経路エントリを持つ実体ノードかをチェックする（Ｓ２６０）。ここでは、このチェック条件を満足するため、集約経路エントリを持つ実体ノード２４０の下位実体ノード２４１、２４４、２４５を登録対象に設定し（Ｓ２６１）、集約経路エントリ２４０、補完経路エントリ２４５を削除する（Ｓ２６２）。次に、上位実体ノード（集約経路エントリを持つ実体ノードを除く）が存在せず、かつ下位実体ノード２４６、または２４８の隣接ノード２４８、または２４６が実体ノードであり、かつ下位実体ノード２４６または２４８と下位実体ノードの隣接実体ノード２４８または２４６の転送条件が同一であり、かつネットワークマスク長の差分が１であるかをチェックする（Ｓ２６３）。ここでは、このチェック条件を満足するため、下位実体ノード２４６または２４８に対する集約経路エントリ２４３、補完経路エントリ２４９を追加し（Ｓ２６４）、下位実体ノード２４６または２４８、下位実体ノード２４６または２４８の隣接実体ノード２４８または２４６を登録対象外に設定する（Ｓ２０６）。以上により、図２５（ｂ）に示すＲａｄｉｘツリーから、ネットワーク“0xxx/1”を持つ経路エントリが追加される前と同一の、図２５（ｂ）に示すＲａｄｉｘツリーに戻される。
【０１４０】
図２９は、補完経路エントリ設定方式において、新たに経路エントリを変更した場合の動作を示すフローチャートである。このフローチャートは、経路表作成部１５において、Ｒａｄｉｘツリーの経路エントリを変更した後に実行される。
【０１４１】
新たに経路エントリが変更された場合、上位実体ノード、または変更前実体ノードに、補完経路エントリ設定方式で生成した集約経路エントリを持つ実体ノードが存在するかをチェックする（Ｓ２８０）。存在する場合、集約経路エントリを持つ実体ノードの下位自体ノードを登録対象に設定し（Ｓ２８１）、集約経路エントリ、補完経路エントリを削除する（Ｓ２８２）。次に、上位実体ノード（集約経路エントリを持つ実体ノードを除く）が存在せず、かつ隣接ノードが実体ノードであり、かつ変更実体ノードと隣接実体ノードの転送条件が同一であり、かつネットワークマスク長が１のみ差分があるかをチェックする（Ｓ２８３）。このチェック条件を満足する場合、集約経路エントリ、補完経路エントリを追加し（Ｓ２８４）、変更実体ノード、隣接実体ノードを登録対象外に設定する（Ｓ２８５）。また、集約経路エントリの追加に伴い、集約経路エントリを基にした新たな集約経路エントリを生成できる場合があり、また、集約経路エントリの削除に伴い、集約経路エントリを基にして生成された集約経路エントリが削除される場合がある。従って、集約経路エントリの追加、または削除の際に、集約経路エントリを追加経路エントリ、または削除経路エントリとし、上記と同様の処理を行う。このような処理の後、経路登録部１７において、登録要否が変化した経路エントリに対し、登録抑止解除された経路エントリ、登録抑止された経路エントリの順で、フォワーディングテーブル２２の更新を行う。
【０１４２】
図２８は、補完経路エントリ設定方式において、新たに経路エントリを変更した場合、Ｒａｄｉｘツリーがどのように変化するかを説明するための説明図である。図２８において、（ａ）が経路エントリ変更前の状態を示し、（ｂ）が経路エントリ変更後の状態を示している。補完経路エントリ設定方式において、図２８（ａ）に示すＲａｄｉｘツリーにて、ネットワーク“000x/3”の経路エントリの転送条件を変更した場合、図２８（ｂ）に示すように、集約経路エントリが接続された実体ノード２７０と補完経路エントリが接続された実体ノード２７４が追加され、実体ノード２７１と実体ノード２７３が登録抑止されている。
【０１４３】
図２８に示すＲａｄｉｘツリーを用いて、図２９のフローチャートの動作を説明する。図２８（ａ）において、新たにネットワーク“000x/3”を持つ経路エントリの転送条件が変更（ネクストホップをＢからＡに変更）された場合、上位実体ノード、または変更前実体ノード２７１に、補完経路エントリ設定方式で生成された集約経路エントリを持つ実体ノードが存在するかをチェックする（Ｓ２８０）。ここでは、このチェック条件を満足しないため、次に、上位実体ノード（集約経路エントリを持つ実体ノードを除く）が存在せず、かつ隣接ノード２７３が実体ノードであり、かつ変更実体ノード２７１と隣接実体ノード２７３の転送条件が同一であり、かつネットワークマスク長の差分が１かをチェックする（Ｓ２８３）。ここでは、このチェック条件を満足するため、集約経路エントリ２７０、補完経路エントリ２７４を追加し（Ｓ２８４）、変更実体ノード２７１、隣接実体ノード２７３を登録対象外に設定する（Ｓ２８５）。以上により、図２８（ｂ）に示すようなＲａｄｉｘツリーが形成される。
【０１４４】
また、図２８（ｂ）において、新たにネットワーク“000x/3”の経路エントリの転送条件が変更（ネクストホップをＡからＢに変更）された場合、上位実体ノード２７０、または変更前実体ノード２７１に、補完経路エントリ設定方式で生成された集約経路エントリを持つ実体ノードが存在するかをチェックする（Ｓ２８０）。ここでは、このチェック条件を満足するため、集約経路エントリを持つ実体ノード２７０の下位実体ノード２７１，２７３、２７４を登録対象に設定し（Ｓ２８１）、集約経路エントリ２７０、補完経路エントリ２７４を削除する（Ｓ２８２）。次に、上位実体ノード（集約経路エントリを持つ実体ノードを除く）が存在せず、かつ隣接ノード２７２が実体ノードであり、かつ変更実体ノード２７１と隣接実体ノードの転送条件が同一であり、かつネットワークマスク長の差分が１かをチェックする（Ｓ２８３）。ここでは、このチェック条件を満足しないため、以降の処理はない。以上により、図２８（ｂ）に示すＲａｄｉｘツリーから、ネットワーク“000x/3”を持つ経路エントリが変更される前と同一の、図２８（ａ）に示すＲａｄｉｘツリーに戻される。
【０１４５】
Ｃ−５．未登録補完経路エントリ設定方式
図３０は、経路エントリ設定方式の１つである未登録補完経路エントリ設定方式を説明するための説明図である。この未登録補完経路エントリ設定方式は、前述の補完経路エントリ設定方式において、補完経路エントリをフォワーディングテーブル２２に登録しない経路エントリとして生成する設定方式である。図３０において、（ａ）は一般的なＲａｄｉｘツリーを示し、（ｂ）は、集約経路エントリ設定方式を適用した場合のＲａｄｉｘツリーを示す。
【０１４６】
未登録補完経路エントリ設定方式では、図６，図１２，図１８，図２４で説明した経路エントリ設定方式と同様に、Ｒａｄｉｘツリーのノードにフォワーディングテーブル２２への登録要否を示す情報を持つ。以降の説明で使用するノードの表記は、図６，図１２，図１８、図２４で示したノードの表記と同様に、左下フィールドの２番目の値が登録要否の情報を示す。この値が“０”の場合は登録対象であることを示し、“８”（“０”以外）の場合は登録対象外であることを示す。すなわち、図６で説明した包含経路エントリ設定方式により登録抑止されたノードでは“１”が設定され、図１２で説明した最長経路エントリ設定方式により登録抑止されたノードでは“２”が設定され、図１８で説明した集約経路エントリ設定方式により登録抑止されたノードでは“４”が設定され、この未登録補完経路エントリ設定方式により登録抑止されたノードでは“８”が設定され、複数の経路エントリ設定方式で登録抑止されたノードには各経路エントリ設定方式での設定値の合計値が設定される。なお、分岐ノードは、常にフォワーディングテーブルに登録することは無く“−”で示す。
【０１４７】
また、未登録補完経路エントリ設定方式では、Ｒａｄｉｘツリーのノードに、自動生成した集約経路エントリを持つ実体ノードであることを示す情報を持つ。以降の説明で使用するノードの表記は、図２４で示したノードの表記と同様に、左下フィールドの３番目の値が自動生成の情報を示す。この値が“２”の場合は、未登録補完経路エントリ設定方式により自動生成した集約経路エントリを持つ実体ノードであることを示し、この値が“３”の場合は、未登録補完経路エントリ設定方式により自動生成した補完経路エントリを持つ実体ノードであることを示し、“−”の場合はそれ以外であることを示す。
【０１４８】
未登録補完経路エントリ設定方式は、任意の複数の経路エントリを組み合わせたものと同じの経路エントリとなる集約した経路エントリを生成する場合において、集約される側の一部の経路エントリが不足している場合に、不足部分を補完する経路エントリをフォワーディングテーブル２２に登録しない経路エントリとして生成し、集約経路エントリをフォワーディングテーブル２２に登録し、補完する経路エントリ、および集約される側の経路エントリをフォワーディングテーブル２２に登録しないことにより、フォワーディングテーブル２２に登録する経路エントリ数を削減し、フォワーディングテーブル容量以上の経路エントリを取り扱うことを可能とするものである。
【０１４９】
図３０のＲａｄｉｘツリーにおいて、送信先アドレス“000x”（ｘは０または１の任意値）宛のパケットは、ネットワーク“000x/3”を持つ実体ノード２９１の経路エントリに基づき、ネクストホップＡに転送される。送信先アドレス“0010”宛のパケットは、ネットワーク“0010/4”を持つ実体ノード２９３の経路エントリに基づき、ネクストホップＡに転送される。また、送信先アドレス“0011”宛のパケットは、最長一致する経路エントリが存在しないため、廃棄される。しかしながら、実体ノード２９１と実体ノード２９３の経路エントリは、同一転送条件を持ち、組み合わせたものと同等のネットワーク“00xx/2”を待つ実体ノード２９０の経路エントリが、フォワーディングテーブル２２に存在すれば、実体ノード２９１と２９３の経路エントリが、フォワーディングテーブルに存在していなくても、上記の送信先アドレス宛のパケットは、実体ノード２９０の経路エントリに基づき、ネクストホップＡに転送される。また、送信先アドレス“0011”宛のパケットは、廃棄することを示す補完経路エントリを登録しないことにより、ネットワーク“00xx/2”を持つ実体ノード２９０の経路エントリに基づき、ネクストホップＡに転送され、ネクストホップＡを持つ隣接の通信装置において廃棄される。このように、下位の実体ノードを組み合わせたものと同等となる集約する経路エントリ、および登録しない補完する経路エントリを生成することにより、集約される側の経路エントリはフォワーディングテーブル２２に登録しなくても、パケットの送信元アドレス、送信先アドレス間の通信は、同等の結果を得ることができる。これにより、未登録補完経路エントリ設定方式を適用した場合、図３０（ｂ）に示すように、実体ノード２９１と実体ノード２９３は、実体ノード２９０と実体ノード２９４を生成することにより、フォワーディングテーブル２２への登録が抑止され、フォワーディングテーブル２２に登録される経路エントリ数が削減される。
【０１５０】
未登録補完経路エントリ設定方式と前述の補完経路エントリ設定方式との差分は、補完経路エントリを登録対象として生成するか、登録対象外として生成するかの違いとなる。従って、未登録補完経路エントリ設定方式における経路エントリ追加、削除、変更時の動作フローは、図２６のＳ２５４、図２７のＳ２６４、図２９のＳ２８４の処理において、補完経路エントリを登録対象外として生成するものとなる。
【０１５１】
Ｄ．経路エントリ設定方式の適用方法
以上、各経路エントリ設定方式について、説明した。これら各経路エントリ設定方式によれば、ルーティングテーブル１８内に保持された宛先毎の１つ以上の経路エントリから、宛先毎の第一優先の経路エントリをフォワーディングテーブル２２に登録した場合と同じ転送先を選定できるように選定された、上記第一優先の経路エントリの一部をフォワーディングテーブル２２に登録することにより、フォワーディングテーブル２２に登録する経路エントリ数を削減することができる。これら各経路エントリ設定方式は、単独で適用しても良く、また任意の組み合わせで適用してもよい。これら経路エントリ設定方式のうち、包括経路エントリ設定方式は、方式適用によるメモリ増分は少ない。最長経路エントリ設定方式は、包含経路エントリ設定方式と同様に、方式適用によるメモリ増分は少ないが、包含経路エントリ設定方式より経路エントリ数の削減率は低い。集約経路エントリ設定方式は、集約経路エントリの追加に伴うメモリ増分が発生する。補完経路エントリ設定方式は、集約経路エントリ、および補完経路エントリの追加に伴うメモリ増分が発生する。未登録補完経路エントリ設定方式は、同様に、集約経路エントリ、および補完経路エントリの追加に伴うメモリ増分が発生する。また、補完経路エントリに対応するパケットは隣接の通信装置に転送され、隣接の通信装置によってパケット廃棄される。従って、望ましい実施形態としては、包含経路エントリ設定方式、最長経路エントリ設定方式、集約経路エントリ設定方式、補完経路エントリ設定方式、未登録補完経路エントリ設定方式の順に組み合わせて使用することが望ましい。なお、各経路エントリ設定方式の登録抑止条件は、各経路エントリ設定方式で異なるため、任意の組み合わせで適用できる。だたし、補完経路エントリ設定方式と未登録補完経路エントリ設定方式は登録抑止条件が同一であるため、適用は排他となる。
【０１５２】
適用する経路エントリ設定方式は、固定的に予め設定しておいてもよく、また、構成情報により静的に決定してもよく、さらに、フォワーディングテーブル２２の登録状況により動的に決定してもよい。
【０１５３】
Ｄ−１．適用する経路エントリ設定方式が予め設定されている場合
図３１は、適用する経路エントリ設定方式が予め設定されている場合において、経路エントリを追加した場合の処理フローを示すフローチャートであり、図３２は、同じく、経路エントリを削除した場合の処理フローを示すフローチャートであり、図３３は、同じく、経路エントリを変更した場合の処理フローを示すフローチャートである。各フローチャート内で参照される「選択方式」には、予め適用する経路エントリ設定方式が設定されているものとする。
【０１５４】
経路エントリ追加時には、図３１に示す処理が実行される。処理フローは、「選択方式」に該当する経路エントリ設定方式が設定されているかをチェックし、設定されている場合に、その経路エントリ設定方式の追加処理を実行する。経路エントリ削除時には、図３２に示す処理が実行される。処理フローは、「選択方式」に該当する経路エントリ設定方式が設定されているかをチェックし、設定されている場合に、その経路エントリ設定方式の削除処理を実行する。経路エントリ変更時には、図３３に示す処理が実行される。処理フローは、「選択方式」に該当する経路エントリ設定方式が設定されているかをチェックし、設定されている場合に、その経路エントリ設定方式の変更処理を実行する。以上のような処理の後、経路登録部１７において、登録要否が変化した経路エントリに対し、登録抑止解除された経路エントリ、登録抑止された経路エントリの順で、フォワーディングテーブル２２の更新を行う。
【０１５５】
Ｄ−２．適用する経路エントリ設定方式を構成情報により静的に決定する場合
図３５は、適用する経路エントリ設定方式を構成情報により静的に決定するための処理フローを示すフローチャートである。このフローチャートは、構成情報により適用する経路エントリ設定方式を変更した場合に起動される。
【０１５６】
処理フローは、包括経路エントリ設定方式の静的適用更新処理（Ｓ３４０）、「最長経路エントリ設定方式の静的適用更新処理（Ｓ３４１）、集約経路エントリ設定方式の静的適用更新処理（Ｓ３４２）、補完経路エントリ設定方式の静的適用更新処理、または未登録補完経路エントリ設定方式の静的適用更新処理（Ｓ３４３）の順に実行する。このような処理の後、経路登録部１７において、登録要否が変化した経路エントリに対し、登録抑止解除された経路エントリ、登録抑止された経路エントリの順で、フォワーディングテーブルの更新を行う。
【０１５７】
図３６は、図３５における各経路エントリ設定方式の静的適用更新処理のフローを示すフローチャートである。図３６に示すように、各経路エントリ設定方式の静的適用更新処理では、選択方式に、その経路エントリ設定方式が設定されているかをチェックする（Ｓ３５０）。設定されている場合は、旧選択方式に、その経路エントリ設定方式が設定されているかをチェックし（Ｓ３５１）、設定されていない場合は、その経路エントリ設定方式が適用対象に変化したことを意味し、その経路エントリ設定方式の一括設定処理を実行する（Ｓ３５２）。設定されていない場合は、旧選択方式に、その経路エントリ設定方式が設定されているかをチェックし（Ｓ３５３）、設定されている場合は、その経路エントリ設定方式が適用対象外に変化したことを示し、その経路エントリ設定方式の一括解除処理を実行する（Ｓ３５４）。
【０１５８】
ここで、各経路エントリ設定方式の一括設定処理及び一括解除処理は、一括更新処理として、図３９〜図４２に示す。図３９は、包括経路エントリ設定方式の一括更新処理のフローを示すフローチャートであり、図４０は、最長経路エントリ設定方式の一括更新処理のフローを示すフローチャートであり、図４１は、集約経路エントリ設定方式の一括更新処理のフローを示すフローチャートであり、図４２は、補完経路エントリ設定方式、または未登録補完経路エントリ設定方式の一括更新処理のフローを示すフローチャートである。これら図において、（ａ）は、その経路エントリ設定方式の一括設定処理を示し、（ｂ）は、その経路エントリ設定方式の一括削除処理を示す。
【０１５９】
図３４は、適用する経路エントリ設定方式を構成情報により静的に決定する方法を説明するための説明図である。図３４において、（ａ）は上記で説明した経路エントリ設定方式を何も適用していない場合のＲａｄｉｘツリーである。（ｂ）は、（ａ）に示すＲａｄｉｘツリーに、上記で説明した経路エントリ設定方式のうち、包含経路エントリ選択方式、最長包含経路エントリ選択方式、集約経路エントリ設定方式、補完経路エントリ設定方式をそれぞれ適用した場合のＲａｄｉｘツリーである。
【０１６０】
包含経路エントリ選択方式の適用により、実体ノード３３１，３３２，３３３，３３５，３３６，３３７，３３８が登録抑止され、最長経路エントリ設定方式の適用により、実体ノード３３６が登録抑止され、集約経路エントリ設定方式の適用により、集約経路エントリを持つ実体ノード３３０、３３２が追加され、実体ノード３３１、３３２、３３５、３３６が登録抑止され、補完経路エントリ設定方式の適用により、集約経路エントリを持つ実体ノード３３１、補完経路エントリを持つ実体ノード３３９が追加され、実体ノード３３３、３３８が登録抑止されている。
【０１６１】
図３４のＲａｄｉｘツリーを用いて、図３５のフローチャートの動作を説明する。図３４（ａ）において、構成情報により、経路エントリ設定方式が何も適用されていない状態から、包含経路エントリ選択方式、最長経路エントリ選択方式、集約経路エントリ設定方式、補完経路エントリ設定方式を適用する状態に設定変更した場合の動作を例に説明する。
【０１６２】
まず、選択方式に包含経路エントリ設定方式が設定されているかをチェックする（Ｓ３５０）。ここでは、設定されているため、旧選択方式に包含経路エントリ設定方式が設定されているかをチェックする（Ｓ３５１）。ここでは、設定されていないため、包含経路エントリ設定方式の一括設定処理を実行する（Ｓ３５２）。包含経路エントリ設定方式の一括設定処理は、図３９（ａ）に示すように、各実体ノードに対し、Ｓ３８１〜Ｓ３８２間の処理を行う（Ｓ３８０）。その実体ノードと上位実体ノードが同一転送条件かをチェックする（Ｓ３８１）。ここでは、実体ノード３３７がチェック条件に一致するため、その実体ノード３３７を登録対象外に設定する（Ｓ３８２）。
【０１６３】
次に、選択方式に最長経路エントリ設定方式が設定されているかをチェックする（Ｓ３５０）。ここでは、設定されているため、旧選択方式に最長経路エントリ設定方式が設定されているかをチェックする（Ｓ３５１）。ここでは、設定されていないため、最長経路エントリ設定方式の一括設定処理を実行する（Ｓ３５２）。最長経路エントリ設定方式の一括設定処理は、図４０（ａ）に示すように、各実体ノードに対し、Ｓ３９１〜Ｓ３９２間の処理を行う（Ｓ３９０）。隣接ノード、上位ノードが実体ノードであり、かつ該実体ノード、隣接実体ノード、上位実体ノードが同一転送条件でなく、かつその実体ノードと隣接実体ノードのネットワークマスク長が同一であり、かつ上位実体ノードとその実体ノードのネットワークマスク長の差が１であるかをチェックする（Ｓ３９１）。ここでは、実体ノード３４０がチェック条件に一致するため、その実体ノード３４０の上位実体ノード３３６を登録対象外に設定する（Ｓ３９２）。
【０１６４】
次に、選択方式に集約経路エントリ設定方式が設定されているかをチェックする（Ｓ３５０）。ここでは、設定されているため、旧選択方式に集約経路エントリ設定方式が設定されているかをチェックする（Ｓ３５１）。ここでは、設定されていないため、集約経路エントリ設定方式の一括設定処理を実行する（Ｓ３５２）。集約経路エントリ設定方式の一括設定処理は、図４１（ａ）に示すように、各実体ノードに対し、Ｓ４０１〜Ｓ４０３間の処理を行う（Ｓ４００）。隣接ノードが実体ノードであり、かつその実体ノードと隣接実体ノードが同一転送条件であり、かつネットワークマスク長は同一かをチェックする（Ｓ４０１）。ここでは、実体ノード３３５がチェック条件に一致するため、集約経路エントリ３３２を追加し（Ｓ４０２）、その実体ノード３３５、隣接実体ノード３３６を登録対象外に設定する（Ｓ４０３）。
【０１６５】
次に、選択方式に補完経路エントリ設定方式が設定されているかをチェックする（Ｓ３５０）。ここでは、設定されているため、旧選択方式に補完経路エントリ設定方式が設定されているかをチェックする（Ｓ３５１）。ここでは、設定されていないため、補完経路エントリ設定の一括設定処理を実行する（Ｓ３５２）。補完経路エントリ設定方式の一括設定処理は、図４２（ａ）に示すように、各実体ノードに対し、Ｓ４１１〜Ｓ４１３間の処理を行う（Ｓ４１０）。上位実体ノード（集約経路エントリを持つ実体ノードを除く）が存在せず、かつ隣接ノードが実体ノードであり、かつその実体ノードと隣接実体ノードの転送条件が同一である、かつネットワークマスク長の差分が１であるかをチェックする（Ｓ４１１）。ここでは、実体ノード３３３がチェック条件に一致するため、集約経路エントリ３３１、補完経路エントリ３３９を追加し（Ｓ４１２）、その実体ノード３３３、隣接実体ノード３３８を登録対象外に設定する（Ｓ４１３）。
【０１６６】
また、生成された集約経路エントリ、補完経路エントリに対し、各経路エントリを追加経路エントリとした、図３１に示した経路エントリ追加時の処理が行われる。追加経路エントリ３３２に伴い、包含経路エントリ設定方式により、実体ノード３３５、３３６が登録抑止され、追加経路エントリ３３１に伴い、包含経路エントリ設定方式により、実体ノード３３３、３３８が登録抑止される。また、追加経路エントリ３３１、３３２に伴い、集約経路エントリ設定方式により、集約経路エントリを持つ実体ノード３３０が追加され、実体ノード３３１，３３２が登録抑止される。また、集約経路エントリ３３０の追加に伴い、包含経路エントリ設定方式により、ノード３３１、３３２が登録抑止される。以上により、図３５（ｂ）に示すようなＲａｄｉｘツリーが形成される。
【０１６７】
同様に、図３４（ｂ）の状態において、構成情報により、経路エントリ設定方式に、包含経路エントリ選択方式、最長経路エントリ選択方式、集約経路エントリ設定方式、補完経路エントリ設定方式を適用した状態から、適用されていない状態に、設定変更した場合の動作を例に説明する。
【０１６８】
まず、選択方式に包含経路エントリ設定方式が設定されているかをチェックする（Ｓ３５０）。ここでは、設定されていないため、旧選択方式に包含経路エントリ設定方式が設定されているかをチェックする（Ｓ３５３）。ここでは、設定されているため、包含経路エントリ設定方式の一括解除処理を実行する（Ｓ３５４）。包含経路エントリ設定方式の一括解除処理は、図３９（ｂ）に示すように、各実体ノードに対し、Ｓ３８５〜Ｓ３８６間の処理を行う（Ｓ３８４）。その実体ノードが包括経路エントリ設定方式で登録抑止した実体ノードかをチェックする（Ｓ３８５）。ここでは、実体ノード３３１、３３２、３３３、３３５、３３６、３３７、３３８がチェック条件に一致するため、その実体ノード３３１、３３２、３３３、３３５、３３６、３３７、３３８を登録対象外に設定する（Ｓ３８６）。
【０１６９】
次に、選択方式に最長経路エントリ設定方式が設定されているかをチェックする（Ｓ３５０）。ここでは、設定されていないため、旧選択方式に最長経路エントリ設定方式が設定されているかをチェックする（Ｓ３５３）。ここでは、設定されているため、最長経路エントリ設定方式の一括解除処理を実行する（Ｓ３５４）。最長経路エントリ設定方式の一括解除処理は、図４０（ｂ）に示すように、各実体ノードに対し、Ｓ３９５〜Ｓ３９６間の処理を行う（Ｓ３９４）。その実体ノードが最長経路エントリ設定方式で登録抑止した実体ノードかをチェックする（Ｓ３９５）。ここでは、実体ノード３３６がチェック条件に一致するため、その実体ノード３３６を登録対象に設定する（Ｓ３９６）。
【０１７０】
次に、選択方式に集約経路エントリ設定方式が設定されているかをチェックする（Ｓ３５０）。ここでは、設定されていないため、旧選択方式に集約経路エントリ設定方式が設定されているかをチェックする（Ｓ３５３）。ここでは、設定されているため、集約経路エントリ設定方式の一括解除処理を実行する（Ｓ３５４）。集約経路エントリ設定方式の一括解除処理は、図４１（ｂ）に示すように、各実体ノードに対し、Ｓ４０６〜Ｓ４０８間の処理を行う（Ｓ４０５）。その実体ノードが集約経路エントリ設定方式で生成した集約経路エントリを持つ実体ノードかをチェックする（Ｓ４０６）。ここでは、実体ノード３３０、３３２がチェック条件に一致するため、集約経路エントリ３３０、３３２を削除し（Ｓ４０７）、その実体ノード３３０、３３２の下位実体ノード３３１、３３２、３３５、３３６を登録対象に設定する（Ｓ４０８）。
【０１７１】
次に、選択方式に補完経路エントリ設定方式が設定されているかをチェックする（Ｓ３５０）。ここでは、設定されていないため、旧選択方式に補完経路エントリ設定方式が設定されているかをチェックする（Ｓ３５３）。ここでは、設定されているため、補完経路エントリ設定方式の一括解除処理を実行する（Ｓ３５４）。補完経路エントリ設定方式の一括解除処理は、図４２（ｂ）に示すように、各実体ノードに対し、Ｓ４１６〜Ｓ４１８間の処理を行う（Ｓ４１５）。その実体ノードは補完経路エントリ設定方式で生成した集約経路エントリを持つ実体ノードかをチェックする（Ｓ４１６）。ここでは、実体ノード３３１がチェック条件に一致するため、その実体ノード３３１の下位実体ノード３３３、３３８，３３９を登録対象に設定し（Ｓ４１７）、集約経路エントリ３３１、補完経路エントリ３３９を削除する（Ｓ４１８）。
【０１７２】
また、削除された集約経路エントリ、補完経路エントリに対し、各経路エントリを削除経路エントリとした、図３２に示した経路エントリ削除時の処理が行われる。以上により、図３４（ａ）に示すようなＲａｄｉｘツリーに戻される。
【０１７３】
Ｄ−３．適用する経路エントリ設定方式を登録状況により動的に決定する場合
図３７は、適用する経路エントリ設定方式をフォワーディングテーブルの登録状況により動的に決定するための処理フローを示すフローチャートである。このフローチャートは、経路エントリが追加、削除、および変更された場合において、図３１、図３２、図３３に示した処理の実行後に実行される。
【０１７４】
処理フローは、まず、包括経路エントリ設定方式の動的適用設定処理（Ｓ３６０）、最長経路エントリ設定方式の動的適用設定処理（Ｓ３６１）、集約経路エントリ設定方式の動的適用設定処理（Ｓ３６２）、補完経路エントリ設定方式の動的適用設定処理、または未登録補完経路エントリ設定方式の動的適用設定処理（Ｓ３６３）の順に実行する。
【０１７５】
次に、補完経路エントリ設定方式の動的適用解除処理、または未登録補完経路エントリ設定方式の動的適用解除処理（Ｓ３６４）、集約経路エントリ設定方式の動的適用解除処理（Ｓ３６５）、最長経路エントリ設定方式の動的適用解除処理（Ｓ３６６）、包含経路エントリ設定方式の動的適用解除処理（Ｓ３６７）の順に実行する。このような処理の後、経路登録部１７において、登録要否が変化した経路エントリに対し、登録抑止解除された経路エントリ、登録抑止された経路エントリの順で、フォワーディングテーブルの更新を行う。
【０１７６】
ここで、各経路エントリ設定方式の動的適用設定処理及び動的適用解除処理は、動的適用更新処理として、図３８に示す。図３８は、図３７における各経路エントリ設定方式の動的適用更新処理のフローを示すフローチャートである。図３８において、（ａ）は、その経路エントリ設定方式の動的適用設定処理を示し、（ｂ）は、その経路エントリ設定方式の動的適用削除処理を示す。
【０１７７】
図３８（ａ）に示すように、各経路エントリ設定方式の動的適用設定処理では、登録経路エントリ数が設定規定値以上かをチェックする（Ｓ３７０）。このチェック条件を満足する場合、選択方式に該経路エントリ設定方式が設定されているかをチェックする（Ｓ３７１）。設定されていない場合、その経路エントリ設定方式の一括設定処理を実行し（Ｓ３７２）、選択方式に、その経路エントリ設定方式を設定する（Ｓ３７３）。
【０１７８】
また、図３８（ｂ）に示すように、各経路エントリ設定方式の動的適用解除処理では、登録経路エントリ数が解除規定値以下かをチェックする（Ｓ３７４）。そのチェック条件を満足する場合、選択方式に、その経路エントリ設定方式が設定されているかをチェックする（Ｓ３７５）。設定されている場合、その経路エントリ設定方式の一括解除処理を実行し（Ｓ３７６）、選択方式から、その経路エントリ設定方式を解除する（Ｓ３７７）。
【０１７９】
各経路エントリ設定方式の一括設定処理、各経路エントリ設定方式の一括解除処理は、適用された、または適用解除された経路エントリ設定方式を一括して設定、または解除しているものであり、構成情報により適用する経路エントリ設定方式を選択する場合と同じとなる。
【０１８０】
経路制御プロトコルを使用し、その経路エントリ設定方式を適用したルーティングテーブル１８に基づき、他の通信装置に配布する経路情報は、その経路エントリ設定方式を適用していない場合と同一の経路情報を配布することができる。これは、その経路エントリ設定方式は、経路エントリの登録抑止情報、自動生成した集約経路エントリ、補完経路エントリの識別情報を各ノードの情報として持っている。これに基づき、経路制御プロトコルは、経路エントリの登録抑止情報を意識せず、また、生成した集約経路エントリや補完経路エントリを配布の対象外して取り扱うことにより実現できる。これにより、他の通信装置に影響を与えることなく、自通信装置のフォワーディングテーブル２２に登録する経路エントリ数を削減することができる。
【０１８１】
Ｅ．経路エントリ設定方式を適用した通信装置における運用面での考慮点
最後に、本実施例における経路エントリ設定方式を適用した通信装置における運用面での考慮を説明する。
【０１８２】
本実施例では、上記で説明した各経路エントリ設定方式を適用し、フォワーディングテーブル２２に登録する経路エントリ数を削減する。削減される経路エントリは、経路情報の内容により動的に変化する。そのため、フォワーディングテーブル２２への登録状況を参照できることが望ましい。また、フォワーディングテーブル２２への登録状況を運用者に自律的に通知できることが望ましい。
【０１８３】
そこで、本実施例では、登録状況の参照を行うために、フォワーディングテーブル２２に登録された経路エントリ数や登録が抑止された経路エントリ数をカウントすることにより、フォワーディングテーブル２２への登録状況を、運用コマンドやＭＩＢ（Management Information Base）などで表示するようにしてもよい。また、上記説明の通り、Ｒａｄｉｘツリーのノード上には、各経路エントリの状態（登録要否情報、集約経路エントリ、補完経路エントリなどの経路種別）を記録しているため、ルーティングテーブル１８、またはフォワーディングテーブル２２上の各経路エントリの内容や状態などを表示するようにしてもよい。
【０１８４】
また、本実施例では、登録状況の通知を行うために、フォワーディングテーブル２２への登録状況（フォワーディングテーブル２２に登録された経路エントリ数が閾値を超えた場合や閾値を下回った場合など）に応じて、システムメッセージの出力や、ＳＮＭＰ（Simple Network Management Protocol）のトラップなどにより、運用者にアラームを通知するようにしてもよい。
【０１８５】
また、本実施例においては、パケットの転送先を選択するためのフォワーディングテーブル２２の検索を、高速に検索するためにＣＡＭ検索方式を推奨する。しかしながら、本発明は、フォワーディングテーブルの構造に依存せず、フォワーディングテーブルに登録する経路エントリ数を削減するものであり、フォワーディングテーブルの構造を限定するものではない。
【符号の説明】
【０１８６】
１０…通信装置
１１…ルーティング機構
１２…フォワーディング機構
１３…ＮＩＣ
１４…経路学習部
１５…経路表作成部
１６…登録制御部
１７…経路登録部
１８…ルーティングテーブル
１９…受信処理部
２０…経路検索部
２１…送信処理部
２１Ａ…パケット転送部
２２…フォワーディングテーブル
５１２…ＣＰＵ
５１４…ＲＡＭ
５１６…ＣＡＭ
【図１】
2010226340.tif 000003
【図２】
2010226340.tif 000004
【図３】
2010226340.tif 000005
【図４】
2010226340.tif 000006
【図５】
2010226340.tif 000007
【図６】
2010226340.tif 000008
【図７】
2010226340.tif 000009
【図８】
2010226340.tif 000010
【図９】
2010226340.tif 000011
【図１０】
2010226340.tif 000012
【図１１】
2010226340.tif 000013
【図１２】
2010226340.tif 000014
【図１３】
2010226340.tif 000015
【図１４】
2010226340.tif 000016
【図１５】
2010226340.tif 000017
【図１６】
2010226340.tif 000018
【図１７】
2010226340.tif 000019
【図１８】
2010226340.tif 000020
【図１９】
2010226340.tif 000021
【図２０】
2010226340.tif 000022
【図２１】
2010226340.tif 000023
【図２２】
2010226340.tif 000024
【図２３】
2010226340.tif 000025
【図２４】
2010226340.tif 000026
【図２５】
2010226340.tif 000027
【図２６】
2010226340.tif 000028
【図２７】
2010226340.tif 000029
【図２８】
2010226340.tif 000030
【図２９】
2010226340.tif 000031
【図３０】
2010226340.tif 000032
【図３１】
2010226340.tif 000033
【図３２】
2010226340.tif 000034
【図３３】
2010226340.tif 000035
【図３４】
2010226340.tif 000036
【図３５】
2010226340.tif 000037
【図３６】
2010226340.tif 000038
【図３７】
2010226340.tif 000039
【図３８】
2010226340.tif 000040
【図３９】
2010226340.tif 000041
【図４０】
2010226340.tif 000042
【図４１】
2010226340.tif 000043
【図４２】
2010226340.tif 000044
【図４３】
2010226340.tif 000045
【図４４】
2010226340.tif 000046
【図４５】
2010226340.tif 000047
【図４６】
2010226340.tif 000048