News Release

Cyber jams

Peer-Reviewed Publication

Office of Naval Research

You go online, type in a web address, and wait... and wait... and wait. A traffic jam on the information superhighway has slowed communications traffic down to a crawl. Going online these days can be as frustrating as driving during rush hour. A Cornell University computer scientist believes he can make networks operate more efficiently by focusing on the routing problems of the Internet. In routing information on a network, different "packets" of information compete for room on the network's links. The router "decides" how to allocate the available capacity. For example, a router in New York City, seeing a packet addressed to San Francisco, probably wouldn't send it straight there, but more likely to Buffalo, or Atlanta, and trust the router there to pass it along in the right direction. A three-year, $305,000 grant from the Office of Naval Research is making it possible for Professor Jon Kleinberg to analyze techniques that fairly allocate the available capacity of a network's links. His work to date reveals that finding the fairest allocation is computationally intractable, but that finding an allocation that is approximately fair can be done very efficiently. Ultimately, the algorithms Kleinberg develops could be applied to other kinds of networks, such as telephone systems, power grids, and traffic lights.

###


Disclaimer: AAAS and EurekAlert! are not responsible for the accuracy of news releases posted to EurekAlert! by contributing institutions or for the use of any information through the EurekAlert system.