Tree Packing for Elastic Machine Allocation in RaaS Cloud

An Elastic Machine (EM) consists of networked fine-grained resources, such as CPU, memory, network and storage, dynamically composed from distributed resource pools offered by a RaaS (Resource-as-a-Service) cloud. EM allocation in RaaS clouds differs from VM placement in IaaS clouds in that it needs to consider the network conditions between the fine-grained resources. To address this problem, this paper presents a d-tree model to represent network conditions for both EM and resource pools and treat EM allocation as a tree packing problem. To solve this NP hard problem efficiently, this paper describes a tree packing framework that combines 12 approximate algorithms by using tree density to sort d-trees and virtual distance to filter d-trees. Using simulation tests and 6 quality measures, new algorithms that outperform the previous tree packing algorithm are discovered. Furthermore, the tests show that the algorithms that respect the network conditions outperform those that ignore them in most cases. Moreover, the top 2 algorithms are identified using a ranking function that combines the quality measures.