CAREER: Fundamental Lower Bound and Tradeoff Problems in Networking

在这项研究中，PI将调查计算机网络的重要领域中的基本权衡，下限和不可能结果。 这样的结果很重要，因为它们通常会结束对不存在的更好算法的积极搜索，或者导致可证明的最佳算法。 它们还将有助于澄清所研究问题领域的基本问题和结构。获得这样的结果是具有挑战性的，因为它们需要对该领域知识的深刻理解和坚实的理论计算机科学背景。在开始时，PI将专注于两个主要领域的下限和权衡结果：（1）分组调度，和（2）对等（P2P）网络。在分组调度下界问题的研究中，PI计划将已完成的延迟界和计算复杂度之间的折衷结果扩展到更强大和更实用的计算模型。 PI还将研究建立其他QoS保证的复杂性，例如带宽、抖动界限和短期公平性。 最后，PI将研究精确跟踪GPS所需的复杂性（通用处理器共享）时钟，和/或在一定误差范围内近似GPS时间。在P2P网络中的下界问题的研究中，PI计划继续研究P2P网络中路由表大小和网络直径之间的权衡，并回答了“P2P路由算法的容错开销和路由效率之间的权衡是什么？”等基本研究问题。" 除了调查这两个领域的下限和权衡问题外，PI还将把所获得的见解和专业知识应用于网络的其他领域，如应用级组播和移动的计算。拟议项目的目标不仅是推进网络理论和基础方面的研究，而且还教育和准备研究生和本科生，对这些理论问题的描述和回答。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.