Network Algorithmics by Varghese

I skimmed Network Algorithmics by George Varghese (2005). This book presents common tricks used at the OS, hardware, and architecture levels to prevent network bottlenecks. Here are 15 principles listed on the first page.

Number	Principle	Example
1	Avoid obvious waste	Zero-copy interfaces
2	Shift computation in time
2a	Precompute	Application device channels
2b	Evaluate lazily	Copy-on-write
2c	Share expenses, batch	Integrated layer processing
3	Relax system requirements
3a	Trade certainty for time	Stochastic fair queuing
3b	Trade accuracy for time	Switch load balancing
3c	Shift computation in space	IPv6 fragmentation
4	Leverage off system components
4a	Exploit locality	Locality-driven receiver
4b	Trade memory for speed	Processing, Lulea IP lookups
4c	Exploit existing hardware	Fast TCP checksum
5	Add hardware
5a	Use memory interleaving and pipelining	Pipelined IP lookups
5b	Use wide word parallelism	Shared memory switches
5c	Combine DRAM and SRAM effectively	Maintaining counters
6	Create efficient specialized routines	UDP checksums
7	Avoid unnecessary generality	Fbufs
8	Do not be tied to reference implementation	Upcalls
9	Pass hints in layer interfaces	Packet filters
10	Pass hints in protocol headers	Tag switching
11	Optimize the expected case	Header prediction
11a	Use caches	Fbufs
12	Add state for speed	Active virtual circuit list
12a	Compute incrementally	Recomputing CRCs
13	Optimize degrees of freedom	IP trie lookups
14	Use bucket sorting, bitmaps	Timing wheels
15	Create efficient data structures	Level-4 switching

Blizzard's Hadoop platform

Talk given by Brian Griffith and Amanda Gerdes at the OC Hadoop user group meeting in October 2013.

Blizzard uses the same Hadoop platform for Diablo 3, Starcraft 2, WoW, and Hearthstone. This platform went live in March 2013. Before this platform, game developers would log game events in log files, and use custom scripts to ETL these log files into relational databases for analysis. Problem: cumbersome, hard to maintain, low performance.

Solution: game developers, on their own, decide what to track in their game, and send that data to the platform. Instead of a log file, the game developers send protobuf objects. The 20 nodes in the Hadoop cluster receive and deserialize around a billion objects per day. The message's headers determine where to store each protobuf object within Hadoop. Blizzard also uses Hadoop as an operational data store. The cluster runs map-reduce jobs to filter and aggregate the stored protobuf objects. Currently, the 20 nodes store 60TB, but now that Blizzard realizes what they can do with Hadoop, they plan a 100-node cluster storing 1PB. Current bottleneck: CPU for deserialization. They rarely hit the disk for data so no IO waiting bottleneck.

For the messaging, they use a federation of machines running RabbitMQ. 50 producers worldwide (China, Europe, US, etc.) and 8 consumers (most likely in the Blizzard headquarters in California). When an Internet cable got cut with China, some messages were queued for 40 hours.

The analysts were using Greenplum for processing game data in parallel and ETL. Now that Hadoop is in place, they could start using Pig for ETL. But sales and customer data still come from relational databases, and the Greenplum is great at ETL. So there is no reason to force analysts into Hadoop. Solution: ETL jobs pull data from Hadoop and store it into Greenplum for warehousing. Greenplum is still in charge of its own ETL jobs.

Some data (such as a character's level or class in WoW) stay interesting across patches, but others (such as transmogrification usage) are only interesting when the feature launches. So the platform allows to build KPIs daily (e.g. activity aggregated per character level) and dive deep on demand.

Use case: WoW economy. Every gold transaction is sent to Hadoop. Reduce step aggregates by NPC id, item id, or player id. Makes it possible to:

• Check if the gold sinks follow designers' expectations.
Detect networks of gold farmers.
• Keep an eye on auction house prices.
• More ...

Netgames 2005

Summary of selected papers from the NetGames 2005 conference.

Traffic Characteristics of a Massively Multi-player Online Role Playing Game, by Kim et al.

• Port mirroring through 1Gbps hub and tcpdump of 92 hours of a Lineage 2 server in December 2004. TCP packets.
• Both upstream and downstream increase linearly with number of concurrent users.
• Play session duration: 3 hours average, 26 min median, 40+ hours 99%

Stream	Number of packets	Ratio of data packets	Payload (avg, median, and 99%)	Bandwidth	Bandwidth per user
Upstream (clients to server)	6.28 billions	23% (the rest are ACKs, SYNs, or FINs)	19, 20, 50 bytes	max 9 Mbps	1.6 kbps
Downstream (server to clients)	6.43 billions	98%	318, 161, 1459 (= MTU) bytes	max 140 Mbps	20 kbps

Dynamic Microcell Assignment for Massively Multiplayer Online Gaming, by De Vleeschauwer et al.

• Divide the world in atomic square microcells. Compute each microcell's load induced by processing player actions (weight=1), forwarding player actions to neighbouring cells (w=0.05 if cells on same machine, w=0.1 if cells on different machines), receiving forwarded actions from neighbouring cells (w=0.2, w=0.4), and moving players to and from neighbouring cells (w=3, w=15). Then, assign cells to servers so that no server has a higher load than another server.
• Algorithms to assign cells to servers:
  • Greedy: processes cells in descending order of their load, and assigns them to the server currently with the lowest load. Pro: fast. Con: does not take locality into account.
  • Clustering: start with each cell is a cluster. Merge two clusters that have the lowest load until there are as many clusters as servers. Con: in the last few steps, some heavy-load clusters are merged and may be assigned to servers that can't handle them.
  • Simulated annealing: start by randomly assigning cells to servers, then randomly swap or move cells around to find a better solution, and keep iterating to refine the solution. Able to find very good solutions if the initial solution comes from another algorithm.
  • Integer linear programming for the optimal deployment. Pro: optimal. Con: takes days to compute, but a timeout can be specified to get a suboptimal solution. (But then, other algorithms give better results faster).
• Evaluation: If player hotspots are spread randomly, the maximum server load can be reduced by 30% compared to the baseline with one large cell of constant size per server. But if hotspots are regularly spread, and there's as many hotspots as available servers, then the microcell algorithms are at least 10% worse than the baseline. In general, simulated annealing starting from a greedy solution was the most efficient of the algorithms.

Netgames 2004

Implementation of a service platform for online games, by Shaikh et al.

• How to provision a cloud infrastructure hosting games
• Each bot sleeps periodically to reduce CPU load and instantiate more bots. Bots connect to the game server according to a Poisson process with mean inter-arrival time of 1/λ=1s
• TIO polls game servers at regular intervals for their CPU load using SNMP. Using the raw CPU leads to occasional over-provisioning and higher costs, but using a moving average to smooth the CPU estimate misses CPU peaks and may result in inefficient QoS for some players.
• Since player load follows daily and weekly patterns, it's possible to anticipate the peaks; in that case, provision slightly ahead of the peak and keep a smoothed metric.
• Relevant metrics other than CPU: "slack time" = unused time during an iteration of the server loop

Zoned federation of game servers: a peer-to-peer approach, by Iimura et al.

• DHT implementation is Pastry. It uses SHA1 to map a game zone to its owner and runner.
• Experimentation with 296 P3 1Ghz 512MB, all connected to a single 100Mbps switch. 295 machines run from 100 to 1,000 members, and a single machine runs the zone owner. Time taken to update the state of everybody is exponential with the number of zone members (average of 50ms for 500 members, 100ms for 700, 200ms for 1,000).
• Spreading users uniformly on multiple zones, each with a single zone owner, reduces the load.

Scalable Peer-to-Peer Networked Virtual Environment, by Hu and Liao

• Scalability implies that nodes can be added or removed on the fly while keeping the whole system functional. Ultimate P2P goal: adding a node should increase overall system resources without consuming centralized resources.
• Cut the virtual space in Voronoi cells, where each user is at the center of his cell (deterministic algorithm). Each user connects with at least all his Vornoi neighbors (min 3, average 6, max n-1), and with more users if they are in his area of interest. Each time a user joins, moves, or leaves the game, his neighbors have to recompute their Voronoi diagram.

Graphics cards on Ubuntu

Problem

My configuration: Lenovo T410, Ubuntu 11.10, Nvidia GT218.

OpenGL does not seem supported by default. Running nvidia-settings in a console says You do not appear to be using the NVIDIA X driver. Please edit your X configuration file (just run `nvidia-xconfig` as root), and restart the X server..

After following these steps, the environment does not show up anymore when rebooted - only a console-like frozen screen. An actual command-line console can be found using ctrl+alt+F1 to ctrl+alt+F6. Ctrl+alt+F7 goes back to the console-like frozen screen. The screen is frozen most likely because the x server did not start.

It turns out the actual problem is the hybrid graphic card configuration. Hybrid cards configurations for laptops have 2 cards: one for performance (e.g. Nvidia GT218), and one for battery life (usually integrated graphics, e.g. from Intel). The switching is supposed to be done automatically by Nvidia's Optimus software. But Ubuntu 11.10 does not support, by default, the switching between integrated graphics and Nvidia graphics.

Quick fix: to discard permanently the integrated graphics, in the BiOS (F1 at computer startup), pick Config > Graphics > Discrete. Problem: heavier battery consumption, and Windows, which is has no problem using Optimus, will now be forced to use only Nvidia. Not good.

Fixing the problem: Bumblebee

Bumblebee is a solution for Optimus on Ubuntu, and they have a tutorial to set it up. But in case it one day disappears, here are the steps.

1) Check hybrid config and support

Determine graphics card(s): lspci | grep VGA

00:02.0 VGA compatible controller: Intel Corporation Core Processor Integrated Graphics Controller (rev 02)
01:00.0 VGA compatible controller: nVidia Corporation GT218 [NVS 3100M] (rev ff)

So there's an Intel integrated card and an Nvidia GT218 card: that's a hybrid configuration. Check Nouveau's supported cards to see if the opensource driver supports your card. If it does not, maybe the proprietary Nvidia driver supports it?
Anyway, the next step is to check that the Nvidia card is not doing its part; run glxspheres. This outputs:

Polygons in scene: 62464
Visual ID of window: 0x97
Context is Direct
OpenGL Renderer: Mesa DRI Intel(R) Ironlake Mobile
21.494593 frames/sec - 23.987966 Mpixels/sec

21 frames/sec is quite lame, so Nvidia is most likely not picked.

2) Installing Bumblebee 3.0 (as of February 2012)

sudo add-apt-repository ppa:bumblebee/stable
sudo apt-get update
sudo apt-get install bumblebee bumblebee-nvidia
sudo usermod -a -G bumblebee $USER
sudo reboot

3) Testing

Any program to be run with the Nvidia card should be prefixed by optirun; for instance, optirun glxspheres outputs:

Polygons in scene: 62464
Visual ID of window: 0x21
Context is Direct
OpenGL Renderer: NVS 3100M/PCI/SSE2
101.341234 frames/sec - 113.096817 Mpixels/sec

Although it takes a tiny bit of delay for the program to start, it's much better than the 21 fps of earlier. Running optirun -c yuv glxspheres shows even better performance (145 FPS). But the CPU consumption remains high: Bumblebee only has the Nvidia card compute 60 frames per sec and send those frames to the Intel card anyway.

References

• Unity and games don't work on new Thinkpad T420
• Thinkpad T520 - problem detecting nvidia card after enabling it after installation
• Bumblebee FAQ explains how the two cards share a frame buffer.
• .desktop files: To launch an application using optirun without having to type it in a terminal, edit the .desktop file of that app, located globally at /usr/share/applications and locally at ~/.local/share/applications (make the folder if it does not exist).

Scaling League of Legends

Notes from a 2011 Qcon talk about scaling the non-gaming server side of League of Legends. They are not worried about persistence during a game, but rather in the match-making, lobby, or store. They have soft real-time requirements: not the order of 10ms, more the order of a few seconds. [Twitter and Facebook are soft RT too]

Scaling

Scalability: it's easier to constrain what the logic developers are allowed to do, than to define what they are not allowed to do. Examples: Map/Reduce is a whole paradigm (you have to make your logic fit into a map() and a reduce()), NoSQL's unstructured data is a double-edge sword (you lose the ability to join, but queries come back faster), and when you're partitioned, you pick to be either atomic/consistent or available

46:50: Scaling should be dynamic/elastic; you need cluster recomposition and stateless growth patterns. Hence the system should be dynamically configurable. On the fly, you should be able to adjust the thread pool size, add/remove roles to machines, and switch logic or system algorithms.

Food for thought: list all the benefits/tricks a load balancer can provide to your system.

Caching

Caching provides flexibility: failovers, distribution of workload (hot code updates or restarts). Coherence is a distributed cache used between Hibernate and the DAO layer as "cache-through". If the DAO asks Coherence and there's a cache miss, then Coherence asks Hibernate (itself using a Coherence cache, or calling MySQL over the network if cache miss).

24:00: How to be sure that cache and DB are consistent? Do not cache! Query the DB directly, latency of few sec is OK for soft RT.

11:30: Serialize the work, not the data. It's faster to serialize the work to the data, than to unserialize the data, work on it, then serialize the result. Avoid moving the data all over the network towards where the process is. It's also easier to distribute the work to all the DB nodes than to send to/receive from all the nodes.
The objects sent on network between server and DB should be small: if you have to edit only one field, you should not have to send a big object of 1MB.

Logging and Testing

42:30: They log each function call with how long it took; overhead of 1% performance, but huge value if able to graph/plot the logs. Compare the average call duration in the last few minutes to the usual average to detect problems.

17:15: Keep in mind that the code will be used/executed in a data center, not on your laptop. 51:25: They use EC2 for load testing. 1000 threads per node, each thread simulating 1 user. Realistic because not all clients (threads) are same speed in real-life, and EC2 network is not always the best/reliable. It's not the most performant, but it looks like a quick-and-dirty way to load test. One of their scale testing environment has more than 50 machines.

Wisdom of the crowd

The term wisdom of the crowd has been popularized by Surowiecki in his 2004 book of the same name. Crowds, he argues, are better than a single entity at processing information, coordinating (eg optimizing pavement flow) and cooperating (local networks of trust). Four criteria for a crowd to be wise are:

• diversity of opinion
• independence
• decentralization/localization
• aggregation, ie combining private thoughts into collective decisions

Surowiecki's book deals with our society, economics and sociology. The wisdom of the crowd paradigm can also be applied to various domains of computer science.

Domain	Example	What it's not about
Machine Learning	State-of-the-art classifiers are boosted random forests. Build many decision trees taking random features and a random part of the whole data set (bootstrapping). In the end, aggregate all of them (bagging).	It's not about having a complex and smart model, it's about having millions of "slightly better than random" trees combined together, reducing the variance of the model.
Information Retrieval	Google uses MapReduce for data processing. Separate your algorithm in small elementary treatments so that it can scale. The more hardware, the faster.	It's not about having a smart and complex algorithm that needs to have 64G of RAM, it's about having many second-hand machines doing an elementary job in a pipelined process, reducing the reliability on a particular machine.

In the case of MMOG, the dominant paradigm is a tightly-coupled client-server architecture. And although server hardware scales, it's still rudimentary: the cutting in shards is often done manually and there's rarely a dynamic allocation of ressources to a particular world region (although that would be helpful in WoW in case of gnome warrior demonstrations). The coupling between client and server has a lot of limits. There are ways to prevent cheating in peer-to-peer MMOG architectures, so why is peer-to-peer still considered a joke?

[Conf] Notes from an NSF workshop about CGVW

This workshop focused on computer games and virtual worlds (CGVW) and gathered researchers in the STEM field and arts.

Notable positions

Some interesting points from position speakers.

Speaker	Desc.
Boellstorff	WoW is not overstudied, but there is a hype cycle. Making a distinction between computer games and virtual worlds. Impossible to research the future.
Hayes	Learning is part problem solving (provided by current computer games) and part sociocultural (provided by multiuser virtual worlds).
Kesselman	WoW is not revolutionary, it is just polish and history. Limited resources for many players is a bad game mechanic, it is frustrating.
Wright	There are few social theories/framwework to explain why VW are so popular. It may be worth studying the impact of CGVW software on exclusion, relations between children and adults, cooperation and conflicts between players, and the reproduction of real-life social inequities in CGVW.
White	Scripting languages can be used by professional game designers; in that case, it is pre-architected. If it is UGC, it is certainly buggy and possibly harmful. In some cases, the system limits the design (ex: 8bit consoles, Racing the Beam from Bogost) but in others, current designs do not yet use the full potential of the systems on which they are built (ex: augmented reality is still nascent).
Wardrip-Fruin	Close-reading (in media studies) goes hand-in-hand with rapid and agile prototyping.

Working Groups

I found the 6 working groups to reflect well the domains currently implied in CGVW research. Here they are, taken from the workshop slides.

Title	Desc.
Advanced GGVW Technologies	AI, scripting, narrative and emergent systems, procedural and non-procedural content generation, avatar generation and customization, world building kits, etc.
Anthropological, Behavioral, Sociological Studies of CGVW	ethnographic studies of CGVW, work-versus-play or work-as-play or play-as-work, patterns of migration across CGVW, CGVW in complex enterprise settings, research methods for studying CGVW,
CGVW for Science, Health, Environment, Energy, Defense	CGVW as research tools or infrastructure for R&D in other scientific, industrial, or government domains, etc.
Education and Learning with CGVW	how CGVW facilitate or inhibit learning in formal or informal education settings, play as learning, CGVW for STEM and Humanities learning, etc.
CGVW Systems Technologies	multi-core and many core processors, computer graphics hardware and software, networking, databases, language design, sensors, etc.
Media, History, Culture and Art of CGVW	CGVW as media, art, literature and expressive forms of social critique; new literacies, creativity with or through CGVW, etc.

Video games birth - 2/2

This article is the second part of the origins of video games. Here, I detail the 1965 - 1977 period relatively to arcade, console and mainframe video games. Many more games than those I mention have been published in this period. However, I try to mention only the ones I find the most interesting and innovative in each of the arcade, console and mainframe video game fields.

Arcade video games

The first arcade games were coin-operated. Arcade controllers were very similar to the 1960's controllers: each player had a knob and a few buttons.

Galaxy Game was released in 1971. I could not find any screenshot or video of it. Computer Space was released two months after Galaxy Game in 1971. The video of the game shows how similar it was to Spacewar! from 1961. Both Galaxy Game and Computer Space were 2D space shooters. In 10 years, not much had evolved, but the shmup genre was certainly defined. I think the Cold War space race context influenced a lot the design of video games. Anyway, Pong was published by Atari in 1972. The video game sport genre began.

Gun Fight was published in 1975. Each of the two players controls a cowboy and shoots at the other. Unlike Spacewar! or the other shmups, bullets are limited in number and bounce against the screen. I could find a few screenshots of Gran Trak 10, the first racing game released in 1974. Gran Trak used ROM to store the game data. People played versus an AI. The player could use a steering wheel, two foot pedals, a gear shifter and a knob. Sprint 2 was a racing game published in 1976. This arcade game added two AI cars and more diverse tracks, but the controller stayed the same as Gran Trak 10. Night Driver, a racing arcade game released in 1976, was the first game to show the world in a first-person view. As seen at the end of this video, the speed of the car increases gradually to make the game more difficult for the player.

Breakout was released in May 1976. You can see the video of its port to the VCS 2600. In the original gameplay, orange blocks speed the ball. Each level increases the speed of the ball and the difficulty of the game.

Home consoles

Before 1977, many home consoles embedded the games inside the hardware - few consoles used ROM cartridge. So it makes sense to analyze the consoles as a whole. I found many information about first-gen consoles in this article.

Magnavox Odissey was the first home console. It was released in 1972 and did not use cartridge (the 1978 upgrade of Odissey has cartridges). Odyssey 200 was a 1975 upgrade of the original Odissey console. It contained three built-in variations of Pong.

Pong was ported from arcade to home in 1975 in the "Atari Pong" home console. This console had the game built-in (there was no cartridge). It took a year for Atari to find a retailer interested in funding the fabrication of the home console. Pong was nevertheless a success on Christmas 1975. In June 1976, Magnavox filed a lawsuit against Atari for patent infringement. Like the Pong console, the APF TV Fun released in 1976 had a monaural sound channel. Like Pong, the APF TV Fun had two knobs and several buttons. Four games were built-in: tennis, hockey, squash and single handball.

The Coleco Telstar was a first-gen console series starting in 1976. Its games were built-in Pong variants (hockey, handball, tennis and Basque Pelota) as well as Pinball games. Some 1978 upgrades had sound and games in color. One of the Telstar upgrades had text in French and English for the Canadian market.
The Color TV Game was a series of Nintendo consoles released in Japan only. Although second-generation consoles started to appear in the US around 1977, I think the Japanese market was at that time out of American console makers' reach. The CTG15 had the first controllers linked by a cable to the console, making the play experience more enjoyable. Games were built-in. Some were based on Atari's successes such as Pong or Breakout, but there was also a racing game.

Mainframes

There are several Mainframe games mentioned at wikipedia. I am sure some games are missing or have been forgotten since the 1970's. The mouse had been invented in 1963 and the ball mouse in 1972. Hence players could already use a mouse and a keyboard to play mainframe games on terminals.
These slides from Pamela Fox provided a lot of information (and screenshots).

PDP-10

PDP-10 games nearly always relied on text-based UI for the input and output. Sometimes, the possible player actions or game feedback were printed (on paper, at 10 or 30 characters per second). Lunar Lander appeared in 1969 (on PDP-8). It was apparently textual (I could not find any screenshot) and was ported to a graphic terminal of PDP-10 in 1973. The company who made the graphic terminal commissioned the game to be written in 1973 as a demonstration of the capabilities of the terminal. The user input was taken from a light pen. Starting in 1971, Don Daglow wrote several games during his college years. Baseball was coded in 1971. No screenshots or videos were found. Then Star Trek in 1972 and Dungeon in 1975. Dungeon was the first RPG and it was multiplayer. Colossal Cave Adventure (or simply, Adventure) was an adventure game created in 1976. The game shows both recreational and educative elements.

PLATO

The TUTOR language was introduced in 1967 for PLATO III. TUTOR made it possible to code PLATO games. The third slide of How College Students Influenced Gaming shows a quite exhaustive timeline of the PLATO games. Users had only a keyboard - no mouse - to interact with a PLATO terminal.

pedit5 was coded in 1974. It was the first dungeon crawler game and it was using some of the Dungeon and Dragon rules. The name of the game, pedit5, was deliberately misleading in order to hide it from administrators who had forbidden them. Following the same naming strategy, another dungeon crawler called m199h was coded in 1974 (and deleted). dnd was allowed to stay on the PLATO mainframe by system administrators in 1975. Before that, at least 7 major versions of dnd [...] were deleted from the PLATO system for being illicit games on computer system designed solely for education. In dnd players could buy items from vendors and face the first boss monster of video games (a dragon).

Empire appeared in 1973. The game was accepted by mainframe administrators because it was part of a class work. Up to 30 players could play the same game of Empire "online". It has been upgraded regularly until 1980. The game looks a lot like Spacewar! - spaceships attacking each other. Nevertheless, the game mechanics were more complex as teams could use spaceships with different characteristics ("strong but slow" versus "weak but fast"), and spaceships had two different weapons on-board.

Spasim was a 32-player 3D networked space shooter coded in 1974 and inspired by Star-Trek (and previously mentioned PLATO game Empire). In Panther (1975) players were driving tanks. The terrain in Panther was generated randomly.

Other mainframes

Several other important games were released on other mainframes than PDP-10 and PLATO. Highnoon was written in BASIC in 1970. You can play its emulation. Hunt the Wumpus was coded in 1972 also in BASIC. It was a text-based maze adventure game. Later implementations had graphics (see this video) but the first version of the game was totally textual. Maze War was done in 1974. Two players (connected by an Ethernet cable) wandered in a 3D maze and tried to shoot at each other. It was the first FPS (see the gameplay on a Xerox machine). The Oregon trail was released in 1974 as well. The goal of the game was to teach children about the 19th century pioneer life. In fact, the gameplay is mostly about resource management.

Video games birth - 1/2

The quite thorough history of video games given in this article starts with the first video games in the late 1940's and ends in 1977. 1977 is a pivotal year for three reasons. First, second generation consoles appeared - with cartridges! Second, the Golden age of arcade video games started. Third, the home computer entered the market. The simultaneous improvements made in these three different hardwares definitely triggered the adoption of video games in our modern society.

It makes sense to analyze the gameplay and graphics of early video games separately. Gameplay and graphics certainly limit, extend or complement each other. However I think the progress made in each of them were made independently. Video game graphics did not improve thanks to gameplay innovations. New gameplays did not appear specifically because developers/researchers found new ways to display objects on a screen. Looking at the controllers also helps to understand which physical affordances the players could have.

1945 - 1965: Origins

The first video games were, like the first movies, technological proofs of concepts. They relied on electronical/electrical engineering prowesses of the time. One could argue that these games were more about cathode ray tube hacks than proper computer logic and graphics. Wikipedia mentions the 1947 Cathode Ray Tube Amusement Device and the 1951 Nimrod as precursors of video games.

OXO (1952) was the first video game, according to students from CMU. It was a version of tic-tac-toe and was only playable on the Cambridge University EDSAC computer. This video shows how the game can be played in an EDSAC emulator. One can measure how clumsy the use of a rotary telephone controller was: the player had to dial the number of the location where he/she wanted to put his/her symbol instead of simply pointing at the location on the screen.

Tennis for two (1958) is a two-player tennis game on oscilloscope. The physicist Higinbotham, creator of the game, reported: I knew from past visitors days that people were not much interested in static exhibits, so for that year. I came up with an idea for a hands-on display – a video tennis game. A video of two people playing the game shows basic elements of gameplay. Around 0:40, the right player seems to dominate the player on the left. The game was only playable on the Brookhaven National Laboratory device, hence hundreds of people lined up to play “Tennis for Two”. For each player, the controller consisted of a knob (for the direction) and a button (to hit the ball).

Other games followed, all developed in universities or by true hackers and which platform were university computers. Examples are Mouse in the Maze (1959), Spacewar! (1962) or the PLATO platform (early 1960's).

The second part of the early video game history deals with mainframes, arcade and consoles.

[Literature] Fundamentals of Game Design, ch3: Game concepts

In order to answer the questions "Why would anyone want to play this game?" and "What's going to make someone buy this game instead of another?", a game concept contains to a minimum:

high-concept statement

description of the game in 2 or 3 sentences

player's role(s) in the game

describe the avatar. Think about player's actions first, not on the story. The more obvious the role, the easier players or publishers can decide if they buy it.

primary gameplay mode

with perspective, interaction model and challenges

genre

category of games characterized by a particular set of challenges regardless of game-world content. Examples are action, strategy, RPG, simulation, sport, tycoon, adventure, puzzle. Mixes are possible. If new genre, describe why.

target audience

Who am I trying to entertain?. Avoid repelling people who might be attracted by the game. Examples of player populations: male/female, children/adults, different cultures, different (dis)abilities, [hardcore/casual].
Localization not only translates but also takes into account other cultures' particularities.

hardware and system requirements

console => TV => 2-3 people around at the same time => small-scale multiplayer game. Local play is more common than networked play [is it still currently the case with systems such as XBLA?]
PC = small and personal high-res display, personal, the PC player can write thanks to the keyboard
pocket console: small cartridges => less room to store audio or video data like cinematics
mobile phones: wireless => can compete against other people
plane seats, gambling machines and arcade machines are niche devices containing games

licenses

if any

competition modes

(singe, dual, mutliplayer, coop, ...)

progress and synopsis

but not a full story

short game world description

[Literature] Network Infrastructure for Massively Distributed Games

by Daniel Bauer et al. 2002

Motivation

Client-Server (CS) Architecture: According to the authors, an Apache server on a usual computer using a Linux OS connected to a Gigabit Ethernet can handle roughly 2000 256-byte HTTP transactions per second. Server farms are said to handle a number of connections on the same order of magnitude. The authors also mention that whereas network bandwidth is abundant, the bottlenecks of such systems are CPU cycles, memory bandwidth, and server I/O. They conclude that server farms handling loads greater than 10⁵ HTTP requests per second currently [in 2002] are infeasible with existing technology and, by extension, so are million-person games requiring as little as a single event per minute. They also take Everquest as an example: Although Everquest claims that tens of thousands of people can participate simultaneously, [...] Everquest is better thought of as 40 independent instances of the same game, each of which handles about 2000 playersEven if this paper was published in 2002, I think what they wrote is still accurate.

Peer-to-Peer (P2P) Architecture: Scalability is limited by the computational power of the weakest peer, because each peer needs to run the complete simulation. Therefore, the authors suggest a hybrid approach to overcome the scalability problems.

Proposed network-level solution: booster boxes

The authors start with the assumption that not all the information the clients send to the server is relevant. The server often sends the same packets to different clients (for instance, in a PVP zone, the death of a player will be communicated to all the players who currently see the dead player). To solve this problem, booster boxes can be set up between ISP Access Routers and Edge Routers. They have 4 roles:

• Caching non-real-time information
• Aggregation of redundant events
• Filtering of no-longer relevant events
• Routing packets to the appropriate server(s)

Booster box architecture

Data layer: for the bulk of traffic, booster boxes behave like ordinary level-2 forwarding devices, e.g. like ethernet switches. The data layer must be able to handle packet forwarding at speeds equivalent to the port of a residential access router, i.e. in the range of 155Mbits/s to 1Gbits/s and still has to process, copy or divert packets to the booster layer. The authors explain that a pure hardware solution is not flexible enough and a pure software solution is not able to handle such line speeds, that is why they introduce Network Processors (NP). A NP is a general purpose processor with access to many network-specific co-processors performing tasks such as checksum generation, table look up and header comparison. They suggest writing the network-forwarding code in C and load this code in the processor.

Booster layer: application-level layer. A Booster Library contains the API through which the boosters can call the data-layer operations (ie copy, divert, pass through, forward, ...). Boosters' code can be executed either on a general-purpose CPU or on the NP (or on a combination of the 2). Boosters can perform tasks independently or be coordinated by the Booster Control Point to work together. Another role of the Booster Control Point is to establish a Quality of Service overlay network between booster boxes. This Booser Overlay Network (BON) can circumvent several network problems that I have not fully understood yet. BON uses its own addressing schemes and packets eventually exchanged between booster boxes and servers contain a BON header (a BON packet is encapsulated in an IP packet).

Examples

Large Interactive Game Show: a TV program asks a question, spectators send their answer to the TV server (on the Internet). The authors pretend their system reduces the server's load exponentially.

Large Virtual World: The dotted arrows in the figure nearby shows how information comes from a player to the server. A white player sends an event to the closest booster box (in the network cloud). The correct server receives the event notification from the booster box. The solid arrows show how the server answers to this information: all the booster boxes to which white players are connected receive the update and forward it to their own white players.
Remark: in the case of a server-wide event such as a GM broadcast, the white game server will have somehow to tell the black game server to forward the information.
Interestingly, the authors suggest creating a game transport protocol in which the virtual location is encoded independently of the particular game, bringing the advantage that a game booster could to a large extent be independent of the game. To my mind, this idea is nice for ISP because they will rent their booster boxes to MMOG companies, but MMOG companies will have to follow booster box norms. I do not think there is currently any consortium able to establish protocol norms on MMOG...

See also: Understanding Network Processors by Shah.