Re: Breaking matchmaking deadlocks

Here are some slides and demo on games networking from GDC10
in which it covers the topic of tie-breaking in situations similiar to this.

Might be of some help...

http://gafferongames.com/

.rex


On Thu, Jul 8, 2010 at 4:19 PM, Alen Ladavac <[email protected]> wrote:

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

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