/*
* The olsr.org Optimized Link-State Routing daemon(olsrd)
- * Copyright (c) 2004, Andreas Tønnesen(andreto@olsr.org)
+ * Copyright (c) 2004, Andreas Tønnesen(andreto@olsr.org)
+ * RIB implementation (c) 2007, Hannes Gredler (hannes@gredler.at)
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* to the project. For more information see the website or contact
* the copyright holders.
*
- * $Id: routing_table.h,v 1.18 2007/08/02 21:54:54 bernd67 Exp $
*/
#ifndef _OLSR_ROUTING_TABLE
#define _OLSR_ROUTING_TABLE
+#include <sys/types.h>
+#include <sys/time.h>
+#include <sys/socket.h>
+#include <net/if.h>
#include <net/route.h>
#include "hna_set.h"
+#include "link_set.h"
+#include "common/avl.h"
+#include "common/list.h"
#define NETMASK_HOST 0xffffffff
#define NETMASK_DEFAULT 0x0
-struct rt_entry
+/*
+ * the kernel FIB does not need to know the metric of a route.
+ * this saves us from enqueuing/dequeueing hopcount only changes.
+ */
+#define RT_METRIC_DEFAULT 2
+
+/* a composite metric is used for path selection */
+struct rt_metric
{
- union olsr_ip_addr rt_dst;
- union olsr_ip_addr rt_router;
- union hna_netmask rt_mask;
- olsr_u8_t rt_flags;
- olsr_u16_t rt_metric;
- float rt_etx;
- struct interface *rt_if;
- struct rt_entry *prev;
- struct rt_entry *next;
+ olsr_linkcost cost;
+ olsr_u32_t hops;
};
+/* a nexthop is a pointer to a gateway router plus an interface */
+struct rt_nexthop
+{
+ union olsr_ip_addr gateway; /* gateway router */
+ int iif_index; /* outgoing interface index */
+};
-struct destination_n
+/*
+ * Every prefix in our RIB needs a route entry that contains
+ * the nexthop of the best path as installed in the kernel FIB.
+ * The route entry is the root of a rt_path tree of equal prefixes
+ * originated by different routers. It also contains a shortcut
+ * for accessing the best route among all contributing routes.
+ */
+struct rt_entry
{
- struct rt_entry *destination;
- struct destination_n *next;
+ struct olsr_ip_prefix rt_dst;
+ struct avl_node rt_tree_node;
+ struct rt_path *rt_best; /* shortcut to the best path */
+ struct rt_nexthop rt_nexthop; /* nexthop of FIB route */
+ struct rt_metric rt_metric; /* metric of FIB route */
+ struct avl_tree rt_path_tree;
+ struct list_node rt_change_node; /* queue for kernel FIB add/chg/del */
};
+/*
+ * For every received route a rt_path is added to the RIB.
+ * Depending on the results of the SPF calculation we perform a
+ * best_path calculation and pick the one with the lowest etx/metric.
+ * The rt_path gets first inserted into the per tc_entry prefix tree.
+ * If during the SPF calculation the tc_entry becomes reachable via
+ * a local nexthop it is inserted into the global RIB tree.
+ */
+struct rt_path
+{
+ struct rt_entry *rtp_rt; /* backpointer to owning route head */
+ struct tc_entry *rtp_tc; /* backpointer to owning tc entry */
+ struct rt_nexthop rtp_nexthop;
+ struct rt_metric rtp_metric;
+ struct avl_node rtp_tree_node; /* global rtp node */
+ union olsr_ip_addr rtp_originator; /* originator of the route */
+ struct avl_node rtp_prefix_tree_node; /* tc entry rtp node */
+ struct olsr_ip_prefix rtp_dst; /* the prefix */
+ olsr_u32_t rtp_version; /* for detection of outdated rt_paths */
+ olsr_u8_t rtp_origin; /* internal, MID or HNA */
+};
+
+/*
+ * In olsrd we have three different route types.
+ * Internal routes are generated by simple reachability
+ * of a node (by means of a tc message reception).
+ * MID routes result from MID messages and HNA routes
+ * from a gw routers HNA anncouncements.
+ */
+enum olsr_rt_origin {
+ OLSR_RT_ORIGIN_MIN,
+ OLSR_RT_ORIGIN_INT,
+ OLSR_RT_ORIGIN_MID,
+ OLSR_RT_ORIGIN_HNA,
+ OLSR_RT_ORIGIN_MAX
+};
+
+/*
+ * OLSR_FOR_ALL_RT_ENTRIES
+ *
+ * macro for traversing the entire routing table.
+ * 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 rt_entry.
+ */
+#define OLSR_FOR_ALL_RT_ENTRIES(rt) \
+{ \
+ struct avl_node *rt_tree_node, *next_rt_tree_node; \
+ for (rt_tree_node = avl_walk_first(&routingtree); \
+ rt_tree_node; rt_tree_node = next_rt_tree_node) { \
+ next_rt_tree_node = avl_walk_next(rt_tree_node); \
+ rt = rt_tree_node->data;
+#define OLSR_FOR_ALL_RT_ENTRIES_END(rt) }}
+
+/*
+ * OLSR_FOR_ALL_HNA_RT_ENTRIES
+ *
+ * macro for traversing the entire routing table and pick only
+ * HNA routes. This is not optimal - however, If the RIBs become
+ * too big one day then we keep an additional per origin tree
+ * in order to speed up traversal.
+ * In the meantime it is recommended to use this macro because
+ * it hides all the internal datastructure from the callers
+ * and the core maintainers do not have to update all the plugins
+ * once we decide to change the datastructures.
+ */
+#define OLSR_FOR_ALL_HNA_RT_ENTRIES(rt) \
+{ \
+ struct avl_node *rt_tree_node, *next_rt_tree_node; \
+ for (rt_tree_node = avl_walk_first(&routingtree); \
+ rt_tree_node; rt_tree_node = next_rt_tree_node) { \
+ next_rt_tree_node = avl_walk_next(rt_tree_node); \
+ rt = rt_tree_node->data; \
+ if (rt->rt_best->rtp_origin != OLSR_RT_ORIGIN_HNA) \
+ continue;
+#define OLSR_FOR_ALL_HNA_RT_ENTRIES_END(rt) }}
+
/**
* IPv4 <-> IPv6 wrapper
{
struct sockaddr rt_dst;
struct sockaddr rt_gateway;
- olsr_u32_t rt_metric;
+ olsr_u32_t metric;
} v4;
struct
};
-extern struct rt_entry routingtable[HASHSIZE];
-extern struct rt_entry hna_routes[HASHSIZE];
+extern struct avl_tree routingtree;
+extern unsigned int routingtree_version;
-
-int
+void
olsr_init_routing_table(void);
-void
-olsr_calculate_routing_table(void);
+unsigned int olsr_bump_routingtree_version(void);
-void
-olsr_calculate_hna_routes(void);
+int avl_comp_ipv4_prefix (const void *, const void *);
+int avl_comp_ipv6_prefix (const void *, const void *);
-void
-olsr_print_routing_table(struct rt_entry *);
+void olsr_rt_best(struct rt_entry *);
+olsr_bool olsr_nh_change(const struct rt_nexthop *, const struct rt_nexthop *);
+olsr_bool olsr_hopcount_change(const struct rt_metric *, const struct rt_metric *);
+olsr_bool olsr_cmp_rt(const struct rt_entry *, const struct rt_entry *);
+olsr_u8_t olsr_fib_metric(const struct rt_metric *);
-struct rt_entry *
-olsr_insert_routing_table(union olsr_ip_addr *, const union olsr_ip_addr *, struct interface *, int, float);
+char *olsr_rt_to_string(const struct rt_entry *);
+char *olsr_rtp_to_string(const struct rt_path *);
+void olsr_print_routing_table(const struct avl_tree *);
-struct rt_entry *
-olsr_lookup_routing_table(union olsr_ip_addr *);
+const struct rt_nexthop * olsr_get_nh(const struct rt_entry *);
+
+/* rt_path manipulation */
+struct rt_path *olsr_insert_routing_table(union olsr_ip_addr *, int, union olsr_ip_addr *, int);
+void olsr_delete_routing_table(union olsr_ip_addr *, int, union olsr_ip_addr *);
+void olsr_insert_rt_path(struct rt_path *, struct tc_entry *, struct link_entry *);
+void olsr_update_rt_path(struct rt_path *, struct tc_entry *, struct link_entry *);
struct rt_entry *
-olsr_lookup_hna_routing_table(union olsr_ip_addr *dst);
+olsr_lookup_routing_table(const union olsr_ip_addr *);
-void
-olsr_free_routing_table(struct rt_entry *);
#endif
+
+/*
+ * Local Variables:
+ * c-basic-offset: 2
+ * End:
+ */
Repositories / olsrd.git / blobdiff