Evaluation of some Network Architectures for KIP II
AUTHOR:Gerd Döben-Henisch/ Leo Pos
FIRST DATE: February 12, 1996
DATE of LAST CHANGE: February 12, 1996
REMARKS: The hardcopy MS contains additionally tables and diagrams
-Introduction
-The local world of KIP I
-Central data base with local copies
-Open Set of processes
-Distributed copies only (DIS, NPSNET IV)
-Conclusions
The paper received many contributions by the comments and critics of Markus Fix, Peter Frank, Tobias Kirchhofer, Sevo Stille,
Thore Swindall, and Detlef Woltmann.
We discussed these topics also in some sessions of our unplugged heads seminar: Febr-2
and Febr-9 1996.
Introduction
From the point of view of the logical concept of the knowbots it would not be necessary
to consider questions like `which operating system', `which programming language',
`scalability', `kind of network', `latency', etc. But because we want to use the
technology of the knowbots later on in a serious way it is recommended to spent some time
for these questions now. To develop the knowbots will in any case need much time.
Thus to select an appropriate context in the beginning will save us the time which
we would need otherwise to transport the elaborated solution later on to another context.
Indeed, there exists already some knowledge about the pros and cons of different
architectures, not to forget our own prototyp of KIP I.
The realization of the above postulates means a mapping of this concept onto a physical
structure. As physical structure we assume some hosts
which are connected through a network. Every host supports at least one process
with a unique process number PRN
and a unique portnumber PON
. Every host has in the network also a unique network-address NAD.
In what comes next we will focus ton the question how big is the load on a certain
network architecture presupposing the activity of a certain logical model. Especially
we want to know which configuration produces the minimal load.
We will consider the following four configurations:
- We have a strong client server architecture where the server manages the world process
and the clients (knowbots, pseudoknowbots, other agents) communicate actions, sensory
data and world updates with the server (KIP I, most other implementations known today).
- We have a weak client server structure where there still exists a central data base
but all clients have a copy of the world data. The clients do all computations. The
central data base is only used to coordinate the changes induced by actions, i.e.
the server guarantees the consistency of the changes (some analogy to transaction systems).
- We have an dynamic open set of processes each representing an individual object. The
objects communicate by messages (suggestion by markus/ peter).
- The client server structure is gone. There is a dynamic open set of hosts each managing
a complete world data set, and the relative consistency is provided by the exchange
of movements (DIS, NPSNET IV). One has to distinguish three subcases: using broadcasts, using multicasting without or with partitioning.
The evaluation is based on the following general assumptions:
- A world
consists of a terrain database, a type list, an object list, and an agent list. Wheras
the objects and the agents can change during a simulation is the terrain database
and the type list assumed to be fixed. It is assumed that the terrain data and the
type list are always available and have not to be communicated through the network. A
standard terrain database is assumed to occupy 50km x 50km, 1m = 100 points.
- A worst case scenario
is assumed with a framerate of 10 frames per second. The mean active time of an agent
is assumed to be 15 minutes. The mean cross rate of an agent in a partitioned world
is also assumed to be 15 minutes. Every agent is full active. The mean rate of change of objects is given by the ratio AgentNumber/ObjectNumber. The mean distribution
of agents and objects in a partitioned world is assumed to be 10%.
I
The local world of KIP I
In KIP I we had chosen a client server architecture where the server manages the
world data including all processing related to collision detection and sensory data.
The clients (knowbots, pseudoknowbots, other agents) transmit action data to the
world and they received success-messages, sensory data, and world updates.
A load will be induced in the network by new entrant learning, by world updates,
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.
- TerrainName := Name of the used terrain database, 4 Bytes.
- ObjNumber := Number of objects in the world, 4 Bytes.
- ObjSize := Data necessary to describe a concrete object presupposing a type database.
[Position+Type+Index+(PartNumber*PartSize)]. (:= 152)
- Position := <x,y,z>, 12 Bytes.
- Type := 4 Bytes.
- Index := 4 Bytes.
- PartNumber := 4 Bytes (for non animated objects we assume a worst case of 5 parts)
- PartSize := (Position+Type+Orientation)
- Orientation := <r1, r2, r3>, 12 Bytes.
- AgNumber := Number of agents in the world, 4 Bytes.
- AgSize := Data necessary to describe a concrete agent presupposing a type database.
(Position+Type+Index+(PartNumber*PartSize)). In case of animated objects we assume
a worst case of 78 parts. (:= 2196)
World update learning:
All clients, expecially pseudoknowbots, which offer a view into the world have to
update their view regularly. It is assumed that the update data are restricted to
the actual area of interest of the agent. [((ObjNumber*ObjSize*DistrObj*ChangedObj)+(AgNumber*AgSize*DistrAg*ChangedAg))*10*AgNumber]
- DistrObj := distribution coefficient of objects in the area of interest. [AOI/(Area/ObjNumber)].
- AOI := area of interest of an object. Worst case is a biological organism with 10*10
meters.
- Area := plane of the terrain; it is assumed to be 50km * 50km.
- ChangedObj := part of the set of objects which have changed compared to the last message.
[AgNumber/ObjNumber].
- DistrAg := distribution coefficient of agents in the area of interest. [AOI/(Area/AgNumber)].
- ChangedAg := part of the set of agents which have changed compared to the last message.
Worst case assumption = 1 (:= all).
Change induced by actions:
Every time an agent announces an action, he will receive back sensory data and a
success message. [(Action+Success+Sensory)*10*AgNumber]
- Action := [Type+Index+(PartNumber*AgSize))]. We assume a part number of 78. (:= 2204)
- Success := [(PartNumber*AgSize)]. We assume a part number of 78. (:= 2196)
- Sensory := We assume 1000 Bytes (smell, hear, touch, taste, up to ten sources each).
(In the original source comes here a table showing the needed bandwidth in Mbps with the parameters agents and objects.)
With regard to some common bandwidth we get the numbers: (9A - 6.000 - 3.92Mbps),
(205A - 1.000 - 89.72Mbps), (2700A - 1.000 - 1.45Gbps), (8.100A - 10.000 - 4.88Gbps).
II
Central data base with local copies
The concept of a weak client server structure is motivated by the idea that one should
(i) reduce the exchange of world data and send only change data; (ii) keep a central
database to guarantee consistency of the world data base.
We make the following assumptions:
Every client holds now his own copy of the world data and he computes collisions and
sensory data by himself. Also he can update his view without asking the server. But
to guarantee consistency he sends all his action data to the server who has to maintain a consistent world data base.
The server with the central data base CDB
consists of the following elements: (i) a list AW of all the actual agents, (ii) a original world file W and an actual copy
W' of W; (iii) a command stack CS
which queues all requests and an additional preference pointer PP,
which will represent an agent which is locking W' for writing; (iv) to keep the consistency
we have to assume that every action has to be preceeded by a LOCK-causing reading
of W'. Thus at any time can only one agent cause a change in W' while all the other
agents have to wait with their computations. The general protocoll will then be the
following sequence: an agent writes to CS. If PP is UNLOCKED then will PP catch the
agents name and the agent will receive a positive feedback, otherwise nothing. In the
positive case will the agent then realize his planned action locally and the CS with
his action will be processed. The action will be interpreted and the changes will
be written into W'. The server will then send a broadcast (or a multicast) to all other
agents and will sent the status of PP to UNLOCKED.
This architecture has its weak point in the locking mechanisms which can become the
main bottleneck of the network. The critical point is the ratio between the mean occurrence time of a request
[motr] (mean command time/number of agents) and the whole individual operation time
[wiot]. As long as motr/wiot >= 1 there will be no queue. If motr/wiot < 1 then there
will be more request during a timeintervall then can be satisfied. Therefore the
queue will growing larger. Every system will have its critical number of agents
where this will happen.
Let us look to the kind of data which are exchanged between W' and any client.
- ACTION message causing a change (2204 Bytes).
- FEEDBACK message for client (12 Bytes).
- CHANGED ACTION message for others ((2204+10) (assuming multicasting)
- Framerate 10 frames per second.
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, will receive a
positiv feedback and the server will transmit his action data also to all other agents.
[(Action+12+Action)*10*AgNumber]
(In the original source comes here a table showing the needed bandwidth in Mbps with the parameters agents and objects.)
With regard to some common bandwidth we get the numbers: (9A - 61.500 - 3.92Mbps),
(205A - 60.300 - 89.75Mbps), (2700A - 100.000 - 1.45Gbps), (8.100A - 68.500 - 4.88Gbps).
III
The world as an open set of processes
Close to the aforementioned case is a proposal newly introduced into the discussion
by Markus Fix and Peter Frank. It does not yet exist as a known implementation of
this idea.
In this proposal there exists no special world process; we have only an dynamically
changing open set of processes where each process represents an object, static as
well as dynamic, guided as well as autonomous. These processes are connected to the
network and they have certain ports for dedicated tasks.
Ideally this model should work without any geometry, but as the discussion until now
revealed, some metric space is necessary, because an object is not able to compute
a spatial relationship to another object without it.
To solve the problem of a consistently shared metric space we can imagine the following
alternatives:
We have a central data base managing a list of network addresses and areas.
Every process possesses an actual list of network addresses and related areas.
There exists a preestablished coding scheme mapping geometrical areas into network
addresses
Continuation
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