CAREER: Fundamental Lower Bound and Tradeoff Problems in Networking

在这项研究中，PI将调查计算机网络重要领域中的基本权衡、下限和不可能性结果。这样的结果很重要，因为它们通常会结束对不存在的更好算法的激烈搜索，或者导致可证明是最优的算法。它们还将有助于澄清正在研究的问题领域的基本问题和结构。要获得这样的结果是具有挑战性的，因为它们需要对领域知识的深入理解和扎实的计算机科学理论背景。在一开始，PI将专注于两个主要领域的下界和权衡结果：(1)分组调度，(2)对等(P2P)网络。在分组调度下界问题的研究中，PI计划将已有的延迟界和计算复杂度之间的折衷结果扩展到一个更强大、更实用的计算模型。PI还将调查建立其他服务质量保证(如带宽、抖动限制和短期公平性)的复杂性。在P2P网络下界问题的研究中，PI计划继续研究P2P网络中路由表大小和网络直径之间的权衡问题，并回答P2P路由算法的容错开销和路由效率之间的权衡问题。除了调查这两个领域的下限和权衡问题外，PI还将把获得的洞察力和专业知识应用于其他网络领域，如应用层组播和移动计算。拟议项目的目标不仅是促进网络理论和基础方面的研究，而且还教育和准备研究生和本科生识别、表征和回答此类理论问题。PI注意到，传统网络课程中对此类问题的覆盖范围有限。为了填补这一空白，PI将积极参与协同教育活动，包括课程开发、课程教学、学生指导和专业技能发展。由于拟议的下限和权衡工作是基础研究，它有可能在多个维度显著影响网络领域。首先，这样的结果描述了算法在给定假设下可以实现的可行“区域”。其次，在这一过程中，它显著澄清了问题的问题和结构，这可能会导致新的问题需要解决。最后，在现有算法还不是最优的情况下，权衡研究指导研究人员找到更好或最优的算法。虽然所提出的研究本质上是理论上的，但它在实际算法和协议中具有重要的应用，如果成功，将构成一个根本性的贡献。这项工作的更广泛影响包括，国际和平研究所继续努力扩大代表性不足群体(HBCU机构)对研究和教育的参与，并让本科生参与理论网络研究。

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.