Social Utility Maximization via Entanglement Connection Provisioning in Quantum Networks

From the perspective of user experience, when optimizing resource provisioning in networks, we have to maximize social utility, which is an abstraction of what users can obtain from the service provided by a network. In quantum networks, unlike their counterparts, circuit-switched classical networks, (i) the utility obtained by a demand is not always concave for the number of Entanglement Connections (ECs) we provision to it; and (ii) each demand requires a different amount of quantum resources over each link along the path to establish an EC. As a result, the Social Utility Maximization (SUM) problem is more challenging than in classic circuit-switched networks. In this paper, we propose an approach also called SUM to maximize social utility in quantum networks by provisioning an appropriate number of ECs (and corresponding resources) to demands. We first formulate the SUM problem and analyze it based on Lagrangian relaxation and duality techniques. Accordingly, we derive the optimal EC provisioning scheme for a given Lagrangian multiplier, depending on whether the utility function of each demand is convex, concave, or sigmoid-like. After that, a primal-dual iteration algorithm is proposed to determine the optimal EC provisioning scheme to maximize social utility. We conduct extensive simulations to demonstrate that SUM outperforms the state-of-the-art approach to maximizing quantum network throughput, i.e., EFiRAP, by up to 58.4%.