Yashar
Ganjali,
Department
of
Computer
Science
University
of
Toronto
A widely-used technique to deal with network resource limitations is to focus on elephant flows. The intuition is that since elephant flows carry most of the packets, allocating resources to them will lead to significant returns. In this talk, we will take a closer look at this technique, and argue that we need to rigorously identify objective and cost functions rather than simply treating elephant flows as the silver bullet for a wide range of network resource allocation problems. Even though this seems like a trivial statement, a survey of papers published in top networking conferences shows that it is often overlooked.
As a case study, we will focus on the problem of limited flow table sizes in OpenFlow switches. Typically, this problem is solved by allocating the entries to elephant flows, and using default catch-all rules for the rest of traffic. Trying to formally define the problem, we'll show how the optimum solution highly dependents on the objective and cost functions. For specific objective and cost functions, we model the problem as a knapsack problem, analyze how its solution minimizes the table occupancy, and show the similarities to and differences from the default idle timeout mechanism in OpenFlow switches.
Finally, we present a new approach to minimize flow table occupancy based on the insight gained from the knapsack model analysis. Our solution expedites rule eviction by forecasting the TCP flow termination from RST/FIN packets, and delays rule installation by incubating non-TCP flows. It reduces average flow table occupancy between 16%-62% in various networks for the negligible cost of less than 1.5% reduction in hit ratio.
Bio: Yashar Ganjali is an associate professor of computer science at the University of Toronto. He is a member of Computer Systems and Networks Group. He received his BSc in Computer Engineering from Sharif University of Technology, and his MSc in Computer Science from University of Waterloo. He completed his PhD in Electrical Engineering at Stanford University. His PhD dissertation studied the buffer sizing problem in Internet core routers, and showed the possibility of reducing buffer sizes from millions of packets to just a few packets in Internet core routers.
Prof. Ganjali's research interests include packet switching architectures/algorithms, software defined networks, data center networking, congestion control, network measurements, and online social networks. He has received several awards for his research including best paper award in Internet Measurement Conference 2008, best paper runner up in IEEE INFOCOM 2003, best demo runner up in SIGCOMM 2008, first and second prizes in NetFPGA Design Competition 2010, Cisco Research Award, and a Distinguished Faculty Award from Facebook.