P2P
P2P的特征没有统一定义, 但是我认为将下面这几个特征写下来有助于理解
- 没有集中数据库
- 没有集中的协调中心
- 每个节点只有局部视图
- 所有数据都可以访问
- 节点不可靠
- 节点自治
- 全局行为依靠局部行为
P2P不适合TCP:上行带宽的堵塞 -> 大量丢包 -> 下行速率也上不去
P2P网络发展
第一代: 集中式,保管各个节点的信息. 服务器gg, 整个网络gg
第二代: 纯分布式, 占用资源 不可靠
第三代: 混合型, 每一簇都有一个超级节点, 超级节点之间组成服务器层. 但是超级节点脆弱导致簇内孤立
第四代: 结构型, DHT算法, 节点没有全局视图, 只维护临近后继节点. 文件信息通过特定算法映射到某个节点
纯分布式
纯分布式的问题
- 为了保证找到最短路径, 可采取生成树. 但是树容易导致出现关键节点
- 信息风暴. 短时间会有大量节点访问信息节点
混合型
因此出现混合型: SN(super node)节点和ON(ordinary node)节点
- 根据性能选取SN节点.
- 新ON加入的时候会得到上百个SN节点信息, 根据自己选取要加入的SN
- ON将自己的文件信息发送给SN
结构型
目的:能够快速的找到资源所在节点的索引节点
创建两个空间:
-
资源空间(每一个资源唯一编号,eg: hash)
-
节点空间, 尽量使节点空间和资源空间一样大, 这样每一个资源都能被唯一的节点索引到
按照类似链表一样的方法将这些节点连接起来
chord算法
逐步成环, 新节点加入时调整环.
定期调用fixTable函数, 给每一个节点修正"捷径"
解决复杂度过高的唯一方法是增加每一个节点的"捷径"
Pastry算法
利用了层次化的路由方案, 最长匹配
- 如果有节点数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简化模型
其中: 黑色部分代表循环队列的展开.
关键因素: 循环队列大小, 初始播放缓存, 允许最大进度差
