October 2001
- (no subject) J C Lawrence
- Lum the Mad is closing--sort of Koster, Raph
- Questing (was: Request for ideas) Eli Stevens
- Questing (was: Request for ideas) Joe Andrieu
- Questing (was: Request for ideas) Matt Mihaly
- Questing (was: Request for ideas) Sellers, Mike
- Questing (was: Request for ideas) Vincent Archer
- contract games/markets (was: Request for ideas) Bruce Mitchener
- DEV: Peer-to-Peer MUD Phil O'Donnell
- DEV: Peer-to-Peer MUD Dan MacDonald
- DEV: Peer-to-Peer MUD Robin Lee Powell
- DEV: Peer-to-Peer MUD Justin Rogers
- DEV: Peer-to-Peer MUD Adam Martin
- DEV: Peer-to-Peer MUD Frank Crowell
- Psychology and game design (Was Geometric content generation) John Hopson
- Psychology and game design (Was Geometric content generation) Ola Fosheim Grøstad
- Psychology and game design (Was Geometric content generation) Dave Rickey
- Psychology and game design (Was Geometric content generation) Ola Fosheim Grøstad
- Psychology and game design (Was Geometric content generation) Matt Mihaly
- Psychology and game design (Was Geometric content generation) Ola Fosheim Grøstad
- Psychology and game design (Was Geometric content generation) rayzam
- in-game vs web-based boards (was: Geometric content generation) Freeman, Jeff
- State of the RP: Verant's attempt at a RP Server Eric Rhea
- New MMP Networking Architecture Lee Sheldon
- New MMP Networking Architecture Adam Martin
- New MMP Networking Architecture Bruce Mitchener
- New MMP Networking Architecture Ling Lo
- New MMP Networking Architecture Norman Nunley, Jr.
- Mucking about in time Eli Stevens
- Mucking about in time Travis Casey
- Mucking about in time Adam Martin
- Mucking about in time John Robert Arras
- Many MUDs in one? (was: Geometric content generation) Ian Collyer
- Many MUDs in one? (was: Geometric content generation) Matt Mihaly
- Many MUDs in one? (was: Geometric content generation) Robin Lee Powell
- Pueblo still kicking Jon Lambert
- FWD: Call for papers: AAAI symposium on AI and Interactive Entertainment Robert Zubek
- Game Theory Introduction Ling Lo
- MUD-Dev digest, Vol 1 #438 - 22 msgs Phil O'Donnell
- Uniqueness of Games Adam Martin
- Uniqueness of Games Ling Lo
- Psychology & Player Motivation (was Geometric Content Generation) Sasha Hart
- Simulation, just how much? (was: Uniqueness of Games) Derek Licciardi
- Laws of Competition Matt Mihaly
- UDP Revisted Daniel.Harman@barclayscapital.com
- UDP Revisted Brian Hook
- UDP Revisted Bobby Martin
- UDP Revisted Brian Hook
- UDP Revisted Dave Rickey
- UDP Revisted Daniel.Harman@barclayscapital.com
- UDP Revisted Dave Rickey
- UDP Revisted Travis Nixon
- UDP Revisted Amanda Walker
- UDP Revisted Brian Hook
- UDP Revisted Ben Greear
- UDP Revisted amanda@alfar.com
- UDP Revisted Brian Hook
- UDP Revisted Travis Nixon
- UDP Revisted Daniel.Harman@barclayscapital.com
- UDP Revisted Travis Nixon
- UDP Revisted David H. Loeser Jr.
- UDP Revisted Adam Martin
- UDP Revisted Bobby Martin
- UDP Revisted Bobby Martin
- UDP Revisted Kwon Ekstrom
- UDP Revisted Bruce Mitchener
- UDP Revisted Bobby Martin
- UDP Revisted Bruce Mitchener
- UDP Revisted Daniel.Harman@barclayscapital.com
- Procedural content generation Brian Hook
- Procedural content generation John Buehler
- Procedural content generation Brian Hook
- Procedural content generation John Buehler
- Procedural content generation Hans-Henrik Staerfeldt
- Procedural content generation lhulbert@hotmail.com
- Procedural content generation Travis Nixon
- Procedural content generation Ola Fosheim Grøstad
- Procedural content generation Daniel.Harman@barclayscapital.com
- Procedural content generation Daniel.Harman@barclayscapital.com
- Procedural content generation Freeman, Jeff
- Procedural content generation Matt Mihaly
- Procedural content generation Ola Fosheim Grøstad
- Simulation, Christopher Allen
- Simulation, Travis Casey
- MMORPG Comparison (UO, EQ, AC, AO, DAoC) Dave Kennerly
- MMORPG Comparison (UO, EQ, AC, AO, DAoC) Robin Lee Powell
- MMORPG Comparison (UO, EQ, AC, AO, DAoC) Dave Rickey
- MMORPG Comparison (UO, EQ, AC, AO, DAoC) John Buehler
- MMORPG Comparison (UO, EQ, AC, AO, DAoC) Dave Rickey
- MMORPG Comparison (UO, EQ, AC, AO, DAoC) John Buehler
- MMORPG Comparison (UO, EQ, AC, AO, DAoC) Brian Hook
- MMORPG Comparison (UO, EQ, AC, AO, DAoC) John Buehler
- MMORPG Comparison (UO, EQ, AC, AO, DAoC) Daniel.Harman@barclayscapital.com
- MMORPG Comparison (UO, EQ, AC, AO, DAoC) Vincent Archer
- MMORPG Comparison (UO, EQ, AC, AO, DAoC) Derek Licciardi
- MMORPG Comparison (UO, EQ, AC, AO, DAoC) John Buehler
- MMORPG Comparison (UO, EQ, AC, AO, DAoC) Dave Rickey
- MMORPG Comparison (UO, EQ, AC, AO, DAoC) Dan Burke
- Simulation, Adam Martin
- UDP Revisited Daniel.Harman@barclayscapital.com
- UDP Revisited Brian Hook
- UDP Revisited Mats Lidstrom
- UDP Revisited Jeremy Gaffney
- Simulation Revisited Dave Rickey
- TCP Vegas Adam Martin
- Procedural content generation, randomness Adam Martin
- Procedural content generation, randomness Brian Hook
- Content authorship Adam Martin
- Content authorship Ola Fosheim Grøstad
- Content authorship Travis Casey
- DAoC dev team (was: MMORPG Comparison (UO, EQ, AC, AO, DAoC)) Eli Stevens
- DAoC dev team (was: MMORPG Comparison (UO, EQ, AC, AO, DAoC)) Dave Rickey
- DAoC dev team (was: MMORPG Comparison (UO, EQ, AC, AO, DAoC)) Ola Fosheim Grøstad
- DAoC dev team (was: MMORPG Comparison (UO, EQ, AC, AO, DAoC)) Robin Lee Powell
- DAoC dev team (was: MMORPG Comparison (UO, EQ, AC, AO, DAoC)) Brian Hook
- DAoC dev team (was: MMORPG Comparison (UO, EQ, AC, AO, DAoC)) Daniel.Harman@barclayscapital.com
- DAoC dev team (was: MMORPG Comparison (UO, EQ, AC, AO, DAoC)) Neufeld, Don
- DAoC dev team (was: MMORPG Comparison (UO, EQ, AC, AO, DAoC)) Brian Hook
- DAoC dev team Dave Rickey
- SSL vs. SASL (was: UDP Revisted) Bruce Mitchener
- MUD-Dev digest, Vol 1 #445 - 27 msgs Paul Schwanz
- MUD-Dev digest, Vol 1 #445 - 27 msgs Travis Nixon
- Proposed Law John Buehler
- Proposed Law Matt Mihaly
- Proposed Law John Buehler
- Proposed Law Freeman, Jeff
- Proposed Law John Buehler
- Proposed Law Matt Mihaly
- Proposed Law John Buehler
- Proposed Law Matt Mihaly
- Proposed Law John Buehler
- Proposed Law Matt Mihaly
- Proposed Law Koster, Raph
- Proposed Law Matt Mihaly
- Proposed Law John Buehler
- Proposed Law Koster, Raph
- Proposed Law Ola Fosheim Grøstad
- Proposed Law Jon Lambert
- Proposed Law Paul Schwanz
- Proposed Law Matt Mihaly
- Proposed Law Paul Schwanz
- Proposed Law Paul Schwanz
- Proposed Law Madman Across the Water
- Proposed Law Travis Nixon
- Proposed Law Mark Eaton
- Proposed Law Sami Kosonen
- Proposed Law Madman Across the Water
- Proposed Law Andrew Hefford {Coregen}
- Proposed Law Dan Burke
- Proposed Law Matt Mihaly
- Proposed Law John Buehler
- Proposed Law Matt Mihaly
- Proposed Law Paul Schwanz
- Proposed Law Ian Collyer
- Proposed Law Matthew Estes
- Proposed Law Matt Mihaly
- Proposed Law Ola Fosheim Grøstad
- Proposed Law John Buehler
- Proposed Law Ola Fosheim Grøstad
- Proposed Law John Buehler
- Proposed Law Adam Martin
- Proposed Law Matt Mihaly
- Proposed Law Adam Martin
- Proposed Law Matt Mihaly
- Proposed Law Paul Schwanz
- Quality Testing Michael Tresca
- Quality Testing John Buehler
- Quality Testing Michael Tresca
- Quality Testing Dave Rickey
- Quality Testing Nathan F. Yospe
- Quality Testing Michael Tresca
- Quality Testing Koster, Raph
- Quality Testing Dave Rickey
- Quality Testing Dave Rickey
- Quality Testing Derek Licciardi
- Quality Testing Dave Rickey
- Quality Testing Michael Tresca
- Quality Testing Dave Rickey
- Quality Testing Jeff Cole
- Quality Testing Robin Lee Powell
- Quality Testing Daniel.Harman@barclayscapital.com
- Quality Testing J C Lawrence
- Quality Testing Daniel.Harman@barclayscapital.com
- Quality Testing Dave Rickey
- Quality Testing Daniel.Harman@barclayscapital.com
- Quality Testing Michael Tresca
- Quality Testing Daniel.Harman@barclayscapital.com
- Quality Testing Paul Dahlke
- Quality Testing Dave Rickey
- Players Controlling Monsters rayzam
- High Level Architecture Adam Martin
- Networking architecture overview Brian Hook
So I finally called up a friend of mine (John Carmack) that really,
really understands real-time networking and asked him to core dump on me
how he has implemented his networking. The answer is not what I
expected, but it's a damn elegant solution.
His original implementation of networking, back in 1995 (for QuakeTest),
used TCP. This was actually fine for LAN play, because the largish
packets (8K) wouldn't fragment on a LAN, but would fragment on the net.
His next iteration involved using UDP with multipled reliable and
unreliable data, pretty much what we've discussed on here. Different
messages had different requirements, and the network layer would manage
this. However there were always difficult to find bugs that would crop
up as a result of mixing reliable and unreliable data, e.g. guaranteed
messages that referenced entities that were altered through unreliable
messages.
The final iteration (Quake3), where he feels he pretty much "got it
right", uses a radically different approach. There are no reliable
packets of any kind. In fact, there is only a single packet type -- the
client's necessary game state. The server sends sequenced game state
updates that are delta compressed from the last acknowledged game state
the client received. This "just works". Dropped packets are handled
very gracefully, and specific commands are never acknowledged, just last
known game states. Obviously the client is sending traffic back to the
server ACKing the last game state received.
The client's receive logic is basically:
if ( newState.sequence < lastState.sequence )
{
//discard
}
else if ( newState.sequence > lastState.sequence )
{
lastState = deltaUncompress( lastState, newState );
ackServer( lastState.sequence );
}
The client then extrapolates movement and whatever other information it
needs based on the last game state it received.
On the server side, it's simple as well:
deltaCompressState( client.lastAckState, newState, &compressedState );
sendToClient( client, compressedState );
So the server never sits around waiting for an acknowledgement. As a
result, latencies are much lower than if you have code that sits there
twiddling its thumbs waiting for a synchronous ACK.
There are two downsides to this implementation. The big one is that it
soaks more bandwidth, because the server is constantly pumping new state
to the client instead of just sending new state when it doesn't get an
ACK. Also, the amount of data it's sending grows with the number of
dropped packets since the delta grows as a result.
The other downside is that the server has to do a lot of buffering,
specifically of the last acked state to the client (so it can delta
compress) along with a list of all the previous states it has sent to
the client (back to the last acked one). This is necessary so it can
rebase its delta comparisons on any of the game states that the client
has acked.
For example, let's say the client last ACKed sequence 14. The server is
sending out new game states with incrementing sequences. It may be up
to sequence 20, when it gets an ack from the client that it received
sequence 17. The server has to have the state that was sent as part of
sequence 17 in order to rebase the delta compression, so if game states
are large enough or the buffers are long enough, this can grow fairly
high (to the tune of several hundred K per client).
Addressing a question from someone else about "are there advantages to
using multiple ports?". There is one significant advantage that I don't
think was mentioned, and that's that the OS buffers incoming data _per
port_. So if you have a chance of a port buffer overflow, then multiple
ports may not be a bad idea.
Speaking of port buffer overflows, John doesn't think this is a problem.
People that spin a second thread just to block on incoming ports are
probably just doing extra work that doesn't need to be done.
Effectively a thread that pumps the data ports is duplicating the exact
same work the network stack is doing in the OS. Instead, John just
pumps the network stack at the top of the event loop. Goes to show that
brute force sometimes "just works" =) On a listen server (i.e. you're
hosting a server on your client), where frame times can be several dozen
milliseconds, there is a chance that you'll get a buffer overrun. In
that case there are some options in Q3 to minimize buffer sizes, etc. to
reduce the likelihood of a buffer overrun.
One nice thing about his networking architecture, however, is that in
the case of a buffer overrun -- it just keeps working. There is NO
difference to his client and server between a dropped packet and a
buffer overrun; as a matter of fact, this may actually be masking some
real buffer overruns, but so far he's pretty sure that he's not even
come close to hitting an overrun situation. Of course, the dynamics of
an FPS are different than those of an MMOG (fewer clients, much higher
bandwidth per client), but it's interesting nonetheless.
One interesting note on NAT: apparently some routers will randomly
switch the client's port when behind a NAT. This is very rare, but
causes lost connections "randomly" for many users. It took forever to
track this down, but once it was discovered he solved it by having a
client randomly generate a unique client-id (16-bits) at connection time
that is appended to every incoming packet. That way multiple clients
with the same IP can work just fine, even if their ports get re-assigned
mid-session. Humorously enough, he never bothered handling the (so rare
as to be insignificant) case where two clients behind the same firewall
randomly generate the exact same ID.
Aside from application level delta compression, Q3 also does per-packet
Huffman compression. Works great, simple to implement, and the upside
to something more aggressive is very low.
He has done some half-hearted work on encryption, but basically
app/stream-level encryption is pointless because of the sophistication
of hackers. In the future he'll probably rely on higher level stuff (a
la Punkbusters for CounterStrike) instead of cute bit-twiddling.
Finally, I asked about packet size. He thinks the notion of a 512-byte
optimal MTU is pretty much at least 5 years out of date. He sees almost
no problems with a max packet size of 1400 bytes, and fragmentation just
isn't an issue. During the course of typical activity, the actual
payload size is often smaller than the UDP header size (!), and even
during hectic activity the packet size is on the order of several
hundred bytes. The large packets (up to 1.4K) are typically when a
large amount of game state must be sent at once, specifically at
connection time when there is no state to delta against and when there
is a lot of startup initialization going on.
So this architecture basically obviates the need to even have a
discussion about UDP vs. TCP and unreliable vs. reliable and
out-of-order vs. in-order. It's all unreliable UDP delta compressed
against the last known state.
Damn that's smooth.
Brian - Networking architecture overview Dave Rickey
- Networking architecture overview Brian Hook
- Networking architecture overview Amanda Walker
- Networking architecture overview Brian Hook
- Networking architecture overview Bobby Martin
- Networking architecture overview Daniel.Harman@barclayscapital.com
- Connection Stats Ben Tolputt
- MUD-Dev digest, Vol 1 #443 - 12 msgs Dr. Cat
- Fourteen forms of fun Ola Fosheim Grøstad
- Fourteen forms of fun rayzam
- Fourteen forms of fun Sasha Hart
- Fourteen forms of fun Jon Lambert
- Fourteen forms of fun David H. Loeser Jr.
- Fourteen forms of fun Matt Mihaly
- Fourteen forms of fun Ola Fosheim Grøstad
- Incorporating Plot/Backstory/Scenario Design Tools Nathan F. Yospe
- Extreme Programing Ling Lo
- DAoC dev team Lars Duening
- Documentation Adam Martin
- Documentation Brian Hook
- English grammar thoughts Par Winzell
- English grammar thoughts Kylotan
- English grammar thoughts Travis Casey
- English grammar thoughts Jasper McChesney
- English grammar thoughts Marian Griffith
- English grammar thoughts Travis Casey
- English grammar thoughts Jasper McChesney
- English grammar thoughts bruce@puremagic.com
- English grammar thoughts Marian Griffith
- English grammar thoughts Travis Casey
- English grammar thoughts Robert Zubek
- English grammar thoughts Robert Zubek
- English grammar thoughts Travis Casey
- English grammar thoughts Chris Gray
- English grammar thoughts Jon Leonard
- ADMIN: The code documenting/commenting thread J C Lawrence
- Players Controlling Monsters David H. Loeser Jr.
- Players Controlling Monsters Brian Hook
- Players Controlling Monsters John Buehler
- Expectations of in-game reality Matt Mihaly
- Expectations of in-game reality Freeman, Jeff
- Expectations of in-game reality J C Lawrence
- Expectations of in-game reality Freeman, Jeff
- Expectations of in-game reality Travis Casey
- Expectations of in-game reality Lars Duening
- Expectations of in-game reality Marian Griffith
- Expectations of in-game reality Derek Licciardi
- Expectations of in-game reality Lars Duening
- Expectations of in-game reality Paul Schwanz
- Expectations of in-game reality Nip
- Expectations of in-game reality Ian Collyer
- Expectations of in-game reality Adam Martin
- Expectations of in-game reality Michael Tresca
- Expectations of in-game reality J C Lawrence
- Expectations of in-game reality Matt Mihaly
- Expectations of in-game reality Daniel.Harman@barclayscapital.com
- Expectations of in-game reality Eli Stevens
- Expectations of in-game reality Marian Griffith
- Expectations of in-game reality Travis Casey
- Expectations of in-game reality Sami Kosonen
- Respecting NPCs Lee Sheldon
- Respecting NPCs J C Lawrence
- Respecting NPCs Lee Sheldon
- Respecting NPCs J C Lawrence
- Respecting NPCs Sami Kosonen
- Respecting NPCs Travis Nixon
- Respecting NPCs Matthew Estes
- Respecting NPCs Chris Gray
- Respecting NPCs Michael Tresca
- Respecting NPCs Freeman, Jeff
- Respecting NPCs Michael Tresca
- Respecting NPCs Freeman, Jeff
- Respecting NPCs Travis Nixon
- Respecting NPCs Michael Tresca
- Respecting NPCs Adam Martin
- Respecting NPCs Michael Tresca
- Respecting NPCs Daniel.Harman@barclayscapital.com
- Respecting NPCs rayzam
- Respecting NPCs Joe Andrieu
- Respecting NPCs Bruce Mitchener
- Respecting NPCs Joe Andrieu
- Respecting NPCs Michael Tresca
- Respecting NPCs Adam Martin
- Respecting NPCs Lee Sheldon
- Respecting NPCs T.A.J.BARTON
- Respecting NPCs Bruce Mitchener
- Respecting NPCs Adam Martin
- Respecting NPCs Madman Across the Water
- Respecting NPCs Travis Nixon
- Respecting NPCs J C Lawrence
- Respecting NPCs John Buehler
- Respecting NPCs lazarus@ourplace.org
- Respecting NPCs Colin Coghill
- Respecting NPCs gamaiun@yahoo.com
- Respecting NPCs J C Lawrence
- Respecting NPCs Phillip Lenhardt
- Respecting NPCs gamaiun@yahoo.com
- Respecting NPCs Ola Fosheim Grøstad
- Respecting NPCs J C Lawrence
- Respecting NPCs Ola Fosheim Grøstad
- Respecting NPCs Bruce Mitchener
- Respecting NPCs Norman Nunley, Jr.
- Respecting NPCs J C Lawrence
- Respecting NPCs Brian Hook
- Respecting NPCs J C Lawrence
- Respecting NPCs gamaiun@yahoo.com
- Respecting NPCs Ola Fosheim Grøstad
- Respecting NPCs Matthew D. Fuller
- Respecting NPCs Timothy Dang
- Respecting NPCs gamaiun@yahoo.com
- TECH : RMI (was UDP Revisted) Daniel.Harman@barclayscapital.com
- TECH : RMI (was UDP Revisted) Bobby Martin
- Chatbots Adam Martin
- TECH: UDP Revisted Bobby Martin
- The function of NPCs in novels versus MUDs Ola Fosheim Grøstad
- RE: Koster, Raph
- RE: Joe Andrieu
- RE: Marian Griffith
- RE: gamaiun@yahoo.com
- RE: Daniel.Harman@barclayscapital.com
- Violence Matt Mihaly
- Quality Testing (and community) Ola Fosheim Grøstad
- ADMIN: Recent outages J C Lawrence
- [ECOSYSTEMS] Fishing in the real world Adam Martin
- [ECOSYSTEMS] Fishing in the real world Daniel.Harman@barclayscapital.com
- [ECOSYSTEMS] Fishing in the real world Hans-Henrik Staerfeldt
- [ECOSYSTEMS] Fishing in the real world Ian Collyer
- [ECOSYSTEMS] Fishing in the real world Dave Rickey
- Statistics Ben Chambers
- Statistics Eli Stevens
- Statistics Adam Martin
- Statistics Hans-Henrik Staerfeldt
- Statistics John Buehler
- Statistics Ben Chambers
- Statistics Ben Chambers
- Statistics Travis Casey