Cloud computing realises the vision of utility computing. Tenants can benefit from on-demand provisioning of computational resources according to a pay-per-use model and can outsource hardware purchases and maintenance. Tenants, however, have only limited visibility and control over network resources. Even for simple tasks, tenants must resort to inefficient overlay networks. To address these shortcomings, we propose Network-as-a-Service (NaaS), a framework that integrates current cloud computing offerings with direct, yet secure, tenant access to the network infrastructure. Using NaaS, tenants can easily deploy custom routing and multicast protocols. Further, by modifying the content of packets onpath, they can efficiently implement advanced network services, such as in-network data aggregation, redundancy elimination and smart caching. We discuss applications that can benefit from NaaS, motivate the functionality required by NaaS, and sketch a possible implementation and programming model that can be supported by current technology. Our initial simulation study suggests that, even with limited processing capability at network switches, NaaS can significantly increase application throughput and reduce network traffic.