Cloud computing allows tenants to run a wide range of applications without any upfront capital investment. However, providers lack mechanisms to provide fair and predictable bandwidth sharing among allocated applications, enabling selfish and malicious tenants to cause performance interference in the network (and denial of service in an extreme case). Such interference results in poor and unpredictable network performance for well-behaved applications. Recent research has proposed techniques that (i) cannot protect tenants against interference; (ii) result in under utilization of resources; or (iii) add substantial management overhead. In this paper, we describe a resource allocation strategy that aims at providing predictable network performance (i.e., minimizing performance interference) with bandwidth guarantees for tenant applications, while maintaining high network utilization and low management overhead. These benefits are achieved by grouping applications from mutually trusting users into logically isolated domains (virtual infrastructures - VIs) with bandwidth guarantees, while also considering the amount of traffic generated by applications. Despite the benefits, grouping may lead to fragmentation (i.e., available resources are dispersed among VIs and some requests may be unnecessarily declined). Therefore, we also study the associated trade-off (grouping to increase isolation versus resource fragmentation). To illustrate the feasibility of grouping applications inside VIs, we develop PredCloud, a system that implements the proposed strategy on SDN/OpenFlow-enabled networks. Through an extensive evaluation, we show that PredCloud significantly reduces performance interference and application exposure to attacks, while maintaining low resource fragmentation. Furthermore, provider revenue can be increased by efficiently managing and charging network resources.