From cc1725bd3437dfb93084960c4a347133c0c5fe19 Mon Sep 17 00:00:00 2001 From: GalaxyGorilla Date: Thu, 22 Oct 2020 10:05:39 +0000 Subject: [PATCH] ospfd: Make use of adjacency SIDs in TI-LFA When P and Q spaces are adjacent then it makes sense to use adjacency SIDs to from the P node to the Q node. There are some other corner cases where this makes also sense like when a P/Q node adjacent to root node. Signed-off-by: GalaxyGorilla --- ospfd/ospf_spf.c | 15 +++++++++++++++ ospfd/ospf_spf.h | 2 ++ ospfd/ospf_sr.c | 27 +++++++++++++++++++++++++++ ospfd/ospf_sr.h | 5 +++++ ospfd/ospf_ti_lfa.c | 39 +++++++++++++++++++++++++++++++++------ tests/ospfd/common.c | 34 +++++++++++++++++++++++++++++++--- tests/ospfd/common.h | 1 + tests/ospfd/topologies.c | 22 +++++++++++++++++++++- 8 files changed, 135 insertions(+), 10 deletions(-) diff --git a/ospfd/ospf_spf.c b/ospfd/ospf_spf.c index 3a5647ee9f..735cc4027d 100644 --- a/ospfd/ospf_spf.c +++ b/ospfd/ospf_spf.c @@ -305,6 +305,21 @@ struct vertex *ospf_spf_vertex_find(struct in_addr id, struct list *vertex_list) return NULL; } +/* Find a vertex parent according to its router id */ +struct vertex_parent *ospf_spf_vertex_parent_find(struct in_addr id, + struct vertex *vertex) +{ + struct listnode *node; + struct vertex_parent *found; + + for (ALL_LIST_ELEMENTS_RO(vertex->parents, node, found)) { + if (found->parent->id.s_addr == id.s_addr) + return found; + } + + return NULL; +} + /* Create a deep copy of a SPF vertex without children and parents */ static struct vertex *ospf_spf_vertex_copy(struct vertex *vertex) { diff --git a/ospfd/ospf_spf.h b/ospfd/ospf_spf.h index c679e5e71d..c341b3ad09 100644 --- a/ospfd/ospf_spf.h +++ b/ospfd/ospf_spf.h @@ -90,6 +90,8 @@ extern int ospf_spf_remove_link(struct vertex *vertex, struct list *vertex_list, struct router_lsa_link *link); extern struct vertex *ospf_spf_vertex_find(struct in_addr id, struct list *vertex_list); +extern struct vertex_parent *ospf_spf_vertex_parent_find(struct in_addr id, + struct vertex *vertex); extern int vertex_parent_cmp(void *aa, void *bb); extern void ospf_spf_print(struct vty *vty, struct vertex *v, int i); diff --git a/ospfd/ospf_sr.c b/ospfd/ospf_sr.c index f3bb4cef83..efe07e1411 100644 --- a/ospfd/ospf_sr.c +++ b/ospfd/ospf_sr.c @@ -687,6 +687,32 @@ mpls_label_t ospf_sr_get_prefix_sid_by_id(struct in_addr *id) return label; } +/* Get the adjacency sid for a specific 'root' id and 'neighbor' id */ +mpls_label_t ospf_sr_get_adj_sid_by_id(struct in_addr *root_id, + struct in_addr *neighbor_id) +{ + struct sr_node *srn; + struct sr_link *srl; + mpls_label_t label; + struct listnode *node; + + srn = (struct sr_node *)hash_lookup(OspfSR.neighbors, root_id); + + label = MPLS_INVALID_LABEL; + + if (srn) { + for (ALL_LIST_ELEMENTS_RO(srn->ext_link, node, srl)) { + if (srl->type == ADJ_SID + && srl->remote_id.s_addr == neighbor_id->s_addr) { + label = srl->sid[0]; + break; + } + } + } + + return label; +} + /* Get neighbor full structure from address */ static struct ospf_neighbor *get_neighbor_by_addr(struct ospf *top, struct in_addr addr) @@ -1596,6 +1622,7 @@ void ospf_sr_ext_itf_add(struct ext_itf *exti) srl->itf_addr = exti->link.link_data; srl->instance = SET_OPAQUE_LSID(OPAQUE_TYPE_EXTENDED_LINK_LSA, exti->instance); + srl->remote_id = exti->link.link_id; switch (exti->stype) { case ADJ_SID: srl->type = ADJ_SID; diff --git a/ospfd/ospf_sr.h b/ospfd/ospf_sr.h index 13649ad4aa..d8079c9905 100644 --- a/ospfd/ospf_sr.h +++ b/ospfd/ospf_sr.h @@ -290,6 +290,9 @@ struct sr_link { /* 24-bit Opaque-ID field value according to RFC 7684 specification */ uint32_t instance; + /* Addressed (remote) router id */ + struct in_addr remote_id; + /* Interface address */ struct in_addr itf_addr; @@ -364,6 +367,8 @@ extern void ospf_sr_update_task(struct ospf *ospf); /* Support for TI-LFA */ extern mpls_label_t ospf_sr_get_prefix_sid_by_id(struct in_addr *id); +extern mpls_label_t ospf_sr_get_adj_sid_by_id(struct in_addr *root_id, + struct in_addr *neighbor_id); extern struct sr_node *ospf_sr_node_create(struct in_addr *rid); #endif /* _FRR_OSPF_SR_H */ diff --git a/ospfd/ospf_ti_lfa.c b/ospfd/ospf_ti_lfa.c index b0a10845c5..3771a412de 100644 --- a/ospfd/ospf_ti_lfa.c +++ b/ospfd/ospf_ti_lfa.c @@ -178,6 +178,7 @@ static void ospf_ti_lfa_generate_label_stack(struct p_space *p_space, pc_node = ospf_spf_vertex_find(q_space->root->id, p_space->pc_vertex_list); + if (!pc_node) { zlog_debug( "%s: There seems to be no post convergence path (yet).", @@ -193,10 +194,22 @@ static void ospf_ti_lfa_generate_label_stack(struct p_space *p_space, /* Found a PQ node? Then we are done here. */ if (q_node_info.type == OSPF_TI_LFA_PQ_NODE) { - labels[0] = ospf_sr_get_prefix_sid_by_id(&q_node_info.node->id); + /* + * If the PQ node is a child of the root, then we can use an + * adjacency SID instead of a prefix SID for the backup path. + */ + if (ospf_spf_vertex_parent_find(p_space->root->id, + q_node_info.node)) + labels[0] = ospf_sr_get_adj_sid_by_id( + &p_space->root->id, &q_node_info.node->id); + else + labels[0] = ospf_sr_get_prefix_sid_by_id( + &q_node_info.node->id); + q_space->label_stack = ospf_ti_lfa_create_label_stack(labels, 1); q_space->nexthop = q_node_info.nexthop; + return; } @@ -211,19 +224,33 @@ static void ospf_ti_lfa_generate_label_stack(struct p_space *p_space, /* * It can happen that the P node is the root itself, therefore we don't - * need a label for it. + * need a label for it. So just one adjacency SID for the Q node. */ if (p_node_info.node->id.s_addr == p_space->root->id.s_addr) { - labels[0] = ospf_sr_get_prefix_sid_by_id(&q_node_info.node->id); + labels[0] = ospf_sr_get_adj_sid_by_id(&p_space->root->id, + &q_node_info.node->id); q_space->label_stack = ospf_ti_lfa_create_label_stack(labels, 1); q_space->nexthop = q_node_info.nexthop; return; } - /* Otherwise we have a P and also a Q node which we need labels for. */ - labels[0] = ospf_sr_get_prefix_sid_by_id(&p_node_info.node->id); - labels[1] = ospf_sr_get_prefix_sid_by_id(&q_node_info.node->id); + /* + * Otherwise we have a P and also a Q node (which are adjacent). + * + * It can happen that the P node is a child of the root, therefore we + * might just need the adjacency SID for the P node instead of the + * prefix SID. For the Q node always take the adjacency SID. + */ + if (ospf_spf_vertex_parent_find(p_space->root->id, p_node_info.node)) + labels[0] = ospf_sr_get_adj_sid_by_id(&p_space->root->id, + &p_node_info.node->id); + else + labels[0] = ospf_sr_get_prefix_sid_by_id(&p_node_info.node->id); + + labels[1] = ospf_sr_get_adj_sid_by_id(&p_node_info.node->id, + &q_node_info.node->id); + q_space->label_stack = ospf_ti_lfa_create_label_stack(labels, 2); q_space->nexthop = p_node_info.nexthop; } diff --git a/tests/ospfd/common.c b/tests/ospfd/common.c index 16145652bd..0ecc0f854e 100644 --- a/tests/ospfd/common.c +++ b/tests/ospfd/common.c @@ -124,11 +124,17 @@ static void inject_router_lsa(struct vty *vty, struct ospf *ospf, } } -static void inject_sr_db_entry(struct vty *vty, struct ospf_test_node *tnode) +static void inject_sr_db_entry(struct vty *vty, struct ospf_test_node *tnode, + struct ospf_topology *topology) { + struct ospf_test_node *tfound_adj_node; + struct ospf_test_adj *tadj; struct in_addr router_id; + struct in_addr remote_id; struct sr_node *srn; struct sr_prefix *srp; + struct sr_link *srl; + int link_count; inet_aton(tnode->router_id, &router_id); @@ -138,13 +144,35 @@ static void inject_sr_db_entry(struct vty *vty, struct ospf_test_node *tnode) srn->srgb.lower_bound = 16000; srn->msd = 16; - srp = XCALLOC(MTYPE_OSPF_SR_PARAMS, sizeof(struct sr_prefix)); + srn->srlb.range_size = 1000; + srn->srlb.lower_bound = 15000; + /* Prefix SID */ + srp = XCALLOC(MTYPE_OSPF_SR_PARAMS, sizeof(struct sr_prefix)); srp->adv_router = router_id; srp->sid = tnode->label; srp->srn = srn; listnode_add(srn->ext_prefix, srp); + + /* Adjacency SIDs for all adjacencies */ + for (link_count = 0; tnode->adjacencies[link_count].hostname[0]; + link_count++) { + tadj = &tnode->adjacencies[link_count]; + tfound_adj_node = test_find_node(topology, tadj->hostname); + + srl = XCALLOC(MTYPE_OSPF_SR_PARAMS, sizeof(struct sr_link)); + srl->adv_router = router_id; + + inet_aton(tfound_adj_node->router_id, &remote_id); + srl->remote_id = remote_id; + + srl->type = ADJ_SID; + srl->sid[0] = srn->srlb.lower_bound + tadj->label; + srl->srn = srn; + + listnode_add(srn->ext_link, srl); + } } int topology_load(struct vty *vty, struct ospf_topology *topology, @@ -162,7 +190,7 @@ int topology_load(struct vty *vty, struct ospf_topology *topology, * SR information could also be inected via LSAs, but directly * filling the SR DB with labels is just easier. */ - inject_sr_db_entry(vty, tnode); + inject_sr_db_entry(vty, tnode, topology); } return 0; diff --git a/tests/ospfd/common.h b/tests/ospfd/common.h index ce2bb319ed..03e4a53c00 100644 --- a/tests/ospfd/common.h +++ b/tests/ospfd/common.h @@ -8,6 +8,7 @@ struct ospf_test_adj { char hostname[256]; char network[256]; uint32_t metric; + mpls_label_t label; }; struct ospf_test_node { diff --git a/tests/ospfd/topologies.c b/tests/ospfd/topologies.c index 37fd89e49e..cf153e675e 100644 --- a/tests/ospfd/topologies.c +++ b/tests/ospfd/topologies.c @@ -43,12 +43,14 @@ struct ospf_topology topo1 = { .network = "10.0.1.1/24", .metric = 10, + .label = 1, }, { .hostname = "rt3", .network = "10.0.3.1/24", .metric = 10, + .label = 2, }, }, }, @@ -63,12 +65,14 @@ struct ospf_topology topo1 = { .network = "10.0.1.2/24", .metric = 10, + .label = 3, }, { .hostname = "rt3", .network = "10.0.2.1/24", .metric = 10, + .label = 4, }, }, }, @@ -83,12 +87,14 @@ struct ospf_topology topo1 = { .network = "10.0.3.2/24", .metric = 10, + .label = 5, }, { .hostname = "rt2", .network = "10.0.2.2/24", .metric = 10, + .label = 6, }, }, }, @@ -134,12 +140,14 @@ struct ospf_topology topo2 = { .network = "10.0.1.1/24", .metric = 10, + .label = 1, }, { .hostname = "rt3", .network = "10.0.3.1/24", .metric = 30, + .label = 2, }, }, }, @@ -154,12 +162,14 @@ struct ospf_topology topo2 = { .network = "10.0.1.2/24", .metric = 10, + .label = 3, }, { .hostname = "rt3", .network = "10.0.2.1/24", .metric = 10, + .label = 4, }, }, }, @@ -174,12 +184,14 @@ struct ospf_topology topo2 = { .network = "10.0.3.2/24", .metric = 30, + .label = 5, }, { .hostname = "rt2", .network = "10.0.2.2/24", .metric = 10, + .label = 6, }, }, }, @@ -207,7 +219,7 @@ struct ospf_topology topo2 = { * * Regarding the protected subnet 10.0.4.0/24, the P and Q spaces for root RT1 * and destination RT4 are disjunct and the P node is RT2 while RT3 is the Q - * node. Hence the backup label stack here is 16020/16030. Note that here the + * node. Hence the backup label stack here is 16020/15004. Note that here the * P and Q nodes are neither the root nor the destination nodes, so this is a * case where you really need a label stack consisting of two labels. */ @@ -225,12 +237,14 @@ struct ospf_topology topo3 = { .network = "10.0.1.1/24", .metric = 10, + .label = 1, }, { .hostname = "rt4", .network = "10.0.4.1/24", .metric = 10, + .label = 2, }, }, }, @@ -245,12 +259,14 @@ struct ospf_topology topo3 = { .network = "10.0.1.2/24", .metric = 10, + .label = 3, }, { .hostname = "rt3", .network = "10.0.2.1/24", .metric = 20, + .label = 4, }, }, }, @@ -265,12 +281,14 @@ struct ospf_topology topo3 = { .network = "10.0.2.2/24", .metric = 20, + .label = 5, }, { .hostname = "rt4", .network = "10.0.3.1/24", .metric = 10, + .label = 6, }, }, }, @@ -285,12 +303,14 @@ struct ospf_topology topo3 = { .network = "10.0.4.2/24", .metric = 10, + .label = 7, }, { .hostname = "rt3", .network = "10.0.3.2/24", .metric = 10, + .label = 8, }, }, }, -- 2.39.5