Subject: Re: [Sweng-Gamedev] Breaking matchmaking deadlocks
If your join requests have timestamps, you can reject a join request
from A if you have already requested to join A's game and the time your
request was sent was before A sent his. In the remote possibility that
two requests are sent at *exactly* the same time you reject as well and
let each client retry. Eventually one will succeed and the other will
fail.
Blair Holloway wrote:
> 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
> <
bored_and_dangerous2003 <at> yahoo.com
> <mailto:
bored_and_dangerous2003 <at> yahoo.com>> 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 <
thynameisblair <at> chaosandcode.com
> <mailto:
thynameisblair <at> chaosandcode.com>>
> *To:*
sweng-gamedev <at> midnightryder.com
> <mailto:
sweng-gamedev <at> midnightryder.com>
> *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
>
Sweng-Gamedev <at> lists.midnightryder.com
> <mailto:
Sweng-Gamedev <at> lists.midnightryder.com>
>
>
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryde
>
r.com
>
>
>
> ----------------------------------------------------------------------
> --
>
> _______________________________________________
> Sweng-Gamedev mailing list
Sweng-Gamedev <at> lists.midnightryder.com
>
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.
com
_______________________________________________
Sweng-Gamedev mailing list
Sweng-Gamedev <at> lists.midnightryder.comhttp://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.
com
_______________________________________________
Sweng-Gamedev mailing list
Sweng-Gamedev <at> lists.midnightryder.comhttp://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com
RSS Feed