Reliable Ordered Messages

http://gafferongames.com/building-a-game-network-protocol/reliable-ordered-messages/

by adamnemecek • 10 years ago

85 28 10 years ago

dividuum• 10 years ago

Nice blog post. It reminded me a bit about how QuakeWorld did networking over UDP back in the days. There is a post about it here: http://fabiensanglard.net/quakeSource/quakeSourceNetWork.php. I remember implementing that myself for a networked version of jump'n'bump which never got anywhere :-)

jhasse• 10 years ago

Jump'n'bump rocks!

derefr5• 10 years ago

Many people will tell you that implementing your own reliable message system on top of UDP is foolish.

It is foolish: both SCTP (over UDP) and RTP+RTCP (over UDP) already exist, and in combination do exactly what the author wants. There are more things in this world than TCP and "your own custom protocol."

It's almost like the 'network engineers' in gaming have never looked at the network architecture of a telecom system. Same problems: well-known standard solutions.

(There is one case where inventing your own transport protocol instead of reusing the standard ones makes sense: when every higher-level protocol but one is blocked, forcing you to tunnel over that one protocol. Thus WebRTC. But now that's a standard too, so don't reinvent that either!)

toomim• 10 years ago

It is foolish: both SCTP (over UDP) and RTP+RTCP (over UDP) already exist, and in combination do exactly what the author wants.

Can you explain this? What parts of "what the author wants" are implemented by which features in these protocols?

vvanders3• 10 years ago

And it's almost like network engineers haven't looked at what gaming does.

it is message-oriented like UDP and ensures reliable, in-sequence transport of messages with congestion control

Emphasis on the sequencing. Usually in games we send multiple channels over a single connection and head of line blocking will wreak havok on your simulation.

In addition you may want different(or no) congestion control which can have significant impact on the realtime nature of your packets(I've looked at WebRTC, it doesn't make any of guarantees that you'd need in games).

derefr5• 10 years ago

What are you quoting? I said in combination:

• SCTP or RTCP for data that needs to arrive (both are reliable, multiplexed connection-oriented protocols, like HTTP2, where packets are demultiplexed into ordered sequences at the receiver, but are not forced into a global linearized order on the wire)

• RTP for data that can be dropped. (Using RTP's realtime-video streaming dataflow semantics, under which congestion-control is handled via the client's transport layer informing the server's application layer of a reliability rate, and the server being able to do things like send more/fewer packets, or just change the data being sent to an entirely different stream, in response.)

CamperBob23• 10 years ago

It's almost like the 'network engineers' in gaming have never looked at the network architecture of a telecom system. Same problems: well-known standard solutions.

Not even remotely.

The biggest difference is that in commercial telecom, there's no such thing as obsolete data that can be safely dropped. If an audio stream packet doesn't arrive in time, the user will perceive a glitch, which the codec may or may not be able to cover up psychoacoustically. So these users try hard to prioritize reliable delivery whenever possible. Telecom's mission is to emulate a circuit-switched network with packet switching, which, while necessary, is never going to be the right strategy in the general case.

In game networking, on the other hand, a 200-millisecond-old packet is like a week-old newspaper. If it doesn't arrive in a reasonable amount of time, there's no upside to delivering it at all. The client is better off waiting for the next update from the server, relying on local prediction in the meantime. There's an excellent chance that the user will never notice the dropped packet(s).

This fact by itself means that any application-agnostic attempt to implement reliable delivery or packet sequencing is a waste of time from a game developer's perspective. Streaming protocols developed for video and other media may be a better match, but they still won't be ideal for a use case involving interactivity and client-side prediction. (For one thing, any media streaming protocol is likely to be more concerned with bandwidth over latency, and games live and die over the latter.)

People have been trying to come up with "one transport protocol to rule them all" since TCP/IP, and have always failed spectacularly. There's always going to be room for interesting work in this space, and the notion that an entire class of users should "just use XYZ/IP" or whatever is always going to be as misguided as the early recommendations to ignore UDP in favor of TCP were.

derefr5• 10 years ago

You attacked a strawman (a "telecom" engineering that hasn't been taking the concerns of realtime video into account every telecom protocol for the last 20 years.) Video has exactly the semantics you're talking about, and video-typed flows in RTP et al are interactive channels (originally, to enable adaptive streaming) in exactly the way games need for their data.

(The sending of extra information to enable client-side prediction, on the other hand, is something that can be added without altering the transport layer at all. Layering!)

Bytes on the wire are bytes on the wire. It doesn't matter what vertical you're working in; it just matters how the bytes on the wire need to behave. People should forget about the fact that something is "a game" and just look for wire-protocol structural isomorphisms before assuming their case is so unique.

felixgallo5• 10 years ago

Oh hi! I'm a network engineer! In gaming! I happen to routinely use 'the network architecture of a telecom system' via erlang so I may be qualified to answer your post.

RFC 6951 style SCTP-over-UDP is not super widely implemented, so you end up having to implement it yourself. When you're doing so, you pretty quickly realize that it's significantly more heavyweight than anything you actually need for a game (e.g. https://tools.ietf.org/html/rfc4960#section-5.1.6), while at the same time missing several key facilities, such as knowing instantly, with every packet received, which of the previous (e.g.) 32 packets have also been received, and so forth.

RTP has the same problem. There's fields included with every packet (SSRC, CSRC, others) which are irrelevant to gaming. There's a bunch of libraries, most of which are total junk. There are end to end compatibility problems owing to different interpretations of the spec.

This turns out to be a gigantic problem, because gaming network engineers use all sorts of ridiculous tricks to try to bum every last byte out of their protocols. For an entertaining afternoon check out http://gafferongames.com/2015/03/14/the-networked-physics-da....

A much more relevant criticism might be, well why don't you use, e.g. protobuf rather than invent your own framing system? Because the case of protobuf -- where you want, essentially, to transmit a purpose designed struct directly over the wire with no bullshit -- is very much like the case of a twitch game network protocol and comes pretty close to hand-bummed byte sizes; close enough that the benefits of using something a bit more extensible and introspectable might be worth it.

Anyway, in short, you don't know what you're talking about and Glenn is a national treasure.

derefr5• 10 years ago

Thanks for that, it was informative! I mean, I certainly don't know what I'm talking about with respect to the specific protocols; SCTP and RTP were ones off the top of my head that seemed to fit the use-case. (I have used both—from Erlang, coincidentally!—as part of real-time collaboration software before. But the "real-time" there isn't nearly the same "real-time" as twitch games have, so I never really needed to dig deep into their semantics.)

I think I got off-track of the original thing that incensed me, though: it's not that there's any perfect existing network protocol that does everything the way games need it.

Rather, my thought was based on this premise: the OSI protocol-layering model is awesome. It allows you to have a stack of very thin protocol layers (e.g. UDP itself) that just add one single thing to the semantics of the layer below them, with as little overhead as it's possible to get away with in doing that. Thin layers, because they just Do One Thing Well, are easy to engineer and QA and port, so you often find (good!) libraries for them available for every platform. Creating your own custom protocol that re-implements the feature a thin protocol layer is intended to provide, often doesn't reduce overhead at all, and in the process often results in worse and less-tested code than you'd get by writing the rest of your custom code on top of the thin layer.

So: maybe you can't find a perfect "gaming protocol." But I can't believe that the most sensible thing to do is to implement one directly on top of UDP, rather than using A and B and C orthogonal protocol layers on top of UDP to handle A and B and C features, and then only coding the stuff that's left over.

In other words: why write your own multiplexing code instead of relying on existing session-layer logic? And why, indeed, write your own network-encoding code instead of relying on existing presentation-layer logic (like, of course, Protobuf)? And on and on for eight to ten other concerns it's possible to "pull out" of any given protocol.

vvanders3• 10 years ago

Agreed with everything above, one of the things I love about games is the really unique problems they tend to present.

FWIW if you're looking at protobuf then take a peek at flatbuffers[1]. We found that protobuf's allocation was hurting perf and flatbuffers fit the same role with much better performance.

[1] https://google.github.io/flatbuffers/

the_angry_angel• 10 years ago

why don't you use, e.g. protobuf

protobuf sounds attractive, but (unless I've missed something in protobuf's implementation), but out of the box you have 2 issues:

1. Protobuf doesn't/can't deal with fragmentation - so you'd have to ensure your protobufs are small enough to fit inside a UDP packet

2. Without a wrapper you couldn't put multiple small protobufs into a single UDP packet?

Both things are fixable by wrapping protobuf, but I suppose if you're trying to get something as small as possible, can you actually just do better by avoiding protobuf in the first place (I guess the answer is yes?)

jwatte2• 10 years ago

To be fair, protobuf adds field-and-type framing for each field, which a known-in-sync client/server don't need; that adds up to 10-30% over a full packet!

jephir• 10 years ago

There's a lot of talk here about TCP vs UDP vs SCTP vs x protocol.

It's important to keep in mind that this is all optimization. Don't lose sight of the big picture.

On one RTS we ended up just serializing world state over a TCP socket. If you can get away with the brute force approach then just do it. Don't optimize until you have a measurable performance problem.

caseymarquis• 10 years ago

Glad to read anything I can regarding networking applications in practice.

Transmitting between embedded devices and PCs, I've been stuck with either Tcp or Udp; no other protocols are typically implemented on the embedded side. I've found sending reliable ordered messages requires implementing something on top of either protocol. Udp is great for concrete messages, but doesn't give you ordered reliability, Tcp has the opposite problem where the streaming nature means you need to wrap messages and occasionally confirm proper receipt of a message to figure out when old messages can be tossed. The issue with Tcp being that when the connection breaks down, you don't in practice know exactly where it broke and if the other side received several completed messages and acted on them, or if you need to resend.

I'd initially assumed Tcp would cover all my needs. Didn't take much initial research to figure out that wasn't true.

Reliable Ordered Messages

Related Stories