(57)【特許請求の範囲】
【請求項１】
それぞれが処理待ちキューを有する複数のパケット処理部と、
外部から受信したパケットをキューイングする受信キューと、
この受信キューから取り出した受信パケットをいずれかの前記処理待ちキューに振り分けるパケット振分け部と、
各処理待ちキューの状態を表すキュー管理情報、及び、各パケットが属するフローの振り分け先と処理待ちのパケット数とを含むフロー管理情報を保持する情報保持部と
を備えるパケット処理装置のパケット処理方法であって、
前記パケット振分け部は、
前記受信パケットのヘッダ情報から当該パケットが含まれるフローを特定して、前記フロー管理情報を参照して同のフローに属するパケット群を同じ処理待ちキューに振り分け、
前記キュー管理情報を参照することにより、振り分け先の前記処理待ちキューにキューイングされているパケットの数が所定の閾値を超えていると判定した場合は、さらに、前記フロー管理情報を参照することにより、当該処理待ちキューに含まれる当該振り分け対象パケットと同じフローに属するパケットの数であるフロー別パケット数が所定のフロー閾値以上であるか否かを判定し、前記フロー別パケット数が前記フロー閾値以上である場合に、当該振り分け対象パケットを所定のアルゴリズムによって確率的に破棄する一方、
前記処理待ちキューに割り当てられているフロー数が前記所定のアルゴリズムを適用するための所定の最小フロー数に満たないものと判定した場合に、前記所定のアルゴリズムを適用しない
ことを特徴とするパケット処理方法。
【請求項２】
それぞれが処理待ちキューを有する複数のパケット処理部と、
外部から受信したパケットをキューイングする受信キューと、
この受信キューから取り出した受信パケットをいずれかの前記処理待ちキューに振り分けるパケット振分け部と、
各処理待ちキューの状態を表すキュー管理情報、及び、各パケットが属するフローの振り分け先と処理待ちのパケット数とを含むフロー管理情報を保持する情報保持部と
を備えるパケット処理装置のパケット処理方法であって、
前記パケット振分け部は、
前記受信パケットのヘッダ情報から当該パケットが含まれるフローを特定して、前記フロー管理情報を参照して同のフローに属するパケット群を同じ処理待ちキューに振り分け、
前記キュー管理情報を参照することにより、振り分け先の前記処理待ちキューにキューイングされているパケットの数が所定の閾値を超えていると判定した場合は、さらに、前記フロー管理情報を参照することにより、当該処理待ちキューに含まれる当該振り分け対象パケットと同じフローに属するパケットの数であるフロー別パケット数が所定のフロー閾値以上であるか否かを判定し、前記フロー別パケット数が前記フロー閾値以上である場合に、当該振り分け対象パケットを所定のアルゴリズムによって確率的に破棄する一方、
前記フロー別パケット数が前記フロー閾値以上であると判定する毎に、当該フロー閾値を段階的に引き下げ、当該フローに属するパケットが振り分けられる前記処理待ちキューに新たにキューイングされる単位時間当たりの受信パケット数が減少する回数をカウントし、当該回数が、所定の回数に達した場合に、当該フロー閾値を所定の初期値に再設定する
ことを特徴とするパケット処理方法。
【請求項３】
請求項１または請求項２に記載のパケット処理方法において、
前記所定のアルゴリズムは、ＲＥＤアルゴリズムまたはそれから派生した類似のアルゴリズムである
ことを特徴とするパケット処理方法。
【請求項４】
それぞれが処理待ちキューを有する複数のパケット処理部と、
外部から受信したパケットをキューイングする受信キューと、
この受信キューから取り出した受信パケットをいずれかの前記処理待ちキューに振り分けるパケット振分け部と、
各処理待ちキューの状態を表すキュー管理情報、及び、各パケットが属するフローの振り分け先と処理待ちのパケット数とを含むフロー管理情報を保持する情報保持部と
を備え、
前記パケット振分け部は、
前記受信パケットのヘッダ情報から当該パケットが含まれるフローを特定して、前記フロー管理情報を参照して同じフローに属するパケット群を同じ処理待ちキューに振り分ける振分け処理部と、
前記キュー管理情報を参照することにより、振り分け先の前記処理待ちキューにキューイングされているパケットの数が所定の閾値を超えていると判定した場合は、さらに、前記フロー管理情報を参照することにより、当該処理待ちキューに含まれる当該振り分け対象パケットと同じフローに属するパケットの数であるフロー別パケット数が所定のフロー閾値以上であるか否かを判定し、前記フロー別パケット数が前記フロー閾値以上である場合に、当該振り分け対象パケットを所定のアルゴリズムによって確率的に破棄する破棄処理部とを有し、
前記処理待ちキューに割り当てられているフロー数が前記所定のアルゴリズムを適用するための所定の最小フロー数に満たないものと判定した場合に、前記所定のアルゴリズムを適用しない
ことを特徴とするパケット処理装置。
【請求項５】
それぞれが処理待ちキューを有する複数のパケット処理部と、
外部から受信したパケットをキューイングする受信キューと、
この受信キューから取り出した受信パケットをいずれかの前記処理待ちキューに振り分けるパケット振分け部と、
各処理待ちキューの状態を表すキュー管理情報、及び、各パケットが属するフローの振り分け先と処理待ちのパケット数とを含むフロー管理情報を保持する情報保持部と
を備え、
前記パケット振分け部は、
前記受信パケットのヘッダ情報から当該パケットが含まれるフローを特定して、前記フロー管理情報を参照して同じフローに属するパケット群を同じ処理待ちキューに振り分ける振分け処理部と、
前記キュー管理情報を参照することにより、振り分け先の前記処理待ちキューにキューイングされているパケットの数が所定の閾値を超えていると判定した場合は、さらに、前記フロー管理情報を参照することにより、当該処理待ちキューに含まれる当該振り分け対象パケットと同じフローに属するパケットの数であるフロー別パケット数が所定のフロー閾値以上であるか否かを判定し、前記フロー別パケット数が前記フロー閾値以上である場合に、当該振り分け対象パケットを所定のアルゴリズムによって確率的に破棄する破棄処理部と、
前記フロー別パケット数が前記フロー閾値以上であると判定する毎に、当該フロー閾値を段階的に引き下げ、当該フローに属するパケットが振り分けられる前記処理待ちキューにキューイングされる単位時間当たりの受信パケット数が減少する回数をカウントし、当該回数が所定の回数に達した場合に、当該フロー閾値を所定の初期値に再設定する閾値初
期化処理部とを有する
ことを特徴とするパケット処理装置。
【請求項６】
請求項４または請求項５に記載のパケット処理装置において、
前記所定のアルゴリズムは、ＲＥＤアルゴリズムまたはそれから派生した類似のアルゴリズムである
ことを特徴とするパケット処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パケット処理装置におけるパケット処理方法に係り、特に、低トラフィックのフローに対するパケット破棄を減らしつつ、ネットワークの輻輳回避を行う技術に関する。
【背景技術】
【０００２】
近年、インターネットを用いた通信サービスの高度化とユーザの増加に伴い、ネットワークトラフィック量が増加し続けている。そのため、トラフィックが集中する箇所では輻輳が発生する可能性が高まり、エンドユーザに多大な影響を及ぼすことが懸念される。このような問題を解決するために、通信装置の多くはパケット処理性能の向上対策や輻輳制御機能を実装する等の対策を施している。
【０００３】
前者の例として、特許文献１には、複数のハードウェアでパケット処理を並列化する方式が開示されている。この方式では、パケット振分け部がすべてのパケットを一旦受信し、受信したパケットを複数のパケット処理部に振り分けることでパケット処理を並列化する。
【０００４】
後者の例としては、パケット破棄による輻輳制御方式があり、中でも最も簡易的なものはTail Drop方式である。このTail Drop方式では、受信したパケットを到着順にキューに蓄積し、このキューが満杯になっているときに到着して溢れたパケットをすべて破棄するものである。しかし、この方式ではパケット破棄が連続的に行われることが多いため、パケットの再送が頻発してパケット間の衝突が起こったときに、ネットワークのスループットが低下するという問題がある。
【０００５】
このTail Drop方式におけるパケットの連続的な破棄を緩和するものとして、非特許文献１には、アクティブキュー管理方式が提案されている。その代表的な方式であるＲＥＤ（Random Early Detection）アルゴリズムにおいては、キュー溢れによる連続的なパケット破棄を抑止するために、キューに格納されているパケット数が所定の閾値を超えると、パケットを統計的（確率的）に破棄することで、キューが溢れないようにする。これにより、Tail Drop方式よりも高いスループットを得ることができる。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２０１０−１６１５４６号公報
【非特許文献】
【０００７】
【非特許文献１】IETF RFC2309: Recommendations on Queue Management and Congestion Avoidance in the Internet, April 1998.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
前記のようなパケット処理の並列化とＲＥＤアルゴリズムとを組み合わせて、パケット振分け部が各パケット処理部の処理待ちキューにパケットを振り分けるときにＲＥＤアルゴリズムを適用することにより、パケット処理性能の向上を図りつつパケットの連続的な破棄に伴うスループットの低下を防ぐことが可能である。
【０００９】
しかし、一つのパケット処理部には複数のフローが割り当てられるのが一般的である。そのため、帯域使用率の高いフローと帯域使用率の低いフローとが同じパケット処理部に割り当てられた場合、ＲＥＤアルゴリズムによるキュー管理のみでは、帯域使用率の低いフローのパケットであっても同じ確率で破棄されることになる。つまり、自身のフローの帯域使用率が低いのにも関わらず、帯域使用率の高いフローの影響によってパケット破棄が発生してしまうという問題がある。これは、ベストエフォート型ネットワークサービスにとって好ましくない。
【００１０】
本発明は、前記のような問題に鑑みてなされたものであり、パケット処理の並列化によるパケット処理性能の向上を図りつつ、帯域使用率の低いフローにおけるパケット破棄を減らすことが可能なパケット処理方法及びパケット処理装置を提供することを目的とする。
【課題を解決するための手段】
【００１１】
前記の目的を達成するために、本発明は、それぞれが処理待ちキューを有する複数のパケット処理部と、外部から受信したパケットをキューイングする受信キューと、この受信キューから取り出した受信パケットをいずれかの前記処理待ちキューに振り分けるパケット振分け部と、各処理待ちキューの状態を表すキュー管理情報、及び、各パケットが属するフローの振り分け先と処理待ちのパケット数とを含むフロー管理情報を保持する情報保持部とを備えるパケット処理装置において、前記パケット振分け部は、前記受信パケットのヘッダ情報から当該パケットが含まれるフローを特定して、前記フロー管理情報を参照して同じフローに属するすべてのパケット群を同じ処理待ちキューに振り分け、前記キュー管理情報を参照することにより、振り分け先の前記処理待ちキューにキューイングされているパケットの数が所定の閾値を超えていると判定した場合は、さらに、前記フロー管理情報を参照することにより、当該処理待ちキューに含まれる当該振り分け対象パケットと同じフローに属するパケットの数であるフロー別パケット数が所定のフロー閾値以上であるか否かを判定し、前記フロー別パケット数が前記フロー閾値以上である場合に、当該振り分け対象パケットを所定のアルゴリズムによって確率的に破棄する一方、前記処理待ちキューに割り当てられているフロー数が前記所定のアルゴリズムを適用するための所定の最小フロー数に満たないものと判定した場合に、前記所定のアルゴリズムを適用しないものとした。
【発明の効果】
【００１２】
本発明によれば、パケット処理の並列化によるパケット処理性能の向上を図りつつ、帯域使用率の低いフローにおけるパケット破棄を減らすことが可能なパケット処理方法及びパケット処理装置を提供することができる。
【図面の簡単な説明】
【００１３】
【図１】パケット処理装置の機能構成例を示す図ある。
【図２】パケット処理装置のハードウェア構成例を示す図である。
【図３】キュー管理テーブルの構成及びデータ例である。
【図４】フロー管理テーブルの構成及びデータ例である。
【図５】統計情報テーブルの構成及びデータ例である。
【図６】パケット振分け部の動作例を示すフローチャートである。
【図７】パケット振分け部におけるパケット振分け及び破棄処理の詳細を示すフローチャートである。
【図８】パケット処理部の動作例を示すフローチャートである。
【図９】パケット振分け部におけるフロー閾値初期化処理の詳細を示すフローチャートである。
【図１０】コンフィグファイルにおけるシステムパラメータの記述例である。
【発明を実施するための形態】
【００１４】
以下、本発明を実施するための形態を適宜図面を参照しながら説明するが、本発明の実施態様はこれに限定されるものではなく、本発明の趣旨を逸脱しない範囲内において各種変形が可能である。
【００１５】
図１は、本発明の実施形態に係るパケット処理装置の機能構成例を示す図である。図１に示すように、パケット処理装置１００は、受信キュー１０１と、パケット振分け部１０２と、複数の処理待ちキュー１０３と、複数のパケット処理部１０４と、送信キュー１０５と、情報保持部１０６とを備えて構成されている。また、情報保持部１０６は、キュー管理テーブル３００、フロー管理テーブル４００、及び統計情報テーブル５００を備え、さらに、装置の動作に必要な各種システムパラメータなどを記憶する。
【００１６】
パケット処理装置１００が中継すべきパケットを受信すると、当該受信パケットは受信キュー１０１に一時保存される。パケット振分け部１０２は、受信キュー１０１に一時保存されている受信パケットを１つずつ取り出して、複数のパケット処理部１０４のなかのいずれか１つに当該パケットを振り分ける。より詳しくは、パケット振分け部１０２は、受信パケットのヘッダ情報から当該パケットのフロー種別及びフローＩＤを抽出し、キュー管理テーブル３００を参照して振分け先の処理待ちキュー１０３（及び対応するパケット処理部１０４）を特定したのち、特定した処理待ちキュー１０３に当該パケットをキューイングする。このとき、キュー管理テーブル３００において、抽出したフローＩＤに対してすでに特定の処理待ちキュー１０３（及びパケット処理部１０４）が割り当てられていれば、当該割り当て済みの処理待ちキュー１０３に当該パケットを振り分け、まだ処理待ちキュー１０３（及びパケット処理部１０４）が割り当てられていなければ、新たにいずれか１つを割り当てる。割り当ての方法は特に限定されないが、例えば、その時点で最も負荷が小さいパケット処理部１０４（及び対応する処理待ちキュー１０３）を割り当てるものとしてもよいし、その時点で最もキューイングされているパケット数が少ない処理待ちキュー１０３（及びパケット処理部１０４）を割り当てるものとしてもよい。
【００１７】
各パケット処理部１０４は、自身に対応する処理待ちキュー１０３からパケットを１つずつ取り出して、ルーティング処理やプロトコル処理など当該パケット処理装置１００に要求されるパケット処理を行ったのち、処理済みのパケットである送信パケットを送信キュー１０５にキューイングする。送信キュー１０５にキューイングされた各送信パケットは、不図示のパケット送信部によって所定の送信先に順次送信される。
【００１８】
続いて、図２を参照して、パケット処理装置のハードウェア構成を説明する。図２は、パケット処理装置のハードウェア構成例を示す図である。図２に示すように、パケット処理装置１００は、バス２００で相互接続されたマルチコアＣＰＵ（Central Processing Unit）２０１と、入力ＩＦ（Interface）２０２と、出力ＩＦ２０３と、メモリ２０４とを備えて構成されている。さらに、マルチコアＣＰＵのなかのコア＃０（符号２０５）は、パケット振分け部として動作し、コア＃１からコア＃Ｎ（符号２０６）は、それぞれパケット処理部として動作する。ここでは、図１に示したパケット振分け部１０２及びパケット処理部１０４は、各コアが所定のプログラムを実行することで具現化されるものとするが、それぞれの処理部をハードウェアで実現するものとしてもよい。
【００１９】
入力ＩＦ２０２は、不図示の通信回線を介して外部から受信した信号を、装置内部で扱うデータ形式に変換し、受信パケットとして受信キュー１０１（図１参照）にキューイングする。出力ＩＦ２０３は、送信キュー１０５（図１参照）から送信パケットを取り出し、外部が扱う信号形式に変換して不図示の通信回線を介して送信する。また、ＲＡＭ（Random Access Memory）などによって構成されるメモリ２０４には、受信キュー１０１と、複数の処理待ちキュー１０３と、送信キュー１０５と、情報保持部１０６との各領域が、それぞれ割り当てられる。
【００２０】
図３は、キュー管理テーブルの構成及びデータ例である。図３に示すように、キュー管理テーブル３００には、コア番号３０１、フロー種別３０２、ＤＲＯＰ閾値３０３、ＲＥＤ閾値３０４、初期フロー閾値３０５、ＲＥＤ適用フロー数３０６、処理待ちパケット数３０７、フロー数３０８、及びフローリスト３０９を属性としてもつレコードが、パケット処理部１０４として機能するコア２０６（コア＃１〜Ｎ）の数だけ登録される。
【００２１】
コア番号３０１は、当該レコードに対応付けられているコア２０６及び対応するパケット処理部１０４の識別番号である。フロー種別３０２は、当該コア２０６に割り当てられるフローの種別を表すものであり、例えば、送信元のＩＰ（Internet Protocol）アドレス毎にフローを区別する「送信元ＩＰ」、宛先ポート毎にフローを区別する「宛先ポート」、宛先のＩＰアドレス毎にフローを区別する「宛先ＩＰ」などの値が設定される。
【００２２】
ＤＲＯＰ閾値３０３は、Tail Drop方式を適用してそれぞれの処理待ちキュー１０３から溢れたパケットを破棄するか否かを判定するための基準となるパケット数であり、それぞれの処理待ちキュー１０３にキューイング可能な最大パケット数に相当する。ＲＥＤ閾値３０４は、それぞれの処理待ちキュー１０３に対してＲＥＤアルゴリズムを適用するか否かを判定するための基準となるパケット数である。初期フロー閾値３０５は、図４の説明にて後記するフロー閾値４０４の初期値である。ＲＥＤ適用フロー数３０６は、当該コア２０６に割り当てられているフローの数が少ないときにはＲＥＤアルゴリズムを適用しないようにするための基準となるフローの数である。
【００２３】
処理待ちパケット数３０７は、当該パケット処理部１０４に対応する処理待ちキュー１０３にキューイングされているパケットの数であり、この値がＲＥＤ閾値３０４よりも大きくＤＲＯＰ閾値よりも小さいときに、ＲＥＤアルゴリズムの適用可否の判定が行われる。フロー数３０８は、当該パケット処理部１０４に割り当てられているフローの数であり、この値がＲＥＤ適用フロー数３０６よりも大きくなければＲＥＤアルゴリズムは適用されない。フローリスト３０９は、当該パケット処理部１０４に割り当てられているすべてのフローのフロー番号のリストであり、例えば図３の１行目のレコードは、コア＃１に対応するパケット処理部１０４に、フロー番号＃１，＃９，＃２６，＃３８，＃４６の５つのフローが割り当てられている状態を示している。これらのフローリスト３０９は、新たなフローの発生やフローの消滅に伴って動的にデータが更新される。
【００２４】
図４は、フロー管理テーブルの構成及びデータ例である。図４に示すように、フロー管理テーブル４００には、フロー番号４０１、コア番号４０２、パケット数４０３、フロー閾値４０４、及び閾値初期化カウンタ４０５を属性としてもつレコードが、パケット処理部１０４に割り当てられているフローの数だけ登録される。
【００２５】
フロー番号４０１は、当該レコードに対応付けられているフローに対して付与されるユニークな識別番号である。各受信パケットが属するフローのフロー番号は、当該パケットのヘッダ情報を解析することにより一意に特定される。コア番号４０２は、当該フローが割り当てられたパケット処理部１０４に該当するコア２０６の識別番号である。パケット数４０３は、当該コア２０６に対応する処理待ちキュー１０３にキューイングされているパケットのうち当該フローに属するパケットの数である。フロー閾値４０４は、当該フローに対してＲＥＤアルゴリズムを適用するか否かを判定するための基準となるパケット数であり、当該フローのパケット数４０３の値がこのフロー閾値を超えている場合に、当該フローに対してＲＥＤアルゴリズムが適用されることになる。後記にて説明するように、フロー閾値４０４の値は、当該フローに対してＲＥＤアルゴリズムが適用される度に減少していく。閾値初期化カウンタ４０５は、減少したフロー閾値４０４の値を所定の初期フロー閾値３０５（図３）に戻すために用いるカウンタである。
【００２６】
なお、図４に示したデータ例は、フロー番号＃１，＃９，＃４６のフローが、フロー閾値４０４の初期値（＝初期フロー閾値３０５）が「１００」であるコア＃１に割り当てられており、フロー＃９のフローに対してＲＥＤアルゴリズムが適用されたことで該当するフロー閾値４０４が「９５」にまで減少した状態を表している。フロー閾値４０４の減少の単位は、システムパラメータとして設定可能であり、この値を０とすれば、フロー閾値４０４を減少させないようにすることも可能である。
【００２７】
図５は、統計情報テーブルの構成及びデータ例である。図５に示すように、統計情報テーブル５００には、コア番号５０１、総受信パケット数５０２、総送信パケット数５０３、総破棄パケット数５０４、前回総受信パケット数５０５、及び前回受信パケット数５０６を属性としてもつレコードが、パケット処理部１０４として機能するコア２０６（コア＃１〜Ｎ）の数だけ登録される。
【００２８】
コア番号５０１は、当該レコードに対応付けられているコア２０６及び対応するパケット処理部１０４の識別番号である。総受信パケット数５０２は、統計情報の収集を開始してから当該コア２０６（パケット処理部１０４）が受信した（当該コアに振り分けられた）パケットの総数であり、総送信パケット数５０３は、当該コア２０６（パケット処理部１０４）が送信した（送信キュー１０５にキューイングした）パケットの総数である。総破棄パケット数５０４は、当該コア２０６（パケット処理部１０４）に振り分けられたパケットのうち破棄されたパケットの総数であり、総受信パケット数５０２から総送信パケット数５０３と処理待ちパケット数３０７（図３）との和を引いた値に等しい。
【００２９】
前回総受信パケット数５０５は、所定の単位時間（例えば５秒）毎にその時点における総受信パケット数５０２の値を記憶したものであり、単位時間毎に値が上書きされて更新される。つまり、前回総受信パケット数５０５は、前回の上書き更新時における総受信パケット数５０２の値を示している。前回受信パケット数５０６は、前回総受信パケット数５０５の前々回の上書き更新時から前回の上書き更新時までの単位時間に受信したパケットの数を記憶したものである。
【００３０】
例えば、図５に例示した状態にて今回の上書き更新が行われるときには、コア番号が１である１行目のレコードについては、総受信パケット数５０２の値である「１３４０」が前回総受信パケット数５０５に上書きされて記憶され、前回受信パケット数５０６には、総受信パケット数５０２の値「１３４０」から前回総受信パケット数５０５の値「１２２０」を引いた値である「１２０」が上書きされて記憶される。
【００３１】
この統計情報テーブル５００を参照することによって、パケット処理部１０４として機能する各コア２０６におけるパケット破棄率や受信パケット数の増減を把握し、パケット処理装置１００の動作を規定する各種システムパラメータを自動または手動で適宜調整することが可能となる。
【００３２】
続いて、図６及び図７を参照して、パケット振分け部の動作を説明する。図６は、パケット振分け部の動作例を示すフローチャートであり、図７は、パケット振分け部におけるパケット振分け及び破棄処理の詳細を示すフローチャートである。
【００３３】
図６に示すように、パケット振分け部１０２の振分け処理部は、まず、入力ＩＦ２０２が受信して受信キュー１０１にキューイングした受信パケットを、受信キュー１０１から１つ取り出す（ステップ６０１）。このとき、パケットに優先度が付されていれば、最も優先度の高いパケット群のなかから優先して受信パケットを取り出すようにしてもよい。次に、振分け処理部は、受信パケットのヘッダ情報を解析することによって当該パケットのフロー種別とフローの識別情報であるフロー番号とを特定し（ステップ６０２）、当該フロー番号がフロー管理テーブル４００に登録されてパケット処理部１０４が割当て済みであるか否かを判定する（ステップ６０３）。
【００３４】
パケット処理部１０４が割当て済みである場合には（ステップ６０３で「Ｙｅｓ」）、ステップ６０６に処理を進めて割当て済みのパケット処理部１０４へのパケット振分け処理を行い、パケット処理部１０４が割り当てられていない新たなフローである場合には（ステップ６０３で「Ｎｏ」）、ステップ６０４に処理を進める。
【００３５】
ステップ６０４では、振分け処理部は、キュー管理テーブル３００を参照することにより、特定したフロー種別に適合するパケット処理部１０４を１つ選択し、当該パケット処理部１０４に対して当該フローを割り当てる（ステップ６０５）。具体的には、フロー管理テーブル４００に当該フローのフロー番号を有する新たなレコードを生成して追加登録するとともに、キュー管理テーブル３００の当該パケット処理部１０４に該当するレコードのフロー数３０８に１を加算し、フローリスト３０９に当該フロー番号を追加登録する。適合するパケット処理部１０４が複数存在するときには、例えば、処理待ちパケット数３０７が最小のパケット処理部１０４を選択するようにしてもよいし、フロー数３０８が最小のパケット処理部１０４を選択するようにしてもよい。そののち、ステップ６０６に処理を進めて新規に割り当てたパケット処理部１０４へのパケット振分け処理を行う。
【００３６】
図７に示すように、パケット振分け及び破棄処理においては、パケット振分け部１０２の破棄処理部は、まず、振分け先のパケット処理部１０４に対応するキュー管理情報及び当該パケットが属するフローのフロー管理情報を取得する（ステップ７０１）。具体的には、キュー管理テーブル３００から当該パケット処理部１０４に該当するコア番号を有するレコードを読み出し、フロー管理テーブル４００から当該パケットに該当するフロー番号を有するレコードを読み出す。次に、破棄処理部は、受信パケット数の加算を行う（ステップ７０２）。具体的には、統計情報テーブル５００において、当該パケット処理部１０４に該当するコア番号を有するレコードの総受信パケット数５０２の値に１を加算する。
【００３７】
次に、破棄処理部は、キュー管理テーブル３００から読み出したレコードを参照することにより、振分け対象のパケットを当該処理待ちキュー１０３にキューイングすると処理待ちパケット数（処理待ちパケット数３０７に１を加算した値）がＤＲＯＰ閾値３０３を超えるか否かを判定する（ステップ７０３）。
【００３８】
処理待ちパケット数＞ＤＲＯＰ閾値  となる場合（ステップ７０３で「Ｙｅｓ」）、ステップ７１４に処理を進め、フロー管理テーブル４００から読み出したレコードを参照することにより、当該パケットを当該処理待ちキュー１０３にキューイングするとフロー別のパケット数（パケット数４０３に１を加算した値）がフロー閾値４０４を超えるか否かを判定する。
【００３９】
フロー別パケット数＞フロー閾値  の場合（ステップ７１４で「Ｙｅｓ」）、ステップ７１５に処理を進めてフロー閾値４０４を引き下げる。ここで閾値を引き下げる単位は、システムパラメータやコマンドラインインタフェースによる入力などによって事前に与えられるものとする。続いて、閾値初期化カウンタ４０５の値を所定値に設定し（ステップ７１６）、当該パケットを破棄し（ステップ７１７）、統計情報テーブル５００の該当する総破棄パケット数５０４を１だけ加算したのち（ステップ７１８）、処理を終了する。フロー別パケット数≦フロー閾値  の場合（ステップ７１４で「Ｎｏ」）、ステップ７１７に処理を進めて当該パケットを破棄し（ステップ７１７）、統計情報テーブル５００の該当する総破棄パケット数５０４を１だけ加算したのち（ステップ７１８）、処理を終了する。
【００４０】
また、処理待ちパケット数≦ＤＲＯＰ閾値  となる場合（ステップ７０３で「Ｎｏ」）、ステップ７０４に処理を進め、フロー管理テーブル４００から読み出したレコードを参照することにより、当該パケットを当該処理待ちキュー１０３にキューイングすると処理待ちパケット数（処理待ちパケット数３０７に１を加算した値）がＲＥＤ閾値３０４を超えるか否かを判定する。
【００４１】
処理待ちパケット数≦ＲＥＤ閾値  となる場合（ステップ７０４で「Ｎｏ」）、ステップ７１１に処理を進めて当該パケットを当該処理待ちキュー１０３にキューイングする。続いて、フロー管理テーブル４００の該当するフローのパケット数４０３を１だけ加算し（ステップ７１２）、キュー管理テーブル３００の該当する処理待ちパケット数３０７を１だけ加算したのち（ステップ７１３）、処理を終了する。
【００４２】
他方、処理待ちパケット数＞ＲＥＤ閾値  となる場合（ステップ７０４で「Ｙｅｓ」）、ステップ７０５に処理を進めて、さらに、フロー管理テーブル４００から読み出したレコードを参照することにより、当該パケットを当該処理待ちキュー１０３にキューイングするとフロー別のパケット数（パケット数４０３に１を加算した値）がフロー閾値４０４を超えるか否かを判定する。
【００４３】
フロー別パケット数≦フロー閾値  の場合（ステップ７０５で「Ｎｏ」）、ステップ７１１に処理を進める。ステップ７１１以降の処理は、前記の処理待ちパケット数≦ＲＥＤ閾値のときと同様である。他方、フロー別パケット数＞フロー閾値  の場合（ステップ７０５で「Ｙｅｓ」）、ステップ７０６に処理を進めて、さらに、フロー管理テーブル４００から読み出したレコードを参照することにより、当該処理待ちキュー１０３に割り当てられているフロー数３０８がＲＥＤ適用フロー数３０６を超えているか否かを判定する。
【００４４】
フロー数≦ＲＥＤ適用フロー数  の場合（ステップ７０６で「Ｎｏ」）、ステップ７１１に処理を進める。ステップ７１１以降の処理は、前記の処理待ちパケット数≦ＲＥＤ閾値のときと同様である。フロー数＞ＲＥＤ適用フロー数  の場合（ステップ７０６で「Ｙｅｓ」）、ステップ７０７に処理を進めてフロー閾値４０４を引き下げたのち、閾値初期化カウンタ４０５の値を所定値に設定する（ステップ７０８）。続いて、ステップ７０９と７１０とによって当該フローに対してＲＥＤアルゴリズムを適用する。
【００４５】
この例では、まず、当該処理待ちキュー１０３のＲＥＤ閾値３０４とＤＲＯＰ閾値３０３との間のランダム値を算出し（ステップ７０９）、現在の処理待ちパケット数３０７が算出したランダム値よりも大きいか否かを判定する（ステップ７１０）。そして、処理待ちパケット数＞ランダム値  の場合（ステップ７１０で「Ｙｅｓ」）、ステップ７１７に処理を進めて当該パケットを破棄し、統計情報テーブル５００の該当する総破棄パケット数５０４を１だけ加算したのち（ステップ７１８）、処理を終了する。また、処理待ちパケット数≦ランダム値  の場合は（ステップ７１０で「Ｎｏ」）、ステップ７１１に処理を進めて当該パケットを当該処理待ちキュー１０３にキューイングしたのち、該当するフロー別のパケット数４０３と処理待ちパケット数３０７を１ずつ加算して（ステップ７１２，７１３）処理を終了する。
【００４６】
以上がパケット振分け部１０２の振分け処理部と破棄処理部とが実行する一連の処理であり、パケット振分け部１０２は、受信キュー１０１に順次キューイングされる受信パケットについて、上記処理を繰り返す。
【００４７】
続いて、図８を参照して、パケット処理部の動作を説明する。図８は、パケット処理部の動作例を示すフローチャートである。
【００４８】
図８に示すように、パケット処理部１０４は、まず、自身に対応する処理待ちキュー１０３にキューイングされているパケットを１つ取り出す（ステップ８０１）。次に、パケット処理部１０４は、キュー管理テーブル３００の該当する処理待ちパケット数３０７とフロー管理テーブル４００の該当するフロー別のパケット数４０３とをそれぞれ１ずつ減算する（ステップ８０２，８０３）。次に、パケット処理部１０４は、そのパケットに対してルーティング処理やプロトコル処理等の所定のパケット処理を行う（ステップ８０４）。パケット処理が成功した場合（ステップ８０５で「Ｙｅｓ」）、パケット処理部１０４は、ステップ８０６に処理を進めて送信キュー１０５にパケットをキューイングしたのち、統計情報テーブル５００の該当する総送信パケット数５０３を１だけ加算して（ステップ８０７）処理を終了する。他方、パケット処理が失敗した場合は（ステップ８０５で「Ｎｏ」）、ステップ８０８に処理を進めて統計情報テーブルの該当する総破棄パケット数を１だけ加算したのち、処理を終了する。
【００４９】
以上がパケット処理部１０４が実行する一連の処理であり、パケット処理部１０４は、自身の処理待ちキュー１０３に順次キューイングされるパケットについて、上記処理を繰り返す。
【００５０】
続いて、図９を参照してフロー閾値初期化処理について説明する。図９は、パケット振分け部におけるフロー閾値初期化処理の詳細を示すフローチャートである。図９に示す処理は、統計情報テーブル５００の上書き更新を行う所定の単位時間（例えば５秒）毎に起動され、それぞれのパケット処理部１０４について個別に実行される。
【００５１】
図９に示すように、パケット振分け部１０２の閾値初期化処理部は、まず、統計情報テーブル５００の対象となるパケット処理部１０４のレコードから総受信パケット数５０２など一連の統計情報を取得する（ステップ９０１）。次に、閾値初期化処理部は、総受信パケット数５０２から前回総受信パケット数５０５を減算することによって、現時点の単位時間前（前回の上書き更新時）以降に受信して振り分けた受信パケットの数である今回の受信パケット数を算出する（ステップ９０２）。次に、閾値初期化処理部は、算出した今回の受信パケット数が前回受信パケット数５０６よりも小さいか否かを判定し（ステップ９０３）、今回の受信パケット数が前回受信パケット数よりも小さい（図９では、「今回＜前回」と表記）場合は（ステップ９０３で「Ｙｅｓ」）ステップ９０４に処理を進め、今回の受信パケット数が前回受信パケット数以上の場合は（ステップ９０３で「Ｎｏ」）ステップ９０７に処理を進める。
【００５２】
ステップ９０４では、閾値初期化処理部は、当該パケット処理部１０４に割り当てられているフローをフロー管理テーブル４００からすべて検索し、該当する閾値初期化カウンタ４０５の値が０でないものがあればその値を１だけ減算する。次に、減算後に閾値初期化カウンタ４０５の値が０となったか否かを判定し（ステップ９０５）、０となった場合は（ステップ９０５で「Ｙｅｓ」）ステップ９０６に処理を進め、フロー管理テーブル４００の該当するフローのフロー閾値４０４の値をキュー管理テーブル３００の該当する初期フロー閾値３０５の値に初期化する。
【００５３】
ステップ９０７では、閾値初期化処理部は、当該パケット処理部１０４に該当する統計情報のうち、前回総受信パケット数５０５及び前回受信パケット数５０６を更新したのち、処理を終了する。このとき、前回総受信パケット数５０５には、その時点の総受信パケット数５０２の値を上書きして更新し、前回受信パケット数５０６には、ステップ９０２にて算出した今回の受信パケット数の値を上書きして更新する。
【００５４】
以上の処理により、フロー別のパケット数が対応するフロー閾値を超えて当該フロー閾値が引き下げられたのちに、当該フローが割り当てられているパケット処理部１０４に振り分けられる単位時間当たりのパケット数が所定の回数だけ減少した場合に、引き下げられたフロー閾値の再設定が行われる。
【００５５】
最後に、装置の動作に必要な各種システムパラメータの設定について説明する。図１０は、コンフィグファイルにおけるシステムパラメータの記述例である。コンフィグファイルは、パケット処理装置１００の起動時に不図示の不揮発性メモリなどから読み込まれる。図１０に示したコンフィグファイルには、図３に例示したキュー管理テーブル３００の初期設定に使用されるシステムパラメータとして、各パケット処理部１０４のコア番号、フロー種別、ＤＲＯＰ閾値、ＲＥＤ閾値、初期フロー閾値、ＲＥＤ適用フロー数が記述されている。これらのシステムパラメータは、コマンドラインインタフェースのような方法により利用者などによって動的に変更されるものとしてもよい。
【００５６】
以上にて、本発明の実施形態の説明を終える。なお、前記の実施形態においては、アクティブキュー管理方式としてＲＥＤアルゴリズムを適用する例について説明したが、例えば重み付きＲＥＤアルゴリズムのようにＲＥＤアルゴリズムを拡張したアルゴリズムを適用してもよいし、ＲＥＤアルゴリズムとは異なる他のアクティブキュー管理アルゴリズムを適用してもよい。また、前記の実施形態においては、高トラフィックのフローのフロー閾値を動的に引き下げるものとしたが、フロー閾値を引き下げずに固定値としてもよく、その場合にはフロー管理テーブル４００におけるフロー閾値４０４と閾値初期化カウンタ４０５とを省略することができる。また、フロー毎に優先度を付与してもよく、その場合には、優先度の高いフローには通常の初期フロー閾値よりも大きいフロー閾値を設定することにより、処理待ちキューにキューイング可能なパケット数を増やして優先度の高いフローのパケットを破棄しにくくするようにしてもよい。
【符号の説明】
【００５７】
１００  パケット処理装置
１０１  受信キュー
１０２  パケット振分け部（振分け処理部、破棄処理部）
１０３  処理待ちキュー
１０４  パケット処理部
１０５  送信キュー
１０６  情報保持部
２００  バス
２０１  マルチコアＣＰＵ
２０２  入力ＩＦ
２０３  出力ＩＦ
２０４  メモリ
２０５  コア（コア＃０）
２０６  コア（コア＃１〜Ｎ）
３００  キュー管理テーブル（キュー管理情報）
３０１  コア番号
３０２  フロー種別
３０３  ＤＲＯＰ閾値
３０４  ＲＥＤ閾値
３０５  初期フロー閾値
３０６  ＲＥＤ適用フロー数（最小フロー数）
３０７  処理待ちパケット数
３０８  フロー数
３０９  フローリスト
４００  フロー管理テーブル（フロー管理情報）
４０１  フロー番号
４０２  コア番号
４０３  パケット数（フロー別パケット数）
４０４  フロー閾値
４０５  閾値初期化カウンタ
５００  統計情報テーブル
５０１  コア番号
５０２  総受信パケット数
５０３  総送信パケット数
５０４  総破棄パケット数
５０５  前回総受信パケット数
５０６  前回受信パケット数
【図１】
0005611171.tif 000002
【図２】
0005611171.tif 000003
【図３】
0005611171.tif 000004
【図４】
0005611171.tif 000005
【図５】
0005611171.tif 000006
【図６】
0005611171.tif 000007
【図７】
0005611171.tif 000008
【図８】
0005611171.tif 000009
【図９】
0005611171.tif 000010
【図１０】
0005611171.tif 000011