Network It

Location:

Berkeley, CA

Posted:

November 17, 2012

Contact this candidate

Resume:

System Area Network Mapping

Alan M. Mainwaring Saul Schleimer

Brent N. Chun Daniel S. Wilkerson

Computer Science Division Department of Mathematics

University of California at Berkeley University of California at Berkeley

Berkeley, CA 94720 Berkeley, CA 94720

*****@**.********.*** *******@****.********.***

***@**.********.*** ********@**.********.***

Abstract: This paper presents a network mapping algorithm and The challenge is two-fold: (1) to map networks concurrently with

proves its correctness assuming a traffic-free network. Respecting the execution of applications, and (2) to accomplish this without

well-defined parameters, the algorithm produces a graph isomorphic losing the high-performance communication enabled from direct,

to, where is the network of switches and hosts and is the protected application access to the network hardware. As a step

set of switches connected by a switch-bridge to the set of hosts . towards this goal, we designed a mapping algorithm and proved

We show its performance on a Myrinet system-area network with a its correctness assuming a quiescent network. We implemented

fat-tree-like topology. It can map 36 nodes, 13 switches and 64 links the algorithm in a network of 100 UltraSPARC workstations with

in 248 ms and 100 nodes, 40 switches, and 193 links in 981 ms. From a Myrinet [3] network. The system periodically discovers the net-

such maps, the system computes mutually deadlock-free routes and work topology and uses it to compute and to distribute a set of mu-

distributes them to all network interfaces. Switched, multi-gigabyte tually-deadlock free routes to all network interfaces.

per second, system area networks are the enabling building-blocks

The contributions of this paper are the description of a network

for networks of workstations. Because of their core role, these net-

mapping algorithm that derives a network map from a set of

works should be dynamically reconfigurable, automatically adapt-

probes in sections 2 and 3, empirical performance results and

ing to the addition or removal of hosts, switches and links.

characterizations in a network of interest to us in sections 4 and 5,

1 Introduction and a discussion of open issues and future topics in this area in

sections 6 and 7.

System area networks [1] move switched, low-latency, high-speed

1.1 Myrinet system area networks

networks away from the backplanes and cabinets of massively par-

allel processors into the traditional territory of local area networks. The Berkeley Network of Workstations [4] (NOW) uses Myrinet

These networks commonly use source-based message routing network switches and network interface cards. The network con-

through anonymous switches. In this regime, their topologies may sists of 8-port cross-bar switches that use source-based, oblivious

no longer be the static, well-defined, and well-understood [2] graphs cut-through routing. Messages have a header flit, routing flits, a

such as hypercubes, meshes, etc., and instead may be arbitrary data payload, an 8-bit CRC, and a tail flit. Upon the arrival of a

graphs that change over time. Therefore, systems must periodically message, a switch uses the next routing flit to direct the message

discover their topologies rather than assuming one a priori. Lacking to the specified output port. Switches use relative port addressing,

an out-of-band mechanism for directly querying switches for their i.e., each routing flit specifies an output port using a turn that is

identities, systems must use in-band messaging to disambiguate relative to the input port. Should a message block and wait for an

switch identities when discovering the network topology. From the output port, the rest of the message may remain in the network,

resulting maps, systems can compute mutually deadlock-free routes occupying switch and link resources. Switches automatically de-

without relying upon properties of traditional multicomputer net- tect and break message deadlock in 50 ms. The worse case switch

works, e.g., static topologies, that may now be transient. latency with no output port contention is 550 ns and each link sup-

ports 1.28 Gb/s data rates.

Switches can be connected to other switches or to hosts in an ar-

Alan Mainwaring is supported by a National Semiconductor Corpo- bitrary fashion. The switches use cut-through routing and there

ration graduate research fellowship. Brent Chun is supported by a exists 108 bytes of per-port buffering. At one extreme with these

National Science Foundation graduate research fellowship. Saul switches, a message can form a circuit from the source to destina-

Schleimer is supported by a Department of Mathematics fellowship. tion. At the other, under a heavy load of small messages, the net-

This research is also supported in part by ARPA grant F30602-95- work can behave more like a packet-switched one. As we show,

C-0014, the California State Micro Program, and Professor David cut-through routing through switches with even modest per-port

Culler s NSF Presidential Faculty Fellowship CCR-9253705. Com- buffering complicates the proof of our mapping algorithm.

putational and experimental infrastructure resources are supported in

The Myrinet switch architecture enables low-cost and high-per-

part by NSF Infrastructure Grant CDA-8722788.

formance implementations because of its functional simplicity.

For example, from the above description of message routing, each

switch performs little interpretation for each message. The bene-

fits of the simplicity are obvious - low-cost, low-latency and

high-bandwidth - but the drawbacks are subtle. For example,

Myrinet lacks a mechanism to query a switch directly either with

in- or out-of-band messages to obtain a unique id number for it.

To appear in the proceedings of the 9th Annual Symposium on Parallel Algorithms and Architectures (SPAA 97)

1.2 Mapping the Berkeley NOW the wires of to be bi-directed. We assume that is connected

and has at least one switch and two hosts. Let be its diameter.

One can envision the Berkeley NOW s network as a collection of

2.2 Sending messages

hosts surrounding and attached to its system area network cloud.

The hosts may send special in-band probe messages into this opaque

The network uses cut-through routing through switches with rel-

cloud: some of them detect switches or hosts while others simply

4" ! E 0

ative and non-modularly computed port addressing. The

disappear. By sampling the cloud with enough probe messages, the

5 SW VUS GGG 4S

5 GG@ H I T T

of a message is a string from the alphabet

algorithm derives its topology. The next sections presents an algo-

P A X@ b 46T S W T D ``T

(

. Call the host sending the message . Let be the im-

rithm to do this. This algorithm is trivially correct assuming packet

( aY (

mediately adjacent switch port. Let where the addi-

routing but non-trivial for cut-through and circuit switched routing.

tion is not performed modulo the switch degree . Assume for

I W GG@ X@ FE

`T (

Informally, consider this approach for network mapping with packet PG

the moment that is in, i.e., it is a legal port number.

F $@D7 6

routing. Suppose a designated root host sends enough probe messag- AB

We have now computed one step of the message path from

9T T

Y T

es to generate a tree of all possible paths from it to all hosts directly

TA e D( A b 9T e( @ C 6 6

to, i.e., taken an a1-turn through the switch . In general,

dA S W Df@ C 6

dYd

attached to the network. Where two distinct paths to the same host d( d

let be the neighbor of in, when such a

exist, multiple tree nodes will correspond to the same actual node is neighbor exists. That is, the subsequent characters of the message

the network. The challenge is to identify all such replicated nodes. determine the next turn to take out of a switch relative to the port

Instead of actually generating a tree of all possible paths, the root taken by the path on the way in. There is no means of addressing

host systematically explores the network in a breadth-first-like man- an absolute output port.

ner, increasing the distance (i.e., the number of turns in the route) of T e U C GG CX C@ T C'@D S hR S 31

G@g B (

The sequence is the . When all

each probe message that it sends. When it explores frontier switches,

routing characters are exhausted, the message path terminates at

it may discover two hosts attached to a switch. TeU

the host that receives the message. A routing address fails to

When two graph nodes representing switches are found to be con- define a message path in the graph only in these four cases.

GGGI FE " 8 i"! Y D(

nected to the same host, we know they represent the same physical

! d

ILLEGAL TURN: If, we have made a turn

switch because every host has a single network connection. The two

resulting in an illegal port.

graph nodes can be oriented with respect to each other and merged.

dG S dD(

Normalizing their orientations is necessary because probes may C

NO SUCH WIRE: If has no wire at port

have entered the switch from different directions. When correspond-

HIT A HOST TOO SOON: If a message arrives at a host and

ing switch ports are aligned and the information from one of the

it still contains routing flits, i.e., is a host for some . C

graph nodes is merged into the other, further replicates can be creat-

ed and detected. For example, merging can cause individual switch STRANDED IN NETWORK: If the message path does not

TeU

ports to become connected to multiple nodes. This configuration is end at a host, i.e., is a switch.

impossible because an actual switch port has a single cable connect-

Only one worm may use a given edge at a time. The hardware or

ing it to one other switch port or host. Thus, multiple links incident

firmware destroys messages that attempt illegal paths. If an output

to a switch port identify additional replicates. The exploration and

port is occupied, a worm waits for the port for a period of time set

merging continues until the algorithm has no switches remaining to

is switch ROMs (currently 55 ms) after which the switch forces a

explore and has no replicated nodes waiting to be merged.

special forward reset message out the blocked output port. This

With packet routing, all paths from the root to all hosts are covered. message clears the path in front of it until finding the head of the

Other forms of routing complicate the proof of the algorithm be- blocking worm (the tail is destroyed by hardware).

cause probe messages might deadlock on themselves or prevent us

A worm on a message path which uses the same edge in the same

from fully exploring all output ports of a switch because the probe

direction will block at that edge if its tail has not yet passed that

message itself is occupying some of them. This stepping on one s

edge. The differences here can depend on several hardware fac-

tail phenomena makes mapping non-packet-switched networks a

tors, such as even modest amounts of buffering in switches.

challenging and interesting problem. The set of all probe paths gen-

erated by probing the network with packet routing is a superset of 2.3 Probing to discover network topology

the sets generated with circuit or cut-through routing. For example,

S 1

(

it might be impossible to establish circuits along some of the paths A distinguished host runs a mapper daemon. This pro-

traversed using packet switching. Still, the algorithm can derive gram probes the network and from the responses builds a model

maps given such subsets of all possible probe paths. tree of the actual network . We distinguish between the two

graphs and their components using the terms, model and actual.

4 q4

2 Formal model of the system 2 ! 2

There are two types of probes, a and a

This section presents a system model to facilitate the presentation of SWITCH-PROBE: To test if a switch port is connected to an-

the mapping algorithm and its proof of correctness. The core model other switch, the mapper sends a message with routing flits

4S GGG VUS F VUS GGG 4S

components are hosts, switches, ports, and wires. Then source- encoding turns . If the mapper receives this

based, cut-though routing with relatively-addressed switches, and loopback message, it knows an output port of a switch k-

the types and behaviors of probe messages are defined. hops away is connected to another switch.

HOST-PROBE: To test if a switch port is connected to a host,

2.1 System components

the mapper sends a message with routing flits encoding the

VUS GGG 4S

The consists of two types of nodes:,, and, turns . If the mapper receives a reply from this host to

(disjoint from ). The network is a finite multi-graph on

this message, it knows that this host is connected to an output

% '

. We refer to the edges as . Each end of every wire is labeled port of a switch k-hops away. Hosts are uniquely identified.

43 ) (

2 10 5!

with a, such that no two incident on the same

Let a be a pair of the two above tests, using the above strings

@ 987 6

node share a port number. Denote uniquely a wire-end by its

sr t S 6 VUS GGG 4S

0 Depending on the results, we

based on the same

A (

'ABD4@$C 6

(Bpair, e.g., . A switch has eight allowable port-numbers:

H GG@ H@ FE F

say the probe response is, a unique host-name, or the

PI G

and a host has one port, . In some contexts, we consider

To appear in the proceedings of the 9th Annual Symposium on Parallel Algorithms and Architectures (SPAA 97)

R !

symbol . If the probe finds a host the mapper obtains an cent switch-vertex. Initially, the frontier queue contains exactly

unambiguous name for it, but if it finds a switch, the identity of the this switch-vertex.

switch remains ambiguous.

EXPLORE

Probing computes a mapping from probe strings to responses, which

while( ( frontier.nextElement )

u hh 0

and

we denote R: {-7, -1, +1, +7}* H {

! ,

( .probeString.length SearchDepth ) )

4" !

R }. Any non-null response to a probe is due to the fact that the

ssy ssy x wv !

x sy y w sy

for in

probe path terminated in an actual node (switch or host) . We say

newProbeString v.probeString + !

u u

that the model vertex corresponds to this actual node . This is a

whatKind R(newProbeString)

well-defined correspondence function, from model vertices to actual

if ( whatKind nothing )

nodes.

.neighbors[i] new edgeAndVertex

(newProbeString, whatKind, )

2.3.1 Two models of probe failures

add new vertex to frontier

Note that even when the probe path exists in the network there may endif

be no response, due to possible worm collisions or other errors, e.g., endfor

message corruption. Worm collisions are the major complication in endwhile

the proof of correctness (Recall the assumption that the network is

MERGE

quiescent during mapping and thus worms can only deadlock on

themselves.) Depending upon hardware considerations, the follow- repeat

boolean anyDeductions? false

ing two models may apply: (1) messages are circuit routed and

9 @ T u

$ f9 ) $ s T u

therefore host-probes reusing edges in the same direction fail and gu

sgu

For all pairs of vertices such that

switch-probes reusing an edge in either direction fail because they ssy x7wv !

x sy

For each port number in

must return, or (2) messages are cut-through routed and therefore

sTu

if ( neighbors[ ].label .neighbors[ ].label)

T !u

probes reusing an edge may or may not fail. Other errors such as

9u !

mergeLabels( .neighbors[ ], .neighbors[ ], i)

message corruption are not addressed in the model.

anyDeductions? true

3 The Mapping Algorithm endif

endfor

This section presents a simplified version of the mapping algorithm.

endfor

In Section 3.2 we prove it correct. In Section 3.3 we apply a series

until( anyDeductions? = true )

of modifications and demonstrate the correctness after each change.

PRUNE

The mapper host sends probes of increasing length into the actual

network, exploring it in a BFS-like manner. The inability to identify repeat

switches means the exploration is not actually a BFS because probes

boolean anyDeleted? false

revisit nodes from different directions. For each non-null response

VUS GGG 4ST u

For each vertex

to a probe, the algorithm builds a new model vertex v in the

if ( ( .kind = switch ) ( degree(v) = 1 ) )

p p

model graph . The resulting tree is a subtree of the natural tree

.delete

on the probe string space.

anyDeleted? true

Because the model graph in general contains replicates of actual net-

endif

work nodes, the algorithm must detect them in order to produce an

endfor

accurate copy of the network. For example, two model vertices are

until( anyDeleted? = false )

recognized as replicates if they purport to be connected to the same

host. This is because each host is connected to a single switch by a

3.1.1 Data structures

single link (by system construction). In essence, this describes the

first step of Lemma 3 below.

The pseudo-code object representing a vertex in has the fol-

lowing fields. Vertices have labels to indicate if they have been

Merging information from the two vertex objects may result in some

determined to be replicates. They also record adjacent neighbors.

switch ports claiming to be connected to multiple other switches or

hosts. This identifies more replicates, and Section 3.2 and especially US GGG 4S

probeString - records the successful probe string

that

Section 3.2.6 show that this deductive process ultimately identifies

lead to the creation of .

all replicates. Identity information from separate regions of the mod-

kind - records the type of node, h

or . The re-

el graph propagates and enables the identification of more replicates.

R ! p

sponse " " never creates a vertex in .

As a proof technique, after deducing that two vertices are replicates

label - when a host-vertex is created, its label is set to the

our simplified algorithm labels them the same, as opposed to merg-

A VUS GGG 4S

host-name, which is the probe string response, .

ing the objects themselves. Subsequent modifications in Section 3.3

When a switch-vertex is created, it gets a fresh label.

change labeling into merging while preserving correctness.

T 4 hR ! G T u

neighbors - an array of edge objects. We say 2

3.1 Algorithm pseudo-code

g u " ! 4 hR ! u

2 G

connects to if the edge object at has and

After presenting the pseudo code, subsequent subsections cover de- 9u

g as its endpoints. Initially an edge s index in this array is the

tails of the core data structures, operations upon them, and algorith- turn that discovered it, which we call the relative port number.

mic parameters.

edge is an object containing a reference to the vertex at each end

INITIALIZATION of it, and the associated indices (relative port numbers) pointing

back to it in these two adjacent vertices. The constructor

D " Dh4" % 4 g e h$R 5

The model graph is initialized with two vertices: the root host-

Au@5 ! @ R 2 f 6 d5 creates an edge object

B D

vertex,, corresponding to the actual mapper host,, and its adja-

connected to in the obvious way and to a new vertex object

To appear in the proceedings of the 9th Annual Symposium on Parallel Algorithms and Architectures (SPAA 97)

a " a h4SR " % i g S a " % iS

5 ! @ 2 f R 2

created with fields bridge as a bridge separating a collection of switches not connect

5 " k " hi2 h ma a ( " j

! 65!

or (given by ), and if to any hosts on one side with a reasonable network on the other

l "

is a host-name) or a fresh label (if "). side.)

At all times, two vertices with the same label correspond to the same 3.2 Proof of correctness

" h42 S nh R 31

actual node in, and the routine maintains this proper-

The following is a sketch of the proof. First we show that each

ty. It is discussed in detail in Section 3.1.2. Hu

node in is represented at least once in . It suffices to show

frontier is a FIFO queue is used in the standard manner of a BFS that all replicates are merged, guaranteeing that each node is rep-

search to hold created but unexplored vertices. resented at most once. Replicates will be merged if they have

parallel paths (corresponding to the same actual path in ) to

SearchDepth limits probe string lengths (see Section 3.1.4. for a spe-

replicate host-vertices. With packet routing, these parallel paths

cific value).

always exist and we will see that this finishes the proof.

3.1.2 The mergeLabels operation

With circuit routing however, the parallel paths are not guaran-

" h42 S nh R 31

We describe the procedure without giving pseudo- teed to exist, and this is the major complication of the proof. Spe-

( pu u

code. This procedure merges the labels of two vertices, and re-in- cifically consider a path from in to a host-vertex h. Let

u u

dexes their neighbors arrays. We show below in Lemma 2 that this be a replicate of . If we can start at and go along the path par-

( ( u

procedure will give only replicate vertices the same label, and allel to, sort of pasting on to, we should arrive at (a

changes the indices to have equal indexing offsets (defined below). replicate of ). We cannot assume that this succeeds because the

implied probe path may step on its tail.

" h42 S nh R 31 Tu

takes as input two vertices and that are labeled the

g9u T u ! !

same, and an index . Initially, and, through relative port, con- The existence of this collision however guarantees the existence

T0 X0 o

S p p

nect to on port and on port, respectively. For every in of other side-paths to in . because we have found more copies

" h 42 n h R 31 X0

with the same label as, changes s label to that of of, we have more information to work with. It will take an in-

S nh R 301

. The indexing of s neighbors array is shifted by . Finally, ductive examination of these side-paths to see that these replicates

" h42

fixes the relative port numbers in all of the affected are discovered.

edge objects.

The case of cut-through routing is similar. Some probes may suc-

ceed where previously they failed due to self-deadlock. This gives

3.1.3 Indexing offset of the neighbors array

us a possibly larger than above. Assuming additionally that

When two replicate vertices are encountered during merging (be- is empty, we ensure that these extra replicates are found.

low), we would like to match up their neighbors. This is non-trivial

3.2.1 Conventions and definitions

because the indexing of the neighbors array of is an artifact of the

u ipp

relative turns of the probe path to . Suppose that in is connect-

u We formalize notions of correspondence, parallel an

Contact this candidate