  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.
