(57)【要約】【解決手段】本発明の実施形態は、両プラットフォームの欠点を取り除きながらソフトウェアベース及びハードウェアベースの転送エンジンの利点を効果的に組み合わせたソフトウェア改良型ステートフルパケット処理アーキテクチャを実現する。ステートフルスイッチングアーキテクチャにおけるハードウェアベースの状態テーブルのサイズ上の制約を克服するため、ハードウェアベースのステートフルパイプラインをソフトウェアベースのステートフルパイプラインで拡張する。これは、全ての新しいフローをソフトウェアベースステートフルパイプラインに転送しソフトウェア状態テーブルにフロー毎の状態を保持することにより実行できる。過剰なトラフィックによりソフトウェアパイプラインがオーバーロードになった場合、一部のフローをその状態とともに最終的にハードウェア状態テーブルに移動することができ、これによりソフトウェアパイプラインを効果的にオフロードできる。【選択図】図３
2019510428.tif 000002
【特許請求の範囲】
【請求項１】
第１の状態テーブル及び第１の有限状態マシン（ＦＳＭ）テーブルを含む第１のステートフルステージ（６）と、
第２の状態テーブル及び第２のＦＳＭテーブルを含む第２のステートフルステージ（７）と、
フローがいつ前記第１のステートフルステージ（６）又は前記第２のステートフルステージ（７）により若しくは前記２つのステートフルステージ（６、７）の組み合わせにより処理されるべきかを決定する分散機構とを含み、
前記２つのＦＳＭテーブルの少なくとも１つは前記分散機構をサポートする状態及び遷移で拡張される、ステートフルネットワークパケット処理システム。
【請求項２】
前記第１のステートフルステージ（６）及び前記第２のステートフルステージ（７）は異なる技術に実装される、請求項１に記載のシステム。
【請求項３】
前記第１のステートフルステージ（６）はハードウェアに実装され、ハードウェア状態テーブル（９）（ＨＳＴ）とハードウェアＦＳＭテーブル（１１）（ＨＦＳＭＴ）とを備え、
前記第２のステートフルステージはソフトウェアに実装され、ソフトウェア状態テーブル（８）（ＳＳＴ）とソフトウェアＦＳＭテーブル（１０）（ＳＦＳＭＴ）とを備える、請求項１又は２に記載のシステム。
【請求項４】
前記ハードウェアステートフルステージ（６）はＴＣＡＭメモリベースのステージとして実装される、請求項３に記載のシステム。
【請求項５】
前記ソフトウェアステートフルステージ（７）は汎用処理装置とＤＲＡＭメモリの組み合わせとして実装される、請求項３又は４に記載のシステム。
【請求項６】
前記２つのステートフルステージ（６、７）はそれぞれ、ネットワークパケットのヘッダーから前記状態テーブル（８、９）のマッチフィールドのためのキーを表す特定の値を引き出すように構成されたキー抽出モジュール（３）を含む、請求項１〜５のいずれかに記載のシステム。
【請求項７】
前記キー抽出モジュール（３）は更に、前記特定の値を前記ＦＳＭテーブル（１０、１１）のそれぞれにおける前記ネットワークパケットに関連付けられた状態に関する情報とともに前記２つの状態テーブル（８、９）のそれぞれに渡すように構成された、請求項６に記載のシステム。
【請求項８】
前記ＨＳＴにはデフォルトで、ワイルドカードマッチ及び関連状態としての状態を示すソフトウェアを持つ単一の優先度の低いエントリのみが含まれる、請求項３〜７のいずれかに記載のシステム。
【請求項９】
前記ＨＦＳＭＴ（１１）にはデフォルトで、状態を示す前記ソフトウェアと関連付けられマッチングパケットを前記ＳＳＴ（８）に転送するアクションを指定するエントリが含まれる、請求項３〜８のいずれかに記載のシステム。
【請求項１０】
前記ＨＦＳＭＴ（１１）から前記ＳＳＴ（８）へのマッチングパケットの前記転送は専用のオープンフローインストラクションを用いることにより実行される、請求項９に記載のシステム。
【請求項１１】
前記ステートフルステージ（６、７）の少なくとも１つは前記分散機構を実行するための評価モジュール（１２）を含み、
前記評価モジュールは（１２）は特定のフローを前記２つのステートフルステージ（６、７）の一方から他方のステートフルステージ（７、６）に移動するための基準を提供するように構成された、請求項１〜１０のいずれかに記載のシステム。
【請求項１２】
前記評価モジュール（１２）はフロー及び／又はパケット統計値に対して行った評価を２値変数に変換するように構成された、請求項１１に記載のシステム。
【請求項１３】
前記評価モジュール（１２）は前記ソフトウェアステージ（７）を備え、
前記評価モジュール（１２）は、前記２値変数の値に基づいて前記ソフトウェアステートフルステージ（７）から前記ハードウェアステートフルステージ（６）への遷移を引き起こすワンウェイオフロード方式の形態で前記分散機構を実行するように構成された、請求項１１又は１２に記載のシステム。
【請求項１４】
前記２つのステートフルステージ（６、７）は、外部接続により互いに連結された２つの物理的に分離されたデータパスを用いることにより実装される、請求項１から１３のいずれかに記載のシステム。
【請求項１５】
前記第１のステートフルステージ（６）及び前記第２のステートフルステージ（７）に加えて１つ又は複数の補足的なステートフルステージを含む、請求項１から１４のいずれかに記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は概してステートフルパケット処理システムに関する。
【背景技術】
【０００２】
“ソフトウェアデファインドネットワーキング”（Ｓｏｆｔｗａｒｅ−Ｄｅｆｉｎｅｄ  Ｎｅｔｗｏｒｋｉｎｇ：ＳＤＮ）パラダイムは、パケット転送（データプレーン）機能とコントロールプレーン機能とを分離する。広く採用されている“オープンフロー”プロトコルは、中央コントローラからのスイッチのデータプレーンの遠隔プログラミングのためにフローレベルのアブストラクションを提供する。コントローラは特定のＦｌｏｗ＿Ｍｏｄメッセージにより基礎スイッチにフロー毎のルールを教える。このようなメッセージには、マッチ部分とアクション部分が含まれており、前者はマッチするパケットヘッダーを特定し、後者は指定されたフローに属する全てのパケットに対し特定の処理判断を適用する。（http://archive.openflow.org/documents/openflow-spec-v1.1.0.pdfに規定されているように）これらの転送ルールは、転送テーブルステートメントに変換されテーブルパイプラインの１つ又はいくつかのテーブルに組み込まれる。このような転送アブストラクションはテーブルパイプラインにおけるステートレスパケット処理を示唆し、特定のフローのあらゆる可能な状態遷移がコントローラ側でのみ実行される可能性があることを意味している。これはステートフルパケット処理を必要とするいずれの転送ロジックも、スイッチとコントローラ間でのいくらかの対話を必要とすることを意味している。そのような対話を必要とする場合のあるステートフル処理アプリケーションの例として、トラフィック異常検出、ファイアウォールのようなプリミティブ（例えば、再帰ＡＣＬ）、適応ＱｏＳエンフォースメントなどがあげられる。
【０００３】
（例えば、Ｇｉｕｓｅｐｐｅ  Ｂｉａｎｃｈｉ、Ｍａｒｃｏ  Ｂｏｎｏｌａ、Ａｎｔｏｎｉｏ  Ｃａｐｏｎｅ、Ｃａｒｍｅｌｏ  Ｃａｓｃｏｎｅ：“オープンステート：スイッチ内のプログラミングプラットフォームから独立したステートフルオープンフローアプリケーション”、ＳＩＧＣＯＭＭ  Ｃｏｍｐｕｔ．  Ｃｏｍｍｕｎ．  Ｒｅｖ．  ４４，  ２（２０１４年４月）、４４−５１ページに記載されるように）“オープンステート”は、“拡張有限ステートマシン”（Ｅｘｔｅｎｄｅｄ  Ｆｉｎｉｔｅ  Ｓｔａｔｅ  Ｍａｃｈｉｎｅ：ＸＦＳＭ）を持つ転送エンジンを向上させるフロー指向のステートレス処理への拡張を可能にする。この拡張は、ステートレス転送アーキテクチャに状態テーブル及びＸＦＳＭ（又は短縮してＦＳＭ）テーブルの２つのテーブルを追加することにより、スイッチングパイプラインにおける各フローの状態の追跡とその状態からの遷移を可能にする。
【０００４】
アーキテクチャの２つのテーブルうちの第１のテーブルである“状態”テーブルは、キー値、第１マッチルックアップテーブルである。状態テーブルでは、第１マッチルックアップを行ってそのフローに関連する状態に対してインカミングフローの何らかのパケットヘッダーをマッチさせる。ＦＳＭテーブルでは、パケットヘッダーと遷移した状態の組み合わせが次のルックアップのキーになる。フローの状態更新が必要な場合、フィードバックループが２つのテーブルにかかわり、ＦＳＭテーブルからの特定のフローのための状態更新を持つメッセージを状態テーブルへ渡す。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
上記したものの１つであるスイッチングプラットフォームにはいくつかの制約がある。最も関係のある制約の１つは、状態テーブルは新しいインカミングフロー毎に（すなわち、リモートホストからの新しい接続毎に）別個のレコードを維持する必要があるということである。このアーキテクチャ上の決定によりスイッチングアーキテクチャは厳しいスケーラビリティ上の課題をつきつけられる。更に、現在のハードウェアベースで“オープンフロー”有効のスイッチは、ＳＤＮの大規模な採用とデプロイへの道の障害となる技術的制約をいくつも有する。それらのスイッチでは、フレキシブルなルックアップフローテーブルが通常、サイズ（レコード数）が限定され電力需要が多く高価なＴＣＡＭなどの特殊メモリを用いて実装される。サイズの制約に加えて、それらのフローテーブルは更新速度が遅い。ハードウェアスイッチングプラットフォームとは対照的に、ソフトウェアスイッチ（ｈｔｔｐ：／／ｏｐｅｎｖｓｗｉｔｃｈ．ｏｒｇ／を参照）は、従来のＲＡＭメモリを用いてＣＰＵベース転送と組み合わせてそのマッチテーブルを保存する。通常、それらのスイッチはフローテーブルの容量は不足しないが、その転送能力はハードウェアスイッチより著しく劣っている。
【０００６】
以上の点から、本発明の目的は、ステートフルパケット処理システムをそのスケーラビリティが向上するように改善及び発展させることである。
【課題を解決するための手段】
【０００７】
本発明によれば、上記の目的は、第１の状態テーブル及び第１の有限状態マシン（ＦＳＭ）テーブルを含む第１のステートフルステージと、第２の状態テーブル及び第２のＦＳＭテーブルを含む第２のステートフルステージと、フローがいつ前記第１のステートフルステージ又は前記第２のステートフルステージにより若しくは前記２つのステートフルステージの組み合わせにより処理されるべきかを決定する分散機構とを含み、前記２つのＦＳＭテーブルの少なくとも１つは前記分散機構をサポートする状態及び遷移で拡張される、ステートフルネットワークパケット処理システムにより達成される。
【０００８】
本発明によれば、ステートフルＳＤＮスイッチのスケーラビリティの向上は、それぞれ状態テーブルとＦＳＮテーブルを含む少なくとも２つのステートフルステージを、いつフローが一方又は他方のＦＳＭテーブルによって処理されるべきかを特定する分散機構とともに組み合わせたハイブリッドスイッチによって実現できることが認識された。本発明の実施形態によれば、ＦＳＭ適応手法を適用することにより、当初のＦＳＭを上記の分散機構を用いてソフトウェア実行装置、ハードウェア実行装置などの２つの異なるＦＳＭ実行装置に分割が可能なＦＳＭに変換することができる。上記のように少なくとも２つのステートフルステージを組み合わせたハイブリッドスイッチは、このように得られたＦＳＭを実行するように構成してもよい。これは、要求される転送動作にしたがうスイッチによるネットワークパケットの処理が第１のステージ、第２のステージ、又はその２つの組み合わせにより実行されるように２つのステートフルステージに対して状態遷移エントリを生成することにより実現できる。転送動作は、定義された分散機構にしたがって２つのステージに分割されて行われる。２つのステージが並立に動作するため、サポートされるフローの総数は大幅に拡張されてスケーラビリティが向上する。
【０００９】
本発明の実施形態によれば、前記第１のステートフルステージ及び前記第２のステートフルステージは、異なる技術、すなわち、特定の技術に関係した障害に対する堅牢性の向上の観点から利点があることが証明されている異質な技術に実装される。ただし、同一の技術に両ステートフルステージを実装することも可能である。このソリューションは、ステージの１つがウィルスなどに冒される場合などの特定の状況の対処に役立つことができる。
【００１０】
一実施形態によれば、前記第１のステートフルステージはハードウェアに実装され、ハードウェア状態テーブル（ＨＳＴ）とハードウェアＦＳＭテーブル（ＨＦＳＭＴ）とを備え、前記第２のステートフルステージはソフトウェアに実装され、ソフトウェア状態テーブル（ＳＳＴ）とソフトウェアＦＳＭテーブル（ＳＦＳＭＴ）とを備える。このような実装は、両ソリューションの欠点を取り除きながらソフトウェアベースとハードウェアベースの転送プラットフォームの利点を組み合わせるため、最も利点がある。特に、前記ハードウェアステートフルステージは、ＴＣＡＭ（Ｔｅｒｎａｒｙ  Ｃｏｎｔｅｎｔ−Ａｄｄｒｅｓｓａｂｌｅ  Ｍｅｍｏｒｙ：三値連想メモリ）ベースのステージとして実装されてもよい。ＴＣＡＭはパケット転送が非常に速いが、ほんの限られた数、例えば、１０，０００のエントリしか保持できない場合がある。この欠点は、第２のステージを、例えば、数百万エントリに対応する能力を提供するが転送性能に限界を有する場合がある汎用処理装置とＤＲＡＭメモリ（Ｄｙｎａｍｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）の組み合わせとしてソフトウェアに実装することにより補うことができる。
【００１１】
一実施形態によれば、前記２つのステートフルステージはそれぞれ、ネットワークパケットのヘッダーから前記状態テーブルのマッチフィールドのためのキーを表す特定の値を引き出すように構成されたキー抽出モジュールを含んでもよい。このキー抽出モジュールは、フローの状態更新が必要なとき前記テーブル間のフィードバックループを提供・管理してもよい。そのため、キー抽出モジュールは、前記特定の値を（一部の実施形態では、‘ｎｅｘｔ＿ｓｔａｔｅ’  として示される）前記ＦＳＭテーブルにおける前記ネットワークパケットに関する情報、すなわち、前記ネットワークパケットの現在の状態又はそれに関連付けられた状態とともに前記２つの状態テーブルのそれぞれに渡すように構成されてもよい。より詳細には、フローの状態更新が必要な場合、フィードバックループが２つのテーブルにかかわって特定のフローの更新を持つメッセージｓｅｔ＿ｓｔａｔｅ：  ｐｋｔ＿ｈｅａｄｅｒｓ＋ｎｅｘｔ＿ｓｔａｔｅを渡す。前記キー抽出モジュールは、前記特定の値をｎｅｘｔ＿ｓｔａｔｅとともに前記状態テーブルに渡し、それにより既存の状態テーブルのエントリを更新する、又は新しいエントリを入力する。
【００１２】
一実施形態によれば、前記ＨＳＴにはデフォルトで、ワイルドカードマッチ及び関連状態としての状態（‘ＳＷ’）を示すソフトウェアを持つ単一の優先度の低いエントリのみが含まれていてもよい。その結果、当初はＨＳＴに関連する詳細なエントリを持たない新たに到着する全てのフローがデフォルトのエントリによって処理されることになる。すなわち、それらのフローは更なる処理のためにソフトウェアパイプラインに転送される。加えて、前記ハードウェアＦＳＭテーブル（ＨＦＳＭＴ）にはデフォルトで、状態‘ＳＷ’と関連付けられ、マッチングパケットを前記ソフトウェア状態テーブル（ＳＳＴ）に転送するアクションを指定するエントリが含まれていてもよい。一実施形態によれば、前記ＨＦＳＭＴから前記ＳＳＴへのマッチングパケットの前記転送は専用のオープンフローインストラクション（例えば、「Ｇｏｔｏ−テーブル」インストラクション）を用いることにより実行されてもよい。
【００１３】
一実施形態によれば、前記ステートフルステージの少なくとも１つは前記分散機構を実行するための評価モジュールを含んでもよく、前記評価モジュールは特定のフローを前記２つのステートフルステージの一方から他方のステートフルステージに移動するための基準を提供するように構成されてもよい。すなわち、前記転送動作は、前記所与の基準、例えば、ただし限定されない、受信したパケット数、転送されたバイト数などに基づく性能基準にしたがって前記２つのステートフルステージの間で分割して実行される。特に、前記評価モジュールはフロー及び／又はパケット統計値に対して行った評価を２値変数に変換するように構成されてもよい。例えば、前記評価モジュールは、例えば、特定のフローのパケット数が所定のしきい値を超えていると評価された場合、値「ｔｒｕｅ」を出力してもよく、パケット数がしきい値を下回る限り値「ｆａｌｓｅ」を出力してもよい。前記２値変数の効率的な採用に関して、ＦＳＭテーブルは２値変数「ｔｒｕｅ／ｆａｌｓｅ」に対してマッチする追加的フィールドにより拡張されてもよい。
【００１４】
一実施形態によれば、前記評価モジュールは前記ソフトウェアステージを備えてもよく、前記２値変数の値に基づいて前記ソフトウェアステートフルステージから前記ハードウェアステートフルステージへの遷移を引き起こすワンウェイオフロード方式の形態で前記分散機構を実行するように構成されてもよい。この場合、（２値変数の値によっては）スイッチに到着する全ての新しいフローは最初は、それらが最終的にハードウェアパイプラインにオフロードされる場所からソフトウェアパイプラインに転送されてもよい。
【００１５】
一実施形態によれば、前記２つのステートフルステージは、外部接続により互いに連結された２つの物理的に分離されたデータパスを用いることにより実装されてもよい。すなわち、例えば、ハードウェアパイプラインの観点から、対応するソフトウェアパイプラインは外部のソフトウェアスイッチで実現されてもよい。
【００１６】
一実施形態によれば、前記システムは前記第１のステートフルステージ及び前記第２のステートフルステージに加えて１つ又は複数の補足的なステートフルステージを含んでもよい。当業者には理解されるように、そのようなマルチステージ（ｎ＞２）パケット処理プラットフォームの操作方式は、前記２つのステージの場合の操作方式から端的に派生するものであってよい。
【００１７】
本発明の内容を有利に設計し発展させる方法がいくつもある。このため、従属する請求項、及び以下の図示された例としての本発明の好適な実施形態の説明を参照されたい。図に補助された本発明の好適な実施形態の説明と関連して、本発明の内容の一般的に好適な実施形態及び更なる進展が説明されよう。
【図面の簡単な説明】
【００１８】
図において、
【図１】図１は、２フェーズのポートノッキングアプリケーションＦＳＭを説明する概略図である。
【図２】図２は、図１のポートノッキングアプリケーションを実装するステートフルスイッチングアーキテクチャを説明する概略図である。
【図３】図３は、本発明の実施形態に係わるステートフルスイッチアーキテクチャの一般概念を説明する概略図である。
【図４】図４ａは、本発明の実施形態に係わるワンウェイ状態遷移を持つ２つの組み合わされたＦＳＭテーブルの実装を説明する概略図である。図４ｂは、本発明の実施形態に係わるツールウェイの状態遷移を持つ２つの組み合わされたＦＳＭテーブルの実装を説明する概略図である。
【図５】図５は、本発明の実施形態に係わるワンウェイ遷移、ソフトウェア改良型ステートフルパイプラインを説明する概略図である。
【図６】図６は、本発明の実施形態に係わる図１のポートノッキングアプリケーションのためのワンウェイ遷移ＦＳＭを説明する概略図である。
【図７】図７は、本発明の実施形態に係わる図１のポートノッキングアプリケーションのためのワンウェイ遷移、ソフトウェア改良型ステートフルパイプラインを説明する概略図である。
【発明を実施するための形態】
【００１９】
図１は、状態テーブルに加えてＦＳＭ（Ｆｉｎｉｔｅ  Ｓｔａｔｅ  Ｍａｃｈｉｎｅ：有限ステートマシン）テーブルを実装することによりフェーズ指向のステートレス処理に対して拡張を提供するステートフルＳＤＮ（Ｓｏｆｔｗａｒｅ  Ｄｅｆｉｎｅｄ  Ｎｅｔｗｏｒｋ：ソフトウェアデファインドネットワーク）スイッチの概念を概略的に示す。この拡張により、スイッチングパイプラインにおける各フローの状態の追跡とその状態からの遷移が可能になる。
【００２０】
具体的には、図１は、「ポートノッキング」として知られる単純なステートフルパケット処理アプリケーションの例を示す（Ｇｉｕｓｅｐｐｅ  Ｂｉａｎｃｈｉ、Ｍａｒｃｏ  Ｂｏｎｏｌａ、Ａｎｔｏｎｉｏ  Ｃａｐｏｎｅ、Ｃａｒｍｅｌｏ  Ｃａｓｃｏｎｅ：“オープンステート：スイッチ内のプログラミングプラットフォームから独立したステートフルオープンフローアプリケーション”、ＳＩＧＣＯＭＭ  Ｃｏｍｐｕｔ．  Ｃｏｍｍｕｎ．  Ｒｅｖ．  ４４，  ２（２０１４年４月）、４４−５１ページを参照）。このアプリケーションは、インカミングフローのパケットが所定のポートシーケンスに向けられた後システム内の特定のリモートホスト用のトランスポートポート（例えば、ＳＳＨ接続のためのＴＣＰポート）を開放する。ポートシーケンスがＦＳＭ内の所定のシーケンス（図の例では、ＴＣＰ送信先ポート［Ｐ１，  Ｐ２］のシーケンス）とマッチする場合、接続はある確立状態（すなわち、Ａ／Ｄｒｏｐ）から別の確立状態（すなわち、Ｂ／Ｆｗｄ）に移動する、すなわち、同じ接続のその後の全てのパケットは転送される。
【００２１】
詳細には、ポートＰ１上のマッチＭが失敗すると、各パケットはドロップされシステムは状態Ａにとどまる。マッチが成功すると、各パケットはドロップされるが、システムは状態Ｂに対しスイッチを実行する。一旦状態Ｂに置かれると、ポートＰ２上のマッチが成功した場合、システムは状態Ｂにとどまりそれぞれの接続のその後の全てのパケットが転送される。ポートＰ２上のマッチが失敗するとすぐに各パケットはドロップされ、システムは状態Ａに戻る。
【００２２】
上記のロジックをコンパイルするには、スイッチングパイプラインを図２に示したように修正する必要がある。ここで、状態テーブル１はアーキテクチャの２つのテーブルのうちの第１のテーブルである。キー値、第１マッチルックアップフローテーブルである状態テーブル１では、第１マッチルックアップを行ってそのフローに関連する状態に対してインカミングフローの何らかのパケットヘッダーをマッチさせる。テーブル１内のレコードは、例えば、“オープンフロー”優先属性によって順序づけられる。例えば、図１のポートノッキングの例で、このようなフィールドが接続を開始する各リモートホストのソースＩＰアドレスに対してマッチする場合がある。ルックアップは、インカミングフロー（ホスト）に関連付けられた状態、又はワイルドカードマッチに関連付けられたデフォルトの状態値（オープンフロー用語のＭＡＴＣＨ＿ＡＬＬ）である値を戻す。この状態はその後対応するパケットヘッダーとともに第２のステージであるＦＳＭテーブル２に渡される。スイッチングパイプラインのテーブル１、２の間の状態移動はメタデータフィールドを用いて行われてもよい。
【００２３】
ＦＳＭテーブル２では、パケットヘッダーと転送された状態の組み合わせが次のルックアップのキーになる。この文脈では、ＦＳＭテーブル２内のマッチフィールド（図２で「マッチ＊」で表される、後の図でも同様）は通常、状態テーブル１におけるマッチフィールド（「Ｍａｔｃｈ」で表される）から独立していることに注意されたい。ポートノッキングの例では、ＦＳＭテーブル２のマッチフィールドはＴＣＰ送信先ポートである。状態及びマッチ＊のフィールドの組み合わせにより、図１と関連付けて示したＦＳＭに応じたフロー処理とその状態更新（必要な場合）のためのアクションがとられる。フローの状態更新が必要な場合、フィードバックループは２つのテーブル１、２にかかわり、メッセージｓｅｔ＿ｓｔａｔｅ：  ｐｋｔ＿ｈｅａｄｅｒｓ＋ｎｅｘｔ＿ｓｔａｔｅを特定のフローの更新とともに渡す。キー抽出モジュール３は、パケットヘッダーから状態テーブル１のマッチフィールド用の特定の値を引き出し、それをｎｅｘｔ＿ｓｔａｔｅとともに状態テーブル１に渡し、それにより既存のレコードを更新する、又は新しいエントリを入力する。図２に点線で示されるように、テーブル１、２の両方の開始プログラミングは、中央コントローラ４からのメッセージＳｔａｔｅ＿ｍｏｄ及びＦｌｏｗ＿ｍｏｄによって行われる。これに関し、状態テーブル１は本例では（状態テーブルの一番下に示される）デフォルトのマッチ／状態決定を持つ単一のメッセージＳｔａｔｅ＿ｍｏｄだけを必要とするのに対し、その後の全ての更新はフィードバックループを通じて行われることに注意されたい。
【００２４】
図３は、本発明の実施形態に係わるステートフルスイッチアーキテクチャ５の一般的概念を示す概略図であり、スイッチアーキテクチャ５は２つのステートフルステージ６、７を含み、一方はハードウェアに実装され、他方はソフトウェアに実装されている。この実施形態はソフトウェア改良型ステートフルパケット処理アーキテクチャを提供しており、このアーキテクチャは両プラットフォームの欠点を取り除きながらソフトウェアベース及びハードウェアベースの転送エンジンの利点を効果的に組み合わせている。（図２に典型的に示されるように）ステートフルスイッチングアーキテクチャにおけるハードウェアベースの状態テーブルのサイズ上の制約を克服するために、図３に示す本発明の実施形態はハードウェアベースのステートフルパイプライン６をソフトウェアベースのステートフルパイプライン７で拡張する。これは、全ての新しいフローをソフトウェアベースパイプライン７に転送しソフトウェア状態テーブル８においてフロー毎の状態を維持することにより実行される。過剰なトラフィックによりソフトウェアパイプライン７がオーバーロードになった場合、一部のフローをその状態とともに最終的にハードウェア状態テーブル９に移動することができ、これによりソフトウェアパイプライン７を効果的にオフロードすることができる。
【００２５】
サポートされるフローの総数を拡張するためにソフトウェアからハードウェアへのオフロードを行うハイブリッドのソフトウェア／ハードウェアアーキテクチャがネットワークスイッチやルーターなどのステートレスフォワーダとして開発されてきたことに注意されたい（Ｒｏｂｅｒｔｏ  Ｂｉｆｕｌｃｏ、Ａｎｔｏｎ  Ｍａｔｓｉｕｋ：「スケーラブルＳＤＮスイッチに向かって：フローテーブルへのより速いエントリ入力」、データ通信に関するスペシャルインタレストグループの２０１５  ＡＣＭ会議の会議録（ＳＩＧＣＯＭＭ’１５）．  ＡＣＭ、ニューヨーク（ＮＹ）、アメリカ合衆国、３４３−３４４．  ＤＯＩ＝ｈｔｔｐ：／／ｄｘ．ｄｏｉ．ｏｒｇ／１０．１１４５／２７８５９５６．２７９０００８、又はＮａｇａ  Ｋａｔｔａ、Ｏｍｉｄ  Ａｌｉｐｏｕｒｆａｒｄ、Ｊｅｎｎｉｆｅｒ  Ｒｅｘｆｏｒｄ、Ｄａｖｉｄ  Ｗａｌｋｅｒ：「ソフトウェアデファインドネットワークにおける無限キャッシュフロー」、ソフトウェアデファインドネットワーキングにおけるホットトピックに関する第３回ワークショップの会議録、  （ＨｏｔＳＤＮ’１４）．ＡＣＭ、ニューヨーク（ＮＹ）、アメリカ合衆国、１７５−１８０．  ＤＯＩ＝ｈｔｔｐ：／／ｄｘ．ｄｏｉ．ｏｒｇ／１０．１１４５／２６２０７２８．２６２０７３４を参照）。本発明の実施形態が扱うステートフルフォワーダなどのステートフルフォワーダに同様の原則を適用した場合、状態遷移の処理が危機的になり、ステートレスの場合のように継ぎ目なく実行することができない。実際、ステートフルスイッチの転送テーブルはフィードバックループにより連結されており、このフィードバックループは上記の文書に提案されたものや関連するソリューションと同様、テーブル毎のオフロード方式により壊されてしまう。
【００２６】
単にハードウェアに実装されたステートフルステージのみを持つステートフルパケット処理アーキテクチャから説明する。本発明の実施形態に係わるシステムは以下の要素を提供することにより実現可能である。
【００２７】
１．  “オープンステート”スイッチなどのステートフルスイッチの場合に指定されるようなＦＳＭを、スイッチの動作に対し同じ意味を維持するがハイブリッドのソフトウェア／ハードウェアスイッチに実装される用意ができている２つのＦＳＭに変換するＦＳＭ適応手法。
【００２８】
２．  いつフローがＦＳＭのハードウェア部分又はソフトウェア部分により処理されるかを決定する分散機構又はオフロード方法。
【００２９】
３．  少なくとも２つのステートフルステージ、例えば、ソフトウェアに実装される一方のステージとハードウェアに実装される他方のステージを組み合わせるハイブリッドスイッチ。
【００３０】
以下、これら３つの要素を図を参照してより詳細に説明する。
【００３１】
本発明の実施形態に係わるＦＳＭ適応から説明する。このＦＳＭ適応は、ＦＳＭの分割と組み合わせたＦＳＭの拡張により実現してもよい。本文脈における「ＦＳＭ拡張」とは、スイッチのＦＳＭテーブルにより実装される元々のステートマシンが、分散又はオフロード方式をサポートするという唯一の目的のために導入される追加的な状態や遷移を用いて拡張されることを意味する。本文脈における「ＦＳＭ分割」とは、新しいＦＳＭ（すなわち、上記のように拡張されたＦＳＭ）がそれぞれソフトウェア及びハードウェアのステートフルステージに実装されることになる２つの部分に分割されることを意味する。この分割は、ＦＳＭ拡張により作成された新しい追加的遷移をソフトウェアで実行することにより端的に実行される。しかし、オフロード手順のための実際の遷移アクションが実際の実装によって異なる動作を要求する場合がある。
【００３２】
上記の修正／適応の結果、図３に示すスイッチアーキテクチャにおいて実行可能なＦＳＭ遷移を実行する２セットのフローエントリが取得される。そのようなアーキテクチャを実現するため、ハードウェアベースのＦＳＭ（ＨＦＳＭ）をソフトウェアベースのＦＳＭ（ＳＦＳＭ）で拡張してもよい。その後各ＦＳＭは該当する（ハードウェア及びソフトウェア）ステートフルスイッチングパイプライン６又は７により処理される。
【００３３】
次に（第２の要素として上述した）分散機構を説明する。この機構は通常、いつフローがＦＳＭのハードウェア部分又はソフトウェア部分により処理されるべきかを指定する。以下、この機構を、全ての新しいフローが最初にソフトウェアパイプライン７に転送される実施形態を検討することにより動機付けられたハードウェアオフロード方式として説明する。ハードウェアオフロード方式はその後、すなわち、所定の条件が満たされたとき、特定のフローをソフトウェアパイプライン７からハードウェアパイプライン６へオフロードする。このため、図４に示されるような、２つのＦＳＭ間の追加的状態遷移のためのトリガーを表す“ハードウェアオフロード基準”（Ｈａｒｄｗａｒｅ  Ｏｆｆｌｏａｄ  Ｃｒｉｔｅｒｉｏｎ：ＨＯＣ）が導入される。
【００３４】
ＨＯＣは特定のフロー（すなわち、マッチ／状態のペア）をソフトウェアパイプライン７からハードウェアパイプライン６に移動するための基準であり、これによりソフトウェアパイプライン７がオフロードされる。例えば、フロー毎のＨＯＣ評価のための特定のアルゴリズムがバイト数又はパケット数（すなわち、フロー重量）若しくは特定のフローのためのパケットレート又はその期間を評価し、それに応じてＨＯＣ値を割り当てる。当業者には容易に理解されるように、このアルゴリズムは更に同様のやり方でフローの統計値についての代替的又は追加的な評価を考慮してもよい。いずれの場合でも、そのようなアルゴリズムの任務は、両パイプライン６、７により処理されるフローの分数間のバランスをとり、ソフトウェアステージ７を処理負荷でオーバーロードさせず、ハードウェアステージ６をフロー数でオーバーロードさせないことである。
【００３５】
具体的に、図４は組み合わされたＦＳＭに対する２つの方式を示す。図４に示されたワンウェイ方式はＳＦＳＭからＨＦＳＭへの遷移のみを示している。ここでは、一旦フローがハードウェアスイッチングパイプラインにオフロードされると、フローは、例えば、所与のタイムアウトの終了によりそれ自体の期間満了までそこにとどまる。一方、図４ｂに示すツーウェイ方式では、ＨＯＣ＝Ｆａｌｓｅである場合、オフロードされたフローはＳＦＳＭに戻ることができる。しかしこの場合、アーキテクチャは複雑なものになる。オフロードのアルゴリズムは両ＦＳＭでＨＯＣ値を追跡しそれに応じて状態遷移を行わなくてはならないからである。
【００３６】
次に、（第３の要素としてあげた）ハイブリッドのステートフルスイッチの実装について説明する。図５は２つのステートフルステージからなる本発明の実施形態に係わるスイッチ５を示し、一方がハードウェアパイプライン６に実装され、他方がソフトウェアパイプライン７に実装されている。スイッチ５は図４の組み合わせＦＳＭを実装している（図５のスイッチ５では、ソフトウェアパイプライン７だけがオフロード基準のための評価モジュールであるＨＯＣエバリュエーター１２を含むので、スイッチ５はソフトウェアからハードウェアへのワンウェイ遷移だけを実行できる）。
【００３７】
図５から分かるように、パイプライン６、７はそれぞれ状態テーブル及びＦＳＭテーブルを備えている。“ハードウェア状態テーブル”（Ｈａｒｄｗａｒｅ  Ｓｔａｔｅ  Ｔａｂｌｅ：ＨＳＴ）９には、デフォルトで、ワイルドカードマッチを持つ単一の優先度の低いレコードだけが含まれ、その関連する状態はＳＷ（ソフトウェア）である。ハードウェアＦＳＭテーブル（ＨＦＳＭＴ）１１には、キーの組み合わせ（ＳＷ状態及びワイルドカードマッチ）と関連付けられたデフォルトのレコードに加えて、（ＳＦＳＭ及びＨＦＳＭを生成するためのＦＳＭ適応手順によって生成された）ＨＦＳＭを実装するレコードのセットが含まれる。ＨＦＳＭＴの１１のエントリの１つはＳＷ状態と関連付けられアクションＧｏｔｏ＿Ｓｗを指定する。アクションＧｏｔｏ＿Ｓｗはパケットヘッダーを“ソフトウェア状態テーブル”（Ｓｏｆｔｗａｒｅ  Ｓｔａｔｅ  Ｔａｂｌｅ：ＳＳＴ）８、すなわち、ソフトウェアパイプライン７に実装されたステートフルステージに転送する。このような転送は「Ｇｏｔｏ−テーブル」“オープンフロー”インストラクションを用いて端的に実行してもよい。このように、ＨＳＴ  ９に関連する詳細なレコードを持たない新しいフローはデフォルトのレコードにより処理され、更なる処理のためにソフトウェアパイプライン７に転送される。
【００３８】
ソフトウェアパイプライン７では、ＳＳＴ  ８がフロー毎のレコード、更に新しいフローのためのワイルドカードのデフォルト状態を維持し、状態とパケットヘッダーを“ソフトウェアＦＳＭテーブル”（Ｓｏｆｔｗａｒｅ  ＦＳＭ  Ｔａｂｌｅ：ＳＦＳＭＴ）１０に渡す。ソフトウェアＦＳＭテーブル１０には、オフロード（より一般的には、分散）手順を扱うために用いられる（‘ＨＯＣ’で示される）追加的なマッチフィールドが含まれる。ＨＯＣ＝Ｆａｌｓｅの場合、フローとその状態はソフトウェアパイプライン７で完全に処理される。一方、ＨＯＣ＝Ｔｒｕｅの場合、スイッチ５は対応するフローのハードウェアへのオフロードを実行する。事実上、これは、［ｍａｔｃｈ，  ｓｔａｔｅ］のペアに関連付けられたフローが、ＨＳＴ  ９においてそのフローの状態を変更するインストラクションｓｅｔ＿ｓｔａｔｅ：  ｎｅｘｔ−ｓｔａｔｅによって更新されることを意味する。ＨＳＴ  ９におけるそのようなフローの状態はＳＷから異なる状態に変更されているので、そのようなフローに属するその後のパケットはＨＦＳＭＴ  １１において処理される。
【００３９】
スイッチ５は、ＨＯＣエバリュエーターモジュール１２を実装して、例えば、その内部アルゴリズムと所定の基準にしたがってフロー毎のＨＯＣ値を算出し、それによりＳＦＳＭテーブル１０内の対応するＨＯＣ値を更新してもよい。ＨＯＣエバリュエーター１２は、例えば、パイプラインの他のテーブル（例えば、メータリングテーブル）から（バイト／パケットカウンター、フローの持続時間などの）フロー毎の統計値を抽出し、それを所定のしきい値と比較し、対応するＨＯＣ値を設定するように構成されてもよい。
【００４０】
また、ＦＳＭ適応プロセスの結果として生成されたＳＦＳＭＴ  １０とＨＦＳＭＴ  １１には、アクションｏｆｆ＿ｓｔａｔｅ＿ｈｗ及びＧｏｔｏ  ＳＷが含まれる。スイッチ５の実装オプションによっては、スイッチングパイプライン６、７は異なる手段や技術により接続されてもよい。例えば、ソフトウェアパイプライン７を外部のソフトウェアスイッチにおいて実現する場合、２つのパイプライン６、７は外部接続により接続された２つの物理的に分離されたデータパスを用いて実装されてもよい。このように、ｏｆｆ＿ｓｔａｔｅ＿ｈｗ  及びＧｏｔｏ  ＳＷの実現は実装に依存する。例えば、このようなアクションにはインカミングパケットと関連付けられたメタデータの適応が必要となる場合がある。
【００４１】
アクションｏｆｆ＿ｓｔａｔｅ＿ｈｗにより、スイッチ５は以下のように特定のフロー（すなわち、［ｍａｔｃｈ，  ｓｔａｔｅ］のペア）をＨＳＴ  ９にオフロードすることができる。特定のフローの状態をインストラクションｓｅｔ＿ｓｔａｔｅ：  ｎｅｘｔ＿ｓｔａｔｅを持つＳＦＳＭにしたがって更新する必要がある場合、キー抽出モジュール３がこのフローをＨＳＴ  ９に転送するように、このインストラクションを（例えば、状態テーブルの異なるアドレスを指定することにより）単純に修正してもよい。一方、現在のフローの状態ＳＳｊを更新する必要はないがＨＯＣ＝Ｔｒｕｅである場合、インストラクションｏｆｆ＿ｈｗはインストラクションｓｅｔ＿ｓｔａｔｅにおける現在の状態値をコピーし（ＳＳｊ≠Ｓｊの場合、修正し）それをＨＳＴ  ９に転送してもよい。
【００４２】
オフロードされたフローをソフトウェアパイプライン７に戻す能力を提供する（図４ｂに示されるような）ツーウェイ遷移ＦＳＭを実装するには、ソフトウェアパイプラインについて説明した拡張のようなハードウェアパイプライン６への類似の拡張（すなわち、ＨＯＣエバリュエーター１２及びＦＳＭテーブルの拡張の提供）が必要となる。この場合、ＨＯＣ＝Ｆａｌｓｅであれば、ＨＦＳＭＴは状態テーブルの更新をＨＦＳＭＴ  １１からＳＳＴ  ８に転送するインストラクションｏｆｆ  ＿ｓｔａｔｅ＿ｓｗを適用する。当業者は、図４ｂに示された方式からこのようなツーウェイ遷移ステートフルパイプラインの方式を端的に引き出すであろう。
【００４３】
図６は、図１に関連して説明したポートノッキングアプリケーションに適応させたワンウェイ遷移ＦＳＭを表す本発明の実施形態を示す。すなわち、図６に示したＦＳＭは、図１のＦＳＭに適用された場合にＦＳＭ適応プロセスにより生成されるＦＳＭである。ＳＦＳＭ、ＨＦＳＭ間の分離は図６の点線によって示される。ソフトウェアＦＳＭからハードウェアＦＳＭへの合計４つの異なる条件が実行される。これらの遷移の典型例を説明する。ポートＰ１上のマッチＭが失敗すると、各パケットはドロップされ、システムは（ＨＯＣ＝Ｆａｌｓｅの場合）状態ＡＳにとどまる、又は（ＨＯＣ＝Ｔｒｕｅの場合）ハードウェア状態Ａに遷移する  。一方、このマッチが成功すると、各パケットはドロップされるが、システムは（ＨＯＣ＝Ｆａｌｓｅの場合）状態ＢＳに対して、（ＨＯＣ＝Ｔｒｕｅの場合）ハードウェア状態Ｂに対してスイッチを実行する。
【００４４】
当業者により容易に理解されるように、ツーウェイＦＳＭの場合、条件ＨＯＣ＝Ｆａｌｓｅを満足させるためにＨＦＳＭからＳＦＳＭに戻る４つの追加的状態遷移が必要となる。
【００４５】
図７はポートノッキングアプリケーションのための組み合わされたＦＳＭの実装を示す。特定の各ＦＳＭ状態遷移は該当するＦＳＭテーブルにコンパイルされ、ＦＳＭ間の４つの状態遷移はＨＯＣ＝Ｔｒｕｅ及び追加的アクションｏｆｆ＿ｈｗを持つエントリとしてＳＦＳＭテーブルにコンパイルされる。それぞれの新しいフローについては、別個の状態レコードがソフトウェア状態テーブル８に維持され（例えば、ＩＰ１、ＩＰ３）、ＨＯＣ＝Ｔｒｕｅ（例えば、フローサイズ又はフローレートが所定のしきい値を横切る）を持つフローがＨＳＴ  ９にオフロードされる。これにより、ＨＳＴ  ９は限定されたサブセットの重い又はレートインセンティブなフローだけを維持し、その結果ソフトウェアＦＳＭテーブル１０における固定された少数の追加的エントリを犠牲にしてソフトウェアパイプライン７がオフロードされる。
【００４６】
ここで説明した本発明の変形例や他の実施形態が、本発明が関係し上記の説明や添付の図面に示された内容の利点を受ける当業者により想到されよう。従って、本発明は開示された特定の実施形態に限定されるべきではなく、変形例や他の実施形態が添付の特許請求の範囲に含まれることが意図されていると理解すべきである。ここでは特定の用語が使われているが、それらは限定する目的ではなく一般的及び説明的意味で使われている。
【符号の説明】
【００４７】
１  状態テーブル
２  ＦＳＭテーブル
３  キー抽出モジュール
４  コントローラ
５  ステートフルスイッチ
６  ハードウェアステートフルステージ
７  ソフトウェアステートフルステージ
８  ソフトウェアステートテーブル（ＳＳＴ）
９  ハードウェアステートテーブル（ＨＳＴ）
１０  ソフトウェアＦＳＭテーブル（ＳＦＳＭＴ）
１１  ハードウェアＦＳＭテーブル（ＨＦＳＭＴ）
１２  ＨＯＣエバリュエーター
【図１】
2019510428.tif 000003
【図２】
2019510428.tif 000004
【図３】
2019510428.tif 000005
【図４】
2019510428.tif 000006
【図５】
2019510428.tif 000007
【図６】
2019510428.tif 000008
【図７】
2019510428.tif 000009
【国際調査報告】
2019510428.tif 000010
2019510428.tif 000011
2019510428.tif 000012