この論文では,マルチツリー型ビデオ配信における転送ホップ数の自明な下界値が(ほぼ)達成できることを明らかにしています.ここで「ほぼ」と言うのは次のような意味です.まず得られた上界と自明な下界のギャップは高々1です(もし改良できるとしても1ホップ減らせるかどうかの水準まで来ている).自明な下界がタイトになるケースとそうならないケースについてはある程度解明しましたが,不明なケースも残されています.
結果の概要は以下の通りです.与えられたビデオストリームがa個の均一なサブストリーム(ストライプ)に分割されており,各ピアのアップロード容量は,a個のストライプを他のピアに転送できるだけの(ギリギリの)大きさであると仮定します.このとき,一つのストライプをサーバからk(>=3)ホップ以内に受け取ることのできる最大のピア数は,等比級数を用いて1+a+a^2+...+a^{k-1}のようにあらわすことができます(完全a分木を考えれば良い).簡単のため,この値をBkとあらわすことにしましょう.視聴者数NがN>Bkを満たすとき,すべての視聴者がストライプをkホップ以内に受け取ることは不可能です.では,N<=B_kであれば常に(すべての視聴者に向けたすべてのストライプの)kホップ配信は可能なのでしょうか.答えは以下の通りです:
1.N<=B_kであってもkホップ配信が不可能なケースがある(自明な下界である「kホップ」はタイトではない)
2.任意のN<=B_kに対して,k+1ホップ配信は常に可能である(上界とのギャップは高々1である)
kホップ配信の可否が一種の「箱詰め問題」と等価であると言う知見は,この論文の中心でもあり,気に入っている箇所です.与えられた箱に与えられたアイテムを過不足なく詰め込んだ状況がkホップ配信を行なっている状況に対応するのですが,そのような直感的な取り扱いができるようになったことで,議論の見通しがグッとよくなりました.残念ながら「上下界の間の1のギャップ」を埋め切ることはできませんでしたが,自明な下界がタイトとはならないケースを少なくとも一つ見つけることができたので,風穴を開けることはできたと考えています(下界の改良は上界の改良に比べて難しいことが多く,この問題の場合も,改良には数ヶ月を要しています).
この論文の主題はあくまでも数理的な性質の解明なので,実用性にはそれほど重点を置いていませんが,自明な下界とのギャップが高々1であると言う結果は,マルチツリー型配信アルゴリズムの性能としてはまずまずだと思います.ただし手法にはアドホックな(場当たり的な)部分も残されているので,それらを分類してパターン化するなどの作業は,実用化に向けては避けては通れない課題です(今後このテーマが実用化フェーズに入ったときに,ライブラリの一部として誰かが実装することになるのだと思う).