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