Fishing in Poisson streams: focusing on the whales, ignoring the minnows
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...
Main Authors: | , , , |
---|---|
Format: | Report |
Language: | unknown |
Published: |
arXiv
2010
|
Subjects: | |
Online Access: | https://dx.doi.org/10.48550/arxiv.1003.2836 https://arxiv.org/abs/1003.2836 |
id |
ftdatacite:10.48550/arxiv.1003.2836 |
---|---|
record_format |
openpolar |
spelling |
ftdatacite:10.48550/arxiv.1003.2836 2023-05-15T18:32:37+02:00 Fishing in Poisson streams: focusing on the whales, ignoring the minnows Raginsky, Maxim Jafarpour, Sina Willett, Rebecca Calderbank, Robert 2010 https://dx.doi.org/10.48550/arxiv.1003.2836 https://arxiv.org/abs/1003.2836 unknown arXiv arXiv.org perpetual, non-exclusive license http://arxiv.org/licenses/nonexclusive-distrib/1.0/ Information Theory cs.IT FOS Computer and information sciences Preprint Article article CreativeWork 2010 ftdatacite https://doi.org/10.48550/arxiv.1003.2836 2022-04-01T14:50:31Z 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. : 6 pages, 6 pdf figures; invited paper to appear in CISS 2010 Report The Minnows DataCite Metadata Store (German National Library of Science and Technology) Minnows ENVELOPE(-65.359,-65.359,-66.027,-66.027) The Minnows ENVELOPE(-65.359,-65.359,-66.027,-66.027) |
institution |
Open Polar |
collection |
DataCite Metadata Store (German National Library of Science and Technology) |
op_collection_id |
ftdatacite |
language |
unknown |
topic |
Information Theory cs.IT FOS Computer and information sciences |
spellingShingle |
Information Theory cs.IT FOS Computer and information sciences Raginsky, Maxim Jafarpour, Sina Willett, Rebecca Calderbank, Robert Fishing in Poisson streams: focusing on the whales, ignoring the minnows |
topic_facet |
Information Theory cs.IT FOS Computer and information sciences |
description |
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. : 6 pages, 6 pdf figures; invited paper to appear in CISS 2010 |
format |
Report |
author |
Raginsky, Maxim Jafarpour, Sina Willett, Rebecca Calderbank, Robert |
author_facet |
Raginsky, Maxim Jafarpour, Sina Willett, Rebecca Calderbank, Robert |
author_sort |
Raginsky, Maxim |
title |
Fishing in Poisson streams: focusing on the whales, ignoring the minnows |
title_short |
Fishing in Poisson streams: focusing on the whales, ignoring the minnows |
title_full |
Fishing in Poisson streams: focusing on the whales, ignoring the minnows |
title_fullStr |
Fishing in Poisson streams: focusing on the whales, ignoring the minnows |
title_full_unstemmed |
Fishing in Poisson streams: focusing on the whales, ignoring the minnows |
title_sort |
fishing in poisson streams: focusing on the whales, ignoring the minnows |
publisher |
arXiv |
publishDate |
2010 |
url |
https://dx.doi.org/10.48550/arxiv.1003.2836 https://arxiv.org/abs/1003.2836 |
long_lat |
ENVELOPE(-65.359,-65.359,-66.027,-66.027) ENVELOPE(-65.359,-65.359,-66.027,-66.027) |
geographic |
Minnows The Minnows |
geographic_facet |
Minnows The Minnows |
genre |
The Minnows |
genre_facet |
The Minnows |
op_rights |
arXiv.org perpetual, non-exclusive license http://arxiv.org/licenses/nonexclusive-distrib/1.0/ |
op_doi |
https://doi.org/10.48550/arxiv.1003.2836 |
_version_ |
1766216824163139584 |