Dynamic Entanglement Routing Based on Stream Processing for Quantum Networks

Quantum Networks (QNs) typically leverage teleportation to send quantum bits (called qubits) to their destinations. To teleport a data qubit from Alice to Bob, one Entanglement Connection (EC) between Alice and Bob needs to be established. Accordingly, we have to concurrently establish as many requested ECs as possible in order to maximize the network throughput. Conventional methods either assumed a known traffic matrix and calculated the Entanglement Paths (EPs) for all requests in one batch or maximized the number of ECs established between all Source-Destination (SD) pairs without considering the amount of data qubits to be teleported. These methods are not scalable in large scale QNs since it is time consuming to calculate the EPs for a batch of requests. In addition, there may be only very few data qubits to be teleported between some SD pairs. Accordingly, the latter method may establish many useless ECs. To address these issues, we propose a Dynamic Entanglement Routing (DER) scheme which determines the EPs based on stream processing. By introducing a method to derive an appropriate purification scheme along each EP, we further extend DER to Dynamic Entanglement Routing with Purification (DERP) that provides fidelity guarantee to the established ECs. Through extensive simulations, we demonstrate that DER outperforms two representative heuristics by up to 52.79% and 61.27%, respectively, in terms of average request completion time and when we have to ensure the fidelity of the established ECs, this performance improvement will become 21.05% and 48.67%, respectively, if DERP is adopted.