Router Utilities

Overview

During simulations, processor models reference the routing tables to send messages through the simulated networks. Building a routing table prior to simulation is more efficient than searching for pathways at runtime, because it finds all the paths once, instead of repetitively.

This ROUTER is based on a breadth-first version of the Dijkstra shortest distance search algorithm. It is efficient, rapid, and general-pupose.

Several heuristical improvements have been incorporated to balance usage of network resources. The ROUTER keeps track of how many paths have used each link. When two otherwise-equivalent pathways are found between PE's, the ROUTER chooses the least used path. This avoids the pathological case of mapping all routes to only one of multiple equidistant paths.

After determining the routing table, the ROUTER produces a usage summary of statistics on how well the paths were balanced. It shows what links, if any, were not used in any path; what links were used by the most paths (potential hot-spots); and the average, peak, and minimum the number of paths using a given link.

For many uses and architectures, the paths found by the automatic router are sufficient without further optimization. However for special cases, the resulting routing table can be manually edited. It is produced in an easy-to-read ASCII format. The ROUTER utility is a convenient starting-point for building optimal routing tables.

Usage

1. Define your architecture in CSIM models and compile the simulation to produce the sim.exe .

   Example:

   • gui arch.sim
     (Enter you topology.)
   • csim arch.sim
     (From GUI: Tools / Build Simulation.)

2. Invoke simulation with -net option.
   (From GUI, this happens automatically as the second part of Tools / Build Simulation above.)

   Example:

   • sim.exe -net
   This produces the netinfo file.

3. Run the ROUTER:
   (From GUI: Tools / Build Routing Table.)

   Example:

   • router netinfo

   This produces the netinfo.rte file containing the routing table.

Port Naming Convention

Figure 1 - Example architecture topology.

Device Name-to-Number Binding

Routing Table File

	ROUTE_TABLE[ source, destination, hop ]

The pathway from each source device to each destination device is listed in the routing table as follows:

	alt  src_dev - dst_dev : x1 x2 x3 x4 x5

The entry can be interpreted as,

	To send a message from src_dev to dst_dev, go through port
	x1, then port x2, ... and finally through port x5.

Advanced Router Aspects

• Multiple alternative paths - Finds multiple paths between each source-destination.
• Variable routing cost - Considers a non-unity routing-cost for each link.

Multiple Path Routing

	router  -alt 5  netinfo

The ROUTER generates a routing table containing four (4) indices, which can be thought of conceptually as the following multi-dimensional array:

	ROUTE_TABLE[ alternate, source, destination, hop ]

The corresponding entry in the routing table for the hops in the given path, from a source, and to a destination is listed in the routing table as:

	alternate  src_dev - dst_dev : x1 x2 x3 x4 x5

• Two paths having 3-link-hops (Path-cost = 3)
• One path having 5-hops (Path-cost = 5)
• Eight paths having 9-hops (Path-cost = 9)

Variable Cost Routing

The link-costs can be specified with the CSIM GUI. The cost is specifiable individually for each direction on each link. If the cost is identical in both directions, you only need to enter one number. If it is non-symmetrical, specify the two costs with a space between them.

The link costs can be used to control the routing-paths chosen. For example, you may wish to avoid a particular link from being used. Then set its routing-cost to infinity (a large number). Conversely, you may not want an intermediate link to be considered as part of the routing-cost. Then set its cost to zero.

Advanced Topics - Customizing Routing Tables

There are various ways to create custom routing tables. One way is to edit the routing-table file directly, since it is editable. However, this is usually very tedious because routing files can be very large. Another way is to write an adhoc program that explicitly writes the routings you wish to use for your architecture. However, we will look at a more automatic method that exploits spoofing the router by editing the netinfo file. This is much more managable than editing the routing-table.

Because the router is a drone that simply finds the shortest way to get from point A to point B in any arbitrary network, there are often convenient and clever ways to trick the router to produce just the routes you want.

For example, in the control/data example above, if you want all control messages to flow over a VME bus, but no application data should flow over the VME bus. Then create two copies of the netinfo file. Call them: netinfo_Control and netinfo_Data. To avoid the data messages from traversing the VME bus, remove the VME bus from the netinfo_Data file and run the ROUTER on it instead of the original netinfo file. Because you have broken the VME path, the router will find alternate pathways through which to route all data-messages.

A convenient way of removing unique keywords is through the grep -v command which returns all lines from a file except those that contain a specified search-string. For example,

	grep -v VME netinfo > netinfo_Data

Likewise, dedicated pathways for the control messages can be forced by cutting any critical links that would otherwise provide shorter paths through links that are to be data-dedicated. Note that not-all the data-dedicated paths need to be cut as long as there is a shorter control-path to get to the same place. The router will simply ignore any paths that are longer.

Reducing Routing-Table Size

Devices that can not be used as a source or destination, may be classified as such, thus reducing the size of the routing file. To classify a device as a non-source, non-destination or as both a non-source and destination, insert one of the following lines in the device behavioral description following the line

	DEFINE_DEVICE_TYPE:     <device_type>
	
	 DEVICE_CLASS=(nosource);
	 DEVICE_CLASS=(nodest);
	 DEVICE_CLASS=(nosrcdst);

Routing Waypoints and Explicit Routes

Command-Line Options

• [second_file] - The second file on the command-line specifies the name and location of the resulting routing table. By default, the routing table has the same root-name as the input netinfo file, but with the .rte extension, (ex. netinfo.rte), unless overrridden by this option.

• -alt - Specifies the number of alternate paths between each source and destination to find distinct routes for. Default = 2.
  Example:   -alt 5

• -n - Specifies the highest routed source or destination device number.
  Example:   -n 200

• -v - Sets the verbosity.
  Example:   -v 10

• -check1 - Causes the Router, -after generating the routing table-, to check every generated route for correctness. This is normally unnecessary, as the Router is a correct-by-construction tool. However, the check is provided as part of the Router's built-in testing capability which helps us validate and maintain the tool. It can be called upon if ever the Router is suspected of making an error, or to be doubly sure of the generated routes.

• -check2 - Causes the Router, -after generating the routing table-, to exhaustively check for missing, or better, paths. For independence, this check uses a totally different, but much slower, routing algorithm method than the Router's primary algorithm. This check is not normally needed, but is provided as part of the Router's built-in testing capability which helps us validate and maintain the tool.

• -check3 - Enables you, the user, to get detailed information about specific paths from the generated routing table after routing is completed, by interactive query. After the routing table is generated, you will be prompted for a source-destination pair. It will then show you, the intermediate nodes and ports for each of the alternative paths. Importantly, this also shows you the so-called invisible devices (devices without numbered ports do not show up in the routing path) and the corresponding unnumbered ports used, along the path. You can continue to ask for other routes or exit as prompted.

• -fullpath - This produces a more explicit routing file with the format being, for example:

           Path 233 586 0: <233 4> <231 3> ... <45 2> 

  The tags in this format are easily parsed by user-scripts. For example, you can search for any route which ran through, say, device <231 and device < 45, and then, perhaps substitute a preferred route-segment for that segment of the route. When invoked, this option prints a message telling you the name of the file it saves the explicit format to, such as netinfo.fullpath.

  Note that the fullpath file is approximately four times (4x) larger than the normal (.rte) routing file, due to the extra tag-characters and device numbers for each hop in the paths.

  The syntax is:

   Path #1 #2 #3: <#4 #5> ...  <#6 #7> 

  Where:

  	#1 = Source device number.
  	#2 = Destination device number.
  	#3 = Alternate path number.
  	#4 = First device in path (same as #1).
  	#5 = First port number in path.
  	... = All the intermediate hops.
  	#6 = Last device hop in path (same as #2).
  	#7 = Last port number in path. 

  Note that path-hops through un-numbered ports of devices, which do not apear in the normal .rte files, will appear in the fullpaths file, but with negative port-numbers. The negative value is a place-holder for indicating an otherwise un-numbered port.

  If you alter the paths in the netinfo.fullpaths file, you can translate the format back to the normal .rte format with the translate_paths.c program.

• -cpc filename - Cross-port routing-cost specification. This option allows consideration of intra-device port-to-port costs to be used from file 'filename' in determininig the best routing paths. Certain port-to-port connections may be inhibited, thus reducing the size of the routing file. For detailed description of its use, see Cross-port routing-cost specification.

• -testbox - Generates full routes for the 'netinfo.rte' file with non-numeric ports specified as negative numbers. A second file called 'portnames' is also generated which shows the mapping between the negative port numbers and the device port names. See Displaying Selected Routing Paths for further information on usage.