Header menu link for other important links
A Centrality Entropy Maximization Problem in Shortest Path Routing Networks
, Kamala Krithivasan, Vanniyarajan Chellappan
Published in Elsevier B.V.
Volume: 104
Pages: 1 - 15
In the context of an IP network, this paper investigates an interesting case of the inverse shortest path problem using the concept of network centrality. For a given network, a special probability distribution, namely the centrality distribution associated with the links of a network can be determined based on the number of the shortest paths passing through each link. An entropy measure for this distribution is defined, and the inverse shortest path problem is formulated in terms of maximizing this entropy. We then obtain a centrality distribution that is as broadly distributed as possible subject to the topology constraints. A maximum entropy distribution signifies the decentralization of the network. An appropriate change in the weight of a link alters the number of the shortest paths that pass through it, thereby modifying the centrality distribution. The idea is to obtain a centrality distribution that maximizes the entropy. This problem is shown to be NP-hard, and a heuristic approach is proposed. An application to handling link failure scenarios in Open Shortest Path First routing is discussed. © 2016 Elsevier B.V. All rights reserved.
About the journal
JournalData powered by TypesetComputer Networks
PublisherData powered by TypesetElsevier B.V.
Open AccessNo
Concepts (11)
  •  related image
  •  related image
    Graph theory
  •  related image
    Heuristic methods
  •  related image
    Probability distributions
  •  related image
  •  related image
  •  related image
  •  related image
  •  related image
  •  related image
    Traffic engineering
  •  related image
    Inverse problems