基于P2P的MMOG中负载均衡算法的研究

摘要

基于DHT的P2P网络中,虽然已经提出了很多算法解决负载均衡问题,但这些算法或者忽略了网络中节点的异构性、扰动性,或者在节点间转移负载的时候没有考虑其临近关系,从而影响负载均衡代价和速度,或者采用集中式的基于协调者的动态负载均衡算法,但此算法可能存在单点失效的问题,没有实现完全的分布式。而大型多人在线网络游戏(massively multiplayec onlinegames,MMOG)系统对上述问题要求比较高,故针对上述缺点本文要完成以下工作:
　　 1)针对目前负载均衡算法没有考虑节点临近关系,从而影响负载均衡代价和速度,所以本文设计了一种考虑节点临近关系的负载均衡算法,该算法采用基于虚拟服务器策略,同时改进Transfer策略的一对一模式为多对多模式。当某个节点重载的时候,按贪婪算法找到距离最近的合适的轻载节点分担它的负载,使得节点间负载的转移消耗减少。
　　 2)具体实现了一种考虑了节点临近关系的负载均衡算法,通过建立全分布式K叉树,调用LIB模块沿着K叉树从叶子节点到根节点收集系统信息,调用NTS模块找出重载节点,调用VSA模块产生负载转移调配信息,最后调用VST模块依据VSA信息实现负载的转移。
　　 3)针对本文提出的负载均衡算法设计了一种仿真算法方案,该方案中结构化的覆盖网络是由Peersim产生的,实现了继承于Peersim的node接口的KTnode类,通过KTnode类实现了考虑了节点临近关系的负载均衡算法,同时编写仿真配置文件、统计分析类和协议类实现仿真方案。
　　 仿真实验中,本文改进的负载均衡算法与未考虑临近关系的Proportion算法分别在设定拓扑1和拓扑2下运行,并分析对比了两种算法的仿真结果。实验表明,本文提出的算法在很大程度上减少了负载均衡代价并能够加快负载均衡速度。

目录

文摘

英文文摘

第1章 绪论

1.1 课题研究背景及意义

1.2 国内外研究现状

1.3 本文的主要研究工作

1.4 论文结构

1.5 本章小结

第2章 对等网络概述及常见负载均衡算法

2.1 对等网络的定义

2.2 对等网络的特点和分类

2.2.1 对等网络的特点

2.2.2 对等网络的分类

2.3 对等网络的关键技术

2.4 结构化对等网络

2.5 负载均衡技术简介

2.5.1 负载均衡技术

2.5.2 负载均衡的作用

2.5.3 负载均衡的分类

2.6 结构化对等网络中负载均衡问题

2.7 结构化对等网络中常用的负载均衡技术

2.7.1 基于复制技术策略

2.7.2 基于流言传播策略

2.7.3 基于虚拟节点策略

2.7.4 三种策略优缺点比较

2.8 基于DHT的结构化对等网络负载均衡技术简介

2.9 基于DHT的结构化对等网络负载均衡算法

2.9.1 基于Proportion的算法

2.9.2 基于Transfer的算法

2.10 基于DHT的对等网络负载均衡算法存在的问题

2.11 本章小结

第3章 考虑临近关系的负载均衡算法的设计与实现

3.1 算法的设计目标

3.2 算法的设计结构

3.3 算法的设计与实现

3.3.1 K叉树创建模块

3.3.2 负载均衡信息收集模块

3.3.3 节点类型判断模块

3.3.4 节点临近关系产生模块

3.3.5 虚拟服务器调配信息模块

3.3.6 虚拟服务器负载转移模块

3.4 各成员模块之间的关系

3.5 考虑临近关系的负载均衡算法的优点

3.6 本章小结

第4章 负载均衡算法仿真的实现与结果分析

4.1 P2P仿真工具

4.1.1 P2P仿真工具分类

4.1.2 Peersim仿真工具概述

4.2 负载均衡算法仿真的实现

4.2.1 配置文件

4.2.2 节点类的实现

4.2.3 统计分析类的实现

4.2.4 协议类的实现

4.3 模拟实验

4.3.1 实验环境

4.3.2 Peersim仿真环境的配置

4.3.3 Peersim模拟仿真实验

4.4 仿真结果分析

4.4.1 算法改进前与改进后对比分析

4.5 小结

第5章 总结与展望

参考文献

致谢