近年、インターネットに代表されるネットワーク通信が急速に一般に普及し、音声や動画など新しい種類のデータをネットワーク経由で送受する要求が出てきている。こうしたマルチメディアデータを安定して再生するには、データ(パケット)を絶え間なく送ることが大切である。しかしながら、現状のインターネットはBest-Effort型通信であり、パケットが届かなかったりと通信が不安定であるため、この要求を満たすことは難しい。

　本研究の目的は、将来のインターネットで通信の品質保証を行うことにより安定してマルチメディアデータをリアルタイムに再生できるネットワーク環境の構築である。通信は送信元、受信先のエンドホストおよび、その間のネットワークがその構成要素であり、本研究では、エンドホストでの通信保証と中継ネットワークでの通信保証に分けて考える。ここで、エンドホストでの通信保証とはパケットを受信するホスト内でなんらかの対策を行って、末端ユーザに対する見掛け上の通信品質を上げることを意味し、中継ネットワークでの通信保証とはネットワーク自体が通信の品質保証を行ういわゆるQoSネットワークを作ることを意味する。

　エンドホストでの通信保証に関しては、従来のビデオストリーミングソフトでもやっているものはあるが、1.5Mbps程度の低帯域を想定している。今後ネットワークの高帯域化が進むにつれ、より高品質なビデオフォーマットが使われるのは必須であり、本研究では高品質なビデオフォーマットとしてDVを取り上げてユーザーへの見かけ上の通信品質を向上する方法を提案する。エンドホストでの通信品質保証を中継ネットワークから切り離したことにより、我々の提案手法は現在のBest-Effort型ネットワークにも適用可能であり、実際に動くシステムとして民生DV機器の映像をインターネット経由でリアルタイム中継するシステムを開発した。このシステムでは、パケットロスがあった時にそれを隠蔽する技術及び受信側ホストでのバッファリングによってパケット毎の遅延のゆらぎ(ジッタ)を吸収する技術によって安定したビデオ再生を実現する。

　中継ネットワークでの通信品質保証については、配送経路途中にあるルータでのパケットスケジューリングを工夫して通信品質を向上することを目標として、理論的なモデル上でオンラインアルゴリズムを検討し、スケジューリングアルゴリズムの性質について考察する。オンラインアルゴリズムの解析手法としては最適オフラインアルゴリズムとの性能を比較するcompetitivenessを用いる。この解析手法は入力に確率分布を仮定しないため、確率分布でモデル化できないがネットワークの品質を悪化させるバーストトラフィック発生時についても評価を与えられるという利点がある。特に、本論文では上記DV中継システムがジッタとパケットロスに対して対策を行なっているという特徴を踏まえて、ジッタ制御およびパケットロス防止を実現するQoSネットワークを主に研究対象とする。

　まず、ジッタについては、ルータ内にパケットをバッファリングすることにより、ジッタを吸収するオンラインアルゴリズムを検討する。既存研究ではルータ内のバッファがあふれない限り、いくらでも長くパケットをルータ内に格納できるという条件でアルゴリズムの解析を行ったものが知られているが、この仮定では通信のリアルタイム性を考慮されていない。そこで本研究では、ルータ内にパケットを保持できる時間に上限があるという条件を新規に追加して解析を行う。その結果、オンラインアルゴリズムのcompetitivenessはバッファ数よりもむしろルータ内のパケット保持時間に依存することを示す。さらに、具体的に本問題に対する最適オンラインアルゴリズムを考案し、ジッタをどれだけ吸収するかについても定量的に明らかにする。

　次に、パケットロスについて述べる。現在のネットワーク通信におけるパケットロスはルータでバッファが足りなくなるのが原因である。本論文では、ルータでオンラインスケジューラがm本のキューからパケットをスケジューリングする際に、どれだけバッファを用意すればパケットロスを防げるかを調べ、その大小でスケジューリングアルゴリズムのパケットロス防止能力を測る枠組みを提案する。少ないバッファ量でパケットロスを防ぐには最大キュー長を短くする必要があり、この新しい問題をBalanced Scheduling Problem (BSP)と呼ぶことにする。本論文では、具体的にBSPに対して、GREEDYアルゴリズムはΘ(log m)-competitiveを達成し、ほぼ最適となるのに対し、ROUND ROBINはm-competitiveとなり自明なupper boundを越えられないことを示す。従来のスケジューリング問題ではトータルの待ち時間や応答時間を最小にすることを目的とする場合が多いが、今後QoSネットワークに対して理論的な解析を行うには、BSPのようにキュー毎に性能指標をバランスさせるモデルを構築することが重要である。

　近年、インターネットが一般に普及するにつれ、ビデオや音声などのマルチメディアデータをインターネット経由でリアルタイム再生したいという要求が強まっている。しかしながら、現在のインターネットではパケットロスやジッタ(遅延のゆらぎ)などの不安定要因によりリアルタイムストリーミングの実現が困難である。本研究では、このような現状をふまえ、将来のインターネットで高品質なリアルタイムマルチメディアストリーミングを実現するために、パケットロスとジッタにどう対策すべきかをエンドホストでのエラー隠蔽アルゴリズムと中継ネットワーク上のルータでの品質保証アルゴリズムの観点から検討している。

　第2章ではDVという高品質なビデオデータフォーマットをインターネット経由でストリーミング再生を行う際のエラー隠蔽技術について述べている。DVは既存のMPEG2と比べるとデータが大容量化しており、ビデオデータエンコーディング時の圧縮率がその分低くパケットロスには強いという特徴を持っている。本研究では実際に動くDVストリーミングシステムを開発し、その中でパケットロス発生時に過去のビデオフレームの同等部分のデータを再利用するという単純なパケットロス隠蔽技術が十分効果があるということを示している。

　第3章では、ルータでパケットをバッファリングしてジッタを吸収するキューイングアルゴリズムについて理論的な解析を行なっている。従来の研究ではルータでのバッファ数に制限を付けて解析を行なった結果があるが、本研究ではストリーミングのリアルタイム性を考慮し、バッファ数の制限だけではなく、ルータにパケットが存在できる時間(Permitted Delay Timeと学位申請者は呼んでいる)が高々定数時間L以内であるという制限をつけて解析を行い、ジッタ吸収にはPermitted Delay Timeの方がバッファ数よりも重要なファクターであるという結果を得ている。オンラインアルゴリズムの評価方法としては最適オフライン解との相対比較で評価するcompetitive analysisを用いて解析を行なっており、この評価尺度で最良のオンラインアルゴリズムを提示している。さらに、本アルゴリズムがパケット到着列に対してどれだけジッタを吸収するかを定量的に解析し、その結果からルータにどれだけのバッファを用意するべきかを考察している。そして、ルータをD台多段接続した場合についても解析を行ない、提案した最良オンラインアルゴリズムが少なくとも(D-1)台のルータで〓だけジッタが吸収できることを解析的に示している。

　第4章では、ルータでm本の複数キューをスケジューリングする際のスケジューリングアルゴリズムのパケットロス防止能力を比較する枠組みをBalanced Scheduling問題(BSP)として提案し、理論的な解析結果を与えている。これはすべてのキューに同じ量のバッファを割り当てると仮定すると、スケジューリング期間中の最大キュー長が短くなるアルゴリズムが少ないメモリ量でパケットロスを防げることに着目し、スケジューリング期間中の最大キュー長でもってスケジューリングアルゴリズムのパケットロス防止能力を評価するものである。BSPは1サーバスケジューリング問題の一種であると見なせるが、従来の典型的なスケジューリング問題ではJob全体の待ち時間合計を最小化するのが目的なのに対し、BSPではキュー(Job)毎に性能指標をバランスさせようとする点が大きく異なっている。今後、インターネットの品質保証技術の必要性が増すに連れ、BSPのようにキュー毎に性能指標をバランスさせるモデルが重要になると思われる。本研究ではキュー長が最大のキューを選んでパケットを出力するGREEDYアルゴリズムが最良のスケジューリングであることを解析的に示している。BSPは最大キュー長をバランスさせる問題であるが、本研究の第5章ではキュー毎に発生する遅延をバランスさせる問題をDBSP (Delay Balanced Scheduling Problem)として提案し、その問題に対するオンラインスケジューリングアルゴリズムの能力限界を示している。

　本研究は、将来のリアルタイムマルチメディアストリーミング通信を見据えて従来にない新しいモデルを構築し理論的解析に成功している点で、今後の関連分野の研究に寄与するところ大であると認められる。また、実際に動くDVストリーミングシステムを完成させた点も、リアルタイムマルチメディアストリーミング技術の発展に貢献するところ大であると認められる。これらの点において、本論文は高く評価され、審査委員全員で,博士(理学)の学位を授与するにふさわしいと判断した。

　なお、本論文の第2章は陣崎明氏との共同研究であるが、DVストリーミングシステムのハードウェア、ファームウェアの開発は論文提出者が主体となって行なったものであり、論文提出者の寄与が十分であると判断する。