Improved Compact Routing Schemes for Random Interconnects

Introduction

The traditional research field of interconnection networks has recently enjoyed a refreshed, strong wave of interest which is motivated by high and new demands from modern ICT technologies related to the areas of massively parallel computing, computing grids, and large-scale data centers. Typically, traditional interconnect topologies have been found less efficient in applications where latency is sensitive, such as massively parallel computing, or found awkwardly inappropriate to cope with incremental expansion¹ that is often required in modern data centers. Thus, researchers are actively investigating new approaches and methods for designing modern interconnects which can solve these emerging issues. A fruitful fresh approach is to use random network models (including small-world models) to provide desired performance qualities such as significant communication latency improvement in high performance computers or to provide incremental expansion. Regarding the first case, the proposed network construction model can produce a significantly shorter graph diameter and hence shorter communication latency comparing to that in traditional topologies (with the same size and same degree). Regarding the second case, the precious property of incremental expansion can be achieved naturally with the random network model, which also offers high bandwidth and hence, makes itself a very appealing design model to data center networks.

In these new interconnect proposals, a typical network setting is a random structure, in which a regular “base” graph is augmented with or extended with a number of random links generated by some specific distribution. Such a “base” graph can often be as simple as a 2-D grid, while the random links can usually be uniformly distributed and added to the nodes rather evenly. However, the approach based on the random network model has to deal with an important issue regarding the limitation in routing scalability. The use of random links which can be added flexibly, possibly between any given two nodes, makes the shortest path routing built on Dijkstra’s algorithm a distinctively popular choice for routing conduct in a network. Nevertheless, the implementation of shortest path routing requires each node to form a large routing table, consisting of entries of all possible routes to every other node, with size . Clearly, this shortcoming becomes significant if the network size is substantially large – of hundreds of thousands computing nodes – due to memory limits in the switches².

Obviously, in order to find the shortest paths in our random network model, one has to use the network global topology, i.e. to afford large routing tables. However, if one adjusts its priority i.e. finding short paths instead of the shortest ones and accepts lower optimization for communication latency, one may only need routing tables of significantly smaller size.

The important and well-established research topic of compact routing is to study how to design schemes that achieve efficient trade-offs among the three performance factors: route stretch³, routing table size (RTS) and routing state (i.e. size of the header of the forwarded packet). Prime general results in this area have been established about 15-20 years before, which are mainly based on the landmark-based approach. The main idea of this landmark-based approach is to find a set of representing nodes, i.e. landmarks that can be thought of as popular locations in a geographic map, of which the positions are globally informed to other nodes as a guidance for the forwarding of a packet during the initial setting of the network. In that sense, a packet that is originated from a source node and is aimed for a destination node can be forwarded to - the landmark closest to - and then from there to . Cowen (Cowen, 2001) proposed a routing algorithm based on using landmarks that achieves stretch-3 with in RTS. Moreover, Thorup and Zwick have improved on the landmark selection technique to achieve stretch-3 with only in RTS (Thorup & Zwick, 2001). These results can be seen as the best in this field for general graphs; however, improvements can still be sought for certain specific network models.