Quick links

Talk

Deterministic Global Minimum Cut in Near-Linear Time

Date and Time
Tuesday, October 14, 2014 - 4:30pm to 5:30pm
Location
Computer Science 402
Type
Talk
Host
Robert Tarjan
We present a deterministic Õ(m) time algorithm finding a global minimum cut of an undirected unweigthed graph G with n nodes and m edges.  In particular, this identifies the edge connectivity k of G.

The previous fastest deterministic algorithm by Gabow from STOC'91 took Õ(km) time. At STOC'96 Karger presented randomized near-linear time Monte Carlo algorithm for the problem. As he points out, there is no better way of certifying the minimality of the returned cut than to use Gabow's slower deterministic algorithm.

In our deterministic near-linear time algorithm, we will decompose the problem via low-conductance cuts found using PageRank a la Brin and Page (1998), as analyzed by Andersson, Chung, and Lang at FOCS'06. Normally such algorithms for low-conductance cuts are randomized Monte Carlo algorithms, because they rely on guessing a good start vertex. However, in our case, we have so much structure that no guessing is needed.
 

Is Multipath Routing Beneficial?

Date and Time
Tuesday, October 7, 2014 - 4:30pm to 5:30pm
Location
Computer Science 402
Type
Talk
Host
Jennifer Rexford

It's often believed that multipath routing is always beneficial. Taking a traffic engineering perspective, we consider commonly used goals such as congestion minimization, minimum average delay, and minimum cost routing. Using a well-known result from linear programming, we show that numbers of paths taken by all demands at optimality is limited by the total number of demands and links in a network. When all node pairs (demands) in a network have traffic,  multipath routing essentially becomes single-path routing, especially as the network becomes large. Under certain traffic conditions, single-path routing is found to be optimal. We will also present results on a number of traffic scenarios and load conditions using topologies used by ISPs and in data center networks. These observations are counter-intuitive due to our commonly held belief about multipath routing. 

Deep Medhi is Curators' Professor in the Department of Computer Science and Electrical Engineering at the University of Missouri- Kansas City, USA. He received B.Sc. in Mathematics from Cotton College, Gauhati University, India, M.Sc. in Mathematics from the University of Delhi, India, and his Ph.D. in Computer Sciences from the University of Wisconsin-Madison, USA. Prior to joining UMKC in 1989, he was a member of the technical staff at AT&T Bell Laboratories. He was an invited visiting professor at the Technical University of Denmark, a visiting research fellow at Lund Institute of Technology, Sweden, a research visitor at University of Campinas, Brazil under the Brazilian Science Mobility Program and served as a Fulbright Senior Specialist. He is the Editor-in-Chief of Springer’s Journal of Network and Systems Management, and is on the editorial board of IEEE/ACM Transactions on Networking, IEEE Transactions on Network and Service Management, and IEEE Communications Surveys & Tutorials. He is co-author of the books, Routing, Flow, and Capacity Design in Communication and Computer Networks (2004) and Network Routing: Algorithms, Protocols, and Architectures (2007), both published by Morgan Kauffman/Elsevier.

Recognition of Faces, Activities and Environments

Date and Time
Friday, May 9, 2014 - 2:00pm to 3:00pm
Location
Computer Science 402
Type
Talk

J. K. Aggarwal is on the faculty of The University of Texas at Austin College of Engineering and is currently a Cullen Professor of Electrical and Computer Engineering and Director of the Computer and Vision Research Center. His research interests include computer vision, pattern recognition and image processing focusing on human motion.

A Fellow of IEEE (1976), IAPR (1998) and AAAS (2005), he received the Senior Research Award of the American Society of Engineering Education in 1992, the 1996 Technical Achievement Award of the IEEE Computer Society and the graduate teaching award at The University of Texas at Austin in 1992. More recently, he is the recipient of the 2004 K S FU prize of the International Association for Pattern Recognition, the 2005 Kirchmayer Graduate Teaching Award of the IEEE and the 2007 Okawa Prize of the Okawa Foundation of Japan.. He is a Life Fellow of IEEE and Golden Core member of IEEE Computer Society. He has authored and edited a number of books, chapters, proceedings of conferences, and papers.

Traffic Engineering: From Distributed Static Optimization to Centralized Transient Control

Date and Time
Wednesday, March 19, 2014 - 11:00am to 12:00pm
Location
Computer Science 402
Type
Talk

Traffic Engineering is of fundamental importance for network operation. Traditionally, it assumes static traffic input and then looks for distributed routing solutions to optimize certain objective. Along this line, in the first part of this talk, we will present HALO (Hop-by-hop Adaptive Link-state Optimal) routing. It is the first provable optimal link-state routing solution with hop-by-hop forwarding. Furthermore, our solution does not require traffic matrix as an explicit input and can adapt to changing traffic input. We prove our solution converges and solves the standard MCF (Multi-Commodity Flow) problem.

Recently, there has been tremendous interest in SDN (Software-Defined Networking), which is an emerging network architecture that separates control and data planes. Conceivably, that means network managers can first solve Traffic Engineering optimization in a centralized manner and then translate the solution to configure network switches. Within this context, in the second part of this talk, we consider the problem of avoiding transient congestion while reconfiguring the routing paths. We formulate a flow-based and a switch-based model. For the flow-based model, we demonstrate that an optimal sequence of minimum update steps could always be found when the dependency graph is acyclic. For the switched model, we find a way to translate a feasible flow-based updating sequence to a feasible switch-based sequence subject to a tree topology constraint on the routing paths.

Really Catching Click-Fraud

Date and Time
Wednesday, March 12, 2014 - 12:00pm to 1:30pm
Location
Sherrerd Hall 302
Type
Talk
Host
Michael Freedman

Click-fraud in online advertising siphons several tens of millions of dollars from the online advertising  ecosystem. In this talk, I'll talk about our in-depth investigations into one of the most common ways of committing  online advertising click-fraud. I'll focus primarily on  the techniques and parties involved, their incentives, points of vulnerability, and how these vulnerabilities can be exploited to get them to stop. This talk will not be recorded for reasons that will become apparent during the talk.

Saikat Guha is a researcher at Microsoft Research in India. He is broadly interested in advertising systems and privacy systems. Saikat received his PhD from Cornell University in '09. He authored the RFC that now serves as the best-practice for building TCP support in NATs and firewalls. In 2012, he was named one of MIT Technology Review's TR-35 (35 young innovators under 35). Saikat is always looking to help PhD students who need data to achieve their world-domination goals.

Dropbox Tech Talk

Date and Time
Monday, February 17, 2014 - 5:30pm to 6:30pm
Location
Computer Science Tea Room
Type
Talk
Speaker
Ritu Vincent, from Dropbox

The Dropbox Desktop Client is one of the most popular programs in the world, with hundreds of millions of users. Interested in finding out how it works? Join Dropbox Engineer Ritu Vincent for a deep dive into some of the tech behind the "magic folder", the challenges involved in building a file syncing solution that works seamlessly across multiple platforms and a quick look at where we're going next.

Fathers of the Internet reflecting on the evolution of the Internet

Date and Time
Wednesday, March 12, 2014 - 4:30pm to 5:30pm
Location
Friend Center 101
Type
Talk

Fathers of the Internet reflecting on the evolution of the Internet (and a celebration of the 40th anniversary of the invention of TCP/IP protocol for the Internet by Cerf & Kahn in 1974.)  

Vinton Cerf (Chief Internet Evangelist at Google) and Robert Kahn (CEO of Corporation for National Research Initiatives), whose pioneering work on the Internet has been widely recognized by numerous awards, including the US Presidential Medal of Freedom, the US National Medal of Technology, and the ACM Turing Award, will together give a public duet lecture on “Perspectives on the Internet and its Evolution.” 

This is an open lecture to general public. No fee or ticket required. 

Seating available on first-come-first-served basis, and starts at 4pm. 

http://edgelab-events.princeton.edu

Tierless Programming and Reasoning for Software-Defined Networks

Date and Time
Tuesday, February 4, 2014 - 4:30pm to 5:30pm
Location
Computer Science 302
Type
Talk
Host
David Walker

Modern network software is implemented across two tiers: the data plane, which contains packet-processing rules implemented efficiently on switching hardware, and the control plane, which implements fundamental algorithms, policies, and business rules that determine what the data plane should do. Thus, programming the network is akin to programming a two-tier, massively distributed system, where each node has heterogeneous processing capabilities. In addition, the persistent store on the controller represents a third tier.

We are designing a language, Flowlog, that exploits software-defined networking (SDN) to provide a ``tierless'' Datalog-like programming language that unifies descriptions of control, data, and external state, making it easier to express and verify invariants that cross-cut tiers. Flowlog has intentionally limited expressiveness, to enable the construction of powerful tools such as proactive compilers, change-impact analyzers, and more. Flowlog also provides a formal mechanism of callouts to general-purpose code (akin to database stored procedures), to reconcile the needs of programmers with the limitations of Flowlog's expressive power.

(Joint work with Tim Nelson (Brown), Andrew Ferguson (Brown), Michael Scheer (Brown), Dan Dougherty (WPI), and Arjun Guha (UMass Amherst).

Efficient multi-pattern matching on Compressed HTTP traffic

Date and Time
Wednesday, December 11, 2013 - 10:00am to 11:00am
Location
Computer Science 402
Type
Talk
Host
Jennifer Rexford

Signature-based detection is one of the fundamental technique to detect malicious activities in a network environment. Today, the performance of the security tools is dominated by the speed of the string-matching algorithms that detect these signatures.

A significant part of the traffic over the Internet is compressed HTTP. However, current security tools do not deal with such a traffic and require some kind of decompression phase before performing the multi-patterns matching task. Thus, there is a high performance penalty in pattern matching on compressed data.

In this talk, we present efficient algorithms for on-the-fly multi-pattern matching algorithms for common HTTP compression algorithms, such as GZIP and SDCH (Google's compression algorithm). Our results show that surprisingly it is usually faster to do pattern matching on the compressed data, with the penalty of decompression, than to do pattern matching on regular traffic.

The talk is based on three papers: one with A. Bremler-Barr (INFOCOM 2009, later in Transactions on Networking 2012), one with Y. Afek and A. Bremler-Barr (Networking 2011, later in Computer Communication 2012) and one with S. Tzur-David, D. Hay and A. Bremler-Barr (INFOCOM 2012).

Determinism Is Not Enough: Making Parallel Programs Reliable with Stable Multithreading

Date and Time
Monday, November 25, 2013 - 4:30pm to 5:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
Talk
Speaker
Host
Michael Freedman
Our accelerating computational demand and the rise of multicore hardware have made parallel programs, especially shared-memory multithreaded programs, increasingly pervasive and critical. Yet, these programs remain extremely dificult to write, test, analyze, debug, and verify. Conventional wisdom has attributed these dificulties to nondeterminism (i.e., repeated executions of the same program on the same input may show different behaviors), and researchers have recently dedicated much effort to bringing determinism into multithreading. In this talk, I argue that determinism is not as useful as commonly perceived: it is neither suficient nor necessary for reliability. We present our view on why multithreaded programs are dificult to get right, describe a promising approach we call stable multithreading to dramatically improve reliability, and summarize our last four years' research on building and applying stable multithreading systems.

Junfeng Yang's research (http://www.cs.columbia.edu/~junfeng) centers on making reliable and secure systems. He earned his PhD at Stanford, where he created eXplode, a general, lightweight system for effectively finding storage system errors. This work has led to an OSDI '04 best paper, numerous bug fixes to real systems such as the Linux kernel, and a featured article in Linux Weekly news. He worked at Microsoft Research, Silicon Valley from 2007-2008, extending eXplode to check production distributed systems. MoDist, the resultant system, is being transferred to Microsoft product groups. He's now co-directing the Software Systems Lab (ssl.cs.columbia.edu) at Columbia University, where his recent work on making reliable parallel programs---the Tern/Peregrine/Parrot stable multithreading systems--- was featured in CACM, ACM Tech News, The Register, and many other sites. He won Sloan and AFOSR YIP both in 2012; and NSF CAREER in 2011.

Follow us: Facebook Twitter Linkedin