一、应用进程跨越网络的通信

在这以前我们已经讨论了互联网使用的几种常用的应用层协议，这些应用协议使广大用户可以更加方便地利用互联网的资源。

现在的问题是:如果我们还有一些特定的应用需要互联网的支持，但这些应用又不能直接使用已经标准化的互联网应用协议，那么我们应当做哪些工作?要回答这个问题，实际上就是要了解下面要介绍的系统调用和应用编程接口。这些问题需要一门专门的课程来学习，我们在这里只能给出一些初步的概念。

1、系统调用和应用编程接口

大多数操作系统使用系统调用(systemcall)的机制在应用程序和操作系统之间传递控制权。对程序员来说，系统调用和一般程序设计中的函数调用非常相似，只是系统调用是将控制权传递给了操作系统。下图说明了多个应用进程使用系统调用的机制。

当某个应用进程启动系统调用时，控制权就从应用进程传递给了系统调用接口。此接口再把控制权传递给计算机的操作系统。操作系统把这个调用转给某个内部过程，并执行所请求的操作。内部过程一旦执行完毕，控制权就又通过系统调用接口返回给应用进程。总之只要应用进程需要从操作系统获得服务，就要把控制权传递给操作系统，操作系统在执行必要的操作后把控制权返还给应用进程。因此，系统调用接口实际上就是应用进程的控制权和操作系统的控制权进行转换的一个接口。由于应用程序在使用系统调用之前要编写一些程序特别是需要设置系统调用中的许多参数，因此这种系统调用接口又称为应用编程接口API。

API从程序设计的角度定义了许多标准的系统调用函数应用进程只要使用标准的系统调用函数就可得到操作系统的服务。因此从程序设计的角度看也可以把 API看成是应用程序和操作系统之间的接口。

现在 TCP/IP协议软件已驻留在操作系统中。由于TCPIP协议族被设计成能运行在多种操作系统的环境中，因此TCP/IP标准没有规定应用程序与TCP/IP协议软件如何接口的细节，而是允许系统设计者能够选择有关API的具体实现细节。目前，只有几种可供应用程序使用 TCPP的应用编程接口AP。这里最著名的就是美国加利福尼亚大学伯克利分校为Berkeley UNIX操作系统定义的一种 API，它又称为套接字接口(socket interface)(或插口接口)。微软公司在其操作系统中采用了套接字接口API，形成了一个稍有不同的API，并称之为 Windows Socket，简称为 WinSock。AT&T 为其 UNIX 系统V定义了一种 API，简写为
TLl (Transport Layer Interface).

我们知道，若要让计算机做某件事情，就要编写使计算机能理解的程序。在网络环境下的计算机应用都有一个共同特点，这就是:位于不同地点的计算机要通过网络进行通信。从另一种角度看，计算机之间的通信就是本计算机要读取另一个地点的计算机中的数据，或者要把数据从本计算机写入到另一个地点的计算机中。这种“读取”和“写入”的过程都要用到上面所说的系统调用。

在讨论网络编程时常常把套接字作为应用进程和运输层协议之间的接口，下图表示这一概念。图中假定了运输层使用TCP协议(若使用UDP 协议，情况也是类似的，只是UDP是无连接的。通信的两端仍然可用两个套接字来标志)。现在套接字已成为计算机操作系统内核的一部分。

请注意:在套接字以上的进程是受应用程序控制的，而在套接字以下的运输层协议软件则是受计算机操作系统的控制。因此，只要应用程序使用TCP/IP协议进行通信，它就必须通过套接字与操作系统交互(这就要使用系统调用函数)并请求其服务。我们应当注意到应用程序的开发者对套接字以上的应用进程具有完全的控制，但对套接字以下的运输层却只有很少的控制，例如，可以选择运输层协议(TCP或UDP)以及一些运输层的参数(如最大缓存空间和最大报文长度等)。

当应用进程(客户或服务器)需要使用网络进行通信时，必须首先发出socket系统调用，请求操作系统为其创建一个“套接字”。这个调用的实际效果是请求操作系统把网络通信所需要的一些系统资源(存储器空间、CPU时间、网络带宽等)分配给该应用进程。操作系统为这些资源的总和用一个叫作套接字描述符(socket descriptor)的号码(小的整数)来表示，然后把这个套接字描述符返回给应用进程。此后，应用进程所进行的网络操作(建立连接、收发数据、调整网络通信参数等)都必须使用这个套接字描述符。所以，几乎所有的网络系统调用都把这个套接字描述符作为套接字的许多参数中的第一个参数。在处理系统调用的时候，通过套接字描述符，操作系统就可以识别出应该使用哪些资源来完成应用进程所请求的服务。通信完毕后，应用进程通过一个关闭套接字的close系统调用通知操作系统回收与该套接字描述符相关的所有资源。由此可见，套接字是应用进程为了获得网络通信服务而与操作系统进行交互时使用的一种机制。

下图给出了当应用进程发出socket 系统调用时，操作系统所创建的套接字描述符与套接字数据结构的关系。由于在一个进程中可能同时出现多个套接字，因此需要有一个存放套接字描述符的表，而每一个套接字描述符有一个指针指向存放套接字的地址。在套接字的数据结构中有许多参数要填写。下图中已填写好的参数是协议族(PFINET，表示使用Interet的TCP/IP协议族)和服务(SOCKSTREAM，表示使用流式服务，也就是使用TCP服务)。在刚刚创建一个新的套接字时，有灰色背景的四个项目(本地和远地IP地址，本地和远地端口)都是未填写的，因此它和任何机器中的应用进程暂时都还没有联系。
这里要特别强调一下，在第5章5.3.2节的最后，我们曾指出，同一个名词socket 可表示多种不同的意思。在本节讨论socket系统调用时，套接字socket 已不仅仅是RFC 793 所定义的如公式(5-1)所示的那样，而是如上图右边所示的套接字的数据结构。

2、几种常用的系统调用

下面我们以使用TCP的服务为例介绍几种常用的系统调用。

1）连接建立阶段

当套接字被创建后，它的端口号和IP地址都是空的，因此应用进程要调用bind(绑定)来指明套接字的本地地址(本地端口号和本地IP地址)。在服务器端调用bind时就是把熟知端口号和本地IP地址填写到已创建的套接字中。这就叫作把本地地址绑定到套接字。在客户端也可以不调用bind，这时由操作系统内核自动分配一个动态端口号(通信结束后由系统收回)。

服务器在调用 bind 后，还必须调用 listen(收听)把套接字设置为被动方式，以便随时接受客户的服务请求。UDP服务器由于只提供无连接服务，不使用listen系统调用。

服务器紧接着就调用accept(接受)，以便把远地客户进程发来的连接请求提取出来。系统调用accept的一个变量就是要指明是从哪一个套接字发起的连接。

调用 accept要完成的动作较多。这是因为一个服务器必须能够同时处理多个连接。这样的服务器常称为并发方式(concurrent)工作的服务器。可以有多种方法实现这种并发方式下图所示的是一种实现方法。

主服务器进程M(就是通常所说的服务器进程)一调用accept，就为每一个新的连接请求创建一个新的套接字，并把这个新创建的套接字的标识符返回给发起连接的客户方。与此同时，主服务器进程还要创建一个从属服务器进程(如下图中的S)来处理新建立的连接。这样，从属服务器进程用这个新创建的套接字和客户进程建立连接，而主服务器进程用原来的套接字重新调用accept，继续接受下一个连接请求。在已建立的连接上，从属服务器进程就使用这个新创建的套接字传送和接收数据。数据通信结束后，从属服务器进程就关闭这个新创建的套接字，同时这个从属服务器也被撤销。

总之，在任一时刻，服务器中总是有一个主服务器进程和零个或多个从属服务器进程主服务器进程用原来的套接字接受连接请求，而从属服务器进程用新创建的套接字(在上图中注明是“连接套接字”)和相应的客户建立连接并可进行双向传送数据。

以上介绍的是服务器为了接受客户端发起的连接请求而进行的一些系统调用。现在看一下客户端的情况。当使用TCP协议的客户已经调用socket创建了套接字后，客户进程就调用connect，以便和远地服务器建立连接(这就是主动打开，相当于客户发出的连接请求)。在connect系统调用中，客户必须指明远地端点(即远地服务器的IP地址和端口号)。

2）数据传送阶段

客户和服务器都在TCP连接上使用send系统调用传送数据，使用recv系统调用接收数据。通常客户使用send发送请求，而服务器使用send发送回答。服务器使用recv接收客户用send 调用发送的请求。客户在发完请求后用recv接收回。

调用 send 需要三个变量:数据要发往的套接字的描述符、要发送的数据的地址以及数据的长度。通常 send 调用把数据复制到操作系统内核的缓存中。若系统的缓存已满，send就暂时阻塞，直到缓存有空间存放新的数据。

调用recv也需要三个变量:要使用的套接字的描述符、缓存的地址以及缓存空间的长度。

3）连接释放阶段

一旦客户或服务器结束使用套接字，就把套接字撤销。这时就调用close释放连接和撤销套接字。

下图画出了上述的一些系统调用的使用顺序。有些系统调用在一个TCP 连接中可能会循环使用。

UDP服务器由于只提供无连接服务，因此不使用listen和accept系统调用。

二、P2P 应用

我们在第1章的1.3.1节中已经简单地介绍了P2P应用的概念。现在我们将进一步讨论P2P 应用的若干工作原理。

P2P应用就是指具有P2P体系结构的网络应用。所谓P2P体系结构就是在这样的网络应用中，没有(或只有极少数的)固定的服务器，而绝大多数的交互都是使用对等方式(P2P方式)进行的。

P2P应用的范围很广，例如，文件分发、实时音频或视频会议、数据库系统、网络服务支持(如P2P打车软件、P2P理财等)。限于篇幅，下面只介绍最常用的P2P文件分发的工作原理。

P2P文件分发不需要使用集中式的媒体服务器，而所有的音频/视频文件都是在普通的互联网用户之间传输的。这其实是相当于有很多(有时达到上百万个)分散在各地的媒体服务器(由普通用户的计算机充当这种媒体服务器)向其他用户提供所要下载的音频/视频文件。这种P2P文件分发方式解决了集中式媒体服务器可能出现的瓶颈问题。

目前在互联网流量中，P2P工作方式下的文件分发已占据了最大的份额，比万维网应用所占的比例大得多。因此单纯从流量的角度看，P2P文件分发应当是互联网上最重要的应用现在P2P文件分发不仅传送音频文件MP3，而且还传送视频文件(10~1000 MB，或更大)、各种软件和图像文件。

1、具有集中目录服务器的P2P工作方式

最早使用P2P工作方式的是Napster。这个名称来自1999年美国东北大学的新生ShawnFanning 所写的一个叫作 Napster 的软件。利用这个软件就可通过互联网免费下载各种 MP3音乐。Napster的出现使MP3成为网络音乐事实上的标准。

Napster能够搜索音乐文件，能够提供检索功能。所有音乐文件的索引信息都集中存放在Napster 目录服务器中。这个目录服务器起着索引的作用。使用者只要查找目录服务器,就可知道应从何处下载所要的MP3文件。在2000年，Napster 成为互联网上最流行的P2P应用，并占据互联网上的通信量中相当大的比例。

这里的关键就是运行 Napster 的所有用户，都必须及时向Napster 的目录服务器报告自己已经存有哪些音乐文件。Napster目录服务器就用这些用户信息建立起一个动态数据库，集中存储了所有用户的音乐文件信息(即对象名和相应的IP地址)。当某个用户想下载某个MP3文件时，就向目录服务器发出查询(这个过程仍是传统的客户-服务器方式)，目录服务器检索出结果后向用户返回存放这一文件的计算机IP地址，于是这个用户就可以从中选取一个地址下载想要得到的MP3文件(这个下载过程就是P2P方式)。可以看出，Napster的文件传输是分散的(P2P方式)，但文件的定位则是集中的(客户-服务器方式)。

下图是 Napster 的工作过程的示意图。假定 Napster 目录服务器已经建立了其用户的动态数据库。图中给出了某个用户要下载音乐文件的主要交互过程。

• 用户X向Napster目录服务器查询(客户-服务器方式)谁有文件MP3#。
• Napster 目录服务器回答X:有三个地点有文件MP3#，即A,B和C(给出了这三个地点的 IP 地址)。于是用户X得知所需的文件 MP3#的三个下载地点。
• 用户X可以随机地选择三个地点中的任一个，也可以使用PING 报文寻找最方便下载的一个。在上图中，我们假定X向A发送下载文件MP3#的请求报文。现在X和A都使用P2P方式通信，互相成为对等方，X是临时的客户，而对等方A是临时的服务器。
• 对等方A(现在作为服务器)把文件MP3#发送给X

这种集中式目录服务器的最大缺点就是可靠性差，而且会成为其性能的瓶颈(尤其是在用户数非常多的情况下)。更为严重的是这种做法侵犯了唱片公司的版权。虽然Napster网站并没有直接非法复制任何MP3文件(Napster 网站不存储任何 MP3 文件，因而并没有直接侵犯版权)，但法院还是判决Napster属于“间接侵害版权”，因此在2000年7月底Napster 网站就被迫关闭了。

2、具有全分布式结构的P2P文件共享程序

在第一代P2P文件共享网站Napster 关闭后，开始出现了以Gnutella 为代表的第二代P2P文件共享程序。Gnutella是一种采用全分布方法定位内容的P2P文件共享应用程序。Gnutella 与Napster 最大的区别就是不使用集中式的目录服务器进行查询，而是使用洪泛法在大量 Gnutella 用户之间进行查询。为了不使查询的通信量过大，Gnutella 设计了一种有限范围的洪泛查询。这样可以减少倾注到互联网的查询流量，但由于查询的范围受限，因而这
也影响到查询定位的准确性。

为了更加有效地在大量用户之间使用P2P技术下载共享文件，最近几年已经开发出很多种第三代 P2P 共享文件程序[KURO17]，它们使用分散定位和分散传输技术。如KaZaA,电骡eMule，比特洪流 BT(Bit Torrent)等。

下面对比特洪流 BT的主要特点进行简单的介绍。

在 P2P的文件分发应用中，2001年由BrahmCohen开发的BitTorrent(中文意思是“比特洪流”)是很具代表性的一个。取这个名称的原因就是BitTorrent 把参与某个文件分发的所有对等方的集合称为一个洪流(torrent)。为了方便，下面我们使用BitTorrent 的简称 BT。BT 把对等方下载文件的数据单元称为文件块(chunk)，一个文件块的长度是固定不变的，例如，典型的数值是 256KB。当一个新的对等方加入某个洪流时，一开始它并没有文件块。但新的对等方逐渐地能够下载到一些文件块。而与此同时，它也为别的对等方上传一些文件块。某个对等方获得了整个的文件后，可以立即退出这个洪流(相当于自私的用户)，也可继续留在这个洪流中，为其他的对等方上传文件块(相当于无私的用户)。加入或退出某个洪流可在任何时间完成(即使在某个文件还没有下载完毕时)，也是完全自由的。

BT 的协议相当复杂[W-BT1。下面讨论其基本机制。

每一个洪流都有一个基础设施节点，叫作追踪器(tracker)。当一个对等方加入洪流时，必须向追踪器登记(或称为注册)，并周期性地通知追踪器它仍在洪流中。追踪器因而就跟踪了洪流中的对等方。一个洪流中可以拥有少到几个多到几百或几千个对等方。

我们用下图来进一步说明BT的工作原理。当一个新的对等方A加入洪流时，追踪器就随机地从参与的对等方集合中选择若干个(例如，30个)，并把这些对等方的IP地址告诉A。于是A就和这些对等方建立了TCP连接。我们称所有与A建立了TCP连接的对等方为“相邻对等方”(neighboring peers)。在下图中我们在上面的覆盖网络中画出了 A有三个相邻对等方(B.C和D)。这些相邻对等方的数目是动态变化的，有的对等方可能不久就离开了，但不久后又有新加入进来的对等方。请注意，实际的网络拓扑可能是非常复杂的(参见下图覆盖网络下面的实际网络图)。我们知道，TCP连接只是个逻辑连接，而一个TCP连接可能会穿越很多的网络。因此我们在讨论问题时，可以利用实际网络上面的一个更加简洁的覆盖网络，这个覆盖网络忽略了实际网络的许多细节，使问题的讨论更加方便。在覆盖网络中，A的三个相邻对等方就看得很清楚。

在任何时刻，每一个对等方可能只拥有某文件的一个文件块子集，而不同的对等方所拥有的文件块子集也不会完全相同。对等方A将通过TCP连接周期性地向其相邻对等方索取它们拥有的文件块列表。根据收到的文件块列表，A就知道了应当请求哪一个相邻对等方把哪些自己缺少的文件块发送过来。

下图是对等方之间互相传送数据块的示意图。例如，A向B、C和D索取数据块，但B同时也向C和D传送数据块，D和C还互相传送数据块。由于P2P对等用户的数量非常多，因此，从不同的对等方获得不同的数据块，然后组装成整个的文件，一般要比仅从一个地方下载整个的文件要快很多。

然而A必须做出两个重要决定。第一，哪些文件块是首先需要向其相邻对等方请求的?第二，在很多向A请求文件块的相邻对等方中，A应当向哪些相邻对等方发送所请求的文件块?

对于第一个问题，A要使用叫作最稀有的优先(rarest first)的技术。我们知道，凡是A所缺少的而正好相邻对等方已拥有的文件块，都应当去索取。可能其中的某些文件块，很多相邻对等方都有(即文件块的副本很多)，这就是“不稀有的”文件块，以后可慢慢请求。如果A所缺少的文件块在相邻对等方中的副本很少，那就是“很稀有的”。因此，A首先应当请求副本最少的文件块(即最稀有的)。否则，一旦拥有最稀有文件块的对等方退出了洪流就会影响 A对所缺文件块的收集。

对于第二个问题，BT采用了一种更加机灵的算法，其基本思想就是:凡当前有以最高数据率向A传送文件块的某相邻对等方，A就优先把所请求的文件块传送给该相邻对等方具体来说，A持续地测量从其相邻对等方接收数据的速率，并确定速率最高的4个相邻对等方。接着，A就把文件块发送给这4个相邻对等方。每隔10秒钟，A还要重新计算数据率，然后可能修改这4个对等方。在BT的术语中，这4个对等方叫作已疏通的或无障碍的(unchoked)对等方。更重要的是，每隔 30 秒，A 要随机地找一个另外的相邻对等方 B，并向其发送文件块。这样，A有可能成为B的前4位上传文件块的提供者。在此情况下，B也有可能向A发送文件块。如果B发送文件块的速率足够快，那么B也有可能进入A的前4位上传文件块的提供者。这样做的结果是，这些对等方相互之间都能够以令人满意的速率交换文件块。

3、P2P 文件分发的分析

我们从一个例子开始，来讨论P2P文件分发中的几个重要概念[KURO17]。

在下图中，有N台主机要从互联网上的服务器下载一个大文件，其长度为Fbit。在图中我们把这个文件也记为F。按照习惯，从互联网传送数据到主机，叫作下载(download)而反过来传送数据，即从主机向互联网传送，则称为上传(upload)或上载。服务器的文件是供互联网上的用户享用的，因此服务器的文件只是单方向上传到互联网。我们把服务器的上传速率记为“，单位是bits。再假定主机与互联网连接的链路的上传速率和下载速率分别为w和d，单位都是 bits。我们还假定互联网的核心部分不会产生拥塞。瓶颈只会发生在服务器的接入链路，或者是某些主机的接入链路。

我们先在传统的客户-服务器方式下，计算给所有主机分发完毕的最短时间T

从服务器端考虑，N台主机共需要从服务器得到的数据总量(比特数)是NF。如果服务器能够不停地以其上传速率“向各主机传送数据，一直到各主机都收到文件F，就需要时间 NF/u，单位是秒。由此可见，T不可能小于NF/u

如果N台主机都以各自的下载速率不停地下载文件F，那么下载速率最慢的主机(设其下载速率为 d)的下载文件时间(F/d)，将是N个下载时间中最大的一个。由此可见T.也不可能小于 F/d。

• 如果 NF/u> F/d，则瓶颈在服务器端的接入链路。这时T=NF/u。
• 如果 F/d> NF/u，则瓶颈在下载最慢的主机的接入链路。这时T=F/dmi。

由此可得出所有主机都下载完文件F的最少时间是

从以上分析可以看出，若公式括号中的第一项大于第二项，则T就与主机数N成正比。如果主机数增大1000倍，那么文件的分发时间也要增大1000倍。

下面讨论在P2P方式下，文件全部分发完毕的最少时间T。然而在P2P方式下，文件分发所需的时间较难计算，这是因为每一台主机在接收文件的同时，还利用自己的上传能力向其他主机传送文件。文件传送所需的时间取决于主机向对等方传送文件的具体方式。但是，我们还是可以导出文件分发所需的最少时间的表达式。

在文件分发开始时，只有服务器有文件F。服务器必须把文件F的每一个比特通过接入链路传送到互联网(至少要传送一次)。因此文件分发的最少时间不可能小于F/u。和客户服务器方式相比，在P2P方式下，服务器不需要一遍一遍地发送文件F，因为互联网上的其他主机(即对等方)可以代替服务器向其他对等方分发文件F。

在P2P方式下，下载速率最慢的主机(设其下载速率为d)下载文件F的时间是F/d这是N个对等方下载时间中最大的一个。可见文件分发的最少时间不可能小于F/d。这个结论和客户-服务器方式是一样的。

整个系统中所有主机(包括服务器)的上传速率之和是ut=us+u1+u2+…+u~。因此文件分发的最少时间也不可能小于 NF/ut。

这样，我们得出在P2P方式下所有主机都下载完文件F的最少时间的下限是

在公式的推导过程中，我们假定每一个对等方只要收到一个比特就立即上传到互联网的其他对等方。但实际上是把收到的若干个比特组成一个数据块后再上传出去。但是当文件 F很大时，我们也可以在公式中取等号，作为文件F的最少分发时间 Tpzp的近似值。

有一种情况最值得我们注意。这就是对等方的数目非常大，因此在公式(6-3)的括号中的最后一项的值将大于前两项的值。这样，Tpzp值的下限就近似为NF/uT。

4、在P2P 对等方中搜索对象

在P2P文件系统中，对等方用户的数量非常多，并且处于一种无序的状态。任何一个对等方可以随时加入进来或随时退出。在这种情况下，怎样有效地找到所需的文件，也就是怎样有效地定位对等方及其资源，乃是P2P系统中的一个十分重要的问题。

限于篇幅，我们在这里只简单介绍一下怎样利用散列函数来定位对等方。

我们知道，Gnutella是一种采用全分布方法定位内容的P2P文件共享应用程序，它解决了集中式目录服务器所造成的瓶颈问题。然而Gnutella是在非结构化的覆盖网络中采用查询洪泛的方法来进行查找的，因此查找的效率较低。现在比较好的查找方法是设法构建一种分布式数据库，以进行对等方及其资源的定位。这种分布式数据库在概念上并不复杂，只要能够支持大量对等方(可能有几百万个)进行索引查找即可。存储在数据库中的信息只有两个部分：

• 要查找的资源名K(例如，电影或歌曲的名字)。资源名也可称为关键字。
• 存放该对象的节点的IP地址N。有的IP地址还附带有端口号。

细心的读者可能会联想到曾在前面6.1节讨论的DNS域名系统。DNS是根据主机的域名来查找其IP地址，这和P2P的情况有相似之处。但我们知道，主机的域名是结构化的命名系统，因此域名服务器可以划分为几种不同的级别(如根服务器等)便于查找。但P2P系统则不同，其资源名是非结构化的。因此不能套用DNS的那种查找方法。

前面已经讲过，Napster在一个集中式目录服务器中构建的查找数据库虽然很简单，但性能上却有瓶颈。在P2P系统中，应怎样构建分布式的P2P数据?让每个对等方都拥有所有对等方IP地址的列表是不可行的。让所有成对出现的(资源名K,IP地址N)随机地分散到各对等方也是不可行的。因为这将使查找对象的次数过大，无法使用。现在广泛使用的索引和查找技术叫作分布式散列表 DHT (Distributed Hash Table)。DHT也可译为分布式哈希表，它是由大量对等方共同维护的散列表。基于DHT的具体算法已有不少，如ChordPastry,CAN(Content Addressable Network)，以及 Kademilia等。下面简单介绍广泛使用的Chord 算法，这是美国麻省理工大学于2001年提出的[STOI011。

分布式散列表DHT利用散列函数，把资源名及其存放的节点P地址N都分别映射为资源名标识符 KID和节点标识符 NID。如果所有的对等方都使用散列函数 SHA-1(我们在下一章 7.3.1节还要介绍SHA-1在网络安全方面的应用)，那么通过散列得出的标识符KID 和 NID 都是 160 位二进制数字，且其数值范围在[0,$2^{160}$-1]之间。虽然从理论上讲，散列函数 SHA-1是多对一的函数，但实际上不同输入得到相同的输出的概率是极小的。此外通过 SHA-1映射得到的标识符能够比较均匀而稀疏地分布在Chord 环上。为便于讨论，我们假定现在标识符只有5位二进制数字，也就是说，所有经散列函数得出的标识符的数值范围都在[0，31]之间。Chord 把节点按标识符数值从小到大沿顺时针排列成一个环形覆盖网络(见图(a))，并按照下面的规则进行映射:

• 节点标识符NID按照其标识符值映射到Chord 环上对应的点，见图(a)中标有NID 的小圆点，如N4.N7.N10.N20.N26 和N30。
• 资源名标识符 KID 则按照其标识符值映射到与其值最接近的下一个 NID，见图 (a)中标有 KID的小方块。所谓“最接近的下一个”NID就是指:从KID值开始，按顺时针方向沿 Chord 环遇到的下一个 NID。例如，K31和K2应放在 N4，因为在环上从 31和2按顺时针方向遇到的下一个NID是N4。同理，K8.K12.K23和K29应分别放在N10,N20,N26和N30。如果碰巧同时出现K29和N29(这种概率极小)，那么K29就应当放在N29。

请注意:在图中，K31和K2都放在N4，这表示要查找存放资源K31或K2的节点的IP地址，就应当到节点N4去查找。请注意，资源K31和K2并非存放在节点N4。

这就是说，每个资源由Chord环上与其标识符值最接近的下一个节点提供服务。我们再强调一下，Chord 环并非实际的网络。在Chord 环上相邻的节点，在地理上很可能相距非常远。

Chord 环上的每一个节点都要维护两个指针变量，一个指向其后继节点，而另一个指向其前任节点。例如，在图(a)中，N10的后继节点是N20(N10沿顺时针方向的下一个节点)，其前任节点是N7(N10沿逆时针方向的前一个节点)。如果一个新的节点N13加入进来，那么N20的前任节点就变为N13，因而K12就要从N20的位置移到N13，同时N10的后继节点就变为N13(见图(b))。此外，如果节点N26退出，那么K23 就要移到N30，而 N30的前任节点就变为N20，同时N20的后继节点变为N30。

在这样的Chord环上查找资源，从理论上讲，任何一个节点，只要从其后继节点一个个地遍历查找下去，一定可以找到所查询的资源。可见要定位一个资源，平均需要沿环发送查找报文 N/2个，或遍历O(N)个节点(N为环上的总节点数)。显然，这种顺序查找的方法效率很低。

为了加速查找，在Chord 环上可以增加一些指针表(finger table)，它又称为路由表或查找器表。若Chord环上的标识符有m位(现在m=5)，则在节点"上的指针表可设置不超过 m个指针，指向其后继的节点。我们先看下图中节点N4的指针表。指针表中的第2列是从N4可以指向的多个后继节点。本来每一个节点仅仅指向沿顺时针方向的下一个后继节点，但现在则指向多个后继节点(在本例中就是N7,N10和N20)。第1列的第i行是计算(N4+$2^{i-1}$)，用来得出后继节点。例如，第4行i=4，算出(N4+$2^{i-1}$)=N4+8=12而Chord 环上的节点 12的后继节点是 N20。图中还画出了从 N4 到这几个后继节点的连线(这些连线就是Chord环上的弦，Chord名字由此得出)。还有一点要注意的是，在N20的指针表中的第5行，N20+16=36，但按照模$2^5$运算，36mod$2^5$=4，恰好节点4的后继节点是 N4。

假定在图6-36中的节点N4要查找K29。如果用遍历各节点的方法，则要查找5次，即 N7→N10→N20→N26→N30。但若利用指针表，则N4首先在自己的指针表中寻找在不到 29且最接近 29的节点，即N20，然后把定位资源K29的请求发送给N20。在N20的指针表中继续类似的寻找。结果是:最接近29的节点是30。这就是存放资源K29的节点。这种查找方法类似于二分查找，只用了两次查找，定位一个资源仅需O($lo{g}_{2}N$)步。

在P2P网络中，对等方可能相当频繁地加入或退出系统，这就需要很好地维护这个分布式数据库(维护各节点的指针和指针表)，而这种维护的工作量可能会很大。当对等方数量非常大时，究竟采用何种查询机制更加合理，则需要根据具体情况来确定。

P2P技术还在不断地改进，但随着P2P文件共享程序日益广泛地使用，也产生了一系列的问题有待于解决。这些问题已迫使人们要重新思考下一代互联网应如何演进。例如，音频/视频文件的知识产权就是其中的一个问题。又如，当非法盗版的、或不健康的音频/视频文件在互联网上利用P2P文件共享程序广泛传播时，要对P2P的流量进行有效的管理，在技术上还是有相当的难度。由于现在P2P文件共享程序的大量使用，已经消耗了互联网主干网上大部分的带宽。因此，怎样制定出合理的收费标准，既能够让广大网民接受，又能使网络运营商赢利并继续加大投入，也是目前迫切需要解决的问题。