CAREER: Fundamental Lower Bound and Tradeoff Problems in Networking

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

In this research the PI will investigate the fundamental tradeoff, lower bound, and impossibility results in important areas of computer networks. Such results are important since they typically end the vigorous search for a better algorithm that does not exist, or lead to provably optimal algorithms. They will also help clarify the fundamental issues and structures of the problem domain under study. Obtaining such results is challenging because they require a deep understanding of the domain knowledge and a solid background in theoretical computer science. In the beginning, the PI will focus on lower bound and tradeoff results in two main areas: (1) packet scheduling, and (2) peer-to-peer (P2P) networks. In the research on lower bound problems in packet scheduling, the PI plans to extend the accomplished tradeoff results between delay bound and computational complexity to a much stronger and more practical computational model. The PI will also look into the complexity of establishing other QoS guarantees such as bandwidth, jitter bound and short-term fairness. Finally, the PI will study the complexity needed to exactly track the GPS (General Processor Sharing) clock, and/or to approximate GPS time within a certain error range. In the research on lower bound problems in P2P networks, the PI plans to continue his research on the tradeoffs between the routing table size and network diameter in P2P networks, and answer the fundamental research questions such as "what is tradeoff between the fault-tolerance overhead of the P2P routing algorithms and their routing efficiency?." In addition to investigating lower bound and tradeoff problems in these two areas, the PI will apply the insights and expertise obtained to other areas of networking such as application-level multicast and mobile computing. The goal of the proposed project is not only to advance research on theoretical and foundational aspects of networking, but also to educate and prepare graduate as well as undergraduate students for identifying, characterizing and answering such theoretical questions. The PI observes that there is limited coverage of such issues in the conventional networking curriculum. To fill this gap, the PI will actively take part in synergistic educational activities including curriculum development, course teaching, student mentoring, and professional skill development. Since the proposed work on lower bounds and tradeoffs is fundamental research, it has the potential to significantly impact the networking field in multiple dimensions. First, such results delineate feasible "regions" in which an algorithm can achieve with given assumptions. Second, during this process, it significantly clarifies the issues and structures of the problem, which may lead to new problems to solve. Finally, in cases where existing algorithms are not yet optimal, the tradeoff research guides researchers to find algorithms that are better or optimal. Although the proposed research is theoretical in nature, it has important applications to real algorithms and protocols, and constitutes a fundamental contribution if successful. The broader impact of the work includes the PI's sustained outreach efforts to broaden the participation of under-represented groups (HBCU institutions) in research and education, and to engage undergraduate students in theoretical networking research.