دانلود رایگان مقاله مساله حداکثرسازی مرکزیت آنتروپی در کوتاه ترین مسیر شبکه مسیریابی

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.

9. Conclusions

The paper presents a new way of measuring the centralization of the network based on the entropy of the shortest path betweenness centrality distribution. We opine that this measurement makes a strong case for considering betweenness centrality distribution and its entropy in designing maximally efficient topologies, and improving the resiliency and quality of routing. The tactical network only serves as a use-case model; however, the idea is applicable to other networks too. The CEM framework can be extended to other centrality measures such as Routing Betweenness centrality to solve inverse shortest path problems in the areas of Traffic Engineering and Routing optimization. Additionally, there is a class of multi-layer topology design problems that can synthesize the optimal topology at both physical and logical layers, that can be analyzed using this framework. It will be worthwhile to build a routing strategy that can automatically detect the occurrence of Braess’ paradox in the network based on the entropy of centrality distribution.