From dfa9a53a66e5747ddbeedfa0a47fa2ca9fc93b99 Mon Sep 17 00:00:00 2001 From: Ondrej Filip Date: Wed, 26 Apr 2000 12:54:23 +0000 Subject: Routing table calculation. Dijkstra done. --- proto/ospf/Makefile | 2 +- proto/ospf/lsupd.c | 6 -- proto/ospf/lsupd.h | 1 - proto/ospf/ospf.h | 14 ++++- proto/ospf/rt.c | 153 ++++++++++++++++++++++++++++++++++++++++++++++++++ proto/ospf/rt.h | 16 ++++++ proto/ospf/topology.c | 2 +- proto/ospf/topology.h | 7 +++ 8 files changed, 191 insertions(+), 10 deletions(-) create mode 100644 proto/ospf/rt.c create mode 100644 proto/ospf/rt.h (limited to 'proto/ospf') diff --git a/proto/ospf/Makefile b/proto/ospf/Makefile index 632c3b6..f90222c 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 7eff7df..2735695 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 e0ecf09..a03ed8c 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 0039787..939bae7 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 0000000..dbdba11 --- /dev/null +++ b/proto/ospf/rt.c @@ -0,0 +1,153 @@ +/* + * BIRD -- OSPF + * + * (c) 2000 Ondrej Filip + * + * 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 0000000..6eb0bcc --- /dev/null +++ b/proto/ospf/rt.h @@ -0,0 +1,16 @@ +/* + * BIRD -- OSPF + * + * (c) 2000 Ondrej Filip + * + * 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 2200aa2..687b889 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 e146c6f..032a977 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 { -- cgit v1.2.3