Loading...

Secure overlay routing for large scale networks

Gharib, M ; Sharif University of Technology | 2018

603 Viewed
  1. Type of Document: Article
  2. DOI: 10.1109/TNSE.2018.2812830
  3. Publisher: IEEE Computer Society , 2018
  4. Abstract:
  5. Probabilistic key pre-distribution schemes have recently emerged as major tools of addressing secure routing challenge in wireless networks. In our previous work, we propose an algorithm capable of finding optimal secure paths in overlay wireless networks. An important concern related to that algorithm is the scalability of the solution for large scale networks containing thousands of nodes. In this paper, we propose two alternative solutions for the previously formulated problem of secure overlay routing that can effectively scale to thousands of nodes. The first one is a deterministic Dijkstra-based algorithm analytically proven to find the optimal path with a time complexity much lower than that of the original algorithm. The second alternative is an approximation method capable of finding a near optimal path with an accuracy of $99%$ compared to the optimal path. At the cost of a space complexity in the order $O(n log^3n)$, this algorithm can find the near optimal path with a linear time complexity compared to quadratic or multiplicative time complexity associated with the first algorithm proposed in this paper. Experimental results using a number of different key pre-distribution schemes confirm our analytical findings. IEEE
  6. Keywords:
  7. Dijkstra Algorithm ; Large Scale Networks ; Optimal Secure Routing ; Probabilistic Key Pre-distribution ; Time complexity ; Approximation algorithms ; Complex networks ; Cryptography ; Heuristic algorithms ; Network routing ; Optimization ; Probability distributions ; Wireless networks ; Dijkstra algorithms ; Key pre-distribution ; Large-scale network ; Routing ; Secure routing ; Time complexity ; Network security
  8. Source: IEEE Transactions on Network Science and Engineering ; 2018 ; 23274697 (ISSN)
  9. URL: https://ieeexplore.ieee.org/document/8307079