NDLI: Scalpel: scalable preferential link tomography based on graph trimming

Content Provider	ACM Digital Library
Author	Chen, Chun Bu, Jiajun Wu, Wenbin Gao, Yi Li, Xiang-Yang Dong, Wei
Copyright Year	2016
Abstract	Inferring per-link metrics through aggregated path measurements, known as network tomography, is an effective way to facilitate various network operations, such as network monitoring, load balancing, and fault diagnosis. We study the problem of identifying additive link metrics of a set of interesting links from end-to-end cycle-free path measurements among selected monitors, i.e., preferential link tomography. Since assigning a node as a monitor usually requires non-negligible operational cost, we focus on assigning the minimum number of monitors (i.e., optimal monitor assignment) to identify all interesting links. By modeling the network as a connected graph, we propose $\textit{Scalpel},$ a scalable preferential link tomography approach. Scalpel trims the original graph by a two-stage graph trimming algorithm and reuses an existing method to assign monitors in the trimmed graph. We theoretically prove Scalpel has several key properties: 1) the graph trimming algorithm in Scalpel is minimal in the sense that further trimming the graph does not reduce the number of monitors; 2) the obtained assignment is able to identify all interesting links in the original graph; and 3) an optimal monitor assignment in the graph after trimming is also an optimal monitor assignment in the original graph. We implement Scalpel and evaluate it based on both synthetic topologies and real network topologies. Compared with state-of-the-art, Scalpel reduces the number of monitors by 39.0% to 98.6% when 50% to 1% of all links are interesting links.
Starting Page	1392
Ending Page	1403
Page Count	12
File Format	PDF
ISSN	10636692
Volume Number	24
Issue Number	3
Journal	IEEE/ACM Transactions on Networking (TON)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2016-06-01
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Graph trimming Network measurement Preferential link tomography
Content Type	Text
Resource Type	Article
Subject	Electrical and Electronic Engineering Computer Networks and Communications Software Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Scalpel: Scalable Preferential Link Tomography Based on Graph Trimming (2015)

FlowMate: scalable on-line flow clustering

Algebra-based scalable overlay network monitoring: algorithms, evaluation, and applications

NetQuest: a flexible framework for large-scale network measurement

Scalable packet classification

GEMNET: a generalized, shuffle-exchange-based, regular, scalable, modular, multihop, WDM lightwave network

Network loss tomography using striped unicast probes

On Identifying Additive Link Metrics Using Linearly Independent Cycles and Paths

Constructing internet coordinate system based on delay measurement

Scalpel: scalable preferential link tomography based on graph trimming

Similar Documents

Scalpel: Scalable Preferential Link Tomography Based on Graph Trimming (2015)

FlowMate: scalable on-line flow clustering

Algebra-based scalable overlay network monitoring: algorithms, evaluation, and applications

NetQuest: a flexible framework for large-scale network measurement

Scalable packet classification

GEMNET: a generalized, shuffle-exchange-based, regular, scalable, modular, multihop, WDM lightwave network

Network loss tomography using striped unicast probes

On Identifying Additive Link Metrics Using Linearly Independent Cycles and Paths

Constructing internet coordinate system based on delay measurement

Scalpel: scalable preferential link tomography based on graph trimming