7i/Iulr
`
`i/I/ledia
`
`2.2mgam
`
`fzfiipumk
`C
`SOClETY@
`
`
`
`mmqummqaomuemmmum
`
`oaoqm
`
`M1
`
`
`
`pomshrew:rum
`
`
`
`HH4mrmbmwzawemm
`
`zH22m¢worHm:2mm»mm:ommH
`
`
`
`
`
`zwramxmmwnwrmmmonmmmazn
`
`THE INSHTUTE OF
`ELECTRICAL AND
`ELECTROMCS
`E E R5, INC.
`
`RPX Exhi it 1127 M"
`
`RPX Exhibit 1127
`RPX v. DAE
`
`RPX V. DAE
`
`IEE-E
`SNmAENUMMOC
`SOCIETY
`
`
`
`
`
`

`
`' Editor in Chief
`Rameshjain
`
`University afcoiifbnrio, .Sroi- Diego
`
`Submissions: P1_e'ja_se 'so_b__m_1t six copies of all articles and_pro-
`posals for special issues to Rarnesh Jain, UC San Diego, Dept.
`ot'Eler:t_r1;':a1ancl Computer Eliglneerlng, MC 0407, 9.500
`Giirnan Dr.-, La Jolla,_ CA 92093-0407, ]ain@'ece.ucsd.ed1.1. All
`_su_bmissions'are subject to_edltin'g "for style, clarity, and space.
`
`_ Associate Edi_tors._ln Chlei
`Ralf S.tein'm‘etz-
`Masao Sakauchi
`Editorial Board
`
`_
`IBM European Networirirtg Ctr."
`U. Tokyo‘
`
`Meera Blattner
`Glorianna Davenport
`Wolfgang Effelsberg
`Christos Faloutsos
`Simon Gibbs
`Athula Ginige
`Forouzan Golshani
`William Groslcy
`Wendy Hall
`Thomas Little
`Pelya Liu
`P. Venkat R-angan
`Dipankar Raychaudhuri
`Sore] Reisman
`Charles Rich
`Arturo A. Rodriguez
`Harrlck Vin
`Jeff Derby
`
`U. Coliflnrnia, Davis; LLNL
`MIT
`U. Moinilleiin
`U. Maryland‘
`GMD
`U. Technology Sydney
`Arizonrr State U.
`Wayne State U.
`U. Soutlunnpton
`Boston U.
`Siemens Corporate Research
`U. Cnlifomio, Son Diego
`NEC USA
`Cnlifonur: State U., Fullerton
`Mitsubishi Electric Research Labs
`Scienn'fic-Atlrmto
`U. ofTexos, Austin
`IBM, and
`Comrmnnrotions Society representative
`
`Managing Editor
`Associate Editor
`Assistant Editor
`Art Direction
`
`Publisher
`Assistant Publisher
`Advertising Manager
`Advertising Coordinator
`Member;'Clrc. Promos Mgr.
`Editorial Secretary
`
`Nancy Hays
`Linda World
`Anne C. Lear
`Joseph Daigle
`
`True Seaborn
`Matt Loeb
`Patricia Garvey
`Marian Tibayan
`Georgann Carter
`Alkenia Winston
`
`Magazine Operations Committee
`James J. Farrel III (chair), Gui Agha, Stephen E. Cross, Alan M.
`Davis, Stephen L. Diamond, Bertram Herzog, Ramesh Jain,
`john A.N. Lee, Edward Parrish, Ahmed Sarneh, Ken Wagner
`Publications Board
`Ronald Williams (chair), Anlello Cimilile, James J. Farrell Ill,
`Tadao lchikawa, Mary Jane Irwin, Raymond Miller, Michael C.
`Mulder, Alice C. Parker, Theo Pavlidis, Walter Tichy, Mladen A.
`Vouk
`
`
`
`Editor-in-Chiefs Message
`Romesh lain
`CAD for Creative People
`
`Web_Sight
`Sorei Reismon
`
`
`
`Keeping an Eye on the Web
`
`in the News
`
`William Grosky
`
`IO
`
`Visions and Views
`
`Glorionno Davenport
`Smarter Tools for Storytelling
`
`74
`
`Multimedia at Work
`
`Charles T. Hemphfll, Philip R. Thrift,
`and john C. Linn
`Speech-Aware Multimedia
`
`79
`
`Project Reports
`Thomas G. Aguierre Smith
`Multimedia Lab Supports
`Sustainable Development
`
`Standards
`
`Bronko ,1‘. Gerovac and David C. Carver
`
`Standardizing Headers in the Quest
`for Interoperability
`
`89
`
`Upcoming Events
`
`Media Reviews
`
`New Products
`
`Advertiser/ Product Index
`
`Computer Society information, C3
`Reader Service Cord, pp. 96a 81 b
`
`E R
`
`,i:ee3
`'aai§a3;;§e,3:laé§o;f6yl:ne3:'-angles"aiia'a1e,ss'r£Hrents;.as.we1|'_ss: descriptions of"products and services, reflect the authorlsgor firmls opinion; inclu-
`,
`__
`
`‘
`_'n‘-_1n t_l_1is_'publ|cat_lon does not'néces‘ranly'constitutc endorsement by the l£EE'or-the computer.so;iety.
`
`5 zcopyrlgfit and .rE§:rlnt permission: Abstracting‘-is-permitted with.-.crefl,;- to the source. libraries are pennltted to photocopy beyond the limits of US copyright
`.
`ljaw tor"p‘,'ri\rat'e-use" of patrons those articles -that carry a code at the-bottom of the first page, provided the per-copy fee Indicated In the code is paid through the
`Copyrlghtclearance Center, 29 Congress St, Salem, MA 01970". Instructors are permitted to photocopy isolated articles for noncommercial classroom use with
`out fee. For other copying, reprint, or republication permission, write to Permissions Editor,
`IEEE Multilviedio, 10662 Los Vaqueros Circle, PO Box 3014, Los
`Alamltos, CA 90720-1264'. All rights reserved. Copyright 9 1996 by the Institute of Electrical and Electronics Engineers, inc.
`
`Circulation: lEEE Mw'tiMeo'lo (l5SN 1070-986X) is published quarterly by the IEEE Computer Society. IEEE Headquarters: 345 East 47th St., New York, NY 1001 F-
`2394. IEEE Computer Society Publications Office: 10662 Los Vaqueros Circle, PO Box 3014, Los Alamitos, CA 90720-1264; (714) 821-5380. IEEE Computer Soci-
`ety Headquarters: 1730 Massachusetts Ave., Washington, DC 20036-1903. Annual subscription: $22 in addition to any IEEE group or society dues. Members of
`other technical organizations: $31. Nonmember subscription rates are available on request. Single copies: members, 310; nonmembers, $20. This journal is also
`available in microfiche form.
`
`i’oslmaster: Send address changes and undelivered copies to IEEE Multimedia, IEEE Computer Society, 10662 Los Vaqueros Circle, PO Box 3014, Los Alamitos,
`CA 90?20-1264. Second class postage is paid at New York, NY, and at additional mailing sites. Canadian GST ii12S634188. Printed in USA..
`
`
`
`

`
`This material may be protected by Copyright law (Title 17 U.S. Code)
`
`

`
`
`
`audio in a traditional conferencing environment.
`The three documents on the table and the wall dis-
`
`play are active, displaying text and graphics cou-
`pled to external tools in the outside (real) world.
`
`Interaction with individual objects
`An interactive multiuser VE, in which partici-
`pants interact with objects constituting a 3D
`scene, must support the creation and modification
`of individual objects. Information is distributed
`on a per object basis, where individual objects are
`addressable and may be requested and retrieved
`over the network.
`
`In a truly interactive environment, participants
`must be able to dynamically create, modify, and
`remove objects, as well as enable others to do the
`same. This means that objects are not owned by a
`creator—once introduced, an object may be
`accessed and modified by any participant.
`if combined with autonomic behaviors, such a
`
`shared environment has enormous power. For
`example, an object created and released in a world
`can perform actions by itself and be picked up and
`used by other participants.
`
`Why networking is important
`Peers of such an advanced distributed applica-
`tion need to exchange large amounts of informa-
`tion,
`including object and world definitions,
`navigation commands, audio, and bitmaps. Over
`an internet, messages might have to be delivered
`among many participants over high-latency
`paths. Recent round-trip estimates measured in
`DIVE experiments range from 25 milliseconds
`within Sweden, 200 ms to American sites, and 800
`ms to Japan.
`In such an environment, it is crucial that par-
`ticipants experience “acceptable" delays. The ulti-
`
`Figure 1. A world seen from a user's
`viewpoint. The scene irrclmles two
`otlrer actors embodied very simply, as
`“blockies.”
`
`
`
`mate endpoints of communication are the human
`senses and the brain's actual perception of sound
`and pictures. Typically, end-to-end latency as
`experienced by a human user has an upper bound
`for acceptability. For audio this limit is roughly on
`the order of 100 ms, while interactive manipula-
`tion requiring feedback has an even lower bound.
`Unfortunately, network and physical realities
`make these limits unreachable for global distrib-
`uted systems. Other properties, such as object
`motion and presentation, might be less sensitive
`to latency, especially if described by behaviors
`evaluated locally at each peer.
`System designers must therefore address pro-
`tocol and performance issues and design the com-
`munication between peers to take advantage of
`the network's available bandwidth. In short, the
`
`amount of traffic between peers must be reduced
`and end-to-end latencies minimized.
`
`two distinguishing features
`Summarizing,
`make interactive multiuser VEs possible: interac-
`tion with individual objects and scalable net-
`working. We will later return to how these issues
`were addressed in DIVE.
`
`For a discussion of networked multiuser VF. sys
`tems, see the sidebar on the next page.
`
`Figure 2. A conferencing
`applicntiorr with three
`actors who can com-
`
`municate rising text and
`audio. The documents
`on the table and wall
`
`display are active,
`displaying text and
`gmplrics coupled to
`external tools. (See the
`
`sidebar on p. 39 to find
`three forms of this
`example on the Web.)
`
`
`
`966i5U!JdS
`
`31
`
`

`
`Ne__twor_ke_d Multiuser-VE Systems
`:Several other multiuser VEs_ take distribution and multiuser aspects into"
`consideration. The VUE system’ is a distributed client-server architecture
`where processes communicate via asynchronous message passing. In the
`Minimal" Reality (MR) Toolkit,’ a set of master processes is connected pair-
`wise to other master processes." Messages may be sent unreliably between
`one process and the other peers.
`Several systems are based on an object-request broker approach. Their
`interfaces let objects be accessed remotely (by asynchronous message pass-
`ing) through a client-server system. Massive‘ and Bricl<Net5 are examples of
`such systems.
`Many systems rely on the DIS protocol,‘ originally designed for multi-
`_ party training in combat situations. With this approach, multiple immobile
`objects form a static background, such as landscapes and buildings, while
`the movements of a smaller set of dynamic objects, such as vehicles, are dis-
`tributed to all connected peers. One such system is NPSNet (Naval
`Postgraduate School Net),’ in which large-scale distribution issues were taken
`very seriously. For example, NPSNet is currently addressing how to increase
`the number of participants and information space to the range of thousands
`of participants over an internet.
`
`The DIVE software model
`To understand the fundamentals of the DIVE
`
`environment, let’s briefly consider the platform's
`software model.
`
`Distributed entities
`DIVE entities form the basic units of distri-
`
`bution that can be addressed, requested, and dis-
`tributed. Figure 3 shows a class hierarchy {used
`only for modeling—DlVE is implemented in plain
`C) where the entity class is the top-level abstrac-
`tion. An entity has a
`globally unique iden-
`tifier used for address-
`
`dive_object
`
`view
`
`world
`
`light
`
`actor
`
`line
`
`box
`
`polygon
`
`cylinder
`
`ing, a name, a behavior
`description, and a set
`of properties usable for
`application-specific
`data. The entity and
`view classes are abstract
`
`while views and a light (a light bulb} are depicted
`graphically. The active object has an associated
`behavior triggered by user interaction. For exam.
`ple, selecting or stepping up close to the light acti.
`vates the light bulb.
`
`DIVE objects
`DIVE objects carry the essential logical, inter.
`action, and dynamic information in a world. This
`includes geometrical orientation, material descrip-
`tions, and variables controlling interaction and.
`rendering. When DIVE objects are composed hier-
`archically, their own geometrical transformation 2
`is composed with the rotation and translation of _'
`the object at the next level in the hierarchy.
`"
`The following DIVE file format definition spec-_I
`ifies the lamp obiect with a default black material"
`and a displacement of 10 meters in the z-axis-
`direction:
`'
`
`object {
`name "lamp"
`trarislation v 0 0 10
`material "black"
`
`,
`Graphical representations: Views
`Lines, spheres, cylinders, boxes, grids, anti?
`polygons are examples of subclasses of the view‘;
`class. Views are passive graphical 3D representa-
`tions that may be dynamically created and modi-
`fied. When a user interacts with a view, typically:
`by pointing to it, the DIVE object closest to it in;
`the hierarchy handles the actual interaction. For
`example, the active object in Figure 4 defines the.‘
`behavior of the views and lights below it.
`i
`The lamp pole in Figure 4 is an example of ai
`cylinder:
`
`view {
`CYLINDER
`0.02
`0.02
`1.3
`
`Figure 3. Class
`hr'erm'chy of'DIl/E
`entities.
`
`that
`classes;
`instantiations
`allowed.
`
`is, no
`are
`
`}
`
`Entities are structured hierarchically in a tree:
`a world is a root, while dive_objects are nodes,
`views are leaves with 3D graphical representa-
`tions, and lights are leaves with a light model def-
`inition.
`
`Figure 4 shows an example of an entity hierar-
`chy of the active lamp object shown in Figure 1.
`lamp and active are examples of clive_objects,
`
`where 0.02 denotes the two radii and 1.3 th'
`
`height of the cylinder.
`
`Multicast domains: Worlds
`
`A world represents a separate virtual space dis—.
`joint from other worlds, with its own set of
`obiects, actors, and views. The world information
`
`is common to all entities within the space, such
`as background light, fog, and spatial boundaries.
`
`

`
`Behavior in objects: The D|VE,fTc|
`interface
`
`DIVE worlds are not passive.
`Entities
`are
`somewhat autono-
`
`Lamp
`
`
`
`Figure 4. An entity
`hierarchy showing two
`obiects, active and
`lamp, with their
`graphical
`representations.
`
`
`
`966Lfiuuds
`
`33
`
`mous-—-they react to stimuli, move,
`transform, and adapt to the chang—
`ing environment. This degree of
`autonomy is achieved by associating
`'I‘ci scripts“ with entities. Typically,
`an event in the system triggers 3
`DlVE.»'Tcl script, resulting in a set of
`actions. Because Tcl is portable and
`interpretative, scripts are replicated along with the
`entities and can be executed immediately on any
`platform without compilation.
`simplified)
`In the following (somewhat
`DIVE,I’Tcl example‘ script, an object selection starts
`a simple motion:
`
`c
`
`proc move_up {id type actor srcid }
`for {set i 0}{$i < 1DO}{incr i}{
`div-e__s1eep 100
`dive__move $id D 0.5 0 LOCALFC
`
`}
`
`{
`
`} d
`
`ive:__r eg i ster selec t: rnove_up
`
`The move_up Tcl procedure is registered by
`divegregister, which is invoked when a DIVE
`
`select occurs at the object containing the script.
`When the move_up procedure is called, the para-
`meters identify which actor and object invoked
`the script. The div:-.~_move procedure itself dis-
`places the object 0.5 meters in the local coordi-
`nate system every 100 ms. Really powerful event-
`and timer-driven behaviors are s pecified by hav-
`ing access to the complete IJIVF. functional inter-
`face in combination with Tcl
`iterations and
`functions.
`.
`We have found autonomous behavior to be
`
`extremely useful in "programming" VES. Graphi-
`cal modeling is a smaller problem; normally a
`standard 3!) modeling tool will serve. A more
`important aspect of modeling is how to animate
`and put life into the objects constituting the VEs.
`
`Collision detection
`
`Collision detection is an essential service in a
`
`VE system. Consequently, collision detection
`forms the basis of many DIVE functions, includ-
`ing gateway detection, interaction, and commu-
`nication support.
`The Massive‘ approach influenced us to have a
`collision manager. Processes register interest in
`certain objects and actors, and the collision man-
`
`The following “park” world is defined with a
`
`fog and a default {grey} background color:
`
`world {
`name
`start
`info
`
`"park”
`v 0 0 -5
`"A test world
`
`showing a niCe_park"
`background. 0.2 0.2 0.2
`fog
`0.0002
`
`}
`
`A world defines a separate spatial domain and
`is therefore naturally assigned a multicast address.
`Only peers that have joined a world-specific mul-
`ficast address can listen to events occurring in that
`world. Requests of entities belonging to the world
`can be made by sending a message to the world’s
`multicast address. A DIVE name server handles
`
`the assignment of multicast addresses and nan1e-
`to-address lookup.
`
`User representations: Actors
`
`An actor, typically a user or an automated
`process, represents a process-bound entity that
`performs actions within a world. The actor modi-
`fies objects and parameters and sends messages to
`other entities within the world. Messages either
`result in concrete changes in the database, such as
`“moving an object,” or are more abstract, such as
`
`“an actor has picked up an object." _
`Since objects can be modified by any actor, not
`only the creator, concurrent modification requests
`must be resolved. Here, we assume that actors
`
`"own” object.s for a long time and that concurrent
`modifications seldom occur. Entities are therefore
`
`protected from concurrent “writes" by a simple
`object—based tokenpassing algorithm: In the rare
`case of a conflict, one actor blocks until it receives
`the token.
`
`An actor can change worlds by entering a gate-
`way, an object serving as a portal to another
`world. When the actor passes through the object,
`a collision manager signals a collision, a name
`server is queried for a multicast group to join, and
`the actor is transferred with its embodiment to the
`new world.
`
`Dynamic interaction and behavior
`The software model described above forms the
`
`basis upon which essential VE functions are
`implemented, such as collision detection, dynam-
`ic object behavior, user interface support, and
`audio.
`I will now describe these functions as
`
`implemented in DIVE.
`
`

`
`
`
`a visor, which is just an invisible object acting as a
`placeholder for the user’s icons. Usually, the visor
`is placed just in front of the actor's eyes, so actor
`and icons move together. The visor thus forms an "
`"2D” working area providing easy access to con-
`trol and monitoring icons.
`Vehicles help users navigate in 3D space. The
`vehicle icons, placed above the three buttons,
`include the rectangle—a "walking-style” vehicle—-. I
`and the triangle—-a "flying-style" vehicle. For
`example, users interacting with the flying-style-= .
`vehicle see their embodiments move as if carriedij ,
`by an airplane.
`'
`The icons in Figure 6 are autonomous objects-_
`defined by DIVE/TCI scripts. When a user interacts} "I
`with these objects, things happen—the user's;
`embodiment moves, menus appear, and other-,
`objects are affected. The car in the foreground has;
`a steering wheel, an ignition button, and a speed
`meter. These control the car's movement, and 5-,":
`user may manipulate them. An actor can attach
`the car and follow it as it drives along. Other actor
`
`also may enter the car and control its movement.-
`Figure 6 also shows another actor controlling a
`different car. As a consequence of the dynamic-
`environment, an actor can change embodiments
`at will. For example, an actor could select the heli- :
`copter as a new embodiment.
`
`Communication by text and audio
`It
`is essential
`to support communication '
`between participants in multiuser \/Es. Dumb par-.
`ticipants can only communicate through body
`language, which is extremely limited given the
`constrained embodiments. Therefore, we made it
`
`possible for DIVE actors to communicate directly
`using text messages and live audio.
`The endpoints of audio communication are
`associated with entities in the 3D environment».
`
`Thus, audio sources, including microphones an '
`Internet audio conferences, can have physical rep-
`resentations such as a mouth or a radio, respec-
`tively. The location and orientation of the entities
`can then be used to model 3D audio—or at leas'
`attenuate audio with distance.
`
`In several 3D audio and speech synthesis"
`experiments, the spatial properties of entities were
`given as input to external tools. Using this tech‘
`nique, current versions of DIVE use standard
`audio conferencing tools, such as Nevot (Network
`Voice Terrninal)," to convey real-time audio. Thus,
`DIVE does not distribute or process the audio data
`itself, but has the ability to feed external tools the
`necessary 3D location information.
`
`
`
`
`
`
`
`age: generates collision
`signals for the regis-
`tered entities as their
`volumes intersect.
`
`system
`In DIVE,
`servers implement col-
`lision managers and
`the handling of colli-
`sion events,
`so the
`semantics can be al-
`
`Figure 5. An actor
`
`approaching a lmup
`intersects a surrounding
`volume. As :1 result, the
`lamp is tumed on.
`
`tered easily to satisfy
`different
`application
`needs. This approach supports different models,
`including the spatial interaction model developed
`by Fahlén and Benfordfi and the use of geograph-
`ical areas in simulation}
`
`Intersecting volumes and behaviors can be
`used in simple interfaces. As an example, Figure 5
`illustrates the use of volumes in animating a VB
`scene. In the figure, an actor is approaching a
`lamp. The system detects the actor's penetration
`of the volume surrounding the lamp (an aura),
`indicated by the yellow lines. The lamp—an
`autonomous object—reacts to the collision by
`turning on the light, as defined with the follow-
`ing DIVEITCI script:
`
`turn_on {idl id2 type} {
`proc:
`set id [dive-_fi.ncl_subobj sidl
`"bulb“]
`
`dive_light $id on
`
`ivt-3__regis tier Col 1 is i0n_on l:urn_on
`
`} d
`
`where the turn_on procedure is called when a
`collision signal occurs and dive_l ight turns the
`actual light source on.
`
`User interface
`
`A process with a 3D rendering module that
`associates a real human user with a virtual user-
`
`an actor-—is called a visualizer. A visualizer pre-
`sents a graphical representation of a virtual world
`and lets the user interact with that world by select-
`
`ing and grabbing objects, sending messages to
`actors, setting up audio connections, and so forth.
`DIVE provides many visualizers, each suited for
`different interface requirements. For example,
`with an immersive interface, magnetic trackers
`
`monitor body movements, and an HMD provides
`the world view. With a nonimmersive interface,
`
`the regular mouse and keyboard are used, and the
`world is viewed on a regular screen.
`Figure 6 shows a typical DIVE user interface. It
`has three buttons and two vehicle icons placed on
`
`
`
`IEEEMultilvledia
`
`
`
`34
`
`

`
`Multimedia documents
`
`An interesting capability is enabled by the
`DIVE Web interface. Apart from the fact that ini-
`tial descriptions of DIVE worlds and objects may
`be read via Web protocols in VRML'° or DIVE. for-
`
`mat, general-purpose multimedia {Mime} ‘docu-
`ments can be presented by external tools. In this
`way, a DIVE world can contain virtually any
`multimedia document, including-MPEG movies
`and bitmaps, that can be activated by DlVE‘.fTcl
`scripts. Sound is especially useful in a VE, since it
`can enhance worlds: the sound of a door opening,
`the click of a button, and background music.
`Further, a standard Web browser can be inter-
`faced to DIVE so that the browser accesses "tradi-
`tional” 2D documents while VE documents are
`
`traversed in DIVE. This arrangement resembles
`the approach taken by many VRML viewers.
`Let us now proceed to the distributed domain.
`First I'll discuss general issues, then describe how
`DIVE entities are distributed and how networking
`capabilities are used.
`
`Networking issues in shared VEs
`Many existing approaches to i/Es are inherent-
`ly single-user approaches extended to the multi-
`user domain. These systems might offer some sort
`of primitive distribution mechanism such as asyn-
`chronous message passing, which gives little help
`to a programmer because all distribution and
`synchronization problems must be dealt with
`explicitly.
`We believe that a distributed multiuser VE sys-
`tem should be designed from the start to be fully
`distributed, with the focus on performance and
`scaling considerations.
`
`Programming distributed applications is diffi-
`cult because of their inherent concurrency. This is
`especially true when objects are fully distributed
`and any process in the system can access them.
`Consistency requirements include {loosely} that
`all processes see the same data and that corrup-
`tions do not occur because of concurrent modifi-
`
`cations of the same data. Several techniques exist
`to ensure consistency, such as distributed trans-
`actions, distributed readlwrite locks, and so on.
`
`One important performance criterion for dis-
`tributed VE systems is latency, that is, the time it
`takes for a message to reach its destination.
`Network latencies range from under a millisecond
`On local area networks up to several hundred
`milliseconds on a wide area network. A related
`
`Performance factor is throughput. On a network
`With bounded bandwidth, only a limited amount
`
`of data may be serviced per time unit.
`It is therefore important to design the distribu-
`tion architecture of distributed VES so as to mini-
`
`mize latency. At the same time, the applications
`should not violate the bandwidth limits of the
`
`internetwork, since doing so causes congestion and
`loss of packets, or overrun of the receiving hosts.
`
`
`
`Xl‘lCLl'SE
`
`Distribution techniques
`A client-server application is based on an asym-
`metric model where a large set of clients connect
`to a small set of servers, often only a single server.
`Repiicas of data reside on servers, from which
`clients request the data. Updates from clients are
`sent to a server before they are distributed to or
`requested by other clients. Thus each message
`must be sent at least twice, which might increase
`latency. Client-server architectures have an advan-
`tage, however: Consistency requirements are eas-
`ily satisfied, since data is modified centrally and
`then distributed to clients.
`
`In peer-to-peer distribution, each peer in the
`distributed environment communicates with
`
`other peers on an "equal" basis. Replicas of data
`exist in each peer, and updates need only be sent
`once. A common peer-to-peer distribution tech-
`nique is full replication, where each participating
`peer actively manages its own complete copy of
`the data. Applications modify data in what they
`
`perceive as a shared database, while modifications
`are transparently distributed among all peers. Full
`replication achieves a high degree of availability
`(no need for remote access) and some degree of
`fault tolerance. It is also conceptually simple.
`
`Figure 6. Example ofn
`user nrterfnce and a set
`of vehicles and actors.
`The three buttons in the
`
`foregromrd are placed
`on an invisible visor
`
`belonging to the viewer.
`
`
`
`966i.5“!-Ids
`
`35
`
`

`
`Multicast protocois potentially use network
`resources better than unicast protocols and thus
`
`{indirectly} reduce latency and increase through-
`put on a network with limited resources. (Note
`that multicast on a transport level, such as reliable
`multicast, may or may not utilize network-level
`multicast.) In a clientlsingle-server architecture,
`multicast provides no benefit when the client
`communicates with the server, since there is only
`one recipient. However, multicast can be used
`when sending to a group of peers, such as in serv-
`er-to-client and peer-to-peer communication.
`Therefore, peer-to-peer distribution combined
`with network-level multicast minimizes latency
`
`and uses system resources well. Thus it is a suit-
`able distribution technique for large-scale distrib-
`uted I/Es.
`
`How VEs scale
`
`As the number of peers increases in a distrib-
`uted VB system, the number of messages needed
`to communicate between these peers increases.
`This increases the load on sending and receiving
`peers, as well as on the network. A system is
`scaierrbie if it can handle a large number of peers
`before its overall performance degrades. Even with
`network-level multicast and peer-to-peer commu-
`nication employed, a system might fail to scale.
`Perhaps the most important scaling criterion,
`then, is how the application itself is designed.
`For example, a distributed VE system using
`unreliable multicast might scale better than one
`using reliable multicast. This happens because reli-
`able multicast protocols using positive acknowl-
`edgments
`suffer
`from the "ack implosion”
`problem-—even though the data is sent by multi-
`cast, the acknowledgments are sent using point-to-
`point messages from each receiving host, leading
`to an increased number of messages as the number
`of peers increases. In reliable multicast protocols
`using negative acknowledgments, or necks,
`receivers send nacks when they discover that pack-
`ets have been lost. This approach has more poten-
`tial for scaling, but it is an ongoing research
`problem to find plausible solutions that scale well.
`Applications can send less information, for
`example by employing compression or using
`dead-reckoning techniques, where kinematic
`equations of the objects may be used to locally
`compute successive positions and orientations.
`DIS-based systems, for example, employ dead-
`reckoning techniques.“
`
`Another technique is to receive less informa-
`tion. In an "optimal" application, peers only
`
`receive exactly the data of interest to them. If the
`data is partitioned in some way, each partition
`can be sent on a separate network connection,
`Then hosts need only process messages from
`those connections of interest to them. In fine-
`
`grained partitioning, a process could, for example,
`register interest in specific objects or even aspects j
`of objects, and then receive updates to just that set
`of objects. In a coarse-grained partitioning, data
`could be separated in disjoint sets, for example
`into completely separated worlds, or partitioned -
`into geographical areas.’
`|
`Whatever the approach, future distributed VE
`systems will require hundreds or thousands of
`multicast addresses that can be simultaneously 1
`connected.“ in comparison, current network
`interfaces have a relatively low limit on the num-
`ber of multicast addresses to which they can con- '
`nect simultaneously. In the case of IP multicast,“
`it
`is unclear whether thousands of multicast
`
`addresses per application are feasible. Despite an‘
`extended address space, routers might not be able I
`to handle the required amount of state.
`Hierarchical encoding techniques provide a
`plausible approach, in which several leveis of res-
`olution are sent; the highest levels are discarded
`at gateways with limited bandwidth. However,
`
`this method might be hard to carry out when the]
`degree of resolution requires knowledge of appli-'
`cation semantics. For example, a peer might want
`low resolution for objects further away in virtual
`space and high resolution for objects that are
`close. But being far away in virtual space might
`have no correlation with being far away in "net-
`working” space.
`Many of the scaling issues in distributed VEs
`depend on how the application is designed.
`Increasing network capacity and processing power.
`make distributed VE. systems possible, but to sup-
`port hundreds or thousands of simultaneous users
`requires software solutions to decrease the num-
`ber of messages.
`
`Distribution In DIVE
`
`DIVE addresses scaling considerations by using-
`a negative acknowledgment reliable multicast pro
`tocol, partial replication, and a simple dead—reck-
`oning module. The distribution model‘ is based
`on peer-to-peer distribution, multicast protocols,
`and coarse-grained partitioning of data. Peers
`connected to the same multicast group interact by
`making concurrent accesses to replicated data
`(entities) and by sending messages. Messages
`addressed to a group are relayed by multicast pro-
`
`IIEEEMuItiMedia
`
`
`
`

`
`I
`
`I
`
`r
`
`i
`
`r
`
`J
`
`3 JOEL-1'3‘: "°—
`
`130
`
`100
`
`80
`
`60
`
`40
`
`20
`
`fr['.«:1aic,ss]
`
`
`
`Since several approaches exist on this issue, the
`semantics of object replication is not part of the
`core DIVE system. Typically, objects are requested
`based on visual range, such as all objects seen by
`an actor, or collisions, such as detected by a colli-
`sion manager controlling a geographical region.
`When a DIVE peer intends to join a world, it
`contacts a name server in order to retrieve a multi-
`
`cast address and thereby join a session. An initial
`world description might exist on a remote system,
`accessible by a universal resource locator (URL).
`However, only the first member of a session loads
`the initial description—all subsequent members
`request world state from an already connected
`peer. The new peer requests initial world state
`over the multicast address and receives an up-to-
`date replica from the closest peer with the latest
`version of the world. This brief initial world state
`
`contains bounding box approximations that serve
`as input on which entities can be requested.
`Since partial replication means that not all
`state is replicated at each peer, data can be lost if
`peers leave the group. In a fault-tolerant applica-
`tion, therefore, the partial replication scheme
`might not be adequate. In this case, a world serv-
`er can keep track of all events in a group and log
`changes to persistent storage.
`To keep the number of messages low, DIVE
`also implements a simple dead-reckoning module
`based on linear and angular velocity. These work
`fine for regular motion, such as vehicle models,
`but such a simple model cannot correctly define
`general human motion.
`
`Sample session
`Figure 7 illustrates a sample DIVE session,
`
`50
`
`Figure 7. Traflic
`received by one peer in a
`DIVE session with three
`
`pm'tic1'pm1t.s. Elapsed
`time is shown on the x
`
`axis, wlrile the received
`
`rate in Kbytes per
`second appears on the y
`axis.
`
`
`
`96-ISLfiuuds
`
`37
`
`tocols to each peer.
`Earlier versions of DIVE use a full replication
`model where peers communicate by a reliable
`multicast protocol using positive acknowledg-
`ments. This approach worked fine for to peers in
`one simultaneous session on a local area network,
`
`but failed beyond this limit. (Note, however, that
`several worlds can run in parallel as well.).Current
`versions use par