研究計画書

信頼性マルチキャストデータ配送システムのための

ツリー構造構築アルゴリズムの設計と実装

慶應義塾大学大学院　政策メディア研究科修士課程2年

氏名:________________

1999年11月1日

Abstract

　本研究では、信頼性のあるマルチキャストデータ配送システムが複雑なネットワーク・トポロジー上で効率よく動作するための、ツリー構造構築アルゴリズムの設計と実装を行う。

現在のインターネットにおいて、信頼性を保証するマルチキャストを使用した効率的なデータ配送システムに対する要求は、非常に高い。しかし、既存の信頼性マルチキャストを利用したデータ配送システムは、大規模性に欠ける、アーカイブの配送には信頼性が不足している、といった欠点があり、実用的ではない。

これらの欠点を改善し効率よくマルチキャストデータ配送を行う手法として、ネットワークをローカルセグメントに分割しマルチキャストデータ配送を行う手法がある。この手法では、広帯域から狭帯域へセグメントがツリー構造を形成している必要がある。しかし、現実のネットワークでは必ずしもトポロジーが理想的なツリー構造を持っているわけではない。また、既存のマルチキャストのためのツリー構造構築のアルゴリズムは、回線の帯域を考慮しないため、前述の手法のためのツリー構造として不適である。

本研究では、複雑なトポロジーを持つ実際のネットワーク上で、前述の手法が有効に働くようなツリー構造を形成するためのアルゴリズムを設計、実装し、インターネット上で信頼性のある効率的なデータ配送システムを完成する。

キーワード

インターネット　信頼性マルチキャスト　データ配信システム

１．背景

現在、インターネットは一般によく普及し、多くの人々にとってなくてはならない情報インフラストラクチャーとして発展している。このためユーザ数も増加の一途であり、またマルチメディア技術が非常に発展してきていることから、インターネット上を流れるデータの量も、級数的に増加している。昨今ではインターネットに使用する回線の帯域も広帯域化が進んでいるが、エンドユーザがストレスなく非常に大きなマルチメディア・データを取り扱えるには、まだ時間がかかる。

こうした現状から、ネットワーク上で効率よくデータを配信するシステムに対する要求が高まっている。

ネットワーク上でデータを配信する際に問題となるのが、データ配送の信頼性である。映像や音声のリアルタイム中継などの一過性・再利用なしのデータであれば、完全な信頼性は要求されず、代わりに実時間性が要求される。これに対して、デジタルコンテンツをネットワークを使って配信する場合や、会議・講義等のマテリアルの共有には、信頼性の保証が強く要求される。

ネットワーク上でデータを広範囲に配送する手法として、マルチキャスト通信がある。特に、信頼性の保証が必要な通信に対して使用する、信頼性マルチキャスト通信が研究され、これが注目を浴びている。

しかし、現状の信頼性マルチキャストには、大規模性に欠ける、スループットが低い、信頼性が十分でないなどの欠点がある。

本研究では、これらの問題を解決する多段通信路ネットワーク・マルチキャストと、特に、これを効率よく使用するためのツリー構造構築アルゴリズムについての研究を行う。

２．現在のReliable Multicast の課題

本節では、既存の広域データ配送システムである Reliable Multicast の問題点について述べる。

既存のReliable Multicast には、前方誤り訂正符号を含んでデータを送信するもの(FEC方式)と、データ配送に再送処理を含むものがある。

２．１．前方誤り訂正方式の問題点

前方誤り訂正符号を含んだデータを送信する方式では、データを送信する際、誤り訂正符号をデータに付加し、データに冗長性を持たせる。このデータを受信した受信者は、データ中に誤りが発見された場合は、誤り訂正符号を利用してある程度のデータ回復を自力で行うことができる。

この方式では、データの誤りが発見された場合、誤り訂正符号で訂正できる範囲内であれば、再送等を行うことなしにデータを回復できるので、複雑な再送処理が不要となる。

しかし、誤り訂正符号の訂正できる範囲を超えたデータの誤りや、データ・パケットそのものの欠落は回復することができず、アーカイブの配信には信頼性に欠ける。

２．２．再送処理方式の問題点

再送処理を行う方式では、データを受信した受信者がデータの誤り、欠落を発見した場合に、そのデータの再送を要求し、これによってデータ配送の信頼性を提供する。

この方式では、end-to-endでのデータ配送の信頼性が確保される。

しかし、現在提案されているアルゴリズムでは、ネットワーク上に広帯域回線に接続された受信者と狭帯域回線に接続された受信者が混在する場合、狭帯域回線上の受信者にシステム全体の転送速度が影響を受け、広帯域回線上に接続された受信者が帯域を有効に活用することができない。

再送処理のアルゴリズムは複雑で実装が困難であり、再送処理によって送信されるパケットが重複し無駄なデータが多く送信される、という問題点がある。

また、データの送信元から再送処理を行うために、大規模性に欠ける。

２．３．既存のReliable Multicastの問題点のまとめ

上述のように、既存のReliable Multicast によるデータ配信は、以下の点で、現在の要求に対して十分でない。

・信頼性に欠ける

・全体の処理が狭帯域回線に影響される

・アルゴリズムが複雑で実装が困難

・大規模性に欠ける

　ネットワーク上で効率よくデータの配布を行う、という要求に応えるためには、これらの問題点を克服し、信頼性のあるマルチキャストデータ配信システムを構築しなければならない。

３．現在までの成果――Segmented Hierarchical Reliable Multicast (セグメント化階層信頼性マルチキャストデータ配送)

私は、環境情報学部在学時並びに政策メディア修士課程在学時に、一貫してインターネットについての研究を続けてきた。中でも特に、衛星回線とインターネットについての研究を行った。衛星回線がインターネット上の通信路として使用されることを想定し、既存の通信技術を衛星回線上に適合させる技術としてのUDLR(Uni-Directional Link Routing)[2][3][4]の研究を行った。また、衛星回線が広く一般の使用者へと伸張した場合に、これを有効に使用するための技術として、衛星回線を含むネットワークにおけるアドレス変換機構を用いたネットワーク・アーキテクチャ[1]について研究した。

衛星回線の特徴として、衛星回線は広域同報性、地理不偏性を持ち、マルチキャスト通信と非常に親和性が高い。インターネット上の通信路として衛星回線を用いる上で、これを有効に活用する技術として、特にマルチキャスト通信に着目し、これの研究を行った。

この中で、既存のReliable Multicast の欠点を改善し、ネットワーク上で有効に信頼性マルチキャストデータ配送を行うシステムを設計・構築した。特に、修士課程では Segmented Hierarchical Reliable Multicast（SHRM:セグメント化階層構造信頼性マルチキャストデータ配送）を設計、実装し、２．で述べた問題点のいくつかを克服した。

この詳細については、修士論文にて成果を公表する予定である。以下に、SHRMの概要と問題点について述べる。

３．１．SHRMの概要

SHRM は、既存のReliable Multicast の問題点を解決し、マルチキャストデータ配送に、信頼性と大規模性を持たせたシステムである。

SHRMは、ネットワークを、マルチキャスト可能なローカルセグメント（MLS: Multicastable Local Segment）に分割し、これらを、最も帯域の広いものを最上段とし、順次帯域の狭いものを下位段とするツリー構造とする。このツリー構造が与えられた時に、マルチキャストを利用して効率的な信頼性のあるデータ配送を実現する。ツリー構造の最上段にデータ・ソースを置き、帯域の広いものから狭いものへ、マルチキャストを用い順次データを配送してゆく。

SHRMは、以下のような特徴を持つ。

・ネットワークをMLS単位に分割し、MLS内で完結した信頼保証データ配送システムを実装

Ø 信頼性保証の責任範囲を限定することにより、ある帯域の回線内でのスループットが他の回線に影響されないシステムを構築

・ MLS間で協調し、広域なネットワーク上でデータ配送を行う

Ø 自立分散したMLS同士がMLS間接続ホストにより相互に接続される。これらMLSが協調することにより、MLS単位でのスループットを保持しつつ信頼性を持つデータ配送を行える

・強い実時間性を持つ通信を想定しない代わりに、信頼性のあるデータ配送を行う

Ø データ配送はMLS内で完結するため、複数MLS間にまたがるデータの配送について実時間性を保証しない

　SHRMのシステム概要を、図１に示す。

図１・SHRMシステム概要図

３．２．SHRMの問題点

SHRMの実装では、多段のMLSを構成するツリー構造は、予め設定されていることを想定している。SHRMでは、広帯域のMLSから順次狭帯域のMLSが階層構造を形成していなければ、十分なスループットを得ることができない。

しかし、現実のネットワークでは、必ずしも回線の帯域の広いものから狭いものへと階層構造をなしているとは限らない。また、回線で使用できる帯域は、回線の混雑状況にも左右される。

従って、SHRMを実際のネットワーク上に後広範に適用するために、SHRMが動作する基幹となるツリー構造は、現実のトポロジーや回線状態に即して動的に構成される必要がある。

現在のSHRMには、このツリー構造の動的な生成機構は含まれていない。

４．研究課題――SHRM におけるツリー構造構築の問題

本節では、本研究で行う、ネットワーク上でのSHRMを利用した信頼性マルチキャストデータ配送のためのツリー構造構築について述べる。

上述したSHRMによる手法は、マルチキャストを利用して信頼性のあるデータ配送を効率よく行うことができる。しかし、現在までに設計、実装したSHRMでは、これを有効に使用するために次のような条件を満たすがある。

・ネットワークが、MLS単位に分割されていること

・ MLSを単位とするデータ配送のツリー構造が、広帯域のものを最上位にして、順次狭帯域のものへと接続されていること

・ MLS間の接続では、上位MLSと下位MLSの間の帯域差が、著しく大きくないこと

現在までのSHRMでは、ネットワークのMLS単位への分割、MLS単位のツリーの構築は含まれていない。従って、既存のSHRMを実際のネットワーク上で有効に使用するためには、このMLS単位のネットワーク分割手法と、ツリー構造構築の手法を提供する必要がある。

マルチキャスト配送のためのツリーを構築する方法には、既存のマルチキャスト経路制御プロトコルの仕組みがある。しかし、このマルチキャスト経路制御プロトコルのツリー構造生成の仕組みでは、回線の帯域の帯域は考慮されない。このため、既存のマルチキャスト経路制御プロトコルは、上述のSHRMにおけるツリー構造には適さない。

また、既存のマルチキャスト経路制御プロトコルは、ルータ間で経路表を生成するものである。SHRMでは、ネットワークをMLS単位で管理するため、ルータを単位としたツリーが必ずしもMLSを単位としたツリーと合致しない。

これらの要求を満たすためSHRMのためのツリー構造構築は、以下の要件を満たしたものでなければならない。

・ MLSをツリー構造の単位とする

・ MLSの回線帯域をツリー構築のための情報として持つ

・回線の帯域を考慮し、広帯域から狭帯域の順に階層構造をもって接続されたツリーを生成する

本研究では、これらの要件を満たす、新しいマルチキャストデータ配信のためのツリー構造構築システム、及びプロトコルを、設計、実装する。

５．期待される成果

本研究によって期待される成果には、次のものがあげられる。

５．１．広範に適用可能なマルチキャストデータ配信システムの構築

本研究の成果をSHRMに適用することにより、実際のネットワーク上の多くの場面で使用可能な、信頼性マルチキャストデータ配信システムが構築できる。

このシステムによって、インターネットを利用した情報の共有やコンテンツの配信がより効率よく行えるようになる。

５．２．ネットワークの帯域を考慮したマルチキャスト経路制御システムの構築

本研究の成果を応用することにより、ネットワーク上の通信路の帯域を考慮した、マルチキャスト経路制御を行うことができる。

これによって、他の一般的なマルチキャスト通信においても、ネットワーク資源を有効に活用した通信が行えるようになる。

参考文献:

[1] 論文・「単一方向衛星回線を含むネットワークのためのアドレス変換機構を用いたネットワークアーキテクチャ」西田視磨,楠本博之,村井純電子情報通信学会和文論文誌B-II,pp458-467,1998年5月

[2] 卒業論文「片方向通信路を含むネットワークアーキテクチャにおける動的な仮想リンク制御機構の設計と実装」西田視磨, 1997年

[3] 論文・「Dynamic Tunnel Configuration for Network with Uni-Directional Link」 Mikiyo Nishida, Hiroyuki Kusumoto, Jun Murai, ICCC99 Technical Speech Session, 15/09/1999

[4] 1997年度WIDEプロジェクト研究報告書,p279-p299