Jump to content

  • Log In with Google      Sign In   
  • Create Account


How to get ping times for large server lists


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
15 replies to this topic

#1 The ZMan   Members   -  Reputation: 702

Like
0Likes
Like

Posted 26 September 2012 - 10:06 AM

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 :-)
ZMan

Sponsor:

#2 hplus0603   Moderators   -  Reputation: 4960

Like
2Likes
Like

Posted 26 September 2012 - 12:08 PM

I cant find any conclusive docs on how this is done


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.

enum Bool { True, False, FileNotFound };

#3 Khatharr   Crossbones+   -  Reputation: 2818

Like
1Likes
Like

Posted 26 September 2012 - 12:09 PM

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.

Edited by Khatharr, 26 September 2012 - 12:18 PM.

void hurrrrrrrr() {__asm sub [ebp+4],5;}

There are ten kinds of people in this world: those who understand binary and those who don't.

#4 The ZMan   Members   -  Reputation: 702

Like
0Likes
Like

Posted 26 September 2012 - 12:32 PM

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.
ZMan

#5 The ZMan   Members   -  Reputation: 702

Like
0Likes
Like

Posted 26 September 2012 - 12:43 PM

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.
ZMan

#6 Khatharr   Crossbones+   -  Reputation: 2818

Like
1Likes
Like

Posted 26 September 2012 - 01:23 PM

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.

Edited by Khatharr, 26 September 2012 - 01:33 PM.

void hurrrrrrrr() {__asm sub [ebp+4],5;}

There are ten kinds of people in this world: those who understand binary and those who don't.

#7 The ZMan   Members   -  Reputation: 702

Like
0Likes
Like

Posted 26 September 2012 - 01:46 PM

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.
ZMan

#8 hplus0603   Moderators   -  Reputation: 4960

Like
2Likes
Like

Posted 26 September 2012 - 03:29 PM

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")

Edited by hplus0603, 26 September 2012 - 03:29 PM.

enum Bool { True, False, FileNotFound };

#9 The ZMan   Members   -  Reputation: 702

Like
0Likes
Like

Posted 26 September 2012 - 04:35 PM

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.
ZMan

#10 Khatharr   Crossbones+   -  Reputation: 2818

Like
1Likes
Like

Posted 26 September 2012 - 06:49 PM

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! :)
void hurrrrrrrr() {__asm sub [ebp+4],5;}

There are ten kinds of people in this world: those who understand binary and those who don't.

#11 0BZEN   Crossbones+   -  Reputation: 2004

Like
1Likes
Like

Posted 27 September 2012 - 04:08 PM

Typically, from what I've seen on console games, it's done brute force. The client sends a ping request to a bunch of servers returned by the matchmaking server.

This involves resolving addresses first, then sending ping packets to the resolved address, waiting for a reply. Often, there are several ping requests sent for latency measurement (and sometimes also to get some information about the game on the server), and then averaged.

On the game hosting side, there is a bandwidth cap you can set for QOS to avoid flooding the upstream bandwidth. If you have too many clients querying the same servers, these ping requests will be dropped at the server end, the gamer will be seen as 'unavailable' to some clients. That could be at the address resolver level, which should be more lightweight that letting the clients flood the game host with QOS requests. Typically, QoS negotiation can take a few seconds.

Also, you can have the game host notify the matchmaking server when their QOS bandwidth load changes significantly (10%, 50%, 90%, ...), then the matchmaking server can lower the priority of that game host if it is overloaded with queries. And of course, you do not advertise full servers, so these that would need to maximise their upstream bandwidth will never get pinged.

You can of course limit the number of concurrent qos requests on the game host side. You don't really want to run 1,000 simulatenous requests (typically, around 20), so you need to stagger them appropriately.

Edited by papalazaru, 27 September 2012 - 04:14 PM.

Everything is better with Metal.


#12 The ZMan   Members   -  Reputation: 702

Like
0Likes
Like

Posted 28 September 2012 - 11:39 AM

Thanks - more great idea for me to think about... amazing how things you didn't think were complex turn out to be quite the opposite eh?

I had thought about hiding full servers but right now we don't have a lot of servers so we want the illusion of as many players as possible.. but we can certainly not ping the full ones.

Edited by thezbuffer, 28 September 2012 - 11:41 AM.

ZMan

#13 0BZEN   Crossbones+   -  Reputation: 2004

Like
1Likes
Like

Posted 28 September 2012 - 07:42 PM

Just a note, a very crude and simple way to cap bandwidth is to use a bucket monitoring your packet being sent, and payback some of the bandwidth every once in a while. It's lightweight, and reasonably accurate.

namespace utils
{
static double current_time()
{
  LARGE_INTEGER frec;
  LARGE_INTEGER ticks;
  if( !QueryPerformanceFrequency(&frec) ||
   !QueryPerformanceCounter(&ticks))
   return 0.0;
  return (double)(ticks.QuadPart / frec.QuadPart);
}
};
class BandwidthThrottler
{
public:
BandwidthThrottler(size_t bits_alloc)
: m_bits_alloc(bits_alloc)
, m_bits_avail(bits_alloc)
, m_timestamp(utils::current_time())
{}
//------------------------------------------------------
// update once in a while
//------------------------------------------------------	
void update()
{
  // check time since last update.
  double  time_now  = utils::current_time();   // time now, taken from high performance counter.
  double  time_elapsed = time_now - m_timestamp;   // time since last update.
  time_elapsed   = max(min(time_elapsed, 1.0), 0.0); // clamp in the range [0.0, 1.0] in seconds.
  m_timestamp	= time_now;	   // timestamp that update.
		
// calculate bit rate available, after paying back a bit of bandwidth.
  size_t  bits_payback = (size_t)((double)m_bits_alloc * (time_elapsed / 1.0)); // how much bandwidth we have to pay back since last update,
					  // given the maximum number of bits we can send over 1.0 seconds.
  m_bits_avail = min(m_bits_avail + bits_payback, m_bits_alloc);	 // how much bandwidth we will have available.
}
//------------------------------------------------------
// a packet has been sent, so consume a bit of bandwidth
// so the packet size, plus the size of a UDP header in bits.
// limit to zero if we consume more than we have available.
//------------------------------------------------------
void consume_bits(size_t bits)
{
  m_bits_avail -= min(m_bits_avail, bits);
}

size_t get_bits_available() const { return m_bits_avail; }
size_t get_bits_allocated() const { return m_bits_alloc; }
void set_bits_allocated(size_t bits_alloc) { m_bits_alloc = bits_alloc; }
private:	
size_t m_bits_avail; // the bitrate cap we want to use.
size_t m_bits_alloc; // the number of bits available for transmission.
double m_timestamp; // the timestamp of the last update.
};

Edited by papalazaru, 28 September 2012 - 07:48 PM.

Everything is better with Metal.


#14 Scorpie   Members   -  Reputation: 173

Like
1Likes
Like

Posted 03 October 2012 - 03:30 PM

Here is an idea i came up with while reading this topic, it's a variant on the geocoding i guess:

How about dividing servers into groups depeding on the ping time between them?
When a new server connects to the lobby to identify itself, it will receive a list of the other servers and ping them (or just two or three per existing group). The result is then returned to the lobby server which assigns this server to a group. If a group exceeds a certain size, for example 30, split them into two new groups using for example the two servers which have the longest ping between them and then divide the rest equally and depending on the ping time to these two "outer" servers.
You can assing a "master / reference" server per group, the one with smallest sum of pings to others in group which can be pinged by a user. If the ping is ok, the user is presented with all servers in the group and can ping these assuming decent ping times.

There are still a few things that need thought, among which:
- Depending on server lifespan this might not give good performance.
- Ping time between servers needs to be updated periodically because it may change depending on the network / internet structure which might cause frequent rearanging of groups (however i think this won't be that bad, else normally you would have varying ping times all the time)
- Merging of groups when they become small

Ok please note, i have no practical experience in this field, this is just a random thought that popped up in my head so it might be either a bad idea, a lot of overhead or contain some assumptions which make this idea just not work but i figured i'd share and see what you guys think.

I hope at least the idea is clear, i don't really feel like writing a two page essay atm but wanted to share it nonetheless, might expand on this later :)

#15 The ZMan   Members   -  Reputation: 702

Like
0Likes
Like

Posted 11 October 2012 - 11:28 AM

@Scorpie - I like that idea and yes you explained it just fine...
ZMan

#16 samoth   Crossbones+   -  Reputation: 4505

Like
0Likes
Like

Posted 11 October 2012 - 02:12 PM

Three servers in sufficiently different networks (different geographic regions) will let you locate both a server and a connecting client on the globe via barycentric coordinates (the ping time being the "coordinate" here). It won't be perfect, because routers and networks are not perfect, but it will be a good measure. It will work with every server requiring 3 pings (regularly) and every client requiring only 3 pings.

A client and a server with similar barycentric coordinates will have a short ping between each other. You could subtract them from each other to get a bogus ping.

To make the ping even more bogus (but more valuable!) add 1 ms for every, say, 20 people currently playing on the server. Since players will choose the server with the lowest ping, this will automatically load-balance them among servers with similar ping.




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS