In this work, we describe a routing algebra corresponding to the problem of establishing end-to-end quantum entanglements between nodes connected through a network of first generation quantum repeaters. Our goal is to design an algorithm which can determine all the routes and swapping schedules to achieve maximal rates of end-to-end entanglement. We aim to provide an improvement in terms of complexity over an existing solution while increasing the number of routes and schedules available to offer more alternatives for the entanglement generation layer of a quantum protocol stack.

Most Internet routing protocols have one of two algorithms lurking at their core - either Dijkstra's algorithm in the case of link-state protocols or a distributed Bellman-Ford algorithm in the case of distance-vector or path-vector protocols. When computing simple shortest paths these protocols can be modified to utilize all best paths with a combination of next-hop sets and Equal Cost Multi-Path (ECMP) forwarding. We show that this picture breaks down even for simple modifications to the shortest path metric. This is illustrated with widest-shortest paths where among all shortest paths only those with greatest bandwidth are considered best. In this case Bellman-Ford and Dijkstra may compute different sets of paths and neither can compute all best paths. In addition, some paths computed by Dijkstra's algorithm cannot be implemented with next-hop forwarding. We provide a general algebraic model that helps to clarify such anomalies. This is accomplished by computing paths within the route metric rather than with specialized algorithmic extensions. Our results depend on the distinction between global and local optima that has hitherto been applied almost exclusively to more exotic routing protocols such as BGP.

We present a formal distributed algorithm that can be used for the deployment of arbitrary routing policies in a network infrastructure that attempts to complete the ideas proposed by Griffin et al. We prove that our algorithm is based on a function that satisfies conditions proposed by Bertsekas. These conditions guarantee that the distributed version of the algorithm will converge and yield the same result as a centralized computation of the routing matrix. We also present a prototype in Haskell that illustrates the possibilities of defining policies and general computations on them.