Location, Location, Location
By Suzanne Ross
July 20, 2001 12:00 AM PT

Isn't it always about location, dahling? The Internet tribe might say, 'not in our backyard, the Web is a wild frontier without borders and laughs at geography.' But if you've ever searched the Web for a service available in your local area, or wanted to get local news and weather on your portal site without having to wade through the personalization feature, or thought it would be nice if your handy PDA could help you find your way around a town or a mall, you may admit that the Internet is also prone to the adage that location is everything.

Location is everything because you want your customers to find you, you want your friends to find you, and you even want your family to find you. You can plunk a giant Godzilla balloon on top of your building, but unless someone just happens to drive by, they won't find you without your address and a map.

The post office developed a protocol that allows mail and packages to find you every time (well almost every time!). The Internet followed suit with a protocol that specifies the numbers for your Internet address so that messages can find their way to your cyber home. It's called an Internet Protocol (IP) address. But unless a Web site gathers information from a user that matches their IP address with their geographic location, there isn't any inherent information to connect the two.

This wasn't such a problem when the Internet was young. But as the Internet grew up, and more and more people became wired, it turned out that more and more of them wanted to filter the information that deluged their e-in baskets and wrecked havoc with their attention spans. They began to want information uniquely suited to their needs. If they log onto MSNBC, they want information for their area, not information that is only useful to people three states away.

That's where Venkat Padmanabhan of the Systems and Networking group at Microsoft Research comes in. In the IP2Geo project, he's matching physical locations with cyberspace locations, trying to bring the two together so that Internet content providers can have more meaningful relationships with all of us.

It's Better Than Breadcrumbs
The first technique Padmanabhan and his summer intern, Lakshmi Subramanian from Berkeley, tried is called GeoTrack. It tries to infer location based on the domain name. The Domain Name System (DNS) translates domain names into IP addresses. If you're really lucky, the domain name will have clues about the host location. For instance, official state of California Web site is http://www.state.ca.us. But this doesn't happen too often, so Padmanabhan tracks the routers along the path of the message, determining the physical location as the location of the last router traced. "The network is basically a bunch of nodes and links connected together. From the domain names of routers, we are able to trace the geographic path leading to the target host that we are trying to locate," he says.

GeoPing is the next method that Padmanabhan tried. It has elements similar to another location mapping system focused on wireless networks called RADAR that he had previously developed. RADAR tries to locate mobile users in localized environments such as office buildings and shopping malls. For instance, it can guide users to resources such as the nearest printer, help them navigate through an unfamiliar building, or help them find their friends in a mall. In contrast, GeoPing (and IP2Geo in general) is targeted at the global Internet, making the scale of the project much larger.

Padmanabhan says that with GeoPing, "What you do instead of tracing the path is measure the delay between where you are and where the unknown machine is. We've found that there is a pretty good correlation between delay and distance. The longer the signal, the farther the packet has to travel." Padmanabhan and Subramanian first had to prove that there was a correlation between network delay and geographic distance. They were able to build a "delay map" that showed the relationship between delay and distance. By measuring the network delay from several geographically dispersed probe machines, they were able to get a much more accurate estimate of location.

GeoCluster was the most successful technique that Padmanabhan developed. It doesn't depend on active network measurements, but instead builds a location map for a large subset of IP addresses from network routing and location information from a few known hosts. "We found that GeoCluster was the most accurate of the IP2Geo techniques. The median error was about 30 kilometers, which is roughly the size of a city or a metropolitan area. The other techniques can give you an answer to within a few hundred kilometers, which is roughly the size of a small state in the U.S.," says Padmanabhan.

The partial location information is gathered from a variety of sources. For instance, a TV program listing site would have zip code information, since users want to find their local listings.

Landmarks
Padmanabhan not only wants to help you find your way around the Internet, he also wants to help you find your way around town. His newest research takes advantage of the way people usually find their way around - through landmarks.

If a stranger stops you on the street and asks you how to get to a favorite local watering hole, it's unlikely that you'll be able to spit out exact directions. Instead you're more likely to say, 'go down this street until you see the Target, then turn left until you see a Dairy Queen and a Skippers, then turn right at the train tracks and you're there.' The stranger will nod, smile and probably not even have to write the directions down. He's got the familiar landmarks etched firmly in his brain.

But most maps don't identify landmarks. Instead they're a sometimes confusing mess of colored lines and teeny, tiny street names. Unless you have a magnifying glass strapped to your head, they're next to impossible to read, especially if you're driving along at 60 miles an hour.

Some cities are beginning to build 3D maps of their areas, complete with landmarks. Padmanabhan thinks that it would be great to use these 3D maps. Then you could enter the landmarks that you see, and where you want to go, and have the program tell you how to get to where you're going using landmark information. This work is still in the baby stages, but recent leaps in the graphics and vision communities are bringing this concept closer to reality.

Location-based awareness services are one of the most useful applications of the Internet. Padmanabhan's work in finding people, local services, and buildings - and bringing them together-should make it easier for us to navigate through our days.