Pat
J-GLOBAL ID：200903067785814218
ルーティングテーブル検索装置および検索法
Inventor：
,
Applicant, Patent owner：
Agent (1)：
磯村 雅俊 (外1名)
Gazette classification：公開公報
Application number (International application number)：1999170479
Publication number (International publication number)：2000358064
Application date： Jun. 17, 1999
Publication date： Dec. 26, 2000
Summary：
【要約】【課題】ルーティングテーブル検索の回数とメモリ量を低減し、高速検索する。【解決手段】検索を2段に分けて行い、1段目処理部1でCAMを用いて1回目の検索を行い、2段目処理部2にツリーを配置して2回目の検索を行う。テーブルにエントリされている全てのPrefixをPrefix長で決められた範囲に分け、そのPrefixをその範囲中で最小のPrefix長に短縮したPrefixをCAMに格納する。1段目処理部1では入力IPアドレスとCAMに格納されたPrefixを比較し、一致したときそのPrefixに対応するツリー格納メモリ部3のアドレスを出力する。ツリーの途中にあるCAMの出力に該当するノードに移り、限定された範囲内で検索し、検索終了時にNextHop情報格納メモリ4の情報を最終的結果として出力する。
Claim (excerpt)：
IPパケットの宛先IPアドレスから、ルーティングテーブル内のPrefixの中で最長一致のPrefixを検索し、Next Hop情報あるいはNext Hop情報を持つ他テーブルへのIndex情報を求めるルーティングテーブル検索装置において、検索すべき宛先IPアドレスをContent Addressable Memory(CAM)に入力すると、該CAMに格納されているPrefixと前記宛先IPアドレスの上位Prefix長ビット分とを比較し、一致したPrefixのうち最長のPrefix長を持つPrefixを答えとして、2段目処理部に移る1段目処理部と、ツリーが配置され、該ツリーの途中にあり、前記1段目処理部で一致したCAMの出力に該当するノードに検索処理が移ると、該ツリーの限定された範囲内で検索を行い、検索が終了した時点でNext Hop情報あるいはNext Hop情報を持った他テーブルへのIndex情報を最終結果として出力する2段目処理部とを具備したことを特徴とするルーティングテーブル検索装置。
F-Term (5)：
5K030GA01
, 5K030GA06
, 5K030KA02
, 5K030KA05
, 5K030LB05
Cited by applicant (3)
-
高速検索方法及び高速検索装置
Gazette classification：公開公報
Application number：特願平10-369960
Applicant：富士通株式会社
-
ネットワーク間接続装置
Gazette classification：公開公報
Application number：特願平7-314071
Applicant：株式会社東芝
-
情報記憶装置
Gazette classification：公開公報
Application number：特願平8-349131
Applicant：株式会社東芝
Cited by examiner (1)
-
高速検索方法及び高速検索装置
Gazette classification：公開公報
Application number：特願平10-369960
Applicant：富士通株式会社
Return to Previous Page
