Coordinated sampling sans origin-destination identifiers: Algorithms and analysis

Vyas Sekar, Anupam Gupta, Michael K. Reiter, Hui Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Flow monitoring is used for a wide range of network management applications. Many such applications require that the monitoring infrastructure provide high flow coverage and support fine-grained network-wide objectives. Coordinated Sampling (cSamp) is a recent proposal that improves the monitoring capabilities of ISPs to address these demands. In this paper, we address a key deployment impediment for cSamp-like solutions-the need for routers to determine the Origin-Destination (OD) pair of each packet. In practice, however, this information is not available without expensive changes. We present a new framework called cSamp-T, in which each router uses only local information, instead of the OD-pair identifiers. Leveraging results from the theory of maximizing submodular set functions, cSamp-T provides near-ideal performance in maximizing the total flow coverage in the network. Further, with a small amount of targeted upgrades to a few routers, cSamp-T nearly optimally maximizes the minimum fractional coverage across all OD-pairs. We demonstrate these results on a range of real topologies.

Original languageEnglish (US)
Title of host publication2010 2nd International Conference on COMmunication Systems and NETworks, COMSNETS 2010
DOIs
StatePublished - 2010
Event2010 2nd International Conference on COMmunication Systems and NETworks, COMSNETS 2010 - Bangalore, India
Duration: Jan 5 2010Jan 9 2010

Publication series

Name2010 2nd International Conference on COMmunication Systems and NETworks, COMSNETS 2010

Conference

Conference2010 2nd International Conference on COMmunication Systems and NETworks, COMSNETS 2010
Country/TerritoryIndia
CityBangalore
Period1/5/101/9/10

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'Coordinated sampling sans origin-destination identifiers: Algorithms and analysis'. Together they form a unique fingerprint.

Cite this