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.