Files in this item



application/pdfUILU-ENG-07-2209 assembled.pdf (186kB)
(no description provided)PDF


Title:Capacity-Approaching Practical Codes for Queueing Channels: An Algebraic, State-Space, Message-Passing Approach
Author(s):Coleman, Todd P.; Kiyavash, Negar
Subject(s):Queueing theory
Information theory
Message-passing algorithms
Algebraic codes
State-space models
Abstract:This report introduces a coding theory for queueing channels and discusses a practical capacity-approaching scheme. Here we consider a communication channel where the encoder communicates information based upon timings between successive packets. A receiver observes packet timings after they have traveled through a communication network with queues at intermediate router nodes. Based upon the encoding mechanism, the statistical structure of the network queues, and the packet timings it observes, the receiver finds the most likely bit sequence. Despite queueing system being nonlinear, non-stationary, and non-memoryless, Verdu and Anantharam provided a closed-form theoretical characterization of the maximum amount of information (i.e. capacity, in bits per second) that can be reliably communicated across a queue in their Information Theory Society Best Paper Award-Winning manuscript “Bits Through Queues”. However, to date, there has been a lack of practical ways to realize these theoretical possibilities. Indeed, the authors themselves claimed in 1998 that ‘Coding theory for queueing channels is virtually nonexistent.’ Here we introduce an architecture - based on algebraic codes, a state-space perspective on queues, and iterative message-passing on graphs – that is capacity-approaching and has low decoding complexity. To the best of the authors' knowledge, this is the first known such scheme.
Issue Date:2007-08
Publisher:Coordinated Science Laboratory, University of Illinois at Urbana-Champaign
Series/Report:Coordinated Science Laboratory Report no. UILU-ENG-07-2209
Genre:Technical Report
Date Available in IDEALS:2018-04-04

This item appears in the following Collection(s)

Item Statistics