bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/spi/AbstractBestPathSelector.java

   1 /*
   2  * Copyright (c) 2016 Cisco Systems, Inc. and others.  All rights reserved.
   3  *
   4  * This program and the accompanying materials are made available under the
   5  * terms of the Eclipse Public License v1.0 which accompanies this distribution,
   6  * and is available at http://www.eclipse.org/legal/epl-v10.html
   7  */
   8
   9 package org.opendaylight.protocol.bgp.mode.spi;
  10
  11 import javax.annotation.Nonnull;
  12 import org.opendaylight.protocol.bgp.mode.api.BestPathState;
  13 import org.opendaylight.protocol.bgp.rib.spi.RouterId;
  14 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.message.rev180329.path.attributes.attributes.OriginatorId;
  15 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.types.rev180329.BgpOrigin;
  16
  17 public class AbstractBestPathSelector {
  18     private final long ourAs;
  19     protected RouterId bestOriginatorId = null;
  20     protected BestPathState bestState = null;
  21
  22     protected AbstractBestPathSelector(final long ourAs) {
  23         this.ourAs = ourAs;
  24     }
  25
  26     /**
  27      * RFC 4456 mandates the use of Originator IDs instead of Router ID for
  28      * selection purposes.
  29      *
  30      * @param routerId     routerID
  31      * @param originatorId originator
  32      * @return returns originators Id if present otherwise routerId
  33      */
  34     protected RouterId replaceOriginator(final RouterId routerId, final OriginatorId originatorId) {
  35         return originatorId != null ? RouterId.forAddress(originatorId.getOriginator()) : routerId;
  36     }
  37
  38     /**
  39      * Chooses best route according to BGP best path selection.
  40      *
  41      * @param state attributes of the new route
  42      * @return true if the existing path is better, false if the new path is better
  43      */
  44     protected boolean isExistingPathBetter(@Nonnull final BestPathState state) {
  45         // 0. draft-uttaro-idr-bgp-persistence-04 defines "depreferenced" paths
  46         final boolean stateDepref = state.isDepreferenced();
  47         if (this.bestState.isDepreferenced() != stateDepref) {
  48             return stateDepref;
  49         }
  50
  51         // 1. prefer path with accessible nexthop
  52         // - we assume that all nexthops are accessible
  53         /*
  54          * 2. prefer path with higher LOCAL_PREF
  55          *
  56          * FIXME: for eBGP cases (when the LOCAL_PREF is missing), we should assign a policy-based preference
  57          *        before we ever get here.
  58          */
  59         final Long bestLocal = this.bestState.getLocalPref();
  60         final Long stateLocal = state.getLocalPref();
  61         if (stateLocal != null) {
  62             if (bestLocal == null) {
  63                 return true;
  64             }
  65
  66             final Boolean bool = firstLower(stateLocal, bestLocal);
  67             if (bool != null) {
  68                 return bool;
  69             }
  70         } else if (bestLocal != null) {
  71             return false;
  72         }
  73
  74         // 3. prefer learned path
  75         // - we assume that all paths are learned
  76
  77         // 4. prefer the path with the shortest AS_PATH.
  78         if (this.bestState.getAsPathLength() != state.getAsPathLength()) {
  79             return this.bestState.getAsPathLength() < state.getAsPathLength();
  80         }
  81
  82         // 5. prefer the path with the lowest origin type
  83         // - IGP is lower than Exterior Gateway Protocol (EGP), and EGP is lower than INCOMPLETE
  84         if (!this.bestState.getOrigin().equals(state.getOrigin())) {
  85             final BgpOrigin bo = this.bestState.getOrigin();
  86             final BgpOrigin no = state.getOrigin();
  87
  88             // This trick relies on the order in which the values are declared in the model.
  89             return no.ordinal() > bo.ordinal();
  90         }
  91         // FIXME: we should be able to cache the best AS
  92         final long bestAs = this.bestState.getPeerAs();
  93         final long newAs = state.getPeerAs();
  94
  95         /*
  96          * Checks 6 and 7 are mutually-exclusive, as MEDs are comparable
  97          * only when the routes originated from the same AS. On the other
  98          * hand, when they are from the same AS, they are in the same iBGP/eBGP
  99          * relationship.
 100          *
 101          */
 102         if (bestAs == newAs) {
 103             // 6. prefer the path with the lowest multi-exit discriminator (MED)
 104             final Boolean cmp = firstLower(this.bestState.getMultiExitDisc(), state.getMultiExitDisc());
 105             if (cmp != null) {
 106                 return cmp;
 107             }
 108         } else {
 109             /*
 110              * 7. prefer eBGP over iBGP paths
 111              *
 112              * EBGP is peering between two different AS, whereas IBGP is between same AS (Autonomous System),
 113              * so we just compare the AS numbers to our AS.
 114              *
 115              * FIXME: we should know this information from the peer directly.
 116              */
 117             if (this.ourAs != bestAs && this.ourAs == newAs) {
 118                 return true;
 119             }
 120         }
 121
 122         // 8. Prefer the path with the lowest IGP metric to the BGP next hop.
 123         // - no next hop metric is advertised
 124
 125         /*
 126          * 9. When both paths are external, prefer the path that was received first (the oldest one).
 127          *
 128          * FIXME: we do not want to store an explicit timer for each set due to performance/memory
 129          *        constraints. Our caller has the information about which attributes have changed
 130          *        since the selection process has ran last time, which may be a good enough approximation,
 131          *        but its properties need to be analyzed.
 132          */
 133
 134         /*
 135          * 10. Prefer the route that comes from the BGP router with the lowest router ID.
 136          *
 137          * This is normally guaranteed by the iteration order of our caller, which runs selection
 138          * in the order of increasing router ID, but RFC-4456 Route Reflection throws a wrench into that.
 139          *
 140          * With RFC-5004, this gets a bit easier, because it completely eliminates step f) and later :-)
 141          *
 142          * RFC-5004 states that this algorithm should end here and select existing path over new path in the
 143          * best path selection process. Benefits are listed in the RFC: @see http://tools.ietf.org/html/rfc500
 144          * - This algorithm SHOULD NOT be applied when either path is from a BGP Confederation peer.
 145          *  - not applicable, we don't deal with confederation peers
 146          * - The algorithm SHOULD NOT be applied when both paths are from peers with an identical BGP identifier
 147          *   (i.e., there exist parallel BGP sessions between two BGP speakers).
 148          *  - not applicable, BUG-2631 prevents parallel sessions to be created.
 149          */
 150         return true;
 151     }
 152
 153     private static Boolean firstLower(final long first, final long second) {
 154         return first < second ? Boolean.TRUE : first == second ? null : Boolean.FALSE;
 155
 156     }
 157 }