将来自远程发送者的数据流传递到远程目的地的方法

摘要

本发明涉及一种通过通信网络将来自远程发送者的数据流传递到远程目的地的方法。该方法包括：确定输入数据流中的至少一个锚，锚是数据在所述输入数据流中的位置的指示，在所述位置处，数据流中的字符组符合预定的标准；所述锚是指示所述输入数据流中相应预定数据范围的基准点，所述预定数据范围用于计算识别所述数据流中相应数据块的数字签名；所述预定数据范围由独立于块大小的多个字节组成；根据所述数据流中的所述预定数据范围计算所述数字签名；并且使用所述数字签名识别包括与所述输入数据流中的数据片段大体相同的数据片段的先前存储的数据块；且用所述先前存储的数据块中的相应数据片段替换对所述输入数据流中的数据片段的位置的引用。

说明书

本申请依据专利法实施细则第四十二条提出，是国际申请日为2005年3月2日、 国际申请号为PCT/IL2005/000247、国家申请号为200580012347.7的发明名称为“用 于减少通信网络上的传输量的通信服务器、方法和系统”的中国发明专利申请的分案 申请。

技术领域

本发明涉及经通信网络的数据传输领域，更具体地讲，涉及减少这种数据传输的 量的领域。

背景技术

第60/548,855号美国临时专利申请的背景技术章节通过引用包含于此。

减少带宽是ISP（互联网服务提供商）、家庭用户、内容提供商和拥有网络的几 乎每个组织的主要期望。由于实际上根据通信线路传输的数据的量来租用它们，所以 带宽就意味着成本。对于承租人而言，占用的带宽越少，在租借通信线路上花费的钱 就越少。对于带宽提供商而言，给定数量的用户在线路上传输的数据量较小，意味着 在不降低服务质量的情况下还可以签约额外的用户。

第2002/0184333号美国专利公报（以下称作D1）旨在改进通信网络的性能。D1 要解决的问题是多个请求者可能发送针对相同文件的请求的情况，其中，每个请求发 往引用不同的URL或甚至不同文件名称的不同的提供商。在传统的缓存（caching） 中，将这多个请求视为对不同文件的请求，这导致多个文件分别被传递。

根据D1发明，在从多个源中的各个源接收到完整的文件后，将分配一数字签名， 进而该数字签名将被识别为与从其它源中的任何一个接收到的相同文件的数字签名 相同。因此，通过从本地存储在缓冲服务器中的单个拷贝中检索该文件将会满足来自 多个提供商中的任何一个的对该文件的更多请求。这种改进在于：通过对被频繁请求 的文件进行缓存，以响应于请求者的查询将这些文件返回给请求者，其中，根据分配 给各个文件的数字签名来索引这些文件，因此，可以避免在从多个源检索一个文件的 情况下，多个缓存和多个提供商服务器传递相同的文件。

正如可理解的那样，为了能够将不同的请求形式和一个被请求的文件相关联， D1需要将缓冲的文件识别两次：第一次是根据它的数字签名，第二次是根据已知的 与该文件相关联的所有URL或文件名称。在接收到对相同文件的请求而该系统不熟 悉该请求的情况下，只有通过从该请求所指示的位置检索该文件才能满足该请求，并 且只有曾经将该文件检索并识别为本地存储文件的拷贝后，才能将该请求所指示的文 件名称或URL与该本地文件相关联以在将来使用（即，用于未来的相似请求）。D1 的另一缺点在于，存储在某些提供商计算机中的文件会改变，而中间节点继续向请求 者提供旧版本的本地存储文件，而没有意识到所述改变。

国际专利申请第WO 95/19003号公报（以下称作D2）涉及接收计算机具有旧文 件、而发送计算机具有新文件的情况，其中，两个文件的一部分可能是相同的。为了 使接收计算机可以将该旧文件更新为与该新文件相同，需要至少将新文件中与旧文件 的任何部分都不相同的那些部分发送到接收计算机。为了使接收计算机和发送计算机 都能够比较该文件的哪些部分不需要发送（从而加快发送过程的速度），作为预备步 骤，接收计算机需要将旧文件划分为段，对每个段计算散列数并将这些散列数发送到 发送计算机。然后发送计算机必须对“在新文件中的各个可能段”（第7页第23-24行） 计算散列数，然后将这些散列数与从接收计算机接收到的散列数进行比较。

正如可以理解的那样，D2旨在根据从发送方接收到的新文件的段和存在于接收 计算机上的预先指定的旧文件的已有段，在接收计算机上重构文件，以使结果为在接 收计算机上得到该新文件的拷贝。第5,721,907号美国专利的目标与D2相似。D1至 D3均与期望从另一计算机获得预定的被请求文件（或文件的部分）并将其存储在接 收计算机上的该接收计算机相关。当已知一文件还具有已知的起始点和终点时，可将 其用作已知范围的数据上的用于计算数字签名的基准位置。

发明内容

与现有技术不同，本发明旨在发起实时数据流的传输缩减，即，减少数据流的量， 该数据流的内容是匿名的，并且发起所述缩减的计算机还无法将该内容识别为文件或 文件的一部分。例如，参照实况视频广播，其中，多个接收计算机实时接收相同的内 容，因为由于在实时创建数据的这种情况下到处都没有任何实际的“文件”，因而中间 节点在其缓存中没有将被检索的文件，所以D1所公开的系统和方法不能减少网络中 的传输量。

由于在接收计算机中不存在其一部分可能与期待的数据相同的“旧文件”，所以 D2和D3的发明也与这种情况无关。

在本发明的上下文中，锚（Anchor）是根据数据流的符合预定标准的内容而确定 的在数据流中的位置。将该标准设置为在预定量的数据上出现锚的概率令人满意。

锚定-由预定函数（以下也称作“锚定函数”）返回的登记值用于检查其位置与锚 相关的预定范围的内容。选择该函数和该数据范围，从而可以以令人满意的概率将返 回的值用作识别所述内容的签名。

本发明涉及一种方法和系统，用于在当前通过通信服务器的数据流的匿名内容之 间以及在已经通过所述服务器并本地存储的相似内容之间进行同步，从而可以消除所 述数据流的一定量的传输。

根据某些实施例，该同步还在同时通过该服务器的相似数据内容的几个拷贝之间 进行。本发明的系统包括至少一个服务器，该至少一个服务器能够减少线路内的网络 传输的量，这是该服务器为了实现量的缩减而自己发起的过程的结果，该过程不需要 关于数据的源、数据的类型、数据的名称或数据的任何其它识别细节的信息。这与所 期望的量的缩减取决于文件名称或路径，以使得所请求的文件和本地存储的文件可以 同步的方法相反。另外，当已知要发送的文件还具有已知的起始点和结束点时，可将 其用作在预定的数据范围上用于计算数字签名的基准位置。在其内容没有所有人都赞 同的起始点或结束点的匿名数据流的情况下（如在根据本发明的情况下），没有允许 计算可重复的数据签名的赞同的基准点。如果数字签名无法重复，则不能用它来识别 内容。正如将要进一步解释的，根据本发明的服务器包括解决这个问题的锚确定单元。

对于通过服务器的数据流的特定部分的另外使用，根据本发明的服务器（以下也 称为“匿名数据缓存服务器”或“ADC服务器”）存储数据的这些部分，而不知道文件 名称、全部数据、URL、文件类型和数据起点或目的地。根据本发明，服务器只存储 纯数据，而不存储从外部文件请求者或文件提供者接收的ID标记。

根据本发明的系统包括具有通信电路的通信服务器和至少一个其可访问的存储 器介质，其中，所述通信电路用于接收和传送数据流。

锚确定单元设置在服务器中，能够确定数据流中的、来自该流的预定义的字符组 符合预定的标准的位置，这些组的位置被确定为锚（以下还称作“基准点”）。

该服务器还包括：

锚定函数单元，用于返回作为流中的数据范围的内容的函数的值（以下还将称作 “数字签名”），其中，所述范围相对于所述锚具有已知相关性（当搜索所述内容时， 所述值就有帮助了）；

数据划分单元，用于将数据流划分成数据块；

登记单元，用于存储从锚定函数单元返回的值的列表，其中，通过适当的引用将 各个值与指定数据块相关联，所述指定数据块包含这样的数据范围，锚定函数根据该 数据范围返回所述值（与块有关的各值在本发明的上下文中将被称作“块ID”，并在 某些特定的情况下被称作“散列键”）。

根据本发明的各种实施例，在正常的情况下，多个块ID与各个数据块相关联。

根据本发明的一个实施例，所述块划分单元将数据划分成预定大小的块。例如， 所述预定大小可选择为64K的数据。

根据另一实施例，为了提高在不同的服务器上包含相似数据的块之间的兼容性， 并避免在每次发送所述块时对该数据进行不同的划分，所述划分单元将块的起始位置 确定为包含在数据流中的数据的函数。根据这种变型，块划分单元对所述数据流激活 用于确定锚的函数，其中，将该函数设计为每数据范围返回一个锚的概率大小令人满 意，例如是这样的函数，根据该函数，可以期望每大约50K的数据一个锚。

可以将数据块保存到缓存存储器中，用于后来的根据块ID的检索，所述块ID 通过适当的引用与这些块相关联。

如上所述，锚是数据流中根据其符合预定标准的内容而确定的位置。将该标准设 置为在预定量的数据上可出现锚的概率令人满意。

例如，根据本发明的一个实施例，与数据块相关联的一组锚可以是在块中出现短 串的一组位置，例如，在块中出现“aaa”的每个地方。根据另一实施例，该组锚可以 是一组n元组（n-tuples）的位置，其中，在该n元组上散列函数返回预定的值，例 如，块中所返回的散列值为123的字节三联组（triplet）所在的每个位置。

可用于寻找锚的散列函数的一些例子为LFSR（也称为CRC）、DES、MD5等。

根据一个优选的实施例，将锚定函数设计为找到锚的可能性为平均每500个字 节。因此，期待在每个数据包中发现三个锚。在数据被分为每个64K大的数据块的 情况下，每个块期望出现128个锚。在使用大约50K的块的情况下，期望的锚的数 量相应减少，因此期望每个块出现大约100个锚。

如上所述，锚定是由用于检查其位置与锚相关联的内容的预定范围的预定函数 （锚定函数）所返回的登记值。选择该函数和该数据范围，从而可以将返回的值用作 具有令人满意的概率的用于识别内容的签名。根据本发明的一个优选实施例，将锚定 函数选择为这样的散列函数，该散列函数对从锚开始的100个连续字节进行运算并返 回96位散列值作为数字签名。

根据本发明的一个优选实施例，登记单元（或者服务器通过其他适当的单元）还 被设计为与块ID的登记相关联地登记锚。例如，在数据划分单元从数据流中划分出 给定的数据块后，登记锚的位置，例如，作为从块的起始点测量的偏移基准。通过这 种登记，当给定数字签名值时，可在块ID的列表中搜索相同的值，如果定位了相同 的值，则可检索或访问与其相关联的块。因此，可根据与从块的起始点测量的、与该 值相关联的锚的位置来容易地定位已经从其返回了数字签名值的数据范围。

根据另一实施例，没有登记块中锚的位置。根据这个实施例，当给出数字签名值 时，可在块ID的列表中搜索相同的值，如果定位了相同的值，则可检索或访问与其 相关联的块。由于根据该特定实施例没有登记锚的位置，所以已经从其返回了数据签 名值的块中的数据范围的位置还是未知的。因此，根据这个实施例，使用字典，这将 在具体实施方式章节解释。出于此目的，ADC服务器还可以包括字典产生器单元。

通过所述锚登记实施例或通过字典产生器实施例，可以使锚定函数单元已经从其 返回了数字签名的当前接收到的数据包与包含在已经存储在存储器中的数据块中的 相似数据包同步，从而可容易地对它们进行比较，以验证它们是否相同。在它们相同 的情况下，当前接收到的包可以被对其在该块中位置的引用所替换，从而减少了发送 到接收端的数据的量。在它们不相同的情况下，通过用对块中的相同的子串（如果存 在）的起始和结束位置的引用来替换相同的子串，仍能减少要发送的数据的量。

根据本发明的服务器可用于两个基本选项之一或其组合，以减少通过通信网络的 传输量:

（i）与相似类型的至少一个对应的服务器协作，两个服务器都位于在它们之间 进行连接的虚拟通信线路的远程端（在本发明的上下文中，术语通信线路包括无线连 接作为一种可能的选项）；

（ii）与至少一个数据提供商计算机（以下称作“数据提供商”）协作，所述数据 提供商包括改向单元；

出于便于描述的目的，假定根据本发明的两个匿名数据缓存服务器连接在通信线 路的两个远程端，并还都与通过各网络和路由器连接到各个服务器的数据提供商一起 工作。

作为起始点，假定两个ADC服务器具有空的缓存存储器。数据流被引导通过ADC 服务器。每个ADC服务器处理通过其的数据，以确定锚、计算数字签名、将数据划 分为块、并创建块ID。在正常情况下，块存储在缓存中，因此缓存开始被不包含识 别信息的纯数据的块填充。每个块的块ID也被存储，从而存储在缓存中的每个块的 地址与块ID的各个列表链接。在各ADC服务器中建立缓存的同时，块被逐个包地 向预期方向发送，所述预期方向根据情况是去往位于通信线路的相对端的对应的 ADC服务器的方向或去往数据路由到其的传统接收者的方向。只要从所接收的数据 流返回了数字签名值，就在ADC服务器中的块ID的存储的列表中搜索相同的值。 当识别出具有这种相同值的块ID时，访问与该块ID相关联的块。现在，例如通过利 用锚相对于块的起始点的已知偏移（根据用块ID来保存锚的实施例），或例如通过 利用字典(根据另一实施例)，服务器对锚定函数从其返回了块ID的该块中的特定点 进行定位，并使当前接收到的数据包的位置和原始接收到的数据包的块中的位置之间 同步。

现在可以对当前接收到的包和原始的包进行比较，以验证它们是否相同，或确定 它们的哪些部分（或它们的哪些大子串）相同。

在它们相同的情况下，（根据各种其他实施例，在它们的某些部分相同的情况下）， ADC服务器发起用于减少数据流的量的过程，所述数据流现在被期望包含已经本地 存储的数据。

如果数据的源是数据提供商，则所述发起ADC服务器将消息发送到该数据提供 商以激活锚定函数，并仅发送对块中的锚的位置的引用，而不是发送数据本身。只要 所接收的引用使服务器可以从本地存储的块中检索到整个的包，则数据提供商就保持 发送引用，而不是全部数据。如果在任何给定点处，服务器识别出接收到的数据的签 名和本地存储的数据的签名之间不匹配，则服务器将消息发送给提供商以返回传统传 输。

在接收到的数据流要转发到对应的ADC服务器的情况下，所述发起服务器将消 息发送到对应的服务器以根据当前所识别的签名从其缓存检索块。然后将又一个或几 个当前接收到的包以传统发送模式发送到对应的服务器，直到该对应的服务器确认预 期的块被识别并取出为止。

在初始化服务器时，用对块的引用来替换当前接收到的包中的与本地存储的包相 同的部分，允许对应的服务器根据该块重构它们。由于引用短于它们所替换的数据， 所以包的大小可被确定地减小。因此，只要可以本地检索到与当前接收到的数据相同 的数据，就可以将减小了大小的包发送到对应的服务器。

根据一个优选的实施例，在相同的信息通过ADC服务器同时流向不同的目的地 的情况下，ADC服务器还用于消除不必要的传输量。根据该实施例，所述发起服务 器在当前接收到的包中搜索锚，并且有时可以识别出几个本地存储的包返回相同的签 名。这可能是例如，当向多个接收者广播实况视频时的情况。在这种情况下，所述发 起服务器可向对应的服务器发送消息，以利用正被发送的单个包，并将其分发给所有 接收者，到这些接收者的相同的包正等待在所述发起服务器中。可以显著地减少在这 种情况下的传输的量，并可以显著地缩短下载大量数据的时间。

现在将简要地描述本发明的一些基本的实施例：

本发明涉及一种用于通过通信网络将数据流传递到远程目的地的通信服务器，所 述服务器包括：替换单元，用于根据由远程发送者提供的引用，用从其可访问的数据 存储器检索的相同的多个数据片段来替换来自远程发送者的要接收的预期输入数据 流的多个数据片段；所述服务器的特征在于，识别单元，用于根据作为包含在所述片 段中的数据的函数的数字签名，识别要替换的数据片段；以及锚确定单元，用于确定 数据流中的位置，在所述位置处来自该流的预定义的字符组符合预定的标准，这些组 的所述位置是所述数字签名的基准点。

根据各种优选的实施例，所述通信服务器还包括发送消息单元，用于通知远程发 送者停止传递可从可访问的数据存储器检索的数据的预期输入片段。

远程发送者可以是传递数据（或文件，本发明的服务器将其当作无格式数据（plain data））的PC。

根据各种优选的实施例，所述服务器单元被设计为处理作为TCP/IP传输协议的 包的数据片段。

根据各种优选的实施例，所述服务器还包括可对其访问的数据存储器，其中，包 以可变大小的块存储在该数据存储器中，所述可变大小是根据锚在原始数据流上的位 置确定的。

根据各种实施例，由锚定函数单元返回的数字签名是基于：对来自所选择的数据 片段的预定数量的字节计算的CRC、SHA1或DES的值中的任何一个。

根据某些优选的实施例，所述数字签名是根据预定数量字节的数据而计算的，所 述多个字节在数据流中的位置与至少一个锚相关，并且所述锚是指向数据流中的兼容 预定标准的位置的指针。

根据各种优选的实施例，所述标准是包含在所述多个数据片段中的数据的函数， 并且独立于所述数据的标题、地址或路由信息。

所述函数响应于预定的字符组合，从而当识别所述字符组合时分配锚。

根据各种实施例，所述字符组合是预定义的字符的短串。

根据各种实施例，将一组锚分配给数据片段，该组中的每个锚与所述数据片段中 的n元组位置相关，其中，所述函数是在所述n元组上产生预定义的值的散列函数。

根据各种优选的实施例，从包含LFSR、CRC、SHA1、DES和MD5的组中选择 所述散列函数。

由于本发明涉及作为无格式匿名数据流的任何类型的文件，所以不管文件的大小 如何或它们是否被分开且从多个提供商处下载，该服务器和包含该服务器的系统可以 处理通过P2P通信传递的文件。

本发明还涉及一种通过通信网路传递数据流的方法，所述方法包括：确定数据流 中的基准点，所述基准点是所述流中预定义数量的字符符合预定的标准的位置；登记 数字签名，所述数字签名是预定函数针对预定义范围的内容所得到的返回的值，所述 范围与基准点有关；利用所述数字签名定位本地存储的内容，并利用基准点或创建字 典从而利用其以在当前接收到的数据片段之间和本地存储的匹配内容之间进行同步。

本发明还涉及一种包含用于控制计算机系统来执行该方法的指令的计算机可读 介质。

一种用于减少通信网络上的传输量的系统，该系统包括由以上和下文的描述所定 义的至少一个通信服务器，该系统也在本发明的范围内。

附图说明

为了理解本发明以及了解其在实际中如何执行，现在将参照附图仅通过非限制性 示例的方式来描述优选的实施例，在附图中：

图1示出了数据流、包含在数据流中的包、从数据流划分出的数据块和根据本发 明产生的锚之间的关系，产生所述锚是为了使在相似匿名数据流的重复实例之间存在 有效相关性。

图2示出了数据的块之间、使得可以定位本地存储的块的块ID的阵列之间、以 及根据一些实施例使得可以定位块中的包的字典之间的关系。

图3示出了表示根据本发明一个优选实施例的用于减少网络线路上的传输量的 处理的流程图的第一部分。

图4示出了图3的流程图的第二部分。

图5示出了根据本发明的系统构造的示例。

具体实施方式

本发明涉及一种用于通过包缓存减小带宽的方法、以及一种用于通过包缓存减小 带宽的系统。本发明的核心是存储包并以有效的方式快速地对其检索。现在将描述如 何存储包以在随后有效地对其检索。

在以下的整个描述中，正被传送的文件将被称作数据流。由于在网络中处理实时 流的设备预先不知道正被传递的文件并且当文件通过这些设备时它们才知道（learn） 该文件，就像流一样，所以这样的叫法是合理的。

当根据本发明的通信服务器从通信线路读取了属于流的包时，该通信服务器获知 数据。正在获知的流将被分为数据块。块的大小与包的大小无关。以下，根据一个实 施例，将64K大的块作为示例（尽管其可以是任何可以接受的大小）。块也不需要 在包的开始处开始。当我们从网络读取流的包时，它们的数据被复制到数据块中。当 块已满并包含64K的数据时，在执行一些将在以下讨论的预处理之后，将该块写入 到本地盘。根据另一实施例，流中块的结束位置和下一块的开始由锚（按将在后面解 释的方式）确定。通过使用锚（与根据另一实施例使用固定大小的块相反），块划分 变得依赖于其内容（因为锚被确定为所包含的数据的函数），因此，在网络上包含相 同数据的块将更可能被发现为被相同地划分，而由于没有固有的规则确定固定大小的 块的划分，所以固定大小的块的划分偶尔会改变。

根据各种实施例，在根据本发明所采用的处理中，将使用散列函数来帮助进行所 需的数据的定位。将散列键（hash key）定义为取决于数据的范围的值的n比特的数， 所述数据的大小为m字节，其中，对于两个不同的m字节的值，具有两个相同的散 列键的概率非常低。可以通过计算m字节的CRC值，或通过计算它们的SHA1值、 DES值或任何其它满足上述条件的已知函数来创建散列键。本领域的技术人员可以 根据应用了该方法的网络和包的类型来确定n和m的具体值。散列键可用于在盘上 定位所需的块。散列键还可用于在块中定位特定的所需的包。

根据本发明的一个优选实施例，在100字节上取得的64位散列键用于使得可以 在盘上定位块。

根据本发明的另一优选的实施例，在100字节上取得的96位散列键用于使得可 以在盘上定位块。

根据一些实施例，在5字节上取得的16位散列键用于创建字典，该字典将允许 在块中找到所请求的包。

根据本发明的各种实施例，优选地这样来选择锚：使所述锚仅依赖于少量的数据 （例如几字节），而独立于包含所述锚的块的起始位置或包含所述锚的包的起始位置。 用于定义流中的锚的一个例子是将锚选为位于流中出现字符串“abc”的每个位置。用 于定义锚的另一个例子是将锚选为位于流中的5个连续字节的9位散列为零的每个位 置。因为当给定了5字节的串的CRC时，容易去除串中第一字节的作用并在该串的 末端添加一新字节，所以选择9位的CRC。因此，在缓冲器中可以使CRC有效地“滚 动（rolled）”。

在我们发现锚的每个地方，在下一100个连续字节上计算96位的散列键。返回 的散列键的值被称作“块ID”。明显地，根据所描述的过程，块将具有多个ID。为了 防止有太多的块ID，可以在找到锚后跳过特定量的数据，例如，在找到下一个锚前， 可从所考虑的前一个锚跳过400字节或500字节。因此，应该理解，包将持有不超过 三个块ID，64K的块将持有不超过128个块ID。

然后将所有的块ID保存在盘上的数组中。该数组还将被称作“散列数组”。尽管 当很多ID引用一个特定块时它们可能被映射到相同的条目（entry）上，但是每个块 ID都与散列数组的一个条目相关联。就这样，在各个条目处，块ID的列表与它们所 关联的块的位置一起保存。

根据一些实施例，对于每个块，计算该块的每m个连续字节的散列键，并且将 每个散列键与产生它的位置一起存储在数组中。这种数组将被称作块的“字典”，根据 这些实施例，该字典将用于在块中定位所需的包。根据一个实施例，如先前面所提到 的，将散列键选择为16位长，并且其是在5个连续字节上计算出来的。将从该计算 中返回的散列键的值存储在数组中，然而根据其它的实施例变型，可以将它们存储在 链表、树或允许有效搜索的任何结构中。因此，将字典设置为65536个条目的数组（其 中，每个条目对应于16位键的一个不同的可能组合）。在位置p处计算出散列键h 的情况下，该数组的第h个条目将被设定为保存数p。因此，为了找到包中计算出散 列键h的位置，应该读取存储在数组的第h个条目中的值。

可以通过仅对每m个连续字节计算散列键来减小字典的大小，所述每个m个连 续字节在包内的起始位置可被x除尽，其中x是可由开发者选择的参数。x的值越高， 将导致字典的尺寸越小。例如，可选定x为16。

现在参照图1进行说明，图1示出了帧1所表示的数据流之间的关系。帧内部的 点表示数据内容。数据流中包含包，如帧2表示，帧2与帧1相同，不同之处在于帧 2通过竖线4示出了包的起始点和结束点。从数据流划分出的数据块由竖直的双线5 表示，还示出了为了使相似匿名数据流的重复实例之间有效相关而根据本发明所产生 的锚6、7和8。在该示出的示例中，将锚定义为在数据流中发现字符组合“abc”的位 置。因此，通过明确地键入所述字符组合，该流中的这种组合的实例被突出显示。竖 直的点划线9、10和11穿过流、包和块的表示，以强调锚向数据流中的位置提供了 内在基准点，从而无论如何划分该流，只要检测到预定的字符组合，则通过激活返回 锚的函数总是可以识别基准点。

参照图2，存储在缓存中的三个块由标记为A、B、C的三个帧分别表示。第一 个块A包含串“abcdeafchijk”。第一个块的字典由标记为D的帧表示。字典D表示块 A中出现字符三联组的位置。该图还示出了块ID的数组（标记为E），其中，在示 出的示例中，ID中的两个与第一个块A相关联并因而寻址到第一块A，如各个箭头 31和32所示。当接收到包时，在该包中搜索锚，并且当找到锚时，由从跟在该锚后 面的100个字节返回散列值的散列函数来计算数字签名。然后在存储有块ID的数组 中搜索数字签名值。该数组还存储了缓存中存储该块的位置。在数字签名值和任何一 个块ID的值之间出现匹配的情况下，从缓存中取出与匹配的块ID相关联的块。在将 该块取出到存储器后，可以使用字典来寻找在块中的包的大子串，所述大子串与在当 前接收到的包中的对应子串相同。然后可将这种子串从包中删除并由对该块的引用所 替代。

接收这种经处理的包的ADC服务器可以从其本地缓存中检索包的所述被删除的 部分，因此，与所删除的子串的量相对应地减少了所发送的数据的量。

将进一步解释根据本发明的各种实施例执行的处理，假定其中两个ADC服务器 分别连接到通信线路的相对端的构成，并假定（为了解释的简单）所有的通信从该线 路的相同端（在本发明的上下文中为“发起者端”）发送，并在另一端（在本发明的上 下文中为“接收端”）接收，并且在该线路两端的服务器运行了足够长的时间，并且已 经研究了通过该线路发送的信息，并已经建立了以上解释的数据结构。

简要地，根据本发明的相同构成涉及一种包括两个ADC服务器，（在通信线路 的相对端各有一个）的系统。在该线路上发送的通信通过这两个服务器。这两个服务 器研究通过该线路发送的文件和流。ADC服务器将文件和流划分为块，并将这些块 与字典（根据一个变型例）或与锚引用（根据另一变型例）一起存储在它们的本地盘 上。ADC服务器还根据新存储的块来更新它们的包含块ID的散列文件。当传送流的 包时，两个计算机利用它们的散列文件来搜索它们的盘，并将先前存储的块取出。发 送计算机使用该块，用对该块内部的数据的引用来替换包内的数据，接收计算机使用 该块根据所述引用重构该包。现在将更详细地描述所述处理。

在发起者端从网络读取的包是通信流的一部分。该通信流由其通信ID与其它通 信进行区分，所述通信ID是四元组：源IP地址、目的IP地址、源端口和目的端口。 在读取包并且在它被发送到接收端之前，发起者服务器检查该包以在该包中寻找锚。 包中的锚的期望的数量是三（假定正在使用针对这个数目的锚的前述实施例）。这意 味着存在着将会找到一些锚的特定概率。要注意，流中的锚的位置是包内容的函数而 不是包中它的位置的函数。这确保了我们在当前接收到的包中发现的锚与先前当获知 流时发现的锚对应，如果事实上这两个包包含有相同部分的信息的话。

在发现一个这种锚后，计算在该锚处定义的数字签名值。我们利用散列数组搜索 与所述计算返回的数字签名相匹配的块ID。在发现匹配的情况下，将与匹配的块ID 相关联的块从缓存取出。同时，在通知接收端从其盘取出相同块的消息之后，通过该 线路将包发送到接收端。由于所述块在过去已经通过了发起者端（去往接收端或来自 接收端），所以期望在正常条件下，在接收端也应该发现该块。将花费接收端的盘几 毫秒来取出该块。在这段时间中，通过该线路可以没有变化地（即，通过传统的发送 模式）发送相同流的更多包。并且不希望这些包的数量大于12个。

在已经从接收端的盘取出该块所需的时间之后（也就是前面所述的几毫秒的时间 之后），并且当来自相同流的包到达时，可利用字典来确定包在流内的位置。为了这 个目的，计算包内的五个字节的散列键，并将值h返回。然后读取字典的第h个条目， 该条目持有在块中出现产生相同散列的串的位置，然后将位于先前存储在包中的该位 置处的数据与在当前接收到的包中的数据进行比较，以看其是否匹配。如果它们匹配， 则用数据出现在块中的指示与所述数据在块中的位置及其长度一起，来代替包中的数 据。将所述过程按需重复很多次直到检查完整个包为止。在线路的接收端的服务器通 过将来自块中的指示数据复制到包中来重构该包。

为了提高来自缓存的块的取出时间，可应用预取技术。例如，通过识别流到达了 当前块的末端，然后预取一组块（已预测出接下来会需要这组块中的一个块），可以 在实际需要一个块之前预取该块（其可在后来被识别为所需的块）。为了这个目的， 可对每个块，例如通过自我学习技术来研究在使用一特定块之后会需要的块的列表。

图3示出了演示根据本发明的一个优选实施例的减少网络线路上的传输量的处 理的流程图的第一部分。该流程图的第一部分总体上示出了第一通信服务器ADC 1 如何预备与相似的第二通信服务器ADC 2一起工作。ADC 1如步骤41所示首先读取 包，在包中寻找锚，并在其位置与所述锚相关的预定的数据范围上计算数字签名，搜 索块ID的列表，试图定位与当前计算出的签名相同的先前存储的签名，如该处理的 步骤42和43所示。在发现匹配的情况下，处理进行到步骤44，根据与块ID（其是 在匹配当前接收到的块的签名时找到的）相关联的块的位置装载来自本地缓存的块。 然后将当前接收到的包的数据与块中的数据进行比较（在例如根据关联了签名的锚而 使各个块同步之后）。在肯定地完成了步骤45并发现相同数据的情况下，第一服务 器将消息发送到第二服务器ADC2（如步骤46表示），以使第二服务器ADC2根据 目前已知的匹配签名从其本地缓存中取出块。第一服务器等待来自第二服务器的确 认，并且只要取出适当的块的确认还没有从第二服务器返回，就保持操作的非同步模 式（如步骤47、48和50所示），其中，非同步模式指的是包以传统的形式（即，以 它们的原始形式）继续被发送到第二服务器，如步骤54所示。因此，重复该处理直 到从第二服务器接收到确认并且这两个服务器开始以同步模式工作为止（如步骤49 所示并在图4中进一步详细描述的），或者直到发现所比较的包不相同为止，从而处 理从步骤45继续进行到步骤53，并如步骤53所示，将对于第一服务器仍然为未知 的当前包保存在缓冲器中，并且如步骤54所示，将当前包继续传统地发送到第二服 务器，然后重复该处理读取另一包直到缓冲器被不熟悉的数据的整个块填满为止，然 后如步骤51所示将该块与其块ID和相关联的锚位置一起在本地存储，这使得以后可 以对将来接收的某些数据流中的匹配的签名进行识别时检索块。

图4示出了图3的流程图中同步模式的第二部分，其中，所述两个服务器对熟悉 的数据（即，所述数据已经本地存储在两个服务器的缓存中）进行操作。在同步模式 中，第一服务器如步骤55所示读取当前接收的包，并将其与在（图3中的）步骤44 中装载的块中对应的包的数据进行比较，在这两个块中的数据相同的情况下，该服务 器随即将指令发送到第二服务器，指示第二服务器响应于在（图3中的）步骤46发 送到该第二服务器的消息而根据第二服务器取出的块来重构数据，并将重构的包发送 到其目的地。在步骤56进行的比较为否定的情况下，如步骤59所示，第一服务器将 同步模式将被停止的消息发送到第二服务器，然后将当前接收到的包以其原始形式发 送到第二服务器。然后如步骤61所示，服务器将其操作模式改为非同步，并且该处 理再次开始，如图3的步骤40所示。

图5示出了根据本发明的系统构造的示例，该系统包括连接到虚拟通信线路63 的两端的两个ADC服务器61和62，还分别通过网络线路64和66与由路由器67和 65以及数据提供商69和68与数据接收者73和72所表示的传统通信网络进行通信。

通过这种网络构成并通过建立两个ADC服务器之间经虚拟线路的通信，可以使 数据流改变方向，从而确保相关的数据流将确定地通过这两个服务器。