Novel Shaping and Complexity-Reduction Techniques for Approaching Capacity over Queuing Timing Channels

This paper discusses practical codes for communication via packet timings across network queuing systems - an instantiation of the "Bits Through Queues" result for timing channels. It has recently been shown that sparse-graph linear codes followed by shaping techniques, combined with message-passing decoding, can enable practical timing channel codes with low symbol error rates near the capacity. The previous work had two main drawbacks. First, the shaping technique was only effective for very large finite field sizes. Secondly, the complexity of the message-passing decoder was quadratic in the block length. In this work, 1) we develop an alternative shaping technique using random dithers with provably good statistical guarantees; 2) we exploit Little\´s Law from queuing theory along with a large deviations argument to reduce the message-passing decoder\´s complexity from quadratic to linear in block length. We illustrate the effectiveness of this approach on simulated queuing systems with low symbol error rates near the capacity.