Solution file (simple ASCII) for SNDlib



This page describes the ASCII file format for the solution file. See the format overview page for a description of the other input and output files.

Summary

A solution for a particular combination of a network model and a network instance is specified by a

Link configurations

The section LINK_CONFIGURATIONS has the following format:

      LINK-CONFIGURATIONS-keyword (
         LINK-configuration-line*
      )
   
   
LINK-CONFIGURATIONS-keyword
The keyword LINK_CONFIGURATIONS.
LINK-configuration-line
For each link, the complete configuration is specified by a line of the following format:

      link-id  ( module-count-pair* )

      
link_id
The identifier of the link.
( module-count-pair* )
A list of pairs where each pair consists of the module capacity and a number specifying how many times it is installed on this link (including preinstalled capacity). If the ROUTING-MODEL is CONTINUOUS, this value may be fractional, otherwise it should be integer.
Example
A line of the section LINK_CONFIGURATIONS in the output file may have the following appearance:

      LinkAB  ( 63 3 )

      
This describes that a capacity of 3 times 63 is installed on the link LinkAB.


Routing

The section ROUTING consists of exactly one routing section for each considered network state, each of these in the following format:

      ROUTING-keyword state (
         ROUTING-demand-section*
      )

      
ROUTING-keyword
The keyword ROUTING.
state
Either NOS for the normal operating state where nothing fails, or the name of a failing link to indicate a single link failure state, or DEFAULT_BACKUP (see below).
ROUTING-demand-section
The complete routing of a single demand in a given network state is specified by exactly one section of the following format:

      demand_id ( 
         PATH-line+
      )

      
demand_id
The identifier of the demand.
PATH-line
Each path used to route some part of the current demand is specified by a line of the following format:

      path_flow_value ( link_id+ )

      
path_flow_value
The amount of flow routed by this path, given in terms of the routing unit for this demand. That is, if the routing unit is 63 (VC-4) and three VC-4 containers are routed on a path, this value should be 3. In failure states, only the rerouted flow value is given here.
link_id+
The non-empty, whitespace-separated list of identifiers of the links used by this path.
In failure states, a complete routing including non-failing working paths must be given for all affected demands, i.e., the total flow given in this ROUTING-demand-section must be at least the demand value.
Example
The following example describes a complete routing with working and backup paths for two demands:

         ROUTINGS NOS (
            D_AC (
               14 ( L_AC )
               36 ( L_AB L_BC )
            )
            D_AB (
               4  ( L_AB )
            )
         )

         ROUTINGS L_AC (
            D_AC (
               40 ( L_AB L_BC )
               10 ( L_AD L_DC )
            )
         )

         ROUTINGS L_AB (
            D_AC (
               50 ( L_AC )
            )
            D_AB (
               4 ( L_AC L_BC )
            )
         )

         ROUTINGS L_BC (
            D_AC (
               50 ( L_AC )
            )
         )
      
In this example, the flow for demand D_AC (from node A to node C) is split on two paths. The first part of value 14 is routed on a path consisting of the single link L_AC. The second part of value 36 is routed on the path consisting of the links L_AB and L_BC. In the network state where link L_AC fails, 4 units of the failing flow are shifted to the already used path (L_AB L_BC), whereas the other 10 units are rerouted on the new backup path (L_AD L_DC) Note that for all demands affected by a failure, the complete routing must be given in the failure routing, i.e., including non-failing working paths.
Simplified notation for 1+1 protection
With 1+1 protection, every demand has exactly one working path and one backup path which is independent of the considered failure state. To simplify the notation in this case, the keyword DEFAULT_BACKUP indicates that the given backup routing is to be used in any failure state affecting the working path routing of the demand. Thus, instead of the cumbersome notation

         ROUTINGS NOS (
            D_AB (
               42 ( L_AC L_CD L_BD )
            )
         )

         ROUTINGS L_AC (
            D_AB (
               42 ( L_AB )
            )
         )

         ROUTINGS L_CD (
            D_AB (
               42 ( L_AB )
            )
         )

         ROUTINGS L_BD (
            D_AB (
               42 ( L_AB )
            )
         )
      
you can simply write

         ROUTINGS NOS (
            D_AB (
               42 ( L_AC L_CD L_BD )
            )
         )

         ROUTINGS DEFAULT_BACKUP (
            D_AB (
               42 ( L_AB )
            )
         )
      
meaning that the backup path (L_AB) is to be used in any failure state where the working path fails.



© 2006 Zuse-Institute Berlin (ZIB)
http://www.zib.de