Friday Facts #136 - Map Transfers

[cube]

I've written tutorials on the subject and made many programs for networking, so some suggestions from me:

1. As ikris points out, please request for mapping (I believe RFC 6887 - PCP mapping dynamics? It's been a few years, I might be rusty)
2. Using TCP does not require a return acknowledgement....it's automatic inside the protocol. You can setSendBufferSize (or setsockopt with SO_SNDBUF, depending on what tool you're using) in order to change the amount of data to buffer up through the protocol ahead of time, but a default amount is usually good enough. When you actually "send" the data, it returns a value which matches how much of the data is actually placed into this buffer for transfer. When this value is less than the amount you actually specified, that means the buffer is full and network has congestion. So, you truncate the data you just sent and wait a few ticks to try again. In order to not block the network onto any given player from the server, you can track the data-per-second rate of each player and keep them at an average level.
3. I would suggest using a separate TCP connection to send map details, and you can actually send the chunks on an as-needed basis. Any update information as the player receives it under the normal connection can be packed until the chunk is sent from the snapshot and applied afterward. This will allow players to immediately play within a small area at the start and the area will increase as chunks become available. It will help the server from having a bottle-neck of update data (as in #2, each connection can be divided by network traffic usage, so chunk data won't bog everything down).
4. In terms of saving locally, this could help even further by giving the player a map to start with, and then updating the chunks. Simply mark all chunks as "not updated" and request each chunk as needed while the player plays....there might be tearing, but at least they'll be playing immediately.
5. Make use of OOB for immediate data....like biter attacks, those are more important than details of whether the iron plate in the furnace is done.

1. Yes
2. It doesn't? ACKs (in some form) need to be sent for every packet received, don't they?
3., 4 and 5. As ssilk said, this can't be done in our current lock step simulation. We don't send biter attacks at all. Every player has the whole map and independently decides (at exactly the same tick) that biters should attack. Once a second (IIRC) we send a CRC to see if they all decided correctly.

[bNarFProfCrazy]

I really like those technical stuff.

However I'm wondering a little bit that you try to reimplement stuff that was published in 1999.
If it is a good solution, then someone already made this (and thus has far more experience than you).
If it is a bad solution, then nobody bothered to wrap this in a libary and you should not use it as well.

KISS: Keep it short and simple. Be satisfied with 90% network throughput and avoid the extra lines to get some extra %.
More code -> less readable + more complicated -> more bugs + higher maintenance costs

I love special case handling myself, but please provide simple solutions for the normal high speed internet comunity as well.
(PS: I usually use a (selfmade) VPN to connect to the other peers to avoid all the UDP punch holing, NAT, IP6to4to6 tunneling, firewalls, packet loss and funky artifacts.
My connection works so I don't need any extra code that slows my connection down in the assumption that it might fail, but doesn't)

EDIT:

The TCP Westwood+ version is implemented in the Linux kernel.

from Wikipedia

[cube]

What I don't understand is why the maps need to be so big. Wouldn't a seed and a diff be both sufficient and relatively small?

Try generating a 4000x4000 tile map once vs loading a 4000x4000 map and let me know how that goes. A rough estimate: generating would take 10~ minutes, loading takes 20 seconds.

There is in fact one trick that could be done -- mark chunks as clean / dirty and ungenerate clean chunks after some time. This might slightly decrease save size (and by that a file size needed to download). It wouldn't help much though, because clean chunks are empty and contain just a few trees, and it would make saving more complicated and fragile. Maybe 0.15, :-)

[indjev99]

The post was really interesting, even though I didn't manage to follow everything (although that might have been caused by the fact that I read it at 3am).

[sabriath]

It sounds like a solution but is not possible. The game needs to have the whole map, before it can start simulation,

In a "not updated" chunk, the client doesn't have to simulate that chunk at all, all objects can be considered disabled (just like when you deconstruct things). The point I was making is to allow the player to walk around and get right into gameplay even though the map isn't finished downloading. When a player logs in, the first 25 chunks are sent to the player in the surrounding 5x5 area for example, but all the other chunks are not that important and can be sent over time.

otherwise the determinism between two players computers isn't guaranteed. Simple example: you make a long belt far from the outlands into your factory. Then you need to load also that outpost, before simulation can start.
The FFF linked to other articles where that is explained.

That doesn't matter much, it's a visual problem more than anything, like seeing material on the belt when there isn't any...or none when there is some. Each chunk could have an associated game tick with it, and if an item hits a boundary to a chunk that isn't updated or is paused, that chunk pauses completely and keeps track of that game tick along with placing the action into a queue. When the action is able to be performed again (by either the chunk getting loaded in, or unpaused), it unpauses the chunk and begins to fast forward until it reaches the sync game tick.

The issues this would solve is huge. First, the entire world doesn't have to be downloaded in order to play, it's all visual anyway....which also means that if a person keeps getting disconnected, they are not wasting so much bandwidth. Secondly, each chunk can be given a checksum for local storage and matched with the server faster....there's no need to download a map that hasn't changed.

The other idea would be to link belts, railways, pipes, etc. on separate "networks." As each entity connects with another, it chains them into a net that can be saved as a "chunk" (but not of a specific size, more like a blueprint)....each actual chunk can point to this net as containing it for reference. This way when you download the network from the server, it can simulate it, even if all the chunks aren't loaded yet.

2. It doesn't? ACKs (in some form) need to be sent for every packet received, don't they?

Not with TCP. The protocol has a buffer for sending and receiving, and upon first connection, a random first SEQ value is determined. As data is transferred, this SEQ is incremented to denote how much data has been sent and received...each packet sent, tells the other side what SEQ it currently is. The receiver sends back ACK messages telling the sender what SEQ it last updated and how far along the continuous data stream it is....which the sender updates its buffer to erase the data it doesn't need to send anymore. These 2 windows wrap around and keep synced with each other automatically.

So....if you are sending your own ACK messages, you are actually putting more bandwidth on the line because then the TCP is telling the server your message while simultaneously telling the protocol that it received it. It's kinda like your buddy telling you on the phone that he's having a party, and you say "ok"....but then you call back and tell him "I received your message." It's redundant.

[bNarFProfCrazy]

otherwise the determinism between two players computers isn't guaranteed. Simple example: you make a long belt far from the outlands into your factory. Then you need to load also that outpost, before simulation can start.
The FFF linked to other articles where that is explained.

That doesn't matter much, it's a visual problem more than anything, like seeing material on the belt when there isn't any...or none when there is some. Each chunk could have an associated game tick with it, and if an item hits a boundary to a chunk that isn't updated or is paused, that chunk pauses completely and keeps track of that game tick along with placing the action into a queue. When the action is able to be performed again (by either the chunk getting loaded in, or unpaused), it unpauses the chunk and begins to fast forward until it reaches the sync game tick.

The issues this would solve is huge. First, the entire world doesn't have to be downloaded in order to play, it's all visual anyway....which also means that if a person keeps getting disconnected, they are not wasting so much bandwidth. Secondly, each chunk can be given a checksum for local storage and matched with the server faster....there's no need to download a map that hasn't changed.

Please read the entire thread. Every chunk of the world is important to the world as such, because of polution, pathfining, general AI, resources... even "empty" chunks.

it's all visual anyway

No its not. There isn't the MC style server client architecture. Its more like a master server and client server. Every "client" calculates everything the server does and only does some did the server do the calculations same as I checks from time to time.

Theoretically if nobody (player) does anything on the map (move, build etc) then you could cut the internet connection and both games should run in parallel without issues or deviations.

If you hide a single change (broken belt) from the server then you will desync with the server, however from your point of view everything is alright and you can still create a valid save game. (Its just not the same as the server's one)

2. It doesn't? ACKs (in some form) need to be sent for every packet received, don't they?

Not with TCP. The protocol has a buffer for sending and receiving, and upon first connection, a random first SEQ value is determined. As data is transferred, this SEQ is incremented to denote how much data has been sent and received...each packet sent, tells the other side what SEQ it currently is. The receiver sends back ACK messages telling the sender what SEQ it last updated and how far along the continuous data stream it is....which the sender updates its buffer to erase the data it doesn't need to send anymore. These 2 windows wrap around and keep synced with each other automatically.

So....if you are sending your own ACK messages, you are actually putting more bandwidth on the line because then the TCP is telling the server your message while simultaneously telling the protocol that it received it. It's kinda like your buddy telling you on the phone that he's having a party, and you say "ok"....but then you call back and tell him "I received your message." It's redundant.

This would be true if they used TCP, but they only use UDP, so they don't have those ACK messages.


However your idea with the sending only the changes is worth being discussed.
On first connect this won't help you, but on first connect your savegame is usually small.
However if you play a longer time you will probably create some autosaves and could then do some kind of incremental update.

Or create a save option that triggers all other clients to create a (hidden) MP save as well, and load that on all clients simultaneously (maybe while waiting in a lobby).
However this will not help anything on real servers, since you won't play at the same time usually.

[CrushedIce]

I think something really useful would be some kind of lobby screen, which allows players who already have the savegame the host wants to load, to join without transferring the map.

For example i have a 2 player coop game, which i never played without my friend. So it is completely unnecessary to transfer the (~30MB) map each time.

[LucidMoses]

Since you have some known information that is not know in general solutions. i.e. you have a minimum latency requirement, a minimum through put requirement and a constant flow of data (I think). Then you can accomplish this in a different way. S=Server, C=Client

S-pick a delay. every so often (say 20 seconds) reduce it by one.
S-Create a number of packet buffers.
S-give each packet a sequence number.
S-Just keep sending packets with said delay between packets.
S-watch for requests and if you get one. resend the packet increase the delay if the delay goes higher then your min end the session. if the request if for a packet that is too old end session.

C-read packets. If packet sequence if one higher then the last one. Great, your done. other wise
C-keep storing packets and request resend of missing sequence number.


Ok, so I left a bunch of details out but you should get the idea. For the resend requests I sometimes just use a TCP connection and don't bother with the details of the request resend messages getting lost.

[ikiris]

I've written tutorials on the subject and made many programs for networking, so some suggestions from me:

1. As ikris points out, please request for mapping (I believe RFC 6887 - PCP mapping dynamics? It's been a few years, I might be rusty)
2. Using TCP does not require a return acknowledgement....it's automatic inside the protocol. You can setSendBufferSize (or setsockopt with SO_SNDBUF, depending on what tool you're using) in order to change the amount of data to buffer up through the protocol ahead of time, but a default amount is usually good enough. When you actually "send" the data, it returns a value which matches how much of the data is actually placed into this buffer for transfer. When this value is less than the amount you actually specified, that means the buffer is full and network has congestion. So, you truncate the data you just sent and wait a few ticks to try again. In order to not block the network onto any given player from the server, you can track the data-per-second rate of each player and keep them at an average level.
3. I would suggest using a separate TCP connection to send map details, and you can actually send the chunks on an as-needed basis. Any update information as the player receives it under the normal connection can be packed until the chunk is sent from the snapshot and applied afterward. This will allow players to immediately play within a small area at the start and the area will increase as chunks become available. It will help the server from having a bottle-neck of update data (as in #2, each connection can be divided by network traffic usage, so chunk data won't bog everything down).
4. In terms of saving locally, this could help even further by giving the player a map to start with, and then updating the chunks. Simply mark all chunks as "not updated" and request each chunk as needed while the player plays....there might be tearing, but at least they'll be playing immediately.
5. Make use of OOB for immediate data....like biter attacks, those are more important than details of whether the iron plate in the furnace is done.

1. Yes
2. It doesn't? ACKs (in some form) need to be sent for every packet received, don't they?
3., 4 and 5. As ssilk said, this can't be done in our current lock step simulation. We don't send biter attacks at all. Every player has the whole map and independently decides (at exactly the same tick) that biters should attack. Once a second (IIRC) we send a CRC to see if they all decided correctly.

On the ACKS, sort of, but they mostly meant its abstracted by the OS and you shouldn't be dealing with it anyway, which is his point on the send buff. If you jack it up initially you can bypass slow start.

The sort of is because of selective ack and nagle. Every packet is acked, but not every packet requires a standalone ack. That's the whole point of the send and receive buffers and their matching windows.

[ikiris]

It was fun to read, I love technical details, however, I feel that firewall, NAT-stuff are non-issues:

... NAT punching ...

If you can open a port on UDP in a firewall then you can open a port on TCP as well.

You should read about http://en.wikipedia.org/wiki/UDP_hole_punching

The same technique is sometimes extended to Transmission Control Protocol (TCP) connections, with less success due to the fact that TCP connection streams are controlled by the host OS, not the application, and sequence numbers are selected randomly; thus any NAT device that performs sequence number checking will not consider the packets to be associated with an existing connection and drop them.

And 90% of this horrible hacky mess isn't necessary if they just used a normal modern library or implemented proper upnp/PCP requests, as enough clients support it that critical mass is achieved enough so that someone can host without issues.

[emithekiller]

What about stopping the game for a second, make a checksum and compare it with the other peers before deciding whether to download the map or not? Or instead downloading the whole map using an algorithm (which I know is more difficult saying than making) which compares the original map seed and the actual and sends only the difference between both. Maybe instead rebuilding the whole map uses the original one and just applies the changes... Well I'm no game developer I just now something about networking ( Did some programs with python and sockets) and loved the technical FFF

[Impatient]

What I don't understand is why the maps need to be so big. Wouldn't a seed and a diff be both sufficient and relatively small?

i imagine, they don't trust the Random Number Generators, the algorithm uses, on different machines, to produce the same results. one could try to generate the same map on different machines and for every part of the map one could send a hash value and compare if it is the same. but what in case it is not (thus the algorithm did not produce the same map on different machines)? then the engine would have to have a way of transmitting the map anyways. and what about all the entities on the map? they too have to be saved, loaded and transmitted somehow.

[roaringdragon2]

I rather liked this one. I don't understand networking very well, and you just improved my understanding of it! : D

[dee-]

Please finally stop welding your own UDP/whatever-protocol.
Use a standardized and real-world-proven protocol and be done.

I know you guys really are smart, so no need to cling to the NIH-syndrome.

I too created my own network protocols, filesystems and whatever back in the MS-DOS times, good times, but (gladly) we've outgrown these and can now stand on the shoulders of giants.

[pr0n]

Completely agree with dee-. As a network engineer I can assure you that you will be tweaking this new cube wheel (get it?) you've invented until the end of time.

There are companies out there that this is literally all they do, because of that they are really good at it. So you have a choice to make. Be mediocre at many things or get help with certain aspects and be really good at 1 thing (making games).

jenkinssoftware
SDL_net
boost
github /google/protobuf#
zeroc
poco libraries
there are many more

I don't mean to sound rude but I've ventured down paths like this myself and lived to regret it.

That said, you've unfortunately done a lot of the work already and by the sound of it you've exchanged wedding vows with this setup so, best of luck to you guys.

[DaveMcW]

Use a standardized and real-world-proven protocol and be done.

"The nice thing about standards is that you have so many to choose from."
Computer Networks, 1st ed., 1981, p. 168

[cube]

Please finally stop welding your own UDP/whatever-protocol.
Use a standardized and real-world-proven protocol and be done.

I know you guys really are smart, so no need to cling to the NIH-syndrome.

I too created my own network protocols, filesystems and whatever back in the MS-DOS times, good times, but (gladly) we've outgrown these and can now stand on the shoulders of giants.

Yes, this whole thing is about 70% NIH syndrome. We're trying to find a balance between using existing libraries and writing our own and it seems that in this case that we have pretty solidly misjudged the complexity of a custom implementation. But the networking API that we created is now so deeply coupled into the MP code that I can't imagine replacing it. It would probably improve the whole thing, but at a cost of several MP-only releases ... and our code is always just one small fix from working correctly ...

[ikiris]

Please finally stop welding your own UDP/whatever-protocol.
Use a standardized and real-world-proven protocol and be done.

I know you guys really are smart, so no need to cling to the NIH-syndrome.

I too created my own network protocols, filesystems and whatever back in the MS-DOS times, good times, but (gladly) we've outgrown these and can now stand on the shoulders of giants.

Yes, this whole thing is about 70% NIH syndrome. We're trying to find a balance between using existing libraries and writing our own and it seems that in this case that we have pretty solidly misjudged the complexity of a custom implementation. But the networking API that we created is now so deeply coupled into the MP code that I can't imagine replacing it. It would probably improve the whole thing, but at a cost of several MP-only releases ... and our code is always just one small fix from working correctly ...

Well, you're basically going to have to, or alternatively you're going to have to get used to the idea of using your own infrastructure as relay servers. You still have got to fix the latency hiding issues though. The experience is still terrible, and reminds me of 90s starcraft, which is the point. Those who refuse to learn from history, are doomed to repeat it, apparently step by step and in order.

[ratchetfreak]

on acks you don't need to send a separate ack for each packet received. Instead you can send the sequence number of the highest received packet from each peer and a 32 or 64 length bitvector of which previous packets were received from that peer.

Embed it into each packet sent to that peer and let him decide whether the information in a packet needs to be resent.

[malecord]

EDIT:

The TCP Westwood+ version is implemented in the Linux kernel.

from Wikipedia

It's incomplete information.
It is implemented in linux kernel but is not the default congestion control algorithm since quite a long time. CUBIC is.


I'll deliberately oversimplify here. But one can say that Westwood+ is the refinement of the original algorithm (Reno, the one usually found in university textbooks) which has been developed when computer networks had very frequent packet losses (and not secondary, Internet was supposed to withstand a nuclear war so a quite different definition of unreliable networks).

As it often turns out with the improvement of science it became clear that the idea behind Westwood+ (i.e. being superaggressive) is inefficient. Intuitively, when saturation occurs the windows is halved and so for a period of time some bandwidth is not used. Because this not utilized space depends on the total bandwidth, the larger is the total bandwidth the larger is the inefficiency. As we know the average available bandwidth increases dramatically each passing year. So Westwood becomes more inefficient each passing year.

Better near perfect algorithms to manage congestion exist since long time (like Vegas). However because most computers already use Westwood, the aggressive behavior of Westwood became part of the problem too (again simplifying: in a LAN with 2 vegas PC you would have optimal and fair bandwidth usage, in a LAN with one vegas and one westwood PCs Westwood would take all bandwidth). New algorithms were developed to also include "Westwood resistance" among their features so that they could be effectively used in the real Internet.

Cubic is one of the many algorithms that improves bandwidth usage by being cautious enough to reduce the number of losses due to band saturation and at the same time is strong enough to survive in a world where most computers use Westwood with its super aggressive behavior. And it does it well enough to be the default CC of linux. When I studied this stuff Microsoft was using Compound. I don't know what it uses now.



My 2 cents here (take it for what it is, I work on different stuff today): I'm super sure that Factorio team has good reasons to "re-invent the wheel" and build a TCP like protocol over UDP. But this is only apparently an easy task. It's actually a very risky one: just because it's very difficult to test this stuff effectively (for non local LAN multiplayer at least). It may very well be that given your "small use case" you'll find a good implementation for Factorio. But it's no doubt that this is a path plenty of pitfalls. Maybe your time would be spent better trying to avoid this path entirely.

Whatever you decide to do, GL!