[PATCH 4/4] Handling routing loops
Dean Luga
dluga93 at gmail.com
Sun May 21 23:01:37 CEST 2017
From: dean <dluga93 at gmail.com>
In networks with both routers that support SADR and routers that
don't, there is the possibility of routing loops.
draft-ietf-rtgwg-dst-src-routing-04 describes some ways to avoid
these loops. One of these ways is to detect that the path for an
SADR route passes through a non-SADR router, and replace that route
with a blackhole route.
To be able to do this, I added a new option flag OPT_SADR (0x40)
to indicate SADR capability of a router. This flag will be included
in LSAs, and can be used during the shortest path calculation.
SADR capability of a node can be read from its LSA. SADR capability
of a path can be calculated during the next-hop calculation. If
the destination node doesn't support SADR, or if the path to its
parent contains non-SADR routers, the path to that destination
doesn't support SADR. The SADR capability of the path to a
destination is stored in the nexthop structure for that destination.
To handle inter-area routes, ABRs clear the OPT_SADR bit when
sending inter-area-router-LSAs if the path to the advertised router
includes non-SADR routers. Then, during summary LSA processing
in the reciever, the next hops for an advertised router will have
the SADR capability as indicated in the OPT_SADR flag of the
inter-area-router-LSA.
Now that SADR capability is indicated by the nexthop, the external
LSA processing function (ospf_ext_spf) uses only the SADR capable
nexthops, and deletes the others. In rt_sync, I set the route's
destination to RTD_BLACKHOLE.
---
nest/route.h | 1 +
proto/ospf/ospf.c | 6 +-
proto/ospf/ospf.h | 2 +
proto/ospf/rt.c | 173 ++++++++++++++++++++++++++++++++++++++++++++++----
proto/ospf/topology.c | 8 +++
proto/ospf/topology.h | 6 ++
6 files changed, 184 insertions(+), 12 deletions(-)
diff --git a/nest/route.h b/nest/route.h
index b12d208..6a946dd 100644
--- a/nest/route.h
+++ b/nest/route.h
@@ -367,6 +367,7 @@ struct nexthop {
ip_addr gw; /* Next hop */
struct iface *iface; /* Outgoing interface */
struct nexthop *next;
+ u8 sadr_capability; /* Whether path through this next hop is SADR capable */
byte weight;
byte labels_orig; /* Number of labels before hostentry was applied */
byte labels; /* Number of all labels */
diff --git a/proto/ospf/ospf.c b/proto/ospf/ospf.c
index fc96d48..9e08e49 100644
--- a/proto/ospf/ospf.c
+++ b/proto/ospf/ospf.c
@@ -174,7 +174,8 @@ ospf_area_add(struct ospf_proto *p, struct ospf_area_config *ac)
if (ospf_is_v2(p))
oa->options = ac->type;
else
- oa->options = ac->type | OPT_V6 | (p->stub_router ? 0 : OPT_R);
+ oa->options = ac->type | OPT_V6 | (p->stub_router ? 0 : OPT_R)
+ | (ospf_is_v3_sadr(p) ? OPT_SADR : 0);
ospf_notify_rt_lsa(oa);
}
@@ -620,6 +621,9 @@ ospf_area_reconfigure(struct ospf_area *oa, struct ospf_area_config *nac)
if (ospf_is_v2(p))
oa->options = nac->type;
+ else if (ospf_is_v3_sadr(p))
+ oa->options = nac->type | OPT_V6 | (p->stub_router ? 0 : OPT_R)
+ | (ospf_is_v3_sadr(p) ? OPT_SADR : 0);
else
oa->options = nac->type | OPT_V6 | (p->stub_router ? 0 : OPT_R);
diff --git a/proto/ospf/ospf.h b/proto/ospf/ospf.h
index 9e69bb3..e1d895c 100644
--- a/proto/ospf/ospf.h
+++ b/proto/ospf/ospf.h
@@ -458,6 +458,8 @@ struct ospf_neighbor
#define OPT_R 0x10 /* OSPFv3, originator is active router */
#define OPT_DC 0x20 /* Related to demand circuits, not used */
+#define OPT_SADR 0x40 /* SADR capability bit */
+
/* Router-LSA VEB flags are are stored together with links (OSPFv2) or options (OSPFv3) */
#define OPT_RT_B (0x01 << 24)
#define OPT_RT_E (0x02 << 24)
diff --git a/proto/ospf/rt.c b/proto/ospf/rt.c
index c0559b2..2490687 100644
--- a/proto/ospf/rt.c
+++ b/proto/ospf/rt.c
@@ -40,6 +40,7 @@ new_nexthop(struct ospf_proto *p, ip_addr gw, struct iface *iface, byte weight)
nh->gw = gw;
nh->iface = iface;
nh->weight = weight;
+ nh->sadr_capability = 0;
return nh;
}
@@ -64,7 +65,12 @@ fix_device_nexthops(struct ospf_proto *p, const struct nexthop *n, ip_addr gw)
struct nexthop **nn2 = &root2;
if (!p->ecmp)
- return new_nexthop(p, gw, n->iface, n->weight);
+ {
+ struct nexthop *nh = new_nexthop(p, gw, n->iface, n->weight);
+ if (ospf_is_v3_sadr(p))
+ nh->sadr_capability = n->sadr_capability;
+ return nh;
+ }
/* This is a bit tricky. We cannot just copy the list and update n->gw,
because the list should stay sorted, so we create two lists, one with new
@@ -73,6 +79,8 @@ fix_device_nexthops(struct ospf_proto *p, const struct nexthop *n, ip_addr gw)
for (; n; n = n->next)
{
struct nexthop *nn = new_nexthop(p, ipa_zero(n->gw) ? gw : n->gw, n->iface, n->weight);
+ if (ospf_is_v3_sadr(p))
+ nn->sadr_capability = n->sadr_capability;
if (ipa_zero(n->gw))
{
@@ -731,6 +739,41 @@ link_back(struct ospf_area *oa, struct top_hash_entry *en, struct top_hash_entry
return 0;
}
+/* Returns a copy of abr_nhs but with sadr_capability set to 0 */
+static struct nexthop *
+copy_nhs_no_sadr(struct ospf_proto *p, struct nexthop *abr_nhs)
+{
+ struct nexthop *ret = NULL;
+
+ if (!p->ecmp)
+ ret = new_nexthop(p, abr_nhs->gw, abr_nhs->iface,
+ abr_nhs->weight);
+ else
+ {
+ struct nexthop *nf_nh = NULL, *abr_nh = abr_nhs;
+ do
+ {
+ if (!nf_nh)
+ {
+ nf_nh = new_nexthop(p, abr_nhs->gw, abr_nhs->iface,
+ abr_nhs->weight);
+ ret = nf_nh;
+ abr_nh = abr_nh->next;
+ }
+ else
+ {
+ nf_nh->next = new_nexthop(p, abr_nh->gw, abr_nh->iface,
+ abr_nh->weight);
+ nf_nh = nf_nh->next;
+ abr_nh = abr_nh->next;
+ }
+ } while (abr_nh);
+
+ nf_nh->next = NULL;
+ }
+
+ return ret;
+}
/* RFC 2328 16.2. calculating inter-area routes */
static void
@@ -822,6 +865,11 @@ ospf_rt_sum(struct ospf_area *oa)
.nhs = abr->n.nhs
};
+ /* if a router's SADR capability is not set in the summary LSA, the abr
+ doesn't have an SADR path to that router */
+ if (ospf_is_v3_sadr(p) && !(options & OPT_SADR))
+ nf.nhs = copy_nhs_no_sadr(p, abr->n.nhs);
+
if (type == ORT_NET) {
if (ospf_is_v3_sadr(p)) {
net_addr_sadr_ip6 sadr_net = NET_ADDR_SADR_IP6(net_prefix(&net), net_pxlen(&net), IP6_NONE, 0);
@@ -1222,7 +1270,7 @@ ospf_rt_abr1(struct ospf_proto *p)
{
net_addr_sadr_ip6 sadr_default =
NET_ADDR_SADR_IP6(IP6_NONE, 0, IP6_NONE, 0);
- default_nf = fib_get(&p->rtf, &sadr_default);
+ default_nf = fib_get(&p->rtf, (net_addr *)&sadr_default);
}
else
default_nf = fib_get(&p->rtf, &default_net);
@@ -1479,6 +1527,28 @@ ospf_fib_route(struct fib *f, ip_addr a, ip_addr sa, int slen)
return ospf_fib_route_ip6(f, ipa_to_ip6(a), IP6_MAX_PREFIX_LENGTH);
}
+static struct nexthop *
+copy_sadr_nh(struct ospf_proto *p, struct nexthop *src)
+{
+ struct nexthop *nh = src;
+ struct nexthop *dst = NULL;
+
+ if (!p->ecmp && nh->sadr_capability)
+ {
+ dst = new_nexthop(p, nh->gw, nh->iface, nh->weight);
+ dst->sadr_capability = 1;
+ return dst;
+ }
+
+ while (nh)
+ {
+ if (nh->sadr_capability)
+ dst = nexthop_merge(dst, new_nexthop(p, nh->gw, nh->iface, nh->weight), 1, 1, p->ecmp, NULL);
+ nh = nh->next;
+ }
+
+ return dst;
+}
/* RFC 2328 16.4. calculating external routes */
static void
@@ -1576,7 +1646,13 @@ ospf_ext_spf(struct ospf_proto *p)
if (!rt.fbit)
{
nf2 = nf1;
- nfa.nhs = nf1->n.nhs;
+
+ // if this is an EXT SADR lsa, we only keep the nexthops with sadr capability
+ if (en->lsa_type == LSA_T_EXT_SADR)
+ nfa.nhs = copy_sadr_nh(p, nf1->n.nhs);
+ else
+ nfa.nhs = nf1->n.nhs;
+
br_metric = nf1->n.metric1;
}
else
@@ -1605,7 +1681,12 @@ ospf_ext_spf(struct ospf_proto *p)
if (!nf2->n.nhs)
continue;
- nfa.nhs = nf2->n.nhs;
+ // if this is an EXT SADR lsa, we only keep the nexthops with sadr capability
+ if (en->lsa_type == LSA_T_EXT_SADR)
+ nfa.nhs = copy_sadr_nh(p, nf2->n.nhs);
+ else
+ nfa.nhs = nf2->n.nhs;
+
br_metric = nf2->n.metric1;
/* Replace device nexthops with nexthops to forwarding address from LSA */
@@ -1769,6 +1850,26 @@ inherit_nexthops(struct nexthop *pn)
return pn && (ipa_nonzero(pn->gw) || !pn->iface);
}
+static int
+calc_nh_sadr_capability(struct top_hash_entry *par, struct top_hash_entry *en)
+{
+ int parent_capable = 0;
+
+ struct nexthop *nh = par->nhs;
+ while (nh)
+ {
+ if (nh->sadr_capability)
+ {
+ parent_capable = 1;
+ break;
+ }
+
+ nh = nh->next;
+ }
+
+ return ospf_entry_sadr_capable(en) && parent_capable;
+}
+
static struct nexthop *
calc_next_hop(struct ospf_area *oa, struct top_hash_entry *en,
struct top_hash_entry *par, int pos)
@@ -1784,7 +1885,25 @@ calc_next_hop(struct ospf_area *oa, struct top_hash_entry *en,
/* Usually, we inherit parent nexthops */
if (inherit_nexthops(pn))
+ {
+ // turn off sadr capability if the next node doesn't support SADR
+ if (ospf_is_v3_sadr(p) && !ospf_entry_sadr_capable(en))
+ {
+ if (!p->ecmp)
+ return pn->sadr_capability ? new_nexthop(p, pn->gw, pn->iface, pn->weight) : pn;
+
+ struct nexthop *nh = nexthop_merge(pn, NULL, 0, 0, p->ecmp, p->nhpool);
+ while (nh)
+ {
+ nh->sadr_capability = 0;
+ nh = nh->next;
+ }
+
+ return nh;
+ }
+
return pn;
+ }
/*
* There are three cases:
@@ -1800,7 +1919,12 @@ calc_next_hop(struct ospf_area *oa, struct top_hash_entry *en,
if (!ifa)
return NULL;
- return new_nexthop(p, IPA_NONE, ifa->iface, ifa->ecmp_weight);
+ struct nexthop *nh = new_nexthop(p, IPA_NONE, ifa->iface, ifa->ecmp_weight);
+
+ if (ospf_is_v3_sadr(p))
+ nh->sadr_capability = calc_nh_sadr_capability(par, en);
+
+ return nh;
}
/* The second case - ptp or ptmp neighbor */
@@ -1811,13 +1935,19 @@ calc_next_hop(struct ospf_area *oa, struct top_hash_entry *en,
return NULL;
if (ifa->type == OSPF_IT_VLINK)
- return new_nexthop(p, IPA_NONE, NULL, 0);
+ {
+ struct nexthop *nh = new_nexthop(p, IPA_NONE, NULL, 0);
+ return nh;
+ }
struct ospf_neighbor *m = find_neigh(ifa, rid);
if (!m || (m->state != NEIGHBOR_FULL))
return NULL;
- return new_nexthop(p, m->ip, ifa->iface, ifa->ecmp_weight);
+ struct nexthop *nh = new_nexthop(p, m->ip, ifa->iface, ifa->ecmp_weight);
+ if (ospf_is_v3_sadr(p))
+ nh->sadr_capability = ospf_entry_sadr_capable(en);
+ return nh;
}
/* The third case - bcast or nbma neighbor */
@@ -1855,7 +1985,10 @@ calc_next_hop(struct ospf_area *oa, struct top_hash_entry *en,
if (ip6_zero(llsa->lladdr))
return NULL;
- return new_nexthop(p, ipa_from_ip6(llsa->lladdr), pn->iface, pn->weight);
+ struct nexthop *nh = new_nexthop(p, ipa_from_ip6(llsa->lladdr), pn->iface, pn->weight);
+ if (ospf_is_v3_sadr(p))
+ nh->sadr_capability = calc_nh_sadr_capability(par, en);
+ return nh;
}
}
@@ -2030,11 +2163,28 @@ again1:
}
}
- /* Remove configured stubnets but keep the entries */
if (nf->n.type && !nf->n.nhs)
{
- reset_ri(nf);
- nf->keep = 1;
+ if (nf->n.type == RTS_OSPF_EXT2)
+ {
+ rta a0 = {
+ .src = p->p.main_source,
+ .source = nf->n.type,
+ .scope = SCOPE_UNIVERSE,
+ .dest = RTD_BLACKHOLE,
+ };
+
+ rta *a = rta_lookup(&a0);
+ rte *e = rte_get_temp(a);
+ rte_update(&p->p, nf->fn.addr, e);
+
+ goto blackholed_sadr;
+ }
+ else /* Remove configured stubnets but keep the entries */
+ {
+ reset_ri(nf);
+ nf->keep = 1;
+ }
}
if (nf->n.type) /* Add the route */
@@ -2085,6 +2235,7 @@ again1:
goto again1;
}
}
+blackholed_sadr:
FIB_ITERATE_END;
diff --git a/proto/ospf/topology.c b/proto/ospf/topology.c
index 3891b40..dcc8d09 100644
--- a/proto/ospf/topology.c
+++ b/proto/ospf/topology.c
@@ -1056,7 +1056,15 @@ ospf_originate_sum_rt_lsa(struct ospf_proto *p, struct ospf_area *oa, u32 drid,
if (ospf_is_v2(p))
prepare_sum2_lsa_body(p, 0, metric);
else
+ {
+ // unset the sadr capability flag if there's no sadr path to dst
+ net_addr_ip4 dst_rid = net_from_rid(drid);
+ ort *dst_rt = fib_find(&oa->rtr, (net_addr *)&dst_rid);
+ if (dst_rt && !dst_rt->n.nhs->sadr_capability)
+ options &= ~OPT_SADR;
+
prepare_sum3_rt_lsa_body(p, drid, metric, options & LSA_OPTIONS_MASK);
+ }
ospf_originate_lsa(p, &lsa);
}
diff --git a/proto/ospf/topology.h b/proto/ospf/topology.h
index d1682c5..1d32f9c 100644
--- a/proto/ospf/topology.h
+++ b/proto/ospf/topology.h
@@ -201,6 +201,12 @@ static inline struct top_hash_entry * ospf_hash_find_entry(struct top_graph *f,
static inline struct top_hash_entry * ospf_hash_get_entry(struct top_graph *f, struct top_hash_entry *en)
{ return ospf_hash_get(f, en->domain, en->lsa.id, en->lsa.rt, en->lsa_type); }
+static inline int ospf_entry_sadr_capable(struct top_hash_entry *en)
+{ if (en->lsa_type == LSA_T_NET) return (((struct ospf_lsa_net *)en->lsa_body)->optx & OPT_SADR) ? 1 : 0;
+ else if (en->lsa_type == LSA_T_RT) return (((struct ospf_lsa_rt *)en->lsa_body)->options & OPT_SADR) ? 1 : 0;
+ else return 0;
+}
+
struct top_hash_entry * ospf_hash_find_rt(struct top_graph *f, u32 domain, u32 rtr);
struct top_hash_entry * ospf_hash_find_rt3_first(struct top_graph *f, u32 domain, u32 rtr);
struct top_hash_entry * ospf_hash_find_rt3_next(struct top_hash_entry *e);
--
2.7.4
More information about the Bird-users
mailing list