/*	$OpenBSD: rde_decide.c,v 1.62 2012/07/04 20:43:26 claudio Exp $ */

/*

 * Copyright (c) 2003, 2004 Claudio Jeker <claudio@openbsd.org>

 * Copyright (c) 2003, 2004 Henning Brauer <henning@openbsd.org>

 *

 * 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 <sys/types.h>

#include <sys/queue.h>

#include <string.h>

#include "bgpd.h"

#include "rde.h"

int	prefix_cmp(struct prefix *, struct prefix *);

/*

 * 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:

 * Our implementation has only one RIB. 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 (path_update)

 *  - withdraw of a prefix (prefix_remove)

 *  - 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)

{

	struct rde_aspath	*asp1, *asp2;

	struct attr		*a;

	u_int32_t		 p1id, p2id;

	int			 p1cnt, p2cnt;

	/* pathes with errors are not eligible */

	/* only loop free pathes are eligible */

	/* 1. check if prefix is eligible a.k.a reachable */

	/* 2. local preference of prefix, bigger is better */

	/* 3. aspath count, the shorter the better */

	/* 4. origin, the lower the better */

	/* 5. MED decision, only comparable between the same neighboring AS */

	    aspath_neighbor(asp1->aspath) == aspath_neighbor(asp2->aspath))

		/* lowest value wins */

	/*

	 * 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)

	 */

	}

	/*

	 * 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.

	 */

	/* 8. nexthop costs. NOT YET -> IGNORE */

	/*

	 * 9. older route (more stable) wins but only if route-age

	 * evaluation is enabled.

	 */

	/* 10. lowest BGP Id wins, use ORIGINATOR_ID if present */

	} else

	} else

	/* 11. compare CLUSTER_LIST length, shorter is better */

	/* 12. lowest peer address wins (IPv4 is better than IPv6) */

	    &p2->aspath->peer->remote_addr,

	    sizeof(p1->aspath->peer->remote_addr)) != 0)

		    &p2->aspath->peer->remote_addr,

		    sizeof(p1->aspath->peer->remote_addr)));

	/* 13. for announced prefixes prefer dynamic routes */

		else

	}

	/* NOTREACHED */

}

/*

 * Find the correct place to insert the prefix in the prefix list.

 * If the active prefix has changed we need to send an update.

 * The to evaluate prefix must not be in the prefix list.

 */

void

prefix_evaluate(struct prefix *p, struct rib_entry *re)

{

	struct prefix	*xp;

		/* decision process is turned off */

		}

		return;

	}

		else {

					/* if xp last element ... */

				}

		}

	}

	    (xp->aspath->nexthop != NULL &&

	    xp->aspath->nexthop->state != NEXTHOP_REACH))

		/* xp is ineligible */

		/* need to generate an update */

		/*

		 * Send update with remove for re->active and add for xp

		 * but remember that xp may be NULL aka ineligible.

		 * Additional decision may be made by the called functions.

		 */

	}

}