The Design of Software (CLOSED)

A public forum for discussing the design of software, from the user interface to the code architecture. Now closed.

The "Design of Software" discussion group has been merged with the main Joel on Software discussion group.

The archives will remain online indefinitely.

Protocol Design

I am interested in writing a multiplayer, turn-based game as a way of learning more about network programming.  It will probably be Monopoly.  At any rate, one feature I'd like to add is a chat window so that clients can chat with each other while they are playing the game.

This may be long, I have a couple questions.

In designing the network protocol, I figure that one model would be for clients to have a persistent socket connection to the server.  I was thinking of a simple protocol in which, conceptually, all requests could boil down to "requests to change game state" and the response would contain any new, relevant game state, or an error code.

I'll call this the 1:1 request/response model, because each request is paired with a response.  Chat messages, on the other hand, seem different.  Chat messages are initiated by someone else; they aren't "requested" per se.

I thought of a couple of solutions, but thought I'd ask the trusty JoS board what they think.

One thing that occurred to me is that the client application could make a distinction between requests for which it expects a response, and those it doesn't.  For example:

The client moves his race car to Marvin Gardens.  This involves sending a request to the server for which a response is expected.  The client updates its state to reflect that it is waiting for a response, and then goes back to blocking on a read of the socket.  Poof!  Immediately, a new message arrives.  But it's not the response to our move to Marvin Gardens-- it's a chat. So the screen is updated and we go back to waiting.

Then I response to the chat by sending out a message for which I don't expect a response.  Then the response from my original request comes back..

All of this suggests to me that I'll have one thread that maintains the I/O and presents the client with an event driven sort of interface. 

Does this sound at all reasonable?  Any other suggestions?
I'm new to this sort of thing but I'm really eager to get it right.
Socket Guy Send private email
Thursday, June 12, 2008
 
 
I would recommend running it over HTTP rather than raw sockets for the simple reason that you'll be able to run this over the web (through firewalls).

A friend and I did a similar game.  The client polled the server via HTTP.  It basically sent messages and received messages.  The messages could be send:chat, send:move, receive:chat, receive:move, etc.  We sent and received a bunch of messages at once if needed (in case the client/server got behind -- all messages would queue up until they could be delivered).

I wouldn't write Quake this way, but for a board game it kept things simple.

And as long as you're at it, you might want to consider security.  How will you prevent player A from sending a request to move player B's piece when it is player B's turn? :)
Doug
Friday, June 13, 2008
 
 
Why would you use blocking sockets for something so clearly async in nature?
So tired
Friday, June 13, 2008
 
 
Doug,

You raise an interesting point in your response when you mention that you recommended polling.  It also occurred to me that this was a potential solution, but does polling really scale well?  It must to some extent because it seems as though AJAX applications rely on polling the server constantly for new information. 

But what about things like trading applications?  I'd have a hard time believing that things like Bloomberg terminals are constantly pinging the server for stock quotes.  Or are they?

Your discussion of security is great too.  That's another reason I favored a persistent connection.  Perhaps there's an authentication step at startup?  Then, the server, which is really only managing a small number of connections, would know which sockets go with whom, and would simply return an error if a client tried to cheat.
Socket Guy Send private email
Friday, June 13, 2008
 
 
You need a message Queue... on the server, and each client will fetch new messages regularly, and whenever it sends a message itself.

I've done something simple with php/mysql on the server and client-side software that interacted with it through simple http requests... Whenever you do anything, it gave a status response + all the messages you missed.
Totally Agreeing
Friday, June 13, 2008
 
 
as for security, one messages could be an authentication that returns a random or GUID session ID, this is used in all requests.
Totally Agreeing
Friday, June 13, 2008
 
 
The architecture of the message systems is usually a subscription.

Call up your server and say "hi. I'd like to join game X"

It says "OK"

From then on, you get "update" messages broadcast to you. Which in this case would be things like;

"Player number 2 has started their turn"

"player number 2 has bought Park Lane"

"player number 2 has mortgaged Park Lane"

{Something to consider given your low bandwith requirements would be a simple text based format. Send 60 characters, the first few describe what happened ("P2 START","P2 B PARK_LANE","P2 M PARK_LANE") and the subsequent data is printable padded with spaces. Ended with a CR. Why do this? Because then you can write the server and test it independently of the client by calling it up using telnet or putty.. You could also easily attach a different client, say a browser based one.}

Since Monopoly like games don't really have much information hiding, you can just send the info to all players. Just build a queue for each connected player, everytime something happens, shove a message onto the ends of the queues.

Internally both ends can do one of several things. 1) Have a thread running a select on the sockets and reading/writing data in and out of the queue.

2) Use IO completions on the sockets so that you get posted a message when there's data ready. This will be fine because you have low latency requirements, and it's almost certainly the easiest for a beginner to do. Basically, whenever there's data for reading or space for writing on the socket Windows will send you a message, just like it sends you paint messages. You just read data out of the sockets when you get the message, and if it's a full message go and process it. Writing works slightly differently -- you set the completion only if you have data to send otherwise you'll keep being told there's space on the socket.

3) Do it "properly" and render the screen, compute a remaining time budget ( 1/50 second minus the time taken to draw the screen), then wait for IO data for that time using select. The advantage here is that your process is basically idle in the select so the OS can go do other things.


Might I suggest heading off and buying something like;

"Programming an RTS Game with Direct3D"

It does say "RTS" in the title, but the general principles end up being much the same -- In reality, most RTS games are built as turn-based games. The turns simply aren't very long - say 1/10th second. When you order your unit to move, there's a bit of delay (which is covered up by the animation on your machine) to allow the move instruction to propagate to all the other players. The unit then marches off, taking (say) a few "turns" to cover each ground tile. It *is* possible to write systems which work on modelling continuous temporal flows, but they're rather specialised and rely on decent network performance.

It has a chapter on using the MS game library to do things like lobbies and connections and moving data about, which will mean it plays nicely with the OS.

It'll also explain all the other bits and bobs you need to make a game work under Windows.
Katie Lucas
Friday, June 13, 2008
 
 
If you're going to go the HTTP route, and you want to avoid excessive polling, you should take a look at Comet -

http://en.wikipedia.org/wiki/Comet_(programming)
http://simonwillison.net/2007/Dec/5/comet/
http://www.slideshare.net/simon/time-for-comet/
Rob
Friday, June 13, 2008
 
 
Katie Lucas: Just what I was looking for and an excellent synopsis.

Thanks!
Socket Guy Send private email
Friday, June 13, 2008
 
 
Rob:

Since my goal is to get my hands dirty implementing a protocol (including the nuts and bolts of writing the server and client) I'm thinking HTTP is not the way to go.

As an aside, I think it's interesting that interest in "server push" technology is bubbling up again, since last time around it proved to be a non-winner.

I suppose "There's nothing new under the sun."
Socket Guy Send private email
Friday, June 13, 2008
 
 
When you write your protocol, stick a version byte at the front of it.  That way when you come out with protocol v2.0, your code can still understand them.

I'm expecting someone to say "but just use XML!", which is a valid possibility, but it's wordiness results in longer transmission and parsing times.
xampl
Friday, June 13, 2008
 
 
You could use http and write the client/server yourself.

Then you have 'real' http clients and servers to test against - the danger of doing both ends yourself is that you end up with a design by coincidence, which happens to work for the small set of messages you test.

You also get experience of a real world protocol.
Martin Send private email
Friday, June 13, 2008
 
 
Martin:

I will probably use a text-based protocol similar in nature to http so that, as a previous poster alluded, it would be simple to debug with telnet.

I see the value in using HTTP as the message format, however, my protocol will likely be more like what Katie Lucas describes, which is somewhat different than the 1:1 request:response model that HTTP uses.

If I'm reading correctly, Lucas suggests:

---
Client:  SUBSCRIBE
Server:  OK
Server:  Msg1
Server:  Msg2
...
Client:  BUY MARVIN GARDENS
Server:  CLIENT xyz BOUGHT MARVIN GARDENS
--
See that there is not a 1:1 correspondence between client and server messages.

I will probably avoid using XML.  I'm actually not a fan.  I think it's overused and cumbersome to work with in many cases.
Socket Guy Send private email
Friday, June 13, 2008
 
 
Socket Guy, yes.  Polling scales quite well:

http://www.expatsoftware.com/articles/2008/03/6-million-hits-day-time-to-think-scale.html

Rob, It's worth keeping in mind that if you're going to go the Comet route, you're essentially going to have to write your own web server so that you can handle thousands of simultaneous connections and deal with them all at once.  It's by no means trivial, and thus far the only people to have pulled it off well at scale have been inside Google.

Neither IIS nor Apache can handle a comet implementation out of the box.  Both will survive just fine under the same load from polling clients.
Jason Kester Send private email
Friday, June 13, 2008
 
 
Jason,

Clearly, although I still doubt that the polling model is used in time critical apps like trading systems.  In fact, I think a lot of those systems actually use UDP, don't they?

Can anyone comment?
Socket Guy Send private email
Friday, June 13, 2008
 
 
> time critical apps ... actually use UDP

See for example http://en.wikipedia.org/wiki/Real-time_Transport_Protocol which is built on top of UDP.
Christopher Wells Send private email
Friday, June 13, 2008
 
 
Socket Guy,

"I'll call this the 1:1 request/response model, because each request is paired with a response."

If you're just going to use a plain persistent TCP/IP connection, I don't know why you want to go with a request/response model.  There's no reason you need to pair them together.

Instead, just have the client wait for events.  These could be chat messages or a change in game state (because the other person moved).  Just have it wait on a socket for anything that comes in. 

As for what you send, when you make a move or send a chat message just send that up to the server immediately.
Almost H. Anonymous Send private email
Friday, June 13, 2008
 
 
> I don't know why you want to go with a request/response model.

I'm guessing it's because he was imagining a single-threaded, non-event-driven client, whose thread does:

void transact(const string& request, string& response)
{
  //send the request
  m_network.send(request);
  //block until a response is received
  m_network.receive(response);
}
Christopher Wells Send private email
Friday, June 13, 2008
 
 
Christopher,

What's funny is that I started out (before posting) assuming that I'd need to use asynchronous I/O on the client.  Then I talked to some people who claimed to be experts who suggested that my model was too complicated. 

Next, I posted here, and behold, some people suggested polling (which I don't believe is efficient) which could e done syncrhonously by the client but seems inefficient.  Lucas and you pointed out that asynch is the way to go.

So in a way, I ended up where I started!  I really just wasn't sure how scalable event driven stuff was developed.  I've written multithreaded servers that handle hundreds of concurrent connections for work, but the protocol was something that was close to HTTP; open socket, make request, read response, close socket.

It sounds to me as though you're saying that you agree with Lucas, which sounds grand to me.

Back to polling-- it seems to work for AJAX-- or does it?  These types of things seem wildly inefficient to me.  Does anyone know about trading apps?  Do they typically follow the subscription model proposed by Lucas?
Socket Guy Send private email
Friday, June 13, 2008
 
 
> Then I talked to some people who claimed to be experts who suggested that my model was too complicated.

Request/response isn't good at receiving unsolicited responses.

> some people suggested polling (which I don't believe is efficient)

The server (and therefore, the network protocol, and the way in which clients load the server) needs to be 'efficient'.

A Monopoly client (unlike a trading app client) probably doesn't need to be efficient (because it's not trying to consume vast quantities of real-time data): so, having chosen a network protocol which optimizes the server's efficiency, you can afford to optimize the client's implementation of that protocol for something other than efficiency (e.g. correctness, simplicity, maintainability).

> I really just wasn't sure how scalable event driven stuff was developed.

Heavily multi-threaded applications are a bear: either you don't have implement enough critical sections, or you implement too many.

> Does anyone know about trading apps?

Try Google: historically people haven't answered that question when it's been asked here, I'm guessing because it's a trade secret.
Christopher Wells Send private email
Friday, June 13, 2008
 
 
If it's a GUI app, it's already going to be event-driven.  It can be single-threaded, it just has to periodically check for data coming on a socket (this isn't polling, but it is asynchronous).

Taking to make it request/response in a game (where events can happen anytime) seems wrong.

AJAX using polling (and other techniques) because the networking ability in a web page is seriously limited.  It's inefficient but it's the only way to do it.
Almost H. Anonymous Send private email
Friday, June 13, 2008
 
 
>See that there is not a 1:1 correspondence between client
>and server messages.

HTTP as a transport is request:response, but if your protocol is message oriented, you can send 0 or more messages, and get 0 or more messages back.

You can also make HTTP pseudo-event oriented.  Imagine a web server that receives a request, has nothing to send, so it simply doesn't respond for 30 seconds or so (in hopes that something will show up that needs to get sent back).  I think this is called reverse HTTP.  I implemented it years ago and it worked great, but it meant you had many sockets open to the HTTP server (which you'll do anyway with a socket-based approach).  You can't go much higher than 30 seconds if you want to work through proxy servers (or you could be clever and slowly increase the wait times until there was a failure/timeout, and then back off).  It's pretty darn efficient.

I used to work at <major exchange information company> (think Bloomberg, but it wasn't them) on their trading servers.  Everything was UDP or TCP, and broadcast when possible.  Basically an update for IBM (for example) was pushed out to an edge server (at client premises) and then the edge server forwarded the update to all clients that had registered interest in IBM.  I remember seeing a server record that it was processing 27,000 quotes/updates PER SECOND.  I was astounded (I didn't work on that server)  Luckily a Monopoly game won't need that level of scalability :)
Doug
Friday, June 13, 2008
 
 
Doug

That's awesome.  That's exactly the sort of clue I was looking for.  Obviously the monopoly game won't need that, but I want to start with something that's easy to grok.

As I was telling another poster, I am fairly experienced when it comes to asynch I/O, I just had no idea what sort of protocols the big boys used when doing high throughput crap like trading.

Thanks everyone for your posts, I love this board because there are so many smart people in the industry to draw from.
Socket Guy Send private email
Friday, June 13, 2008
 
 
In regarding to trading desk kind of apps, most of them use publish/subscribe model with MOM, which ends up using broadcast or multicast to publish messages.  The clients would subscribe to a topic on the MOM, like a certain stock ticker.  The server publishes the stock quotes to the topic on the MOM, which just broadcast/multicast to the clients.  The client side's MOM would decide to throw away the unsubscribed messages and returns the subscribed ones.

100% reliability is not really needed in this kind of message streaming.  Since if you miss one stock quote, you will get the same thing again the next second.
been there done that
Friday, June 13, 2008
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz