(57)【要約】【課題】待ち行列や処理のブロッキングを発生させることなく、テーブル検索とも競合せずに、エントリ・テーブルに対してエントリの登録・削除・変更などを高速に行うことができるエントリ登録方法を提供する。【解決手段】それぞれハッシュ・テーブルを有するエントリ・テーブル、例えばアクセス制御リスト（ＡＣＬ）処理に際して参照されるテーブルを２面設け、一方の面においてエントリに応じたハッシュ・テーブルを構築する処理を行いながら、他方の面においてハッシュ・テーブルに対する検索処理を可能にし、ハッシュ・テーブルの構築処理に対象となる面と検索処理の対象となる面とを任意のタイミング（例えば周期的に）で入れ替える。【選択図】図２
2013179421.tif 000002
【特許請求の範囲】
【請求項１】
エントリ・テーブルに対する検索処理を可能にしつつ、前記エントリ・テーブルへのエントリの登録を行うエントリ登録方法において、
第１及び第２のエントリ・テーブルを使用し、
第１の期間において、テーブル操作指示に基づくエントリをそのハッシュ値に応じて格納する第１のハッシュ・テーブルを前記第１のエントリ・テーブル内に構築しつつ、前記第２のエントリ・テーブルに設けられて前記テーブル操作指示に基づくエントリをそのハッシュ値に応じて格納した第２のハッシュ・テーブルに対する検索処理を可能にし、
第２の期間において、前記第２のエントリ・テーブル内に前記第２のハッシュ・テーブルを構築しつつ、前記第１のハッシュ・テーブルに対する検索処理を可能にし、
前記第１の期間と前記第２の期間とを交互に繰り返すことを特徴とするエントリ登録方法。
【請求項２】
前記第１及び第２のエントリ・テーブルにそれぞれ第１及び第２の実データ・テーブルが設けられ、
前記第１の期間において、前記第２の実データ・テーブルに対して、前記エントリの操作を行い、前期第１の実データ・テーブルに登録されたエントリから前記第１のハッシュ・テーブルを構築し、
前記第２の期間において、前記第１の実データ・テーブルに対して前記エントリの操作を行い、前期第２の実データ・テーブルに登録されたエントリから前記第２のハッシュ・テーブルを構築し、
前記エントリの操作は、登録、削除及び変更の少なくとも１つを含んでいる、請求項１に記載のエントリ登録方法。
【請求項３】
前記第１の期間の開始直後に、前記第２の実データ・テーブルの内容をクリアして前記第１の実データ・テーブルの内容を前記第２の実データ・テーブルにコピーし、その後、前記第２の実データ・テーブルに対して前記エントリの操作を行い、
前記第２の期間の開始直後に、前記第１の実データ・テーブルの内容をクリアして前記第２の実データ・テーブルの内容を前記第１の実データ・テーブルにコピーし、その後、前記第１の実データ・テーブルに対して前記エントリの操作を行う、請求項２に記載のエントリ登録方法。
【請求項４】
前記第１及び第２のハッシュ・テーブルの構築に際し、複数のハッシュ関数を有する群の中から選択された最適のハッシュ関数を使用し、前記最適のハッシュ関数は当該ハッシュ・テーブルに対する検索処理においても使用される、請求項１乃至３のいずれか１項に記載のエントリ登録方法。
【請求項５】
前記第１及び第２のハッシュ・テーブルは、いずれも異なる複数のハッシュ関数に基づく複数の面を備え、
前記第１の期間において、前記テーブル操作指示に基づくエントリに対して前記複数のハッシュ関数をそれぞれ適用して得られたハッシュ値を前記第１のハッシュ・テーブルにおける対応する面に格納するとともに、前記第１のハッシュ・テーブルに対応する最適となるハッシュ関数を選定し、前記第２のハッシュ・テーブルに対する検索処理では、前記第２のハッシュ・テーブルに対応するものとして選定された最適なハッシュ関数と当該最適なハッシュ関数に対応する前記面を使用し、
前記第２の期間において、前記テーブル操作指示に基づくエントリに対して前記複数のハッシュ関数をそれぞれ適用して得られたハッシュ値を前記第２のハッシュ・テーブルにおける対応する面に格納するとともに、前記第２のハッシュ・テーブルに対応する最適となるハッシュ関数を選定し、前記第１のハッシュ・テーブルに対する検索処理では、前記第１のハッシュ・テーブルに対応するものとして選定された最適なハッシュ関数と当該最適なハッシュ関数に対応する前記面を使用する、請求項１に記載のエントリ登録方法。
【請求項６】
エントリ・テーブルへのエントリの登録を行いつつ前記エントリ・テーブルに対する検索処理を実行する処理装置であって、
第１のハッシュ・テーブルを備える第１のテーブル格納部と、
第２のハッシュ・テーブルを備える第２のテーブル格納部と、
テーブル操作指示に基づくエントリをそのハッシュ値に応じて第１及び第２のハッシュ・テーブルに格納することによって前記第１及び第２のハッシュ・テーブルを構築するハッシュ構築部と、
入力データから得られたハッシュ値に応じて前記第１及び第２のハッシュ・テーブルを検索し検索結果に応じて前記入力データに対する処理を実行する検索・処理部と、
第１の期間において前記ハッシュ構築部が前記第１のハッシュ・テーブルを構築しかつ前記検索・処理部が前記第２のハッシュ・テーブルを検索し、第２の期間において前記ハッシュ構築部が前記第２のハッシュ・テーブルを構築しかつ前記検索・処理部が前記第１のハッシュ・テーブルを検索し、前記第１の期間と前記第２の期間とが交互に繰り返されるように前記ハッシュ構築部と前記検索・処理部とを制御する制御部と、
を有する処理装置。
【請求項７】
前記第１及び第２のエントリ・テーブルに、前記テーブル操作指示に基づくエントリをそれぞれ格納する第１及び第２の実データ・テーブルが設けられ、
前記テーブル操作指示に基づいて前記第１及び第２の実データ・テーブル内のエントリを操作するテーブル操作部をさらに有し、
前記制御部は、前記第１の期間において前記テーブル操作部が前記第２の実データ・テーブル内のエントリを操作し、前記第２の期間内において前記テーブル操作部が前記第１の実データ・テーブル内のエントリを操作するように前記テーブル操作部を制御し、
前記ハッシュ構築部は、前記第２の実データ・テーブル内のエントリに前記ハッシュ関数を適用して前記第１のハッシュ・テーブルを構築し、前記第１の実データ・テーブル内のエントリに前記ハッシュ関数を適用して前記第２のハッシュ・テーブルを構築する、請求項６に記載の処理装置。
【請求項８】
前記ハッシュ構築部は、前記第１及び第２のハッシュ・テーブルの構築に際し、複数のハッシュ関数を有する群の中から選択された最適のハッシュ関数を使用し、前記最適のハッシュ関数は前記検索・処理部が当該ハッシュ・テーブルを検索する際にも使用される、請求項５または６に記載の処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワーク機器に用いられる処理内容等を記述するテーブル情報に対して各種情報（エントリ）を登録する登録方法と、そのような登録方法が適用された処理装置と、に関する。
【背景技術】
【０００２】
ルータやスイッチなどのネットワーク機器は、回線からパケットを受信し、そのパケットのヘッダに格納された情報などに基づいて、装置内に設定されたテーブル情報を検索し、検索結果に基づいてそのパケットに対して指定された処理を実行したりそのパケットを指定された回線から送信している。テーブル情報は、パケットのヘッダ情報などに含まれている特定の値に対して実行される特定の処理内容（あるいは特定の相手先への送信）の情報を、特定の値（キーという）とそれに対応した特定の処理との組み合わせ（エントリという）として格納したものであり、エントリ・テーブルなどと称されるものである。例えば、ネットワーク機器においてパケットフィルタリングの処理を行う場合には、パケットのヘッダ情報に基づきパケットの通過（スルー）／廃棄（ドロップ）等を指定するＡＣＬ（アクセス制御リスト：Access Control List）をテーブル情報として用い、受信したパケットのヘッダ情報に基づいてＡＣＬテーブルを検索し、検索結果に応じてそのパケットを通過（スルー）させたり廃棄（ドロップ）する処理を実行する。テーブル情報の検索は、テーブル内のエントリを順番に調べ、パケットヘッダから取り出した値と一致するエントリがあれば、そのエントリにおいて規定された処理を実行し、いずれのエントリとも一致しない場合には、予め定めたデフォルトの処理を実行するようにしている。テーブル情報は、パケットに対する処理とは別の登録機能や、外部サーバなどからの登録・削除・変更指示により操作される。なお、パケットのヘッダ情報として可能性のあるすべての値に対して処理を記述した場合、テーブル情報のデータ量が極端に大きくなるため、対応するエントリがない場合にはデフォルトの処理を行うことを前提として、（デフォルト以外の）特定の処理を行うべき場合にエントリをテーブル情報として格納している。
【０００３】
図１０は、このようなパケット処理を行う処理装置の構成の一例を示している。この処理装置９０１は、ルータやスイッチといったネットワーク機器として利用されることを前提としたものであって、外部からパケットを受信するパケット受信部９０２と、テーブル情報を格納するテーブル格納部９０３と、受信したパケットのヘッダ情報などに基づいてテーブル格納部９０３内のテーブル情報を検索し、検索結果に応じた処理をそのパケットに施す検索・処理部９０４と、処理されたパケットを外部に送出するパケット送信部９０５と、外部サーバ９１０からの指示によってテーブル格納部９０３内のテーブル情報に対して登録・削除・変更などの処理を行うテーブル操作部９０６と、から構成されている。
【０００４】
テーブル情報の検索において、パケットのヘッダ情報に合致するエントリがテーブル情報内にあるかどうかを検索するが、テーブル情報内の多数のエントリのすべてを順番に総当たりで検索した場合、検索に要する演算回数が多くなり、検索時間がかかりすぎるという問題が生じる。そこで非特許文献１には、実際のエントリ・テーブルに対してハッシュ関数を適用してハッシュ・テーブルを作成し、パケットヘッダから取り出した値に対しても同じハッシュ関数を適用してハッシュ値を求め、このハッシュ値を用いてハッシュ・テーブルを検索することによって高速な検索を実行することが示されている。図１１は、ハッシュ・テーブルを用いたエントリ・テーブル検索の一例を示している。ここでは、ＩＰ(Internet Protocol)アドレスに基づき、テーブル情報を用いたパケット処理を実行する場合を説明する。
【０００５】
図１１に示すように、特定のＩＰアドレス（Ａ〜Ｆ）を有する６つのパケットに対して特定の処理を行うものとする。ハッシュ・テーブルを用いない場合には、入力パケットのヘッダからＩＰアドレスを取り出し、テーブル情報の６個のエントリと順番に比較することになる。比較途中でヒットしないと、最大６回のアドレス比較を行う必要がある。
【０００６】
これに対してハッシュ・テーブルを用いる場合には、実際のエントリ・テーブルに対してハッシュ関数を適用し、３２ビット長のＩＰアドレスから例えば４ビットのハッシュ値を求め、ハッシュ値ごとに対応するエントリを配置してハッシュ・テーブルを構築する。その結果、テーブル情報でのエントリは、ハッシュ・テーブルにおいて異なるハッシュ値のところに適度に散らばって分布することになる。そして、パケットに対する処理を行う場合には、パケットから取り出したＩＰアドレスに対して同じハッシュ関数を適用してハッシュ値を求め、ハッシュ・テーブルにおいてパケット側からのハッシュ値と同じハッシュ値であるところのみを検索することによって、テーブル情報のエントリのうちアドレスが一致するエントリがあるかどうかを調べる。図示した例では、ハッシュ・テーブルにおいてハッシュ値ごとのエントリの数は高々１つであるから、１回の検索を行うだけで、パケットに対する処理に必要な情報を得ることができる。
【０００７】
しかしながら、実際のエントリ・テーブルの内容に変更があり、例えば、６個のエントリが、アドレスＧ〜Ｌにそれぞれ対応するものになったものとする。この場合も、ハッシュ・テーブルを用いない場合には最大６回の検索が必要である。一方、エントリの内容によっては、ハッシュ・テーブルにおいて同一のハッシュ値に複数のエントリが対応することが考えられる。図示した例では、アドレスＬ，Ｇ，Ｉ，Ｈの４個のエントリがハッシュ・テーブルにおいて同一のハッシュ値に対応している。エントリの内容によってこのようなハッシュ値の集中が生じ、その結果、その集中が生じたハッシュ値に対しては、パケット処理のために複数回の検索を行う必要が生じて、ハッシュを用いたことの効果が薄れ、処理装置におけるスループットの低下がもたらされることになる。ハッシュ値におけるエントリの集中は、処理装置がその速度保証値を満たせなくなることの原因ともなり得る。
【０００８】
そこで、図１２に示すように、複数のハッシュ関数（図１２に示した例では関数１〜関数１２８までで表される１２８通りのハッシュ関数）を用意し、実際のエントリ・テーブルのエントリの内容に応じて最適なハッシュ関数を選択して、ハッシュ値におけるエントリの集中が起こずに各ハッシュ値にエントリが分散するようにハッシュ・テーブルを構築することが考えられている。図１２に示した例では、６個のアドレス（Ｇ〜Ｌ）に対応するエントリに関し、関数１では特定のハッシュ値に対して４個のエントリが集中し（すなわち、最大４回の検索が必要となる）、関数１２８では特定のハッシュ値に対して２個のエントリが集中しているが、関数１０では、ハッシュ値あたりのエントリの数は高々１個となっている。すなわち、６個のエントリがアドレスＧ〜Ｌにそれぞれ対応するものである場合には、関数１０をハッシュ関数として選択してハッシュ・テーブルを構築することにより、パケットを処理するためのテーブル検索では最大１回の検索を行えばよいようになる。
【０００９】
このように、実際のエントリ・テーブルに登録されているエントリに応じてハッシュ関数を選択し、ハッシュ・テーブルを構築することによって、パケット処理のための検索に要する時間をさらに短縮することが可能になる。
【００１０】
しかしながら、ハッシュ関数等を用いてテーブル情報の検索に要する時間を短縮できたとしても、テーブル情報自体に対する登録・削除・変更の操作がテーブル情報の検索と競合によって、全体としての処理性能の低下がもたられる可能性がある。例えば、図１０に示した処理装置９０１において、テーブル格納部９０３では複数のハッシュ関数の中から最適なハッシュ関数を選択してハッシュ・テーブルが構築されていたとしても、受信したパケットの処理のために検索・処理部９０４によって行われるテーブル情報の検索と、外部サーバ９１０からの指示によってテーブル操作部９０６が行うテーブル情報の登録・削除・変更などの操作（これには、ハッシュ関数の選択やハッシュ・テーブルの構築も含まれる）とが競合し、パケット処理性能あるいはテーブル情報操作性能に影響を及ぼす可能性がある。パケットに対する処理を行う処理装置では、近年のトラヒック増加に伴って高い処理性能（パケット転送性能、登録処理性能等）が望まれるが、そのような高い処理性能を有するパケット処理装置においては、テーブル情報に対する検索処理と操作処理との競合の対策が必要となる。
【００１１】
図１３は、テーブル情報に対する検索処理と操作処理との競合を説明する図である。ここでは、テーブル情報は、実際のエントリが登録される実データ・テーブルと、実データ・テーブル中のエントリに基づいて構成されたハッシュ・テーブルと、から構成されているものとする。
【００１２】
実データ・テーブルに対し、エントリの登録・削除要求（図中の［１］）があると、実データ・テーブルはその要求に応じて書き換えられる。次に、１２８個のハッシュ関数の群の中から、書き換え後の実データ・テーブルに応じた最適なハッシュ関数が選択され、書き換え後の実データ・テーブルに対してその選択されたハッシュ関数を適用することにより、ハッシュ・テーブル（すなわち新ハッシュ・テーブル）がテーブル情報とは別の記憶領域である作業領域内において構築される（図中の［２］）。その後、新ハッシュ・テーブルをコピーし、テーブル情報内のハッシュ・テーブルを新ハッシュ・テーブルによって上書きする（図中の［３］）。外部から到来したパケットに対しては、そのヘッダ情報からハッシュ値を計算し、ハッシュ・テーブルを用いたテーブル情報の検索を行うことにより、対応するパケット処理が行われる（図中の［４］）。
【００１３】
［１］に示すエントリの登録・削除要求が頻繁に生じ、かつ到達パケット数が多い場合、上述の［１］〜［４］の処理に関してブロッキングや待ち行列など発生する。一括して多数のエントリをまとめて登録・削除などの操作を行う可能性は多々あることから、このようにバースト的にエントリの登録・削除要求が発生することは想定される。
【００１４】
図において［２］に示したハッシュ・テーブルの構築の際には、実データ・テーブルはロックされ、エントリの登録・削除についての新たな要求は受け付けられなくなるため、［１］に示したエントリの登録・削除の処理にブロッキングが生じることになる（図中のＡ）。ブロックされた要求は、処理待ち状態となり、ハッシュ・テーブルの構築に長時間を要すると、エントリの登録・削除の要求と同様に長時間待たされることになる。［３］の新ハッシュ・テーブルのコピーを行っているときは、［４］のパケット処理を行うことができないため、パケットの入力がブロックされて、パケットロスの要因となり得る（図中Ｂ）。新ハッシュ・テーブルのコピーの完了後、未処理のままバッファリングされていた一連のパケットに対するパケット処理が順次実行されるが、バッファリングされていたパケットの処理を行っているときは、逆に、［３］の新ハッシュ・テーブルのコピーがブロックされ（図中Ｃ）、コピーの遅れにつながる。
【先行技術文献】
【非特許文献】
【００１５】
【非特許文献１】神明  達哉、尾上  淳、山本  和彦、萩野  純一郎、江崎  浩、村井  純、「経路表を利用したＩＰパケット受信処理」、電子情報通信学会論文誌Ｂ、第Ｊ８５−Ｂ巻、第８号、１３１１−１３３８頁、２００２年８月
【発明の概要】
【発明が解決しようとする課題】
【００１６】
エントリ・テーブルを検索し検索結果に応じてパケット処理を行う場合、エントリ・テーブルへの登録・削除・変更の操作の処理とエントリ・テーブルの検索の処理の競合とが発生し、処理の遅れやパケットロスの原因ともなり得る。
【００１７】
本発明の目的は、待ち行列や処理のブロッキングを発生させることなく、テーブル検索とも競合せずに、エントリ・テーブルに対してエントリの登録・削除・変更などを高速に行うことができるエントリ登録方法を提供することにある。
【００１８】
本発明の別の目的は、エントリ・テーブルに対するエントリの登録・削除・変更などの操作の処理とテーブルを検索する処理とが競合せず、パケットロスなどを生じることなく、エントリの操作の処理とテーブル検索結果に基づくパケットに対する処理とを高速に行うことができる処理装置を提供することにある。
【課題を解決するための手段】
【００１９】
本発明の登録方法は、エントリ・テーブルに対する検索処理を可能にしつつ、エントリ・テーブルへのエントリの登録を行うための方法である。この方法では、第１及び第２のエントリ・テーブルを使用し、第１及び第２のエントリ・テーブルには、それぞれ、テーブル操作指示に基づく実際のエントリが格納されるとともに、エントリをそのハッシュ値に応じて格納する第１及び第２のハッシュ・テーブルが構築されるようにする。第１の期間においては、第１のハッシュ・テーブルを第１のエントリ・テーブル内に構築しつつ、第２のハッシュ・テーブルに対する検索処理を可能にし、第２の期間においては、第１の期間とは逆に、第２のエントリ・テーブル内に第２のハッシュ・テーブルを構築しつつ、第１のハッシュ・テーブルに対する検索処理を可能にする。このような第１の期間と第２の期間とを交互に繰り返す。
【００２０】
本発明の処理装置は、エントリ・テーブルへのエントリの登録を行いつつエントリ・テーブルに対する検索処理を実行する処理装置である。この処理装置は、実際のエントリを格納するとともに第１のハッシュ・テーブルを備える第１のテーブル格納部と、実際のエントリを格納するとともに第２のハッシュ・テーブルを備える第２のテーブル格納部と、テーブル操作指示に基づくエントリをそのハッシュ値に応じて第１及び第２のハッシュ・テーブルに格納することによって第１及び第２のハッシュ・テーブルを構築するハッシュ構築部と、入力データから得られたハッシュ値に応じて第１及び第２のハッシュ・テーブルを検索し検索結果に応じて入力データに対する処理を実行する検索・処理部と、制御部と、を備える。制御部は、第１の期間においては、ハッシュ構築部が第１のハッシュ・テーブルを構築しかつ検索・処理部が第２のハッシュ・テーブルを検索し、第２の期間においては、第１の期間とは逆に、ハッシュ構築部が第２のハッシュ・テーブルを構築しかつ検索・処理部が第１のハッシュ・テーブルを検索するように、かつ、これらの第１の期間と第２の期間とが交互に繰り返されるように、ハッシュ構築部と検索・処理部とを制御する。
【発明の効果】
【００２１】
本発明は、それぞれハッシュ・テーブルを有するエントリ・テーブルを２面設け、一方の面においてエントリに応じたハッシュ・テーブルを構築する処理を行いながら、他方の面においてハッシュ・テーブルに対する検索処理を可能にし、ハッシュ・テーブルの構築処理に対象となる面と検索処理の対象となる面とを任意の契機をもとに入れ替えることにより、エントリの操作の処理とテーブル検索結果に基づく処理との競合が避けられて、これらの処理を高速に行うことができるようになる、という効果が得られる。
【図面の簡単な説明】
【００２２】
【図１】本発明の実施の一形態の処理装置を説明するブロック図である。
【図２】図１に示す処理装置の動作原理を示すブロック図である。
【図３】（ａ），（ｂ）は、いずれも、メモリとバスの構成を示す図である。
【図４】処理対象面の構成と初期値とを示す図である。
【図５】テーブル操作処理とＡＣＬ処理がなされるときの処理対象面を示す図である。
【図６】ハッシュ構築処理用のワーク（作業用）テーブルの構成を示す図である。
【図７】ハッシュ構築処理がなされるときの処理対象面を示す図である。
【図８】ハッシュ値の生成を説明する図である。
【図９】処理面ごとに複数のハッシュ・テーブルを備える構成を示す図である。
【図１０】処理装置の構成の一例を示すブロック図である。
【図１１】ハッシュ・テーブルを用いたエントリ・テーブル検索の一例を示す図である。
【図１２】複数のハッシュ関数によるハッシュ・テーブルを用いたエントリ・テーブル検索の一例を示す図である。
【図１３】テーブル情報に対する検索処理と操作処理の競合を説明する図である。
【発明を実施するための形態】
【００２３】
次に、本発明の好ましい実施の形態について、図面を参照して説明する。
【００２４】
図１に示す本発明の実施の一形態の処理装置１０１は、ルータやスイッチといったネットワーク機器として利用されることを前提としたものであって、図１０〜１３を用いて示したものと同様に、パケットを受信し、パケットのヘッダ情報などに含まれる値に基づいてエントリ・テーブルを検索し検索結果に応じてそのパケットに対する処理を行うものである。エントリ・テーブルは、実際のエントリのデータから構成される実データ・テーブルと、実データ・テーブル中のエントリに基づいて構築されたハッシュ・テーブルとからなっている。この処理装置では、図１において符号１１１，１１２により示すように、エントリ・テーブルを格納するテーブル格納部が２つ設けられている。すなわちこの処理装置１０１には、エントリ・テーブルが２面設けられることになる。各テーブル格納部１１１，１１２は、実データ・テーブルを格納する実エントリ登録部１２１，１３１と、ハッシュ・テーブルを格納するハッシュ・テーブル登録部１２２，１３２とから構成されている。また、外部サーバなどからの指示を受けて実データ・テーブル１２１，１３１内の実データ・テーブルに対して登録・削除・変更の操作の処理を行うテーブル操作部１１３と、実データ・テーブル１２１，１３１内の実データ・テーブルからハッシュ・テーブルを構築して対応するハッシュ・テーブル登録部１２２，１３２内に格納するハッシュ構築部１１４が設けられている。
【００２５】
さらにこの処理装置１０１には、外部からパケットを受信するパケット受信部１０２と、受信したパケットのヘッダ情報などに基づいてテーブル格納部１１１，１１２を検索し、検索結果に応じた処理をそのパケットに施す検索・処理部１０４と、処理されたパケットを外部に送出するパケット送信部１０５と、全体の動作タイミングを規定するタイミング制御部１１５とを備えている。ここでは、検索・処理部１０４、テーブル操作部１１３及びハッシュ構築部１１４は、２つのテーブル格納部１１１，１１２に対して共通のものとされており、後述するように、エントリ操作処理とエントリ検索処理とが競合しないように、タイミング制御部１１５によって制御されて、２つのテーブル格納部１１１，１１２にアクセスする。このとき検索・処理部１０４とテーブル操作部１１３、ハッシュ構築部１１４は、同一のエントリ・テーブルに同時にはアクセスせず、周期的に切り替わるようにして、交互にアクセスする。
【００２６】
図２は、本実施形態の処理装置１０１の動作原理を示している。ここでは、テーブル格納部１２１，１２２に格納されるエントリ・テーブル（テーブル情報）を区別するため、テーブル格納部１２１に格納されるものをテーブルＡで表わし、テーブル格納部１２２に格納されるものをテーブルＢで表わす。本実施形態では、エントリに対する登録や削除の処理とパケット処理とを一方の面に関して実行し、ハッシュ・テーブルの構築を他方の面に関して実行することとして、任意のタイミングで、これらの面の間でそれらの面に対してなされる処理を切り替えるようにしている。
【００２７】
第１の期間においては、テーブルＡにおいて、実データ・テーブルに対してエントリの登録・削除・変更の操作処理が行われ、同時に、パケットに対する処理の実行のためにハッシュ・テーブルが検索対象となる。同じ期間において、テーブルＢでは、実データ・テーブルからハッシュ・テーブルを構築する。動作開始時には、その時点で、実データ・テーブル及びハッシュ・テーブルに関してテーブルＡ，Ｂ間において内容が同じであるようにする。動作開始時に処理対象とする面の切替が起きている場合には、当該切替の直後に、テーブルＡにおいて、実データ・テーブルの内容をクリアして、最新データをテーブルＢの実データ・ファイルから内容をコピーするようにする。
【００２８】
第１の期間から第２の期間へ切り替わるときに、処理対象とする面の切替が起こり、この切替の直後に、テーブルＢにおいて、実データ・テーブルの内容をクリアして、最新データをテーブルＡの実データ・ファイルから内容をコピーするようにする。そして、第２の期間内においては、テーブルＡでは実データ・テーブルからハッシュ・テーブルを構築し、テーブルＢでは、実データ・テーブルに対してエントリの登録・削除・変更の操作処理が行われ、同時に、パケットに対する処理の実行のためにハッシュ・テーブルが検索対象となる。
【００２９】
それ以降は、任意のタイミングで処理対象の面を切り替えることを繰り返す。
【００３０】
この処理装置では、２面のテーブルを設け、一方の面で実データ・テーブルに対するエントリの操作処理とハッシュ・テーブルを用いたエントリの検索処理とを行わせ、他方の面でハッシュ・テーブルの構築を行うことによって、処理のブロッキングなどが起こることはない。具体的に言えば、図１３に示した例におけるブロッキングの要因のうち、エントリの登録・削除とハッシュ・テーブルの構築とが別の面で行われるので、エントリの登録・削除の処理にブロッキングは生じず、処理対象の面の切替の形で新ハッシュ・テーブルを導入しているので、新ハッシュ・テーブルのコピーに伴うパケット処理におけるブロッキングも生じないことになる。当然のことながら、処理待ちのパケットが生じないので、パケット処理遅延も生じない。なお、処理対象面の切替の直後に、実データ・テーブルの内容をクリアして最新のデータをもう一方の面の実データ・テーブルからコピーする処理を行っており、このコピーの処理を行っている間は、実データ・テーブルに対するエントリ登録処理を行うことはできない。しかしながら、コピーに要する時間が短いことと、エントリ登録とハッシュ・テーブル構築とが分離していて処理対象面の次回の切替が行われるまでにエントリ登録処理が完了していれば上述した最大２サイクルの遅延を超える遅延は発生し得ないことから、実データ・テーブルのコピーに起因する遅延は無視することができる。
【００３１】
このように本実施形態の処理装置１０１では、データが面を移動するのではなく、面の間で処理が移動する（処理対象の面を切り替える）ことにより、データのコピーに伴う処理のブロッキングを防ぐことができる。処理対象の面の切り替えを任意のタイミングに行うことにより、エントリの登録などが最大で２サイクル遅れて反映することになるが、処理待ちによる大幅な遅延を防ぐことができる。この処理装置では、エントリ検索に基づく処理の性能（例えば、パケット転送性能）とエントリの登録処理性能とを両立させている。
【００３２】
上記の説明では、処理対象面の切替を任意のタイミングで行うものとしたが、周期的に処理対象面の切替を行うようにしてもよい。処理対象面の切替を周期的に行うものとした場合、エントリ登録操作が一切なされないまま、処理対象面の切替のタイミングが到来することもあり得る。そのような場合、エントリ登録操作が行われていないことを確認し、そのタイミングで切替を行わないようにすることで、実データ・エントリのコピーやハッシュ・テーブルの構築を行う計算リソースの浪費を回避することもできる。
【００３３】
本実施形態の処理装置１０１をハードウェアとして実装する場合には、高速処理を実現するために、例えば、検索・処理部１０４、テーブル操作部１１３及びハッシュ構築部１１４をそれぞれ独立したＣＰＵ（中央演算ユニット）あるいはプロセッサで構成することが好ましい。また、検索・処理部１０４、テーブル操作部１１３及びハッシュ構築部１１４をそれぞれ独立したＣＰＵで構成した場合、タイミング制御部１１５は、処理対象面の切替のためのタイマ管理を行うとともに、各ＣＰＵに対してどちらの面のテーブルに対して処理を行うかを指示することになる。このようなタイミング制御部１１５自体も、検索・処理部１０４、テーブル操作部１１３及びハッシュ構築部１１４を構成する各ＣＰＵとは別個のＣＰＵによって構成することが好ましい。テーブルＡ，Ｂ（すなわちテーブル格納部１２１，１２２）は、各ＣＰＵに共通に接続したメモリ内に設けられる。その場合、テーブルに対する登録・削除・変更等の操作の処理、パケット処理のためのテーブルの検索処理、及びハッシュ・テーブル構築処理におけるメモリアクセスがメモリバス上で競合しないように、メモリ構成としては、書き込みバスと読み出しバスとが分離したものを用いることが好ましい。図３（Ａ）は、単一の物理的なメモリ内に２面のテーブルを格納する場合を示し、この場合は、書き込みバス１５１、読み出しバス１５２とも十分に帯域が大きいものを用いることが好ましい。あるいは、図３（Ｂ）に示すように、テーブルＡ用のメモリとテーブルＢとを別個に設け、これらのメモリに接続する書き込みバス１５３と読み出しバス１５４とをメモリごとに分離して設けるようにする。
【００３４】
［実施例］
以下、ＩＰｖ４によるＩＰパケットに対するＡＣＬによるパケット・フィルタリングを例に挙げて、上述した処理装置の動作をさらに詳しく説明する。ここでは、ＩＰパケットのヘッダに含まれる３２ビットの送信元アドレスによってパケット・フィルタリングを行うものとし、ＡＣＬテーブルにヒットした場合にパケットを廃棄(drop)し、ヒットしない場合にパケットを通過(through)させるものとする。またここでは、ハッシュ関数として８通りのものを用意し、図１２に示したものと同様に、８通りのハッシュ関数の中から最適なものを選択して、その選択したハッシュ関数によるハッシュ・テーブルを構築するものとする。
【００３５】
処理装置は４個のＣＰＵを含んでおり、それらをＣＰＵ＃０〜＃３とする。ＣＰＵ＃０は、処理対象面の切替の指示等を行うものであって、図１に示したものでのタイミング制御部１１５に相当し、ＣＰＵ＃１は、実データ・テーブルに対するエントリの登録・削除・変更の処理（テーブル操作処理）を行うものであって、テーブル操作部１１３に相当し、ＣＰＵ＃２は、実データ・テーブルからハッシュ・テーブルを構築する処理（ハッシュ構築処理）を行うものであって、ハッシュ構築部１１４に相当し、ＣＰＵ＃３は、ＡＣＬテーブルを検索し検索結果に応じてパケットの通過や廃棄などを行う処理（ＡＣＬ処理）を行うものであって、検索・処理部１０４に相当する。
【００３６】
２面のＡＣＬテーブルとして同一フォーマットのＡＣＬテーブルＡ及びＡＣＬテーブルＢ（すなわちテーブル格納部１２１，１２２）を用いる。表１は、どのＣＰＵがどのタイミングでどの面に対して処理を行っているかのスケジューリングを示している。処理対象となる面は、０．５秒ごとに周期的に切り替わる。
【００３７】
【表１】
2013179421.tif 000003
【００３８】
図４は、各ＡＣＬテーブルの初期値を示す図である。上述したようにＡＣＬテーブルは、実データ・テーブルが格納される実エントリ登録部とハッシュ・テーブルが格納されるハッシュ・テーブル登録部とから構成されている。
【００３９】
実エントリ登録部では、実データ・テーブルとして、エントリ情報が、ポインタによって次のエントリを特定するようにしたチェーン構成で登録される。実エントリ登録部にはハッシュ値は登録されない。各エントリは、当該エントリの実データと、メモリにおける次のエントリの格納位置を示すポインタである次メモリ位置情報と、から構成されている。実エントリ登録部はさらに先頭ポインタを含んでおり、実エントリ登録部にエントリがあれば、最初のエントリのメモリ位置情報がポインタに登録される。これに対し、実エントリ登録部にエントリが１つも登録されていない場合には、「ＮＵＬＬ」が先頭ポインタに登録される。また、次エントリが存在しないときには、次メモリ位置情報には「ＮＵＬＬ」が登録される。図４は初期値を示しているので、実エントリ登録部の先頭ポインタには「ＮＵＬＬ」が登録され、他のエントリは示されていない。
【００４０】
ハッシュ・テーブル登録部は、実際にハッシュ・テーブルが登録されるハッシュ・テーブル部と、ハッシュ・テーブル部に登録されたハッシュ・テーブルを生成するために用いたハッシュ関数を特定する情報を格納するハッシュ関数ＩＤ部と、からなっている。ハッシュ・テーブル部は、実エントリ登録部の情報をハッシュ・テーブルに展開するための配列であり、そのインデックスがハッシュ値を表し、値はそのハッシュ値に対応するエントリに対する先頭ポインタ（すなわち位置情報）である。ここでは、ハッシュ関数は０から２５５までのいずれかの整数をとるものとしている。ハッシュ・テーブルにおける１つのインデックスに対して複数のエントリが対応することがあるので、インデックスごとに、対応するエントリ情報の実データが、実エントリ登録部の場合と同様に、ポインタによって次のエントリを指定するようにしてチェーン構成で登録される。図４は初期値を示しているので、ハッシュ・テーブル部の各値には「ＮＵＬＬ」が登録されている。ハッシュ関数ＩＤ部では、後述するハッシュ構築処理において８個のハッシュ関数の中から選択したハッシュ関数を特定するためのＩＤが登録される。
【００４１】
次に、各ＣＰＵによる処理を具体的に説明する。
【００４２】
表１に示すように、同一のＡＣＬテーブル（例えば、時刻０秒から０．５秒の期間ではＡＣＬテーブルＡ）に対し、ＣＰＵ＃１によるテーブル操作処理とＣＰＵ＃３によるＡＣＬ処理とが同時に行われる。
【００４３】
テーブル操作処理は、ＡＣＬテーブルへのエントリの登録・削除・変更の要求を元に処理対象面の実エントリ登録部への登録・削除処理を行い、実エントリ登録部の最新情報化（処理対象面の切替時の最新データのコピー）も行う処理である。このテーブル操作処理では、まず、処理対象面の切替があった直後に、実エントリ登録部の内容を図４に示すようにゼロまたはＮＵＬＬにクリアし、次に、もう一つのＡＣＬテーブル（ハッシュ構築処理の対象となっている方のＡＣＬテーブル）の実エントリ登録部の情報、すなわち、処理対象面の切替の前にテーブル操作処理の対象となっていた面の情報を現在のテーブル操作処理の対象である面の実エントリ登録部にコピーして、実エントリ登録部の情報を最新のものとする。そして、エントリ登録・削除・変更要求に基づき、実エントリ登録部への登・削除・変更の処理を行う。その結果、図５に示すように、実エントリ登録部において、チェーン状にエントリが構成されることになる。そして、予め定めた時間の経過後、表１に示したスケジュールに基づく切り替え指示に応じて、処理対象面を切り替える。その後は、それまでとは異なるＡＣＬテーブルにおいて、テーブル操作処理が行われることになる。
【００４４】
同一のＡＣＬテーブルに対してテーブル操作処理と並行してＣＰＵ＃３により行われるＡＣＬ処理は、ハッシュ構築処理で構築したハッシュ・テーブルを使用して、通常のパケット処理と同様の手順で行われるものである。この処理では、まず、ハッシュ関数ＩＤ部に登録されているハッシュ関数（図５に示した例ではＩＤが２で表されるハッシュ関数）を入力パケットの送信元アドレスに適用してハッシュ値を求め、次に、ハッシュ・テーブル部内で、送信元アドレスから求めたハッシュ値と一致するインデックスに対応する先頭ポインタを求め、このポインタからチェーンをたどりながらエントリである実データを取り出し、入力パケットのアドレスと一致するエントリがあった場合にはその入力パケットを廃棄し、なかった場合にはその入力パケットを通過させる。
【００４５】
予め定めた時間の経過後、表１に示したスケジュールに基づく切り替え指示に応じて、テーブル操作処理での切替と同時に処理対象面を切り替える。その後は、それまでとは異なるＡＣＬテーブルにおいて、ＡＣＬ処理が行われることになる。
【００４６】
ＣＰＵ＃２によるハッシュ構築処理は、ＣＰＵ＃１によるテーブル操作処理とＣＰＵ＃３によるＡＣＬ処理の対象となっているＡＣＬテーブルとは異なるＡＣＬテーブルにおいて行なわれる。ハッシュ構築処理では、テーブル操作処理によって作成された実エントリ登録部の情報に基づいて、８個のハッシュ関数からなるハッシュ関数群の中からハッシュ値の衝突の少ない関数を選定し、その関数のＩＤ情報をハッシュ関数ＩＤ部に登録し、また、選定したハッシュ関数を用いて、実エントリ登録部の情報をハッシュ・テーブル部に展開する。具体的には、図６に示すようなワーク（作業用）テーブルを例えばメモリ上に用意し、実エントリ部の各エントリ（実データ）に対して８個のハッシュ関数をそれぞれ適用して、ハッシュ値ごとに何個のエントリがそのハッシュ値に対して生成されたかをカウントし、カウントした結果をワーク・テーブルの該当箇所に記録する。以下の説明において、１つのハッシュ値に対して何個のエントリが対応するかを集中度と呼ぶ。例えば、ＩＤが０であるハッシュ関数では、５個のエントリのいずれもがハッシュ値が１となったとすると、ワーク・テーブルでは、ＩＤ０かつハッシュ値１に対応して、集中度として「５」が記録される。そして、ワーク・テーブルにおいて、ハッシュ関数ごとに集中度の最大値を求め、集中度の最大値が最小であるハッシュ関数を選択し、そのハッシュ関数のＩＤをハッシュ関数ＩＤ部に格納する。図６のワーク・テーブルにおいて、ハッシュ関数ごとの最大の集中度は、太枠に囲まれて示されている。そして、集中度の最大値が２であるハッシュ関数ＩＤ２が、実際にハッシュ・テーブルを構築するためのハッシュ関数として選択される。
【００４７】
その後、ハッシュ・テーブル部を図４に示すようにゼロまたは「ＮＵＬＬ」にクリアし、その後、改めて、実エントリ登録部の情報に対してその選択したハッシュ関数を適用して各エントリのハッシュ値を求め、求めたハッシュ値にインデックス値に対応させるようにしてハッシュ・テーブル部においてチェーン構造で実データを格納するようにして、ハッシュ・テーブルの構築を行う。その結果、図７に示すように、ハッシュ・テーブル部が構築される。
【００４８】
予め定めた時間の経過後、表１に示したスケジュールに基づく切り替え指示に応じて、テーブル操作処理及びＡＣＬ処理での切替と同時に、ハッシュ構築処理の対象面を切り替える。その後は、それまでとは異なるＡＣＬテーブルにおいて、ハッシュ構築処理が行われることになる。
【００４９】
以上説明した例では、テーブル操作処理、ハッシュ構築処理及びＡＣＬ処理は、いずれも、切替の周期である０．５秒以内に完了する必要がある。そのため、必要に応じて、最大登録エントリ数やハッシュ関数群における関数の数、切替時間（本例では０．５秒）の調整を行う。特にハッシュ構築処理では、各ハッシュ関数ごと、各ハッシュ値ごとの集中度の係数と、その後のハッシュ関数の選定に時間がかかるおそれがある。そこで、ハッシュ構築処理のうち、上述したワーク・テーブルの生成と集中度の算出までをテーブル操作処理において実行することも可能である。テーブル操作としてエントリの登録と削除だけを認めるとすると、テーブル操作処理の一環として、エントリの登録があった場合にそのエントリのデータに対してすべてのハッシュ関数を適用してハッシュ値を算出し、算出されたハッシュ値に対応させてワーク・テーブル内の値を１だけ増やし、エントリの削除があった場合にも同様にすべてのハッシュ関数を適用し、ハッシュ値に対応させてワーク・テーブル内の値を１だけ減らすようにする。このようにすれば、ハッシュ構築処理の実行に要する処理時間を短縮することが可能である。なおエントリの変更処理は、エントリの削除処理とエントリの登録処理とを組み合わせることにより実行可能である。
【００５０】
次に、本実施例で使用可能なハッシュ関数群について説明する。図８は、ハッシュ関数の生成の一例を説明する図である。ここでは、３２ビット長のアドレスを対象としているので、図８に示すように、３２ビット長のデータを８ビットずつの領域＜Ａ＞〜＜Ｄ＞に４分割する。そして、Ｎを関数のＩＤ番号として（Ｎは０から７までのいずれかの整数）、＜Ａ＞の８ビットと、＜Ｂ＞をＮビット左に回転して得た８ビットと、＜Ｃ＞を２Ｎビット左に回転して得た８ビットと、＜Ｄ＞を３Ｎビット左に回転して得た８ビットとを加算し、オーバーフロー分を無視した８ビットをハッシュ値とする。このようなハッシュ関数は、基本的な演算命令としてＣＰＵに備えられている加算命令とビット回転命令だけで計算可能であるので、高速に算出することができる。
【００５１】
また、上述したハッシュ構築処理では、集中度の最大値が最小となるハッシュ関数の選定のためにハッシュ値を計算し、ハッシュ・テーブル部の構築のためにもハッシュ値を計算しており、計算量が多くなって処理に時間がかかる恐れがある。そこで、メモリは大量に消費するものの、計算量を減らし、かつ、ハッシュ構築処理用のＣＰＵ＃２を削減できるものとして、図９に示すような構成が考えられる。
【００５２】
図９に示した構成では、実データ・テーブルも使用せず、その代わり、ハッシュ関数ごとにハッシュ・テーブルを２面ずつ用意する。図示したものでは、ハッシュ関数群は４個のハッシュ関数からなり、それぞれがＡ，Ｂの２面のハッシュ・テーブルの構築に用いられることから、ハッシュ・テーブルはＡ−１〜Ａ−４，Ｂ−１〜Ｂ−４の８面が設けられることになる。ある期間において、ハッシュ・テーブルＡ−１〜Ａ−４は参照用であり、ハッシュ・テーブルＢ−１〜Ｂ−４は書込用であり、その期間の終了後、各ハッシュ・テーブルの用途が入れ替わって、ハッシュ・テーブルＡ−１〜Ａ−４は書込用となり、ハッシュ・テーブルＢ−１〜Ｂ−４は参照用となる。このような入れ替えは周期的に繰り返して実行される。図において読込フラグ、書込フラグとあるのは、Ａ，Ｂのいずれの面が参照用であり書込用であるかを示すものであり、読込フラグは参照用の面を示し、書込フラグは書込用の面を示している。
【００５３】
参照用のハッシュ・テーブルは、ＣＰＵ＃３による上述したものと同様のＡＣＬ処理に実行される。その場合、４つのハッシュ関数のそれぞれのハッシュ・テーブルのうち、以下に述べる最適面として選択されたものが、エントリ検索に使用される。
【００５４】
書込用の面に対しては、テーブル操作処理用のＣＰＵ＃１が処理を実行する。処理対象面の切替があったらその直後に、ＣＰＵ＃１は、参照用のハッシュ・テーブルの各面の内容をその時点で書込用とされたハッシュ・テーブルの各面にコピーする。テーブル操作指示があった場合には、その指示内容に応じて各ハッシュ関数ごとのハッシュ値を算出し、その結果を対応するハッシュ・テーブルに書き込む。この場合、算出されたハッシュ値に基づいて、ハッシュ・テーブルでの該当するインデックス値に対応してチェーン状に書き込まれている実データが書き換えられる。そして、各ハッシュ・テーブルごとにインデックス値ごとの集中度をカウントし、集中度の最大値が最小であるハッシュ・テーブルを最適面として選択する。
【００５５】
この構成では、各面は、常時、ハッシュ・テーブルの構成を維持しており、書込用の面では、エントリの登録・削除とハッシュ・テーブルの構築、最適面の選択とが行なわれ、参照用の面では最適なハッシュ・テーブルを用いたＡＣＬ処理が行われることになる。書込用の面と参照用の面とを周期的に切り替えることによって、ハッシュ・テーブルの構築と最適面の選択までを含むテーブル操作処理と、テーブル検索処理とが競合しないようになり、パケットロスなどを生じることなく、エントリの操作の処理とテーブル検索結果に基づくパケットに対する処理とを高速に行うことができるようになる。
【符号の説明】
【００５６】
１０１，９０１    処理装置
１０２，９０２    パケット受信部
１０４，９０４    検索・処理部
１０５，９０５    パケット送信部
１１１，１１２，９０３    テーブル格納部
１１３，９０６    テーブル操作部
１１４    ハッシュ構築部
１１５    タイミング制御部
１２１，１３１    実エントリ登録部
１２２，１３２    ハッシュ・テーブル登録部
１５１，１５３    書き込みバス
１５２，１５４    読み出しバス
９１０    外部サーバ
【図１】
2013179421.tif 000004
【図２】
2013179421.tif 000005
【図３】
2013179421.tif 000006
【図４】
2013179421.tif 000007
【図５】
2013179421.tif 000008
【図６】
2013179421.tif 000009
【図７】
2013179421.tif 000010
【図８】
2013179421.tif 000011
【図９】
2013179421.tif 000012
【図１０】
2013179421.tif 000013
【図１１】
2013179421.tif 000014
【図１２】
2013179421.tif 000015
【図１３】
2013179421.tif 000016