2 * Copyright (c) 2013 Cisco Systems, Inc. and others. All rights reserved.
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
8 package org.opendaylight.protocol.bgp.rib.impl;
10 import com.google.common.annotations.VisibleForTesting;
11 import com.google.common.base.Preconditions;
12 import com.google.common.net.InetAddresses;
14 import java.util.Arrays;
15 import java.util.Comparator;
16 import java.util.List;
18 import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.inet.types.rev100924.AsNumber;
19 import org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.inet.types.rev100924.Ipv4Address;
20 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.message.rev130919.PathAttributes;
21 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.message.rev130919.path.attributes.as.path.Segments;
22 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.types.rev130919.BgpOrigin;
23 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.types.rev130919.as.path.segment.c.segment.AListCase;
24 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.types.rev130919.as.path.segment.c.segment.ASetCase;
27 * This comparator is intended to implement BGP Best Path Selection algorithm, as described at
29 * @see http://www.cisco.com/en/US/tech/tk365/technologies_tech_note09186a0080094431.shtml
31 * @param <T> Actual object state reference
33 final class BGPObjectComparator implements Comparator<PathAttributes> {
34 private final byte[] localId, remoteId;
35 private final AsNumber ourAS;
37 public BGPObjectComparator(final AsNumber ourAs, final Ipv4Address localId, final Ipv4Address remoteId) {
38 this.ourAS = Preconditions.checkNotNull(ourAs);
39 this.localId = InetAddresses.forString(localId.getValue()).getAddress();
40 this.remoteId = InetAddresses.forString(remoteId.getValue()).getAddress();
44 public int compare(final PathAttributes o1, final PathAttributes o2) {
51 if (o1.equals(o2) && Arrays.equals(this.localId, this.remoteId)) {
54 // 1. prefer path with accessible nexthop
55 // - we assume that all nexthops are accessible
57 // 2. prefer path with higher LOCAL_PREF
58 if ((o1.getLocalPref() != null || o2.getLocalPref() != null)
59 && (o1.getLocalPref() != null && !o1.getLocalPref().equals(o2.getLocalPref()))) {
60 return o1.getLocalPref().getPref().compareTo(o2.getLocalPref().getPref());
63 // 3. prefer learned path
64 // - we assume that all paths are learned
66 // 4. prefer the path with the shortest AS_PATH.
67 if (!o1.getAsPath().equals(o2.getAsPath())) {
68 final Integer i1 = countAsPath(o1.getAsPath().getSegments());
69 final Integer i2 = countAsPath(o2.getAsPath().getSegments());
70 return i2.compareTo(i1);
73 // 5. prefer the path with the lowest origin type
74 // - IGP is lower than Exterior Gateway Protocol (EGP), and EGP is lower than INCOMPLETE
75 if (!o1.getOrigin().equals(o2.getOrigin())) {
76 if (o1.getOrigin().getValue().equals(BgpOrigin.Igp)) {
79 if (o2.getOrigin().getValue().equals(BgpOrigin.Igp)) {
82 if (o1.getOrigin().getValue().equals(BgpOrigin.Egp)) {
89 // 6. prefer the path with the lowest multi-exit discriminator (MED)
90 if ((o1.getMultiExitDisc() != null || o2.getMultiExitDisc() != null)
91 && (o1.getMultiExitDisc() != null && !o1.getMultiExitDisc().equals(o2.getMultiExitDisc()))) {
92 return o2.getMultiExitDisc().getMed().compareTo(o1.getMultiExitDisc().getMed());
95 // 7. prefer eBGP over iBGP paths
96 // EBGP is peering between two different AS, whereas IBGP is between same AS (Autonomous System).
97 final AsNumber first = getPeerAs(o1.getAsPath().getSegments());
98 final AsNumber second = getPeerAs(o2.getAsPath().getSegments());
99 if ((first != null || second != null) && (first != null && !first.equals(second))) {
100 if (first == null || first.equals(this.ourAS)) {
103 if (second == null || second.equals(this.ourAS)) {
108 // 8. Prefer the path with the lowest IGP metric to the BGP next hop.
109 // - no next hop metric is advertized
111 // 9. When both paths are external, prefer the path that was received first (the oldest one).
112 // if (first.equals(this.ourAS) && second.equals(this.ourAS)) {
113 // FIXME: do we have a way how to determine which one was received first?
116 // 10. Prefer the route that comes from the BGP router with the lowest router ID.
117 // The router ID is the highest IP address on the router, with preference given to loopback addresses.
118 // If a path contains route reflector (RR) attributes, the originator ID is substituted for the router ID in the
119 // path selection process.
120 byte[] oid1 = this.localId;
121 byte[] oid2 = this.remoteId;
122 if (o1.getOriginatorId() != null) {
123 oid1 = InetAddresses.forString(o1.getOriginatorId().getOriginator().getValue()).getAddress();
125 if (o2.getOriginatorId() != null) {
126 oid2 = InetAddresses.forString(o2.getOriginatorId().getOriginator().getValue()).getAddress();
128 if (!Arrays.equals(oid1, oid2)) {
129 return compareByteArrays(oid1, oid2);
131 // 11. prefer the path with the minimum cluster list length
134 if (o1.getClusterId() != null) {
135 cluster1 = o1.getClusterId().getCluster().size();
137 if (o2.getClusterId() != null) {
138 cluster2 = o2.getClusterId().getCluster().size();
140 if (cluster1 != cluster2) {
141 return ((Integer) cluster1).compareTo(cluster2);
144 // 12. Prefer the path that comes from the lowest neighbor address.
145 // FIXME: do we know this?
150 private static int countAsPath(final List<Segments> segments) {
151 // an AS_SET counts as 1, no matter how many ASs are in the set.
153 boolean setPresent = false;
154 for (final Segments s : segments) {
155 if (s.getCSegment() instanceof ASetCase) {
158 final AListCase list = (AListCase) s.getCSegment();
159 count += list.getAList().getAsSequence().size();
162 return (setPresent) ? ++count : count;
165 private static AsNumber getPeerAs(final List<Segments> segments) {
166 if (segments.size() == 0) {
169 final AListCase first = (AListCase) segments.get(0).getCSegment();
170 return first.getAList().getAsSequence().get(0).getAs();
174 public static int compareByteArrays(final byte[] byteOne, final byte[] byteTwo) {
175 for (int i = 0; i < byteOne.length; i++) {
176 final int res = Byte.compare(byteOne[i], byteTwo[i]);