Header menu link for other important links
X
A Centrality Entropy Maximization Problem in Shortest Path Routing Networks
, Kamala Krithivasan, Vanniyarajan Chellappan
Published in Elsevier B.V.
2016
Volume: 104
   
Pages: 1 - 15
Abstract
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.
ISSN13891286
Open AccessNo
Concepts (11)
  •  related image
    Entropy
  •  related image
    Graph theory
  •  related image
    Heuristic methods
  •  related image
    Probability distributions
  •  related image
    Topology
  •  related image
    BETWEENNESS CENTRALITY
  •  related image
    OSPF
  •  related image
    Routing
  •  related image
    TOPOLOGY DESIGN
  •  related image
    Traffic engineering
  •  related image
    Inverse problems