An Introduction to Distributed Virtual Environment Research

(Using Ten Quick Questions and Answers)

Graham Morgan (page created in 2005)

This page is now quite out of date in places (but I have not had time to update it). Research has moved on a bit since this was written.

When project students ask me about distributed systems research associated to distributed virtual environments I usually end up answering the following types of questions. The answers I provide here can be found in the literature (most of it from my papers) but I have found that students prefer to have a "one stop shop" with the minimum to read (just getting to the point of the matter). Therefore, I have put this page together for anyone interested in distributed virtual environment research who is new to the subject (but mainly for those project students of mine so they can ask me some more interesting questions in the future).

  1. Why do distributed virtual environment (DVE) research?
  2. What is a DVE and what is the main research challenge?
  3. Can you give a few hints of what to Google to find out about DVE research?
  4. What is the consistency-throughput tradeoff?
  5. What does scalability mean in a DVE and why is it difficult to achieve?
  6. How can we try to make a DVE scalable?
  7. What types of interest management are there?
  8. What is the missed interaction problem?
  9. How is the missed interaction problem reflected in region and aura based interest management schemes?
  10. Are there any other challenges apart from the consistency and real-time ones?

 

1. Why do distributed virtual environment research?

·        Distributed virtual environment (DVE) research at Newcastle has been ongoing for the last few years (since 2001) and has focused on the distributed systems type challenges. My background is in distributed systems (e.g., fault-tolerance, group communication protocols, middleware technologies) and my initial intention was to see if techniques from distributed systems research could aid DVE research. The reason for this was that as I read DVE literature I made two observations: (i) the majority of academic research had been derived from a number of  non-distributed systems type research groups, such as computer supported collaborative work (CSCW), human computer interaction (HCI), virtual reality (VR), and graphics; (ii)  for some reason all aspects of DVE research had become  "unpopular" in that little was been published on the subject anymore and many researchers seemed to have "moved off" into other domains. The main issue I could see was that although there was quite substantial middleware technologies (from around twenty years of distributed systems research) available for distributed application developers to use (much of it open source), such technologies did not appear to have been incorporated into DVEs. For example, I fully expected to be able to download some open source server side solution for node clustering to allow quick development of scalable server based virtual worlds (in the same way I would build an auction site for example). Needless to say, I couldn't. However, with recent commercialisation of online games the need for DVEs and associated development technologies is growing. (it really is an interesting problem area).

2. What is a DVE and what is the main research challenge?

·        DVE - Defined as a computer simulation subject to user manipulation in real-time that is presented via multimedia technologies (e.g., graphics, sound) to more than one user at the same time.

·        Research Challenge - To provide services with qualities that ensure users share a mutually consistent view of a virtual world while enabling users to interact with each other in real-time.

3. Can you give a few hints of what to Google to find out about DVE research?

·        Michael Zyda (USA) is a recognised pioneer in this field, there are others, but Michael is probably the most prominent person in the field. Worked on early DVEs related to military simulations in the USA. If you want to know about DVE research a must read text for beginners is his book "Networked Virtual Environments - Design and Implementation".

·        Steve Benford and Chris Greenhalgh (UK) wrote many papers related to DVEs in the mid to late 90s. Chris's PhD Thesis won an award for his work in this area and was published in 1999 ("Large Scale Collaborative Virtual Environments").

·        DIVE is one of the best supported academic implementations of a distributed virtual environment. An early paper provides a good insight into DIVE (although it has been an ongoing work for many years now): Carlsson and Hagsand, "DIVE - A Multi User Virtual Reality System", IEEE VRAIS, Sept, 1993

·        Other academic work? Well there are many: try Googling the following to find out about them (add virtual environment for a more narrower search): SIMNET, NPSNET, SPLINE, RING, MASSIVE, PARADISE, BrickNet, NetEffect,VNet, Mercury, ATLAS, MOVE.

·        What about commercial games? Well Doom was one of the first to provide networking support, but there are many more now: Quake, Unreal Tournament, Diablo, Ultima, Everquest, Star Wars Galaxies.

4. What is the consistency-throughput tradeoff?

·        This is an interesting, but quite obvious (when you think about it), side effect reflected in user interaction because of network delays and processing overheads (Michael Zyda and Co. coined the phrase). In fact, this makes satisfying the research challenge of "consistency between users" difficult in a DVE. Here is a quick example that will explain what it is:

·        The consistency-throughput tradeoff may be described via an example involving two virtual world objects, say Obja and Objb. Obja is at position (15, 15) in a two dimensional virtual world and sends a message to Objb describing its coordinates. Due to message latency Obja has reached (20, 15) by the time Objb receives Obja’s message. Objb will have an out of date view of Obja’s position: consistency is reduced, but the world is dynamic and responsive (object movement is unrestricted). To improve consistency we may stop Obja from moving until we are sure all objects view Obja’s position as (15, 15). This can be done via the use of agreement protocols or a shared, transactional, central database that maintains virtual world state. These approaches incur processing overheads that lead to delays in the virtual world simulation, reducing throughput and making simulations less responsive. This is not acceptable for real-time simulations; therefore inconsistency is present to some degree.

5. What does scalability mean in a DVE and why is it difficult to achieve?

·        Providing DVEs that may scale to support many hundreds and thousands of users while satisfying real-time (responsive virtual worlds) and consistency (participants view mutually consistent events) is a significant research challenge. The quality of service associated with the underlying messaging middleware (e.g., latency, jitter, message loss) coupled with finite processing resources make ensuring all participants in a virtual world view events in a mutually consistent way difficult. In addition, as message exchange is the only way to propagate events to geographically dispersed users care must be taken to prevent exhaustion of bandwidth and available processing resources when managing message exchange.

6. How can we try to make a DVE scalable?

  • Interest management is an accepted approach to achieving scalability in a DVE: freeing up bandwidth and processing resources via targeted message passing (not broadcast) ensuring messages are only sent to recipients that may be interested in them. Defined areas within a virtual world are used to restrict message passing: a message and its receivers are associated to an area of a virtual world. This approach is achieved by attributing the sending and receiving entities of a message to objects that inhabit a virtual world (i.e., objects inform each other of their actions via the exchange of messages). Areas used for restricting message passing are commonly termed areas of influence and an object is said to exert influence (send messages) to all other objects that share its area of influence.

7. What types of interest management are there?

  • Region - virtual world is divided into well defined regions that are static in nature (defined at virtual world creation time). The recipient (object) of a message is limited to only interested participants (i.e., reside within the same, or neighboring, region as the sender object). This approach is illustrated by NPSNET, where the terrain of the virtual world is divided into hexagonal cells.
  • Aura - each object is associated to an aura that defines an area of the virtual world over which an object may exert influence. An aura may be simply modelled as a sphere that shares its centre with the positional vector of the object it is associated with. An object may potentially communicate their actions only to objects that fall within their aura. This approach is illustrated by the Model, Architecture and System for Spatial Interaction in Virtual Environments projects (MASSIVE 1 & 2).

8. What is the missed interaction problem?

  • Considering the consistency-throughput tradeoff, missed interactions occur because the degree of inconsistency present in a DVE is sufficient to allow an object’s traversal of an area of influence to go undetected by an interest management scheme. Considering the example given earlier when highlighting the consistency-throughput tradeoff, it is quite conceivable that an area of influence belonging to Objb is identified as between (16, 15) and (19, 15), resulting in Obja traversing this space with no messages sent to or received by Objb (missed interaction).

9. How is the missed interaction problem reflected in region and aura based interest management schemes?

  • Region - When considering an object that represents a fighter aircraft we can see that the size of a region may be appropriately measured in kilometres. However, this size of region may not be suitable for all types of objects. For example, if region size is decided when considering the top speed of a fighter aircraft then the presence of soldiers travelling on foot may give rise to unnecessary message exchange between nodes that host foot soldier objects that are separated by a distance too great for such objects to influence each other. Furthermore, if region size is more suited to foot soldier objects then a fighter aircraft may traverse region boundaries with such frequency that region membership may not be resolved in a timely fashion. Therefore, when objects coexist within the same virtual world and can traverse the virtual world at greatly varying speeds, relying on a region based approach alone may not be appropriate.
  • Aura - If the fighter aircraft flies over the position of the foot soldier and initiates an attack on the soldier’s position then the DVE must detect when aura collision occurs and enable message exchange between the appropriate objects. The aura of the fighter aircraft object may only collide with the aura of the foot soldier object for such a small period of time that it may not be possible to resolve the appropriate object group membership in a timely fashion. A solution to this would be to extend the fighter aircraft’s aura to enable such interaction. However, extending the aura may result in the fighter aircraft potentially influencing many more objects than is necessary and may result in scalability problems as the node hosting the fighter aircraft would be required to participate in redundant message exchange with many nodes.

10. Are there any other challenges apart from the consistency and real-time ones?

Yes, there are. I know quite a few, but this is left to the reader to find out.....