对等网络内容搜索及索引缓存研究

论文摘要

近年来,对等网络日益成为Internet一个重要应用。对等网络将Internet边缘节点的资源收集起来,提供强大的计算与存储能力。无结构对等网络由于查询的灵活性和对动态环境的适应性,得到大力部署,成为对等网络的主流。但无结构对等网络存在网络性能低下等困难,这使搜索算法一直是无结构对等网络的研究重点。本论文研究无结构对等网络的内容搜索算法和分布式索引缓存算法,主要研究内容和创新成果如下:1)提出了一个基于查询代理的自适应无结构对等网络盲搜索算法（QAA, Query AgentAlgorithm）。盲搜索算法的主要目标是控制查询规模,降低冗余开销,但现有算法缺少对网络状况的感知能力,难以自适应地根据查询及网络情况调整查询规模。QAA通过查询代理不断发出子查询来完成查询工作,其核心思想是通过子查询探测网络状况,再利用这些信息指导后续子查询规模,从而有效降低冗余开销,其规则是:离查询成功越近,查询规模越小。利用这种探测过程,QAA避免了现有算法的参数优化难题。本论文将QAA与现有盲搜索算法进行了对比实验,结果表明,对uni-uni模式及Zipf-sqrt模式,QAA即使在高查询满足率条件下,也实现了有效冗余开销控制,其结果冗余率分别为1.1和1.4,是几个实验算法中最低的,并且两个模式下的结果冗余率提高也是最低的,这说明QAA有更好的网络适应性。2)提出了一个基于缓存生命期（TTL）的分布式索引缓存模型。分布式索引缓存方法的基本思想是以较低代价扩大网络中信息数量,以此提高网络搜索性能,因此索引缓存密度在影响对等网络的搜索性能上占据核心地位,但目前对此的研究工作还很少见报道。本论文分析了查询到达对缓存索引扩散的驱动作用以及缓存生命期超时对缓存索引的消灭作用,发现网络索引缓存密度在这两个因素影响下可以维持一定的稳定状态,这意味着,可以通过一些简单的参数来模型网络搜索性能。基于上述发现本论文研究了两个具代表性的基本节点发现算法——Gnutella算法与随机漫游算法,其分别具有最短和最长的缓存路径。我们研究了这两个算法的索引缓存密度如何受查询到达速率以及缓存生命期时长的影响,发现在Gnutella算法下,查询到达速率及缓存生命期时长对缓存密度表现出明显的线性关系,而在随机漫游算法下,表现出幂指数关系。

论文目录

• 第一章 引言
• 1.1 无结构对等网络及其搜索算法
• 1.2 已有盲搜索算法的不足
• 1.3 目前索引缓存研究的不足
• 1.4 本文研究的主要内容和创新工作
• 1.5 本文组织结构
• 第二章 对等网络及相关技术介绍
• 2.1 对等网络介绍
• 2.1.1 对等网络发展的背景
• 2.1.2 对等网络定义及协议栈
• 2.1.3 对等网络分类
• 2.1.4 对等网络应用
• 2.2 无结构对等网络基本算法
• 2.2.1 洪泛类搜索算法
• 2.2.2 漫游类搜索算法
• 2.3 分布式索引缓存技术
• 2.3.1 UIC 方法
• 2.3.2 UIC 方法改进
• 2.3.3 DiCAS 方法
• 2.4 应用层网络仿真工具
• 2.5 本章小结
• 第三章 自适应查询代理算法
• 3.1 前言
• 3.2 相关研究
• 3.2.1 紧结构对等网络搜索算法
• 3.2.2 无结构对等网络搜索算法
• 3.3 盲搜索算法冗余开销分析
• 3.4 查询代理算法
• 3.4.1 查询代理
• 3.4.2 子查询
• 3.5 实验场景
• 3.5.1 网络场景
• 3.5.2 查询及复制分布模式
• 3.5.3 算法参数
• 3.6 实验结果及分析
• 3.6.1 对比实验结果
• 3.6.2 邻居节点度的影响
• 3.7 查询代理算法的局限
• 3.8 查询代理算法实现说明
• 3.8.1 系统框架
• 3.8.2 消息格式
• 3.8.3 节点信息管理
• 3.8.4 算法主要流程图
• 3.9 本章小结
• 第四章 分布式索引缓存模型研究
• 4.1 前言
• 4.2 相关研究
• 4.2.1 主动信息交换
• 4.2.2 分布式索引缓存
• 4.2.3 内容复制研究
• 4.2.4 基于TTL 机制的Web 缓存及DNS 缓存模型研究
• 4.3 目前分布式索引缓存研究的不足
• 4.4 分布式索引缓存模型
• 4.5 实验方法描述
• 4.5.1 节点发现算法
• 4.5.2 对等网络环境
• 4.5.3 内容复制及缓存参数
• 4.5.4 查询到达模型
• 4.6 实验结果及分析1:索引缓存密度
• 4.6.1 Gnutella 算法
• 4.6.2 随机漫游算法
• 4.6.3 讨论
• 4.7 实验结果及分析2:搜索性能分析
• 4.7.1 Gnutella 算法
• 4.7.2 随机漫游算法
• 4.7.3 讨论
• 4.8 与基于TTL 的Web-Cache 及DNS-Cache 的比较
• 4.9 本章小结
• 第五章 分布式索引缓存方法的问题及改善
• 5.1 前言
• 5.2 相关研究
• 5.2.1 对等网络索引缓存
• 5.2.2 Web 缓存及DNS 缓存有效性研究
• 5.2.3 对等网络索引缓存
• 5.3 基本索引缓存算法
• 5.4 缓存索引失效及解决办法
• 5.4.1 网络动态性
• 5.4.2 索引失效问题
• 5.4.3 有效性检测方法
• 5.4.4 实验
• 5.5 负载均衡问题及解决办法
• 5.5.1 索引缓存引起的负载均衡问题
• 5.5.2 内容共享关联机制
• 5.5.3 实验
• 5.6 局限与讨论
• 5.7 本章小结
• 第六章 论文总结和进一步工作
• 6.1 论文工作总结
• 6.2 进一步工作
• 参考文献
• 致谢
• 作者简历