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 com.google.common.net.InetAddresses;
  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<?, ?, ?>> {
  32     private final AsNumber ourAS;
  33
  34     public BGPObjectComparator(final AsNumber ourAs) {
  35         this.ourAS = Preconditions.checkNotNull(ourAs);
  36     }
  37
  38     @Override
  39     public int compare(final RIBEntryData<?, ?, ?> e1, final RIBEntryData<?, ?, ?> e2) {
  40         if (e1 == e2) {
  41             return 0;
  42         }
  43         if (e1 == null) {
  44             return 1;
  45         }
  46         if (e2 == null) {
  47             return -1;
  48         }
  49
  50         final PathAttributes o1 = e1.getPathAttributes();
  51         final PathAttributes o2 = e2.getPathAttributes();
  52         if (o1.equals(o2) && Arrays.equals(e1.getPeer().getRawIdentifier(), e2.getPeer().getRawIdentifier())) {
  53             return 0;
  54         }
  55
  56         // 1. prefer path with accessible nexthop
  57         // - we assume that all nexthops are accessible
  58
  59         // 2. prefer path with higher LOCAL_PREF
  60         if ((o1.getLocalPref() != null || o2.getLocalPref() != null)
  61                 && (o1.getLocalPref() != null && !o1.getLocalPref().equals(o2.getLocalPref()))) {
  62             return o1.getLocalPref().getPref().compareTo(o2.getLocalPref().getPref());
  63         }
  64
  65         // 3. prefer learned path
  66         // - we assume that all paths are learned
  67
  68         // 4. prefer the path with the shortest AS_PATH.
  69         if (!o1.getAsPath().equals(o2.getAsPath())) {
  70             final Integer i1 = countAsPath(o1.getAsPath().getSegments());
  71             final Integer i2 = countAsPath(o2.getAsPath().getSegments());
  72             return i2.compareTo(i1);
  73         }
  74
  75         // 5. prefer the path with the lowest origin type
  76         // - IGP is lower than Exterior Gateway Protocol (EGP), and EGP is lower than INCOMPLETE
  77         if (!o1.getOrigin().equals(o2.getOrigin())) {
  78             if (o1.getOrigin().getValue().equals(BgpOrigin.Igp)) {
  79                 return 1;
  80             }
  81             if (o2.getOrigin().getValue().equals(BgpOrigin.Igp)) {
  82                 return -1;
  83             }
  84             if (o1.getOrigin().getValue().equals(BgpOrigin.Egp)) {
  85                 return 1;
  86             } else {
  87                 return -1;
  88             }
  89         }
  90
  91         // 6. prefer the path with the lowest multi-exit discriminator (MED)
  92         if ((o1.getMultiExitDisc() != null || o2.getMultiExitDisc() != null)
  93                 && (o1.getMultiExitDisc() != null && !o1.getMultiExitDisc().equals(o2.getMultiExitDisc()))) {
  94             return o2.getMultiExitDisc().getMed().compareTo(o1.getMultiExitDisc().getMed());
  95         }
  96
  97         // 7. prefer eBGP over iBGP paths
  98         // EBGP is peering between two different AS, whereas IBGP is between same AS (Autonomous System).
  99         final AsNumber first = getPeerAs(o1.getAsPath().getSegments());
 100         final AsNumber second = getPeerAs(o2.getAsPath().getSegments());
 101         if ((first != null || second != null) && (first != null && !first.equals(second))) {
 102             if (first.equals(this.ourAS)) {
 103                 return -1;
 104             }
 105             if (second == null || second.equals(this.ourAS)) {
 106                 return 1;
 107             }
 108         }
 109
 110         // 8. Prefer the path with the lowest IGP metric to the BGP next hop.
 111         // - no next hop metric is advertized
 112
 113         // 9. When both paths are external, prefer the path that was received first (the oldest one).
 114         // if (first.equals(this.ourAS) && second.equals(this.ourAS)) {
 115         // FIXME: do we have a way how to determine which one was received first?
 116
 117         // 10. Prefer the route that comes from the BGP router with the lowest router ID.
 118         // The router ID is the highest IP address on the router, with preference given to loopback addresses.
 119         // If a path contains route reflector (RR) attributes, the originator ID is substituted for the router ID in the
 120         // path selection process.
 121         byte[] oid1 = e1.getPeer().getRawIdentifier();
 122         byte[] oid2 = e2.getPeer().getRawIdentifier();
 123         if (o1.getOriginatorId() != null) {
 124             oid1 = InetAddresses.forString(o1.getOriginatorId().getOriginator().getValue()).getAddress();
 125         }
 126         if (o2.getOriginatorId() != null) {
 127             oid2 = InetAddresses.forString(o2.getOriginatorId().getOriginator().getValue()).getAddress();
 128         }
 129         if (!Arrays.equals(oid1, oid2)) {
 130             return compareByteArrays(oid1, oid2);
 131         }
 132         // 11. prefer the path with the minimum cluster list length
 133         int cluster1 = 0;
 134         int cluster2 = 0;
 135         if (o1.getClusterId() != null) {
 136             cluster1 = o1.getClusterId().getCluster().size();
 137         }
 138         if (o2.getClusterId() != null) {
 139             cluster2 = o2.getClusterId().getCluster().size();
 140         }
 141         if (cluster1 != cluster2) {
 142             return ((Integer) cluster1).compareTo(cluster2);
 143         }
 144
 145         // 12. Prefer the path that comes from the lowest neighbor address.
 146         // FIXME: do we know this?
 147
 148         return 0;
 149     }
 150
 151     private static int countAsPath(final List<Segments> segments) {
 152         // an AS_SET counts as 1, no matter how many ASs are in the set.
 153         int count = 0;
 154         boolean setPresent = false;
 155         for (final Segments s : segments) {
 156             if (s.getCSegment() instanceof ASetCase) {
 157                 setPresent = true;
 158             } else {
 159                 final AListCase list = (AListCase) s.getCSegment();
 160                 count += list.getAList().getAsSequence().size();
 161             }
 162         }
 163         return (setPresent) ? ++count : count;
 164     }
 165
 166     private static AsNumber getPeerAs(final List<Segments> segments) {
 167         if (segments.size() == 0) {
 168             return null;
 169         }
 170         final AListCase first = (AListCase) segments.get(0).getCSegment();
 171         return first.getAList().getAsSequence().get(0).getAs();
 172     }
 173
 174     @VisibleForTesting
 175     public static int compareByteArrays(final byte[] byteOne, final byte[] byteTwo) {
 176         for (int i = 0; i < byteOne.length; i++) {
 177             final int res = Byte.compare(byteOne[i], byteTwo[i]);
 178             if (res != 0) {
 179                 return res;
 180             }
 181         }
 182         return 0;
 183     }
 184 }