The change log for recent QStat releases have alluded to email I've sent to id about the Q3 master server. A couple people have asked about the content of the messages, so here they are for all to enjoy. (assuming you enjoy such things)The email is very technical. If you're not into programming, it will probably be meaningless. If you're not into low-level programming it may be difficult to understand.
For those who don't care about the details, the summary is that the Q3 master server and protocol need serious improvement. The design of the current protocol is severely limiting Internet player's successful use of the id Q3 master server list.
I'd be happy to discuss these issues with anyone. I don't know if id is listening, but I could collect suggestions, edit, and forward to id. steve@activesw.com
From steve Mon May 3 15:27:30 1999 To: zaphod@idsoftware.com, zoid@idsoftware.com Subject: Q3 Master server protocol Content-Length: 4037 Hello, Graeme, saw your note requesting ideas about the master server protocol for Q3. I'm the author of QStat, so I've seen lots of game protocols, and network programming has been part of my job for many years. Here's my two-bits ... Your criteria seemed to be packet size and "detail". I assume detail means more information about servers. Let's look at detail first, then see how we can compress it. The information players like to see are: IP address, port#, current # players, ping, is it full?, mods (eg. ctf), server name A master server can't provide meaningful ping measures, and the server name would be too much info. So that leaves us: IP address, port#, current # players, is it full?, mods (eg. ctf) Quite a bit can be done with the IP address. The high order octet is the same for alot of servers. This is caused by the nature of subnetting and the practice of running multiple servers on one machine. Both can lead to optimizations. Consider representing the high order octet as a count and an octet value. The following count servers would be represented as three octets instead of four. You could do the same thing for the second octet, but there is very little to be gained there. For multiple servers on one IP, consider listing the IP only once. Doing this without wasting space on the single server/IP case is tricky. The simplest is to embed a flag in one of the server info values. The flag would indicate whether the following bytes in the packet was info about a server on the same IP. It's tempting to try optimizing the port number. Currently, 1,618 of the 2,669 servers listed with the id Q2 master are using the default port. That's 3,236 bytes of duplicate info. Again, this is a place where a flag would be handy. Oh, and you should include the default port in the beginning of the master packet. Makes the master portable to your licencees. Representing players is pretty easy; one byte for current # of players. I don't think most people care much about max players when selecting a game server, so that could be left out if desired. In either case, if you are willing to restrict game status from the master to 127 players, then you can gain one or two bytes for flags. The mod info can be done in a single byte if you provide a map in the packet to translate the mod numbers into string names. The number to mod name map would likely change dynamically, so browser authors would have to always map using the latest info. The same technique could be use for the map name. But, personally, I can't translate a map name (eg. q2dm1) into, "The one with lots of lava and teleporters". So, the map isn't that useful to me. Ok, let's see how we might apply these techniques. The server list might look like this: # count; number of servers using following high octet # high octet ### lower octets of first server # current players [0-127], default port [128] # max players [0-127], next server on same IP [128] # mod [0-255] If "default port" is _not_ set, then the next two bytes are the server's port number. ## port number If "next server on same IP" is set, then the next 3 or 5 bytes are "current players", "max players", "mod", and maybe "port number". If "next server on same IP" is not set, then the another IP is started with another "lower octets". If the count of servers using the octet has been exhausted, then the next thing is another "count" and "high octet". I think you can imagine how to pack the mod name map. (if you want to get really crazy, you can steal a bit from "mod" and use it indicate just one byte to represent the port. This would be a signed byte that would be an offset from the default port) That's about it. You'll gain enormous savings from optimizing the default port and the high order octet. In the id Q2 master list, there are just 66 unique high order bytes for 2600+ servers. And you get to include a little detail to provide the impatient gamer with some quick info for decision making. Cheers! Steve |
From steve Wed May 12 16:44:30 1999
To: q3feedback@idsoftware.com, zoid@idsoftware.com
Subject: Q3 master server problems [ANALYSIS & SUGGESTIONS]
Content-Length: 4378
Hi, I'm the author of QStat and have been working on support for
the Q3 servers and master. In particular I noticed that the id
server list page included many more servers than I was getting
with QStat. Upon investigation, I discovered that the master was
returning multiple packets instead of just the one that I was
expecting.
Ok, that's fine. I fixed QStat to expect multiple packets, but
there's serious problems with this approach and with the Q3 master
server in general.
1. The master response is much too verbose. It's currently hovering
around 20k. I sent some suggestions for optimizing the packet
size. I hope you implement some kind of improvement because the
current design won't scale. The current 20K packet only nets
about 740 servers.
2. The master's max UDP size is 8000 bytes. This arrives at my
machine as six packets; a UDP packet with LEN=8030 and then five
UDP continuation packets. To send 20K, the master sends two 8000
byte UDP packets and one 4100 byte UDP packet. These get split
into a total of 14-15 packets. That's all the back-ground. The
problem is that a dropped UDP continuation nullifies the entire
UDP packet; all 8000 (or 4100) bytes are lost. This is because
the OS will not pass incomplete UDP packets to the application.
3. There is no way to determine if I've received all the packets.
The packets are not distinguished in any way. There's no way to
tell if I've received all the UDP packets or should wait for more.
There's no way to tell if UDP packets arrive out of order.
4. The "EOT" packet you're sending is useless. Sometimes it does
not arrive at all. Often it arrives in the middle of the UDP
continuations for the second or third UDP packets. If I stopped
when I saw "EOT", then I'd missed more than half of the servers.
5. Server response time is often very long. This is probably a
problem with the network rather than the server software.
6. Finally, and WORST OF ALL; items 1-5 add up to a very unreliable
master server. It's so bad I'd venture to guess that half of the
data sent out by the master goes in the bit bucket because;
- UDP continuation loss nullified entire 8000 byte packet
- user got tired of waiting and hit [Cancel] [Update] thus
ignoring any much delayed packets from the previous update.
Just to illustrate my points, here's some typical output from my
network snoop:
broccoli -> monster.idsoftware.com UDP D=27950 S=60065 LEN=24
monster.idsoftware.com -> broccoli UDP D=60065 S=27950 LEN=8009
monster.idsoftware.com -> broccoli UDP continuation ID=63007
monster.idsoftware.com -> broccoli UDP continuation ID=63007
monster.idsoftware.com -> broccoli UDP continuation ID=63007
monster.idsoftware.com -> broccoli UDP continuation ID=63007
monster.idsoftware.com -> broccoli UDP continuation ID=63007
monster.idsoftware.com -> broccoli UDP D=60065 S=27950 LEN=8014
monster.idsoftware.com -> broccoli UDP continuation ID=63008
monster.idsoftware.com -> broccoli UDP D=60065 S=27950 LEN=11
monster.idsoftware.com -> broccoli UDP continuation ID=63008
monster.idsoftware.com -> broccoli UDP continuation ID=63008
monster.idsoftware.com -> broccoli UDP continuation ID=63008
monster.idsoftware.com -> broccoli UDP continuation ID=63008
monster.idsoftware.com -> broccoli UDP D=60065 S=27950 LEN=4137
monster.idsoftware.com -> broccoli UDP continuation ID=63009
monster.idsoftware.com -> broccoli UDP continuation ID=63009
The "LEN=11" packet is the "EOT". It arrived before the second UDP
packet was complete. In this example, I actually received all the
packets. But sometimes I get just 5 out of the 15 and sometimes
the UDP continuations are all out of order, or get delayed many
seconds.
Suggestions
-----------
1. Drop the master's max packet size to 1K. On most any network this will
not cause packet fragmentation.
2. Number the packets with a sequence number, _and_ mark the last packet
in the sequence.
3. Reduce the overall data size by using an application specific
packet optimizer.
Implementing #1 and #2 on the existing data format would be a great
improvement. But you'll need to make the leap to #3 if you want to
scale to thousands of servers.
Steve
http://www.qstat.org
|