On the Stochastic End-to-End Delay Analysis in Sink Trees Under Independent and Dependent Arrivals

摘要

Sink trees are a frequent topology in many networked systems; typical examples are multipoint-to-point label switched paths in Multiprotocol Label Switching networks or wireless sensor networks with sensor nodes reporting to a base station. In this paper, we compute end-to-end delay bounds using a stochastic network calculus approach for a flow traversing a sink tree. For n servers with one flow of interest and n cross-flows, we derive solutions for a general class of arrivals with moment-generating function bounds. Comparing algorithms known from the literature, our results show that, e.g., pay multiplexing only once has to consider less stochastic dependencies in the analysis. In numerical experiments, we observe that the reduced dependencies to consider, and therefore less applications of Holder's inequality, lead to a significant improvement of delay bounds with fractional Brownian motion as a traffic model. Finally, we also consider a sink tree with dependent cross-flows and evaluate the impact on the delay bounds.