Tit-for-Tat型P2Pファイル配信の間接的制御方式

小川夏輝 (1451030)


大容量のファイルをサーバから多数のユーザに迅速に配信する際には,Peer-to-Peer (P2P) ファイル配信システムが有効である. ユーザ端末(ピア)はファイルの断片(ピース)をサーバや他のピアから取得する. ピアが取得したピースを協力的に他のピアに送信することでシステムの配信性能が高まる一方,ピースの取得のみを行うピア (フリーライダー) が増加すると配信性能が低下する問題がある. P2Pファイル配信システムの一つであるBitTorrentでは,ゲーム理論におけるTit-for-Tat (TFT) 戦略に基づき,ピアのピース取得には他のピアへのピース提供か必要となる仕組みが導入されている. このことにより,フリーライダーの発生を抑制することができる. 本発表では,このようなTFT戦略には,さらにピア間のピース交換を制限する効果がある点に着目し,サーバが間接的にシステムを制御し,全体として望ましいファイル配信を実現することのできる方式の確立を目指す. まず,TFT型P2Pファイル配信システムにおける最適なピースフローの決定問題を整数線形計画問題として定式化し,既存の線形ソルバで最適解を導出する. 最適なピースフローを分析することで,最適なピア間の接続関係を明らかにするとともに,サーバのピース送信戦略,ピアのピース取得戦略からなる,TFT型P2Pファイル配信システムの間接型制御方式を提案する. シミュレーション評価により,提案方式が最適解と近い平均ファイル取得完了時間を実現できること,提案方式と最適トポロジの組合せにより,ピア数やピース数の観点でシステムのスケールが大きくなった場合においても効率的なファイル配信を実現できることを示す.