(57)【特許請求の範囲】
【請求項１】
パケットのヘッダ部に含まれる宛先アドレスに基づいて、前記パケットの宛先アドレスを検索する宛先検索システムにおいて、
前記パケットのヘッダ部は、各々宛先アドレスを有する複数段のヘッダを有するように構成されると共に、
受信したパケットを記憶するパケット記憶手段と、
パケットのアドレス情報を格納したアドレス情報テーブルを記憶すると共に、検索結果に応じた返り値を出力するアドレス情報記憶手段と、
前記パケット記憶手段に記憶したパケットのヘッダ情報から検索キーを生成して、前記検索キーに基づいて前記アドレス情報記憶手段の前記アドレス情報テーブルを検索し、前記アドレス情報記憶手段から内部ヘッダを有する旨の返り値を受けて、前記パケット記憶手段に記憶したパケットの内部ヘッダ情報から検索キーを生成すると共に、該検索キーに基づいて前記アドレス情報記憶手段の前記アドレス情報テーブルを検索するアドレス検索処理手段とを備えて成ることを特徴とするパケットの宛先検索システム。
【請求項２】
前記アドレス検索処理手段は、
アドレス検索指示に応答して前記パケット記憶手段に記憶したパケットのヘッダ情報から検索キーを生成すると共に、内部ヘッダ抽出指示に応答して前記パケット記憶手段に記憶したパケットの内部ヘッダ情報から前記検索キーを生成する検索キー生成手段と、
前記検索キーに基づいて、前記アドレス情報記憶手段の前記アドレス情報テーブルを検索すると共に、前記アドレス情報記憶手段から内部ヘッダを有する旨の返り値を受けて、前記内部ヘッダ抽出指示を行う検索手段とを備えて成ることを特徴とする請求項１記載のパケットのアドレス検索システム。
【請求項３】
パケットのヘッダ部に含まれる宛先アドレスに基づいて、前記パケットの宛先アドレスを検索する宛先検索システムにおいて、
前記パケットのヘッダ部は、各々宛先アドレスを有する複数段のヘッダを有するように構成されると共に、
受信したパケットを記憶するパケット記憶手段と、
パケットのアドレス情報を格納したアドレス情報テーブルを記憶すると共に、複数段分のヘッダに相当するヘッダデータを検索キーとして検索可能なアドレス情報記憶手段と、
複数段分のヘッダに相当するヘッダデータを抽出し、該抽出したヘッダデータを用いて前記アドレス情報記憶手段に記憶したアドレス情報テーブルを検索するアドレス検索処理手段とを備えて成ることを特徴とするパケットの宛先検索システム。
【請求項４】
前記アドレス検索処理手段は、
複数段分のヘッダに相当するヘッダデータを抽出するヘッダデータ抽出手段と、前記ヘッダデータ抽出手段で抽出したヘッダデータを用いて前記アドレス情報記憶手段に記憶したアドレス情報テーブルを検索する検索手段とを備えて成ることを特徴とする請求項３記載のパケットの宛先検索システム。
【請求項５】
パケットのヘッダ部に含まれる宛先アドレスに基づいて、前記パケットの宛先アドレスを検索する宛先検索システムにおいて、
前記パケットのヘッダ部は、各々宛先アドレスを有する複数段のヘッダを有するように構成されると共に、
パケットを記憶するパケット記憶手段と、
受信したパケットを前記パケット記憶手段に記憶するパケット受信手段と、
パケットのアドレス情報を格納したアドレス情報テーブルを記憶すると共に、検索結果に応じた返り値を出力するアドレス情報記憶手段と、
前記パケット記憶手段に記憶したパケットに対して付与された抽出位置指定情報に対応する位置のヘッダの情報から検索キーを生成し、前記検索キーに基づいて前記アドレス情報記憶手段の前記アドレス情報テーブルを検索すると共に、前記アドレス情報記憶手段から内部ヘッダを有する旨の返り値を受けて、ヘッダの新たな抽出位置指定情報をパケットに付与して前記パケット受信手段に転送するアドレス検索処理手段とを備えて成ることを特徴とするパケットの宛先検索システム。
【請求項６】
前記アドレス検索処理手段は、
パケットに付与された抽出位置指定情報に対応する位置のヘッダの情報から検索キーを生成する検索キー生成手段と、
前記検索キーに基づいて前記アドレス情報記憶手段の前記アドレス情報テーブルを検索すると共に、前記アドレス情報記憶手段から内部ヘッダを有する旨の返り値を受けて、パケットを帰還させるための帰還処理指示を行う検索手段と、
前記検索手段から前記帰還処理指示を受けて、ヘッダの抽出位置指定情報を前記パケットに付与し、該パケットをスイッチを経由して前記パケット受信手段に転送する転送手段とを備えて成ることを特徴とする請求項５記載のパケットの宛先検索システム。
【請求項７】
前記検索手段は、更に、前記検索結果に応じたヘッダ書き換え情報を出力すると共に、前記ヘッダ書き換え情報に応答して前記パケット記憶手段に記憶したパケットのヘッダを書き換えるヘッダ変換手段を備えて成ることを特徴とする請求項１乃至６のいずれか一に記載のパケットのアドレス検索システム。
【請求項８】
前記アドレス検索処理手段はハードウェアによって構成されていることを特徴とする請求項１乃至７のいずれか一に記載のパケットのアドレス検索システム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、パケットを送信すべき宛先を検索する宛先検索システムに関し、特に、宛先検索を高速に行うことを可能とする宛先検索システムに関する。
【０００２】
【従来の技術】
従来から、パケットヘッダに記述された内容からパケットを転送するべき宛先の解決を行うために、宛先検索システムが使用されている（例えば、特開平１１−１８７０２４号公報、特開２０００−２４４５７１号公報、特開２０００−１５１７０９号公報参照。）。
図１１は、従来の宛先検索システムの一例を示すブロック図である。
図１１において、パケット受信部１３０は、宛先を決定する必要のあるパケットの受信を行う。パケットバッファ１００は、受信したパケットを格納するメモリである。
【０００３】
パケット送信部１４０は、宛先が決定されたパケットの送信、あるいはＣＰＵ部１５０へパケットの転送を行う。アドレス検索処理部１１０は、パケットバッファ１００に格納されたパケットの宛先を解決する処理を行う。アドレス情報記憶部１２０は、宛先アドレスに対応するパケットの宛先を検索するためのテーブルを格納するメモリである。ＣＰＵ部１５０は、プログラムを実行することによってアドレス検索処理部１１０における例外処理などを行う。
【０００４】
図１２は、アドレス検索処理部１１０の内部ブロックを示す。
図１２において、ヘッダ抽出・検索法判定部１１１は、パケットバッファに格納されたパケットからヘッダを抽出し、パケット種別を示す部分から検索法を決定する。
ここで、パケット種別によってアドレスの位置及びサイズ、宛先決定のために必要な情報（アドレス等）の数が異なるため、テーブル検索に使用するアドレスの位置、サイズ、その他の必要な情報の数、抽出位置を決定し、アドレス検索に必要となる情報をどのようにテーブル検索部１１２に渡すかが予め決められている。このようなアドレス検索に必要な情報を検索法と称し、前記検索法はテーブル検索部１１２が使用する検索キーに相当する。
【０００５】
また、パケット種別としては、例えば、ＩＰｖ（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ  ｖｅｒｓｉｏｎ）４、ＩＰｖ６、ＭＰＬＳ（Ｍｕｌｔｉｐｒｏｔｏｃｏｌ  Ｌａｂｅｌ  Ｓｗｉｔｃｈｉｎｇ）等のパケットがある。
テーブル検索部１１２は、該ヘッダ抽出・検索法判定部１１１から指定された検索法に応じて、アドレス情報記憶部１２０に格納された複数のアドレス情報テーブルの中からパケット種別に応じたアドレス情報テーブル１２１を選択する処理と、選択したアドレス情報テーブル１２１を用いて宛先を検索する処理を行う。ヘッダ変換部１１３は、該テーブル検索部１１２から渡された宛先に応じた編集処理と、パケット送信時に必要とされる編集処理をパケットバッファ１００に格納されたパケットに対して行う。
【０００６】
図１３は、前記宛先検索システムのパケット受信時の動作を示すフローチャートである。
パケットがパケット受信部１３０において受信されると、該パケット受信部１３０はパケットをパケットバッファに格納し、アドレス検索指示をアドレス検索処理部１１０に送出する（ステップ２００）。
該アドレス検索処理部１１０のヘッダ抽出・検索法判定部１１１は、この指示を受けるとパケットバッファ１００からヘッダ部分の抽出を行い、パケット種別を判断する。
この後、ヘッダ抽出・検索法判定部１１１は、パケット種別とヘッダのアドレス部分をテーブル検索部１１２に送信する（ステップ２１０）。
【０００７】
テーブル検索部１１２は、アドレス情報記憶部１２０に格納された複数のアドレス情報テーブルの中から、渡されたパケット種別に対応するアドレス情報テーブル１２１を選択した後、前記アドレスを用いてアドレス情報テーブル１２１を検索し、宛先情報を取得する（ステップ２２０）。
宛先の検索が完了すると、テーブル検索部１１２からの宛先情報とヘッダ抽出・検索法判定部１１１からのヘッダ及びパケット種別情報を取得したヘッダ変換部１１３は、パケットバッファ１００に格納された該パケットのヘッダ部分の宛先情報に応じた編集およびパケット送信時に必要とされるヘッダの更新処理を行った後、パケット送出指示をパケット送信部１４０に送出する（ステップ２３０）。
【０００８】
該パケット送出指示を受信したパケット送信部１４０は、前記パケット送出指示に応じた宛先へパケットバッファ１００に格納されたパケットを送信する。
アドレス検索処理部１１０において宛先が解決できないパケットである場合、パケット処理はＣＰＵ部１５０で行う。この場合、ＣＰＵ部１５０はパケットバッファ１００に格納されたパケットをプログラムされた内容にしたがって処理する。
【０００９】
【発明が解決しようとする課題】
前記従来の宛先検索システムの問題点は、二種類のアドレス空間を使い分けるために、図１５に示すような内部ヘッダ（カプセル化される側のヘッダ）のアドレスで運用される網と外部ヘッダ（カプセル化する側のヘッダ）のアドレスで運用される網において、内部ヘッダのアドレスで運用される網４１０、４２０、４３０間のパケットを外部ヘッダのアドレスで運用される網を図１４（Ｂ）に示すようなカプセル化を用いて転送する二段ヘッダ対応パケット交換装置に、従来の宛先検索システムを適用しても高速な宛先解決を行うことができないという点である。
【００１０】
その理由は、従来の宛先検索システムにおいては、図１４の（Ａ）に示すような宛先解決が必要なヘッダ３０１が一段のパケット３００の処理しか高速な宛先解決処理を行うことができず、図１４の（Ｂ）に示すようなヘッダが多段、すなわち外部ヘッダ３１１と内部ヘッダ３１２が付与されるパケット３１０に対して要求される図１６に示すアドレス検索が複数回必要な処理に対しては、各パケット交換装置４１５、４２５、４３５において、低速となるＣＰＵ部において図１６に示す処理を行うことになるためである。
【００１１】
即ち、図１６において、ＣＰＵ部１５０は、まず、外部アドレス網からのパケットか否かを判断し（ステップ５００）、外部ヘッダアドレス網からのパケットではないと判断した場合、内部ヘッダの内容を検索する（ステップ５１０）。次に、外部ヘッダアドレス網へ転送必要か否かを判断し（ステップ５２０）、外部ヘッダアドレス網への転送が不要と判断した場合には内部ヘッダアドレス網へ転送する（ステップ５４０）。ステップ５２０において、外部ヘッダアドレス網への転送が必要と判断した場合にはパケットに外部ヘッダを追加して（ステップ５３０）、外部ヘッダアドレス網へ転送する（ステップ５８０）。
【００１２】
一方、ステップ５００において、外部アドレス網からのパケットであると判断した場合には、外部ヘッダの内容を検索する（ステップ５５０）。次に、内部ヘッダアドレス網へ転送必要か否かを判断し（ステップ５６０）、内部ヘッダアドレス網への転送が不要と判断した場合には外部ヘッダアドレス網へ転送する（ステップ５８０）。ステップ５６０において、外部ヘッダアドレス網への転送が必要と判断した場合にはパケットの外部ヘッダを削除して（ステップ５７０）、内部ヘッダアドレス網へ転送する（ステップ５４０）。
【００１３】
一般にＣＰＵ部１５０に転送されたパケットの処理は、アドレス検索処理部１１０で宛先解決処理を行うよりもはるかに処理速度が遅いため、複数のヘッダが付与されたパケットの場合には、迅速な宛先の検索処理が困難という問題がある。
また、内部ヘッダを使用する網や外部ヘッダを使用する網のみならず、他のヘッダを使用する網を利用する場合、即ち、３段以上のヘッダを使用する場合にも前記同様の問題がある。
【００１４】
本発明は、カプセル化のように複数のヘッダが付与されたパケットに対しても、高速な宛先検索を可能にすることを課題としている。
【００１５】
【課題を解決するための手段】
本発明によれば、パケットのヘッダ部に含まれる宛先アドレスに基づいて、前記パケットの宛先アドレスを検索する宛先検索システムにおいて、前記パケットのヘッダ部は、各々宛先アドレスを有する複数段のヘッダを有するように構成されると共に、受信したパケットを記憶するパケット記憶手段と、パケットのアドレス情報を格納したアドレス情報テーブルを記憶すると共に、検索結果に応じた返り値を出力するアドレス情報記憶手段と、前記パケット記憶手段に記憶したパケットのヘッダ情報から検索キーを生成して、前記検索キーに基づいて前記アドレス情報記憶手段の前記アドレス情報テーブルを検索し、前記アドレス情報記憶手段から内部ヘッダを有する旨の返り値を受けて、前記パケット記憶手段に記憶したパケットの内部ヘッダ情報から検索キーを生成すると共に、該検索キーに基づいて前記アドレス情報記憶手段の前記アドレス情報テーブルを検索するアドレス検索処理手段とを備えて成ることを特徴とするパケットの宛先検索システムが提供される。
【００１６】
アドレス検索処理手段は、パケット記憶手段に記憶したパケットのヘッダ情報から検索キーを生成して、前記検索キーに基づいてアドレス情報記憶手段のアドレス情報テーブルを検索し、前記アドレス情報記憶手段から内部ヘッダを有する旨の返り値を受けて、前記パケット記憶手段に記憶したパケットの内部ヘッダ情報から検索キーを生成すると共に、該検索キーに基づいて前記アドレス情報記憶手段の前記アドレス情報テーブルを検索する。
【００１７】
ここで、前記アドレス検索処理手段は、アドレス検索指示に応答して前記パケット記憶手段に記憶したパケットのヘッダ情報から検索キーを生成すると共に、内部ヘッダ抽出指示に応答して前記パケット記憶手段に記憶したパケットの内部ヘッダ情報から前記検索キーを生成する検索キー生成手段と、前記検索キーに基づいて、前記アドレス情報記憶手段の前記アドレス情報テーブルを検索すると共に、前記アドレス情報記憶手段から内部ヘッダを有する旨の返り値を受けて、前記内部ヘッダ抽出指示を行う検索手段とを備えて成るように構成してもよい。
【００１８】
また、本発明によれば、パケットのヘッダ部に含まれる宛先アドレスに基づいて、前記パケットの宛先アドレスを検索する宛先検索システムにおいて、前記パケットのヘッダ部は、各々宛先アドレスを有する複数段のヘッダを有するように構成されると共に、受信したパケットを記憶するパケット記憶手段と、パケットのアドレス情報を格納したアドレス情報テーブルを記憶すると共に、複数段分のヘッダに相当するヘッダデータを検索キーとして検索可能なアドレス情報記憶手段と、複数段分のヘッダに相当するヘッダデータを抽出し、該抽出したヘッダデータを用いて前記アドレス情報記憶手段に記憶したアドレス情報テーブルを検索するアドレス検索処理手段とを備えて成ることを特徴とするパケットの宛先検索システムが提供される。
【００１９】
アドレス情報記憶手段は、複数段分のヘッダに相当するヘッダデータを抽出し、該抽出したヘッダデータを用いてアドレス情報記憶手段に記憶したアドレス情報テーブルを検索する。
ここで、前記アドレス検索処理手段は、複数段分のヘッダに相当するヘッダデータを抽出するヘッダデータ抽出手段と、前記ヘッダデータ抽出手段で抽出したヘッダデータを用いて前記アドレス情報記憶手段に記憶したアドレス情報テーブルを検索する検索手段とを備えて成るように構成してもよい。
【００２０】
また、本発明によれば、パケットのヘッダ部に含まれる宛先アドレスに基づいて、前記パケットの宛先アドレスを検索する宛先検索システムにおいて、前記パケットのヘッダ部は、各々宛先アドレスを有する複数段のヘッダを有するように構成されると共に、パケットを記憶するパケット記憶手段と、受信したパケットを前記パケット記憶手段に記憶するパケット受信手段と、パケットのアドレス情報を格納したアドレス情報テーブルを記憶すると共に、検索結果に応じた返り値を出力するアドレス情報記憶手段と、前記パケット記憶手段に記憶したパケットに対して付与された抽出位置指定情報に対応する位置のヘッダの情報から検索キーを生成し、前記検索キーに基づいて前記アドレス情報記憶手段の前記アドレス情報テーブルを検索すると共に、前記アドレス情報記憶手段から内部ヘッダを有する旨の返り値を受けて、ヘッダの新たな抽出位置指定情報をパケットに付与して前記パケット受信手段に転送するアドレス検索処理手段とを備えて成ることを特徴とするパケットの宛先検索システムが提供される。
【００２１】
アドレス検索処理手段は、パケット記憶手段に記憶したパケットに対して付与された抽出位置指定情報に対応する位置のヘッダの情報から検索キーを生成し、前記検索キーに基づいてアドレス情報記憶手段のアドレス情報テーブルを検索すると共に、前記アドレス情報記憶手段から内部ヘッダを有する旨の返り値を受けて、ヘッダの新たな抽出位置指定情報をパケットに付与してパケット受信手段に転送する。これにより、新たなヘッダからの検索キーによって検索処理が行われる。
【００２２】
ここで、前記アドレス検索処理手段は、パケットに付与された抽出位置指定情報に対応する位置のヘッダの情報から検索キーを生成する検索キー生成手段と、前記検索キーに基づいて前記アドレス情報記憶手段の前記アドレス情報テーブルを検索すると共に、前記アドレス情報記憶手段から内部ヘッダを有する旨の返り値を受けて、パケットを帰還させるための帰還処理指示を行う検索手段と、前記検索手段から前記帰還処理指示を受けて、ヘッダの抽出位置指定情報を前記パケットに付与し、該パケットをスイッチを経由して前記パケット受信手段に転送する転送手段とを備えて成るように構成してもよい。
【００２３】
また、前記各検索手段は、更に、前記検索結果に応じたヘッダ書き換え情報を出力すると共に、前記ヘッダ書き換え情報に応答して前記パケット記憶手段に記憶したパケットのヘッダを書き換えるヘッダ変換手段を備えて成るように構成してもよい。
また、前記各アドレス検索処理手段の構成全てをハードウェアによって構成することが好ましい。
【００２４】
【発明の実施の形態】
次に、本発明の実施の形態に係る宛先検索システムについて説明する。尚、以下の各実施の形態で使用するパケットは、そのヘッダ部に、各々宛先アドレスを有する複数段のヘッダを有している。
図１は、本発明の第１の実施の形態に係る宛先検索システムのブロック図で、図１１と同一機能を有する部分には同一符号を付している。
【００２５】
図１において、パケット受信部１３０は、パケットスイッチから宛先を決定する必要のあるパケットの受信を行うものであり、パケット受信手段を構成している。パケットバッファ１００は、パケット受信部１３０が受信したパケットを格納するメモリであり、パケット記憶手段を構成している。パケット送信部１４０は、宛先が決定されたパケットをパケットスイッチへ送信するものであり、パケット送信手段を構成している。多段段アドレス検索処理部６１０はハードウェアによって構成されており、後述する処理を行うことにより、パケットバッファ１００に格納したパケットの宛先解決処理を行うものであり、アドレス検索処理手段を構成している。
【００２６】
アドレス情報記憶部６２０は、ＣＡＭ（Ｃｏｎｔｅｎｔ  Ａｄｄｒｅｓｓａｂｌｅ  Ｍｅｍｏｒｙ）等によって構成され、宛先アドレスに対応するパケットの宛先を検索するためのアドレス情報を記憶したアドレス情報テーブルを格納したメモリであり、アドレス情報記憶手段を構成している。アドレス情報記憶部６２０には、パケットのヘッダの深度毎に、パケットの宛先検索用のアドレス情報テーブルが複数格納されている。前記アドレス情報テーブルは、パケットの種別毎に設けられており、各パケット種別毎に、ヘッダ深度毎に分けられた複数のアドレス情報テーブルが格納されている。これにより、同一種別のパケットの場合でも、パケットヘッダの深度が異なるアドレス空間を使用して、アドレス情報テーブルを検索することが可能になる。
【００２７】
図２は、多段段アドレス検索処理部６１０の詳細を示すブロック図である。
多段アドレス検索処理部６１０において、ヘッダ抽出・検索法判定部６１１は、多段テーブル検索部６１２からのヘッダ抽出要求によって内部ヘッダ（カプセル化される方のヘッダ）部分の抽出を行う機能が、図１２のヘッダ抽出・検索法判定部１１１の機能に追加されている。
ヘッダ抽出・検索法判定部６１１は、前記ヘッダ抽出要求に応答して内部ヘッダ部分の抽出を行い、検索法を指示する情報である検索キーを生成して多段テーブル検索部６１２に与える検索キー生成手段を構成している。
【００２８】
多段テーブル検索部６１２は、アドレス情報テーブルを検索して、アドレス情報テーブルからの返り値に含まれる内部ヘッダ処理指定フラグの値を判断することによってパケットが内部ヘッダを有することを検索結果として取得し、内部ヘッダの抽出をヘッダ抽出・検索法判定部６１１に指示し、ヘッダ抽出・検索法判定部６１１から内部ヘッダを渡された場合、内部ヘッダのアドレスによって対応するアドレス情報テーブルを検索し、ヘッダ変換部６１３に外部ヘッダ（カプセル化する方のヘッダ）を削除する指示を行う機能を有している。
【００２９】
また、多段テーブル検索部６１２は、アドレス情報テーブルの検索の結果、アドレス情報テーブルからの返り値に含まれる外部ヘッダ追加フラグの値を判断することにより、パケットに対して外部ヘッダを付与する必要があるという情報を取得し、外部ヘッダ追加指示と追加すべき外部ヘッダ情報をヘッダ変換部６１３に転送する機能とを有している。尚、多段テーブル検索部６１２は検索手段を構成している。
【００３０】
ヘッダ変換部６１３は、図１２のヘッダ変換部１１３の機能に加えて多段テーブル検索部６１２からの外部ヘッダ削除、追加指示を受けヘッダ削除、追加を行う機能を有する。ヘッダ変換部６１３はヘッダ変換手段を構成している。
アドレス情報記憶部６２０は、パケットヘッダの深度毎に且つパケットの種別毎に、パケットの宛先検索用のアドレス情報テーブルを複数格納しており、図２には１つのパケット種別に対応して設けられると共に３種類の深度に対応する３種類のアドレス情報テーブル６２１〜６２３を格納した例を示している。例えば、アドレス情報テーブル６２１は、あるパケット種別の深度が１（１段ヘッダ）の外部アドレス情報テーブルであり又、アドレス情報テーブル６２２は、アドレス情報テーブル６２１と同一パケット種別で深度が２（２段ヘッダ）のアドレス情報テーブルであり、又、アドレス情報テーブル６２３は、アドレス情報テーブル６２１、６２１と同一パケット種別で深度が３（３段ヘッダ）のアドレス情報テーブルである。また、アドレス検索情報テーブル６２１〜６２３は、多段テーブル検索部６１２が外部ヘッダ、内部ヘッダのアドレスに対する宛先と外部ヘッダの追加の要否、外部ヘッダ削除の要否を検索可能とするアドレス情報テーブルである。
【００３１】
尚、多段テーブル検索部６１２が検索に使用する検索キーとしては、ヘッダのアドレス情報等があり、多段テーブル検索部６１２がアドレス情報記憶部６２０のアドレス情報テーブルを検索することによって得られる返り値としては、送信先情報（宛先方路、宛先ＭＴＵ等）、ヘッダ処理情報（ヘッダ更新情報、内部ヘッダ処理フラグ、外部ヘッダ追加フラグ、追加用外部ヘッダ情報）がある。
【００３２】
図３は、図１、図２の多段アドレス検索処理部６１０の動作を説明するためのフローチャートである。
本第１の実施の形態は、内部ヘッダの抽出を実現する手段（図２のヘッダ抽出・検索法判定部６１１）と、内部ヘッダの存在の検知、及び内部ヘッダの検索、ヘッダの追加削除の検索を実現する手段（図２の多段テーブル検索部６１２）と、ヘッダの追加削除、内部ヘッダの有無を検索ためのデータを格納する手段（図２のアドレス情報記憶部６２０）とを有することにより、宛先検索システムは、多段のヘッダが使用されるパケットの宛先及びパケットのヘッダの追加、削除を行うことを可能とするものである。以下、図１〜図３を参照して、本第１の実施の形態の動作を詳細に説明する。
【００３３】
図３の処理ステップ７００で、図１のパケット受信部１３０は受信したパケットをパケットバッファ１００に格納し、図２のヘッダ抽出・検索法判定部６１１にアドレス検索指示を送信する。
前記アドレス検索指示を受け取ったヘッダ抽出・検索法判定部６１１は、パケットバッファ１００に格納した対応するパケットのヘッダを抽出し、前記ヘッダからパケット種別を判定した後、パケット種別情報、ヘッダ深度（ヘッダの段数）の情報及び検索キーを多段テーブル検索部６１２へ通知して検索指示を通知する（ステップ７１０）。ヘッダ抽出・検索法判定部６１１は、前記ヘッダ深度情報を最初は１として多段テーブル検索部６１２にアドレス検索指示を通知する。
【００３４】
前記通知を受け取った多段テーブル検索部６１２は、複数のアドレス情報テーブル６２１〜６２３の中のパケット種別及びヘッダ深度情報に対応するアドレス情報テーブルを選択し、前記検索キーに基づいて、該選択したアドレス情報テーブルの検索を行い（ステップ７２０）、返り値に含まれる内部処理ヘッダフラグの値を判別することにより、内部ヘッダ処理が必要か否かを判断する（ステップ７３０）。尚、前記内部ヘッダ処理とは、内部ヘッダに対して、ヘッダの抽出処理、パケット種別の判定、アドレス情報テーブル検索（ステップ７６０、７１０、７２０）という一連の処理を意味している。
【００３５】
内部処理が必要か否かの判断は、各段のヘッダの情報には、最終段のヘッダのみが最終段のヘッダである旨の情報を含むようにし、あるいは、最終段以外のヘッダには最終段のヘッダでない旨の情報を含むようにしておくことにより、多段テーブル検索部６１２が検索した際に、アドレス情報記憶部６２０から最手段のヘッダでない旨の返り値、即ち、内部ヘッダ処理が必要である旨の返り値を多段テーブル検索部６１２に返すよう構成する等の方法を採用することにより行うことができる。
【００３６】
ステップ７３０において多段テーブル検索部６１２は、内部ヘッダ処理が必要と判断した場合、前記検索に用いたヘッダ深度に１を加えた新たなヘッド深度（この場合はヘッダ深度が２）の情報とともに内部ヘッダ抽出指示をヘッダ抽出・検索法判定部６１１に送信する（ステップ７６０）。
ヘッダ抽出・検索法判定部６１１は、前記ヘッダ深度情報及び前記内部ヘッダ抽出指示を受け取り、前記ヘッダ深度情報に対応する深度のヘッダを抽出し、前記ヘッダ深度情報、パケット種別及び検索キーとともにアドレス検索指示を多段テーブル検索部６１２に送信する。
【００３７】
前記通知を受け取った多段テーブル検索部６１２は、複数のアドレス情報テーブル６２１〜６２３の中のパケット種別及びヘッダ深度情報（この場合はヘッダ深度が２）に対応するアドレス情報テーブルを選択し、前記検索キーに基づいて、該選択したアドレス情報テーブルの検索を行い（ステップ７２０）、この検索の結果、内部ヘッダ処理が必要か否かを判断する（ステップ７３０）。以下、全ての段のヘッダに対してステップ７１０、７２０、７３０、７６０の処理を繰り返す。
【００３８】
ステップ７３０において、多段テーブル検索部６１２は、内部ヘッダの処理が必要でないと判断した場合、検索結果から外部ヘッダ追加処理が必要であるか否かを判断する（ステップ７４０）。多段テーブル検索部６１２は、アドレス情報テーブルからの返り値に含まれる外部ヘッダ追加フラグの値を判定することによって外部ヘッダの追加処理が必要であると判断した場合には、外部ヘッダ追加指示及び追加すべき外部ヘッダ情報をヘッダ変換部６１３に送信し（ステップ７７０）、ヘッダ変換部６１３は、外部ヘッダの追加、宛先に応じたヘッダ変更（例えば、宛先用の下位レイヤヘッダ追加処理）、ヘッダ更新処理（例えば、ループ防止カウンタの減算やそれに伴うチェックサム更新）を行いパケット送出指示をパケット送信部１４０に送信する（ステップ７５０）。
【００３９】
ステップ７４０において、多段テーブル検索部６１２は、外部ヘッダ追加処理が必要ないと判定した場合には、検索した結果をヘッダ変換部６１３に送信する。この場合、ステップ７２０、７３０、７６０での検索により宛先が検索されるので、多段テーブル検索部６１２は、外部ヘッダ削除要求と宛先情報をヘッダ変換部６１３に送信する。
これを受信したヘッダ変換部６１３は、ヘッダの書き換え処理を行った後、パケット送出指示をパケット送信部１４０に送信する（ステップ７５０）。
【００４０】
以上のように、本第１の実施の形態に係るパケットの宛先検索システムは、特に、多段アドレス検索処理部６１０が、アドレス検索指示に応答してパケットバッファ１００に記憶したパケットのヘッダ情報から検索キーを生成すると共に、内部ヘッダ抽出指示に応答してパケットバッファ１００に記憶したパケットの内部ヘッダ情報から前記検索キーを生成するヘッダ抽出・検索法判定部６１１と、前記検索キーに基づいて、アドレス情報記憶部６２０のアドレス情報テーブル６２１〜６２３を検索すると共に、アドレス情報記憶部６２０から内部ヘッダを有する旨の返り値を受けて、内部ヘッダ抽出指示を行う多段テーブル検索部６１２とを備えて成ることを特徴としている。
したがって、ヘッダ部に複数のヘッダを有するパケットを受信した場合でも、ハードウェア構成された多段アドレス検索処理部６１０によって宛先検索処理が行われるため、ＣＰＵを用いてパケットを処理する必要がなくなり、多段ヘッダを有したパケットの転送処理が高速化される。
【００４１】
次に、本発明の第２の実施の形態について説明する。
図４は、本発明の第２の実施の形態に係る宛先検索システムのブロック図で、図１と同一機能を有する部分には同一符号を付している。
図４において、パケット受信部１３０は、パケットスイッチから宛先を決定する必要のあるパケットの受信を行う。パケットバッファ１００は、パケット受信部１３０が受信したパケットを格納するメモリである。パケット送信部１４０は、宛先が決定されたパケットをパケットスイッチへ送信する。多段段アドレス一括検索処理部８１０はハードウェアによって構成されており、後述する処理を行うことにより、パケットバッファ１００に格納されたパケットの宛先解決処理を行う。アドレス情報記憶部８２０は、宛先アドレスに対応するパケットの宛先を検索するためのテーブルを格納するメモリである。
【００４２】
図５は、多段アドレス一括検索処理部８１０の内部ブロック構成を示したものである。
多段アドレス一括検索処理部８１０において、多段ヘッダ抽出・検索法判定部８１１は、所定の複数段分のヘッダを一括してパケットから抽出する機能が、図１２に示すヘッダ抽出・検索法判定部１１１の機能に追加されている。
多段テーブル一括検索部８１２は、所定の複数段分のヘッダを多段アドレス情報テーブルから検索し、外部ヘッダの削除、追加と宛先を検索し、ヘッダ変換部８１３に指示を送る機能を有する。
ヘッダ変換部８１３は、前記第１の実施の形態におけるヘッダ変換部６１３と同じ機能を有している。
【００４３】
アドレス情報記憶部８２０は、外部ヘッダ、内部ヘッダのアドレスに対する宛先と外部ヘッダの追加の要否、外部ヘッダ削除の要否を、所定の複数段分のヘッダを検索キーとして検索することが可能な多段アドレス情報テーブル８２１、８２２を有する。また、アドレス情報記憶部８２０は、パケットの種別毎に、パケットの宛先検索用のアドレス情報テーブル８２１、８２２を複数格納している。
尚、パケットバッファ１００はパケット記憶手段を構成し、アドレス情報記憶部８２０はアドレス情報記憶手段を構成し、多段アドレス一括検索処理部はアドレス検索処理手段を構成し、ヘッダ抽出・検索法判定部８１１はヘッダデータ検出手段を構成し、多段テーブル検索部８１２は検索手段を構成し、ヘッダ変換部８１３はヘッダ変換手段を構成している。
【００４４】
図６は、アドレス情報テーブル８２１、８２２に格納されたアドレス検索エントリを示す図である。
多段テーブル検索部８１２は、抽出した複数段分のヘッダのアドレスを検索キーとして、図６のアドレス検索エントリの最長一致エントリを該当エントリと判断する処理を行う。
本第２の実施の形態における特徴は、複数段分のヘッダに相当するデータを抽出する手段（図５の多段ヘッダ抽出・検索法判定部８１１）と、複数段分のヘッダを用いてヘッダの追加削除、テーブルを用いた宛先検索を行う手段（図５の多段テーブル一括検索部８１２）と、複数段分のヘッダに相当するデータを検索キーとしてヘッダの追加削除、宛先の検索を行うためのデータを格納する手段（図５のアドレス情報記憶部８２０）とを有している点である。
【００４５】
図７は、図４、図５の多段アドレス一括検索処理部８１０の動作を説明するためのフローチャートである。
図１１に示した宛先検索システムとの違いは、処理ステップ９１０において複数段分のパケットヘッダの有無に関わらず、ヘッダ抽出・検索法判定部８１１が複数段分に相当する所定ヘッダ長のデータをパケットから一括して抽出してパケット種別や検索キーをパケット種別とともに多段テーブル検索部８１２に送信する点と、ステップ９２０において多段テーブル検索部８１２が複数段分のヘッダを検索キーとして検索し、外部ヘッダの追加、削除、追加外部ヘッダデータをヘッダ変換部８１３に送信する点である。ヘッダ変換部８１３における処理は前記第１の実施の形態と同じである。
【００４６】
前記処理を図４〜図７に沿って説明すると、図７の処理ステップ９００で、図４のパケット受信部１３０は受信したパケットをパケットバッファ１００に格納し、図５の多段ヘッダ抽出・検索法判定部８１１にアドレス検索指示を送信する。
前記アドレス検索指示を受け取ったヘッダ抽出・検索法判定部８１１は、複数段分のパケットヘッダの有無に関わらず、ヘッダ部の中から予め定めた所定ビット数分を、パケットバッファ１００に格納したパケットから一括して抽出し、パケット種別を判別して、検索キーをパケット種別とともに多段テーブル検索部８１２に送信する（ステップ９１０）。
【００４７】
多段テーブル検索部８１２は複数段分のヘッダを検索キーとして、パケット種別に応じた多段アドレス情報テーブルから、宛先アドレス情報及びヘッダ処理情報（外部ヘッダの追加、削除、追加外部ヘッダデータ）検索する（ステップ９２０）。このとき、多段テーブル検索部８１２は、抽出した所定ビット数分のヘッダのアドレスを検索キーとして、図６のアドレス検索エントリの最長一致エントリを該当エントリと判断する処理を行う。多段テーブル検索部８１２は、前記検索処理後、多段アドレス情報テーブルからの返り値に含まれる外部ヘッダ追加フラグ等の値を判定して、外部ヘッダの追加、削除等のヘッダ書き換え情報をヘッダ変換部８１３に送信する（ステップ９２０）。
【００４８】
次に、ヘッダ変換部８１３は、送信先ヘッダの書き換え処理を行った後、パケット送信部１４０に対してパケット送信指示を行う（ステップ９３０）。
以上のように、第２の実施の形態に係る宛先検索システムは、特に、多段アドレス一括検索処理部８１０が、複数段分のヘッダに相当するヘッダデータを抽出するヘッダ抽出・検索法判定部８１１と、ヘッダ抽出・検索法判定部８１１で抽出したヘッダデータを用いてアドレス情報記憶部８２０に記憶したアドレス情報テーブル８２１、８２２を検索する多段テーブル検索部８１２とを備えて成ることを特徴としているので、多段ヘッダを有するパケットを受信した場合でも、ＣＰＵを用いてパケットを処理する必要がなくなり、多段ヘッダを有するパケットの転送処理が高速化される。
【００４９】
次に、本発明の第３の実施の形態について説明する。
図８は、本発明の第３の実施の形態に係る宛先検索システムのブロック図で、図１と同一機能を有する部分には同一符号を付している。
本第３の実施の形態に係る宛先検索システムは、図８に示すように、前記図１１の宛先検索システムのブロック図におけるアドレス検索処理部１１０がハードウェア構成の帰還型アドレス検索処理部１０１０に置換されており又、パケット受信部１３０とパケット送信部１４０の間に、パケット送信部１４０からパケット受信部１３０へパケットを転送するためのスイッチ１０５０が追加された構成となっている。
【００５０】
図９は、帰還型アドレス検索処理部１０１０の内部ブロック構成を示したものである。
帰還型アドレス検索処理部１０１０において、選択的ヘッダ抽出・検索法判定部１０１１は、指定段ヘッダの処理指示フラグの有無によってパケットから抽出するデータ部分を選択する機能を有し、テーブル検索部１０１２は、内部ヘッダの有無、外部ヘッダの追加削除処理の要否をアドレス情報記憶部１０２０に記憶したアドレス情報テーブル１０２１、１０２２から検索する機能を有する。
【００５１】
ヘッダ変換・帰還指定部１０１３は、図１２のヘッダ変換部１１３の機能に加えてテーブル検索部１０１２からの外部ヘッダ削除、追加指示を受け、パケットからヘッダ追加、削除を行う機能と、指定段ヘッダの処理指示フラグをパケットに追加し、パケット送信部１４０からスイッチ１０５０を介してパケット受信部１３０へパケットを送信する機能が追加されている。
アドレス情報記憶部１０２０は、外部ヘッダ、内部ヘッダのアドレスに対する宛先と外部ヘッダの追加の要否および指定段処理指示フラグ、外部ヘッダ削除の要否を検索可能とする複数のアドレス情報テーブルを有している。各アドレス情報テーブルはパケットの種別毎に設けられている。図９には、同一パケット種別に対応する複数のアドレス情報テーブル１０２１、１０２２を示している。
【００５２】
本第３の実施の形態は、パケットに付与された抽出位置指定によって抽出するヘッダを抽出する部分を変更することを可能とするヘッダ抽出手段（図９の選択的ヘッダ抽出・検索法判定部１０１１）と、テーブル検索の結果によってヘッダの抽出位置およびヘッダの追加削除、宛先を検索する手段（図９のテーブル検索部１０１２）と、ヘッダの抽出位置をパケットに付与し、パケットをスイッチを経由して再び自分に転送する手段（図９のヘッダ変換・帰還指定部１０１３）と、ヘッダの追加削除、宛先、ヘッダの抽出位置を検索するためのデータを格納する手段（図９のアドレス情報記憶部１０２０）とを有する点に特徴を有している。
尚、パケットバッファ１００はパケット記憶手段を構成し、アドレス情報記憶部１０２０はアドレス情報記憶手段を構成し、帰還型アドレス検索処理部１０１０はアドレス検索処理手段を構成し、選択的ヘッダ抽出・検索法判定部１０１１は検索キー生成手段を構成し、テーブル検索部１０１２は検索手段を構成し、ヘッダ変換・帰還指定部１０１３は転送手段及びヘッダ変換手段を構成している。
【００５３】
図１０は、図８、図９の帰還型アドレス検索処理部１０１０の動作を説明するためのフローチャートである。
以下、図８〜図１０を参照して、本第３の実施の形態に係る宛先検索システムの動作を詳細に説明する。
図１０において、パケット受信部１３０は、パケットスイッチから受信した受信パケットをパケットバッファに格納し、帰還型アドレス検索処理部１０１０にアドレス検索指示を送信する（ステップ１１００）。
【００５４】
該アドレス検索指示を受けた帰還型アドレス検索処理部１０１０の選択的ヘッダ抽出・検索法判定部１０１１は、多段ヘッダの処理段を指定するフラグである指定段処理指示フラグの有無を確認し、無い場合は一段目ヘッダを、ある場合には指定段フラグで指定された段のヘッダをパケットバッファ１００から抽出し、パケット種別とともにテーブル検索部１０１２に検索キーを送信する（ステップ１１１０）。尚、指定段フラグは宛先検索システム内の全パケットに対して装置内ヘッダを追加し、該ヘッダ内に格納されるものである。
次に、テーブル検索部１０１２は、受信した検索キーに基づいて、パケット種別に対応するアドレス検索テーブル１０２１、１０２２を検索する（ステップ１１２０）。
【００５５】
テーブル検索部１０１２は、アドレス検索テーブル１０２１、１０２２からの返り値に含まれる内部ヘッダ処理フラグの値を判定することによって内部ヘッダ処理指示があるかの判定を行い（ステップ１１３０）、内部ヘッダ処理指示があった場合には帰還処理指示をヘッダ変換・帰還指定部１０１３に送信する（ステップ１１６０）。内部処理が必要か否かの判断は、各段のヘッダの情報に、最終段のヘッダのみが最終段のヘッダである旨の情報を含むようにし、あるいは、最終段以外のヘッダには最終段のヘッダでない旨の情報を含むようにしておくことにより、テーブル検索部１０１２が検索した際に、アドレス情報記憶部１０２０から最手段のヘッダでない旨の内部ヘッダ処理フラグを返り値として返す、即ち、内部ヘッダ処理が必要である旨を示す内部ヘッダ処理フラグを返り値としてテーブル検索部１０１２に返すよう構成する等の方法を採用することによって行うことができる。
【００５６】
該帰還処理指示を受け取ったヘッダ変換・帰還指定部１０１３は、指定段処理指示フラグをパケットに追加し、パケットをパケット受信部１３０に転送する指示をパケット送信部１４０に送信する（ステップ１１５０）。
処理ステップ１１３０において、テーブル検索部１０１２は、内部ヘッダ処理指示がないと判断した場合には、アドレス検索テーブル１０２１、１０２２の返り値に含まれる外部ヘッダ追加フラグの値を判定することによって外部ヘッダ追加の要否を判定し（ステップ１１４０）、外部ヘッダの追加処理が必要な場合、外部ヘッダ追加の指示をヘッダ変換・帰還指定部１０１３に送信する（ステップ１１７０）。
【００５７】
該外部ヘッダ追加指示を受け取るとヘッダ変換・帰還指定部１０１３は、外部ヘッダを追加し、パケット更新処理を行うことによってヘッダ部を書き換えた後、パケット送信指示をパケット送信部１４０に送信する（ステップ１１５０）。
処理ステップ１１４０で、外部ヘッダの追加が不要の場合、検索結果として得られた情報をヘッダ変換・帰還指定部１０１３に送信し、これを受信したヘッダ変換・帰還指定部１０１３は、宛先に応じたヘッダ変換とパケット更新処理を行うことによってヘッダを書き換えた後、パケット送信指示をパケット送信部１４０に送信する（ステップ１１５０）。
【００５８】
以上のように、第３の実施の形態に係る宛先検索システムは、特に、帰還型アドレス検索処理部１０１０が、パケットに付与された抽出位置指定情報に対応する位置のヘッダの情報から検索キーを生成する選択的ヘッダ抽出・検索法判定部１０１１と、前記検索キーに基づいてアドレス情報記憶部１０２０のアドレス情報テーブル１０２１、１０２２を検索すると共に、アドレス情報記憶部１０２０から内部ヘッダを有する旨の返り値を受けて、パケットを帰還させるための帰還処理指示を行うテーブル検索部１０１２と、テーブル検索部１０１２から前記帰還処理指示を受けて、ヘッダの抽出位置指定情報を前記パケットに付与し、該パケットをスイッチ１０５０を経由してパケット受信部１３０に転送するヘッダ変換・帰還指定部１０１３とを備えて成ることを特徴としている。
【００５９】
したがって、多段ヘッダを有したパケットを受信した場合でも、ＣＰＵを用いてパケットを処理する必要がなくなるため、多段ヘッダを有したパケットの転送処理が高速化される。
また、前記第１、第２の実施の形態ではパケットの保留時間が１段ヘッダの場合でも多段ヘッダの場合でも同じ時間となるのに対して、本第３の実施の形態の場合には、１段ヘッダのパケットの場合には帰還処理を実施することなく宛先に転送することができるため、１段ヘッダパケットの伝送品質の向上が実現できるという効果を奏する。
【００６０】
【発明の効果】
本発明によれば、カプセル化のように複数のヘッダが付与された多段ヘッダのパケットに対しても、高速な宛先検索が可能になる。
また、特に請求項５、６記載の発明によれば、１段ヘッダのパケットの場合には帰還処理を実施することなく宛先に転送することができるため、１段ヘッダパケットの伝送品質の向上が実現できるという効果を奏する。
【図面の簡単な説明】
【図１】本発明の第１の実施の形態に係る宛先検索システムの構成を示すブロック図である。
【図２】本発明の第１の実施の形態に使用する多段アドレス検索処理部の内部構成を示すブロック図である。
【図３】本発明の第１の実施の形態の動作を説明するためのフローチャートである。
【図４】本発明の第２の実施の形態に係る宛先検索システムの構成を示すブロック図である。
【図５】本発明の第２の実施の形態に使用する多段アドレス一括検索処理部の内部構成を示すブロック図である。
【図６】本発明の第２の実施の形態に使用する多段アドレス情報テーブルの内容を示す図である。
【図７】本発明の第２の実施の形態の動作を説明するためのフローチャートである。
【図８】本発明の第３の実施の形態に係る宛先検索システムの構成を示すブロック図である。
【図９】本発明の第３の実施の形態に使用する帰還型アドレス検索処理部の内部構成を示すブロック図である。
【図１０】本発明の第３の実施の形態の動作を説明するためのフローチャートである。
【図１１】従来の宛先検索システムの構成を示すブロック図である。
【図１２】図１のアドレス検索処理部の内部構成を示すブロック図である。
【図１３】従来の宛先検索システムの処理のフローチャートである。
【図１４】１段ヘッダ及び２段ヘッダのパケットの説明図である。
【図１５】１段ヘッダが使用される網の例を示した説明図である。
【図１６】従来の宛先検索システムにおける２段ヘッダ処理のフローチャートである。
【符号の説明】
１００・・・パケット記憶手段を構成するパケットバッファ
１３０・・・パケット受信手段を構成するパケット受信部
１４０・・・パケット送信手段を構成するパケット送信部
６１０・・・アドレス検索処理手段を構成する多段アドレス検索処理部
６１１・・・検索キー生成手段を構成するヘッダ抽出・検索法判定部
６１２・・・検索手段を構成する多段テーブル検索部
６１３、８１３・・・ヘッダ変換手段を構成するヘッダ変換部
６２０、８２０、１０２０・・・アドレス情報記憶手段を構成するアドレス情報記憶部
８１０・・・アドレス検索処理手段を構成する多段アドレス一括検索処理部
８１１・・・ヘッダデータ抽出手段を構成するヘッダ抽出・検索法判定部
８１２・・・検索手段を構成する多段テーブル検索部
１０１０・・・アドレス検索処理手段を構成する帰還型アドレス検索処理部
１０１１・・・検索キー生成手段を構成する選択的ヘッダ抽出・検索法判定部
１０１２・・・検索手段を構成するテーブル検索部
１０１３・・・転送手段及びヘッダ変換手段を構成するヘッダ変換・帰還指定部
１０５０・・・スイッチ
【図１】
0003627697.tif 000002
【図２】
0003627697.tif 000003
【図３】
0003627697.tif 000004
【図４】
0003627697.tif 000005
【図５】
0003627697.tif 000006
【図６】
0003627697.tif 000007
【図７】
0003627697.tif 000008
【図８】
0003627697.tif 000009
【図９】
0003627697.tif 000010
【図１０】
0003627697.tif 000011
【図１１】
0003627697.tif 000012
【図１２】
0003627697.tif 000013
【図１３】
0003627697.tif 000014
【図１４】
0003627697.tif 000015
【図１５】
0003627697.tif 000016
【図１６】
0003627697.tif 000017