ldpd: adding support for LDP ordered label distribution control

LDP ordered label distribution control only binds a label to
a FEC if it is the egress LSR, or the router received a label
binding for a FEC from the next hop router.  In this mode,
an MPLS router will create a label binding for each FEC and
distribute it to its neighbors so long as he has a entry in
the RIB for the destination.

Signed-off-by: Lynne Morrison <lynne@voltanet.io>
Signed-off-by: Karen Schoener <karen@voltanet.io>

9 files changed, 212 insertions, 13 deletions

diff --git a/doc/user/ldpd.rst b/doc/user/ldpd.rst
index 977195d6a..2df4ba300 100644
--- a/doc/user/ldpd.rst
+++ b/doc/user/ldpd.rst
@@ -108,6 +108,11 @@ LDP Configuration
    The following command located under MPLS router node configures the MPLS
    router-id of the local device.
 
+.. index:: [no] ordered-control
+.. clicmd:: [no] ordered-control
+
+   Configure LDP Ordered Label Distribution Control.
+
 .. index:: [no] address-family [ipv4 | ipv6]
 .. clicmd:: [no] address-family [ipv4 | ipv6]
 
diff --git a/ldpd/lde.c b/ldpd/lde.c
index 006d27f6a..8a7c4bc7c 100644
--- a/ldpd/lde.c
+++ b/ldpd/lde.c
@@ -61,6 +61,8 @@ static void		 lde_label_list_init(void);
 static int		 lde_get_label_chunk(void);
 static void		 on_get_label_chunk_response(uint32_t start, uint32_t end);
 static uint32_t		 lde_get_next_label(void);
+static bool		 lde_fec_connected(const struct fec_node *);
+static bool		 lde_fec_outside_mpls_network(const struct fec_node *);
 
 RB_GENERATE(nbr_tree, lde_nbr, entry, lde_nbr_compare)
 RB_GENERATE(lde_map_head, lde_map, entry, lde_map_compare)
@@ -661,18 +663,31 @@ lde_acl_check(char *acl_name, int af, union ldpd_addr *addr, uint8_t prefixlen)
 	return ldp_acl_request(iev_main_sync, acl_name, af, addr, prefixlen);
 }
 
+static bool lde_fec_connected(const struct fec_node *fn)
+{
+	struct fec_nh *fnh;
+
+	LIST_FOREACH(fnh, &fn->nexthops, entry)
+		if (fnh->flags & F_FEC_NH_CONNECTED)
+			return true;
+
+	return false;
+}
+
+static bool lde_fec_outside_mpls_network(const struct fec_node *fn)
+{
+	struct fec_nh *fnh;
+
+	LIST_FOREACH(fnh, &fn->nexthops, entry)
+		if (!(fnh->flags & F_FEC_NH_NO_LDP))
+			return false;
+
+	return true;
+}
+
 uint32_t
 lde_update_label(struct fec_node *fn)
 {
-	struct fec_nh	*fnh;
-	int		 connected = 0;
-
-	LIST_FOREACH(fnh, &fn->nexthops, entry) {
-		if (fnh->flags & F_FEC_NH_CONNECTED) {
-			connected = 1;
-			break;
-		}
-	}
 
 	/* should we allocate a label for this fec? */
 	switch (fn->fec.type) {
@@ -698,7 +713,14 @@ lde_update_label(struct fec_node *fn)
 		break;
 	}
 
-	if (connected) {
+	/*
+	 * If connected interface act as egress for fec.
+	 * If LDP is not configured on an interface but there
+	 * are other NHs with interfaces configured with LDP
+	 * then don't act as an egress for the fec, otherwise
+	 * act as an egress for the fec
+	 */
+	if (lde_fec_connected(fn) || lde_fec_outside_mpls_network(fn)) {
 		/* choose implicit or explicit-null depending on configuration */
 		switch (fn->fec.type) {
 		case FEC_TYPE_IPV4:
@@ -738,6 +760,13 @@ lde_send_change_klabel(struct fec_node *fn, struct fec_nh *fnh)
 	struct zapi_pw	 zpw;
 	struct l2vpn_pw	*pw;
 
+	/*
+	 * Ordered Control: don't program label into HW until a
+	 * labelmap msg has been received from upstream router
+	 */
+	if (fnh->flags & F_FEC_NH_DEFER)
+		return;
+
 	switch (fn->fec.type) {
 	case FEC_TYPE_IPV4:
 		memset(&kr, 0, sizeof(kr));
@@ -904,6 +933,27 @@ lde_send_labelmapping(struct lde_nbr *ln, struct fec_node *fn, int single)
 	struct lde_req		*lre;
 	struct map		 map;
 	struct l2vpn_pw		*pw;
+	struct fec_nh		*fnh;
+	bool			 allow = false;
+
+	/*
+	 * Ordered Control: do not send a labelmap msg until
+	 * a labelmap message is received from downstream router
+	 * and don't send labelmap back to downstream router
+	 */
+	if (ldeconf->flags & F_LDPD_ORDERED_CONTROL) {
+		LIST_FOREACH(fnh, &fn->nexthops, entry) {
+			if (fnh->flags & F_FEC_NH_DEFER)
+				continue;
+
+			if (lde_address_find(ln, fnh->af, &fnh->nexthop))
+				return;
+			allow = true;
+			break;
+		}
+		if (!allow)
+			return;
+	}
 
 	/*
 	 * We shouldn't send a new label mapping if we have a pending
@@ -1244,6 +1294,7 @@ lde_nbr_del(struct lde_nbr *ln)
 	struct fec_node		*fn;
 	struct fec_nh		*fnh;
 	struct l2vpn_pw		*pw;
+	struct lde_nbr		*lnbr;
 
 	if (ln == NULL)
 		return;
@@ -1259,6 +1310,25 @@ lde_nbr_del(struct lde_nbr *ln)
 				if (!lde_address_find(ln, fnh->af,
 				    &fnh->nexthop))
 					continue;
+
+				/*
+				 * Ordered Control: must mark any non-connected
+				 * NH to wait until we receive a labelmap msg
+				 * before installing in kernel and sending to
+				 * peer, must do this as NHs are not removed
+				 * when lsps go down.  Also send label withdraw
+				 * to other neighbors for all fecs from neighbor
+				 * going down
+				 */
+				if (ldeconf->flags & F_LDPD_ORDERED_CONTROL) {
+					fnh->flags |= F_FEC_NH_DEFER;
+
+					RB_FOREACH(lnbr, nbr_tree, &lde_nbrs) {
+						if (ln->peerid == lnbr->peerid)
+							continue;
+						lde_send_labelwithdraw(lnbr, fn, NULL, NULL);
+					}
+				}
 				break;
 			case FEC_TYPE_PWID:
 				if (f->u.pwid.lsr_id.s_addr != ln->id.s_addr)
diff --git a/ldpd/lde.h b/ldpd/lde.h
index ce466c16b..a099f8d28 100644
--- a/ldpd/lde.h
+++ b/ldpd/lde.h
@@ -114,6 +114,8 @@ struct fec_nh {
 };
 #define F_FEC_NH_NEW		0x01
 #define F_FEC_NH_CONNECTED	0x02
+#define F_FEC_NH_DEFER		0x04		/* running ordered control */
+#define F_FEC_NH_NO_LDP		0x08		/* no ldp on this interface */
 
 struct fec_node {
 	struct fec		 fec;
diff --git a/ldpd/lde_lib.c b/ldpd/lde_lib.c
index eb1a6d943..8f524e0aa 100644
--- a/ldpd/lde_lib.c
+++ b/ldpd/lde_lib.c
@@ -20,6 +20,7 @@
 #include <zebra.h>
 
 #include "ldpd.h"
+#include "ldpe.h"
 #include "lde.h"
 #include "log.h"
 
@@ -325,6 +326,7 @@ lde_kernel_insert(struct fec *fec, int af, union ldpd_addr *nexthop,
 {
 	struct fec_node		*fn;
 	struct fec_nh		*fnh;
+	struct iface		*iface;
 
 	fn = (struct fec_node *)fec_find(&ft, fec);
 	if (fn == NULL)
@@ -333,9 +335,21 @@ lde_kernel_insert(struct fec *fec, int af, union ldpd_addr *nexthop,
 		fn->data = data;
 
 	fnh = fec_nh_find(fn, af, nexthop, ifindex, route_type, route_instance);
-	if (fnh == NULL)
+	if (fnh == NULL) {
 		fnh = fec_nh_add(fn, af, nexthop, ifindex, route_type,
 		    route_instance);
+		/*
+		 * Ordered Control: if not a connected route and not a route
+		 * learned over an interface not running LDP and not a PW
+		 * then mark to wait until we receive labelmap msg before
+		 * installing in kernel and sending to peer
+		 */
+		iface = if_lookup(ldeconf, ifindex);
+		if ((ldeconf->flags & F_LDPD_ORDERED_CONTROL) &&
+		    !connected && iface != NULL && fec->type != FEC_TYPE_PWID)
+			fnh->flags |= F_FEC_NH_DEFER;
+	}
+
 	fnh->flags |= F_FEC_NH_NEW;
 	if (connected)
 		fnh->flags |= F_FEC_NH_CONNECTED;
@@ -374,15 +388,25 @@ lde_kernel_update(struct fec *fec)
 	struct fec_nh		*fnh, *safe;
 	struct lde_nbr		*ln;
 	struct lde_map		*me;
+	struct iface		*iface;
 
 	fn = (struct fec_node *)fec_find(&ft, fec);
 	if (fn == NULL)
 		return;
 
 	LIST_FOREACH_SAFE(fnh, &fn->nexthops, entry, safe) {
-		if (fnh->flags & F_FEC_NH_NEW)
+		if (fnh->flags & F_FEC_NH_NEW) {
 			fnh->flags &= ~F_FEC_NH_NEW;
-		else {
+			/*
+			 * if LDP configured on interface or a static route
+			 * clear flag else treat fec as a connected route
+			 */
+			iface = if_lookup(ldeconf,fnh->ifindex);
+			if (iface || fnh->route_type == ZEBRA_ROUTE_STATIC)
+				fnh->flags &=~F_FEC_NH_NO_LDP;
+			else
+				fnh->flags |= F_FEC_NH_NO_LDP;
+		} else {
 			lde_send_delete_klabel(fn, fnh);
 			fec_nh_del(fnh);
 		}
@@ -445,6 +469,7 @@ lde_check_mapping(struct map *map, struct lde_nbr *ln)
 	struct lde_req		*lre;
 	struct lde_map		*me;
 	struct l2vpn_pw		*pw;
+	bool			 send_map = false;
 
 	lde_map2fec(map, ln->id, &fec);
 
@@ -525,6 +550,15 @@ lde_check_mapping(struct map *map, struct lde_nbr *ln)
 			if (!lde_address_find(ln, fnh->af, &fnh->nexthop))
 				continue;
 
+			/*
+			 * Ordered Control: labelmap msg received from
+			 * NH so clear flag and send labelmap msg to
+			 * peer
+			 */
+			if (ldeconf->flags & F_LDPD_ORDERED_CONTROL) {
+				send_map = true;
+				fnh->flags &= ~F_FEC_NH_DEFER;
+			}
 			fnh->remote_label = map->label;
 			lde_send_change_klabel(fn, fnh);
 			break;
@@ -558,6 +592,15 @@ lde_check_mapping(struct map *map, struct lde_nbr *ln)
 	 * loop detection. LMp.28 - LMp.30 are unnecessary because we are
 	 * merging capable.
 	 */
+
+	/*
+	 * Ordered Control: just received a labelmap for this fec from NH so
+	 * need to send labelmap to all peers
+	 * LMp.20 - LMp21 Execute procedure to send Label Mapping
+	 */
+	if (send_map && fn->local_label != NO_LABEL)
+		RB_FOREACH(ln, nbr_tree, &lde_nbrs)
+			lde_send_labelmapping(ln, fn, 1);
 }
 
 void
@@ -757,6 +800,7 @@ lde_check_withdraw(struct map *map, struct lde_nbr *ln)
 	struct fec_nh		*fnh;
 	struct lde_map		*me;
 	struct l2vpn_pw		*pw;
+	struct lde_nbr		*lnbr;
 
 	/* wildcard label withdraw */
 	if (map->type == MAP_TYPE_WILDCARD ||
@@ -803,6 +847,26 @@ lde_check_withdraw(struct map *map, struct lde_nbr *ln)
 	if (me && (map->label == NO_LABEL || map->label == me->map.label))
 		/* LWd.4: remove record of previously received lbl mapping */
 		lde_map_del(ln, me, 0);
+
+	/* Ordered Control: additional withdraw steps */
+	if (ldeconf->flags & F_LDPD_ORDERED_CONTROL) {
+		/* LWd.8: for each neighbor other that src of withdraw msg */
+		RB_FOREACH(lnbr, nbr_tree, &lde_nbrs) {
+			if (ln->peerid == lnbr->peerid)
+				continue;
+
+			/* LWd.9: check if previously sent a label mapping */
+			me = (struct lde_map *)fec_find(&lnbr->sent_map,
+			    &fn->fec);
+			/*
+			 * LWd.10: does label sent to peer "map" to withdraw
+			 * label
+			 */
+			if (me)
+				/* LWd.11: send label withdraw */
+				lde_send_labelwithdraw(lnbr, fn, NULL, NULL);
+		}
+	}
 }
 
 void
@@ -813,6 +877,7 @@ lde_check_withdraw_wcard(struct map *map, struct lde_nbr *ln)
 	struct fec_nh	*fnh;
 	struct lde_map	*me;
 	struct l2vpn_pw	*pw;
+	struct lde_nbr  *lnbr;
 
 	/* LWd.2: send label release */
 	lde_send_labelrelease(ln, NULL, map, map->label);
@@ -859,6 +924,26 @@ lde_check_withdraw_wcard(struct map *map, struct lde_nbr *ln)
 			 * label mapping
 			 */
 			lde_map_del(ln, me, 0);
+
+		/* Ordered Control: additional withdraw steps */
+		if (ldeconf->flags & F_LDPD_ORDERED_CONTROL) {
+			/* LWd.8: for each neighbor other that src of withdraw msg */
+			RB_FOREACH(lnbr, nbr_tree, &lde_nbrs) {
+				if (ln->peerid == lnbr->peerid)
+					continue;
+
+				/* LWd.9: check if previously sent a label mapping */
+				me = (struct lde_map *)fec_find(&lnbr->sent_map,
+					&fn->fec);
+				/*
+				 * LWd.10: does label sent to peer "map" to withdraw
+				 * label
+				 */
+				if (me)
+					/* LWd.11: send label withdraw */
+					lde_send_labelwithdraw(lnbr, fn, NULL, NULL);
+			}
+		}
 	}
 }
 
diff --git a/ldpd/ldp_vty.h b/ldpd/ldp_vty.h
index 5e9df4aaf..af5f1d561 100644
--- a/ldpd/ldp_vty.h
+++ b/ldpd/ldp_vty.h
@@ -52,6 +52,7 @@ int	 ldp_vty_label_expnull(struct vty *, const char *, const char *);
 int	 ldp_vty_label_accept(struct vty *, const char *, const char *, const char *);
 int	 ldp_vty_ttl_security(struct vty *, const char *);
 int	 ldp_vty_router_id(struct vty *, const char *, struct in_addr);
+int	 ldp_vty_ordered_control(struct vty *, const char *);
 int	 ldp_vty_ds_cisco_interop(struct vty *, const char *);
 int	 ldp_vty_trans_pref_ipv4(struct vty *, const char *);
 int	 ldp_vty_neighbor_password(struct vty *, const char *, struct in_addr, const char *);
diff --git a/ldpd/ldp_vty_cmds.c b/ldpd/ldp_vty_cmds.c
index c24e1917c..c10c6ae35 100644
--- a/ldpd/ldp_vty_cmds.c
+++ b/ldpd/ldp_vty_cmds.c
@@ -221,6 +221,15 @@ DEFPY  (ldp_router_id,
 	return (ldp_vty_router_id(vty, no, address));
 }
 
+DEFPY  (ldp_ordered_control,
+        ldp_ordered_control_cmd,
+        "[no] ordered-control",
+        NO_STR
+        "Configure LDP ordered label distribution control mode\n")
+{
+	return (ldp_vty_ordered_control(vty, no));
+}
+
 DEFPY  (ldp_discovery_targeted_hello_accept,
 	ldp_discovery_targeted_hello_accept_cmd,
 	"[no] discovery targeted-hello accept [from <(1-199)|(1300-2699)|WORD>$from_acl]",
@@ -807,6 +816,7 @@ ldp_vty_init (void)
 	install_element(LDP_NODE, &ldp_neighbor_session_holdtime_cmd);
 	install_element(LDP_NODE, &ldp_neighbor_ttl_security_cmd);
 	install_element(LDP_NODE, &ldp_router_id_cmd);
+	install_element(LDP_NODE, &ldp_ordered_control_cmd);
 
 	install_element(LDP_IPV4_NODE, &ldp_discovery_link_holdtime_cmd);
 	install_element(LDP_IPV4_NODE, &ldp_discovery_targeted_holdtime_cmd);
diff --git a/ldpd/ldp_vty_conf.c b/ldpd/ldp_vty_conf.c
index 816fcc64b..05b896256 100644
--- a/ldpd/ldp_vty_conf.c
+++ b/ldpd/ldp_vty_conf.c
@@ -278,6 +278,9 @@ ldp_config_write(struct vty *vty)
 	if (ldpd_conf->flags & F_LDPD_DS_CISCO_INTEROP)
 		vty_out (vty, " dual-stack cisco-interop\n");
 
+	if (ldpd_conf->flags & F_LDPD_ORDERED_CONTROL)
+		vty_out (vty, " ordered-control\n");
+
 	RB_FOREACH(nbrp, nbrp_head, &ldpd_conf->nbrp_tree) {
 		if (nbrp->flags & F_NBRP_KEEPALIVE)
 			vty_out (vty, " neighbor %s session holdtime %u\n",
@@ -997,6 +1000,19 @@ ldp_vty_router_id(struct vty *vty, const char *negate, struct in_addr address)
 }
 
 int
+ldp_vty_ordered_control(struct vty *vty, const char *negate)
+{
+	if (negate)
+		vty_conf->flags &= ~F_LDPD_ORDERED_CONTROL;
+	else
+		vty_conf->flags |= F_LDPD_ORDERED_CONTROL;
+
+	ldp_config_apply(vty, vty_conf);
+
+	return (CMD_SUCCESS);
+}
+
+int
 ldp_vty_ds_cisco_interop(struct vty *vty, const char * negate)
 {
 	if (negate)
diff --git a/ldpd/ldpd.c b/ldpd/ldpd.c
index dcbcf8ce5..9afd92d07 100644
--- a/ldpd/ldpd.c
+++ b/ldpd/ldpd.c
@@ -1284,6 +1284,14 @@ merge_global(struct ldpd_conf *conf, struct ldpd_conf *xconf)
 		conf->rtr_id = xconf->rtr_id;
 	}
 
+	/*
+	 * Configuration of ordered-control or independent-control
+	 * requires resetting all neighborships.
+	 */
+	if ((conf->flags & F_LDPD_ORDERED_CONTROL) !=
+	    (xconf->flags & F_LDPD_ORDERED_CONTROL))
+		ldpe_reset_nbrs(AF_UNSPEC);
+
 	conf->lhello_holdtime = xconf->lhello_holdtime;
 	conf->lhello_interval = xconf->lhello_interval;
 	conf->thello_holdtime = xconf->thello_holdtime;
diff --git a/ldpd/ldpd.h b/ldpd/ldpd.h
index bd7562e5a..28590e9bb 100644
--- a/ldpd/ldpd.h
+++ b/ldpd/ldpd.h
@@ -511,6 +511,8 @@ DECLARE_QOBJ_TYPE(ldpd_conf)
 #define	F_LDPD_NO_FIB_UPDATE	0x0001
 #define	F_LDPD_DS_CISCO_INTEROP	0x0002
 #define	F_LDPD_ENABLED		0x0004
+#define	F_LDPD_ORDERED_CONTROL  0x0008
+
 
 struct ldpd_af_global {
 	struct thread		*disc_ev;