From e2bbf175a2184bd76f6c54ccf8456babeb1a46fc Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Tue, 9 Apr 2024 15:16:35 +0200 Subject: Adding upstream version 9.1. Signed-off-by: Daniel Baumann --- tests/ospfd/.gitignore | 3 + tests/ospfd/common.c | 249 +++++++++++++++++ tests/ospfd/common.h | 47 ++++ tests/ospfd/subdir.am | 21 ++ tests/ospfd/test_ospf_spf.c | 305 +++++++++++++++++++++ tests/ospfd/test_ospf_spf.in | 10 + tests/ospfd/test_ospf_spf.py | 4 + tests/ospfd/test_ospf_spf.refout | 130 +++++++++ tests/ospfd/topologies.c | 575 +++++++++++++++++++++++++++++++++++++++ 9 files changed, 1344 insertions(+) create mode 100644 tests/ospfd/.gitignore create mode 100644 tests/ospfd/common.c create mode 100644 tests/ospfd/common.h create mode 100644 tests/ospfd/subdir.am create mode 100644 tests/ospfd/test_ospf_spf.c create mode 100644 tests/ospfd/test_ospf_spf.in create mode 100644 tests/ospfd/test_ospf_spf.py create mode 100644 tests/ospfd/test_ospf_spf.refout create mode 100644 tests/ospfd/topologies.c (limited to 'tests/ospfd') diff --git a/tests/ospfd/.gitignore b/tests/ospfd/.gitignore new file mode 100644 index 0000000..c659b64 --- /dev/null +++ b/tests/ospfd/.gitignore @@ -0,0 +1,3 @@ +/*_afl/* +test_ospf_spf +core diff --git a/tests/ospfd/common.c b/tests/ospfd/common.c new file mode 100644 index 0000000..e394186 --- /dev/null +++ b/tests/ospfd/common.c @@ -0,0 +1,249 @@ +#include + +#include "lib/stream.h" +#include "lib/vty.h" +#include "lib/mpls.h" +#include "lib/if.h" +#include "lib/table.h" + +#include "ospfd/ospfd.h" +#include "ospfd/ospf_route.h" +#include "ospfd/ospf_spf.h" +#include "ospfd/ospf_flood.h" +#include "ospfd/ospf_lsa.h" +#include "ospfd/ospf_lsdb.h" +#include "ospfd/ospf_interface.h" +#include "ospfd/ospf_sr.h" + +#include "common.h" + +struct event_loop *master; +struct zebra_privs_t ospfd_privs; + + +struct ospf_topology *test_find_topology(const char *name) +{ + if (strmatch(name, "topo1")) + return &topo1; + else if (strmatch(name, "topo2")) + return &topo2; + else if (strmatch(name, "topo3")) + return &topo3; + else if (strmatch(name, "topo4")) + return &topo4; + else if (strmatch(name, "topo5")) + return &topo5; + + return NULL; +} + +int sort_paths(const void **path1, const void **path2) +{ + const struct ospf_path *p1 = *path1; + const struct ospf_path *p2 = *path2; + + return (p1->nexthop.s_addr - p2->nexthop.s_addr); +} + +void print_route_table(struct vty *vty, struct route_table *rt) +{ + struct route_node *rn; + struct ospf_route * or ; + struct listnode *pnode; + struct ospf_path *path; + struct mpls_label_stack *label_stack; + char buf[MPLS_LABEL_STRLEN]; + + for (rn = route_top(rt); rn; rn = route_next(rn)) { + if ((or = rn->info) == NULL) + continue; + + vty_out(vty, "N %-18pFX %-15pI4 %d\n", &rn->p, + & or->u.std.area_id, or->cost); + + list_sort(or->paths, sort_paths); + + for (ALL_LIST_ELEMENTS_RO(or->paths, pnode, path)) { + if (path->nexthop.s_addr == 0) + continue; + + vty_out(vty, " -> %pI4 with adv router %pI4", + &path->nexthop, &path->adv_router); + + if (path->srni.backup_label_stack) { + label_stack = path->srni.backup_label_stack; + mpls_label2str(label_stack->num_labels, + label_stack->label, buf, + MPLS_LABEL_STRLEN, + ZEBRA_LSP_NONE, true); + vty_out(vty, " and backup path %s", buf); + } + vty_out(vty, "\n"); + } + } +} + +struct ospf_test_node *test_find_node(struct ospf_topology *topology, + const char *hostname) +{ + for (int i = 0; topology->nodes[i].hostname[0]; i++) + if (strmatch(hostname, topology->nodes[i].hostname)) + return &topology->nodes[i]; + + return NULL; +} + +static void inject_router_lsa(struct vty *vty, struct ospf *ospf, + struct ospf_topology *topology, + struct ospf_test_node *root, + struct ospf_test_node *tnode) +{ + struct ospf_area *area; + struct in_addr router_id; + struct in_addr adj_router_id; + struct prefix_ipv4 prefix; + struct in_addr data; + struct stream *s; + struct lsa_header *lsah; + struct ospf_lsa *new; + int length; + unsigned long putp; + uint16_t link_count; + struct ospf_test_node *tfound_adj_node; + struct ospf_test_adj *tadj; + bool is_self_lsa = false; + + area = ospf->backbone; + inet_aton(tnode->router_id, &router_id); + + if (strncmp(root->router_id, tnode->router_id, 256) == 0) + is_self_lsa = true; + + s = stream_new(OSPF_MAX_LSA_SIZE); + lsa_header_set(s, LSA_OPTIONS_GET(area) | LSA_OPTIONS_NSSA_GET(area), + OSPF_ROUTER_LSA, router_id, router_id); + + stream_putc(s, router_lsa_flags(area)); + stream_putc(s, 0); + + putp = stream_get_endp(s); + stream_putw(s, 0); + + 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); + str2prefix_ipv4(tnode->adjacencies[link_count].network, + &prefix); + + inet_aton(tfound_adj_node->router_id, &adj_router_id); + data.s_addr = prefix.prefix.s_addr; + link_info_set(&s, adj_router_id, data, + LSA_LINK_TYPE_POINTOPOINT, 0, tadj->metric); + + masklen2ip(prefix.prefixlen, &data); + link_info_set(&s, prefix.prefix, data, LSA_LINK_TYPE_STUB, 0, + tadj->metric); + } + + /* Don't forget the node itself (just a stub) */ + str2prefix_ipv4(tnode->router_id, &prefix); + data.s_addr = 0xffffffff; + link_info_set(&s, prefix.prefix, data, LSA_LINK_TYPE_STUB, 0, 0); + + /* Take twice the link count (for P2P and stub) plus the local stub */ + stream_putw_at(s, putp, (2 * link_count) + 1); + + length = stream_get_endp(s); + lsah = (struct lsa_header *)STREAM_DATA(s); + lsah->length = htons(length); + + new = ospf_lsa_new_and_data(length); + new->area = area; + new->vrf_id = area->ospf->vrf_id; + + if (is_self_lsa) + SET_FLAG(new->flags, OSPF_LSA_SELF | OSPF_LSA_SELF_CHECKED); + + memcpy(new->data, lsah, length); + stream_free(s); + + ospf_lsdb_add(area->lsdb, new); + + if (is_self_lsa) { + ospf_lsa_unlock(&area->router_lsa_self); + area->router_lsa_self = ospf_lsa_lock(new); + } +} + +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); + + srn = ospf_sr_node_create(&router_id); + + srn->srgb.range_size = 8000; + srn->srgb.lower_bound = 16000; + srn->msd = 16; + + 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, + struct ospf_test_node *root, struct ospf *ospf) +{ + struct ospf_test_node *tnode; + + for (int i = 0; topology->nodes[i].hostname[0]; i++) { + tnode = &topology->nodes[i]; + + /* Inject a router LSA for each node, used for SPF */ + inject_router_lsa(vty, ospf, topology, root, tnode); + + /* + * 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, topology); + } + + return 0; +} diff --git a/tests/ospfd/common.h b/tests/ospfd/common.h new file mode 100644 index 0000000..18e412b --- /dev/null +++ b/tests/ospfd/common.h @@ -0,0 +1,47 @@ +#ifndef _COMMON_OSPF_H +#define _COMMON_OSPF_H + +#define MAX_ADJACENCIES 8 +#define MAX_NODES 12 + +struct ospf_test_adj { + char hostname[256]; + char network[256]; + uint32_t metric; + mpls_label_t label; +}; + +struct ospf_test_node { + char hostname[256]; + const char *router_id; + mpls_label_t label; + struct ospf_test_adj adjacencies[MAX_ADJACENCIES + 1]; +}; + +struct ospf_topology { + struct ospf_test_node nodes[MAX_NODES + 1]; +}; + +/* Prototypes. */ +extern struct ospf_topology *test_find_topology(const char *name); +extern struct ospf_test_node *test_find_node(struct ospf_topology *topology, + const char *hostname); +extern int topology_load(struct vty *vty, struct ospf_topology *topology, + struct ospf_test_node *root, struct ospf *ospf); + +/* Global variables. */ +extern struct event_loop *master; +extern struct ospf_topology topo1; +extern struct ospf_topology topo2; +extern struct ospf_topology topo3; +extern struct ospf_topology topo4; +extern struct ospf_topology topo5; +extern struct zebra_privs_t ospfd_privs; + +/* For stable order in unit tests */ +extern int sort_paths(const void **path1, const void **path2); + +/* Print the routing table */ +extern void print_route_table(struct vty *vty, struct route_table *rt); + +#endif /* _COMMON_OSPF_H */ diff --git a/tests/ospfd/subdir.am b/tests/ospfd/subdir.am new file mode 100644 index 0000000..5ed5b9d --- /dev/null +++ b/tests/ospfd/subdir.am @@ -0,0 +1,21 @@ +if !OSPFD +PYTEST_IGNORE += --ignore=ospfd/ +endif +OSPFD_TEST_LDADD = ospfd/libfrrospf.a $(ALL_TESTS_LDADD) +noinst_HEADERS += \ + tests/ospfd/common.h \ + # end + + +if OSPFD +check_PROGRAMS += tests/ospfd/test_ospf_spf +endif +tests_ospfd_test_ospf_spf_CFLAGS = $(TESTS_CFLAGS) +tests_ospfd_test_ospf_spf_CPPFLAGS = $(TESTS_CPPFLAGS) +tests_ospfd_test_ospf_spf_LDADD = $(OSPFD_TEST_LDADD) +tests_ospfd_test_ospf_spf_SOURCES = tests/ospfd/test_ospf_spf.c tests/ospfd/common.c tests/ospfd/topologies.c +EXTRA_DIST += \ + tests/ospfd/test_ospf_spf.py \ + tests/ospfd/test_ospf_spf.in \ + tests/ospfd/test_ospf_spf.refout \ + # end diff --git a/tests/ospfd/test_ospf_spf.c b/tests/ospfd/test_ospf_spf.c new file mode 100644 index 0000000..fc6b8e8 --- /dev/null +++ b/tests/ospfd/test_ospf_spf.c @@ -0,0 +1,305 @@ +#include + +#include "getopt.h" +#include "frrevent.h" +#include +#include "vty.h" +#include "command.h" +#include "log.h" +#include "vrf.h" +#include "table.h" +#include "mpls.h" + +#include "ospfd/ospfd.h" +#include "ospfd/ospf_asbr.h" +#include "ospfd/ospf_lsa.h" +#include "ospfd/ospf_route.h" +#include "ospfd/ospf_spf.h" +#include "ospfd/ospf_ti_lfa.h" +#include "ospfd/ospf_vty.h" +#include "ospfd/ospf_dump.h" +#include "ospfd/ospf_sr.h" + +#include "common.h" + +DECLARE_RBTREE_UNIQ(p_spaces, struct p_space, p_spaces_item, + p_spaces_compare_func); +DECLARE_RBTREE_UNIQ(q_spaces, struct q_space, q_spaces_item, + q_spaces_compare_func); + +static struct ospf *test_init(struct ospf_test_node *root) +{ + struct ospf *ospf; + struct ospf_area *area; + struct in_addr area_id; + struct in_addr router_id; + + ospf = ospf_new_alloc(0, VRF_DEFAULT_NAME); + + area_id.s_addr = OSPF_AREA_BACKBONE; + area = ospf_area_new(ospf, area_id); + listnode_add_sort(ospf->areas, area); + + inet_aton(root->router_id, &router_id); + ospf->router_id = router_id; + ospf->router_id_static = router_id; + ospf->ti_lfa_enabled = true; + + return ospf; +} + +static void test_run_spf(struct vty *vty, struct ospf *ospf, + enum protection_type protection_type, bool verbose) +{ + struct route_table *new_table, *new_rtrs; + struct route_table *all_rtrs = NULL; + struct ospf_area *area; + struct p_space *p_space; + struct q_space *q_space; + char label_buf[MPLS_LABEL_STRLEN]; + char res_buf[PROTECTED_RESOURCE_STRLEN]; + + /* Just use the backbone for testing */ + area = ospf->backbone; + + new_table = route_table_init(); + new_rtrs = route_table_init(); + all_rtrs = route_table_init(); + + /* dryrun true, root_node false */ + ospf_spf_calculate(area, area->router_lsa_self, new_table, all_rtrs, + new_rtrs, true, false); + + if (verbose) { + vty_out(vty, "SPF Tree without TI-LFA backup paths:\n\n"); + ospf_spf_print(vty, area->spf, 0); + + vty_out(vty, + "\nRouting Table without TI-LFA backup paths:\n\n"); + print_route_table(vty, new_table); + } + + if (verbose) + vty_out(vty, "\n... generating TI-LFA backup paths ...\n"); + + /* TI-LFA testrun */ + ospf_ti_lfa_generate_p_spaces(area, protection_type); + ospf_ti_lfa_insert_backup_paths(area, new_table); + + /* Print P/Q space information */ + if (verbose) { + vty_out(vty, "\nP and Q space info:\n"); + frr_each (p_spaces, area->p_spaces, p_space) { + ospf_print_protected_resource( + p_space->protected_resource, res_buf); + vty_out(vty, "\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) { + vty_out(vty, + "\nQ Space for destination %pI4:\n", + &q_space->root->id); + 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, + label_buf, MPLS_LABEL_STRLEN, + ZEBRA_LSP_NONE, true); + vty_out(vty, "\nLabel stack: %s\n", + label_buf); + } else { + vty_out(vty, + "\nLabel stack not generated!\n"); + } + } + + vty_out(vty, "\nPost-convergence SPF Tree:\n"); + ospf_spf_print(vty, p_space->pc_spf, 0); + } + } + + /* Cleanup */ + ospf_ti_lfa_free_p_spaces(area); + ospf_spf_cleanup(area->spf, area->spf_vertex_list); + + /* + * Print the new routing table which is augmented with TI-LFA backup + * paths (label stacks). + */ + if (verbose) + vty_out(vty, + "\n\nFinal Routing Table including backup paths:\n\n"); + + print_route_table(vty, new_table); +} + +static int test_run(struct vty *vty, struct ospf_topology *topology, + struct ospf_test_node *root, + enum protection_type protection_type, bool verbose) +{ + struct ospf *ospf; + + ospf = test_init(root); + + /* Inject LSAs into the OSPF backbone according to the topology */ + if (topology_load(vty, topology, root, ospf)) { + vty_out(vty, "%% Failed to load topology\n"); + return CMD_WARNING; + } + + if (verbose) { + vty_out(vty, "\n"); + show_ip_ospf_database_summary(vty, ospf, 0, NULL); + } + + test_run_spf(vty, ospf, protection_type, verbose); + + return 0; +} + +DEFUN(test_ospf, test_ospf_cmd, + "test ospf topology WORD root HOSTNAME ti-lfa [node-protection] [verbose]", + "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" + "Use Topology-Independent LFA\n" + "Use node protection (default is link protection)\n" + "Verbose output\n") +{ + struct ospf_topology *topology; + struct ospf_test_node *root; + enum protection_type protection_type = OSPF_TI_LFA_LINK_PROTECTION; + int idx = 0; + bool verbose = false; + + /* Parse topology. */ + argv_find(argv, argc, "topology", &idx); + topology = test_find_topology(argv[idx + 1]->arg); + if (!topology) { + vty_out(vty, "%% Topology not found\n"); + return CMD_WARNING; + } + + argv_find(argv, argc, "root", &idx); + root = test_find_node(topology, argv[idx + 1]->arg); + if (!root) { + vty_out(vty, "%% Root not found\n"); + return CMD_WARNING; + } + + if (argv_find(argv, argc, "node-protection", &idx)) + protection_type = OSPF_TI_LFA_NODE_PROTECTION; + + if (argv_find(argv, argc, "verbose", &idx)) + verbose = true; + + return test_run(vty, topology, root, protection_type, verbose); +} + +static void vty_do_exit(int isexit) +{ + printf("\nend.\n"); + + cmd_terminate(); + vty_terminate(); + event_master_free(master); + + if (!isexit) + exit(0); +} + +struct option longopts[] = {{"help", no_argument, NULL, 'h'}, + {"debug", no_argument, NULL, 'd'}, + {0} }; + +/* Help information display. */ +static void usage(char *progname, int status) +{ + if (status != 0) + fprintf(stderr, "Try `%s --help' for more information.\n", + progname); + else { + printf("Usage : %s [OPTION...]\n\ +ospfd SPF test program.\n\n\ +-u, --debug Enable debugging\n\ +-h, --help Display this help and exit\n\ +\n\ +Report bugs to %s\n", + progname, FRR_BUG_ADDRESS); + } + exit(status); +} + +int main(int argc, char **argv) +{ + char *p; + char *progname; + struct event thread; + bool debug = false; + + /* Set umask before anything for security */ + umask(0027); + + /* get program name */ + progname = ((p = strrchr(argv[0], '/')) ? ++p : argv[0]); + + while (1) { + int opt; + + opt = getopt_long(argc, argv, "hd", longopts, 0); + + if (opt == EOF) + break; + + switch (opt) { + case 0: + break; + case 'd': + debug = true; + break; + case 'h': + usage(progname, 0); + break; + default: + usage(progname, 1); + break; + } + } + + /* master init. */ + master = event_master_create(NULL); + + /* Library inits. */ + cmd_init(1); + cmd_hostname_set("test"); + vty_init(master, false); + if (debug) + zlog_aux_init("NONE: ", LOG_DEBUG); + else + zlog_aux_init("NONE: ", ZLOG_DISABLED); + + /* Install test command. */ + install_element(VIEW_NODE, &test_ospf_cmd); + + /* needed for SR DB init */ + ospf_vty_init(); + ospf_sr_init(); + + term_debug_ospf_ti_lfa = 1; + + /* Read input from .in file. */ + vty_stdio(vty_do_exit); + + /* Fetch next active thread. */ + while (event_fetch(master, &thread)) + event_call(&thread); + + /* Not reached. */ + exit(0); +} diff --git a/tests/ospfd/test_ospf_spf.in b/tests/ospfd/test_ospf_spf.in new file mode 100644 index 0000000..f1e7467 --- /dev/null +++ b/tests/ospfd/test_ospf_spf.in @@ -0,0 +1,10 @@ +test ospf topology topo1 root rt1 ti-lfa +test ospf topology topo1 root rt1 ti-lfa node-protection +test ospf topology topo2 root rt1 ti-lfa +test ospf topology topo2 root rt1 ti-lfa node-protection +test ospf topology topo3 root rt1 ti-lfa +test ospf topology topo3 root rt1 ti-lfa node-protection +test ospf topology topo4 root rt1 ti-lfa +test ospf topology topo4 root rt1 ti-lfa node-protection +test ospf topology topo5 root rt1 ti-lfa +test ospf topology topo5 root rt1 ti-lfa node-protection diff --git a/tests/ospfd/test_ospf_spf.py b/tests/ospfd/test_ospf_spf.py new file mode 100644 index 0000000..92a1c6a --- /dev/null +++ b/tests/ospfd/test_ospf_spf.py @@ -0,0 +1,4 @@ +import frrtest + +class TestOspfSPF(frrtest.TestRefOut): + program = './test_ospf_spf' diff --git a/tests/ospfd/test_ospf_spf.refout b/tests/ospfd/test_ospf_spf.refout new file mode 100644 index 0000000..d1e3c7b --- /dev/null +++ b/tests/ospfd/test_ospf_spf.refout @@ -0,0 +1,130 @@ +test# test ospf topology topo1 root rt1 ti-lfa +N 1.1.1.1/32 0.0.0.0 0 +N 2.2.2.2/32 0.0.0.0 10 + -> 10.0.1.2 with adv router 2.2.2.2 and backup path 15002 +N 3.3.3.3/32 0.0.0.0 10 + -> 10.0.3.2 with adv router 3.3.3.3 and backup path 15001 +N 10.0.1.0/24 0.0.0.0 10 +N 10.0.2.0/24 0.0.0.0 20 + -> 10.0.1.2 with adv router 2.2.2.2 and backup path 15002 + -> 10.0.3.2 with adv router 3.3.3.3 and backup path 15001 +N 10.0.3.0/24 0.0.0.0 10 +test# test ospf topology topo1 root rt1 ti-lfa node-protection +N 1.1.1.1/32 0.0.0.0 0 +N 2.2.2.2/32 0.0.0.0 10 + -> 10.0.1.2 with adv router 2.2.2.2 +N 3.3.3.3/32 0.0.0.0 10 + -> 10.0.3.2 with adv router 3.3.3.3 +N 10.0.1.0/24 0.0.0.0 10 +N 10.0.2.0/24 0.0.0.0 20 + -> 10.0.1.2 with adv router 2.2.2.2 + -> 10.0.3.2 with adv router 3.3.3.3 +N 10.0.3.0/24 0.0.0.0 10 +test# test ospf topology topo2 root rt1 ti-lfa +N 1.1.1.1/32 0.0.0.0 0 +N 2.2.2.2/32 0.0.0.0 10 + -> 10.0.1.2 with adv router 2.2.2.2 and backup path 15002 +N 3.3.3.3/32 0.0.0.0 20 + -> 10.0.1.2 with adv router 3.3.3.3 and backup path 15002 +N 10.0.1.0/24 0.0.0.0 10 +N 10.0.2.0/24 0.0.0.0 20 + -> 10.0.1.2 with adv router 2.2.2.2 and backup path 15002 +N 10.0.3.0/24 0.0.0.0 30 +test# test ospf topology topo2 root rt1 ti-lfa node-protection +N 1.1.1.1/32 0.0.0.0 0 +N 2.2.2.2/32 0.0.0.0 10 + -> 10.0.1.2 with adv router 2.2.2.2 +N 3.3.3.3/32 0.0.0.0 20 + -> 10.0.1.2 with adv router 3.3.3.3 and backup path 15002 +N 10.0.1.0/24 0.0.0.0 10 +N 10.0.2.0/24 0.0.0.0 20 + -> 10.0.1.2 with adv router 2.2.2.2 +N 10.0.3.0/24 0.0.0.0 30 +test# test ospf topology topo3 root rt1 ti-lfa +N 1.1.1.1/32 0.0.0.0 0 +N 2.2.2.2/32 0.0.0.0 10 + -> 10.0.1.2 with adv router 2.2.2.2 and backup path 16030 +N 3.3.3.3/32 0.0.0.0 20 + -> 10.0.4.2 with adv router 3.3.3.3 and backup path 15001 +N 4.4.4.4/32 0.0.0.0 10 + -> 10.0.4.2 with adv router 4.4.4.4 and backup path 15001/15004 +N 10.0.1.0/24 0.0.0.0 10 +N 10.0.2.0/24 0.0.0.0 30 + -> 10.0.1.2 with adv router 2.2.2.2 and backup path 16030 +N 10.0.3.0/24 0.0.0.0 20 + -> 10.0.4.2 with adv router 4.4.4.4 and backup path 15001/15004 +N 10.0.4.0/24 0.0.0.0 10 +test# test ospf topology topo3 root rt1 ti-lfa node-protection +N 1.1.1.1/32 0.0.0.0 0 +N 2.2.2.2/32 0.0.0.0 10 + -> 10.0.1.2 with adv router 2.2.2.2 +N 3.3.3.3/32 0.0.0.0 20 + -> 10.0.4.2 with adv router 3.3.3.3 and backup path 15001 +N 4.4.4.4/32 0.0.0.0 10 + -> 10.0.4.2 with adv router 4.4.4.4 +N 10.0.1.0/24 0.0.0.0 10 +N 10.0.2.0/24 0.0.0.0 30 + -> 10.0.1.2 with adv router 2.2.2.2 +N 10.0.3.0/24 0.0.0.0 20 + -> 10.0.4.2 with adv router 4.4.4.4 +N 10.0.4.0/24 0.0.0.0 10 +test# test ospf topology topo4 root rt1 ti-lfa +N 1.1.1.1/32 0.0.0.0 0 +N 2.2.2.2/32 0.0.0.0 10 + -> 10.0.1.2 with adv router 2.2.2.2 and backup path 16030/15006 +N 3.3.3.3/32 0.0.0.0 20 + -> 10.0.4.2 with adv router 3.3.3.3 and backup path 15001/15004 +N 4.4.4.4/32 0.0.0.0 10 + -> 10.0.4.2 with adv router 4.4.4.4 and backup path 15001/15004 +N 10.0.1.0/24 0.0.0.0 10 +N 10.0.2.0/24 0.0.0.0 60 + -> 10.0.1.2 with adv router 2.2.2.2 and backup path 16030/15006 +N 10.0.3.0/24 0.0.0.0 20 + -> 10.0.4.2 with adv router 4.4.4.4 and backup path 15001/15004 +N 10.0.4.0/24 0.0.0.0 10 +test# test ospf topology topo4 root rt1 ti-lfa node-protection +N 1.1.1.1/32 0.0.0.0 0 +N 2.2.2.2/32 0.0.0.0 10 + -> 10.0.1.2 with adv router 2.2.2.2 +N 3.3.3.3/32 0.0.0.0 20 + -> 10.0.4.2 with adv router 3.3.3.3 and backup path 15001/15004 +N 4.4.4.4/32 0.0.0.0 10 + -> 10.0.4.2 with adv router 4.4.4.4 +N 10.0.1.0/24 0.0.0.0 10 +N 10.0.2.0/24 0.0.0.0 60 + -> 10.0.1.2 with adv router 2.2.2.2 +N 10.0.3.0/24 0.0.0.0 20 + -> 10.0.4.2 with adv router 4.4.4.4 +N 10.0.4.0/24 0.0.0.0 10 +test# test ospf topology topo5 root rt1 ti-lfa +N 1.1.1.1/32 0.0.0.0 0 +N 2.2.2.2/32 0.0.0.0 30 + -> 10.0.4.2 with adv router 2.2.2.2 and backup path 15001 +N 3.3.3.3/32 0.0.0.0 20 + -> 10.0.4.2 with adv router 3.3.3.3 and backup path 15001/15004 +N 4.4.4.4/32 0.0.0.0 10 + -> 10.0.4.2 with adv router 4.4.4.4 and backup path 15001/15004/15006 +N 10.0.1.0/24 0.0.0.0 40 + -> 10.0.4.2 with adv router 2.2.2.2 and backup path 15001 +N 10.0.2.0/24 0.0.0.0 30 + -> 10.0.4.2 with adv router 3.3.3.3 and backup path 15001/15004 +N 10.0.3.0/24 0.0.0.0 20 + -> 10.0.4.2 with adv router 4.4.4.4 and backup path 15001/15004/15006 +N 10.0.4.0/24 0.0.0.0 10 +test# test ospf topology topo5 root rt1 ti-lfa node-protection +N 1.1.1.1/32 0.0.0.0 0 +N 2.2.2.2/32 0.0.0.0 30 + -> 10.0.4.2 with adv router 2.2.2.2 and backup path 15001 +N 3.3.3.3/32 0.0.0.0 20 + -> 10.0.4.2 with adv router 3.3.3.3 and backup path 15001/15004 +N 4.4.4.4/32 0.0.0.0 10 + -> 10.0.4.2 with adv router 4.4.4.4 +N 10.0.1.0/24 0.0.0.0 40 + -> 10.0.4.2 with adv router 2.2.2.2 and backup path 15001 +N 10.0.2.0/24 0.0.0.0 30 + -> 10.0.4.2 with adv router 3.3.3.3 and backup path 15001/15004 +N 10.0.3.0/24 0.0.0.0 20 + -> 10.0.4.2 with adv router 4.4.4.4 +N 10.0.4.0/24 0.0.0.0 10 +test# +end. diff --git a/tests/ospfd/topologies.c b/tests/ospfd/topologies.c new file mode 100644 index 0000000..2dc611c --- /dev/null +++ b/tests/ospfd/topologies.c @@ -0,0 +1,575 @@ +#include + +#include "mpls.h" +#include "if.h" + +#include "ospfd/ospfd.h" + +#include "common.h" + +/* + * +---------+ +---------+ + * | | | | + * | RT1 |eth-rt2 eth-rt1| RT2 | + * | 1.1.1.1 +---------------------+ 2.2.2.2 | + * | | 10.0.1.0/24 | | + * +---------+ +---------+ + * |eth-rt3 eth-rt3| + * | | + * |10.0.3.0/24 | + * | | + * |eth-rt1 | + * +---------+ | + * | |eth-rt2 10.0.2.0/24| + * | RT3 +--------------------------+ + * | 3.3.3.3 | + * | | + * +---------+ + * + * 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 = + { + { + .hostname = "rt1", + .router_id = "1.1.1.1", + .label = 10, + .adjacencies = + { + { + .hostname = "rt2", + .network = + "10.0.1.1/24", + .metric = 10, + .label = 1, + }, + { + .hostname = "rt3", + .network = + "10.0.3.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 = 10, + .label = 4, + }, + }, + }, + { + .hostname = "rt3", + .router_id = "3.3.3.3", + .label = 30, + .adjacencies = + { + { + .hostname = "rt1", + .network = + "10.0.3.2/24", + .metric = 10, + .label = 5, + }, + { + .hostname = "rt2", + .network = + "10.0.2.2/24", + .metric = 10, + .label = 6, + }, + }, + }, + }, +}; + + +/* + * +---------+ +---------+ + * | | | | + * | RT1 |eth-rt2 eth-rt1| RT2 | + * | 1.1.1.1 +---------------------+ 2.2.2.2 | + * | | 10.0.1.0/24 (10) | | + * +---------+ +---------+ + * |eth-rt3 eth-rt3| + * | | + * |10.0.3.0/24 (30) | + * | | + * |eth-rt1 | + * +---------+ | + * | |eth-rt2 10.0.2.0/24|(10) + * | RT3 +--------------------------+ + * | 3.3.3.3 | + * | | + * +---------+ + * + * 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 = + { + { + .hostname = "rt1", + .router_id = "1.1.1.1", + .label = 10, + .adjacencies = + { + { + .hostname = "rt2", + .network = + "10.0.1.1/24", + .metric = 10, + .label = 1, + }, + { + .hostname = "rt3", + .network = + "10.0.3.1/24", + .metric = 30, + .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 = 10, + .label = 4, + }, + }, + }, + { + .hostname = "rt3", + .router_id = "3.3.3.3", + .label = 30, + .adjacencies = + { + { + .hostname = "rt1", + .network = + "10.0.3.2/24", + .metric = 30, + .label = 5, + }, + { + .hostname = "rt2", + .network = + "10.0.2.2/24", + .metric = 10, + .label = 6, + }, + }, + }, + }, +}; + +/* + * +---------+ +---------+ + * | | | | + * | RT1 |eth-rt4 eth-rt1| RT4 | + * | 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 (20) | 3.3.3.3 | + * | | | | + * +---------+ +---------+ + * + * 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 = + { + { + .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 = 20, + .label = 4, + }, + }, + }, + { + .hostname = "rt3", + .router_id = "3.3.3.3", + .label = 30, + .adjacencies = + { + { + .hostname = "rt2", + .network = + "10.0.2.2/24", + .metric = 20, + .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 = "rt1", + .network = + "10.0.4.2/24", + .metric = 10, + .label = 7, + }, + { + .hostname = "rt3", + .network = + "10.0.3.2/24", + .metric = 10, + .label = 8, + }, + }, + }, + }, +}; + +/* + * +---------+ +---------+ + * | | | | + * | RT1 |eth-rt4 eth-rt1| RT4 | + * | 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, + }, + }, + }, + }, +}; + +/* + * +---------+ +---------+ + * | | | | + * | RT1 |eth-rt4 eth-rt1| RT4 | + * | 1.1.1.1 +---------------------+ 4.4.4.4 | + * | | 10.0.4.0/24 | | + * +---------+ +---------+ + * |eth+rt2 eth-rt3| + * | | + * |10.0.1.0/24 | + * | 10.0.3.0/24| + * |eth-rt1 eth-rt4| + * +---------+ +---------+ + * | |eth-rt3 eth-rt2| | + * | RT2 +---------------------+ RT3 | + * | 2.2.2.2 | 10.0.2.0/24 | 3.3.3.3 | + * | | | | + * +---------+ +---------+ + * + * Weights: + * - clockwise: 10 + * - counterclockwise: 40 + * + * This is an example where 3 (!) labels are needed for the protected + * link RT1<->RT2, e.g. the subnet 10.0.1.0/24, to reach RT4. + * + * Because the initial P and Q spaces will not be overlapping or + * adjacent for this case the TI-LFA will be applied recursively. + */ +struct ospf_topology topo5 = { + .nodes = + { + { + .hostname = "rt1", + .router_id = "1.1.1.1", + .label = 10, + .adjacencies = + { + { + .hostname = "rt2", + .network = + "10.0.1.1/24", + .metric = 40, + .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 = 40, + .label = 4, + }, + }, + }, + { + .hostname = "rt3", + .router_id = "3.3.3.3", + .label = 30, + .adjacencies = + { + { + .hostname = "rt2", + .network = + "10.0.2.2/24", + .metric = 10, + .label = 5, + }, + { + .hostname = "rt4", + .network = + "10.0.3.1/24", + .metric = 40, + .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 = 40, + .label = 8, + }, + }, + }, + }, +}; -- cgit v1.2.3