Wolfram|Alpha: Systematic knowledge, immediately computable.

Saturday, May 1, 2010

Black Holes Stephen Hawking Knows Not. But You Will.

Black Holes. Undoubtedly the most enigmatic titans of our universe. Prodigious consumers of all matter that finds itself too near their inescapable gravitational grasp, a force so powerful even light itself cannot escape, never to be able to return to the known universe. By Einstein's Theory of Relativity, they are time machines through gravitational time dilation. Perhaps more exotic time travel is possible for those of the species fitting the Kerr solutions to the field equations, allowing travel through time and space, even to other universes.

Through the work of the brilliant physicist Stephen Hawking, master of all things "black hole", we know that we may even be surrounded my tiny, microscopic primordial black holes, and should the geometry of the universe be appropriate, we may find ourselves producing our own microscopic black holes at the rate of one a second through experiments at the Large Hadron Collider. Fortunately, these will evaporate nearly instantly. Recent work by astrophysicists points to the tiny primordial black holes as a likely culprit for the ultra-high energy cosmic rays occasionally observed on earth.

But there are back holes lurking here on earth already. You may be closer to one than you might imagine. They will gobble up your network packets as efficiently as their cosmic cousins quaff matter. I am of course referring to Black Hole Routers and their cohorts in the crime of packet theft, overly restrictive or misbehaving firewalls. What is a black hole router, and why should it matter to a gamer? After some preparatory material, we'll cover that in this blog entry.

In the typical network environment, IP provides the basic Internet layer mechanism on top of the nearly universal Ethernet V2 frame. The commonly used TCP and UDP protocols ride on top of the IP layer. Each Ethernet frame can have a data packet up to 1500 Bytes in size (we'll not go into exceptions for our examples here). The primary purpose of network devices is to route these protocols from senders to receivers, and back. Along any given path between a sender and receiver, there may be devices that are unable to process packets beyond a certain size limit. Usually, the device sending packets to such a device will simply break the packet into smaller packets, a process called fragmentation.

Fragmentation of packets has undesirable side effects, including a performance impact, so ideally we want to minimize this for a route. The same holds true for packets traveling the return path (which may differ from the send path) to the sender. A mechanism that will allow the sender to determine the ideal maximum packet size to avoid any fragmentation will maximize performance and minimize network overhead. The standard mechanism for achieving this goal is known as Path Maximum Transmission Unit Discovery, or PMTUD.

Devices along the path (usually exclusively routers) that must impose a limit on the packet size by fragmentation when the sender has explicitly disallowed fragmentation by using the IP "Do not fragment" (DF, the normal default behavior in modern systems) flag are expected to notify the sender of this limit. This is done thorough a standardized ICMP "Fragmentation needed and DF set" message, with the required limit encapsulated. A sender receiving such a message can adjust the outgoing packet size accordingly. All would be well if everything worked as it should, but in the real world there are routers that misbehave and do not respond with the needed ICMP message, and firewalls that block these needed messages. These are known as Black Holes.

The result is senders appearing to establish a proper connection (the three-way TCP handshake is successful), but having sporadic problems sending and/or receiving data. For a game, this can result in the appearance of lagging, connection loss, etc. (N.B., the PMTUD is normally reserved for the TCP protocol. While it can be used for UDP, it is seldom utilized due to difficulties in determining proper sender behavior for packets dropped by black holes.) Since most games use a combination of UDP and TCP, it is quite possible that black hole on the path between the game client and server(s) will adversely affect game play and connectivity.

Fortunately, there are steps the gamer can take to diagnose and remedy problems with black holes. The Ping utility provides a ready tool to aid us in our diagnosis. Using ping -f -l#, where # is the packet size, we can send probes toward the desired destination. The "f" flag denotes setting the "DF" flag in the IP header.

For example, the command:

ping -f -l 1450

will send packets of length 1450 to the destination IP of The returned results will tell us much about the characteristics and behavior of devices along the path of the packets.

If the ping command returns with the expected results, we know that all is well, and no device in the path is requiring a smaller packet size than the length specified (with the addition of the IP overhead).

If the ping command returns with the ICMP "Fragmentation needed and DF set" message, we know that some device in the path needs a smaller packet size to avoid it fragmenting our packets. We can modulate the value of l until we find a length that passes the path with normal results.

If the ping command returns "Request timed out", we know that some device in the path requires a smaller packet size, but is not returning the needed ICMP message or that message is being blocked. As with the second case, we can modulate the value of l until we get the expected return results.

A good starting point for l to work down from is 1472, and 1464 for PPPoE connections. In particular, users of PPPoE should check their environment for proper MTU and PMTUD behavior: in some cases, when PPPoE is done on the router, the PC or responding server may only see the router MTU of 1500, causing dropped packets and connection issues. Check with your ISP to determine if your required MTU is other than the typical 1492 for PPPoe.

Once armed with the appropriate MTU value (l+28, 28 is the overhead for the IP and ICMP headers), we can configure our PC and router as required. Other more drastic measures may be used to diagnose or bypass black holes, such as enabling PMTU black hole detection, disabling PMTUD, and hard setting the MTU (MSS clamping) for the interface device. The details of these steps vary by device and OS, by router make/model, and are beyond the scope of a blog entry.

Consult the documentation for your hardware and OS environment for details, or use the web: there are many excellent detailed descriptions for configuring these settings. Or give Stephen Hawking a call. But you now probably know more than he does on the subject!

No comments:

Post a Comment