What's new: Finding significant differences in network data streams

Graham Cormode; S. Muthukrishnan

doi:10.1109/INFCOM.2004.1354567

What's new: Finding significant differences in network data streams

Graham Cormode, S. Muthukrishnan

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Monitoring and analyzing network traffic usage patterns is vital for managing IP Networks. An important problem is to provide network managers with information about changes in traffic, informing them about "what's new". Specifically, we focus on the challenge of finding significantly large differences in traffic: over time, between interfaces and between routers. We introduce the idea of a deltoid: an item that has a large difference, whether the difference is absolute, relative or variational. We present novel algorithms for finding the most significant deltoids in high speed traffic data, and prove that they use small space, very small time per update, and are guaranteed to find significant deltoids with pre-specified accuracy. In experimental evaluation with real network traffic, our algorithms perform well and recover almost all deltoids. This is the first work to provide solutions capable of working over the data with one pass, at network traffic speeds.

Original language	English (US)
Title of host publication	IEEE INFOCOM 2004 - Conference on Computer Communications - Twenty-Third Annual Joint Conference of the IEEE Computer and Communications Societies
Pages	1534-1545
Number of pages	12
DOIs	https://doi.org/10.1109/INFCOM.2004.1354567
State	Published - 2004
Event	IEEE INFOCOM 2004 - Conference on Computer Communications - Twenty-Third Annual Joint Conference of the IEEE Computer and Communications Societies - Hongkong, China Duration: Mar 7 2004 → Mar 11 2004

Publication series

Name	Proceedings - IEEE INFOCOM
Volume	3
ISSN (Print)	0743-166X

Other

Other	IEEE INFOCOM 2004 - Conference on Computer Communications - Twenty-Third Annual Joint Conference of the IEEE Computer and Communications Societies
Country/Territory	China
City	Hongkong
Period	3/7/04 → 3/11/04

Keywords

Network measurements
Traffic data analysis

ASJC Scopus subject areas

General Computer Science
Electrical and Electronic Engineering

Access to Document

10.1109/INFCOM.2004.1354567

Cite this

What's new: Finding significant differences in network data streams. / Cormode, Graham; Muthukrishnan, S.
IEEE INFOCOM 2004 - Conference on Computer Communications - Twenty-Third Annual Joint Conference of the IEEE Computer and Communications Societies. 2004. p. 1534-1545 (Proceedings - IEEE INFOCOM; Vol. 3).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Cormode, G & Muthukrishnan, S 2004, What's new: Finding significant differences in network data streams. in IEEE INFOCOM 2004 - Conference on Computer Communications - Twenty-Third Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings - IEEE INFOCOM, vol. 3, pp. 1534-1545, IEEE INFOCOM 2004 - Conference on Computer Communications - Twenty-Third Annual Joint Conference of the IEEE Computer and Communications Societies, Hongkong, China, 3/7/04. https://doi.org/10.1109/INFCOM.2004.1354567

@inproceedings{76553561875345fd8dd2e6d6b5652e2f,

title = "What's new: Finding significant differences in network data streams",

abstract = "Monitoring and analyzing network traffic usage patterns is vital for managing IP Networks. An important problem is to provide network managers with information about changes in traffic, informing them about {"}what's new{"}. Specifically, we focus on the challenge of finding significantly large differences in traffic: over time, between interfaces and between routers. We introduce the idea of a deltoid: an item that has a large difference, whether the difference is absolute, relative or variational. We present novel algorithms for finding the most significant deltoids in high speed traffic data, and prove that they use small space, very small time per update, and are guaranteed to find significant deltoids with pre-specified accuracy. In experimental evaluation with real network traffic, our algorithms perform well and recover almost all deltoids. This is the first work to provide solutions capable of working over the data with one pass, at network traffic speeds.",

keywords = "Network measurements, Traffic data analysis",

author = "Graham Cormode and S. Muthukrishnan",

year = "2004",

doi = "10.1109/INFCOM.2004.1354567",

language = "English (US)",

isbn = "0780383559",

series = "Proceedings - IEEE INFOCOM",

pages = "1534--1545",

booktitle = "IEEE INFOCOM 2004 - Conference on Computer Communications - Twenty-Third Annual Joint Conference of the IEEE Computer and Communications Societies",

note = "IEEE INFOCOM 2004 - Conference on Computer Communications - Twenty-Third Annual Joint Conference of the IEEE Computer and Communications Societies ; Conference date: 07-03-2004 Through 11-03-2004",

}

TY - GEN

T1 - What's new

T2 - IEEE INFOCOM 2004 - Conference on Computer Communications - Twenty-Third Annual Joint Conference of the IEEE Computer and Communications Societies

AU - Cormode, Graham

AU - Muthukrishnan, S.

PY - 2004

Y1 - 2004

N2 - Monitoring and analyzing network traffic usage patterns is vital for managing IP Networks. An important problem is to provide network managers with information about changes in traffic, informing them about "what's new". Specifically, we focus on the challenge of finding significantly large differences in traffic: over time, between interfaces and between routers. We introduce the idea of a deltoid: an item that has a large difference, whether the difference is absolute, relative or variational. We present novel algorithms for finding the most significant deltoids in high speed traffic data, and prove that they use small space, very small time per update, and are guaranteed to find significant deltoids with pre-specified accuracy. In experimental evaluation with real network traffic, our algorithms perform well and recover almost all deltoids. This is the first work to provide solutions capable of working over the data with one pass, at network traffic speeds.

AB - Monitoring and analyzing network traffic usage patterns is vital for managing IP Networks. An important problem is to provide network managers with information about changes in traffic, informing them about "what's new". Specifically, we focus on the challenge of finding significantly large differences in traffic: over time, between interfaces and between routers. We introduce the idea of a deltoid: an item that has a large difference, whether the difference is absolute, relative or variational. We present novel algorithms for finding the most significant deltoids in high speed traffic data, and prove that they use small space, very small time per update, and are guaranteed to find significant deltoids with pre-specified accuracy. In experimental evaluation with real network traffic, our algorithms perform well and recover almost all deltoids. This is the first work to provide solutions capable of working over the data with one pass, at network traffic speeds.

KW - Network measurements

KW - Traffic data analysis

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

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

U2 - 10.1109/INFCOM.2004.1354567

DO - 10.1109/INFCOM.2004.1354567

M3 - Conference contribution

AN - SCOPUS:8344272783

SN - 0780383559

T3 - Proceedings - IEEE INFOCOM

SP - 1534

EP - 1545

BT - IEEE INFOCOM 2004 - Conference on Computer Communications - Twenty-Third Annual Joint Conference of the IEEE Computer and Communications Societies

Y2 - 7 March 2004 through 11 March 2004

ER -

What's new: Finding significant differences in network data streams

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this