3 * The olsr.org Optimized Link-State Routing daemon(olsrd)
4 * Copyright (c) 2004, Andreas Tonnesen(andreto@olsr.org)
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
11 * * Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * * Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in
15 * the documentation and/or other materials provided with the
17 * * Neither the name of olsr.org, olsrd nor the names of its
18 * contributors may be used to endorse or promote products derived
19 * from this software without specific prior written permission.
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
25 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
27 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
29 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
31 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
32 * POSSIBILITY OF SUCH DAMAGE.
34 * Visit http://www.olsr.org for more information.
36 * If you find this software useful feel free to make a donation
37 * to the project. For more information see the website or contact
38 * the copyright holders.
43 * Link sensing database for the OLSR routing daemon
49 #include "hysteresis.h"
52 #include "neighbor_table.h"
55 #include "scheduler.h"
59 #include "lq_plugin.h"
61 /* head node for all link sets */
62 struct list_node link_entry_head;
64 bool link_changes = false; /* is set if changes occur in MPRS set */
67 signal_link_changes(bool val)
73 static int check_link_status(const struct hello_message *message, const struct interface_olsr *in_if);
74 static struct link_entry *add_link_entry(const union olsr_ip_addr *, const union olsr_ip_addr *, const union olsr_ip_addr *,
75 olsr_reltime, olsr_reltime, const struct interface_olsr *);
76 static int get_neighbor_status(const union olsr_ip_addr *);
77 static void olsr_expire_link_sym_timer(void *context);
80 olsr_init_link_set(void)
84 list_head_init(&link_entry_head);
88 * This function resets all links to lost, so that
89 * a final "lost all links" hello can be generated to
90 * tell your neighbors that you are gone now.
92 void olsr_reset_all_links(void) {
93 struct link_entry *link;
95 OLSR_FOR_ALL_LINK_ENTRIES(link) {
96 link->ASYM_time = now_times-1;
98 olsr_stop_timer(link->link_sym_timer);
99 link->link_sym_timer = NULL;
101 link->neighbor->is_mpr = false;
102 link->neighbor->status = NOT_SYM;
103 } OLSR_FOR_ALL_LINK_ENTRIES_END(link)
106 OLSR_FOR_ALL_LINK_ENTRIES(link) {
107 olsr_expire_link_sym_timer(link);
108 olsr_clear_hello_lq(link);
109 } OLSR_FOR_ALL_LINK_ENTRIES_END(link)
113 * Get the status of a link. The status is based upon different
114 * timeouts in the link entry.
116 * @param entry link entry
117 * @return the link status of the link
120 lookup_link_status(const struct link_entry *entry)
123 if (entry == NULL || list_is_empty(&link_entry_head)) {
130 if (olsr_cnf->use_hysteresis) {
133 * if L_LOST_LINK_time is not expired, the link is advertised
134 * with a link type of LOST_LINK.
137 if (!TIMED_OUT(entry->L_LOST_LINK_time)) {
142 * otherwise, if L_LOST_LINK_time is expired and L_link_pending
143 * is set to "true", the link SHOULD NOT be advertised at all;
145 if (entry->L_link_pending == 1) {
147 struct ipaddr_str buf;
148 OLSR_PRINTF(3, "HYST[%s]: Setting to HIDE\n", olsr_ip_to_string(&buf, &entry->neighbor_iface_addr));
154 * otherwise, if L_LOST_LINK_time is expired and L_link_pending
155 * is set to "false", the link is advertised as described
156 * previously in section 6.
160 if (entry->link_sym_timer) {
164 if (!TIMED_OUT(entry->ASYM_time)) {
172 * Find the "best" link status to a neighbor
174 * @param address the address to check for
175 * @return SYM_LINK if a symmetric link exists 0 if not
178 get_neighbor_status(const union olsr_ip_addr *address)
180 const union olsr_ip_addr *main_addr;
181 struct interface_olsr *ifs;
183 /* Find main address */
184 if (!(main_addr = mid_lookup_main_addr(address)))
187 /* Loop trough local interfaces to check all possebilities */
188 for (ifs = ifnet; ifs != NULL; ifs = ifs->int_next) {
189 struct mid_address *aliases;
190 struct link_entry *lnk = lookup_link_entry(main_addr, NULL, ifs);
193 if (lookup_link_status(lnk) == SYM_LINK)
198 for (aliases = mid_lookup_aliases(main_addr); aliases != NULL; aliases = aliases->next_alias) {
200 lnk = lookup_link_entry(&aliases->alias, NULL, ifs);
201 if (lnk && (lookup_link_status(lnk) == SYM_LINK)) {
211 * Find best link to a neighbor
214 get_best_link_to_neighbor(const union olsr_ip_addr *remote)
216 const union olsr_ip_addr *main_addr;
217 struct link_entry *walker, *good_link, *backup_link;
218 struct interface_olsr *tmp_if;
219 int curr_metric = MAX_IF_METRIC;
220 olsr_linkcost curr_lcost = LINK_COST_BROKEN;
221 olsr_linkcost tmp_lc;
223 /* main address lookup */
224 main_addr = mid_lookup_main_addr(remote);
226 /* "remote" *already is* the main address */
231 /* we haven't selected any links, yet */
235 /* loop through all links that we have */
236 OLSR_FOR_ALL_LINK_ENTRIES(walker) {
238 /* if this is not a link to the neighour in question, skip */
239 if (!ipequal(&walker->neighbor->neighbor_main_addr, main_addr))
242 if (olsr_cnf->lq_level == 0) {
245 * handle the non-LQ, RFC-compliant case
249 * find the interface for the link.
250 * we select the link with the best local interface metric.
252 tmp_if = walker->if_name ? if_ifwithname(walker->if_name) : if_ifwithaddr(&walker->local_iface_addr);
259 * is this interface better than anything we had before ?
260 * use the requested remote interface address as a tie-breaker
262 if ((tmp_if->int_metric < curr_metric) || ((tmp_if->int_metric == curr_metric) && ipequal(&walker->local_iface_addr, remote))) {
264 /* memorize the interface's metric */
265 curr_metric = tmp_if->int_metric;
267 /* prefer symmetric links over asymmetric links */
268 if (lookup_link_status(walker) == SYM_LINK) {
271 backup_link = walker;
277 * handle the LQ, non-RFC compliant case.
280 /* get the link cost */
281 tmp_lc = walker->linkcost;
284 * is this link better than anything we had before ?
285 * use the requested remote interface address as a tie-breaker.
287 if ((tmp_lc < curr_lcost) || ((tmp_lc == curr_lcost) && ipequal(&walker->local_iface_addr, remote))) {
289 /* memorize the link quality */
292 /* prefer symmetric links over asymmetric links */
293 if (lookup_link_status(walker) == SYM_LINK) {
296 backup_link = walker;
301 OLSR_FOR_ALL_LINK_ENTRIES_END(walker);
304 * if we haven't found any symmetric links, try to return an asymmetric link.
306 return good_link ? good_link : backup_link;
310 set_loss_link_multiplier(struct link_entry *entry)
312 struct interface_olsr *inter = NULL;
313 struct olsr_if *cfg_inter = NULL;
314 struct olsr_lq_mult *mult;
316 union olsr_ip_addr null_addr;
317 struct ipaddr_str buf;
319 /* find the interface for the link */
320 assert(entry->if_name);
321 inter = if_ifwithname(entry->if_name);
324 /* find the interface configuration for the interface */
325 for (cfg_inter = olsr_cnf->interfaces; cfg_inter; cfg_inter = cfg_inter->next) {
326 if (cfg_inter->interf == inter) {
333 /* create a null address for comparison */
334 memset(&null_addr, 0, sizeof(union olsr_ip_addr));
336 /* loop through the multiplier entries */
337 for (mult = cfg_inter->cnf->lq_mult; mult != NULL; mult = mult->next) {
340 * use the default multiplier only if there isn't any entry that
341 * has a matching IP address.
343 if ((ipequal(&mult->addr, &null_addr) && val == 0) || ipequal(&mult->addr, &entry->neighbor_iface_addr)) {
349 /* if we have not found an entry, then use the default multiplier */
351 val = LINK_LOSS_MULTIPLIER;
354 /* store the multiplier */
355 entry->loss_link_multiplier = val;
357 OLSR_PRINTF(1, "Set linkloss multiplier for %s on %s to %d\n",
358 olsr_ip_to_string(&buf, &entry->neighbor_iface_addr), cfg_inter->name, val);
362 * Delete, unlink and free a link entry.
365 olsr_delete_link_entry(struct link_entry *link)
367 struct tc_edge_entry *tc_edge;
369 /* delete tc edges we made for SPF */
370 tc_edge = olsr_lookup_tc_edge(tc_myself, &link->neighbor_iface_addr);
371 if (tc_edge != NULL) {
372 olsr_delete_tc_edge_entry(tc_edge);
376 /* Delete neighbor entry */
377 if (link->neighbor->linkcount == 1) {
378 olsr_delete_neighbor_table(&link->neighbor->neighbor_main_addr);
380 link->neighbor->linkcount--;
383 /* Kill running timers */
384 olsr_stop_timer(link->link_timer);
385 link->link_timer = NULL;
386 olsr_stop_timer(link->link_sym_timer);
387 link->link_sym_timer = NULL;
388 olsr_stop_timer(link->link_hello_timer);
389 link->link_hello_timer = NULL;
390 olsr_stop_timer(link->link_loss_timer);
391 link->link_loss_timer = NULL;
392 list_remove(&link->link_list);
397 changes_neighborhood = true;
401 * Delete all link entries matching a given interface address.
404 olsr_delete_link_entry_by_ip(const union olsr_ip_addr *int_addr)
406 struct link_entry *link;
408 if (list_is_empty(&link_entry_head)) {
412 OLSR_FOR_ALL_LINK_ENTRIES(link) {
413 if (ipequal(int_addr, &link->local_iface_addr)) {
414 olsr_delete_link_entry(link);
417 OLSR_FOR_ALL_LINK_ENTRIES_END(link);
422 * Callback for the link loss timer.
425 olsr_expire_link_loss_timer(void *context)
427 struct link_entry *link;
429 link = (struct link_entry *)context;
431 /* count the lost packet */
432 olsr_update_packet_loss_worker(link, true);
434 /* next timeout in 1.0 x htime */
435 olsr_change_timer(link->link_loss_timer, link->loss_helloint, OLSR_LINK_LOSS_JITTER, OLSR_TIMER_PERIODIC);
440 * Callback for the link SYM timer.
443 olsr_expire_link_sym_timer(void *context)
445 struct link_entry *link;
447 link = (struct link_entry *)context;
448 link->link_sym_timer = NULL; /* be pedandic */
450 if (link->prev_status != SYM_LINK) {
454 link->prev_status = lookup_link_status(link);
455 update_neighbor_status(link->neighbor, get_neighbor_status(&link->neighbor_iface_addr));
456 changes_neighborhood = true;
460 * Callback for the link_hello timer.
463 olsr_expire_link_hello_timer(void *context)
465 struct ipaddr_str buf;
466 struct link_entry *link;
468 link = (struct link_entry *)context;
470 link->L_link_quality = olsr_hyst_calc_instability(link->L_link_quality);
472 OLSR_PRINTF(1, "HYST[%s] HELLO timeout %f\n", olsr_ip_to_string(&buf, &link->neighbor_iface_addr), (double)link->L_link_quality);
474 /* Update hello_timeout - NO SLACK THIS TIME */
475 olsr_change_timer(link->link_hello_timer, link->last_htime, OLSR_LINK_JITTER, OLSR_TIMER_PERIODIC);
477 /* Update hysteresis values */
478 olsr_process_hysteresis(link);
480 /* update neighbor status */
481 update_neighbor_status(link->neighbor, get_neighbor_status(&link->neighbor_iface_addr));
483 /* Update seqno - not mentioned in the RFC... kind of a hack.. */
488 * Callback for the link timer.
491 olsr_expire_link_entry(void *context)
493 struct link_entry *link;
495 link = (struct link_entry *)context;
496 link->link_timer = NULL; /* be pedandic */
498 olsr_delete_link_entry(link);
502 * Set the link expiration timer.
505 olsr_set_link_timer(struct link_entry *link, unsigned int rel_timer)
507 struct ipaddr_str buf;
509 OLSR_PRINTF(3, "reset link timer: %s = %u\n",
510 olsr_ip_to_string(&buf, &link->neighbor_iface_addr),
511 (unsigned int)(now_times + rel_timer/1000));
512 olsr_set_timer(&link->link_timer, rel_timer, OLSR_LINK_JITTER, OLSR_TIMER_ONESHOT, &olsr_expire_link_entry, link, 0);
516 * Nothing mysterious here.
517 * Adding a new link entry to the link set.
519 * @param local the local IP address
520 * @param remote the remote IP address
521 * @param remote_main the remote nodes main address
522 * @param vtime the validity time of the entry
523 * @param htime the HELLO interval of the remote node
524 * @param local_if the local interface
525 * @return the new link_entry
527 static struct link_entry *
528 add_link_entry(const union olsr_ip_addr *local, const union olsr_ip_addr *remote, const union olsr_ip_addr *remote_main,
529 olsr_reltime vtime, olsr_reltime htime, const struct interface_olsr *local_if)
531 struct link_entry *new_link;
532 struct neighbor_entry *neighbor;
533 struct link_entry *tmp_link_set;
535 tmp_link_set = lookup_link_entry(remote, remote_main, local_if);
541 * if there exists no link tuple with
542 * L_neighbor_iface_addr == Source Address
547 struct ipaddr_str localbuf, rembuf;
548 OLSR_PRINTF(1, "Adding %s=>%s to link set\n", olsr_ip_to_string(&localbuf, local), olsr_ip_to_string(&rembuf, remote));
552 /* a new tuple is created with... */
553 new_link = olsr_malloc_link_entry("new link entry");
555 /* copy if_name, if it is defined */
556 if (local_if->int_name) {
557 size_t name_size = strlen(local_if->int_name) + 1;
558 new_link->if_name = olsr_malloc(name_size, "target of if_name in new link entry");
559 strscpy(new_link->if_name, local_if->int_name, name_size);
561 new_link->if_name = NULL;
563 /* shortcut to interface. XXX refcount */
564 new_link->inter = local_if;
567 * L_local_iface_addr = Address of the interface
568 * which received the HELLO message
570 new_link->local_iface_addr = *local;
572 /* L_neighbor_iface_addr = Source Address */
573 new_link->neighbor_iface_addr = *remote;
575 /* L_time = current time + validity time */
576 olsr_set_link_timer(new_link, vtime);
578 new_link->prev_status = ASYM_LINK;
581 if (olsr_cnf->use_hysteresis) {
582 new_link->L_link_pending = 1;
583 new_link->L_LOST_LINK_time = GET_TIMESTAMP(vtime);
584 olsr_update_hysteresis_hello(new_link, htime);
585 new_link->last_htime = htime;
586 new_link->olsr_seqno = 0;
587 new_link->olsr_seqno_valid = false;
590 new_link->L_link_quality = 0.0;
592 if (olsr_cnf->lq_level > 0) {
593 new_link->loss_helloint = htime;
595 olsr_set_timer(&new_link->link_loss_timer, htime + htime / 2, OLSR_LINK_LOSS_JITTER, OLSR_TIMER_PERIODIC,
596 &olsr_expire_link_loss_timer, new_link, 0);
598 set_loss_link_multiplier(new_link);
601 new_link->linkcost = LINK_COST_BROKEN;
604 list_add_before(&link_entry_head, &new_link->link_list);
607 * Create the neighbor entry
610 /* Neighbor MUST exist! */
611 neighbor = olsr_lookup_neighbor_table(remote_main);
614 struct ipaddr_str buf;
615 OLSR_PRINTF(3, "ADDING NEW NEIGHBOR ENTRY %s FROM LINK SET\n", olsr_ip_to_string(&buf, remote_main));
617 neighbor = olsr_insert_neighbor_table(remote_main);
620 neighbor->linkcount++;
621 new_link->neighbor = neighbor;
627 * Lookup the status of a link.
629 * @param int_addr address of the remote interface
630 * @return 1 of the link is symmertic 0 if not
633 check_neighbor_link(const union olsr_ip_addr *int_addr)
635 struct link_entry *link;
637 OLSR_FOR_ALL_LINK_ENTRIES(link) {
638 if (ipequal(int_addr, &link->neighbor_iface_addr)) {
639 return lookup_link_status(link);
642 OLSR_FOR_ALL_LINK_ENTRIES_END(link);
648 * Lookup a link entry
650 * @param remote the remote interface address
651 * @param remote_main the remote nodes main address
652 * @param local the local interface address
653 * @return the link entry if found, NULL if not
656 lookup_link_entry(const union olsr_ip_addr *remote, const union olsr_ip_addr *remote_main, const struct interface_olsr *local)
658 struct link_entry *link;
660 OLSR_FOR_ALL_LINK_ENTRIES(link) {
661 if (ipequal(remote, &link->neighbor_iface_addr)
662 && (link->if_name ? !strcmp(link->if_name, local->int_name) : ipequal(&local->ip_addr, &link->local_iface_addr))) {
663 /* check the remote-main address only if there is one given */
664 if (NULL != remote_main && !ipequal(remote_main, &link->neighbor->neighbor_main_addr)) {
665 /* Neighbor has changed it's main_addr, update */
666 struct ipaddr_str oldbuf, newbuf;
668 OLSR_PRINTF(1, "Neighbor changed main_ip, updating %s -> %s\n",
669 olsr_ip_to_string(&oldbuf, &link->neighbor->neighbor_main_addr), olsr_ip_to_string(&newbuf, remote_main));
670 olsr_update_neighbor_main_addr(link->neighbor, remote_main);
675 OLSR_FOR_ALL_LINK_ENTRIES_END(link);
681 * Update a link entry. This is the "main entrypoint" in
682 * the link-sensing. This function is called from the HELLO
683 * parser function. It makes sure a entry is updated or created.
685 * @param local the local IP address
686 * @param remote the remote IP address
687 * @param message the HELLO message
688 * @param in_if the interface on which this HELLO was received
689 * @return the link_entry struct describing this link entry
692 update_link_entry(const union olsr_ip_addr *local, const union olsr_ip_addr *remote, const struct hello_message *message,
693 const struct interface_olsr *in_if)
695 struct link_entry *entry;
697 /* Add if not registered */
698 entry = add_link_entry(local, remote, &message->source_addr, message->vtime, message->htime, in_if);
700 /* Update ASYM_time */
701 entry->vtime = message->vtime;
702 entry->ASYM_time = GET_TIMESTAMP(message->vtime);
704 entry->prev_status = check_link_status(message, in_if);
706 switch (entry->prev_status) {
708 olsr_stop_timer(entry->link_sym_timer);
709 entry->link_sym_timer = NULL;
714 /* L_SYM_time = current time + validity time */
715 olsr_set_timer(&entry->link_sym_timer, message->vtime, OLSR_LINK_SYM_JITTER, OLSR_TIMER_ONESHOT, &olsr_expire_link_sym_timer,
718 /* L_time = L_SYM_time + NEIGHB_HOLD_TIME */
719 olsr_set_link_timer(entry, message->vtime + NEIGHB_HOLD_TIME * MSEC_PER_SEC);
725 /* L_time = max(L_time, L_ASYM_time) */
726 if (entry->link_timer == NULL || (entry->link_timer->timer_clock < entry->ASYM_time)) {
727 olsr_set_link_timer(entry, TIME_DUE(entry->ASYM_time));
730 /* Update hysteresis values */
731 if (olsr_cnf->use_hysteresis)
732 olsr_process_hysteresis(entry);
734 /* Update neighbor */
735 update_neighbor_status(entry->neighbor, get_neighbor_status(remote));
741 * Function that updates all registered pointers to
742 * one neighbor entry with another pointer
743 * Used by MID updates.
745 * @param old the pointer to replace
746 * @param new the pointer to use instead of "old"
747 * @return the number of entries updated
750 replace_neighbor_link_set(const struct neighbor_entry *old, struct neighbor_entry *new)
752 struct link_entry *link;
755 if (list_is_empty(&link_entry_head)) {
759 OLSR_FOR_ALL_LINK_ENTRIES(link) {
761 if (link->neighbor == old) {
762 link->neighbor = new;
766 OLSR_FOR_ALL_LINK_ENTRIES_END(link);
772 *Checks the link status to a neighbor by
773 *looking in a received HELLO message.
775 *@param message the HELLO message to check
776 *@param in_if the incoming interface
778 *@return the link status
781 check_link_status(const struct hello_message *message, const struct interface_olsr *in_if)
783 int ret = UNSPEC_LINK;
784 struct hello_neighbor *neighbors;
786 neighbors = message->neighbors;
790 * Note: If a neigh has 2 cards we can reach, the neigh
791 * will send a Hello with the same IP mentined twice
793 if (ipequal(&neighbors->address, &in_if->ip_addr) &&
794 neighbors->link != UNSPEC_LINK) {
795 ret = neighbors->link;
796 if (SYM_LINK == ret) {
800 neighbors = neighbors->next;
808 olsr_print_link_set(void)
810 /* The whole function makes no sense without it. */
811 struct link_entry *walker;
812 const int addrsize = olsr_cnf->ip_version == AF_INET ? (INET_ADDRSTRLEN - 1) : (INET6_ADDRSTRLEN - 1);
814 OLSR_PRINTF(0, "\n--- %s ---------------------------------------------------- LINKS\n\n", olsr_wallclock_string());
815 OLSR_PRINTF(1, "%-*s %-6s %-14s %s\n", addrsize, "IP address", "hyst", " LQ ", "ETX");
817 OLSR_FOR_ALL_LINK_ENTRIES(walker) {
819 struct ipaddr_str buf;
820 struct lqtextbuffer lqbuffer1, lqbuffer2;
821 OLSR_PRINTF(1, "%-*s %5.3f %-14s %s\n", addrsize, olsr_ip_to_string(&buf, &walker->neighbor_iface_addr),
822 (double)walker->L_link_quality,
823 get_link_entry_text(walker, '/', &lqbuffer1),
824 get_linkcost_text(walker->linkcost,false, &lqbuffer2));
825 } OLSR_FOR_ALL_LINK_ENTRIES_END(walker);
830 * called for every LQ HELLO message.
831 * update the timeout with the htime value from the message
834 olsr_update_packet_loss_hello_int(struct link_entry *entry, olsr_reltime loss_hello_int)
836 entry->loss_helloint = loss_hello_int;
840 olsr_received_hello_handler(struct link_entry *entry)
842 olsr_update_packet_loss_worker(entry, false);
844 /* timeout for the first lost packet is 1.5 x htime */
845 olsr_set_timer(&entry->link_loss_timer, entry->loss_helloint + entry->loss_helloint / 2, OLSR_LINK_LOSS_JITTER,
846 OLSR_TIMER_PERIODIC, &olsr_expire_link_loss_timer, entry, 0);
852 * indent-tabs-mode: nil