summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--proto/ospf/Makefile2
-rw-r--r--proto/ospf/lsupd.c6
-rw-r--r--proto/ospf/lsupd.h1
-rw-r--r--proto/ospf/ospf.h14
-rw-r--r--proto/ospf/rt.c153
-rw-r--r--proto/ospf/rt.h16
-rw-r--r--proto/ospf/topology.c2
-rw-r--r--proto/ospf/topology.h7
8 files changed, 191 insertions, 10 deletions
diff --git a/proto/ospf/Makefile b/proto/ospf/Makefile
index 632c3b6a..f90222cf 100644
--- a/proto/ospf/Makefile
+++ b/proto/ospf/Makefile
@@ -1,4 +1,4 @@
-source=ospf.c topology.c packet.c hello.c neighbor.c iface.c dbdes.c lsreq.c lsupd.c lsack.c lsalib.c
+source=ospf.c topology.c packet.c hello.c neighbor.c iface.c dbdes.c lsreq.c lsupd.c lsack.c lsalib.c rt.c
root-rel=../../
dir-name=proto/ospf
diff --git a/proto/ospf/lsupd.c b/proto/ospf/lsupd.c
index 7eff7dfe..2735695e 100644
--- a/proto/ospf/lsupd.c
+++ b/proto/ospf/lsupd.c
@@ -8,12 +8,6 @@
#include "ospf.h"
-void
-ospf_lsupd_tx(struct ospf_neighbor *n)
-{
- /* FIXME Go on! */
-}
-
int
flood_lsa(struct ospf_neighbor *n, struct ospf_lsa_header *hn,
struct ospf_lsa_header *hh, struct proto_ospf *po, struct ospf_iface *iff,
diff --git a/proto/ospf/lsupd.h b/proto/ospf/lsupd.h
index e0ecf097..a03ed8c5 100644
--- a/proto/ospf/lsupd.h
+++ b/proto/ospf/lsupd.h
@@ -10,7 +10,6 @@
#ifndef _BIRD_OSPF_LSUPD_H_
#define _BIRD_OSPF_LSUPD_H_
-void ospf_lsupd_tx(struct ospf_neighbor *n);
void ospf_lsupd_tx_list(struct ospf_neighbor *n, list *l);
void ospf_lsupd_rx(struct ospf_lsupd_packet *ps, struct proto *p,
struct ospf_iface *ifa, u16 size);
diff --git a/proto/ospf/ospf.h b/proto/ospf/ospf.h
index 00397870..939bae7d 100644
--- a/proto/ospf/ospf.h
+++ b/proto/ospf/ospf.h
@@ -202,6 +202,10 @@ struct ospf_lsa_rt_link_tos { /* Actually we ignore TOS. This is useless */
u16 metric;
};
+struct ospf_lsa_net {
+ u32 netmask;
+};
+
struct ospf_lsa_summ {
u32 netmask;
};
@@ -320,7 +324,9 @@ struct ospf_area {
struct top_graph *gr; /* LSA graph */
slist lsal; /* List of all LSA's */
struct top_hash_entry *rt; /* My own router LSA */
- int stub;
+ list cand; /* List of candidates for RT calc. */
+ u8 stub;
+ u8 trcap; /* Transit capability? */
};
struct proto_ospf {
@@ -330,6 +336,11 @@ struct proto_ospf {
int areano; /* Number of area I belong to */
};
+struct spf_n {
+ node n;
+ struct top_hash_entry *en;
+};
+
static int ospf_start(struct proto *p);
static void ospf_dump(struct proto *p);
static struct proto *ospf_init(struct proto_config *c);
@@ -346,5 +357,6 @@ static void ospf_postconfig(struct proto_config *c);
#include "proto/ospf/lsupd.h"
#include "proto/ospf/lsack.h"
#include "proto/ospf/lsalib.h"
+#include "proto/ospf/rt.h"
#endif /* _BIRD_OSPF_H_ */
diff --git a/proto/ospf/rt.c b/proto/ospf/rt.c
new file mode 100644
index 00000000..dbdba11d
--- /dev/null
+++ b/proto/ospf/rt.c
@@ -0,0 +1,153 @@
+/*
+ * BIRD -- OSPF
+ *
+ * (c) 2000 Ondrej Filip <feela@network.cz>
+ *
+ * Can be freely distributed and used under the terms of the GNU GPL.
+ */
+
+#include "ospf.h"
+
+void
+ospf_rt_spfa(struct ospf_area *oa, struct proto *p)
+{
+ struct top_hash_entry *en;
+ slab *sl;
+ struct spf_n *cn;
+ u32 i,*rts;
+
+ /*
+ * First of all, mark all vertices as they are not in SPF
+ * Maybe I can join this work with Aging of structure
+ */
+
+ WALK_SLIST(SNODE en, oa->lsal)
+ {
+ en->color=OUTSPF;
+ en->dist=LSINFINITY;
+ }
+
+ init_list(&oa->cand); /* Empty list of candidates */
+ oa->trcap=0;
+
+ sl=sl_new(p->pool,sizeof(struct spf_n));
+
+ cn=sl_alloc(sl);
+ cn->en=oa->rt;
+ oa->rt->dist=0;
+ oa->rt->color=CANDIDATE;
+ add_head(&oa->cand,NODE cn);
+
+ while(!EMPTY_LIST(oa->cand))
+ {
+ struct top_hash_entry *act,*tmp;
+ node *n;
+ struct ospf_lsa_rt *rt;
+ struct ospf_lsa_rt_link *rtl;
+ struct ospf_lsa_net *net;
+
+ n=HEAD(oa->cand);
+ act=((struct spf_n *)n)->en;
+ rem_node(n);
+ sl_free(sl,n); /* Good idea? */
+
+ act->color=INSPF;
+ switch(act->lsa.type)
+ {
+ case LSA_T_RT:
+ rt=(struct ospf_lsa_rt *)act->lsa_body;
+ if((rt->VEB)&(1>>LSA_RT_V)) oa->trcap=1;
+ rtl=(struct ospf_lsa_rt_link *)(rt+1);
+ for(i=0;rt->links;i++)
+ {
+ tmp=NULL;
+ switch((rtl+i)->type)
+ {
+ case LSART_STUB:
+ case LSART_VLNK:
+ continue;
+ break;
+ case LSART_NET:
+ tmp=ospf_hash_find(oa->gr,rtl->data,rtl->id,LSA_T_RT);
+ break;
+ case LSART_PTP:
+ tmp=ospf_hash_find(oa->gr,rtl->data,rtl->id,LSA_T_NET);
+ break;
+ default:
+ log("Unknown link type in router lsa.\n");
+ break;
+ }
+ add_cand(&oa->cand,tmp,act->dist+rtl->metric,sl);
+ }
+ break;
+ case LSA_T_NET:
+ net=(struct ospf_lsa_net *)act->lsa_body;
+ rts=(u32 *)(net+1);
+ for(i=0;i<(act->lsa.length-sizeof(struct ospf_lsa_header)-
+ sizeof(struct ospf_lsa_net))/sizeof(u32);i++)
+ {
+ tmp=ospf_hash_find(oa->gr, *rts, *rts, LSA_T_RT);
+ add_cand(&oa->cand,tmp,act->dist,sl);
+ }
+ break;
+ }
+ }
+}
+
+void
+add_cand(list *l, struct top_hash_entry *en, u16 dist, slab *s)
+{
+ struct spf_n *tmp;
+ node *prev;
+ int flag=0;
+
+ if(en==NULL) return;
+ if(en->lsa.age==LSA_MAXAGE) return;
+ /* FIXME Does it have link back? Test it! */
+ if(en->color==INSPF) return;
+
+ if(dist>en->dist) return;
+
+ if(dist==en->dist)
+ {
+ //Next hop calc
+ }
+ else
+ {
+ /* Clear next hop */
+
+ if(en->color==CANDIDATE)
+ {
+ WALK_LIST(tmp,*l)
+ {
+ if(tmp->en==en)
+ {
+ rem_node(NODE tmp);
+ flag=1;
+ break;
+ }
+ }
+ }
+
+ if(flag!=1)
+ {
+ tmp=sl_alloc(s);
+ tmp->en=en;
+ }
+
+ en->dist=dist;
+ en->color=CANDIDATE;
+
+ prev=NULL;
+
+ WALK_LIST(tmp,*l)
+ {
+ if(tmp->en->dist>dist)
+ {
+ if(prev==NULL) add_head(l,NODE tmp);
+ else insert_node(NODE tmp,prev);
+ break;
+ }
+ }
+ }
+}
diff --git a/proto/ospf/rt.h b/proto/ospf/rt.h
new file mode 100644
index 00000000..6eb0bcc3
--- /dev/null
+++ b/proto/ospf/rt.h
@@ -0,0 +1,16 @@
+/*
+ * BIRD -- OSPF
+ *
+ * (c) 2000 Ondrej Filip <feela@network.cz>
+ *
+ * Can be freely distributed and used under the terms of the GNU GPL.
+ *
+ */
+
+#ifndef _BIRD_OSPF_RT_H_
+#define _BIRD_OSPF_RT_H_
+
+void ospf_rt_spfa(struct ospf_area *oa, struct proto *p);
+void add_cand(list *l, struct top_hash_entry *en, u16 dist, slab *s);
+
+#endif /* _BIRD_OSPF_RT_H_ */
diff --git a/proto/ospf/topology.c b/proto/ospf/topology.c
index 2200aa21..687b889e 100644
--- a/proto/ospf/topology.c
+++ b/proto/ospf/topology.c
@@ -175,7 +175,7 @@ addifa_rtlsa(struct ospf_iface *ifa)
{
struct ospf_lsa_header *lsa;
- oa=mb_alloc(po->proto.pool, sizeof(struct ospf_area));
+ oa=mb_allocz(po->proto.pool, sizeof(struct ospf_area));
add_tail(&po->area_list,NODE oa);
oa->areaid=ifa->an;
oa->gr=ospf_top_new(po);
diff --git a/proto/ospf/topology.h b/proto/ospf/topology.h
index e146c6f3..032a977b 100644
--- a/proto/ospf/topology.h
+++ b/proto/ospf/topology.h
@@ -15,6 +15,13 @@ struct top_hash_entry { /* Index for fast mapping (type,rtrid,LSid)->vertex */
struct ospf_lsa_header lsa;
void *lsa_body;
bird_clock_t inst_t; /* Time of installation into DB */
+ list nh; /* List of next hops */
+ u16 dist; /* Distance from the root */
+ u8 color;
+#define OUTSPF 0
+#define CANDIDATE 1
+#define INSPF 2
+ u8 padding;
};
struct top_graph {
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-24 21:18:44 +0000