Inverse shortest path algorithm for weighted graphs

Inverse shortest path algorithm for weighted graphs: Flow-based resource management for path networks

Darsi, Sai Poojitha (TU Delft Electrical Engineering, Mathematics and Computer Science)

Van Mieghem, P.F.A. (mentor)
Noldus, R.A.C.J. (mentor)
Feld, S. (graduation committee)

Delft University of Technology

2021-07-22

With the proliferating networks, resource allocation based on Quality of Service (QoS) constraints mapping has been one of the difficulties faced by Internet Service Providers (ISP). The advent of new technologies such as virtualization and cloud computing have enabled the users to access content from anywhere around the world. This results in a need for an efficient and fast resource allocation method based on demand acting on the network. Many researchers have developed various algorithms to address this issue. However, they have considered only flow-based network properties, while the contemporary networks communicate mostly through path-based communication using the shortest paths. Inverse shortest path algorithm (ISPA) is a graph-theory based heuristic developed to solve this network resource allocation problem which considers both flow-based communication properties through Effective resistance matrix and path-based communication properties through shortest path matrix. Nevertheless, ISPA is so far implemented only for unweighted graphs. This study aims at assessing the feasibility of ISPA for weighted graphs by understanding the nature of Inverse shortest path problem (ISPP) bounds in weighted random graphs and implementing ISPA for weighted graphs. ISPP bounds behaviour is studied for weighted graphs by analyses of Q-norm distributions, probability of failure distributions and hopcount distributions. A feasibility condition verifying ISPP bounds is derived in relation with the input parameters of the weighted random graph. The solutions obtained through hop count distribution analysis are observed to be Poissonian in nature. Finally, ISPA is implemented for weighted graphs such that demand matrix can be resolved into a simple distance matrix to obtain solution which is a non-negative weighted Adjacency matrix and feasibility conditions are verified for the solutions obtained through ISPA.

Resource allocation
inverse shortest path problem
shortest path computations

http://resolver.tudelft.nl/uuid:44e2cc2b-5ea8-49f0-aa15-6d05b287327d

2022-07-22

Student theses

master thesis

© 2021 Sai Poojitha Darsi