Header menu link for other important links
X
Distance realization problem in Network Tomography: A heuristic approach
Kamala Krithivasan
Published in IEEE Computer Society
2013
Abstract
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.
About the journal
JournalData powered by Typeset2013 IEEE International Conference on Advanced Networks and Telecommunications Systems, ANTS 2013
PublisherData powered by TypesetIEEE Computer Society
Open AccessNo
Concepts (14)
  •  related image
    Forestry
  •  related image
    Heuristic methods
  •  related image
    Topology
  •  related image
    DISTANCE CONSTRAINTS
  •  related image
    DISTANCE REALIZATION
  •  related image
    End-to-end measurement
  •  related image
    LINK-LEVEL PERFORMANCE
  •  related image
    Network tomography
  •  related image
    POLYNOMIAL ALGORITHM
  •  related image
    Realization problems
  •  related image
    TOPOLOGY DISCOVERY
  •  related image
    Trees (mathematics)
  •  related image
    Algorithms
  •  related image
    Problem solving