(57)【特許請求の範囲】
【請求項１】
パケットを転送する転送プロセッサを複数備えるパケット処理装置において、
受信した各前記パケットの処理の有無を示す処理状態を示すと共に転送順序を転送経路別に示す制御情報を生成する手段を備え、
各前記転送プロセッサが、
個別に、前記制御情報に示される処理状態を参照してパケット処理を行うと共に、前記転送経路別の転送順序に基づいて、各前記パケットを転送する手段を備えることを特徴とするパケット処理装置。
【請求項２】
前記制御情報が、各前記パケット毎に、当該パケットに対するパケット処理が未処理であるのか処理済であるのかを示す情報と、当該パケットが排他制御中であるか否かを示す情報を含み、
各前記転送プロセッサが、
個別に、各前記パケットに対し前記パケット処理を実行する手段を備え、
前記制御情報に示される、前記パケット処理が未処理でありかつ前記排他制御中でない前記パケットに対して、前記パケット処理を実行することを特徴とする請求項１に記載のパケット処理装置。
【請求項３】
各前記転送プロセッサが、
前記制御情報に示される各前記パケットの情報を、当該パケットに対する前記パケット処理の開始時に、当該パケットが前記排他制御中である旨を示すように更新し、当該パケットに対する前記パケット処理の完了時に、当該パケットが前記排他制御中ではなくかつ前記パケット処理が処理済である旨を示すように更新する手段を備えることを特徴とする請求項２に記載のパケット処理装置。
【請求項４】
各前記転送プロセッサが、
前記パケットに対する前記パケット処理の終了時点において、当該パケットと伝送経路が同一である転送待機中の他のパケットが存在しない場合、前記パケット処理を終了した前記パケットを転送することを特徴とする請求項３に記載のパケット処理装置。
【請求項５】
前記制御情報が、各前記パケット毎に、かつ当該パケットに対し各前記転送プロセッサの少なくとも１つにより処理可能である各処理毎に、各前記処理が未処理であるのか処理済であるのかを示す情報を含み、
各前記転送プロセッサが、
前記制御情報に基づいて、前記排他制御中でない前記パケットに対して、前記パケットにおいて未処理でありかつ当該転送プロセッサにより処理可能な前記処理を実行することを特徴とする請求項２から請求項４のいずれか１つに記載のパケット処理装置。
【請求項６】
各前記転送プロセッサにおいて機能する各タスクのそれぞれに、前記制御情報に基づいて、各前記パケットに対する前記パケット処理を実行させることを特徴とする請求項２から請求項５のいずれか１つに記載のパケット処理装置。
【請求項７】
前記制御情報が、各前記パケット毎に、かつ当該パケットに対し各前記転送プロセッサにおいて機能する各タスクの少なくとも１つにより処理可能である各処理毎に、各前記処理が未処理であるのか処理済であるのかを示す情報を含み、
各前記転送プロセッサにおいて機能する各タスクのそれぞれに、前記制御情報に基づいて、前記排他制御中でない前記パケットに対して、前記パケットにおいて未処理でありかつ当該タスクにより処理可能な前記処理を実行させることを特徴とする請求項２から請求項４のいずれか１つに記載のパケット処理装置。
【請求項８】
各前記転送プロセッサにおいて機能する各タスクのそれぞれに、前記制御情報に示される転送経路別の転送順序に基づいて、各前記パケットの転送を実行させることを特徴とする請求項１から請求項７のいずれか１つに記載のパケット処理装置。
【請求項９】
パケットを転送する転送プロセッサを複数備えるパケット処理装置のパケット転送方法において、
受信した各前記パケットの処理の有無を示す処理状態を示すと共に転送順序を転送経路別に示す制御情報を生成するステップを備え、
各前記転送プロセッサが、
個別に、前記制御情報に示される処理状態を参照してパケット処理を行うと共に、前記転送経路別の転送順序に基づいて、各前記パケットを転送するステップを備えることを特徴とするパケット転送方法。
【請求項１０】
前記制御情報が、各前記パケット毎に、当該パケットに対するパケット処理が未処理であるのか処理済であるのかを示す情報と、当該パケットが排他制御中であるか否かを示す情報を含み、
各前記転送プロセッサが、
個別に、前記制御情報に示される、前記パケット処理が未処理でありかつ前記排他制御中でない前記パケットに対して、前記パケット処理を実行するステップを備えることを特徴とする請求項９に記載のパケット転送方法。
【請求項１１】
各前記転送プロセッサが、
前記制御情報に示される各前記パケットの情報を、当該パケットに対する前記パケット処理の開始時に、当該パケットが前記排他制御中である旨を示すように更新し、当該パケットに対する前記パケット処理の完了時に、当該パケットが前記排他制御中ではなくかつ前記パケット処理が処理済である旨を示すように更新するステップを備えることを特徴とする請求項１０に記載のパケット転送方法。
【請求項１２】
各前記転送プロセッサが、
前記パケットに対する前記パケット処理の終了時点において、当該パケットと伝送経路が同一である転送待機中の他のパケットが存在しない場合、前記パケット処理を終了した前記パケットを転送することを特徴とする請求項１１に記載のパケット転送方法。
【請求項１３】
前記制御情報が、各前記パケット毎に、かつ当該パケットに対し各前記転送プロセッサの少なくとも１つにより処理可能である各処理毎に、各前記処理が未処理であるのか処理済であるのかを示す情報を含み、
各前記転送プロセッサが、
前記制御情報に基づいて、前記排他制御中でない前記パケットに対して、前記パケットにおいて未処理でありかつ当該転送プロセッサにより処理可能な前記処理を実行することを特徴とする請求項１０から請求項１２のいずれか１つに記載のパケット転送方法。
【請求項１４】
各前記転送プロセッサにおいて機能する各タスクのそれぞれに、前記制御情報に基づいて、各前記パケットに対する前記パケット処理を実行させることを特徴とする請求項１０から請求項１３のいずれか１つに記載のパケット転送方法。
【請求項１５】
前記制御情報が、各前記パケット毎に、かつ当該パケットに対し各前記転送プロセッサにおいて機能する各タスクの少なくとも１つにより処理可能である各処理毎に、各前記処理が未処理であるのか処理済であるのかを示す情報を含み、
各前記転送プロセッサにおいて機能する各タスクのそれぞれに、前記制御情報に基づいて、前記排他制御中でない前記パケットに対して、前記パケットにおいて未処理でありかつ当該タスクにより処理可能な前記処理を実行させることを特徴とする請求項１０から請求項１２のいずれか１つに記載のパケット転送方法。
【請求項１６】
各前記転送プロセッサにおいて機能する各タスクのそれぞれに、前記制御情報に示される転送経路別の転送順序に基づいて、各前記パケットの転送を実行させることを特徴とする請求項９から請求項１５のいずれか１つに記載のパケット転送方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、パケットに対する処理を分散処理するパケット処理装置に関し、特に、転送経路別の転送順序に基づいて各パケットを転送するパケット処理装置とそのパケット転送方法に関する。
【０００２】
【従来の技術】
インターネットの普及とＣＡＴＶ、ＡＤＳＬ、光ファイバーといった広帯域アクセス網の普及により、インターネット上を流れるトラヒック量が増大している。インターネット上のルータやサーバ等のパケット処理装置は、装置の高速化や負荷分散処理を用いて、トラヒックの増加に対応している。
【０００３】
こうしたトラヒックの増加に対応する従来技術として、特開２０００−２２２３７４号公報に開示された負荷分散型パケット並列処理装置がある。
【０００４】
この従来技術は、複数のパケットプロセッサを用いてパケット処理を行ない、かつ１つのパケットプロセッサに負荷が集中しないように、各パケットプロセッサの負荷状況を確認しながら、最も負荷の軽いパケットプロセッサへパケットを配分するパケット処理装置を提案している。これにより、各パケットプロセッサの負荷が平均化されるという効果を得ている。
【０００５】
ここでパケット処理とは、転送するパケットのヘッダ部の書き換え処理や、そのパケットの送信に用いるポートを適正に選択する等の処理である。また、パケットプロセッサとは、パケット処理装置内において、こうしたパケット処理やパケットの転送を実行するプロセッサである。
【０００６】
【発明が解決しようとする課題】
しかし、上述した従来技術では、フロー（転送経路）毎の転送順序に基づいて各パケットを正しく転送することができいという問題点があった。
【０００７】
つまり、特開２０００−２２２３７４号公報の従来の技術では、各パケットプロセッサの負荷状況のみに基づいて、各パケットプロセッサに対するパケットの分配を判断している。このため、同一の端末の同一のアプリケーションから発せられた複数のＩＰパケット等の、フロー（転送経路）が同一の複数のパケットが、異なるパケットプロセッサで処理される可能性がある。そして、各パケットプロセッサにおける負荷はそれぞれに異なるため、各パケットプロセッサの処理時間のばらつきにより各パケットの順序の逆転が生じることがあった。
【０００８】
本発明の目的は、上記従来技術の欠点を解決し、複数のパケットプロセッサにより処理を分散すると共に、転送経路毎の転送順序に基づいて各パケットを転送することのできるパケット処理装置とそのパケット転送方法を提供することにある。
【０００９】
【課題を解決するための手段】
上記目的を達成するため本発明のパケット処理装置は、パケットを転送する転送プロセッサを複数備えるパケット処理装置において、受信した各前記パケットの処理の有無を示す処理状態を示すと共に転送順序を転送経路別に示す制御情報を生成する手段を備え、各前記転送プロセッサが、個別に、前記制御情報に示される処理状態を参照してパケット処理を行うと共に、前記転送経路別の転送順序に基づいて、各前記パケットを転送する手段を備えることを特徴とする。
【００１０】
請求項２の本発明のパケット処理装置は、前記制御情報が、各前記パケット毎に、当該パケットに対するパケット処理が未処理であるのか処理済であるのかを示す情報と、当該パケットが排他制御中であるか否かを示す情報を含み、各前記転送プロセッサが、個別に、各前記パケットに対し前記パケット処理を実行する手段を備え、前記制御情報に示される、前記パケット処理が未処理でありかつ前記排他制御中でない前記パケットに対して、前記パケット処理を実行することを特徴とする。
【００１１】
請求項３の本発明のパケット処理装置は、各前記転送プロセッサが、前記制御情報に示される各前記パケットの情報を、当該パケットに対する前記パケット処理の開始時に、当該パケットが前記排他制御中である旨を示すように更新し、当該パケットに対する前記パケット処理の完了時に、当該パケットが前記排他制御中ではなくかつ前記パケット処理が処理済である旨を示すように更新する手段を備えることを特徴とする。
【００１２】
請求項４の本発明のパケット処理装置は、各前記転送プロセッサが、前記パケットに対する前記パケット処理の終了時点において、当該パケットと伝送経路が同一である転送待機中の他のパケットが存在しない場合、前記パケット処理を終了した前記パケットを転送することを特徴とする。
【００１３】
請求項５の本発明のパケット処理装置は、前記制御情報が、各前記パケット毎に、かつ当該パケットに対し各前記転送プロセッサの少なくとも１つにより処理可能である各処理毎に、各前記処理が未処理であるのか処理済であるのかを示す情報を含み、各前記転送プロセッサが、前記制御情報に基づいて、前記排他制御中でない前記パケットに対して、前記パケットにおいて未処理でありかつ当該転送プロセッサにより処理可能な前記処理を実行することを特徴とする。
【００１４】
請求項６の本発明のパケット処理装置は、各前記転送プロセッサにおいて機能する各タスクのそれぞれに、前記制御情報に基づいて、各前記パケットに対する前記パケット処理を実行させることを特徴とする。
【００１５】
請求項７の本発明のパケット処理装置は、前記制御情報が、各前記パケット毎に、かつ当該パケットに対し各前記転送プロセッサにおいて機能する各タスクの少なくとも１つにより処理可能である各処理毎に、各前記処理が未処理であるのか処理済であるのかを示す情報を含み、各前記転送プロセッサにおいて機能する各タスクのそれぞれに、前記制御情報に基づいて、前記排他制御中でない前記パケットに対して、前記パケットにおいて未処理でありかつ当該タスクにより処理可能な前記処理を実行させることを特徴とする。
【００１６】
請求項８の本発明のパケット処理装置は、各前記転送プロセッサにおいて機能する各タスクのそれぞれに、前記制御情報に示される転送経路別の転送順序に基づいて、各前記パケットの転送を実行させることを特徴とする。
【００１７】
請求項９の本発明のパケット転送方法は、パケットを転送する転送プロセッサを複数備えるパケット処理装置のパケット転送方法において、受信した各前記パケットの処理の有無を示す処理状態を示すと共に転送順序を転送経路別に示す制御情報を生成するステップを備え、各前記転送プロセッサが、個別に、前記制御情報に示される処理状態を参照してパケット処理を行うと共に、前記転送経路別の転送順序に基づいて、各前記パケットを転送するステップを備えることを特徴とする。
【００１８】
請求項１０の本発明のパケット転送方法は、前記制御情報が、各前記パケット毎に、当該パケットに対するパケット処理が未処理であるのか処理済であるのかを示す情報と、当該パケットが排他制御中であるか否かを示す情報を含み、各前記転送プロセッサが、個別に、前記制御情報に示される、前記パケット処理が未処理でありかつ前記排他制御中でない前記パケットに対して、前記パケット処理を実行するステップを備えることを特徴とする。
【００１９】
請求項１１の本発明のパケット転送方法は、各前記転送プロセッサが、前記制御情報に示される各前記パケットの情報を、当該パケットに対する前記パケット処理の開始時に、当該パケットが前記排他制御中である旨を示すように更新し、当該パケットに対する前記パケット処理の完了時に、当該パケットが前記排他制御中ではなくかつ前記パケット処理が処理済である旨を示すように更新するステップを備えることを特徴とする。
【００２０】
請求項１２の本発明のパケット転送方法は、各前記転送プロセッサが、前記パケットに対する前記パケット処理の終了時点において、当該パケットと伝送経路が同一である転送待機中の他のパケットが存在しない場合、前記パケット処理を終了した前記パケットを転送することを特徴とする。
【００２１】
請求項１３の本発明のパケット転送方法は、前記制御情報が、各前記パケット毎に、かつ当該パケットに対し各前記転送プロセッサの少なくとも１つにより処理可能である各処理毎に、各前記処理が未処理であるのか処理済であるのかを示す情報を含み、各前記転送プロセッサが、前記制御情報に基づいて、前記排他制御中でない前記パケットに対して、前記パケットにおいて未処理でありかつ当該転送プロセッサにより処理可能な前記処理を実行することを特徴とする。
【００２２】
請求項１４の本発明のパケット転送方法は、各前記転送プロセッサにおいて機能する各タスクのそれぞれに、前記制御情報に基づいて、各前記パケットに対する前記パケット処理を実行させることを特徴とする。
【００２３】
請求項１５の本発明のパケット転送方法は、前記制御情報が、各前記パケット毎に、かつ当該パケットに対し各前記転送プロセッサにおいて機能する各タスクの少なくとも１つにより処理可能である各処理毎に、各前記処理が未処理であるのか処理済であるのかを示す情報を含み、各前記転送プロセッサにおいて機能する各タスクのそれぞれに、前記制御情報に基づいて、前記排他制御中でない前記パケットに対して、前記パケットにおいて未処理でありかつ当該タスクにより処理可能な前記処理を実行させることを特徴とする。
【００２４】
請求項１６の本発明のパケット転送方法は、各前記転送プロセッサにおいて機能する各タスクのそれぞれに、前記制御情報に示される転送経路別の転送順序に基づいて、各前記パケットの転送を実行させることを特徴とする。
【００２６】
【発明の実施の形態】
以下、本発明の実施の形態について図面を参照して詳細に説明する。
【００２７】
図１は、本発明の第１の実施の形態によるパケット処理装置１０００の構成を示すブロック図である。
【００２８】
本実施の形態のパケット処理装置１０００は、各パケットの転送順序を転送経路別に示す制御情報を生成し、その制御情報を複数のパケットプロセッサ（転送プロセッサ）３０ａ、３０ｂがそれぞれ個別に参照して各パケットを転送経路別の転送順序に基づいて転送することを特徴とする。これにより、複数のパケットプロセッサ３０ａ、３０ｂによる負荷分散と共に、転送経路毎の転送順序に基づく各パケットの転送を実現する。
【００２９】
また本実施の形態では、各パケット毎の、パケット処理に関する情報を含めて、上述の制御情報を生成することにより、制御情報を各パケットプロセッサ３０ａ、３０ｂによるパケット処理の負荷分散にも用いる。
【００３０】
ここで、パケット処理に関する情報とは、各パケットにおいて、パケット処理が未処理であるのか処理済であるのかを示す情報や、そのパケットが排他制御中であるか否かを示す情報等である。また、各パケットプロセッサ３０ａ、３０ｂは、それぞれ個別にこの制御情報を、そのパケットプロセッサ３０ａ、３０ｂにおけるパケット処理等の進行に応じて随時更新する。
【００３１】
図１を参照すると、本実施の形態のパケット処理装置１０００は、パケットインタフェース１０、受信プロセッサ２０、複数のパケットプロセッサ３０ａ、３０ｂ、メモリアクセス調停部５０、メインメモリ６０を備えている。
【００３２】
また、受信プロセッサ２０及び各パケットプロセッサ３０ａ、３０ｂは、バス４０によりパケットインタフェース１０と接続され、バス４１によりメモリアクセス調停部５０と接続されている。
【００３３】
ここで図１では、２個のパケットプロセッサ３０ａ、３０ｂが示されているが、その個数を限定する必要はなく、パケットプロセッサを２個以上の任意の個数（３個、４個、…）備える場合においても本実施の形態と同様にして実施することができる。
【００３４】
パケットインタフェース１０は、外部の装置やネットワークとのパケット入出力を行なう。パケットインタフェース１０は、外部から受信したパケットを受信プロセッサ２０に送り、また、外部に送信するパケットを各パケットプロセッサ３０ａ、３０ｂから受け付けて送信する。
【００３５】
受信プロセッサ２０は、受信したパケットをメインメモリ６０に格納すると共に、そのパケットの受信に応じてメインメモリ６０中に格納されている制御情報を更新する。
【００３６】
各パケットプロセッサ（転送プロセッサ）３０ａ、３０ｂは、受信した各パケットに対してパケット処理やパケットの転送を行なうためのプロセッサである。パケット処理は、例えばＩＰ（Internet Protocol）パケット処理等を行なう。
【００３７】
メモリアクセス調停部５０は、受信プロセッサ２０及び各パケットプロセッサ３０ａ、３０ｂからメインメモリ６０への、メモリアクセス調停を行なう。
【００３８】
メインメモリ６０は、受信プロセッサ２０及び各パケットプロセッサ３０ａ、３０ｂからのアクセスを受け付けて、受信パケットや送信パケットまたパケット処理等で使用する制御情報等の各種データの入力や更新を受け付けて、これらのデータを保持する。
【００３９】
次に、本実施の形態の動作を説明する。ここでは、各パケットをＩＰパケットとし、パケット処理をＩＰパケット処理とする場合を例に説明する。
【００４０】
図５は、本実施の形態の受信プロセッサ２０の動作を説明するためのフローチャートであり、図６は、本実施の形態の各パケットプロセッサ３０ａ、３０ｂのパケット処理の動作を説明するためのフローチャートであり、図７は、本実施の形態のパケットプロセッサ３０ａ、３０ｂのパケット送信の動作を説明するためのフローチャートである。
【００４１】
また、図１においては、本実施の形態のパケット処理装置１０００内のＩＰパケットの処理の流れを、パケットフロー７０により示している。
【００４２】
また図２は、本実施の形態によるパケット処理装置１０００の実施例を示す図である。図２では、各プロセッサに割り当てられた機能も示しており、受信プロセッサ２０は、パケットを受信する受信処理部２１と、制御情報を生成するチェーン生成部２２を備えている。また、各パケットプロセッサ３０ａ、３０ｂは、パケット処理を実行するパケット処理部３１と、パケットを送信する送信処理部３２を備えている。
【００４３】
図５を参照すると本実施の形態の受信プロセッサ２０は、まず受信処理部２１により、パケットインタフェース１０から入力されたＩＰパケットを受信して、パケット受信処理を行なう（ステップ１００１）。そして、チェーン生成部２２により、制御情報である到着シーケンスチェーン６１とフロー別チェーン６２の２種類のパケットチェーンを生成して、メインメモリ６０内に格納する（ステップ１００２、１００３）。また、受信したパケットは、メインメモリ６０に格納する（ステップ１００４）。
【００４４】
到着シーケンスチェーン６１は、各パケットの到着順を示すチェーンである。図２においては、パケット▲１▼、▲２▼、▲３▼、…というように到着シーケンスチェーン６１を組んでいる。
【００４５】
フロー別チェーン６２は、各パケットの到着順をフロー別に示すチェーンである。図２においては、各フロー毎に到着したパケットが示されており、例えば、到着シーケンスチェーン６１のパケット▲１▼と同一のフローのパケットは、パケット▲１▼、▲５▼、▲７▼、…の順に到着していることが示されている。
【００４６】
受信プロセッサ２０のチェーン生成部２２は、例えばＩＰｖ４パケットの場合は、Source IPアドレスやDestination Address、プロトコル情報、ＴＣＰ／ＩＰのSource Port番号やDestination Port番号、ＴＯＳ情報を基に、フロー別チェーン６２を生成することができる。またＩＰｖ６パケットの場合は、受信プロセッサ２０は、Source IPアドレスやプロトコル情報、ＴＣＰ／ＩＰのSource Port番号やDestination Port番号、Traffic Class情報、Flow Label情報を基に、フロー別チェーン６２を生成することができる。
【００４７】
到着シーケンスチェーン６１とフロー別チェーン６２の２つのチェーンは、本実施の形態のパケット処理装置１０００が、パケット処理等行なうために用いる制御情報であり、図３にその例を示し、図４にて図３に示される各パケットの制御情報の一具体例を示している。
【００４８】
パケット番号１００〜１４０は、各々の受信パケットに割り当てた番号である。図４では、各パケットＰ１００〜Ｐ１４０のパケット番号として、それぞれに１００〜１４０を割り当てている。
【００４９】
到着ポインタ２００〜２４０は、双方向ポインタであり、到着シーケンスチェーン６１を形成するために使用する。図３の到着ポインタ同士の接続から分かるように、逆方向のポインタは後に到着したパケット番号、順方向のポインタは前に到着したパケット番号を示している。
【００５０】
フローポインタ３００〜３４０は、双方向ポインタで、フロー別チェーン６２を形成するために使用する。図３のフローポインタ同士の接続から分かるように、逆方向のポインタは、同一フローで後に到着したパケット番号、順方向のポインタは、同一フローで前に到着したパケット番号を示している。
【００５１】
図３、図４を参照すると、到着ポインタ２００〜２４０に示されるように、各パケットＰ１００〜Ｐ１４０は、パケットＰ１００を先頭にパケットＰ１４０までその番号順に到着している。また、フローポインタ３００〜３４０に示されるように、フローは、Ｐ１００、Ｐ１３０、Ｐ１４０の順番に到着したフローと、Ｐ１１０、Ｐ１２０の順番に到着したフローとがある。
【００５２】
受信処理状態４００〜４４０は、その各パケットに対する受信プロセッサ２０での処理状態を示す。例えば、受信処理状態４００が「００」ならば未処理、「０１」ならば処理中、「１０」ならば処理完了を示している。
【００５３】
図４の受信処理状態４００〜４４０を参照すると、パケットＰ１００〜Ｐ１３０（パケット番号が１００〜１３０のパケット）は受信処理が完了しており、またパケットＰ１４０は現在受信処理中である。
【００５４】
処理状態Ａ  ５００〜５４０は、その各パケットに対するパケットプロセッサ３０ａの処理状態を示し、処理状態Ｂ  ６００〜６４０は、その各パケットに対するパケットプロセッサ３０ｂの処理状態を示す。処理状態Ａ  ５００〜５４０及び処理状態Ｂ  ６００〜６４０は、「００」ならば未処理、「０１」ならば処理中、「１０」ならば処理完了を示している。
【００５５】
図４の処理状態Ａ  ５００〜５４０、処理状態Ｂ  ６００〜６４０を参照すると、まだ処理を完了したパケットは１つもなく、パケットプロセッサ３０ｂはパケットＰ１００に対し処理中であり、パケットプロセッサ３０ａには処理中のパケットはない。また、このように図４の状態においてはパケットＰ１００とパケット１４０は現在排他制御中であるため、パケットプロセッサ３０ａは、これ以外のパケットに対してパケット処理を行なう。
【００５６】
受信プロセッサ２０は、パケット受信を開始すると、メインメモリに前記制御情報を格納し、受信パケットの受信処理を行なう。例えば、この受信パケットに図３のパケット番号１００が割り当てられると、到着ポインタ２００とフローポインタ３００への値の割り当て（連結処理）を行ない、処理状態Ａ  ５００を「１０」（処理完了）に設定する。処理状態Ａ  ５００と処理状態Ｂ  ６００は「００」の未処理状態に設定する。
【００５７】
図６を参照すると、各パケットプロセッサ３０ａ、３０ｂは、まず到着シーケンスチェーン６１の先頭を監視することによって、受信パケットの有無を検知する（ステップ１１０１）。
【００５８】
例えば、前記パケット番号１００のパケットを、パケットプロセッサ３０ａが到着シーケンスチェーン６１の先頭に検知すると、パケットプロセッサ３０ａは処理状態Ａ  ５００の状態をチェックする。
【００５９】
このとき処理状態Ａ  ５００が「００」（未処理）であれば、パケットプロセッサ３０ａが、このパケットのパケット処理処理を行なう（ステップ１１０２）。
【００６０】
もし処理状態Ｂ  ６００が「０１」（処理中）であれば、このパケットはパケットプロセッサ３０ｂが処理中であることを示している。従って、パケットプロセッサ３０ａは、このパケットに対する処理を行なわない（ステップ１１０３）。
【００６１】
このようにして、パケット処理が未処理でありかつ他のパケットプロセッサ３０ｂにより処理中ではない（排他制御中ではない）場合に、当該パケットに対しパケット処理を実行する（ステップ１１０４、１１０３）。
【００６２】
パケット処理においては、パケットプロセッサ３０ａは、そのパケット処理の進行に応じて、随時そのパケットの制御情報を更新する。つまり、パケット処理の開始時点において、そのパケットの制御情報である処理状態Ａ  ５００をパケット処理実行中（排他制御中）を示す「０１」に更新する（ステップ１１０４、１１０５）。また、パケット処理の完了時点において、そのパケットの制御情報である処理状態Ａ  ５００を、パケット処理完了を示す「１０」に更新する（ステップ１１０６、１１０７）。
【００６３】
次にパケットプロセッサ３０ａは、到着ポインタ２００を参照して、次のパケットがあるかどうかを調べ（ステップ１１０８）、もしある場合にはそのパケットに対しステップ１１０２以下の処理を同様に実行する。また、もし次のパケットがない場合には、ステップ１１０１に戻り新たなパケットの到着を待機する。
【００６４】
ここでは、次のパケットとしてパケットＰ１１０があるため、そのパケットＰ１１０の処理状態Ａ  ５１０をチェックする等の、ステップ１１０２以下の処理を同様に実行する。
【００６５】
以上のようにして、受信パケットに対するパケット処理は、制御情報を参照することにより２つのパケットプロセッサ３０ａ、３０ｂが独立に行なうことができ、パケット処理を複数のパケットプロセッサ３０ａ、３０ｂに効率よく負荷分散することができる。
【００６６】
また、本実施の形態のパケットプロセッサ３０ａ、３０ｂは、送信処理部３２を備えることにより、パケットの送信処理も行なう。
【００６７】
図７を参照すると、本実施の形態の各パケットプロセッサ３０ａ、３０ｂのパケット送信の動作は、まず各パケットプロセッサ３０ａ、３０ｂは、独立にフロー別チェーン６２の各チェーンの先頭に送信可能なパケットがあるかどうかをチェックする（ステップ１２０１）。ここで、送信可能なパケットとは、パケット処理の完了した排他制御中ではない（処理中ではない）パケットであり、そのパケットの制御情報を確認することでチェックすることができる。
【００６８】
またここでは、フロー別チェーン６２の各チェーンの先頭に、最後に送信したパケットの制御情報を保持する方式を採用している。これにより、各パケットプロセッサ３０ａ、３０ｂは、この制御情報のフローポインタが持つ順方向ポインタを参照することで、次に送信すべきパケットを特定する。
【００６９】
例えば、最後に送信したパケットがパケット番号１００を持つパケット（パケットＰ１００）であったとすると、その保持されている制御情報を参照することで、次に送信すべきパケットがパケット番号１３０を持つパケット（パケットＰ１３０）であることが分かる。
【００７０】
この場合、パケットプロセッサ３０ａは、パケットＰ１３０の処理状態Ａ  ５３０、処理状態Ｂ  ６３０をチェックする。処理状態Ａ  ５３０又は処理状態Ｂ６３０が「１０」（処理完了）であれば、パケット処理が終了しているので送信可能であることが分かる。
【００７１】
ここで送信可能の場合には、パケットプロセッサ３０ａは、パケット番号１３０のパケットを送信する（ステップ１２０２）。そしてパケットプロセッサ３０ａは、パケットＰ１３０の送信に伴いメインメモリ６０内の制御情報を更新する（ステップ１２０３）。これは、フロー別チェーン６２のそのチェーンにおいて現在保持されているパケットＰ１００の制御情報を削除し、パケットＰ１３０の制御情報を前回送信したパケットの情報として保持する等の処理を行なう。
【００７２】
以上のパケットプロセッサ３０ａのパケット送信処理は、パケットプロセッサ３０ｂの送信処理でも同様である。
【００７３】
また、本実施の形態の送信処理においては、フロー別チェーン６２の各フローのチェーンに対し、その先頭の送信可能なパケットをチェックする順番は任意であり、例えばフロー別にこれをチェックする優先順位を設定することにより、パケットを送信する優先度をフロー単位に設定することが可能である。
【００７４】
以上説明したように、本実施の形態のパケット処理装置１０００によれば、制御情報を参照することにより、複数のパケットプロセッサが独立にパケット単位でパケット処理を行なうことができる。従って、パケット処理の負荷が各々のパケットプロセッサに分散され、各々のパケットプロセッサの処理能力を効果的に利用できるうえ、装置全体の処理能力の向上が見込める。
【００７５】
また、フロー別チェーン６２を備えてパケットのフロー別の転送順序を管理することにより、装置内でのパケットを転送する順序の逆転を防ぐことができる。また、パケット送信処理において、フロー別チェーンに優先度をつけて読み出すことも可能であり、これによりＱｏＳ保証機能を持ったパケット処理装置としても動作可能である。
【００７６】
また、メモリアクセス調停部によりメモリアクセスを調停することにより、複数のパケットプロセッサが同時にメモリアクセスを行なうことを防止でき、例えば参照中の制御データが上書きされたりするような誤動作を防止できる。
【００７７】
また、パケット同士を双方向ポインタでチェーンすることにより、パケット処理で、例えばＱｏＳ廃棄が発生したとしても、その廃棄パケットの前後のパケットの制御情報に含まれる双方向チェーンを書き換えることでパケット送信処理に影響を与えることがない。
【００７８】
また、上記本実施の形態の図１の例では、２個のパケットプロセッサ３０ａ、３０ｂを備える場合を例として説明したが、パケットプロセッサの個数はこれに限るものではない。また、より多くの個数のパケットプロセッサ（パケットプロセッサ３０ｃ、３０ｄ、…）を備える場合には、各パケットの制御情報として、パケットプロセッサの個数に対応させて処理状態Ａ、処理状態Ｂ、処理状態Ｃ、処理状態Ｄ、…を備えることにより、上記第１の実施の形態と同様にして、各パケットプロセッサが分散処理を行なうことがでいる。
【００７９】
次に、本発明の第２の実施の形態を説明する。
【００８０】
一般的なパケット処理装置、例えばルータでは、さまざまなフローのＩＰパケットが到来する。メインメモリ６０の容量にも限界があるので、登録できるフロー数にも制限がある。従って、フローの登録エリアを有効に活用する必要がある。
【００８１】
パケットフローの順序を保証しなければならないのは、パケット処理装置内に、そのフローの１個以上のパケットが滞留している場合である。従って、滞留していない場合は、そのフローの登録を解放しても問題はない。
【００８２】
そこで、本発明の第２の実施の形態では、第１の実施の形態の構成に加えて、パケット滞留状況を監視するためのフローテーブル７００を新たに備える。図８に、そのフローテーブル７００の構成の一例を示す。
【００８３】
図８では、Source IPアドレスでフローを決定する場合のフローテーブル７００が示されている。このフローテーブル７００は、メインメモリ６０上に置かれている。フローテーブル７００の構成要素は、Source IPアドレス７０１とパケットカウンタ７０２である。Source IPアドレス７０１は、登録されているフローを示している。またパケットカウンタ７０２は、そのフローの滞留パケット数を示している。
【００８４】
受信プロセッサ２０は、パケット受信時に、Source IPアドレスを検索キーとして、フローテーブル７００を検索する。もし一致するSource IPアドレスが登録されていれば、パケットカウンタを１カウントアップする。もし一致しなければ、そのSource IPアドレスを、フローテーブル７００に登録し、パケットカウンタを１カウントアップする。
【００８５】
パケットプロセッサ３０ａ、３０ｂは、パケット送信時に、Source IPアドレスを検索キーとして、フローテーブル７００を検索する。もし一致するSource IPアドレスが登録されていれば、パケットカウンタを１カウントダウンする。カウントダウンした結果が「０」となった場合、パケットプロセッサ３０ａ、３０ｂは、そのフローの登録を抹消する。Source IPアドレスを１以上であれば、そのままとする。
【００８６】
図９は、本実施の形態の各パケットプロセッサ３０ａ、３０ｂのパケット処理の動作を説明するためのフローチャートである。
【００８７】
図９を参照すると、第１の実施の形態との違いは、各パケットプロセッサ３０ａ、３０ｂは、パケット処理の完了時点においてフローテーブル７００を参照し、そのパケットと同一のフローの他のパケットが滞留していない場合には、直ちにそのパケットの送信を実行する点がある（ステップ１３０８、１３０９）。
【００８８】
以上説明したように本実施の形態のパケット処理装置は、第１の実施の形態の効果に加えて、パケットフローを動的に登録することにより、フロー別のパケットの転送順序を保証したより効率のよいパケット転送を実現することができる。
【００８９】
次に、本発明の第３の実施の形態を説明する。
【００９０】
上記各実施の形態では、同一機能を持った複数のパケットプロセッサで、受信パケットを分散処理する方式を説明した。しかし、本発明のパケット処理装置は、別の分散処理方法も可能であり、例えば、異なる機能を備える各パケットプロセッサによる機能別の分散処理も実施することができる。
【００９１】
図１０に、本発明の第３の実施の形態のパケット処理装置１０００ｂを示す。図１０では、第１の実施の形態の構成に加えて、新たな機能を備えるパケットプロセッサ８０を追加している。
【００９２】
ここで、このパケットプロセッサ８０は、各パケットプロセッサ３０ａ、３０ｂが備えない機能であるＩＰヘッダの拡張ヘッダ処理機能を備える場合を例に説明する。
【００９３】
図１１は、本実施の形態によるパケット処理装置１０００ｂにおいて用いる各パケットの制御情報の一例を示す図である。本実施の形態では、第１の実施の形態の各パケットの制御情報のデータ構成に加えて、処理状態Ｘ  ８００と処理状態Ｙ  ９００のフィールドを新たに追加している。
【００９４】
処理状態Ｘは、前記パケットプロセッサ８０がＩＰパケットを受信したときに行なう拡張ヘッダ処理の処理状態を示すためのフィールドである。処理状態Ｙは、前記パケットプロセッサ８０がＩＰパケットを送信するときに行なう拡張ヘッダ処理の処理状態を示すためのフィールドである。処理状態Ｘと処理状態Ｙは、処理状態Ａや処理状態Ｂと同様にして、「００」ならば未処理、「０１」ならば処理中、「１０」ならば処理完了を示す。
【００９５】
図１２は、本実施の形態の各パケットプロセッサ３０ａ、３０ｂのパケット処理の動作を説明するためのフローチャートである。本実施の形態の動作の第１の実施の形態との違いは、パケットプロセッサ３０ａ、３０ｂは、処理状態Ｘが「１０」（処理完了）でなければ、パケット処理を行なわない点である。
【００９６】
またパケットプロセッサ３０ａ、３０ｂは、処理状態Ｙが「１０」（処理完了）でなければ、パケットプロセッサ３０ａ、３０ｂはパケット送信処理を行なわない。つまり、本実施の形態では、第１の実施の形態のステップ１２０１に示される送信可能なパケットのチェックにおいて、処理状態Ａ又は処理状態Ｂが処理完了であることのチェックに加えて、処理状態Ｙが処理完了であることのチェックを行なうのである。
【００９７】
図１３は、本発明の第３の実施の形態のパケットプロセッサ８０の拡張ヘッダ処理の動作を説明するためのフローチャートである。図１３に示されるように、パケットプロセッサ８０の制御情報のチェックや更新の動作は、パケットプロセッサ３０ａ、３０ｂの動作と同様である。
【００９８】
パケット受信時の拡張ヘッダ処理において、パケットプロセッサ８０は、処理状態Ｘが「００」（未処理）であれば（ステップ１５０２）、受信時の拡張ヘッダ処理を行なう。
【００９９】
ただし、ステップ１５０２においては、受信したパケットに拡張ヘッダが存在しない場合には、パケットプロセッサ８０は処理状態Ｘを処理済に更新する処理を行ない、そのパケットの処理を終了することとする。
【０１００】
拡張ヘッダ処理が存在すれば、パケットプロセッサ８０は拡張ヘッダ処理を実行し、処理終了時に処理状態Ｘの更新する。拡張ヘッダ処理を完了すれば、パケットプロセッサ８０は、処理状態Ｘを「１０」（処理完了）に設定する（ステップ１５０４〜１５０７）。
【０１０１】
パケット送信時の拡張ヘッダ処理において、パケットプロセッサ８０は、処理状態Ｙが「００」（未処理）であれば、拡張ヘッダ処理を行なう（ステップ１５０９）。
【０１０２】
ただし、ステップ１５０９においては、そのパケットに拡張ヘッダが存在しない場合には、パケットプロセッサ８０は処理状態Ｙを処理済に更新する処理を行ない、そのパケットの処理を終了することとする。
【０１０３】
拡張ヘッダ処理が存在すれば、パケットプロセッサ８０は拡張ヘッダ処理を実行し、処理終了時に処理状態Ｙの更新する。拡張ヘッダ処理を完了すれば、パケットプロセッサ８０は、処理状態Ｙを「１０」（処理完了）に設定する（ステップ１５１１〜１５１４）。
【０１０４】
以上のようにして、本実施の形態のパケットプロセッサ８０は、拡張ヘッダ処理を行なうことができる。
【０１０５】
また、上記のパケットプロセッサ８０の動作では、パケットの受信時と送信時との双方において拡張ヘッダ処理を実行するが、その受信時と送信時の一方のみにおいて実行する方式も同様に実施することがでいる。
【０１０６】
パケットプロセッサ８０の処理としては、上記説明した拡張パケット処理以外にも、例えばIP Fragmentation処理（組み立て、分割処理）や、ある一定長以上、又は一定以下のＩＰパケットだけを処理させること等も同様に実施することができる。またパケットプロセッサ８０を、複数用意して、分散処理させることも、第１の実施の形態のパケットプロセッサ３０ａ、３０ｂと同様にして実施することができる。
【０１０７】
また、パケットプロセッサを、様々なプロトコルのそれぞれに対応させて備えることで、マルチプロトコルによる通信に対応することができる。
【０１０８】
以上説明したように、本実施の形態の本実施の形態のパケット処理装置１０００ｂは、第１の実施の形態の効果に加えて、異なる機能を割り当てた複数のパケットプロセッサにより、パケットに対する処理を機能分散して処理することができる。例えば、上記説明したようにパケットプロセッサ３０ａ、３０ｂには通常のＩＰパケットを処理させ、パケットプロセッサ８０に、突発的に発生する例外ＩＰパケットを処理させることができる。
【０１０９】
このように、本実施の形態のパケット処理装置１０００ｂは、同一の機能を備えるパケットプロセッサの複数化による負荷分散処理だけでなく、機能分散による負荷分散を行なうことができる。
【０１１０】
例えば、図２に示される第１の実施の形態のパケット処理装置１０００の構成において、各パケットプロセッサ３０ａ、３０ｂにおけるパケット処理部３１と送信処理部３２をそれぞれ独立のプロセッサとして分割し、機能分散させて実施することも可能である。
【０１１１】
また、上記各実施の形態のパケット処理装置は、各パケットプロセッサにおいて機能するタスク単位での分散処理も同様にして実施することができる。
【０１１２】
例えば、１つのパケットプロセッサが、同時にパケット処理とパケット転送を並行して実施する機能を備えたり、パケット処理を同時に複数個のパケットに対し並行して実施する機能を備える場合においては、これらの処理を実行する各タスク毎に分散処理を行なうことも同様に実施することができる。つまり、これらタスク単位にその処理状態の情報を制御情報に示し、各タスクがその制御情報を参照してパケット処理やパケット転送等の処理を実行することにより、上記各実施の形態と同様にして、負荷分散や機能分散を実現することができる。
【０１１３】
また、上記各実施の形態は、互いに自由に組み合わせて実施することができる。例えば、第２の実施の形態と、第３の実施の形態を組み合わせることにより、第２の実施の形態のフローテーブル７００を用いたフロー別のパケットの転送順序を保証した効率のよいパケット転送と、第３の実施の形態のパケットプロセッサ毎の機能分散を同時に実現することができる。
【０１１４】
以上好ましい実施の形態及び実施例をあげて本発明を説明したが、本発明は必ずしも上記実施の形態及び実施例に限定されるものではなく、その技術的思想の範囲内において様々に変形して実施することができる。
【０１１５】
【発明の効果】
以上説明したように本発明によれば、受信した各前記パケットの転送順序を転送経路別に示す制御情報を生成することにより、複数の転送プロセッサ（パケットプロセッサ）が、個別に、その制御情報に示される転送経路別の転送順序に基づいて各パケットを転送することができる。また、制御情報において、各パケット毎に、パケット処理が未処理であるのか処理済であるのか、又排他制御中であるか否かを示すことにより、複数の転送プロセッサが、個別に、パケット処理を効率よく分散して処理することができる。このようにして、複数のパケットプロセッサにより処理を分散すると共に、転送経路毎の転送順序に基づいて各パケットを転送することができる。
【図面の簡単な説明】
【図１】  本発明の第１の実施の形態によるパケット処理装置の構成を示すブロック図である。
【図２】  本発明の第１の実施の形態によるパケット処理装置の実施例を示す図である。
【図３】  本発明の第１の実施の形態によるパケット処理装置において用いる制御情報の一例を示す図である。
【図４】  本発明の第１の実施の形態によるパケット処理装置において用いる制御情報の一例を示す図である。
【図５】  本発明の第１の実施の形態の受信プロセッサの動作を説明するためのフローチャートである。
【図６】  本発明の第１の実施の形態のパケットプロセッサのパケット処理の動作を説明するためのフローチャートである。
【図７】  本発明の第１の実施の形態のパケットプロセッサのパケット送信の動作を説明するためのフローチャートである。
【図８】  本発明の第２の実施の形態のフローテーブルの一例を示す図である。
【図９】  本発明の第２の実施の形態のパケットプロセッサのパケット処理の動作を説明するためのフローチャートである。
【図１０】  本発明の第３の実施の形態によるパケット処理装置の構成を示すブロック図である。
【図１１】  本発明の第３の実施の形態によるパケット処理装置において用いる制御情報の一例を示す図である。
【図１２】  本発明の第３の実施の形態のパケットプロセッサのパケット処理の動作を説明するためのフローチャートである。
【図１３】  本発明の第３の実施の形態の拡張ヘッダ処理を行なうパケットプロセッサの動作を説明するためのフローチャートである。
【符号の説明】
１０００、１０００ｂ  パケット処理装置
１０  パケットインタフェース
２０  受信プロセッサ
２１  受信処理部
２２  チェーン生成部
３０ａ、３０ｂ  パケットプロセッサ
３１  パケット処理部
３２  送信処理部
４０、４１  バス
５０  メモリアクセス調停部
６０  メインメモリ
６１  到着シーケンスチェーン
６２  フロー別チェーン
７０  パケットフロー
８０  パケットプロセッサ
１００〜１４０  パケット番号
２００〜２４０  到着ポインタ
３００〜３４０  フローポインタ
４００〜４４０  受信処理状態
５００〜５４０  処理状態Ａ
６００〜６４０  処理状態Ｂ
７００  フローテーブル
８００  処理状態Ｘ
９００  処理状態Ｙ
２０００  制御情報
【図１】
0003635660.tif 000002
【図２】
0003635660.tif 000003
【図３】
0003635660.tif 000004
【図４】
0003635660.tif 000005
【図５】
0003635660.tif 000006
【図６】
0003635660.tif 000007
【図７】
0003635660.tif 000008
【図８】
0003635660.tif 000009
【図９】
0003635660.tif 000010
【図１０】
0003635660.tif 000011
【図１１】
0003635660.tif 000012
【図１２】
0003635660.tif 000013
【図１３】
0003635660.tif 000014