(57)【要約】【課題】テーブルを構成するエントリの追加・削除を短時間で行うためのテーブル更新方法および回路を提供する。【解決手段】テーブルを初期的に作るときに、空きエントリを前記テーブル全体に分散して配置する。また、既存の実エントリの間に新規エントリを追加する場合には、追加後に新規エントリの直前または直後になる既存の実エントリから最も近い空きエントリまでのエントリデータを、新規エントリも含めて書き換え、既存の実エントリを削除する場合には、当該エントリを空きエントリにする。さらに、書き換える部分を新規エントリの前方にするか後方にするか決定する際に、当該書き換える部分から空きエントリまでのエントリ数が少ない方を選択する。【選択図】　　　図２
2004080714.tif 000002
【特許請求の範囲】
【請求項１】
テーブルのエントリの検索キーによってソートされたテーブルを更新するテーブル更新方法において、
前記テーブルを初期的に作るときに、空きエントリを前記テーブル全体に分散して配置する、ことを特徴とするテーブル更新方法。
【請求項２】
テーブルのエントリの検索キーによってソートされたテーブルを更新するテーブル更新方法において、
既存の実エントリの間に新規エントリを追加する場合には、追加後に新規エントリの直前または直後になる既存の実エントリから最も近い空きエントリまでのエントリデータを、新規エントリも含めて書き換え、
既存の実エントリを削除する場合には、当該エントリを空きエントリにする、
ことを特徴とするテーブル更新方法。
【請求項３】
請求項２に記載のテーブル更新方法において、
既存の実エントリの間に新規エントリを追加する場合に書き換える部分を新規エントリの前方にするか後方にするか決定する際に、当該書き換える部分から空きエントリまでのエントリ数が少ない方を選択する、
ことを特徴とするテーブル更新方法。
【請求項４】
請求項３に記載のテーブル更新方法において、
前記テーブルの各エントリに、前方の空きエントリまでのエントリ数と後方の空きエントリまでのエントリ数をそれぞれ記憶させる領域を設けておき、
既存の実エントリの間に新規エントリを追加する場合に、これら前方の空きエントリまでのエントリ数と後方の空きエントリまでのエントリ数に基づいて書き換える部分を前方にするか後方にするかを選択するとともに、
既存の実エントリの間に新規エントリを追加する場合および既存の実エントリを削除する場合に、前記前方の空きエントリまでのエントリ数と後方の空きエントリまでのエントリ数を更新する
ことを特徴とするテーブル更新方法。
【請求項５】
テーブルのエントリの検索キーによってそれぞれソートされた現用テーブルおよび予備テーブルを用いて、現用テーブルと予備テーブルとを交互に切り替えるとともに、予備テーブルを更新対象とするテーブル更新方法において、
請求項１から請求項４までのいずれかに記載のテーブル更新方法を用いて前記予備テーブルを更新することを特徴とするテーブル更新方法。
【請求項６】
エントリ毎に検索キーと空きエントリ表示とデータとをそれぞれ記憶する領域を備えた複数のテーブルと、
前記複数のテーブルを、現用テーブルあるいは予備テーブルのいずれかに切り替える切り替え手段と、
前記切り替え手段によって切り替えられた結果予備テーブルとなっている側のテーブルを更新対象として書き換える書き換え手段と
を備えるテーブル更新回路において、
前記書き換え手段は、前記テーブルを初期的に作るときに、空きエントリを前記テーブル全体に分散して配置する、
ことを特徴とするテーブル更新回路。
【請求項７】
エントリ毎に検索キーと空きエントリ表示とデータとをそれぞれ記憶する領域を備えた複数のテーブルと、
前記複数のテーブルを、現用テーブルあるいは予備テーブルのいずれかに切り替える切り替え手段と、
前記切り替え手段によって切り替えられた結果予備テーブルとなっている側のテーブルを更新対象として書き換える書き換え手段と
を備えるテーブル更新回路において、
前記書き換え手段は、既存の実エントリの間に新規エントリを追加する場合には、追加後に新規エントリの直前または直後になる既存の実エントリから最も近い空きエントリまでのエントリデータを、新規エントリも含めて書き換え、
既存の実エントリを削除する場合には、当該エントリを空きエントリにする、
ことを特徴とするテーブル更新回路。
【請求項８】
請求項７に記載のテーブル更新回路において、
前記書き換え手段は、既存の実エントリの間に新規エントリを追加する場合に書き換える部分を新規エントリの前方にするか後方にするか決定する際に、当該書き換える部分から空きエントリまでのエントリ数が少ない方を選択する、
ことを特徴とするテーブル更新回路。
【請求項９】
請求項８に記載のテーブル更新回路において、
前記テーブルは、各エントリに、前方の空きエントリまでのエントリ数と後方の空きエントリまでのエントリ数をそれぞれ記憶させる領域を備えており、
前記書き換え手段は、既存の実エントリの間に新規エントリを追加する場合に、これら前方の空きエントリまでのエントリ数と後方の空きエントリまでのエントリ数に基づいて書き換える部分を前方にするか後方にするかを選択するとともに、既存の実エントリの間に新規エントリを追加する場合および既存の実エントリを削除する場合に、前記前方の空きエントリまでのエントリ数と後方の空きエントリまでのエントリ数を更新する
ことを特徴とするテーブル更新回路。
【請求項１０】
エントリ毎に検索キーと空きエントリ表示とデータとをそれぞれ記憶する領域を備えたテーブル記憶媒体において、
エントリ毎に、前方の空きエントリまでのエントリ数と後方の空きエントリまでのエントリ数をそれぞれ記憶する領域を設けたことを特徴とするテーブル記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、例えば通信機器やコンピュータなどにおいて、検索テーブルの更新を高速に行うためのテーブル更新方法および回路に関する。
特に、現用および予備の２系のテーブルを交互に切り替え、予備系のテーブルを対象として更新を高速に行うテーブル更新方法および回路に関する。
【０００２】
【従来の技術】
従来、コンピュータや通信機器等においてテーブル検索を高速に行う手法には幾つかあり、大別すると、所定のアルゴリズムに従ってＣＰＵ（Ｃｅｎｔｒａｌ　Ｐｒｏｃｅｓｓｉｎｇ　Ｕｎｉｔ　）で命令を実行することにより論理的に検索の高速化を図る手法と、ＦＰＧＡ（Ｆｉｅｌｄ　Ｐｒｏｇｒａｍｍａｂｌｅ　Ｇａｔｅ　Ａｒｒａｙ）や高速メモリで構成されたハードウェア回路を用いて処理することにより物理的に検索の高速化を図る手法とがある。
【０００３】
一般的特徴として、前者の手法は、テーブルを構成するエントリの追加・削除に対して柔軟に対応できるため短時間に行えるという長所がある反面、検索時間が長い場合があるという短所がある。
一方、後者の手法は、前者の逆で、検索時間は前者に比較して短いという長所があるが、テーブルを構成するエントリの追加・削除に対して柔軟性を欠くため短時間に行えないという短所がある。
【０００４】
後者の手法では、テーブルを構成するエントリの追加・削除をいかに短時間で行うかが問題となる。
従来は、上述のような検索キーを数値と見なしソートされたテープルを検索する方法として、下記の特許文献１に示されているようなバイナリサーチをベースとした検索方法が用いられている。
この方法では、ソートされた全エントリを検索テーブルの先頭から隙間無く配置する。そして、エントリ数がテーブルサイズより小さい一般的な場合に検索を正しく行えるようにするために、検索テーブル後方の空きエントリには、検索キーの最大値（例、検索キー部分がオール”１”）を設定し、エントリ内の検索キー以外の部分に、空きエントリ表示ビットを設ける等して、空きエントリとして管理していた。
このような検索テーブルで、エントリの追加・削除を行う方法としては、図４に示すように、物理検索テーブル（以下、単に検索テーブルと記すときはこれを指す）をハード的に物理メモリ上に、現用と予備の２面実装しておき、ＣＰＵでエントリの追加・削除を行った論理検索テーブルのデータ（全エントリ＋空きエントリ）を予備の検索デーブル上に転送した後、ＣＰＵからの切り替えトリガに基づき、切り替え器（切り替え手段）によって予備を現用に電子的に１クロックで切り替える方法が取られている。
【０００５】
［特許文献１］
特開平１０−１２６４４２号公報
【０００６】
【発明が解決しようとする課題】
従来の方法では、上述のように、エントリの追加・削除を行うために、全エントリを管理しているプロセッサ上で予備の検索テーブルに書き込むデータ（ソート処理等を終了済み）を作成して予備の検索テーブル（メモリ上）に転送していたため、この転送に数分〜数十分かかる。この方法は、エントリの追加・削除を、例えば翌日までにあるいは数時間後までにテーブルに反映させれば良いという従来の用途では特に問題はなかった。
しかしながら、昨今、顧客へのサービス向上等で、検索テーブルへの追加・削除がネットワークに反映されるまでの時間の短縮が求められるようになった。
【０００７】
本発明は、上記のような事情に鑑みて為されたものであり、テーブルを構成するエントリの追加・削除を短時間で行うためのテーブル更新方法および回路を提供することを目的とする。
より具体的に言うと、ハードウェア回路で高速に（例えば、ワイヤースピードで）テーブル検索処理を行うために、エントリの検索キーを数値と見なしてソートしたテーブルを検索するためのテーブル更新方法および回路を提供することを目的とする。ここでエントリの検索キーとは、例えば、ＩＰ（Ｉｎｔｅｒｎｅｔ　Ｐｒｏｔｏｃｏｌ　）アドレスや、ＭＡＣ（Ｍｅｄｉａ　Ａｃｃｅｓｓ　Ｃｏｎｔｒｏｌ）アドレス、ＡＴＭ（Ａｓｙｎｃｈｒｏｎｏｕｓ　Ｔｒａｎｓｆｅｒ　Ｍｏｄｅ　）におけるＶＰＩ（Ｖｉｒｔｕａｌ　Ｐａｔｈ　Ｉｄｅｎｔｉｆｉｅｒ）／ＶＣＩ（Ｖｉｒｔｕａｌ　Ｃｈａｎｎｅｌ　Ｉｄｅｎｔｉｆｉｅｒ　）である。
【０００８】
【課題を解決するための手段】
上記の課題を解決するために、本発明は、テーブルのエントリの検索キーによってソートされたテーブルを更新するテーブル更新方法において、前記テーブルを初期的に作るときに、空きエントリを前記テーブル全体に分散して配置する、ことを特徴とするテーブル更新方法を要旨とする。
【０００９】
また、本発明は、テーブルのエントリの検索キーによってソートされたテーブルを更新するテーブル更新方法において、既存の実エントリの間に新規エントリを追加する場合には、追加後に新規エントリの直前または直後になる既存の実エントリから最も近い空きエントリまでのエントリデータを、新規エントリも含めて書き換え、既存の実エントリを削除する場合には、当該エントリを空きエントリにすることを特徴とするものである。
また、本発明は、前記のテーブル更新方法において、既存の実エントリの間に新規エントリを追加する場合に書き換える部分を新規エントリの前方にするか後方にするか決定する際に、当該書き換える部分から空きエントリまでのエントリ数が少ない方を選択することを特徴とするものである。
また、本発明は、前記のテーブル更新方法において、前記テーブルの各エントリに、前方の空きエントリまでのエントリ数と後方の空きエントリまでのエントリ数をそれぞれ記憶させる領域を設けておき、既存の実エントリの間に新規エントリを追加する場合に、これら前方の空きエントリまでのエントリ数と後方の空きエントリまでのエントリ数に基づいて書き換える部分を前方にするか後方にするかを選択するとともに、既存の実エントリの間に新規エントリを追加する場合および既存の実エントリを削除する場合に、前記前方の空きエントリまでのエントリ数と後方の空きエントリまでのエントリ数を更新することを特徴とするものである。
【００１０】
また、本発明は、テーブルのエントリの検索キーによってそれぞれソートされた現用テーブルおよび予備テーブルを用いて、現用テーブルと予備テーブルとを交互に切り替えるとともに、予備テーブルを更新対象とするテーブル更新方法において、前記いずれかのテーブル更新方法を用いて前記予備テーブルを更新することを特徴とするテーブル更新方法である。
【００１１】
また、本発明は、エントリ毎に検索キーと空きエントリ表示とデータとをそれぞれ記憶する領域を備えた複数のテーブルと、前記複数のテーブルを、現用テーブルあるいは予備テーブルのいずれかに切り替える切り替え手段と、前記切り替え手段によって切り替えられた結果予備テーブルとなっている側のテーブルを更新対象として書き換える書き換え手段とを備えるテーブル更新回路において、前記書き換え手段は、前記テーブルを初期的に作るときに、空きエントリを前記テーブル全体に分散して配置することを特徴とするものである。
【００１２】
また、本発明は、エントリ毎に検索キーと空きエントリ表示とデータとをそれぞれ記憶する領域を備えた複数のテーブルと、前記複数のテーブルを、現用テーブルあるいは予備テーブルのいずれかに切り替える切り替え手段と、前記切り替え手段によって切り替えられた結果予備テーブルとなっている側のテーブルを更新対象として書き換える書き換え手段とを備えるテーブル更新回路において、前記書き換え手段は、既存の実エントリの間に新規エントリを追加する場合には、追加後に新規エントリの直前または直後になる既存の実エントリから最も近い空きエントリまでのエントリデータを、新規エントリも含めて書き換え、既存の実エントリを削除する場合には、当該エントリを空きエントリにすることを特徴とするものである。
また、本発明は、前記のテーブル更新回路において、前記書き換え手段は、既存の実エントリの間に新規エントリを追加する場合に書き換える部分を新規エントリの前方にするか後方にするか決定する際に、当該書き換える部分から空きエントリまでのエントリ数が少ない方を選択することを特徴とするものである。
また、本発明は、前記のテーブル更新回路において、前記テーブルは、各エントリに、前方の空きエントリまでのエントリ数と後方の空きエントリまでのエントリ数をそれぞれ記憶させる領域を備えており、前記書き換え手段は、既存の実エントリの間に新規エントリを追加する場合に、これら前方の空きエントリまでのエントリ数と後方の空きエントリまでのエントリ数に基づいて書き換える部分を前方にするか後方にするかを選択するとともに、既存の実エントリの間に新規エントリを追加する場合および既存の実エントリを削除する場合に、前記前方の空きエントリまでのエントリ数と後方の空きエントリまでのエントリ数を更新することを特徴とするものである。
【００１３】
また、本発明は、エントリ毎に検索キーと空きエントリ表示とデータとをそれぞれ記憶する領域を備えたテーブル記憶媒体において、エントリ毎に、前方の空きエントリまでのエントリ数と後方の空きエントリまでのエントリ数をそれぞれ記憶する領域を設けたことを特徴とするテーブル記憶媒体である。
【００１４】
【発明の実施の形態】
以下、この発明の一実施形態について説明する。
本実施形態の基本的方針は、メモリ上の予備の検索テーブルに全データを転送する従来の方法をやめ、追加・削除に基づいて検索テーブルの一部を変更する方法とすることである。
具体的には、まず最初に検索テーブルを作るときに、従来方法では検索テーブルの後方にまとめて配置された空きエントリを検索テーブル全体に分散して配置する。
そして、既存の実エントリの間に新規エントリを追加する場合には、新規エントリの直前（または直後）の既存の実エントリから最も近い空きエントリまでのエントリデータを、新規エントリも含めて書き換える。
また、既存の実エントリを削除する場合には、そのエントリを空きエントリにする。
以上のように、メモリ上の予備の検索テーブル上で、新規エントリの追加・削除に応じて部分的にデータを書き換えるため、反映時間を従来よりも短縮することができる。
【００１５】
尚、書き換える部分が新規エントリの前方（上方）になるか後方（下方）になるかは、空きエントリまでのエントリ数（即ち、書き換えエントリ数）が少ない方を選択する。
そのために、各エントリ内の検索キー以外の部分に、テーブルの上（前方）の空きエントリまでのエントリ数と、テーブルの下（後方）の空きエントリまでのエントリ数を表示するビットを設け、エントリ数を記入しておく。記入されるエントリ数は、例えば、当該エントリ自身が空きエントリの場合はどちらも”０”、上下双方とも空きエントリに隣接する実エントリの場合はどちらも”１”となる。
【００１６】
以下、図面を参照しながら、本実施形態をより具体的に説明する。
図１は、メモリ上の予備の検索テーブルにおける空きエントリの配備方法の違いを、例示したものである。
図１（ａ）は従来の配備方法で、ソートされた全エントリを検索テーブルの先頭から隙間無く配置し、空きエントリが検索テーブルの後方（下部）に配置されている。なお、空きエントリ表示が”１”となっているエントリが空きエントリである。また、各エントリには、検索結果として出力するための「データ」が対応付けて格納される。
図１（ｂ）は本実施形態の配備方法で、空きエントリが検索テーブル内に分散して配置されている。なお、上と同様に空きエントリ表示が”１”となっているエントリが空きエントリである。また、空きエントリのキー情報には隣接する上下いずれかの実エントリのキー情報とデータとを設定しておく。
最初の検索テーブル作成時の分散配置の具体的方法については後述するが、その後のエントリの追加・削除により、空きエントリの位置は逐次変化する。
【００１７】
図２は、本実施形態において、既存の実エントリの間に新規エントリを追加する場合のテーブル操作の例である。図示するように、検索テーブルには、エントリ毎に、「下の空きエントリまでのエントリ数」と「上の空きエントリまでのエントリ数」を記憶する領域がそれぞれ設けられている。
新規エントリを追加する位置を決める手順は次の通りである。
まず、検索キーを値とみなして比較して検索テーブル内をサーチし、ｎエントリ目と（ｎ＋１）エントリ目の間に位置することを検出する。
次に、検索テーブル内のｎエントリ目と（ｎ＋１）エントリ目のそれぞれの「下の空きエントリまでのエントリ数」と「上の空きエントリまでのエントリ数」、即ち４つの数値を比較し、最も小さい値を持つエントリに新規エントリを書き込む。
【００１８】
図２に示す例では、新規エントリのキー（Ｎ）の値が、キー（５）とキー（６）の値の間であり、これら２つのエントリの計４つの「空きエントリまでのエントリ数」が｛２，２，１，３｝であることから、もっとも小さい値「１」を持つキー（６）のエントリの位置に新規エントリを書き込む。同様に、新規エントリを書き込むことによってなくなるキー（６）のエントリは一つ下のエントリに書き込み、これと同様な書き込み処理を、空きエントリに書き込むまで順次行う。よって、検索テーブル全体を書き換える従来方式に比べて、本発明では一部しか書き換えないため、書き換えエントリ数が少なく、書き換え時間を短くできる。
【００１９】
なお、図２に示す例において、キー（５）とキー（６）との２つのエントリの計４つの「空きエントリまでのエントリ数」の中から最も小さい値を選択する代わりに、キー（５）のエントリの「上の空きエントリまでのエントリ数」（図の例の場合、「２」）と、キー（６）のエントリの「下の空きエントリまでのエントリ数」（図の例の場合、「１」）との２つの値を比較して、小さいほうの値を選択するようにしても良い。
【００２０】
なお、「上の空きエントリまでのエントリ数」または「下の空きエントリまでのエントリ数」における「Ｍ」は、これらの数値のためにテーブル内に設けられたビット数で表現可能な最大値を表している。このビット数は例えばパラメータで規定するようにする。
また、なお、図２（ｂ）において、右下コーナーを黒く塗った箇所がデータに変更があった箇所である。
【００２１】
図３は、本実施形態において、既存の実エントリを削除する場合の例である。図３に示す例において、キー（５）のエントリを削除する場合の具体的手順は次のとおりである。
削除対象のエントリは空きエントリとなるため空きエントリ表示を「１」とする。そして、当該エントリの「下の空きエントリまでのエントリ数」と「上の空きエントリまでのエントリ数」にそれぞれ初期値０を書き込む。
そして、削除対象のエントリから、順次、上のエントリに進みながら、「下の空きエントリまでのエントリ数」を、１、２、３、・・・と書き換えていく。これを他の空きエントリあるいはテーブルの端（先頭）に出会う直前まで繰り返す。
次に、削除対象のエントリから、順次、下のエントリに進みながら、「上の空きエントリまでのエントリ数」を、１、２、３、・・・と書き換えていく。これを他の空きエントリあるいはテーブルの端（末尾）に出会う直前まで繰り返す。なお、図３（ｂ）においても、右下コーナーを黒く塗った箇所がデータに変更があった箇所である。
【００２２】
この場合の空きエントリの検索キーとデータ部分は、隣接する実エントリの検索キーをコピーしたものであり、空きエントリの表示ビットと、上方向と下方向の空きエントリまでのエントリ数以外は同じである。
【００２３】
最初の検索テーブル作成時における空きエントリの配置方法としては、検索テーブル内のエントリの「空きエントリまでのエントリ数」の最大値が最小になるように配置する方法がある。
【００２４】
本実施形態では、従来技術のように予備テーブルを全て書き換えることはしないため、開始時を除いて、現用と予備のテーブルが切り替わった直後は、予備テーブルのデータの方が現用テーブルのデータより古い。このため、予備テーブルの更新（追加・削除）は、まず、この予備テーブルが現用テーブルだった時に当時の予備テーブルに対して加えられた更新処理を行い、更に現在要求されている更新処理を行うことになる。
但し、テーブルの切り替えは頻繁に行われることが想定されるため、処理量としては少ないものである。
【００２５】
なお、本実施形態を実現するためのハードウェア構成は基本的には図４に示した従来技術によるものと同様のもので良いが、追加・削除の際には、直接予備系のテーブルが書き換えられるため、図４に示されている論理検索テーブルは使用しなくてもよい。また、物理検索テーブルの記憶媒体には半導体等のメモリを用いる。また、物理検索テーブル上でのエントリの更新（追加・削除など）を行うために、ＦＰＧＡで構成されたハードウェア回路を用いてテーブルの書き換えを行うようにしても良いし、ＣＰＵが直接テーブルの書き換えを行うようにしても良い（書き換え手段）。
【００２６】
以上、図面を参照してこの発明の実施形態を詳述してきたが、具体的な構成はこれらの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【００２７】
【発明の効果】
上述したように、本発明を用いると、エントリの追加や削除において、従来方式に比べて、検索テーブル内の書き換えエントリ数が少ないので、書き換え時間を短くできる。より具体的には、以下の通りである。
【００２８】
本発明では、既存の実エントリの間に新規エントリを追加する場合には、追加後に新規エントリの直前または直後になる既存の実エントリから最も近い空きエントリまでのエントリデータを、新規エントリも含めて書き換えるため、書き換える必要のあるエントリ数が少なくなり、書き換え時間を短くできる。
また、本発明では、既存の実エントリの間に新規エントリを追加する場合に書き換える部分を新規エントリの前方にするか後方にするか決定する際に、当該書き換える部分から空きエントリまでのエントリ数が少ない方を選択するため、より一層書き換え時間を短くできる。
また、その実現方法として、本発明では、テーブルの各エントリに、前方の空きエントリまでのエントリ数と後方の空きエントリまでのエントリ数をそれぞれ記憶させる領域を設けておき、これらのエントリ数に基づいて書き換える部分を前方にするか後方にするかを選択するため、単なる数値比較を行えば良く、この選択のために必要な処理又は回路を小さくすることができる。
【００２９】
さらに、本発明では、テーブルを初期的に作るときに空きエントリをテーブル全体に分散して配置するため、既存の実エントリの間に新規エントリを追加する場合に、最も近い空きエントリまでのエントリ数の平均値が小さくなり、従って、書き換える必要のあるエントリ数が少なくなり、平均書き換え時間を短くできる。
【図面の簡単な説明】
【図１】本発明の一実施形態における空きエントリの配備方法を、従来技術と比較して示した概略図であり、（ａ）は従来の配備方法、（ｂ）は同実施形態の配備方法を示す。
【図２】同実施形態において、既存の実エントリの間に新規エントリを追加する場合の例を示す概略図であり、（ａ）は追加前のテーブル、（ｂ）は追加後のテーブルを示す。
【図３】同実施形態において、既存の実エントリを削除する場合の例を示す概略図であり、（ａ）は削除前のテーブル、（ｂ）は削除後のテーブルを示す。
【図４】従来技術によるハードウェア構成であり、本発明が対象とするテーブル検索およびテーブル更新の回路を示すブロック図である。
【図１】
2004080714.tif 000003
【図２】
2004080714.tif 000004
【図３】
2004080714.tif 000005
【図４】
2004080714.tif 000006