Match making based on proximity measures between devices

• US 7,634,569 B2
• Filed: 04/23/2003
• Issued: 12/15/2009
• Est. Priority Date: 04/23/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Multerer, Boyd C., VanAntwerp, Mark D.
• Primary Examiner(s): Lim; Krisna
• Application Number:
  US10/421,073
• Publication Number:
  US 20040215756A1
• Time in Patent Office: 2,428 Days
• Field of Search: 709/205, 709/227, 709/228, 463/25, 463/29, 463/42
• US Class Current: 709/227
• CPC Class Codes: A63F 13/216 using geographical information, e.g. location of the game device or player using GPS
• CPC Class Codes: A63F 13/23 for interfacing with the game device, e.g. specific interfaces between game controller and console
• CPC Class Codes: A63F 13/335 using Internet
• CPC Class Codes: A63F 13/35 Details of game servers
• CPC Class Codes: A63F 13/358 Adapting the game course according to the network or server load, e.g. for reducing latency due to different connection speeds between clients
• CPC Class Codes: A63F 13/795 for finding other players; for building a team; for providing a buddy list
• CPC Class Codes: A63F 2300/1025 details of the interface with the game device, e.g. USB version detection
• CPC Class Codes: A63F 2300/205 for detecting the geographical location of the game platform
• CPC Class Codes: A63F 2300/407 Data transfer via internet
• CPC Class Codes: A63F 2300/50 characterized by details of game servers
• CPC Class Codes: A63F 2300/534 for network load management, e.g. bandwidth optimization, latency reduction
• CPC Class Codes: A63F 2300/556 Player lists, e.g. online players, buddy list, black list
• CPC Class Codes: A63F 2300/5566 by matching opponents or finding partners to build a team, e.g. by skill level, geographical area, background, play style
• CPC Class Codes: H04L 67/131 Protocols for games, networked simulations or virtual reality
• CPC Class Codes: H04L 67/52 specially adapted for the location of the user terminal
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

In accordance with one aspect of match making based on proximity measures between devices, a record of distances between groups of network addresses is maintained. This record is then used as a basis for selecting an ordering for online game sessions that is to be returned to a computing device requesting information regarding current online game sessions.

Claims

1. A method comprising:

receiving a request, from a computing device, for an identification of one or more online game sessions that satisfy one or more criteria;

identifying a plurality of online game sessions that satisfy the one or more criteria;

determining, for each of the plurality of online game sessions, a distance between the computing device and another computing device that hosts the online game session, the determining comprising;

identifying a first bucket to which the computing device is assigned;

identifying a second bucket to which the other computing device is assigned; and

identifying a distance between the first and second buckets wherein the second bucket is formed by selecting a set of devices belonging to the first bucket and assigning the set of devices of the first bucket to the second bucket when the number of devices, each device having an IP address, assigned to the first bucket exceeds a bucket threshold, the bucket threshold being a predetermined number of IP addresses which can belong to the first bucket;

selecting an order in which the plurality of online game sessions are to be presented at the computing device, wherein the order is based at least in part on the determined distances; and

returning identifiers of the plurality of online game sessions to the computing device for presentation at the computing device in the selected order.

2. A method as recited in claim 1, wherein the determining comprises determining the distance without communicating directly with any of the computing devices, whereby the device is assigned to the nearest bucket as measured geographically when the device is not assigned to or is not within a geographical boundary of a bucket or the another device is assigned to the nearest bucket when the another device is not assigned to or is not within a geographical boundary of a bucket.

3. A method as recited in claim 1, wherein the second bucket is additionally formed by collecting a set of devices not belonging to the first bucket and second bucket.

4. A method as recited in claim 1, wherein approximately one-half of the devices in the first bucket are assigned to the second bucket when the second bucket is formed.

5. A method as recited in claim 1, wherein:

the determining further comprises identifying an Internet provider for the computing device and an Internet provider for the other computing device; and

the selecting further comprises selecting the order based at least in part on whether the Internet provider for the computing device is the same as the Internet provider for the other computing device.

6. A method as recited in claim 1, wherein determining the distance between the computing device and the other computing device comprises accounting for different data transfer rates in different parts of a network via which communication between the computing device and the other computing device occurs, wherein the first bucket belongs to a first layer and the second bucket belongs to a second layer such that a layer is a collection of buckets, and wherein layers are one of the criteria with which to identify online game sessions.

7. A method as recited in claim 6, wherein the network comprises the Internet.

8. A method as recited in claim 1, wherein the computing device comprises a first game console and the other computing device comprises a second game console.

9. A method as recited in claim 1, wherein the method is implemented in a match making system separate from both the computing device and the other computing device.

10. A method as recited in claim 1, wherein the one or more online game sessions comprise short-lived game sessions.

11. A method as recited in claim 1, wherein the one or more online game sessions comprise tournament game sessions.

12. One or more computer readable media having stored thereon a plurality of instructions that, when executed by one or more processors, causes the one or more processors to perform a method, the method comprising:

maintaining a record of spatial distances between groups of network addresses, wherein each spatial distance is measured between a center of each group, wherein the center of each group is an IP population center of each group where the IP population refers to a number of IP addresses, wherein each group belongs to a layer where a layer is a collection of groups of network addresses, and wherein layers are one of a set of criteria with which to identify current online game sessions; and

selecting and ordering a set of current online game sessions, based at least in part on the record, when a computing device requests information regarding current online game sessions.

13. One or more computer readable media as recited in claim 12, wherein the one or more processors are implemented in a match making system separate from the computing device and wherein approximately one-half of the devices in a first group are assigned to a second group when the second group is formed such that the first group is a first geographic region and the second group is a second geographic region.

14. One or more computer readable media as recited in claim 12, wherein the computing device comprises a game console, and wherein a new group of game sessions is formed from other groups of current online game sessions when the number of current online game sessions in any one of the existing groups exceeds a group threshold value.

15. One or more computer readable media as recited in claim 12, wherein the distances between groups of network addresses are based at least in part on different data transfer rates in different parts of a network via which communication between devices assigned the network addresses occurs.

16. One or more computer readable media as recited in claim 12, wherein the distances between groups of network addresses are based at least in part on latitude and longitude values of geographic locations of devices assigned the network addresses.

17. One or more computer readable media as recited in claim 12, wherein the record comprises a table wherein a second group is formed by collecting a set of devices belonging to a first group and assigning the set of devices to the second group when the number of devices, each having an IP address, assigned to the first group exceeds a group threshold, the group threshold being a predetermined number of IP addresses which can belong to a group.

18. One or more computer readable media as recited in claim 12, wherein the method further comprises:

maintaining a record of Internet providers of the network addresses; and

selecting the ordering based at least in part on both the record of distances and the record of Internet providers.

19. One or more computer readable media as recited in claim 12, wherein the current online game sessions comprise one or more of short-lived game sessions and persistent game sessions.

20. A method comprising:

identifying a plurality of online game sessions, wherein one of a plurality of computing devices is part of each of the online game sessions;

determining distances between a game console and each of the plurality of computing devices, the distances being based at least in part on different data transfer rates in different parts of a network via which communication between the game console and the plurality of computing devices occurs, wherein each computing device belongs to one of a plurality of buckets, and wherein each bucket belongs to one of a plurality of layers such that a layer is a collection of buckets; and

determining an ordering for the plurality of online game sessions, wherein the ordering is based at least in part on the distances, wherein the ordering is based at least in part on distances between the plurality of buckets and on distances between the plurality of layers, and wherein the ordering is determined without any communication between the game console and the plurality of computing devices.

21. A method as recited in claim 20, wherein the method is implemented in a match making system separate from the plurality of computing devices.

22. A method as recited in claim 20, wherein one of the plurality of computing devices comprises a game console, and wherein an additional bucket is formed by assigning a set of the computing devices to the additional bucket when the number of computing devices in any one of the plurality of buckets exceeds a bucket threshold value.

23. A method as recited in claim 22, wherein the distances are based at least in part on latitude and longitude values of geographic locations of the game console and the plurality of computing devices, wherein the additional bucket is formed by assigning a portion of the computing devices of a bucket having the most computing devices to the additional bucket.

24. A method as recited in claim 20, wherein the distances are maintained in a table, and wherein a computing device is assigned to a bucket which is geographically closest to the computing device when the computing device is assigned to a bucket and when the computing device is not within geographic boundaries of any of the buckets.

25. A method as recited in claim 20, wherein the ordering is further based at least in part on an Internet provider of the game console and Internet providers of each of the plurality of computing devices.

26. A method as recited in claim 20, wherein the plurality of online game sessions comprise tournament game sessions.

27. A method as recited in claim 20, wherein the plurality of online game sessions comprise game sessions for which no computing device is currently playing in an individual game play session of the game session.

28. A system comprising:

an interface to allow communication with a network; and

a processing unit configured to;

request information from a match making service regarding current online game sessions, wherein the match making service is coupled to the system via the network, wherein each online game session belongs to one of a plurality of buckets and to one of a plurality of layers;

receive, from the match making service, an indication of a plurality of current online game sessions; and

present, in an order based at least in part on distances between the system and other devices that are part of the plurality of current online game sessions, at least a subset of the plurality of current online game sessions, wherein the distances are based at least in part on different data transfer rates in different parts of the network, and wherein the order is also based at least in part on a distance between buckets and on a distance between layers.

29. A system as recited in claim 28, wherein the system comprises a game console, and wherein an additional bucket is formed when the number of online game sessions belonging to any one of the buckets exceeds a bucket threshold value.

30. A system as recited in claim 28, wherein the system comprises a display and wherein the processor is to present the subset via the display, and wherein the system is assigned to the nearest bucket as measured geographically when the system is not assigned to or is not within a geographical boundary of a bucket.

31. A system as recited in claim 28, wherein the processing unit is further to receive, from the match making service, the order for the plurality of current online game sessions.

32. A system as recited in claim 28, wherein the network comprises the Internet.

33. A system as recited in claim 29, wherein the distances are based at least in part on latitude and longitude values of geographic locations of the system and the other devices, and wherein the additional bucket is assigned approximately half of the number of online game sessions belonging to the bucket which has assigned a number of online game sessions which exceeds the bucket threshold value.

34. A system as recited in claim 28, wherein the order is further based at least in part on an Internet provider of the system and Internet providers of each of the other devices.

35. One or more computer readable media having stored thereon a plurality of instructions that, when executed by one or more processors, causes the one or more processors to perform a method, the method comprising:

obtaining, from a match making service over a network, a list of multiple online game sessions that may be joined; and

presenting to a user identifiers of the multiple online game sessions in an order that is based at least in part on distances between the one or more processors and each of a plurality of computing devices that are part of one of the multiple online game sessions, wherein the distances are based at least in part on (1) different data transfer rates in different parts of the (2) a distance between a bucket to which the one or more processors is assigned and a bucket to which each computing device is assigned, and (3) a distance between a layer to which the one or more processors is assigned and a layer to which each computing device is assigned, each game session being assigned to one of a plurality of buckets and to one of a plurality of a plurality of layers.

36. One or more computer readable media as recited in claim 35, wherein the distances are based at least in part on latitude and longitude values of the one or more processors and latitude and longitude values of each of the plurality of computing devices.

37. One or more computer readable media as recited in claim 35, wherein the order is further based at least in part on Internet providers of each of the plurality of computing devices.

38. One or more computer readable media as recited in claim 35, wherein the one or more processors are part of a game console.

39. One or more computer readable media as recited in claim 38, wherein the multiple online game sessions include comprise one or more of short-lived game sessions and persistent game sessions.

40. A method comprising:

receiving a request, from a computing device, for an identification of one or more online game sessions that satisfy one or more criteria;

identifying a plurality of online game sessions that satisfy the one or more criteria;

determining, for each of the plurality of online game sessions, a first distance and a second distance between the computing device and another computing device that is part of the online game session, the determining comprising;

identifying a first bucket of a first layer to which the computing device is assigned, and a second bucket of a second layer to which the computing device is assigned, wherein a layer is a collection of buckets;

identifying a third bucket of the first layer to which the other computing device is assigned, and a fourth bucket of the second layer to which the other computing device is assigned;

identifying the first distance between the first and third buckets; and

identifying the second distance between the second and fourth buckets;

selecting an order in which the plurality of online game sessions are to be presented at the computing device, wherein the order is based at least in part on both the first distance and the second distance; and

returning identifiers of the plurality of online game sessions to the computing device for presentation at the computing device in the selected order.

41. A method comprising:

receiving a request, from a computing device, for an identification of one or more online game sessions that satisfy one or more criteria;

identifying a plurality of online game sessions that satisfy the one or more criteria;

determining, for each of the plurality of online game sessions, a spatial distance between the computing device and another computing device that is part of the online game session, the spatial distance being determined without communicating directly with any of the computing devices;

determining, for each of the plurality of online game sessions, a bucket distance between a bucket to which the computing device is assigned and another bucket to which the another computing device is assigned, the bucket distance being determined without communicating directly with any of the computing devices;

determining, for each of the plurality of online game sessions, a layer distance between a layer to which the computing device is assigned and another layer to which the another computing device is assigned, the layer distance being determined without communicating directly with any of the computing devices;

selecting an order in which the plurality of online game sessions are to be presented at the computing device, wherein the order is based at least in part on the spatial distances, the bucket distances, and the layer distances; and

returning identifiers of the plurality of online game sessions to the computing device for presentation at the computing device in the selected order.