[Olsr-cvs] olsrd-current/src lq_route.c, 1.50, 1.51 lq_route.h, 1.5, 1.6 process_package.c, 1.41, 1.42 tc_set.c, 1.27, 1.28 tc_set.h, 1.15, 1.16
Bernd Petrovitsch
(spam-protected)
Thu Sep 13 17:32:01 CEST 2007
Update of /cvsroot/olsrd/olsrd-current/src
In directory sc8-pr-cvs3.sourceforge.net:/tmp/cvs-serv16823/src
Modified Files:
lq_route.c lq_route.h process_package.c tc_set.c tc_set.h
Log Message:
* patch by Hannes Gredler <(spam-protected)> to consolidate the the link-state database and the spf-calculation
Index: tc_set.h
===================================================================
RCS file: /cvsroot/olsrd/olsrd-current/src/tc_set.h,v
retrieving revision 1.15
retrieving revision 1.16
diff -C2 -d -r1.15 -r1.16
*** tc_set.h 29 May 2005 12:47:46 -0000 1.15
--- tc_set.h 13 Sep 2007 15:31:59 -0000 1.16
***************
*** 2,5 ****
--- 2,6 ----
* The olsr.org Optimized Link-State Routing daemon(olsrd)
* Copyright (c) 2004, Andreas Tønnesen((spam-protected))
+ * LSDB rewrite (c) 2007, Hannes Gredler ((spam-protected))
* All rights reserved.
*
***************
*** 46,108 ****
#include "packet.h"
! struct topo_dst
{
! union olsr_ip_addr T_dest_addr;
! clock_t T_time;
! olsr_u16_t T_seq;
! struct topo_dst *next;
! struct topo_dst *prev;
! double link_quality;
! double inverse_link_quality;
! double saved_link_quality;
! double saved_inverse_link_quality;
};
struct tc_entry
{
! union olsr_ip_addr T_last_addr;
! struct topo_dst destinations;
! struct tc_entry *next;
! struct tc_entry *prev;
};
! /* Queue */
! extern struct tc_entry tc_table[HASHSIZE];
!
!
! int
! olsr_init_tc(void);
!
!
! int
! olsr_tc_delete_mprs(struct tc_entry *, struct tc_message *);
!
!
! struct tc_entry *
! olsr_lookup_tc_entry(union olsr_ip_addr *);
!
!
! struct topo_dst *
! olsr_tc_lookup_dst(struct tc_entry *, union olsr_ip_addr *);
!
!
! int
! olsr_tc_delete_entry_if_empty(struct tc_entry *);
!
!
! struct tc_entry *
! olsr_add_tc_entry(union olsr_ip_addr *);
! int
! olsr_tc_update_mprs(struct tc_entry *, struct tc_message *);
! int
! olsr_print_tc_table(void);
! void
! olsr_time_out_tc_set(void);
#endif
--- 47,145 ----
#include "packet.h"
! /*
! * This file holds the definitions for the link state database.
! * The lsdb consists of nodes and edges.
! * During input parsing all nodes and edges are extracted and syntesized.
! * The SPF calculation operates on these datasets.
! */
!
! struct tc_edge_entry
{
! struct avl_node edge_node; /* edge_tree node in tc_entry */
! union olsr_ip_addr T_dest_addr; /* edge_node key */
! struct tc_edge_entry *edge_inv; /* shortcut, used during SPF calculation */
! struct tc_entry *tc; /* backpointer to owning tc entry */
! clock_t T_time; /* expiration timer, timer_node key */
! olsr_u16_t T_seq; /* sequence number */
! olsr_u16_t flags; /* misc flags */
! float etx; /* metric used for SPF calculation */
! float link_quality;
! float inverse_link_quality;
};
+ #define OLSR_TC_EDGE_DOWN (1 << 0) /* this edge is down */
+
+ /*
+ * Garbage collection time for downed edges
+ */
+ #define OLSR_TC_EDGE_GC_TIME 15*1000 /* milliseconds */
struct tc_entry
{
! struct avl_node vertex_node; /* node keyed by ip address */
! struct avl_node cand_tree_node; /* SPF candidate heap, node keyed by path_etx */
! struct list_node path_list_node; /* SPF result list */
! union olsr_ip_addr addr; /* vertex_node key */
! struct avl_tree edge_tree; /* subtree for edges */
! struct link_entry *next_hop; /* SPF calculated link to the 1st hop neighbor */
! float path_etx; /* SPF calculated distance, cand_tree_node key */
! olsr_u8_t hops; /* SPF calculated hopcount */
};
+ /*
+ * macros for traversing the vertices and edges in the link state database.
+ * it is recommended to use this because it hides all the internal
+ * datastructure from the callers.
+ *
+ * the loop prefetches the next node in order to not loose context if
+ * for example the caller wants to delete the current entry.
+ */
+ #define OLSR_FOR_ALL_TC_ENTRIES(tc) \
+ { \
+ struct avl_node *tc_tree_node, *next_tc_tree_node; \
+ for (tc_tree_node = avl_walk_first(&tc_tree); \
+ tc_tree_node; tc_tree_node = next_tc_tree_node) { \
+ next_tc_tree_node = avl_walk_next(tc_tree_node); \
+ tc = tc_tree_node->data;
+ #define OLSR_FOR_ALL_TC_ENTRIES_END(tc) }}
! #define OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) \
! { \
! struct avl_node *tc_edge_node, *next_tc_edge_node; \
! for (tc_edge_node = avl_walk_first(&tc->edge_tree); \
! tc_edge_node; tc_edge_node = next_tc_edge_node) { \
! next_tc_edge_node = avl_walk_next(tc_edge_node); \
! tc_edge = tc_edge_node->data;
! #define OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc, tc_edge) }}
+ extern struct avl_tree tc_tree;
+ extern struct tc_entry *tc_myself;
! int olsr_init_tc(void);
! int olsr_tc_delete_mprs(struct tc_entry *, struct tc_message *);
! int olsr_tc_update_mprs(struct tc_entry *, struct tc_message *);
! int olsr_print_tc_table(void);
! void olsr_time_out_tc_set(void);
! /* tc_entry manipulation */
! struct tc_entry *olsr_lookup_tc_entry(union olsr_ip_addr *);
! struct tc_entry *olsr_add_tc_entry(union olsr_ip_addr *);
! struct tc_entry *olsr_getnext_tc_entry(struct tc_entry *);
! /* tc_edge_entry manipulation */
! char *olsr_tc_edge_to_string(struct tc_edge_entry *);
! struct tc_edge_entry *olsr_lookup_tc_edge(struct tc_entry *,
! union olsr_ip_addr *);
! struct tc_edge_entry *olsr_add_tc_edge_entry(struct tc_entry *,
! union olsr_ip_addr *, u_int16_t,
! unsigned int, float, float);
! void olsr_delete_tc_edge_entry(struct tc_edge_entry *);
! void olsr_calc_tc_edge_entry_etx(struct tc_edge_entry *);
#endif
+
+ /*
+ * Local Variables:
+ * c-basic-offset: 2
+ * End:
+ */
Index: lq_route.h
===================================================================
RCS file: /cvsroot/olsrd/olsrd-current/src/lq_route.h,v
retrieving revision 1.5
retrieving revision 1.6
diff -C2 -d -r1.5 -r1.6
*** lq_route.h 5 Sep 2007 16:11:10 -0000 1.5
--- lq_route.h 13 Sep 2007 15:31:59 -0000 1.6
***************
*** 48,51 ****
--- 48,52 ----
void olsr_calculate_routing_table(void);
+ char *olsr_etx_to_string(float);
#endif
Index: process_package.c
===================================================================
RCS file: /cvsroot/olsrd/olsrd-current/src/process_package.c,v
retrieving revision 1.41
retrieving revision 1.42
diff -C2 -d -r1.41 -r1.42
*** process_package.c 2 Aug 2007 22:07:19 -0000 1.41
--- process_package.c 13 Sep 2007 15:31:59 -0000 1.42
***************
*** 229,234 ****
}
! OLSR_PRINTF(3, "Processing TC from %s\n",
! olsr_ip_to_string(&message->originator));
/*
--- 229,234 ----
}
! OLSR_PRINTF(3, "Processing TC from %s, seq 0x%04x\n",
! olsr_ip_to_string(&message->originator), message->ansn);
/*
***************
*** 273,280 ****
if(olsr_tc_update_mprs(tc_last, message))
changes_topology = OLSR_TRUE;
-
- /* Delete possible empty TC entry */
- if(changes_topology)
- olsr_tc_delete_entry_if_empty(tc_last);
}
--- 273,276 ----
Index: tc_set.c
===================================================================
RCS file: /cvsroot/olsrd/olsrd-current/src/tc_set.c,v
retrieving revision 1.27
retrieving revision 1.28
diff -C2 -d -r1.27 -r1.28
*** tc_set.c 2 Aug 2007 22:07:19 -0000 1.27
--- tc_set.c 13 Sep 2007 15:31:59 -0000 1.28
***************
*** 2,5 ****
--- 2,6 ----
* The olsr.org Optimized Link-State Routing daemon(olsrd)
* Copyright (c) 2004, Andreas Tønnesen((spam-protected))
+ * LSDB rewrite (c) 2007, Hannes Gredler ((spam-protected))
* All rights reserved.
*
***************
*** 40,52 ****
*/
[...967 lines suppressed...]
! etx = 0.0;
! } else {
! etx = 1.0 / (tc_edge->link_quality * tc_edge->inverse_link_quality);
! }
!
! OLSR_PRINTF(1, fstr, olsr_ip_to_string(&tc->addr),
! olsr_ip_to_string(&tc_edge->T_dest_addr),
! tc_edge->link_quality, tc_edge->inverse_link_quality, etx);
!
! } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc, tc_edge);
! } OLSR_FOR_ALL_TC_ENTRIES_END(tc);
return 1;
}
+
+ /*
+ * Local Variables:
+ * c-basic-offset: 2
+ * End:
+ */
Index: lq_route.c
===================================================================
RCS file: /cvsroot/olsrd/olsrd-current/src/lq_route.c,v
retrieving revision 1.50
retrieving revision 1.51
diff -C2 -d -r1.50 -r1.51
*** lq_route.c 5 Sep 2007 16:17:36 -0000 1.50
--- lq_route.c 13 Sep 2007 15:31:59 -0000 1.51
***************
*** 55,77 ****
#include "lq_route.h"
- struct olsr_spf_edge
- {
- struct avl_node tree_node;
- struct olsr_spf_vertex *dest;
- float etx;
- };
-
- struct olsr_spf_vertex
- {
- struct avl_node tree_node; /* node keyed by ip address */
- struct avl_node cand_tree_node; /* node keyed by etx */
- struct list_node path_list_node; /* SPF result list */
- union olsr_ip_addr addr;
- struct avl_tree edge_tree;
- struct link_entry *next_hop; /* the link to the 1st hop neighbor */
- float path_etx;
- olsr_u8_t hops;
- };
-
/*
* avl_comp_etx
--- 55,58 ----
***************
*** 104,108 ****
static void
olsr_spf_add_cand_tree (struct avl_tree *tree,
! struct olsr_spf_vertex *vert)
{
vert->cand_tree_node.key = &vert->path_etx;
--- 85,89 ----
static void
olsr_spf_add_cand_tree (struct avl_tree *tree,
! struct tc_entry *vert)
{
vert->cand_tree_node.key = &vert->path_etx;
***************
*** 115,119 ****
#endif
! avl_insert(tree, &vert->cand_tree_node, 1);
}
--- 96,100 ----
#endif
! avl_insert(tree, &vert->cand_tree_node, AVL_DUP);
}
***************
*** 125,129 ****
static void
olsr_spf_del_cand_tree (struct avl_tree *tree,
! struct olsr_spf_vertex *vert)
{
--- 106,110 ----
static void
olsr_spf_del_cand_tree (struct avl_tree *tree,
! struct tc_entry *vert)
{
***************
*** 145,149 ****
olsr_spf_add_path_list (struct list_node *head,
int *path_count,
! struct olsr_spf_vertex *vert)
{
vert->path_list_node.data = vert;
--- 126,130 ----
olsr_spf_add_path_list (struct list_node *head,
int *path_count,
! struct tc_entry *vert)
{
vert->path_list_node.data = vert;
***************
*** 161,307 ****
/*
- * olsr_spf_add_vertex
- *
- * Add a node to the tree of all nodes in the network.
- */
- static struct olsr_spf_vertex *
- olsr_spf_add_vertex (struct avl_tree *vertex_tree,
- union olsr_ip_addr *addr, float path_etx)
- {
- struct avl_node *node;
- struct olsr_spf_vertex *vert;
-
- // see whether this destination is already in our tree
-
- node = avl_find(vertex_tree, addr);
-
- if (node) {
- return node->data;
- }
-
- // if it's not in our list, add it
-
- vert = olsr_malloc(sizeof (struct olsr_spf_vertex), "Dijkstra vertex");
-
- vert->tree_node.data = vert;
- vert->tree_node.key = &vert->addr;
-
- COPY_IP(&vert->addr, addr);
-
- vert->path_etx = path_etx;
- vert->next_hop = NULL;
- vert->hops = 0;
-
- avl_init(&vert->edge_tree, avl_comp_default);
-
- avl_insert(vertex_tree, &vert->tree_node, 0);
- return vert;
- }
-
- static struct olsr_spf_vertex *
- olsr_spf_add_edge (struct avl_tree *vertex_tree,
- union olsr_ip_addr *src, union olsr_ip_addr *dst,
- float etx)
- {
- struct avl_node *node;
- struct olsr_spf_vertex *svert;
- struct olsr_spf_vertex *dvert;
- struct olsr_spf_edge *edge;
-
- // source lookup
-
- node = avl_find(vertex_tree, src);
-
- // source vertex does not exist
-
- if (node == NULL)
- return NULL;
-
- svert = node->data;
-
- // destination lookup
-
- node = avl_find(vertex_tree, dst);
-
- // destination vertex does not exist
-
- if (node == NULL)
- return NULL;
-
- dvert = node->data;
-
- // check for existing forward edge
-
- if (avl_find(&svert->edge_tree, dst) == NULL)
- {
- // add forward edge
-
- edge = olsr_malloc(sizeof (struct olsr_spf_vertex), "Dijkstra forward edge");
-
- edge->tree_node.data = edge;
- edge->tree_node.key = &dvert->addr;
-
- edge->dest = dvert;
- edge->etx = etx;
-
- avl_insert(&svert->edge_tree, &edge->tree_node, 0);
- }
-
- // check for existing inverse edge
-
- if (avl_find(&dvert->edge_tree, src) == NULL)
- {
- // add inverse edge
-
- edge = olsr_malloc(sizeof (struct olsr_spf_vertex), "Dijkstra inverse edge");
-
- edge->tree_node.data = edge;
- edge->tree_node.key = &svert->addr;
-
- edge->dest = svert;
- edge->etx = etx;
-
- avl_insert(&dvert->edge_tree, &edge->tree_node, 0);
- }
-
- return svert;
- }
-
- static void olsr_free_everything(struct avl_tree *vertex_tree)
- {
- struct avl_node *vert_node;
- struct avl_node *edge_node;
- struct olsr_spf_vertex *vert;
- struct olsr_spf_edge *edge;
-
- vert_node = avl_walk_first(vertex_tree);
-
- // loop through all vertices
-
- while (vert_node)
- {
- vert = vert_node->data;
- edge_node = avl_walk_first(&vert->edge_tree);
-
- // loop through all edges of the current vertex
-
- while (edge_node != NULL)
- {
- edge = edge_node->data;
- edge_node = avl_walk_next(edge_node);
- free(edge);
- }
-
- vert_node = avl_walk_next(vert_node);
- free(vert);
- }
- }
-
- /*
* olsr_spf_extract_best
*
* return the node with the minimum pathcost.
*/
! static struct olsr_spf_vertex *
olsr_spf_extract_best (struct avl_tree *tree)
{
--- 142,150 ----
/*
* olsr_spf_extract_best
*
* return the node with the minimum pathcost.
*/
! static struct tc_entry *
olsr_spf_extract_best (struct avl_tree *tree)
{
***************
*** 314,319 ****
! #ifdef DEBUG
! static char *olsr_etx_to_string(float etx)
{
static char buff[20];
--- 157,161 ----
! char *olsr_etx_to_string(float etx)
{
static char buff[20];
***************
*** 325,329 ****
return buff;
}
- #endif
--- 167,170 ----
***************
*** 336,342 ****
*/
static void
! olsr_spf_relax (struct avl_tree *cand_tree, struct olsr_spf_vertex *vert)
{
! struct olsr_spf_edge *edge;
struct avl_node *edge_node;
float new_etx;
--- 177,184 ----
*/
static void
! olsr_spf_relax (struct avl_tree *cand_tree, struct tc_entry *vert)
{
! struct tc_entry *new_vert;
! struct tc_edge_entry *tc_edge;
struct avl_node *edge_node;
float new_etx;
***************
*** 348,398 ****
#endif
! edge_node = avl_walk_first(&vert->edge_tree);
! // loop through all edges of this vertex
! while (edge_node != NULL)
! {
! edge = edge_node->data;
! // total quality of the path through this vertex to the
! // destination of this edge
! new_etx = vert->path_etx + edge->etx;
! // if it's better than the current path quality of this
! // edge's destination, then we've found a better path to
! // this destination
- if (new_etx < edge->dest->path_etx)
- {
/* if this node has been on the candidate tree delete it */
! if (edge->dest->path_etx != INFINITE_ETX) {
! olsr_spf_del_cand_tree(cand_tree, edge->dest);
}
/* re-insert on candidate tree with the better metric */
! edge->dest->path_etx = new_etx;
! olsr_spf_add_cand_tree(cand_tree, edge->dest);
/* pull-up the next-hop and bump the hop count */
if (vert->next_hop) {
! edge->dest->next_hop = vert->next_hop;
}
! edge->dest->hops = vert->hops + 1;
#ifdef DEBUG
OLSR_PRINTF(1, "SPF: better path to %s, cost %s -> %s, via %s, hops %u\n",
! olsr_ip_to_string(&(edge->dest->addr)),
! olsr_etx_to_string(edge->dest->path_etx),
olsr_etx_to_string(new_etx),
olsr_ip_to_string(vert->next_hop ?
&vert->next_hop->neighbor_iface_addr : NULL),
! edge->dest->hops);
#endif
}
-
- edge_node = avl_walk_next(edge_node);
}
}
--- 190,264 ----
#endif
! /*
! * loop through all edges of this vertex.
! */
! for (edge_node = avl_walk_first(&vert->edge_tree);
! edge_node;
! edge_node = avl_walk_next(edge_node)) {
! tc_edge = edge_node->data;
! /*
! * We are not interested in dead-end or dying edges.
! */
! if (!tc_edge->edge_inv || (tc_edge->flags & OLSR_TC_EDGE_DOWN)) {
! #ifdef DEBUG
! OLSR_PRINTF(1, "SPF: ignoring edge %s\n",
! olsr_ip_to_string(&tc_edge->T_dest_addr));
! if (tc_edge->flags & OLSR_TC_EDGE_DOWN) {
! OLSR_PRINTF(1, "SPF: edge down\n");
! }
! if (!tc_edge->edge_inv) {
! OLSR_PRINTF(1, "SPF: no inverse edge\n");
! }
! #endif
! continue;
! }
! /*
! * total quality of the path through this vertex
! * to the destination of this edge
! */
! new_etx = vert->path_etx + tc_edge->etx;
! #ifdef DEBUG
! OLSR_PRINTF(1, "SPF: exploring edge %s, cost %s\n",
! olsr_ip_to_string(&(tc_edge->T_dest_addr)),
! olsr_etx_to_string(new_vert->path_etx));
! #endif
! /*
! * if it's better than the current path quality of this edge's
! * destination node, then we've found a better path to this node.
! */
! new_vert = tc_edge->edge_inv->tc;
! if (new_etx < new_vert->path_etx) {
/* if this node has been on the candidate tree delete it */
! if (new_vert->path_etx != INFINITE_ETX) {
! olsr_spf_del_cand_tree(cand_tree, new_vert);
}
/* re-insert on candidate tree with the better metric */
! new_vert->path_etx = new_etx;
! olsr_spf_add_cand_tree(cand_tree, new_vert);
/* pull-up the next-hop and bump the hop count */
if (vert->next_hop) {
! new_vert->next_hop = vert->next_hop;
}
! new_vert->hops = vert->hops + 1;
#ifdef DEBUG
OLSR_PRINTF(1, "SPF: better path to %s, cost %s -> %s, via %s, hops %u\n",
! olsr_ip_to_string(&new_vert->addr),
! olsr_etx_to_string(new_vert->path_etx),
olsr_etx_to_string(new_etx),
olsr_ip_to_string(vert->next_hop ?
&vert->next_hop->neighbor_iface_addr : NULL),
! new_vert->->hops);
#endif
}
}
}
***************
*** 414,418 ****
int *path_count)
{
! struct olsr_spf_vertex *vert;
*path_count = 0;
--- 280,284 ----
int *path_count)
{
! struct tc_entry *vert;
*path_count = 0;
***************
*** 434,454 ****
olsr_calculate_routing_table (void)
{
! struct avl_tree vertex_tree, cand_tree;
struct list_node path_list;
int i, plen, max_host_plen, path_count = 0;
! struct tc_entry *tcsrc;
! struct topo_dst *tcdst;
! struct olsr_spf_vertex *vert, *myself;
struct neighbor_entry *neigh;
struct mid_address *mid_walker;
- float etx;
struct hna_entry *hna_gw;
struct hna_net *hna;
- struct neighbor_2_entry *neigh2;
struct interface *inter;
struct link_entry *link;
#ifdef SPF_PROFILING
! struct timeval t1, t2, t3, t4, t5, t6, spf_init, spf_run, route, kernel, cleanup, total;
gettimeofday(&t1, NULL);
--- 300,318 ----
olsr_calculate_routing_table (void)
{
! struct avl_tree cand_tree;
struct list_node path_list;
int i, plen, max_host_plen, path_count = 0;
! struct tc_entry *tc;
! struct tc_edge_entry *tc_edge;
! struct tc_entry *vert;
struct neighbor_entry *neigh;
struct mid_address *mid_walker;
struct hna_entry *hna_gw;
struct hna_net *hna;
struct interface *inter;
struct link_entry *link;
#ifdef SPF_PROFILING
! struct timeval t1, t2, t3, t4, t5, spf_init, spf_run, route, kernel, total;
gettimeofday(&t1, NULL);
***************
*** 457,513 ****
max_host_plen = olsr_host_rt_maxplen();
! // initialize the graph
!
! avl_init(&vertex_tree, avl_comp_default);
avl_init(&cand_tree, avl_comp_etx);
list_head_init(&path_list);
-
olsr_bump_routingtree_version();
- // add ourselves to the vertex and candidate tree
-
- myself = olsr_spf_add_vertex(&vertex_tree, &olsr_cnf->main_addr, ZERO_ETX);
- olsr_spf_add_cand_tree(&cand_tree, myself);
-
/*
! * Add our neighbours.
*/
! for (i = 0; i < HASHSIZE; i++)
! for (neigh = neighbortable[i].next; neigh != &neighbortable[i];
! neigh = neigh->next) {
!
! if (neigh->status != SYM)
! continue;
!
! olsr_spf_add_vertex(&vertex_tree, &neigh->neighbor_main_addr, INFINITE_ETX);
! }
!
! // add our two-hop neighbours
!
! for (i = 0; i < HASHSIZE; i++)
! for (neigh2 = two_hop_neighbortable[i].next;
! neigh2 != &two_hop_neighbortable[i];
! neigh2 = neigh2->next) {
!
! olsr_spf_add_vertex(&vertex_tree, &neigh2->neighbor_2_addr, INFINITE_ETX);
! }
! // add remaining vertices
!
! for (i = 0; i < HASHSIZE; i++)
! for (tcsrc = tc_table[i].next; tcsrc != &tc_table[i]; tcsrc = tcsrc->next)
! {
! // add source
!
! olsr_spf_add_vertex(&vertex_tree, &tcsrc->T_last_addr, INFINITE_ETX);
!
! // add destinations of this source
!
! for (tcdst = tcsrc->destinations.next; tcdst != &tcsrc->destinations;
! tcdst = tcdst->next)
! olsr_spf_add_vertex(&vertex_tree, &tcdst->T_dest_addr, INFINITE_ETX);
! }
! // add edges to and from our neighbours
for (i = 0; i < HASHSIZE; i++)
for (neigh = neighbortable[i].next; neigh != &neighbortable[i];
--- 321,349 ----
max_host_plen = olsr_host_rt_maxplen();
! /*
! * Prepare the candidate tree and result list.
! */
avl_init(&cand_tree, avl_comp_etx);
list_head_init(&path_list);
olsr_bump_routingtree_version();
/*
! * Initialize vertices in the lsdb.
*/
! OLSR_FOR_ALL_TC_ENTRIES(tc) {
! tc->next_hop = NULL;
! tc->path_etx = INFINITE_ETX;
! tc->hops = 0;
! } OLSR_FOR_ALL_TC_ENTRIES_END(tc);
! /*
! * zero ourselves and add us to the candidate tree.
! */
! tc_myself->path_etx = ZERO_ETX;
! olsr_spf_add_cand_tree(&cand_tree, tc_myself);
+ /*
+ * add edges to and from our neighbours.
+ */
for (i = 0; i < HASHSIZE; i++)
for (neigh = neighbortable[i].next; neigh != &neighbortable[i];
***************
*** 516,564 ****
if (neigh->status == SYM) {
link = get_best_link_to_neighbor(&neigh->neighbor_main_addr);
if (!link) {
continue;
}
! if (olsr_cnf->lq_level < 2) {
! /* for non-lq the etx is always 1.0 */
! vert = olsr_spf_add_edge(&vertex_tree, &neigh->neighbor_main_addr,
! &olsr_cnf->main_addr, 1.0 );
! vert->next_hop = link;
!
! } else if (link->loss_link_quality2 >= MIN_LINK_QUALITY &&
! link->neigh_link_quality2 >= MIN_LINK_QUALITY) {
!
! etx = 1.0 / (link->loss_link_quality2 * link->neigh_link_quality2);
!
! vert = olsr_spf_add_edge(&vertex_tree, &neigh->neighbor_main_addr,
! &olsr_cnf->main_addr, etx);
! vert->next_hop = link;
}
! }
! }
!
! /* add remaining edges from TC messages */
!
! for (i = 0; i < HASHSIZE; i++)
! for (tcsrc = tc_table[i].next; tcsrc != &tc_table[i]; tcsrc = tcsrc->next)
! for (tcdst = tcsrc->destinations.next; tcdst != &tcsrc->destinations;
! tcdst = tcdst->next) {
!
! if (olsr_cnf->lq_level < 2) {
!
! /* for non-lq the etx is always 1.0 */
! olsr_spf_add_edge(&vertex_tree, &tcdst->T_dest_addr,
! &tcsrc->T_last_addr, 1.0);
!
! } else if (tcdst->link_quality >= MIN_LINK_QUALITY &&
! tcdst->inverse_link_quality >= MIN_LINK_QUALITY) {
!
! etx = 1.0 / (tcdst->link_quality * tcdst->inverse_link_quality);
!
! olsr_spf_add_edge(&vertex_tree, &tcdst->T_dest_addr,
! &tcsrc->T_last_addr, etx);
}
}
#ifdef SPF_PROFILING
--- 352,387 ----
if (neigh->status == SYM) {
+ tc_edge = olsr_lookup_tc_edge(tc_myself, &neigh->neighbor_main_addr);
link = get_best_link_to_neighbor(&neigh->neighbor_main_addr);
if (!link) {
+
+ /*
+ * If there is no best link to this neighbor
+ * and we had an edge before then flush the edge.
+ */
+ if (tc_edge) {
+ olsr_delete_tc_edge_entry(tc_edge);
+ }
continue;
}
! /*
! * Set the next-hops of our neighbors.
! */
! if (!tc_edge) {
! tc_edge = olsr_add_tc_edge_entry(tc_myself, &neigh->neighbor_main_addr,
! 0, link->last_htime,
! link->loss_link_quality2,
! link->neigh_link_quality2);
! } else {
! tc_edge->link_quality = link->loss_link_quality2;
! tc_edge->inverse_link_quality = link->neigh_link_quality2;
! olsr_calc_tc_edge_entry_etx(tc_edge);
}
! if (tc_edge->edge_inv) {
! tc_edge->edge_inv->tc->next_hop = link;
}
}
+ }
#ifdef SPF_PROFILING
***************
*** 652,672 ****
#endif
- /* free the SPF graph */
-
- olsr_free_everything(&vertex_tree);
-
#ifdef SPF_PROFILING
- gettimeofday(&t6, NULL);
-
timersub(&t2, &t1, &spf_init);
timersub(&t3, &t2, &spf_run);
timersub(&t4, &t3, &route);
timersub(&t5, &t4, &kernel);
! timersub(&t6, &t5, &cleanup);
! timersub(&t6, &t1, &total);
! olsr_printf(1, "\n--- SPF-stats for %d nodes, %d routes (total/init/run/route/kern/cleanup): %d, %d, %d, %d, %d, %d\n",
path_count, routingtree.count,
(int)total.tv_usec, (int)spf_init.tv_usec, (int)spf_run.tv_usec,
! (int)route.tv_usec, (int)kernel.tv_usec, (int)cleanup.tv_usec);
#endif
}
--- 475,489 ----
#endif
#ifdef SPF_PROFILING
timersub(&t2, &t1, &spf_init);
timersub(&t3, &t2, &spf_run);
timersub(&t4, &t3, &route);
timersub(&t5, &t4, &kernel);
! timersub(&t5, &t1, &total);
! olsr_printf(1, "\n--- SPF-stats for %d nodes, %d routes (total/init/run/route/kern): "
! "%d, %d, %d, %d, %d\n",
path_count, routingtree.count,
(int)total.tv_usec, (int)spf_init.tv_usec, (int)spf_run.tv_usec,
! (int)route.tv_usec, (int)kernel.tv_usec);
#endif
}
More information about the Olsr-cvs
mailing list