  In this paper we analyze the distribution of the Age of Information (AoI) of
a tagged data stream sharing a processor with a set of other data streams. We
do so in the highly general setting in which the interarrival times pertaining
to the tagged stream can have any distribution, and also the service times of
both the tagged stream and the background stream are generally distributed. The
packet arrival times of the background process are assumed to constitute a
Poisson process, which is justified by the fact that it typically is a
superposition of many relatively homogeneous streams. The first major
contribution is that we derive an expression for the Laplace-Stieltjes
transform of the AoI in the resulting GI+M/GI+GI/1 model. Second, we use
stochastic ordering techniques to identify tight stochastic bounds on the AoI.
In addition, when approximating the tagged stream's inter-generation times
through a phase-type distribution (which can be done at any precision), we
present a computational algorithm for the mean AoI. As illustrated through a
sequence of numerical experiments, the analysis enables us to assess the impact
of background traffic on the AoI of the tagged stream.
