Gnutella网络的路由搜索算法研究

摘要

随着网络计算机系统的飞速发展，信息量越来越庞大，用户对海量信息存储和数据交换、查询、检索等技术和方式的选择越来越重要。为了满足人们对各种类型敏感信息的需求，P2P(Peer-to-Peer)技术应运而生。P2P在对等计算、协同工作、搜索引擎、文件交换等领域有很好的应用前景。在目前的P2P应用模型中，非结构化p2p系统得到了非常广泛的应用。Gnutella是非结构化P2P的网络通信协议，基于Gnutella通信协议的网络叫做Gnutella网络。近年来Cnutella网络发展的非常迅速。但是由于Gnutella网络的资源查询机制采用洪泛策略，从而导致了查询速度慢与查询效果不佳等缺点，限制了P2P网络的进一步发展。如何管理网络连接、实施高效的搜索算法、减少冗余消息、增加搜索的查准率、解决Gnutella网络的可扩展性对该网络的进一步发展至关重要。 Gnutella协议洪泛机制的最大问题是导致冗余消息的产生。节点将查询消息向其所有邻居节点转发，从而造成搜索消息被迅速复制，网络负载过重，查准率和查找效率不高。在以往改进的算法中，虽然在一定程度上减少了查询消息的转发量，但是在资源查准率和查找消息可达性方面仍有不足。本文在总结以往改进算法的基础上，对其不足进行改进，引入了一种基于索引机制的资源搜索改进算法。 本文首先介绍了P2P的产生背景、主要应用领域及其目前的发展状况，重点分析了非结构化P2P代表协议Gnutella的搜索策略及其改进算法RWRI(R~domWalk with RoWing Index)，并分析RWRI算法存在的不足。其次针对RWRI算法的不足提出了如下改进：通过在路由索引表中增加记录查询信息和当前节点到达资源目标节点的最小跳数信息来指导查询，从而弥补了原算法在指引查询时不能保证查询消息可达性的缺点；引入返回路径表与路由索引表互相呼应，采用缓存查询返回消息的策略来提高重复查询的效率。最后在NS2+Cygwin平台下对本文提出的改进算法进行了验证，将改进算法和改进前算法进行了比较。实验结果表明：改进后的算法在一定程度上提高了资源搜索的查准率，减少了资源搜索的盲目性。

目录

文摘

英文文摘

声明

1绪论

1.1论文的研究背景及意义

1.2国内外研究现状

1.3论文的研究内容

1.4论文的组织结构

2 P2P网络概述

2.1 P2p的产生

2.2 P2P的概念形成

2.3 P2P与传统的C/S模型的对比

2.4 P2P的发展现状

2.4.1代表性产品和技术

2.4.2 P2P的困境

2.5 P2P当前的主要应用

2.6 P2P的未来

2.7 P2P亟待解决的问题

2.8小结

3 Gnutella网络概述

3.1 Gnutella网络协议

3.2 Gnutella的数据包格式

3.2.1 ping数据包格式

3.2.2 pong数据包格式

3.2.3 Push请求数据包格式

3.2.4搜索数据包格式

3.2.5搜索结果数据包格式

3.3 Gnutella网络的消息机制和路由策略

3.4 Gnutella网络文件下载机制

3.5 Gnutella网络的特性

3.6 Gnutella网络中的搜索机制及其对比

3.7小结

4基于索引机制的Gnutella路由算法及其改进

4.1相关概念和定义

4.2 RWRI算法及不足

4.3算法改进思路及内容

4.4改进后算法索引表的建立和维护

4.5改进后算法描述

4.6小结

5实验仿真及结果分析

5.1实验环境简介

5.1.1网络模拟器NS2简析

5.1.2 Cygwin简析

5.2实验环境搭建

5.2.1安装设置cygwin

5.2.2安装设置NS2

5.2.3安装设置GnutellaSim

5.3核心类及数据结构定义

5.4网络拓扑结构的建立

5.5算法模拟过程

5.6实验数据及比较

5.7小结

6结论及展望

6.1论文总结

6.2下一步的工作

致 谢

参考文献

附 录