<!-- MHonArc v2.4.4 --> <!--X-Subject: [MUD-Dev] Re: DIS: Client-Server vs Peer-to-Peer --> <!--X-From-R13: X Q Znjerapr <pynjNhaqre.rate.ftv.pbz> --> <!--X-Date: Wed, 25 Nov 1998 15:22:47 -0800 --> <!--X-Message-Id: 199811252322.PAA03890#under,engr.sgi.com --> <!--X-Content-Type: text/plain --> <!--X-Reference: Pine.SOL.3.96.981124161642.5501A-100000#licia,dtek.chalmers.se --> <!--X-Head-End--> <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN"> <html> <head> <title>MUD-Dev message, [MUD-Dev] Re: DIS: Client-Server vs Peer-to-Peer</title> <!-- meta name="robots" content="noindex,nofollow" --> <link rev="made" href="mailto:claw#under,engr.sgi.com"> </head> <body background="/backgrounds/paperback.gif" bgcolor="#ffffff" text="#000000" link="#0000FF" alink="#FF0000" vlink="#006000"> <font size="+4" color="#804040"> <strong><em>MUD-Dev<br>mailing list archive</em></strong> </font> <br> [ <a href="../">Other Periods</a> | <a href="../../">Other mailing lists</a> | <a href="/search.php3">Search</a> ] <br clear=all><hr> <!--X-Body-Begin--> <!--X-User-Header--> <!--X-User-Header-End--> <!--X-TopPNI--> Date: [ <a href="msg00858.html">Previous</a> | <a href="msg00860.html">Next</a> ] Thread: [ <a href="msg00855.html">Previous</a> | <a href="msg00864.html">Next</a> ] Index: [ <A HREF="author.html#00859">Author</A> | <A HREF="#00859">Date</A> | <A HREF="thread.html#00859">Thread</A> ] <!--X-TopPNI-End--> <!--X-MsgBody--> <!--X-Subject-Header-Begin--> <H1>[MUD-Dev] Re: DIS: Client-Server vs Peer-to-Peer</H1> <HR> <!--X-Subject-Header-End--> <!--X-Head-of-Message--> <UL> <LI><em>To</em>: <A HREF="mailto:mud-dev#kanga,nu">mud-dev#kanga,nu</A></LI> <LI><em>Subject</em>: [MUD-Dev] Re: DIS: Client-Server vs Peer-to-Peer </LI> <LI><em>From</em>: J C Lawrence <<A HREF="mailto:claw#under,engr.sgi.com">claw#under,engr.sgi.com</A>></LI> <LI><em>Date</em>: Wed, 25 Nov 1998 15:22:16 -0800</LI> <LI><em>Reply-To</em>: <A HREF="mailto:mud-dev#kanga,nu">mud-dev#kanga,nu</A></LI> </UL> <!--X-Head-of-Message-End--> <!--X-Head-Body-Sep-Begin--> <HR> <!--X-Head-Body-Sep-End--> <!--X-Body-of-Message--> <PRE> On Tue, 24 Nov 1998 22:06:23 +0100 (MET) Niklas Elmqvist<d97elm#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: <A HREF="http://www.pasteur.fr/other/computer/RFC/9xx/994">http://www.pasteur.fr/other/computer/RFC/9xx/994</A> -or- <A HREF="http://www.kanga.nu/~petidomo/lists/mud-dev/1998Q1/msg00774.html">http://www.kanga.nu/~petidomo/lists/mud-dev/1998Q1/msg00774.html</A> > 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 <A HREF="http://developer.intel.com/drg/hybrid_author/cookbooks/games/">http://developer.intel.com/drg/hybrid_author/cookbooks/games/</A>). Related slideshow (nothing new here, just noticed it in passing while looking for the above doc): <A HREF="http://developer.intel.com/drg/news/class6/">http://developer.intel.com/drg/news/class6/</A> 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#kanga,nu (Contractor) Internet: coder#kanga,nu ---------(*) Internet: claw#under,engr.sgi.com ...Honourary Member of Clan McFud -- Teamer's Avenging Monolith... </PRE> <!--X-Body-of-Message-End--> <!--X-MsgBody-End--> <!--X-Follow-Ups--> <HR> <ul compact><li><strong>Follow-Ups</strong>: <ul> <li><strong><A NAME="00864" HREF="msg00864.html">[MUD-Dev] Re: DIS: Client-Server vs Peer-to-Peer</A></strong> <ul compact><li><em>From:</em> Niklas Elmqvist <d97elm#dtek,chalmers.se></li></ul> </UL></LI></UL> <!--X-Follow-Ups-End--> <!--X-References--> <UL><LI><STRONG>References</STRONG>: <UL> <LI><STRONG><A NAME="00855" HREF="msg00855.html">[MUD-Dev] DIS: Client-Server vs Peer-to-Peer</A></STRONG> <UL><LI><EM>From:</EM> Niklas Elmqvist <d97elm#dtek,chalmers.se></LI></UL></LI> </UL></LI></UL> <!--X-References-End--> <!--X-BotPNI--> <UL> <LI>Prev by Date: <STRONG><A HREF="msg00858.html">[MUD-Dev] Re: [RELEASE] Insanity To Infinity (I:I_OS) v.01a</A></STRONG> </LI> <LI>Next by Date: <STRONG><A HREF="msg00860.html">[MUD-Dev] Re: DIS: Client-Server vs Peer-to-Peer</A></STRONG> </LI> <LI>Prev by thread: <STRONG><A HREF="msg00855.html">[MUD-Dev] DIS: Client-Server vs Peer-to-Peer</A></STRONG> </LI> <LI>Next by thread: <STRONG><A HREF="msg00864.html">[MUD-Dev] Re: DIS: Client-Server vs Peer-to-Peer</A></STRONG> </LI> <LI>Index(es): <UL> <LI><A HREF="index.html#00859"><STRONG>Date</STRONG></A></LI> <LI><A HREF="thread.html#00859"><STRONG>Thread</STRONG></A></LI> </UL> </LI> </UL> <!--X-BotPNI-End--> <!--X-User-Footer--> <!--X-User-Footer-End--> <ul><li>Thread context: <BLOCKQUOTE><UL> <LI><strong><A NAME="00856" HREF="msg00856.html">[MUD-Dev] [RELEASE] Insanity To Infinity (I:I_OS) v.01a</A></strong>, Bobby Bailey <a href="mailto:mush#smidefix,karen.hik.se">mush#smidefix,karen.hik.se</a>, Wed 25 Nov 1998, 03:21 GMT <UL> <LI><strong><A NAME="00857" HREF="msg00857.html">[MUD-Dev] Re: [RELEASE] Insanity To Infinity (I:I_OS) v.01a</A></strong>, Robin Carey <a href="mailto:r.carey#dcs,napier.ac.uk">r.carey#dcs,napier.ac.uk</a>, Wed 25 Nov 1998, 09:07 GMT <UL> <LI><strong><A NAME="00858" HREF="msg00858.html">[MUD-Dev] Re: [RELEASE] Insanity To Infinity (I:I_OS) v.01a</A></strong>, Bobby Bailey <a href="mailto:mush#smidefix,karen.hik.se">mush#smidefix,karen.hik.se</a>, Wed 25 Nov 1998, 15:44 GMT </LI> </UL> </LI> </UL> </LI> <LI><strong><A NAME="00855" HREF="msg00855.html">[MUD-Dev] DIS: Client-Server vs Peer-to-Peer</A></strong>, Niklas Elmqvist <a href="mailto:d97elm#dtek,chalmers.se">d97elm#dtek,chalmers.se</a>, Tue 24 Nov 1998, 21:06 GMT <UL> <LI><strong><A NAME="00859" HREF="msg00859.html">[MUD-Dev] Re: DIS: Client-Server vs Peer-to-Peer</A></strong>, J C Lawrence <a href="mailto:claw#under,engr.sgi.com">claw#under,engr.sgi.com</a>, Wed 25 Nov 1998, 23:22 GMT <UL> <LI><strong><A NAME="00864" HREF="msg00864.html">[MUD-Dev] Re: DIS: Client-Server vs Peer-to-Peer</A></strong>, Niklas Elmqvist <a href="mailto:d97elm#dtek,chalmers.se">d97elm#dtek,chalmers.se</a>, Sun 29 Nov 1998, 22:15 GMT <UL> <LI><strong><A NAME="00874" HREF="msg00874.html">[MUD-Dev] Re: DIS: Client-Server vs Peer-to-Peer</A></strong>, J C Lawrence <a href="mailto:claw#under,engr.sgi.com">claw#under,engr.sgi.com</a>, Tue 01 Dec 1998, 04:26 GMT <UL> <LI><strong><A NAME="00888" HREF="msg00888.html">[MUD-Dev] Re: DIS: Client-Server vs Peer-to-Peer</A></strong>, Ling <a href="mailto:K.L.Lo-94#student,lboro.ac.uk">K.L.Lo-94#student,lboro.ac.uk</a>, Wed 02 Dec 1998, 12:04 GMT <UL> <LI><strong><A NAME="00897" HREF="msg00897.html">[MUD-Dev] Re: DIS: Client-Server vs Peer-to-Peer</A></strong>, Niklas Elmqvist <a href="mailto:d97elm#dtek,chalmers.se">d97elm#dtek,chalmers.se</a>, Thu 03 Dec 1998, 09:06 GMT </LI> </UL> </LI> </UL> </LI> </UL> </LI> </UL> </LI> </UL> </LI> </UL></BLOCKQUOTE> </ul> <hr> <center> [ <a href="../">Other Periods</a> | <a href="../../">Other mailing lists</a> | <a href="/search.php3">Search</a> ] </center> <hr> </body> </html>