From 75aa7aa1352a06c2045c027dc792f14c925aa3a3 Mon Sep 17 00:00:00 2001 From: Renato Westphal Date: Mon, 24 Aug 2020 15:27:15 -0300 Subject: [PATCH] isisd: add abiliy to compute the reverse shortest path tree RFC 7490 says: "The reverse SPF computes the cost from each remote node to root. This is achieved by running the normal SPF algorithm but using the link cost in the direction from the next hop back towards root in place of the link cost in the direction away from root towards the next hop". Support for reverse SPF will be necessary later as it's one of the algorithms used to compute R-LFA/TI-LFA repair paths. Signed-off-by: Renato Westphal --- isisd/fabricd.c | 7 +-- isisd/isis_spf.c | 85 ++++++++++++++++++++++++++++++-- isisd/isis_spf.h | 8 ++- isisd/isis_spf_private.h | 1 + tests/isisd/test_isis_spf.c | 32 ++++++++++-- tests/isisd/test_isis_spf.in | 3 ++ tests/isisd/test_isis_spf.refout | 84 +++++++++++++++++++++++++++++++ 7 files changed, 207 insertions(+), 13 deletions(-) diff --git a/isisd/fabricd.c b/isisd/fabricd.c index 2953ee681c..1a081bbea6 100644 --- a/isisd/fabricd.c +++ b/isisd/fabricd.c @@ -221,9 +221,10 @@ struct fabricd *fabricd_new(struct isis_area *area) rv->area = area; rv->initial_sync_state = FABRICD_SYNC_PENDING; - rv->spftree = isis_spftree_new(area, &area->lspdb[IS_LEVEL_2 - 1], - area->isis->sysid, ISIS_LEVEL2, - SPFTREE_IPV4, F_SPFTREE_HOPCOUNT_METRIC); + rv->spftree = + isis_spftree_new(area, &area->lspdb[IS_LEVEL_2 - 1], + area->isis->sysid, ISIS_LEVEL2, SPFTREE_IPV4, + SPF_TYPE_FORWARD, F_SPFTREE_HOPCOUNT_METRIC); rv->neighbors = skiplist_new(0, neighbor_entry_list_cmp, neighbor_entry_del_void); rv->neighbors_neighbors = hash_create(neighbor_entry_hash_key, diff --git a/isisd/isis_spf.c b/isisd/isis_spf.c index 19a373791e..dd0a6ec824 100644 --- a/isisd/isis_spf.c +++ b/isisd/isis_spf.c @@ -276,7 +276,8 @@ static void isis_spf_adj_free(void *arg) struct isis_spftree *isis_spftree_new(struct isis_area *area, struct lspdb_head *lspdb, const uint8_t *sysid, int level, - enum spf_tree_id tree_id, uint8_t flags) + enum spf_tree_id tree_id, + enum spf_type type, uint8_t flags) { struct isis_spftree *tree; @@ -293,6 +294,7 @@ struct isis_spftree *isis_spftree_new(struct isis_area *area, tree->last_run_monotime = 0; tree->last_run_duration = 0; tree->runcount = 0; + tree->type = type; memcpy(tree->sysid, sysid, ISIS_SYS_ID_LEN); tree->level = level; tree->tree_id = tree_id; @@ -336,9 +338,10 @@ void spftree_area_init(struct isis_area *area) if (area->spftree[tree][level - 1]) continue; - area->spftree[tree][level - 1] = isis_spftree_new( - area, &area->lspdb[level - 1], - area->isis->sysid, level, tree, 0); + area->spftree[tree][level - 1] = + isis_spftree_new(area, &area->lspdb[level - 1], + area->isis->sysid, level, tree, + SPF_TYPE_FORWARD, 0); } } } @@ -956,6 +959,76 @@ static void isis_spf_preload_tent(struct isis_spftree *spftree, } } +struct spf_adj_find_reverse_metric_args { + const uint8_t *id_self; + uint32_t reverse_metric; +}; + +static int spf_adj_find_reverse_metric_cb(const uint8_t *id, uint32_t metric, + bool oldmetric, + struct isis_ext_subtlvs *subtlvs, + void *arg) +{ + struct spf_adj_find_reverse_metric_args *args = arg; + + if (memcmp(id, args->id_self, ISIS_SYS_ID_LEN)) + return LSP_ITER_CONTINUE; + + args->reverse_metric = metric; + + return LSP_ITER_STOP; +} + +/* + * Change all SPF adjacencies to use the link cost in the direction from the + * next hop back towards root in place of the link cost in the direction away + * from root towards the next hop. + */ +static void spf_adj_get_reverse_metrics(struct isis_spftree *spftree) +{ + struct isis_spf_adj *sadj; + struct listnode *node, *nnode; + + for (ALL_LIST_ELEMENTS(spftree->sadj_list, node, nnode, sadj)) { + uint8_t lspid[ISIS_SYS_ID_LEN + 2]; + struct isis_lsp *lsp_adj; + const uint8_t *id_self; + struct spf_adj_find_reverse_metric_args args; + + /* Skip pseudonodes. */ + if (LSP_PSEUDO_ID(sadj->id)) + continue; + + /* Find LSP of the corresponding adjacency. */ + memcpy(lspid, sadj->id, ISIS_SYS_ID_LEN); + LSP_PSEUDO_ID(lspid) = 0; + LSP_FRAGMENT(lspid) = 0; + lsp_adj = lsp_search(spftree->lspdb, lspid); + if (lsp_adj == NULL || lsp_adj->hdr.rem_lifetime == 0) { + /* Delete one-way adjacency. */ + listnode_delete(spftree->sadj_list, sadj); + continue; + } + + /* Find root node in the LSP of the adjacent router. */ + if (CHECK_FLAG(sadj->flags, F_ISIS_SPF_ADJ_BROADCAST)) + id_self = sadj->lan.desig_is_id; + else + id_self = spftree->sysid; + args.id_self = id_self; + args.reverse_metric = UINT32_MAX; + isis_lsp_iterate_is_reach(lsp_adj, spftree->mtid, + spf_adj_find_reverse_metric_cb, + &args); + if (args.reverse_metric == UINT32_MAX) { + /* Delete one-way adjacency. */ + listnode_delete(spftree->sadj_list, sadj); + continue; + } + sadj->metric = args.reverse_metric; + } +} + static void spf_adj_list_parse_tlv(struct isis_spftree *spftree, struct list *adj_list, const uint8_t *id, const uint8_t *desig_is_id, @@ -1092,6 +1165,9 @@ static void isis_spf_build_adj_list(struct isis_spftree *spftree, if (!CHECK_FLAG(spftree->flags, F_SPFTREE_NO_ADJACENCIES)) list_delete(&adj_list); + + if (spftree->type == SPF_TYPE_REVERSE) + spf_adj_get_reverse_metrics(spftree); } /* @@ -1181,6 +1257,7 @@ struct isis_spftree *isis_run_hopcount_spf(struct isis_area *area, if (!spftree) spftree = isis_spftree_new(area, &area->lspdb[IS_LEVEL_2 - 1], sysid, ISIS_LEVEL2, SPFTREE_IPV4, + SPF_TYPE_FORWARD, F_SPFTREE_HOPCOUNT_METRIC); init_spt(spftree, ISIS_MT_IPV4_UNICAST); diff --git a/isisd/isis_spf.h b/isisd/isis_spf.h index 61a107bea2..b2dc23496f 100644 --- a/isisd/isis_spf.h +++ b/isisd/isis_spf.h @@ -26,6 +26,11 @@ struct isis_spftree; +enum spf_type { + SPF_TYPE_FORWARD = 1, + SPF_TYPE_REVERSE, +}; + struct isis_spf_adj { uint8_t id[ISIS_SYS_ID_LEN + 1]; struct isis_adjacency *adj; @@ -43,7 +48,8 @@ struct isis_spf_adj { struct isis_spftree *isis_spftree_new(struct isis_area *area, struct lspdb_head *lspdb, const uint8_t *sysid, int level, - enum spf_tree_id tree_id, uint8_t flags); + enum spf_tree_id tree_id, + enum spf_type type, uint8_t flags); void isis_spf_invalidate_routes(struct isis_spftree *tree); void isis_spf_verify_routes(struct isis_area *area, struct isis_spftree **trees); diff --git a/isisd/isis_spf_private.h b/isisd/isis_spf_private.h index 6bdf900d1c..1e61bf0f48 100644 --- a/isisd/isis_spf_private.h +++ b/isisd/isis_spf_private.h @@ -314,6 +314,7 @@ struct isis_spftree { time_t last_run_monotime; /* last run as monotime for scheduling */ time_t last_run_duration; /* last run duration in msec */ + enum spf_type type; uint8_t sysid[ISIS_SYS_ID_LEN]; uint16_t mtid; int family; diff --git a/tests/isisd/test_isis_spf.c b/tests/isisd/test_isis_spf.c index 4e1d7b050f..dae906b956 100644 --- a/tests/isisd/test_isis_spf.c +++ b/tests/isisd/test_isis_spf.c @@ -38,6 +38,7 @@ enum test_type { TEST_SPF = 1, + TEST_REVERSE_SPF, }; #define F_DISPLAY_LSPDB 0x01 @@ -51,13 +52,15 @@ static struct isis *isis; static void test_run_spf(struct vty *vty, const struct isis_topology *topology, const struct isis_test_node *root, struct isis_area *area, struct lspdb_head *lspdb, - int level, int tree) + int level, int tree, bool reverse) { struct isis_spftree *spftree; + enum spf_type spf_type; /* Run SPF. */ + spf_type = reverse ? SPF_TYPE_REVERSE : SPF_TYPE_FORWARD; spftree = isis_spftree_new(area, lspdb, root->sysid, level, tree, - F_SPFTREE_NO_ADJACENCIES); + spf_type, F_SPFTREE_NO_ADJACENCIES); isis_run_spf(spftree); /* Print the SPT and the corresponding routing table. */ @@ -110,7 +113,12 @@ static int test_run(struct vty *vty, const struct isis_topology *topology, case TEST_SPF: test_run_spf(vty, topology, root, area, &area->lspdb[level - 1], level, - tree); + tree, false); + break; + case TEST_REVERSE_SPF: + test_run_spf(vty, topology, root, area, + &area->lspdb[level - 1], level, + tree, true); break; } } @@ -126,7 +134,11 @@ static int test_run(struct vty *vty, const struct isis_topology *topology, } DEFUN(test_isis, test_isis_cmd, - "test isis topology (1-13) root HOSTNAME spf\ + "test isis topology (1-13) root HOSTNAME\ + <\ + spf\ + |reverse-spf\ + >\ [display-lspdb] [] []", "Test command\n" "IS-IS routing protocol\n" @@ -135,6 +147,7 @@ DEFUN(test_isis, test_isis_cmd, "SPF root\n" "SPF root hostname\n" "Normal Shortest Path First\n" + "Reverse Shortest Path First\n" "Display the LSPDB\n" "Do IPv4 processing only\n" "Do IPv6 processing only\n" @@ -144,6 +157,7 @@ DEFUN(test_isis, test_isis_cmd, uint16_t topology_number; const struct isis_topology *topology; const struct isis_test_node *root; + enum test_type test_type; uint8_t flags = 0; int idx = 0; @@ -165,6 +179,14 @@ DEFUN(test_isis, test_isis_cmd, return CMD_WARNING; } + /* Parse test information. */ + if (argv_find(argv, argc, "spf", &idx)) + test_type = TEST_SPF; + else if (argv_find(argv, argc, "reverse-spf", &idx)) + test_type = TEST_REVERSE_SPF; + else + return CMD_WARNING; + /* Parse control flags. */ if (argv_find(argv, argc, "display-lspdb", &idx)) SET_FLAG(flags, F_DISPLAY_LSPDB); @@ -177,7 +199,7 @@ DEFUN(test_isis, test_isis_cmd, else if (argv_find(argv, argc, "level-2-only", &idx)) SET_FLAG(flags, F_LEVEL2_ONLY); - return test_run(vty, topology, root, TEST_SPF, flags); + return test_run(vty, topology, root, test_type, flags); } static void vty_do_exit(int isexit) diff --git a/tests/isisd/test_isis_spf.in b/tests/isisd/test_isis_spf.in index 28d3c59e1e..d9a61782e9 100644 --- a/tests/isisd/test_isis_spf.in +++ b/tests/isisd/test_isis_spf.in @@ -11,3 +11,6 @@ test isis topology 10 root rt1 spf test isis topology 11 root rt1 spf test isis topology 12 root rt1 spf ipv4-only test isis topology 13 root rt1 spf ipv4-only + +test isis topology 4 root rt1 reverse-spf ipv4-only +test isis topology 11 root rt1 reverse-spf diff --git a/tests/isisd/test_isis_spf.refout b/tests/isisd/test_isis_spf.refout index ee82926197..ed0569947c 100644 --- a/tests/isisd/test_isis_spf.refout +++ b/tests/isisd/test_isis_spf.refout @@ -615,5 +615,89 @@ IS-IS L1 IPv4 routing table: 10.0.255.6/32 30 - rt3 - 10.0.255.7/32 40 - rt3 - +test# +test# test isis topology 4 root rt1 reverse-spf ipv4-only +IS-IS paths to level-1 routers that speak IP +Vertex Type Metric Next-Hop Interface Parent +rt1 +10.0.255.1/32 IP internal 0 rt1(4) +rt2 TE-IS 10 rt2 - rt1(4) +rt3 TE-IS 10 rt3 - rt1(4) +rt4 TE-IS 20 rt2 - rt2(4) +rt5 TE-IS 20 rt3 - rt3(4) +10.0.255.2/32 IP TE 20 rt2 - rt2(4) +10.0.255.3/32 IP TE 20 rt3 - rt3(4) +rt6 TE-IS 30 rt2 - rt4(4) +rt7 TE-IS 30 rt3 - rt5(4) +10.0.255.4/32 IP TE 30 rt2 - rt4(4) +10.0.255.5/32 IP TE 30 rt3 - rt5(4) +rt8 TE-IS 40 rt2 - rt6(4) +10.0.255.6/32 IP TE 40 rt2 - rt6(4) +10.0.255.7/32 IP TE 40 rt3 - rt7(4) +10.0.255.8/32 IP TE 50 rt2 - rt8(4) + +IS-IS L1 IPv4 routing table: + + Prefix Metric Interface Nexthop Label(s) + ----------------------------------------------------- + 10.0.255.2/32 20 - rt2 - + 10.0.255.3/32 20 - rt3 - + 10.0.255.4/32 30 - rt2 - + 10.0.255.5/32 30 - rt3 - + 10.0.255.6/32 40 - rt2 - + 10.0.255.7/32 40 - rt3 - + 10.0.255.8/32 50 - rt2 - + +test# test isis topology 11 root rt1 reverse-spf +IS-IS paths to level-1 routers that speak IP +Vertex Type Metric Next-Hop Interface Parent +rt1 +10.0.255.1/32 IP internal 0 rt1(4) +rt2 TE-IS 10 rt1(4) +rt3 TE-IS 10 rt3 - rt1(4) +rt2 pseudo_TE-IS 20 rt3 - rt3(4) +rt4 TE-IS 20 rt2(4) +rt5 TE-IS 20 rt3 - rt3(4) +10.0.255.2/32 IP TE 20 rt2(4) +10.0.255.3/32 IP TE 20 rt3 - rt3(4) +rt6 TE-IS 30 rt3 - rt4(4) + rt5(4) +10.0.255.4/32 IP TE 30 rt4(4) +10.0.255.5/32 IP TE 30 rt3 - rt5(4) +10.0.255.6/32 IP TE 40 rt3 - rt6(4) + +IS-IS L1 IPv4 routing table: + + Prefix Metric Interface Nexthop Label(s) + ----------------------------------------------------- + 10.0.255.3/32 20 - rt3 - + 10.0.255.5/32 30 - rt3 - + 10.0.255.6/32 40 - rt3 - + +IS-IS paths to level-1 routers that speak IPv6 +Vertex Type Metric Next-Hop Interface Parent +rt1 +2001:db8::1/128 IP6 internal 0 rt1(4) +rt2 TE-IS 10 rt1(4) +rt3 TE-IS 10 rt3 - rt1(4) +rt2 pseudo_TE-IS 20 rt3 - rt3(4) +rt4 TE-IS 20 rt2(4) +rt5 TE-IS 20 rt3 - rt3(4) +2001:db8::2/128 IP6 internal 20 rt2(4) +2001:db8::3/128 IP6 internal 20 rt3 - rt3(4) +rt6 TE-IS 30 rt3 - rt4(4) + rt5(4) +2001:db8::4/128 IP6 internal 30 rt4(4) +2001:db8::5/128 IP6 internal 30 rt3 - rt5(4) +2001:db8::6/128 IP6 internal 40 rt3 - rt6(4) + +IS-IS L1 IPv6 routing table: + + Prefix Metric Interface Nexthop Label(s) + ------------------------------------------------------- + 2001:db8::3/128 20 - rt3 - + 2001:db8::5/128 30 - rt3 - + 2001:db8::6/128 40 - rt3 - + test# end. -- 2.39.5