Priyanka B | e25cefe8 | 2015-11-28 14:47:23 +0530 | [diff] [blame] | 1 | /* |
Brian O'Connor | a09fe5b | 2017-08-03 21:12:30 -0700 | [diff] [blame] | 2 | * Copyright 2015-present Open Networking Foundation |
Priyanka B | e25cefe8 | 2015-11-28 14:47:23 +0530 | [diff] [blame] | 3 | * |
| 4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
| 5 | * you may not use this file except in compliance with the License. |
| 6 | * You may obtain a copy of the License at |
| 7 | * |
| 8 | * http://www.apache.org/licenses/LICENSE-2.0 |
| 9 | * |
| 10 | * Unless required by applicable law or agreed to in writing, software |
| 11 | * distributed under the License is distributed on an "AS IS" BASIS, |
| 12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 13 | * See the License for the specific language governing permissions and |
| 14 | * limitations under the License. |
| 15 | */ |
| 16 | package org.onosproject.bgp.controller.impl; |
| 17 | |
Priyanka B | e25cefe8 | 2015-11-28 14:47:23 +0530 | [diff] [blame] | 18 | import org.onosproject.bgpio.protocol.linkstate.PathAttrNlriDetailsLocalRib; |
| 19 | import org.onosproject.bgpio.types.AsPath; |
| 20 | import org.onosproject.bgpio.types.BgpValueType; |
| 21 | import org.onosproject.bgpio.types.LocalPref; |
| 22 | import org.onosproject.bgpio.types.Med; |
| 23 | import org.onosproject.bgpio.types.Origin; |
Jonathan Hart | 51539b8 | 2015-10-29 09:53:04 -0700 | [diff] [blame] | 24 | import org.onosproject.bgpio.types.Origin.OriginType; |
Priyanka B | e25cefe8 | 2015-11-28 14:47:23 +0530 | [diff] [blame] | 25 | import org.slf4j.Logger; |
| 26 | import org.slf4j.LoggerFactory; |
| 27 | |
Jonathan Hart | 51539b8 | 2015-10-29 09:53:04 -0700 | [diff] [blame] | 28 | import java.util.Comparator; |
| 29 | import java.util.List; |
| 30 | import java.util.ListIterator; |
| 31 | |
Priyanka B | e25cefe8 | 2015-11-28 14:47:23 +0530 | [diff] [blame] | 32 | /** |
| 33 | * Implementation of BGP best path Selection process. |
| 34 | */ |
| 35 | public final class BgpSelectionAlgo implements Comparator<PathAttrNlriDetailsLocalRib> { |
| 36 | private static final Logger log = LoggerFactory.getLogger(BgpSelectionAlgo.class); |
Ray Milkey | 9922d5c | 2017-12-15 15:25:59 -0800 | [diff] [blame] | 37 | private LocalPref obj1LocPref = null; |
| 38 | private AsPath obj1Aspath = null; |
| 39 | private Origin obj1Origin = null; |
| 40 | private Med obj1Med = null; |
| 41 | private LocalPref obj2LocPref = null; |
| 42 | private AsPath obj2Aspath = null; |
| 43 | private Origin obj2Origin = null; |
| 44 | private Med obj2Med = null; |
Priyanka B | e25cefe8 | 2015-11-28 14:47:23 +0530 | [diff] [blame] | 45 | |
| 46 | @Override |
| 47 | public int compare(PathAttrNlriDetailsLocalRib pathNlriDetails1, PathAttrNlriDetailsLocalRib pathNlriDetails2) { |
| 48 | if (pathNlriDetails1 == null) { |
| 49 | return -1; |
| 50 | } |
| 51 | if (pathNlriDetails2 == null) { |
| 52 | return 1; |
| 53 | } |
| 54 | if (pathNlriDetails1.equals(pathNlriDetails2)) { |
| 55 | return 0; |
| 56 | } |
| 57 | |
| 58 | List<BgpValueType> o1 = pathNlriDetails1.localRibNlridetails().pathAttributes(); |
| 59 | List<BgpValueType> o2 = pathNlriDetails2.localRibNlridetails().pathAttributes(); |
| 60 | ListIterator<BgpValueType> listIteratorObj1 = o1.listIterator(); |
| 61 | ListIterator<BgpValueType> listIteratorObj2 = o2.listIterator(); |
| 62 | storeAttr(listIteratorObj1, listIteratorObj2); |
| 63 | |
| 64 | // prefer attribute with higher local preference |
Ray Milkey | 9922d5c | 2017-12-15 15:25:59 -0800 | [diff] [blame] | 65 | if (obj1LocPref != null && obj2LocPref != null && !obj1LocPref.equals(obj2LocPref)) { |
Priyanka B | e25cefe8 | 2015-11-28 14:47:23 +0530 | [diff] [blame] | 66 | return compareLocalPref(obj1LocPref, obj2LocPref); |
| 67 | } |
| 68 | |
| 69 | // prefer attribute with shortest Aspath |
| 70 | if (!obj1Aspath.equals(obj2Aspath)) { |
| 71 | Integer obj1Size = countASSize(obj1Aspath); |
| 72 | Integer obj2Size = countASSize(obj2Aspath); |
sivag | e1162b5 | 2017-02-01 18:54:00 +0530 | [diff] [blame] | 73 | if (!obj1Size.equals(obj2Size)) { |
Priyanka B | e25cefe8 | 2015-11-28 14:47:23 +0530 | [diff] [blame] | 74 | return compareAsPath(obj1Size, obj2Size); |
| 75 | } |
| 76 | } |
| 77 | |
| 78 | // prefer attribute with lowest origin type |
| 79 | if (!obj1Origin.equals(obj2Origin)) { |
| 80 | return compareOrigin(obj1Origin, obj2Origin); |
| 81 | } |
| 82 | |
| 83 | // prefer attribute with lowest MED |
Ray Milkey | 9922d5c | 2017-12-15 15:25:59 -0800 | [diff] [blame] | 84 | if (obj1Med != null && obj2Med != null && !obj1Med.equals(obj2Med)) { |
Priyanka B | e25cefe8 | 2015-11-28 14:47:23 +0530 | [diff] [blame] | 85 | return compareMed(obj1Med, obj2Med); |
| 86 | } |
| 87 | |
Ray Milkey | 9922d5c | 2017-12-15 15:25:59 -0800 | [diff] [blame] | 88 | return comparePeerDetails(pathNlriDetails1, pathNlriDetails2); |
| 89 | |
Priyanka B | e25cefe8 | 2015-11-28 14:47:23 +0530 | [diff] [blame] | 90 | } |
| 91 | |
| 92 | /** |
| 93 | * Compares local preference of two objects and returns object with higher preference. |
| 94 | * |
| 95 | * @param obj1LocPref local preference object1 |
| 96 | * @param obj2LocPref local preference object2 |
| 97 | * @return object with higher preference |
| 98 | */ |
Ray Milkey | 9922d5c | 2017-12-15 15:25:59 -0800 | [diff] [blame] | 99 | private int compareLocalPref(LocalPref obj1LocPref, LocalPref obj2LocPref) { |
| 100 | return Integer.compare(obj1LocPref.localPref(), obj2LocPref.localPref()); |
Priyanka B | e25cefe8 | 2015-11-28 14:47:23 +0530 | [diff] [blame] | 101 | } |
| 102 | |
| 103 | /** |
| 104 | * Compares AsPath of two objects and returns object with shortest AsPath. |
| 105 | * |
| 106 | * @param obj1Size object1 AS count |
| 107 | * @param obj2Size object2 AS count |
Jian Li | dfba739 | 2016-01-22 16:46:58 -0800 | [diff] [blame] | 108 | * @return object with shortest AsPath |
Priyanka B | e25cefe8 | 2015-11-28 14:47:23 +0530 | [diff] [blame] | 109 | */ |
Ray Milkey | 9922d5c | 2017-12-15 15:25:59 -0800 | [diff] [blame] | 110 | private int compareAsPath(Integer obj1Size, Integer obj2Size) { |
Priyanka B | e25cefe8 | 2015-11-28 14:47:23 +0530 | [diff] [blame] | 111 | return obj1Size.compareTo(obj2Size); |
| 112 | } |
| 113 | |
| 114 | /** |
| 115 | * Compare Origin of two objects and returns object with lowest origin value. |
| 116 | * |
| 117 | * @param obj1Origin Origin object1 |
| 118 | * @param obj2Origin Origin object1 |
| 119 | * @return object with lowest origin value |
| 120 | */ |
Ray Milkey | 9922d5c | 2017-12-15 15:25:59 -0800 | [diff] [blame] | 121 | private int compareOrigin(Origin obj1Origin, Origin obj2Origin) { |
Jonathan Hart | 51539b8 | 2015-10-29 09:53:04 -0700 | [diff] [blame] | 122 | if (obj1Origin.origin() == OriginType.IGP) { |
Priyanka B | e25cefe8 | 2015-11-28 14:47:23 +0530 | [diff] [blame] | 123 | return 1; |
| 124 | } |
Jonathan Hart | 51539b8 | 2015-10-29 09:53:04 -0700 | [diff] [blame] | 125 | if (obj2Origin.origin() == OriginType.IGP) { |
Priyanka B | e25cefe8 | 2015-11-28 14:47:23 +0530 | [diff] [blame] | 126 | return -1; |
| 127 | } |
Jonathan Hart | 51539b8 | 2015-10-29 09:53:04 -0700 | [diff] [blame] | 128 | if (obj1Origin.origin() == OriginType.EGP) { |
Priyanka B | e25cefe8 | 2015-11-28 14:47:23 +0530 | [diff] [blame] | 129 | return 1; |
| 130 | } else { |
| 131 | return -1; |
| 132 | } |
| 133 | } |
| 134 | |
| 135 | /** |
| 136 | * Compare Med of two objects and returns object with lowestMed value. |
| 137 | * |
| 138 | * @param obj1Med Med object1 |
| 139 | * @param obj2Med Med object2 |
| 140 | * @return returns object with lowestMed value |
| 141 | */ |
Ray Milkey | 9922d5c | 2017-12-15 15:25:59 -0800 | [diff] [blame] | 142 | private int compareMed(Med obj1Med, Med obj2Med) { |
| 143 | return Integer.compare(obj2Med.med(), obj1Med.med()); |
Priyanka B | e25cefe8 | 2015-11-28 14:47:23 +0530 | [diff] [blame] | 144 | } |
| 145 | |
| 146 | /** |
| 147 | * Compares EBGP over IBGP, BGP identifier value and peer address. |
| 148 | * |
| 149 | * @param pathNlriDetails1 PathAttrNlriDetailsLocalRib object1 |
| 150 | * @param pathNlriDetails2 PathAttrNlriDetailsLocalRib object2 |
| 151 | * @return object which as EBGP over IBGP, lowest BGP identifier value and lowest peer address |
| 152 | */ |
Ray Milkey | 9922d5c | 2017-12-15 15:25:59 -0800 | [diff] [blame] | 153 | private int comparePeerDetails(PathAttrNlriDetailsLocalRib pathNlriDetails1, |
| 154 | PathAttrNlriDetailsLocalRib pathNlriDetails2) { |
Priyanka B | e25cefe8 | 2015-11-28 14:47:23 +0530 | [diff] [blame] | 155 | // consider EBGP over IBGP |
| 156 | if (pathNlriDetails1.isLocalRibIbgpSession() != pathNlriDetails2.isLocalRibIbgpSession()) { |
Palash Kala | b46d220 | 2017-03-30 19:23:26 +0900 | [diff] [blame] | 157 | if (pathNlriDetails1.isLocalRibIbgpSession()) { |
Priyanka B | e25cefe8 | 2015-11-28 14:47:23 +0530 | [diff] [blame] | 158 | return -1; |
| 159 | } |
Palash Kala | b46d220 | 2017-03-30 19:23:26 +0900 | [diff] [blame] | 160 | if (pathNlriDetails2.isLocalRibIbgpSession()) { |
Priyanka B | e25cefe8 | 2015-11-28 14:47:23 +0530 | [diff] [blame] | 161 | return 1; |
| 162 | } |
| 163 | } |
| 164 | // prefer lowest BGP identifier value. |
| 165 | if (pathNlriDetails1.localRibIdentifier() != pathNlriDetails2.localRibIdentifier()) { |
Ray Milkey | 9922d5c | 2017-12-15 15:25:59 -0800 | [diff] [blame] | 166 | return Integer.compare(pathNlriDetails2.localRibIdentifier(), |
| 167 | pathNlriDetails1.localRibIdentifier()); |
Priyanka B | e25cefe8 | 2015-11-28 14:47:23 +0530 | [diff] [blame] | 168 | } |
| 169 | //prefer lowest peer address |
| 170 | if (pathNlriDetails1.localRibIpAddress() != pathNlriDetails2.localRibIpAddress()) { |
| 171 | return pathNlriDetails2.localRibIpAddress().compareTo(pathNlriDetails1.localRibIpAddress()); |
| 172 | } |
| 173 | return 0; |
| 174 | } |
| 175 | |
| 176 | /** |
| 177 | * Returns ASes count of AsPath attribute , if AS_SET is present then count as 1. |
| 178 | * |
| 179 | * @param aspath object of AsPath |
| 180 | * @return count of ASes |
| 181 | */ |
Ray Milkey | 9922d5c | 2017-12-15 15:25:59 -0800 | [diff] [blame] | 182 | private Integer countASSize(AsPath aspath) { |
Priyanka B | e25cefe8 | 2015-11-28 14:47:23 +0530 | [diff] [blame] | 183 | boolean isASSet = false; |
| 184 | int count = 0; |
| 185 | if (!aspath.asPathSet().isEmpty()) { |
| 186 | isASSet = true; |
| 187 | } |
| 188 | if (!aspath.asPathSeq().isEmpty()) { |
| 189 | count = aspath.asPathSeq().size(); |
| 190 | } |
| 191 | return isASSet ? ++count : count; |
| 192 | } |
| 193 | |
| 194 | /** |
| 195 | * Stores BGP basic attributes of two objects. |
| 196 | * |
| 197 | * @param listIteratorObj1 list iterator of object1 |
| 198 | * @param listIteratorObj2 list iterator of object2 |
| 199 | */ |
Ray Milkey | 9922d5c | 2017-12-15 15:25:59 -0800 | [diff] [blame] | 200 | private void storeAttr(ListIterator<BgpValueType> listIteratorObj1, ListIterator<BgpValueType> listIteratorObj2) { |
Priyanka B | e25cefe8 | 2015-11-28 14:47:23 +0530 | [diff] [blame] | 201 | while (listIteratorObj1.hasNext()) { |
| 202 | BgpValueType pathAttributeObj1 = listIteratorObj1.next(); |
| 203 | switch (pathAttributeObj1.getType()) { |
| 204 | case LocalPref.LOCAL_PREF_TYPE: |
| 205 | obj1LocPref = (LocalPref) pathAttributeObj1; |
| 206 | break; |
| 207 | case AsPath.ASPATH_TYPE: |
| 208 | obj1Aspath = (AsPath) pathAttributeObj1; |
| 209 | break; |
| 210 | case Origin.ORIGIN_TYPE: |
| 211 | obj1Origin = (Origin) pathAttributeObj1; |
| 212 | break; |
| 213 | case Med.MED_TYPE: |
| 214 | obj1Med = (Med) pathAttributeObj1; |
| 215 | break; |
| 216 | default: |
| 217 | log.debug("Got other type, Not required: " + pathAttributeObj1.getType()); |
| 218 | } |
| 219 | } |
| 220 | while (listIteratorObj2.hasNext()) { |
| 221 | BgpValueType pathAttributeObj2 = listIteratorObj2.next(); |
| 222 | switch (pathAttributeObj2.getType()) { |
| 223 | case LocalPref.LOCAL_PREF_TYPE: |
| 224 | obj2LocPref = (LocalPref) pathAttributeObj2; |
| 225 | break; |
| 226 | case AsPath.ASPATH_TYPE: |
| 227 | obj2Aspath = (AsPath) pathAttributeObj2; |
| 228 | break; |
| 229 | case Origin.ORIGIN_TYPE: |
| 230 | obj2Origin = (Origin) pathAttributeObj2; |
| 231 | break; |
| 232 | case Med.MED_TYPE: |
| 233 | obj2Med = (Med) pathAttributeObj2; |
| 234 | break; |
| 235 | default: |
| 236 | log.debug("Got other type, Not required: " + pathAttributeObj2.getType()); |
| 237 | } |
| 238 | } |
| 239 | } |
Jonathan Hart | 51539b8 | 2015-10-29 09:53:04 -0700 | [diff] [blame] | 240 | } |