| /* |
| * Copyright 2015-present Open Networking Foundation |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| package org.onosproject.segmentrouting; |
| |
| import com.google.common.base.MoreObjects; |
| import com.google.common.collect.ImmutableMap; |
| import com.google.common.collect.ImmutableMap.Builder; |
| import com.google.common.collect.ImmutableSet; |
| import com.google.common.collect.Lists; |
| import com.google.common.collect.Maps; |
| import com.google.common.collect.Sets; |
| |
| import org.onlab.packet.Ip4Address; |
| import org.onlab.packet.Ip6Address; |
| import org.onlab.packet.IpPrefix; |
| import org.onlab.packet.MacAddress; |
| import org.onlab.packet.VlanId; |
| import org.onosproject.cluster.NodeId; |
| import org.onosproject.net.ConnectPoint; |
| import org.onosproject.net.Device; |
| import org.onosproject.net.DeviceId; |
| import org.onosproject.net.Link; |
| import org.onosproject.net.PortNumber; |
| import org.onosproject.segmentrouting.config.DeviceConfigNotFoundException; |
| import org.onosproject.segmentrouting.config.DeviceConfiguration; |
| import org.onosproject.segmentrouting.grouphandler.DefaultGroupHandler; |
| import org.slf4j.Logger; |
| import org.slf4j.LoggerFactory; |
| |
| import java.time.Instant; |
| import java.util.ArrayList; |
| import java.util.HashMap; |
| import java.util.HashSet; |
| import java.util.Iterator; |
| import java.util.Map; |
| import java.util.Objects; |
| import java.util.Set; |
| import java.util.concurrent.ScheduledExecutorService; |
| import java.util.concurrent.TimeUnit; |
| import java.util.concurrent.locks.Lock; |
| import java.util.concurrent.locks.ReentrantLock; |
| |
| import static com.google.common.base.MoreObjects.toStringHelper; |
| import static com.google.common.base.Preconditions.checkNotNull; |
| import static java.util.concurrent.Executors.newScheduledThreadPool; |
| import static org.onlab.util.Tools.groupedThreads; |
| |
| /** |
| * Default routing handler that is responsible for route computing and |
| * routing rule population. |
| */ |
| public class DefaultRoutingHandler { |
| private static final int MAX_CONSTANT_RETRY_ATTEMPTS = 5; |
| private static final int RETRY_INTERVAL_MS = 250; |
| private static final int RETRY_INTERVAL_SCALE = 1; |
| private static final long STABLITY_THRESHOLD = 10; //secs |
| private static final int UPDATE_INTERVAL = 5; //secs |
| private static Logger log = LoggerFactory.getLogger(DefaultRoutingHandler.class); |
| |
| private SegmentRoutingManager srManager; |
| private RoutingRulePopulator rulePopulator; |
| private HashMap<DeviceId, EcmpShortestPathGraph> currentEcmpSpgMap; |
| private HashMap<DeviceId, EcmpShortestPathGraph> updatedEcmpSpgMap; |
| private DeviceConfiguration config; |
| private final Lock statusLock = new ReentrantLock(); |
| private volatile Status populationStatus; |
| private ScheduledExecutorService executorService |
| = newScheduledThreadPool(1, groupedThreads("retryftr", "retry-%d", log)); |
| private Instant lastRoutingChange; |
| |
| /** |
| * Represents the default routing population status. |
| */ |
| public enum Status { |
| // population process is not started yet. |
| IDLE, |
| |
| // population process started. |
| STARTED, |
| |
| // population process was aborted due to errors, mostly for groups not |
| // found. |
| ABORTED, |
| |
| // population process was finished successfully. |
| SUCCEEDED |
| } |
| |
| /** |
| * Creates a DefaultRoutingHandler object. |
| * |
| * @param srManager SegmentRoutingManager object |
| */ |
| public DefaultRoutingHandler(SegmentRoutingManager srManager) { |
| this.srManager = srManager; |
| this.rulePopulator = checkNotNull(srManager.routingRulePopulator); |
| this.config = checkNotNull(srManager.deviceConfiguration); |
| this.populationStatus = Status.IDLE; |
| this.currentEcmpSpgMap = Maps.newHashMap(); |
| } |
| |
| /** |
| * Returns an immutable copy of the current ECMP shortest-path graph as |
| * computed by this controller instance. |
| * |
| * @return immutable copy of the current ECMP graph |
| */ |
| public ImmutableMap<DeviceId, EcmpShortestPathGraph> getCurrentEmcpSpgMap() { |
| Builder<DeviceId, EcmpShortestPathGraph> builder = ImmutableMap.builder(); |
| currentEcmpSpgMap.entrySet().forEach(entry -> { |
| if (entry.getValue() != null) { |
| builder.put(entry.getKey(), entry.getValue()); |
| } |
| }); |
| return builder.build(); |
| } |
| |
| /** |
| * Acquires the lock used when making routing changes. |
| */ |
| public void acquireRoutingLock() { |
| statusLock.lock(); |
| } |
| |
| /** |
| * Releases the lock used when making routing changes. |
| */ |
| public void releaseRoutingLock() { |
| statusLock.unlock(); |
| } |
| |
| /** |
| * Determines if routing in the network has been stable in the last |
| * STABLITY_THRESHOLD seconds, by comparing the current time to the last |
| * routing change timestamp. |
| * |
| * @return true if stable |
| */ |
| public boolean isRoutingStable() { |
| long last = (long) (lastRoutingChange.toEpochMilli() / 1000.0); |
| long now = (long) (Instant.now().toEpochMilli() / 1000.0); |
| log.trace("Routing stable since {}s", now - last); |
| return (now - last) > STABLITY_THRESHOLD; |
| } |
| |
| |
| ////////////////////////////////////// |
| // Route path handling |
| ////////////////////////////////////// |
| |
| /* The following three methods represent the three major ways in which |
| * route-path handling is triggered in the network |
| * a) due to configuration change |
| * b) due to route-added event |
| * c) due to change in the topology |
| */ |
| |
| /** |
| * Populates all routing rules to all switches. Typically triggered at |
| * startup or after a configuration event. |
| */ |
| public void populateAllRoutingRules() { |
| lastRoutingChange = Instant.now(); |
| statusLock.lock(); |
| try { |
| if (populationStatus == Status.STARTED) { |
| log.warn("Previous rule population is not finished. Cannot" |
| + " proceed with populateAllRoutingRules"); |
| return; |
| } |
| |
| populationStatus = Status.STARTED; |
| rulePopulator.resetCounter(); |
| log.info("Starting to populate all routing rules"); |
| log.debug("populateAllRoutingRules: populationStatus is STARTED"); |
| |
| // take a snapshot of the topology |
| updatedEcmpSpgMap = new HashMap<>(); |
| Set<EdgePair> edgePairs = new HashSet<>(); |
| Set<ArrayList<DeviceId>> routeChanges = new HashSet<>(); |
| for (DeviceId dstSw : srManager.deviceConfiguration.getRouters()) { |
| EcmpShortestPathGraph ecmpSpgUpdated = |
| new EcmpShortestPathGraph(dstSw, srManager); |
| updatedEcmpSpgMap.put(dstSw, ecmpSpgUpdated); |
| DeviceId pairDev = getPairDev(dstSw); |
| if (pairDev != null) { |
| // pairDev may not be available yet, but we still need to add |
| ecmpSpgUpdated = new EcmpShortestPathGraph(pairDev, srManager); |
| updatedEcmpSpgMap.put(pairDev, ecmpSpgUpdated); |
| edgePairs.add(new EdgePair(dstSw, pairDev)); |
| } |
| DeviceId ret = shouldHandleRouting(dstSw); |
| if (ret == null) { |
| continue; |
| } |
| Set<DeviceId> devsToProcess = Sets.newHashSet(dstSw, ret); |
| // To do a full reroute, assume all routes have changed |
| for (DeviceId dev : devsToProcess) { |
| for (DeviceId targetSw : srManager.deviceConfiguration.getRouters()) { |
| if (targetSw.equals(dev)) { |
| continue; |
| } |
| routeChanges.add(Lists.newArrayList(targetSw, dev)); |
| } |
| } |
| } |
| |
| if (!redoRouting(routeChanges, edgePairs, null)) { |
| log.debug("populateAllRoutingRules: populationStatus is ABORTED"); |
| populationStatus = Status.ABORTED; |
| log.warn("Failed to repopulate all routing rules."); |
| return; |
| } |
| |
| log.debug("populateAllRoutingRules: populationStatus is SUCCEEDED"); |
| populationStatus = Status.SUCCEEDED; |
| log.info("Completed all routing rule population. Total # of rules pushed : {}", |
| rulePopulator.getCounter()); |
| return; |
| } finally { |
| statusLock.unlock(); |
| } |
| } |
| |
| /** |
| * Populate rules from all other edge devices to the connect-point(s) |
| * specified for the given subnets. |
| * |
| * @param cpts connect point(s) of the subnets being added |
| * @param subnets subnets being added |
| */ |
| // XXX refactor |
| protected void populateSubnet(Set<ConnectPoint> cpts, Set<IpPrefix> subnets) { |
| if (cpts == null || cpts.size() < 1 || cpts.size() > 2) { |
| log.warn("Skipping populateSubnet due to illegal size of connect points. {}", cpts); |
| return; |
| } |
| |
| lastRoutingChange = Instant.now(); |
| statusLock.lock(); |
| try { |
| if (populationStatus == Status.STARTED) { |
| log.warn("Previous rule population is not finished. Cannot" |
| + " proceed with routing rules for added routes"); |
| return; |
| } |
| populationStatus = Status.STARTED; |
| rulePopulator.resetCounter(); |
| log.info("Starting to populate routing rules for added routes, subnets={}, cpts={}", |
| subnets, cpts); |
| // Take snapshots of the topology |
| updatedEcmpSpgMap = new HashMap<>(); |
| Set<EdgePair> edgePairs = new HashSet<>(); |
| Set<ArrayList<DeviceId>> routeChanges = new HashSet<>(); |
| boolean handleRouting = false; |
| |
| if (cpts.size() == 2) { |
| // ensure connect points are edge-pairs |
| Iterator<ConnectPoint> iter = cpts.iterator(); |
| DeviceId dev1 = iter.next().deviceId(); |
| DeviceId pairDev = getPairDev(dev1); |
| if (iter.next().deviceId().equals(pairDev)) { |
| edgePairs.add(new EdgePair(dev1, pairDev)); |
| } else { |
| log.warn("Connectpoints {} for subnets {} not on " |
| + "pair-devices.. aborting populateSubnet", cpts, subnets); |
| populationStatus = Status.ABORTED; |
| return; |
| } |
| for (ConnectPoint cp : cpts) { |
| EcmpShortestPathGraph ecmpSpgUpdated = |
| new EcmpShortestPathGraph(cp.deviceId(), srManager); |
| updatedEcmpSpgMap.put(cp.deviceId(), ecmpSpgUpdated); |
| DeviceId retId = shouldHandleRouting(cp.deviceId()); |
| if (retId == null) { |
| continue; |
| } |
| handleRouting = true; |
| } |
| } else { |
| // single connect point |
| DeviceId dstSw = cpts.iterator().next().deviceId(); |
| EcmpShortestPathGraph ecmpSpgUpdated = |
| new EcmpShortestPathGraph(dstSw, srManager); |
| updatedEcmpSpgMap.put(dstSw, ecmpSpgUpdated); |
| if (srManager.mastershipService.isLocalMaster(dstSw)) { |
| handleRouting = true; |
| } |
| } |
| |
| if (!handleRouting) { |
| log.debug("This instance is not handling ecmp routing to the " |
| + "connectPoint(s) {}", cpts); |
| populationStatus = Status.ABORTED; |
| return; |
| } |
| |
| // if it gets here, this instance should handle routing for the |
| // connectpoint(s). Assume all route-paths have to be updated to |
| // the connectpoint(s) with the following exceptions |
| // 1. if target is non-edge no need for routing rules |
| // 2. if target is one of the connectpoints |
| for (ConnectPoint cp : cpts) { |
| DeviceId dstSw = cp.deviceId(); |
| for (Device targetSw : srManager.deviceService.getDevices()) { |
| boolean isEdge = false; |
| try { |
| isEdge = config.isEdgeDevice(targetSw.id()); |
| } catch (DeviceConfigNotFoundException e) { |
| log.warn(e.getMessage() + "aborting populateSubnet"); |
| populationStatus = Status.ABORTED; |
| return; |
| } |
| if (dstSw.equals(targetSw.id()) || !isEdge || |
| (cpts.size() == 2 && |
| targetSw.id().equals(getPairDev(dstSw)))) { |
| continue; |
| } |
| routeChanges.add(Lists.newArrayList(targetSw.id(), dstSw)); |
| } |
| } |
| |
| if (!redoRouting(routeChanges, edgePairs, subnets)) { |
| log.debug("populateSubnet: populationStatus is ABORTED"); |
| populationStatus = Status.ABORTED; |
| log.warn("Failed to repopulate the rules for subnet."); |
| return; |
| } |
| |
| log.debug("populateSubnet: populationStatus is SUCCEEDED"); |
| populationStatus = Status.SUCCEEDED; |
| log.info("Completed subnet population. Total # of rules pushed : {}", |
| rulePopulator.getCounter()); |
| return; |
| |
| } finally { |
| statusLock.unlock(); |
| } |
| } |
| |
| /** |
| * Populates the routing rules or makes hash group changes according to the |
| * route-path changes due to link failure, switch failure or link up. This |
| * method should only be called for one of these three possible event-types. |
| * Note that when a switch goes away, all of its links fail as well, |
| * but this is handled as a single switch removal event. |
| * |
| * @param linkDown the single failed link, or null for other conditions |
| * such as link-up or a removed switch |
| * @param linkUp the single link up, or null for other conditions such as |
| * link-down or a removed switch |
| * @param switchDown the removed switch, or null for other conditions such as |
| * link-down or link-up |
| */ // refactor |
| public void populateRoutingRulesForLinkStatusChange(Link linkDown, |
| Link linkUp, |
| DeviceId switchDown) { |
| if ((linkDown != null && (linkUp != null || switchDown != null)) || |
| (linkUp != null && (linkDown != null || switchDown != null)) || |
| (switchDown != null && (linkUp != null || linkDown != null))) { |
| log.warn("Only one event can be handled for link status change .. aborting"); |
| return; |
| } |
| lastRoutingChange = Instant.now(); |
| executorService.schedule(new UpdateMaps(), UPDATE_INTERVAL, |
| TimeUnit.SECONDS); |
| statusLock.lock(); |
| try { |
| |
| if (populationStatus == Status.STARTED) { |
| log.warn("Previous rule population is not finished. Cannot" |
| + " proceeed with routingRules for Link Status change"); |
| return; |
| } |
| |
| // Take snapshots of the topology |
| updatedEcmpSpgMap = new HashMap<>(); |
| Set<EdgePair> edgePairs = new HashSet<>(); |
| for (Device sw : srManager.deviceService.getDevices()) { |
| EcmpShortestPathGraph ecmpSpgUpdated = |
| new EcmpShortestPathGraph(sw.id(), srManager); |
| updatedEcmpSpgMap.put(sw.id(), ecmpSpgUpdated); |
| DeviceId pairDev = getPairDev(sw.id()); |
| if (pairDev != null) { |
| // pairDev may not be available yet, but we still need to add |
| ecmpSpgUpdated = new EcmpShortestPathGraph(pairDev, srManager); |
| updatedEcmpSpgMap.put(pairDev, ecmpSpgUpdated); |
| edgePairs.add(new EdgePair(sw.id(), pairDev)); |
| } |
| } |
| |
| log.info("Starting to populate routing rules from link status change"); |
| |
| Set<ArrayList<DeviceId>> routeChanges; |
| log.debug("populateRoutingRulesForLinkStatusChange: " |
| + "populationStatus is STARTED"); |
| populationStatus = Status.STARTED; |
| rulePopulator.resetCounter(); |
| // try optimized re-routing |
| if (linkDown == null) { |
| // either a linkUp or a switchDown - compute all route changes by |
| // comparing all routes of existing ECMP SPG to new ECMP SPG |
| routeChanges = computeRouteChange(); |
| |
| // deal with linkUp of a seen-before link |
| if (linkUp != null && srManager.linkHandler.isSeenLink(linkUp)) { |
| if (!srManager.linkHandler.isBidirectional(linkUp)) { |
| log.warn("Not a bidirectional link yet .. not " |
| + "processing link {}", linkUp); |
| srManager.linkHandler.updateSeenLink(linkUp, true); |
| populationStatus = Status.ABORTED; |
| return; |
| } |
| // link previously seen before |
| // do hash-bucket changes instead of a re-route |
| processHashGroupChange(routeChanges, false, null); |
| // clear out routesChanges so a re-route is not attempted |
| routeChanges = ImmutableSet.of(); |
| } |
| // for a linkUp of a never-seen-before link |
| // let it fall through to a reroute of the routeChanges |
| |
| // now that we are past the check for a previously seen link |
| // it is safe to update the store for the linkUp |
| if (linkUp != null) { |
| srManager.linkHandler.updateSeenLink(linkUp, true); |
| } |
| |
| //deal with switchDown |
| if (switchDown != null) { |
| processHashGroupChange(routeChanges, true, switchDown); |
| // clear out routesChanges so a re-route is not attempted |
| routeChanges = ImmutableSet.of(); |
| } |
| } else { |
| // link has gone down |
| // Compare existing ECMP SPG only with the link that went down |
| routeChanges = computeDamagedRoutes(linkDown); |
| if (routeChanges != null) { |
| processHashGroupChange(routeChanges, true, null); |
| // clear out routesChanges so a re-route is not attempted |
| routeChanges = ImmutableSet.of(); |
| } |
| } |
| |
| // do full re-routing if optimized routing returns null routeChanges |
| if (routeChanges == null) { |
| log.info("Optimized routing failed... opting for full reroute"); |
| populationStatus = Status.ABORTED; |
| populateAllRoutingRules(); |
| return; |
| } |
| |
| if (routeChanges.isEmpty()) { |
| log.info("No re-route attempted for the link status change"); |
| log.debug("populateRoutingRulesForLinkStatusChange: populationStatus is SUCCEEDED"); |
| populationStatus = Status.SUCCEEDED; |
| return; |
| } |
| |
| // reroute of routeChanges |
| if (redoRouting(routeChanges, edgePairs, null)) { |
| log.debug("populateRoutingRulesForLinkStatusChange: populationStatus is SUCCEEDED"); |
| populationStatus = Status.SUCCEEDED; |
| log.info("Completed repopulation of rules for link-status change." |
| + " # of rules populated : {}", rulePopulator.getCounter()); |
| return; |
| } else { |
| log.debug("populateRoutingRulesForLinkStatusChange: populationStatus is ABORTED"); |
| populationStatus = Status.ABORTED; |
| log.warn("Failed to repopulate the rules for link status change."); |
| return; |
| } |
| } finally { |
| statusLock.unlock(); |
| } |
| } |
| |
| |
| /** |
| * Processes a set a route-path changes by reprogramming routing rules and |
| * creating new hash-groups or editing them if necessary. This method also |
| * determines the next-hops for the route-path from the src-switch (target) |
| * of the path towards the dst-switch of the path. |
| * |
| * @param routeChanges a set of route-path changes, where each route-path is |
| * a list with its first element the src-switch (target) |
| * of the path, and the second element the dst-switch of |
| * the path. |
| * @param edgePairs a set of edge-switches that are paired by configuration |
| * @param subnets a set of prefixes that need to be populated in the routing |
| * table of the target switch in the route-path. Can be null, |
| * in which case all the prefixes belonging to the dst-switch |
| * will be populated in the target switch |
| * @return true if successful in repopulating all routes |
| */ |
| private boolean redoRouting(Set<ArrayList<DeviceId>> routeChanges, |
| Set<EdgePair> edgePairs, Set<IpPrefix> subnets) { |
| // first make every entry two-elements |
| Set<ArrayList<DeviceId>> changedRoutes = new HashSet<>(); |
| for (ArrayList<DeviceId> route : routeChanges) { |
| if (route.size() == 1) { |
| DeviceId dstSw = route.get(0); |
| EcmpShortestPathGraph ec = updatedEcmpSpgMap.get(dstSw); |
| if (ec == null) { |
| log.warn("No graph found for {} .. aborting redoRouting", dstSw); |
| return false; |
| } |
| ec.getAllLearnedSwitchesAndVia().keySet().forEach(key -> { |
| ec.getAllLearnedSwitchesAndVia().get(key).keySet().forEach(target -> { |
| changedRoutes.add(Lists.newArrayList(target, dstSw)); |
| }); |
| }); |
| } else { |
| DeviceId targetSw = route.get(0); |
| DeviceId dstSw = route.get(1); |
| changedRoutes.add(Lists.newArrayList(targetSw, dstSw)); |
| } |
| } |
| |
| // now process changedRoutes according to edgePairs |
| if (!redoRoutingEdgePairs(edgePairs, subnets, changedRoutes)) { |
| return false; //abort routing and fail fast |
| } |
| |
| // whatever is left in changedRoutes is now processed for individual dsts. |
| if (!redoRoutingIndividualDests(subnets, changedRoutes)) { |
| return false; //abort routing and fail fast |
| } |
| |
| // update ecmpSPG for all edge-pairs |
| for (EdgePair ep : edgePairs) { |
| currentEcmpSpgMap.put(ep.dev1, updatedEcmpSpgMap.get(ep.dev1)); |
| currentEcmpSpgMap.put(ep.dev2, updatedEcmpSpgMap.get(ep.dev2)); |
| log.debug("Updating ECMPspg for edge-pair:{}-{}", ep.dev1, ep.dev2); |
| } |
| return true; |
| } |
| |
| /** |
| * Programs targetSw in the changedRoutes for given prefixes reachable by |
| * an edgePair. If no prefixes are given, the method will use configured |
| * subnets/prefixes. If some configured subnets belong only to a specific |
| * destination in the edgePair, then the target switch will be programmed |
| * only to that destination. |
| * |
| * @param edgePairs set of edge-pairs for which target will be programmed |
| * @param subnets a set of prefixes that need to be populated in the routing |
| * table of the target switch in the changedRoutes. Can be null, |
| * in which case all the configured prefixes belonging to the |
| * paired switches will be populated in the target switch |
| * @param changedRoutes a set of route-path changes, where each route-path is |
| * a list with its first element the src-switch (target) |
| * of the path, and the second element the dst-switch of |
| * the path. |
| * @return true if successful |
| */ |
| private boolean redoRoutingEdgePairs(Set<EdgePair> edgePairs, |
| Set<IpPrefix> subnets, |
| Set<ArrayList<DeviceId>> changedRoutes) { |
| for (EdgePair ep : edgePairs) { |
| // temp store for a target's changedRoutes to this edge-pair |
| Map<DeviceId, Set<ArrayList<DeviceId>>> targetRoutes = new HashMap<>(); |
| Iterator<ArrayList<DeviceId>> i = changedRoutes.iterator(); |
| while (i.hasNext()) { |
| ArrayList<DeviceId> route = i.next(); |
| DeviceId dstSw = route.get(1); |
| if (ep.includes(dstSw)) { |
| // routeChange for edge pair found |
| // sort by target iff target is edge and remove from changedRoutes |
| DeviceId targetSw = route.get(0); |
| try { |
| if (!srManager.deviceConfiguration.isEdgeDevice(targetSw)) { |
| continue; |
| } |
| } catch (DeviceConfigNotFoundException e) { |
| log.warn(e.getMessage() + "aborting redoRouting"); |
| return false; |
| } |
| // route is from another edge to this edge-pair |
| if (targetRoutes.containsKey(targetSw)) { |
| targetRoutes.get(targetSw).add(route); |
| } else { |
| Set<ArrayList<DeviceId>> temp = new HashSet<>(); |
| temp.add(route); |
| targetRoutes.put(targetSw, temp); |
| } |
| i.remove(); |
| } |
| } |
| // so now for this edgepair we have a per target set of routechanges |
| // process target->edgePair route |
| for (Map.Entry<DeviceId, Set<ArrayList<DeviceId>>> entry : |
| targetRoutes.entrySet()) { |
| log.debug("* redoRoutingDstPair Target:{} -> edge-pair {}", |
| entry.getKey(), ep); |
| DeviceId targetSw = entry.getKey(); |
| Map<DeviceId, Set<DeviceId>> perDstNextHops = new HashMap<>(); |
| entry.getValue().forEach(route -> { |
| Set<DeviceId> nhops = getNextHops(route.get(0), route.get(1)); |
| log.debug("route: target {} -> dst {} found with next-hops {}", |
| route.get(0), route.get(1), nhops); |
| perDstNextHops.put(route.get(1), nhops); |
| }); |
| Set<IpPrefix> ipDev1 = (subnets == null) ? config.getSubnets(ep.dev1) |
| : subnets; |
| Set<IpPrefix> ipDev2 = (subnets == null) ? config.getSubnets(ep.dev2) |
| : subnets; |
| ipDev1 = (ipDev1 == null) ? Sets.newHashSet() : ipDev1; |
| ipDev2 = (ipDev2 == null) ? Sets.newHashSet() : ipDev2; |
| // handle routing to subnets common to edge-pair |
| // only if the targetSw is not part of the edge-pair |
| if (!ep.includes(targetSw)) { |
| if (!populateEcmpRoutingRulePartial( |
| targetSw, |
| ep.dev1, ep.dev2, |
| perDstNextHops, |
| Sets.intersection(ipDev1, ipDev2))) { |
| return false; // abort everything and fail fast |
| } |
| } |
| // handle routing to subnets that only belong to dev1 |
| Set<IpPrefix> onlyDev1Subnets = Sets.difference(ipDev1, ipDev2); |
| if (!onlyDev1Subnets.isEmpty() && perDstNextHops.get(ep.dev1) != null) { |
| Map<DeviceId, Set<DeviceId>> onlyDev1NextHops = new HashMap<>(); |
| onlyDev1NextHops.put(ep.dev1, perDstNextHops.get(ep.dev1)); |
| if (!populateEcmpRoutingRulePartial( |
| targetSw, |
| ep.dev1, null, |
| onlyDev1NextHops, |
| onlyDev1Subnets)) { |
| return false; // abort everything and fail fast |
| } |
| } |
| // handle routing to subnets that only belong to dev2 |
| Set<IpPrefix> onlyDev2Subnets = Sets.difference(ipDev2, ipDev1); |
| if (!onlyDev2Subnets.isEmpty() && perDstNextHops.get(ep.dev2) != null) { |
| Map<DeviceId, Set<DeviceId>> onlyDev2NextHops = new HashMap<>(); |
| onlyDev2NextHops.put(ep.dev2, perDstNextHops.get(ep.dev2)); |
| if (!populateEcmpRoutingRulePartial( |
| targetSw, |
| ep.dev2, null, |
| onlyDev2NextHops, |
| onlyDev2Subnets)) { |
| return false; // abort everything and fail fast |
| } |
| } |
| } |
| // if it gets here it has succeeded for all targets to this edge-pair |
| } |
| return true; |
| } |
| |
| /** |
| * Programs targetSw in the changedRoutes for given prefixes reachable by |
| * a destination switch that is not part of an edge-pair. |
| * If no prefixes are given, the method will use configured subnets/prefixes. |
| * |
| * @param subnets a set of prefixes that need to be populated in the routing |
| * table of the target switch in the changedRoutes. Can be null, |
| * in which case all the configured prefixes belonging to the |
| * paired switches will be populated in the target switch |
| * @param changedRoutes a set of route-path changes, where each route-path is |
| * a list with its first element the src-switch (target) |
| * of the path, and the second element the dst-switch of |
| * the path. |
| * @return true if successful |
| */ |
| private boolean redoRoutingIndividualDests(Set<IpPrefix> subnets, |
| Set<ArrayList<DeviceId>> changedRoutes) { |
| // aggregate route-path changes for each dst device |
| HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>> routesBydevice = |
| new HashMap<>(); |
| for (ArrayList<DeviceId> route: changedRoutes) { |
| DeviceId dstSw = route.get(1); |
| ArrayList<ArrayList<DeviceId>> deviceRoutes = |
| routesBydevice.get(dstSw); |
| if (deviceRoutes == null) { |
| deviceRoutes = new ArrayList<>(); |
| routesBydevice.put(dstSw, deviceRoutes); |
| } |
| deviceRoutes.add(route); |
| } |
| for (DeviceId impactedDstDevice : routesBydevice.keySet()) { |
| ArrayList<ArrayList<DeviceId>> deviceRoutes = |
| routesBydevice.get(impactedDstDevice); |
| for (ArrayList<DeviceId> route: deviceRoutes) { |
| log.debug("* redoRoutingIndiDst Target: {} -> dst: {}", |
| route.get(0), route.get(1)); |
| DeviceId targetSw = route.get(0); |
| DeviceId dstSw = route.get(1); // same as impactedDstDevice |
| Set<DeviceId> nextHops = getNextHops(targetSw, dstSw); |
| if (nextHops.isEmpty()) { |
| log.warn("Could not find next hop from target:{} --> dst {} " |
| + "skipping this route", targetSw, dstSw); |
| continue; |
| } |
| Map<DeviceId, Set<DeviceId>> nhops = new HashMap<>(); |
| nhops.put(dstSw, nextHops); |
| if (!populateEcmpRoutingRulePartial(targetSw, dstSw, null, nhops, |
| (subnets == null) ? Sets.newHashSet() : subnets)) { |
| return false; // abort routing and fail fast |
| } |
| log.debug("Populating flow rules from target: {} to dst: {}" |
| + " is successful", targetSw, dstSw); |
| } |
| //Only if all the flows for all impacted routes to a |
| //specific target are pushed successfully, update the |
| //ECMP graph for that target. Or else the next event |
| //would not see any changes in the ECMP graphs. |
| //In another case, the target switch has gone away, so |
| //routes can't be installed. In that case, the current map |
| //is updated here, without any flows being pushed. |
| currentEcmpSpgMap.put(impactedDstDevice, |
| updatedEcmpSpgMap.get(impactedDstDevice)); |
| log.debug("Updating ECMPspg for impacted dev:{}", impactedDstDevice); |
| } |
| return true; |
| } |
| |
| /** |
| * Populate ECMP rules for subnets from target to destination via nexthops. |
| * |
| * @param targetSw Device ID of target switch in which rules will be programmed |
| * @param destSw1 Device ID of final destination switch to which the rules will forward |
| * @param destSw2 Device ID of paired destination switch to which the rules will forward |
| * A null deviceId indicates packets should only be sent to destSw1 |
| * @param nextHops Map indication a list of next hops per destSw |
| * @param subnets Subnets to be populated. If empty, populate all configured subnets. |
| * @return true if it succeeds in populating rules |
| */ // refactor |
| private boolean populateEcmpRoutingRulePartial(DeviceId targetSw, |
| DeviceId destSw1, |
| DeviceId destSw2, |
| Map<DeviceId, Set<DeviceId>> nextHops, |
| Set<IpPrefix> subnets) { |
| boolean result; |
| // If both target switch and dest switch are edge routers, then set IP |
| // rule for both subnet and router IP. |
| boolean targetIsEdge; |
| boolean dest1IsEdge; |
| Ip4Address dest1RouterIpv4, dest2RouterIpv4 = null; |
| Ip6Address dest1RouterIpv6, dest2RouterIpv6 = null; |
| |
| try { |
| targetIsEdge = config.isEdgeDevice(targetSw); |
| dest1IsEdge = config.isEdgeDevice(destSw1); |
| dest1RouterIpv4 = config.getRouterIpv4(destSw1); |
| dest1RouterIpv6 = config.getRouterIpv6(destSw1); |
| if (destSw2 != null) { |
| dest2RouterIpv4 = config.getRouterIpv4(destSw2); |
| dest2RouterIpv6 = config.getRouterIpv6(destSw2); |
| } |
| } catch (DeviceConfigNotFoundException e) { |
| log.warn(e.getMessage() + " Aborting populateEcmpRoutingRulePartial."); |
| return false; |
| } |
| |
| if (targetIsEdge && dest1IsEdge) { |
| subnets = (subnets != null && !subnets.isEmpty()) |
| ? Sets.newHashSet(subnets) |
| : Sets.newHashSet(config.getSubnets(destSw1)); |
| // XXX - Rethink this |
| /*subnets.add(dest1RouterIpv4.toIpPrefix()); |
| if (dest1RouterIpv6 != null) { |
| subnets.add(dest1RouterIpv6.toIpPrefix()); |
| } |
| if (destSw2 != null && dest2RouterIpv4 != null) { |
| subnets.add(dest2RouterIpv4.toIpPrefix()); |
| if (dest2RouterIpv6 != null) { |
| subnets.add(dest2RouterIpv6.toIpPrefix()); |
| } |
| }*/ |
| log.debug(". populateEcmpRoutingRulePartial in device {} towards {} {} " |
| + "for subnets {}", targetSw, destSw1, |
| (destSw2 != null) ? ("& " + destSw2) : "", |
| subnets); |
| result = rulePopulator.populateIpRuleForSubnet(targetSw, subnets, |
| destSw1, destSw2, |
| nextHops); |
| if (!result) { |
| return false; |
| } |
| /* XXX rethink this |
| IpPrefix routerIpPrefix = destRouterIpv4.toIpPrefix(); |
| log.debug("* populateEcmpRoutingRulePartial in device {} towards {} " |
| + "for router IP {}", targetSw, destSw, routerIpPrefix); |
| result = rulePopulator.populateIpRuleForRouter(targetSw, routerIpPrefix, |
| destSw, nextHops); |
| if (!result) { |
| return false; |
| } |
| // If present we deal with IPv6 loopback. |
| if (destRouterIpv6 != null) { |
| routerIpPrefix = destRouterIpv6.toIpPrefix(); |
| log.debug("* populateEcmpRoutingRulePartial in device {} towards {}" |
| + " for v6 router IP {}", targetSw, destSw, routerIpPrefix); |
| result = rulePopulator.populateIpRuleForRouter(targetSw, routerIpPrefix, |
| destSw, nextHops); |
| if (!result) { |
| return false; |
| } |
| }*/ |
| } |
| |
| if (!targetIsEdge && dest1IsEdge) { |
| // MPLS rules in all non-edge target devices. These rules are for |
| // individual destinations, even if the dsts are part of edge-pairs. |
| log.debug(". populateEcmpRoutingRulePartial in device{} towards {} for " |
| + "all MPLS rules", targetSw, destSw1); |
| result = rulePopulator.populateMplsRule(targetSw, destSw1, |
| nextHops.get(destSw1), |
| dest1RouterIpv4); |
| if (!result) { |
| return false; |
| } |
| if (dest1RouterIpv6 != null) { |
| result = rulePopulator.populateMplsRule(targetSw, destSw1, |
| nextHops.get(destSw1), |
| dest1RouterIpv6); |
| if (!result) { |
| return false; |
| } |
| } |
| } |
| |
| // To save on ECMP groups |
| // avoid MPLS rules in non-edge-devices to non-edge-devices |
| // avoid MPLS transit rules in edge-devices |
| // avoid loopback IP rules in edge-devices to non-edge-devices |
| return true; |
| } |
| |
| /** |
| * Processes a set a route-path changes by editing hash groups. |
| * |
| * @param routeChanges a set of route-path changes, where each route-path is |
| * a list with its first element the src-switch of the path |
| * and the second element the dst-switch of the path. |
| * @param linkOrSwitchFailed true if the route changes are for a failed |
| * switch or linkDown event |
| * @param failedSwitch the switchId if the route changes are for a failed switch, |
| * otherwise null |
| */ |
| private void processHashGroupChange(Set<ArrayList<DeviceId>> routeChanges, |
| boolean linkOrSwitchFailed, |
| DeviceId failedSwitch) { |
| Set<ArrayList<DeviceId>> changedRoutes = new HashSet<>(); |
| // first, ensure each routeChanges entry has two elements |
| for (ArrayList<DeviceId> route : routeChanges) { |
| if (route.size() == 1) { |
| // route-path changes are from everyone else to this switch |
| DeviceId dstSw = route.get(0); |
| srManager.deviceService.getAvailableDevices().forEach(sw -> { |
| if (!sw.id().equals(dstSw)) { |
| changedRoutes.add(Lists.newArrayList(sw.id(), dstSw)); |
| } |
| }); |
| } else { |
| changedRoutes.add(route); |
| } |
| } |
| |
| for (ArrayList<DeviceId> route : changedRoutes) { |
| DeviceId targetSw = route.get(0); |
| DeviceId dstSw = route.get(1); |
| if (linkOrSwitchFailed) { |
| boolean success = fixHashGroupsForRoute(route, true); |
| // it's possible that we cannot fix hash groups for a route |
| // if the target switch has failed. Nevertheless the ecmp graph |
| // for the impacted switch must still be updated. |
| if (!success && failedSwitch != null && targetSw.equals(failedSwitch)) { |
| currentEcmpSpgMap.put(dstSw, updatedEcmpSpgMap.get(dstSw)); |
| currentEcmpSpgMap.remove(targetSw); |
| log.debug("Updating ECMPspg for dst:{} removing failed switch " |
| + "target:{}", dstSw, targetSw); |
| continue; |
| } |
| //linkfailed - update both sides |
| if (success) { |
| currentEcmpSpgMap.put(targetSw, updatedEcmpSpgMap.get(targetSw)); |
| currentEcmpSpgMap.put(dstSw, updatedEcmpSpgMap.get(dstSw)); |
| log.debug("Updating ECMPspg for dst:{} and target:{} for linkdown", |
| dstSw, targetSw); |
| } |
| } else { |
| //linkup of seen before link |
| boolean success = fixHashGroupsForRoute(route, false); |
| if (success) { |
| currentEcmpSpgMap.put(targetSw, updatedEcmpSpgMap.get(targetSw)); |
| currentEcmpSpgMap.put(dstSw, updatedEcmpSpgMap.get(dstSw)); |
| log.debug("Updating ECMPspg for target:{} and dst:{} for linkup", |
| targetSw, dstSw); |
| } |
| } |
| } |
| } |
| |
| /** |
| * Edits hash groups in the src-switch (targetSw) of a route-path by |
| * calling the groupHandler to either add or remove buckets in an existing |
| * hash group. |
| * |
| * @param route a single list representing a route-path where the first element |
| * is the src-switch (targetSw) of the route-path and the |
| * second element is the dst-switch |
| * @param revoke true if buckets in the hash-groups need to be removed; |
| * false if buckets in the hash-groups need to be added |
| * @return true if the hash group editing is successful |
| */ |
| private boolean fixHashGroupsForRoute(ArrayList<DeviceId> route, |
| boolean revoke) { |
| DeviceId targetSw = route.get(0); |
| if (route.size() < 2) { |
| log.warn("Cannot fixHashGroupsForRoute - no dstSw in route {}", route); |
| return false; |
| } |
| DeviceId destSw = route.get(1); |
| log.debug("* processing fixHashGroupsForRoute: Target {} -> Dest {}", |
| targetSw, destSw); |
| // figure out the new next hops at the targetSw towards the destSw |
| Set<DeviceId> nextHops = getNextHops(targetSw, destSw); |
| // call group handler to change hash group at targetSw |
| DefaultGroupHandler grpHandler = srManager.getGroupHandler(targetSw); |
| if (grpHandler == null) { |
| log.warn("Cannot find grouphandler for dev:{} .. aborting" |
| + " {} hash group buckets for route:{} ", targetSw, |
| (revoke) ? "revoke" : "repopulate", route); |
| return false; |
| } |
| log.debug("{} hash-groups buckets For Route {} -> {} to next-hops {}", |
| (revoke) ? "revoke" : "repopulating", |
| targetSw, destSw, nextHops); |
| return (revoke) ? grpHandler.fixHashGroups(targetSw, nextHops, |
| destSw, true) |
| : grpHandler.fixHashGroups(targetSw, nextHops, |
| destSw, false); |
| } |
| |
| /** |
| * Start the flow rule population process if it was never started. The |
| * process finishes successfully when all flow rules are set and stops with |
| * ABORTED status when any groups required for flows is not set yet. |
| */ |
| public void startPopulationProcess() { |
| statusLock.lock(); |
| try { |
| if (populationStatus == Status.IDLE |
| || populationStatus == Status.SUCCEEDED |
| || populationStatus == Status.ABORTED) { |
| populateAllRoutingRules(); |
| } else { |
| log.warn("Not initiating startPopulationProcess as populationStatus is {}", |
| populationStatus); |
| } |
| } finally { |
| statusLock.unlock(); |
| } |
| } |
| |
| /** |
| * Revoke rules of given subnet in all edge switches. |
| * |
| * @param subnets subnet being removed |
| * @return true if succeed |
| */ |
| protected boolean revokeSubnet(Set<IpPrefix> subnets) { |
| statusLock.lock(); |
| try { |
| return srManager.routingRulePopulator.revokeIpRuleForSubnet(subnets); |
| } finally { |
| statusLock.unlock(); |
| } |
| } |
| |
| /** |
| * Populates IP rules for a route that has direct connection to the switch |
| * if the current instance is the master of the switch. |
| * |
| * @param deviceId device ID of the device that next hop attaches to |
| * @param prefix IP prefix of the route |
| * @param hostMac MAC address of the next hop |
| * @param hostVlanId Vlan ID of the nexthop |
| * @param outPort port where the next hop attaches to |
| */ |
| void populateRoute(DeviceId deviceId, IpPrefix prefix, |
| MacAddress hostMac, VlanId hostVlanId, PortNumber outPort) { |
| if (srManager.mastershipService.isLocalMaster(deviceId)) { |
| srManager.routingRulePopulator.populateRoute(deviceId, prefix, hostMac, hostVlanId, outPort); |
| } |
| } |
| |
| /** |
| * Removes IP rules for a route when the next hop is gone. |
| * if the current instance is the master of the switch. |
| * |
| * @param deviceId device ID of the device that next hop attaches to |
| * @param prefix IP prefix of the route |
| * @param hostMac MAC address of the next hop |
| * @param hostVlanId Vlan ID of the nexthop |
| * @param outPort port that next hop attaches to |
| */ |
| void revokeRoute(DeviceId deviceId, IpPrefix prefix, |
| MacAddress hostMac, VlanId hostVlanId, PortNumber outPort) { |
| if (srManager.mastershipService.isLocalMaster(deviceId)) { |
| srManager.routingRulePopulator.revokeRoute(deviceId, prefix, hostMac, hostVlanId, outPort); |
| } |
| } |
| |
| /** |
| * Remove ECMP graph entry for the given device. Typically called when |
| * device is no longer available. |
| * |
| * @param deviceId the device for which graphs need to be purged |
| */ |
| protected void purgeEcmpGraph(DeviceId deviceId) { |
| currentEcmpSpgMap.remove(deviceId); // XXX reconsider |
| if (updatedEcmpSpgMap != null) { |
| updatedEcmpSpgMap.remove(deviceId); |
| } |
| } |
| |
| ////////////////////////////////////// |
| // Routing helper methods and classes |
| ////////////////////////////////////// |
| |
| /** |
| * Computes set of affected routes due to failed link. Assumes |
| * previous ecmp shortest-path graph exists for a switch in order to compute |
| * affected routes. If such a graph does not exist, the method returns null. |
| * |
| * @param linkFail the failed link |
| * @return the set of affected routes which may be empty if no routes were |
| * affected, or null if no previous ecmp spg was found for comparison |
| */ |
| private Set<ArrayList<DeviceId>> computeDamagedRoutes(Link linkFail) { |
| Set<ArrayList<DeviceId>> routes = new HashSet<>(); |
| |
| for (Device sw : srManager.deviceService.getDevices()) { |
| log.debug("Computing the impacted routes for device {} due to link fail", |
| sw.id()); |
| DeviceId retId = shouldHandleRouting(sw.id()); |
| if (retId == null) { |
| continue; |
| } |
| Set<DeviceId> devicesToProcess = Sets.newHashSet(retId, sw.id()); |
| for (DeviceId rootSw : devicesToProcess) { |
| EcmpShortestPathGraph ecmpSpg = currentEcmpSpgMap.get(rootSw); |
| if (ecmpSpg == null) { |
| log.warn("No existing ECMP graph for switch {}. Aborting optimized" |
| + " rerouting and opting for full-reroute", rootSw); |
| return null; |
| } |
| if (log.isDebugEnabled()) { |
| log.debug("Root switch: {}", rootSw); |
| log.debug(" Current/Existing SPG: {}", ecmpSpg); |
| log.debug(" New/Updated SPG: {}", updatedEcmpSpgMap.get(rootSw)); |
| } |
| HashMap<Integer, HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>>> |
| switchVia = ecmpSpg.getAllLearnedSwitchesAndVia(); |
| // figure out if the broken link affected any route-paths in this graph |
| for (Integer itrIdx : switchVia.keySet()) { |
| log.trace("Current/Exiting SPG Iterindex# {}", itrIdx); |
| HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>> swViaMap = |
| switchVia.get(itrIdx); |
| for (DeviceId targetSw : swViaMap.keySet()) { |
| log.trace("TargetSwitch {} --> RootSwitch {}", |
| targetSw, rootSw); |
| for (ArrayList<DeviceId> via : swViaMap.get(targetSw)) { |
| log.trace(" Via:"); |
| via.forEach(e -> log.trace(" {}", e)); |
| } |
| Set<ArrayList<DeviceId>> subLinks = |
| computeLinks(targetSw, rootSw, swViaMap); |
| for (ArrayList<DeviceId> alink: subLinks) { |
| if ((alink.get(0).equals(linkFail.src().deviceId()) && |
| alink.get(1).equals(linkFail.dst().deviceId())) |
| || |
| (alink.get(0).equals(linkFail.dst().deviceId()) && |
| alink.get(1).equals(linkFail.src().deviceId()))) { |
| log.debug("Impacted route:{}->{}", targetSw, rootSw); |
| ArrayList<DeviceId> aRoute = new ArrayList<>(); |
| aRoute.add(targetSw); // switch with rules to populate |
| aRoute.add(rootSw); // towards this destination |
| routes.add(aRoute); |
| break; |
| } |
| } |
| } |
| } |
| |
| } |
| |
| } |
| return routes; |
| } |
| |
| /** |
| * Computes set of affected routes due to new links or failed switches. |
| * |
| * @return the set of affected routes which may be empty if no routes were |
| * affected |
| */ |
| private Set<ArrayList<DeviceId>> computeRouteChange() { |
| ImmutableSet.Builder<ArrayList<DeviceId>> changedRtBldr = |
| ImmutableSet.builder(); |
| |
| for (Device sw : srManager.deviceService.getDevices()) { |
| log.debug("Computing the impacted routes for device {}", sw.id()); |
| DeviceId retId = shouldHandleRouting(sw.id()); |
| if (retId == null) { |
| continue; |
| } |
| Set<DeviceId> devicesToProcess = Sets.newHashSet(retId, sw.id()); |
| for (DeviceId rootSw : devicesToProcess) { |
| if (log.isTraceEnabled()) { |
| log.trace("Device links for dev: {}", rootSw); |
| for (Link link: srManager.linkService.getDeviceLinks(rootSw)) { |
| log.trace("{} -> {} ", link.src().deviceId(), |
| link.dst().deviceId()); |
| } |
| } |
| EcmpShortestPathGraph currEcmpSpg = currentEcmpSpgMap.get(rootSw); |
| if (currEcmpSpg == null) { |
| log.debug("No existing ECMP graph for device {}.. adding self as " |
| + "changed route", rootSw); |
| changedRtBldr.add(Lists.newArrayList(rootSw)); |
| continue; |
| } |
| EcmpShortestPathGraph newEcmpSpg = updatedEcmpSpgMap.get(rootSw); |
| if (log.isDebugEnabled()) { |
| log.debug("Root switch: {}", rootSw); |
| log.debug(" Current/Existing SPG: {}", currEcmpSpg); |
| log.debug(" New/Updated SPG: {}", newEcmpSpg); |
| } |
| // first use the updated/new map to compare to current/existing map |
| // as new links may have come up |
| changedRtBldr.addAll(compareGraphs(newEcmpSpg, currEcmpSpg, rootSw)); |
| // then use the current/existing map to compare to updated/new map |
| // as switch may have been removed |
| changedRtBldr.addAll(compareGraphs(currEcmpSpg, newEcmpSpg, rootSw)); |
| } |
| } |
| |
| Set<ArrayList<DeviceId>> changedRoutes = changedRtBldr.build(); |
| for (ArrayList<DeviceId> route: changedRoutes) { |
| log.debug("Route changes Target -> Root"); |
| if (route.size() == 1) { |
| log.debug(" : all -> {}", route.get(0)); |
| } else { |
| log.debug(" : {} -> {}", route.get(0), route.get(1)); |
| } |
| } |
| return changedRoutes; |
| } |
| |
| /** |
| * For the root switch, searches all the target nodes reachable in the base |
| * graph, and compares paths to the ones in the comp graph. |
| * |
| * @param base the graph that is indexed for all reachable target nodes |
| * from the root node |
| * @param comp the graph that the base graph is compared to |
| * @param rootSw both ecmp graphs are calculated for the root node |
| * @return all the routes that have changed in the base graph |
| */ |
| private Set<ArrayList<DeviceId>> compareGraphs(EcmpShortestPathGraph base, |
| EcmpShortestPathGraph comp, |
| DeviceId rootSw) { |
| ImmutableSet.Builder<ArrayList<DeviceId>> changedRoutesBuilder = |
| ImmutableSet.builder(); |
| HashMap<Integer, HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>>> baseMap = |
| base.getAllLearnedSwitchesAndVia(); |
| HashMap<Integer, HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>>> compMap = |
| comp.getAllLearnedSwitchesAndVia(); |
| for (Integer itrIdx : baseMap.keySet()) { |
| HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>> baseViaMap = |
| baseMap.get(itrIdx); |
| for (DeviceId targetSw : baseViaMap.keySet()) { |
| ArrayList<ArrayList<DeviceId>> basePath = baseViaMap.get(targetSw); |
| ArrayList<ArrayList<DeviceId>> compPath = getVia(compMap, targetSw); |
| if ((compPath == null) || !basePath.equals(compPath)) { |
| log.trace("Impacted route:{} -> {}", targetSw, rootSw); |
| ArrayList<DeviceId> route = new ArrayList<>(); |
| route.add(targetSw); // switch with rules to populate |
| route.add(rootSw); // towards this destination |
| changedRoutesBuilder.add(route); |
| } |
| } |
| } |
| return changedRoutesBuilder.build(); |
| } |
| |
| /** |
| * Returns the ECMP paths traversed to reach the target switch. |
| * |
| * @param switchVia a per-iteration view of the ECMP graph for a root switch |
| * @param targetSw the switch to reach from the root switch |
| * @return the nodes traversed on ECMP paths to the target switch |
| */ |
| private ArrayList<ArrayList<DeviceId>> getVia(HashMap<Integer, HashMap<DeviceId, |
| ArrayList<ArrayList<DeviceId>>>> switchVia, DeviceId targetSw) { |
| for (Integer itrIdx : switchVia.keySet()) { |
| HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>> swViaMap = |
| switchVia.get(itrIdx); |
| if (swViaMap.get(targetSw) == null) { |
| continue; |
| } else { |
| return swViaMap.get(targetSw); |
| } |
| } |
| |
| return null; |
| } |
| |
| /** |
| * Utility method to break down a path from src to dst device into a collection |
| * of links. |
| * |
| * @param src src device of the path |
| * @param dst dst device of the path |
| * @param viaMap path taken from src to dst device |
| * @return collection of links in the path |
| */ |
| private Set<ArrayList<DeviceId>> computeLinks(DeviceId src, |
| DeviceId dst, |
| HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>> viaMap) { |
| Set<ArrayList<DeviceId>> subLinks = Sets.newHashSet(); |
| for (ArrayList<DeviceId> via : viaMap.get(src)) { |
| DeviceId linkSrc = src; |
| DeviceId linkDst = dst; |
| for (DeviceId viaDevice: via) { |
| ArrayList<DeviceId> link = new ArrayList<>(); |
| linkDst = viaDevice; |
| link.add(linkSrc); |
| link.add(linkDst); |
| subLinks.add(link); |
| linkSrc = viaDevice; |
| } |
| ArrayList<DeviceId> link = new ArrayList<>(); |
| link.add(linkSrc); |
| link.add(dst); |
| subLinks.add(link); |
| } |
| |
| return subLinks; |
| } |
| |
| /** |
| * Determines whether this controller instance should handle routing for the |
| * given {@code deviceId}, based on mastership and pairDeviceId if one exists. |
| * Returns null if this instance should not handle routing for given {@code deviceId}. |
| * Otherwise the returned value could be the given deviceId itself, or the |
| * deviceId for the paired edge device. In the latter case, this instance |
| * should handle routing for both the given device and the paired device. |
| * |
| * @param deviceId device identifier to consider for routing |
| * @return null or deviceId which could be the same as the given deviceId |
| * or the deviceId of a paired edge device |
| */ |
| private DeviceId shouldHandleRouting(DeviceId deviceId) { |
| if (!srManager.mastershipService.isLocalMaster(deviceId)) { |
| log.debug("Not master for dev:{} .. skipping routing, may get handled " |
| + "elsewhere as part of paired devices", deviceId); |
| return null; |
| } |
| NodeId myNode = srManager.mastershipService.getMasterFor(deviceId); |
| DeviceId pairDev = getPairDev(deviceId); |
| |
| if (pairDev != null) { |
| if (!srManager.deviceService.isAvailable(pairDev)) { |
| log.warn("pairedDev {} not available .. routing this dev:{} " |
| + "without mastership check", |
| pairDev, deviceId); |
| return pairDev; // handle both temporarily |
| } |
| NodeId pairMasterNode = srManager.mastershipService.getMasterFor(pairDev); |
| if (myNode.compareTo(pairMasterNode) <= 0) { |
| log.debug("Handling routing for both dev:{} pair-dev:{}; myNode: {}" |
| + " pairMaster:{} compare:{}", deviceId, pairDev, |
| myNode, pairMasterNode, |
| myNode.compareTo(pairMasterNode)); |
| return pairDev; // handle both |
| } else { |
| log.debug("PairDev node: {} should handle routing for dev:{} and " |
| + "pair-dev:{}", pairMasterNode, deviceId, pairDev); |
| return null; // handle neither |
| } |
| } |
| return deviceId; // not paired, just handle given device |
| } |
| |
| /** |
| * Returns the configured paired DeviceId for the given Device, or null |
| * if no such paired device has been configured. |
| * |
| * @param deviceId |
| * @return configured pair deviceId or null |
| */ |
| private DeviceId getPairDev(DeviceId deviceId) { |
| DeviceId pairDev; |
| try { |
| pairDev = srManager.deviceConfiguration.getPairDeviceId(deviceId); |
| } catch (DeviceConfigNotFoundException e) { |
| log.warn(e.getMessage() + " .. cannot continue routing for dev: {}"); |
| return null; |
| } |
| return pairDev; |
| } |
| |
| /** |
| * Returns the set of deviceIds which are the next hops from the targetSw |
| * to the dstSw according to the latest ECMP spg. |
| * |
| * @param targetSw the switch for which the next-hops are desired |
| * @param dstSw the switch to which the next-hops lead to from the targetSw |
| * @return set of next hop deviceIds, could be empty if no next hops are found |
| */ |
| private Set<DeviceId> getNextHops(DeviceId targetSw, DeviceId dstSw) { |
| boolean targetIsEdge = false; |
| try { |
| targetIsEdge = srManager.deviceConfiguration.isEdgeDevice(targetSw); |
| } catch (DeviceConfigNotFoundException e) { |
| log.warn(e.getMessage() + "Cannot determine if targetIsEdge {}.. " |
| + "continuing to getNextHops", targetSw); |
| } |
| |
| EcmpShortestPathGraph ecmpSpg = updatedEcmpSpgMap.get(dstSw); |
| if (ecmpSpg == null) { |
| log.debug("No ecmpSpg found for dstSw: {}", dstSw); |
| return ImmutableSet.of(); |
| } |
| HashMap<Integer, |
| HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>>> switchVia = |
| ecmpSpg.getAllLearnedSwitchesAndVia(); |
| for (Integer itrIdx : switchVia.keySet()) { |
| HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>> swViaMap = |
| switchVia.get(itrIdx); |
| for (DeviceId target : swViaMap.keySet()) { |
| if (!target.equals(targetSw)) { |
| continue; |
| } |
| if (!targetIsEdge && itrIdx > 1) { |
| // optimization for spines to not use other leaves to get |
| // to a leaf to avoid loops |
| log.debug("Avoiding {} hop path for non-edge targetSw:{}" |
| + " --> dstSw:{}", itrIdx, targetSw, dstSw); |
| break; |
| } |
| Set<DeviceId> nextHops = new HashSet<>(); |
| for (ArrayList<DeviceId> via : swViaMap.get(targetSw)) { |
| if (via.isEmpty()) { |
| // the dstSw is the next-hop from the targetSw |
| nextHops.add(dstSw); |
| } else { |
| // first elem is next-hop in each ECMP path |
| nextHops.add(via.get(0)); |
| } |
| } |
| return nextHops; |
| } |
| } |
| return ImmutableSet.of(); //no next-hops found |
| } |
| |
| /** |
| * Represents two devices that are paired by configuration. An EdgePair for |
| * (dev1, dev2) is the same as as EdgePair for (dev2, dev1) |
| */ |
| protected final class EdgePair { |
| DeviceId dev1; |
| DeviceId dev2; |
| |
| EdgePair(DeviceId dev1, DeviceId dev2) { |
| this.dev1 = dev1; |
| this.dev2 = dev2; |
| } |
| |
| boolean includes(DeviceId dev) { |
| return dev1.equals(dev) || dev2.equals(dev); |
| } |
| |
| @Override |
| public boolean equals(Object o) { |
| if (this == o) { |
| return true; |
| } |
| if (!(o instanceof EdgePair)) { |
| return false; |
| } |
| EdgePair that = (EdgePair) o; |
| return ((this.dev1.equals(that.dev1) && this.dev2.equals(that.dev2)) || |
| (this.dev1.equals(that.dev2) && this.dev2.equals(that.dev1))); |
| } |
| |
| @Override |
| public int hashCode() { |
| if (dev1.toString().compareTo(dev2.toString()) <= 0) { |
| return Objects.hash(dev1, dev2); |
| } else { |
| return Objects.hash(dev2, dev1); |
| } |
| } |
| |
| @Override |
| public String toString() { |
| return toStringHelper(this) |
| .add("Dev1", dev1) |
| .add("Dev2", dev2) |
| .toString(); |
| } |
| } |
| |
| /** |
| * Updates the currentEcmpSpgGraph for all devices. |
| */ |
| private void updateEcmpSpgMaps() { |
| for (Device sw : srManager.deviceService.getDevices()) { |
| EcmpShortestPathGraph ecmpSpgUpdated = |
| new EcmpShortestPathGraph(sw.id(), srManager); |
| currentEcmpSpgMap.put(sw.id(), ecmpSpgUpdated); |
| } |
| } |
| |
| /** |
| * Ensures routing is stable before updating all ECMP SPG graphs. |
| * |
| * TODO: CORD-1843 will ensure maps are updated faster, potentially while |
| * topology/routing is still unstable |
| */ |
| private final class UpdateMaps implements Runnable { |
| @Override |
| public void run() { |
| if (isRoutingStable()) { |
| updateEcmpSpgMaps(); |
| } else { |
| executorService.schedule(new UpdateMaps(), UPDATE_INTERVAL, |
| TimeUnit.SECONDS); |
| } |
| } |
| } |
| |
| ////////////////////////////////////// |
| // Filtering rule creation |
| ////////////////////////////////////// |
| |
| /** |
| * Populates filtering rules for port, and punting rules |
| * for gateway IPs, loopback IPs and arp/ndp traffic. |
| * Should only be called by the master instance for this device/port. |
| * |
| * @param deviceId Switch ID to set the rules |
| */ |
| public void populatePortAddressingRules(DeviceId deviceId) { |
| // Although device is added, sometimes device store does not have the |
| // ports for this device yet. It results in missing filtering rules in the |
| // switch. We will attempt it a few times. If it still does not work, |
| // user can manually repopulate using CLI command sr-reroute-network |
| PortFilterInfo firstRun = rulePopulator.populateVlanMacFilters(deviceId); |
| if (firstRun == null) { |
| firstRun = new PortFilterInfo(0, 0, 0); |
| } |
| executorService.schedule(new RetryFilters(deviceId, firstRun), |
| RETRY_INTERVAL_MS, TimeUnit.MILLISECONDS); |
| } |
| |
| /** |
| * Utility class used to temporarily store information about the ports on a |
| * device processed for filtering objectives. |
| */ |
| public final class PortFilterInfo { |
| int disabledPorts = 0, errorPorts = 0, filteredPorts = 0; |
| |
| public PortFilterInfo(int disabledPorts, int errorPorts, |
| int filteredPorts) { |
| this.disabledPorts = disabledPorts; |
| this.filteredPorts = filteredPorts; |
| this.errorPorts = errorPorts; |
| } |
| |
| @Override |
| public int hashCode() { |
| return Objects.hash(disabledPorts, filteredPorts, errorPorts); |
| } |
| |
| @Override |
| public boolean equals(Object obj) { |
| if (this == obj) { |
| return true; |
| } |
| if ((obj == null) || (!(obj instanceof PortFilterInfo))) { |
| return false; |
| } |
| PortFilterInfo other = (PortFilterInfo) obj; |
| return ((disabledPorts == other.disabledPorts) && |
| (filteredPorts == other.filteredPorts) && |
| (errorPorts == other.errorPorts)); |
| } |
| |
| @Override |
| public String toString() { |
| MoreObjects.ToStringHelper helper = toStringHelper(this) |
| .add("disabledPorts", disabledPorts) |
| .add("errorPorts", errorPorts) |
| .add("filteredPorts", filteredPorts); |
| return helper.toString(); |
| } |
| } |
| |
| /** |
| * RetryFilters populates filtering objectives for a device and keeps retrying |
| * till the number of ports filtered are constant for a predefined number |
| * of attempts. |
| */ |
| protected final class RetryFilters implements Runnable { |
| int constantAttempts = MAX_CONSTANT_RETRY_ATTEMPTS; |
| DeviceId devId; |
| int counter; |
| PortFilterInfo prevRun; |
| |
| private RetryFilters(DeviceId deviceId, PortFilterInfo previousRun) { |
| devId = deviceId; |
| prevRun = previousRun; |
| counter = 0; |
| } |
| |
| @Override |
| public void run() { |
| log.debug("RETRY FILTER ATTEMPT {} ** dev:{}", ++counter, devId); |
| PortFilterInfo thisRun = rulePopulator.populateVlanMacFilters(devId); |
| boolean sameResult = prevRun.equals(thisRun); |
| log.debug("dev:{} prevRun:{} thisRun:{} sameResult:{}", devId, prevRun, |
| thisRun, sameResult); |
| if (thisRun == null || !sameResult || (sameResult && --constantAttempts > 0)) { |
| // exponentially increasing intervals for retries |
| executorService.schedule(this, |
| RETRY_INTERVAL_MS * (int) Math.pow(counter, RETRY_INTERVAL_SCALE), |
| TimeUnit.MILLISECONDS); |
| if (!sameResult) { |
| constantAttempts = MAX_CONSTANT_RETRY_ATTEMPTS; //reset |
| } |
| } |
| prevRun = (thisRun == null) ? prevRun : thisRun; |
| } |
| } |
| |
| } |