Thu

Jun 19
2008

Andy Oram

Andy Oram

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-8Top Level Address (e.g. FF = location-aware subnet)\
Bits 9-23Latitude (medium resolution, approximately 1/3 mile or ha\ lf a kilometer)
Bits 24-39Longitude (medium resolution, approximately 1/3 mile or \ half a kilometer)
Bits 40-127Remaining 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: emerging telephony, geo, location  | comments: 9   | Sphere It
submit:

 
Previous  |  Next

0 TrackBacks

TrackBack URL for this entry: http://blogs.oreilly.com/cgi-bin/mt/mt-t.cgi/6564

Comments: 9

  Peter Cranstone [06.19.08 11:53 AM]

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
www.5o9inc.com

  Roger Nolan [06.19.08 05:33 PM]

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

  Andrew Russell [06.19.08 05:46 PM]

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.

  Ken McNamara [06.20.08 02:17 AM]

"... 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.

  Rob [06.20.08 03:07 AM]

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

  Noah [06.20.08 06:22 AM]

@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.

  Carl Malamud [06.23.08 01:00 AM]

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 [07.05.08 04:26 PM]

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

  hemanth [11.05.08 07:10 PM]

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..

Post A Comment:

 (please be patient, comments may take awhile to post)






Type the characters you see in the picture above.

RECOMMENDED FOR YOU

RECENT COMMENTS