Subject: [Nel] Game Object Models

From: "John Hayes" <[email-masked]>
Date: Mon, 21 Jan 2002 18:47:30 -0500

I read through the archive of the NeL library and found it interesting
because I'm working on my own project and mostly focusing on areas where
NeL is silent.

In the source code, mailing list and documentation - I couldn't find any
references to an application object model or persistence, and these are
pretty big components. It is also the core mechanism for automating
database storage, the network protocol, marshalling and transaction
integrity.

I'll give an example about how the object model relates to the network
protocol:

There was a great deal of discussion about TCP vs. UDP and assuming you
want some form of reliability, UDP gives you control over the frequency
and conditions for retransmission. In terms of server resources,
successful packet transmission time, bandwidth use - they're probably
pretty close (with Nagle Algorithm disabled), and if these were the only
factors you couldn't justify the added complexity.

The problem is TCP is substantially slower for retransmission because it
uses a fairly lazy algorithm to ask for retransmission - it waits a bit
before asking again for a packet. Because there's a connection to make,
timing out and reconnecting is very slow ... like a minute - and the
whole game is halted in the meantime because TCP enforces ordering
despite whatever application level dependencies exist.

Ok, so no TCP, UDP is great but you don't want to reimplement TCP all
over again - reliability is good but you want the minimum number of
packet dependencies (loose ordering so the game doesn't stall) and the
minimum amount of retransmission (discard what you no longer care about)
but conflicting goal of a minimum amount of latency for retransmission
when it's required.

So - what kind of rules can we make up for this? Network messages from
the server to the client have two functions - updating state and
"one-shot" actions (which is really a special case of updating state).

If a character is running along, they have a running state and a
position state that are continually updated. They may also have internal
states like their "tiredness", "hunger" which may be related from the
game logic's POV, but not the client - assuming the client is rather
dumb, or applies simple algorithms like dead-reckoning until it gets an
authoritative update from the server.

Now the packet example, in this and all examples - all failed packet
transmissions (lost, malformed) are considered equal.

Update Position v1
Update Position v2 (lost)
Update Position v3

If the client receives v3, it doesn't care if v2 is lost - for
frequently updating fields, no need for retransmission.

Update Position v1 (lost)
Update Tiredness v1

The client can process the Tiredness packet because it's on a different
"stream" from the position - it may ask for position to be
retransmitted.

Update Position v2
Update Position v1

The second packet is ignored because the client already has a newer
version of the state.

Now this is all very application specific (as was argued on the mailing
list). But software can be pretty good at figuring this stuff out when
given a little metadata to work with, and this is where the object model
steps in.

You have an object model, and you want to replicate part of this object
model to the client, and you want to replicate another part of the
object model to all clients that can "see" your object.

The tricky part can be the granularity for these replications, doing the
entire object at once is very easy and requires no more server state
than a "version flag" but uses a tons of bandwidth - replicating a
single field is very efficient from a bandwidth POV but requires more
server state to manage. A practical system would have property groups
which are considered to be likely to change at the same interval.

---

Here's one possible design for a system to perform this kind of
tracking:

Each object has a version number and everything that attaches has a
dirty mask of which fields are out of date. As an object changes - it
broadcasts the aggregate of fields that changed during a transaction to
each of the listeners, if it matches their listen mask, they get an
update and the object version increments.

The listener transmits all of the fields in the dirty mask to the
client. Client responds which version and which fields are up to date
and if the version hasn't incremented the server clears the dirty mask.
The server could keep a history of which dirty masks applied to which
versions to keep from pathologically retransmitting fields which haven't
changed.

An object model can also serve to tune such a protocol. First by
packaging fields together into mask bits and second by setting times for
each mask bit when the client might get suspicious. If the client is
expected to have the latest data but the latest data may be dropped, how
long should the server wait before retransmitting any given data? If
it's something interactive - not very long, something that's slowly
updated, it should give a reasonably long wait.

I'd hate to be encoding rules like these in source code and it probably
wouldn't be practical in the end anyways.

---

I'm currently working on an object model with these kinds of
capabilities - the major attraction to me is it allows other activities
like network data and persistence to be decoupled from the application.

Right now, it builds the database tables, queries, and C++ classes
(opaque in-memory layout, no code generation) from an XML file like this
extract:

<schema>
	<class name="Entity">
		<field name="template" type="int"/>
		<field name="aspects" type="binary" length="16"/>
		<field name="behavior" type="int"/>
		<field name="name" type="string" length="16"/>
		<field name="children" type="ownsmany" related="Entity"
inverse="parent"/>
		<field name="parent" type="ownsmany" related="Entity"
inverse="children"/>
	</class>
</schema>

---

This is a lot at once, but I'm hoping to stir up some conversation :-)

John
- These aren't the thoughts you're looking for

---

From: Vincent Caron <[email-masked]>
Date: 26 Jan 2002 04:55:38 +0100

On Tue, 2002-01-22 at 00:47, John Hayes wrote:
> The problem is TCP is substantially slower for retransmission [...]

At least you didn't say the famous 'TCP is slow' statement :)
TCP is designed with precise purposes in mind, which are (in order) :
sequential delivering of datagrams and reliability, both making up the
'stream' service delivered by TCP. The notion of 'speed' is somewhat
linked with the notion of reliability : it depends on your viewing
window on the stream. If you expect a large amount of data to be
delivered on a given schedule, then you won't ever notice that some
packets of the window were late because they had to be retransmitted.
The whole was globally on time. When you lower your window and reach the
datagram size, a dropped packet means an immediate bandwidth drop, since
you don't want to consider the following packets until the lost one is
retransmitted.

I believe the 'game model' is actually somewhere in between the stream
and datagram notions. The fact that TCP has been designed with 'long'
(considering our problem) timeouts comes from the congestion pb : all
parameters of TCP have been finely tuned (in every implementation of
TCP/IP stack) for a model that provides good cooperation between network
nodes. TCP will bring sequentiality, reliability, inernet-wide
cooperation, but certainly not delay guarantees, we all know that.

> but conflicting goal of a minimum amount of latency for retransmission

The Internet infrastructure is packet driven : every packet is supposed
to take an impredictable path between constant nodes, every packet can
suffer a variable delay, and finaly packets can be dropped. We have to
live with that, this is real life :)

Sequentiality, reliability, delay and bandwith are all linked. In most
cases you can't raise one without lowering the others. From there you
can progress in two ways :

- find a set of feature above IP (the lowest level you can access with
Internet operability in mind) matching the closest to your needs. Expect
to come up with your own layer 5 protocol over UDP, since it is rather
difficult to 'remove' features from TCP :)

- find the network properties you can live with. This is the most
disregarded path. I'm always wondering why people always blindly try to
implement more or less ackward reliability hacks over UDP, before even
asking if they need reliability. Yes, you often can live with dropped
packets : this is what interpolation and extrapolation is about.
Detecting them is easy, if you numbered your packets for sequentiality.
You might even find yourself dropping a late packet, because you already
have fresher info (depends on the info carried by the packet, of
course).

> "one-shot" actions (which is really a special case of updating state).

Your description is interesting. I won't comment directly on it, instead
I would stress the importance of a dimension that is so commonly
neglected : time.

Considering the kind of real-time info you're mentioning (player pos,
shot, etc), time is a vital info. The pb is that you don't have an
absolute clock that every network node shares. With a synchronization
protocol such as NTP you can achieve 1ms coherence on a LAN, maybe 500ms
on a WAN/MAN if you're lucky, and most of all you'll need something like
1 hour to converge toward this figure ! :)

Until computers can get a pico-second timestamp from a GPS satellite,
we'll have a tough ride. [Well, it is perfectly possible to connect a
GPS device to your computer, but you won't ask this to all gamers... oh,
and why not ?:)]

So we don't have synchronized nodes, and what's worse, we don't know
path time length between nodes, but we know this kind of value is not
constant ! Ouch. Now you replicate a client object on a bunch of target
nodes. What do they get _when_ they receive their copy  ? The state of
the object at a slightly elapsed time. They don't know how much. The
only measure you can get between two nodes is the round time trip (RTT),
ie. the A->B->A time (what 'ping' measure). Since most packet delivery
is assymetrical, you only have a poor estimation of A->B or B->A delays
with RTT/2, and this measure is _not_ constant.

When you realized that every node (clients and servers) have their own,
timely view of the objects, my guess is that you end with two model of
distribution :

- centralized : one (server/master) node is considered to be the only
one to have a full coherent view of all objects at any time. All other
nodes (clients, or let's say more generaly 'slaves') have a slightly and
globally delayed view of the referential view. If you get lucky, RTT 
between master and slaves is homogeneous and you'll end up with tightly
synchronized slaves. You'll only get into trouble when the master must
integrate client responses, since they 1) are a reaction to an info
which is 1 RTT late and 2) a client info which is ~RTT/2 late.

  This approach has well known pb : if a client is notably lagging, he
will contribute only sparse info to the server, and thus to all other
clients. And it's often an advantage for the lagging player, since with
poor inerpolation he will only exist on discrete time-space points of
your scene (ever seen these quake players jumping from places to places
between frames ? :)). But it is easy to implement.

- fully distributed : the 'holy grail' :). In theory, each node is
connected to all the other participating nodes. Of course, it's a
bandwidth killer and it doesn't scale. But there are some points that
make it somewhat conceivable :

 * a node is often only affected by a few other nodes : the players in
sight of your gun, etc. If every node can maintain a 'neighborhood
dependency', you'll end with a finite number of links per node (depends
on your game design, might prove wrong in a virtual stadium :))

 * you might find optimal time paths between nodes. You actually have
the internet model : choose any path to go from A to B ! Clients are not
dependent on a server location/reachability.

- in-between: such as the Fastrack P2P (peer-to-peer) model (Morpheus,
Kazaaa, etc). A server holds a directory of nodes with relevant per-node
info. You get connected to another node when you decided that it has
relevant information for you (Hey, I want this DivX;). Not a real-time
example, but a distribution model. Server themselves can belong to a P2P
subnet, solving the directory scaling pb easily.

Of course the P2P model is in its infancy, and what's important, the
infrastructure is not ready. Multicast would be a blessing for instance,
but it's only integrated in Ipv6, and there will be a long time before
global routers do multicast. You'll also eagerly wait for scheduling
options (again in IPv6, IPv4 has an 'urgent' bit which is ignored by
most routers), they will enable you to choose VoIP-like (real time
behaviour) which would be of course very desirable for MMORPG.

--

Well, just my 2 cents. I had something like that in my head when the TCP
vs UDP debate occured. My main concerns are (as a conclusion) :

- can't you cope with the inherent non-sequential and unreliable
Internet infrastructure rather than applying a TCP-like work around ?

- think 4D, _time_ counts ! I wouldn't talk about a 'replication pb',
rahter an 'information transportation pb'. This is where the strict
object concept fails : an object must be considered in its environment.
An object stored in A at time t0, and arriving in B a t0+t doesn't carry
the same information. Pretty disturbing to locate objects in time and
space, eh ? Time slips, nothing to do about that ... :))

- data/computing distribution is an open problem today. However there
are solutions on many precise applications at very different scales
(Mosix clusters, NUMA, Fastrack, [Internet at the packet level]!), so
why not a good model for MMORPG ?

So long. If I was clear somewhere, you're lucky ;)