(57)【要約】【課題】  広帯域伝送路の高速化に適応した拡張が可能であり、各パケット処理部の動作効率の向上が可能である負荷分散装置を提供する。【解決手段】  負荷分散装置１００は、ｎ段に直列接続された同一構成のパケット処理モジュールを備える。１段目のパケット処理モジュールは、パケット処理部４と、入力パケットを入力順にＰ１１ポートとＰ１２ポートとのいずれかに振り分けるパケット振り分け部７と、パケット振り分け部７による入力パケットの振り分け先とその順序とを「振り分け先順序情報」として記憶する振り分け先順序記憶部１０と、Ｐ１１ポートに対応するＰ１３ポートから処理結果パケットを入力し、Ｐ１２ポートに対応するＰ１４ポートから返送パケットを入力し、「振り分け先順序情報」に基づき、処理結果パケットと返送パケットとの出力順序を決定し出力パケットとしてＰ１５ポートから出力する並べ替え部１３とを備えた。【選択図】        図１
2007116350.tif 000002
【特許請求の範囲】
【請求項１】
パケット処理の負荷を分散する負荷分散装置において、
パケットを処理するパケット処理部と、
処理対象である複数のパケットのそれぞれを入力パケットとして順次入力し、順次入力した入力パケットのそれぞれを、入力順に、前記パケット処理部に処理用パケットとして出力するための第１ポートと転送パケットとして通過させるための第２ポートとのいずれかの振り分け先に振り分けるパケット振り分け部と、
前記パケット振り分け部が前記第１ポートと前記第２ポートとのいずれかの振り分け先に入力パケットのそれぞれを振り分けた場合に、振り分け先と振り分け先の順序とを振り分け先順序情報として記憶する振り分け先順序記憶部と、
前記第１ポートに対応する第３ポートから前記パケット処理部が処理用パケットを処理した処理結果パケットを入力し、前記第２ポートに対応する第４ポートから前記パケット振り分け部が前記第２ポートに振り分けた転送パケットに対応する返送パケットを入力し、前記振り分け先順序記憶部が記憶した前記振り分け先順序情報に基づいて、入力した処理結果パケットと返送パケットとの出力順序を決定し、決定した出力順序にしたがって処理結果パケットと返送パケットとを出力パケットとして出力ポートである第５ポートから出力する出力順序制御部と
を有するｎ（ｎ≧２）個のパケット処理モジュールを備え、
前記ｎ個のパケット処理モジュールは、
１段目からｎ段目にわたるｎ段の直列接続であって、
直列接続における互いに隣接する２つのパケット処理モジュールのうち後段のパケット処理モジュールは、前段のパケット処理モジュールから出力された転送パケットを入力パケットとして入力し、自己の出力する出力パケットを前段のパケット処理モジュールに返送パケットとして出力する直列接続を形成することを特徴とする負荷分散装置。
【請求項２】
前記出力順序制御部は、
前記振り分け先順序記憶部が記憶する前記振り分け先順序情報の示す振り分け先の順序にしたがって、前記振り分け先順序情報の示す振り分け先が前記第１ポートの場合には前記第３ポートから入力した処理結果パケットを出力パケットとして前記第５ポートから出力し、前記振り分け先順序情報の示す振り分け先が前記第２ポートの場合には前記第４ポートから入力した返送パケットを出力パケットとして前記第５ポートから出力することを特徴とする請求項１記載の負荷分散装置。
【請求項３】
前記パケット処理部は、
前記第１ポートを介して処理用パケットを入力した場合に、次の処理用パケットを前記第１ポートへ振り分けることを許可する振り分け許可パケットを前記第３ポートに出力し、
前記パケット振り分け部は、
前記第１ポートに処理用パケットを振り分けた後は、前記パケット処理部から前記第３ポートを介して振り分け許可パケットを入力するまで、次の処理用パケットを前記第１ポートに振り分けず、前記第２ポートに転送パケットを振り分けることを特徴とする請求項１記載の負荷分散装置。
【請求項４】
前記パケット処理部は、
振り分け許可パケットを出力するべきタイミングを振り分け許可パケット出力タイミングとして予め記憶し、予め記憶した前記振り分け許可パケット出力タイミングにしたがって振り分け許可パケットを出力することを特徴とする請求項３記載の負荷分散装置。
【請求項５】
前記パケット処理部は、
前記第１ポートを介して入力する処理用パケットを一時的に保管する処理側受信バッファを備えるとともに、前記処理側受信バッファが次の処理用パケットを保管可能な場合に、振り分け許可パケットを出力することを特徴とする請求項３記載の負荷分散装置。
【請求項６】
前記パケット振り分け部は、
前記第１ポートに振り分ける処理用パケットを一時的に保管する振り分け側バッファを備えるとともに、前記振り分け側バッファが次の処理用パケットを保管可能となるまで、前記第２ポートに転送パケットを振り分けることを特徴とする請求項１記載の負荷分散装置。
【請求項７】
前記パケット振り分け部は、
入力パケットを構成する一連のデータ列の入力と、前記第１ポートと前記第２ポートとのいずれかへの振り分けとを、並列処理することを特徴とする請求項１記載の負荷分散装置。
【請求項８】
前記出力順序制御部は、
前記第３ポートから入力する処理結果パケットを一時的に保管する処理結果パケット用バッファと、
前記第４ポートから入力する返送パケットを一時的に保管する返送パケット用バッファとを備え、
前記振り分け先順序情報に基づいて、前記処理結果パケット用バッファが保管した処理結果パケットと、前記返送パケット用バッファが保管した返送パケットとの出力順序を決定し、決定した前記出力順序にしたがって前記処理結果パケット用バッファが保管した処理結果パケットと前記返送パケット用バッファが保管した返送パケットとを出力パケットとして前記第５ポートから出力することを特徴とする請求項１記載の負荷分散装置。
【請求項９】
前記振り分け先順序記憶部は、
前記振り分け先順序情報を前記出力順序制御部に出力し、
前記出力順序制御部は、
前記振り分け先順序記憶部から振り分け先が前記第１ポートを示す前記振り分け先順序情報を入力した後に前記第３ポートから処理結果パケットを入力した場合には、入力した処理結果パケットを前記処理結果パケット用バッファに留めることなく前記出力パケットとして前記第５ポートから出力し、
前記振り分け先順序記憶部から振り分け先が前記第２ポートを示す前記振り分け先順序情報を入力した後に前記第４ポートから返送パケットを入力した場合には、入力した返送パケットを前記返送パケット用バッファに留めることなく前記出力パケットとして前記第５ポートから出力することを特徴とする請求項８記載の負荷分散装置。
【請求項１０】
前記パケット振り分け部は、
前記パケット処理部の障害の発生を監視して障害が発生したかどうかを判定し、障害が発生したと判定した場合には、以降の入力パケットを転送パケットとして前記第２ポートに振り分けることを特徴とする請求項３記載の負荷分散装置。
【請求項１１】
前記パケット振り分け部は、
前記第１ポートに処理用パケットを振り分けた場合に処理用パケットを振り分けてからの経過時間を計測し、予め設定された設定時間を経過しても前記第３ポートから振り分け許可パケットの入力がない場合には、前記パケット処理部に障害が発生したと判定することを特徴とする請求項１０記載の負荷分散装置。
【請求項１２】
前記パケット処理部は、
自己の障害の発生を検出した場合に障害の発生を示す障害報告パケットを前記第３ポートを介して前記パケット振り分け部に出力し、
前記パケット振り分け部は、
前記障害報告パケットを入力した場合には、以降の入力パケットを前記第２ポートに振り分けることを特徴とする請求項１記載の負荷分散装置。
【請求項１３】
前記負荷分散装置は、さらに、
第ｎ段目の負荷分散モジュールに接続し、第ｎ段目のパケット処理モジュールがパケットを出力した場合に、そのパケットを入力して第ｎ段目パケット処理モジュールに返送する終端モジュールを備えたことを特徴とする請求項１記載の負荷分散装置。
【請求項１４】
前記終端モジュールは、
入力したパケットを第ｎ段目パケット処理モジュールに返送するときに、オーバーフローを示す情報をパケットに付加して返送することを特徴とする請求項１３記載の負荷分散装置。
【請求項１５】
ｎ段目のパケット処理モジュールの有する前記パケット振り分け部は、
入力した入力パケットを前記第１ポートにのみ振り分けることを特徴とする請求項１記載の負荷分散装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、パケット処理の負荷を分散する負荷分散装置に関する。
【背景技術】
【０００２】
広帯域の伝送路から受信したパケットに暗号処理等の重い処理を行なう場合、複数の処理装置にパケット単位で分散処理させることにより装置全体としてのスループットを確保するとともに、パケットの転送順序を保存するための工夫が必要である。そのため、種々の負荷分散装置が利用されている。
【０００３】
従来の負荷分散装置では、広帯域伝送路から受信したパケットをひとつの負荷分散装置から複数の狭帯域伝送路上のデータ変換装置へ集中的に分配し、分配後に複数のデータ変換装置間の通信や外部の制御装置との連携によって処理結果パケットの送出順序を維持していた。（例えば、特許文献１）。また、複数の拡張系をスイッチで接続し、各拡張系内部のルーティングテーブルを工夫することでパケットの転送順序を制御するとともに、負荷分散を図る方法も考案されている（例えば、特許文献２）。
【特許文献１】特開２００３−２１８９３８号公報  第４頁〜５頁、第１図
【特許文献２】特開２０００−１３８６８７号公報  第３頁〜５頁、第１図
【発明の開示】
【発明が解決しようとする課題】
【０００４】
従来の負荷分散装置は、広帯域伝送路から受信したパケットを複数のデータ変換装置に分配する機構に負荷が集中するため、広帯域伝送路の高速化にともないハードウェア規模が大きくなり実装コストが膨らむという課題があった。また、受信パケットのパケット長のばらつきに即した適正な負荷バランスの調整が十分考慮されていないため、各データ変換装置の動作効率が下がるという課題があった。
【０００５】
この発明は、広帯域伝送路の高速化に適応した拡張が可能であり、各データ変換装置（パケット処理部）の動作効率の向上が可能である負荷分散装置を提供することを目的とする。
【課題を解決するための手段】
【０００６】
この発明の負荷分散装置は、
パケット処理の負荷を分散する負荷分散装置において、
パケットを処理するパケット処理部と、
処理対象である複数のパケットのそれぞれを入力パケットとして順次入力し、順次入力した入力パケットのそれぞれを、入力順に、前記パケット処理部に処理用パケットとして出力するための第１ポートと転送パケットとして通過させるための第２ポートとのいずれかの振り分け先に振り分けるパケット振り分け部と、
前記パケット振り分け部が前記第１ポートと前記第２ポートとのいずれかの振り分け先に入力パケットのそれぞれを振り分けた場合に、振り分け先と振り分け先の順序とを振り分け先順序情報として記憶する振り分け先順序記憶部と、
前記第１ポートに対応する第３ポートから前記パケット処理部が処理用パケットを処理した処理結果パケットを入力し、前記第２ポートに対応する第４ポートから前記パケット振り分け部が前記第２ポートに振り分けた転送パケットに対応する返送パケットを入力し、前記振り分け先順序記憶部が記憶した前記振り分け先順序情報に基づいて、入力した処理結果パケットと返送パケットとの出力順序を決定し、決定した出力順序にしたがって処理結果パケットと返送パケットとを出力パケットとして出力ポートである第５ポートから出力する出力順序制御部と
を有するｎ（ｎ≧２）個のパケット処理モジュールを備え、
前記ｎ個のパケット処理モジュールは、
１段目からｎ段目にわたるｎ段の直列接続であって、
直列接続における互いに隣接する２つのパケット処理モジュールのうち後段のパケット処理モジュールは、前段のパケット処理モジュールから出力された転送パケットを入力パケットとして入力し、自己の出力する出力パケットを前段のパケット処理モジュールに返送パケットとして出力する直列接続を形成することを特徴とする。
【発明の効果】
【０００７】
この発明により、広帯域伝送路の高速化に適応した拡張が可能であり、各データ変換装置（パケット処理部）の動作効率の向上が可能である負荷分散装置を提供することができる。
【発明を実施するための最良の形態】
【０００８】
実施の形態１．
図１〜図２７を用いて実施の形態１を説明する。実施の形態１は、複数の負荷分散部を直列に接続し、各負荷分散部は、入力したパケットを２つのポートのいずれかに送り出し、２つのポートに送り出した順番を記憶し、さらに自己に返送されたパケットをその順番で並べ替えて前段の負荷分散部に返送する負荷分散装置に関する。
【０００９】
なお、実施の形態１は、パケット処理モジュールにおける負荷分散部とパケット処理部との間を広帯域の伝送路で接続し、負荷分散部からパケット処理部へは即座に入力パケットを送信することを想定している。
【００１０】
図１は、実施の形態１における負荷分散装置１００のハードウェアブロック図である。図１において、パケット処理部と負荷分散部とは一つのハードウェアシステムであるパケット処理モジュールを構成する。負荷分散装置１００は、同一のハードウェア構成のｎ個のパケット処理モジュールと、終端部１６（終端モジュール）とを備える。ｎ個のパケット処理モジュールは、１段目からｎ段目にわたり直列に接続されている。具体的には、負荷分散部１（１段目）〜負荷分散部３（ｎ段目）は、それぞれ直列に接続され、終端部１６で終端される。
また、
負荷分散部１（１段目）はパケット処理部４と接続し、
負荷分散部２（２段目）はパケット処理部５と接続し、
負荷分散部３（ｎ段目）はパケット処理部６と接続している。
【００１１】
図２は、１段目の負荷分散部１のポートを示す。他の負荷分散部についても同様である。
（１）Ｐ１０ポートは、処理対象のパケットである「入力パケット」の受信ポートである。
（２）Ｐ１１ポート（第１ポート）は、パケット処理部４へ入力パケットを「処理用パケット」として送信するポートである。
（３）Ｐ１２ポート（第２ポート）は、後段の負荷分散部２へ入力パケットを「転送パケット」として送信するポートである。
（４）Ｐ１３ポート（第３ポート）は、パケット処理部４が処理用パケットを処理したパケットである「処理結果パケット」を受信するポートである。
（５）Ｐ１４ポート（第４ポート）は、後段の負荷分散部２の出力する出力パケットを「返送パケット」として受信するポートである。
（６）Ｐ１５ポート（第５ポート）は、並べ替え部１３の並べ替えた処理結果パケット、返送パケットを「出力パケット」として出力するポートである。
【００１２】
図１に示す様に、負荷分散部１は、パケット振り分け部７と、振り分け先順序記憶部１０と、並べ替え部１３（出力順序制御部）とを備える。パケット振り分け部７は、振り分け先順序記憶部１０へ振り分け順序書込み信号３５を送る。また、振り分け先順序記憶部１０は、並べ替え部１３へ、振り分け順序読み出し信号３８を送る。
【００１３】
振り分け先順序記憶部１０は、振り分け順序書込み信号３５（後述のＷ１）で指示される順序にしたがって入力パケットの転送先ポート番号を後述の「振り分け先順序情報」として記憶するとともに、書込み順序にしたがって書き込まれた転送先ポート番号を読み出す機能を備える。「振り分け先順序情報」については、図１４、図１５での説明で後述する。
【００１４】
図３は、負荷分散装置１００において、入力パケットが１段目のパケット処理モジュールからｎ段目のパケット処理モジュールに向かう場合の動作を説明する図である。図３を用いてこの動作を説明する。
（１）負荷分散部１は、Ｐ１０ポートから入力パケットを受信すると、パケット振り分け部７の制御によりＰ１１ポートからパケット処理部４へ入力パケットを処理用パケットとして送信する（Ｓ１０１）。
（２）パケット処理部４は、処理用パケットを受信するとこれを処理し、処理結果パケットとしてＰ１３ポートに送信する（Ｓ１０２）。負荷分散部１の並べ替え部１３は、受信した処理結果パケットをＰ１５ポートに出力パケットとして出力する。
（３）一方、パケット処理部４がパケット処理中で次の処理用パケットを受け付けられない場合、負荷分散部１は、Ｐ１０ポートで受信した入力パケットをパケット振り分け部７の制御によりＰ１２ポートから負荷分散部２のＰ２０ポートに転送する（Ｓ１０３）。
（４）負荷分散部２も負荷分散部１と同様に、Ｐ２０ポートで受信した入力パケットをパケット振り分け部８の制御によって、パケット処理部５に送るか（Ｓ１０４）、Ｐ２２ポートに転送する（Ｓ１０５）。
（５）入力パケットは、負荷分散部１（１段目）から負荷分散部３（ｎ段目）に至るまで直列に接続された複数の負荷分散部に接続されるいずれかのパケット処理部に送信されるまでは、負荷分散部１（１段目）から負荷分散部３（ｎ段目）に向かって順次転送される。
（６）末端に位置する負荷分散部３（ｎ段目）まで入力パケットが順次転送され（Ｓ１０６）、かつ、負荷分散部３（ｎ段目）でもパケット処理部６（ｎ段目）へ入力パケットを処理用パケットとして送信できない場合は、終端部１６が受信し（Ｓ１０７）、オーバーフローが発生した旨の情報を付加（Ｓ１０８）して負荷分散部３へ返送する（Ｓ１０９）。
（７）オーバーフローが発生した旨の情報を付加されたパケットは、負荷分散部３を経由して図１の左方向（前段方向）に順次返送され、負荷分散部１から出力される。このパケット対しては、後段の装置で再送や廃棄などの処理を行なえるようにする。
【００１５】
なお、本実施の形態１では、ｎ段目のパケット処理モジュールが出力した転送パケットに対して、終端部１６は、オーバーフローが発生した旨の情報を付加してｎ段目のパケット処理モジュールへ返送するようにしている。しかし、これに限るものではなく、終端部１６は、受信したパケットを、そのままｎ段目のパケット処理モジュールに返送しても構わない。
【００１６】
また、本実施の形態１では、負荷分散装置１００は、終端部１６を備えているが、備えていなくても構わない。この場合、ｎ段目のパケット処理モジュールのパケット振り分け部は、入力パケットの全てをパケット処理部に振り分けるようにすればよい。
【００１７】
次に、図４、図５〜図１３、図１４、図１５を用いて、パケット処理の負荷分散の動作を説明する。
図４は、負荷分散部１と負荷分散部２による入力パケットの処理フローを示すデータフロー図である。
図５〜図１３は、図４の個々の状態を説明する図である。
図１４と図１５とは、負荷分散部１、負荷分散部２の「振り分け先順序情報」を示す。
図４では、負荷分散部１のＰ１０ポートに入力パケットＤ１が到達した時刻をＴ１とし、Ｔ７に至るまでの期間を示す。図４の左端には、負荷分散部１と負荷分散部２との入出力ポート名を示し、また、負荷分散部１の振り分け順序書込み信号３５をＷ１として示し、負荷分散部２の振り分け順序書込み信号３６をＷ２として示している。以下では、振り分け順序書込み信号３５を単に「Ｗ１」と表し、振り分け順序書込み信号３６を単に「Ｗ２」と表す場合がある。
【００１８】
図４を中心に、また、図５〜図１３を参照して説明する。図４の時刻Ｔ１からＴ７にわたり、図５に示すように負荷分散部１のＰ１０ポートがパケットＤ１からパケットＤ７を連続して受信した場合を想定する。この場合、図６に示す様に、負荷分散部１は、パケット振り分け部７の制御により、Ｐ１１ポートからＤ１を処理用データとしてパケット処理部４へ送信するとともに、「Ｗ１」（ＮＯ．１）により、Ｐ１１ポートへ送信した旨を振り分け先順序記憶部１０に記憶する。図１４は、負荷分散部１の振り分け先順序記憶部１０が記憶する「振り分け先順序情報」の一例を示している。また、図１５には、負荷分散部２の振り分け先順序記憶部１１が記憶する「振り分け先順序情報」の一例を示している。図１４では、振り分け先順序記憶部１０が、振り分け先であるポート名と、書込みの順序（振り分け先の順序に同じである）とを「振り分け先順序情報」として記憶する場合を示している。図１５も同様に、振り分け先順序記憶部１１が、ポート名と、書込みの順序とを「振り分け先順序情報」として記憶する場合を示している。図１４、図１５における書込みの順序を示す「ＮＯ」（ナンバー）は、図４及び後述の図１６に示す「ＮＯ」に対応している。
【００１９】
図７に示す様に、処理用パケットＤ１を受信したパケット処理部４は、Ｄ１の処理を進めている。このため、パケット振り分け部７は、以降のＤ２からＤ４までをパケット処理部４へは振り分けない。図７のように、パケット振り分け部７は、これらのＤ２からＤ４の入力パケットをＰ１２ポートに、転送パケットとして出力するとともに、「Ｗ１」（ＮＯ．２〜ＮＯ．４）により、Ｐ１２ポートへ送信した旨を振り分け先順序記憶部１０に記憶する。
【００２０】
図８に示す様に、負荷分散部２（２段目）では、Ｐ２０ポートで負荷分散部１から転送された転送パケットＤ２〜Ｄ４を、入力パケットとして受け取る。Ｄ２については、パケット振り分け部８の制御でパケット処理部５へ処理用パケットとしてＰ２１ポートから送信すると共に、「Ｗ２」（ＮＯ．１）によりＰ２１ポートから送信した旨を振り分け先順序記憶部１１に記憶する。Ｄ３とＤ４については、パケット処理部５がＤ２を処理中のため、パケット処理部５に振り分けられない。このため、パケット振り分け部８の制御で、Ｐ２２ポートへ転送すると共に、「Ｗ２」（ＮＯ．２，ＮＯ．３）によりＰ２２ポートへ転送した旨を振り分け先順序記憶部１１に記憶する。
【００２１】
一方、次に図９に示す様に、１段目のパケット処理部４は、Ｄ１を受信してパケット処理を進め、次の入力パケット（処理用パケット）を受信できるようになった時点で、負荷分散部１のＰ１３ポートへ、処理用パケットを受付可能であることを伝える「振り分け許可パケットＡ１１」を発行する。図４では、時刻Ｔ４で「振り分け許可パケットＡ１１」が発行されている。この場合、負荷分散部１のパケット振り分け部７は、次のＴ５から入力パケットをパケット処理部４へ送信するよう制御する。
【００２２】
次に図１０に示す様に、この制御により、パケット振り分け部７は、図４の時刻Ｔ５に入力された入力パケットＤ５を、Ｐ１１ポートからパケット処理部４に向けて出力すると共に、「Ｗ１」（ＮＯ．５）により、Ｐ１１ポートから送信した旨を、振り分け先順序記憶部１０に記憶する。
【００２３】
次に図１１に示す様に、以降、パケット処理部４はＤ５を処理するので、パケット振り分け部７は、Ｄ６とＤ７とをパケット処理部４へは振り分けない。パケット振り分け部７は、Ｐ１２ポートからＤ６とＤ７とを負荷分散部２へ転送すると共に、「Ｗ１」（ＮＯ．６，ＮＯ．７）によりＰ１２ポートから転送した旨を振り分け先順序記憶部１０に記憶する。
【００２４】
次に図１２に示す様に、負荷分散部２（２段目）では、パケット処理部５が、Ｄ２の処理を図４のＴ５で完了する見込みがついたため、Ｔ４の後半からＴ５にかけて、「振り分け許可パケットＡ２２」を負荷分散部２のＰ２３ポートに発行する。これをうけて、負荷分散部２のパケット振り分け部８は、以降の入力パケットをパケット処理部５へ転送するよう制御する。
【００２５】
したがって、図１３に示す様に、図４の時刻Ｔ６で、負荷分散部２が入力パケットＤ６を受信した際、パケット振り分け部８は、入力パケットＤ６をＰ２１ポートからパケット処理部５へ送信すると共に、「Ｗ２」（ＮＯ．４）によりＰ２１ポートからＤ７を送信した旨を、振り分け先順序記憶部１１に記憶する。図１３に示すように、次のＤ７については、パケット処理部５がＤ６の処理を行なっているため、Ｄ７をパケット処理部５へは送信できない。このため、パケット振り分け部８は、Ｄ７をＰ２２ポートから転送するとともに、「Ｗ２」（ＮＯ．５）によりＰ２２ポートから転送した旨を振り分け先順序記憶部１１に記憶する。
【００２６】
以上、図５から図１３で説明した内容は、主にパケットを振り分ける動作を説明した。次に、図１６〜図２４を用いて、並べ替え部によるパケットの並べ替え動作を説明する。
【００２７】
次に図１６及び図１７〜図２４を用いて、パケット処理モジュールが自己のパケット処理部が処理した処理結果パケットと後段のパケット処理モジュールから返送された返送パケットとに対する並べ替え動作を説明する。図１６は、負荷分散部１（１段目）と負荷分散部２（２段目）とによる、処理結果パケットと返送パケットとの処理フローを示すデータフロー図であり図４に対応する。図１６は、パケット処理部４から処理結果パケットＤ１がＰ１３ポートへ送信された時刻をＴ１としてＴ７に至るまでの期間を示す。図１７〜図２４は、図１６の個々の状態を説明する図である。図１６を中心に、また図１７〜図２４を参照して以下に説明する。
【００２８】
図１６では、左端に負荷分散部１と負荷分散部２の入出力ポート名を示す。また、左端に負荷分散部１の振り分け順序読み出し信号３８を「Ｒ１」で示し、負荷分散部２の振り分け順序読み出し信号３９を「Ｒ２」で示す。以下の説明では、振り分け順序読み出し信号３８を単に「Ｒ１」で表し、振り分け順序読み出し信号３９を「Ｒ２」で表す場合がある。図１６では、パケットＤ１からパケットＤ７までの振り分け先と、それらに関する振り分け先順序記憶部１０及び１１の記憶内容は、図４で説明した振り分け先と振り分け順序とを引き継ぐものとする。
【００２９】
なお、振り分け先順序記憶部１０は、例えば、ＦＩＦＯ（Ｆｉｒｓｔ  Ｉｎ  Ｆｉｒｓｔ  Ｏｕｔ）メモリを想定する。ＦＩＦＯメモリが空のときは、振り分け先順序記憶部１０に振り分け先ポート情報（例えばＰ１１ポート等）が書き込まれた次の瞬間には、並べ替え部１３から見ることが可能となる。ただし、この情報を読み出さなければ、その情報の内容を知ることはできない。図１６において、Ｔ１で「Ｒ１」としてみえているＰ１１は、Ｔ１以前でパケットの転送処理をしていない場合は、Ｔ１以前から出力されているものである。次のＰ１２への変化は、並べ替え部１３がＤ１をＰ１５へ送り出す際、「Ｒ１」からＰ１２を読み出した結果、Ｔ２でＰ１２ポートの情報が見えた状況を表す。具体的な手順としては、パケットを受信した場合には「Ｒ１」を確認し、「Ｒ１」の内容に従ってパケットの転送を開始する。パケット転送が終わるころに「Ｒ１」のデータを読み出して、次のデータを出力させる。
【００３０】
図１７に示す様に、図１６の時刻Ｔ１でパケット処理部４から処理結果パケットＤ１が負荷分散部１のＰ１３ポートに送信されると、負荷分散部１の並べ替え部１３が、振り分け先順序記憶部１０の「Ｒ１」（ＮＯ．１）によりＰ１１ポートへの送信履歴を確認する。そして、並べ替え部１３は、Ｐ１３ポートで受信された処理結果パケットを、Ｐ１５ポートへ出力するよう制御する。これにより、処理結果パケットＤ１が出力パケットとしてＰ１５ポートへ出力される。
【００３１】
次に図１８に示す様に、並べ替え部１３は、図１７に示した処理結果パケットＤ１の送信後、図１６の時刻Ｔ２からＴ４の間、振り分け先順序記憶部１０の「Ｒ１」（ＮＯ．２〜ＮＯ．４）より、Ｐ１２ポートへ振り分けられたことを示す送信履歴を確認する。そして、並べ替え部１３は、この送信履歴に基づいて、Ｐ１４ポートで受信される連続する３つの返送パケットをＰ１５ポートへ転送するように制御する。これにより、並べ替え部１３により、Ｐ１４ポートで受信される返送パケットＤ２〜Ｄ４が、Ｐ１５ポートへ転送され、出力パケットとして出力される。
【００３２】
次に図１９に示す様に、図１６の時刻Ｔ５では、Ｐ１３ポートに処理結果パケットＤ５が送信されていると共に、Ｐ１４ポートには返送パケットＤ６が返送されている。この場合、振り分け先順序記憶部１０の「Ｒ１」（ＮＯ．５）にはＰ１１ポートへの送信履歴が示されている。よって、並べ替え部１３は、Ｐ１３ポートで受信した処理結果パケットＤ５をＰ１５ポートへ出力する。
【００３３】
次に図２０に示す様に、図１６の時刻Ｔ６とＴ７では、振り分け先順序記憶部１０の「Ｒ１」（ＮＯ．６、ＮＯ．７）には、Ｐ１２ポートへの転送履歴が連続して示されている。よって、並べ替え部１３は、返送パケットＤ６とＤ７とをＰ１５ポートから出力する。
【００３４】
ここで、例えば、図２１のように、処理結果パケットＤ５の到着が送れて時刻Ｔ５で受信できていない場合であっても、ＮＯ．５の「Ｒ１」はＰ１１となっている。このため、並べ替え部１３は、図２２に示すように、Ｐ１３からのパケット（処理結果パケットＤ５）を待つ。並べ替え部１３は、処理結果パケットＤ５を受信してＰ１５ポートへ転送するまで、振り分け先順序記憶部１０の「Ｒ１」の出力をＰ１１に保持する。これにより、図２２のように、パケット転送経路をＰ１３ポートからＰ１５ポートに保持し、返送パケットＤ６とＤ７をＰ５１ポートから出力する前に処理結果パケットＤ５をＰ１５ポートから出力する。
【００３５】
一方、図２３に示す様に、負荷分散部２（２段目）では、図１６の時刻Ｔ１でパケット処理部５から処理結果パケットＤ２がＰ２３ポートに届いていると共に、振り分け先順序記憶部１１の「Ｒ２」（ＮＯ．１）にＰ２１ポートへの送信履歴が示されている。よって、並べ替え部１４は、Ｐ２３ポートで受信した処理結果パケットＤ２をＰ２５ポートへ出力パケットとして出力する。
【００３６】
次に図２４に示す様に、図１６の時刻Ｔ２からＴ３の間では、振り分け先順序記憶部１１の「Ｒ２」（ＮＯ．２、ＮＯ．３）には、Ｐ２２ポートへの転送履歴が連続して示されている。よって、並べ替え部１４は、Ｐ２４ポートで受信した返送パケットＤ３とＤ４とをＰ２５ポートへ出力する。
【００３７】
この間、図１６における時刻Ｔ３では、図２４に示すように、パケット処理部５から処理結果パケットＤ６がＰ２３ポートへ送られてくる。しかし、並べ替え部１４は、時刻Ｔ４で振り分け先順序記憶部１１の「Ｒ２」にＰ２１ポートへの送信履歴が示される時刻Ｔ４まで、処理結果パケットＤ６のＰ２５ポートからの送信を保留する。また、図１６において、負荷分散部２では、時刻Ｔ４には返送パケットＤ７がＰ２４ポートに到着するが、並べ替え部１４は、時刻Ｔ５において振り分け先順序記憶部１１の「Ｒ２」にＰ２２ポートの転送履歴が示されるまで、返送パケットＤ７のＰ２５ポートからの送信を保留する。
【００３８】
ここで、図１６において、例えば、返送パケットＤ４が遅れて、時刻Ｔ３で受信できていない場合を考える。この場合、並べ替え部１４は、送信履歴としてＰ２１（ＮＯ．４）よりも前にＰ２２（ＮＯ．３）が示されているため、Ｐ２４ポートから返送パケットＤ４を受信しＰ２５ポートへ転送するまで、振り分け先順序記憶部１１の「Ｒ２」の出力をＰ２２に保持することにより、図２４に示すように、パケット転送経路をＰ２４ポートからＰ２５ポートに保持する。これにより、並べ替え部１４は、処理結果パケットＤ６をＰ２５ポートから出力する前に、返送パケットＤ４をＰ２５ポートから出力する。
【００３９】
次に、図２５を用いて、負荷分散部１の内部における振り分け制御と並べ替え制御との具体的な動作を説明する。図２５は、１段目パケット処理モジュールにおける負荷分散部１とパケット処理部４との内部構成を示すハードウェアブロック構成図である。
【００４０】
パケット処理部４は、処理用データ受信部５２と、受信バッファ５３（処理側受信バッファ）と、演算処理部５４と、送信バッファ５５と、処理結果データ送信部５６とを備える。
【００４１】
パケット振り分け部７は、入力データ受信部４１と、処理用データ送信部４２と、転送データ送信部４３と、処理結果データ受信部４４と、振り分け順序判定部５０とを備える。
【００４２】
並べ替え部１３は、処理結果パケット用バッファ４５と、返送データ受信部４６と、返送パケット用バッファ４７と、選択回路４８と、出力データ送信部４９と、並べ替え判定部５１とを備える。
【００４３】
（１）入力データ受信部４１は、入力パケットを受信する。
（２）処理用データ送信部４２は、パケット処理部４へ処理用パケットを送信する。
（３）転送データ送信部４３は、負荷分散部２へ転送パケットを送信する。
（４）処理結果データ受信部４４は、パケット処理部４から処理結果パケット、振り分け許可パケットＡ１１等を受信する。なお、処理結果データ受信部４４は振り分け許可パケットＡ１１を受信すると「振り分け許可信号５８」を振り分け順序判定部５０に送信し、入力パケットをパケット処理部４へ振り分け可能な旨を通知する。
（５）処理結果パケット用バッファ４５は、パケット処理部４から送られる複数の処理結果パケットを保管する。
（６）返送データ受信部４６は、負荷分散部２から返送される返送パケットを受信する。
（７）返送パケット用バッファ４７は、負荷分散部２から返送される複数の返送パケットを保管する。
（８）選択回路４８は、処理結果パケット用バッファ４５内のパケットか返送パケット用バッファ４７内のパケットのいずれか一方を選択して出力パケットとする。
（９）出力データ送信部４９は、選択回路４８で選択されたパケットを出力パケットとして出力する。
（１０）振り分け順序判定部５０は、入力データ受信部４１からの入力パケット受信信号５７と処理結果データ受信部４４からの「振り分け許可信号５８」を受けて、入力パケットの出力先を決定する。
（１１）並べ替え判定部５１は、振り分け先順序記憶部１０から振り分け順序読み出し信号３８（Ｒ１）を受けて処理結果パケットを出力するか返送パケットを出力するかを決定する。
（１２）処理用データ受信部５２は、パケット処理部４で処理用パケットを受信する。
（１３）受信バッファ５３は、パケット処理部４内で処理用パケットをパケット処理前に一旦保管する。
（１４）演算処理部５４は、パケット処理部４内のパケット処理を行なう。
（１５）送信バッファ５５は、演算処理部５４から出力される処理結果パケットを送信前に一旦保管する。
（１６）処理結果データ送信部５６は、パケット処理部４から処理結果パケットを送信する。
【００４４】
図２６は，パケット処理部４へ振り分けられる処理用パケットの流れを示すフローチャートである。図２６を用いて、入力パケットをパケット処理部４へ処理用パケットとして振り分けてから処理結果パケットがＰ１５ポートから出力されるまでの過程を図２５に示した各構成要素の動作とともに説明する。
【００４５】
入力パケットがＰ１０ポートに到着すると、入力データ受信部４１は、連続的に送られてくる一連のパケットデータを順に受け取ると共に、「入力パケット受信信号５７」を振り分け順序判定部５０に送信することにより、振り分け順序判定部０に入力パケットの到着を伝える（Ｓ４０１）。
【００４６】
振り分け順序判定部５０は、処理結果データ受信部４４から「振り分け許可信号５８」を受信することによりパケット処理部４への振り分けが可能であることを判定した場合は、それ以降、入力データ受信部４１から「入力パケット受信信号５７」を受信した時点で、入力データ受信部４１の出力データ（入力パケットを構成する一連のデータ）を処理用データ送信部４２が受け取るよう制御する（Ｓ４０２）。
【００４７】
処理用データ送信部４２は、入力データ受信部４１の出力データを受け取ると、このデータをＰ１１ポートへ処理用データとして送信する（Ｓ４０３）。
【００４８】
パケット処理部４は、Ｐ１１ポートに出力される処理用パケットの一連のデータを処理用データ受信部５２により順に受け取り、受信バッファ５３に保管する（Ｓ４０４）。
【００４９】
パケット処理部４は、受信バッファ５３に処理用パケットが一式保管された時点で、演算処理部５４に処理用パケットを送りパケット処理を開始する（Ｓ４０５）。なお、処理用パケットの受信速度に比べ演算処理部５４の処理速度が遅い場合は、受信バッファ５３に処理用パケット一式が完全に保管される前に、演算処理部５４へデータを送り出し、パケット処理を開始してもよい。
【００５０】
演算処理部５４による処理結果は順次送信バッファ５５に蓄えられ（Ｓ４０６）、処理結果パケットとして一式そろった時点で、処理結果データ送信部５６からＰ１３ポートに送信する（Ｓ４０７）。
【００５１】
処理結果データ送信部５６から送信された処理結果パケットは、負荷分散部１のＰ１３ポートに送られ、負荷分散部１の処理結果データ受信部４４で受信される（Ｓ４０８）。
【００５２】
処理結果データ受信部４４で受信された処理結果パケットは、並べ替え判定部５１の制御により出力データ送信部４９へ送られＰ１５ポートから出力されるまで、処理結果パケット用バッファ４５に保管される。処理結果パケット用バッファ４５は、複数の処理結果パケットを蓄えることができる（Ｓ４０９）。
【００５３】
並べ替え判定部５１は、振り分け先順序記憶部１０の「Ｒ１」を常に観測し、入力パケットの転送履歴から出力データ送信部４９への送信元（処理結果パケット用バッファ４５か返送パケット用バッファ４７か）を判定する。そして、並べ替え判定部５１は、選択回路４８により処理結果パケット用バッファ４５の出力か返送パケット用バッファ４７の出力かを出力データ送信部４９への出力として選択する（Ｓ４１０）。
【００５４】
ここでは、振り分け順序判定部５０が入力パケットをパケット処理部４へ送信した時点で、「Ｗ１」によってＰ１１ポートへのパケット転送を振り分け先順序記憶部１０に記録する。これに対応して「Ｒ１」によって、並べ替え判定部５１はＰ１１ポートへのパケット転送履歴を認識し、選択回路４８を制御し処理結果パケット用バッファ４５の出力を出力データ送信部４９へ振り向ける。この制御により、パケット処理部４でのパケット処理が完了し、処理結果パケットが処理結果パケット用バッファ４５に送られるときには、処理結果パケットは、処理結果バッファに留められることなく、即座に、出力データ送信部４９へ転送され、出力パケットとしてＰ１５ポートから出力される。
【００５５】
この転送動作は、処理結果パケットを構成する一連のパケットデータが、Ｐ１３ポートに到着してから、処理結果データ受信部４４が受け取り、処理結果パケット用バッファ４５、選択回路４８及び出力データ送信部４９を経由してＰ１５ポートに出力される間、途切れなく実行される。これにより、Ｐ１３ポートとＰ１５ポートの間のカットスルー動作が実現される。
【００５６】
以上、図２６におけるＳ４０１〜Ｓ４１０の説明では、パケット処理部４が、入力パケットを処理用パケットとして受け付ける場合について説明した。次に図２７を用いて、パケット処理部４に障害が発生した場合等の動作を説明する。
【００５７】
図２７は、パケット処理部４による振り分け許可パケットの出力動作、及び障害が発生した場合の動作を示すフローチャートである。振り分け順序判定部５０は、Ｓ４０２で説明したように、パケット処理部４の入力パケット受付可否を、処理結果データ受信部４４から「振り分け許可信号５８」を受け取ることによって判断する。この「振り分け許可信号５８」は、処理結果データ受信部４４が、パケット処理部４の送信した「振り分け許可パケットＡ１１」を受信した場合に送信する信号である。
【００５８】
（１）パケット処理部４は、入力パケット（処理用パケット）を受け付けられるようになった時点で、「振り分け許可パケットＡ１１」を負荷分散部１のＰ１３ポートに送る（Ｓ５０１）。
（２）処理結果データ受信部４４は、「振り分け許可パケットＡ１１」を受信すると、「振り分け許可信号５８」によって、パケット処理部４へ振り分け可能な旨を、振り分け順序判定部５０に通知する（Ｓ５０２）。
（３）振り分け順序判定部５０は、振り分け許可信号５８を受け取った後、次の入力パケットの受信を「入力パケット受信信号５７」によって伝えられる。そして、振り分け順序判定部５０は、当該入力パケットをパケット処理部４へ送信するまで、パケット処理部４は入力パケット受付可能と判断する（Ｓ５０３）。振り分け順序判定部５０は、入力パケットをパケット処理部４へ送信した後は、次の「振り分け許可信号５８」を受け取るまで、パケット処理部４は、処理用パケットを受付しないと判断する。
（４）パケット処理部４は、「振り分け許可パケットＡ１１」を発行するべきタイミングを、「振り分け許可パケット出力タイミング」として予め記憶しておく。パケット処理部４は、その「振り分け許可パケット出力タイミング」に従って、「振り分け許可パケットＡ１１」を出力する。例えば、一例として次の場合が考えられる。パケット処理部４は、「振り分け許可パケット出力タイミング」として、演算処理部５４によるパケット処理の残り時間ｔ１が、振り分け許可パケットを発行してから次の処理用パケットが送られてくるまでの最短時間ｔ２より短くなった時点（ｔ１＜ｔ２の時点）で、「振り分け許可パケットＡ１１」を発行する。あるいは、別の「振り分け許可パケット出力タイミング」として、受信バッファ５３に保存されている処理用パケットのデータ量が減り、次の処理用パケットを受信する余裕ができた時点を「振り分け許可パケットＡ１１」を出力タイミングとしてもよい。
【００５９】
次に、負荷分散部１のパケット振り分け部７が、パケット処理部４に障害が発生したと判定する場合を説明する。パケット振り分け部７は、パケット処理部４の障害の発生を監視し、障害が発生したかどうかを判定する。パケット振り分け部７は、パケット処理部４に障害が発生したと判定した場合は、以降の入力パケットを転送パケットとしてＰ１２ポートに振り分けるとともに、パケット処理部４の障害発生の通知を並べ替え部１３に出力する。並べ替え部１３は、パケット振り分け部７から障害発生の通知を入力すると、Ｐ１４ポートから入力した返送パケットのみをＰ１５ポートから出力する。以下では、パケット処理部４からの振り分け許可パケットの送信時間を計測する場合を説明する。
（１）パケット振り分け部７の振り分け順序判定部５０は、入力パケットをパケット処理部４へ送信してから、「振り分け許可パケットＡ１１」に基づき処理結果データ受信部４４が送信する「振り分け許可信号５８」を受け取るまでの経過時間を計測することによりパケット処理部４の障害の発生を監視する（Ｓ５０４）。そして、振り分け順序判定部５０は、規定の時間を過ぎても「振り分け許可信号５８」が送られてこない場合は、パケット処理部４に障害が発生したものと判定する。そして、振り分け順序判定部５０は、以降の入力パケットを全てＰ１２ポートへ転送するとともに、並べ替え判定部５１に、パケット処理部４の障害発生を通知する（Ｓ５０５）。
（２）並べ替え判定部５１は、パケット処理部４に障害が発生したという連絡を受け取ると、処理結果パケット用バッファ４５に保管されている処理結果パケットの送信完了を待って、振り分け先順序記憶部１０から読み出されるＰ１１ポートへの送信履歴を廃棄し、Ｐ１４ポートからの返送パケットをＰ１５ポートへ出力するよう制御する（Ｓ５０６）。
【００６０】
次に、パケット処理部４が、自己の障害発生を検出する場合を説明する。
（１）パケット処理部４は、自己の障害等のため処理結果パケットを送信できなくなった場合、振り分け許可パケットＡ１１の代わりに、自己の障害の発生を通知する「障害報告パケット」を負荷分散部１に送信する（Ｓ５０７）。
（２）処理結果データ受信部４４は、「障害報告パケット」を受信すると、振り分け順序判定部５０にパケット処理部４の障害発生を通知する（Ｓ５０８）。
（３）振り分け順序判定部５０は、その障害発生の通知を受け取ると、以降の入力パケットを全てＰ１２ポートへ転送するとともに、並べ替え判定部５１にパケット処理部４の障害を通知する（Ｓ５０９）。
（４）並べ替え判定部５１は、この通知を受け取ると、前記Ｓ５０６の処理を行なう。
【００６１】
「障害報告パケット」を発行したパケット処理部４に対する処置としては、負荷分散部１から切り離すなどして修復後、再度、負荷分散部１へ接続する。そして、パケット処理部４から「振り分け許可パケットＡ１１」を負荷分散部１へ発行するようにすることで、負荷分散部１は、パケット処理部４へ入力パケットを振り分けることを再開することが可能となる。
【００６２】
また、パケット処理部４の障害の場合とは別に、パケット処理部４を保守などのために一時的に負荷分散部１から切り離したい場合もある。このような場合には、処理用パケットの振り分けの停止を求める「振り分け停止パケット」をパケット処理部４から負荷分散部１へ出力させるようにする。負荷分散部１は、パケット処理部４から「振り分け停止パケット」を受け取った場合には、以降の入力パケットのパケット処理部４への振り分けを停止する。「振り分け停止パケット」の場合は、「障害報告パケット」の場合とは異なり、処理中のパケットがパケット処理部４に残っている場合は、パケット処理部４は、これら処理中のパケットの処理を継続する。なお、パケット処理部４への振り分け再開は、障害からの復旧と同様に、パケット処理部４から負荷分散部１へ「振り分け許可パケットＡ１１」を発行することで行なうことができる。
【００６３】
次に入力パケットを転送パケットとしてＰ１２ポートへ振り分ける場合について説明する。パケット処理部４が、処理用パケットを処理中であったり、あるいは障害の発生のために入力パケット（処理用パケット）を受け付けられない間、振り分け順序判定部５０は、入力データ受信部４１が受信した入力データを転送データ送信部４３へ転送する。これより、入力パケットが負荷分散部２に振り分けられる。例えば、入力パケットの一連のパケットデータをパケット処理部４へ送信し終わった直後、連続して入力パケットがＰ１０ポートに届いたとする。この場合、振り分け順序判定部５０は、以降の入力データ（入力パケットを構成するデータ）を転送データ送信部４３へ転送する。この場合、入力データ受信部４１が受信した入力パケットの一連の入力データは、連続的に転送データ送信部４３に送られてＰ１２ポートから送信され、カットスルー動作が行なわれる。ここで、振り分け順序判定部５０は、入力パケットをＰ１２ポートから負荷分散部２へ転送すると同時に、振り分け先順序記憶部１０に「Ｗ１」により、振り分け先ポートとしてＰ１２ポートを書き込む。書き込み結果は、「Ｒ１」によって並べ替え判定部５１に伝えられる。これらの動作は、前記図４、図１６の説明で述べた通りである。
【００６４】
次に、Ｐ１４ポートから返送パケットを受信してＰ１５ポートから出力する場合について説明する。
（１）負荷分散部２（２段目）へ転送された入力パケット（転送パケット）は、パケット処理部５（２段目）以降のいずれかのパケット処理部でパケット処理され、負荷分散部２を介して負荷分散部１のＰ１４ポートに再び返送される。返送された返送パケットの一連のパケットデータは、返送データ受信部４６で受信され、返送パケット用バッファ４７に保管される。返送パケット用バッファ４７は、複数の返送パケットを保管することができる。
（２）並べ替え判定部５１は、振り分け先順序記憶部１０からの「Ｒ１」によりＰ１２ポートへの振り分け履歴を確認すると、選択回路４８を制御して、返送パケット用バッファ４７の出力を出力データ送信部４９へと接続する。
（３）このとき、返送パケット用バッファ４７に返送パケットが保管されていれば、返送パケットの一連のパケットデータが選択回路４８を経由して出力データ送信部４９へと送られ、Ｐ１５ポートから返送パケットが出力される。一方、返送パケット用バッファ４７に返送パケットがまだ届いていない場合は、返送パケットが届くまで、選択回路４８の状態は維持される。このように選択回路４８が維持された状態で返送パケットがＰ１４ポートに届くと、返送データ受信部４６は、返送パケットの一連のパケットデータを順次受信しつつ、返送パケット用バッファ４７と選択回路４８とを経由して出力データ送信部４９へ連続的に送ることにより、カットスルー動作を実現する。
【００６５】
以上説明した実施の形態１の負荷分散装置１００は、パケット処理部４で入出力するパケットの順序を変えないことを前提に、本ハードウェア構成とパケット転送の手順を取ることで、最終的に出力されるパケットの順番を入力時の順番に合わせることが特徴である。各負荷分散部は、一つの入力を２系統に分岐する。分岐したパケットが帰ってくるタイミングはまちまちである。そこを、振り分け先順序記憶部に記憶した履歴に従って、元の入力順序に戻すという処理を積み重ねる。これにより、負荷分散装置に入力したパケットの順序を次第にそろえていく。例えば、ｋ段目の負荷分散部につながっているパケット処理部においてｎ番目のパケットの処理に時間がかかり、ｋ＋１段目以降に転送したｎ＋１段目以降のパケットがｋ段目の負荷分散部に戻ってきた場合、ｋ段目のパケット処理部からｎ番目のパケットが戻ってくるまで、ｎ＋１番目以降のパケットはｋ段目の負荷分散処理部を通過することはできない。逆に、ｋ＋１段目に送ったｎ番目のパケットの処理に時間がかかり、ｋ段目のパケット処理部に送ったｎ＋１番目のパケットが先に戻ってきたとしても、ｎ番目のパケットがｋ＋１段目の負荷分散部から返送されてｋ段目の負荷分散部を通過するまで、ｎ＋１番目のパケットは、ｋ段目の負荷分散部で待たされる。すなわち、ｋ段目の負荷分散部は、２つに分岐して送ったパケットが、分岐先ごとに送り出した順序で戻ってくれば、これらの戻りパケットを分岐させた順番で前段に送り返すことで、ｋ−１段目の負荷分散部から受け取った順番でパケットを戻すことができる。パケット処理部へ送り出したパケットは、パケット処理部の前提として順番を変えないことを保障する。ｋ＋１段目の負荷分散部に送り出したパケットが送り出した順序で戻ってくることは、例えば、パケットが届く最後段の負荷分散部がパケット処理部にのみパケットを送ることで決着する。最後段（ｍ段目）の負荷分散部は、ｍ−１段目の負荷分散部に、受け取った順序でパケットを戻す。よって、ｍ−１段目の負荷分散部は、２分岐したパケットがそれぞれ送り出した順序で受信できることが保障される。この結果、ｍ−１段目の負荷分散部は、ｍ−２段目の負荷分散部に、受け取った順番でパケットを返送することが可能となる。ｍ−２段目の負荷分散部も同様にして、パケットの順序を守ることができる。よって、以降、ｋ段目から１段目の負荷分散部にわたり、パケットの順序を守ることができる。
【００６６】
以上のように、実施の形態１における負荷分散装置１００は、負荷分散部のパケット振り分け部が入力パケットをパケット処理部と後段の負荷分散部へ振り分けるとともに、振り分け先順序記憶部がパケット振り分け部の振り分けた履歴である振り分け情報を記憶し、並べ替え部が振り分け情報を元にパケット処理部からの処理結果パケットと後段の負荷分散部から送られる返送パケットとを並べ替えて出力ポートであるＰ１５ポートから出力する。したがって、パケット処理の負荷を軽くすることができるとともに、少ない回路であっても広帯域の伝送路によるパケット伝送に対応することが可能となる。
【００６７】
また、実施の形態１の負荷分散装置１００は、複数の負荷分散部を直列に接続するので、入力パケットの処理負荷に応じて柔軟に拡張することができる。また、オンライン稼動中の拡張も可能である。よって、それぞれの負荷分散部の稼動状況を観測し、入力パケットの負荷が低下した時点で、パケット処理に関わっていない負荷分散部とパケット処理部の動作クロックとを停止したり、あるいは電源を遮断したりすることで、動的に省エネルギー化を図ることもできる。
【００６８】
更に、実施の形態１の負荷分散装置１００は、パケット振り分け部が、パケット処理部からの振り分け許可パケットに基づいて動的に負荷分散を行っている。このため、特定のパケット処理部への負荷集中や、特定のパケット処理部の負荷低下などの非効率的な動作を防ぐことができる。
【００６９】
また、実施の形態１の負荷分散装置１００は、各負荷分散部が、自身のパケット処理部に処理用パケットとして入力パケットを送るまではカットスルー動作により入力パケットを後段の負荷分散部へ転送する。また、処理結果パケットの返送に際しても、並べ替え判定が合致している間は返送パケットを複数の負荷分散部にわたってカットスルー動作により転送する。このため、広帯域伝送路の伝送速度を生かし、遅延を抑えたパケット転送ができる。
【００７０】
実施の形態１の負荷分散装置１００は、パケット振り分け部がパケット処理部の障害の発生を検出するので、迅速かつ容易に、パケット処理部の障害を知ることができる。また、パケット振り分け部は、パケット処理部に障害が発生したことを検出した後は、入力パケットを後段の負荷分散部に転送するので、あるパケット処理部に障害が発生した場合でも、パケット処理を継続して実行することができる。
【００７１】
実施の形態１の負荷分散装置１００は、パケット処理部が自身の障害の発生を検出するので、迅速かつ容易に、パケット処理部の障害を知ることができる。また、パケット振り分け部は、パケット処理部に障害が発生した後は、入力パケットを後段の負荷分散部に転送するので、あるパケット処理部に障害が発生した場合でも、パケット処理を継続して実行することができる。
【００７２】
実施の形態１の負荷分散装置１００は、ｎ段目のパケット処理モジュールが出力したパケットをｎ段目のパケット処理モジュールに返送する終端部を備えたので、ｎ段目のパケット処理モジュールが転送パケットを出力した場合でも、このパケットを確実に１段目のパケット処理モジュールに返すことができる。
【００７３】
実施の形態１の負荷分散装置１００は、ｎ段目のパケット処理モジュールが出力したパケットを入力してオーバーフローを示す情報を付加した後、そのパケットをｎ段目のパケット処理モジュールに返送する終端部を備えた。よって、他の装置は、未処理のパケットを容易に知ることが可能となる。
【００７４】
実施の形態１の負荷分散装置１００は、ｎ段目のパケット処理モジュールが、入力パケットをすべて処理用パケットとして、パケット処理へ出力するポートへ振り分けるので、ｎ段目のパケット処理モジュールへの入力パケットをすべて前段に返送することができる。
【００７５】
以上の実施の形態１の図１に示した負荷分散装置１００において、パケット処理モジュール及び終端部は、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）により制御されるハードウェアで実現される。すなわち、図１において「〜部」として説明したパケット処理部、パケット振り分け部等は、ＣＰＵにより制御されるハードウェアで実現される。しかし、これに限ることはなく、「〜部」として説明したものは、ハードウェアとソフトウェアの組合せ、あるいはソフトウェアで実現されても構わない。
【００７６】
実施の形態２．
以上の実施形態１では、負荷分散部１とパケット処理部４との間を広帯域の伝送路で接続し、負荷分散部１からパケット処理部４へは即座に入力パケットを送信することを想定した。実施の形態２は、パケット処理モジュールにおける負荷分散部とパケット処理部との間の伝送路を狭帯域化するような場合に、負荷分散部の内部で一旦入力パケットを保管する実施形態である。
【００７７】
図２８は、実施の形態２における、負荷分散部１とパケット処理部４の内部構成を示すハードウェアブロック構成図である。負荷分散部１のパケット振り分け部７が、入力データを一旦保管する処理用データバッファ５９（振り分け側バッファ）を備えた以外は、図２５と同一である。
【００７８】
次に、動作について説明する。
（１）入力パケットが負荷分散部１のＰ１０ポートに到着すると、入力データ受信部４１が入力パケットの一連のパケットデータを受信する。そして、振り分け順序判定部５０は、パケット処理部４へ入力データを送るために、処理用データバッファ５９にデータを転送する。
（２）処理用データバッファ５９は、一連のパケットデータを受信して保管すると同時に、処理用データ送信部４２にパケットデータを送る。
（３）処理用データ送信部４２は、負荷分散部１とパケット処理部４との間の伝送路の帯域に合わせて、パケット処理部４へ処理用データバッファ５９で受信した入力パケットのパケットデータを順次送信する。
（４）負荷分散部１とパケット処理部４との間の伝送路の帯域が、負荷分散部１の入力や負荷分散部２との間の伝送路の帯域より狭い場合、パケット処理部４へ入力パケットを送り終わる前に、処理用データバッファ５９に入力パケットが一式保管され、引続き、次の入力パケットの受信が始まる。この場合、パケット処理部４へは、直前の入力パケットが送られつつある段階のため、パケット処理部４から「振り分け許可パケットＡ１１」は発行されない。そのため、振り分け順序判定部５０は、次の入力パケットを、負荷分散部２へ転送する。
（５）パケット処理部４は、受信した処理用パケットのパケット処理が終わると、処理結果データ送信部５６からＰ１３ポートへ処理結果パケットの一連のパケットデータを送信する。
（６）負荷分散部１は、処理結果データ受信部４４により処理結果パケットのパケットデータを受信すると、処理結果パケット用バッファ４５に保管する。
（７）並べ替え判定部５１は、処理結果パケットが一式処理結果パケット用バッファ４５に保管された時点で、「Ｒ１」に示される振り分け履歴にしたがって、処理結果パケットを出力データ送信部４９へ送る。ここで、パケット処理部４から処理結果パケット用バッファ４５に処理結果パケットを保管するまでは、負荷分散部１とパケット処理部４との間の狭帯域伝送路の伝送速度に合わせてパケットデータが転送される。
（８）一方、処理結果パケット用バッファ４５から選択回路４８と出力データ送信部４９とを経てＰ１５ポートへ処理結果パケットを転送する場合は、広帯域の伝送路と同じ伝送速度でパケットデータが伝送される。
（９）なお、以上の動作説明では、入力パケットを処理用データバッファ５９に保管してから、パケット処理部４が振り分け許可を発行するまで振り分け順序判定部５０は入力パケットを後段の負荷分散部２へ転送するようにした。しかし、振り分け順序判定部５０で処理用データバッファ５９の空き容量を確認し、処理用データバッファ５９からパケット処理部４へのデータ転送が進んで次の入力パケットを保管する余裕ができたことを確認した時点で、入力パケットを処理用データバッファ５９へ書き込むように制御してもよい。この方法によれば、パケット処理部４から「振り分け許可パケットＡ１１」を発行しなくてもよい。
【００７９】
以上のように、実施の形態２の負荷分散装置２００によれば、負荷分散部１の処理用データバッファ５９が、一旦入力パケットを保管するようにしたので、負荷分散部１とパケット処理部４の間の伝送路を狭帯域にすることができ、ケーブル等による延長も可能となる。
【００８０】
以上の実施の形態では、以下の手段を備えたパケット処理の負荷分散装置を説明した。
（ａ）負荷分散部とパケット処理部を一組とし、それら複数組を負荷分散部で直列に接続することによって、前段の負荷分散部から受け取った入力パケットを後段の負荷分散部へ転送するとともに、後段の負荷分散部から受け取った処理結果パケットを前段の負荷分散部へ返送するパケット転送手段；
（ｂ）前段の負荷分散部から送られた入力パケットを、パケット処理部か後段の負荷分散部かのいずれか一方に振り分けるパケット振り分け手段；
（ｃ）前段の負荷分散部から送られた入力パケットの振り分け先順序を記憶する振り分け順序記憶手段；
（ｄ）パケット処理部からの処理結果パケットと後段の負荷分散部からの返送パケットを受け取り、振り分け順序記憶手段で記憶した振り分け先順序に従って前段の負荷分散部へ返送する処理結果パケットの並べ替え手段。
【００８１】
以上の実施の形態では、各負荷分散部は、自身に接続されたパケット処理部へ入力パケットを振り分けてから当該パケット処理部から振り分け許可を受け取るまで、以降の入力パケットを後段の負荷分散部へ振り分けることを特徴とする負荷分散装置を説明した。
【００８２】
以上の実施の形態では、パケット処理部は、次のパケット処理を受付可能となるまでの残り時間が振り分け許可送信後負荷分散部から次の入力パケットを受信するまでに要する最短時間を下回った時点で、負荷分散部へ振り分け許可を送ることを特徴とする負荷分散装置を説明した。
【００８３】
以上の実施の形態では、パケット処理部は、受信バッファを設け、当該受信バッファに次の入力パケットを受信する余裕ができた時点で、負荷分散部へ振り分け許可を送ることを特徴とする負荷分散装置を説明した。
【００８４】
以上の実施の形態では、負荷分散部にパケット処理部向け入力パケットを一時的に保管するバッファを設け、当該バッファに保管した入力パケットをパケット処理部へ送信して次の入力パケットを当該バッファに保管する余裕ができるまで、以降の入力パケットを後段の負荷分散部へ振り分けることを特徴とする負荷分散装置を説明した。
【００８５】
以上の実施の形態では、各負荷分散部は、入力パケットを構成する一連のデータ列の受信と振り分け先への送信を並列に実行することを特徴とする負荷分散装置を説明した（カットスルー動作）。
【００８６】
以上の実施の形態では、各負荷分散部は、パケット処理部から受け取った複数の処理結果パケットを保持する処理結果パケットバッファと後段の負荷分散部から返送される複数の返送パケットを保持する返送パケットバッファとを備えることを特徴とする負荷分散装置を説明した。
【００８７】
以上の実施の形態では、負荷分散部は、並べ替え手段によって当該負荷分散部に接続されているパケット処理部から受信する処理結果パケットを前段の負荷分散部へ返送することが予め指示されている場合は、受信した処理結果パケットを処理結果パケットバッファに留めることなく、前段の負荷分散部へ返送し、逆に、並べ替え手段によって後段の負荷分散部からの返送パケットを前段の負荷分散部へ返送することが予め指示されている場合は、受信した返送パケットを返送パケットバッファに留めることなく前段の負荷分散部へ返送することを特徴とする負荷分散装置を説明した（カットスルー動作）。
【００８８】
以上の実施の形態では、各負荷分散部は、入力パケットをパケット処理部へ転送した後、処理結果パケット受信までの時間を計測し、一定時間以上経過後も処理結果パケットが受信されない場合は、以降の入力パケットのパケット処理部への転送を停止すると共に、振り分け順序記憶手段に記憶されている当該パケット処理部への振り分け情報を廃棄することを特徴とする負荷分散装置を説明した。
【００８９】
以上の実施の形態では、パケット処理部は、障害が発生した際、当該パケット処理部が接続されている負荷分散部へ障害報告を発行し、障害報告を受けた当該負荷分散部は、入力パケットの振り分けを停止すると共に、振り分け順序記憶手段に記憶されている当該パケット処理部への振り分け情報を廃棄することを特徴とする負荷分散装置を説明した。
【００９０】
以上の実施の形態では、負荷分散部は、パケット処理部から振り分け許可を受け取ることで、入力パケットのパケット処理部への振り分けを再開することを特徴とする負荷分散装置を説明した。
【００９１】
以上の実施の形態では、直列に接続されている負荷分散部の最後段の負荷分散部から後段の負荷分散部向け入力パケットが出力された場合、オーバーフローを示すパケットを最後段の負荷分散部へ返送する終端部を備えることを特徴とする負荷分散装置を説明した。
【図面の簡単な説明】
【００９２】
【図１】実施の形態１における負荷分散装置１００のブロック図を示す。
【図２】実施の形態１における負荷分散装置１００のポートとパケットとの対応を示す。
【図３】実施の形態１における負荷分散装置１００の入力パケットの転送を示すフローチャートである。
【図４】実施の形態１における入力パケットの処理フローを示すデータフロー図である。
【図５】図４の個々の状態を示す図である。
【図６】図４の個々の状態を示す図である。
【図７】図４の個々の状態を示す図である。
【図８】図４の個々の状態を示す図である。
【図９】図４の個々の状態を示す図である。
【図１０】図４の個々の状態を示す図である。
【図１１】図４の個々の状態を示す図である。
【図１２】図４の個々の状態を示す図である。
【図１３】図４の個々の状態を示す図である。
【図１４】実施の形態１における振り分け先順序情報を示す。
【図１５】実施の形態１における振り分け先順序情報を示す。
【図１６】実施の形態１における処理結果パケットと返送パケットとのデータフロー図である。
【図１７】図１６の個々の状態を示す図である。
【図１８】図１６の個々の状態を示す図である。
【図１９】図１６の個々の状態を示す図である。
【図２０】図１６の個々の状態を示す図である。
【図２１】図１６の個々の状態を示す図である。
【図２２】図１６の個々の状態を示す図である。
【図２３】図１６の個々の状態を示す図である。
【図２４】図１６の個々の状態を示す図である。
【図２５】実施の形態１における負荷分散部１とパケット処理部４との内部構成を示す図である。
【図２６】実施の形態１におけるパケット処理部４への処理用パケットの流れを示す。
【図２７】実施の形態１におけるパケット処理部４に障害が発生した場合の動作を示すフローチャートである。
【図２８】実施の形態２における負荷分散装置２００における負荷分散部１とパケット処理部４との内部構成を示す。
【符号の説明】
【００９３】
１，２，３  負荷分散部、４，５，６  パケット処理部、７，８，９  パケット振り分け部、１０，１１，１２  振り分け先順序記憶部、１３，１４，１５  並べ替え部、１６  終端部、５２  処理用データ受信部、５３  受信バッファ、５４  演算処理部、５５  送信バッファ、５６  処理結果データ送信部、３５，３６，３７  振り分け順序書込み信号、３８，３９，４０  振り分け順序読み出し信号、４１  入力データ受信部、４２  処理用データ送信部、４３  転送データ送信部、４４  処理結果データ受信部、５０  振り分け順序判定部、５７  入力パケット受信信号、５８  振り分け許可信号、５９  処理用データバッファ、４５  処理結果パケット用バッファ、４６  返送データ受信部、４７  返送パケット用バッファ、４８  選択回路、４９  出力データ送信部、５１  並べ替え判定部、１００  負荷分散装置、２００  負荷分散装置。
【図１】
2007116350.tif 000003
【図２】
2007116350.tif 000004
【図３】
2007116350.tif 000005
【図４】
2007116350.tif 000006
【図５】
2007116350.tif 000007
【図６】
2007116350.tif 000008
【図７】
2007116350.tif 000009
【図８】
2007116350.tif 000010
【図９】
2007116350.tif 000011
【図１０】
2007116350.tif 000012
【図１１】
2007116350.tif 000013
【図１２】
2007116350.tif 000014
【図１３】
2007116350.tif 000015
【図１４】
2007116350.tif 000016
【図１５】
2007116350.tif 000017
【図１６】
2007116350.tif 000018
【図１７】
2007116350.tif 000019
【図１８】
2007116350.tif 000020
【図１９】
2007116350.tif 000021
【図２０】
2007116350.tif 000022
【図２１】
2007116350.tif 000023
【図２２】
2007116350.tif 000024
【図２３】
2007116350.tif 000025
【図２４】
2007116350.tif 000026
【図２５】
2007116350.tif 000027
【図２６】
2007116350.tif 000028
【図２７】
2007116350.tif 000029
【図２８】
2007116350.tif 000030