Net2Plan [2] is a free and open-source Java tool devoted to the planning, optimization and evaluation of communication networks. It has been originally thought as a tool to assist the teaching of communication networks planning courses. Eventually it has converted into a powerful network planning tool for the academia and industry, together with a growing repository of network planning resources.
Net2Plan is built on top of an abstract network representation, so-called network plan, based on six abstract components: nodes, links, routes, traffic demands, protection segments and network layers. The network representation is technology-agnostic, thus Net2Plan can be adapted for planning networks in any technology. Technology-specific information can be introduced in the network representation via user-defined attributes attached to any of the abstract components mentioned above. Some attribute names has been fixed to ease the adaptation in well-known technologies (i.e. IP networks). For more information, see Section 3.1↓.
Net2Plan is implemented as a Java library along with both command-line and graphical user interfaces (CLI and GUI, respectively). The GUI is specially useful for laboratory sessions as an educational resource, or for a visual inspection of the network. In its turn, the command-line interface is specifically devoted to in-depth research studies, making use of batch processing or large-scale simulation features. Therefore, Net2Plan is a tool intended for a broad spectrum of users: industry, research, and academia.
Regardless of the interface (CLI or GUI) selected by the user, Net2Plan currently provides six different tools:
Offline network design: Targeted to evaluate the network designs generated by built-in or user-defined offline network design algorithms, deciding on aspects such as the network topology, the traffic routing, link capacities, protection routes and so on. If needed, those algorithms based on constrained optimization formulations (i.e. ILPs) can be fast-prototyped using the open-source Java Optimization Modeler library (JOM [1]), to interface to a number of external solvers such as GPLK, CPLEX or IPOPT.
Traffic matrix generation: Assists users in the process of generating and normalizing traffic matrices i.e. following random models found in the literature.
Resilience simulation: Simulates the network operation, where failures in links and nodes randomly appear according to user-defined reliability information and the definition of shared-risk groups (see Section 3.1.8.1↓). Targeted to evaluate availability performances of built-in or user-defined protection/restoration schemes.
Time-varying traffic simulation: Simulates the network operation, where traffic demand volumes vary with time according to a built-in or user-defined pattern. Targeted to evaluate the performances of built-in or user-defined schemes that react to traffic variations (i.e. traffic rerouting schemes, on-demand capacity-provisioning schemes, etc.)
Connection-admission-control simulation: Simulates the network operation, where traffic demands are the source of connection requests. Targeted to evaluate built-in or user-defined CAC (Connection-Admission-Control) algorithms, which dynamically allocate resources to connection requests.
Reporting: Net2Plan permits the generation of built-in or user-defined reports, from any network design. The report generation tool is integrated within all the previous functionalities, so that it is possible to create reports collecting performance measures in any of these aspects.
In all the features, the GUI organizes network statistics and performance estimations computed from the network design/simulation.
Algorithms in each of the features mentioned are Java .class/.jar files implementing a particular public interface (see Javadoc information). Net2Plan allows testing built-in or user-created algorithms. Creating a new algorithm for a particular Net2Plan feature, just requires programming a Java class implementing the appropriate interface.
And remember that Net2Plan is free and open-source! It is licensed under the GNU Lesser General Public License Version 3 or later (the "LGPL").
Numerous network planning software tools can be found spanning a broad range of platforms, systems, languages, functionalities and applications. Some of them are oriented to the industry, whereas others are developed by academia for educational and research purposes. On the academia side, researchers investigating novel planning problems commonly need full control of the planning decisions, and develop their algorithms almost from scratch. Planning algorithms can be based on solving problem formulations (i.e. Integer Linear Programs) using specialized solvers (i.e. CPLEX, or MOSEK), or applying heuristic techniques. From the industry side, there is a trend to prefer commercial network planning tools that hide the planning decisions and any algorithmic details under intuitive graphical interfaces resembling computer-aided tools. All of them provide a more or less complete set of features to design and analyze networks, without relying on a specific vendor. These features are simulations of several configuration scenarios, routing schemes, network recovery tests, or traffic load analysis.
Unfortunately, existing tools lack of flexibility for testing different planning algorithms (i.e. users are only allowed to use built-in algorithms) or are not designed for educational purposes (i.e. their underlying algorithmic details are not publicly available). This is very important, since network optimization is more than drag and drop icons and connecting them to build a network. In addition, those tools only provide support for mature technologies and protocols for which there is a definite and large market, but don’t provide assistance for the abundance of possible prospective studies on emergent alternatives which could be performed.
In contrast, Net2Plan is a publicly-available open-source network optimization tool, not constrained to any specific network technology (and suitable to any of them), which allows users to test their own algorithms, or use the built-in ones. Net2Plan assists the task of creating and evaluating network design algorithms by providing a large set of built-in examples (together with its source code), many of them thoroughly described in the examples section of [2], a set of libraries (e.g. compute k-shortest paths, network performance metrics, or random traffic matrix models) documented in the Library API Javadoc (see Section 4.1↓ to know where you can find it). Moreover, automatic report generation (with built-in or user-defined reports) and post-analysis simulation tools integrated in Net2Plan help users to get insight into the network design merits.
The Net2Plan philosophy enforces software reutilization. Once an algorithm is developed within the Net2Plan framework it can be modified or reused as parts of others, and can be applied to any network instance, so that network can be progressively designed. That is, users can chain successive algorithms, each one completing a part of the network design. For instance, you can start with a network where only the nodes are defined. Then, an algorithm is used to define the links in the network according to some figure of performance. Afterwards, another algorithm can be run to jointly decide on the capacity in the links and routing of the flows, for a given traffic matrix. As a result, Net2Plan can be a powerful tool for communications network planning courses, since students can see step by step how their designs grow. Besides, once the network design is completed, users can analyze and evaluate it by means of several reports, which can be built-in or user-defined ones, and post-analysis simulation tools. Fig. 2.1↓ summarizes this philosophy. In addition, the tool is intended to become a repository for network planning algorithms in any technology. Thus, the algorithms in the repository will become open for validation and verification, improving the trustworthiness of their results.
Figure 2.1 Workflow
In our opinion, all of these building block make Net2Plan a powerful tool for network planning for academia and industry.
As stated in the previous section, Net2Plan is designed with the aim to overcome the barriers imposed by existing network planning tools for two main reasons: (i) users are not limited to execute built-in algorithms, but also can integrate their own algorithms, applicable to any network instance, as Java classes implementing particular interfaces, and (ii) Net2Plan defines a network representation, so-called network plan, based on abstract concepts such as nodes, links, routes, traffic demands, and protection segments and network layers, without relying on any network technology. We believe that these are the key features enabling Net2Plan to be applicable to almost any (existing or not) technology, in contrast to the restricted scope of commercial tools, limited to mature technologies and built-in algorithms.
Nonetheless, even though Net2Plan is a technology-agnostic tool, users can introduce their technology-specific information via user-defined attributes for each element in the network design. In Section 3.1.8↓, some examples of technology-specific usages are shown. We remark that users are in charge to check the validity of the technology-specific attributes (i.e. negative link weights for OSPF routing). In this respect, Net2Plan provides some libraries (i.e. WDMUtils and IPUtils) to ease the prototyping of some technology-specific algorithms.
The network design is stored into a data structure so-called network plan (class com.net2plan.interfaces.networkDesign.NetPlan in the Net2Plan library). In the offline network design feature, algorithms receive a network plan and return a modified network plan. The NetPlan object contains only the base minimum member variables (node position, link capacity, link length, offered traffic by demand...), which can be accessed or modified by getX() and setX() methods. Problem- or technology-specific attributes (i.e. link weights for OSPF routing), that are often attached to a network element (node, link...) in a specific tool, are divorced from those elements and are stored in key-value maps within the NetPlan object for each one, or even for the whole network. By doing so, users can add/remove attributes to every network element at run-time without having to change the NetPlan representation. For more information, check the Library API Javadoc for the class NetPlan.
Nodes are the basic entity of a network design, and are either a connection point, a redistribution point or a communication end-point, which are able to send, receive, or forward traffic over a communication channel (or link).
Nodes are characterized by three member variables: identifier, position and name. The first one, it is internally defined by the kernel and determines a serial unique number of the node. The second one represents the position of the node in a bidimensional Cartesian plane. The last one indicates the node name i.e. to be shown in the graphical interface.
Along with nodes, links comprise the topology of the network. They are the communication channels enabling connectivity between two nodes. In Net2Plan, links are unidirectional, from a node to another one. Two nodes can be connected by zero, one or more links. However, self-links (links where origin node and destination node are the same one) are forbidden.
Links are characterized by five member variables: identifier, origin node, destination node, capacity and length. Again, the identifier is a serial unique identifier of the link. Origin and destination nodes are the identifiers of the corresponding nodes. Capacity (measured in Erlangs) is the amount of traffic the link is able to carry. Finally, length (assumed to be in kilometers) represents the physical length of the node.
Traffic is modelled through a set of demands (or commodities). Each demand represents an offered end-to-end traffic flow to the network. In Net2Plan, demands are considered unicast, that is, they have only one ingress node and one egress node. In addition, self-demands are not allowed.
Demands have four member variables: identifier, ingress node, egress node and offered traffic volume. The first one is a serial number assigned by the kernel that uniquely identify the demand. The second one indicates the traffic source node identifier, while the third one is the sink node identifier. Finally, the latter is the traffic volume (assumed in Erlangs) for the demand.
A simplified approach to model the offered traffic between nodes is the so-called traffic matrix. A traffic matrix is a matrix (where is the number of nodes in the network) in which each pair represents the (average) traffic from node to node . The main drawback of representing the offered traffic by means of traffic matrices, is that the traffic matrix representation assumes that at most one demand exists between each pair of nodes. Then, if we compute the traffic matrix representation of a demand set where some node pairs have more than one demand between them, an ambiguity can occur. This situation is posed in Fig. 3.1↓, where demands 1 and 2 from the demand set on the left are grouped in a single entry in the traffic matrix. The same result is obtained with the demand set on the right. For this reason, in Net2Plan is employed a demand-based traffic model.
Routes are the paths in a network along which to send the traffic from demands. Routes are defined as an ordered (and contiguous) sequence of links going from the ingress node of the demand to the egress node. Each demand may have zero, one or more routes carrying traffic at the same time, provided that the carried traffic cannot overcome the offered traffic. The CandidatePathList library included into the Net2Plan Library (see Section 3.2.1↓) allows to determine a set of feasible routes for demands using shortest-path algorithms.
Routes have five member variables: identifier, demand, sequence of links, carried traffic, and protection segment list. The first one is a unique serial number determined by the kernel. The second one is the identifier of the demand associated to the path. The third one is the sequence of link identifiers followed by the route. The fourth one is the traffic volume that carries this route. Finally, the latter is the set of protection segments that protect traffic from this route (see next section for more information).
Next, two typical routing constraints are described:
Unsplittable or non-bifurcated routing: If the routing is non-bifurcated, each traffic demand is carried by at most one path. Conversely, if traffic from a given demand is carried by more than one path, we say that the routing of the demand is balanced among those paths.
Integral flows routing: Each path must carry an integer amount of traffic. In some cases, the offered traffic is measured on integer units and it has no sense to carry non-integer fractions of traffic (i.e. technologies based on virtual circuits of fixed bandwidth). Thus, an integral routing is constrained to carry an integral amount of traffic in each path (or an integer multiple of a base value).
A protection segment is defined as an ordered sequence of links with a specific volume of reserved bandwidth (or capacity) which is used to (partially or completely) protect one or more traffic routes, taking an alternative path to the original one. The power of the protection segments comes from the fact that they are not forced to be installed from the initial node to the destination node of the route(s), that is, they can protect only a segment of the whole route, as logical, starting and ending from nodes in the original route, and the reserved bandwidth can be shared among several routes. Please, note that the reserved bandwidth is taken from the capacity of the link, so if there are a set of defined protection segments, the maximum capacity available in the corresponding links is reduced by the amount of reserved bandwidth. Also, a link may be associated to several protection segments.
Protection segments have three member variables: identifier, sequence of links and reserved bandwidth. The first one is a unique serial number determined by the kernel. The second one is the sequence of links followed by the protection segment. Finally, the latter is the reserved bandwidth in any of the links in the protection segment.
The flexibility provided by protection segments allows to model different protection techniques:
If a protection segment is associated to one single route, we model the so-called dedicated protection: the reserved bandwidth in that segment can only be used if the (primary) route fails. If a protection segment is associated to more than one routes, we are modeling a shared protection scheme.
If the reserved bandwidth of a protection segment is below the carried traffic by the primary route, you are modeling a partial-protection scheme.
If a protection segment shares the origin and destination nodes of the route, you are modeling a path-protection scheme. If only shares the origin and destination nodes of a link in the network, you are modeling a link-protection scheme. Otherwise, it is the subpath-protection scheme.
Table 3.1↓ summarizes the aforementioned information. Here, if a member attribute cannot be change by the user once the element is defined, or if the attribute is internally handled by the kernel, is marked as read-only.
Element
Member attribute
Description
Node
id
Identifier (read-only)
name
Node name
position
Position in a 2D plane (x,y)
Link
id
Identifier (read-only)
origin node
Origin node of the link (read-only)
destination node
Destination node of the link (different than the origin node) (read-only)
capacity
Capacity of the link (in Erlangs)
length
Physical link length (in kilometers)
Demand
id
Identifier (read-only)
ingress node
Source node of the demand (read-only)
egress node
Sink node of the demand (different than the ingress node) (read-only)
offered traffic volume
Amount of traffic offered by the demand (in Erlangs)
Route
id
Identifier (read-only)
demand
Demand identifier (read-only)
sequence of links
Sequence of links followed by the route
carried traffic volume
Amount of traffic carried by the route (in Erlangs)
backup segment list
Set of protection segments associated to the route
Protection segments
id
Identifier (read-only)
sequence of links
Sequence of links followed by the protection segment
reserved bandwidth
Amount of bandwidth reserved in every link in the protection segment (in Erlangs)
Table 3.1 Summary of network elements involved in Net2Plan, and its member attributes
The NetPlan class, in an effort to make the tool as generic and flexible as possible, provides a simple way to model generic multilayer networks. In a conceptual way, given a multilayer network, links in the upper layer could be seen as traffic demands in the lower layer, which if have an associated route are assumed to be carried, and otherwise, they are blocked. So, users who try to develop multilayer algorithms just have to decompose the multilayer network in a list of single layer networks, that is, as a list of NetPlan objects.
As stated in previous sections, the NetPlan object contains only the base minimum member variables (node position, link capacity, link length, offered traffic by demand...). Problem- or technology-specific attributes (i.e. link weights for OSPF routing in IP networks), that are often attached to a network element (node, link...) in a specific tool, are divorced from those elements and are stored in key-value maps within the NetPlan object. By doing so, users can add/remove attributes to every network element at run-time without having to change the NetPlan representation. For more information, check the Library API Javadoc for the class NetPlan.
As an example, let us to suppose you are using an algorithm to determine link capacities given a traffic demand set, and you have to choose between several capacity values in order to minimize the total network cost while all traffic is carried. You could define the options for capacity values and associated costs into two network-wide variables which would be used by your algorithm.
Important: All key-value pairs in the attribute maps are stored as String values. Users are responsible to make the proper conversions. For example, you can store an int array as a succession of numbers separated by spaces.
In the following sections, we show some examples of technological conventions used within Net2Plan, and supported by the library API. Users are free to use their own conventions, without support from the library API.
A challenging issue for service providers is to provide reliable routes for accepted requests. At this level, the reliability of a single connection in the network might be measured as a function of the number of links it uses, each single link having its own probability of failure. However, in a physical network, several links may be packed together and hence physically cut simultaneously (earthquake, fire, malicious behaviour etc), or nodes may go down due to a lack of electrical power. Consequently, a single cause of breakdown induces several failures among network infrastructure. The concept of Shared Risk Group (SRG), has been introduced to capture network survivability issues in this situation, i.e. when a set of resources may fail simultaneously.
SRGs information in the network representation is defined as follows:
Nodes and links are the elements that can be a subject of failure. For each node and link in a SRG, users should define an attribute srgs and indicate the associated SRG identifiers the node/link belongs to, separated by spaces. Note that a node/link can be in zero or more SRGs.
The mean time to fail (MTTF) and mean time to repair (MTTR) information for each SRG should be provided. To define the MTTF (or MTTR) per SRG, users should define a network attribute mttf (or mttr) with the corresponding values separated by spaces. The first number is assumed to be associated to SRG 0, next SRG 1, etc. For this reason, it is recommended to use consecutive numbers starting from 0 in SRG identifiers in the previous point.
The SRG concept is widely employed in the resilience simulation (see Section 5.4.1↓). Here, an event generator is in charge of randomly generating SRG failure/reparation events according to the MTTF and MTTR values provided. When a failure/reparation event occurs associated to a SRG, all the nodes/links belonging to it are supposed to fail/be repaired simultaneously. Also, availability and disaster-vulnerability reports make intensive use of the SRG concept (see Built-in Examples in [2]).
Nonetheless, the simulator and built-in reports dealing with resilience include a number of models to automate the definition of SRGs in a network design. In other words, users can define SRGs manually (or using a network design algorithm), but also are able to use one of the models provided: one SRG per node, one SRG per unidirectional link, one SRG per unidirectional link bundle (all unidirectional links between a node pair), or one SRG per bidirectional link bundle (all links between each node pair). Please note that in case you use one of these models, the information about SRGs included in the network design is ignored.
The basic building blocks of the Internet are smaller subnetworks called routing domains or autonomous systems (AS). The operator of an AS is called an Internet service provider (ISP) and is, among other things, responsible of the routing of the traffific within the domain. The routing is conducted by routers via static or dynamic routing tables. While in small domains routes are configured manually, in larger domains routing tables are maintained into routers communicating with each other via an interior gateway protocol (IGP). In IP networks, most of the IGPs use shortest-path routing, and send traffic along the shortest paths from the origins to the destinations, with respect to an artificial metric. Link weights are part of the routing protocol parameters.
The open shortest-path first (OSPF) protocol and the intermediate system to intermediate system (IS-IS) are the most common IGPs. In OSPF, it is required that the link weights are integer numbers in range [1, 65535]. Then, shortest paths are determined given the weights using the Dijkstra’s algorithm. However, a standard of how to deal with the case where there are several paths is not specificied in the original OSPF. In the absense of any explicit support to take advantage of this, a path may be chosen arbitrarily, or the same path may be used forever.
Anyway, some techniques have been utilized to divide traffic somewhat evenly among the available paths. A widely utilized technique to improve loading is known as Equal-Cost Multipath (ECMP) [4]. If, at a node, there are several shortest paths to a destination, then the incoming traffic to this node is divided evenly among all the outgoing interfaces associated to one of the shortest paths to the destination. Unfortunately, in general this not equivalent to an even distribution of the traffic on all shortest paths. In its turn, the optimized multipath extension to OSPF (OSPF-OMP) [7] incorporates a link-load feedback mechanism which allows splitting the traffic load among multiple (near) equal cost paths.
In Net2Plan, as stated in Section 3.1.8.1↑, routing is represented according to a path-based policy. In other words, for every demand a set of end-to-end paths are defined and also the traffic volume carried into each one. In contrast, IP uses destination-based routing, that is, every node has a routing table in which for every incoming packet, independently of its corresponding traffic demand, the forwarding engine decides the output interface according to its destination address.
Fortunately, the IPUtils library, included into the Net2Plan library (see Library API Javadoc), allows interoperation between these schemes. First, a link attribute so-called linkWeight is assigned in every link to represent its weight in IGPs. While IGP standards recommend to use integer values, we relax this limitation and allow double precision values, even though we also discourage users from using fractional values. Once link weights are defined, IP routing tables can be computed in the form of the matrix, which represents for every sink node the fraction of traffic carried by every output link in the network. In other words, it is fraction of the traffic targeted to node that arrives (or is generated in) node (the initial node of link ), that is, forwarded through link . If a node does not forward any traffic to a destination , it is not possible to determine the fractions for the output links of the node. Then, it is arbitrarily assumed that the 100% of the traffic to node , would be forwarded through the shortest path (in number of hops) from to . Please note that for every destination , for every outgoing link from node . Finally, once is determined, the library is able to convert it to a path-based routing and add it to the design. Of course, the library allows to make the inverse process and obtain the destination-based routing from the path-based routing of a given design. Given a set of link weights, the library is able to compute the destination-based routing using either the ECMP rule or the OMP rule.
To summarize, the following may be a process to apply IP routing to a previous design with nodes, links, capacities and traffic demands (i.e. stored into a variable named netPlan).
Compute the set of link weights (i.e. stored into a variable named linkWeights), or define according to a given criteria (i.e. all-one weights imply min-hop routing)
Apply the link weights to the links in the design: IPUtils.setLinkWeightAttributes(netPlan, linkWeights);
Compute the destination-based routing: double[][] f_te = IPUtils.computeECMPRoutingTableMatrix(netPlan.getLinkTable(), linkWeights, netPlan.getNumberOfNodes());
Apply the new routing to the design: IPUtils.setRoutesFromRoutingTableMatrix(netPlan, f_te);
For more information, we refer to the IPUtils library in the Javadoc.
Optical networks have been established as the enabling technology for today’s high-speed communication networks. Wavelength Division Multiplexing (WDM) enables the efficient utilization of optical fibers by dividing its tremendous bandwidth into a set of disjoint wavelength bands, referred to as wavelengths. Each wavelength supports one communication channel which corresponds to an end user operating at an arbitrary speed, e.g. peak electronic speed. This helps to overcome the opto-electronic mismatch between the multiple terabit-per-second bandwidth of optical fibers and the gigabit-per-second electronic processing speeds at end users. In wavelength-routed WDM networks, all-optical directed channels, called lightpaths, can be established between pairs of nodes which are not necessarily neighboring in the physical topology.
A set of lightpaths creates a so-called virtual topology over the physical interconnection of fibers. Packet-switched traffic is then routed over this virtual topology, independent of the physical topology. Traffic send via a lightpath is transmitted in the optical domain with no opto-electronic conversion at intermediate nodes. Establishing a lightpath requires a transmitter and receiver at the source and destination nodes, respectively, and includes routing it over the physical topology and assigning to it a wavelength. This is known as the routing and wavelength assignment (RWA) problem.
Lightpaths routed over the same physical links at the same time cannot be assigned the same wavelength. This is called the wavelength clash constraint. If there are no wavelength converters available, which is often the case due to their high prices, the entire lightpath must be established the same wavelength. This is known as the wavelength continuity constraint.
In Net2Plan, the WDMUtils library is provided to ease the handling of WDM networks. Here, optical lightpath requests are assumed to be traffic demands, each one with a traffic volume equal to its nominal rate (i.e. 40 Gbps), being its route the RWA. The fiber plant is associated with the links. The WDM technology-specific attributes in this network representation are as follows. For fiber links, we introduce the attribute numWavelengths to represent the number of WDM channels available; for working and protection lightpaths (represented by routes and protection segments, respectively), we introduce the attributes seqWavelenghts, a vector with the wavelengths used in each traversed fiber, and nodesWithRegenerator a vector storing those nodes in which a regenerator (or wavelength converter) is installed (if available). Methods to check the validity of the design and to solve the wavelength assignment problem are provided.
For more information, we refer to the WDMUtils library in the Javadoc.
One of the most important features of Net2Plan is that allows users to execute their own code (algorithms, reports... in general we refer to them as runnable code). Here, we briefly describe how integrate their code into Net2Plan.
Runnable code is implemented as Java classes, using single .class files or integrated into .jar files, with a given signature (check the Library API Javadoc for more information). Integration of runnable code simply requires saving it into any directory of the computer, although it is a good practice to store them in the workspace directory.
In addition, in order to improve the user experience, kernel is able to catch any exception thrown by runnable code. Those exceptions are introduced in a Java error console (see Section 5.1.1.3↓ for more information). For example, exceptions allow users to check if their algorithms are well-programmed (i.e. no null-pointers), thus in the error console they got a full trace of the error (files, line numbers...). However, when input parameters are wrong or an error within the algorithm is returned (i.e. an optimization problem is unable to find feasible solutions), we recommend to throw extensions using the Net2PlanException class (see Library API Javadoc for more information), since it allows users to see the error in a small dialog in which the only information is the error message (i.e. "A feasible solution was not found") instead of the full error trace in the error console (i.e. RuntimeException: A feasible solution was not found (MyAlgorithm.java:35), ...).
Important: When runnable code is implemented as Java .class files, the full path to the class must follow the package name of the class, in order to successfully load the code. For example, if we create an algorithm named testAlgorithm in the package test.myAlgorithms, the full path to the class must be like ...{any}.../test/myAlgorithms/testAlgorithm.class. For .jar files there is not any restriction on the full path, they can be stored at any folder.
Important: Net2Plan allows to make “online” changes in the runnable code, that is, users can modify their runnable code, recompile and reexecute without the need to restart Net2Plan.
3.2.1 Net2Plan Library, Built-in Examples and Code Repository
Net2Plan assists the task of creating and evaluating algorithms by providing built-in example algorithms and a set of libraries (e.g. k-loopless shortest paths, minimum spanning tree…). An exhaustive list of built-in algorithms and the Library API Javadoc can be found in [2]. The idea is that the website becomes a repository for network planning algorithms in any technology. Thus, the algorithms in the repository will be open for validation and verification, improving the trustworthiness of planning results.
The library is divided into three parts:
Input/Output interfaces: Provides a set of classes and interfaces for the different tools: offline network design, reporting and simulators. Users should check these packages in order to develop their own code.
Libraries: Provides a set of useful libraries to develop algorithms and reports (i.e. to compute candidate path list, graph metrics...)
Utils: General utility static methods for Java language (i.e. methods to work with int/double arrays)
For more information, we refer to the Library API Javadoc.
Often, some network design problems are solved by modeling them as optimization problems (i.e. integer linear problems, linear problems, convex problems…), and then calling an optimization solver to obtain its numerical solution. In this context, optimization modeling tools are targeted to ease the definition of the problem decision variables, constraints and objective function, and become an interface with the (usually complex) solver libraries. AMPL and GAMS are examples of commercial modeling tools. JOM (Java Optimization Modeler) is an open-source Java library which can interface with a number of solvers using vectorial MATLAB-like syntax, which i.e. permits the addition of sets of constraints in one line of code. Current JOM version can interface with GPLK (free) and CPLEX (commercial) solvers for mixed integer linear problems, and IPOPT (free) for non-linear differentiable problems. JOM directly interfaces with compiled solver libraries (.DLLs in Windows and .SOs in Linux), via Java Native Access (JNA). JOM is independent from Net2Plan and can be used for any type of optimization problem. However, Net2Plan uses JOM in all the network design algorithm examples based on solving formulations that are included in the Net2Plan distribution [1].
In Appendix A↓, we include a brief summary of mathematical notation we use in the built-in code using JOM library. Also, in Appendix B↓, we include the mathematical definition of several performance metrics integrated into Net2Plan.
4 Installation guide, system requirements and starting Net2Plan
Net2Plan requires Java Runtime Environment 7 or higher versions and a screen resolution of, at least, 800x600 pixels. Since it is developed in Java, it works in the most well-known operation systems (Microsoft Windows, Linux, Mac OS X).
To install Net2Plan, just save the compressed file in any directory. Then, extract all the files and folders into a new directory, for example C:\Work\Net2Plan (in a Windows environment), and now it is ready to run.
To execute Net2Plan in GUI mode (see Section 5↓), just double click on Net2Plan.jar, or execute the following command in a terminal: java -jar Net2Plan.jar
To execute Net2Plan in CLI mode (see Section 6↓), execute the following command in a terminal: java -jar Net2Plan-cli.jar
Use Options to set Net2Plan-wide parameters. These options have a global scope to all Net2Plan modules: are used within the kernel, and, for instance, to compute delay metrics in built-in reports. Users implementing their own algorithms/reports/event generators/event processors have access to these parameters through a key-value map endorsed as an input parameter so-called net2planParameters. For more information, see the class com.net2plan.interfaces.networkDesign.Configuration in the Library API Javadoc.
In this version there are just four options:
Precision factor for checks (field precisionFactor in net2planParameters): This parameter allows considering in the kernel small tolerances in the sanity-checks of the network designs. It avoids situations in which numerical inaccuracies would be interpreted as errors, i.e. if carried traffic by a link is greater than link capacity, kernel may show a warning, but in some cases due to solvers precision there might be due to a numerical error. For example, if = 10 and = 10.000001 in general the kernel would trigger an error, but with this precision factor if PRECISIONFACTOR then the kernel assumes . Its value is constrained to be in range (0,1).
Average packet length (bytes) (field averagePacketLengthInBytes in net2planParameters): To get average packet delay metrics in the reports, it is needed to convert the traffic in the links from an adimensional Erlang units to seconds. This parameter divided by the next one allows such conversion. Its value is constrained to be greater than zero.
Binary rate per Erlang (bps) (field binaryRateInBitsPerSecondPerErlang in net2planParameters): Binary rate equivalent to 1 Erlang. Its value is constrained to be greater than zero.
Propagation speed (km/s) (field propagationSpeedInKmPerSecond in net2planParameters): Velocity of propagation in the media considered for the links. It allows to compute propagation times. A zero or negative value implies that propagation times are equal to zero.
Options are saved when user presses the “Update” button. Then, new values are checked and saved in the options file.
Although a moderate library set is provided within Net2Plan, users may require extra Java libraries (.jar files) to develop their own algorithms or reports (i.e. mathematical or graph theory libraries). So, the classpath editor avoids the tedious task of include Java libraries in environment variables (i.e. CLASSPATH in Windows).
Important: In the current version of Net2Plan Java libraries can be included in run-time, but unfortunately it is not possible to do the same to remove libraries. In this case, user is forced to restart Net2Plan.
This feature centralizes the error handling within Net2Plan. When an error is thrown, for example, due to invalid input parameters in an algorithm, the error and the stack trace is shown there. Moreover, System.out/System.err is redirected there also, allowing users to debug their Java code.
Important: When JNI/JNA for native library access is used, the native output (i.e. stdout in C/C++) is not equivalent to the Java output, thus such an information will not appeared in the Java error console. A workaround is to start the GUI from the command-line according to Section 4↑.
Under this menu are organized all the tools provided within Net2Plan: Offline network design, Traffic matrix design and post-analysis simulation tools.
This tool assists users in the process of offline network design and planning. In practical network design different variables can be involved: link capacities, the traffic routing, the topological design of the network, the storage capacity at each node, and so on. Usually, offline network design problems receive some of this information as input parameters (e.g. traffic demand, and network topology) and try optimize the rest (e.g. capacities in the links and traffic routing) according to a performance merit of interest. Clearly, the number of possible variants and subtypes of network design problems is infinite. Moreover, different technologies add their own particular aspects to network design. For this reason, network design has become a mixture of art and engineering.
In an attempt to provide a (somehow) systematic criteria to cathegorize network design problems, in Net2Plan we adopted the following scheme, which is just an extension of the network design problems’ taxonomy in Kleinrock’s book [5]:
Topology Assignment (TA): The nodes and/or links in the network are decision variables to optimize (graph )
Capacity Assignment (CA): The capacities in the links are decision variables to optimize (vector )
Flow Assignment (FA): The routing of the traffic demands is to be optimized (vector )
Bandwidth Assignment (BA): The traffic carried by each demand is to be optimized (vector )
According to this naming scheme, combinations of these problems are named combining the acronyms. For example, a capacity and flow assignment (CFA) problem involves the joint computation of routing and link capacities. We remark that this taxonomy should be considered as an attempt to give a didactic organization to the utmost diversity of planning problems that arise in communication networks.
Depending on the scope of the algorithm, single layer or multilayer, the algorithm must implement a different Java interface. Check the package com.net2plan.interfaces.networkDesign in the Library API Javadoc to obtain more information.
Selecting Offline network design opens the Network design window, which you can use to execute your algorithms. The workspace of the window is divided into three areas: input data, execution and reporting (right area), plot area (top-left area), and warning area (bottom-left area).
This panel is used for graphically design and see networks. Users are able to add or remove nodes and links, make zoom or take a picture.
Nodes are inserted by right clicking into the canvas and using the option Add node here. Nodes can be removed by right clicking on them and using the option Remove node. Also it is possible to move nodes by dragging them (in this case, you must press CTRL key during that process).
Figure 5.7 Inserting a node
Links are inserted by clicking first in the origin node and then in the destination node. It is possible to insert unidirectional links or bidirectional ones (in this case, you must press SHIFT key during that process). Also links can be inserted by right clicking over the origin node and selecting the destination node in the popup menu.
Figure 5.8 Inserting a link graphically
Figure 5.9 Inserting a link using a popup menu
In addition, in this panel you can see the current state of the network design through the "Edit network plan" tab. If the design includes routing information, it is possible to visualize the paths which carry traffic of a demand, the paths traversing a link...
Figure 5.10 Showing the route followed by a traffic demand
Finally, users can add/remove network elements (nodes, links, demands...), assign values to certain properties (e.g. link capacities to all links), or even add/remove user-specific attributes to every network element (nodes, links... or the whole network) using popup menus in the "Edit network plan" tab.
In this panel you can see the general state of the network design e.g. if node, link or demand sets are defined, if routing is defined, that is, to check the current state in which the network is.
With these two panels, users are able to execute and edit their designs and execute algorithms. In the Execution controller, users can load network designs and traffic demands and execute algorithms. In general, to calculate a new design the user has to specify the following things:
Network structure: a .n2p file with a previously computed and saved network design. The design can be partial: e.g. only the nodes of the network are present. Loading a new design, overwrites any active design coming from previous design algorithm executions.We note the current version of Net2Plan only allows to load single layer designs, while it is able to save multilayer designs.
Traffic demands: a .n2p file describing a demand set. If the network structure already contains a demand set and then you load a new .n2p file, you will be asked to overwrite it and to remove routing information. Asking “No” you cancel that process.
Algorithm: a Java code, implementing the algorithm to be applied. The algorithm is applied to the current network plan, that is, the result that is active in the GUI, being the result of previous design algorithm executions, manual editing of links/nodes/demands/routes etc. In case a multilayer design is active, if the algorithm is for single layer designs, then it will be applied to the active layer; otherwise, to the whole design.
Parameters: if the algorithm selected requires specific parameters, they are shown in a table. Each parameter has a default value that the user can change.
Figure 5.12 Executing an algorithm
Once those inputs are filled, the algorithm can be executed by clicking on Execute. A popup will be shown during the execution of the algorithms, allowing to stop algorithms taking long execution times. When the execution finishes, a message will be shown, informing whether the algorithm runs well or some error was thrown. Users are able to save current designs using the option Save. For multilayer designs it gives the option to save all layers (using the following naming criterium: filename-layerId.n2p , where filename is the name given by the user, and layerId is the layer index).
In the Edit network plan tab, users can see and edit information of each element within the network plan e.g. change node name or position, change link capacity, or add a demand attribute. Moreover, as network plan is being completed, more information appears, e.g. if all traffic is being carried, if there are traffic losses...
In this panel user can select a report to apply to the network plan. The structure is similar to those to execute algorithms. Upon selection and clicking Show the report is shown in the bottom part. Users can see it in a browser using the option View in navigator. For multilayer designs the report will be applied to the active layer.
Figure 5.14 Showing a report
Reports can be closed individually using the CTRL + W combination.
As stated in Section A↓, network dimensioning is based on a set (or more than one) of traffic demands that contains the average traffic volume demand for each node pair. In the simplest case, it is assumed that no more than one demand between each node pair exists. Therefore, the traffic matrix is a non-ambiguous way to represent the traffic demands.
However, it is difficult to measure these matrices directly in large operational networks, or they don’t exist for non-operational networks. Hence, operators estimate traffic matrices from measurements of link load and other more easily measured data. Another classical way to obtain traffic matrices is to make use of existing models in the literature, for example, from population-distance models [3] (see Section 5.3.4↓), which assumes that the traffic between each node pair is proportional to the population associated to the nodes and inversely proportional to the distance between them.
The traffic matrix design tool (see Section 5.3↑) assists users in the process of generating user-defined traffic matrices following (or not) several models found in the literature, and exporting in .n2p format to be used in the Network design tool. In addition, these models are available in the Net2Plan library so that can be used by users in their own algorithms directly. For more information, check the class com.net2plan.libraries.TrafficMatrixGenerationModels in the Javadoc.
Selecting Traffic matrix design under Tools menu activates the Traffic generation window. This interface allows the user to generate a .n2p file representing a traffic matrix. Fig. 5.15↓ displays the workspace window for this option.
Figure 5.15 Traffic matrix design window
The Traffic design window is divided into four different parts:
The user initiates the process by selecting the number of nodes in the network using the Resize option. The traffic matrix will be like this:
where and are the node identifiers. Self-demands are not allowed ( = 0).
Next, the user has two options: to introduce values manually, or to use traffic generation patterns. Also you can open an existing .n2p file to edit it, or reset to all-zero matrix. Multiple traffic matrices can be edited at the same time.
Finally, the user can save it into the file system with the Save this (or Save all) button.
Now, the user can apply an automatic normalization of the matrix. Three types of normalization methods are implemented: total, row and column normalization [3]. The first adjusts the traffic matrix so that the total traffic offered to the network matches a user defined value. The second (third) modifies the matrix so that the -th row (column) of the matrix sums , being () a vector defined by the user. Note that this means that the total traffic transmitted (received) by node is fixed to exactly . More formally:
Total normalization: the sum of matrix elements have to be the value of total offered traffic, by following the next expression:
where is the normalized traffic and is the original traffic matrix.
The user introduces the total offered traffic volume in a popup.
Row normalization: the sum of each traffic matrix row have to be the value that the user introduces in a popup.
Column normalization: the sum of each traffic matrix column have to be the value that the user introduces in a popup.
After this, the user can select one of the traffic generation patterns among the five modes available: four of them are simpler, and based on the uniform distribution.
Uniform (0, 10): Generates a traffic matrix with random values in the range (0,10)
Uniform (0, 100): Generates a traffic matrix with random values in the range (0,100)
50% Uniform (0, 100) & 50% Uniform (0, 10): Generates a traffic matrix with 50% of its entries with random values in the range (0,100), and the rest of the entries with random values in the range (0,10)
25% Uniform (0, 100) & 75% Uniform (0, 10): Generates a traffic matrix with 25% of the entries with random values in the range (0,100) and the rest of the entries with random values in the range (0,10)
Please note at the end of this process diagonal values of traffic matrix are zero, since self-demands are not allowed.
Figure 5.17 Uniform traffic models
5.3.4 Traffic generation: population-distance traffic model
The fifth mode allows creating a traffic matrix according to the model described in [3]. This latter model applies the information of node position, population and node level, present in a topology information table (user can load a topology from a .n2p file). The distribution based on populations and distances follows the next expression:
where is a two-dimensional matrix (: number of levels or node types defined by the user). This matrix allows us to introduce asymmetric traffic in the traffic generator; is the population of the node ; is the maximum population; is a matrix (: number of nodes) with the distances between nodes; is the maximum distance.
In a real-world environment, network conditions vary during its operation, according to different phenomena. Failures in nodes and links, establishment of virtual circuits, or variation in traffic volumes are some examples. In this case, users could be interested in analyze how their networks can react to those changes and how their designs are consequently adapted for it.
Net2Plan provides three post-analysis simulation tools:
The Resilience simulator (see Section 5.4.1↓) permits evaluating the availability performance of protection and restoration algorithms in the network.
The Connection and Admission Control (CAC) simulator (see Section 5.4.2↓) is targeted to analyze the performance of on-line provisioning schemes that allocate resources to incoming connections (e.g. virtual circuits requests, lightpath requests, multimedia sessions…).
The Time-varying traffic simulator (see Section 5.4.3↓) is devoted to analyze the performance of dynamic allocation algorithms which reacts to variations in traffic demand volumes. Allocation is not only referred to modify traffic routing, but also it means that the network topology may change along time (i.e. adding new links)
The architecture of the three simulators is similar, based on the well-known discrete-event simulation paradigm. The network operation is modeled as a discrete sequence of events in time. Each event occurs at a particular instant in time and marks a change of state in the system [6]. Between consecutive events, no change in the network occurs; thus the simulation can directly jump in time from one event to the next.
The basic event-driven simulation model is illustrated in Fig. 5.19↓. The Event Generator creates events according to a given algorithm (which can be from the built-in ones or user-made), and deposits the ordered events in the event list in the Kernel. The scheduler in the Kernel steps through the event list in chronological order according to the global simulation time clock, calling the Event Processor (which can also be user-made) to each event. Then, the Event Processor reacts to the event taking some actions, which are processed by the Kernel to update the network state. Statistics are collected by the Kernel during the simulation.
Regarding to the statistics collection, the Event Processor interface provides a method so-called finish which can be used to collect technology-specific statistics.
Figure 5.19 Event-driven simulation model
Important: Current version of Net2Plan only allows simulation of single layer designs.
This tool simulates the network operation, where failures and links and nodes randomly appear according to the user-defined availability information of the network nodes/links. Allows testing built-in or user-made provisioning algorithms, that react to failure/reparation events from an initial network design. Network and service availability results are collected and reported to the user.
The simulation is based on the shared risk group (SRG) concept (see Section 3.1.8.1↑). A SRG is a set of links and/or nodes that are assumed to share a potential cause of malfunction. Thus, when this malfunction occurs, all of the elements in the SRG fail simultaneously. Users can define the SRGs in the network, according to their identification of the resources that are subject to fail (nodes, links, bidirectional links...). For each SRG defined, the mean time to fail (MTTF) and mean time to repair (MTTR) information is provided. The event generator is in charge of generating SRG failure/reparation events, while the event processor receives single node/link failure/reparation events and can take some actions: reroute traffic or restore primary route.
While Net2Plan provides some modes to generate SRGs from a network design, users are able to define their own SRG models. To do so, users should define an attribute srgs in every node or link in a SRG, and indicate the associated SRG identifiers (a node/link can be in zero or more SRGs) separated by spaces. To define the MTTF (or MTTR) per SRG, users should define an attribute mttf (or mttr) with the corresponding values separated by spaces.
For more information about implementation details check the com.net2plan.interfaces.resilienceSimulation package in the Library API Javadoc.
Selecting Resilience simulation opens the corresponding window. The workspace of the window is divided into three areas, in a similar way to the network design mode: input data, execution and reporting (right area), plot area (top-left area), and simulation controller and information area (bottom-left area).
With this panel, users are able to execute simulations and view the current state of the network. In the Execution controller, users can load network designs and execute simulations. To execute a resilience simulation user has to specify the following things:
Network design: a .n2p file with a previously computed and saved network design. The design must be complete: nodes, links, capacities, demands and routes (and optionally, protection segments). The current version of Net2Plan only allows single layer simulations.
Simulation parameters: general parameters for the simulation (SRG model, total events to simulate...). Each parameter has a default value that the user can change. Now, two special-meaning parameters are commented:
“disableStatistics”: In some occasions, users might be interested in collecting only their own statistics, and they might want to eliminate the (large) overhead that requires statistics collection. This can be done with this parameter. In this case, kernel statistics will present zero-valued results, while algorithm-specific statistics are shown.
“omitProtectionSegments”: As stated in Section 3.1.5↑, protection segments reserve a certain amount of bandwidth to provide (partial) backup-paths for primary routes. However, in some situations, users might be interested in execute their simulations assuming that no protection segments are defined. If this parameter is set to true, then protection segments are removed from the network plan just before the simulation starts.
Failure/reparation event generator: a Java code, implementing the event generator to be employed. This is the class in charge of generate SRG failure/reparation events. Optionally, if the selected event generator requires specific parameters, they are shown in a table. Again, each parameter has a default value that the user can change.
Provisioning algorithm: a Java code, implementing the event procesor to be employed. This is the class in charge of react to node/link failure/reparation events. Optionally, if the selected event generator requires specific parameters, they are shown in a table. Again, each parameter has a default value that the user can change.
During the simulation, users are able to save the current network state using the option Savecurrent state as a network plan.
Important: Once the simulation is started, no one of the above things can be changed. Users should reset the simulation to perform changes.
In this panel users can control the execution of the simulation. There are the classical Run, Pause-Continue, Stop and Reset controls, and also a Step button to execute the simulation event by event. Aditionally, users can add manually their own failure/reparation events.
Also, in this panel is shown some brief information about the simulation state: simulation time, CPU time, last event processed and corresponding actions... This simulation is updated according to the refresh time parameter, which can be configured before the execution, and the checkbox Refresh, which enables/disables the update even though the timer is configured.
Finally, users can also take a look on the future events by clicking in the View FEL (Future Event List) button.
In the View current network state tab, users can see information about the network state. Optionally, users can also show the same information (gray-shaded) as it was in the network design, for comparisons. Routes are shaded in yellow when correspond to a rerouted path but carrying the same traffic as the primary. If there are losses, then rows are shaded in red. In addition, rows corresponding to nodes and links that are down in the current state are shaded in red, and also painted in red in the topology canvas.
If user clicks in a route, then in the topology canvas the planned and current routes are shown. The former with lines, and the latter dashed.
In this panel, users can obtain the availability statistics collected by the kernel, and also those collected by the provisioning algorithm (if any). Users can see the report in any moment during the simulation, and can be viewed in a web browser, as reports for network designs.
Similarly to the reporting tool into network design, here user can select a report to apply to the network state. Upon selection and clicking Show the report is shown in the bottom part. Users can see it in a browser using the option View in navigator.
This post-analysis tool simulates the network operation, where traffic demands are the source of connection requests. This permits testing the performances of built-in or user-defined CAC (Connection-Admission-Control) algorithms, that block the connections or allocate them (deciding their route). For each traffic source, the requested connections duration, reserved capacity and interarrival time can be user-defined following different patterns (also built-in or user-defined). Network performances like connection blocking measures are collected and reported to the user.
The event generator is in charge of generating connection requests (arrival time, requested traffic volume, holding time), while the event processor decides whether or not is accepted (and if commit all the requested traffic volume) and can take some extra actions: release existing connections, vary traffic volume... Also, it can react to connection release events and can take other actions.
For more information about implementation details check the com.net2plan.interfaces.cacSimulation package in the Library API Javadoc.
Selecting Connection-admission-control simulation opens the corresponding window. Since the interface is similar to that in the resilience simulation, we only refer to the main features of this tool.
Here, the changes are with respect to the event generator and processor. In this case, the simulator has a connection event generator in charge of generate connection requests, and the CAC algorithm in charge of process events and take some actions.
In the View current network state tab, users can see information about the network state. Optionally, users can also show the same information (gray-shaded) as it was in the network design, for comparisons. The difference here is that routes only represents the planned state, while connections represents the active connections, which are modified with arrives and departures.
This post-analysis tool simulates the network operation, where traffic demand volumes vary with time according to a user-defined pattern. It is targeted to evaluate the performances of built-in or user-defined schemes that react to traffic variations (i.e. traffic rerouting schemes, on-demand capacity-provisioning schemes, etc.). Here, collected statistics are referred to the average network state during the simulation (link capacities, utilization, protection degrees...).
The event generator is in charge of modify the current traffic volume per demand at periodic intervals, while the event processor take other actions: add/remove links, reroute traffic demands, and so on.
For more information about implementation details check the com.net2plan.interfaces.timeVaryingTrafficSimulation package in the Library API Javadoc.
Selecting Time-varying traffic simulation opens the corresponding window. Again, since the interface is similar to that in the resilience simulation, we only refer to the main features of this tool.
Again, there are changes with respect to the event generator and processor. In this case, the simulator has a traffic change generator in charge of generate period changes in the traffic volume per demand, and the allocation algorithm in charge of allocate this varying traffic volume taking any required action.
In the View current network state tab, users can see information about the network state. Since changes are made directly over the original network design, the comparison planned-current makes no sense.
Contrary to the GUI, the command-line interface allows users to make use of batch processing or large-scale simulation features, thus it is specifically devoted to in-depth research studies. As stated before, all features available for GUI mode are also available here.
The execution is controlled via command-line arguments. To run Net2Plan in CLI mode, users must execute the following command in a terminal:
java -jar Net2Plan-cli.jar [more options]
Help information can be obtained through the help argument in the following ways:
To obtain a brief information, including only the execution modes, users should execute the CLI without arguments: java -jar Net2Plan-cli.jar
To obtain the complete information, including invidual help for every execution mode, users should execute: java -jar Net2Plan-cli.jar --help
To obtain the information about a certain execution mode, users should execute: java -jar Net2Plan-cli.jar --help mode-name
Then, help for the selected mode is shown. All commands and options are self-explained there.
Anyway, we show here some examples:
To execute the FA_shortestPath algorithm for the NSFNet network and its reference matrix: java -jar Net2Plan-cli.jar --mode net-design --input-file workspace\data\physicalTopologies\NSFNet_N14_E42.n2p --traffic-file workspace\data\trafficMatrices\NSFNet.n2p --output-file workspace\data\NSFNet.n2p --class-file workspace\BuiltInExamples.jar --class-name com.net2plan.examples.netDesignAlgorithm.fa.FA_shortestPath --alg-param shortestPathType=km
To execute the delay report over the previous design: java -jar Net2Plan-cli.jar --mode report --input-file workspace\data\NSFNet.n2p --output-file workspace\data\report.html --class-file workspace\BuiltInExamples.jar --class-name com.net2plan.examples.reports.delay.ReportDelay --report-param hurstParameter=0.6
To generate a series of 4 10x10 traffic matrices using a (0, 100) random uniform model: java -jar Net2Plan-cli.jar --mode traffic-design --num-nodes 10 --traffic-pattern uniform-random-100 --output-file workspace\data\trafficMatrices\tm10nodes.n2p --num-matrices 4
New: ’Network design’ is able to execute multilayer algorithms
Minor changes
Net2Plan 0.2.0 (March 18, 2013)
Initial Java version, many major changes from latest MATLAB version
In its very early stage Net2Plan was designed as a MATLAB toolbox. From version 0.2.0, previous MATLAB versions were discontinued, thus backward-compatibility is not ensured at all. However, interested users can found them in the website.
Net2Plan tool has its origins in 2011, during the preparation of the teaching materials for two new Communication Networks Planning courses at Universidad Politécnica de Cartagena (Spain) taught by Prof. Pablo Pavón Mariño:
“Telecommunication networks theory” (2nd year, 2nd quarter, “Degree in Telematics Engineering” and “Degree in Telecommunication Systems Engineering”
“Network planning and management” (3rd year, 2nd quarter, “Degree in Telematics Engineering”)
Net2Plan is also a part of the Ph.D. work of José Luis Izquierdo Zaragoza, supervised by Prof. Pablo Pavón Mariño.
Aside from Net2Plan, authors also collaborate in the development of MatPlanWDM, an open-source tool for multilayer optical networks. In addition, Prof. Pablo Pavón Mariño develops JOM, an open-source Java library for modeling and solving optimization problems in a simple MATLAB-like syntax.
Net2Plan defines a network representation based on abstract concepts such as nodes, links, routes, traffic demands and network layers, without relying on any network technology. This is the key idea that allows Net2Plan to not be constrained by any particular network technology, and is, thus, applicable to any and all of them. To achieve such functionality, we define a data storage called network plan (class com.net2plan.interfaces.networkDesign.NetPlan in the Net2Plan library) which contains all the current state of the network design, so every algorithm receives a network plan and returns a modified network plan.
In this section, we provide the theoretical framework that is behind Net2Plan philosophy, and the (common) notation we use to characterize the network, topology, routing, etc.
In Net2Plan a network topology is defined as a graph , where is the set of nodes and is the set of links. The number of nodes and links are the cardinality of sets and , which are and , respectively. Network topologies are considered as multi-digraphs. This means that every link is unidirectional (directed graph or digraph), and that network topologies can have multiple links between the same node pair. No self-links are allowed.
Given a link , denotes the initial node of the link, and denotes its destination node. We use to denote the link length (measured in km). Given a node , is the set of outgoing links from () and is the set of incoming links to (). In Fig. A.1↓ an example of network topology is shown.
Figure A.1 Topology with = 3 nodes, , = 3, . End nodes of are and . Outgoing links from node are , and the incoming one is
Each link in a network has associated a real number which represents its capacity. The capacity is the amount of traffic the link is able to carry. Thus, capacities and traffics are measured in the same units. Unless stated otherwise, the traffic and capacities in Net2Plan are measured in Erlangs.
For the sake of simplicity, we denote the set of link capacities as a vector . In addition, the carried traffic by link is denoted by . The vector represents the traffic carried in all the links in the network.
Typically, link capacities are limited to a discrete range of values due to technological reasons, such as STM- carriers in SDH. In these cases, capacities are referred as modular capacities.
Traffic is modelled through a set of demands (or commodities) . Each demand represents an offered traffic flow to the network. In general, the traffic of a demand can have one or more ingress nodes in the set , and one or more egress nodes denoted by the set ; however, in current version of Net2Plan demands are considered unicast. This means that each demand has one ingress node and one egress node, thus . In addition, self-demands are not allowed.
The offered traffic by a demand is represented as . Such value is measured in the same units as link capacities (i.e. Erlangs). In some situations, it is not possible to carry all the offered traffic by the demands. Then, represents the amount of traffic belonging to demand that is carried. In their vector form, and represent offered and carried traffic, respectively.
Given a network topology , a path is an ordered sequence of links , such that the destination node of a link is the origin node of the following link . The set of all possible paths in a network is denoted as . The first node of the path is the origin node of the first link , and the last node in the path is the destination node of the last link . Finally, given a link , is the set of paths which traverse the link . For example in Fig. A.2↓, given and , . In addition, is the number of hops in path .
Figure A.2 Topology with = 4 nodes, , = 4 links,
In Net2Plan, the routing is internally represented in the form of demand-path variables. Formally, for each demand in the network, a set of paths is defined between the end nodes of the demand (, ). Also, given a path , the demand that the path is linked to is denoted as . Then, traffic routing is represented by a vector where is the traffic volume carried through the path for demand . Note that we define a path as a sequence of links that carry traffic of a specific demand . If two demands exist between the same end nodes, and the traffic of both demands is carried through the same sequence of links, we consider in Net2Plan that the routing is composed of two paths with the same end nodes, one for each demand, so that .
According to the notation used to define the network routing in Net2Plan, the following relations hold:
where Eq. ↓ implies that the traffic carried by a demand is the sum of traffics in the paths assigned to that demand, and this amount is upper bounded by the offered traffic by the demand, while Eq. ↓ reflects the fact that the traffic in a link is the sum of the traffic in the paths traversing that link, and is constrained (in general) to be limited by the link capacity.
The set of all possible protection segments in a network is denoted as . The first node of the protection segment is the origin node of the first link in the original route which is not in the protection segment, and the last node in the protection segment is the destination node of the last link which is in the original route and not in the protection segment. A link may be associated to several protection segments, which is denoted as . Finally, given a path , is the set of protection segments which protect the path . In addition, is the number of hops in protection segment .
Protection segments resemble “virtual links”, in the sense that a protection segment have a reserved bandwidth (may be zero, too) and this bandwidth (or capacity) can be shared by several traffic routes. For example, if a protection segment has reserved 10 Erlangs and a route is using 5 Erlangs, still there is 5 Erlangs available for other routes.
In this section several performance metrics are described. These metrics are useful to define objective functions or problem constraints. Notation is based on that presented in Appendix A↑.
Link utilization: It is equal to the carried traffic by the link and the total reserved bandwidth by protection segments associated to the link, all divided by the link capacity
Network congestion (or bottleneck utilization): Maximum load among all links
Throughtput (Erlangs): Total traffic injected to the network
Total in-network carried traffic (Erlangs): Total traffic traversing the network
Average number of hops
Average ingress -and egress- traffic per node (Erlangs)
Average traversing traffic per node (Erlangs)
Bifurcation degree: Average number of paths carrying traffic per each demand
In packet-switched networks, traffic sources split data into smaller pieces called packets, along with a header with control information. Per each received packet, switching nodes read its header and take appropriate forwarding decisions.
In real networks, traffic is highly unpredictable and often modelled as random processes. When it is said that a traffic source generates traffic units, it is referred as average traffic. As a result, link capacities would be not enough to forward traffic and nodes have to store packets in queues, so they are delayed until they can be transmitted (this delay is known as queuing delay). If this situation remains for a long time, queues are filled and links become saturated, provoking packet drops.
Network design tries to model statistically delays and drops in order to minimize their effects. In Net2Plan each link is modeled as a queue fed by a self-similar source with a given Hurst parameter, getting the whole network average delay using Kleinrock’s independence assumption [15].
Propagation delay per link (seconds)
where is the speed of light when traverses link
Transmission delay per link (seconds)
where is the average packet length (in bits), and is the capacity in bits per second per one Erlang
Buffering delay per link (seconds)
where Hurst Parameter. Choosing yields to same result as that predicted by M/M/1 queue model
In circuit-switched networks, traffic sources reserve a given capacity during certain time, along paths followed by traffic demands. It is possible that if a new traffic source wants to reserve resources its petition would be blocked, since it would not be enough available resources to satisfy its demand. Here, theload-sharingmodel is applied [16, 17]. According to this model, each connection request from a demand chooses randomly a path among the paths in . The probability of choosing a path is proportional to the traffic carried, and given by . After choosing the path , the connection is accepted if all the links in have enough spare capacity. If not, the connection is blocked. This means that there is no attempt to carry the connection in other possible routes in . This is the distinguishing trait of this model. Note that thanks to this assumption, there is no overflow traffic in the network (traffic offered to a route, that if blocked, and overflows to an alternate route).
It is assumed that arrivals of connection requests to each link are Poisson processes, independent link-by-link. Therefore, blocking performance metrics can be computed using Erlang-B formula. Obviously only has sense when link capacities are integer.