Novel shaping and complexity-reduction techniques for approaching capacity over queuing timing channels

Negar Kiyavash, Todd P. Coleman, Mavis Rodrigues

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings - 2009 IEEE International Conference on Communications, ICC 2009
DOIs
StatePublished - Nov 19 2009
Event2009 IEEE International Conference on Communications, ICC 2009 - Dresden, Germany
Duration: Jun 14 2009Jun 18 2009

Publication series

NameIEEE International Conference on Communications
ISSN (Print)0536-1486

Other

Other2009 IEEE International Conference on Communications, ICC 2009
CountryGermany
CityDresden
Period6/14/096/18/09

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Novel shaping and complexity-reduction techniques for approaching capacity over queuing timing channels'. Together they form a unique fingerprint.

Cite this