API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Oct 18th, 2019
113
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 16.86 KB | None | 0 0
raw download clone embed print report
  1. /*
  2. * Copyright (c) 2010, Swedish Institute of Computer Science.
  3. * All rights reserved.
  4. *
  5. * Redistribution and use in source and binary forms, with or without
  6. * modification, are permitted provided that the following conditions
  7. * are met:
  8. * 1. Redistributions of source code must retain the above copyright
  9. * notice, this list of conditions and the following disclaimer.
  10. * 2. Redistributions in binary form must reproduce the above copyright
  11. * notice, this list of conditions and the following disclaimer in the
  12. * documentation and/or other materials provided with the distribution.
  13. * 3. Neither the name of the Institute nor the names of its contributors
  14. * may be used to endorse or promote products derived from this software
  15. * without specific prior written permission.
  16. *
  17. * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
  18. * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  19. * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  20. * ARE DISCLAIMED. IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
  21. * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  22. * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  23. * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  24. * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  25. * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  26. * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  27. * SUCH DAMAGE.
  28. *
  29. * This file is part of the Contiki operating system.
  30. */
  31.  
  32. /**
  33. * \file
  34. * RPL timer management.
  35. *
  36. * \author Joakim Eriksson <joakime@sics.se>, Nicolas Tsiftes <nvt@sics.se>
  37. */
  38.  
  39. /**
  40. * \addtogroup uip6
  41. * @{
  42. */
  43.  
  44. #include "contiki-conf.h"
  45. #include "net/rpl/rpl-private.h"
  46. #include "net/rpl/rpl-ns.h"
  47. #include "net/link-stats.h"
  48. #include "net/ipv6/multicast/uip-mcast6.h"
  49. #include "lib/random.h"
  50. #include "sys/ctimer.h"
  51.  
  52. #define DEBUG DEBUG_NONE
  53. #include "net/ip/uip-debug.h"
  54.  
  55. /* A configurable function called after update of the RPL DIO interval */
  56. #ifdef RPL_CALLBACK_NEW_DIO_INTERVAL
  57. void RPL_CALLBACK_NEW_DIO_INTERVAL(uint8_t dio_interval);
  58. #endif /* RPL_CALLBACK_NEW_DIO_INTERVAL */
  59.  
  60. #ifdef RPL_PROBING_SELECT_FUNC
  61. rpl_parent_t *RPL_PROBING_SELECT_FUNC(rpl_dag_t *dag);
  62. #endif /* RPL_PROBING_SELECT_FUNC */
  63.  
  64. #ifdef RPL_PROBING_DELAY_FUNC
  65. clock_time_t RPL_PROBING_DELAY_FUNC(rpl_dag_t *dag);
  66. #endif /* RPL_PROBING_DELAY_FUNC */
  67.  
  68. /*---------------------------------------------------------------------------*/
  69. static struct ctimer periodic_timer;
  70.  
  71. static void handle_periodic_timer(void *ptr);
  72. static void new_dio_interval(rpl_instance_t *instance);
  73. static void handle_dio_timer(void *ptr);
  74.  
  75. static uint16_t next_dis;
  76.  
  77. /* dio_send_ok is true if the node is ready to send DIOs */
  78. static uint8_t dio_send_ok;
  79.  
  80. /*---------------------------------------------------------------------------*/
  81. static void
  82. handle_periodic_timer(void *ptr)
  83. {
  84. rpl_dag_t *dag = rpl_get_any_dag();
  85.  
  86. rpl_purge_dags();
  87. if(dag != NULL) {
  88. if(RPL_IS_STORING(dag->instance)) {
  89. rpl_purge_routes();
  90. }
  91. if(RPL_IS_NON_STORING(dag->instance)) {
  92. rpl_ns_periodic();
  93. }
  94. }
  95. rpl_recalculate_ranks();
  96.  
  97. /* handle DIS */
  98. #if RPL_DIS_SEND
  99. next_dis++;
  100. if(dag == NULL && next_dis >= RPL_DIS_INTERVAL) {
  101. next_dis = 0;
  102. dis_output(NULL);
  103. }
  104. #endif
  105. ctimer_reset(&periodic_timer);
  106. }
  107. /*---------------------------------------------------------------------------*/
  108. static void
  109. new_dio_interval(rpl_instance_t *instance)
  110. {
  111. uint32_t time;
  112. clock_time_t ticks;
  113.  
  114. /* TODO: too small timer intervals for many cases */
  115. time = 1UL << instance->dio_intcurrent;
  116.  
  117. /* Convert from milliseconds to CLOCK_TICKS. */
  118. ticks = (time * CLOCK_SECOND) / 1000;
  119. instance->dio_next_delay = ticks;
  120.  
  121. /* random number between I/2 and I */
  122. ticks = ticks / 2 + (ticks / 2 * (uint32_t)random_rand()) / RANDOM_RAND_MAX;
  123.  
  124. /*
  125. * The intervals must be equally long among the nodes for Trickle to
  126. * operate efficiently. Therefore we need to calculate the delay between
  127. * the randomized time and the start time of the next interval.
  128. */
  129. instance->dio_next_delay -= ticks;
  130. instance->dio_send = 1;
  131.  
  132. #if RPL_CONF_STATS
  133. /* keep some stats */
  134. instance->dio_totint++;
  135. instance->dio_totrecv += instance->dio_counter;
  136. ANNOTATE("#A rank=%u.%u(%u),stats=%d %d %d %d,color=%s\n",
  137. DAG_RANK(instance->current_dag->rank, instance),
  138. (10 * (instance->current_dag->rank % instance->min_hoprankinc)) / instance->min_hoprankinc,
  139. instance->current_dag->version,
  140. instance->dio_totint, instance->dio_totsend,
  141. instance->dio_totrecv,instance->dio_intcurrent,
  142. instance->current_dag->rank == ROOT_RANK(instance) ? "BLUE" : "ORANGE");
  143. #endif /* RPL_CONF_STATS */
  144.  
  145. /* reset the redundancy counter */
  146. instance->dio_counter = 0;
  147.  
  148. /* schedule the timer */
  149. PRINTF("RPL: Scheduling DIO timer %lu ticks in future (Interval)\n", ticks);
  150. ctimer_set(&instance->dio_timer, ticks, &handle_dio_timer, instance);
  151.  
  152. #ifdef RPL_CALLBACK_NEW_DIO_INTERVAL
  153. RPL_CALLBACK_NEW_DIO_INTERVAL(instance->dio_intcurrent);
  154. #endif /* RPL_CALLBACK_NEW_DIO_INTERVAL */
  155. }
  156. /*---------------------------------------------------------------------------*/
  157. static void
  158. handle_dio_timer(void *ptr)
  159. {
  160. rpl_instance_t *instance;
  161.  
  162. instance = (rpl_instance_t *)ptr;
  163.  
  164. PRINTF("RPL: DIO Timer triggered\n");
  165. if(!dio_send_ok) {
  166. if(uip_ds6_get_link_local(ADDR_PREFERRED) != NULL) {
  167. dio_send_ok = 1;
  168. } else {
  169. PRINTF("RPL: Postponing DIO transmission since link local address is not ok\n");
  170. ctimer_set(&instance->dio_timer, CLOCK_SECOND, &handle_dio_timer, instance);
  171. return;
  172. }
  173. }
  174.  
  175. if(instance->dio_send) {
  176. /* send DIO if counter is less than desired redundancy */
  177. if(instance->dio_redundancy == 0 || instance->dio_counter < instance->dio_redundancy) {
  178. #if RPL_CONF_STATS
  179. instance->dio_totsend++;
  180. #endif /* RPL_CONF_STATS */
  181. dio_output(instance, NULL);
  182. } else {
  183. PRINTF("RPL: Suppressing DIO transmission (%d >= %d)\n",
  184. instance->dio_counter, instance->dio_redundancy);
  185. }
  186. instance->dio_send = 0;
  187. PRINTF("RPL: Scheduling DIO timer %lu ticks in future (sent)\n",
  188. instance->dio_next_delay);
  189. ctimer_set(&instance->dio_timer, instance->dio_next_delay, handle_dio_timer, instance);
  190. } else {
  191. /* check if we need to double interval */
  192. if(instance->dio_intcurrent < instance->dio_intmin + instance->dio_intdoubl) {
  193. instance->dio_intcurrent++;
  194. PRINTF("RPL: DIO Timer interval doubled %d\n", instance->dio_intcurrent);
  195. }
  196. new_dio_interval(instance);
  197. }
  198.  
  199. #if DEBUG
  200. rpl_print_neighbor_list();
  201. #endif
  202. }
  203. /*---------------------------------------------------------------------------*/
  204. void
  205. rpl_reset_periodic_timer(void)
  206. {
  207. next_dis = RPL_DIS_INTERVAL / 2 +
  208. ((uint32_t)RPL_DIS_INTERVAL * (uint32_t)random_rand()) / RANDOM_RAND_MAX -
  209. RPL_DIS_START_DELAY;
  210. ctimer_set(&periodic_timer, CLOCK_SECOND, handle_periodic_timer, NULL);
  211. }
  212. /*---------------------------------------------------------------------------*/
  213. /* Resets the DIO timer in the instance to its minimal interval. */
  214. void
  215. rpl_reset_dio_timer(rpl_instance_t *instance)
  216. {
  217. #if !RPL_LEAF_ONLY
  218. /* Do not reset if we are already on the minimum interval,
  219. unless forced to do so. */
  220. if(instance->dio_intcurrent > instance->dio_intmin) {
  221. instance->dio_counter = 0;
  222. instance->dio_intcurrent = instance->dio_intmin;
  223. new_dio_interval(instance);
  224. }
  225. #if RPL_CONF_STATS
  226. rpl_stats.resets++;
  227. #endif /* RPL_CONF_STATS */
  228. #endif /* RPL_LEAF_ONLY */
  229. }
  230. /*---------------------------------------------------------------------------*/
  231. static void handle_dao_timer(void *ptr);
  232. static void
  233. set_dao_lifetime_timer(rpl_instance_t *instance)
  234. {
  235. if(rpl_get_mode() == RPL_MODE_FEATHER) {
  236. return;
  237. }
  238.  
  239. /* Set up another DAO within half the expiration time, if such a
  240. time has been configured */
  241. if(instance->default_lifetime != RPL_INFINITE_LIFETIME) {
  242. clock_time_t expiration_time;
  243. expiration_time = (clock_time_t)instance->default_lifetime *
  244. (clock_time_t)instance->lifetime_unit *
  245. CLOCK_SECOND / 2;
  246. /* make the time for the re registration be betwen 1/2 - 3/4 of lifetime */
  247. expiration_time = expiration_time + (random_rand() % (expiration_time / 2));
  248. PRINTF("RPL: Scheduling DAO lifetime timer %u ticks in the future\n",
  249. (unsigned)expiration_time);
  250. ctimer_set(&instance->dao_lifetime_timer, expiration_time,
  251. handle_dao_timer, instance);
  252. }
  253. }
  254. /*---------------------------------------------------------------------------*/
  255. static void
  256. handle_dao_timer(void *ptr)
  257. {
  258. rpl_instance_t *instance;
  259. #if RPL_WITH_MULTICAST
  260. uip_mcast6_route_t *mcast_route;
  261. uint8_t i;
  262. #endif
  263.  
  264. instance = (rpl_instance_t *)ptr;
  265.  
  266. if(!dio_send_ok && uip_ds6_get_link_local(ADDR_PREFERRED) == NULL) {
  267. PRINTF("RPL: Postpone DAO transmission\n");
  268. ctimer_set(&instance->dao_timer, CLOCK_SECOND, handle_dao_timer, instance);
  269. return;
  270. }
  271.  
  272. /* Send the DAO to the DAO parent set -- the preferred parent in our case. */
  273. if(instance->current_dag->preferred_parent != NULL) {
  274. PRINTF("RPL: handle_dao_timer - sending DAO\n");
  275. /* Set the route lifetime to the default value. */
  276. dao_output(instance->current_dag->preferred_parent, instance->default_lifetime);
  277.  
  278. #if RPL_WITH_MULTICAST
  279. /* Send DAOs for multicast prefixes only if the instance is in MOP 3 */
  280. if(instance->mop == RPL_MOP_STORING_MULTICAST) {
  281. /* Send a DAO for own multicast addresses */
  282. for(i = 0; i < UIP_DS6_MADDR_NB; i++) {
  283. if(uip_ds6_if.maddr_list[i].isused
  284. && uip_is_addr_mcast_global(&uip_ds6_if.maddr_list[i].ipaddr)) {
  285. dao_output_target(instance->current_dag->preferred_parent,
  286. &uip_ds6_if.maddr_list[i].ipaddr, RPL_MCAST_LIFETIME);
  287. }
  288. }
  289.  
  290. /* Iterate over multicast routes and send DAOs */
  291. mcast_route = uip_mcast6_route_list_head();
  292. while(mcast_route != NULL) {
  293. /* Don't send if it's also our own address, done that already */
  294. if(uip_ds6_maddr_lookup(&mcast_route->group) == NULL) {
  295. dao_output_target(instance->current_dag->preferred_parent,
  296. &mcast_route->group, RPL_MCAST_LIFETIME);
  297. }
  298. mcast_route = list_item_next(mcast_route);
  299. }
  300. }
  301. #endif
  302. } else {
  303. PRINTF("RPL: No suitable DAO parent\n");
  304. }
  305.  
  306. ctimer_stop(&instance->dao_timer);
  307.  
  308. if(etimer_expired(&instance->dao_lifetime_timer.etimer)) {
  309. set_dao_lifetime_timer(instance);
  310. }
  311. }
  312. /*---------------------------------------------------------------------------*/
  313. static void
  314. schedule_dao(rpl_instance_t *instance, clock_time_t latency)
  315. {
  316. clock_time_t expiration_time;
  317.  
  318. if(rpl_get_mode() == RPL_MODE_FEATHER) {
  319. return;
  320. }
  321.  
  322. expiration_time = etimer_expiration_time(&instance->dao_timer.etimer);
  323.  
  324. if(!etimer_expired(&instance->dao_timer.etimer)) {
  325. PRINTF("RPL: DAO timer already scheduled\n");
  326. } else {
  327. if(latency != 0) {
  328. expiration_time = latency / 2 +
  329. (random_rand() % (latency));
  330. } else {
  331. expiration_time = 0;
  332. }
  333. PRINTF("RPL: Scheduling DAO timer %u ticks in the future\n",
  334. (unsigned)expiration_time);
  335. ctimer_set(&instance->dao_timer, expiration_time,
  336. handle_dao_timer, instance);
  337.  
  338. set_dao_lifetime_timer(instance);
  339. }
  340. }
  341. /*---------------------------------------------------------------------------*/
  342. void
  343. rpl_schedule_dao(rpl_instance_t *instance)
  344. {
  345. schedule_dao(instance, RPL_DAO_DELAY);
  346. }
  347. /*---------------------------------------------------------------------------*/
  348. void
  349. rpl_schedule_dao_immediately(rpl_instance_t *instance)
  350. {
  351. schedule_dao(instance, 0);
  352. }
  353. /*---------------------------------------------------------------------------*/
  354. void
  355. rpl_cancel_dao(rpl_instance_t *instance)
  356. {
  357. ctimer_stop(&instance->dao_timer);
  358. ctimer_stop(&instance->dao_lifetime_timer);
  359. }
  360. /*---------------------------------------------------------------------------*/
  361. static void
  362. handle_unicast_dio_timer(void *ptr)
  363. {
  364. rpl_instance_t *instance = (rpl_instance_t *)ptr;
  365. uip_ipaddr_t *target_ipaddr = rpl_get_parent_ipaddr(instance->unicast_dio_target);
  366.  
  367. if(target_ipaddr != NULL) {
  368. dio_output(instance, target_ipaddr);
  369. }
  370. }
  371. /*---------------------------------------------------------------------------*/
  372. void
  373. rpl_schedule_unicast_dio_immediately(rpl_instance_t *instance)
  374. {
  375. ctimer_set(&instance->unicast_dio_timer, 0,
  376. handle_unicast_dio_timer, instance);
  377. }
  378. /*---------------------------------------------------------------------------*/
  379. #if RPL_WITH_PROBING
  380. clock_time_t
  381. get_probing_delay(rpl_dag_t *dag)
  382. {
  383. if(dag != NULL && dag->instance != NULL
  384. && dag->instance->urgent_probing_target != NULL) {
  385. /* Urgent probing needed (to find out if a neighbor may become preferred parent) */
  386. return random_rand() % (CLOCK_SECOND * 10);
  387. } else {
  388. /* Else, use normal probing interval */
  389. return ((RPL_PROBING_INTERVAL) / 2) + random_rand() % (RPL_PROBING_INTERVAL);
  390. }
  391. }
  392. /*---------------------------------------------------------------------------*/
  393. rpl_parent_t *
  394. get_probing_target(rpl_dag_t *dag)
  395. {
  396. /* Returns the next probing target. The current implementation probes the urgent
  397. * probing target if any, or the preferred parent if its link statistics need refresh.
  398. * Otherwise, it picks at random between:
  399. * (1) selecting the best parent with non-fresh link statistics
  400. * (2) selecting the least recently updated parent
  401. */
  402.  
  403. rpl_parent_t *p;
  404. rpl_parent_t *probing_target = NULL;
  405. rpl_rank_t probing_target_rank = INFINITE_RANK;
  406. clock_time_t probing_target_age = 0;
  407. clock_time_t clock_now = clock_time();
  408.  
  409. if(dag == NULL ||
  410. dag->instance == NULL) {
  411. return NULL;
  412. }
  413.  
  414. /* There is an urgent probing target */
  415. if(dag->instance->urgent_probing_target != NULL) {
  416. return dag->instance->urgent_probing_target;
  417. }
  418.  
  419. /* The preferred parent needs probing */
  420. if(dag->preferred_parent != NULL && !rpl_parent_is_fresh(dag->preferred_parent)) {
  421. return dag->preferred_parent;
  422. }
  423.  
  424. /* With 50% probability: probe best non-fresh parent */
  425. if(random_rand() % 2 == 0) {
  426. p = nbr_table_head(rpl_parents);
  427. while(p != NULL) {
  428. if(p->dag == dag && !rpl_parent_is_fresh(p)) {
  429. /* p is in our dag and needs probing */
  430. rpl_rank_t p_rank = rpl_rank_via_parent(p);
  431. if(probing_target == NULL
  432. || p_rank < probing_target_rank) {
  433. probing_target = p;
  434. probing_target_rank = p_rank;
  435. }
  436. }
  437. p = nbr_table_next(rpl_parents, p);
  438. }
  439. }
  440.  
  441. /* If we still do not have a probing target: pick the least recently updated parent */
  442. if(probing_target == NULL) {
  443. p = nbr_table_head(rpl_parents);
  444. while(p != NULL) {
  445. const struct link_stats *stats =rpl_get_parent_link_stats(p);
  446. if(p->dag == dag && stats != NULL) {
  447. if(probing_target == NULL
  448. || clock_now - stats->last_tx_time > probing_target_age) {
  449. probing_target = p;
  450. probing_target_age = clock_now - stats->last_tx_time;
  451. }
  452. }
  453. p = nbr_table_next(rpl_parents, p);
  454. }
  455. }
  456.  
  457. return probing_target;
  458. }
  459. /*---------------------------------------------------------------------------*/
  460. static void
  461. handle_probing_timer(void *ptr)
  462. {
  463. rpl_instance_t *instance = (rpl_instance_t *)ptr;
  464. rpl_parent_t *probing_target = RPL_PROBING_SELECT_FUNC(instance->current_dag);
  465. uip_ipaddr_t *target_ipaddr = rpl_get_parent_ipaddr(probing_target);
  466.  
  467. /* Perform probing */
  468. if(target_ipaddr != NULL) {
  469. const struct link_stats *stats = rpl_get_parent_link_stats(probing_target);
  470. (void)stats;
  471. PRINTF("RPL: probing %u %s last tx %u min ago\n",
  472. rpl_get_parent_lladdr(probing_target)->u8[7],
  473. instance->urgent_probing_target != NULL ? "(urgent)" : "",
  474. probing_target != NULL ?
  475. (unsigned)((clock_time() - stats->last_tx_time) / (60 * CLOCK_SECOND)) : 0
  476. );
  477. /* Send probe, e.g. unicast DIO or DIS */
  478. RPL_PROBING_SEND_FUNC(instance, target_ipaddr);
  479. instance->urgent_probing_target = NULL;
  480. }
  481.  
  482. /* Schedule next probing */
  483. rpl_schedule_probing(instance);
  484.  
  485. #if DEBUG
  486. rpl_print_neighbor_list();
  487. #endif
  488. }
  489. /*---------------------------------------------------------------------------*/
  490. void
  491. rpl_schedule_probing(rpl_instance_t *instance)
  492. {
  493. ctimer_set(&instance->probing_timer, RPL_PROBING_DELAY_FUNC(instance->current_dag),
  494. handle_probing_timer, instance);
  495. }
  496. #endif /* RPL_WITH_PROBING */
  497. /** @}*/
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!