JPH08510071A - 待ち行列管理装置および方法 - Google Patents

Abstract

(57)【要約】 複数のクライアントをサービスするための待ち行列管理装置では、クライアントは種々異なるクライアントタイプを表し、制御待ち行列はクライアントを所定の順序で待ち行列に入れる。待ち行列管理プログラムは複数の処理待ち行列を、前記クライアントタイプの異なる１つに整合するためアロケートおよびリアロケートする。ここで複数の処理待ち行列の数はクライアントタイプの数より少ない。待ち行列管理プログラムは、制御待ち行列のクライアントの１つを連続的に、整合する処理待ち行列がある場合には、クライアントタイプに整合する処理待ち行列に配置し、整合する処理待ち行列はないが空の処理待ち行列がある場合には、空の処理待ち行列をアロケートまたはリアロケートする。サーバーは処理待ち行列をバッチで空にする。テレフォンシステム環境では、クライアントはメッセージであり、クライアントタイプは種々のデスティネーションに対するメッセージ内のコードである。待ち行列管理プログラムは複数の処理待ち行列の各々を制御待ち行列のデスティネーションの１つに提供し、制御待ち行列の先頭メッセージにアクセスし、整合する場合はメッセージのデスティネーションコードに整合する処理待ち行列にメッセージを配列し、整合する処理待ち行列はないが空の処理待ち行列はある場合は空の処理待ち行列を目的デスティネーションに提供する。

Description

【発明の詳細な説明】 待ち行列管理装置および方法 発明の背景技術 本発明は、種々のタイプのサービスを要求するクライアントの待ち行列を、必 要なサービスを提供するサーバーに割り当てるための方法および手段に関する。 別の面から見ると、本発明はさらに具体的には、記録された電話メッセージの待 ち行列を管理し、メッセージのバッチを意図するデスティネーションに伝送でき るようにする方法および手段に関する。 このような待ち行列管理装置はサービスをクライアントに割り当てる。このク ライアントは変化する処理要求をそれらのタイプに依存して有する。例えばＡ， Ｂ，Ｃ等のクライアントの各タイプごとに管理装置は例えばＡ，Ｂ，Ｃ等のクラ イアントにサービスすることのできるサーバーの等級を規定する。管理装置はそ の代わりに、ユニバーサルサーバーを提供することもできる。このユニバーサル サーバーは自身を種々異なるサーバーの等級、例えばＡ，Ｂ，Ｃ等にクライアン トのニーズとして伝送することができる。 単一待ち行列ストラテジーでは、すべてのクライアントが同じ待ち行列で到着 順に待機し、サービスを一人ずつ受ける。待ち行列の先頭のクライアントが今サ ービスを受けたクライアントと同じタイプ、例えばタイプＡであれば、タイプＡ のクライアントを処理しているサーバーが次のタイプＡのクライアントを直ちに 処理することができる。それ以外の場合は、管理装置はサーバーの等級を次のク ライアントに適切なように、例えばタイプＢに変化させるか、または最初のタイ プ、すなわちタイプＡの次のクライアントを待ち行列の中から検索しなければな らない。 存在する電話ボイスメールシステムの環境では、クライアントが記録メッセー ジのフォームを種々のデスティネーションに対して使用する。単一待ち行列スト ラテジーは次のように機能する。すべてのメッセージが同じ待ち行列にそれらの 到着順に待機し、サーバーは各メッセージを１つずつサービスし、伝送する。同 じデスティネーションに宛てたメッセージが順次連続すれば、管理装置はそれら をバッチとして伝送することができる。それ以外の場合、管理装置はデスティネ ーションを次のメッセージのデスティネーションに変更するか、または最初のメ ッセージと同じデスティネーションに宛てたメッセージを待ち行列で検索し、同 じデスティネーションへの複数のメッセージを相互にバッチとして伝送するため に抽出する。 このような単一待ち行列システムは明らかに非効率的である。このようなシス テムでは、種々のクライアントまたはメッセージの同時サービスに簡単に適応す ることはできない。 多重待ち行列ストラテジーは多重待ち行列を使用し、各待ち行列をクライアン トタイプおよび相応するサーバータイプと関連づける。同じタイプのクライアン トは同じ待ち行列で、それらの到着順に待機する。電話ボイスメールシステムの 環境における多重待ち行列スキーマにより、クライアントは種々のデスティネー ションに対して符号化された記録メッセージである。多重待ち行列のそれぞれは 固有のデスティネーションに対するメッセージを有する。同じデスティネーショ ンに対するメッセージは同じ待ち行列でそれらの到着順に待機する。このような 多重待ち行列構成はデスティネーションの最大数が等しい複数の待ち行列を必要 とする。しかしデスティネーションは非常に大きかったり、未知であったりする 。各メッセージは所定のデスティネーションの待ち行列を通過しなければならな い。 本発明の課題は、待ち行列管理装置を改善し、特にテレフォンシステムに対し てボイスメールを使用できるようにすることである。 本発明の別の課題は、上記の欠点を回避することである。 発明の要約 本発明では、種々のタイプのクライアントすべてを 制御待ち行列に所定の順序でアセンブルし、クライアント数よりも少ない数の処 理待ち行列の各々を空にし、クライアントタイプの各連続するクライアントを、 制御待ち行列から他のクライアントタイプのない処理待ち行列に周期的に伝送す る。これは、各処理待ち行列を１つのクライアントタイプに、処理待ち行列が空 になるまでアロケートし、各空になった処理待ち行列をこれに伝送される次のク ライアントのクライアントタイプにリアロケートする。 待ち行列管理プログラムは、各処理待ち行列に常に、プロセス待ち量行列を常 に含むクライアントの同じタイプを付け加えるから、待ち行列管理プログラムは 本質的に各処理待ち行列をクライアントのタイプにアロケートし、これを待ち行 列管理プログラムはまず処理待ち行列に配置する。このアロケーションはサーバ ーが処理待ち行列を空にするまで続けられる。次に待ち行列管理プログラムが新 たなクライアントタイプを空の処理待ち行列比おけば、待ち行列管理プログラム は処理待ち行列を前のクライアントタイプからデアロケートし、これをもっとも 最近のタイプにリアロケートする。このデアロケートとリアロケートにより、処 理待ち行列の数を、例えば５０に制限することができ、任意の数のクライアント タイプ、例えば１０００以上を取り扱うことができる。 本発明の別の側面では、すなわち電話環境の１つで は、クライアントが複数のデスティネーションへの伝送のために符号化されたボ イスメールメッセージを記録する。すべてのデスティネーションへのメッセージ すべては制御待ち行列に所定の順序で、例えばファストイン−ファストアウトベ ースで現れる。待ち行列管理プログラムはメッセージを制御待ち行列に１つずつ 処理待ち行列の数で分配する。この処理待ち行列の数は、各連続する第１のメッ セージを制御待ち行列に処理待ち行列に基づいて配置することによりデスティネ ーションの数より少ない。処理待ち行列のデスティネーションは最初のメッセー ジのデスティネーションに整合する。整合する処理待ち行列がなければ、待ち行 列管理プログラムはメッセージを制御待ち行列に、処理待ち行列からのメッセー ジの伝送が処理待ち行列を空にするまで保持する。待ち行列管理プログラムは次 に、伝送に対する処理待ち行列を新たなデスティネーションにだけリアロケート し、次のメッセージを空の処理待ち行列に配置する。 本発明は、制限された数の待ち行列を使用して、多数のクライアントタイプま たはデスティネーションの同時サービスを可能にする。仮想的にはクライアント タイプの数またはデスティネーションの数に制限はない。同じタイプのクライア ントまたは同じデスティネーションへのメッセージは同じ処理待ち行列で待機す る。クライアントまたはメッセージは同じ待ち行列で 待機する。通常は時間順に待機するが、別の順序も可能である。異なるクライア ントタイプまたは異なるメッセージデスティネーションの同時処理は簡単に得ら れる。本発明の装置はダイナミックに待ち行列を各クライアントタイプまたはデ スティネーションにアロケートし、それらを空になったときにデアロケートし、 新たなクライアントタイプまたはメッセージが新たなデスティネーションに到着 する。本発明は共通の属性を、所定のクライアントタイプまたはデスティネーシ ョンの処理に関連して、処理の軽減のため相応する待ち行列により割り当てる。 多重クライアントタイプまたは多重デスティネーション向けメッセージの処理 は、単一待ち行列スキーマよりさらに効率的であり、前に述べた多重待ち行列シ ステムと同等である。本発明は処理における柔軟性が大きい。 本発明の特徴は請求項に記載されており、この明細書の一部を形成する。本発 明の別の目的および利点は、添付図面を見れば当業者には明白である。 図面の簡単な説明 図１は、本発明の実施例の待ち行列管理装置のブロック回路図である。 図２は、図１に示した本発明の実施例の待ち行列管理装置の動作を説明するフ ローチャートである。 図３は、図１に示した本発明の実施例の待ち行列管 理装置の動作の別の方法を説明するフローチャートである。 図４は、図１の処理待ち行列でのサービスを開始するサーバーの動作を説明す るフローチャートである。 図５は、待ち行列で動作を導く図１のサーバーの動作を説明する別のフローチ ャートである。 図６は、本発明の実施例に組み込まれるテレフォンシステムのブロック回路図 である。 図７は、図６のテレフォンシステムの環境における本発明の待ち行列管理装置 のブロック回路図である。 図８は、図６と図７に示された本発明の実施例の待ち行列管理装置の動作ステ ップを説明するフローチャートである。 図９は、図６と図７に示された本発明の実施例の待ち行列管理装置の別の動作 ステップを説明するフローチャートである。 図１０は、図６と図７に示された本発明の実施例の待ち行列管理装置のさらに 別の動作ステップを説明するフローチャートである。 図１１は、図６と図７に示された本発明の実施例の待ち行列処理コントローラ の動作を説明するフローチャートである。 有利な実施例の説明 図１の待ち行列管理装置ＱＭＳのブロック回路図において、待ち行列管理プロ グラムは待ち行列プールを 管理する。すなわち、制御待ち行列ＱＣと複数の処理待ち行列ＱＰ１，ＱＰ２， ...ＱＰ（ｎ−１），ＱＰｎを管理する。制御待ち行列は、種々異なるクライア ントタイプＴＣ１〜ＴＣｔのクライアントＣＬ１〜ＣＬｍのシーケンスを含む。 この種々異なるクライアントタイプは異なる処理等級または処理タイプを要求す る。処理待ち行列ＱＰ１〜ＱＰｎの数ｎは、クライアントタイプＴＣ１〜ＴＣｔ の数ｔより小さい。処理待ち行列の数ｎは例えば５０であり、クライアントタイ プの数ｔは例えば１０００である。 制御待ち行列ＱＣはすべてのクライアントタイプＴＣ１〜ＴＣｔのすべてのク ライアントを受信し、これらを到着順に保持する。待ち行列管理プログラムＱＭ はクライアントを制御待ち行列から同じ順序で移動する。したがって、制御待ち 行列ＱＣはファストイン−ファストアウト（ＦＩＦＯ）待ち行列である。しかし これは単なる例であり、制御待ち行列はクライアントを別の所望の順序で配列す ることができる。 待ち行列管理プログラムＱＭは、制御待ち行列ＱＣの各先頭クライアントを処 理待ち行列ＱＰ１〜ＱＰｎにクライアントタイプに関連して配置する。待ち行列 管理プログラムはクライアントタイプとの関連づけを最初のクライアントのクラ イアントタイプに基づいて確定する。この最初のクライアントを待ち行列管理プ ログラムは空の処理待ち行列ＱＰ１〜ＱＰｎに配置す る。これは以下のようにして行われる。 始めはすべての処理待ち行列ＱＰ１〜ＱＰｎが空であり、制御待ち行列ＱＣの 最初のクライアントはタイプＴＣ１０のクライアントであると仮定する。この場 合、待ち行列管理プログラムはクライアントを処理待ち行列ＱＰ１に配置する。 このステップは、処理待ち行列ＱＰ１をクライアントタイプＴＣ１０にアロケー トまたは提供する。それにしたがって待ち行列管理プログラムはクライアントタ イプＴＣ１０だけを処理待ち行列ＱＰ１に、サーバーＳＥの１つが処理待ち行列 ＱＰ１を空にするまで配置する。制御待ち行列ＱＣの次の先頭クライアントがタ イプＴＣ１４３であれば、待ち行列管理プログラムＱＭはタイプＴＣ１４３のク ライアントを処理待ち行列ＱＰ２に配置し、したがって、処理待ち行列ＱＰ２を クライアントタイプＴＣ１４３に提供またはアロケートする。 制御待ち行列ＱＣの次の先頭クライアントがタイプＴＣ１０であれば、待ち行 列管理プログラムはクライアントを他のクライアントＴＣ１０と共に処理待ち行 列ＱＰ１に配置し、他の空き処理待ち行列には配置しない。その後、待ち行列管 理プログラムＱＭは、先頭クライアントをすでにクライアントタイプに対してア ロケートした処理待ち行列に配置し続ける。そしてこのような専用処理待ち行列 が存在しなければ、待ち行列管理プログラムは次の先頭クライアントを空の処理 待ち行列に配置する。空の処理待ち行列がクライアントタイプを受信するたびに 、待ち行列管理プログラムはその処理待ち行列をそのクライアントタイプに提供 する。 待ち行列管理プログラムがすべての処理待ち行列を提供するかアロケートし、 サービスを受ける次のクライアントが処理待ち行列の提供またはアロケートされ ていないタイプであれば、待ち行列管理プログラムは制御待ち行列ＱＣからのク ライアントの分配を停止し、サーバーＳＥが処理待ち行列ＱＰ１〜ＱＰｎの１つ を空にするのを待機する。サーバーＳＥは処理待ち行列ＱＰ１〜ＱＰｎを個別に 、クライアントを１つずつか、またはバッチでサービスする。このようなサービ スは例えば処理待ち行列を空にし、これにより待ち行列管理プログラムが処理待 ち行列をデアロケートし、これをクライアントの先頭に、制御待ち行列ＱＣの先 頭でリロケートする。 択一的実施例では、クライアントが最大サイズでバッチ処理される。待ち行列 管理プログラムがすべての処理待ち行列を提供するかまたはアロケートし、サー ビスすべき次のクライアントが処理待ち行列がまだ提供されていないかまたはア ロケートされていない場合、待ち行列管理プログラムは制御待ち行列を検査し、 後のクライアントを制御待ち行列に伝送する。この制御待ち行列は、伝送が処理 すべき外部バッチを引き起こ さない場合、処理待ち行列をその処理待ち行列にマッチングする。 待ち行列管理プログラムは、待ち行列情報を各処理待ち行列に対して関連づけ 、または保守する。この待ち行列情報は、瞬時のアロケートされたクライアント タイプを含み、他のフィールドも含むことができる。 本発明は、クライアントタイプの最大数ＴＣ１〜ＴＣｔが非常に大きくても、 この時点では通常制限されたクライアント数しか実際にはサービスを待機してい ないという認識に基づく。したがって、いくつのクライアントタイプがこのクラ イアントの部分集合において実際にサービスを待機しているかを評価することに より十分な待ち行列ＱＰ１〜ＱＰｎＷＱをアロケートし、これを保持することが できる。 待ち行列管理プログラムＱＭは恒久的にいずれかの処理待ち行列を固定のクラ イアントタイプに提供するのではない。そうではなく、処理待ち行列を同時に１ つのクライアントタイプに割り当てるのである。処理待ち行列ＱＰ１〜ＱＰｎは 、待ち行列管理プログラムがこれをクライアントタイプに割り当てるときに使用 される。その他の場合は、処理待ち行列は空であり使用可能である。処理待ち行 列は、クライアントがその処理待ち行列にいないときだけ割り当てまたは再割り 当てに使用することができる。 図２は、図１の待ち行列管理装置ＱＭＳの動作を説 明するフローチャートである。ステップ１００では、待ち行列管理プログラムが 待機を実行し、これにより１つ以上のソースによりクライアントを制御待ち行列 ＱＣに付加することができる。私たちの処理は待機で開始する。これは無効を意 味するが、本当ではない。処理は周期的であり、したがって初期待機の後は、待 機が終了部にあるかのように処理される。多くの場合、装置が始動するときクラ イアントはいない。したがって、処理が待機でスタートしなければ、何も処理せ ずに待機を失敗することになる。したがって待機でスタートすることは通常かな り有効である。他の実行では異なる場合もある。ステップ１０４で、待ち行列管 理プログラムは制御待ち行列がからかい中を検出する。空であれば、待ち行列管 理プログラムＱＭはステップ１００の待機に戻る。制御待ち行列ＱＣが空でなく 、クライアントを含んでいれば、待ち行列管理プログラムはステップ１０７へ進 み、最初のクライアントのクライアントタイプを読み出す。ステップ１１０で、 待ち行列管理プログラムは最初のクライアントのクライアントタイプが処理待ち 行列のいずれかのクライアントタイプと整合するか否か検出する。すなわち、待 ち行列管理プログラムは、それが有するデータから処理待ち行列のいずれかを、 ステップ１０７に発見されたクライアントタイプにすでにアロケートしているか 否かを検出する。ある意味で、待ち行列管理プログラム ＱＭは、処理待ち行列ＱＰ１〜ＱＰｎのいずれかがステップ１０７のタイプのク ライアントタイプをすでに有しているか否かを確定する。 ステップ１０７でのクライアントタイプが処理待ち行列ＱＰ１〜ＱＰｎの１つ に整合すれば、待ち行列管理プログラムＱＭはステップ１１４へ進み、先頭、ま たは最初のクライアントを制御待ち行列から移動し、これを同じクライアントタ イプにアロケートされた処理待ち行列ＱＰ１〜１Ｐｎに追加する。ステップ１０ ７での最初のクライアントのクライアントタイプがステップ１１０でのいずれの 処理待ち行列でのクライアントタイプに整合しなければ、待ち行列管理プログラ ムはステップ１１７へ進み、そこで使用可能な処理待ち行列が存在するか否かを 質問する。すなわち、処理待ち行列ＱＰ１〜ＱＰｎの１つが空であるか否かを質 問する。処理待ち行列ＱＰ１〜ＱＰｎの１つが使用可能、すなわち空であれば、 待ち行列管理プログラムはＱＭはステップ１２０で、使用可能な新たな処理待ち 行列をそのクライアントタイプに割り当て、ステップ１０７の最初のクライアン トを移動し、これを処理待ち行列に付加する。次にステップ１０４に戻り、制御 待ち行列ＱＣが空か否かを質問する。 処理待ち行列ＱＰ１〜ＱＰｎのいずれもが空きでなければ処理待ち行列は効率 的に混雑している。ステップ１２４で、待ち行列管理プログラムＱＭは、サーバ ーＳＥが少なくとも１つの処理待ち行列のクライアントをサービスしているか、 または反対に混雑しているか否か、またはすべての処理待ち行列がブロックして いるか否かを確定する。クライアントをサービスするための全ブロックが存在し ていなれば、すなわち少なくとも１つの処理待ち行列のサービスがうまく処理さ れていれば、待ち行列管理プログラムＱＭはステップ１００のクライアント待機 に戻り、処理全体の実行を中止する。これにより、処理待ち行列をサービスし、 空にするための時間が得られ、処理待ち行列を使用することができるようになる 。 サーバーが、処理待ち行列のいずれかでクライアントをうまく処理できなけれ ば、すなわち、ブロックされるか、またはすべての処理待ち行列のサービスが混 雑していれば、待ち行列管理プログラムＱＭは処理待ち行列ＱＰ１〜ＱＰｎのす べてを、待ち行列を空にし、含まれるクライアントをそれらのソースに戻すこと によって一掃する。この時点で、これらのクライアントはもはや処理の一部でな くなるが、ソースはクライアントを制御待ち行列に戻すことができる。他の動作 を混雑の原因となる問題を補正するために実行することができる。いったん待ち 行列管理プログラムが処理待ち行列ＱＰ１〜ＱＰｎを一掃すれば、管理プログラ ムはその処理待ち行列を先頭のクライアントのクライアントタイプに対してアロ ケートし、先頭のクライアン トを、処理待ち行列を空にするため制御待ち行列ＱＣに伝送することができる。 本発明の実施例によれば、待ち行列管理プログラムＱＭは、ステップ１２７で 処理待ち行列ＱＰ１〜ＱＰｎの１つまたは複数だけを一掃する。本発明の別の実 施例では、ステップ１２７で待ち行列管理プログラムはまた制御待ち行列を検査 し、混雑している処理待ち行列の１つにそのタイプがアロケートされたいずれか のクライアントに戻る。本発明の別の実施例によれば、ステップ１２７で、クラ イアントをそれらのソースにリターンする代わりに、待ち行列管理プログラムは クライアントを制御待ち行列に戻す。２つの条件がこの実施例に対し、適切に動 作するため満たされなければならない。第１は、制御待ち行列での（すなわち未 だ処理待ち行列にない）処理待ち行列に割り当てられたクライアントタイプに対 しするいずれのエントリも、制御待ち行列へ処理待ち行列から戻されたエントリ の後に終了しなければならない。これはそのタイプのクライアントに対して時間 順序を守るためである。第２は、無限ループを回避するため、恒久的問題がある 場合には、処理待ち行列から戻された各クライアントはこれに関連したリターン カウントを有しなければならない。最大リターンカウントが割り当てられ、クラ イアントに関連したリターンカウントが最大値に達したならば、クライアントは 制御待ち行列に戻されるので はなく、そのソースに戻される。 本発明の別の実施例が、図３のフローチャートに示された図２の変形から明ら かである。ここでは、ステップ１２４での答えが否定であり、処理待ち行列がす べて混雑していなければ、待ち行列管理プログラムはステップ１３０で待機を開 始する。この待機は、ステップ１００での待機と同等である。その後、待ち行列 管理プログラムは直接ステップ１１７へ戻る。図３での動作はステップ１００に 戻る図２のものより、制御待ち行列ＱＣが厳密にＦＩＦＯである場合により効率 的である。この場合、処理待ち行列ＱＰ１〜ＱＰｎのいずれかのクライアントタ イプに整合できなかったトップエントリを置換することができない。したがって 、処理は常にステップ１０４、１０７および１１０〜１１７に先行して行われる こととなる。図３の実施例では、待ち行列管理プログラムＱＭはステップ１１７ へ直接進む。本発明の別の実施例によれば、クライアントのソースは、そのクラ イアントの処理が失敗した場合、サーバーＳＥによって通報される。 本発明の別の実施例によれば、待ち行列管理プログラムＱＭは他の待ち行列順 序を制御待ち行列ＱＣまたはＱＰ１〜ＱＰｎに導入する。すなわち時間順序以外 の順序である。１つの実施例では、順序は優先度に基づきものである。他の実施 例では、優先度と時間の組み合わせである。いずれもスカラーフィールドも優先 度として使用できる。すなわち、待ち行列管理プログラムＱＭは上昇または下降 の順序をスカラーフィールドの値によって形成する。 一般的な場合、処理待ち行列ＱＰ１〜ＱＰｎは多数の異なる優先度を有する多 数のクライアントを所定の時間で含むことができる。同じ事が制御待ち行列ＱＣ でも言える。なぜなら、すべての処理待ち行列のすべてのクライアントは制御待 ち行列を最初に通過するからである。実施例によれば、待ち行列管理プログラム ＱＭはヒープまたはリンクリストを使用する。他の実施例では、ＦＩＦＯ待ち行 列が使用され、この待ち行列は補助変数を有していて、これが待ち行列での現在 の最優先値を告げる。この実施例は、セットアップタイムと処理での次のクライ アントを見つける効率との妥協をはかる。 サーバーＳＥは処理待ち行列ＱＰ１〜ＱＰｎを図４と図５のフローチャートに 示されたようにサービスする。 図４は、処理の開始を表し、図５は実際の処理を表す。処理の開始および処理 は別個に行われ、これによりサーバーＳＥは多重待ち行列を同時に処理すること ができる。ステップは、“処理スタート”チェックを含み、これにより多重プロ セスが同じ待ち行列生じないことが保証される。 待ち行列管理プログラムＱＭの動作タイミングとは 独立して、サーバーＳＥは処理待ち行列ＱＰ１〜ＱＰｎのチェックを所定のシー ケンスでステップ２００でまず待機することにより開始する。我々の処理は待機 でスタートする。処理は周期的である。したがって初期待機の後、処理は待機が 終了部にあるかのように実行される。多くの場合、装置がスタートするときクラ イアントはいない。したがって、処理が待機でスタートしないと、何の行わない うちに待機を失敗することとなる。したがって待機によりスタートすることは通 常かなり有効である。他の実行では異なることができる。ステップ２０４でサー バーＳＥは次の待ち行列を、処理に対して準備のできたクライアントに対しチェ ックする。そしてステップ２０７で、処理待ち行列がすでにクライアントを有す るか否か質問する。回答が否定であれば、サーバーＳＥステップ２１０に行き、 以前にその待ち行列にいてその待ち行列からデアロケートされたクライアントに 関連するすべての待ち行列情報をクリアまたは除去する。次にサーバーはステッ プ２１４で次の待ち行列のチェックを開始し、ステップ２００へ戻る。 ステップ２０７での回答が肯定であれば、問題の処理待ち行列がクライアント を含んでおり、サーバーはステップ２２０へ進み、処理待ち行列がすでにスター トしているか否か、またサービスを受けているか否かが検出される。肯定であれ ば、サーバーはステップ２ １４へ進み、次の待ち行列のチェックを開始する。回答が否定であれば、サーバ ーはステップ２２４へ進み、その待ち行列を処理対象にマークし、処理待ち行列 のクライアントのサービスを開始する。次にサーバーＳＥはステップ２２７で、 サービスがうまくスタートしたか否か検出する。否定であればサーバーＳＥはス テップ２００へ戻る。肯定であれば、サーバーはその待ち行列を処理中としてス テップ２３４でマークし、ステップ２００へ戻る前にステップ２１４へ進む。 開始後の処理ステップは図５に示されている。ここではステップ２６０での待 機の後、サーバーはステップ２６４で処理を実行する。ステップ２６７は処理が 成功したか否か質問する。肯定であれば、サーバーはクライアントを待ち行列か らステップ２７０で転送する。ステップ２７４では、サーバーは処理中の待ち行 列にそれ以上のクライアントがいるか否か検出する。いなければ、ステップ２８ ７へ進み、そこでサーバーはその待ち行列を処理なしとしてマークし、この待ち 行列での処理が終了する。まだクライアントがいる場合は、サーバーはステップ ２７７で、クライアントの最大数が処理されたか否か検出する。クライアントを バッチで取り扱うサーバーもある。このバッチは最大サイズであることも、そう でないこともある。サーバーがクライアントをバッチで処理し、サーバーがクラ イアントの最大数をバッチで取り扱う場合、サーバー は処理を次のパスまで中断する。ステップ２７７で回答が肯定であれば、サーバ ーは最大数を処理している。そうでなければ、サーバーはステップ２８０へ進み 、ステップ２６４へ戻る。ステップ２６７で回答が否定であれば、サーバーはス テップ２８４へ進み、エラー処理を行う。本発明の実施例によれば、エラー処理 は、待ち行列を“再試行”に対してマークすること、とリトライタイムを指定す ることも含む。待ち行列処理コントローラは、初期プロセス（図４）では、所定 のリトライタイムまで、再試行にマークされた待ち行列のチェックをスキップす る。 本発明の実施例によれば、サーバーはエラー処理を省略する。 図６のブロック回路図は、テレフォンシステム環境での本発明の実施例を表す 。ここでは、図２のクライアントＣＬ１〜ＣＬｍはボイスメールメッセージであ り、そのタイプはそれらのデスティネーションと共に変化する。図６のテレフォ ンシステムでは、電話ブランチ交換局ＢＥ１はユーザー位置Ｌ１にあり、複数の 電話Ｔ１，Ｔ２，...Ｔｋを公衆または私用電話網ＴＮと関連するボイスメール システムＶＭ１に接続する。電話網ＴＮはブランチ交換局ＢＥ１を複数の他のブ ランチ交換局ＢＥ２...ＢＥｑに接続する。すべての位置ＬＣ１〜ＬＣｈは場合 により位置Ｌ１から離れている。各ブランチ交換局ＢＥ２〜ＢＥｑは複数の電話 Ｔ Ｌを電話網ＴＮと、それぞれ関連するボイスメールシステムＶＭ２〜ＶＭｑに接 続する。各ボイスメールシステムＶＭ１〜ＶＭｑは公知の形式であり、電話Ｔ１ 〜ＴｋおよびＴＬのいずれからその関連するブランチ交換局ＢＥ１〜ＢＥｑに到 着したメッセージを記録する。 図６の位置ＬＣ１〜ＬＣｈは広く拡散することができる。ブランチ交換局ＢＥ １とボイスメールシステムＶＭ１の位置Ｌ１は例えば、サンタクララ、カリフォ ルニアであり、他の位置は例えばニューヨーク、ニューヨーク；ボストン、マサ チューセッツ；そしてノッティンガム、英国等とすることができる。 ボイスメールシステムＶＭ１は待ち行列管理装置ＱＭＴを有する。この管理装 置の詳細は図７のブロック回路図に示されている。ボイスメールシステムＶＭ１ は、ローカル位置Ｌ１の電話Ｔ１〜Ｔｋからの、またはリモート位置ＬＣ１〜Ｌ Ｃｈの電話ＴＬからのブランチ交換局ＢＥ１を介して到着したすべてのメッセー ジを受信および記憶する。これらは、電話Ｔ１〜Ｔｋによる検索のためのメッセ ージと、リモート電話ＴＬへ伝送するためのメッセージを含む。各メッセージは 、所定のデスティネーションまたは複数の所定のデスティネーションに対するデ スティネーションコードを有する。 典型的にはデスティネーションは他のボイスメール システム、例えばＶＭ２〜ＶＭｑのいずれか１つである。待ち行列管理装置ＱＭ Ｔは、これが複数のメッセージをボイスメールシステムのような単一のデスティ ネーションへバッチ伝送するために収集するときに、最高の効率で動作する。各 メッセージの符号は目的ボイスメールシステムの数と、目的ボイスメールシステ ム内の所定のデスティネーションのメールボックス番号とを含む。デスティネー ションの数は例えば１０００である。 ボイスメールシステムＶＭ１では、セレクタ（図示せず）がリモート電話ＴＬ への伝送のための記録メッセージをローカル電話Ｔ１〜Ｔｋに向けられた記録メ ッセージから分離する。リモート電話は、ボイスメールシステムＶＭ１のブラン チ交換局ＢＥ１の外にある位置ＬＣ１〜ＬＣｈにある。ボイスメールシステムＶ Ｍ１により各ローカル電話Ｔ１〜Ｔｋは、これらローカル電話に向けられたメッ セージにアクセスすることができる。図７の待ち行列管理装置ＱＭＴは、クライ アントとしてメッセージＭＥ１〜ＭＥｍだけを受信する。これらのメッセージは 、リモート電話ＴＬおよびブランチ交換局ＢＥ１の外の位置ＬＣ１〜ＬＣｈにお けるデスティネーションＤＥ１〜ＤＥｔへの伝送のために符号化されている。 図７は、待ち行列管理装置ＱＭＴの詳細を示す。後者は、図１のシステムＱＭ Ｓをテレフォンシステム、 特に図６のボイスメールシステムと関連して構成する。図７は図１と次の点を除 いて同じである。すなわち、クライアントＣＬ１〜ＣＬｍがメッセージＭＥ１〜 ＭＥｍの特別の形態をとり、タイプＴＣ１〜ＴＣｔがデスティネーションＤＥ１ 〜ＤＥｔの特別の形態をとり、サーバーＳＥが待ち行列処理コントローラＰＣの 特別の形態をとる点である。コントローラＰＣはリモートデスティネーションを ダイヤルし、メッセージを伝送する。図１からず７と同じ参照符号を用いる。 図７では、制御待ち行列ＱＣはすべてのデスティネーションＤＥ１〜ＤＥｔに 対するメッセージＭＥ１〜ＭＥｍを受信し、それらを到着順に保持する。待ち行 列管理プログラムＱＭは制御待ち行列ＱＣからのメッセージを同じ順序で転送す る。したがって、制御待ち行列ＱＣはファストイン・ファストアウト（ＦＩＦＯ ）待ち行列である。しかしこれは単なる例であり、制御待ち行列は所望の他の順 序でメッセージを配列することができる。 図７では、待ち行列管理プログラムＱＭは制御待ち行列ＱＣの各先頭メッセー ジを処理待ち行列ＱＰ１〜ＱＰｎに、デスティネーションの１つに関連して配置 する。待ち行列管理プログラムＱＭはデスティネーションとの関連を最初のメッ セージのデスティネーションに基づいて確定する。最初のメッセージは待ち行列 管理プログラムＱＭにより空の処理待ち行列に配置さ れる。これは以下のようにして行われる。 最初は処理待ち行列ＱＰ１〜ＱＰｎがすべて空であり、制御待ち行列ＱＣの最 初または先頭のメッセージがデスティネーションＤＥ１０を有すると仮定すれば 、待ち行列管理プログラムＱＭはメッセージを処理待ち行列ＱＰ１に配置する。 このステップは一時的に、処理待ち行列ＱＰ１をデスティネーションＤＥ１０に アロケートまたは提供する。その後、待ち行列管理プログラムＱＭはデスティネ ーションＤＥ１０を有するメッセージのみを処理待ち行列ＱＰ１に配置する。こ れは、待ち行列処理コントローラＰＣが処理待ち行列ＱＰ１を空にするまで行わ れる。制御待ち行列ＱＣの次の先頭メッセージがデスティネーションＤＥ１４３ を有していれば、待ち行列管理プログラムＱＭはデスティネーションＤＥ１４３ を有するメッセージのみを処理待ち行列ＱＰ２に配置し、したがって処理待ち行 列ＱＰ２をデスティネーションＤＥ１４３に提供またはアロケートする。 制御待ち行列ＱＣの次の先頭メッセージがデスティネーションＤＥ１０を有し ていれば、待ち行列管理プログラムは、そのメッセージを他のデスティネーショ ンＤＥ１０を有するメッセージの後に処理待ち行列ＱＰ１に配置し、空の処理待 ち行列の１つに配置することはしない。その後、待ち行列管理プログラムＱＭは 所定のデスティネーションを有する先頭メッセージを、 待ち行列管理プログラムＱＭがそのデスティネーションに対してアロケートした 処理待ち行列に配置し続ける。このような提供された処理待ち行列がなければ、 待ち行列管理プログラムは次の先頭クライアントを空の処理待ち行列に配置する 。空の処理待ち行列が所定のデスティネーションを有するメッセージを受信する たびに、待ち行列管理プログラムはその処理待ち行列をそのデスティネーション に提供する。 待ち行列処理コントローラＰＣは処理待ち行列を、待ち行列管理プログラムＱ Ｍによる動作に無関係にときどき巡回する。各処理待ち行列において、待ち行列 処理コントローラＰＣは提供された処理待ち行列のデスティネーション番号をダ イヤルする。コールが完了すると、待ち行列処理コントローラＰＣはメッセージ のバッチをその待ち行列プロセッサにブランチ交換局を介して伝送する。バッチ におけるメッセージの最大数はシステムがいつでも伝送できるメッセージの数に 依存している。これはまた、メッセージの伝送を管理するプロトコルに依存する 。 処理待ち行列のメッセージの数がバッチの最大数より小さければ、このような 動作は処理待ち行列を空にする。これにより、待ち行列管理プログラムＱＭは、 その処理待ち行列をデアロケートし、これを制御待ち行列ＱＣの先頭にあるメッ セージのでデスティネーションにリアロケートすることができる。しかし処理待 ち行列のメッセージ数がバッチの最大数を越えると、この手続きは待ち行列処理 コントローラＰＣの次のサイクルまで動作を中止する。コントローラは常に次の 待ち行列がうまくメッセージを送信しているか否かをチェックする。 待ち行列管理プログラムがすべての処理待ち行列を提供またはアロケートし、 制御待ち行列の次のメッセージが、処理待ち行列の提供またはアロケートされて いないデスティネーションに対するものであれば、待ち行列管理プログラムは制 御待ち行列ＱＣからのメッセージの分配を停止し、待ち行列処理コントローラＰ Ｃの動作を待機し、ブランチ交換局を空にし、メッセージを処理待ち行列ＱＰ１ 〜ＱＰｎの１つに伝送する。 待ち行列管理プログラムＱＭと処理コントローラＰＣは待ち行列情報を各処理 待ち行列に対して関連づけ、維持する。この待ち行列情報は、現在アロケートさ れているデスティネーションコードを含み、他のフィールド、例えば現在処理さ れている処理待ち行列が空か否か、再試行の数、再試行の処理待ち行列、次のリ トライタイム等のフィールドを含むことができる。 本発明は、デスティネーションＤＥ１〜ＤＥｔの最大数が１０００以上の非常 に大きな数であっても、同時に実際にサービスを待機してるメッセージの数は普 通制限された数であり、ソースの数も制限されている という認識に基づくものである。したがって、いくつのデスティネーションがこ のメッセージの部分集合において実際に伝送を待機しているか評価することによ って、十分な処理待ち行列ＱＰ１〜ＱＰｎ（例えば５０）をアロケートしこれを ホールドすることができる。 待ち行列管理プログラムは恒久的に、いずれかの処理待ち行列を固定のデステ ィネーションに提供することはせず、処理待ち行列を１つのデスティネーション にその処理待ち行列が空になるまで割り当てる。待ち行列管理プログラムは次に 、空の待ち行列をリアロケートする。処理待ち行列ＱＰ１〜ＱＰｎは、待ち行列 管理プログラムＱＭがこれをデスティネーションに割り当てたときに使用される 。それ以外は、処理待ち行列は空であり、使用可能である。処理待ち行列は、メ ッセージがその処理待ち行列にない場合だけ、割り当てまたは再割り当てに対し て使用することができる。 図８は、図６と図７の待ち行列管理装置ＱＭＴの動作を説明するフローチャー トである。動作は図２のそれと似ているが、電話およびボイスメール環境である 点が異なる。ステップ３００で、待ち行列管理プログラムＱＭは待機を実行し、 これによりメッセージを制御待ち行列ＱＣに付加することができる。私たちの処 理は待機でスタートする。これは非効率的に見えるが、実際は違う。処理は周期 的なものであり、したがって 初期待機の後、処理は待機が終了部にあるかのように行われる。多くの場合、装 置がスタートするときクライアントはいない。したがって、処理が待機でスター トしないと、何の動作もせずに待機に失敗することとなる。したがって待機での スタートは通常、かなり効率的である。他の実行は異なることができる。ステッ プ３０４で、待ち行列管理プログラムは制御待ち行列ＱＣが空であるか否か検査 する。空であれば、待ち行列管理プログラムＱＭはステップ３００に戻る。制御 待ち行列ＱＣが空でなく、メッセージを含んでいれば、待ち行列管理プログラム ＱＭはステップ３０７に進み、最初のメッセージのデスティネーションコードを 読み出す。ステップ３１０で、待ち行列管理プログラムは、最初のデスティネー ションコードが処理待ち行列ＱＰ１〜ＱＰｎのいずれかのデスティネーションコ ードと整合するか否か検出する。すなわち、待ち行列管理プログラムＱＭはデー タをチェックし、処理待ち行列に関して、処理待ち行列のいずれかをステップ３ ０７で発見されたデスティネーションにアロケートしたか否かを検出する。ある 意味では、待ち行列管理プログラムＱＭは、処理待ち行列ＱＰ１〜ＱＰｎのいず れかがすでに、ステップ３０７でのデスティネーションへのメッセージを含んで いるか否かを確定する。 ステップ３０７でのデスティネーションが処理待ち行列ＱＰ１〜ＱＰｎに整合 すれば、処理待ち管理プログラムＱＭはステップ３１４へ進み、先頭または最初 のメッセージを同じデスティネーションにアロケートされている処理待ち行列Ｑ Ｐ１〜ＱＰｎへ伝送する。ステップ３０７での最初のメッセージのデスティネー ションがステップ３１０での処理待ち行列のいずれのデスティネーションとも整 合しなければ、待ち行列管理プログラムはステップ３１７に進み、空の処理待ち 行列ＱＰ１〜ＱＰｎが存在しないか否か質問する。処理待ち行列ＱＰ１〜ＱＰｎ の１つが空であれば、処理待ち管理プログラムＱＭはステップ３２０で、空の新 たな処理待ち行列をそのメッセージのデスティネーションに割り当て、先頭のメ ッセージをステップ３０７でその処理待ち行列に伝送する。次にステップ３０４ に戻り、制御待ち行列ＱＣが空であるか否かを質問する。 整合の欠如または空処理待ち行列ＱＰ１〜ＱＰｎの欠如は処理待ち行列の混雑 を示唆する。ステップ３２４で、待ち行列管理プログラムは、待ち行列処理コン トローラＰＣの結果のチェックから、混雑しているか否か、すべての処理待ち行 列からのメッセージの転送がブロックされているか否かを確定する。転送が完全 にブロックされていなければ、すなわち少なくとも１つの処理待ち行列からの転 送がうまく行っていれば、 待ち行列管理プログラムＱＭはメッセージを制御待ち行列に残し、ステップ３０ ０で待機し、処理全体の実行を中止する。これにより処理待ち行列を空にする時 間が得られる。すべての処理待ち行列からのメッセージの転送がブロックされて いれば、待ち行列管理プログラムＱＭはステップ３２７に進む。待ち行列管理プ ログラムＱＭは１つまたはそれ以上の処理待ち行列ＱＰ１〜ＱＰｎを、待ち行列 を空にしメッセージをそのソースに戻すことによって一掃する。他の動作を混雑 の原因となる問題を補正するために実行することができる。 この一掃処理はメッセージをその送信者に戻す。いったん待ち行列管理プログ ラムが処理待ち行列ＱＰ１〜ＱＰｎを一掃すれば、これは制御待ち行列からの先 頭メッセージを空の処理待ち行列に伝送することができ、したがってその処理待 ち行列をそのメッセージのデスティネーションにアロケートする。本発明の別の 実施例によれば、待ち行列管理プログラムＱＭはすべての処理待ち行列ＱＰ１〜 ＱＰｎを一掃する。 図８では、待ち行列管理プログラムＱＭはまた別の待ち行列順序を制御待ち行 列ＱＣまたはＱＰ１〜ＱＰｎに導入することができる。すなわち、時間順序以外 の順序である。いずれのスカラーフィールドも優先度として使用することができ る。すなわち、待ち行列管理プログラムＱＭは上昇または下降順序を、そのスカ ラーフィールドの値により形成する。 一般的な場合、処理待ち行列ＱＰ１〜ＱＰｎは多数の異なる優先度を有する多 数のメッセージを所定の時間に同時に含むことができる。同じ事が制御待ち行列 ＱＣにも当てはまる。なぜなら、すべての処理待ち行列のすべてのメッセージは 制御待ち行列を最初に通過するからである。 待ち行列処理コントローラＰＣはブランチ交換器ＢＥ１に処理待ち行列ＱＰ１ 〜ＱＰｎからのメッセージをそれらに相応するデスティネーションに伝送するこ とを指示する。これは図９と図１０のフローチャートに示されている。図９と図 １０では、図４と図５のように、待ち行列処理コントローラＰＣがメッセージの 処理を２つの別個のタスクに分割する。これにより、多重待ち行列を同時に使用 することができる。図９は伝送の初期化を表し、図１０は図９のメッセージの伝 送を表す。 図９のステップは待ち行列管理プログラムＱＭの動作タイミングとは無関係で ある。ここでは、待ち行列処理コントローラＰＣは所定のシーケンスで処理待ち 行列ＱＰ１〜ＱＰｎのチェックを開始し、一方では同時に、待ち行列のチェック 間ではステップ４００に示されているように待機する。私たちの処理は待機でス タートする。これは非効率的に思えるが、実際はそうでない。処理は周期的であ り、したがって初期待機の 後は、処理は待機が終了部にあるかのように行われる。多くの場合、装置がスタ ートするときにクライアントはいない。したがって、処理が待機でスタートしな いと、何も動作しないうちに待機を失敗することとなる。したがって待機による スタートは通常、かなり効率的である。他の実行では異なることもできる。ステ ップ４０４では、待ち行列処理コントローラＰＣが伝送準備のできたメッセージ に対する次の待ち行列をチェックする。そしてステップ４０７で、処理待ち行列 がメッセージを有するか否か質問する。質問が否定であれば、待ち行列処理コン トローラＰＣはステップ４１０へ進み、この待ち行列における以前のメッセージ に関連する待ち行列情報をクリアまたは除去し、この待ち行列をデアロケートす る。待ち行列処理コントローラＰＣはステップ４１４で次の待ち行列のチェック を開始し、ステップ４００へ戻る。 ステップ４０７での回答が肯定であれば、問題の処理待ち行列にメッセージが ある。待ち行列処理コントローラＰＣはステップ４２０へ進み、ブランチ交換局 ＢＥ１がすでに処理待ち行列からのメッセージを伝送しているか否かを検出する 。伝送していれば、待ち行列処理コントローラＰＣはステップ４１４へ進み、次 の待ち行列のチェックを開始する。エラー処理のための再試行を行う実施例では 、ステップ４１４でリトライタイムに達していない再試行中の待ち行列をスキッ プすることができる。回答が否定であれば、待ち行列処理コントローラＰＣはス テップ４２４へ進み、待ち行列を伝送対象としてマークし、ブランチ交換局ＢＥ １にメッセージ転送のためのチャネルを要求することによって処理を開始する。 待ち行列処理コントローラＰＣはステップ４２７で、チャネルがうまく得られた か否かを検出する。チャネルが得られていなければ、待ち行列処理コントローラ ＰＣはステップ４００へ戻る。チャネルが得られれば、待ち行列処理コントロー ラＰＣは処理の対する待ち行列をステップ４３４でマークし、ステップ４１４、 そしてステップ４００へ戻る。 処理ステップは図１０に示されている。ここではステップ４６０での待機の後 、処理コントローラＰＣはステップ４６４で直接、ブランチ交換局ＢＥ１に処理 待ち行列のメッセージのデスティネーション番号をダイヤルさせ、処理待ち行列 の最初のメッセージを使用可能となっているチャネルを介して伝送する。私たち の処理は待機でスタートする。これは非効率的に思えるが、実際はそうでない。 処理は周期的であり、したがって初期待機の後は、処理は待機が終了部にあるか のように行われる。多くの場合、装置がスタートするときクライアントはいない 。そのため、処理が待機でスタートしなければ、何も動作しないで待機に失敗す ることとなる。したがって、待機によるスタートは通 常、かなり効率的である。他の実行では異なることもできる。ステップ４６７で 、処理コントローラＰＣは伝送がうまくいったか否かを質問する。うまくいって いれば、ステップ４７０で待ち行列処理コントローラＰＣはメッセージを待ち行 列から転送する。ステップ４７４で、処理コントローラＰＣは処理待ち行列にま だメッセージがあるかどうかチェックする。回答が肯定であれば、ステップ４７ ７で、待ち行列処理コントローラは、交換局ＢＥ１が各伝送に対するメッセージ の最大数を伝送したか否かを質問する。伝送していなければ、ステップ４８０で 、待ち行列処理コントローラＰＣは次のメッセージを獲得し、処理をステップ４ ６４で再スタートする。 ステップ４８４はオプションであり、省略することができる。ステップ４８４ は、ステップ４６７でブランチ交換局ＢＥ１がコールを完了しなかった場合、す なわち処理が失敗した場合に動作する。待ち行列処理コントローラＰＣは、待ち 行列に関連する待ち行列情報を状況を反映するために更新する。 ステップ４６７でのメッセージ転送が失敗した場合、本発明の別の複数の実施 例ではエラー処理がステップ４８４で実行される。１つの実施例では、待ち行列 処理コントローラはメッセージを待ち行列から除去し、これをソースに戻し、処 理待ち行列のサービスを処理コントローラの次のサイクルまでに終了する。別の 実 施例では、待ち行列処理コントローラはすべてのメッセージを待ち行列から除去 し、そのソースに戻す。 別の実施例では、待ち行列処理コントローラはメッセージを待ち行列に残すが 、再試行の時間をセットする。メッセージのこの待ち行列からの転送は再試行と みなされる。待ち行列処理コントローラＰＣは再試行数の追跡を続ける。待ち行 列管理プログラムは、その待ち行列が再試行であることをマークし、図８のステ ップ３２４で待ち行列混雑をチェックするとき、すべての待ち行列が再試行でな いことを確認するためモニタする。 メッセージが再試行を行った後でも通じなければ、待ち行列処理コントローラ ＰＣはそのメッセージ（場合によりそのデスティネーションに対する他のすべて ）をそのソースに戻す。 待ち行列を循環して処理をスタートさせると、待ち行列処理コントローラは再 試行に対してマークされた待ち行列を処理の時間までスキップする。 エラー処理をステップ４８４で完了すると、待ち行列処理コントローラＰＣは ステップ４８７へ進み、待ち行列を処理なしとしてマークし、この待ち行列に対 する処理を終了する。次に図９のステップにより次の待ち行列の処理の開始を待 機する。 ステップ４７４で待ち行列処理コントローラＰＣがその待ち行列にそれ以上メ ッセージがないことを検出 すると、またはステップ４７７で交換局ＢＥ１がメッセージの最大数を処理した ことを検出すると、コントローラＰＣはステップ４８７へ進む。 コールがうまく通じれば、待ち行列処理コントローラＰＣはメッセージの所定 の最大数のバッチを転送し、転送は終了する。バッチの所定数は、処理待ち行列 でのすべてのメッセージの転送を可能にする。しかし、待ち行列処理コントロー ラＰＣはその次のチェックサイクル中にさらに多くの処理待ち行列を転送するこ とができる。 図１１の処理は図９と図１０の処理の簡単化実施例である。この実施例では、 １つの待ち行列の処理は、他の待ち行列の処理が開始する前に終了しなければな らない。ここでも、図１１のステップは待ち行列管理プログラムＱＭの動作タイ ミングに無関係である。ここでは、待ち行列処理コントローラＰＣは処理待ち行 列ＱＰ１〜ＱＰｎのチェックを所定のシーケンスで開始する。一方では同時に、 待ち行列チェックの間は待機でステップ５００に示されている。私たちの処理は 待機でスタートする。これは非効率的に思えるかもしれないが、実際はそうでな い。処理は周期的なものであり、初期待機の後、処理は待機が終了部にあるよう に行われる。多くの場合、装置がスタートするときクライアントはいないから、 処理が待機でスタートしなければ、何の動作もせずに待機を失敗することとなる 。 したがって待機によるスタートは通常かなり効率的である。他の実行では異なる こともできる。ステップ５０４で、待ち行列処理コントローラＰＣは次の待ち行 列を伝送準備のできたメッセージに対してチェックし、ステップ５０７で処理待 ち行列がメッセージを有しているか否かを質問する。回答が否定であれば、待ち 行列処理コントローラＰＣはステップ５１０へ進み、この待ち行列の以前のメッ セージに関連する待ち行列譲歩をクリアまたは除去し、この待ち行列をデアロケ ートする。待ち行列処理コントローラＰＣは次にステップ５１４で次の待ち行列 のチェックを開始し、ステップ５００へ戻る。 ステップ５０７での回答が肯定であれば、処理待ち行列にメッセージがあり、 待ち行列処理コントローラＰＣはブランチ交換局ＢＥ１に、処理待ち行列のメッ セージのデスティネーション番号をダイヤルすることと、処理待ち行列の最初の メッセージを使用可能としたチャネルを介して伝送することを指示する。ステッ プ５６７では、処理コントローラＰＣが伝送がうまくいったか否かを質問する。 うまくいっていればステップ５７０で、待ち行列コントローラＰＣが処理待ち行 列にメッセージがあるか否かをチェックする。回答が肯定であれば、ステップ５ ７７で、待ち行列処理コントローラは交換局ＢＥ１がメッセージの最大数を書く 伝送に対して伝送したか否かを質問する。伝送してい なければ、ステップ５８０で、待ち行列処理コントローラＰＣは次のメッセージ を獲得し、処理をステップ５２０で再スタートする。 ステップ５７４で、待ち行列にメッセージがないことが検出されるか、または ステップ５７７で、交換局ＢＥ１がメッセージの最大数を処理したことが指示さ れれば、コントローラＰＣはステップ５１４へ進む。 ステップ５８４はオプションであり、省略することができる。ステップ５６７ で、ブランチ交換局ＢＥ１がコールを完了していなければ、すなわち、処理が失 敗していれば、ステップ５８４で待ち行列情報が状況を反映するために更新され る。ステップ５８４では、メッセージ転送の次の試みが再試行される。メッセー ジが再試行マーク後に通じなければ、待ち行列処理コントローラＰＣはそのメッ セージを戻し、場合により他のすべてもそのデスティネーションに戻す。 コールがうまく行けば、待ち行列コントローラＰＣは所定の最大数のメッセー ジのバッチを転送し、転送が終了する。バッチの所定数は処理待ち行列のすべて のメッセージの転送を許可しない。しかし、待ち行列処理コントローラＰＣはチ ェックの次のサイクル中に、より多くの処理待ち行列を転送することができる。 本発明は、たとえデスティネーションの最大数が例えば１０００のように非常 に大きくても効率的なサービスを行うことができるという利点を有する。本発明 は、任意の時点では通常制限された数のデスティネーションしか実際にサービス を受けるのを待機していないという認識に基づく。したがって、少数の処理待ち 行列ＱＰ１〜ＱＰｎ、例えば５０だけで多数のデスティネーションをサービスす ることができる。制御待ち行列は、処理待ち行列の数が不十分な場合はオーバー フロー待ち行列としてサービスする。 本発明の利点は、待ち行列管理プログラムが、処理待ち行列ＱＰ１〜ＱＰｎを 固定のデスティネーションに恒久的に提供せず、それらを一時的に所定のデステ ィネーションに提供することである。処理待ち行列ＱＰ１〜ＱＰｎの１つは１つ のデスティネーションに提供されたとき使用される。いったん空になれば、処理 待ち行列を他のデスティネーションのアロケートに使用することができる。また 待ち行列管理プログラムは、処理が行われている間にメッセージを処理待ち行列 に付加する。 本発明の別の形態では、処理コントローラＰＣが他の情報を受信し、これによ り処理待ち行列の作動をいつトリガするか決定する。例えば、転送時間と転送回 数がいつかを決定し、転送処理がメッセージをデスティネーションに送信するこ とを試みるべき場合、および他の再試行がペンディングの場合には、何回試行す べきかを決定する。 本発明の別の実施例では、制御待ち行列ＱＣは待ち 行列に対して時間順序以外の順序法を使用する。１つの例では、制御待ち行列Ｑ Ｃがメッセージを優先度ベースまたは優先度とファストイン・ファストアウト・ ベースの組み合わせに基づいて配置する。制御待ち行列ＱＣはスカラーフィール ドを優先度として使用することができ、メッセージをそのフィールドの上昇値ま たは下降値の順序で処理する。本発明のさらに別の実施例では、制御待ち行列Ｑ Ｃは、処理待ち行列ＱＰ１〜ＱＰｎの１つの多数の異なる優先度を所定の時間で 並べる。効率のためにはヒープまたはリンクリストがファストイン・ファストア ウト待ち行列を置換する。別のスキーマは、付加的変数を有するファストイン・ ファストアウト待ち行列を使用する。この付加変数は現在の待ち行列における最 優先度を指示する。これにより、セットアップタイムと処理すべき次のメッセー ジを発見するための効率との妥協が図られる。本発明の別の実施例によれば、制 御待ち行列管理プログラムＱＭは異なる処理待ち行列を同じタイプではあるがし かし優先度の異なるクライアントに対して使用する。 本発明の実施例によれば、待ち行列管理プログラムＱＭは処理待ち行列ＱＰ１ 〜ＱＰｎの混雑を次のようにして取り扱う。待ち行列管理プログラムＱＭは制御 待ち行列ＱＣからのメッセージの移動を、少なくとも処理待ち行列ＱＰ１〜ＱＰ ｎの１つが使用可能になるまで中止する。択一的に、待ち行列管理プログラムＱ Ｍは、次のような処理待ち行列ＱＰ１〜ＱＰｎを一掃する。すなわち、各処理待 ち行列に関連する処理問題を有する処理待ち行列を一掃する。管理プログラムは 処理待ち行列ＱＰ１〜ＱＰｎのいくつかを混雑中に使用可能であるとマークし、 処理全体を促進する。 混雑を取り扱う他の方法では、処理待ち行列ＱＰ１〜ＱＰｎ全体が処理問題を かかえるまで待機し、処理待ち行列ＱＰ１〜ＱＰｎ全部を一度に一掃する。これ により、処理待ち行列ＱＰ１〜ＱＰｎのすべてが使用可能になる。 テレフォンまたはボイスメッセージ環境では、本発明はメッセージを他のデス ティネーションに向けられたメッセージのない処理待ち行列だけに割り当てる。 したがって同じデスティネーションに対するメッセージが同じ処理待ち行列に行 く。これは、仮想的には無限の数のデスティネーションが存在しており、待ち行 列の数は制限されているもそうである。ソースはメッセージを制御待ち行列ＱＣ にまず送り出し、待ち行列管理プログラムＱＭはこれをさらなる処理のため処理 待ち行列の１つに移動する。これは、処理待ち行列ＱＰ１〜ＱＰｎの知識を待ち 行列管理プログラムＱＭと処理コントローラＰＣに対して孤立させる。メッセー ジを制御待ち行列に送信する外部処理は制御待ち行列ＱＣだけを知る。 本発明により、異なるデスティネーションを有する メッセージの同時処理が可能であり、同じメッセージデスティネーションを有す るこれらメッセージに対して時間順序を守る。本発明は、同じメッセージタイプ 、例えばデスティネーションのメッセージをホールドするために待ち行列をダイ ナミックに使用する。処理待ち行列ＱＰ１〜ＱＰｎの１つは、１つのデスティネ ーションに対するメッセージをある時にホールドし、別のデスティネーションに 対するメッセージを他の時にホールドすることができる。待ち行列管理プログラ ムＱＭは処理待ち行列が使用されているか、再試行条件にあるか、または空であ り使用可能であるかを知る。 本発明により、メッセージを時間に付加された優先度または時間の代わりの優 先度により配列することができる。本発明は、制限された数の待ち行列を使用し て多数のデスティネーションの同時サービスを可能にする。実際にはデスティネ ーションの数に制限はない。同じデスティネーションに対するメッセージは同じ 処理待ち行列で待機する。同じ処理待ち行列のメッセージは通常、選択的なアプ ローチが所望されない限り、時間順序である。異なるメッセージの同時処理は簡 単に利用できる。装置はダイナミックに処理待ち行列ＱＰ１〜ＱＰｎを各デステ ィネーションに割り当て、それらをこのようなデスティネーションからデアロケ ートする。本発明は、所定のメッセージの処理に関連する共通の属性を、処理の 簡単化のために相応する待ち 行列に関連づける。 同じデスティネーションに対する多重メッセージの処理は、単一待ち行列シス テムに対するよりもさらに効率的であり、前の多重待ち行列システムに対するの と同等である。本発明により処理に多種多様の柔軟性が得られる。 メッセージ転送が失敗した場合、本発明のいくつかの他の実施例ではエラー処 理が実行される。１つの実施例では、待ち行列処理コントローラまたは待ち行列 管理プログラムがメッセージを待ち行列から除去し、これをソースに戻し、処理 のサービスを処理コントローラの次のサイクルまでに終了する。別の実施例では 、待ち行列処理コントローラまたは待ち行列管理プログラムがすべてのメッセー ジを除去する。他の実施例では待ち行列処理コントローラまたは待ち行列管理プ ログラムはメッセージを待ち行列に残すが、再試行時間をセットする。サイクル が待ち行列を処理スタートのために循環すると、待ち行列処理コントローラはそ の待ち行列を処理の時間までスキップする。 本発明の実施例を詳細に説明したが、当業者には本発明の精神と観点から離れ ることなく本発明を別に実施することができる。例えば、待ち行列管理プログラ ムをボイスメールシステムに関連して説明したが、当業者であれば、上記の方法 および装置を他の形式のメッセージシステムに適切に適用することができる。例 えば本発明の実施例は、ストア・アンド・フォワード・メッセージシステムにも 、例えばファクシミリメッセージ（ＦＡＸ）、電子メールメッセージ（Ｅ−メー ル）、ビデオメッセージ、またそのすべての種類のマルチメディアメッセージに 適用することができる。

───────────────────────────────────────────────────── フロントページの続き (72)発明者 ペレルマン， ロベルト アメリカ合衆国 94087 カリフォルニア サニーヴェイル イーグル ドライヴ 1614 (72)発明者 バイピン， ペイテル アメリカ合衆国 95139 カリフォルニア サン ホセ プリンプトン コート 120 (72)発明者 イチノフスキー， ジャンヌ アメリカ合衆国 94301 カリフォルニア パロ アルト グリーンウッド アヴェ ニュー 1051 (72)発明者 ユアン， クリス アメリカ合衆国 945390 カリフォルニア フリモント ビーヴァー コート 823 【要約の続き】 整合する場合はメッセージのデスティネーションコード に整合する処理待ち行列にメッセージを配列し、整合す る処理待ち行列はないが空の処理待ち行列はある場合は 空の処理待ち行列を目的デスティネーションに提供す る。

Claims (1)

1. 【特許請求の範囲】 １． システム内の複数のクライアントに対する待ち行列管理装置であって、ク ライアントは複数のクライアントタイプを表し、待ち行列管理装置は、 行列に並ぶクライアントに対する制御待ち行列と、複数の処理待ち行列と、 待ち行列管理プログラムとを有し、 前記処理待ち行列の数はクライアント受信のためのクライアントタイプの数 より少なく、 各処理待ち行列は周期的にクライアントを空にされ、 前記待ち行列管理プログラムは、１つのクライアントタイプのクライアント を前記制御待ち行列から、他のクライアントタイプのクライアントのない処理待 ち行列に転送するためのものであり、 処理待ち行列は１つのクライアントタイプに、処理待ち行列が空になるまで アロケートされる ことを特徴とする待ち行列管理装置。 ２． 待ち行列管理プログラムはさらにクライアント保持手段を有し、 該保持手段は、あるクライアントタイプを有するクライアントを制御待ち行 列に、空の処理待ち行列がない場合、および前記のクライアントタイプを有する １つ以上のクライアントを含む処理待ち行列が ない場合に保持する 請求の範囲第１項記載の装置。 ３． 前記待ち行列管理プログラムは、 制御待ち行列のクライアントのクライアントタイプを検出するための手段と、 前記のクライアントタイプを備えたクライアントを有する処理待ち行列があ るか否かを検出する手段と、 クライアントを整合する処理待ち行列に転送する手段、すなわち前記クライ アントタイプを備えたクライアントを含む処理待ち行列に転送する手段と を有する請求の範囲第１項記載の装置。 ４． 前記待ち行列管理プログラムはさらに、 整合する処理待ち行列がない場合に、空の処理待ち行列を探すための手段と 、 空の処理待ち行列がある場合に、クライアントを空の処理待ち行列に転送す るための手段と を有する請求の範囲第３項記載の装置。 ５． 前記待ち行列管理プログラムはさらに、 空の処理待ち行列がないときに、処理待ち行列のいずれかが空か否かを確定 するための手段と、 処理待ち行列が空でない場合に、少なくとも１つの処理待ち行列を空にし、 クライアントを制御待ち行列から空の処理待ち行列の１つに転送するための手段 と を有する請求の範囲第４項記載の装置。 ６． 前記処理待ち行列はさらに、 すべての処理待ち行列がアロケートされ、処理待ち行列が空である場合に、 クライアントを制御待ち行列から除去するための処理を中断するための手段を有 する 請求の範囲第５項記載の装置。 ７． さらに、前記処理待ち行列の各々において交互にバッチとしてクライアン トを処理するための処理手段と、 バッチで許容されたクライアントの最大数を検出するための手段と、 最大数に達した時を検出するための手段 とを有する請求の範囲第１項記載の装置。 ８． 前記処理手段は、 クライアントに対する処理待ち行列をチェックするための手段と、 チェックされた処理待ち行列にクライアントがいない場合に、クライアント に対して次の処理待ち行列をチェックするための手段と、 チェックされた処理待ち行列が処理されているか否かを検査する手段と、 処理待ち行列が処理されていなければ、処理をスタートさせるための手段と をさらに有する請求の範囲第７項記載の装置。 ９． 管理装置で複数のクライアントをサービスするための待ち行列管理方法で あって、 クライアントは複数のクライアントタイプを表し、 待ち行列管理方法は、 クライアントを制御待ち行列に転送するステップと、 複数の処理待ち行列の各々を周期的に空にするステップと、 ここで処理待ち行列の数はクライアントタイプの数よりも少なく、 所定のクライアントタイプのクライアントを前記制御待ち行列から、他のク ライアントタイプのない処理待ち行列に転送するステップとからなり、 ここで前記処理待ち行列は、処理待ち行列が空になるまで１つのクライアン トタイプにアロケートされる ことを特徴とする待ち行列管理方法。 10． さらに、空の処理待ち行列がない場合、および前記クライアントタイプを 有する１つ以上のクライアントを備えた処理待ち行列がない場合、制御待ち行列 の所定のクライアントタイプを有するクライアントを保持するステップを有する 請求の範囲第９項記載の方法。 11． 前記転送ステップは、 制御待ち行列のクライアントのクライアントタイ プを検出するステップと、 クライアントを、整合する処理待ち行列、すなわち前記クライアントタイプ を有するクライアントを含む処理待ち行列に転送するステップと を含む請求の範囲第９項記載の方法。 12． 前記転送ステップはさらに、 整合する処理待ち行列がない場合に、空の処理待ち行列を探すステップと、 空の処理待ち行列がある場合、クライアントを空の処理待ち行列に転送する ステップと を含む請求の範囲第１１項記載の方法。 13． 前記転送ステップはさらに、 空の処理待ち行列がないときに、処理待ち行列のいずれかが空になるか否か を確定するステップと、 空になる処理待ち行列がない場合に、処理待ち行列の少なくとも１つを空に し、クライアントを制御待ち行列から空の処理待ち行列の１つに転送するステッ プと を含む請求の範囲第１２項記載の方法。 14． 前記転送ステップはさらに、 すべての処理待ち行列がアロケートされ、処理待ち行列が空になる場合に、 制御待ち行列からのクライアントの転送処理を中断するステップ を含む請求の範囲第１３項記載の方法。 15． 前記処理待ち行列の各々のクライアントを交互 にバッチで処理するステップと、 バッチの許容されたクライアントの最大数を検出するステップと、 いつ最大数に達したかを検出するステップと を有する請求の範囲第１６項記載の方法。 16． 前記処理ステップは、 クライアントに対して処理待ち行列をチェックするステップと、 チェックされた緒リマ知行列にクライアントがいない場合、クライアントに 対して次の処理待ち行列をチェックするステップと、 チェックされた処理待ち行列に対し、それらが処理されているか否かを検査 するステップと、 処理待ち行列が処理されていなければ処理をスタートするステップとを 有する請求の範囲第１５項記載の方法。 17． デスティネーションコードを有するメッセージを、複数の目的デスティネ ーションの１つに転送するため受信する手段と、 メッセージの順番を待ちための制御待ち行列と、 複数の処理待ち行列と、 ただし当該処理待ち行列の数は目的デスティネーションの数よりも少なく、 デスティネーションコードに対するメッセージを前記制御待ち行列から、他 のデスティネーションコ ードへのメッセージのない処理待ち行列に転送するための待ち行列管理プログラ ムと を有し、 これにより処理待ち行列は、処理待ち行列が空になるまで１つのデスティネ ーションコードにアロケートされる ことを特徴とするストア・アンド・フォワード・メッセージシステム。 18． 前記待ち行列管理プログラムはさらに、 空の処理待ち行列がない場合、およびデスティネーションを有する１つ以上 のクライアントを備えた処理待ち行列がない場合に、デスティネーションコード を有するメッセージを制御待ち行列に保持するための手段を有する 請求の範囲第１７項記載のシステム。 19． 前記待ち行列管理プログラムはさらに、 制御待ち行列のメッセージのデスティネーションコードを検出するための手 段と、 デスティネーションコードを備えたメッセージを有する処理待ち行列がある か否かを検出するための手段と、 メッセージを、整合する待ち行列、すなわち前記デスティネーションコード を有するメッセージを含む処理待ち行列に転送するための手段とを有する 請求の範囲第１７項記載のシステム。 20． 前記待ち行列管理プログラムはさらに、 整合する処理待ち行列がない場合に空の処理待ち行列を探すための手段と、 空の処理待ち行列がある場合、空の処理待ち行列にメッセージを転送するた めの手段とを有する 請求の範囲第１９項記載のシステム。 21． 前記待ち行列管理プログラムはさらに、 空の処理待ち行列がないときに、処理待ち行列のいずれかが空になるか否か を確定するための手段と、 空になる処理待ち行列がない場合、処理待ち行列の少なくとも１つを空にし 、メッセージを制御待ち行列から空の処理待ち行列の１つに転送するための手段 を有する 請求の範囲第２０項記載のシステム。 22． 前記待ち行列管理プログラムはさらに、 処理待ち行列のすべてアロケートされ、処理待ち行列が空になる場合、制御 待ち行列からのメッセージの除去処理を中止する手段を有する 請求の範囲第２１項記載のシステム。 23． 前記処理待ち行列の各々におけるメッセージを交互にバッチで処理するた めの処理手段と、 バッチで許容されたメッセージの最大数を検出するための手段と、 いつ最大数に達したかを検出するための手段とをさらに有する請求の範囲第 １７項記載のシステム。 24． 前記処理手段手段は、 メッセージ対して処理待ち行列をチェックする手段と、 チェックされた処理待ち行列にメッセージがない場合、メッセージに対して 次の処理待ち行列をチェックするための手段と、 チェックされた処理待ち行列を、処理されているか否か検査するための手段 と、 当該処理待ち行列が処理されていなければ、処理をスタートさせるための手 段とを有する 請求の範囲第２３項記載のシステム。 25． 複数の所定目的デスティネーションの１つに対するデスティネーションコ ードを有するメッセージの転送のための行列待ち方法であって、 当該方法は、 メッセージを制御待ち行列に転送するステップと、 複数の処理待ち行列の各々を周期的に空にするステップと、 ここで前記処理待ち行列の数はデスティネーションの数より少なく、 デスティネーションに対するメッセージを前記制御待ち行列から、他のデス ティネーションのない処理待ち行列に転送するステップとからなり、 処理待ち行列は、当該処理待ち行列が空になるまで１つのデスティネーショ ンにアロケートされる ことを特徴とする方法。 26． 空の処理待ち行列がなく、デスティネーションを有する１つ以上のメッセ ージを備えた処理待ち行列がない場合、デスティネーションを有するメッセージ を制御待ち行列に保持するステップをさらに含む 請求の範囲第２５項記載の方法。 27． 処理待ち行列の少なくとも１つを空にするための手段と、 クライアントを空の処理待ち行列から制御待ち行列に戻すための手段とを有 する 請求の範囲第５項記載の装置。 28． 空の処理待ち行列がない場合に、処理待ち行列のいずれかが空になるか否 かを確定するための手段と、 空になる処理待ち行列がない場合、処理待ち行列の少なくとも１つを空にし 、クライアントのクライアントタイプを有するクライアントを空の処理待ち行列 に制御待ち行列から転送するための手段とを有する 請求の範囲第４項記載の装置。