From 385a1e07b13e53f2d9b3ec06eadd82b3e8bb64fa Mon Sep 17 00:00:00 2001 From: GalaxyGorilla Date: Mon, 26 Oct 2020 11:27:09 +0000 Subject: [PATCH] ospfd: Add support for TI-LFA node protection Signed-off-by: GalaxyGorilla --- doc/user/ospfd.rst | 6 +- ospfd/ospf_spf.c | 154 ++++++++++++++++++++++---- ospfd/ospf_spf.h | 7 +- ospfd/ospf_ti_lfa.c | 211 ++++++++++++++++++++++++++++-------- ospfd/ospf_ti_lfa.h | 10 +- ospfd/ospf_vty.c | 26 ++++- ospfd/ospfd.c | 14 ++- ospfd/ospfd.h | 22 +++- tests/ospfd/common.c | 2 + tests/ospfd/common.h | 1 + tests/ospfd/test_ospf_spf.c | 46 +++++--- tests/ospfd/topologies.c | 134 +++++++++++++++++++++++ 12 files changed, 535 insertions(+), 98 deletions(-) diff --git a/doc/user/ospfd.rst b/doc/user/ospfd.rst index b45427d128..9a40f080f9 100644 --- a/doc/user/ospfd.rst +++ b/doc/user/ospfd.rst @@ -1233,7 +1233,6 @@ Summary Route will be originated on-behalf of all matched external LSAs. Show configuration for display all configured summary routes with matching external LSA information. -====== TI-LFA ====== @@ -1241,11 +1240,10 @@ Experimental support for Topology Independent LFA (Loop-Free Alternate), see for example 'draft-bashandy-rtgwg-segment-routing-ti-lfa-05'. Note that TI-LFA requires a proper Segment Routing configuration. -.. index:: fast-reroute ti-lfa -.. clicmd:: fast-reroute ti-lfa +.. index:: fast-reroute ti-lfa [node-protection] +.. clicmd:: fast-reroute ti-lfa [node-protection] Configured on the router level. Activates TI-LFA for all interfaces. - Currently just link protection for P2P interfaces is supported. Debugging OSPF ============== diff --git a/ospfd/ospf_spf.c b/ospfd/ospf_spf.c index 735cc4027d..cacf858cf2 100644 --- a/ospfd/ospf_spf.c +++ b/ospfd/ospf_spf.c @@ -142,7 +142,7 @@ static void ospf_canonical_nexthops_free(struct vertex *root) ospf_canonical_nexthops_free(child); /* Free child nexthops pointing back to this root vertex */ - for (ALL_LIST_ELEMENTS(child->parents, n2, nn2, vp)) + for (ALL_LIST_ELEMENTS(child->parents, n2, nn2, vp)) { if (vp->parent == root && vp->nexthop) { vertex_nexthop_free(vp->nexthop); vp->nexthop = NULL; @@ -151,6 +151,7 @@ static void ospf_canonical_nexthops_free(struct vertex *root) vp->local_nexthop = NULL; } } + } } } @@ -320,6 +321,22 @@ struct vertex_parent *ospf_spf_vertex_parent_find(struct in_addr id, return NULL; } +struct vertex *ospf_spf_vertex_by_nexthop(struct vertex *root, + struct in_addr *nexthop) +{ + struct listnode *node; + struct vertex *child; + struct vertex_parent *vertex_parent; + + for (ALL_LIST_ELEMENTS_RO(root->children, node, child)) { + vertex_parent = ospf_spf_vertex_parent_find(root->id, child); + if (vertex_parent->nexthop->router.s_addr == nexthop->s_addr) + return child; + } + + return NULL; +} + /* Create a deep copy of a SPF vertex without children and parents */ static struct vertex *ospf_spf_vertex_copy(struct vertex *vertex) { @@ -345,10 +362,9 @@ ospf_spf_vertex_parent_copy(struct vertex_parent *vertex_parent) vertex_parent_copy = XCALLOC(MTYPE_OSPF_VERTEX, sizeof(struct vertex_parent)); - nexthop_copy = - XCALLOC(MTYPE_OSPF_VERTEX, sizeof(struct vertex_nexthop)); - local_nexthop_copy = - XCALLOC(MTYPE_OSPF_VERTEX, sizeof(struct vertex_nexthop)); + + nexthop_copy = vertex_nexthop_new(); + local_nexthop_copy = vertex_nexthop_new(); memcpy(vertex_parent_copy, vertex_parent, sizeof(struct vertex_parent)); memcpy(nexthop_copy, vertex_parent->nexthop, @@ -459,8 +475,8 @@ static void ospf_spf_remove_branch(struct vertex_parent *vertex_parent, } } -int ospf_spf_remove_link(struct vertex *vertex, struct list *vertex_list, - struct router_lsa_link *link) +static int ospf_spf_remove_link(struct vertex *vertex, struct list *vertex_list, + struct router_lsa_link *link) { struct listnode *node, *inner_node; struct vertex *child; @@ -494,6 +510,39 @@ int ospf_spf_remove_link(struct vertex *vertex, struct list *vertex_list, return 1; } +void ospf_spf_remove_resource(struct vertex *vertex, struct list *vertex_list, + struct protected_resource *resource) +{ + struct listnode *node, *nnode; + struct vertex *found; + struct vertex_parent *vertex_parent; + + switch (resource->type) { + case OSPF_TI_LFA_LINK_PROTECTION: + ospf_spf_remove_link(vertex, vertex_list, resource->link); + break; + case OSPF_TI_LFA_NODE_PROTECTION: + found = ospf_spf_vertex_find(resource->router_id, vertex_list); + if (!found) + break; + + /* + * Remove the node by removing all links from its parents. Note + * that the child is automatically removed here with the last + * link from a parent, hence no explicit removal of the node. + */ + for (ALL_LIST_ELEMENTS(found->parents, node, nnode, + vertex_parent)) + ospf_spf_remove_branch(vertex_parent, found, + vertex_list); + + break; + default: + /* do nothing */ + break; + } +} + static void ospf_spf_init(struct ospf_area *area, struct ospf_lsa *root_lsa, bool is_dry_run, bool is_root_node) { @@ -1098,18 +1147,83 @@ static unsigned int ospf_nexthop_calculation(struct ospf_area *area, return added; } -static int ospf_spf_is_protected_link(struct ospf_area *area, - struct router_lsa_link *link) +static int ospf_spf_is_protected_resource(struct ospf_area *area, + struct router_lsa_link *link, + struct lsa_header *lsa) { + uint8_t *p, *lim; struct router_lsa_link *p_link; + struct router_lsa_link *l = NULL; + struct in_addr router_id; + int link_type; - p_link = area->spf_protected_link; - if (!p_link) + if (!area->spf_protected_resource) return 0; - if ((p_link->link_id.s_addr & p_link->link_data.s_addr) - == (link->link_data.s_addr & p_link->link_data.s_addr)) - return 1; + link_type = link->m[0].type; + + switch (area->spf_protected_resource->type) { + case OSPF_TI_LFA_LINK_PROTECTION: + p_link = area->spf_protected_resource->link; + if (!p_link) + return 0; + + /* For P2P: check if the link belongs to the same subnet */ + if (link_type == LSA_LINK_TYPE_POINTOPOINT + && (p_link->link_id.s_addr & p_link->link_data.s_addr) + == (link->link_data.s_addr + & p_link->link_data.s_addr)) + return 1; + + /* For stub: check if this the same subnet */ + if (link_type == LSA_LINK_TYPE_STUB + && (p_link->link_id.s_addr == link->link_id.s_addr) + && (p_link->link_data.s_addr == link->link_data.s_addr)) + return 1; + + break; + case OSPF_TI_LFA_NODE_PROTECTION: + router_id = area->spf_protected_resource->router_id; + if (router_id.s_addr == INADDR_ANY) + return 0; + + /* For P2P: check if the link leads to the protected node */ + if (link_type == LSA_LINK_TYPE_POINTOPOINT + && link->link_id.s_addr == router_id.s_addr) + return 1; + + /* The rest is about stub links! */ + if (link_type != LSA_LINK_TYPE_STUB) + return 0; + + /* + * Check if there's a P2P link in the router LSA with the + * corresponding link data in the same subnet. + */ + + p = ((uint8_t *)lsa) + OSPF_LSA_HEADER_SIZE + 4; + lim = ((uint8_t *)lsa) + ntohs(lsa->length); + + while (p < lim) { + l = (struct router_lsa_link *)p; + p += (OSPF_ROUTER_LSA_LINK_SIZE + + (l->m[0].tos_count * OSPF_ROUTER_LSA_TOS_SIZE)); + + /* We only care about P2P with the proper link id */ + if ((l->m[0].type != LSA_LINK_TYPE_POINTOPOINT) + || (l->link_id.s_addr != router_id.s_addr)) + continue; + + /* Link data in the subnet given by the link? */ + if ((link->link_id.s_addr & link->link_data.s_addr) + == (l->link_data.s_addr & link->link_data.s_addr)) + return 1; + } + + break; + case OSPF_TI_LFA_UNDEFINED_PROTECTION: + break; + } return 0; } @@ -1217,13 +1331,13 @@ static void ospf_spf_next(struct vertex *v, struct ospf_area *area, continue; /* - * Don't process TI-LFA protected links. + * Don't process TI-LFA protected resources. * * TODO: Replace this by a proper solution, e.g. remove * corresponding links from the LSDB and run the SPF * algo with the stripped-down LSDB. */ - if (ospf_spf_is_protected_link(area, l)) + if (ospf_spf_is_protected_resource(area, l, v->lsa)) continue; /* @@ -1475,9 +1589,9 @@ static void ospf_spf_process_stubs(struct ospf_area *area, struct vertex *v, p += (OSPF_ROUTER_LSA_LINK_SIZE + (l->m[0].tos_count * OSPF_ROUTER_LSA_TOS_SIZE)); - /* Don't process TI-LFA protected links */ + /* Don't process TI-LFA protected resources */ if (l->m[0].type == LSA_LINK_TYPE_STUB - && !ospf_spf_is_protected_link(area, l)) + && !ospf_spf_is_protected_resource(area, l, v->lsa)) ospf_intra_add_stub(rt, l, v, area, parent_is_root, lsa_pos); lsa_pos++; @@ -1534,7 +1648,6 @@ void ospf_rtrs_free(struct route_table *rtrs) void ospf_spf_cleanup(struct vertex *spf, struct list *vertex_list) { - /* * Free nexthop information, canonical versions of which are * attached the first level of router vertices attached to the @@ -1721,7 +1834,8 @@ void ospf_spf_calculate_area(struct ospf *ospf, struct ospf_area *area, false, true); if (ospf->ti_lfa_enabled) - ospf_ti_lfa_compute(area, new_table); + ospf_ti_lfa_compute(area, new_table, + ospf->ti_lfa_protection_type); ospf_spf_cleanup(area->spf, area->spf_vertex_list); } diff --git a/ospfd/ospf_spf.h b/ospfd/ospf_spf.h index c341b3ad09..66555be4b7 100644 --- a/ospfd/ospf_spf.h +++ b/ospfd/ospf_spf.h @@ -86,10 +86,13 @@ extern void ospf_spf_calculate_areas(struct ospf *ospf, extern void ospf_rtrs_free(struct route_table *); extern void ospf_spf_cleanup(struct vertex *spf, struct list *vertex_list); extern void ospf_spf_copy(struct vertex *vertex, struct list *vertex_list); -extern int ospf_spf_remove_link(struct vertex *vertex, struct list *vertex_list, - struct router_lsa_link *link); +extern void ospf_spf_remove_resource(struct vertex *vertex, + struct list *vertex_list, + struct protected_resource *resource); extern struct vertex *ospf_spf_vertex_find(struct in_addr id, struct list *vertex_list); +extern struct vertex *ospf_spf_vertex_by_nexthop(struct vertex *root, + struct in_addr *nexthop); 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); diff --git a/ospfd/ospf_ti_lfa.c b/ospfd/ospf_ti_lfa.c index 3771a412de..0830b82f6a 100644 --- a/ospfd/ospf_ti_lfa.c +++ b/ospfd/ospf_ti_lfa.c @@ -24,6 +24,7 @@ #include "prefix.h" #include "table.h" +#include "printfrr.h" #include "ospfd/ospfd.h" #include "ospfd/ospf_asbr.h" @@ -39,6 +40,29 @@ DECLARE_RBTREE_UNIQ(p_spaces, struct p_space, p_spaces_item, DECLARE_RBTREE_UNIQ(q_spaces, struct q_space, q_spaces_item, q_spaces_compare_func) +void ospf_print_protected_resource( + struct protected_resource *protected_resource, char *buf) +{ + struct router_lsa_link *link; + + switch (protected_resource->type) { + case OSPF_TI_LFA_LINK_PROTECTION: + link = protected_resource->link; + snprintfrr(buf, PROTECTED_RESOURCE_STRLEN, + "protected link: %pI4 %pI4", &link->link_id, + &link->link_data); + break; + case OSPF_TI_LFA_NODE_PROTECTION: + snprintfrr(buf, PROTECTED_RESOURCE_STRLEN, + "protected node: %pI4", + &protected_resource->router_id); + break; + case OSPF_TI_LFA_UNDEFINED_PROTECTION: + snprintfrr(buf, PROTECTED_RESOURCE_STRLEN, + "undefined protected resource"); + break; + } +} static void ospf_ti_lfa_find_p_node(struct vertex *pc_node, struct p_space *p_space, @@ -263,7 +287,23 @@ static void ospf_ti_lfa_generate_q_spaces(struct ospf_area *area, struct vertex *child; struct route_table *new_table, *new_rtrs; struct q_space *q_space, q_space_search; - char buf[MPLS_LABEL_STRLEN]; + char label_buf[MPLS_LABEL_STRLEN]; + char res_buf[PROTECTED_RESOURCE_STRLEN]; + + ospf_print_protected_resource(p_space->protected_resource, res_buf); + + /* + * If node protection is used, don't build a Q space for the protected + * node of that particular P space. Move on with children instead. + */ + if (p_space->protected_resource->type == OSPF_TI_LFA_NODE_PROTECTION + && dest->id.s_addr + == p_space->protected_resource->router_id.s_addr) { + /* Recursively generate Q spaces for all children */ + for (ALL_LIST_ELEMENTS_RO(dest->children, node, child)) + ospf_ti_lfa_generate_q_spaces(area, p_space, child); + return; + } /* Check if we already have a Q space for this destination */ q_space_search.root = dest; @@ -289,9 +329,9 @@ static void ospf_ti_lfa_generate_q_spaces(struct ospf_area *area, q_space->vertex_list = area->spf_vertex_list; q_space->label_stack = NULL; - /* 'Cut' the branch of the protected link out of the new SPF tree */ - ospf_spf_remove_link(q_space->root, q_space->vertex_list, - p_space->protected_link); + /* 'Cut' the protected resource out of the new SPF tree */ + ospf_spf_remove_resource(q_space->root, q_space->vertex_list, + p_space->protected_resource); /* * Generate the smallest possible label stack from the root of the P @@ -299,19 +339,20 @@ static void ospf_ti_lfa_generate_q_spaces(struct ospf_area *area, */ ospf_ti_lfa_generate_label_stack(p_space, q_space); + if (q_space->label_stack) { mpls_label2str(q_space->label_stack->num_labels, - q_space->label_stack->label, buf, + q_space->label_stack->label, label_buf, MPLS_LABEL_STRLEN, true); zlog_info( - "%s: Generated label stack %s for root %pI4 and destination %pI4 for protected link %pI4", - __func__, buf, &p_space->root->id, &q_space->root->id, - &p_space->protected_link->link_id); + "%s: Generated label stack %s for root %pI4 and destination %pI4 for %s", + __func__, label_buf, &p_space->root->id, + &q_space->root->id, res_buf); } else { zlog_info( - "%s: NO label stack generated for root %pI4 and destination %pI4 for protected link %pI4", + "%s: NO label stack generated for root %pI4 and destination %pI4 for %s", __func__, &p_space->root->id, &q_space->root->id, - &p_space->protected_link->link_id); + res_buf); } /* We are finished, store the new Q space in the P space struct */ @@ -330,20 +371,22 @@ static void ospf_ti_lfa_generate_post_convergence_spf(struct ospf_area *area, new_table = route_table_init(); new_rtrs = route_table_init(); - area->spf_protected_link = p_space->protected_link; + area->spf_protected_resource = p_space->protected_resource; /* * The 'post convergence' SPF tree is generated here * dry run true, root node false * * So how does this work? During the SPF calculation the algorithm - * checks if a link belongs to a protected stub and then just ignores - * it. This is actually _NOT_ a good way to calculate the post + * checks if a link belongs to a protected resource and then just + * ignores it. + * This is actually _NOT_ a good way to calculate the post * convergence SPF tree. The preferred way would be to delete the - * relevant links from a copy of the LSDB and then just run the SPF - * algorithm on that as usual. However, removing links from router - * LSAs appears to be its own endeavour (because LSAs are stored as a - * 'raw' stream), so we go with this rather hacky way for now. + * relevant links (and nodes) from a copy of the LSDB and then just run + * the SPF algorithm on that as usual. + * However, removing links from router LSAs appears to be its own + * endeavour (because LSAs are stored as a 'raw' stream), so we go with + * this rather hacky way for now. */ ospf_spf_calculate(area, area->router_lsa_self, new_table, new_rtrs, true, false); @@ -351,12 +394,12 @@ static void ospf_ti_lfa_generate_post_convergence_spf(struct ospf_area *area, p_space->pc_spf = area->spf; p_space->pc_vertex_list = area->spf_vertex_list; - area->spf_protected_link = NULL; + area->spf_protected_resource = NULL; } -static void ospf_ti_lfa_generate_p_space(struct ospf_area *area, - struct vertex *child, - struct router_lsa_link *link) +static void +ospf_ti_lfa_generate_p_space(struct ospf_area *area, struct vertex *child, + struct protected_resource *protected_resource) { struct vertex *spf_orig; struct list *vertex_list, *vertex_list_orig; @@ -369,16 +412,16 @@ static void ospf_ti_lfa_generate_p_space(struct ospf_area *area, ospf_spf_copy(area->spf, vertex_list); p_space->root = listnode_head(vertex_list); p_space->vertex_list = vertex_list; - p_space->protected_link = link; + p_space->protected_resource = protected_resource; - /* Initialize the Q spaces for this P space and protected link */ + /* Initialize the Q spaces for this P space and protected resource */ p_space->q_spaces = XCALLOC(MTYPE_OSPF_Q_SPACE, sizeof(struct q_spaces_head)); q_spaces_init(p_space->q_spaces); - /* 'Cut' the child branch out of the new SPF tree */ - ospf_spf_remove_link(p_space->root, p_space->vertex_list, - p_space->protected_link); + /* 'Cut' the protected resource out of the new SPF tree */ + ospf_spf_remove_resource(p_space->root, p_space->vertex_list, + p_space->protected_resource); /* * Since we are going to calculate more SPF trees for Q spaces, keep the @@ -401,7 +444,8 @@ static void ospf_ti_lfa_generate_p_space(struct ospf_area *area, p_spaces_add(area->p_spaces, p_space); } -void ospf_ti_lfa_generate_p_spaces(struct ospf_area *area) +void ospf_ti_lfa_generate_p_spaces(struct ospf_area *area, + enum protection_type protection_type) { struct listnode *node, *inner_node; struct vertex *root, *child; @@ -409,6 +453,7 @@ void ospf_ti_lfa_generate_p_spaces(struct ospf_area *area) uint8_t *p, *lim; struct router_lsa_link *l = NULL; struct prefix stub_prefix, child_prefix; + struct protected_resource *protected_resource; area->p_spaces = XCALLOC(MTYPE_OSPF_P_SPACE, sizeof(struct p_spaces_head)); @@ -439,6 +484,30 @@ void ospf_ti_lfa_generate_p_spaces(struct ospf_area *area) p += (OSPF_ROUTER_LSA_LINK_SIZE + (l->m[0].tos_count * OSPF_ROUTER_LSA_TOS_SIZE)); + /* First comes node protection */ + if (protection_type == OSPF_TI_LFA_NODE_PROTECTION) { + if (l->m[0].type == LSA_LINK_TYPE_POINTOPOINT) { + protected_resource = XCALLOC( + MTYPE_OSPF_P_SPACE, + sizeof(struct protected_resource)); + protected_resource->type = protection_type; + protected_resource->router_id = l->link_id; + child = ospf_spf_vertex_find( + protected_resource->router_id, + root->children); + if (child) + ospf_ti_lfa_generate_p_space( + area, child, + protected_resource); + } + + continue; + } + + /* The rest is about link protection */ + if (protection_type != OSPF_TI_LFA_LINK_PROTECTION) + continue; + if (l->m[0].type != LSA_LINK_TYPE_STUB) continue; @@ -467,26 +536,50 @@ void ospf_ti_lfa_generate_p_spaces(struct ospf_area *area) zlog_info( "%s: Generating P space for %pI4", __func__, &l->link_id); - ospf_ti_lfa_generate_p_space(area, - child, l); + + protected_resource = XCALLOC( + MTYPE_OSPF_P_SPACE, + sizeof(struct + protected_resource)); + protected_resource->type = + protection_type; + protected_resource->link = l; + + ospf_ti_lfa_generate_p_space( + area, child, + protected_resource); } } } } } -static struct p_space * -ospf_ti_lfa_get_p_space_by_nexthop(struct ospf_area *area, - struct in_addr *nexthop) +static struct p_space *ospf_ti_lfa_get_p_space_by_path(struct ospf_area *area, + struct ospf_path *path) { struct p_space *p_space; struct router_lsa_link *link; + struct vertex *child; + int type; frr_each(p_spaces, area->p_spaces, p_space) { - link = p_space->protected_link; - if ((nexthop->s_addr & link->link_data.s_addr) - == (link->link_id.s_addr & link->link_data.s_addr)) - return p_space; + type = p_space->protected_resource->type; + + if (type == OSPF_TI_LFA_LINK_PROTECTION) { + link = p_space->protected_resource->link; + if ((path->nexthop.s_addr & link->link_data.s_addr) + == (link->link_id.s_addr & link->link_data.s_addr)) + return p_space; + } + + if (type == OSPF_TI_LFA_NODE_PROTECTION) { + child = ospf_spf_vertex_by_nexthop(area->spf, + &path->nexthop); + if (child + && p_space->protected_resource->router_id.s_addr + == child->id.s_addr) + return p_space; + } } return NULL; @@ -502,6 +595,7 @@ void ospf_ti_lfa_insert_backup_paths(struct ospf_area *area, struct p_space *p_space; struct q_space *q_space, q_space_search; struct vertex root_search; + char label_buf[MPLS_LABEL_STRLEN]; for (rn = route_top(new_table); rn; rn = route_next(rn)) { or = rn->info; @@ -510,12 +604,22 @@ void ospf_ti_lfa_insert_backup_paths(struct ospf_area *area, /* Insert a backup path for all OSPF paths */ for (ALL_LIST_ELEMENTS_RO(or->paths, node, path)) { - p_space = ospf_ti_lfa_get_p_space_by_nexthop( - area, &path->nexthop); + + if (path->adv_router.s_addr == INADDR_ANY + || path->nexthop.s_addr == INADDR_ANY) + continue; + + zlog_debug( + "%s: attempting to insert backup path for prefix %pFX, router id %pI4 and nexthop %pI4.", + __func__, &rn->p, &path->adv_router, + &path->nexthop); + + p_space = ospf_ti_lfa_get_p_space_by_path(area, path); if (!p_space) { zlog_debug( - "%s: P space not found for nexthop %pI4.", - __func__, &path->nexthop); + "%s: P space not found for router id %pI4 and nexthop %pI4.", + __func__, &path->adv_router, + &path->nexthop); continue; } @@ -532,6 +636,22 @@ void ospf_ti_lfa_insert_backup_paths(struct ospf_area *area, path->srni.backup_label_stack = q_space->label_stack; path->srni.backup_nexthop = q_space->nexthop; + + if (path->srni.backup_label_stack) { + mpls_label2str(q_space->label_stack->num_labels, + q_space->label_stack->label, + label_buf, MPLS_LABEL_STRLEN, + true); + zlog_debug( + "%s: inserted backup path %s for prefix %pFX, router id %pI4 and nexthop %pI4.", + __func__, label_buf, &rn->p, + &path->adv_router, &path->nexthop); + } else { + zlog_debug( + "%s: inserted NO backup path for prefix %pFX, router id %pI4 and nexthop %pI4.", + __func__, &rn->p, &path->adv_router, + &path->nexthop); + } } } } @@ -554,6 +674,7 @@ void ospf_ti_lfa_free_p_spaces(struct ospf_area *area) } ospf_spf_cleanup(p_space->root, p_space->vertex_list); ospf_spf_cleanup(p_space->pc_spf, p_space->pc_vertex_list); + XFREE(MTYPE_OSPF_P_SPACE, p_space->protected_resource); q_spaces_fini(p_space->q_spaces); XFREE(MTYPE_OSPF_Q_SPACE, p_space->q_spaces); @@ -563,13 +684,15 @@ void ospf_ti_lfa_free_p_spaces(struct ospf_area *area) XFREE(MTYPE_OSPF_P_SPACE, area->p_spaces); } -void ospf_ti_lfa_compute(struct ospf_area *area, struct route_table *new_table) +void ospf_ti_lfa_compute(struct ospf_area *area, struct route_table *new_table, + enum protection_type protection_type) { /* - * Generate P spaces per protected link and their respective Q spaces, - * generate backup paths (MPLS label stacks) by finding P/Q nodes. + * Generate P spaces per protected link/node and their respective Q + * spaces, generate backup paths (MPLS label stacks) by finding P/Q + * nodes. */ - ospf_ti_lfa_generate_p_spaces(area); + ospf_ti_lfa_generate_p_spaces(area, protection_type); /* Insert the generated backup paths into the routing table. */ ospf_ti_lfa_insert_backup_paths(area, new_table); diff --git a/ospfd/ospf_ti_lfa.h b/ospfd/ospf_ti_lfa.h index 8f2effae48..bc8f19b98f 100644 --- a/ospfd/ospf_ti_lfa.h +++ b/ospfd/ospf_ti_lfa.h @@ -23,13 +23,19 @@ #ifndef _OSPF_TI_LFA_H #define _OSPF_TI_LFA_H +#define PROTECTED_RESOURCE_STRLEN 100 + extern void ospf_ti_lfa_compute(struct ospf_area *area, - struct route_table *new_table); + struct route_table *new_table, + enum protection_type protection_type); /* unit testing */ -extern void ospf_ti_lfa_generate_p_spaces(struct ospf_area *area); +extern void ospf_ti_lfa_generate_p_spaces(struct ospf_area *area, + enum protection_type protection_type); extern void ospf_ti_lfa_insert_backup_paths(struct ospf_area *area, struct route_table *new_table); extern void ospf_ti_lfa_free_p_spaces(struct ospf_area *area); +void ospf_print_protected_resource( + struct protected_resource *protected_resource, char *buf); #endif /* _OSPF_TI_LFA_H */ diff --git a/ospfd/ospf_vty.c b/ospfd/ospf_vty.c index 4c5c5234ad..c87d357b4b 100644 --- a/ospfd/ospf_vty.c +++ b/ospfd/ospf_vty.c @@ -2602,28 +2602,38 @@ ALIAS(no_ospf_write_multiplier, no_write_multiplier_cmd, "Write multiplier\n" "Maximum number of interface serviced per write\n") -DEFUN(ospf_ti_lfa, ospf_ti_lfa_cmd, "fast-reroute ti-lfa", +DEFUN(ospf_ti_lfa, ospf_ti_lfa_cmd, "fast-reroute ti-lfa [node-protection]", "Fast Reroute for MPLS and IP resilience\n" - "Topology Independent LFA (Loop-Free Alternate)\n") + "Topology Independent LFA (Loop-Free Alternate)\n" + "TI-LFA node protection (default is link protection)\n") { VTY_DECLVAR_INSTANCE_CONTEXT(ospf, ospf); ospf->ti_lfa_enabled = true; + if (argc == 3) + ospf->ti_lfa_protection_type = OSPF_TI_LFA_NODE_PROTECTION; + else + ospf->ti_lfa_protection_type = OSPF_TI_LFA_LINK_PROTECTION; + ospf_spf_calculate_schedule(ospf, SPF_FLAG_CONFIG_CHANGE); return CMD_SUCCESS; } -DEFUN(no_ospf_ti_lfa, no_ospf_ti_lfa_cmd, "no fast-reroute ti-lfa", +DEFUN(no_ospf_ti_lfa, no_ospf_ti_lfa_cmd, + "no fast-reroute ti-lfa [node-protection]", NO_STR "Fast Reroute for MPLS and IP resilience\n" - "Topology Independent LFA (Loop-Free Alternate)\n") + "Topology Independent LFA (Loop-Free Alternate)\n" + "TI-LFA node protection (default is link protection)\n") { VTY_DECLVAR_INSTANCE_CONTEXT(ospf, ospf); ospf->ti_lfa_enabled = false; + ospf->ti_lfa_protection_type = OSPF_TI_LFA_UNDEFINED_PROTECTION; + ospf_spf_calculate_schedule(ospf, SPF_FLAG_CONFIG_CHANGE); return CMD_SUCCESS; @@ -12389,8 +12399,12 @@ static int ospf_config_write_one(struct vty *vty, struct ospf *ospf) } /* TI-LFA print. */ - if (ospf->ti_lfa_enabled) - vty_out(vty, " fast-reroute ti-lfa\n"); + if (ospf->ti_lfa_enabled) { + if (ospf->ti_lfa_protection_type == OSPF_TI_LFA_NODE_PROTECTION) + vty_out(vty, " fast-reroute ti-lfa node-protection\n"); + else + vty_out(vty, " fast-reroute ti-lfa\n"); + } /* Network area print. */ config_write_network_area(vty, ospf); diff --git a/ospfd/ospfd.c b/ospfd/ospfd.c index a0a746488c..56424abeca 100644 --- a/ospfd/ospfd.c +++ b/ospfd/ospfd.c @@ -89,8 +89,18 @@ static void ospf_finish_final(struct ospf *); int p_spaces_compare_func(const struct p_space *a, const struct p_space *b) { - return (a->protected_link->link_id.s_addr - - b->protected_link->link_id.s_addr); + if (a->protected_resource->type == OSPF_TI_LFA_LINK_PROTECTION + && b->protected_resource->type == OSPF_TI_LFA_LINK_PROTECTION) + return (a->protected_resource->link->link_id.s_addr + - b->protected_resource->link->link_id.s_addr); + + if (a->protected_resource->type == OSPF_TI_LFA_NODE_PROTECTION + && b->protected_resource->type == OSPF_TI_LFA_NODE_PROTECTION) + return (a->protected_resource->router_id.s_addr + - b->protected_resource->router_id.s_addr); + + /* This should not happen */ + return 0; } int q_spaces_compare_func(const struct q_space *a, const struct q_space *b) diff --git a/ospfd/ospfd.h b/ospfd/ospfd.h index ad8f561610..f92c967124 100644 --- a/ospfd/ospfd.h +++ b/ospfd/ospfd.h @@ -127,6 +127,13 @@ enum { OSPF_LOG_ADJACENCY_DETAIL = (1 << 4), }; +/* TI-LFA */ +enum protection_type { + OSPF_TI_LFA_UNDEFINED_PROTECTION, + OSPF_TI_LFA_LINK_PROTECTION, + OSPF_TI_LFA_NODE_PROTECTION, +}; + /* OSPF instance structure. */ struct ospf { /* OSPF's running state based on the '[no] router ospf []' @@ -377,6 +384,7 @@ struct ospf { /* TI-LFA support for all interfaces. */ bool ti_lfa_enabled; + enum protection_type ti_lfa_protection_type; QOBJ_FIELDS }; @@ -395,6 +403,16 @@ struct ospf_ti_lfa_node_info { struct in_addr nexthop; }; +struct protected_resource { + enum protection_type type; + + /* Link Protection */ + struct router_lsa_link *link; + + /* Node Protection */ + struct in_addr router_id; +}; + PREDECL_RBTREE_UNIQ(q_spaces) struct q_space { struct vertex *root; @@ -407,7 +425,7 @@ struct q_space { PREDECL_RBTREE_UNIQ(p_spaces) struct p_space { struct vertex *root; - struct router_lsa_link *protected_link; + struct protected_resource *protected_resource; struct q_spaces_head *q_spaces; struct list *vertex_list; struct vertex *pc_spf; @@ -513,7 +531,7 @@ struct ospf_area { root node of the SPF tree */ /* TI-LFA protected link for SPF calculations */ - struct router_lsa_link *spf_protected_link; + struct protected_resource *spf_protected_resource; /* P/Q spaces for TI-LFA */ struct p_spaces_head *p_spaces; diff --git a/tests/ospfd/common.c b/tests/ospfd/common.c index 0ecc0f854e..e5139f799c 100644 --- a/tests/ospfd/common.c +++ b/tests/ospfd/common.c @@ -27,6 +27,8 @@ struct ospf_topology *test_find_topology(const char *name) return &topo2; else if (strmatch(name, "topo3")) return &topo3; + else if (strmatch(name, "topo4")) + return &topo4; return NULL; } diff --git a/tests/ospfd/common.h b/tests/ospfd/common.h index 03e4a53c00..6a6fe97f85 100644 --- a/tests/ospfd/common.h +++ b/tests/ospfd/common.h @@ -34,6 +34,7 @@ extern struct thread_master *master; extern struct ospf_topology topo1; extern struct ospf_topology topo2; extern struct ospf_topology topo3; +extern struct ospf_topology topo4; extern struct zebra_privs_t ospfd_privs; #endif /* _COMMON_OSPF_H */ diff --git a/tests/ospfd/test_ospf_spf.c b/tests/ospfd/test_ospf_spf.c index b55951d193..5757778e40 100644 --- a/tests/ospfd/test_ospf_spf.c +++ b/tests/ospfd/test_ospf_spf.c @@ -47,13 +47,15 @@ static struct ospf *test_init(struct ospf_test_node *root) return ospf; } -static void test_run_spf(struct vty *vty, struct ospf *ospf) +static void test_run_spf(struct vty *vty, struct ospf *ospf, + enum protection_type protection_type) { struct route_table *new_table, *new_rtrs; struct ospf_area *area; struct p_space *p_space; struct q_space *q_space; - char buf[MPLS_LABEL_STRLEN]; + char label_buf[MPLS_LABEL_STRLEN]; + char res_buf[PROTECTED_RESOURCE_STRLEN]; /* Just use the backbone for testing */ area = ospf->backbone; @@ -69,13 +71,15 @@ static void test_run_spf(struct vty *vty, struct ospf *ospf) ospf_route_table_print(vty, new_table); /* TI-LFA testrun */ - ospf_ti_lfa_generate_p_spaces(area); + ospf_ti_lfa_generate_p_spaces(area, protection_type); ospf_ti_lfa_insert_backup_paths(area, new_table); /* Print P/Q space information */ frr_each(p_spaces, area->p_spaces, p_space) { - vty_out(vty, "\n\nP Space for root %pI4 and link %pI4:\n", - &p_space->root->id, &p_space->protected_link->link_id); + ospf_print_protected_resource(p_space->protected_resource, + res_buf); + vty_out(vty, "\n\nP Space for root %pI4 and %s\n", + &p_space->root->id, res_buf); ospf_spf_print(vty, p_space->root, 0); frr_each(q_spaces, p_space->q_spaces, q_space) { @@ -84,17 +88,17 @@ static void test_run_spf(struct vty *vty, struct ospf *ospf) ospf_spf_print(vty, q_space->root, 0); if (q_space->label_stack) { mpls_label2str(q_space->label_stack->num_labels, - q_space->label_stack->label, buf, - MPLS_LABEL_STRLEN, true); - vty_out(vty, "\nLabel stack: %s\n", buf); + q_space->label_stack->label, + label_buf, MPLS_LABEL_STRLEN, + true); + vty_out(vty, "\nLabel stack: %s\n", label_buf); } else { vty_out(vty, "\nLabel stack not generated!\n"); } } - vty_out(vty, - "\nPost-convergence path for root %pI4 and link %pI4:\n", - &p_space->root->id, &p_space->protected_link->link_id); + vty_out(vty, "\nPost-convergence path for root %pI4 and %s\n", + &p_space->root->id, res_buf); ospf_spf_print(vty, p_space->pc_spf, 0); } @@ -111,7 +115,8 @@ static void test_run_spf(struct vty *vty, struct ospf *ospf) } static int test_run(struct vty *vty, struct ospf_topology *topology, - struct ospf_test_node *root) + struct ospf_test_node *root, + enum protection_type protection_type) { struct ospf *ospf; @@ -126,21 +131,25 @@ static int test_run(struct vty *vty, struct ospf_topology *topology, vty_out(vty, "\n"); show_ip_ospf_database_summary(vty, ospf, 0, NULL); - test_run_spf(vty, ospf); + test_run_spf(vty, ospf, protection_type); return 0; } -DEFUN(test_ospf, test_ospf_cmd, "test ospf topology WORD root HOSTNAME", +DEFUN(test_ospf, test_ospf_cmd, + "test ospf topology WORD root HOSTNAME ti-lfa [node-protection]", "Test mode\n" "Choose OSPF for SPF testing\n" "Network topology to choose\n" "Name of the network topology to choose\n" "Root node to choose\n" - "Hostname of the root node to choose\n") + "Hostname of the root node to choose\n" + "Use Topology-Independent LFA\n" + "Use node protection (default is link protection)\n") { struct ospf_topology *topology; struct ospf_test_node *root; + enum protection_type protection_type; int idx = 0; /* Parse topology. */ @@ -158,7 +167,12 @@ DEFUN(test_ospf, test_ospf_cmd, "test ospf topology WORD root HOSTNAME", return CMD_WARNING; } - return test_run(vty, topology, root); + if (argc == 8) + protection_type = OSPF_TI_LFA_NODE_PROTECTION; + else + protection_type = OSPF_TI_LFA_LINK_PROTECTION; + + return test_run(vty, topology, root, protection_type); } static void vty_do_exit(int isexit) diff --git a/tests/ospfd/topologies.c b/tests/ospfd/topologies.c index cf153e675e..ea17a76e28 100644 --- a/tests/ospfd/topologies.c +++ b/tests/ospfd/topologies.c @@ -26,8 +26,12 @@ * | | * +---------+ * + * Link Protection: * P and Q spaces overlap here, hence just one P/Q node regardless of which * link is protected. Hence the backup label stack just has one label. + * + * Node Protection: + * Obviously no backup paths involved. */ struct ospf_topology topo1 = { .nodes = @@ -121,10 +125,15 @@ struct ospf_topology topo1 = { * | | * +---------+ * + * Link Protection: * Regarding the subnet 10.0.1.0/24, the P space of RT1 is just RT1 itself * while the Q space of RT3 consists of RT3 and RT2. Hence the P and Q * nodes are disjunct (tricky: the root node is the P node here). For the * backup label stack just one label is necessary. + * + * Node Protection: + * For protected node RT2 and route from RT1 to RT3 there is just the backup + * path consisting of the label 15002. */ struct ospf_topology topo2 = { .nodes = @@ -217,11 +226,16 @@ struct ospf_topology topo2 = { * | | | | * +---------+ +---------+ * + * Link Protection: * 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/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. + * + * Node Protection: + * For the protected node RT4 and the route from RT1 to RT3 there is a backup + * path with the single label 15001. */ struct ospf_topology topo3 = { .nodes = @@ -316,3 +330,123 @@ struct ospf_topology topo3 = { }, }, }; + +/* + * +---------+ +---------+ + * | | | | + * | RT1 |eth-rt4 eth-rt1| RT5 | + * | 1.1.1.1 +---------------------+ 4.4.4.4 | + * | | 10.0.4.0/24 (10) | | + * +---------+ +---------+ + * |eth+rt2 eth-rt3| + * | | + * |10.0.1.0/24 (10) | + * | 10.0.3.0/24 (10) | + * |eth-rt1 eth-rt4| + * +---------+ +---------+ + * | |eth-rt3 eth-rt2| | + * | RT2 +---------------------+ RT3 | + * | 2.2.2.2 | 10.0.2.0/24 (40) | 3.3.3.3 | + * | | | | + * +---------+ +---------+ + * + * This case was specifically created for Node Protection with RT4 as + * protected node from the perspective of RT1. Note the weight of 40 + * on the link between RT2 and RT3. + * The P space of RT1 is just RT2 while the Q space of RT3 is empty. + * This means that the P and Q spaces are disjunct and there are two + * labels needed to get from RT1 to RT3. + */ +struct ospf_topology topo4 = { + .nodes = + { + { + .hostname = "rt1", + .router_id = "1.1.1.1", + .label = 10, + .adjacencies = + { + { + .hostname = "rt2", + .network = + "10.0.1.1/24", + .metric = 10, + .label = 1, + }, + { + .hostname = "rt4", + .network = + "10.0.4.1/24", + .metric = 10, + .label = 2, + }, + }, + }, + { + .hostname = "rt2", + .router_id = "2.2.2.2", + .label = 20, + .adjacencies = + { + { + .hostname = "rt1", + .network = + "10.0.1.2/24", + .metric = 10, + .label = 3, + }, + { + .hostname = "rt3", + .network = + "10.0.2.1/24", + .metric = 50, + .label = 4, + }, + }, + }, + { + .hostname = "rt3", + .router_id = "3.3.3.3", + .label = 30, + .adjacencies = + { + { + .hostname = "rt2", + .network = + "10.0.2.2/24", + .metric = 50, + .label = 5, + }, + { + .hostname = "rt4", + .network = + "10.0.3.1/24", + .metric = 10, + .label = 6, + }, + }, + }, + { + .hostname = "rt4", + .router_id = "4.4.4.4", + .label = 40, + .adjacencies = + { + { + .hostname = "rt3", + .network = + "10.0.3.2/24", + .metric = 10, + .label = 7, + }, + { + .hostname = "rt1", + .network = + "10.0.4.2/24", + .metric = 10, + .label = 8, + }, + }, + }, + }, +}; -- 2.39.5