Re: Breaking matchmaking deadlocks

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

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