48.6 Network Layout

In nam, a topology is specified by alternating node objects with edge objects. But to display the topology in a comprehensible way, a layout mechanism is needed. Currently nam provides three layout methods. First, user may specify layout by the link's orientation. A link orientation is the angle between the edge and a horizontal line, in the interval [0, 2$\pi$]. During layout, nam will honor the given link orientation. Generally, it will first choose a reference node, then place other nodes using link orientations and link length. The link length is determined by link delay and connecting node sizes. This works well for small and manually generated topologies.

Second, when dealing with randomly generated topologies, we may want to do layout automatically. An automatic graph layout algorithm has been adapted and implemented. The basic idea of the algorithm is to model the graph as balls (nodes) connected by springs (links). Balls will repulse each other, while springs pull them together. This system will (hopefully) converge after some number of iterations. In practice, after a small number of iterations (tens or hundreds), most small to medium sized graphs will converge to a visually comprehensible structure. Larger graphs may take a combination of automatic layout and hand placement to achieve an acceptable layout.

There are 3 parameters to tune the automatic layout process: Ca Attractive force constant, which controls springs's force between balls. Cr Repulsive force constant, which controls the repulsive force between balls. Number of iterations How many times to run the autolayout procedure.

For small topologies with tens of nodes, using the default parameters (perhaps with 20 to 30 more iterations) will suffice to produce a nice layout. But for larger topology, careful parameter tuning is necessary. Following is a empirical method to layout a 100 node random transit stub topologygenerated by Georgia Tech's ITM internet topology modeler. First, set Ca and Cr to 0.2, do about 30 iterations, then set Cr to 1.0, Ca to about 0.01, then do about 10 iterations, then set Ca to 0.5, Cr to 1.0, do about 6 iterations.

Third, there is a x,y coordinate style layout. This was developed for use in displaying a wireless topologies in which permanent links don't exist. Using this style, nodes events are given x and y coordinate values indicating where those nodes should be placed in a cartesian world.