Metric Increment Tool

Metric Increment Tool is designed to compute 'safe' update sequences, allowing to gracefully perform maintenance operations in a network without triggering transient forwarding loops [1],[2]. In its current state, this tool can handle the removal operation of an arbitrary number of outgoing links surrounding a single router (or the router itself). For a given operation, the program returns a sequence of intermediate increments (relative to the current link weights) to be applied on the links before removing it from the network. Note that a reasonable delay (depending on the size of the network) must be respected between two consecutive updates. Finally, safely re-enabling the removed component, or adding a new one, can be done by applying the computed sequence in reversed order.

Requirements

This program requires no additional library or software for a basic usage. However, some options allow to export graphs in Graphviz .gv format, and you may need one of Graphviz's binary to read them.

Installation

This program is only available for Linux and Mac OS X (10.7 or above).

tar xvzf mincr-tool*
cd mincr-tool
make

Usage

In order to compute an increment sequence for the safe removal of a set of outgoing links of a node, the parameters must be provided as follows:

path/to/binary <topology> <src_node> [ <dst_node_list> ]

Where:

• <topology> represents the path to the topology file in NTF format (see below).
• <src_node> is the identifier of the links source node.
• <dst_node_list> is a comma separated list (no spaces) containing the identifiers of the links destination nodes. If not specified, a complete removal all outgoing links of <src_node> are considered (i.e. complete node removal).

Examples:

# Removal of link CHIC -> ATLA in Internet2 topology
release/mincr Internet2.ntf CHIC ATLA

# Removal of links LOSA -> SALT and LOSA -> HOUST
release/mincr Internet2.ntf LOSA SALT,HOUST

# Removal of node NEWY
release/mincr Internet2.ntf NEWY

For usage information about options and additional modes, use --help.

Network Topology File (NTF) format

In NTF format, graphs are represented as lists of weighted directed links. Each line consists of three space separated fields, the first two are strings representing the link's end nodes, while the last one is a strictly positive integer value corresponding to the IGP weight. Empty lines and characters following a hash (#) are ignored.

# Link SEAT -> LOSA with an IGP weight of 1342
SEAT LOSA 1342

For complete examples, you may refer to the sample files provided along with this program.

Please note that parallel links are currently not supported.

License

Copyright 2011, 2012, 2013 Francois Clad.

This program is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with this program. If not, see http://www.gnu.org/licenses/.

Contact

For any information regarding this program, feel free to send me an email at fclad@unistra.fr.

References

• [1] F. Clad, P. Merindol, J.-J. Pansiot, P. Francois and O. Bonaventure, "Graceful Convergence in Link-State IP Networks: A Lightweight Algorithm Ensuring Minimal Operational Impact," IEEE/ACM Transactions on Networking, 2013, to appear.
• [2] F. Clad, P. Merindol, S. Vissicchio, J.-J. Pansiot and P. Francois, "Graceful Router Updates in Link-State Protocols," In proceedings of the IEEE International Conference on Network Protocols, 2013, to appear.