## 2 Backhaul Design as a Graph Optimization Problem
### Mapping C-RAN Resilience Requirements to Graph Invariants  
Once the constraints of potential backhaul interconnection have defined a space, wireless objectives may be mapped into graph theoretic terms to guide a search. For example, the concept of betweenness of an edge \(e\) in a graph \(G\) measures the proportion of the number of shortest paths among all node pairs in \(G\) that pass through \(e\); as such, this invariant can be used as measurement of potential network congestion. As another example, since latency is fundamentally limited by propagation delay, the diameter and the average distance invariants provide the means to describe the fundamental latency performance of a network. Minimization of these invariants finds topologies with the highest potential for supporting wireless networks with strict latency requirements. On the usage of the betweenness invariant, the latency requirements for C-RAN, such as posed by the HARQ protocol, can be better managed defining the exactly topology, which would give the best survivability in case of backhaul overloads, preventing C-RAN to lose connectivity and performance. Alternatively, the resilience requirements of a wireless network can be described in terms of the effect of alterations to a topology. For example, traditional tree topologies lack fault tolerance due to collapse upon loss of any edge or non-leaf node. A need for survivability may be translated into the search for \(k\)-connected graphs, where the value of \(k\) is proportional to the level of backhaul fault tolerance required by the wireless network. Given the dynamic capabilities of C-RAN to readjust the RRHs workload distribution to BBU pools on the fly, changing the communication topology to achieve better fault tolerance is not just feasible, but is also required. Therefore, to enhance survivability, the C-RAN topology can be reconfigured online through different graph invariants to achieve better fault tolerance and resilience. By describing backhaul interconnection constraints and wireless objectives in this manner, our approach allows the refinement of existing topologies to address novel challenges. For example, the traditional ring topology is commonly used for its fault tolerance, but exhibits undesirable latency properties. Specifically, the ring topology has the maximum diameter of all 2-connected graphs with \(n\) nodes [29] and the diameter of a ring increases from \(\lfloor n/2\rfloor\) to \(n-1\) after the removal of any edge. Our approach proposes the refinement of the ring topology allowing it to be more suitable for supporting wireless networks with tight latency requirements. In this case, we may constrain our search space to contain only topologies with two disjoint paths for each pair of nodes, while minimizing the diameter of the resultant topology. To this end, we propose a new invariant called the node Wiener impact, which provides a measure for a 2-connected graph \(G\) of the impact on the distances between node pairs in the remaining graph when a node \(v\) is removed. This new node invariant is based on well-known invariants: the node transmission [29] and the graph Wiener index [26]. The Wiener index of a given graph is the half sum of its distance matrix, which represents the total number of hops that are necessary to interconnect all pair of nodes using the shortest path between them. If the load is homogeneously distributed among all the node pairs and the routing algorithm considers the shortest paths, this invariant gives an idea of the cost to route data in a network: the lower is the Wiener index, the more likely is a network to route data using fewer hops. The transmission of a node, on the other hand, is the sum of the distances from this node to all other nodes. In an ideal solution, all the distances remain the same after a vertex removal and, consequently, there are at least two disjoint geodesics interconnecting any pair of nodes.