(57)【要約】【課題】汎用性の高い部品を用いてシステムを構成する場合であっても、処理に無駄が生じるのを抑制し、性能を向上するために役立つ負荷分散制御装置を提供すること。【解決手段】複数の情報処理装置を用いて並列処理を行う場合に、各々の情報処理装置の入力における情報パケット等の処理待ち時間Ｔｗ３［ｙ］を各情報パケット等の到着時刻ｔａと各バッファ上の処理待ち行列の数とに基づいて推定し、前記複数の情報処理装置の中で最も早く処理が可能な情報処理装置を振り分け先に決定する。情報処理装置の処理に空きができるのを防止でき、処理の無駄がなくなって性能の低下が生じない。振り分け先を情報パケット等の種別毎にグループ化して分ける。サービス種別毎に負荷の変動を検出し、各グループに割り当てる情報処理装置の装置台数などを動的に変更する。負荷分散装置における転送遅延時間を考慮して時間を算出する。【選択図】図１０
2018037957.tif 000002
【特許請求の範囲】
【請求項１】
予め構成が定められた単位情報の集合として順次に入力される入力データを、前記単位情報毎に区別して、予め用意された複数の情報処理装置の中のいずれかの入力に順次に振り分ける負荷分散制御装置であって、
前記複数の情報処理装置の各々の入力における前記単位情報の処理待ち時間を、前記単位情報の到着時刻と処理待ち行列の数とに基づいて推定し、前記複数の情報処理装置の中で、最も早く処理が可能な情報処理装置を振り分け先に決定する振り分け先決定部、を備えたことを特徴とする負荷分散制御装置。
【請求項２】
前記振り分け先決定部は、前記処理待ち時間を推定する際に、負荷分散制御装置と前記情報処理装置との間における前記単位情報の転送遅延時間を考慮して時間を算出する、請求項１に記載の負荷分散制御装置。
【請求項３】
前記複数の情報処理装置が、前記単位情報の種別毎に用意してある場合に、
前記振り分け先決定部は、到着した前記単位情報毎に、その種別を識別し、識別した種別に割り当てられた１つ又は複数の情報処理装置を振り分け先に決定する、請求項１に記載の負荷分散制御装置。
【請求項４】
前記振り分け先決定部は、前記単位情報の種別毎に、所定の部位を通過する情報量の変化を検出し、検出した前記情報量の変化を、前記単位情報の種別毎に割り当てる前記情報処理装置の少なくとも装置台数の変化に動的に反映する、請求項３に記載の負荷分散制御装置。
【請求項５】
前記振り分け先決定部は、前記単位情報の処理待ち時間を推定する際に、前記単位情報の処理に要する時間の長さを、前記単位情報から抽出した情報に基づいて特定する、請求項１乃至請求項４のいずれか１項に記載の負荷分散制御装置。
【請求項６】
前記振り分け先決定部は、前記単位情報の処理待ち時間を、前記単位情報の到着時刻と、処理待ち行列の数と、前記単位情報の種別とに基づいて推定する、請求項１に記載の負荷分散制御装置。
【請求項７】
予め構成が定められた単位情報の集合として順次に入力される入力データを、前記単位情報毎に区別して、予め用意された複数の情報処理装置の中のいずれかの入力に順次に振り分ける負荷分散制御方法であって、
前記複数の情報処理装置の各々の入力における前記単位情報の処理待ち時間を、前記単位情報の到着時刻と処理待ち行列の数とに基づいて推定し、前記複数の情報処理装置の中で、最も早く処理が可能な情報処理装置を振り分け先に決定する、ことを特徴とする負荷分散制御方法。
【請求項８】
予め用意された複数の情報処理装置と、予め構成が定められた単位情報の集合として順次に入力される入力データを、前記単位情報毎に区別して、前記複数の情報処理装置の中のいずれかの入力に順次に振り分ける負荷分散制御装置と、で構成される負荷分散処理システムであって、
前記複数の情報処理装置の各々の入力における前記単位情報の処理待ち時間を、前記単位情報の到着時刻と処理待ち行列の数とに基づいて推定し、前記複数の情報処理装置の中で、最も早く処理が可能な情報処理装置を振り分け先に決定する振り分け先決定部、を備えたことを特徴とする負荷分散処理システム。
【請求項９】
予め構成が定められた単位情報の集合として順次に入力される入力データを、前記単位情報毎に区別して、予め用意された複数の情報処理装置の中のいずれかの入力に順次に振り分ける負荷分散制御装置によって実行される負荷分散制御プログラムであって、
前記複数の情報処理装置の各々の入力における前記単位情報の処理待ち時間を、前記単位情報の到着時刻と処理待ち行列の数とに基づいて推定し、前記複数の情報処理装置の中で、最も早く処理が可能な情報処理装置を振り分け先に決定する振り分け先決定手順、をコンピュータに実行させるための負荷分散制御プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、負荷分散制御装置、負荷分散制御方法、負荷分散処理システムおよび負荷分散制御プログラムに関し、例えばパケット通信におけるパケット処理サーバのタスク処理や、様々な計算機における情報処理に利用可能な技術に関する。
【背景技術】
【０００２】
例えば、ＩＰ（Internet Protocol）パケット処理を行う通信システムにおいて、大量のパケットを扱う通信装置は、従来より高速処理が可能な高機能部品で構成されている。すなわち、高速ネットワーク専用のパケット処理部品やネットワーク専用ＣＰＵ（中央処理装置）を用いて構成した通信装置を利用している。また、このような通信装置を構成する専用の部品は、製造者が限られるため価格が高止まりする傾向にある。
【０００３】
これに対し、近年、汎用的に利用が可能なパケット処理部品や汎用ＣＰＵを用いた通信装置が幅広い製造者により製品化され始めている。つまり、汎用的に利用可能な部品は、出荷数が多く価格も安いので、安価な通信装置を提供することができる。また、非特許文献１に示されているように、汎用品を活用したネットワークの提案も行われている。
【０００４】
一方、重み付けフェアスケジューリング（ＷＦＱ：weighted fair queuing）の技術が非特許文献２に示されている。すなわち、複数のフローから入力されるパケットをキューに蓄えると共に、ゲートウェイがキューに蓄えられているパケットの中から処理対象のパケットを選択して処理するための技術が示されている。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】小野・吉岡・金子・他、"キャリアネットワークのあり方を変革する新R&DコンセプトNetroSphere構想の実現に向けた取り組み NetroSphere構想の実現に向けた取り組み"、ＮＴＴ技術ジャーナル、２０１５年８月１日、第２７巻、第８号、ｐ．１４−２１．
【非特許文献２】戸田巖、“詳解ネットワークＱｏＳ技術”、オーム社、２００１年５月、ｐｐ．１８９．
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、汎用的に利用が可能な部品を用いて通信装置を構成する場合には、汎用部品の単体での機能や性能が、一般的に高機能品に比べて劣る場合が多いため、その対策が必要となる。
【０００７】
そこで、例えば図１（ａ）に示した情報処理システム１０のように、負荷を分散し、複数台の処理装置で並列処理を行うように構成する。図１（ａ）に示した情報処理システム１０は、複数のｓ台の情報処理装置１４−１、１４−２、・・・、および１４−ｓで構成された処理装置群１２と、負荷分散装置１１と、情報出力部１３とを備えている。情報処理装置１４−１〜１４−ｓの各々の内部には、処理待ちバッファ１５および情報処理部１６が備わっている。
【０００８】
すなわち、入力情報１７は、負荷分散装置１１の制御により、複数のｓ台の情報処理装置１４−１〜１４−ｓのいずれかの入力にパケット毎に振り分けられる。情報処理装置１４−１〜１４−ｓの各々に入力されたパケットは、処理待ちバッファ１５上で順番に並んだ状態で一時的に保持され待ち行列（キュー）を形成する。そして、情報処理部１６の処理が空き状態になると、処理待ちバッファ１５上の待ち行列から順番にパケットが取り出され、このパケットは情報処理部１６に入力されて処理される。情報処理装置１４−１〜１４−ｓで処理が完了したパケットは、情報出力部１３から出力される。
【０００９】
一方、図１（ｂ）に示した情報処理装置１００は、高機能部品を用いて構成する場合を想定しているので、並列処理を行う必要がない。したがって、１台の情報処理装置１００だけで入力情報１７を処理することができ、負荷分散装置１１を設ける必要もない。情報処理装置１００の内部には、処理待ちバッファ１０１および情報処理部１０２が備わっている。すなわち、入力情報１７の各パケットは、処理待ちバッファ１０１上で順番に並んだ状態で一時的に保持され待ち行列（キュー）を形成する。そして、情報処理部１０２の処理が空き状態になると、処理待ちバッファ１０１上の待ち行列から順番にパケットが取り出され、このパケットは情報処理部１０２に入力されて処理される。
【００１０】
図１（ａ）に示した情報処理装置１４−１〜１４−ｓ内の各処理待ちバッファ１５−１〜１５−ｓ、および各情報処理部１６−１〜１６−ｓにおける情報パケット１８の状態の例を図２（ａ）に示す。また、図１（ｂ）に示した処理待ちバッファ１０１および情報処理部１０２における情報パケット１０３の状態の具体例を図２（ｂ）に示す。
【００１１】
図２（ａ）に示した構成において、処理待ちバッファ１５−１〜１５−ｓの箇所では、入力された情報パケット１８−２、１８−１は順番に並び、待ち行列を形成している。また、情報処理部１６−１、１６−２、・・・の各々の処理の窓口１６ａ−１、１６ａ−２、・・・においては、それぞれ１つの情報パケット１８−０が処理対象として保持されている。情報処理部１６−１、１６−２、・・・の各々は、情報パケット１８を１個ずつ順番に処理することができる。
【００１２】
一方、図２（ｂ）に示した構成において、処理待ちバッファ１０１の箇所では、入力された情報パケット１０３は順番に並び、待ち行列を形成している。また、情報処理部１０２の内部にはｓ個の処理の窓口１０２ａ−１、１０２ａ−２、・・・、１０２ａ−ｓが形成され、これらの各々の窓口に、それぞれ１個の情報パケット１０４が処理対象として保持されている。つまり、情報処理部１０２は高機能であるため、ｓ個の情報パケット１０４を効率よく並列処理することができる。
【００１３】
ところで、図１（ａ）および図２（ａ）に示したような構成において、パケットの並列分散処理を実施する場合には、負荷分散装置１１が複数の情報処理装置１４−１〜１４−ｓにパケットを振り分ける方法として、一般的な方法である「ラウンドロビン」を採用することが想定される。
【００１４】
すなわち、図３に示すように負荷分散装置１１の出力から処理待ちバッファ１５−１〜１５−ｓのいずれかの入力に情報パケット１８を振り分ける際に、負荷分散装置１１が処理待ちバッファ１５−１〜１５−ｓを順番に選択する。そして、選択した処理待ちバッファに情報パケット１８を順番に入力する。
【００１５】
しかしながら、図３に示した構成においては、処理待ちバッファ１５−１〜１５−ｓの各々に待ち行列として並んだ情報パケット１８の数が均一であるとは限らない。また、処理の窓口１６ａ−１〜１６ａ−ｓの各々における処理の所要時間が均一であるとも限らない。そのため、例えばｎ番目の情報処理部１６−ｎの処理が終了し、ｎ番目の処理の窓口１６ａ−ｎが空き状態になった時に、もしもｎ番目の処理待ちバッファ１５−ｎに情報パケット１８が存在しないと、情報処理部１６−ｎが有効な処理を実行することができず無駄が発生する。
【００１６】
一方、図２（ｂ）に示した構成の場合には、処理待ちバッファ１０１が１つだけである。そのため、処理待ちバッファ１０１上に情報パケット１０３が存在している限り、ｎ番目の処理の窓口１０２ａ−ｎが空き状態になった時には、新たな処理対象の情報パケット１０３を処理待ちバッファ１０１から処理の窓口１０２ａ−ｎに常に入力し処理することができる。したがって、処理の無駄は生じない。
【００１７】
つまり、汎用部品を用いて図１（ａ）のように構成した情報処理システム１０の場合には、高機能部品を用いて図１（ｂ）のように構成した情報処理装置１００と比べて、性能的に劣る点が課題である。
【００１８】
本発明は、上記の状況に鑑みてなされたものであり、汎用性の高い部品を用いてシステムを構成する場合であっても、処理に無駄が生じるのを抑制し、性能を向上するために役立つ負荷分散制御装置、負荷分散制御方法、負荷分散処理システムおよび負荷分散制御プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１９】
（１）予め構成が定められた単位情報の集合として順次に入力される入力データを、前記単位情報毎に区別して、予め用意された複数の情報処理装置の中のいずれかの入力に順次に振り分ける負荷分散制御装置であって、
前記複数の情報処理装置の各々の入力における前記単位情報の処理待ち時間を、前記単位情報の到着時刻と処理待ち行列の数とに基づいて推定し、前記複数の情報処理装置の中で、最も早く処理が可能な情報処理装置を振り分け先に決定する振り分け先決定部、を備える。
【００２０】
この負荷分散制御装置によれば、前記単位情報の処理待ち時間を前記複数の情報処理装置の各々の入力について推定するので、最も早く処理が可能な情報処理装置を振り分け先に決定できる。そのため、複数の処理待ちバッファのいずれかの待ち行列に空きができて、情報処理装置の処理に無駄が生じるような状況の発生を避けることができる。
【００２１】
（２）前記振り分け先決定部は、前記処理待ち時間を推定する際に、負荷分散制御装置と前記情報処理装置との間における前記単位情報の転送遅延時間を考慮して時間を算出する。
この負荷分散制御装置によれば、前記処理待ち時間を推定する際に前記転送遅延時間を考慮するので、処理待ち時間の推定精度を高めることができる。
【００２２】
（３）前記複数の情報処理装置が、前記単位情報の種別毎に用意してある場合に、
前記振り分け先決定部は、到着した前記単位情報毎に、その種別を識別し、識別した種別に割り当てられた１つ又は複数の情報処理装置を振り分け先に決定する。
【００２３】
この負荷分散制御装置によれば、複数種別の前記単位情報が混在した状態で共通の情報処理装置に振り分けられるのを避けることができる。これにより、情報処理装置における処理を高速化することができる。具体的には、処理対象の情報の種別の特定や種別の違いに応じた処理内容の切替が不要になり、更に種別の切り替わりに伴う割り込み信号の発生が無くなるため、効率よく処理を実行できる。
【００２４】
（４）前記振り分け先決定部は、前記単位情報の種別毎に、所定の部位を通過する情報量の変化を検出し、検出した前記情報量の変化を、前記単位情報の種別毎に割り当てる前記情報処理装置の少なくとも装置台数の変化に動的に反映する。
【００２５】
この負荷分散制御装置によれば、例えば特定種別の前記単位情報について入力される情報量が増えた時、すなわち負荷が増大したときに、前記特定種別に割り当てる前記情報処理装置の装置台数を増やして処理能力を向上させることができる。これにより、特定種別の前記単位情報について待ち行列が長くなり処理の待ち時間が増大するのを避けることが可能になる。
【００２６】
（５）前記振り分け先決定部は、前記単位情報の処理待ち時間を推定する際に、前記単位情報の処理に要する時間の長さを、前記単位情報から抽出した情報に基づいて特定する。
この負荷分散制御装置によれば、前記単位情報として様々な種類の情報を扱う場合に、前記単位情報の種類毎に処理の所要時間が大きく変動するような場合であっても、前記所要時間を高精度で特定することが容易になる。また、前記所要時間に基づいて、前記処理待ち時間を高精度で推定可能になる。
（６）前記振り分け先決定部は、前記単位情報の処理待ち時間を、前記単位情報の到着時刻と、処理待ち行列の数と、前記単位情報の種別とに基づいて推定する。この負荷分散制御装置によれば、単位情報の種別毎の特性に応じた処理負荷の大きさを考慮して高精度で処理待ち時間を推定できる。
【００２７】
（７）予め構成が定められた単位情報の集合として順次に入力される入力データを、前記単位情報毎に区別して、予め用意された複数の情報処理装置の中のいずれかの入力に順次に振り分ける負荷分散制御方法であって、
前記複数の情報処理装置の各々の入力における前記単位情報の処理待ち時間を、前記単位情報の到着時刻と処理待ち行列の数とに基づいて推定し、前記複数の情報処理装置の中で、最も早く処理が可能な情報処理装置を振り分け先に決定する。
【００２８】
この負荷分散制御方法によれば、前記単位情報の処理待ち時間を前記複数の情報処理装置の各々の入力について推定するので、最も早く処理が可能な情報処理装置を振り分け先に決定できる。そのため、複数の処理待ちバッファのいずれかの待ち行列に空きができて、情報処理装置の処理に無駄が生じるような状況の発生を避けることができる。
【００２９】
（８）予め用意された複数の情報処理装置と、予め構成が定められた単位情報の集合として順次に入力される入力データを、前記単位情報毎に区別して、前記複数の情報処理装置の中のいずれかの入力に順次に振り分ける負荷分散制御装置と、で構成される負荷分散処理システムであって、
前記複数の情報処理装置の各々の入力における前記単位情報の処理待ち時間を、前記単位情報の到着時刻と処理待ち行列の数とに基づいて推定し、前記複数の情報処理装置の中で、最も早く処理が可能な情報処理装置を振り分け先に決定する振り分け先決定部、を備える。
【００３０】
この負荷分散処理システムによれば、前記単位情報の処理待ち時間を前記複数の情報処理装置の各々の入力について推定するので、最も早く処理が可能な情報処理装置を振り分け先に決定できる。そのため、複数の処理待ちバッファのいずれかの待ち行列に空きができて、情報処理装置の処理に無駄が生じるような状況の発生を避けることができる。
【００３１】
（９）予め構成が定められた単位情報の集合として順次に入力される入力データを、前記単位情報毎に区別して、予め用意された複数の情報処理装置の中のいずれかの入力に順次に振り分ける負荷分散制御装置によって実行される負荷分散制御プログラムであって、
前記複数の情報処理装置の各々の入力における前記単位情報の処理待ち時間を、前記単位情報の到着時刻と処理待ち行列の数とに基づいて推定し、前記複数の情報処理装置の中で、最も早く処理が可能な情報処理装置を振り分け先に決定する振り分け先決定手順、を備える。
【００３２】
この負荷分散制御プログラムによれば、前記単位情報の処理待ち時間を前記複数の情報処理装置の各々の入力について推定するので、最も早く処理が可能な情報処理装置を振り分け先に決定できる。そのため、複数の処理待ちバッファのいずれかの待ち行列に空きができて、情報処理装置の処理に無駄が生じるような状況の発生を避けることができる。
【発明の効果】
【００３３】
本発明の負荷分散制御装置、負荷分散制御方法、負荷分散処理システムおよび負荷分散制御プログラムによれば、前記単位情報の処理待ち時間を前記複数の情報処理装置の各々の入力について推定するので、最も早く処理が可能な情報処理装置を振り分け先に決定できる。そのため、複数の処理待ちバッファのいずれかの待ち行列に空きができて、情報処理装置の処理に無駄が生じるような状況の発生を避けることができる。
【図面の簡単な説明】
【００３４】
【図１】図１（ａ）は汎用性の高い部品を用いて構成した情報処理システムの構成例を示すブロック図、図１（ｂ）は高機能部品を用いて構成した情報処理装置の構成例を示すブロック図である。
【図２】図２（ａ）は図１（ａ）に示した情報処理システムにおける複数の情報パケットの流れおよび位置の具体例を示す模式図、図２（ｂ）は図１（ｂ）に示した情報処理装置の内部における複数の情報パケットの流れおよび位置の具体例を示す模式図である。
【図３】図２（ａ）に示した構成における負荷分散装置の情報パケット振り分け動作を示す模式図である。
【図４】図１（ａ）に示した情報処理システムに本発明の制御を適用した場合における複数の情報パケットの振り分け、流れ、および位置の具体例を示す模式図である。
【図５】本発明を実施する情報処理システムの構成例を示すブロック図である。
【図６】本発明を実施する情報処理システムの構成例を示すブロック図である。
【図７】図５に示した情報処理システムの各部における処理の概要を示すブロック図である。
【図８】図６に示した情報処理システムの各部における処理の概要を示すブロック図である。
【図９】図１（ａ）に示した情報処理システムにおける複数の情報パケットの個数、流れおよび位置の具体例を示す模式図である。
【図１０】本発明を実施する情報処理システムにおいて負荷分散装置が各情報パケットを振り分けるために行われる処理の具体例を示すフローチャート（その１）である。
【図１１】本発明を実施する情報処理システムにおいて負荷分散装置が各情報パケットを振り分けるために行われる処理の具体例を示すフローチャート（その２）である。
【図１２】負荷分散装置が各情報パケットを振り分ける制御に負荷の変化を動的に反映するための処理の具体例を示すフローチャートである。
【図１３】負荷分散装置がＵＲＩに基づいて各情報パケットの振り分けを制御する場合のシステム構成例（１）を示すブロック図である。
【図１４】負荷分散装置がＵＲＩに基づいて各情報パケットの振り分けを制御する場合のシステム構成例（２）を示すブロック図である。
【図１５】図１（ａ）に示した情報処理システムに本発明の制御を適用した場合における複数の情報パケットの振り分け、流れ、および位置の具体例を示す模式図である。
【発明を実施するための形態】
【００３５】
本発明の実施形態について各図を参照しながら以下に説明する。
＜振り分け制御の概要＞
図１（ａ）に示した情報処理システム１０に本発明の制御を適用した場合における複数の情報パケットの振り分け、流れ、および位置の具体例を図４に示す。
【００３６】
図４に示した情報処理システムは、負荷分散装置１１を制御するために負荷分散装置制御サーバ２０を備えている。この負荷分散装置制御サーバ２０の制御機能により、入力情報１７として負荷分散装置１１に入力される情報パケット１８を負荷分散装置１１が複数の情報処理装置１４−１〜１４−ｓに振り分ける際に、以下に示すような特別な制御が実施される。これにより、図１（ｂ）に示した情報処理装置１００のように単一の高機能装置を採用したシステムと同等の性能を実現できる。
【００３７】
なお、ここでは情報処理システム１０がＩＰパケットのような情報パケット１８を処理する場合を想定して説明しているが、本発明における処理対象の情報はパケットに限らない。例えば、パケットの代わりに、事前に定めたデータフォーマットの規定に従い構成された単位情報の集合を扱うことも可能である。したがって、一般的な並列計算機における複数タスク処理や、複数スレッド又は複数プロセスを扱う処理に本発明を適用することも可能である。
【００３８】
図４に示した負荷分散装置制御サーバ２０は、情報処理装置１４−１〜１４−ｓに入力した情報パケット１８が、処理待ちバッファ１５で処理開始を待った後、情報処理部１６に最も早く到着するように、複数の情報処理装置１４−１〜１４−ｓの１つを振り分け先として選択するように振り分け制御する。
【００３９】
また、この振り分け制御においては、各情報処理装置１４−１〜１４−ｓの入力情報が情報処理部１６に入力するまでの待ち時間を、情報パケット１８が情報処理装置１４−１〜１４−ｓに入力される都度に計算し、待ち時間最小の条件で入力可能な１つの情報処理装置１４を決定する。
【００４０】
これにより、情報処理装置１４の処理が空き状態になった時の処理の無駄が無くなり、即時に情報が入力することになるため、図１（ｂ）に示した情報処理装置１００のように高機能部品を採用した場合と同等の性能が実現する。
【００４１】
また、負荷分散装置制御サーバ２０は、複数種別の情報パケット１８が入力情報１７として負荷分散装置１１に入力される場合には、種別毎の情報パケット１８に関する負荷情報に基づき、種別毎に情報処理装置１４−１〜１４−ｓを割り当てる。そして、負荷分散装置１１の振り分け制御１１ａにおいては、処理対象の情報パケット１８の種別から、該当する種別に割り当てられたグループの情報処理装置１４−１〜１４−ｓを認識し、このグループの中で上記に述べたように入力する情報処理装置１４を決定する。
【００４２】
これにより、単一の情報処理装置１４が複数種別の情報パケット１８が混在する状態で処理を実行する必要がなくなり、種別の切り替わりの影響を受けて処理の効率が低下することも無くなる。したがって、単一の情報処理装置１４が複数種別の情報パケット１８が混在する状態で処理を実行する場合と比べて、情報処理を高速化できる。また、種別毎の負荷情報が時間的に変化する場合には、負荷情報の変化に追随して、情報処理装置１４の割り当てを動的に変化させることで情報処理をさらに高速化する。
【００４３】
図４に示した例では、情報パケット１８Ａ、１８Ｂの種別が異なる場合を想定している。したがって、情報パケット１８Ａの振り分け先として負荷分散装置１１が選択可能な情報処理装置１４のグループと、情報パケット１８Ｂの振り分け先として負荷分散装置１１が選択可能な情報処理装置１４のグループとが異なる。そのため、図４に示すように、情報パケット１８Ａは上側の複数の処理待ちバッファ１５に振り分けられ、情報パケット１８Ｂは下側の複数の処理待ちバッファ１５に振り分けられる。
【００４４】
なお、図４に示した構成においては、負荷分散装置制御サーバ２０が独立した装置として存在する場合を想定しているが、負荷分散装置制御サーバ２０の機能を、負荷分散装置１１に内蔵することもできる。また、情報処理装置１４−１〜１４−ｓ、および負荷分散装置１１は、それぞれ情報処理サーバ、および負荷分散サーバとして構成することもできる。そして、計算機処理や、サーバ内処理の高速化のために本発明の適用が可能である。
【００４５】
つまり、単一の高性能なＣＰＵ等のリソースを用いる構成に対し、複数の高性能ではないＣＰＵ等のリソースを用いて情報処理を行う場合において、ＣＰＵ処理の待ち時間を最小にすることで処理の高速化を行う。また、複数種別の情報に対してＣＰＵ処理を行う場合には、複数のＣＰＵをそれぞれの情報に割り当てることで、各ＣＰＵが他の情報種別の影響を受けることが無くなるため、単一のＣＰＵ構成に対してＣＰＵ処理の待ち時間を最小にして処理を高速化できる。
【００４６】
＜システムの構成＞
＜構成例１＞
本発明を実施する情報処理システムの構成例を図５に示す。
図５に示した情報処理システム１０は、負荷分散装置１１、負荷分散装置制御サーバ２０、および複数台の情報処理装置１４−１〜１４−ｓを備えている。負荷分散装置１１に入力される入力情報１７は、例えばＩＰパケットの集合として順次に入力されるデータである。
【００４７】
図５に示した構成においては、負荷分散装置１１は入力情報識別部３１、振分部３２、および通信制御部３３を備えている。また、負荷分散装置制御サーバ２０はサービス種別識別部２１、情報処理装置割り当て計算部２２、および通信制御部２３を備えている。また、情報処理装置１４−１〜１４−ｓのそれぞれは、処理待ちバッファ１５、情報処理部１６、通信制御部４１、および情報処理部管理部４２を備えている。
【００４８】
負荷分散装置１１の入力情報識別部３１は、入力情報１７として入力される各情報パケット１８、具体的にはＩＰパケットの内容をそれぞれ識別するための処理を行う。振分部３２は、入力情報識別部３１の処理が終了した情報パケット１８を入力して、情報処理装置１４−１〜１４−ｓの中で最適な振り分け先に出力する。この振り分けを最適化するために必要な情報は、負荷分散装置制御サーバ２０から提供される。通信制御部３３は、負荷分散装置１１と負荷分散装置制御サーバ２０との間、および負荷分散装置１１と各情報処理装置１４−１〜１４−ｓとの間で情報を交換するための通信処理を行う。
【００４９】
負荷分散装置制御サーバ２０内のサービス種別識別部２１は、入力情報１７として負荷分散装置１１に到着し振り分けられる前の処理対象の情報パケット１８について、情報パケット１８の内容からそのサービス種別を識別する。
【００５０】
サービス種別の具体例としては、アプリケーション、送信情報、送信元又は送信先別の情報、通信プロトコル毎の情報などがある。また、アプリケーションの具体例としては、音声、データ、映像などがあり、送信情報の具体例としては、異なるＨＴＭＬファイルなどがある。このようなサービス種別は、例えばＩＰパケットの中に含まれているＩＰアドレス、ポート番号、プロトコル、ＵＲＩ（Universal Resource Identifier）の情報に基づいて特定できる。
【００５１】
負荷分散装置制御サーバ２０内の情報処理装置割り当て計算部２２は、情報パケット１８の種別毎に割り当てる情報処理装置１４の台数、および種別と各情報処理装置１４との関係を管理する。また、情報処理装置割り当て計算部２２は情報パケット１８の種別毎に割り当てる情報処理装置１４の台数などを負荷の変化に応じて動的に制御する。また、情報処理装置割り当て計算部２２は、負荷分散装置１１の振分部３２が情報パケット１８を情報処理装置１４−１〜１４−ｓのいずれかに振り分ける際の振り分けを最適化するために必要な情報を算出する。通信制御部２３は、負荷分散装置制御サーバ２０と負荷分散装置１１との間の通信を制御する。
【００５２】
各情報処理装置１４−１〜１４−ｓ内の処理待ちバッファ１５は、負荷分散装置１１から入力された情報パケット１８が情報処理部１６で処理可能な状態になるまで、待ち行列として順番に並べて一時的に保持するための記憶装置である。情報処理部１６は、処理対象の情報パケット１８を、１つずつ処理待ちバッファ１５の待ち行列から取り出して所定の情報処理を実行する。情報処理部管理部４２は、情報処理部１６の状態を管理する。通信制御部４１は、情報処理装置１４と負荷分散装置１１との間の通信制御を行う。
【００５３】
＜構成例２＞
本発明を実施する情報処理システムの構成例を図６に示す。
図６に示した情報処理システムは、負荷分散装置１１、および複数台の情報処理装置１４−１〜１４−ｓを備えている。負荷分散装置１１に入力される入力情報１７は、例えばＩＰパケットの集合として順次に入力されるデータである。
【００５４】
図６に示した構成においては、負荷分散装置１１は入力情報識別部３１、振分部３２、通信制御部３３、サービス種別識別部３４、および情報処理装置割当て計算部３５を備えている。つまり、図６に示した負荷分散装置１１には、図５に示した負荷分散装置制御サーバ２０に相当する機能が内蔵されている。情報処理装置１４−１〜１４−ｓのそれぞれは、図５に示した構成と同様に、処理待ちバッファ１５、情報処理部１６、通信制御部４１、および情報処理部管理部４２を備えている。
【００５５】
負荷分散装置１１内のサービス種別識別部３４は、入力情報１７として負荷分散装置１１に到着し振り分けられる前の処理対象の情報パケット１８について、情報パケット１８の内容からそのサービス種別を識別する。
【００５６】
情報処理装置割当て計算部３５は、情報パケット１８の種別毎に割り当てる情報処理装置１４の台数、および種別と各情報処理装置１４との関係を管理する。また、サービス時間計算部３５は情報パケット１８の種別毎に割り当てる情報処理装置１４の台数などを負荷の変化に応じて動的に制御する。また、サービス時間計算部３５は、振分部３２が情報パケット１８を情報処理装置１４−１〜１４−ｓのいずれかに振り分ける際の振り分けを最適化するために必要な情報を算出する。
【００５７】
負荷分散装置１１内の入力情報識別部３１、振分部３２、通信制御部３３、および情報処理装置１４−１〜１４−ｓのそれぞれの機能については、図５に示した構成と同様である。
【００５８】
＜処理の概要＞
＜処理例１＞
図５に示した情報処理システムの各部における処理の概要を図７に示す。
【００５９】
負荷分散装置１１は、入力情報１７として外部から入力される情報パケット１８をステップＳ５１で入力し、入力情報識別部３１がステップＳ５２で入力された情報パケット１８の識別情報を取得する。この識別情報の代表例としては、ＩＰアドレス、ポート番号、プロトコル、ＵＲＩなどが想定される。この識別情報は、通信制御部３３の実行するステップＳ５３の処理で負荷分散装置制御サーバ２０に送信される。
【００６０】
負荷分散装置制御サーバ２０の通信制御部２３は、負荷分散装置１１から送信された前記識別情報をステップＳ６１の処理で受信してサービス種別識別部２１に渡す。サービス種別識別部２１は、負荷分散装置１１から受け取った前記識別情報の内容に基づき、ステップＳ６２で振り分け処理対象の情報パケット１８のサービス種別を識別する。
【００６１】
情報処理装置割り当て計算部２２は、サービス種別識別部２１が識別したサービス種別に基づき、例えばサービスに依存する情報処理時間の標準値を指定するなどの処理を行い、サービスに依存する情報処理時間（サービス時間）を決定する。この情報処理時間は、情報処理部１６おいて例えばＩＰパケット処理等に要する所要時間の長さを表す。
【００６２】
または、情報処理時間を直接、情報の本体等に記載しておく。例えば、負荷分散装置制御サーバ２０が、ＩＰパケット種別毎の情報処理時間情報を予め保持するように構成する。又は負荷分散装置１１に到着するＩＰパケット等の情報の一部に、情報処理時間として識別可能な情報を予め保持することが想定される。これにより、サービス種別毎に情報処理時間を特定する処理が容易になる。
【００６３】
一方、各情報処理装置１４−１〜１４−ｓの情報処理部管理部４２は、処理待ちバッファ１５における情報パケット１８の待ち行列の情報や、情報処理部１６を通過する情報パケット１８の負荷の増減などの情報をステップＳ５４の処理で取得する。情報処理部管理部４２が取得した情報は、通信制御部４１のステップＳ５５の処理により負荷分散装置１１に送信され、更に負荷分散装置制御サーバ２０に送信される。
【００６４】
負荷分散装置制御サーバ２０の通信制御部２３は、ステップＳ６３の処理により、情報処理部管理部４２が取得した情報を情報処理装置割り当て計算部２２に渡す。情報処理装置割り当て計算部２２は、ステップＳ６２により取得したサービス種別の情報等と、ステップＳ６３の処理により受け取った情報処理装置１４の情報とに基づき、ステップＳ６４の処理により、各情報処理装置１４−１〜１４−ｓの中で、振り分け対象の情報パケット１８の情報処理開始時刻が最も早い１つの情報処理装置１４を計算により特定する。
【００６５】
具体的には、負荷分散装置１１から情報処理装置１４への情報パケット１８の出力時刻、又は、情報処理装置１４の処理待ちバッファ１５の到着時刻から負荷分散装置制御サーバ２０の情報処理装置割り当て計算部２２が、各情報処理装置１４−１〜１４−ｓの中で、情報処理開始時刻の最も早い情報処理装置１４を計算する。また、この計算においては、既に処理待ちバッファ１５に到着している情報パケット１８についても、情報処理時間と上記当該時刻が上述の方法で判明していることから、本情報を利用して、到着した情報パケット１８の処理待ちバッファ１５での待ち時間を計算する。
【００６６】
また、情報処理装置割り当て計算部２２が到着した情報パケット１８の処理待ちバッファ１５での待ち時間を計算する際に、振分部３２から情報処理装置１４に出力した時刻の情報を用いる場合には、負荷分散装置１１と情報処理装置１４との間の転送遅延を考慮して処理待ちバッファ１５における到着時刻を推定する。その場合は負荷分散装置制御サーバ２０と情報処理装置１４との間の通信が不要になるため、装置構成が簡易になる。また、複数種別の情報パケット１８に対して制御を行う場合には、情報処理装置１４毎に実施する上記処理を、情報パケット１８の種別毎にそれぞれ実施する。
【００６７】
情報処理装置割り当て計算部２２がステップＳ６４で決定した「情報処理開始の最も早い情報処理装置」の情報は、通信制御部２３がステップＳ６５の処理を行うことにより、負荷分散装置１１に通知される。負荷分散装置１１の通信制御部３３は、通知された情報をステップＳ６６の処理により振分部３２に通知する。
【００６８】
負荷分散装置１１の振分部３２は、入力情報１７として到着した振り分け対象の情報パケット１８を、負荷分散装置制御サーバ２０から通知された情報に従ってステップＳ６７で振り分け、情報処理装置１４へ出力する。
【００６９】
なお、図５に示した構成では、情報処理装置１４が取得した情報を負荷分散装置１１を経由して負荷分散装置制御サーバ２０に通知する場合を想定しているが、情報処理装置１４と負荷分散装置制御サーバ２０との間で直接通信を行うように変更することも考えられる。
【００７０】
また、各情報処理装置１４でのサービス種別毎の情報処理量変化、すなわち負荷の変動に対して、情報処理装置１４の割り当て方法を動的に変更する。例えば、同じ種別の情報パケット１８又は同じサービス種別の情報パケット１８の処理に割り当て可能な情報処理装置１４の装置台数を負荷が増大した場合には増やし、負荷が減少した場合には減らすように自動的に制御する。
【００７１】
例えば、負荷分散装置１１又は各情報処理装置１４において、通過する情報パケット１８の情報量に閾値を設け、閾値に対する増減の情報を、負荷分散装置制御サーバ２０の情報処理装置割り当て計算部２２に送信する。そして、情報処理装置割り当て計算部２２が情報処理装置割り当て方法を計算し、例えば該当するサービス種別の情報パケット１８の振り分け先として選択可能な情報処理装置１４の装置台数などを制御する。
【００７２】
なお、情報量を負荷分散装置１１の入力情報識別部３１で管理する場合には、上述の制御のための負荷分散装置１１と情報処理装置１４との間の通信が不要になるため、装置構成を簡単にできる。
【００７３】
なお、図７に示した処理において、負荷分散装置１１と各情報処理装置１４との間の通信は、上述のサービス種別毎の情報処理量の変化に対する負荷分散装置制御サーバ２０における情報処理装置１４の割り当て変更のための通信である。また、図７中のステップＳ５４において、情報処理部管理部４２が取得する情報は、各情報処理装置１４におけるサービス種別毎の情報処理量変化、つまり閾値に対する情報量の増減を表す情報である。
【００７４】
＜処理例２＞
図６に示した情報処理システムの各部における処理の概要を図８に示す。図８に示した負荷分散装置１１は負荷分散装置制御サーバ２０の機能を内蔵しているので、システム全体の機能については、図８に示した処理と図７に示した処理とで大きな違いは無い。
【００７５】
すなわち、図８に示した各処理ステップＳ７４、Ｓ７５、Ｓ７６、Ｓ７７、Ｓ７８、およびＳ７１の内容は、既に説明した図７中の各処理ステップＳ５１、Ｓ５２、Ｓ６２、Ｓ６４、Ｓ６７、およびＳ５４と同様である。したがって、これらの処理の説明は省略する。
【００７６】
＜特徴的な処理の内容の詳細＞
＜各情報パケット１８の状況の具体例＞
図１（ａ）に示した情報処理システム１０における複数の情報パケット１８の個数、流れおよび位置の具体例を図９に示す。
【００７７】
図９に示した例では、入力情報１７として負荷分散装置１１に到着した情報パケット１７ａを振り分け可能な情報処理装置１４としてｓ台の情報処理装置１４−１、１４−２、・・・、および１４−ｓが存在している場合を想定している。そして、情報処理装置１４−１〜１４−ｓの処理待ちバッファ１５−１〜１５−ｓ上には、それぞれ待ち行列（キュー）として順番に並んだ情報パケット１８−Ｑ１〜１８−Ｑｓが存在している。
【００７８】
また、情報処理装置１４−１〜１４−ｓの情報処理部１６−１〜１６−ｓには、それぞれ１つの処理の窓口１６ａ−１〜１６ａ−ｓが設けられている。また、各情報処理部１６−１〜１６−ｓは、それぞれの処理の窓口１６ａ−１〜１６ａ−ｓに取り込んだ１つの情報パケット１８−０１〜１８−０ｓを処理することができる。
【００７９】
例えば、ｋ番目の情報処理部１６−ｋにおいて情報パケット１８−０ｋの処理が完了して空き状態になると、次に処理する情報パケット１８を、ｋ番目の待ち行列１８−Ｑｋの先頭（図９中の右端側）からｋ番目の処理の窓口１６ａ−ｋに取り込み、情報処理部１６−ｋが該当する情報パケット１８−０の処理を開始する。
【００８０】
ｋ番目の待ち行列１８−Ｑｋから１個の情報パケット１８をｋ番目の処理の窓口１６ａ−ｋに移動することにより、ｋ番目の待ち行列１８−Ｑｋにおける情報パケット１８の個数は１つ減少する。また、例えば負荷分散装置１１に到着した情報パケット１７ａをｋ番目の処理待ちバッファ１５−ｋに入力してｋ番目の待ち行列１８−Ｑｋの最後尾（図９中の左端側）に追加すると、待ち行列１８−Ｑｋに情報パケット１８の個数は１つ増加する。
【００８１】
図９に示した例では、１番目〜ｓ番目の待ち行列１８−Ｑ１〜１８−Ｑｓに並んだ情報パケット１８の個数は、それぞれＸ１個、Ｘ２個、・・・、Ｘｓ個であり、これらは状況に応じて変化する。
【００８２】
情報処理部１６が情報パケット１８を処理するのに要する所要時間はサービス種別毎に異なる。したがって、例えば、サービス種別がそれぞれ異なる情報パケット１８が、情報処理部１６−１〜１６−ｓの処理の窓口１６ａ−１〜１６ａ−ｓに存在する場合には、処理の窓口１６ａ−１〜１６ａ−ｓのそれぞれに１つの情報パケット１８が滞在する時間の長さが変化する。
【００８３】
サービス種別に応じた情報処理部１６における情報パケット１８の１個あたりの処理の所要時間、すなわちサービス時間Ｔｂを表す情報については、例えば負荷分散装置１１の内部に記録しておくことができる。また、負荷分散装置１１は、現在時刻を管理することにより、入力情報１７として到着した情報パケット１７ａの到着時刻ｔａの情報を記録することができる。
【００８４】
したがって、各処理待ちバッファ１５−１〜１５−ｓの待ち行列１８−Ｑ１〜１８−Ｑｓの各情報パケット１８や、処理の窓口１６ａ−１〜１６ａ−ｓのそれぞれに存在する情報パケット１８−０１〜１８−０ｓについても、それぞれの到着時刻ｔａの情報、およびサービス時間Ｔｂの情報を管理することができる。
【００８５】
＜最も早く処理を開始できる情報処理装置１４の推定＞
本発明を実施する情報処理システム１０において負荷分散装置１１が各情報パケット１８を振り分けるために行われる処理の具体例を図１０に示す。図１０に示す処理は、負荷分散装置１１の内部又は負荷分散装置制御サーバ２０の内部で実行される。
【００８６】
入力情報１７として新たな情報パケット１７ａが負荷分散装置１１に到着すると、これを負荷分散装置１１が検出し、ステップＳ１１を実行する。すなわち、当該情報パケット１７ａの到着時刻ｔａ、およびサービス時間Ｔｂの情報を負荷分散装置１１が把握し内部に記録する。
【００８７】
また、負荷分散装置１１又は負荷分散装置制御サーバ２０は、サービス時間Ｔｂを次に示す手順で特定する。
【００８８】
（１）情報パケット１７ａに含まれているＩＰアドレス、ポート番号、プロトコル、ＵＲＩなどの情報に基づいて、サービスの種類を特定する。
（２）サービスの種類から事前に定めた時間の標準値を特定する。
（３）この標準値を使ってサービス時間Ｔｂの長さを決定する。
【００８９】
ステップＳ１２では、負荷分散装置１１又は負荷分散装置制御サーバ２０が振り分け対象の情報パケット１７ａのサービス種別を識別し、該当するサービス種別に割り当てられた情報処理装置１４のみを振り分け先として選択可能な窓口に定める。
【００９０】
例えば、図４に示した例のように、情報処理装置１４−１〜１４−ｓの中で、サービス種別Ａに対しては上から２つの情報処理装置１４−１および１４−２を割り当て、サービス種別Ｂに対しては下側３つの情報処理装置１４−３、１４−４、および１４−ｓを割り当てる。そして、サービス種別Ａに該当する情報パケット１８Ａは、２つの情報処理装置１４−１および１４−２のみを振り分け先として選択可能にし、サービス種別Ｂに該当する情報パケット１８Ｂは、３つの情報処理装置１４−３、１４−４、および１４−ｓのみを振り分け先として選択可能にする。
【００９１】
ステップＳ１３では、負荷分散装置１１又は負荷分散装置制御サーバ２０が、時間Ｔｗ１[ｘ][ｙ]、およびＴｗ２[ｙ]を算出する。
ここで、時間Ｔｗ１[ｘ][ｙ]は、ｙ番目窓口の待ち行列１８−Ｑｙの最後尾の情報パケット１８のサービス終了までの時間を含む。また、この時間Ｔｗ１を特定する１番目のインデックス変数[ｘ]は該当する待ち行列上の該当する情報の並び位置（最後尾＝Ｘｋ）を表し、「ｘ＝０」は処理の窓口１６ａでサービス中の情報パケット１８を表し、２番目のインデックス変数[ｙ]は窓口やバッファの番号を表す。また、時間Ｔｗ２[ｙ]は、ｙ番目窓口でサービス中の情報パケット１８のサービス終了までの時間を表す。
【００９２】
また、該当する窓口の待ち行列で待つ情報パケット１８の数を、変数Ｘｋで表すと、時間Ｔｗ１[Ｘｋ][y]は、式（１）により算出できる。
【数１】
2018037957.tif 000003
但し、Ｔｂ[ｎ][ｙ]：ｙ番目の待ち行列でｎ番目に待つ情報パケット１８の処理時間
【００９３】
また、時間Ｔｗ２[ｙ]は、式（２）により算出できる。
Ｔｗ２[ｙ]＝（ｔａ[０][ｙ]＋Ｔｗ１[０][ｙ]）−ｔａ０    ・・・（２）
但し、ｔａ[０][ｙ]：ｙ番目の窓口でサービス中の情報パケット１８の負荷分散装置１１の到着時刻
Ｔｗ１[０][ｙ]：ｙ番目の窓口でサービス中の情報パケット１８の到着からサービス終了までの時間
ｔａ０：現在時刻
また、算出した時間Ｔｗ１[Ｘｋ][ｙ]は、インデックス変数Ｘｋ，ｙで特定可能なメモリに保持する。
【００９４】
また、時間Ｔｗ３[ｙ]が最小となる窓口が複数存在する場合には、負荷分散装置１１又は負荷分散装置制御サーバ２０が、ラウンドロビンの方法によりｙの値が小さい窓口から順に窓口を割り当てるか、又は、ランダムに窓口を割り当てる。
なお、時間Ｔｗ３[ｙ]が最小となる窓口が複数存在する場合の窓口割当方法は、ラウンドロビンやランダムに限定されない。
ステップＳ１４では、負荷分散装置１１又は負荷分散装置制御サーバ２０が、ステップＳ１３で算出した時間Ｔｗ１[Ｘｋ][ｙ]、およびＴｗ２[ｙ]に基づき、ｙ番目の各窓口で、新たに到着した情報パケット１７ａがサービスを開始するまでの時間Ｔｗ３[ｙ]を算出する。そして、時間Ｔｗ３[ｙ]が最小になるｙ番目の窓口を、新たに到着した情報パケット１７ａの振り分け先として割り当てる。時間Ｔｗ３[ｙ]は、式（３）により算出できる。
Ｔｗ３[ｙ]＝Ｔｗ１[Ｘｋ][ｙ]＋Ｔｗ２[ｙ]    ・・・（３）
【００９５】
ステップＳ１５では、負荷分散装置１１又は負荷分散装置制御サーバ２０が、ステップＳ１４で割り当てたｙ番目の窓口について次の処理を行う。すなわち、今回振り分けた情報パケット１８の到着時刻ｔａのデータを、変数（Ｘｋ＋１）、ｙでインデックス可能な配列ｔａ[Ｘｋ＋１][ｙ]に保存する。また、今回振り分けた情報パケット１８のサービス時間Ｔｂのデータを、変数Ｘｋ＋１、ｙでインデックス可能な配列Ｔｂ[Ｘｋ＋１][ｙ]に保存する。更に、該当する窓口の待ち行列で待つ情報パケット１８が１つ増加したので、情報パケット１８の数を示す変数Ｘｋをインクリメントする。
ステップＳ１６において、時間Ｔｗ３の値が「０」になる窓口、すなわち現在サービスが行われていない窓口が選択される場合には、負荷分散装置１１又は負荷分散装置制御サーバ２０が、新たに待ち行列に入り、そのままサービスの窓口に入ることになる情報パケット１８に対するサービス時間、および到着時刻を、それぞれ、Ｔｂ[０][ｙ]、ｔａ[０][ｙ]で特定可能なメモリに保持する。
次のステップＳ１７では、ｙ番目に空き窓口が発生したか否かを負荷分散装置１１又は負荷分散装置制御サーバ２０が識別する。そして、負荷分散装置１１又は負荷分散装置制御サーバ２０は、ｙ番目に空き窓口が発生した場合（ステップＳ１７→Ｙｅｓ）、次のステップＳ１８に進む。負荷分散装置１１又は負荷分散装置制御サーバ２０は、ｙ番目に空き窓口が発生しない場合（ステップＳ１７→Ｎｏ）、ステップＳ１１の処理に戻り、次の情報パケット１７ａが入力情報１７として到着するのを待つ。
ステップＳ１８では、ｙ番目の待ち行列先頭の情報パケット１８が空いた窓口に入り、この情報パケット１８の時間Ｔｗ１[１][ｙ]が、時間Ｔｗ１[０][ｙ]として管理される。また、ｙ番目の待ち行列の時間Ｔｗ１[Ｘｋ][ｙ]、ｔａ[Ｘｋ][ｙ]について、それぞれ変数Ｘｋでインデックスされる配列要素が１つずつ繰り下げられて、変数（Ｘｋ−１）でインデックスされるようになる。更に負荷分散装置１１又は負荷分散装置制御サーバ２０は、ステップＳ１１の処理に戻り、次の情報パケット１７ａが入力情報１７として到着するのを待つ。
なお、図１０と図１１に示した振り分け処理においては、各情報パケットの処理待ち時間を推定するために、各情報パケットの到着時刻と、待ち行列の数とを用いているが、更に各情報パケットの種別の情報を加えて推定してもよい。すなわち、情報パケットの種別毎に処理負荷の大きさが大きく変動し実際の処理時間も変化するが、種別を考慮して情報パケット毎の処理時間を推定することにより正確な待ち時間の推定が可能になる。
【００９６】
＜負荷の変化に応じた振り分けの動的制御＞
負荷分散装置１１が各情報パケット１８を振り分ける制御に負荷の変化を動的に反映するための処理の具体例を図１２に示す。図１２に示した処理は、例えば負荷分散装置１１又は負荷分散装置制御サーバ２０が実行する。
【００９７】
ステップＳ２１では、負荷分散装置１１又は負荷分散装置制御サーバ２０が、通過パケットのサービス種別毎に、通過パケット量を検知し、予め定めた閾値と検知した通過パケット量とを比較することにより、通過パケット量の増減を識別する。
【００９８】
図１０と図１１に示した振り分け処理を実施する場合には、情報処理装置１４−１〜１４−ｓの各々は、予め割り当てられたサービス種別の情報パケット１８のみを処理することになる。したがって、例えば情報処理装置１４−１〜１４−ｓの各々を通過する情報パケット１８の量を検知することにより、サービス種別毎の通過パケット量、すなわち負荷の大きさを情報処理装置１４毎に検出できる。また、検知した通過パケット量を事前に定めた閾値と比較することにより、負荷が過大になっている状態や、処理能力に余裕のある状態を識別することができる。
【００９９】
各情報処理装置１４における通過パケット量が増えて閾値を上回り、負荷が過大な状態になると、負荷分散装置１１又は負荷分散装置制御サーバ２０の処理はステップＳ２２からＳ２３に進む。そして、該当する情報パケット１８のサービス種別に対して割り当てる情報処理装置１４の装置台数を増やすように負荷分散装置１１又は負荷分散装置制御サーバ２０が制御する。
【０１００】
また、各情報処理装置１４における通過パケット量が減少して閾値を下回り、処理能力に余裕のある状態になると、負荷分散装置１１又は負荷分散装置制御サーバ２０の処理はステップＳ２４からＳ２５に進む。そして、該当する情報パケット１８のサービス種別に対して割り当てる情報処理装置１４の装置台数を減らすように負荷分散装置１１又は負荷分散装置制御サーバ２０が制御する。
【０１０１】
全てのサービス種別について処理が完了していない場合は、ステップＳ２６からＳ２１に戻ってステップＳ２１〜Ｓ２５の処理を繰り返す。全てのサービス種別について処理が完了した場合は図１２の処理を終了する。また、図１２の処理は例えば定期的に繰り返し実行される。
【０１０２】
なお、図１２に示した処理においては、各サービス種別に割り当てる情報処理装置１４の装置台数のみを動的に変更する場合を想定しているが、装置台数以外を制御対象として変更してもよい。例えば、各サービス種別に割り当てる情報処理装置１４のタスク数、スレッド数、プロセス数などを変更してもよい。また、負荷の大きさを検出する方法については、各情報処理装置１４を通過するパケット量の増減に限らず、例えばＣＰＵ使用率のような各情報処理装置１４の性能情報を利用することも可能である。
【０１０３】
＜情報処理システム１０の利点＞
図１（ａ）に示した情報処理システム１０のように、並列分散処理を実施する構成を採用する場合であっても、図１０に示したような特徴的な振り分け処理を実施することにより、情報パケット１８の振り分けを最適化し、各情報処理装置１４における処理の無駄をなくすることができる。したがって、安価な汎用部品を用いて情報処理システムを構築し、性能を犠牲にすることなくコスト効果を高めることが出来る。
【０１０４】
＜本発明を適用可能な現実的な装置の具体例＞
本発明の負荷分散制御装置は、例えば、ＩＰパケットを転送するＩＰルータや、ＩＰパケットのペイロードの内容を読み取るＤＰＩ（Deep Packet Inspection）装置などへ適用することが考えられる。
【０１０５】
ＩＰルータや、ＤＰＩ装置などに本発明を適用する場合には、例えば図５に示した負荷分散装置制御サーバ２０は、次の表１、表２に示すような情報を各装置から取得することができる。
【表１】
2018037957.tif 000004
【０１０６】
【表２】
2018037957.tif 000005
【０１０７】
すなわち、表１に示すように、パケット識別情報Ｄ１として、ＩＰアドレスの情報Ｄ１ａ、ポート番号の情報Ｄ１ｂ、プロトコルの情報Ｄ１ｃ、ＵＲＩの情報Ｄ１ｄなどを負荷分散装置１１から取得できる。また、表２に示すように、負荷分散装置１１から取得する情報Ｄ２として、振分部３２の出力時刻の情報Ｄ２ａ、通過パケットの変動量又はトラヒックの変動量を表す情報Ｄ２ｂを利用できる。また、表２に示すように、ＩＰルータなどから取得する情報Ｄ３として、処理待ちバッファ１５の到着時刻を表す情報Ｄ３ａ、通過パケットの変動量又はトラヒックの変動量を表す情報Ｄ３ｂを利用できる。
【０１０８】
表１および表２に示した情報に基づいて、負荷分散装置制御サーバ２０は、図１０、図１１および図１２に示したような処理を実行し、ＩＰルータなどに入力するＩＰパケット振分の制御を行うことができる。
【０１０９】
また、計算機での並列データ処理や、アプリケーションサーバなどのサーバ処理において並列に処理タスクを配備する場合のタスクスケジューリングや負荷分散、更に、複数の処理窓口を有する業務処理システムにおける最適な窓口選択方法として本発明の適用が可能である。
【０１１０】
なお、図５に示した負荷分散装置制御サーバ２０の情報処理装置割り当て計算部２２が、複数の情報処理装置１４の中で情報処理開始時刻の最も早い情報処理装置１４を計算するための処理で必要とされる時刻の情報については、次の（１）〜（３）に示すものを利用できる。
【０１１１】
（１）負荷分散装置１１から情報処理装置１４への出力時刻の情報を利用する。
（２）情報処理装置１４の処理待ちバッファ１５に情報パケット１８が到着した時刻の情報を利用する。
（３）負荷分散装置制御サーバ２０が通信制御部２３を介して負荷分散装置１１から入力情報の識別情報を入力しサービス種別の情報を取得すると同時に、情報到着時刻も取得する。
【０１１２】
また、上記（３）の情報到着時刻を利用して、複数の情報処理装置１４の中で、情報処理開始時刻が最も早い１つの情報処理装置１４を計算により特定することもできる。この情報到着時刻を利用する場合には、負荷分散装置１１の出力時刻を求めるために、負荷分散装置１１の内部処理にかかる所要時間の推定値（転送遅延時間）を予め求め、この推定値を情報到着時刻に加算する。
【０１１３】
＜変形例の説明＞
＜変形例１＞
負荷分散装置１１がＵＲＩに基づいて各情報パケットの振り分けを制御する場合のシステム構成例（１）を図１３に示す。
【０１１４】
図１３に示した情報処理システム１０においては、負荷分散装置１１Ｂに内蔵された制御部１１Ｂａが振り分け対象の情報パケット１８に対応付けられたＵＲＩに応じて、最適化するように各情報パケット１８の振り分け先を決定する。
【０１１５】
すなわち、負荷分散装置１１Ｂの制御部１１Ｂａが、情報パケット１８のＵＲＩによりアプリケーションやサービス負荷に依存するネットワーク上のリソース情報を識別して、負荷を分散させるように各情報パケット１８を複数の情報処理装置１４−１、１４−２のいずれかに振り分ける。この場合、アプリケーション特性に基づいた装置負荷を考慮して振り分けるため、処理開始を早めることが可能である。
【０１１６】
＜変形例２＞
負荷分散装置がＵＲＩに基づいて各情報パケットの振り分けを制御する場合のシステム構成例（２）を図１４に示す。
【０１１７】
図１４に示した情報処理システム１０においても、負荷分散装置１１Ｃに内蔵された制御部１１Ｃａが振り分け対象の情報パケット１８に対応付けられたＵＲＩに応じて、最適化するように各情報パケット１８の振り分け先を決定する。また、ＵＲＩの他に、各情報処理装置１４−１〜１４−ｓの処理待ちバッファ１５における処理待ち時間を考慮して、振り分ける情報パケット１８の処理が最も早く開始されるように、情報パケット１８の振り分け先を制御部１１Ｃａが決定する。
【０１１８】
例えば、図１４に示したように、１番目のＵＲＩ、すなわちＵＲＩ１で特定されるアプリケーションの情報パケット１８を振り分け可能な情報処理装置１４のグループとして、上側２つの情報処理装置１４−１、１４−２を割り当てた場合に、該当する情報パケット１８が最も早く処理されるように、処理１１Ｃｂが情報処理装置１４−１、１４−２のいずれかを振り分け先として選択する。
【０１１９】
また、２番目のＵＲＩ、すなわちＵＲＩ２で特定されるアプリケーションの情報パケット１８を振り分け可能な情報処理装置１４のグループとして、下側の情報処理装置１４−３〜１４−ｓを割り当てた場合に、該当する情報パケット１８が最も早く処理されるように、処理１１Ｃｂが情報処理装置１４−３〜１４−ｓのいずれかを振り分け先として選択する。
【０１２０】
＜変形例３＞
図１（ａ）に示した情報処理システムに本発明の制御を適用した場合における複数の情報パケットの振り分け、流れ、および位置の具体例を図１５に示す。
【０１２１】
図１５に示した情報処理システムにおいて、負荷分散装置１１Ｄに備わっている制御部１１Ｄａは、振り分け対象となる情報パケット１８のサービス種別毎に、振り分け先の処理待ちバッファ１５−１〜１５−５の窓口を制御部１１Ｄａが予め固定している。
【０１２２】
図１５に示した例では、情報パケット１８Ａに対応するサービス種別に対しては、処理待ちバッファ１５−１〜１５−５のうち上側２つの処理待ちバッファ１５−１および１５−２を割り当ててあり、情報パケット１８Ｂに対応するサービス種別に対しては、処理待ちバッファ１５−１〜１５−５のうち下側３つの処理待ちバッファ１５−３〜１５−５を割り当ててある。つまり、２種類のサービス種別に対して２対３の比率で情報処理装置１４の台数を割り当ててある。
【０１２３】
また、負荷分散装置１１Ｄの処理１１Ｄｂにより、振り分け対象の各情報パケット１８は、サービス種別毎に、最も早く処理が開始される待ち行列に追加するように、振り分け先（送出先）の処理待ちバッファ１５を選択する。例えば、情報パケット１８Ａを処理する場合には、そのサービス種別に割り当てられた２つの処理待ちバッファ１５−１、１５−２の中で最も早く処理が開始されるように、いずれか一方が出力先として選択される。
【０１２４】
また、情報パケット１８Ｂを処理する場合には、そのサービス種別に割り当てられた３つの処理待ちバッファ１５−３〜１５−５の中で最も早く処理が開始されるように、いずれか１つが出力先として選択される。
【０１２５】
なお、本発明と類似する技術として、非特許文献２に示されたＷＦＱ（Weighted Fair Queuing）が知られているが、これは処理開始時刻が最も早くなるよう処理待ちバッファを選択するものではない。また、処理待ちバッファの割り当てを変化させることが可能な技術でもない。
【符号の説明】
【０１２６】
１０  情報処理システム
１１  負荷分散装置
１２  処理装置群
１３  情報出力部
１４  情報処理装置
１５  処理待ちバッファ
１６  情報処理部
１６ａ  処理の窓口
１７  入力情報
１８，１８Ａ，１８Ｂ  情報パケット
２０  負荷分散装置制御サーバ（負荷分散制御装置）
２１  サービス種別識別部
２２  情報処理装置割り当て計算部（振り分け先決定部）
２３  通信制御部
３１  入力情報識別部
３２  振分部
３３  通信制御部
３４  サービス種別識別部
３５  情報処理装置割当て計算部
４１  通信制御部
４２  情報処理部管理部
１００  情報処理装置
１０１  処理待ちバッファ
１０２  情報処理部
１０２ａ  処理の窓口
１０３，１０４  情報パケット
【図１】
2018037957.tif 000006
【図２】
2018037957.tif 000007
【図３】
2018037957.tif 000008
【図４】
2018037957.tif 000009
【図５】
2018037957.tif 000010
【図６】
2018037957.tif 000011
【図７】
2018037957.tif 000012
【図８】
2018037957.tif 000013
【図９】
2018037957.tif 000014
【図１０】
2018037957.tif 000015
【図１１】
2018037957.tif 000016
【図１２】
2018037957.tif 000017
【図１３】
2018037957.tif 000018
【図１４】
2018037957.tif 000019
【図１５】
2018037957.tif 000020