Publication Date: 2015-Dec-07
The IP.com Prior Art Database
Low-diameter topologies such as the Slim Fly and the Multi-Layer Full-Mesh have been recently proposed as low-cost and low latency alternatives to the popular, higher-cost Fat-Trees. We propose the Sudoku topology class of interconnection networks that has the same cost and latency/diameter benefits, but offers more scalability than these topologies, being able to accommodate as many as twice the number of end points. We describe the structure of these topologies and the construction process, the latter being based on restricting a Fat-Tree's path diversity as much as possible, resulting in increased scale and a cost of only 3 router ports and 2 links per network end-node.
Page 01 of 3
Interconnection networks need to balance several optimization criteria, including cost (typically measured in number of links and switch ports per network endpoint), scale (maximum number
of endpoints supported for a given maximum switch radix and maximum network diameter ), bisection bandwidth (aggregate bandwidth across minimum network bisection), diameter (number of hops in the longest direct path between any pair of end nodes), and path diversity (number of alternative direct or indirect paths between a pair of endpoints).
The topological structure of a network determines the values of these metrics. The user/buyer of a given network generally provides a hard upper-bound requirement on cost and a hard lower bound on scale. Performance-related requirements may put additional bounds on (minimum) bisection bandwidth and (maximum) diameter. With the design space demarcated by these bounds, some freedom may remain to select a specific topology.
Low-diameter networks are generally quite attractive, a low diameter implies few hops between any two points and hence low end-to-end latency. Although there is no immediate relationship between diameter and cost, given two networks with the same bisection bandwidth and the same scale but different diameter, the lower diameter network will generally be less costly, because the product of the bisection bandwidth and the average number of hops should be proportional to the total number of links.
However, the well-known Moore bound imposes a hard limit on maximum network scale for a given switch radix and diameter. Hence, low diameter is a trade-off vs limited scale. Path diversity can also be traded-off against scale; for a given scale and switch radix, a network with higher path diversity will generally provide fewer endpoints.
We propose a topology class that enables construction of networks with diameter two and a scale that is about twice as large as the current state of the art , while providing full bisection bandwidth.
The present invention improves on the two state-of-the art topologies described above by providing a) the same diameter of two, b) the same or better bisection bandwidth, c) and about twice the maximum scale (for a given switch radix).
The core idea of the invention is to exploit the trade-off between (shortest) path diversity and network scale. We sacrifice shortest path diversity in favor of gaining network scale, as compared to e.g. a fat tree network (k-ary n-tree). We provide a novel method for constructing such a network with 2k^3 - 2k^2 + 2k end nodes, using 3k^2 - 3k + 3 switches with radix 2k each. This method encompasses a procedure to create a strictly single-shortest path multi-tree with exactly as many first-level switches as the Moore bound for d=2.
We construct a two-level multi-tree Sudoku network as follows:
1. Select a prime number q.
2. Assign network degree k = q + 1,
3. Assign switch radix r = 2*k.
4. Arrange a total of 3*(1+k(k-1)) r...