P2P的特征没有统一定义, 但是我认为将下面这几个特征写下来有助于理解

• 没有集中数据库
• 没有集中的协调中心
• 每个节点只有局部视图
• 所有数据都可以访问
• 节点不可靠
• 节点自治
• 全局行为依靠局部行为

P2P不适合TCP:上行带宽的堵塞 -> 大量丢包 -> 下行速率也上不去

P2P网络发展

第一代: 集中式,保管各个节点的信息. 服务器gg, 整个网络gg
第二代: 纯分布式, 占用资源 不可靠
第三代: 混合型, 每一簇都有一个超级节点, 超级节点之间组成服务器层. 但是超级节点脆弱导致簇内孤立
第四代: 结构型, DHT算法, 节点没有全局视图, 只维护临近后继节点. 文件信息通过特定算法映射到某个节点

纯分布式

纯分布式的问题

1. 为了保证找到最短路径, 可采取生成树. 但是树容易导致出现关键节点
2. 信息风暴. 短时间会有大量节点访问信息节点

混合型

因此出现混合型: SN(super node)节点和ON(ordinary node)节点

• 根据性能选取SN节点.
• 新ON加入的时候会得到上百个SN节点信息, 根据自己选取要加入的SN
• ON将自己的文件信息发送给SN

结构型

目的:能够快速的找到资源所在节点的索引节点
创建两个空间:

• 资源空间(每一个资源唯一编号,eg: hash)

• 节点空间, 尽量使节点空间和资源空间一样大, 这样每一个资源都能被唯一的节点索引到

  按照类似链表一样的方法将这些节点连接起来

chord算法
逐步成环, 新节点加入时调整环.
定期调用fixTable函数, 给每一个节点修正"捷径"
解决复杂度过高的唯一方法是增加每一个节点的"捷径"

Pastry算法
利用了层次化的路由方案, 最长匹配

1. 如果有节点数4位, 那么每个节点保存四种类型的指针.
2. 第一种类型指向了第一位不同的其他节点.
3. 第二种类型指向了第一位相同&第二位不同的节点
4. 最后一种要记录所有的指针, 因为类型记录的是真实的节点

通俗理解: 从大工去天安门.问大工的人怎么去北京, 问北京人怎么去长安街, 在长安街上问天安门在哪

CAN 算法
将节点编号看做是一个d维的向量, 节点只和自己空间距离为1的节点建立连接.
请求时, 直接发送给距离更近的方向的邻居.
邻居退出时, 接管对方; 有新加入者时, 分自己的空间一半给对方.

文件传输策略

传统传输方法?
稀有优先策略?
随机片段开始?
-> 都没有解决"最终导致均为头部传输"的问题

考虑引入线代的知识"线性无关""线性变换"

• 设文件分成四个片段x1,x2,x3,x4
• 节点1请求时, 种子节点给四个x分配权重a1,a2,a3,a4, -> 节点1拿到的是b1片段
• 以此类推, 节点2,3,4分别拿到了b2, b3, b4
• 当节点5向节点1234请求时,对于拿到的b5, 想要还原出X, 有: B=AX
• 只要A可逆, 就能求得X

但是这样做还有一个问题, 可能随着反复迭代, 后续节点拿到的数据是不可还原的

节点10拿到的数据不可还原成整个文件

因此当某个节点拿到两个片段后, 应该重新运算分片(使得后续分发每一次都是线性无关的)

文件传输策略(视频流)

• 一般是单向的

• 两者buffer时间相差不大

  
  视频流P2P简化模型
  

  其中: 黑色部分代表循环队列的展开.

关键因素: 循环队列大小, 初始播放缓存, 允许最大进度差