Hacking TCP/IP To Support Location Aware Services

I just received a simple proposal (which is usually the best type) from Brian McConnell, an O'Reilly author and old phone hand who has founded several telecom companies. His proposal, which follows, represents a creative linking of the GPS/location domain and TCP/IP. If you thought there was no use for IPv6, read on (but it could work with IPv4 now).

Hacking TCP/IP To Support Location Aware Services

by Brian McConnell

18 June 2008

Most of the Internet services we rely on have prospered because they are based on open standards. The Internet itself would not exist in its present form were it not for open services such as DNS. Location-aware services, while they have great potential, have yet to coalesce around a simple, open standard that encourages an ecosystem of products and vendors to develop around it.

I would like to share a rather simple idea for hacking the TCP/IP protocol (specifically IP addresses) to support location-based services; I'm calling it geoIP.

I'll start with IP version 6 which, as most of you know, creates a very large address space (128 bits, enough to support 3.4 x 10^38 unique addresses, vastly more than we can ever use). Because the address space is so large, we can partition it to create a block of location aware addresses. Here's how this would work.

The 128-bit IPv6 address can be broken into smaller sub-addresses to embed latitude and longitude information within the address. We might use a formula like the following:

Note: high resolution location information and other metadata would be presented in a separate message, such as an XML file sent during a device-device handshake.

The idea here is to enable devices to automatically search for other IPv6 addresses that are mapped to physical locations. If a device knows its latitude and longitude, it can scan the address space FFLLLLLLNNNNNNNN* to find other devices in the local zone. This can probably be done most efficiently by sending a multicast message that routers repeat to devices that are nearby with the matching public IP addresses (e.g., "I am trying to contact all mobile phones near 37.46N / 122.26W").

What this address space does is to subdivide a larger address into 1/3 mile × 1/3 mile subnets, each of which can accommodate a very large number of devices. We can then find all devices within this zone via a simple peer-to-peer handshake, and filter the results by device type, precise location, and other characteristics.

We could do this with IPv4 using a lower geographical resolution, plus a requirement for devices to reside behind a NAT interface of some sort. In the case of IPv4, the formula could be as follows: Reserve a top level address (such as 254.*.*.*) for geoIP service. The remaining 24 bits are mapped to a 12-bit × 12-bit latitude/longitude address space, yielding approximately 0.088° accuracy, or about a 7-mile/11-kilometer cell size at the equator).

A number of tricks could be employed to reduce the grid size, such as weighting the address space so that cells are densest at low and middle latitudes, while becoming larger in high latitudes, using a simple algorithm to map latitude/longitude coordinates into the IP addresses. The same approach can be used to adjust cell width (in longitude) so it is compressed over land masses, and more sparse over oceans. Compression can also be expressed as a simple equation that translates an angular (longitudinal coordinate) into 12-bit number. With a little bit of fine tuning, it should be possible to adjust cell/grid size so that the average cell is 2 or 3 miles (3 to 5 kilometers) in low/middle latitudes over land masses, yet considerably larger over areas that are, on average, less populated. This is obviously not as simple as the IPv6 approach, but it is not very difficult either, and should work fine.

In both cases, we do not need to embed super high resolution position data in the IP address itself. What we want to enable is a simple peer-to-peer method for discovering nearby devices through direct interrogation. If I know I am at an IP address that maps to 37.5N / 122.25W, I can start scanning the nearby address space in expanding circles to see who else is around, or send a multicast message to the geoIP subnet asking devices to report back to my static IP address. The geoIP address may change frequently, which will update the device via DHCP.

The idea here is to create a vendor-neutral method for device discovery and search. A device does not need to know anything about the other devices attached to the network except the formula used to embed location information within IP addresses.

These devices can then expose a simple web server on a designated port at the location based address. Other devices, upon discovering active devices in their local zone, can fetch pages or XML files that contains additional information about the device, its capabilities, etc.

The combination of these techniques would make device discovery and search open and vendor-neutral. Once devices have discovered each other, they can communicate using existing Internet services, such as email, XMPP, SIP, etc. via conventional IP addresses. The key idea is to create a peer-to-peer discovery mechanism that is not dependent on centralized services or proprietary vendor APIs. With that in place, any device should be able to find and talk to other devices within a cell or group of cells defined by latitude and longitude coordinates.

Appendix : Sample Algorithms To Map Location Based IP Addresses

IPv4 Latitude

Lat = 12-bit integer ranging from 000 (-90/90S) to FFF (90/90N)

Resolution can be improved by using a non-linear mapping algorithm that emphasizes low and mid latitude addresses.

IPv4 Longitude

Long = 12-bit integer ranging from 000 (-180/180W) to FFF (180/180E)

Note: because latitude covers a 180-degree range while longitude covers a 360-degree range, and because we can reasonably assume we don't need high resolution cells above or below 66° North or South, we could specify 11-bit addresses for latitude (approximately 5.85-mile/9.4 kilometer resolution, better with non-linear mapping), and 13 bit-addresses for longitude (2.9-mile/4.67-kilometer resolution).

IP Address Assignment Via DHCP

Because a device may be in motion, we should assume that geoIPs are dynamic, with a short time to live. GeoIP-enabled devices would obtain a second location-based IP address from a DHCP server. DHCP already recognizes an optional DHCP client ID, which can be used to transmit location information in a dotted format (e.g. mad_address . latitude . longitude). With th\ is information, the DHCP server can then assign a public or NAT'ed IP address that appears to other devices as a geoIP.