bgp/rib-impl/src/main/java/org/opendaylight/protocol/bgp/rib/impl/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.impl;
   9
  10 import java.util.Arrays;
  11 import java.util.Comparator;
  12 import java.util.List;
  13
  14 import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.inet.types.rev100924.AsNumber;
  15 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.message.rev130919.PathAttributes;
  16 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.message.rev130919.path.attributes.as.path.Segments;
  17 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.types.rev130919.BgpOrigin;
  18 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.types.rev130919.as.path.segment.c.segment.AListCase;
  19 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.types.rev130919.as.path.segment.c.segment.ASetCase;
  20
  21 import com.google.common.annotations.VisibleForTesting;
  22
  23 /**
  24  * This comparator is intended to implement BGP Best Path Selection algorithm, as described at
  25  *
  26  * @see http://www.cisco.com/en/US/tech/tk365/technologies_tech_note09186a0080094431.shtml
  27  *
  28  * @param <T> Actual object state reference
  29  */
  30 final class BGPObjectComparator implements Comparator<PathAttributes> {
  31
  32         private final AsNumber ourAS;
  33
  34         private final byte[] id1;
  35
  36         private final byte[] id2;
  37
  38         public BGPObjectComparator(final AsNumber ourAs, final byte[] id1, final byte[] id2) {
  39                 this.ourAS = ourAs;
  40                 this.id1 = id1;
  41                 this.id2 = id2;
  42         }
  43
  44         @Override
  45         public int compare(final PathAttributes o1, final PathAttributes o2) {
  46                 if (o1 == null) {
  47                         return 1;
  48                 }
  49                 if (o2 == null) {
  50                         return -1;
  51                 }
  52                 if (o1.equals(o2) && Arrays.equals(this.id1, this.id2)) {
  53                         return 0;
  54                 }
  55                 // 1. prefer path with accessible nexthop
  56                 // - we assume that all nexthops are accessible
  57
  58                 // 2. prefer path with higher LOCAL_PREF
  59                 if ((o1.getLocalPref() != null || o2.getLocalPref() != null)
  60                                 && (o1.getLocalPref() != null && !o1.getLocalPref().equals(o2.getLocalPref()))) {
  61                         return o1.getLocalPref().getPref().compareTo(o2.getLocalPref().getPref());
  62                 }
  63
  64                 // 3. prefer learned path
  65                 // - we assume that all paths are learned
  66
  67                 // 4. prefer the path with the shortest AS_PATH.
  68                 if (!o1.getAsPath().equals(o2.getAsPath())) {
  69                         final Integer i1 = countAsPath(o1.getAsPath().getSegments());
  70                         final Integer i2 = countAsPath(o2.getAsPath().getSegments());
  71                         return i2.compareTo(i1);
  72                 }
  73
  74                 // 5. prefer the path with the lowest origin type
  75                 // - IGP is lower than Exterior Gateway Protocol (EGP), and EGP is lower than INCOMPLETE
  76                 if (!o1.getOrigin().equals(o2.getOrigin())) {
  77                         if (o1.getOrigin().getValue().equals(BgpOrigin.Igp)) {
  78                                 return 1;
  79                         }
  80                         if (o2.getOrigin().getValue().equals(BgpOrigin.Igp)) {
  81                                 return -1;
  82                         }
  83                         if (o1.getOrigin().getValue().equals(BgpOrigin.Egp)) {
  84                                 return 1;
  85                         } else {
  86                                 return -1;
  87                         }
  88                 }
  89
  90                 // 6. prefer the path with the lowest multi-exit discriminator (MED)
  91                 if ((o1.getMultiExitDisc() != null || o2.getMultiExitDisc() != null)
  92                                 && (o1.getMultiExitDisc() != null && !o1.getMultiExitDisc().equals(o2.getMultiExitDisc()))) {
  93                         return o2.getMultiExitDisc().getMed().compareTo(o1.getMultiExitDisc().getMed());
  94                 }
  95
  96                 // 7. prefer eBGP over iBGP paths
  97                 // EBGP is peering between two different AS, whereas IBGP is between same AS (Autonomous System).
  98                 final AsNumber first = getPeerAs(o1.getAsPath().getSegments());
  99                 final AsNumber second = getPeerAs(o2.getAsPath().getSegments());
 100                 if ((first != null || second != null) && (first != null && !first.equals(second))) {
 101                         if (first == null || first.equals(this.ourAS)) {
 102                                 return -1;
 103                         }
 104                         if (second == null || second.equals(this.ourAS)) {
 105                                 return 1;
 106                         }
 107                 }
 108
 109                 // 8. Prefer the path with the lowest IGP metric to the BGP next hop.
 110                 // - no next hop metric is advertized
 111
 112                 // 9. When both paths are external, prefer the path that was received first (the oldest one).
 113                 // if (first.equals(this.ourAS) && second.equals(this.ourAS)) {
 114                 // FIXME: do we have a way how to determine which one was received first?
 115                 // }
 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 = this.id1;
 122                 byte[] oid2 = this.id2;
 123                 if (o1.getOriginatorId() != null) {
 124                         oid1 = o1.getOriginatorId();
 125                 }
 126                 if (o2.getOriginatorId() != null) {
 127                         oid2 = o2.getOriginatorId();
 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().size();
 137                 }
 138                 if (o2.getClusterId() != null) {
 139                         cluster2 = o2.getClusterId().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 }