Information Theory of Timing Channels

对通过定时传输信息的通信信道的容量进行了全面的信息论研究。适合本研究的通信信道包括：排队系统、随机传输信道、协议信息、隐蔽信道、时间抖动存储信道、受时间不确定性影响的计算机内通信。上述模型的能力研究可能与通信领域以外的随机离散事件系统有关。在模糊时序信息的随机现象中，排队是最重要的理论和实践问题之一。队列是数据通信网络的基本建模模块，因此找到它们的香农容量是一个有充分动机的问题。Anantharam和Verdu最近对单服务器队列的研究结果显示出相当大的前景，而排队系统的香农理论研究在这个项目中起着核心作用。在这些问题中，信息被编码为数据包到达排队系统的时间（除了这些数据包的内容之外），接收方观察数据包离开排队系统的时间。上述信道模型的共同主题是在连续时间内通过离散事件进行通信。在大多数情况下，发现这些通道的容量远不是基本的，因为信息理论的挑战，如无限内存，非加性噪声，反馈，非标准输入约束，非线性输入输出依赖关系往往存在。源编码问题，如泊松过程的率失真函数和通信通过观察马尔可夫过程也在这个项目的范围内。在这些问题中，指数分布的时间起着中心作用，高斯问题的丰富的信息理论结构找到了一个新的对应。本研究所需的工具来自概率、随机过程和优化；特别是从信息论，排队论，马尔可夫过程，和数据通信网络。

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.