(57)【特許請求の範囲】
【請求項１】
受信先アドレスをあらわすデステイネーションＩＰアドレスを含むネットワークパケットが入力され、入力されたネットワークパケットを、登録された複数のエントリのうちの、入力されたネットワークパケット中のデスティネーションＩＰアドレスに適合したエントリのネットワークに送り出すルータにおける、複数のエントリのアドレスが登録され、これら登録された複数のエントリの中から、入力されたネットワークパケット中のデスティネーションＩＰアドレスに最上位ビット側から最長ビット長一致するアドレスをもつエントリを検索する最長一致検索装置において、
複数のメモリ領域それぞれに所定のビット長のデータを格納しておき、キーデータが入力され、マスクされたビットを除く残りのビットについて該キーデータと一致するデータが格納されたメモリ領域を検索する連想メモリであって、前記複数のメモリ領域それぞれに、各エントリのアドレスをあらわすアドレスデータと各エントリのプレフィックス長をあらわすプレフィックスデータとのペアが格納されてなる連想メモリと、
検索用のプレフィックスデータを順次に作成するプレフィックスデータ作成回路と、
入力されたネットワークパケット中のデスティネーションＩＰアドレスと前記プレフィックスデータ作成回路により作成されたプレフィックスデータとに基づいて、検索用のキーデータを作成するキーデータ作成回路とを備え、
前記連想メモリが、前記キーデータ作成回路により作成されたキーデータに基づいて、最上位ビット側から最長ビット長一致するアドレスデータであって、かつ、最上位ビット側から最長ビット長一致するアドレスデータが複数格納されていた場合に、これら複数のアドレスデータのうち、最長のプレフィックス長をあらわすプレフィックスデータとペアのアドレスデータが格納されたメモリ領域を検索するものであることを特徴とする最長一致検索装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、インターネット通信回線網内に配置されその通信回線網内を流れるネットワークパケットの伝達を仲介するルータに搭載される、登録されたアドレスと、入力されたネットワークパケット中のアドレスとの最長一致検索を行なう最長一致検索装置に関する。
【０００２】
【従来の技術】
現在インターネットと呼ばれる通信が広く普及してきており、それに伴って発信元や受信先を特定するアドレスの枯渇が問題となり、現在、インターネットプロトコルでは、アドレスの枯渇問題への対策から、３２ビットからなるＩＰアドレスを構成するネットワークアドレスとホストアドレスとの境目を自由に設定できる手法が採られてきている。ここで、ＩＰアドレスのうちのネットワークアドレスの長さはプレフィックス長と呼ばれる。
【０００３】
このような手法が採用されたインタネットプロトコルのＩＰアドレスは、最長一致検索と呼ばれる方法でそのアドレスの検索が行なわれる。
図９は、最長一致検索の説明図である。
図９（Ａ）は、ルータが伝達を仲介しようとしているネットワークパケット中のデスティネーションＩＰアドレスからなるキーデータであり、ここでは、１８６．２４１．０．６であるとする。
【０００４】
ルータ内には、図９（Ｂ）に示す２つのエントリ、すなわちエントリ１：１８６．２４０．０／１２、エントリ２：１８６．１９２．０．０／１０が登録されているものとする。ここで／１２，／１０は各エントリのプレフィックス長を示すものであり、例えば／１２は、上位１２ビットがネットワークアドレスであることを示している。
【０００５】
ここで、図９（Ａ）に示すキーデータが検索対象として入力された（すなわち、図９（Ａ）に示すデスティネーションＩＰアドレスをもったネットワークパケットが入力された）とすると、両エントリ共に、各エントリがもつプレフィックス長までキーデータと一致するが、この場合、上位ビット側から最も長いビット長部分が一致しているエントリ１のネットワークに対して経路が開かれることになる。このように、上位ビット側から最も長いビット長部分までキーデータと一致しているエントリを検索することを最長一致検索と称する。
【０００６】
上記の最長一致検索を、連想メモリを使用して実現することを考える。ここで、連想メモリとは、複数のメモリ領域を備え、それら複数のメモリ領域それぞれに所定のビット長のデータを格納しておき、キーデータが入力され、マスクされたビットを除く残りのビットについて、入力されたキーデータと一致するデータが格納されたメモリ領域を検索する機能を有する一種のメモリである。連想メモリ自体は、既に広く知られた技術であり、ここでは連想メモリ自体についての詳細説明は省略する。
【０００７】
図１０は、連想メモリを用いた最長一致検索方法の説明図である。
ＩＰアドレスは３２ビットであるため、連想メモリによって検索を行なう場合に、まず、図１０（Ａ）に示すように、３２ビットをマスクなしで検索する。つまり、３２ビット全てについて一致しているエントリが存在するか否かを検索する。次に、図１０（Ｂ）に示すように、最下位ビット１ビットのみにマスクをかけて３１ビットの検索を行なう。次には、最下位ビット側から２ビットにマスクをかけて３０ビットの検索を行ない、以後同様にしてマスクを順次１ビットずつ増加させながら検索を行なう。
【０００８】
このように、順次マスク長を増やしながら３２回の検索を行なえば、最長一致しているエントリを得ることができる。上記の順序に従えば、検索の結果ヒットが最初に生じた（マスクがかけられないビット部分について一致が検出された）エントリが最長一致したエントリとなる。
【０００９】
【発明が解決しようとする課題】
図１１は、連想メモリを用い上記のようにして行なう最長一致検索の問題点の説明図である。
上記のようにして検索を行なっても、この図１１を参照して説明するような場合は、最長一致を正確に求めていることにはならない。すなわち、２つのエントリ１，２が図１１（Ｂ），（Ｃ）のように定義されていたとき、図１１（Ａ）に示すキーデータを用い下位３ビットをマスクして検索を行なうと、エントリ１とエントリ２では、プレフィックス長は、エントリ１の場合はプレフィックス長＝１２，エントリ２の場合はプレフィックス長＝１０のように異なるが、検索の結果としてはエントリ１とエントリ２の双方で一致が検出されることになる。インターネットプロトコルのルールによるとプレフィックス長の長いエントリ、すなわちここではエントリ１が選ばれるべきであるが、このような場合、エントリ１が選ばれるという保証がないことになる。
【００１０】
本発明は、上記事情に鑑み、連想メモリを用い、正しいエントリを検出することのできる最長一致検索装置を提供することを目的とする。
【００１１】
【課題を解決するための手段】
上記目的を達成する本発明の最長一致検索装置は、受信先アドレスをあらわすデステイネーションＩＰアドレスを含むネットワークパケットが入力され、入力されたネットワークパケットを、登録された複数のエントリのうちの、入力されたネットワークパケット中のデスティネーションＩＰアドレスに適合したエントリのネットワークに送り出すルータにおける、複数のエントリのアドレスが登録され、これら登録された複数のエントリの中から、入力されたネットワークパケット中のデスティネーションＩＰアドレスに最上位ビット側から最長ビット長一致するアドレスをもつエントリを検索する最長一致検索装置において、
複数のメモリ領域それぞれに所定のビット長のデータを格納しておき、キーデータが入力され、マスクされたビットを除く残りのビットについてキーデータと一致するデータが格納されたメモリ領域を検索する連想メモリであって、上記複数のメモリ領域それぞれに、各エントリのアドレスをあらわすアドレスデータと各エントリのプレフィックス長をあらわすプレフィックスデータとのペアが格納されてなる連想メモリと、
検索用のプレフィックスデータを順次に作成するプレフィックスデータ作成回路と、
入力されたネットワークパケット中のデスティネーションＩＰアドレスとプレフィックスデータ作成回路により作成されたプレフィックスデータとに基づいて、検索用のキーデータを作成するキーデータ作成回路とを備え、
上記連想メモリが、キーデータ作成回路により作成されたキーデータに基づいて、最上位ビット側から最長ビット長一致するアドレスデータであって、かつ、最上位ビット側から最長ビット長一致するアドレスデータが複数格納されていた場合に、これら複数のアドレスデータのうち、最長のプレフィックス長をあらわすプレフィックスデータとペアのアドレスデータが格納されたメモリ領域を検索するものであることを特徴とする。
【００１２】
図１は、本発明の原理説明図である。
連想メモリには、図１（Ｂ）に示すエントリ１と図１（Ｃ）に示すエントリ２が登録されているものとする。すなわち、各エントリに対応して、ここに示す例では、３２ビットのアドレスデータと、５ビットのプレフィックスデータが登録されている。
【００１３】
キーデータも、図１（Ａ）に示すように、３２ビットのアドレスデータと５ビットのプレフィックスデータとの合計３７ビットであり、図１に示す例では、図１（Ａ）に示すキーデータを用いて検索を行なうと、アドレスデータとしてはエントリ１とエントリ２の双方で一致するが、プレフィックスデータは、キーデータが１Ｃ（ｈｅｘ）（プレフィックス＝２９を意味する）であるのに対し、エントリ１のプレフィックス長は、キーデータのプレフィックス長と同じ１Ｃ（ｈｅｘ）、エントリ２のプレフィックス長は、キーデータのプレフィックス長とは異なり１Ａ（ｈｅｘ）（プレフィックス長＝２７を意味する）であり、したがってここに示す例では、エントリ１のみが検出される。
【００１４】
このように本発明の最長一致検索装置は、連想メモリに、各エントリのアドレスをあらわすアドレスデータと各エントリのプレフィックス長（ネットワークアドレスの長さ）をあらわすプレフィックスデータとをペアを格納しておき、それらのペアで検索を行なうようにしたため、エントリのアドレスのみでは同時に複数のエントリで一致が検出されるような状況であっても、プレフィックス長の長いエントリのみで一致が検出されることになり、図１１を参照して説明したような問題が解消され、正しいエントリが検出される。
【００１５】
【発明の実施の形態】
以下、本発明の実施形態における２種類の最長一致検索法について説明し、次いで本発明の最長一致検索装置の実施形態について説明する。
図２は、２種類の最長一致検索法のうちの第１の最長一致検索法の説明図である。
【００１６】
この図２には、検索回数ごとのキーデータのビット配列が示されでおり、各検索において３２ビットからなるアドレスデータは同一、５ビットからなるプレフィックスデータは検索１回目は１Ｆ（ｈｅｘ）（プレフィックス長＝３２を意味する）から始まり、１ずつデクリメントされて検索３２回目では０（ｈｅｘ）（プレフィックス長＝１を意味する）となる。また、検索１回目はマスクなし、検索２回目は３２ビットのアドレスデータの最下位１ビットをマスクする、検索３回目は３２ビットのアドレスデータのうちの下位２ビットをマスクする、……、検索３２回目では３２ビットのアドレスデータのうちの下位３１ビットをマスクする（最上位１ビットのみ有効とする）、のようにマスクを１ビットずつ順次増やして検索する。尚プレフィックスデータに関しては上記のように検索毎に値が書き換えられ、常に有効データとして検索に参加する。
【００１７】
この図２に示す検索順序に従って順次に検索を行ない、最初にヒットのあったエントリが、プレフィックス長も含めて正しいエントリとして検出される。
尚、この図２に示す最長一致検索法を採用すると、検索対象を指定するためのマスクが３２種類必要になるようにも考えられるが、キーデータの検索対象部分は順次１ビットずつ狭められるため、マスクレジスタとしてシフトレジスタを１つ用意すればよい。
【００１８】
図３は、２種類の最長一致検索法のうちの第２の最長一致検索法の説明図である。
この図３における検索１回目のキーデータを構成するアドレスデータ（３２ビット）およびプレフィックスデータ（５ビット）は、いずれも、図２に示す検索法における検索１回目のものと同一である。
【００１９】
検索２回目〜検索３２回目について、プレフィックスデータが順次デクリメントされる点も、図２に示す検索法と同一である。
ただし、３２ビットのアドレスデータに関し、検索２回目は最下位１ビットを‘０’に置き換えたデータで検索を行ない、検索３回目は下位２ビットを‘０’に置き換えたデータで検索を行ない、……、検索３２回目では、下位３１ビットを‘０’に置き換えたデータで検索を行なう。すなわち、図２を参照して説明した検索法におけるマスクをかけるビットに、マスクをかける代わりに‘０’を代入する。
【００２０】
一方、この図３に示すキーデータを用いた検索が行なわれる連想メモリ側には、各エントリに対応して、アドレスデータとしては、ネットワークアドレスのみ有効なデータを登録し、ホストアドレスの部分は全て‘０’を登録しておく。各エントリに対応して、このようなアドレスデータと、プレフィックスデータとのペアを連想メモリに登録しておく。
【００２１】
こうしておいて、キーデータを図３に示すように順次変更しながら順次検索を行なう。
この検索法によっても、図２を参照して説明した検索法と同様に、プレフィックス長を含め正しいエントリを検出することができる。
尚、図３を参照して説明した検索法では、キーデータ側はマスクをかける代わりに‘０’を代入し、連想メモリ側はホストアドレスの部分は全て‘０’を登録しておく旨説明したが、例えばキーデータ側はマスクの代わりに‘１’を代入し、連想メモリ側のホストアドレスの部分に全て‘１’を登録しておいてもよく、検索の障害とならないように双方が同一のビット配列であればよい。
【００２２】
図４は、本発明の最長一致検索装置の一実施形態を示すブロック図、図５は、そのタイミングチャートである。ここでは、この図４に示す最長一致検索装置において、図２を参照して説明した検索法による検索が行なわれるものとして説明する。
この図４に示す最長一致検索装置１０にはＣＡＭメモリブロック１１が備えられており、このＣＡＭメモリブロック１１には、メンテナンスポートを経由して入力されるデータに応じて、ＣＡＭデータ入出力制御回路１２により各エントリに対応したデータが登録され、必要に応じて追加、変更される。
【００２３】
図６は、ＣＡＭメモリブロック１１内に登録される１つのエントリに対応するデータ構成を示す図である。
ここには、３２ビットのＩＰアドレスデータと、５ビットのプレフィックスデータと、その他のデータの各領域が示されている。その他のデータの中には、詳細説明は省略するが、例えばそのエントリの登録時刻をあらわすタイムスタンプなどがある。
【００２４】
図４に示す最長一致検索装置には、最長一致検索制御回路１３が備えられており、この最長一致検索制御回路１３にはクロックが入力され、この最長一致検索制御回路１３は、入力されたクロックに同期して、ＣＡＭメモリブロック１１に登録された各エントリの中から所望のエントリを検索するための各部の制御を行なう。
【００２５】
また、図４に示す最長一致検索装置１０には、キーデータ生成回路１４およびプレフィックスデータ生成回路１５が備えられている。キーデータ生成回路１４には、入力ポートを経由して検索用キーデータの基になる入力データ（デスティネーションＩＰアドレス）が入力され、さらに検索の開始を指示する検索開始信号が入力される（図５参照）。すると、プレフィックスデータ生成回路１５では、前述したように順次デクリメントされるプレフィックスデータが生成されてキーデータ生成回路１４に入力され、キーデータ生成回路１４では、ＩＰアドレスとプレフィックスデータとからなるキーデータが生成されてＣＡＭメモリブロック１１に入力される。
【００２６】
図７は、キーデータ生成回路１４で生成されるキーデータの構成を示した図である。
キーデータ生成回路１４では、３２ビットのＩＰアドレスデータと５ビットのプレフィックスデータと、さらにその他のデータとからなるキーデータが生成される。ここではその他のデータは、ＣＡＭメモリブロックに登録されたデータ（図６参照）とデータ長を合わせるためだけの役割りを担っており、どのようなデータであってもかまわない。
【００２７】
図８は、検索１回目〜検索３２回目の各検索に用いられるキーデータの一例を示した図である。
各回の検索とも、ＩＰアドレスデータは同一であり、プレフィックスデータは順次１ずつデクリメントされている。
マスク生成回路１６では、キーデータをマスクするためのマスクデータが生成されてＣＡＭメモリブロック１１に入力される。検索１回目では、その他のデータの部分についてのみマスクされ、検索２回目では、その他のデータの部分と、３２ビットのＩＰアドレスデータのうちの最下位１ビットについてマスクされ、……、検索３２回目では、その他のデータの部分と、３２ビットのＩＰアドレスデータのうちの下位３１ビットについてマスクされるように、順次異なるマスクデータが生成される。
【００２８】
ＣＡＭメモリブロック１１内では、キーデータ生成回路１４で生成されてＣＡＭメモリブロック１１に入力されるキーデータのうち、マスク生成回路１６で生成されたマスクデータでマスクされていない有効部分について順次に３２回の検索が行なわれ、最初にヒットがあった時点のＣＡＭメモリブロック１１のアドレスとそのアドレスに格納された内容からなる最長一致検索結果がＣＡＭメモリブロック１１から出力されて最長一致検索結果出力回路１７に一旦格納され、３２回の検索が終了した時点で最長一致検索制御回路１３から最長一致検索結果出力回路１７に検索終了信号が送られ、最長一致検索結果出力回路１７は、その検索終了信号を受けて、その最長一致検索結果を出力ポートから出力する。
【００２９】
尚、上記の、図４に示す最長一致検索装置１０の説明は、図２を参照して説明した検索法を適用するものとしたときの説明であるが、この図４に示した最長一致検索装置１０では、図３を参照して説明した検索法を適用した検索を行なうこともできる。すなわち、このときは、ＣＡＭメモリブロック１１には、各エントリのＩＰアドレスのうちのネットワークアドレスのみ有効なデータを格納し、ホストアドレスの部分には全て‘０’を書き込んでおき、一方、キーデータ生成回路１４では、検索２回目は３２ビットのアドレスデータの最下位１ビットを‘０’とし、検索３回目は３２ビットのアドレスデータの下位２ビットを‘０’とし、……、検索３２回目は３２ビットのアドレスデータの下位３１ビットを‘０’としたデータを生成し、ＣＡＭメモリブロック１１では、そのように生成されたキーデータを用いた検索を行なう。このとき、マスク生成回路１６で生成されるマスクデータは、３２回の検索の全てにおいて、その他のデータの部分のみマスクをかけるマスクデータを生成する。このような検索を行なうことにより、図４に示した最長一致検索装置１０を用い、図３を参照して説明した検索法がそのまま実現される。
【００３０】
【発明の効果】
以上説明したように、本発明によれば、正しい最長一致検索が行なわれる。
【図面の簡単な説明】
【図１】本発明の原理説明図である。
【図２】２種類の最長一致検索法のうちの第１の最長一致検索法の説明図である。
【図３】２種類の最長一致検索法のうちの第２の最長一致検索法の説明図である。
【図４】本発明の最長一致検索装置の一実施形態を示すブロック図である。
【図５】図５は、そのタイミングチャートである。
【図６】ＣＡＭメモリブロック１１内に登録される１つのエントリに対応するデータ構成を示す図である。
【図７】キーデータ生成回路１５で作成されるキーデータの構成を示した図である。
【図８】検索１回目〜検索３２回目の各検索に用いられるキーデータの一例を示した図である。
【図９】最長一致検索の説明図である。
【図１０】連想メモリを用いた最長一致検索方法の説明図である。
【図１１】連想メモリを用いた最長一致検索の問題点の説明図である。
【符号の説明】
１０    最長一致検索装置
１１    ＣＡＭメモリブロック
１２    ＣＡＭデータ入出力制御回路
１３    最長一致検索制御回路
１４    キーデータ生成回路
１５    プレフィックスデータ生成回路
１６    マスク生成回路
１７    最長一致検索結果出力回路
【図１】
0003845512.tif 000002
【図２】
0003845512.tif 000003
【図３】
0003845512.tif 000004
【図４】
0003845512.tif 000005
【図５】
0003845512.tif 000006
【図６】
0003845512.tif 000007
【図７】
0003845512.tif 000008
【図８】
0003845512.tif 000009
【図９】
0003845512.tif 000010
【図１０】
0003845512.tif 000011
【図１１】
0003845512.tif 000012