になり、計算が困難である。 待ち行列理論というものがある。これを使うと、例えば銀行のATMの順番を待っている待ち行列について、平均何分待たされるか、行列で待っている人数は平均何人かなどを計算することができる。その際に、単位時間当たりに来る平均人数（λ）、単位時間当たりに帰る平均人数（λ）などのパラメータが必要になる。
待ち行列理論は、電話会社に勤務していたアーランという人物が、「許容される電話サービスを提供するために、どれだけの回線を用意する必要があるか」を決定する問題を提示されたことをきっかけにつくられた。待ち行列理論の中にアーランC式というものがある。これは、例えばコールセンターにかけられた電話がすぐに繋がらない確率を計算するもので、オペレータの人数をS人、利用率ρ（＝λ／μ）とすると、になり、計算が困難である。
インターネットの解析のために開発されたNS2というソフトウェアがある。NS2では、構成したいネットワークをObject Tcl言語で記述すると、そのネットワークのトラフィックをシミュレーションできるソフトウェアである。
使用例としては、図１のようにノード、ノード間のリンク（回線速度、遅延）、プロトコルなどを設定して、パケットを送るプログラムをつくる。
図２のようなプログラムをつくり、NS２で待ち行列モデルをシミュレーションする。
本研究では、計算が困難な待ち行列理論の式を実際に計算せず、代わりにシミュレーション結果から答えを得られないかを調べる。具体的には、待ち行列モデルM/M/1(k)の呼損率を求めるアーランB式、待ち率を求めるアーランC式の分析をして、理論値と実験値の比較をする。
第２章では、待ち行列理論の説明とアーランB式・アーランC式の導出を行う。第３章では、分析に使用したソフトウェアの説明をしている。第４章では、シミュレーション実験を行う。第５章ではまとめを行っている。
待ち行列理論は、通信トラヒック理論と似ており、現在は統合されつつある。用語は異なるが、同等な理論と思って良い。
通信トラヒック理論は、電話通信網の交換設備の解析・設計のための理論で、２０世紀の始めにデンマークのA.K.Erlang（アーラン）によってつくられた。
一方、サービスを提供する上で重要な視点として、ユーザ集団から発生してくる需要の量と、その需要を受け止めてサービスを提供する環境（設備や人）、そしてその結果として現れるサービス品質や性能がある。待ち行列理論はこの三つの関係に確率論を用いて数学的な根拠を与える理論である。
待ち行列理論は、第二次世界大戦中に米英軍により開発されたオペレーションズリサーチ（数学的なアプローチにより経営問題の意思決定を支援する）の分野において研究され、窓口問題、交通問題、在庫管理等の広い分野に適用されている。
待ち行列のモデルでは、客が来て窓口に並び、順番が来れば窓口でサービスを受け、サービスを受け終われば客は去る、というものである。待ち行列理論と通信トラヒック理論で使われる用語は違うので、対応表を表１に示す。
表１．待ち行列理論と通信トラヒック理論の用語の対応表
| 待ち行列理論 | 客 | サービス | 窓口 |
| 通信トラヒック理論 | 呼（電話やデータなどの接続要求） | 保留 | 出線 |
待ち行列システムは、次の五つの要素からなる確率モデルで表される。
これらを、a／b／c（d）と表記するのがケンドールの記号と呼ばれる。但し、このa、b、c、d、eとして以下のような表記が用いられる。
aとbは、確率分布であり、以下の記号のいずれかで表されることがある。
：指数分布（後述）
：位相ｋアーラン分布（ｋ個の独立な同一指数分布の和）
：ｎ次超指数分布（ｎ個の異なる指数分布の混合）
：単位分布
：一般分布
：再生過程（間隔が独立な一般分布に従う過程）cは自然数である。サービス窓口の数が複数あれば、一度に複数の呼を扱うことが可能になり、処理効率が上がる。
dの待ち行列の長さの上限も自然数である。これは、待ち行列に入ることができる呼の最大値である。待ち行列の長さの上限が有限の場合はｋまたはSと表記し、無限の場合は省略される。待ち行列に空きが無い時に呼が到着すると、その呼は捨てられる。
eの処理規範は、通常到着した呼から処理をする到着順処理（FIFO：First In First Out）で、特に表記されることは無い。他にも、逆順処理（LIFO）、ランダム処理などがある。
特に、本研究で扱う待ち行列モデルM/M/1(k)は、呼の到着時間間隔と保留時間が指数分布によってランダムに決まり、サービス窓口の数は一つ、システムの容量はｋ個であるという意味である。
呼がランダムに発生する過程を解析する。ランダムな呼の発生は、次のルールに従うとする。
上の三つのルールのもとに、時間(0,t)中にｋ個の呼が生起する確率
を求める。時間(0,t)を十分多くのｎ個の区間に分割し、一つの区間を微小時間
とする。ここで、単位時間中に呼が一つ発生する確率を生起率とし
で表す。ｎ個の区間のうち、特定のｋ個の区間で呼が発生し、残りの(n-k)個の区間で発生しない確率は
となる。ｋ個の区間の選び方は
通りあることを考慮し、
、
とすると、
ネイピア数の定義式
を利用すると、最終的に
これは、平均値
のポアソン分布である。このような生起をポアソン生起と呼ぶ。
時間(0,t)中に一つも呼が発生しない確率は
となる。したがって、(0,t)以内に呼が発生する確率は、
になるので、呼の生起間隔の分布関数は
となり、平均値
の指数分布に従う。このように、生起間隔が指数分布となることが、ランダム生起の特徴である。
呼がランダムに終了する（保留時間が終わる）場合について考える。これは、微小時間
中に呼が終了する確率が、時刻に無関係に
となるモデルに相当する。（
：終了率）
保留時間がｔより大きくなる確率は、時間ｔ中に呼が終了しない確率と等しい。そこで、時間ｔをｎ個の微小区間
lに分割すれば、時間ｔ中に呼が終了しない確率は
となるから、
、
とすると、保留時間がｔを超える確率は
となる。すなわち、保留時間がｔを超えない確率は平均値
の指数分布に従う。
本研究で扱う待ち行列モデルM/M/1(k)の解析を行う。呼の到着分布が生起率λのポアソン分布、保留時間分布が終了率μの指数分布、サービス窓口の数が１個、待ち行列の長さの上限は
k個である。ここで、利用率
を定義する。これは、サービス窓口で単位時間に終了する呼の数に対して、単位時間当たり、何倍の呼が発生するかを表している。単位としては、
[erl]（アーラン）を用いる。システムの容量が＝∞のシステムでは、λ＞μ（ρ＞１）ならば呼の発生するスピードが呼の終了するスピードを上回ることになり、
待ち行列の長さはどんどん長くなってしまう。したがって、シミュレーションが終わらなくなってしまうので注意が必要である。一方、システムの容量が有限ならば、あふれた分は捨てられる。
システム内呼数は、０、１、～（k-１）、kのいずれかである。それぞれの状態に対応した定常確率（時刻を無限まで伸ばすと、極限値になる）を、
とする。これを、状態遷移図で表すと、
のようになる。
状態遷移図の中にある矢印は、確率的な流れの出入りを表している。たとえば、（n-１）と
nの間の上にある矢印は、時刻ｔの時にシステム内呼数がn-1で、
後にシステム内呼数がnになる確率は、
となる。以後、は省略して記述する。隣接するシステム内呼数の間の確率的な流れの出入りが等しい
(Flow-out=Flow-in)という性質があるので、
という方程式を得る。これらと、すべてのPnの和が１という関係
より定常確率Pnを計算することができる。
式（１）より、
である。
式（３）においてn=1として、さらに式（５）を代入すると、
さらに、
を求めると、
となるので、同様にして
となる。式（６）より、
を式（２）に代入すると、
となる。結局、すべての
n=0,1,2,…,kに対して
となる。式（７）を式（４）に代入して
となる。等比級数の和の公式より
となるので、式（８）より、
となり、したがって、式（７）より
を得る。
アーランB式は、発生した呼がシステムに空きが無いので捨てられてしまう確率、呼損率を計算する式である。
アーランB式を導くために、待ち行列モデルM/M/S(0)の解析を行う。呼の到着分布が生起率λのポアソン分布、保留時間分布が終了率μの指数分布、サービス窓口の数がS個である。このモデルでは待ち行列は無い。システム内呼数がS個のときの定常確率が、アーランB式である。
システム内呼数は、０、１、～（S-１）、Sのいずれかである。それぞれの状態に対応した定常確率を、
とする。これを、状態遷移図で表すと、
この状態遷移図により、
を得る。これを変形して、
はシステムに呼がない状態の確率で、正規化条件
より
と決定される。こうして
となることが導かれた。この式からシステム内呼数がS個の定常確率を求めると
これが、M/M/S(0)型のアーランB式である。
M/M/1(k)型では、６ページの式（９）より定常確率が
で表されるので、アーランB式は、
になる。
アーランC式は、発生した呼が待ち行列で待たされる確率、待ち率を計算する式である。
アーランC式を導くために、待ち行列モデルM/M/Sの解析を行う。呼の到着分布が生起率λのポアソン分布、保留時間分布が終了率μの指数分布、サービス窓口の数がS個、システムの容量は無限である。このモデルの単位時間当たりの終了する呼の数はSμ個なので、λ＜Sμが条件である。サービス窓口に空きが無い、つまり、システム内呼数がS個以上の定常確率の和がアーランC式である。
システム内呼数は、０、１、～（S-１）、S、…である。それぞれの状態に対応した定常確率を、
とする。ここで、サービス窓口に空きがある場合(a)（ｎ＜S）と、サービス窓口に空きが無い場合(b)（ｎ≧S）に分けて考えてみる。これを、状態遷移図で表すと、
(a)の場合は、アーランＢ式のときと同様に、
(b)の場合は、
が成り立つ。ここで、式（１０）にｎ＝Ｓ－１を代入して、
となる。式（１１）から、
を知って、式（１３）に代入すると、
式（１２）にｎ＝Sを代入して、
式（１２）にｎ＝S＋１を代入して、
同様にして、
を得る。これで、すべてのｎに対して、
を
で表すことができたので、最後に正規化条件
よりの値を計算することができる。式（１１）と式（１４）より
また、ρ＜Sのときにこの無限級数は収束するので、
となり、最終的に
がわかったことにより、すべてのｎに対する
がわかるようになった。
したがって、アーランC式はシステム内呼数がS個以上の定常確率の和なので、
になる。
M/M/1(k)型のアーランC式は、システム内呼数が一個以上の時の定常確率（６ページの式（９）より）の和なので、
となる。また、正規化条件
より、
でもよい。
NS2とは，カリフォルニア大学バークレイ校で開発されたネットワークシミュレータである。NS2のソース，マニュアル，英語のチュートリアルなどはhttp://www.isi.edu/nsnam/で取得できる。NS2は、C++とOTclで書かれたオブジェクト指向のイベントドリブン・ネットワークシミュレータである。NS2自体はC++で記述されており、インターフェースの操作をOTclで行う。
簡単な使用例を挙げると、まず、ノードとリンクをつくり、リンクの最高転送速度などのパラメータを決め、ノード間でどのような通信（パケットサイズや接続形式）を行うかを決めてからシミュレートを開始すれば、テキストエディタで見ることができる出力ファイルが得られる。その出力ファイルには、マイクロセカンド単位でパケットの動きが詳細に記録されている。
Otclの構文を説明する。基本的には「コマンド 引数１ 引数２ …」という形である。一番使われるコマンドのsetの使用例は「set a 1」など。変数aに1という値を代入する。変数には文字列や数字などの型は無い。
変数の値を使いたいときは、変数の前に$をつける。具体的には、「set b a」と書けば変数bの値はaになるが、「set b $a」と書けば変数bの値は1になる。
計算をしたい時は、「set c [expr 1+1]」というように書けば、変数cの値は計算結果の2になる。これは、まずexprコマンドが1+1を計算し、その結果を[ ]が中の値を返す無名関数の役割をしているためである。
オブジェクトを生成するには、「set オブジェクトの名前 [new オブジェクトの種類]」と書きます。生成したオブジェクトに命令を出したいときは、「$オブジェクトの名前 コマンド 引数」と書きます。
ユーザー独自の関数を作りたい場合は、「proc 関数の名前 ｛引数｝｛内容｝」で定義する。この関数の中の変数は基本的にローカル変数なので、global宣言をしてグローバル変数にする必要がある。
Perlは、Webページの掲示板やチャットなどのCGIやシステム管理、テキスト処理などのプログラムに使われるインタプリタ方式のプログラミング言語で、Larry Wall氏によって開発され、1987年に一般公開された。記述の美しさよりも実用性をモットーにしている。当初はUNIX上で利用されたが、現在ではボランティアによりWindowsやMacintoshなどのプラットフォームに移植され、急速に普及を遂げてきた。Perlという名称には、次の二つのキーワードの意味がある。
Perlの構文はC言語に似ており、強力な文字列演算機能があるため、本実験で使用した。
複数の処理をまとめて行う（バッチ処理）ときに使われる、OSのシェルが直接解釈・処理できるスクリプト。シェルスクリプトはシェルごとに独自の機能を使用して処理されるため、起動の方法や文法はシェルによって変わってくる。例えばUNIX系OS（厳密にはその上で動作するbashなどのシェル）では、シェルにシェルスクリプトを引数として渡して実行したり、シェルスクリプトの冒頭に起動プログラムを書き込んでシェルスクリプト自体を実行したりすると起動できる。シェルスクリプトではシェルごとに独自の文法が採用されているが、おおむね一行が一つのコマンドとして扱われる。特にUNIX系OSのシェルは複雑な繰り返し処理や条件分岐などに対応しており、シェルスクリプトだけでかなり複雑な処理を自動化できる。
cygwinは、MicrosoftWindowsオペレーティングシステム上で動作するUNIXライクな環境の一つである。無料で入手・使用できる。本実験で使用するNS2がUNIX用に開発されたソフトウェアなので、Windowsで使うためにcygwinを使用した。
待ち行列モデルM/M/1(k)の動作をするシミュレーションをつくるために、二つのノードをつくる。そして、一方から他方へとパケットを送り続けるようにする。その際、パケットの発生する時間間隔を呼の到着時間間隔分布モデル、パケットのデータサイズを保留時間分布モデルにみたてる（パケットのデータサイズによって、パケットが伝送路を通る時間が変わるため）。そして、それぞれを指数分布にする。サービス窓口が一つで、伝送路のキューをシステムの容量にみたてる。それを図にすると図７になり、プログラム「mm1k.tcl」を以下に示す。
mm1k.tcl
set lambda [lindex $argv 0]
set mu [lindex $argv 1]
set qsize [lindex $argv 2]
set ns [new Simulator]
set tf [open out.tr w]
$ns trace-all $tf
set n1 [$ns node]
set n2 [$ns node]
set link [$ns simplex-link $n1 $n2 100kb 0ms DropTail]
$ns queue-limit $n1 $n2 $qsize
set InterArrivalTime [new RandomVariable/Exponential]
$InterArrivalTime set avg_ [expr 1/$lambda]
set pktSize [new RandomVariable/Exponential]
$pktSize set avg_ [expr 100000.0/(8*$mu)]
set src [new Agent/UDP]
$ns attach-agent $n1 $src
set qmon [$ns monitor-queue $n1 $n2 [open qm.out w] 0.1]
$link queue-sample-timeout
proc finish {} {
global ns tf
$ns flush-trace
close $tf
exit 0
}
proc sendpacket {} {
global ns src InterArrivalTime pktSize
set time [$ns now]
$ns at [expr $time + [$InterArrivalTime value]] "sendpacket"
set bytes [expr round ([$pktSize value])]
$src send $bytes
}
set sink [new Agent/Null]
$ns attach-agent $n2 $sink
$ns connect $src $sink
$ns at 0.0001 "sendpacket"
$ns at 1000.0 "finish"
$ns run
プログラムでは、生起率λ（パケット発生の時間間隔）、終了率μ（パケットのデータサイズ）、システムの容量（伝送路のキューのサイズ）、をプログラムの実行時にコマンドラインから引数として持ってくるようにしている。そして、二つのノードをつくり、そのノード間の伝送路の伝送速度、キューのサイズを決める。そして、パケット発生の時間間隔とパケットのデータサイズの平均値を指数分布に設定する（このプログラムでは、伝送路の伝送速度とパケットのデータサイズをうまく調整して、コマンドラインから持ってきた生起率と終了率がそのまま使えるようになっている）。二つのノード間の接続において、UDP（User Datagram Protocol：パケットが相手に届かなくても、再送しないという設定）、終了時の手続き、パケット送信の設定を決める。最後に、シミュレーションを時刻0.0001秒から開始し、1000.0秒で終了する。
NS2のプログラムを実行すると、以下のように「out.tr」というテキストファイルができる。
+ 681.616875 0 1 udp 109 ------- 0 0.0 1.0 21231 21231 + 681.628971 0 1 udp 25 ------- 0 0.0 1.0 21232 21232 d 681.628971 0 1 udp 25 ------- 0 0.0 1.0 21232 21232 r 681.648839 0 1 udp 965 ------- 0 0.0 1.0 21227 21227 - 681.648839 0 1 udp 24 ------- 0 0.0 1.0 21228 21228 r 681.650759 0 1 udp 24 ------- 0 0.0 1.0 21228 21228 - 681.650759 0 1 udp 234 ------- 0 0.0 1.0 21229 21229 + 681.662248 0 1 udp 437 ------- 0 0.0 1.0 21233 21233
一つの行にスペースで区切られた１２個の項目があり、一番目から順に
四つの文字(r,+,-,d)のいずれかで表され、 r:receive パケットの受け取り +:enqueued 伝送路のキューにパケットが入る -:dequeued パケットが伝送路のキューから出る d:drop 伝送路のキューが満タンで、パケットを捨てる を意味する。
を表している。このうち、実験に必要なのは１．イベントの種類、２．イベントが発生した時間、１２．パケットの連続番号である。呼損率を求めるためには、受け取られたパケットと捨てられたパケットを数えて、呼損率＝捨てられたパケット／（受け取られたパケット＋捨てられたパケット）で求めることができる。待ち率は、発生したパケット（＝受け取られたパケット＋捨てられたパケット）とキューで待たなかったパケット（キューに入った時刻と出た時刻が同じ）を数えて、待ち率＝（発生したパケット－待たなかったパケット）／発生したパケットで求めることができる。最後に利用率、呼損率、待ち率を出力するプログラム「mm1k.pl」を以下に示す。
プログラム中では、$n1に「out.tr」から一行読み込み、１２個の項目を@d1という配列に格納している。その中でも、必要な$d1[0] （イベントの種類）、$d1[1] （イベントが発生した時間）、$d1[11]（パケットの連続番号）を使う。$receiveにはノード２で受け取られたパケットの数を、$dropでは捨てられたパケットの数をカウントしている。@plusにはそれぞれのパケットがキューに入った時間を、@minusにはキューから出た時間を記録している。$nowaitには、キューで待たされなかったパケットの数をカウントしている。最後に利用率$ro、呼損率$koson、待ち率$matiを出力する
mm1k.pl
open(IN, 'out.tr');
@temp = <IN>;
@plus;
@minus;
$receive=0;
$drop=0;
foreach $n1 (@temp){
chomp;
@d1 = split(/ /,$n1);
if($d1[0] eq '+'){
$plus[$d1[11]] = $d1[1];
}
elsif($d1[0] eq '-'){
$minus[$d1[11]] = $d1[1];
}
elsif($d1[0] eq 'r'){
$receive++;
}
elsif($d1[0] eq 'd'){
$drop++;
}
}
$i = 0;
$nowait = 0;
for ($i=0;$i<=$#minus;$i++){
if (defined($minus[$i])){
if ($minus[$i] == $plus[$i]){
$nowait++;
}
}
}
$koson=$dr/($dr+$re);
$mati=($drop+$receive-$nowait)/($drop+$receive);
$ro=$ARGV[0]/$ARGV[1];
print "$ro,$koson,$mati\n";
アーランB・C式のグラフを描くために、あるキューの数に対して利用率が０～１の範囲で変化したものが必要になる。それを、シェルスクリプトによる繰り返し処理で行う。プログラムの実行時に、コマンドラインから四つの引数（開始時の生起率、終了時の生起率、終了率、キューの数）を入力する。終了率は固定で、生起率を上げていくことにより、利用率も上がっていき、それぞれの利用率の時にNS2のプログラムとPerlのプログラムを実行して、呼損率、待ち率を得る。その出力を「log.csv」というファイルにする。プログラム名を「mm1k.sh」とすると、使用例は、
sh mm1k.sh 1 59 60 5 >log.csv
というようになる。シェルスクリプトによるプログラムを以下に示す。
mm1k.sh
count=$1
while [ $count -le $2 ];
do
usr/bin/ns mm1k.tcl ${count}.0 ${3}.0 $4
perl mm1k.pl $count $3
count=`expr $count + 1`
done
アーランBの理論値は、アーランC式の理論値は
で計算して、Microsoft Office Excel 2003で図８のようにした。これと実験値をグラフにすると、図９、図１０のようになった。
アーランB式のグラフは、実験値と理論値はほぼ等しい。アーランC式のグラフは、利用率が上がるにつれて誤差が少し見られるものの、最も誤差が大きい場所でも誤差率は約０．５％なので実験値と理論値はほぼ等しいと言える。
待ち行列理論において呼損率・待ち率の計算は、式が複雑で難解なものが多い。しかし、NS2を用いたシミュレーションプログラムを作り、そのシミュレーション結果を解析することにより、呼損率・待ち率を容易に得られることがわかった。また、この手法を応用すれば、ルータの呼損率・待ち率の解析も可能であり、実用性はある。
次は、待ち行列モデルで窓口が複数のものの解析に挑戦したい。
mm1k.tcl
set lambda [lindex $argv 0]
set mu [lindex $argv 1]
set qsize [lindex $argv 2]
set ns [new Simulator]
set tf [open out.tr w]
$ns trace-all $tf
set n1 [$ns node]
set n2 [$ns node]
set link [$ns simplex-link $n1 $n2 100kb 0ms DropTail]
$ns queue-limit $n1 $n2 $qsize
set InterArrivalTime [new RandomVariable/Exponential]
$InterArrivalTime set avg_ [expr 1/$lambda]
set pktSize [new RandomVariable/Exponential]
$pktSize set avg_ [expr 100000.0/(8*$mu)]
set src [new Agent/UDP]
$ns attach-agent $n1 $src
set qmon [$ns monitor-queue $n1 $n2 [open qm.out w] 0.1]
$link queue-sample-timeout
proc finish {} {
global ns tf
$ns flush-trace
close $tf
exit 0
}
proc sendpacket {} {
global ns src InterArrivalTime pktSize
set time [$ns now]
$ns at [expr $time + [$InterArrivalTime value]] "sendpacket"
set bytes [expr round ([$pktSize value])]
$src send $bytes
}
set sink [new Agent/Null]
$ns attach-agent $n2 $sink
$ns connect $src $sink
$ns at 0.0001 "sendpacket"
$ns at 1000.0 "finish"
$ns run
mm1k.pl
open(IN, 'out.tr');
@temp = <IN>;
@plus;
@minus;
$receive=0;
$drop=0;
foreach $n1 (@temp){
chomp;
@d1 = split(/ /,$n1);
if($d1[0] eq '+'){
$plus[$d1[11]] = $d1[1];
}
elsif($d1[0] eq '-'){
$minus[$d1[11]] = $d1[1];
}
elsif($d1[0] eq 'r'){
$receive++;
}
elsif($d1[0] eq 'd'){
$drop++;
}
}
$i = 0;
$nowait = 0;
for ($i=0;$i<=$#minus;$i++){
if (defined($minus[$i])){
if ($minus[$i] == $plus[$i]){
$nowait++;
}
}
}
$koson=$dr/($dr+$re);
$mati=($drop+$receive-$nowait)/($drop+$receive);
$ro=$ARGV[0]/$ARGV[1];
print "$ro,$koson,$mati\n";
mm1k.sh
count=$1
while [ $count -le $2 ];
do
usr/bin/ns mm1k.tcl ${count}.0 ${3}.0 $4
perl mm1k.pl $count $3
count=`expr $count + 1`
done