Virtualization enables multiple networks, each customized for a particular purpose, to run concurrently over a shared substrate. One such model for managing these virtual net-works is to create a hosting platform where companies can deploy services by leasing a portion of several physical routers. While lowering the barrier for innovation in the network, this model introduces new security concerns. In this paper we examine the issue of accountability in this setting of hosted virtual networks. That is, how a service provider can know its software is running without modification and that the in-frastructure provider's physical router is forwarding packets as instructed with the quality of service promised. Rather than presenting a single specification of what every router on the Internet must look like, in this paper we examine two possible approaches: one that detects violations by monitor-ing the service and one that prevents violations from occur-ring in the first place. For each, we provide a description of an architecture that can be achieved with technology avail-Able today, the limitations of that architecture, and then propose an extension which overcomes the limitations.