A memoryless channel coding methodology for infinite-memory queuing timing channels

The exponential server timing channel - the simplest queuing timing channel - is non-stationary and has infinite memory. Thus, developing error-correcting codes for such channels is challenging. Previously, Coleman and Kiyavash developed a class of coding techniques that are reliable in limited scenarios, but have undesirable complexity-performance tradeoffs. This paper utilizes a recent result by Coleman on developing an achievability theorem based upon how the channel is memoryless conditioned upon intermediate queue states. In this paper, we use this property, along with the fact that the distribution of a Poisson process conditioned upon the number of counts at time T is a uniform distribution on the unordered time epochs on [0,T]. Our approach uses a sparse graph coding technique over finite fields of large alphabets. Unlike the previous coding scheme, all intermediate messages of the decoder are of a fixed alphabet and the graphical representation is equivalent to a sparse graph for decoding on memoryless channels. Simulation results demonstrate the effectiveness of this approach.