Guessing secrets: applying mathematics to the efficient delivery of Internet content

Science News, April 6, 2002 by Ivars Peterson

Even on uneventful days, traffic on the Internet can sometimes stutter to a crawl. It gets much worse when millions of people go online at the same time to view the latest images from a Mars expedition, download a trailer for an upcoming Star Wars movie, or take in a titillating fashion show. The mushrooming demand on such days can rapidly clog this worldwide web of computer networks, causing horrendous delays and outages. In other words, access to Web sites melts down just as things get interesting.

"We have to use the Internet the way it is, bugs and all," says mathematician Tom Leighton of the Massachusetts Institute of Technology, one of the founders of Akamai Technologies in Cambridge, Mass. Originally designed several decades ago to handle communication among researchers at a handful of laboratories, the system that's now the Internet can falter in the face of massive, global migrations of digital data.

Since 1999, Akamai has offered to highly popular Web sites ways to ease congestion. The company redistributes text, images, and movies through its own computer network, which is independent of but connected to the Internet. Akamai's network takes advantage of sophisticated mathematical methods to determine which of the company's worldwide collection of more than 14,000 computers should store a Web site's content so that it can unfailingly get to users in the shortest possible time. Akamai's customers include the Centers for Disease Control, retailer Victoria's Secret, and the search engine Yahoo.

Leighton, graduate student Danny Lewin, and several colleagues developed the proprietary algorithms that govern the way Akamai manages and redistributes information. (Lewin died on Sept. 11, 2001, aboard one of the planes that struck the World Trade Center.)

The data-management tools developed by Akamai to keep Web sites operating efficiently solve about 99 percent of the problem of Internet-style traffic jams, Leighton says. To better that performance, Akamai researchers must tackle various quirks in the rules that govern Internet communication.

One recent effort to improve network performance has mathematicians taking a fresh look at the familiar game of 20 questions. In this game, a player tries to identify a secret object by asking a sequence of questions--traditionally beginning with "Animal? Vegetable? Mineral?"-- that can be answered by yes or no.

In the Internet variant of the game, the secret is a sequence of 32 binary digits representing a computer's Internet protocol (IP) address. In this game, however, there are always two or more secret solutions, and the responder supplies a truthful answer to a given question without specifying for which secret the answer is true.

"The research issues are: How much can you learn, and how quickly can you do it?" says Ronald L. Graham of the University of California, San Diego. "It's a fascinating problem that has surprising links to all sorts of mathematics."

INTERNET MATCH GAME Roaming the Internet's World Wide Web appears effortless. To join the hordes eager for a glimpse of a newly imaged Martian rock, for instance, you simply fire up your Web browser and type in a Web-page identifier--the so-called uniform resource locator, or URL. If the image is available only at a single computer that's sitting in, say, a NASA laboratory, every such request must find its way to that one Internet address. The frequent result is a mess of jammed communication lines, an overwhelmed Web site, and frustrated armchair explorers.

A significant part of Akamai's strategy is to make high-demand content available at multiple computers throughout the world. The next step is to match Web-page requests with the appropriate Akamai servers--in effect, shortening the paths traversed by requests and data throughout the Internet labyrinth. For the Akamai system to decide which server should deliver the requested content, it's desirable to quickly and accurately pinpoint the geographic location of a user's computer.

Every computer connected to the Internet has its own numerical address, but there's a burdensome complication in the way the system operates. When a browser makes a request, the message goes to a network computer known as a nameserver, which looks up the target Web site's numerical Internet address and passes the message on to the relevant server. For example, any request for a Science News Online Web page (at www.sciencenews.org) must be sent to a computer with the IP address 216.167.111.80.

If the message is directed to a Web site for an Akamai customer (Science News Online is not one), the Akamai system receives the message and must decide which of its servers should provide the content. However, all that system sees initially is the Internet address of the nameserver, not of the client. The nameserver's address doesn't reliably indicate locations of the computers it serves.

So, it would be helpful for Akamai to know which nameservers handle which clients. In a quirk of the protocols governing Internet communication, the address of a nameserver never appears together with the address of any one of its clients. However, the nameserver can provide some additional information, which might be used to deduce the client address.