Scott Shenker

Rollback-Recovery for Middleboxes

By: 
Justine Sherry, Peter Xiang Gao, Soumya Basu, Aurojit Panda, Arvind Krishnamurthy, Christian Maciocco, Maziar Manesh, Jo?o Martins, Sylvia Ratnasamy, Luigi Rizzo, Scott Shenker
Appears in: 
CCR August 2015

Network middleboxes must offer high availability, with automatic failover when a device fails. Achieving high availability is challenging because failover must correctly restore lost state (e.g., activity logs, port mappings) but must do so quickly (e.g., in less than typical transport timeout values to minimize disruption to applications) and with little overhead to failure-free operation (e.g., additional per-packet latencies of 10-100s of us). No existing middlebox design provides failover that is correct, fast to recover, and imposes little increased latency on failure-free operations.

SDX: a software defined internet exchange

By: 
Arpit Gupta, Laurent Vanbever, Muhammad Shahbaz, Sean P. Donovan, Brandon Schlinker, Nick Feamster, Jennifer Rexford, Scott Shenker, Russ Clark, Ethan Katz-Bassett
Appears in: 
CCR August 2014

BGP severely constrains how networks can deliver traffic over the Internet. Today’s networks can only forward traffic based on the destination IP prefix, by selecting among routes offered by their immediate neighbors. We believe Software Defined Networking (SDN) could revolutionize wide-area traffic delivery, by offering direct control over packet-processing rules that match on multiple header fields and perform a variety of actions.

SDX: a software defined internet exchange

By: 
Arpit Gupta, Laurent Vanbever, Muhammad Shahbaz, Sean Patrick Donovan, Brandon Schlinker, Nick Feamster, Jennifer Rexford, Scott Shenker, Russ Clark, Ethan Katz-Bassett
Appears in: 
CCR August 2014

BGP severely constrains how networks can deliver traffic over the Internet. Today’s networks can only forward traffic based on the destination IP prefix, by selecting among routes offered by their immediate neighbors. We believe Software Defined Networking (SDN) could revolutionize wide-area traffic delivery, by offering direct control over packet-processing rules that match on multiple header fields and perform a variety of actions.

Troubleshooting blackbox SDN control software with minimal causal sequences

By: 
Colin Scott, Andreas Wundsam, Barath Raghavan, Aurojit Panda, Andrew Or, Jefferson Lai, Eugene Huang, Zhi Liu, Ahmed El-Hassany, Sam Whitlock, H.B. Acharya, Kyriakos Zarifis, Scott Shenker
Appears in: 
CCR August 2014

Software bugs are inevitable in software-defined networking control software, and troubleshooting is a tedious, time-consuming task. In this paper we discuss how to improve control software troubleshooting by presenting a technique for automatically identifying a minimal sequence of inputs responsible for triggering a given bug, without making assumptions about the language or instrumentation of the software under test.

Architecting for Innovation

By: 
Teemu Koponen, Scott Shenker, Hari Balakrishnan, Nick Feamster, Igor Ganichev, Ali Ghodsi, P. Brighten Godfrey, Nick McKeown, Guru Parulkar, Barath Raghavan, Jennifer Rexford, Somaya Arianfar, and Dmitriy Kuptsov
Appears in: 
CCR July 2011

We argue that the biggest problem with the current Internet architecture is not a particular functional deficiency, but its inability to accommodate innovation. To address this problem we propose a minimal architectural “framework” in which comprehensive architectures can reside. The proposed Framework for Internet Innovation (FII) — which is derived from the simple observation that network interfaces should be extensible and abstract — allows for a diversity of architectures to coexist, communicate, and evolve.

YAMR: Yet Another Multipath Routing Protocol

By: 
Igor Ganichev, Bin Dai, P. Brighten Godfrey, and Scott Shenker
Appears in: 
CCR October 2010

Multipath routing is a promising technique to increase the Internet’s reliability and to give users greater control over the service they receive. However, past proposals choose paths which are not guaranteed to have high diversity. In this paper, we propose yet another multipath routing scheme (YAMR) for the interdomain case. YAMR provably constructs a set of paths that is resilient to any one inter-domain link failure, thus achieving high reliability in a systematic way.

Public Review By: 
J. Wang

This paper presents an Interdomain multipath routing protocol. Multipath routing has been shown to be a promising technique to increase reliability of Internet routing and provide greater flexibility for users to choose paths that best suit their needs. In recent years, many schemes have been proposed to support multipath interdomain routing. These existing works demonstrated the feasibility of providing alternative paths in a scalable and policy-compliant manner. In this work, authors propose “Yet Another Multipath Routing Protocol” (YAMR). The contributions of this paper are two-fold. The paper first presents a path calculation mechanism called YPC. YPC constructs a set of policy-complaint interdomain routing paths which tolerant any single interdomain link failure. However, the increase in path resiliency comes at a price: a considerable increase in the control message overhead imposed by alternative path advertisement. The paper then presents a mechanism which reduce control message overhead by localizing routing updates. The idea is that a router does not notify its neighbors failure event if it still has an available path to reach the same destination. This method can effectively reduce the control message overhead. To avoid forwarding loops and disconnectivity due to information hiding, a token is used as a signal to determine if information hiding is needed or not. All reviewers found that this failure hiding mechanism is quite interesting.
The paper uses simulations to evaluate the benefit of YAMR and compares it with BGP. The results show that YAMR not only outperforms BGP in terms of reliability, but also bests BGP in terms of control message overhead (a benefit from failure hiding). These results clearly demonstrate that YAMR is a promising technique for multipath interdomain routing. The current evaluation is based on synthetic topology. It would be interesting to see how YAMR performs on the real Internet topology. In addition, there are many interesting performance tradeoffs that clearly need careful exploration. For example, YPC requires each router to keep a set of alternative forwarding paths. This would incease router FIB size consumption. This can be a concern that impacts the routing scalability. What would be the ideal tradeoff between the increase in path diversity and the increase in router FIB size? The failure hiding mechanism can lead to inconsistency between the control plane and the data plane. To what extend would this inconsistency impact the failure resilience and existing routing dependent systems on the Internet? All of these tradeoffs warrant further exploration.

Dynamic route recomputation considered harmful

By: 
Matthew Caesar, Martin Casado, Teemu Koponen, Jennifer Rexford, and Scott Shenker
Appears in: 
CCR April 2010

This paper advocates a different approach to reduce routing convergence—side-stepping the problem by avoiding it in the first place! Rather than recomputing paths after temporary topology changes, we argue for a separation of timescale between offline computation of multiple diverse paths and online spreading of load over these paths. We believe decoupling failure recovery from path computation leads to networks that are inherently more efficient, more scalable, and easier to manage.

Pathlet Routing

By: 
P. Brighten Godfrey, Igor Ganichev, Scott Shenker, and Ion Stoica
Appears in: 
CCR October 2009

We present a new routing protocol, pathlet routing, in which networks advertise fragments of paths, called pathlets, that sources concatenate into end-to-end source routes. Intuitively, the pathlet is a highly exible building block, capturing policy constraints as well as enabling an exponentially large number of path choices. In particular, we show that pathlet routing can emulate the policies of BGP, source routing, and several recent multipath proposals.

Accountable Internet Protocol (AIP)

By: 
David G. Andersen, Hari Balakrishnan, Nick Feamster, Teemu Koponen, Daekyeong Moon, and Scott Shenker
Appears in: 
CCR October 2008

This paper presents AIP (Accountable Internet Protocol), a networkarchitecture that provides accountability as a first-order property.AIP uses a hierarchy of self-certifying addresses, in which eachcomponent is derived from the public key of the correspondingentity. We discuss how AIP enables simple solutions to sourcespoofing, denial-of-service, route hijacking, and route forgery. Wealso discuss how AIP’s design meets the challenges of scaling, keymanagement, and traffic engineering.

Packet Caches on Routers: The Implications of Universal Redundant Traffic Elimination

By: 
Ashok Anand, Archit Gupta, Aditya Akella, Srinivasan Seshan, and Scott Shenker
Appears in: 
CCR October 2008

Many past systems have explored how to eliminate redundant transfers from network links and improve network efficiency. Several of these systems operate at the application layer, while the more recent systems operate on individual packets. A common aspect of these systems is that they apply to localized settings, e.g. at stub network access links. In this paper, we explore the benefits of deploying packet-level redundant content elimination as a universal primitive on all Internet routers. Such a universal deployment would immediately reduce link loads everywhere.

Syndicate content