(57)【特許請求の範囲】
【請求項１】
データブロックに対して所定の処理を行う複数のデータ処理部のうちから、前記データブロックに基づく第１の識別情報による第１のデータブロックグループの振分先を決定し、
振り分けられた処理量が第１の閾値を超えるデータ処理部がある場合に、該データ処理部を振分先とする第１のデータブロックグループを、前記データブロックに基づく第２の識別情報による複数の第２のデータブロックグループに細分化し、前記複数の第２のデータブロックグループのそれぞれの振分先を前記複数のデータ処理部のうちから決定する、プロセッサ、
を備え、
前記プロセッサは、
前記第１の識別情報を、前記データブロックが属するフローのフロー情報から取得し、
前記第２の識別情報を、前記フロー情報のうち前記第１の識別情報とは異なる情報から取得する、
情報処理装置。
【請求項２】
データブロックに対して所定の処理を行う複数のデータ処理部のうちから、前記データブロックに基づく第１の識別情報による第１のデータブロックグループの振分先を決定し、
振り分けられた処理量が第１の閾値を超えるデータ処理部がある場合に、該データ処理部を振分先とする第１のデータブロックグループを、前記データブロックに基づく第２の識別情報による複数の第２のデータブロックグループに細分化し、前記複数の第２のデータブロックグループのそれぞれの振分先を前記複数のデータ処理部のうちから決定する、プロセッサ、
を備え、
前記プロセッサは、
前記データブロックが属するフローのフロー情報からハッシュ値を算出し、
前記第１の識別情報として、前記ハッシュ値のうちのＮ桁（Ｎ:正の整数）の値を取得
し、
前記第２の識別情報として、前記ハッシュ値のうち前記Ｎ桁の値を含むＭ桁（Ｎ＜Ｍ≦
ハッシュ値全桁）の値を取得する、
情報処理装置。
【請求項３】
前記プロセッサは、
少なくとも１つの第１のデータブロックグループから分割された各第２のデータブロックグループに含まれるフローの偏りσ１と、前記複数のデータ処理部のそれぞれに振り分けられたフローの偏りσ２と、に基づいて、新たな第１のデータブロックグループの第２のデータブロックグループへの分割に用いられる前記第２の識別情報として取得される前記ハッシュ値の前記Ｍ桁を決定する、
請求項２に記載の情報処理装置。
【請求項４】
前記プロセッサは、
前記偏りσ１を、前記少なくとも１つの第１のデータブロックグループから分割された各第２のデータブロックグループに含まれる前記フローの数の標準偏差に基づいて取得し、
前記偏りσ２を、前記複数のデータ処理部のそれぞれに振り分けられたフロー数の標準偏差に基づいて取得する、
請求項３に記載の情報処理装置。
【請求項５】
前記プロセッサは、
前記Ｍの初期値と、前記偏りσ１に重み係数ｍ１を乗じた値と、前記偏りσ２に重み係数ｍ２を乗じた値と、を加算して前記Ｍ桁を決定する、
請求項４に記載の情報処理装置。
【請求項６】
前記プロセッサは、
前記複数のデータ処理部のそれぞれに振り分けられたフロー数の最大値が第３の閾値以上であり、且つ、前記複数のデータ処理部のそれぞれに振り分けられたフロー数の標準偏差が第４の閾値以上である場合に、前記偏りσ２を該標準偏差の正の値とし、
前記複数のデータ処理部のそれぞれに振り分けられたフロー数の最大値が前記第３の閾値未満であり、且つ、前記複数のデータ処理部のそれぞれに振り分けられたフロー数の標準偏差が前記第４の閾値未満である場合に、前記偏りσ２を該標準偏差の負の値とし、
前記複数のデータ処理部のそれぞれに振り分けられたフロー数の最大値が前記第３の閾値以上であり、且つ、前記複数のデータ処理部のそれぞれに振り分けられたフロー数の標準偏差が前記第４の閾値未満である場合、及び、前記複数のデータ処理部のそれぞれに振り分けられたフロー数の最大値が前記第３の閾値未満であり、且つ、前記複数のデータ処理部のそれぞれに振り分けられたフロー数の標準偏差が前記第４の閾値以上である場合に、前記偏りσ２を０とする、
請求項５に記載の情報処理装置。
【請求項７】
前記プロセッサは、
前記複数の第２のデータブロックグループの総処理量が、第２の閾値以下になり、且つ、前記複数のデータ処理部のうちのいずれか一つで処理可能な量になった場合に、前記第２のデータブロックグループを集約して前記第１のデータブロックグループに戻す、
請求項１から６のいずれか一項に記載の情報処理装置。
【請求項８】
前記プロセッサは、
前記第１の識別情報と前記第１のデータブロックグループの振分先となるデータ処理部との対応付けを第１の記憶部に格納し、
前記第１のデータブロックグループから前記複数の第２のデータブロックグループを作成する場合に、前記第２の識別情報と前記複数の第２のデータブロックグループのそれぞ
れの振分先となるデータ処理部との対応付けを、前記第１の記憶部とは異なる第２の記憶部に格納する、
請求項１から７のいずれか一項に記載の情報処理装置。
【請求項９】
コンピュータが、
データブロックに対して所定の処理を行う複数のデータ処理部のうちから、前記データブロックに基づく第１の識別情報による第１のデータブロックグループの振分先を決定し、
振り分けられた処理量が第１の閾値を超えるデータ処理部がある場合に、該データ処理部を振分先とする第１のデータブロックグループを、前記データブロックに基づく第２の識別情報による複数の第２のデータブロックグループに細分化し、前記複数の第２のデータブロックグループのそれぞれの振分先を前記複数のデータ処理部のうちから決定する、方法であって、
前記第１の識別情報を、前記データブロックが属するフローのフロー情報から取得し、
前記第２の識別情報を、前記フロー情報のうち前記第１の識別情報とは異なる情報から取得する、
情報処理方法。
【請求項１０】
コンピュータが、
データブロックに対して所定の処理を行う複数のデータ処理部のうちから、前記データブロックに基づく第１の識別情報による第１のデータブロックグループの振分先を決定し、
振り分けられた処理量が第１の閾値を超えるデータ処理部がある場合に、該データ処理部を振分先とする第１のデータブロックグループを、前記データブロックに基づく第２の識別情報による複数の第２のデータブロックグループに細分化し、前記複数の第２のデータブロックグループのそれぞれの振分先を前記複数のデータ処理部のうちから決定する、方法であって、
前記データブロックが属するフローのフロー情報からハッシュ値を算出し、
前記第１の識別情報として、前記ハッシュ値のうちのＮ桁（Ｎ:正の整数）の値を取得
し、
前記第２の識別情報として、前記ハッシュ値のうち前記Ｎ桁の値を含むＭ桁（Ｎ＜Ｍ≦ハッシュ値全桁）の値を取得する、
情報処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、処理の分散を行う情報処理装置及び情報処理方法に関する。
【背景技術】
【０００２】
例えば、音声パケットや映像パケット等のマルチメディアを取り扱うネットワークでは、遅延を少なくするため、複数の処理装置にフロー単位で処理が分散される。フロー単位で処理を複数の処理装置に分散させる技術として、例えば、以下の２つがある。
【０００３】
例えば、技術１では、入力パケットの宛先アドレス、送信元アドレス、送信元ポート番号、宛先ポート番号等から得られるハッシュ値が同一の入力パケットを同一のグループに分類し、各グループのフローをグループごとに異なる経路へ出力する（例えば、特許文献１）。技術１では、各グループの単位使用帯域幅に基づき各グループの重み係数が調節され、各グループの重み係数の比となるようにハッシュ値の値域を分割してグループに対応付けることによって、経路間のトラフィックの配分が動的に最適化される。
【０００４】
また、例えば、技術２では、クライアントのＩＰアドレスに基づくハッシュ値の特定のビット分を用いて、該クライアントの割り当て先のマルチキャストグループを計算する（例えば、特許文献２）。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００３−１６３６８７号公報
【特許文献２】特開２００９−２１８９８８号公報
【特許文献３】特開平１１−８５７７１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、従来の技術には、以下のような問題があった。技術１では、例えば、１つのハッシュ値にフローが集中し、該ハッシュ値の振分先となる経路の許容処理量を超える場合には、該ハッシュ値のフローを受け入れる振分先を選択する手段がなかった。
【０００７】
技術２においては、グループに所属するクライアント数が増えた場合に、該グループを再分割することが開示されている。しかしながら、技術２では、以下のような問題がある。技術２では、グループの分割数は、ハッシュ値のビット数で決められており、ビット数毎に対応する表が準備されている。グループの分割は、ビット数の表に基づいて行われる。例えば、２ビット（４分割）で分割していた場合に、３ビット（８分割）で再分割する際には、２ビットの表から３ビットの表に置き換えられる。すなわち、技術２においては、グループの再分割の際に、システム全体でグループが再編され、例えば、グループを記録するメモリの書き換え等が行われる。
【０００８】
パケットの追い越しや共有メモリアクセス時の排他ロックが発生することを防ぐため、原則、同一のフローは同一の処理装置で処理される。しかしながら、グループ再編のメモリ書き換えによって、通信中の全フローの処理装置が更新されて、グループ再編の前後で処理装置が変わってしまう可能性がある。これによって、例えば、通信中のフローではパケットロスや遅延が発生する可能性がある。そのため、技術２では、グループの再分割の影響が、システム全体に及ぶ可能性がある。
【０００９】
本発明の一態様は、複数の処理装置に処理を分散させるシステムにおいて、所定の処理装置への処理の集中をより簡易且つ安全に抑制するための情報処理装置及び情報処理方法を提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明の態様の一つは、データブロックに対して所定の処理を行う複数のデータ処理部のうちから、データブロックに基づく第１の識別情報による第１のデータブロックグループの振分先を決定し、振り分けられた処理量が第１の閾値を超えるデータ処理部がある場合に、該データ処理部を振分先とする第１のデータブロックグループを、データブロックに基づく第２の識別情報による複数の第２のデータブロックグループに細分化し、該複数の第２のデータブロックグループのそれぞれの振分先を複数のデータ処理部のうちから決定する、プロセッサを備える情報処理装置である。
【００１１】
本発明の他の態様の一つは、情報処理装置が上述の処理を実行する情報処理方法である。また、本発明の他の態様は、コンピュータを上述した情報処理装置として機能させるプログラム、及び当該プログラムを記録したコンピュータ読み取り可能な非一時的な記録媒体を含むことができる。コンピュータ等が読み取り可能な非一時的な記録媒体には、データやプログラム等の情報を電気的、磁気的、光学的、機械的、または化学的作用によって蓄積し、コンピュータ等から読み取ることができる記録媒体をいう。
【発明の効果】
【００１２】
開示の情報処理装置及び情報処理方法によれば、複数の処理装置に処理を分散させるシステムにおいて、所定の処理装置への処理の集中をより簡易且つ安全に抑制することができる。
【図面の簡単な説明】
【００１３】
【図１】第１実施形態に係る処理の振り分けの一例を示す図である。
【図２】第１実施形態に係る分散処理システムの構成の一例を示す図である。
【図３】パケット処理装置のハードウェア構成の一例を示す図である。
【図４】第１実施形態に係るパケット処理装置の機能構成の一例を示す図である。
【図５】パケットの構成の一例を示す図である。
【図６】振分テーブルの一例を示す図である。
【図７】拡張振分テーブルの一例を示す図である。
【図８】処理コア管理テーブルの一例を示す図である。
【図９】全桁ハッシュ値管理テーブルの一例を示す図である。
【図１０】いずれのグループも細分化されていない状態のテーブル構成の一例を示す図である。
【図１１】グループの細分化が発生している状態のテーブル構成の一例を示す図である。
【図１２Ａ】フロー登録時の振分管理コアによる処理のフローチャートの一例である。
【図１２Ｂ】フロー登録時の振分管理コアによる処理のフローチャートの一例である。
【図１２Ｃ】フロー登録時の振分管理コアによる処理のフローチャートの一例である。
【図１３】図１２ＡのＯＰ１０のグループ細分化処理のフローチャートの一例である。
【図１４Ａ】フロー削除時の振分管理コアによる処理のフローチャートの一例である。
【図１４Ｂ】フロー削除時の振分管理コアによる処理のフローチャートの一例である。
【図１４Ｃ】フロー削除時の振分管理コアによる処理のフローチャートの一例である。
【図１４Ｄ】フロー削除時の振分管理コアによる処理のフローチャートの一例である。
【図１５】各処理コアに登録されているフロー数と、フローグループの分割数との関係の一例を示す図である。
【図１６】ハッシュ拡張幅の算出処理のフローチャートの一例である。
【図１７】偏りσ１の算出処理のフローチャートの一例である。
【図１８】偏りσ２の算出処理のフローチャートの一例である。
【発明を実施するための形態】
【００１４】
以下、図面に基づいて、本発明の実施の形態を説明する。以下の実施形態の構成は例示であり、本発明は実施形態の構成に限定されない。
【００１５】
＜第１実施形態＞
図１は、第１実施形態に係る処理の振り分けの一例を示す図である。第１実施形態では、情報処理装置は、データブロックの処理を行う処理コアを複数有するＣＰＵ（Central Processing Unit）を備える。情報処理装置は、データブロックに含まれる情報から算出
されるハッシュ値によってデータブロックをグループ化し、グループごとに振分先の処理コアを決定する。例えば、データブロックは、２進数のハッシュ値の上位Ｎ桁（Ｎ：正の整数、Ｎ＜ハッシュ値の全桁数）の値でグループ化される。
【００１６】
例えば、図１中の処理コア＃１に振り分けられている処理量が処理コア＃１の処理性能の上限を超過した場合に、情報処理装置は、処理コア＃１に振り分けられている上位Ｎ桁ハッシュ値Ａのグループを、ハッシュ値の上位Ｍ桁（Ｍ：正の整数、Ｎ＜Ｍ≦ハッシュ値の全桁数）でさらに細分化する。情報処理装置は、細分化によって作成された、上位Ｍ桁ハッシュ値ＡＡ、ＡＢ、ＡＣ、ＡＤのグループを、それぞれ、処理コア＃１〜＃３に割り当てる。
【００１７】
これによって、上位Ｎ桁ハッシュ値Ａのグループの振分先の処理コア＃１の処理量が処理性能の上限を超過した場合でも、上位Ｎ桁ハッシュ値Ａのグループの処理は処理コア＃１〜＃３のいずれかに振り分けられる。また、上位Ｎ桁ハッシュ値Ａのグループ以外のグループでは、グループの細分化は発生せず、通信中の全フローの更新は行われずに継続して処理が行われる。そのため、グループの細分化による影響を上位Ｎ桁ハッシュ値Ａのグループに含まれるフローに、局所的に抑えることができる。また、ハッシュ値の再計算等もなく細分化することが可能なため、簡易な処理でグループを細分化することができる。上位Ｎ桁ハッシュ値は、「第１の識別情報」の一例である。上位Ｍ桁ハッシュ値は、「第２の識別情報」の一例である。
【００１８】
＜システム構成＞
図２は、第１実施形態に係る分散処理システム５００の構成の一例を示す図である。第１実施形態では、ＶｏＩＰ（Voice over IP(Internet Protocol)）やＶｏＬＴＥ(Voice over LTE(Long Term Evolution))など、音声パケットを取り扱うシステムが想定される。
分散処理システム５００は、ゲートウェイ装置１００、複数の音声端末３を含む。
【００１９】
ゲートウェイ装置１００は、例えば、キャリアネットワーク内の装置である。ゲートウェイ装置１００は、パケット処理装置１と、ＳＩＰ（Session Initiation Protocol）サ
ーバ２とを含む。パケット処理装置１とＳＩＰサーバ２とは、例えば、それぞれ、ゲートウェイ装置５００を形成する筺体のスロットに挿入されるユニットカードである。ＳＩＰ
サーバ２は、音声端末３間のセッションの制御パケットを処理し、パケット処理装置１は、音声端末３間の音声パケットを処理する。
【００２０】
ＶｏＩＰなどでは、まず、ＳＩＰサーバ２と音声端末３との間で通話の準備のための制御パケット（非音声パケット）がやり取りされ、音声端末３間で通話の準備が完了すると、パケット処理装置１によってユーザパケット（音声パケット）の中継が開始され、通話が開始される。したがって、ＳＩＰサーバ２は、パケット処理装置１に音声パケットが流れる前に、該音声パケットのフローの情報を取得することができる。そのため、ＳＩＰサーバ２は、パケット処理装置１に音声パケットが届く前に、該音声パケットのフローの情報をＡＰＩ（Application Programming Interface）を用いてパケット処理装置１に登録
する。ＳＩＰサーバ２は、「管理装置」の一例である。
【００２１】
パケット処理装置１は、複数の処理コアを有するＣＰＵを備えており、ＳＩＰサーバ２からＡＰＩを通じてフローが登録されると、該フローのハッシュ値を算出し、ハッシュ値に基づいて振分先の処理コアを決定する。該フローの音声パケットが到着すると、パケット処理装置１は、振分先の処理コアに振り分け、所定の処理を行い、音声パケットを出力する。
【００２２】
＜装置構成＞
図３は、パケット処理装置１のハードウェア構成の一例を示す図である。パケット処理装置１は、ＣＰＵ（Central Processing Unit）１０１、主記憶装置１０２、補助記憶装
置１０５、ネットワークインタフェース１０７を備え、これらはバス１０９によって電気的に接続される。
【００２３】
主記憶装置１０２は、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）を含む。ＲＡＭは、例えば、ＤＲＡＭ（Dynamic RAM）、ＳＲＡＭ（Static RAM）、ＳＤ
ＲＡＭ（Synchronous  DRAM）、のような半導体メモリである。ＲＯＭには、オペレーテ
ィングシステム（ＯＳ）、フロー振分先決定プログラム、パケット振分プログラム、その他様々なプログラムが保持される。
【００２４】
フロー振分先決定プログラムは、フローの振分先の処理コアを決定するためのプログラムである。パケット振分プログラムは、パケットを該当フローの振分先の処理コアに振り分けるためのプログラムである。
【００２５】
主記憶装置１０２のＲＡＭは、ＣＰＵ  １０１に、ＲＯＭに格納されているプログラムをロードする記憶領域および作業領域を提供したり、バッファとして用いられたりする。
【００２６】
補助記憶装置１０５は、例えば、各プログラムの実行に際してＣＰＵ  １０１が使用するデータを格納する。補助記憶装置１０５は、例えば、ＥＰＲＯＭ（Erasable Programmable ROM）、又はハードディスクドライブ（Hard Disk Drive）等の不揮発性の記憶媒体である。主記憶装置１０２のＲＯＭに格納されるプログラムは、補助記憶装置１０５に格納されてもよい。
【００２７】
ＣＰＵ  １０１は、主記憶装置１０２のＲＯＭに保持されたＯＳやプログラムをＲＡＭにロードして実行することによって、様々な処理を実行する。ＣＰＵ  １０１は、複数のコアを有する。
【００２８】
ネットワークインタフェース１０７は、例えば、光ケーブル、ＬＡＮ（Local Area Network）ケーブル等の有線のネットワーク回線のケーブルを接続する回路及びポートである。パケット処理装置１は、複数のネットワークインタフェース１０７を有するが、図３で
は、便宜上、１つのネットワークインタフェース１０７が示されている。例えば、パケット処理装置１は、ネットワークインタフェース１０７としての光ケーブルを接続する回路及びポートを通じて、キャリアネットワークと接続する。例えば、パケット処理装置１は、ネットワークインタフェース１０７としてのＮＩＣ（Network Interface Card）を通じて、ＬＡＮに接続し、ＳＩＰサーバ２と通信を行う。
【００２９】
なお、図３に示されるパケット処理装置１のハードウェア構成は、一例であり、上記に限られず、実施の形態に応じて、適宜、構成要素の省略や置換、追加が可能である。例えば、パケット処理装置１は、補助記憶装置１０５を備えていなくてもよい。また、例えば、パケット処理装置１は、可搬記録媒体駆動装置を備え、ＳＤカード等の可搬記録媒体を補助記憶装置の一つとして使用してもよい。
【００３０】
なお、ＳＩＰサーバ２のハードウェア構成はパケット処理装置１とほぼ同様である。すなわち、ＳＩＰサーバ２は、ＣＰＵ、主記憶装置、補助記憶装置、ネットワークインタフェースを備える。各ハードウェア構成要素については、概要はパケット処理装置１と同様であり、説明を省略する。
【００３１】
図４は、第１実施形態に係るパケット処理装置１の機能構成の一例を示す図である。パケット処理装置１は、機能構成として、振分管理コア１１、振分コア１２、処理コア＃１〜＃Ｘ（Ｘ：正の整数）を有する。
【００３２】
振分管理コア１１は、ＣＰＵ  １０１が有する複数のコアのうち、フロー振分先決定プログラムを実行し、フローの振分先となる処理コアを決定するコアである。
【００３３】
振分コア１２は、ＣＰＵ  １０１が有する複数のコアのうち、パケット振分プログラムを実行し、ユーザパケットを振分管理コア１１によって決定された振分先の処理コアに振り分けるコアである。振分コア１２は、「振分部」の一例である。
【００３４】
処理コア＃１〜＃Ｘは、ＣＰＵ  １０１が有する複数のコアのうち、パケット処理に係るプログラムを実行し、ユーザパケットを処理するコアである。処理コアが行うパケット処理の一例には、パケット転送、ＮＡＴ（Network Address Translation）、帯域制御等
がある。処理コアは、「データ処理部」の一例である。
【００３５】
図５は、パケットの構成の一例を示す図である。第１実施形態では、音声パケットを取り扱うシステムが想定されているので、図５には、ＵＤＰ（User Datagram Protocol）及びＲＴＰ（Real-time Transport Protocol）のパケットが示されている。パケットは、「データブロック」の一例である。
【００３６】
ＳＩＰサーバ２は、制御パケットから、例えば、パケットのＩＰヘッダ内の宛先ＩＰアドレス、送信元ＩＰアドレス、及びプロトコルタイプ、ＵＤＰヘッダ内の宛先ポート番号及び送信元ポート番号を含むフロー情報を取得する。ＳＩＰサーバ２は、ＡＰＩを通じて、パケット処理装置１に通知する。以降、ＳＩＰサーバ２からフロー情報が通知されることは、フローの登録とも称される。
【００３７】
第１実施形態では、宛先ＩＰアドレス、送信元ＩＰアドレス、プロトコルタイプ、宛先ポート番号、及び送信元ポート番号が一致するパケット群をフローと定義する。ただし、フローの定義はこれに限定されない。
【００３８】
パケット処理装置１の振分管理コア１１は、ＳＩＰサーバ２からフロー情報が入力されると、フロー情報に含まれる宛先ＩＰアドレス、送信元ＩＰアドレス、プロトコルタイプ
、宛先ポート番号、及び送信元ポート番号からハッシュ値を算出する。ハッシュ値は、例えば、排他的論理和や、素数による除算等によって算出される。ハッシュ値は、例えば、４〜３２桁の２進数の数列で算出される。振分管理コア１１は、上位Ｎ桁ハッシュ値に基づいて、フローの振分先の処理コアを決定する。すなわち、上位Ｎ桁ハッシュ値が共通するフローは、同じグループに分類される。
【００３９】
処理コア＃１〜＃Ｘには、それぞれ、処理可能なフロー数に上限がある。処理可能なフロー数を、上限フロー数と称する。振分管理コア１１は、上限フロー数を超える処理コアが存在する場合には、該処理コアに振り分けられている上位Ｎ桁ハッシュ値が共通するフローのグループの一つを、上位Ｍ桁ハッシュ値（Ｎ＜Ｍ）でさらに細分化する。振分管理コア１１は、細分化によって作成された上位Ｍ桁ハッシュ値が共通するグループの振分先の処理コアを決定する。振分管理コア１１は、「情報処理装置」の一例である。
【００４０】
振分管理コア１１は、データベース１４を有する。データベース１４は、例えば、主記憶装置１０２のＲＡＭの記憶領域に作成される。データベース１０４には、振分テーブル、拡張振分テーブル、処理コア管理テーブル、全桁ハッシュ値管理テーブルが保持される。
【００４１】
図６は、振分テーブルの一例を示す図である。振分テーブルは、ハッシュ値の上位Ｎ桁が共通するフローのグループの振分先の処理コアを保持するテーブルである。振分テーブルのエントリには、Ｎ桁ハッシュ値、振分先処理コア、フロー数、集約閾値の項目が含まれる。
【００４２】
「Ｎ桁ハッシュ値」は、ハッシュ値の上位Ｎ桁の値が格納される。振分テーブルのエントリは、初期状態で、２＾Ｎ個分用意される。各エントリの「Ｎ桁ハッシュ値」には、初期状態で、Ｎ桁の２進数の取り得るすべての値が格納される。エントリは、例えば、上位Ｎ桁ハッシュ値の昇順で格納されている。
【００４３】
「振分先処理コア」は、振分先の情報が格納される。初期状態では、「振分先処理コア」は空（ＮＵＬＬ）である。「振分先処理コア」には、該当エントリの「Ｎ桁ハッシュ値」のグループのフローが登録された場合に、振分先の処理コアの識別番号が格納される。振分先の処理コアは、上限フロー数に達していない処理コアの中から、例えば、ラウンドロビン方式で選択される。該当エントリの「Ｎ桁ハッシュ値」のグループが細分化されている場合には、「振分先処理コア」には、細分化されてできたグループの振分先が格納される拡張振分テーブルへのポインタが格納される。拡張振分テーブルの詳細は、後述される。拡張振分テーブルのポインタは、例えば、拡張振分テーブルの格納場所を示すアドレスである。
【００４４】
「フロー数」は、該当エントリの「Ｎ桁ハッシュ値」のフロー数が格納される。初期状態では、「フロー数」は空（ＮＵＬＬ）である。「振分先処理コア」、「フロー数」は、該当の上位Ｎ桁ハッシュ値のフローが登録された場合に、振分管理コア１１によって更新される。
【００４５】
「集約閾値」は、該当の上位Ｎ桁ハッシュ値のグループが上位Ｍ桁ハッシュ値で細分化されている場合に、細分化されてできたグループの集約の判定に用いられる閾値である。「集約閾値」には、閾値として用いられるフロー数が格納される。上位Ｎ桁ハッシュ値のグループの登録フロー数が該当エントリの「集約閾値」のフロー数よりも少なくなった場合に、細分化されていたグループが集約される。
【００４６】
「集約閾値」の値は、該当エントリの上位Ｎ桁ハッシュ値のグループが細分化される際
に、振分管理コア１１によって登録される。また、「集約閾値」の値は、細分化されていたグループが集約された場合に、振分管理コア１１によって削除される。「集約閾値」の値は、例えば、予めシステムで一律に決められていてもよいし、フローの種類ごとに決められていてもよい。
【００４７】
なお、図６に示される振分テーブルは一例であって、これに限定されない。例えば、振分テーブルは、初期状態で空であって、新たな上位Ｎ桁のハッシュ値のフローが登録される毎に、新たにエントリが追加されるようにしてもよい。振分テーブルは、「第１の記憶部」の一例である。また、上位Ｎ桁ハッシュ値が共通するフローのグループは、「第１のデータブロックグループ」の一例である。
【００４８】
振分コア１２は、ユーザパケットを振り分ける際には、該ユーザパケットからハッシュ値を算出し、振分管理コア１１のデータベース１４内の振分テーブル内の上位Ｎ桁ハッシュ値が該当するエントリの「振分先処理コア」の値を取得する。「振分先処理コア」の値が処理コアの識別番号である場合には、振分コア１２は、該識別番号の処理コアにユーザパケットを振り分ける。「振分先処理コア」の値が拡張振分テーブルへのポインタである場合には、振分コア１２は、ポインタが示す拡張振分テーブルを参照する。「振分先処理コア」の値が空の場合には、振分コア１２は、該当のユーザパケットを廃棄する。ＳＩＰサーバ２によって登録されていないフローのパケットは、パスがないからである。
【００４９】
図７は、拡張振分テーブルの一例を示す図である。拡張振分テーブルは、上位Ｎ桁ハッシュ値のグループが細分化された場合に、該グループについて作成される。拡張振分テーブルは、細分化されてできたグループの振分先を保持するテーブルである。拡張振分テーブルのエントリの項目は、Ｍ桁ハッシュ値、振分先処理コア、フロー数、集約閾値である。
【００５０】
「Ｍ桁ハッシュ値」には、上位Ｍ桁のハッシュ値が２進数表記で格納される。「Ｍ桁ハッシュ値」の上位Ｎ桁の値は、細分化対象グループの上位Ｎ桁ハッシュ値と同じ値である。拡張振分テーブルには、初期状態で、２＾（Ｍ−Ｎ）個のエントリ分のメモリ容量が確保されている。また、拡張振分テーブルの各エントリの「Ｍ桁ハッシュ値」には、それぞれ、上位Ｎ桁が共通し、上位Ｎ＋１桁から上位Ｍ桁までのビットが異なる上位Ｍ桁のハッシュ値が格納される。
【００５１】
「振分先処理コア」、「フロー数」、「集約閾値」については、振分テーブルと同様であるため、説明を省略する。なお、振分テーブルは、１台のパケット処理装置１につき１つ存在する。拡張振分テーブルは、細分化が発生しているグループ分存在する。また、上位Ｍ桁ハッシュ値で細分化されてできたグループが細分化対象となる場合もあり、その場合には、拡張振分テーブル内の「振分先処理コア」には上位Ｌ桁ハッシュ値（Ｍ＜Ｌ）の拡張振分テーブルへのポインタが格納される。拡張振分テーブルは、「第２の記憶部」の一例である。上位Ｍ桁が共通するフローのグループは、「第２のデータブロックグループ」の一例である。
【００５２】
振分コア１２は、ユーザパケットの上位Ｎ桁ハッシュ値に該当する振分テーブルのエントリの「振分先処理コア」が、拡張振分テーブルへのポインタである場合には、該ポインタが示す拡張振分テーブルを参照する。振分コア１２は、ユーザパケットの上位Ｍ桁ハッシュ値に該当する拡張振分テーブルのエントリの「振分先処理コア」の値を取得する。「振分先処理コア」の値が処理コアの識別番号である場合には、振分コア１２は、該識別番号の処理コアにユーザパケットを振り分ける。「振分先処理コア」の値がさらに拡張振分テーブルへのポインタである場合には、振分コア１２は、ポインタが示す拡張振分テーブルを参照する。
【００５３】
図８は、処理コア管理テーブルの一例を示す図である。処理コア管理テーブルは、各処理コアに割り振られるフロー数を管理するためのテーブルである。処理コア管理テーブルは、振分管理コア１１のデータベースに格納される。処理コア管理テーブルは、１台のパケット処理装置１につき１つ用意される。
【００５４】
処理コア管理テーブルのエントリには、処理コア、フロー数、連結リスト先頭へのポインタ、の項目が含まれる。「処理コア」には、処理コアとして動作するコアの識別番号が格納される。「フロー数」には、該当エントリの処理コアに割り振られているフロー数が格納される。
【００５５】
「連結リスト先頭へのポインタ」には、連結リストの先頭グループの格納場所のアドレスが格納される。連結リストは、該当の処理コアを振分先とする、ハッシュ値によるフローグループのリストである。連結リストには、グループの識別情報（上位Ｘ桁のハッシュ値）とフロー数とが含まれる。連結リストは、例えば、フロー数の降順でグループが並べられている。なお、図８に示される処理コア管理テーブルの構成は、一例であり、これに限定されない。
【００５６】
図９は、全桁ハッシュ値管理テーブルの一例を示す図である。全桁ハッシュ値管理テーブルは、パケット処理装置１が実際に処理を取り扱うフローの全桁ハッシュ値と、各フローのフロー数とを管理するテーブルである。全桁ハッシュ値管理テーブルは、グループ細分化の際に、ハッシュ値の上位Ｎ＋１桁以降の内訳を参照するために用いられる。全桁ハッシュ値管理テーブルのエントリには、全桁ハッシュ値、フロー数、の項目がある。
【００５７】
「全桁ハッシュ値」には、パケット処理装置１が処理を取り扱うフローの全桁のハッシュ値が格納される。「フロー数」には、該当の全桁ハッシュ値のフロー数が格納される。
【００５８】
全桁ハッシュ値管理テーブルの初期状態は、空であり、新たなハッシュ値のフローがＳＩＰサーバ２から通知されると、振分管理コア１１によってエントリが追加される。また、全桁ハッシュ値管理テーブルのエントリは、該当のハッシュ値のフロー数が０になると、振分管理コア１１によって削除される。
【００５９】
＜グループ細分化の一例＞
図１０は、いずれのグループも細分化されていない状態のテーブル構成の一例を示す図である。図１０に示される例では、パケット処理装置１は、処理コア＃１、＃２、＃３を有すると想定する。また、処理コア＃１、＃２、＃３の処理可能なフロー数の上限は、それぞれ、１０００であるとする。なお、各処理コアの処理可能な上限フロー数は、パケット処理装置１において定義されており、各処理コアが認識しているものとする。また、図１０では、Ｎ桁＝８桁と想定されている。
【００６０】
図１０に示される例では、処理コア＃１には、上位Ｎ桁ハッシュ値が「０ｂ００００００００」、「０ｂ００００００１１」、「０ｂ１１１１１１１０」のグループが振り分けられていることが、振分テーブルによって示される。また、処理コア＃１に振り分けられているフローの総数は上限フロー数の１０００であることが、処理コア管理テーブルによって示される。すなわち、処理コア＃１は、これ以上フローを処理することができない状態である。図１０に示される例のように、例えば、一つの処理コアの登録フロー数が処理可能な上限フロー数に達した場合に、グループの細分化が行われる。
【００６１】
図１１は、グループの細分化が発生している状態のテーブル構成の一例を示す図である。図１１に示される例は、図１０の状態から処理コア＃１を振分先とするグループの細分
化が発生した場合の例である。
【００６２】
例えば、細分化対象グループには、処理コア＃１を振分先とするグループのうち最多のフロー数のグループが選択される。図１１では、処理コア＃１を振分先とするグループのうち、最多のフロー数５００を有する上位Ｎ桁ハッシュ値「０ｂ００００００１１」のグループが細分化対象となる。
【００６３】
図１１では、上位Ｎ桁ハッシュ値「０ｂ００００００１１」の拡張振分テーブルが示される。図１１に示される例では、Ｍ桁＝１２桁が想定されている。上位Ｎ桁が「０ｂ００００００１１」である上位Ｍ桁のハッシュ値のフローのグループは、全桁ハッシュ値管理テーブルより、「０ｂ００００００１１００００」、「０ｂ００００００１１０００１」、「０ｂ００００００１１１１１０」であることが取得される。また、それぞれ、フロー数、２００、１００、２００である。
【００６４】
細分化によってできた上位Ｍ桁ハッシュ値のグループの振分先は、例えば、登録フロー数が上限フロー数に達していない処理コアから循環的に選択される。上位Ｍ桁のハッシュ値「０ｂ００００００１１００００」、「０ｂ００００００１１０００１」、「０ｂ００００００１１１１１０」のグループは、それぞれ、処理コア＃３、処理コア＃２、処理コア＃３に振り分けられている。
【００６５】
また、振分テーブルの上位Ｎ桁ハッシュ値「０ｂ００００００１１」のエントリの「振分先処理コア」は、拡張振分テーブルへのポインタに変更される。また、該エントリの「集約閾値」には、集約閾値４００が格納される。すなわち、上位Ｎ桁ハッシュ値「０ｂ００００００１１」のグループのフロー数が４００以下になった場合には、細分化によってできたグループは集約され、これに伴い、拡張振分テーブルは削除される。
【００６６】
また、グループの細分化に伴い、処理コア管理テーブルの各処理コアのフロー数、連結リストも更新される。
【００６７】
図１０に示される細分化前の状態では、処理コア＃１、処理コア＃２、処理コア＃３のそれぞれの処理フロー数は、１０００、５００、０であり、処理コア＃１にフローが集中している。一方、図１１に示される細分化後の状態では、処理コア＃１、処理コア＃２、処理コア＃３のそれぞれの処理フロー数は、６００、５００、４００であり、フローは比較的処理コア全体に分散している。したがって、グループを細分化することによって所定の処理コアにフローが偏ることを解消することができる。
【００６８】
なお、拡張振分テーブル内の上位Ｍ桁ハッシュ値のグループをさらに細分化することもできる。この場合には、上位Ｌ桁（Ｍ＜Ｌ）のハッシュ値の拡張振分テーブルが作成される。
【００６９】
図１１に示されるように、振分テーブルと拡張振分テーブルとは、階層構造になっている。以降、グループの細分化によって作成された拡張振分テーブルを、下段の拡張振分テーブルと称する。また、拡張振分テーブルのポインタを「振分先処理コア」の値として有する振分テーブル又は拡張振分テーブルを、上段の振分テーブル又は拡張振分テーブルと称する。
【００７０】
＜処理の流れ＞
図１２Ａ、図１２Ｂ、図１２Ｃは、フロー登録時の振分管理コア１１による処理のフローチャートの一例である。図１２Ａに示される処理は、ＡＰＩを通じて、振分管理コア１１にＳＩＰサーバ２からフロー情報の通知を受けると開始される。通知されたフローを以
降、処理対象フローと称する。
【００７１】
ＯＰ１では、振分管理コア１１は、通知されたフロー情報からハッシュ値を算出する。次に処理がＯＰ２に進む。
【００７２】
ＯＰ２では、振分管理コア１１は、処理対象フローの全桁ハッシュ値が全桁ハッシュ値管理テーブルに登録済みであるか否かを判定する。処理対象フローの全桁ハッシュ値が全桁ハッシュ値管理テーブルに登録済みである場合には（ＯＰ２：ＹＥＳ）、処理がＯＰ３に進む。処理対象フローの全桁ハッシュ値が全桁ハッシュ値管理テーブルに登録されていない場合には（ＯＰ２：ＮＯ）、処理がＯＰ４に進む。
【００７３】
ＯＰ３では、処理対象フローの全桁ハッシュ値が全桁ハッシュ値管理テーブルに登録済みであるので、振分管理コア１１は、処理対象フローの全桁ハッシュ値に該当する全桁ハッシュ値管理テーブルのエントリの「フロー数」の値に、＋１を加算して更新する。次に処理がＯＰ５に進む。
【００７４】
ＯＰ４では、処理対象フローの全桁ハッシュ値が全桁ハッシュ値管理テーブルに登録されていないので、振分管理コア１１は、全桁ハッシュ値管理テーブルに処理対象フローのハッシュ値のエントリを登録する。該エントリの「フロー数」の値は１で登録される。次に処理がＯＰ５に進む。
【００７５】
ＯＰ５では、振分管理コア１１は、処理対象フローの上位Ｎ桁ハッシュ値に該当する振分テーブルのエントリの「振分先処理コア」の値が決定済みであるか否かを判定する。処理対象フローの上位Ｎ桁ハッシュ値に該当する振分テーブルのエントリの「振分先処理コア」の値が決定済みである場合には（ＯＰ５：ＹＥＳ）、処理が図１２ＢのＯＰ１１に進む。処理対象フローの上位Ｎ桁ハッシュ値に該当する振分テーブルのエントリの「振分先処理コア」の値が決定済みでない、すなわち、Ｎｕｌｌである場合には（ＯＰ５：ＮＯ）、処理がＯＰ６に進む。
【００７６】
ＯＰ６では、振分管理コア１１は、処理対象フローの上位Ｎ桁ハッシュ値のグループの振分先の処理コアを決定し、振分テーブルの該当エントリの「振分先処理コア」、「フロー数」を更新する。振分先の処理コアは、処理フロー数が上限に達していない処理コアの中から選択される。振分テーブルの該当エントリの「フロー数」の値は、１である。次に処理がＯＰ７に進む。
【００７７】
ＯＰ７では、振分管理コア１１は、ＯＰ６で選択された振分先の処理コアに該当する処理コア管理テーブルのエントリの「フロー数」の値に＋１を加算して更新する。次に処理がＯＰ８に進む。
【００７８】
ＯＰ８では、新たにフローグループが追加されたので、振分管理コア１１は、振分先の処理コアに該当する処理コア管理テーブルのエントリの連結リストの最後尾に、新規フローグループを追加する。次に処理がＯＰ９に進む。
【００７９】
ＯＰ９では、振分管理コア１１は、振分先の処理コアの登録フロー数が上限に達しているか否かを判定する。振分先の処理コアの登録フロー数が上限に達している場合には（ＯＰ９：ＹＥＳ）、処理がＯＰ１０に進み、ＯＰ１０ではフローグループの細分化処理が行われる。フローグループの細分化処理の詳細については、図１３において後述される。フローグループの細分化処理が終了すると、図１２Ａに示される処理が終了する。
【００８０】
振分先の処理コアの処理フロー数が上限に達していない場合には（ＯＰ９：ＮＯ）、図
１２Ａに示される処理が終了する。
【００８１】
図１２Ｂに示される処理は、処理対象フローの上位Ｎ桁ハッシュ値に該当する振分テーブルのエントリの「振分先処理コア」の値が決定済みである場合（図１２Ａ、ＯＰ５：ＹＥＳ）の処理である。
【００８２】
ＯＰ１１では、振分管理コア１１は、処理対象フローの上位Ｎ桁ハッシュ値に該当する振分テーブルのエントリの「振分先処理コア」の値を判定する。振分テーブルの該当エントリの「振分先処理コア」の値が処理コアの識別番号である場合には、処理がＯＰ１２に進む。振分テーブルの該当エントリの「振分先処理コア」の値が拡張振分テーブルへのポインタである場合には、処理がＯＰ１５に進む。
【００８３】
ＯＰ１２〜ＯＰ１４は、処理対象フローの上位Ｎ桁ハッシュ値に該当する振分テーブルのエントリの「振分先処理コア」の値が処理コアの識別番号である場合の処理である。ＯＰ１２では、振分管理コア１１は、振分テーブルの該当エントリの「フロー数」の値に＋１を加算して更新する。次に処理がＯＰ１３に進む。
【００８４】
ＯＰ１３では、振分管理コア１１は、振分テーブルの該当エントリの「振分先処理コア」に該当する処理コア管理テーブルのエントリの「フロー数」の値に＋１を加算して更新する。次に処理がＯＰ１４に進む。
【００８５】
ＯＰ１４では、振分管理コア１１は、処理対象フローの振分先の処理コアの連結リストを更新する。具体的には、振分管理コア１１は、連結リスト内の該当フローグループのフロー数に＋１を加算し、フロー数の降順で連結リスト内のフローグループを並び変える。次に処理が図１２ＡのＯＰ９に進む。
【００８６】
ＯＰ１５、ＯＰ１６は、処理対象フローの上位Ｎ桁ハッシュ値に該当する振分テーブルのエントリの「振分先処理コア」の値が下段の拡張振分テーブルへのポインタである場合の処理である。ＯＰ１５では、振分管理コア１１は、振分テーブルの「振分先処理コア」に格納されるポインタが示す下段の拡張振分テーブルを参照する。次に処理がＯＰ１６に進む。
【００８７】
ＯＰ１６では、振分管理コア１１は、処理対象フローの上位Ｍ桁ハッシュ値に該当する下段の拡張振分テーブルのエントリの「振分先処理コア」の値を判定する。下段の拡張振分テーブルの該当エントリの「振分先処理コア」の値が処理コアの識別番号又はＮｕｌｌである場合には、処理が図１２ＣのＯＰ２１に進む。下段の拡張振分テーブルの該当エントリの「振分先処理コア」の値がさらに下段の拡張振分テーブルへのポインタである場合には、該ポインタが示す拡張振分テーブルについて、ＯＰ１５、ＯＰ１６の処理が繰り返される。
【００８８】
図１２ＣのＯＰ２１〜ＯＰ２７の処理は、処理対象フローの上位Ｍ桁ハッシュ値に該当する下段の拡張振分テーブルのエントリの「振分先処理コア」の値が処理コアの識別番号又はＮｕｌｌである場合の処理である。以降、処理対象の拡張振分テーブルのハッシュ値の桁数をＱ（Ｑ：整数、Ｍ≦Ｑ≦ハッシュ値の全桁数）とする。
【００８９】
ＯＰ２１では、振分管理コア１１は、処理対象フローの上位Ｑ桁ハッシュ値に該当する拡張振分テーブルのエントリの「振分先処理コア」の値が決定済みであるか否かを判定する。処理対象フローの上位Ｑ桁ハッシュ値に該当する拡張振分テーブルのエントリの「振分先処理コア」の値が決定済みである場合には（ＯＰ２１：ＹＥＳ）、処理がＯＰ２５に進む。処理対象フローの上位Ｑ桁ハッシュ値に該当する拡張振分テーブルのエントリの「
振分先処理コア」の値が決定済みでない、すなわち、Ｎｕｌｌである場合には（ＯＰ２１：ＮＯ）、処理がＯＰ２２に進む。
【００９０】
ＯＰ２２では、振分管理コア１１は、処理対象フローの上位Ｑ桁ハッシュ値のグループの振分先の処理コアを決定し、拡張振分テーブルの該当エントリの「振分先処理コア」、「フロー数」を更新する。拡張振分テーブルの該当エントリの「フロー数」の値は、１で登録される。次に処理がＯＰ２３に進む。
【００９１】
ＯＰ２３では、振分管理コア１１は、ＯＰ２２で選択された振分先の処理コアに該当する処理コア管理テーブルのエントリの「フロー数」の値に＋１を加算して、該エントリを更新する。次に処理がＯＰ２４に進む。
【００９２】
ＯＰ２４では、新たにフローグループが追加されたので、振分管理コア１１は、振分先の処理コアに該当する処理コア管理テーブルのエントリの連結リストの最後尾に、新規フローグループを追加する。次に処理が図１２ＡのＯＰ９に進む。
【００９３】
ＯＰ２５〜ＯＰ２７は、処理対象フローの上位Ｑ桁ハッシュ値に該当する拡張振分テーブルのエントリの「振分先処理コア」の値が処理コアの識別番号である場合の処理である。ＯＰ２５では、振分管理コア１１は、拡張振分テーブルの該当エントリの「フロー数」の値に＋１を加算して更新する。次に処理がＯＰ２６に進む。
【００９４】
ＯＰ２６では、振分管理コア１１は、振分テーブルの該当エントリの「振分先処理コア」に該当する処理コア管理テーブルのエントリの「フロー数」の値に＋１を加算して、該エントリを更新する。次に処理がＯＰ２７に進む。
【００９５】
ＯＰ２７では、振分管理コア１１は、処理対象フローの振分先の処理コアの処理コア管理テーブルの該当エントリに対応する連結リストを更新する。具体的には、振分管理コア１１は、連結リスト内の該当フローグループのフロー数に＋１を加算し、フロー数の降順で連結リスト内のフローグループを並び変える。次に処理が図１２ＡのＯＰ９に進む。
【００９６】
図１３は、図１２ＡのＯＰ１０のグループ細分化処理のフローチャートの一例である。図１３では、上段の振分テーブル又は拡張振分テーブルのハッシュ値の桁数をＰ（整数、Ｎ≦Ｐ＜Ｑ）、下段の拡張振分テーブルのハッシュ値の桁数をＱとする。
【００９７】
ＯＰ３１では、振分管理コア１１は、登録フロー数が上限フロー数に達した処理コアの連結リスト内のグループの中で、フロー数が最大のグループを細分化対象グループとして選択する。次に処理がＯＰ３２に進む。
【００９８】
ＯＰ３２では、振分管理コア１１は、連結リストから細分化対象グループを削除する。次に処理がＯＰ３３に進む。
【００９９】
ＯＰ３３では、振分管理コア１１は、上位Ｐ桁が細分化対象グループと同じ値の上位Ｑ桁ハッシュ値の拡張振分テーブルを作成する。この上位Ｐ桁の値を、以降、Ｘとする。なお、この段階では、作成された拡張振分テーブルでは、「Ｑ桁ハッシュ値」の値の昇順で、上位Ｐ桁がＸであるすべてのＱ桁ハッシュ値のエントリが並んでおり、「振分先処理コア」、「フロー数」、「集約閾値」が初期状態（空）である。次に処理がＯＰ３４に進む。
【０１００】
ＯＰ３４、ＯＰ３５の処理は、全桁ハッシュ値管理テーブルの全エントリに対して実行される。以降、変数ｉは、全桁ハッシュ値管理テーブル内のエントリの並び順を示す。変
数ｉの初期値は０であり、ＯＰ３４、ＯＰ３５の処理が繰り返される度に＋１が加算される。
【０１０１】
ＯＰ３４では、振分管理コア１１は、全桁ハッシュ値管理テーブルのｉ行目の「全桁ハッシュ値」の上位Ｐ桁の値とＸとが一致するか否かを判定する。全桁ハッシュ値管理テーブルのｉ行目の「全桁ハッシュ値」の上位Ｐ桁の値とＸとが一致する場合には（ＯＰ３４：ＹＥＳ）、処理がＯＰ３５に進む。全桁ハッシュ値管理テーブルのｉ行目の「全桁ハッシュ値」の上位Ｐ桁の値とＸとが一致しない場合には（ＯＰ３４：ＮＯ）、次のエントリについてＯＰ３４の処理が繰り返される。
【０１０２】
ＯＰ３５では、振分管理コア１１は、全桁ハッシュ値テーブルのｉ行目のエントリの「全桁ハッシュ値」と上位Ｑ桁目まで一致する拡張振分テーブルのエントリの「フロー数」の値に＋１を加算する。その後、全桁ハッシュ値テーブルに未処理のエントリがある場合には、次のエントリについてＯＰ３４から処理が繰り返される。全桁ハッシュ値テーブルの全エントリについてＯＰ３４、ＯＰ３５の処理が行われた場合には、処理がＯＰ３６に進む。
【０１０３】
ＯＰ３６では、振分管理コア１１は、拡張振分テーブルのフローの登録がある、すなわち、「フロー数」が空でないエントリの「振分先処理コア」を決定して、拡張振分テーブルを更新する。次に処理がＯＰ３７に進む。
【０１０４】
ＯＰ３７では、振分管理コア１１は、拡張振分テーブルに基づいて、処理コア管理テーブル、連結リストを更新する。具体的には、振分管理コア１１は、処理コア管理テーブルの各エントリの「フロー数」に、「振分先処理コア」の処理コアが該当する拡張振分テーブルの全エントリの「フロー数」の総和を、加算する。また、振分管理コア１１は、拡張振分テーブル内の「フロー数」が１以上で、「振分先処理コア」の処理コアが決定済みのエントリのグループを、対応の処理コアの連結リストに追加し、フロー数の降順で並び変える。次に処理がＯＰ３８に進む。
【０１０５】
ＯＰ３８では、振分管理コア１１は、上段の振分テーブル又は拡張振分テーブルの該当エントリの「振分先処理コア」、「集約閾値」を更新する。具体的には、振分管理コア１１は、上段の振分テーブル又は拡張振分テーブルの該当エントリの「振分先処理コア」に下段の拡張振分テーブルへのポインタを格納する。また、振分管理コア１１は、上段の振分テーブル又は拡張振分テーブルの該当エントリの「集約閾値」に所定の値を格納する。ＯＰ３８の処理が終了すると、図１３に示されるグループ細分化処理が終了する。
【０１０６】
なお、ＯＰ３１では、細分化対象グループとして、登録フロー数が上限フロー数に達した処理コアの連結リストの中からフロー数が最大のグループが選択されたが、細分化対象グループはこれに限定されない。例えば、細分化対象グループは、登録フロー数が上限フロー数に達した処理コアの連結リストの中からランダムに選択されてもよいし、フロー数が最小のグループでもよい。
【０１０７】
図１４Ａ、図１４Ｂ、図１４Ｃ、図１４Ｄは、フロー削除時の振分管理コア１１による処理のフローチャートの一例である。図１４Ａに示されるフローチャートは、振分管理コア１１が、ＳＩＰサーバ２からＡＰＩを通じて削除対象のフロー情報の通知を受けると開始される。
【０１０８】
ＯＰ４１では、振分管理コア１１は、フロー情報からハッシュ値を算出する。次に処理がＯＰ４２に進む。
【０１０９】
ＯＰ４２では、振分管理コア１１は、全桁ハッシュ値管理テーブルから削除対象フローのハッシュ値に一致する「全桁ハッシュ値」を検索し、該当エントリの「フロー数」から１を引く。次に処理がＯＰ４３に進む。
【０１１０】
ＯＰ４３では、振分管理コア１１は、削除対象フローのハッシュ値に該当する全桁ハッシュ値管理テーブルのエントリの「フロー数」の値を判定する。削除対象フローのハッシュ値に該当する全桁ハッシュ値管理テーブルのエントリの「フロー数」の値が０である場合には、処理がＯＰ４４に進む。削除対象フローのハッシュ値に該当する全桁ハッシュ値管理テーブルのエントリの「フロー数」の値が１以上である場合には、処理がＯＰ４５に進む。
【０１１１】
ＯＰ４４では、振分管理コア１１は、削除対象フローのハッシュ値に該当する全桁ハッシュ値管理テーブルのエントリの「フロー数」の値が０であるので、該エントリを全桁ハッシュ値管理テーブルから削除する。次に処理がＯＰ４５に進む。
【０１１２】
ＯＰ４５では、振分管理コア１１は、振分テーブルから削除対象フローの上位Ｎ桁ハッシュ値と一致する「Ｎ桁ハッシュ値」を検索し、該当エントリの「フロー数」から１を引く。次に処理がＯＰ４６に進む。
【０１１３】
ＯＰ４６では、振分管理コア１１は、振分テーブルの該当エントリの「振分先処理コア」の値を判定する。振分テーブルの該当エントリの「振分先処理コア」の値が処理コアの識別番号である場合には、処理が図１４ＢのＯＰ５１に進む。振分テーブルの該当エントリの「振分先処理コア」の値が下段の拡張振分テーブルへのポインタである場合には、処理が図１４ＣのＯＰ６１に進む。
【０１１４】
図１４ＢのＯＰ５１〜ＯＰ５５は、削除対象フローの上位Ｎ桁ハッシュ値に該当する振分テーブルのエントリの「振分先処理コア」が、処理コアの識別番号である場合の処理である。ＯＰ５１では、振分管理コア１１は、削除対象フローの振分先の処理コアに該当する処理コア管理テーブルのエントリの「フロー数」から１を引く。次に処理がＯＰ５２に進む。
【０１１５】
ＯＰ５２では、振分管理コア１１は、削除対象フローの上位Ｎ桁ハッシュ値に該当する振分テーブルのエントリの「フロー数」の値を判定する。削除対象フローの上位Ｎ桁ハッシュ値に該当する振分テーブルのエントリの「フロー数」の値が０である場合には、処理がＯＰ５３に進む。削除対象フローの上位Ｎ桁ハッシュ値に該当する振分テーブルのエントリの「フロー数」の値が１以上である場合には、処理がＯＰ５５に進む。
【０１１６】
ＯＰ５３では、振分管理コア１１は、振分テーブルの該当エントリの「フロー数」の値が０であるので、処理コア管理テーブルの該当「処理コア」のエントリに対応する連結リストから、削除対象のフローの上位Ｎ桁ハッシュ値に該当するグループを削除する。次に処理がＯＰ５４に進む。
【０１１７】
ＯＰ５４では、振分管理コア１１は、削除対象フローの上位Ｎ桁ハッシュ値に該当する振分テーブルのエントリの「振分先処理コア」の値を削除し、Ｎｕｌｌとする。その後、図１４Ｂに示される処理が終了する。
【０１１８】
ＯＰ５５では、振分テーブルの該当エントリの「フロー数」の値が１以上であるので、振分管理コア１１は、処理コア管理テーブルの該当処理コアの連結リスト内の削除対象のフローの上位Ｎ桁ハッシュ値に該当するグループの「フロー数」から１を引いて更新する。その後、図１４Ｂに示される処理が終了する。
【０１１９】
図１４ＣのＯＰ６１以降の処理は、削除対象フローの上位Ｎ桁ハッシュ値に該当する振分テーブルのエントリの「振分先処理コア」が、下段の拡張振分テーブルへのポインタである場合の処理である。
【０１２０】
ＯＰ６１、ＯＰ６２の処理は、削除対象フローの上位Ｎ桁ハッシュ値に該当する拡張振分テーブルのエントリの「振分先処理コア」が下段の拡張振分テーブルへのポインタを示すたびに繰り返される。すなわち、ＯＰ６１、ＯＰ６２の処理は、拡張振分テーブルのさらに下段の拡張振分テーブルが存在する場合に段階的に確認を行う処理である。
【０１２１】
ＯＰ６１では、振分管理コア１１は、削除対象フローの上位Ｑ桁ハッシュ値に該当する拡張振分テーブルのエントリの「フロー数」の値から１を引く。次に処理がＯＰ６２に進む。
【０１２２】
ＯＰ６２では、振分管理コア１１は、削除対象フローの上位Ｑ桁ハッシュ値に該当する拡張振分テーブルのエントリの「振分先処理コア」の値を判定する。削除対象フローの上位Ｑ桁ハッシュ値に該当する拡張振分テーブルのエントリの「振分先処理コア」の値がさらに下段の拡張振分テーブルへのポインタである場合には、該下段の拡張振分テーブルについて、ＯＰ６１から処理が繰り返される。削除対象フローの上位Ｑ桁ハッシュ値に該当する拡張振分テーブルのエントリの「振分先処理コア」の値が、処理コアの識別番号である場合には、処理がＯＰ６３に進む。
【０１２３】
ＯＰ６３では、振分管理コア１１は、拡張振分テーブルの該当エントリの「振分先処理コア」が示す処理コアに該当する処理コア管理テーブルのエントリの「フロー数」の値から１を引く。次に処理がＯＰ６４に進む。
【０１２４】
ＯＰ６４では、振分管理コア１１は、削除対象フローの上位Ｑ桁ハッシュ値に該当する拡張振分テーブルのエントリの「フロー数」の値を判定する。拡張振分テーブルの該当エントリの「フロー数」の値が０である場合には、処理がＯＰ６５に進む。拡張振分テーブルの該当エントリの「フロー数」の値が１以上である場合には、処理がＯＰ６７に進む。
【０１２５】
ＯＰ６５では、振分管理コア１１は、拡張振分テーブルの該当エントリの「フロー数」の値が０であるので、処理コア管理テーブルの該当処理コアの連結リストから、削除対象のフローの上位Ｑ桁ハッシュ値に該当するグループを削除する。次に処理がＯＰ６６に進む。
【０１２６】
ＯＰ６６では、振分管理コア１１は、削除対象フローの上位Ｑ桁ハッシュ値に該当する拡張振分テーブルのエントリの「振分先処理コア」の値を削除し、Ｎｕｌｌとする。次に処理が図１４ＤのＯＰ６８に進む。
【０１２７】
ＯＰ６７では、拡張振分テーブルの該当エントリの「フロー数」の値が１以上であるので、振分管理コア１１は、処理コア管理テーブルの該当処理コアの連結リスト内の削除対象フローが属するグループのフロー数から１を引いて更新する。次に処理が図１４ＤのＯＰ６８に進む。
【０１２８】
図１４のＯＰ６８以降の処理は、細分化されてできたグループの集約を、階層構造の最下層の拡張振分テーブルから段階的に確認するための処理である。ＯＰ６８以降の処理は、階層構造になっている拡張振分テーブルの数だけ繰り返される。
【０１２９】
ＯＰ６８では、振分管理コア１１は、上段の振分テーブル又は拡張振分テーブルにおけ
る削除対象フローの上位Ｐ桁ハッシュ値に該当するエントリの「フロー数」の値が「集約閾値」の値以下であるか否かを判定する。上段の振分テーブル又は拡張振分テーブルにおける削除対象フローの上位Ｐ桁ハッシュ値に該当するエントリの「フロー数」の値が「集約閾値」の値より大きい場合には（ＯＰ６８：ＮＯ）、細分化されてできたグループの集約は行われず、図１４Ｄに示される処理が終了する。
【０１３０】
上段の振分テーブル又は拡張振分テーブルにおける削除対象フローの上位Ｐ桁ハッシュ値に該当するエントリの「フロー数」の値が「集約閾値」の値以下の場合には（ＯＰ６８：ＹＥＳ）、処理がＯＰ６９に進む。
【０１３１】
ＯＰ６９では、振分管理コア１１は、集約した場合のフロー、すなわち、上段の振分テーブル又は拡張振分テーブルにおける削除対象フローの上位Ｐ桁ハッシュ値に該当するエントリの「フロー数」のすべてを登録可能な処理コアがあるか否かを判定する。この判定は、処理コア管理テーブルに基づいて行われる。
【０１３２】
細分化されてできたグループを集約した場合のフローすべてを登録可能な処理コアがない場合には（ＯＰ６９：ＮＯ）、グループの集約ができず、図１４Ｄに示される処理が終了する。細分化されてできたグループを集約した場合のフローすべてを登録可能な処理コアがある場合には（ＯＰ６９：ＹＥＳ）、グループを集約することができ、処理がＯＰ７０に進む。
【０１３３】
ＯＰ７０では、振分管理コア１１は、現段の拡張振分テーブルの各エントリについて、「振分先処理コア」の「フロー数」の分だけ処理コア管理テーブルの該当処理コアのエントリの「フロー数」を減少させる。次に処理がＯＰ７１に進む。
【０１３４】
ＯＰ７１では、振分管理コア１１は、現段の拡張振分テーブルにおいて、「フロー数」が１以上であるエントリの「Ｑ桁ハッシュ値」に該当するグループを、該当処理コアの連結リストから外す。次に処理がＯＰ７２に進む。
【０１３５】
ＯＰ７２では、振分管理コア１１は、上段の振分テーブル又は拡張振分テーブルにおける削除対象フローの上位Ｐ桁ハッシュ値に該当するエントリを更新する。具体的には、振分管理コア１１は、上段の振分テーブル又は拡張振分テーブルの該当エントリの「振分先処理コア」の値を、下段の拡張振分テーブルへのポインタから処理コアの識別番号に書き換える。振分先の処理コアは、細分化されてできたグループを集約した場合のフローすべてを登録可能な処理コアから選択される。また、振分管理コア１１は、上段の振分テーブル又は拡張振分テーブルの該当エントリの「集約閾値」の値を削除する。次に処理がＯＰ７３に進む。
【０１３６】
ＯＰ７３では、振分管理コア１１は、ＯＰ７２で振分先に選択された処理コアに該当する処理コア管理テーブルの「フロー数」に、上段の振分テーブル又は拡張振分テーブルにおける削除対象フローの上位Ｐ桁ハッシュ値に該当するエントリの「フロー数」の値を加算する。次に処理がＯＰ７４に進む。
【０１３７】
ＯＰ７４では、振分管理コア１１は、ＯＰ７２で振分先に選択された処理コアに該当する処理コア管理テーブルのエントリの連結リストに、削除対象フローの上位Ｐ桁ハッシュ値に該当するグループを追加して、フロー数の降順に並び替える。次に処理がＯＰ７５に進む。
【０１３８】
ＯＰ７５では、振分管理コア１１は、現段の拡張振分テーブルを削除する。上段が拡張振分テーブルである場合には、該上段の拡張振分テーブルについてＯＰ６８からの処理が
繰り返される。上段が振分テーブルである場合には、図１４Ｄに示される処理が終了する。
【０１３９】
＜第１実施形態の作用効果＞
第１実施形態では、パケット処理装置１は、登録フロー数が処理コアの上限フロー数を超えた場合に、該処理コアを振分先とするフローグループのうちの一つを細分化し、細分化によってできたグループを各処理コアに振り分ける。これによって、図１０、図１１にも示したように、一つの処理コアにフローが偏ることを解消し、処理コア間でより均等にフローを振り分けることができる。
【０１４０】
また、第１実施形態では、グループの細分化に伴い、細分化対象グループについて振分テーブル又は拡張振分テーブルのエントリの更新が行われるが、他のグループについては振分テーブル又は拡張振分テーブルのエントリの更新は行われない。また、振分テーブル、拡張振分テーブルは、予め、取りうる上位Ｎ桁又はＭ桁のハッシュ値すべてについてエントリが用意される。さらに、グループの細分化に際しても、振分テーブルのデータ構造は変更なく、主記憶装置１０２の別の記憶領域に拡張振分テーブルが作成される。そのため、細分化対象以外のグループは、グループの細分化と並行して処理を継続でき、グループ細分化の影響を局所的に抑えることができる。
【０１４１】
また、細分化対象以外のグループのエントリについて振分テーブル又は拡張振分テーブルの更新が行われないため、振分管理コア１１のテーブル更新処理に要する時間も短くなる。これに伴い、振分コア１２が参照する振分テーブル又は拡張振分テーブルの更新に要する時間も短くなるため、振分コア１２によるテーブル参照の待ち時間分のパケットロスや遅延を軽減することができる。これによって、フローのパケット順の入れ違いを抑制でき、処理を安定させることができる。
【０１４２】
第１実施形態では、音声通信を取り扱うシステムが想定されている。音声通信は、遅延に敏感な通信の一つである。第１実施形態の場合には、ＳＩＰパケット（制御パケット）からフロー情報を取得可能なＳＩＰサーバ２によって、パケット処理装置１にフロー情報が通知される。そのため、パケット処理装置１は、音声パケット（ユーザパケット）が流れる前に、該当のフローの振分先を決定することができる。これによって、より遅延を少なくすることができる。
【０１４３】
また、音声パケットはパケットサイズが一定であり、処理量を管理しやすい。また、音声通信では、セッションの開始及び終了が明示的に行われる。そのため、第１実施形態の技術による効果が得られやすい。
【０１４４】
また、第１実施形態では、ハッシュ値を用いてフローグループが作成される。ハッシュ値は、フロー情報に含まれるＩＰアドレスやポート番号等のいずれかの情報に依存しないので、或る値に偏る可能性が少ない。また、グループの細分化の際には対象とするハッシュ値の桁数を多くして、フローグループを作成することによって、再計算をせずに、簡易な処理でグループを細分化することができる。
【０１４５】
＜その他＞
第１実施形態では、音声パケットを取り扱うネットワークが想定されていたが、第１実施形態で説明された技術の適用は、音声パケットを取り扱うネットワークに限定されず、あらゆるパケットを取り扱う通信ネットワークにおいて適用可能である。第１実施形態で説明された技術が適用可能なシステムには、例えば、ＨＴＴＰ（Hypertext Transfer Protocol）、ＦＴＰ（File Transfer Protocol）等のＴＣＰ（Transmission Control Protocol）の通信を扱うネットワークがある。音声パケットのように、制御パケットとユーザパ
ケットとで異なる装置に中継される通信を扱うネットワークに適用する場合には、ＳＩＰサーバ２が存在しないので、パケット処理装置１は、新規なハッシュ値を有するパケットの受信を契機に、振分先の処理コアの決定処理を開始する。
【０１４６】
また、第１実施形態では、フロー情報から算出される上位Ｎ桁ハッシュ値を用いて振分テーブルが、上位Ｍ桁ハッシュ値を用いて拡張振分テーブルが作成されるが、これに限られない。例えば、下位Ｎ桁、下位Ｍ桁のハッシュ値が用いられてもよいし、ハッシュ値中のいずれの桁の値が用いられてもよい。
【０１４７】
また、また、第１実施形態では、フロー情報から算出されるハッシュ値によってグループ化がなされているが、これに限られず、ハッシュ値以外の情報がグループ化に用いられてもよい。パケットから得られる情報であれば、宛先ＩＰアドレス、送信元ＩＰアドレス、宛先ポート番号、送信元ポート番号等のうちいずれの情報が用いられてもよい。例えば、上位Ｎ桁ハッシュ値の代わりに宛先ＩＰアドレスを用いて振分テーブルが作成され、上位Ｍ桁ハッシュ値の代わりに拡張振分テーブルが作成されてもよい。この場合には、宛先ＩＰアドレスは「第１の識別情報」、送信元ＩＰアドレスは「第２の識別情報」の一例となる。また、この逆であってもよい。
【０１４８】
また、第１実施形態では、パケット処理装置１内の複数の処理コアにパケットを振り分ける例が想定されていたが、振分管理コア１１、振分コア１２、処理コアの処理を、それぞれ独立した処理装置であってもよい。すなわち、振分管理コア１１に相当する処理装置がフローグループの振分先の処理装置を決定し、振分コア１２に相当する処理装置がパケットを該当する振分先の処理装置に転送し、処理コアに相当する処理装置がパケットの処理を行うシステムであってもよい。
【０１４９】
また、第１実施形態では、通信に係るパケットを処理するネットワークシステムが想定されていたが、第１実施形態において説明された技術は、通信に係るパケットに限られず、あらゆる分散処理のシステムに対して適用可能である。例えば、データセンタ内の分散処理等、並行して複数のデータブロックグループに対する処理が行われるシステムに適用可能である。この場合には、データブロックは、例えば、格納されるＤＢの識別情報、データの種類、データの作成者等によってグループ化されてもよい。
【０１５０】
＜第２実施形態＞
第１実施形態では、フローグループの細分化の際のグループ識別に用いられるハッシュ値の上位の桁数（Ｍ桁）は、予め管理者によって設定されている固定値が用いられる。第２実施形態では、新たに作成されるＭ桁拡張振分テーブルのグループ識別に用いられるハッシュ値の上位の桁数（Ｍ桁）は、細分化によって作成された各フローグループに対するフローの偏り及び全処理コアに対するフローの偏りに応じて、決定される。第２実施形態では、第１実施形態と共通の説明は省略される。
【０１５１】
図１５は、各処理コアに登録されているフロー数と、フローグループの分割数との関係の一例を示す図である。フローグループの細分化の際のグループ識別に用いられるハッシュ値の上位桁数の拡張幅は（Ｍ−Ｎ）であるので、フローグループの分割数は２＾（Ｍ−Ｎ）となる。以降、フローグループの細分化の際のグループ識別に用いられるハッシュ値の上位桁数の拡張幅を、単に、ハッシュ拡張幅、と称する。
【０１５２】
図１５では、処理コア１から処理コア１６にフローが登録されている例が示される。例えば、処理コア９に登録されている約７００のフローグループが分割される場合について、説明する。
【０１５３】
図１５には、処理コア９に登録されている約７００のフローが４分割された場合、及び、８分割された場合の、分割後のフローグループに登録されるフロー数のグラフも示されている。フローグループが４分割される場合には、ハッシュ拡張幅は２（２＾２＝４）である。フローグループが８分割される場合には、ハッシュ拡張幅は３（２＾３＝８）である。図１５に示されるように、４分割の場合と８分割の場合とを比較すると、８分割された場合の方が、分割後の各フローグループに登録されたフロー数の最大値は、小さくなる可能性が高い。
【０１５４】
図１５に示される例では、処理コア８にフローが集中しており、処理コア８の登録可能なフロー数は、残り約２００であるとする。処理コア９に登録されている約７００のフローが４分割された後のグループＡ（フロー数約３００）のフローの登録先に処理コア８が選択される場合には、処理コア８の最大処理可能フロー数を超えてしまう。そのため、この場合には、該グループＡを再度分割することになる。他にグループＡのフローを登録可能な処理コアがあり、全体的な性能には余裕があるにもかかわらず、フローグループの再細分化が発生する。
【０１５５】
フローグループの再細分化が発生すると、細分化処理の増加と、テーブルの多段化による振分管理コア１１、振分コア１２のリソースの消費が懸念される。
【０１５６】
一方、８分割された後のグループＡ（フロー数約１５０）のフローの登録先に処理コア８が選択される場合には、処理コア８の最大処理可能フロー数を超えないので、グループＡのフローを処理コア８に登録することができる。したがって、フローグループの分割数は多いほど、すなわち、ハッシュ拡張幅が大きいほど、フローグループの再細分化を抑制することができる、といえる。
【０１５７】
しかしながら、Ｍ桁拡張振分テーブルの行数は、２＾（Ｍ−Ｎ）であり、ハッシュ拡張幅が大きくなるほど、Ｍ桁拡張振分テーブルのサイズも増加する。そのため、ハッシュ拡張幅が大きくなると、Ｍ桁拡張振分テーブルを保持するメモリ使用量、検索にかかる時間の増加が懸念される。
【０１５８】
したがって、ハッシュ拡張幅は、フローグループの再細分化の発生の抑制と、Ｍ桁拡張振分テーブルのサイズ拡大による弊害の抑制との双方をできるだけ満たす値にすることが望ましい。そのために、第２実施形態では、ハッシュ拡張幅は、細分化によって作成された各フローグループに対するフローの偏り及び全処理コアに対するフローの偏りを考慮して、決定される。
【０１５９】
＜第２実施形態に係る装置構成＞
第２実施形態では、パケット処理装置のハードウェア構成及び機能構成は、第１実施形態と同様である。
【０１６０】
第２実施形態では、振分管理コア１１は、各Ｍ桁拡張振分テーブル内の各フローグループに登録されているフローの偏り（σ１）と、各処理コアに登録されているフローの偏り（σ２）とに基づいて、ハッシュ拡張幅を決定する。以降、ハッシュ拡張幅Ｍ−ＮをＸとする。
【０１６１】
振分管理コア１１は、各Ｍ桁拡張振分テーブル内の各フローグループに登録されているフローの偏りσ１として、各Ｍ桁拡張振分テーブルの各フローグループに登録されているフロー数の標準偏差の平均値を用いる。ここで用いられる標準偏差は、絶対値であり、０以上１以下の値をとる。すなわち、σ１は、０以上１以下の値をとる。
【０１６２】
偏りσ１の値が０に近い場合には、各Ｍ桁拡張振分テーブルにおいて、該Ｍ桁拡張振分テーブル内のフローグループについて、ほぼフローが均等に登録されており、現在のハッシュ拡張幅が適正であることが示される。そのため、振分管理コア１１は、ハッシュ拡張幅Ｘの増加幅が小さくなるように、換言すると、ハッシュ拡張幅Ｘが現在値から変動しないように、働きかける。
【０１６３】
一方、偏りσ１の値が１に近い場合には、１又は複数のいずれかのＭ桁拡張振分テーブルにおいて、特定のフローグループにフローが偏っていることが示される。この場合には、新たに細分化されるフローグループについて、フローをなるべく分散させるために、ハッシュ拡張幅Ｘが大きくなるように働きかける。
【０１６４】
すなわち、各Ｍ桁拡張振分テーブル内の各フローグループに登録されているフローの偏りσ１を算出することによって、現在のハッシュ拡張幅Ｘが適正であるか否かが確認される。偏りσ１の値が０に近いことを、以降、偏りσ１が小さい、と表現する。また、偏りσ１の値が１に近いことを、以降、偏りσ１が大きい、と表現する。
【０１６５】
フローグループごとに見た場合にフローが分散されていたとしても、処理コアごとに見た場合には、特定の処理コアにフローが偏って登録されている場合がある。そのため、振分管理コア１１は、各処理コアに登録されているフロー数の最大値と、全処理コアのフローの偏りσ２と、についても考慮する。
【０１６６】
各処理コアに登録されているフロー数の最大値が、処理コアの処理可能なフロー数の上限値に近い場合には、細分化されたフローグループの再振分によって、再細分化が発生する可能性が高い（図１５参照）。一方、各処理コアに登録されているフロー数の最大値が処理コアの処理可能なフロー数の上限値に比べて十分に小さい場合には、各処理コアのフローの受け入れに余裕があり、再細分化の発生の可能性は低い。以降、各処理コアに登録されているフロー数の最大値が、処理コアの処理可能なフロー数の上限値に近い又は該上限値に比べて十分に小さいことを、それぞれ、単に、各処理コアに登録されているフロー数の最大値が、大きい又は小さい、と称する。
【０１６７】
全処理コアのフローの偏りσ２として、第２実施形態では、各処理コアに登録されたフロー数の標準偏差の絶対値が用いられる。全処理コアのフローの偏りσ２が０に近い値の場合には、各処理コアのフローの登録に偏りがないことが示される。全処理コアのフローの偏りσ２が１に近い値の場合には、各処理コアのフローの登録に偏りがあることが示される。以降、全処理コアのフローの偏りσ２が０又は１に近い値であることを、それぞれ、全処理コアのフローの偏りσ２が小さい又は大きい、と表現する。
【０１６８】
各処理コアに登録されているフロー数の最大値が大きく、全処理コアのフローの偏りσ２も大きい場合には、図１５のように、特定の処理コアにフローが偏っており、且つ、該処理コアの登録可能なフロー数が少ないことが示される。この場合には、フローグループの再細分化が起こりやすくなっているため、振分管理コア１１は、ハッシュ拡張幅Ｘを大きくするように働きかける。
【０１６９】
各処理コアに登録されているフロー数の最大値が小さく、全処理コアのフローの偏りσ２も小さい場合には、処理コアへのフローの登録が分散されており、且つ、各処理コアの登録可能なフロー数にも余裕があることが示される。この場合には、振分管理コア１１は、現在のハッシュ拡張幅Ｘで十分又は過剰である、と判断し、ハッシュ拡張幅Ｘを小さくするように働きかける。
【０１７０】
以上のように作用するハッシュ拡張幅Ｘの算出式の一例として、振分管理コア１１は、
以下の算出式を用いる。
【数１】
0006606875.tif 000002
Ｄ：デフォルトのハッシュ拡張幅
ｍ１：フローグループのフローの偏り  重み係数（０≦ｍ１）
ｍ２：処理コアのフローの偏り  重み係数（０≦ｍ２）
σ１：Ｍ桁拡張振分テーブルの各フローグループのフローの偏り（０≦σ１≦１）
σ２：全処理コアのフローの偏り（０≦σ２≦１）
Ｓ１：各処理コアのフロー数の閾値
Ｓ２：全処理コアのフロー数の標準偏差の閾値
【０１７１】
Ｄは、ハッシュ拡張幅のデフォルト値である。ｍ１、ｍ２は、重み係数である。ｍ１、ｍ２は、それぞれ、０以上の値であり、管理者によって任意に設定される。例えば、ｍ１又はｍ２のいずれか一方を０に設定し、Ｍ桁拡張振分テーブルの各フローグループのフローの偏りσ１、又は、全処理コアのフローの偏りσ２のいずれか一方を考慮せずにハッシュ拡張幅Ｘを算出することも可能である。
【０１７２】
σ２の値は、各処理コアのフロー数の最大値が閾値Ｓ１以上である場合には、＋の値となる。各処理コアのフロー数の最大値が閾値Ｓ１以上である場合には、再細分化が発生する可能性が高いと判定されるので、ハッシュ拡張幅Ｘを大きくするためである。
【０１７３】
また、σ２の値は、各処理コアのフロー数の最大値が閾値Ｓ１未満である場合には、マイナスの値となる。各処理コアのフロー数の最大値が閾値Ｓ１未満である場合には、再細分化が発生する可能性が低いと判定されるので、ハッシュ拡張幅Ｘを小さくするためである。
【０１７４】
また、Ｓ１≦各処理コアのフロー数の最大値（“＋”）、且つ、Ｓ２≦σ２となる場合、及び、各処理コアのフロー数の最大値＜Ｓ１（“−”）、且つ、σ２＜Ｓ２となる場合には、０が乗じられる。Ｓ１≦各処理コアのフロー数の最大値（“＋”）、且つ、Ｓ２≦σ２となる場合には、フローの偏りが少なく、各処理コアに登録可能な上限値に近い値でフローが登録されていると判定され、いずれの処理コアも余裕が少ない。Ｓ２≦σ２となる場合、及び、各処理コアのフロー数の最大値＜Ｓ１（“−”）、且つ、σ２＜Ｓ２となる場合には、特定の処理コアにフローの偏りはあるものの、該処理コアの余裕がある。これらの場合には、各処理コアのフローの偏りによる再細分化の発生への作用が少ないためである。
【０１７５】
なお、ハッシュ拡張幅Ｘの算出式は上記のものに限定されない。例えば、Ｓ１≦各処理コアのフロー数の最大値（“＋”）、且つ、Ｓ２≦σ２となる場合、及び、各処理コアのフロー数の最大値＜Ｓ１（“−”）、且つ、σ２＜Ｓ２となる場合でも、０を乗じなくともよい。
【０１７６】
＜処理の流れ＞
図１６は、ハッシュ拡張幅の算出処理のフローチャートの一例である。図１６に示される処理は、例えば、フローグループの細分化が行われる前、又は、後に開始される。より具体的には、例えば、図１２ＡのＯＰ１０の処理の前、又は、後に開始される。
【０１７７】
ＯＰ８１では、振分管理コア１１は、既存の各Ｍ桁拡張振分テーブル内の各フローグループに登録されているフロー数の標準偏差から、偏りσ１を算出する。ＯＰ８１の処理の詳細は、後述される。次に処理がＯＰ８２に進む。
【０１７８】
ＯＰ８２では、振分管理コア１１は、各処理コアに登録されているフロー数の標準偏差から偏りσ２を算出する。ＯＰ８２の処理の詳細は、後述される。次に処理がＯＰ８３に進む。
【０１７９】
ＯＰ８３では、振分管理コア１１は、偏りσ１、σ２の値から、ハッシュ拡張幅Ｘを算出する。ＯＰ８３では、例えば、式１が用いられる。その後、図１６に示される処理が終了する。
【０１８０】
ハッシュ拡張幅の算出処理がフローグループの細分化の前に行われる場合には、ＯＰ８３で算出されたハッシュ拡張幅を用いて、Ｍ桁拡張振分テーブルが作成される（図１３、ＯＰ３３）。ハッシュ拡張幅の算出処理がフローグループの細分化の後に行われる場合には、ＯＰ８３で算出されたハッシュ拡張幅は、メモリに保持され、次のフローグループの細分化の際に、用いられる。
【０１８１】
なお、ＯＰ８１の偏りσ１の算出処理と、ＯＰ８２の偏りσ２の算出処理との実行順は、逆であってもよい。
【０１８２】
図１７は、偏りσ１の算出処理のフローチャートの一例である。変数ｉは、既存のＭ桁拡張振分テーブルのいずれかを示すポインタである。変数ｉは初期値が１であり、１からＰまでの値をとる。Ｐは、Ｍ桁拡張振分テーブルの数である。
【０１８３】
ＯＰ９１では、振分管理コア１１は、ｉ個目のＭ桁拡張振分テーブル内の上位Ｍ桁ハッシュ値で識別される各フローグループのフロー数から、標準偏差σ１ｉを算出する。なお、標準偏差σ１ｉは、絶対値として算出される。ＯＰ９１の処理は、変数ｉがＰになるまで繰り返し行われ、すべてのＭ桁拡張振分テーブルについて標準偏差σ１ｉが算出されると、処理がＯＰ９２に進む。
【０１８４】
ＯＰ９２では、振分管理コア１１は、各Ｍ桁拡張振分テーブルについて算出された標準偏差σ１１、σ１２、．．．、σ１Ｐの平均値をσ１として算出する。その後、図１７に示される処理が終了し、図１６に示される処理に戻る。
【０１８５】
なお、図１６のハッシュ拡張幅の算出処理がフローグループの細分化の前に実行される場合には、フローグループの細分化の１回目の時点では、Ｍ桁拡張振分テーブルは存在しておらず、σ１は、０となる。図１６のハッシュ拡張幅の算出処理がフローグループの細分化の後に実行される場合には、フローグループの細分化の１回目の時点では、該細分化によって作成された１つのＭ桁拡張振分テーブルの標準偏差σ１１がσ１となる。
【０１８６】
図１８は、偏りσ２の算出処理のフローチャートの一例である。ＯＰ１０１では、振分管理コア１１は、処理コア管理テーブルを参照して、各処理コアに登録されているフロー数の標準偏差を、偏りσ２として算出する。なお、偏りσ２は、各処理コアに登録されているフロー数の標準偏差の絶対値をとった値である。次に処理がＯＰ１０２に進む。
【０１８７】
ＯＰ１０２では、振分管理コア１１は、各処理コアに登録されているフロー数の最大値が閾値Ｓ１以上であるか否かを判定する。この判定は、処理コア管理テーブルに基づいて行われる。
【０１８８】
各処理コアに登録されているフロー数の最大値が閾値Ｓ１以上である場合には（ＯＰ１０２：ＹＥＳ）、処理がＯＰ１０３に進む。各処理コアに登録されているフロー数の最大値が閾値Ｓ１未満である場合には（ＯＰ１０２：ＮＯ）、処理がＯＰ１０５に進む。
【０１８９】
ＯＰ１０３では、振分管理コア１１は、偏りσ２が閾値Ｓ２以上であるか否かを判定する。偏りσ２が閾値Ｓ２以上である場合には（ＯＰ１０３：ＹＥＳ）、処理がＯＰ１０４に進む。偏りσ２が閾値Ｓ２未満である場合には（ＯＰ１０３：ＮＯ）、処理がＯＰ１０６に進む。
【０１９０】
ＯＰ１０４では、振分管理コア１１は、各処理コアに登録されているフロー数の最大値が閾値Ｓ１以上であり、且つ、偏りσ２が閾値Ｓ２以上であるので、偏りσ２を＋の値とする。これによって、偏りσ２は、ハッシュ拡張幅が広げられる方向に作用する。その後、図１８に示される処理が終了し、処理が図１６に戻る。
【０１９１】
ＯＰ１０５では、振分管理コア１１は、偏りσ２が閾値Ｓ２以上であるか否かを判定する。偏りσ２が閾値Ｓ２以上である場合には（ＯＰ１０５：ＹＥＳ）、処理がＯＰ１０６に進む。偏りσ２が閾値Ｓ２未満である場合には（ＯＰ１０５：ＮＯ）、処理がＯＰ１０７に進む。
【０１９２】
ＯＰ１０６では、振分管理コア１１は、各処理コアに登録されているフロー数の最大値が閾値Ｓ１以上であり、且つ、偏りσ２が閾値Ｓ２未満、又は、各処理コアに登録されているフロー数の最大値が閾値Ｓ１未満であり、且つ、偏りσ２が閾値Ｓ２以上であるので、偏りσ２の値を０にする。その後、図１８に示される処理が終了し、処理が図１６に戻る。
【０１９３】
ＯＰ１０７では、振分管理コア１１は、各処理コアに登録されているフロー数の最大値が閾値Ｓ１未満であり、且つ、偏りσ２が閾値Ｓ２未満であるので、偏りσ２を−の値とする。これによって、偏りσ２は、ハッシュ拡張幅を小さくする方向に作用する。その後、図１８に示される処理が終了し、処理が図１６に戻る。
【０１９４】
＜第２実施形態の作用効果＞
第２実施形態では、振分管理コア１１は、ハッシュ拡張幅を、各Ｍ桁拡張振分テーブル内の各フローグループに登録されているフローの偏りσ１と、各処理コアに登録されているフローの偏りσ２とに応じて、算出する。これによって、フローグループの細分化の際に、細分化されたフローグループをさらに細分化する再細分化の発生を抑制しつつ、新規のＭ桁拡張テーブルのサイズが大きくなりすぎてリソースが無駄に消費されることを抑制することができる。
【０１９５】
なお、第２実施形態では、各Ｍ桁拡張振分テーブル内の各フローグループに登録されているフローの偏りσ１は、各Ｍ桁拡張振分テーブル内の各フローグループに登録されているフロー数の標準偏差に基づいて、算出される。また、各処理コアに登録されているフローの偏りσ２は、各処理コアに登録されているフロー数の標準偏差に基づいて算出される。ただし、これに限られず、偏りσ１、σ２は、それぞれ、各Ｍ桁拡張振分テーブル内の各フローグループに登録されているフロー数、各処理コアに登録されているフロー数の分散に基づいて算出されてもよい。フローの偏り具合を示す指標であれば、偏りσ１、σ２
は、標準偏差、分散等のいずれかに限定されない。
【符号の説明】
【０１９６】
１        パケット処理装置
２        ＳＩＰサーバ
１１      振分管理コア
１２      振分コア
１４      データベース
１０１    ＣＰＵ
１０２    主記憶装置
【図１】
0006606875.tif 000003
【図２】
0006606875.tif 000004
【図３】
0006606875.tif 000005
【図４】
0006606875.tif 000006
【図５】
0006606875.tif 000007
【図６】
0006606875.tif 000008
【図７】
0006606875.tif 000009
【図８】
0006606875.tif 000010
【図９】
0006606875.tif 000011
【図１０】
0006606875.tif 000012
【図１１】
0006606875.tif 000013
【図１２Ａ】
0006606875.tif 000014
【図１２Ｂ】
0006606875.tif 000015
【図１２Ｃ】
0006606875.tif 000016
【図１３】
0006606875.tif 000017
【図１４Ａ】
0006606875.tif 000018
【図１４Ｂ】
0006606875.tif 000019
【図１４Ｃ】
0006606875.tif 000020
【図１４Ｄ】
0006606875.tif 000021
【図１５】
0006606875.tif 000022
【図１６】
0006606875.tif 000023
【図１７】
0006606875.tif 000024
【図１８】
0006606875.tif 000025