JP4556761B2 - パケット転送装置 - Google Patents

Description

本発明は、ネットワーク中継点に設置されパケット転送装置に利用される、ルーティングテーブル（経路検索テーブル）の構成方法に関する。

近年のインターネットトラフィックの急速な増加により、ネットワーク中継点に設置されるパケット転送装置には、より高速なパケット転送技術が要求されている。パケット転送装置は、到着したパケットを自身が接続しているどのネットワークへ転送すべきかを、到着パケットが保持する宛先アドレスによって判断し、転送する。前記の宛先アドレスにより、パケットの転送先を決定するために、パケット転送装置はルーティングテーブル（経路検索テーブル）を利用する。

ルーティングテーブルは、ＩＰアドレスの上位ビットでありネットワークを表すプレフィックスと、このプレフィックスに対応する次ホップＩＰアドレスと出力回線番号から成る経路エントリを複数格納する。パケット転送装置は、パケットが入力されるとルーティングテーブル内のプレフィックスと、パケット内の宛先ＩＰアドレスの上位ビットが一致する経路エントリを探し出し、一致した経路エントリの内容を入力パケットの次ホップＩＰアドレスおよび出力回線番号と判定する。

前記の宛先検索動作は、パケット転送処理のボトルネックとなる処理であり、ネットワークの回線速度が向上するに連れより顕著な問題となっている。さらに、近年のインターネットトラフィックの急速な増加により、ルーティングテーブルに必要な登録エントリ数が急増していることもパケット転送装置にとって問題である。そこで、非特許文献１に示されるように、ＩＰアドレス空間を有効利用するために、任意のプレフィックス位置によりＩＰアドレスをネットワークアドレスとホストアドレスに分割するＣＩＤＲ（Ｃｌａｓｓｌｅｓｓ Ｉｎｔｅｒ−Ｄｏｍａｉｎ Ｒｏｕｔｉｎｇ）が１９９０年中頃に導入された。ＣＩＤＲにより、複数のエントリを単一のエントリで表現可能になったため、ルーティングテーブルの必要エントリ数の増加率はやや穏やかになったものの、http://bgp.potaroo.net/index-bgp.htmlに示されるＩＰｖ４ ＢＧＰ（Ｂｏｒｄｅｒ Ｇａｔｅｗａｙ Ｐｒｏｔｏｃｏｌ） Ｒｅｐｏｒｔによれば、ネットワークコアのパケット転送装置に必要なルーティングテーブルエントリ数は２００４年末時点で約１８万エントリ強に達している。

ＣＩＤＲの導入は、ルーティングテーブルの必要エントリ数を削減できるメリットをもたらしたが、ロンゲスト・プレフィックス・マッチ（最長一致検索）を必要とするため、ＣＩＤＲ導入前に利用されていた固定長比較（完全一致検索）と比べてルーティングテーブル検索処理が複雑になるデメリットを同時に生じさせた。すなわち、検索の結果、ルーティングテーブルの複数エントリが検索条件に一致する可能性があるため、一致した検索結果のうち、最も多くのビットが一致する結果を選択する必要（ロンゲスト・プレフィックス・マッチ）が生じた。

このルーティングテーブル検索を図２に示すルーティングテーブルを用いて具体的に説明する。図２のルーティングテーブル１０００には、ＩＰアドレスが８ビットで表現されるときに６つのエントリ１０００−１〜６が存在していることを示し、それぞれのエントリ１０００−１〜６はプレフィックスと等価な情報であるＩＰアドレス条件と、これらの各ＩＰアドレス条件に対応する次ホップＩＰアドレスおよび出力回線番号をから構成される。ここで、ＩＰアドレス条件とは、プレフィックスを上位ビットとし、ＩＰアドレスの残りのビットをマスク（＊）とした情報である。例えば、エントリ１０００−２の“０１１１１＊＊＊”は、上位５ビットが“０１１１１”であり、下位３ビットは“０００、００１、０１０、０１１、１００、１０１、１１０、１１１”のいずれでもよいことを示す。また、１０００−２〜６の“０１１１１＊＊＊”は “０１１１１/５”、“０１１０＊＊＊＊”は“０１１０/４”、“１０１０＊＊＊＊”は“１０１０/４”、“１０１＊＊＊＊＊”は“１０１/３”、“０１＊＊＊＊＊＊”は“０１/２”とそれぞれ表現することもできる。スラッシュ記号の後ろの数字はプレフィックス長と呼ばれ、プレフィックスのマスク以外の部分の長さを示す。

例えば、宛先ＩＰアドレスが二進数で“０１１１１０１０”のパケットが入力された場合を考える。この場合、エントリ１０００−２と１０００−６の二つのエントリのＩＰアドレス条件と入力した宛先ＩＰアドレスが一致するが、プレフィックス長が一番長いエントリ１０００−２の次ホップＩＰアドレスBと出力回線番号３が一致結果と判定される。

上記のルーティングテーブル検索を高速化するために、近年のハイエンドパケット転送装置ではＴＣＡＭ（Ｔｅｒｎａｒｙ Ｃｏｎｔｅｎｔｓ Ａｄｄｒｅｓｓａｂｌｅ Ｍｅｍｏｒｙ）と呼ばれるメモリデバイスを用いることが多い。例えば、ルーティングテーブル検索とフローの識別処理をＴＣＡＭにより高速に実現する方法が非特許文献２や非特許文献３に記載されている。

ＴＣＡＭは、一致条件のビット毎に「０」、「１」のほか、「０」でも「１」でも良いことを示す「＊（Ｄｏｎ’ｔ Ｃａｒｅ、Ｍａｓｋ）」の三種類の値を指定することが可能である。ＴＣＡＭは、複数ビットの一致条件を格納するエントリを複数備え、検索キーが入力されるとエントリ内の一致条件と検索キーの一致比較を全エントリに対し同時に行い、一致したエントリのアドレスの中でもっとも優先度の高い（例えば一番小さい）アドレス値を出力する。もっとも長いプレフィックスを持つＩＰアドレス条件を優先度の高いエントリに格納しておくことにより、ＴＣＡＭはロンゲスト・プレフィックス・マッチを実現可能である。

前述のＴＣＡＭは、高速なルーティングテーブル検索に適したメモリデバイスではあるものの、ＤＲＡＭ（Ｄｙｎａｍｉｃ Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）やＳＲＡＭ（Ｓｔａｔｉｃ Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）に比較して一桁から二桁程度消費電力が高く、同様に集積度が低く、最も高価なデバイスである点が問題である。

今日のパケット転送装置は、図３に示すように制御カード３００がルーティングテーブルの本体３０１を持ち、各ラインカード１００−ｉ（ｉ＝１〜Ｎ）はルーティングテーブル情報を独立して高速に検索できるように、制御カード３００のルーティングテーブル３０１と同一の内容のコピーをハードウェアが検索しやすい形式にした完全ルーティングテーブル２１０として備えている。近年のハイエンドパケット転送装置では、各ラインカードのルーティングテーブルに前述のＴＣＡＭを用いる構成がみられる。

特許文献１では、ネットワーク転送装置におけるルーティングテーブルおよびその検索機構を改善し、ネットワーク転送装置の大容量化、低遅延化（高速化）、低コスト化を図るために、制御カードのルーティングテーブル情報を分割した部分集合となる情報を各ラインカードに分散ルーティングテーブルとして配置する方法を提案している。また、分散ルーティングテーブルは、ルーティングテーブルの持つ情報の一部の複製を格納するルーティングテーブルキャッシュを有し、あるルーティングテーブルキャッシュにおいて検索がヒットしなかった場合、そのルーティングテーブルキャッシュに対応するルーティングテーブルを検索して、宛先を検索する構成を提案している。

特開２００４−２２１８０７号公報

ＲＦＣ１５１９ 宇賀 雅則、塩平 公平 著、「連想メモリを用いたフロー識別法」、社団法人電子情報通信学会、2000年総合大会講演論文集、SB-4-2、第６５４頁 ＩＤＴ Ｗｈｉｔｅ Ｐａｐｅｒ "Ｏｐｔｉｍｕｍ Ｓｅａｒｃｈ Ｍｅｔｈｏｄｓ ｆｏｒ Ｓｗｉｔｃｈ／Ｒｏｕｔｅｒ Ｄａｔａｂａｓｅｓ ｉｎ Ａｃｃｅｓｓ ａｎｄ Ｍｅｔｒｏ Ｅｄｇｅ Ｎｅｔｗｏｒｋｓ"

宛先アドレスに対応する転送情報は、日々増加しているため、パケット転送装置の各ラインカードに搭載する前記転送情報を記録するためのルーティングテーブルに必要なメモリ量も増加する必要がある。やがて、各ラインカードの必要メモリ量は実装の許容範囲を超える恐れがあるため、必要な総メモリ量を増加させずに、ルーティングテーブルに登録可能なエントリ数を増加させることが必要である。なおかつ、ルーティングテーブル検索はパケット転送装置においてボトルネックとなる処理であるため、高速な経路検索を実現する必要がある。

前述した図３のように制御カード３００のルーティングテーブルの本体３０１のコピーを各ラインカード１００に搭載するＴＣＡＭに格納する手法は、ルーティングテーブルを大容量化する場合、ＴＣＡＭの実装量を増加する必要があるため、装置全体の消費電力およびコストの増加を招く問題を抱えている。

また、特許文献１に示すように、パケット転送装置内で基本的にひとつだけのルーティングテーブルを搭載し、各ラインカードは前記ルーティングテーブルの各部分だけを分散配置する手法は、ルーティングテーブルを大容量化しても搭載するメモリ量が大きく増加しない点で有望である。しかしながら、あるラインカードのルーティングテーブルを複数のラインカードが検索する場合、単にルーティングテーブルの各部を分散配置するだけではメモリ競合による検索速度の低下が発生し問題である。このため、特許文献１では、ルーティングテーブルキャッシュの搭載が必然であるが、このルーティングテーブルキャッシュは、完全一致する宛先ＩＰアドレス情報のエントリしか格納できないため、キャッシュミスの可能性が高く、またキャッシュミス時に対応するＩＰアドレス情報を当該キャッシュに格納するまでのレイテンシが長いという欠点を持っている。

本発明は、これらの問題点に鑑みてなされたもので、二種類のルーティングテーブルを各ラインカードに配置し制御することにより、ルーティングテーブルの大容量化、すなわち、ルーティングテーブルに登録可能なエントリ数を増加させることを目的とする。また、同時にルーティングテーブル検索の高速化を実現することを目的とする。

本発明では、パケット転送装置の各ラインカードに、二種類の異なる役目を持つルーティングテーブルを具備する。第一のルーティングテーブルは、頻繁に利用する転送情報を一連のグループとして記録するための自ラインカード専用のローカルルーティングテーブルである。第二のルーティングテーブルは、転送情報を他のラインカードと一致しないように分散して記録し、すべての分散情報を合わせるとパケット転送装置が保持する全ての転送情報と一致する分散共有ルーティングテーブルである。

各ラインカードは接続されるネットワーク回線に依存する宛先検索の局所性、すなわち、完全に同一の宛先や、プレフィックスの上位部が同一の宛先が出現しやすい性質を利用できる。よって、ローカルルーティングテーブルは、パケット転送装置が保持する全ての転送情報を一度に記録する必要がなく、比較的小容量のメモリで実現してよい。各ラインカードは、パケットの宛先検索を実施する際に、最初にローカルルーティングテーブルを検索し、当該転送情報があれば利用する。当該転送情報がなければ、対応する分散共有ルーティングテーブルから検索に利用した宛先アドレスに関連すると判断した全ての転送情報をローカルルーティングテーブルにコピーしてから利用する。

分散共有ルーティングテーブルにより、パケット転送装置全体の総メモリ量を増加させずに、ルーティングテーブルに登録可能なエントリ数を増加することができる。
ローカルルーティングテーブルにより、自ラインカードは他ラインカードに邪魔されず、頻繁に利用する転送情報を利用できるため、ルーティングテーブル検索を高速に行うことができる。

また、分散共有ルーティングテーブルからローカルルーティングテーブルへは宛先アドレスに関連すると判断した全ての転送情報をコピーするため、宛先アドレスに完全に対応する唯一つの転送情報だけを分散共有ルーティングテーブルからコピーする単純なキャッシュ方式と比較して、分散共有ルーティングテーブルを検索する頻度が減少するため、分散共有ルーティングテーブルを複数のラインカードが検索することにより発生するメモリアクセスボトルネックの解消も可能となる。

以下、より詳細な内容を添付図面に基づいて実施例で説明する。

図１に本発明を適用したパケット転送装置のブロック図を示す。パケット転送装置はパケットを入力するＮ個の入力回線１０−ｉ（ｉ＝１〜Ｎ）、Ｎ個の出力回線２０−ｉ（ｉ＝１〜Ｎ）、一連のパケット処理を実施するためのＮ個のラインカード１００−ｉ（ｉ＝１〜Ｎ）、パケット転送装置全体を制御するための制御カード３００、前記ラインカード１００−ｉと前記制御カード３００を結合するためのスイッチファブリック４００から構成される。

前記ラインカード１００−ｉは、ネットワーク側とのパケットの送受信を行うネットワークインタフェース部１０２、パケット処理を実施するパケット処理部１０３、パケット処理のうちルーティングテーブル検索を実施する経路検索制御部１０５、自ラインカードが利用した転送情報を保持するための第一のルーティングテーブル（ローカルルーティングテーブル）２０１と、パケット転送装置内の全てのラインカード間で転送情報を分散共有するための第二のルーティングテーブル（分散共有ルーティングテーブル）２０２、スイッチファブリックとのパケットの送受信を行うスイッチファブリックインタフェース１０４、制御用のＣＰＵ１１０から構成される。

前記制御カード３００は、第三のルーティングテーブル（完全ルーティングテーブル）３０１を保持しており、完全ルーティングテーブル３０１は、前記分散共有ルーティングテーブル２０２の和集合と一致する。

まず、パケット転送装置の動作概略について説明する。パケットが入力回線１０−ｉより入力されると、ネットワークインタフェース１０２は、パケット処理部１０３が認識可能なフォーマットへパケットを変換し転送する。
パケット処理部１０３は、受信パケットを蓄積し、受信パケットから抽出した宛先ＩＰアドレスを経路検索制御部１０５へ転送する。
経路検索制御部１０５はローカルルーティングテーブル２０１、分散共有ルーティングテーブル２０２を利用し、次ホップＩＰアドレスと出力回線番号を判定し、結果をパケット処理部１０３へ転送し、パケット処理部はスイッチファイブリックインタフェース１０４へ転送する。

スイッチファイブリックインタフェース１０４は、受信パケットをスイッチファブリック４００へ転送し、スイッチファブリック４００は、受信パケットに記録されている出力回線番号に相当するラインカード１００−ｉへ当該パケットを転送する。

パケットを受信した当該ラインカード１００−ｉは、当該パケットをスイッチファブリックインタフェース１０４を介してパケット処理部１０３へ転送する。前記パケット処理部１０３は、経路検索制御部１０５へ前記パケットが含む次ホップＩＰアドレスを転送する。前記経路検索制御部１０５は、前記次ホップＩＰアドレスより次ホップのＭＡＣ（Ｍｅｄｉａ Ａｃｃｅｓｓ Ｃｏｎｔｒｏｌ）アドレス判定し、ＭＡＣアドレス情報として、前記パケット処理部１０３へ転送する。前記パケット処理部１０３は次ホップＭＡＣアドレスをパケットの宛先ＭＡＣアドレスに書き込み、送信元ＭＡＣアドレスを次ラインカードのネットワークインタフェース１０２のＭＡＣアドレスに書換え、パケットを出力回線２０−ｉへ送信する。

次に、本発明によるパケット転送装置のルーティングテーブル制御方法および検索方法について詳細動作を説明する。まず、ローカルルーティングテーブル２０１−ｎ（ｎ＝１，２，３）と分散共有ルーティングテーブル２０２−ｎ、完全ルーティングテーブル３０１の保持するＩＰアドレス条件の関係を図４に示す。この図４では、理解を容易にするため、ＩＰｖ４のＩＰアドレスを例とし、完全ルーティングテーブル３０１に登録されているＩＰアドレス条件を６グループ分だけとしている。実際には、より多数のグループが存在する。また、ＩＰｖ４アドレスに限らずＩＰｖ６アドレスなどでもよい。

分散共有ルーティングテーブル２０２−ｎは、完全ルーティングテーブル３０１の登録情報の一部ずつを互いに重複しないように保持する。図４の例では、ラインカード１００−１の分散共有ルーティングテーブル２０２−１はグループ１とグループ２、ラインカード１００−２の分散共有ルーティングテーブル２０２−２はグループ３とグループ４、ラインカード１００−３の分散共有ルーティングテーブル２０２−３はグループ５とグループ６を保持する。グループ分けは、制御カード３００により実施される。

ここで、グループとは、ロンゲスト・プレフィックス・マッチを実施する際にチェックすべきアドレス条件すべてを指す。すなわち、複数のＩＰアドレス条件があった時、プレフィックス部分が他のＩＰアドレス条件に内包される場合、それらのＩＰアドレス条件群を同一グループと呼ぶ。例えば、図４において１００．１３２．１０．８/３０は１００．１３２．１０．０/２４に内包される。このため、同一のグループとしている。グループ２〜６も同様の理由によりグループとしている。

ここで、プレフィックス長が例えば１の場合、すべてのＩＰアドレス条件が同一グループとなり、そもそもグループ分けをする意味がなくなる。しかしながら、http://bgp.potaroo.net/index-bgp.htmlのデータによるとＩＰｖ４では８未満のプレフィックス長は、事実上利用されていない。同様に、ＩＰｖ６では２０未満のプレフィックス長は、事実上利用されていない。よって、ＩＰｖ４の場合は、少なくとも２５６以上のグループ、ＩＰｖ６の場合は、少なくとも１メガ（１０４８５７６）以上のグループに分かれることが期待できる。

また、図５に代表的なＩＰｖ４のルーティングテーブル情報の例として、プレフィックス長と対応するエントリ数の関係を示す。多くのＩＰｖ４のルーティングテーブルは同様の傾向を示すとされており、プレフィックス長２４の全体に占める割合が非常に高く、プレフィックス長１６から２３までがついで高く、これら１６から２４の９種類のプレフィックス長だけで全体の８割を占めることが多い。プレフィックス長の長いＩＰアドレス条件がプレフィックス長の短いＩＰアドレス条件に内包されていなければ（同一グループでなければ）、上記に述べた最低数より多くのグループが存在することになる。

ローカルルーティングテーブル２０１は、検索に利用されたＩＰアドレスが含まれるＩＰアドレス条件のグループを分散共有ルーティングテーブルからコピーして利用する。通常、ハイエンドのパケット転送装置は複数枚（例えば１６枚）のラインカードと前記ラインカード数と同じかそれ以上のネットワーク回線を具備している。あるラインカードにネットワークから入力されるパケット群が、すべてのＩＰアドレス領域に対してアクセスすることは稀である。よって、パケット転送装置の各ラインカードは特定の頻繁に利用されるＩＰアドレス条件のグループが異なる可能性が高い。この性質を利用すると、ローカルルーティングテーブル２０１は、すべての分散共有ルーティングテーブル２０２のＩＰアドレス条件すべて、すなわち、完全ルーティングテーブル３０１と同等のＩＰアドレス条件を保持している必要がない。よって、ローカルルーティングテーブル２０１は巨大である必要はない。

図４の例では、ローカルルーティングテーブル２０１−１はグループ１、ローカルルーティングテーブル２０１−２はグループ１とグループ３、ローカルルーティングテーブル２０１−３はグループ５、それぞれのＩＰアドレス条件をコピーして保持している状態を示す。また、それぞれのローカルルーティングテーブル２０１は、自身が保持していないＩＰアドレス条件のグループがどの分散共有ルーティングテーブルに保持されているかのポインタ情報をすべて保持している。前記ポインタ情報が存在しないＩＰアドレス条件は、完全ルーティングテーブル３０１にも登録がなく、宛先不明であるためデフォルトルート宛として扱う。

次に、より具体的なローカルルーティングテーブル２０１、分散共有ルーティングテーブル２０２の構成例を示した後、ＩＰアドレス条件の登録方法、アクセス方法について説明する。
まず、ローカルルーティングテーブル２０１、分散共有ルーティングテーブル２０２の構成例として、消費電力を上げずにより多くのエントリを保持するための手段として、ＴＣＡＭを利用せず、ＤＲＡＭもしくはＳＲＡＭを複数個並列に並べ利用するｍ−Ｔｒｉｅ（Ｍｕｌｔｉ―ｌｅｖｅｌ Ｔｒｉｅ）アルゴリズムを適用する実施例について図６と図７を用いて説明する。

まず、検索の際に利用する検索キーである宛先ＩＰアドレスを、複数個の塊に分割する。ＩＰｖ４であれば、３２ビットアドレスを、例えば、Ｋ０、Ｋ１、Ｋ２の３箇所に分割する。例えば、Ｋ０＝１６ビット、Ｋ１＝８ビット、Ｋ２＝８ビットが代表的な分割方法である。分割部位ごとに検索用のノードを生成する。この例では、最上位のルートノードＫ０は２¹⁶個のエントリを持つ。次レベルのノードＫ１は、２^８個のエントリを持つノードを複数個持つ。同様に最下位レベルのノードＫ２も、２^８個のエントリを持つノードを複数個持つ。レベル１ノードおよびレベル２ノードの複数個とは、現実的な実装量とのトレードオフになるが、例えば４０９６個とする。各ノードは、複数個のＤＲＡＭもしくはＳＲＡＭにより構成可能である。

次に、分割したＩＰｖ４の上位１６ビットにより、ルートノード内のエントリを選択してレベル１ノードへのポインタを獲得する。獲得した前記レベル１へのポインタにより、レベル１ノードを選択し、前記レベル１ノードにおいて、ＩＰｖ４の次の８ビットにより、当該レベル１ノード内のエントリを選択してレベル２ノードへのポインタを獲得する。獲得した前記レベル２へのポインタにより、レベル２ノードを選択し、前記レベル２ノードにおいて、ＩＰｖ４の最後の８ビットにより、当該レベル２ノード内のエントリを選択して検索結果、もしくは検索結果、すなわち、「次ホップＩＰアドレスと出力回線番号」が収められているメモリへのポインタを獲得する。以降では、最終レベルノードには、検索結果が収められているものとして説明を行う。

図６は、ローカルルーティングテーブル２０１をＫ０＝１６ビット、Ｋ１＝８ビット、Ｋ２＝８ビットのｍ−Ｔｒｉｅで構成した例である。６４キロエントリを持つレベル０ルートノード５００を１個、２５６エントリを持つレベル１ノード５１０が４０９６個、２５６エントリを持つレベル２ノード５２０が４０９６個で構成されている。各ノードのエントリ内容を次に示す。

ルートノードのエントリ５０１は、有効ビット５０２、プレフィックス長情報５０３、情報元ラインカード番号５０４、ローカルノード登録済みビット５０５、ポインタ５０６で構成されている。有効ビット５０２がセットされているとき、当該エントリが有効となる。プレフィックス長情報５０３とは、当該エントリのＩＰアドレス条件のプレフィックス長である。情報元ラインカード番号５０４は、当該ＩＰアドレス条件が記録されている分散共有ルーティングテーブル２０２のラインカード番号を示す。ローカルノード登録済みビット５０５は、当該エントリがローカルルーティングテーブル２０１にコピーされていることを示す。ポインタ５０６は、レベル１ノードを選択するためのポインタである。この例では４０９６あるレベル１ノードのうちひとつを指す。

レベル１ノードのエントリ５１１は、有効ビット５１２、プレフィックス長情報５１３、（レベル２ノードへの）ポインタ５１４で構成されている。
レベル２ノードのエントリ５２１は、有効ビット５２２、プレフィックス長情報５２３、検索結果５２４で構成されている。

図７は、分散共有ルーティングテーブル２０２をＫ０＝１６ビット、Ｋ１＝８ビット、Ｋ２＝８ビットのｍ−Ｔｒｉｅで構成した例である。６４キロエントリを持つレベル０ルートノード５００を１個、２５６エントリを持つレベル１ノード５１０が４０９６個、２５６エントリを持つレベル２ノード５２０が４０９６個で構成されている。前記のローカルルーティングテーブル２０１と同一の構成を例示しているが、レベル１ノード、レベル２ノードの数は、ローカルルーティングテーブル２０１より多くしても構わない。各ノードのエントリ内容を次に示す。

ルートノードのエントリ６０１は、有効ビット６０２、プレフィックス長情報６０３、共有ラインカード情報６０４、ポインタ６０５で構成されている。有効ビット６０２がセットされているとき、当該エントリが有効となる。プレフィックス長情報６０３とは、当該エントリのＩＰアドレス条件のプレフィックス長である。共有ラインカード情報６０４は、当該ＩＰアドレス条件がコピーされているローカルルーティングテーブル２０１のあるラインカード番号を示す。複数枚のラインカードで共有される可能性があるため、ひとつのラインカードを１ビットで表現する形式が適している。ポインタ６０５は、レベル１ノードを選択するためのポインタである。この例では４０９６あるレベル１ノードのうちひとつを指す。

レベル１ノードのエントリ６１１は、有効ビット６１２、プレフィックス長情報６１３、（レベル２ノードへの）ポインタ６１４で構成されている。
レベル２ノードのエントリ６２１は、有効ビット６２２、プレフィックス長情報６２３、検索結果６２４で構成されている。

ローカルルーティングテーブル２０１、および分散共有ルーティングテーブル２０２の各ノードは、先に述べたようにＴＣＡＭではなく、ＤＲＡＭもしくはＳＲＡＭを用いて構成する。図８に各ノードをＤＲＡＭで構成した例を示す。いずれのテーブルも基本的な構成は同等であり、ルートノード５００、ＲＯＷアドレスにより選択可能な４０９６個のノードを含むレベル１ノード５１０、ＣＯＬＵＭＮアドレスにより選択可能な２５６個のレベル１ノードのエントリのセレクタ５１９、ＲＯＷアドレスにより選択可能な４０９６個のノードを含むレベル２ノード５２０、ＣＯＬＵＭＮアドレスにより選択可能な２５６個のレベル２ノードのエントリのセレクタ５２９により構成される。

各ノードは独立したＤＲＡＭを用いる。ＤＲＡＭは、汎用パッケージのＤＤＲ−ＳＤＲＡＭ（Ｄｏｕｂｌｅ Ｄａｔａ Ｒａｔｅ−Ｓｙｎｃｈｒｏｎｏｕｓ ＤＲＡＭ）やＦＣＲＡＭ（Ｆａｓｔ Ｃｙｃｌｅ ＲＡＭ）を用いてもよいし、経路検索制御部１０５と同一のＬＳＩパッケージ中に組み込みＤＲＡＭの形式で用いてもよい。後者の組み込みＤＲＡＭは、製造上のコストは嵩むが、アクセスレイテンシを短縮し、かつ、専用の幅広のＤＲＡＭ内部バスを利用し、ＤＲＡＭと経路検索制御部１０５の間で大量のデータを一度にやり取りできる点で有利である。

次に、パケット転送装置にＩＰアドレス条件を新たに登録する際の動作について、図１０に示す無効化型分散共有ルーティングテーブルの更新動作例のフローチャートを利用して説明する。ここで、無効化型とは、分散共有ルーティングテーブル２０２を更新する際、対応するＩＰアドレス条件を持つローカルルーティングテーブル２０１の当該エントリを破棄（無効化）することを意味する。

パケット転送装置の保持する完全なルーティングテーブルは、制御カード３００が具備する完全ルーティングテーブル３０１で管理される。新たなＩＰアドレス条件が完全ルーティングテーブル３０１に追加されると（図９の８０１→８０２）、制御カード３００は対応する分散共有ルーティングテーブル２０２へ、前記ＩＰアドレス条件を図７で示したエントリ形式で、ノードの関連するエントリすべてに登録する（図９の８０３）。

ここで、関連するエントリとは、例えばＩＰアドレス条件が１１１．２２２．３．４/１５の場合、ルートノード５００では、１１１．２２２と１１１．２２３の二つのエントリであり、両エントリのポインタ５０６は、ともにレベル１ノード５１０で共通のノードを指す。プレフィックス長１５なので、レベル１、２ノード内の当該ノードの２５６エントリはすべて当該エントリとなる。

同様の例をいくつか挙げると、ＩＰアドレス条件が１１１．２２２．３．４/１４の場合、関連するエントリとは、ルートノード５００では、１１１．２２０と１１１．２２１、１１１．２２２、１１１．２２３の四つのエントリであり、全エントリのポインタ５０６は、ともにレベル１ノード５１０上の共通のエントリを指す。プレフィックス長１４なので、レベル１、２ノード内の当該ノードの２５６エントリはすべて当該エントリとなる。

ＩＰアドレス条件が１１１．２２２．３．４/２４の場合、関連するエントリとは、ルートノード５００では、１１１．２２２のただ一つのエントリであり、前記エントリのポインタ５０６は、レベル１ノード５１０のある一つのノードを指す。レベル１ノード５１０の当該ノードでは、ＩＰアドレス条件の次の８ビットが示すエントリ３が関連するエントリである。レベル２ノード５２０では、プレフィックス長２４なので、当該レベル２ノードの２５６エントリが関連するエントリである。

ＩＰアドレス条件が１１１．２２２．３．４/３０の場合、関連するエントリとは、ルートノード５００では、１１１．２２２のただ一つのエントリであり、前記エントリのポインタ５０６は、レベル１ノード５１０のある一つのノードを指す。レベル１ノード５１０の当該ノードでは、ＩＰアドレス条件の次の８ビットが示すエントリ３が関連するエントリである。レベル２ノード５２０では、プレフィックス長２８で最後の８ビットが４なので、当該レベル２ノードのエントリ４、５、６、７の四つのエントリが関連するエントリである。

まとめると、プレフィックス長をＬで表現するとき、Ｌが１６未満（図５の例より、通常、Ｌは８以上）の場合は、ルートノード５００において２^{（Ｌ−１６）}個のエントリが同一の内容で埋め尽くされ、当該レベル１ノード５１０、レベル２ノード５２０の２５６エントリすべてが同一の内容で埋め尽くされている。

Ｌが１６以上２４未満の同様は、ルートノード５００は１エントリのみ利用され、当該レベル１ノード５１０の対応する２^{（２４−Ｌ）}個のエントリが同一の内容で、また当該レベル２ノード５２０の２５６エントリすべてが同一の内容で埋め尽くされている。
Ｌが２４以上の場合は、ルートノード５００およびレベル１ノード５１０は１エントリのみ利用され、当該レベル２ノード５２０の対応する２^{（３２−Ｌ）}個のエントリが同一の内容で埋め尽くされている。

以上、「関連するエントリ」の例を示した。ここで、前記ＩＰアドレス条件を含むグループがなければ新たに生成し、すべてのローカルルーティングテーブル２０１のルートノードへ前記グループが登録されている分散共有ルーティングテーブル２０２の存在するラインカード番号を「情報元ラインカード番号５０４」として登録し、有効ビット５０２をセットして更新処理を終了する（図９の８０４→８０５→８０８）。

前記ＩＰアドレス条件を含むグループが存在すれば、分散共有ルーティングテーブル２０２のルートノードエントリ６０１の共有ラインカード情報６０４を参照し、当該グループがいずれかのローカルルーティングテーブル２０１にコピーされているかどうか確認する（図９の８０６）。いずれかのローカルルーティングテーブル２０１にコピーされていれば、装置内でのローカルルーティングテーブル情報の一貫性を維持するために前記コピー内容に対して無効化型または更新型の処理を行う。まず、無効化型の場合のメリットは、更新型に比べて制御論理実装が容易な点である。無効化型の場合、当該ローカルルーティングテーブル２０１の当該ＩＰアドレス条件を破棄し、更新処理を終了する（図９の８０７→８０８）。なお、破棄の際には、ローカルルーティングテーブル２０１の関連するノードのエントリのプレフィックス長情報５０３、５１３、５２３を参照し、破棄要求のあったプレフィックス長のＩＰアドレス条件のみを破棄する。例えば、ＩＰアドレス条件として１１１．２２２．０．０/１６と１１１．２２２．０．０/２４がそれぞれ登録されている場合、１１１．２２２．０．０/２４は１１１．２２２．０．０/１６の枝のエントリにあたる。ここで、１１１．２２２．０．０/１６を破棄する場合、１１１．２２２．０．０/２４は破棄せず残す。

なお、無効化型ではなく、更新型の分散共有ルーティングテーブル２０２の場合、図９の状態８０７において、当該ローカルルーティングテーブル２０１の当該ＩＰアドレス条件を新しい条件に更新して、処理を終了する。また、前記更新にあたり、更新情報は前回登録分と新規登録分の差分だけを転送すればよい。更新型は無効化型に比べて制御が複雑であるため論理実装が困難であるが、ルーティングテーブルを制御する情報の通信量を削減できるメリットを持つ。

次に、ラインカード１００の経路検索制御部１０５が、経路検索をする場合の動作について、図１０に示すフローチャートを利用して説明する。経路検索制御部１０５は、受信パケットから抽出された宛先ＩＰアドレスを検索キーとして利用し、まず、ローカルルーティングテーブル２０１のルートノード５００を検索する（図１０の９０１→９０２）。
検索キーの上位１６ビットに一致するＩＰアドレス条件がローカルルーティングテーブル２０１のルートノード５００に存在する場合（当該エントリのローカルルーティングテーブル登録済みビット５０５がセットされている）、当該エントリのポインタ５０６により、次レベル以降のノードの検索を末端ノードに到達するまで繰り返す。

この例では、レベル１ノード５１０をルートノード５００のエントリポインタ５０６により選択し、検索キーの次の８ビットで当該レベル１ノード５１０内のエントリを選択し、そのエントリ内のポインタ５１４でレベル２ノード５２０を選択し、検索キーの最後の８ビットで当該レベル２ノード５２０内のエントリを選択する。以上の操作により、結果となる情報（次ホップＩＰアドレスと出力回線番号）を獲得する（図１０の９０３→９０７→９０８→９０７→９０８→９０９）。

また、検索キーの上位１６ビットに一致するＩＰアドレス条件がローカルルーティングテーブル２０１のルートノード５００に存在しない場合、情報元ラインカード番号５０４を参照して、対応する分散共有ルーティングテーブル２０２へＩＰアドレス条件の情報を要求する（図１０の９０３→９０４）。

対応するラインカード１００の分散共有ルーティングテーブル２０２は、対応するエントリ情報をルートノード６００、レベル１ノード６１０、レベル２ノード６２０から読み出し、そのコピーをまとめて要求元ラインカード１００へ送信する。また、同時に当該エントリの情報が、特定のラインカードにより共有されたことを分散共有ルーティングテーブル２０２のルートノードエントリ６０１の共有ラインカード情報６０４へ記録する（図１０の９０５）。

要求元ラインカードのローカルルーティングテーブル２０１は、送信されてくる前記エントリ情報を対応するルートノード５００、レベル１ノード５１０、レベル２ノード５２０へ記録し、再度ローカルルーティングテーブルのルートノード５００を検索する（図１０の９０６）。この検索では、既にローカルルーティングテーブル５００に目的の結果が登録されているため、先に示した図１０の９０３→９０７のフローを辿り、検索結果を得ることができる。

なお、ローカルルーティングテーブル２０１のレベル１ノード５１０およびレベル２ノード５２０のノードが不足する自体が発生する可能性がある。ノードエントリ不足が生じた場合、無作為（ランダム）または、ＦＩＦＯ（Ｆｉｒｓｔ Ｉｎ Ｆｉｒｓｔ Ｏｕｔ）、ＬＲＵ（Ｌｅａｓｔ Ｒｅｃｅｎｔｌｙ Ｕｓｅｄ）などのアルゴリズムに従って、利用中のノードエントリを解放して新規に利用する。
解放したエントリは、分散共有ルーティングテーブル２０２からみて共有状態ではなくなるため、対応する分散共有ルーティングテーブル２０２のルートノード６００の当該エントリの共有ラインカード情報６０４の内容を更新する。

以上、詳細な実施の形態について例を示して説明した。本実施例で示した分散共有ルーティングテーブル２０２をパケット転送装置に適用することで、パケット転送装置全体に必要なルーティングテーブル用メモリ量を削減することが可能となる。また、見方を変えると、従来の方法に比較して、パケット転送装置全体でラインカード数に比例しただけ多くの転送情報を登録可能となる。

更に、頻繁に利用する転送情報は、各ラインカードが専用のローカルルーティングテーブル２０１を利用して高速に検索が可能である。ローカルルーティングテーブル２０１には、ＴＣＡＭのような高速でロンゲスト・プレフィックス・マッチには適しているが、消費電力が大きく、登録エントリ数も少ないメモリを利用しなくても、本実施例に示したようにＤＲＡＭ、もしくはＳＲＡＭを各ノードに利用し、各ノードをパイプライン方式で１サイクルに１ノードずつ順次アクセスする方式を用いることに高速化が可能である。

また、分散共有ルーティングテーブル２０２からローカルルーティングテーブル２０１へは宛先アドレスに関連すると判断した全ての転送情報をコピーするため、宛先アドレスに完全に対応する唯一つの転送情報だけを分散共有ルーティングテーブル２０２からコピーする方式と比較して、分散共有ルーティングテーブル２０２を検索する頻度が減少するため、分散共有ルーティングテーブル２０２を複数のラインカード１００が検索することにより発生するメモリアクセスボトルネックの解消も可能になる。

本実施例中に用いた数値は、あくまで参考例であり、ｍ−Ｔｒｉｅのノードの数、検索キーとなるＩＰアドレスの分割位置、エントリ数など、他の数値を用いて様々な構成を同様に実施可能である。例えば、ロンゲスト・プレフィックス・マッチを利用しない、ＭＡＣアドレスなどの検索にも応用可能である。ＭＡＣアドレス用のルーティングテーブルの場合、プレフィックス長の概念が存在しないため、ルーティングテーブルのプレフィックス長用のフィールドは不要であり、また、ローカルルーティングテーブル２０１の上位から下位までの各ノードのエントリは、必ず１エントリずつ利用される。
また、本実施例同様、ロンゲスト・プレフィックス・マッチを利用するＩＰｖ６用のルーティングテーブルとしても同様の考え方により実施可能である。

実施例１では、完全ルーティングテーブル３０１を制御ラインカード３００が持つ形式を説明したが、完全ルーティングテーブル３０１を持たないパケット転送装置であってもよい。この場合、各ラインカード１００の分散共有ルーティングテーブル２０２とその制御ＣＰＵ１１０が、それぞれが担当するアドレス検索条件領域を独自に管理する。

この場合、ＯＳＰＦ（Ｏｐｅｎ Ｓｈｏｒｔｅｓｔ Ｐａｔｈ Ｆｉｒｓｔ）やＲＩＰ（Ｒｏｕｔｉｎｇ Ｉｎｆｏｒｍａｔｉｏｎ Ｐｒｏｔｏｃｏｌ）やＢＧＰなどのルーティングプロトコルを各ラインカード１００の制御ＣＰＵ１１０上で動作させ、各ＣＰＵは自分が管理する分散されたアドレスについてのみルーティングテーブルの管理を行う。他のパケット転送装置から見た場合、ルーティングプロトコルは単一のＣＰＵにより動作しているように観測されるが、当該パケット転送装置内部では、複数の制御ＣＰＵ１１０が協調動作することにより分散共有ルーティングテーブル２０２を管理する。

ローカルルーティングテーブル２０１の登録、アクセス方法や更新方法、分散共有ルーティングテーブル２０２のアクセス方法など、完全ルーティングテーブル３０１がないことを除いては実施例１と同様に扱える。
この実施例２では、制御カード３００を用いずパケット転送装置を構成することで、パケット転送装置の搭載資源を減らすことができる。

以上の実施例では、ロンゲスト・プレフィックス・マッチに対応可能なローカルルーティングテーブルの構成と分散共有ルーティングテーブルの構成を示した。ネットワークの端末間では、データを複数個のパケットにして送受信を行うため、短時間に同一のＩＰアドレス情報を持つパケットが大量に出現する時間ローカリティが強く存在する。よって、これまでの分散共有ルーティングテーブルの実施例において、ローカルルーティングテーブルを構成するメモリよりも高速なメモリで構成したルーティグテーブルキャッシュを組み合わせることで、より高速なルーティングテーブルアクセスを実現する実施例が考えられる。

具体的には、図１のラインカード１００において、経路検索制御部１０５はローカルルーティングテーブル２０１と分散共有ルーティングテーブル２０２とは独立したルーティングテーブルキャッシュメモリを具備し、前記ルーティングテーブルキャッシュはローカルルーティングテーブル２０１の一部の情報を検索キーとして利用されたＩＰアドレスに完全一致する形でエントリとして保持する。

例えば、分散共有ルーティングテーブル２０２が１１１．２２２．３．４/２４というＩＰアドレス条件を保持する場合に、１１１．２２２．３．１から、末尾のＩＰアドレスを一ずつ１００まで増加させたと１１１．２２２．３．１００までのＩＰアドレスキーによる検索が、１０回連続で実施された場合の動作例を説明する。

前記の場合、ローカルルーティングテーブル２０１は一回の一連の登録操作により１１１．２２２．３．４/２４に対応するＩＰアドレス条件を分散共有ルーティングテーブル２０２からコピーするため、最初の１１１．２２２．３．１による検索は時間がかかるものの、以降の１１１．２２２．３．１００までは既にローカルルーティングテーブル２０１に登録されているため、検索には最初の１１１．２２２．３．１ほどの時間はかからない。以降の９回の１１１．２２２．３．１から１１１．２２２．３．１００までの連続検索は、ローカルルーティングテーブル２０１のみで実施可能である。

次に、ルーティングテーブルキャッシュは最初の１１１．２２２．３．１から１１１．２２２．３．１００までの検索はすべてキャッシュミスを起こし、毎回、ローカルルーティングテーブル２０１から異なるルーティングテーブルキャッシュエントリへ、対応する結果となる情報（次ホップＩＰアドレスと出力回線番号）をコピーする必要がある。以降の９回の１１１．２２２．３．１から１１１．２２２．３．１００までの連続検索は、ルーティングテーブルキャッシュのみで実施可能であり、高速なルーティングテーブルキャッシュメモリの恩恵により検索時間の短縮が期待できる。

なお、ルーティングテーブルキャッシュを用いる場合、ローカルルーティングテーブル２０１のあるエントリが破棄または更新された場合、対応するルーティングテーブルキャッシュエントリも同様に破棄、または更新を実施する。

本実施例は、ルーティングテーブルキャッシュ用に別途メモリと制御機構が必要であるため、ハードウェア物量の増加を許容しても高速なルーティングテーブル検索を実施したい場合に適する手段である。

以上のように、本発明のルーティングテーブル分散管理方式は、二種類のルーティングテーブルを併用することにより、ルーティングテーブルに登録可能なエントリ数を増加させつつ、高速なルーティングテーブル検索を実現できる。よって、ルータやＬ３スイッチに代表される高速なパケット転送装置への適用が可能である。

本発明のパケット転送装置の一実施形態を示すブロック図。 ６エントリを持つルーティングテーブルの例を示す説明図。 従来のパケット転送装置の一実施形態によるブロック図。 第一、第二、第三のルーティングテーブルの包含関係の一例を示す説明図。 プレフィックス長の分布の様子。 ローカルルーティングテーブルの構成例とエントリ内容の一実施形態を示す説明図。 分散共有ルーティングテーブルの構成例とエントリ内容の一実施形態を示す説明図。 ローカル、分散共有ルーティングテーブルの物理的な構成例を示す説明図。 無効化型分散共有ルーティングテーブルの更新動作例を示すフローチャート。 ルーティングテーブル検索動作例を示すフローチャート。

符号の説明

１００：パケット転送装置のラインカード
３００：パケット転送装置の制御カード
４００：パケット転送装置のスイッチファブリック
１０２：ネットワークインタフェース
１０３：パケット処理部
１０４：スイッチファブリックインタフェース
１０５：経路検索制御部
１１０：制御ＣＰＵ
２０１：ローカルルーティングテーブル（第一のルーティングテーブル）
２０２：分散共有ルーティングテーブル（第二のルーティングテーブル）
３０１：完全ルーティングテーブル（第三のルーティングテーブル）
２１０：完全ルーティングテーブル。

Claims (12)

1. 複数のラインカードと制御カードとスイッチファブリック部とを備えたパケット転送装置であって、
   前記複数のラインカードはそれぞれ、
   装置外部のネットワークからパケットを入力する一つ以上の入力回線と、
   装置外部のネットワークへパケットを出力する一つ以上の出力回線と、
   装置内部のネットワークとパケットを送受信する内部回線と、
   宛先アドレスに対応する転送情報を複数記録するための第一のルーティングテーブルと、
   前記宛先アドレスに対応する転送情報を複数記録するための第二のルーティングテーブルと、
   前記入力回線より受信したパケットの持つ宛先アドレスを検索キーとして前記第一もしくは第二のルーティングテーブルから前記宛先アドレスに対応する転送情報を検索するための経路検索部と、
   前期経路検索部に検索要求を出し、前期検索の結果となる前記転送情報を受信し、パケットに必要な処理を実施したのち前記内部回線または前記出力回線へ転送するパケット処理部と、
   制御ＣＰＵと、
   を備え、
   前記制御カードは、
   前記宛先アドレスに対応する転送情報を複数記録する第三のルーティングテーブルと、
   前記第三のルーティングテーブルを管理するための機能を持つ制御ＣＰＵと、
   を備え、
   前記スイッチファブリック部は、
   装置内において、パケットを指定された前記出力回線のある前記パケット処理部へ転送し、
   さらに、
   前記第三のルーティングテーブルは、前記パケット転送装置内の全ての転送情報を記録し、
   前記第二のルーティングテーブルは、前記第三のルーティングテーブルの転送情報を、他の前記第二のルーティングテーブル間で重複がないように分散して記録し、
   前記第一のルーティングテーブルは、前記第二のルーティングテーブルの転送情報のうち転送に利用した宛先および前記宛先と同じグループに属すると判断した転送情報のみを、前記転送情報を保持する前記第二のルーティングテーブルから読み出して記録することを
   特徴とするパケット転送装置。
2. 宛先アドレスに対応する転送情報を複数記録するための複数の第一のルーティングテーブルと、
   前記宛先アドレスに対応する転送情報を複数記録するための複数の第二のルーティングテーブルと、
   複数の前記第二のルーティングテーブルに記録される転送情報を複数記録するための第三のルーティングテーブルと、を有し、
   前記複数の第二のルーティングテーブルはそれぞれ、該パケット転送装置内のルーティングテーブルの転送情報を、他の前記第二のルーティングテーブル間で重複がないように分散して記録し、
   前記第一のルーティングテーブルは、前記第二のルーティングテーブルの転送情報のうち転送に利用した宛先および前記宛先と同じグループに属すると判断した転送情報のみを、前記転送情報を保持する前記第二のルーティングテーブルから読み出して記録し、
   さらに、
   前記第一のルーティングテーブルは、宛先アドレスに対応する転送情報が、前記第一、第二のいずれのルーティングテーブルに記録されているかの情報を保持し、
   前記第二のルーティングテーブルは、宛先アドレスに対応する転送情報がどの前記第一のルーティングテーブルに記録されているかの情報を保持することを特徴とするパケット転送装置。
3. 宛先アドレスに対応する転送情報を複数記録するための複数の第一のルーティングテーブルと、
   前記宛先アドレスに対応する転送情報を複数記録するための複数の第二のルーティングテーブルと、
   前記入力回線より受信したパケットの持つ宛先アドレスを検索キーとして利用し、前記第一もしくは第二のルーティングテーブルを検索するための経路検索部と、
   前記宛先アドレスに対応する転送情報を複数記録する第三のルーティングテーブルと、
   を持つパケット転送装置で、
   前記第三のルーティングテーブルは、前記パケット転送装置内の全ての転送情報を記録し、
   前記第二のルーティングテーブルは、前記第三のルーティングテーブルの転送情報を、他の前記第二のルーティングテーブル間で重複がないように分散して記録し、
   前記第一のルーティングテーブルは、前記第二のルーティングテーブルの転送情報のうち転送に利用した宛先および前記宛先と同じグループに属すると判断した転送情報のみを、前記転送情報を保持する前記第二のルーティングテーブルから読み出して記録することを特徴とするパケット転送装置であり、
   前記第一のルーティングテーブルと前記第二のルーティングテーブルをｍ−Ｔｒｉｅアルゴリズムを用いて構成し、
   前記第一のルーティングテーブルと前記第二のルーティングテーブルとしてＳＲＡＭもしくはＤＲＡＭを用いることを特徴とするパケット転送装置。
4. 請求項１乃至３のいずれか一つに記載のパケット転送装置において、
   前記第一のルーティングテーブルが記録する前記転送情報のグループとは、最長一致検索が可能となる全ての転送情報であることを特徴とするパケット転送装置。
5. 請求項１乃至３のいずれか一つに記載のパケット転送装置において、
   前記第一のルーティングテーブルと前記第二のルーティングテーブルは複数のエントリを保持する複数のノードで構成され、
   前記第一のルーティングテーブルの最上位のノードの各エントリは、
   前記エントリが装置内に登録されていることを示す情報と、
   前記エントリが第一のルーティングテーブルに登録されていることを示す情報と、
   宛先ＩＰアドレスのプレフィックス長を表す情報と、
   当該エントリが存在する第二のルーティングテーブルを持つラインカード番号を示す情報と、
   前記エントリの下位のノードを示すためのポインタを少なくとも備え、
   前記第二のルーティングテーブルの最上位のノードの各エントリは、
   前記エントリの有効を示す情報と、
   宛先ＩＰアドレスのプレフィックス長を表す情報と、
   当該エントリがコピーされた先の第一のルーティングテーブルを持つラインカード番号を示す情報と、
   前記エントリの下位のノードを示すためのポインタを備え、
   前記第一および第二のルーティングテーブルの最下位でない下位のノードの各エントリは、
   前記エントリの有効を示す情報と、
   宛先ＩＰアドレスのプレフィックス長を表す情報と、
   前記エントリの下位のノードを示すためのポインタを備え、
   前記第一および第二のルーティングテーブルの最下位のノードの各エントリは、
   前記エントリの有効を示す情報と、
   宛先ＩＰアドレスのプレフィックス長を表す情報と、
   転送情報、または該転送情報が格納されるメモリ上のエントリを示すためのポインタと、
   を備えることを特徴とするパケット転送装置。
6. 請求項１乃至３のいずれか一つに記載のパケット転送装置において、
   前記経路検索部は、最初に前記第一のルーティングテーブルを検索し、
   前記第一のルーティングテーブルに前記検索キーに対応する転送情報がある場合は、前記第一のルーティングテーブルから該転送情報を読出し、
   前記第一のルーティングテーブルに前記検索キーに対応する転送情報がない場合は、対応する前記第二のルーティングテーブルへ該転送情報を要求し、
   前記対応する第二のルーティングテーブルは、要求元である前記第一のルーティングテー
   ブルを備えるラインカード番号を記録した上で、当該転送情報と前記転送情報のグループをまとめて前記要求元である前記第一のラインカードへ送信し、
   前記要求元である前記第一のラインカードは、前記第一のルーティングテーブルの該当エントリを前記転送情報および前記転送情報のグループで更新し、当該転送情報が前記第一のルーティングテーブルにあることを記録し、当該転送情報を読み出すことを特徴とするパケット転送装置。
7. 請求項１または３に記載のパケット転送装置において、
   前記制御カードの前記制御ＣＰＵは、他のパケット転送装置と通信し、前記第三のルーティングテーブルの更新を行い、
   該当する前記転送情報のエントリを持つ前記ラインカードへ更新要求を出し、
   当該ラインカードは、前記更新要求により前記第二のルーティングテーブルの当該エントリを更新し、
   前記第二のルーティングテーブルの前記エントリが自カードを含む前記第一のルーティングテーブルに共有されていれば、必要な情報を該当する前記ラインカードに通達し、
   前記該当するラインカードは、前記第一のルーティングテーブルを前記情報により更新、または無効化することを特徴とするパケット転送装置。
8. 請求項１または３に記載のパケット転送装置において、
   前記第三のルーティングテーブルも前記第二のルーティングテーブル同様に前記各ラインカードで分散して保持し、
   前記各ラインカードの前記制御ＣＰＵが担当する前記第三のルーティングテーブル部分の更新を独立して実施することを特徴とするパケット転送装置。
9. 請求項１または３に記載のパケット転送装置において、
   前記第三のルーティングテーブルが存在せず、前記第二のルーティングテーブルが前記第三のルーティングテーブルの役割も果たすことを特徴とするパケット転送装置。
10. 請求項１乃至３のいずれか一つに記載のパケット転送装置において、
    前記第一のルーティングテーブルに前記転送情報がなく、前記第二のルーティングテーブルへ前記転送情報を要求する際、
    パケット転送に用いる前記スイッチファブリック部とは別の専用スイッチファブリックを介して、他の前記ラインカードの前記第二のルーティングテーブルと通信することを特徴とするパケット転送装置。
11. 請求項１乃至３のいずれか一つに記載のパケット転送装置において、
    前記第二のルーティングテーブルが更新されるとき、前記更新の差分情報のみを共有状態にある前記第一のルーティングテーブルへ更新することを特徴とするパケット転送装置。
12. 請求項１乃至３のいずれか一つに記載のパケット転送装置において、
    前記第一のルーティングテーブルと前記経路検索部との間に、頻繁に利用される前記エントリを完全一致する状態で記録するルーティングテーブルキャッシュを具備することを特徴とするパケット転送装置。

Images