# On Maximizing the Probability of Achieving Deadlines in Communication Networks
## 4 Algorithm for Determining the Probabilities of Achieving Deadlines  
Assume that the routing tables of all nodes in the network have been set to a known and valid state, for instance, by using a metric such as the hop count. The proposed algorithm for finding the DAP-CDFs \(\tilde{F}_{u}(\tau)\) corresponding to the routing tables \(\tilde{h}_{u}(\tau)\) is based on an iterative approach that leverages Equations (1) and (2). During iteration, intermediate cumulative distribution functions (CDFs) are obtained and denoted by \(F_{u}(\tau)\). These CDFs eventually converge to actual DAP-CDFs, denoted by \(\tilde{F}_{u}(\tau)\). The complete Algorithm for Determining the Probabilities of Achieving Deadlines (ADPAD) is presented in pseudo-code as Algorithm 1 below.  
The algorithm has two phases: an initialization phase and a round-based updating phase of the node CDFs \(F_{u}(\tau)\). Both phases run locally on each node and rely only on the exchange of information with direct neighbors. The algorithm description is therefore presented from the local view of an arbitrary node \(u\). The algorithm is carried out in a distributed and joint fashion by all nodes in the network. No centralized processing is performed at any time.  
The CDF of a given node \(u\) is initialized as \(F_{u}(\tau)=0\) (line 5). After initialization, a round-based updating of the CDFs begins. The destination \(s\) is an exception because its CDF is initialized as the step function (\(F_{s}(\tau)=1\) for \(\tau\geq 0\) and \(0\) otherwise) (line 3) and does not ever change.  
At the beginning of each new round, every node in the network and the destination broadcast their CDFs (line 9). We assume a mechanism is in place at the data link layer (DLL) for ensuring correct delivery to all corresponding neighbors. Upon receiving all neighbors' CDFs (line 10), every node except the destination \(s\) performs one round of the algorithm. With a focus on node \(u\), the round consists of the following two steps:  
**Step 1:**: For every neighbor \(v_{i}\) (line 11), node \(u\) calculates the expression in Equation (1), using the latest \(F_{v_{i}}(\tau)\) received instead of the still unknown \(\tilde{F}_{v_{i}}(\tau)\) (line 12). The set \(N(u)\) in line 11 denotes the neighboring nodes of node \(u\) in the network, consisting of the nodes to which \(u\) can directly communicate or forward data packets.
**Step 2:**: Node \(u\) updates its CDF \(F_{u}(\tau)\) according to Equation (2) (line 14). The resulting CDF will be broadcast at the beginning of the next round.  
After performing the above steps, \(u\) waits until the beginning of the next round. The rounds are repeated at regular intervals by all nodes in the network.  
```
procedureInit  if this node is destination then \(F_{s}(\tau)\gets 1\), \(\tau\geq 0\), \(0\) otherwise else \(F_{u}(\tau)\gets 0\)\(\forall\tau\) endif endprocedureprocedureRound  Broadcast \(F_{u}\)  Receive CDFs \(F_{v_{i}}\) from all neighbors \(v_{i}\) for each \(v_{i}\in N(u)\)do \(F_{u\to v_{i}}(\tau)\gets F_{v_{i}}(\tau)*f_{uv_{i}}(\tau)\)\(\forall\tau\) endfor \(F_{u}(\tau)\gets F_{u\to\tilde{h}_{u}(\tau)}(\tau)\)\(\forall\tau\) endprocedure
```  
**Algorithm 1** Algorithm for Determining the Probabilities of Achieving Deadlines (ADPAD)  
Appendix A presents proof that the ADPAD converges to a stable solution in finite time and that it returns actual DAP-CDFs. While DAP-CDFs obtained using the aforementioned approach correspond to given routing tables, it is important to note that these routing tablesmay not be optimal for deadline-aware traffic. A modification of the ADPAD can be made in order to also return DAP-optimal routing tables. The details of this modification will be explained in the following section.