待ち行列理論を用いたPub/Subシステムの数学的・確率的モデル化・入門篇 [Pub/Sub] [Queuing theory] [Statistics]待ち行列理論を用いたPub/Subシステムの数学的・確率的モデル化・入門篇 [Pub/Sub] [Queuing theory] [Statistics]

初夏を飛ばしていきなり夏になったかのような気温変化にやられ気味な、学生の方の松浦です.
もう少し暑くなってグランフロント大阪の客足が落ち着いてきたら、世界のビール博物館へ行って一杯、というのを画策しております.

さて、今回の記事は待ち行列理論を使ったネットワークシステムのモデリングに関してです.
といいますのも、かつての私(今も多かれ少なかれ…)を含め、研究であったり開発であったりを行うに当たって、数学的・確率的・統計的な要素が難解あったり面倒であったりといった理由から,つい目を背けてしまう方が多いのでは,と思ったからです.

システムのモデル化、あるいは提案システムの有用性を示すためのシミュレーションを行うようなシーンにおいて、これらの要素と一切向き合わずに乗り切るということは不可能です.
そこで本稿では、私の研究分野を例に取りつつ、待ち行列理論を実際に使うための導入的な部分について説明します.
できるだけネットワークシステム全般に使えそうな汎用性の高そうな内容をご紹介できればと思っていますので、待ち行列だ統計だと聞いて気分が悪くなり、そっとブラウザバックしようとした方にも、お付き合いいただければ幸いです.

待ち行列の概略、あるいは数学から逃げないための身近な事例

皆さまは日頃、待ち行列理論を使われているでしょうか.
数学の講義などで M/M/1 とか G/M/c/k とか見かけたことがある方も居られるのではないかと思います.
身近なところだと、スーパーのレジの待ちに関する例などが有名かもしれません.

まず、実際のモデル化に入る前に、待ち行列とは何かということを簡単におさらいしてみましょう.Wikipedia先生を使って.
Wikipedia – 待ち行列理論
Wikipedia – ケンドールの記号
大雑把にまとめると、ある系におけるパケットの出入に着目し、その振る舞いを決定するためのパラメータを定義して、確率的に扱えるようにしたもの、といったところでしょうか.
改めてそのパラメータ(=ケンドールの記号)が持つ意味を示すと、

A/B/C/D(A:パケットの到着過程、B:サービス時間分布、C:サーバ数、D:バッファサイズ、無限大の場合は省略)

などとなります.
先のスーパーのレジを例にとると、系をスーパー,パケットをスーパー内の買い物客と考えて、
A:店内の客がレジに到着する率
B:レジ一カ所あたりのサービス率
C:レジの数
D:レジで待ちが発生したときにできる列の長さの制限

といったように考えることができるかと思います.
要は、「客一人への対応にB時間かかるレジがC台あって、レジ全体に対して客はAという頻度で到着し、全てのレジが埋まっているときはD人までなら並べます」と言っているわけです.
ここでレジの列にD人既に並んでいて、列に入れなかった客=パケットが呼損、つまりパケロスとなります.

今回は、この待ち行列理論を用いて、私の研究分野でもあるPublish/Subscribeモデルを適応したネットワークシステムのモデル化、その触りを少しだけご紹介できればと考えています.
前述の通り、本稿ではpub/subシステムを扱うとはいえ、なるべく一般的なシステムに展開しやすいような話題にするつもりです.

pub/subシステムのモデル化

さて、前置きが長くなりましたが本題に入りましょう.
今回は簡単のため、brokerモデルのpub/sub、それもpublisher, subscriber, broker各1台の環境を想定し、メッセージの配送率に着目したモデル化を行います.
対象とするシステムの構成を簡単に図示すると下記の通りです.とても単純な構成であることがわかります.
[p] ——— [b] ——— [s]

まずはメッセージの到着率とかも考えずに、兎に角シンプルにシステムのモデル化を行うための基本的なパラメータを考えてみます.
– publisherのデータ生成頻度 λ1
– brokerのサービス時間分布 μ
– broker上のsubscriptionと到着したデータの合致率 P
以上です.たった3項目ですが、これだけでシステムの挙動をある程度記述できます.
ここでは簡単のため、subscriptionは単一でありlife timeも無限大、また、publicationに関するbrokerのモデルがM/M/1で記述できるとします.即ち、brokerへの publicationの到着はマルコフ過程に従い(=publisherのデータ生成頻度は指数分布に従う)、そのサービス率は指数分布に従うというこ とです.何か特定のイベントを検知して通知するセンサなどをpublisherとして考えると、このモデルが適応できるのではないでしょうか.
brokerにおける到着率として、publisherで適当なλを決めて時刻tに従う指数乱数を生成し、何らかの閾値を超えればメッセージを生成する、とすれば良いでしょう.

つまり、いま、非常に単純化したネットワークシステムのメッセージ到着率を取り扱っているとはいえ、指数乱数を生成するだけでモデル化ができたわけです.
かなりお手軽だと納得してもらえたら幸いです.

少し実践的に

上記の例は単一のsubscriptionであり、そのlife timeも考慮していないため常に一定の配送率となります.
そこで、次のようなパラメータを導入してみます.
– subscriptionのlife time Ts
– 新規subscriptionの到着頻度 λ2
– publisherとbroker間、brokerとsubscriber間におけるメッセージのdrop率 Lp, Ls
よって、あるsubscription sが時刻Tnにおいてbroker上に存在する確率Psはλ2に関する指数乱数を時刻Tn-TsからTnまで積分し、そこにメッセージをdropしていない確率1 – Lsを乗じたものとして求められます.
これにより、時刻t – dtにおいてpublisherが何らかのデータを生成したとすると、t – dtに従うλ1の指数乱数が閾値以上であり、先のsubscriptionの存在確率にLpを乗じることで、あるpublicationに関する配送確率 が求められます.
この試行をシステム時間に関して実行し、あとは、
実際にsubscriberまで配送されたpublication数 / 生成された全publication数
をメッセージの配送率として求めることができます.

まとめ

上記試行を何度か繰り返し、その平均を取れば、信頼度の高いメッセージ配送確率としてデータを示すことができるかと思います.
この節の例も、subscriptionの種類などを考慮しておらず、また、各ノードが1台ずつと単純なため、この例を直接何らかのシステムに適応することは難しいかと思われますが、思っていた以上に簡単な手順でモデル化できたと感じていただけたのではないでしょうか.
「どんなデータが、どんな確率で、どこに存在していて、そのデータを求めている人までメッセージがfailすることなく届く確率がどれくらいか」を念頭に置けば、今回のようなメッセージ配送率に関するモデル化は可能です.

Masanao MATSUURA