CIF: Small: Removing Inherent Instabilities in Communication Networks

Columbia University, New York NY

Investigators

Abstract

Proposal 0915784: Removing Inherent Instabilities in Communication Networks Abstract Since 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.