NDLI: On the Maximum Number of Linearly Independent Cycles and Paths in a Network

Content Provider	IEEE Xplore Digital Library
Author	Gopalan, A. Ramasubramanian, S.
Copyright Year	1993
Abstract	Central to network tomography is the problem of identifiability, the ability to identify internal network characteristics uniquely from end-to-end measurements. This problem is often underconstrained even when internal network characteristics such as link delays are modeled as additive constants. While it is known that the network topology can play a role in determining the extent of identifiability, there is a lack in the fundamental understanding of being able to quantify it for a given network. In this paper, we consider the problem of identifying additive link metrics in an arbitrary undirected network using measurement nodes and establishing paths/cycles between them. For a given placement of measurement nodes, we define and derive the “link rank” of the network-the maximum number of linearly independent cycles/paths that may be established between the measurement nodes. We achieve this in linear time. The link rank helps quantify the exact extent of identifiability in a network. We also develop a quadratic time algorithm to compute a set of cycles/paths that achieves the maximum rank.
Sponsorship	IEEE Computer Society IEEE Communications Society Association for Computing Machinery (ACM)
Starting Page	1373
Ending Page	1388
Page Count	16
File Size	2241459
File Format	PDF
ISSN	10636692
Volume Number	22
Issue Number	5
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2014-01-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Measurement Equations Monitoring Tomography Mathematical model Ear Network topology statistical inverse Additive link metrics end-to-end measurements identifiability independent trees linear independence network monitoring network tomography
Content Type	Text
Resource Type	Article
Subject	Computer Networks and Communications Electrical and Electronic Engineering Computer Science Applications Software

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

On Identifying Additive Link Metrics Using Linearly Independent Cycles and Paths

On the maximum number of linearly independent cycles and paths in a network

On identifying additive link metrics using linearly independent cycles and paths

On the maximum number of linearly independent cycles and paths in a network (2012).

On identifying additive link metrics using linearly independent cycles and paths (2011).

Inferring Link Metrics From End-To-End Path Measurements: Identifiability and Monitor Placement

Identifiability of link metrics based on end-to-end path measurements (2013).

Topological constraints on identifying additive link metrics via end-to-end paths measurements.

Efficient Identification of Additive Link Metrics via Network Tomography

On the Maximum Number of Linearly Independent Cycles and Paths in a Network

Similar Documents

On Identifying Additive Link Metrics Using Linearly Independent Cycles and Paths

On the maximum number of linearly independent cycles and paths in a network

On identifying additive link metrics using linearly independent cycles and paths

On the maximum number of linearly independent cycles and paths in a network (2012).

On identifying additive link metrics using linearly independent cycles and paths (2011).

Inferring Link Metrics From End-To-End Path Measurements: Identifiability and Monitor Placement

Identifiability of link metrics based on end-to-end path measurements (2013).

Topological constraints on identifying additive link metrics via end-to-end paths measurements.

Efficient Identification of Additive Link Metrics via Network Tomography

On the Maximum Number of Linearly Independent Cycles and Paths in a Network