- talks - lists.cs.princeton.edu

11am Mon Jul 20 talk on measuring Internet quality of experience
by Jennifer Rexford 16 Jul '15

16 Jul '15

[Please contact Jen Rexford at jrex(a)cs.princeton.edu <mailto:jrex@cs.princeton.edu> if you are interested in meeting with the speaker.] Speaker: Renata Teixeira, Inria Paris-Rocquencourt Title: HostView: Measuring Internet quality of experience on end-hosts Date/time: 11:00am-12:00pm Monday July 20 Location: CS 402 Abstract: There is much interest recently in doing automated performance diagnosis on user laptops or desktops. One interesting aspect of performance diagnosis that has received little attention is the user perspective on performance. To conduct research on both end-host performance diagnosis and user perception of network and application performance, we designed an end-host data collection tool, called HostView. HostView not only collects network, application and machine level data, but also gathers feedback directly from users. User feedback is obtained via two mechanisms, a system-triggered questionnaire and a user-triggered feedback form, that for example asks users to rate the performance of their network and applications. This talk will describe our experience with the first deployment of HostView. Using data from 40 users, we articulate the challenges in this line of research, and report on initial findings in correlating user data to system-level data. We then describe our more recent efforts in conducting an in-depth study with twelve users in France to guide our design of the next version of HostView and of methods to infer user context and activities. This is joint work with Diana Joumblatt, Jaideep Chandrashekar, Nina Taft, Anna-Kaisa Pietilainen, George Rosca, Peter Tolmie, Tom Rodden, Tom Lodge, Richard Motier. This work is funded in part by the EU FP7 User-Centric Networking project, Grant No. 611001. Bio: Renata Teixeira received the Ph.D. degree in computer science from the University of California, San Diego, in 2005. During her Ph.D. studies, she worked on Internet routing at the AT&T Research. She was a researcher with the Centre National de la Recherche Scientifique (CNRS) at LIP6, UPMC Sorbonne Universites, Paris, France from 2006 to 2013. She joined Inria Paris-Rocquencourt as senior researcher in October 2013. She was a visiting scholar at UC Berkeley/ICSI in 2011. Her research interests are in measurement, analysis, and management of data networks. She has authored more than 60 papers in this area. Renata is vice-chair of ACM SIGCOMM. She is a member of the steering committee of the ACM Internet Measurement Conference and has been active in the program committees of ACM SIGCOMM, ACM IMC, ACM CoNEXT, PAM, IEEE INFOCOM, among others.

1 0

Jonathan Frankle will present his Masters talk on Friday, July 17, 2015 at 10am in rm 401.
by Nicki Gotsis 16 Jul '15

16 Jul '15

Jonathan Frankle will present his Masters talk on Friday, July 17, 2015 at 10am in rm 401. The members of his committee are David Walker and Aarti Gupta. Everyone is invited to attend his talk. Title and abstract are below. Example-Directed Synthesis: A Type-Theoretic Interpretation Input-output examples have emerged as a practical and user-friendly specification mechanism for program synthesis in many environments. While example-driven tools have demonstrated tangible impact that has inspired adoption in industry, their underlying semantics are less well understood: what are "examples" and how do they relate to other kinds of specifications? I describe examples as "refinement types." Seen in this light, program synthesis is the task of finding an inhabitant of such a type. This insight provides an immediate semantic interpretation for examples. Moreover, in makes it possible to exploit decades of research in type theory as well as its correspondence with intuitionistic logic rather than designing ad hoc synthesis systems from scratch.

1 0

Tianqiang Liu will present his FPO Thursday, 7/23/2015 at 2pm, 401 Computer Science Building. "Analyzing, Optimizing and Synthesizing Scenes by Reasoning About Relationships Between Objects"
by Nicki Gotsis 16 Jul '15

16 Jul '15

Tianqiang Liu will present his FPO, "Analyzing, Optimizing and Synthesizing Scenes by Reasoning About Relationships Between Objects", Thursday, 7/23/2015 at 2:00pm, 401 Computer Science Building. The members of his committee are Thomas Funkhouser (adviser); Readers: Szymon Rusinkiewicz, Wilmot Li (Adobe Research); Non-readers: David Dobkin, Adam Finkelstein A copy of his thesis, is available in Room 310. Everyone is invited to attend his talk.

1 0

Nanxi Kang will present her Pre-FPO on Monday, June 29 at 12pm in CS 401.
by Nicki Gotsis 22 Jun '15

22 Jun '15

Nanxi Kang will present her Pre-FPO on Monday, June 29 at 12pm in CS 401. The members of her committee are: Jennifer Rexford (adviser), David Walker, Sanjay Rao (Purdue), Nick Feamster, Mike Freedman. Everyone is invited to attend her talk. The the abstract follow below: Managing large enterprise networks is challenging. Operators need diverse policies such as routing, access control, QoS and load balancing, for performance, security and reliability. The best practice to enforce these policies today is to configure rules on network switches individually. This forces operators to reason about many low-level details, all at the same time, including the choice of path, the rule-table space limits on each switch, and the hop-by-hop interaction of rules for forwarding, dropping, modifying, and monitoring packets. The rule-table space, in particular, is a scarce commodity on switches. While the rule-tables (e.g., TCAM) are optimized for high-speed arbitrary packet-header matching and widely used for ACL, QoS and forwarding, they have small capacities on the order of a few thousand entries. In this talk, we propose a series of abstractions that enable operators to specify high-level goals without worry about the configurations of underlying switches, and algorithms that realize these abstractions within the constrained rule-table sizes. We first present the "One-Big-Switch" abstraction, which virtualizes the network topology as a single switch and allows operators to specify network policies as if configuring a single switch. The rule placement algorithm is responsible for distributing the rules for this single switch to the underlying physical switches. With this abstraction, we also develop a traffic monitoring system, PacketSeer, which acts as "Wireshark" running on top of the "One-Big-Switch" to aid measurement and troubleshooting. The second abstraction is "One-Big-Server", which consists of a set of equivalent servers offering the same services (e.g., websites). Given the desired distribution of server loads, Niagara algorithms compute forwarding rules on a switch to split incoming traffic accurately. Finally, we propose "Attribute-Carrying IPs". ACIP allows operators to define policies for groups of hosts with the same attributes (e.g., owner role or department). Our ACIP allocation algorithms effectively compact these policies defined on host attributes (e.g., faculty or students, CS or EE) into a small number of switch rules. Together, these abstractions -- coupled with efficient algorithms for realizing the abstractions -- enables flexible enterprise network management on commodity switches.

1 0

11am Tue Jun 9 talk by George Varghese on "Treating Networks like Chips and Programs" in CS 105
by Jennifer Rexford 08 Jun '15

08 Jun '15

Speaker: George Varghese, Microsoft Research Title: From EDA to NDA: Treating Networks like Chips and Programs Date/time: 11:00am Tuesday June 9 Location: CS 105 (small auditorium) Abstract: Surveys reveal that network outages are prevalent, and that many outages take hours to resolve, resulting in significant lost revenue. Many bugs are caused by errors in configuration files which are programmed using arcane, low-level languages, akin to machine code. Further, mistakes are often hunted down using rudimentary tools such as Ping and Traceroute. Taking our cue from other fields such as hardware design, we suggest fresh approaches. Our first attempt was a geometric model of network forwarding called Header Space together with parsers that convert router configurations to header space representations. Header Space ideas were used to build a static checker (Hassel) that can identify reachability bugs and a dynamic checker (ATPG) that can identify performance faults. Unlike classical model checkers, Hassel does not have a notion of a specification language or a modeling language, which makes it difficult to write higher level specifications or deal with changing router behaviors. Our attempt to remedy this was to teach an old dog (Datalog) new tricks to create what we call Network Optimized Datalog (NoD) followed by extensions to quantitative and automatic verification. These results suggest that concepts from Electronic Design Automation (EDA) and program verification can be leveraged to create what might be termed Network Design Automation (NDA). What might the equivalent of Layout Versus Schematic tools or Specification Mining be? What are the differences in the domain that can be exploited? The second part of this talk will explore this vision, touching upon modular network semantics, language design, performance invariants, and interactive network debuggers. This is joint work with collaborators at Berkeley, MSR, and Stanford. Bio: George Varghese received his Ph.D. in 1992 from MIT. From 1993-1999, he was a professor at Washington University, and at UCSD from 1999 to 2013. He was the Distinguished Visitor in the computer science department at Stanford University from 2010-2011. He joined Microsoft Research in 2012. His book "Network Algorithmics" was published in December 2004 by Morgan-Kaufman. In May 2004, he co-founded NetSift, which was acquired by Cisco Systems in 2005. With colleagues, he has won best paper awards at SIGCOMM (2014), ANCS (2013), OSDI (2008), PODC (1996), and the IETF Applied Networking Prize (2013). He won the Kobayashi Award and the SIGCOMM Lifetime Award, both in 2014, and the IIT Bombay Distinguished Alumni Award in 2015.

1 1

Nicholas Johnson will present his FPO on Thursday, 5/28/2015 at 1:00pm, CS 401 Computer Science Building, "Static Dependence Analysis in an Infrastructure for Automatic Parallelization"
by Nicki Gotsis 20 May '15

20 May '15

Nicholas Johnson will present his FPO on Thursday, 5/28/2015 at 1:00pm, 401 Computer Science Building, "Static Dependence Analysis in an Infrastructure for Automatic Parallelization" The members of his committee are as follows: Readers: David Wentzlaff and Jae W. Lee (Sungkyunkwan University); Examiners: Andrew Appel, David August, and David Walker. A copy of his thesis is available in Room 310. Everyone is invited to attend his talk.

1 1

Colloquium Speaker Dana Moshkovitz Tuesday May 19, 12:30pm
by Nicole E. Wagenblast 19 May '15

19 May '15

Colloquium Speaker Dana Moshkovitz , Massachusetts Institute of Technology Tuesday, May 19, 12:30pm Computer Science 105 Many of the optimization problems of interest to humanity are NP-hard, and most computer scientists believe that they have no efficient algorithms. Focusing on approximation rather than exact optimization might extend the reach of algorithmic technique into the intractable. However, for many NP-hard problems approximating them better than a problem-dependent threshold turns out to be NP-hard as well. Proving so rigorously is a difficult task, which -- by a leap of thought -- leads to fundamental questions about the nature of proofs and their verification. In this talk I'll discuss the phenomenon of sharp thresholds in approximability, namely how many approximation problems transform instantly from efficiently solvable to exponentially hard as one focuses on a better approximation (joint work with Ran Raz). I'll discuss two prover games and a new, incredibly simple, method ("fortification") for analyzing their parallel repetition. Finally, I'll discuss a recent candidate hard instance for unique games, which might lead to progress on the Unique Games Conjecture - one of the biggest open problems in approximability (joint work with Subhash Khot).

1 1

Fwd: EE Seminar - May 27, 2015, 1:30 pm, E-Quad B205 - Dr. Yuval Yarom
by Jennifer Rexford 18 May '15

18 May '15

> > Speaker: Dr. Yuval Yarom > University of Adelaide > Title: A Side-channel Attack on the OpenSSL Implementation of the Bitcoin Elliptic Curve Digital Signature > Date: Wednesday, May 27, 2015 > Time: 1:30 p.m. > Room: E-Quad, Room B205 > Host: Prof. Ruby Lee > > Abstract: Side-channel attacks aim to break cryptosystems by exploiting information leaked through the interaction of the cryptosystem's Implementation with its environment. This talk presents some recent advances in side-channel analysis. It demonstrates how to combine a new side channel, a recently discovered property of many standard elliptic curves and an improved lattice technique in order to break the OpenSSL implementation of the Elliptic Curves Digital Signature Algorithm (ECDSA). When used against the secp256k1 curve, employed in the Bitcoin protocol, an attacker can break the cryptosystem by observing as little as 25 signatures. > > The talk is based on a joint work with Naomi Benger, Joop van de Pol and Nigel Smart. > > Biography: Yuval Yarom is a Research Associate in the School of Computer Science at the University of Adelaide. His main research interests are computer security and cryptography, with a current focus on side-channel attacks and defences. He obtained his BSc and MSc from the Hebrew University, Jerusalem and a PhD in Computer Science from the University of Adelaide. Prior to resuming his academic interests he has spent several years in the industry, doing computer security research at Memco Software and co-founding Girafa.com. > >

1 0

10-11am Monday May 18 talk in 402 on network verification
by Jennifer Rexford 17 May '15

17 May '15

Speaker: Toshio Tonouchi, NEC Title: A fast method of verifying network routing with back-trace header space analysis Date/time: 10-11am Monday May 18 Location: CS 402 Abstract: It is a tough job for operators to make perfectly accurate configuration of many network elements in large networks. Erroneous configurations may cause critical incidents in network, on which many ICT systems are running. It may also result in a security hole as well as system incidents. There has been much work on preventing erroneous configurations, but this has taken a lot of time to verify routing with large networks. We propose a new method of verifying network routing. It only focuses on verifying isolation and reachability, but it can verify these properties with O(R^2), where R is the number of flow entries, while the performance of an existing method of verification is O(R^3). We also provide a proof of the correctness of our method.

1 0

1:30pm talk today by John Doyle (Caltech) on "Universal laws and architectures" in CS 105
by Jennifer Rexford 15 May '15

15 May '15

Speaker: John Doyle, Caltech Title: Universal laws and architectures: Theory and lessons from brains, nets, hearts, bugs, grids, flows, and zombies Date/time: 1:30-2:30pm Friday May 15 Location: CS 105 (small auditorium) Abstract: This talk aims to accessibly introduce a new theory of network architecture relevant to biology, medicine and technology (particularly SDN/NFV and cyberphysical systems), initially minimizing math details. Key ideas are motivated by familiar examples from neuroscience, including live demos using audience brains, and further illustrated with examples from technology and biology. The status of the necessary math will be sketched in as much detail as time permits. Background material is in online videos (accessible from website above) and a recent blog post: rigorandrelevance.wordpress.com/author/doyleatcaltech. My research is aimed at developing a more “unified” theory for complex networks motivated by and drawing lessons from neuroscience[4], cell biology[3], medical physiology[9], technology (internet, smartgrid, sustainable infrastructure)[1][8], and multiscale physics [2],[5],[6]. This theory involves several elements: hard limits, tradeoffs, and constraints on achievable robust, efficient performance ( “laws”), the organizing principles that succeed or fail in achieving them (“architectures” and protocols), the resulting high variability data and “robust yet fragile” behavior observed in real systems and case studies (behavior, data, statistics), the processes by which systems adapt and evolve (variation, selection, design), and their unavoidable fragilities (hijacking, parasites, predation, zombies). We will leverage a series of case studies with live demos from neuroscience, particularly vision and sensorimotor control, plus some hopefully familiar and simple insights from medicine, cell biology and modern computer and networking technology. Zombies emerge throughout as a ubiquitous, strangely popular, and annoying system fragility, particularly in the form of zombie science. In addition to the above mentioned blog and videos, papers [1] and [4] (and references therein) are the most accessible and broad introduction while the other papers give more domain specific details. For math details the best place to start is Nikolai Matni’s website (cds.caltech.edu/~nmatni/). Selected recent references: [1] Alderson DL, Doyle JC (2010) Contrasting views of complexity and their implications for network-centric infrastructures. IEEE Trans Systems Man Cybernetics—Part A: Syst Humans 40:839-852. [2] Sandberg H, Delvenne JC, Doyle JC. On Lossless Approximations, the Fluctuation-Dissipation Theorem, and Limitations of Measurements, IEEE Trans Auto Control, Feb 2011 [3] Chandra F, Buzi G, Doyle JC (2011) Glycolytic oscillations and limits on robust efficiency. Science, Vol 333, pp 187-192. [4] Doyle JC, Csete ME(2011) Architecture, Constraints, and Behavior, P Natl Acad Sci USA, vol. 108, Sup 3 15624-15630 [5] Gayme DF, McKeon BJ, Bamieh B, Papachristodoulou P, Doyle JC (2011) Amplification and Nonlinear Mechanisms in Plane Couette Flow, Physics of Fluids, V23, Issue 6, 065108 [6] Page, M. T., D. Alderson, and J. Doyle (2011), The magnitude distribution of earthquakes near Southern California faults, J. Geophys. Res., 116, B12309, doi:10.1029/2010JB007933. [7] Namas R, Zamora R, An, G, Doyle, J et al, (2012) Sepsis: Something old, something new, and a systems view, Journal Of Critical Care Volume: 27 Issue: 3 [8] Chen, L; Ho, T; Chiang, M, Low S; Doyle J,(2012) Congestion Control for Multicast Flows With Network Coding, IEEE Trans On Information Theory Volume: 58 Issue: 9 Pages: 5908-5921 [9] Li, Cruz, Chien, Sojoudi, Recht, Stone, Csete, Bahmiller, Doyle (2014) Robust efficiency John Doyle is the Jean-Lou Chameau Professor of Control and Dynamical Systems, Electrical Engineer, and BioEngineering at Caltech (BS&MS EE, MIT (1977), PhD, Math, UC Berkeley (1984)). Research is on mathematical foundations for complex networks with applications in biology, technology, medicine, ecology, and neuroscience. Paper prizes include IEEE Baker and Automatic Control Transactions (twice), ACM Sigcomm, AACC American Control Conference. Individual awards include IEEE Power Hickernell, AACC Eckman, UCB Friedman, IEEE Centennial Outstanding Young Engineer, and IEEE Control Systems Field Award. Best known for fabulous friends, colleagues, and students, plus national and world records and championships in various sports. Extremely fragile.

1 0