A Network Communication Protocol For Distributed Virtual Environment Systems
A Network Communication Protocol For Distributed Virtual Environment Systems
A Network Communication Protocol For Distributed Virtual Environment Systems
1. Introduction
Virtual environment (VE) applications usually consist
of many different tasks that modify or examine a shared
environment. The tasks vary considerably in computing
requirements, from obtaining tracking and hand input
information through continuous communication with
external devices, to rendering processes that require
graphics intensive computation, to processes that perform
collision detection between entities of the environment
and simulate movement and behaviors for those entities, to
processes that produce audio output. Clearly, VE systems
benefit from a distributed computing design, allowing
tasks to be performed by the computing resources that best
match the task. The issue that arises from such a design is
how information is communicated between tasks.
GIT-GVU-96-03
2. Related Work
Communication in current distributed VE systems usually involves one-to-one communication with processes
that interface external devices, or one-to-many communication among processes that share a common state. Com-
3.2. Commands
Command messages convey instructions from one task
Receive
Wait
Client
Poll
Server
Response
Send-and-Wait Polling
Send
Client
Receive
Other Work
Poll
Server
Response
Event Polling
Figure 2: Polling Communication
3.3. Events
Event messages communicate the occurrence of events,
such as key-presses, button presses, or object collisions. In
addition, commands that do not require a response can be
represented as events. Events could occur frequently, but
like commands, are unique, do not become obsolete, and
therefore require guaranteed, FIFO delivery. When processing events, a task often needs the context, or state, at
the time of the event. As a result, the last state update messages before the event cannot become obsolete until after
the event has been processed.
Like command messages, event messages can also be
used to obtain state information from another task through
polling. In this case, the poll and response messages are
event messages. This method has an advantage over using
command messages in that the client does not need to
block for a response (the communication is asynchronous). The disadvantage is that the response may arrive
2
x
1
b
2
y
1
b
Data
0
a
2
x
1
b
0
a
2
x
1
b
5. Implementation
To allow for communication between tasks of a VE
application which are being performed by separate processes on the same machine or on different, networked
machines, we designed a prototype implementation of
updatable queue pairs, which we have named the InterProcess Queue (IPQ) library. Using the IPQ library, each
task can send state update, event, and command messages.
In addition, a task can read the latest command, event, or
state update without waiting, if none has arrived. The
functions to perform these tasks are the same for connections between processes on the same machine, or processes on separate machines, although the message
passing is implemented differently.
Our implementation uses one-to-one communication
either through shared memory (when the two processes
are on the same physical machine) or UDP messages
(when the processes are on separate physical machines).
We have chosen not to utilize an IP-Multicast protocol due
to the added complexity of providing guaranteed, FIFO
message delivery. Future implementations may utilize this
protocol to reduce message traffic between processes.
2
z
0
a
2
x
2
z
0
a
2
x
The task which is to be the client end of the connection requests that a connection be established by giving the
appropriate service name and machine location to
IPQ_openConnection(). Note that the client task can
also specify how large the outgoing queue should be.
IPQ_connect IPQ_openConnection(char
*serviceName, int serviceType, char
*machine, int outSize);
Once a connection has been established, the two processes can construct packets to send to each other, complete with the key value that indicates if a message is a
command or event (0) or a state update (>0), and can
receive and de-construct packets from the other task.
one for outgoing messages, and one for incoming messages, which reside in shared memory blocks. If the two
task processes reside on the same machine, the updatable
queues are direct connections between the task processes
(Figure 6). If the task processes reside on separate
machines, the queues actually connect the task process to
its communication process (Figure 7). Messages to the
other task process are read from the shared memory queue
and sent from the tasks communication process to the
communication process of the other task, which forwards
it to the task process. Messages received from the other
tasks communication process are placed on the tasks
incoming queue by the tasks communication process.
Shared memory is utilized for communication between
processes on the same machine for two reasons. First, data
passed through shared memory does not need to pass
through the kernel, which would slow down the transfer.
Second, messages sent through the shared memory updatable queues are inherently guaranteed, as the queue is one
way (only one process entering data), and flags are used
for mutual exclusion.
UDP messages, however, are not guaranteed. Our
implementation provides guaranteed message passing with
UDP messages by using sequence numbers, and a stop and
wait method with an adaptive time-out and an exponential
back off. This method, called Jacobsons algorithm, is
described in [12]. In our implementation, the method is
slightly modified so that if a message fails to be acknowledged, and the information in the message becomes obsolete (because it is of the state update type, and new
information has arrived), then we give up on the obsolete
information, and continue trying with the new information
instead. In addition, if a send does not succeed, it is not
immediately re-sent if there are other messages waiting to
be sent to different destinations. The other waiting messages are sent first to prevent a bad connection from completely stopping transmission through other connections.
6. Performance
In order to judge the performance of the protocol
described here, we created a benchmark application which
we implemented using the IPQ library and using the TCP/
IP Internet protocol. The benchmark application consists
of two processes, one which sends a stream of 1000 messages, and one which receives the messages. Each message contains the (machine local) time the message was
sent, an ID value, and an array of 16 floating point numbers. This benchmark simulates a pair of processes, in
which one process informs the other of a 3D position and
orientation of an entity (a common VE task). The processes were run on SparcStation 2 workstations connected
via 10Mb/s Ethernet.
We have, in fact, three different implementations. One
Name
Server
Task A
Process
Task A Comm.
Process
Task B
Process
Task B Comm.
Process
Process
Updatable
Queue
Name
Server
Name
Server
Task A
Process
Task A Comm.
Process
Task B Comm.
Process
Task B
Process
1.2
1
0.8
0.6
1
0.8
0.6
0.4
0.4
0.2
0.2
0
0
0
0.02
0.04
0.06
0.08
Receiver delay (secs)
0.1
Figure 8a: Message lag for local processes given that the
receiver spends time doing other things (the delay time)
0.02
0.04
0.06
0.08
Receiver delay (secs)
0.1
Figure 8b: Message lag for remote processes given that the
receiver spends time doing other things (the delay time)
18
18
TCP Send time
IPQ-Update Send time
IPQ-Unique Send time
16
16
14
Total send time (secs)
14
Total send time (secs)
1.2
TCP Lag
IPQ-Update Lag
IPQ-Unique Lag
1.4
TCP Lag
IPQ-Update Lag
IPQ-Unique Lag
1.4
12
10
8
6
12
10
8
6
2
0
0
0
0.02
0.04
0.06
0.08
Receiver delay (secs)
0.1
0.02
0.04
0.06
0.08
Receiver delay (secs)
0.1
7. Conclusions
The goal of most VE applications is to provide a
dynamic environment that is interactive with the user or
users. Meeting these requirements can involve a distributed design, with communication that reflects the most
current state available. Existing communication protocols,
such as TCP, do not allow messages to become obsolete,
and therefore do not allow for state update messages to
overwrite older state update messages. We have described
an updatable queue abstraction that we use to develop a
protocol that does allow messages to be discarded because
they become obsolete. Using a prototype implementation
of the protocol, we have shown that, when state update
communication is a substantial component of the communication between tasks of a VE application, our protocol
provides better performance than a traditional TCP message passing implementation.
8. Acknowledgment
We would like to acknowledge the extensive discussion
and advice provided by Brad Topol during the development of this protocol.
9. References
[1] Birman, K., A. Schiper, and P. Stephenson. Lightweight
Causal and Atomic Group Multicast. ACM Transactions on
Computer Systems, 9, 3, (Aug., 1991), pp. 272-314.
[2] Birrell, A. D. and B. J. Nelson. Implementing Remote Procedure Calls. ACM Transactions on Computer Systems, 2, 1,
(Feb., 1984), pp. 39-59.
[3] Blau, B., C. E. Hughes, J. M. Moshell, and C. Lisle. Networked Virtual Environments. Symposium on Interactive
3D Graphics (1992), pp. 157-160.
[4] Calvin, J., A. Dickens, B. Gaines, P. Metzger, D. Miller, and
D. Owen. The SIMNET Virtual World Architecture. Proc.
of IEEE VRAIS (Seattle, WA, Sept., 1993), pp. 450-455.
[5] Carlsson, C. and O. Hagsand, DIVE - A Platform for Multiuser Virtual Environments. Computers & Graphics, 17, 6,
(1993), pp. 663-669.
[6] Cheriton, D. R. and D. Skeen. Understanding the Limitations of Causally and Totally Ordered Communication.
ACM SOSP (Dec., 1993), pp. 44-57.
[7] Codella, C., R. Jalili, L. Koved, J. B. Lewis, D. T. Ling, J. S.
Lipscomb, D. A. Rabenhorst, C. P. Wang. Interactive Simulation in a Multi-Person Virtual World. Proc. of ACM CHI
(May, 1992), pp. 329-334
[8] Funkhouser, T. A. RING: A Client-Server System for MultiUser Virtual Environments. Symposium on Interactive 3D
Graphics (1995), pp. 85-92.
[9] Holbrook, Hugh W., Sandeep K. Singhal, and David R.
Cheriton. Log-Based Receiver-Reliable Multicast for Distributed Interactive Simulation. Proc. of ACM SIGCOMM
(Cambridge, MA, Aug. 1995), pp. 328-341.
[10] Macedonia, M. R., M. J. Zyda, D. R. Pratt, D. P. Brutzman,
and P. T. Barham. Exploiting Reality with Multicast
Groups: A Network Architecture for Large-scale Virtual
Environments. Proc. of IEEE VRAIS (RTP, NC, Mar.,
1995), pp. 2-10.
[11] Shaw, C., J. Liang, M. Green, and Y. Sun. The Decoupled
Simulation Model for Virtual Reality Systems. Proc. of
ACM CHI (May, 1992), pp. 321-328.
[12] Singh, G., W. Png, A. Wong, and L. Serra. Networked Virtual Worlds. Proc. of Computer Animation 95 (Geneva,
Switzerland, Apr., 1995), pp.44-49.
[13] Stevens, W. R. UNIX Network Programming. Englewood
Cliffs, NJ: Prentice-Hall (1990).
[14] Sunderam, V. S. An Inclusive Session Level Protocol for
Distributed Applications. Proc. of ACM SIGCOMM 90;
(Special Issue Computer Communication Review), 20, 4,
(Sept., 1990), pp. 307-316.
[15] Sunderam, V. S. PVM: A Framework for Parallel Distributed Computing. Concurrency: Practice & Experience, 2, 4,
(Dec., 1990), 315-339.
[16] Wang, Q., M. Green, and C. Shaw. EM - An Environment
Manager for Building Networked Virtual Environments.
Proc. of IEEE VRAIS (RTP, NC, Mar., 1995), pp. 11-18.