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.segmentrouting.config.DeviceConfigNotFoundException;
  27 import org.onosproject.segmentrouting.config.DeviceConfiguration;
  28 import org.slf4j.Logger;
  29 import org.slf4j.LoggerFactory;
  30
  31 import java.util.ArrayList;
  32 import java.util.HashMap;
  33 import java.util.HashSet;
  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.isLocalMaster(sw.id())) {
 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.isLocalMaster(sw.id())) {
 150                     continue;
 151                 }
 152                 ECMPShortestPathGraph ecmpSpgUpdated =
 153                         new ECMPShortestPathGraph(sw.id(), srManager);
 154                 updatedEcmpSpgMap.put(sw.id(), ecmpSpgUpdated);
 155             }
 156
 157             log.info("Starts rule population from link change");
 158
 159             Set<ArrayList<DeviceId>> routeChanges;
 160             log.trace("populateRoutingRulesForLinkStatusChange: "
 161                     + "populationStatus is STARTED");
 162             populationStatus = Status.STARTED;
 163             if (linkFail == null) {
 164                 // Compare all routes of existing ECMP SPG with the new ones
 165                 routeChanges = computeRouteChange();
 166             } else {
 167                 // Compare existing ECMP SPG only with the link removed
 168                 routeChanges = computeDamagedRoutes(linkFail);
 169             }
 170
 171             if (routeChanges.isEmpty()) {
 172                 log.info("No route changes for the link status change");
 173                 log.debug("populateRoutingRulesForLinkStatusChange: populationStatus is SUCCEEDED");
 174                 populationStatus = Status.SUCCEEDED;
 175                 return true;
 176             }
 177
 178             if (repopulateRoutingRulesForRoutes(routeChanges)) {
 179                 log.debug("populateRoutingRulesForLinkStatusChange: populationStatus is SUCCEEDED");
 180                 populationStatus = Status.SUCCEEDED;
 181                 log.info("Complete to repopulate the rules. # of rules populated : {}",
 182                         rulePopulator.getCounter());
 183                 return true;
 184             } else {
 185                 log.debug("populateRoutingRulesForLinkStatusChange: populationStatus is ABORTED");
 186                 populationStatus = Status.ABORTED;
 187                 log.warn("Failed to repopulate the rules.");
 188                 return false;
 189             }
 190         } finally {
 191             statusLock.unlock();
 192         }
 193     }
 194
 195     private boolean repopulateRoutingRulesForRoutes(Set<ArrayList<DeviceId>> routes) {
 196         rulePopulator.resetCounter();
 197         HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>> routesBydevice =
 198                 new HashMap<>();
 199         for (ArrayList<DeviceId> link: routes) {
 200             // When only the source device is defined, reinstall routes to all other devices
 201             if (link.size() == 1) {
 202                 log.trace("repopulateRoutingRulesForRoutes: running ECMP graph for device {}", link.get(0));
 203                 ECMPShortestPathGraph ecmpSpg = new ECMPShortestPathGraph(link.get(0), srManager);
 204                 if (populateEcmpRoutingRules(link.get(0), ecmpSpg)) {
 205                     log.debug("Populating flow rules from {} to all is successful",
 206                               link.get(0));
 207                     currentEcmpSpgMap.put(link.get(0), ecmpSpg);
 208                 } else {
 209                     log.warn("Failed to populate the flow rules from {} to all", link.get(0));
 210                     return false;
 211                 }
 212             } else {
 213                 ArrayList<ArrayList<DeviceId>> deviceRoutes =
 214                         routesBydevice.get(link.get(1));
 215                 if (deviceRoutes == null) {
 216                     deviceRoutes = new ArrayList<>();
 217                     routesBydevice.put(link.get(1), deviceRoutes);
 218                 }
 219                 deviceRoutes.add(link);
 220             }
 221         }
 222
 223         for (DeviceId impactedDevice : routesBydevice.keySet()) {
 224             ArrayList<ArrayList<DeviceId>> deviceRoutes =
 225                     routesBydevice.get(impactedDevice);
 226             for (ArrayList<DeviceId> link: deviceRoutes) {
 227                 log.debug("repopulate RoutingRules For Routes {} -> {}",
 228                           link.get(0), link.get(1));
 229                 DeviceId src = link.get(0);
 230                 DeviceId dst = link.get(1);
 231                 ECMPShortestPathGraph ecmpSpg = updatedEcmpSpgMap.get(dst);
 232                 HashMap<Integer, HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>>> switchVia =
 233                         ecmpSpg.getAllLearnedSwitchesAndVia();
 234                 for (Integer itrIdx : switchVia.keySet()) {
 235                     HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>> swViaMap =
 236                             switchVia.get(itrIdx);
 237                     for (DeviceId targetSw : swViaMap.keySet()) {
 238                         if (!targetSw.equals(src)) {
 239                             continue;
 240                         }
 241                         Set<DeviceId> nextHops = new HashSet<>();
 242                         for (ArrayList<DeviceId> via : swViaMap.get(targetSw)) {
 243                             if (via.isEmpty()) {
 244                                 nextHops.add(dst);
 245                             } else {
 246                                 nextHops.add(via.get(0));
 247                             }
 248                         }
 249                         if (!populateEcmpRoutingRulePartial(targetSw, dst, nextHops)) {
 250                             return false;
 251                         }
 252                         log.debug("Populating flow rules from {} to {} is successful",
 253                                   targetSw, dst);
 254                     }
 255                 }
 256                 //currentEcmpSpgMap.put(dst, ecmpSpg);
 257             }
 258             //Only if all the flows for all impacted routes to a
 259             //specific target are pushed successfully, update the
 260             //ECMP graph for that target. (Or else the next event
 261             //would not see any changes in the ECMP graphs)
 262             currentEcmpSpgMap.put(impactedDevice,
 263                                   updatedEcmpSpgMap.get(impactedDevice));
 264         }
 265         return true;
 266     }
 267
 268     private Set<ArrayList<DeviceId>> computeDamagedRoutes(Link linkFail) {
 269
 270         Set<ArrayList<DeviceId>> routes = new HashSet<>();
 271
 272         for (Device sw : srManager.deviceService.getDevices()) {
 273             log.debug("Computing the impacted routes for device {} due to link fail",
 274                       sw.id());
 275             if (!srManager.mastershipService.isLocalMaster(sw.id())) {
 276                 continue;
 277             }
 278             ECMPShortestPathGraph ecmpSpg = currentEcmpSpgMap.get(sw.id());
 279             if (ecmpSpg == null) {
 280                 log.error("No existing ECMP graph for switch {}", sw.id());
 281                 continue;
 282             }
 283             HashMap<Integer, HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>>> switchVia =
 284                     ecmpSpg.getAllLearnedSwitchesAndVia();
 285             for (Integer itrIdx : switchVia.keySet()) {
 286                 HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>> swViaMap =
 287                         switchVia.get(itrIdx);
 288                 for (DeviceId targetSw : swViaMap.keySet()) {
 289                     DeviceId destSw = sw.id();
 290                     Set<ArrayList<DeviceId>> subLinks =
 291                             computeLinks(targetSw, destSw, swViaMap);
 292                     for (ArrayList<DeviceId> alink: subLinks) {
 293                         if ((alink.get(0).equals(linkFail.src().deviceId()) &&
 294                                 alink.get(1).equals(linkFail.dst().deviceId()))
 295                                 ||
 296                              (alink.get(0).equals(linkFail.dst().deviceId()) &&
 297                                      alink.get(1).equals(linkFail.src().deviceId()))) {
 298                             log.debug("Impacted route:{}->{}", targetSw, destSw);
 299                             ArrayList<DeviceId> aRoute = new ArrayList<>();
 300                             aRoute.add(targetSw);
 301                             aRoute.add(destSw);
 302                             routes.add(aRoute);
 303                             break;
 304                         }
 305                     }
 306                 }
 307             }
 308
 309         }
 310
 311         return routes;
 312     }
 313
 314     private Set<ArrayList<DeviceId>> computeRouteChange() {
 315
 316         Set<ArrayList<DeviceId>> routes = new HashSet<>();
 317
 318         for (Device sw : srManager.deviceService.getDevices()) {
 319             log.debug("Computing the impacted routes for device {}",
 320                       sw.id());
 321             if (!srManager.mastershipService.isLocalMaster(sw.id())) {
 322                 log.debug("No mastership for {} and skip route optimization",
 323                           sw.id());
 324                 continue;
 325             }
 326
 327             log.trace("link of {} - ", sw.id());
 328             for (Link link: srManager.linkService.getDeviceLinks(sw.id())) {
 329                 log.trace("{} -> {} ", link.src().deviceId(), link.dst().deviceId());
 330             }
 331
 332             log.debug("Checking route change for switch {}", sw.id());
 333             ECMPShortestPathGraph ecmpSpg = currentEcmpSpgMap.get(sw.id());
 334             if (ecmpSpg == null) {
 335                 log.debug("No existing ECMP graph for device {}", sw.id());
 336                 ArrayList<DeviceId> route = new ArrayList<>();
 337                 route.add(sw.id());
 338                 routes.add(route);
 339                 continue;
 340             }
 341             ECMPShortestPathGraph newEcmpSpg = updatedEcmpSpgMap.get(sw.id());
 342             //currentEcmpSpgMap.put(sw.id(), newEcmpSpg);
 343             HashMap<Integer, HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>>> switchVia =
 344                     ecmpSpg.getAllLearnedSwitchesAndVia();
 345             HashMap<Integer, HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>>> switchViaUpdated =
 346                     newEcmpSpg.getAllLearnedSwitchesAndVia();
 347
 348             for (Integer itrIdx : switchViaUpdated.keySet()) {
 349                 HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>> swViaMapUpdated =
 350                         switchViaUpdated.get(itrIdx);
 351                 for (DeviceId srcSw : swViaMapUpdated.keySet()) {
 352                     ArrayList<ArrayList<DeviceId>> viaUpdated = swViaMapUpdated.get(srcSw);
 353                     ArrayList<ArrayList<DeviceId>> via = getVia(switchVia, srcSw);
 354                     if ((via == null) || !viaUpdated.equals(via)) {
 355                         log.debug("Impacted route:{}->{}", srcSw, sw.id());
 356                         ArrayList<DeviceId> route = new ArrayList<>();
 357                         route.add(srcSw);
 358                         route.add(sw.id());
 359                         routes.add(route);
 360                     }
 361                 }
 362             }
 363         }
 364
 365         for (ArrayList<DeviceId> link: routes) {
 366             log.trace("Route changes - ");
 367             if (link.size() == 1) {
 368                 log.trace(" : {} - all", link.get(0));
 369             } else {
 370                 log.trace(" : {} - {}", link.get(0), link.get(1));
 371             }
 372         }
 373
 374         return routes;
 375     }
 376
 377     private ArrayList<ArrayList<DeviceId>> getVia(HashMap<Integer, HashMap<DeviceId,
 378             ArrayList<ArrayList<DeviceId>>>> switchVia, DeviceId srcSw) {
 379         for (Integer itrIdx : switchVia.keySet()) {
 380             HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>> swViaMap =
 381                     switchVia.get(itrIdx);
 382             if (swViaMap.get(srcSw) == null) {
 383                 continue;
 384             } else {
 385                 return swViaMap.get(srcSw);
 386             }
 387         }
 388
 389         return null;
 390     }
 391
 392     private Set<ArrayList<DeviceId>> computeLinks(DeviceId src,
 393                                                   DeviceId dst,
 394                        HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>> viaMap) {
 395         Set<ArrayList<DeviceId>> subLinks = Sets.newHashSet();
 396         for (ArrayList<DeviceId> via : viaMap.get(src)) {
 397             DeviceId linkSrc = src;
 398             DeviceId linkDst = dst;
 399             for (DeviceId viaDevice: via) {
 400                 ArrayList<DeviceId> link = new ArrayList<>();
 401                 linkDst = viaDevice;
 402                 link.add(linkSrc);
 403                 link.add(linkDst);
 404                 subLinks.add(link);
 405                 linkSrc = viaDevice;
 406             }
 407             ArrayList<DeviceId> link = new ArrayList<>();
 408             link.add(linkSrc);
 409             link.add(dst);
 410             subLinks.add(link);
 411         }
 412
 413         return subLinks;
 414     }
 415
 416     private boolean populateEcmpRoutingRules(DeviceId destSw,
 417                                              ECMPShortestPathGraph ecmpSPG) {
 418
 419         HashMap<Integer, HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>>> switchVia = ecmpSPG
 420                 .getAllLearnedSwitchesAndVia();
 421         for (Integer itrIdx : switchVia.keySet()) {
 422             HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>> swViaMap = switchVia
 423                     .get(itrIdx);
 424             for (DeviceId targetSw : swViaMap.keySet()) {
 425                 Set<DeviceId> nextHops = new HashSet<>();
 426                 log.debug("** Iter: {} root: {} target: {}", itrIdx, destSw, targetSw);
 427                 for (ArrayList<DeviceId> via : swViaMap.get(targetSw)) {
 428                     if (via.isEmpty()) {
 429                         nextHops.add(destSw);
 430                     } else {
 431                         nextHops.add(via.get(0));
 432                     }
 433                 }
 434                 if (!populateEcmpRoutingRulePartial(targetSw, destSw, nextHops)) {
 435                     return false;
 436                 }
 437             }
 438         }
 439
 440         return true;
 441     }
 442
 443     private boolean populateEcmpRoutingRulePartial(DeviceId targetSw,
 444                                                    DeviceId destSw,
 445                                                    Set<DeviceId> nextHops) {
 446         boolean result;
 447
 448         if (nextHops.isEmpty()) {
 449             nextHops.add(destSw);
 450         }
 451         // If both target switch and dest switch are edge routers, then set IP
 452         // rule for both subnet and router IP.
 453         boolean targetIsEdge;
 454         boolean destIsEdge;
 455         Ip4Address destRouterIp;
 456
 457         try {
 458             targetIsEdge = config.isEdgeDevice(targetSw);
 459             destIsEdge = config.isEdgeDevice(destSw);
 460             destRouterIp = config.getRouterIp(destSw);
 461         } catch (DeviceConfigNotFoundException e) {
 462             log.warn(e.getMessage() + " Aborting populateEcmpRoutingRulePartial.");
 463             return false;
 464         }
 465
 466         if (targetIsEdge && destIsEdge) {
 467             Set<Ip4Prefix> subnets = config.getSubnets(destSw);
 468             log.debug("* populateEcmpRoutingRulePartial in device {} towards {} for subnets {}",
 469                       targetSw, destSw, subnets);
 470             result = rulePopulator.populateIpRuleForSubnet(targetSw,
 471                                                            subnets,
 472                                                            destSw,
 473                                                            nextHops);
 474             if (!result) {
 475                 return false;
 476             }
 477
 478             Ip4Address routerIp = destRouterIp;
 479             IpPrefix routerIpPrefix = IpPrefix.valueOf(routerIp, IpPrefix.MAX_INET_MASK_LENGTH);
 480             log.debug("* populateEcmpRoutingRulePartial in device {} towards {} for router IP {}",
 481                       targetSw, destSw, routerIpPrefix);
 482             result = rulePopulator.populateIpRuleForRouter(targetSw, routerIpPrefix, destSw, nextHops);
 483             if (!result) {
 484                 return false;
 485             }
 486
 487         } else if (targetIsEdge) {
 488             // If the target switch is an edge router, then set IP rules for the router IP.
 489             Ip4Address routerIp = destRouterIp;
 490             IpPrefix routerIpPrefix = IpPrefix.valueOf(routerIp, IpPrefix.MAX_INET_MASK_LENGTH);
 491             log.debug("* populateEcmpRoutingRulePartial in device {} towards {} for router IP {}",
 492                       targetSw, destSw, routerIpPrefix);
 493             result = rulePopulator.populateIpRuleForRouter(targetSw, routerIpPrefix, destSw, nextHops);
 494             if (!result) {
 495                 return false;
 496             }
 497         }
 498         // Populates MPLS rules to all routers
 499         log.debug("* populateEcmpRoutingRulePartial in device{} towards {} for all MPLS rules",
 500                 targetSw, destSw);
 501         result = rulePopulator.populateMplsRule(targetSw, destSw, nextHops);
 502         if (!result) {
 503             return false;
 504         }
 505         return true;
 506     }
 507
 508     /**
 509      * Populates filtering rules for permitting Router DstMac and VLAN.
 510      *
 511      * @param deviceId Switch ID to set the rules
 512      */
 513     public void populatePortAddressingRules(DeviceId deviceId) {
 514         rulePopulator.populateRouterMacVlanFilters(deviceId);
 515         rulePopulator.populateRouterIpPunts(deviceId);
 516     }
 517
 518     /**
 519      * Start the flow rule population process if it was never started. The
 520      * process finishes successfully when all flow rules are set and stops with
 521      * ABORTED status when any groups required for flows is not set yet.
 522      */
 523     public void startPopulationProcess() {
 524         statusLock.lock();
 525         try {
 526             if (populationStatus == Status.IDLE
 527                     || populationStatus == Status.SUCCEEDED
 528                     || populationStatus == Status.ABORTED) {
 529                 populationStatus = Status.STARTED;
 530                 populateAllRoutingRules();
 531             } else {
 532                 log.warn("Not initiating startPopulationProcess as populationStatus is {}",
 533                          populationStatus);
 534             }
 535         } finally {
 536             statusLock.unlock();
 537         }
 538     }
 539
 540     /**
 541      * Resume the flow rule population process if it was aborted for any reason.
 542      * Mostly the process is aborted when the groups required are not set yet.
 543      *  XXX is this called?
 544      *
 545      */
 546     public void resumePopulationProcess() {
 547         statusLock.lock();
 548         try {
 549             if (populationStatus == Status.ABORTED) {
 550                 populationStatus = Status.STARTED;
 551                 // TODO: we need to restart from the point aborted instead of
 552                 // restarting.
 553                 populateAllRoutingRules();
 554             }
 555         } finally {
 556             statusLock.unlock();
 557         }
 558     }
 559 }