bgpd: Re-use TX Addpath IDs where possible

The motivation for this patch is to address a concerning behavior of
tx-addpath-bestpath-per-AS. Prior to this patch, all paths' TX ID was
pre-determined as the path was received from a peer. However, this meant
that any time the path selected as best from an AS changed, bgpd had no
choice but to withdraw the previous best path, and advertise the new
best-path under a new TX ID. This could cause significant network
disruption, especially for the subset of prefixes coming from only one
AS that were also communicated over a bestpath-per-AS session.

The patch's general approach is best illustrated by
txaddpath_update_ids. After a bestpath run (required for best-per-AS to
know what will and will not be sent as addpaths) ID numbers will be
stripped from paths that no longer need to be sent, and held in a pool.
Then, paths that will be sent as addpaths and do not already have ID
numbers will allocate new ID numbers, pulling first from that pool.
Finally, anything left in the pool will be returned to the allocator.

In order for this to work, ID numbers had to be split by strategy. The
tx-addpath-All strategy would keep every ID number "in use" constantly,
preventing IDs from being transferred to different paths. Rather than
create two variables for ID, this patch create a more generic array that
will easily enable more addpath strategies to be implemented. The
previously described ID manipulations will happen per addpath strategy,
and will only be run for strategies that are enabled on at least one
peer.

Finally, the ID numbers are allocated from an allocator that tracks per
AFI/SAFI/Addpath Strategy which IDs are in use. Though it would be very
improbable, there was the possibility with the free-running counter
approach for rollover to cause two paths on the same prefix to get
assigned the same TX ID. As remote as the possibility is, we prefer to
not leave it to chance.

This ID re-use method is not perfect. In some cases you could still get
withdraw-then-add behaviors where not strictly necessary. In the case of
bestpath-per-AS this requires one AS to advertise a prefix for the first
time, then a second AS withdraws that prefix, all within the space of an
already pending MRAI timer. In those situations a withdraw-then-add is
more forgivable, and fixing it would probably require a much more
significant effort, as IDs would need to be moved to ADVs instead of
paths.

Signed-off-by Mitchell Skiba <mskiba@amazon.com>

1 files changed, 72 insertions, 0 deletions

diff --git a/bgpd/bgp_addpath.h b/bgpd/bgp_addpath.h
new file mode 100644
index 000000000..c0c182791
--- /dev/null
+++ b/bgpd/bgp_addpath.h
@@ -0,0 +1,72 @@
+/*
+ * Addpath TX ID selection, and related utilities
+ * Copyright (C) 2018  Amazon.com, Inc. or its affiliates
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by the Free
+ * Software Foundation; either version 2 of the License, or (at your option)
+ * any later version.
+ *
+ * This program is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
+ * more details.
+ *
+ * You should have received a copy of the GNU General Public License along
+ * with this program; see the file COPYING; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#ifndef _QUAGGA_BGPD_TX_ADDPATH_H
+#define _QUAGGA_BGPD_TX_ADDPATH_H
+
+#include <stdint.h>
+#include <zebra.h>
+
+#include "bgpd/bgp_addpath_types.h"
+#include "bgpd/bgp_route.h"
+#include "bgpd/bgp_table.h"
+#include "lib/json.h"
+
+#define BGP_ADDPATH_TX_ID_FOR_DEFAULT_ORIGINATE 1
+
+void bgp_addpath_init_bgp_data(struct bgp_addpath_bgp_data *d);
+
+int bgp_addpath_is_addpath_used(struct bgp_addpath_bgp_data *d, afi_t afi,
+			      safi_t safi);
+
+void bgp_addpath_free_node_data(struct bgp_addpath_bgp_data *bd,
+			      struct bgp_addpath_node_data *nd,
+			      afi_t afi, safi_t safi);
+
+void bgp_addpath_free_info_data(struct bgp_addpath_info_data *d,
+			      struct bgp_addpath_node_data *nd);
+
+
+int bgp_addpath_info_has_ids(struct bgp_addpath_info_data *d);
+
+uint32_t bgp_addpath_id_for_peer(struct peer *peer, afi_t afi, safi_t safi,
+				struct bgp_addpath_info_data *d);
+
+struct bgp_addpath_strategy_names *
+bgp_addpath_names(enum bgp_addpath_strat strat);
+
+int bgp_addpath_dmed_required(int strategy);
+
+/*
+ * Return true if this is a path we should advertise due to a configured
+ * addpath-tx knob
+ */
+int bgp_addpath_tx_path(enum bgp_addpath_strat strat,
+			    struct bgp_path_info *pi);
+/*
+ * Change the type of addpath used for a peer.
+ */
+void bgp_addpath_set_peer_type(struct peer *peer, afi_t afi, safi_t safi,
+			      enum bgp_addpath_strat addpath_type);
+
+void bgp_addpath_update_ids(struct bgp *bgp, struct bgp_node *bn, afi_t afi,
+			    safi_t safi);
+
+void bgp_addpath_type_changed(struct bgp *bgp);
+#endif