基于新兴古典经济理论的分布式资源分配算法研究

摘要

分布式计算经历了一系列发展，从以利用网络闲置资源执行大规模科研项目的志愿计算到以共享存储为目标的P2P计算，从科学研究为导向的网格计算到面向商业服务用户的云计算，每一次发展都是为了更好地利用网络中的资源，提高系统效率。计算资源与用户需求相比永远是稀缺的，如何在分布式网络环境中合理地调度任务，更有效地利用稀缺的计算资源，一直是分布式计算领域的关键问题，即分布式资源分配问题。 随着应用的拓广，分布式环境中资源的动态性、分布性和异构性等特征对资源分配的影响越来越明显，为了更高效地解决分布式资源分配问题，许多学者引入了经济理论。经济理论解决分布式资源分配问题，可以充分利用其固有的动态性，经济学中的一些分析框架及调度模式可以有效地指导分布式资源分配建模和求解，通过定价使得资源分布性和异构性等诸多特征反映到价格上，非常适合于解决分布式资源分配问题。 基于经济理论解决分布式资源分配问题，目前仍然面临一些问题，一是算法建模求解方面，多是简单地将经济理论中的算法映射到分布式环境，忽略了分布式环境和经济市场环境的特征;二是算法效率方面，合理的资源定价机制是提高算法效率的关键。 本文利用新兴古典经济理论研究分布式资源分配问题，该理论是对古典经济学中分工和专业化理论的继承和发展，同时，将新古典经济学中的边际分析方法纳入其中。所建立的模型不同于的基于瓦尔拉斯一般均衡的商品市场模型，不同于基于纳什均衡的博弈模型，也不同于基于线性规划的拍卖模型。其关注点不仅包括资源分配过程，还研究如何在众多节点中选取最优效能计算节点进行资源调度并动态调整网络结构，通过有效的分工结构，达到系统整体帕累托最优，具有高度自治性，更符合分布式资源分配问题的需求。每个节点能够根据个体信息做出分配决策，简化了资源分配过程的复杂性。本文主要工作如下: (1)从分布式环境特征入手，对分布式环境与经济市场环境进行比较分析，基于新兴古典经济理论的分析框架，提出一种基于新兴古典经济理论的分布式资源分配问题建模方法，给出了一种基于新兴古典经济理论的资源分配算法NCEDRA(New Classical Economics based Distributed Resource allocation Algorithm)，实现了系统中节点之间的分工，能够根据一个或多个关键参数的取值范围选择最适合当前系统环境的分配结构，优化了资源配置，提高了系统的计算效率。 (2)提出一种基于超边际分析的分布式调度算法IADSA（Inframarginal Analysis based Distributed Schedule Algorithm），在调度过程中充分考虑任务类型，以外生比较优势理论确定每个节点具有适合执行的任务类型，实现节点间的分工交互，使得节点尽可能执行具有优势的任务类型，最终达到帕累托最优的均衡状态，在保证负载平衡的基础上，进一步降低了系统执行时间。 (3)基于经济理论的分布式资源分配算法包括定价和分配两部分，如何合理定义及调整价格，是分配的基础和依据。论文提出一种基于个体负载和历史交易记录的分布式资源定价方法HIILDPM(History Information and Individual Load based Distributed resource Pricing Method)，能够在不使用动态的系统级价格影响因素基础上实现合理定价，更符合分布式计算的特征。通过买卖双方相似的定价，避免了因预算不合理等诸多因素造成的价格差距过大现象。HIILDPM属于个体理性的资源定价策略，可以通过与其他分配方法结合的方式应用于多种环境中。 (4)将HIILDPM与连续双向拍卖(CDA，continuous double auction)中的分配策略结合，设计了一种资源分配方法HIIL-CDA，能够提高单位时间内的交易完成率。实验结果表明，HIILDPM与现有定价方法相比具有较好的价格收敛性，较高的资源利用率和执行效率。在考虑任务分类的海量任务环境下，仍然具有良好的价格收敛速度，提高了系统稳定性，适用于任务密集的分布式系统环境。 (5)以GridSim框架为参考开发了一个仿真工具包EDistributed，建立了利用经济理论解决分布式资源分配问题的仿真环境，能够实现多种算法间的比较，支持以静态方法模拟动态过程。基于SimJava开发了一个仿真工具包EScheduler，建立了利用经济理论解决分布式调度问题的仿真环境。将IADSA算法与博弈算法进行比较，IADSA算法能够通过分工交互的方式提高系统效率，在实现负载平衡的基础上缩短系统的任务执行时间。

目录

声明

摘要

1．1研究背景

1．2典型分布式计算模型

1．2．1 P2P计算

1．2．2志愿计算

1．2．3网格计算

1．2．4云计算

1．3基于经济理论的分布式资源分配问题

1．3．1基于经济理论的分布式资源分配算法

1．3．2基于经济理论的分布式资源定价方法

1．3．3基于经济理论的分布式负载平衡问题

1．4本文工作及创新点

1．5论文结构安排

第2章一种基于新兴古典经济理论的分布式资源分配方法

2．1引言

2．2分布式环境下的资源分配模式分析

2．3经济市场中的资源分配问题分析

2．4基于新兴古典经济理论的分布式资源分配问题的经济性分析

2．5基于新兴古典经济的分布式资源分配建模

2．6基于新兴古典经济理论的分布式资源分配算法NCEDRA

2．7本章小结

第3章基于超边际分析的分布式调度算法

3．1引言

3．2建模思想

3．3两节点两种任务的调度模型

3．3．1不交互模式

3．3．2服务模式

3．3．3交换模式

3．3．4混合模式

3．3．5算法流程

3．4两节点多种任务的调度模型

3．5多节点多种任务的调度模型

3．6仿真工具EScheduler

3．7仿真实验

3．8本章小结

第4章基于个体负载和历史交易记录的分布式资源定价方法

4．1引言

4．2分布式资源价格影响因素分析

4．3基于个体负载和历史交易记录的分布式资源定价方法HIILDPM

4．3．1相关假设和定义

4．3．2定价方法

4．3 HIILDPM分析

4．4本章小结

5．1引言

5．3 HIIL-NCEDRA算法

5．4仿真工具EDistmuted

5．4．1开放性仿真平台需求分析

5．4．2仿真平台EDistributed的分析与设计

5．5仿真实验

5．5．1初始条件范围讨论

5．5．2模型经验参数确定

5．5．3 HIIL-CDA算法与改进CDA算法的性能比较

5．5．4 HIILDPM与其他定价方法的性能比较

5．5．5基于HIILDPM与新兴古典经济理论的分布式资源分配算法分析

5．6本章小结

第6章总结与展望

6．1全文总结

6．2未来工作展望

参考文献

致谢

攻读博士学位期间的主要成果