やさしい待ち行列（4）ネットワークとコントロール
高橋 幸雄

I…lll川…lll llMl lJ ll Jf…ll l J

lHILLll…ll M LL…ll…1111…lLL…Illl…u …LLu IL

tIILLl………ItLL………… M………l…州…l……ll川州…l…‖ I … t…tl ll……llt ………t

Mt…

tMI……‖tlIIMM…

…

最終回の今回は、待ち行列がネットワーク状につながった待ち行列ネットワークと、そのときに重要となるコントロールの問題について考えてみましょう。
前回お話ししたような待ち行列は、単独で存在するものばかりではなく、あちこちに互いに関連しながらできることがよくあります。たとえば組立工填では組→み立てられていく半製品が工程ごとに待ち行列を作っていますし、コンピュータの中でもジョブがCPtJの前到着

待ち行列
窓口やディスクの前などで行列を作って自分の順番を待っ

図1：最短順と最長順ています。最近、急速に技術革新が行われている高速通信でも、ネットワークを通じて情報が送られるときた。もうひとつ、サービスの順番を変えることによっ各ノードのバッファで待ちが入ります。このような複て平均待ち時間を小さくすることもできます。

数の待ち行列が関連してシステムを構成しているものを、待ち行列ネットワークと呼んでいます。

ここでも簡単のためM／M／1モデル、つまり窓口は1つで、客はパラメータ入のポアソン過程にしたがっ

このような待ち行列ネットワークでは、どの待ち行て到着し、平均1ルの指数分布にしたがう時間だけサ列が混んで、どれがすいているか、ボトルネックはどービスをうける、というモデルで考えてみましょう。

こか、ある待ち行列が混みだすと、それが他の待ち行いま、待ち行列で待っている客それぞれの要求サー列にどのように伝播するか、などいろいろな問題があビス時間が、前もってわかっているものとします。あり、さらにこれらの問題を解消するためにどのようなる客のサービスが終了したときに、つぎにサービスすコントロールが可能なのか、といる客は、到着順に関わらず、待っている客の中でサーえていかなければなりません。

ビス時間が最も短い客を選ぶ、というサービス規律をこれらはモデル解析という点からもたいへん難しく、本講座のレベルをはるかに超えていますが、ここ最短順 、最も長い客を選ぶサービス規律を 最長順と呼びます（図1）。ではクイズ、ではその一部をちらっとご紹介しましょう。まずは、単独の待ち行列のコントロールの問題からです。

クイズ1

M／M／1モデルにおいて、先着順、最短順、最1．最短順サービス

長順の3つのサービス規律で前回、待ち時間を小さくするには、i）到着客の数をどれが一番短くなるでしょう。

減らすかサービス時間を短くして利用率βを小さくすること、ii）到着間隔やサービス時間の分布のランダムネスを小さくすること、iii）そして可能ならば複数窓口にすること、が有効であることをお話ししまし何をどう考えたらよいのか、わかりにくかったかもしれませんが、つぎのように考えると理解しやすいと思います。

図2を見てください。いま、客Fのサービスが終たかはし ゆきお 東京工業大学 大学院 情報理工学

了した時刻tにおいて3人の客A，B，Cが待ち行列研究科 数理・計算科学専攻で待っているものとしましょう。この3人が先着順で〒152東京都目黒区大岡山2−12−1

サービスされるなら、時刻t以降のこれら 3人の待‖川（38）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ

到着t

窓口

図2：待ち時間の比較

図3：プロセッサーシェアリング

ち時間の合計（図の格子のハッチ部分の面積）はこれをみると、利用率βが0．8のときは、最短順ではⅣヴが先着順のときの半分以下になることがわかⅣt（先着順）＝25■A＋5βとなります。ここで∫A，∫β，∫cはそれぞれ客A，B，ります。βが0．5のときは、これほどの効果はありませんが、それでも待ち時間をかなり短くしています。

Cのサービス時間です。

3人のサービス時間の長さがぶβ＜∫c＜∫Aという順序であったとすると、最短順のときはB，C，Aの順にサービスされます。するとこのときのt以降の3表1の割り込み最短順というのは、新たな客が到着したとき、その客のサービス時間がサービス中の客の残りサービス時間より短かければ、サービス中の客のサービスを一時中断し、到着した客のサービスを先人の待ち時間の合計はに行う（割り込み、図5参照）、というサービス規律でl弟（最短順）＝25 β＋∫cす。これは最短順をさらに徹底したもので、これが平となりますが、これが上のⅣ亡（先着順）よりも小さい
ことはサービス時間の大小関係から明らかです。最長
傾が最も大きくなることも、同様に確かめられます。

均待ち時間を最も小さくすることが知られています。

2．計算機とサービス規律

3人のサービスの順番をこのようにいろいろ変えて

前節の最短順は、客のサービス時間があらかじめわも、他の客の待ち時間には影響しませんので、待ち時かるときしか使えません。しかし実際には、客のサー間の合計は、したがって平均待ち時間も、最短順のとビス時間はサービスをしてみないとわからないのかきがもっとも短く、最長順がもっとも長くなります。こふつうです。そこで計算機の世界では、サービス時間

こでの議論にはポアソン到着や指数分布といった仮定がわからないときでも実質的に最短順サービスに近は何も使っていませんので、この性質はすべての標準づけるよう、いろいろな工夫がなされています。

型待ち行列モデルに対して成り立ちます。

2．1 プロセッサーシェアリング
では、最短順ではどのくらい平均待ち時間Ⅳ9か短くなるかというと、残念ながらこれは解析的には求められません。そこでシミュレーションで確かめてみました。表1がその結果です。ここでは平均サービス時間を1としています。

そのひとつは、プロセッサーシェアリングといって、図3のように待ち行列は作らず、そのときに系内にれ個のジョブがあったとすると、サービス能力を1／mずつに分けて†l個のジョブを少しずつ同時にサービスするものです。たとえば、あるジョブが、そのサービ

表1：サービス順による平均待ち時間の違い

ス中、ずっとn−1個のジョブと一緒だったとすると、そのジョブのサービスには本来のサービス時間のTl倍

β．5

1．78

割り込み最短順 0．58

1996年2 月号．8

最短順0．72

1．88

先着順

1．00

4．00

最長順

1．44

9．10かかるということです。

こうすると、最短順ほどではありませんか、サービス時間の短いジョブは長いジョブよりも早めにサービスが終了され、全体として平均系内滞在時間が小さくなることが期待されます。

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（39）川1

待ち行列

到着

待ち行列

到着

待避

窓口

窓口

図4：非割り込み優先権

図5：割り込み継続型優先権

2．2 優先権をつける

このクイズに答えるため、つぎのような待ち行列モデルを考えてみましょう。

計算機に投入するジョブを、バッチジョブと会話型ジョブの2種類に分類することがよくあります。
会話型ジョブは、エディタを使うなど、ちょっと計算機で試してみて、その結果をもとにまた修正する、といったごく短い計算時間のジョブで、結果がすぐに返ってくることが要求されます。一方、バッチジョブ
は計算時間が長く、結果が返ってくるのに多少時間が客にはタイプ1（会話型ジョブ）とタイプ2（バッチジョブ）があり、タイプ1の客はパラメータ入1のポア
ソン過程にしたがって到着し、パラメータ〃1の指数分布にしたかう時間だけサービスを受けます。タイプ

2の客も同様で、パラメータはそれぞれ入2，〃2です。
記号を少し導入しておきましょう。

かかることは仕方がありません。そこで、この違いを

β1＝〃rl入1，β2＝〃；1人2（1）利用して、会話型ジョブに優先権を与えます。

β＝β1＋β2，占＝〃「1β1＋〃；1β2（2）

優先権の与え方には何通りかありますが、代表的なのは非割り込み優先権と割り込み継続型優先権です。
非割り込み優先権というのは、ある客のサービスが終了したときに、図4のように待ち行列にバッチジョブ（網掛け）と会話型ジョブ（白抜き）の両方が待ってすると、クイズのサービス規律のもとでのタイプ1とタイプ2の客の平均系内滞在時間Ⅳ1とl悔は、表2のように与えられることが知られています。そして、全体の平均系内滞在時間は
lルr ＝いるときは、会話型ジョブを優先してサービスするも入11γ1＋12Ⅳ2（3）

入1＋Å2のです。図4では、待ち行列の先頭と2番目のバッチで求められます。Ⅳ1とⅣ2の間にはジョブを3番目に並んでいる会話型ジョブが追い越し
β1Ⅳ1十β2Ⅳ2 ＝ 一定て、つぎにサービスを受けます。一般に会話型ジョブ（4）の方がバッチジョブよりも短いので、という関係がありますので、lγ1とⅣ2の両方を小さ同様の効果があり、平均待ち時間が短くなるのです。

くすることは不可能です。しかし入1＞Å2 という関割り込み継続型優先権では、つぎにサービスされるジョブとして会話型ジョブが優先されることに加え

衰2：サービス規律と平均系内滞在時間の公式て、会話型ジョブが到着したときにバッチジョブがサービス中であれば、そのバッチジョブのサービスを一l鳩∽′1FCFS

時的に中断し、到着した会話型ジョブをサービスしまー ＋〃rl
1−βす（図5）。ではクイズ、

l‑p＋〃；1lPS垢1〃r

1−β1一βクイズ2NP

計算機でジョブの平均ターンアラウンドタイ

ム（平均系内滞在時間）を短くするには、先着順（FCFS）、プロセッサーシェアリング（PS）、非割り込み優先権（NP）、割り込み継続型優先権（PR）のうち、どのサービス規律をとるとよいでしょう。

川2（40）

PR

1空β1＋〃rl〃rlβ1＋〟rl 1一戸l（1−刷1−β）＋〃；1み＋（1＿Pl）（トβ）1

FCFS：先着順 PS：プロセッサーシェアリング
NP：非割り込み優先権 PR：割り込み継続型優先権© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ

●

・二キニ
図7：閉待ち行列ネットワーク

図6：開待ち行列ネットワーク

係を利用して、l鳩の犠牲のもとにⅣ1を小さくすることによって、全体の平均系内滞在時間Ⅳを小さくすることは可能です。（この原理は最短順でも同じです。つまりある種の不公平を導入しているのです。）
具体的に数値をあてはめて、平均系内滞在時間はどれが短いかみてみましょう。結果は表3の通りです。
表3：サービス規律による平均系内滞在時間の違い
入1＝2，入2＝1，〃1＝20，〃2＝2

図8：直列型待ち行列システム

外から入ってきて、あちこちのノード（個別の待ち行列）を訪問してサービスを受けた後、ネットワークの外へ出ていきます。図8の直列型待ち行列システムは生産ラインの性能評価に欠かせないものですが、これは典型的な開ネットワークです。

lγ1

FCFS ．6875

l砺lルr

一方、図7の閉待ち行列ネットワークでは、客はネ

1．1375．8375

ットワークの外から入ったり外へ出たりしません。し

PS

．1250

1．2500．5000

たがって常に一定の数の客がネットワークの中を動きNP．3333

1．2083．6250

回っていることになります。計算機システムの代表的PR．0556

1．2639．4583

なモデルである図9のセントラルサーバモデルは、典型的な閉ネットワークです。

先着順（FCFS）と較べて、プロセッサーシェアリン

待ち行列ネットワークは、単独の待ち行列モデルがグ（PS）と割り込み継続型優先権（PR）が優れている

いくつもつながっているのですから、大変複雑なモデことがわかります。実際、多くの汎用計算機では割りルになり、そう簡単に解析することはできません。た

込み継続型優先権が、またUNIX系の計算機ではプだ、ジャクソン型ネットワークというM／M／c待ち行ロセッサーシェアリングが採用されています。

列がつながったような特殊なケースについては、横形

3．待ち行列ネットワーク
計算機や通信システム、生産システムなどでは、客がシステムの中で何度もサービスをうけて出ていきます。そのため待ち行列もたくさんできてきます。このような複雑なシステムをモデル化するには、待ち行式解という大変きれいな結果が得られています。

4．ジャクソン型ネットワーク
つぎのような待ち行列ネットワークをジャクソン型ネットワークといいます1。
〃個のノードがあり、ひとつひとつのノードは窓列がネットワーク状につながった 待ち行列ネットワーク モデルが必要です。

待ち行列ネットワークは、客がネットワークの外から入ったり外へ出たりするかどうかによって、開ネットワークと閉ネットワーク、およぴそれらの混合型に大別することができます。

開待ち行列ネットワークでは、図6のように、客は1本文の仮定はもっとゆるめられます。たとえば、窓口の数は複数でもよいし、サービス率はそのときのノードにいる客の数に依存してもかまいません。また、外からの客の到着率も、ネットワーク内の客の総数に依存してかまいません。

ただし、待合い室の容量は無限でなければなりません。有限のときはブロッキングという面倒な状況が発生します。
また、ジャクソン型をさらに一般化したBCMP型ネットワークというのもあります。

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

1996年2 月号（41）103

ロと待ち行列から成っています。ここでは簡単のためすべて単一窓口であるものとしましょう。 ノードノの窓口では、パラメータが朽の指数分布にしたがったサービスが行われます。ノードfでサービスを終了した客は、確率rfjでノードブへ進みます。

さらに、開ネットワークでは、外部からノードJへ

図9：セントラルサーバモデルの客の到着は、パラメータスノのポアソン過程に従います。また、ノードブでサービスを終了した客は、確十分時間がたったときに、ノードノ，ノ＝1，2，…，〃，に，り人の客がいる確率は、∑た17り＝〟のとき、率り0でネットワークを去ります。
むろん、客の到着、サービス、ノード選択などの確率現象は、みな互いに独立であるものと仮定します。

p（…Ⅳ）＝去蝉）nメ（8）

4．1 開ネットワークとなることが知られています。ここでCは（8）の和
ち，ブ＝1，2，…，〃，を方程式が1となるような正規化定数です。この式は各ノード〃

βメ＝入ブ＋∑βiγiJ，ノ＝1，2，…，Ⅳに対応する項の積の形をしていますので、 横形式解（5）と呼ばれています。

i＝1の解とします。このβJは、ノードノへの到着率と開ネットワークのときはどんなりの組み合わせにみなせます。そこでの＝と置くことにしましょ対しても（6）の式が成り立ちました。閉ネットワーク

杓う。すると、十分時間がたったとき、ノードノ，ノ＝の場合、（8）が成り立つのは∑た1γlJ＝〟となると

1，2，…，〃，に丁り人の客がいるという状態の確率はきだけです。したがって、各ノードは独立ではありま．Ⅳ

p（711，…，叫＝n÷β；Jせん。そのため正規化定数Gを求めること、さらに（6）

L−／一Jは各ノードでの平均客数やスループットといったネッで与えられることが知られています。

トワークの特性量を求めることは、簡単にはできませJ＝1（6）から、各ノードはあたかも互いに独立なM／M／1ん。このためたたみこみ法や平均値解析法といった閉ネットワーク専用の■解析手法が開発されています。

待ち行列モデルであるかのように考えられます2。したがって、各ノードにおける平均滞在時間やネットワ

4．3 セントラルサーバモデル

ークに入ってからそこを去るまでの平均滞在時間などは、簡単に計算することができます。この意味で、ジ閉待ち行列ネットワークの例として、計算機の典型ャクソン型の開ネットワークほ容易に解析することが的なモデルであるセントラルサーバモデルをみてみできるといってよいでしょう。

ましょう。これは図9のように、CPUに対応する1つ4．2 閉ネットワークと横形式解のノードと、ディスクに対応する複数の並列ノードからなっているモデルです。ここでは簡単のため、ディ条件はほとんど同じでも、閉ネットワークの場合にスクは2台しかないものとします。

は状況がかなり異なります。ネットワーク内に〟人

CPUで平均扁1の指数分布にしたがう時間サービ（一定）の客がいるものとしましょう。

スされたジョブは、確率γ1でディスク1へ、確率γ2

βブ，ノ＝1，2，・‥，〃，を方程式でディスク2へ進みます。ディスク1と2ではそれぞノⅤ

βJ＝∑甚句，J＝1，2，…，〃

れ平均〃rl，〃・；1の指数分布にしたがう時間サービス（7）を受け、またCPUへ戻ります。

i＝1の解とします。ただしこの方程式から求められたβブ

このモデルでは、システム内にあるジョブの数〟は、定数倍の自由度があります。そこで、ひとつのβJは一定であるものと仮定されています。実際の計算機（たとえば町の値は任意に定めることができます。

では、ジョブの多重度が設定されていることが多く、CPUにアクセスできるジョブの数は一定に制限され2厳密にいうと、互いに独立な のは平衡状態における同時分布だけで、ノード内客数の変化などの過程は互いに独立にています。各ジョブは何回かCPUで処理されるとシはなりません。

ステムの外に出ていきますが、すると入れ替わりにシ104（42）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ●

ステムの外で待っていたジョブが入ってきます。この

表5：クイズ3のセントラルサーバモデル

ように、ジョブ数一定という仮定は不自然ではなく、ケース1

ケース2

むしろ理にかなったものなのです。
J

具体的な数字を入れて、各ノードでの平均ジョブ数などを求めてみましょう。平均値解析法という計算方法を用いると簡単に求められるのですが、紙数の関係

エゴ

0 4．000

2

呵

エゴ

町

5．000 95．000 95．000

2．000

5．000

94．000235．000

3．000

5．000

2．000

5．000

で詳細は省略いたします。
〃0＝1 〃1＝・6例少々パラメークをいじってみても、ジョブが確率的〃2＝・4

rl＝．6にルート選択している限り、ボトルネックができるとr2＝．4とします。このとき、システム内の客数が10人のときと100人のときの、ノードJにおける平均客数エJと、ノードノを1回通過するのにかかる時間の平均いう性質を回避できません。これを避けるには、強力なコントロールを導入するしかありません。
現在、構築が始まっている超高速情報ネットワーク
では、ノードの混雑状況を情報発信源に知らせることlりは、表4のようになります。

によって、混雑をコントロールしようとしています。
表4：バランスしたセントラルサーバモデルの例

ットワークを構築することは、いま、緊急の課題です。

〟＝10＿打＝10

その効果を評価し、信頼性と効率性とを兼ね備えたネ

5．新しい待ち行列理論を求めて

ノエゴ

呵

0

3．333

4．000

33．33334．000口3．3336．667

33．33356．667

待ち行列ネットワークに関して、残念ながら待ち行

2

3．333

10．00033．33385．000

列理論はまだまだ未熟です。ジャクソン型の仮定が少町上Jし崩れただけでも、その挙動はまだほとんどわかっていません。ましてや、コントロールが入ったり、動画ここでクイズです。

データのように従来のポアソン到着とは全く異なる到着パターンが出現すると、それをどう扱うか、といクイズ3上のセントラルサーバモデルで、パラメータがう段階から考え直さなければなりません。

つぎのように少し変わったら、システム内総ジョ現在、情報通信ネットワークが急速に発展していま

ブ数〟＝100のとき、平均ノード内ジョブ数上Jすが、その性能評価をタイムリーに行うためにも、待はどのように変わるでしょうか。

ち行列理論は大いに期待されています。従来の解析手

ケース1

rl＝．5 r2＝．5

法にとらわれず、新しい発想で新しい理論構築を行う

ケース2〃1＝．8 〃2＝・6

時期にきたのだと思います。若い方々にも、ぜひ、研これは、ぜひ、答えをみる前にご自分で考えてみてください。たとえば、ケース1ではrlが少し減ってr2が増えたのだから、上の例から類推すると・。ていってほしいものです。
この4回シリーズもいよいよ今回で終わりですが、長いことお付き合いくださいましてありがとうござじつは、表5のようになります。
どうですか、全く予想はあたりましたか。これはわざと意地悪な出題をしたのです。はじめの例では、たまたま各ノードの負荷がバランスしていたので、上よもバランスしていたのですが、これはとても特殊な場合なのです。たいていはどこか1ヶ所がボトルネックとなって、そこだけに客が集まってしまいます。ケー

ス1ではディスク2がボトルネックとなり、ケース2
ではCPUノードがボトルネックになっています。
1996年2 月号

究に参加して、新しい待ち行列理論を一緒に作り上げいました。参考文献はつぎの補遺をご覧ください。
このシリーズを執筆するにあたり、待ち行列研究部会および高校生のためのOR研究部会のメンバーの方々から貴重なご意見をたくさん頂戴いたしました。
また、今回のシミュレーションを含め、原稿作成に全面的に協力してくれた大学院生の大原久樹君はじめ、東京工大の高橋・牧本研究室の諸君にもお世話になりましたb この場を借りて深く感謝いたします。

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（43）105