Jens B. Schmitt

Network Calculus (NC) is a versatile analytical methodology to efficiently compute performance bounds in networked systems. The arrival and service curve abstractions allow to model diverse and heterogeneous distributed systems. The operations to compute residual service curves and to concatenate sequences of systems enable an efficient and accurate calculation of per-flow timing guarantees. Yet, in some scenarios involving multiple concurrent flows at a system, the central notion of so-called min-plus service curves is too weak to still be able to compute a meaningful residual service curve. In these cases, one usually resorts to so-called strict service curves that enable the computation of per-flow bounds. However, strict service curves are restrictive: (1) there are service elements for which only min-plus service curves can be provided but not strict ones and (2) strict service curves generally have no concatenation property, i.e., a sequence of two strict systems does not yield a strict service curve. In this report, we extend NC to deal with systems only offering aggregate min-plus service curves to multiple flows. The key to this extension is the exploitation of minimal arrival curves, i.e., lower bounds on the arrival process. Technically speaking, we provide basic performance bounds (backlog and delay) for the case of negative service curves. We also discuss their accuracy and show them to be tight. In order to illustrate their usefulness we also present patterns of application of these new results for: (1) heterogeneous systems involving computation and communication resources and (2) finite buffers that are shared between multiple flows.

Network technologies are being developed to increase not only performance of data communication but also for provision of deterministic guarantees. Such designs foster the development of distributed real-time applications. When networks must provide time-sensitive communication, a commonly found design feature is First-In First-Out (FIFO) – a natural design for multiplexing different data flows into queues and for scheduling queued data. Alongside technological advancements, there is the development of formal tools to reason about timing behavior. Network Calculus is such a methodology. It has been widely adopted already and its modeling capabilities were extended to features found in modern standards as, e.g., in IEEE Time-Sensitive Networking. However, the basic challenge to compute a deterministic bound on a flow’s worst-case end-to-end delay in FIFO networks still imposes challenges. Different …

The stochastic network calculus (SNC) holds promise as a versatile and uniform framework to calculate probabilistic performance bounds in networks of queues. A great challenge to accurate bounds and efficient calculations are stochastic dependencies between flows due to resource sharing inside the network. However, by carefully utilizing the basic SNC concepts in the network analysis the necessity of taking these dependencies into account can be minimized. To that end, we unleash the power of the pay multiplexing only once principle (PMOO, known from the deterministic network calculus) in the SNC analysis. We choose an analytic combinatorics presentation of the results in order to ease complex calculations. In tree-reducible networks, a subclass of general feedforward networks, we obtain an effective analysis in terms of avoiding the need to take internal flow dependencies into account. In a …

Weighted round robin (WRR) is an effective, yet particularly easy-to-implement packet scheduler. A slight modification in the implementation of WRR, interleaved weighted round robin, has been proposed as an enhancement of the initial version and has been recently investigated. Network calculus is a versatile framework to model and analyze such network schedulers. By means of this, one can derive theoretical upper bounds on network performance metrics, such as delay or backlog. In our previous work, we derive performance bounds by showing that both round-robin variants belong to a class called bandwidth-sharing policy; however, the proofs are incomplete and thus, we cannot conclude that the round-robin schedulers are bandwidth-sharing policies (under variable packet sizes). To that end, in the subsequent erratum, we introduce so-called resource-segregating policies and show the round-robin schedulers to be members of this class.

Weighted round robin (WRR) is a simple, efficient packet scheduler providing low latency and fairness by assigning flow weights that define the number of possible packets to be sent consecutively. A variant of WRR that mitigates its tendency to increase burstiness, called interleaved weighted round robin (IWRR), has seen analytical treatment recently [1]; a network calculus approach was used to obtain the best-possible strict service curve. From a different perspective, WRR can also be interpreted as an emulation of an idealized fair scheduler known as generalized processor sharing (GPS). Inspired by profound literature results on the performance analysis of GPS, we show that both, WRR and IWRR, belong to a larger class of fair schedulers called bandwidth-sharing policies. We use this insight to derive new strict service curves for both schedulers that, under the additional assumption of constrained cross-traffic …

Given the nature of satellites orbiting the Earth on a fixed trajectory, in principle, it is interesting to investigate how this invariant can be exploited for security purposes. In particular, satellite orbit information can be retrieved from public databases. Using time difference of arrival (TDOA) measurements from multiple receivers, we can check this orbit information against a corresponding TDOA-based signature of the satellite. In that sense, we propose an orbit-based authentication scheme for down-link satellite communications in this paper. To investigate the properties and fundamentals of our novel TDOA signature scheme we study two satellite systems at different altitudes: Iridium and Starlink. Clearly, many challenging questions with respect to the feasibility and effectiveness of this authentication scheme arise; to name some: how many receivers are necessary, how should they be distributed, and how many …

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 Hölder’s inequality, lead to a significant improvement of delay bounds with fractional Brownian motion as a traffic model …

The integrity of location information is crucial in many applications such as access control or environmental sensing. Although there are several solutions to the problem of secure location verification, they all come with expensive requirements such as tight time synchronization, cooperative verification protocols, or dedicated hardware. Yet, meeting these requirements in practice is often not feasible which renders the existing solutions unusable in many scenarios. We therefore propose a new solution which exploits the mobility of verifiers to verify locations. We show that mobility can help minimize system requirements while at the same time achieves strong security. Specifically, we show that two moving verifiers are sufficient to securely verify location claims of a static prover without the need for time synchronization, active protocols, or otherwise specialized hardware. We provide formal proof that our method is …

Computing probabilistic end-to-end delay bounds is an old, yet still challenging problem. Stochastic network calculus enables closed-form delay bounds for a large class of arrival processes. However, it encounters difficulties in dealing with dependent flows, as standard techniques require to apply Hölder’s inequality. In this paper, we present an alternative bounding technique that, under specific conditions, treats them as if flows were independent. We show in two case studies that it often provides better delay bounds while simultaneously significantly improving the computation time.

Stochastic network calculus is a versatile framework to derive probabilistic end-to-end delay bounds. Its popular subbranch using moment-generating function bounds allows for accurate bounds under the assumption of independence. However, in the dependent flow case, standard techniques typically invoke Hölder's inequality, which in many cases leads to loose bounds. Furthermore, optimization of the Hölder parameters is computationally expensive. In this work, we show that two simple, yet effective techniques related to the deterministic network calculus are able to improve the delay analysis in many scenarios, while at the same time enabling a considerably faster computation. Specifically, in a thorough numerical evaluation of two case studies, we show that using the proposed techniques: 1. we can improve the stochastic delay bounds often considerably and sometimes even obtain a bound where the …