(57)【要約】【課題】  効率的なテーブル処理のコアの割り当てを決定し、マルチテーブルにおけるパケット処理を高速化する。【解決手段】  本発明は、各テーブルが使用する使用メモリまたは該テーブルの各エントリを検索するために必要な予想検索時間またはパケット処理を行う予想パケット処理時間を含む検索テーブルの情報のうちのいずれか少なくとも一つを取得し、該検索テーブルの情報に基づいて、各コアの処理時間が同じになるようにテーブルの検索とパケット処理のうちの少なくともいずれかを各コアに割り当て、割当結果を出力し、割当結果に基づいて、コアで行う処理内容の変更及び制御を行う。【選択図】  図７
2015231110.tif 000002
【特許請求の範囲】
【請求項１】
マルチコアCPUを有するフロースイッチの各コアに処理を割り当てるCPU割当装置であって、
各テーブルが使用する使用メモリまたは該テーブルの各エントリを検索するために必要な予想検索時間またはパケット処理を行う予想パケット処理時間を含む検索テーブルの情報のうちのいずれか少なくとも一つを取得し、該検索テーブルの情報に基づいて、各コアの処理時間が同じになるようにテーブルの検索とパケット処理のうちの少なくともいずれかを各コアに割り当て、割当結果を出力する処理コア管理手段と、
前記割当結果に基づいて、前記コアで行う処理内容の変更及び制御を行う処理コア制御手段と、
を有することを特徴とするCPU割当装置。
【請求項２】
前記処理コア管理手段は、
前記検索テーブルの処理内容を、前記検索テーブルの情報に基づいて、フロー検索処理とパケット処理のいずれか、または、フロー検索処理とパケット処理の組み合わせに分割し、分割された結果に基づいて各コアに割り当てる処理を決定する割当手段を含む
請求項１記載のCPU割当装置。
【請求項３】
前記割当手段は、
フロー検索処理またはパケット処理に時間がかかるエントリと時間がかからないエントリに分割する手段と、
前記フロー検索処理またはパケット処理に時間がかからないエントリは、元のコアａで処理を行うように割り当て、前記時間がかかるエントリは、該コアａとは異なるコアｂで処理を行うように割り当てる手段と、
を含む請求項２記載のCPU割当装置。
【請求項４】
前記割当手段は、
テーブル毎、エントリ毎の処理を行う頻度に応じて、該処理に対して重み付けを行う手段と、
重みに基づいて、前記検索テーブルの処理を分割し、分割した該処理を各コアに割り当てる手段と、
を含む請求項２記載のCPU割当装置。
【請求項５】
前記重みは、
エントリの中で最も処理の時間がかかるエントリの処理時間、
各エントリの各処理の処理時間の平均、
各エントリの処理時間に、到達パケットが各エントリにヒットする確率を乗算したもの
のいずれかを用いる
請求項４記載のCPU割当装置。
【請求項６】
マルチコアCPUを有するフロースイッチの各コアに処理を行うテーブルを割り当てる装置におけるCPU割当方法であって、
各テーブルが使用する使用メモリまたは該テーブルの各エントリを検索するために必要な予想検索時間またはパケット処理を行う予想パケット処理時間を含む検索テーブルの情報のうちのいずれか少なくとも一つを取得し、該検索テーブルの情報に基づいて、各コアの処理時間が同じになるようにテーブルの検索とパケット処理のうちの少なくともいずれかを各コアに割り当て、割当結果を出力する処理コア管理ステップと、
前記割当結果に基づいて、前記コアで行う処理内容の変更及び制御を行う処理コア制御ステップと、
を行うことを特徴とするCPU割当方法。
【請求項７】
コンピュータを、
請求項１ないし５のいずれか１項に記載のCPU割当装置の各手段として機能させるためのCPU割当プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、CPU割当装置及び方法及びプログラムに係り、特に、OpenFlow(登録商標)  Wire Protocolに代表されるような、マルチコアCPU環境におけるマルチテーブルのフロー検索やパケット処理に対して、効率的な処理割り当てを行うためのCPU割当装置及び方法及びプログラムに関する。
【背景技術】
【０００２】
近年、OpenFlow(登録商標) Wire Protocol等の通信制御をフロー単位で行い、より粒度の細かいサービス品質制御、経路制御を可能とするフローベースネットワーキングの利用が広がっている。フローとは、MAC（Media Access Control）アドレスやVLAN(Virtual LAN)におけるVID、IP(Internet Protocol)アドレス、ポート番号等で識別される。アプリケーション毎の一連の通信のまとまりであり、フローベースネットワーキングではユーザやアプリケーションに応じたQoS制御やパケットヘッダの書き換え、経路制御が可能となる。
【０００３】
フローベースネットワーキングの中継ノードであるフロースイッチでは、フローテーブルに登録されたエントリを参照して、エントリに従ったパケットヘッダの書き換え、パケットの送出等を行う。フローエントリは、エントリの優先度、受信ポートやヘッダの各情報に相当するフィールドを持つ一致条件、一致条件に一致したパケットに行う処理内容によって構成される。
【０００４】
OpenFlow (登録商標) Wire Protocolに代表される最近のプロトコルに対応するフロースイッチでは、フローテーブルの簡易性向上のため、複数のフローテーブル（マルチテーブル）を扱うことができる。図１の中央部に示すように、"table 0"から順にフロー検索とパケット処理を繰り返す。
【０００５】
これまで、フロースイッチにおけるマルチテーブル処理は、図２に示すように、一つのパケットに対し、一つのコアがすべてのテーブル処理を行っていた。
【０００６】
また、単純な並列化としては、図３に示すように、テーブルの数を基準に各コアに処理を行うテーブルを分割する手法が考えられる。
【０００７】
また、テーブルのエントリをMaskを持つものとMaskを持たないものに分け、Maskを持たないものはハッシュでCPUで行い、Maskを持つものはNIC(Network Interface Card)やGPU(Graphics Processing Unit))に処理をオフロードする手法が知られている（例えば、非特許文献１，２参照）。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】Sangjin Han, Keon Jang, KyoungSoo Park, and Sue Moon.  Packetshader: a gpu-accelerated software router. ACM SIGCOMM Computer Communication Review, 40(4): 195-206, 2010.
【非特許文献２】Voravit Tanyingyong, Markus Hidell, and Peter sjodin.  Inproving pc-based Openflow switching performance.  In Proceedings of the 6th ACM/IEEE Symposium on Architectures for Networking and Communications Systems, page 13. ACM, 2010.
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかし、図２の例のように、１つのコアが全てのテーブルのルックアップを行う方法では、CPUキャッシュのキャッシュミスが増え、検索速度が劣化する。
【００１０】
また、図３の例のようにテーブルの数を基準とした並列化では、CPUのアイドル時間（図４のコアの待ち時間）が増え、効率的な並列が達成できない。
【００１１】
また、Maskを持つエントリとMaskを持たないエントリに分ける手法では、Maskを持たないエントリが大半であった場合、エントリを分割しない手法と違いがない。
【００１２】
これらの課題は、各テーブルで行うフローの検索、及びパケットへの処理の時間が一定でないこと、複数のテーブルの処理を一つのコアで行うとキャッシュミスが増加することが原因である。
【００１３】
本発明は、上記の点に鑑みなされたもので、効率的なテーブル処理のコアの割り当てを決定し、マルチテーブルにおけるパケット処理を高速化できるCPU割当装置及び方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１４】
一態様によれば、マルチコアCPUを有するフロースイッチの各コアに処理を割り当てるCPU割当装置であって、
各テーブルが使用する使用メモリまたは該テーブルの各エントリを検索するために必要な予想検索時間またはパケット処理を行う予想パケット処理時間を含む検索テーブルの情報のうちのいずれか少なくとも一つを取得し、該検索テーブルの情報に基づいて、各コアの処理時間が同じになるようにテーブルの検索とパケット処理のうちの少なくともいずれかを各コアに割り当て、割当結果を出力する処理コア管理手段と、
前記割当結果に基づいて、前記コアで行う処理内容の変更及び制御を行う処理コア制御手段と、を有するCPU割当装置が提供される。
【発明の効果】
【００１５】
一態様によれば、テーブルの処理を各コアに均等に分配し、並列化の効率を上げることにより、フロースイッチのフロー検索処理及びパケット処理を高速に行うことができ、フロースイッチの高速化を図ることができる。
【図面の簡単な説明】
【００１６】
【図１】従来のマルチテーブル処理の例。
【図２】従来のマルチテーブル処理において一つのコアがすべてのテーブルのルックアップを行う例。
【図３】従来のテーブルの数を基準にテーブルを分割する例。
【図４】コアに対する単純割り当て時のテーブルの処理時間とコアの待ち時間の例。
【図５】本発明の一実施の形態における処理概要を示す図。
【図６】本発明の一実施の形態におけるCPUに均等に割り当てた場合のコアの例。
【図７】本発明の一実施の形態におけるシステム構成例。
【図８】本発明の一実施の形態における検索テーブルの例。
【図９】本発明の一実施の形態におけるテーブルの処理分割の単位を説明するための図。
【図１０】本発明の一実施の形態におけるパケット処理の分割の例。
【発明を実施するための形態】
【００１７】
以下、図面と共に本発明の実施の形態を説明する。
【００１８】
まず、本発明の概要を説明する。
【００１９】
図５は、本発明の一実施の形態における処理概要を示す。
【００２０】
本発明は、マルチテーブルの各テーブルで行うフローの検索処理及びパケット処理の時間及び、メモリ使用量を取得、または、推定し、各CPUに均等に負荷が分散されるようフローの検索及びパケット処理を分割し、各コアに割り当てる。メモリ使用量を取得することで、テーブル分割の際に、フローの検索及び処理がCPUのキャッシュメモリ内に収まると高速に動作可能であるため、メモリ使用量を処理時間計算の手掛かりとする。これにより、CPUキャッシュを有効活用した検索及び処理を実現できる。
【００２１】
各CPUに均等に負荷を分散することによって図６に示すように各コアのアイドル時間が削減され、単位時間あたりに処理可能なパケットの量も増加する。処理時間を完全に均等に割ることは難しいため、従来の単純なテーブル単位での処理割り当てよりも、本発明により処理を割り当てた場合、負荷を分散できたと判断する。勿論、可能な限り均等に近づけることが望ましい。
【００２２】
例えば、図４、図６の例における各テーブルの処理時間を以下の通りとする。
【００２３】
table 0  28
table 1  10
table 2  10
table 3  10
table 4  14
table 5  14
図４、図６では、３つのコアで処理しているが、x個のパケットを処理する際、xが十分大きければ（(x+2)/x=1と考えても差し支えない程度に大きい）一個あたりのパケット処理時間tは以下の通りとなる。ここで、T(corex)tとはコアxにおけるパケットの処理時間であり、T(tablei)はtalbeiにおける処理時間を示す。
【００２４】
従来技術である図４の単純な並列化時の処理時間は以下通りである。
【００２５】
T(corea)=T(table0)+T(table1)=38
T(coreb)=T(table2)+T(table3)=20
T(corec)=T(table4)+T(table5)=28
T=max(T(corea),T(coreb),T(corec))×(x+2)/x
xは十分大きいので、
t=38
となる。
【００２６】
本発明の図６の均等な割り当て時の各コアの処理時間は以下の通りである。
【００２７】
T(corea)=T(table0)=28
T(coreb)=T(table1)+T(table2) +T(table３)=30
T(corec)=T(table4)+T(table5)=28
T=max(T(corea),T(coreb),T(corec))×(x+2)/x
xは十分大きいので、
t=30
となる。
【００２８】
上記の例では、単純な並列化時（図４）よりも各コアの処理時間が均等になるよう分割した方が約1.27倍高速に処理できることがわかる。
【００２９】
以下に、本発明の処理を詳細に説明する。
【００３０】
図７は、本発明の一実施の形態におけるシステム構成例を示す。
【００３１】
同図に示すシステムは、フロールール入力部１０、検索テーブル管理部２０、検索テーブル３０、フロー検索・パケット処理部４０、CPU割当装置１００を有する。
【００３２】
検索テーブル管理部２０は、フロールール入力部１０から取得したフロールールに基づいて検索テーブル３０を生成する。図８に検索テーブル３０の例を示す。同図に示す各値は、"値"、"値／bitmask"、"*"のいずれかであり、"*"はDon't careを表す。なお、他のヘッダフィールドも検索で使用でき、ヘッダ情報だけに限定されない（例えば、ペイロードの一部など）。
【００３３】
CPU割当装置１００は、処理コア管理部１１０と処理コア制御部１２０を有する。
【００３４】
CPU割当装置１００は、フロールール入力部１０から入力されたフロールールより検索テーブル管理部２０から、作成された検索テーブル３０の各テーブルが使用するメモリ及び各テーブルの各エントリを検索するために必要な予想検索時間、パケット処理を行う予想パケット処理時間等の検索テーブル３０の情報を取得し、その情報を用いてフロー検索・パケット処理部４０におけるコアの処理割り当てを行う。
【００３５】
処理コア管理部１１０は、検索テーブル管理部２０より、各テーブルが使用する使用メモリ及び各テーブルの各エントリを検索するために必要な予想検索時間等の、検索テーブル３０の情報を取得し、フロー検索とパケット処理を行う各コアでどのテーブルのどの処理を行うかを決定し、これを処理コア制御部１２０に対して、これらの情報をプログラム中の関数の引数などとして伝える。
【００３６】
処理コア制御部１２０は、処理コア管理部１１０から取得した情報に従い、フロー検索・パケット処理部４０に対し、各コアで行うフロー検索及びパケット処理の処理内容を出力する。
【００３７】
フロー検索・パケット処理部４０は、これらの内容に従い、各コアで行う処理を変更する。
【００３８】
以下に、処理コア管理部１１０と処理コア制御部１２０の処理について詳述する。
【００３９】
処理コア管理部１１０は、取得した検索テーブル３０の内容からパケット処理を行う各コアでどの処理を行うかを決定し、処理コア制御部１２０にフロー検索・パケット処理及びコアの割当リストとして出力する。処理コア決定の動作については後述する。
【００４０】
処理コア制御部１２０は、処理コア管理部１１０で決定され、入力されたフロー検索・パケット処理及びコアの割当リストに従い、フロー検索・パケット処理部４０に対し、各コアで行う処理内容を変更し、制御する。
【００４１】
以下、処理コア管理部１１０の処理コア決定の動作を説明する。
【００４２】
処理コア管理部１１０では、検索テーブル３０の処理内容を分割し、分割した結果を基に各コアへ割り当てる処理を決定する。検索テーブルの処理内容の分割は以下の２つの方法がある。
【００４３】
(a)「フロー検索処理」と「パケット処理」の分割；
(b)検索テーブルの分割；
上記の(a)、(b)を組み合わせ、フロー検索またはパケット処理に時間がかかるエントリとそうでないエントリに分割し、パケット処理に時間がかかるエントリにはフロー検索とパケット処理で別のコアを割り当てる方法がある（図９(a)）。ここで、時間がかかるエントリとは、パケットヘッダの複数の書き換えやプロトコル処理、トンネリングプロトコルによるヘッダの付け外しなどが、そのエントリにマッチした際に行われるパケット処理として記述されたエントリである。検索テーブル３０中に前述のようなパケット処理が記述されたエントリは時間がかかるエントリとして判断できる。また、図９(b)のように、フロー検索処理は「core a」に、パケット処理は「core b」に振り分ける方法がある。
【００４４】
また、フロー検索を行い、処理に時間がかかるエントリにマッチした場合には、フロー検索は自コア（検索を行ったコア）で、別のコアでパケット処理を行い、処理に時間がかからないエントリの場合にはフロー検索に加えて自コアでパケット処理を行う割当方法もある（図１０）。ここで、「処理に時間がかかる」とは、n(n≧１)個のパケットヘッダの書き換え処理、プロトコル処理、トンネリングプロトコルのヘッダの変更、複雑な一致条件（比較するbit数が高い、bitmaskが指定されている）である場合等を指す。図１０の例では、「core a」にフロー検索処理と軽いパケット処理が指定された「table 0」がある場合、フロー検索処理と軽いパケット処理（table 0）は「core a」で行い、処理時間がかかる重いパケット処理(talbe 0-b)は「core c」で行うように振り分ける。
【００４５】
従来の処理の分割方法は、テーブル単位でしか考慮されていなかったが、本発明の上記の２種類の処理の分割を行うことでテーブル単位からフロー検索処理、パケット処理の単位に処理の単位を小さくすることができ、より均等に処理を分散することができる。
【００４６】
さらに、テーブル毎、エントリ毎に処理を行う頻度は異なるため、これらも考慮して分割した各処理に重み付けを行い、その結果を元に各コアの処理割り当てを決定することも可能である。
【００４７】
例えば、各テーブルのフロー検索処理やパケット処理の処理時間は以下の基準で決定できる。
【００４８】
(a)エントリの中で最も処理の時間がかかるエントリの処理時間；
(b)各エントリの各処理の処理時間の平均；
(c)各エントリの処理時間に、到達パケットが各エントリにヒットする確率を掛けたもの；
上記の重み付けの重みは、例えば、(c)の到達パケットがエントリにヒットする確率のことである。到達パケットがエントリにヒットする確率は、あらかじめ何らかの方法で予想しておくか、ある程度運用し、その際に取得し、エントリのヒット数を取得し、確率を計算することで求めることができる。
【００４９】
処理コア制御部１２０は、上記のように、処理コア管理部１１０で割り当てられた処理を行うテーブルをコアに設定するようフロー検索・パケット処理部４０を制御する。
【００５０】
なお、図７に示すCPU割当装置１００の構成要素の動作をプログラムとして構築し、CPU割当装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００５１】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【００５２】
１０  フロールール入力部
２０  検索テーブル管理部
３０  検索テーブル
４０  フロー検索・パケット処理部
１００  CPU割当装置
１１０  処理コア管理部
１２０  処理コア制御部
【図１】
2015231110.tif 000003
【図２】
2015231110.tif 000004
【図３】
2015231110.tif 000005
【図４】
2015231110.tif 000006
【図５】
2015231110.tif 000007
【図６】
2015231110.tif 000008
【図７】
2015231110.tif 000009
【図８】
2015231110.tif 000010
【図９】
2015231110.tif 000011
【図１０】
2015231110.tif 000012