# On Maximizing the Probability of Achieving Deadlines in Communication Networks
## Appendix B Proof of Optimality  
The proof in this appendix is valid only for the AMPAD.  
Among all possible sets of routing tables and their corresponding sets of DAP-CDFs, we will show that the set of DAP-CDFs \(\{F_{u}^{r}(\tau)\}\) found by the AMPAD after reaching a stable state have the highest DAP for any given remaining TTD \(\tau\). We will prove this by contradiction. Assume that there is a set of routing tables \(\{\tilde{h}_{u}(\tau)\}\) and a corresponding set of DAP-CDFs \(\{\tilde{F}_{u}(\tau)\}\) whose DAP is larger as follows:  
\[\exists u\in V,\tau\geq 0:\tilde{F}_{u}(\tau)>F_{u}^{r}(\tau).\] (A18)  
Consider further that \(\tilde{\tau}\geq 0\) is the smallest remaining TTD for which the above equation is valid for at least one node \(\tilde{u}\) in the network. Concretely, we have  
\[\tilde{\tau}=\operatorname*{arg\,min}_{\tau}(\exists\tilde{u}\in V:\tilde{F}_ {\tilde{u}}(\tau)>F_{\tilde{u}}^{r}(\tau)).\] (A19)The above definition of \(\tilde{\tau}\) implies that there is no DAP \(\tilde{F}_{u}(\tau)\) in the network larger than \(F_{u}^{r}(\tau)\) for all remaining TTDs \(\tau<\tilde{\tau}\):  
\[\forall u\in V,\tau<\tilde{\tau}:\tilde{F}_{u}(\tau)\leq F_{u}^{r}(\tau). \tag{100}\]  
This holds in particular for the neighbors of \(\tilde{u}\), whose DAP \(\tilde{F}_{\tilde{u}}(\tilde{\tau})\) can be calculated in analogy with Equation (11) by letting \(\tilde{v}=\tilde{h}_{\tilde{u}}(\tilde{\tau})\) be the next hop used by \(\tilde{u}\) at remaining TTD \(\tilde{\tau}\) and performing convolution as follows:  
\[\tilde{F}_{\tilde{u}}(\tilde{\tau}) =\tilde{F}_{\tilde{v}}(\tau)*f_{\tilde{u}\tilde{v}}(\tau)|_{\tau= \tilde{\tau}} \tag{101}\] \[=\int_{-\infty}^{\infty}\tilde{F}_{\tilde{v}}(\tilde{\tau}-t)f_{ \tilde{u}\tilde{v}}(t)dt\] (102) \[=\int_{t_{min}}^{\infty}\tilde{F}_{\tilde{v}}(\tilde{\tau}-t)f_{ \tilde{u}\tilde{v}}(t)dt. \tag{103}\]  
Because of Equation (100), \(\tilde{F}_{\tilde{v}}(\tilde{\tau}-t)\leq F_{\tilde{v}}^{r}(\tilde{\tau}-t)\) for any value of \(\tilde{\tau}-t<\tilde{\tau}\). Therefore, for Equation (103), it holds that  
\[\int_{t_{min}}^{\infty}\tilde{F}_{\tilde{v}}(\tilde{\tau}-t)f_{ \tilde{u}\tilde{v}}(t)dt \leq\int_{t_{min}}^{\infty}F_{\tilde{v}}^{r}(\tilde{\tau}-t)f_{ \tilde{u}\tilde{v}}(t)dt \tag{104}\] \[=\int_{-\infty}^{\infty}F_{\tilde{v}}^{r}(\tilde{\tau}-t)f_{ \tilde{u}\tilde{v}}(t)dt\] (105) \[=F_{\tilde{v}}^{r}(\tau)*f_{\tilde{u}\tilde{v}}(\tau)|_{\tau= \tilde{\tau}}. \tag{106}\]  
Above, Equation (106) is the DAP-CDF of \(\tilde{u}\) when routing over \(\tilde{v}\) at remaining TTD \(\tilde{\tau}\). However, after reaching a stable state, the ADPAD may not route over node \(\tilde{v}\) for that remaining TTD. In fact, the DAP may be maximized by routing over another node \(x=h_{\tilde{u}}(\tilde{\tau})\) whose DAP-CDF satisfies  
\[F_{\tilde{v}}^{r}(\tau)*f_{\tilde{u}\tilde{v}}(\tau)|_{\tau=\tilde{\tau}}\leq F _{x}^{r}(\tau)*f_{\tilde{u}\tilde{v}}(\tau)|_{\tau=\tilde{\tau}}=F_{\tilde{u }}^{r}(\tilde{\tau}). \tag{107}\]  
From the chain of inequalities between Equations (101) and (107), we conclude that  
\[\tilde{F}_{\tilde{u}}(\tilde{\tau})\leq F_{\tilde{u}}^{r}(\tilde{\tau}), \tag{108}\]  
which contradicts the initial assumption that a set of DAP-CDFs \(\{\tilde{F}_{u}(\tau)\}\) exists that contains CDFs with larger DAPs than the corresponding DAPs of the set \(\{F_{u}^{r}(\tau)\}\) found by the algorithm in a stable state. Consequently, the ADPAD achieves at each node the maximum possible DAP values for all remaining TTDs.