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.
How to get ping times for large server lists
Author
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.
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.
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.
};
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
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
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement