Overview of Input Data for Mesh Restoration
Mesh restoration refers to a family of problems related to the allocation of spare bandwidth in a "service" network (composed of nodes and edges) so that for each of a set of pre-defined failures (each defined by a set of spans in the underlying "physical" network), any circuits routed through a span affected by the failure can be rerouted on remaining spans. The choice of problems as well as the respective models reflect current products and technologies deployed in telecommunication networks, but innovations will continue. For this reason, the network input file format allows for richer models than those described in the literature.
The essential data needed to describe the network are:
- Study (study name, description, type, optional parameters)
- Objective Function (name, expression)
- Nodes (node id, node name, optional parameters)
- Spans (span id, From node id, To node id, length, optional parameters)
- Edges (edge id, From node id, To node id, list of span ids, optional parameters)
- Demands (From node id, To node id, Num, Modularity, optional parameters)
- Failure Scenarios - one of the following: single_span, single_node, dual_span, custom
- Restoration Method - one of the following: fip, fip1, fip11, fdp, fdp1, fdp11, fie, fie1, fie11, fde, fde1, fde11.
where fip = "fault-independent path ", fip1 = "fault-independent single path", fip11 = "fault-independent single shortest path", fdp = "fault-dependent path", fie = "fault-independent edge", fde = "fault-dependent edge."
Parameters may include either input attributes and constraints, or attributes calculated from other attributes or network design results. By convention, node, demand, span, and edge ids are prefixed by 'n', 'd', 's', and 'e', respectively, and the appropriate letter will be added to any nonconforming id.
The problem qualifiers (q records) describe the type of mesh restoration problem. First, we distinguish between link, subpath, and path mesh restoration. With link mesh restoration, the endpoints of links affected by a failure perform the restoration switching. With subpath restoration, switching occurs at a pair of nodes along the working path: one upstream and the other downstream from the failure. With path mesh restoration, the endpoints of the demands perform the restoration switching. Within link mesh restoration, one can choose the modularity of switching: per-demand, at a chosen modularity up to the link transmission rate. Similarly, path mesh is performed per-demand or at a chosen modularity. Higher modularity reduces the time to restore but may require more bandwidth.
Since a failure usually affects multiple links and multiple demands, we need to describe how much information about the failed links is known prior to establishing the restoration paths. In the case of failure-independent restoration, no failure isolation on the affected link or demand is assumed. The restoration path must be physically-diverse of the entire length of the link or demand. In the other case, failure-dependent restoration, the exact set of links that are affected by the failure are known, and the restoration path only needs to be disjoint from this set.
The objective function (to be minimized) is defined in terms of a set of quantities calculated from the design. These quantities must be given as optional parameters (attributes) in either the nodes, spans, or edges. Normally, the objective function is a linear function of edges and node attributes, but it is useful to retain the ability to express objective functions and network attributes that have a nonlinear or modular relationship to the basic attributes, which are common to all of the mesh restoration networks considered here.
An edge in the service topology is an abstraction of a link group or link bundle, where each link in the group/bundle represents a specific bandwidth. In the solution to the problems, each demand is routed onto a sequence of edges (on one or more link per edge), and each edge is routed (unless already specified) on a sequence of spans. The inclusion of both edges and spans needs some explanation. Although it is customary to describe the network by its physical connectivity, here represented by spans, the logical (edge) topology that connects switches (at nodes) is not restricted to the span topology, especially when the switches form a strictly smaller subset of the nodes in the network. Express edges (composed of one or more express links), traversing multiple spans, are commonly used in telecommunications networks. It is important to note that the spans are usually fixed, since they represent the physical connectivity of the network, but the choice of edges may be included in the optimization problem. The set of edges given as input represent the candidates to be considered for use, and the restriction to this set can be used to assist the optimization method to find a cost-effective design in a reasonable amount of time.
St*Mesh Data Files
The mrn file generates a number of data files that are loaded by St*Mesh. This data may be edited directly by expert users to address problem types that are currently not supported by St*Network. The data files are:
- Demand-Failureset-Altpathlist (DFA)
- Network links
- Network spans
- Network nodes
Most of the customization addresses the DFA file. In its most generality, demands specify the endpoint nodes, the size (modularity) of each instance, and the number of instances
represented by this demand. The failureset is the OR-set of failure scenarios that affect this demand. A failure scenario is an AND-set of span, link, and/or node failures. The
altpathlist is the ordered list of paths (each a set of links) that may be used when this demand fails.
One means of generating the DFA file is with a traffic file (From-node, To-node, Traffic) and a PPP (point-to-point with paths) file, where the latter associates a nodepair with a list of
failureset-altpathlists. The user needs to specify (with a parm) how traffic is split into separate demands. For example, aggregate STS-1 traffic (on an OC-192 transport network) is
typically composed of STS-1, STS-3c, STS-12c, and STS-48c demands. The tool generates a DFA record (for a given nodepair) from each possible combination of demand and failure-altpathlist.
This method is convenient when a study of the impact of traffic changes is performed.
Each altpath is normally a set of links that forms a contiguous path through the network, but this is not a requirement. In the case where the original working path is reused in the
restoration routing, the altpath given in the DFA is actually the difference between the complete altpath and the original working path. In the most general context, an altpath represents a
set of resource loadings.
Some examples of altpathlists:
- A single shortest path, calculated after the failed links are removed, between From-node and To-node is used to model SBPP, LSP recalculation (in MPLS), and IGP recalculation.
- A single shortest path between nodes adjacent to the failure is used for link Fast ReRoute (FRR). Node FRR is handled similarly.
- Dynamic mesh restoration is more difficult, since the shortest available path is normally taken, but it may not be the (uncapacitated) shortest path. To handle this, the recommended approach is to limit the number of altpaths for each demand to a small number and configure the tool to favor strongly the shortest path.
Network Description File Format
The network description is a modification of a DIMACS file format. Each line of the graph begins with a letter that defines the rest of the line. Many new letters have been added, and some of the current ones have been modified. The lines may be grouped as follows: comment lines (c), the problem definition lines (p, q, g, o), essential network data (n, s, e, d), optional network data and constraints (u, t, r, m), the failure scenarios (f), attributes of network objects (a, b), and finally any custom extensions (x). This is only a suggested ordering, and no particular ordering is required. The interpreter for this file format is not complete, and hence the format may change once the interpreter is finished.
The legal lines are
Comment:
c <remainder of line>
is stored and written back to the solution (.mrn) file. Lines starting with % are ignored entirely.
Problem:
p ptype format version network_id <external_id>
where ptype, format, version, and external_id are alphanumerical strings that describes how this file should be interpreted, and network_id is a alphanumerical string that is used to link this network input file to a solution file or other network input files. The string ptype refers to the problem type. Currently, only ptype = mrn, format = pro, and version = v001 are supported. The pro format is intended to be conform to prolog data types: all lines consist of one or more atoms or terms, separated by one or more spaces.
External_id is an optional field that may be used to denote custom extensions to this format through the use of "x" lines. Note that any solution file for this network_id must preserve the "x" lines, so documentation of the network data that is useful in interpreting the solution may be supplied in one or more "x" lines.
Problem Qualifiers:
q objFunc(costType) <resPathType(Val) faultData(Val) resBWmod(Val) transBWmod(Val) failures(Val)>
where costType is the objective function to be minimized, resPathType Val is a member of {dedicated, path, link, segment}, faultData Val is a member of {fd, fi}, resBWmod Val is an integer > 0,and transBWmod Val is an integer >= ResBWmod. If resPathType Val = dedicated, faultData is ignored. For failures(Val), Val = singleSpan implies that the failure scenarios consist of all single span failures.
Generators:
g network <edgeTopology(Val) demandDistr(Val) demandDefault(Val) edgeRouting(Val)>g group_name <demandDistr(Val) demandDefault(Val)>
where g is either followed by "network" or a group name. In the case of network, there follows a list of generators involving types {n, s, e, d, p}. Subsets of members of a type may be associated with a group. In the case of group_name, the generators listed override the network generators for the members of the group when there is any inconsistency. Individual attributes of the same group_name have highest precedence.
Objective Function:
o costType (Expression)
where costType is the objective function being defined, normally a linear combination of the terms Scalar*Attribute, for each Attribute listed. Any term with an attribute of an object is assumed to be summed over all instances of that object. For example, a design that minimizes the number of edges with total distance breaking ties may be o samplecost (10000*e + 1*edgeLength)where samplecost is the name of the objective function.
Node:
n node_id node_name
where node_id and node_name are alphanumerical strings
Span:
s s1 n1 n2 d
where s1 is the span id, n1 and n2 are the node_id endpoints of the span. The optional d value denotes a positive distance associated with the span (if there is no d value, it is assumed d=1). This value is associated with the attribute "spanLength"
Edge:
e e1 n1 n2 <edgeLength sp([...]) sm([...]) sf([...])>
where e1 is the edge id, n1 and n2 are the endpoints of the edge. There may be multiple edges between two nodes. There are several optional entries for describing the span path of the edge. An explicit span path is given by sp(list of spans). For partially explicit description of the span path, sm (followed by a list of span ids) and sf (followed by a list of span ids) are used to denote mandatory and forbidden spans, respectively, used in the routing of the edge. Since each edge is routed over a sequence of spans, the attribute "edgeLength" is defined as the sum of these span distances, unless specified explicitly.
Demands:
d d1 n1 n2 k m<sp([...]) group_name>
where d1 is the demand id, n1 and n2 are the endpoints of the demand, k is the number of demand units, each unit consuming m capacity. There may be multiple demand elements between two nodes. All demands are assumed to be protected as specified by the resPathType, unless overriden by a protection attribute. The optional field group_name identifies the type of demand and thus assigns this demand all of the attributes of the group.
User-Defined Table:
u table_type key1_type key2_type ...
where table_type must be globally unique, key1_type is one of {node, span, edge, path, failure, parm}, and key2_type is one of {node, span, edge, path, failure, parm}. For example, paths are assigned to demands byu dempathlist d [p]
It is also possible to define constants with the built-in table_type "parm"
u parm constant_name(value)
Table:
t table_type row_id key1 key2 ...
where table_type must be globally unique, row_id is an integer, and each of {key1, key2, ...} is an id for the key_type defined by table_type. For example, routes are assigned to demands byt dempathlist dempath_id dem_id [route1, route2, ... ]
Route Constraints:
r route_id from to <sp([...]) sm([...]) sf([...]) ep([...]) em([...]) ef([...]) np([...]) nm([...]) nf([...]) rd([...])>
where route_id is the route id, sp is followed by the exact list of spans on the route, sm is followed by a list of mandatory spans, from and to are the endpoint nodes of the route, sf followed by a list of forbidden spans, ep followed by the exact list of edges on the route, em followed by mandatory_edges, ef followed by forbidden_edges, np followed by the exact list of nodes on the route, nm followed by mandatory_nodes, nf followed by forbidden nodes, rd followed by the diverse route ids.
min/max constraints:
m type resource id/group min max
where type is one of {n, e, s, p}, resource is one of {working, spare}, id is the type instance id, min is the minimum resource capacity, and max is the maximum resource capacity
Failure (SRG) Scenario:
f id <s([...]) e([...]) n([...])>
states that failure scenario id includes a combination of spans, edges, and nodes.
Attribute:
a type attribute id/group val
where type is one of {n, e, s, d, r, t}, attribute is a string beginning with a lowercase letter, id/group is either the type instance id or a group name, and val is the value of the attribute for this instance. When a group is specified, the value of the attributes is associated with each member of the group. Attributes can be used to define different cost components for use in the objective function. Attributes must be given globally unique names.
Derived Attribute:
b type derived_attribute formula
where formula may involve any combination of constants, attributes or derived_attributes for this type, with the operators {+, -, *, /, ^}, enclosed with parentheses. For example, a modified edge distance can be defined
- b edge edgeDistance1 (edgeDistance + 1)
External Data:
x user-defined
where the format of the user-defined.
Conversion from other formats currently has limited support. Grover has provided MeshBuilder and AMPL-compatible files for a large number of sample networks:
http://www.ece.ualberta.ca/~grover/book/protected-material/
Other formats can be supported, upon request.
Built-in Tables
The table rd, routed-demand, associates a working route with a demand
u rd d r
The table df, demand-failure, connects the routed demand with a list of failures affecting it. The attribute cpaths associates with df a list of candidate restoration
paths.
u df rd [f]
a df cpaths [...]
The table dfp assigns a path to a df. The spareLoad attribute of dfp describes how many mod units were assigned to this path as spare capacity
u dfp df r
a dfp spareLoad dfp_id k
The table ef associates a failure with an edge. The spareLoad attribute defines the spare capacity table for the edge e.
u ef e f
a ef spareLoad ef_id k
Output Files
Solution Line:
s format id objective_function_value
The lower-case character s signifies that this is a solution line. The format field denotes the type of solution contained in the file. This should be the string "mrn'' denoting a mesh restoration network solution. The id is the same as the id in the p line of the input file. The SOLUTION field contains a number corresponding to the objective function value.
Edge Loading
a edge spare edge_id n
Path Loading
a dfp spareLoad dfp_id n
Remarks
By convention, attributes will be used to denote current or new knowledge about data objects, with respect to a problem id. Constraints will be used to describe current
knowledge or desired attributes of these objects. In some cases, data can be described using either attributes or constraints in the network input file, but only attributes may be used to
describe the solution.
One goal of this format is to enable both network input files and solution files to describe partially-instantiated and constrained networks. In the simplest examples, the
input network specifies the nodes, spans, edges, and demands with few constraints. There is a class of problems with network input constraints on the edge topology and routing that
were reported in a DRCN 2003 paper by the author. In these cases, the solution network is fully-instantiated. There are interesting applications involving the exposure
to the user of some nondeterminism where such full-instantiation is undesirable. Rather, the solution file is a generator of one or more fully-instantiated networks. In other
situations, the partial completion of a multi-step solution procedure may be described by a solutions file with some instantiations and some additional constraints.