基于负载均衡的超立方体网络容错路由算法研究

摘要

超立方体网络是迄今为止最为重要和最具吸引力的网络拓扑结构之一.本文通过对当前网络中的拥塞控制、流量控制和负载均衡等问题的深入研究,提出和设计了基于负载均衡的超立方体网络中的单播容错路由算法.本文研究了超立方体网络中容错路由算法的有效性及其保障机制.现有的超立方体网络中的容错模型和容错路由算法存在着安全性和有效性方面的欠缺,因而不能避免网络路由中出现的死锁、冲突、消息拥塞等现象的发生.而以前对负载均衡等技术的研究很少针对超立方体网络.本文在全面了解了当前网络上的流量控制、拥塞控制和负载均衡等技术的基础上,重点挖掘出这些技术在超立方体网络及其容错路由算法上的适用性.本文在引入了负载均衡机制的基础上,对原有的基于局部连通性容错模型的超立方体网络上的单播容错路由算法进行了改进.改进后的算法既是简单的同时又是高效的.首先,不管所给定的超立方体网络是否满足要求的条件,算法都能适用:在满足要求的条件时,算法将成功地构造一条满足负载均衡的路由路径;在不满足要求的条件时,如果算法不能成功地构造一条路径,则算法将正确地报告出给定的超立方体网络不满足要求的条件.其次,这些算法是分布式的和基于局部信息的:网络中的每一个结点只需要知道其邻结点的状态而不要求知道网络的全局信息.更重要的是,路由算法的有效性得到了进一步的提高.模拟实验结果表明,改造后的算法不仅成功地达到了负载均衡的目的,所成功发现路由路径的概率得到了提高.

目录

文摘

英文文摘

原创性声明及关于学位论文使用授权说明

第一章 绪论

1.1超立方体网络结构及其表示

1.2课题的研究意义

1.3国内外研究现状与分析

1.4课题的主要研究内容

1.5论文的结构

第二章 负载均衡技术剖析

2.1概述

2.2拥塞控制技术

2.2.1基本概念

2.2.2拥塞控制机制

2.2.3拥塞控制算法的概况

2.3流量控制技术

2.3.1流量控制的基本概念

2.3.2流量控制的作用

2.3.3流量控制、拥塞控制和过载处理的关联

2.4负载均衡技术

2.4.1负载均衡的实现方法及分类

2.4.2基本的网络负载均衡策略和算法

2.4.3负载均衡实施要素

2.5负载均衡技术在超立方体网络中的适用性研究

2.5.1网络拓扑结构与基本通信方式

2.5.2任务粒度划分

2.5.3静态调度与负载平衡

2.5.4结合负载均衡等技术对超立方体网络路由的思考

2.6本章小结

第三章基于负载均衡的超立方体网络容错路由算法

3.1概述

3.2局部连通性网络容错模型及其容错路由算法

3.2.1局部连通性的概念

3.2.2局部连通的超立方体网络容错路由算法

3.3改进的局部连通的超立方体网络容错路由算法

3.3.1局部k维子立方体连通的容错路由算法的改进

3.3.2局部子立方体连通的容错路由算法的改进

3.4算法实例

3.5本章小节

第四章 模拟实验及分析

4.1概述

4.2实验采用的数据结构

4.3模拟实验及结果分析

4.3.1实验参数及说明

4.3.2实验结果

4.3.3结果分析

4.3.4进一步的实验

4.4关于伪随机数的研究与思考

4.4.1随机函数对实验的影响

4.4.2伪随机数

4.4.3对实现超立方体网络非均匀结点错误概率分布的思考

4.5本章小结

第五章 结束语

5.1工作总结

5.2研究展望

参考文献

致 谢

攻读硕士学位期间参加科研及论文完成情况