load_balance.c

00001 /*
00002  * Copyright (c) 2016-2018, Arm Limited and affiliates.
00003  * SPDX-License-Identifier: Apache-2.0
00004  *
00005  * Licensed under the Apache License, Version 2.0 (the "License");
00006  * you may not use this file except in compliance with the License.
00007  * You may obtain a copy of the License at
00008  *
00009  *     http://www.apache.org/licenses/LICENSE-2.0
00010  *
00011  * Unless required by applicable law or agreed to in writing, software
00012  * distributed under the License is distributed on an "AS IS" BASIS,
00013  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00014  * See the License for the specific language governing permissions and
00015  * limitations under the License.
00016  */
00017 
00018 
00019 #include "nsconfig.h"
00020 #include "ns_types.h"
00021 #include "eventOS_event.h"
00022 #include "eventOS_scheduler.h"
00023 #include "eventOS_callback_timer.h"
00024 #include "load_balance_api.h"
00025 #include "string.h"
00026 #include "ns_trace.h"
00027 #include "nsdynmemLIB.h"
00028 #include "randLIB.h"
00029 #include "mlme.h"
00030 
00031 typedef enum {
00032     LB_NWK_SWITCH_IDLE = 0,
00033     LB_NWK_SWITCH_ROUTER_LEAVE,
00034     LB_NWK_SWITCH_NEIGHBOUR_LEAVE
00035 } lb_nwk_switch_state_t;
00036 
00037 typedef enum {
00038     LB_IDLE_STATE = 0,
00039     LB_BLOCK_STATE,
00040     LB_ACCEPT_STATE,
00041     LB_BLOCK_COMPARE,
00042     LB_BLOCK_NETWORK_SELECT,
00043 } lb_state_t;
00044 
00045 /**
00046  * @brief struct lb_network_s Load balance network information
00047  *
00048  */
00049 typedef struct lb_network_s {
00050     struct mlme_pan_descriptor_s PANDescriptor;
00051     uint8_t priority;
00052     bool network_switch_accepted;
00053     lb_nwk_switch_state_t state;
00054     uint16_t state_timer;
00055     uint16_t beacon_data_length;
00056     uint8_t beacon_data[];
00057 } lb_network_t;
00058 
00059 /** get pointer to Mac header start point*/
00060 #define beacon_payload_start_pointer(x)  (&(x)->beacon_data[0])
00061 
00062 typedef struct lb_monitor_internal_s {
00063     load_balance_api_get_node_count *get_count_cb;
00064     load_balance_api_set_load_level *set_new_load_cb;
00065     uint16_t expected_node_count;
00066     uint8_t network_load_scaler;
00067     uint8_t last_load_level;
00068     uint16_t timer2update;
00069 } lb_monitor_internal_t;
00070 
00071 
00072 typedef struct lb_internal_s {
00073     load_balance_api_t *lb_api;
00074     lb_monitor_internal_t *lb_border_router;
00075     //user spesific callback
00076     load_balance_beacon_tx *load_balance_beacon_tx_cb;
00077     load_balance_priority_get *lb_priority_get_cb;
00078     load_balance_network_switch_req *lb_nwk_switch_cb;
00079     load_balance_network_switch_notify *lb_nwk_switch_notify; //Can be NULL if app not want to control
00080     //APP defined nwk switch callback
00081     net_load_balance_network_switch_notify *lb_access_switch_cb;
00082     void *lb_user_parent_id;
00083     lb_network_t *notified_network;
00084     uint32_t triggle_period;
00085     uint32_t lb_state_timer;
00086     uint32_t time_to_next_beacon;
00087     uint16_t beacon_max_payload_length;
00088     uint8_t nwk_switch_threshold_min;
00089     uint8_t nwk_switch_threshold_max;
00090     uint8_t nwk_maX_P;
00091     lb_state_t lb_state;
00092     bool load_balance_activate;
00093     bool periodic_beacon_activated;
00094 } lb_internal_t;
00095 
00096 
00097 /**
00098  * Load balance internal variables
00099  */
00100 static load_balance_api_t lb_api;
00101 static lb_internal_t *lb_store = NULL;
00102 
00103 /**
00104  * Load balance internal used functions
00105  */
00106 static lb_internal_t *load_balance_class_allocate(void);
00107 static void load_balance_class_free(lb_internal_t *api);
00108 static lb_internal_t *lb_api_get(const load_balance_api_t *api);
00109 static bool load_balance_network_class_allocate(lb_internal_t *lb_store_ptr, uint16_t beacon_max_payload_length);
00110 static void lb_network_switch_handle(lb_internal_t *this);
00111 static void lb_load_level_poll(lb_internal_t *this, uint32_t trigle_period);
00112 
00113 /**
00114  * Load balance shared functions to user
00115  */
00116 static void lb_beacon_notify(const load_balance_api_t *api, const struct mlme_beacon_ind_s *beacon_ind, uint8_t priority);
00117 static void lb_enable(const load_balance_api_t *api, bool active_state, uint32_t network_triggle_max_period, uint32_t network_route_life_time);
00118 static int8_t lb_api_initialize(load_balance_api_t *api, load_balance_beacon_tx *lb_beacon_tx,
00119                                 load_balance_priority_get *priority_get_cb, load_balance_network_switch_req *lb_nwk_switch_cb, uint16_t baecon_max_payload_length, void *lb_user);
00120 static void lb_second_ticks(const load_balance_api_t *api);
00121 
00122 #define TRACE_GROUP "lba"
00123 
00124 /**
00125  * Load balance border router class allocate
00126  */
00127 static lb_monitor_internal_t *lb_border_router_api_allocate(lb_internal_t *api)
00128 {
00129     if (!api->lb_border_router) {
00130         api->lb_border_router = ns_dyn_mem_alloc(sizeof(lb_monitor_internal_t));
00131     }
00132     return api->lb_border_router;
00133 }
00134 
00135 /**
00136  * Load balance border router class free
00137  */
00138 static int8_t lb_border_router_api_free(lb_internal_t *api)
00139 {
00140     if (api->lb_border_router) {
00141         ns_dyn_mem_free(api->lb_border_router);
00142         api->lb_border_router = NULL;
00143         return 0;
00144     }
00145     return -1;
00146 }
00147 
00148 /**
00149  * Allocate Load balance class base
00150  */
00151 static lb_internal_t *load_balance_class_allocate(void)
00152 {
00153     if (lb_store) {
00154         if (lb_store->lb_user_parent_id) {
00155             return NULL;
00156         }
00157         return lb_store;
00158     }
00159 
00160     lb_internal_t *store = ns_dyn_mem_alloc(sizeof(lb_internal_t));
00161     if (store) {
00162 
00163         store->lb_api = &lb_api;
00164         lb_api.lb_beacon_notify = lb_beacon_notify;
00165         lb_api.lb_enable = lb_enable;
00166         lb_api.lb_initialize = lb_api_initialize;
00167         lb_api.lb_seconds_tick_update = lb_second_ticks;
00168 
00169         store->lb_border_router = NULL;
00170         store->load_balance_beacon_tx_cb = NULL;
00171         store->lb_nwk_switch_cb = NULL;
00172         store->lb_priority_get_cb = NULL;
00173         store->lb_user_parent_id = NULL;
00174         store->notified_network = NULL;
00175         store->lb_access_switch_cb = NULL;
00176         store->beacon_max_payload_length = 0;
00177         store->nwk_switch_threshold_max = 0;
00178         store->nwk_switch_threshold_min = 0;
00179         store->nwk_maX_P = 25;
00180         store->load_balance_activate = false;
00181         store->time_to_next_beacon = 0;
00182         store->triggle_period = 0;
00183         lb_store = store;
00184     }
00185 
00186     return store;
00187 }
00188 
00189 /**
00190  * Free allocated load balance class
00191  */
00192 static void load_balance_class_free(lb_internal_t *api)
00193 {
00194     //Clean heared networks
00195     ns_dyn_mem_free(api->notified_network);
00196     lb_border_router_api_free(api);
00197     ns_dyn_mem_free(api);
00198 }
00199 
00200 /**
00201  * Load balance class get by user API pointer
00202  */
00203 static lb_internal_t *lb_api_get(const load_balance_api_t *api)
00204 {
00205     if (!api || !lb_store || lb_store->lb_api != api) {
00206         return NULL;
00207     }
00208     return lb_store;
00209 }
00210 
00211 
00212 
00213 /**
00214  * Allocate notified network class
00215  */
00216 static bool load_balance_network_class_allocate(lb_internal_t *lb_store_ptr, uint16_t beacon_max_payload_length)
00217 {
00218     ns_dyn_mem_free(lb_store_ptr->notified_network);
00219     lb_store_ptr->beacon_max_payload_length = 0;
00220     if (beacon_max_payload_length) {
00221         lb_store_ptr->notified_network = ns_dyn_mem_alloc(sizeof(lb_network_t) + beacon_max_payload_length);
00222         if (!lb_store_ptr->notified_network) {
00223             return false;
00224         }
00225         lb_store_ptr->notified_network->network_switch_accepted = false;
00226         lb_store_ptr->notified_network->priority = 0xff;
00227         lb_store_ptr->notified_network->state = LB_NWK_SWITCH_IDLE;
00228         lb_store_ptr->notified_network->state_timer = 0;
00229         lb_store_ptr->beacon_max_payload_length = beacon_max_payload_length;
00230 
00231     }
00232     return true;
00233 }
00234 
00235 /**
00236  * Switch to notified and selected network
00237  */
00238 static void lb_network_switch_handle(lb_internal_t *this)
00239 {
00240     lb_network_t *network_class = this->notified_network;
00241     if (network_class->state_timer) {
00242         network_class->state_timer--;
00243         return;
00244     }
00245 
00246     switch (network_class->state) {
00247         case LB_NWK_SWITCH_IDLE:
00248             if (!this->notified_network->network_switch_accepted) {
00249                 if (this->lb_access_switch_cb && !this->lb_access_switch_cb()) {
00250                     return;
00251                 }
00252                 this->notified_network->network_switch_accepted = true;
00253             }
00254             tr_info("Start NWK switch statemachine!");
00255             this->lb_nwk_switch_notify(this->lb_user_parent_id, LB_ROUTER_LEAVE, &network_class->state_timer);
00256             network_class->state = LB_NWK_SWITCH_ROUTER_LEAVE;
00257             break;
00258 
00259         case LB_NWK_SWITCH_ROUTER_LEAVE:
00260             tr_info("Router leave state!");
00261             this->lb_nwk_switch_notify(this->lb_user_parent_id, LB_NEIGHBOUR_LEAVE, &network_class->state_timer);
00262             network_class->state = LB_NWK_SWITCH_NEIGHBOUR_LEAVE;
00263             break;
00264 
00265         case LB_NWK_SWITCH_NEIGHBOUR_LEAVE:
00266             tr_info("Neighbour leave state!");
00267             //Disable beacon send
00268             lb_enable(this->lb_api, false, 0, 0);
00269             this->lb_nwk_switch_cb(this->lb_user_parent_id, &network_class->PANDescriptor, beacon_payload_start_pointer(network_class), network_class->beacon_data_length);
00270             break;
00271     }
00272 
00273 }
00274 
00275 static bool lb_accept_beacon_state(lb_state_t lb_state)
00276 {
00277     //Check state
00278     switch (lb_state) {
00279         case LB_IDLE_STATE:
00280         case LB_BLOCK_STATE:
00281         case LB_BLOCK_COMPARE:
00282             return false;
00283         default:
00284             break;
00285 
00286     }
00287     return true;
00288 }
00289 
00290 /**
00291  * Beacon notify handler
00292  */
00293 static void lb_beacon_notify(const load_balance_api_t *api, const struct mlme_beacon_ind_s *beacon_ind, uint8_t priority)
00294 {
00295     lb_internal_t *this = lb_api_get(api);
00296     if (!beacon_ind || !this || !this->nwk_switch_threshold_max || !this->nwk_switch_threshold_min) {
00297         return;
00298     } else if (!lb_accept_beacon_state(this->lb_state)) {
00299         return;
00300     } else if (beacon_ind->beacon_data_length > this->beacon_max_payload_length) {
00301         return;
00302     }
00303 
00304     lb_network_t *nwk = this->notified_network;
00305     //Get current global part joining priority
00306     uint8_t current_priority = this->lb_priority_get_cb(this->lb_user_parent_id);
00307 
00308     if (this->lb_state == LB_ACCEPT_STATE) {
00309         //Compare new network priority
00310         if (current_priority < priority) {
00311             return;
00312         }
00313 
00314         uint16_t diff = current_priority - priority;
00315         uint16_t switch_prob; // 256 * percent (0-25600)
00316 
00317         if (diff >= this->nwk_switch_threshold_max) {
00318             switch_prob = this->nwk_maX_P * 256;
00319             tr_debug("diff %"PRIu16", tmax %"PRIu8" %"PRIu16, diff, this->nwk_switch_threshold_max, switch_prob);
00320         } else if (diff <= this->nwk_switch_threshold_min) {
00321             tr_debug("diff %"PRIu16", tmin %"PRIu8, diff, this->nwk_switch_threshold_min);
00322             switch_prob = 0;
00323         } else {
00324             // The multiplication could overflow 16-bit, even though the final result will be 16-bit
00325             switch_prob = (uint32_t) this->nwk_maX_P * 256 * (diff - this->nwk_switch_threshold_min) / (this->nwk_switch_threshold_max - this->nwk_switch_threshold_min);
00326             tr_debug("diff between min & max, diff %"PRIu16", tmax %"PRIu8" prob%"PRIu16, diff, this->nwk_switch_threshold_max, switch_prob);
00327         }
00328 
00329         if (switch_prob > randLIB_get_random_in_range(0, 25599)) {
00330             this->lb_state_timer = randLIB_get_random_in_range(1, 32);
00331             this->lb_state = LB_BLOCK_NETWORK_SELECT;
00332         } else {
00333             //Enter Block state
00334             this->lb_state_timer = this->triggle_period;
00335             this->lb_state = LB_BLOCK_COMPARE;
00336             return;
00337         }
00338 
00339     } else {
00340         //Compare priority to saved network
00341         if (priority > nwk->priority) {
00342             return;
00343         } else if (priority == nwk->priority && nwk->PANDescriptor.LinkQuality > beacon_ind->PANDescriptor.LinkQuality) {
00344             return;
00345         }
00346     }
00347 
00348     //Copy network info
00349     nwk->priority = priority;
00350     nwk->PANDescriptor = beacon_ind->PANDescriptor;
00351     memcpy(beacon_payload_start_pointer(nwk), beacon_ind->beacon_data, beacon_ind->beacon_data_length);
00352     nwk->beacon_data_length = beacon_ind->beacon_data_length;
00353 }
00354 /**
00355  * Load balance activate or disable
00356  */
00357 static void lb_enable(const load_balance_api_t *api, bool active_state, uint32_t network_triggle_max_period, uint32_t network_route_life_time)
00358 {
00359     lb_internal_t *this = lb_api_get(api);
00360     if (!this || !this->lb_user_parent_id) {
00361         return;
00362     }
00363 
00364     this->load_balance_activate = active_state;
00365 
00366     if (active_state) {
00367         //Start Block_period
00368         this->triggle_period = network_triggle_max_period;
00369         this->lb_state = LB_BLOCK_STATE;
00370         tr_debug("Enable Network Triggle max time %"PRIu32" %"PRIu32" route life time", network_triggle_max_period, network_route_life_time);
00371         if (this->nwk_switch_threshold_min && this->nwk_switch_threshold_max) {
00372             this->lb_state_timer = network_route_life_time > network_triggle_max_period ? network_route_life_time : network_triggle_max_period;
00373         } else {
00374             this->lb_state_timer = 10;
00375             if (this->lb_border_router) {
00376                 this->lb_border_router->timer2update = 0;
00377                 lb_load_level_poll(this, this->triggle_period);
00378             }
00379         }
00380 
00381     } else {
00382         this->lb_state = LB_IDLE_STATE;
00383     }
00384 
00385     if (this->notified_network) {
00386         this->notified_network->priority = 0xff;
00387         this->notified_network->network_switch_accepted = false;
00388         this->notified_network->state = LB_NWK_SWITCH_IDLE;
00389         this->notified_network->state_timer = 0;
00390     }
00391 }
00392 
00393 /**
00394  * Load balance activate or disable
00395  */
00396 static int8_t lb_api_initialize(load_balance_api_t *api, load_balance_beacon_tx *lb_beacon_tx,
00397                                 load_balance_priority_get *priority_get_cb, load_balance_network_switch_req *lb_nwk_switch_cb, uint16_t beacon_max_payload_length, void *lb_user)
00398 {
00399     lb_internal_t *this = lb_api_get(api);
00400     if (!this || !lb_beacon_tx || !priority_get_cb || !lb_nwk_switch_cb || !lb_user) {
00401         return -1;
00402     }
00403 
00404     //Allocate beacon payload here
00405     if (!load_balance_network_class_allocate(this, beacon_max_payload_length)) {
00406         return -2;
00407     }
00408 
00409     this->lb_user_parent_id = lb_user;
00410     this->load_balance_beacon_tx_cb = lb_beacon_tx;
00411     this->lb_nwk_switch_cb = lb_nwk_switch_cb;
00412     this->lb_priority_get_cb = priority_get_cb;
00413     return 0;
00414 }
00415 
00416 static void lb_load_level_poll(lb_internal_t *this, uint32_t trigle_period)
00417 {
00418     if (!this->lb_border_router || !this->lb_user_parent_id) {
00419         return;
00420     }
00421 
00422     if (this->lb_border_router->timer2update) {
00423         this->lb_border_router->timer2update--;
00424         return;
00425     }
00426 
00427     uint16_t node_count;
00428     if (this->lb_border_router->get_count_cb(this->lb_user_parent_id, &node_count) != 0) {
00429         this->lb_border_router->last_load_level = 0xff;
00430         this->lb_border_router->timer2update = 10;
00431         return;
00432     }
00433     //Calculate
00434     uint8_t new_load;
00435     if (node_count >= this->lb_border_router->expected_node_count) {
00436         new_load = this->lb_border_router->network_load_scaler - 1;
00437     } else {
00438         uint16_t scaled_level = this->lb_border_router->expected_node_count / this->lb_border_router->network_load_scaler;
00439         new_load = node_count / scaled_level;
00440     }
00441 
00442     if (this->lb_border_router->last_load_level != new_load) {
00443 
00444         if (this->lb_border_router->set_new_load_cb(this->lb_user_parent_id, new_load) == 0) {
00445             this->lb_border_router->last_load_level = new_load;
00446         }
00447     }
00448     this->lb_border_router->timer2update = trigle_period >> 1; //Update Every block period / 2
00449 }
00450 
00451 static void lb_second_ticks(const load_balance_api_t *api)
00452 {
00453     lb_internal_t *this = lb_api_get(api);
00454     if (!this || this->lb_state == LB_IDLE_STATE) {
00455         return;
00456     }
00457 
00458     lb_load_level_poll(this, this->triggle_period);
00459 
00460     //Update Next beacon generation timer
00461     if (this->periodic_beacon_activated && this->lb_state != LB_BLOCK_STATE && --this->time_to_next_beacon == 0) {
00462         this->time_to_next_beacon = this->triggle_period;
00463         this->load_balance_beacon_tx_cb(this->lb_user_parent_id);
00464     }
00465 
00466     if (this->lb_state_timer == 0) {
00467 
00468         switch (this->lb_state) {
00469             case LB_BLOCK_STATE:
00470                 //Enter block state to accept state
00471                 this->lb_state = LB_ACCEPT_STATE;
00472                 this->time_to_next_beacon = randLIB_get_random_in_range(1, 32);
00473                 break;
00474             case LB_BLOCK_COMPARE:
00475                 this->lb_state = LB_ACCEPT_STATE;
00476                 break;
00477             case LB_BLOCK_NETWORK_SELECT:
00478                 lb_network_switch_handle(this);
00479                 break;
00480             default:
00481                 break;
00482         }
00483     } else {
00484         this->lb_state_timer--;
00485     }
00486 }
00487 
00488 load_balance_api_t *load_balance_create(load_balance_network_switch_notify *lb_notify_cb, bool activate_periodic_beacon)
00489 {
00490     //validate beacon period & beacon_notify
00491     if (!lb_notify_cb) {
00492         return NULL;
00493     }
00494 
00495     //allocate load balance class
00496     lb_internal_t *this = load_balance_class_allocate();
00497     if (!this) {
00498         return NULL;
00499     }
00500     this->lb_state = LB_IDLE_STATE;
00501     this->lb_nwk_switch_notify = lb_notify_cb;
00502     this->periodic_beacon_activated = activate_periodic_beacon;
00503 
00504     return this->lb_api;
00505 }
00506 
00507 int load_balance_delete(load_balance_api_t *api)
00508 {
00509     if (!lb_store || lb_store->lb_api != api) {
00510         return -1;
00511     }
00512 
00513     load_balance_class_free(lb_store);
00514     lb_store = NULL;
00515     return 0;
00516 }
00517 
00518 int load_balance_network_threshold_set(load_balance_api_t *api, uint8_t threshold_min, uint8_t threshold_max)
00519 {
00520     lb_internal_t *this = lb_api_get(api);
00521     if (!this) {
00522         return -1;
00523     }
00524 
00525     this->nwk_switch_threshold_min = threshold_min;
00526     this->nwk_switch_threshold_max = threshold_max;
00527     return 0;
00528 }
00529 
00530 int load_balance_network_load_monitor_enable(load_balance_api_t *api, uint16_t expected_node_count, uint8_t network_load_scaler, load_balance_api_get_node_count *get_count_cb, load_balance_api_set_load_level *set_new_load_cb)
00531 {
00532     lb_internal_t *this = lb_api_get(api);
00533     if (!this) {
00534         return -1;
00535     }
00536     if (expected_node_count == 0 || network_load_scaler == 0 || expected_node_count < network_load_scaler) {
00537         return -1;
00538     }
00539 
00540     if (!get_count_cb || !set_new_load_cb) {
00541         return -1;
00542     }
00543 
00544     lb_monitor_internal_t *border_router = lb_border_router_api_allocate(this);
00545     if (!border_router) {
00546         return -2;
00547     }
00548     border_router->expected_node_count = expected_node_count;
00549     border_router->network_load_scaler = network_load_scaler;
00550     border_router->get_count_cb = get_count_cb;
00551     border_router->last_load_level = 0xff;
00552     border_router->set_new_load_cb = set_new_load_cb;
00553     border_router->timer2update = 10;
00554     return 0;
00555 }
00556 
00557 int load_balance_network_load_monitor_disable(load_balance_api_t *api)
00558 {
00559     lb_internal_t *this = lb_api_get(api);
00560     if (!this) {
00561         return -1;
00562     }
00563     return lb_border_router_api_free(this);
00564 }
00565 
00566 int load_balance_set_max_probability(load_balance_api_t *api, uint8_t max_p)
00567 {
00568     lb_internal_t *this = lb_api_get(api);
00569     if (!this) {
00570         return -1;
00571     }
00572     if (max_p > 100 || max_p == 0) {
00573         return -1;
00574     }
00575 
00576     this->nwk_maX_P = max_p;
00577 
00578     return 0;
00579 
00580 }
00581 
00582 int load_balance_network_switch_cb_set(load_balance_api_t *api, net_load_balance_network_switch_notify *network_switch_notify)
00583 {
00584     lb_internal_t *this = lb_api_get(api);
00585     if (!this) {
00586         return -1;
00587     }
00588 
00589     this->lb_access_switch_cb = network_switch_notify;
00590 
00591     return 0;
00592 }
00593 
00594