待ち行列の通信への応用
【まちぎょうれつのつうしんへのおうよう (applications of queueing theory to communication)】
概要
望ましい情報通信ネットワークを構築するには, 方式, 構成, 品質, コスト等の関係を定量的に評価分析する必要がある. 需要(トラヒック)と供給(設備数, 処理能力等)の関係により, ユーザの感じる通信品質に満足/不満足が生じる. 特に需要は時間的, 空間的に確率的に変動するものであり, 待ち行列理論が必須である. 電話の出現とともに上記の評価分析が開始され, さらに情報通信の発展が待ち行列理論の研究を促進した.
詳説
はじめに 1878年の電話機の発明からほどなくして, 電話交換の設備数に関して通信トラヒック面からの検討が始められた. その後, デンマークの電話会社の技師 アーラン(A. K. Erlang)により体系的に研究された. これが待ち行列理論の始まりといわれる. このように待ち行列理論は情報通信ネットワークの進展・革新とともに発展してきた [1]. 通信網において接続される単位, すなわち電話網における通話やパケット網におけるパケット等はトラヒックとよばれる. トラヒックの発生や継続時間は確率的に変動しており, 通信網においてそれを運ぶための回線, 交換機あるいはコンピュータなどの設備を, 大多数の利用者が満足できるサービス品質のもとでシステム設計するための理論を通信トラヒック理論という. 待ち行列理論の通信への応用とはすなわち通信トラヒック理論そのものである [2] [3].
電話交換, 電話網, ディジタル網への応用 1965年頃から交換機の制御系が蓄積プログラム制御となり, 処理能力評価あるいは処理能力を向上させる方式の考案が大きな課題であった. リアルタイム性の要求される交換機に特有の周期処理スケジュール方式に関して, 優先クラスごとの平均遅延時間の近似式が求められた [4]. ISDN (サービス総合ディジタル網) では, 性質の異なるトラヒックが同一の設備に加わる. このトラヒックを多元トラヒックとよび, マルチメディア通信網においてはさらに各所に出現する. 多元トラヒックの処理方法には即時式/待時式, 優先権待ち行列 (回線留保を含む) 等がある. パケット網や計算機は随所にバッファを設置しており, 待時式処理が基本となる. これらを評価・分析するモデルとして待ち行列ネットワークが有効である.
パケット網, データ網への応用 パケット網については, 1970年頃に, 米国でインターネットのルーツであるARPA網が活発に研究・開発された. ルーチング方式やウィンドウ制御, ACKの返送方式に関して, 遅延時間や処理量の観点から多くの研究がなされた. データ通信やLANに関するトラヒック研究も活発に展開された [5].
CSMA/CD方式に対する平衡状態を仮定した理論解析, ポーリング方式に関するモデル解析およびLANの性能評価への応用, ALOHAシステムの解析等がなされた.
ATM方式への応用 マルチメディア通信に対する通信方式として, 1980年代初め, ATM (AsynchronousTransfer Mode)方式が考案された. ATM方式では, 情報がセルという固定長の情報単位に分割されて, 網内を流れる. セルが待ち行列理論の客そのものであり, ATM方式の検討には待ち行列理論が必須である [6]. 当初, セルのヘッダによるハードウェアルーチングが注目され, バッファの設置形式を含めて通話路網が多数研究された. ビデオ情報のセルストリームはバースト的であるということで, トラヒックの入力モデルが活発に研究された. さらに, LANの長時間のトラヒックストリームが統計的に分析され, 長時間依存性, 自己相似性が指摘されている [7]. ATM方式のサービスカテゴリーとして, CBR (Constant Bit Rate), VBR (VariableBit Rate)等が提案されその標準化がなされた. 並行して, セルの統計的多重効果に関する実に多くの研究がなされ, トラヒック制御として, コネクション受付制御や使用量パラメータ制御が活発に研究された [8].
移動通信網への応用 1980年代初頭に自動車電話サービスが開始され, 1993年にディジタル方式が提供され始め, 1990年代後半急速に普及している. 移動通信方式では, 有限の無線周波数をいかに有効活用するかが最も重要であり, トラヒック理論が非常に有効な分野である. 電波強度の関係と周波数を繰り返して使用するため, 地域を比較的小さなゾーンに分けている. そこで無線チャネルの割り当て法の研究が必要となる. また, ユーザの移動のため, 位置登録信号, 通話中チャネル切り替え, 一斉呼び出し等の信号が使用される. これら運ぶ制御チャネルの動作分析に関してもトラヒック理論が使える [9].
インターネットへの応用 爆発的に成長しているインターネットは待時式処理が基本であり, その評価・分析には待ち行列理論が利用できる. たとえば, WWWで画像データを取込むと大きなデータが動く. これはテキスト情報の情報量と比較すると数桁以上も大きい. WWWの発生間隔や情報量の統計的分析をベースに, 待ち行列理論を利用して応答時間等が評価できる.
参考文献
[1] 高橋幸雄, 「待ち行列研究の変遷」, 『オペレーションズ・リサーチ』, 43 (1998), 495-502.
[2] 秋丸春夫, 川島幸之助, 『情報通信トラヒック』, 電気通信協会, 1990.
[3] 村田正幸, 宮原秀夫, 「通信トラヒック理論とその応用[I]～[VII]」, 『電子情報通信学会誌』, 77 (1994), 968-975, 1043-1051, 1249-1255, 78 (1995). 85-90, 195-202, 264-270, 482-488.
[4] 藤木正也, 「トラヒック理論の応用 5. 交換機制御系への応用」, 『電子通信学会誌』, 64 (1981), 50-58.
[5] 秋山稔, 川島幸之助, 木村丈治, 『LANのシステム設計』, オーム社, 1989.
[6] 川島幸之助, 町原文明, 高橋敬隆, 斎藤洋, 『通信トラヒック理論の基礎とマルチメディア通信網』, 電子情報通信学会, 1995.
[7] 小沢利久, 「いろいろな入力過程モデル」, 『オペレーションズ・リサーチ』, 43 (1998), 680-686.
[8] 滝根哲哉, 村田正幸, 「通信網における待ち行列 －理論の応用と課題－」, 『オペレーションズ・リサーチ』, 43 (1998), 264-271.
[9] Davide Grillo, Ronald A. Skoog, Stanley Chia and Kin K. Leung, "Teletraffic Engineering for Mobile Personal Communications in ITU-T Work: The Need to Match Practice and Theory," IEEE Personal Communications Magazine, 5 (1998), 38-58.