CIF: Small: Removing Inherent Instabilities in Communication Networks

提案0915784：消除通信网络固有的不稳定性摘要自60年代末以来，通信网络经历了巨大的变化，包括：增长到不可预见的规模；在非常动态和不利的条件下操作；全媒体存储传输一体化；在我们生活的方方面面无处不在；等。展望未来，这些趋势将继续增加和扩大，导致对现有网络的压力越来越大，因此，越来越重视新的网络设计，通常被称为？层次清晰的架构?。因此，为了寻求更好的设计，有必要重新审视现有的网络设计原则，特别是那些固有的所有网络层，如基于重传的故障恢复。为此，研究人员最近的工作发现了一种全新的网络现象，表明即使所有的流量和网络特征都是轻尾的，例如指数或高斯，重传也会导致长尾延迟和不稳定。这一发现对于以频繁故障为特征的高度拥塞的多跳无线网络尤其重要，例如ad hoc和传感器网络。由于基于重传的故障恢复是现有网络的核心，这一新现象为该领域沿着垂直（协议栈）、时间和空间网络维度的更多发现奠定了基础。此外，本研究还调查了广泛部署的公平资源共享机制是如何带来代价的，因为它们可能负责将长尾延迟传播到整个网络。最后，基于对现有协议的批判性研究，研究者对网络协议进行了仔细的重新设计，这些协议被证明会导致或传播长时间的延迟和不稳定性。一般关注的是设计易于实现、自适应、可扩展和可证明接近最优的算法。

Proposal 0915784: Removing Inherent Instabilities in Communication NetworksAbstractSince the late 60s, communication networks have experienced dramatic changes, including: growth to unforeseen scales; operation under very dynamic and adverse conditions; integration of storage and transfer of all media; ubiquitous presence in all parts of our lives; etc. Going forward, these trends will continue to increase and broaden, resulting in mounting stress on the existing networks and, thus, growing emphasis on new network designs, often referred to as the ?clean-slate architectures?.Hence, in search of better designs, it is necessary to reexamine the existing network design principles, especially those that are inherent to all networking layers, such as the retransmission-based failure recovery. To this end, recent work by the investigator discovers an entirely new networking phenomenon by showing that retransmissions can cause long (-tailed) delays and instabilities even if all traffic and network characteristics are light-tailed, e.g. exponential or Gaussian. This finding is especially crucial for highly congested multi-hop wireless networks that are characterized by frequent failures, e.g. ad hoc and sensor networks. Since the retransmission-based failure recovery is at the core of the existing networks, this new phenomenon sets the basis for many more discoveries in this domain along the vertical (protocol stack), temporal and spatial network dimensions. Furthermore, this research also investigates how widely deployed fair resource sharing mechanisms come with a price since they may be responsible for spreading the long-tailed delays to the entire network. Finally, based on the critical study of the exiting protocols, the investigator pursues careful redesign of network protocols that are shown to cause or spread long delays and instabilities. The general focus is on designing algorithms that are easy to implement, adaptive, scalable and provably near-optimal.