インターネット通信における新しいスケジューリング問題

古賀　久志  

誌名
電子情報通信学会論文誌 A   Vol.J88-A   No.4   pp.447-456
発行日: 2005/04/01
Online ISSN: 
DOI: 
Print ISSN: 0913-5707
論文種別: 招待解説論文
専門分野: 
キーワード: 
インターネット,  スケジューリング,  オンラインアルゴリズム,  競合比解析,  

本文: PDF(532.8KB)>>
論文を購入



あらまし: 
スケジューリングは工場での生産管理などで使われ，古くから重要な最適化問題として研究されてきた．しかし，インターネット通信の普及に伴い，従来のスケジューリング理論の枠組みでは取り扱われなかった新しいスケジューリング問題を解く必要がでてきている．インターネット通信におけるスケジューリングは（ 1 ）通信プロトコルやスイッチの構造をもとにした問題である，（ 2 ）将来到着するパケットが分からない状態でスケジューリングするオンライン問題である，という2点が従来のスケジューリング問題と異なる．インターネット通信におけるスケジューリング問題を，オンラインアルゴリズムの解析手法である競合度解析（competitive analysis）を用いて解析するアプローチが，近年活発であり，本論文はその動向を解説する．Competitive analysisは入力をあらかじめ知っている最適オフラインアルゴリズムとのコスト比によりオンラインアルゴリズムの性能を測る手法であり，待ち行列理論と違って入力にポアソン分布などの確率分布を仮定しない．ネットワーク通信におけるトラヒックは，ポアソン分布で表現するのが難しいことが知られており，その意味でcompetitive analysisはインターネット通信の解析に適している．