# On Maximizing the Probability of Achieving Deadlines in Communication Networks
## 1 Introduction  
End-to-end (E2E) delay, which measures the time taken for packets to travel from a source node to a destination node in communication networks, is a widely used performance metric. It is frequently defined as the average delay of packets along a given path. This average delay is typically calculated as the sum of the average delays of each individual link along the path. However, it is crucial to point out that link delays possess inherent stochastic characteristics, leading to stochastic path delays and E2E delays within the network [1]. Consequently, link and path delays may be modeled by probability density functions (PDFs). An example is shown in Figure 1, which illustrates the PDFs of the delay of two paths \(P_{1}\) and \(P_{2}\). The expected E2E delay of path \(P_{2}\) (dashed orange line) is larger than the expected E2E delay of path \(P_{1}\) (dashed blue line). By expected E2E delay, we refer to the expected value of the corresponding PDF. Some existing and emerging wireless network communication applications in fields such as critical care and industrial processes require timely data delivery in order to fulfill their purpose. In these contexts, lost packets or missed deadlines can result in severe consequences, especially in industrial control applications [2]. Therefore, it is crucial to meet deadlines with a certain level of reliability. Analytic tools play a significant role in this context, as they can provide operators with key information about the supporteddelay and reliability bounds [3], helping operators to make informed decisions to fulfill the application's requirements. Consider thus a time-critical networking application requiring data from a source node to arrive at a destination node by a given deadline. In Figure 1, the deadline is shown by the dashed black line. The shaded areas under the curves to the right of the deadline indicate the probability of missing the deadline for each path. Even though path \(P_{1}\) has a smaller expected delay than path \(P_{2}\), the probability of missing the deadline is higher along path \(P_{1}\). This example supports the idea that analyzing and designing time-critical network communications by considering the probability density functions of E2E delays rather than relying solely on statistical measures, such as expected delay, should be a beneficial approach. E2E delays ensue from the accumulation of delays of links followed by the data. We refer to the likelihood of successfully meeting a specified deadline for timely data delivery, considering the PDF of E2E delays, as the deadline achievement probability (DAP). Because the routing algorithm ultimately selects the paths, the statistics of E2E delays and the resulting DAPs are closely linked to the routing protocol in use. Building on the aforementioned ideas, we present our first contribution in the form of an algorithm that determines the DAP between a source and a destination node based on probability distributions of link delays and the given routing tables. This algorithm allows for analyzing the DAPs of a wide range of routing protocols within the family of proactive, non-multipath or multicast routing strategies. This therefore contributes to works such as [5; 6] by providing an additional methodology and corresponding performance metric for comparing routing protocols. We further extend this algorithm to iteratively optimize the routing tables within the network, resulting in a routing protocol that maximizes the DAP for every transmitted packet. Both algorithms operate locally at each node and rely solely on information exchanged with direct neighbors. We prove the convergence of both algorithms to the correct solution within a finite number of iterations. In addition to these contributions, we present a practical implementation of the algorithm. We demonstrate its functionality through simulations and provide a quantitative assessment of its performance. The structure of this paper is as follows. Section 2 provides an overview of related works in the literature.