Node capacity optimization and simulation

Router dimensioning is an important part of the network design process from the cost perspective, especially for metropolitan and regional networks. Depending on the type of routing machinery chosen, the throughput of the network may vary substantially. We want to re-assess the installation of node capacity in a given network after the decisions on edge capacity have been partly made and implemented.

A network is given as a graph G=(V,E) where edge capacities c_{ij} for each \{i,j\}\in E are given as input and are bidirectional. There are two technologies available for network nodes, which are not mutually exclusive — one can install both at a node:

  1. Cost: $1500/unit. It can be connected with 25 capacity units, but there cannot be more than two per node;
  2. Cost: $4000 for a node setup plus $40 for each link capacity unit connected to it, with no limit on the number of links connected to it.

As a further constraint, every node admitting at least an originating demand cannot have more than one unit of technology 1.

The purpose of this project is to find the minimum cost node configuration that allows the network to route a given set Q of traffic demands, each defined by the triple (s_q,t_q,d_q).

The simulation part consists in modeling a simple network where the two technologies have different behavior: in technology 1, a node has the same queue structure as the node we saw in class, with a maximum rate at the routing block given by R Mb/s, while technology 2 has virtually no limit on the number of packet per second processed as each packet is directly transferred from the incoming link to the outgoing link.

Instance: See the Atlanta backbone network. This realistic instance has capacity and demands required for the problem. Note that the capacity is expressed in terms of units of 144 Mb/s (to be used as units for the node technology as well) while all demands are in Mb/s. Also, R=20,000\times 144 Mb/s.