TY - GEN

T1 - Counter braids

T2 - 46th Annual Allerton Conference on Communication, Control, and Computing

AU - Lu, Yi

AU - Montanari, Andrea

AU - Prabhakar, Balaji

PY - 2008

Y1 - 2008

N2 - A novel counter architecture, called Counter Braids, has recently been proposed for per-flow counting on high-speed links. Counter Braids has a layered structure and compresses the flow sizes as it counts. It has been shown that with a Maximum Likelihood (ML) decoding algorithm, the number of bits needed to store the size of a flow matches the entropy lower bound. As ML decoding is too complex to implement, an efficient message passing decoding algorithm has been proposed for practical purposes. The layers of Counter Braids are decoded sequentially, from the most significant to the least significant bits. In each layer, the message passing decoder solves a sparse signal recovery problem. In this paper we analyze the threshold dimensionality reduction rate (d-rate) of the message passing algorithm, and prove that it is correctly predicted by density evolution. Given a signal in ℝ n + with n∈ non-vanishing entries, we prove that one layer of Counter Braids can reduce its dimensionality by a factor 2.08 ∈log (1/∈) + O(∈). This essentially matches the rate for sparse signal recovery via L 1 minimization, while keeping the overall complexity linear in n.

AB - A novel counter architecture, called Counter Braids, has recently been proposed for per-flow counting on high-speed links. Counter Braids has a layered structure and compresses the flow sizes as it counts. It has been shown that with a Maximum Likelihood (ML) decoding algorithm, the number of bits needed to store the size of a flow matches the entropy lower bound. As ML decoding is too complex to implement, an efficient message passing decoding algorithm has been proposed for practical purposes. The layers of Counter Braids are decoded sequentially, from the most significant to the least significant bits. In each layer, the message passing decoder solves a sparse signal recovery problem. In this paper we analyze the threshold dimensionality reduction rate (d-rate) of the message passing algorithm, and prove that it is correctly predicted by density evolution. Given a signal in ℝ n + with n∈ non-vanishing entries, we prove that one layer of Counter Braids can reduce its dimensionality by a factor 2.08 ∈log (1/∈) + O(∈). This essentially matches the rate for sparse signal recovery via L 1 minimization, while keeping the overall complexity linear in n.

UR - http://www.scopus.com/inward/record.url?scp=64549111742&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=64549111742&partnerID=8YFLogxK

U2 - 10.1109/ALLERTON.2008.4797558

DO - 10.1109/ALLERTON.2008.4797558

M3 - Conference contribution

AN - SCOPUS:64549111742

SN - 9781424429264

T3 - 46th Annual Allerton Conference on Communication, Control, and Computing

SP - 209

EP - 216

BT - 46th Annual Allerton Conference on Communication, Control, and Computing

Y2 - 24 September 2008 through 26 September 2008

ER -