日本オペレーションズ。リサーチ学会 2005年春季研究発表会
周一6−2
制限型プ：＝セッサシェアリングモデルについて
01009830 駒澤大学 小沢利久 OZAWATbshihisa mpsモデル【2】：サーバー能力の配分率にクラス依存 の制限（上限）があるモデルのことで，た＝1，…，〝に 対して， 1． はじめに TCP／IPに代表されるパケット通信では，リンクな どの共通リソースを複数のコネクション（ユーザー）で シェアしながら利用しているが，そのような仕組みはひ とつのリソースに注目し，適当な時間スケールでの平均 的な挙動を考えることでプロセッサシェアリングモデル （PSモデル）のバリエーションとして近似的に表すこと ができる【2，3，4トその中のひとつに制限型PSモデル （LPSモデル）〔21がある・これは，客にクラスを設け， クラス毎にサーバー能力割り当て（配分率）の上限値を 設定するPSモデルである．パケット通信ではその上限 値が，例えばアクセスラインの帯域に相当する．よって， クラス（上限値）を変更したときに平均ファイル転送時 間などの通信性能がどのように改善（悪化）するのかは， クラス所属の選択権を持つ客にとって蒐要な関心事とな る．そこで本報告では，LPSモデルについて，配分率の 上限値の変更が性能に及ぼす影響を考察する1． 2．mpSモデル 2．1．複数クラスpSモデル ここでは複数クラスPSモデルを広く次のように定義 する．まず，客のクラス数を∬とし，クラスたの時点 壬での系内客数をズ〆り，そのベクトルを∬（りとする・ サーバーが単位時間に提供可能なサービス時間を1と し，クラスたの客一人当りへのサーバー能力の瞬間的な 配分率を7た（∬（り），そのベクトルを7（∬（り）で与える・ ここで，7た（∬（f））≧0，71（∬（り）＋…＋7〝（∬（り）≦1 とする・このとき，クラスたのある客が時間区間【0，f】 で受けたサービスの竜はかた（g（β））dβで与えられる・ 2．2．ⅢPSモデルとmpSモデル ここでは代表的なPSモデルであるDiscriminatory PS（DPS）モデルとLPSモデルについて示す． のpSモデル【5】‥配分にクラス依存の重みを考慮した PSモデルのことで， 7パ諾）＝飢／（飢諾），た＝1，…，∬・ ここで，諾＝（ェ1 ，…，笹〝），鋸はクラスたの重みでgはそ のベクトル，（g，ご）は内積である．飢＝COれβf．の場合が 標準的なPSモデルであり，Egali七a最am】PS岬pS）モ デルと呼ばれ，7パ昔）＝1／瞳Ilとなる．ここで，瞳】l＝ 霊1＋…＋エ〝である．〈γた，
▼￣ 7た（諾）＝min −ma）（ 「．こ 1≦j≦り酬一∑崇薫
ここで，0＜γた≦1はクラスたの配分率の上限（上限配 分率）であり，γ1≦γ2≦…≦r〝とする．LPSモデル はmax−min公平性（最小の配分率を最大にする）に従う． 制限値がクラスに依存しないLPSモデル（γた＝CO†lβ壬・） をhLPSモデルと呼ぶことにする． 3．mPSモデルの解析（数値計算） クラスたの客は強度入たのポアソン過程に従って到着 し，サービス時間は平均1／仰の一一一一般分布に従うとする・ EPSモデルとhLPSモデルは対称待ち行列であり，系 内客数の定常分布は横形式解によって表すことができる 【3］．しかし，DPSモデルとLPSモデルは対称待ち行列 の性質を満たさないため，系内客数の定常分布を簡単な 式で表すことはできない．DPSモデルについては，同 時にサービスを受けているクラスたとクラスJの客の配 分率の比が状態に依存せず常に鋸／別であることを利用 して平均応答時間を求めることができるが【1】，LPSで はそのような単純な関係は成り立たない． そこで，サービス時間を指数分布として，マルコフ連 鎖（∬（り）の定常分布を数値計算によって求めることに する．数値計算の方法は様々考えられるが，ここでは以 下の方法を用いる． 。まず，レベル乃を￡れ＝（霊∈Zf：l匝‖＝れ） で与える．このレベル分けを基にして推移速度行 列￠をブロック行列化する．するとQは非均質 な（nonhomogeneous）ブロック3重対角行列となる （（X（t））はnonhomogeneousQBDになる）・この Qに対して縮約／非縮約法を適用して定常分布を 数値的に求める． 0ただし，￠は無限次元なので，適当なレベル以上で はレベル内での分布（条件付き分布）が多項分布に 従うとして有限次元に落とす．これは，が＝「1／rll として，LPSモデルではレベルが以上での状態推 移率がEPSモデルでのそれと同じになることから， 適当なレベル以上ではレベル内での分布がEPSモ デルでのそれと十分近いという仮定に基づく． この方法では，￠のブロック対角成分が対角行列とな 1この報告の内容はNTT研究所の川原亮一氏と石橋圭介氏とのコ ミュニケーションが切っ掛けとなっており，ベースとなっている． −48 − © 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.り，非対角成分も階層的な構造を持つ．また，縮約され たマルコフ連鎖は出生死滅過程になる．しかし，やはり 次元との関係で大きなモデルに適用するは困難である． 4．数値例 クラス数が∬＝2の場合について，一方が上限配分 率を増加させた場合の平均応答時間lγ七，た＝1，2，の変 化について調べる．どの数値例も〃1＝〃2＝1とした． 表1は両クラスの到着率が等しい場合に，γ2または γ1を増加させていったときの平均応答時間である．こ れらの表から， ●γ2を増加させてもⅥ1はあまり変化しない， ●γ1を増加させてもl鳩はあまり変化しない， ことが分かる．このことから，LPSモデルではあるクラ スの上限配分率の変化はその他のクラスにはあまり影響 しないことが予想される．また， ・γ2を増加させるとl仇，l鳩 とも単調に減少して いる， ●γ1を増加させるとⅣ1は単調に減少するが，l鳩は 増加の後，減少する， ことより，あるクラスが上限配分率を増加させると他の クラスの平均応答時間も減る可能性があることを示して いる．これについては次節で取り上げる． 表2■は両クラスの到着率が異なる場合に，γ2またはγ1 を増加させていったときの平均応答時間である．比較の ために到着率が等しい場合の数値例も示す．表より，両ク ラスの到着率が異なる場合もそれらが等しい場合と同様 の数値的傾向を示していることが分かる．ところで，表 2は，入1＝入2＝0．4であったものを入1＝0．1，入2＝0．7 に変えた場合の比較も示している．これは，クラス1の トラヒックを一部分，クラス2へ移したことを意味する が，そのような移行をしても平均応答時間はあまり変化 しないことが分かる．パケット通信でいえば，より広い アクセス帯域のサービスに多くの人が移行したときの状 況に対応する． 以上に示したことは文献［2】でもシミュレーションに よって確認されている． 5．考察 数値例で示したことに関連し，サンプルパスの議論を 用いて次が成立することが分かる． ● 一一一般の到着過程，一般のサービス時間分布，一般の クラス数∬であるエルゴード的なLPSモデルに おいて，最上位クラスの上限配分率γ〝を増加させ ると系内客数の定常分布は確率順序の意味で単調非 増加となる． このことより，平均系内客数及びリトルの式から平均応 時間についても同様の単調性が成り立つことが分かる． ところで，LPSモデルについて数値例で示したよう に，あるクラスの上限配分率の変化がその他のクラスに あまり影響を与えないことが確かであれば，平均応答時 間を近似するひとつの方法が導かれる．すなわち，クラ スたを注目するクラスとし，そのクラス以外のクラスの 上限配分率を全てγたにしたhLPSモデルを構成し，そ のモデルにおけるクラスたの平均応答時間をⅣたの近 似として用いるのである．文献【2］で提案された近似式 はこのようにして構成された近似式と解釈することもで きる． 6．おわりに 数値例から予想される性質がどこまで正確に成り立つ かの確認をこれからの課題としたい． 参考文献
【l］G・Fayolle andI・Mitrani，Sharing aprocessor among
manyjobclasses，J．ofACM27（3）（1980）・
【2】早・KチWahara，etal・，Amethodofbandwidthdimen−
SlOnlng and management for aggregated TCP nows
withheterogeneousaccess，Submitted（2004）・ 【3】小沢利久，プロセッサシェアリングモデルを用いた通信応 答時間の近似解析，信学技報NS2002−12（2002）． 【4】J・W・RobertsandL・Massouli6，Bandwidthsharingand admissioncontrolfbrelastictrafBc，11thITCSpecial− istSeminar（1998）． 【5】S・F・Yashkov，Proc讐SOr−Sharingqueues‥SOmeprOgreSS inanalysis，QueuelngSyStemS2（1987）・ 表1：平均応答時間：到着率が等しい場合
