Efficient Landmark-Based Compact Routing for Random Interconnection Topologies
Chi-Hieu Nguyen, Chung T. Kieu, Khanh Van Nguyen · 2019
We revisit the well-known research topic of landmark-based compact routing in order to support designing interconnection topologies that can meet new demanding requirements and issues brought up by advances in areas such as massively parallel computing or large-scale data centers. Particularly, it is necessary to reduce the routing table size (RTS) as much as possible while maintaining other performance factors in a good state. Based on a new landmark selection technique, we propose our Geographic Landmark-based Compact Routing scheme which can reduce the RTS from the well-known Thorup and Zwick's scheme by roughly 15% for a network of 1024 nodes and roughly 45% for a network of at least 100K nodes, and which also produces shorter avcrago path length.