Software-Defined Networking (SDN) has evolved as a new networking paradigm to solve many of current obstacles and limitations in communication networks. While initially intended mainly for single-domain networks, SDN technology is going to be deployed also to large cloud-based data centers where several customers, called tenants, share network resources. In a multi-tenant environment, the SDN technology allows the customers to have higher level of control over the available network resources. However, as the underlying network elements and control logic are shared between multiple tenants, the isolation between tenant domains becomes an important factor in the design of all multi-tenant solutions. In this paper, we propose a scalable system architecture based on OpenFlow and packet rewriting that provides isolation and controlled sharing between tenants while enabling them to have control over their assigned resources. The architecture addresses different facets of isolation in a multi-tenant network including traffic, address space, and control isolation. Our solution improves on previous ones by putting special emphasis on inter-tenant communication, e.g. on subcontractor relations in cloud services. The evaluation of the prototype indicates that our solution puts only a small performance overhead on forwarding in a shared network.