Editing Distributed Routing in a Quantum Internet (section)

==Protocol Description==
<!-- Mathematical step-wise protocol algorithm helpful to write a subroutine. -->
* All of the three routing algorithms are used as a subroutine (<math>\mathbf{PathDisc}</math>) of '''Algorithm 1'''.
* The entire routing procedure between any two nodes can be subdivided into following three phases:
# Path discovery phase.
# Entanglement reservation phase.
# Entanglement distribution phase.

'''Algorithm 1''' - Distributed Routing Algorithm <math>(s, e, \mathcal{G}, D, cap)</math>
# <math>round = \lceil \frac{D_{s,e}}{cap} \rceil</math>
# <math>i = 1</math> 
# '''while''' <math> i \leq round</math> '''do'''
## <math>CommPath_{s,e} = \mathbf{PathDisc}(s, e, \mathcal{G}, D_{s,e})</math> 
## <math>CommPath_{s,e} = \{ s=u_0, u_1,...,u_{d-1} = e\}</math> 
## '''if''' in <math>CommPath_{s,e}</math> some of the neighbour nodes do not have enough entangled links '''then'''
### Generate all the missing links
## '''else'''
### <math>j=1</math> 
### '''while''' <math>j \leq d-2</math> '''do'''
#### <math>EntSwap(u_0,u_j,j_{j+1})</math> 
#### j = j + 1
### dem = dem - cap
### i = i + 1

* During the path discovery phase (<math>\mathbf{PathDisc}</math>) each node decides the next hop on the basis of the physical graph topology and the information it has about the shared entangled links with its neighbours.
* In this phase given a demand <math>D_{v,e}</math> if <math>v</math> is an optimal neighbour of <math>u</math> to reach a destination node <math>e</math> then the routing algorithm has three options:
** (1) Select the path via <math>v</math> and generate sufficient amount of links between <math>u, v</math> - see '''Algorithm 2 - Modified Greedy'''
** (2) Try to select another neighbour with whom it already shares enough amount of entangled links - see '''Algorithm 3 - Local Best Effort'''
** (3) (2) + Assume that the quantum repeater nodes have information about its neighbours as well as the neighbours of the neighbours in the virtual graph - see '''Algorithm 4 - NoN Local Best Effort'''.