Distributed virtual environments and the Web:

A simple definition of a Virtual Environment (VE) is a computer-generated simulation, and the term usually implies the use of 3D computer graphics in the interface. VEs can in addition be multi-user, supporting multiple interacting users, and distributed, running on several computers connected by a network. It has become common to refer to a VE with both these additional properties as a DVE (Distributed Virtual Environment).

The World-Wide Web (WWW) can be thought of as a virtual space of documents. Although many users may be using it at once they are not aware of each other and cannot usually interact via the Web, so the Web is not multi-user in the sense used in this paper. One of the Web's strongest points is that almost anyone can run a Web server or add a document, and all you need to access a document is its URL. You can also link your document into the virtual space using URL hyperlinks. So the Web has distributed construction, but not distributed execution. Other than conceptually, there is no totality of Web documents. Even if you to try to list all the accessible URLs, the list changes as you enumerate it.

Present VE technology, such as Virtual Reality Modeling Language (VRML, 1997), treats VEs very much as 3D Web documents. VRML worlds can include content from URLs, and contain hyperlinks to other VRML worlds or any URL. VRML has its own MIME type, and is normally viewed using a Web browser plugin such as Intervista's WorldView or SGI's CosmoPlayer. This makes a VRML world appear very much like a JPEG image or Java applet from a user's perspective.

The challenge for DVEs is to maintain the Web properties of distributed construction and connectivity, while adding multi-user interaction and distributed execution. Successful solutions have the potential to change the Web itself, taking it in the direction of the global cyberspace dreamt of by many (Gelernter 1991, Krueger 1991).

The Openness property perhaps needs more discussion. In a typical VE, it is assumed that behaviour is essentially internal, under the control of the VE implementation. In many of our applications we have VEs that are reacting to external events, and sometimes controlling them through the generation of external events, and we believe this should be explicitly supported. This property also supports the composability of VEs.

Engineering a DVE is not easy. One has to attempt to maintain consistency of state across the DVE, keep latency within bounds making interaction possible, and use the minimum amount of bandwidth. Trade-offs obviously have to be made. A common approach is to sacrifice exact consistency at all times in favour of approximate consistency. This can improve latency and reduce bandwidth. Another common technique is to subdivide the environment into zones, pieces that can be treated more-or-less independently (Barrus et al., 1996).

Other work

The first large-scale DVE was the military simulation system SIMNET (Calvin et al., 1993) which networked various simulators (mainly tanks) using dedicated networks. The success of SIMNET triggered a standards push in the form of Distributed Interactive Simulation (DIS — DIS, 1995). In spite of its success, problems with DIS, such as its limited scalability and the rigidity caused by embedding its application in its architecture, have made the military community feel the need to move on. To support its wider goals for modelling and simulation, the US Department of Defense recently started the High-Level Architecture [HLA] initiative, to define an open framework for the interoperability of heterogeneous simulations (DMSO, 1997).

Some other systems worthy of note are DIVE (Distributed Interactive Virtual Environment) from the Swedish Institute of Computer Science (Carlsson and Hagsand, 1993), Spline from Mitsubishi Electric Research Laboratories (Waters et al., 1997a), AVIARY (Snowdon, 1995) and USS (Universal Simulation System — Hawkes, 1996). Both DIVE and AVIARY utilise a layered approach to DVE support, DIVE being originally based on ISIS (Birman et al., 1987) and Spline on its own Interactive Sharing Transfer Protocol (Waters et al., 1997b). AVIARY and USS concern themselves more with the distribution of data and computation in a heterogeneous network.

2. Architecture

Our approach is to base the DVE architecture on the communication protocols needed for DVEs. This is because we want our DVEs to be able to work on the Internet, and because protocols are the starting point for interoperability.

Our implementation of DVE support follows a layered architecture. The lowest level is the Keryx Notification System (KNS) which we use as our communications medium. Above that we have generic support for state sharing provided by an event interface implemented by an Event Distributor extension. The top layer is specific support for DVE zones. The following sections describe these layers in more detail, starting with the lowest layer.

2.1. Keryx Notification System

We only have space to give a summary of KNS here, more detail can be found on the Keryx Web site [KERYX], which also contains a downloadable Java implementation of the Keryx system.

KNS supports anonymous interactions between loosely coupled parties. While a distributed object model typically assumes direct coupling between interacting parties, the notification service routes messages between parties based on their content. The producer of a notification does not have to know who the receivers are, or how many there are, and the receiver of a notification does not have to know where it came from. We think of the notification service as a cloud of events. Sources inject events into the cloud, and the notification service takes care of delivering them to clients. The internal structure of the cloud is of no concern to clients. Other event-oriented notification systems include TIBCO's The Information Bus [TIBCO] and the recent submission to the Object Management Group's RFP for notification services (BEA Systems et al., 1998).

A notification can be thought of as signalling the occurrence of some event. The notification contains information about the event in a structured and self-describing format. We often use the terms event and notification interchangeably.

Keryx events are encoded in SDR (Self-Describing Data Representation, Low et al., 1997), a textual syntax for structured data. A Keryx event is an SDR map, an unordered list of field name and value pairs. Values in the map may themselves be maps, lists or unstructured data such as numbers, strings. SDR supports flexible quoting making it straightforward to encapsulate strings containing data with its own syntax, such as VRML, without extensive processing. Counted binary data can also be used. Although KNS is implemented in Java, the simplicity of the SDR format for events makes it a simple matter to send and receive events from other languages. We have used Scheme, C/C++, and Perl as well as Java applets in our research.

Clients of the notification system are decoupled by Event Distributors (ED). Sources send events to an ED which delivers them to clients. An ED also provides services, by recognising some events as directed to its own event interfaces and processing them specially. Other events are treated transparently by an ED. In addition, the basic functionality of an ED may be extended by modifying its internal event handling and introducing new event interfaces at load-time. Event Distributors can be connected together to provide wide-area distribution of events and scale the capacity of the notification system. Keryx events are often transported over TCP/IP, but a reliable transport built on top of UDP is also available, among others.

Some DVEs use IP multicast as a group communication mechanism. There are problems with this, such as the low penetration of IP multicast. IP multicast is also a datagram service, and so has no delivery guarantees. Reliable IP multicast is an active research area (Floyd et al., 1995, [RMP]). Wide area event distribution can be seen as simulated multicast. However, EDs can use multicast itself where appropriate. In some ways, event filtering makes event distribution more powerful than IP multicast (see Section 3.3).

Among the events recognised by an ED are subscriptions, which a client sends to request delivery of events they are interested in. A subscription defines the events of interest to a client by including a filter, a predicate over events. Only events that pass some subscription's filter will be delivered to a client.

An event source simply connects to an ED and sends an event with the content it wishes distributed. The ED then delivers the event to all clients having matching subscriptions. An event sender does not need to know who the receivers are, nor does an event receiver need to know who the senders are. As long as an event satisfies a client's subscription it is delivered, and the presence of data not examined by the filters has no effect on delivery. This means that fields can be added to events without disturbing existing clients. This can be useful when evolving an existing system, such as a VE.

3. DVE Support

We believe that DVEs must be open. By this we mean that they must essentially be defined in terms of the protocols they use, and that there should be no artificial barriers obstructing the implementation of those protocols. It should be possible to build a seamless DVE out of pieces having diverse implementations. We also believe that DVEs should be open in the sense of being able to interwork with external, and legacy, applications. It is in order to satisfy these openness requirements that we use KNS as our transport for DVE protocols. In addition we find its properties match DVE requirements well. KNS supports group interactions, it has no bias towards graphical data, and scales to many parties.

We imagine a DVE being constructed of zones. A zone represents a collection of information of interest to participants in the DVE. Zones need not be defined spatially, but this is one obvious use for them, as in MERL's Spline system (Waters et al., 1997a, [MEITCA]). Each zone has an Event Distributor acting as the coordination point for its events, with the whole DVE being a network of these. Each ED coordinating a zone runs a zone server extension to implement the zone-specific functionality.

A zone server implements a generic state-sharing protocol using events. There are events for initial object creation, differential state update, complete state update, object deletion, operations on objects, and they are also used to manage participation in zones. Events for all zones have the same content type, and are disambiguated by their zone id field. Clients use their subscription filters to restrict their event flows to the zones they are interested in. The event distribution mechanisms do not interpret the events, and place no restrictions on the contents of updates. It is up to the object receiving an event to interpret it, whether the event is a state update or other message.

If several clients were to emit updates for a given object it would lead to intolerable inconsistency. In our Living Worlds implementation this is avoided by nominating a pilot who is responsible for updates. All clients receive updates but only the pilot sends them.

3.1. Persistence

If a client owning a persistent object disconnects, the zone server will nominate a new owner and engage in an event dialogue to make sure that ownership is transferred and no events are lost in the process. If all clients disconnect then ownership must be transferred to the zone server to ensure object persistence. Keeping objects running even when all clients have disconnected is a strong form of persistence that maintains the world dynamics. There may be some cases, however, when it may suffice simply to save the current state of the world to non-volatile storage and restart the world from the state when a client connects.

3.2. Prediction

Our event-based architecture easily accommodates the general notion of prediction derived from dead-reckoning used in DIS (DIS, 1995). In DIS a client uses the last known position and velocity of an entity to predict its current position. The entity performs the same calculation, and only emits messages updating its position and velocity when the discrepancy between the actual and predicted values exceeds some threshold, so reducing update frequency.

This technique works well for simple dynamical entities, but does not handle entities with more complex internal state. However the technique can be generalised as follows. If we have a function that can predict an entity's state from some prediction parameters we can update the prediction parameters (and the state) only when the prediction error is above some threshold, as discussed in (Roehl, 1997). This provides a general means of reducing the frequency of state update, providing a prediction function is known. Objects in a DVE will often be executing scripts determining their behaviour, and prediction is particularly effective in this case, since the object's state is completely defined by its script.

Since we are using a general state transport that is not sensitive to the contents of the state we are easily able to accommodate prediction in our DVE support. Prediction simply changes the frequency of state updates, and may add some new state parameters.

3.3. Spatial filtering

Even though zones restrict the event traffic somewhat we want to be able to further restrict traffic using spatial filters. A spatial filter includes a predicate saying that only updates with a position in a given region should be received, for example within a given radius of the client's position. This can greatly reduce update traffic. However updating the region involved in the spatial filter for a moving client could cause a lot of traffic. We envisage applying the general prediction technique to spatial filters, thus reducing filter update traffic.

Since our event filters are completely general we can filter events using any suitable criteria. This allows clients to filter out events from objects they are not interested in for any reason, not just their location.

Filters give us new ways of grouping traffic based on interest, and in the extreme can give each user their own channel within the wider event flow. This is much more general than the dynamic allocation of multicast groups based on location, as discussed in (Macedonia and Zyda, 1997).

4. VRML and Living Worlds

One of the layers we are currently developing to sit on our general DVE support is based on the Living Worlds specification for multi-user VRML worlds (LW, 1997, [LWNEWS]).

VRML is an authoring standard for three-dimensional (3D) content on the Internet (VRML, 1997, [VRMLC]). It defines a number of nodes that describe 3D geometrical objects, materials to be applied to these objects, light sources, cameras, transformations and so on. These nodes may be connected together by routes along which information, in the form of VRML events, can flow, e.g. the output of a TimeSensor node could be routed into a Transformation node to create moving geometry. In addition, the core set of nodes may be extended through the use of a native prototyping mechanism.

A reference to a VRML world can be embedded in a Hypertext Markup Language (HTML) page and is viewed by a VRML browser, often in the form of a Web browser plug-in. Uniform Resource Locators (URLs) can be embedded in a VRML world and are frequently used to reference other VRML worlds, or an HTML document. An HTML page containing embedded Java applets may interact with the VRML browser through the External Authoring Interface (EAI) and, similarly, the VRML world may interact with external entities by using Java scripts executing autonomously in the VRML browser (Fig. 1).

VRML does not, at present, address any of the issues to do with networking these worlds to enable multiple participants to interact with each other or distribute the workload associated with the simulation. This deficiency was addressed by a number of companies over the past two years, e.g. Sony and Blaxxun, resulting in proprietary, closed implementations of multi-user VRML-based systems. These systems could not interoperate and the additional VRML authoring required differed depending on which solution was used.

4.1. Architecture

These systems motivated the formation of the Living Worlds (LW) working group which produced a draft specification addressing these issues. In essence, it is another authoring standard, but this time for multi-user worlds described in VRML. A number of new nodes are introduced that are used to interface with an external application implementing the logic to handle state sharing of specific objects in the VRML world. LW is not interested in which technology is used to implement what it calls the multi-user technology (MUtech), it only requires that certain semantic constraints are met, e.g. the right information goes to the right object. It is for this reason that we chose to apply our DVE technology to LW. We have used the event-based DVE architecture described above to implement a subset of the LW specification. Implementing LW involves supplying implementations for the VRML prototype interfaces it defines, such as SharedObject and Zone, and mapping the VRML events it defines onto Keryx events that are then delivered by the notification service.

Figure 2 shows the various layers that constitute a LW client. The top layer represents the standard VRML used to describe the world. Those objects that must be shared have their description supplemented with LW nodes and other LW nodes are used to describe the zones and associated LW constructs. These nodes interface with the client side of the MUtech which, conceptually at least, is the last layer that is contained within the VRML browser. The KNS is a service available to any process on the client machine, not just the browser.

VRML events reflecting changes in state, etc., are relayed by the LW layer to the MUtech which, using our DVE layer, sends them to the appropriate zone server. The relevant remote clients are informed and the event is transported back up through the stack until the end effect on the VRML world is realised.

In LW, each VRML browser participating in a world has a complete copy of the world. Some of the objects in the world may be treated entirely locally, as normal VRML would be, and some objects may be SharedObjects whose state is coordinated across clients. This is done by nominating one of the object replicas as the pilot, and the others as drones (Fig. 3). The drones are merely local surrogates for the object and simply reflect updates received from the pilot. VRML events routed to drones, e.g. the results of remote user interactions with the shared object, are forwarded to the pilot, via the MUtech, for processing. This ensures that the pilot acts as a synchronisation point for all changes to the shared object.

The LW specification does not address interoperability of MUtechs, or the communication of VRML objects with external entities. We get support for the latter as a side-effect of using KNS. VRML objects sending messages do not actually know whether the receiver is another VRML object or not. So in our architecture the receiver could well be an external application (Fig. 4). Conversely external applications can send messages to VRML objects.

We believe that events may also be a good approach to MUtech interoperability. Whatever a MUtech does internally, it only has to deal with our LW event interface in order to interoperate with our implementation. Although LW content is portable among MUtechs, without interoperability a given world has to execute on a single MUtech implementation. Interoperability will be central to scaling LW, and allowing distributed construction and execution of large-scale worlds. One cannot assume that a large-scale world executes on a single MUtech implementation.

Fig. 4. Living Worlds and non-LW clients are united by a common notification system.

4.2. Modelling

Two common approaches to data management in DVE systems are to either use a server to hold all the information and partially replicate this at the clients or to replicate the whole environment at every node in the network. The former burdens the server and the latter burdens the clients. Also, both solutions do not address the issue of ownership adequately.

Decentralising the contents of the VE would be a better compromise and follows a similar model to the WWW. A skeletal model of the VE would contain hyperlinks to the segments of content which would be stored on different machines. Ownership of and access to this content would be administered by these clients and not arbitrated by a server or some form of peer negotiation. This kind of organisation is already supported by VRML and is supplemented by LW zones.

5. CubeWorld

Given a DVE infrastructure, using LW or not, there are many ways in which it may be applied. One such possibility is presented in this section.

HP has a worldwide policy of open-plan offices, with individual cubicles known as cubes, and the Bristol Lab is no exception. At Bristol we have installed an Olivetti Active Badge system with sensors in the cubes, meeting rooms and public areas. The sensors are triggered by infra-red signals sent by active badges worn by people. The sensor sightings are then emitted as active badge events containing the sensor and badge ids.

The badge sighting events are subscribed to by a VE application containing a database defining who owns which badge, and where sensors are. The application also has a 3D model of the lab. This allows the application to interpret the raw badge sightings as information about the position of the badge's owner, and position their avatar within the 3D model of the lab (Fig. 5). The VE application also knows the phone numbers associated with locations, which allows it to place calls to the current location of individuals sighted in the model. It does this using an event interface to a small telephone exchange.

This application shows one form of the openness that can be achieved using events. We have a VE driven not by internal behaviour, but by events in the real world. This VE may also, in turn, trigger external events and hence influence the real environment it is simulating.

6. Summary

We began this paper with our view of the properties a DVE system should have: scalability, interoperability, extensibility, openness, content-independence and communication. We then described how we are attempting to provide those properties with our work.

Our DVE implementation is based on the Keryx Notification System, which provides a language-neutral platform for the asynchronous delivery of events to clients in a heterogeneous network. KNS employs a publish/subscribe paradigm to ensure that clients only receive the information they need, thus reducing bandwidth consumption. Clients express what they want to receive using filters, which are applied to events by Event Distributors. Only events passing the filters are forwarded to clients.

The basic services required to support a DVE, such as zoning and state updates, are implemented in layers on top of KNS. The final complementary layer provides more intelligent functionality, e.g. data consistency management. This layered architecture makes it possible to experiment with different methods of maintaining a DVE while minimising rework.

We showed how our DVE support could be applied to VRML and Living Worlds. As we are using a generic content delivery platform we are able to support non-LW clients interacting with the VE, providing they respect the prescribed event interfaces. This provides DVEs with straightforward connectivity to the external world and legacy systems, and increases their potential uses.

We already have one application, CubeWorld, which links a VE to external communications. One of the directions we hope to pursue in the future is integration of audio communications with VEs. Initial work in this area is reported in (Low and Babarit, 1997). We also hope to investigate scaling in widely distributed large-scale VEs.

References

Barrus, J.W., Waters, R.C. and Anderson, D.B., Locales and beacons: efficient and precise support for large multi-user virtual environments. MERL Technical Report TR95-16a, 1996, http://www.merl.com/reports/TR95-16a/locales.html

Bhagwat, P., Mishra, P.P. and Tripathi, S.K., Effect of topology on performance of reliable multicast communication, in: IEEE INFOCOM '94: Conference on Computer Communications, Ch. 175, Vols 1–3: 602–609, 1994.

Birman, K., Joseph, T., and Schmuck, F., ISIS – a distributed programming environment, Version 2.1 – User's guide and reference, 1987.

Calvin, J., Dickens, A., Gaines, B., Metzger, P., Miller, M., and Owen, D., The SIMNET virtual world architecture, in: Proceedings of the IEEE VRAIS '93 Conference, 1993, pp. 450–455.

Carlsson, C. and Hagsand, O., DIVE – a multi-user virtual reality system, in: Proceedings of the IEEE VRAIS '93 Conference, 1993, pp. 394–400.

DIS, 1278.1 IEEE standard for distributed interactive simulation–application protocols (ANSI), 1995 .

Floyd, S., Jacobson, V., Liu, C., McCanne, S. and Zhang, L., A reliable multicast framework for light-weight sessions and application level framing, ACM SIGCOMM, 95: 342–356, 1995.

Hawkes, R., A software architecture for modeling and distributing virtual environments, Ph.D. Thesis, University of Edinburgh, 1996, http://www.dcs.ed.ac.uk/~rjh/

Lawton, W., Poston, T., and Serra L., in: R.A. Earnshaw et al. (Eds.), Time-Lag Reduction in a Medical Application. Academic Press, New York, NY, 1995, pp. 123–148.

Low, C., Randell, J., and Wray, M., Self-Describing Data Representation (SDR), 1997. Internet draft: draft-low-sdr-00.txt, Work in Progress.

Low, C. and Babarit, L., Distributed 3D audio rendering, in: Proceedings of the 7th International World Wide Web Conference (WWW7), Brisbane, Australia, 1997.

Macedonia, M.R. and Zyda, M.J., A taxonomy for networked virtual environments, IEEE Multimedia, Jan–Mar: 48–56, 1997.

Snowdon, D.N., AVIARY: a model for a general purpose virtual environment, Ph.D. Thesis, Department of Computer Science, University of Manchester, 1995.

Talpede, R. and Ammar, M.H., Single Connection Emulation (SCE): an architecture for providing a reliable multicast transport service, in: Proceedings of the International Conference on Distributed Computing Systems, Ch. 62, 1995, pp. 144–151.

Waters, R., Anderson, D., Barrus, J., Brogan, D., Casey, M., McKeown, S., Nitta, T., Sterns, I., and Yerazunis, W., Diamond Park and Spline, Presence, 6(4): 461–481, 1997a.

Waters, R.C., Anderson, D.B., and Schwenke, D.L., Design of the Interactive Sharing Transfer Protocol, in: Postproc. WET ICE '97 – IEEE 6th Workshop on Enabling Technologies: Infrastructure for Collaborative Enterprises, (MIT, June 1997), IEEE Computer Society Press, Los Alamitos, CA, 1997b.

URLs

Vitae

Mike Wray is a Technical Contributor at HP Laboratories Bristol, UK, where his main research interest is Distributed Virtual Environments. He has previously worked on a variety of topics including Intelligent Network Service Creation, Distributed Systems, Formal Methods, and Automatic Theorem Proving. Mike has an M.Sc. in Mathematics from Warwick University and a B.Sc. in Mathematics from Reading University.

Rycharde Hawkes graduated from Coventry Polytechnic, UK in 1991 with a B.Sc. (Hons) in Computer Science. Whilst working as a Research Associate in the Virtual Environment Laboratory at the University of Edinburgh, he completed his part-time Ph.D. and is currently employed as a Member of Technical Staff at HP Laboratories, Bristol, UK. His research interests include computer graphics, distributed systems, real-time systems, human–computer interaction, Virtual Environment design, modelling and implementation.

Distributed virtual environments and VRML: an event-based architecture

1. Introduction