This paper presents an algorithm to automatically design two-level fat-tree networks, such as ones widely used in large-scale data centres and cluster supercomputers. The two levels may each use a different type of switches from design database to achieve an optimal network structure. Links between layers can run in bundles to simplify cabling. Several sample network designs are examined and their technical and economic characteristics are discussed. The characteristic feature of our approach is that real life equipment prices and values of technical characteristics are used. This allows to select an optimal combination of hardware to build the network (including semi-populated configurations of modular switches) and accurately estimate the cost of this network. We also show how technical characteristics of the network can be derived from its per-port metrics and suggest heuristics for equipment placement. The algorithm is useful as a part of a bigger design procedure that selects optimal hardware of cluster supercomputer as a whole. Therefore the article is focused on the use of fat-trees for high-performance computing, although the results are valid for any type of data centres.
Gupta and Dally @cite_0 suggested a tool to optimize network topology, in the broad class of hybrid Clos-torus networks. Cost, packaging and performance constraints can be specified. This tool is most valuable for building custom interconnection solutions when arbitrary topologies are feasible, contrary to the case of using commodity switches where most parameters are fixed but optimization can take actual prices into account.
@cite_0
1983242583 2127380142 2163392581 2104060777
This paper describes an automatic optimization tool that searches a family of network topologies to select the topology that best achieves a specified set of design goals while satisfying specified packaging constraints. Our tool uses a model of signaling technology that relates bandwidth, cost and distance of links. This model captures the distance-dependent bandwidth of modern high-speed electrical links and the cost differential between electrical and optical links. Using our optimization tool, we explore the design space of hybrid Clos-torus (C-T) networks. For a representative set of packaging constraints we determine the optimal hybrid C-T topology to minimize cost and the optimal C-T topology to minimize latency for various packet lengths. We then use the tool to measure the sensitivity of the optimal topology to several important packaging constraints such as pin count and critical distance. Aggregate traffic loads and topology in multihop wireless networks may vary slowly, permitting MAC protocols to "learn" how to spatially coordinate and adapt contention patterns. Such an approach could reduce contention, leading to better throughput. To that end, we propose a family of MAC scheduling algorithms and demonstrate general conditions, which, if satisfied, ensure lattice rate optimality (i.e., achieving any rate-point on a uniform discrete lattice within the throughput region). This general framework enables the design of MAC protocols that meet various objectives and conditions. In this paper, as instances of such a lattice-rate-optimal family, we propose distributed, synchronous contention-based scheduling algorithms that: 1) are lattice-rate-optimal under both the signal-to-interference-plus-noise ratio (SINR)-based and graph-based interference models; 2) do not require node location information; and 3) only require three-stage RTS CTS message exchanges for contention signaling. Thus, the protocols are amenable to simple implementation and may be robust to network dynamics such as topology and load changes. Finally, we propose a heuristic, which also belongs to the proposed lattice-rate-optimal family of protocols and achieves faster convergence, leading to a better transient throughput. Interconnection networks based on the k-ary n-tree topology are widely used in high-performance parallel computers. However, this topology is expensive and complex to build. In this paper we evaluate an alternative tree-like topology that is cheaper in terms of cost and complexity because it uses fewer switches and links. This alternative topology leaves unused upward ports on switches, which can be rearranged to be used as downward ports. The increase of locality might be efficiently exploited by applications. We test the performance of these thin-trees, and compare it with that of regular trees. Evaluation is carried out using a collection of synthetic traffic patterns that emulate the behavior of scientific applications and functions within message passing libraries, not only in terms of sources and destinations of messages, but also considering the causal relationships among them. We also propose a methodology to perform cost and performance analysis of different networks. Our main conclusion is that, for the set of studied workloads, the performance drop in thin-trees is less noticeable than the cost savings. This paper studies a multi-facility network synthesis problem, called the Two-level Network Design (TLND) problem, that arises in the topological design of hierarchical communication, transportation, and electric power distribution networks. We are given an undirected network containing two types of nodes---primary and secondary---and fixed costs for installing either a primary or a secondary facility on each edge. Primary nodes require higher grade interconnections than secondary nodes, using the more expensive primary facilities. The TLND problem seeks a minimum cost connected design that spans all the nodes, and connects primary nodes via edges containing primary facilities; the design can use either primary or secondary edges to connect the secondary nodes. The TLND problem generalizes the well-known Steiner network problem and the hierarchical network design problem. In this paper, we study the relationship between alternative model formulations for this problem (e.g., directed and undirected models), and analyze the worst-case performance for a composite TLND heuristic based upon solving embedded subproblems (e.g., minimum spanning tree and either Steiner tree or shortest path subproblems). When the ratio of primary to secondary costs is the same for all edges and when we solve the embedded subproblems optimally, the worst-case performance ratio of the composite TLND heuristic is 4 3. This result applies to the hierarchical network design problem with constant primary-to-secondary cost ratio since its subproblems are shortest path and minimum spanning tree problems. For more general situations, we express the TLND heuristic worst-case ratio in terms of the performance of any heuristic used to solve the embedded Steiner tree subproblem. A companion paper develops and tests a dual ascent procedure that generates tight upper and lower bounds on the optimal value of a multi-level extension of this problem.