互连网络负载平衡理论与算法 PDF下载

编辑推荐

暂无

内容简介

　　本书主要通过研究若干互连网络的拓扑模型并在研究这些模型特征的基础上提出了一些比已知算法具有更高执行效率的负载平衡算法，并对这些算法的性能给出了理论分析。全书主要内容包括并行计算互连网络和对等覆盖网络计算的负载平衡理论、模型和算法，也简　　要介绍了Web服务器集群和云计算中的负载平衡的基本知识。

　　本书可供计算机科学和应用数学领域的博士研究生和硕士研究生作为教学参考书，也可供信息技术相关领域的研究人员参考。

作者简介

暂无

互连网络负载平衡理论与算法 PDF下载

前言
第一章 互连网络负载平衡技术介绍
 ； ； ； 1.1 负载平衡技术介绍
 ； ； ； ； ； ； ； 1.硬件负载平衡和软件负载平衡
 ； ； ； ； ； ； ； 2.本地负载平衡和全局负载平衡
 ； ； ； ； ； ； ； 3.计算负载平衡和服务负载平衡
 ； ； ； 1.2 互连网络介绍
 ； ； ； ； ； ； ； 1.互连网络概念
 ； ； ； ； ； ； ； 2.互连网络的功能和特征
 ； ； ； 1.3 互连网络的负载平衡算法的并行编程实现
 ； ； ； ； ； ； ； 1.并行程序的设计过程
 ； ； ； ； ； ； ； 2.并行编程语言环境
 ； ； ； ； ； ； ； 3. MPI程序设计过程
 ； ； ； ； ； ； ； 4.互连网络选择
 ； ； ； ； ； ； ； 5.负载平衡任务的MPI实现
 ； ； ； 1.4 并行计算机系统互连网络的负载平衡
 ； ； ； 1.5 静态负载平衡
 ； ； ； ； ； ； ； 1.负载平衡分类
 ； ； ； ； ； ； ； 2.静态负载平衡介绍
 ；   1.6 动态负载平衡
        1.动态负载平衡介绍
        2.动态负载平衡算法
    1.7 最近邻居负载平衡方案
    1.8 相关研究综述
    1.9 局部迭代负载平衡方案介绍
        1.基本定义和理论背景
        2.同构网络的局部迭代方案
        3.异构网络的局部迭代方案
    1.10 小结
    参考文献
第二章 一般异构网络的扩散负载平衡方案
    2.1 异构网络负载平衡问题描述
    2.2 基本理论结果
    2.3 异构网络的扩散负载平衡方案
    2.4 流的质量分析
    2.5 实验结果
    2.6 小结
    参考文献
第三章 同构OTIS网络的混合负载平衡方案
    3.1 基本定义
    3.2 OTIS网络的混合扩散负载平衡方案
    3.3 混合扩散方案收敛性分析
    3.4 混合扩散方案负载流分析
    3.5 模拟实验
        1.收敛速度分析
        2.流的质量
        3.稳定性分析
    3.6 小结
    参考文献
第四章 异构OTIS网络的混合负载平衡方案
    4.1 异构OTIS网络的混合扩散负载平衡方案
    4.2 算法分析
    4.3 实验
        1.流分析
        2.收敛速度和稳定性
    4.4 小结
    参考文献
第五章 Biswapped网络上的最优负载平衡算法
    5.1 导语
    5.2 BSN网络的定义
    5.3 Biswapped网络上的最优负载平衡算法
    5.4 算法分析
    5.5 实验结果
        1.参数验证
        2. GPM的执行效率和稳定性分析
    5.6 小结
    参考文献
第六章 若干多级互连网络的统一Cayley构建及负载平衡方案
    6.1 定义和背景
        1.介绍
        2.基本定义
    6.2 若干多级网络的统一Cayley构建
    6.3 Cayley图CSC(p,q,r,k)的谱特征
    6.4 多级网络的负载平衡方案
    6.5 实验
    6.6 小结
    参考文献
第七章 聚类连通多阶互连网络的负载平衡算法
    7.1 介绍
    7.2 CCMN网络的定义
    7.3 CCMN网络的负载平衡策略
    7.4 基于H*K谱分析的CED算法复杂度分析
    7.5 实验
    7.6 结论
    参考文献
第八章 互连网络负载平衡方案运用-POVC工程
    8.1 POVC工程介绍
    8.2 POVC系统结构
        1.系统基本参数设置
        2.任务分配
    8.3 负载平衡策略
    8.4 实验结果分析
    8.5 结论
    参考文献
第九章 WEB计算和云计算中的负载平衡技术
    9.1 WEB服务器集群负载平衡技术
        1.概述
        2.Web服务器集群负载平衡技术
    9.2 云计算中基于MapReduce的负载平衡技术
    参考文献
第十章 P2P覆盖网络的负载平衡算法
    10.1 P2P系统负载平衡技术介绍
        1.负载不平衡的原因
        2.负载平衡技术的启动
        3.虚拟服务器的概念
        4.负载平衡实现
    10.2 P2P负载平衡实例:GCNET对等覆盖网络的负载平衡
        1. 引言
        2. GCNET的定义和负载平衡算法
    参考文献
附录:主要符号表

免费在线读

　　第一章互连网络负载平衡技术介绍
   由于网络技术的发展和网络应用的普遍化，许多新的基于网络的计算模式在并行和分布式计算的基础上得以发展起来，如网格计算、云计算、P2P计算等等.对于这些新的计算模式，它们之间各有差别，但是这些新技术的共同特点是计算节点之间都通过网络进行通信.也就是说，这些节点之间或者通过物理互连的硬件，或者通过运行在计算机上的软件之间逻辑的互连，形成互连网络.对各个计算节点产生的工作负载进行平衡是提高计算系统性能的关键策略之一.本书中，将计算系统参加计算的节点形成的通信拓扑叫做互连网络(并不考虑通信软件和协议)，将互连网络的计算节点用一个有限符号集V表示，称为顶点集；将计算节点之间逻辑的或者物理的连接关系用一个V中符号组成的关系二元组E表示，称为边集；互连网络由(V,E)所构建的模型，称为图G.本章首先介绍互连网络的若干概念；其次，介绍在互连网络上求解负载平衡问题的一般方法.
    1.1 负载平衡技术介绍
   负载平衡技术可分为软/硬件负载平衡、本地/全局负载平衡等.软/硬件负载平衡为软件负载平衡解决方案，是指在一台或多台服务器相应的操作系统上，安装一个或多个软件来实现负载平衡，如DNS负载平衡等.它的优点是基于特定环境、配置简单、使用灵活、成本低廉，可以满足一般的负载平衡需求；硬件负载平衡解决方案，是直接在服务器和外部网络间安装负载平衡设备，这种设备我们通常称之为负载平衡器.因为是专门的设备完成专门的任务，独立于操作系统，所以整体性能得到大量提高，加上多样化的负载平衡策略、智能化的流量管理，可达到最佳的负载平衡效果.一般而言，硬件负载平衡在功能、性能上优于软件方式，不过代价较高.
    1. 硬件负载平衡和软件负载平衡
   负载平衡可以由软件或者硬件两种方式来实现.通常的硬件实现负载平衡是通过F5等专用硬件设备来实现负载的分配，这种直接通过智能交换机实现，处理能力较强，而且与系统无关，这是其最明显的优势，目前著名的负载均衡器品牌包括ARRAY，FOUNDRY，网泰VTINFO等.
   硬件解决方案的最大优点是实现的负载均衡效果显著，能缩小规模数据的计算时间，提高运算的精确度；不足是成本昂贵，代价较高，上述各类产品价格在几万到几十万之间；而且主要应用于节点较多，访问量较大，应用简单的场合.
   软件实现则是指借助普通计算机设备，安装合适的软件平台来实现网络中负载平衡划分，一般说来，这种方式在网络拓扑中每个节点都需要安装配套的软件.相对于硬件负载平衡来说，软件实现的方法实现灵活，容易扩展，成本较低.
   2.本地负载平衡和全局负载平衡负载平衡从应用的地理结构上分为本地负载平衡和全局负载平衡.本地负载平衡指对本地的服务器机群做负载平衡；全局负载平衡指在不同地理位置、在不同网络结构的服务器机群间做负载平衡.本地负载平衡可以克服数据流量过大、网络负载过重的困惑，并且无需花费昂贵成本来购买性能卓越的服务器，可充分利用现有设备，避免服务器单点故障造成数据流量的损失.有灵活多样的平衡策略，可把数据流量合理地分配给机群内的服务器来共同承担.即便是给现有服务器扩充升级，也仅简单地增加一个新的服务器到服务器机群中，而不需改变现有拓扑结构、停止目前已有的服务.
    3.计算负载平衡和服务负载平衡
   负载有两种类型，一种是需要提供的服务请求太多，一种是运算的数据量比较大，称作计算负载平衡.前者例如网络Web服务器的负载平衡称作服务负载平衡.后者如并行计算中的负载平衡，本书着重讨论计算负载平衡.在最后的章节，也简要讨论服务负载平衡.
    1.2 互连网络介绍
    1.互连网络概念
   互连网络是构成并行计算系统和决定系统通信性能的关键部件.其主要功能是实现系统中大量节点机之间的消息通信.因而其通信带宽和延迟将直接影响并行系统计算能力的发挥.互连网络的性能相对节点机的速度和应用程序的通信粒度是高带宽和低延迟的，以充分发挥并行系统的效率.
   用交叉开关或多级互连网络连接多个计算机构成大规模并行处理系统，用互连网络互连多个服务器构成集群系统等.由于互联网络其节点间的带宽很难超过500MB/s，不能满足那些小粒度、大通信量的并行应用程序对通信带宽的要求，导致并行系统效率不高.互连网络成了限并行系统性能发挥的瓶颈.这方面的研究工作显得十分重要，研究者已在互连网络涉及的拓扑结构、切换技术、流控策略和路由算法等方面进行了大量深入研究，互连网络的复杂平衡技术也成为高性能并行计算机系统中的重要研究内容.
    2.互连网络的功能和特征
   互连网络是一种由高速开关元件按照一定的拓扑结构和控制方式构成的网络，用来实现计算系统多个计算节点之间的相互连接.是计算系统的核心组成部分，它对整个系统的性能有着决定性的影响.
   互连网络通常可以分为两大类，即静态互连网络和动态互连网络.静态网络是指处理单元间有着固定连接的一类网络，在程序执行期间，这种点到点的链接保持不变.动态网络是用交换开关构成的，可按运行程序的要求动态地改变连接状态.
   静态互连网络拓扑结构在各个节点间有专用的链路，这些链路是固定连接的，不能重新组合.每一个开关元件固定地与一个节点相连，建立该节点与邻近节点之间的连接通路，直接实现两节点之间的通信.这种网络比较适合于构造通信模式可预测或可用静态连接实现的计算机.在动态拓扑结构中，各个节点的链路可以通过设置网络中的开关来重新组合.互连网络的链路，是连接网络中相邻节点所用的通信线路，是网络的相邻节点间进行数据和控制信息传送时所使用的通路.为了反映不同互连网络的连接特性，在输入节点与输出节点之间建立对应关系，互连网络通常采用互连函数表示法和图形表示法表示输入端与输出端之间的一一对应关系.
    1.3 互连网络的负载平衡算法的并行编程实现
    1.并行程序的设计过程
    并行程序的设计过程分为4步：即任务划分、通信分析、任务组合
    和处理器映射，简称为PCAM设计过程.
    （1）任务划分：将整个计算分解为一些小的任务，以便尽可能地挖掘并行计算的机会.
   （2）通信分析：确定各任务在执行过程中所需要交换的数据并协调各任务的执行，同时可以检验任务划分的合理性.
   （3）任务组合：根据性能要求和实现的代价来考察前两步的结果，必要时可将一些小的任务组合成略大的任务，以减少通信开销或提高性能.
   （4）处理器映射：将每个任务分配到一个处理器上，其目的是最小化全局执行时间和通信成本，以及最大化处理器的利用率.
    2.并行编程语言环境
   并行编程语言环境分为共享存储编程环境和分布式编程环境两种.共享存储并行编程系统采用共享变量模型，驻留在各个处理器上的进程通过读写公共存储器中的共享变量实现相互通信，分布存储系统与共享存储系统不同，从并行程序设计的角度来看有以下两个特点：
   （1）系统通过互联网络将每个处理器连接起来，每个处理器均有自己独立的局部存储器，所有的局部存储器构成了整个地址空间.
   （2）整个地址空间有局部和全局两种编址方式，前者是系统中各局部存储器单独编址，所以用户程序空间是多地址的，远程存储器访问要通过调用消息传递库来实现；后者是系统中所有局部存储器统一编址，所以用户程序空间是一个统一单地址空间.远程存储器访问和局部存储器的访问一样用指令来完成，其指令地址由处理器地址和局部存储器地址组成.上述特点决定了分布式存储系统的两种并行编程模式：基于多地址空间的消息传递编程模型和基于单地址空间的数据并行编程模型.本书中所涉及到的并行编程语言环境，是基于多地址空间的消息传递编程模型——消息传递接口MPI（MessagePassing Interface）.
    　……