Patent Publication Number: US-2010113158-A1

Title: Method and apparatus for hosting a distributed virtual world system

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention relates generally to online applications and in particular to online gaming applications. 
     2. Background Information 
     Conventional massively multiplayer online games (MMOGs) and virtual worlds (such as Second Life), shown by example in  FIG. 1 , are unable to scale to support very large numbers of players within a single game/world. This is because such games and virtual worlds are reliant on a single instance of the game, running on a single physical computer system, acting as the authority for all activities within the game. Typically, the limits to scaling in this scenario are the network bandwidth of the single system and, more significantly, the processor capacity of a game server in the system. The game server, functioning as a game engine, is required to provide the simulation capabilities for every object and player in the virtual world. As the number of players (clients) increases, the computing resources required increases dramatically. Certain game servers, particularly those providing FPS (First Person Shooter) styles of games, are only capable of supporting tens of users due to the complexity of the simulation and the low latency requirements of the game. 
     As shown in  FIG. 2 , in an attempt to address such issues, in certain conventional approaches, game systems implement “sharded” architectures that use a number of game servers (game engines), each hosting identical copies of a game. The players (clients) sometimes connect to the game through a common “lobby” service that hides the fact that there are multiple servers hosting the game. A major disadvantage to such approaches is that players are assigned to a particular server (at connection time) for the duration of their game session, and are thus effectively in different games and only able to interact with other players on the same server. Players on other servers are invisible. 
     Other approaches involve dividing up a virtual world between servers, and the players then teleport or use a device to move between world areas. A disadvantage of such approaches is that artificial boundaries have to be imposed between areas of the world to prevent the players from walking to or seeing between areas hosted on different servers. These approaches also can fail if all the players teleport to the same area, causing a single server in the system to overload. 
     Yet other approaches attempt to address the problem of scaling, such as OptimalGrid architecture shown in  FIG. 3 . The OptimalGrid approach used with QuakeII as the game engine relies on proxy servers receiving data for their clients from every game server (game engine) that is running a map part within the current sphere of interest of the client. As such, the game servers are required to transmit more data across the internal network (e.g., User Datagram Protocol (UDP)), between the servers and the proxies, than is actually required by the clients. This can lead to network congestion and excess work for the proxy and/or game client in filtering out the unwanted data. The approach also relies on the proxy emulating the client protocol to the server, and thus additional UDP protocol hops are introduced increasing the possibility of packet loss. 
     SUMMARY OF THE INVENTION 
     The invention provides a method and apparatus for hosting a virtual world system including clients and game engine servers, comprising: providing a publication and subscription framework; interfacing the clients with the framework using a plurality of client proxies; interfacing each game engine server with the framework using a game engine agent; and decoupling the proxies from the game engine servers using the framework. 
     Other aspects and advantages of the present invention will become apparent from the following detailed description, which, when taken in conjunction with the drawings, illustrate by way of example the principles of the invention. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       For a fuller understanding of the nature and advantages of the invention, as well as a preferred mode of use, reference should be made to the following detailed description read in conjunction with the accompanying drawings, in which: 
         FIG. 1  shows a typical massively multiplayer online game (MMOG) architecture. 
         FIG. 2  shows a typical shared MMOG architecture. 
         FIG. 3  shows an OptimalGrid MMOG architecture. 
         FIG. 4  shows a functional block diagram of a virtual world hosting architecture using a publish and subscribe (pub/sub) framework, according to an embodiment of the invention. 
         FIG. 5  shows a functional block diagram of the pub/sub framework, according to an embodiment of the invention. 
         FIGS. 6-7  show processes and data flows illustrating hosting a distributed virtual world system, according to an embodiment of the invention. 
     
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     The following description is made for the purpose of illustrating the general principles of the invention and is not meant to limit the inventive concepts claimed herein. Further, particular features described herein can be used in combination with other described features in each of the various possible combinations and permutations. Unless otherwise specifically defined herein, all terms are to be given their broadest possible interpretation including meanings implied from the specification as well as meanings understood by those skilled in the art and/or as defined in dictionaries, treatises, etc. 
     The invention provides a method and apparatus for hosting a distributed virtual world system. One embodiment involves a method and apparatus for hosting a distributed virtual world system using a publish and subscribe (pub/sub) framework and prioritized topic spaces. The invention allows hosting a virtual world that is distributed across multiple servers (game engines), with all players (clients) in the same game. The invention also provides dynamic adjustment of the game workload to avoid system overload situations. In addition, the network usage between the servers and proxies is essentially minimized by delivering data using a high speed publish and subscribe framework, optionally using UDP multicasting. This permits prioritization of the data flows, increasing the decoupling of the proxies and servers, and removing duplicate data transmission. 
       FIG. 4  shows a functional block diagram of a system  10  embodying the invention. The system  10  provides a virtual world hosting architecture, including a topology where world/game clients  12  connect to one of a number m of client proxy servers  14  which in turn communicate with a grid of n game engine servers  16  over which the world map is spread. Each game engine server  16  is interfaced to a pub/sub framework  18  and managed by a corresponding engine agent  19  that isolates the game engine from the details of the pub/sub mechanism. A hosting architecture according to an embodiment of the invention includes said client proxies  14 , the framework  18  and engine agents  19 . 
     The World Manager is an optional component that listens to traffic in the pub/sub framework and can reorganize the hosting of the game/virtual world so as to balance the load across the servers. 
     In one embodiment, the virtual world map can be statically divided up before starting the system and no World Manager is required, the allocation of responsibility for areas of the map being fixed for the duration of the game/world run. 
     In another embodiment, a World Manager is added to dynamically rebalance the load on the servers in the system by changing their responsibilities in response to changes in the usage patterns. Servers publish information about their usage periodically or when exceptional situations develop. As such, a server that is becoming overloaded publishes information (i.e., via the pub/sub framework) that the World Manager will listen for. The World Manager can then reallocate responsibility for the pieces (i.e., grid squares/cubes) of the map between the servers to ensure that the load can be accommodated. Busy areas of the map may be divided between servers, or moved to more capable servers, whereas areas where there is little activity may be handed off to less capable servers. 
     The clients  12  communicate with the proxies  14  using the UDP protocol over a network  15 . The proxies  14  communicate with the game engines  16  using the pub/sub framework  18  which may operate e.g., using a very high performance network mechanism, such as UDP multicasting, a reliable transport such as TCP (transport control protocol), or a very specialized system such as a high speed processor interconnection mechanism. The system  10  hides the underlying communication technology and protocols from both the proxies  14  and the servers  16  which use a pub/sub application programming interface (API) for interaction with the pub/sub framework  18 . 
     In a preferred implementation, the high-performance pub/sub framework  18  connects the proxy servers  14  with game servers  16  via engine agents  19 . The pub/sub framework  18  services game and world clients (players)  12 , and connects them to a grid of game and world servers (game engines)  16 . The pub/sub framework  18  provides decoupling of the proxies  14  from the servers  16 , and permits proxies  14  and servers  16  to be taken on and off line, or the workload to be rebalanced between them without the need to inform all the other systems within the grid. Data is published to topics, which may represent logical server identities or roles, and is delivered by the pub/sub framework  18  to those processes that expressed an interest (subscribed) to the topic. 
     Specifically, the pub/sub framework  18  decouples the proxies  14  and servers  16  from the underlying network technology and topology of the grid. By removing any knowledge of the underlying network topology or technology from the proxies  14  and servers  16 , the same pub/sub framework approach may be deployed on multiple technologies. This allows the approach to be adapted for the specific requirements, where for a first person shooter (FPS) game, performance and minimal latency is key and thus the system may be deployed using UDP multicasting. On the other hand, for a virtual world commerce system used for retail, where the quality of visual experience is key and financial transactions are taking place, the same basic pub/sub framework approach may be deployed over a reliable network technology to ensure all client to server interactions are guaranteed to be delivered to the server. 
       FIG. 5  shows a functional block diagram of a preferred implementation of a high-performance pub/sub framework  18  for connecting the proxy servers  14  with the game servers  16  via engine agents  19  ( FIG. 4 ). The pub/sub framework  18  provides a filtering service process  20  for filtering data flowing between the game engine servers  16  and the proxies  14 . Accordingly, using a subscription service process  22  of the pub/sub framework  18 , the proxy servers  14  subscribe to topics relevant for their clients  12 . Using a publication service process  21  of the framework  18 , a game engine  16  publishes data changes for each object or player it is managing once per game cycle (i.e., publishing data to named topics). The subscribing proxies then aggregate the received data from the framework  18  and forward the aggregated data to their clients  12 . This reduces the load on the game engines  16  and thus allows them to support more entities at any time. By contrast, in conventional approaches, game servers provide client specific data updates. The server cycles through each of its currently connected clients and deduces which data is needed for each client based on the context of the player&#39;s avatar. This process involves the transmission of a large amount of duplicate data where the same data for an object may be required by multiple clients. The process of cycling through and delivering data based on the context for each client is expensive in both computation time and network bandwidth. 
     An example of a method wherein the topics of the pub/sub framework are used by the components of the system, is now described. Consider topics that are related in some way to the coordinate system of the map. The map is subdivided into grid squares/cubes to allow distribution of responsibility across the available simulation engines. Each square/cube is associated with 2 topics, one for inbound data from clients and one for outbound data destined for clients. 
     A client proxy representing a client will publish data arriving from the client to a topic that represents the grid square/cube that the avatar of the client is currently residing in. The engine agent for the simulation engine with responsibility for that grid square/cube will subscribe to that topic (and the topics of any other squares/cubes it is responsible for) and will thus receive data updates from the client. 
     As the simulation runs, a simulation engine will periodically generate updated data about the objects in the area(s) of the map that it is responsible for. It publishes each data update to the topic associated with outbound data for the grid square/cube in which the object is currently located. The client proxy for a given client subscribes to the outbound data topics for the square/cube in which the avatar of the client currently resides and any other squares/cubes within the visible distance of the avatar. The client proxy thus receives data updates for all objects that are visible to the client from all simulation engines responsible for those objects. The client proxy aggregates this data into an outbound data packet that is then sent to the client. 
     The pub/sub framework  18  provides a prioritization function process  23  that prioritize data flows between game engine servers and client proxies, wherein in addition to publishing data to named topics, the framework  18  allows associating a priority along with any publication. This publication affects the order in which data packets are queued for delivery to the subscribers. Further, the subscribers can associate a subscription priority, which can override the priority associated with a transmission by the publisher. This prioritization allows a game server  16  to flag important data with a high priority, such as that associated with a fast moving projectile, to provide clues to the subscriber. On the other hand, a proxy server  14  may associate a lower priority with topics associated with objects further away from the client and thus can receive the most significant data first for each update cycle. In situations where bandwidth is constrained, the prioritization allows a proxy server  16  to filter out less important data with minimum computational effort. 
     The pub/sub framework  18  further provides a mediation process  24  with the ability to add mediations to the data flows between the proxies  14  and the servers  16 . The mediation process modifies or redirects data flows within the framework. These mediations are hidden from the publisher and the subscriber, as they are within the framework itself and not visible via the normal publication and subscription application programming interfaces (APIs). This allows dynamic text translation or rerouting to take place without the need to change the application itself. 
     The pub/sub framework  18  further provides a process addition function  25  for adding complex event processing systems without modification to the core game or hosting components. Using the function  25 , other processes in addition to ClientProxy and EngineAgent processes (modules), can subscribe to topics. This permits use of complex event processing systems to detect malicious activity, such as denial of service attacks, cheating using automated clients, or account hijacking. Other capabilities such as logging and audit sampling or workload balancing capabilities may be easily attached. 
       FIG. 6  shows an architecture  30  of processes and data flows illustrating how the client  12 , proxy sever  14 , engine agent  19 , game engine  16  and framework  18  function and interact, according to an embodiment of the invention. 
     Setup Phase 
     When the system starts up the engine agents, the game simulation engines of the system are allocated areas of responsibility within the virtual world/game map by the World Manager. These areas of responsibility are represented by one or more grid square/cube identities. Further, as part of the start up phase the engine agents subscribe to the topics in the pub/sub framework that represent each of the grid squares/cubes. At least one of the engine agents also subscribes to a topic representing new client connection requests. 
     Client Connect 
     Once the system is operational, at some point game clients will attempt to connect by opening a network connection with an available client proxy. That client proxy receives the inbound connect message and in response subscribes to a topic in the pub/sub framework representing the new client. The client proxy then publishes the connect message to a topic representing new client requests. An engine agent receives the new client request and forwards the connect message to its game engine. The game engine creates the in-game representation of the player at some defined point in the map and responds back to the engine agent. The engine agent publishes the response on the topic expected by the client proxy which then receives it and returns the response to the client. 
     Run Phase 
     Once connected, clients and game engines run a continuous cycle of message exchanges e.g., typically every 100 milliseconds (10 times per second). The client sends any updates reflecting the movement and actions of the player in an update packet to the corresponding client proxy. The client proxy performs a partial decode of this information to locate the position of the player within the virtual world/game. The client proxy maps the player&#39;s position into a set of topics that represent the grid squares/cubes that surround the player and are visible to the player. The client proxy ensures it has active subscriptions with the pub/sub framework for each of the outbound data topics that represent these grid squares/cubes. As the player moves around the map, this may involve the client proxy dropping existing subscriptions and creating new ones. 
     The client proxy then publishes the clients update message to the inbound data topic that represents the grid square/cube in which the player currently resides. The engine agent responsible for that area of the map, having a subscription for the relevant inbound topic, receives the update packet and forwards it to the game engine for processing. 
     At regular intervals (e.g., typically 10 times per second) the game engines in the system run a simulation and reconcile the updated data from the various clients with the simulation data generated. Updated data for objects and players within the game is generated. As part of the simulation process the game engine sends data updates for each object within its areas of responsibility to its engine agent that publishes each update on the outbound topic that represents the grid square/cube in which the object resides. 
     The client proxy, having subscriptions to the outbound topics for the grid squares/cubes surrounding the player receives one or more update messages from one or more engine agents. The client proxy aggregates these changes into a single update packet for the client and transmits it to the client. 
     Client Disconnect 
     At some point the client ends the game or otherwise disconnects. A message is sent to the client proxy or the network connection to the client is dropped whereupon the client proxy sends a disconnect message to the game engine controlling the clients avatar by publishing it to the inbound topic representing the grid square/cube in which the player was last known to reside. 
       FIG. 7  shows an architecture  40  for processes and data flows illustrating how the engine agent  19 , World Manager  17  and game engine  16  function and interact in conjunction with a World Manager, according to an embodiment of the invention. 
     World Manager Interactions 
     The World Manager controls the operation of the system and performs load balancing to ensure the simulation runs smoothly. The World Manager uses a set of topics on which it publishes and to which it subscribes. One of the topics used represents performance feedback data from the engine agents reflecting the current state of the game engine. Other topics are used to represent the individual engine agents within the system. Each engine agent subscribes to its own topic which the World Manager uses to communicate with it. The use of a topic abstracts the engine agent and allows the World Manager to operate without information on the physical machines or network topography. 
     Setup Phase 
     During the system setup phase the World Manager assigns responsibility for the grid squares/cubes representing the area of the virtual world/game to the available game engines. The mapping of the virtual world map may be performed in a number of ways, for example, by allocating equal sized contiguous areas to each server or by randomly allocating grid squares/cubes. More or less complex schemes can be employed. The World Manager informs each engine agent of its map responsibilities by publishing to the topic representing the engine agent. The World Manager also subscribes to the general feedback topic ready to receive periodic updates from the engines. 
     Run Phase 
     Once the setup is complete the system transitions to the Run phase whereupon the game engines begin the simulation. As clients connect, disconnect and move around the map, the load on each of the individual servers may change dramatically. At regular intervals each of the engine agents publishes feedback data which may include data concerning the CPU utilization, network utilization, memory usage, number of clients currently within the area of responsibility, etc. 
     The World Manager receives these regular feedback reports from each of the engine agents and builds an overall view of the state of the system. If a game server is detected to be overloaded, or likely to become overloaded if the trends continue, the World Manager may decide to repartition the virtual world to reduce the number of grid squares/cubes being handled by the overloaded server to attempt to reduce its load. The World Manager publishes new partitioning data to the topics representing those engine agents affected by the changes. 
     As is known to those skilled in the art, the aforementioned example embodiments described above, according to the present invention, can be implemented in many ways, such as program instructions for execution by a processor, as software modules, as computer program product on computer readable media, as logic circuits, as silicon wafers, as integrated circuits, as application specific integrated circuits, as firmware, etc. Though the present invention has been described with reference to certain versions thereof; however, other versions are possible. Therefore, the spirit and scope of the appended claims should not be limited to the description of the preferred versions contained herein. 
     Those skilled in the art will appreciate that various adaptations and modifications of the just-described preferred embodiments can be configured without departing from the scope and spirit of the invention. Therefore, it is to be understood that, within the scope of the appended claims, the invention may be practiced other than as specifically described herein.