A Privacy-Preserving Reinforcement Learning Algorithm for Multi-Domain Virtual Network Embedding

The problem of optimally deploying a virtual network onto a substrate physical network is referred to as Virtual Network Embedding (VNE). In general, this embedding is requested by a customer to an Internet Service Provider (ISP), which performs the VNE over its physical telecom network. In several situations, the physical substrate infrastructure is composed of multiple independent ISPs. In this scenario, ISPs are concerned about exposing to a third-party entity (e.g., the customer) sensitive infrastructural details that are needed to perform an effective embedding. Following a common privacy-preserving approach, known as Limited Information Disclosure (LID), the embedding may be performed by the customer based on a limited and abstracted view of the multi-domain infrastructure that ISPs accept to expose. With this approach, embedding is sub-optimal (e.g., embedding cost is not minimized) in comparison with the case where all information is available, i.e., Full Information Disclosure (FID). In this work, we propose a Reinforcement-Learning-based algorithm able to process data that the customer and ISPs cipher under the Shamir Secret Sharing (SSS) scheme. This approach guarantees total privacy to both the customer and the ISPs (e.g., details about a virtual function are only revealed to the ISP in charge of hosting it) and achieves comparable embedding cost of an existing FID heuristic, as observed from extensive simulations. The main drawback of our algorithm is the high overhead of data that ISPs and the customer need to exchange with each other to execute it. Hence, we also explore the trade-off between embedding cost and data overhead resulting from the reduction of operations done by the RL. In general, intermediate embedding costs between the FID and LID heuristics can be obtained at a significant reduction of data overhead, while not sacrificing any privacy guarantees.