Doing the Jitterbug: Lag, Latency, Jitter and Throughput and How They Affect Online Gaming (Part I)

Consistency: In an ideal online online gaming world, every player in the game would see the same consistent game world, and every client of a game server would have access to exactly the same game state information at any given instant. No player would suffer from seeing actions in the game world at a later time than other players, or losing a shooting duel because the opponent has a faster, lower lower latency connection to the game server. In the real world, this is of course impossible to achieve with existing technology.

Perhaps the greatest impediment to reaching this goal is caused by the vagaries of the underlying infrastructure that provides the communication between the game clients and servers: the Internet. The path to the goal of perfection is washed away by two primary effects in game communication over the Internet:

• Throughput limitations - the connection between server and client has some maximum throughput.
• Network delays - even with unlimited throughput, server messages do not arrive instantly.

The first, throughput limitations (bandwidth), means that the game state transmitted to game clients is at best a sample, or approximation, of the actual complete game world. The bandwidth and processing power simply do not exist in typical environments to allow all of the information required to completely represent the game state to be communicated. Just as the typical music CD has less information than the master recording from which it is made due to the sampling of the audio signal to match the constraints of the CD audio format, so too do the messages that the game clients and servers interchange. By careful crafting of the structure of the messages used, game developers can provide an approximation that is sufficient for realistic game play, so long as the minimum throughput requirements of the game are met.

The second, network delays, means that regardless of the available bandwidth, there is always a delay between the servers sending a message and the client receiving it and vice versa. In effect, the information in the message is time-shifted to a later wall-clock time: an event may happen at actual time X, but by the time the client receives the message of the event, the actual time is perhaps X+2.  When the possibility of time-shifting is present, the possibility of causality violations rears its head: events may seem to occur in the wrong order for game clients. For example, a player may open a door, but that door isn't there in the game world because it was destroyed by a grenade (and seen as such by another online player), an event that the client component of the first player was not yet aware of due to the delays in message arrival. Other players might see the first player's avatar "opening" a door that isn't even there.

We will review the details of these problems, the effect they have for players of online games, and the techniques commonly used to minimize the unfairness between players that can result if these problems are left untreated. We will cover the definitions and details of the problems in this blog entry, with part II to cover the effects these have on players and the techniques used in games to minimize their impact.

Throughput and Latency: 

The throughput requirements for online PC games vary widely, but in general are far below the available bandwidth of the typical client (we will only be discussing the client side and impact, obviously, running a server for a game dictates a much higher aggregate bandwidth requirement). Recent studies (Feng 2002 & 2005) using games such as Counter-Strike, Day of Defeat, Medal of Honor: Allied Assault, and Unreal Tournament 2003 showed a client load ranging from 6400bps to 8000bps for client to server packets and 20800bps to 36000bps for server to client communications. These are far below even lower-tired ISP services typically used by online gamers.

Congestion of the network may cause throughput to drop to a level that is insufficient for smooth game play. Congestion typically occurs in one of three primary areas: the last mile near the user, the middle or Internet cloud, and the last mile on the server side.

In the case of the user-side congestion, they may simply have a service tier that does not provide sufficient bandwidth. This can of course be remedied with a service upgrade. At a minimum, a service with 600kbps down and 50kbps up should suffice. The faster down link speed while not strictly required to play online will ensure faster downloads of game items such as server hosted maps.

The gamer should also ensure that other activities on their local network are not causing congestion. Other users gaming, streaming audio or video, using services such as torrents, etc. can all adversely affect the overall available broadband bandwidth for the player.

Problems in the last mile on the server side can be caused by too many players joining a specific game server, causing a bottleneck on the network link to that server. Game servers typically employ a player count limit to avoid this occurrence. Any other congestion in this link of the game communication network (router congestion or failure modes, etc.) is likely to be out of the control of both the player and their server provider.

Congestion in the Internet cloud is usually temporal: Perhaps a widely viewed sporting event is viewed by large numbers via streaming technologies. As with most last mile issues on the server side, these are out of the control of the server provider and game player. In cases where Internet cloud congestion is the cause of game play issues, the only remedy is to wait until the problem "goes away".

Any kind of congestion, whatever the cause, can cause throughput degradation that may adversely affect the consistency of game play. If the game client is starved of message packets due to actual throughput issues or congestion related throughput issues, the synchronization between the client and server will be lost, resulting in "laggy" game play, "rubber-banding", and other temporal effects. Severe throughput problems can result in the game client "giving up" and disconnecting from the game server.

There is no accepted and commonly agreed upon definition for latency (Delaney 2006). The latency of a network is commonly measured using the ping command. This however measures not the one-way trip from client to server or vice versa, but instead measures the round-trip time. Since the routes from client to server and server to client are usually asymmetric, simply guessing at half the value arrived at from a ping measurement may be grossly inaccurate, and provide incorrect information for making client and server timing decisions. In addition, such a measurement does not account for processing and other delays at the client and server endpoints.

A more useful measurement is the endpoint-to-endpoint measurement of latency that accounts for time needed for client-side processing, bi-directional network delay, and server-side processing (Stead 2008).
This is important: It has been found in studies that much of the delay in the overall game processing loop is caused by the game client handling and processing of messages.

The sources of network delay fall into four basic categories (Kurose 2009):

• Transmission delay: Packet time to physical layer.
• Queuing delay: Packet time waiting to be sent to a link.
• Processing delay: Packet time spent at routers along the route.
• Propagation delay: Packet time in physical link (bounded by the speed of light).

Transmission delay occurs during the movement of the packet to a physical link. For example, if you are using a 1Mbps WAN connection, each bit takes 1 µs to send, and a 500 byte packet takes 0.5 ms.

Queuing delay can occur at routers along the path of the packets. If a router is is under heavy utilization or the required outbound link is busy, the packet will be queued into a buffer until it can be sent.

Processing delay is also incurred at routers, since these must handle routing table checks, possible firewall rule application, packet check sum and error checking.

Lastly, even if  delays in packet transmission due to processing overhead , transmission delays and queuing delays could be eliminated, we are still bound by the laws of physics. No signal can travel faster than light (2.998x10^8 m/s in vacuo). Speeds in actual transmission media will be lower (e.g. 1.949x10^8 m/s in typical optical fiber, significantly lower for twisted-pair copper). This means we are bounded by an absolute minimum round-trip latency of roughly 2 ms client endpoint to server endpoint and back for a client to server distance of 200 km.

Jitter:

Jitter is the variation in network latency caused by changes in the state of the network. Packets that comprise the communication between the game client and server seldom follow the exact same route endpoint to endpoint. This can cause packets to have different latencies. In addition, network congestion can result in changes in the routing and router buffering behavior, changing the queuing delays for the affected routers.

We can visualize this effect with the aid of a diagram.

In this diagram, packets are sent from the server represented by the lower solid line at regular intervals (time ticks) to the client represented by the upper solid line. If we were able to construct a network with none of the four causes of latency outlined, and in addition discovered a way to violate the laws of physics and send our packets with infinite speed, the green line results: there is no latency between the server sending a packet and the client receiving it.

The more realistic example is represented by the blue line, which shows the slight delay the packet experiences traversing the network from the server to the client. The orange line depicts the next packet in the sequence, which is delayed by the same amount as the packet of the blue line. In the ideal world, the latency from the server to client and vice versa would exhibit this constancy. This would simplify any "compensation" for latency the game developers might wish to utilize, and even without compensation, humans tend to have an easier time adapting to latency in a game when it is relatively constant, even when the latency is rather large (Claypool 2006).

More typically, the game packets experience changes in latency from routing and congestion problems. This is illustrated with the final train of three packets colored red, magenta, and dark brick red. For these packets, it is clear any semblance of packet arrival at relatively regular time ticks is completely lost. There is currently no standard measure for jitter in game traffic. Jitter in networks tends to exhibit randomness, but can be characterized by a Gaussian distribution for inter-packet arrival times (Perkins 2003). Since we are bounded by conditions such as some minimal amounts of processing, queuing, and transmission delay in addition to the absolute bound due to the propagation delay, the actual distribution is biased: there is some absolute minimum that can be realized, and network congestion and related issues can cause delays to be skewed. This is illustrated in the following graph.

Graph of Gaussian (Red) and skewed/biased distributions (Blue) for inter-packet arrival times.

The fit is sufficient that we can use this model for predicting the likelihood of specific inter-packet times for use in the design of compensatory mechanisms for games.

In part II of Doing the Jitterbug, we will investigate what effects these issues have on game play, and what techniques can be used to minimize these effects.

Interested readers can find references for further study after the jump break.

See Your Way Out - Using mathematics and image processing to quickly pathfind

As I outlined in my blog entry Earning Your Pathfinding Merit Badge: How Game Characters Navigate Their Game World, pathfinding (or path finding) is a critical component in PC games.

Pathfinding refers to the techniques used in games to allow Non-Player Characters (NPC) to navigate the game world.

Most games use some variant of Dijkstra's algorithm, a technique pioneered by Dutch computer scientist Edsger Dijkstra. Dijkstra's algorithm produces a shortest path tree for its result by solving the shortest path problem for a graph with non-negative edge length (the distance between the vertices of the graph are never negative).  It is one of a myriad of graph search (or graph traversal) algorithms.

Dijkstra's algorithm is often used in routing problems, such as network routing protocols, most notably IS-IS and OSPF (Open Shortest Path First), and transportation map shortest path solutions.

Perhaps the most commonly used variant in games is the A* search algorithm. Instead of using the distance from the start node (vertex) of the graph, this variant chooses nodes based on an estimate of the distance from the start node to the destination node. This estimate is formed by adding the known distance to the start node to a guess of the distance to the destination node. This guess is called the heuristic of the algorithm.

By utilizing such a technique, the A* algorithm provides improved performance when compare to the behavior of Dijkstra's algorithm. If the guess is set to zero, the two algorithms are equivalent. When the guess is made positive but less than the true distance to the goal, A* continues to find optimal paths, but because fewer nodes are examined, performance is improved. When the guess exactly matches the actual distance, A* finds the optimal path and does so while examining the minimal possible number of nodes. If the guess is increased yet more, A* continues to find paths, examining fewer nodes still, but no longer guaranteeing an optimal path. In most games, since it is not practical to guarantee a correct heuristic at all times, this is acceptable due to the increase in algorithm performance.

With extremely complex environments (like the maze we'll be looking at), these algorithms can prove to be impractical, with other solutions preferred. A nice overview of such issues can be seen at Sean Barrett's Path Finding blog entry.

I'm going to go through a technique that is conceptually beautiful to me: Using image processing to solve a maze path finding problem.

I'm sure every reader is familiar with mazes. Perhaps some of you have found yourself lost in a particularly fiendish one, having to ring the nearby "rescue bell'!

I'll be using the superb Matlab system from Mathworks.

From their web site: "MATLAB® is a high-level language and interactive environment that enables you to perform computationally intensive tasks faster than with traditional programming languages such as C, C++, and Fortran." 

It most certainly is! Along with the equally superb Mathematica it is the staple of my tool set for doing complex mathematical programming, analysis, graphing, and data manipulation. These two products would be my desert island choices to take with me if I could only have two programming environments.

I'll be using the Matlab image processing package DIPimage, developed by Cris Luengo, Professor in multidimensional image analysis at the Swedish University of Agricultural Sciences and Uppsala University. I've borrowed copiously from his examples. Users of Matlab can obtain a license for DIPimage free of charge (normally a $3200.00 and up cost) for academic, non-commercial use. I highly recommend it!

Let's begin.

We will start with the following simple (no holes, loops, etc.) maze:

Note the entry and exit apertures in the lower right and upper right areas of the outer call of the maze. Try solving it manually if you'd like!

Next, we use our image processing functions to convert our maze to grey-valued, and threshold it to obtain the binary image. The maze walls are now shown in red, with the path areas in black:

maze = colorspace(inputmaze,'grey');
maze = ~threshold(maze)

We use image processing functions to "label" any found walls and show them with differing colors. In this case, we clearly see the maze comprises two walls:

maze = label(maze);
dipshow(maze*2,'labels')

From this we can easily see the path is the area between the two maze walls. By applying a little mathematical morphology, we can isolate one of the walls:

path = maze==1

We then can do a binary dilation on the wall and fill in any holes (effectively a smearing of the wall):

pathwidth = 5;
path = bdilation(path,pathwidth);
path = fillholes(path)

Next, let us erode this smeared version of the wall. This operation effectively "shrinks" the wall by subtracting components smaller than the erosion radius and in the case of a binary image such as ours by removing the perimeter pixels. We then take the difference of the eroded image and the original image:
 
path = path - berosion(path,pathwidth);

Finally, overlaying the result with our original maze shows our desired goal:

overlay(inputmaze,path)

I think you'll agree, a most fascinating use of tools to solve a problem from a domain you'd not likely think to be image processing.

The interested reader can find details of techniques such as these in these excellent references:
 
The Image Processing Handbook by John C. Russ
 
Digital Image Processing Using MATLAB by Rafael C. Gonzalez
 
Feature Extraction & Image Processing by Mark Nixon
 
Happy trails to you!

Bar Bets and Thermonuclear Bombs

Stanislaw Ulam, along with Edward Teller, fathered the thermonuclear bomb or Hydrogen Bomb as it is more commonly known. Ulam is one of the many great mathematical minds of Polish descent. Known as a rather cantankerous fellow, he made major contributions in the fields of Set Theory, Topology, Ergodic Theory, Biology and Physics. A true polymath.

While residing in the United States during World War II, Ulam was invited to join a secret project in New Mexico by his close friend John von Neumann, one of the greatest mathematicians in history and an epic contributor to the the fields of mathematics, economics, set theory, game theory, logic, quantum mechanics, computer science and nuclear physics. Neumann created the field of Cellular Automata (see Life Goes On: Further Ruminations on Conway's Game of Life for examples) with a pencil and graph paper as tools to build the first self-replicating automata.

With his typical scientific curiosity, Ulam checked out a book on New Mexico from the University of Wisconsin–Madison library, the campus where he was a faculty member at the time. In it, he found the names of all those that had previously disappeared from the campus on the check-out card. He subsequently joined the  Manhattan Project at Los Alamos, where the development of the first atomic bomb was progressing.

As the atomic bomb project was nearing fruition, Teller had turned his attention to the creation of a vastly more powerful tool of destruction, the Hydrogen Bomb, or "Super" as it came to be known. Ulam, made aware of the "super", showed that Teller's design was faulty and devised a much more suitable design. While the design took on the moniker of "the Teller-Ulam design", most involved in the project credit Ulam with being the true father of modern thermonuclear devices, as contrasted to Teller's rumored contribution as the character model for Dr. Strangelove in the eponymous film by Stanley Kubrick.

A particularly interesting contribution of Ulam's to mathematics and topology specifically is the Borsuk-Ulam theorem, first conjectured by Ulam and later proved by Karol Borsuk in 1933. The theorem is stated as follows:

Call a continuous map f:Sm→  Sn antipode preserving if f(−x)=−f(x) for all x∈  Sm

Theorem: There exists no continuous map f:Sn→ Sn−1 which is antipode preserving for n > 0

In English, this states that any continuous function from an n-sphere to Euclidean n-space maps some pair of antipodal points to the same point.

In even more plain English, I'll try to explain why this results in things that can sound incredulous to most non-mathematicians, and why it provides for the opportunity of a "bar bet" that at the very least might get you a free beer.

Take the circle above with the two labeled points A and B. This will be the only drawing here, to start us off. I'm no artist, and my meager attempts at drawings for the steps would likely confuse rather than help. Get out your pencil and paper, put on your thinking caps, and follow along!

Imagine this is a line drawn around a sphere, such as the idealized Earth. The equator is an example of such a line. In this case, we only require that it is maximal in size, that is, it is drawn around the Earth in a way that it is as large as it can be, like the equator or any of the lines of longitude that run north to south on the globe.

You've perhaps heard the term "Great Circle" used for navigation. A Great Circle is a circle around the earth that is maximal. Any segment of such a circle that connects two points is the shortest distance between those points on the globe. So taking the great circle path is always the shortest route between points on the surface of the Earth.

A shape such as the circle we are using is known mathematically (at least by topologists) as a 1-sphere or Disc: it is a one dimensional surface embedded in two dimensional Euclidean space. What non-mathematicians call a sphere is known as a 2-sphere or ball: A two dimensional surface embedded in three dimensional Euclidean space.

We want to show that we can always find two points, opposite (antipodal) to each other on the planet, that have exactly the same temperature. If we find that points A and B in fact measure the same temperature for the circle we've drawn, we have made our point. But suppose the temperatures are different.

Let's call A the colder measurement point, and B the hotter measurement point. Now imagine moving the measuring points, keeping them diametrically opposed, around the circle until they have exchanged places. Let us assume that the measurements never share the same temperature. Because of this assumption, measurement point A must remain colder than measurement point B for the whole trip, and measurement point B must remain hotter than measurement point A.

But after rotating the measurement points 180°, we know that measurement point B must be measuring a colder temperature than measurement point A and vice versa. This contradicts our assumption, and by the mathematical technique of proof by contradiction we now know that there must have been some point along the path where measurement points A and B showed the same temperature.

The same proof technique can be extended to any 2-sphere/ball like the Earth. When moving to the higher dimensions, we are allowed more degrees of freedom in our chosen path for the antipodal points. We can choose any arbitrary meandering path, so long as the two measuring points remain antipodal.

Imagine we choose some path, again resulting in the exchanging of the positions of the two measurement points. By the same methods, we can see that again, there must be two antipodal points somewhere on that path that share the same measurement. This is critical to our emerging bar bet. This means that every path taken by measurement point A on it's way to measurement point B, with measurement point B following along by remaining diametrically opposed (antipodal) on the opposite site of the Earth must have a point where the two points shared the same temperature.

Let's consider the set of all possible pairs of antipodal points on the Earth with the same temperature. These points need not have the same temperatures, they must only have the same temperature as their matching antipodal point on the opposite side if the Earth to be a member of this special set.

You may be thinking that the result might be some myriad of dots scattered across the surface of the ball where the matching antipodal dot shares the same temperature. But this would be wrong!

If this was the case, we could always find some path from the original measurement point A to measurement point B without needing to touch any of the dots in the set. But as we have already shown, this set must contain a pair of the dots opposite each other on the Earth that share the same temperature along whatever path we take from A to B.

From this, we can make the conclusion that the set of dots must contain some set of dots that result in a continuous path dividing our ball (the Earth) into two sections, one containing the original measurement point A and the other containing measurement point B.

Now imagine applying the same line of thinking to this path, except we'll use some other continuous function such as barometric pressure. We pick two antipodal measurement points, call them C and D, and take our measurement. If the result is the same, we are finished showing the same fact that we proved for temperature holds true for barometric pressure. If they differ, we again let measurement point C follow the path to measurement point D, with point D following along on the opposite side of the globe. As with temperature, we will find some point along the path that has matching measurements for measurement points C and D.

But as we know, this point is on the path that contains all of the points where the temperature measurements are equal for the matching antipodal points of the path.

This means that that point, and its matching antipodal point, simultaneously have the same temperature and barometric pressure! Such points can always be shown to exist on a 2-sphere/ball, in our case the Earth, for any two continuous functions on its surface. We could have just as well used temperature and wind speed, wind speed and barometric pressure, etc.

The Borsuk-Ulman theorem proves that this is true for any pair of continuous functions on any 2-sphere! As can be seen in the theorem, it can be extended to any number of dimensions, with a corresponding increase in the number of continuous functions that will share a pair of antipodal points with equivalent values for each function.

This means for example that when that big plump helium-filled party balloon diffuses to death and is lying on the floor in a crumpled mass, there is a pair of points that were antipodal when the balloon was inflated that are now lying precisely on top of each other. Always.

So the next time you find yourself at the local watering hole with your bright companions, bet them a beer that there are two places on the opposite sides of the Earth, right now, that have exactly the same temperature and barometric pressure.

The bet is almost surely to be taken, and you'll earn yourself a free beer. Or maybe have one tossed at you!

While you might curse Ulam for his contributions to nuclear weaponry, remember to raise a toast to him before drinking your free beer! 

For more uses on this most interesting theorem, the book Using the Borsuk-Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry by Jiri Matousek and published by Springer provides a rewarding overview in an approachable text at the elementary level.

Excellent introductory topology books can be had in Topology by K. Jänich (also from Springer) and the classic Topology by James R. Munkres, published by Prentice Hall. 

Topology and Its Applications by William F. Basener published by Wiley provides more examples of useful results from general topology.

The Topology entry at Wolfram Mathworld provides a one page description of the field with copious references. You may find yourself wandering the site following one interesting link after another.

Earning Your Pathfinding Merit Badge: How Game Characters Navigate Their Game World. A µ post.

As most gamers probably have, I've pondered what mechanism must games use to allow the NPCs in the game to find their way around the game world. Why did games like F.E.A.R. and Halo seem to exhibit more realistic NPC movements?

I was exposed more deeply to the problem when I embarked on building a simple FPS game from scratch including AI, rendering, and netcode. I'd originally planned on a game that mirrored my neighborhood so my friends and I could run around familiar territory and maim each other. It ended up being a shoot-the-aliens sci-fi game: I'm no artist, and it was easier for me to make characters that didn't look like pale imitations of humans.

I'd pulled out all my references in preparation for writing a blog entry outlining the basics of the techniques used for pathfinding in games, when I happened upon a most excellent overview written by a game developer.

They do a much better job than I think I could have, you can view the overview at Fixing Pathfinding Once and For All at the Game/AI blog. Nice graphical explanations, with videos demonstrating the differences in pathfinding strategies.

Other useful background information can be found at A* Pathfinding for Beginners and a short entry at Wikipedia.

My own personal references are the superb four volumes of AI Game Programming Wisdom, and the equally excellent Game Programming Gems, now up to eight volumes with the most recent 2010 release. I was heavily influenced by reading the more academic treatments found in both Artificial Intelligence for Games by Ian Millington by and Behavioral Mathematics for Game AI by Dave Mark.

If you have any interest in how realistic character movement is accomplished in games, I highly recommend taking a look at the links, and if you decide to program your own, I can't think of better reference works than the book series I've used.

I Know What You Did Last Summer: Omniscient Debugging.

I've been doing some coding using the recently released Visual Studio 2010 from Microsoft to experiment with some of the new features and capabilities added since the release of version 2008, my day to day coding platform.

One of the more interesting and very useful features added (only in the Ultimate edition, unfortunately) is IntelliTrace historical debugging. The ability to debug an application while in effect manipulating time (going backwards in the execution history, for example) is known as Omniscient Debugging. The term is properly used when referring to the eponymous open source debugger by Bill Lewis, a computer scientist at Lambda Computer Science and Tufts University, but has become part of the vernacular and a synecdoche for such debuggers.

For readers that are not programmers, the "debugging" of programs is part of the life of any developer. Any sufficiently complex application is likely to have a few "bugs", cases where the expected behavior of the application is not observed to happen. This can be caused by any number of things, from incorrect specification of the design, mistakes in translating the design into program code, use cases that were not considered, bugs in the very tools used to produce the application, etc.

By way of example, let us consider the following tiny application (written in a form of psuedocode):

(define add_two_numbers using Number1, Number2 as (return Number1 * Number2))

The developer hands this off to the users, who start using the new routine add_two_numbers:

add_two_numbers 0,0  →  0

add_two_numbers 2,2  →  4

add_two_numbers 4,4  →  16

Oops! The first two test cases return the proper expected results, but the third returns 16 instead of the expected 8. In our admittedly trival example, we can see from visual inspection the programmer mistakenly put the multiplication operator "*" where the addition operator "+" should have been.

In real applications, mistakes may be buried in hundreds of thousands of lines of program code, and visual inspection is seldom practical. This is where the traditional debugger comes into play for the developer.

A debugger allows the programmer to observe the execution of the application under consideration, by showing exactly where in the execution stream the application is, and allowing the viewing and changing of variables and storage for the application, setting "breakpoints" where the programmer wishes to temporarily halt the execution,  stepping through the execution one step at a time, stopping when certain conditions are met, and in some cases even allowing the changing of the program's state.

Workspace for a typical debugger, in this case  the WinPDB debugger debugging itself.

These capabilities greatly assist the developer in the determination and correction of problem cases. In our example, one could imagine the developer has determined the problem lies in the add_two_numbers routine (imagine of course that the routine is sufficiently large that simple inspection is not an option). By utilizing the debugger, the developer could execute the application, requesting that execution be paused when the add_two_numbers routine is entered.

At that point, the developer could step through the execution of the routine, observing the flow through the source code step-by-step. The source of the problem would of course become apparent, and could be quickly remedied.

In the case of severe bugs, an application may "crash". In some cases, a "crash dump" will be produced by the execution environment. This contains information about the state of the application at the time of the crash. This information can be used by the developer with the debugger to analyze the state of the application when it crashed, and observer the contents of variables, the place in the source code the execution was at the moment of the crash, and basic information about the path by which the application came to that place.

A core problem with this model of debugging, however, is that detailed information about the execution path and program states leading up to the bug or crash is generally not available, even in a detailed crash dump file. This forces the developer to deduce where the problem might be and then test that hypothesis with the debugger by setting conditions and breakpoints while analyzing the application flow. This will usually lead to a more refined hypothesis, leading to further debugging, leading to a more refined hypothesis, nearly ad infinitum (or at least it can feel that way) until the problem is found. In cases where the bug is sporadic, the programmer may have difficulty even reproducing the problem.

This can be a very time consuming and taxing practice for the programmer involved!

Ideally, the programmer would be able to observe the state of execution for the application at any point in time of the execution lifetime.

That is precisely the capability that omniscient debugging brings to the tool set of the programmer. The concept of such historical debugging has been around for decades, but implementations proved impractical for most of this time. The first truly practical and usable example is surely the Omniscient Debugger (ODB) of Bill Lewis. A very detailed paper by Bill can be seen in Debugging Backwards in Time, and a most interesting video lecture of the same name is hosted by Google.  You can view these to garner details on how this functionality is achieved, with examples of the kinds of bugs that are vastly simpler to find by taking advantage of this kind of technology.

With Visual Studio 2010, Microsoft has incorporated and extended this capability and technology, calling it IntelliTrace. Supporting the historical debugging of managed C# and Visual Basic, with experimental support for F#, the product promises to make the work of developers on the Microsoft platform vastly more productive. Details of the new capabilities can be found in the MSDN articles Debugging With IntelliTrace and Debugging Applications with IntelliTrace.

Open source developers can avail themselves of historical debugging with the aforementioned ODB, TOD and GDB debuggers.

I know what you're thinking. More importantly, I know what you were thinking...

Life Goes On: Further Ruminations on Conway's Game of Life.

Conway's Game of Life, as I noted in an earlier blog entry An Alien Message? is an utterly fascinating example of Cellular Automata, capable of mind boggling complexity from an incredibly simple set of base rules.

As a further example of how the game can "compute" in the same way that a traditional computer and programming language can be used to execute programs that compute, I loaded up the recently created seed pattern by Jason Summers for a new type of "Primer" pattern. These patterns in the game will in some fashion "output" the sequence of prime numbers. This particular pattern emits the type of prime number most familiar to us: 2, 3, 5, 7, 11,13... ad infinitum.

Start the video, and observe the area where the "gate" is in the lower left middle. Passing through it will be Life "Spaceships" spaced precisely as the sequence of primes.

As discussed in my earlier entry, patterns for the game exist that create a Universal Turing Machine, meaning the game can "compute" in the same way that any program can. If it can be done in any programming language, so it can be done in the Game of Life using such a pattern. Mind blowing!

Stephen Wolfram, polymath extraordinaire and creator of the widely used mathematical, programming, and graphing workbench Mathematica has written extensively on the subject of cellular automata in his book A New Kind of Science.

In all fairness, while well received overall the book was the target of some rather excoriating reviews by experts in the various related fields, and accusations of intellectual thievery have been raised. Perhaps the most scathing of these and an interesting read on its own can be found in Quantum Information & Computation with the review by Scott Aaronson, a theoretical computer scientist and member of the MIT Electrical Engineering and Computer Science department.

The book is good read nonetheless for a view into the wide applicability of cellular automata, and the five pound nearly 1300 page tome will make a fine doorstop if you find it not to your fancy.

Wolfram extensively discusses the relationship of these objects to nature, modeling complex behaviors and results with simple basic starting seeds. A good example is that of certain seashells, where the complex patterns of their shell is generated by natural cellular automata.

Wolfram's central point in the book is that complex behaviors and results do not require a complex system for their production.

This culminates in the core of his "new science", the "Principle of computational equivalence".

As eloquently described in the Wikipedia entry for the book, "The principle states that systems found in the natural world can perform computations up to a maximal ("universal") level of computational power. Most systems can attain this level. Systems, in principle, compute the same things as a computer. Computation is therefore simply a question of translating inputs and outputs from one system to another. Consequently, most systems are computationally equivalent. Proposed examples of such systems are the workings of the human brain and the evolution of weather systems."

To get your own hands-on feel for how simple systems can generate incredibly complex results, get yourself a copy of the most excellent Golly cellular automata application where you can explore Conway's Game of Life and other types of cellular systems.

You may find yourself as addicted and fascinated as I am!

Always Be Reading A Book That Will Make You Look Good If You Die In The Middle Of It.

When I was doing the start up thing in the Silicon Valley, there was an engineer the I'd always see reading some pretty esoteric books. I queried them one day when I noticed they were carrying a rather large book on quantum mechanics. Having an interest myself, I welcomed the chance to discuss the subject. Turned out he wasn't even really reading the book. It was, in his words, "bait for the smart ones over at the Stanford campus." He would spend his lunch time over there at the commons, hunting his prey. I never did find out if the bait actually worked...

 "Outside of a dog, a book is man's best friend. Inside of a dog it's too dark to read. " - Groucho Marx

A good bookshelf is a must for any serious devotee of hardware and software. Myself, I stopped counting when I crested the 1000 book mark for my computer science related texts. As learning tools, reference works, and sources of pleasure, a good computer book is hard to beat in my opinion. With that in mind, I thought I'd make an entry listing the top tenish books that I think every serious programmer should have in their shelves.

These are not listed in any particular order other than that which they came to mind, and are operating system and language agnostic for the most part.

The Art of Computer Programming; Donald Knuth
All three volumes of course, plus the five fascicles that presage volume 4. Never has so much CS knowledge been packed into such a small space. This truly is a CS degree in a box.

Elements of Programming; Alexander Stepanov
Programming is mathematics. Seldom is this fact given proper treatment. This book remedies that brilliantly.

Introduction to Algorithms; Cormen, Leiserson, Rivest, Stein
A standard reference for professionals, and a widely used university text. Half of a CS degree is in this book.

Modern Operating Systems; Andrew Tanenbaum
The classic all-around reference and learning resource for the details of the inner workings of operating systems. From the creator of Minix, a Unix like teaching OS that was the template for the first Linux.

Beautiful Code; Andy Oram, Greg Wilson
See how luminaries in the programming world have created elegant solutions to difficult problems in a variety of programming paradigms and languages.

Masterminds of Programming: Conversations with the Creators of Major Programming Languages; Federico Biancuzzi, Chromatic
A superb 'behind the scenes' look at how historic and influential languages came to be, told by their progenitors.

Code Complete: A Practical Handbook of Software Construction ; Steve McConnell
A classic, recently updated. Certainly one of my 'desert island' picks for instruction on the proper design and construction of software.

Programming Windows; Charles Petzold
It's dated. It's also still the classic reference for Windows programming. "Look it up in Petzold!"

Windows Internals; Mark Russinovich, David Solomon, Alex Ionescu
There is no better publicly available reference for what makes Windows tick than this tome from the 'ghostbusters' of the Windows world.

The Algorithm Design Manual; Steven Skiena
Implementations and explanations of all of the important algorithms, and humorous to boot.

Structure and Interpretation of Computer Programs; Harold Abelson, Gerald Jay Sussman
This classic, often called 'the wizard book', was the text for MIT's introduction to programming classes. A rigorous lesson in how to think about programming.

Compilers: Principles, Techniques, & Tools ; Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman
The best survey, in my opinion, of the inner workings of compilers, with a sharp view of how design decisions affect the user.

I think if I awoke to my house on fire, after getting my family out, these would be the books I'd want to save from the blaze. I could happily settle for them being the only books on my personal shelf.

What's on your own list that you'd bring to a desert island?

I P in the Pool.

Internet Protocols and address pools, that is!  IP, the Internet protocol, is one of the foundational support structures of  the Internet that supports our gaming. IPv4, the first widely adopted version, was specified in RFC 791 during September 1981. IPv4 is a connectionless protocol for use on packet-switched networks such as Ethernet. It is a 'best effort' delivery protocol, that is, there is no guarantee of packet delivery, nor assurance of  proper sequencing of packets, nor any guards against packet duplication. These aspects, usually important for useful network communication, are handled by higher-level protocols on top of IP, such as TCP. UDP traffic, the most common for online games, is also a protocol that rides over IP.

At the core of the IP protocol is the concept of addresses. You've probably seen these on you gaming machine with references to things like 192.168.1.2, etc. The IP address consists of four Octets (less pedantically known as Bytes). So the same example address can be written as 0xC0.0xA8.0x01.0x02 in hexadecimal notation or 11000000.10101000.00000001.00000010 in binary (usually done when manually calculating subnet information).

The IP address, since it consists of four octets, has a total of 2^32 available addresses. There are actually fewer available for actual use, since parts of the specification allow for specialized addresses for use by things like broadcast traffic, loopback, testing, etc. Even so, there are a bit over 4,000,000,000 unique addresses available for use.

Early on, the bodies (most notably the Internet Engineering Task Force, IETF) involved in the design and specification of Internet protocols and technologies realised that an address pool of this size would likely become insufficient at a future time, and designed mechanisms to effectively extend the size of the available address pool. The almost universally used mechanism is known as Network Address Translation, or NAT. NAT allows Local Area Networks (LAN) to reside on some segment of addresses defined in the protocol as private while providing bidirectional access to public WAN addresses. Your PC, using a 192.168.#.# address, is on one such private address. Among other characteristics of Private addresses is that they are non-routable, that is, once they reach any router, they are kept on the LAN - no information is leaked to the WAN side of the router, and packets with addresses confined to the LAN will not be routed via the WAN. This ensures such packets from private networks stay on the private network.

So how does a PC on a LAN with a private address gain access to the rest of the Internet WAN residing at public addresses if their own traffic must remain on their LAN? That is of course the primary function of the router via NAT. Any traffic from a LAN PC destined for a public WAN destination has the address information in the packet manipulated by the router to appear to have originated at the public address of the WAN side of the router. Any return traffic is directed toward the public WAN address of the router, whereby the router manipulates the address information of the packet and forwards it to the appropriate PC on the LAN. For an excellent overview, see Network Address Translation in an unusually well written Wikipedia entry.

Using NAT, we can have tens of thousands of PCs on a LAN residing on one single public WAN address. Other groups of PCs can be residing behind other routers with other public WAN addresses, where the PCs on different routers may have the same private addresses, but there will be no conflicts: the WAN outside of each router cannot even 'see' the LAN since it is composed of private addresses, so no source of conflict can exist.

Even with this 'multiplication factor' of addresses provided by NAT, there is a growing shortage of available addresses: there is a growing number of services that need public addresses, and an explosion of devices (phones, media devices, even refrigerators!) that use addresses. Technologists in the field predict we will run out of IPv4 addresses sometime in 2011-2012.

The IETF realized early on a better solution would be needed, and started work in earnest in 1991. By 1998, RFC 2460 resulted, defining IPv6. The biggest change in this new version of IP is an address space consisting of 16  octets, or 128 bits. This means, compared to the roughly four billion (4,000,000,000) addresses available in IPv4, IPv6 has over 340 Undeciliion. That's a huge number, written out in its full glory,  it's:

340,000,000,000,000,000,000,000,000,000,000,000,000.

That's roughly seven IP addresses for each atom in each body of every human on the planet today.

Or about 3,120,000,000,000,000,000,000,000,000 (~3 Octillion) addresses for each man, woman and child that has ever lived on our planet (thanks, Population Reference Bureau). I think this will suffice for some time!

How long? To put this enormous number into perspective consider this: The age of the Earth is about 4.54 billion years. If we had been assigning IPv6 addresses for this entire period at the rate of 1,000,000,000 (one billion) addresses per second, we would have used a little over .00000000004% of the available address pool! It's BIG!

How big? If you imagine all of the IPv4 addresses mapped into the area of a space the size of one typical pixel of the display you're reading this on, the IPv6 address space would need a square about 52,500,000 miles on each side (thanks, WolframAlpha), roughly the surface area of 14,000,000 Earths.

An address space that large ensures every device on our planet can have a unique address, and completely eliminates any need for troublesome mechanisms like NAT (though there are proposals to retain such functionality for specific purposes).

IPv6 offers many other improvements compared to IPv4, such as much simplified address configuration options, much improved and intrinsic multicast support, mandatory network security support (IPSec), vastly simplified and improved handling by routers (no fragmentation by routers is allowed, PMTUD is mandatory), no header checksum is utilized (reducing processing load on routers), TTL replaced with Hop Limit (routers no longer need to make time in queue calculations), and vastly improved mobility components (no proxy/triangular routing, devices and whole subnets can move between  router points without renumbering), jumbogram support (packets up to 4,294,967,295 bytes long), and vastly improved extensibility (options are implemented as extension headers, effectively meaning unlimited protocol extensibility without requiring any changes in the basic protocol design).

Being the protocol newborn, adoption rates are in the early adopter stages: only a fraction of a percent of current Internet traffic at the time of writing is IPv6. Nonetheless, technologies to ease the transition  to IPv6 such as Teredo which tunnels IPv6 over IPv4 NAT using UDP, point-to-point tunnel services, etc. ensure that the migration to IPv6 will happen. It is not question of if IPv6 will be the predominant standard, but when. Behemoths such as Google are leading the charge, offering IPv6 interfaces to their search engine at ipv6.google.com and support for Google Services over IPv6 to compatible networks.

So why should we as gamers care about this? NAT is one of the primary culprits in connectivity issues for on-line gamers. Often, problems with the behavior or configuration of NAT in consumer routers result in spotty connectivity and sporadic connection problems. Additionally users that play peer-to-peer games or need to run a game server suffer all the slings and arrows of router configuration and port forwarding in attempts to attain proper game functionality.

IPv6 will eliminate the need for these machinations, providing a much more reliable, higher performance, more flexible infrastructure for on-line gaming.

Maximum PC: Maximum Content.

I get asked often 'what PC magazine should I get?'. Honestly, there are only three real players as far as I'm concerned: MAXIMUMPC, CPU and Dr. Dobb's, the latter now only available on-line.

There used to be a myriad of well put together PC centric magazines. Sadly, it seems the market for these is not sufficient to support the print publishing side for most of them. Only the strong have survived. Of the few remaining, most have devolved into Reader's Digest style shadows of their former selves, catering to a pretty dumbed-down demographic.

If you're a developer, Dr. Dobb's still has a constant stream of fairly deep and interesting articles that any coder can enjoy. For those that aren't coders, where Dr. Dobb's might be too deep, that still want a slightly more technical bent from a hardware and software standpoint, CPU fits this need well, along with decently in-depth hardware and software reviews.

If you're on the Linux side of things, your choices widen. Linux Journal provides a Dr. Dobb's feel in a Linux centric rag. Linux Magazine and Linux Format provide the novice with a gentler format (but be prepared to check your bank account before subscribing: the cost of these imported periodicals is wallet numbing!)

My desert island choice is MAXIMUMPC. The technical staff there is almost always on the ball, seldom making any glaring errors. The reviews are quite in-depth, you'll have to find a specialist web site to exceed their detail (has anyone figured out the meanings of the occasional random 'factoids' placed in the specifications of reviews? Enquiring minds want to know!)

Since it's my desert island pick, it has fortunately started covering Linux in the recent past, so I'll not miss out too much on happenings in the alternate OS universe.

The writers have a sense of humor sharp enough that it has on occasion generated controversy and feedback from the more uxorious readers. You've got to love it! Always interesting, sometimes controversial, I've been an avid reader since the days when it was called Boot.

Add to this that the publisher has seen fit to make available PDFs of back issues dating all the way back to 2003 at MAXIMUMPC PDF Archives, and you've got to want to support these guys. Their No BS Podcast series is one of the few I'm interested in listening to. Finally, the magazine supports a very active forum community at MAXIMUMPC Forums.

It is the one PC magazine I wait for like a cat hearing a can opener.

If anyone knows of other worthwhile PC centric magazines, I'm all ears! I miss the days of having a panoply of choices.

I Read it in a National Enquirer Survey, it Must Be True!

Is extrapolation from forum 'game problem' posts to indicting a game as a steaming pile 'o poo the same as taking a Cosmo survey at face value?

I think so. Every day, I see Forum Fights where particularly vociferous posters scream bloody murder over their current 'problem' game, lamenting how poorly coded some part of the game is, how anserine the developers are, usually by members that have demonstrated through prior diatribes they likely couldn't tell a line of code from a line of coke.

There are of course, mixed in with the cacophonous whiners, posters with real, genuine problems. It is often stated by some in the forums that the number of complaints over a game proves that the game has problems, and not just for them, but for everybody. These posters will argue to no end that this is so, even when shown contradictory evidence such as the vast majority of players that seem to be enjoying the game without issue. To me, their claims have always been analogous to making the logical leap from seeing everyone in a hospital is ill to the population of the planet is sick.

Can we make any valid statistical inferences from what we see in a forum? I think not. I'm more on the number theory side of things, but I'm comfortable enough with my background in statistics to state that we really can't make any valid inferences on the whole population of players for a game from what we see in forums.

Basic statistics (AP High School level) reveals to the learner some facts that at first seem perhaps implausible, and that would most likely seem implausible to the lay person. That valid inferences for large populations can be made from small samples (e.g., a few hundred persons sampled from a population of say one million that is being studied), and that the larger the population under consideration the smaller the sample size needed (expressed as a percentage of the total population) do seem a bit hard to believe.

But basic statistics shows us this is so. The interested reader not already versed can see Sample Size Calculator for some quick experimentation, and Required sample sizes for hypothesis tests in the Wikipedia article Sample Size for a quick brush up on the basics.

Key to these facts is that the sample is unbiased and random. Otherwise, all bets are off. The introduction of of bias can be subtle. Say for example, you are thinking of producing a new widget that improves the flavor of coffee. You're going to take the world by storm! You want to get an idea of how many people would buy it, so you construct a survey, randomly picking a few hundred home phone numbers from the phone book of a random city with a fairly large population. Over a period of a few work days, your staff calls these random possible buyers, and queries their interest. Much to your dismay, very, very few have an interest. Was the survey proper? Can you infer that you might want to rethink your widget idea from the results?

Did you catch the two (and there of course are more) possibly fatal biases introduced by the survey? Firstly, calls were made during 'work days'. Perhaps the most interested prospective buyers work during the day, so you completely missed them in the results. Secondly, just what was the 'random' city? If it turned out to be say Salt Lake City, with a core and suburb population of well over 50% Mormon, a faith that many followers believe precludes the drinking of coffee (actually, from The Book of Mormon: "And again, hot drinks are not for the body or belly."), your results are going to be wildly biased.

So much for an unbiased and random survey.

The posters in a typical game enthusiast forum produce a vastly more biased view of the population than even this woefully inadequate example survey. This is because they are self-selecting. They are there by choice, not because they were randomly selected from the population. Importantly, a high percentage of these self-selected forum members only make posts when looking for solutions to problems, game caused or otherwise, or to state some other dissatisfaction with the product. Self-selection introduces one type of Selection Bias that makes any kind of valid statistical inference nearly impossible, even after adjusting or weighting the data.

One of the more interesting studies related to this kind of problem is covered in the landmark study Comparing the Accuracy of RDD Telephone Surveys and Internet Surveys Conducted with Probability and Non-Probability Samples by David S. Yeager and Jon A. Krosnick of Stanford University. In it, the authors state:

"If the factors that determine a population member’s presence or absence in the sample are all uncorrelated with variables of interest in a study, then the observed distributions of those variables should be identical to the distributions in the population. And if the factors that determine a population member’s presence or absence in the sample are all uncorrelated with the magnitudes of associations between pairs of variables measured in the study, then the observed associations should also be identical to those in the population. However, if these conditions do not hold, then survey results may not be comparable to those that would be obtained from probability samples...More generally, the present investigation suggests that the foundations of statistical sampling theory are sustained by actual data in practice. Probability samples, even ones without especially high response rates, yield quite accurate results. In contrast, non-probability samples are not as accurate, and are sometimes strikingly inaccurate."

Quite the mouthful! Nonetheless, it cuts to the quick of the problem of trying to project the experiences of forum posters with game problems onto the general population of players of the game.

You can't, really. And doing so in a forum rant probably does nothing more than make one look like an Internet Jackass.

A Most Interesting Development in Graphics and Rendering

Check out the stuff at Unlimited Detail Technology.

Most fascinating, an amazing start for an autodidact. It is so good, I wonder if it is some elaborate April Fools' joke...

It will be quite interesting to follow the progress of this project, even more so the reactions of Nvidia and ATI. If they're smart, and this is the 'real deal', one should buy the technology outright, and utilize the GPGPU functionality available in their products to speed computation.

The Race for Real-Time Photorealism

Having built a simple client-server FPS game including a simple rendering infrastructure and even simpler netcode from scratch as a brain exercise, I'm always amazed at what the real experts in the field can do.

A most fascinating article in the March 2010 issue of American Scientist covers aspects of rendering for realistic scene generation. My feeling is we are less than a decade away from games that can render environments indistinguishable from a movie. The rendering of humans, or other familiar living things, may be a bit further down the road: We are so programmed to incredibly subtle visual triggers, while it is currently posssible to render a human that is indistinguishable from reality, the illusion collapses once movement, speech, or other interaction occurs.

A fascinating read, available at the time of this post at: http://sigmaxi.org/4Lane/QMag/AMS_Mar_2010.pdf

How could it possibly be my router causing connection issues?

Readers of game enthusiast forums have undoubtedly seen the sometimes heated exchanges between the It's all gotta be the GAME, crap developers! crowd, and the It could be a problem on your end gang.

I'm of the latter, if you've read any of my posts.

I produced a guide based on helping users in BFBC2 and other games, called Troubleshooting Multi-Player PC Game Connectivity Issues that covers many of the often subtle conditions that can cause connectivity issues for online games. This is rather long - there are many interacting factors that can cause these problems. Some may not have the time to read it, some just won't, sticking to their guns of It's all gotta be the GAME!

I've been attacked by a few, questioned by many. That's fine (the latter, at least), skepticism is good. Ignorance isn't!

I've compiled a list of references for those that want to take the time to see what experts in the field, and real users of many other games, have to say on this matter. In particular, there are much more detailed NAT technical information and the issues involved covered in some of these. It was not practical for me to include this level of detail in my document - it would have become a hardbound book!

If you're really interested in answering the question How could it possibly be my router causing connection problems? , these will help you get there. It will also help you to understand how things can be fine in every other game yet broken for a certain few games, with different users having differing experiences.

I've also included links to forum posts for many games, and many platforms, clearly showing that this kind of issue happens all the time.

Perhaps with a clearer understanding, these may help you solve your own connection problems.

They should also help you to dispel the myth of 'port forwarding has to be used' often repeated in forums. A read of Port Forwarding: Slaying the Mythical Dragon of Online PC Gaming will clarify how NAT and port forwarding are related, and why forwarding ports blindly is unneeded and potentially problematic when used.

Good reading!

References for NAT technologies and issues involved:

Superb overview by Geoff Huston of CISCO
http://www.cisco.com/web/about/ac123/ac147/archived_issues/ipj_7-3/anatomy.html

Nice overview by the author of RakNet, with success/failure charts:
http://www.jenkinssoftware.com/raknet/manual/nattypedetection.html
http://www.jenkinssoftware.com/raknet/manual/natpunchthrough.html

IETF recommendations for NAT behavior:
http://www.ietf.org/rfc/rfc4787.txt

A very good overview, with diagrams:
http://en.wikipedia.org/wiki/Network_address_translation

For the absolute bibles for NAT and other TCP/IP technical information:
http://preview.tinyurl.com/yefzpfv
http://www.amazon.com/TCP-Guide-Comprehensive-Illustrated-Protocols/dp/159327047X

AnalogX NAT and Nat traversal issues overview:
Interesting test of 100 consumer routers. DGL-4300 top rates, Apple /3com/US Robotics the worst.
Only 43% of routers properly supported full cone NAT.
http://www.analogx.com/contents/articles/nattraversal.htm

A game developer talks about problems with NAT of differing types by consumers:
"If it is a router, it's the user's problem to solve it."
http://forum.unity3d.com/viewtopic.php?p=233448

Other forums for games where users have the same issues some have with game "X".
These same users could well be playing game "Y" without issue.

http://forums.gamesforwindows.com/p/1860/23980.aspx
http://utforums.epicgames.com/showthread.php?t=665969
http://support.microsoft.com/kb/840420 (Microsoft? What would they know?)
http://utforums.epicgames.com/showthread.php?t=602500
http://forums.epicgames.com/showthread.php?t=616452
http://www.dslreports.com/forum/r19418084-Gaming-Mode-Why-does-Dlink-recommend-disabling
http://www.dslreports.com/forum/r20554921-Xtreme-NAT-help-with-Netopia-2241n006
http://support.microsoft.com/kb/941207 (More Microsoft. Maybe they know something about networking?)
http://www.gtaforums.com/index.php?showtopic=353023
http://forum.instantaction.com/smf/index.php?topic=3631.0
http://blogs.msdn.com/johnmil/archive/2006/10/29/nat-traversal.aspx
http://www.gtagaming.com/forums/archive/index.php/t-103945.html
http://www.xfire.com/nat_types/ (widely used Xfire, and problems NAT can cause in the wrong router)
http://forums.electronicarts.co.uk/fifa-10-sony-playstation-3-microsoft-xbox-360/840675-game-no-longer-available-still-9.html
http://www.ureadit.com/solutions/home-network/79-xbox-live-compatible-router.html
http://www.gtagaming.com/forums/archive/index.php/t-103841.html
http://forums.eu.atari.com/archive/index.php/t-59626.html
http://www.bing.com/search?q=full-cone+nat+games&first=51&FORM=PORE
http://forums.eu.atari.com/archive/index.php/t-62799.html
http://openarena.ws/board/index.php?topic=3261.0
http://www.poweredbygamespy.com/services/view/category/connect/ (Gamespy - they brag at only having 10% failure of NAT)
http://boardreader.com/thread/Port_Restricted_Cone_Nat_Router_l9xyXvexg.html
http://text.broadbandreports.com/forum/r22505721-HSI-Known-NAT-problem-with-Charter-HSI
http://computerhelpforum.org/forum/networking/f43/full_cone_nat/t18037.html
http://forums.gametrailers.com/thread/nat-type-1-question/1042731
http://forums.epicgames.com/showthread.php?t=665969
http://www.bgforums.com/forums/viewtopic.php?f=58&t=12277

There are a myriad more, Google is your friend!