(57)【特許請求の範囲】
【請求項１】
一意に識別可能な第１のアドレス情報で転送が行われる複数の第１のネットワークと、ネットワーク内でのみ一意に識別可能な第２のアドレス情報で転送が行われる第２のネットワークとに接続され、前記複数の第１のネットワークと第２のネットワークとの間でデータを転送するデータ転送装置であって、
第１のアドレス情報と、当該第１のアドレス情報に対応する前記第２のアドレス情報とを対応付けた変換情報を記憶する変換情報記憶手段と、
前記変換情報記憶手段が記憶する複数の変換情報に含まれる前記第１のアドレス情報を数値で示した場合、当該数値の値の大きさの順に前記変換情報を参照できるようにする第１の順序情報を記憶する第１の順序情報記憶手段と、
前記変換情報記憶手段が記憶する複数の変換情報に含まれる前記第２のアドレス情報を数値で示した場合、当該数値の値の大きさの順に前記変換情報を参照できるようにする第２の順序情報を記憶する第２の順序情報記憶手段と、
前記複数の第１のネットワークのいずれか１つからデータを受信した場合、前記データに含まれる送信先を示す第１のアドレス情報から当該第１のアドレス情報を含む検索キー情報を生成し、前記第１の順序情報記憶手段が記憶する第１の順序情報及び前記検索キー情報に基づいて、二分探索法にて前記変換情報記憶手段から前記検索キー情報を含む変換情報を検索し、検索した変換情報に含まれる第２のアドレス情報を前記変換情報記憶手段から読み出して出力する第１の検索手段と、
前記第１の検索手段が出力した第２のアドレス情報で、前記データの送信先を書き換えて第２のネットワークへ転送する第１の転送手段と、
前記第２のネットワークからデータを受信した場合、前記データに含まれる送信先を示す第２のアドレス情報から当該第２のアドレス情報を含む検索キー情報を生成し、前記第２の順序情報記憶手段が記憶する第２の順序情報及び前記検索キー情報に基づいて、二分探索法にて前記変換情報記憶手段から前記検索キー情報を含む変換情報を検索し、検索した変換情報に含まれる第１のアドレス情報を前記変換情報記憶手段から読み出して出力する第２の検索手段と、
前記第２の検索手段が出力した第１のアドレス情報で、前記データの送信元を書き換えて第１のネットワークへ転送する第２の転送手段と、
を備えたことを特徴とするデータ転送装置。
【請求項２】
前記変換情報記憶手段が記憶する変換情報は、前記第１のＩＰアドレスと、前記第１のポート番号と、前記第２のＩＰアドレスと、前記第２のポート番号と、前記プロトコル番号とを含み、
前記第１のアドレス情報は、前記第１のＩＰアドレスと、前記第１のポート番号とを組
み合わせた情報であり、
前記第２のアドレス情報は、前記第２のＩＰアドレスと、前記第２のポート番号とを組
み合わせた情報であり、
前記検索キー情報は、前記第１のＩＰアドレスと、前記第１のポート番号と、前記プロ
トコル番号とを組み合わせた情報、あるいは前記第２のＩＰアドレスと、前記第２のポー
ト番号と前記プロトコル番号とを組み合わせた情報であり、
前記第１の順序情報は、
前記変換情報記憶手段が記憶する複数の変換情報に含まれる前記第１のアドレス情報と
前記プロトコル番号とを組み合わせた情報を数値で表した場合、当該数値の値の大きさの
順に前記変換情報を参照できるようにし、
前記第２の順序情報は、
前記変換情報記憶手段が記憶する複数の変換情報に含まれる前記第２のアドレス情報と
前期プロトコル番号とを組み合わせた情報を数値で表した場合、当該数値の値の大きさの
順に前記変換情報を参照できるようにする
ことを特徴とする請求項１に記載のデータ転送装置。
【請求項３】
受信するデータに含まれる送信先あるいは送信元のアドレス情報を他のアドレス情報へ変換して転送するデータ転送装置に具備されるアドレス情報検索回路であって、
アドレス情報と、当該アドレス情報に対応する前記他のアドレス情報とを対応付けた所定の個数の変換情報を、前記アドレス情報が示す数値が大きい順に記憶する記憶手段と、
一定周期でクロックを生成するクロック生成手段と、
前記アドレス情報を含む検索キー情報を入力する入力手段と、
最初のクロックにて、前記所定の個数の中央値が記録され、クロック周期ごとに内部に記憶している情報を出力する第１のレジスタと、
最初のクロックにて、零の値が記録され、クロック周期ごとに内部に記憶している情報を出力する第２のレジスタと、
最初のクロックにて、前記所定の個数の中央値を最大値とした場合の中央値が記録され、クロック周期ごとに、内部に記憶している情報を出力する第３のレジスタと、
クロック周期ごとに、前記第１のレジスタが出力する値と、前記第３のレジスタから出力される値との論理和を算出し、算出した論理和を第１の論理和として出力する第１の論理和演算手段と、
クロック周期ごとに、前記第２のレジスタから出力される値と、前記第３のレジスタから出力される値との論理和を算出し、算出した論理和を第２の論理和として出力する第２の論理和演算手段と、
クロック周期ごとに、前記第３のレジスタが出力する値を最大値とした場合の中央値を出力する中央値算出手段と、
クロック周期ごとに、前記記憶手段から第１のレジスタから出力される値に対応する順位の変換情報を読み出し、読み出した変換情報に含まれる検索対象部分を組み合わせた情報の数値が、前記入力手段が入力する前記検索キー情報が示す数値以下であるか否か、あるいは前記入力手段が入力する前記検索キー情報が示す数値に一致するか否かを判定する判定手段と、
クロック周期ごとに、前記第１の論理和演算手段が出力する第１の論理和、及び前記第２の論理和演算手段が出力する第２の論理和を記憶し、前記判定手段が、読み出した変換情報に含まれる検索対象部分を組み合わせた情報の数値が、前記入力手段が入力する前記検索キー情報が示す数値以下であると判定した場合、記憶している前記第１の論理和を前記第１のレジスタに記録し、前記判定手段が、前記変換情報に含まれる検索対象部分を組み合わせた情報の数値が、前記入力手段が入力する前記検索キー情報の数値以下でないと判定した場合、記憶している前記第２の論理和を前記第１のレジスタに記録する第１のセレクタと、
クロック周期ごとに、前記第１のレジスタから出力される値と、前記第２のレジスタから出力される値とを記憶し、前記判定手段が、読み出した変換情報に含まれる検索対象部分を組み合わせた情報の数値が、前記入力手段が入力する前記検索キー情報が示す数値以下であると判定した場合、記憶している前記第１のレジスタから出力される値を前記第２のレジスタに記録し、前記判定手段が、前記変換情報に含まれる検索対象部分を組み合わせた情報の数値が、前記入力手段が入力する前記検索キー情報が示す数値以下でないと判定した場合、記憶している前記第２のレジスタが出力した値を第２のレジスタに記録する第２のセレクタと、
クロック周期ごとに、前記中央値算出手段が算出した値を前記第３のレジスタに記録する第３のセレクタと、
前記判定手段が、前記変換情報に含まれる検索対象部分を組み合わせた情報の数値が、前記入力手段が入力する前記検索キー情報が示す数値に一致すると判定した場合、一致したことを示す情報とともに当該変換情報に含まれる他のアドレス情報を出力する出力手段と、
を備えたことを特徴とするアドレス情報検索回路。
【請求項４】
前記出力手段は、  前記所定の個数に応じた回数、クロック生成手段からクロックが生成された後に、前記判定手段が、前記変換情報に含まれる検索対象部分を組み合わせた情報の数値が、前記入力手段が入力する前記検索キー情報が示す数値が一致すると判定した場合、一致したことを示す情報とともに当該変換情報に含まれる他のアドレス情報を出力する
ことを特徴とする請求項３に記載のアドレス情報検索回路。
【請求項５】
前記記憶手段は、アドレス情報と、当該アドレス情報に対応する前記他のアドレス情報とを対応付けた所定の個数の変換情報を記憶する変換情報記憶手段と、
前記変換情報記憶手段が記憶する所定の個数の変換情報に含まれる前記アドレス情報を数値で示した場合に、当該数値の値の大きさの順に前記変換情報を参照できるようにする順序情報を記憶する順序情報記憶手段と、
を備え、
前記判定手段は、
クロック周期ごとに、前記順序情報記憶手段から順序情報を読み出し、読み出した順序情報と、前記記憶手段から第１のレジスタから出力される値とに基づいて、前記変換情報記憶手段から変換情報を読み出し、読み出した変換情報に含まれる検索対象部分を組み合わせた情報の数値が、前記入力手段が入力する前記検索キー情報が示す数値以下であるか否か、あるいは前記入力手段が入力する前記検索キー情報が示す数値に一致するか否かを判定する
ことを特徴とする請求項３に記載のアドレス情報検索回路。
【請求項６】
前記変換情報記憶手段が記憶する変換情報は、前記第１のＩＰアドレスと、前記第１のポート番号と、前記第２のＩＰアドレスと、前記第２のポート番号と、前記プロトコル番号とを含み、
前記アドレス情報は、前記第１のＩＰアドレスと、前記第１のポート番号とを組み合わせた情報であり、
前記他のアドレス情報は、前記第２のＩＰアドレスと、前記第２のポート番号とを組み合わせた情報であり、
前記検索キー情報及び前記変換情報に含まれる検索対象部分とは、前記第１のＩＰアドレスと、前記第１のポート番号と、前記プロトコル番号とを組み合わせた情報、あるいは前記第２のＩＰアドレスと、前記第２のポート番号と前記プロトコル番号とを組み合わせた情報であり、
前記順序情報は、
前記変換情報記憶手段が記憶する所定の個数の変換情報に含まれる前記アドレス情報及び前記プロトコル番号を組み合わせた情報を数値で示した場合に、当該数値の値の大きさの順に前記変換情報を参照できるようにする
ことを特徴とする請求項５に記載のアドレス情報検索回路。
【請求項７】
前記所定の個数は２のべき乗数であり、
前記記憶手段は、
前記変換情報記憶手段が記憶する前記変換情報の個数が前記所定の個数に満たない場合、２進数のビット列で数値で示した場合、全てのビットが１となる値の変換情報を前記所定の個数に対して不足する個数分、予め記憶し、前記変換情報記憶手段が記憶する前記変換情報の個数を所定の個数に合わせる
ことを特徴とする請求項３から６のいずれか１つに記載のアドレス情報検索回路。
【請求項８】
前記記憶手段は、
送信先のアドレス情報の変換の際に参照される変換情報と、送信元のアドレス情報の変換の際に参照される変換情報とを記憶することを特徴とする請求項３から７のいずれか１つに記載のアドレス情報検索回路。
【請求項９】
追加する変換情報を入力する変換情報追加手段を備え、
前記入力手段は、
前記変換情報追加手段が入力する変換情報に含まれるアドレス情報を入力し、
前記変換情報追加手段は、
前記所定の個数に応じた回数、クロック生成手段からクロックが生成された後に、前記第１のレジスタに記憶されている値を参照し、追加する変換情報を読み出した値に基づいて、前記記憶手段に記録する
ことを特徴とする請求項３から８のいずれか１つに記載のアドレス情報検索回路。
【請求項１０】
前記記憶手段は、
前記変換情報を記憶する第１の領域と、前記第１の領域と同じ内容の情報が記憶され、前記変換情報が追加あるいは削除される際に、書き換えが行われる第２の領域とを有し、
前記変換情報追加手段は、
入力する変換情報を前記第２の領域に追加して記録し、前記第２の領域の内容で、前記第１の領域を書き換える
ことを特徴とする請求項３から９のいずれか１つに記載のアドレス情報検索回路。
【請求項１１】
一意に識別可能な第１のアドレス情報で転送が行われる複数の第１のネットワークと、ネットワーク内でのみ一意に識別可能な第２のアドレス情報で転送が行われる第２のネットワークとに接続され、前記複数の第１のネットワークと第２のネットワークとの間でデータを転送し、第１のアドレス情報と、当該第１のアドレス情報に対応する前記第２のアドレス情報とを対応付けた変換情報を記憶する変換情報記憶手段と、前記変換情報記憶手段が記憶する複数の変換情報に含まれる前記第１のアドレス情報を数値で示した場合、当該数値の値の大きさの順に前記変換情報を参照できるようにする第１の順序情報を記憶する第１の順序情報記憶手段と、前記変換情報記憶手段が記憶する複数の変換情報に含まれる前記第２のアドレス情報を数値で示した場合、当該数値の値の大きさの順に前記変換情報を参照できるようにする第２の順序情報を記憶する第２の順序情報記憶手段と、を備えたデータ転送装置におけるアドレス情報検索方法であって、
前記複数の第１のネットワークのいずれか１つからデータを受信した場合、前記データに含まれる送信先を示す第１のアドレス情報から当該第１のアドレス情報を含む検索キー情報を生成するステップと、
前記第１の順序情報記憶手段が記憶する第１の順序情報及び前記検索キー情報に基づいて、二分探索法にて前記変換情報記憶手段から前記検索キー情報を含む変換情報を検索するステップと、
検索した変換情報に含まれる第２のアドレス情報を前記変換情報記憶手段から読み出して出力するステップと、
出力した第２のアドレス情報で、前記データの送信先を書き換えて第２のネットワークへ転送するステップと、
前記第２のネットワークからデータを受信した場合、前記データに含まれる送信先を示す第２のアドレス情報から当該第２のアドレス情報を含む検索キー情報を生成するステップと、
前記第２の順序情報記憶手段が記憶する第２の順序情報及び前記検索キー情報に基づいて、二分探索法にて前記変換情報記憶手段から前記検索キー情報を含む変換情報を検索するステップと、
検索した変換情報に含まれる第１のアドレス情報を前記変換情報記憶手段から読み出して出力するステップと、
出力した第１のアドレス情報で、前記データの送信元を書き換えて第１のネットワークへ転送するステップと、
を含むことを特徴とするアドレス情報検索方法。
【請求項１２】
受信するデータに含まれる送信先あるいは送信元のアドレス情報を他のアドレス情報へ変換して転送するデータ転送装置に具備され、一定周期でクロックを生成し、アドレス情報と、当該アドレス情報に対応する前記他のアドレス情報とを対応付けた所定の個数の変換情報を、前記アドレス情報が示す数値が大きい順に記憶する記憶手段を備えたアドレス情報検索回路におけるアドレス情報検索方法であって、
前記アドレス情報を含む検索キー情報を入力するステップと、
最初のクロックにて、前記所定の個数の中央値を第１のレジスタに記録するステップと、
最初のクロックにて、零の値を第２のレジスタに記録するステップと、
最初のクロックにて、前記所定の個数の中央値を最大値とした場合の中央値を第３のレジスタに記録するステップと、
クロック周期ごとに、前記第１のレジスタが出力する値と、前記第３のレジスタから出力される値との論理和を算出するステップと、
算出した論理和を第１の論理和として出力するステップと、
クロック周期ごとに、前記第２のレジスタから出力される値と、前記第３のレジスタから出力される値との論理和を算出し、算出した論理和を第２の論理和として出力するステップと、
クロック周期ごとに、前記第３のレジスタが出力する値を最大値とした場合の中央値を出力し第３のセレクタに記録するステップと、
クロック周期ごとに、前記記憶手段から第１のレジスタから出力される値に対応する順位の変換情報を読み出し、読み出した変換情報に含まれる検索対象部分を組み合わせた情報の数値が、入力される前記検索キー情報が示す数値以下であるか否か、あるいは前記入力手段が入力する前記検索キー情報が示す数値に一致するか否かを判定するステップと、
クロック周期ごとに、前記第１の論理和、及び前記第２の論理和を第１のセレクタに記録するステップと、
読み出した変換情報に含まれる検索対象部分を組み合わせた情報の数値が、入力される前記検索キー情報が示す数値以下であると判定した場合、前記第１のセレクタが前記第１の論理和を前記第１のレジスタに記録するステップと、
前記変換情報に含まれる検索対象部分を組み合わせた情報の数値が、入力される前記検索キー情報の数値以下でないと判定した場合、前記第１のセレクタが前記第２の論理和を前記第１のレジスタに記録するステップと、
クロック周期ごとに、前記第１のレジスタから出力される値と、前記第２のレジスタから出力される値とを第２のセレクタに記録するステップと、
読み出した変換情報に含まれる検索対象部分を組み合わせた情報の数値が、入力される前記検索キー情報が示す数値以下であると判定した場合、前記第２のセレクタが前記第１のレジスタから出力される値を前記第２のレジスタに記録するステップと、
前記変換情報に含まれる検索対象部分を組み合わせた情報の数値が、入力される前記検索キー情報が示す数値以下でないと判定した場合、前記第２のセレクタが前記第２のレジスタが出力した値を第２のレジスタに記録するステップと、
クロック周期ごとに、前記第３のセレクタが前記第３のレジスタが出力する値を最大値とした場合の中央値を前記第３のレジスタに記録するステップと、
前記変換情報に含まれる検索対象部分を組み合わせた情報の数値が、入力される前記検索キー情報が示す数値に一致すると判定した場合、一致したことを示す情報とともに当該変換情報に含まれる他のアドレス情報を出力するステップと、
を含むことを特徴とするアドレス情報検索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、転送されるデータに含まれるＩＰアドレス及びポート番号を変換する処理に用いて好適なデータ転送装置、アドレス情報検索回路、及びアドレス情報検索方法に関する。
【背景技術】
【０００２】
従来、グローバルＩＰアドレスでルーティングされるインターネットと、プライベートＩＰアドレスでルーティングされるイントラネット等を接続する場合、限られたグローバルＩＰアドレスを有効に利用するため、あるいはインターネットとイントラネットの間においてファイアウォールを構築するために、ＴＣＰやＵＤＰのパケットのＩＰアドレス及びポート番号を変換するＮＡＰＴ(Network Address Port Transport)という技術が知られている。
【０００３】
ＮＡＰＴは、ルータ等の内部に記憶される変換テーブルに基づいてＩＰアドレス及びポート番号の変換が行われ、例えば、インターネットからイントラネットの方向へ送信される場合、ルータは、パケットのヘッダの送信先のグローバルＩＰアドレスと送信先ポート番号の組み合わせのエントリを変換テーブルから検出し、検出したエントリに含まれるプライベートＩＰアドレスとポート番号との組み合わせで、当該パケットの送信先のグローバルＩＰアドレスと送信先ポート番号を書き換える。そして、ルータは書き換えたパケットをイントラネット側に送出し、当該パケットを端末に到達させる。
【０００４】
イントラネットからインターネットの方向へ送信される場合には、パケットのヘッダの送信元のプライベートＩＰアドレスと送信元のポート番号の組み合わせのエントリを変換テーブルから検出し、検出したエントリに含まれるグローバルＩＰアドレスとポート番号との組み合わせで、当該パケットの送信元のプライベートＩＰアドレスとポート番号を書き換え、インターネット側へ送出する。
【０００５】
ところで、変換テーブルに記憶されるエントリの数が少ない場合には、順次検索しても、転送時間に支障をきたすことがないが、エントリの数が非常に多い場合、転送時間に支障をきたすため、検索方法を工夫し、さらに、ハードウェア処理により検索時間を短縮することが望まれている。
【０００６】
検索方法としては、従来よりルーティングテーブルから送信先のＩＰアドレスを高速に検索する方法であるラディックスツリーを用いた二分探索方法などが一般的に知られており、この方法をＮＡＰＴにおける検索処理に適用することも可能である（非特許文献１参照）。
【非特許文献１】ゲーリ・Ｒ．ライト（著），Ｗ．リチャード  スティーヴンス（著），徳田  英幸（翻訳），戸辺  義人（翻訳），“詳解ＴＣＰ／ＩＰ  ＜Ｖｏｌ．２＞  実装”，ISBN4-89471-495-7,pp527-534，ピアソンエデュケーション
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかしながら、上記のラディックスツリーを用いた検索方法は、検索対象となるデータのパターンにより、早期に検索が終了する場合と、検索に長時間を要してしまう場合とがあり、ハードウェア処理で実現する場合、タイミング制御を行うことが困難であるという問題がある。
【０００８】
本発明は、上記問題を解決すべくなされたもので、その目的は、ＮＡＰＴにおける検索時間の短縮を可能とし、さらに、ハードウェア処理に適したＮＡＰＴの検索処理を実現することを可能とするデータ転送装置、アドレス情報検索回路、及びアドレス情報検索方法を提供することにある。
【課題を解決するための手段】
【０００９】
上記問題を解決するために、本発明は、一意に識別可能な第１のアドレス情報で転送が行われる複数の第１のネットワークと、ネットワーク内でのみ一意に識別可能な第２のアドレス情報で転送が行われる第２のネットワークとに接続され、前記複数の第１のネットワークと第２のネットワークとの間でデータを転送するデータ転送装置であって、第１のアドレス情報と、当該第１のアドレス情報に対応する前記第２のアドレス情報とを対応付けた変換情報を記憶する変換情報記憶手段と、前記変換情報記憶手段が記憶する複数の変換情報に含まれる前記第１のアドレス情報を数値で示した場合、当該数値の値の大きさの順に前記変換情報を参照できるようにする第１の順序情報を記憶する第１の順序情報記憶手段と、前記変換情報記憶手段が記憶する複数の変換情報に含まれる前記第２のアドレス情報を数値で示した場合、当該数値の値の大きさの順に前記変換情報を参照できるようにする第２の順序情報を記憶する第２の順序情報記憶手段と、前記複数の第１のネットワークのいずれか１つからデータを受信した場合、前記データに含まれる送信先を示す第１のアドレス情報から当該第１のアドレス情報を含む検索キー情報を生成し、前記第１の順序情報記憶手段が記憶する第１の順序情報及び前記検索キー情報に基づいて、二分探索法にて前記変換情報記憶手段から前記検索キー情報を含む変換情報を検索し、検索した変換情報に含まれる第２のアドレス情報を前記変換情報記憶手段から読み出して出力する第１の検索手段と、前記第１の検索手段が出力した第２のアドレス情報で、前記データの送信先を書き換えて第２のネットワークへ転送する第１の転送手段と、前記第２のネットワークからデータを受信した場合、前記データに含まれる送信先を示す第２のアドレス情報から当該第２のアドレス情報を含む検索キー情報を生成し、前記第２の順序情報記憶手段が記憶する第２の順序情報及び前記検索キー情報に基づいて、二分探索法にて前記変換情報記憶手段から前記検索キー情報を含む変換情報を検索し、検索した変換情報に含まれる第１のアドレス情報を前記変換情報記憶手段から読み出して出力する第２の検索手段と、前記第２の検索手段が出力した第１のアドレス情報で、前記データの送信元を書き換えて第１のネットワークへ転送する第２の転送手段と、を備えたことを特徴とするデータ転送装置である。
【００１２】
本発明は、上記に記載の発明において、前記変換情報記憶手段が記憶する変換情報は、前記第１のＩＰアドレスと、前記第１のポート番号と、前記第２のＩＰアドレスと、前記第２のポート番号と、前記プロトコル番号とを含み、前記第１のアドレス情報は、前記第１のＩＰアドレスと、前記第１のポート番号とを組み合わせた情報であり、前記第２のアドレス情報は、前記第２のＩＰアドレスと、前記第２のポート番号とを組み合わせた情報であり、前記検索キー情報は、前記第１のＩＰアドレスと、前記第１のポート番号と、前記プロトコル番号とを組み合わせた情報、あるいは前記第２のＩＰアドレスと、前記第２のポート番号と前記プロトコル番号とを組み合わせた情報であり、前記第１の順序情報は、前記変換情報記憶手段が記憶する複数の変換情報に含まれる前記第１のアドレス情報と前記プロトコル番号とを組み合わせた情報を数値で表した場合、当該数値の値の大きさの順に前記変換情報を参照できるようにし、前記第２の順序情報は、前記変換情報記憶手段が記憶する複数の変換情報に含まれる前記第２のアドレス情報と前期プロトコル番号とを組み合わせた情報を数値で表した場合、当該数値の値の大きさの順に前記変換情報を参照できるようにすることを特徴とする。
【００１３】
本発明は、受信するデータに含まれる送信先あるいは送信元のアドレス情報を他のアドレス情報へ変換して転送するデータ転送装置に具備されるアドレス情報検索回路であって、アドレス情報と、当該アドレス情報に対応する前記他のアドレス情報とを対応付けた所定の個数の変換情報を、前記アドレス情報が示す数値が大きい順に記憶する記憶手段と、一定周期でクロックを生成するクロック生成手段と、前記アドレス情報を含む検索キー情報を入力する入力手段と、最初のクロックにて、前記所定の個数の中央値が記録され、クロック周期ごとに内部に記憶している情報を出力する第１のレジスタと、最初のクロックにて、零の値が記録され、クロック周期ごとに内部に記憶している情報を出力する第２のレジスタと、最初のクロックにて、前記所定の個数の中央値を最大値とした場合の中央値が記録され、クロック周期ごとに、内部に記憶している情報を出力する第３のレジスタと、クロック周期ごとに、前記第１のレジスタが出力する値と、前記第３のレジスタから出力される値との論理和を算出し、算出した論理和を第１の論理和として出力する第１の論理和演算手段と、クロック周期ごとに、前記第２のレジスタから出力される値と、前記第３のレジスタから出力される値との論理和を算出し、算出した論理和を第２の論理和として出力する第２の論理和演算手段と、クロック周期ごとに、前記第３のレジスタが出力する値を最大値とした場合の中央値を出力する中央値算出手段と、クロック周期ごとに、前記記憶手段から第１のレジスタから出力される値に対応する順位の変換情報を読み出し、読み出した変換情報に含まれる検索対象部分を組み合わせた情報の数値が、前記入力手段が入力する前記検索キー情報が示す数値以下であるか否か、あるいは前記入力手段が入力する前記検索キー情報が示す数値に一致するか否かを判定する判定手段と、クロック周期ごとに、前記第１の論理和演算手段が出力する第１の論理和、及び前記第２の論理和演算手段が出力する第２の論理和を記憶し、前記判定手段が、読み出した変換情報に含まれる検索対象部分を組み合わせた情報の数値が、前記入力手段が入力する前記検索キー情報が示す数値以下であると判定した場合、記憶している前記第１の論理和を前記第１のレジスタに記録し、前記判定手段が、前記変換情報に含まれる検索対象部分を組み合わせた情報の数値が、前記入力手段が入力する前記検索キー情報の数値以下でないと判定した場合、記憶している前記第２の論理和を前記第１のレジスタに記録する第１のセレクタと、クロック周期ごとに、前記第１のレジスタから出力される値と、前記第２のレジスタから出力される値とを記憶し、前記判定手段が、読み出した変換情報に含まれる検索対象部分を組み合わせた情報の数値が、前記入力手段が入力する前記検索キー情報が示す数値以下であると判定した場合、記憶している前記第１のレジスタから出力される値を前記第２のレジスタに記録し、前記判定手段が、前記変換情報に含まれる検索対象部分を組み合わせた情報の数値が、前記入力手段が入力する前記検索キー情報が示す数値以下でないと判定した場合、記憶している前記第２のレジスタが出力した値を第２のレジスタに記録する第２のセレクタと、クロック周期ごとに、前記中央値算出手段が算出した値を前記第３のレジスタに記録する第３のセレクタと、前記判定手段が、前記変換情報に含まれる検索対象部分を組み合わせた情報の数値が、前記入力手段が入力する前記検索キー情報が示す数値に一致すると判定した場合、一致したことを示す情報とともに当該変換情報に含まれる他のアドレス情報を出力する出力手段と、を備えたことを特徴とするアドレス情報検索回路である。
【００１４】
本発明は、上記に記載の発明において、前記出力手段は、前記所定の個数に応じた回数、クロック生成手段からクロックが生成された後に、前記判定手段が、前記変換情報に含まれる検索対象部分を組み合わせた情報の数値が、前記入力手段が入力する前記検索キー情報が示す数値が一致すると判定した場合、一致したことを示す情報とともに当該変換情報に含まれる他のアドレス情報を出力することを特徴とする。
【００１５】
本発明は、上記に記載の発明において、前記記憶手段は、アドレス情報と、当該アドレス情報に対応する前記他のアドレス情報とを対応付けた所定の個数の変換情報を記憶する変換情報記憶手段と、前記変換情報記憶手段が記憶する所定の個数の変換情報に含まれる前記アドレス情報を数値で示した場合に、当該数値の値の大きさの順に前記変換情報を参照できるようにする順序情報を記憶する順序情報記憶手段と、を備え、前記判定手段は、クロック周期ごとに、前記順序情報記憶手段から順序情報を読み出し、読み出した順序情報と、前記記憶手段から第１のレジスタから出力される値とに基づいて、前記変換情報記憶手段から変換情報を読み出し、読み出した変換情報に含まれる検索対象部分を組み合わせた情報の数値が、前記入力手段が入力する前記検索キー情報が示す数値以下であるか否か、あるいは前記入力手段が入力する前記検索キー情報が示す数値に一致するか否かを判定することを特徴とする。
【００１６】
本発明は、上記に記載の発明において、前記変換情報記憶手段が記憶する変換情報は、前記第１のＩＰアドレスと、前記第１のポート番号と、前記第２のＩＰアドレスと、前記第２のポート番号と、前記プロトコル番号とを含み、前記アドレス情報は、前記第１のＩＰアドレスと、前記第１のポート番号とを組み合わせた情報であり、前記他のアドレス情報は、前記第２のＩＰアドレスと、前記第２のポート番号とを組み合わせた情報であり、前記検索キー情報及び前記変換情報に含まれる検索対象部分とは、前記第１のＩＰアドレスと、前記第１のポート番号と、前記プロトコル番号とを組み合わせた情報、あるいは前記第２のＩＰアドレスと、前記第２のポート番号と前記プロトコル番号とを組み合わせた情報であり、前記順序情報は、前記変換情報記憶手段が記憶する所定の個数の変換情報に含まれる前記アドレス情報及び前記プロトコル番号を組み合わせた情報を数値で示した場合に、当該数値の値の大きさの順に前記変換情報を参照できるようにすることを特徴とする。
【００１７】
本発明は、上記に記載の発明において、前記所定の個数は２のべき乗数であり、前記記憶手段は、前記変換情報記憶手段が記憶する前記変換情報の個数が前記所定の個数に満たない場合、２進数のビット列で数値で示した場合、全てのビットが１となる値の変換情報を前記所定の個数に対して不足する個数分、予め記憶し、前記変換情報記憶手段が記憶する前記変換情報の個数を所定の個数に合わせることを特徴とする。
【００１８】
本発明は、上記に記載の発明において、前記記憶手段は、送信先のアドレス情報の変換の際に参照される変換情報と、送信元のアドレス情報の変換の際に参照される変換情報とを記憶することを特徴とする。
【００１９】
本発明は、上記に記載の発明において、追加する変換情報を入力する変換情報追加手段を備え、前記入力手段は、前記変換情報追加手段が入力する変換情報に含まれるアドレス情報を入力し、前記変換情報追加手段は、前記所定の個数に応じた回数、クロック生成手段からクロックが生成された後に、前記第１のレジスタに記憶されている値を参照し、追加する変換情報を読み出した値に基づいて、前記記憶手段に記録することを特徴とする。
【００２０】
本発明は、上記に記載の発明において、前記記憶手段は、前記変換情報を記憶する第１の領域と、前記第１の領域と同じ内容の情報が記憶され、前記変換情報が追加あるいは削除される際に、書き換えが行われる第２の領域とを有し、前記変換情報追加手段は、入力する変換情報を前記第２の領域に追加して記録し、前記第２の領域の内容で、前記第１の領域を書き換えることを特徴とする。
【００２１】
本発明は、一意に識別可能な第１のアドレス情報で転送が行われる複数の第１のネットワークと、ネットワーク内でのみ一意に識別可能な第２のアドレス情報で転送が行われる第２のネットワークとに接続され、前記複数の第１のネットワークと第２のネットワークとの間でデータを転送し、第１のアドレス情報と、当該第１のアドレス情報に対応する前記第２のアドレス情報とを対応付けた変換情報を記憶する変換情報記憶手段と、前記変換情報記憶手段が記憶する複数の変換情報に含まれる前記第１のアドレス情報を数値で示した場合、当該数値の値の大きさの順に前記変換情報を参照できるようにする第１の順序情報を記憶する第１の順序情報記憶手段と、前記変換情報記憶手段が記憶する複数の変換情報に含まれる前記第２のアドレス情報を数値で示した場合、当該数値の値の大きさの順に前記変換情報を参照できるようにする第２の順序情報を記憶する第２の順序情報記憶手段と、を備えたデータ転送装置におけるアドレス情報検索方法であって、前記複数の第１のネットワークのいずれか１つからデータを受信した場合、前記データに含まれる送信先を示す第１のアドレス情報から当該第１のアドレス情報を含む検索キー情報を生成するステップと、前記第１の順序情報記憶手段が記憶する第１の順序情報及び前記検索キー情報に基づいて、二分探索法にて前記変換情報記憶手段から前記検索キー情報を含む変換情報を検索するステップと、検索した変換情報に含まれる第２のアドレス情報を前記変換情報記憶手段から読み出して出力するステップと、出力した第２のアドレス情報で、前記データの送信先を書き換えて第２のネットワークへ転送するステップと、前記第２のネットワークからデータを受信した場合、前記データに含まれる送信先を示す第２のアドレス情報から当該第２のアドレス情報を含む検索キー情報を生成するステップと、前記第２の順序情報記憶手段が記憶する第２の順序情報及び前記検索キー情報に基づいて、二分探索法にて前記変換情報記憶手段から前記検索キー情報を含む変換情報を検索するステップと、検索した変換情報に含まれる第１のアドレス情報を前記変換情報記憶手段から読み出して出力するステップと、出力した第１のアドレス情報で、前記データの送信元を書き換えて第１のネットワークへ転送するステップと、を含むことを特徴とするアドレス情報検索方法である。
【００２２】
本発明は、受信するデータに含まれる送信先あるいは送信元のアドレス情報を他のアドレス情報へ変換して転送するデータ転送装置に具備され、一定周期でクロックを生成し、アドレス情報と、当該アドレス情報に対応する前記他のアドレス情報とを対応付けた所定の個数の変換情報を、前記アドレス情報が示す数値が大きい順に記憶する記憶手段を備えたアドレス情報検索回路におけるアドレス情報検索方法であって、前記アドレス情報を含む検索キー情報を入力するステップと、最初のクロックにて、前記所定の個数の中央値を第１のレジスタに記録するステップと、最初のクロックにて、零の値を第２のレジスタに記録するステップと、最初のクロックにて、前記所定の個数の中央値を最大値とした場合の中央値を第３のレジスタに記録するステップと、クロック周期ごとに、前記第１のレジスタが出力する値と、前記第３のレジスタから出力される値との論理和を算出するステップと、算出した論理和を第１の論理和として出力するステップと、クロック周期ごとに、前記第２のレジスタから出力される値と、前記第３のレジスタから出力される値との論理和を算出し、算出した論理和を第２の論理和として出力するステップと、クロック周期ごとに、前記第３のレジスタが出力する値を最大値とした場合の中央値を出力し第３のセレクタに記録するステップと、クロック周期ごとに、前記記憶手段から第１のレジスタから出力される値に対応する順位の変換情報を読み出し、読み出した変換情報に含まれる検索対象部分を組み合わせた情報の数値が、入力される前記検索キー情報が示す数値以下であるか否か、あるいは前記入力手段が入力する前記検索キー情報が示す数値に一致するか否かを判定するステップと、クロック周期ごとに、前記第１の論理和、及び前記第２の論理和を第１のセレクタに記録するステップと、読み出した変換情報に含まれる検索対象部分を組み合わせた情報の数値が、入力される前記検索キー情報が示す数値以下であると判定した場合、前記第１のセレクタが前記第１の論理和を前記第１のレジスタに記録するステップと、前記変換情報に含まれる検索対象部分を組み合わせた情報の数値が、入力される前記検索キー情報の数値以下でないと判定した場合、前記第１のセレクタが前記第２の論理和を前記第１のレジスタに記録するステップと、クロック周期ごとに、前記第１のレジスタから出力される値と、前記第２のレジスタから出力される値とを第２のセレクタに記録するステップと、読み出した変換情報に含まれる検索対象部分を組み合わせた情報の数値が、入力される前記検索キー情報が示す数値以下であると判定した場合、前記第２のセレクタが前記第１のレジスタから出力される値を前記第２のレジスタに記録するステップと、前記変換情報に含まれる検索対象部分を組み合わせた情報の数値が、入力される前記検索キー情報が示す数値以下でないと判定した場合、前記第２のセレクタが前記第２のレジスタが出力した値を第２のレジスタに記録するステップと、クロック周期ごとに、前記第３のセレクタが前記第３のレジスタが出力する値を最大値とした場合の中央値を前記第３のレジスタに記録するステップと、前記変換情報に含まれる検索対象部分を組み合わせた情報の数値が、入力される前記検索キー情報が示す数値に一致すると判定した場合、一致したことを示す情報とともに当該変換情報に含まれる他のアドレス情報を出力するステップと、を含むことを特徴とするアドレス情報検索方法である。
【発明の効果】
【００２３】
この発明によれば、データ転送装置は、第１のアドレス情報と、当該第１のアドレス情報に対応する第２のアドレス情報とを対応付けた変換情報を記憶する変換情報記憶手段と、変換情報記憶手段が記憶する複数の変換情報に含まれる第１のアドレス情報を数値で示した場合、当該数値の値の大きさの順に変換情報を参照できるようにする第１の順序情報を記憶する第１の順序情報記憶手段と、変換情報記憶手段が記憶する複数の変換情報に含まれる第２のアドレス情報を数値で示した場合、当該数値の値の大きさの順に変換情報を参照できるようにする第２の順序情報を記憶する第２の順序情報記憶手段と、複数の第１のネットワークのいずれか１つからデータを受信した場合、データに含まれる送信先を示す第１のアドレス情報から当該第１のアドレス情報を含む検索キー情報を生成し、第１の順序情報記憶手段が記憶する第１の順序情報及び検索キー情報に基づいて、変換情報記憶手段から検索キー情報を含む変換情報を検索し、検索した変換情報に含まれる第２のアドレス情報を変換情報記憶手段から読み出して出力する第１の検索手段と、第１の検索手段が出力した第２のアドレス情報で、データの送信先を書き換えて第２のネットワークへ転送する第１の転送手段と、第２のネットワークからデータを受信した場合、データに含まれる送信先を示す第２のアドレス情報から当該第２のアドレス情報を含む検索キー情報を生成し、第２の順序情報記憶手段が記憶する第２の順序情報及び検索キー情報に基づいて、変換情報記憶手段から検索キー情報を含む変換情報を検索し、検索した変換情報に含まれる第１のアドレス情報を変換情報記憶手段から読み出して出力する第２の検索手段と、第２の検索手段が出力した第１のアドレス情報で、データの送信元を書き換えて第１のネットワークへ転送する第２の転送手段と、を備えた構成とした。これにより、第１の順序情報記憶手段と、第２の順序情報記憶手段とを参照することで、値の大きさの順に検索が行えることから、ＮＡＰＴにおける検索時間の短縮を可能とすることができる。
【００２４】
また、本発明によれば、データ転送装置において第１の検索手段は、読み出した第１の順序情報及び検索キー情報に基づいて、二分探索法にて変換情報記憶手段からから検索キー情報を含む変換情報を検索する構成とした。これにより、第１の順序情報に基づいて二分探索を行い、二分探索による検索時間内で第１のアドレス情報を検索することが可能となる。
【００２５】
また、本発明によれば、データ転送装置において第２の検索手段は、読み出した第２の順序情報及び検索キー情報に基づいて、二分探索法にて変換情報記憶手段からから検索キー情報を含む変換情報を検索する構成とした。これにより、第２の順序情報に基づいて二分探索を行い、二分探索による検索時間内で第２のアドレス情報を検索することが可能となる。
【００２６】
また、本発明によれば、データ転送装置において変換情報記憶手段が記憶する変換情報は、第１のＩＰアドレスと、第１のポート番号と、第２のＩＰアドレスと、第２のポート番号と、プロトコル番号とを含み、第１のアドレス情報は、第１のＩＰアドレスと、第１のポート番号とを組み合わせた情報であり、第２のアドレス情報は、第２のＩＰアドレスと、第２のポート番号とを組み合わせた情報であり、検索キー情報は、第１のＩＰアドレスと、第１のポート番号と、プロトコル番号とを組み合わせた情報、あるいは第２のＩＰアドレスと、第２のポート番号とプロトコル番号とを組み合わせた情報であり、第１の順序情報は、変換情報記憶手段が記憶する複数の変換情報に含まれる第１のアドレス情報とプロトコル番号とを組み合わせた情報を数値で表した場合、当該数値の値の大きさの順に変換情報を参照できるようにし、第２の順序情報は、変換情報記憶手段が記憶する複数の変換情報に含まれる第２のアドレス情報と前期プロトコル番号とを組み合わせた情報を数値で表した場合、当該数値の値の大きさの順に変換情報を参照できるようにする構成とした。これにより、ＩＰアドレスとポート番号に対して変換を行うＮＡＰＴ処理が可能となる。
【００２７】
また、本発明によれば、アドレス情報検索回路は、アドレス情報と、当該アドレス情報に対応する他のアドレス情報とを対応付けた所定の個数の変換情報を、アドレス情報が示す数値が大きい順に記憶する記憶手段と、一定周期でクロックを生成するクロック生成手段と、アドレス情報を含む検索キー情報を入力する入力手段と、最初のクロックにて、所定の個数の中央値が記録され、クロック周期ごとに内部に記憶している情報を出力する第１のレジスタと、最初のクロックにて、零の値が記録され、クロック周期ごとに内部に記憶している情報を出力する第２のレジスタと、最初のクロックにて、所定の個数の中央値を最大値とした場合の中央値が記録され、クロック周期ごとに、内部に記憶している情報を出力する第３のレジスタと、クロック周期ごとに、第１のレジスタが出力する値と、第３のレジスタから出力される値との論理和を算出し、算出した論理和を第１の論理和として出力する第１の論理和演算手段と、クロック周期ごとに、第２のレジスタから出力される値と、第３のレジスタから出力される値との論理和を算出し、算出した論理和を第２の論理和として出力する第２の論理和演算手段と、クロック周期ごとに、第３のレジスタが出力する値を最大値とした場合の中央値を出力する中央値算出手段と、クロック周期ごとに、記憶手段から第１のレジスタから出力される値に対応する順位の変換情報を読み出し、読み出した変換情報に含まれる検索対象部分を組み合わせた情報の数値が、入力手段が入力する検索キー情報が示す数値以下であるか否か、あるいは入力手段が入力する検索キー情報が示す数値に一致するか否かを判定する判定手段と、クロック周期ごとに、第１の論理和演算手段が出力する第１の論理和、及び第２の論理和演算手段が出力する第２の論理和を記憶し、判定手段が、読み出した変換情報に含まれる検索対象部分を組み合わせた情報の数値が、入力手段が入力する検索キー情報が示す数値以下であると判定した場合、記憶している第１の論理和を第１のレジスタに記録し、判定手段が、変換情報に含まれる検索対象部分を組み合わせた情報の数値が、入力手段が入力する検索キー情報の数値以下でないと判定した場合、記憶している第２の論理和を第１のレジスタに記録する第１のセレクタと、クロック周期ごとに、第１のレジスタから出力される値と、第２のレジスタから出力される値とを記憶し、判定手段が、読み出した変換情報に含まれる検索対象部分を組み合わせた情報の数値が、入力手段が入力する検索キー情報が示す数値以下であると判定した場合、記憶している第１のレジスタから出力される値を第２のレジスタに記録し、判定手段が、変換情報に含まれる検索対象部分を組み合わせた情報の数値が、入力手段が入力する検索キー情報が示す数値以下でないと判定した場合、記憶している第２のレジスタが出力した値を第２のレジスタに記録する第２のセレクタと、クロック周期ごとに、中央値算出手段が算出した値を第３のレジスタに記録する第３のセレクタと、判定手段が、変換情報に含まれる検索対象部分を組み合わせた情報の数値が、入力手段が入力する検索キー情報が示す数値に一致すると判定した場合、一致したことを示す情報とともに当該変換情報に含まれる他のアドレス情報を出力する出力手段とを備える構成とした。これにより、ハードウェアによる並列処理にてＮＡＰＴ処理のアドレス情報の検索処理を実現し、処理時間の短縮を図ることが可能となる。
【００２８】
また、本発明によれば、アドレス情報検索回路において出力手段は、所定の個数に応じた回数、クロック生成手段からクロックが生成された後に、判定手段が、変換情報に含まれる検索対象部分を組み合わせた情報の数値が、入力手段が入力する検索キー情報が示す数値が一致すると判定した場合、一致したことを示す情報とともに当該変換情報に含まれる他のアドレス情報を出力する構成とした。これにより、所定の個数に応じた回数、二分探索処理を行った後に、検索対象のアドレス情報を検索することが可能となり、一定の時間で検索処理を終了させることが可能となる。
【００２９】
また、本発明によれば、アドレス情報検索回路における記憶手段は、アドレス情報と、当該アドレス情報に対応する他のアドレス情報とを対応付けた所定の個数の変換情報を記憶する変換情報記憶手段と、変換情報記憶手段が記憶する所定の個数の変換情報に含まれるアドレス情報を数値で示した場合に、当該数値の値の大きさの順に変換情報を参照できるようにする順序情報を記憶する順序情報記憶手段と、を備え、判定手段は、クロック周期ごとに、順序情報記憶手段から順序情報を読み出し、読み出した順序情報と、記憶手段から第１のレジスタから出力される値とに基づいて、変換情報記憶手段から変換情報を読み出し、読み出した変換情報に含まれる検索対象部分を組み合わせた情報の数値が、入力手段が入力する検索キー情報が示す数値以下であるか否か、あるいは入力手段が入力する検索キー情報が示す数値に一致するか否かを判定する構成とした。これにより、アドレス情報の対応関係を示したいわゆるＮＡＰＴテーブルである変換情報記憶手段のデータ構成はそのままにして、順序情報記憶手段により並べ替えを行うことを可能とすることができる。
【００３０】
また、本発明によれば、アドレス情報検索回路における変換情報記憶手段が記憶する変換情報は、第１のＩＰアドレスと、第１のポート番号と、第２のＩＰアドレスと、第２のポート番号と、プロトコル番号とを含み、アドレス情報は、第１のＩＰアドレスと、第１のポート番号とを組み合わせた情報であり、他のアドレス情報は、第２のＩＰアドレスと、第２のポート番号とを組み合わせた情報であり、検索キー情報及び変換情報に含まれる検索対象部分とは、第１のＩＰアドレスと、第１のポート番号と、プロトコル番号とを組み合わせた情報、あるいは第２のＩＰアドレスと、第２のポート番号とプロトコル番号とを組み合わせた情報であり、順序情報は、変換情報記憶手段が記憶する所定の個数の変換情報に含まれるアドレス情報及びプロトコル番号を組み合わせた情報を数値で示した場合に、当該数値の値の大きさの順に変換情報を参照できるようにする構成とした。これにより、ＩＰアドレスとポート番号に対して変換を行うＮＡＰＴ処理が可能となる。
【００３１】
また、本発明によれば、アドレス情報検索回路における所定の個数は２のべき乗数であり、記憶手段は、変換情報記憶手段が記憶する変換情報の個数が所定の個数に満たない場合、２進数のビット列で数値で示した場合、全てのビットが１となる値の変換情報を所定の個数に対して不足する個数分、予め記憶し、変換情報記憶手段が記憶する変換情報の個数を所定の個数に合わせる構成とした。これにより、変更情報が所定の個数存在しない場合であっても、ハードウェア構成において、変更情報の数を所定の個数に保つことができ、所定の個数に応じた回数、二分探索処理を行うことで、アドレス情報を検索することができる。
【００３２】
また、本発明によれば、アドレス情報検索回路における記憶手段は、送信先のアドレス情報の変換の際に参照される変換情報と、送信元のアドレス情報の変換の際に参照される変換情報とを記憶することを特徴とする構成とした。これにより、送信先のアドレス情報を変換する処理と、送信元のアドレス情報を変換する処理とを実現することができる。
【００３３】
また、本発明によれば、アドレス情報検索回路は、追加する変換情報を入力する変換情報追加手段を備え、入力手段は、変換情報追加手段が入力する変換情報に含まれるアドレス情報を入力し、変換情報追加手段は、所定の個数に応じた回数、クロック生成手段からクロックが生成された後に、第１のレジスタに記憶されている値を参照し、追加する変換情報を読み出した値に基づいて、記憶手段に記録する構成とした。これにより、記憶手段に、大きさの順に従って変換情報を追加することが可能となる。
【００３４】
また、本発明によれば、アドレス情報検索回路における記憶手段は、変換情報を記憶する第１の領域と、第１の領域と同じ内容の情報が記憶され、変換情報が追加あるいは削除される際に、書き換えが行われる第２の領域とを有し、変換情報追加手段は、入力する変換情報を第２の領域に追加して記録し、第２の領域の内容で、第１の領域を書き換える構成とした。これにより、変換情報が追加あるいは削除される際であっても、第１の領域を参照して検索処理を行うことができ、検索処理の終了時などに、第２の領域の内容で、第１の領域を書き換えることで短時間で変換情報の追加あるいは削除を行うことが可能となる。
【発明を実施するための最良の形態】
【００３５】
以下、本発明の一実施形態を図面を参照して説明する。
図１は、本実施形態によるデータ転送装置１の内部構成を示した概略ブロック図である。データ転送装置１は、ＩＰ(Internet Protocol)ネットワークにおけるルータ等のＩＰパケットを転送する装置である。データ転送装置１において、接続部１１は、ＷＡＮ(Wide Area Network)に接続され、ＷＡＮを介してデータの送受信を行う。接続部１３は、ＬＡＮ(Local Area Network)に接続され、ＬＡＮを介してデータの送受信を行う。
【００３６】
ここで、ＷＡＮは、例えば、インターネット等であり、当該ＷＡＮに接続する端末等には、一意に識別可能なグローバルＩＰアドレスが付与されている。また、ＬＡＮは、例えば、イントラネット等であり、当該ＬＡＮに属する端末には、当該ＬＡＮ内のみで一意に識別可能なプライベートＩＰアドレスが付与されている。
【００３７】
アドレス情報検索回路２０は、受信したＩＰパケットに含まれる変換対象のアドレス情報に基づいて、当該アドレス情報に対応するアドレス情報を検索して出力する。ここで、アドレス情報とは、ＩＰアドレスやポート番号のそれぞれや、ＩＰアドレスとポート番号とを組み合わせた情報を示している。
【００３８】
変換部２３は、ＷＡＮから受信したＩＰパケットの送信先のアドレス情報を、アドレス情報検索回路２０から出力されるプライベートＩＰアドレスとポート番号へ変換、すなわちヘッダを書き換えて経路検索部１２に出力する。
【００３９】
変換部２４は、ＬＡＮから受信したＩＰパケットが経路検索部１２に入力され、経路検索部１２により出力されたＩＰパケットの送信元のアドレス情報を、アドレス情報検索回路２０から出力されるグローバルＩＰアドレスとポート番号へ変換し、変換したＩＰパケットを接続部１１に出力する。ここで、送信元のＩＰアドレスをグローバルＩＰアドレスへ変換する理由は、例えば、当該ＩＰパケットを受信した端末が、送信元のアドレス情報を参照して返信のためのデータを送信する場合などのためである。
【００４０】
経路検索部１２は、内部に経路情報テーブルを記憶しており、入力されるＩＰパケットの送信先を参照して、ＩＰパケットを送出する接続部１１、１３を経路情報テーブルから検出し、検出した接続部１１、１３に当該ＩＰパケットを送出させる。
【００４１】
アドレス情報検索回路２０において、検索部２２は、接続部１１がＷＡＮから受信したＩＰパケットであってＬＡＮに転送されるべきＩＰパケットが入力され、入力されるＩＰパケットのヘッダに含まれる送信先のＩＰアドレス、ポート番号、ＯＳＩ(Open Systems Interconnection)参照モデルの第４層のプロトコルのプロトコルタイプを示すプロトコル番号を読み出す。ここで、第４層のプロトコルとは、ＩＰプロトコルの１階層上のＴＣＰ(Transmission Control Protocol)や、ＵＤＰ（User Datagram Protocol）などであり、ＴＣＰの場合、プロトコル番号には６が割り当てられており、ＵＤＰの場合には１７が割り当てられている。
【００４２】
また、検索部２２は、後述する順序テーブル２６と、ＷＡＮ側のアドレス情報と、ＬＡＮ側のアドレス情報との対応関係を示したＮＡＰＴテーブル２１とを参照し、二分探索により、ＮＡＰＴテーブル２１から、読み出したＩＰアドレス、ポート番号、プロトコル番号の組み合わせを検索キー情報として、当該検索キー情報に一致するエントリを検索し、検索したエントリに記録されているアドレス情報、すなわちプライベートＩＰアドレスと、当該プライベートＩＰアドレスに対応するポート番号とを読み出す。
【００４３】
検索部２５は、接続部１３がＬＡＮから受信したＩＰパケットであってＷＡＮへ転送されるべきＩＰパケットが入力され、入力されるＩＰパケットのヘッダに含まれる送信元のＩＰアドレス、ポート番号、プロトコル番号を読み出す。また、検索部２５は、後述する順序テーブル２７と、ＮＡＰＴテーブル２１とを参照し、二分探索により、ＮＡＰＴテーブル２１から、読み出したＩＰアドレス、ポート番号、プロトコル番号の組み合わせを検索キー情報として、当該検索キー情報に一致するエントリを検索し、検索したエントリに記録されているグローバルＩＰアドレスと、当該グローバルＩＰアドレスに対応するポート番号とを読み出す。
【００４４】
なお、図１では、ＷＡＮに接続される接続部１１と、ＬＡＮに接続される接続部１３との２つの接続部のみを示したが、ＷＡＮに接続される接続部１１は複数存在しているようにしてもよい。
【００４５】
次に、図２を参照して、ＮＡＰＴテーブル２１及び順序テーブル２６、２７のデータ構成、及び上述した検索部２２及び２４による検索の手順について説明する。
【００４６】
ＮＡＰＴテーブル２１は、「ｅｎｔｒｙ」と、「ｇＡｄｄｒ：ｇｌｏｂａｌ  Ａｄｄｒｅｓｓ」と、「ｇＰｏｒｔ＃」と、「ｌＡｄｄｒ：Ｌｏｃａｌ  Ａｄｄｒｅｓｓ」と、「ｌＰｏｒｔ＃」と、「Ｐｒｏｔｏｃｏｌ＃」の項目を有している。「ｅｎｔｒｙ」には、ＮＡＰＴテーブル２１に含まれる各エントリを一意に識別できるエントリ番号が記録される。「ｇＡｄｄｒ」には、グローバルＩＰアドレスが記録される。「ｇＰｏｒｔ＃」には、グローバルＩＰアドレスに対応するポート番号が記録される。「ｌＡｄｄｒ」には、グローバルＩＰアドレスに対応するプライベートＩＰアドレスが記録される。「ｌＰｏｒｔ＃」には、プライベートＩＰアドレスに対応するポート番号が記録される。「Ｐｒｏｔｏｃｏｌ＃」には、プロトコル番号が記録される。
【００４７】
順序テーブル２６は、「ｏｒｄｅｒ」と「ｅｎｔｒｙ」の項目を有しており、「ｏｒｄｅｒ」には、０から順に番号が付与される。「ｅｎｔｒｙ」には、ＮＡＰＴテーブル２１の「ｇＡｄｄｒ」（３２ビット）と「ｇＰｏｒｔ＃」（１６ビット）と「Ｐｒｏｔｏｃｏｌ＃」（１６ビット）とを組み合わせた６４ビットを１つの変数として、当該変数が昇べきの順に並べ替えた場合のＮＡＰＴテーブル２１のエントリ番号の順序が記録される。
【００４８】
順序テーブル２７は、順序テーブル２６と同じく「ｏｒｄｅｒ」と「ｅｎｔｒｙ」の項目を有しており、「ｏｒｄｅｒ」には、０から順に番号が付与される。「ｅｎｔｒｙ」には、ＮＡＰＴテーブル２１の「ｌＡｄｄｒ」（３２ビット）と「ｌＰｏｒｔ＃」（１６ビット）と「Ｐｒｏｔｏｃｏｌ＃」（１６ビット）とを組み合わせた６４ビットを１つの変数として、当該変数が昇べきの順に並べ替えた場合のＮＡＰＴテーブル２１のエントリ番号の順序が記録される。
【００４９】
従来のＮＡＰＴにおける検索は、ＷＡＮから受信したパケットの送信先のＩＰアドレス及びポート番号を変換する場合、まず、ＷＡＮから受信したＩＰパケットの送信先のＩＰアドレス及びポート番号、並びにプロトコル番号を読み出し、読み出したＩＰアドレスとポート番号とプロトコル番号を検索キー情報（ｋｅｙｗ）として、ＮＡＰＴテーブル２１の「ｇＡｄｄｒ」及び「ｇＰｏｒｔ＃」と「Ｐｒｏｔｏｃｏｌ＃」の項目に対して、検索キー情報と同じ組み合わせを検索する。そして、検索の結果、同じ組み合わせの「ｇＡｄｄｒ」と「ｇＰｏｒｔ＃」と「Ｐｒｏｔｏｃｏｌ＃」のエントリが存在した場合、当該エントリに含まれる「ｌＡｄｄｒ」と「ｌＰｏｒｔ＃」の項目に記録されているプライベートＩＰアドレスとポート番号を読み出し、検索結果（ｒｅｓｗ）として出力する。
【００５０】
また、逆に、ＬＡＮから受信したパケットの送信元のＩＰアドレス及びポート番号を変換する場合、まず、ＬＡＮから受信したＩＰパケットの送信元のＩＰアドレス及びポート番号、並びにプロトコル番号を読み出し、読み出したＩＰアドレスとポート番号とプロトコル番号を検索キー情報（ｋｅｙｌ）として、ＮＡＰＴテーブル２１の「ｌＡｄｄｒ」及び「ｌＰｏｒｔ＃」と「Ｐｒｏｔｏｃｏｌ＃」の項目に対して、検索キー情報と同じ組み合わせを検索する。そして、検索の結果、同じ組み合わせの「ｌＡｄｄｒ」と「ｌＰｏｒｔ＃」と「Ｐｒｏｔｏｃｏｌ＃」のエントリが存在した場合、当該エントリに含まれえる「ｇＡｄｄｒ」と「ｇＰｏｒｔ＃」の項目に記録されているプライベートＩＰアドレスとポート番号を読み出し、検索結果（ｒｅｓｌ）として出力する。
【００５１】
しかし、ＮＡＰＴテーブル２１は、通常のグローバルＩＰアドレスとポート番号の組みと、プライベートＩＰアドレスとポート番号の組みの対応関係を記憶させておくためのテーブルであるため、最初のエントリから最後のエントリまで検索を行わないと結果が得られない場合がある。
【００５２】
そこで、本実施形態では、順序テーブル２６及び順序テーブル２７を備えることにより、それぞれの検索キー情報（ｋｅｙｗ、ｋｅｙｌ）で検索を行う場合に、検索キー情報に対応する変数ごとの順序を容易に参照することができ、中央より上位の値のグループに存在しているか、あるいは中央より下位の値のグループに存在するかを判定して検索を行う二分探索を容易に行うことができ、検索時間の短縮を可能としている。
【００５３】
次に、図３から図５を参照して、上述した二分探索によりＮＡＰＴテーブル２１から検索を行う具体的なハードウェア構成及びその動作について説明する。
【００５４】
図３は、上述したデータ転送装置１に備えられるアドレス情報検索回路２０をハードウェアで構成したアドレス情報検索回路２０ａを示した図である。
【００５５】
アドレス情報検索回路２０ａは、４つのレジスタ、すなわちデータレジスタ３１（Ｄａｔａ）、第１レジスタ３２（ｎａｐｔｐ）、第２レジスタ３３（ｎａｐｔｍｐ）、第３レジスタ３４（Ｓｈｉｆｔｒｅｇ）、アドレスレジスタ５０（Ａｄｄｒｒｅｇ）と、４つのセレクタ、すなわちセレクタ４０、４１、４２、４３と、２つの論理和演算回路（ＯＲｓ）３５、３６と、１つのビットシフタ３７と、減算器（ＳＵＢ）５１と、バッファ回路５２、ｅｎａｂｌｅ信号回路５３と、判定回路５４と、ＮＡＰＴテーブル２１ａと、順序テーブル２６ａとを備えている。
【００５６】
なお、図３には示していないが、アドレス情報検索回路２０ａは、クロックを発生するクロック回路と、検索処理の開始指示信号を出力する開始信号回路とを備えている。
【００５７】
順序テーブル２６ａは、上述したＷＡＮから受信したＩＰアドレスの送信先のアドレス情報の変換に用いられる順序テーブル２６と同じデータ構成でデータが記録されており、第１レジスタ３２が値を記憶すると、「ｏｒｄｅｒ」の値が第１レジスタ３２が記憶した値に一致するあるいは、第１レジスタが示す順序テーブル２６ａのアドレスのエントリを検出し、検出したエントリの「ｅｎｔｒｙ」の項目に記録されている値（ｗ２ｌ［ｎａｐｔｐ］）を出力する構成を有している。
【００５８】
アドレスレジスタ５０は、順序テーブル２６ａの出力に接続されており、クロックの立ち下りにて順序テーブル２６ａから出力されるデータを記憶する。
【００５９】
ＮＡＰＴテーブル２１ａは、上述したＮＡＰＴテーブル２１と同じデータ構成で、予め２５６のエントリが記録されている。また、ＮＡＰＴテーブル２１ａは、アドレスレジスタ５０が値を記憶すると、「ｅｎｔｒｙ」の値がアドレスレジスタ５０が記憶した値に一致するエントリを検出し、検出したエントリの「ｇＡｄｄｒ」、「ｇＰｏｒｔ＃」、「Ｐｒｏｔｏｃｏｌ＃」の項目の値（ＮＡＰＴＴａｂｌｅ［ｗ２ｌ［ｎａｐｔｐ］］）を減算器５１に出力する。また、ＮＡＰＴテーブル２１ａは、当該エントリの「ｌＡｄｄｒ」、「ｌＰｏｒｔ＃」の項目の値（ｒｅｓ（ＮｅｗＡｄｄｒ、ＮｅｗＰｏｒｔ＃））をバッファ回路５２に出力する。
【００６０】
減算器５１は、２つの入力端子と、２つの出力端子を有しており、一方の入力端子は、セレクタ４０に接続され、他方の入力端子はＮＡＰＴテーブル２１ａの出力に接続されている。また、減算器５１は、セレクタ４０から入力される検索キー情報を６４ビットで表した場合の数値から、ＮＡＰＴテーブル２１ａから出力される「ｇＡｄｄｒ」、「ｇＰｏｒｔ＃」、「Ｐｒｏｔｏｃｏｌ＃」を６４ビットで表した場合の数値を減算し、減算の結果が負の場合、出力端子ｓｉｇｎから１、出力端子ｚｅｒｏから０を出力する。また、演算結果が０の場合、出力端子ｓｉｇｎから０、出力端子ｚｅｒｏから１を出力する。また、演算結果が、負あるいは０以外、すなわち正の場合、出力端子ｓｉｇｎから０、出力端子ｚｅｒｏから０を出力する。
【００６１】
ここで、出力端子ｚｅｒｏから１が出力される場合（Ｈｉｔ）とは、検索キー情報の値とＮＡＰＴテーブル２１ａから出力される値が一致している場合を示しており、０が出力される場合（Ｍｉｓｓ）とは、検索キー情報の値とＮＡＰＴテーブル２１ａから出力される値が一致していない場合を示している。
【００６２】
バッファ回路５２は、ＮＡＰＴテーブル２１ａから出力される「ｌＡｄｄｒ」、「ｌＰｏｒｔ＃」の項目の値（ｒｅｓ（ＮｅｗＡｄｄｒ、ＮｅｗＰｏｒｔ＃））と、減算器５１の出力端子ｚｅｒｏから出力される値とを対応付けて記憶する。
【００６３】
ｅｎａｂｌｅ信号回路５３は、バッファ回路５２に記憶しているデータを出力させるためのｅｎａｂｌｅ信号を出力する回路であり、内部にカウンタを有しており、例えば、ＮＡＰＴテーブル２１ａのエントリ数が２５６の場合、二分探索で必要となる探索回数となる９（＝ｌｏｇ２（２５６）＋１）回目のクロックがクロック回路から出力された後に、ｅｎａｂｅｌ信号を出力する。
【００６４】
判定回路５４は、バッファ回路５２から出力される検索結果のうち、出力端子ｚｅｒｏが１である検索結果が存在するか否かを判定し、存在する場合、当該検索結果のＩＰアドレスとポート番号（ｒｅｓ（ＮｅｗＡｄｄｒ、ＮｅｗＰｏｒｔ＃））とを上述した変換部２３に出力する。
【００６５】
データレジスタ３１、第１レジスタ３２、第２レジスタ３３、第３レジスタ３４は、クロックの立ち上がりで、入力されるデータをラッチ、すなわち入力されるデータを記憶し、記憶しているデータを出力し、次のクロックの立ち上がりまで記憶しているデータを保持する。
【００６６】
セレクタ４０は、２つの入力端子ｉｎ１とｉｎ２とを有している。ｉｎ１には、データレジスタ３１から出力されるデータが入力され、ｉｎ２には、データ転送装置１の検索部２２あるいは検索部２５が受信したＩＰパケットから読み出した検索キー情報、すなわちＩＰアドレス、ポート番号、プロトコル番号が入力される。また、セレクタ４０は、最初のクロックでは、ｉｎ２から入力されるデータをデータレジスタ３１に出力し、それ以降のクロックではｉｎ１から入力されるデータをデータレジスタ３１に出力する。
【００６７】
セレクタ４１は、３つの入力端子ｉｎ１とｉｎ２とｉｎ３とを有している。ｉｎ１には論理和演算回路３５から出力されるデータが入力され、ｉｎ２には論理和演算回路３６から出力されるデータが入力され、ｉｎ３には初期値としてＮＡＰＴテーブル２１のエントリ数の半数である１２８（１０００＿００００ｂ）が入力される。また、セレクタ４１は、最初のクロックでは、ｉｎ３から入力されるデータを第１レジスタ３２に出力し、それ以降のクロックでは減算器５１の出力端子ｓｉｇｎから出力される値が１の場合、ｉｎ２から入力されるデータを第１レジスタ３２に出力する。また、減算器５１の出力端子ｓｉｇｎから出力される値が０の場合、ｉｎ１から入力されるデータを第１レジスタ３２に出力する
【００６８】
セレクタ４２は、セレクタ４１と同様に、３つの入力端子ｉｎ１とｉｎ２とｉｎ３とを有している。ｉｎ１には第１レジスタ３２から出力されるデータが入力され、ｉｎ２には第２レジスタ３３から出力されるデータが入力され、ｉｎ３には初期値として０（００００＿００００ｂ）が入力される。また、セレクタ４２は、最初のクロックでは、ｉｎ３から入力されるデータを第２レジスタ３３に出力し、それ以降のクロックでは減算器５１の出力端子ｓｉｇｎから出力される値が１の場合、ｉｎ２から入力されるデータを出力する。また、減算器５１の出力端子ｓｉｇｎから出力される値が０の場合、ｉｎ１から入力されるデータを出力する。
【００６９】
セレクタ４３は、２つの入力端子ｉｎ１とｉｎ２とを有している。ｉｎ１には、ビットシフタ３７から出力されるデータが入力され、ｉｎ２には初期値として１２８の半数の値である６４（０１００＿００００ｂ）が入力される。また、セレクタ４３は、最初のクロックでは、ｉｎ２から入力されるデータを第３レジスタ３４に出力し、それ以降のクロックではｉｎ１から入力されるデータを第３レジスタ３４に出力する。
【００７０】
なお、図３は、ＷＡＮから受信したＩＰパケットの送信先のアドレス情報を変換する構成として示しているため、順序テーブル２６ａを備えることとしているが、ＬＡＮから受信したＩＰパケットの送信元のアドレス情報を変換する場合には、順序テーブル２６ａを順序テーブル２７と同じデータ構成を有する順序テーブル２７ａに置き換えられる。また、ＮＡＰＴテーブル２１ａから減算器５１に出力されるのは「ｌＡｄｄｒ」、「ｌＰｏｒｔ＃」、「Ｐｒｏｔｏｃｏｌ」の項目の値となりバッファ回路５２に出力されるのは「ｇＡｄｄｒ」、「ｇＰｏｒｔ＃」の項目となる。また、判定回路５４は、図１の変換部２４に出力する構成となる。
【００７１】
また、図３に示したアドレス情報検索回路２０ａにおいて、上述した４つのレジスタ、４つのセレクタと、２つの論理和演算回路と、１つのビットシフタと、減算器５１と、バッファ回路５２、ｅｎａｂｌｅ信号回路５３と、判定回路５４、及びクロック回路、開始信号回路は、図１の検索部２２あるいは検索部２５に対応することになる。
【００７２】
また、上述した図３のアドレス情報検索回路２０ａにおいて、各レジスタのメモリの速度によりデータをラッチする位置を適宜変更するようにしてもよい。
【００７３】
次に、図４及び図５を参照して、アドレス情報検索回路２０ａの動作について説明する。図４は、アドレス情報検索回路２０ａによる二分探索の動作を示したフローチャートである。
【００７４】
最初に、セレクタ４０の入力端子ｉｎ２には、検索キー情報（Ａｄｄｒ、Ｐｏｒｔ＃、Ｐｒｏｔｏｃｏｌ）が入力され、セレクタ４１の入力端子ｉｎ３には１２８が入力され、セレクタ４２の入力端子ｉｎ３には、０が入力され、セレクタ４３の入力端子ｉｎ３には、６４が入力される。また、ｅｎａｂｌｅ回路５３が内部に備えるカウンタｉには０が設定される（ステップＳａ１）。
【００７５】
ここで、開始信号回路から開始信号が出力されると検索の処理が開始され、ｅｎａｂｌｅ回路５３はカウンタｉが９未満であるか否かを判定し、カウンタｉが９未満である場合、ｅｎａｂｌｅ信号を出力せずステップＳａ３に進む（ステップＳａ２）。一方、カウンタｉが９未満でない場合、ｅｎａｂｌｅ信号を出力し、ステップＳａ８に進む。
【００７６】
最初のクロックの立ち上がりにおいて、データレジスタ３１は、セレクタ４０から出力される検索キー情報（Ａｄｄｒ、Ｐｏｒｔ＃、Ｐｒｏｔｏｃｏｌ）を記憶する。第１レジスタ３２は、セレクタ４１から出力される１２８を記憶する。第２レジスタ３３は、セレクタ４２から出力される０を記憶する。第３レジスタ３４は、セレクタ４３から出力される６４を記憶する。
【００７７】
当該クロック周期において、第１レジスタ３２は、記憶している１２８の値を論理和演算回路３５とセレクタ４２に出力する。第２レジスタ３３は、記憶している０の値を論理和演算回路３６とセレクタ４２に出力する。第３レジスタ３４は、記憶している６４の値を論理和演算回路３５と、論理和演算回路３６と、ビットシフタ３７に出力する。
【００７８】
論理和演算回路３５は、第１レジスタ３２から出力される１２８と、第３レジスタ３４から出力される６４の論理和である１９２を出力する。論理和演算回路３６は、第２レジスタから出力される０と、第３レジスタから出力される６４の論理和である６４（２０ｈ）を出力する。
【００７９】
順序テーブル２６ａは、第１レジスタ３２が記憶している１２８の値を参照し、「ｏｒｄｅｒ」が１２８であるエントリの「ｅｎｔｒｙ」の項目に記録されている値（ｗ２ｌ［ｎａｐｔｐ］）を出力する。
【００８０】
そして、クロックの立ち下りにより、アドレスレジスタ５０は、順序テーブル２６ａから出力される値を記憶する。ＮＡＰＴテーブル２１ａは、アドレスレジスタ５０が記憶している値を参照し、「ｅｎｔｒｙ」の項目が当該値であるエントリを読み出し、「ｇＡｄｄｒ」、「ｇＰｏｒｔ＃」、「Ｐｒｏｔｏｃｏｌ」を組み合わせた６４ビットの値（ＮＡＰＴＴａｂｌｅ［ｗ２ｌ［ｎａｐｔｐ］］）を減算器５１に出力する。また、ＮＡＰＴテーブル２１ａは、読み出したエントリに含まれる「ｌＡｄｄｒ」、「ｌＰｏｒｔ＃」（ｒｅｓ（ＮｅｗＡｄｄｒ，ＮｅｗＰｏｒｔ＃）をバッファ回路５２に出力する（ステップＳａ３）。
【００８１】
減算器５１は、セレクタ４０から出力された検索キー情報を６４ビットで示した場合の数値から、ＮＡＰＴテーブル２１ａから出力された数値を減算し、出力端子ｚｅｒｏと出力端子ｓｉｇｎに減算した結果を出力する（ステップＳａ４）。
【００８２】
減算結果が正の場合、すなわち出力端子ｓｉｇｎから０が出力された場合、セレクタ４１は、ｉｎ１から入力されている値、すなわち論理和演算回路３５の演算結果（ｎａｐｔｐ｜ｓｈｉｆｔｒｅｇ）を第１レジスタ３２（ｎａｐｔｐ）に出力する。また、セレクタ４２は、ｉｎ１から入力されている値、すなわち第１レジスタ３２から出力される値（ｎａｐｔｐ）を第２レジスタ３３（ｎａｐｔｍｐ）に出力する（ステップＳａ５）。
【００８３】
一方、演算結果が負の場合、すなわち出力端子ｓｉｇｎから１が出力された場合、セレクタ４１は、ｉｎ２から入力されている値、すなわち論理和演算回路３６の演算結果（ｎａｐｔｍｐ｜ｓｈｉｆｔｒｅｇ）を第１レジスタ３２（ｎａｐｔｐ）に出力する。また、セレクタ４２は、ｉｎ２から入力されている値、すなわち第２レジスタ３３から出力される値（ｎａｐｔｍｐ）を第２レジスタ３３（ｎａｐｔｍｐ）に出力する（ステップＳａ６）。
【００８４】
ｅｎａｂｌｅ信号回路５３は、クロックの発生後にカウンタｉに１を加える。ビットシフタ３７は、第３レジスタ３４から出力される６４を１ビット右シフトした３２を出力する（ステップＳａ７）。上記のステップＳａ２からステップＳａ７の処理が９回繰り返され、９回目で、ｅｎａｂｌｅ信号回路５３は、ｅｎａｂｌｅ信号をバッファ回路５２に出力する。バッファ回路５２は、記憶している検索結果を判定回路５４に出力する。そして、判定回路５４は、検索キー情報がＮＡＰＴテーブル２１ａに存在している場合、すなわち出力端子ｚｅｒｏの出力が１となっているか否かを判定し（ステップＳａ８）、出力端子ｚｅｒｏの出力が１となっている場合、ＮＡＰＴテーブル２１ａから出力されたｒｅｓ（ＮｅｗＡｄｄｒ、ＮｅｗＰｏｒｔ＃）を変換部２３に出力し、変換部２３が受信したＩＰパケットの送信先のＩＰアドレスとポート番号をＮｅｗＡｄｄｒ、ＮｅｗＰｏｒｔ＃で書き換える。（ステップＳａ９）。一方、出力端子ｚｅｒｏの出力が１となっている検索結果が存在しない場合、ＩＰアドレス、ポート番号を変更しないか、あるいは当該ＩＰパケット自体を破棄する（ステップＳａ１０）。
【００８５】
なお、クロックが９回発生していない場合であっても、ステップＳａ４において、減算結果が零、すなわち検索キー情報とＮＡＰＴテーブル２１ａから出力された情報とが一致した場合に、ステップＳａ５に進まず、ステップＳａ８に進み処理を終了させるようにしてもよい。
【００８６】
図５は、順序テーブル２６ａにおいて１３４番目で、検索キー情報とＮＡＰＴテーブル２１ａのエントリが一致する場合におけるアドレス情報検索回路２０ａの各回路の動作を示したタイミングチャートである。
【００８７】
図５に示すように、クロック（ｃｌｋ１、ｃｌｋ２、・・・）が立ち上がるごとに、第１レジスタ３２、第２レジスタ３３、第３レジスタ３４が内部に記憶する値が変化し、９回目のクロック（ｃｌｋ９）にて、第１レジスタ３２が記憶する値が１３４に収束することになる。そして、９回目のクロックの立ち下りにおいて、ｅｎａｂｌｅ信号がｅｎａｂｌｅ信号回路５３から出力され、バッファ回路５２からＨｉｔ／Ｍｉｓｓ、すなわち出力端子ｚｅｒｏの値と、検索されたアドレス情報（ｒｅｓ（ＮｅｗＡｄｄｒ，ＮｅｗＰｏｒｔ＃））が対応付けられて判定回路５４に出力されることになる。
【００８８】
なお、上述した実施形態において、ＮＡＰＴテーブル２１ａを構成するメモリのメモリ速度が速い場合には、アドレスレジスタ５０を除いて構成することも可能である。
【００８９】
また、上述した実施形態において、ＮＡＰＴテーブル２１ａに記録されるエントリが２５６に満たない場合には、図２のＮＡＰＴテーブル２１のエントリ番号２５５に示すように全ての項目のビットを１としたエントリを追加し、対応するエントリ番号が存在しない順序テーブル２６の「ｏｒｄｅｒ」の値が２５４と２５５の「ｅｎｔｒｙ」に２５５を記録することで２５６個にすることができ、回路構成を変更せずに９回の二分探索処理を支障なく実行することが可能となる。
【００９０】
また、ＮＡＰＴテーブル２１ａに記録されるエントリが２５６に満たない場合の他の対策としては、対応するエントリ番号が存在しない順序テーブル２６の「ｅｎｔｒｙ」に、検索対象としないことを示すフラグを設定するようにしてもよい。
【００９１】
また、一度検索対象のエントリがＮＡＰＴテーブル２１ａから減算器５１に出力されると、その後、第１レジスタ３２に記憶される値が変化しないため、バッファ回路５２には同じ情報が出力されることになる。そのため、バッファ回路５２には、減算器５１から出力される情報を全て記憶しておくのではなく、最新の情報のみを記憶しておくようにし、ｅｎａｂｌｅ信号回路５３からｅｎａｂｌｅ信号がバッファ回路５２に入力されると、バッファ回路５２は、ｅｎａｂｌｅ信号の入力の際に記憶している情報を判定回路５４に出力するようにしてもよい。
【００９２】
上記の実施形態の構成により、ＮＡＰＴテーブル２１ａのエントリ数に応じた回数、すなわちエントリ数をＮとした場合、ｌｏｇ２（Ｎ）＋１の回数の二分探索により、アドレス情報を検索することが可能となる。また、上記のような順序テーブル２６ａ及び２７ａを設けることで、ハードウェア処理に適したＮＡＰＴにおける検索処理を実現することが可能となる。
【００９３】
次に、図６から図８を参照して、図１に示したデータ転送装置１においてＮＡＰＴテーブル２１にエントリを追加する処理と、削除する処理について説明する。
【００９４】
図６は、ＮＡＰＴテーブル２１に対してエントリを追加、あるいは削除するエントリ追加削除部６０が追加されたデータ転送装置１ｂのアドレス情報検索回路２０の構成を示した図である。エントリ追加削除部６０は、エントリを追加する場合には、追加するエントリに含まれるアドレス情報を検索部２２及び２５に入力し、検索部２２及び２５から出力される検索結果に基づいてＮＡＰＴテーブル２１へのエントリの追加し、順序テーブル２６と２７のエントリの書き換えを行う。また、エントリ追加削除部６０は、エントリを削除する場合、削除するエントリを含むＮＡＰＴテーブル２１のエントリ番号及び当該エントリ番号に対応する順序テーブル２６及び２７の「ｏｒｄｅｒ」の番号に基づいて、エントリの削除を行う。
【００９５】
次に、図７を参照してエントリを追加する処理について説明する。
図７では、図６のアドレス情報検索回路２０に対して図３のアドレス情報検索回路２０ａを適用した場合について説明する。
エントリを追加する場合、追加するエントリに含まれる「ｇＡｄｄｒ」、「ｇＰｏｒｔ＃」、「Ｐｒｏｔｏｃｏｌ」を６４ビットで表した数値の大きさに応じて順序テーブル２６ａの順序を入れ替え、さらに、「ｌＡｄｄｒ」、「ｌＰｏｒｔ＃」、「Ｐｒｏｔｏｃｏｌ」を６４ビットで表した数値の大きさに応じて順序テーブル２７ａの順序を入れ替える必要がある。
【００９６】
まず最初に、エントリ追加削除部６０は、検索キー情報として、追加するエントリの「ｇＡｄｄｒ」、「ｇＰｏｒｔ＃」、「Ｐｒｏｔｏｃｏｌ」を６４ビットで表した数値をアドレス情報検索回路２０ａのセレクタ４０に入力する。アドレス情報検索回路２０ａは、図４で説明した二分探索の処理であるステップＳａ１からＳａ７と同じ処理であるステップＳｂ１からＳｂ８の処理を行い、９回のクロック発生の後、バッファ回路５２から検索結果が出力され、判定回路５４が検索結果の中で出力端子ｚｅｒｏが１となっている検索結果をエントリ追加削除部６０に出力する。
【００９７】
出力端子ｚｅｒｏからの出力が１となっている検索結果が存在する場合、エントリ追加削除部６０は、第１レジスタ３２の値を読み出して、内部の変数ｎａｐｔｐとして記憶する。そして、変数にｎａｐｔｐに１加えた値をｎａｐｔｐとする（ステップＳｂ９）。また、出力端子ｚｅｒｏからの出力が１となっている検索結果が存在しない場合には、エントリ追加削除部６０は、第１レジスタ３２の値を読み出して、読み出した値を内部の変数ｎａｐｔｐとして記憶する。
【００９８】
エントリ追加削除部６０は、内部のカウンタｊに２５５を設定し、カウンタｊの値が、変数ｎａｐｔｐの値より大きいか否かを判定する（ステップＳｂ１１）。カウンタｊの値が、変数ｎａｐｔｐの値より大きい場合、エントリ追加削除部６０は、順序テーブル２６ａの「ｏｒｄｅｒ」の値がｊの値の「ｅｎｔｒｙ」の項目（ｗ２ｌ［ｊ］）に、１つ前の「ｅｎｔｒｙ」の項目（ｗ２ｌ［ｊ−１］）を書き込み、カウンタｊから１減算した値をカウンタｊに代入する。そして、カウンタｊの値が、変数ｎａｐｔｐの値より大きい間ステップＳｂ１２の書き換え処理を繰り返す。
【００９９】
カウンタｊの値が、変数ｎａｐｔｐの値以下となった場合、エントリ追加削除部６０は、ＮＡＰＴテーブル２１ａの空きエントリを検索し、空きエントリに追加するエントリを記録する（ステップＳｂ１３）。そして、エントリ追加削除部６０は、追加したエントリに付与されるＮＡＰＴテーブル２１ａの「ｅｎｔｒｙ」の番号を読み出し、順序テーブル２６ａの空きエントリ、すなわち変数ｎａｐｔｐの値の順序に読み出したＮＡＰＴテーブル２１ａの「ｅｎｔｒｙ」の番号を記録する（ステップＳｂ１４）。
【０１００】
図７の処理の後、順序テーブル２７ａを書き換える処理を上記のフローチャートと同様に、順序テーブル２７ａに対して新たなエントリのＮＡＰＴテーブル２１ａにおけるエントリ番号を挿入すべき位置を検出して、順序テーブル２７ａを書き換えることにより、エントリの追加を完了することができる。
【０１０１】
上記の処理により、追加しようとするエントリに対する順序テーブル２６ａ、２７ａへの挿入位置を検索することができ、検索した挿入位置に従って、順序テーブル２６ａ、２７ａの「ｅｎｔｒｙ」に記録されている値を移動させることができる。そして、ＮＡＰＴテーブル２１ａの空きエントリに追加するエントリを書き込み、書き込んだエントリのエントリ番号を順序テーブル２６ａ、２７ａの挿入位置に記録することで、エントリの追加時における順序テーブル２６ａ、２７ａの変更を行うことが可能となる。
【０１０２】
次に、図８を参照してエントリ追加削除部６０が行うエントリの削除処理について説明する。
まず最初に、エントリ追加削除部６０が削除するＮＡＰＴテーブル２１ａのエントリ番号と、当該エントリ番号に対応する順序テーブル２６ａの「ｏｒｄｅｒ」の項目の番号を読み出す。カウンタｊに読み出した「ｏｒｄｅｒ」の項目の番号を設定し（ステップＳｃ２）、カウンタｊの値が２５５未満であるか否かを判定する（ステップＳｃ３）。カウンタｊの値が２５５未満である場合、エントリ追加削除部６０は、順序テーブル２６ａの「ｏｒｄｅｒ」の値がｊの値の「ｅｎｔｒｙ」の項目（ｗ２ｌ［ｊ］）に、１つ後の「ｅｎｔｒｙ」の項目（ｗ２ｌ［ｊ＋１］）を書き込み（ステップＳｃ４）、カウンタｊに１加算した値をカウンタｊに代入する。そして、カウンタｊの値が、変数ｎａｐｔｐの値より大きい間ステップＳｃ４の書き換え処理を繰り返す。
【０１０３】
カウンタｊの値が、２５５以上となった場合、エントリ追加削除部６０は、順序テーブル２６ａのｏｒｄｅｒ＝２５５の「ｅｎｔｒｙ」の項目（ｗ２ｌ［２５５］）に削除するＮＡＰＴテーブル２１ａのエントリ番号を記録し（ステップＳｃ５）、当該ＮＡＰＴテーブル２１ａのエントリ（ＮＡＰＴＴａｂｌｅ［ｅｎｔｒｙ］）に全てのビットを１として記録する（ステップＳｃ６）。
【０１０４】
図８の処理の後、順序テーブル２７ａについても同様の処理を行うことで、エントリの削除処理を完了することができる。
【０１０５】
上記の処理により、順序テーブル２６ａ及び２７ａから削除するエントリに対応するエントリ番号を削除し、それ以降のエントリを詰めておき、ＮＡＰＴテーブル２１ａの削除するエントリには全てのビットを１として記録することが可能となる。
【０１０６】
なお、エントリの追加、削除において、図３に示したハードウェアで構成されるアドレス情報検索回路２０ａの場合には、順序テーブル２６ａ、２７ａ、ＮＡＰＴテーブル２１ａに書き込み、あるいは削除を行うため、各テーブルの状態や、削除するエントリの位置などを予め検出しておく必要があるが、これらの情報は、例えば、エントリ追加削除部６０を外部プロセッサにより構成してアドレス情報検索回路２０ａに組み込み、当該エントリ追加削除部６０に管理させるようにしてもよい。
【０１０７】
なお、図８の処理では、ＮＡＰＴテーブル２１ａのエントリ番号に基づいて、削除する場合について示したが、削除するエントリの情報、すなわち「ｇＡｄｄｒ」、「ｇＰｏｒｔ＃」、「ｌＡｄｄｒ」、「ｌＰｏｒｔ＃」、「Ｐｒｏｔｏｃｏｌ＃」に基づいて、削除を行うようにすることも可能である。
【０１０８】
なお、上記のエントリ追加及び削除では、ＮＡＰＴテーブル２１ａや順序テーブル２６ａ及び２７ａの「ｅｎｔｒｙ」に記録されている値の位置を移動させる必要があるため、その処理中は、ＮＡＰＴ検索の処理を行うことができない。そのため、順序テーブル２６ａ及び２７ａを２面備え、追加・削除時に裏面の順序テーブルに対して処理を行い、更新のタイミング、裏面の順序テーブルと表面の順序テーブルを入れ替えることにより、ＮＡＰＴ検索ができなくなる時間を大幅に短縮することが可能となる。
ここで、更新のタイミングとは、追加や削除の要求が発生した場合に、現在実行されているＮＡＰＴ検索処理が終了した時点や、２面のテーブルを用いて更新を行う場合には、１回のＮＡＰＴテーブルの検索終了後、あるいは複数回のＮＡＰＴテーブルの検索終了後に予め設けられる更新許可時間などがある。
【０１０９】
また、ＷＡＮから受信したＩＰパケットに対するＮＡＰＴテーブルと、ＬＡＮから受信したＩＰパケットに対するＮＡＰＴテーブルとを備えることができる場合、順序テーブルを除いて、ＮＡＰＴテーブルの検索対象部分、すなわち検索キー情報を構成する項目を組み合わせた情報が示す数値を昇べきの順に設定して運用するようにすることもできる。また、それぞれのＮＡＰＴテーブルを備える場合において、エントリの追加及び削除を行う場合には、合計４面のＮＡＰＴテーブルを有することにより、ＮＡＰＴ検索ができなくなる時間を大幅に短縮することが可能となる。
【０１１０】
なお、上記の実施形態において、減算器５１の代わりに比較器を適用するようにしてもよい。
【０１１１】
また、上記の実施形態では、順序テーブル２６及び２７に記憶されるエントリの数は２５６であるとして説明したが、本発明は、当該数値に限られず、どのような数であってもよいが、二分探索における中央値は、偶数の場合には、エントリ数を２で割った値であり、奇数の場合には、エントリ数を２で割った値に１加算した値として処理を行うことができる。
【０１１２】
また、上記の実施形態では、検索キー情報として、ＩＰアドレス、ポート番号、プロトコル番号の組み合わせた情報としたが、本発明はこれに限られず、検索キー情報に含まれる情報は、ＩＰアドレスのみであってもよく、また、ＩＰアドレスとポート番号を組み合わせた情報であってもよい。
【０１１３】
また、本発明に記載の変換情報記憶手段は、ＮＡＰＴテーブル２１、２１ａに対応し、第１の順序情報記憶手段は、順序テーブル２６、２６ａに対応し、第２の順序情報記憶手段は、順序テーブル２７、２７ａに対応する。また、本発明の第１の検索手段は、検索部２２に対応し、第２の検索手段は、検索部２５に対応する。また、本発明の第１の転送手段は、変換部２３、経路検索部１２、接続部１２を組み合わせた構成に対応し、第２の転送手段は、変換部２４、経路検索部１２、接続部１３を組み合わせた構成に対応する。
【０１１４】
また、本発明に記載の入力手段は、検索部２２あるいは検索部２５において接続部１１あるいは接続部１３から入力されるＩＰパケットから検索キー情報に含まれる情報を読み出して入力する構成に対応する。また、本発明に記載のクロック生成手段は、上述したクロック回路に対応し、第１レジスタは、第１レジスタ３２、第２レジスタは第２レジスタ３３、第３レジスタは第３レジスタ３４に対応し、第１の論理和演算手段は、論理和演算部３５、第２の論理和演算手段は、論理和演算部３６に対応する、また、本発明に記載の中央値算出手段は、ビットシフタ３７に対応し、判定手段は、減算器５１に対応する。また、本発明に記載の第１のセレクタは、セレクタ４１に対応し、第２のセレクタは、セレクタ４２に対応し、第３のセレクタは、セレクタ４３に対応する。また、本発明に記載の出力手段は、バッファ回路５２及びｅｎａｂｌｅ信号回路５３に対応する。また、本発明に記載の変換情報追加手段は、エントリ追加削除部６０に対応する。
【図面の簡単な説明】
【０１１５】
【図１】本実施形態によるデータ転送装置を示すブロック図である。
【図２】同実施形態におけるＮＡＰＴテーブル及び順序テーブルのデータ構成を示した図である。
【図３】同実施形態におけるアドレス情報検索回路のハードウェア構成を示した図である。
【図４】同実施形態におけるアドレス情報検索処理を示したフローチャートである。
【図５】同実施形態におけるアドレス情報検索処理時のタイミングチャートを示した図である。
【図６】同実施形態におけるエントリ追加及び削除を行う場合のデータ転送装置を示すブロック図である。
【図７】同実施形態におけるエントリ追加処理を示したフローチャートである。
【図８】同実施形態におけるエントリ削除処理を示したフローチャートである。
【符号の説明】
【０１１６】
１  データ転送装置
１１  接続部
１２  経路検索部
１３  接続部
２０  アドレス情報検索回路
２１  ＮＡＰＴテーブル
２６  順序テーブル
２７  順序テーブル
２２  検索部
２３  変換部
２４  変換部
２５  検索部
【図１】
0004642628.tif 000002
【図２】
0004642628.tif 000003
【図３】
0004642628.tif 000004
【図４】
0004642628.tif 000005
【図５】
0004642628.tif 000006
【図６】
0004642628.tif 000007
【図７】
0004642628.tif 000008
【図８】
0004642628.tif 000009