Given the explosively growing traffic related to data-centric applications and AI, especially to and from the cloud, it is crucial to make the best use of the given resources of wide-area backbone networks (WANs). An intriguing approach to improve both efficiency and performance of WANs is to render networks more adaptive and "demand-aware", on the physical layer: innovative programmable wide-area topologies support dynamic wavelength assignments. This is enabled by the application of colorless and directionless Reconfigurable Optical Add/Drop Multiplexers (CD ROADM), and by leveraging the capabilities of software-defined controllers.

Most ISPs use sophisticated traffic engineering strategies based on link weight optimizations to efficiently provision their backbone network and to serve intra-domain traffic. While traditionally, traffic is split among the shortest weighted paths using ECMP, recently, an additional dimension for optimization arose in the context of segment routing: traffic can be steered away from congested shortest paths by inserting intermediate destinations, so-called waypoints.

More and more networks are becoming reconfigurable: not just the routing can be programmed, but the physical layer itself as well. Various technologies enable this programmability, ranging from optical circuit switches to beamformed wireless connections and free-space optical interconnects. Existing reconfigurable network topologies are typically hybrid in nature, consisting of static and a reconfigurable links. However, even though the static and reconfigurable links form a joint structure, routing policies are artificially segregated and hence do not fully exploit the network resources: the state of the art is to route large elephant flows on direct reconfigurable links, whereas the remaining traffic is left to the static network topology. Recent work showed that such artificial segregation is inefficient, but did not provide the tools to actually leverage the benefits on non-segregated routing. In this paper, we provide several algorithms which take advantage of non-segregated routing, by jointly optimizing topology and routing. We compare our algorithms to segregated routing policies and also evaluate their performance in workload-driven simulations, based on real-world traffic traces. We find that our algorithms do not only outperform segregated routing policies, in various settings, but also come close to the optimal solution, computed by a integer linear program formulation, also presented in this paper. Finally, we also provide insights into the complexity of the underlying combinatorial optimization problem, by deriving approximation hardness results.

More and more networks are becoming reconfigurable: not just the routing can be programmed, but the physical layer itself as well. Various technologies enable this programmability, ranging from optical circuit switches to beamformed wireless connections and free-space optical interconnects. Existing reconfigurable network topologies are typically hybrid in nature, consisting of static and a reconfigurable links. However, even though the static and reconfigurable links form a joint structure, routing policies are artificially segregated and hence do not fully exploit the network resources: the state of the art is to route large elephant flows on direct reconfigurable links, whereas the remaining traffic is left to the static network topology. Recent work showed that such artificial segregation is inefficient, but did not provide the tools to actually leverage the benefits on non-segregated routing. In this paper, we provide several algorithms which take advantage of non-segregated routing, by jointly optimizing topology and routing. We compare our algorithms to segregated routing policies and also evaluate their performance in workload-driven simulations, based on real-world traffic traces. We find that our algorithms do not only outperform segregated routing policies, in various settings, but also come close to the optimal solution, computed by a mixed integer program formulation, also presented in this paper. Finally, we also provide insights into the complexity of the underlying combinatorial optimization problem, by deriving approximation hardness results.