Quick links

Talk

Learning and Mining in Complex Networks, with Applications to Cyber Situational Awareness

Date and Time
Tuesday, March 8, 2011 - 12:00pm to 1:00pm
Location
Computer Science 302
Type
Talk
Speaker
Tina Eliassi-Rad, from Rutgers University
Complex networks are ubiquitous in many domains. Examples include spatial, technological, informational, social, and biological networks. In this talk, I will present algorithms for both network classification and clustering, paying specific attention to evaluation in such non-IID settings, scalability, transfer learning, and applications to cyber situational awareness.

Tina Eliassi-Rad is an Assistant Professor at the Department of Computer Science at Rutgers University. She is also a member of the Rutgers Center for Computational Biomedicine, Imaging, and Modeling (CBIM) and Rutgers Center for Cognitive Science (RuCCS). Until September 2010, Tina was a Member of Technical Staff at Lawrence Livermore National Laboratory. Tina earned her Ph.D. in Computer Sciences (with a minor in Mathematical Statistics) at the University of Wisconsin-Madison in 2001. Broadly speaking, Tina's research interests include machine learning, data mining, and artificial intelligence. Her work has been applied to the World-Wide Web, text corpora, large-scale scientific simulation data, and complex networks. Tina is an action editor for the Data Mining and Knowledge Discovery Journal. She received a US DOE Office of Science Outstanding Mentor Award in 2010.

Let the Market Drive Deployment: A Strategy for Transitioning to BGP Security

Date and Time
Tuesday, March 29, 2011 - 12:30pm to 1:30pm
Location
Computer Science 402
Type
Talk
With a cryptographic root-of-trust for Internet routing (RPKI) on the horizon, we can finally start planning the deployment of one of the secure interdomain routing protocols proposed over a decade ago (Secure BGP, secure origin BGP). However, if experience with IPv6 is any indicator, this will be no easy task. Security concerns alone seem unlikely to provide sufficient local incentive to drive the deployment process forward. Worse yet, the security benefits provided by the S*BGP protocols do not even kick in until a large number of ASes have deployed them.

Instead, we appeal to ISPs' interest in increasing revenue-generating traffic. We propose a strategy that governments and industry groups can use to harness ISPs' local business objectives and drive global S*BGP deployment. We evaluate our deployment strategy using theoretical analysis and large-scale simulations on empirical data. Our results give evidence that the market dynamics created by our proposal can transition the majority of the Internet to S*BGP.

Joint work with Sharon Goldberg and Michael Schapira

Predicting Faults in Heterogeneous, Federated Distributed Systems

Date and Time
Friday, October 1, 2010 - 2:00pm to 3:00pm
Location
Computer Science 402
Type
Talk
Host
Jennifer Rexford
It is notoriously difficult to make distributed systems reliable. This becomes even harder in the case of the widely-deployed systems that become heterogeneous and federated. The set of routers in charge of the inter-domain routing in the Internet is a prime example of such a system. The unanticipated interaction of nodes under seemingly valid configuration changes and local fault-handling can have a profound effect. For example, the Internet has suffered from multiple IP prefix hijackings, as well as performance and reliability problems due to emergent behavior resulting from a local session reset.

We argue that the key step in making these systems reliable is the need to automatically predict faults. In this talk, I will describe the design and implementation of DiCE, a system that uses temporal and spatial awareness to predict faults in heterogeneous, federated systems. Our live evaluation in the testbed shows that DiCE quickly and successfully predicts two important classes of faults, operator mistakes and programming errors, that have plagued BGP routing in the Internet.

Joint work with Marco Canini, Vojin Jovanovic, and Gautam Kumar

Bio: Dejan Kostić obtained his Ph.D. in Computer Science at the Duke University, under Amin Vahdat. He spent the last two years of his studies and a brief stay as a postdoctoral scholar at the University of California, San Diego. He received his Master of Science degree in Computer Science from the University of Texas at Dallas, and his Bachelor of Science degree in Computer Engineering and Information Technology from the University of Belgrade (ETF), Serbia. In January 2006, he started as a tenure-track assistant professor at the School of Computer and Communications Sciences at EPFL (Ecole Polytechnique Fédérale de Lausanne), Switzerland. In 2010, he received a European Research Council (ERC) Starting Investigator Award. His interests include Distributed Systems, Computer Networks, Operating Systems, and Mobile Computing.

Wide-Area Route Control for Distributed Services

Date and Time
Tuesday, June 15, 2010 - 11:00am to 11:45am
Location
Computer Science 402
Type
Talk
Speaker
Vytautas Valancius, from Georgia Tech
Host
Jennifer Rexford
Many distributed services would benefit from control over the flow of traffic to and from their users, to offer better performance and higher reliability at a reasonable cost. Unfortunately, although today's cloud-computing platforms offer elastic computing and bandwidth resources, they do not give services control over wide-area routing. We propose replacing the data center's border router with a Transit Portal (TP) that gives each service the illusion of direct connectivity to upstream ISPs, without requiring each service to deploy hardware, acquire IP address space, or negotiate contracts with ISPs. Our TP prototype supports many layer-two connectivity mechanisms, amortizes memory and message overhead over multiple services, and protects the rest of the Internet from misconfigured and malicious applications. Our implementation extends and synthesizes open-source software components such as the Linux kernel and the Quagga routing daemon. We also implement a management plane based on the GENI control framework and couple this with our four-site TP deployment and Amazon EC2 facilities.

Vytautas Valancius is a Ph.D candidate at Georgia Institute of Technology, advised by professor Nick Feamster. His research interests include interdomain routing, Internet economics, and network virtualization. Prior to his Ph.D studies, Vytautas obtained M.S. in KTH, Sweden and worked in the networking industry as a consultant for 5 years, earning CCIE#14359 certification.

Alumni- Faculty Forum: New Directions in Socail Media

Date and Time
Friday, May 28, 2010 - 2:30pm to 3:30pm
Location
McCosh Hall 50
Type
Talk
Moderator: Ed Felten, Director, Center for Information Technology and Professor, Computer Science and Public Affairs Panelists: Bruce Campbell '90, President, Corporate Development and Digital Media, Discovery Communications Abe Crystal '00, Co-Founder, MoreBetter Labs Bradford Lyman '05, Manager, Client Services, Medallia LLC Alexander Macgillivray '95, General Council, Twitter Inc.

Programming Parallel Accelerators at the \

Date and Time
Thursday, May 20, 2010 - 3:30pm to 4:30pm
Location
Computer Science 302
Type
Talk
Speaker
Ben Ylvisaker, from University of Washington
Parallel accelerators like FPGAs and GPUs have been shown to provide huge performance and energy efficiency advantages on a wide range of applications, from video coding to scientific simulation to wireless communication. However, accelerators are still harder to program than conventional processors, which is almost certainly limiting their use. I advocate for "C level" programming of accelerators, and in this talk I will describe several projects I have worked on to enable that. Specifically, I will discuss a new approach to pipelining complex loops, probabilistic auto-tuning, and relaxed I/O ordering operational semantics.

Ben Ylvisaker is almost finished being a graduate student at the University of Washington. There he is advised by Carl Ebeling and Scott Hauck, and works in the Mosaic group, which does research on architectures, tools and applications for parallel accelerators. Before coming to UW, he earned a master's degree at Carnegie Mellon, where he also got an undergrad degree a few years earlier. Interspersed between the academic adventures, Ben has worked at a number of startup companies, none of which exist anymore.

Data Aware Scheduling for Multi-threaded Applications on SMP Machines

Date and Time
Tuesday, February 16, 2010 - 12:30pm to 1:30pm
Location
Computer Science 402
Type
Talk
Host
Andrea LaPaugh
Extensive use of multi-threaded applications that run on SMP machines justifies modifications in thread scheduling algorithms to consider threads' characteristics in order to improve performance. Current schedulers (e.g. in Linux, AIX) avoid migrating tasks between CPUs unless absolutely necessary. Unwarranted data cache misses occur when tasks that share data run on different CPUs, or are far apart time-wise on the same CPU. This work presents an extension to the Linux scheduler that exploits inter-task data relations to reduce data cache misses in multi-threaded applications running on SMP platforms, thus improving runtime, memory throughput, and energy consumption. Our approach schedules the tasks to the CPU that holds the relevant data rather than to the one with highest affinity. We observed improvements in CPU time and throughput on several benchmarks. For the Chat benchmark the improvement in CPU time and cache misses is over 30% on average.

Dr. Pinter was a research specialist at MIT before receiving her Ph.D. in computer science from Boston University. Following her Ph. D., she joined the faculty of the Electrical Engineering Department of Technion (Israel), remaining for twelve years before joining the IBM research lab in Haifa as member of research staff. She recently left IBM to become CTO of Rascal Software Security. She is also an adjunct faculty member of the Department of Computer Science, Haifa University, supervising graduate student research.

A Universal Calculus for Stream Processing Languages

Date and Time
Tuesday, May 18, 2010 - 11:00am to 12:00pm
Location
Computer Science 302
Type
Talk
Speaker
Robert Soule, from New York University
Stream processing applications such as algorithmic trading, MPEG processing, and web content analysis are ubiquitous and essential to business and entertainment. Language designers have developed numerous domain-specific languages that are both tailored to the needs of their applications, and optimized for performance on their particular target platforms. Unfortunately, the goals of generality and performance are frequently at odds, and prior work on the formal semantics of stream processing languages does not capture the details necessary for reasoning about implementations. This talk presents Brooklet, a core calculus for stream processing that allows us to reason about how to map languages to platforms and how to optimize stream programs. We translate from three representative languages, CQL, StreamIt, and Sawzall, to Brooklet, and show that the translations are correct. We formalize three popular and vital optimizations, data-parallel computation, operator fusion, and operator re-ordering, and show under which conditions they are correct. Language designers can use Brooklet to specify exactly how new features or languages behave. Language implementors can use Brooklet to show exactly under which circumstances new optimizations are correct. In on-going work, we are developing an intermediate language for streaming that is based on Brooklet. We are implementing our intermediate language on System S, IBM's high-performance streaming middleware.

This work is based upon the paper "A Universal Calculus for Stream Processing Languages" by Robert Soule, Martin Hirzel, Robert Grimm, Buğra Gedik, Henrique Andrade, Vibhore Kumar, and Kun-Lung Wu, in the Proceedings of ESOP 2010.

Robert Soule is a Ph.D. candidate at New York University, working with Professor Robert Grimm, and a research co-op in the Data Intensive Systems and Analytics Group at IBM T. J. Watson Research Center, under the guidance of Martin Hirzel. His research interests are in distributed systems, and language support for building systems.

Robust and Efficient TCAM-Based Packet Classification

Date and Time
Wednesday, May 19, 2010 - 12:30pm to 1:30pm
Location
Computer Science 402
Type
Talk
Speaker
Dr. David Hay, from Columbia
Host
Jennifer Rexford
Ternary content-addressable memory (TCAM) devices are increasingly used for performing high-speed packet classification, one of the most challenging tasks in router design today. TCAM enables parallel matching of a key against all TCAM entries, which consist of ``0'',``1'' and ``*'' (don't care) bits, in O(1) time. In this talk we tackle two challenges related to these devices. First, we present PEDS, a novel parallel error detection scheme that locates the erroneous entries in a TCAM device. Time permitting, we will also discuss how one can use TCAM to boost memory-efficiency of Aho-Corasick-like Deep Packet Inspection (DPI) algorithms; this is done by efficiently encoding transitions into prefixes and applying Longest Prefix Matching rule.

These works appear in INFOCOM 2010 and INFOCOM 2009 (runner-up to best paper) and in ACM/IEEE Transactions on Networking. Joint work with Anat Bremler-Barr (IDC), Yaron Koral (IDC), Danny Hendler (BGU) and Ron M. Roth (Technion).

David Hay received his BA (summa cum laude) and PhD degree in computer science from the Technion - Israel Institute of Technology in 2001 and 2007, respectively. He is currently a post-doctoral research scientist at the department of electrical engineering, Columbia University, NY, USA. His main research interests are algorithmic aspects of high-performance switches and routers; in particular: Packet classification, QoS provisioning and competitive analysis. Between 1999-2002, David Hay was with IBM Haifa Research Labs. During summer 2006, he was interning at the Data Center Business Unit of Cisco Systems, San Jose. He was also a post-doc fellow at the department of computer science, Ben Gurion University of the Negev, Israel (2007-2008), and at the departmenty of electrical engineering, Politecnico di Torino, Italy (2008-2009). In October 2009, he is expected to join the school of Computer Science of the Hebrew University of Jerusalem, Israel.

Exploring the Stratified Shortest Paths Problem

Date and Time
Tuesday, May 4, 2010 - 3:00pm to 4:00pm
Location
Computer Science 302
Type
Talk
Speaker
Tim Griffin, from University of Cambridge
Host
Jennifer Rexford
The Border Gateway Protocol (BGP) is the keystone among Internet routing protocols as it maintains connectivity in the entire global Internet. BGP has evolved into a rather mysterious beast. Theoretical work over the last ten years has made it clear that BGP represents something novel in the context of routing protocols: BGP does not compute globally optimal paths, but only locally optimal paths. The talk will explain how this exotic type of routing can be understood in an algebraic setting. The Stratified Shortest-Paths Problem (SSPP) is presented as a very simple example of this type of algebra. The SSPP is meant to capture the essence of a BGP-like path problem without BGP's many operational complexities.

Tim Griffin is a Senior Lecturer and Fellow at King's College, University of Cambridge. His research interests include network protocol design and analysis, with a focus on Internet routing protocols.

Follow us: Facebook Twitter Linkedin