load_balance.c

00001 /*
00002  * Copyright (c) 2016-2017, 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         }
00333         else {
00334             //Enter Block state
00335             this->lb_state_timer = this->triggle_period;
00336             this->lb_state = LB_BLOCK_COMPARE;
00337             return;
00338         }
00339 
00340     } else {
00341         //Compare priority to saved network
00342         if (priority > nwk->priority) {
00343             return;
00344         } else if (priority == nwk->priority && nwk->PANDescriptor.LinkQuality > beacon_ind->PANDescriptor.LinkQuality) {
00345             return;
00346         }
00347     }
00348 
00349     //Copy network info
00350     nwk->priority = priority;
00351     nwk->PANDescriptor = beacon_ind->PANDescriptor;
00352     memcpy(beacon_payload_start_pointer(nwk), beacon_ind->beacon_data, beacon_ind->beacon_data_length);
00353     nwk->beacon_data_length = beacon_ind->beacon_data_length;
00354 }
00355 /**
00356  * Load balance activate or disable
00357  */
00358 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)
00359 {
00360     lb_internal_t * this = lb_api_get(api);
00361     if (!this || !this->lb_user_parent_id) {
00362         return;
00363     }
00364 
00365     this->load_balance_activate = active_state;
00366 
00367     if (active_state) {
00368         //Start Block_period
00369         this->triggle_period = network_triggle_max_period;
00370         this->lb_state = LB_BLOCK_STATE;
00371         tr_debug("Enable Network Triggle max time %"PRIu32" %"PRIu32" route life time", network_triggle_max_period, network_route_life_time);
00372         if (this->nwk_switch_threshold_min && this->nwk_switch_threshold_max) {
00373             this->lb_state_timer = network_route_life_time > network_triggle_max_period ? network_route_life_time : network_triggle_max_period;
00374         } else {
00375             this->lb_state_timer = 10;
00376             if (this->lb_border_router) {
00377                 this->lb_border_router->timer2update = 0;
00378                 lb_load_level_poll(this, this->triggle_period);
00379             }
00380         }
00381 
00382     } else {
00383         this->lb_state = LB_IDLE_STATE;
00384     }
00385 
00386     if (this->notified_network) {
00387         this->notified_network->priority = 0xff;
00388         this->notified_network->network_switch_accepted = false;
00389         this->notified_network->state = LB_NWK_SWITCH_IDLE;
00390         this->notified_network->state_timer = 0;
00391     }
00392 }
00393 
00394 /**
00395  * Load balance activate or disable
00396  */
00397 static int8_t lb_api_initialize(load_balance_api_t *api, load_balance_beacon_tx *lb_beacon_tx,
00398                                            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)
00399 {
00400     lb_internal_t * this = lb_api_get(api);
00401     if (!this || !lb_beacon_tx || !priority_get_cb || !lb_nwk_switch_cb || !lb_user) {
00402         return -1;
00403     }
00404 
00405     //Allocate beacon payload here
00406     if (!load_balance_network_class_allocate(this, beacon_max_payload_length)) {
00407         return -2;
00408     }
00409 
00410     this->lb_user_parent_id = lb_user;
00411     this->load_balance_beacon_tx_cb = lb_beacon_tx;
00412     this->lb_nwk_switch_cb = lb_nwk_switch_cb;
00413     this->lb_priority_get_cb = priority_get_cb;
00414     return 0;
00415 }
00416 
00417 static void lb_load_level_poll(lb_internal_t * this, uint32_t trigle_period)
00418 {
00419     if (!this->lb_border_router || !this->lb_user_parent_id) {
00420         return;
00421     }
00422 
00423     if (this->lb_border_router->timer2update) {
00424         this->lb_border_router->timer2update--;
00425         return;
00426     }
00427 
00428     uint16_t node_count;
00429     if (this->lb_border_router->get_count_cb(this->lb_user_parent_id, &node_count) != 0) {
00430         this->lb_border_router->last_load_level = 0xff;
00431         this->lb_border_router->timer2update = 10;
00432         return;
00433     }
00434     //Calculate
00435     uint8_t new_load;
00436     if (node_count >= this->lb_border_router->expected_node_count) {
00437         new_load = this->lb_border_router->network_load_scaler - 1;
00438     } else {
00439         uint16_t scaled_level = this->lb_border_router->expected_node_count / this->lb_border_router->network_load_scaler;
00440         new_load = node_count / scaled_level;
00441     }
00442 
00443     if (this->lb_border_router->last_load_level != new_load) {
00444 
00445         if (this->lb_border_router->set_new_load_cb(this->lb_user_parent_id, new_load) == 0) {
00446             this->lb_border_router->last_load_level = new_load;
00447         }
00448     }
00449     this->lb_border_router->timer2update = trigle_period >> 1; //Update Every block period / 2
00450 }
00451 
00452 static void lb_second_ticks(const load_balance_api_t* api)
00453 {
00454     lb_internal_t * this = lb_api_get(api);
00455     if (!this || this->lb_state == LB_IDLE_STATE) {
00456         return;
00457     }
00458 
00459     lb_load_level_poll(this, this->triggle_period);
00460 
00461     //Update Next beacon generation timer
00462     if (this->periodic_beacon_activated && this->lb_state != LB_BLOCK_STATE && --this->time_to_next_beacon == 0) {
00463         this->time_to_next_beacon = this->triggle_period;
00464         this->load_balance_beacon_tx_cb(this->lb_user_parent_id);
00465     }
00466 
00467     if (this->lb_state_timer == 0) {
00468 
00469         switch (this->lb_state) {
00470             case LB_BLOCK_STATE:
00471                 //Enter block state to accept state
00472                 this->lb_state = LB_ACCEPT_STATE;
00473                 this->time_to_next_beacon = randLIB_get_random_in_range(1, 32);
00474                 break;
00475             case LB_BLOCK_COMPARE:
00476                 this->lb_state = LB_ACCEPT_STATE;
00477                 break;
00478             case LB_BLOCK_NETWORK_SELECT:
00479                 lb_network_switch_handle(this);
00480                 break;
00481             default:
00482                 break;
00483         }
00484     } else {
00485        this->lb_state_timer--;
00486     }
00487 }
00488 
00489 load_balance_api_t *load_balance_create(load_balance_network_switch_notify *lb_notify_cb, bool activate_periodic_beacon)
00490 {
00491     //validate beacon period & beacon_notify
00492     if (!lb_notify_cb) {
00493         return NULL;
00494     }
00495 
00496     //allocate load balance class
00497     lb_internal_t * this = load_balance_class_allocate();
00498     if (!this) {
00499         return NULL;
00500     }
00501     this->lb_state = LB_IDLE_STATE;
00502     this->lb_nwk_switch_notify = lb_notify_cb;
00503     this->periodic_beacon_activated = activate_periodic_beacon;
00504 
00505     return this->lb_api;
00506 }
00507 
00508 int load_balance_delete(load_balance_api_t *api)
00509 {
00510     if (!lb_store || lb_store->lb_api != api) {
00511         return -1;
00512     }
00513 
00514     load_balance_class_free(lb_store);
00515     lb_store = NULL;
00516     return 0;
00517 }
00518 
00519 int load_balance_network_threshold_set(load_balance_api_t *api, uint8_t threshold_min, uint8_t threshold_max)
00520 {
00521     lb_internal_t * this = lb_api_get(api);
00522     if (!this) {
00523         return -1;
00524     }
00525 
00526     this->nwk_switch_threshold_min = threshold_min;
00527     this->nwk_switch_threshold_max = threshold_max;
00528     return 0;
00529 }
00530 
00531 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)
00532 {
00533     lb_internal_t * this = lb_api_get(api);
00534     if (!this) {
00535         return -1;
00536     }
00537     if (expected_node_count == 0 || network_load_scaler == 0 || expected_node_count < network_load_scaler) {
00538         return -1;
00539     }
00540 
00541     if (!get_count_cb || !set_new_load_cb) {
00542         return -1;
00543     }
00544 
00545     lb_monitor_internal_t *border_router = lb_border_router_api_allocate(this);
00546     if (!border_router) {
00547         return -2;
00548     }
00549     border_router->expected_node_count = expected_node_count;
00550     border_router->network_load_scaler = network_load_scaler;
00551     border_router->get_count_cb = get_count_cb;
00552     border_router->last_load_level = 0xff;
00553     border_router->set_new_load_cb = set_new_load_cb;
00554     border_router->timer2update = 10;
00555     return 0;
00556 }
00557 
00558 int load_balance_network_load_monitor_disable(load_balance_api_t *api)
00559 {
00560     lb_internal_t * this = lb_api_get(api);
00561     if (!this) {
00562         return -1;
00563     }
00564     return lb_border_router_api_free(this);
00565 }
00566 
00567 int load_balance_set_max_probability(load_balance_api_t *api, uint8_t max_p)
00568 {
00569     lb_internal_t * this = lb_api_get(api);
00570     if (!this) {
00571         return -1;
00572     }
00573     if (max_p > 100 || max_p == 0) {
00574         return -1;
00575     }
00576 
00577     this->nwk_maX_P = max_p;
00578 
00579     return 0;
00580 
00581 }
00582 
00583 int load_balance_network_switch_cb_set(load_balance_api_t *api, net_load_balance_network_switch_notify *network_switch_notify)
00584 {
00585     lb_internal_t * this = lb_api_get(api);
00586     if (!this) {
00587         return -1;
00588     }
00589 
00590     this->lb_access_switch_cb = network_switch_notify;
00591 
00592     return 0;
00593 }
00594 
00595