Optimization access point assignment algorithms in sdn-controlled wireless access networks

Resumen

Our lives are becoming increasingly dependent on different services provided by the Inter-net such as social media, banking, emails and online shopping. This dependency comeshand-in-hand with an increase of cellphone production to serve highly interactive and highlybandwidth-consuming applications such as 4K streaming and virtual reality.As a result of these trends, developers are driven and motivated to create applicationswith increasingly demanding bandwidth and latency requirements. Despite all the work toimprove access networks, new applications will still face several connection issues duringtheir use, especially if multiple applications with high demands try to connect to the sameAPs at a time. In this context, in order to satisfy the QoS levels of the network and the QoEof the users, the former must evolve. 5G is presented as an alternative towards this goal.5G is the next-generation standard for cellular networks and other advanced wirelesscommunications. 5G networks are expected to include the high-frequency band of thewireless spectrum, also known as the millimeter wave (mmWave) spectrum. It will providea higher bandwidth availability to end users. 5G networks are also expected to increasenetwork capacity and speed, while lowering latency.Despite of being the standard of reference of the near future, 5G will not be able toreplace LTE immediately. For example, cellular networks will be a hybrid comprising highperformance mmWave small cells and less powerful LTE macro cells.In this scenario, as a result of the shorter range of millimeter waves it can be expectedthat terminals will experience a considerable amount of APs changes and hand-offs. Becauseof this, it is necessary to provide solutions to protect end users from a severe decrease of QoEduring these multiple and frequent transitions, especially considering that most applicationsare getting bandwidth hungry and delay sensitive. In order to face this, in this work we consider the AP assignment problem as a keycomponent for the success of 5G networks. With this in mind, we also consider the speed atwhich AP assignment decisions will be made a crucial metric in determining the success ofAP assignment solutions as well as ensuring the QoE experimented by end users. To put itin another way, to rightly assign terminals to APs in our view means, on the one hand, toconnect the terminals to an AP that can support their bandwidth needs, to respect the rest ofthe terminals needs, and to perform connections as fast as possible at all times.Software Defined Networking is a revolutionary paradigm that allows network managersto quickly and programmatically configure, manage, secure, and optimize network resources.Network management is centralized in a programmable central controller, by completelyseparating the forwarding plane and the control plane. The logical centralization of thenetwork intelligence in the SDN network controller supports a global view of the network.Therefore, network programmers can directly and dynamically adjust network traffic flowsaccording to their needs thanks to the agile nature of SDN.As an open standard and a vendor-neutral architecture, SDN has become very popular inthe past few years. Taking into consideration its agility and capabilities, we consider it anexcellent choice for controlling 5G networks and other advanced wireless networks.We have recently proposed to embed SDN virtual switches into users’ terminals. A SDNcontroller can monitor and manage them directly with the Openflow protocol, enabling aglobal SDN-oriented network optimization. We call this approach Traffic Steering Architec-ture (TSA).Despite all the advantages of SDN for user traffic monitoring, many users may be worriedabout the possibility of their data being used by companies or for illegal activities. As aresult of the General Regulation of Data Protection (GRDP), which is being implemented indifferent sectors in the European Union (EU), users may restrict monitoring their data forprivacy reasons.In order to overcome this issue, previous authors have proposed network-side traffic classprediction (e.g. at the APs). Even though it has been demonstrated that accurate predictionsare feasible in a matter of seconds, since 5G networks are expected to support latency-criticalapplications, any decision delay should be minimized whenever possible. Besides, priorknowledge of protocol characteristics (which may change in time) and even deep packet inspection are often assumed.In our work we have focused on making the AP assignment process as fast as possibleby eliminating real-time traffic analysis whenever an AP receives a new flow or terminalconnection request, through implementing a traffic flow predictor at the SDN controller basedon previous user history.As a consequence, we have managed to decrease the time needed for AP assignmentdecisions and thus overall AP handover time in the network. Accurate traffic characterizationis still necessary to update historical data, but it can be performed in the background at thenetwork side if the users are not willing to release this information.In order to test our TSA AP assignment algorithm, we needed a realistic network layoutwith a dense population of APs that may be representative of 5G networks. We also neededmonitoring data containing detailed user terminal activities such as positions and used appli-cations. Regarding the latter, we specifically needed network related applications. As for thelocation data, we need it to be detailed and frequent.In order to emulate a test-bed suitable to our needs, we decided to simulate it by modify-ing the LiveLab dataset [35]. This dataset contains real data from mobile terminals in theRice University Wi-Fi campus network. Its features include the applications running in theterminals, accelerometer measurements and the set of available Wi-Fi APs to each terminalat all times. When the data were collected, the campus network had 834 APs covering anarea of 700×500m2.The applications are classified by tags such as entertainment and news, but these tagshave nothing to do with network traffic nor flow types, which makes them useless for our purpose.Therefore, in order to adapt the data to our purposes, we cleaned the dataset from allthe instances of irrelevant offline applications such as calendar, clock and gallery, and thentagged the remaining ones with two new labels to guide our AP assignment algorithm basedon the flows the terminals generate. These new tags were “Elephant Flow” (EF) and “MouseFlow” (MF), for applications with high and low bandwidth demands, respectively. Besides, the live LiveLab dataset contains all needed data to reverse-deduct the Rice Uni-versity AP network. The process we followed for recreating the network can be summarizedas follows: •We started by estimating the general layout of the network, by collecting individualviews from the users’ terminals as they moved across the network, served by differentAPs. We created matrices of distances, adjacency, incidence angles, and radii for allusers.•Using those data, we could infer network size, APs coverage, and the relative locationof each AP compared to each other. In order to calculate the distance between the APs,first we guessed all the different locations a userkhad occupied while connected to acertain AP and calculated the center of gravity of those positions. Then we consideredthat center of gravity as the possible location of the AP from the point of view of userk. This was averaged for all users and these actions were repeated for all APs. •Next, we focused on finding a solution for the range extenders in the campus network.We assumed an average coverage radius of 10-12meters for Wi-Fi APs, so any dis-covered AP with higher coverage could be considered a set of extenders. Therefore,we replaced the extended area by a random group of APs with coverage radius of12meters each. •Finally, we determined the initial location of the users using the position of two APs towhich the user had been connected, and the coverage radius of those APs. Using thehand-off point between them as a starting point, the angle of movement the user hadbefore arriving to that hand-off point, and the distance the user had covered to arrive tothat hand-off point, we could estimate the starting position for the user.As described, the process used the terminals’ accelerometer data (to deduct their posi-tions) and the terminals’ history of AP assignments as sole inputs. The result of our network recreation approach was a highly dense network containingmultiple AP with overlapping ranges. It presents an interesting portrayal of how dense 5Gnetworks are expected to be in reality, while at the same time it offers a convenient envi-ronment for testing AP assignment algorithms, since the terminals will often have multiple choices of APs to serve their needs.As previously mentioned, we propose to take AP allocation decisions in the SDN-controller based exclusively on predictions made from the past history of terminals’ behavior(this historical terminal information would be either provided by the terminals themselves orestimated at the network side in the background).Our AP assignment algorithm was validated on 42 simulations of the same number ofworking days of the Rice University calendar. Each simulation covered at least 18 activeusers between 8:00 and 13:00 in second-by-second algorithm executions.In order to ensure that QoS and QoE objectives are achieved by our AP assignmentalgorithm, we used a fitness function that measured the number of correctly assigned flows aswell as the relation between assigned and demanded bandwidth. The assignments guaranteethat any AP can serve the needs of its assigned terminals and that handover times fulfil QoErequirements.Each second, the AP assignment algorithm updates the predictions for all the users,anticipating flow changes, and receives monitoring data on new terminal activities if avail-able. In case a terminal starts generating traffic, the AP assignment algorithm uses alreadypredicted flow types to test possible terminal reassignments to new APs. That is, the re-assignments do not only apply to the terminals whose flow predictions change or whichstart generating traffic, but to any terminal that can be reassigned (those with alternativeAPs available in the neighboring area) leading to fitness function improvement. This illustrates that our algorithm considers the whole access network state when reassigning terminals.In order to evaluate our AP assignment algorithm, we compared it with two competi-tors. First, a trivial AP assignment method that takes decisions based on RSSI strength, theclosest-AP assignment. It consists of assigning the terminals to the AP with the strongestRSSI, which may be overloaded when the load of attached users exceeds available capacity.Although the performance of this method is low, it is in use today by the IEEE standard802.11 [52] because of its simplicity. It is obviously executed by the terminals themselves ina fully decentralized way. It does not consider the network state nor any AP constraint.The second competing AP assignment approach for comparing our proposal is an opti-mum AP assignment algorithm. This approach assumes complete knowledge of the state of the network and the terminals. In it, the controller knows the exact traffic type the terminalswill be generating (compared to our AP assignment approach where a predictor guesses thetraffic type the terminals will generate). It attains the optimum AP assignment in terms ofour fitness objectives.By running closest-AP, our AP assignment algorithm and the optimum AP assignmentalgorithm on the same testing scenarios, we show that the rather simple prediction in our cen-tralized approach based on previous history allows achieving network utilization levels thatare relatively close to those of optimal allocations and is much better than trivial assignmentsbased on RSSI strength.When checking our approach against the optimum, the results show that a worse per-formance, but the difference only exceeded 10% of the upper bound for 8% of the time.Actually, our performance was strictly better than 95% of the optimum for 80% of the time.We also tested a distributed version of our algorithm where network APs are clusteredinto groups. In this version, instead of solving the assignment problem for the whole network,the controller of each cluster solves its own sub-problem.The motivation of a distributed version of our AP assignment algorithm is to minimizedecision delay since the local SDN controllers will handle a limited number of APs each.First we applied our AP assignment algorithm in a K-means clustered network andcompared the results with the closest-AP assignment and the centralized AP assignmentalgorithms in terms of fitness. The distributed version of the algorithm did not performsignificantly worse than the centralized version, and it still outperformed the closest-APassignment. This experiment suggests that our distributed AP assignment algorithm haspotential to provide results close to those of centralized AP assignment approaches, for areduced decision time.The results of this test encouraged us to study the effect of cluster size on algorithmperformance, in terms of fitness value, data loss, time, throughput and assignment changes.We decided to use increasingly finer uniform grids to cluster the network topology (networkswith 1, 2, 4, 14, 47, 153, 440 and 686 clusters). The results revealed that our distributed AP algorithm can be up to65%faster than thecentralized assignment algorithms, and that the number of AP assignment changes can belimited to27%narrowing down the hand-offs in the network. On the other hand, the resultsindicate that a large number of clusters may lead to drastic increases of data loss and availablebandwidth.In our testbed scenario a choice of 14 clusters yields a good balance between performanceand decision time.Finally, we provide a bound on elapsed decision time since a user traffic event takes placeuntil an access point is reassigned. In this part of the work, we determined that the process ofAP assignment in an SDN network can be divided into five stages: • Detecting the flow (χ), • Notifying the controller (β), • Executing the AP assignment algorithm (γ), • Commanding the terminal to connect to the new AP (δ), • Establishing the new connection (ζ). Each of these stages has impact on the delay in the network.We analyzed the time needed for each stage depending on possible supporting tech-nologies. We started by comparing different existing SDN controllers e in terms of χ, β, δ and we arrived to the conclusion that the sum χ+β+δ would be in the order of tensof milliseconds in our SDN-TSA architecture. The simulations carried out to measure δ,show that, in practice, we need less than 0.2 ms to execute the assignment algorithm in ourtestbed. Finally, the time to establish a new connection will greatly depend on the particularcommunications technology, ranging from 6 to 9 seconds in a secure Wi-Fi network to lessthan 40 ms in a SDN-Enabled Wi-Fi network or even less than 1 ms in future 5G networks.Adding all the parameters, elapsed decision time can be bounded by 100 ms.Summing up, in this thesis we propose a new approach for centralized AP assignment touser terminals in an SDN network. It reduces decision delay, and thus handover time, by tak-ing decisions exclusively based on past history. However, it still attains excellent QoS levelssubject to QoE constraints. This work is motivated by the claimed goals for 5G networks that will support bandwidth-hungry applications with stringent latency requirements. Thearchitecture in this work, SDN TSA, has been tested on a realistic network that simulates theRice University campus network as described by the LiveLab dataset.