计算机网络笔记5——P2P 2024.06.10 计算机网络笔记

这篇文章上次修改于 373 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

计算机网络笔记5——P2P

P2P连接是两个主机之间直接通信，现在没有客户端和服务器一说，两者都是对等方。

P2P与客户-服务器结构对比

客户-服务器结构分发时间

• 定义一个文件有F大小，那么服务器如果向N个客户发送，就需要服务器上载NF大小的文件进行发送，并且速度受到服务器的上载速率限制。以u作为服务器上载上限，则要有至少要有NF/u的时间。
• 并且完成在最慢的客户下载完为止，则至少要有F/dmin。

D = max(F/dmin, NF/u)

能说明客户-服务器结构分发时间是跟随客户数量N线性增长的。

P2P结构分发时间

特点：P2P中每个对等方都可以帮助这个服务器分发这个文件，也就是说，不同于C-S，作为客户不仅在下载文件，还在把下载的文件上传。

• 分发开始时，只有服务器有文件，然而在服务器传输完F的每一个部分后，这个F都已经在这个P2P网络中了，即使这个服务器不进行上传，其它对等方依旧可以帮助完成，故至少需要F/u的时间。
• 同样完成在最慢的客户下载完为止，则至少要有F/dmin。
• 实际上系统整体的总上载能力=服务器的上载速率 + 对等方的上载速率和。故完成所有分发也要NF，最少时间是NF/(u + sum(u))

D = max(NF/(u + sum(u)), F/dmin, F/u)

根据数据模拟，可以得到，在N不断增长的情况下，P2P相比CS结构，完成的时间将越来越有优势。

这体现P2P体系结构的拓展性，在对等方的不断加入后，这个系统会更加有效率。

BitTorrent

BitToiTent是一种用于文件分发的流行P2P协议。

洪流（torrent）：参与一个特定文件分发的所有对等方的集合

文件块（chunk）：指在P2P文件分发过程中，将一个大文件拆分成的较小部分。（例如256KB、512KB或1MB）

工作机制

一个对等方A没有任何文件，后加入一个洪流时，不断获得越来越多的文件块，在获得一个文件块后，A也开始为其他没有这个文件块的对等方上载文件块。直到这个A获取完所有文件块，就已经下载好，它可以选择退出，也可以选择继续为其他对等方上载文件块。并且在下载中途也可以退出，进入只会下载没有的文件块直到结束。

追踪器Tracker

每个torrent都有几个基础设施节点Tracker，当一个对等方加入某个torrent的时候，它就会向Tracker注册自己，并且周期性地通知Tracker它在该torrent中。

Tracker如其名，负责跟踪参与在这个torrent中的所有对等方。一个给定的torrent可能在任何时刻具有数以百计或数以千计的对等方。

当有对等方加入torrent时，Tracker要记录它并且从torrent所有对等方取出一个子集交给这个对等方。

邻近对等方

当一个对等方A加入这个torrent时，它会从Tracker中获得一个torrent对等方子集，对等方会向子集中的所有对等方尝试建立TCP连接，成功连接的对等方我们称作“邻近对等方”，在此后，可能会有邻进对等方退出，也可能会有子集之外的对等方来与A进行TCP连接，邻近对等方会不断变化。

每个对等方都会有文件的不同部分，A将周期性询问每个邻近对等方他们具有的块列表。并且从这些邻近对等方中请求A还没有的块。

所以A要处理两个问题，向谁要哪些块，向谁提供自己的哪些块

最稀缺优先技术（Rarest First）

要哪些块？

对于所有邻近对等方，A已经获取了它们所拥有的块的信息，A就优先去请求最稀缺的文件块，这样可以均衡每个块在torrent中的量已达到平均。

Tit-for-Tat 策略

给哪些块？

这种策略确保对等体之间的公平性和效率。A在决定响应哪个请求时，会优先考虑那些能够以最高速率向她提供数据的邻居。

• 疏通（unchoked）：A持续记录每个邻近对等方的传输速率，确定最高流速的4个对等方，这四个对等方被称为疏通（unchoked）。即即允许这些邻居从她那里下载数据。
• Optimistic Unchoking：每过30秒，她也要随机地选择另外一个邻居并向其发送块。
• 堵塞（Choking）：除了unchoked和随机选择的一个，所有其他相邻对等方均被“阻塞”，即它们不能从Alice接收到任何块。

在P2P工作的时候，每个对等方都要储存一些数据，比如当有对等方询问是否有某个文件块时就应当作出回复。但是对于数据记录来说，这是有多个点，并且每个点都会进入和退出。

所以我们为了便于记录，可以使用DHT。

节点需要能够有效地查找和访问存储在其他节点上的数据。DHT通过将数据的查找和路由任务分布到网络中的各个节点上，实现了高效的数据查找和访问。

分布式哈希表（DHTs）

在P2P系统中，每个对等方只存储少量键值对。对等方可以通过特定键查询数据库，找到存储该键值对的对等方并返回结果。对等方也可以向数据库中插入新的键值对。这种数据库称为分布式哈希表（DHT）。在P2P文件共享应用中，DHT用于存储文件块与拥有这些块的对等方IP的关联。

标识符分配

我们为每个对等方分配一个标识符，该标识符是在一个固定范围内的整数，范围是[0, 2^n - 1]，其中n是一个确定的值。这样的标识符可以使用n位表示。我们使用一个哈希函数将非整数值转换为整数值。假设所有对等方都可以使用这个函数。对于键的分配：我们将每个(键, 值)对分配给标识符最接近该键的对等方，即该键的最接近的后继者对等方。为了避免每个对等方都跟踪所有其他对等方（可扩展性问题），我们使用可以使用环形DHT。

环形DHT

如果我们将节点组织成一个环，每个节点只需跟踪其后继者和前驱者（模2^n）。

在环中，一个节点会问k键由谁负责，然后顺时针发送消息绕环。节点可以确定自己是否负责（最接近）该键。如果不是，它将消息传递给其后继者。当消息到达负责该键的节点时，它可以向查询节点发送消息，表明它负责该键。

使用此系统，平均发送N/2条消息（N = 节点数）。在设计DHT时，总是存在每个节点的邻居数与解析单个查询所需的DHT消息数之间的权衡。（如果每个节点跟踪所有其他节点则需要1条消息；如果每个节点只知道2个邻居则需要N/2条消息）。

为了改进我们的环形DHT，我们可以添加快捷方式，使每个节点不仅跟踪其直接后继者和前驱者，还跟踪环中分散的相对较少的快捷节点。有多少快捷邻居？研究表明，DHT可以设计为每个节点的邻居数和每次查询所需的消息数都是O(log *N*)（N为节点数）。

节点流动

在P2P系统中，节点会增加和减少。为了在这种不稳定下保持DHT覆盖网络，我们要求每个节点跟踪（知道IP地址）其前驱者和后继者，并定期验证其两个后继者是否在线。如果一个节点突然离开，其后继者和前驱者需要更新其信息。前驱者将其第一个后继者替换为第二个后继者，并询问其即时后继者的标识符和IP地址。

如果一个节点加入呢？如果它只知道一个节点，它会问该节点它的前驱者和后继者是谁。消息将到达前驱者，前驱者将发送新加入节点其前驱者和后继者信息。新加入的节点可以加入DHT，将其前驱者的后继者作为自己的后继者，并通知其前驱者更改其后继者信息。