Information Theory of Timing Channels

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

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.