An information-theoretic and game-theoretic study of timing channels

Abstract

This paper focuses on jammed timing channels. Pure delay jammers with a maximum delay constraint, an average delay constraint, or a maximum buffer size constraint are explored, for continuous-time or discrete-time packet waveforms. Fluid waveform approximations of each of these classes of waveforms are employed to aid in analysis. Channel capacity is defined and an information-theoretic game based on mutual information rate is studied. Min-max optimal jammers and max-min optimal input processes are sought. Bounds on the min-max and max-min mutual information rates are described, and numerical examples are given. For maximum-delay-constrained (MDC) jammers with continuous-time packet waveforms, saddle-point input and jammer strategies are identified. The capacity of the maximum-delay constrained jamming channel with continuous-time packet waveforms is shown to equal the mutual information rate of the saddle point. For MDC jammers with discrete-time packet waveforms, saddle-point strategies are shown to exist. Jammers which have quantized batch departures at regular intervals are shown to perform well. Input processes with batches at regular intervals perform well for MDC or maximum-buffer-size-constrained jammers.