This paper aims at semi-parametrically estimating the input process to a Lévy-driven
queue by sampling the workload process at Poisson times. We construct a method-of-
moments based estimator for the Lévy process’ characteristic exponent. This method
exploits the known distribution of the workload sampled at an exponential time, thus
taking into account the dependence between subsequent samples. Verifiable conditions
for consistency and asymptotic normality are provided, along with explicit expressions
for the asymptotic variance. The method requires an intermediate estimation step of
estimating a constant (related to both the input distribution and the sampling rate); this
constant also features in the asymptotic analysis. For subordinator Lévy input, a partial
MLE is constructed for the intermediate step and we show that it satisfies the consistency
and asymptotic normality conditions. For general spectrally-positive Lévy input a biased
estimator is proposed that only uses workload observations above some threshold; the bias
can be made arbitrarily small by appropriately choosing the threshold.