Routing Algorithm for Fastest Path – a Queuing Approach

  • Authors

    • Nandhini S
    • Shajitha Begum S
    • Sanjay M S
    2018-10-02
    https://doi.org/10.14419/ijet.v7i4.10.26107
  • Dijkstra’s Algorithm, M/M/1 Queuing model, Optimized shortest path, shortest path algorithms.

  • Finding a fastest route for data packets is a complex process as far as large scale network is considered.  Fastest path helps to minimize the delay, data loss and in turn minimizes the total cost of the network. Dijkstra’s algorithm is one of the most commonly used algorithms for finding the shortest path from one source node to another destination node, which pertains to positive weights only.  In this paper, Dijkstra’s Algorithm combined with the features of single server queuing model is presented to find the fastest route between any two given nodes.  In this improvised algorithm, every edge along with its end vertices is considered as M/M/1 queuing model.  The Waiting time of a packet, number of packets in the system and the probability that the queue length exceeds  packets are considered along with the weight of the particular link, for the calculation of the fastest route. 

     

     

  • References

    1. [1] Artalejo J R, Gomez-Corral, Performance Analysis of a Single-Server Queue with Repeated Attempts, Mathematical and Computer Modelling, 30 (1998), 79-88.

      [2] Haysam Selim , Justin Zhan, Towards Shortest Path Identification on Large Networks, Journal of Big Data, (2016), 3-10.

      [3] Kairanbay Magzhan , Hajar Mat Jani, A Review and Evaluations of Shortest Path Algorithms, International Journal of Scientific & Technology Research, 2, no.6 (2013), 99-104.

      [4] Narsing Deo, Graph Theory with Applications to Engineering and Computer Science (2014), Prentice-Hall, Inc.

      [5] Palaniammal, S, Probability and Queueing Theory (2012), PHI Learning Private Ltd, New Delhi.

      [6] Wang Shu-Xi , The Improved Dijkstra's Shortest Path Algorithm and Its Application, Procedia Engineering , 29, (2012), 1186 – 1190.

      [7] Yong Deng, Yuxin Chen, Yajuan Zhang ,Sankaran Mahadevan, Fuzzy Dijkstra Algorithm for Shortest Path Problem under Uncertain Environment Applied Soft Computing, 12, no.3 (2012) 1231-1237.

  • Downloads

  • How to Cite

    S, N., Begum S, S., & M S, S. (2018). Routing Algorithm for Fastest Path – a Queuing Approach. International Journal of Engineering & Technology, 7(4.10), 753-754. https://doi.org/10.14419/ijet.v7i4.10.26107