by [email="omar.abdelwahed@bestbuy.com"]Omar A. Abdelwahed[/email]
Revision 1.1
Abstract
This document discusses the concept of "distributed gaming" and the Meesha Network implementation. Distributed gaming allows the specification of application-level resources within a game design. These resources are distributed across a network of peers where multiple peers may serve identical resources. Through a trust relationship, these peers are able to dynamically locate one another and individually determine the best resources available from their own specific view of the network. This allows a high degree of scalability that is both flexible and specific to a resource. As well, distributed gaming creates a means to aggregate the total bandwidth across the network of peers.
It is the goal of this document to show how distributing gaming will dramatically benefit network intensive games.
Background
Distributed computing and peer networks have been around for a long time [1]. There have been several well-known topologies with recent popular implementations seen in such applications as Napster and Gnutella. In fact, the Internet itself can be viewed as a network of distributed, but similar, resources tied together by a common naming system supported by a hierarchical peer network of servers, the Domain Name Service (DNS).
The common distributed topologies include: Centralized, Ring, Hierarchical and Decentralized.
Centralized
The most common topology we see on the Internet is centralized. This design is closely associated with the "client-server" model where a centralized server manages all resources available for client consumption. Most web sites, database applications and online games use such a model.
Pros:
- Simplified administration.
- Ease of maintenance.
- Ease of locating resources. Cons:
- Difficult to scale.
- High cost of ownership.
- Little or no redundancy.
Ring
In a typical ring topology, several identical servers are tied together in a loop-fashion. This allows a degree of scalability and provides simple load-balancing for increases in demand by clients. To facilitate this, servers implementing ring topologies are normally co-located for reliability.
Pros:
- Some scalability.
- Some redundancy.
- Simple load-balancing. Cons:
- Scalability limited to hardware.
- Higher cost of ownership than centralized model.
- Difficult to add more resources.
Hierarchical
Hierarchical topologies follow a tree-like structure where dominance is indicated by the depth at which a node or "leaf" is located. The most dominant node, called the "root", is located at the very top of the tree. Lower-level nodes generally take instruction from higher-level nodes giving a very structured form of communication and control.
Pros:
- Structured communications flow.
- Quick location of resources.
- Resources can be in disparate locations. Cons:
- Timeliness of information can be limiting.
- Propagation of "bad" data can occur.
- Difficult to extend and add new resources.
Decentralized
In a decentralized topology, all peers are equal. They most often duplicate the same resources with connections between peers unstructured and often dynamic. Decentralized applications boast to be the most scalable, but are also the most difficult to manage.
Pros:
- Highly extensible and scalable.
- Highly fault tolerant.
- Dynamic addition of new resources. Cons:
- Scalability overhead can be large.
- Difficultly in synchronizing data and state.
- Extremely difficult to manage all resources. Note: The above descriptions are very basic in nature. They are given only as a generalization for further discussion.
Most modern distributed applications take a hybrid approach by mixing two of the above common topologies. A hybrid approach aims to bridge several benefits of the combined topologies while limiting the difficulties. This approach is used in the Meesha Network implementation of distributed gaming, described below.
Distributed Gaming
The First Attempt
The first network games took a centralized approach. This was the most obvious choice when considering a current game design that one would like to make network-aware. The "client-server" model was well known in other software applications and so were the methods to combat latency and scalability: buy a lot of pipe and high-end servers.
For small network games, a client-server model is still a popular choice. However, this becomes quickly un-wieldy when attempting to scale to thousands or more concurrent users. Obvious bottlenecks occur and the overall game-play degrades.
E-commerce Similarity
A similar situation occurred within e-commerce and the Web. The first approach to sell products online took a client-server model where customers interacted with one or more web servers that in turn interacted with one or more databases. The performance issues that ensued surfaced as incomplete orders, credit authorizations that "hung", and product pages that never fully displayed, to name a few.
Reliable methods were needed to scale specific "pieces" within an e-commerce site. This led to the introduction of several component architectures (including CORBA, COM and EJB) to better identify and encapsulate these pieces of functionality. This also facilitated the means to dynamically scale resources within a given server. However, scaling across server boundaries was still very difficult to accomplish and generally required that all servers were co-located for better efficiency. Without the ability to scale specific resources across a collection of servers, component architectures were limited to duplicating all resources across identical servers with the load-balancing of user requests handled by external network hardware.
A further means was needed to scale specific e-commerce resources. The ability to perform this across heterogeneous platforms was also desired. Moreover, the ability for disparate systems to interact from separate, remote locations would facilitate business-to-business (B2B) transactions between corporate partners. In the end, such facilities would help prove e-commerce as an efficient, online retail channel.
Recently, "web services" has become a popular technology to deliver such facilities. This technology enables disparate, heterogeneous systems to communicate effectively across the Internet with one another and expose internal services in a common structured language. Web services also shares many goals with peer networking. [2]
Distributed Gaming
Online gaming can learn from the trials put through e-commerce development. The differences between the two applications can be generally boiled down to the nature of the specific resources and the timeliness of the data. Whether we talk about the state of product information in an e-commerce system or the state of the "universe" in an online game, the issues of scalability, reliability and availability are still the same.
Drawing from web services and peer networking, we can envision a model for online gaming with the following features:
- Redundant, loosely-coupled, game-specific resources.
- A mechanism for the discovery of these resources.
- The ability to dynamically switch between resources that provide the same service or information.
- A trust relationship between resources and metrics by which to measure that trust. To facilitate these features, we define the following:
The Resource: The encapsulation of a specific source of information or service particular to a game. The total extent of a game application is the summation of all unique resources. All resources share these qualities:
- Uniquely identifiable.
- Locatable.
- Ability to communicate with other resources.
- Ability to synchronize internal state with other similar resources. The Provider: A peer that provides a unique resource to consumers.
The Consumer: A peer that seeks service or information from another peer it considers "trustworthy" to some measurable degree. A consumer can be any peer in the network, including those that are also providers.
The Trusted Peer: A provider that, over time, has given a degree of consistent information or service so that it is considered relatively "trustworthy" by a specific consumer. Trust is measured by a combination of metrics that represent the reliability and availability of the information or service that the trusted peer provides to the consumer. As such, these metrics are calculated from the viewpoint of the consumer but can be shared with other consumers to build a "network of trust" amongst all consumers seeking the same resource.
The Registrar: A specific type of provider that manages the discovery and location of all types of resources. All providers are required to provide information to a registrar that uniquely identifies it in the network and describes the type of information or service that it provides. Registrars maintain a map of resources amongst one another so consumers have a means of discovery for specific resources and the available providers.
The Game Network: A network of loosely-coupled resources that collectively represent all functionality, services and information for a specific game application. The state of the game is the collective state of the individual resources for any point in time. Multiple resources exist that duplicate the same information or service. Resources can discover and locate one another through a specific resource called the Registrar. These resources can then actively communicate with one another and dynamically determine the most available and reliable resources from their unique view of the network based on a measurable trust relationship. Scalability is dynamically increased as more redundant resources are introduced to the network, are discovered by other consumers, and rise in trust value. Similarly, the game network is extended in functionality by the introduction of new types of resources.
The Game: An application that consists of a dynamic collection of unique resources provided by the game network. The specific resources that make up a game for an end-user can change at any time but must always provide the most reliable and most available services and information. The switching of resources must be transparent to the user. At all times the user's view and experience of the game must be consistent and not interrupted by the switching of resources.
An Example
Suppose we have a typical massive, multi-player, online, role-playing game (MMORPG). We can define the features and functionality of this game as a set of unique resources (Diagram1):
- Map System: The world in which the game takes place.
- Events System: Unique activities that are time sensitive, such as weather, changes in environment and non-player character (NPC) campaigns.
- Player System: The management of player state and related information. (Note that in this example our players make up part of this system.)
- NPC System: The management of NPC state and related information. This could include monsters, wildlife and other non-player characters.
- Time System: The global clock. A simple resource to synchronize time amongst all resources. With this simple set of resources, we have a representation of the majority of functionality found in today's MMORPGs. In order for a player to enter the game, she must locate providers of these five resources. (This will require, of course, Registrar resources, as described above.)
As with other MMORPGs, we quickly realize that we must handle thousands of players, if not more. Thus, the Game Network needs to include more redundant providers in the Player System. As players come online, they will locate an available provider from the Registrar. Scaling the network to meet the demand of even more players simply requires the addition of more providers.
Similarly, the other resources must scale as demand increases. However, for simple resources, providers that also serve other, more complex resources may manage this. The Time System is a good example of this. All resources, including the Player System that represents the users themselves, can be providers of the global clock. This is a design consideration to allow the other resources a more reliable means to synchronize state amongst each other.
As a user interacts with the game application (or, rather, as the player plays the game), the supporting systems may change according to the user's unique view of the network at specific moments in time. Indeed, the game itself may add new features and functionality as the user's game progresses. This is perhaps the greatest feature of distributed gaming: the ability to scale and simultaneously evolve without disturbing game play. As more resources are introduced to the game, the better the game becomes.
Diagram1: The entire game network for our MMORPG example consists of six distinct systems containing redundant resources. Note that the players are considered part of one system.
The Meesha Network
The Meesha Network is an implementation of distributed gaming, as described above. It presents a simple API to create game-specific resources and the game network in which they exist. Meesha facilitates all functionality and management transparently to the game application.
The Meesha Network provides the following:
- Creation of resources.
- Discovery of resources.
- Communication between resources.
- Trust metrics.
- Dynamic resource switching. The current Meesha implementation is specific to Windows platforms. Its API is exposed as a collection of COM objects for quick and easy integration to existing game designs. A technical demo is available upon request (see "About the Author", below).
Demo Screenshots
The current technical demo implements a single resource type: the map system. The map system tracks information regarding the position of a single terrain object. For the purposes of the demo, one local consumer and two remote providers are shown (Screen1).
When the demo starts, the consumer has not received information from either provider resource, thus showing the position of the terrain object incorrectly (Screen2). (Note: the providers are shown side-by-side for the purposes of the demo. In reality, they would serve the exact same positional data.) As the consumer receives data from one of the providers, it corrects its display of the terrain object to follow this provider (Screen3). The consumer will continue to follow the provider across the screen as information is received (Screen4). Artificial latency is introduced between the providers and the consumer so that the consumer will attempt to re-send requests that were not answered in a timely fashion (Screen5). When the "retries" count reaches 10, the consumer will switch from its current provider to the other provider (Screen6). This demonstrates the ability of the consumer (and all peers in the Meesha Network) to dynamically switch resources based on its particular view of the network.
Screen1: The red ring indicates the "localmap" consumer. Particle effects rings indicate the "remotemap1" and "remotemap2" providers.
Screen2: The state of "localmap" is not synchronized with any provider.
Screen3: "Localmap" is following "remotemap1".
Screen4: As long as responses are timely, "localmap" continues to follow "remotemap1".
Screen5: "Localmap" re-sends several requests to "remotemap1".
Screen6: "Localmap" switches resource providers to "remotemap2".
Conclusion
Distributed gaming and the Meesha Network implementation have profound implications for online gaming. It is easy to imagine a highly distributed game application where the users themselves increase resource availability by becoming resource providers. (This would have the added benefit of aggregating bandwidth at the end-users!) However, traditional online games companies can also leverage the Meesha Network as a means to easily evolve existing applications in order to scale specific resources (the Player System, the Map System, etc.) and to leverage existing investments in infrastructure. Meesha is an enabling technology that is non-specific to any particular online game.
Distributed gaming provides availability, reliability and scalability to online gaming. It consists of a hybrid of peer topologies and provides a proven services model found in e-commerce. The Meesha Network implements distributed gaming in a simple API so that existing and future game applications may feature distributed gaming in their designs.
About the Author
Omar Abdelwahed graduated from the University of Minnesota-Duluth in 1994 with a bachelor's degree in Computer Engineering. He has worked in Information Technology since the ripe old age of 15 and wrote his first video game in 1984 (affectionately titled "Save the World From All the Rockets that Keep Appearing from the Right-Hand Side of the Screen"). Currently, Omar is a lead software engineer at Best Buy Co., Inc. where he designs and develops entertainment web sites.
Omar can be reached by e-mail at: [email="omar.abdelwahed@bestbuy.com"]omar.abdelwahed@bestbuy.com[/email].
Further Information / Endnotes
[1] Distributed Systems Topologies: Part 1 by Nelson Minar.
[2] Convergence of Peer and Web Services by Jeff Schneider.
