[THESIS06] Takayuki Osogami, Analysis of multiserver systems via dimensionality reduction of Markov chains, Ph.D. thesis, School of Computer Science, Carnegie Mellon University, June 2005.

Task assignment with cycle stealing

例として、スーパーマーケットで買い物を終えたお客様にどのレジに並んでも らうと良いかを考えてみましょう。簡単のためにレジは2つだけあり、 誰も並 んでいなければどちらのレジで精算しても同じだけの時間がかかるとします。目標 は平均の待ち時間ができるだけ短くなるような並び方のルールを考えることで す。どのようなルールが良いと思いますか？

まず思いつくルールは「並んでいる人の少ないレジに並んでもらう」ではない でしょうか？このルールをShortest Queueと呼ぶことにします。一見すると Shortest Queueは非常にうまいルールのような気がします。実際にレジでの精 算にかかる時間がどの人もまったく同じであれば、Shortest Queueはほぼ最適 なルールであることが示せます。ところが実際にはたくさん買い物をした人も いれば、少ししか買っていない人もいて、精算にかかる時間は違ってきます。 同じ3人が並んでいても、1週間分の買い物をした3人が並んでいるレジと、 牛乳だけを買った人が3人並んでいるレジでは、待ち時間が大きく異なってきます。

そこで思いつくルールは「並ぶ時間が短い方のレジに並んでもらう」ではない でしょうか？このルールをLeast Remaining Workと呼ぶことにします。現実の スーパーマーケットでは並ぶ時間を正確に知ることは難しいので、Least Remaining Workに厳密に従うことはできないかもしれません。しかし、もし待ち 時間を厳密に知ることができたとしたら、Least Remaining Workに従うべ きでしょうか？一人一人のお客様の視点から見るとLeast Remaining Workにし たがって並ぶのが最適なように思われます。確かにLeast Remaining Workに従 わなかったお客様は、Least Remaining Workに従った場合に比べて長く待たな ければなりません。ところが、全てのお客様の待ち時間の平均を考えた場合に はLeast Remaining Workは最適なルールではありません。それどころか、 Least Remaining Workにおける平均の待ち時間が最適なルールに比べて無限に 長くなることがありえるのです。

Least Remaining Workの最大の問題点は、1週間分の買い物をした2人のお客様 が2つのレジを長い時間占有してしまい、そのあとに牛乳だけを買いたい大多 数のお客様がたくさん並んでしまう様な状況になりえることです。日本のスー パーマーケットでは一度に大量に購入する人はそれほどいないかもしれません が、アメリカのスーパーマーケットでは巨大なカートに山ほど買い物をする人 をよく見かけます。全てのレジで山ほど買い物をしたお客様の精算をしている と、その後には長い行列ができてしまいます。牛乳を一本だけ買いたくても何 十分と並ぶ必要がでてきます。

Least Remaining Workの問題点を解決するルールのひとつに、「たく さん買うお客様に一方のレジに並んでもらい、あまり買わないお客様 に他方のレジに並んでもらう」というのが考えられます。このルールを Dedicatedと呼ぶことにします。例えば、買う商品の数が20個以上のお客様に は一方のレジに並んでもらい、20個未満のお客様には他方のレジに並んでもら うようにします。Dedicatedにおいては、20個以上買う少数のお客様のあとに 20個未満しか買わない大多数のお客様が長い列を成して待つような状況がなく なります。実際に、精算にかかる時間のばらつきが大きいときには、 Dedicated に従ったときの平均の待ち時間はLeast Remaining Workに従ったと きの平均の待ち時間に比べてはるかに短くなることが示せます。 ところがDedicatedも最適なルールではありません。Dedicatedの問題点は、 20個未満しか購入していないお客様がたくさん並んでいるにもかかわらず、 他方のレジでは誰も精算をしていないという状況がありえることです。

Dedicatedの問題点を解決するルールのひとつに、「たくさん買うお客様に 一方のレジ（レジ１）に並んでもらい、あまり買わないお客様に他方のレ ジ（レジ２）に並んでもらう。ただし、レジ１に誰も並んでいないときにあま り買わないお客様が精算のために並ぼうとするときには、レジ１に並んで もらう。」というのが考えられます。このルールをCycle Stealingと呼ぶこと にします。Cycle StealingはDedicatedの問題点を解決し、かつたくさん買う 少数のお客様のあとにあまり買わない大多数のお客様が長い列を成して待つよ うな状況がないので、Least Remaining Workのような問題点もありません。

Cycle Stealingよりも良いルールは存在するでしょうか？存在するとしたら最 適なルールはどのようなルールなのでしょうか？これらの問いに対する回答は いくらかありますが、まだ完全な答えは分かっていません。もう少し研究が進 んだら紹介したいと思います。ただし次のようなルールは望ましくないことに 注意してください。「たくさん買うお客様に一方のレジ（レジ１）に並んでも らい、あまり買わないお客様に他方のレジ（レジ２）に並んでもらう。ただし、 レジ１に誰も並んでいないときにあまり買わないお客様が精算のために並ぼう とするときには、レジ１に並んでもらう。また、レジ２に誰も並んでいないと きにたくさん買うお客様が精算のために並ぼうとするときには、レジ２に並ん でもらう。」このルールを2-way Cycle Stealing と呼ぶことします。2-way Cycle Stealingがなぜ望ましくないかはもうお分かりでしょうか。2-way Cycle Stealingにおいては、両方のレジにたくさん買うお客様が並んでしまう ことがあります。そうなると、そのあとに多くのあまり買わないお客様が ならんでしまい、これはLeast Remaining Workの問題点でもありました。

ここまでCycle Stealingにおける平均の待ち時間は、Shortest Queue, Least Remaining Work, Dedicatedなどに比べてずっと短いということを、言葉で直 感的に説明してきました。本当にCycle Stealingにおける平均の待ち時間は短 いのでしょうか？どんな場合でも平均の待ち時間が短いのでしょうか？そうで ないとしたら、どのような場合に平均の待ち時間が短いのでしょうか？このよ うな疑問に答えるためには、Cycle Stealingやその他のルールに従ったときの 平均の待ち時間を求めることが必要になります。現実のスーパーマーケットで 実験をしても良いですし、コンピューター上でシミュレーションをしても良いで しょう。しかし、実験やシミュレーションによって、正確に平均の待ち時間を 求めようとすると、非常に時間がかかってしまうために、限られた状況におい てしかCycle Stealingと他のルールの比較ができません。解析的に数学を使って 平均の待ち時間を求めることができれば、様々な状況における比較が可能となり、 結果的により多くの知見を得ることができるでしょう。

「確率モデルにおける性能の解析」の研究では、単にCycle Stealingのような ルールを考えるだけではなく、そのルールの性能、例えば平均の待ち時間がど れくらいになるかを解析する手法についても考えます。性能を解析するには、 まず厳密にモデルを定義する必要があります。お客様が買い物をしてレジにやっ てくる確率過程、レジで精算にかかる時間の確率分布などを過去の履歴などか ら推定して、それらの確率過程、確率分布のもとで平均の待ち時間を解析しま す。（このあたりから専門的になります。博士論文[THESIS06]ではもう少し分 かりやすく解説していますので参照してください。）一般に解析は非常に困難 であるため、確率過程はMarkovian Arrival Process (MAP)、確率分布は Phase-type distribution (PH 分布)で近似します。こうすると、平均の待ち 時間はMarkov chainを解析することで求めることができるようになります。 MAPはどんな確率過程でも任意の精度で近似でき、PH分布はどんな確率分布で も任意の精度で近似できますが、精度を上げると解析時間により長い時間がか かってしまいます。またCycle Stealingのようなモデルでは得られるMarkov chainは多次元に巨大な状態空間を持ち、通常の解析手法ではうまく解析でき ません。そこで、Markov chainの状態空間の次元をうまく下げてあげて効率的 に解析できるようにしました。詳細は論文[SPAA03]や博士論文[THESIS06]を参 照してください。

発表論文

論文誌, 査読あり

• [PE06b] Adam Wierman, Takayuki Osogami, Mor Harchol-Balter, and Alan Scheller-Wolf, "How many servers are best in a dual-priority FCFS system?," Performance Evaluation, accepted for publication.
• [PE06a] Takayuki Osogami and Mor Harchol-Balter, "Closed Form Solutions for Mapping General Distributions to Minimal PH Distributions," Performance Evaluation, Special issue for the selected best papers of TOOLS 2003, 63(6):524-552, 2006.
• [QUESTA05] M. Harchol-Balter, T. Osogami, A. Scheller-Wolf, and A. Wierman, "Multi-server queueing systems with multiple priority classes," Queueing Systems: Theory and Applications, 51(3-4):331-360, 2005.
• [PE05] Takayuki Osogami, Mor Harchol-Balter, and Alan Scheller-Wolf, "Analysis of cycle stealing with switching costs and thresholds," Performance Evaluation, 61(4): 347-369, 2005.

国際会議・研究会, 査読あり

• [SIGMETRICS05] Adam Wierman, Mor Harchol-Balter, and Takayuki Osogami, "Nearly Insensitive Bounds on SMART Scheduling," The ACM International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS 2005), pages 205-216, Banff, Canada, June 2005.
• [MAMA05] Mor Harchol-Balter, Takayuki Osogami, Alan Scheller-Wolf, "Robustness of Threshold Policies for Beneficiary-Donor Model," The Seventh Workshop on Mathematical Performance Modeling and Analysis (MAMA 2005), Banff, Canada, June 2005; Performance Evaluation Review, 33(2):36-38, 2005
  
• [ALLERTON04] Takayuki Osogami, Mor Harchol-Balter, Alan Scheller-Wolf, Li Zhang, "Exploring Threshold-based Policies for Load Sharing," The Forty-Second Annual Allerton Conference on Communication, Control, and Computing, pages 1012-1021, Urbana, IL, September 2004 (invited).
• [MAMA04] Takayuki Osogami, Adam Wierman, Mor Harchol-Balter, and Alan Scheller-Wolf, "A recursive analysis technique for multi-dimensionally infinite Markov chains," The Sixth Workshop on Mathematical Performance Modeling and Analysis (MAMA 2004), New York, NY, June 2004; Performance Evaluation Review, 32(2):3-5, 2004.
• [MASCOTS03] Adam Wierman, Takayuki Osogami, and Jorgen Olsen, "A Unified Framework for Modeling TCP-Vegas, TCP-SACK, and TCP-Reno," The 11th IEEE/ACM International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS 2003), pages 269-278, Orlando, FL, October 2003.
• [TOOLS03b] Takayuki Osogami and Mor Harchol-Balter, "A Closed-form Solution for Mapping General Distributions to Minimal PH Distributions," The 12th International Conference on Modelling Tools and Techniques for Computer and Communication System Performance Evaluation (TOOLS 2003), pages 200-217, Urbana, IL, September 2003.
• [TOOLS03a] Takayuki Osogami and Mor Harchol-Balter, "Necessary and Sufficient Conditions for Representing General Distributions by Coxians," The 12th International Conference on Modelling Tools and Techniques for Computer and Communication System Performance Evaluation (TOOLS 2003), pages 182-199, Urbana, IL, September 2003.
• [SIGMETRICS03] Takayuki Osogami, Mor Harchol-Balter, and Alan Scheller-Wolf, "Analysis of Cycle Stealing with Switching Cost," The ACM International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS 2003), pages 184-195, San Diego, CA, June 2003.
• [MAMA03] Adam Wierman, Takayuki Osogami, and Jorgen Olsen, "Modeling TCP-Vegas under On/Off Traffic," The Fifth Workshop on Mathematical Performance Modeling and Analysis (MAMA 2003), San Diego, CA, September 2003; Performance Evaluation Review, 31, pages 6-8, 2003.
• [ICDCS03] Mor Harchol-Balter, Cuihong Li, Takayuki Osogami, Alan Scheller-Wolf, and Mark S. Squillante, "Analysis of Task Assignment with Cycle Stealing under Central Queue," The 23rd IEEE International Conference on Distributed Computing Systems (ICDCS 2003), pages 628-637, Providence, RI, May 2003.

その他の論文と発表

• 恐神貴行, "［招待講演］マルコフ連鎖の次元削減法とタスク割り当てルールの性能解析への応用," 電子情報通信学会 情報ネットワーク研究会, 愛知郡, 2007年2月.
• "複数のサーバからなる様々なシステムの性能解析" 日本オペレーションズ・リサーチ学会　待ち行列研究部会, 東京, 2006年11月.
• "Approximating general distributions by minimal PH distributions," Workshop on Quantitative Models for Production and Communication Networks, Eindhoven, Netherlands, July 2004.
• "An adaptive threshold-based policy for sharing servers with affinities," INFORMS/APS Conference, Beijing, China, June 2004.
• "Designing good & robust policies," The ACM International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS 2004), Work-in-progress session, New York, NY, June 2004.
• Alan Sheller-Wolf, Mor Harchol-Balter, Takayuki Osogami, and Adam Wierman, "A new dimensionality reduction approach applied to computer scheduling," INFORMS 2003, Atlanta, GA, October 2003.
• Mor Harchol-Balter, Takayuki Osogami, and Alan Scheller-Wolf, "Cycle Stealing and the Dimensionality Reduction Technique."
• Takayuki Osogami, Mor Harchol-Balter, and Alan Scheller-Wolf, "Performance Analysis of Benefits of Cycle Stealing."
• Alan Scheller-Wolf, Mor Harchol-Balter, Cuihong Li, Takayuki Osogami, and Mark Squillante, "Analysis of Task Assignment."
• Adam Wierman, Mor Harchol-Balter, Takayuki Osogami, and Alan Scheller-Wolf, "Priority Scheduling in Multiserver System."