# On Maximizing the Probability of Achieving Deadlines in Communication Networks
## Appendix A Proof of Convergence to a Stable Solution for DAP-CDFs
### Proof 3: Algorithm Returns Actual DAP-CDFs  
The AMPAD was shown to reach a stable solution for the functions \(F_{u}^{r}(\tau)\) in finite time. However, it has not been shown that these functions are proper CDFs of the deadline achievement probabilities (DAP-CDFs). This aspect is proven next.  
For any given set \(\{h_{u}(\tau)\}\) of routing tables, with \(u\) enumerating all nodes in the network, a corresponding set \(\{\tilde{F}_{u}(\tau)\}\) of DAP-CDFs exists and can be determined, for example, by using the method presented in [32]. The DAP-CDFs always satisfy  
\[\tilde{F}_{u}(\tau)=\tilde{F}_{v}(\tau)*f_{uv}(\tau)|_{v=h_{u}(\tau)} \tag{11}\]  
for all remaining TTDs \(\tau\), with \(v\) denoting the neighbors of \(u\).  
Next, we show that any set of CDFs different from \(\{\tilde{F}_{u}(\tau)\}\) violates Equation (11). Therefore, the set of DAP-CDFs \(\{\tilde{F}_{u}(\tau)\}\) is unique.  
**Lemma A2**.: _For a given set of routing tables, there can only be one unique set of CDFs that satisfies Equation (11)._  
Proof.: Assume that more than one set of CDFs satisfies Equation (11) for a given set of routing tables. Note that the assumptions \(F_{u}(\tau)=0,\tau<0\), and \(F_{s}(\tau)=1,\tau\geq 0\) must be satisfied by these sets. Denote one such set by \(\{\tilde{F}_{u}\}\), and define \(\tilde{\tau}\geq 0\) as the smallest value of \(\tau\) for which the CDFs in both sets present a difference for some node \(u\). Concretely, we have  
\[\tilde{\tau}=\operatorname*{arg\,min}_{\tau}(\exists u\in V:\tilde{F}_{u}( \tau)\
eq\tilde{F}_{u}(\tau)). \tag{12}\]Denote \(\tilde{u}\) as the node for which this \(\tilde{\tau}\) was found. The next hop for the remaining TTD \(\tilde{\tau}\), denoted as node \(v=h_{\tilde{u}}(\tilde{\tau})\), remains constant irrespective of the set of CDFs considered, as the routing table for \(\tilde{u}\) remains unchanged.  
By denoting \(\tilde{F}_{\tilde{u}}\) and \(\tilde{F}_{\tilde{u}}\) generically as \(F_{\tilde{u}}\), we may develop Equation (A11) for one or either of them as follows:  
\[F_{\tilde{u}}(\tilde{\tau}) =F_{v}(\tau)*f_{\tilde{u}v}(\tau)|_{\tau=\tilde{\tau}}\] (A13) \[=\int_{-\infty}^{\infty}F_{v}(\tilde{\tau}-t)f_{\tilde{u}v}(t)dt\] (A14) \[=\int_{t_{min}}^{\infty}F_{v}(\tilde{\tau}-t)f_{\tilde{u}v}(t)dt.\] (A15)  
Because of the assumption about the CDFs underlying Equation (A12) that the CDFs are identical for any argument smaller than \(\tilde{\tau}\), it follows that \(\tilde{F}_{v}(\tilde{\tau}-t)\) and \(\tilde{F}_{v}(\tilde{\tau}-t)\) in Equation (A15) are identical for any value of \(\tilde{\tau}-t<\tilde{\tau}\), and in Equation (A15), the integral must be equal for both sets of CDFs. Therefore, \(\tilde{F}_{\tilde{u}}(\tilde{\tau})=\tilde{F}_{\tilde{u}}(\tilde{\tau})\), which contradicts the initial assumption that more than one set of CDFs that satisfies Equation (A11) exists.  
From Lemma A2, it follows furthermore that any set that satisfies Equation (A11) must be the set of DAP-CDFs \(\{\tilde{F}_{u}(\tau)\}\). We show in the sequel that this is the case for the CDFs found by the AMPAD in a stable state and hence that the algorithm returns the DAP-CDFs.  
The node CDFs of the presented algorithm are calculated using the CDFs of the previous round as follows:  
\[F_{u}^{r}(\tau)=F_{v}^{r-1}(\tau)*f_{uv}(\tau)|_{v=h_{u}^{r}(\tau)},\] (A16)  
where \(v\) varies with \(\tau\) according to the routing table \(h_{u}^{r}(\tau)\) obtained at round \(r\). (Equation (A16) is a compact notation for the result of steps 12-16 in the algorithm.)  
In the stable state, the CDFs remain unchanged from one round to the next, and \(F_{u}^{r}~{}=~{}F_{u}^{r-1}\). Using this, we can rewrite Equation (A16) as  
\[F_{u}^{r}(\tau)=F_{v}^{r}(\tau)*f_{uv}(\tau)|_{v=h_{u}^{r}(\tau)}.\] (A17)  
This equation satisfies Equation (A11), which leads to the conclusion that the set \(\{F_{u}^{r}(\tau)\}\), with \(r\) in a stable state, is the set of DAP-CDFs.