etworked virtual environment (NVE) [1, 2] , also known as distributed virtual environment, is a relatively new field that combines 3D graphics with networking to provide simulated yet immersive experiences for people across the globe. NVEs originated in the 1980s with military simulators [3] and has since evolved to today's Massively Multiplayer Online Games (MMOGs) [4] , where hundreds of thousands of people interact simultaneously in fantasy worlds. As of early 2006, the most popular title, World of Warcraft, has attracted more than six million subscribers within two years, while the game Lineage also has more than four million subscribers worldwide. The MMOG genre has grown rapidly since its inception in the mid-1990s, making it a multibillion dollar business and a major Internet application [5] . More than 100,000 peak concurrent users are frequently reported for major MMOGs, making scalability a defining trait. NVE scalability is fundamentally a resource issue, and is determined by whether the system has enough resources to continuously accommodate new participants. However, existing server-based architectures pose inherent scalability limits and significant costs. Though much effort has been spent on improving scalability, no real system exists as yet that could feasibly support more than one million concurrent users. The popularity and rapid growth of large-scale NVEs such as MMOGs will likely pose serious challenges to existing networks and architectures in the near future. On the other hand, a new class of peer-to-peer (P2P) applications that seeks to realize large-scale NVEs has recently appeared as an alternative. P2P applications are distributed systems in which each node runs the same software [6] . They differ from grid computing in that the basic units are commodity PCs instead of well-provisioned facilities. Although the early P2P systems adopted point-to-point topologies that scaled poorly, P2P file sharing made of millions of nodes (e.g., Gnutella and Kazaa) has publicized scalable P2P systems, which also include significant recent research on distributed hash table (DHT) [6] , where a given key is mapped to a node and may be searched efficiently (allowing, for example, files to be found without any centralized directories). P2P systems promise scalability and affordability by bringing user resources to the system and are composed of commodity hardware. Yet they also create new challenges such as topology maintenance (as nodes can join or leave at any time) and efficient content search (as the global topology is unknown to each node). This article extends our previous work [7] and identifies an emerging field that applies P2P techniques to realize NVEs on scales unattainable by existing architectures. A simple and efficient design based on Voronoi diagrams [8] , called the Voronoi-based Overlay Network (VON), is also presented. VON exploits the locality of user interests to maintain the P2P topology with small overhead, and achieves high scalability by bounding resource use at each participating node. This article provides an analysis of the NVE scalability problem, identifies the emerging P2P-based NVE (P2P-NVE) research, and presents a description of VON. In the following sections, we first provide the background of NVE systems and explain the scalability problem with respect to P2P adaptation, followed by examinations of recent P2P-NVE proposals. We then explain the design rationales and procedures of VON, and demonstrate its scalability, consistency, and reliability with simulations. Discussions of VON's properties and comparisons with other systems are made before we conclude this article with a summary and some future perspectives. NVEs are synthetic worlds where each user assumes a virtual identity (called avatar) in order to interact with other human or computer players. Users may perform different actions such as moving to new locations, looking around at the surroundings, using items, or engaging in conversations and N N Shun-Yun Hu, Institute of Physics, Academia Sinica, Taiwan Jui-Fa Chen and Tsu-Han Chen, Tamkang University The scalability of large-scale networked virtual environments (NVEs) such as today's Massively Multiplayer Online Games (MMOGs) faces inherent limits imposed by client-server architectures. We identify an emerging research direction that applies peer-to-peer (P2P) networks in order to realize more scalable and affordable NVEs. The central issue for P2P-based NVE (P2P-NVE) systems is to correctly and efficiently maintain the topology of all participating peers by solving the neighbor discovery problem. We also propose the Voronoi-based Overlay Network (VON), a simple and efficient design that maintains the P2P topology in a fully-distributed, low-latency, and message-efficient manner. Simulation results show that by bounding the pernode resource consumption, VON can be fundamentally more scalable than existing methods while achieving high topology consistency and reliability. A number of issues are involved in building an NVE system; several are described as follows. Consistency -As NVEs are shared environments, it is important that each participant perceives the same states and events. Consistency in NVEs usually refers to consistent object states and event orderings [1] , which are maintained through the transmission of event messages. However, event messages may be delayed or lost, making consistency a challenging issue. Responsiveness -To provide a sense of natural interactions, the delay between a user's action and observable consequence should be minimized despite network latency. NVE systems thus have a real-time requirement. However, latency tolerance can be application dependent [9] . Responsiveness and consistency are usually seen as trade-offs, as waiting for late or retransmission of missing packets results in delays. Scalability -The true potential of NVEs lies in networking large numbers of people, which makes scalability a key aspect for future NVEs. It is also important in terms of service availability (i.e., whether systems can sustain rapid usage increase) and content possibilities (i.e., large participant size enables new types of designs and interactions). Persistency -Contents within NVEs (e.g., virtual objects and computer characters) may need to exist persistently to provide a sense of realism. Current MMOGs provide persistent-world experiences that operate 24 hours a day, where users can keep virtual items and player profiles between login sessions via centralized database storage. Reliability -As NVEs become scalable and persistent, they will also need to sustain hardware or software failures, in order to ensure service availability and smooth user experiences. Reliable and fault-tolerant systems will increase in importance as NVEs become more service oriented. Security -Many types of NVE maintain user accounts and allow competitions between users. Security is therefore important to ensure fairness during interactions and privacy of user information. It is especially emphasized in commercial systems. Our focus is on scalability, as it allows new design possibilities. Responsiveness and reliability are also discussed; however, consistency is only considered for user position states, while persistency and security are beyond our scope. Two main types of resources in NVE systems are processing power and bandwidth [1] . As bandwidth tends to be the main resource bottleneck, it will be our focus (see [4] , p. 228). MMOG is an important and arguably the most successful subset of NVE. To provide an entertaining experience, MMOGs focus more on game designs, continuous supplies of game contents, and security than other types of NVEs [2, 4] . Game states for users, virtual items, terrain, and computer-controlled characters are maintained at the servers. Typical network messages include environmental changes (e.g., door opening), movements, interactions (e.g., chatting, trading, or combating), and system services (e.g., login, friends search, software, or content updates) [4, 9] . However, in this article we focus on position updates, as they represent the most fundamental and largest share of message traffic [10] (see also [4] , p. 278). Scalability in this article refers to whether an NVE system can accommodate a wide range of concurrent users without compromising certain quality of service (e.g., sufficient message updates that ensure consistency or responsiveness). The issue at heart is whether system resources do not deplete as new users join. In a generalized NVE, users can be conceptually seen as coordinate points on a 2D plane (as nodes), each with a visibility range called area of interest (AOI). AOI is a fundamental NVE concept, as even though many users and events may exist in the system, each user -as in the real world -is only affected by nearby users or events. AOI thus specifies a scope for information which the system should provide to each user. For simplicity, we assume that AOI is a circle centered on the user, and nodes move at discrete time-steps. The central communication problem thus is: how does each node receive relevant messages (generated by other nodes) within its AOI as they move around? The earliest solution to this problem is to simply broadcast updates, or connect everyone in a point-to-point manner. are the classic examples. Broadcast is applicable only to LANs, while point-to-point is not scalable as connections grow at O(n 2 ) with user size. Client-server architectures improve the situation, where each user communicates with a centralized server (e.g., ). Relevant messages are relayed by the server, reducing message traffic to O(n) (Fig. 1a) . However, the server becomes the bottleneck and its resources availability dictates the system's scale. To increase server-side resources, server clusters are devised to combine multiple servers on a high-speed LAN with large amount of bandwidth for external connectivity (e.g., [12] , RING [13] ). Contrary to "increase resources" methods, the "decrease consumption" strategies try to reduce message transfers by packet compression or aggregation (i.e., combining several messages into a coarse representation [14] ), or through interest management [15] , which seeks to filter out irrelevant messages (i.e., those generated outside a user's AOI should not be received). Interest management is of particular importance, as com- ), each with a prespecified multicast address. A node sends messages to the address of its residing group, and subscribes for groups that coincide with its AOI. Ideally each node would then only process a finite amount of relevant messages, thus making the system more scalable (Fig. 1b) . Various designs mainly differ in the grouping methods and the abstraction that is assigned an address (e.g., NPSNET divides the world into hexagonal cells, while VELVET assigns each user a multicast address). Multicast has two major benefits: messages are sent only once to the network, and are filtered by the infrastructure without host processing. However, the messages received may be irrelevant or insufficient if group scopes are improperly defined [21] . The most serious problem, however, is that multicast has not been widely deployed and relatively few addresses are available for largescale applications. Application-layer multicast [22] has been proposed to address the lack of network-layer multicast by building overlay networks. Nodes self-organize into multicast trees and deliver messages to many recipients via node relays. However, defining the appropriate multicast groups is still challenging, while the latency due to relays may not be appropriate for NVEs' real-time requirements. Today's MMOGs overwhelmingly adopt server clusters due to well-supported security and persistency mechanisms. They nevertheless face three scalability issues: insufficient total resources, high user density, and excessive interserver communications. The first issue is dealt with by provisioning more hardware. However, MMOG traffic analysis [10] shows that human behaviors cause bursty traffic such that instantaneous resource use can be much higher than average. Hence overprovisioning is likely to happen. Even with enough total resources, users would often concentrate at hotspots where interesting events occur (known as user crowding or flocking), and overload the servers handling the hotspots. Though server-cluster load balancing has been proposed [23] , migrating users to other servers may induce the third issue of excessive interserver communications that consume bandwidth and introduce latency (e.g., when transferring user profiles across servers, or when supporting interactions between users on different servers). P2P designs may alleviate these issues due to the following reasons: • Resources are brought into the system with each additional node joined. • Nodes may individually determine and reduce their messaging scopes when user densities increase. • Message exchange only with relevant (i.e., AOI) neighbors may effectively restrict internode traffics. Due to NVEs' unique requirements, we argue that P2P-NVE poses as a new class of P2P systems worthy of study. One notable difference between P2P-NVE and DHT or file sharing is that the problem of content search is greatly simplified: as each node's AOI is limited, the desired content is localized and easily identified as the messages generated by other nodes within the AOI. This differs from file sharing, where the desired content may potentially be on any node. The central content search in P2P systems thus becomes a neighbor discovery problem, and may be stated as: given a node's position and AOI, find all neighboring nodes within the AOI. NVE design criteria also transform into the following issues and metrics. Consistency -As consistency issues other than user positions are outside our scope, here we focus on topology consistency [24] , which can be defined as the percentage of correctly known AOI neighbors (e.g., for a node that is aware of four out of five AOI neighbors, topology consistency is 80 percent). Another useful metric is drift distance [19] , defined as the distance (in absolute value) between the observed and actual coordinates of a node. Two closely related concepts are global connectivity (i.e., whether the overlay is fully connected) and local awareness (i.e., whether each node is fully aware of its AOI neighbors) [25] . Ensuring these properties presents a challenge for any P2P-NVEs. Responsiveness -To fulfill the real-time requirement, message latency should be minimized while bandwidth use should be efficient. Ideally, nodes should connect directly to their AOI neighbors so as to minimize latency. Scalability -In a P2P environment, the key scalability issues are whether resource use is bounded at each node, and if potential traffic bursts can be handled. Average and maximum transfer-sizes on each node within a period are thus useful indicators. Reliability -As packet loss, delay, and node failures can adversely affect topology consistency, robustness against these problems is the main reliability issue. Recovery steps, defined as the number of time-steps to recover to 100 percent topology consistency, may be a useful metric. P2P-NVEs can potentially be more scalable, responsive, and reliable than server-based solutions, while it remains for future research topics to provide adequate support for consistency, persistency, and security in a P2P environment. We now describe and categorize some recent P2P-NVE proposals as follows. Enhanced Point-to-Point -Novel message-filtering techniques have been devised for point-to-point architecture, where all nodes know each other. The idea is to allow transmission only under mutual visibility. Update-free regions (UFRs) [26] define pairs of mutually invisible regions in the NVE. Message exchange is not needed if two nodes stay within their respective UFRs, and only resumes if one of them steps out. Then, either the UFRs are renegotiated (if visibilities are still blocked) or position exchange begins. However, UFRs do not scale, as each node needs to negotiate with all other nodes. Also, excessive message exchanges can happen if many neighbors are mutually visible (e.g., when sights are not blocked or crowding occurs). Frontier sets [27] provide an improved approach for UFRs, but suffer from the same limitations. DHT-Based -Significant research efforts have been devoted to interest management via multicast. As multicast is not widely used, application-layer multicast provides a workaround. SimMud [9] uses Scribe, an application-layer multicast built on the DHT Pastry, and divides the NVE into some fixed-size regions. Each region is managed by a promoted super-node, which serves as the root of a multicast tree. region and relays the updates to them. Links are maintained between super-nodes to aid user transitions across regions. However, a super-node can be overwhelmed by crowding in the region, and message latency may be up to several seconds due to relays. To reduce latency, Zoned Federation [28] uses DHT only for topology connectivity, while regular nodes connect directly to the region's super-node. However, crowding can still be a concern. Neighbor-List Exchange -To discover neighbors without resorting to centralized servers or super-nodes, knowledge from existing neighbors may be exploited. Kawahara et al. describe a fully-distributed scheme [24] in which each node directly connects with a fixed number of nearest neighbors and constantly exchanges neighbor lists in order to discover new nodes. Although direct connections minimize latency, constant list exchanges incur transmission overheads. When separated by large distances, nodes may also lose mutual contacts and cause overlay partitions [24] . To ensure global connectivity, the Message Interchange Protocol (MIP) [29] keeps at least one neighbor in each of the four cornering directions of a node. However, the frequency of list exchange is still a delicate trade-off between neighbor discovery timeliness and bandwidth use. Mutual Notification -Neighbor-list exchange may not be bandwidth efficient, as much of the transmission is redundant. A better approach is to notify new neighbors only when necessary. Solipsis [25] is another fully-distributed system, where each node connects to all the neighbors within its AOI. Neighboring nodes serve as the "watchmen" for approaching foreign nodes and neighbor discovery is achieved by notifications from known neighbors. As Solipsis maintains direct connections among neighbors, latency is minimized. To ensure global connectivity, each node needs to be inside the polygon (i.e., a convex hull) formed by its outmost neighbors. However, neighbor discovery is occasionally incomplete, as incoming nodes may be unknown to directly connected neighbors. In other cases, active queries are required when the within-convex-hull property is violated, which slows down neighbor discovery [30] . is a hybrid between client-server and P2P architectures. Nodes organize into various groups and are managed by provisioned hardware called multicast reflectors. Groups are created or modified by control servers, from which participating nodes obtain mappings between the groups and multicast reflectors. Nodes subscribe and send updates to multicast reflectors by individual interests, and discover neighbors via messages relayed by the multicast reflectors. Strictly speaking, client-server hybrids are server-cluster variants where the combined bandwidth of specialized servers determines the scalability limit. [32] is an interesting mix of DHT, neighbor-list exchange, and direct transfer. The NVE is divided into hexagonal cells (like NPSNET), and DHT is used to ensure global connectivity. Within each cell, a master node maintains a list of slave nodes and exchanges the list periodically with neighboring masters. Slave nodes are notified of new neighbors by the masters. To avoid latency, slave nodes exchange messages directly among themselves. However, the selection of adequate masters is a concern, especially when crowding is considered. The frequency of slave-node list exchange is also a difficult balance between bandwidth use and neighbor discovery timeliness, as in other neighbor-list exchange schemes. Client-Server Hybrid Various P2P-NVE schemes differ in their degree of decentralization. In general, the more distributed the design, the more responsive the system becomes; however, this occurs at the expense of increased bandwidth utilization. Super-nodes may use less bandwidth at the cost of worse tolerance to node failures and crowding. Other differences include neighbor-discovery timeliness and event-ordering support. Although these designs are potentially more scalable than client-server, correct and timely neighbor discovery and user crowding tolerance are still the most common issues. We propose the use of Voronoi diagrams [8] to solve the neighbor discovery problem in a fully-distributed, bandwidthefficient, and low-latency manner. Our design objectives are: scalability, achieved by limiting per-node transmission; and responsiveness, achieved by requiring direct connections for all data exchanges. Given a number of points (called sites) on a 2D plane, a Voronoi diagram partitions the plane into the same number of Voronoi regions (or simply regions), such that each region contains all the points closer to the region's site than to any other site (Fig. 2a) . The Voronoi diagram defines a spatial relationship between various nodes and may be used to find the k-nearest neighbor of any site efficiently. Since Voronoi diagrams have been widely studied and applied to diverse fields (e.g., computational geometry and mobile computing), we do not consider the specifics of Voronoi construction but assume that good algorithms exist. For our purpose, each node in VON is represented as a site in the Voronoi diagram. For a given node, we define AOI neighbors as the nodes whose positions are within its AOI. Enclosing neighbors are nodes whose regions immediately surround the given node, and boundary neighbors are AOI neighbors whose enclosing neighbors may partially lie outside the AOI (Fig. 2b) . Each node maintains a Voronoi diagram of all AOI neighbors and directly connects them to minimize latency. As only a few neighbors are kept, the cost to maintain a Voronoi diagram at each node is low. To prevent overlay partition (i.e., groups of nodes become mutually unaware of each other), we also require each node to minimally keep its enclosing neighbors (which may be outside the AOI when neighboring nodes are sparse). When a node moves, position updates are sent to all connected neighbors (i.e., AOI neighbors plus any enclosing neighbors beyond AOI). Neighbor discovery is done via notifications from boundary neighbors, as they know both the moving node and other nodes beyond the AOI (which happen to be their enclosing neighbors). This way, potential AOI neighbors are discovered with mutual collaborations. As a node moves around, it will constantly discover new nodes and disconnect those that have left its AOI (unless they are enclosing neighbors). A node thus restricts communications with mostly the actual AOI neighbors, independent of the scale of the system. Keeping bandwidth consumption at each node bounded is the key to VON's scalability. One potential concern is that when crowding occurs (i.e., user gatherings that cause high densities of nodes, see the center of adjustable AOI [20] , so that nodes with different bandwidths can individually determine their optimal AOI radii. We also apply dynamic AOI adjustments according to three simple rules: • A node shrinks its AOI when the number of connected neighbors exceeds a prespecified connection limit. • AOI restores to the preferred size if the number of connected neighbors again falls below the limit. • To ensure mutual awareness between nodes, a node will not disconnect a neighbor whose AOI still covers it, even if that neighbor is outside of its own AOI. We now describe VON's three main procedures (see [30] for pseudocodes). JOIN Procedure -A joining node first contacts the gateway server (i.e., the first bootstrapping node in VON) for a unique ID, then sends a query with its joining coordinates to any existing node (which can be the gateway). Using greedy forward, the query will eventually reach the acceptor (i.e., the node whose region contains the joining node's coordinates, see Fig. 3a ), which responds by sending a list of joining node's AOI and enclosing neighbors. The joining node then connects to each neighbor on the list and organizes their coordinates into a Voronoi diagram. The neighbors also update their Voronoi diagrams to account for the joining node (Fig. 3b) . MOVE Procedure -When a node moves, position updates are sent to all currently connected neighbors. If the recipient is a boundary neighbor, it will check to see if any of its enclosing neighbors is now visible to, or has become the enclosing neighbor of, the moving node (Fig. 4a) . If new neighbors are identified, notifications are sent to the moving node for initiating connections. During handshakes with a new neighbor, the moving node also sends its knowledge of the enclosing neighbors of the new neighbor, which would verify and notify the moving node of any missing ones. The moving node will also disconnect any boundary neighbors that have left its AOI (Fig. 4b) . During each time-step, Voronoi diagrams are updated at all nodes to reflect the current topology. LEAVE Procedure -The leaving node simply disconnects (no distinction is made between proper and abnormal departures from the overlay network, see Fig. 5a ). Affected neighbors will update their Voronoi diagrams. In case of boundaryneighbor departures, replacements are learned via other stillconnected boundary neighbors (Fig. 5b) . Significant work has been done using Delaunay triangulation (the dual structure of the Voronoi diagram [8]) to construct overlays for application-layer multicast (DT-overlay) [22] . DToverlay provides a scalable protocol where nodes use only local information for packet forwarding. However, requirements for application-layer multicast and NVE differ in important aspects: the former aims to send data to potentially many recipients, so that message delivery is characterized by relays between nodes, yet NVE's real-time trait demands minimal latency (i.e., relays should be avoided if possible). The Voronoi diagram (or Delaunay triangulation) is thus used differently in VON (i.e., to discover new neighbors) than in DToverlay (i.e., to derive routing paths). VON also differs from DT-overlay in at least two respects: • It lacks DT-overlay's main drawbacks of high end-to-end latency and multiple transfers of the same data over a physical link [22] , as all transmissions are direct. • It considers constant node movements, whereas there is no equivalent of VON's MOVE procedure in DT-overlay's protocol. VON is similar to DT-overlay only if all nodes just connect with their enclosing neighbors and do not move. Voronoi diagrams simplify two difficult identifications in neighbor discovery: the nodes making the discovery decisions and the minimal set of connected neighbors to ensure com- plete discovery. The former is solved by boundary neighbors, while the latter by enclosing neighbors. To evaluate VON's properties, simulations using both fixed and dynamic AOI are performed (referred to as the basic and dynamic AOI, or dAOI model, respectively, see Table 1 ). The simulations proceed in more than 3000 discrete time-steps, where nodes move randomly with a constant speed. As users in real NVEs do not distribute uniformly, we place up to 2000 nodes within a 1200 × 1200 area to simulate high-density scenarios. After allowing the system to stabilize for 200 steps, we measure the transmission size per node per second, assuming 10 movements per second (for comparison, typical update rates for MMOGs are 1-5 times/s [10] , and 10-20 times/s for fastaction games). For simplicity, we assume constant latency for all simulations (i.e., messages sent are processed in the next time-step). The simulation results are presented with 95 percent confidence intervals; VON's properties are discussed as follows. Scalability - Figure 6 shows that the average transmissions per node per second grow linearly for the basic, and sublinearly for the dAOI model. However, transmissions level off if
Voronoi diagram is a mathematical construct such that given n nodes on a 2-D plane; these n nodes can partition the plane into n non-overlapping Voronoi regions REF .
VON: a scalable peer-to-peer network for virtual environments
IEEE Network
IEEE Network
Computer Science