ネットワーク装置
【課題】処理待ちのパケットが存在するにもかかわらず空きのパケット処理部を有効に利用できない状況が長く続く可能性が高いこと。
【解決手段】ネットワーク装置100は、第1のキュー110と、複数の第2のキュー130と、分配部140と、複数のパケット処理部120とを有する。分配部140は、第1のキュー110から取り出したパケットを、そのパケットのグループ以外のグループのパケットが格納されていない第2のキュー130に格納する。複数のパケット処理部120は、1以上のパケットが格納されている第2のキュー130のうち、他のパケット処理部が処理の対象としていないグループのパケットを格納する第2のキュー130からパケットを取り出して処理を行う。
【解決手段】ネットワーク装置100は、第1のキュー110と、複数の第2のキュー130と、分配部140と、複数のパケット処理部120とを有する。分配部140は、第1のキュー110から取り出したパケットを、そのパケットのグループ以外のグループのパケットが格納されていない第2のキュー130に格納する。複数のパケット処理部120は、1以上のパケットが格納されている第2のキュー130のうち、他のパケット処理部が処理の対象としていないグループのパケットを格納する第2のキュー130からパケットを取り出して処理を行う。
【発明の詳細な説明】
【技術分野】
【0001】
本発明はネットワーク装置に関し、特に複数のパケット処理部を使用してパケットを並列に処理するネットワーク装置に関する。
【背景技術】
【0002】
この種のネットワーク装置の一例が特許文献1に記載されている。特許文献1に記載されたネットワーク装置(以下、本発明に関連するネットワーク装置と言う)は、パケットを受信順に記憶する第1のキューと、複数のパケット処理部と、このパケット処理部に1対1に対応する第2のキューと、パケット振り分け部と、振り分け情報テーブルと、複数のパケット処理部の負荷状態を定期的に収集する統計情報収集部とを有する。このような構成を有するネットワーク装置は、以下のように動作する。
【0003】
振り分け情報テーブルには、ハッシュ値とパケット処理部とカウンタとの組が記憶されている。ここで、ハッシュ値はパケットが属するグループを特定する情報である。特許文献1では、グループとしてフローを使用する。パケット振り分け部は、第1のキューからパケットを取り出し、そのパケットのヘッダ情報から計算したハッシュ値と同じハッシュ値に対応して上記振り分け情報テーブルに記憶されているパケット処理部に対応する第2のキューに格納し、対応するカウンタを+1する。各パケット処理部は、対応する第2のキューからパケットを取り出して処理を行い、振り分け情報テーブル上の対応するカウントを−1する。
【0004】
またパケット振り分け部は、統計情報収集部で収集された各パケット処理部の負荷状態を参照して、最も負荷の少ないパケット処理部に特定のグループのパケットを振り分けるべく、振り分け情報テーブル中のハッシュ値とパケット処理部との対応関係を更新する。このパケット振り分け先の変更は、何れの第2のキューにも上記特定のグループのパケットが存在していないタイミングを捉えて実施される。
【先行技術文献】
【特許文献】
【0005】
【特許文献1】特開2010−161546号公報
【発明の概要】
【発明が解決しようとする課題】
【0006】
上述した本発明に関連するネットワーク装置は、同じグループのパケットを同じパケット処理部で処理するようにしており、また特定のグループの振り分け先を変更する際にはそのグループのパケットが何れの第2のキューにも格納されていないタイミングを捉えて実施するため、グループ内でのパケットの順序の逆転は発生しない。
【0007】
しかしながら、上述した本発明に関連するネットワーク装置は、同じキューに複数のグループのパケットを混在させているため、処理待ちのパケットが存在するにもかかわらず空きのパケット処理部を有効に利用できない状況が長い時間続く可能性が高い。
【0008】
例えば、図12および図13において、A〜Dの4つのグループを想定し、各々のグループA〜Dのパケットをa〜dとする。また図12に示すように、グループAとグループBは第1のパケット処理部で処理し、グループCとグループDは第2のパケット処理部で処理するようにグループの振り分け先が設定されているとする。このとき、グループA〜Dのパケットがその後も継続して入力されるならば、2つのパケット処理部は空き状態になることはない。しかし、グループAとグループBのパケットがその後も継続して入力される一方、グループCとグループDのパケットが全く途絶えると、図13に示すように、第2のパケット処理部に対応するキューは空になり、第2のパケット処理部は空き状態になる。このとき、グループAとグループBのパケットはその後も継続して第1のパケット処理部に対応するキューに入力され続けるため、グループAまたはグループBの何れか一方のグループの振り分け先を第1のパケット処理部から第2のパケット処理部に変更することはできない。従って、空いている第2のパケット処理部を有効に利用できない状態が長く続くことになる。
【0009】
本発明の目的は、上述した課題、すなわち、処理待ちのパケットが存在するにもかかわらず空きのパケット処理部を有効に利用できない状況が長く続く可能性が高い、という課題を解決するネットワーク装置を提供することにある。
【課題を解決するための手段】
【0010】
本発明の一形態にかかるネットワーク装置は、
第1のキューと、
複数の第2のキューと、
前記第1のキューから取り出したパケットを、そのパケットのグループ以外のグループのパケットが格納されていない前記第2のキューに格納する分配手段と、
1以上の前記パケットが格納されている前記第2のキューのうち他のパケット処理手段が処理の対象としていないグループのパケットを格納する前記第2のキューからパケットを取り出して処理を行う複数のパケット処理手段と
を有する、といった構成を採る。
【発明の効果】
【0011】
本発明は上述したような構成を有するため、処理待ちのパケットが存在するにもかかわらず空きのパケット処理部を有効に利用できない状況が長く続くことを防止でき、パケット処理部の有効利用が可能になる。
【図面の簡単な説明】
【0012】
【図1】本発明の第1の実施形態のブロック図である。
【図2】本発明の第2の実施形態のブロック図である。
【図3】本発明の第2の実施形態における管理情報記憶部の構成例を示す図である。
【図4】本発明の第2の実施形態における分配部の処理を示すフローチャートである。
【図5】本発明の第2の実施形態におけるパケット処理部の処理を示すフローチャートである。
【図6】本発明の第3の実施形態のブロック図である。
【図7】本発明の第3の実施形態における分配部の処理を示すフローチャートである。
【図8】本発明の第3の実施形態におけるパケット処理部の処理を示すフローチャートである。
【図9】本発明の第4の実施形態のブロック図である。
【図10】本発明の第4の実施形態の動作説明図である。
【図11】本発明の第5の実施形態のブロック図である。
【図12】本発明に関連するネットワーク装置の動作説明図である。
【図13】本発明に関連するネットワーク装置の動作説明図である。
【発明を実施するための形態】
【0013】
次に本発明の実施の形態について図面を参照して詳細に説明する。
[第1の実施形態]
図1を参照すると、本発明の第1の実施形態にかかるネットワーク装置100は、第1のキュー110と、N(≧2)個のパケット処理部120と、M(≧N)個の第2のキュー130と、分配部140とを有する。
【0014】
第1のキュー110および複数の第2のキュー130は、パケットを先入れ先だし方式で格納する機能を有する記憶手段である。
【0015】
分配部140は、第1のキュー110から取り出したパケットを、そのパケットのグループ以外のグループのパケットが格納されていない第2のキュー130に格納する機能を有する。グループとは、例えばセッションである。パケットのグループは、例えばパケットのヘッダ情報に含まれる情報に基づいて決定される。
【0016】
パケット処理部120は、1以上のパケットが格納されている第2のキュー130のうち、他のパケット処理部120が処理の対象としていないグループのパケットを格納する第2のキュー130からパケットを取り出して処理を行う機能を有する。パケット処理部120で処理されたパケットは、例えば図示しない処理済キューに格納してもよいし、それ以外の任意の方法で処理してもよい。
【0017】
次に本実施形態の動作を説明する。
【0018】
処理の対象となるパケットは、第1のキュー110に一旦入力され、保持される。分配部140は、第1のキュー110に格納されたパケットを入力順に取り出し、そのパケットのグループを認識する。そして分配部140は、複数の第2のキュー120のうち、認識したグループ以外のグループのパケットが格納されていない第2のキュー130に上記のパケットを格納する。若し、そのような第2のキューが存在しなければ、そのような第2のキューが生じるまで処理を保留する。
【0019】
それぞれのパケット処理部120は、1以上のパケットが格納されている第2のキュー130のうち、他のパケット処理部120が処理の対象としていないグループのパケットを格納する第2のキュー130からパケットを取り出して処理を行う。それぞれのパケット処理部120は、同時には1つの第2のキュー130を処理の対象とする。
【0020】
次に本実施形態の効果を説明する。
【0021】
本実施形態では、1つの第2のキュー130には、1つのグループのパケットしか格納されない。また、複数のパケット処理部120が同じ第2のキュー130を同時に処理対象とすることはない。これにより、第1のキュー110に格納されているパケットの順序とパケット処理部120で処理されて出力されるパケットの順序とは、同じグループのパケット間で同じになる。すなわち、パケットの順序性を保証することができる。
【0022】
また本実施形態によれば、処理待ちのパケットが存在するにもかかわらず空きのパケット処理部120を有効に利用できない状況が長く続くことを防止でき、パケット処理部120の有効利用が可能になる。その理由は、空きの生じたパケット処理部120に処理待ちのパケットを投入できない状況が続くのは、第1のキュー110から次に取り出すパケットが、他のパケット処理部120で現在処理されているグループと同じグループの場合であるが、そのような状況になる確率は、1つの第2のキュー130に1つのグループしか格納しない方が、1つの第2のキュー130に複数のグループを混在させて格納するよりも小さくなるためである。特に本実施形態によれば、ネットワーク装置100で処理されるパケットのグループの数がパケット処理部120の数まで低下した場合、必ず、1つのパケット処理部120で1つのグループのパケットが処理される状態になるため、図13に示したような空きの第2のパケット処理部が発生することはない。
【0023】
[第2の実施形態]
図2を参照すると、本発明の第2の実施形態にかかるネットワーク装置200は、第1のキュー210と、N(≧2)個のパケット処理部220と、M(>N)個の第2のキュー230と、分配部240と、管理情報記憶部250とを有する。
【0024】
第1のキュー210および複数の第2のキュー230は、パケットを先入れ先だし方式で格納する機能を有する記憶手段である。
【0025】
管理情報記憶部250は、図3に示すように、キュー管理テーブル251と処理待ちキューのリスト252とから構成される。
【0026】
キュー管理テーブル251は、第2のキュー230のキュー識別子に対応付けて、グループ識別子とキュー長とを記憶する。グループとは、例えばセッションである。パケットのグループは、例えばパケットのヘッダ情報に含まれる情報に基づいて決定される。
【0027】
リスト252は、キュー長が1以上の第2のキュー230のリストである。
【0028】
分配部240は、第1のキュー210から取り出したパケットを、そのパケットのグループ識別子と同じグループ識別子に対応してキュー管理テーブル251に記憶されているキュー識別子で特定される第2のキュー230に格納し、対応するキュー長をインクリメントする機能を有する。また、分配部240は、第1のキュー210から取り出したパケットのグループ識別子と同じグループ識別子に対応するキュー識別子がキュー管理テーブル251に記憶されていないときは、第2のキュー230のうちキュー長が0の何れか1つの第2のキューに上記パケットを格納し、その格納した第2のキュー230のキュー識別子に対応付けて上記格納したパケットのグループ識別子をキュー管理テーブル251に記憶する機能を有する。さらに、分配部240は、キュー長が0の第2のキュー230が1つも存在しない場合には、キュー長が0の第2のキュー230が発生するまで待ち合わせを行う機能を有する。また分配部240は、パケットを格納することによってキュー長が1になった第2のキュー230のキュー識別子を、処理待ちキューのリスト252の最後尾につなぐ機能を有する。
【0029】
パケット処理部220は、空きが生じたときにリスト252の先頭につながれているキュー識別子を外して、この外したキュー識別子で特定される第2のキュー230を自パケット処理手段による処理の対象とする機能を有する。またパケット処理部220は、処理対象の第2のキュー230からパケットを取り出して処理し、キュー管理テーブル251の対応するキュー長をデクリメントする機能を有する。さらに、パケット処理部220は、自パケット処理手段が処理の対象としている第2のキュー230から連続して閾値の数だけのパケットを取り出して処理し終えた時点で、この第2のキュー230を処理の対象から外し、その第2のキュー230のキュー長が1以上であればそのキュー識別子をリスト252の最後尾につなぐ機能を有する。パケット処理部220で処理されたパケットは、例えば図示しない処理済キューに格納してもよいし、それ以外の任意の方法で処理してもよい。
【0030】
次に本実施形態の動作を説明する。
【0031】
図4は分配部240の処理の一例を示すフローチャートである。処理の対象となるパケットは、第1のキュー210に一旦入力され、保持される。分配部240は、第1のキュー210に1以上のパケットが格納されているか否かを判定し(ステップS1)、格納されていれば、その先頭のパケットのグループ識別子を求める(ステップS2)。
【0032】
次に分配部240は、この求めたグループ識別子に対応する第2のキュー230が存在するか否かをキュー管理テーブル251を検索して調べ(ステップS3)、存在すれば、第1のキュー210の先頭のパケットをその第2のキュー230に移動させ、対応するキュー長を+1する(ステップS6)。
【0033】
また分配部240は、上記求めたグループ識別子に対応する第2のキュー230が存在しなければ、キュー長が0の第2のキュー230が存在するか否かをキュー管理テーブル251を検索して調べる(ステップS4)。存在すれば、その中の1つの第2のキュー230を当該グループ用に使用するために選択し、この選択した第2のキュー230のキュー識別子に対応付けて上記先頭のパケットのグループ識別子をキュー管理テーブル251に記憶する(ステップS5)。そして、第1のキュー210の先頭のパケットをその第2のキュー230に移動させ、対応するキュー長を+1する(ステップS6)。
【0034】
また分配部240は、キュー長が0の第2のキュー230が1つも存在しなければ、キュー長が0の第2のキュー230が発生するまで待ち合わせを行う。そして、キュー長が0の第2のキュー230が発生すると、分配部240は、その発生した第2のキュー230のキュー識別子に対応付けて上記先頭のパケットのグループ識別子をキュー管理テーブル251に記憶し(ステップS5)、第1のキュー210の先頭のパケットをその第2のキュー230に移動させて、対応するキュー長を+1する(ステップS6)。
【0035】
分配部240は、上述のように或る第2のキュー230に1つのパケットを格納すると、その第2のキュー230のキュー長が0から1になったか否かを判定する(ステップS7)。若し、1になったならば、分配部240は、その第2のキューのキュー識別子を処理待ちキューのリスト252の最後尾につなぐ(ステップS8)。そして、分配部240はステップS1の処理へと戻る。
【0036】
図5はパケット処理部220の処理の一例を示すフローチャートである。パケット処理部220は、処理待ちキューのリスト252に1以上の第2のキュー230のキュー識別子が存在するか否かを判定する(ステップS11)。若し、存在すれば、パケット処理部220は、その先頭につながれている第2のキュー230のキュー識別子をリスト252から外し、自パケット処理手段による処理対象キューとする(ステップS12)。次にパケット処理部220は、処理対象キューとした第2のキュー230対応する処理数カウンタを0に初期化する(ステップS13)。処理数カウンタは、例えばパケット処理部220内に存在する。
【0037】
続いてパケット処理部220は、処理対象キューの第2のキュー230に対応してキュー管理テーブル251に記憶されているキュー長が1以上であることを確認し(ステップS14)、処理対象キューの第2のキュー230からパケットを1つ取り出して処理し、対応するキュー長を−1、処理数カウンタを+1する(ステップS15)。次にパケット処理部220は、処理数カウンタが予め設定された閾値以上になったか否かを判定する(ステップS16)。未だ閾値以上でないならば、パケット処理部220は、ステップS14の処理へと戻る。これにより、処理対象キューの第2のキュー230に残りのパケットが存在すれば、そのパケットが処理されることになる。若し、処理対象キューの第2のキュー230に残りのパケットが存在しなければ(ステップS14でNO)、この第2のキュー230を自パケット処理部による処理対象から外し、ステップS11の処理へと戻る。
【0038】
パケット処理部220は、処理対象キューとした第2のキュー230に格納されたパケットを閾値の数だけ処理し終えると(ステップS16でYES)、その第2のキュー230のキュー長が1以上であるか否か、すなわち未処理のパケットが残っているか否かを判定する(ステップS17)。若し、未処理のパケットが残っていれば、この第2のキュー230のキュー識別子を処理待ちキューのリスト252の最後尾につなぐ(ステップS18)。そして、この第2のキュー230を自パケット処理部による処理対象から外し、ステップS11の処理へと戻る。未処理のパケットが残っていなければ、リスト252につなぐことなく、この第2のキュー230を自パケット処理部による処理対象から外す。
【0039】
次に本実施形態の効果を説明する。
【0040】
本実施形態では、第1の実施形態と同様の理由により、パケットの順序性を保証することができると共に、処理待ちのパケットが存在するにもかかわらず空きのパケット処理部220を有効に利用できない状況が長く続くことを防止することができる。
【0041】
また本実施形態によれば、処理待ちキューのリスト252を有するため、パケット処理部220は、1以上のパケットが格納されている第2のキュー230のうち他のパケット処理部が処理の対象としていないグループのパケットを格納する第2のキュー230を探す必要がない。そのため、パケット処理部220は、処理を待っている第2のキューに対する処理を直ちに開始でき、スループットを高めることができる。
【0042】
また本実施形態によれば、パケット処理部220は、1つの第2のキュー220から一定個数のパケットを処理したら別の第2のキューを処理するため、1つの第2のキュー220に1種類のグループのパケットを格納するという構成を採用しながら、パケット処理部220の数以上の多数のグループのパケットを並行して処理することができる。
【0043】
また本実施形態によれば、第2のキュー220とグループとの関係を固定せず、動的に対応付けるため、ネットワーク装置200で扱うグループの最大数以下の数の第2のキューを使用して、全てのグループのパケットの処理が可能になる。
【0044】
なお、ネットワーク装置200で処理するパケットのグループが事前に定まっており、グループの数以上の数の第2のキュー230が存在する場合、第2のキュー230とグループとを事前に1対1に対応付けておいてもよい。すなわち、図3のキュー管理テーブル251のキューIDとグループIDとを事前に設定しておいてもよい。この場合、図4のステップS3〜S5を省略してもよい。
【0045】
[第3の実施形態]
図6を参照すると、本発明の第3の実施形態にかかるネットワーク装置300は、第1のキュー310と、N(≧2)個のパケット処理部320と、同じくN個の第2のキュー330と、分配部340と、キュー管理テーブル350とを有する。
【0046】
第1のキュー310および複数の第2のキュー330は、パケットを先入れ先だし方式で格納する機能を有する記憶手段である。第2のキュー330とパケット処理部320とは1対1に対応付けられている。
【0047】
キュー管理テーブル350は、第2の実施形態におけるキュー管理テーブル251と同様に、第2のキュー330のキュー識別子に対応付けて、グループ識別子とキュー長とを記憶する。グループとは、例えばセッションである。パケットのグループは、例えばパケットのヘッダ情報に含まれる情報に基づいて決定される。
【0048】
分配部340は、第1のキュー310から取り出したパケットを、そのパケットのグループ識別子と同じグループ識別子に対応してキュー管理テーブル350に記憶されているキュー識別子で特定される第2のキュー330に格納し、対応するキュー長をインクリメントする機能を有する。また、分配部340は、第1のキュー310から取り出したパケットのグループ識別子と同じグループ識別子に対応するキュー識別子がキュー管理テーブル350に記憶されていないときは、第2のキュー330のうちキュー長が0の何れか1つの第2のキューに上記パケットを格納し、その格納した第2のキュー330のキュー識別子に対応付けて上記格納したパケットのグループ識別子をキュー管理テーブル350に記憶する機能を有する。さらに、分配部340は、キュー長が0の第2のキュー330が1つも存在しない場合には、キュー長が0の第2のキュー330が発生するまで待ち合わせを行う機能を有する。
【0049】
パケット処理部320は、対応する第2のキュー330に1以上のパケットが存在すれば、パケットを1つずつ取り出して処理し、キュー管理テーブル350の対応するキュー長をデクリメントする機能を有する。パケット処理部320で処理されたパケットは、例えば図示しない処理済キューに格納してもよいし、それ以外の任意の方法で処理してもよい。
【0050】
次に本実施形態の動作を説明する。
【0051】
図7は分配部340の処理の一例を示すフローチャートである。処理の対象となるパケットは、第1のキュー310に一旦入力され、保持される。分配部340は、第1のキュー310に1以上のパケットが格納されているか否かを判定し(ステップS21)、格納されていれば、その先頭のパケットのグループ識別子を求める(ステップS22)。
【0052】
次に分配部340は、この求めたグループ識別子に対応する第2のキュー330が存在するか否かをキュー管理テーブル350を検索して調べ(ステップS23)、存在すれば、第1のキュー310の先頭のパケットをその第2のキュー330に移動させ、対応するキュー長を+1する(ステップS26)。そして、分配部340はステップS21の処理へと戻る。
【0053】
また分配部340は、上記求めたグループ識別子に対応する第2のキュー330が存在しなければ、キュー長が0の第2のキュー330が存在するか否かをキュー管理テーブル350を検索して調べる(ステップS24)。存在すれば、その中の1つの第2のキュー330を当該グループ用に使用するために選択し、この選択した第2のキュー330のキュー識別子に対応付けて上記先頭のパケットのグループ識別子をキュー管理テーブル350に記憶する(ステップS25)。次に、第1のキュー310の先頭のパケットをその第2のキュー330に移動させ、対応するキュー長を+1する(ステップS26)。そして、分配部340はステップS21の処理へと戻る。
【0054】
また分配部340は、キュー長が0の第2のキュー330が1つも存在しなければ、キュー長が0の第2のキュー330が発生するまで待ち合わせを行う(ステップS24)。そして、キュー長が0の第2のキュー330が発生すると、分配部340は、その発生した第2のキュー330のキュー識別子に対応付けて上記先頭のパケットのグループ識別子をキュー管理テーブル350に記憶し(ステップS25)、第1のキュー310の先頭のパケットをその第2のキュー330に移動させて、対応するキュー長を+1する(ステップS26)。そして、分配部340はステップS21の処理へと戻る。
【0055】
図8はパケット処理部320の処理の一例を示すフローチャートである。パケット処理部320は、自パケット処理手段による対応する第2のキュー330のキュー長が1以上であるか否かを確認する(ステップS31)。次に、パケット処理部320は、キュー長が1以上であれば、対応する第2のキュー230からパケットを1つ取り出して処理し、対応するキュー長を−1する(ステップS32)。そして、パケット処理部320はステップS31の処理へと戻る。
【0056】
次に本実施形態の効果を説明する。
【0057】
本実施形態では、第1の実施形態と同様の理由により、パケットの順序性を保証することができると共に、処理待ちのパケットが存在するにもかかわらず空きのパケット処理部320を有効に利用できない状況が長く続くことを防止することができる。
【0058】
また本実施形態によれば、第2のキュー320とグループとの関係を固定せず、動的に対応付けるため、パケット処理部320と同じ数の第2のキュー320を使用して、全てのグループのパケットの処理が可能になる。
【0059】
[第4の実施形態]
図9を参照すると、本発明の第4の実施形態としてのマルチコアプロセッサ上の論理プロセッサを使用したネットワーク装置が示されている。
【0060】
図9において、1230は、受信したパケットが順に格納されるキュー、1220は1230に格納されたパケットを取り出し、セッション(グループ)(以下、単にセッションと記す)別のキューに分配処理を行うデバイス(または論理プロセッサ)、1210〜1215は、セッション別のキュー、1200〜1203は、論理プロセッサである。セッション数は、論理プロセッサ数よりも十分に大きな値(例えば、論理プロセッサ数:32に対し、セッション数:20,000など、二桁の差があるなど)を想定するが、説明を容易とするため、例では6つで説明する。また、論理プロセッサは、32、64など多数を想定するが、説明を容易とするため例では、4つで説明する。
【0061】
1220の分配処理を行うデバイスは、単純な分配であれば、受信デバイス付属の分配機能を利用して分配を行う。複雑な条件による分配を行う場合には、論理プロセッサを使用することで分配が可能となる。
【0062】
次に、本実施形態の動作を説明する。図9において、受信デバイスがパケットを受信すると、1230で示される受信デバイス用のキューに格納される。分配処理を行うデバイス1220(または論理プロセッサ)は、受信デバイス用のキュー1230からパケットを取り出し、指定されたセッションの定義に従い、セッション毎のキュー1210〜1215に分配する。セッションの定義は、例えば、タイプ(IPv4/IPv6/など)、宛先IPアドレス、送信元IPアドレス、プロトコル(TCP/UDP/など)、宛先ポート番号、送信元ポート番号を使用する。
【0063】
セッション毎のキュー1210〜1215にパケットが格納された後、1200〜1203の論理プロセッサは、パケット処理対象のキューからパケットを取り出しパケット処理を行う。
【0064】
図10を参照して、論理プロセッサがパケット処理対象のキューを選択するしくみを説明する。図10において、1321は、キュー長(キュー内パケット数)が0のキュー、1311は、キュー長が1以上の、受信処理待ちキューのリスト、1300〜1303は、論理プロセッサとその論理プロサッサにて処理されているキューの組である。
【0065】
受信パケットは、分配処理を行うデバイスにより1321のセッション毎のキューに分配され格納される(1351)。この時、キュー長(キュー内のパケット数)が0から1以上に変化した場合にはキューは処理対象キューリスト1311の最後につながれる(1352)。
【0066】
論理プロセッサ1300〜1303は、パケット処理対象のキューリストの先頭を確認し、キューがあればキューリストからキューを外す。論理プロセッサ1300がキューリストからキュー1390を外し、論理プロセッサ1300処理用のキューとする動作を、1361にて示している。
【0067】
次に、論理プロセッサ1300〜1303は、キューからパケットを取り出し、パケット処理を行う。論理プロセッサ1300がキュー1390からパケットを取り出し、処理する動作を1371にて示している。パケット処理後、キューにさらにパケットがあれば取り出し、パケット処理を行う。キュー1390にパケットがなくなれば、処理を終えキューを論理プロセッサの処理キュー組み合わせから外す(1381)。キューは1321に戻ることと同じ扱いとなる。
【0068】
論理プロセッサは、再度パケット処理対象のキューリスト1311の先頭を確認し、キューリストにキューがあれば、1361と同様に論理プロセッサ1300処理用キューとしパケット処理を行う。
【0069】
また論理プロセッサは、パケット処理後、キューにパケットがある場合にも、特定の個数のパケットを処理した場合には、連続してパケット処理を行わず、キューをパケット処理対象のキューリスト1311の最後につなぐ。例えば特定の個数を4とした場合、1301では、キュー1391の5つ目のパケット処理は連続して行わず、キュー1391を一度1311のキューリストへ戻す(1382)。
【0070】
このように本実施形態においては、以下に記載するような効果を奏する。
【0071】
第1の効果は、セッションが同一のパケットはひとつの論理プロセッサで処理されるため、順序性が保証されることである。また、排他制御による待ちがなくなり、論理プロセッサが並列処理できるため、性能が向上する。
【0072】
第2の効果は、論理プロセッサがひとつのキューから連続処理する数の上限値に達したら、次のキューを処理するため、論理プロセッサ数に縛られることなく、多数のセッションを処理できることである。
【0073】
第3の効果は、論理プロセッサとセッションを固定で括りつけず、どの論理プロセッサでもどのセッションのキューを処理できるため、受信するパケットが一部のセッションに偏っていたとしても、処理(CPU使用率)に偏りが発生せず、平均的なパフォーマンスが発揮できることである。
【0074】
第4の効果は、処理対象キューリストを用意することで、論理プロセッサが処理すべきキューを探す必要がなくなり、性能が向上することである。これによって、より効率的に第2の効果と第3の効果を発揮できることである。
【0075】
[第5の実施形態]
本発明の第5の実施形態の構成を図11に示す。図11において、1430は、受信したパケットが順に格納されるキュー、1420は1430に格納されたパケットを取り出し、セッション別のキューに分配処理を行うデバイス(または論理プロセッサ)、1440は、1420がセッションを検索する際に利用されるCAM(Content Addressable Memory)、1410〜1413は、セッション別のキュー、1400〜1403は、論理プロセッサである。
【0076】
本実施形態では、1410〜1413のセッション別のキューの個数は、1400〜1403の論理プロセッサの個数と同一とし、分配デバイス(論理プロセッサ)との組み合わせとする。
【0077】
次に、本実施形態の動作を説明する。その基本的動作は、図9と同様であるが、本実施形態ではセッションの検索にCAMを用いる。CAMには、セッションを決定するキーを事前に設定する。
【0078】
図11において、デバイスがパケットを受信すると、1430で示される受信デバイス用のキューに格納される。分配処理を行うデバイス1420(または論理プロセッサ)は、受信デバイス用のキュー1430に格納されたパケットから、CAMを利用してセッション(グループ)を決定する。CAMの一般的な動作として、検索にヒットしたインデックスを得る。CAMの動作は一般的なものなのでここでは説明しない。
【0079】
CAMにて取得したインデックスと同一のインデックスのパケットを処理しているキュー1410〜1413があれば、受信デバイス用のキューからパケットを取り出し、インデックスが一致しているキューに格納する。インデックスが一致したキューがなく、さらにインデックスと関連付けされていないキューがある場合には、キューにインデックスを関連付け、受信デバイス用のキューからパケットをとりだし、そのパケットをインデックスが一致しているキューに格納する。インデックスが一致したキューがなく、全てのキューがインデックスと関連付けられている場合には、受信デバイスのキューからパケットの取り出しを保留する。
【0080】
CAMにはインデックス値を持った処理キューへ繋いだパケットカウンタを持ち、この値が閾値(連続処理してよいパケット数を事前に設定)を超えた場合には、処理キューへ積まず保留させる。これにより連続して同じセッション(グループ)のパケットばかりが処理されないように処理を分散させる。
【0081】
1410-1413の論理プロセッサは、自身が処理するキューが空になるもしくは閾値を超えると処理キューから自身が処理するインデックスを削除し、分配デバイス(論理プロセッサ)に通知する。分配デバイス(論理プロセッサ)1420は保留を解除する。
【0082】
こうすることで、CAMを利用した高速検索を可能とし、論理プロセッサに関連づけた処理キューを効率的に使用しながらセッション(グループ)毎の並列処理を可能とする。
【0083】
[その他の実施形態]
図11のキュー1430中のパケットe-1,d-2に示すように、対応するセッション(グループ)用の第2のキューが存在しないために処理が保留されているパケットe-1を飛び越えて、対応するセッション(グループ)用の第2のキューが存在する後続のパケットd-2を第2のキューに格納するようにしてもよい。
【0084】
更に他の例を説明する。図9〜図11にての説明は、受信パケットについてであるが、送信パケットや再送タイマーのタイムアウト処理などのイベントについても、セッションと対応させることで、同一セッションを同一の論理プロセッサで処理することが出来、送信/受信/タイマー各処理で共有するべき状態情報などへの排他制御を不要とすることで、並列性を向上させることができる。
【0085】
更に他の例としては、セッションの定義を拡大し、複数のセッションを同一グループと扱うことで、処理アプリケーション全体での排他制御を減らす(なくす)ことができる。
【0086】
更に他の例では、パケットのネットワーク(プロトコル)部分の処理と、アプリケーション部分で排他制御の範囲が異なる場合には、ネットワーク部とアプリケーション部を処理する論理プロセッサを分割し、受け渡し部分に本発明を適用すれば、ネットワーク部とアプリケーション部で異なるポリシーの分配による並列処理を実施することができる。
【0087】
また、本発明のネットワーク装置は、その有する機能をハードウェアで実現することは勿論、コンピュータとプログラムで実現することができる。プログラムは、磁気ディスクや半導体メモリなどのコンピュータ読み取り可能な記録媒体に記録されて提供され、コンピュータの立ち上げ時などにコンピュータに読み取られ、そのコンピュータの動作を制御することにより、そのコンピュータを前述した各実施形態における分配手段やパケット処理部として機能させる。
【符号の説明】
【0088】
100…ネットワーク装置
110…第1のキュー
120…パケット処理部
130…第2のキュー
140…分配部
【技術分野】
【0001】
本発明はネットワーク装置に関し、特に複数のパケット処理部を使用してパケットを並列に処理するネットワーク装置に関する。
【背景技術】
【0002】
この種のネットワーク装置の一例が特許文献1に記載されている。特許文献1に記載されたネットワーク装置(以下、本発明に関連するネットワーク装置と言う)は、パケットを受信順に記憶する第1のキューと、複数のパケット処理部と、このパケット処理部に1対1に対応する第2のキューと、パケット振り分け部と、振り分け情報テーブルと、複数のパケット処理部の負荷状態を定期的に収集する統計情報収集部とを有する。このような構成を有するネットワーク装置は、以下のように動作する。
【0003】
振り分け情報テーブルには、ハッシュ値とパケット処理部とカウンタとの組が記憶されている。ここで、ハッシュ値はパケットが属するグループを特定する情報である。特許文献1では、グループとしてフローを使用する。パケット振り分け部は、第1のキューからパケットを取り出し、そのパケットのヘッダ情報から計算したハッシュ値と同じハッシュ値に対応して上記振り分け情報テーブルに記憶されているパケット処理部に対応する第2のキューに格納し、対応するカウンタを+1する。各パケット処理部は、対応する第2のキューからパケットを取り出して処理を行い、振り分け情報テーブル上の対応するカウントを−1する。
【0004】
またパケット振り分け部は、統計情報収集部で収集された各パケット処理部の負荷状態を参照して、最も負荷の少ないパケット処理部に特定のグループのパケットを振り分けるべく、振り分け情報テーブル中のハッシュ値とパケット処理部との対応関係を更新する。このパケット振り分け先の変更は、何れの第2のキューにも上記特定のグループのパケットが存在していないタイミングを捉えて実施される。
【先行技術文献】
【特許文献】
【0005】
【特許文献1】特開2010−161546号公報
【発明の概要】
【発明が解決しようとする課題】
【0006】
上述した本発明に関連するネットワーク装置は、同じグループのパケットを同じパケット処理部で処理するようにしており、また特定のグループの振り分け先を変更する際にはそのグループのパケットが何れの第2のキューにも格納されていないタイミングを捉えて実施するため、グループ内でのパケットの順序の逆転は発生しない。
【0007】
しかしながら、上述した本発明に関連するネットワーク装置は、同じキューに複数のグループのパケットを混在させているため、処理待ちのパケットが存在するにもかかわらず空きのパケット処理部を有効に利用できない状況が長い時間続く可能性が高い。
【0008】
例えば、図12および図13において、A〜Dの4つのグループを想定し、各々のグループA〜Dのパケットをa〜dとする。また図12に示すように、グループAとグループBは第1のパケット処理部で処理し、グループCとグループDは第2のパケット処理部で処理するようにグループの振り分け先が設定されているとする。このとき、グループA〜Dのパケットがその後も継続して入力されるならば、2つのパケット処理部は空き状態になることはない。しかし、グループAとグループBのパケットがその後も継続して入力される一方、グループCとグループDのパケットが全く途絶えると、図13に示すように、第2のパケット処理部に対応するキューは空になり、第2のパケット処理部は空き状態になる。このとき、グループAとグループBのパケットはその後も継続して第1のパケット処理部に対応するキューに入力され続けるため、グループAまたはグループBの何れか一方のグループの振り分け先を第1のパケット処理部から第2のパケット処理部に変更することはできない。従って、空いている第2のパケット処理部を有効に利用できない状態が長く続くことになる。
【0009】
本発明の目的は、上述した課題、すなわち、処理待ちのパケットが存在するにもかかわらず空きのパケット処理部を有効に利用できない状況が長く続く可能性が高い、という課題を解決するネットワーク装置を提供することにある。
【課題を解決するための手段】
【0010】
本発明の一形態にかかるネットワーク装置は、
第1のキューと、
複数の第2のキューと、
前記第1のキューから取り出したパケットを、そのパケットのグループ以外のグループのパケットが格納されていない前記第2のキューに格納する分配手段と、
1以上の前記パケットが格納されている前記第2のキューのうち他のパケット処理手段が処理の対象としていないグループのパケットを格納する前記第2のキューからパケットを取り出して処理を行う複数のパケット処理手段と
を有する、といった構成を採る。
【発明の効果】
【0011】
本発明は上述したような構成を有するため、処理待ちのパケットが存在するにもかかわらず空きのパケット処理部を有効に利用できない状況が長く続くことを防止でき、パケット処理部の有効利用が可能になる。
【図面の簡単な説明】
【0012】
【図1】本発明の第1の実施形態のブロック図である。
【図2】本発明の第2の実施形態のブロック図である。
【図3】本発明の第2の実施形態における管理情報記憶部の構成例を示す図である。
【図4】本発明の第2の実施形態における分配部の処理を示すフローチャートである。
【図5】本発明の第2の実施形態におけるパケット処理部の処理を示すフローチャートである。
【図6】本発明の第3の実施形態のブロック図である。
【図7】本発明の第3の実施形態における分配部の処理を示すフローチャートである。
【図8】本発明の第3の実施形態におけるパケット処理部の処理を示すフローチャートである。
【図9】本発明の第4の実施形態のブロック図である。
【図10】本発明の第4の実施形態の動作説明図である。
【図11】本発明の第5の実施形態のブロック図である。
【図12】本発明に関連するネットワーク装置の動作説明図である。
【図13】本発明に関連するネットワーク装置の動作説明図である。
【発明を実施するための形態】
【0013】
次に本発明の実施の形態について図面を参照して詳細に説明する。
[第1の実施形態]
図1を参照すると、本発明の第1の実施形態にかかるネットワーク装置100は、第1のキュー110と、N(≧2)個のパケット処理部120と、M(≧N)個の第2のキュー130と、分配部140とを有する。
【0014】
第1のキュー110および複数の第2のキュー130は、パケットを先入れ先だし方式で格納する機能を有する記憶手段である。
【0015】
分配部140は、第1のキュー110から取り出したパケットを、そのパケットのグループ以外のグループのパケットが格納されていない第2のキュー130に格納する機能を有する。グループとは、例えばセッションである。パケットのグループは、例えばパケットのヘッダ情報に含まれる情報に基づいて決定される。
【0016】
パケット処理部120は、1以上のパケットが格納されている第2のキュー130のうち、他のパケット処理部120が処理の対象としていないグループのパケットを格納する第2のキュー130からパケットを取り出して処理を行う機能を有する。パケット処理部120で処理されたパケットは、例えば図示しない処理済キューに格納してもよいし、それ以外の任意の方法で処理してもよい。
【0017】
次に本実施形態の動作を説明する。
【0018】
処理の対象となるパケットは、第1のキュー110に一旦入力され、保持される。分配部140は、第1のキュー110に格納されたパケットを入力順に取り出し、そのパケットのグループを認識する。そして分配部140は、複数の第2のキュー120のうち、認識したグループ以外のグループのパケットが格納されていない第2のキュー130に上記のパケットを格納する。若し、そのような第2のキューが存在しなければ、そのような第2のキューが生じるまで処理を保留する。
【0019】
それぞれのパケット処理部120は、1以上のパケットが格納されている第2のキュー130のうち、他のパケット処理部120が処理の対象としていないグループのパケットを格納する第2のキュー130からパケットを取り出して処理を行う。それぞれのパケット処理部120は、同時には1つの第2のキュー130を処理の対象とする。
【0020】
次に本実施形態の効果を説明する。
【0021】
本実施形態では、1つの第2のキュー130には、1つのグループのパケットしか格納されない。また、複数のパケット処理部120が同じ第2のキュー130を同時に処理対象とすることはない。これにより、第1のキュー110に格納されているパケットの順序とパケット処理部120で処理されて出力されるパケットの順序とは、同じグループのパケット間で同じになる。すなわち、パケットの順序性を保証することができる。
【0022】
また本実施形態によれば、処理待ちのパケットが存在するにもかかわらず空きのパケット処理部120を有効に利用できない状況が長く続くことを防止でき、パケット処理部120の有効利用が可能になる。その理由は、空きの生じたパケット処理部120に処理待ちのパケットを投入できない状況が続くのは、第1のキュー110から次に取り出すパケットが、他のパケット処理部120で現在処理されているグループと同じグループの場合であるが、そのような状況になる確率は、1つの第2のキュー130に1つのグループしか格納しない方が、1つの第2のキュー130に複数のグループを混在させて格納するよりも小さくなるためである。特に本実施形態によれば、ネットワーク装置100で処理されるパケットのグループの数がパケット処理部120の数まで低下した場合、必ず、1つのパケット処理部120で1つのグループのパケットが処理される状態になるため、図13に示したような空きの第2のパケット処理部が発生することはない。
【0023】
[第2の実施形態]
図2を参照すると、本発明の第2の実施形態にかかるネットワーク装置200は、第1のキュー210と、N(≧2)個のパケット処理部220と、M(>N)個の第2のキュー230と、分配部240と、管理情報記憶部250とを有する。
【0024】
第1のキュー210および複数の第2のキュー230は、パケットを先入れ先だし方式で格納する機能を有する記憶手段である。
【0025】
管理情報記憶部250は、図3に示すように、キュー管理テーブル251と処理待ちキューのリスト252とから構成される。
【0026】
キュー管理テーブル251は、第2のキュー230のキュー識別子に対応付けて、グループ識別子とキュー長とを記憶する。グループとは、例えばセッションである。パケットのグループは、例えばパケットのヘッダ情報に含まれる情報に基づいて決定される。
【0027】
リスト252は、キュー長が1以上の第2のキュー230のリストである。
【0028】
分配部240は、第1のキュー210から取り出したパケットを、そのパケットのグループ識別子と同じグループ識別子に対応してキュー管理テーブル251に記憶されているキュー識別子で特定される第2のキュー230に格納し、対応するキュー長をインクリメントする機能を有する。また、分配部240は、第1のキュー210から取り出したパケットのグループ識別子と同じグループ識別子に対応するキュー識別子がキュー管理テーブル251に記憶されていないときは、第2のキュー230のうちキュー長が0の何れか1つの第2のキューに上記パケットを格納し、その格納した第2のキュー230のキュー識別子に対応付けて上記格納したパケットのグループ識別子をキュー管理テーブル251に記憶する機能を有する。さらに、分配部240は、キュー長が0の第2のキュー230が1つも存在しない場合には、キュー長が0の第2のキュー230が発生するまで待ち合わせを行う機能を有する。また分配部240は、パケットを格納することによってキュー長が1になった第2のキュー230のキュー識別子を、処理待ちキューのリスト252の最後尾につなぐ機能を有する。
【0029】
パケット処理部220は、空きが生じたときにリスト252の先頭につながれているキュー識別子を外して、この外したキュー識別子で特定される第2のキュー230を自パケット処理手段による処理の対象とする機能を有する。またパケット処理部220は、処理対象の第2のキュー230からパケットを取り出して処理し、キュー管理テーブル251の対応するキュー長をデクリメントする機能を有する。さらに、パケット処理部220は、自パケット処理手段が処理の対象としている第2のキュー230から連続して閾値の数だけのパケットを取り出して処理し終えた時点で、この第2のキュー230を処理の対象から外し、その第2のキュー230のキュー長が1以上であればそのキュー識別子をリスト252の最後尾につなぐ機能を有する。パケット処理部220で処理されたパケットは、例えば図示しない処理済キューに格納してもよいし、それ以外の任意の方法で処理してもよい。
【0030】
次に本実施形態の動作を説明する。
【0031】
図4は分配部240の処理の一例を示すフローチャートである。処理の対象となるパケットは、第1のキュー210に一旦入力され、保持される。分配部240は、第1のキュー210に1以上のパケットが格納されているか否かを判定し(ステップS1)、格納されていれば、その先頭のパケットのグループ識別子を求める(ステップS2)。
【0032】
次に分配部240は、この求めたグループ識別子に対応する第2のキュー230が存在するか否かをキュー管理テーブル251を検索して調べ(ステップS3)、存在すれば、第1のキュー210の先頭のパケットをその第2のキュー230に移動させ、対応するキュー長を+1する(ステップS6)。
【0033】
また分配部240は、上記求めたグループ識別子に対応する第2のキュー230が存在しなければ、キュー長が0の第2のキュー230が存在するか否かをキュー管理テーブル251を検索して調べる(ステップS4)。存在すれば、その中の1つの第2のキュー230を当該グループ用に使用するために選択し、この選択した第2のキュー230のキュー識別子に対応付けて上記先頭のパケットのグループ識別子をキュー管理テーブル251に記憶する(ステップS5)。そして、第1のキュー210の先頭のパケットをその第2のキュー230に移動させ、対応するキュー長を+1する(ステップS6)。
【0034】
また分配部240は、キュー長が0の第2のキュー230が1つも存在しなければ、キュー長が0の第2のキュー230が発生するまで待ち合わせを行う。そして、キュー長が0の第2のキュー230が発生すると、分配部240は、その発生した第2のキュー230のキュー識別子に対応付けて上記先頭のパケットのグループ識別子をキュー管理テーブル251に記憶し(ステップS5)、第1のキュー210の先頭のパケットをその第2のキュー230に移動させて、対応するキュー長を+1する(ステップS6)。
【0035】
分配部240は、上述のように或る第2のキュー230に1つのパケットを格納すると、その第2のキュー230のキュー長が0から1になったか否かを判定する(ステップS7)。若し、1になったならば、分配部240は、その第2のキューのキュー識別子を処理待ちキューのリスト252の最後尾につなぐ(ステップS8)。そして、分配部240はステップS1の処理へと戻る。
【0036】
図5はパケット処理部220の処理の一例を示すフローチャートである。パケット処理部220は、処理待ちキューのリスト252に1以上の第2のキュー230のキュー識別子が存在するか否かを判定する(ステップS11)。若し、存在すれば、パケット処理部220は、その先頭につながれている第2のキュー230のキュー識別子をリスト252から外し、自パケット処理手段による処理対象キューとする(ステップS12)。次にパケット処理部220は、処理対象キューとした第2のキュー230対応する処理数カウンタを0に初期化する(ステップS13)。処理数カウンタは、例えばパケット処理部220内に存在する。
【0037】
続いてパケット処理部220は、処理対象キューの第2のキュー230に対応してキュー管理テーブル251に記憶されているキュー長が1以上であることを確認し(ステップS14)、処理対象キューの第2のキュー230からパケットを1つ取り出して処理し、対応するキュー長を−1、処理数カウンタを+1する(ステップS15)。次にパケット処理部220は、処理数カウンタが予め設定された閾値以上になったか否かを判定する(ステップS16)。未だ閾値以上でないならば、パケット処理部220は、ステップS14の処理へと戻る。これにより、処理対象キューの第2のキュー230に残りのパケットが存在すれば、そのパケットが処理されることになる。若し、処理対象キューの第2のキュー230に残りのパケットが存在しなければ(ステップS14でNO)、この第2のキュー230を自パケット処理部による処理対象から外し、ステップS11の処理へと戻る。
【0038】
パケット処理部220は、処理対象キューとした第2のキュー230に格納されたパケットを閾値の数だけ処理し終えると(ステップS16でYES)、その第2のキュー230のキュー長が1以上であるか否か、すなわち未処理のパケットが残っているか否かを判定する(ステップS17)。若し、未処理のパケットが残っていれば、この第2のキュー230のキュー識別子を処理待ちキューのリスト252の最後尾につなぐ(ステップS18)。そして、この第2のキュー230を自パケット処理部による処理対象から外し、ステップS11の処理へと戻る。未処理のパケットが残っていなければ、リスト252につなぐことなく、この第2のキュー230を自パケット処理部による処理対象から外す。
【0039】
次に本実施形態の効果を説明する。
【0040】
本実施形態では、第1の実施形態と同様の理由により、パケットの順序性を保証することができると共に、処理待ちのパケットが存在するにもかかわらず空きのパケット処理部220を有効に利用できない状況が長く続くことを防止することができる。
【0041】
また本実施形態によれば、処理待ちキューのリスト252を有するため、パケット処理部220は、1以上のパケットが格納されている第2のキュー230のうち他のパケット処理部が処理の対象としていないグループのパケットを格納する第2のキュー230を探す必要がない。そのため、パケット処理部220は、処理を待っている第2のキューに対する処理を直ちに開始でき、スループットを高めることができる。
【0042】
また本実施形態によれば、パケット処理部220は、1つの第2のキュー220から一定個数のパケットを処理したら別の第2のキューを処理するため、1つの第2のキュー220に1種類のグループのパケットを格納するという構成を採用しながら、パケット処理部220の数以上の多数のグループのパケットを並行して処理することができる。
【0043】
また本実施形態によれば、第2のキュー220とグループとの関係を固定せず、動的に対応付けるため、ネットワーク装置200で扱うグループの最大数以下の数の第2のキューを使用して、全てのグループのパケットの処理が可能になる。
【0044】
なお、ネットワーク装置200で処理するパケットのグループが事前に定まっており、グループの数以上の数の第2のキュー230が存在する場合、第2のキュー230とグループとを事前に1対1に対応付けておいてもよい。すなわち、図3のキュー管理テーブル251のキューIDとグループIDとを事前に設定しておいてもよい。この場合、図4のステップS3〜S5を省略してもよい。
【0045】
[第3の実施形態]
図6を参照すると、本発明の第3の実施形態にかかるネットワーク装置300は、第1のキュー310と、N(≧2)個のパケット処理部320と、同じくN個の第2のキュー330と、分配部340と、キュー管理テーブル350とを有する。
【0046】
第1のキュー310および複数の第2のキュー330は、パケットを先入れ先だし方式で格納する機能を有する記憶手段である。第2のキュー330とパケット処理部320とは1対1に対応付けられている。
【0047】
キュー管理テーブル350は、第2の実施形態におけるキュー管理テーブル251と同様に、第2のキュー330のキュー識別子に対応付けて、グループ識別子とキュー長とを記憶する。グループとは、例えばセッションである。パケットのグループは、例えばパケットのヘッダ情報に含まれる情報に基づいて決定される。
【0048】
分配部340は、第1のキュー310から取り出したパケットを、そのパケットのグループ識別子と同じグループ識別子に対応してキュー管理テーブル350に記憶されているキュー識別子で特定される第2のキュー330に格納し、対応するキュー長をインクリメントする機能を有する。また、分配部340は、第1のキュー310から取り出したパケットのグループ識別子と同じグループ識別子に対応するキュー識別子がキュー管理テーブル350に記憶されていないときは、第2のキュー330のうちキュー長が0の何れか1つの第2のキューに上記パケットを格納し、その格納した第2のキュー330のキュー識別子に対応付けて上記格納したパケットのグループ識別子をキュー管理テーブル350に記憶する機能を有する。さらに、分配部340は、キュー長が0の第2のキュー330が1つも存在しない場合には、キュー長が0の第2のキュー330が発生するまで待ち合わせを行う機能を有する。
【0049】
パケット処理部320は、対応する第2のキュー330に1以上のパケットが存在すれば、パケットを1つずつ取り出して処理し、キュー管理テーブル350の対応するキュー長をデクリメントする機能を有する。パケット処理部320で処理されたパケットは、例えば図示しない処理済キューに格納してもよいし、それ以外の任意の方法で処理してもよい。
【0050】
次に本実施形態の動作を説明する。
【0051】
図7は分配部340の処理の一例を示すフローチャートである。処理の対象となるパケットは、第1のキュー310に一旦入力され、保持される。分配部340は、第1のキュー310に1以上のパケットが格納されているか否かを判定し(ステップS21)、格納されていれば、その先頭のパケットのグループ識別子を求める(ステップS22)。
【0052】
次に分配部340は、この求めたグループ識別子に対応する第2のキュー330が存在するか否かをキュー管理テーブル350を検索して調べ(ステップS23)、存在すれば、第1のキュー310の先頭のパケットをその第2のキュー330に移動させ、対応するキュー長を+1する(ステップS26)。そして、分配部340はステップS21の処理へと戻る。
【0053】
また分配部340は、上記求めたグループ識別子に対応する第2のキュー330が存在しなければ、キュー長が0の第2のキュー330が存在するか否かをキュー管理テーブル350を検索して調べる(ステップS24)。存在すれば、その中の1つの第2のキュー330を当該グループ用に使用するために選択し、この選択した第2のキュー330のキュー識別子に対応付けて上記先頭のパケットのグループ識別子をキュー管理テーブル350に記憶する(ステップS25)。次に、第1のキュー310の先頭のパケットをその第2のキュー330に移動させ、対応するキュー長を+1する(ステップS26)。そして、分配部340はステップS21の処理へと戻る。
【0054】
また分配部340は、キュー長が0の第2のキュー330が1つも存在しなければ、キュー長が0の第2のキュー330が発生するまで待ち合わせを行う(ステップS24)。そして、キュー長が0の第2のキュー330が発生すると、分配部340は、その発生した第2のキュー330のキュー識別子に対応付けて上記先頭のパケットのグループ識別子をキュー管理テーブル350に記憶し(ステップS25)、第1のキュー310の先頭のパケットをその第2のキュー330に移動させて、対応するキュー長を+1する(ステップS26)。そして、分配部340はステップS21の処理へと戻る。
【0055】
図8はパケット処理部320の処理の一例を示すフローチャートである。パケット処理部320は、自パケット処理手段による対応する第2のキュー330のキュー長が1以上であるか否かを確認する(ステップS31)。次に、パケット処理部320は、キュー長が1以上であれば、対応する第2のキュー230からパケットを1つ取り出して処理し、対応するキュー長を−1する(ステップS32)。そして、パケット処理部320はステップS31の処理へと戻る。
【0056】
次に本実施形態の効果を説明する。
【0057】
本実施形態では、第1の実施形態と同様の理由により、パケットの順序性を保証することができると共に、処理待ちのパケットが存在するにもかかわらず空きのパケット処理部320を有効に利用できない状況が長く続くことを防止することができる。
【0058】
また本実施形態によれば、第2のキュー320とグループとの関係を固定せず、動的に対応付けるため、パケット処理部320と同じ数の第2のキュー320を使用して、全てのグループのパケットの処理が可能になる。
【0059】
[第4の実施形態]
図9を参照すると、本発明の第4の実施形態としてのマルチコアプロセッサ上の論理プロセッサを使用したネットワーク装置が示されている。
【0060】
図9において、1230は、受信したパケットが順に格納されるキュー、1220は1230に格納されたパケットを取り出し、セッション(グループ)(以下、単にセッションと記す)別のキューに分配処理を行うデバイス(または論理プロセッサ)、1210〜1215は、セッション別のキュー、1200〜1203は、論理プロセッサである。セッション数は、論理プロセッサ数よりも十分に大きな値(例えば、論理プロセッサ数:32に対し、セッション数:20,000など、二桁の差があるなど)を想定するが、説明を容易とするため、例では6つで説明する。また、論理プロセッサは、32、64など多数を想定するが、説明を容易とするため例では、4つで説明する。
【0061】
1220の分配処理を行うデバイスは、単純な分配であれば、受信デバイス付属の分配機能を利用して分配を行う。複雑な条件による分配を行う場合には、論理プロセッサを使用することで分配が可能となる。
【0062】
次に、本実施形態の動作を説明する。図9において、受信デバイスがパケットを受信すると、1230で示される受信デバイス用のキューに格納される。分配処理を行うデバイス1220(または論理プロセッサ)は、受信デバイス用のキュー1230からパケットを取り出し、指定されたセッションの定義に従い、セッション毎のキュー1210〜1215に分配する。セッションの定義は、例えば、タイプ(IPv4/IPv6/など)、宛先IPアドレス、送信元IPアドレス、プロトコル(TCP/UDP/など)、宛先ポート番号、送信元ポート番号を使用する。
【0063】
セッション毎のキュー1210〜1215にパケットが格納された後、1200〜1203の論理プロセッサは、パケット処理対象のキューからパケットを取り出しパケット処理を行う。
【0064】
図10を参照して、論理プロセッサがパケット処理対象のキューを選択するしくみを説明する。図10において、1321は、キュー長(キュー内パケット数)が0のキュー、1311は、キュー長が1以上の、受信処理待ちキューのリスト、1300〜1303は、論理プロセッサとその論理プロサッサにて処理されているキューの組である。
【0065】
受信パケットは、分配処理を行うデバイスにより1321のセッション毎のキューに分配され格納される(1351)。この時、キュー長(キュー内のパケット数)が0から1以上に変化した場合にはキューは処理対象キューリスト1311の最後につながれる(1352)。
【0066】
論理プロセッサ1300〜1303は、パケット処理対象のキューリストの先頭を確認し、キューがあればキューリストからキューを外す。論理プロセッサ1300がキューリストからキュー1390を外し、論理プロセッサ1300処理用のキューとする動作を、1361にて示している。
【0067】
次に、論理プロセッサ1300〜1303は、キューからパケットを取り出し、パケット処理を行う。論理プロセッサ1300がキュー1390からパケットを取り出し、処理する動作を1371にて示している。パケット処理後、キューにさらにパケットがあれば取り出し、パケット処理を行う。キュー1390にパケットがなくなれば、処理を終えキューを論理プロセッサの処理キュー組み合わせから外す(1381)。キューは1321に戻ることと同じ扱いとなる。
【0068】
論理プロセッサは、再度パケット処理対象のキューリスト1311の先頭を確認し、キューリストにキューがあれば、1361と同様に論理プロセッサ1300処理用キューとしパケット処理を行う。
【0069】
また論理プロセッサは、パケット処理後、キューにパケットがある場合にも、特定の個数のパケットを処理した場合には、連続してパケット処理を行わず、キューをパケット処理対象のキューリスト1311の最後につなぐ。例えば特定の個数を4とした場合、1301では、キュー1391の5つ目のパケット処理は連続して行わず、キュー1391を一度1311のキューリストへ戻す(1382)。
【0070】
このように本実施形態においては、以下に記載するような効果を奏する。
【0071】
第1の効果は、セッションが同一のパケットはひとつの論理プロセッサで処理されるため、順序性が保証されることである。また、排他制御による待ちがなくなり、論理プロセッサが並列処理できるため、性能が向上する。
【0072】
第2の効果は、論理プロセッサがひとつのキューから連続処理する数の上限値に達したら、次のキューを処理するため、論理プロセッサ数に縛られることなく、多数のセッションを処理できることである。
【0073】
第3の効果は、論理プロセッサとセッションを固定で括りつけず、どの論理プロセッサでもどのセッションのキューを処理できるため、受信するパケットが一部のセッションに偏っていたとしても、処理(CPU使用率)に偏りが発生せず、平均的なパフォーマンスが発揮できることである。
【0074】
第4の効果は、処理対象キューリストを用意することで、論理プロセッサが処理すべきキューを探す必要がなくなり、性能が向上することである。これによって、より効率的に第2の効果と第3の効果を発揮できることである。
【0075】
[第5の実施形態]
本発明の第5の実施形態の構成を図11に示す。図11において、1430は、受信したパケットが順に格納されるキュー、1420は1430に格納されたパケットを取り出し、セッション別のキューに分配処理を行うデバイス(または論理プロセッサ)、1440は、1420がセッションを検索する際に利用されるCAM(Content Addressable Memory)、1410〜1413は、セッション別のキュー、1400〜1403は、論理プロセッサである。
【0076】
本実施形態では、1410〜1413のセッション別のキューの個数は、1400〜1403の論理プロセッサの個数と同一とし、分配デバイス(論理プロセッサ)との組み合わせとする。
【0077】
次に、本実施形態の動作を説明する。その基本的動作は、図9と同様であるが、本実施形態ではセッションの検索にCAMを用いる。CAMには、セッションを決定するキーを事前に設定する。
【0078】
図11において、デバイスがパケットを受信すると、1430で示される受信デバイス用のキューに格納される。分配処理を行うデバイス1420(または論理プロセッサ)は、受信デバイス用のキュー1430に格納されたパケットから、CAMを利用してセッション(グループ)を決定する。CAMの一般的な動作として、検索にヒットしたインデックスを得る。CAMの動作は一般的なものなのでここでは説明しない。
【0079】
CAMにて取得したインデックスと同一のインデックスのパケットを処理しているキュー1410〜1413があれば、受信デバイス用のキューからパケットを取り出し、インデックスが一致しているキューに格納する。インデックスが一致したキューがなく、さらにインデックスと関連付けされていないキューがある場合には、キューにインデックスを関連付け、受信デバイス用のキューからパケットをとりだし、そのパケットをインデックスが一致しているキューに格納する。インデックスが一致したキューがなく、全てのキューがインデックスと関連付けられている場合には、受信デバイスのキューからパケットの取り出しを保留する。
【0080】
CAMにはインデックス値を持った処理キューへ繋いだパケットカウンタを持ち、この値が閾値(連続処理してよいパケット数を事前に設定)を超えた場合には、処理キューへ積まず保留させる。これにより連続して同じセッション(グループ)のパケットばかりが処理されないように処理を分散させる。
【0081】
1410-1413の論理プロセッサは、自身が処理するキューが空になるもしくは閾値を超えると処理キューから自身が処理するインデックスを削除し、分配デバイス(論理プロセッサ)に通知する。分配デバイス(論理プロセッサ)1420は保留を解除する。
【0082】
こうすることで、CAMを利用した高速検索を可能とし、論理プロセッサに関連づけた処理キューを効率的に使用しながらセッション(グループ)毎の並列処理を可能とする。
【0083】
[その他の実施形態]
図11のキュー1430中のパケットe-1,d-2に示すように、対応するセッション(グループ)用の第2のキューが存在しないために処理が保留されているパケットe-1を飛び越えて、対応するセッション(グループ)用の第2のキューが存在する後続のパケットd-2を第2のキューに格納するようにしてもよい。
【0084】
更に他の例を説明する。図9〜図11にての説明は、受信パケットについてであるが、送信パケットや再送タイマーのタイムアウト処理などのイベントについても、セッションと対応させることで、同一セッションを同一の論理プロセッサで処理することが出来、送信/受信/タイマー各処理で共有するべき状態情報などへの排他制御を不要とすることで、並列性を向上させることができる。
【0085】
更に他の例としては、セッションの定義を拡大し、複数のセッションを同一グループと扱うことで、処理アプリケーション全体での排他制御を減らす(なくす)ことができる。
【0086】
更に他の例では、パケットのネットワーク(プロトコル)部分の処理と、アプリケーション部分で排他制御の範囲が異なる場合には、ネットワーク部とアプリケーション部を処理する論理プロセッサを分割し、受け渡し部分に本発明を適用すれば、ネットワーク部とアプリケーション部で異なるポリシーの分配による並列処理を実施することができる。
【0087】
また、本発明のネットワーク装置は、その有する機能をハードウェアで実現することは勿論、コンピュータとプログラムで実現することができる。プログラムは、磁気ディスクや半導体メモリなどのコンピュータ読み取り可能な記録媒体に記録されて提供され、コンピュータの立ち上げ時などにコンピュータに読み取られ、そのコンピュータの動作を制御することにより、そのコンピュータを前述した各実施形態における分配手段やパケット処理部として機能させる。
【符号の説明】
【0088】
100…ネットワーク装置
110…第1のキュー
120…パケット処理部
130…第2のキュー
140…分配部
【特許請求の範囲】
【請求項1】
第1のキューと、
複数の第2のキューと、
前記第1のキューから取り出したパケットを、そのパケットのグループ以外のグループのパケットが格納されていない前記第2のキューに格納する分配手段と、
1以上の前記パケットが格納されている前記第2のキューのうち他のパケット処理手段が処理の対象としていないグループのパケットを格納する前記第2のキューからパケットを取り出して処理を行う複数のパケット処理手段と
を有することを特徴とするネットワーク装置。
【請求項2】
キュー長が1以上の前記第2のキューのリストを有し、
前記分配手段は、前記キュー長が1になった前記第2のキューのキュー識別子を前記リストの最後尾につなぎ、
前記パケット処理手段は、空きが生じたときに前記リストの先頭につながれている前記キュー識別子を外して、該外したキュー識別子で特定される前記第2のキューを自パケット処理手段による処理の対象とする
ことを特徴とする請求項1に記載のネットワーク装置。
【請求項3】
前記第2のキューのキュー識別子に対応付けてグループ識別子とキュー長とを記憶するキュー管理テーブルを有し、
前記分配手段は、前記第1のキューから取り出したパケットを、そのパケットのグループ識別子と同じグループ識別子に対応して前記キュー管理テーブルに記憶されているキュー識別子で特定される前記第2のキューに格納すると共に、対応する前記キュー長をインクリメントし、
前記パケット処理手段は、自パケット処理手段が処理の対象としている前記第2のキューのパケットの処理に応じて、対応する前記キュー長をデクリメントする
ことを特徴とする請求項2に記載のネットワーク装置。
【請求項4】
前記パケット処理手段は、自パケット処理手段が処理の対象としている前記第2のキューから連続して閾値の数だけのパケットを取り出して処理し終えた時点で当該第2のキューを処理の対象から外し、該外した前記第2のキューのキュー長が1以上であればそのキュー識別子を前記リストの最後尾につなぐ
ことを特徴とする請求項3に記載のネットワーク装置。
【請求項5】
前記分配手段は、前記第1のキューから取り出したパケットのグループ識別子と同じグループ識別子に対応するキュー識別子が前記キュー管理テーブルに記憶されていないときは、前記複数の第2のキューのうちキュー長が0の何れか1つの前記第2のキューに前記パケットを格納すると共に、該格納した第2のキューのキュー識別子に対応付けて前記格納したパケットのグループ識別子を前記キュー管理テーブルに記憶する
ことを特徴とする請求項4に記載のネットワーク装置。
【請求項6】
前記分配手段は、前記複数の第2のキューのうちキュー長が0の前記第2のキューが存在しない場合には、キュー長が0の前記第2のキューが発生するまで待ち合わせを行う
ことを特徴とする請求項5に記載のネットワーク装置。
【請求項7】
前記複数の第2のキューは、前記パケット処理手段の数だけ存在し、前記パケット処理手段と前記第2のキューとが1対1に対応付けられている
ことを特徴とする請求項1に記載のネットワーク装置。
【請求項8】
前記分配手段は、前記第1のキューから取り出したパケットのグループが何れの前記第2のキューに格納されているパケットのグループとも一致しない場合には、何れかの前記第2のキューのキュー長が0になるまで待ち合わせを行う
ことを特徴とする請求項7に記載のネットワーク装置。
【請求項9】
前記第2のキューのキュー識別子に対応付けてグループ識別子とキュー長とを記憶するキュー管理テーブルを有し、
前記分配手段は、前記第1のキューから取り出したパケットのグループ識別子と同じグループ識別子が前記キュー管理テーブルに記憶されているか否かを判定し、記憶されていれば、記憶されているキュー識別子で特定される前記第2のキューに前記取り出したパケットを格納すると共に対応する前記キュー長をインクリメントし、記憶されていなければ、キュー長が0の第2のキューが存在するか否かを判定し、存在すれば、存在した第2のキューのキュー識別子に対応するグループ識別子に前記取り出したパケットのグループ識別子を設定して前記取り出したパケットを格納すると共に対応する前記キュー長をインクリメントし、存在しなければ何れかの前記第2のキューのキュー長が0になるまで待ち合わせを行い、
前記パケット処理手段は、対応する前記第2のキューのパケットの処理に応じて、対応する前記キュー長をデクリメントする
ことを特徴とする請求項8に記載のネットワーク装置。
【請求項10】
第1のキューと、複数の第2のキューと、分配手段と、複数のパケット処理手段とを有するネットワーク装置が実行する処理方法であって、
前記分配手段が、前記第1のキューから取り出したパケットを、そのパケットのグループ以外のグループのパケットが格納されていない前記第2のキューに格納し、
前記複数のパケット処理手段が、1以上の前記パケットが格納されている前記第2のキューのうち他のパケット処理手段が処理の対象としていないグループのパケットを格納する前記第2のキューからパケットを取り出して処理を行う
ことを特徴とする処理方法。
【請求項1】
第1のキューと、
複数の第2のキューと、
前記第1のキューから取り出したパケットを、そのパケットのグループ以外のグループのパケットが格納されていない前記第2のキューに格納する分配手段と、
1以上の前記パケットが格納されている前記第2のキューのうち他のパケット処理手段が処理の対象としていないグループのパケットを格納する前記第2のキューからパケットを取り出して処理を行う複数のパケット処理手段と
を有することを特徴とするネットワーク装置。
【請求項2】
キュー長が1以上の前記第2のキューのリストを有し、
前記分配手段は、前記キュー長が1になった前記第2のキューのキュー識別子を前記リストの最後尾につなぎ、
前記パケット処理手段は、空きが生じたときに前記リストの先頭につながれている前記キュー識別子を外して、該外したキュー識別子で特定される前記第2のキューを自パケット処理手段による処理の対象とする
ことを特徴とする請求項1に記載のネットワーク装置。
【請求項3】
前記第2のキューのキュー識別子に対応付けてグループ識別子とキュー長とを記憶するキュー管理テーブルを有し、
前記分配手段は、前記第1のキューから取り出したパケットを、そのパケットのグループ識別子と同じグループ識別子に対応して前記キュー管理テーブルに記憶されているキュー識別子で特定される前記第2のキューに格納すると共に、対応する前記キュー長をインクリメントし、
前記パケット処理手段は、自パケット処理手段が処理の対象としている前記第2のキューのパケットの処理に応じて、対応する前記キュー長をデクリメントする
ことを特徴とする請求項2に記載のネットワーク装置。
【請求項4】
前記パケット処理手段は、自パケット処理手段が処理の対象としている前記第2のキューから連続して閾値の数だけのパケットを取り出して処理し終えた時点で当該第2のキューを処理の対象から外し、該外した前記第2のキューのキュー長が1以上であればそのキュー識別子を前記リストの最後尾につなぐ
ことを特徴とする請求項3に記載のネットワーク装置。
【請求項5】
前記分配手段は、前記第1のキューから取り出したパケットのグループ識別子と同じグループ識別子に対応するキュー識別子が前記キュー管理テーブルに記憶されていないときは、前記複数の第2のキューのうちキュー長が0の何れか1つの前記第2のキューに前記パケットを格納すると共に、該格納した第2のキューのキュー識別子に対応付けて前記格納したパケットのグループ識別子を前記キュー管理テーブルに記憶する
ことを特徴とする請求項4に記載のネットワーク装置。
【請求項6】
前記分配手段は、前記複数の第2のキューのうちキュー長が0の前記第2のキューが存在しない場合には、キュー長が0の前記第2のキューが発生するまで待ち合わせを行う
ことを特徴とする請求項5に記載のネットワーク装置。
【請求項7】
前記複数の第2のキューは、前記パケット処理手段の数だけ存在し、前記パケット処理手段と前記第2のキューとが1対1に対応付けられている
ことを特徴とする請求項1に記載のネットワーク装置。
【請求項8】
前記分配手段は、前記第1のキューから取り出したパケットのグループが何れの前記第2のキューに格納されているパケットのグループとも一致しない場合には、何れかの前記第2のキューのキュー長が0になるまで待ち合わせを行う
ことを特徴とする請求項7に記載のネットワーク装置。
【請求項9】
前記第2のキューのキュー識別子に対応付けてグループ識別子とキュー長とを記憶するキュー管理テーブルを有し、
前記分配手段は、前記第1のキューから取り出したパケットのグループ識別子と同じグループ識別子が前記キュー管理テーブルに記憶されているか否かを判定し、記憶されていれば、記憶されているキュー識別子で特定される前記第2のキューに前記取り出したパケットを格納すると共に対応する前記キュー長をインクリメントし、記憶されていなければ、キュー長が0の第2のキューが存在するか否かを判定し、存在すれば、存在した第2のキューのキュー識別子に対応するグループ識別子に前記取り出したパケットのグループ識別子を設定して前記取り出したパケットを格納すると共に対応する前記キュー長をインクリメントし、存在しなければ何れかの前記第2のキューのキュー長が0になるまで待ち合わせを行い、
前記パケット処理手段は、対応する前記第2のキューのパケットの処理に応じて、対応する前記キュー長をデクリメントする
ことを特徴とする請求項8に記載のネットワーク装置。
【請求項10】
第1のキューと、複数の第2のキューと、分配手段と、複数のパケット処理手段とを有するネットワーク装置が実行する処理方法であって、
前記分配手段が、前記第1のキューから取り出したパケットを、そのパケットのグループ以外のグループのパケットが格納されていない前記第2のキューに格納し、
前記複数のパケット処理手段が、1以上の前記パケットが格納されている前記第2のキューのうち他のパケット処理手段が処理の対象としていないグループのパケットを格納する前記第2のキューからパケットを取り出して処理を行う
ことを特徴とする処理方法。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【公開番号】特開2012−209695(P2012−209695A)
【公開日】平成24年10月25日(2012.10.25)
【国際特許分類】
【出願番号】特願2011−72786(P2011−72786)
【出願日】平成23年3月29日(2011.3.29)
【出願人】(000004237)日本電気株式会社 (19,353)
【出願人】(390001395)NECシステムテクノロジー株式会社 (438)
【Fターム(参考)】
【公開日】平成24年10月25日(2012.10.25)
【国際特許分類】
【出願日】平成23年3月29日(2011.3.29)
【出願人】(000004237)日本電気株式会社 (19,353)
【出願人】(390001395)NECシステムテクノロジー株式会社 (438)
【Fターム(参考)】
[ Back to top ]