November 2008 - talks - lists.cs.princeton.edu

1:30-2:30pm Fri Dec 5 talk on Effective Diagnosis of Routing Disruptions from End Systems
by Jennifer Rexford 30 Nov '08

30 Nov '08

Invited talk, note the unusual room (CS 102). Please let me know if you would like to meet with Morley Mao while she is here. Speaker: Professor Morley Mao, U. Michigan Title: Effective Diagnosis of Routing Disruptions from End Systems Date/time: 1:30-2:30pm Friday December 5 Room: 102 in the CS building Abstract: Internet routing events are known to introduce severe disruption to application performance. So far effective diagnosis of routing events has relied on proprietary ISP data feeds, resulting in limited ISP-centric views not easily accessible by customers or other ISPs. In this work, we propose a novel approach to diagnosing significant routing events associated with any large networks from the perspective of end systems. Our approach is based on scalable, collaborative probing launched from end systems and does not require proprietary data from ISPs. Using a greedy scheme for event correlation and root cause inference, we can diagnose both interdomain and intradomain routing events. Unlike existing methods based on passive route monitoring, our approach is able to measure the impact of routing events on end-to-end network performance as well. We demonstrate the effectiveness of our approach by studying five large ISPs over more than three and half months. We validate the accuracy of our approach by comparing with the existing ISP-centric method and with events reported on NANOG mailing lists. Our work is the first to scalably and accurately diagnose routing events associated with large networks purely from end systems. Bio: Z. Morley Mao is an assistant professor of Computer Science and Engineering at the University of Michigan. Morley received her Ph.D., M.S., and B.S. from the University of California at Berkeley. She is a recipient of the NSF CAREER award in 2007, an IBM Faculty Award in 2008, and was recently named the Morris Wellman Faculty Development Professor. Her research interests include network measurements, routing protocols, distributed systems, and network security.

1 1

Yi Wang preFPO
by Melissa Lawson 26 Nov '08

26 Nov '08

Yi Wang will present his preFPO on Wednesday December 3 at 1:30 PM in Room 401. The members of his committee are: Jennifer Rexford, advisor; Michael Freedman and Kobus van der Merwe (AT&T), readers; Larry Peterson and Ed Felten, nonreaders. Everyone is invited to attend his talk. His abstract follows below. ------------------------------------ Title: A Principled Approach to Managing Routing in Large ISP Networks Abstract: Today's Internet Service Providers (ISPs) face a number of challenges in introducing changes to their networks at different frequencies. Firstly and most frequently, ISPs need to perform daily planned maintenance to keep their networks running healthily. However, despite of the importance and frequency of the planned maintenance operation, there is no existing method that can handle such operations without causing packet losses and routing protocol re-convergence. Secondly, once in a while, ISPs have to adjust their routing policies to meet changing needs and make flexible trade-offs between different policy objectives (such as business relationships, performance, security, etc.). However, today's network architecture forces administrators to realize network- wide routing policies through router-level configurations and makes it very difficult (if not impossible) to make flexible trade-offs. Thirdly, ISPs also have the incentive to make a one-time change (transition) from the current restrictive route-selection model, in which each router selects a single best route for all neighbors, to a neighbor- specific route-selection model, in which each router can provide value-added customized route- selection services to different neighbors. However, it is currently unknown if such transition to a more flexible route-selection model may cause the Internet routing to oscillate. In this thesis, we take a principled approach to solving these "change-related" challenges and propose three abstractions that guide the design and implementation of our system solutions. First, we propose the abstraction of a "neighbor-specific route selection problem" and a corresponding "Neighbor-Specific BGP" (NS- BGP) model that capture the requirement of customized route selection for different neighbors. We prove that the Internet is guaranteed to remain stable even if individual ISPs make transition to this more flexible route-selection model incrementally. Second, we propose the abstraction of "policy configuration as a decision problem of reconciling multiple objectives". Guided by this abstraction and the Analytic Hierarchy Process, a decision-theoretic technique for balancing conflicting objectives, we designed and implemented a prototype of an extensible routing control platform (Morpheus) that enables an ISP to select routes for different neighbors individually and make flexible trade-offs among policy objectives through a simple and intuitive configuration interface. Finally, we propose the abstraction of the separation between "physical" and "logical" configurations of routers, which leads us to the design and prototype implementation of "virtual router migration" (VROOM), a new, generic technique to simplify/enable a broad range of tasks that require the network to adapt in certain ways, from planned maintenance to reducing power consumption. Collectively, the contributions of the thesis provide simple and effective solutions for an ISP to autonomously introduce changes to its network at various frequencies without sacrificing global routing stability.

1 0

Bill Press speaking at PICASso today, 12:30
by Elena Zaslavsky 24 Nov '08

24 Nov '08

Bill Press of "Numerical Recipes in C" speaking at PICASso today. From: picasso-bounces(a)lists.cs.princeton.edu [mailto:picasso-bounces@lists.cs.princeton.edu] On Behalf Of Cecile Huttenhower Sent: Monday, November 24, 2008 9:12 AM To: picasso-faculty(a)lists.cs.princeton.edu; picasso(a)lists.cs.princeton.edu Subject: [PICASso] TODAY - What Is a Statistical Model and When Do I Need One? ** PICASso: ** Program in Integrative Information, Computer and Application Sciences ** www.cs.princeton.edu/picasso ** ** TALK TODAY -- Monday, November 24, 2008 Interdisciplinary Computational Seminars http://www.cs.princeton.edu/picasso/computational_lunch.php TITLE: What Is a Statistical Model and When Do I Need One? SPEAKER: Bill Press, CS, U. Texas TIME: Monday, November 24, 2008 Seminar begins at 12:30 p.m. (lunch provided ~12:20) LOCATION: Room 104, Computer Science, Princeton University ABSTRACT: Whether by differential equations (ODEs or PDEs) or algebraic systems of equations, computational science traffics mainly in deterministic models of physical systems. While we sometimes make the mistake of thinking that the model "is" the physical system, it is always only an abstract, and approximate, representation. Statistical models are a different kind of abstraction, not for the deterministic part of a system, but for how it interacts with physical stochasticity and/or with Bayesian priors expressing imperfect knowledge. This talk compares statistical and deterministic models, using examples drawn from cosmology and bioinformatics. SIGN UP FOR THE PICASSO MAILING LIST: ===================================== If you would like to be kept informed of computationally-oriented events in (and around) Princeton, please SUBSCRIBE to the PICASso mailing list by visiting https://lists.cs.princeton.edu/mailman/listinfo/picasso. This page also contains information on how to UNSUBSCRIBE. PLEASE FORWARD THIS MESSAGE TO OTHER COMPUTATIONALLY-ORIENTED RESEARCHERS WHO MAY BE INTERESTED IN THIS EVENT, OR FUTURE PROGRAMS. THANKS!

1 0

D Xiao preFPO
by Melissa Lawson 14 Nov '08

14 Nov '08

David Xiao will present his preFPO on Friday November 21 at 1PM in Room 402. The members of his committee are; Boaz Barak, advisor; Avi Wigderson (IAS) and Russell Impagliazzo (IAS), readers; Sanjeev Arora and Rob Schapire, non-readers. Everyone is invited to attend his talk. His abstract follows below. New Connections Between Cryptography and Learning Cryptography and learning are intuitively inverse tasks: the first deals with obscuring information while the second aims to extract hidden information. Not surprisingly, many relationships were discovered early on between the two: a secure encryption system implies that learning how to decipher encrypted messages is hard, while on the other hand extremely powerful learning algorithms can potentially be used to break the security of cryptographic protocols. In this thesis, we deepen the understanding of the relationship between the complexity of these two tasks and use their relationship to inform the design of secure cryptographic protocols. In our first set of results, we investigate under what assumptions learning can be proven to be hard for polynomial-time algorithms. First we show that the assumption ZK != BPP (and in particular the worst-case hardness of problems such as Graph Isomorphism and Quadratic Residuosity) suffices to imply that learning is hard. We then show that on the other hand the weaker assumption P != NP is unlikely to imply that learning is hard via standard proof techniques. In our second result, we study secure fault localization in Internet routing. In this problem, a sending router and a receiving router wish to discover if there are any adversaries along the path between them causing faults, i.e. that are dropping or modifying packets. We build a formal model of security for this problem and show that in order to achieve security, the intermediate routers must share keys and perform cryptographic operations. This suggests that this security goal inherently requires expensive computation at all nodes in the network, not just the sender and receiver. Our result follows from applying a specific learning algorithm to breaking protocols that do not satisfy the requirements of keys and/or cryptographic operations at each intermediate router.

1 0

Syslunch presentation by Marc Shapiro (NOW!)
by Sapan Bhatia 11 Nov '08

11 Nov '08

Marc Shapiro is a director of research with INRIA and the chairmain of Eurosys, the ACM SIGOPS chapter of Europe. He is going to give a talk in today's systems lunch: Speaker: Marc Shapiro, INRIA and LIP6 Title: Telex: A Principled Platform for Peer-to-Peer Collaboration Abstract: Developers of co-operative applications encounter difficult issues of distributed state, disconnections, and conflicts. Our approach is to factor these system issues out from application logic, but we recognise that they cannot be entirely divorced. The Telex platform that we designed is application-independent, but parameterised by application-specific information. An application provides Telex with actions (operations) and constraints (invariants). In return, Telex takes care of replication and persistence, drives application progress while verifying its invariants, and ensures that replicas eventually agree on a correct, common state. Time permitting, I will present a number of contributions. I show by example how application design proceeds from high-level invariants to actions and constraints, and how the platform ensures application safety and liveness. The main data structure of Telex is a large, replicated, very dynamic graph; I discuss the engineering trade-offs for such a graph and our solutions. I describe our how Telex ensures, in the background, that replicas converge to a safe state. Finally, I describe experimental evaluation of the Telex platform. Joint work with Lamia Benmouffok, Jean-Michel Busca, Joan Manuel Marquhs, Marc Shapiro, Pierre Sutra, Georgios Tsoukalas

1 0

E Chlamtac FPO
by Melissa Lawson 10 Nov '08

10 Nov '08

Eden Chlamtac will present his FPO on Monday November 17 at 4PM in Room 402. The members of his committee are: Sanjeev Arora, advisor; Moses Charikar and Bernard Chazelle, readers; Ken Steiglitz and Boaz Barak, nonreaders. A copy of his thesis, "Non-Local Analysis of SDP-Based Approximation Algorithms", is on display in room 310. Everyone is invited to attend his talk.

1 0

J Lai FPO
by Melissa Lawson 10 Nov '08

10 Nov '08

Junwen Lai will present his FPO on Thursday November 13 at 11AM in Room 401 (note room). The members of his committee are: Kai Li, advisor; Larry Peterson and David August, readers; J.P. Singh and David Walker, nonreaders. A copy of his thesis, "Virtualizing Network File Systems" is available in Room 310. Everyone is invited to attend his talk.

1 0

Where’s Waldo? Practical Searches for Stability in iBGP
by Yi Wang 10 Nov '08

10 Nov '08

Hi all, Next Monday (November 10), Ashley Flavel from University of Adelaide will be giving a talk on modeling IGP/iBGP interaction. Both systems and theory people may find this talk interesting. Thanks, Yi -------------------------------------------------------- Time: 11:30-12:30, Monday November 10 Room: CS 301 Title: Where’s Waldo? Practical Searches for Stability in iBGP Abstract: What does a child’s search of a large, complex cartoon for the eponymous character (Waldo) have to do with Internet routing? Network operators also search complex datasets, but Waldo is the least of their worries. Routing oscillation is of much greater concern. One cause of such oscillations is the interaction between the routing protocols used for reaching internal (IGP) and external destinations (iBGP). In this talk we model the interaction between these two routing protocols and precisely identify where oscillation can occur due to the interaction, and where it cannot. We apply this analysis to the iBGP configuration of a large Tier-2 ISP and show that despite the problem being NP-hard, we can restrict our search to a feasible size in a realistic network. Short bio: Ashley Flavel is a Phd candidate at the University of Adelaide in the School of Applied Mathematics. He holds degrees from the University of Adelaide in both Telecommunications Engineering and Mathematical and Computer Science. His current research involves the measurement and modeling of the Border Gateway Protocol. He will be submitting his Phd thesis in late 2008.

1 1

1-2pm Fri Dec 12 on wireless interference by Ramki Gummadi in B205 in the E-Quad
by Jennifer Rexford 10 Nov '08

10 Nov '08

Speaker: Dr. Ramakrishna Gummadi, MIT Title: Interference rendered significantly harmless Location: B205 in the E-Quad (note: talk in ELE wing of E-Quad, not in CS building) Date/time: 1-2pm Friday December 12 Abstract: The throughput of existing wireless networks is often limited by interference. One fundamental reason is that the current designs are constrained by a "one-transmission-at-a-time" model at the link layer and a fixed-width spectrum allocation at the physical layer. We present a new wireless design that exploits traffic burstiness and node heterogeneity, thereby improving concurrency and spectrum usage. The main challenge is the unmanaged nature of many wireless networks such as 802.11 and mesh, which makes centralized resource allocation impractical. We show through analysis and implementation that simple randomized allocation policies can overcome this challenge, and improve throughput by 2x or more. This work is joint with Rabin Patra, Hari Balakrishnan and Eric Brewer. Bio: Ramakrishna Gummadi is a post-doc at the MIT Computer Science and Artificial Intelligence Laboratoray (CSAIL). He obtained his B.Tech. from IIT-Madras, M.S. from UC Berkeley and Ph.D. from USC, all in Computer Science. His dissertation was about reliable and efficient programming languages for sensor networks. He is interested in building scalable and reliable systems and networks based on sound principles. His awards include a UC Regents Graduate Fellowship, a best paper awarded out of all 2001 Journal of Computer Networks papers, a best poster/demo award at SenSys 2004, and an award at the ACM Student Research Competition (SRC) held at PLDI 2007.

1 0

E Karpilovsky preFPO
by Melissa Lawson 06 Nov '08

06 Nov '08

Elliott Karpilovsky will present his preFPO on Tuesday November 11 at 3PM in Room 402. The members of his committee are: Jennifer Rexford, advisor; Larry Peterson and Aman Shaikh (AT&T), readers; Vivek Pai and Mike Freedman, nonreaders. Everyone is invited to attend his talk. His abstract follows below. ----------------------------------- Title: "Reducing Memory Requirements for Routing Protocols" Abstract: With the rapid growth of the Internet, routers need more and more memory to forward packets to their correct destinations. Lack of sufficient memory can cause routers to crash, reject new routing information, or enter into indeterminate state, as current protocols and systems do not deal gracefully with memory exhaustion. Current "solutions" are often ineffective, as they typically rely on over-provisioning memory (an expensive and sometimes infeasible solution), or in restricting the set of routes that can be learned (and such restrictions must be very loose, to ensure routers have alternate paths to use in the event of a failure). Our study measures the deployment of routing protocols, along with the burdens they impose on routers. We evaluate two different ways to reduce router memory requirements, and additionally investigate how router memory requirements might change in the future, due to emerging protocols. First, we examine how to compress the Routing Information Base (RIB), a data structure routers use to store information about all possible paths, using Forgetful Routing. In our work, we explore a space-time trade-off and demonstrate how RIB memory can be reduced by a factor of 3 or more. Second, we reduce the size of the Forwarding Information Base (FIB), a different router data structure used for forwarding packets, with a Memory Management System. We demonstrate how to optimally compress the FIB without changing forwarding behavior, as well as how forwarding behavior can be slightly perturbed to reduce memory usage up to a factor of 3. Finally, we examine the growth trends of new protocols such as IPv6 and multicast which are rapidly emerging and expect to become widespread; IPv6 is being deployed to solve the address shortage problem, and multicast's one-to-many model has become a popular means to distribute content such as IPTV. By measuring these protocols, we better understand where they are headed, and thus better understand future routing requirements.

1 0