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