A comprehensive information-theoretic study of the capacity of communication channels where information is transmitted via timing is undertaken. Communication channels that lend themselves to this study include: queueing systems, random transit channels, protocol information, covert channels, time-jitter storage channels, intracomputer communications subject to timing uncertainties. The study of the capacity of the above models may be relevant in stochastic discrete-event systems outside the realm of communications. Among the random phenomena that blur timing information, queueing is one of the most important practically and theoretically. Queues are the basic modeling blocks of data communication networks, so finding their Shannon capacity is a problem for which there is ample motivation. Very recent results by Anantharam and Verdu for the single-server queue have shown considerable promise, and the Shannon theoretic study of queueing systems plays a central role in this project. In these problems, information is encoded in the times of arrival of packets to the queueing system (in addition to the contents of those packets), and the receiver observes the times of departure of the packets from the queueing system. The common theme of the foregoing channel models is communication via discrete-events in continuous time. In most of these cases, finding the capacity of those channels is far from elementary because information theoretic challenges such as infinite memory, non-additive noise, feedback, non-standard input constraints, nonlinear input-output dependencies are often present. Source coding problems such as the rate distortion function of the Poisson process and communication via observed Markov processes are also under the purview of this project. In those problems, exponentially distributed times play a central role, for which the rich information theoretic structure of Gaussian problems finds a novel counterpart. The tools required in this study are drawn fr om probability, random processes and optimization; specifically from information theory, queueing theory, Markov processes, and data communication networks.
