Re: Breaking matchmaking deadlocks

When I see this kind of chicken/egg problem I usually first think of priority sorting:

Assign a unique ID to each machine (GUID, XUID, whatever), and make sure it is communicated both ways when connecting. Each machine, if it detects it has duplicate connections to some other machine, drops that connection from the pair where the server side of the connection has lower UID than the client side.

In your case, A=123, B=456. At moment * there are 2 connections:

c1: A=server, B=client

c2: B=server, A=client

Since 123<456, both machines simultaneously drop c1. Et voilà.

Does the explanation make sense? I haven't actually used this in practice for this particular use case, but it works fine for some other single-machine problems of similar nature.

HTH,

Alen

Blair wrote at 7/8/2010:

>

For sure, rejecting a duplicate connection like this will work in cases where the connection is fully established. However, I'm not sure that it works if both machines join each other's games simultaneously. Let me demonstrate with ASCII!

(If the formatting is stuffed, try pastebin: http://pastebin.com/U1YP7Ain )

A -----a---c---*

\ / \ /

X X

/ \ / \

B -----b---d---*

A = machine A's timeline

B = machine B's timeline

a = machine A sends request to join machine B's game

b = machine B sends request to join machine A's game

c = machine A receives request to join from machine B, accepts, sends back response

d = machine B receives request to join from machine A, accepts, sends back response

* = both machines suddenly realise that they are connected to each other's games

Because each machine is responding to each other's join requests in their "cone of silence" -- the time between their request to join a game and receiving the result -- they can't know to turn the other machine's request away; therefore, they end up becoming doubly connected to one another.

- Blair

On Thu, Jul 8, 2010 at 3:14 PM, Conor Stokes <[email protected] > wrote:

Maintain a shared set of connections (in a hash or something) for both in-coming and out-going (hunting and gathering), protected by a lock and keyed by user. Then don't allow inserts/drop the connection into the shared set if you find a connection already there. It's a small relatively constant time operation and you should be able to set it up for the right order of operations such that you won't end up with an inconsistent set between players.

Cheers,

Conor

----------

From: Blair Holloway <[email protected] >

To: [email protected]

Sent: Thu, 8 July, 2010 10:50:25 AM

Subject: [Sweng-Gamedev] Breaking matchmaking deadlocks

Rather than taking the typical "join session/host session" approach with our upcoming title, we're going to adopt a matchmaking solution - the user selects the "find players" option, and under the covers the game deals with creating and joining as necessary.

We've been examining the matchmaking system described in "E Pluribus Unum: Matchmaking in HALO 3"[1], and decided to take a similar approach -- when matchmaking begins, a "gatherer" task hosts a session, and waits for players to connect to it, whilst a "hunter" task enumerates a list of sessions and tries to join each in turn.

Since these tasks happen simultaneously, it's possible to end up in a quasi-deadlock -- the hunter task from machine A can connect to the gatherer's session on machine B, whilst machine B's hunter simultaneously connects to machine A's gatherer; both machines would be simultaneously hosting two sessions, and each machine would be participating in both.

The easiest solution to this is perhaps to avoid the "deadlock" in the first place, and not simultaneously search and host. Indeed, the system described in Halo 3 seems to randomly decide at the start of matchmaking whether a machine is a hunter or a gatherer, and simply sticks to that choice until a timeout occur.

However, Halo has the advantage of a huge player base to make this work; we're expecting a few orders-of-magnitude less players, and are worried that when, say only a few tens of people are online at any given time, only gathering or hunting will make the matchmaking experience slow for the user. Therefore, we'd like to both gather and hunt at the same time, and try to avoid the deadlocks and "break" them when they occur -- i.e. when detecting simultaneous connections, choose one session to destroy, whilst keeping the other.

Does anyone have any suggestions for how to break these "deadlocks"?

Cheers,

- Blair

[1] http://www.bungie.net/images/Inside/publications/presentations/gdc2008_butcher_chris_matchmaking.ppt

_______________________________________________

Sweng-Gamedev mailing list

[email protected]

http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com

--

Alen

_______________________________________________
Sweng-Gamedev mailing list
[email protected]
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com