The scale and complexity of online applications and e-business infrastructures has led service providers to rely on the capabilities of large-scale hosting platforms, i.e., data centers. Dynamic resource allocation (DRA) algorithms have been shown to allow server resource allocation to be matched with application workload, which can improve server resource utilisation and drive down costs for service providers. However, research on DRA algorithms has almost exclusively focused on their performance characteristics at small-scale, precluding their useful application in commercial hosting environments, such as those dedicated to supporting cloud computing. In this paper, we show, and subsequently propose a framework to address, the scalability problems of current DRA algorithms. We then build on the proposed framework to develop a highly-scalable algorithm for dynamic resource allocation.