(57)【要約】【課題】処理ユニットの利用効率を向上させることができるフロー制御装置を提供することを目的とする。【解決手段】  フロー制御装置１２は、受信されたパケットのフローを識別する解析部２２と、フローごとに振り分けられたパケットを一時的に格納する複数のキュー２７と、フローごとに割り当てられるキューに関する割当情報を記憶する割当情報記憶部２４と、解析部２２によって識別された結果と割当情報とに基づいて、受信されたパケットの格納先となるキュー２７を決定して振り分ける振分部２５と、振分部２５によって割り当て先のキュー２７に関する割当情報が無いと判断されたフローに属するパケットを退避させる退避パケット保持部２６と、複数のキュー２７に一時的に格納されたパケット、および、退避パケット保持部２６に退避されたパケットを、パケットの処理を行う処理ユニット１３に送信する送信部２８とを備える。【選択図】  図２
2019140553.tif 000002
【特許請求の範囲】
【請求項１】
パケットを受信する受信部と、
受信された前記パケットのフローを識別する解析部と、
前記解析部が識別したフローごとに振り分けられたパケットを一時的に格納する複数のキューと、
前記フローごとに割り当てられるキューに関する割当情報を記憶する割当情報記憶部と、
前記解析部によって識別された結果と前記割当情報記憶部に記憶されている前記割当情報とに基づいて、受信された前記パケットの格納先となるキューを決定し、前記パケットを振り分ける振分部と、
前記振分部によって前記パケットの格納先として割り当てられたキューが無いと判断されたフローに属するパケットを退避させる退避パケット保持部と、
前記複数のキューに一時的に格納されたパケット、および、前記退避パケット保持部に退避されたパケットを、パケットの処理を行う処理ユニットに送信する送信部と
を備える
ことを特徴とするフロー制御装置。
【請求項２】
請求項１に記載のフロー制御装置において、
パケットを未格納のキューが存在し、かつ、前記退避パケット保持部にパケットが退避されている場合に、退避されている前記パケットの先頭パケットのフローを所定のフローとして決定し、前記所定のフローを前記未格納のキューに割り当てる制御部をさらに備え、
前記送信部は、前記所定のフローに属するパケットを前記退避パケット保持部から全て取得して前記処理ユニットに送信し、
前記振分部は、前記受信部によって受信されたパケットのうち、前記所定のフローに属するパケットを前記未格納のキューに振り分ける
ことを特徴とするフロー制御装置。
【請求項３】
請求項１または請求項２に記載のフロー制御装置において、
前記退避パケット保持部は、
退避する前記パケットが入力される入力部と、
入力された前記パケットを保持する退避用メモリと、
前記退避用メモリを管理するためのポインタの情報を保持するポインタ記憶部と、
前記退避用メモリへのデータの読み書きを制御するメモリ制御部と、
前記退避用メモリに保持されている前記パケットを前記送信部に出力する出力部と
を備えることを特徴とするフロー制御装置。
【請求項４】
請求項３に記載のフロー制御装置において、
前記退避用メモリは、前記パケットが格納された領域を第１連結リストとして保持し、かつ、空き領域を第２連結リストとして保持することを特徴とするフロー制御装置。
【請求項５】
請求項４に記載のフロー制御装置において、
前記メモリ制御部は、
前記退避用メモリが保持する前記第２連結リストの先頭ノードから末尾ノード側に向けて順にパケットを格納し、前記パケットが格納されたノードを前記第１連結リストの末尾ノードに追加し、かつ、並行して、前記第１連結リストの先頭ノードから末尾ノード側に向けて順に、退避されている前記パケットの先頭パケットのフローである所定のフローに属するパケットを取り出し、前記第２連結リストの末尾ノードに追加する
ことを特徴とするフロー制御装置。
【請求項６】
請求項５に記載のフロー制御装置において、
前記ポインタ記憶部は、
前記退避用メモリが保持する前記第１連結リストおよび前記第２連結リストのそれぞれの先頭ノードの番地および末尾ノードの番地と、前記メモリ制御部が、前記所定のフローに属するパケットを取り出す際に用いる走査用ポインタとを記憶する
ことを特徴とするフロー制御装置。
【請求項７】
パケットを受信する受信ステップと、
受信したパケットのフローを識別する解析ステップと、
前記解析ステップで識別した結果と割当情報記憶部に記憶されている前記フローごとに割り当てられるキューに関する割当情報とに基づいて、前記解析ステップで識別したフローごとに振り分けられたパケットを一時的に格納する複数のキューのうち、受信された前記パケットの格納先となるキューを決定し、前記パケットを振り分ける振分ステップと、
前記振分ステップで振り分けた前記パケットを前記キューに格納するキュー格納ステップと、
前記振分ステップで前記パケットの格納先として割り当てられたキューが無いと判断したフローに属するパケットを退避パケット保持部に退避させるパケット退避ステップと、
前記複数のキューに一時的に格納されたパケット、および、前記退避パケット保持部に退避されたパケットを、パケットの処理を行う処理ユニットに送信する送信ステップと
を備える
ことを特徴とするフロー制御方法。
【請求項８】
請求項７に記載のフロー制御方法において、
パケットを未格納のキューが存在し、かつ、前記退避パケット保持部にパケットが退避されている場合に、退避されている前記パケットの先頭パケットのフローを所定のフローとして決定し、前記所定のフローを前記未格納のキューに割り当てるフロー割り当てステップをさらに備え、
前記送信ステップでは、前記所定のフローに属するパケットを前記退避パケット保持部から全て取得して前記処理ユニットに送信し、
前記振分ステップでは、前記受信ステップで受信されたパケットのうち、前記所定のフローに属するパケットを前記未格納のキューに振り分ける
ことを特徴とするフロー制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、フロー制御装置および方法に関し、特にパケットを並列処理する技術に関する。
【背景技術】
【０００２】
一般に、データセンタでは、一台のサーバで複数のユーザからのリクエストを処理する必要がある。従来より、このようなサーバなどのデータ処理装置における処理性能を向上させるために、データ処理装置に、並列化した処理ユニットを設けて、リクエストなどのデータを処理している。複数の処理ユニットを並列化した構成のデータ処理装置では、混在する複数のパケットフローを識別し、各パケットフローに含まれるパケットを適した処理ユニットに振り分ける必要がある。
【０００３】
例えば、特許文献１は、同一のパケットフロー（以下、「フロー」という。）内でのパケット順序を保証し、かつ並列化された処理ユニットに負荷が偏らないパケット振り分け装置および方法を開示している。特許文献１の技術では、処理ユニット毎にキューを用意し、以下の制約のもとパケットを振り分ける。
【０００４】
第１に、同じフローのパケットがいずれかのキューに存在する場合は、同じフローの新たなパケットを同じキューに振り分ける。これにより、同一フロー内のパケットについては処理の前後で順序反転が発生しないことを保証できる。第２に、新規フローのパケットは空のキューにのみ振り分ける。これにより、長いフローが特定の処理ユニットに集中することが回避される。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０１２−２０９６９５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかし、フローの数が処理ユニットの数よりも多い場合、空のキューが無い状態で新たなフローのパケットが入力される可能性がある。特許文献１に記載されたパケットの振り分け技術では、空のキューが無い状態で新たなフローのパケットが入力されると、いずれかのキューが空になるまで入力パケットを待機させる必要がある。待機中は入力バッファからの後続パケットの入力がストールし、処理ユニットの利用効率の低下に繋がる問題がある。
【０００７】
本発明は、上述した課題を解決するためになされたものであり、処理ユニットの利用効率を向上させることができるフロー制御装置を提供することを目的とする。
【課題を解決するための手段】
【０００８】
上述した課題を解決するために、本発明に係るフロー制御装置は、パケットを受信する受信部と、受信された前記パケットのフローを識別する解析部と、前記解析部が識別したフローごとに振り分けられたパケットを一時的に格納する複数のキューと、前記フローごとに割り当てられるキューに関する割当情報を記憶する割当情報記憶部と、前記解析部によって識別された結果と前記割当情報記憶部に記憶されている前記割当情報とに基づいて、受信された前記パケットの格納先となるキューを決定し、前記パケットを振り分ける振分部と、前記振分部によって前記パケットの格納先として割り当てられたキューが無いと判断されたフローに属するパケットを退避させる退避パケット保持部と、前記複数のキューに一時的に格納されたパケット、および、前記退避パケット保持部に退避されたパケットを、パケットの処理を行う処理ユニットに送信する送信部とを備えることを特徴とする。
【０００９】
また、本発明に係るフロー制御装置において、パケットを未格納のキューが存在し、かつ、前記退避パケット保持部にパケットが退避されている場合に、退避されている前記パケットの先頭パケットのフローを所定のフローとして決定し、前記所定のフローを前記未格納のキューに割り当てる制御部をさらに備え、前記送信部は、前記所定のフローに属するパケットを前記退避パケット保持部から全て取得して前記処理ユニットに送信し、前記振分部は、前記受信部によって受信されたパケットのうち、前記所定のフローに属するパケットを前記未格納のキューに振り分けてもよい。
【００１０】
また、本発明に係るフロー制御装置において、前記退避パケット保持部は、退避する前記パケットが入力される入力部と、入力された前記パケットを保持する退避用メモリと、前記退避用メモリを管理するためのポインタの情報を保持するポインタ記憶部と、前記退避用メモリへのデータの読み書きを制御するメモリ制御部と、前記退避用メモリに保持されている前記パケットを前記送信部に出力する出力部とを備えていてもよい。
【００１１】
また、本発明に係るフロー制御装置において、前記退避用メモリは、前記パケットが格納された領域を第１連結リストとして保持し、かつ、空き領域を第２連結リストとして保持していてもよい。
【００１２】
また、本発明に係るフロー制御装置において、前記メモリ制御部は、前記退避用メモリが保持する前記第２連結リストの先頭ノードから末尾ノード側に向けて順にパケットを格納し、前記パケットが格納されたノードを前記第１連結リストの末尾ノードに追加し、かつ、並行して、前記第１連結リストの先頭ノードから末尾ノード側に向けて順に、退避されている前記パケットの先頭パケットのフローである所定のフローに属するパケットを取り出し、前記第２連結リストの末尾ノードに追加してもよい。
【００１３】
また、本発明に係るフロー制御装置は、前記ポインタ記憶部は、前記退避用メモリが保持する前記第１連結リストおよび前記第２連結リストのそれぞれの先頭ノードの番地および末尾ノードの番地と、前記メモリ制御部が、前記所定のフローに属するパケットを取り出す際に用いる走査用ポインタとを記憶してもよい。
【００１４】
また、本発明に係るフロー制御方法は、パケットを受信する受信ステップと、受信したパケットのフローを識別する解析ステップと、前記解析ステップで識別した結果と割当情報記憶部に記憶されている前記フローごとに割り当てられるキューに関する割当情報とに基づいて、前記解析ステップで識別したフローごとに振り分けられたパケットを一時的に格納する複数のキューのうち、受信された前記パケットの格納先となるキューを決定し、前記パケットを振り分ける振分ステップと、前記振分ステップで振り分けた前記パケットを前記キューに格納するキュー格納ステップと、前記振分ステップで前記パケットの格納先として割り当てられたキューが無いと判断したフローに属するパケットを退避パケット保持部に退避させるパケット退避ステップと、前記複数のキューに一時的に格納されたパケット、および、前記退避パケット保持部に退避されたパケットを、パケットの処理を行う処理ユニットに送信する送信ステップとを備えることを特徴とする。
【００１５】
また、本発明に係るフロー制御方法において、パケットを未格納のキューが存在し、かつ、前記退避パケット保持部にパケットが退避されている場合に、退避されている前記パケットの先頭パケットのフローを所定のフローとして決定し、前記所定のフローを前記未格納のキューに割り当てるフロー割り当てステップをさらに備え、前記送信ステップでは、前記所定のフローに属するパケットを前記退避パケット保持部から全て取得して前記処理ユニットに送信し、前記振分ステップでは、前記受信ステップで受信されたパケットのうち、前記所定のフローに属するパケットを前記未格納のキューに振り分けてもよい。
【発明の効果】
【００１６】
本発明によれば、受信したパケットを振り分け可能なキューが存在しない場合に、退避パケット保持部にパケットを退避させて、さらに、退避パケット保持部で保持しているパケットから、所定のフローのパケットのみを、そのパケットの入力順に取り出して、送信部に送出するので、空のキューが存在しない状態で新たなフローに属するパケットが入力された場合であっても、後続パケットの入力のストールを抑制することができ、処理ユニットの利用効率を向上させることが可能である。
【図面の簡単な説明】
【００１７】
【図１】図１は、本発明の実施の形態に係るフロー制御装置を備えるデータ処理装置の構成を示すブロック図である。
【図２】図２は、本発明の実施の形態に係るフロー制御装置の構成を示すブロック図である。
【図３】図３は、本発明の実施の形態に係る割当情報記憶部のデータ構造の説明図である。
【図４】図４は、本発明の実施の形態に係るフロー制御装置の動作を説明するためのフローチャートである。
【図５】図５は、本発明の実施の形態に係るフロー制御装置の動作例を示す図である。
【図６Ａ】図６Ａは、本発明の実施の形態に係るフロー制御装置の動作例を示す図である。
【図６Ｂ】図６Ｂは、本発明の実施の形態に係るフロー制御装置の動作を説明するための図である。
【図６Ｃ】図６Ｃは、本発明の実施の形態に係るフロー制御装置の動作例を示す図である。
【図７】図７は、本発明の実施の形態に係る退避パケット処理部の構成を示すブロック図である。
【図８Ａ】図８Ａは、本発明の実施の形態に係る退避用メモリの論理構成を説明するための図である。
【図８Ｂ】図８Ｂは、本発明の実施の形態に係る退避用メモリの物理構成を説明するための図である。
【図９】図９は、本発明の実施の形態に係る退避パケット保持部の動作モード１を説明するためのフローチャートである。
【図１０】図１０は、本発明の実施の形態に係るパケット追加処理の動作例を説明するための図である。
【図１１】図１１は、本発明の実施の形態に係るパケット追加処理を説明するためのフローチャートである。
【図１２】図１２は、本発明の実施の形態に係るマージ処理の動作例を説明するための図である。
【図１３】図１３は、本発明の実施の形態に係るマージ処理を説明するためのフローチャートである。
【図１４】図１４は、本発明の実施の形態に係る退避パケット保持部の動作モード２を説明するためのフローチャートである。
【図１５】図１５は、本発明の実施の形態に係るパケット取り出し判定処理を説明するためのフローチャートである。
【図１６Ａ】図１６Ａは、本発明の実施の形態に係るパケット取り出し判定処理の動作例を示す図である。
【図１６Ｂ】図１６Ｂは、本発明の実施の形態に係るパケット取り出し判定処理の動作例を示す図である。
【図１６Ｃ】図１６Ｃは、本発明の実施の形態に係るパケット取り出し判定処理の動作例を示す図である。
【図１６Ｄ】図１６Ｄは、本発明の実施の形態に係るパケット取り出し判定処理の動作例を示す図である。
【図１６Ｅ】図１６Ｅは、本発明の実施の形態に係るパケット取り出し判定処理の動作例を示す図である。
【図１７】図１７は、本発明の実施の形態に係るパケット取り出し判定処理の動作例を示す図である。
【図１８】図１８は、本発明の実施の形態に係る終端処理の動作例を示す図である。
【図１９】図１９は、本発明の実施の形態に係る終端処理を説明するためのフローチャートである。
【発明を実施するための形態】
【００１８】
以下、本発明の好適な実施の形態について、図１から図１９を参照して詳細に説明する。
［実施の形態］
図１は、本発明の実施の形態に係るフロー制御装置１２を備えるデータ処理装置１０の構成を示すブロック図である。データ処理装置１０は、例えば、データセンタに設置されるサーバなどの各種コンピュータで実現される。データ処理装置１０は、図示しない外部ネットワークを介して複数のユーザ端末から受信する複数のリクエストなどのデータの並列処理を行う。
【００１９】
データ処理装置１０は、例えば、ＣＰＵなどのプロセッサがデータ処理装置１０内に設けられた図示されない記憶装置に格納されたプログラムに従って、複数のリクエストの処理など各種のデータ処理を実行する。より具体的には、ＣＰＵなどのプロセッサは、複数のコアを有するマルチコアプロセッサとして具現可能である。
【００２０】
データ処理装置１０は、入力部１１、フロー制御装置１２、複数の処理ユニット１３、および出力部１４を備える。
【００２１】
入力部１１は、図示されない外部ネットワークを介してデータ通信を行い、データ処理装置１０の外部からパケットを受け取る。入力部１１は、データ処理装置１０と各種外部電子機器との間を通信ネットワークを介して接続するための通信制御装置を含む。入力部１１によって受け取られたパケットは、フロー制御装置１２に入力される。
【００２２】
フロー制御装置１２は、入力部１１を介して入力されたパケットのフローを識別し、フローに応じて振り分け先の処理ユニットを決定する。フロー制御装置１２によってフローが制御されたパケットは、処理ユニット１３に入力される。フロー制御装置１２は、ＣＰＵなどのプロセッサが図示されないＲＯＭ、ＲＡＭおよびフラッシュメモリなどの記憶装置に格納されたプログラムに従って入力パケットの識別および制御を実行することで実現される。なお、フロー制御装置１２の詳細は後述する。
【００２３】
処理ユニット１３は、並列化された複数の処理ユニット１３によって構成される。処理ユニット１３は、例えば、マルチコアＣＰＵなどのマルチコアプロセッサによって実現される。複数の処理ユニット１３（処理ユニット＃０，処理ユニット＃１，・・・，処理ユニット＃Ｎ、Ｎは１以上の整数）は、パケットの並列処理を行う。
【００２４】
出力部１４は、処理ユニット１３によって実行されたパケットの処理の結果を、図示しない外部ネットワークを介して外部に出力する。出力部１４は、前述した入力部１１と同様に、通信制御装置を含む。
【００２５】
［フロー制御装置の構成］
次に、フロー制御装置１２の構成について、図２に示すブロック図を用いて説明する。
フロー制御装置１２は、入力バッファ２０、受信部２１、解析部２２、制御部２３、割当情報記憶部２４、振分部２５、退避パケット保持部２６、複数のキュー２７、および送信部２８を備える。
【００２６】
入力バッファ２０は、入力部１１を介して入力されたパケットを保持する。
受信部２１は、入力バッファ２０に保持されているパケットを受信する。
【００２７】
解析部２２は、受信部２１によって受信されたパケットのフローを識別する。パケットのフローは、例えば、受信したパケットのヘッダ情報に含まれるパケットの送信元や宛先に関するパケットの属性を示す情報である。
【００２８】
制御部２３は、フロー制御装置１２に含まれる解析部２２や振分部２５などの各機能部を制御する。また、制御部２３は、割当情報記憶部２４が記憶する情報の読み書きなどを行う。
割当情報記憶部２４は、フローごとに割り当てられるキュー２７に関する割当情報を記憶する。割当情報記憶部２４のデータ構造は後述する。
【００２９】
振分部２５は、解析部２２によって識別されたパケットのフローの情報と、割当情報記憶部２４に記憶されている割当情報とに基づいて、受信部２１によって受信されたパケットの格納先となるキュー２７を決定して振り分ける。より詳細には、振分部２５は、一定の条件下において、受信されたパケットをキュー２７へ振り分け、また、空のキュー２７が無い場合には、受信されたパケットを退避パケット保持部２６へ退避させる。
【００３０】
退避パケット保持部２６は、振分部２５によって割り当て先のキュー２７に関する割当情報が無いと判断されたフローに属するパケットを退避させ格納する。具体的には、退避パケット保持部２６は、空のキュー２７が無い場合に、パケットを退避させて格納する。また、退避パケット保持部２６は、保持しているパケットから、所定のフローに属するパケットのみを、パケットの入力順に取り出して、後段の送信部２８に送出する。退避パケット保持部２６は、全ての送信部２８に接続されている。
【００３１】
キュー２７は、解析部２２が識別したフロー毎に振り分けられたパケットを一時的に格納するメモリである。キュー２７は、処理ユニット１３毎に設けられている。各キュー２７は、パケットを先入れ先出し方式で格納する構造を有する。また、各キュー２７に格納されたパケットは、入力順に取り出され、送信部２８に送出される。
【００３２】
送信部２８は、キュー２７に一時的に格納されたパケット、および、退避パケット保持部２６に退避されたパケットを、処理ユニット１３に送信する。送信部２８は、キュー２７毎に、すなわち、処理ユニット１３毎に設けられている。
【００３３】
［割当情報記憶部のデータ構造］
次に、割当情報記憶部２４のデータ構造について、図３を用いて説明する。割当情報記憶部２４は、キュー２７に割り当てられているフローの対応を記述した割当情報のテーブルを保持する。図３に示すように、割当情報記憶部２４には、処理ユニット１３の識別ＩＤとフローの識別ＩＤとが互いに関連付けて記憶されている。
【００３４】
具体的には、処理ユニット１３の識別ＩＤ「＃０」と割り当てフローの識別ＩＤ「Ａ」、処理ユニット識別ＩＤ「＃１」と割り当てフロー識別ＩＤ「Ｂ」、さらに、処理ユニット識別ＩＤ「＃２」と割り当てフロー識別ＩＤ「Ｃ」とがそれぞれ互いに関連付けて記憶されている。なお、処理ユニット１３の識別ＩＤの代わりに、対応するキュー２７の識別ＩＤを用いてもよい。
【００３５】
［フロー制御装置の動作］
次に、フロー制御装置１２の動作について、図４のフローチャートを用いて説明する。図４のフローチャートは、フロー制御装置１２が入力バッファ２０に入力されたパケットを退避パケット保持部２６および複数のキュー２７のいずれかに格納するまでの処理を示したものである。まず、受信部２１は、入力バッファ２０からパケットを受信する（ステップＳ１０１）。次に、解析部２２は、受信されたパケットのフローを識別する（ステップＳ１０２）。より詳細には、解析部２２は、受信したパケットのヘッダ情報に含まれる情報に基づいて、フローを識別する。
【００３６】
次に、制御部２３は、割当情報記憶部２４の割当情報テーブルを参照し、解析部２２によって識別された受信パケットのフローが、処理ユニット１３のいずれか、すなわちキュー２７のいずれかに割り当てられているかどうかを確認する（ステップＳ１０３）。例えば、図３に示すように、解析部２２によって識別されたパケットのフローの識別ＩＤが「Ａ」である場合、フロー「Ａ」に属するパケットは、処理ユニット１３の識別ＩＤ「＃０」に対応するキュー２７に割り当てられる。
【００３７】
受信されたパケットのフローが処理ユニット１３のいずれかに割り当てられている場合には（ステップＳ１０４：ＹＥＳ）、振分部２５は、対応するキュー２７の末尾にパケットを追加する（ステップＳ１０５）。
【００３８】
一方、受信されたパケットのフローが、いずれの処理ユニット１３にも割り当てられていない場合には（ステップＳ１０４：ＮＯ）、振分部２５は、空のキュー２７が存在するかを確認し、存在しない場合には（ステップＳ１０６：ＮＯ）、パケットを退避パケット保持部２６に退避させる（ステップＳ１１０）。
【００３９】
一方、空のキュー２７が存在する場合に（ステップＳ１０６：ＹＥＳ）、退避パケット保持部２６において既に退避され、保持されているパケットが存在する場合には（ステップＳ１０７：ＹＥＳ）、振分部２５は、受信されたパケットを退避パケット保持部２６に退避させる（ステップＳ１１０）。
【００４０】
さらに一方において、退避パケット保持部２６に、既に退避され、保持されているパケットが存在しない場合には（ステップＳ１０７：ＮＯ）、制御部２３は、割当情報記憶部２４の割当情報テーブルの情報を更新する（ステップＳ１０８）。
【００４１】
より詳細には、制御部２３による割当情報テーブルの情報を更新により、受信されたパケットのフローを示す割り当てフロー識別ＩＤと、空のキュー２７に対応する処理ユニット識別ＩＤとが新規フローの割当情報として割当情報記憶部２４に記憶される。
その後、振分部２５は、新規フローが割り当てられた空のキュー２７にパケットを振り分ける。そして、空のキュー２７は振り分けられたパケットを一時的に格納する（ステップＳ１０９）。
【００４２】
［退避パケット保持部の動作の概要］
次に、退避パケット保持部２６の動作の概要について、図５を参照して説明する。前述したように、退避パケット保持部２６は、受信したパケットを格納する機能と、保持しているパケットを取り出す機能とを有する。退避パケット保持部２６は、これらの２つの異なる機能に基づいて、「動作モード１」および「動作モード２」の２種類の動作モードで動作する。
【００４３】
図５に示すように、退避パケット保持部２６は、フロー制御装置１２におけるフロー制御の開始から所定の通常の状態では、受信したパケットの格納のみを行う「動作モード１」で動作する。退避パケット保持部２６は、後述するパケットのフロー切り替えのタイミングを起点に、受信したパケットの格納と、保持しているパケットの取り出しの両方が有効な「動作モード２」に切り替わる。
【００４４】
その後、パケットのフロー切り替えが完了すると、退避パケット保持部２６は、「動作モード１」に切り替わる。
【００４５】
［フローの割り当て処理］
図６Ａから図６Ｃは、特に、空のキュー２７が生じた場合において、退避パケット保持部２６に既に保持されているパケットのフローを、キュー２７に割り当てる際のフロー制御装置１２全体における動作例を示す。なお、図６Ａから図６Ｃでは、制御部２３および割当情報記憶部２４を省略している。
【００４６】
図６Ａの例に示すように、まず、複数のキュー２７のうちのいずれかに空きが生じたとする。このタイミングで、退避パケット保持部２６が保持しているパケットの先頭パケットの属するフローが、空きの生じたキュー２７に割り当てられる。すなわち、退避パケット保持部２６が保持している先頭パケット「Ａ１」の属するフロー「Ａ」が、制御部２３によって空のキュー２７に割り当てられる。制御部２３は、例えば、先頭パケットのヘッダ情報などにより、先頭パケットのフローを識別することができる。
【００４７】
次に、図６Ｂに示すように、空のキュー２７に対応する送信部２８によるパケットの取得先は、退避パケット保持部２６に変更される。これにより、送信部２８は、フロー「Ａ」に属するパケット「Ａ１」「Ａ２」を退避パケット保持部２６から全て取得して、対応する処理ユニット１３に送信する。
【００４８】
ここで、入力バッファ２０に保持されているフロー「Ａ」に属するパケット「Ａ３」「Ａ４」は、振分部２５によって、処理ユニット１３毎のキュー２７に振り分けられる。これに平行して、退避パケット保持部２６は、入力バッファ２０に保持されているパケットの格納を行う。
【００４９】
より詳細には、図６Ｂおよび図６Ｃに示すように、入力バッファ２０に保持されているフロー「Ｂ」に属するパケット「Ｂ３」および「Ｂ４」は、振分部２５によって、退避パケット保持部２６に退避される。
【００５０】
その後、退避パケット保持部２６が、フロー「Ａ」に属するパケットを全て取り出し終えると、制御部２３によって送信部２８のパケット取得先が、退避パケット保持部２６からキュー２７に変更される。そして、キュー２７に一時的に格納されているフロー「Ａ」に属するパケット「Ａ３」「Ａ４」は、送信部２８によって処理ユニット１３に送信される。
【００５１】
［退避パケット保持部の構成］
次に、退避パケット保持部２６の構成について、図７のブロック図を参照して説明する。
退避パケット保持部２６は、入力部２６１、メモリ制御部２６２、退避用メモリ２６３、ポインタ記憶部２６４、および出力部２６５を備える。
【００５２】
入力部２６１は、振分部２５によって退避されたパケットの入力を受け付ける。
メモリ制御部２６２は、退避用メモリ２６３へのデータの読み書きを制御する。
退避用メモリ２６３は、入力部２６１から入力された退避するパケットを記憶する。退避用メモリ２６３は、後述するパケットリスト、および空リストの２つの連結リストを保持する。また、退避用メモリ２６３は、退避させるパケットを一時的に保持する一時パケットリストを有する。退避用メモリ２６３は、例えば、不揮発性メモリを用いてもよい。
【００５３】
ポインタ記憶部２６４は、退避用メモリ２６３の管理に用いる、退避用メモリ２６３のアドレスを特定するポインタの情報を記憶する。なお、ポインタの詳細は後述する。
【００５４】
出力部２６５は、メモリ制御部２６２が退避用メモリ２６３から読み出したパケットを送信部２８に出力する。
【００５５】
［退避用メモリの構成］
次に、退避用メモリ２６３の構成について、図８Ａおよび図８Ｂを用いて説明する。
図８Ａに示すように、退避用メモリ２６３の論理構成としては、退避したパケットを管理する「パケットリスト」および退避用メモリ２６３の空き領域を管理する「空リスト」の２つの連結リストを有する。
【００５６】
図８Ｂは、退避用メモリ２６３の物理構成を示す。退避用メモリ２６３の「番地」が、図８Ａで示した連結リストのノード識別番号として用いられる。各ノードは、「パケット」を示す情報と合わせて、「次のノードの番地」を示す情報を保持することで退避用メモリ２６３のリスト構造が実現される。図８Ａおよび図８Ｂにおいて、パケットリストのノードは、灰色で示されるノードであり、空リストのノードは、白色で示されている。
【００５７】
また、パケットリストと空リストとを区別するために、各リストの先頭ノードと末尾ノードとを示すポインタが用意される。図８Ａおよび図８Ｂに示すように、パケットリストの先頭ノードはポインタｐｈ、末尾ノードはポインタｐｔで管理される。一方、空リストの先頭ノードはポインタｅｈ、末尾ノードはポインタｅｔで管理される。
【００５８】
さらに、連結リストにおける走査処理を簡単化するために、パケットリストの先頭ノードと末尾ノードにはパケットは格納せずダミーノードとして扱う。
【００５９】
［退避パケット保持部の動作モード１］
次に、上述した構成を有する退避パケット保持部２６の動作の詳細について、図９のフローチャートを用いて説明する。退避パケット保持部２６の動作の概要については図５に示したとおりである。ここでは、退避パケット保持部２６における「動作モード１」について詳細に説明する。
【００６０】
図９は、退避パケット保持部２６における動作モード１を説明するフローチャートである。動作モード１において、退避パケット保持部２６は、入力されたパケットの格納処理を繰り返し行うループ処理を実行するが、フロー切り替えが発生した時点で、ループから抜け、動作モード２へ移行する。なお、フロー切り替えのタイミングは、設計によって指定されるパラメータである。
【００６１】
ここで、フロー切り替えの必要性について説明する。
【００６２】
同じフローに属する全てのパケットが、外部ネットワークを介してデータ処理装置１０などに到着するまでの時間は、パケットの種類、すなわちフローによって異なる。例えば、フローが経由するネットワークの輻輳状態や物理的な転送レートの違いにより、そのフローに含まれるすべてのパケットが到着するまでに要する時間は異なる。また、フローに含まれるパケット数の違いなどにより、そのフローに属する全てのパケットの転送にかかる時間は異なる。
【００６３】
そのため、フロー制御装置１２においてフローの切り換えを行わない場合、全パケットの到着までの時間が長いフローは、処理ユニット１３を長時間占有することになる。一つのフローが処理ユニット１３を占有している間は、他のフローの処理は待たされることになり、処理遅延が増大する。
【００６４】
このような、１つのフローに含まれる全パケットの到着までの時間に依存した処理遅延の増大を抑制する方法として、処理ユニット１３の占有時間に上限を設け、フロー内の全パケットの処理が完了していない場合でも強制的に処理対象のフローを切り替えるという方式が考えられる。
【００６５】
この方式では、処理遅延のワースト値を「専有時間の上限値」、言い換えると「フロー切り換えのタイミング」というパラメータで制御することが可能である。フロー切り換えのタイミングは設計時に固定する方法と、可変値としてフロー制御装置１２の動作中に外部からの入力として与えるという方法とが考えられる。なお、設定されたパラメータの値は、例えば、割当情報記憶部２４の所定の領域に記憶される。
【００６６】
ここで、図９に戻り、退避パケット保持部２６における動作モード１について説明する。まず、フロー制御装置１２の制御部２３は、上述したフロー制御のパラメータである処理ユニット１３での「専有時間の上限値」に基づいて、フローの切り替えタイミングの確認を行う（ステップＳ２０１）。
【００６７】
制御部２３がフロー切り替えタイミングではないと判断した場合において（ステップＳ２０２：ＮＯ）、退避パケット保持部２６の入力部２６１にパケットが入力された場合（ステップＳ２０３：ＹＥＳ）、メモリ制御部２６２は、退避用メモリ２６３の一時パケットリストに入力されたパケットを追加する（ステップＳ２０４）。メモリ制御部２６２によるパケットの退避用メモリ２６３の一時パケットリストへの追加処理の詳細は後述する。
【００６８】
なお、図８Ａおよび図８Ｂに示したように、退避用メモリ２６３において、パケットが格納されたノードは、逐次パケットリストに追加されるわけではなく、実際にはフロー切り替えタイミングまで、一時パケットリストとして管理される。
【００６９】
制御部２３がフロー切り替えタイミングであると判断した場合（ステップＳ２０２：ＹＥＳ）、退避用メモリ２６３の一時パケットリストをパケットリストにマージする（ステップＳ２０５）。その後、退避パケット保持部２６は、動作モード２へ移行する（ステップＳ２０６）。なお、連結リストのマージ処理の詳細は後述する。
【００７０】
［一時パケットリストへのパケットの追加処理］
次に、図９で示した動作モード１における、一時パケットリストへのパケットの追加処理（ステップＳ２０４）について、図１０および図１１を参照して説明する。
まず、メモリ制御部２６２によるパケットの一時パケットリストへの追加処理の動作例について説明する。
【００７１】
図１０に示す例では、ノード０からノード４が空リストを表している。また、一時パケットリストでは、先頭ノードはポインタｐｈ＿ｔｍｐで、末尾ノードはポインタｐｔ＿ｔｍｐを用いて管理される。
【００７２】
図１０の最も左側に示す、一時パケットリストが空の状態から右側へ進むにしたがって、一時パケットリストにパケットが追加されていく。図１０に示す退避用メモリ２６３の構成において、図１０の最も左側の状態では、一時パケットリストの先頭ノードを指すポインタｐｈ＿ｔｍｐは、空リストの先頭ノードを指すポインタｅｈと一致している。
【００７３】
次に、図１０の左から２番目の状態では、パケット「Ａ１」が空リストの先頭ノード（ポインタｅｈが指すノード）に格納される。左から３番目の状態では、一時パケットリストの末尾ノードを示すポインタｐｔ＿ｔｍｐが空リストの先頭ノードを指すポインタｅｈの値に更新される。このようにして、一時パケットリストへのパケットの追加が行われる。
【００７４】
次に、図１０の最も右側の状態では、パケット「Ａ２」および「Ａ３」が同様に一時パケットリストに追加されている。空リストの先頭ノードを指すポインタｅｈは、ノード３を指し、一時パケットリストの先頭ノードを指すポインタｐｈ＿ｔｍｐは、パケット「Ａ１」が追加されているノード０を指している。また、一時パケットリストの末尾ノードを指すポインタｐｔ＿ｔｍｐは、パケット「Ａ３」が追加されているノード２を指している。
【００７５】
このように、新たなパケット「Ａ２」および「Ａ３」についても、これらのパケットが格納されたノードは、一時パケットリストとして保持されることがわかる。
【００７６】
次に、図１０で説明した、一時パケットリストへのパケットの追加処理について、さらに図１１のフローチャートを用いて説明する。
【００７７】
まず、メモリ制御部２６２は、退避用メモリ２６３において、空リストの先頭ノードを指すポインタｅｈと末尾ノードを指すポインタｅｔとが一致する場合には（ステップＳ３０１：ＹＥＳ）、処理を図９のステップＳ２０１（フロー切り替えタイミングの確認）に戻す。
【００７８】
一方、空リストのポインタｅｈとポインタｅｔとが一致しない場合には（ステップＳ３０１：ＮＯ）、メモリ制御部２６２は、入力部１１からパケットを取得する（ステップＳ３０２）。
【００７９】
次に、メモリ制御部２６２は、空リストのポインタｅｈが指す番地のノードに、取得したパケットを格納する（ステップＳ３０３）。その後、メモリ制御部２６２は、一時パケットリストの末尾ノードを指すポインタｐｔ＿ｔｐｍを空リストの先頭ノードを指すポインタｅｈに更新する（ステップＳ３０４）。
【００８０】
次に、メモリ制御部２６２は、空リストの先頭ノードを現在指しているポインタｅｈが、次のノードを指す（ｅｈ−＞ｎｅｘｔ）ように更新する（ステップＳ３０５）。
以上の手順により、パケットが一時パケットリストに追加される。
【００８１】
［マージ処理］
次に、図９で示した、フロー切り替えタイミングが生じた場合に、一時パケットリストをパケットリストにマージする処理（ステップ２０５）について、図１２および図１３を参照して説明する。図１２は、メモリ制御部２６２が行うマージ処理の動作例を示す。図１２に示す動作例では、ノード０からノード１がパケットリストを表し、ノード２からノード４が一時パケットリストを表している。
【００８２】
また、パケットリストにおいて、ポインタｐｈは先頭ノードを指し、ポインタｐｔは末尾ノードを指す。さらに、ポインタｐｔ＿ｐｒｅｖは、パケットリストの末尾ノードを指すポインタｐｔの１つ前のノードを指すポインタである。なお、「一つ前」とは、退避用メモリ２６３における論理的なリスト構造での前後関係を示しており、物理アドレスでの前後関係ではない。
【００８３】
また、図１２に示す例では、パケットリストが空である場合を想定しているが、パケットリストが空でない場合も同様の処理でマージ処理が可能である。
【００８４】
図１２に示す退避用メモリ２６３の論理構成において、灰色で示されるノードはパケットリストのノードであり、白色で示されるノードは一時パケットリストのノードである。まず、図１２の最も左側の退避用メモリ２６３の構成に示すように、一時パケットリストには、ノード２からノード４に、パケット「Ｂ１」「Ｂ２」、および「Ｂ３」が格納されている。パケット「Ｂ１」が格納されているノード２が、一時パケットリストの先頭ノードであり、パケット「Ｂ３」が格納されているノード４が、末尾ノードである。
【００８５】
次に、図１２の左から２番目の状態に示すように、メモリ制御部２６２は、ポインタｐｔ＿ｐｒｅｖが指すノード（ノード０）の矢印方向の次のノードを、一時パケットリストの先頭ノードを指すポインタｐｈ＿ｔｍｐが指すノード（ノード２）に更新する。
【００８６】
次に、図１２の左から３番目の状態に示すように、メモリ制御部２６２は、一時パケットリストのポインタｐｔ＿ｔｍｐが指すノード（ノード４）の次のノードを、パケットリストの末尾ノード（ポインタｐｔが指すノード１）に更新する。
【００８７】
さらに、図１２の最も右側の状態に示すように、メモリ制御部２６２は、ポインタｐｔ＿ｐｒｅｖをポインタｐｔ＿ｔｍｐに更新する。最後に、メモリ制御部２６２は、一時パケットリストの先頭ノードを指すポインタｐｈ＿ｔｍｐを、空リストの先頭ノードを指すポインタｅｈに更新する。以上によりメモリ制御部２６２のマージ処理が終了する。
【００８８】
次に、図１２で説明したマージ処理について、さらに図１３のフローチャートを参照して説明する。
【００８９】
まず、メモリ制御部２６２は、退避用メモリ２６３において、ポインタｐｔ＿ｐｒｅｖが指すノードの次（ｐｔ＿ｐｒｅｖ−＞ｎｅｘｔ）のノードが、ポインタｐｈ＿ｔｍｐが指すノードとなるように更新する（ステップＳ４０１）。
【００９０】
次に、メモリ制御部２６２は、ポインタｐｔ＿ｔｍｐが指すノードの次（ｐｔ＿ｔｍｐ−＞ｎｅｘｔ）のノードが、パケットリストの末尾ノードであるポインタｐｔが指すノードとなるように更新する（ステップＳ４０２）。
【００９１】
次に、メモリ制御部２６２は、ポインタｐｔ＿ｐｒｅｖをポインタｐｔ＿ｔｍｐに更新する（ステップＳ４０３）。その後、メモリ制御部２６２は、ポインタｐｈ＿ｔｍｐをポインタｅｈに更新して（ステップＳ４０４）、処理を動作モード２（図９、ステップＳ２０６）に戻す。
【００９２】
［退避パケット保持部の動作モード２］
次に、退避パケット保持部２６による動作モード２について、図１４のフローチャートを参照して説明する。
【００９３】
動作モード２の基本動作は、退避パケット保持部２６がパケットリストを先頭ノードから末尾ノードまで走査して、取り出すフローに一致するパケットを取り出すループ処理である。退避パケット保持部２６における走査処理の途中でパケットが入力された場合は、退避用メモリ２６３の一時パケットリストに、入力されたパケットが追加される。なお、以下において、ポインタ「ｓｐ」は、走査用のポインタを表す。
【００９４】
図１４に示すように、まず、入力部２６１にパケットが入力された場合には（ステップＳ５０１：ＹＥＳ）、メモリ制御部２６２は、入力されたパケットを退避用メモリ２６３の一時パケットリストに追加する（ステップＳ５０２）。
【００９５】
ステップＳ５０２で実行される一時パケットリストへのパケットの追加処理は、動作モード１における一時パケットリストへのパケットの追加処理（図９のステップＳ２０４、図１０および図１１）と同様の手順で行われる。
【００９６】
一方、入力部２６１にパケットが入力されていない場合（ステップＳ５０１：ＮＯ）、メモリ制御部２６２は、走査用ポインタｓｐが指すノードのパケットが、取り出すべきパケットか否かを判定する（ステップＳ５０３）。また、ステップＳ５０２で一時パケットリストにパケットが追加された後においても、処理はステップＳ５０３に移行する。なお、ステップＳ５０３の判定処理の詳細は後述する。
【００９７】
ステップＳ５０３の判定処理の後、メモリ制御部２６２は、走査用ポインタｓｐが、現在指しているノードの次（ｓｐ−＞ｎｅｘｔ）のノードを指すように更新する（ステップＳ５０４）。
【００９８】
次に、走査用ポインタｓｐが、パケットリストの末尾ノードを指すポインタｐｔと一致する場合（ステップＳ５０５：ＹＥＳ）、メモリ制御部２６２は、終端処理を行う（ステップＳ５０６）。その後、メモリ制御部２６２は、処理を動作モード１へ移行する（ステップＳ５０７）。なお、終端処理の詳細は後述する。
【００９９】
［取り出し判定処理］
次に、図１４に示した取り出し判定処理（ステップＳ５０３）について、図１５のフローチャートを参照して説明する。
【０１００】
まず、走査用ポインタｓｐが指すノードのパケットのフローが、取り出すべきフローと一致しない場合には（ステップＳ６０１：ＮＯ）、メモリ制御部２６２は、走査用ポインタｓｐの一つ前のノードを指すポインタｓｐ＿ｐｒｅｖが、現在指しているノードの次のノードを指すように更新する（ステップＳ６０２）。これにより、処理は図１４で示した走査用ポインタｓｐを更新するステップ（図１４、ステップＳ５０４）に戻される。
【０１０１】
なお、ポインタｓｐ＿ｐｒｅｖは、常に走査用ポインタｓｐの一つ前のノードを指すポインタである。「一つ前」とは、退避用メモリ２６３における論理的なリスト構造での前後関係を示しており、物理アドレスでの前後関係ではない。
【０１０２】
一方において、走査用ポインタｓｐが指すノードのパケットのフローが、取り出すべきフローと一致する場合には（ステップＳ６０１：ＹＥＳ）、メモリ制御部２６２は、走査用ポインタｓｐが指すノードのパケットを取り出して、出力部２６５を介して送信部２８に送出する（ステップＳ６０３）。
【０１０３】
次に、メモリ制御部２６２は、ポインタｅｔが指すノードの次（ｅｔ−＞ｎｅｘｔ）のノードが、走査用ポインタｓｐを指すノードとなるように更新する（ステップＳ６０４）。その後、メモリ制御部２６２は、ポインタｅｔを、走査用ポインタｓｐに更新する（ステップＳ６０５）。
【０１０４】
最後に、メモリ制御部２６２は、ポインタｓｐ＿ｐｒｅｖが指すノードの次（ｓｐ＿ｐｒｅｖ−＞ｎｅｘｔ）のノードが、走査用ポインタｓｐが指すノードの次（ｓｐ−＞ｎｅｘｔ）のノードを指すように更新する（ステップＳ６０６）。以上の手順によって、取り出し判定処理は終了し、処理は動作モード２のステップＳ５０４（図１４）に戻される。
【０１０５】
ここで、上述した取り出し判定処理において、走査用ポインタｓｐが指すノードのパケットのフローが、取り出すべきフローと一致する場合（ステップＳ６０１：ＹＥＳ）における、メモリ制御部２６２の動作例を図１６Ａから図１６Ｅを用いて説明する。
【０１０６】
図１６Ａから図１６Ｅに示す動作例では、ノード０からノード３までがパケットリストを表し、ノード４が空リストを表している。また、以下においては、パケットのフロー「Ａ」をメモリ制御部２６２が取り出すこととする。
【０１０７】
まず、図１６Ａに示すように、メモリ制御部２６２は、走査用ポインタｓｐが指すノード１のパケット「Ａ１」が属するフローが、取り出すべきフロー「Ａ」と一致することを確認する（図１５のステップＳ６０１）。
【０１０８】
次に、図１６Ｂに示すように、メモリ制御部２６２は、ノード１のパケット「Ａ１」を取り出して、出力部２６５を介して送信部２８に送出する（図１５のステップＳ６０３）。
【０１０９】
次に、図１６Ｃに示すように、メモリ制御部２６２は、ポインタｅｈの指すノード（ノード４）の次のノードを、走査用ポインタｓｐが指すノード（ノード１）に更新する（図１５のステップＳ６０４）。また、メモリ制御部２６２は、ポインタｅｔを走査用ポインタｓｐが指すノード（ノード１）に更新する（図１５のステップＳ６０５）。
【０１１０】
これにより、図１６Ｃに示すように、番地「４」の「次のノードの番地」の値が「１」となり、「空リストの末尾（ポインタｅｔ）」の値が「１」に更新されている。
【０１１１】
次に、図１６Ｄに示すように、メモリ制御部２６２は、ポインタｓｐ＿ｐｒｅｖが指すノード（ノード０）の次のノードを、走査用ポインタｓｐが指すノード（ノード１）の次のノード（ノード２）に更新する（図１５のステップＳ６０６）。
【０１１２】
最後に、図１６Ｅに示すように、メモリ制御部２６２は、走査用ポインタｓｐが指すノード（ノード１）を次のノード（ノード２）に更新する（図１４のステップＳ５０４）。以上の手順により、メモリ制御部２６２によるパケットの取り出し処理が行われる。
【０１１３】
一方、上述した取り出し判定処理において、走査用ポインタｓｐが示すノードのパケットのフローが、取り出すべきフローと一致しない場合（ステップＳ６０１：ＮＯ）における、メモリ制御部２６２の動作例を、図１７を用いて以下説明する。
【０１１４】
上述した図１６Ａから図１６Ｅと同様に、メモリ制御部２６２は、フロー「Ａ」のパケットを取り出す場合を考える。
【０１１５】
図１７の最も左側の退避用メモリ２６３の構成に示すように、走査用ポインタｓｐが指すノード（ノード１）にはパケット「Ｂ１」が格納されている。パケット「Ｂ１」が属するフロー「Ｂ」は、メモリ制御部２６２が取り出すべきフロー「Ａ」とは一致しない。
【０１１６】
この場合、図１７の左から２番目の状態に示すように、メモリ制御部２６２は、パケット「Ｂ１」を取り出さず、ポインタｓｐ＿ｐｒｅｖが指すノード（ノード０）を次のノード（ノード１）に更新する（図１５のステップＳ６０２）。
【０１１７】
また、図１７の最も右側の状態に示すように、メモリ制御部２６２は、走査用ポインタｓｐが指すノード（ノード１）を次のノード（ノード２）に更新する（図１４のステップＳ５０４）。以上が、走査用ポインタｓｐが指すノードのパケットのフローが取り出すべきフローと一致しない場合のメモリ制御部２６２の動作例である。
【０１１８】
［終端処理］
次に、図１４で説明した終端処理（ステップＳ５０６）について、図１８および図１９を参照して詳細に説明する。終端処理では、メモリ制御部２６２は、走査用ポインタｓｐと、走査用ポインタの一つ前のポインタｓｐ＿ｐｒｅｖの値を初期状態に戻す。また、パケットリストの末尾ノード（ポインタｐｔが指すノード）の一つ前のノードのパケットが取り出された場合、ポインタｐｔ＿ｐｒｅｖは正しい値ではなくなる。そのため、終端処理として、ポインタｐｔ＿ｐｒｅｖの値が修正される。
【０１１９】
まず、図１８に示すメモリ制御部２６２による終端処理の動作例を説明する。なお、図１８に示す例では、ノード０からノード３までがパケットリストを表している。
図１８の最も左側に示す退避用メモリ２６３の構成に示すように、走査用ポインタｓｐとパケットリストの末尾のポインタｐｔとが指すノード（ノード３）が一致している。
【０１２０】
次に、図１８の左から２番目の状態に示すように、メモリ制御部２６２は、ポインタｐｔ＿ｐｒｅｖを、走査用ポインタｓｐの一つ前のポインタｓｐ＿ｐｒｅｖの値（ノード２、パケット「Ｂ１」）に更新する。
【０１２１】
次に、図１８の左から３番目の状態に示すように、メモリ制御部２６２は、ポインタｓｐ＿ｐｒｅｖを、パケットリストの先頭を指すポインタｐｈ（ノード０）に更新する。
【０１２２】
その後、図１８の最も右側の状態に示すように、メモリ制御部２６２は、走査用ポインタｓｐが指すノード（ノード３）が、パケットリストにおける先頭のポインタｐｈの次のノード（ノード１）を指すように更新する。
【０１２３】
以上のように、メモリ制御部２６２は終端処理を実行し、走査用ポインタｓｐと走査用ポインタｓｐの一つ前のポインタｓｐ＿ｐｒｅｖの値を初期状態に戻す。
【０１２４】
次に、終端処理について図１９のフローチャートを用いて説明する。
まず、メモリ制御部２６２は、ポインタｐｔ＿ｐｒｅｖをポインタｓｐ＿ｐｒｅｖに更新する（ステップＳ７０１）。
【０１２５】
次に、メモリ制御部２６２は、ポインタｓｐ＿ｐｒｅｖをポインタｐｈに更新する（ステップＳ７０２）。その後、メモリ制御部２６２は、走査用ポインタｓｐをポインタｐｈが指すノードの次（ｓｐ−＞ｎｅｘｔ）のノードを指すように更新する（ステップＳ７０３）。以上の手順により終端処理が終了し、処理は動作モード２から動作モード１へ移行する（図１４、ステップＳ５０７）。
【０１２６】
このように、メモリ制御部２６２が走査用ポインタｓｐを用いて走査を末尾ノードまで行うと、終端処理を経て動作モード１に移行する。
【０１２７】
以上説明したように、本実施の形態によれば、受信したパケットを振り分け可能なキュー２７が存在しない場合に、退避パケット保持部２６はパケットを退避させて格納し、保持しているパケットから、所定のフローのパケットのみを、そのパケットの入力順に取り出して、後段の送信部２８に送出する。そのため、空のキュー２７が存在しない状態で新たなフローに属するパケットが入力された場合であっても、後続パケットの入力のストールを抑制することができ、並列化された処理ユニットの利用効率を向上させることが可能である。
【０１２８】
また、パケットを保持するメモリの断片化を防止することができ、メモリリソースの消費量をより抑えることが可能である。
【０１２９】
以上、本発明のフロー制御装置および方法における実施の形態について説明したが、本発明は説明した実施の形態に限定されるものではなく、請求項に記載した発明の範囲において当業者が想定し得る各種の変形を行うことが可能である。
【０１３０】
本発明の実施の形態で説明したフロー制御装置、および処理ユニットは、汎用プロセッサ、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、アプリケーションに固有の集積回路（ＡＳＩＣ）、その他のプログラマブル論理デバイス、ディスクリートゲートあるいはトランジスタロジック、ディスクリートハードウェア部品、または上述した機能を実現するために設計された上記いずれかの組み合わせを用いて実現することができる。
【０１３１】
また、本発明の処理ユニットは、汎用プロセッサが記憶装置に格納されたプログラムに従って処理を実行することによっても実現することができる。
【符号の説明】
【０１３２】
１０…データ処理装置、１１…入力部、１２…フロー制御装置、１３…処理ユニット、１４…出力部、２０…入力バッファ、２１…受信部、２２…解析部、２３…制御部、２４…割当情報記憶部、２５…振分部、２６…退避パケット保持部、２７…キュー、２８…送信部、２６１…入力部、２６２…メモリ制御部、２６３…退避用メモリ、２６４…ポインタ記憶部、２６５…出力部。
【図１】
2019140553.tif 000003
【図２】
2019140553.tif 000004
【図３】
2019140553.tif 000005
【図４】
2019140553.tif 000006
【図５】
2019140553.tif 000007
【図６Ａ】
2019140553.tif 000008
【図６Ｂ】
2019140553.tif 000009
【図６Ｃ】
2019140553.tif 000010
【図７】
2019140553.tif 000011
【図８Ａ】
2019140553.tif 000012
【図８Ｂ】
2019140553.tif 000013
【図９】
2019140553.tif 000014
【図１０】
2019140553.tif 000015
【図１１】
2019140553.tif 000016
【図１２】
2019140553.tif 000017
【図１３】
2019140553.tif 000018
【図１４】
2019140553.tif 000019
【図１５】
2019140553.tif 000020
【図１６Ａ】
2019140553.tif 000021
【図１６Ｂ】
2019140553.tif 000022
【図１６Ｃ】
2019140553.tif 000023
【図１６Ｄ】
2019140553.tif 000024
【図１６Ｅ】
2019140553.tif 000025
【図１７】
2019140553.tif 000026
【図１８】
2019140553.tif 000027
【図１９】
2019140553.tif 000028