Documentation to "calculation of minimum spanning tree and shortest path tree" MST_SPT

Disclaimer:

This software is (c) 2000 by the LKN - Lehrstuhl fuer Kommunikationsnetze at TU Muenchen (www.lkn.e-technik.tu-muenchen.de).
Software coding and documentation by Daniel Roegelein (daro@roegelein.net).
Idea to the project by Dipl.-Ing. Anton Riedl of LKN (anton.riedl@ei.tum.de).
Any suggestions are appreciated.

System requirements of this version

MLS_SPT runs on i386-systems with a VGA compatible graphics adapter under DOS 5.0 up to Windows 2000/XP.
This documentation is written accordingly to version 1.00.

Download

You may download the software for Windows here.

Overview on the software

This software is designed to provide a possibility to supervise the minimum spanning tree (MST) and shortest path tree (SPT) algorithms calculating their respective trees based on a topology read from user-defined files.
In two separate windows the user can watch the calculation process with different algorithms and root nodes simultaneously.
During calculation the trees form up successively with the most recently attached links being marked in a blue and yellow shape so they can be distinguished well from those formerly included.
Using the shortest path tree method, also a traceroute can be performed on attached nodes to view the calculated routes destined for them.

The graphical user interface

MLS_SPT runs in full-screen vga mode (640x480). Within the GUI the user can interact with the software simply by using the mouse (or the keyboard for some basic functions).
All important elements are described below.




Globals
	With LOAD a predefined toplogy can be loaded from a file that has to be conform to the structure described later on. Template graphs "large.map" and "small.map" are delivered with the software. EXIT (or hitting ESC) quits the program.
	With these three buttons referred to as play, pause and stop the calculation process can be initiated, paused, stopped and reset. The current status is represented by an highlighted (blue) button. From status stop the user can initiate the calculation by pressing play or hitting the space bar on the keyboard, reset the calculated trees by pressing stop again. From status play the user can pause the process by pressing pause or hitting the space bar, stop the process by pressing stop. From status paused the user can resume the process by pressing play or hitting the space bar, stop the process by pressing stop. You didn't expect all of this for sure...
	This scroll bar enables the user to set the preferred speed of the calulation process. For changing the speed the bar has to be dragged with the mouse to any desired point. With the bar being set between the left and right margins, delay time can be set from some ms to one second between each calculation step. Having the bar set at the very right (SLOW) results into the program changing to paused status after each calculation step, and having it set at the very left (FAST) will suppress any grapical output of intermediate calculation steps.
	The border separating the two windows can be moved to any desired point using the mouse.
Window specific
	Every window graphically represents its tree's current calculation status. Concerning nodes, gray means unattached, green means attached to the tree and red shows the node being the root node. Concerning links, gray means unused link, yellow used link and yellow/blue represents the most recently attached link.
	With these two buttons the user can choose the algorithm being used for a certain window. MST means minimum spanning tree and SPT means shortest path tree.
	Within this window the user can choose the root node. Changing it can either be done using the arrow buttons or by picking a specific node using the mouse whilst ROOT button is being "pressed". The screen output shows the name of the root node as supplied in the NAME statement of the input file and an internal number which ranges from 1 to the max. number of nodes. Should any data be too long for the text fileds the string will be cut and extended by "..". Changing the root node causes a reset of the calculated tree. The upper picture illustrates the layout whilst in MST-mode. In the lower picture (which is for SPT-mode) the user can perform a traceroute to any attached node (completed calculation required) by clicking TRACERT. As long as the mouse cursor is located over a linked node, its route will be highlighted.
	The LENGTH window shows the actual length (or cost) of the calculated tree and will be updated at every calculation step.

Required file format

To use this software a topology has to be read from a plain-text ascii file. The global structure of this file is as following:

1.) Node part: descriptions of all nodes with their names and x/y-coordinates
2.) Link part: descriptions of all links with start node and end node name

1.) Node part: node definition example, all statements mandatory and case sensitive



BEGINNODE NAME NODE_1 X_COORD 1 Y_COORD 1 ENDNODE BEGINNODE NAME NODE_2 X_COORD 2 Y_COORD 1 ENDNODE

Annotation: NAME is the node's name X_COORD is the x-coordinate (0..65534) Y_COORD is the y-coordinate (0..65534)


2.) Link part: link definition example, all statements mandatory and case sensitive

Please remark that all links are considered bi-directional!



BEGINLINK SRC NODE_1 DEST NODE_2 LENGTH 44 ENDLINK

Annotation: SRC is the name of the link's source node DEST is the name of the link's destination node LENGTH is the length (or cost) of the link (0..65534)

Appendix: Short description of used algorithms

1.) The minimum spanning tree algorithm

The MST algorithm is used to calculate a tree that links every node of a given topology while having the minimum possible overall length.
Initially the whole tree is reset (all links and nodes unattached) and the root node is added to the tree, i.e. becomes marked as attached.
In every subsequent step, all unattached nodes are regarded that can be reached via links to formerly attached nodes. (In case of the first subsequent step these are all nodes that can be reached from the root node).
Of all those reachable nodes the one with the minimum link length (to his "uplink", not the root node) is then attached to the tree.
With a certain topology the calculation allways results into the same tree independet of the chosen root node. The minimum spanning tree is therefor called deterministic.

2.) The shortest path tree algorithm (according to the Dijkstra table method)

Different to the MST method the intention of SPT is to find the shortest link to the root node for every node.
For calculation it is required to memorize every node's uplink node which is considered the next hop in direction of the root node.
Furthermore the actual link length from every node (over his uplink and so on..) to the root node has to be saved in a table.
After an initial reset (all links and nodes unattached, uplink-tables emptied and all nodes' link lengths set to infinite (unreachable)) the root node is attached to the tree.
In every following calculation step, all nodes are regarded that can be reached via formerly attached nodes, their length to the root via these uplinks is calculated, saved to the link length table and the one with minimum length to the root node is then attached to the tree (please mind the difference to MST in this point of choice).
Right before the next calculation step, every unattached node has to be controlled as following:
If the node was unreachable right up to now (infinite length to root node) it has to be checked whether a new possibility has occured to eventually link it by having attached the "cheapest" node before and should this be the case the uplink and link length tables have to be updated.
If the node was allready considered reachable (entries in uplink node and link length tables) it has to be checked whether the node could be reached "cheaper" by the recent attachement and in that case the forementioned tables have to be updated.

Enjoy!