Capacity-Approaching Practical Codes for Queueing Channels: An Algebraic, State-Space, Message-Passing Approach

Coleman, Todd P.; Kiyavash, Negar

Permalink

https://hdl.handle.net/2142/99603 Copy

Description

Title

Capacity-Approaching Practical Codes for Queueing Channels: An Algebraic, State-Space, Message-Passing Approach

Author(s)

• Coleman, Todd P.
• Kiyavash, Negar

Issue Date

2007-08

Keyword(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.

Publisher

Coordinated Science Laboratory, University of Illinois at Urbana-Champaign

Series/Report Name or Number

Coordinated Science Laboratory Report no. UILU-ENG-07-2209

Type of Resource

text

Language

en

Permalink

http://hdl.handle.net/2142/99603

Owning Collections