(57)【要約】【課題】処理待ちのパケットが存在するにもかかわらず空きのパケット処理部を有効に利用できない状況が長く続く可能性が高いこと。【解決手段】ネットワーク装置１００は、第１のキュー１１０と、複数の第２のキュー１３０と、分配部１４０と、複数のパケット処理部１２０とを有する。分配部１４０は、第１のキュー１１０から取り出したパケットを、そのパケットのグループ以外のグループのパケットが格納されていない第２のキュー１３０に格納する。複数のパケット処理部１２０は、１以上のパケットが格納されている第２のキュー１３０のうち、他のパケット処理部が処理の対象としていないグループのパケットを格納する第２のキュー１３０からパケットを取り出して処理を行う。【選択図】図１
2012209695.tif 000002
【特許請求の範囲】
【請求項１】
第１のキューと、
複数の第２のキューと、
前記第１のキューから取り出したパケットを、そのパケットのグループ以外のグループのパケットが格納されていない前記第２のキューに格納する分配手段と、
１以上の前記パケットが格納されている前記第２のキューのうち他のパケット処理手段が処理の対象としていないグループのパケットを格納する前記第２のキューからパケットを取り出して処理を行う複数のパケット処理手段と
を有することを特徴とするネットワーク装置。
【請求項２】
キュー長が１以上の前記第２のキューのリストを有し、
前記分配手段は、前記キュー長が１になった前記第２のキューのキュー識別子を前記リストの最後尾につなぎ、
前記パケット処理手段は、空きが生じたときに前記リストの先頭につながれている前記キュー識別子を外して、該外したキュー識別子で特定される前記第２のキューを自パケット処理手段による処理の対象とする
ことを特徴とする請求項１に記載のネットワーク装置。
【請求項３】
前記第２のキューのキュー識別子に対応付けてグループ識別子とキュー長とを記憶するキュー管理テーブルを有し、
前記分配手段は、前記第１のキューから取り出したパケットを、そのパケットのグループ識別子と同じグループ識別子に対応して前記キュー管理テーブルに記憶されているキュー識別子で特定される前記第２のキューに格納すると共に、対応する前記キュー長をインクリメントし、
前記パケット処理手段は、自パケット処理手段が処理の対象としている前記第２のキューのパケットの処理に応じて、対応する前記キュー長をデクリメントする
ことを特徴とする請求項２に記載のネットワーク装置。
【請求項４】
前記パケット処理手段は、自パケット処理手段が処理の対象としている前記第２のキューから連続して閾値の数だけのパケットを取り出して処理し終えた時点で当該第２のキューを処理の対象から外し、該外した前記第２のキューのキュー長が１以上であればそのキュー識別子を前記リストの最後尾につなぐ
ことを特徴とする請求項３に記載のネットワーク装置。
【請求項５】
前記分配手段は、前記第１のキューから取り出したパケットのグループ識別子と同じグループ識別子に対応するキュー識別子が前記キュー管理テーブルに記憶されていないときは、前記複数の第２のキューのうちキュー長が０の何れか１つの前記第２のキューに前記パケットを格納すると共に、該格納した第２のキューのキュー識別子に対応付けて前記格納したパケットのグループ識別子を前記キュー管理テーブルに記憶する
ことを特徴とする請求項４に記載のネットワーク装置。
【請求項６】
前記分配手段は、前記複数の第２のキューのうちキュー長が０の前記第２のキューが存在しない場合には、キュー長が０の前記第２のキューが発生するまで待ち合わせを行う
ことを特徴とする請求項５に記載のネットワーク装置。
【請求項７】
前記複数の第２のキューは、前記パケット処理手段の数だけ存在し、前記パケット処理手段と前記第２のキューとが１対１に対応付けられている
ことを特徴とする請求項１に記載のネットワーク装置。
【請求項８】
前記分配手段は、前記第１のキューから取り出したパケットのグループが何れの前記第２のキューに格納されているパケットのグループとも一致しない場合には、何れかの前記第２のキューのキュー長が０になるまで待ち合わせを行う
ことを特徴とする請求項７に記載のネットワーク装置。
【請求項９】
前記第２のキューのキュー識別子に対応付けてグループ識別子とキュー長とを記憶するキュー管理テーブルを有し、
前記分配手段は、前記第１のキューから取り出したパケットのグループ識別子と同じグループ識別子が前記キュー管理テーブルに記憶されているか否かを判定し、記憶されていれば、記憶されているキュー識別子で特定される前記第２のキューに前記取り出したパケットを格納すると共に対応する前記キュー長をインクリメントし、記憶されていなければ、キュー長が０の第２のキューが存在するか否かを判定し、存在すれば、存在した第２のキューのキュー識別子に対応するグループ識別子に前記取り出したパケットのグループ識別子を設定して前記取り出したパケットを格納すると共に対応する前記キュー長をインクリメントし、存在しなければ何れかの前記第２のキューのキュー長が０になるまで待ち合わせを行い、
前記パケット処理手段は、対応する前記第２のキューのパケットの処理に応じて、対応する前記キュー長をデクリメントする
ことを特徴とする請求項８に記載のネットワーク装置。
【請求項１０】
第１のキューと、複数の第２のキューと、分配手段と、複数のパケット処理手段とを有するネットワーク装置が実行する処理方法であって、
前記分配手段が、前記第１のキューから取り出したパケットを、そのパケットのグループ以外のグループのパケットが格納されていない前記第２のキューに格納し、
前記複数のパケット処理手段が、１以上の前記パケットが格納されている前記第２のキューのうち他のパケット処理手段が処理の対象としていないグループのパケットを格納する前記第２のキューからパケットを取り出して処理を行う
ことを特徴とする処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はネットワーク装置に関し、特に複数のパケット処理部を使用してパケットを並列に処理するネットワーク装置に関する。
【背景技術】
【０００２】
この種のネットワーク装置の一例が特許文献１に記載されている。特許文献１に記載されたネットワーク装置（以下、本発明に関連するネットワーク装置と言う）は、パケットを受信順に記憶する第１のキューと、複数のパケット処理部と、このパケット処理部に１対１に対応する第２のキューと、パケット振り分け部と、振り分け情報テーブルと、複数のパケット処理部の負荷状態を定期的に収集する統計情報収集部とを有する。このような構成を有するネットワーク装置は、以下のように動作する。
【０００３】
振り分け情報テーブルには、ハッシュ値とパケット処理部とカウンタとの組が記憶されている。ここで、ハッシュ値はパケットが属するグループを特定する情報である。特許文献１では、グループとしてフローを使用する。パケット振り分け部は、第１のキューからパケットを取り出し、そのパケットのヘッダ情報から計算したハッシュ値と同じハッシュ値に対応して上記振り分け情報テーブルに記憶されているパケット処理部に対応する第２のキューに格納し、対応するカウンタを＋１する。各パケット処理部は、対応する第２のキューからパケットを取り出して処理を行い、振り分け情報テーブル上の対応するカウントを−１する。
【０００４】
またパケット振り分け部は、統計情報収集部で収集された各パケット処理部の負荷状態を参照して、最も負荷の少ないパケット処理部に特定のグループのパケットを振り分けるべく、振り分け情報テーブル中のハッシュ値とパケット処理部との対応関係を更新する。このパケット振り分け先の変更は、何れの第２のキューにも上記特定のグループのパケットが存在していないタイミングを捉えて実施される。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０１０−１６１５４６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
上述した本発明に関連するネットワーク装置は、同じグループのパケットを同じパケット処理部で処理するようにしており、また特定のグループの振り分け先を変更する際にはそのグループのパケットが何れの第２のキューにも格納されていないタイミングを捉えて実施するため、グループ内でのパケットの順序の逆転は発生しない。
【０００７】
しかしながら、上述した本発明に関連するネットワーク装置は、同じキューに複数のグループのパケットを混在させているため、処理待ちのパケットが存在するにもかかわらず空きのパケット処理部を有効に利用できない状況が長い時間続く可能性が高い。
【０００８】
例えば、図１２および図１３において、Ａ〜Ｄの４つのグループを想定し、各々のグループＡ〜Ｄのパケットをａ〜ｄとする。また図１２に示すように、グループＡとグループＢは第１のパケット処理部で処理し、グループＣとグループＤは第２のパケット処理部で処理するようにグループの振り分け先が設定されているとする。このとき、グループＡ〜Ｄのパケットがその後も継続して入力されるならば、２つのパケット処理部は空き状態になることはない。しかし、グループＡとグループＢのパケットがその後も継続して入力される一方、グループＣとグループＤのパケットが全く途絶えると、図１３に示すように、第２のパケット処理部に対応するキューは空になり、第２のパケット処理部は空き状態になる。このとき、グループＡとグループＢのパケットはその後も継続して第１のパケット処理部に対応するキューに入力され続けるため、グループＡまたはグループＢの何れか一方のグループの振り分け先を第１のパケット処理部から第２のパケット処理部に変更することはできない。従って、空いている第２のパケット処理部を有効に利用できない状態が長く続くことになる。
【０００９】
本発明の目的は、上述した課題、すなわち、処理待ちのパケットが存在するにもかかわらず空きのパケット処理部を有効に利用できない状況が長く続く可能性が高い、という課題を解決するネットワーク装置を提供することにある。
【課題を解決するための手段】
【００１０】
本発明の一形態にかかるネットワーク装置は、
第１のキューと、
複数の第２のキューと、
前記第１のキューから取り出したパケットを、そのパケットのグループ以外のグループのパケットが格納されていない前記第２のキューに格納する分配手段と、
１以上の前記パケットが格納されている前記第２のキューのうち他のパケット処理手段が処理の対象としていないグループのパケットを格納する前記第２のキューからパケットを取り出して処理を行う複数のパケット処理手段と
を有する、といった構成を採る。
【発明の効果】
【００１１】
本発明は上述したような構成を有するため、処理待ちのパケットが存在するにもかかわらず空きのパケット処理部を有効に利用できない状況が長く続くことを防止でき、パケット処理部の有効利用が可能になる。
【図面の簡単な説明】
【００１２】
【図１】本発明の第1の実施形態のブロック図である。
【図２】本発明の第２の実施形態のブロック図である。
【図３】本発明の第２の実施形態における管理情報記憶部の構成例を示す図である。
【図４】本発明の第２の実施形態における分配部の処理を示すフローチャートである。
【図５】本発明の第２の実施形態におけるパケット処理部の処理を示すフローチャートである。
【図６】本発明の第３の実施形態のブロック図である。
【図７】本発明の第３の実施形態における分配部の処理を示すフローチャートである。
【図８】本発明の第３の実施形態におけるパケット処理部の処理を示すフローチャートである。
【図９】本発明の第４の実施形態のブロック図である。
【図１０】本発明の第４の実施形態の動作説明図である。
【図１１】本発明の第５の実施形態のブロック図である。
【図１２】本発明に関連するネットワーク装置の動作説明図である。
【図１３】本発明に関連するネットワーク装置の動作説明図である。
【発明を実施するための形態】
【００１３】
次に本発明の実施の形態について図面を参照して詳細に説明する。
[第１の実施形態]
図１を参照すると、本発明の第１の実施形態にかかるネットワーク装置１００は、第１のキュー１１０と、Ｎ（≧２）個のパケット処理部１２０と、Ｍ（≧Ｎ）個の第２のキュー１３０と、分配部１４０とを有する。
【００１４】
第１のキュー１１０および複数の第２のキュー１３０は、パケットを先入れ先だし方式で格納する機能を有する記憶手段である。
【００１５】
分配部１４０は、第１のキュー１１０から取り出したパケットを、そのパケットのグループ以外のグループのパケットが格納されていない第２のキュー１３０に格納する機能を有する。グループとは、例えばセッションである。パケットのグループは、例えばパケットのヘッダ情報に含まれる情報に基づいて決定される。
【００１６】
パケット処理部１２０は、１以上のパケットが格納されている第２のキュー１３０のうち、他のパケット処理部１２０が処理の対象としていないグループのパケットを格納する第２のキュー１３０からパケットを取り出して処理を行う機能を有する。パケット処理部１２０で処理されたパケットは、例えば図示しない処理済キューに格納してもよいし、それ以外の任意の方法で処理してもよい。
【００１７】
次に本実施形態の動作を説明する。
【００１８】
処理の対象となるパケットは、第１のキュー１１０に一旦入力され、保持される。分配部１４０は、第１のキュー１１０に格納されたパケットを入力順に取り出し、そのパケットのグループを認識する。そして分配部１４０は、複数の第２のキュー１２０のうち、認識したグループ以外のグループのパケットが格納されていない第２のキュー１３０に上記のパケットを格納する。若し、そのような第２のキューが存在しなければ、そのような第２のキューが生じるまで処理を保留する。
【００１９】
それぞれのパケット処理部１２０は、１以上のパケットが格納されている第２のキュー１３０のうち、他のパケット処理部１２０が処理の対象としていないグループのパケットを格納する第２のキュー１３０からパケットを取り出して処理を行う。それぞれのパケット処理部１２０は、同時には１つの第２のキュー１３０を処理の対象とする。
【００２０】
次に本実施形態の効果を説明する。
【００２１】
本実施形態では、１つの第２のキュー１３０には、１つのグループのパケットしか格納されない。また、複数のパケット処理部１２０が同じ第２のキュー１３０を同時に処理対象とすることはない。これにより、第１のキュー１１０に格納されているパケットの順序とパケット処理部１２０で処理されて出力されるパケットの順序とは、同じグループのパケット間で同じになる。すなわち、パケットの順序性を保証することができる。
【００２２】
また本実施形態によれば、処理待ちのパケットが存在するにもかかわらず空きのパケット処理部１２０を有効に利用できない状況が長く続くことを防止でき、パケット処理部１２０の有効利用が可能になる。その理由は、空きの生じたパケット処理部１２０に処理待ちのパケットを投入できない状況が続くのは、第１のキュー１１０から次に取り出すパケットが、他のパケット処理部１２０で現在処理されているグループと同じグループの場合であるが、そのような状況になる確率は、１つの第２のキュー１３０に１つのグループしか格納しない方が、１つの第２のキュー１３０に複数のグループを混在させて格納するよりも小さくなるためである。特に本実施形態によれば、ネットワーク装置１００で処理されるパケットのグループの数がパケット処理部１２０の数まで低下した場合、必ず、１つのパケット処理部１２０で１つのグループのパケットが処理される状態になるため、図１３に示したような空きの第２のパケット処理部が発生することはない。
【００２３】
[第２の実施形態]
図２を参照すると、本発明の第２の実施形態にかかるネットワーク装置２００は、第１のキュー２１０と、Ｎ（≧２）個のパケット処理部２２０と、Ｍ（＞Ｎ）個の第２のキュー２３０と、分配部２４０と、管理情報記憶部２５０とを有する。
【００２４】
第１のキュー２１０および複数の第２のキュー２３０は、パケットを先入れ先だし方式で格納する機能を有する記憶手段である。
【００２５】
管理情報記憶部２５０は、図３に示すように、キュー管理テーブル２５１と処理待ちキューのリスト２５２とから構成される。
【００２６】
キュー管理テーブル２５１は、第２のキュー２３０のキュー識別子に対応付けて、グループ識別子とキュー長とを記憶する。グループとは、例えばセッションである。パケットのグループは、例えばパケットのヘッダ情報に含まれる情報に基づいて決定される。
【００２７】
リスト２５２は、キュー長が１以上の第２のキュー２３０のリストである。
【００２８】
分配部２４０は、第１のキュー２１０から取り出したパケットを、そのパケットのグループ識別子と同じグループ識別子に対応してキュー管理テーブル２５１に記憶されているキュー識別子で特定される第２のキュー２３０に格納し、対応するキュー長をインクリメントする機能を有する。また、分配部２４０は、第１のキュー２１０から取り出したパケットのグループ識別子と同じグループ識別子に対応するキュー識別子がキュー管理テーブル２５１に記憶されていないときは、第２のキュー２３０のうちキュー長が０の何れか１つの第２のキューに上記パケットを格納し、その格納した第２のキュー２３０のキュー識別子に対応付けて上記格納したパケットのグループ識別子をキュー管理テーブル２５１に記憶する機能を有する。さらに、分配部２４０は、キュー長が０の第２のキュー２３０が１つも存在しない場合には、キュー長が０の第２のキュー２３０が発生するまで待ち合わせを行う機能を有する。また分配部２４０は、パケットを格納することによってキュー長が１になった第２のキュー２３０のキュー識別子を、処理待ちキューのリスト２５２の最後尾につなぐ機能を有する。
【００２９】
パケット処理部２２０は、空きが生じたときにリスト２５２の先頭につながれているキュー識別子を外して、この外したキュー識別子で特定される第２のキュー２３０を自パケット処理手段による処理の対象とする機能を有する。またパケット処理部２２０は、処理対象の第２のキュー２３０からパケットを取り出して処理し、キュー管理テーブル２５１の対応するキュー長をデクリメントする機能を有する。さらに、パケット処理部２２０は、自パケット処理手段が処理の対象としている第２のキュー２３０から連続して閾値の数だけのパケットを取り出して処理し終えた時点で、この第２のキュー２３０を処理の対象から外し、その第２のキュー２３０のキュー長が１以上であればそのキュー識別子をリスト２５２の最後尾につなぐ機能を有する。パケット処理部２２０で処理されたパケットは、例えば図示しない処理済キューに格納してもよいし、それ以外の任意の方法で処理してもよい。
【００３０】
次に本実施形態の動作を説明する。
【００３１】
図４は分配部２４０の処理の一例を示すフローチャートである。処理の対象となるパケットは、第１のキュー２１０に一旦入力され、保持される。分配部２４０は、第１のキュー２１０に１以上のパケットが格納されているか否かを判定し（ステップＳ１）、格納されていれば、その先頭のパケットのグループ識別子を求める（ステップＳ２）。
【００３２】
次に分配部２４０は、この求めたグループ識別子に対応する第２のキュー２３０が存在するか否かをキュー管理テーブル２５１を検索して調べ（ステップＳ３）、存在すれば、第１のキュー２１０の先頭のパケットをその第２のキュー２３０に移動させ、対応するキュー長を＋１する（ステップＳ６）。
【００３３】
また分配部２４０は、上記求めたグループ識別子に対応する第２のキュー２３０が存在しなければ、キュー長が０の第２のキュー２３０が存在するか否かをキュー管理テーブル２５１を検索して調べる（ステップＳ４）。存在すれば、その中の１つの第２のキュー２３０を当該グループ用に使用するために選択し、この選択した第２のキュー２３０のキュー識別子に対応付けて上記先頭のパケットのグループ識別子をキュー管理テーブル２５１に記憶する（ステップＳ５）。そして、第１のキュー２１０の先頭のパケットをその第２のキュー２３０に移動させ、対応するキュー長を＋１する（ステップＳ６）。
【００３４】
また分配部２４０は、キュー長が０の第２のキュー２３０が１つも存在しなければ、キュー長が０の第２のキュー２３０が発生するまで待ち合わせを行う。そして、キュー長が０の第２のキュー２３０が発生すると、分配部２４０は、その発生した第２のキュー２３０のキュー識別子に対応付けて上記先頭のパケットのグループ識別子をキュー管理テーブル２５１に記憶し（ステップＳ５）、第１のキュー２１０の先頭のパケットをその第２のキュー２３０に移動させて、対応するキュー長を＋１する（ステップＳ６）。
【００３５】
分配部２４０は、上述のように或る第２のキュー２３０に１つのパケットを格納すると、その第２のキュー２３０のキュー長が０から１になったか否かを判定する（ステップＳ７）。若し、１になったならば、分配部２４０は、その第２のキューのキュー識別子を処理待ちキューのリスト２５２の最後尾につなぐ（ステップＳ８）。そして、分配部２４０はステップＳ１の処理へと戻る。
【００３６】
図５はパケット処理部２２０の処理の一例を示すフローチャートである。パケット処理部２２０は、処理待ちキューのリスト２５２に１以上の第２のキュー２３０のキュー識別子が存在するか否かを判定する（ステップＳ１１）。若し、存在すれば、パケット処理部２２０は、その先頭につながれている第２のキュー２３０のキュー識別子をリスト２５２から外し、自パケット処理手段による処理対象キューとする（ステップＳ１２）。次にパケット処理部２２０は、処理対象キューとした第２のキュー２３０対応する処理数カウンタを０に初期化する（ステップＳ１３）。処理数カウンタは、例えばパケット処理部２２０内に存在する。
【００３７】
続いてパケット処理部２２０は、処理対象キューの第２のキュー２３０に対応してキュー管理テーブル２５１に記憶されているキュー長が１以上であることを確認し（ステップＳ１４）、処理対象キューの第２のキュー２３０からパケットを１つ取り出して処理し、対応するキュー長を−１、処理数カウンタを＋１する（ステップＳ１５）。次にパケット処理部２２０は、処理数カウンタが予め設定された閾値以上になったか否かを判定する（ステップＳ１６）。未だ閾値以上でないならば、パケット処理部２２０は、ステップＳ１４の処理へと戻る。これにより、処理対象キューの第２のキュー２３０に残りのパケットが存在すれば、そのパケットが処理されることになる。若し、処理対象キューの第２のキュー２３０に残りのパケットが存在しなければ（ステップＳ１４でＮＯ）、この第２のキュー２３０を自パケット処理部による処理対象から外し、ステップＳ１１の処理へと戻る。
【００３８】
パケット処理部２２０は、処理対象キューとした第２のキュー２３０に格納されたパケットを閾値の数だけ処理し終えると（ステップＳ１６でＹＥＳ）、その第２のキュー２３０のキュー長が１以上であるか否か、すなわち未処理のパケットが残っているか否かを判定する（ステップＳ１７）。若し、未処理のパケットが残っていれば、この第２のキュー２３０のキュー識別子を処理待ちキューのリスト２５２の最後尾につなぐ（ステップＳ１８）。そして、この第２のキュー２３０を自パケット処理部による処理対象から外し、ステップＳ１１の処理へと戻る。未処理のパケットが残っていなければ、リスト２５２につなぐことなく、この第２のキュー２３０を自パケット処理部による処理対象から外す。
【００３９】
次に本実施形態の効果を説明する。
【００４０】
本実施形態では、第１の実施形態と同様の理由により、パケットの順序性を保証することができると共に、処理待ちのパケットが存在するにもかかわらず空きのパケット処理部２２０を有効に利用できない状況が長く続くことを防止することができる。
【００４１】
また本実施形態によれば、処理待ちキューのリスト２５２を有するため、パケット処理部２２０は、１以上のパケットが格納されている第２のキュー２３０のうち他のパケット処理部が処理の対象としていないグループのパケットを格納する第２のキュー２３０を探す必要がない。そのため、パケット処理部２２０は、処理を待っている第２のキューに対する処理を直ちに開始でき、スループットを高めることができる。
【００４２】
また本実施形態によれば、パケット処理部２２０は、１つの第２のキュー２２０から一定個数のパケットを処理したら別の第２のキューを処理するため、１つの第２のキュー２２０に１種類のグループのパケットを格納するという構成を採用しながら、パケット処理部２２０の数以上の多数のグループのパケットを並行して処理することができる。
【００４３】
また本実施形態によれば、第２のキュー２２０とグループとの関係を固定せず、動的に対応付けるため、ネットワーク装置２００で扱うグループの最大数以下の数の第２のキューを使用して、全てのグループのパケットの処理が可能になる。
【００４４】
なお、ネットワーク装置２００で処理するパケットのグループが事前に定まっており、グループの数以上の数の第２のキュー２３０が存在する場合、第２のキュー２３０とグループとを事前に１対１に対応付けておいてもよい。すなわち、図３のキュー管理テーブル２５１のキューＩＤとグループＩＤとを事前に設定しておいてもよい。この場合、図４のステップＳ３〜Ｓ５を省略してもよい。
【００４５】
[第３の実施形態]
図６を参照すると、本発明の第３の実施形態にかかるネットワーク装置３００は、第１のキュー３１０と、Ｎ（≧２）個のパケット処理部３２０と、同じくＮ個の第２のキュー３３０と、分配部３４０と、キュー管理テーブル３５０とを有する。
【００４６】
第１のキュー３１０および複数の第２のキュー３３０は、パケットを先入れ先だし方式で格納する機能を有する記憶手段である。第２のキュー３３０とパケット処理部３２０とは１対１に対応付けられている。
【００４７】
キュー管理テーブル３５０は、第２の実施形態におけるキュー管理テーブル２５１と同様に、第２のキュー３３０のキュー識別子に対応付けて、グループ識別子とキュー長とを記憶する。グループとは、例えばセッションである。パケットのグループは、例えばパケットのヘッダ情報に含まれる情報に基づいて決定される。
【００４８】
分配部３４０は、第１のキュー３１０から取り出したパケットを、そのパケットのグループ識別子と同じグループ識別子に対応してキュー管理テーブル３５０に記憶されているキュー識別子で特定される第２のキュー３３０に格納し、対応するキュー長をインクリメントする機能を有する。また、分配部３４０は、第１のキュー３１０から取り出したパケットのグループ識別子と同じグループ識別子に対応するキュー識別子がキュー管理テーブル３５０に記憶されていないときは、第２のキュー３３０のうちキュー長が０の何れか１つの第２のキューに上記パケットを格納し、その格納した第２のキュー３３０のキュー識別子に対応付けて上記格納したパケットのグループ識別子をキュー管理テーブル３５０に記憶する機能を有する。さらに、分配部３４０は、キュー長が０の第２のキュー３３０が１つも存在しない場合には、キュー長が０の第２のキュー３３０が発生するまで待ち合わせを行う機能を有する。
【００４９】
パケット処理部３２０は、対応する第２のキュー３３０に１以上のパケットが存在すれば、パケットを１つずつ取り出して処理し、キュー管理テーブル３５０の対応するキュー長をデクリメントする機能を有する。パケット処理部３２０で処理されたパケットは、例えば図示しない処理済キューに格納してもよいし、それ以外の任意の方法で処理してもよい。
【００５０】
次に本実施形態の動作を説明する。
【００５１】
図７は分配部３４０の処理の一例を示すフローチャートである。処理の対象となるパケットは、第１のキュー３１０に一旦入力され、保持される。分配部３４０は、第１のキュー３１０に１以上のパケットが格納されているか否かを判定し（ステップＳ２１）、格納されていれば、その先頭のパケットのグループ識別子を求める（ステップＳ２２）。
【００５２】
次に分配部３４０は、この求めたグループ識別子に対応する第２のキュー３３０が存在するか否かをキュー管理テーブル３５０を検索して調べ（ステップＳ２３）、存在すれば、第１のキュー３１０の先頭のパケットをその第２のキュー３３０に移動させ、対応するキュー長を＋１する（ステップＳ２６）。そして、分配部３４０はステップＳ２１の処理へと戻る。
【００５３】
また分配部３４０は、上記求めたグループ識別子に対応する第２のキュー３３０が存在しなければ、キュー長が０の第２のキュー３３０が存在するか否かをキュー管理テーブル３５０を検索して調べる（ステップＳ２４）。存在すれば、その中の１つの第２のキュー３３０を当該グループ用に使用するために選択し、この選択した第２のキュー３３０のキュー識別子に対応付けて上記先頭のパケットのグループ識別子をキュー管理テーブル３５０に記憶する（ステップＳ２５）。次に、第１のキュー３１０の先頭のパケットをその第２のキュー３３０に移動させ、対応するキュー長を＋１する（ステップＳ２６）。そして、分配部３４０はステップＳ２１の処理へと戻る。
【００５４】
また分配部３４０は、キュー長が０の第２のキュー３３０が１つも存在しなければ、キュー長が０の第２のキュー３３０が発生するまで待ち合わせを行う（ステップＳ２４）。そして、キュー長が０の第２のキュー３３０が発生すると、分配部３４０は、その発生した第２のキュー３３０のキュー識別子に対応付けて上記先頭のパケットのグループ識別子をキュー管理テーブル３５０に記憶し（ステップＳ２５）、第１のキュー３１０の先頭のパケットをその第２のキュー３３０に移動させて、対応するキュー長を＋１する（ステップＳ２６）。そして、分配部３４０はステップＳ２１の処理へと戻る。
【００５５】
図８はパケット処理部３２０の処理の一例を示すフローチャートである。パケット処理部３２０は、自パケット処理手段による対応する第２のキュー３３０のキュー長が１以上であるか否かを確認する（ステップＳ３１）。次に、パケット処理部３２０は、キュー長が１以上であれば、対応する第２のキュー２３０からパケットを１つ取り出して処理し、対応するキュー長を−１する（ステップＳ３２）。そして、パケット処理部３２０はステップＳ３１の処理へと戻る。
【００５６】
次に本実施形態の効果を説明する。
【００５７】
本実施形態では、第１の実施形態と同様の理由により、パケットの順序性を保証することができると共に、処理待ちのパケットが存在するにもかかわらず空きのパケット処理部３２０を有効に利用できない状況が長く続くことを防止することができる。
【００５８】
また本実施形態によれば、第２のキュー３２０とグループとの関係を固定せず、動的に対応付けるため、パケット処理部３２０と同じ数の第２のキュー３２０を使用して、全てのグループのパケットの処理が可能になる。
【００５９】
[第４の実施形態]
図９を参照すると、本発明の第４の実施形態としてのマルチコアプロセッサ上の論理プロセッサを使用したネットワーク装置が示されている。
【００６０】
図９において、1230は、受信したパケットが順に格納されるキュー、1220は1230に格納されたパケットを取り出し、セッション（グループ）（以下、単にセッションと記す）別のキューに分配処理を行うデバイス（または論理プロセッサ)、1210〜1215は、セッション別のキュー、1200〜1203は、論理プロセッサである。セッション数は、論理プロセッサ数よりも十分に大きな値（例えば、論理プロセッサ数：32に対し、セッション数：20,000など、二桁の差があるなど）を想定するが、説明を容易とするため、例では６つで説明する。また、論理プロセッサは、32、64など多数を想定するが、説明を容易とするため例では、４つで説明する。
【００６１】
1220の分配処理を行うデバイスは、単純な分配であれば、受信デバイス付属の分配機能を利用して分配を行う。複雑な条件による分配を行う場合には、論理プロセッサを使用することで分配が可能となる。
【００６２】
次に、本実施形態の動作を説明する。図９において、受信デバイスがパケットを受信すると、1230で示される受信デバイス用のキューに格納される。分配処理を行うデバイス1220（または論理プロセッサ）は、受信デバイス用のキュー1230からパケットを取り出し、指定されたセッションの定義に従い、セッション毎のキュー1210〜1215に分配する。セッションの定義は、例えば、タイプ（IPv4/IPv6/など）、宛先IPアドレス、送信元IPアドレス、プロトコル（TCP/UDP/など）、宛先ポート番号、送信元ポート番号を使用する。
【００６３】
セッション毎のキュー1210〜1215にパケットが格納された後、1200〜1203の論理プロセッサは、パケット処理対象のキューからパケットを取り出しパケット処理を行う。
【００６４】
図１０を参照して、論理プロセッサがパケット処理対象のキューを選択するしくみを説明する。図１０において、1321は、キュー長（キュー内パケット数）が0のキュー、1311は、キュー長が１以上の、受信処理待ちキューのリスト、1300〜1303は、論理プロセッサとその論理プロサッサにて処理されているキューの組である。
【００６５】
受信パケットは、分配処理を行うデバイスにより1321のセッション毎のキューに分配され格納される（1351）。この時、キュー長（キュー内のパケット数）が0から1以上に変化した場合にはキューは処理対象キューリスト1311の最後につながれる（1352）。
【００６６】
論理プロセッサ1300〜1303は、パケット処理対象のキューリストの先頭を確認し、キューがあればキューリストからキューを外す。論理プロセッサ1300がキューリストからキュー1390を外し、論理プロセッサ1300処理用のキューとする動作を、1361にて示している。
【００６７】
次に、論理プロセッサ1300〜1303は、キューからパケットを取り出し、パケット処理を行う。論理プロセッサ1300がキュー1390からパケットを取り出し、処理する動作を1371にて示している。パケット処理後、キューにさらにパケットがあれば取り出し、パケット処理を行う。キュー1390にパケットがなくなれば、処理を終えキューを論理プロセッサの処理キュー組み合わせから外す（1381）。キューは1321に戻ることと同じ扱いとなる。
【００６８】
論理プロセッサは、再度パケット処理対象のキューリスト1311の先頭を確認し、キューリストにキューがあれば、1361と同様に論理プロセッサ1300処理用キューとしパケット処理を行う。
【００６９】
また論理プロセッサは、パケット処理後、キューにパケットがある場合にも、特定の個数のパケットを処理した場合には、連続してパケット処理を行わず、キューをパケット処理対象のキューリスト1311の最後につなぐ。例えば特定の個数を４とした場合、1301では、キュー1391の５つ目のパケット処理は連続して行わず、キュー1391を一度1311のキューリストへ戻す（1382）。
【００７０】
このように本実施形態においては、以下に記載するような効果を奏する。
【００７１】
第１の効果は、セッションが同一のパケットはひとつの論理プロセッサで処理されるため、順序性が保証されることである。また、排他制御による待ちがなくなり、論理プロセッサが並列処理できるため、性能が向上する。
【００７２】
第２の効果は、論理プロセッサがひとつのキューから連続処理する数の上限値に達したら、次のキューを処理するため、論理プロセッサ数に縛られることなく、多数のセッションを処理できることである。
【００７３】
第３の効果は、論理プロセッサとセッションを固定で括りつけず、どの論理プロセッサでもどのセッションのキューを処理できるため、受信するパケットが一部のセッションに偏っていたとしても、処理（CPU使用率）に偏りが発生せず、平均的なパフォーマンスが発揮できることである。
【００７４】
第４の効果は、処理対象キューリストを用意することで、論理プロセッサが処理すべきキューを探す必要がなくなり、性能が向上することである。これによって、より効率的に第２の効果と第３の効果を発揮できることである。
【００７５】
[第5の実施形態]
本発明の第５の実施形態の構成を図１１に示す。図１１において、1430は、受信したパケットが順に格納されるキュー、1420は1430に格納されたパケットを取り出し、セッション別のキューに分配処理を行うデバイス（または論理プロセッサ）、1440は、1420がセッションを検索する際に利用されるCAM（Content Addressable Memory）、1410〜1413は、セッション別のキュー、1400〜1403は、論理プロセッサである。
【００７６】
本実施形態では、1410〜1413のセッション別のキューの個数は、1400〜1403の論理プロセッサの個数と同一とし、分配デバイス（論理プロセッサ）との組み合わせとする。
【００７７】
次に、本実施形態の動作を説明する。その基本的動作は、図９と同様であるが、本実施形態ではセッションの検索にCAMを用いる。CAMには、セッションを決定するキーを事前に設定する。
【００７８】
図１１において、デバイスがパケットを受信すると、1430で示される受信デバイス用のキューに格納される。分配処理を行うデバイス1420（または論理プロセッサ）は、受信デバイス用のキュー1430に格納されたパケットから、CAMを利用してセッション（グループ）を決定する。CAMの一般的な動作として、検索にヒットしたインデックスを得る。CAMの動作は一般的なものなのでここでは説明しない。
【００７９】
CAMにて取得したインデックスと同一のインデックスのパケットを処理しているキュー1410〜1413があれば、受信デバイス用のキューからパケットを取り出し、インデックスが一致しているキューに格納する。インデックスが一致したキューがなく、さらにインデックスと関連付けされていないキューがある場合には、キューにインデックスを関連付け、受信デバイス用のキューからパケットをとりだし、そのパケットをインデックスが一致しているキューに格納する。インデックスが一致したキューがなく、全てのキューがインデックスと関連付けられている場合には、受信デバイスのキューからパケットの取り出しを保留する。
【００８０】
CAMにはインデックス値を持った処理キューへ繋いだパケットカウンタを持ち、この値が閾値（連続処理してよいパケット数を事前に設定）を超えた場合には、処理キューへ積まず保留させる。これにより連続して同じセッション（グループ）のパケットばかりが処理されないように処理を分散させる。
【００８１】
1410-1413の論理プロセッサは、自身が処理するキューが空になるもしくは閾値を超えると処理キューから自身が処理するインデックスを削除し、分配デバイス（論理プロセッサ）に通知する。分配デバイス（論理プロセッサ）1420は保留を解除する。
【００８２】
こうすることで、CAMを利用した高速検索を可能とし、論理プロセッサに関連づけた処理キューを効率的に使用しながらセッション（グループ）毎の並列処理を可能とする。
【００８３】
[その他の実施形態]
図１１のキュー1430中のパケットe-1,d-2に示すように、対応するセッション（グループ）用の第２のキューが存在しないために処理が保留されているパケットe-1を飛び越えて、対応するセッション（グループ）用の第２のキューが存在する後続のパケットd-2を第２のキューに格納するようにしてもよい。
【００８４】
更に他の例を説明する。図９〜図１１にての説明は、受信パケットについてであるが、送信パケットや再送タイマーのタイムアウト処理などのイベントについても、セッションと対応させることで、同一セッションを同一の論理プロセッサで処理することが出来、送信/受信/タイマー各処理で共有するべき状態情報などへの排他制御を不要とすることで、並列性を向上させることができる。
【００８５】
更に他の例としては、セッションの定義を拡大し、複数のセッションを同一グループと扱うことで、処理アプリケーション全体での排他制御を減らす（なくす）ことができる。
【００８６】
更に他の例では、パケットのネットワーク（プロトコル）部分の処理と、アプリケーション部分で排他制御の範囲が異なる場合には、ネットワーク部とアプリケーション部を処理する論理プロセッサを分割し、受け渡し部分に本発明を適用すれば、ネットワーク部とアプリケーション部で異なるポリシーの分配による並列処理を実施することができる。
【００８７】
また、本発明のネットワーク装置は、その有する機能をハードウェアで実現することは勿論、コンピュータとプログラムで実現することができる。プログラムは、磁気ディスクや半導体メモリなどのコンピュータ読み取り可能な記録媒体に記録されて提供され、コンピュータの立ち上げ時などにコンピュータに読み取られ、そのコンピュータの動作を制御することにより、そのコンピュータを前述した各実施形態における分配手段やパケット処理部として機能させる。
【符号の説明】
【００８８】
１００…ネットワーク装置
１１０…第1のキュー
１２０…パケット処理部
１３０…第2のキュー
１４０…分配部
【図１】
2012209695.tif 000003
【図２】
2012209695.tif 000004
【図３】
2012209695.tif 000005
【図４】
2012209695.tif 000006
【図５】
2012209695.tif 000007
【図６】
2012209695.tif 000008
【図７】
2012209695.tif 000009
【図８】
2012209695.tif 000010
【図９】
2012209695.tif 000011
【図１０】
2012209695.tif 000012
【図１１】
2012209695.tif 000013
【図１２】
2012209695.tif 000014
【図１３】
2012209695.tif 000015