RING: A Client—Server System
`
`for Multi-User Virtual Environments
`
`Thomas A. F‘unkhouser
`AT&T Bell Laboratories 1
`
`shared virtual environment. Applications for these systems
`include distributed training simulations, collaborative design,
`virtual meetings, and multiplayer games.
`
`A difficult challenge in multi-user visual simulation is main-
`taining consistent state among a large number of worksta—
`tions distributed over a wide-area network. Since three di-
`mensional rendering at interactive rates requires fast access
`to the geometric database, shared portions of the virtual en—
`vironment (including dynamic entity states) are replicated on
`every participating workstation. As a result, whenever any
`entity changes state (e.g., moves) or modifies the shared en-
`vironment, an appropriate update must be applied to every
`copy of the database in order to maintain consistent state
`(see Figure 1).
`
`Abstract
`
`This paper describes the client-server design, implementation
`and experimental results for a system that supports real-time
`visual interaction between a large number of users in a shared
`3D virtual environment. The key feature of the system is that
`server-based visibility algorithms compute potential visual in-
`teractions between entities representing users in order to re-
`duce the number of messages required to maintain consistent
`state among many workstations distributed across a wide—area
`network. When an entity changes state, update messages are
`sent only to workstations with entities that can potentially
`perceive the change , i.e., ones to which the update is visi—
`ble. Initial experiments show a 40x decrease in the number of
`messages processed by client workstations during tests with
`1024 entities interacting in a large densely occluded virtual
`environment
`
`CR Categories and Subject Descriptors:
`[Computer Graphics]: 1.3.7 Three—Dimensional Graphics
`and Realism — Virtual Reality.
`
`Additional Key Words and Phrases: Visual simulation,
`multi—user systems, virtual reality, 3D virtual environments,
`real-time graphics, client-server design, distributed systems.
`
`1
`
`Introduction
`
`In a niulti-user visual simulation system, users run an interac—
`tive interface program on (usually distinct) workstations con-
`nected to each other via a network. The interface program
`simulates the experience of immersion in a virtual environ—
`ment by rendering images of the environment as perceived
`from the user’s simulated viewpoint. Each user is represented
`in the shared virtual environment by an entity rendered on
`every other user’s workstation, and multi—user interaction is
`supported by matching user actions to entity updates in the
`
`3600 Mountain Avenue,
`funk©rescarch.att.eoni
`
`2A-202, Murray Hill, NJ
`
`07974,
`
`Permission to copy without fee all or part of this material is
`granted provided that the copies are not made or distributed for
`direct commercial advantage. the ACM copyright notice and the
`title of the publication and its data appear, and notice is given
`that copying Is by permission of the Association of Computing
`Machinery. To copy otherwise, or to republish, requires a fee
`and/or specific permission.
`1995 Symposium on Interactive 3D Graphics, Monterey CA USA
`© 1995 ACM 0-89791—736-7/95/0004...$3.50
`
`
`
`
`
`
`
`
`
`
`
`::.: ...... 555953335313":
`..Vi|'tua|- EhVifdhmeni
`
`
`
`
`
`
`
`Figure 1: Multi—user systems must maintain consistency be
`tween entities (A, B, C, and D) replicated on multiple work-
`stations.
`
`Implementing visual simulation systems for large numbers
`of users is especially challenging because updates can occur at
`extremely high rates. If N entities move through a shared vir—
`tual environment simultaneously, each modifying its position
`and/or orientation .M times per second, then M * N updates
`are generated to a shared database per second. Moreover,
`updates must be propagated to participating workstations in
`near real-time since large variances or delays in updates can
`result in visually perceptible jerky 0r latent motion, and thus
`may be disturbing to users. As a result, general—purpose dis
`tributed database systems are not adequate for use in multi-
`user visual simulation applications, and specialvpurpose mes—
`saging protocols are typically used to maintain consistent state
`in multi-user visual simulation systems [9, 13].
`
`85
`
`MS 1005
`
`1
`
`MS 1005
`
`

`

`2 Previous work
`
`Numerous experimental virtual reality systems and multi—
`player games have been developed for real time interaction
`in shared virtual environments. Unfortunately, most existing
`systems do not scale well to large numbers of simultaneous
`users.
`
`Reality Built For Two [2], VEOS [4], and MR Toolkit [14]
`are multi-user virtual reality systems that maintain consis-
`tent state among N workstations by sending a point-to-point
`message to each of N-l workstations whenever any entity in
`the distributed simulation changes state. This approach yields
`0(N2) update messages during every simulation step (see Fig-
`ure 2), and thus does not scale to many simultaneous users
`before the network gets saturated.
`
`
`
`
`
`
`
`
`
`
`Point—to—Point
`Connections
`
`Systems using point-to-point connections pass
`Figure 2:
`0(N2) update messages (labeled arrows) during each simu-
`lation step.
`
`SIMNET [5], NPSNET [17], and VERN [3] use broadcast
`messages to send updates to all other workstations participat—
`ing in a virtual environment at once. Although, this approach
`cuts down on the total number of messages transmitted to
`0(N), every workstation still must process a message when—
`ever any entity in the distributed simulation changes state
`(see Figure 3). Since every workstation must store data and
`process update messages and/or simulate behavior for all N
`entities during every simulation step,
`these systems do not
`scale beyond the capabilities of the least powerful participat-
`ing workstation. Experiences with SIMNET and NPSNET
`show that a significant percentage of every workstation’s pro—
`cessing capability is used just to read update messages from
`other workstations during large simulations; and,
`therefore,
`broadcast protocols are not practical for more than a few hun-
`dred users on inexpensive workstations [17].
`In order to support very large numbers of users (> 1000) in—
`teracting simultaneously in a distributed virtual environment
`it is necessary to develop a system design and communication
`protocol that does not require sending update messages to
`all participating hosts for every entity state change. Kazman
`has proposed a. system design, called W'AVES, in which mes-
`sage managers mediate communication between hosts, possi-
`bly culling irrelevant messages [10, 11]. His approach is very
`similar to the one presented in this paper. One difference is
`that this paper presents algorithms and experimental results
`for visibility-based message culling during large simulations.
`
`
`
`
`Broadcast
`Network
`
`
`
`
`
`Figure 3: Systems using broadcast messages pass only 0(N)
`updates each simulation step. But, every workstation still
`must process every update message.
`
`3 Overview of Approach
`
`This paper describes a system (called RING) that supports
`interaction between large numbers of users in virtual envi—
`ronments with dense occlusion (e.g., buildings, cities, etc.)
`RING takes advantage of the fact that state changes must be
`propagated only to hosts containing entities that can possibly
`perceive the change e i.e., the ones that can see it. Object-
`space visibility algorithms are used to compute the region of
`influence for each state change, and then update messages are
`sent only to the small subset of workstations to which the
`update is relevant.
`The key idea is illustrated in Figure 4. Although entities
`A, B, C, and. D (filled circles) all inhabit the same virtual
`environment, very little visual interaction (hatched polygons)
`is possible due to the occlusion of walls (solid lines). In fact,
`in this example, only one visual interaction is possible — entity
`A can see entity B. Therefore, only one update message must
`be sent for each update to entity B’s position in real—time (to
`the workstation with entity A). All other entities need not
`distribute any update messages in real—time since they are not
`visible to any other entity. From this example, we see that it
`is possible to greatly reduce the number of messages passed in
`real-time to maintain consistent state among multiple entities
`in a densely occluded environment using line—of—sight visibility
`to determine the region of influence for each update.
`
`Only B is
`visible to A
`
`
`
`User (3
`Visibility
`
`
`
`Figure 4: A system that culls messages based on entity-entity
`visibility may be able to reduce the number of messages pro-
`cessed by each workstation in densely occluded environments.
`
`2
`
`

`

`The following section describes the RING system design.
`Results of experiments with the system are presented in Sec-
`tion 5, while a discussion of alternate approaches and possible
`future work appears in Section 6. Finally, Section 7 contains
`a brief summary and conclusion.
`
`4 RING System Design
`
`RING represents a virtual environment as a set of indepen-
`dent entities each of which has a geometric description and
`a behavior. Some entities are static (e.g., terrain, buildings,
`etc.), whereas others have dynamic behavior that can be either
`autonomous (_e.g., robots) or controlled by a user via input
`devices (e.g., vehicles). Distributed simulation occurs when
`multiple entities interact in a shared virtual environment by
`sending messages to one another to announce updates to their
`own geometry or behavior, modifications to the shared envi-
`ronment, or impact on other entities.
`Every RING entity is managed by exactly one client work-
`station. Clients execute the programs necessary to generate
`behavior for their entities. They may map user input to con-
`trol of particular entities and may include viewing capabilities
`in which the virtual environment is displayed on the client
`workstation screen from the point of view of one or more of its
`entities. In addition to managing their own entities (local en-
`tities), clients maintain surrogates for some entities managed
`by other clients (remote entities). Surrogates contain (often
`simplified) representations for the entity’s geometry and be-
`havior. When a client receives an update message for an eli-
`tity managed by another client, it updates the geometric and
`behavioral models for the entity’s local surrogate. Between
`updates, surrogate behavior is simulated by every client.
`Communication between clients is managed by servers.
`Clients do not send messages directly to other clients, but iri-
`stead send them to servers which forward them to other client
`and server workstations participating in the same distributed
`simulation (see Figure 5). A key feature of this client-server
`design is that servers can process messages before propagating
`them to other workstations, culling, augmenting, or altering
`them. For instance, a server may determine that a particular
`update message is relevant only to a small subset of clients
`and then propagate the message only to those clients or their
`servers. In addition, a server may send clients auxiliary mes-
`sages that contain status information helpful for future client
`processing. Finally, a server may replace some set of ines-
`sages intended for a client with another (possibly simpler) set
`of messages better suited to the client’s performance capabil—
`ities. The aim of this client-server design is to shift some of
`the processing burden away from the client workstations and
`into servers so that larger, more affordable, multi-user visual
`simulation systems can be built using primarily 10\ ’-cost Client
`workstations.
`
`In the current implementation, RING servers forward up—
`date messages in real-time only to other servers and clients
`managing entities that can possibly “see” the effects of the
`update. Server—based message culling is implemented using
`precomputed line~of~sight visibility information. Prior to the
`multi—user simulation, the shared virtual environment is par-
`titioned into a spatial subdivision of cells whose boundaries
`are comprised of the static, axis—aligned polygons of the vir-
`tual environment [1, 15]. A visibility precomputation is per—
`
`
`
`Figure 5: RING servers manage communication between
`clients, possibly culling, augmenting, or altering messages.
`
`formed in which the set of cells potentially visible to each cell
`is determined by tracing beams of possible sight-lines through
`transparent cell boundaries [15, 16]
`(see Figure 6). During
`the multi—user simulation, servers keep track of which cells
`contain which entities by exchanging “periodic" update ines-
`sages when entities cross cell boundaries. Real-time update
`messages are propagated only to servers and clients contain
`ing entities inside some cell visible to the one containing the
`updated entity. Since an entity’s visibility is conservatively
`over-estimated by the precomputed visibility of its containing
`cell, this algorithm allows servers to process update messages
`quickly using cell visibility “look-ups" rather than more exact
`real-time entity visibility computations which would be too
`expensive on currently available workstations.
`
`
`
`is the set of cells
`Figure 6: Cell-tovcell visibility (stipple)
`reached by some sight-line from anywhere in the source cell
`(dark box) passing only through transparent portals (dash
`lines) and no opaque walls (black lines).
`It is a useful, pre-
`computed overestimate of the visibility of any entity resident
`in the source cell.
`
`As an example of RING server operation, consider the flow
`of messages between clients A, B, C, and D for the entities
`shown in Figure 4 connected to servers in the topology shown
`in Figure 5. Figure 7 shows the surrogates (small squares
`labeled by entity) and flow of update messages (arrows labeled
`by entity) for each of the four entities in this example.
`
`87
`
`3
`
`

`

`o If entity A is modified: client A sends an update message
`to server X. Server X propagates that message to server
`Y, but not to server Z because entities C and D are not
`inside cells in the cell-to-cell visibility of the cell contain-
`ing entity A. Server Y forwards the message to Client B
`which updates its local surrogate for entity A.
`
`o If entity B is modified: client B sends an update message
`to server Y. Server Y then propagates that message to
`servers X and Z, which forward it to clients A and C.
`Server Z does not send the update message to client D
`because the cell containing entity D is not in the cell-to-
`cell visibility of the cell containing entity B.
`
`o If entity 0 is modified: client C sends an update message
`to server Z. Server Z propagates that message to server
`Y. which then forwards the message to Client B. Server Z
`does not send the message to either server X or client D
`because neither is managing entities in the visibility set
`for entity C.
`
`u If entity D is modified: client D sends an update message
`to server Z. Server Z does not forward the message to
`any other server or client because no other entity can
`potentially see entity D.
`
`Client A
`
`
`
`
`
`Figure 7: Flow of update messages (labeled arrows) for up-
`dates to entities A, B, C, and D arranged in a. virtual environ-
`ment as shown in Figure 4.
`
`RING servers allow each client workstation to maintain sur-
`rogates for only the subset of remote entities visible to at least
`one entity .local to the client. All other remote entities are ir-
`relevant
`to the client so there is no need to waste storage
`space or behavioral simulation processing for them. To sup-
`port this feature, servers send their clients an “Add" message
`each time a remote entity enters a cell potentially visible to
`one of the client’s local entities for the first time. A “Remove"
`message is sent when the server determines that the entity has
`left the client's visible region. As entities move through the
`environment, servers augment update messages with “Add"
`and “Remove" messages notifying clients that remote entities
`have become relevant or irrelevant to the client’s local enti-
`ties. Since the system uses an unreliable network protocol,
`the “Add” and “Remove” messages are considered hints and
`
`88
`
`need not necessarily be processed by clients. However, they al—
`low a client to store and simulate a small subset of the entities
`with little additional processing or message traffic.
`
`The primary advantage of the RING system design is that
`the storage, processing, and network bandwidth requirements
`of the client workstations are not dependent on the numl: er of
`entities in the entire distributed simulation. Client worksta~
`tions must store, simulate, and process update messages only
`for the subset of entities visible to one of the client’s local en-
`
`In densely occluded virtual environments, visible sets
`tities.
`tend to be constant size (e.g., how many rooms you can see
`looking into the hallway from your office usually does not de-
`pend on the size of your building or whether your building is
`surrounded by a large city), so the burden on individual client
`workstations does not grow as the entire system (lees.
`
`Another advantage is that high—level management of the
`virtual environment may be performed by servers without the
`involvement of every Client. For instance, adding or removing
`an entity to or from the virtual environment requires rioti-
`fication of only one server. That server handles notification
`of other servers and clients. Also, the client-server design al—
`lows use of efiicient networks and protocols available between
`server workstations, but not universally available to all client
`workstations.
`For instance, clients may connect to servers
`via low-bandwidth networks, while servers communicate with
`each other via high—bandwidth networks.
`
`The storage and processing requirements of RING servers
`are within practical limits. Unlike clients, servers do not have
`to store display data (e.g., polygons,
`textures, etc.). But,
`they must maintain spatial subdivision and visibility informa-
`tion for the virtual environment (typically < 20MB for large
`environments) and a surrogate representation for every entity
`in the environment (currently 48 bytes per entity). As server
`storage requirements grow linearly with the total number of
`entities, the size of server workstation memory may theoreti-
`cally limit the number of entities that are able to share a vir-
`tual environment simultaneously. However, this is not likely
`to be a problem in practice since a workstation with 6-1MIB of
`memory can accommodate nearly one million entities.
`
`Server workstation processing is also within reasonable
`bounds. Servers must process messages in real—time only for
`entities visible to some entity managed by one of their clients;
`they are not required to simulate entity behavior between upe
`dates; and, they do not render images of the virtual environ-
`ment. As a result, the memory capacity and processing power
`of standard UNIX workstations are adequate for RING servers
`in densely occluded virtual environments with very large num-
`bers of simultaneous users.
`
`The disadvantage of the RING system design is that ex-
`tra latency is introduced when messages are routed through
`servers.
`Rather
`than sending messages directly between
`clients, RING routes each one through at least one server,
`and possibly two. Computations are performed in the servers
`before messages are propagated further adding to latency. So
`far, the extra latency due to server processing has not been
`noticeable during experiments. Additional work will have to
`be done to quantify the latency costs and to determine which
`types of entity interactions are sensitive to latency issues.
`
`4
`
`

`

`5 Experimental Results
`
`
`
`Entities
`#
`#
`ClientHServer
`
`Per Room Entities Rooms 11 Output
`input
`‘
`10.24
`1024
`100
`H
`0.44
`61.37
`’
`
`10.24
`512
`50
`0 43
`70.43
`
`10.24
`256
`0. 47
`53.68
`5.12
`1024
`2200
`0.55
`55.93
`5.12
`512
`100
`0. 45
`37.37
`5.12
`256
`50
`0.44
`33.20
`
`5.12
`128
`25
`0.46
`27.26
`
`1024
`400
`0.50
`24.56
`
`.
`512
`200
`0.47
`19.88
`2.56
`256
`100
`0.46
`23.19
`2.56
`128
`50
`0.41
`17.42
`
`2.56
`64
`25
`0.46
`13.65
`1.28
`1024
`800
`0.50
`11.35
`r
`1.28
`512
`400
`0.46
`14.18
`1.28
`256
`200
`0.43
`13.28
`1.28
`128
`100
`0.45
`12.08
`
`1.28
`64
`50
`0.43
`8.39
`0.64
`512
`800
`0.40
`4.62—+
`0.64
`256
`400
`0.45
`6.57
`0.64
`128
`200
`0.50
`6.41
`64
`100
`0.46
`5.37
`.
`256
`800
`.
`.
`0.32
`128
`400
`0.38
`3.20
`0.32
`64
`200
`0.33
`3.35
`|' 0.16128
`800
`0.38
`1.91
`0.16
`64
`400
`0.40
`1.68
`f 0.08
`64
`800
`0.32
`0.52
`
`i
`
`
`
`
`
`
`
`
`
`Table 1: Average message. processing rates (messages per sec-
`ond) measured in a single client (managing one entity) during
`experiments with 64, 128, 256, 512, and 1024 entities in virtual
`environments with 25, 50, 100, 200, 400, and 800 “rooms.”
`
`
`
`MessagesperSecond
`
`1024 Entities
`512 Entities
`256 Entities
`128 Entities
`64 Entities
`
`
`
`Entities per Room
`
`to a single client
`Figure 9: Average rate of messages sent
`(managing one entity) during tests with 64, 128, 256, 512,
`and 1024 entities interacting in virtual environments with 25,
`50, 100, 200, 400, and 800 “rooms." Horizontal axis represents
`the density of entities in the environment.
`
`A prototype multi-user simulation system has been imple-
`mented with the client-server design described in the previous
`section. The system runs on Silicon Graphics workstations
`and uses UDP/IP datagrams for message passing. This sec-
`tion presents results of experiments with this system manag—
`ing many entities interacting in large densely occluded virtual
`environments. The virtual environments used in these ex
`periments were mazes of “rooms” connected by “hallways.”
`They were constructed by instancing a simple floor—plan 1, 2,
`4, 8, 16, and 32 times in a square tiling pattern. Each tile
`contained 25 rooms (counting hallways) and had 724 poly-
`gons (see Figure 8). The largest environment used in these
`tests had 23,168 polygons which formed 2,219 cells. The spa-
`tial subdivision and visibility information for this environment
`took 99 seconds to compute and required 11.2MB of storage.
`
` \ngRoom
`
`w
`
`Room .
`
`\ H
`
`\ :Em
`oom'ELRoom
`
`Figure 8: One tile of virtual environment used in tests.
`
`Experiments were run with several environment sizes and
`various numbers of entities, clients, and servers to charac-
`terize the scalability of the system design. During these
`experiments, entities navigated through the virtual environ-
`ment “randomly” following piecewise linear paths in random-
`ized directions for randomized distances. Clients sent update
`messages only for changes in derivatives of entity position
`and/or orientation (i.e., dead—reckoning) while other clients
`simulated intermediate positions with linear “smooth-back.”
`Update messages containing 40 bytes (message—type[4]. entityv
`1D[4],
`target—positionflZ],
`target—orientationflZ], positional-
`velocity[4], and rotationalsvelocity[4]) were generated for each
`entity once every 2.3 seconds on average with this “random”
`navigational behavior.
`To investigate the message processing requirements of a sin-
`gle client in RING, we performed tests measuring the rates of
`messages received by clients managing one entity navigating
`through virtual environments containing 64, 128, 256, 512,
`and 1024 entities managed by other clients. Each test was
`repeated in virtual environments containing 25, 50, 100, 200,
`400, and 800 rooms. Plates I and 11 contain images captured
`during tests with 512 entities in a 400 room environment. Ta-
`ble 1 and Figure 9 show average rates of messages received by
`individual clients in each test. In Figure 9, points represent-
`ing the same number of total entities are connected by lines,
`while points representing the same density of entities are at
`the same horizontal position in the plot.
`
`89
`
`5
`
`

`

`the total number of
`As the number of servers increases,
`messages input and output by a single server decreases. This
`phenomenon is aided by the fact that update messages are
`propagated only to servers attached to clients with e11t:.ties
`that can potentially see the updated entity.
`In the test with
`16 servers, 74% of the real-time serverHserver messages are
`culled due to visibility (i.e., the 16 entities managed by each
`of the 16 servers cumulatively see 26% of the environn'ient).
`These results are encouraging since visibility-based message
`culling becomes more effective as the number of servers in-
`creases and less of the model becomes relevant to each server.
`From these results, we conclude that it is possible to build
`large multi—user visual simulation systems using a client—server
`design. We have found that server-based message processing
`algorithms which cull messages based on the three dimensional
`geometry of the virtual environment can be effective at reduc-
`ing the network traflic into client workstations. As a result,
`for sufliciently occluded virtual environments, it is possible to
`build large, affordable multi-user virtual environments using
`inexpensive client workstations with low-bandwidth network
`connections, while higher performance workstations are re-
`quired only for the relatively few servers.
`
`6 Discussion
`
`Several alternate approaches and future extensions are possi—
`ble for this system.
`
`Multicast
`
`In our first experiments with multi-user virtual environments,
`we used IP multicast to send update messages directly be;
`tween clients. The general idea is to map entity properties into
`multicast groups, and send update messages only to relevant
`groups [6]. For instance, Macedonia [l2] partitions a virtual
`world into a 2D grid of hexagonal shaped cells each of which
`is represented by a separate multicast group. Entities localize
`their visual interactions by sending updates only to the multi-
`cast group representing the cell in which they reside, and they
`listen only to multicast groups representing cells within some
`radius.
`The multicast approach is similar to the RING client-server
`approach for wide-area networks. In both cases, intermediate
`machines may cull messages rather than propagating them to
`all participating workstations. However, using multicast, mes-
`sage culling is done by routers at the network layer, whereas,
`in RING, message culling is done by server machines at the
`application layer (see Figure 11). The advantages of the mul-
`ticast approach are that: 1) fewer messages must be passed
`if clients are connected directly to a multicast-capable LAN
`(e.g., ethernet), and 2) latency is reduced due to faster mes-
`sage routing. The disadvantages are that: 1) delays associated
`with joining and leaving multicast groups make it impractical
`to use highly dynamic entity properties for multicast group
`mappings, 2) the number of unique multicast groups accessi-
`ble to any one application may not be sufficient for complex
`virtual environments, and 3) multicast is not generally avail-
`able across wide—arca networks to many types of networked
`computers (e.g., PCs with modems).
`The advantage of the RING client-server approach is that
`very dynamic and complex message processing may be per—
`
`From the grouping of points in the plot, we see that the
`rate of messages received by a single client is dependent more
`on the density of entities in the virtual environment than the
`total number of entities. This is because each client has a
`relatively constant sized region of interest (its visible region)
`which is independent of the total size of the environment or
`the total number of entities inhabiting it. During the test
`with 1024 entities simultaneously navigating through an 800
`room environment each client processed only 11.35 messages
`(4360 bits) per second on average (row 13 of Table 1). This
`was approximately 2.5% of the 450 messages per second that
`would have been processed by each client in a system without
`visibility-based culling — a 40x decrease.
`To characterize the message processing requirements of a
`single server in RING, we performed tests with various num-
`bers of servers managing communication for 16 clients and
`256 entities distributed evenly across the clients and servers
`in a virtual environment with 800 rooms. Table 2 lists aver-
`
`age server—>client, serverHserver, and total message rates for
`a single server during tests with 1, 2, 4, 8, and 16 servers. Fig-
`ure 10 shows a plot of total message rates per server measured
`during each of these tests.
`
`
`ServerHClient
`ServerHServer
`Input Output
`Input Output
`
`
`
`
`I|
`
`Tot al
`Input Output
`
`#
`
`Table 2: Average message processing rates (messages per sec-
`ond) measured in a single server during tests with 1, 2, 4, 8,
`and 16 servers managing communication for 16 clients and 256
`entities distributed evenly across the clients and servers in a
`virtual environment with 800 rooms.
`
`600
`
`
`
`MessagesperSecond
`
`Output Messages
`
`50 0
`4 0 0
`
`3 0 O
`
`100
`
`2 o o
`
`..........
`Input Messages ‘______________________________________
`
`
`
`0
`
`2
`
`4
`
`12
`10
`8
`6
`Number of Servers
`
`14
`
`16
`
`Figure 10: Average rates of messages sent to (input) and from
`(output) a single server during tests with 1, 2, 4, 8, and 16
`servers managing communication for 16 clients and 256 en-
`tities distributed evenly across the clients and servers in a
`virtual environment with 800 rooms.
`
`90
`
`6
`
`

`

`Sewer Layers
`
`5
`
`Multicast
`Router
`IP Addr 5 For!
`
`
`
`
`Figure 11: RING servers process messages in the application
`layer using 3D model and semantic information. Multicast
`routers use only IP addressing in the network layer.
`
`formed by servers. In contrast to multicast routers, which can
`only cull messages based on a relatively small, static set of
`multicast groups, RING servers can cull messages using high—
`level geometric algorithms and knowledge regarding a multi—
`plicity of highly dynamic entity attributes (e.g., location, ori-
`entation, velocity, etc.) and interaction types (e.g., visibility,
`sound, collision, etc.). Since RING servers can take advantage
`of knowledge regarding message semantics and the 3D geome—
`try of the virtual environment directly, they can execute more
`effective and flexible culling algorithms than would be possi~
`ble using only IP address and port mappings. Furthermore,
`unlike multicast routers, RING servers may process, augment,
`and alter messages in addition to culling them. For instance,
`RING servers already augment update messages with “Add”
`and “Remove” messages to inform clients that entities are en-
`tering or leaving their potentially visible sets.
`
`Server Topology
`
`We have experimented with a variety of topologies for con-
`necting RING clients and servers. For practical reasons, we
`have focused mainly on arrangements in which clients com-
`municate with a single server. However, depending on the ca-
`pabilities of available workstations and networks, clients can
`send messages to server(s) via unicast or multicast. Clients
`can choose server(s) to manage their messages statically (i.e.,
`all of a client’s messages are sent to the same server(s)) or
`dynamically (e.g., based on the position of the updated en-
`tity). Servers have similar choices for distribution of messages
`among themselves, but can also be arranged in a hierarchy in
`which some servers manage communication between others.
`Perhaps the most promising topologies are those in which
`servers manage communication between entities in separate
`regions of the virtual environment. For instance, we have im-
`plemented protocols with which entities migrate to a server
`managing the region of the environment containing the cen-
`troid of its enclosing cell. The advantage of this approach is
`that server-server communication is greatly reduced if there
`
`91
`
`In such
`is relatively little inter—visibility between regions.
`cases, most real~time updates affect only entities managed by
`the same server, and periodic updates must be passed only
`to servers whose region is visible to the updated entity.
`In
`early experiments, more than 95% of server—server messages
`are eliminated with regional servers. Further work is required
`-to fully investigate the trade-offs between regional and other
`types of client-server topologies.
`
`Multiresolution Simulation
`
`An extension to RING currently being investigated is to use
`multiresolution simulation to reduce network traffic and client
`behavioral simulation processing. One idea is to allow RING
`servers to process sequences of messages and elide updates
`based on the perceptible importance to each client’s entities.
`For example, consider the situation shown in Figure 12. Al-
`though A can see both B and E, B is closer to A. Thus, up—
`dates to B may be more important to A than updates to E,
`and could be sent to A at a finer resolution.
`In fact, E may
`be far enough away that small updates are imperceptible to
`A, so they can be elided completely. More generally, RING
`servers can alter any sequence of update messages for any en-
`tity dynamically to meet the perceptible quality required by
`each client. Finally, time crit