An Efficient Compact Routing Scheme for Interconnection Topologies based on the Random Model
Chung Kieu Thanh, Anh Dinh The, Cuong Van Bui, Hai Duc Pham, Khanh-Van Nguyen · 2017
The field of interconnection network has recently observed a resurgent interest that are fueled by modern ICT technologies wherein traditional topologies have been found less desirable. The recent approach using the random network model has been considered a good answer to new challenges but also has a limitation in routing scalability, i.e. the routing table size (RTS) can become very large which is not affordable by market commodity switches. We propose to design new routing schemes especially designed for the random network model that can improve this situation. As a major contribution, we propose a new compact routing scheme named by CORRA which exploits the random model properties that help to achieve near optimum route length while keeps the routing table size small enough. In general, our new routing algorithm can achieve average route length only a bit longer than in using the shortest path routing. The RTS achieved by CORRA is very small as expected, e.g. 520 for network size 8192, which is small enough to allow network size even up to millions of nodes.