src/lq_route.c

   1 /*
   2  * The olsr.org Optimized Link-State Routing daemon(olsrd)
   3  * Copyright (c) 2004, Thomas Lopatic (thomas@lopatic.de)
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  *
  10  * * Redistributions of source code must retain the above copyright
  11  *   notice, this list of conditions and the following disclaimer.
  12  * * Redistributions in binary form must reproduce the above copyright
  13  *   notice, this list of conditions and the following disclaimer in
  14  *   the documentation and/or other materials provided with the
  15  *   distribution.
  16  * * Neither the name of olsr.org, olsrd nor the names of its
  17  *   contributors may be used to endorse or promote products derived
  18  *   from this software without specific prior written permission.
  19  *
  20  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  21  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  22  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  23  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
  24  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  25  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
  26  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  27  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  28  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  29  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
  30  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  31  * POSSIBILITY OF SUCH DAMAGE.
  32  *
  33  * Visit http://www.olsr.org for more information.
  34  *
  35  * If you find this software useful feel free to make a donation
  36  * to the project. For more information see the website or contact
  37  * the copyright holders.
  38  *
  39  * $Id: lq_route.c,v 1.27 2005/02/17 02:06:22 tlopatic Exp $
  40  */
  41
  42 #include "defs.h"
  43 #include "tc_set.h"
  44 #include "neighbor_table.h"
  45 #include "two_hop_neighbor_table.h"
  46 #include "link_set.h"
  47 #include "routing_table.h"
  48 #include "mid_set.h"
  49 #include "hna_set.h"
  50 #include "lq_list.h"
  51 #include "lq_avl.h"
  52 #include "lq_route.h"
  53
  54 struct dijk_edge
  55 {
  56   struct avl_node tree_node;
  57   struct list_node node;
  58   struct dijk_vertex *dest;
  59   float etx;
  60 };
  61
  62 struct dijk_vertex
  63 {
  64   struct avl_node tree_node;
  65   struct list_node node;
  66   union olsr_ip_addr addr;
  67   struct avl_tree edge_tree;
  68   struct list edge_list;
  69   float path_etx;
  70   struct dijk_vertex *prev;
  71   olsr_bool done;
  72 };
  73
  74 static int avl_comp_ipv6(void *ip1, void *ip2)
  75 {
  76   return memcmp(ip1, ip2, ipsize);
  77 }
  78
  79 static int avl_comp_ipv4(void *ip1, void *ip2)
  80 {
  81   if (*(unsigned int *)ip1 < *(unsigned int *)ip2)
  82     return -1;
  83
  84   if (*(unsigned int *)ip1 == *(unsigned int *)ip2)
  85     return 0;
  86
  87   return 1;
  88 }
  89
  90 static int (*avl_comp)(void *, void *);
  91
  92 static void add_vertex(struct avl_tree *vertex_tree, struct list *vertex_list,
  93                        union olsr_ip_addr *addr, float path_etx)
  94 {
  95   struct avl_node *node;
  96   struct dijk_vertex *vert;
  97
  98   // see whether this destination is already in our list
  99
 100   node = avl_find(vertex_tree, addr);
 101
 102   // if it's not in our list, add it
 103
 104   if (node == NULL)
 105   {
 106     vert = olsr_malloc(sizeof (struct dijk_vertex), "Dijkstra vertex");
 107
 108     vert->tree_node.data = vert;
 109     vert->tree_node.key = &vert->addr;
 110
 111     vert->node.data = vert;
 112
 113     COPY_IP(&vert->addr, addr);
 114
 115     vert->path_etx = path_etx;
 116     vert->prev = NULL;
 117     vert->done = OLSR_FALSE;
 118
 119     avl_init(&vert->edge_tree, avl_comp);
 120     list_init(&vert->edge_list);
 121
 122     avl_insert(vertex_tree, &vert->tree_node);
 123     list_add_tail(vertex_list, &vert->node);
 124   }
 125 }
 126
 127 static void add_edge(struct avl_tree *vertex_tree, struct list *vertex_list,
 128                      union olsr_ip_addr *src, union olsr_ip_addr *dst,
 129                      float etx)
 130 {
 131   struct avl_node *node;
 132   struct dijk_vertex *svert;
 133   struct dijk_vertex *dvert;
 134   struct dijk_edge *edge;
 135
 136   // source lookup
 137
 138   node = avl_find(vertex_tree, src);
 139
 140   // source vertex does not exist
 141
 142   if (node == NULL)
 143     return;
 144
 145   svert = node->data;
 146
 147   // destination lookup
 148
 149   node = avl_find(vertex_tree, dst);
 150
 151   // destination vertex does not exist
 152
 153   if (node == NULL)
 154     return;
 155
 156   dvert = node->data;
 157
 158   // check for existing forward edge
 159
 160   if (avl_find(&svert->edge_tree, dst) == NULL)
 161   {
 162     // add forward edge
 163
 164     edge = olsr_malloc(sizeof (struct dijk_vertex), "Dijkstra edge 1");
 165
 166     edge->tree_node.data = edge;
 167     edge->tree_node.key = &dvert->addr;
 168
 169     edge->node.data = edge;
 170
 171     edge->dest = dvert;
 172     edge->etx = etx;
 173
 174     avl_insert(&svert->edge_tree, &edge->tree_node);
 175     list_add_tail(&svert->edge_list, &edge->node);
 176   }
 177
 178   // check for existing inverse edge
 179
 180   if (avl_find(&dvert->edge_tree, src) == NULL)
 181   {
 182     // add inverse edge
 183
 184     edge = olsr_malloc(sizeof (struct dijk_vertex), "Dijkstra edge 2");
 185
 186     edge->tree_node.data = edge;
 187     edge->tree_node.key = &svert->addr;
 188
 189     edge->node.data = edge;
 190
 191     edge->dest = svert;
 192     edge->etx = etx;
 193
 194     avl_insert(&dvert->edge_tree, &edge->tree_node);
 195     list_add_tail(&dvert->edge_list, &edge->node);
 196   }
 197 }
 198
 199 static void free_everything(struct list *vertex_list)
 200 {
 201   struct list_node *vnode, *enode;
 202   struct dijk_vertex *vert;
 203   struct dijk_edge *edge;
 204
 205   vnode = list_get_head(vertex_list);
 206
 207   // loop through all vertices
 208
 209   while (vnode != NULL)
 210   {
 211     vert = vnode->data;
 212
 213     enode = list_get_head(&vert->edge_list);
 214
 215     // loop through all edges of the current vertex
 216
 217     while (enode != NULL)
 218     {
 219       edge = enode->data;
 220
 221       enode = list_get_next(enode);
 222       free(edge);
 223     }
 224
 225     vnode = list_get_next(vnode);
 226     free(vert);
 227   }
 228 }
 229
 230 // XXX - bad complexity
 231
 232 static struct dijk_vertex *extract_best(struct list *vertex_list)
 233 {
 234   float best_etx = INFINITE_ETX + 1.0;
 235   struct list_node *node;
 236   struct dijk_vertex *vert;
 237   struct dijk_vertex *res = NULL;
 238
 239   node = list_get_head(vertex_list);
 240
 241   // loop through all vertices
 242
 243   while (node != NULL)
 244   {
 245     vert = node->data;
 246
 247     // see whether the current vertex is better than what we have
 248
 249     if (!vert->done && vert->path_etx < best_etx)
 250     {
 251       best_etx = vert->path_etx;
 252       res = vert;
 253     }
 254
 255     node = list_get_next(node);
 256   }
 257
 258   // if we've found a vertex, remove it from the set
 259
 260   if (res != NULL)
 261     res->done = OLSR_TRUE;
 262
 263   return res;
 264 }
 265
 266 static void relax(struct dijk_vertex *vert)
 267 {
 268   struct dijk_edge *edge;
 269   float new_etx;
 270   struct list_node *node;
 271
 272   node = list_get_head(&vert->edge_list);
 273
 274   // loop through all edges of this vertex
 275
 276   while (node != NULL)
 277   {
 278     edge = node->data;
 279
 280     // total quality of the path through this vertex to the
 281     // destination of this edge
 282
 283     new_etx = vert->path_etx + edge->etx;
 284
 285     // if it's better than the current path quality of this
 286     // edge's destination, then we've found a better path to
 287     // this destination
 288
 289     if (new_etx < edge->dest->path_etx)
 290     {
 291       edge->dest->path_etx = new_etx;
 292       edge->dest->prev = vert;
 293     }
 294
 295     node = list_get_next(node);
 296   }
 297 }
 298
 299 static char *etx_to_string(float etx)
 300 {
 301   static char buff[20];
 302
 303   if (etx == INFINITE_ETX)
 304     return "INF";
 305
 306   sprintf(buff, "%.2f", etx);
 307   return buff;
 308 }
 309
 310 void olsr_calculate_lq_routing_table(void)
 311 {
 312   struct avl_tree vertex_tree;
 313   struct list vertex_list;
 314   int i;
 315   struct tc_entry *tcsrc;
 316   struct topo_dst *tcdst;
 317   struct dijk_vertex *vert;
 318   struct link_entry *link;
 319   struct neighbor_entry *neigh;
 320   struct list_node *node;
 321   struct dijk_vertex *myself;
 322   struct dijk_vertex *walker;
 323   int hops;
 324   struct mid_address *mid_walker;
 325   float etx;
 326   struct hna_entry *hna_gw;
 327   struct hna_net *hna;
 328   struct rt_entry *gw_rt, *hna_rt, *head_rt;
 329   struct neighbor_2_entry *neigh2;
 330   struct neighbor_list_entry *neigh_walker;
 331   struct interface *inter;
 332
 333   if (ipsize == 4)
 334     avl_comp = avl_comp_ipv4;
 335
 336   else
 337     avl_comp = avl_comp_ipv6;
 338
 339   // initialize the graph
 340
 341   avl_init(&vertex_tree, avl_comp);
 342   list_init(&vertex_list);
 343
 344   // add ourselves to the vertex list
 345
 346   add_vertex(&vertex_tree, &vertex_list, &main_addr, 0.0);
 347
 348   // add our neighbours
 349
 350   for (i = 0; i < HASHSIZE; i++)
 351     for (neigh = neighbortable[i].next; neigh != &neighbortable[i];
 352          neigh = neigh->next)
 353       if (neigh->status == SYM)
 354         add_vertex(&vertex_tree, &vertex_list, &neigh->neighbor_main_addr,
 355                    INFINITE_ETX);
 356
 357   // add our two-hop neighbours
 358
 359   for (i = 0; i < HASHSIZE; i++)
 360     for (neigh2 = two_hop_neighbortable[i].next;
 361          neigh2 != &two_hop_neighbortable[i];
 362          neigh2 = neigh2->next)
 363       add_vertex(&vertex_tree, &vertex_list, &neigh2->neighbor_2_addr,
 364                  INFINITE_ETX);
 365
 366   // add remaining vertices
 367
 368   for (i = 0; i < HASHSIZE; i++)
 369     for (tcsrc = tc_table[i].next; tcsrc != &tc_table[i]; tcsrc = tcsrc->next)
 370     {
 371       // add source
 372
 373       add_vertex(&vertex_tree, &vertex_list, &tcsrc->T_last_addr,
 374                  INFINITE_ETX);
 375
 376       // add destinations of this source
 377
 378       for (tcdst = tcsrc->destinations.next; tcdst != &tcsrc->destinations;
 379            tcdst = tcdst->next)
 380         add_vertex(&vertex_tree, &vertex_list, &tcdst->T_dest_addr,
 381                    INFINITE_ETX);
 382     }
 383
 384   // add edges to and from our neighbours
 385
 386   for (i = 0; i < HASHSIZE; i++)
 387     for (neigh = neighbortable[i].next; neigh != &neighbortable[i];
 388          neigh = neigh->next)
 389       if (neigh->status == SYM)
 390       {
 391         link = get_best_link_to_neighbor(&neigh->neighbor_main_addr);
 392
 393         if (link->loss_link_quality >= MIN_LINK_QUALITY &&
 394             link->neigh_link_quality >= MIN_LINK_QUALITY)
 395           {
 396             etx = 1.0 / (link->loss_link_quality * link->neigh_link_quality);
 397
 398             add_edge(&vertex_tree, &vertex_list, &neigh->neighbor_main_addr,
 399                      &main_addr, etx);
 400           }
 401       }
 402
 403   // add edges between our neighbours and our two-hop neighbours
 404
 405   for (i = 0; i < HASHSIZE; i++)
 406     for (neigh2 = two_hop_neighbortable[i].next;
 407          neigh2 != &two_hop_neighbortable[i];
 408          neigh2 = neigh2->next)
 409       for (neigh_walker = neigh2->neighbor_2_nblist.next;
 410            neigh_walker != &neigh2->neighbor_2_nblist;
 411            neigh_walker = neigh_walker->next)
 412       {
 413         if (neigh_walker->second_hop_link_quality >=
 414             MIN_LINK_QUALITY * MIN_LINK_QUALITY)
 415         {
 416           neigh = neigh_walker->neighbor;
 417
 418           etx = 1.0 / neigh_walker->second_hop_link_quality;
 419
 420           add_edge(&vertex_tree, &vertex_list, &neigh2->neighbor_2_addr,
 421                    &neigh->neighbor_main_addr, etx);
 422         }
 423       }
 424
 425   // add remaining edges
 426
 427   for (i = 0; i < HASHSIZE; i++)
 428     for (tcsrc = tc_table[i].next; tcsrc != &tc_table[i]; tcsrc = tcsrc->next)
 429       for (tcdst = tcsrc->destinations.next; tcdst != &tcsrc->destinations;
 430            tcdst = tcdst->next)
 431       {
 432         if (tcdst->link_quality >= MIN_LINK_QUALITY &&
 433             tcdst->inverse_link_quality >= MIN_LINK_QUALITY)
 434           {
 435             etx = 1.0 / (tcdst->link_quality * tcdst->inverse_link_quality);
 436
 437             add_edge(&vertex_tree, &vertex_list, &tcdst->T_dest_addr,
 438                      &tcsrc->T_last_addr, etx);
 439           }
 440       }
 441
 442   // run Dijkstra's algorithm
 443
 444   for (;;)
 445   {
 446     vert = extract_best(&vertex_list);
 447
 448     if (vert == NULL)
 449       break;
 450
 451     relax(vert);
 452   }
 453
 454   // save the old routing table
 455
 456   olsr_move_route_table(routingtable, old_routes);
 457
 458   node = list_get_head(&vertex_list);
 459
 460   // we're the first vertex in the list
 461
 462   myself = node->data;
 463
 464   olsr_printf(2, "\n--- %02d:%02d:%02d.%02d ------------------------------------------------- DIJKSTRA\n\n",
 465               nowtm->tm_hour,
 466               nowtm->tm_min,
 467               nowtm->tm_sec,
 468               now.tv_usec/10000);
 469
 470   for (node = list_get_next(node); node != NULL; node = list_get_next(node))
 471   {
 472     vert = node->data;
 473
 474     hops = 1;
 475
 476     // count hops to until the path ends or until we have reached a
 477     // one-hop neighbour
 478
 479     for (walker = vert; walker != NULL && walker->prev != myself;
 480          walker = walker->prev)
 481     {
 482       olsr_printf(2, "%s:%s <- ", olsr_ip_to_string(&walker->addr),
 483                   etx_to_string(walker->path_etx));
 484       hops++;
 485     }
 486
 487     // if no path to a one-hop neighbour was found, ignore this node
 488
 489     if (walker != NULL)
 490     {
 491       olsr_printf(2, "%s:%s (one-hop)\n", olsr_ip_to_string(&walker->addr),
 492                   etx_to_string(walker->path_etx));
 493
 494       // node reachable => add to the set of unprocessed nodes
 495       // for HNA processing
 496
 497       vert->done = OLSR_FALSE;
 498     }
 499
 500     else
 501     {
 502       olsr_printf(2, "FAILED\n", olsr_ip_to_string(&vert->addr));
 503       continue;
 504     }
 505
 506     // find the best link to the one-hop neighbour
 507
 508     link = get_best_link_to_neighbor(&walker->addr);
 509
 510     // we may see NULL here, if the one-hop neighbour is not in the
 511     // link and neighbour sets any longer, but we have derived an edge
 512     // between us and the one-hop neighbour from the TC set
 513
 514     if (link != NULL)
 515     {
 516       // find the interface for the found link
 517
 518       inter = if_ifwithaddr(&link->local_iface_addr);
 519
 520       // we may see NULL here if the interface is down, but we have
 521       // links that haven't timed out, yet
 522
 523       if (inter != NULL)
 524       {
 525         // add a route to the main address of the destination node, if
 526         // we haven't already added it above
 527
 528         olsr_insert_routing_table(&vert->addr, &link->neighbor_iface_addr,
 529                                   inter, hops);
 530
 531         // add routes to the remaining interfaces of the destination node,
 532         // if we haven't already added it above
 533
 534         for (mid_walker = mid_lookup_aliases(&vert->addr); mid_walker != NULL;
 535              mid_walker = mid_walker->next_alias)
 536           olsr_insert_routing_table(&mid_walker->alias,
 537                                     &link->neighbor_iface_addr, inter, hops);
 538       }
 539     }
 540   }
 541
 542   // add HNA routes - the set of unprocessed network nodes contains
 543   // all reachable network nodes
 544
 545   for (;;)
 546   {
 547     // extract the network node with the best ETX and remove it
 548     // from the set of unprocessed network nodes
 549
 550     vert = extract_best(&vertex_list);
 551
 552     // no more nodes left
 553
 554     if (vert == NULL)
 555       break;
 556
 557     // find the node's HNAs
 558
 559     hna_gw = olsr_lookup_hna_gw(&vert->addr);
 560
 561     // node doesn't announce any HNAs
 562
 563     if (hna_gw == NULL)
 564       continue;
 565
 566     // find route to the node
 567
 568     gw_rt = olsr_lookup_routing_table(&hna_gw->A_gateway_addr);
 569
 570     // maybe we haven't found a link or an interface for the gateway above
 571     // and hence haven't added a route - skip the HNA in this case
 572
 573     if (gw_rt == NULL)
 574       continue;
 575
 576     // loop through the node's HNAs
 577
 578     for (hna = hna_gw->networks.next; hna != &hna_gw->networks;
 579          hna = hna->next)
 580     {
 581       // we already have a route via a previous (better) node
 582
 583       if (olsr_lookup_routing_table(&hna->A_network_addr) != NULL)
 584         continue;
 585
 586       // create route for the HNA
 587
 588       hna_rt = olsr_malloc(sizeof(struct rt_entry), "LQ HNA route entry");
 589
 590       // set HNA IP address and netmask
 591
 592       COPY_IP(&hna_rt->rt_dst, &hna->A_network_addr);
 593       hna_rt->rt_mask = hna->A_netmask;
 594
 595       // copy remaining fields from the node's route
 596
 597       COPY_IP(&hna_rt->rt_router, &gw_rt->rt_router);
 598       hna_rt->rt_metric = gw_rt->rt_metric;
 599       hna_rt->rt_if = gw_rt->rt_if;
 600
 601       // we're not a host route
 602
 603       hna_rt->rt_flags = RTF_UP | RTF_GATEWAY;
 604
 605       // find the correct list
 606
 607       head_rt = &routingtable[olsr_hashing(&hna->A_network_addr)];
 608
 609       // enqueue
 610
 611       head_rt->next->prev = hna_rt;
 612       hna_rt->next = head_rt->next;
 613
 614       head_rt->next = hna_rt;
 615       hna_rt->prev = head_rt;
 616     }
 617   }
 618
 619   // free the graph
 620
 621   free_everything(&vertex_list);
 622
 623   // move the route changes into the kernel
 624
 625   olsr_update_kernel_routes();
 626
 627   // free the saved routing table
 628
 629   olsr_free_routing_table(old_routes);
 630 }