Traffic is getting worse every day. Not just on city streets and freeways, but also on the Internet, cellular phone systems and other communication networks. Not only is it hard to get where you're going, it's sometimes hard even to figure out where to go.

Cornell University computer scientist Jon Kleinberg hopes to make the networks more efficient. He has received a three-year, $305,000 grant from the Office of Naval Research to study the way information moves around in networks and methods for mining data from them.

Kleinberg, an assistant professor of computer science at Cornell, is a specialist in algorithms, the problem-solving strategies on which computer programs are built. While he will focus on the routing problems of the Internet, the algorithms he develops could be applied to many other kinds of networks, from telephone systems and power grids to networks of people, and maybe even the timing of traffic lights.

A network can be described as a collection of points called "nodes" and the paths between them. On the Internet, the nodes are computers; the paths are communication lines over which information travels in small bursts of bytes called "packets." Traffic is managed by computers called "routers." Each packet of information contains the address of the computer to which it is going. The job of a router is to look at that address and send the packet along the best route to its destination. A router in New York, seeing a packet addressed to San Francisco, probably wouldn't send it straight there, but more likely to Buffalo, or Atlanta or Columbus, trusting a router there to send it on in the right direction.

Just as a presidential motorcade can clog city streets, a busy node can clog net traffic.

"Each machine has information that is only local and not about the whole network," Kleinberg points out. "Some results show that algorithms that operate purely with local knowledge work well." He plans to investigate how the router can make the best use of local information. Routing might also be improved, he adds, by giving routers a way to predict how many requests will be coming in the immediate future, based on recent experience.

Another question is how computers should assign priorities to incoming requests. "Some people request large amounts of information, some small," Kleinberg explains. "If you handle all the large requests first, the small ones have to wait a long time. The order in which you service requests has global effect, and a set of decisions one computer makes can have effects all over."

Understanding these problems, Kleinberg says, can help in designing networks of the future. "If you see congestion in one part of the network, what's the best way to add capacity, to allocate your resources?" he asks. "There have been cases in the past where congestion grew out of control. The fact that we have been able to build better networks is because there has been a huge amount of effort behind the scenes to find better ways."

The study of algorithms is an important focus of computer science research at Cornell. In particular, Kleinberg works closely on algorithms with Eva Tardos, professor of computer science, and with Srinivasan Keshav, associate professor of computer science, who designs and builds applications and protocols for networks.

Kleinberg also will investigate the best ways to get information out of large distributed networks. He already has created web-searching systems based on the link structure of the net, rather than on the content of web pages, on the theory that sites to which many other sites provide links are the most likely to contain useful information. The hyperlinks of the web, he points out, form a sort of network of their own that is different from the physical network of computers and fiber optics over which they work. His results could apply not only to web searching but to all kinds of information links, like those that are created by references in scientific papers or connections in computer databases.

Related Websites:

• Jon Kleinberg: http://www.cs.cornell.edu/annual_report/1997/kleinberg.htm
• Cornell Computer Science department: http://www.cs.cornell.edu/