• Print

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:

Bits 0-8 Top Level Address (e.g. FF = location-aware subnet)
Bits 9-23 Latitude (medium resolution, approximately 1/3 mile or ha
lf a kilometer)
Bits 24-39 Longitude (medium resolution, approximately 1/3 mile or
half a kilometer)
Bits 40-127 Remaining 88 bits used to identify devices on subnet

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.

tags: , ,
  • http://www.5o9inc.com Peter Cranstone

    Here’s an alternative solution that is already up and running AND has an Open API. (

    Write a simple widget that reads the GPS comm port. Take that data and pass it via the API to a browser extension which in turn injects the data into the outgoing HTTP request headers.

    Result… the web server you’re requesting the page from instantly knows where you are. You can learn more at the web address below.

    Bonus feature – zero changes required to your current infrastructure.

    Cheers,

    Peter
    http://www.5o9inc.com

  • http://www.rogernolan.name Roger Nolan

    Nice idea but what’s the application?

    I’ve seen a few ideas like this and it’s all very clever but adding location awareness to transport isn’t very useful. Location is application information.

    If my terminal knows its location it can embed it in the server request – it doesn’t need to have the IP address represent its location.

    If you just want my terminal to find its location by looking at the address of the router, there are simpler and more elegant ways to do that than encoding the location in the address.

    r

  • http://www.amateurlayman.com Andrew Russell

    Maybe the better way would be to use the DNS system the same way that reverse IP lookups use the forward DNS infrastructure.

    The GEO DNS system could resolve to a ‘localised’ server that supports a specific geographical area that stores and allows visibility between devices in the area. There are already services that make available a persons geo information with a fine grained permissions infrastructure, which would be mandatory for this application as it would impinge on the peoples privacy (and dangerous to boot).

    This would enable the existing technology to manage things, without forgoing a large address space. The Chinese would be livid about setting aside a large chunk of the V4 address space for an edge application experiment, they are already hurting from the V4 address limitations.

    The other major problem with the approach above is that you are scanning the IP range, which is not scalable and will activate Network based Intrusion Detection/Prevention devices.

  • http://grandcanyonhiker.com Ken McNamara

    “… vastly more than we can ever use.”

    Did anyone else notice the irony?

    Right after that the author slurps up 40 bits of this unlimited resource.

    Still, great thinking and a nice proposal.

  • http://gisconsultancy.com/blog Rob

    So this would allow location aware devices to discover other location aware devices? Sweet.

    It doesn’t seem to resolve that the location of devices that are unaware of their location (currently the majority) is riddled with problems…see the following post over at slashdot

    http://ask.slashdot.org/article.pl?sid=08/06/18/2242251

    Please correct me if I’m missing something.

    Rob

  • http://noahsloan.com Noah

    @Peter, Roger, Andrew: Your solutions rely on a central server which doesn’t provide much fault tolerance or scale to a large number of users. Multicast is localized and bandwidth optimal (no packets leave the area, only devices in the area receive packets) and isn’t relying on a central server, only that the routers support it and virtually all routers do at this point (most have it enabled within the AS, it’s inter-AS multicast that isn’t turned on, mostly for political/business reasons).

    There are plenty of applications for geolocal devices in a P2P network. e.g., you have thousands of people in traffic, their phones moving with them. That means each one can report their average speed and location, giving you real time traffic information. 50 devices average speed just dropped to 5PMH on the highway? You now know about it and can see the alternate route with 5 cars on it all going 55. There are a million things like that, you just need a scalable infrastructure to make it happen.

    Unfortunately, as long as a majority of APs are owned by major ISPs, services like this will likely be blocked for the same reason inter-AS multicast is blocked: they can’t make any money off it.

  • http://public.resource.org/ Carl Malamud

    Hi -

    Tony Hain has had some similar IPv6 work under development since 2006:

    http://www.ietf.org/internet-drafts/draft-hain-ipv6-geo-addr-00.txt

    You might also want to look at the minefield that is geopriv:

    http://www.ietf.org/html.charters/geopriv-charter.html

    I’m not quite sure I understand the IPv4 example, in particular the requirement “for devices to reside behind a NAT interface of some sort” and then subsequently “send a multicast message to the geoIP subnet.” In IPv6, the address is globally visible, but I’m not sure in the IPv4 example Brian is talking about if he envisions many NAT’s (e.g., this is a private address space, in which case I’m not sure how you do discovery) or some single mother-NAT (in which case one wonders about scaling).

    In any case … throwing this over the wall as an internet-draft into the IETF would definitely get you some pretty immediate and specific feedback.

  • Karen

    Could anyone help me find an address or name if I have an email address ip address

  • http://friendfeed.com/subhaa hemanth

    mai i no how to hack ip through my computer to another net cafe can u say me and plz send me how to do it ..to this Email.. me bujjigadumunna@gmail.com this is my Email..

  • Seth

    This is a VERY POOR idea with respect to privacy and free exercise of liberty.

    If anything this should be double opt-in.

  • Andy

    I agree with Noah, money talks… companies wont like something if they cant dip their hands in your pockets….