Dr. Gordon Wilfong Distinguished Member of Technical Staff Mathematics of Networks and Systems Department Bell Labs in Alcatel-Lucent "Optimal Path Encoding for SDN ” Thursday, September 24, 4:00 PM Packard Lab room 258 |

**Abstract: ** Packet networks need to maintain state in the form of forwarding tables at each switch. The cost of this state increases as networks support ever more sophisticated per-flow routing, traffic engineering, and service chaining. Per-flow or per-path state at the switches can be eliminated by encoding each packet's desired path in its header. A key component of such a method is an efficient encoding of paths through the network. We introduce a mathematical formulation of this optimal path-encoding problem. We prove that the problem is APX-hard, by showing that approximating it to within a factor less than 8/7 is NP-hard. Thus, at best we can hope for a constant-factor approximation algorithm. We then present such an algorithm, approximating the optimal path-encoding problem to within a factor of 2. Finally, we provide empirical results illustrating the effectiveness of the proposed algorithm. (Joint work with H. Adiseshu (Bell Labs) and U. Niesen (Qualcomm).)

**Bio: ** Gordon Wilfong is a Distinguished Member of Technical Staff in the Mathematics of Networks and Systems Department department at Bell Labs in Alcatel-Lucent. His major research interests are in algorithm design and analysis. Dr. Wilfong received his B.Sc., First Class Honours, in mathematics from Carleton University in 1980 and his M.S. and Ph.D. in computer science from Cornell University in 1983 and 1984 respectively.