[MUD-Dev] Re: DIS: Client-Server vs Peer-to-Peer

[J C Lawrence]

On Tue, 24 Nov 1998 22:06:23 +0100 (MET) 
Niklas Elmqvist<d97elm at dtek.chalmers.se> wrote:

> The subject is the construction of a complete DIS (Distributed
> Interactive Simulations) system with real-time simulators used for
> education as well as entertainment. 

<nod>

> Hopefully, we will be able to come up with a system that will
> accept a plethoria of heterogenous clients (potentially hundreds
> of them) connecting from an unsafe network (such as the Internet)
> and playing in a shared world. 

As you have correctly identified, this is the crux of your problem
(the aspect of the network being unsafe).  

> With enough flexibility built into the system, I am envisioning
> sort of a universal battlefield simulator able to support
> simulations of all kinds of battles -- why not pop onto the net,
> take a look at the current scenarios being played out, and then
> jump into a simulation of Omaha Beach at D-Day, for example? Or
> why not the Battle of Endor, Thermopylae, Hastings or Gettysburg?

AI's dynamically and transparently replaced in an ad-hoc manner by
humans such that protagonists are unable to transparently determine
if their opposition is AI or human?  Neat.

> That's the idea, anyway. Of course, I am concealing all of these
> entertainment aspects in a cloak of respectability; I am not
> entirely sure everyone would approve of a game project! ;)

The better profs (and contract agencies) tend to realise that games
have more demanding technical and performance restrictions than
business-related projects.  

> I am also recommending the project members to release the
> simulator system as Open Source under the GPL at the end of the
> project (GNU Sim?), so hopefully, this quite ambitious undertaking
> will bring something back to the community. You can do a whole lot
> with eight enthusiastic developers in a full year! (Despite the
> fact that we won't be exclusively working on this project.)

> Enough chattering -- this brings me to the problem. The term DIS
> is quite general; for one thing, there is a DIS standard. 

DIS: 

  http://www.pasteur.fr/other/computer/RFC/9xx/994

  -or- 

  http://www.kanga.nu/~petidomo/lists/mud-dev/1998Q1/msg00774.html

> I have some problems with it, though, and I am looking for
> justification of the deviations I want to make from the standard
> (in general, I believe it is a good read). One of the keypoints of
> DIS is that it is a strict peer-to-peer architecture...

DIS has a number of problems for this type of application which can
be mostly summarised into:

  -- Assumes that all nodes are equally trustworthy.
  -- Assumes that bandwidth is free.
  -- Assumes that nodes have infinite resources.
  -- Has no explicit security model (not even an entrance gatekeeper).

Intel used to have a high level discussion of the problems of peer
based designs for multiplayer games, most of which translates into
factorial bandwidth requirements, but they've removed it
unfortunately (used to be at
http://developer.intel.com/drg/hybrid_author/cookbooks/games/).

Related slideshow (nothing new here, just noticed it in passing
while looking for the above doc):

  http://developer.intel.com/drg/news/class6/

The problem is that, pessimally, every node has to coordinate with
every other node, each of which has a highly variant latency
(comparitively and over time) in regard to the local node, and as
regards the same mapping fromn other nodes.  Translation:

  Given:

    The average latency from node X to all other nodes is Y.
    The average latency from node Q to all other nodes is R.
    The average latency from node S to node T is W.
    The current latency from node S to node T is V.

  Y need not have any relation in value to R, which makes "fairness"
algorithms _extremely_ important and non-trivial to get right.

  W need not have any relation to V, and at any instant the actual
values for both are not only unavailable, but a pseudo-heisenberg
ensures that any data you have is stale dated and of uncertain
relevance to current conditions (ack latency).

So, now only do you need to account for the variant latency, you
need to do it why sending and receiving status data to and from N-1
nodes, which, if you have any sort of reactive process in place can
blow your bandwidth requirements out the roof:

  X sends status update to every node.

  Y other nodes repond to the status update with state changes, and
  broadcast their new states.

  Z nodes respond to this new state with their state changes, and
  broadcast state messages. 

Want a really simple example?  Gravity/velocity positions:

  X figures out its current velocity and sends that to all the other
  nodes.

  All the other nodes receive the new position of X, calculate the
effect of X'es gravity on their own velocity and position, and
broadcast that new data.

  __EVERY__ node now receives the new velocity and position data,
computes the effects on themselves (we'll conveniently ignore the
three body problem), and broadcast the results.

And no, you can't use IP multicast/broadcast as a carrier for your
games (alas).

  FWLIW SGI runs their own broadcast backbone inside the company
(separate from the WAN backbone, using Indy Challenge S'es as
routers due to Cisco having terrible broadcast routing performance).
A massively usefull thing.  Almost all the demo games that ship with
Irix, such as Cycles (a Tron bikes clone I've become very fond of),
by default use the broadcast backbone to look for other players so
that at any instant you can't tell which other bikes are being
controlled by AI's and which are actually other people, anywhere in
the company, also playing Cycles.  Its really cute to just install a
fresh OS on a machine and bring up Cycles and _instantly_ and
transparently be part of the mega floating game.

  The multicast backbone also gets used for less interesting things
like broadcasting local radio stations across the net so you can
hear pretty well any local station thru your system's speakers.
Don't see a station you want, want to spread your CD's around, or
have an MP3 collection?  Just install the radio server, and plug
your radio or Cd changer into the audio-in sockets on your Indy or
O2, and Voila!, you are now broadcasting that "station" for
everybody else to listen to.

Conversely moving to a client/server model allows the server to act
as a latency mediator (appropriate use of predictive algorithms
comes in *really* big here).  

> For example, in the DIS standard, the shooting client is
> responsible for reporting the shot and the ballistics to the
> targeted client, but it us up to the targeted client to decide
> whether the shot is a hit or not, and the extents of the
> damages. In a trusted network environment (such as the "safe" LANs
> the US DoD no doubt is using DIS on), this is no problem.  To me,
> however, this instinctively feels like a big stumbling block in an
> untrusted network such as the Internet -- horrible visions of
> Interstate '76 and Diablo multiplayer rise up to haunt me. 

Bingo.  Without a trusted something doing sanity checking its not
going to work, and if you merely to probability checking (X% of all
shots must hit), the level of tolerance you are going to have to put
in to ensure you don't get drowned in false positives is going to
let your cheating players get away with blue murder.

> In a naive DIS implementation running on the devious Internet,
> clients could easily be hacked (especially if the client is Open
> Source) and modified to always tell the shooter that the shot
> missed (or that the damages are minimal). Clearly, this simply
> won't do. (Yes, one in Raph's collection of laws, the one about
> clients being in the hands of the enemy, does spring to mind.)

Do a quick web search on the various hacks to the UOL protocols.
Its been ugly.

> So ATM I am seriously thinking about proposing a client-server
> architecture instead of peer-to-peer. I now need justification for
> this decision. 

Without concentrator points (either central server or hubs
(distributed server or IO-collection points feeding a central
server)) peer-to-peer doesn't scale for low-latency tasks.
Client/server doesn't scale where clients are able to exceed the sum
IO or CPU bandwidth of the server.  Peer models, by their very
nature, assume a level of trust among peers.  That assumption is
explicitly false when dealing with the Open Internet.  Peer models
assume that individual nodes have good connectivity (latency and
bandwidth proportional to the task), and that a node is responsbile
for their own connection characteristics (latency and bandwidth).
Both aspects are false on the Open Internet due to intervening
connection characteristics (eg router between X and Y goes down) or
lack of local 'net control (Denial of Service attack against node or
subnet (a not uncommon tactic with some UOL players is for a player
on a fast connection to swamp a player on a slow connection's link
with large ping packets (eg 64K pings), rendering that player's
character easy prey (they can't run, they can't fight, they can't
hide)).

> Basically, I am looking for all the good arguments why
> client-server should be used instead of peer-to-peer as well as
> the advantages and disadvantages of each approach. 

The above do?

> Some sample questions:
>  - Is it a sound decision (using client-server)?  

Yes.

> - Can peer-to-peer be implemented without a lot of hassle with
> authentication and so on? How?  

Yes.  There are standard libraries and protocols for this sort of
thing.  (SSH and Kereberos come to mind)

> - Is it possible in an Open Source project where anyone has access
> to the source? 

Peer to peer?  No, due to trusted information paradoxes.

Client/server?  Yes, as the server can retain final arbiter status
for critical points.

Guiding rule: No matter what your approach is you have to have at
least one source of data which you can define as authoritative.
Somebody or something has to be arbiter.  Further, where the task is
the maintenace of a consistent shared image (the game world, data
set, whatever), everybody must either agree on the same
authoritative source, __or__ you must be able to guarantee that the
fact that they agree on different authoritative sources must have no
net effect.

  Note; That "authoritative source" can be virtual, much in the
manner that NTP, say, determines which of its NTP peers is
"authoritative" via simple quorum mechanics (higher or equal stratum
level and reporting similar time values to other equivalent peers,
thus rendering any similar peer reporting odd times as explicitly
non-authoritative).

Possible peer-to-peer model (no, this doesn't scale):  

  1) X shoots a bullet at Y.

  2) X elects an arbitrary neighbor node Z of X (minimum latency
  class) and sends it a message indicating X.

  3) Z requests state data of X

  4) X sends its state data to Z.

  5) X sends the bullets flight characteristics, velocity etc to Y
  and Z.
  
  6) Y determines if bullet strikes Y, and the characteristics of
  the event, and sends that data to X and Z.

  7) Z returns its own computed results to X.  X arbitrates the
difference between X and Z, and in the event of arbitration failure, 
repeats the sequence from #2.

The tricky bit is ensuring that Y cannot guess the originator and
likely characteristic of the event type to be arbitrated, and thus
cannot provide usefully doctored information to Z:

  "Oh yes, Z is requesting my state data.  That must be because X
shot another bullet at me, so I'll report that I'm oriented so that
my minimum profile is presented to X and that my shields just
flashed on."

This is why the request to Y doesn't come from X. but instead comes
from Z, effectively attempting to make the source of the event
anonymous with respect to Y.

> - Are there any large-scale multiplayer games (MMPOG, I believe
> they are called) which uses a peer-to-peer architecture?

Not that I know of.

> - How would you keep the "distributed" in DIS with a client-server
> architecture?  

Intelligent clients -- push all the computational load you can onto
the client and then implement hairy trust models for your
client/server relationships.

> What things can be trusted to the client? (Yes, I know there has
> been a rather extensive thread on that.) 

Things which you can effectively sanity check at both other clients
and at the server with a far lessor computational load than making
the original computations.

> Any comments, suggestion, pointers or links to documentation are
> welcome.

If you or anyone else can find a mirror of that Intel doc above, it
would be a good touchstone for this.

--
J C Lawrence                               Internet: claw at kanga.nu
(Contractor)                              Internet: coder at kanga.nu
---------(*)                     Internet: claw at under.engr.sgi.com
...Honourary Member of Clan McFud -- Teamer's Avenging Monolith...