A Routing Framework for Quantum Entanglements with Heterogeneous Duration

Entanglement routing is a fundamental problem in the network layer of quantum networks, which has become an increasingly popular research topic. This paper addresses a common problem of existing entanglement routing algorithms: they assume the Synchronized Single-time-slot model (SynSts) that requires all entanglement generation and swapping to be completed in a single time slot. This model does not align with future large-scale quantum networks that will incrementally deploy heterogeneous devices: old ones generate short-duration entanglements while advanced devices can generate long-duration entanglements. Forcing long-duration entanglements to finish in one time slot will result in sub-optimal routing performance. This paper presents a new routing framework for quantum entanglements with heterogeneous duration, including a Synchronous Multi-time-slots (SynMts) routing model and two algorithms to manage routing requests and link states. The framework is designed in such a generalized way that all existing algorithms designed for the SynSts model can still run with the SynMts model while achieving higher performance. We conduct experiments using three recently-proposed routing algorithms and find they all achieve evident throughput improvement in the new framework.