University of Illinois computer science professor Brighten Godfrey has been awarded $450,000 by the National Science Foundation for his group's effort in designing scalable, low latency networks.
The project focuses on routing, the process of finding paths between sources and destinations. Routing protocols work behind the scenes to decide what path each packet should follow as it flows through the Internet towards its destination. Today's big networks, like the Internet, scale to large size by making routing decisions in a hierarchical manner; but this approach unfortunately can result in paths much longer than optimal. Even more delay is added to translate a name that's useful to humans, like "www.illinois.edu", into an IP address that helps the routing protocol locate the destination. This "name resolution" process, which is the job of the Internet’s Domain Name System (DNS), might require the message to travel across the world even if the destination is next door. The resulting delay can be important. A study by Google, for example, showed that even a tenth of a second of added latency has a significant impact on how often users perform searches, and name resolution can take much longer than this. Going far out of the way also makes the network more unreliable.
"Our work takes a substantially different approach by routing given only arbitrary names, or 'flat names' as they're sometimes known to emphasize the difference with hierarchical IP addresses," said Godfrey. The project has built a system, called Disco, that routes directly on location-independent names, while guaranteeing that packets will be sent along near-optimal paths and that routers require only a limited amount of memory to choose the routes. This design provides a way to guarantee more responsive, scalable networks.
"Routing based on a flat name would be easy if we could simply tell every router what is the shortest path to every destination name; but that has no hope of working in very large or resource-constrained networks. So, the trick is to simultaneously find short routes and not require much communication or memory," Godfrey said.
To accomplish that goal, Disco builds on advances in compact routing theory. But while past work in this area assumed centralized routing table construction and an unchanging network, Disco solves a key challenge by providing the above guarantees via a practical dynamic distributed protocol. The research team is also addressing important practical challenges such as interdomain routing policies, congestion, and heterogeneity in the capabilities of routers, as well as applications to the Internet, content-centric, and other networks.
A paper on the work, by graduate student Ankit Singla, Godfrey, and researchers at Intel Labs Berkeley, was presented at the ACM CoNEXT conference in Philadephia in December.
Ph.D. student Rachit Agarwal, Godfrey, and computer science professor Sariel Har-Peled are also exploring how properties of realistic networks can be exploited to find even better routes.
"In general, routing protocols 'stretch' routes somewhat beyond the actual shortest paths, in exchange for ensuring that these routes can be found efficiently. Although the best possible ways of doing this have been characterized in theory, they are best only for networks with a ridiculously large number of links," said Godfrey.
Social networks, for example, have a limited number of connections -- one might have hundreds of friends, but not 500 million -- and this rule applies to realistic computer networks as well.
In such "sparse" networks, the researchers showed that routes could be provably shortened via a lightweight exchange of a few kilobytes of data between the source and destination, efficiently finding the exact shortest paths in a surprisingly large number of cases. A paper describing the technique will be presented at IEEE INFOCOM 2011.
Ultimately, the results of this project can make networks more responsive, scalable, and fault-tolerant, bridging a gap between promising theoretical results and emerging practical needs.