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