第 25 卷第 12 期 2008 年 12 月 计 算 机 应 用 研 究 Application Research of Computers Vol. 25 No. 12 Dec . 2008 一 种 基 于 DHT 的 W eb 缓 存 共 享 方 法 * 刘 建 a, b, 孙晓辉 a, b , 倪 宏 b ( 中 国科 学院 a. 研究 生院 ; b. 声 学研 究所 , 北京 100190) 摘 要: 提出 了一种 基于 DHT 技术 的 Web 缓存 共享 方法 。该方 法使 得企 业网 络中 所有 节点 能够 相互共 享浏 览 器中 的本 地缓 存, 从而 形成 一个 高效的 、大规 模的分 布式 缓存 共享 系 统。 针对 Web 缓存 共 享 的系 统 响 应迅 速 的 要求 提出 一种 路由步 长为 O( 2) 的路 由协 议, 保证 Web 查询 请求最 多只 经过 一 次转 发 就 可到 达 目 标节 点 。性 能 分析 和仿 真实 验的结 果证 明其 在路 由可 靠性 、命 中率 、系 统响 应和 缓存 代价 方面 均有 满意 的效果 。 关键 词: 分 布式 哈希 表; Web 缓 存; 命 中率 ; 系统 响应 中图 分类 号: TP303 文 献标 志码: A 文 章编 号: 1001- 3695( 2008) 12- 3804- 03 Web caching system based on DHT architecture ( a. Graduate School, b. Institute of Acoustics, Chinese Academy of Sciences, Beijing 100190, China) LIU Jiana, b, SUN Xiao-huia, b, NI Hongb Abstract: This paper proposed a Web caching plan based on DHT, whose underlying ideology was that all the terminals in an Intranet were able to share their local caching to constitute a large-scale, effective distributed Web caching system. Given the responding rapidly characteristic of Web caching, proposed a new routing scheme with a constant O( 2) hop per lookup re- quest, with which a Web query request could reach the target node within only one transfer. Furthermore, the evaluation re- sults prove that it achieves a satisfied performance in routing reliability, hits-ratio, latency of response and caching cost. Key words: distributed hash table( DHT) ; Web-cache; hits-ratio; system response Web 缓存技术实 现 Web 内容的 关键 节点 存储, 它 能减 少 网络带宽的占用, 改 善响应 时间, 提高用 户的访 问效率。现 在 大多数 Web 缓存 技 术采 用 代 理服 务 器 和网 络 缓 存的 方 式 实 现, 即缓存内容保存在特 定的缓 存服务 器上面, 这样 可能会 造 成缓存服务器负载过重, 没有充分利 用网络上 大部分 PC 节 点 的带宽, 距离缓存服务器很远的节点响应速度没有改善。如果 让网络中的节点能够共享本地缓存, 不仅可以提高用户的 Web 信息获取速度, 而且可以大大降低该网络的外部流量。 本文提出一种基于 P2P overlay 结构分布式 Web 缓存共享 方法, 采用分布式哈 希表 ( DHT) 将 节点 和缓 存 目录 信息 均 映 射到同一个键值 空间 ( 或者 叫做 标号 空间) 中, 键 值 为 k 的 缓 存目录信息存储在标号为 k 的节 点上。所有 Web 缓存对象 目 录信息均匀分布在所有节点 上, 节点负 载小, 同时采 用分区 域 管理的方式, 使 得缓 存 目 录信 息 查 询路 由 最 多只 需 要 O( 2) 步, 即查询消息最多只经 过一次 转发就 可以定 位到目 标节点, 大大提高了缓存响应的速度, 保证缓存获取的高效性。 1 相关研究 基于 DHT 各种应用的区 别在于 路由 方式 的不 同, 每个 基 点上的路由表保存了不同的信息, 导致路由步长不一样。一种 是如 Chord[ 1] 、Pastry、Tapestry、Koorde、Viceroy 采用 多跳 路 由 方式, 路由表仅需 要维 护 O( log N) 或 O( 1) 个 节 点的 状 态 信 息, 查询步长均为 O( log N) 。另 外一种 是 Kelips[ 2] 系 统, 以 及 A. T. Mizrakd 等 人和 A. Gupta 等人 提出 的采 用超 级节点 结 构 的单跳路由算法 [ 3] , 每个 超 级节 点 的路 由表 维 护全 局路 由 状 态, 路由表维护( O( N) ) 或 O( N) 个 节点的状 态信息, 但查 询 路由步长仅需要 O( 1) 跳。 √ Web 共享的目 标是 共 享所 有节 点 上的 缓存 信 息, 用 户 需 要系统响应迅速, 可以很快 定位目 标节点 并获取 缓存, 同时 保 证节点维护代价比较小。现在提出的基于 P2P 的 Web 缓存 共 享方法已经有人提出: BuddyWeb[ 4] 采用自适 应跳步 算法查 询 目标节点, 步长 2 ～7, 聚 类失 败将 会导 致查 询失 败; Squirrel[ 5] 基于 Pastry 构建 DHT, 查询 路由 步长 为 O( log N) ; Kache[ 6] 路 由步长为 O( 1) , 但是每个节点 需要保 存位于 当前分 组的所 有 节点上的缓存目 录信 息, 并 采用 泛 洪方 式进 行 组内 信息 的 传 递, 目录信息存储和维护代价高。 本文试图找到一种查询 步长短, 节点 负载小, 缓存 内容 及 目录信息分布存储的 Web 缓存 共享 方法。采 用 DHT 的 over- lay 结构, 可以使节 点地 址和 Web 缓 存得 到统 一, 通 过缓 存 对 象的 hash 值可 以 查 询到 存 储 该缓 存 的 源节 点 地 址。考 虑 到 chord 环的抗干扰性和 Kelips 的 分组 思想, 设 计一 种节 点易 于 管理、抗干扰性强、常数路由步 长的 DHT 方法, 作为 Web 缓 存 共享应用的基础。 2 实现方法 2. 1 路由协议 通过一致性 hash 函数如 SHA-1 将节点 n 映射为节点空 间 ( k ×m) 中的一点, 用 hash 值( k, id) 来表示每一个节点。形 象 收 稿日期 : 2008- 03- 13; 修 回日期 : 2008- 05- 23 作 者简介 : 刘建( 1982- ) , 男, 湖南 人, 博士研 究生 , 主 要研究 方向 为网络 新媒 体( liuj@ dsp. ac. cn) ; 孙 晓辉( 1981 -) , 男, 博士 研究 生, 主要研 究方 基 金项 目: 国 家下 一代互 联网 示范工 程资助 项目 ( CNGI-04 -15 -2A) 向为信 号与信 息处 理; 倪宏 ( 1964 - ) , 男, 研究员 , 博导, 主要 研究 方向为 网络 新媒体 、多 媒体 通信 . 

第 12 期 刘 建, 等: 一种 基于 DHT 的 Web 缓存共 享方 法 ·5083· 地说, 首先将所有节点 分为 k 个子 区域, 每个子 区域内 的所 有 节点 均匀分 布在大 小为 m 的环形 值域空 间, 那 么在节 点 n 的 hash 标号( k, id) 中, k 为区域标号, id 为子区域环上标号。 节点通过 URL 的 hash 值建立本地 缓存目 录索引, 所有 的 缓存对象放在一个 hash 表中, 通过 hash 值可 以很快 查找出 对 应的缓存信息。 所有 Web 缓存对象的 目录 信息 分布 存储 在所 有节 点中, 将缓存 URL 作为 key 并 通过 hash 运算 映射到 空间 ( k ×m) 中 的一点( k, id) , 该 键值 为 key 的 缓 存对 象 的 目录 信 息 ( IP, 端 口) 就存储在节点( k, id) 的 后继节 点上 ( 类 似 chord 定 义节 点 ( k, id) 的后继 节点( k′, id′) 满 足: 首先 k′= k, 即位于同一 个子 区域; 其次 id′≥id, 即如果节点( k, n) 是 活动的, 那么其后 继节 点就是它本身, 否则是环上该节点后面的空间距离最近的活动 节点) 。图 1 所示为( 6 ×8) 个节点的子区域划分情况。 每个节点管理的信息包括本地缓存信息、缓存目录信息和 路由表。 a) 本地缓存信息指该节点上 实际存储的 各种 Web 缓存信 息, 包括 URL、缓存内容、缓存大小、上次修改日期、过期日期等。 b) 因为目录标号为 ( k, n) 的 缓存信 息存 储在 节点 标号 为 ( k, n) 后继节点上, 所以缓存目录 信息指该节 点负责 管理的 缓 存目录, 包括目录标号, 网络中 实际存 储该缓 存的源 节点的 信 息列表( IP 和端口) 。图 2 为 节点( 4, 3) 的缓 存目录 信息表 结 构图。 c) 路由表包括两 部 分, 即子 区 域内 所有 节 点的 路由 信 息 和其他子区域内的邻居节 点。通过前 者可以 单跳到 达本子 区 域内的任意节点; 通过后者可以单跳到达空间内的其他任意子 区域, 这种结构可以保证最多两跳查询到目标节点。子区域内 节点路由信息一共 m 项, 每 一项 包括后 继节 点标 号和 IP。区 域间路由信息包 括( k - 1) 项, 每一 项保 存其他 子区 域内 物 理 距离较近的物理邻居节点列表, 包括节点标号、节点 IP 和 网络 延时 RTT 值。图 3 表示节点( 4, 3) 的路由表结构。 2. 2 本地缓存管理 当节点发送请求或者收到响应以后, 首先应该判断请求或 者响应 的 Web 对 象 是 否 能 够 缓 存, 因 为 现 在 有 越 来 越 多 的 Web 对象具有动态性交互性, 不 符合缓 存的条 件, 没 有必要 向 其他节点查询 Web 共享缓存, 直接向 服务器请求, 可以加 快用 户的响应速度。判断 Web 对 象的可 缓存性 可以通 过分析 http 的请求方式, http 的响 应状态 码 和 URL 的 后 缀属 性等 方 法 [ 7] 来判定。节点通过解析 http 请求和响应的报文, 通过特定的规 则, 来判断出对象的可缓存性。 / / 缓存 网页 的 URL / / 缓存 数据 的地址 / / 缓存 数据的 大小 节点为每个缓存对象建立一个结构体, 保存缓存信息: typedef struct{ const char* url, void * cache_data, size_t size, PriorityListNode * pnode, / / 优先 级链 表节点 指针 const char* content_type, const char* response_header, / / http 响应 头 int last_time_modified, / / 上次修 改时 间 / / 上次访 问时 间 int last_time_visited, / / 过 期时 间 int time_expired, / / 缓存 命中次 数 int visit_times, / / http 响应 头中的 content-type } CacheData; 为保持缓存对象的一致性, 必须对缓存作不定时更新和清 除等。节点为所有缓存的 引用维 护一个 双向 列表 priorityList, 采用 LRU( least recently used) 策略 对缓存 进行维 护, 如果缓 存 被请求命中, 将该对象调整 至列表 首位, 最新 命中的 缓存和 命 中次数多的缓存具有较高的优先级。当 Web 对 象第一次被 缓 存时, 该缓存引用加入列表 首位, 同时 将该缓 存目录 信息通 知 此节点对应的目录索引节点。系统也不定期地进行缓存清理, 维持缓存规模大小和最新状 态, 将 时间过 期的、命中 次数低 的 缓存对象从 hash 表和 priorityList 中清除, 同时通知保存该目录 信息的节点更新其缓存目录信息, 保持系统同步更新。 2. 3 节点查询 节点截获到自身的 http 请求以后, 首先判断是否满足缓存 条件, 如 果可 缓存, 向 网络 中其 他节 点查 询, 否则直 接向 Web 服务器请求。向其他节点查询缓存的过程如下: a) 首先计算 URL 的 hash 值, 得到该目录 存储的 目标节 点 ( k, id) 。 b) 若目标节点在本子区域, 直接转发给( k, id) 的后继节点; 否则, 向路由表区域 k 中物理距离最近的邻 居节点发送 目录查 询请求, 邻居节点再将查询请求转发给( k, id) 的后继节点, 如果 命中, 将缓存目录信息返回, 否则返回查询失败的消息。 c) 发起者收到目 录 信息, 向 实 际存 储该 缓 存的 节点 发 送 缓存内容请求, 在规定时间内如果收到内容, 则查询结束; 否则 直接向 Web 服务器请求 Web 对象。 d) 发起者获取了完整的 Web 对 象以 后, 如果 该对 象可 缓 存, 将该对象添加到本 地缓存 中, 同 时通知 目标节 点( k, id) 的 后继节点自己拥有该缓存副本。 整个查询过程最多只经过一次转发, 查询步长 为O( 2) , 考 虑缓存获取高效性, 根据实 际响应 最大延 时设定 查询时 限, 超 时即认为查询失败。 / / 请求 缓存对 象 / / 请 求缓 存源节 点 消息类型和消息体的定义如下: typedef enum{ CACHE_DATA_REQUEST, CACHE_IP_REQUEST, CACHE_DATA_RESPONSE, / / 响应 缓存对 象 / / 响应 缓存 源节点 CACHE_IP_RESPONSE, CACHE_REQUEST_FAIL, / / 查 询请求 失败 NOTIFY_HAS_URL, NOTIFY_NODE_LEAVE, NOTIFY_URLINDEX_TRANSFER, / / 通 知缓存 目录 转移 } MsgType; typedef struct{ MsgType msg_type; unsigned int src_ip; unsigned int ip; / / 通知拥 有缓 存副本 / / 通知节 点离 开 / / 消息发 起者 的 IP / / 消 息返回 内容 char* data; } MsgData; / / URL 目录 的 hash 值 int url_id; / / 消息 类型 / / 请求 发起者 的 IP 2. 4 节点的加入和离开 在一个动态网络中, 节点可以在任意时刻加入和离开。为 了确保系统在网络中能及时定位查找目标节点, 需要及时更新 相关节点的路由表信息。 节点加入时, 可 以通 过某 种方 式( 如 广播) 获得 一个 相 同 子区域内的某个邻居 n, 然后用 n 的 路由表来初 始化自己的 路 由表, 并向自己的 后 继节 点 请求 管 理自 己负 责 的缓 存目 录 信 

·6083· 计 算 机 应 用 研 究 第 25 卷 息, 同时修改自己的区域 内节点 信息列 表, 并 将自己 上线的 消 息信息采用泛洪的方式通知子区域内的其他所有节点。 节点离开, 正常退出时也只要自己负责的缓存目录信息转 移到环上相邻的下一个活动节点并通知本子区域自己离开; 非 正常退出时, 子区域内的 节点信 息采用 被动发 现的方 式更新。 区域内任意节点执行查询操作发现某后继节点无效后, 更新自 己的节 点 信 息 表, 并 通 知 大 家。 节 点 加 入 和 退 出 需 要 发 送 O( m) 条消息告知所属区域其他节点。 路由表中区域间邻居节点采用动态加入更新的办法, 对于 每个子区域均对应管理一个节点列表, 只要其他子区域有节点 与自己发生连接, 就将该节点按照 RTT 值大小插入 到列表中。 其实每个区域内的所有节点可 以维护 一个相 同的区 域间邻 居 节点, 但是每个节点具有平等性并且 RTT 值不一样, 所以采 用 独自管理的 方式。在 空 闲期, 发 送测 试 消息 维 护列 表最 新 状 态, 将无法响应的节点从列表中删除, 当列表出现空邻居后, 可 以从区域内邻居节点获取。 3 性能评估 3. 1 性能分析 1) 负载均衡 它 是 影响 分布 式 系统 性 能的 重要 因 素, 本 文采用一致性哈希函数保证所 有的缓 存以很 大的概 率均匀 分 布在系统的各个节点上。同时 节点向 其他节 点获取 缓存成 功 之后, 缓存 该 Web 对 象, 即同一 对象在 系统中 有多个 副本, 对 于提高获取速度和解决 Web 访问热点现象均有效。 2) 节点代价 在这个系统 中本地 缓存的 开销可 以设定 为 固定大小, 并定时更新维护。每个节点除了本地缓存以外需要 管理大量信息, 在( N = k ×m) 大小的系统中内存开销可以表示 为 S( k, N) = A ×N/k + B ×( k - 1) + C( 其中: A 为子 区域内 每 个节 点的路 由信息; B 为到 达其他 子区域 的路由 信息; C 为 缓 存目录信息) 。在系统负载均衡条件 下, 缓存 目录信息 C 大 小 近似相等, 每个子区域的 路由信 息对应 一个节 点列表, 可以 取 槡 B = 2A, 那 么 S( k, N) 在 k = N/2时 取 最 小值。 比 如在 N = 100 000的系统中, 划分 k = 223 个子区域, 每个区域有 447 个节 点。假 定每个 节点路 由信息 需要 40 Byte, 每 条缓存 目录信 息 ( 缓存系统中可 能 有多 项 副本) 需 要 500 Byte, 每 个节 点 管 理 100 条 目 录 信 息, 那 么 平 均 每 个 节 点 的 内 存 开 销 S( 223, 100 000) 只有 85. 7 KB。 3) 状态维护 当系 统中 的节 点发生 变化 ( 包括 发布 缓 存 消息、节点加入和离开) , 系统必 须做两 件事, 即更新 节点自 身 信息和通知其他节点发生了变化。 系统发布缓存消息只需要查找到目标节点的后继, 然后存 储目录信息即可。系统路由查 询只需 要 O( 2) 的代价, 而且 相 当部分缓存消息发布均是副本发布, 可以直接利用缓存请求得 到的路由查询结果。 节点加入和离 开的 消息 通知 采用 泛洪 ( flooding) 方 式, 一 个节点变化只需要通知该子区域内的其他节点。关于 Gnutella 和 Napster 的一项研 究 [ 8] 表 明: 在 100 000 个 节 点规 模的 开 放 式网络中, 平均每秒 只有 19 个成员 发生状 态变化。那 么可 以 推论出在一个 105 ～106 个 节点的 网络缓 存系统 中, 只有 20 ～ 200 个节点发生状 态变 化, 平 均每 个子 区域 不到 一次, 而 且 每 个子区域内的节点数目数量级在 103 以下, 由此可知节点 加入 和离开的泛洪消息造成的 背景带 宽负载 很小。节点 离开时 后 继节点接管自己的缓存目录信息, 对其他节点也无影响。 区域节点邻居的更新采 用主动 探测的 方式。当该 子区 域 内有节点与自己相互发生查询请求或其他连接, 就将该节点作 为子区域邻居 候选节 点, 根据 RTT 值 更新 区域 邻居 列 表。 这 样保持区域邻居节点均是 最近活 动且物 理距离 相对近 的。 同 时将相互共享过缓存的节点设为物理邻居, 可以增加节点按兴 趣聚类的可能, 提高查询速度。 4) 其他 为了减 轻 系统 的存 储 压力, 位 于 同一 个页 面 下 的大量不同 Web 对象的目 录信 息只 存储 一次, 因 为在 同一 个 页面下的 Web 对象具有极大相关性, 通 常请求是连 续发生, 所 以只需要将主页面的目录信息存储在目标节点, 节点在响应用 户请求时, 在发送主页面对象的同时, 将 相关的 Web 对象一 起 响应给用户, 也提高了用户的响应速度。 3. 2 仿真实验评估 本文采用 NS2 网络仿真软件对缓 存系统 进行仿 真实验 评 估, 多用户节点运行 在同一 台机器。仿 真对 象来 自 UC Berke- ley home IP Web traces[ 9 ] 位 于 proxy 缓 存服 务器 上 的 trace 记 录, 一共 916 个节点, 95 768 条请求, 时 间为 4 h, 应用 proxy 中 心缓存方式。仿真时每个客户节点对应于一个仿真节点, 所有 节点位于一个网关下面, 节 点之间 的链路 延时是 毫秒级; 网 络 拓扑采用 GT 拓扑 生成 器生成, 节 点之 间采 用 flat 模 式以 0. 2 概率互连。节点分组 如下: 916 个 节点, 分成 23 个子 区域, 每 个子区域 40 个节点。假定每个节点的默认缓存大小为 1 MB, 节点以指数分布概率离开 网络。仿真 实验主 要基于 以下度 量 指标: 命中率、外部带宽、系统响应延时、缓存空间大小。 1) 命中率 包括响应命中率 和字节 命中率。前 者指网 络 中所有节点发出的请求被缓存命中响应的百分比; 后者指缓存 命中的字节数占所有请求 总字节 数的百 分比。本地 分布缓 存 命中字节数可以降低网络 外部带 宽。 影响缓 存命中 率的因 素 包括节点的 缓 存大 小、系 统 的 动态 性 ( 包括 节 点 的 加 入 和 退 出) 。 图 4 是缓存大小变 化对命 中率大 小的影 响。原日 志中 记 录响应命中率为 0. 335, 字节命中率为 0. 258。可以 看出, 随 着 每个节点本地缓存的增加, 命中率得到很大的提高, 超 过 1 MB 以后变化很缓慢, 均已接近 中心缓 存的命 中率大 小, 所以说 在 具有适当缓存空间大小条件下, 本方法可以与中心缓存效果相 当; 同时可以看出字节命中 率比响 应命中 率要小, 这 时因为 缓 存存储一般采用的是小文件优先的原则。 2) 外部带宽 缓 存 可以 降低 网 络的 外部 带 宽, 图 5 比 较 了 DHT 缓存、proxy 中心式缓存和无 缓存三种情 况下网络外 部 带宽的变化情况。可以看出 DHT 分布式缓存和中心式缓存 一 样, 都极大地降低了网络的外部带宽, 降低了系统对外的流量。 3) 响应延时 图 6、7 统计所有命中记录的延时, 包括目标查 询延时和目标获取延时, 可以看出查询目标节点延时集中在100 ～ 150 ms, 获取目标对象延时集中在 150 ～200 ms, 因为目标对象链 路传输的延时稍大。在 O( 2) 步长 DHT 存储的条件下, 缓存命中 的总时间一般小于 500 ms, 具有低延时特点。 ( 下 转第 3812 页 ) 

·2183· 计 算 机 应 用 研 究 第 25 卷 表 1 TCP、IP 拥塞 控制与 本文 中的拥 塞控 制的比 较 比 较 项 TCP 拥 塞 控 制 IP 拥 塞 控 制 本 文 中 的 拥 塞 控 制 实 现 位 置 延 迟 不 同 数 据 流 间 的 公 平 性 端 系 统 较 大 网 络 内 部 无 交 换 机 较 小 难 以 实 现 可 以 实 现 较 好 实 现 长 期 拥 塞 可 以 处 理 无 法 处 理 可 以 处 理 较 好 处 理 理 想 处 理 可 以 处 理 短 期 拥 塞 由图 3 所示的实验结果可以看出, 经过本文所提出的基于 开闭环 PID 型迭代学习控制算法的拥塞控制后, 其网络流量得 到了很好的控制, 发生拥 塞的次 数较以 前有了 明显减 少, 并 提 高了网络资源的利用率和提供给信源公平的资源分配份额, 说 明本文所提出的网络拥塞控制有很好的效果。 4 结束语 迭代学习控制由于其结构 简单和 对系统 精确模 型的不 依 赖性使其在控制系统中得 到了广 泛的应 用。但开环 迭代学 习 控制只利用了系 统前 次 运行 的信 息, 而 忽略 了 系统 当前 的 信 息, 使得系统对被控制对 象无镇 定作用, 闭环 迭代学 习控制 往 往又需要高增益反馈从而 影响 了系 统迭 代收 敛速度。本文 提 出了一种同时利用 开闭 环 PID 型 迭 代学 习 控制 律, 并证 明 了 其收敛性。将这一方法应用于网络拥塞控制中, 其主要目标是 ( 上 接第 3806 页 ) 控制进入网络的数据流量, 保证通信网络不会被用户发送的数 据流阻塞, 并合理地使用瓶 颈资源, 克 服了传 统控制 方法的 许 多局限, 取得了较好的效果。 参考文献: [ 1] U Jian-xin, TAN Ying. Linear and nonlinear iterative learning con- trol[ C] / / Proc of Lecture Notes in Control and Information Sciences. [ S. l. ] : Springer-Verlag, 2003 . [ 2] XU Jian-xin, TAN Ying. On the convergence speed of a class of hig- her order ILC schemes[ C] / / Proc of the 40th IEEE Conference on Decision and Control Orlando. Florida: [ s. n. ] , 2001: 4932-4937. [ 4] [ 3] CHEN W, SAIF M. Avariable structure controller for a class of uncer- tain systems with unknown uncertainty bounding function[ C] / / Proc of American Control Conference. 2006. ZHENG K, LEE A H, BENTSMAN J, et al. Steady-state bumpless transfer under controller uncertainty using the state / output feedback topology[ J] . IEEE Trans on Control Systems Tech nology, 2006, 14 ( 1) : 3-17. [ 5] MACRI P A, PIONTTI A L P, BRAUNSTEIN L A. Reducing con- gestion on complex networks by dynamic relaxation processes [ J] . Physical A : Statistical Me chanics and its Ap plicatio ns, 2007, 386 ( 2) : 776 -779. [ 6 ] CEHN Hua-liang, LIU Zhong-xin, CHEN Zeng-qiang, et al. Exten- ding TCP congestion control to multicast[ J] . Comp uter Networks, 2007, 51 ( 11 ) : 3090-3109. [ 7] JIN C, WEI D, LOW S H, et al. FAST TCP: from theory to experi- ments [ J] . IEEE Network, 2005, 19 ( 1) : 4-11. [ 8] TAN Lian-sheng, YUAN Cao, ZUKERMAN M. FAST TCP: fairness IE EE Com municatio ns Let ters, 2005, 9 and queuing issues [ J] . ( 8) : 762-764 . [ 9] CASETTI C, GERLA M, MASCOLO S, et al. TCP westwood: end- to-end congestion control for wired / wireless networks[ J] . W ireless Networks. 2002, 8 ( 5 ) : 467-479. [ 10 ] GRIECO L A, MASCOLO S. End-to-end bandwidth estimation for congestion control in packet networks[ C] / / Proc of Lecture Notes in Computer Science on Quality of Service in Multiservice IP Networks. London: Springer-Verlag, 2003. 实验可以看出, 此分 布式 Web 缓 存在 命中 率、内 存空 间 成本、 系统响应 延 时等 方 面 均 有 令 人 满 意 的 性 能。它 相 对 于 传 统 proxy 中 心缓存, 充分利用了 单个节点带 宽和资源, 提高了 http 请求的响应速度, 节约网络 带宽, 适用于 构建 一个 高效 大规 模 的缓存系统。 参考文献: [ 1] TOICA L, MORRIS R, KARGER D, et al. Chord: a scalable peer- to-peer lookup protocol IEEE / ACM Trans on Networking , 2003, 1 1( 1 ) : 17- 32. for internet application [ J] . 4) 缓存大小 为了控制缓存的规模和实际应用的需 要, 设 定每个节点上的最大 缓存 为 10 MB。图 8 揭示 了缓 存大 小随 时间的变化趋势, 可以看出节点上的平均缓存大小随 时间增长 而变大, 在 4 h 以内 平均 缓存大 小大 约在 500 KB 以 下。 可以 看出, 本方法对缓存空 间要求 相对比 较小, 易于 在内 存受 限的 设备上使用。 4 结束语 本文设计了适用于 Web 缓存应用的查询路由步长为O( 2) 的路由方法, 并提出一种查询步长短、节点负载小、缓 存内容及 目录信息分布存储的基于 DHT 的 Web 缓存共享方法。从仿真 [ 2] GUPTA I, BIRMAN K, LINGA P. Kelips: building an efficient and stable P2P DHT through increase memory and background overhead [ C] / / Proc of the 2nd International Workshop on Peer-to-Peer Sys- tems. 2003: 160- 169 . [ 3] GUPTA A, LISKOV B, RODRIGUES R. One hop lookups for peer- to-peer overlays [ C] / / Proc of the 9th Workshop on Hot Topics in Operating Systems. Berkeley: USENIV Association, 2003. [ 4] 凌波 , 王 晓宇 , 周 傲英, 等 . 一 种基 于 peer-to-peer 技 术 的 Web 缓 存 共 享系统 的研究 [ J] . 计算机 学报 , 2005, 28 ( 2) : 170 - 178. [ 5] LYER S, ROWSTRON A, DRUSCHEL P. Squirrel: a decentralized peer-to-peer Web cache [ C] / / Proc of the 21 st ACM Symposium on Principles of Distributed Computing. 2002: 213- 222 . [ 6] LINGA P, GUPTA I, BIRMAN K. Kache: peer-to-peer Web caching using Kelips [ J] . A CM Trans on Information S ystem, 2004, 5 ( 9) : 1 -29. [ 7] 石 磊, 卫琳, 古志 明, 等. Web 对 象 可 缓 存性 研 究 及 加速 方 案 [ J] . [ 8] 计 算机工 程, 2005 , 31 ( 18 ) : 74- 77. SAROIU S, GUMMADI P K, GRIBBLE S D. A measurement study of peer-to-peer file sharing systems[ C] / / Proc of Multimedia Computing and Networking 2002( MMCN’02) . 2002: 156- 170 . [ 9] UC Berkeley home IP Web traces homepage [ EB/ OL] . http: / / ita. ee. lbl. gov / html/ contrib / UCB. home-IP-HTTP. html.