预取信息的方法,系统和服务器

暂无

本发明涉及为客户机动态预取信息或对象(object)的方法和装置，这 里的客户机最好是与分级代理服务器系统相关联，例如可能在万维网上 预取万维网对象当中涉及到。\n术语集\n因特网(Internet)：使用一套TCP/IP协议的若干网络和网关组成的 网络。\n客户机(Client)：客户机是一台计算机，它向服务器发出命令，服务 器完成与该命令相关联的任务。\n服务器(Server)：按另一台计算机的命令完成任务的任何计算机称为 服务器。一个万维网服务器通常支持一个或多个客户机。\n万维网(World Wide Web)(WWW或Web)：一种因特网应用，它让 使用者通过选择(“点击”)被点亮的感兴趣词或短语，在从服务器到服务 器和从数据库到数据库的因特网交换连接(称作超链接)上查寻信息。因特 网WWW服务器支持客户机并向客户机提供信息。万维网可以被认为是 其全部资源用URL定址的因特网，它使用HTML显示对应于URL的信 息并向其他URL提供点击(point-and-click)接口。\n通用资源定位符(Universal Resource Locator)(URL)：URL是对因 特网上信息进行唯一标识或编址的方法，它可以被认为是电子邮件地址 的万维网文档版本。URL可以由超链接来访问。URL标识的一个实例是 “http://www.philipyu.com：80/table.html”。URL有4个组成部分。从 这个实例的左边开始，第一部分指定所用协议(在该例中是http)，它与定 位符的其余部分用“:”分开。下一部分是目标主机的主机名或IP地址； 这一部分在其左侧用双斜线“//”定界，在其右侧用单斜线“/”(或可选 地使用“:”)定界。端口号是一个可选部分，在左侧用“:”与主机名 划界，在右侧用一单斜线“/”定界。第四部分是实际 的文件名或程序名(在本例中是table.html)，再使用单斜线按传统方式 分开目录和子目录。在本例中，扩展名“.html”意味着这是一个HTML 文件。\n超文本标记语言(HyperText Markup Language)(HTML)：HTML 是一种语言，由万维网服务器用于创建和连接被万维网客户机观看的 文档。HTML产生超文本文档。\n超文本传输协议(Hypertext Transfer protocol)(HTTP)：HTTP是 无状态(stateless)协议的一例，其中由客户机向服务器发出的每个请求 都被独立地处置。服务器没有关于先前连接的记录。在URL的开头， “http:”指明对于指定的资源发出请求的客户机与目标服务器之间 应使用HTTP协议进行通信。\n因特网浏览器或Web浏览器(Internet Browser或Web Browser)： 一种图形接口工具，它运行因特网协议，如HTTP，并在使用者的屏 幕上显示结果。当使用者在因特网上“冲浪”时，浏览器能作为因特 网上的漫游响导，与图形桌面、目录和查寻工具配套。在本申请中， Web浏览器是一个与万维网通信的一种客户机服务。\n客户机高速缓存(Client cache)：客户机高速缓存通常用作为被客 户机访问的原始对象组(高速缓存)。在万维网环境中，客户机高速缓存 通常由Web浏览器实现，可以高速缓存当前调用过程中被访问的对象 (即非持久性高速缓存)，或者可以高速缓存跨越多个调用的对象。\n高速缓存代理(Caching proxy)：网络中的专用服务器，作为代表 客户机的代理去定位一个对象，可能返回一个被高速缓存的副本。高 速缓存代理通常用作为第二层或更高层高速缓存，因为它们是在对客 户高速缓存器未高速缓存命中的情况下才被调用的。\n元标记(META-tagging)：信息与给定对象的组合。例如，在HTTP 中，在HTTP标题的各字段(field)中信息能与请求和响应二者组合在一 起。例如，一个HTTP客户机能指定请求从其中返回页面的URL。\n                     *    *    *\n随着万维网(WWW或Web)在大众中的增加，在因特网上的业务 量已相当大地增加了。现在万维网已成为网络性能的主要瓶颈之一。 例如，当一个通过慢网络链路连于服务器的使用者请求文档或信息 时，该Web用户可能会感受到显著的延迟。Web在网络上向使用者传 送信息进一步提高了网络上的通信量水平。这种增加了的通信量降低 了其他使用者的请求所能得到的带宽，造成额外的可能延迟。\n为减小客户机访问迟延，现有技术已把常用的信息文档存储或高 速缓存到更接近使用者的网络节点处，访问这些节点的访问迟延更可 接受。高速缓存可在网络上的各种节点上实现。例如，一所大的大学 或公司可以有它自己的本地高速缓存，注册到那个网络上的所有使用 者都可以从其中取回文档。本地高速缓存可以以专用服务器的形式实 现。\n称作高速缓存代理的一种专用服务器可以作为代表客户机的代理， 去定位被请求信息的任何可能被高速缓存的副本。高速缓存代理通常 作为第二层或更高层高速缓存，因为高速缓存代理只与对失效客户机 高速缓存的未命中有关。客户机高速缓存建立在各种Web浏览器中。 客户机高速缓存或者可以只存储在当前调用过程中被访问的文档(非 持久性高速缓存，如Mosaic)，或者可以高速缓存跨越多个调用的文档。\n先前在Web文档高速缓存方面的工作主要是在请求式(on-demand) 高速缓存这一领域。请求式高速缓存的意思是在一个对象被请求之后 才作出高速缓存决定。例如，Abrams等在“高速缓存代理：局限与潜 力”(第4届国际万维网会议文集，1996)中描述了已对Web检验过的 不同的请求式高速缓存策略。\n在因特网服务供给商(ISP)的网络或合作网络中，在代理分层系统 中不同的区域代理或部门代理可能会观察到不同的查访(reference)行 为或面对不同的网络业务和延迟。代理分层系统的存在进一步使预取 决策复杂化，即是否所有的中间代理、客户机或它们的子集都应进行 预取。这样，便需要一种预取方法和系统，它能有效地协调代理服务 器分层系统和相关联的客户机所进行的预取活动。\n于是，本发明提供了一种从内容服务器(content server)中预取选定 信息的方法，它能使经由通信网络以及一个或多个代理服务器与内容 服务器相连的一个或多个客户机容易地访问所选定的信息，该方法包 含如下步骤：\n从至少一个代理服务器中请求信息；\n根据任何所述客户机过去对所请求信息的提取或访问情况，建立 用于所述用户的预取线索信息；\n以所述预取线索信息对所请求的信息作注解；以及\n根据预取线索信息和所请求信息，从任何所述服务器中预取选定 信息。\n通常，所请求信息包含所请求的对象，而选定信息包含预取候选 对象，如因特网数据。在这种情况下，所请求的对象能通过与该因特 网数据相关联的一个超文本传输协议(HTTP)链路去查访这选定对 象，代理服务器通过存储在所请求对象的对象标题中的所请求对象通 用资源定位符(URL)来识别选定对象与所请求对象之间的关系。\n建立预取线索信息的步骤最好包括以下步骤：追踪与所述客户机 关联的数据查访模式(pattern)；把数据查访模式组织到对象标识符组 中，这对象标识符组是根据所请求对象和预取候选对象之间的关系组 织的；以及确定所述组中哪些具有足够的预取候选对象和所请求对象 之间的关系，以证明有理由把所述预取候选对象作为选定信息预取回 来。这样，所述各客户机的数据查访模式有利地依据过去对所请求信 息的提取或先前的访问，数据查访模式被选定为代表与所述代理服务 器之一相关联的所述不同客户机在过去的提取或访问中的任何共同趋 势。然后，它能用于确定预取线索信息。\n追踪和组织步骤最好包括建立数据库以把查访数据模式存储于代 理服务器中；安排所述数据库每个中的字段，这些字段包括对象标识 符和对象计数，这对象标识符把所请求对象彼此区分开，对象计数则 指明被所述服务器之一观察到的所请求对象曾被请求的次数；以及把 访问清单与所述数据库关联起来，每个所述访问清单含有与每个所请 求对象相关联的一个或多个预取候选对象。\n这种数据库能用于确定所请求对象与预取候选对象之间的关系和 追踪关于所请求对象和预取候选对象的访问统计；这访问统计包括关 于所请求对象的父(parent)对象访问频率和关于预取候选对象的子 (child)对象访问频率；父对象访问频率代表所请求对象中的一个特定 对象被至少一个所述客户机请求的次数；子对象访问频率代表紧随访 问该特定对象之后一个或多个所述预取候选对象被实际请求的次数。 这便允许根据子对象访问频率和与该子对象访问频率相关联的父对象 访问频率的比值来选定预取候选对象的预取清单，这预取清单只包含 它们的该比值超过一阈值概率的那些预取候选对象。\n一般而言，只有预取候选对象的一个子集将在所述代理服务器之 一或所述客户机之一被实际预取和接收，通常对预取候选对象这一子 集的选择以作为选择信息是基于诸多因素的，如在所述代理服务器之 一处能得到的存储大小和/或在所述代理服务器之一处的访问时间。这 样，是根据与某一相应预取值相关联的优先级来预取预取候选对象 的。\n在最佳实施例中，对所请求信息加注解的步骤包含把预取线索信 息放入预取标记(label)中的步骤，这预取标记有因特网内容选择平台 (PICS)格式或与PICS格式兼容的标记协议。在这一(PICS)格式的一个 具体实现中，定义了一个对象标识符类别和查访者(referrer)标识符类 别，所述方法进一步包括向内容服务器返回查访者标识符类别的步 骤，以识别实际被查访过的任何预取候选对象。根据因特网内容选择 平台(PICS)协议或PICS兼容协议组织预取线索信息利用了已被许多 浏览器支持的格式。\n通常，存在一个所述代理服务器的分层系统。在这一分层系统中 定义一个发送节点和一个接收节点，预取线索信息最好从一个初始状 态修改为一个最终状态，这初始状态由发送节点确定，而最终状态由 接收节点确定。正是所述最终状态下的预取线索信息在其后构成最终 预取决定的基础(假定预取选择信息由接收节点发生)。\n换句话说，当预取线索信息通过该分层系统从代理服务器传送到 客户机时，该预取线索信息能被解释和更新。如果存在对所请求信息 的本地查访而且如果本地级服务器的计数超过了一个最小阈值计数 (即因此能在本地得到可靠的统计)，则最好由一代理服务器来更新预取 线索信息。预取线索信息的更新还能根据代理分层系统中的高速缓存 状态(例如指出在该分层系统中何处可以高速缓存一特定的预取候选 对象)。\n本发明还提供了一个数据处理系统，用于通过网络从一内容服务 器预取选定信息，所述系统包括一个或多个与该网络关联的代理服务 器，以及通过网络与该内容服务器及一个或多个代理服务器进行通信 的若干客户机；所述系统包含：\n从至少一个代理服务器请求信息的装置；\n根据任何所述客户机过去对所请求信息的提取或访问情况，为所 述客户机建立预取线索信息的装置；\n以所述预取线索信息注解所请求信息的装置；以及\n根据预取线索信息和所请求信息，从任何所述服务器中预取选定 信息的装置。\n在一个最佳实施例中，所请求信息包含所请求的对象，而选定信 息包含预取候选对象，这里每个所述代理服务器和至少一个客户机有 一个存储器，它至少有一个在主高速缓存和预选高速缓存之间的逻辑 分隔，其中预取的选定信息存储在预取高速缓存中。\n最好是由预取装置根据一种优先级方案来预取对象和把所预取的 对象存储到预取高速缓存中，这优先级方案首先存储具有最高预取值 的对象，并考虑可能得到的预取高速缓存存储器大小，该预取值是基 于一个或多个客户机对预取对象进行查访的单个查访概率或累积查访 概率。特别是，该预取值可以基于预取线索信息清单上的一个预取候 选对象将被一些特定客户机访问的估计访问概率，以及基于根据存储 选定的一些预取候选对象所需存储大小而确定的对象访问成本。\n在一个最佳实施例中，预取装置包含一个预取处理器，它包括计 算所述预取值的计算装置和对计算装置计算出的预取值进行评估的评 估装置；所述计算装置为预取线索信息清单上的每个预取对象标识符 计算其预取值；所述评估装置对多个候选预取对象的预取值进行评 估，并对预取线索信息清单上与那些最高预取值相关联的那些候选预 取对象给予高速缓存优先。该预取装置可以包含在至少一个所述代理 服务器中的第一预取处理器和在至少一个所述客户机中的第二预取处 理器(即预取可以在这分层系统中的不同/多个位置上完成)。\n一个最佳实施例还包括一个存储在所述客户机之一的存储器中的 客户机对象请求处理器，在向代理服务器或网络请求所请求对象之 前，该客户机对象请求处理器先在主高速缓存和预取高速缓存上搜索 所请求的对象，如果该对象位于预取高速缓存中，则由客户机对象请 求处理器产生一个发给服务器的预取被查访消息，指出该预取对象已 被该客户机实际访问过，以此来通告内容服务器或代理服务器。类似 地，最好是至少一个所述代理服务器包括一个预取被查访消息处理 器，用于在调用一个高速缓存管理器例行程序之后传送预取被查访消 息，如果所请求的对象位于该预取高速缓存中的话。这样，即使因为 一子对象能从该客户机处的预取高速缓存或代理服务器中的高速缓存 中得到，因而该服务器没有和这一子对象直接接触，但该服务器也能 保持访问统计的准确记录。\n本发明进一步提供了一个用于这种数据处理系统中的内容服务器 或代理服务器，其中所请求的信息包含所请求对象，其中选定信息包 含预取候选对象，所述服务器包括：\n一个统计表，存储父对象标识符和相关联的子对象标识符，该统 计表含有关于父对象的第一计数，该第一计数代表父对象被客户机查 访的频率，统计表含有关于子对象的第二计数，该第二计数代表选定 的所述父对象被查访之后相应子对象被查访的频率；以及\n产生装置，用于根据统计表中的信息产生预取线索信息清单。\n在一个实施例中，该产生装置从统计表中接受第一计数、第二计 数、子对象标识符和父对象标识符输入，该产生装置包括评估装置用 于评估父对象与其相关联的子对象之间的访问关系，如果在客户机查 访相应父对象之前一些子对象被以适当的频率靠近地、接续地被查 访，则评估装置把这些子对象放入预取线索信息清单中。这适当的频 率可以基于子访问次数与相应父访问次数的比值。通常，这涉及对每 个所述父对象标识符计算其第二计数与第一计数的比值；把该比值与 一线索阈值作比较；如果该比值超过该线索阈值，则在预取线索信息 清单上把子对象和相关联的父对象组成组或者说组合起来。\n最好是该服务器进一步包含统计更新装置，用于根据实际被查访 的子对象来更新统计表；该统计更新装置首先查找正在查访的一个所 述父对象的标识，这个在查访对象，或者说查访者(referrer)对象，是 在子对象实际被请求之前被查访的对象，这个实际被请求的子对象使 其在统计表中的相应第二计数被更新。这个统计表还应在一旦收到来 自预取被查访消息处理器的预取被查访消息时立即更新。\n在服务器为一代理服务器时，它最好进一步包含预取更新装置， 用于接收和更新预取线索信息清单。预取更新装置把第一计数与第一 本地阈值计数进行比较，并对第一计数超过第一本地阈值计数的每个 子对象标识符调用产生装置，如果第一计数没有超过第一本地阈值计 数，则预取更新装置保持原来的预取线索信息清单。在一种更复杂的 途径中，预取更新装置把第一计数与第一和第二本地阈值计数进行比 较，并且(i)如果第一计数没有超过第一本地阈值计数则保持原来的预 取线索信息清单；(ii)如果第一计数超过第一本地阈值计数但没有超过 第二本地阈值计数则修改原来的预取线索信息清单；以及(iii)如果第一 计数超过第一和第二本地阈值计数二者，则替换原来的预取线索信息 清单。\n该服务器最好进一步包括：一个代理对象处理器，用于把所请求 对象回送给请求所请求对象的较低层代理服务器或客户机，如果所请 求对象不是预取对象，则代理对象处理器回送所请求对象并相应地更 新统计表；以及一个预取高速缓存管理器，用于管理预取高速缓存。 这样，代理对象处理器把所请求对象从预取高速缓存回送给发请求的 客户机或代理服务器，并把该对象标记为可从预取高速缓存删除的对 象，如果该对象是遵循一个预取请求而被请求的话。如果所请求对象 不在主高速缓存或预取高速缓存中，则代理对象管理器向另一服务器 发出对象请求。如果这个所请求对象不与一预取请求相关联，而且如 果所请求对象位于该预取高速缓存或主高速缓存中，则代理对象处理 器相应地更新统计表。\n从另一方面看，本发明提供了一种方法，用于通过通信网络从一 内容服务器中预取选定对象以使与一个或多个代理服务器相关联的客 户机容易地得到这些选定对象；该方法包含的步骤有：\na)从至少一个所述代理服务器请求所请求的对象；\nb)根据客户机过去对所请求对象提取或访问情况，识别相应客户机的 数据查访模式；\nc)由数据查访模式生成预取线索信息送入预取线索信息清单；\nd)以预取线索信息注解所请求对象；\ne)根据预取线索信息和当前所请求对象，从至少一个所述服务器中预 取选定对象。\n这样，被预取的选定信息包含一个预取候选对象；而建立预取线 索信息的步骤进一步包含在所述代理服务器的分层系统中的一个发送 节点建立预取线索信息；这里预取候选信息通过所述代理服务器的分 层系统；在该分层系统中的接收节点要预取的选定信息是基于预取线 索信息。\n通常有一代理服务器分层系统与网络相关联，该代理服务器分层 系统包括一个较低层服务器，它比其他代理服务器更紧密地与这些客 户机相关联。在一个最佳实施例中，如果存在对所请求对象的本地查 访而且本地级服务器计数超过一个最小阈值计数，则通过该代理服务 器分层系统来更新预取线索信息；另一种作法(或者说再一种作法)是可 以通过分析较高层处的高速缓存状态来更新预取线索信息，该分层系 统的最高层是最紧密地与网络相关联的。\n从另一方面看，本发明提供了一种系统，用于增强治网络从服务 器到客户机的数据流，该处理系统包含：\n与该网络相关联的代理服务器；\n与该网络相关联的内容服务器；\n配置成与一个或多个所述代理服务器进行通信的客户机；\n存储在至少一个所述代理服务器中的统计表，该统计表存储父对 象标识符和相关联的子对象标识符，该统计表含有关于父对象的第一 计数，该第一计数代表父对象被客户机查访的频率，该统计表含有关 于子对象的第二计数，该第二计数代表选定的所述父对象被查访之后 相应子对象被查访的频率；以及\n产生装置，用于根据第一计数和相应的第二计数输入产生预取线 索信息，以导出预取线索信息清单，所述产生装置包括：\n计算装置，用于对每个所述父对象标识符计算第二计数与第一计 数的比值；\n比较装置，用于把该比值与一线索预值进行比较，如果该比值超 过该线索阈值，则比较装置在预取线索信息清单上把子对象和相关联 的父对象组成组或者说组合起来；以及\n预取装置，用于根据预取线索信息和由客户机实际请求的父对 象，预取子对象。\n在一个最佳实施例中，每个所述代理服务器有第一处理器、第一 存储器和用于存储数据的第一存储装置；这第一存储器至少有一个在 第一主高速缓存和第一预取高速缓存之间的逻辑分隔；内容服务器有 第二处理器、第二存储器和用于存储数据的第二存储装置；以及至少 一个客户机有第三处理器、第三存储器以及用于存储数据的第三存储 装置，这第三存储器至少有一个在第二主高速缓存和第二预取高速缓 存之间的逻辑分隔，预取处理装置把子对象存储在第一预取高速缓存 或第二预取高速缓存中。\n在一个最佳实施例中，预取装置包括计算装置用于计算预取值， 和评估装置用于评估由计算装置计算出的预取值；所述计算装置对预 取线索信息清单上的每个子对象标识符计算一个预取值，并对预取线 索信息清单上那些具有最高预取值的子对象给予高速缓存优先，预取 处理装置管理预取高速缓存中的可使用的空间。\n该系统最好进一步包括：预取更新装置，用于更新预取线索信息 清单；该预取更新装置把第一计数与第一本地阈值计数和第二本地阈 值计数进行比较，这第一本地阈值计数根据来自一个服务器的统计， 这第二本地阈值计数根据来自另一服务器的统计，对于第一计数超过 第一本地阈值计数和第二本地阈值计数二者的每个子对象标识符，所 述预取更新装置调用产生装置；如果第一计数不超过第一本地阈值计 数，则预取更新装置保持原来的预取线索信息清单。\n最好是这个系统进一步包括：\n统计更新装置，用于更新统计表；\n存储在所述代理服务器之一中的代理对象处理器，这代理对象处 理器调用预取线索信息清单更新例行程序，如果一较低层代理服务器 请求所请求的对象，则该代理对象处理器向该较低层代理服务器回送 所请求的对象，如果所请求对象不是一个预取对象，则代理对象处理 器回送所请求对象并调用统计更新装置；\n预取高速缓存管理器，用于管理与所述代理服务器之一相关联的 预取高速缓存，如果较低层服务器未曾请求所请求的对象，则代理对 象管理器调用该预取高速缓存管理器；\n存储在所述代理服务器之一中的代理对象请求处理器，如果对象 在预取高速缓存中和如果该对象曾遵循一个预取请求而被请求过，则 该代理对象请求处理器向所述客户机中发请求的一个回送这些对象并 使该对象标记为可从预取高速缓存中删除的对象；如果这所请求的对 象不在主高速缓存或该预取高速缓存中，则代理对象请求处理器向另 一服务器发送一个对象请求，如果所请求对象不与该预取请求相关联 和如果所请求对象位于该预取高速缓存或主高速缓存中，则代理对象 请求处理器与统计更新装置通信。\n该系统最好还进一步包括：\n统计更新装置，用于更新统计表；\n以及存储在所述代理服务器之一中的预取所查访消息管理器，该 预取所查访消息管理器调用统计更新装置，如果一所请求对象位于预 取高速缓存中，则预取所查访消息处理器在调用一高速缓存管理器例 行程序之后传递一个预取所查访消息。\n本发明进一步提供一个处理系统用于增强沿网络从服务器到客户 机的数据流，该处理系统包含：\n与该网络关联的代理服务器；\n与该网络关联的内容服务器；\n被配置成与一个或多个所述代理服务器通信的代理服务器；\n一个统计表被存储在该内容服务器和至少一个所述代理服务器 中，该统计表存储父对象标识符和相关联的子对象标识符，该统计包 含有关于父对象的第一计数，该第一计数代表父对象被客户机查访的 频率，该统计表含有关于子对象的第二计数，该第二计数代表所述父 对象中的选定对象被查访之后紧接着被暂时查访的相应子对象的频 率；\n产生装置，从统计表中接受第一计数、第二计数、子对象标识符 及父对象标识符输入，该产生装置包括评估装置用于评估父对象和与 它们关联的子对象之间的访问关系，如果在客户机查访相应父对象之 前一些子对象被以适当的频率靠近地、依次地被查访，则评估装置把 这些子对象标识符放入预取线索信息清单中；以及\n预取装置，用于根据预取线索信息和被客户机实际请求的父对象 预取子对象。\n在一个最佳实施例中，预取装置进一步包含分配装置用于把存储 优先级分配给预取线索信息清单上标识的各子对象，以及选择性存储 装置用于根据存储优先级存储选定的子对象。该分配装置最好根据预 取线索信息清单上的一子对象将被特定客户机访问的访问概率以及基 于存储选定子对象所需存储器大小而定的子对象访问成本来分配存储 优先级。\n这样，在一个代理分层系统中信息能被预取以减少客户机通过网 络(例如因特网)的对象访问时间。选定信息从一内容服务器中预取，以 使网络中与内容服务器关联的客户机能容易地访问选定的信息。这些 客户机最好与网络中的代理服务器关联。客户机从至少一个代理服务 器中请求信息。内容服务器根据被客户机请求过的信息的过去数据访 问模式，产生用于客户机的预取线索信息。内容服务器以预取线索信 息注解所请求的信息。一个或多个代理服务器可以根据动态使用情况 统计来动态地更新预取线索信息。随着对象通过代理分层系统，该预 取线索信息被更新，以反映所完成的预取操作、在代理分层系统较高 层次上的高速缓存状态、以及其他本地考虑，如本地查访模式。可以 根据预取线索信息和所请求的信息，从内容服务器或代理服务器中的 任何一个中预取选定的信息。可以根据查访访问概率和存储考虑对预 取线索信息分配一个预取值。在预取线索信息清单中具有那些最高预 取值的选定信息被首先高速缓存，而且可能直至预取高速缓存被充 满。\n现在将参考如下附图仅以举例方式详细描述本发明的一个最佳实 施例：\n图1是一方框图，显示内容服务器(即万维网站点)、网络(即因特 网)、代理服务器分层系统、以及客户机；\n图2又是一个方框图，比图1更详细地显示一内容服务器、一客 户机、和一个代理服务器；\n图3A是一流程图，说明经由代理服务器分层系统从一内容服务器 动态预取数据的方法；\n图3B是一统计表的示例；\n图4是流程图，说明该内容服务器的操作；\n图5是说明统计更新的流程图；\n图6是说明产生预取线索信息的流程图；\n图7是说明客户机操作的流程图；\n图8是说明预取过程的流程图；\n图9是说明一客户机对象请求处理器操作的流程图；\n图10是说明代理服务器操作的流程图；\n图11是说明一代理对象请求处理器操作的流程图；\n图12是说明一预取所查访消息处理器操作的流程图；\n图13是说明一代理对象处理器操作的流程图；以及\n图14是说明一预取线索信息更新例行程序操作的流程图。\n图1显示的数据处理系统包括客户机22、代理服务器分层系统 24、网络25及内容服务器20。\n客户机可以以父对象、子对象、所请求对象、选定对象、页面、 所请求信息、和选定信息的形式请求信息。父对象与子对象相关，即 这些父对象可能在历史上已着手过对相关联的一个或多个子对象的相 继请求。所请求对象类似于父对象，而选定对象类似于子对象。所请 求对象是被一个或多个客户机实际请求的对象。与此同时，选定对象 是与所请求对象成组或与所请求对象相关的对象，即选择对象可能在 所请求对象之后紧接地、暂时地被请求。所请求信息包括所请求对象、 父对象、以及由客户机请求的其他形式数据。选定信息包括子对象、 选定对象、以及其他形式的可能被预取的数据。\n客户机22可以从内容服务器20或代理服务器24请求信息。然而， 代理服务器24通常作为客户机和网络25以及内容服务器20之间的中 介物。有利的是，如果代理服务器分层系统含有所请求信息或有能力 完成所请求的任务，则代理服务器24可以满足客户机的信息请求而无 需与内容服务器20接触。图1所示数据处理系统可以应用于因特网。 例如，内容服务器20可以包含一万维网站点，而网络25可以包含因 特网。\n图1显示的是数据处理系统各组成部分之间的逻辑连接26，这与 物理连接相反。逻辑连接26代表数据处理系统内对象和请求的信息 流。逻辑连接26通常不代表各代理服务器24之间的物理连接。由于 工作负载和/或诸如节点或通信链络失效等物理事件，逻辑连接26可 能会改变。不同类型的对象可能沿不同的逻辑传输路径到达客户机 22。\n尽管在实践中实质上可使用任何数量的客户机22和代理服务器 24，但在图1所示举例中以4个客户机22和4个分层级别的代理服务 器24为其特征。在实践中，允许在代理服务器分层系统中有任意的分 层数，而客户机22可以在逻辑上连接于代理服务器分层系统的任何 层。例如，代理服务器分层系统24可以是单一的代理服务器。本发明 可以以仅只单个客户机22和单个代理服务器24来实现。\n如图所示，最高层代理服务器被指定为零层代理服务器30。“零 层”是一种任意性指定，它只是定义图1示例中一个代理服务器相对 于另一代理服务器所处的状态。最高层代理服务器可以在逻辑上与网 络25相连。较高层的代理服务器21与较低层的代理服务器23相比 较，逻辑上网络25的关联更近。(所以可以理解，用这里的术语，把 零层代理服务器看作是代理分层系统的顶级，零层“高于”1层，而1 层又“高于”2层，如此等等)。\n第一1层代理服务器35和第二1层代理服务器37逻辑上与0层 代理服务器30相连。第一1层代理服务器35与第一2层代理服务器 40和第二2层代理服务器43相连。第一2层代理服务器40逻辑上与 第一3层代理服务器50和第二3层代理服务器55相连。\n客户机22包括第一客户机600、第二客户机603、第三客户机700、 以及第四客户机703。第一客户机600和第二客户机603逻辑上与第一 3层代理服务器50相连。第三客户机700和第四客户机703逻辑上与 第二3层代理服务器55相连。\n现在从第二客户机603的角度描述该数据处理系统。该第二客户 机603与它的直接较高层代理服务器相连。如所示，该直接较高层代 理是第一3层代理50然后第二客户机603分别与第一2层代理服务器 40、第一1层代理服务器35以及0层代理服务器30相连。第二客户 机603能通过网络25访问各种内容服务器20。虽然第二客户机603 的通常通信路径是经由直接较高层代理服务器(即第一3层代理服务器 50)，但第二客户机603或较低层代理服务器可以与较高层代理服务器 24或网络25直接通信。这第二客户机甚至可以有其自己的客户机代 理去管理高速缓存。\n从第二客户机603的角度去看，某些代理服务器不是它的代理分 层系统的一部分。例如，第二3层代理服务器55和第二2层代理服务 器43以及第二1层代理服务器37不是这第二客户的代理服务器分层 系统的一部分。\n客户机22可以包括但不限于个人计算机、工作站、机顶盒(set top box)等。网络25可以包括但不需要包括因特网、万维网、内联网 (Intranet)、局域网(LAN)等。\n代理服务器24和内容服务器20可以包含各种市场上可得到的计 算机。例如，代理服务器24可以以IBM公司出售的因特网连接服务 器(ICS)来实现，内容服务器20可以以Lotus Go Web服务器、Lotus Domino服务器等来实现(也可从IBM公司购到)。代理服务器24或内 容服务器20能在任何计算节点上运行，这包括但不限于S/390 SYSPLEX、SP2、或RS6000工作站等产品(也可从IBM公司购到)。 总之，代理服务器24或内容服务器20可以包含任何通用计算机和能 提供万维网页面访问、远程文件传输、电子邮件、以及对客户机22的 事务支持的相关软件。\n图1的数据处理系统可以使用传统代理分层系统的层性来维持数 据传输的效率。例如，如果一个所请求的对象不能在本地的较低层代 理服务器上得到，则向较高一层代理服务器发出请求请求这不能得到 的对象。如果该较高层代理服务器先前已把该对象高速缓存在它的高 速缓存存储器，则该较高层代理服务器经由该较低层代理服务器把所 请求对向下传到该客户机。否则，该较高层代理服务器将试图从更高 一层的服务器得到该对象。一旦得到了所请求的对象，它便被下传到 较低层代理服务器或请求该对象的客户机。\n图2更详细地描述了图1所示数据处理系统。该数据处理系统包 括代理服务器24、内容服务器20、网络25及客户机22。该数据处理 系统最好包括预取单元250、统计表261、统计更新单元252、主高速 缓存297、以及预取高速缓存298。\n预取单元250最好包括代理服务器24中的第一预取处理器248和 客户机22中的第二预取处理器241。统计表261包括与代理服务器24 相关联的统计表293和与内容服务器20相关联的统计表267。统计更 新单元252包括用于更新第一统计表293的第一更新统计单元264和 用于更新第二统计表267的第二更新统计单元269。主高速缓存297 包括每个代理服务器24中的第一主高速缓存294和在每个客户机22 中的第二主高速缓存246。预取高速缓存298包括代理服务器24中的 第一预取高速缓存296和在客户机22中的第二预取高速缓存249。\n代理服务器24是能通过网络25服务于请求的计算节点。代理服 务器24包括第一处理器280、第一存储器290以及第一存储单元281。 第一存储器290可以包含例如，随机存取存储器(RAM)。第一存储单 元281可以包含例如直接存取存储装置(DASD)。第一存储器290存储 代理服务器逻辑295，它以计算机可执行代码形式实现。代理服务器 逻辑295从第一存储单元281加载到第一存储器290供第一处理器280 执行。代理服务器逻辑295操作的详情示于图10。\n代理服务器逻辑295包括一个代理对象请求处理器283、代理对象 处理器284、第一预取处理器248、预取被查访消息处理器285、预取 更新装置291、第一更新统计例行程序264、第一统计表293、第一主 高速缓存294以及第一预取高速缓存296。\n代理对象请求处理器283的操作详情在图11中描述。代理对象处 理器284的操作详情在图13中描述。预取被查访消息处理器285的操 作示于图12。统计更新单元252(即第一更新统计例行程序264)的操作 详情示于图5。\n预取单元250(即第一预取处理器248)的操作详情示于图8。预取 更新单元291或预取线索信息更新例行程序的操作示于图14。代理服 务器逻辑295维持第一主高速缓存294和第一预取高速缓存296。\n内容服务器20是能通过网络25服务于请求的计算节点。内容服 务器20包括第二处理器260、第二存储器263、及第二存储单元265。 第二存储器263可以包含例如随机存取存储器(RAM)。第二存储单元 265可以包含例如直接存取存储装置(DASD)。第二存储器263存储内 容服务器逻辑268或内容服务器软件。\n接下来参考图4更详细地说明内容服务器逻辑268的操作。内容 服务器逻辑268作为计算机可执行代码来实现，它从第二存储单元265 加载到第二存储器263供第二处理器260执行。内容服务器逻辑268 包括第二统计表267、第二更新统计单元269用于更新第二统计表 267、以及产生单元266用于产生预取线索信息。第二统计表267存储 关于客户机所请求信息和与所请求信息关联的可能预取信息的数据。 统计表261对预取线索信息的产生做贡献，预取线索信息是基于客户 机的实际查询行为。图3B中给出统计表261的详情。\n参考图5更详细地说明第二更新统计单元269的操作。产生单元 266由第二统计表267中的信息和所请求信息产生预取线索信息。产 生单元266可以作为产生预取线索信息(PHI)例行程序来实现，如图6 所描述的那样。\n客户机22最好包括第三处理器240、第三存储器245和第三存储 单元242。第三存储器245可以包含例如随机存取存储器。第三存储 单元242可以包含例如直接存取存储装置(DASD)。第三存储器245存 储客户机逻辑244或客户机软件。接下来参考图7更详细地说明客户 机逻辑244的操作。客户机逻辑244作为计算机可执行代码来实现， 它从第三存储单元242加载到第三存储器245供第三处理器240执行。\n客户机逻辑244包括客户机对象请求处理器247、第二预取处理器 241、第二主高速缓存246、以及第二预取高速缓存249。客户机对象 请求处理器247从第二主高速缓存246、第二预取高速缓存249、代理 服务器24或内容服务器20中得到客户机所请求的对象。客户机对象 请求处理器247的操作详情示于图9。\n客户机逻辑244维持第二主高速缓存246和第二预取高速缓存 249。第二主高速缓存246用于存储被频繁查访的对象，而第二预取高 速缓存249则用于存储实际受到查访之前的对象。预取对象是尚未在 新近或先前被查访过但与所查访对象有牵连的对象。在最佳实施例 中，主高速缓存297由传统的LRU(最近最少使用)算法管理。本领域 技术人员还会理解，任何其他替代策略可用于维持主高速缓存297。\n主高速缓存297和预取高速缓存298可以在逻辑上分开。把预取 对象与主高速缓存297中的实际被查访对象在逻辑上分开是为了防止 预取对象占用太大的存储空间。可以有各种不同方法来实现从逻辑上 分开预取高速缓存和主高速缓存。例如，单个高速缓存可以对预取对 象个数加上上限和/或对预取对象所占空间加上上限。主高速缓存297 和预取高速缓存298的意思是支持不同的目标。主高速缓存297是用 于高速缓存那些具有被重复查访潜力的普及对象。而预取高速缓存只 用于支持一次特定的浏览对话(session)，作法是预取那些在该对话中接 下来最有可能被查访的对象。在本最佳实施例下，如果在分层系统中 的较低层节点对一较高层节点的预取高速缓存中的一个对象发出预取 请求，则该对象将被下传到该较低层节点并被标记为可从该较高层节 点的预取高速缓存中删除，因为预取的目的已经完成。当一预取对象 实际得到查访时，它可以被移到主高速缓存297，这取决于主高速缓 存297的管理策略。在本最佳实施例下，使用LRU替换策略，一个预 取对象一旦被查访则被移到主高速缓存。\n可以设计出另一种判据用于把对象从预取高速缓存298接纳到主 高速缓存297中。在Abrams等的“高速缓存代理：限制与潜力”(第 4届国际万维网会议文集，1996)中讨论了一些高速缓存替换策略，这 些策略在决策过程中考虑了对象的大小。对于本领域一般技术人员而 言，其他高速缓存替换策略也是公知的。\n图3A的流程图说明从一内容服务器20或一代理服务器分层系统 为客户机动态预取数据的方法。首先，在框100中，一客户机从一代 理服务器或一内容服务器20请求信息。第二，在框102中，识别出在 该内容服务器20和代理服务器中历史数据访问或数据查访的模式。在 实践中，完成框100和框102的顺序可以被颠倒。\n第三，在框104中，内容服务器20根据在框102中识别出的数据 查访模式产生关于对所请求信息进行相关访问的预取线索信息。第 四，在框105中预取线索信息可以注解所请求的信息。例如，预取线 索信息可以作为与所请求信息(即对象)搭在一起的元数据被传送。对于 建立或产生预取线索信息的步骤，内容服务器20从大量并发用户或客 户机中追踪使用/查访模式。在实践中，内容服务器20确定哪组对象 与所请求信息或所请求对象相关联。内容服务器20利用所请求对象产 生和提供预取线索信息(PHI)。在预取步骤或直接在该步骤之前，代理 服务器可以借助本地考虑去解释PHI，以决定要预取哪些选定对象。\n第五，在框106中，随着所请求信息通过代理服务器分层系统， 预取线索信息得到更新。在框106中的更新反映了所完成的预取操作 和在较高的各层中的高速缓存状态，以及诸如本地查访模式等其他本 地考虑。在把对象传送给下一(较低)层代理或客户相站之前，该代理服 务器可以修改PHI以反映它的预取决定和各种本地考虑。随着一个对 象通过代理分层系统，发送节点设置一个初始PHI，而接收节点可以 从这初始PHI中导出一个最终PHI。最终PHI根据所请求对象确定哪 些选定对象要预取。预取操作和决定是由接收端发起的，而不是由发 送端发起的。\n最后，在框108中，根据预取线索信息和所请求信息，选定信息 被预取。代理服务器或客户机根据所收到对象中的PHI信息、本地保 持的查访信息(如果能得到的话)和诸如可得到的存储大小等本地考 虑、以及访问时间，来决定是否预取在PHI中指定的对象子集。\n在框104中产生预取线索信息最好使用PICS协议或PICS兼容格 式(见下文)。在框104中产生的PHI与每个被高速缓存的对象一起存 储，作为其元数据部分，从而当一被高速缓存的对象被请求时，该对 象的PHI能被检查以发起适当的预取操作。PHI信息可通过PICS协 议提供。PICS协议提供关于每个PHI对象及其特征(如大小)的临界性 信息以及分层系统较高层的高速缓存状态。\n对预取线索信息的更新可通过代理服务器分层系统来完成。代理 服务器可以收集本地信息并在代理分层系统中向下分配或分发预取决 定。再有，关于哪个中间代理已预取了一个对象的信息能应用于较低 层代理的预取决定，以优化存储和带宽的利用。\n在代理服务器分层系统中的代理服务器彼此合作以提供指向接收 器的预取决定。该预取决定可以由每个代理和客户机合作作出。元信 息格式的预取线索信息注解(即附带)所请求对象。预取线索信息提供关 于潜在预取候选者的信息。中间代理服务器可以根据本地条件修改元 信息或预取线索信息，并在一对象被高速缓存时把它和元信息一起存 储，所以在其后一旦查访该对象预取便能被触发。\n图3B说明统计表261的数据格式。统计表261将通指第一统计表 293或第二统计表267。一个或多个代理服务器24维持第一统计表 293。内容服务器20可以维持第二统计表267。第一统计表293和第二 统计表267的格式最好相似或相同，以促进在代理服务器分层系统中 的不同代理服务器中更新统计表261。统计表261有助于根据从与统 计表261相关联的代理服务器或内容服务器20的角度看到的实际观察 者查询行为，提供预取线索信息(PHI)。统计表261能用于现察代理服 务器分层系统中在它之下的所有通信联系的客户机的查访情况。\n例如，在图1中，在第一3层代理服务器50中的第一统计表293 追踪第一客户机600和第二客户机603的集合数据访问行为。与此同 时，在第二3层代理服务器55中的第一统计表293追踪第三客户机700 和第四客户机703的集合数据访问行为。在第一2层代理服务器40中 的第一统计表追踪第一客户机600、第二客户机603、第三客户机700 以及第四客户机703的集合行为。虽然较低层代理，如第一3层代理 服务器50，可能会更好地跟踪客户机600的兴趣，但较低层代理可能 不能从客户机的足够样本量中得到足够的查访统计来提供有意义的预 取线索信息(PHI)。\n在本最佳实施例中，当对象O被从内容服务器20中请求时，服 务器20根据它的第二统计表267中的信息提供初始预取线索信息 PHI。当对象O沿代理分层系统下传时，沿到客户机22路径的任何代 理服务器24都能修改在对象标题中的预取线索信息(PHI)，以使PHI 符合于第一统计表293中的本地情况，如果存在对对象O足够的本地 查访的话。根据诸如由较低层代理服务器编好索引的一特定客户机的 兴趣或偏好，第一统计表293可以替换第二统计表267。\n在本最佳实施例中，内容服务器20保持第二统计表267，它是客 户机22关于所请求信息的数据访问频度数据库。该数据库可以扩展成 包括请求代理服务器24的数据访问频率。类似地，一个或多个代理服 务器24保持第一统计表293。例如，统计表261有具有第一数据结构 304和第二数据结构306的第一数据(array)383。如图所示，第一数据 结构304和第二数据结构306是记录。在统计表261中的每个记录包 含若干字段，包括父对象标识符301(即ObjectID)、第一计数302(即 TCount)、以及访问清单数据指针303(即Alist)。\n父对象标识符字段301含有对象标识符。例如，对于因特网或相 关应用，父对象标识符301含有对象的URL。第一计数字段302含有 由该服务器观察到的与该父对象标识符相关联的父对象被查访的次 数。就是说，第一计数字段含有所请求对象的实际请求次数。第一计 数302代表父对象访问频率。访问清单数据指针303含有指向访问清 单370的数据指针。\n统计表261有访问清单370，它含有例如第一访问记录340、第二 访问记录350、第三访问记录360以及第四访问记录380。如图所示， 与第一数据结构304相关联的父对象标识符有一访问清单370，它包 含第一访问记录340、第二访问记录350、以及第三访问记录360的被 链接清单。下一个记录数据指针字段313含有一个指针，指向与一特 定父对象标识符301关联的访问清单370上的下一个访问记录。与第 二数据结构306相关联的父对象标识符301的访问清单只包含第四访 问记录380。\n在访问清单上的每个记录或数据结构含有若干字段，包括子对象 标识符310(即AObjectID)，第二计数312(即RCount)、下一个记录数 据指针313(即Nxt)。数据结构可以是一般数据结构、记录或数组的格 式。如图4所示，该数据结构是记录，这些记录构成访问清单370内 部的一个被链接清单。\n在另一个实施例中，统计表的数据格式可以包括一个原初数组， 它与树结构中的多个另一种次级数组相关联。这原初数组将包含关于 父对象的信息，而次级数组将包含关于相应父对象的子对象的信息。\n子对象标识符310含有一对象的对象标识符(URL)。父对象标识符 301与访问清单上的一个或多个子对象标识符相关联。子对象标识符 310标识出潜在的预取候选对象，如果该子对象的父对象实际被查访 的话。第二计数312含有子对象通过其父对象被查访的次数。换句话 说，第二计数是在相关联的父对象先前查访之后接下来该子对象暂 时、紧接地被查访的频率。第二计数312代表子对象访问频率。\n可根据对客户机实际查访行为的观察，动态地得到访问清单370 上的子对象标识符310。例如，在HTML中，一个Web页面能有到达 其他Web页面的HTTP链路。由HTTP链路指出的那些Web页面是 含有这些HTTP链路的(父)Web页面的潜在子对象。当该父对象在被 观看时，如果在该父对象中含有的一个查访(HTTP)链路被点击，则相 应的子对象得到查访。由于到该子对象的查访链路能被包括在多个其 他父对象中，所以一个子对象能含有不只一个父对象。在HTTP协议 下，对子对象的请求包含父URL作为其标题中的查访者信息。所以服 务器能把其后的子查访动态地关联于它的父对象(通过子对象标题中 的查访者信息)。如果一个客户机频繁地点击或选择一个子对象，该子 对象可能变为预取候选或选定信息。\n除了动态追踪观看者查访行为外，还能周期性地完成对Web日志 的静态分析或挖掘(mining)，以提取统计表261的对象组合信息。挖掘 算法识别一起被查访的对象组，以得到潜在的预取对象组用于HPI(预 取线索信息)。在Kun-lung Wu等的“Speed Tracer(高速追踪器)：一 种Web使用情况的挖掘和分析工具”(IBM研究文档20895，1997年5 月(见IBM系统杂志V37，n1，p89-105，1998))中描述了挖掘Web日志 以提取查访模式的一种方法。Speed Tracer算法提供关于在一个使用 者对话中被频繁共同查访的页面组的信息和频繁往返路径的信息。 Speed Tracer算法是一种深处挖掘型算法，它能发现不是立即被共同 查访的相关联查访。它还能根据到给定对象的往返路径对下一组板查 访对象作出较好预测。\n其他类型的数据挖掘算法能被用于识别统计表261的访问模式。 例如，其他数据挖掘算法包括分类和集群(clastering)，它也能用于Web 日志分析以得到查访模式。再有，还能由内容提供者根据它对对象关 系的了解来提供PHI。例如，PHI能包括，但不限于，所请求软件下 载的修补和升级、所请求JAVA小应用(applet)的Java类、以及在所 请求对象内包含的各对象(例如GIF)。\n在本最佳实施例中，在收集统计信息时，由客户机站对一对象的 实际查访是与对一对象的预取请求区分开的。在统计表261中的第一 计数302(即TCount)和第二计数310(即RCount)反映的是实际查访， 而不是预取。这就是说，预取操作将不造成对第一统计表293或第二 统计表267的更新，只有实际的对象查访才将造成这种更新。\n预取线索信息或预取线索信息清单能使用各种数据结构来注解所 请求信息或所请求对象。例如，预取线索信息可以使用搭载的元数据 在请求者和服务器节点之间通信。在一个HTTP实现中，信息交换可 作为元数据包括在使用现有万维网协议的对象标题中。PICS(因特网内 容选择平台)指定了一种发送关于电子内容的元信息的方法。PICS可 应于(a)所请求信息的注解，(b)预取选定信息、预取候选者、或子对象， 以及(c)在信息被预取后确认预取操作。\nPICS是作为万维网联合协议推荐(Web Consortium Protocol Recommendation)的一种本领域周知技术。PICS最初是用于发送基于 值的定额标签(rating label)，如“有多少裸露(nudity)与本内容相关 联”，但元信息的格式和含义是全通用的。在PICS中，关于电子内 容的元信息根据该信息的“定额服务”或“产出者的预期应用”来分 组，而在这样的一组内部可以传输任意多的信息类别或维数。每个类 别有一个允许值范围，而对于特定的一条内容，一个特定类别可以有 单一值或多个值。此外，元信息组(称作“PICS标签”)可以包含期满 信息。还有一些手段允许把PICS标签应用于不只一条电子内容。用 于具体的一条电子内容的每个PICS标签，能独立地加到该内容上或 从该内容上去掉。\n例如，可以从一服务器发送一个图像文件，它带有一个PICS标 签，该标签的“定额服务”字段指出，它含有根据“Safe Surf(安全漫 游)”定额系统给出的基于值的定额标签。根据本发明的最佳实施例， 当该图像文件传送通过一个企业级代理时，它可能在PICS标签上得 到一个新的被更新的类别值，以反映“定额服务”的本地考虑。这样， 客户计算机将只看见PICS标签的新类别值。HTTP协议已被扩展，从 而使其请求标题和响应标题支持PICS。规定其他公共应用协议(如 NNTP)的技术团体现在也在考虑增加对PICS的支持。可以把所希望的 PICS标签类型清单与请求一起包括进去，作为这些协议的组成部分。 PICS还指定一个询问格式，用于从一个中央标签局(bureau)服务器请 求PICS信息。\n一个PICS标签实例是：\n(PICS-1.1“http://the.rating.service”labels for\n“http://the.content”exp“1997.07.09 T 08：15-0500”r(n 4s 3\nV2))\n这里“n”、“s”和“v”是各种元信息类型的传送名，这些内容的可 应用值是4(对于n)、3(对于s)和2(对于v)。只有认识标识符 “http://the.rating.service”的软件才会知道如何解释这些类别和值。\n在一个最佳实施例中，引入了三种不同的PICS标签。第一种PICS 标签称作预取标签(即P-标签)，由服务器节点用于提供PHI。第二种 PICS标签称作请求标签(即R-标签)，用于请求预取候选对象。第三种 PICS标签称作查访标签(即X-标签)，用于根据哪些预取对象实际得到 查访来提供对预取有效性的反馈。\n预取标签能包括，但不限于下述类别的组合，包括标识符类别、 概率类别、大小类别、以及高速缓存类别。标识符类别(即ID类)有一 个值，它传递预取候选者的URL。概率类别(即PROB类)有一个值， 它传递预取有用性概率。在本最佳实施例中，使用一个查访概率估计 值。查访概率指示该预取候选者得到查访的概率。大小类别有一个值， 它传递预取候选者的大小或存储器需求。高速缓存类别有一个值，它 传递关于任何较高层代理服务器的信息，该代理服务器或者在其第一 主高速缓存294中或者在其第一预取高速缓存296中有该预取候选对 象的副本。在本最佳实施例中，只有最靠近的较高层代理被标识出来。\n请求标签能包括但不限于如下类别，包括标识符类别(即ID类 别)。标识符类别的值传递要被预取对象的URL。在本最佳实施例中， 当一个(代理或客户机)节点要预取一个被建议的预取候选对象时，使用 请求标签传递要被查访的对象的URL，通过代理分层系统，把一个 HTTP标题请求送回内容服务器。当代理服务器24从一较低层节点收 到一个预取请求时，如果该对象在这个代理服务器24的主高速缓存中 或其预取高速缓存中，则它将服务于该请求。否则，它把该预取请求 向前送到下一个较高层代理。\n查访标签可包括，但不限于如下类别，包括对象标识符类别 (Object-ID类别)和查访者标识符类别(Referrer-ID类别)。对象标识符 类别有一个值，它传递得到查访的预取对象的URL。查访者标识符类 别有一个值，它传递一个对象的URL，该对象在其PHI中含有由对象 标识符类别值指出的对象。\n在本最佳实施例中，当一预取对象得到实际查访时，则用查访标 签通过代理分层系统将一HTTP标题请求发送回内容服务器20，以传 递被查访的预取对象及其查访者对象的URL。在后面把这种类型的 HTTP标题请求称为预取被查访消息。当一代理服务器24从一较低层 节点收到一预取被查访消息时，它更新其第一统计表293，并把该请 求向前传送给下一个较高层代理服务器。\n图4描述服务器逻辑268的一个实例，它更新内容服务器20中的 第二统计表267。对第二统计表267的更新是由来自客户机22的一个 对象请求触发的。内容服务器20最好在把所请求的对象发送给客户机 22之前，先产生一个预取线索信息，以作为注解放入或插入到该对象 的对象标题中。\n在参考框405开始，内容服务器20等待输入。在决策框410中， 如果所收到的输入是对请求对象O的一个对象请求，则在参考框415 统计更新单元252或第二更新统计例行程序269被调用。在参考框 420，用于产生预取线索信息266的产生单元266或一预取产生便行程 序被调用。在下文中将参考图6描述产生单元266或PHI产生例行程 序的更详细举例。在参考框425，例如PHI被插入所请求对象的对象 标题内。否则，预取线索信息可以在框425中注解所请求对象或所请 求信息。在本最佳实施例中，PICS协议可以用于注解所请求对象。PHI 被收集在P-标签中，在那里标识符类别值反映预取候选者的URL。在 框430中，所请求对象被送回到发请求的客户机或发请求的代理服务 器。在决策符号435中，如果所收到的输入是一预取被查访消息(即带 有X-标签的HTTP标题请求，它指出预取对象O实际得到查访)，则 在步骤440统计更新装置252或第二更新统计例行程序269被调用。 对于其他类型输入，它们不是本发明的集中点，例如一个FTP(文件传 输协议)请求，可以在参考框445中调用适当的其他处理器。\n图5显示统计更新单元252如何更新所求统计表261之一。统计 更新单元252是指用于更新第一统计表293的第一更新统计例行程序 264，或用于更新第二统计表267的第二更新统计例行程序269，或者 指第一更新统计例行程序264和第二更新统计例行程序269二者。统 计表261或者指第一统计表293，或者第二统计表267，或者指第一统 计表293和第二统计表267二者。统计更新单元252首先查找查访者 对象中的信息。然后所请求对象被放在查访者对象的访问清单或预取 清单中。\n在参考框505开始，统计表261通过使第一计数递增，来反映对 象O已经又被查访了一次。换句话说，在框505中TCount(O)被增1。 如果对象O尚未在统计表261中，则一父对象标识符被插入统计表 261，并使TCount(O)的初值为1。如果在统计表261中得不到空的位 置，则新的父对象标识符替代最近最少被查访的条目。在决策符号510 中，通过例如检查所请求对象的对象标题，来检查所请求对象，以得 到查访者信息。例如，在HTTP协议中，在标题中提供查访者对象以 指出哪个对象含有与所请求对象的HTTP链接。如果在标题中发现了 一个查访者对象(R)，则在步骤520统计表261被检验，看看对象O是 否已在对象R的访问清单上。如果是，则在框530对所请求对象使其 第二计数(即RCount(O))增加1。否则，在框525，所请求对象(即对象 O)被插入父对象(即对象R)的访问清单中，并使第二计数(即RCount(O)) 初始化为1。\n图6描述产生单元266的一例，产生单元266用于产生放入预取 线索信息清单的预取线索信息。预取线索信息清单含有子对象的子对 象标识符，如果第二计数与第一计数之比超过一个线索阈值的话。预 取线索信息清单代表一个精炼过的或过滤过的访问清单。就是说，产 生单元266从统计表261接受输入并对输入过滤，以得到预取线索信 息清单。\n产生预取线索信息的产生单元266代表一个预取线索信息(PHI)产 生例行程序266，它在参考框610中开始。在参考框610中，一个父对 象(即对象O)的访问清单被检验，看它是否为空的(即Alist(O)是否为 “空(null)”)。如果访问清单不是空的，则在参考框620中令Cj为该 父对象(即对象O)的访问清单上标识的下一个子对象(即子对象标识 符)。\n在决策符号630中，子对象Cj的查访概率与一线索阈值(即TH) 比较，线索阈值(TH)是预先指定的阈值值(例如0.75)。在本最佳实施例 中，Cj的查访概率被定义为第二计数与第一计数之比(即 RCount(Cj)/TCount(O))。该比值是在父对象(对象O)被查访之后子对 象(对象Cj)得到查访的概率的估计值。如果在决策符号630中，Cj的 查访概率大于线索阈值(即TH)，则在参考框640中子对象标识符(Cj) 将被包括在PHI清单中。换句话说，如果该比值超过信息阈值，则该 子对象标识符和相关联信息被放在预取线索信息清单上。\n产生单元266可能需要软件子例行程序或软件组成部件以在参考 框630中实现比较。具体地说，用于产生预取线索信息放入预取线索 信息清单的产生单元266可以包括计算查访概率的计算手段和把查访 概率与线索阈值进行比较的比较手段。\n在本最佳实施例中，使用PICS协议，PHI信息存在P-标签中， 这里子对象(Cj)的URL被取作标识符类别(即ID类别值)，它的查访概 率和大小被分别取为概率类别(即PROB)和大小类别值。在决策符号 645中，如果对象O的访问清单尚未被完全扫描，则查访框620将被 再次执行。\n可有各种不同的判据用于从统计表261中选择预取候选者。例 如，可把过去时间间隔的查访概率滑动平均作为判据。再有，预取候 选者选择过程可以做成迭代式的。如果一个子对象(对象Cj)被选作父 对象(对象O)的预取对象，则在子对象(对象Cj)的访问清单上的任何子 对象(对象Cji)可以被评估，以确定是否要被包括在父对象(对象O)的 预取清单中，如果尚未被包括的话。在决策符号630中，比较单元或 评估单元现在可以测试RCount(Cj)/TCount(O)和RCount(Cji)/ TCount(Cj)二者乘积是否大于线索阈值(TH)。\n图7描述客户机逻辑244的操作举例。图7显示，一旦一个对象 被请求，则客户机对象请求处理器247便被调用。否则，预取处理器 241可以处理那些没有被请求但需要存储在客户机22的第二预取高速 缓存249中的对象。\n在框710中开始，客户机22等待输入。在决策符号720中，如果 所收到的输入是一对象，则在参考框730中第二预取处理器241被调 用。在框740中，客户机对象处理器被调用，以把对象回送给客户机 22处发请求的应用程序。如果在决策符号750中所收到的输入是一对 象请求，则客户机对象请求处理器247在参考框760处被调用。对于 其他类型输入，它们不是本发明的集中点(例如推入(push)请求)，在参 考框770中可调用一适当的其他处理器。\n图8描述预取单元250的操作举例，其包括第一预取处理器248、 或第二预取处理器241、或第一预取处理器248和第二预取处理器241 二者。总之，预取单元250使用图6中的产生装置266所产生的预取 清单作为输入，以确定在预取线索信息清单上所查访的子对象是否有 理由存储在预取高速缓存298之一中。预取单元250为预取线索信息 清单上的每个预取对象候选者或子对象标识符计算一个预取值。该预 取值考虑子对象的访问概率和存储子对象的访问费用。具有最高阈值 值的那些子对象被首先高速缓存，直至预取高速缓存298之一中可能 得到的空间被充满为止。\n在参考框805开始，令L为预取候选对象的PHI清单。预取候选 对象可以以预取线索信息清单上的子对象标识符形式来表示。在本地 高速缓存(即预取高速缓存或主高速缓存)中出现的任何预取候选者被 从L中去掉。在框810中，L中每个对象的预取值(PV)被计算出来。 在本最佳实施例中，PV值被定义为查访概率乘以访问费用。访问费用 是基于高速缓存预取候选对象或PHI清单上标识的子对象的最近场地 而估计出来的。作为一个实践中的问题，子对象最好在PHI清单上由 子对象标识符来识别而不是作为整个子对象，以节省存储空间。查访 概率最好来自概率类别(PROB类别)值，而最靠近的高速缓存场地来自 PICS标签的高速缓存类别值。在框820，具有最高PV值的预取候选 对象被选择。在参考框830，确定为容纳该预取候选对象(即Oj)所能 得到的预取缓存空间量。这一空间或者是当前没有使用的，或者被有 较低PV值的对象所占据，这些较低的PV值只是被评估的当前预取候 选对象(即Oj)PV值的一分数(例如一半)。在预取高速缓存298之一中 被标记为可删除的对象所占有的任何存储空间被认为是当前未使用的 空间。在决策符号840中，预取高速缓存298之一被检验，看看是否 有足够的空间给Oj。如果是，则在参考框850中，对象Oj被预取到 预取高速缓存298之一中。在框860，Oj从PHI清单(即L)中去掉。 在参考框870，如果L不是空的，则重新执行与参考框820相关联的 步骤。\n虽然在本实施例中，每次预取一个对象，但在一个请求中能一起 预取多个对象。在参考框850中，Oj可被放在一个预取清单上。在框 870，如果L为空的，则以这整个预取清单发出预取请求。再有，即使 在预取高速缓存中没有足够的存储空间，仍可维持一个待决预取清 单，从而当存储空间变为可得到时，能发起补充的预取。\n通过使用HTTP协议，在预取过程中该通信对话能保持开放，以 减小通信开销。无需对每次预取重新建立对话。\n图9描述客户机对象请求处理器247的操作举例。概括地说，客 户机对象请求处理器247首先搜索第二主高速缓存246，然后再搜索 第二预取高速缓存249。如果该对象既不在第二主高速缓存246又不 在第二预取高速缓存249中，则向服务器发送一个对象请求。如果该 对象是在第二预取高速缓存249中，则有一个预取被查访消息发送到 服务器之一，以指出该预取对象实际被查访过。然后，这第二预取处 理器241和客户机对象处理器被使用。\n在决策符号905处开始，如果在第二主高速缓存246中发现了所 请求的对象，则在参考框925中第二预取处理器241被调用，以根据 与对象O关联的PHI发起适当的预取操作。在参考框930，客户机对 象处理器被调用，以把所请求对象回送给客户机处发请求的应用程 序。在决策符号910中，如果在第二预取高速缓存249中发现了所请 求的对象，则在框920中向内容服务器20发送一个预取被查访消息， 从而使它的第二统计表267能被更新，以包含对该预取对象的实际查 访。事实上，当预取被查访消息通过代理分层系统传播到内容服务器 20时，在每个中间代理中的第二统计表267也将得到更新。在框910， 如果该对象不在第二预取高速缓存249中，则在参考框915中通过代 理分层系统向内容服务器20发送一个对象请求。\n预取被查访消息可以批处理。就是说，可以维持一个预取被查访 清单，并周期性地向较高层服务器发送一个组合预取被查访消息，以 确认预取被查访清单上所有对象的查访。\n图10描述代理服务器逻辑295的操作举例。概括地说，对输入根 据该输入是否是一个对象请求、对象传输、或预取被查访消息进行分 类。根据该输入，可得到三种不同的处理器或软件例行程序：代理对 象请求处理器283、代理对象处理器284、以及所预取的查访消息处理 器285。\n在参考框1005开始，代理服务器24等待输入。如果在决策符号 1010中所收到的输入是对对象O的对象请求，则在框1015中代理服 务器24检验是否已经存在一个对该对象O的待决请求。这个待决请 求可能是由于由这个代理服务器24发出的对对象O的预取请求，或 者是由另一个代理服务器节点在早些时候发起的对该对象O的请求， 而这另一个代理服务器节点在代理服务器分层系统中是一个较低层的 节点。如果在参考框1015中没有对对象O的待决请求，则在框1020 中代理对象请求处理器283被调用。在决策符号1025中，如果所收到 的输入是一个对象(来自较高层代理)，则在参考框1030中代理对象处 理器284被调用。否则，在框1040，如果所收到的输入是一个预取被 查访消息，则在框1045中调用预取被查访消息处理器285。对于其他 类型的输入，它们不是本发明的集中点(如FTP请求)，这可在框1060 中调用适当的其他处理器。\n图11描述代理对象请求处理器283的操作举例。概括地说，如果 对象在预取高速缓存中，则该对象被回送或发送到发请求的客户机， 或发请求的代理服务器。在此之后，如果所请求的对象是一个预取请 求，则所请求的对象被标记为可从代理服务器24的第一预取高速缓存 296中删除的。如果对于所请求的对象未曾提供过预取请求，则把一 个预取被查访消息发送给内容服务器20。然而，只有当从第一预取高 速缓存296中发送出所请求对象时，才发送所预取的查访消息。如果 一个所请求的对象既不在第一预取高速缓存296也不在第一主高速缓 存294，则向另一代理服务器24或内容服务器20发送一个对象请求。 在第一主高速缓存294中发现的所请求对象被回送或发送到发请求的 客户机或代理服务器24并且第一统计表293被更新，如果该请求不曾 是一个预取请求的话。\n在决策符号1105中开始，如果在预取高速缓存中发现所请求对象 O，则在框1130中对象O被回送到发请求的节点。在决策符号1135 中，如果该请求是一个预取请求，则在框1150中把第一预取高速缓存 296中的对象O标记为可删除的。从第一预取高速缓存296中删除对 象为将来的预取造成了空间，因为该预取对象O现在已被代理服务器 24的一些较低层节点预取了。否则，在参考框1140中，高速缓存管 理器被调用，以把对象O从第一预取高速缓存296移到第一主高速缓 存294，因为对象O已实际被查访。在框1160，一个预取被查访消息 通过代理分层系统服务器发送到内容服务器20。在框1170，更新统计 例行程序被调用，以更新本地第一统计数293，以包含该预取对象O 的实际查访。在决策符号1110中，如果没有在第一主高速缓存294中 发现该对象，则在参考框1125通过代理服务器分层系统向内容服务器 20发送一个对象请求。在决策符号1115中，如果该对象请求不是一 个预取请求，则在框1120中第一更新统计例行程序264被调用，以更 新本地第一统计表293，使其包含该对象的实际查访。在框1180，对 象O被回送到发请求的节点。\n图12描述预取被查访消息处理器285的操作举例。预取被查访消 息处理器285首先看看一个对象是否在第一预取高速缓存296中。如 果该对象是在第一高速缓存296中，则在传送预取被查访消息之前先 调用高速缓存管理器例行程序。如果该对象不在第一高速缓存296 中，则把预取被查访消息传送出去。\n在步骤1205开始，第一更新统计例行程序264被调用以更新本地 第一统计表293，使其包含对预取对象(O)的实际查访。在决策符号1210 中，如果对象O是在第一预取高速缓存296中，则在参考框1215中 高速缓存管理器被调用，以把对象O从第一预取高速缓存296移到第 一主高速缓存294，因为该对象已实际被查访。在框1220，预取被查 访消息传送到下一较高层代理。\n图13描述代理对象处理器284的操作举例。代理对象处理器284 首先调用预取更新单元291或预取线索信息更新例行程序，对此一律 进行没有例外。根据预取对象是否被较低层服务器请求过，预取对象 请求被不同的处理。如果该预取对象是被一较低层服务器请求过，则 把该对象回送给该较低层服务器；否则调用预取高速缓存管理器。如 果一预取对象未被请求，则把该对象回送给发请求的代理服务器24或 客户机，并调用第一更新统计例行程序264。\n在参考框1305开始，PHI更新例行程序或预取更新手段291被调 用，以更新对象O的PHI。在参考框1310，如果所收到的对象不是一 个预取对象，则在步骤1315调用第一预取处理器248。在参考框1320， 该对象被回送到发请求的节点(在较低层中)。在该最佳实施例下使用 PICS协议，在P-标签中的高速缓存类别值被更新，如果相应的预取候 选对象(由标识符类别值指示)是被这一代理服务器24预取的话。在框 1325，高速缓存管理器被调用，以把该对象存储在主高速缓存中。在 参考框1355中，更新统计例行程序被调用。在框1330中，如果所收 到的预取对象被分层系统中的更低层节点所请求，则在参考框1350中 把该对象回送给请求者。否则，它被当前节点请求，并在参考框1340 中调用预取高速缓存管理器，通过进行必要的替换以给该对象造成空 间，把该对象存储在预取高速缓存。\n图14描述预取更新手段291或PHI更新例行程序的操作举例。 PHI更新例行程序把所请求对象的本地计数与一预值计数作比较。如 果所请求对象超过了第一最小阈值，则它们受第二最小阈值测试。这 些阈值可根据经验结果设定。如果本地计数小于第一最小阈值，则保 持原来的预取线索信息清单。如果本地计数大于第一阈值，但不大于 第二阈值，则预取线索信息清单被修改。\n在决策符号1405中开始，如果在本地第一统计表293中对象(O) 的本地计数(即TCount)不大于第一最小阈值(即CTM)，则保持该对象 O标题中的原来PHI。这只是由于这样的事实，即在代理服务器较低 层中对该对象没有进行过足够的查访以证明需要进行任何更新行动。 在决策符号1415中，如果在本地统计表261中对象(O)的本地计数(即 TCount)大于第二最小阈值(即TCH)，则忽略该对象标题中的原来 PHI，并在框1420中调用PHI产生例行程序以根据本地第一统计表293 产生PHI。这是因为在代理服务器24的较低层中有对该对象足够的查 访，从而能基于其本地行为产生PHI。否则，在参考框1425中调用 PHI修改器，对查访概率本地估计值和PHI清单中每个对象标题(由较 高层设置)中的概率值取平均，以此来修改概率类别值。\n即使代理服务器24中有一些并没有保持第一统计表293和追踪本 地查访模式，该预取方案仍然有效。非追踪的代理服务器简单地接收 从较高层代理服务器或内容服务器20传下来的PHI中概率(即PROB) 类别值。\n该预取方案在多机种代理服务器环境中也仍然有效，在那里一些 代理服务器是不理解预取协议和不参加这一合作的传统代理服务器。 这些传统的代理服务器既不解释对象标题以发动预取操作，也不保持 第一统计表293。传统代理服务器将只是把元数据(即标题中的PICS 标签)和对象一起传送给下一层代理服务器，或者把元数据与对象一起 存储起来，如果它决定本地高速缓存该对象的话。\n即使不存在代理分层系统，本发明也能应用于任何网络或客户机/ 服务器环境。对象发送者节点能追踪查访模式，导出PHI，并将其包 括在对象标题中。此外，对象接收者节点可在它的高速缓存中存储PHI 和该对象。一旦查访该对象，则能基于所存储的PHI和本地因素(如前 文讨论过的高速缓存大小和访问费用)来发起预取操作。\n与高速缓存的对象一起存储PHI为预取提供了额外的机会。诸如 有更多存储空间变为可使用、发生额外的查访、或收到预取对象的这 些事件能被用于通过检验被高速缓存对象的PHI来触发额外的预取。 预取操作不限于从服务器请求对象的时刻，即不象由发送者发起的过 程那样。\n在本最佳实施例中，已对Web和代理服务器的通用预取策略进行 了描述，但本领域技术人员将会理解，本发明可适用于被预取对象具 有类似特性的任何场合类型，并不一定限于因特网或万维网应用。\n再有，尽管本发明的最佳实施例是针对分层系统中父代理和子代 理之间的联合预取，但它能容易地适应于包括兄弟代理之间的联合。 例如，如果在较高层没有代理高速缓存了所请求的对象或预取候选 者，一个代理还能质询那些兄弟代理。