Scalable and Privacy-Preserving Inter-AS Routing Through Machine-Learning-Based Graph Pruning

The decentralized nature of traditional inter-domain routing protocols may lead to several issues, including convergence issues and proneness to misconfiguration. In response to these problems, alternative approaches that leverage the Software Defined Networking (SDN) paradigm to increase the control over routing operations have been recently proposed. In this context, Autonomous Systems (ASs) form a multi-domain network where routing tasks are delegated to an SDN controller. To perform inter-domain routing, each controller must learn how to reach any other node outside its domain. Thus, severe privacy concerns emerge, as the controllers need to access sensitive, business-critical information (e.g., links costs) of all the domains. Recently, protocols for computing the shortest path between a source and a destination (i.e., a common policy in routing tasks) in a privacy-preserving manner have been proposed. These protocols are based on Multi-Party Computation (MPC) schemes, which guarantee privacy at the cost of high computational and communication complexity, thus limiting scalability. In this paper, we exploit machine learning (ML) techniques to prune the network graph by removing the nodes with a low likelihood of being traversed by the shortest path. Privacy-preserving shortest path algorithms are then executed on the pruned graph, at a much lower complexity. Extensive experiments performed in multiple scenarios (varying topologies and number of nodes) indicate a major reduction of computational complexity (up to 75%) and communication complexity (up to 85%), at the expense of an acceptable increase in the average path cost (at most by 16%).