Laboratory of Networked Systems

Computer Science Department, Yale University

REIN: Robust and Efficient Internet Infrastructure

The phenomenal growth of computer networks has far outpaced our development of fundamental principles to understand them and practical techniques to effectively manage our computer network infrastructure. There are two substantial and engaging technical challenges:

Members

  • Hao Wang
  • Haiyong Xie
  • Multiple autonomous entities: A particular character of many computer networks is that their infrastructure is controlled by multiple autonomous entities. For example, the global Internet consists of a large number of interconnected autonomous systems (ASes), each of which owns part of the global Internet and conducts its own network management; the emerging peer-to-peer paradigm empowers end hosts to improve their collective application performance, but often is at odds with network provider traffic management.

  • Uncertainty: The second challenge is that there is always substantial uncertainty when making network management decisions. A decision maker is limited not only by possessing only partial information due to decentralized control but also by the impossibility of predicting the future in terms of traffic demand and/or network topology status.
How to understand and design robust networks where these self-interested entities optimize their individual objectives under uncertainty is among the most fundamental challenges in computer networks. A key objective of our group is to make contributions to both the fundamental scientific advancement and the practical deployment in this fascinating, challenging and important field. Our research so far has focused on the following perspectives.

Robust Intradomain Traffic Engineering

How to achieve robust routing under traffic and topology uncertainties. In [SIGCOMM06], we develop the framework of Common-case Optimization with Penalty Envelope (COPE) framework to improve robustness and stability with little loss of efficiency. In [SODA07], we develop techniques to be robust against peering links. In a recent paper, we develop techniques to be robust against multiple failures.

Stable and Efficient Interdomain Traffic Engineering

Internet traffic engineering deals with how traffic should be distributed among the autonomous networks (called domains) in the Internet. A key challenge here is that the traffic distribution decisions are decentralized. To emphasize this multi-domain perspective, Internet traffic engineering involving multiple domains is referred to as interdomain traffic engineering. Although the importance of interdomain traffic engineering is widely realized, it is also recognized that the state of art for interdomain traffic engineering is extremely ad hoc and primitive. The lacking in both fundamental understanding and capability has led to low robustness, instability, and low efficiency. As an example, during one recent event on January 9, 2006, the Sprint backbone network was partitioned with just two link failures, even though there was enough redundancy in the Internet to avoid the partition. The partition led to the disconnection of long-distance service for millions of Sprint PCS and Nextel wireless customers west of the Rockies, and network partitions of many corporate networks relying on the carrier. Our research on interdomain traffic engineering started with the observation that we lack fundamental understanding on this crucially important subject. Our first progress is the recognition that interdomain traffic engineering is essentially a social choice problem (i.e., aggregating individual domain preferences to form a collective preference; see our IBC paper). This novel perspective immediately reveals fundamental tradeoffs that must be made on designing any interdomain traffic engineering systems. Although some results are impossibility results, this research, puts a science boundary on the largely ad hoc engineering design. Integrating the descriptive model with the notion of rational route selection (see [ICNP 2006]) to model operational protocols, this research not only demonstrates the potential instability of the prevailing interdomain traffic engineering practices but also establishes provably-stable interdomain traffic engineering guidelines. Guided by the fundamental understanding, this research develops methodology for achieving robust, efficient traffic engineering. For example, the Reliability as an Interdomain Service (REIN) framework [SIGCOMM07] overcomes the fundamental limitation of individual traffic engineering, by prompting interdomain collaboration to address challenges such as the aforementioned Sprint event.

Integration of Applications into Network Traffic Management

Members

  • Haiyong Xie
  • Glenn Thorpe
The multi-domain structure addressed in the REIN project is fundamental but does not account for all of the challenges facing Internet traffic engineering. The additional player here is the applications, who ultimately generate Internet traffic. While traditional applications (e.g., Web) yield all routing decisions to the networks, new adaptive applications such as the overlay and peer-to-peer (P2P) applications (e.g., BitTorrent) conduct network-oblivious, application-oriented routing. In less than five years, the amount of peer-to-peer traffic in the Internet has increased from zero to 50-80% of current total Internet traffic. These adaptive applications, as our research first discovered [SIGCOMM04], can interact poorly with Internet traffic engineering and lead to significant instability and inefficiency for both the applications and the networks. In a most fundamental level, this discovery reveals that there is a fundamental issue in the traditional Internet traffic engineering architecture: emerging applications can have tremendous flexibility in how data is communicated; thus, they should be an integral part of Internet traffic engineering. However, if end hosts are to participate in network resource optimizations, then the networks cannot continue to be opaque but need to export their status and policy information. Motivated by this observation, we design a new network architecture to integrate such applications.

High Capacity and Incentive-compatible Wireless Access

Members

  • Richard Alimi
  • Xueyuan Su
For related papers, please see here.

End Host Fairness and Rate Control

For related papers, please see here.

Network Localization

Members

  • David Goldenberg
For related papers, please see here.

Security and Privacy

For related papers, please see here.

LANS at Yale University. Initial CSS template from free css templates. Last modified at $Id$