Design and Analysis of Internet Algorithms: Routing, Filtering, Overlay Design and Influence of Heterogeneity

University Of California-Berkeley, Berkeley CA

Investigators

Abstract

This research concerns protocols used for the efficient transmission of data in the Internet and other distributed communication networks, such as wireless networks. The research focuses on routing, congestion control and heterogeneity. Routing concern the choice of routes for messages and the enforcement of those routes by local decisions governed by routing tables stored at the routers. It is a fundamental constraint that the sizes of these tables must be small. Congestion control strives to reduce congestion by selectively dropping packets from flows that are receiving more than their fair share of bandwidth. The issue of heterogeneity is whether it is better to have the capacity of a distributed system divided evenly or unevenly among its processors. Geographic routing assigns coordinates to each processor, placing it in a metric space. The research investigates the correctness and efficiency of geographic routing schemes. Special cases of geographic routing include greedy routing, in which each hop is chosen to minimize distance to the destination, and beacon routing, in which each coordinate of a host gives the minimum number of hops from the host to a selected beacon node. The research explores the loss of efficiency imposed by routing constraints of the type arising in the Border Gateway Protocol. The ability of overlay nodes to improve routing efficiency is explored. The construction of compact multicast routing tables is investigated. Efficient methods are given for identifying high-rate flows and dropping their packets preferentially. Finally, evidence is provided that systems are more robust when their capacity is distributed heterogeneously among the processors.