(57)【要約】【課題】  一度に受信した最後のパケットの木との照合を行うとき、ノードの読み込み時間中に照合ができる他のパケットが無い為に発生する、性能低下を抑制する。【解決手段】  パケット処理装置は、複数のパケットを順序付けて記憶するパケット記憶手段と、パケットのデータから得られるキーを探索キーとするノードで構成され、末端ノードがパケットの処理を特定するデータを含む木を記憶する木記憶手段と、パケットから探索キーを得て、木のノードを辿ってパケットの処理を決定する探索処理を、木記憶手段から次ノード情報を読み込む時間を利用して、複数パケットについて、付けられた順序にしたがって開始して並列に実行する木探索手段と、パケットごとに探索処理で辿るノード数の予測値を求め、当該予測値の多い順にパケット記憶手段内の複数のパケットを順序付けるスケジューリング手段と、を備える。【選択図】      図４
2016100624.tif 000002
【特許請求の範囲】
【請求項１】
複数のパケットを順序付けて記憶するパケット記憶手段と、
パケットのデータから得られるキーを探索キーとするノードで構成され、末端ノードがパケットの処理を特定するデータを含む木を記憶する木記憶手段と、
パケットから探索キーを得て、前記木のノードを辿ってパケットの処理を決定する探索処理を、前記木記憶手段から次ノード情報を読み込む時間を利用して、複数パケットについて、付けられた順序にしたがって開始して並列に実行する木探索手段と、
パケットごとに前記探索処理で辿るノード数の予測値を求め、当該予測値の多い順に前記パケット記憶手段内の複数のパケットを順序付けるスケジューリング手段と、
を備えるパケット処理装置。
【請求項２】
識別子とノード数を関連付けて記憶する予測表を記憶する予測表記憶手段をさらに備え、
前記スケジューリング手段は、パケットに格納されているデータの一部から前記識別子を得て、当該識別子で前記予測表を探索してノード数の前記予測値を得る、請求項１のパケット処理装置。
【請求項３】
前記スケジューリング手段は、パケットの前記識別子と、当該パケットの前記探索処理で辿られたノード数を得て、当該ノード数に基づいて前記予測表のノード数を更新する、請求項２のパケット処理装置。
【請求項４】
前記木記憶手段は、前記木の所定の深さのノードとノード数を関連付けて記憶し、
前記スケジューリング手段は、パケットから探索キーを得て、前記木のノードを前記所定の深さまで辿って、到達したノードに関連付けられているノード数を前記予測値として得る、請求項１のパケット処理装置。
【請求項５】
前記スケジューリング手段は、パケットから探索キーを得て、前記木のノードを前記所定の深さまで辿って到達したノードを当該パケットに記録し、
前記木探索手段は、パケットに記録されているノードから前記探索処理を開始する、請求項４のパケット処理装置。
【請求項６】
パケットを受信する１以上の通信手段と、
前記通信手段からパケットを複数受信し、前記パケット記憶手段に記憶させるパケット受信手段と、
前記木探索手段によりパケットに対して決定された処理を、該パケットに適用するパケット処理手段と、
をさらに備える請求項１乃至５の何れか１項に記載のパケット処理装置。
【請求項７】
複数のパケットを順序付けて記憶し、
パケットのデータから得られるキーを探索キーとするノードで構成され、末端ノードがパケットの処理を特定するデータを含む木を木記憶手段に記憶し、
パケットから探索キーを得て、前記木のノードを辿ってパケットの処理を決定する探索処理を、前記木記憶手段から次ノード情報を読み込む時間を利用して、複数パケットについて、付けられた順序にしたがって開始して並列に実行する方法であって、
パケットごとに前記探索処理で辿るノード数の予測値を求め、当該予測値の多い順に記憶している前記複数のパケットを順序付ける、パケット処理方法。
【請求項８】
識別子とノード数を関連付けて記憶する予測表をさらに記憶し、
パケットに格納されているデータの一部から前記識別子を得て、当該識別子で前記予測表を探索してノード数の前記予測値を得る、請求項７のパケット処理方法。
【請求項９】
前記木の所定の深さのノードとノード数を関連付けて記憶し、
パケットから探索キーを得て、前記木のノードを前記所定の深さまで辿って、到達したノードに関連付けられているノード数を前記予測値として得る、請求項７のパケット処理方法。
【請求項１０】
コンピュータに、請求項７乃至９の何れか１項のパケット処理方法を実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パケット処理装置、パケット処理方法、および、プログラム、特に、パケット処理過程で木の探索を行うパケット処理装置、パケット処理方法、および、プログラムに関する。
【背景技術】
【０００２】
高速にパケットを処理するため、ネットワークインタフェースから一度に複数のパケットを受信する技術が開示されている（非特許文献１）。
【０００３】
受信されたパケットはルールに従って処理される。ルールは、処理を適用すべき対象パケットのヘッダ情報と、適用すべき処理の組によって構成されるのが一般的である。そのため、パケット処理においては、ルールとパケットとの照合が行われる。照合は、木を探索することによって行われる場合がある（特許文献１）。
【０００４】
木は、一般的に図１に図示されるような構造を有する。すなわち、木は階層化された複数のノードで構成され、階層の上位のノードから、１以上の下位のノードに対するリンクが張られている。木において、最上位のノード（図１おける、２重丸のノード）はルートノードと呼ばれ、最下位のノード（図１おける、Ａ乃至Ｆのノード）は葉ノードまたは末端ノードと呼ばれる。
【０００５】
木とパケットの照合は、パケットの宛先アドレス等から求められるキーを用いて行われる。木とパケットの照合は、パケットのキーとノードに格納されているキーとを照合してリンクを選択し、選択したリンクを辿って次に照合に用いるべきノードを求め、さらにパケットのキーと該次のノードのキーとの照合を繰り返すことで進行する。木とパケットの照合は、一般的に、パケットのキーとルートノードのキーとの照合で始まり、幾つかの中間ノードを辿って、葉ノードに到達して終了する。葉ノードは、パケットに適用される処理を特定する情報を含む。
【０００６】
ノードを辿る過程で、あるノードの照合を終えたとき、処理装置は、選択したリンクの先に有る次のノードのデータを参照する。該データが処理装置のキャッシュに存在しない場合、すなわちキャッシュミスが発生する場合、処理装置は、該データをメインメモリから読み込む必要がある。この時、大きな読み込み待ち時間が発生する。読み込み待ちを行っている間、処理装置は待ち状態となる為、木探索性能は大きく低下する。
【０００７】
図２は、パケットのキーとノードのキーとの照合処理と、ノード情報の読み込み時間の発生シーケンス例を示す。図２の例は、パケットのキーとノードのキーとの照合処理を丸で示し、読み込み時間を長方形で示している。
【０００８】
照合処理を示す丸の中には、照合対象となっているパケット番号と木のノードの深さの組が表示されている。例えば、１−２は、パケット番号１における、木の２段目のノードとの照合処理であることを示している。以降、この照合処理は、ノード照合処理１−２と表記され、他の照合処理もこの例に従って表記される。パケットと葉ノードとの照合処理を示す丸はハッチングして示されている。
【０００９】
一方、処理装置にはプリフェッチ機能と呼ばれる先読み機能が備わっている。この機能は、指定したアドレスのデータをメインメモリからキャッシュに読み込むことをメモリ制御装置に指示する機能である。この機能を利用することで、あるパケットの処理に必要なデータをメインメモリから読み込んでいる間に、処理装置が別のパケットを処理することが可能となる。処理装置がコンピュータのＣＰＵ（Central Processing Unit）である場合、プリフェッチ機能は、プリフェッチ命令として実装されている。
【００１０】
図３は、プリフェッチ機能を利用した場合の、パケットとノードとの照合処理と、木の読み込み時間の発生シーケンス例を示す。例えば、処理装置は、ノード照合処理１−１において、ノード照合処理１−２に用いるデータのアドレスを求め、該アドレスのデータをキャッシュに読み込むことをメモリ制御装置に指示する。メモリ制御装置がこのデータを読み込んでいる間、処理装置は、ノード照合処理２−１及び３−１を実行することができる。
【００１１】
また、ノード照合処理１−２においては、データがキャッシュに存在するため、処理装置は、データの読み込みにかかる時間を大きく削減できる。さらに、パケット番号１と木との照合処理は１−２で終了したため、ノード照合処理３−２の次には、処理装置は、パケット番号４に関する照合処理であるノード照合処理４−１を実行できる。
【００１２】
処理装置は、図２の例では、長方形で示しているデータの読み込み時間中、読み込み完了を待ち合わせているのに対し、図３の例では、他のパケットの照合処理を実行できる。すなわち、非特許文献１に開示されている技術と、プリフェッチ機能を用いることで、木とパケットの照合処理を効率よく実行できる。
【先行技術文献】
【特許文献】
【００１３】
【特許文献１】特表2014-504042号公報
【非特許文献】
【００１４】
【非特許文献１】Intel Data Plane Development Kit（http://dpdk.org/）
【発明の概要】
【発明が解決しようとする課題】
【００１５】
処理装置が一度に受信するパケットの数は有限であり、受信した最後のパケットの照合を行うとき、メインメモリからのデータの読み込み時間中にノード照合処理ができる他のパケットが無いことがある。
【００１６】
図３の例で、パケット番号５以降をネットワークインタフェースから受信していない場合、ノード照合処理４−３以降に使用するデータをメインメモリから読み込む時間に、処理装置がノード照合処理を実行できる他のパケットが存在しない。このため、データをメインメモリから読み込む間、処理装置が有効に動作しない。図３は、この時間を、データの読み込み時間を示す長方形に斜線を付して示している。
【００１７】
最後のパケットと木との照合において、木の探索が深い場合、パケット処理性能の低下を招く。パケット処理においては、パケットと木のノードとの照合回数が数十から数百にも上ることが想定される。そのため、性能低下は大きくなる。
【００１８】
なお、上記説明は、ノード情報を、メインメモリから処理装置のキャッシュに読み込む場合を想定したものであるが、ノード情報をディスク装置からメインメモリに読み込む場合についても同様である。但し、この場合、特にプリフェッチ機能は必要とならず、ディスク装置に対する先行読み出しを実行すればよい。
【００１９】
本発明は、一度に受信した最後のパケットの照合を行うとき、メインメモリ等からのデータの読み込み時間中に、ノード照合処理ができる他のパケットが無い為に発生するパケット処理性能の低下を抑制するパケット処理装置等を提供することを目的とする。
【課題を解決するための手段】
【００２０】
本発明の一実施形態にかかるパケット処理装置は、複数のパケットを順序付けて記憶するパケット記憶手段と、パケットのデータから得られるキーを探索キーとするノードで構成され、末端ノードがパケットの処理を特定するデータを含む木を記憶する木記憶手段と、パケットから探索キーを得て、前記木のノードを辿ってパケットの処理を決定する探索処理を、前記木記憶手段から次ノード情報を読み込む時間を利用して、複数パケットについて、付けられた順序にしたがって開始して並列に実行する木探索手段と、パケットごとに前記探索処理で辿るノード数の予測値を求め、当該予測値の多い順に前記パケット記憶手段内の複数のパケットを順序付けるスケジューリング手段と、を備える。
【００２１】
本発明の一実施形態にかかるパケット処理方法は、複数のパケットを順序付けて記憶し、パケットのデータから得られるキーを探索キーとするノードで構成され、末端ノードがパケットの処理を特定するデータを含む木を木記憶手段に記憶し、パケットから探索キーを得て、前記木のノードを辿ってパケットの処理を決定する探索処理を、前記木記憶手段から次ノード情報を読み込む時間を利用して、複数パケットについて、付けられた順序にしたがって開始して並列に実行する方法であって、パケットごとに前記探索処理で辿るノード数の予測値を求め、当該予測値の多い順に記憶している前記複数のパケットを順序付ける。
【発明の効果】
【００２２】
本発明にかかるパケット処理装置は、一度に受信した最後のパケットの木との照合を行うとき、メインメモリ等からのノードの読み込み時間中に、照合処理ができる他のパケットが無い為に発生する性能の低下を抑制できる。
【図面の簡単な説明】
【００２３】
【図１】図１は、木の構造を例示する。
【図２】図２は、パケットのキーとノードのキーとの照合処理と、ノード情報の読み込み時間の発生シーケンス例（その１）を示す。
【図３】図３は、パケットのキーとノードのキーとの照合処理と、ノード情報の読み込み時間の発生シーケンス例（その２）を示す。
【図４】図４は、第１の実施形態におけるパケット処理装置１０の構成図である。
【図５】図５は、パケットのキーとノードのキーとの照合処理と、ノード情報の読み込み時間の発生シーケンス例（その３）を示す。
【図６】図６は、第１の実施の形態のパケット処理装置１０の動作フローチャートである。
【図７】図７は、第２の実施形態におけるパケット処理装置１０の構成図である。
【図８】図８は、第２の実施の形態のパケット処理装置１０の動作フローチャートである。
【図９】図９は、第３の実施形態におけるパケット処理装置１０の構成図である。
【発明を実施するための形態】
【００２４】
＜第１の実施の形態＞
[構成の説明]
図４は、本発明の第１の実施形態におけるパケット処理装置１０の構成図である。本実施形態におけるパケット処理装置１０、１つ以上の通信部１１、パケット受信部１２、パケット記憶部１３、木記憶部１４、スケジューリング部１５、予測表記憶部１６、木探索部１７、及びパケット処理部１８と、を備える。
【００２５】
通信部１１は、パケット受信部１２とパケット処理部１８とに接続される。パケット受信部１２は、通信部１１とパケット記憶部１３に接続される。パケット記憶部１３は、パケット受信部１２とスケジューリング部１５と木探索部１７とパケット処理部１８とに接続される。
【００２６】
木記憶部１４は、スケジューリング部１５と木探索部１７とに接続される。スケジューリング部１５は、パケット記憶部１３と木記憶部１４と予測表記憶部１６と木探索部１７と接続される。木探索部１７は、木記憶部１４とスケジューリング部１５とパケット記憶部１３とパケット処理部１８と接続される。予測表記憶部１６は、スケジューリング部１５と接続される。パケット処理部１８は、通信部１１とパケット記憶部１３と木探索部１７とに接続される。
【００２７】
通信部１１は、図示しない他の装置から通信パケットを受信する。通信部１１は、例えばEthernet（登録商標）通信制御装置である。
【００２８】
パケット受信部１２は、通信部１１から一度に複数のパケットを受信し、該パケットをパケット記憶部１３に記憶させる。パケット記憶部１３は、０個以上のパケットを記憶する。
【００２９】
木記憶部１４は、パケットの宛先／送信元アドレス、ペイロード等から求められるキーを探索キーとする木を保持する。この木の葉ノードには、パケットに適用されるべき処理を特定する情報、例えば処理内容または処理プログラム名、が記憶されている。木探索部１７は、パケットから求められるキーを用いてこの木を探索して葉ノードに到達し、当該パケットに適用されるべき処理を決定する。パケットの処理内容は、例えば通信部１１へのパケットの出力や、パケットのヘッダの変換や、パケットの削除などである。このような木の探索は、例えば、オープンフローネットワークの拡張マッチングで行われる。
【００３０】
木探索部１７は、パケットの処理を決定する為の木の探索処理で、木のノードを辿りながら、木とパケットの照合を行う。木とパケットの照合は、パケットの宛先アドレス、等から求められるキーを用いて行われる。木とパケットの照合は、パケットのキーとノードに格納されているキーとを照合してリンクを選択し、選択したリンクを辿って次に照合に用いるべきノードを求め、さらにパケットのキーと該次のノードのキーとの照合を繰り返すことで進行する。木とパケットの照合は、パケットのキーとルートノードのキーとの照合で始まり、幾つかの中間ノードを辿って、葉ノードに到達して終了する。
【００３１】
木記憶部１４がメインメモリである場合、木探索部１７は、或るパケットの為の木の探索処理で、次に辿るべきノードの情報がキャッシュメモリに格納されていないと、該ノード情報を対象にプリフェッチ命令を発行して、木記憶部１４からの読み出しを開始する。
【００３２】
木記憶部１４がディスク装置である場合、木探索部１７は、或るパケットの為の木の探索処理で、次に辿るべきノードの情報がメインメモリに格納されていないと、該ノード情報を対象にディスク読み込み命令を発行して、木記憶部１４からの読み出しを開始する。
【００３３】
何れの場合も、読み出し時間中、木探索部１７は、他のパケットの為の木の探索処理を実行する。このようにして、木探索部１７は、複数のパケットの為の木の探索処理を並列して実行する。
【００３４】
スケジューリング部１５は、パケット記憶部１３に記憶されたパケットと予測表記憶部１６を参照し、各パケットと木との照合の回数を予測する。換言すれば、スケジューリング部１５は、パケットの処理を決定する為に実行される木の探索処理で、当該パケットから求められたキーと木のノードが格納するキーとの照合回数を予測する。そして、スケジューリング部１５は、予測された照合回数の多い順にパケットを並べ、その順序をパケット記憶部１３に記憶する。 
予測表記憶部１６は、ハッシュ値に対して照合回数を関連付ける予測表を記憶する。スケジューリング部１５は、パケット記憶部１３に記憶されているパケットから得られるキーの一部からハッシュ値を計算し、該ハッシュ値に関連付けられている照合回数を予測表から検索することで、照合回数を予測する。スケジューリング部１５は、例えば、パケットのヘッダのＭＡＣアドレスや、ＩＰアドレスの上位数バイトをハッシュ値の計算に用いる。
【００３５】
予測表が記憶するハッシュ値と照合回数は、木を作成するときに記憶してもよいし、木探索部１７の探索結果から学習してもよい。木探索部１７の探索結果から学習する場合、
スケジューリング部１５は、木探索部１７からパケット番号と照合回数とを取得して、該パケットのハッシュ値をもとに、予測表に記憶している照合回数を更新する。
【００３６】
木探索部１７は、パケット記憶部１３に記憶された順序で、パケット記憶部１３に記憶されている各パケットの処理を決定する為の木の探索処理を行う。木探索部１７は、パケットのキーを用いて行った木の探索処理の結果、到達した葉ノードに記憶されている処理の特定情報を、該パケットに付加する。
【００３７】
パケット処理部１８は、パケット記憶部１３に記憶されている各パケットに付加されている処理内容に応じて、該パケットを処理する。
【００３８】
図５は、本実施の形態のパケット処理装置１０が実行する処理の順序を、図３と同様に例示する。図５の例では、パケット番号１の照合回数が１、パケット番号２の照合回数が４、パケット番号３の照合回数が３、パケット番号４の照合回数が４である。木の探索処理の対象となるパケットの順序は、２→４→３→１の順となる。
【００３９】
図５の例では、最後に木と照合するパケット１の照合回数が１である。したがって、本実施の形態のパケット処理装置１０は、木記憶部１４からデータを読み込むことによる性能低下を小さくすることができる。なお、図５において、処理装置が有効に動作しない時間は、照合処理１−２の為のノード情報の読み込み時間であり、この時間は長方形に斜線を付して示されている。
【００４０】
通信部１１、パケット受信部１２、スケジューリング部１５、木探索部１７、及び、パケット処理部１８は、論理回路で実現される。通信部１１、パケット受信部１２、スケジューリング部１５、木探索部１７、または、パケット処理部１８は、コンピュータでもあるパケット処理装置１０の図示されないＣＰＵ（Central Processing Unit）が実行するプログラムによって実現されても良い。
【００４１】
パケット記憶部１３、木記憶部１４、および、予測表記憶部１６は、例えばランダムアクセスメモリやキャッシュメモリによって実現される。パケット記憶部１３、木記憶部１４、または、予測表記憶部１６は、ディスク装置などの外部記憶装置で実装されても良い。
【００４２】
[動作の説明]
図６は、本実施の形態のパケット処理装置１０の動作フローチャートである。
【００４３】
まず、パケット受信部１２が、通信部１１からパケットを１つ以上、通常複数、まとめて受信する（ステップＳ１）。次に、パケット受信部１２が、受信したパケットをパケット記憶部１３に記憶する（ステップＳ２）。
【００４４】
スケジューリング部１５が、パケット記憶部１３に記憶された各パケットの一部を用いてハッシュ値を計算し、該ハッシュ値を用いて予測表を検索し、木探索処理の照合回数を予測する（ステップＳ３）。
【００４５】
スケジューリング部１５が、ステップＳ３で予測した照合回数の大きい順にパケットの木探索を行うよう順序付けて（ステップＳ４）、順序をパケット記憶部１３に記憶する（ステップＳ５）。
【００４６】
木探索部１７が、パケット記憶部１３に記憶された順序で、パケットと木を照合する（ステップＳ６）。パケット処理部１８が、木との照合結果をもとにパケットを処理する（ステップＳ７）。
【００４７】
木探索部１７は、ステップＳ６でパケットと木を照合した結果から、パケット番号と照合回数の組を各パケットについて求め、スケジューリング部１５に送信する（ステップＳ８）。スケジューリング部１５は、受信した各パケットについてパケット番号と照合回数をもとに、予測表の値を更新する（Ｓ９）。
【００４８】
[発明の効果]
本実施の形態のパケット処理装置１０は、一度に受信した最後のパケットの木との照合を行うとき、メインメモリ等からのノードの読み込み時間中に、照合処理ができる他のパケットが無い状況の発生頻度を低下させる。その結果、本実施の形態のパケット処理装置１０は、そのような状況に起因して発生するパケット処理性能の低下を抑制することができる。
【００４９】
その理由は、スケジューリング部１５が、各パケットと木の照合における木の照合回数を予測し、木探索部１７が、照合回数の大きいパケット順に木とパケットを照合するからである。
【００５０】
本実施の形態のスケジューリング部１５は、各パケットと木の照合における木の照合回数を適切に予測できる。その理由は、スケジューリング部１５が、パケットから得られるキーの一部からハッシュ値を計算し、予測表記憶部１６に格納されている予測表を照合して照合回数を推定するからである。
【００５１】
木の探索処理は、キーの一部（例えば、上位ビット列）で木の部分木を特定し、キーの残りの部分（例えば、キーの下位ビット列）で、部分木内の葉ノードを特定する処理と捉えることが可能である。そして、木は、その部分木によって深さが異なることが有る。探索が、深い部分木を対象に行われれば照合回数は多く、浅い部分木を対象に行われれば照合回数は少ないと予測される。したがって、予測表が、部分木を特定するキーの一部のハッシュ値と、当該キーの一部により特定される部分木の深さに応じた値と、を関連付けて格納していれば、スケジューリング部１５は、照合回数を適切に予測できる。
【００５２】
木の構造が初めから明確である場合、予測表はシステムパラメータとしてパケット処理装置１０に与えられても良い。木の構造が当初は不明、または運転過程で変化するのであれば、上述したように、予測表に記憶される値は、木探索部１７における探索結果すなわち過去の履歴を反映して設定されるのが有効である。
【００５３】
＜第２の実施形態＞
[構成の説明]
図７は、本発明の第２実施形態におけるパケット処理装置１０の構成図である。本実施形態におけるパケット処理装置１０は、予測表記憶部１６を包含しない。他は、第１の実施形態におけるパケット処理装置１０と同様の構成である。
【００５４】
本実施形態におけるスケジューリング部１５は、パケット記憶部１３の各パケットについて、木を所定の段数だけ探索し、到達したノードをもとに照合回数を予測する。
【００５５】
到達したノードと照合回数の予測値との紐付けは、木を作成・変更するときに行っても良いし、過去の探索履歴によって行っても良い。以下の動作発明は、木の作成・変更時に行う場合についての説明である。
【００５６】
また、本実施形態のスケジューリング部１５は、到達した木の中間ノード、すなわち木探索の途中結果を、各パケットの付加情報としてパケット記憶部１３に記憶しても良い。この場合、木探索部１７は、パケット記憶部１３に記憶されている各パケットについて、パケット記憶部１３に記憶された順序で木との照合を行うとき、該パケットの付加情報として記憶されているノードの照合処理から開始する。これにより、木探索部１７は、スケジューリング部１５が既に実行した照合を省略することが出来る。
【００５７】
[動作の説明]
図８は、本実施の形態のパケット処理装置１０の動作フローチャートである。ステップＳ１１及び１２は、第１の実施形態におけるステップＳ１及びＳ２とそれぞれ同様である。
【００５８】
次に、スケジューリング部１５が、パケット記憶部１３に格納された各パケットについて、所定ノード数だけ木を探索し、到達した中間ノードから照合回数を予測し、該到達したノードの情報を該パケットに付加する（ステップＳ１３）。ここで、スケジューリング部１５は、木を探索して到達した中間ノードに紐付けられている照合回数を予測値として出力する。
【００５９】
ステップＳ１４及びＳ１５は、第１の実施形態におけるステップＳ４及びＳ５とそれぞれ同様である。
【００６０】
木探索部１７が、パケット記憶部１３に記憶された順序で、パケット記憶部１３に記憶されている各パケットと木の照合を、該パケットに付加されているノード情報のノードから行う（ステップＳ１６）。
【００６１】
ステップＳ１７は、第１の実施形態におけるステップＳ７と同様である。
【００６２】
[発明の効果]
本実施の形態のスケジューリング部１５は、各パケットと木の照合における木の照合回数を適切に予測できる。その理由は、スケジューリング部１５が、パケット記憶部１３に格納された各パケットについて、所定ノード数だけ木を探索し、到達した中間ノードから照合回数を予測するからである。
【００６３】
上述したように、木の深さは、木の部分木によって異なる。本実施の形態では、木の所定段数下位の中間ノードをルートとする部分木のルートノードに当該部分木の深さを反映した予測値を紐付けることで、照合回数の予測精度を高めることが可能である。
【００６４】
さらに、木探索部１７が或る部分木を探索する場合に、最終的に特定の葉ノードに到達する確率が高い時は、当該部分木のルートノードに、当該葉ノードまでの照合回数を紐付けることで、照合回数の予測精度を高めることが可能である。
【００６５】
＜第３の実施形態＞
図９は、本発明の第３実施形態におけるパケット処理装置１０の構成図である。本実施形態におけるパケット処理装置１０は、パケット記憶部１３、木記憶部１４、スケジューリング部１５、および、木探索部１７を備える。
【００６６】
パケット記憶部１３は、複数のパケットを順序付けて記憶する。木記憶部１４は、パケットのデータから得られるキーを探索キーとするノードで構成され、末端ノードがパケットの処理を特定するデータを含む木を記憶する。
【００６７】
木探索部１７は、パケットから探索キーを得て、木のノードを辿ってパケットの処理を決定する探索処理を、木記憶手段から次ノード情報を読み込む時間を利用して、複数パケットについて、付けられた順序にしたがって開始して並列に実行する。
【００６８】
スケジューリング部１５は、パケットごとに探索処理で辿るノード数の予測値を求め、当該予測値の多い順にパケット記憶手段内の複数のパケットを順序付ける。
【００６９】
本実施の形態のパケット処理装置１０は、一度に受信した最後のパケットの木との照合を行うとき、メインメモリ等からのノードの読み込み時間中に、照合処理ができる他のパケットが無い状況の発生頻度を低下させる。その結果、本実施の形態のパケット処理装置１０は、そのような状況に起因して発生するパケット処理性能の低下を抑制することができる。
【００７０】
その理由は、スケジューリング部１５が、各パケットと木の照合における木の照合回数を予測し、木探索部１７が、照合回数の大きいパケット順に木とパケットを照合するからである。
【００７１】
以上、実施形態を参照して本願発明を説明したが、本願発明は上記実施形態に限定されものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【符号の説明】
【００７２】
１０    パケット処理装置
１１    通信部
１２    パケット受信部
１３    パケット記憶部
１４    木記憶部
１５    スケジューリング部
１６    予測表記憶部
１７    木探索部
１８    パケット処理部
【図１】
2016100624.tif 000003
【図２】
2016100624.tif 000004
【図３】
2016100624.tif 000005
【図４】
2016100624.tif 000006
【図５】
2016100624.tif 000007
【図６】
2016100624.tif 000008
【図７】
2016100624.tif 000009
【図８】
2016100624.tif 000010
【図９】
2016100624.tif 000011