IV
Distributed copies only
The last configuration illustrates a network where every host has equal rights. Every
host holds a complete copy of the world data, does all necessary computations and
has only inform the other hosts if he is doing an action which will change the world.
Concrete models for such network configurations exists as SIMNET, DIS (IEEE 1278)
and NPSNET IV; this are recent developments of the US Navy. The NPSNET IV is a enhancement
(since 1992) of DIS. A very good introduction can be found in Macedonia, Michael
R. "A Network Software Architecture for Large Scale Virtual Environments," Ph.D. Disertation,
Naval Postgraduate School, Monterey, California, June, 1995, and NPSNET IV.7J Programmer
Guide, Naval Postgraduate School, Monterey, California, June, 1995 (see: NPS Homepage).
The following example is nevertheless not an exact copy of the NPSNET IV architecture.
The public available parts of the documents are lacking very often necessary details.
Ax.1:
The world
can be flat (but with a non-flat surface) or elliptical.
Ax.2:
Connected to a world exists a collision algorithm
which operates on different levels (candidates, cylinders/spheres, polygons/finite
elements). At the polygon/finite element level we have a complexity-measure of O(n^2)/
O(n^3).
Ax.3:
There is no central world-model
, instead the world-model is distributed
; every agent possesses a complete individual copy. Any agent shows up in the world-copy
of another agent as a ghost
. The ghost acts like the original agent. A world computes the behavior of it's ghosts
with a dead reckoning algorithm
by taking the last position with the last velocity and last heading for granted.
Because every agent applies dead reckoning also to himself he can detect the point
at which his real position is different to his computed position by some predefined
deviation. If this happens he will send a correction message
to all other members of his group. The message will be send by using multicasting
.
Ax.4:
Every message between agents conforms to a Protocol Data Unit [PDU]
, to an active stream
or to a reference pointer
. Depending on the importance of the message will the message be sent in a reliable
way (IP) -only a few- or in an unreliable
way (UDP) -default-.
Ax.5:
Because the everlasting target is to keep the latency below 0,1sec
one can today under normal conditions not work with the internet
, but with LANs like e.g. Ethernet (10 Mbps), or FDDI (100 Mbps), or combinations
of several ISDN-lines. If one wants to include the internet one has to activate MBones
with especially dedicated lines with a high bandwidth.
Ax.6:
A possible basic structure of a single host could be the following one (In the original source you will find here a diagram):
The user interface
allows an input at least by a keyboard and a mouse; additionally there can be special
input devices (space ball, tabletts, microphone, tec.). The output to the user contains
at least a graphic screen and an audio-speaker. The main process is the application process
; in the main loop of the application program it will check user input and net input,
then it will compute the next state of the world by computing the movements and
possible collisions, and, if necessary, it will send some messages to other hosts.
If the application program has completed its main loop the cull process
can start to calculate a view for the user with respect to the user's point of view.
If this has be done, then can the draw process
take over and he can compute the final image. There exist two main data structes:
the object data base and the terrain or world database. The object database
contains a list of objects and a type list. The world data base
has to represent the world with all the graphical, acustical and sensorical informations
needed. This data base is usually organized as a complex tree.
NSPNET IV is specialized for SGI workstations. For KIP II we try to keep the model
as independent as possible. We want to use HP-UX, LINUX, MS Windows95, IRIX, a WWW-Browser
(Netscape with Java), and eventually NextStep.
AX.7:
The network protocol uses IP Multicasting
. This presupposes that every participating host is able to handle multi cast packages.
Every LAN needs additionally a dedicated mrouter
. The mrouter manages the actual multicast addresses. A host can send a message to
join
or to leave
a multicast group. A mrouter can forward multicast packages to other subnets and
he can occasionally poll the known addresses to check whether the individual host
is still alive. Every host can join more than one multicast group.
Ax.8:
One can further enhance IP multicasting with a partitioning mechanism for every host.
This is done by the area of interest manager [AOIM]
. The AOIM computes a virtual hexagonal partitioning
of the surface with a default radius of 4 km for every hexagon (the radius can be
changed). Then one has to assume a fixed mapping between hexagonal cells and IP-numbers
of class D, i.e. every hexagonal cell can be associated with one multicast group.
The eldest member of a group is the group leader
. The group leader has a list of all active members. Every new member has to communicate
with the group leader his entrance and will receive the list of the other members.
If an agent leaves one hexagonal cell and enters another one he has to change his
multicast group by announcing this change. Any time when a local agent of a host enters
a hexagon the agent will send a `leave group' to the old group leader and a `join
group' to the mrouter. Then he will send a `request for data with his reference'.
If there comes no answer, he is the first and single member of the new hexagonal cell
and the single member of the multicast group. The agent will then set up a list of
all members. If the request for data is positiv the agent will receive data about
all the actual members of this group together with all the necessary information about type,
name, position, orientation, kind of movement, and velocity. In turn will the new
member send his data to all members of the multicast group.
Moreover is the local agent correlated with an area of interest AIM
which consists of the at least hexagon where he is actually in and all the adjacent
cells. The host listens to all multicast groups of the AIM, but he will send messages
only to the one multicast group to which the local host belongs.
AX.9:
It is possible to dynamically change a world
by unmounting a world and loading a new one. The handling of interferences between
to different worlds which have shared boundaries has not yet been solved.
Broadcast version
The DIS implementation does not use IP multicasting and not partitioning. If an agent
has to announce an action he has to make a broadcast which results in n-1 packages
which have to be send through the network.
A load will be induced in the network by new entrant learning and by changes induced
by actions. The following formulae compute the load per second measured in bytes.
New entrant learning:
[((TerrainName + (ObjNumber*ObjSize) + (AgNumber*AgSize))*AgNumber)/MeanActiveTime].
Every time when a new client becomes a new inhabitant of the world he has to undergo
a new entrant learning.
Change induced by actions:
Every time an agent announces an action, he will send action data to all other agents.
[Action*10*(AgNumber-1)*AgNumber]
(In the original source you will see here a table showing the bandwidth measured in Mbps according to the active agents and objects).
With regard to some common bandwidth we get the numbers: (5A - 72.000 - 4Mbps), (23A
- 26.500 - 89.62Mbps), (91A - 90.000 - 1.45Gbps), (167A - 60.000 - 4.88Gbps).
If one uses dead reckoning
then one can reduce the rate of action messages. We assume the formula:
Change induced by actions (+DR):
Every time an agent announces an action, he will send action data to all other agents.
[Action*10*DR*(AgNumber-1)*AgNumber]
(In the original source you will see here a table showing the bandwidth measured in Mbps according to the active agents and objects).
With regard to some common bandwidth we get the numbers: (5A - 280.000 - 4Mbps), (23A
- 1.167.500 - 89.79Mbps), (91A - 4.800.000 - 1.45Gbps), (167A - 8.700.000 - 4.88Gbps).
Multicast version
The above mentioned bad behavior of a broadcast architecture was the main driving
force to find an improvment. There are basically two ideas which can minimize the
problem.
The first idea makes use of the fact that in most cases a moving agent will affect
only a few objects in his immediate neighbourship
. Thus it would not be necessary to load the data of all the other objects which are
not in the actual cell. The second idea exploits technical features of the network
software insofar it is possible to gather sets of hosts under one group address
called multicast address
. With this technique it is possible that a host sends one message and there will
be as many recipients as there are members of such a multicast address.
Multicast without partitioning
Let us first examine the case where there exists only one group.
New entrant learning:
[((TerrainName + (ObjNumber*ObjSize) + (AgNumber*AgSize))*AgNumber)/MeanActiveTime].
Every time when a new client becomes a new inhabitant of the world he has to undergo
a new entrant learning.
Change induced by actions (+DR, +Multicast)):
Every time an agent announces an action, he will send action data to all other agents.
[Action*10*DR*AgNumber]
(In the original source you will see here a table showing the bandwidth measured in Mbps according to the active agents and objects).
With regard to some common bandwidth we get the numbers: (9A - 251.000 - 4Mbps), (205A
- 242.900 - 89.71Mbps), (2700A - 282.000 - 1.45Gbps), (8100A - 251.000 - 4.88Gbps).
Multicast with partitioning
Let us now examine the effect if one additionally tries to incorporate a partitioning
into small subgroups by neighbourship. How does one define the `neighourship' of
an agent? You could use some radius with respect to the actual position of the agent,
but if you would try to map such a region consistently to some IP number you would
be lost; the partitioning would highly depend on the individual positions. Thus one
needs a partitioning of the terrain which is independent of the individual agents.
In the NPSNET IV architecture this is done with a hexagonal partitioning. Every hexagonal
cell is indexed by a unique pair (i,j) of column and row numbers which have a fixed
relationship to the underlying geometrical coordinate system. Then you can establisch
a unique mapping of those cells into the set of D-class IP numbers. At the moment will
this work only for `one party at the same time' and also only for areas which are
not bigger than 256 x 256 hexagons. If b1.b2.b3.b4 is the IP number, then one could
use B3 and B4 for the encoding of row and column and B1 and B2 to disthinguish between
parties or worlds.
Group management means: One has to install a group leader
(eventually the oldest member
of a cell), and then one has to practice a certain protocoll when an agent does change
from one cell to another, the `new' cell. With the new cell-coordinates he will have
the multicast address of the new cell. Then he can send a `request for data' along with his individual IP address (about 10 Bytes). If he will get no answer he can
assume that he is the only member; then he will be the group leader and he has to
manage a list of all group members. If the agent will receive an answer, then will
this answer contain all the necessary informations about all the other members. In the worst
case he will get 2196 Bytes * (n*(d/100)-1). The question is how often this will
happen. If you have biological agents like humans walking by feet and they are working
`normally' it is not very likely that they change their cell during 24 hours, if we assume
a cell radius of 4km. If they are using cars in a city with a `real velocity' of
17km/h, then they will change cells at a rate of about 4 cells/h. Let us takes this
last case as our `worst case'. Furthermore, if the agents receive a feedback with all
the data he has himself to send his indivual data to the group: 2196 Bytes. We get
therefore the complete formula 10+(2196 Bytes * (n*(d/100)-1))+2196 for one agent
when he is entering a new cell. If every agent has a change-rate of (60/4)*60 sec, then will
at every ((60/4)*60)/n sec an agent change it's cell.
We assume the following formulae:
New entrant learning:
[((TerrainName + (ObjNumber*ObjSize*DistrObj) + (AgNumber*AgSize*DistrAg))*AgNumber)/MeanActiveTime].
Every time when a new client becomes a new inhabitant of the world he has to undergo
a new entrant learning.
Area change:
[((AgSize + (ObjNumber*ObjSize*DistrObj) + (AgNumber*AgSize*DistrAg))*AgNumber)/MeanAreaChangeTime].
Every time an agent crosses a section he will send his data and he will receive as
many data as objects and agents are in this cell.
MeanAreaChangeTime: 15 minutes.
Change induced by actions (+DR, +Multicast)):
Every time an agent announces an action, he will send action data to all other agents.
[Action*10*DR*AgNumber]
With regard to some common bandwidth we get the numbers: (9A - 2.505.000 - 4Mbps),
(205A - 2.479.500 - 89.72Mbps), (2700A - 2.830.000 - 1.45Gbps), (8100A - 3.036.000
- 4.88Gbps).
(In the original source you will see here a table showing the bandwidth measured in Mbps according to the active agents and objects).
Besides spatial classes
(introduced by the partitioning) one could also use temporal or functional classes;
these have not been taken into account here.
Conclusions
The worst results are obtained by the distributed broadcast case without dead reckoning.
Dead reckoning improves the results by a factor of 3 to 146 in the object dimension.
If one compares KIP I with regard to objects and with agent numbers and bandwidth
fixed against the weak client server solution and the multicast version of the distributiv
case with and without partitioning one gets:
1 : 15.13 : 147.96 : 1507.65
These ratios tell us to which degree the different version are more efficient in using
the available bandwidth.
Nothing is said here about the computational burden.
With regard to KIP II it is clear that one should at least adhere to the distributed
configuration with multicasting and dead reckoning. A partitioning should be considered
for large applications.
Comments are welcomed to kip-ml@inm.de
Daimlerstrasse 32, 60314 Frankfurt am Main, Deutschland. Tel +49- (0)69-941963-0, Tel-Gerd: +49- (0)69-941963-10