bgp/rib-impl/src/main/java/org/opendaylight/protocol/bgp/rib/impl/BestPathSelector.java

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