P2P对等体系结构

对一直开启的基础设施服务器有最小程度的依赖，成对间歇连接的主机（对等方）彼此直接通信。

P2P文件分发与C/S文件分发的对比

文件分发模型

将一个文件分发给一个固定的集合。
假定因特网核心带宽充足，网络瓶颈在接入网
服务器接入链路上载速率 $u_s$
对等方 $i$ 接入链路上载速率 $u_i$
对等方 $i$ 接入链路下载速率 $d_i$
待分发文件大小 $F$
要获得该文件的对等方数量 $N$

客户/服务器文件分发

服务器向每个客户发送文件的一个副本，服务器负担大，服务器流量消耗大

$D_{cs} = max \{ \frac{NF}{u_s},\frac{F}{d_{min} } \}$

对足够大的N,分发时间随N线性增加

P2P文件分发

每个客户作为对等方，可重新分发它所有的文件的任何部分。

$D{p2p} = max \{ \frac{F}{u_s}, \frac{F}{d_{min}},\frac{NF}{u_s+\sum_{i=1}^{n}u_i}\}$

扩展性 对于变量用户规模，客户/服务器体系的总传输时间是线性的，而P2P体系的总传输时间是亚线性且有上界的。

BitTorrent协议

用于文件分发的流行P2P协议。

洪流(torrent) 参与一个特定文件分发的所有对等体的集合

文件块 洪流中的对等方彼此传输等长的文件块；

追踪器（tracker） 一个对等方加入洪流时，向追踪器注册自己，并周期性地通知追踪器自己仍在洪流中。追踪器维护正在参与洪流的对等方列表。
BitTorrent协议中的追踪器是分布式的，即后文中的DHT。

邻近对等方 洪流中，成功创建TCP连接的一对对等方。

新对等方A加入洪流时，追踪器（随机地）将洪流的某个子集中所有对等方的ip地址发送给A;
A持有该对等方列表，并试图与该列表上的所有对等方创建并行的TCP连接；
A的邻近对等方不断变动，旧邻近对等方可能离开，新邻近对等方可能与A成功创建TCP连接；
A周期性地询问邻近对等方所持有的块列表，并根据列表信息，对A自身当前未拥有的块发出请求；

最稀缺优先技术 对等方A在决定请求哪些块时，首先请求那些A的邻近对等方中副本最少的块，以大致均衡每个块在洪流中的副本数量。

对换算法 对等方A决定响应邻近对等方们的那个请求。A根据当前向它提供数据的邻居的速率，给出优先权。每个时间周期，A根据优先权决定它向哪些邻居传送数据；每过多个时间周期，A随机选出一个邻居并向他发送数据。
以上关于交换的激励机制常被称为一报还一报。这种激励方案能被回避。但事实上，BitTorrent的生态比较成功。

分布式P2P体系数据库，DHT

中心式数据库模型
客户/服务器体系，中心数据库存储键值对，客户可用特定键查询值。

分布式散列表(Distributed Hash Table,DHT)
分布式P2P体系，大量对等方维护一个键值对的表，每个对等方只存储该表的一个小子集。
允许任一对等方用一个特定键查询该分布式数据库。分布式数据库定位拥有该键值对的对等方，并返回该键值对。
允许任一对等方向数据库中插入新键值对。

朴素设计

在所有对等方中随机分布键值对，每个对等方维护一个所有参与对等方的表。查询键k时向所有其他对等方发送查询。维护键k的对等方向查询者发送响应。
此方案无扩展性，随对等方数量增多，数据库复杂性大大增加。

基于散列的设计

为每个对等方分配一个标识符id，id为n比特整数。
定义将键映射到n比特整数的哈希函数。

中心问题
定义为对等方分配键的规则。

对键key，为id最邻近hash(key)的对等方分配该键值对。
最邻近：键的最邻近后继

插入键值对：确定最邻近该键hash的对等方，而后向该对等方发送查询报文。
如何确定最邻近该键hash的对等方？恰当组织数据库结构

DHT结构

将DHT组织为连通图
连通度过高，每个对等方需维护的邻居数过多
连通度过低，DHT为解析一个查询而需转发的报文次数过多

环形DHT
将对等方组织为环，每个对等方仅与其直接后继和直接前驱联系。

对等方收到一个查询报文时，判断是否应有自己处理该报文，若不是，则将报文转发给后继邻居

捷径DHT
以环形DHT为基础，为每个对等方维护适量的捷径对等方。

对等方收到一个查询报文时，判断是否应有自己处理该报文，若不是，则将报文转发给最邻近该键hash的邻居

研究表明，DHT可被设计为每个对等方的邻居数和每个请求的报文转发次数都在O(logN)，N为对等方总数

对等方扰动

P2P体系中，对等方可不加警示地到来或离去。

为处理对等方扰动，每个对等方应存储冗余的邻居信息。如环形DHT中每个对等方可以同时存储第一后继和第二后继。

计算机网络——应用层-P2P文件分发