Features

Cyberspace in the 21st Century:
Foundations

Cyberspace Modeling Language
You must be joking? Not another language! What about VRML? Or others? There must be hundreds of candidates to be considered. I'm not specifying a system here; I'll let you choose the language, but I will make some recommendations of the features it should have.

• General Purpose We don't necessarily know that we'll be dealing with a single type of application, so the language should have a general purpose basis. However, the ability to cope with the needs of 3D applications is likely to be indispensable.
  
  
• Object Oriented Object orientation seems to be a pretty useful and popular way of doing things. It'll probably also make a good match with the notions of discreet 3D objects and levels of detail (derived classes being more detailed and less abstract versions of their bases).
  
  
• Simple Data Structures Given we're expecting to communicate data quickly and across the network, I'd suggest that simple data structures are de rigueur. We should be able to keep data marshalling fairly efficient if we keep objects as the most sophisticated data structures, and deprecate complex built-in structures such as linked lists, pointers, and multi-dimensional arrays.
  
  
• Multithreaded & Event Based Like most games engines we'll need the facility for event based processing, and support for such things as hierarchical finite state machines.
  
  
• Compact representation
  Code, as well as data, has to be compact, because code is part of the model too - we're distributing everything! So some kind of p-code or byte code representation will be likely (just like Java).

Narrator: "Percival walks towards the castle. No signs of life."
"He nears the drawbridge. He starts walking across."
"The drawbridge starts to be raised"
Percival: "Eeek!"
Player: "Well, shout 'Stop!' and that you've a message for King John, you fool!"
Percival: "Stop! I have a message for King John, you fool!"

The important thing to remember here is that the player behind the avatar winding up the drawbridge may well be seeing everything in glorious 3D. Percival the avatar isn't blind, only the influencing player is - alternatively, the player might just as well be someone stuck in outer Mongolia, using a telex machine…

Percival the avatar isn't blind, only the influencing player is.

Choosing the Networking Method
If you thought it was fairly plain sailing so far, you're right. However, I think you'll find things get a little bit more choppy from now on. In fact some of you will think that the heading I've set us on will recklessly endanger the safety of the passengers. I just hope no one gets too upset when, a bit like Quint in Jaws, I smash the radio up with a baseball bat. So if you're like Police Chief Brody, the sort that espouses integrity and despises unreliability, you can grab those lifebelts now if you want - but they won't help you.

The question we're all asking is just how are we going to communicate the game across all these millions of players' impatient computers? It's the answer that may make you a bit queasy.

You may remember in my first installment that I mentioned the variety of mechanisms by which a game could be networked. There were a few choices, but I think there were enough hints to show you where my money was. I wish I could remember why, all those years ago, I concluded that a distributed approach was the best solution. I feel it would be a useful thing to document the thinking that led to it, but my memory isn't that good.

Yup, the brain works in mysterious ways. It is indeed difficult to recall the order of thinking that led one to arrive at a particular design of system. However, instead of spending years on introspection and oodles of shrink bills on recovered memory sessions, I've used the same mysterious ways of the brain to arrive at a solution. I woke up one morning with a way of rationalizing it all. You know - the design of the distributed system.

What follows is a methodology for selecting a distributed system and its characteristics for the purpose of enabling massive multiplayer games, I will not be considering security, revenue generation, administration, or any other ancillary issues at this stage. Suffice it to say there are no great white sharks you need to worry about right now.

Working Back from the Future
Our objective is scalability. That means we're into conquering the world and keeping it that way. We have to plan for things scaling up from what they are today to the limitless resources of the future. Rather than design a system from a contemporary perspective, with the handicap on ones imagination of contemporary feasibilities, it's better to start off designing a system that has the luxury of infinite resources. The trick is gradually pulling these resources down according to their relative growth curves.

Well, here's my view on the long term growth curves of computing resources. This is where you may have to stop reading and do something more useful with your life if you find yourself strongly disagreeing with me. As you will have gathered by now, my entire case rests on latency being fairly stagnant for the foreseeable future. Bandwidth, and by that I mean the 'available' sort, I expect will grow slowly. The bandwidth of a single connection (piece of optic fiber) may well double every so often, but that isn't the same as the bandwidth of a networked connection. Perhaps its growth is still exponential, but I'd rather not put in the same class as processing and storage. And as for the growth of these last two, well nothing short of global catastrophe will flatten their curves!

Latency: Asymptotic, e.g. a+b/t
Bandwidth: Parabolic, e.g. a+t^b
Processing: Exponential, e.g. a+b^t
Storage: Exponential

Let's see what this might mean in practice:

These figures are just an illustration of the growth curves -- don't read too much into them. I mean only to suggest that to all intents and purposes, current systems have meager amounts of processing and storage resources, especially when you compare them to what the situation will probably be like in a few decades' time.

Carte Blanche
Perhaps now it's a little more obvious why I'm suggesting that the trick is to pull down resources. Given carte blanche, almost any design will work. There's not really much point in suggesting any one in particular. However, it's interesting the way the choice of design starts to narrow as you limit each resource, and importantly in order of their cost. In the future, latency (and bandwidth to a lesser extent) will be the most significant cost and thus must have primary impact upon the system's design.

A Future With Today's Latency
Ok, so what happens if we don't quite have carte blanche? Let's say we have unlimited bandwidth and other resources, but messages are no longer delivered in an instant -- non-zero latency in other words. Even so, don't think this is simply where messages always take 200ms. Latency means you no longer know when any message will arrive at its destination, if at all. You might be able to measure some statistics of message trip time, and these might be maintained for a while, but you can't be certain. Coping with latency is key to designing massive multiplayer games.

First consider a peer-to-peer approach: every participant holds the entire model and transmits player input to every other participant. It works. However, if you were hoping for perfection then the game will be at the mercy of the longest message delays - the weak link in the chain as it were. No matter, maybe you can come up with 'coping mechanisms' to ameliorate these delays. If very long delays, or message losses in other words, are a likelihood, well, you could try continuously reconciling state between peers rather than surviving on input alone. After all, we haven't considered limiting bandwidth yet.

How about client/server? Well, it's a single authoritative model, so little chance of corruption. After collecting all input it could even return rendered frames to each player. Remember, we're pretending we've got the bandwidth to do this. Even if message loss occurs, it needn't cause widespread corruption or delay. Players with high latency or flaky connections would simply have to put up with it.

It's not that clear yet whether peer-to-peer or client/server is better. I suspect that the latter would probably win out at this stage, if only because it's more straightforward. Whilst the former might ameliorate latency (assuming it was related to network topology) this would probably require sacrificing global synchronization, i.e. in practice, synchronization is only required between players in the same mutual area of effect.

Limited Bandwidth
When you consider the bottlenecks that arise, to now introduce limits on bandwidth immediately knocks the client/server approach on the head. It also persuades us to review the design of the peer-to-peer model.

We can still afford to have every computer hold and compute the entire game model, but can we still receive billions of player input events? No, we must presume that there's probably not enough bandwidth. Broadcasting player input is now a no-no.

As I mentioned in the case of non-zero latency, we'd probably adopt a peer-to-peer design where each peer only subscribed to the input events of players that were within the same area of effect. We'd also have a continuous background process of model reconciliation, i.e. partial synchronization.

But, let's stop right here. Things are no longer quite so straightforward -- we've long since left Kansas as some might say. We are now in the realms of The Internet as it stands today. I can't cover in only a few sentences the wealth of techniques that have been developed over the last few years to cope within known bounds of latency and bandwidth - when trying to develop multiplayer games (or battlefield simulators). As I've mentioned previously, DIS and HLA are the acronyms to check out. They're the sort of approaches you'd use if money were no object, but you were stuck with a limited network.

However, whilst many of those techniques will work fine when you have known bounds of latency, bandwidth and numbers of participants, that is not the case we have to deal with. We are not operating in circumstances where there is theoretically a way of getting the right information to the right computers without noticeable delay or artifact. Indeed, we have to embrace at the core of our design the case where there is more going on than can be communicated in any reasonable time. This gives rise to the need to prioritize communication -- the first hint that we're destined for scalable approach.

This is also the point at which we realize synchronization is no longer the right word for what we're trying to do. We're now trying to design a modeling system that only tends toward agreement. We accept we'll never get perfect agreement, but as long as few players notice, it'll have to do. Just as in the real world, all we need is a consensus of reality. For example, I don't think anyone's been able to prove that a tree falling in a forest still makes a sound in the absence of witnesses. As long as it turns up on a tape recorder we're happy. Even reality does not necessarily need a synchronized model; it just needs to be synchronized when we inspect it. Dinosaur bones don't need to exist until we dig them up. Of course, it's easier for our Occam oriented brains to believe the universe doesn't work like this, but you never know…

Dinosaur bones don't need to exist until we dig them up.

The important thing about consensus is that it is a human construct arrived at by discussion - it is not reality, it is only a description. In other words, as long as players' discussions of their experience of cyberspace agree, then it does not matter if the quality of their experience differs. This is our guideline in prioritizing the information that is communicated between computers. The most salient and critical aspects of the virtual world become the most important to communicate. For example, it is more important to know that a landmine has been laid nearby than whether it's round or square, just as it is more important to hear the rapid approach of footsteps than whether boots or stilettos are being worn. The relative importance of these salient features can either be extracted from the dynamic relationships between objects in the virtual world or can be imparted into the model by the game creators.

Limited Storage and Processing
It's only when you squeeze the resources a little tighter that a more streamlined and scalable design emerges. Once you attempt to cater for a local computing environment in which storage and processing resources are no longer unlimited, and furthermore, where their limits are unknown, you can either continue with a brute force approach and refuse to operate on incapable systems or you go scalable and adopt a best effort approach.

The thing is, because we are having to design a system to operate in an unknown local environment it is pointless to try and continue to make any guarantees about local systems integrity (and blame the network when things get sluggish). Ok, local resource restriction doesn't really directly lead to a best effort approach, but it does make it look more and more appealing. After all, when faced with the impossible, your best effort is all you can hope to do.
When 'less than perfection' is adopted as the essential heart of a system rather than regarded as a runtime hazard, this best effort approach is quite liberating and allows for simpler and probably more elegant systems design.

Not only do we prioritize the communication of the model's state, but we also have to prioritize its storage and processing - and again, according to its importance to the avatar.
The local resources are in effect a read/write cache to the global model (even though it may only ever exist as a composite of all these caches). Of course it is an active cache; in as much as it is not just state, but also a portion of a model and thus must be continuously computed. And we all know about caching policies such as 'least recently used' and multi-processing systems that time-share according to process priority - don't we?

The Solution
Given the assumption that storage and processing resources are eminently scalable, we must be able to dynamically take advantage of their growth. This means we need a model that has a fine granularity, i.e. where the model when reduced to any fraction, continues to operate but at a lower effectiveness and quality. Such graceful degradation might lead one to conclude that neural networks were in order, but given that we need to understand what we're dealing with, I'd suggest that an object oriented model was a good compromise. Objects are supposedly, nice and discreet, self-contained packages of state and functionality. And simpler objects are always available given the use of inheritance.

So at last we end up with the beginnings of a solution, a hint of the architecture that will form the basis of cyberspace. It looks very much to me like an active, object oriented, distributed database. All we need to do is: according to certain priorities, continuously distribute and process a collection of objects.

We accept that each computer is likely to have a different version of model state, but that the state in each computer should exhibit a tendency (to converge) toward agreement. This is based on the premise that there is unlikely to be sufficient time in which to obtain perfect agreement.

The Best Efforts of Mice and Men
So here we say goodbye to integrity and all those who cannot tolerate its passing.
In order to arrive at a system that can model a virtual universe for an unlimited number of participants with unknown resources we've discovered that the system must adopt the best effort principle at its heart. This means embracing the compromised integrity of an unsynchronized model.

The plane has to be built and flown before people will believe it can fly.

As you'll see in one of my next installments, in many ways this makes the system simpler and our life easier. Unfortunately, like as Orville and Wilbur discovered, the plane has to be built and flown before people will believe it can fly.

Moving toward an asynchronous system may be a little bit of a paradigm shift for some people, and I expect it may be too much for a few. Perhaps some of you will be able to suspend disbelief long enough to accompany those who've accepted its feasibility in reading next month's installment. I'll be discussing how to go about organizing all these billions of computers to co-operate in distributing what might be trillions of objects.

If I haven't raised enough contentious issues already here are a couple of things to think about or research in the next few weeks:

1) If a game model consists of state, events, and behavior; when we come to network it, which should be distributed and which should remain local?
2) 'Tuple space', Linda, and Objective Linda - will give you a taste of distributed objects.

Discuss this article in Gamasutra's discussion forums

________________________________________________________

[Back To] Ground Rules

join | contact us | advertise | write | my profile
news | features | companies | jobs | resumes | education | product guide | projects | store



Copyright © 2003 CMP Media LLC

privacy policy | terms of service