Optimal flow segmentation in SDN with memory constraints: a reinforcement learning approach

Speaker : Antonio Massaro
Fondazione Bruno Kessler
Date: 22/11/2017
Time: 2:00 pm - 3:00 pm
Location: LINCS Seminars room


Datacenter flow routing relies on packet-in messages generated by switches and directed to the controller upon new flows arrivals. The SDN controller reacts to packet-in events by installing forwarding rules in the memory of all switches along an optimized path. Since flow arrival rates can peak to millions per second, a relevant constraint is represented by the scarce amount of TCAM memory on switches. We assume that if a routing table is full, a flow will be routed on a default, sub-optimal path. A viable solution is to restrict the optimized traffic to critical flows: this corresponds to performing traffic segmentation, prioritizing larger flows over smaller flows. However, choosing the optimal threshold to discriminate optimized flows from non-optimized flows is not a trivial task. This work focuses on learning the optimal flow segmentation policy under memory constraints. We formulate this task as a Markov decision problem. Based on the structure of the optimal stationary policy, we propose a reinforcement learning algorithm tailored to the problem at hand. We prove it is adaptive, correct and has a polynomial time complexity. Finally, numerical experiments characterize the performance of the algorithm.Joint work with Francesco de Pellegrini (Fondazione Bruno Kessler), Lorenzo Maggi (Huawei Algorithmic and Mathematical Sciences Lab, Paris)