Transcript M*N - UCL Computer Science

Network Topologies for Scalable
Multi-User Virtual Environments
Lingrui Liang
Syllabus
Introduction
Related work
Network characteristics
Network topologies
Experimental result
Conclusion
Introduction
Network bandwidth and graphics
performance are increased, distributed
visual simulation systems are allowed
multiple users to interact in a shared 3D
virtual environment(VE)
Workstations run 3D graphics interface
program to simulate the virtual
environment, each user can be a role to
see other roles via wide-area network
Introduction
 Avatars controlled by users and kept the
newest information in the workstation
through messages
 Support: visual interactions bewteen
multiple users in a shared 3D VE
Applications
Distributed training simulations
Virtual meetings
Collaborative design
Multiplayer games
Challenge
Keep consistent state among a larger
number of workstations
E.g. One entity moves or modifies the
shared environment, an update must be
applied on each workstation
N entities move, M times per second.
Updates should be M*N per second to a
shared database
Goal and Aim
Goal: trade-offs of different network
topologies and messaging protocols for
multi-user virtual environments
Aim: represent the design of system that
can support very large numbers of users
at the same time
Related Work
A virtual environment is represented by
these systems as a set of independent
entities. Each entity has a geometric
description and a behaviour
Types of entity:
Static entity
Dynamic entity
Related Work
Conditions for activating distributed
simulation with multiple entities interact in
a shared VE:
Sending message to one another to update the
geomotry or behaviour of entities
Modifications to the shared environment
Impact on other entities
Related Work – Entity Management
Every entity is managed by one of the
workstation in the distributed system
Workstation may map user input to control
of entities and may include viewing
capabilities
To manage its own entities (local entities),
each workstation maintains surrogate for
some entities managed by other
workstation (remote entities)
Related Work – Surrogate
It contatins representations for the
geometry and behaviour of entity
If a workstation receives an update
message from a remote entity, it will
update the geometric and behavioural
models for the entity’s local surrogate
Surrogate behaviour is simulated by each
workstation in the processing of update
Communication Mode for Network Nodes
Four routing schemes:
Unicast
Multicast
Broadcast
Anycast
Unicast
 Unicast transmission is the sending of information
packets to a single destination
 E.g. Reality Bulit for Two, VEOS and MR Toolkit are
based on unicast peer-to-peer
Multicast
 Using multicast to send update message to a subset of
participating workstation. The general idea is to map
entity properties into multicast groups, and send update
message only to relevant groups
 E.g. NPSNET and DIVE are multicast peer-to-peer
systems
Broadcast
 Broadcast refers to transmitting a packet that will be
received by every device on the network
 E.g. VERN and SIMNET are broadcast peer-to-peer
systems
Anycast
 Anycast is a network addressing and routing scheme
whereby data is routed to the "nearest" or "best"
destination as viewed by the routing topology
 E.g. DNS and IPv6 are based on the anycast systems
Client-Server System
Communication between client workstation
is managed by message server with
intelligent server message processing
Key feature of client-server design:
servers can process messages before
propagating them to other cilents,
selecting, augmenting, or modifying
messages
Example for Client-Server Design
A server may determine to send a
particular update message only to a
relevant small subset of clients and then
broadcast the message only to those
clients and their servers
It can be applied to many users at the
same time
Client-Server Design
Motivations:
To support modem connections to clients
To simplify implementation
Assumption: a client can send a message
to any one or set of clients and/or servers
at any time
Result: with better processing and
messaging properties, a variety of
alternate system topologies are possible
Network Characteristics
 Communication between workstations
participating can be implemented by a various
possible network with different features
 Logical networks:
Transport is oriented connection or connectionless
Message delivery is unicast or multicast
Message latency
Data bandwidth
Wide-Area Network - Connections
Connections:
data exchange between two workstations
two-way, oriented connection, unicast transport
low latency and low bandwidth(14.4Kb/s or
28.8Kb/s)
e.g. A network is a modem using a standard
telephone cable
Wide-Area Network - Unicast
Unicast:
random number of workstations are connected
to a network logically
the network supports connectionless and
unicast messages
e.g. Internet
Wide-Area Network - Multicast
Multicast:
random number of workstations communicate
with each other with connectionless and
multicast messages
e.g. Mbone(Multicaste Backbone)
Network Characteristics
Different networks can be constructed
using combinations of different types of
networks
Each combination can affect the design of
the multi-user virtual environments
systems
Basic Concept - Network Topology
 Network topology is
the study of the
arrangement or
mapping of the
elements of a network,
especially the
physical (real) and
logical (virtual)
interconnections
between nodes
Peer-to-Peer Topologies
Arranged system with a set of
workstations
Communication method: peer-to-peer
(P2P) directly
Peers send a unicast message to other
peers when an entity is updated (unicast
message is available)
Peer-to-Peer Topologies - Unicast
Peer-to-Peer Topologies
Filters must be applied
What for? – Update messages are not
sent to every peer for every update
Peers maintain lists of entities in each cell
Update messages are sent to all peers
whenever an entity moves to a new cell,
mapping must be changed among peers
Peer-to-Peer Topologies
Peers can send a single multicast
message to a subset of peers at one time
(Multicast message is available)
A multicast group can be assigned to each
cell
Peers do not maintain the lists of entities
in each cell, but they join and leave
multicast groups as their entities move
between cells
Peer-to-Peer Topologies - Multicast
Hierarchical Topologies
Hierarchical Topologies = Tree Topologies
A hierarchical topology is created similar to
an extended star topology. The primary
difference is that it does not use a central
node. Instead, it uses ad trunk node from
which it branches to another nodes.
Hierarchical Topologies
Multi-user VE can be designed by this
topology
Each entity’s update, a client sends
update message to server, the it
propogates to other servers and clients
Types of network used for client-server
and for server-server links
Hierarchical Topologies
Properties
Advantages:
Message distribution is shifted out of the client
and into the server
Server: litter processing, storage or messaging
to keep entities consistent in a large VE
Client: precessing, storage and network
bandwidth requirements scale unlimited
Disadvantages
Extra latency may be introduced for each
update message
Communications – Client/Server
 Oriented connection, unicast: each server
manages message distribution for a subset of
clients
 Every entity’s update, client
server,
server
other servers and client with entities,
but maintaining mappings and periodic update
are required
Not scale infinitely
Communications – Client/Server
 Connectionless, unicast: each server manages
message distribution for separate regions of the
VE
 Advantage: fewer server-to-sercer messages
are generated
 Maintaining mappings and periodic update are
also required
 Scales infinitely and server are limited to finite
subsets of the VE
Communications – Server/Server
 Multicast: similar to the P2P multicast system
design
 Region managed by each server is static,
servers do not join and leave multicast group
dynamically
 No periodic update required
 Scales infinitely
Experiment
 VE conditions: 800
rooms connected by
hallways consisting of
23,168 polygons and
2,219 cells
 Runs 256 computercontrolled entites at
the same time
 With 2,4, 8 or 16
servers
Experimental Scheme
 Two schemes to demonstrate the eect of system
design on the message processing requirements
of workstations in a multiuser virtual environment:
A) clients made static connections to one server while
servers passed messages to each other using a
connectionless unicast network
B) clients and servers both passed messages on a
connectionless unicast network, each server
managed message distribution for a separate region
of the virtual environment
Experimental Results
Experimental Analysis
A) the number of servers increased, the
total number of server-server messages
output by each server increased as
separate unicast messages were sent to
multiple servers. This is sublinear increase
B) the number of servers increased, and
the intervisibility between server regions
decreased, server-server messaging was
reduced
Experimental Result
Using B) system design, the message
processing burden of each client and
server can be quite small, and these
systems can scale many users at the
same time
Conclusion
 Characteristics of the networks can greatly impact the
message distribution performance of a particular system
design for multi-user VE
 The results of experiments demonstrate that different
network characteristics and different system designs can
seriously affect the message processing rates required
by workstations in a multi-user VE
 Perhaps, by identifying network characteristics and
system designs that improve the message distribution
properites or decrease the cost of multi-user VE systems,
we can help software and network architects in the
design of future systems