Changed link/interface detection for route calculation
authorAndreas Tonnesen <andreto@olsr.org>
Sat, 12 Feb 2005 22:32:42 +0000 (22:32 +0000)
committerAndreas Tonnesen <andreto@olsr.org>
Sat, 12 Feb 2005 22:32:42 +0000 (22:32 +0000)
src/interfaces.c
src/interfaces.h
src/ipc_frontend.c
src/link_set.c
src/link_set.h
src/lq_route.c
src/routing_table.c
src/routing_table.h

index 88d8b8e..9803dca 100644 (file)
@@ -36,7 +36,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: interfaces.c,v 1.12 2004/11/21 11:28:56 kattemat Exp $
+ * $Id: interfaces.c,v 1.13 2005/02/12 22:32:41 kattemat Exp $
  */
 
 #include "defs.h"
@@ -110,6 +110,9 @@ if_ifwithaddr(union olsr_ip_addr *addr)
 {
   struct interface *ifp;
 
+  if(!addr)
+    return NULL;
+
   for (ifp = ifnet; ifp; ifp = ifp->int_next)
     {
       if(olsr_cnf->ip_version == AF_INET)
index 7713bb5..f7bc3b2 100644 (file)
@@ -36,7 +36,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: interfaces.h,v 1.14 2004/11/21 11:28:56 kattemat Exp $
+ * $Id: interfaces.h,v 1.15 2005/02/12 22:32:42 kattemat Exp $
  */
 
 
@@ -69,6 +69,8 @@
 #define IPV6_ADDR_RESERVED     0x2000U
 
 
+#define MAX_IF_METRIC           100
+
 struct vtimes
 {
   olsr_u8_t hello;
index e1a3899..9bdf4c7 100644 (file)
@@ -36,7 +36,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: ipc_frontend.c,v 1.22 2005/02/02 18:57:02 kattemat Exp $
+ * $Id: ipc_frontend.c,v 1.23 2005/02/12 22:32:42 kattemat Exp $
  */
 
 /*
@@ -340,7 +340,7 @@ ipc_send_all_routes()
          destination != &routingtable[index];
          destination = destination->next)
        {
-         ifn = get_interface_link_set(&destination->rt_router);
+         ifn = NULL;//get_interface_link_set(&destination->rt_router);
          
 
          memset(&packet, 0, sizeof(struct ipcmsg));
@@ -387,7 +387,7 @@ ipc_send_all_routes()
          destination != &hna_routes[index];
          destination = destination->next)
        {
-         ifn = get_interface_link_set(&destination->rt_router);
+         ifn = NULL;//get_interface_link_set(&destination->rt_router);
 
          packet.size = htons(IPC_PACK_SIZE);
          packet.msgtype = ROUTE_IPC;
index f337a4c..88411ff 100644 (file)
@@ -36,7 +36,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: link_set.c,v 1.45 2005/02/12 11:26:21 kattemat Exp $
+ * $Id: link_set.c,v 1.46 2005/02/12 22:32:42 kattemat Exp $
  */
 
 
@@ -71,6 +71,8 @@ olsr_time_out_link_set(void);
 static int
 get_neighbor_status(union olsr_ip_addr *);
 
+static struct link_entry *
+find_best_link(union olsr_ip_addr *);
 
 
 
@@ -213,183 +215,123 @@ get_neighbor_status(union olsr_ip_addr *address)
 }
 
 
-
-
 /**
- *Get the remote interface address to use as nexthop
- *to reach the remote host.
+ *Find the best link to a neighbor interface 
  *
- *@param address the address of the remote host
- *@return the nexthop address to use. Returns the pointer
- *passed as arg 1 if nothing is found(if no MID is registered).
  */
-union olsr_ip_addr *
-get_neighbor_nexthop(union olsr_ip_addr *address)
+
+static struct link_entry *
+find_best_link(union olsr_ip_addr *remote)
 {
-  union olsr_ip_addr *main_addr;
-  struct interface   *ifs;
+  struct link_entry *tmp_link_set, *entry;
+  int curr_metric = MAX_IF_METRIC;
+  float curr_lq = -1.0;
 
-  /* First try to find a direct link */
-  for(ifs = ifnet; ifs != NULL; ifs = ifs->int_next)
-    {
-      struct link_entry  *link;
-      if((link = lookup_link_entry(address, &ifs->ip_addr)) != NULL)
-       {
-         if(lookup_link_status(link) == SYM_LINK)
-           return address;
-       }
-    }
+  tmp_link_set = link_set;
+  entry = NULL;
 
-  /* Find main address */
-  if(!(main_addr = mid_lookup_main_addr(address)))
-    main_addr = address;
-  
-  for(ifs = ifnet; ifs != NULL; ifs = ifs->int_next)
+  while(tmp_link_set)
     {
-      struct mid_address *aliases;
-      struct link_entry  *link;
-
-      /* Try main address */
-      if((!COMP_IP(main_addr, address)) &&
-        (link = lookup_link_entry(main_addr, &ifs->ip_addr)) != NULL)
-       {
-         if(lookup_link_status(link) == SYM_LINK)
-           return main_addr;
-       }
-      
-      /* Try aliases */
-      for(aliases = mid_lookup_aliases(main_addr);
-         aliases != NULL;
-         aliases = aliases->next_alias)
+      if(COMP_IP(remote, &tmp_link_set->neighbor_iface_addr))
        {
-         if((!COMP_IP(&aliases->alias, address)) &&
-            (link = lookup_link_entry(&aliases->alias, &ifs->ip_addr)) != NULL)
+         struct interface *tmp_if = if_ifwithaddr(&tmp_link_set->local_iface_addr);
+
+         if (olsr_cnf->lq_level == 0)
            {
-             if(lookup_link_status(link) == SYM_LINK)
-               return &aliases->alias;
+             if(tmp_if->int_metric < curr_metric)
+               {
+                 entry = tmp_link_set;
+                 curr_metric = tmp_if->int_metric;
+               }
+           }
+         else
+           {
+             float tmp_lq = tmp_link_set->loss_link_quality *
+               tmp_link_set->neigh_link_quality;
+
+             if (tmp_lq > curr_lq)
+               {
+                 entry = tmp_link_set;
+                 curr_lq = tmp_lq;
+               }
            }
        }
+         tmp_link_set = tmp_link_set->next;
     }
   
-  /* This shoud only happen if not MID addresses for the
-   * multi-homed remote host are registered yet
-   */
-  return address;
+  return entry;
 }
 
 
-
-
 /**
- *Get the interface to use when setting up
- *a route to a neighbor. The interface with
- *the lowest metric is used.
- *
- *As this function is only called by the route calculation
- *functions it is considered that the caller is responsible
- *for making sure the neighbor is symmetric.
- *Due to experiences of route calculaition queryig for interfaces
- *when no links with a valid SYM time is avalibe, the function
- *will return a possible interface with an expired SYM time
- *if no SYM links were discovered.
- *
- *@param address of the neighbor - does not have to
- *be the main address
- *
- *@return a interface struct representing the interface to use
+ * Find best link to a neighbor
  */
-struct interface *
-get_interface_link_set(union olsr_ip_addr *remote)
-{
-  struct link_entry *tmp_link_set;
-  struct interface *if_to_use, *backup_if;
-  float link_quality, backup_link_quality;
 
-  if_to_use = NULL;
-  backup_if = NULL;
+struct link_entry *
+get_best_link_to_neighbor(union olsr_ip_addr *remote)
+{
+  struct link_entry *good_link = NULL, *backup_link = NULL;
+  int curr_metric = MAX_IF_METRIC;
+  float curr_lq = -1.0;
+  union olsr_ip_addr *main_addr;
+  struct mid_address *aliases, main_alias;
+  
+  /* Find main address */
+  if(!(main_addr = mid_lookup_main_addr(remote)))
+    main_addr = remote;
 
-  link_quality = -1.0;
-  backup_link_quality = -1.0;
+  COPY_IP(&main_alias.alias, main_addr);
+  main_alias.next_alias = mid_lookup_aliases(main_addr);
 
-  if(remote == NULL || link_set == NULL)
+  for(aliases = &main_alias;
+      aliases != NULL;
+      aliases = aliases->next_alias)
     {
-      olsr_printf(1, "Get interface: not sane request or empty link set!\n");
-      return NULL;
-    }
+      struct link_entry *link;
 
-
-  tmp_link_set = link_set;
-  while(tmp_link_set)
-    {
-      struct interface *tmp_if;
-      float curr;
-      //printf("Checking %s vs ", olsr_ip_to_string(&tmp_link_set->neighbor_iface_addr));
-      //printf("%s\n", olsr_ip_to_string(addr));
-      
-      if(COMP_IP(remote, &tmp_link_set->neighbor_iface_addr))
+      if((link = find_best_link(&aliases->alias)) != NULL)
        {
-         tmp_if = if_ifwithaddr(&tmp_link_set->local_iface_addr);
-
-         /* Must be symmetric link! */
-         if(!TIMED_OUT(tmp_link_set->SYM_time))
+         if (olsr_cnf->lq_level == 0)
            {
-              if (olsr_cnf->lq_level == 0)
-                {
-                  if (if_to_use == NULL ||
-                      if_to_use->int_metric > tmp_if->int_metric)
-                    if_to_use = tmp_if;
-                }
-              else
-                {
-                  curr = tmp_link_set->loss_link_quality *
-                    tmp_link_set->neigh_link_quality;
-
-                  if (curr > link_quality)
-                    {
-                      if_to_use = tmp_if;
-                      link_quality = curr;
-                    }
-                }
+             struct interface *tmp_if = if_ifwithaddr(&link->local_iface_addr);
+             if((tmp_if->int_metric < curr_metric) ||
+                /* Prefer the requested link */
+                ((tmp_if->int_metric == curr_metric) && 
+                 COMP_IP(&link->local_iface_addr, remote)))
+               {
+                 curr_metric = tmp_if->int_metric;
+                 if(lookup_link_status(link) == SYM_LINK)
+                   good_link = link;
+                 else
+                   backup_link = link;
+               }
            }
-         /* Backup solution in case the links have timed out */
          else
            {
-              if (olsr_cnf->lq_level == 0)
-                {
-                  if (if_to_use == NULL &&
-                      (backup_if == NULL ||
-                       backup_if->int_metric > tmp_if->int_metric))
-                    backup_if = tmp_if;
-                }
-
-              else 
-                {
-                  curr = tmp_link_set->loss_link_quality *
-                    tmp_link_set->neigh_link_quality;
-
-                  if (if_to_use == NULL && curr > backup_link_quality)
-                    {
-                      backup_if = tmp_if;
-                      backup_link_quality = curr;
-                    }
-                }
-            }
+             float tmp_lq = link->loss_link_quality *
+               link->neigh_link_quality;
+             
+             if((tmp_lq > curr_lq) ||
+                /* Prefer the requested link */
+                ((tmp_lq == curr_lq) && 
+                 COMP_IP(&link->local_iface_addr, remote)))              
+               {
+                 curr_lq = tmp_lq;
+                 if(lookup_link_status(link) == SYM_LINK)
+                   good_link = link;
+                 else
+                   backup_link = link;
+               }
+           } 
        }
-      
-      tmp_link_set = tmp_link_set->next;
     }
 
-
-  
-  /* Not found */
-  if(if_to_use == NULL)
-    return backup_if;
-  
-  return if_to_use;
+  return good_link ? good_link : backup_link;
 }
 
 
 
+
 /**
  *Nothing mysterious here.
  *Adding a new link entry to the link set.
@@ -414,7 +356,8 @@ add_new_entry(union olsr_ip_addr *local, union olsr_ip_addr *remote, union olsr_
 
   while(tmp_link_set)
     {
-      if(COMP_IP(remote, &tmp_link_set->neighbor_iface_addr))
+      if(COMP_IP(remote, &tmp_link_set->neighbor_iface_addr) &&
+        COMP_IP(local, &tmp_link_set->local_iface_addr))
        return tmp_link_set;
       tmp_link_set = tmp_link_set->next;
     }
index 3d6fc12..ad88841 100644 (file)
@@ -36,7 +36,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: link_set.h,v 1.19 2005/01/16 19:49:28 kattemat Exp $
+ * $Id: link_set.h,v 1.20 2005/02/12 22:32:42 kattemat Exp $
  */
 
 
@@ -117,11 +117,8 @@ clock_t hold_time_neighbor;
 void
 olsr_init_link_set(void);
 
-struct interface *
-get_interface_link_set(union olsr_ip_addr *);
-
-union olsr_ip_addr *
-get_neighbor_nexthop(union olsr_ip_addr *);
+struct link_entry *
+get_best_link_to_neighbor(union olsr_ip_addr *);
 
 struct link_entry *
 lookup_link_entry(union olsr_ip_addr *, union olsr_ip_addr *);
@@ -139,10 +136,16 @@ replace_neighbor_link_set(struct neighbor_entry *,
 int
 lookup_link_status(struct link_entry *);
 
-void olsr_update_packet_loss_hello_int(struct link_entry *entry, double htime);
-void olsr_update_packet_loss(union olsr_ip_addr *rem, union olsr_ip_addr *loc,
-                        olsr_u16_t seqno);
-void olsr_print_link_set(void);
-struct link_entry *olsr_neighbor_best_link(union olsr_ip_addr *main);
+void 
+olsr_update_packet_loss_hello_int(struct link_entry *, double);
+
+void 
+olsr_update_packet_loss(union olsr_ip_addr *, union olsr_ip_addr *, olsr_u16_t);
+
+void 
+olsr_print_link_set(void);
+
+struct link_entry *
+olsr_neighbor_best_link(union olsr_ip_addr *);
 
 #endif
index 8b8fbe2..36b5d36 100644 (file)
@@ -36,7 +36,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: lq_route.c,v 1.23 2005/01/24 10:35:58 tlopatic Exp $
+ * $Id: lq_route.c,v 1.24 2005/02/12 22:32:42 kattemat Exp $
  */
 
 #include "defs.h"
@@ -483,16 +483,24 @@ void olsr_calculate_lq_routing_table(void)
 #endif
 
     // add a route to the main address of the destination node
+    link = get_best_link_to_neighbor(&walker->addr);
 
     olsr_insert_routing_table(&vert->addr,
-                              get_neighbor_nexthop(&walker->addr), hops);
+                             &link->neighbor_iface_addr,
+                             if_ifwithaddr(&link->local_iface_addr),
+                              hops);
 
     // add routes to the remaining interfaces of the destination node
 
     for (mid_walker = mid_lookup_aliases(&vert->addr); mid_walker != NULL;
          mid_walker = mid_walker->next_alias)
-      olsr_insert_routing_table(&mid_walker->alias,
-                                get_neighbor_nexthop(&walker->addr), hops);
+      {
+       link = get_best_link_to_neighbor(&mid_walker->alias);
+       olsr_insert_routing_table(&mid_walker->alias,
+                                 &link->neighbor_iface_addr,
+                                 if_ifwithaddr(&link->local_iface_addr),
+                                 hops);
+      }
   }
 
   // add HNA routes - the set of unprocessed network nodes contains
index 1c9e3b4..10dc876 100644 (file)
@@ -36,7 +36,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: routing_table.c,v 1.15 2005/02/01 20:27:57 kattemat Exp $
+ * $Id: routing_table.c,v 1.16 2005/02/12 22:32:42 kattemat Exp $
  */
 
 
@@ -169,7 +169,10 @@ olsr_free_routing_table(struct rt_entry *table)
  *@return the new rt_entry struct
  */
 struct rt_entry *
-olsr_insert_routing_table(union olsr_ip_addr *dst, union olsr_ip_addr *router, int metric)
+olsr_insert_routing_table(union olsr_ip_addr *dst, 
+                         union olsr_ip_addr *router, 
+                         struct interface *iface, 
+                         int metric)
 {
   struct rt_entry *new_route_entry, *rt_list;
   olsr_u32_t       hash;
@@ -181,6 +184,7 @@ olsr_insert_routing_table(union olsr_ip_addr *dst, union olsr_ip_addr *router, i
 
   COPY_IP(&new_route_entry->rt_dst, dst);
   COPY_IP(&new_route_entry->rt_router, router);
+  new_route_entry->rt_if = iface;
 
   new_route_entry->rt_metric = metric;
   if(COMP_IP(dst, router))
@@ -196,18 +200,6 @@ olsr_insert_routing_table(union olsr_ip_addr *dst, union olsr_ip_addr *router, i
     /* IPv6 */
     new_route_entry->rt_mask.v6 = 128;
 
-  /* Find interface */
-  if((new_route_entry->rt_if = get_interface_link_set(router)) == NULL)
-    {
-      fprintf(stderr, "ADD ROUTE 1: %s Could not find neighbor interface ", 
-             olsr_ip_to_string(dst));
-      fprintf(stderr, "for %s!!\n", 
-             olsr_ip_to_string(router));
-      free(new_route_entry);
-      return NULL;
-    }
-  
-
   /* queue */
   rt_list->next->prev = new_route_entry;
   new_route_entry->next = rt_list->next;
@@ -258,11 +250,15 @@ olsr_fill_routing_table_with_neighbors()
 
              while(addrs2!=NULL)
                {
+                 struct link_entry *link = get_best_link_to_neighbor(&addrs2->alias);
 #ifdef DEBUG
                  olsr_printf(7, "(ROUTE)Adding neighbor %s\n", olsr_ip_to_string(&addrs.alias));
 #endif
-                 /* New in 0.4.6 */
-                 new_route_entry = olsr_insert_routing_table(&addrs2->alias, get_neighbor_nexthop(&addrs2->alias), 1);
+
+                 new_route_entry = olsr_insert_routing_table(&addrs2->alias, 
+                                                             &link->neighbor_iface_addr,
+                                                             if_ifwithaddr(&link->local_iface_addr),
+                                                             1);
              
                  addrs2 = addrs2->next_alias;
                }
@@ -362,13 +358,14 @@ olsr_fill_routing_table_with_two_hop_neighbors()
              while(addrsp!=NULL)
                {
                  struct rt_entry *new_route_entry = NULL;
+                 struct link_entry *link = get_best_link_to_neighbor(&neighbor->neighbor_main_addr);
 #ifdef DEBUG
                  olsr_printf(7, "(ROUTE)Adding neighbor %s\n", olsr_ip_to_string(&addrsp->alias));
 #endif
-                 /* New in 0.4.6 */
                  new_route_entry = 
                    olsr_insert_routing_table(&addrsp->alias, 
-                                             get_neighbor_nexthop(&neighbor->neighbor_main_addr), 
+                                             &link->neighbor_iface_addr,
+                                             if_ifwithaddr(&link->local_iface_addr),
                                              2);
 
                  if(new_route_entry != NULL)
@@ -462,6 +459,7 @@ olsr_calculate_routing_table()
                          destination_n_1->destination = 
                            olsr_insert_routing_table(&tmp_addrsp->alias, 
                                                      &list_destination_n->destination->rt_router, 
+                                                     list_destination_n->destination->rt_if,
                                                      list_destination_n->destination->rt_metric+1);
                          if(destination_n_1->destination != NULL)
                            {
@@ -651,11 +649,14 @@ olsr_calculate_hna_routes()
                  new_rt->rt_metric = tmp_rt->rt_metric;
                  /* Flags */
                  new_rt->rt_flags = RTF_UP | RTF_GATEWAY;
-
+                 /* Interface */
+                 new_rt->rt_if = tmp_rt->rt_if;
                }
              /* If not - create a new one */
              else
                {
+                 olsr_u32_t  hna_hash;
+
                  new_rt = olsr_malloc(sizeof(struct rt_entry), "New rt entry");
 
                  /* Fill struct */
@@ -668,26 +669,16 @@ olsr_calculate_hna_routes()
                  new_rt->rt_metric = tmp_rt->rt_metric;
                  /* Flags */
                  new_rt->rt_flags = RTF_UP | RTF_GATEWAY;
-             
-                 /* Find interface */
-                 if((new_rt->rt_if = get_interface_link_set(&new_rt->rt_router)) == NULL)
-                   {
-                     fprintf(stderr, "ADD ROUTE 2: %s Could not find neighbor interface!!!\n", 
-                             olsr_ip_to_string(&new_rt->rt_dst));
-                     /* This hopefullt never happens */
-                     free(new_rt);
-                   }
-                 else
-                   {
-                     olsr_u32_t  hna_hash;
-
-                     /* Queue HASH will almost always be 0 */
-                     hna_hash = olsr_hashing(&tmp_net->A_network_addr);
-                     hna_routes[hna_hash].next->prev = new_rt;
-                     new_rt->next = hna_routes[hna_hash].next;
-                     hna_routes[hna_hash].next = new_rt;
-                     new_rt->prev = &hna_routes[hna_hash];
-                   }
+
+                 /* Interface */
+                 new_rt->rt_if = tmp_rt->rt_if;
+                         
+                 /* Queue HASH will almost always be 0 */
+                 hna_hash = olsr_hashing(&tmp_net->A_network_addr);
+                 hna_routes[hna_hash].next->prev = new_rt;
+                 new_rt->next = hna_routes[hna_hash].next;
+                 hna_routes[hna_hash].next = new_rt;
+                 new_rt->prev = &hna_routes[hna_hash];
                }
            }
        }
index 2ecb225..336d473 100644 (file)
@@ -36,7 +36,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: routing_table.h,v 1.12 2005/01/22 12:25:25 tlopatic Exp $
+ * $Id: routing_table.h,v 1.13 2005/02/12 22:32:42 kattemat Exp $
  */
 
 #ifndef _OLSR_ROUTING_TABLE
@@ -108,7 +108,7 @@ void
 olsr_print_routing_table(struct rt_entry *);
 
 struct rt_entry *
-olsr_insert_routing_table(union olsr_ip_addr *, union olsr_ip_addr *, int);
+olsr_insert_routing_table(union olsr_ip_addr *, union olsr_ip_addr *, struct interface *, int);
 
 struct rt_entry *
 olsr_lookup_routing_table(union olsr_ip_addr *);