Communication-oriented Optimal Deployment In Virtual Computing Environment

Internet-based Virtual Computing Environment (iVCE) is a novel network comput-ing platform targeting the features of Internet. Based on the autonomy of Internet re-sources, iVCE focuses on resource sharing and collaborative working on open networkinfrastructures, with the key mechanisms of on-demand aggregation and autonomic col-laboration. Applications deployment is a key technology and a basic service in iVCE,and influences the scalability, reliability and performance of iVCE greatly. Comparedwith traditional distributed systems, e.g., Grid computing, iVCE exhibits some specialcharacteristics, which bring many challenges for application deploymentTherearemanydifferenttypesofapplicationsiniVCE,includingnotonlycomputing-intensive applications, but also communication-intensive applications. Autonomic ele-ment is the basic resource management unit in iVCE, and can be a physical machine or avirtual machine. Autonomic elements usually interact and collaborate with each other toaccomplish a task. Thus, communication is an important factor when deploying applica-tions on iVCE. This dissertation focuses on optimizing the deployment of applications iniVCE with respect to communication characteristics, aiming to improve the performanceof these applications. Specifically, the dissertation makes the following contributions.Firstly, a communication-aware deployment method is proposed. Usually, rankingmethods are used to rank iVCE nodes based on their QoS values, without consideringthe communication performance between nodes. Therefore, ranking based methods can-not be applied to communication-intensive applications. A communication-aware de-ployment method is proposed for communication-intensive applications. This methodnot only takes into account node computation performance, but also the communicationperformance among different nodes. In addition, the response time of some iVCE nodepairs may not be available in some scenarios. For this problem, this dissertation proposesa method that uses similarity to predict the missing communication information amongiVCE nodes. The experimental results show the effectiveness of the communication-aware deployment method.Secondly, a spectral clustering based deployment method is proposed. In tradition-al distributed computing systems, clustering-based deployment methods usually partitionsubtasksintodifferentgroupsbasedontaskgraphs. However, iniVCE,usersusuallycan- not provide task graphs, since users may not be the developers of applications. Therefore,itisdifficulttousetaskgraphbaseddeploymentmethodiniVCE.Toattackthischallenge,this dissertation proposes a spectral clustering based deployment method, which formu-lates the deployment problem as a graph partition problem, and uses a spectral clusteringalgorithm to partition nodes into different groups. The method does not require users toprovide task graphs. To improve the quality of clustering, a K-means algorithm is refined,and the basic idea is to cluster only the nodes in high-density areas. Based on the resultof clustering, a greedy algorithm is proposed to find an approximately optimal node setto deploy applications.Thirdly, a method for automatically discovering communication topologies is pro-posed. Instead of requiring users to provide communication topologies, the method usespre-execution and multi-scale graph clustering to discover communication topologies au-tomatically. Pre-execution records the execution information of the application to be de-ployed. To ensure the effectiveness of pre-execution, the problem size of an application isreduced when pre-executing the application. After obtaining the traces of the application,a multi-scale algorithm is used to discover the communication topology automatically. Inaddition, to improve the performance of collective operations, the dissertation proposes amethodthatusescommontopologystructuresandhierarchicalmodelstodooptimization,instead of designing collective operation algorithms or implementing MPI libraries. Theexperimental results show the practicality of the method.Finally, a cost-aware virtual machine (VM) dynamic deployment method is pro-posed. Thisdissertationmodelthecostofusersandserviceproviders, andpresentthattheexecution time of applications and the number of idle service influence the cost greatlybased on the cost model. In order to reduce the cost, this dissertation proposes a cost-aware VM dynamic deployment method based on the cost model. The method includestwo stages: build time stage and runtime stage. At runtime stage, a traffic-aware VM-s is proposed. The online optimization method monitors the traffics among VM to gettraffic topologies, based on which related VMs are migrated to neighbors to improve theperformance and reduce the traffics.To justify the effectiveness of the deployment methods proposed in this dissertation,we conducted comprehensive experiments on a real-world experimental platform and awell-knownsimulator. Theexperimentalresultsshowtheeffectivenessofthedeployment methods.