gerrit.opnfv Code Review - onosfw.git/blob

   1 /*
   2  * Copyright 2015 Open Networking Laboratory
   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.segmentrouting;
  17
  18 import com.google.common.collect.Maps;
  19 import com.google.common.collect.Sets;
  20 import org.onlab.packet.Ip4Address;
  21 import org.onlab.packet.Ip4Prefix;
  22 import org.onlab.packet.IpPrefix;
  23 import org.onosproject.net.Device;
  24 import org.onosproject.net.DeviceId;
  25 import org.onosproject.net.Link;
  26 import org.slf4j.Logger;
  27 import org.slf4j.LoggerFactory;
  28
  29 import java.util.ArrayList;
  30 import java.util.HashMap;
  31 import java.util.HashSet;
  32 import java.util.Set;
  33 import java.util.concurrent.locks.Lock;
  34 import java.util.concurrent.locks.ReentrantLock;
  35
  36 import static com.google.common.base.Preconditions.checkNotNull;
  37
  38 public class DefaultRoutingHandler {
  39
  40     private static Logger log = LoggerFactory
  41             .getLogger(DefaultRoutingHandler.class);
  42
  43     private SegmentRoutingManager srManager;
  44     private RoutingRulePopulator rulePopulator;
  45     private HashMap<DeviceId, ECMPShortestPathGraph> currentEcmpSpgMap;
  46     private HashMap<DeviceId, ECMPShortestPathGraph> updatedEcmpSpgMap;
  47     private DeviceConfiguration config;
  48     private final Lock statusLock = new ReentrantLock();
  49     private volatile Status populationStatus;
  50
  51     /**
  52      * Represents the default routing population status.
  53      */
  54     public enum Status {
  55         // population process is not started yet.
  56         IDLE,
  57
  58         // population process started.
  59         STARTED,
  60
  61         // population process was aborted due to errors, mostly for groups not
  62         // found.
  63         ABORTED,
  64
  65         // population process was finished successfully.
  66         SUCCEEDED
  67     }
  68
  69     /**
  70      * Creates a DefaultRoutingHandler object.
  71      *
  72      * @param srManager SegmentRoutingManager object
  73      */
  74     public DefaultRoutingHandler(SegmentRoutingManager srManager) {
  75         this.srManager = srManager;
  76         this.rulePopulator = checkNotNull(srManager.routingRulePopulator);
  77         this.config = checkNotNull(srManager.deviceConfiguration);
  78         this.populationStatus = Status.IDLE;
  79         this.currentEcmpSpgMap = Maps.newHashMap();
  80     }
  81
  82     /**
  83      * Populates all routing rules to all connected routers, including default
  84      * routing rules, adjacency rules, and policy rules if any.
  85      *
  86      * @return true if it succeeds in populating all rules, otherwise false
  87      */
  88     public boolean populateAllRoutingRules() {
  89
  90         statusLock.lock();
  91         try {
  92             populationStatus = Status.STARTED;
  93             rulePopulator.resetCounter();
  94             log.info("Starting to populate segment-routing rules");
  95             log.debug("populateAllRoutingRules: populationStatus is STARTED");
  96
  97             for (Device sw : srManager.deviceService.getDevices()) {
  98                 if (!srManager.mastershipService.isLocalMaster(sw.id())) {
  99                     log.debug("populateAllRoutingRules: skipping device {}...we are not master",
 100                               sw.id());
 101                     continue;
 102                 }
 103
 104                 ECMPShortestPathGraph ecmpSpg = new ECMPShortestPathGraph(sw.id(), srManager);
 105                 if (!populateEcmpRoutingRules(sw.id(), ecmpSpg)) {
 106                     log.debug("populateAllRoutingRules: populationStatus is ABORTED");
 107                     populationStatus = Status.ABORTED;
 108                     log.debug("Abort routing rule population");
 109                     return false;
 110                 }
 111                 currentEcmpSpgMap.put(sw.id(), ecmpSpg);
 112
 113                 // TODO: Set adjacency routing rule for all switches
 114             }
 115
 116             log.debug("populateAllRoutingRules: populationStatus is SUCCEEDED");
 117             populationStatus = Status.SUCCEEDED;
 118             log.info("Completed routing rule population. Total # of rules pushed : {}",
 119                     rulePopulator.getCounter());
 120             return true;
 121         } finally {
 122             statusLock.unlock();
 123         }
 124     }
 125
 126     /**
 127      * Populates the routing rules according to the route changes due to the link
 128      * failure or link add. It computes the routes changed due to the link changes and
 129      * repopulates the rules only for the routes.
 130      *
 131      * @param linkFail link failed, null for link added
 132      * @return true if it succeeds to populate all rules, false otherwise
 133      */
 134     public boolean populateRoutingRulesForLinkStatusChange(Link linkFail) {
 135
 136         statusLock.lock();
 137         try {
 138
 139             if (populationStatus == Status.STARTED) {
 140                 log.warn("Previous rule population is not finished.");
 141                 return true;
 142             }
 143
 144             // Take the snapshots of the links
 145             updatedEcmpSpgMap = new HashMap<>();
 146             for (Device sw : srManager.deviceService.getDevices()) {
 147                 if (!srManager.mastershipService.isLocalMaster(sw.id())) {
 148                     continue;
 149                 }
 150                 ECMPShortestPathGraph ecmpSpgUpdated =
 151                         new ECMPShortestPathGraph(sw.id(), srManager);
 152                 updatedEcmpSpgMap.put(sw.id(), ecmpSpgUpdated);
 153             }
 154
 155             log.info("Starts rule population from link change");
 156
 157             Set<ArrayList<DeviceId>> routeChanges;
 158             log.trace("populateRoutingRulesForLinkStatusChange: "
 159                     + "populationStatus is STARTED");
 160             populationStatus = Status.STARTED;
 161             if (linkFail == null) {
 162                 // Compare all routes of existing ECMP SPG with the new ones
 163                 routeChanges = computeRouteChange();
 164             } else {
 165                 // Compare existing ECMP SPG only with the link removed
 166                 routeChanges = computeDamagedRoutes(linkFail);
 167             }
 168
 169             if (routeChanges.isEmpty()) {
 170                 log.info("No route changes for the link status change");
 171                 log.debug("populateRoutingRulesForLinkStatusChange: populationStatus is SUCCEEDED");
 172                 populationStatus = Status.SUCCEEDED;
 173                 return true;
 174             }
 175
 176             if (repopulateRoutingRulesForRoutes(routeChanges)) {
 177                 log.debug("populateRoutingRulesForLinkStatusChange: populationStatus is SUCCEEDED");
 178                 populationStatus = Status.SUCCEEDED;
 179                 log.info("Complete to repopulate the rules. # of rules populated : {}",
 180                         rulePopulator.getCounter());
 181                 return true;
 182             } else {
 183                 log.debug("populateRoutingRulesForLinkStatusChange: populationStatus is ABORTED");
 184                 populationStatus = Status.ABORTED;
 185                 log.warn("Failed to repopulate the rules.");
 186                 return false;
 187             }
 188         } finally {
 189             statusLock.unlock();
 190         }
 191     }
 192
 193     private boolean repopulateRoutingRulesForRoutes(Set<ArrayList<DeviceId>> routes) {
 194         rulePopulator.resetCounter();
 195         HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>> routesBydevice =
 196                 new HashMap<>();
 197         for (ArrayList<DeviceId> link: routes) {
 198             // When only the source device is defined, reinstall routes to all other devices
 199             if (link.size() == 1) {
 200                 log.trace("repopulateRoutingRulesForRoutes: running ECMP graph for device {}", link.get(0));
 201                 ECMPShortestPathGraph ecmpSpg = new ECMPShortestPathGraph(link.get(0), srManager);
 202                 if (populateEcmpRoutingRules(link.get(0), ecmpSpg)) {
 203                     log.debug("Populating flow rules from {} to all is successful",
 204                               link.get(0));
 205                     currentEcmpSpgMap.put(link.get(0), ecmpSpg);
 206                 } else {
 207                     log.warn("Failed to populate the flow rules from {} to all", link.get(0));
 208                     return false;
 209                 }
 210             } else {
 211                 ArrayList<ArrayList<DeviceId>> deviceRoutes =
 212                         routesBydevice.get(link.get(1));
 213                 if (deviceRoutes == null) {
 214                     deviceRoutes = new ArrayList<>();
 215                     routesBydevice.put(link.get(1), deviceRoutes);
 216                 }
 217                 deviceRoutes.add(link);
 218             }
 219         }
 220
 221         for (DeviceId impactedDevice : routesBydevice.keySet()) {
 222             ArrayList<ArrayList<DeviceId>> deviceRoutes =
 223                     routesBydevice.get(impactedDevice);
 224             for (ArrayList<DeviceId> link: deviceRoutes) {
 225                 log.debug("repopulate RoutingRules For Routes {} -> {}",
 226                           link.get(0), link.get(1));
 227                 DeviceId src = link.get(0);
 228                 DeviceId dst = link.get(1);
 229                 ECMPShortestPathGraph ecmpSpg = updatedEcmpSpgMap.get(dst);
 230                 HashMap<Integer, HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>>> switchVia =
 231                         ecmpSpg.getAllLearnedSwitchesAndVia();
 232                 for (Integer itrIdx : switchVia.keySet()) {
 233                     HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>> swViaMap =
 234                             switchVia.get(itrIdx);
 235                     for (DeviceId targetSw : swViaMap.keySet()) {
 236                         if (!targetSw.equals(src)) {
 237                             continue;
 238                         }
 239                         Set<DeviceId> nextHops = new HashSet<>();
 240                         for (ArrayList<DeviceId> via : swViaMap.get(targetSw)) {
 241                             if (via.isEmpty()) {
 242                                 nextHops.add(dst);
 243                             } else {
 244                                 nextHops.add(via.get(0));
 245                             }
 246                         }
 247                         if (!populateEcmpRoutingRulePartial(targetSw, dst, nextHops)) {
 248                             return false;
 249                         }
 250                         log.debug("Populating flow rules from {} to {} is successful",
 251                                   targetSw, dst);
 252                     }
 253                 }
 254                 //currentEcmpSpgMap.put(dst, ecmpSpg);
 255             }
 256             //Only if all the flows for all impacted routes to a
 257             //specific target are pushed successfully, update the
 258             //ECMP graph for that target. (Or else the next event
 259             //would not see any changes in the ECMP graphs)
 260             currentEcmpSpgMap.put(impactedDevice,
 261                                   updatedEcmpSpgMap.get(impactedDevice));
 262         }
 263         return true;
 264     }
 265
 266     private Set<ArrayList<DeviceId>> computeDamagedRoutes(Link linkFail) {
 267
 268         Set<ArrayList<DeviceId>> routes = new HashSet<>();
 269
 270         for (Device sw : srManager.deviceService.getDevices()) {
 271             log.debug("Computing the impacted routes for device {} due to link fail",
 272                       sw.id());
 273             if (!srManager.mastershipService.isLocalMaster(sw.id())) {
 274                 continue;
 275             }
 276             ECMPShortestPathGraph ecmpSpg = currentEcmpSpgMap.get(sw.id());
 277             if (ecmpSpg == null) {
 278                 log.error("No existing ECMP graph for switch {}", sw.id());
 279                 continue;
 280             }
 281             HashMap<Integer, HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>>> switchVia =
 282                     ecmpSpg.getAllLearnedSwitchesAndVia();
 283             for (Integer itrIdx : switchVia.keySet()) {
 284                 HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>> swViaMap =
 285                         switchVia.get(itrIdx);
 286                 for (DeviceId targetSw : swViaMap.keySet()) {
 287                     DeviceId destSw = sw.id();
 288                     Set<ArrayList<DeviceId>> subLinks =
 289                             computeLinks(targetSw, destSw, swViaMap);
 290                     for (ArrayList<DeviceId> alink: subLinks) {
 291                         if ((alink.get(0).equals(linkFail.src().deviceId()) &&
 292                                 alink.get(1).equals(linkFail.dst().deviceId()))
 293                                 ||
 294                              (alink.get(0).equals(linkFail.dst().deviceId()) &&
 295                                      alink.get(1).equals(linkFail.src().deviceId()))) {
 296                             log.debug("Impacted route:{}->{}", targetSw, destSw);
 297                             ArrayList<DeviceId> aRoute = new ArrayList<>();
 298                             aRoute.add(targetSw);
 299                             aRoute.add(destSw);
 300                             routes.add(aRoute);
 301                             break;
 302                         }
 303                     }
 304                 }
 305             }
 306
 307         }
 308
 309         return routes;
 310     }
 311
 312     private Set<ArrayList<DeviceId>> computeRouteChange() {
 313
 314         Set<ArrayList<DeviceId>> routes = new HashSet<>();
 315
 316         for (Device sw : srManager.deviceService.getDevices()) {
 317             log.debug("Computing the impacted routes for device {}",
 318                       sw.id());
 319             if (!srManager.mastershipService.isLocalMaster(sw.id())) {
 320                 log.debug("No mastership for {} and skip route optimization",
 321                           sw.id());
 322                 continue;
 323             }
 324
 325             log.trace("link of {} - ", sw.id());
 326             for (Link link: srManager.linkService.getDeviceLinks(sw.id())) {
 327                 log.trace("{} -> {} ", link.src().deviceId(), link.dst().deviceId());
 328             }
 329
 330             log.debug("Checking route change for switch {}", sw.id());
 331             ECMPShortestPathGraph ecmpSpg = currentEcmpSpgMap.get(sw.id());
 332             if (ecmpSpg == null) {
 333                 log.debug("No existing ECMP graph for device {}", sw.id());
 334                 ArrayList<DeviceId> route = new ArrayList<>();
 335                 route.add(sw.id());
 336                 routes.add(route);
 337                 continue;
 338             }
 339             ECMPShortestPathGraph newEcmpSpg = updatedEcmpSpgMap.get(sw.id());
 340             //currentEcmpSpgMap.put(sw.id(), newEcmpSpg);
 341             HashMap<Integer, HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>>> switchVia =
 342                     ecmpSpg.getAllLearnedSwitchesAndVia();
 343             HashMap<Integer, HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>>> switchViaUpdated =
 344                     newEcmpSpg.getAllLearnedSwitchesAndVia();
 345
 346             for (Integer itrIdx : switchViaUpdated.keySet()) {
 347                 HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>> swViaMapUpdated =
 348                         switchViaUpdated.get(itrIdx);
 349                 for (DeviceId srcSw : swViaMapUpdated.keySet()) {
 350                     ArrayList<ArrayList<DeviceId>> viaUpdated = swViaMapUpdated.get(srcSw);
 351                     ArrayList<ArrayList<DeviceId>> via = getVia(switchVia, srcSw);
 352                     if ((via == null) || !viaUpdated.equals(via)) {
 353                         log.debug("Impacted route:{}->{}", srcSw, sw.id());
 354                         ArrayList<DeviceId> route = new ArrayList<>();
 355                         route.add(srcSw);
 356                         route.add(sw.id());
 357                         routes.add(route);
 358                     }
 359                 }
 360             }
 361         }
 362
 363         for (ArrayList<DeviceId> link: routes) {
 364             log.trace("Route changes - ");
 365             if (link.size() == 1) {
 366                 log.trace(" : {} - all", link.get(0));
 367             } else {
 368                 log.trace(" : {} - {}", link.get(0), link.get(1));
 369             }
 370         }
 371
 372         return routes;
 373     }
 374
 375     private ArrayList<ArrayList<DeviceId>> getVia(HashMap<Integer, HashMap<DeviceId,
 376             ArrayList<ArrayList<DeviceId>>>> switchVia, DeviceId srcSw) {
 377         for (Integer itrIdx : switchVia.keySet()) {
 378             HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>> swViaMap =
 379                     switchVia.get(itrIdx);
 380             if (swViaMap.get(srcSw) == null) {
 381                 continue;
 382             } else {
 383                 return swViaMap.get(srcSw);
 384             }
 385         }
 386
 387         return null;
 388     }
 389
 390     private Set<ArrayList<DeviceId>> computeLinks(DeviceId src,
 391                                                   DeviceId dst,
 392                        HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>> viaMap) {
 393         Set<ArrayList<DeviceId>> subLinks = Sets.newHashSet();
 394         for (ArrayList<DeviceId> via : viaMap.get(src)) {
 395             DeviceId linkSrc = src;
 396             DeviceId linkDst = dst;
 397             for (DeviceId viaDevice: via) {
 398                 ArrayList<DeviceId> link = new ArrayList<>();
 399                 linkDst = viaDevice;
 400                 link.add(linkSrc);
 401                 link.add(linkDst);
 402                 subLinks.add(link);
 403                 linkSrc = viaDevice;
 404             }
 405             ArrayList<DeviceId> link = new ArrayList<>();
 406             link.add(linkSrc);
 407             link.add(dst);
 408             subLinks.add(link);
 409         }
 410
 411         return subLinks;
 412     }
 413
 414     private boolean populateEcmpRoutingRules(DeviceId destSw,
 415                                              ECMPShortestPathGraph ecmpSPG) {
 416
 417         HashMap<Integer, HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>>> switchVia = ecmpSPG
 418                 .getAllLearnedSwitchesAndVia();
 419         for (Integer itrIdx : switchVia.keySet()) {
 420             HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>> swViaMap = switchVia
 421                     .get(itrIdx);
 422             for (DeviceId targetSw : swViaMap.keySet()) {
 423                 Set<DeviceId> nextHops = new HashSet<>();
 424                 log.debug("** Iter: {} root: {} target: {}", itrIdx, destSw, targetSw);
 425                 for (ArrayList<DeviceId> via : swViaMap.get(targetSw)) {
 426                     if (via.isEmpty()) {
 427                         nextHops.add(destSw);
 428                     } else {
 429                         nextHops.add(via.get(0));
 430                     }
 431                 }
 432                 if (!populateEcmpRoutingRulePartial(targetSw, destSw, nextHops)) {
 433                     return false;
 434                 }
 435             }
 436         }
 437
 438         return true;
 439     }
 440
 441     private boolean populateEcmpRoutingRulePartial(DeviceId targetSw,
 442                                                    DeviceId destSw,
 443                                                    Set<DeviceId> nextHops) {
 444         boolean result;
 445
 446         if (nextHops.isEmpty()) {
 447             nextHops.add(destSw);
 448         }
 449
 450         // If both target switch and dest switch are edge routers, then set IP
 451         // rule for both subnet and router IP.
 452         if (config.isEdgeDevice(targetSw) && config.isEdgeDevice(destSw)) {
 453             Set<Ip4Prefix> subnets = config.getSubnets(destSw);
 454             log.debug("* populateEcmpRoutingRulePartial in device {} towards {} for subnets {}",
 455                     targetSw, destSw, subnets);
 456             result = rulePopulator.populateIpRuleForSubnet(targetSw,
 457                                                            subnets,
 458                                                            destSw,
 459                                                            nextHops);
 460             if (!result) {
 461                 return false;
 462             }
 463
 464             Ip4Address routerIp = config.getRouterIp(destSw);
 465             IpPrefix routerIpPrefix = IpPrefix.valueOf(routerIp, IpPrefix.MAX_INET_MASK_LENGTH);
 466             log.debug("* populateEcmpRoutingRulePartial in device {} towards {} for router IP {}",
 467                     targetSw, destSw, routerIpPrefix);
 468             result = rulePopulator.populateIpRuleForRouter(targetSw, routerIpPrefix, destSw, nextHops);
 469             if (!result) {
 470                 return false;
 471             }
 472
 473         // If the target switch is an edge router, then set IP rules for the router IP.
 474         } else if (config.isEdgeDevice(targetSw)) {
 475             Ip4Address routerIp = config.getRouterIp(destSw);
 476             IpPrefix routerIpPrefix = IpPrefix.valueOf(routerIp, IpPrefix.MAX_INET_MASK_LENGTH);
 477             log.debug("* populateEcmpRoutingRulePartial in device {} towards {} for router IP {}",
 478                     targetSw, destSw, routerIpPrefix);
 479             result = rulePopulator.populateIpRuleForRouter(targetSw, routerIpPrefix, destSw, nextHops);
 480             if (!result) {
 481                 return false;
 482             }
 483         }
 484
 485         // Populates MPLS rules to all routers
 486         log.debug("* populateEcmpRoutingRulePartial in device{} towards {} for all MPLS rules",
 487                 targetSw, destSw);
 488         result = rulePopulator.populateMplsRule(targetSw, destSw, nextHops);
 489         if (!result) {
 490             return false;
 491         }
 492
 493         return true;
 494     }
 495
 496     /**
 497      * Populates filtering rules for permitting Router DstMac and VLAN.
 498      *
 499      * @param deviceId Switch ID to set the rules
 500      */
 501     public void populatePortAddressingRules(DeviceId deviceId) {
 502         rulePopulator.populateRouterMacVlanFilters(deviceId);
 503         rulePopulator.populateRouterIpPunts(deviceId);
 504     }
 505
 506     /**
 507      * Start the flow rule population process if it was never started. The
 508      * process finishes successfully when all flow rules are set and stops with
 509      * ABORTED status when any groups required for flows is not set yet.
 510      */
 511     public void startPopulationProcess() {
 512         statusLock.lock();
 513         try {
 514             if (populationStatus == Status.IDLE
 515                     || populationStatus == Status.SUCCEEDED
 516                     || populationStatus == Status.ABORTED) {
 517                 populationStatus = Status.STARTED;
 518                 populateAllRoutingRules();
 519             } else {
 520                 log.warn("Not initiating startPopulationProcess as populationStatus is {}",
 521                          populationStatus);
 522             }
 523         } finally {
 524             statusLock.unlock();
 525         }
 526     }
 527
 528     /**
 529      * Resume the flow rule population process if it was aborted for any reason.
 530      * Mostly the process is aborted when the groups required are not set yet.
 531      *  XXX is this called?
 532      *
 533      */
 534     public void resumePopulationProcess() {
 535         statusLock.lock();
 536         try {
 537             if (populationStatus == Status.ABORTED) {
 538                 populationStatus = Status.STARTED;
 539                 // TODO: we need to restart from the point aborted instead of
 540                 // restarting.
 541                 populateAllRoutingRules();
 542             }
 543         } finally {
 544             statusLock.unlock();
 545         }
 546     }
 547 }