Talk

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.

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.

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.

Communication technology has advanced significantly over the last decade enabling people to communicate anytime from anywhere using a multiplicity of devices. However, the power of this advancement in communication technology has hardly been leveraged in traditional services industry. Specifically, the vertical service providers, such as the Health Care industry, the Banking industry, the Education industry, and others who require network-based services to efficiently conduct their business reducing their operational expenses, and to provide novel value-added services to their customers generating additional revenue, have hardly been able to leverage the power of the network to their advantage. In the talk, I will describe several applications from the services industry that can be built on a platform (referred to as Network as a Service or NaaS platform) based on the concept of network virtualization and shows how various parties involved in providing the services are economically incentivized to make them feasible in real life.

The NaaS platform enables Communication Service Providers (CSPs) to work collaboratively with Vertical Service Providers (VSPs) to offer novel services leveraging their existing network infrastructure through the techniques of network virtualization. This solution enables CSPs to generate new revenue without additional capital expenditure, and in addition, also enables VSPs to generate additional revenue via novel value-added service offerings to their customers without incurring any capital expenditure either. Thus, this model of offering services provides a win-win value proposition to both CSPs as well as to VSPs.

NaaS Platform is being built at Infosys Technologies Limited. In course of my presentation, I'll describe a high-level architecture of the platform and discuss how various functional blocks in the architecture are used synergistically to deliver a novel service called On Demand Health Care (ODHC).

Sanjoy Paul (sanjoy_paul@infosys.com) is Associate Vice President, General Manager-Research and Head of Convergence Lab at Infosys Technologies Limited where he heads research and innovation in the field of Communications, Media and Entertainment. Prior to that, he was a Research Professor at WINLAB, Rutgers University, and Founder of RelevantAd Technologies Inc. Before that Sanjoy spent five years as the Director of Wireless Networking Research at Bell Labs, Lucent Technologies, and as the CTO of two start-up companies (Edgix and WhenU) based in New York. In a previous tenure at Bell Labs as a Distinguished Member of Technical Staff, Sanjoy was the chief architect of Lucent's IPWorX Caching and Content Distribution product line. Sanjoy has authored a book on Multicasting, published over 100 papers in International Journals and refereed Conference Proceedings, authored over 80 US patents (28 granted, 50+ pending), and is the co-recipient of 1997 William R. Bennett award from IEEE Communications Society for the best original paper in IEEE/ACM Transactions on Networking. He holds a Bachelor of Technology degree from IIT Kharagpur, India, an M.S and a Ph.D. degree from the University of Maryland, College Park, and an MBA from the Wharton Business School, University of Pennsylvania. Sanjoy is a Fellow of IEEE and a Member of the ACM.

Operators of data centers want a scalable network fabric that supports high bisection bandwidth and host mobility, but which costs very little to purchase and administer. Ethernet almost solves the problem -- it is cheap and supports high link bandwidths -- but traditional Ethernet does not scale, because its spanning-tree topology forces traffic onto a single tree. Many researchers have described "scalable Ethernet" designs to solve the scaling problem, by enabling the use of multiple paths through the network. However, most such designs require specific wiring topologies, which can create deployment problems, or changes to the network switches, which could obviate the commodity pricing of these parts.

In this talk, I will describe SPAIN ("Smart Path Assignment In Networks"). SPAIN provides multipath forwarding using inexpensive, commodity off-the-shelf COTS) Ethernet switches, over arbitrary topologies. SPAIN pre-computes a set of paths that exploit the redundancy in a given network topology, then merges these paths into a set of trees; each tree is mapped as a separate VLAN onto the physical Ethernet. SPAIN requires only minor end-host software modifications, including a simple algorithm that chooses between pre-installed paths to efficiently spread load over the network. We demonstrate SPAIN's ability to improve bisection bandwidth over both simulated and experimental data-center networks.

Joint work with Jayaram Mudigonda and Praveen Yalagandula, and with Mohammad Al-Fares (UCSD)

Today, mobile phones are increasingly used for content-centric communication, whereby users access and share content with each other (e.g., pictures on Facebook). However, content sharing is limited to infrastructure networks and legacy Internet technologies are ill suited for content-centric communication. Moreover, the Internet protocols and APIs do not work well in highly mobile and disruptive environments, where intermittent connectivity is the norm rather than the exception. These deficiencies make it is cumbersome, or even impossible, to share content directly between mobile phones, leading to high stress on existing infrastructure and high costs for the consumer, while putting limitations on the possibilities for developing new and innovative applications.

In this talk, I will present Haggle, a novel network architecture built from the ground up to support opportunistic content-centric communication directly between mobile phones. Haggle addresses content rather than hosts, which makes it irrelevant from where a user receives a content item. The content-centric communication is driven by a novel distributed search-based resolution scheme, which draws inspiration from online search engines. The search scheme resolves the mappings between the content and its interest group, i.e., the nodes that have an interest in the content. Search has the benefit of ranking, and therefore provides a natural limitation and ordering mechanism for content dissemination. This means that content, in general, has a higher likelihood of being disseminated if there is a high interest in it in the network.

After the talk, I will demonstrate Haggle using a visualization tool that shows how photos taken with a phone's camera are shared with other mobile phones or devices.

Reception immediately following 3rd Floor Atrium

The MIT Center for Future Civic Media is a multidisciplinary research group that develops sociotechnical systems to strengthen geographic communities. Working in urban and rural communities, from the US to Peru, our civic projects focus on a community's ownership of its own information and the ability to turn that information into constructive social change. This lecture will give an overview of recent activity at the Center, and cover lessons learned in the process of fieldwork and deployment.

Chris Csikszentmihalyi directs the MIT Center for Future Civic Media, dedicated to developing technologies that strengthen communities. He also founded and directs the Media Lab's Computing Culture group, which works to create unique media technologies for cultural applications. He has worked in the intersection of new technologies, media, politics, and the arts for 16 years, lecturing, showing new media work, and presenting installations on five continents and one subcontinent.

Hellenic Studies has invited Professor Christos Papademetriou, Computer Science Division, University of California, Berkeley, to give a lecture entitled "Logicomix" with a reception to follow in the gallery. Hosts: Dimitri Gondicas and Ken Steiglitz

The European Union's recent legislation on data retention is highly controversial and perceived as threat to an array of individual freedoms. Its technical provisions cover all kinds of communications providers, including proxy servers. This justifies a closer look at how data retention affects the ability to deploy mix-based anonymity services and what level of security can still be provided legally. Rainer will talk in particular about the situation in Germany and the experience gained from the popular cascade-based web anonymizer AN.ON, which is operated at his former university TU Dresden. Citing empirical data collected from AN.ON, new "legal adversary models" are introduced, calibrated, and assessed. While the overall situation for online anonymity is not too bad under current law, an outlook on possible future developments and adequate technological responses is given.

Rainer is a postdoctoral fellow in the Networking Group of the International Computer Science Institute in Berkeley, supported by the German Academic Exchange Service (DAAD). His research interests include privacy-enhancing technologies, economics of privacy and information security, and multimedia forensics. He holds an M.A. degree in Communication Science and Economics, and a PhD in Computer Science, both from Technische Universitaet Dresden in Germany. Before he obtained his PhD, he worked in the European Central Bank, where he served in the directorates for economics and financial stability and supervision.

Common wisdom is that the way to scale networks to large size is hierarchy: routing is performed on higher level aggregates across domains, separately from routing within domains. We live with the consequences: inflated path lengths, and the use of location-dependent addresses (IP addresses in the Internet) which complicate management, mobility, and multihoming.

I will present Distributed Compact Routing, a protocol which (1) guarantees scalability, in the form of roughly \\\\sqrt{n} state for a network of n nodes; (2) guarantees approximately-shortest paths, in the form of constant stretch; and (3) routes directly on flat, location-independent identifiers. Our work builds on recent theoretical advances in the area of compact routing. Past attempts to translate these centralized algorithms to practical distributed protocols have had limited success, compromising state or stretch guarantees or assuming special topologies. Our results thus represent a significant step forward in routing technology, which we believe has direct applicability to many kinds of networks including peer-to-peer networks, Internet routing, and content-centric networks.

Joint work with Ankit Singla, Kevin Fall, Gianluca Iannaccone, and Sylvia Ratnasamy.