(57)【要約】【課題】FEにおけるテーブル操作に伴ってCPUに余分な負荷を与える。【解決手段】Table検索部３は検索キーを元に宛先Table７を検索し、得られた検索結果を検索キーとともに出力する。検索結果振分け部４はHitした場合は検索結果を後処理に付し、Misshitの場合は検索結果をCPU９に通知する。able操作部５は宛先TableにおけるTable操作を実施する。検索結果訂正部１０は、Table検索部から入力される検索キーと検索結果に対して、Table操作部におけるTable操作中のリストを検索し、Hitした場合は検索結果をTable操作後の情報に書き換えてパケットとともに検索結果振分け部に出力し、また付加情報を元にしたCPUからのTable操作要求が入力するとTable操作部に対してTable操作を指示する。【選択図】図２
2011024165.tif 000002
【特許請求の範囲】
【請求項１】
パケットの宛先検索に伴う宛先テーブル操作中に、検索キーと同一の検索キーによる後続の検索要求があると、その検索結果を前記宛先テーブル操作による検索結果と同一となるように訂正することを特徴とする宛先検索処理回路。
【請求項２】
通信装置におけるパケット等の宛先検索処理回路において、
検索キーを元に宛先Tableを検索し、得られた検索結果（Hit情報および付加情報）を検索キーとともに出力するTable検索部と、
前記Hit情報を参照し、Hitした場合は検索結果を後処理に付し、Misshitの場合は前記検索結果をCPUに通知する検索結果振分け部と、
前記宛先TableにおけるTable操作（データの追加、更新または削除）を実施するable操作部と、
前記Table検索部から入力される検索キーと検索結果に対して、前記Table操作部におけるTable操作中のリストを検索し、Hitした場合は検索結果をTable操作後の情報に書き換えてパケットとともに前記検索結果振分け部に出力し、また前記付加情報を元にした前記CPUからのTable操作要求が入力すると該Table操作要求を管理しつつ前記Table操作部に対してTable操作を指示する検索結果訂正部とを有することを特徴とする宛先検索処理回路。
【請求項３】
前記検索結果訂正部は、
前記CPUからのTable操作要求をエントリとして管理するTable操作要求バッファと、
Hashサイズ分のエントリを管理し、前記CPUからのTable操作要求を受信順に処理するために前記Table操作要求バッファとでリングバッファを構成するHashメモリと、
前記Table検索部から通知される検索キーおよび検索結果により、前記リングバッファから同一検索キーがTable操作中か否かの検索を行い、同一検索キーが検出された場合は、その検索結果の訂正を行った後に前記検索結果振分け部へ出力するTable操作チェック部と、
前記CPUからのTable操作要求を受けると前記リングバッファへの登録を行ない、また前記Table操作要求バッファにTable操作要求がある場合は、前記Table操作部に対して前記Table操作を要求するTable操作制御部とを有することを特徴とする請求項２に記載の宛先検索処理回路。
【請求項４】
前記検索結果訂正部は、
前記Table操作部からの検索キーを元に予め決められたHash演算関数によりHashキーを生成して前記Table操作チェック部へ出力する第１Hash値生成部と、
前記検索結果振分け部または前記Table操作部に要求中の前記Table操作の検索キーを元に予め決められたHash演算関数によりHashキーを生成して前記Table操作制御部へ出力するする第２Hash値生成部と、
前記Table操作チェック部は前記第１Hash値生成部、前記Table操作制御部は第２Hash値生成部からの各Hashキーによって前記Hashメモリをアクセスすることを特徴とする請求項３に記載の宛先検索処理回路。
【請求項５】
前記Table操作要求バッファの各エントリは、同一Hashキーのエントリを連結するNextポインタ，Table操作内容，検索キーおよび登録付加情報から成り、
前記Hashメモリの各エントリは、前記Table操作要求バッファにおける何れかの連結エントリの先頭のエントリを示すNextポインタと、前記Table操作要求バッファにおける同一Hashキーのエントリ数を示すエントリカウンタから成ることを特徴とする請求項３または請求項４に記載の宛先検索処理回路。
【請求項６】
前記検索結果訂正部による訂正後の検索結果、前記Table操作要求バッファの検索がHitし、且つ前記Table操作内容が追加または更新であった場合、検索結果訂正部は、前記Table検索部でのHit情報をHitと訂正し、且つ付加情報を登録付加情報に訂正することを特徴とする請求項３または請求項２〜５に記載の宛先検索処理回路。
【請求項７】
前記検索結果訂正部による訂正後の検索結果、前記Table操作要求バッファの検索がHitし、且つ、前記Table操作内容が削除であった場合、前記検索結果訂正部は、前記Table検索部でのHit情報をMisshitと訂正することを特徴とする請求項２〜５に記載の宛先検索処理回路。
【請求項８】
前記Table操作要求バッファと前記Hashメモリそれぞれに対してメモリ制御部を設け、前記Table操作要求バッファと前記Hashメモリを当該宛先検索処理回路の外部メモリとして構成することを特徴とする請求項３〜７に記載の宛先検索処理回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は通信装置におけるパケット等の宛先検索処理回路に関する。
【背景技術】
【０００２】
近年、通信回線の高速化により、単位時間当たりの入力パケット数が増大する傾向にあり、例えば、IEEE（国際電気電子学会）が定めるIEEE802.3aeにおいて、10Gbit/秒のイーサネット（登録商標）が規格化されている。この例では、10Gbit/秒の通信回線で通信単位であるイーサフレームを処理する場合、最小フレームサイズにて秒間約15,000,000フレームという高速処理が求められる。
【０００３】
これに対し、L2スイッチやルータと呼ばれる通信装置では、フォワーディングエンジン（Forwarding Engine：以下、「FE」と記載）と呼称されるハードウェアによる専用回路にて高速に宛先解決処理を行うことで、膨大な受信フレームに対応している。一般に、通信単位をLayer２ではフレーム、Layer３ではパケットと称するが、以下「パケット」と記載する。
【０００４】
図１２に従来のFEの構成例を示す（文献公知発明に係るものではない）。なお、非特許文献１において、断片的ではあるが同様な技術を窺わせる記載がある。図１２では、入力するパケットの宛先を求めてFE100が宛先Table７を検索する。検索キー抽出部２は、宛先Table７を検索するための検索キーを入力パケットから抽出する。宛先Table７内のエントリは、MACアドレス(MediaAccess Control Address)や、IPアドレス(Internet Protocol Address)、Layer４のポート番号などを検索キーとして識別され、ここでは、特にIPアドレスとLayer４ポート番号の組合せをフローという。
【０００５】
Table検索部３は検索キーを元に宛先Table７を検索し、得られた検索結果を検索キーとともに検索結果振分け部４へ出力する。検索結果とは、具体的に、Table検索部３での検索処理において、該当エントリが見つかったか否かの情報（Hit情報）と付加情報である。Hit情報は、該当エントリが見つかった場合にHit、見つからなかった場合にMisshitとなる。また、付加情報とは、Hitした場合に行なう処理の内容、例えば音声に対する処理を優先する等をいう。
【０００６】
検索結果振分け部４は、Hit情報を参照し、Hitした場合は検索結果を後処理デバイス８に出力する。後処理デバイス８では、付加情報を元に不正パケットの廃棄やQoS(Quality of Service)制御などが行われるが、これは通信装置で実装される個別機能に依存するため、その詳細な記載は省略する。
【０００７】
一方、Misshitの場合、検索結果振分け部４は、CPUアクセス処理部６を介して検索結果をCPU９に通知する。CPUアクセス処理部６は、FE100における処理とCPU９における処理の速度調整を行なう。CPU９では、FE100からの検索結果における付加情報を元にTable操作要求をCPUアクセス処理部６へ出力する。CPUアクセス処理部６は、これをTable操作部５へ転送し、Table操作部５は宛先Table７に対するTable操作を実施する。Table操作とは、宛先Table７におけるデータの追加、更新、削除をいう。
【０００８】
図１３は、図１２に示した従来の宛先検索処理回路の処理イメージを示す図である。図１３において、テーブル操作中における、検索処理の結果を時間軸別に示す。時刻ｔ１において、FE100ではフローXに対するエントリが存在しないため、Hit情報＝MissHitとなり、時刻ｔ２において、フローXに対するテーブル操作（追加）が要求される。
【０００９】
テーブル操作において、宛先Table７の実現方法には規定がなく、各装置の設計方針に依存する部分ではあるが、複数のエントリを管理する必要があるため、何らかのメモリデバイスで構成されている。従って、テーブル操作には、メモリアクセスのためのレイテンシや、テーブル構成変更のための遅延が発生することが一般的に知られており、時刻ｔ２〜時刻ｔ５が本遅延を示している。この時間帯はフローXのエントリが追加中の状態であるため、時刻ｔ３やｔ４の検索要求に対して、Hit情報＝MissHitと判定される。
【００１０】
図１３のケースにおいて、時刻ｔ３および時刻ｔ４の検索要求がMissHitと判定され、同じフローであるにも関わらずCPU９に通知されることで、CPU９に余分な負荷を与え、CPUアクセス処理部６〜CPU９間のバス帯域を切迫する。
【００１１】
また、図１３を実際の通信イメージに置き換えた図１４において、クライアント２１〜サーバ２２間の通信状態（セッションと定義）の監視を行うような通信装置２０では、Frame#0でフロー登録要求を行ったにも関わらず、上記の遅延が発生しているため、フロー登録が終了するｔ５までの間におけるFrame#1とFrame#2はMissHitと判定される。
【００１２】
通信装置２０とは、具体的にIDS(Intrusion Detection System)や、IPS(IntrusionPrevention System)といったセキュリティ装置などが想定されるが、MissHitと判定された場合、Frame#0とFrame#1、Frame#0とFrame#2の間の状態が不一致となるので、そのセッション状態を確認するという手間が増えるという点で、先に述べた、CPU負荷が更に増大することになる。
【００１３】
このような宛先検索処理におけるCPUの負荷の軽減を図った技術として、特許文献１には、予め登録された種類のパケットのフィルタリングを行うフィルタリング手段と、フィルタリング手段にパケットが入力される前に、パケットを処理するアプリケーションによって指定された種類を上記の予め登録された種類とする制御手段とを備えたパケット中継装置が開示されている。しかし、この技術では、パケットの中継処理において情報端末装置とプロセッサが連係することを要し、情報端末装置は、所定のアプリケーションの実行の過程で、やがて配信されるパケットの列を識別し、ルータを経由して制御パケットをFEに引き渡すという繁雑な処理を必要とする。
【先行技術文献】
【特許文献】
【００１４】
【特許文献１】特開２００６−３４５３６６
【非特許文献】
【００１５】
【非特許文献１】富士通株式会社、富士通半導体デバイスＤＡＴＡ ＳＨＥＥＴ：ＤＳ０４−２２１１４−１ ＩＰフォワーディングエンジン ＭＢ８６９７７（P.10〜11）、［online］、［平成２１年４月２０日検索］、インターネット＜ＵＲＬ：http://edevice.fujitsu.com/jp/datasheet/j-ds/j422114.pdf＞
【発明の概要】
【発明が解決しようとする課題】
【００１６】
解決しようとする問題点は、FEにおけるテーブル操作に伴ってCPUに余分な負荷を与え、更にセッション状態の管理によりCPU負荷が増大し、または宛先検索処理が煩雑になる点である。
【課題を解決するための手段】
【００１７】
本発明は、テーブル操作中において、後続の同一フローに対する検索結果をテーブル操作後の検索結果と同一となるように訂正することを最も主要な特徴とする。
【発明の効果】
【００１８】
本発明の宛先検索処理回路は、テーブル追加処理中のフローに対して、同一フローの検索結果が矛盾なく処理されるため、未登録フローとしてCPUに通知されるパケットが減少するので、CPU負荷を削減できるという利点がある。更に、この波及効果として、FEの検索結果出力までの処理時間が小さくなるため、パケットレイテンシが減少する。
【図面の簡単な説明】
【００１９】
【図１】本発明の宛先検索処理回路の処理イメージを示す図である。
【図２】本発明の宛先検索処理回路の実施例１のブロック図である。
【図３】図２における検索結果訂正部の詳細図である。
【図４】Table操作要求バッファの構成例を示す図である。
【図５】Hashメモリの構成例を示す図である。
【図６】片方向Listの構成イメージ図である。
【図７】検索キーおよび検索結果を元に行う検索手順を示す図である。
【図８】検索結果の訂正パタンを示す図である。
【図９】エントリ追加後の片方向Listの構成イメージ図である。
【図１０】エントリ削除後の片方向Listの構成イメージ図である。
【図１１】本発明の宛先検索処理回路の実施例２のブロック図である。
【図１２】従来のフォワーディングエンジンの構成例を示すブロック図である。
【図１３】従来のフォワーディングエンジンの処理イメージを示す図である。
【図１４】従来の通信状態監視イメージを示す図である。
【発明を実施するための最良の形態】
【００２０】
本発明の宛先検索処理回路は、図１３に対応して図１に示す処理イメージのとおり、フロー登録処理中における同一フローの検索要求に対して、検索結果をテーブル操作後の検索結果と同一となるように訂正する。即ち、ｔ１でのフローＸの検索要求に対してMissHitし、ｔ２でフローＸの登録要求があり、そのフロー登録処理中（ｔ２〜ｔ５）に、ｔ３およびｔ４でフローＸの検索要求があった場合、Hit情報は、図１３のようにMissHitではなく、テーブル操作後の内容（Hit）に訂正する。
【実施例１】
【００２１】
図２は本発明の宛先検索処理回路の実施例１のブロック図であり、図１２と対比して、検索結果訂正部１０が追加されていることが分かる。図１２におけるのと同一の参照番号が付された構成要素の機能は、以下に記載のとおり多少の相違を除いて前述のとおりである。
【００２２】
検索結果訂正部１０は、Table検索部３から入力される検索キーと検索結果に対して、Table操作部５におけるTable操作中のリストを検索し、Hitした場合は、検索結果をTable操作後の情報に書き換えて、パケットとともに検索結果振分け部４に出力する。また、CPUアクセス処理部６からのTable操作要求を管理しつつ、Table操作部５に対してTable操作を指示することで、追加、変更、削除などのTable操作機能を実現する。従って、CPUアクセス処理部６は検索結果訂正部１０に対してTable操作要求を行い、Table操作部５は検索結果訂正部１０からの検索を受けTable操作を指示される。
【００２３】
図３は検索結果訂正部１０の詳細図であり、Table操作要求バッファ１１，Hashメモリ１２，２つのHash値生成部１３，１４，Table操作チェック部１５およびTable操作制御部１６で構成される。
【００２４】
Table操作要求バッファ１１は、CPUアクセス処理部６からのTable操作要求をエントリとして管理する。各エントリは、図４に示すように、Nextポインタ11-1とTable操作内容11-2と検索キー11-3と登録付加情報11-4により構成され、図４では最大Ｎ個のTable操作要求を管理できることを示している。Nextポインタ11-1は一連のTable操作要求に対するエントリを連結するためのものである。Table操作内容11-2とは、宛先Table７におけるデータの追加、更新、削除の何れかをいう。また、登録付加情報11-4とは登録された付加情報を意味する。
【００２５】
Hashメモリ１２は、Table検索部３からの検索結果を訂正するために、Table操作要求バッファ１１を高速検索することを目的としたメモリである。Hashサイズ分のエントリを管理し、各エントリは、図５に示すように、Nextポインタ12-1とエントリカウンタ12-2より構成される。Nextポインタ12-1はTable操作要求バッファ１１における何れかの連結エントリの先頭のエントリを示し、エントリカウンタ12-2は同一Hashキーのエントリ数を示す。
【００２６】
以上のTable操作要求バッファ１１とHashメモリ１２によるメモリ構成により、Table操作部５に対しては、Table操作要求バッファ１１におけるHeadポインタ11-5とTailポインタ11-6でリングバッファを実現し、複数のTable操作要求を受信順に処理する一方で、Table検索部３からの処理要求に対しては、任意のフローに対して、図６示すような片方向リストによる高速検索処理を実現する。
【００２７】
Hash値生成部１３とHash値生成部１４は、入力元と出力先が異なるが機能は同じであり、与えられた検索キーを元に予め決められたHash演算関数によりHash値を生成する。Hash値を生成することで、検索キーを圧縮することができ、Hashメモリ１２の容量を削減しつつ高速検索を実現できるが、Hash論理やHash演算関数については、当業者にとってよく知られているので説明を省略する。
【００２８】
Table操作チェック部１５は、Table検索部３から通知される検索キーおよび検索結果と、Hash値生成部１３から通知されるHashキーにより、Hashメモリ１２とTable操作要求バッファ１１から、同一フローがTable操作中か否かの検索を行い、Table操作要求バッファ１１内に同一フローとして検出された場合は、検索結果の訂正を行った後、検索結果振分け部４に出力する。
【００２９】
Table操作制御部１６は、CPUアクセス処理部６から検索キーおよび検索結果を伴ったTable操作要求を受けると、Hash値生成部１４から通知されるHashキーにより、図４と図５に示したように、Hashメモリ１２とTable操作要求バッファ１１のエントリへの登録を行なう。また、Table操作要求バッファ１１にTable操作要求がある場合は、Table操作部５に対して、Table操作を要求する。
【００３０】
次に、検索結果訂正部１０で行われるTable操作中のエントリの検索処理について説明する。図６に示したように、Hash１２メモリとTable操作要求バッファ１１にて、片方向のリストを構成することにより検索処理を高速化する。
【００３１】
図７はTable検索部３からの検索キーおよび検索結果を元に行う検索手順を示す。Table検索部３から入力される検索キー＝Ｘに対して、Hash値生成部１３はHashキー＝Ａを出力する。Table操作チェック部１５は、このHashキー＝ＡをアドレスとしてHashメモリ１２をリードすることで、Nextポインタ12-1＝Ｂとエントリカウンタ12-2＝「２」が得られる。
【００３２】
エントリカウンタ12-2はTable操作要求バッファ１１内の同一Hashキーのエントリ数を示している。つまり、エントリカウンタ12-2が１以上の場合は、Table操作要求バッファ１１内に同一Hashキーのエントリが存在することを示している。次に、Nextポインタ12-1＝Ｂをアドレスとして、Table操作要求バッファ１１をリードする。
【００３３】
リードされたエントリの要素の内、検索キー11-3はＹであって要求元の検索キー＝Ｘと異なるため、Nextポインタ11-1＝Ｃが示すアドレスをリードする。ここで、検索キー11-3と要求元の検索キーが一致するため、検索処理を終了し、Table操作内容11-2と登録付加情報11-4を得る。
【００３４】
以上の処理結果から、図８に示すとおり、Table操作要求バッファ検索結果によって判別される３パタンの訂正後検索結果が得られる。Table操作要求バッファ検索結果は、MisshitとHitの別、Hitの場合におけるTable操作内容11-2が追加または更新と削除の別で３区分される。
【００３５】
第１は、Table操作要求バッファ１１の検索がMisshitした場合である。この場合、検索結果訂正部１０では検索結果の訂正を行わず、Table検索部３の情報をそのまま検索結果振分け部４に出力する。これは当該フローがTable操作中でないことを意味しており、図１の時刻ｔ１の検索処理が該当する。
【００３６】
第２は、Table操作要求バッファ１１の検索がHitし、且つ、Table操作内容11-2が追加または更新であった場合である。この場合、検索結果訂正部１０では、Table検索部３でのHit情報をHitと訂正し、且つ、付加情報を登録付加情報11-4に訂正する。これは当該フローがTable操作中であることを意味しており、図１の時刻ｔ３、ｔ４の検索処理が該当する。
【００３７】
第３は、Table操作要求バッファ１１の検索がHitし、且つ、Table操作内容11-2が削除であった場合である。この場合、検索結果訂正部１０では、Table検索部３でのHit情報をMisshitと訂正する。Hit情報がMisshitとなるため、付加情報については無効情報となる。これは第２と同様に、当該フローがTable操作中であることを意味している。
【００３８】
次に、Hash１２メモリとTable操作要求バッファ１１の追加動作について説明する。CPUアクセス処理部６の要求に対し、Table操作制御部１６は、Hashキーをアドレスとして、Hashメモリ１２をリードし、Nextポインタ12-1とエントリカウンタ12-2を得る。図６の状態からHashメモリ１２のエントリ＃０にエントリを追加した例が図９である。次に、Tailポインタ11-6が指すTable操作要求バッファ１１のエントリに、Nextポインタ11-1とTable操作内容11-2と検索キー11-3と登録付加情報11-4を設定する。Nextポインタ11-1には、Hashメモリ１2のリード値であるNextポインタ12-1を設定する。
【００３９】
図９の例では、Tailポインタ11-6＝５とし、Table操作要求バッファ１１のエントリ＃５に設定している。次に、リードしたHashメモリ１２に対して、エントリカウンタ12-2を１加算し、Nextポインタ12-1にTailポインタ11-6の値を設定した後、Tailポインタ11-6を１加算する。以上により、Hashメモリ１２にエントリが追加されていく形で片方向リストが構成される。
【００４０】
次に、Table操作部５に対する制御と、それに伴うHashメモリ１２とTable操作要求バッファ１１の削除動作について説明する。Table操作部５に対する制御は、Headポインタ11-5とTailポインタ11-6によるリングバッファにより制御される。具体的には、Table操作制御部１６は、Headポインタ11-5が指す、Table操作要求バッファ１１のエントリより処理要求を行い、Table操作部５のTable操作応答を待って処理完了とする。この間に、Table操作制御部１６は、Table操作中の検索キーよりHashキーを取得する。図３の回路構成では、Hash値生成部１４を併用する例を示している。
【００４１】
図９の状態から、Hashメモリ１２のエントリ＃２のTable操作要求バッファ１１のエントリ＃０を削除した例が図１０である。図１０の例では、Headポインタ11-5＝１として、削除後の状態を示している。Table操作部５からのTable操作応答受信時に、先に取得したHashキーをアドレスとした、Hashメモリ１２のエントリカウンタ12-2を１減算した後、Headポインタ11-5を１加算する。エントリカウンタ12-2が減算されていくことで片方向リストの末端から削除されていく形となる。
【００４２】
Table操作制御部１６ではHeadポインタ11-5＝Tailポインタ11-6となるまで本削除動作を繰り返す。つまり、Headポインタ11-5＝Tailポインタ11-6は、Table操作要求が全て完了した状態を示している。
【実施例２】
【００４３】
本発明の他の実施例として、その基本的構成は上記の通りであるが、メモリ配置について工夫した構成を図１１に示す。図３では内部メモリで実現していたTable操作要求バッファ１１とHashメモリ１２を、図１１では、Table操作要求バッファ１１に対するメモリ制御部１７と、Hashメモリ１２に対するメモリ制御部１８を追加することで検索結果訂正部10-1の外部メモリとして構成する形態を示している。
【００４４】
一般に、デバイス内部のメモリはデュアルポートメモリとして使用可能な場合が多く、本発明におけるように、Table操作制御部１６とTable操作チェック部１５の双方からのアクセスが容易に実現できるが、高コストである点と、メモリ容量が外部メモリに比べると小さいという問題点がある。ここで図１１のように、外部メモリにTable操作要求バッファ１１とHashメモリ１２を実装することで、内部メモリリソースが足りない場合の対策や、メモリ容量が増えることで、Table操作要求バッファ１１やHashメモリ１２のエントリ数を増やせるという効果が得られる。
【符号の説明】
【００４５】
１…FE（フォワーディング・エンジン）
２…検索キー抽出部
３…Table検索部
４…検索結果振分け部
５…Table操作部
６…CPUアクセス処理部
７…宛先Table
８…後処理デバイス
９…CPU
１０…検索結果訂正部
１１…Table操作要求バッファ
１２…Hashメモリ
１３…Hash値生成部
１４…Hash値生成部
１５…Table操作チェック部
１６…Table操作制御部
１７  メモリ制御部
１８  メモリ制御部
10-1  検索結果訂正部
11-1  Nextポインタ
11-2  Table操作内容
11-3  検索キー
11-4  登録付加情報
11-5  Headポインタ
11-6  Tailポインタ
12-1  Nextポインタ
12-2  エントリカウンタ
【図１】
2011024165.tif 000003
【図２】
2011024165.tif 000004
【図３】
2011024165.tif 000005
【図４】
2011024165.tif 000006
【図５】
2011024165.tif 000007
【図６】
2011024165.tif 000008
【図７】
2011024165.tif 000009
【図８】
2011024165.tif 000010
【図９】
2011024165.tif 000011
【図１０】
2011024165.tif 000012
【図１１】
2011024165.tif 000013
【図１２】
2011024165.tif 000014
【図１３】
2011024165.tif 000015
【図１４】
2011024165.tif 000016