(57)【要約】【課題】従来は、先に到着したパケット処理が終了するまで後続のパケット処理が待たされ、転送効率が低くなってしまうことがある。また、同一の入力情報を持つパケットが集中して入力された場合、並列処理を行うメリットが損なわれてしまう。【解決手段】並列処理を行うパケット処理エレメント１０２−１〜１０２−Ｎの入出力端で、所定のパケット条件毎に独立したカウンタ１０１、１０３を参照・更新可能な場所に設置する。処理対象のパケットは処理開始が可能なパケット処理エレメントによって取り込まれる。シーケンス番号付与部１０２−１−１〜１０２−Ｎ−１は入力パケットにシーケンス番号（入力側カウンタ値）を付与する。シーケンス番号比較部１０２−１−２〜１０２Ｎ−２は処理後のパケットに付与されたシーケンス番号と出力側カウンタ値を比較し、一致した場合にのみ出力する。これによりパケットの転送順序保障が可能となる。【選択図】図１
2008236653.tif 000002
【特許請求の範囲】
【請求項１】
処理パケット入力キューから順次取り出したパケットを複数のパケット処理エレメントに分散入力してそれぞれで並列処理した後、該複数のパケット処理エレメントのそれぞれから処理後のパケットを共通の処理パケット出力キューに積んで出力させるパケット転送システムのパケット転送順序保障方法であって、
前記処理パケット入力キューから順次取り出した異なるパケットを前記複数のパケット処理エレメントに順番に入力する第１のステップと、
前記複数のパケット処理エレメントのそれぞれにおいて、入力パケットの順序保障を行う単位毎にその入力パケットが所定のパケット条件に一致するとき、その入力パケットに対して、前記複数のパケット処理エレメントの間での入力順を示す値のシーケンス番号を付与する第２のステップと、
前記複数のパケット処理エレメントのそれぞれで前記シーケンス番号が付与されたパケットを処理する第３のステップと、
前記複数のパケット処理エレメントのそれぞれにおいて、前記処理後の前記シーケンス番号が付与されたパケットに付与されている前記シーケンス番号と、前記所定のパケット条件に一致するパケットの出力順を示す出力カウンタ値とを比較する第４のステップと、
前記出力カウンタ値に一致するシーケンス番号が付与されている前記処理後のパケットを前記パケット処理エレメントから取り出して前記処理パケット出力キューに積み込む第５のステップと
を含むことを特徴とするパケット転送順序保障方法。
【請求項２】
前記第４のステップによる前記シーケンス番号と前記出力カウンタ値との比較により一致の比較結果が得られたときは、前記出力カウンタ値を次のパケット出力順を示す値に更新する第６のステップを更に含むことを特徴とする請求項１記載のパケット転送順序保障方法。
【請求項３】
前記第４のステップによる前記シーケンス番号と前記出力カウンタ値との比較により一致の比較結果が得られないときは、一定時間待機した後再び前記処理後の前記シーケンス番号が付与されたパケットに付与されている前記シーケンス番号と、前記所定のパケット条件に一致するパケットの出力順を示す出力カウンタ値とを比較することを特徴とする請求項１記載のパケット転送順序保障方法。
【請求項４】
前記所定のパケット条件は、パケット種別、処理内容及び入出力ポートを含むことを特徴とする請求項１乃至３のうちいずれか一項記載のパケット転送順序保障方法。
【請求項５】
処理パケット入力キューから順次取り出したパケットを複数のパケット処理エレメントに分散入力してそれぞれで並列処理した後、該複数のパケット処理エレメントのそれぞれから処理後のパケットを共通の処理パケット出力キューに積んで出力させるパケット転送システムのパケット転送順序保障装置であって、
前記複数のパケット処理エレメントから参照・更新可能であり、入力パケットの転送順序保障を行う単位毎にシーケンス番号を個別管理している複数のカウンタから形成される入力側カウンタ群と、
前記複数のパケット処理エレメントから参照・更新可能であり、前記転送順序保障を行う単位毎（各種条件の組み合わせ毎）に出力可能なシーケンス番号を個別管理し、かつ、前記入力側カウンタ群の複数のカウンタと対を構成する複数のカウンタから形成された出力側カウンタ群と、
前記処理パケット入力キューからパケットを順次取り出して前記複数のパケット処理エレメントに順番に入力するパケット入力手段と、
前記複数のパケット処理エレメントのそれぞれにおいて、入力パケットの順序保障を行う単位毎にその入力パケットが所定のパケット条件に一致するとき、前記入力カウンタ群中の前記所定のパケット条件に一致したカウンタから前記複数のパケット処理エレメントの間での入力順を示す値を読み出して、前記入力パケットにシーケンス番号として付与するシーケンス番号付与手段と、
前記複数のパケット処理エレメントのそれぞれにおいて、処理された後の前記シーケンス番号が付与されたパケットに付与されている前記シーケンス番号と、前記出力カウンタ群中の前記所定のパケット条件に一致したカウンタから読み出したパケットの出力順を示す出力カウンタ値とを比較するシーケンス番号比較手段と、
前記シーケンス番号比較手段で一致する比較結果が得られたシーケンス番号が付与されている前記処理後のパケットを前記パケット処理エレメントから取り出して前記処理パケット出力キューに積み込む出力選択手段と
を有することを特徴とするパケット転送順序保障装置。
【請求項６】
前記シーケンス番号比較手段による前記シーケンス番号と前記出力カウンタ値との比較により一致の比較結果が得られたときは、前記出力カウンタ値を次のパケット出力順を示す値に更新する更新手段を更に有することを特徴とする請求項５記載のパケット転送順序保障装置。
【請求項７】
前記シーケンス番号比較手段による前記シーケンス番号と前記出力カウンタ値との比較により一致の比較結果が得られないときは、一定時間待機した後再び前記処理後の前記シーケンス番号が付与されたパケットに付与されている前記シーケンス番号と、前記所定のパケット条件に一致するパケットの出力順を示す出力カウンタ値とを比較することを特徴とする請求項５記載のパケット転送順序保障装置。
【請求項８】
前記所定のパケット条件は、パケット種別、処理内容及び入出力ポートを含むことを特徴とする請求項５乃至７のうちいずれか一項記載のパケット転送順序保障装置。
【請求項９】
処理パケット入力キューから順次取り出したパケットを複数のパケット処理エレメントに分散入力してそれぞれで並列処理した後、該複数のパケット処理エレメントのそれぞれから処理後のパケットを共通の処理パケット出力キューに積んで出力させるパケット転送システムのパケット転送順序をコンピュータにより保障させるパケット転送順序保障プログラムであって、
前記コンピュータに、
前記処理パケット入力キューから順次取り出した異なるパケットを前記複数のパケット処理エレメントに順番に入力する第１のステップと、
前記複数のパケット処理エレメントのそれぞれにおいて、入力パケットの順序保障を行う単位毎にその入力パケットが所定のパケット条件に一致するとき、その入力パケットに対して、前記複数のパケット処理エレメントの間での入力順を示す値のシーケンス番号を付与する第２のステップと、
前記複数のパケット処理エレメントのそれぞれで前記シーケンス番号が付与されたパケットを処理する第３のステップと、
前記複数のパケット処理エレメントのそれぞれにおいて、前記処理後の前記シーケンス番号が付与されたパケットに付与されている前記シーケンス番号と、前記所定のパケット条件に一致するパケットの出力順を示す出力カウンタ値とを比較する第４のステップと、
前記出力カウンタ値に一致するシーケンス番号が付与されている前記処理後のパケットを前記パケット処理エレメントから取り出して前記処理パケット出力キューに積み込む第５のステップと
を実行させることを特徴とするパケット転送順序保障プログラム。
【請求項１０】
前記第４のステップによる前記シーケンス番号と前記出力カウンタ値との比較により一致の比較結果が得られたときは、前記出力カウンタ値を次のパケット出力順を示す値に更新する第６のステップを更に含むことを特徴とする請求項９記載のパケット転送順序保障プログラム。
【請求項１１】
前記第４のステップによる前記シーケンス番号と前記出力カウンタ値との比較により一致の比較結果が得られないときは、一定時間待機した後再び前記処理後の前記シーケンス番号が付与されたパケットに付与されている前記シーケンス番号と、前記所定のパケット条件に一致するパケットの出力順を示す出力カウンタ値とを比較することを特徴とする請求項９記載のパケット転送順序保障プログラム。
【請求項１２】
前記所定のパケット条件は、パケット種別、処理内容及び入出力ポートを含むことを特徴とする請求項９乃至１１のうちいずれか一項記載のパケット転送順序保障プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はパケット転送順序保障方法、パケット転送順序保障装置及びパケット転送順序保障プログラムに係り、特に並列処理におけるパケット転送順序保障方法、パケット転送順序保障装置及びパケット転送順序保障プログラムに関する。
【背景技術】
【０００２】
パケットが複数のスイッチング用並列処理エレメントに入力されて並列処理するパケット処理装置では、パケット転送順序が入れ替わることがあり、その場合にはそのパケット処理装置から出力されるパケットのうち、中継装置を経てそのパケットの最終の受信処理装置である転送先に届かず廃棄されてしまうものがある。これを防ぐためにパケット転送順序保障を行う必要がある。そこで、従来は、並列処理でのパケット転送順序を保障する方法として、同じ入力情報（例えば、パケット種別、処理内容、入出力ポート番号等）のパケットを、その入力情報を基に同じ処理エレメントに割り当て、シーケンシャルに処理する方法がとられている。
【０００３】
また、パケット転送の順序を保障する方法に類似の方法として、フレームの順序を保障する方法が従来知られている（例えば、特許文献１参照）。この特許文献１には、２台の情報処理装置間を１本以上の通信回線で相互に接続し通信データフレームを１本以上の通信回線に分配してデータ通信を行うデータ通信システムにおいて、送信側システムの送信制御部においてフレームに順序情報を挿入し、受信側システムの受信制御部でフレームの受信時にフレームに挿入された順序情報からそのフレームの順序を判断し、順序を直して収集・受信処理を行うことでフレームの順序保障を行う技術が記載されている。
【０００４】
【特許文献１】特開２００２−９８６６号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかるに、並列処理でのパケット転送順序を保障する上記の従来の方法は、先に到着したパケットの処理時間が長く、後に到着したパケットの処理時間が短い場合は、先に到着したパケット処理が終了するまで後続のパケット処理が待たされ、転送効率が低くなってしまう。また、同一の入力情報を持つパケットが集中して入力された場合、同一処理エレメントで処理を行うためにその処理エレメントに負荷が集中してしまい、並列処理を行うメリットが損なわれてしまう。
【０００６】
また、特許文献１記載のフレームの順序保障を行う方法は、１対１の通信を想定しているので、通信相手単位でフレームの順序保障を行うものであり、多対多通信においてパケット種別、入出力ポート番号で順序保障を行う用途には適用できない。また、特許文献１記載のフレームの順序保障を行う方法は、送信元装置に出力用の、送信先装置に入力用の順序保障機構が揃っていないと順次が保障されず、対向装置に条件（制限）がある。
【０００７】
本発明は以上の点に鑑みなされたもので、順序保障制御を簡単にすることでその処理によるオーバヘッドを極力無くし、かつ、パケット転送効率も落とさないパケット転送順序保障方法、パケット転送順序保障装置及びパケット転送順序保障プログラムを提供することを目的とする。
【０００８】
また、本発明の他の目的は、対向装置に条件（制限）を有することなく、多対多通信においてパケット種別、入出力番号などでパケットの順序保障を行い得るパケット転送順序保障方法、パケット転送順序保障装置及びパケット転送順序保障プログラムを提供することにある。
【課題を解決するための手段】
【０００９】
上記の目的を達成するため、本発明のパケット転送順序保障方法は、処理パケット入力キューから順次取り出したパケットを複数のパケット処理エレメントに分散入力してそれぞれで並列処理した後、複数のパケット処理エレメントのそれぞれから処理後のパケットを共通の処理パケット出力キューに積んで出力させるパケット転送システムのパケット転送順序保障方法であって、
処理パケット入力キューから順次取り出した異なるパケットを複数のパケット処理エレメントに順番に入力する第１のステップと、複数のパケット処理エレメントのそれぞれにおいて、入力パケットの順序保障を行う単位毎にその入力パケットが所定のパケット条件に一致するとき、その入力パケットに対して、複数のパケット処理エレメントの間での入力順を示す値のシーケンス番号を付与する第２のステップと、複数のパケット処理エレメントのそれぞれでシーケンス番号が付与されたパケットを処理する第３のステップと、複数のパケット処理エレメントのそれぞれにおいて、処理後のシーケンス番号が付与されたパケットに付与されているシーケンス番号と、所定のパケット条件に一致するパケットの出力順を示す出力カウンタ値とを比較する第４のステップと、出力カウンタ値に一致するシーケンス番号が付与されている処理後のパケットをパケット処理エレメントから取り出して処理パケット出力キューに積み込む第５のステップとを含むことを特徴とする。
【００１０】
また、上記の目的を達成するため、本発明のパケット転送順序保障装置は、処理パケット入力キューから順次取り出したパケットを複数のパケット処理エレメントに分散入力してそれぞれで並列処理した後、複数のパケット処理エレメントのそれぞれから処理後のパケットを共通の処理パケット出力キューに積んで出力させるパケット転送システムのパケット転送順序保障装置であって、
複数のパケット処理エレメントから参照・更新可能であり、入力パケットの転送順序保障を行う単位毎にシーケンス番号を個別管理している複数のカウンタから形成される入力側カウンタ群と、複数のパケット処理エレメントから参照・更新可能であり、パケット転送順序保障を行う単位毎（各種条件の組み合わせ毎）に出力可能なシーケンス番号を個別管理し、かつ、入力側カウンタ群の複数のカウンタと対を構成する複数のカウンタから形成された出力側カウンタ群と、処理パケット入力キューからパケットを順次取り出して複数のパケット処理エレメントに順番に入力するパケット入力手段と、複数のパケット処理エレメントのそれぞれにおいて、入力パケットの順序保障を行う単位毎にその入力パケットが所定のパケット条件に一致するとき、入力カウンタ群中の所定のパケット条件に一致したカウンタから複数のパケット処理エレメントの間での入力順を示す値を読み出して、入力パケットにシーケンス番号として付与するシーケンス番号付与手段と、複数のパケット処理エレメントのそれぞれにおいて、処理された後のシーケンス番号が付与されたパケットに付与されているシーケンス番号と、出力カウンタ群中の所定のパケット条件に一致したカウンタから読み出したパケットの出力順を示す出力カウンタ値とを比較するシーケンス番号比較手段と、シーケンス番号比較手段で一致する比較結果が得られたシーケンス番号が付与されている処理後のパケットをパケット処理エレメントから取り出して処理パケット出力キューに積み込む出力選択手段とを有することを特徴とする。
【００１１】
また、上記の目的を達成するため、本発明のパケット転送順序保障プログラムは、上記の本発明のパケット転送順序保障方法の各ステップをコンピュータにより実行させることを特徴とする。
【００１２】
本発明では、パケット処理エレメントの入出力端で、順序保障を必要とする所定のパケット条件（パケット種別、処理内容、入出力ポート番号等）毎に独立した複数のカウンタを、並列処理を行う各パケット処理エレメントから参照・更新可能な場所に設置する。処理対象のパケットは処理開始が可能なパケット処理エレメントによって取り込まれる（ラウンドロビン等のパケット取り込み制御は行わない）。パケット処理エレメント入力端では入力パケットにシーケンス番号（入力側カウンタ値）を付与し、パケット処理エレメント出力端では処理後のパケットに付与されたシーケンス番号と出力側カウンタ値を比較し、一致した場合にのみ出力し、そうでなければカウンタ値が一致するまで待機、比較を繰り返す。
【００１３】
これにより中間の並列で行われるパケット処理では順序保障を意識することなく自由に処理を行え、順序保障を行うべきパケットについて並列処理が可能となり、出力時にはパケット転送順序保障が行われ、並列処理の負荷分散が可能となる。すなわち、本発明は、簡単な仕組みにより並列処理が可能なパケット処理装置でパケットの入力順序通りに出力する方法（順序保障）と、並列処理エレメントの有効活用を行うことを実現し、その制御による転送効率劣化を低減することが可能となる。
【発明の効果】
【００１４】
本発明によれば、パケットがシーケンス番号を付与されてから実際に順序保障を行う部分（出力直前）までの間、パケットの追い越しを気にせず自由に処理できるため、従来のパケット転送順序保障方法と比べてパケット転送効率劣化を低減することができる。
【００１５】
また、本発明によれば、シーケンス番号付与とシーケンス番号比較がカウンタとその値との一致比較のみで行われるため、従来のパケット転送順序保障方法と比べて順序保障論理の単純化が可能となる。
【発明を実施するための最良の形態】
【００１６】
次に、本発明を実施するための最良の形態について図面と共に詳細に説明する。図１は本発明になるパケット転送順次保障方法及び保障装置の一実施の形態の説明図を示す。図１に示すように、本実施の形態では、前段からの入力パケットを貯める処理パケット入力キュー１００、処理パケット入力キュー１００からパケットを引き取りそのパケットの処理を行って処理パケット出力キュー１０４にパケットを渡すＮ個（Ｎは２以上の自然数）のパケット処理エレメント１０２−１〜１０２−Ｎ、パケット処理エレメント１０２−１〜１０２−Ｎで処理を終えたパケットを後段へ渡すためにパケットを貯める処理パケット出力キュー１０４とを配置する。
【００１７】
また、パケット処理エレメント１０２−１〜１０２−Ｎの入口には、入力パケットの順序保障を行う単位毎（各種条件の組み合わせ毎）にシーケンス番号を個別管理している複数のカウンタから形成される入力側カウンタ群１０１から、シーケンス番号を読み出して入力パケットに付与するシーケンス番号付与部１０２−１−１〜１０２−Ｎ−１が配置され、また、パケット処理エレメントの出口には、入力側カウンタ群１０１と同じく順序保障を行う単位毎（各種条件の組み合わせ毎）に出力可能なシーケンス番号を個別管理している複数のカウンタから形成された出力側カウンタ群１０３を参照し、処理パケット出力キュー１０４への積み込みが可能かチェックするシーケンス番号比較部１０２−１−２〜１０２−Ｎ−２が配置される。
【００１８】
入力側カウンタ群１０１と出力側カウンタ群１０３とは、全てのパケット処理エレメント１０２−１〜１０２−Ｎから参照・更新可能な位置に同じ条件下で対になるように配置され、各々のカウンタは、同時に処理することが可能な数Ｎ以上の値を表すことができるようにする。
【００１９】
次に、本発明における順序保障の基本動作を、図２の説明図と図３のフローチャートを併せ参照して説明する。なお、図２中、図１と同一構成部分には同一符号を付してある。前提条件として入力側カウンタ群１０１のカウンタ１０１−１〜１０１−Ｎと、出力側カウンタ群１０３のカウンタ１０３−１〜１０３−Ｎとのうち、対になっているカウンタ（１０１−１と１０３−１、１０１−２と１０３−２、・・・、１０１−Ｎと１０３−Ｎ）の値は初期状態で同一とし、またカウンタ更新は同じルール（１増加）に従って更新することとする。
【００２０】
まず、図１のＸ番目（Ｘは１〜Ｎの自然数）のパケット処理エレメント１０２−Ｘ内のシーケンス番号付与部１０２−Ｘ−１は、図２（Ａ）に示すように、処理パケット入力キュー１００からパケット２００を取り出し（図３のステップＳ１）、その取り出しの際にシーケンス番号付与部１０２−Ｘ−１は入力側カウンタ群１０１中の、取り出したパケットの条件（パケット種別、処理内容、入出力ポート等）に一致するカウンタ（仮にカウンタ１０１−１とする）から値を読み取る（図３のステップＳ２）。続いて、シーケンス番号付与部１０２−Ｘ−１は、値を読み取ったカウンタ１０１−１の値を同一条件で入力されてくる後続パケットに同じシーケンス番号を付与しないように更新し（図３のステップＳ３）、また読み取ったカウンタ１０１−１の値をシーケンス番号として、パケット２００に付与する（図３のステップＳ４）。
【００２１】
続いて、シーケンス番号を付与されたパケット２００は、図２（Ｂ）に示すように、パケット処理エレメント１０２−Ｘ内でその入力順序を意識することなく自由に処理される（図３のステップＳ５）。パケット２００のパケット処理を終え、処理パケット出力キュー１０４に渡す前にシーケンス番号比較部１０２−Ｘ−２は、出力側カウンタ群１０３中の、パケット２００に値を付加したカウンタ１０１−１と対となるカウンタ１０３−１から値を読み取り（図３のステップＳ６）、パケットに付与されたシーケンス番号と一致比較を行う（図３のステップＳ７）。
【００２２】
その一致比較の結果、一致していなければ一定時間待機して（図３のステップＳ８）、再度カウンタ１０３−１の値を読み込んで、一致比較を行う（図３のステップＳ６、Ｓ７）。この動作を一致するまで繰り返す。また、一致比較の結果、一致していれば図２（Ｃ）に示すように、一致比較に使用したカウンタ１０３−１の値を更新し（図３のステップＳ９）、処理パケット２００を処理パケット出力キュー１０４に積む（図３のステップＳ１０）。パケット２００を処理パケット出力キュー１０４に積み込んだ場合は、この基本動作によってパケットの順序保障が行われる。
【００２３】
次に、順序保障を行わなければならないパケット（同一条件のパケット）が複数のパケット処理エレメントで並列処理される場合について図４を用いて説明する。処理パケット入力キュー１００にパケット４００、４０１が積まれているとする。この２つのパケット４００、４０１は処理を行っていないパケット処理エレメントによって空いている順に取り出される（ラウンドロビンなどの取り出し制御は行わない）。
【００２４】
ここで、図４に示すように、パケット４００、４０１がそれぞれパケット処理エレメント１０２−Ｘ、１０２−Ｙに順に取り出されたとする。パケット処理エレメント１０２−Ｘのシーケンス番号付与部１０２−Ｘ−１は、入力側カウンタ群１０１のパケット４００（およびパケット４０１）の条件（パケット種別、処理内容、入出力ポート等）に一致するカウンタ（仮に１０１−１とする）からシーケンス番号ｎを読み出してパケット４００に付与し、カウンタ１０１−１の値を（ｎ＋１）に更新する。少し遅れてパケット処理エレメント１０２−Ｙのシーケンス番号付与部１０２−Ｙ−１は同様にカウンタ１０１−１から更新した値（ｎ＋１）を読み出してパケット４０１にシーケンス番号として付与し、カウンタ１０１−１の値を（ｎ＋２）に更新する。
【００２５】
パケット処理エレメント１０２−Ｘ、１０２−Ｙで行われるパケット処理は、それぞれ他のパケット処理エレメントで処理されているパケットを意識することなく並列処理される。パケット４００の処理時間がパケット４０１の処理時間よりも長い場合には、シーケンス番号比較部１０２−Ｘ−２、１０２−Ｙ−２に到達するまでにその順序が入れ替わる。
【００２６】
この場合、先にシーケンス番号比較部１０２−Ｙ−２にパケット４０１が到達し、シーケンス番号比較部１０２−Ｙ−２でパケット４０１に付与された値と、その値を付与したカウンタ１０１−１と対になる出力側カウンタ群内のカウンタ１０３−１の値を比較すると、パケット４０１に付与された値は（ｎ＋１）でカウンタ１０３−１の値はｎであるから両者は不一致となり、カウンタ１０３−１の値がパケット４０１に付与されたシーケンス番号になるまで一定時間待機と比較を交互に繰り返す。
【００２７】
パケット処理エレメント１０２−Ｙでパケット４０１が待機と比較を行っている間に、パケット４００がシーケンス番号比較部１０２−Ｘ−２に到達し、パケット４００に付与された値とカウンタ１０３−１の値とを比較する。この場合は、パケット４００に付与されたシーケンス番号の値はｎでカウンタ１０３−１の値はｎであるから両者は値が一致し、パケット処理エレメント１０２−Ｘは処理パケット出力キュー１０４にパケット４００を積み込む。
【００２８】
その後、カウンタ１０３−１の値は（ｎ＋１）に更新されるので、カウンタ１０３−１の値がパケット４０１に付与されたシーケンス番号と一致するので、パケット４０１がパケット４００の次に処理パケット出力キュー１０４に積み込まれる。このようにして順序保障の必要なパケットはその順序を保つことができる。
【００２９】
次に、順序保障を行う必要のないパケット（異なる条件のパケット）が複数のパケット処理エレメントで並列処理される場合について図５を用いて説明する。処理パケット入力キューにパケット５００、５０１が積まれているとする。この２つのパケットは前述と同様に、処理を行っていないパケット処理エレメントによって空いている順に取り出される。ここで、パケット５００、５０１がそれぞれパケット処理エレメント１０２−Ｘ、１０２−Ｙに順に取り出されたとする。
【００３０】
パケット処理エレメント１０２−Ｘのシーケンス番号付与部１０２−Ｘ−１は、入力側カウンタ群１０１のパケット５００の条件に一致するカウンタ（仮に１０１−１とする）からシーケンス番号ｎ１を読み出してパケット５００に付与し、カウンタ１０１−１の値をｎ２に更新する。少し遅れてパケット処理エレメント１０２−Ｙのシーケンス番号付与部１０２−Ｙ−１はパケット５０１の条件に一致したカウンタ（仮に１０１−２とする）からシーケンス番号ｎ２を読み出してパケット５０１に付与し、カウンタ１０１−２の値を更新する。パケット処理エレメント１０２−Ｘ、１０２−Ｙで行われるパケット処理はそれぞれ、他のパケット処理エレメントで処理されているパケットを意識することなく並列処理される。
【００３１】
パケット５００の処理がパケット５０１の処理よりも長い場合には、シーケンス番号比較部１０２−Ｘ−２、１０２−Ｙ−２に到達するまでに、パケット５００とパケット５０１の順序が入れ替わる。先にシーケンス番号比較部１０２−Ｙ−２にパケット５０１が到達し、シーケンス番号比較部１０２−Ｙ−２でパケット５０１に付与された値ｎ２と、その値を付与したカウンタ１０１−２と対になる出力側カウンタ群１０３内のカウンタ１０３−２の値ｎ２とを比較すると、両者の値が一致して後にシーケンス番号比較部１０３−１に到達するパケット５００を待つことなく処理パケット出力キュー１０４に積まれる。その後、パケット５００も同様の動作で処理パケット出力キュー１０４に積まれる。この結果、順序保証が不要なパケット５００、５０１の場合は、パケットの転送順序は保たれないまま出力される。
【００３２】
このようにして、本実施の形態によれば、順序保障の必要／不要のパケットが混在する場合でも前述により順序保障が必要なパケットのみの順序保障を行うことができる。これにより、本実施の形態では、簡単な仕組みにより並列処理が可能なパケット処理装置でパケットの入力順序通りに出力する方法（順序保障）と、並列に配置されたパケット処理エレメントの有効活用を行うことを実現し、その制御による転送効率劣化を低減することが可能となる。また、本実施の形態では、パケット処理エレメント１０２−１〜１０２−Ｎのそれぞれの内部にシーケンス番号付与部１０２−１−１〜１０２−Ｎ−１と、シーケンス番号比較部１０２−１−２〜１０２−Ｎ−２というパケット転送順序保障機構が設けられているため、対向装置に条件（制限）がなく、パケット種別、入出力番号などでパケットの順序保障を行っているので、多対多通信に適用できる。
【００３３】
なお、上記の実施の形態では、パケットの条件としてパケット種別、処理内容、入出力ポートを用い、これらの全てに一致するときパケットの条件を満足する（パケットの条件に一致する）としてカウンタ値をシーケンス番号として付与している。しかし、パケットの条件が分類できない場合は、上記の３つのいずれか一つでもよいが、条件分けが可能であれば、上記の３つの条件に限らず、できるだけ細かく分類することが望ましい。それは、同一パケットの条件に一致しない場合は、パケットの追い越しが発生しても、パケットの順序を保障しなくても問題が起こらず（パケットの順序が入れ替わることによる廃棄が起きないため）、逆に粗い条件分けであると、パケットの追い越しの発生が発生しても、そのパケットの順序が殆どの場合保障されるため、パケットの追い越しの問題が起きないパケットの処理を待たせることになり、無駄な処理待ち時間を作ってしまうからである。
【００３４】
なお、本発明は上記の実施の形態に限定されるものではなく、例えば競合制御としても利用できる。競合制御を行うべき動作を開始する以前にシーケンス番号を付与し、競合制御が必要な動作の直前にシーケンス番号比較を行うことで競合制御が必要な動作はある１つの処理エレメントから起動されることが許可される。また、本発明は、図３の各ステップの手順をコンピュータのソフトウェアにより実行させるパケット転送順序保障プログラムも包含するものである。
【図面の簡単な説明】
【００３５】
【図１】本発明のパケット転送順次保障方法及び保障装置の一実施の形態の説明図である。
【図２】本発明における順序保障の基本動作の説明図である。
【図３】本発明における順序保障の基本動作説明用フローチャートである。
【図４】順序保障を行わなければならないパケット（同一条件のパケット）が複数のパケット処理エレメントで並列処理される場合の説明図である。
【図５】順序保障を行う必要のないパケット（異なる条件のパケット）が複数のパケット処理エレメントで並列処理される場合の説明図である。
【符号の説明】
【００３６】
１００  処理パケット入力キュー
１０１  入力側カウンタ群
１０１−１〜１０１−Ｎ  入力側カウンタ
１０２−１〜１０２−Ｎ  パケット処理エレメント
１０２−１−１、１０２−２−１、１０２−Ｎ−１、１０２−Ｘ−１、１０２−Ｙ−１  シーケンス番号付与部
１０２−１−２、１０２−２−２、１０２−Ｎ−２、１０２−Ｘ−２、１０２−Ｙ−２  シーケンス番号比較部
１０３  出力側カウンタ群
１０３−１〜１０３−Ｎ  出力側カウンタ
１０４  処理パケット出力キュー
４００、４０１、５００、５０１  パケット
【図１】
2008236653.tif 000003
【図２】
2008236653.tif 000004
【図３】
2008236653.tif 000005
【図４】
2008236653.tif 000006
【図５】
2008236653.tif 000007