## 2 Backhaul Design as a Graph Optimization Problem
### Backhaul Design Method  
Our approach offers an extensible method for backhaul design, which means that additional constraints or objectives may be represented through the incorporation of new invariants to the graph optimization problem. The development of new graph invariants increases the power of our approach to backhaul design in the direction of capturing desirable topological properties. For instance, it is possible to design backhaul networks that prioritize power minimization or energy consumption, whenever these physical quantities can be expressed by appropriated graph invariants.  
Table 1 summarizes the above discussion by showing the mapping of some common network features into graph invariants.  
Figure 1 presents our proposed method. The first step is to define the network requirements that will guide the topology design (e.g., low latency, resilience, and nodes have up to four communication interfaces). Then, these requirements are mapped into graph invariants that are described in the literature. For instance, average latency can be mapped to average distance, and the maximum number of interfaces can be mapped to maximum node degree. If it is possible to map all the requirements, then the next step is to create an optimization model. Otherwise, it is necessary to design new invariants that can capture the outstanding network requirements. One example is the design of the Wiener impact invariant, described in the previous section, for capturing the resilience requirement.  
When all the requirements are mapped, it is possible to define constraints and objective functions in terms of graph invariants. For example, the problem of finding a resilient network with low latency, where nodes have a maximum of four communication interfaces, could be stated as: minimize the Wiener impact and the average distance, subject to a 2-connected graph of maximum degree less than or equal to four. Finally, this graph optimization problem can be solved using a integer linear programming (ILP) method or heuristics. In our case, we use Variable Neighborhood Search (VNS) heuristic with the help of the AutoGraphX III (AGX) software [32; 35], as explained in the next section. The result of this optimization process is the interconnection topology itself.  
After defining a candidate topology that meets the defined network requirements, one may run other optimization steps to guarantee capacity allocation using the topology and the traffic matrix as inputs. For example, the problem may be stated as the minimization of the operational cost  
\begin{table}
\begin{tabular}{c c} \hline \hline
**Feature** & **Invariant** \\ \hline Cost & Order, size, and maximum/average degree \\ Maximum latency & Diameter \\ Average latency & Average distance \\ Network congestion & Edge betweenness, and degree variance \\ Survivability & 2-connectivity \\ Resilience & Node Wiener impact \\ \hline \hline \end{tabular}
\end{table}
Table 1: Network requirements and invariants.  
represented by bandwidth usage or processing power. Afterwards, this solution can be tested in a prototype, simulated or emulated environment, and analyzed against a set of network metrics (e.g., flow completion time and traffic distribution among nodes). If the results are satisfactory, the solution may be deployed in production networks. Otherwise, it may be necessary to redefine the network requirements and execute the design method of Figure 1 again.