U.S. Pat. No. 9,474,967

DETAILED DESCRIPTION

FIG. 1is a block diagram illustrating an exemplary system100in accordance with aspects of the present invention. System100improves online multiplayer matchmaking by providing improved predictions of network latency and network connection quality between a user of an online multiplayer game and hosts of the online multiplayer game. System100includes a communication network110, which may be the interne, for example. System100also includes user computers120-160and a matchmaking server170. User computers120-160may comprise various compute devices suitable for executing video games and communicating over communication network110. In this example, system100comprises a first game console120and a second game console130, each with associated monitor and game controller. In addition to the game consoles, user computers may comprise any other suitable compute devices such as smartphone140, desktop computer150, and laptop computer160. The user computers120-160each have one or more processors, memory, communication circuitry, and associated hardware. User computers120-160may communicate with other user computers120-160by sending and receiving data through communication network110. Of course, the number of devices shown inFIG. 1is merely exemplary, and in many embodiments, many more devices may be present.

Using a user computer120-160, a user seeking to join a game can connect to the matchmaking server170through the communication network110. Once connected to the matchmaking server170, the user can request a list of games matching one or more selected game characteristics. Examples of selectable game characteristics may include game mode or game type, level or map difficulty, maximum or minimum skill or experience level of other users, preferred game maps, preferred playing partners, gameplay rules, and/or any other characteristics of the desired game. It should be appreciated that the selectable game characteristics may differ from embodiment to embodiment depending on the specific genre and implementation of the game. For example, a first-person shooter game may have different selectable game characteristics than a real-time strategy game or a sports game. In some embodiments, the user's preferred game characteristics may be saved in a user profile, and automatically loaded as default selections.

In some embodiments, the user may select from one or more playlists, which reflect predefined configurations of game characteristics. For example, in a first-person shooter game, playlists may be based on the game mode or game type, and may, for example, include Team Deathmatch (multiple teams competing to vanquish the most opposing teams' members or be the first to vanquish a certain number of opposing teams' members), Capture the Flag (multiple teams competing to capture the opposing teams' flag(s)), Free for All (individual players competing to vanquish the most opponents or be the first to vanquish a certain number of opponents), Kill Confirmed (multiple teams competing to earn points by vanquishing and collecting items from opposing teams' members), and Search & Destroy (multiple teams take turns attempting to achieve a certain objective, for example, deploying a bomb in the other team's base). Of course, these examples of playlists are merely exemplary, and any number of game characteristics can be used to craft a playlist. For example, a playlist may comprise games in which only small maps are used, or games in which only novice players may join. In an online basketball game, playlists may be based on the duration of the basketball game (e.g., two minute quarters, five minute quarters, or fifteen minute quarters) or the number of players per team (e.g., two-on-two or five-on-five). In some embodiments, the user may define his or her own playlists.

After the desired game characteristics are been selected, the matchmaking server170determines available hosts of games matching the selected characteristics. The details of this process are described in more detail below. The matchmaking server170then returns a list of available hosts of games matching the selected characteristics. Alternatively, in some embodiments, instead of returning a list of available games, the matchmaking server may automatically match the user with one of the available hosts.

System100generally comprises a pool of user computers for users seeking to join a game and a pool of potential hosts for the game. In some embodiments, system100is generally configured such that user computers120-160can comprise both users seeking to join an online multiplayer game and users hosting an online multiplayer game. Additionally or alternatively, however, system100may be configured such that user computers120-160are clients seeking to join games hosted by dedicated game servers. The dedicated game servers may perform functions related to video game play amongst users of the user computers120-160. In some embodiments, the server may distribute and coordinate game state and/or action information received from the user computers to allow for coordinated game play amongst multiple users. And in some embodiments, the dedicated game servers may also determine game states based on information received from the user computers regarding actions taken during game play. In some embodiments, the dedicated game servers may be integrated with matchmaking server170. However, in some embodiments, the functionality of the dedicated game servers and/or matchmaking server170may be performed by user computers120-160.

During game play the user computers120-160execute program instructions to provide for play of the video game. Video game users provide game play inputs using their respective input devices, for example game controllers, keyboards, mice, etc., and the associated displays and monitors display game play events. As suggested above, the present matchmaking invention may be applied to virtually any genre of online multiplayer video game, including action/adventure games, fighting games, first-person shooter games, real-time strategy games, role playing games, sporting games, or vehicle simulator games.

FIG. 2is an example of a block diagram of a user computer's processor and associated circuitry useful in accordance with aspects of the invention. As shown inFIG. 2, a processor211is connected to other components via a bus. The other components include a main memory213and a removable memory interface215, generally coupled to a removable memory device, for example, a CD-ROM, DVD-ROM, or Blu-ray disc drive. The processor may execute instructions retrieved from the removable memory device to control game play and store game state information in the main memory. For example, the instructions may be for determining possible movements, positions, and locations of a game character.

The processor is coupled to an audio driver221and a video driver223. The audio driver produces sound signals and the video driver produces image signals. The sound signals and image signals are transmitted from the game console via a display I/O device225. The display I/O device generally supplies the sound and image signals to a display device external to the game console.

The processor may also be coupled to a user I/O device217, a wireless transceiver219, an Internet I/O device227, and other circuitry229. The user I/O device may receive signals from a peripheral device and/or signals from a keyboard, a mouse, and/or a game controller, with generally the keyboard, mouse, and/or controller being used by a user and providing user inputs, for example, during game play. Alternatively or additionally, the game console may receive user inputs via the wireless transceiver. The Internet I/O device provides a communication channel that may be used, for example, for multiple player games.

FIG. 3is an example of a block diagram of a matchmaking server300useful in accordance with aspects of the invention. The matchmaking server is coupled to a network (not explicitly shown), for example the internet. In some implementations, matchmaking server300may comprise one or more of electronic storage302, processor(s)304, external resources306, and/or other components. The various components of matchmaking server300may be configured for electronic communication among one another. Such communication may be accomplished via one or more networks, one or more direct connections, one or more wireless connections, one or more wired connections, and/or other electronic communication media. Matchmaking server300may be in communication with user computers and other client computing platforms.

Processor(s)304may be configured to provide information processing capabilities within matchmaking server300. For example, processor(s)304may configured to execute computer program modules that may include one or more of a matchmaking module310, a data collection module312, a user profile module314, an authentication module316, a communication module318, and/or other modules. In various embodiments, these modules may perform various operations as further discussed herein. In some embodiments, the matchmaking module performs operations relating to matching user game systems with host game systems for multiplayer video gaming sessions. In some embodiments, the data collection module performs operations relating to collection of information regarding potential host systems, and network connection quality indicators between the potential host systems and other potential host systems and/or other game systems. In some embodiments, the user profile module receives and/or determines user information, for example user skill levels, game system game capabilities, preferred game characteristics, and other user related information. In some embodiments, the authentication module performs operations relating to authentication of users and potential hosts. In some embodiments, the communications module performs operations relating to communication with storage and/or external resources, as well as communicating over a network, for example the Internet.

In some implementations, electronic storage302may include information about available games, user profile data, data collected from previous gameplay and matchmaking sessions, and/or other data. In some implementations, electronic storage302may comprise non-transitory electronic storage media that electronically stores information. Electronic storage302may include one or both of system storage that is provided integrally (e.g., substantially non-removable) with matchmaking server300and/or removable storage that is removably connectable to matchmaking server300via, for example, a port (e.g., a USB port, a firewire port, etc.) or a drive (e.g., a disk drive, etc.). Electronic storage302may include one or more of optically readable storage media (e.g., optical disks, etc.), magnetically readable storage media (e.g., magnetic tape, magnetic hard drive, floppy drive, etc.), electrical charge-based storage media (e.g., EEPROM, RAM, etc.), solid-state storage media (e.g., flash drive, etc.), and/or other electronically readable storage media. Electronic storage302may include virtual storage resources, such as storage resources provided via a cloud and/or a virtual private network. Electronic storage302may store software algorithms, information determined by processor304, information received via client computing platforms308, and/or other information that enables matchmaking server300to function properly. Electronic storage302may be a separate component within matchmaking server300, or electronic storage302may be provided integrally with one or more other components of matchmaking server300. For example, in certain implementations, the non-transitory electronic storage media of electronic storage302may include a cache (e.g., L1 cache, L2 cache, etc.) of processor304.

In some implementations, electronic storage302, processor(s)304, external resources306, and/or other components (e.g., additional instances of matchmaking server system100) may be operatively linked via one or more electronic communication links. For example, such electronic communication links may be established, at least in part, via a network such as the internet and/or other networks. It will be appreciated that this is not intended to be limiting, and that the scope of this disclosure includes implementations in which electronic storage302, processor(s)304, external resources306, and/or other components may be operatively linked via some other communication media.

In some implementations, the external resources306may include services and sources of information external to matchmaking server300, for example, autonomous system number lookup services, geo-location lookup services, WHOIS services, or lists of available games external to matchmaking server300. In some implementations, some or all of the functionality attributed herein to external resources306may be provided by resources included in matchmaking server300.

In some implementations, processor(s)304may include one or more of a digital processor, an analog processor, a digital circuit designed to process information, an analog circuit designed to process information, a state machine, and/or other mechanisms for electronically processing information. Although processor(s)304is shown inFIG. 3as a single entity, this is for illustrative purposes only. In some implementations, processor(s)304may include a plurality of processing units. These processing units may be physically located within the same device, or processor(s)304may represent processing functionality of a plurality of distributed devices operating in coordination.

Processor(s)304may be configured to execute matchmaking module310, data collection module312, user profile module314, authentication module316, communication module318, and/or other modules. Processor(s)304may be configured to execute modules310,312,314,316,318, and/or other modules by software; hardware; firmware; some combination of software, hardware, and/or firmware; and/or other mechanisms for configuring processing capabilities on processor(s)304.

It should be appreciated that although modules310,312,314,316, and318are illustrated inFIG. 3as being co-located within a single processing unit, in implementations in which processor(s)304includes multiple processing units, one or more of modules310,312,314,316, and318may be located remotely from the other modules. The description of the functionality provided by the different modules310,312,314,316, and318provided below is for illustrative purposes, and is not intended to be limiting, as any of modules310,312,314,316, and318may provide more or less functionality than is described. For example, one or more of modules310,312,314,316, and318may be eliminated, and some or all of its functionality may be provided by other ones of modules310,312,314,316, and318. As another example, processor304may be configured to execute one or more additional modules that may perform some or all of the functionality attributed below to one of modules310,312,314,316, and318.

FIG. 4shows a flow chart of an illustrative process for online multiplayer matchmaking in accordance with aspects of the present invention. The process may be performed by a matchmaking server as described in connection withFIGS. 1 and 3.

At block402, a user logs into a matchmaking server. There are a number of different ways in which a user may connect to the matchmaking server, including by connecting via a high-speed internet connection, dial-up connection, or any other suitable connection. In some embodiments, the user may be required to have a valid account with the matchmaking server. In some embodiments, the matchmaking service may prompt the user to input a valid username and password. Additionally, the matchmaking service may provide the option of anonymous play or guest login, where authentication is not required. The login process may be performed, for example, by an authentication module of the matchmaking server.

In block404, the process determines if a user profile exists for the user. In some embodiments, the matchmaking service may maintain profiles for users of the matchmaking server, for example, using a user profile module. A user profile can comprise any set of information associated with a user. For example, the profile may contain the user's computing capabilities (e.g., processor speed, storage capacity, connection bandwidth, etc.), skill level, game preferences, login patterns/history, and/or personal information (e.g., location, age, gender, etc.). If a profile is found to exist for the user, the process proceeds to block408. Otherwise, the process proceeds to block406, where a user profile is created for the user. After the user profile is created for the user in block406, the process proceeds to block408, where the process loads the user's profile.

In block410, the process determines the user's selected game characteristics. In some embodiments, the game characteristics may include game mode or game type, level or map difficulty, maximum or minimum skill or experience level of other players, preferred game maps, preferred playing partners, gameplay rules, and/or any other characteristics of the desired game. In some embodiments, the user's preferred game characteristics may be saved in the user's user profile, and automatically loaded as default selections.

In some embodiments, the user may select from one or more playlists, which reflect predefined configurations of game characteristics. For example, in a first-person shooter game, playlists may be based on the game mode or game type, and may, for example, include Team Deathmatch (multiple teams competing to vanquish the most opposing teams' members or be the first to vanquish a certain number of opposing teams' members), Capture the Flag (multiple teams competing to capture the opposing teams' flag(s)), Free for All (individual players competing to vanquish the most opponents or be the first to vanquish a certain number of opponents), Kill Confirmed (multiple teams competing to earn points by vanquishing and collecting items from opposing teams' members), and Search & Destroy (multiple teams take turns attempting to achieve a certain objective, for example, deploying a bomb in the other team's base). Of course, these examples of playlists are merely exemplary, and any number of game characteristics can be used to craft a playlist. For example, a playlist may comprise games in which only small maps are used, or games in which only novice players may join. In some embodiments, the user may define his or her own playlists.

In block412, the process searches for hosts of games matching the user's selected game characteristics. As discussed above, in some embodiments, the games may be hosted centrally by one or more dedicated game servers, which may or may not be part of the matchmaking server. Additionally or alternatively, in some embodiments, the games may be hosted by users. In any case, the matchmaking server maintains a database of all hosted games and their characteristics. The matchmaking server then queries the database to obtain a list of hosts of games matching the user's selected game characteristics. The process then proceeds to block414.

In block414, the process filters the hosts of games matching the user's selected game characteristics (returned in block412) using predefined filters to reduce the number of hosts. In some embodiments, block414may be performed as part of block412. In some embodiments, the filters are based on characteristics of the multiplayer video game to be hosted, characteristics of the players for the multiplayer video game, and/or an internet distance between the user's computer and a host's computer. In some embodiments, internet distance is based on the network conditions and/or the quality of service of communications between computers in the user's autonomous system and computers in the host's autonomous system (e.g., latency, packet loss, jitter (or packet delay variation), availability, etc.). In some embodiments, the network conditions and/or quality of service of communications between computers in the user's autonomous system and computers in the host's autonomous system are continuously collected and updated as part of this process, as discussed below in block416. Additionally or alternatively, internet distance may be determined by the number of hops between computers in the user's autonomous systems and computers in the host's autonomous system. Additionally or alternatively, internet distance may be determined by whether the user's computer shares an autonomous system with the host. In some embodiments internet distance is based on autonomous system distance between game player systems and the host, and in some embodiments internet distance is based on autonomous system numbers. In some embodiments, the predefined filters include a filter based on internet distance between a user and a host and one, some, or all of filters based on skill level of the user, games that allow new users to join, games that have particular aspects requested by or available to the user, or filters based on other criteria. The details of an example filtering process are discussed below in connection withFIG. 5. The process then proceeds to block416.

In block416, the process tests the network connection quality between the user and the hosts remaining after the filtering process. In some embodiments, testing the network connection quality may comprise one or more of determining the round trip time of sending data between the user and the host, determining the connection bandwidth and/or throughput between the user and the host, determining the ratio of sent packets to dropped packets between the user and the host, determining the jitter of packets sent between the user and host, determining the availability of the host, or any other indicators of the quality of service and network connection quality between the user and the host. In some embodiments, the process logs the results of the quality of service and network connection quality tests to provide a continuously updating table or graph showing empirical network conditions and/or quality of service data collected for communications between various computers. In some embodiments, the table or map may be used to determine historical or average network conditions and/or quality of service metrics between a plurality of computers in different autonomous systems. The table or graph may be used in future matchmaking sessions as discussed in block414, above. The process then proceeds to block418.

In block418, the process returns a set of hosts with suitable network connection quality to the user. The criteria for determining whether a host has a suitable connection to the user may depend on the metric used to determine network connection quality in block416. For example, if the network connection quality between the user and the host was determined in block416by observing the round trip time for sending data between the user and the host, then any host that has an observed round trip time less than a threshold amount (e.g., 200 ms or 300 ms) may be deemed to have a suitable connection to the user.

FIG. 5shows a flow chart of an illustrative process for filtering hosts of online multiplayer games in accordance with aspects of the present invention. The process may be performed by the matchmaking servers described in connection withFIGS. 1 and 3. The process may also be performed in conjunction with the process described in connection withFIG. 4.

At block502, the process begins by receiving a list of hosts of an online multiplayer game and information associated with the hosts. In some embodiments, the information associated with the hosts includes information from which an autonomous system of the host may be derived or determined, characteristics of a user of the host, and characteristics of a video game to be hosted. In many embodiments, the hosts may be running games, or be available and/or ready to run games, that match the selected game characteristics of a user seeking to join an online multiplayer game. The process then proceeds to block504.

In block504, the process filters and sorts the received list based on the internet distance between the user and hosts in the list. Generally, the internet distance between a user and a host may be a measurement of the number of hops or transit path length between the user and the host. The internet distance between a user and a host may be determined in a number of ways. In one embodiment, the internet distance may be a function of the number of autonomous systems that a communication from the user must traverse to reach the host. As used herein, the term autonomous system refers to a connected group of one or more internet protocol prefixes run by one or more network operators which, from the perspective of external agents, appears to have a single routing policy. Autonomous systems (also referred to as routing domain identifiers) are used as the unit of routing policies in exterior routing protocols, and are applicable to protocols including EGP (Exterior Gateway Protoocol), BGP (Border Gateway Protocol), and IDRP (OSI Inter-Domain Routing Protocol).

FIG. 6depicts an example of a network of user computers620-650located in autonomous systems AS1-AS3. In the example ofFIG. 6, user computer620and user computer630are both located in AS1, and thus may be considered the closet in terms of internet distance. On the other hand, a communication packet from user computer620in AS1to user computer640in neighboring autonomous system AS2must traverse inter-domain routers connecting AS1to AS2. Communication from user computer620in AS1to user computer650in AS3are farther still, as they must traverse AS2and any other autonomous systems in communication network610connecting AS1to AS3.

Referring back to the filtering process described inFIG. 5, in block504, the process filters the received list of hosts based on the internet distance between the user and hosts. In some embodiments, the process may determine the autonomous system for the user and each host, for example, by using WHOIS services, autonomous system number lookup services, and/or examining BGP routing tables. The process may then determine the hosts that share the same autonomous system as the user. In some embodiments, if the number of hosts that share the same autonomous system as the user does not meet or exceed a certain threshold, the process may additionally determine the hosts that are in neighboring autonomous systems or that are in autonomous systems that can be reached within a certain number of inter-domain hops.

In some embodiments, the process may collect quality of service statistics between users in various autonomous systems and use those statistics as a predictor of internet distance. For example, Table 1, below, shows the average round trip times for packets sent from users located in AS1to users located in AS1, AS2, and AS3:

TABLE 1Average RTT For Packets Sent From AS1AS1AS2AS350 ms100 ms1000 ms
The process may determine that, for a given game, an average round trip time greater than 200 ms would be undesirable. Hence, using the statistical data observed in Table 1, the process would determine that users in AS1may be successfully matched with hosts in AS1and AS2, but would be too remote from the hosts in AS3. Any quality of service metrics can be used including: latency, packet loss, jitter, availability, etc.

In block506, the process filters the returned list for games that are currently allowing users to join. The process then proceeds to block508.

In block508, the process filters the returned games based on skill level (e.g., only return games hosted by similarly skilled players or games allowing similarly skilled players). For example, in some embodiments, skill level of players may be indicated in a numeric manner, and only players within a predefined range of skill values may be allowed to join. In some embodiments, a skill level of a user of the host system is also considered in this regard. The process then returns.

Although the invention has been discussed with respect to various embodiments, it should be recognized that the invention comprises the novel and non-obvious claims supported by this disclosure. For example, while certain embodiments discussed herein have been in the context of multiplayer matchmaking in online video games, one of ordinary skill will appreciate that aspects of the invention may be applied to embodiments outside the gaming context. In particular, the use of internet distance metrics (e.g., the quality of service between computers in different autonomous systems, the number of hops between computers, etc.) as a filter or predictor of network connection quality is useful in any network-based application that attempts to match or pair a user with one of a plurality of potential hosts, servers, and/or peers. As just one example, a media streaming system may have many potential servers capable of streaming a piece of content to a user. In selecting the optimal server to be paired with the user, the system may filter the potential servers based on the internet distance between the user and potential servers, as described in the above embodiments. As another example, peer-to-peer file sharing systems may use the internet distance between the user and potential peers to select suitable network connections.

FIG. 7shows a flow chart of an illustrative process for a user computer selecting a peer (or sever, host, etc.) for networked communications in accordance with aspects of the present invention. The process may be performed, for example, by a system in which a user computer determines a peer with suitable network connection quality from a plurality of candidates.

In block702, the process searches for peers matching the user's desired characteristics. The desired characteristics vary from system to system. For example, in file sharing systems, the desired characteristics may include whether a peer is sharing a desired media file. As another example, in a content delivery system, the desired characteristics may include whether a server is streaming the desired content. The process then proceeds to block704.

In block704, the process filters the peers matching the user's desired characteristics (returned in block702) using predefined filters to reduce the number of peers. The filtering process is generally similar to the filtering process described in connection withFIGS. 4 and 5, and in some embodiments, block704may be performed as part of block702. In some embodiments, the filters are based on an internet distance between the user's computer and a peer's computer. In some embodiments, internet distance is based on the network conditions and/or the quality of service of communications between computers in the user's autonomous system and computers in the peer's autonomous system (e.g., latency, packet loss, jitter (or packet delay variation), availability, etc.). In some embodiments, the network conditions and/or quality of service of communications between computers in the user's autonomous system and computers in the peer's autonomous system are continuously collected and updated as part of this process, as discussed below in block706. Additionally or alternatively, internet distance may be determined by the number of hops between computers in the user's autonomous systems and computers in the peer's autonomous system. Additionally or alternatively, internet distance may be determined by whether the user's computer shares an autonomous system with the peer.

In block706, the process tests the network connection quality between the user and the peers remaining after the filtering process. In some embodiments, testing the network connection quality may comprise one or more of determining the round trip time of sending data between the user and the peer, determining the connection bandwidth and/or throughput between the user and the peer, determining the ratio of sent packets to dropped packets between the user and the peer, determining the jitter of packets sent between the user and peer, determining the availability of the peer, or any other indicators of the quality of service and network connection quality between the user and the peer. In some embodiments, the process logs the results of the quality of service and network connection quality tests to provide a dynamically updating table or graph showing empirical quality of service data collected between various computers. In some embodiments, the table or graph may be used to determine historical or average network conditions and/or quality of service metrics between a plurality of computers in different autonomous systems. The table or graph may be used in future matchmaking sessions as discussed in block704, above. The process then proceeds to block708.

In block708, the process returns a set of peers with suitable network connection quality to the user. The criteria for determining whether a peer has a suitable connection to the user may depend on the metric used to determine network connection quality in block706. For example, if the network connection quality between the user and the peer was determined in block706by observing the round trip time for sending data between the user and the host, then any peer that has an observed round trip time less than a threshold amount (e.g., 200 ms or 300 ms) may be deemed to have a suitable connection to the user. One skilled in the art will appreciate that although specific examples and embodiments of the system and methods have been described for purposes of illustration, various modifications can be made without deviating from the present invention. For example, embodiments of the present invention may be applied to many different types of databases, systems and application programs. Moreover, features of one embodiment may be incorporated into other embodiments, even where those features are not described together in a single embodiment within the present document. Furthermore, all or portions of the subject innovation can be implemented as a system, method, apparatus, or article of manufacture using standard programming and/or engineering techniques to produce software, firmware, hardware or any combination thereof to control a computer to implement the disclosed innovation.