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 -