/* $OpenBSD: rde_decide.c,v 1.91 2022/03/22 10:53:08 claudio Exp $ */ /* * Copyright (c) 2003, 2004 Claudio Jeker * Copyright (c) 2003, 2004 Henning Brauer * * Permission to use, copy, modify, and distribute this software for any * purpose with or without fee is hereby granted, provided that the above * copyright notice and this permission notice appear in all copies. * * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */ #include #include #include #include "bgpd.h" #include "rde.h" #include "log.h" int prefix_cmp(struct prefix *, struct prefix *, int *); void prefix_insert(struct prefix *, struct prefix *, struct rib_entry *); void prefix_remove(struct prefix *, struct rib_entry *); /* * Decision Engine RFC implementation: * Phase 1: * - calculate LOCAL_PREF if needed -- EBGP or IGP learnt routes * - IBGP routes may either use LOCAL_PREF or the local system computes * the degree of preference * - If the route is ineligible, the route MAY NOT serve as an input to * the next phase of route selection * - if the route is eligible the computed value MUST be used as the * LOCAL_PREF value in any IBGP readvertisement * * Phase 2: * - If the NEXT_HOP attribute of a BGP route depicts an address that is * not resolvable the BGP route MUST be excluded from the Phase 2 decision * function. * - If the AS_PATH attribute of a BGP route contains an AS loop, the BGP * route should be excluded from the Phase 2 decision function. * - The local BGP speaker identifies the route that has: * a) the highest degree of preference of any route to the same set * of destinations * b) is the only route to that destination * c) is selected as a result of the Phase 2 tie breaking rules * - The local speaker MUST determine the immediate next-hop address from * the NEXT_HOP attribute of the selected route. * - If either the immediate next hop or the IGP cost to the NEXT_HOP changes, * Phase 2 Route Selection MUST be performed again. * * Route Resolvability Condition * - A route Rte1, referencing only the intermediate network address, is * considered resolvable if the Routing Table contains at least one * resolvable route Rte2 that matches Rte1's intermediate network address * and is not recursively resolved through Rte1. * - Routes referencing interfaces are considered resolvable if the state of * the referenced interface is up and IP processing is enabled. * * Breaking Ties (Phase 2) * 1. Remove from consideration all routes which are not tied for having the * smallest number of AS numbers present in their AS_PATH attributes. * Note, that when counting this number, an AS_SET counts as 1 * 2. Remove from consideration all routes which are not tied for having the * lowest Origin number in their Origin attribute. * 3. Remove from consideration routes with less-preferred MULTI_EXIT_DISC * attributes. MULTI_EXIT_DISC is only comparable between routes learned * from the same neighboring AS. * 4. If at least one of the candidate routes was received via EBGP, * remove from consideration all routes which were received via IBGP. * 5. Remove from consideration any routes with less-preferred interior cost. * If the NEXT_HOP hop for a route is reachable, but no cost can be * determined, then this step should be skipped. * 6. Remove from consideration all routes other than the route that was * advertised by the BGP speaker whose BGP Identifier has the lowest value. * 7. Prefer the route received from the lowest peer address. * * Phase 3: Route Dissemination * - All routes in the Loc-RIB are processed into Adj-RIBs-Out according * to configured policy. A route SHALL NOT be installed in the Adj-Rib-Out * unless the destination and NEXT_HOP described by this route may be * forwarded appropriately by the Routing Table. */ /* * Decision Engine OUR implementation: * The filtering is done first. The filtering calculates the preference and * stores it in LOCAL_PREF (Phase 1). * Ineligible routes are flagged as ineligible via nexthop_add(). * Phase 3 is done together with Phase 2. * In following cases a prefix needs to be reevaluated: * - update of a prefix (prefix_update) * - withdraw of a prefix (prefix_withdraw) * - state change of the nexthop (nexthop-{in}validate) * - state change of session (session down) */ /* * Compare two prefixes with equal pt_entry. Returns an integer greater than or * less than 0, according to whether the prefix p1 is more or less preferred * than the prefix p2. p1 should be used for the new prefix and p2 for a * already added prefix. */ int prefix_cmp(struct prefix *p1, struct prefix *p2, int *testall) { struct rde_aspath *asp1, *asp2; struct rde_peer *peer1, *peer2; struct attr *a; uint32_t p1id, p2id; int p1cnt, p2cnt, i; /* * If a match happens before the MED check then the list is * correctly sorted. If a match happens after MED then further * elements may need to be checked to ensure that all paths * which could affect this path were considered. This only * matters for strict MED evaluation and in that case testall * is set to 1. If the check happens to be on the MED check * itself testall is set to 2. */ *testall = 0; if (p1 == NULL) return -1; if (p2 == NULL) return 1; asp1 = prefix_aspath(p1); asp2 = prefix_aspath(p2); peer1 = prefix_peer(p1); peer2 = prefix_peer(p2); /* pathes with errors are not eligible */ if (asp1 == NULL || asp1->flags & F_ATTR_PARSE_ERR) return -1; if (asp2 == NULL || asp2->flags & F_ATTR_PARSE_ERR) return 1; /* only loop free pathes are eligible */ if (asp1->flags & F_ATTR_LOOP) return -1; if (asp2->flags & F_ATTR_LOOP) return 1; /* * 1. check if prefix is eligible a.k.a reachable * A NULL nexthop is eligible since it is used for locally * announced networks. */ if (prefix_nexthop(p2) != NULL && prefix_nexthop(p2)->state != NEXTHOP_REACH) return 1; if (prefix_nexthop(p1) != NULL && prefix_nexthop(p1)->state != NEXTHOP_REACH) return -1; /* 2. local preference of prefix, bigger is better */ if (asp1->lpref > asp2->lpref) return 1; if (asp1->lpref < asp2->lpref) return -1; /* 3. aspath count, the shorter the better */ if ((asp2->aspath->ascnt - asp1->aspath->ascnt) != 0) return (asp2->aspath->ascnt - asp1->aspath->ascnt); /* 4. origin, the lower the better */ if ((asp2->origin - asp1->origin) != 0) return (asp2->origin - asp1->origin); /* * 5. MED decision * Only comparable between the same neighboring AS or if * 'rde med compare always' is set. In the first case * set the testall flag since further elements need to be * evaluated as well. */ if ((rde_decisionflags() & BGPD_FLAG_DECISION_MED_ALWAYS) || aspath_neighbor(asp1->aspath) == aspath_neighbor(asp2->aspath)) { if (!(rde_decisionflags() & BGPD_FLAG_DECISION_MED_ALWAYS)) *testall = 2; /* lowest value wins */ if (asp1->med < asp2->med) return 1; if (asp1->med > asp2->med) return -1; } if (!(rde_decisionflags() & BGPD_FLAG_DECISION_MED_ALWAYS)) *testall = 1; /* * 6. EBGP is cooler than IBGP * It is absolutely important that the ebgp value in peer_config.ebgp * is bigger than all other ones (IBGP, confederations) */ if (peer1->conf.ebgp != peer2->conf.ebgp) { if (peer1->conf.ebgp) /* peer1 is EBGP other is lower */ return 1; else if (peer2->conf.ebgp) /* peer2 is EBGP */ return -1; } /* * 7. local tie-breaker, this weight is here to tip equal long AS * paths in one or the other direction. It happens more and more * that AS paths are equally long and so traffic engineering needs * a metric that weights a prefix at a very late stage in the * decision process. */ if (asp1->weight > asp2->weight) return 1; if (asp1->weight < asp2->weight) return -1; /* 8. nexthop costs. NOT YET -> IGNORE */ /* * 9. older route (more stable) wins but only if route-age * evaluation is enabled. */ if (rde_decisionflags() & BGPD_FLAG_DECISION_ROUTEAGE) { if (p1->lastchange < p2->lastchange) /* p1 is older */ return 1; if (p1->lastchange > p2->lastchange) return -1; } /* 10. lowest BGP Id wins, use ORIGINATOR_ID if present */ if ((a = attr_optget(asp1, ATTR_ORIGINATOR_ID)) != NULL) { memcpy(&p1id, a->data, sizeof(p1id)); p1id = ntohl(p1id); } else p1id = peer1->remote_bgpid; if ((a = attr_optget(asp2, ATTR_ORIGINATOR_ID)) != NULL) { memcpy(&p2id, a->data, sizeof(p2id)); p2id = ntohl(p2id); } else p2id = peer2->remote_bgpid; if (p1id < p2id) return 1; if (p1id > p2id) return -1; /* 11. compare CLUSTER_LIST length, shorter is better */ p1cnt = p2cnt = 0; if ((a = attr_optget(asp1, ATTR_CLUSTER_LIST)) != NULL) p1cnt = a->len / sizeof(uint32_t); if ((a = attr_optget(asp2, ATTR_CLUSTER_LIST)) != NULL) p2cnt = a->len / sizeof(uint32_t); if ((p2cnt - p1cnt) != 0) return (p2cnt - p1cnt); /* 12. lowest peer address wins (IPv4 is better than IPv6) */ if (peer1->remote_addr.aid < peer2->remote_addr.aid) return 1; if (peer1->remote_addr.aid > peer2->remote_addr.aid) return -1; switch (peer1->remote_addr.aid) { case AID_INET: i = memcmp(&peer1->remote_addr.v4, &peer2->remote_addr.v4, sizeof(struct in_addr)); break; case AID_INET6: i = memcmp(&peer1->remote_addr.v6, &peer2->remote_addr.v6, sizeof(struct in6_addr)); break; default: fatalx("%s: unknown af", __func__); } if (i < 0) return 1; if (i > 0) return -1; /* RFC7911 does not specify this but something like this is needed. */ /* 13. lowest path identifier wins */ if (p1->path_id < p2->path_id) return 1; if (p1->path_id > p2->path_id) return -1; fatalx("Uh, oh a politician in the decision process"); } /* * Insert a prefix keeping the total order of the list. For routes * that may depend on a MED selection the set is scanned until the * condition is cleared. If a MED inversion is detected the respective * prefix is taken of the rib list and put onto a redo queue. All * prefixes on the redo queue are re-inserted at the end. */ void prefix_insert(struct prefix *new, struct prefix *ep, struct rib_entry *re) { struct prefix_queue redo = TAILQ_HEAD_INITIALIZER(redo); struct prefix *xp, *np, *insertp = ep; int testall, selected = 0; /* start scan at the entry point (ep) or the head if ep == NULL */ if (ep == NULL) ep = TAILQ_FIRST(&re->prefix_h); for (xp = ep; xp != NULL; xp = np) { np = TAILQ_NEXT(xp, entry.list.rib); if (prefix_cmp(new, xp, &testall) > 0) { /* new is preferred over xp */ if (testall == 0) break; /* we're done */ else if (testall == 2) { /* * MED inversion, take out prefix and * put it onto redo queue. */ TAILQ_REMOVE(&re->prefix_h, xp, entry.list.rib); TAILQ_INSERT_TAIL(&redo, xp, entry.list.rib); } else { /* * lock insertion point and * continue on with scan */ selected = 1; continue; } } else { /* * xp is preferred over new. * Remember insertion point for later unless the * traverse is just looking for a possible MED * inversion (selected == 1). * If the last comparison's tie-breaker was the MED * check reset selected and with it insertp since * this was an actual MED priority inversion. */ if (testall == 2) selected = 0; if (!selected) insertp = xp; } } if (insertp == NULL) TAILQ_INSERT_HEAD(&re->prefix_h, new, entry.list.rib); else TAILQ_INSERT_AFTER(&re->prefix_h, insertp, new, entry.list.rib); /* Fixup MED order again. All elements are < new */ while (!TAILQ_EMPTY(&redo)) { xp = TAILQ_FIRST(&redo); TAILQ_REMOVE(&redo, xp, entry.list.rib); prefix_insert(xp, new, re); } } /* * Remove a prefix from the RIB list ensuring that the total order of the * list remains intact. All routes that differ in the MED are taken of the * list and put on the redo list. To figure out if a route could cause a * resort because of a MED check the next prefix of the to-remove prefix * is compared with the old prefix. A full scan is only done if the next * route differs because of the MED or later checks. * Again at the end all routes on the redo queue are reinserted. */ void prefix_remove(struct prefix *old, struct rib_entry *re) { struct prefix_queue redo = TAILQ_HEAD_INITIALIZER(redo); struct prefix *xp, *np; int testall; xp = TAILQ_NEXT(old, entry.list.rib); TAILQ_REMOVE(&re->prefix_h, old, entry.list.rib); /* check if a MED inversion could be possible */ prefix_cmp(old, xp, &testall); if (testall > 0) { /* maybe MED route, scan tail for other possible routes */ for (; xp != NULL; xp = np) { np = TAILQ_NEXT(xp, entry.list.rib); /* only interested in the testall result */ prefix_cmp(old, xp, &testall); if (testall == 0) break; /* we're done */ else if (testall == 2) { /* * possible MED inversion, take out prefix and * put it onto redo queue. */ TAILQ_REMOVE(&re->prefix_h, xp, entry.list.rib); TAILQ_INSERT_TAIL(&redo, xp, entry.list.rib); } } } /* Fixup MED order again, reinsert prefixes from the start */ while (!TAILQ_EMPTY(&redo)) { xp = TAILQ_FIRST(&redo); TAILQ_REMOVE(&redo, xp, entry.list.rib); prefix_insert(xp, NULL, re); } } /* helper function to check if a prefix is valid to be selected */ int prefix_eligible(struct prefix *p) { struct rde_aspath *asp = prefix_aspath(p); struct nexthop *nh = prefix_nexthop(p); /* The aspath needs to be loop and error free */ if (asp == NULL || asp->flags & (F_ATTR_LOOP|F_ATTR_PARSE_ERR)) return 0; /* * If the nexthop exists it must be reachable. * It is OK if the nexthop does not exist (local announcement). */ if (nh != NULL && nh->state != NEXTHOP_REACH) return 0; return 1; } struct prefix * prefix_best(struct rib_entry *re) { struct prefix *xp; struct rib *rib; rib = re_rib(re); if (rib->flags & F_RIB_NOEVALUATE) /* decision process is turned off */ return NULL; xp = TAILQ_FIRST(&re->prefix_h); if (xp != NULL && !prefix_eligible(xp)) xp = NULL; return xp; } /* * Find the correct place to insert the prefix in the prefix list. * If the active prefix has changed we need to send an update also special * treatment is needed if 'rde evaluate all' is used on some peers. * To re-evaluate a prefix just call prefix_evaluate with old and new pointing * to the same prefix. */ void prefix_evaluate(struct rib_entry *re, struct prefix *new, struct prefix *old) { struct prefix *xp, *active; struct rib *rib; rib = re_rib(re); if (rib->flags & F_RIB_NOEVALUATE) { /* decision process is turned off */ if (old != NULL) TAILQ_REMOVE(&re->prefix_h, old, entry.list.rib); if (new != NULL) TAILQ_INSERT_HEAD(&re->prefix_h, new, entry.list.rib); return; } active = prefix_best(re); if (old != NULL) prefix_remove(old, re); if (new != NULL) prefix_insert(new, NULL, re); xp = TAILQ_FIRST(&re->prefix_h); if (xp != NULL && !prefix_eligible(xp)) xp = NULL; /* * If the active prefix changed or the active prefix was removed * and added again then generate an update. */ if (active != xp || (old != NULL && xp == old)) { /* * Send update withdrawing re->active and adding xp * but remember that xp may be NULL aka ineligible. * Additional decision may be made by the called functions. */ rde_generate_updates(rib, xp, active, 0); if ((rib->flags & F_RIB_NOFIB) == 0) rde_send_kroute(rib, xp, active); return; } /* * If there are peers with 'rde evaluate all' every update needs * to be passed on (not only a change of the best prefix). * rde_generate_updates() will then take care of distribution. */ if (rde_evaluate_all()) if ((new != NULL && prefix_eligible(new)) || old != NULL) rde_generate_updates(rib, prefix_best(re), NULL, 1); }