STK Network Multiplayer Progress

[kobos]

Hi all,


I want to help contribute to the (re) Integration of the network code but i thought i'd ask you guys for your opinions and any further detail on the matter.

for instance
- Why was the existing code deprecated in the first place?
- What are the challenges invovled in moving the network code over to the new game engine (if any)
- What doesn't need re-writing and what does?

regards


K

[hiker]

Hi,

a very brief answer only for now:

Hi all,


I want to help contribute to the (re) Integration of the network code

That would be great!

but i thought i'd ask you guys for your opinions and any further detail on the matter.

for instance
- Why was the existing code deprecated in the first place?

The old code was (by design) LAN only.

- What are the challenges invovled in moving the network code over to the new game engine (if any)

The network code has to be rewritten, porting doesn't make any sense.

- What doesn't need re-writing and what does?

Everything needs to be rewritten: we have the addon server, which we can use to store user id information (with the 2nd goal of enabling people to vote for addons). So then we need a lobby (including things like creating groups, inviting people, consider the risk of having kids part of an online community - e.g. perhaps we want to give parents an option that they can restrict which groups a kid can play in???), followed by the actual networking implementation. I'll try to write a wiki page in the next couple of days outlining the (imho) useful steps and order of implementation (which would allow us to keep on releasing STK with increasing networking capability: voting for addons, online highscores including ghost races, then actual races). The only thing that is still in place is basically enet (though it could be replaced, but from my brief work in the LAN implementation it looked like a reasonable small but complete library). I've left the implementation of the LAN work mostly in place (though it won't work) since the comments and some implementation detail might prove useful.

Do you have the experience to implement this? The actual networking code is not trivial (e.g. it involves understanding of the physics engine in order to implement rollbacks which are most likely necessary, ...) - we had a few people volunteering for this, and my guess is so far they have all underestimated the difficulties

Cheers,
Joerg

[kobos]

Joerg, I have academic experience in implementing distributed computational physics problems, so i have a good handle on real time physics engines having built one myself, it also contained network code but owing to the fact that i had to write all the code myself from scratch including the rendering engine I was able to perform hacks and take shortcuts that won't be possible here. Also I never had to consider latency issues as it all the simulations took place over a fibre network.

From the layers you've described i'd rather concern myself with the network code, so how players communicate with the server and if/how they communicate with each other (p2p) with consideration as to how collisions are handled between clients and how the traffic is managed / structured (ie prioritization and frequency of updates).


From looking at the code i see that the NetworkManager owns the current player information for all players as far as RaceManager (RM) is concerned, in that the RM pulls the new information from the NM and pushes back updates as a result of a players interaction with the world. Am I right ish?

The network manager would be responsible for pushing out updates to other players, but the ferocity at which the updates are sent would be decided by the NM. In that there is no need to update another player at 50-70hz if they can't yet see each other; this gives rise to having update frequency levels (low,normal,high) so the frequency level between players could either be decided by the server or mutually between clients.

sorry this sounds so vauge but it's 5:30 here and we've run out of coffee!

so my first hurdle is how to optimally handle traffic between clients, i've tried pure client server configs in the past but i find unless the server is dedicated it can easily get flooded so handling the majority of data passing p2p makes sense even if it is a little harder.

i'll start prototyping in python how the network communication aspect should work before i move to C++.

[hiker]

Hi,
...

From the layers you've described i'd rather concern myself with the network code, so how players communicate with the server and if/how they communicate with each other (p2p) with consideration as to how collisions are handled between clients and how the traffic is managed / structured (ie prioritization and frequency of updates).

Which is the most complicated and last step in the 'natural' order of implementation. I am going to write an outline on what my thinking so far is in the wiki, but that might take a day or two.

From looking at the code i see that the NetworkManager owns the current player information for all players as far as RaceManager (RM) is concerned, in that the RM pulls the new information from the NM and pushes back updates as a result of a players interaction with the world. Am I right ish?

Yes, but as I've said, that probably needs to be re-implemented. We can't simply use p2p, since this makes cheating way too easy.

The network manager would be responsible for pushing out updates to other players, but the ferocity at which the updates are sent would be decided by the NM. In that there is no need to update another player at 50-70hz if they can't yet see each other; this gives rise to having update frequency levels (low,normal,high) so the frequency level between players could either be decided by the server or mutually between clients.

I don't think a kind of regular frequency update will work - in LAN networking you have to handle latency of 100ms and more. Also even if all karts on one computer (think splitscreen) can't see any kart on another computer, there is still need for communication, e.g. to inform about collected items, projectiles flying, physical objects being pushed around etc.

sorry this sounds so vauge but it's 5:30 here and we've run out of coffee!

Gee, that's bad news

so my first hurdle is how to optimally handle traffic between clients, i've tried pure client server configs in the past but i find unless the server is dedicated it can easily get flooded so handling the majority of data passing p2p makes sense even if it is a little harder.

I am not sure that this is the best approach: as I've said above with p2p it's very easy to cheat, and p2p might be more complex to implement. A simple example: an item gets collected by a kart on two different computers 'at the same time', i.e. on each computer (due to differences in the simulation) the 'local' kart collects the item. How do you synchronise this? Yes, I know that it can be done, but I'd say it's easier if a server has the final say and you 'only' need to rewind to get back in synch with the server. But we can see, I haven't had too much time to come up with the design.

So give me a day or two to update the wiki, and let's see what we can come up with.

Cheers,
Joerg

[Auria]

I might just want to chime in and add... if someone determines that p2p is the best way to go then I don't think we should bother with cheating. Very few people will have the know-how to cheat, and a cheater will be quickly marked as such and no one will want to play with him.

[Arthur]

Well if we're going to have some sort of ranking system like in TrackMania, there would have to be some cheat prevention. Also, cheating by e.g. editing the stk_config.xml file to have slightly higher values should be prevented, as that would be really easy to do.

I am really glad to see that you want to work on this, kobos. It's a highly anticipated feature.

[Auria]

Well if we're going to have some sort of ranking system like in TrackMania, there would have to be some cheat prevention. Also, cheating by e.g. editing the stk_config.xml file to have slightly higher values should be prevented, as that would be really easy to do.

I am really glad to see that you want to work on this, kobos. It's a highly anticipated feature.

For highscores indeed, then I think the only appropriate way is replay support

[hiker]

I might just want to chime in and add... if someone determines that p2p is the best way to go then I don't think we should bother with cheating. Very few people will have the know-how to cheat, and a cheater will be quickly marked as such and no one will want to play with him.

I disagree with this to a certain extend: anything that involves modifying a simple text file (which is well documented and mentioned in several threads in the forum) would make it way too easy to cheat. It could even happen by mistake - you followed our instructions to tweak the physics, and you just forgot. Changing the program would be more difficult, and might be an acceptable risk.

So if P2P should be the way to go (which I wouldn't say it is) then the implementation should make sure that all peers are at least using the same kart parameters (which of course could then be avoided, but that involves patching STK).

Obviously a client/server architecture has similar (and actually more severe) issues, but it would mostly involve code changes (well, some cheats could be done by modifying the config files as well). But (since we can't afford dedicated servers) if we add some kind of voting features it would be easier to detect by the community. So some kind of voting system for people's server should be part of the overall design.

Cheers,
Joerg

[hiker]

Hi,

I've created a very first page for the networking discussion, see http://supertuxkart.sourceforge.net/Net ... ultiplayer and http://supertuxkart.sourceforge.net/Net ... lemetation

Cheers,
Joerg

[kobos]

Brief of what i think so far:

Pure Client Server : cons{latency, cost}, pros{easy}
Client Side Prediction : cons{Cost, difficulty}, pros{Hard to cheat, latency}
Peer-to-Peer : cons{difficulty, cheating}, pros{cost}

So the only option we can literally afford is p2p, all other options require a dedicated server that means hardware, bandwidth and maintenance aka money.
Cheating will be an issue, but remember this is open source and there isn't much we can do about it. We can have a system of distributed authority where if a player seems to go too fast or be just that little bit too accurate then the nodes can detect this and flag it; given enough flags the player gets booted.

I did alot of research into networking api's such as RakNet and its base UDT not to mention ENET etc, I realized all they can provide is crossplatform sockets and not much else. I don't really want to be the one with the task of implementing an efficient p2p layer with all the accompanying work load so I went in search of an existing p2p layer and came across the SpoVNet project.


SpoVNet is an architecture for establishing “spontaneous virtual networks” that enable distributed end to end communication across a wide range of different protocols and infrastructures. For example if Player-A connects to the public Server-1 and then Player-B behind a NAT now connects to Server-1, then players A&B and Server-1 now form a spovnet. So if Player-A needs to send a message to Player-B then can do so without routing everything through Server-1 or say if Player-B was geographically closer to Server-1 than Player-B then Player-A can route its messages through Player-B. The advantage of this routing mechanism is scalability, in a very basic implementation of p2p all parties have to connected to each other so if there were 8 peers than each peer would have to send any update messages to each and every peer, this adds considerable overhead and restricts scalability.

But the organization of the network isn't predetermined or necessarily mono-dimensional, you can view the network from a number of perspectives such that you could organize the network in terms of how close people are in that do their interactions affect each other? etc. etc.

The key concept behind spovnet is that the nodes in organize themselves into clusters, so if we had 3 clusters each with 4 players with one control player in each cluster, the control players would form a cluster that is a superset of all players. so if a player in one of the clusters needed to broadcast a message to all other players it would only need to be broadcast to the players in its cluster, upon reaching the control player for its cluster that message would then be broadcast to all members of the super cluster which would in turn disseminate said message down to all other players.

{l Code}: {l Select All Code}


  |            Application layer      |
  ------------------------------------
s |             |                     |
p |             |         CORDIES     |
o | MCPO        |---------------------|
v |             |          EONSON     |
n |-----------------------------------|
e |             Ariba                 |
t |                                   |
  |-----------------------------------|
  | TCP/IP etc.



ARIBA -Base layer, handles the communication between different nodes; allowing nodes to communicate with each other or every node through a self-organizing p2p network. http://ariba-underlay.org/

MCPO - provides multicast services, so disseminating messages from one player to every other player in an efficient manner through the spovnet. http://ariba-underlay.org/wiki/Documentation/MCPO

EONSON - provides publish/subscribe services through an event notification system. ie p1 and p2 are in the same area of a map and so are interested in each others activities http://ipvs.informatik.uni-stuttgart.de ... tion.shtml

CORDIES - provides event correlation, to detect complex event patterns and provide an appropriate response. p3 moves into the area containing p1 and p2 so cordies detects this pattern and joins p1,p2,p3 http://ipvs.informatik.uni-stuttgart.de ... tion.shtml



useful links:

http://www.SpoVNet.de

From the application perspective we build the message and event infrastructure and then a network manager that interfaces with the spovnet API and then done.

The games state is modified through the passing of messages, so as long as all changes by each client are propagated then all clients will have the same state. This doesn't include a mechanism for when the physics is processed on the client side! We'd have to create a p2p prediction & correction system for that to happen otherwise its sending positions.

There is also a networked multiplayer game already implemented using spovnet!
https://i72projekte.tm.uka.de/trac/SpoV ... plications

[Auria]

I'll let Joerg answer too; on my end I think SpoVNet looks interesting though built out of many components so maybe a little complex to deploy

[hiker]

Hi,

Brief of what i think so far:

Pure Client Server : cons{latency, cost}, pros{easy}

Cons: will not work in WANs.

Client Side Prediction : cons{Cost, difficulty}, pros{Hard to cheat, latency}

What exactly do you mean with Cost? Communication cost? And difficulty means implementation difficulty?
Pros: Bandwidth requirements only increase on server if number of clients increases.

Peer-to-Peer : cons{difficulty, cheating}, pros{cost}

Cons: bandwidth requirements increases on all clients if the number of connected peers increases (which is significant since most adsl connections offer a significant lower upload speed than download speed). Also I am not entirely sure if your p2p approach involves prediction. If not, and you want to do basically frame-by-frame exchange of steering information etc then I can tell you this will not work: we implemented this previously (it was intended for wired LAN usage), and became (from reports) unplayable the moment someone with a wireless network connection joined - not to mentioned latencies you will see when using WAN.

So the only option we can literally afford is p2p, all other options require a dedicated server that means hardware, bandwidth and maintenance aka money.

I don't agree with that. We need a server (which we already have - the addon server) to group people together, after that one of STKs of a player becomes the server. People can at the end vote a server up or down (perhaps including some warnings printed by the clients if certain inconsistencies are detected, e.g. too high speed etc.).

Cheating will be an issue, but remember this is open source and there isn't much we can do about it.

As I have written before - anything that just involves editing a simple (well documented) text file is imho too easy and should be discouraged. Cheating by actual code changes is indeed nearly impossible to prevent.

We can have a system of distributed authority where if a player seems to go too fast or be just that little bit too accurate then the nodes can detect this and flag it; given enough flags the player gets booted.

Yes, certain conditions could be checked, but this is going to be difficult - kicking someone off because he drives too accurate will result in complains

I did alot of research into networking api's such as RakNet and its base UDT not to mention ENET etc, I realized all they can provide is crossplatform sockets and not much else. I don't really want to be the one with the task of implementing an efficient p2p layer with all the accompanying work load so I went in search of an existing p2p layer and came across the SpoVNet project.


SpoVNet is an architecture for establishing “spontaneous virtual networks” that enable distributed end to end communication across a wide range of different protocols and infrastructures. For example if Player-A connects to the public Server-1 and then Player-B behind a NAT now connects to Server-1, then players A&B and Server-1 now form a spovnet. So if Player-A needs to send a message to Player-B then can do so without routing everything through Server-1 or say if Player-B was geographically closer to Server-1 than Player-B then Player-A can route its messages through Player-B. The advantage of this routing mechanism is scalability, in a very basic implementation of p2p all parties have to connected to each other so if there were 8 peers than each peer would have to send any update messages to each and every peer, this adds considerable overhead and restricts scalability.

Yes. But if you add other peers to forward/piggyback messages, you remove the advantage of low latency you mentioned above (assuming that your 'cost' is this), instead you get a higher latency than with client/server.

But the organization of the network isn't predetermined or necessarily mono-dimensional, you can view the network from a number of perspectives such that you could organize the network in terms of how close people are in that do their interactions affect each other? etc. etc.

The key concept behind spovnet is that the nodes in organize themselves into clusters, so if we had 3 clusters each with 4 players with one control player in each cluster, the control players would form a cluster that is a superset of all players. so if a player in one of the clusters needed to broadcast a message to all other players it would only need to be broadcast to the players in its cluster, upon reaching the control player for its cluster that message would then be broadcast to all members of the super cluster which would in turn disseminate said message down to all other players.

That is indeed a nice feature, but remember that this means the latency will in the scenario you describe increase 3-fold compared to a simple p2p approach, and it's 50% higher than client/server.

I will certainly have a look at SpoVNet (once we get 0.7.3. rc1 out), and the other libraries you've found - nice work.

...

From the application perspective we build the message and event infrastructure and then a network manager that interfaces with the spovnet API and then done.

The games state is modified through the passing of messages, so as long as all changes by each client are propagated then all clients will have the same state. This doesn't include a mechanism for when the physics is processed on the client side! We'd have to create a p2p prediction & correction system for that to happen otherwise its sending positions.

I don't really understand this - if all clients have the same state, this would include the position of the karts(?) If each client only handles its own physics, who is responsible for collision handling? Collisions are handled in bullet by a collision detection and correction algorithm: if two objects are intersecting, their position (and velocity, ...) are adjusted so that at the end of the physics step no more intersections exist. Who will do this in your p2p implementation?

There is also a networked multiplayer game already implemented using spovnet!
https://i72projekte.tm.uka.de/trac/SpoV ... plications

I can't reach this page atm, will try again later.

But generally, if you think that p2p is the way to go, feel free to go ahead, I am certainly not a game networking authority I am more than happy to create a branch for you - just let me know. I won't have time to do much for networking, since in the 0.8 releases I want to get the physics finalised first, but I am happy to help you with any questions you might have.

Cheers,
Joerg

[hiker]

One thing auria came just up with on irc:

it would be good if the 'hoster' (i.e. the person who opens a room) would initially distribute all his kart settings to all other peers. This would at least avoid some simple cheating (and if all peers exchange the data we can actually display messages if people are using modified data files), and also allow each peer to do additional tests, e.g. to see if a kart suddenly teleported itself to far ahead or so.

Cheers,
Joerg

[count_0]

Hi, this is Josh (I've been discussing some of the networking separately with hiker).

As an aside from this project, spovnet looks really interesting - where did you come across it kobos? Anyways, while it is interesting, I think that it is meant for more robust systems than this one (for instance, it provides a chord-based control overlay, which I can only assume is for some generic load balancing, something that is far beyond what is necessary for stk). I agree that spovnet seems to provide good support for a wide range of protocols and that it provides good scalability, but I think it is more robust than we need and that we don't really need to worry much about scalability (we will have a bounded number of karts, and therefore a bounded set of test parameters, so we only need to build a system that works under acceptable network conditions for our maximum-sized games). I would like to note that the client-server model is by far the most dominant in gaming, which seems to indicate it might be the better model; however, I am 100% supportive of kobos' interest in exploring the p2p model as well.

To do a little traffic analysis, lets assume a naive system in which each packet sent by each node must be received by each other node (I am very much not a graphics person, but I am a distributed systems person, so while I realize there will be aggregation at any server of the information for other nodes, I think that this analysis is still useful).

Now, assuming that in both the client-server model and the p2p model the servers are network-bound in their work, then we would just have to compare the overall traffic and latency using a single server, versus the traffic and latency for any subset of super-nodes. Any given super-node does receive less traffic from its subordinate nodes, in comparison to the single-server in the client-server model. However, if the single-server receives N bytes from K clients each second, then its total aggregate input is N*K bytes per second and its total output would be K*(K-1)*N. In the p2p model, any super-node receives N bytes from its P < K clients, but then for it to correctly propagate all of the information, it would have to receive the N*P bytes that each other super-node received, and so in the end would receive N*K bytes per second, but would only have to send its aggregated information to its subset of P nodes.

Therefore, in the naive case where each node has to send all of its packets to each other node, each super-node in the p2p system ends up processing much the same input as the single-server in the client-server model, but less output on an individual basis. For the whole system, there ends up probably being more total network traffic for the p2p model because there would be some replication of messages in sharing information between super-nodes. So the p2p model could only outperform the single-server model if the extra latency (as pointed out by hiker) from having the intermediate super-nodes and an overall increase in network traffic was outweighed by the total decrease in processing time and client-bound network traffic from each super-node to its set of clients.

In the end, i would say that clustering is an interesting idea, but the fact that it introduces a definite latency with an uncertain benefit means that we should not engineer the system as a p2p network. I advocate that we build the initial implementation using a basic client-server model and get it working. Then, if we still have the people and the interest, we could do some performance testing of the client-server model against a p2p clustering model (which we could build ourselves using the client-server model as a basis; I argue that this would not be overly difficult and that it would probably provide better performance than using spovnet since we could engineer to with only the frills that we need).