Northeastern University Rajaraman, Rajmohan
How blissful is ignorance? The role of obliviousness in network optimization
The next-generation Internet will be orders of magnitude bigger in scale, connecting together nodes that are very different in their capabilities and requirements. Traditional algorithm design has tended to focus on problems with complete information over a homogeneous platform. However, the dramatic increase in scale and heterogeneity means that nodes can neither hope to obtain nor store and process full information. Therefore, it is important today to focus on algorithms and protocols that can operate obliviously, i.e., with limited knowledge. This research develops formal frameworks for quantifying the associated tradeoffs in oblivious network optimization and delivers infrastructure-class algorithms that can secure the foundations of the Internet of tomorrow. This project also trains students in the design of advanced network infrastructure and incorporates the research into the curriculum for algorithms and networking.
The focus of this research is three-fold. The first component concerns oblivious algorithms for network design through universally approximate solutions that simultaneously approximate the optimal over all possible inputs. The investigators study the TSP, Steiner tree, and other fundamental optimization problems within this framework, and also apply these ideas to protocols for data acquisition in sensor networks. The second component of this project is the design of fault-oblivious algorithms for load balancing and scheduling that can offer performance guarantees for arbitrary unknown and unpredictable fault patterns. The third component of this research is confluent routing, which is a source-oblivious approach to routing that increases efficiency while maintaining scalability.
