The Taub Faculty of Computer Science Events and Talks

Packet classification is a building block in many network services such as routing, filtering, intrusion detection, accounting, monitoring, load-balancing and policy enforcement. Compression has gained attention recently as a way to deal with the expected increase of classifiers size. Typically, compression schemes try to reduce a classifier size while keeping it semantically-equivalent to its original form. Inspired by the advantages of popular compression schemes (e.g. JPEG and MPEG), in the presentation I overview the applicability of lossy compression to create packet classifiers requiring less memory than optimal semantically-equivalent representations. Our objective is to find a limited-size classifier that can correctly classify a high portion of the traffic so that it can be implemented in commodity switches with classification modules of a given size. Next an optimal dynamic programming based algorithms for several versions of the problem is presented and described how to treat the small amount of traffic that cannot be classified, especially in software-defined networks. We evaluate their performance on real classifiers and traffic traces and show that in some cases we can reduce a classifier size by orders of magnitude while still classifying almost all the traffic correctly. The presentation is concluded with an outlook on more general applications of lossy compression.

Bio:
Janos Tapolcai received his M.Sc. (’00 in Technical Informatics), Ph.D. (’05 in Computer Science) degrees from Budapest University of Technology and Economics (BME), Budapest, and D.Sc. ('13 in Engineering Science) from Hungarian Academy of Sciences (MTA). Currently he is an Associate Professor at the High-Speed Networks Laboratory at the Department of Telecommunications and Media Informatics at BME. His research interests include applied mathematics, combinatorial optimization, optical networks and IP routing, addressing and survivability. He is an author of over 110 scientific publications, he is the recipient of the Google Faculty Award and Best Paper Award in ICC'06, in DRCN'11. He is a TPC member of leading conferences such as IEEE INFOCOM (2012 - 2014), and is a winner of MTA Momentum (Lendulet) Program.

Gábor Rétvári 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.