Star Graph Knapsack Problem With Traffic Constraint

As the rapid development of Internet technology, companies’increasing need for high resource utilization, and users’desire for easy access to hardware and software, cloud computing arises. Cloud computing, together with IT technology and internet ideology, makes powerful computing ability and large storage capacity possible. A user places a virtual machine running on the cloud platform, and pays for the resource the virtual machine needs, such as the computing resource, the storage space and the network bandwidth.For a particular cloud platform, the physical resources are always limited especially for rare resource. Once too many users ask for resource in the platform, maximizing revenue becomes an important objective of resource allocation.In this paper, star graph topology is considered as a physical resource organization structure, and then the resource optimization problem is modeled as a star graph knapsack problem. For this problem, two methods have been proposed. First one is an exact algorithm, which is aimed at obtaining an optimal solution. The integer programming of star graph knapsack problem is formulated, and then is solved by linear programming kit lpsolve. Also a theoretical result is given for a special subproblem, including optimal value and optimal solution. Second method is a heuristic method, which gives non-optimal solution. Greedy method is applied to solve the problem and some greedy strategies are proposed. Greedy algorithm is much faster than the integer programming. The experiment results imply that greedy algorithm works well for small scale instances, and also explain that worst-fit performs better than best-fit for the strategy of choosing knapsack to place items.