System area network mapping
Brent N. Chun, Alan M. Mainwaring, Saul Schleimer, Daniel Shawcross Wilkerson · 1997
This paper presents a network mapping algorithm and proves its correctness assuming a traffic-free network.Respecting well-defined parameters, the algorithm produces a graph isomorphic to N -F, where N is the network of switches and hosts and F is the set of switches connected by a switch-bridge to the set of hosts I-I.We show its performance on a Myrinet system-area network with a fat-tree-like topology.It can map 36 nodes, 13 switches and 64 links in 248 ms and 100 nodes, 40 switches, and 193 linksin981 rns.From such maps, the system computes mutually deadlock-free routes and distributes them to all network interfaces.Switched, multi-gigabyte per second, system area networks are the enabling building-blocks for networks of workstations.Because of their core role, these networks should be dynamically recontigurable, automatically adapting to the addition or removal of hosts, switches and links. IntroductionSystem area networks [1] move switched, low-latency, high-speed networks away from the backplanes and cabinets of massively parallel processors into the traditional territory of local area networks.These networks commonly use source-based message routing through anonymous switches.In this regime, their topologies may no longer be the static, well-defined, and well-understood [2] graphs such as hypercubes, meshes.etc., and instead may be arbitrary graphs that change over time.Therefore, systems must periodically discover their topologies rather than assuming one a priori.Lacking an out-of-band mechanism for directly querying switches for their identities, systems must use in-band messaging to disambiguate switch identities when discovering the network topology.From the resulting maps, systems can compute mutually deadlock-free routes without relying upon properties of traditional multicomputer networks, e.g., static topologies, that may now be transient.