Research On Algorithms Of Distributed Resource Allocation Based On New Classical Economic Theory

Distributed computing has been experienced a series of progresses in which involved technologies having different objectives.That is,P2P is to share storage resources,volunteer computing is to utilize idle computing resources to execute large-scale distributed tasks,grid computing is usually used by universities and research institutes for scientific research,and cloud computing provides services for commercial users.It is obvious that the development of distributed computing always aims at using network resources preferably and improving system efficiency to some extent.However,computing resources are always scarce compared with user requirements.It always is a key issue in distributed computing that how to utilize scarce computing resources reasonably,that is,the distributed resource allocation problem.With the extension of distributed applications,influences of the dynamic nature,distributivity,and heterogeneity of computing resources in distributed environments are becoming more and more obvious.In order to figure out how to allocate distributed resources much more efficiently,economics theories are introduced to this field in the literature due to inherent dynamic natures included in the theories.In additional,some analytical frameworks and scheduling models existing in economics theories can be used to guide distributed resource allocation effectively.In particular,many features of the network including distributivity and heterogeneity can be mapped onto the final price if computing resources are priced beforehand.Therefore,economics theories are suitable for distributed resource allocation.However,it is still challenging to solve distributed resource allocation problem by using economics theories.On one hand,economics theories are simply mapped to distributed environment generally,corresponding relations of distributed environment to economic markets are ignored.On the other hand,it is very important but difficult to develop a reasonable resource pricing mechanism to improve algorithm efficiency.In this thesis,new classical economic theory is used to allocate distributed resources.It is the inheritance and development of classical economic theory,especially division of labor theory.Marginal analysis method in neoclassical economic theory is also included by new classical economic theory.The model based on new classical economic theory is different from the Walrasian general equilibrium based commodity market model,the Nash equilibrium based game model and the linear programming based auction model.Its focus includes not only the resource allocation process,but also how to pick up best efficiency node to allocate distributed resources.The system can achieve the state of Pareto optimality by the division of labor.Each node can make allocation decisions based on individual information,which simplifies the complexity of the resource allocation process.The main works are given as follows:(1)Environment characteristics are first compared between distributed and economic market environments.A new modeling method is then proposed to allocate distributed resources based on new classical economic theory.A New Classical Economics based Distributed Resource allocation Algorithm(NCEDRA)is finally proposed,where division of labor among system nodes is included and resource allocation is optimized.The most suitable distribution structure for the current system environment is selected according to the range of one or more key parameters,which increases resource utilization and system efficiency.(2)An infra-marginal analysis based distributed schedule algorithm called IADSA is proposed.Task type is concerned in schedule process,and each individual has an advantage task type computed by exogenous comparative advantage theory.The division of labor among nodes is achieved,and each node executes tasks whose type is the advantage task type of this node.The system can achieve the equilibrium state of Pareto optimality.The system execution time is further reduced on the basis of load balance.(3)Pricing and allocation are two main parts of economic theory based distributed resource allocation algorithms.Therefore,it is the basis of distribution that how to define and adjust the price reasonably.A history information and individual load based distributed resource pricing method called HIILDPM is proposed which is more in line with the characteristics of distributed computing and where pricing is reasonable without the use of dynamic system-level influencing factors.The phenomenon of large price gap because of the non-reasonable budget is avoided due to similar pricing ideas of buyers and sellers.HIILDPM belongs to individual rational resource pricing strategies,which can be applied to different environments combined with other distribution methods.(4)HIILDPM is combined with the allocation strategy in continuous double auctions(CDA)to form a resource allocation method called HIIL-CDA.The proposed method increases transaction completion rate of unit time interval.Experimental results show that HIILDPM has a better price convergence,higher resource utilization,and efficiency than existed pricing methods.In addition,HIILDPM has a good convergence rate in massive task environment.It improved system stability and is suitable for task-intensive distributed system environment.(5)A simulation toolkit called EDistributed was developed based on the GridSim framework in which distributed resource allocation using economic theories can be simulated and relative algorithms can be compared.The dynamic processes are simulated in a static way.A simulation toolkit called EScheduler was developed based on SimJava,in which economic theory based distributed load balancing problem is simulated and relative algorithms can be compared.Experimental results show that IADSA has better performance than the game theory.It can improve system efficiency through the division of labor among nodes,and reduce system execute time on the basis of load balance.