bgp/rib-spi/src/main/java/org/opendaylight/protocol/bgp/rib/spi/BGPObjectComparator.java

   1 /*
   2  * Copyright (c) 2013 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.spi;
   9
  10 import com.google.common.annotations.VisibleForTesting;
  11 import com.google.common.base.Preconditions;
  12 import java.io.Serializable;
  13 import java.util.Arrays;
  14 import java.util.Comparator;
  15 import java.util.List;
  16 import org.opendaylight.protocol.bgp.rib.spi.AbstractAdjRIBs.RIBEntryData;
  17 import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.inet.types.rev100924.AsNumber;
  18 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.message.rev130919.PathAttributes;
  19 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.message.rev130919.path.attributes.as.path.Segments;
  20 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.types.rev130919.BgpOrigin;
  21 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.types.rev130919.as.path.segment.c.segment.AListCase;
  22 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.types.rev130919.as.path.segment.c.segment.ASetCase;
  23
  24 /**
  25  * This comparator is intended to implement BGP Best Path Selection algorithm, as described at
  26  *
  27  * @see http://www.cisco.com/en/US/tech/tk365/technologies_tech_note09186a0080094431.shtml
  28  *
  29  * @param <T> Actual object state reference
  30  */
  31 public final class BGPObjectComparator implements Comparator<RIBEntryData<?, ?, ?>>, Serializable {
  32
  33     private static final long serialVersionUID = 3299599519482155374L;
  34
  35     private final AsNumber ourAS;
  36
  37     public BGPObjectComparator(final AsNumber ourAs) {
  38         this.ourAS = Preconditions.checkNotNull(ourAs);
  39     }
  40
  41     @Override
  42     public int compare(final RIBEntryData<?, ?, ?> newObject, final RIBEntryData<?, ?, ?> oldObject) {
  43         if (newObject == oldObject) {
  44             return 0;
  45         }
  46         if (newObject == null) {
  47             return 1;
  48         }
  49         if (oldObject == null) {
  50             return -1;
  51         }
  52
  53         final PathAttributes newPath = newObject.getPathAttributes();
  54         final PathAttributes oldPath = oldObject.getPathAttributes();
  55         if (newPath.equals(oldPath) && Arrays.equals(newObject.getPeer().getRawIdentifier(), oldObject.getPeer().getRawIdentifier())) {
  56             return 0;
  57         }
  58
  59         // 1. prefer path with accessible nexthop
  60         // - we assume that all nexthops are accessible
  61
  62         // 2. prefer path with higher LOCAL_PREF
  63         if ((newPath.getLocalPref() != null || oldPath.getLocalPref() != null)
  64                 && (newPath.getLocalPref() != null && !newPath.getLocalPref().equals(oldPath.getLocalPref()))) {
  65             return newPath.getLocalPref().getPref().compareTo(oldPath.getLocalPref().getPref());
  66         }
  67
  68         // 3. prefer learned path
  69         // - we assume that all paths are learned
  70
  71         // 4. prefer the path with the shortest AS_PATH.
  72         if (!newPath.getAsPath().equals(oldPath.getAsPath())) {
  73             final Integer i1 = countAsPath(newPath.getAsPath().getSegments());
  74             final Integer i2 = countAsPath(oldPath.getAsPath().getSegments());
  75             return i2.compareTo(i1);
  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 (!newPath.getOrigin().equals(oldPath.getOrigin())) {
  81             if (newPath.getOrigin().getValue().equals(BgpOrigin.Igp)) {
  82                 return 1;
  83             }
  84             if (oldPath.getOrigin().getValue().equals(BgpOrigin.Igp)) {
  85                 return -1;
  86             }
  87             if (newPath.getOrigin().getValue().equals(BgpOrigin.Egp)) {
  88                 return 1;
  89             } else {
  90                 return -1;
  91             }
  92         }
  93
  94         // 6. prefer the path with the lowest multi-exit discriminator (MED)
  95         if ((newPath.getMultiExitDisc() != null || oldPath.getMultiExitDisc() != null)
  96                 && (newPath.getMultiExitDisc() != null && !newPath.getMultiExitDisc().equals(oldPath.getMultiExitDisc()))) {
  97             return oldPath.getMultiExitDisc().getMed().compareTo(newPath.getMultiExitDisc().getMed());
  98         }
  99
 100         // 7. prefer eBGP over iBGP paths
 101         // EBGP is peering between two different AS, whereas IBGP is between same AS (Autonomous System).
 102         final AsNumber first = getPeerAs(newPath.getAsPath().getSegments());
 103         final AsNumber second = getPeerAs(oldPath.getAsPath().getSegments());
 104         if ((first != null || second != null) && (first != null && !first.equals(second))) {
 105             if (first.equals(this.ourAS)) {
 106                 return -1;
 107             }
 108             if (second == null || second.equals(this.ourAS)) {
 109                 return 1;
 110             }
 111         }
 112
 113         // 8. Prefer the path with the lowest IGP metric to the BGP next hop.
 114         // - no next hop metric is advertized
 115
 116         // 9. When both paths are external, prefer the path that was received first (the oldest one).
 117         // if (first.equals(this.ourAS) && second.equals(this.ourAS)) {
 118         // FIXME: do we have a way how to determine which one was received first?
 119
 120         // 10. Prefer the route that comes from the BGP router with the lowest router ID.
 121         // The router ID is the highest IP address on the router, with preference given to loopback addresses.
 122         // If a path contains route reflector (RR) attributes, the originator ID is substituted for the router ID in the
 123         // path selection process.
 124
 125         // RFC5004 states that this algorithm should end here and select existing path over new path in the
 126         // best path selection process. Benefits are listed in the RFC: @see http://tools.ietf.org/html/rfc500
 127         // - This algorithm SHOULD NOT be applied when either path is from a BGP Confederation peer.
 128         //  - not applicable, we don't deal with confederation peers
 129         // - The algorithm SHOULD NOT be applied when both paths are from peers with an identical BGP identifier (i.e., there exist parallel BGP sessions between two BGP speakers).
 130         //  - not applicable, BUG-2631 prevents parallel sessions to be created.
 131
 132         return -1;
 133     }
 134
 135     private static int countAsPath(final List<Segments> segments) {
 136         // an AS_SET counts as 1, no matter how many ASs are in the set.
 137         int count = 0;
 138         boolean setPresent = false;
 139         for (final Segments s : segments) {
 140             if (s.getCSegment() instanceof ASetCase) {
 141                 setPresent = true;
 142             } else {
 143                 final AListCase list = (AListCase) s.getCSegment();
 144                 count += list.getAList().getAsSequence().size();
 145             }
 146         }
 147         return (setPresent) ? ++count : count;
 148     }
 149
 150     private static AsNumber getPeerAs(final List<Segments> segments) {
 151         if (segments.size() == 0) {
 152             return null;
 153         }
 154         final AListCase first = (AListCase) segments.get(0).getCSegment();
 155         return first.getAList().getAsSequence().get(0).getAs();
 156     }
 157
 158     @VisibleForTesting
 159     public static int compareByteArrays(final byte[] byteOne, final byte[] byteTwo) {
 160         for (int i = 0; i < byteOne.length; i++) {
 161             final int res = Byte.compare(byteOne[i], byteTwo[i]);
 162             if (res != 0) {
 163                 return res;
 164             }
 165         }
 166         return 0;
 167     }
 168 }