With the emergence of small cell networks and fifth-generation (5G) wireless networks, the backhaul becomes increasingly complex. This study addresses the problem of how a central SDN orchestrator can flexibly share the total backhaul capacity of the various wireless operators among their gateways and radio nodes (e.g., LTE enhanced Node Bs or Wi-Fi access points). In order to address this backhaul resource allocation problem, we introduce a novel backhaul optimization methodology in the context of the recently proposed LayBack SDN backhaul architecture. In particular, we explore the decomposition of the central optimization problem into a layered dual decomposition model that matches the architectural layers of the LayBack backhaul architecture. In order to promote scalability and responsiveness, we employ different timescales, i.e., fast timescales at the radio nodes and slower timescales in the higher LayBack layers that are closer to the central SDN orchestrator. We numerically evaluate the scalable layered optimization for a specific case of the LayBack backhaul architecture with four layers, namely a radio node (eNB) layer, a gateway layer, an operator layer, and central coordination in an SDN orchestrator layer. The coordinated sharing of the total backhaul capacity among multiple operators lowers the queue lengths compared to the conventional backhaul without sharing among operators. emerged as a critical bottleneck of novel high-capacity wireless networks, such as small cell networks and 5G networks [1] [2] [3] [4] [5] [6] [7] . Recently, Software-Defined Networking (SDN)-based backhaul architectures have been proposed to flexibly interconnect the backhaul networks of the different operators in a centrally controlled manner, as reviewed in detail in Section 2. The central SDN control enables the dynamic on-demand sharing of the backhaul resources among the various operators. Thus, sudden demand surges for backhaul capacity from the radio nodes (e.g., LTE eNBs and Wi-Fi APs) of one operator may be served by sharing the backhaul capacities of the various operators. Of course, aside from the technical capabilities, appropriate legal and business agreements need to be in place between the operators to make the sharing practically feasible and economically advantageous. The SDN-based control of the backhaul resource sharing poses two main challenges. First, the aggregate of multiple operator networks with all their radio nodes and subscribing wireless devices considered by the central SDN orchestrator can be very large; thus posing scalability challenges. Second, the central SDN orchestrator that coordinates among multiple operators may be far removed from the distributed radio nodes resulting in long signaling delays and accordingly slow reactions to dynamic demand variations at the radio nodes. Thus, purely centralized optimization is not practical for backhaul networks. Rather, distributed optimization strategies are needed for operating large backhaul networks. Network optimization that operates on distributed systems has so far had two flavors: (i) peer-to-peer optimization for a flat (i.e., not layered) system and (ii) Network Utility Maximization (NUM) [8] [9] [10] [11] which employs dual decomposition to distribute computations across different terminals that share the network resources. The dual decomposition leads to a master-slave model, where each user (slave) needs to directly interact with the SDN controller (master). The main benefit of operating the NUM is that the SDN controller simply passes the dual variable iterates, and the slaves pass only their demands (while locally monitoring their constraints). Thus, the SDN controller does not need to know all the details of the users and yet, can solve the global optimization problem. However, for large backhaul networks, it is not practical for the numerous eNBs to directly interact with the central SDN controller, as the NUM dual decomposition would require. Essentially, the well-researched NUM dual decomposition models are incompatible with the multiple layers in large practical backhaul network architectures. This article presents a generalization of the NUM framework using auxiliary variables to make NUM modeling compatible with the multiple layers in layered backhaul network architectures. More specifically, we decompose the global optimization that the central SDN orchestrator is trying to solve, through formulation of a multi-layer NUM. Moreover, we include a virtual queue framework in our formulation to allow the SDN orchestrator to comply to long-term agreements. Our formulation strives to optimize the sharing of backhaul resources in an SDN-based backhaul network architecture. In particular, this case study is conducted in the context of the recently proposed LayBack backhaul network architecture [12] . LayBack, as reviewed in more detail in Section 3, introduces layers for the different wireless network components, including layers for wireless devices, radio nodes (e.g., eNBs, Wi-Fi APs), and gateways (e.g., small cell gateways, LTE gateways). LayBack interconnects the gateways through an SDN switching layer in a full mesh with the respective core network entities (e.g., the LTE Enhanced Packet Core (EPC)) of the various operators. The gateways and core network entities of the various operators as well as the SDN switching network are under the control of a unifying SDN orchestrator. The LayBack backhaul architecture provides centralized fine-grained tuning knobs to optimize the backhaul operation, e.g., to share backhaul capacity among the different operators in a dynamic fashion. Our layered iterative optimization formulation distributes the optimization computations over the LayBack layers. We conduct numerical evaluations with the formulated optimization to quantify the performance gains that the optimized backhaul Electronics 2019, 8, 937 3 of 28 resource sharing in the SDN-based LayBack architecture achieves compared to the conventional non-SDN backhaul. Background and Related Work The SDN paradigm with a control plane that is separate from the data plane and with a centralized SDN controller has spurred significant research interest in wireless networks [13] [14] [15] . An extensive set of studies have developed SDN-based architectures for the backhaul of wireless network traffic [16] [17] [18] . Given the complexity of the backhaul, most of this work has considered layered or tiered architectures [12, [19] [20] [21] [22] [23] [24] , whereby intermediate gateway nodes perform various protocol related functions [25] [26] [27] [28] . For instance, there may be gateway nodes that interface with Internet of Things nodes [29, 30] or specific wireless network technologies, such as wireless local area networks [31] . Moreover, the efficient interconnection via metropolitan area networks to the Internet at large has received increasing attention [32, 33] . This case study considers the LayBack architecture [12] which can encompass the layering structures of a wide range of other proposed architectures and wireless technologies while allowing for fine-grained SDN control, as elaborated in Section 3. The enabling idea is the generalization of the decomposition approach referred to as network utility maximization (NUM) to a multi-tier system. Kelly et al. [8] introduced the NUM concept to solve the problem of rate allocation in a network with link capacity constraints. Extensive follow-up studies have analyzed the NUM concept in the contexts of distributed optimization and stochastic network theory [9] [10] [11] . For instance, Tassiulas and Ephremides [34, 35] analyzed Queue length Maximum Weight (QMW) scheduling, which facilitated the subsequent analysis of throughput optimality conditions and related performance guarantees [36, 37] . However, QMW scheduling does not guarantee minimal delay [38] , which has led to investigations of QMW variations that reduce delays in general multi-hop networks [39] or provide better delay guarantees [40, 41] . A common shortcoming of these optimization models is that a centralized optimal scheduler can be impractical, mainly due to scalability problems and signaling delays. Decompositions of NUM models can provide the desired implementation scalability to a certain extent. The existing NUM model decompositions strictly conform to a master-slave architecture, which means that these decompositions do not truly reflect the many intermediate layers that exist between the edge devices and the core network in large-scale wireless networks. Furthermore, NUM model decompositions commonly build on the so-called timescale separation assumption [42, 43] , which states that the session interval is much longer than the convergence time of the greedy resource allocation policy [11] . With the timescale separation assumption, the decomposition neglects the convergence of the local control. Building on the timescale separation assumption, decentralized algorithms for link scheduling based on queue lengths have been proposed in [44] [45] [46] . Our multi-layer multi-timescale NUM framework contains two innovative aspects. First, rather than having a single central master (or single master layer), we consider four decomposition layers that include the SDN controller at the backhaul, the operators, the network gateways, and the eNodeBs. Second, we consider realistic network signaling latencies for the decomposition of the QMW utility over the LayBack architecture layers. The signaling delays make the timescale separation assumption unrealistic. Generally, there have been two categories of studies that have examined the removal of the timescale separation assumption: (1) studies that use intermediate iterates as decisions and assume continuous underlying flows [47, 48] , and (2) studies that use a multi-timescale approach across different layers of the protocol stack [49, 50] . More specifically, the study [47] showed that a β-fairness utility function can be maximized, while guaranteeing system stability, under the assumptions that the number of users per class follows a recurrent Markov Chain. We follow
In REF , the authors present a flexible way to optimize network resources sharing among wireless operators and nodes across the network by using gradient methodology.
A Multi-Layer Multi-Timescale Network Utility Maximization Framework for the SDN-Based LayBack Architecture Enabling Wireless Backhaul Resource Sharing
Electronics
Engineering