logo EDITE Sujets de doctorat

Scalable Online Algorithms for Software Defined Wireless Networks

Sujet proposé par
Directeur de thèse:
Encadré par
Doctorant: Nikolaos LIAKOPOULOS
Unité de recherche UMR 7102 Laboratoire de recherche d'EURECOM

Domaine: Sciences et technologies de l'information et de la communication


Software-Defined Networking (SDN) technologies are quickly gaining momentum in the networking industry. By separating the data plane from the control plane, they allow for quick & easy on-the-fly implementation of flow rules in the network routers and switches (see for example: Forces [1], PCEP [2] and OpenFlow [3]). Using such rules, network administrators can go beyond the standard MPLS approaches, engineer the network in a central manner by collecting data and dispatching router commands, and ultimately optimize resource utilization, cost, reliability, and other objectives. Due to this flexibility, SDN is a major technological driving force today. Huawei, is a leading contributor to the open-source ONOS platform for SDN [4], a leading constructor of networking equipment controlled by SDN, and also a technological leader in proposing new algorithms for network optimization. In the wireless domain, operators are struggling to keep up with the rapidly increasing mobile data traffic, while at the same time facing increasing costs to upgrade to the newer technologies (e.g., LTE/LTE-A) needed to alleviate this data crunch in the short term. As a consequence, the upcoming 5th Generation (5G) networks are considering a number of technological breakthroughs in order to provide the urgently required 1000x performance improvements in the long term. This vision includes aggressive densification (via femto-cells, pico-cells and relays), extensive carrier aggregation and offloading (between carriers and/or RATs), cooperation between BSs (such as Coordinated Multi-Point Transmission/Reception, and eICIC), and massive centralization of baseband processing, especially to facilitate cooperation and optimal resource allocation, in the context of CloudRAN [5]. While of high potential benefit, the above technologies also introduce significant additional complexity for the implementation, reconfiguration, and update of related algorithms. Softwarization and virtualization of the often ossified, highly complex, and expensive Radio Access Network (RAN) architecture via SDN is seen as a necessary step towards 5G networks, often referred to as Software Defined Wireless Networks (SDWN) [6,7]. Radio access, backhaul, and core network programmability will allow easy reconfiguration and tuning, flexible online adaptation of algorithms to react to traffic load shifts, context- and service-specific traffic handling, and the ability to optimally allocate resources when and where needed. Nevertheless, while centralization of network control increases the flexibility to handle different traffic flows at will, it also raises some performance and scalability concerns. Given the number of users, BSs, access technologies and (virtual) operators sharing a given network, taking all flow decisions at a remote, centralized SDN controller is prohibitive. Furthermore, classical SDN schemes control the network by deciding rules that apply to flows (sequences of packets). This flow-level approach has the advantage of being simple and easy to apply to network routers. Yet, wireless systems are extremely sensitive to time-variations of transmitted signals. Two subsequent packets in the same flow might encounter an entirely different electromagnetic environment. Hence, the benefits of specific optimization algorithms (as, for example opportunistic scheduling [8]) hinge on performing fast operations at packet-level. This might require a reaction from the local network at a time-scale that is much smaller than the time to send relevant information to and receive a decision from a central SDN controller. Summarizing, SDN promises to facilitate novel, optimal resource allocation algorithms for wireless networks, but wireless optimization is currently performed at a closed-loop involving the communication devices, and at the moment is seems impossible to include in this loop the SDN controller. The motivation for this PhD topic comes from exactly these tradeoffs. Specifically, the thesis has two key goals: 1) To model and understand the performance tradeoffs stemming from the combination of SDN with wireless networks, and the interplay between optimal flow-level rules at the SDN controller with dynamic optimization at packet-level in the wireless communication devices. 2) To use this understanding to propose an optimization framework for scalable online (semi-)distributed SDWN algorithms for efficient resource allocation and traffic steering in dense, heterogeneous 5G SDWNs. Objectives and research directions The main objective is to propose flow management algorithms that optimize performance along both short (packet-level) and longer (flow-level) time-scales, taking into account the dynamics of wireless networks and finding an optimal partition or placement of the algorithm between the SDN controller(s) and the local communication devices. Specifically, we will be using techniques inspired from the literature on online and distributed optimization, resource allocation, and decomposition algorithms, to explore the following main research directions: Coupled SDN flow-level rules with packet-level control of wireless channels In traditional wired networks, SDN abstracts the key features of the underlying topology and derives specific long-term traffic flow-based handling rules based on attributes like source-destination IP and port, protocol, etc. Unlike wired networks whose topology and link characteristics are very slowly changing, wireless networks are subject to considerable variability at very small time scales due to node mobility and rapidly changing channels, making performance dependent on a large number of additional and fast changing parameters. As a result, simply extending traditional SDN protocols (e.g. OpenFlow) to expose all possible parameters of the physical layer to the SDN controller would lead to major scalability problems. On the other hand, abstracting away too many of these details would lead to suboptimal performance of the rules devised at the central controller. As one example, implementing an LTE scheduler at a central controller would require to transport and process a very large number of rapidly changing information about the channel and queue sizes of different users. A key goal of this thesis is to understand the performance enhancements possible by (physically or virtually) centralized flow-level rules, based on a network view that is sufficiently abstracted to ensure scalability, but is aware of, facilitates, or modifies the local algorithms optimizing performance at packet level, towards better network-wide performance. We intend to model these tradeoffs and analyze the performance impact of different abstraction levels proposed in related literature [9], and utilize the theory of time-scale separation and decomposition-based distributed algorithms [10, 11] to devise an appropriate hierarchical and semi-distributed optimization framework for SDWNs. SDWN Traffic Steering 5G networks are expected to aggregate a number of different carriers (licensed and unlicensed), network tiers (e.g. macro-, micro-, pico-cells), and Radio Access Technologies (RAT), such as LTE or WiFi. In this complex environment, it becomes increasingly important to optimally and seamlessly (re-)associate users between to the different tiers, carriers, etc., as well as optimally allocating the resources of a given network (or carrier) among the users assigned to it. The former problem usually is referred to as user association and/or offloading, while the latter relates to scheduling. User association and offloading is often performed using Absolute Broadcasted or Dedicated Priorities [12] while scheduling algorithms, although varying between RATs and vendor implementations often aim to achieve a balance between spectral efficiency, fairness, and user-agreed QoS [13]. Nevertheless, in the above highly heterogeneous context, static rules for offloading [14] and simple, proportionally fair allocation scheduling algorithms lack the required flexibility and may lead to suboptimal performance. Our goal is to jointly study the problem of user association and scheduling as a larger resource allocation problem at different time-scales. Users will have to be distributed to the different carriers and networks on a longer time-scale (to avoid excessive handovers) and using a global view of the availability of various resources. On a specific resource (e.g. one carrier) resource blocks will have to be quickly reshuffled between associated users, on a much smaller time-scale, to exploit channel variations and react to instantaneous queue overloads. A useful analogy is that of task assignment and scheduling in clouds, and we’ll borrow from the extensive literature in this area, to appropriately address these problems [15].


Distributed vs Centralized Optimization of the SDWN Radio Access The considerable network densification will require complex interference management techniques to ensure good performance, especially for edge users. Distributed solutions will have a number of BSs coordinating their scheduling decisions (e.g. through Almost Blank Subframes [16]) or even their transmission/reception to/from the same UE (e.g. CoMP [17]) to improve performance. However, these schemes require the transmission of a large amount of channel and user information along the X2 interface and have to satisfy very stringent synchronization constraints to ensure good performance. For this reason, CloudRAN architectures that centralize baseband processing over a large number of BSs are gaining momentum. Such a centralized view enables wireless resources to be allocated when and where needed, and facilitates coordination techniques like the above. This centralized cloud emerges as a natural candidate for the placement of the SDN controller, which can be programmed to perform different interference management tasks at will. Nevertheless, the CloudRAN architecture requires an ultrafast fronthaul network to carry radio samples to and from the remote radio heads (RRHs). As a result, industry and researchers are revisiting the CloudRAN paradigm considering a more flexible and dynamic functional split between the BS and the central BBU pool [18,19]. Our goal will be to devise online algorithms that dynamically decide when and what type of processing to perform locally at the BS, and what centrally, in the BBU pool. These decisions take into account the traffic type, user characteristics and desired QoS, as well as the radio access, fronthaul and backhaul loads. The optimization algorithm should strike a tradeoff between appropriate traffic handling rules at the communication devices, based on longer term performance goals, while at the same time not compromising radio access performance. For example, the algorithm should be able to recognize when the network fronthaul or backhaul is overloaded and attempt to perform processing and scheduling decisions locally, based on installed rules and locally observed states, but should be ready to shift processing centrally in low loads, or for users whose performance might clearly benefit from it.Expected scientific outcome This thesis topic falls into the research areas of software-defined networking, wireless networks, stochastic optimization and network control theory. We will target high quality journals and conferences which are of interest for these areas (e.g., journals IEEE JSAC, Trans. on Networking, Trans. on Network and Service Management, Trans. on Wireless Communications, Elsevier Computer Networks, and conferences ACM Sigmetrics, Sigcomm, Mobihoc, CoNext, and SODA, IEEE Infocom, NetSoft, SDN-NFV, CDC, WCNC). Methodology, work plan and organization Work plan Task 1 – State of the art (M0→M6): (i) Study of the relevant literature on dynamic network control & wireless resource allocation, network utility maximization & fairness, optimization algorithms and decomposition techniques, and queueing/scheduling theory; (ii) Attendance of relevant courses in UPMC, and online seminars from MIT & Stanford; (iii) Review of relevant SDWN and 5G literature to fully understand the technical and system challenges. Task 2 – Online flow allocation and α-fair active queue management (M6→M25): (i) Problem formulations for time-scale decoupling techniques for SDWN, traffic steering techniques in SDWN, distributed/centralized control in wireless networks; (ii) Design of algorithms towards a unified SDWN framework, including placement algorithms, traffic steering algorithms, and online distributed algorithms. Task 3 – SDWN Scalable Optimization Framework (M25→M33): Generalization of proposed methodologies. Design of practical architecture for the proposed SDWN framework. Performance evaluation on a real platform with the help of Huawei research engineers & EURECOM infrastructure. Task 4 – Preparation of the PhD manuscript and defense (M33→M36) Time sharing and activities across the two organizations The PhD candidate will spent 80% of his time at the Mathematical and Algorithmic Sciences Lab of Huawei in Paris and 20% at EURECOM in Sophia Antipolis. He will participate to the following events: At Huawei: (i) Weekly lab meetings which include a project/work presentation from permanent staff, PhD students or interns. (ii) Periodic supervision meetings (remote or physical) with the PhD candidate and all supervisors will also be held (once a month and more if necessary). (iii) Regular seminars with world-class researchers. (iv) Internal training events on Huawei products and systems. (v) Cooperation projects with our academic partners (especially one with Dr. Panayotis Mertikopoulos on learning-based scheduling algorithms for wireless systems). (vi) Seminar attendance at the LINCS in Paris. At Eurecom: (i) At least 4 extended visits (several days and weeks) per year to Sophia Antipolis in the EURECOM institute. (ii) Pr. Spyropoulos will also come at least 4 times a year at Huawei in Boulogne. Dissemination and Exploitation In addition to scientific publications, the work of the PhD student will be disseminated internally at Huawei to experts and engineers working on SDN controllers. The goal is to challenge them with new concepts and innovative solutions, while collecting requirements and feedback. The research work could lead, at the end of the PhD, to innovation demonstrators, with the help of Huawei engineers and to patents if strategic for the company. The FRC Algorithms lab of Huawei in Paris maintains excellent ties with the implementation teams of CloudRAN within Huawei, which gives the PhD candidate a unique opportunity to implement the research ideas in industrial testbeds. In term of impact, this thesis is expected to provide fundamental and practical answers to a large set of application domains: cloud networking, carrier networks and wide-area networks. Relevance of the partnership Nikolaos Liakopoulos has already been directly exposed to the topic of SDN through his participation as a junior researcher in the EU H2020 project NEPHELE. He also has previous research experience through his participation in the EU PANDA and COCONUT projects, which have led to two publications accepted in the IEEE ICECS 2015 conference. Finally, Mr. Liakopoulos has both a strong mathematical background (evidenced by his undergraduate studies in Physics), which is a key requirement for this position, but also has a good grasp of Computer Systems, as suggested by his excellent performance during his master studies (ranked 1st in his class) on the subject, suggesting a potential to complement his theoretical research with some development and experimental aspects. Prof. Thrasyvoulos Spyropoulos is an assistant professor in the mobile communications department at Eurecom. He holds a PhD degree from the University of Southern California (USC), Los Angeles and a diploma in Electrical and Computer Engineering from the National Technical University of Athens (NTUA). Before joining EURECOM he spent a year as a post-doctoral researcher at INRIA, Sophia-Antipolis, and 3 years as a Senior Researcher and Lecturer at ETH Zurich. His research interests include performance analysis, load-balancing and traffic steering in HetNets, and SDN-based wireless networks. He also has extensive project experience with industrial, European, and national projects, including the H2020 COHERENT project [9], where he is a co-PI working on SDN network abstractions for D2D and traffic steering, as well as functional split algorithms for fronthaul networks in CloudRAN. Dr. Georgios Paschos is a Principal Engineer at Huawei and is leading the Network Control and Resource Allocation (NCRA) group in the French Research Center of Huawei. He is a Senior IEEE member and an Associate editor of the IEEE/ACM Trans. on Networking. His 5 current research interests are stochastic optimization for wireless networks and routing for SDN. He received a Ph.D. degree from the University of Patras, Greece in 2006, and before joining Huawei he was a researcher at the Massachusetts Institute of Technology (MIT), USA, working on stochastic optimization of wireless networks. Potential collaborations Within the framework of this PhD, there will be an opportunity to collaborate with the teams of Leandros Tassiulas (Yale University), Eytan Modiano (MIT), and Panayotis Mertikopoulos (CNRS-Grenoble). They all possess relevant expertise in dynamic scheduling and network optimization. Prof. Tassiulas in particular is the inventor of the ``backpressure algorithm’’, and the related theory is expected to play a key role and serve as the basis for the development of this phd. Additionally, we expect to closely consult with Prof. N. Nikaein (EURECOM), who is an expert on the system aspects of LTE Systems, CloudRAN, and SDN/NFV for wireless, and has a track record on architecture and experimentation aspects for cellular networks. The NCRA group of Huawei has 6 members, all phd experts in resource allocation and network optimization. There are also established external research collaborations on the topic of SDN and wireless scheduling, with Supelec, Paris-sud, and CNRS.