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 traffic 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 based on configurable link weights.
The open shortest-path first (OSPF) protocol and the intermediate system to intermediate system (IS-IS) are the most common shortest-path based 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 absence 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. The most widely utilized technique to improve loading is known as Equal-Cost Multipath (ECMP) . If, at a node, there are several shortest paths to a destination, then the node divides the traffic targeted to the destination evenly among all the outgoing interfaces associated to one of the shortest paths to the destination.
In Net2Plan, 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 by 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 and GraphUtils libraries (see Library API Javadoc), allows interoperation between these schemes. The IPUtils library permits assigning weights to the links, representing its weight in an IGP. Weights are actually stored using a link attribute so-called linkWeight. While IGP standards recommend to use integer values, we relax this limitation and allow double values, even though we also discourage users from using fractional values. Once link weights are defined, IPUtils permits computing the routing tables produced if the network was using a standard OSPF routing with Equal-Cost Multipath (ECMP). The form in which this library produces and handles routing table information in the form of a \( f_{te} \) double 2D array. For each destination node \( t \) in the network, \( f_{te} \) contains the fraction of traffic targeted to \( t \) that arrives or is generated by node \( a(e) \) (the initial node of link \( e \), that is forwarded through link \( e \). Please note that for every destination \( t \), \( f_{te}=0 \) for every outgoing link \( e \) from node \( t \).
As a result, \( f_{te} \) contains the information of all the routing tables of all the nodes in the network. The routing table of a node \( n \) is extracted from the \( f_{te} \) values for the links \( e \) outgoing from \( n \). The GraphUtils library in Net2Plan provides functions to manipulate routing tables (\( f_{te} \)), and convert them to/from other routing representations like a set of origin-destination routes that can be inserted into a NetPlan object. Also, the IPUtils library provides a method to automatically configure the routing in a netPlan object, as the one that would occur if all the nodes were IP routers, with routing tables given by a \( f_{te} \) representation. Finally, IPUtils also permits doing the opposite operation: given a netPlan object with a set of routes, produce the routing table in the nodes that is compatible with those routes. In this case, the operation will fail if the routes in the netPlan object are not compatible with a destination-based routing, and thus the routing cannot be reproduced in an IP network as is. Also, if in the original routing a node \( n \) does not forward traffic to a particular target node \( t \), it is not possible to determine the \( f_{te} \) fractions for the output links of the node. Then, it is arbitrarily assumed that node \( n \) would forward the 100% of the traffic to node \( t \), through the shortest path (in number of hops) from \( n \) to \( t \).
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 and GraphUtils library in the Javadoc. In addition, network design algorithms and other resources for designing IP networks can be found in the Net2Plan code repository under keyword IP.
