一种负载敏感的区域自治P2P覆盖网

摘要

近年来，计算机计算能力的提高和网络带宽的增加带来了计算模式的变化。在这种背景之下，结构化对等网络在十数年间得到了迅猛的发展，并在应用上得到了长足的进步。但是，在这个过程中也暴露出了结构化对等网络在理论上的一些固有问题：路由效率问题和负载均衡问题。
　　 本文对结构化对等网络的架构和算法进行了分析与研究，在此基础之上，以它们的代表网络之一Chord为对象，引入了区域自治和负载敏感的概念，深入地探讨了针对路由效率和负载均衡的改进措施与策略。本文的主要工作包括了以下部分：
　　 (1)提出了一种对等网络节点间距离探测与感知技术。由于Chord缺乏路由邻近信息，为了引入区域自治的概念，有必要对网络节点间距离进行探测与感知，本文将Vivaldi框架与Meridian覆盖网相结合，并根据Chord网络路由表的特点，设计了一种适用于对等网络的机制，有效地解决了路由邻近信息缺失的问题。
　　 (2)提出了以Treap树为基本架构的负载敏感的覆盖网。本文基于Treap树设计了一个用于负载均衡问题的负载信息传递机制，节点按照自身的索引大小被编排在一个Treap树上，同时，以负载率为旋转优先级让该区域内的Treap树维护它的最小堆性质。这种覆盖网允许负载信息以O(logN)的效率进行传播与散发的同时，还解决了其他树形覆盖网所存在的单点失效与维护代价昂贵的问题。
　　 (3)以Chord网络为基础实现了上述技术和架构。节点在加入Chord后，根据距离探测与感知的结果决定加入一个区域性的Treap覆盖网。两种协议的结合具有了以下优点：Treap树中存在随机路由带来的最大路由跳数偏大的问题，可以由TTL加Chord路由的方式得到解决；Chord中缺少邻近路由信息的问题，区域性Treap网络正是为此而设计。本文还设计了一个基于层次化路由表的副本选择机制，以解决负载均衡时的数据对象转移与热点响应问题。
　　 本文所设计实现的覆盖网，结合结构化对等网络中代表之一Chord，引入了负载敏感与区域自治的概念，为解决结构化对等网络中的路由效率问题和负载均衡问题提出了一种新的思路。仿真结果表明，本文所提出的框架与技术是可行的，值得进一步的研究与优化。

目录

文摘

英文文摘

第一章 绪论

1.1 研究背景

1.2 研究现状

1.3 主要研究内容

1.4 本文组织结构

第二章 结构化P2P网络概述

2.1 结构化P2P网络拓扑与算法

2.1.1 结构化P2P网络结构

2.1.2 结构化P2P网络的节点加入与离开

2.1.3 结构化P2P网络路由

2.2 Chord

2.2.1 节点的加入与数据对象的分配

2.2.2 节点的退出

2.2.3 Chord网络的自组织

2.2.4 查询操作

2.3 结构化P2P网络的应用

2.3.1 PAST系统

2.3.2 eDonkey中的Kad网络

2.4 结构化P2P网络中存在的问题

2.3.1 路由效率问题

2.3.2 负载均衡问题

2.5 本章小结

第三章 区域自治技术研究

3.1 网络距离预测技术

3.1.1 基于网络拓扑结构的距离预测技术

3.1.2 基于虚拟坐标的距离预测技术

3.1.3 虚拟坐标空间插入的距离预测技术

3.2 网络邻近度感知技术

3.2.1 Netvigator

3.2.2 Meridian

3.3 本章小结

第四章 负载敏感的结构化P2P覆盖网

4.1 覆盖网结构

4.1.1 负载率

4.1.2 Treap树

4.2 覆盖网协议

4.2.1 Treap协议

4.2.2 区域自治与网络距离感知

4.2.3 Treap-Chord协议

4.3 负载均衡策略

4.3.1 负载消息传递机制

4.3.2 副本选择机制

4.4 本章小结

第五章 实验与结果分析

5.1 仿真环境

5.1.1 PeerSim的框架

5.1.2 Peersim的运行

5.2 实验设计

5.2.1 配置文件

5.2.2 Treap-Chord协议所实现的接口

5.3 结果分析

5.3.1 路由跳数比较

5.3.2 网络维护代价

5.3.3 负载均衡策略的有效性

5.4 本章小结

第六章 总结与展望

6.1 本文的主要工作

6.2 未来工作的展望

参考文献

致谢

在读期间发表的学术论文和参与项目