## The Zero-Rate Error Exponent of the Exponential-Server Timing Channel

Aaron Wagner

(Professor Venkat Anantharam)

(DARPA) F30602-00-2-0538, (DARPA) N66001-00-C-8062, NSF Graduate Research Fellowship, (NSF) SBR-9873086, and (ONR) N00014-1-0637

The exponential-server timing channel (ESTC) is one in which the sender
chooses times at which identical jobs are submitted to a single-server
queue with an exponential service time distribution, while the
receiver observes their departure times. Our interest in this channel
is due to its canonical nature and the central role it plays in the
study of covert timing channels, in which the sender sends messages
containing irrelevant or misleading information, and actually
communicates with the receiver using the timing of the messages,
unknown to a casual observer.

Previous work has established the Shannon capacity of the channel [1],
and the random-coding and sphere-packing bounds on its reliability
function [2]. The bounds prove that the reliability function is at
least as large as the reliability function of the well-known Poisson
channel [3,4], and that the two reliability functions coincide at rates
close to their common capacity. We have proved that at sufficiently low
rates, the reliability function of the ESTC lies strictly above the
Poisson
channel's, answering in the negative the open question of whether the two
reliability functions coincide at all rates [2]. Our results reveal a
distance metric between codewords for the ESTC that parallels Hamming
distance for the binary symmetric channel and Euclidean distance for the
Gaussian channel. We are currently attempting to determine the zero-rate
error exponent of the ESTC exactly.

- [1]
- V. Anantharam and S. Verdú, "Bits through Queues,"
*IEEE Trans.
Information Theory,* Vol. 42, No. 1, January 1996.
- [2]
- E. Arikan, "On the Reliability Exponent of the Exponential Timing
Channel,"
*IEEE Trans. Information Theory,* Vol. 48, No. 6, June 2002.
- [3]
- A. D. Wyner, "Capacity and Error Exponent for the Direct Detection Photon
Channel Part I,"
*IEEE Trans. Information Theory,* Vol. 34, No. 6,
November 1988.
- [4]
- A. D. Wyner, "Capacity and Error Exponent for the Direct Detection Photon
Channel Part II,"
*IEEE Trans. Information Theory,* Vol. 34, No. 6,
November 1988.

Send mail to the author : (awagner@eecs.berkeley.edu)

Edit this abstract