一种基于选择性缓存的内容中心网络动态路由方法

摘要

一种基于选择性缓存的内容中心网络动态路由方法，其中在将用户请求中的兴趣包从终端用户传输到数据提供者的过程中，由所经过的路由器动态修改兴趣包中的信息来确定缓存路由器；兴趣包最终到达数据提供者时，兴趣包确定并记录从终端用户到数据提供者之间的距离，以及从终端用户到缓存返回的数据包的缓存路由器之间的距离；在从数据提供者返回数据包时，数据提供者将兴趣包中关于选择缓存路由器的信息复制到返回的数据包中；在数据包返回过程中，每到达一个路由器对其信息进行动态更新，根据更新结果，数据包缓存在缓存路由器上。本发明能充分利用网络中路由器的缓存空间，实现负载平衡，可在不给网络带宽带来额外的负担的情况下进行有效的路由。

说明书

技术领域

本发明涉及计算机网络，特别是涉及一种基于选择性缓存的内容中心网络动态路 由方法。

背景技术

当今的网络架构是上世纪六七十年代建立的。在互联网建立之初，互联网主要用 于主要科研机构和政府机构之间的联系，因此互联网的各台主机之间是相互信任的。 而且互联网最初主要用于大型机器之间数据和服务的共享，网络拓扑比较简单，服务 类型也很单一，因此，局限于当时互联网的用途，互联网中各个主机之间的通信采用 了点对点通信的方式。

随着科技和社会的发展，在当今社会，硬件设备生产成本不断降低，终端设备在 日常生活中不断得到普及，使互联网逐渐渗透到社会生活的方方面面。在互联网广泛 应用于生产生活的同时，它的功能和用途也发生了深刻的变化。在当今的互联网中， 随着YouTube，P2P等内容分享应用的逐渐流行，内容分享应用所产生的流量在网络 总流量中所占的比例越来越大。一方面，对于内容分享应用而言，用户关心的只是数 据本身，而并不关心数据存放的具体位置；另一方面，当今的互联网架构依然是基于 点对点通信的，所以尽管我们并不关心数据存放的位置，但是我们必须首先将数据映 射成它们的存放位置，然后再去相应的位置去获取数据。这造成了目标和方法的分离， 增加了我们获取数据的复杂度。同时，随着网络的规模的不断扩大，网络中的可能发 生的状况变得越来越复杂，新的网络安全问题层出不穷。为了保证网络的正常运转， 在原来的系统的基础上，我们给网络引入了各种各样的机制，使得网络变得越来越复 杂，网络的管理也变得越来越困难。

为了从根本上解决上述问题，针对当前网络的特点，人们提出了一种新的网络体 系结构，称为命名数据网络(Named Data Networking)。与传统的IP网络不同，在命名 数据网络中，数据而非主机是最基本的路由对象。命名数据网络最基本的特点是，当 我们在请求某一个数据的时候，我们直接请求这个数据本身，而不再是通过访问这个 数据存放的位置来获取这个数据。此外，重新构造网络也允许我们结合当今网络的具 体特性，引入一些新的机制以简化网络的架构，建立更加简单有效的网络安全模型。 从这个意义上讲，命名数据网络的提出蕴含了诸多的机会和希望。

命名数据网络的特点如下：

1)每一个数据包都有一个唯一的名字。当我们要获取某个数据包的时候，我们根 据这个数据包的名字请求这个数据包，而不是将这个数据包映射成它的存放位置，然 后通过访问它的存放位置来获取这个数据包。此外，命名数据网络采用了层次化的命 名结构，比如ndn/video/transformer这样的形式，这样可以通过聚合来有效减小路由表 的规模。

2)每一个路由器的都有缓存数据的功能。当一个数据经过一个路由器的时候，这 个路由器可以选择对这个数据进行缓存。当用户发出一个请求的时候，这个请求会在 网络中进行传播。如果这个请求到达一个路由器，这个路由器发现它缓存了所请求的 数据，那这个路由器就会返回这个数据，因此这个请求就得到了满足。

命名数据网络中有两种不同的数据类型，分别是数据包(Data packet)和兴趣包 (Interest packet)。当一个用户要请求一个数据的时候，他首先需要知道这个数据的 名字，然后这个用户根据这个名字生成一个兴趣包，并将这个兴趣包发送给它的代理 路由器。当这个代理路由器收到这个兴趣包的时候，代理路由器会根据它本身的路由 策略对这个兴趣包进行路由。如果这个兴趣包到达一个路由器并且这个路由器存放了 这个兴趣包所请求的数据包的话，这个数据包就会被返回，否则这个兴趣包最终将会 被传送给所请求的数据包的源服务器，并从源服务器取回所请求的数据包。一个兴趣 包在网络中进行传输的过程中，网络中的路由器会为这个兴趣包维护相应的信息；当 这个兴趣包最终到达了所请求的数据包的存放位置的时候，这个数据包就会沿着原来 兴趣包到达的路径返回。

命名数据网络的路由器主要有三种数据结构，分别是数据仓库(Data Store)，等待 兴趣表(Pending Interest Table)和路由表(Routing Table)。其中，数据仓库主要用于缓存 数据包，等待兴趣表用于记录转发的兴趣包以及聚合兴趣包，路由表则用于转发兴趣 包。兴趣包在网络中的转发过程如下：

1)当一个路由器收到一个兴趣包的时候，它首先在它的数据仓库中查找有没有和 这个兴趣包匹配的数据包。如果有和这个兴趣包匹配的数据包，它就从这个兴趣包到 达的端口返回这个数据包，并终止这个兴趣包的传播。

2)如果这个兴趣包所请求的数据包不存在于这个路由器的数据仓库中，那这个路 由器就会在它的等待兴趣表中查找有没有和这个兴趣包匹配的表项。如果它的等待兴 趣表中有和这个兴趣包匹配的表项，那就说明这个路由器之前已经收到过相同的兴趣 包，并且已经把这个兴趣包转发出去了。因此这个路由器就会把这个兴趣包的到达端 口加入到匹配的等待兴趣表表项的端口列表中并终止这个兴趣包的传播。

3)如果在等待兴趣表中没有和这个兴趣包匹配的表项，那就说明这个路由器第一 次收到这种类型的兴趣包，因此这个路由器根据它自己的转发策略，查找它的路由表。 如果这个路由表中有匹配的路由信息，那这个路由器就会把这个兴趣包从相应的端口 转发出去，并在它的等待兴趣表中加入一个表项，把这个兴趣包的到达端口加入到这 个等待兴趣表表项的端口列表中。

4)如果这个路由器的路由表中没有和这个兴趣包匹配的路由信息，那这个路由器 就会将这个数据包丢弃，并向它的上一跳发送错误报告，告诉它当前路由器无法转发 这个兴趣包。

数据包在网络中的传播过程如下：

1)当一个路由器收到一个数据包的时候，它会根据它的缓存策略来决定是否对这 个数据包进行缓存。如果缓存策略表明这个路由器需要对这个数据包进行缓存，那这 个路由器就会检查它的数据仓库。如果它的数据仓库已经缓存了这个数据包，那这个 路由器就会更新它的数据仓库中的数据包，比如刷新这个数据包的生命周期，(也可 以不更新)；否则这个路由器就会将这个数据包缓存到它的数据仓库中。如果它需要 缓存这个数据包，但是它的数据仓库已经满了，那这个路由器就会根据一定的策略将 原来的数据包替换出来。

2)接着，这个路由器考虑转发这个数据包。这个路由器查找它的等待兴趣表，如 果它的等待兴趣表中有和这个数据包匹配的表项，这个路由器就会将这个数据包从这 个表项的端口列表中的每一个端口转发出去。

3)如果这个路由器的等待兴趣表中没有和这数据包匹配的表项，这个路由器就会 丢弃这个数据包。

4)为实际部署命名数据网络首先需要解决的两个基本的问题是对网络中的数据的 缓存策略和对这些缓存的数据的路由策略。目前存在三种比较流行的缓存策略：

a)普遍缓存策略。使用这种缓存策略时，在数据包从数据提供者(可能是路由器 也可能是源服务器)到达用户的过程中，它所经过的每一个路由器都会对这个数据包 进行缓存。这个缓存策略已经被证明是低效的，因为它不仅会造成缓存的数据的严重 冗余和频繁替换，导致很多缓存的数据还来不及被再次利用就已经被替换出来。

b)最高中间度缓存策略。使用这种缓存策略时，我们首先给网络中的每个节点都 计算一个中间度(betweenness centrality)。统计证明，在实际网络中，一个节点的中 间度反映了经过这个节点的最短路径的数目。所以中间度越高的节点，经过它的最短 路径的数目也越多。在一个数据包从数据提供者传输到用户的过程中，我们总是把这 个数据缓存在中间度最高的节点上，这样被缓存的数据被再次访问的可能性最大。但 是这种缓存方式的一个缺点是按照这样的缓存方式会导致中间度高的节点的负担过 重，而中间度相对较低的节点的上的缓存空间却被闲置了，导致网络中路由器的缓存 空间没有得到充分利用。

c)远离提供者优先缓存策略。这是一种概率缓存方式。在数据包从数据提供者传 输到终端用户的过程中，我们给数据包的传输路径上的每个路由器都赋予一个缓存这 个数据包的概率；距离数据提供者比较远的路由器具有比较大的概率来缓存这个数据 包。这种缓存策略的思想是，我们总是把数据包优先缓存在靠近终端用户的位置，这 样可以用距离源服务器比较近的路由器上的缓存空间来缓存距离源服务器比较近的用 户的数据。但是这种缓存逻辑的有效性并不能得到广泛认可。因为我们完全可以认为 我们应该优先把数据缓存在靠近数据提供者的位置，这样这个数据可以被更多的用户 访问，因而能得到更高的利用率。

当前存在两种比较受到认可的两种路由策略分别是静态路由策略和链路状态路由 策略。

1)静态路由策略。这种路由策略就是完全不考虑命名数据网络中路由器上缓存的 数据。路由器每当收到一个兴趣包，总是将这个兴趣包向所请求的数据包的源服务器 的方向转发。如果这个兴趣包到达了一个路由器，并且这个路由器缓存了这个兴趣包 所请求的数据包，这个路由器就会返回这个数据包。

2)链路状态路由策略。这种路由策略实际上就是OSPF协议的在命名数据网络中 的应用。它的做法是每当一个路由器的数据仓库中的内容发生了改变，这个路由器都 会把这个信息通告到全网中。因此网络中的每个路由器都知道网络中任意一个路由器 中缓存的数据。在网络中每个路由器都知道全网的拓扑结构的前提下，一个路由器可 以通过Dijkstra算法算出到达每个数据包的最优路径所对应的下一跳。但是这种方法在 实际部署中是很难应用的，因为网络中的数据包会被频繁地缓存和替换，如果每一次 缓存和替换都向全网通告的话会在网络中产生巨大的网络流量，给网络带来巨大的负 担。而且在网络中存在大量的数据包(比路由器的数目要大很多)的情况下，要以数 据包为单位运行Dijkstra算法来计算最短路径的代价是很大的。

由于缺乏有效的缓存和替换策略，命名数据网络在实际网络中很难实现部署。寻 找一种有效的缓存和替换策略已经成为了命名数据网络中一个亟待解决的问题。

发明内容

本发明的主要目的在于针对现有技术的不足，提供一种基于选择性缓存的内容中 心网络动态路由方法。

为实现上述目的，本发明采用以下技术方案：

一种基于选择性缓存的内容中心网络动态路由方法，其中：

为命名数据网络中的路由器配置静态路由表和动态路由表，分别用于记录源服务 器中存放的数据和路由器中缓存的数据的路由信息；将数据包的名字定义成包含该数 据包的源服务器的标识符、该数据包的源文件的名字、该数据包的源文件分成的数据 包的个数、以及该数据包在它的源文件产生的数据包中的序号；

在将用户请求中的兴趣包从终端用户传输到数据提供者的过程中，由所经过的路 由器动态修改兴趣包中的信息来确定缓存路由器；当兴趣包最终到达数据提供者的时 候，兴趣包确定并记录从终端用户到数据提供者之间的距离，以及从终端用户到缓存 返回的数据包的缓存路由器之间的距离；在从数据提供者返回数据包的时候，数据提 供者将兴趣包中关于选择缓存路由器的信息复制到返回的数据包中；在数据包返回过 程中，每到达一个路由器，该路由器对数据包中记录的信息进行动态更新，利用更新 结果，数据包缓存在所确定的缓存路由器上。

在一个具体方面，明确定义了命名数据网络中数据包的名字的结构。将数据包的 名字定义成"server-name/file-name/packet-number/packet-sequence"的形式，其中 "server-name"是这个数据包的源服务器的标识符，"file-name"是这个数据包的源文 件的名字，"packet-number"是这个数据包的源文件分成的数据包的个数， "packet-sequence"是这个数据包在它的源文件产生的数据包中的序号。通过这样的命 名方式，不仅把关于这个数据包的源服务器的信息部分地融入了数据包的名字中，而 且把这个数据包的源文件产生的数据包的个数加入到这个数据包的名字中，这样的设 计有利于对存放在源服务器中的数据和缓存在路由器中的数据包进行路由。

在另一个具体方面，将路由器中的路由表分别分成了静态路由表和动态路由表， 分别记录源服务器中存放的数据和路由器中缓存的数据的路由信息。

在另一个具体方面，提出了使用哈希和局部决策来决定缓存路由器并实现缓存负 载平衡的缓存方案。在这种缓存方案中，只在每个兴趣包上增加了四个域，每个数据 包上增加了两个域，然后兴趣包在从终端用户传输到数据提供者的过程中，动态修改 兴趣包中的这四个域来决定缓存路由器；数据提供者在返回数据包的时候，它将兴趣 包中关于选择缓存路由器的信息复制到返回的数据包中。数据包在返回过程中这些信 息会被动态修改，从而将数据包缓存在预先确定的路由器上。通过这样的方式，不仅 有效减少了网络中的缓存冗余(因为在数据包从数据提供者传输到终端用户的过程中， 它至多只会被缓存一次)，而且实现了路由器上的缓存负载平衡。

在另一个具体方面，提出了一个为路由器中缓存的数据包建立动态路由信息的方 案。在建立动态路由信息的方案中，只为通过本路由器的数据包建立路由信息，建立 的路由信息不仅包括这些数据包存放的位置，而且还包括它们的存放位置和当前路由 器的距离，以及具有相同前缀的数据包在目标位置上缓存的数量。方案在为数据包建 立路由信息的同时没有给网络带来额外的负担。我们发现，来自相同文件的数据包的 缓存具有集聚的特性，所以在一个路由器上为一个文件至多只建立一个动态路由表项， 这在很大程度上保持了路由信息的准确性的同时极大地降低了动态路由表的规模。

在又一个具体方面，提出了一个基于概率的转发策略。这种转发策略为动态路由 表和静态路由表所提供的转发端口分别计算一个获取目标数据的转发延迟的期望，然 后选择转发延迟的期望最小的端口来转发兴趣包。

综上，本发明提出了一种在命名数据网络中进行选择性缓存和动态路由的策略， 把命名数据网络中数据的缓存和路由有机地结合在一起，在缓存数据的过程中为数据 建立动态路由信息。通过本发明，不仅充分利用了网络中路由器的缓存空间，实现了 负载平衡，而且在不给网络带宽带来额外的负担的情况下对路由器中的数据进行了有 效的路由。此外，还提出了一种基于概率的充分利用关于路由器中和源服务器中的数 据的路由信息的转发策略，以最大程度上减少终端用户请求一个数据所需要的延迟。 本发明只需要对兴趣包和数据包进行非常有限的修改，然后再通过一定的缓存策略， 就可以实现对路由器中缓存的数据的有效路由，并且不会给网络引入额外的流量。

附图说明

图1a和图1b为本发明实施例选择性缓存动态路由方案中的兴趣包和数据包的格 式；

图2为本发明实施例选择性缓存动态路由方案中的动态路由示意图；

图3为本发明实施例的缓存方案及动态路由示意图；

其中client₁至client₄为终端用户，youtube、serner为数据提供者，R₁到R₁₄为路由器。

具体实施方式

以下对本发明的实施方式作详细说明。应该强调的是，下述说明仅仅是示例性的， 而不是为了限制本发明的范围及其应用。

参阅图1a至图3，本发明的实施例主要包括两个方面，一个是对数据包进行缓存 并为其建立动态路由信息，另一个是利用这些路由信息对数据包进行转发。现将这两 种方案分别叙述如下。

1.相关数据结构

在本发明中，我们规定数据包的名字是 "server-name/file-name/packet-number/sequence-number"的形式。我们假定，每一 个数据包都只有一个唯一的源服务器；对于任意一个有效的数据包，这个数据包都可 以在它的源服务器中获取得到。这里的"server-name"就是这个数据包的源服务器的标 志符，它可以直接采用现在的IP网络中服务器的IP地址。在命名数据网络中，一个 数据包的大小是有限的，但是一个文件有时候会很大，所以我们经常需要将一个文件 分成若干个数据包，这里"file-name"即为这个数据包的源文件的文件名， "packet-number"是这个源文件所分成的数据包的个数，"packet-sequence"是这个数 据包在源文件产生的数据包中的序号。这里的"file-name"字段也可以是层次化结构 的。如果一个数据包的名字是"youtube/video/transformer/1000/0"，那就说明这个 数据包的源服务器的标识符是"youtube"，它的源文件的文件名是 "video/transformer"，这个文件被分成了1000个数据包，这个数据包是其中的序号 为0的数据包。

我们在路由器中构造了两个路由表，分别是动态路由表和静态路由表。静态路由 表记录了前往每个源服务器的最短路径的路由信息，具体来说就是前往每个源服务器 的最短路径所对应的下一跳，以及从当前路由器到源服务器的距离。静态路由表可以 用IP网络中的方法进行构造；因为静态路由表不是本发明的主要创新点，所以我们不 再这里对其进行进一步的论述，而把它的构造方法留在第六章。动态路由表则记录了 关于路由器中缓存的数据的路由信息。动态路由表的结构如表1所示。

表1动态路由表的结构

在动态路由表里，"prefix"是数据包的名字的前缀，在我们的发明里，我们采用的数 据包的名字前缀是"server-name/file-name/packet-number"部分。在表1中，对应于 前缀"prefix₁"有一个三元组(face₁，number₁，distance₁)，说明有number₁个具有前缀 prefix₁的数据包被缓存在某个路由器上，这个路由器可以通过端口face₁到达，这个路 由器和当前路由器的距离为distance₁。动态路由表的具体构造方法我们将会在下边叙 述。

2.缓存数据包并建立动态路由信息

如图1a和图1b所示，我们在命名数据网络的兴趣包的头部中添加了四个域，分别 是URD，ARD，WT和HV；同时我们在数据包的头部增加了两个域，分别是URD和ARD。 我们预先定义了一个哈希函数h。h能够把任意两个字符串哈希成一个在[0，1]之间均匀 分布的随机数。一个路由器有三个属性，分别是它的标志符ID(IDtifier)，它的数据 仓库的容量CP(CaPacity)和它的流行度PP(PoPularity)。

当一个用户要请求一个数据包时，它需要产生一个兴趣包并将这个兴趣包的四个域 URD，ARD，WT和HV都置为0，然后将这个兴趣包发送给它的代理路由器。这个兴趣包 每当到达一个路由器的时候，这个路由器首先都会将这个兴趣包的URD域的值增加1。 因此一个兴趣包的URD域的值记录了当前路由器到终端用户的距离。这里的距离和路 径的长度我们都用跳数来表示。对于链路上有权值的情况我们可以很容易通过扩展这 里讨论的方法来得出相应的结论。然后这个路由器查询它的数据仓库，检查它是否能 够提供这个兴趣包所请求的数据。我们首先讨论它不能提供这个兴趣包所请求的数据 包的情况。在这种情况下，这个路由器需要对这个兴趣包进行合适的处理，然后将这 个兴趣包进行转发。这个路由器首先把这个兴趣包的WT值赋给w₁，把这个兴趣包的 HV值赋给v₁，即

w₁＝I.WT，v₁＝I.HV。

然后这个路由器把这个它的数据仓库的容积和流行度的商赋给w₂，把它的标志符和这 个数据包的名字的哈希值赋给v₂，即

$w_2=\frac{R.\mathrm{CP}}{R.\mathrm{PP}},v_2=h(R.\mathrm{ID},I.\mathrm{name}).$

这里w₂是这个路由器缓存一个数据包的权值。这个路由器的数据仓库的容量越大，这 个路由器缓存一个数据包的概率就越大，因此它的权值就越大；反之，如果一个路由 器的流行度越高，经过它的数据越多，为达到路由器的缓存负载平衡，它缓存一个数 据包的概率就越小，因此它的权值就越小。这里我们把一个路由器的中间度作为它的 流行度；统计数据说明一个路由器的中间度和经过它的最短路径的数量在网络所有的 最短路径中所占的比例具有很强的相关性，所以我们这里简单认为一个路由器的中间 度和经过这个路由器的最短路径的数目在网络中所有的最短路径中所占的比例成正 比。

接着我们定义两个变量α₁和α₂并给它们赋值如下：

如果w₁＜w₂，则

${\alpha }_1=\frac{2w_1}{w_1+w_2},{\alpha }_2=1$

否则，

${\alpha }_1=1,{\alpha }_2=\frac{2w_2}{w_1+w_2}$

然后，我们比较α₁v₁和α₂v₂。如果α₂v₂＞α₁v₁，则我们将当前路由器选为所请求的 数据返回时的缓存路由器。于是我们将这个数据包的ARD值置为更新后的兴趣包的URD 值。ARD值的含义是我们选定的缓存数据包的路由器距离终端用户的距离。同时，我们 将兴趣包的HV值更新为v₂，将兴趣包的WT值更新为w₂值，即：

URD＝ARD，HV＝v₂，WT＝w₂。

以上算法可以描述如下

这样，当兴趣包最终到达数据提供者的时候，兴趣包的URD记录了从终端用户到数据 提供者之间的距离(以跳数计)，而ARD记录了从终端用户到我们选定的缓存返回的 数据包的路由器(以下简称为缓存路由器)之间的距离，此外，兴趣包的WT记录了缓 存路由器缓存一个数据包的权值，即它的数据仓库的容量和流行度的商，HV记录了这 个返回的数据包的名字和缓存路由器的标识符的哈希值。

下面我们证明按照这种方式选择缓存路由器，我们可以实现路由器的缓存负载平 衡，从而充分利用网络中路由器的缓存空间。

因为用户最初产生兴趣包I的时候，兴趣包I的WT值为0，所以当I到达用户的代理 路由器的时候这个路由器就会暂时被选为缓存返回数据包的路由器，因此兴趣包I中的 WT记录的是这个代理路由器的缓存一个数据包的权值，HV记录的是这个兴趣包的名字 和代理路由器的标识符的哈希值。现在假定当前被选定的缓存路由器是R₁，则这个兴 趣包WT记录的是R₁缓存一个数据包的权值，即它的HV记录的是R₁的标识符和 I的名字的哈希值，即h(R₁.ID，I.name)。现在兴趣包I到达一个新的路由器R_k并且R_k不 能提供I所请求的数据包，于是根据算法1，R_k给v₁，w₁，v₂，w₂赋值如下：

v₁←I.HV，w₁←I.WT

$v_2\leftarrow h(R_k.\mathrm{ID},I.\mathrm{name}),w_2\leftarrow \frac{R_k.\mathrm{CP}}{R_k.\mathrm{PP}}$

如果w₁＜w₂，则我们令

${\alpha }_1\leftarrow \frac{2w_1}{w_1+w_2},{\alpha }_2\leftarrow 1$

我们已经知道哈希函数h能够将任意两个字符串哈希成一个在[0，1]中均匀分布的 随机数，所以v₁和v₂是[0，1]内两个相互独立且均匀分布的随机数。路由器R_k重新选择 缓存路由器的时候，R₁被选中的概率为

$p\{{\alpha }_1{v}_1>{\alpha }_2{v}_2\}=p\{\frac{2w_1}{w_1+w_2}·v_1>v_2\}=\frac{w_1}{w_1+w_2}$

而R_k被选为新的缓存路由器的概率为

$p\{{\alpha }_1{v}_1\le {\alpha }_2{v}_2\}=1-p\{{{\alpha }_{1}v}_1>{\alpha }_2{v}_2\}=\frac{w_1}{w_1+w_2}$

所以R₁和R_k被选定为缓存路由器的概率之比为w₁∶w₂，即R₁和R_k缓存一个给定的 数据包的权值的比(添加一句话“为w₁∶w₂”)。很容易证明按照算法1，当w₁＞w₂时 也有相同的结论。

更进一步，假设从用户到数据提供者的路径上的路由器分别为R₁，R₂，...，R_n，为方便 起见，我们把它们缓存一个给定数据包的权重分别记为w₁，w₂，...，w_n，则它们被选定 为缓存返回的数据包的概率之比为w₁∶w₂∶...∶w_n。

我们假定经过每个路由器的路径和它的流行度成正比，并且每条路径上的数据流 量相等。对于两个路由器R₁和R₂，它们的流行度分别为PP₁和PP₂，它们的数据仓库 的容量分别为CP₁和CP₂，于是它们缓存一个给定的数据包的概率之比为假 定它们缓存一个数据包的概率分别为和其中δ是一个常数。假定通过R₁和R₂上的路径数分别为PP₁·ρ和PP₂·ρ，通过每个路径上的数据流量为λ。则缓存在R₁和R₂上的数据包数目的比值为

${\mathrm{PP}}_1·\rho ·\lambda ·\frac{{\mathrm{CP}}_1}{{\mathrm{PP}}_1}·\delta :{\mathrm{PP}}_2·\rho ·\lambda ·\frac{{\mathrm{CP}}_2}{{\mathrm{PP}}_2}·\delta ={\mathrm{CP}}_1:{\mathrm{CP}}_2$

即在这个简化模型下，每个路由器上缓存的数据和这个路由器的数据仓库的容积 成比例，于是我们实现了路由器上的负载平衡。

为了便于我们之后为缓存在路由器中的数据包建立动态路由信息，这里我们将数据包 的名字和路由器的标识符哈希成一个随机数的时候，我们实际上采用的是数据包的名 字的"server-name/file-name/packet-number"部分，所以同一个源文件的所有的数据 包的名字前缀和一个路由器的标识符进行哈希都会得到一个相同的哈希值，来自同一 个文件并且在同一条路径上进行传输的数据包都会选择相同的缓存路由器。

当兴趣包最终到达所请求的数据包的提供者的时候，数据包提供者把兴趣包的URD 和ARD的值分别赋给返回数据包的URD域和ARD域，并从这个兴趣包到达的端口将这 个数据包转发回去。

数据包每到达一个路由器，这个路由器都会把数据包的URD值减1，即这个数据包和终 端用户的距离减少了1。然后这个路由器比较数据包的URD值和ARD值，如果这个数据 包的URD值和ARD值相等的话，那就说明这个数据包已经到达了兴趣包在传播过程中 选定的缓存路由器，因此这个路由器将这个数据包的一份拷贝缓存在本地。否则如果 这个数据包的URD值小于ARD值，那就说明这个数据包已经在之前的路由器上被缓存 过了，并且这个数据包缓存的路由器和当前路由器的距离为ARD-URD，这个路由器 可以通过这个数据包的到达端口到达。反之，如果这个数据包的URD值大于ARD值， 那就说明这个数据包从每个转发端口转发的备份都将在以后的路由器中被缓存，并且 缓存路由器和当前路由器的距离都为URD-ARD，因此对应于这个数据包的每一个转 发端口，我们都为这个数据包建立相应的路由信息。

当这个路由器将这个数据包缓存在本地或者为这个数据包建立路由信息以后，这 个路由器会查询它的等待兴趣表，如果它的等待兴趣表中有匹配的表项，那它就会从 这个表项的端口列表中的每一个端口中转发一份这个数据包的拷贝。

我们处理一个数据包的方法如算法2所示。

从以上算法中可以看出，我们在为路由器中缓存的数据包建立动态路由信息的时 候，对于缓存在同一个路由器上的来自同一个文件的数据包，我们至多为它建立一个 路由表项(因为动态路由表项的前缀是数据包的名字的 "server-name/file-name/packet-number"部分)。一方面因为我们在实际生活极少会 请求一个单独的数据包，而一般都是请求整个文件；另一方面，我们在将数据包名字 和路由器的标识符进行哈希生成一个随机数的时候我们采用的是数据包的名字的 "server-name/file-name/packet-number"部分，所以同一个源文件的数据包会得到相 同的哈希值，经过同一条路径的同一个源文件的数据包会被缓存在相同的路由器上。 因此数据包的缓存表现出了集聚的性质，于是我们只需要为缓存在同一个路由器上的 来自相同文件的数据包建立一个路由表项。更进一步，为了方便实现，一个路由器只 记录了从它的每一个端口能到达多少个数据包，以及到达这些数据包的平均距离。这 样我们在很大程度上保持了动态路由信息的基础上，极大地减少了动态路由表的规模。

3.查询路由表以转发兴趣包

当一个路由器收到一个兴趣包的时候，这个路由器考虑转发这个兴趣包。因为现在路 由表中有一个静态路由表和一个动态路由表，分别记录了关于存放在源服务器中的数 据和缓存在路由器中的数据的路由信息。我们考虑综合利用这两种路由信息，在不增 加网络负担的条件下，尽量减少终端用户请求一个数据包的延迟。

假设路由器R收到了兴趣包I，R通过查询静态路由表知道所请求的数据包的源服 务器对应的转发端口是face₁，从路由器R到达源服务器的距离为dist₁。我们假定一个 数据包总是能够在它的源服务器中被找到。所以如果路由器R将兴趣包I从端口face₁转 发，则路由器R取回所请求的数据包需要的延迟的期望是2·dist₁。假设路由器R查询 它的动态路由表，知道从当前路由器到某个可能缓存了所请求的数据包的路由器的距 离为dist₂，转发端口为face₂，有m个和所请求的数据包具有相同的前缀的数据包缓 存在了目标路由器上，而根据I的名字可知所请求的数据包的源文件一共产生了n个数 据包。因此如果R将这个兴趣包从端口face₂进行转发，如果所请求的数据包缓存在了目 标路由器上，那路由器R取回所请求的数据包的延迟是2·dist₂，这种情况发生的概率 是如果所请求的数据包不存在于目标路由器上，那么路由器R收到错误报告以后， 它需要再次向数据包的源服务器请求这个数据包，所以路由器R取回所请求的数据包的 延迟是2·dist₁+2·dist₂，这种情况发生的概率为所以路由器R从端口face₂转发 兴趣包时取回所请求的数据包的期望为

$\frac{m}{n}·{2\mathrm{dist}}_1+\frac{n-m}{n}·({2\mathrm{dist}}_1+{2\mathrm{dist}}_2)$

这样我们就可以计算出从每个端口(包括静态路由表提供的端口和动态路由表提 供的端口)转发这个兴趣包时取回所请求的数据包的延迟的期望。我们总是优先选择 延迟最小的端口来转发这个兴趣包。这样我们就可以在概率上最小化我们请求一个数 据包所需要的延迟。

本发明实施例只需要对兴趣包和数据包进行非常有限的修改，然后再通过一定的 缓存策略，就可以实现对路由器中缓存的数据的有效路由，并且不会给网络引入额外 的流量。在具体实施的过程中，可分成如下几个模块：

(1)规定数据包的命名格式

在我们的方案中，我们明确规定了数据包的命名格式，即数据包的名字是 "server-name/file-name/packet-number/packet-sequence"的形式，其中"server-name"是数据 包的源服务器的标识符。在我们方案中我们假定每个数据包都有唯一的一个源服务器， 并且任何一个有效的数据包都能够在它的源服务器中被找到。所以当我们拿到一个兴 趣包的时候，我们总是能够知道往哪里去获取所请求的数据包。数据包名字的 "file-name"字段是这个数据包的源文件的名称。这个字段可以是层次化的。这个文件的 所有者可以以任意一种方式给这个文件命名。"packet-number"字段是源文件所分成的数 据包的个数。"packet-sequence"字段是这个数据包在源文件生成的数据包中的序号。我 们用这个字段来区分同一个文件的不同的数据包。因为我们往往不能把一个文件完全 存放在一个路由器上，很多时候一个路由器上只缓存了一个文件的数据包中的部分数 据包。所以我们把"packet-number"这个字段加入到数据包的名字中，这样当我们在一个 路由器上存放了若干同一个文件的数据包的时候，我们就可以有效地估计我们在多大 程度上保存了这个文件的数据，以及如果有个用户请求一个这个文件的数据包的时候， 这个路由器能够提供这个数据包的可能性有多大。因为数据包的这四个字段对数据包 的所有者都是已知的，所以在数据包所有者创建这个数据包的时候可以很方便地给这 个数据包命名。一般情况下，如果源文件被分成了n个数据包，这些数据包的 "packet-number"字段为n，这些数据包的"packet-sequence"的值分别从0到n-1。

(2)将路由表分成静态路由表和动态路由表

与传统的命名数据网络中的路由表不同，在我们的方案中，我们把路由器中的路 由表明确分成了静态路由表和动态路由表，分别负责对源服务器和路由器中的数据的 路由。静态路由表表项是(server-name,face,distance)的形式，其中"server-name"是一个 源服务器的标识符，"face"是前往这个源服务器的路径所对应的转发端口，"distance" 是从当前路由器到这个源服务器的距离。注意到一个数据包的名字的最高层的前缀正 是它的源服务器的标识符，并且一个数据包总是能够在它的源服务器中被找到，所以 当一个路由器拿到一个兴趣包的时候，如果这是一个有效的兴趣包，那这个兴趣包的 名字的最高层的前缀就一定存在于静态路由表中，所以在没有关于这个兴趣包的动态 路由信息的情况下，这个路由器可以像在IP网络中一样将这个兴趣包转发向所请求的 数据包的源服务器。在存在关于所请求的数据包的动态路由信息的情况下，通过 "distance"属性即当前路由器到源服务器的距离，当前路由器还能决定它是要用静态路 由表提供的端口还是动态路由表提供的端口来转发这个兴趣包。

静态路由表可以用现有的技术和基础设施很方便地实现。一个可选的方案是，在 用BGP,OSPF等IP网络中的协议来计算出了一个IP网络中的路由表以后，对于每一 个源服务器，我们通过DNS服务得到它的IP地址，然后我们就可以通过查询IP路由 表来确定到达前往每一个源服务器的最优路径所对应的端口以及从当前路由器到这个 服务器的距离。或者我们直接用一个源服务器的IP地址作为这个源服务器的标识符， 这样我们就可以把IP路由表作为命名数据网络的静态路由表了。因为静态路由表的构 造方法比较直观，所以我们并不把静态路由表的构造作为本发明的创新点。

动态路由表的结构如表1所示。动态路由表的每个表项对应于一个数据包的前缀， 这里的前缀我们采用的是一个数据包的名字的"server-name/file-name/packet-number"部 分，因此每一个源文件在同一个动态路由表中至多对应于一个动态路由表表项。动态 路由表中对应于每一个前缀"prefix"都有一个动态路由信息列表，这个列表由若干个 (face,number,distance)这样的三元组构成。在每一个这样的三元组中，"face"表示经过 哪一个端口可以到达缓存了这些数据包的路由器，"number"表示有多少个具有前缀 "prefix"的数据包被缓存在了目标路由器，"distance"表示当前路由器和目标路由器之间 的距离。这里的目标路由器并不一定是一个单一的路由器；也许从当前路由器的某个 端口出发的若干个路由器都缓存了具有前缀"prefix"的数据包，但是我们只给这些路由 器上缓存的数据包维护了一个三元组，这个三元组的"distance"是当前路由器到这些路 由器的所有数据包的平均距离。动态路由表需要通过我们以下提出的缓存策略和动态 路由信息构造策略构造。

(3)定义兴趣包和数据包的格式

兴趣包和数据包的结构如图1a和图1b所示。我们在兴趣包中增加了四个域，分 别是URD，ARD，HV和WT。其中URD表示当前路由器到终端用户的距离，ARD 表示我们目前选定的缓存路由器到终端用户的距离，HV表示这个数据包的名字的 "server-name/file-name/packet-number"部分和缓存路由器的标识符的哈希值，WT表示 缓存路由器缓存一个数据包的权值。当一个用户产生一个兴趣包的时候，这个新产生 的兴趣包的URD，ARD，HV和WT四个域的值都为0。在这个数据包从终端用户传 输到数据包的提供者的过程中，我们的缓存策略会不断选择新的路由器作为缓存路由 器，所以兴趣包的这四个域会不断地进行更新。

我们在数据包中加入了另外两个域URD和ARD。和兴趣包一样，这两个域的意 义分别为当前路由器和缓存路由器到终端用户的距离。当兴趣包最终到达所请求数据 包的提供者的时候，URD和ARD分别记录了终端用户到数据包提供者和数据包的缓 存路由器的距离。接着，数据包提供者把兴趣包的URD域和ARD域的值分别复制到 返回的数据包的URD域和ARD域中。当这个数据包返回的时候，URD域的值会逐跳 减少，而ARD域的值则保持不变。这样这个数据包每到达一个路由器，这个路由器都 能够很方便地计算当前路由器和缓存路由器之间的距离。我们正是利用了这一信息来 为缓存在路由器中的数据包来构造动态路由信息。

(4)定义路由器的属性

在我们的方案中，我们假定每个路由器都有三个属性，分别是这个路由器的标识 符，这个路由器的数据仓库的容量和这个路由器的流行度。一个路由器的标识符唯一 地标识了这个路由器。这个路由器的数据仓库的容量决定了这个数据仓库最多能够缓 存多少数据包，当路由器的数据仓库满了以后还要缓存新的数据的时候，就需要把数 据仓库中的某些数据包替换出来。一个路由器的流行度则表明了通过这个路由器的路 径的数目，从而进一步表明了通过这个路由器的数据包的数量。给定一个数据包，一 个路由器的容积越大，我们希望它缓存这个数据包的概率越大，而一个路由器的流行 度越高，我们希望它缓存这个数据包的概率越小。我们可以简单地认为一个路由器的 流行度是和它连接的边的数目，或者我们也可以借用社交网络中的概念，把一个路由 器的中间度(betweenness centrality)作为这个路由器的流行度。

(5)缓存路由器选择策略

在一个数据包从数据包的提供者传输到终端用户的过程中，这个数据包至多会被 缓存在这条路径上唯一的一个路由器上。这个路由器是在兴趣包在从终端用户传输到 数据包提供者的过程中确定的。当一个用户产生一个兴趣包的时候，这个兴趣包的 URD，ARD，HV，和WT的值都为0。然后每当这个兴趣包到达一个新的路由器的时 候，这个路由器会把这个兴趣包的URD值增加1，这样这个兴趣包的URD域就记录 了从终端用户到当前路由器的距离。然后，这个路由器开始查询它的数据仓库，如果 它的数据仓库中不存在这个兴趣包所请求的数据包，那这个路由器就需要对这个兴趣 包进行相应的处理，然后再转发这个兴趣包。路由器对数据包的处理过程如下：

这个路由器把这个兴趣包的HV域的值赋给v₁，把这个兴趣包的WT域的值赋给 w₁，然后把这个兴趣包的名字的"server-name/file-name/packet-number"部分和这个路由 器的标识符的哈希值赋给v₂，把这个路由器的缓存这个数据包的权值即它的数据仓库 的容量和流行度的商赋给w₂。接着这个路由器给两个变量α₁和α₂赋值如下：

如果w₁＜w₂，则

${\alpha }_1=\frac{2w_1}{w_1+w_2},{\alpha }_2=1$

否则，

${\alpha }_1=1,{\alpha }_2=\frac{2w_2}{w_1+w_2}$

然后这个路由器比较α₁v₁和α₂v₂的值，如果α₂v₂≥α₁v₁，那么这个路由器就被选 为新的缓存路由器，于是它将这个兴趣包的ARD的值更新为URD的值，将这个兴趣 包的HV值更新为v₂，将这个兴趣包的WT值更新为w₂。我们可以证明，在每一个路 由器的流行度和经过它的路径数目成比例，并且每条路径上的数据流量大小相等的假 设下，我们所提出的这种选择缓存路由器的方案能够达到网络中路由器的(添加一个 词“缓存”)负载平衡，也就是每个路由器上缓存的数据量和它的数据仓库的容积成比 例。

(6)传输数据包并为其建立动态路由信息

在命名数据网络中，每一个路由器都维护了一个等待兴趣表。等待兴趣表的每一 个表项都是(name，face_list)的形式。这里的"name"是这个兴趣包的名字，"face_list"是 名字为"name"的兴趣包的到达端口列表。

如果一个路由器收到一个兴趣包并且这个路由器无法提供这个兴趣包所请求的数 据包，这个路由器就会首先检查它的等待兴趣表中是否有和这个兴趣包匹配的表项。 如果它的等待兴趣表中已经有和这个兴趣包匹配的表项，那么它就会直接把这个兴趣 包的到达端口加入到这个表项的端口列表中，而不转发这个兴趣包；否则这个路由器 就会把这个兴趣包从合适的端口转发出去，并且新建一个等待兴趣表表项，把这个数 据包的名字和它的到达端口存放到这个表项中。所以当这个兴趣包所请求的数据包返 回的时候，这个数据包每到达一个路由器，这个路由器都会查询它的等待兴趣表。对 于匹配的等待兴趣表表项的端口列表中的每一个端口，这个路由器都会从中转发一个 这个数据包的拷贝。借助于等待兴趣表，一个数据包从提供者返回到终端用户所经过 的路径恰好是原来相应的兴趣包所经过的路径。

在我们的方案中，在一个路由器转发一个数据包之前，这个路由器需要首先对这 个数据包进行额外的处理，以决定应该缓存这个数据包还是为这个数据包建立动态路 由信息。一个数据包每到达一个路由器，这个路由器首先将这个数据包的URD值减1， 所以这个数据包的URD值记录了当前路由器到终端用户的距离。注意到这个数据包的 ARD值记录的是原来兴趣包传输过程当中选定的缓存路由器到终端用户的距离。这个 路由器会比较这个兴趣包的URD和ARD的值，如果这个数据包的URD值和ARD值 相等，那就说明这个数据包已经到达了原来兴趣包选定的缓存路由器，所以这个路由 器就会把这个数据包的一份拷贝缓存起来。否则，如果这个数据包的URD的值大于这 个数据包的ARD的值，那就说明这个数据包还没有到达原来选定的缓存路由器，也就 是说这个数据包将会在以后的路由器中被缓存起来，并且缓存路由器和当前路由器的 距离为URD-ARD。因为这个数据包将会被从匹配的等待兴趣表项的端口列表的每个 端口中转发出去，所以这些缓存路由器能够通过匹配的等待兴趣表项的端口列表中的 每个端口到达。如果URD的值小于ARD的值，那就说明这个数据包已经在之前的路 由器上被缓存过了，并且缓存路由器到当前路由器的距离为URD-ARD，这个缓存路 由器可以通过这个数据包的到达端口到达。

现在假设我们知道一个数据包的缓存路由器到当前路由器的距离为distance_x，这 个缓存路由器可以通过端口face_x到达。我们简单将这个数据包的名字的 "server-name/file-name/packet-number"部分记为prefix_x。我们已经知道路由器的动态路 由表中，对应于每一个前缀prefix是一个(face,number,distance)这样的三元组的列表， 其中face表示缓存了具有前缀prefix的数据包的路由器可以由哪个端口到达，number 表示有多少个具有前缀prefix的数据包被缓存在了目标路由器上，distance表示当前路 由器到目标路由器的距离。如果当前路由器中没有关于前缀prefix_x的路由表项，那这 个路由器为前缀prefix_x建立一个动态路由表项，并在这个动态路由表项中插入一个三 元组(face_x，1，distance_x)。如果动态路由表中已经存在了关于prefix_x的动态路由表项， 那么这个路由器就会进一步检查这个表项中有没有存在和转发端口face_x对应的三元 组，如果不存在对应的三元组，这个路由器就会在这个路由表项中加入一个三元组 (face_x，1，distance_x)。否则，如果已经存在了一个对应于转发端口face_x的三元组，假设 这个三元组为(face_x，number_xx，distance_xx)，那这个路由器将更新这个三元组如下：

${\mathrm{dis}\tan \mathrm{ce}}_{\mathrm{xx}}\leftarrow \frac{{\mathrm{dis}\tan \mathrm{ce}}_{\mathrm{xx}}·{\mathrm{number}}_{\mathrm{xx}}+{\mathrm{dis}\tan \mathrm{ce}}_x}{{\mathrm{number}}_{\mathrm{xx}}+1}$

number_xx←number_xx+1

(7)兴趣包转发策略

一个路由器收到一个兴趣包的时候，如果这个兴趣包所请求的数据包是一个有效 的数据包，那这个路由器的静态路由表中就应该维护了到达所请求的数据包的源服务 器的路由信息。如果每个路由器都按照他们的静态路由表中的路由信息来转发这个兴 趣包，那么这个兴趣包最终将到达所请求的数据包的源服务器。当一个路由器中包含 了关于所请求的数据包的动态路由信息的时候，我们考虑充分利用静态路由表中的路 由信息和动态路由表中的路由信息来尽量减少终端用户请求这个数据包所需要的延 迟。

在我们的兴趣包转发策略中，我们采用了一种基于概率的转发策略。如果静态路 由表提供的转发端口是face₁，从当前路由器到源服务器的距离为distance₁，那假如 我们从端口face₁转发这个兴趣包，我们取回所请求的数据包所需要的延迟是 2·distance₁。我们已经知道动态路由表中每一个路由表项对应于一个数据包的名字的 "server-name/file-name/packet-number"部分，并且每一个动态路由表项都对应于一 个(face，number，distance)这样的三元组的列表。假设动态路由表提供的端口是face₂， 当前路由器到目标路由器的距离为distance₂，有m个和这个兴趣包有相同的名字前 缀的数据包缓存在了目标路由器，而源文件一共产生了n个数据包。如果我们从face₂转 发这个兴趣包，假设所请求的数据包存在于目标路由器上，我们取回这个数据包所需 要的延迟是2·distance₂，而所请求的数据包存在于目标路由器上的概率为如果 所请求的数据包不存在于目标路由器上，那么当前路由器在收到找不到数据包的错误 报告后还需要向数据包的源服务器请求这个数据包，这个时候取回数据包所需要的延 迟是2·distance₁+2·distance₂，这种情况发生的概率为所以如果我们采用动 态路由表提供的路由信息来转发这个兴趣包的话我们取回数据包所需要的延迟的期望 为$\frac{m}{n}·{2\mathrm{dis}\tan \mathrm{ce}}_1+\frac{n-m}{n}·({2\mathrm{dis}\tan \mathrm{ce}}_1+2{\mathrm{dis}\tan \mathrm{ce}}_2).$所以通过这种方式我们可以给动 态路由表和静态路由表提供的每一个端口计算获取目标数据包所需要的延迟的期望， 然后我们选择延迟期望最小的端口来转发这个兴趣包。

在图2中，终端用户client₃产生了一个兴趣包来请求名字为

"youtube/transformer/100/2"的兴趣包。当这个兴趣包到达R₃的时候，R₃通过查询静 态路由表知道它到源服务器的距离为4，所以它向源服务器请求这个数据包所需要的延 迟为8；R₃查询动态路由表知道有40个前缀为"youtube/transformer/100"的数据包 被缓存在了某个路由器，这个路由器可以通过前往R₂的端口到达，这个路由器距离R₃的 距离为1。我们从兴趣包的名字中可以知道源文件一共被分成了100个数据包，所以如 果R₃向R₂转发这个兴趣包，R₃取回所请求的数据包所需要的延迟的期望为6.8。所以R₃将把这个兴趣包转发到R₂。

(8)设置数据包为不缓存

在我们的缓存方案，每一次数据包从数据提供者传输到终端用户，这个数据包都会在 它的传输路径上的一个路由器上被缓存。在模拟实验过程中，我们发现这种缓存方案 仍然会引起严重的缓存冗余，原因是使用这种缓存方案时，一个数据包被连接在同一 个边缘路由器上的用户请求了多次以后，这个数据包就会被缓存在了这个边缘路由器 上。而在实际网络中，一个数据包被同一个局域网中的用户在一段比较短的时间内访 问多次这是比较普遍的，结果就导致了很多数据在竞争邻近用户的路由器，而远离用 户的路由器的缓存空间则没有受到充分的利用，所以在实际的部署中我们提出了一种 简易的方案来缓解这个问题。

当数据包的提供者收到一个兴趣包的时候，在返回数据包之前，它会首先检 查这个兴趣包的URD和ARD的值。如果这个兴趣包的的值超过了一定的阈值，那就 说明这个兴趣包在传输过程中选择的缓存路由器距离数据包的提供者太近，因此为了 避免缓存冗余，我们把这个数据包的ARD值置为-1。当以后的路由器收到这个数据包， 发现它的ARD值为-1的时候，这些路由器将不会缓存这个数据包，也不会为这个数据 包建立动态路由器信息。在我们的实验中，我们选择的阈值是黄金分割比即0.618。所 以如果数据提供者发现对于一个兴趣包有则这个数据提供者就会把返回 数据包的ARD值置为-1，因此这个数据包的返回路径上的路由器既不会缓存这个数据 包，也不会为这个数据包建立动态路由信息。在图3中，终端用户client₁要请求一个 数据包，因此他发出了一个兴趣包。这个兴趣包最终在server上得到了满足，并且在兴 趣包的传输过程当中，R₁被选为了缓存路由器。当server收到这个兴趣包的时候，他发 现这个兴趣包的ARD值为4，URD值为5，因此因此server把返回 数据包的ARD值置为-1，这个数据包的返回路径上的路由器既不会缓存这个路由器， 也不会为这个路由器建立路由信息。终端用户client₃请求一个数据包，被选中的缓存路 由器为R₁，因为缓存路由器距离数据提供者太近，所以server把返回的数据包的ARD值 置为-1，因此返回的数据包将不会被缓存。

(9)对等待兴趣表的改进

在按照以上所描述的方式来构造动态路由表的过程中，我们建立的动态路由信息 依然会存在明显的误差。比如在图3中，如果终端用户发出了一个兴趣包来请求某一 个数据包，这个兴趣包最终在server上得到了满足。在兴趣包从client₂传输到server的 过程中，我们的缓存策略选择了路由器R₁₀作为了缓存路由器。这个时候，终端用户 client₁也产生了一个兴趣包以请求相同的数据包。在返回的数据包到达R₄之前，client₁的兴趣包也到达了R₄，于是R₄把这个兴趣包的到达端口加入了它的等待兴趣表中相应 的表项。当返回的数据包到达R₄的时候，根据命名数据网络自身的机制，R₄会从到达R₇和R₈的端口分别转发一份这个数据包的拷贝。我们注意到这个数据包中关于缓存路由 器的信息是根据从client₂到server的路径建立的，且选定的缓存路由器是R₁₀，所以对 于转发给R₇的数据包的拷贝，当它到达路由器R₇的时候，它发现数据包的URD的值为 2，ARD的值为1，所以它并不会缓存这个数据包，而是为这个数据包建立了相应的动 态路由信息，这个路由信息指向前往client₁的端口。但是我们知道R₇之后不会再有路 由器来缓存这个数据包了，于是R₇记录了错误的路由信息。为了解决这一问题，我们 在模拟实验室中(也将应用于实际部署中)，我们对等待兴趣表的结构进行了一定的 改变。

name₁(face₁,distance₁),(face₂,distance₂),… name₂(face₃,distance₃),(face₄,distance₄),…

表2本方案中等待兴趣表的结构

本方案中的等待兴趣表的结构如表2所示。当一个路由器收到一个兴趣包，并且这个 路由器不能提供这个兴趣包所请求的数据包时，如果它的等待兴趣表中没有和这个兴 趣包对应的表项的话它会为这个兴趣包建立相应的表项并记录关于这个兴趣包的相关 信息，或者如果它的等待兴趣表中已经有了和这个兴趣包相应的表项的话，这个路由 器就会直接记录关于这个兴趣包的相关信息，然后将这个兴趣包丢弃。在我们的方案 中，我们为一个兴趣包记录的信息不仅包括这个兴趣包的到达端口，而且还包括这个 兴趣包和产生它的终端用户的距离，具体而言就是这个兴趣包所携带的URD的值。在 表2中，对应于name₁有一个二元组(face₁，distance₁)，这说明路由器收到了一个兴趣 包，这个兴趣包的名字为name₁，它的到达端口为face₁，这个兴趣包的URD值为 distance₁。

这样当一个路由器收到一个数据包的时候，它考虑转发这个数据包。这个路由器 会查询它的等待兴趣表，如果它得到和它匹配的等待兴趣表表项中有一个二元组 (face_x，distance_x)，并且distance_x小于等于这个数据包的URD的值，这个路由器就会 把从端口face_x转发出去的拷贝的ARD值置为-1，因此对应于端口face_x的后继的路由器 都不会缓存这个数据包，也不会为这个数据包建立相应的动态路由信息。

本发明能够在不给网络中引入额外的流量的条件下为缓存在路由器中的数据建 立路由信息，为解决命名数据网络中对路由器中缓存的数据的路由问题提供了一个有 效的方案，大幅度降低了终端用户请求一个数据包的延迟，极大地减小了源服务器的 负荷，并且路由器中缓存的数据的利用率也大大提高。通过模拟实验证明，在最好情 况下，相比IP网络终端用户请求一个数据包的延迟减少了34％，源服务器的负荷减少 了80％，每个被缓存的数据包平均被使用了0.8次。而使用最初提出的命名数据网络中 的普遍缓存策略和静态路由策略时，终端用户请求一个数据包的延迟减少了19％，源服 务器的负荷减少了43％，每一个被缓存的数据平均被缓存了0.04次。可见我们提出的 方案的性能要远远优于命名数据网络中的普遍缓存策略和静态路由策略。此外，本方 案还能够使路由器中缓存的数据和路由器的数据仓库容量成比例，有效地实现网络中 路由器的缓存负载平衡。

以上内容是结合具体/优选的实施方式对本发明所作的进一步详细说明，不能认 定本发明的具体实施只局限于这些说明。对于本发明所属技术领域的普通技术人员来 说，在不脱离本发明构思的前提下，其还可以对这些已描述的实施方式做出若干替代 或变型，而这些替代或变型方式都应当视为属于本发明的保护范围。