We propose the research project ASCEND (Adaptive Scalable Cooperative Environment for NVE Developments) that aims to build scalable, affordable, and accessible peer-to-peer (P2P)-based 3D networked virtual environments (NVEs) where participants may share data (e.g. files, photos, blogs) and interact with one another in real-time. We will study a number of important P2P-based NVE (P2P-NVE) research issues which include: 3D streaming for P2P-NVEs, state consistency control in P2P-NVEs, persistent storage design for P2P-NVEs, and suitable P2P overlays specifically for NVE applications. ASCEND's motivation is based on three important Internet trends: the rising popularity of Massively Multiplayer Online Games (MMOGs), the scalability potential of P2P networks, and the rapid growth of user-generated contents such as blog, file and photo sharing. We hope that ASCEND may bridge the transitions toward the next level of Internet communication that is 3D-based, highly interactive, and user-empowering.

            Networked virtual environment (NVE) [Singhal and Zyda 1999] is a virtual environment in which multiple users interact with each other in real-time via network connections, even though they may be physically located around the globe. It can be regarded as a distributed system providing immersive multiuser experience in a shared syntactic world. Users situated at different physical locations may meet and interact through 3D representations of themselves (called avatars). The study of NVE began with U.S Department of Defense's Simulator Networking (SIMNET) Project [Miller and Thorpe 1995] in the 1980s, and was researched and developed by DARPA, the same agency that created the Internet. NVE has since been growing steadily into diverse applications that include military training, scientific visualization, education and entertainment. Arguably the most successful subset of NVE today is what is known as Massively Multiplayer Online Games (MMOGs), where thousands to hundreds of thousands of players interact with each other simultaneously in a virtual universe. MMOG has become one of the fastest growing genres of computer games since its inception in the mid 1990's, and is now a popular form of entertainment in North America and Asia, especially among the youth. As of 2005, 4 millions paid subscribers are reported for the MMOG Lineage [Lineage 2005], made by Korean game company NCSoft, while World of Warcraft [WoW 2005], a game by U.S.-based Blizzard Entertainment, has accumulated over 2 millions subscribers within a year since its release in 2004. In some way, MMOG has become not just a multi-billion industry [IGDA 2004], but a cultural phenomenon as well, and its main attraction has gone beyond gaming to the support of social interactions. With continuing advances in CPU, broadband network, and consumer-grade 3D accelerators, it is not unreasonable to expect MMOG to become an immersive interaction medium that may develop beyond entertainment into areas such as education, training, e-commerce, and communication. We may thus be expecting the emergence and widespread use of NVE systems on the Internet in the near future.

           However, for NVEs to be truly widespread, they will need to become more scalable, affordable and accessible. Good scalability allows a single system to accommodate dynamic user size without service interruption, increasing the service-quality and immersiveness of the user experience. Affordability lowers the entry barrier in creating and hosting such systems, while accessibility indicates the ease of access of such systems to the ordinary computer user. The ideal scenario is that NVEs may become scalable to millions of concurrent users and accessible to the general public, yet affordable enough for individuals to create and host. Indeed, a great example is the development of WWW, whose rapid rise of popularity can be traced to its scalability, affordability, and accessibility.

            We can only imagine the impact when NVEs become as popular and widespread as today's WWW. Yet various indicators and hardware trends show that a 3D-based, interactive Internet experience is realizable in the foreseeable future. For example, Microsoft's next OS Windows Vista [MS 2005] contains a 3D interface, 2004 Turing Award winner and Xerox PARC founder Alan Kay has also been leading the research of a distributed 3D Operating System called Croquet since 2000 [Croquet 2005].

            Existing server-based NVE architectures have inherent scalability limits and are expensive to deploy or maintain [Hu et al. 2006]. While over 150,000 concurrent users have been reported for a single MMOG, the infrastructure cost of scaling user size into the range of millions might become unbearably expensive, without even considering the design and maintenance difficulties. A promising alternative is the peer-to-peer (P2P) architecture that has become well-publicized with file-sharing applications such as Napster, Gnutella, Kazza, eDonkey, and VoIP application such as Skype. P2P networks promise high scalability and affordability by self-organizing individual computer nodes into a collective platform where resources (i.e. processing power and bandwidth) are shared. P2P-based NVE systems may also be seen as a distributed systems with self-stabilizing properties, which makes them an interesting topic to study. However, issues such as consistency, persistency, and security will need to be reconsidered when NVEs are adopted to P2P architectures.

            The current model of NVE content distribution, which requires users to pre-install proprietary software clients and large amount (hundreds to thousands of megabytes) of content data, also makes the use of NVE inconvenient and inaccessible to the general public. From the experience of WWW, we may infer that for NVE systems to be universally adopted, their contents  (e.g. static data such as 3D meshes and textures, or transient data such as user commands or voice chats) will need to be delivered in real-time to users quickly and efficiently using just a single client software with standardized data formats and transmission protocols.

            A number of P2P-based NVE research have been proposed in the last three years, mainly addressing the basic question of constructing a P2P overlay. Among existing approaches [Keller and Simon 2003; Knutsson et al. 2004; Kawahara et al. 2004; Hu and Liao 2004], Voronoi-based Overlay Network (VON) [Hu et al. 2006] appears to be very promising, with demonstrated scalability, topology consistency, and simplicity. ASCEND aims for a comprehensive study on various issues related to viable NVEs based on VON. General NVE design criteria such as consistency, responsiveness, scalability, reliability, and persistency will be thoroughly studied via specific research topics described in the next section. The main goal of ASCEND is to derive better understandings on how to design NVE systems using the P2P paradigm. Specifically, we seek to study how 3D contents may be delivered effectively on P2P overlays (i.e. 3D streaming on P2P networks), and how persistent data and consistency control may be maintained. Secondary goals include the implementation of a prototype P2P-based NVE system for educational use and a related set of open source programming libraries (the ASCEND library). We note that security is also a very important and relevant issue to many NVE systems, however, as it can be highly application-specific (i.e. solutions likely will not be general), yet at the same time, NVE systems without strict security functionalities may still gain wide appeal (e.g. for distance-learning, simulation, or promotion purposes), we will leave security issues as future research topics.

            In some sense, the main relevance of ASCEND is the understanding and development of the next level of Internet communication beyond World-wide Web. While WWW has been an amazing medium for the capture, sharing, and access of information, it is a flat and asynchronous medium that does not effectively enable, capture, or deliver the real-time interactions among people. Yet real-time interactions of various forms are at the heart of human societies and activities. Evidences are abundant in the popularity and growth of today's mobile phones, instant messaging, and MMOG applications. With continuing hardware trends in CPU, broadband, and 3D acceleration, as well as the growing amount of interests, tools, and industries related to both the creation and consumption of 3D contents (e.g. Computer-aided designs (CAD), TV commercials, computer-synthesized movies, and MMOG), the time is approaching for various 3D-based real-time interactive environments to emerge on the Internet. We believe that the emergence of potentially millions of interactive virtual worlds is a matter of time, not viability. These virtual worlds will likely create dramatic impacts on the ways we learn, work, and socialize. Yet the widespread and adoption of virtual environments will require viable architectures that are both scalable and affordable, hence the goal of ASCEND: to study the main architectural issues involved in constructing P2P-based NVE systems that are highly scalable yet affordable and accessible.

            From a more practical perspective, fundamental understandings in constructing viable P2P-based NVE systems will allow us to speed up the developments and deployments of such systems, creating opportunities for NVE to be applied in promising new areas such as education, training, and social interactions -- fields which so far cannot afford the large budgets to develop and deploy NVE-based solutions as well as the game industry.

Related Work in P2P-based NVE

            The main issue in P2P-based NVE is how the entire virtual world may be maintained in a distributed fashion by various participating nodes through connections with only a limited set of neighbors (i.e. how a P2P topology can be maintained through certain node connection patterns). In contrast to file-sharing P2P, where content search is the main problem and can be difficult (as a desired content may be located anywhere on the network), the desired content in P2P-based NVE is simply the event messages generated by each node's nearby neighbor within its visibility (i.e. an area of interest, or AOI, see Figure 1). The general content discovery problem in P2P thus transforms to a neighbor discovery problem in the context of P2P-based NVE. Three main approaches have been proposed to deal with the neighbor discovery problem: Distributed Hash Table (DHT)-based, neighbor-list exchange, and mutual notification.

Figure 1. Abstraction of a NVE. Participating users may be represented as nodes (the dots). The circle is the area of interest (AOI) of the center node.

            SimMud [Knutsson 2004] is representative of the DHT-based approach, where the entire virtual world is sub-divided into fixed-size regions, each managed by a super-node. Super-nodes maintain contacts with one another through the use of DHT. DHT-based approaches, however, face the problem of high latency due to message relay, thus may not fulfill the real-time requirement of NVE. Fixed-size regions also cannot handle situations when many users have crowded into the same region, potentially slowing down or overloading the responsible super-nodes.

            The second approach (i.e. neighbor-list exchange) requires each node in the P2P network to maintain a fixed number of nearby neighbors (in terms of distance within the virtual environment), and exchange the “neighbor-lists” regularly so that new neighbors can be learned. However, much of the exchange contains redundant information, as neighbor-relationships do not change rapidly. A more serious issue is that simulations have shown that the P2P overlay may partition into mutually unaware parts after some time, as the clustering of nodes may make connecting only to nearest neighbors inadequate in keeping the topology globally connected.

            The third approach (i.e. mutual notification) also requires each node to maintain a certain number of neighbors, but neighbor discovery is done in a more message-efficient manner through collaborative notifications between connected nodes. New neighbors are learned from notification messages only when the appropriate situation occurs. As no fixed region is defined and no super-nodes are used, proposals in this category may handle user crowding better than DHT-based approaches. Solipsis [Keller and Simon 2003] and VON [Hu et al. 2006] are the two main proposals, and differ mainly in the types of neighboring nodes to maintain. Solipsis requires each node to be within the outermost boundary of connected neighbors (i.e. within a convex-hull formed by the neighbors, see Figure 2), while VON requires all nodes to maintain at least the enclosing neighbors as defined by a Voronoi diagram of connected neighbors (Figure 3). Under certain circumstances, Solipsis may not discover neighbors properly and the topology will need to be fixed by a time-consuming query process, while VON does not have these issues. Simulation also shows that topology can be maintained quite consistently with VON [Hu et al. 2006]. We therefore choose to base this research project on the continuing studies and development of VON as it has shown to maintain consistent P2P topology in a bandwidth-efficient manner, which are crucial for true scalability in practical applications.

Research Topics

            In this section, we will outline the main research topics in ASCEND as carried out in three years, explain the main problems involved, and some directions towards potential solutions. The major research topics in each year are:

            First Year:      3D Streaming for P2P-NVEs

Second Year:  State Consistency Control in P2P-NVEs

            Third Year:     Persistent Storage Design for P2P-NVEs

            Each year will have one major research theme, and the choices of these themes are based on what we consider as the major unresolved issues regarding P2P-based NVE designs. The first year topic of 3D streaming for P2P-NVEs is based on previously published works of Voronoi-based Overlay Network (VON) [Hu et al. 2006], and is more or less independent from the next two year's research topics. The second year's topic of distributed state consistency will lay the foundation for the third year's study on persistent storage design. There are six major issues in the development of a NVE system, namely: consistency, responsiveness, scalability, reliability, persistency, and security [Hu 2005]. As VON has shown to possess good scalability and responsiveness [Hu et al. 2006], we intend to investigate the remaining issues of consistency, reliability, and persistency of a VON-based P2P-NVE. However, as stated earlier in our goals, although security is also an important issue, its solutions tend to be application-specific and less general. Security issues will thus be left as future work. The details of each year are described below:

First Year: 3D Streaming for P2P-NVEs

            To allow NVE to become as easily and conveniently accessible as the WWW today, one crucial requirement is that relevant 3D contents for navigation must be obtainable in real-time. However, 3D data (i.e. geometric meshes and graphical textures) are typically large in size, which can easily reach over to hundreds of megabytes for an application, effective real-time transfer of 3D contents through streaming techniques thus might be needed. 3D streaming involves two major tasks: the selection of relevant data as determined by the user's viewpoint (i.e. object selection), and efficient transfer of the content (i.e. object transmission) [Sahm et al. 2004]. For the first task, server-side visibility determination methods are generally used, while efficient representation and compression of 3D objects, as well as progressive transmission methods, are usually utilized for the second task.

            The major pending issues, however, are the scalability of the system in terms of the number of concurrent users, and the amount of download time (i.e. delay) experienced by each user. As each user request will add a certain amount of processing and bandwidth burden to the server, scalability may be limited. On the other hand, a single source (i.e. the server) of 3D content also sets an upper limit to the bandwidth and latency of a given transmission.

            3D streaming is inherently a processing and bandwidth intensive operation, we thus believe that for 3D streaming to be usefully adopted by large number of users, a new paradigm for data transfer is likely needed. Recent studies in using P2P to support networked virtual environments (P2P-NVE) might be utilized to support 3D streaming as well, and we plan to investigate how 3D streaming might be supported on top of Voronoi-based Overlay Network (VON) [Hu et al. 2006], as it has been demonstrated to possess good scalability, consistency, and reliability among existing P2P-NVE proposals.

            Our initial proposal is to divide an NVE into fixed-size cells, each of which contains a scene description, which is simply summary information of the 3D objects whose location points (i.e. a representation point coordinate of the object) lie within the cell (Figure 4). As each node can independently calculate which cells its AOI overlaps given the dimensions of the NVE and cell size, a node's visibility may be determined without server intervention, solving the first issue of object selection. Once a node learns of which 3D objects it needs to download, it may send out requests to other user nodes within its AOI (i.e. the AOI neighbors), which can be learned through VON. We assume that the data of each 3D object can be decomposed into a base piece and many refinement pieces, 3D data will thus be obtained through requests to a pool of potential data sources that include the AOI neighbor and the server (as a final data source). This will solve the second issue of object transmission in a more distributed manner, as AOI neighbors likely already possess the data pieces of interest, we can effectively alleviate the server's load by sending requests to them first.

Figure 4: Schematic diagram of a NVE divided into cells. The big circle indicates the AOI of the center node (star) and triangles are other user nodes. Rectangular or irregular shapes are the 3D objects in the NVE, with dots indicating their location points. Note that cell numbers can be deterministically calculated from cell size and world dimensions by each node (source: [Hu 2005]).

            As we intend to support 3D streaming by using VON, we will also need to improve VON's existing delivery mechanisms. The original proposal of VON requires all nodes to maintain direct connections and mutual visibility with one another, thus it may be called the direct connection (DC) model [Hu et al. 2006]. Works are also now in progress to develop a forwarding model (FO), where all nodes connect only to their enclosing neighbors, and receive additional messages through node relays, in order to minimize bandwidth use [Chen 2005].

            While scalability has been demonstrated in the DC model, it does not take consideration or advantage of the various bandwidth capacities of different nodes. For example, nodes with more bandwidth and processing power should be able to have larger visibilities in the NVE if the users desire, or be used to help relay and process messages for the less powerful nodes. On the other hand, a pure FO model of VON will have latency not suitable for many NVE applications. A hybrid approach that combines the DC and FO models of VON in an adaptive way, in order to take full advantage of the heterogeneity of the P2P network thus is an important direction if practical VON-based NVE systems were to be built.

Second Year: State Consistency Control in P2P-NVEs

            Although consistency has been studied extensively in parallel and distributed systems, many approaches may need to be re-adopted and re-investigated for NVE applications, due to the real-time, responsive requirements of NVE systems (i.e. message complexity and latency need to be minimized in order to allow smooth and responsive human interactions) [Zhou et al. 2002]. Consistency takes a myriad of meanings in various contexts, however, in NVE there are mainly two types of consistency to consider: state consistency and event consistency. State consistency refers to whether different users share the same sets of object states (i.e. information about an object) within the NVE (e.g. whether we both see that a glass of water is full), while event consistency refers to whether the users experience event occurrences in the same order. In order to synchronize object states and event ordering, messages need to be sent between each participating nodes of a NVE. However, message transmissions face the issues of latency, jitter (i.e. variance in latency) and packet loss, which in turn can cause asynchrony (i.e. event or state changes are processed at a later time than their actual occurrences due to latency), mis-ordering (i.e. different nodes may receive event messages in different orders due to jitter), and mis-information (i.e. remote nodes are not aware of the occurrence of events due to packet loss or corruption), making consistency maintenance a challenging issue.

            In today's MMOG, consistency is maintained via the server by keeping an authoritative central repository of object states and a total ordering of all event messages. All clients must follow and synchronize with the server's version of states and events. This solution is simple and an authoritative server is seen by many as the natural way to maintain consistent event records. However, when adopting NVE to a P2P environment, such centralized event records may not exist, the challenge for distributed state consistency is therefore to avoid asynchrony, mis-ordering and mis-information in a distributed fashion.

            Current view held by MMOG developers is that server-based consistency control is the only viable method. However, as consistency maintenances rely on message delivery, which in turn is strongly influenced by latency, higher latency likely will make event synchronizations at various nodes more problematic. Yet, server-based architecture necessarily require two end-to-end hops for messages to travel from the originating node to the destination nodes (via server relay), causing longer latency than if messages were to transmit directly (i.e. only one end-to-end hop) as in a P2P-based system. An interesting research topic thus is to investigate if P2P-based NVE can actually achieve better consistency than server-based approach due to smaller latency.

            For state consistency, we plan to assign each node (i.e. a user's computer) in the P2P network to maintain the states of its nearby objects within the virtual environment. Whenever updates are sent to update the object states, these object owners would then be the authoritative node in determining the true values of object states. The reason of having object owner is to avoid concurrent updates of the same object state by two different nodes, resulting in potentially illogical operations (e.g. both users are able to drink up a glass of water). Additionally, to allow efficient load balancing in the state maintenances, it is best if ownership assignments are done dynamically.

            Our initial proposal is to assume that every object state within an NVE is associated with a coordinate; we can thus designate the maintenances of its states to the node closest to it (i.e. the node whose Voronoi region contains the object's coordinate, see Figure 5). Whenever a node wishes to update the state of an object (e.g. a user wishes to close a door with his magic spell), it would send out an update request to the object's owner (i.e. the node whose Voronoi region covers the object). However, as nodes may know the coordinates of their neighbors in a slightly different manner (due to the latency in position update messages), different nodes may have different understanding as to which node is the actual owner. Update requests will thus be sent not just to the object's owner, but also to the owner's enclosing neighbors (which are the surrounding nodes sharing an edge with a particular node, indicated by the stars in Figure 5). The enclosing neighbors would then send their agree or disagree vote to the supposed object owner, and only the node that receives a majority vote will then proceed with processing the request, and propagates the result of the update to other interested nodes (i.e. nodes that could see the object).

Figure 5: Object ownership determination using enclosing neighbors voting. Squares indicate objects, stars indicate enclosing neighbors (EN) of the center node.

            The approach just described, however, will introduce an ownership transfer problem, as user nodes are constantly moving, and their nearby objects are also constantly changing. How to balance between distributing the object maintenance load and the distribution overhead (i.e. ownership transfer) efficiently and correctly thus will become one of our main research issues.

            For event consistency, we plan to investigate certain distributed synchronization methods such as bucket synchronization [Diot and Gautier 1999] and critical causality [Zhou et al. 2002] to see their suitability on P2P networks and whether better approaches may be adopted. Bucket synchronization is a technique where each node in a distributed system maintains certain time buckets of a fixed period (e.g. 100 ms), and event messages are put into respective buckets according to their time-stamps (i.e. a mark in the logical time) once received. By queuing event messages without immediately executing them, each node will be able to preserve better event ordering according to the time stamps of event messages. Critical causality is based on the observation that not all events need to be properly ordered, but only those that are casually related (i.e. an event B is caused by event A). Each node thus attaches to the event message it sends out with a previously received message that triggers the local event. This way, if an event is triggered by another remote event, the receiving node will not miss the triggering event due to packet loss of the previous triggering event. We will investigate how bucket synchronization may be combined with the concept of critical causality to achieve proper event ordering in a message-efficient way.

            Another issue related with consistency is the reliability of the P2P network's topology. Packet loss and node failures can potentially destroy the topology consistency of the P2P overlay. It is thus crucial that a P2P overlay is designed to handle such situations in order to prevent overlay partition [Kawahara et al. 2004]. While existing P2P-based NVE proposals have more or less some mechanisms to tolerate packet loss and node failures, no empirical studies has yet been done to compare the various proposals. On the other hand, general mechanism to handle node failures still would not prevent overlay partition when massive number of nodes fail simultaneously (which is true in other types of P2P system as well, including DHT [Stoica et al. 2001]), mechanisms to recover from overlay partition thus is also an important topic.

            Potential solutions may be found from existing proposals such as checking back with a centralized server periodically (e.g. “random introduction” [Kawahara et al. 2004]). However, trade-off between the ease of centralized mechanisms and the scalability of distributed mechanisms must be carefully investigated and weighted. Another potential path of investigation is to identify “critical nodes” whose failures might create overlay partition. If correct and efficient mechanisms may be developed to identify and subsequently enhance the availability or reliability of these “critical nodes”, we might be able to reduce the probability of overlay partitions.

Third Year: Persistent Storage Design for P2P-NVEs

            To provide a sense of realism and immersion, current MMOGs often operate 24 hours a day throughout the year except for scheduled server maintenance, so that users can login and experience the world at any time, while keeping the same user status (e.g. position in the virtual world, virtual item possessions, health and experience points, etc.). Ideally, a P2P-based NVE system should also be able to store persistent content (i.e. user stats or information about the virtual worlds) even as users come and go. However, persistent data in server-based MMOG is handled through storage in server-side databases, which would not be available in a true fully-distributed P2P environment. Persistent data storage in a P2P environment thus is challenging where issues such as data replication, migration, recovery, consistency, and security need to be considered in order to ultimately ensure data availability despite of constant joining and departure of nodes.

            We acknowledge that there have already been extensive studies on various aspects of P2P-based storage systems [Kubiatowicz et al. 2000; Clarke et al. 2000; Hansen 2002; Zheng et al. 2004]. The approach of our study thus is to survey and adopt existing solutions that would be suitable for the unique characteristics of P2P-based NVE systems. We expect that the optimal persistent storage for P2P-based NVE and other types of P2P systems may differ as relevant content to a particular node is usually localized and may be found at the neighboring nodes. Consistency or security requirements may also be more relaxed for certain types of data than in generalized P2P-based storage systems. Specifically, we intend to devise solutions to support scalable P2P storage using only a light-weight server (LWS) for data backup, as our project goal is to provide scalable yet affordable P2P-based NVE designs where systems with various scale and budget may all be supported.

            Under the assumption that a certain percentage of nodes are always online, persistency in a NVE may be achieved with enough data (i.e. object states) replications. However, as no single user node is permanently reliable, eventually we will need to rely on the server for object state maintenances. Yet, if all data updates were to be synchronized back to the server without a scheduling mechanism, the server may become overloaded. Our proposed study therefore focuses on how the server may collect updated object states from all the participating nodes in a scalable, controlled manner, while potentially utilizing client-side data aggregation and compression techniques to facilitate the message and time efficiency of such data collection.

    An example of such data collection can be found in the crawling of search engines, which attempts to find updated information on large number of web servers through scheduled visits of each site.  Bandwidth efficiency and the discovery latency however are the main problems.

Figure 6: Design for a light-weight server (LWS)-based persistent storage. (Step 0) Clients connect to a LWS first to discover an initial set of AOI neighbors (Step 1) Leader node is elected locally (Step 2) Whenever states are updated, such as Node A or Node B in the figure, updates are propagated to the leader node. (Step 3) The leader node notifies the server that new states are ready for backup. (Step 4) The server retrieves aggregated and compressed updates from the leader node according to its schedule.

            Our initial proposal involves the election of leader nodes, which are responsible to collect state updates from neighboring nodes and synchronize the updates with the server. Meanwhile, any state update will trigger a version-update flag to the light weight server to notify for scheduling data-retrieval at a later time convenient to the server. In our design, a light weight server is assumed to be reliable and persistent, and acts as the first contact point of entering into the P2P-NVE, as well as the initial source for all object states (Figure 6).

            Some potential problems to be addressed are the selection of leader nodes, as well as up-to-date data aggregation from peers, and we discuss certain existing approaches which we might adopt below:

Leader nodes election

            Leader nodes are important elements in our approach, since they provide the ability for light-weight servers to retrieve the most up-to-date data. However, leader nodes are prone to failure if excessive bandwidth is consumed. Our concept of leader nodes is similar to [Su and Lee 2004], who proposes a gateway nodes recovery approach, which is fully distributed and allows for surviving gateway nodes to recover other gateway nodes that have failed. [Basagni et al. 2004] proposes the generation of a clusterhead via the DCA algorithm, which is based on a generic "weight" attribute associated to each node. Each Wireless Sensor Network (WSN) node in LEACH [Handy et al. 2002.] rotates to be cluster-head to ensure fairness. In the same way, we could rotate nodes in a VON-based NVE as leader nodes. The popular peer-to-peer file sharing system Kazaa [Kazaa] implements supernodes that have strong processing and bandwidth capacities. Regular peers connect to a certain supernodes which act as their local servers. [Lo et al. 2005] define the supernode selection problem, which has emerged across a variety of P2P applications. Supernode selection involves the selection of a subset of the peers to serve a special role as leaders. The supernodes must be well-dispersed throughout the P2P overlay network to balance the load.

Data Aggregation

            Aggregation has been discussed in different contexts such as large scale databases [Gray et al. 1997], active networks [Raz and Shavitt 2002], and wireless sensor network applications [Intanagonwiwat et al. 2000; Madden, Szewczyk et al. 2002; Madden, Franklin et al. 2002]. In network aggregation schemes such as Astrolabe [Renesse et al. 2003] and TAG [Madden, Franklin et al. 2002], hierarchical aggregation in the network is performed to reduce bandwidth consumption and achieve better load-balancing. TAG simplifies aggregation without the SQL clauses Group By or Having while Astrolabe aggregates data in large distributed systems hierarchically. A related work also based on a hierarchical approach is [Gupta et al. 2001]. While building hierarchies indeed reduces the cost of finding the aggregates, it introduces additional overhead in maintaining this hierarchical topology within a dynamic and distributed environment. Moreover, due to the hierarchical organization, extra efforts and protocols are needed to broadcast the result continuously for all nodes to know. In gossip-based aggregation [Montresor et al. 2004], the state of a node is a numeric value. In a practical setting, this value can be any attribute of the environment, such as the load or the storage capacity. The task of the protocol is to calculate an aggregate value over the set of all numbers stored at nodes. As long as the overlay network remains connected, link failures do not affect the final value, but only slow down the aggregation process. [Li et al. 2005] design a algorithm for aggregation over existing DHTs. It builds an aggregation tree in a bottom-up manner by mapping nodes to their parents in the tree with a predefined parent function. [Müller 2005] proposes a process to aggregate player’s information to a two-dimensional histogram for MMOG. The aggregation performs on a dynamic Delaunay triangulation network with compass routing in a grouped NVE.

            Another goal in the third year is to integrate the research results of P2P-based 3D streaming, consistency control and persistent storage into a coherent set of interrelated programming libraries so that P2P-based NVE applications may be developed and supported with minimal redundant efforts. We will apply these novel techniques to build a NVE environment in collaboration with other researchers in the fields of learning and education, so that practical issues in the development and deployment of P2P-based NVE systems may be discovered and studied.

            In summary, each of the three years will have major and minor research issues, which are listed below:

Expected Results

            The complete execution of the ASCEND project will bring three research contributions: 1) a validated 3D streaming mechanism using P2P networks 2) a consistency control mechanism that ensures both the topology and event consistency in a P2P environment 3) a light-weight server-based P2P storage system designed for NVE applications. Specific milestones for each year are described below:

First Year

            In the first year, we expect to have done thorough surveys in related fields and created three main proposals regarding the adoption of 3D streaming on P2P networks. The milestones are:

• Parallel streaming mechanisms of 3D contents (meshes and textures) on a P2P network

• A fully-distributed visibility determination method

• An enhanced VON that combines direct and relayed message transmissions

Second Year

            The second year will mainly focus on the state and event consistency control for P2P-based NVE. Evaluation and validation of proposed solutions will also be carried out. The milestones are:

• Distributed consistency control mechanisms that ensure proper event ordering
• Ownership transfer mechanisms for object states in P2P environment

• Overlay partition recovery mechanism and reliability simulations of VON

Third Year

            The goal of the third year is a distributed P2P data storage for NVE applications utilizing only a light-weight server, and the application of the research results in the first two years into an actual P2P-based NVE application, likely for education and e-learning purposes. Most of the components in the ASCEND library will be ready, which include components for 3D streaming, consistency control, and persistent storage support. Efforts will also be spent to transfer the implementation to the open source community for the continuing development and maintenances of the library. The milestones are:

• Scalable and distributed backup techniques utilizing only a light-weight server.

• Data availability mechanism exploiting the locality of user interests
• A prototype P2P-based NVE system for educational purpose

            P2P-based network virtual environment is an emerging field that likely will become an important application domain for P2P systems, as indicated by the emergence of MMOG, P2P file-sharing, and hardware trends in CPU, broadband, and consumer-level 3D acceleration. The ASCEND project seeks to take on a leadership position in this exciting new research by thoroughly investigating selected major aspects related to fundamental issues in P2P-based NVE systems.

            As the output of ASCEND project will include a set of related programming libraries to support the development of P2P-based NVE systems (i.e. the ASCEND Library), throughout the three years we will also be hosting research results on the open source website SourceForge [ASCEND 2005] and engaging in community building so that the ASCEND project can continue its developments after this three year period.

            Implications of the ASCEND project will be three-fold:

1)     Increase in our understandings of how to construct practical P2P-based NVE systems with proposed solutions in related issues such as real-time 3D data delivery, persistent storage, and consistency control in a distributed P2P environment.

2)     Creation of a set of foundational open-source programming library (i.e. the ASCEND library) which will facilitate further the research, development, and adoption of P2P-based NVE systems for new domain areas such as education, training, and e-commerce.

3)     The training and development of a core team of researchers and developers who will have in-depth knowledge on various aspects of P2P-based NVE issues, as well as practical experience in the development and integration of related programming libraries. This will hopefully form the basis of a new open source based software industry specialized in the development of 3D-based virtual environments for various purposes.

            We believe that the time is approaching for a viable interactive medium to emerge on the Internet that is 3D-based, highly interactive, and user-empowering. Within a few years, adequate hardware infrastructure will mature to support such NVE systems on a large-scale, it is thus essential, even necessary, to start off research efforts now to be ahead in this important Internet application domain.

References