P2P 型ストリーミング配信における課金モデルの提案

(1)

卒業研究論文

P2P

型ストリーミング配信における課金モデルの提案

学籍番号 00D8101036H 藤村浩俊

中央大学理工学部情報工学科田口研究室 2004 3

(2)

あらまし

本研究では，P2P型ストリーミング配信において各サーバントが抱えられる最大クライアント数やサーバへの貢献度を考慮した配信ツリー構築のアルゴリズムを考える．また，

そのアルゴリズムを用いた課金モデルを提案し，計算機上で実験を行う．

キーワード P2P，ストリーミング配信，課金モデル，根付き木

(3)

近年，インターネットの急速な技術の発展と社会への普及に伴い，インターネット上でさまざまなコンテンツが公開されている．また，そのコンテンツを公開，獲得する技術が開発されている．その中でも，動画や音楽を配信する手段としてストリーミング配信が挙げられる．ストリーミング配信は，サーバへ直接繋ぎ，サービスを提供する．サーバの回線帯域によって，配信を受けられる人数は決まっているため，多数の人が利用するためには，より太い回線が必要となる．回線帯域を太くするためには，莫大な費用がかかり，有料コンテンツでは，料金設定を高くせざるをえない．

本研究では，ストリーミング配信における P2P の有効性を考える．そして，受信するコンピュータの負荷軽減を考慮した配信ツリー構築のアルゴリズムを考え，それに合う課金モデル提案を行う．

(5)

第

2

章

従来の課金方法

２．１一般的な課金モデル

現在，適用されている主な課金モデルには，定額制課金モデル，従量制課金モデル，

定額従量制課金モデルがある．

定額課金モデルとは，「月額 3000 円」などのように，一定期間内に一定金額で無制限にアクセスできる方式である．

従量課金モデルとは，「3分10円」などのように，利用時間の長さに応じて課金される料金体系である．

定額従量課金モデルとは，「30 時間まで3000円，それ以降は3分 10円」といったように，基本料金に一定の金額を含み，超過した部分について従量で追加料金を課金される料金体系のことである．インターネットサービスプロバイダの接続料金や，携帯電話の通話料などがこのような料金体系を利用している．

同じように定額制と従量制を組み合わせた料金体制に，キャップ制がある．これは，一定時間に満たない利用については従量制もしくは定額従量制を採用し，一定時間以上の利用についてはそれ以上いくら利用しても常に一定料金を課金するモデルである．

２．２ストリーミングに適応する際の問題点

現在，ストリーミング配信に適応されている課金モデルには，定額制，従量制課金モデルがある．しかし，定額課金制では約 80％，従量課金制では人気の高いライブ，ビデオ配信でも約60％の人が，料金を500円以下に抑えたいと考えている．このためには，サービスを提供する配信サーバの費用削減，ユーザーに対する割引制度を整える必要がある．

(6)

第

3

章

ストリーミングと

P2P

システム

ストリーミングとは，インターネットなどのネットワークを通じて映像や音声などのマルチメディアデータを視聴する際に，データを受信しながら同時に再生を行う方式である．一般にクライアントサーバシステムにより配信されることが多い．

３．１ストリーミングの形式

ストリーミングには大きく分けて二種類あると考えられている．ストリーミングファイルへの変換作業をした後に，ウェブサーバに置いてストリーミングファイルを配信する方式と，ストリーミングサーバに置いてストリーミングファイルを配信する方式である．

３．２ウェブサーバによる配信

ウェブサーバとはそもそも，HTML ファイルや画像などをクライアントにダウンロードさせることが目的である．そのため，ウェブサーバでは「TCP」というプロトコルが利用されている．当然ウェブサーバにあるストリーミングファイルを見ようとするとこのTCPプロトコルが使用されるが，このプロトコルは「クライアントと対話を行いながら」ストリーミングを配信するので，配信されている動画は途中で止まったり，動いたりを繰り返すことが多々ある．また，当然この配信方法では，ファイルサイズが大きいほど，つまり，動画の画面サイズが大きく，再生時間が長いほど，停止時間は長くなり，再生されるまでの待ち時間が相当長くなる．これは，ウェブサーバにおけるストリーミング配信においては必ずファイルを「ダウンロード」しなければならないからである．当然この方法ではライブ中継などはできない．また，ダウンロードされてしまうということは，ストリーミング配信者側にしてみれば簡単にその動画ファイルを保存できてしまうということである．

(7)

したがって，"STREAMING"の本来の意味である「流れる」という意味から考えると，上記のように「ダウンロードしながら再生する」ウェブサーバを利用したストリーミングはもはや「ストリーミング」とは言えない．

３．３ストリーミングサーバによる配信

ウェブサーバにおいては，ＴＣＰという「クライアントと対話（送受信）をしながら」

ファイル情報を送信するプロトコルを使用したが，ストリーミングサーバにおいては UDP というプロトコルを利用して送信のみに特化した配信を行うことができる．そのため動画のデータは文字通り流れるようにクライアントに配信され，再生まで何十秒も何分も待つということはなくなる．なぜなら，このストリーミングサーバによる配信はダウンロードを用いていないことがその理由として挙げられる．また，ダウンロードを用いないということは，ファイルが勝手に保存されて転用されることもなくなり，ライブ中継の映像を半永久的に流すこともできるということを意味する．

この，ストリーミングサーバによるストリーミングこそ本来の「ストリーミング」であり，商業用に動画を配信するのであればストリーミングサーバを利用するのは不可避な選択といえる．

３．４ P2Pシステム

P2P(Peer to Peer)システムはクライアントサーバシステムのような分散処理型のシステム形態である．これは，サーバ(Server)のみに負荷が集中するシステムとは違い，クライアント(Client)間で完結できる処理をサーバを介さずに行うことができる．ピア (peer)とは対等な関係という意味であり，構成するコンピュータ同士が対等に処理を行う．クライアントサーバシステムは処理を要求し結果を受け取るコンピュータがクライアントと呼ばれ，要求を受けて処理結果を返すコンピュータをサーバと呼ぶ．P2Pシステムではすべてのコンピュータがサーバ，クライアントの機能を持つためサーバント (Servent)と呼ばれる．

P2Pシステムには以下の２つのシステム形態がある．

(8)

３．４．１ Pure型 P2Pシステム

Pure型P2Pシステムとは，全ての完全に対等であるシステムである．すべてのコンピュータがサーバントとしてまったく同一の機能をもっている．情報の蓄積は情報の発生源であるサーバントで行い，情報の提供もそのサーバントが行う．

図１：Pure型P2Pシステム

３．４．２ Hybrid型P2Pシステム

Hybrid型P2Pシステムとは，サーバと複数のサーバントで構成されるシステム形態である．システムの中心にサーバがある点ではクライアントサーバシステムと似ているが，

サーバ以外のコンピュータが要求を送受信するサーバントであることが相違点として挙げられる．情報の蓄積は，情報の発生源であるサーバントで行い，情報の提供もそのサーバントが行う．サーバはサーバント間の処理を円滑に行うための情報を提供する．

たとえば，サーバが「どこのサーバントにどんな情報があるか」という情報を提供することで，サーバントは情報の検索を簡単に行うことができる．

(9)

図2：Hybrid型システム

３．５ P2Pストリーミング

P2P ストリーミングは，P2P 技術を応用してストリーミング配信を行う．一般に言われているストリーミング配信では，クライアントサーバシステムで行われており，その場合，受信する側はすべてサーバからのデータを直接受信する．当然ながら，サーバから流れるデータ量は，n人を相手にする場合，n倍となる．このとき，サーバ側には人数や帯域の制限があるので，接続する人数が増えるにつれて回線が混雑し，接続できなくなるという現象が起こる．

一方 P2P ストリーミングでは，各受信者がサーバとしての機能を有するため，サーバに過剰な負担をかけずに多数の受信者を抱えることができる．接続数が多くなるほど，

接続先の数も増えるが，その分多くのサーバントを経由していくことになるので，クライアントサーバシステムよりも接続が不安定になる．また，受信する側もサーバと同じように配信するので，受信側の上り帯域が確保されている必要がある．

(10)

第

4

章根付き木

根と呼ばれる１個の特別視された点をもつ木を根付き木という．根付き木において，

点は通常ノードと呼ばれる．根から各ノードvへのパスは１個ずつあり，そのパスに沿う直前のノードwをの親といい，v w=p(v)と表す．をの子という．ノードから根へのパス上にあるノードをの祖先という．またノードの子孫は，ノードから子を次々とたどって到達できるノードである．子をもたないノードを外点という．

v w v

v v v

根付き木におけるノードvの深さdepth(v)は，

⎩⎨

⎧

= +

1 )) ( ( ) 0

(v depth p v

depth

) (

それ以外のときが根のとき v

で定義される．また，根付き木におけるノードvの高さheight(v)は，

⎩⎨

⎧

+

= =

1 } ) (

| ) ( max{

) 0

(v height w p w v

height

) (

それ以外のときが葉のとき v

で定義される．根付き木の高さは根rの高さと定義し，根付き木の深さは，木に含まれるノードの最大の深さと定義する．そのとき，根付き木の深さと高さは一致する．

(11)

第

5

章

配信ツリーの構築

５．１配信ツリーの構成

サーバを根，サーバントをノードとして，サーバントの情報を元に配信ツリーの構築を行うアルゴリズムを考える．サーバは最大接続可能サーバント数，サーバント接続優先度の情報を持つとする．最大接続可能サーバント数は，根もしくはノードに接続できる最大の数を表す．サーバント接続優先度は，他ノードと比較し，値が大きいものに優先して接続することを表す．サーバントvは次のような情報を持つ．

• 最大接続可能サーバント数 m

• 現在接続しているサーバント数 n

• 接続時間 t

• 志向度 r

• 貢献度 W

• 接続優先度 l

• 配信サーバからの深さ depth(v)

接続時間は，配信ツリーへ参加した時間を表す．志向度は，他サーバントへの配信を極力避け，自分のコンピュータの負荷軽減を優先する安定志向と，他サーバントへの配信を積極的に行い，サーバの負荷軽減を優先するサーバ貢献志向の2種類とする．安定志向は0，サーバ貢献志向は1とおく．貢献度Wは単位時間ごとの接続サーバント数，

つまり，

∑=

= ^t

i

ni

W

0

と表す．接続優先度l^は，

( )

( )^v

depth tr n m

l m −

=

(12)

と表す．図5.1に配信ツリー例を示す．左の数値は各サーバントの接続最大サーバント数である．

図5.1 配信ツリー例(左の数値は最大接続サーバント数)

５．２サーバントの追加

サーバントを配信ツリーへ追加する場合，接続優先度によって接続先を決定する．配信ツリーに参加しているサーバントの中で，現在接続しているサーバント数が，最大接続可能サーバント数より少ないサーバントが存在する場合，新規サーバントは接続優先度の最も高いサーバントへ追加される．また，そのようなサーバントが存在しない場合，

サーバへ直接追加する．

追加の例として，図5.2のような配信ツリーを示す．今，このツリーへサーバントを追加すると仮定する．ここで，各サーバントの接続優先度は，表5.2のようになる．

表5.2：各サーバントの接続優先度

(13)

サーバント A B C D E F G H

接続優先度 3 5 0 4 7 8 0 0

図5.2：配信ツリー例

よって，最も接続優先度の高いサーバントは F なので，そこへ追加される．追加後の配信ツリーは図5.3のようになる．

図5.3：サーバント追加後の配信ツリー

(14)

５．３サーバントの離脱

サーバントが配信ツリーから離脱するとき，離脱するサーバントが子をもっていないならば，そのまま離脱する．子をもっているならば，離脱するサーバントの親へ接続する．このとき，親に接続しているサーバント数が最大接続可能サーバント数となっているとき，深さが大きく，最大接続可能サーバント数と，現在接続しているサーバントの数の差が最大となるようなサーバントへ子を接続する．

図5.4：配信ツリー例

離脱の例として，図5.4のような配信ツリーを示す．今，サーバントIが配信ツリーから離脱すると仮定する．このとき，サーバントIはサーバント L，サーバントMをもっているので，サーバントCへ接続する．Iが離脱した後，Cの最大接続可能サーバント数と現在接続しているサーバント数の差は3なので，Iの子L，MはCへ接続される．離脱後の配信ツリーは図5.5のようになる．

次に，図5.5 からサーバント Fがすると仮定する．このときサーバントF はサーバントJ，サーバントKをもっているので，サーバントBへ接続する．しかしBの最大接続可能サーバント数は1より，２つのサーバントを持つことができない．したがってこのツリーで最も深さが大きいのは，D，E，G，H，L，M のサーバントであるから，

この6つのサーバントについてサーバント接続優先度を求める．ここで各サーバントの接続優先度は表5.2のようになる．

(15)

図5.5：サーバントI離脱後の配信ツリー

表5.2：各サーバントの接続優先度

サーバント D E G H L M

接続優先度 0 0 2 0 0 4

表 5.2より，接続優先度が最も高いのはMなので，Kをそこへ接続する．サーバントFが離脱した後の配信ツリーは図5.6のようになる．

(16)

図5.6：サーバントF離脱後の配信ツリー

第

6

章

課金モデルの提案

第５章において提案した配信ツリー構築のアルゴリズムを用いて，課金モデルの提案を行う．

サーバに対する負荷を下げ，多くの人へ配信することを目的とすると，サーバに接続したサーバントが，できるだけ多くの人へ配信することが望ましい．そのため，多くの子をもち，配信ツリーへ長く接続しているサーバントの割引率が高くなる課金モデルを提案する．これはサーバへの負荷軽減を第一に考えたモデルであり，安定志向のサーバントには，割引サービスの対象とならない．

まず，接続する全サーバントに対して，一律の金額を課金する．そして各サーバントの通信時間に対するサーバ貢献度から割引率を計算し，一律に課金した金額を割引することとする．このとき割引率は，

10 通信時間

貢献度 ×

として計算する．

(17)

(18)

第７章

計算機実験

７．１実験手法

提案した課金モデルを用いて計算機実験を行う．サーバの最大接続可能サーバント数を10000，サーバント接続優先度を0とする．配信時間を3600秒とし，サーバントは単位時間あたりの到着率0.3のポアソン分布に従って到着するものとする．また，サーバントは単位時間あたり0.01 の確率で離脱するものとする．到着したサーバントに接続可能な最大クライアント数は 0〜9 台とし，その確率は等確率とする．また志向度も等確率で与えられるものとする．サーバ貢献度は，接続している各クライアントの接続時間の総和とし，サーバント接続優先度は，最大接続可能サーバント数から現時点で接続しているサーバント数を差し引いたたものとする．

７．２実験結果

実験結果から，接続可能な最大クライアントの数ごとに算出した，台数，(貢献度／

通信時間)の平均値，最大，最小を表7.1に示す．

表7.1：実験結果

標本数平均値最小最大総合 525 2.02168 0 27.67521

9 53 5.721449 4.040179 9 8 52 5.090972 2 19.06838

7 47 4.14769 2.115063 27.67521

6 61 2.715238 0 6

5 44 2.166707 0.697183 11.73882

4 60 1.001469 0 5.41181

3 58 0.214359 0 3

2 46 0.151964 0 2

1 55 0.054499 0 1

(19)

表7.1から

サーバ貢献志向のサーバントにおける最大サーバント数と割引率の関係を図 2 に示す．図2から最大クライアント数が多いほど，割引率が高いことがわかる．最大クライアント数が9のサーバントの場合，平均して6割近くの割引を受けることができる．逆に最大クライアント数が3以下の場合，割引はほとんど行われない．これは同じ最大クライアント数をもつサーバントの合計にほぼ差がないためと考えられる．

図7.1：サーバントの割引率

(20)

第

8

章おわりに

８．１まとめ

本研究では，P2Pストリーミングの有効性を挙げ，サーバントの最大接続サーバント数とサーバントごとの志向度を考慮した配信ツリーの構築を行った．この配信ツリーを用いた課金モデルを提案した．

８．２今後の課題

本研究では，サーバントがもつ情報の相違によって，配信ツリーへ追加する確率に変化はなく全て一定であった．しかし，実社会において，コンピュータの性能の違いにかかわらず，所持台数が変わるため，実用的とはいえない．そこで，サーバントがもつ情報によって，到着確率を変えて実験を行うことで，より現実的な結果が得られると思われる．また，サーバントが配信ツリーへ追加するとき，すでに配信ツリーへ参加している，性能の低いサーバントへ優先して追加することで，より効率的な課金モデルになると思われる．

(21)

謝辞

本研究を進めるにあたり，御指導御助言を頂きました，中央大学理工学部情報工学科の田口東教授，鳥海重喜氏には，心より感謝致します．また田口研究室の院生の方々，

研究室の仲間達に感謝の意を表します．

(22)

参考文献

[1] 浅野孝夫，今井浩，“計算とアルゴリズム，”オーム社，2000． [2] 浅野孝夫，“情報の構造[上]，”日本評論社，1994．

[3] 伊藤直樹，“P2Pコンピューティング，”ソフト・リサーチ・センター，2001． [4] 仲山昌宏，“オーバーレイネットワークの最適化手法の提案, ”慶応義塾大学卒業

論文，2002．

[5] 仲山昌宏，“ネットワークとノード情報を利用したオーバーレイネットワークの最適化，”慶應義塾大学情報学部卒業論文，2003．

[6] 数字で語るストリーミング，http://www.stream.co.jp/mailnews/data/．

P2P 型ストリーミング配信における課金モデルの提案

型ストリーミング配信における課金モデルの提案

あらまし

目次

第

章

はじめに

第