Get all the updates for this publication

Conferences

Distance realization problem in Network Tomography: A heuristic approachPublished in IEEE Computer Society

2013

This paper proposes a heuristic approach for the distance realization problem, which arises in Network Tomography. Network Tomography is the study of estimating internal network structure and link-level performance from end-to-end measurements. A distance realization problem is to reconstruct a graph or topology from its distance matrix, i.e., the matrix containing the pairwise distances between the terminal nodes. The graph, thus realized from the pairwise distances of terminal nodes, can either be a tree or a general graph. There are efficient polynomial algorithms developed for the case of tree realization. However, the problem of finding optimal realization (i.e., the total length of the graph realized is minimum) of distance matrix for a general graph is shown to be NP-hard. Our proposed heuristic approach for distance realization consists of three stages: (i) find a closer tree realizable distance matrix based on the shortest paths, (ii) construct a tree and (iii) fix the differences between the tree realizable distance matrix and the original distance matrix. It also attempts to maximize the 'entropy of betweenness-centrality' measure in the network while satisfying the distance constraints. © 2013 IEEE.

Topics: Distance matrix (72)%72% related to the paper, Resistance distance (64)%64% related to the paper, Distance (64)%64% related to the paper, Adjacency matrix (64)%64% related to the paper and Spatial network (62)%62% related to the paper

View more info for "Distance realization problem in Network Tomography: A heuristic approach"

Content may be subject to copyright.

About the journal

Journal | Data powered by Typeset2013 IEEE International Conference on Advanced Networks and Telecommunications Systems, ANTS 2013 |
---|---|

Publisher | Data powered by TypesetIEEE Computer Society |

Open Access | No |

Concepts (14)

- Forestry
- Heuristic methods
- Topology
- DISTANCE CONSTRAINTS
- DISTANCE REALIZATION
- End-to-end measurement
- LINK-LEVEL PERFORMANCE
- Network tomography
- POLYNOMIAL ALGORITHM
- Realization problems
- TOPOLOGY DISCOVERY
- Trees (mathematics)
- Algorithms
- Problem solving