Large-scale Networked Virtual Environments (NVEs) are used to enable rich interactive experiences such as multiplayer games, military and industrial training, and collaborative engineering systems. In these applications, hosts must exchange data updates to maintain a consistent view of the virtual environment. In large-scale environments, the volume of data places a heavy load on the networking and computational resources available to each host. To improve scalability, systems have employed a variety of techniques, including data subscription, data segmentation, and multicast. In this paper, we describe a communication architecture for Networked Virtual Environments that takes advantage of unstructured peer-to-peer (P2P) overlay networks for message distribution. The overlay network design provides scalability while supporting easy deployment over today’s Internet. The approach, when combined with data segmentation and data subscription, enables Internet deployment of large-scale NVEs.