Any idea how the ping times are calculated for online games in the game server list.

We have a master server that keeps a list of the current games. When a client goes to the lobby we send them the list of game servers. We thought we could do some fancy math on ping times between the master server and the game server but that doesn't work of course.

So we have come to the conclusion that each client must iterate the servers in the list and 'ping' each one. But we see online games with hundreds or thousands of game servers and we know some games have 10s of thousands of people in the lobby so it seems like a lot of traffic with everyone pinging every game server and every game server having to respond to every ping request.

If we do send a ping packet to every server then we need to worry about NAT stuff just to get that ping time - usually we don't worry about that until we try to connect.

We wiresharked TF2 and didn't see anything that lead us to believe this is calculated on the clients...

I cant find any conclusive docs on how this is done, though there's lots of speculation by gamers usually about why the game developer gets it wrong :-)

I cant find any conclusive docs on how this is done[/quote]

That's because it's done differently for different games.
You should define what the number is that you actually want to display.
Then you should write code to determine that number.
Then you should display it.

For example, if you want to display the UDP datagram round-trip time to a particular destination, you need to send a UDP datagram to that server, and then measure how long it takes before an answer comes back.
For servers behind NAT (that's most user-hosted servers these days) you will also need to set up NAT punch-through introduction before you can send that datagram.

Possibly the pings listed for servers by games such as TF2 are ping times from the server in question to what you describe as a 'master server'.

If it were just an issue of a huge unsorted list then you could just ping the server as it's scrolled into the list, but since ping time is something you'd want to sort by that wouldn't really work if you're pinging from the client machine for the reason you mentioned.

A hybrid approach may be viable. Sort the list tentatively by the ping to the list server (plus the client's ping to the list server, maybe minus a small % if you're off by a lot, depending on how your game's routing works) and then have the client ping the top N servers in the list. Pinging is pretty lightweight, especially if you don't retry, but it's wise to throttle it anyway since a some consumer ISPs will actually halt your service temporarily if they think you may be ICMP flooding.

I'm not really sure what you mean when you say fancy math.

Possibly the pings listed for servers by games such as TF2 are ping times from the server in question to what you describe as a 'master server'.

If it were just an issue of a huge unsorted list then you could just ping the server as it's scrolled into the list, but since ping time is something you'd want to sort by that wouldn't really work if you're pinging from the client machine for the reason you mentioned.

Yes thats our current approach but if Master Server is in the US, game server is in Australia that gives a slow 'ping'. An Australian client joins and avoids the Australian game server even though for him it would be a fast ping. Which is why we feel the right way is a 'ping' per client.

I'm not really sure what you mean when you say fancy math.

Don't ask.. it didn't work :-) We were averaging the 'ping' times from each client that was already connected to the game server and some other magic. The idea was to give a representative quality value. Sometimes it goes negative which is clearly not right.

For example, if you want to display the UDP datagram round-trip time to a particular destination, you need to send a UDP datagram to that server, and then measure how long it takes before an answer comes back.

Yes that would be the perfect measure for us as it represents our game packets. But if that's too expensive an operation then I'm open to other ideas too. I put 'ping' in quotes because I'm really after a best/closest type measurement that allows people to make an educated decision about the server they choose or something to sort the list by.

That's because it's done differently for different games.

I was more worried about the 'communicate with every server on the list from every client' part of the algorithm than what I 'ping' with. I'm not a network programmer (hence asking here) but my gut feeling was that this is not very efficient. My gut could well be wrong here I was just looking for some feedback before we rewrite it all to do it this way. We would add some caching of course so that we don't reping servers we have already talked to in the past couple of days since perf proabbly doesn't change all that much.

Ah, I see the problem.

Well, if fancy is what you're into then you could go as far as having both servers and clients report their region (or use IP-based whois) to the master server and then prefer servers that are in the same region as the client.

That is to say, when the master server pings a game server it holds that ping as a weight, then have a map of regions and how proximate they are to one another. When a player logs in to look at the list use the two weights to identify the servers likely to have the best ping for that player based on proximity and performance and then have the player ping the game servers that look like the best bets.

If this causes too much of a hit to the servers in heavily populated areas or something then you could probably get away with doing something along the lines of what you were saying there - the master would ping the client to estimate their connection speed and then use that to calculate an estimated ping based on the reported pings of other clients in the same region as the interested client. It could get messy, but I don't think there's a silver bullet for this kind of thing. That being said, you'd have to be pretty hugely popular to DDoS a server with one-per-client pings.

I like that - thanks for the idea...

I guess I was hoping for someone who had written something similar to say 'here's what we did'.. I don't enjoy looking in the large iD codebases but I guess I could crack one of those and see. I wonder if there's any other large networked games that have source available.

Note that you only need to communicate with the servers you can see in the list, not with all servers in the list. This means that the GUI and the networking parts need to communicate to give a good experience to users.
Also, you typically want to send a ping packet for latency detection only seldom -- once every 5 seconds, for example. That will generate a lot less traffic than a user actually in a game.

If you're worried about 100,000 users all trying to measure ping to the same top 10 servers, yes, that wouldn't work so well. But neither would the game experience be very good if 100,000 users were all given the same 10 servers to choose from to join -- they'd all be full! (Btw: The "ping" packet could return information like "current map" and "number of playing/free slots")

Seems like a vicious circle there... we want to present the best servers to people, but we don't know the best servers until we've given them the list and got them to ping them. So how to decide which servers to show first and in what order...

I can see how Geocoding the IP would be one good way to segment the servers - and I know on Xbox Live you often get a seemingly random list back.. i wonder how else that selection happens.

(Btw: The "ping" packet could return information like "current map" and "number of playing/free slots")

Our master server already has that information.. the game server messages it every so often to update the status.

Thanks for letting me bounce things off you all... one of the downsides of being small and indie is the lack of people to talk to about stuff.

Seems like a vicious circle there... we want to present the best servers to people, but we don't know the best servers until we've given them the list and got them to ping them. So how to decide which servers to show first and in what order...

You should be able to refine the prediction process until it's highly accurate. It seems like you're really concerned about pings impacting the game servers. This honestly probably won't be a problem unless you ping continually, which really isn't necessary. Sending one (or even three, for an average) pings and then letting that be your value should be enough. You can add a button to request a refresh if you want. If you can't shake the feeling or if there's really a significant problem from it then you can just randomize the predicted list a bit. For instance, the first X servers at the top of the list are ones that you haven't suggested for a while. As long as the clients tell the master server what result they get whenever they ping a game server you should be able to have a pretty accurate dynamic map of what's going on 'out there'.

Thanks for letting me bounce things off you all... one of the downsides of being small and indie is the lack of people to talk to about stuff.

It's fun!