Reverse Engineering Segment Routing Policies and Link Costs with Inverse Reinforcement Learning and EM

Network routing is a core functionality in computer networks that holds significant potential for integrating newly developed techniques with minimal software effort through the use of Software-Defined Networking (SDN). However, with the ever-expansion of the Internet, traditional destination-based IP routing techniques struggle to meet Quality-of-Service (QoS) requirements with SDN alone. To address these challenges, a modern network routing technique called Segment Routing (SR) has been designed to simplify traffic engineering and make networks more flexible and scalable. However, existing SR routing algorithms used by major Internet Service Providers (ISPs) are mostly proprietary, whose details remain unknown. This study delves into the inverse problem of a general type of SR and attempts to infer the SR policies given expert traffic traces. To this end, we propose MoME, a Mixture-of-Experts (MoE) model using the Maximum Entropy Inverse Reinforcement Learning (MaxEnt-IRL) framework that is capable of incorporating diverse features (e.g., router, link and context) and capturing complex relationships in the link cost, in combination with an Expectation-Maximization (EM) based iterative algorithm that jointly infers link costs and SR policy classes. Experimental results on real-world ISP topologies and Traffic Matrices (TMs) demonstrate the superior performance of our approach in jointly classifying SR policies and inferring link cost functions. Specifically, our model achieves classification accuracies of 0.90, 0.81, 0.75, and 0.57 on datasets that contain five SR policies over the small-scale Abilene and GÉANT, the medium-scale Exodus, and the large-scale Sprintlink network topologies, respectively.