Network input file (simple ASCII) for SNDlib

• Nodes The nodes section specifies all (potential) nodes together with their locations and options.
• Links The links section describes all (potential) connections between nodes.
• Demands The demand section specifies all communication requirements which have to be satisfied by a feasible routing and flow allocation.
• Admissible paths This (optional) path section specifies a list of admissible paths for each demand.

NODES section

      NODES-keyword (
        NODE-line*
      )

      

NODES-keyword

The literal word NODES in uppercase letters is the section identifier.

NODE-line

Each node of the network is specified by exactly one line of the following format:

         node_id ( x-coordinate y-coordinate ) ( node_design_ids ) ( node_options )

         

node_id

The identifier of the node. The identifier node_id must be unique within the section NODES.

x-coordinate

The x-coordinate of the node. If you specify geographical coordinates, this is the geographical longitude in (-180,180], where locations west of Greenwich have negative x-coordinates.

y-coordinate

The y-coordinate of the node. If you specify geographical coordinates, this is the geographical latitude in [-90,90], where locations south of the equator have negative y-coordinates.

node_design_ids

In Version 2.0 of SNDlib, the hardware installable at a node location will be described in this section. It is optional now but should be empty if present.

node_options

In Version 2.0 of SNDlib, there may be optional node parameters which location will be described in this section. It is optional now but should be empty if present.

Example

A line of the section NODES in the network design file may have the following appearance:

         Berlin ( 13.4 52.5 ) () ()

         

This defines a node Berlin which is located at the geographical position 13.4 E / 52.5 N.

Note that the coordinates are only used for visualization purposes. When specifying geographical coordinates, make sure to give them in degrees and fractions of degrees instead of degrees and minutes, otherwise the nodes will be in slightly wrong positions in the generated pictures.

LINKS section

         LINKS-keyword (
            LINK-line*
         )

         

LINKS-keyword

The literal word LINKS in uppercase letters is the section identifier.

LINK-line

Each link of the network is specified by exactly one line of the following format:

      link_id  \
      ( source_id  target_id ) \
      preinstalled_cap  
      preinstalled_cost  \
      routing_cost  \
      setup_cost  \
      ( capacity_cost_list )  \
      ( link_options )
      

(broken up into several lines here for readability).

link_id

The identifier of the link. The link_id must be unique within the section LINKS.

( source_id target_id )

The identifiers of the two end-nodes of the link. source_id and target_id must be different and have to be specified in the NODES section.
Whether links are directed, bidirected or undirected depends on the LINK_MODEL specified in the network model file. Parallel links between the same node pair are allowed.

preinstalled_cap

Pre-installed capacity installed on this link, which can be used for expansion planning problems or for allocation problems. If no capacity is pre-installed, 0 has to be used. A link with preinstalled capacity C > 0 has to be included in any feasible solution, and capacity C is provided on that link at cost preinstalled_cost. Additional capacity may be installed on that link as specified in the capacity_cost_list for that link.

preinstalled_cost

Cost associated with the pre-installed capacity. Note that this is a constant term included in the cost of every feasible solution, which is only included for the sake of completeness to get the total network cost in expansion planning problems.

routing_cost

Cost incurred by each unit of flow using the link (w.r.t. routing_unit 1, see the demand section).

setup_cost

Fixed cost incurred for including this link in the final solution topology. In particular, if a link has preinstalled capacity, its setup cost must be added to the total network cost.

capacity_cost_list

This is a whitespace-separated list of capacity-cost-pairs: ( cap1 cost1 cap2 cost2 ... ) specifying the capacities which can be installed on the link (in addition to pre-installed capacity). The cost value is the cost of one capacity unit, i.e., n units of cap2 incur a cost of n * cost2. The interpretation of the capacities (whether multiples are allowed or not) depends on the link capacity model specified in the network model file. If no capacity is installable (in addition to preinstalled capacity), no value need to be specified, but parentheses have to be present. For pure fixed-charge problems, i.e., a link has either no or unlimited capacity, the list (UNLIMITED 0) should be used and setup cost should be set accordingly.

( link options )

This is a future-use list for link options in later versions of SNDlib. It is optional now but should be empty if present.

Example

A line of the section LINKS in the network design file may have the following appearance:

         L_AB ( A B ) 63 100 10 1000 ( 63 1000 252 1200 ) ()

         

For the purpose of the explanation, assume that unit 1 corresponds to 2 Mbit/s. Then the above line defines the link L_AB between nodes A and B. Capacity 63 (STM-1) is preinstalled at cost 100. A cost of 1 is incurred for each flow unit using this link. In addition to the preinstalled capacity, modules of capacity 63 (STM-1) and modules of capacity 252 (STM-4) are installable at cost 1000 and 1200 per module, respectively. With an EXPLICIT link capacity model, at most one of these additional modules may be chosen, whereas with a MODULAR link capacity model, several of these modules may be installed.

Another line of the section LINKS may have the following appearance:

         LinkCD ( NodeC NodeD ) 0 0 0 2000 ( UNLIMITED 0 ) ()

         

This defines the link LinkCD between NodeC and NodeD, with no preinstalled capacity, with no routing cost, with a setup cost of 2000, and no capacity-dependent cost. This corresponds to a fixed-charge problem where an unlimited capacity is available on that link at cost 2000, and the only question is whether to use the link or not.

DEMANDS section

            DEMANDS-keyword (
              DEMAND-line*
            )

      

DEMANDS-keyword

The literal word DEMANDS in uppercase letters is the section identifier.

DEMAND-line

Each communication demand is specified by exactly one line of the following format:

         demand_id  ( source_id  target_id )  routing_unit  \
         demand_value  max_path_length  ( demand_options )

      

(broken up into several lines here for readability).

demand_id

The unique identifier of this demand.

( source_id target_id )

The identifiers of the two end-nodes of this demand. source_id and target_id must be different and have to be specified in the section NODES. Whether the demands are directed or undirected depends on the DEMAND_MODEL specified in the network model file.

routing_unit

The individual routing unit of this demand. With an integer ROUTING_MODEL, each demand must be routed in integer units of its routing unit, i.e., in a bifurcated for this demand, the flow on each path of the routing must be an integer multiple of the routing unit. Furthermore, with an integer routing, for each demand routed over a given link, the link must have enough capacity provided by modules whose capacity is at least the routing unit of each demand. If all your demands have the same granularity, simply set all routing units to 1.

demand_value

This parameter value is interpreted for a specific demand such that at least routing_unit times demand_value many units must be routed through the network during normal operation (where all network components are active).

max_path_length

The maximum number of links allowed in any routing path for this demand during normal operation. The keyword UNLIMITED specifies that no path length restrictions need to be considered.

( demand_options )

This is a future-use list for link options in later versions of SNDlib. It is optional now but should be empty if present.

Example

A demand line in the network design file may have the following appearance:

            D_AC ( A C )  1 50 UNLIMITED ()
            D_AB ( A B ) 63  2 10        ()

         

These lines define two communication demands D_AC and D_AB between the nodes A and C and between A and B, respectively. For the purpose of the explanation, assume again that unit 1 corresponds to 2 Mbit/s. Then 50 flow units (routing unit 1) must be routed for demand D_AC, and 2x63 flow units (corresponding to two VC-4 containers) have to be routed for demand D_AB. With an INTEGER routing model, every routing path for the latter demand must carry either flow 63 or flow 126 (corresponding to one or two VC-4 containers). Routing paths for demand D_AC have no length restriction, whereas routing paths for demand D_AB must contain at most 10 links.

ADMISSIBLE_PATHS section

         ADMISSIBLE_PATHS-keyword (
            DEMAND-PATHS*
         )

      

ADMISSIBLE_PATHS-keyword

The keyword ADMISSIBLE_PATHS.

DEMAND-PATHS

The admissible paths for a particular demand are specified by exactly one section of the following format:

  
         demand_id ( 
            PATH-line+
         )

      

demand_id

The identifier of the demand.

PATH-line

Each path potentially used to route some part of the demand is specified by a line of the following format:

         path_id ( link_id+ )

      

path_id

A unique identifier for the path.

link_id+

The links used by this path. These links must establish a path from the source to the target node of the demand and satisfy the hop restrictions for the demand.

Example

An example (incomplete since not all demands are covered) of the section ADMISSIBLE_PATHS may have the following appearance:

         ADMISSIBLE_PATHS (
              D_AC ( L_AB L_BC )
         )

      

In this example, only one path is specified for the demand D_AC from node A to node C which consists of the links L_AB and L_BC.