26/11/2014EE, Meyer 1007


On the Scalability of Hop-by-hop Packet Routing

Gabor Retvari

Budapest University

Many of our computer networks, not the least of which the Internet, are built upon hop-by-hop destination-based routing. Here, network devices are equipped with a unique address and routers use giant lookup tables to forward packets towards the intended destination based on the address encoded in the header. At the moment, it is not clear whether we will be able to scale the hop-by-hop routing paradigm into the future economically, as the memory requirement for storing these giant lookup tables keeps on increasing at a fast pace. The main goal of this talk is to highlight some recent results in the related research field on routing scalability.

First, we present the fundamental impossibility result of the field, asserting that no routing scheme can achieve better than linearly increasing routing tables in general. We extend this result from shortest-path routing to general routing policies using an algebraic approach and, for the special case of BGP, we state a Separation Theorem that divides scalable BGP routing policies from unscalable ones. We then do a reality check: we show that IP forwarding tables used in Internet routers can be compressed way beyond what the worst-case analysis would suggest. To do so, we systematically squeeze out every single bit of redundancy from the most common forwarding table data structure, the prefix tree. We find that compression in this case not only does not ruin lookup performance but it even improves it, so this one turns out to be one of those rare cases in computer science when there is no space-time trade-off. Finally, we speculate about the reasons behind this seemingly magical compressibility of IP forwarding tables. We present preliminary analysis suggesting that some form of "heterogeneity" might be a main factor behind compressibility, we attempt to characterize this notion using the concept of certain routing table symmetries, and then we sketch the scalability map of the Internet which we then use to make some bold predictions.

Bio: Gabor Retvari received the M.Sc. and Ph.D. degrees in electrical engineering from the Budapest University of Technology and Economics (BME). He is now a Senior Research Fellow at the High Speed Networks Laboratory, BME. He has been passionate about the questions of routing scalability for a long time and he has done plenty of research in this field, using a diverse set of mathematical tools ranging from abstract algebra to computational geometry and, more recently, information-theory. He maintains numerous open source scientific tools written in Perl, C and Haskell.

03/12/2014CS, Taub 337


Making machine learning accessible with GraphLab

Dr. Danny Bickson


GraphLab started as research project at Carnegie Mellon University were our main goal was implementing machine learning methods in large scale, (and writing papers about it!). Despite thousands of users of our open source software (and many papers written), the experience of setting up the system and using a distributed system was quite frustrating, where our target audience was mainly double PhDs with machine learning and graph theory & distributed systems background.

When forming a company around GraphLab, we have decided to switch our focus and make machine learning much more accessible for the masses. In this talk I will summarize our experience in this direction. I will describe data structures we found useful for many commonly repeating computation patterns in machine learning, including support for dense data, graph (sparse) data, text records and even images. I will describe how we tackle the problem of wrapping up machine learning algorithms in a way which is user friendly to non experts, while algorithmic details can be tweaked layer. During the talk I will show many demos of cool applications that run on GraphLab.

About GraphLab: GraphLab is a popular open source big data analytics project initiated in 2009 at Carnegie Mellon University. GraphLab implements numerous machine learning algorithms using a highly efficient multicore machines and over clusters. A year and a half ago we have formed a company in Seattle to backup the open source project, and grown to a machine learning research group of around 12 PhDs. GraphLab is free for academic usages, and has a major open source component.

Bio: Danny is holding a PhD in distributed systems at the Hebrew University (advised by Prof. Danny Dolev and Prof. Dahlia Malkhi), and was a postdoc at the machine learning department at Carngie Mellon University (advised by Prof. Carlos Guestrin and Prof. Joe Hellerstein from Berkeley). Danny was involved in the GraphLab project from its early stages and is a co-founder of the GraphLab company. His research interests are distributed algorithms and large scale machine learning.