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.