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