  Scheduling packets with end-to-end deadline constraints in multihop networks
is an important problem that has been notoriously difficult to tackle.
Recently, there has been progress on this problem in the worst-case traffic
setting, with the objective of maximizing the number of packets delivered
within their deadlines. Specifically, the proposed algorithms were shown to
achieve $\Omega(1/\log(L))$ fraction of the optimal objective value if the
minimum link capacity in the network is $C_{\min}=\Omega(\log (L))$, where $L$
is the maximum length of a packet's route in the network (which is bounded by
the packet's maximum deadline). However, such guarantees can be quite
pessimistic due to the strict worst-case traffic assumption and may not
accurately reflect real-world settings. In this work, we aim to address this
limitation by exploring whether it is possible to design algorithms that
achieve a constant fraction of the optimal value while relaxing the worst-case
traffic assumption.
  We provide a positive answer by demonstrating that in stochastic traffic
settings, such as i.i.d. packet arrivals, near-optimal,
$(1-\epsilon)$-approximation algorithms can be designed if $C_{\min} =
\Omega\big(\frac{\log (L/\epsilon) } {\epsilon^2}\big)$. To the best of our
knowledge, this is the first result that shows this problem can be solved
near-optimally under nontrivial assumptions on traffic and link capacity. We
further present extended simulations using real network traces with
non-stationary traffic, which demonstrate that our algorithms outperform
worst-case-based algorithms in practical settings.
