Traffic is getting worse every day. Not just on city streets and freeways: on the Inter-net, cellular phone systems and other communication networks. Computer scientist Jon Kleinberg has received a three-year grant totaling $305,000 from the Office of Naval Research to study ways to make networks like these more efficient.
Kleinberg, an assistant professor of computer science, is a specialist in algorithms, the problem-solving strategies on which computer programs are built. While he will focus on 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 and the paths are communication lines over which information travels in small bursts called "packets." Each packet contains the address of the computer to which it is going, and computers called "routers" look at the address and send the packet along the best route to its destination. A packet from New York addressed to San Francisco might be sent to Buffalo, Atlanta or Columbus, and a router there would send it on in the right direction.
But suppose a router along the way happens to serve a web site that is getting millions of "hits" per day. 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 pointed out. One of the questions he wants to investigate is how best to use that information. Routing might also be improved, he added, by giving routers a way to guess from recent experience how many requests will be coming in the immediate future.
Another question is how computers should assign priorities to incoming requests. "Some people request large amounts of information, some small," Kleinberg explained. "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, Klein-berg said, can help in designing the networks of the future. He 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.
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.
| Cornell Chronicle Front Page | | Table of Contents | | Cornell News Service Home Page |