Chatty Tenants and the Cloud Network Sharing Problem

by Bryan Ford

The cloud service ecosystem is exploding not only in the number and variety of services available to end users, but also in the depth and complexity of the component stacks that constitute any particular user-visible cloud service. This trend makes it increasingly critical for cloud infrastructure providers to manage not just intra-tenant but inter-tenant communication traffic fairly and efficiently, since a growing fraction of traffic within a data center occurs between distinct but cooperating tenants to implement these deep and intricate cloud component service structures. This paper takes an importantstep toward formulating a principled but realistic and implementable theory of how to manage inter-tenant cloud communication effectively, starting with the critical and nontrivial problem of defining what "fairness" and "bandwidth proportionality" should mean in this context: i.e., proportional to what? The approach this paper proposes is to seek to offer bandwidth guarantees, for a given communication flow, proportional to the lowest-paying of the two tenants involved. This approach addresses perverse incentives and vulnerabilities to abuse that result from other more obvious schemes, such as the abilityfor tenants to obtain disproportionate bandwidth by communicating with a large number of partner VMs owned by different tenants.

The paper presents Hadrian, a practical VM placement and bandwidth allocation system built on this approach to defining communication bandwidth fairness. Hadrian's placement algorithm accounts for tenants' minimum bandwidth requirements and inter-tenant communication dependencies, modeling these constraints as a max-flow network, and uses a greedy first-fit algorithm to place VMs and provide admission control ensuring that the minimum bandwidth guarantees can be met. Once VMs are placed, Hadrian then uses a hose-compliant allocation scheme to assign network bandwidths to flows, thereby satisfying both minimum bandwidth constraints and fairness goals. Through a small-scale prototype testbed coupled with larger-scale simulation-based analysis, the paper provides experimental evidence suggesting that Hadrian's approach is realistic and efficiently implementable in data centers with up to 16,000 hosts and four VMs per host.

Hadrian will not be the last word in fair bandwidth management for inter-tenant communication, of course. Many unresolved questions remain, such as whether there are other less-obvious incentive compatibility issues or vulnerabilities to abuse that the proposed scheme leaves un-addressed, such as other variants of Sybil attacks. The paper clearly suggests opportunities for future synergistic research in modeling and formally analyzing the robustness of this and similar schemes to arbitrary strategic behaviors by tenants. The paper also leaves some important practical questions to future work, such as how to manage fair allocation for services likely to be used by most or all tenants, such as central storage services offered by the cloud infrastructure provider. In general, even if not the last word, the NSDI PC felt that this paper represents a clear, principled, and compelling step forward toward a deeper understanding of fair communication resource allocation mechanisms to manage today's and tomorrow's tangled stacks of interdependent cloud-based services.