Abstract | ||
---|---|---|
Resources in modern computer systems include not only CPU, but also memory, hard disk, bandwidth, etc. To serve multiple users simultaneously, we need to satisfy their requirements in all resource dimensions. Meanwhile, their demands follow a certain distribution and may change over time. Our goal is then to admit as many users as possible to the system without violating the resource capacity more often than a predefined overflow probability. In this paper, we study the problem of allocating multiple resources among a group of users/tasks with stochastic demands. We model it as a stochastic multi-dimensional knapsack problem. We extend and apply the concept of effective bandwidth in order to solve this problem efficiently. Via numerical experiments, we show that our algorithms achieve near-optimal performance with specified overflow probability. |
Year | DOI | Venue |
---|---|---|
2012 | 10.1109/DCOSS.2012.16 | DCOSS |
Keywords | Field | DocType |
multiple resource allocation,effective bandwidth,hard disk,stochastic demands,multiple resource,stochastic multi-dimensional knapsack problem,resource allocation,stochastic demand,certain distribution,resource dimension,multiple user,modern computer systems,resource capacity,stochastic multidimensional knapsack problem,knapsack problems,cpu,predefined overflow probability,specified overflow probability,probability,knapsack problem,vectors,satisfiability,upper bound,bandwidth,approximation algorithms,mathematical model | Approximation algorithm,Mathematical optimization,Computer science,Upper and lower bounds,Bandwidth (signal processing),Resource allocation,Knapsack problem,Distributed computing | Conference |
ISBN | Citations | PageRank |
978-1-4673-1693-4 | 2 | 0.42 |
References | Authors | |
7 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Fangfei Chen | 1 | 65 | 5.48 |
Thomas La Porta | 2 | 801 | 91.33 |
Mani Srivastava | 3 | 13052 | 1317.38 |