Reliable and efficient routing protocol for graph theory based communication topology

In this paper, we propose the Aggressive Multi-path Aware (AMA) routing protocol. The AMA routing protocol is designed to demonstrate routing feasibility in the resized Borel Cayley Graphs (BCGs) and Expanded Borel Cayley Graphs (Ex-BCGs) formulated by the Cut-Through Rewiring (CTR) algorithm. The AMA routing protocol focuses on resolving the single shortest path and multi-paths depletion problems of the Vertex-Transitive (VT) and Class-level Vertex-Transitive (CVT) routing protocols when BCGs and Ex-BCGs are resized. The AMA routing protocol updates the routing table to reflect topology changes with a small network overhead. Based on the updated routing table, the AMA routing protocol delivers data with the Multi-path Aware routing and the Random Direction routing schemes. The multi-path aware routing exploits all available multi-paths with prioritized selection from the updated routing table. The random direction routing supplements the multi-path aware routing failure by relaying the packet to randomly selected neighbor. From simulation, we observe that the AMA routing protocol has reliable reachability and efficient average routing path length along the removed node ratios. Furthermore, we identify that the AMA routing protocol achieves almost identical reachabilities independent of the networks generated by different parameters. For extensive evaluation with traffic patterns, we show the potential of the AMA routing protocol for network applications with reasonable reachability, End-to-End delay and dropped packets analysis.