Skip to main content

Fishing in poisson streams: Focusing on the whales, ignoring the minnows

Publication ,  Journal Article
Raginsky, M; Jafarpour, S; Willett, R; Calderbank, R
Published in: 2010 44th Annual Conference on Information Sciences and Systems, CISS 2010
June 24, 2010

This paper describes a low-complexity approach for reconstructing average packet arrival rates and instantaneous packet counts at a router in a communication network, where the arrivals of packets in each flow follow a Poisson process. Assuming that the rate vector of this Poisson process is sparse or approximately sparse, the goal is to maintain a compressed summary of the process sample paths using a small number of counters, such that at any time it is possible to reconstruct both the total number of packets in each flow and the underlying rate vector. We show that these tasks can be accomplished efficiently and accurately using compressed sensing with expander graphs. In particular, the compressive counts are a linear transformation of the underlying counting process by the adjacency matrix of an unbalanced expander. Such a matrix is binary and sparse, which allows for efficient incrementing when new packets arrive. We describe, analyze, and compare two methods that can be used to estimate both the current vector of total packet counts and the underlying vector of arrival rates. ©2010 IEEE.

Duke Scholars

Published In

2010 44th Annual Conference on Information Sciences and Systems, CISS 2010

DOI

Publication Date

June 24, 2010
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Raginsky, M., Jafarpour, S., Willett, R., & Calderbank, R. (2010). Fishing in poisson streams: Focusing on the whales, ignoring the minnows. 2010 44th Annual Conference on Information Sciences and Systems, CISS 2010. https://doi.org/10.1109/CISS.2010.5464841
Raginsky, M., S. Jafarpour, R. Willett, and R. Calderbank. “Fishing in poisson streams: Focusing on the whales, ignoring the minnows.” 2010 44th Annual Conference on Information Sciences and Systems, CISS 2010, June 24, 2010. https://doi.org/10.1109/CISS.2010.5464841.
Raginsky M, Jafarpour S, Willett R, Calderbank R. Fishing in poisson streams: Focusing on the whales, ignoring the minnows. 2010 44th Annual Conference on Information Sciences and Systems, CISS 2010. 2010 Jun 24;
Raginsky, M., et al. “Fishing in poisson streams: Focusing on the whales, ignoring the minnows.” 2010 44th Annual Conference on Information Sciences and Systems, CISS 2010, June 2010. Scopus, doi:10.1109/CISS.2010.5464841.
Raginsky M, Jafarpour S, Willett R, Calderbank R. Fishing in poisson streams: Focusing on the whales, ignoring the minnows. 2010 44th Annual Conference on Information Sciences and Systems, CISS 2010. 2010 Jun 24;

Published In

2010 44th Annual Conference on Information Sciences and Systems, CISS 2010

DOI

Publication Date

June 24, 2010