Chuan Wu, Baochun Li （University of Toronto）
Shuqiao Zhao （UUSee, Inc）

目标：分析拓扑。

指出商业系统中的peer选择和拓扑构造算法不复杂。

提到mesh比tree好的原因，但未展开证明。

  • - 适应peer dynamics
  • - flash crowd时好
  • - 带宽利用率高
  • - 拓扑维护简单

对flash crowd时，拓扑如何react，简单的结果。（事实上也无法细化）

2个月（2006年9月-10月）的trace。120GB。结论还用07年的一个trace进行了验证。

方法：Peer周期报告，服务器收集。认为爬的方法的缺陷：1）peer list不是真实的连接。2）没有indegree。

五个主要结论：

  1. 在拓扑变化中发现flash crowd：说明能扛住一定的flash crowd
  2. 度分布不是幂率
  3. 按ISP形成了簇
  4. 互惠
  5. 没有超级节点

UUSee的算法的介绍：

  • 一个media编码server （400Kbps，专有codec）+ 一大群streaming server
  • peer playback buffer：500。每块1/3s。
  • 同步方法：大家都比server晚20s放。
  • TCP
  • 启动时
    • 邻居选择：用握手信号检测RTT，再测TCP速度，由此通过估计算法，选最好的30个邻居作为起始的邻居请求数据。
    • Buffer初始化：抓最新的包，20s后检查。如果此时buffer级别不行，就重新启动，再用20s去抓。所以延时可能有20s，40s，60s。（和同步似乎有矛盾，怀疑前者）
  • 连续请求块。（具体算法没说）
  • 到了Deadline了但还没有收到的piece被跳过
  • buffer填充率到达总大小的75%时就不填了。（特别，保守一点，防止拥塞？）

Peer选择算法的细节：

  • 初始启动时，peer估计自己的最大上载、下载速度。
  • 运行过程中，Peer一直评估自己的uploading能力是否用尽。如果没有，则通知tracker自己有余力。而tracker将其加入有余力的peer的列表里。
  • 当新的peer来时，Tracker告诉它有余力的这些友邻。
  • buffer count为‘1’的个数。运行过程中，peer如果发现一个邻居的buffer count小，就发送buffer count大的邻居给它。
  • peer如果发现自己的buffer count很长时间都很小，就向tracker要新的peer。

（有趣的Peer集中式选择算法，如何评估？）

分析Peer个数：

  • 发现了flash crowd：
  • 每天9pm为一个高峰。在6小时左右，上去又下来，为一个三角形。对CCTV1这个最流行的频道，在中秋节晚会时，最高的人数，变化幅度为10K，折算的平均到达率为：10K/3*3.6K=1 peer/s （还不算太高吧）
  • 稳定的peer为所有peer的1/4。

用buffer count进行的质量评估：发现大多数人还不错。

度分布：

  • 稳定Peer的度分布：要求至少下了10个piece的Peer的度。
    • 入度：10
    • 出度：10-20
  • 总partner：包括那些下了不到10个piece的，或根本没下的Peer
    • 总度30-40。
  • 度随着人数的增长而增长
    • 9pm时，度增大。
  • 出degree与上载throughput有一点相关性：
    • Pearson product-moment correlation coefficient：0.4871

分析是否有超级节点：

  • 用likelihood metric proposed by Li et al. in [Li et al. 2004],
  • 用上载throughput来计算。
  • 没有超级节点

参考文献：

回顾历史：

  • Kazza，第一代Gnutella，
  • 现代Gnutella的经典文献：P2P topology characterization, Stutzbach et al. [Stutzbach et al. 2005]
  • 没有BT网络的拓扑分析
  • BT性能，[Pouwelse et al. 2005], Izal et al. [Izal et al. 2004] and Guo et al. [Guo et al. 2005]
  • KAD的peer churn，session特点。 [Stutzbach and Rejaie 2006] and Steiner et al. [Steiner et al. 2007]
  • Skype：协议，流量特性，用户满意度。[Chen et al. 2006].
  • Ali,Hei,Silverston,Vu的测量
  • GridCast P2P VoD用户体验的测量 Cheng et al. [Cheng et al. 2007]