(57)【特許請求の範囲】
【請求項１】
予め宛先ＩＰアドレスをテーブルに登録すると共に、ＩＰパケットの出力方路を前記宛先ＩＰアドレス毎に登録しておき、受信したＩＰパケットから宛先ＩＰアドレスを読み出し、該宛先ＩＰアドレスをキーにして前記テーブルを検索することにより、前記テーブルから網内経路の転送処理情報を読み出し、事前に定められた経路でＩＰパケットの転送を行うＩＰパケット転送処理装置において、
登録する宛先ＩＰアドレスのホストアドレス部分の全てのビットを”０”とし、かつ宛先ＩＰアドレスに対応したサブネットマスク部分のビットを”１”とした後、一つの宛先ＩＰアドレスと、前記サブネットマスクと転送処理情報とをひとまとめにして１行のデータとして、前記宛先ＩＰアドレスを数値とみなして昇順または降順に並べたテーブルを設定するテーブル設定手段と、
前記テーブルにおける検索範囲の先頭行番号を記憶する先頭行番号レジスタと、
前記テーブルにおける検索範囲の末尾行番号を記憶する末尾行番号レジスタと、
前記テーブルにおける検索範囲の中央行番号を記憶する中央行番号レジスタと、
検索範囲の中央の中央行番号を、前記先頭行番号レジスタに記憶された先頭行番号および前記末尾行番号レジスタに記憶された末尾行番号に基づいて計算する照合範囲設定手段と、
前記中央行番号レジスタに記憶された中央行番号と、前記照合範囲設定手段が計算した中央行番号とを照合し、等しい場合には、ＩＰアドレス未登録を出力して検索を終了し、等しくない場合には、前記照合範囲設定手段が計算した中央行番号の書き込み信号を前記中央行番号レジスタに出力する照合手段と、
前記照合範囲設定手段が計算した中央行番号を入力し、該中央行番号におけるサブネットマスクと受信したＩＰパケットから読み出した宛先ＩＰアドレスとを各ビット毎にＡＮＤ演算した結果と、登録された宛先ＩＰアドレスとを数値とみなして比較し、前記比較結果が、
（ａ）［ＩＰパケットから読み出した宛先ＩＰアドレス］＜［登録された宛先ＩＰアドレス］であるとき、前記照合範囲設定手段が計算した中央行番号の書き込み信号を前記末尾行番号レジスタに出力し、
（ｂ）［ＩＰパケットから読み出した宛先ＩＰアドレス］＞［登録された宛先ＩＰアドレス］であるとき、前記照合範囲設定手段が計算した中央行番号の書き込み信号を前記先頭行番号レジスタに出力し、
（ｃ）［ＩＰパケットから読み出した宛先アドレス］＝［登録された宛先ＩＰアドレス］であるとき、そのときの前記テーブルにおける行に記載されている転送処理情報を出力した後、検索を終了する比較手段と
を具備することを特徴とするＩＰパケット転送処理装置における高速検索回路。
【請求項２】
前記テーブル設定手段は、登録する宛先ＩＰアドレスのホストアドレス部分のビットの全てを、前記”０”に代えて”１”とし、前記比較手段は、選択された行における”サブネットマスクの反転ビット”と受信したＩＰパケットから読み出した宛先ＩＰアドレスとを各ビット毎に前記ＡＮＤ演算に代えてＯＲ演算した結果と、登録された宛先ＩＰアドレスとを比較する
ことを特徴とする請求項１に記載のＩＰパケット転送処理装置における高速検索回路。
【請求項３】
各々に入力されるＩＰパケット流の中から個々のＩＰパケットを識別して、ＩＰパケットの区切り情報と一緒にＩＰパケットを各々出力するとともに、前記ＩＰパケットに記載されているＩＰアドレスを各々出力する複数のＩＰパケット識別手段と、前記複数のＩＰパケット識別手段に対応して各々設けられる請求項１または請求項２に記載の高速検索回路と、
前記複数のＩＰパケット識別手段に対応して各々設けられた複数の入力端子と、複数の出力端子とを有し、当該入力端子に前記転送処理情報および前記ＩＰパケットが入力された場合、該転送処理情報により決定される当該出力端子へ前記前記ＩＰパケットを出力し、一方、当該入力端子に前記ＩＰアドレス未登録情報および前記ＩＰパケットが入力された場合、該ＩＰアドレス未登録情報に基づいて決定される未登録専用の出力端子へ前記ＩＰパケットを出力するＩＰパケットスイッチ手段と
を具備することを特徴とするＩＰパケット転送処理装置。
【請求項４】
各々に入力されるセル流の中から個々のＩＰパケットを再生して、前記ＩＰパケットに記載されているＩＰアドレスを各々出力する複数のＩＰパケット再生手段と、前記複数のＩＰパケット再生手段に対応して各々設けられる請求項１または請求項２に記載の高速検索回路と、
前記複数のＩＰパケット再生手段に対応して各々設けられた複数の入力端子と、複数の出力端子とを有し、当該入力端子に前記転送処理情報および前記ＩＰパケットが入力された場合、該転送処理情報により決定される当該出力端子へ前記前記ＩＰパケットを出力し、一方、当該入力端子に前記ＩＰアドレス未登録情報および前記ＩＰパケットが入力された場合、該ＩＰアドレス未登録情報に基づいて決定される未登録専用の出力端子へ前記ＩＰパケットを出力するＩＰパケットスイッチ手段と、前記ＩＰパケットスイッチ手段の前記複数の出力端子に対応して各々設けられ、入力されるＩＰパケットを各々セル化する複数のセル化手段と
を具備することを特徴とするＩＰパケット転送処理装置。
【請求項５】
各々に入力されるセル流からＩＰパケットが収容されているセルを識別し、該セルのＩＰパケットに記載されているＩＰアドレスを各々出力する複数のＩＰパケットセル識別手段と、前記複数のＩＰパケットセル識別手段に対応して各々設けられる請求項１または請求項２に記載の高速検索回路と、
前記複数のＩＰパケットセル識別手段に対応して各々設けられ、前記テーブル内の全ての行に対応する、前記ＡＮＤ演算した結果と、登録された前記宛先ＩＰアドレスとの比較結果が全て不一致である場合、ＩＰアドレス未登録情報を各々出力した後、検索を終了する複数の出力手段と、前記複数のＩＰパケットセル識別手段に対応して各々設けられた複数の入力端子と、複数の出力端子とを有し、当該入力端子に前記転送処理情報および前記セルが入力された場合、該転送処理情報により決定される当該出力端子へ前記前記セルを出力し、一方、当該入力端子に前記ＩＰアドレス未登録情報および前記セルが入力された場合、該ＩＰアドレス未登録情報に基づいて決定される未登録専用の出力端子へ前記セルを出力するセルスイッチ手段と
を具備することを特徴とするＩＰパケット転送処理装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、コンピュータ間通信等において、ＩＰ（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）パケットを受信してデータ等を転送する場合に、大量に高速で入力するＩＰパケットを受信した後、瞬時に、宛先につながる方路へＩＰパケットを出力するＩＰパケット転送処理装置に適用され、宛先ＩＰアドレスをキーとした宛先情報検索で利用されるＩＰパケット転送処理装置における高速検索回路およびＩＰパケット転送処理装置に関する。
【０００２】
【従来の技術】
従来より、コンピュータ間通信等においては、ＩＰパケットを予め登録された対地に転送するために、ルータと呼ばれる装置が用いられている。このルータは、マイクロプロセッサと該マイクロプロセッサで実行されるソフトウェアとによって、入力したＩＰパケットに記載されている宛先ＩＰアドレスに基づいて、宛先ＩＰアドレスが登録されたテーブルを検索して、そこから得られた転送宛先情報に基づいて宛先につながる方路へ該ＩＰパケットを出力する。
【０００３】
上記ソフトウェアが行う探索アルゴリズムは、例えば文献「Ｉｎｔｅｒｃｏｎｎｅｃｔｉｏｎｓ−ブリッジとルータについて」（Ｒａｄｉｓ  Ｐｅｒｌｍａｎ著、加藤朗監訳）で紹介されているように、ツリーアルゴリズムやバイナリサーチといった最も一致している（一致しているビット数が一番多い）宛先ＩＰアドレスをテーブル内から見つけ出すものである。
【０００４】
【発明が解決しようとする課題】
ところで、上述した従来のルータにおいては、宛先ＩＰアドレスをキーとしたＩＰパケットの転送宛先情報の検索処理を、マイクロプロセッサ上でソフトウェアによって実行しているため、おのずと処理能力に限界があった。従って、上述した従来のルータにおいては、大量に高速で入力するＩＰパケットを受信して瞬時に宛先につながる方路へＩＰパケットを出力することが困難であるという問題があった。
【０００５】
本発明は、このような背景の下になされたもので、宛先ＩＰアドレスをキーとしたＩＰパケットの転送先情報の検索処理を高速で行うことができ、かつ大量に高速で入力するＩＰパケットを受信して瞬時に宛先につながる方路へＩＰパケットを出力することができるＩＰパケット転送処理装置における高速検索回路およびＩＰパケット転送処理装置を提供することを目的とする。
【０００６】
【課題を解決するための手段】
この課題を解決するために、本発明においては、高速のハードウェア回路構成して、並列ビット演算によって一致／不一致を瞬時に判定できるようにした。即ち、マッチングを取る必要のないホストアドレス部分については、予め各ビットの値を”０”または”１”として固定した値にしてテーブルに登録し、入力したＩＰパケットの宛先ＩＰアドレスに対しても、サブネットマスクとのビット演算により、ホストアドレス部分の各ビットの値を”０”または”１”として値を固定してしまうので、サブネットアドレスを含むＩＰネットワークアドレスの一致／不一致を瞬時に判定できる。
また、本発明においては、高速検索を行うために、テーブル内に登録されている宛先ＩＰアドレスとＡＮＤ演算結果との照合回数が少なくなるように、照合順序を工夫した。即ち、本発明においては、登録されている宛先ＩＰアドレス（ホストアドレス部分のビットが全て”０”または”１”）をソートして昇順または降順に並べ、検索範囲を最初は全体の行とし、その範囲の中央の行の宛先ＩＰアドレスと比較して不一致の場合、その大小関係から検索対象範囲を半分に絞るようにし、検索が行われる度に検索範囲が半減するようにした。
【０００７】
具体的には、請求項１に記載の発明は、予め宛先ＩＰアドレスをテーブルに登録すると共に、ＩＰパケットの出力方路を前記宛先ＩＰアドレス毎に登録しておき、受信したＩＰパケットから宛先ＩＰアドレスを読み出し、該宛先ＩＰアドレスをキーにして前記テーブルを検索することにより、前記テーブルから網内経路の転送処理情報を読み出し、事前に定められた経路でＩＰパケットの転送を行うＩＰパケット転送処理装置において、登録する宛先ＩＰアドレスのホストアドレス部分の全てのビットを”０”とし、かつ宛先ＩＰアドレスに対応したサブネットマスク部分のビットを”１”とした後、一つの宛先ＩＰアドレスと、前記サブネットマスクと転送処理情報とをひとまとめにして１行のデータとして、前記宛先ＩＰアドレスを数値とみなして昇順または降順に並べたテーブルを設定するテーブル設定手段と、前記テーブルにおける検索範囲の先頭行番号を記憶する先頭行番号レジスタと、前記テーブルにおける検索範囲の末尾行番号を記憶する末尾行番号レジスタと、前記テーブルにおける検索範囲の中央行番号を記憶する中央行番号レジスタと、
検索範囲の中央の中央行番号を、前記先頭行番号レジスタに記憶された先頭行番号および前記末尾行番号レジスタに記憶された末尾行番号に基づいて計算する照合範囲設定手段と、前記中央行番号レジスタに記憶された中央行番号と、前記照合範囲設定手段が計算した中央行番号とを照合し、等しい場合には、ＩＰアドレス未登録を出力して検索を終了し、等しくない場合には、前記照合範囲設定手段が計算した中央行番号の書き込み信号を前記中央行番号レジスタに出力する照合手段と、前記照合範囲設定手段が計算した中央行番号を入力し、該中央行番号におけるサブネットマスクと受信したＩＰパケットから読み出した宛先ＩＰアドレスとを各ビット毎にＡＮＤ演算した結果と、登録された宛先ＩＰアドレスとを数値とみなして比較し、前記比較結果が、（ａ）［ＩＰパケットから読み出した宛先ＩＰアドレス］＜［登録された宛先ＩＰアドレス］であるとき、前記照合範囲設定手段が計算した中央行番号の書き込み信号を前記末尾行番号レジスタに出力し、（ｂ）［ＩＰパケットから読み出した宛先ＩＰアドレス］＞［登録された宛先ＩＰアドレス］であるとき、前記照合範囲設定手段が計算した中央行番号の書き込み信号を前記先頭行番号レジスタに出力し、（ｃ）［ＩＰパケットから読み出した宛先アドレス］＝［登録された宛先ＩＰアドレス］であるとき、そのときの前記テーブルにおける行に記載されている転送処理情報を出力した後、検索を終了する比較手段とを具備することを特徴とする。
【０００８】
請求項２に記載の発明は、前記テーブル設定手段は、登録する宛先ＩＰアドレスのホストアドレス部分のビットの全てを、前記”０”に代えて”１”とし、前記比較手段は、選択された行における”サブネットマスクの反転ビット”と受信したＩＰパケットから読み出した宛先ＩＰアドレスとを各ビット毎に前記ＡＮＤ演算に代えてＯＲ演算した結果と、登録された宛先ＩＰアドレスとを比較する
ことを特徴とする。
【０００９】
請求項３に記載の発明は、各々に入力されるＩＰパケット流の中から個々のＩＰパケットを識別して、ＩＰパケットの区切り情報と一緒にＩＰパケットを各々出力するとともに、前記ＩＰパケットに記載されているＩＰアドレスを各々出力する複数のＩＰパケット識別手段と、前記複数のＩＰパケット識別手段に対応して各々設けられる請求項１または請求項２に記載の高速検索回路と、前記複数のＩＰパケット識別手段に対応して各々設けられた複数の入力端子と、複数の出力端子とを有し、当該入力端子に前記転送処理情報および前記ＩＰパケットが入力された場合、該転送処理情報により決定される当該出力端子へ前記前記ＩＰパケットを出力し、一方、当該入力端子に前記ＩＰアドレス未登録情報および前記ＩＰパケットが入力された場合、該ＩＰアドレス未登録情報に基づいて決定される未登録専用の出力端子へ前記ＩＰパケットを出力するＩＰパケットスイッチ手段とを具備することを特徴とする。
【００１０】
請求項４に記載の発明は、各々に入力されるセル流の中から個々のＩＰパケットを再生して、前記ＩＰパケットに記載されているＩＰアドレスを各々出力する複数のＩＰパケット再生手段と、前記複数のＩＰパケット再生手段に対応して各々設けられる請求項１または請求項２に記載の高速検索回路と、前記複数のＩＰパケット再生手段に対応して各々設けられた複数の入力端子と、複数の出力端子とを有し、当該入力端子に前記転送処理情報および前記ＩＰパケットが入力された場合、該転送処理情報により決定される当該出力端子へ前記前記ＩＰパケットを出力し、一方、当該入力端子に前記ＩＰアドレス未登録情報および前記ＩＰパケットが入力された場合、該ＩＰアドレス未登録情報に基づいて決定される未登録専用の出力端子へ前記ＩＰパケットを出力するＩＰパケットスイッチ手段と、前記ＩＰパケットスイッチ手段の前記複数の出力端子に対応して各々設けられ、入力されるＩＰパケットを各々セル化する複数のセル化手段とを具備することを特徴とする。
【００１１】
請求項５に記載の発明は、各々に入力されるセル流からＩＰパケットが収容されているセルを識別し、該セルのＩＰパケットに記載されているＩＰアドレスを各々出力する複数のＩＰパケットセル識別手段と、前記複数のＩＰパケットセル識別手段に対応して各々設けられる請求項１または請求項２に記載の高速検索回路と、前記複数のＩＰパケットセル識別手段に対応して各々設けられ、前記テーブル内の全ての行に対応する、前記ＡＮＤ演算した結果と、登録された前記宛先ＩＰアドレスとの比較結果が全て不一致である場合、ＩＰアドレス未登録情報を各々出力した後、検索を終了する複数の出力手段と、前記複数のＩＰパケットセル識別手段に対応して各々設けられた複数の入力端子と、複数の出力端子とを有し、当該入力端子に前記転送処理情報および前記セルが入力された場合、該転送処理情報により決定される当該出力端子へ前記前記セルを出力し、一方、当該入力端子に前記ＩＰアドレス未登録情報および前記セルが入力された場合、該ＩＰアドレス未登録情報に基づいて決定される未登録専用の出力端子へ前記セルを出力するセルスイッチ手段とを具備することを特徴とする。
【００１５】
【発明の実施の形態】
＜第１実施形態＞
以下、図面を参照して本発明の実施形態について説明する。図１は本発明の第１実施形態によるＩＰパケット転送処理装置における高速検索回路の構成を示すブロック図である。この図に示す高速検索回路１０において、先頭行番号レジスタ１１は、先頭行番号を保持する。ここで、先頭行番号とは、後述するテーブル１５における検索範囲の先頭行を指示する番号をいう。
【００１６】
末尾行番号レジスタ１２は、末尾行番号行を保持する。ここで、末尾行番号とは、テーブル１５における検索範囲の末尾を指示する番号をいう。ただし、上述した先頭行番号レジスタ１１および末尾行番号レジスタ１２に検索開始時に保持される先頭行番号および末尾行番号は、後述する検索の課程において変化する。
【００１７】
中央行番号演算回路１３は、末尾行番号レジスタ１２および中央行番号演算回路１３より各々入力される先頭行番号および末尾行番号で特定される行範囲の中央行を求め、これを中央行番号として出力する。例えば、中央行番号演算回路１３が中央行番号を求める方法として、先頭行番号と末尾行番号の平均加算（小数点以下切り捨て）する、すなわち、先頭行番号と末尾行番号とを加算した後、加算結果のビット列を１ビット右シフトする方法がある。
【００１８】
変換回路１４は、中央行番号演算回路１３より入力される中央行番号に対応する、テーブル１５の登録情報を読み出すためのメモリアドレスを生成する。テーブル１５は、登録すべき宛先ＩＰアドレスとサブネットマスクとＩＰパケットの転送情報とをひとまとめにして一行とした場合に、複数行のデータからなる。このテーブル１５は、予め、宛先ＩＰアドレスを数値と見なして各行を昇順（または降順）にソートしたものから構成されている。
【００１９】
中央行番号レジスタ１６は、中央行番号演算回路１３から入力される中央行番号を保持する。照合回路１７は、検索対象である入力情報のＩＰアドレスが、テーブル１５に登録されているか否かを、中央行番号レジスタ１６に保持されている中央行番号に基づいて、検出する。具体的には、照合回路１７は、中央行番号レジスタ１６に保持されている中央行番号が前回の中央行番号と等しいとき、検索対象であるＩＰアドレスが未登録であることを検出する。
【００２０】
ＡＮＤ演算回路１８は、検索対象である入力情報のＩＰアドレス（３２ビット）と、サブネットマスク（３２ビット構成からなり”１”のもの）とをビット毎にＡＮＤ演算して、演算結果（以下、入力ＩＰアドレスと称する）を出力する。比較器１９は、ＡＮＤ演算回路１８より入力される入力ＩＰアドレスと、テーブル１５より入力される登録ＩＰアドレスとを数値とみなして比較して、次の３種類の結果のうちいずれかのものを出力する。
［ケースＡ］：入力ＩＰアドレス値＝登録ＩＰアドレス値
［ケースＢ］：入力ＩＰアドレス値＜登録ＩＰアドレス値
［ケ一スＣ］：入力ＩＰアドレス値＞登録ＩＰアドレス値
【００２１】
上記［ケースＡ］は、入力ＩＰアドレスと登録ＩＰアドレスとが等しいという結果である。この［ケースＡ］の結果が出た場合には、比較器１９からＩＰアドレス一致パルスが出力されるとともに、テーブル１５から転送処理情報が出力され、検索が終了する。
【００２２】
また、［ケースＢ］は、入力ＩＰアドレスが登録ＩＰアドレスより小であるという結果であり、検索対象である入力情報のＩＰアドレスがテーブル１５における検索範囲の前半、言い換えれば、中央行番号より前にあるという結果である。この［ケースＢ］の結果が出た場合には、中央行番号を末尾行番号レジスタ１２に書き込むための書き込みパルスが比較器１９から末尾行番号レジスタ１２へ供給される。
【００２３】
［ケ一スＣ］は、入力ＩＰアドレスが登録ＩＰアドレスより大であるという結果であり、検索対象である入力情報のＩＰアドレスがテーブル１５における検索範囲の後半、言い換えれば、中央行番号より後にあるという結果である。この［ケ一スＣ］の結果が出た場合には、中央行番号を先頭行番号レジスタ１１に書き込むための書き込みパルスが比較器１９から先頭行番号レジスタ１１へ供給される。
【００２４】
次に、上述した第１実施形態によるＩＰパケット転送処理装置における高速検索回路の動作を説明する。まず、高速検索回路１０を使用する前には、次の初期動作が行われる。すなわち、初期動作においては、登録する宛先ＩＰアドレスとサブネットマスクとＩＰパケットの転送処理情報とがひとまとめ、言い換えれば一行にされたデータが、複数行分のデータされたテーブルが作成される。次に、宛先ＩＰアドレスを数値と見なして各行を昇順（または、降順）にソートしたテーブルが、テーブル１５に転送される。
【００２５】
また、検索開始トリガが入力する前に、最初の検索範囲の先頭行番号と末尾行番号とが、それぞれ先頭行番号レジスタ１１と末尾行番号レジスタ１２に設定される。
例えば、中央行番号演算回路１３が、先頭行番号と末尾行番号の加算平均（小数点以下切り捨て）する、すなわち、先頭行番号と末尾番号とを加算した後、加算演算のビット列を１ビット右シフトするという前述した動作を行う場合には、末尾行番号レジスタ１２に最初に設定される値としては、実際の末尾行番号に１を加算した値が用いられる。また、この場合には、最初に設定される先頭行番号は、０から始まっても、また１から始まっても良い。
【００２６】
次に、検索開始トリガが中央行番号演算回路１３に入力されると、該演算回路１３は、先頭行番号レジスタ１１および末尾行番号レジスタ１２に保持されている先頭行番号および末尾行番号から中央行番号を求める。すなわち、中央行番号演算回路１３は、上記先頭行番号と末尾行番号とを加算した後、加算結果であるビット列を１ビット右シフトした結果を中央行番号として、これを中央行番号レジスタ１６および変換回路１４へ出力する。これにより、中央行番号レジスタ１６には、中央行番号が保持される。
【００２７】
一方、変換回路１４は、入力された中央行番号に対応する、テーブル１５の登録情報を読み出すためのメモリアドレスを生成して、これをテーブル１５へ出力する。これにより、テーブル１５からは、中央行番号に対応する登録情報（登録ＩＰアドレス、サブネットマスク、転送処理情報）が出力される。ただし、上記登録情報のうち登録ＩＰアドレスは、該検索回路１０がホストアドレス以外の部分が一致するＩＰアドレスを検索することを目的としているため、ホストアドレス部分が何であっても良いようにするために、ホストアドレス部分のビットがオール”０”にされる。
【００２８】
そして、テーブル１５より出力されたサブネットマスク（３２ビット）は、ＡＮＤ演算回路１８に入力され、検索対象の入力情報のＩＰアドレスと各ビット毎にＡＮＤ演算され、演算結果（入力ＩＰ［が比較器１９へ出力される。これにより、比較器１９は、ＡＮＤ演算回路１８より入力された入力ＩＰアドレス（３２ビット）とテーブル１５から出力された登録ＩＰアドレス（３２ビット）を比較して、前述した［ケースＡ］、［ケースＢ］または［ケ一スＣ］のうちいずれかの結果を出力する。
【００２９】
ここで、比較器１９において［ケースＡ］の結果が出た場合には、前述したように入力ＩＰアドレスと登録ＩＰアドレスとが等しいということであるから、比較器１９からＩＰアドレス一致パルスが出力されるとともに、テーブル１５から当該登録ＩＰアドレスに対応する転送処理情報が出力され、検索が終了する。
【００３０】
また、比較器１９において［ケースＢ］の結果が出た場合には、前述したように入力ＩＰアドレスが登録ＩＰアドレスより小であるということであるから、比較器１９から書き込みパルスが末尾行番号レジスタ１２へ供給される。これにより、末尾行番号レジスタ１２には、中央行番号演算回路１３から出力されている中央行番号が保持される。すなわち、中央行番号演算回路１３は、上記中央行番号を新しい末尾行番号として、前述した動作と同様にして新たな中央行番号を演算する。つまり、中央行番号演算回路１３における演算が行われる毎に、テーブル１５における検索範囲が順次、半分にしぼり込まれるのである。
【００３１】
また、比較器１９において［ケ一スＣ］の結果が出た場合には、前述したように入力ＩＰアドレスが登録ＩＰアドレスより大であるということから、比較器１９から書き込みパルスが先頭行番号レジスタ１１へ供給される。これにより、先頭行番号レジスタ１１には、中央行番号演算回路１３から出力されている中央行番号が保持される。すなわち、中央行番号演算回路１３は、上記中央行番号を新しい先頭行番号として、前述した動作と同様にして新たな中央行番号を演算する。この中央行番号演算回路１３における演算が行われる毎に、上述したようにテーブル１５における検索範囲が順次、半分にしぼりこまれるのである。
【００３２】
また、検索対象の入力情報のＩＰアドレスがテーブル１５に登録されていない場合には、上述した［ケースＢ］または［ケ一スＣ］の結果に基づいて、検索処理が繰り返されると先頭行番号レジスタ１１および末尾行番号レジスタ１２に保持されるデータが次の状態となる。すなわち、最終的には、先頭行番号レジスタ１１に保持されている先頭行番号と、末尾行番号レジスタ１２に保持されている末尾行番号とが等しいか、または上記末尾行番号が上記開始行番号より１だけ大きいという状態となる。
【００３３】
上述した状態は、照合回路１７において検出される。すなわち、照合回路１７は、中央行番号レジスタ１６に保持されている一つ前の中央行番号と、中央行番号演算回路１３から出力されている今回の中央行番号とを照合して、一つ手前の中央行番号が今回の中央行番号と等しい場合、「ＩＰアドレス未登録」を出力する。一方、照合回路１７は、一つ手前の中央行番号が、今回の中央行番号と異なる場合、検索範囲が今後狭くなるので、今回の中央行番号を中央行番号レジスタ１６に書き込む。
【００３４】
以上、本発明の第１実施形態を図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、本発明の要旨を逸脱しない範囲の設計変更等があっても本発明に含まれる。
例えば、上述した第１実施形態によるＩＰパケット転送処理装置における高速検索回路においては、テーブル１５における宛先ＩＰアドレスのホストアドレス部分の全てのビットを”０”とした後、ＡＮＤ演算回路１８においてＡＮＤ演算をする例について説明したがこれに限定されることはない。すなわち、上述した第１実施形態によるＩＰパケット転送装置においては、テーブル１５における宛先ＩＰアドレスのホストアドレス部分の全てを、上述した”０”に代えて”１”とした後、選択された行におけるサブネットマスクの反転ビット（”０”と”１”とを入れ換えたもの）と宛先ＩＰアドレスとを、上述したＡＮＤ演算回路１８に代えて設けたＯＲ演算回路によってＯＲ演算をするようにしてもよい。
【００３５】
＜第２実施形態＞
図２は、本発明の第２実施形態によるＩＰパケット転送処理装置の構成を示すブロック図である。同図に示すＩＰパケット転送処理装置３０は、上述した図１に示す高速検索回路１０が複数適用されたものである。また、このＩＰパケット転送処理装置は、送信装置（図示略）と受信装置（図示略）との間に介挿されており、送信装置より送出されたＩＰパケットを受信装置へ転送するという機能を有する通信装置の一種である。
【００３６】
図２において、３１１〜３１ｎは、ｎ（自然数）個の入力ＩＦ（インターフェイス）回路であり、各々に入力される各ＩＰパケットに対して、ＭＡＣ（Ｍｅｄｉａ  Ａｃｃｅｓｓ  Ｃｏｎｔｒｏｌ：媒体アクセス制御）フレーム処理等を行い、同処理が施されたＩＰパケットをＩＰパケット流として各々出力する。
また、入力ＩＦ回路３１１〜３１ｎは、必要に応じて各ＩＰパケットに対して、光・電気変換処理やＳＤＨ（Ｓｙｎｃｈｒｏｎｏｕｓ  Ｄｉｇｉｔａｌ  Ｈｉｅｒａｒｃｈｙ：同期ディジタルハイアラーキー）処理を各々行う。
ここで、ＳＤＨ処理とは、光ファイバによるディジタル通信の信号多重化に際し、階層的にチャネルを多重化する処理をいう。
【００３７】
３２１〜３２ｎは、入力ＩＦ回路３１１〜３１ｎに各々対応して設けられたｎ個のＩＰパケット識別回路であり、各々に入力されるＩＰパケット流の中から個々のＩＰパケットを識別する。また、ＩＰパケット識別回路３２１〜３２ｎは、ＩＰパケットの区切り情報と一緒に上記ＩＰパケットを処理回路３５１〜３５ｎへ各々出力するとともに、識別した上記ＩＰパケット内部に記載されているＩＰアドレスを各々読み出し、これらを高速検索回路１０１〜１０ｎへ各々出力する。
処理回路３５１〜３５ｎは、入力されるＩＰアドレス一致／未登録情報、転送情報に基づいて、ＩＰパケットに対して所定の処理を各々行う。この処理回路３５１〜３５ｎの動作の詳細については、後述する。
【００３８】
高速検索回路１０１〜１０ｎは、ＩＰパケット識別回路３２１〜３２ｎに各々対応して設けられた高速検索回路であり、前述した図１に示す高速検索回路１０と同一構成とされている。これら高速検索回路１０１〜１０ｎは、前述したように各々に入力されるＩＰアドレスに基づいて、ＩＰアドレス一致／未登録情報、転送処理情報等（図１参照）を処理回路３５１〜３５ｎへ各々出力する。１５１〜１５ｎは、高速検索回路１０１〜１０ｎ内部に各々設けられたテーブルであり、図１に示すテーブル１５と各々同一構成とされている。
【００３９】
３３は、ｎ個の入力端子および出力端子を有するｎ×ｎ型のＩＰパケットスイッチであり、入力端子に入力される転送処理情報等により決定される当該出力端子へＩＰパケットを出力するというスイッチ機能を有している。
【００４０】
３４１〜３４ｎは、ＩＰパケットスイッチ３３のｎ個の出力端子に各々対応して設けられたｎ個の出力ＩＦ回路である。これら出力ＩＦ回路３４１〜３４ｎは、ＩＰパケットスイッチ３３の出力端子より入力されるＩＰパケットに対して、上述したＭＡＣフレーム処理を行い、このＩＰパケットを受信装置（図示略）へ各々出力する。なお、出力ＩＦ回路３４１〜３４ｎは、必要に応じてＩＰパケットに対して、光・電気変換処理やＳＤＨ処理を行う。
【００４１】
次に、上述した第２実施形態によるＩＰパケット転送処理装置の動作を説明する。図２において、図示しない送信装置より送出されたＩＰパケットが入力ＩＦ回路３１１へ入力されると、該入力ＩＦ回路３１１は、該ＩＰパケットに対してＭＡＣフレーム処理等を行った後、同処理が施されたＩＰパケットをＩＰパケット流としてＩＰパケット識別回路３２１へ出力する。
【００４２】
これにより、ＩＰパケット識別回路３２１は、入力されたＩＰパケット流の中から個々のＩＰパケットを識別した後、ＩＰパケットの区切り情報と、ＩＰパケットとを処理回路３５１へ出力するとともに、上記ＩＰパケット内部に記載されているＩＰアドレスを読み出し、これを高速検索回路１０１へ出力する。
これにより、高速検索回路１０１は、前述した動作と同様にして入力されたＩＰアドレスがテーブル１５１に登録されているか否かを高速で検索する。そして、上記検索が終了すると、高速検索回路１０１は、検索結果に応じてＩＰアドレス一致情報および転送処理情報、またはＩＰアドレス未登録情報を処理回路３５１へ出力する。
【００４３】
そして、今、ＩＰアドレス一致情報および転送処理情報が処理回路３５１に入力されたとすると、処理回路３５１は、当該ＩＰパケットおよび転送処理情報等をＩＰパケットスイッチ３３へ出力する。これにより、ＩＰパケットスイッチ３３は、転送処理情報から出力すべき出力端子を認識した後、該出力端子を介して当該ＩＰパケットを例えば、出力ＩＦ回路３４ｎへ出力する。これにより、出力ＩＦ回路３４ｎは、ＩＰパケットに対してＭＡＣフレーム処理等を行った後、同処理が施されたＩＰパケットを図示しない受信装置へ送出する。
【００４４】
一方、処理回路３５１にＩＰアドレス未登録情報が入力された場合、処理回路３５１は、例えば、未登録用に予め定められたデフォルト転送処理情報および当該ＩＰパケットをＩＰパケットスイッチ３３へ出力する。これによりＩＰパケットスイッチ３３は、上記デフォルト転送情報から出力すべき出力端子を認識した後、該出力端子を介して、当該ＩＰパケットを例えば、出力ＩＦ回路３４２へ出力する。この出力ＩＦ回路３４２は、デフォルト専用のものである。
また、処理回路３５１は、上述したデフォルト転送処理の他、必要に応じてＩＰパケットをＩＰパケットスイッチ３３へ出力することなく廃棄するという処理をも行う。
【００４５】
＜第３実施形態＞
図３は、本発明の第３実施形態によるＩＰパケット転送処理装置の構成を示すブロック図である。同図に示すＩＰパケット転送処理装置４０は、上述した図１に示す高速検索回路１０が複数適用されたものである。このＩＰパケット転送処理装置４０は、セル化されたＩＰパケットを送信する送信装置（図示略）と受信装置（図示略）との間に介挿されており、上記セルを転送処理する装置である。
【００４６】
図３において、図２の各部に対応する部分には、同一の符号を付けその説明を省略する。同図に示すＩＰパケット転送処理装置４０において、４１１〜４１ｎは、ｎ個の入力ＩＦ回路であり、入力されるセル化されたＩＰパケット（以下、単にセルと称する）に対して、光・電気変換処理やＳＤＨ処理等を各々行う。また、上記入力ＩＦ回路４１１〜４１ｎは、同処理が施されたセルをセル流として出力する。
【００４７】
４２１〜４２ｎは、入力ＩＦ回路４１１〜４１ｎに対応して各々設けられたｎ個のＩＰパケット再生回路である。このＩＰパケット再生回路４２１〜４２ｎは、入力されるセル流におけるセルヘッダ内の情報（ＶＰＩ（Ｖｉｒｔｕａｌ  Ｐａｔｈ  Ｉｄｅｎｔｉｆｉｅｒ：仮想パス識別子）、ＶＣＩ（Ｖｉｒｔｕａｌ  Ｃｈａｎｎｅｌ  Ｉｄｅｎｔｉｆｉｅｒ：仮想チャネル識別子）、ペイロードタイプ表示の第３ビット、等）、ＡＡＬ（ＡＴＭ  Ａｄａｐｔａｔｉｏｎ  Ｌａｙｅｒ）ヘッダ情報、ＩＰヘッダ情報等（以下、総称してセル情報と称する）を利用して、セル流から個々のＩＰパケットを各々再生して、このＩＰパケットを処理回路３５１〜３５ｎへ各々出力する。また、ＩＰパケット再生回路４２１〜４２ｎは、再生されたＩＰパケット内部に記載されているＩＰアドレスを読み出し、これらを高速検索回路１０１〜１０ｎへ各々出力する。
【００４８】
４３１〜４３ｎは、ＩＰパケットスイッチ３３のｎ個の出力端子に対応して各々設けられたセル化回路であり、上記出力端子より入力されるＩＰパケットをセル化する。４４１〜４４ｎは、セル化回路４３１〜４３ｎに対応して各々設けられたｎ個の出力ＩＦ回路であり、入力されるセルに対して、ＳＤＨ処理や電気変換・光変換等を各々行う。また、出力ＩＦ回路４４１〜４４ｎは、同処理が施されたセルをセル流として、これらを図示しない受信装置へ各々出力する。
【００４９】
次に、上述した第３実施形態によるＩＰパケット転送処理装置の動作を説明する。図３において、図示しない送信装置よりセル流が入力ＩＦ回路４１１に入力されると、入力ＩＦ回路４１１は、上記セル流に対して光・電気変換処理、ＳＤＨ等の処理を行った後、同処理が施されたセル流をＩＰパケット再生回路４２１へ出力する。
【００５０】
これにより、ＩＰパケット再生回路４２１は、入力されたセル流におけるセル情報を利用して、セル流から個々のＩＰパケットを再生する。次いで、ＩＰパケット再生回路４２１は、ＩＰパケットの区切り情報と一緒にＩＰパケットを処理回路３５１へ転送するとともに、再生されたＩＰパケット内部に記載されているＩＰアドレスを読み出した後、これを高速検索回路１０１へ出力する。
【００５１】
これにより、高速検索回路１０１は、上述した第１実施形態によるＩＰパケット転送処理装置（図１参照）と同様にしてＩＰアドレスの検索処理を高速で行う。  そして、上記検索処理が終了すると、高速検索回路１０１は、検索結果に応じてＩＰアドレス一致情報および転送処理情報、またはＩＰアドレス未登録情報を処理回路３５１へ出力する。
【００５２】
そして、今、ＩＰアドレス一致情報および転送処理情報が処理回路３５１に入力されたとすると、該処理回路３５１は、当該ＩＰパケットおよび転送処理情報等をＩＰパケットスイッチ３３へ出力する。これにより、ＩＰパケットスイッチ３３は、転送処理情報から出力すべき出力端子を認識した後、該出力端子を介して当該ＩＰパケットを例えば、セル化回路４３ｎへ出力する。
【００５３】
これにより、セル化回路４３ｎは、入力されたＩＰパケットをセル化してこれを出力ＩＦ回路４４ｎへ出力する。そして、上記セルは、出力ＩＦ回路４４ｎにおいてＳＤＨ処理や電気変換・光変換等が施された後、図示しない受信装置へ出力される。
【００５４】
一方、処理回路３５１にＩＰアドレス未登録情報が入力された場合、処理回路３５１は、前述した動作と同様にして、デフォルト転送処理またはＩＰパケット廃棄処理を行う。
【００５５】
＜第４実施形態＞
図４は、本発明の第４実施形態によるＩＰパケット転送処理装置の構成を示すブロック図である。同図に示すＩＰパケット転送処理装置５０は、上述した図１に示す高速検索回路１０が複数適用されたものであり、セルベースの装置である。図４において、図３の各部に対応する部分には、同一の符号を付けその説明を省略する。
【００５６】
図４においては、図３に示すＩＰパケット再生回路４２１〜４２ｎに代えてＩＰパケット先頭セル識別回路５２１〜５２ｎが、図３に示す処理回路３５１〜３５ｎに代えて処理回路５５１〜５５ｎが、さらに図３に示すＩＰパケットスイッチ３３に代えてセルスイッチ５３が各々設けられている。また、同図に示すＩＰパケット転送処理装置５０は、図３に示すセル化回路４３１〜４３ｎが設けられていない構成とされている。
【００５７】
上記ＩＰパケット先頭セル識別回路５２１〜５２ｎは、入力ＩＦ回路４１１〜４１ｎに各々対応して設けられており、セルヘッダ内の上述したセル情報を利用して、入力されるセル流からＩＰパケットの先頭が収容されているセルを各々識別する。また、ＩＰパケット先頭セル識別回路５２１〜５２ｎは、ＩＰパケット内部に記載されているＩＰアドレスを各々読み出し、これらを高速検索回路１０１〜１０ｎへ各々出力する。
【００５８】
さらに、ＩＰパケット先頭セル識別回路５２１〜５２ｎは、上述した情報から個々のＩＰパケットをも識別して、ＩＰパケットの区切り情報と一緒にセル流を処理回路５５１〜５５ｎへ各々出力する。なお、ＩＰパケット先頭セル識別回路５２１〜５２ｎは、上述した図３に示すＩＰパケット再生回路４２１〜４２ｎのごとき処理、すなわちＩＰパケットの再生処理を行わない。
【００５９】
セルスイッチ５３は、ｎ個の入力端子および出力端子を有するｎ×ｎ型のスイッチであり、入力端子に入力される転送処理情報により決定される当該出力端子へセルを出力するというスイッチ機能を有している。
【００６０】
次に、上述した第４実施形態によるＩＰパケット転送処理装置の動作を説明する。図４において、図示しない送信装置よりセル流が入力ＩＦ回路４１１に入力されると、このセル流は、光・電気変換処理、ＳＤＨ等の処理が施された後、ＩＰパケット先頭セル識別回路５２１に入力される。
【００６１】
これにより、ＩＰパケット先頭セル識別回路５２１は、セルヘッダ内の上述したセル情報を利用して、入力されるセル流からＩＰパケットの先頭が収容されているセルを識別する。次に、ＩＰパケット先頭セル識別回路５２１は、上記ＩＰパケット内部に記載されているＩＰアドレスを各々読み出し、これを高速検索回路１０１へ出力する。
また、ＩＰパケット先頭セル識別回路５２１は、セルヘッダ内の情報等から個々のＩＰパケットを識別し、ＩＰパケットの区切り情報と一緒にセル流を処理回路５５１へ出力する。
【００６２】
これにより、高速検索回路１０１は、前述した検索結果に応じてＩＰアドレス一致情報および転送処理情報、またはＩＰアドレス未登録情報を処理回路５５１へ出力する。
【００６３】
そして、今、ＩＰアドレス一致情報および転送処理情報が処理回路５５１に入力されたとすると、該処理回路５５１は、当該セルおよび転送処理情報等をセルスイッチ５３へ出力する。
【００６４】
これにより、セルスイッチ５３は、転送処理情報から出力すべき出力端子を認識した後、該出力端子を介して当該セルを例えば、出力ＩＦ回路４４ｎへ出力する。そして、上記セルは、出力ＩＦ回路４４ｎにおいてＳＤＨ処理や電気変換・光変換等が施された後、図示しない受信装置へ出力される。
【００６５】
一方、処理回路５５１へＩＰアドレス未登録情報が入力されたとすると、該処理回路５５１は、例えば、未登録用に予め定められたデフォルト転送処理情報と共に、そのＩＰパケットに属するセルをセルスイッチ５３へ出力する。
これにより、セルスイッチ５３は、セルと共に入力されたデフォルト転送処理情報にから当該セルを出力すべき出力端子を認識した後、該出力端子を介して、例えば、出力ＩＦ回路４４２へセルを出力する。
また、処理回路５５１は、上述したデフォルト転送処理または当該ＩＰパケットに属するセルを廃棄するという廃棄処理を行う。
【００６６】
【発明の効果】
本発明によれば、従来のソフトウェアに代えてハードウェアにより動作するので、宛先ＩＰアドレスをキーとしたＩＰパケットの転送宛先情報の検索処理を従来より高速に行え、かつ大量に高速で入力するＩＰパケットを受信して瞬時に宛先につながる方路に出力することができるという効果が得られる。
【図面の簡単な説明】
【図１】本発明の第１実施形態によるＩＰパケット転送処理装置における高速検索回路の構成を示すブロック図である。
【図２】同第２実施形態によるＩＰパケット転送処理装置の構成を示すブロック図である。
【図３】同第３実施形態によるＩＰパケット転送処理装置の構成を示すブロック図である。
【図４】同第４実施形態によるＩＰパケット転送処理装置の構成を示すブロック図である。
【符号の説明】
１０、１０１〜１０ｎ  高速検索回路
１１  先頭行番号レジスタ
１２  末尾行番号レジスタ
１３  中央行番号演算回路
１４  変換回路
１５、１５１〜１５ｎ  テーブル
１６  中央行番号レジスタ
１７  照合回路
１８  ＡＮＤ演算回路
１９  比較器
３０、４０、５０  ＩＰパケット転送処理装置
３１１〜３１ｎ  入力ＩＦ回路
３２１〜３２ｎ  ＩＰパケット識別回路
３３  ＩＰパケットスイッチ
３４１〜３４ｎ  出力ＩＦ回路
３５１〜３５ｎ  処理回路
４１１〜４１ｎ  入力ＩＦ回路
４２１〜４２ｎ  ＩＰパケット再生回路
４３１〜４３ｎ  セル化回路
４４１〜４４ｎ  出力ＩＦ回路
５２１〜５２ｎ  ＩＰパケット先頭セル識別回路
５３  セルスイッチ
５５１〜５５ｎ  処理回路
【図１】
0003573319.tif 000002
【図２】
0003573319.tif 000003
【図３】
0003573319.tif 000004
【図４】
0003573319.tif 000005