blob: 5b6b07e0d35041dc31d2e25c9f959596ba424774 [file] [log] [blame]
/*
* Copyright 2015-present Open Networking Laboratory
*
* 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.onosproject.net.ConnectPoint;
import org.onosproject.net.Device;
import org.onosproject.net.DeviceId;
import org.onosproject.net.Link;
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.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
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 String ECMPSPG_MISSING = "ECMP shortest path graph not found";
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));
/**
* 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 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();
}
/**
* Populates all routing rules to all connected routers, including default
* routing rules, adjacency rules, and policy rules if any.
*/
public void populateAllRoutingRules() {
statusLock.lock();
try {
populationStatus = Status.STARTED;
rulePopulator.resetCounter();
log.info("Starting to populate segment-routing rules");
log.debug("populateAllRoutingRules: populationStatus is STARTED");
for (Device sw : srManager.deviceService.getDevices()) {
if (!srManager.mastershipService.isLocalMaster(sw.id())) {
log.debug("populateAllRoutingRules: skipping device {}..."
+ "we are not master", sw.id());
continue;
}
EcmpShortestPathGraph ecmpSpg = new EcmpShortestPathGraph(sw.id(), srManager);
if (!populateEcmpRoutingRules(sw.id(), ecmpSpg, ImmutableSet.of())) {
log.debug("populateAllRoutingRules: populationStatus is ABORTED");
populationStatus = Status.ABORTED;
log.debug("Abort routing rule population");
return;
}
currentEcmpSpgMap.put(sw.id(), ecmpSpg);
log.debug("Updating ECMPspg for sw:{}", sw.id());
// TODO: Set adjacency routing rule for all switches
}
log.debug("populateAllRoutingRules: populationStatus is SUCCEEDED");
populationStatus = Status.SUCCEEDED;
log.info("Completed routing rule 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
*/
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;
}
statusLock.lock();
try {
if (populationStatus == Status.STARTED) {
log.warn("Previous rule population is not finished.");
return;
}
// Take the snapshots of the links
updatedEcmpSpgMap = new HashMap<>();
for (Device sw : srManager.deviceService.getDevices()) {
if (!srManager.mastershipService.isLocalMaster(sw.id())) {
continue;
}
EcmpShortestPathGraph ecmpSpgUpdated =
new EcmpShortestPathGraph(sw.id(), srManager);
updatedEcmpSpgMap.put(sw.id(), ecmpSpgUpdated);
}
log.info("Starts rule population from link change");
Set<ArrayList<DeviceId>> routeChanges;
log.debug("populateRoutingRulesForLinkStatusChange: "
+ "populationStatus is STARTED");
populationStatus = Status.STARTED;
// 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();
if (routeChanges != null) {
// deal with linkUp of a seen-before link
if (linkUp != null && srManager.isSeenLink(linkUp)) {
if (!isBidirectional(linkUp)) {
log.warn("Not a bidirectional link yet .. not "
+ "processing link {}", linkUp);
srManager.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();
}
//deal with switchDown
if (switchDown != null) {
processHashGroupChange(routeChanges, true, switchDown);
// 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.updateSeenLink(linkUp, true);
}
} 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... doing full re-route");
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 (repopulateRoutingRulesForRoutes(routeChanges)) {
log.debug("populateRoutingRulesForLinkStatusChange: populationStatus is SUCCEEDED");
populationStatus = Status.SUCCEEDED;
log.info("Completed repopulation of rules. # of rules populated : {}",
rulePopulator.getCounter());
return;
} else {
log.debug("populateRoutingRulesForLinkStatusChange: populationStatus is ABORTED");
populationStatus = Status.ABORTED;
log.warn("Failed to repopulate the rules.");
return;
}
} finally {
statusLock.unlock();
}
}
/**
* Returns true if the link being queried is a bidirectional link. A bidi
* link is defined as a link, whose reverse link - ie. the link in the reverse
* direction - has been seen-before and is up.
*
* @param link the infrastructure link being queried
* @return true if another unidirectional link exists in the reverse direction,
* has been seen-before and is up
*/
private boolean isBidirectional(Link link) {
Link reverseLink = srManager.linkService.getLink(link.dst(), link.src());
if (reverseLink == null) {
return false;
}
Boolean result = srManager.isSeenLinkUp(reverseLink);
if (result == null) {
return false;
}
return result.booleanValue();
}
/**
* 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) {
for (ArrayList<DeviceId> route : routeChanges) {
DeviceId targetSw = route.get(0);
boolean success;
DeviceId dstSw = null;
if (route.size() > 1) {
dstSw = route.get(1);
}
if (linkOrSwitchFailed) {
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 (failedSwitch != null && targetSw.equals(failedSwitch)
&& dstSw != null) {
currentEcmpSpgMap.put(dstSw, updatedEcmpSpgMap.get(dstSw));
currentEcmpSpgMap.remove(targetSw);
log.debug("Updating ECMPspg for dst:{} removing failed "
+ "target:{}", dstSw, targetSw);
return;
}
//linkfailed - update both sides
currentEcmpSpgMap.put(targetSw, updatedEcmpSpgMap.get(targetSw));
dstSw = route.get(1);
currentEcmpSpgMap.put(dstSw, updatedEcmpSpgMap.get(dstSw));
log.debug("Updating ECMPspg for dst:{} and target:{}", dstSw, targetSw);
} else {
success = fixHashGroupsForRoute(route, false);
if (success) {
currentEcmpSpgMap.put(targetSw, updatedEcmpSpgMap.get(targetSw));
if (dstSw != null) {
currentEcmpSpgMap.put(dstSw, updatedEcmpSpgMap.get(dstSw));
}
log.debug("Updating ECMPspg for target:{} and dst:{}",
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);
boolean targetIsEdge = false;
try {
targetIsEdge = srManager.deviceConfiguration.isEdgeDevice(targetSw);
} catch (DeviceConfigNotFoundException e) {
log.warn(e.getMessage() + "Cannot determine if targetIsEdge {}.. "
+ "continuing fixHash", targetSw);
}
// figure out the new next hops at the targetSw towards the destSw
Set<DeviceId> nextHops = new HashSet<>();
EcmpShortestPathGraph ecmpSpg = updatedEcmpSpgMap.get(destSw);
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)) {
// found the iteration where targetSw is reached- get nextHops
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, destSw);
break;
}
for (ArrayList<DeviceId> via : swViaMap.get(target)) {
if (via.isEmpty()) {
nextHops.add(destSw);
} else {
// first elem is next-hop in each ECMP path
nextHops.add(via.get(0));
}
}
break;
}
}
}
// 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);
}
/**
* Processes a set a route-path changes by reprogramming routing rules and
* creating new hash-groups if necessary.
*
* @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.
* @return true if successful in repopulating routes
*/
private boolean repopulateRoutingRulesForRoutes(Set<ArrayList<DeviceId>> routeChanges) {
rulePopulator.resetCounter();
HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>> routesBydevice =
new HashMap<>();
for (ArrayList<DeviceId> link: routeChanges) {
// When only the source device is defined, reinstall routes to all other devices
if (link.size() == 1) {
log.debug("-- repopulateRoutingRulesForRoutes: running ECMP graph for device {}", link.get(0));
EcmpShortestPathGraph ecmpSpg = new EcmpShortestPathGraph(link.get(0), srManager);
if (populateEcmpRoutingRules(link.get(0), ecmpSpg, ImmutableSet.of())) {
log.debug("Populating flow rules from all to dest:{} is successful",
link.get(0));
currentEcmpSpgMap.put(link.get(0), ecmpSpg);
log.debug("Updating ECMPspg for dest:{}", link.get(0));
} else {
log.warn("Failed to populate the flow rules from all to dest:{}", link.get(0));
return false;
}
} else {
ArrayList<ArrayList<DeviceId>> deviceRoutes =
routesBydevice.get(link.get(1));
if (deviceRoutes == null) {
deviceRoutes = new ArrayList<>();
routesBydevice.put(link.get(1), deviceRoutes);
}
deviceRoutes.add(link);
}
}
for (DeviceId impactedDevice : routesBydevice.keySet()) {
ArrayList<ArrayList<DeviceId>> deviceRoutes =
routesBydevice.get(impactedDevice);
for (ArrayList<DeviceId> link: deviceRoutes) {
log.debug("-- repopulateRoutingRulesForRoutes {} -> {}",
link.get(0), link.get(1));
DeviceId src = link.get(0);
DeviceId dst = link.get(1);
EcmpShortestPathGraph ecmpSpg = updatedEcmpSpgMap.get(dst);
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 targetSw : swViaMap.keySet()) {
if (!targetSw.equals(src)) {
continue;
}
Set<DeviceId> nextHops = new HashSet<>();
for (ArrayList<DeviceId> via : swViaMap.get(targetSw)) {
// in this ECMP path to the targetSw, get the next hop
if (via.isEmpty()) {
nextHops.add(dst);
} else {
nextHops.add(via.get(0));
}
}
if (!populateEcmpRoutingRulePartial(targetSw, dst,
nextHops, ImmutableSet.of())) {
return false;
}
log.debug("Populating flow rules from {} to {} is successful",
targetSw, dst);
}
}
}
//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(impactedDevice,
updatedEcmpSpgMap.get(impactedDevice));
log.debug("Updating ECMPspg for impacted dev:{}", impactedDevice);
}
processHashGroupChange(routeChanges, false, null);
return true;
}
/**
* 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());
if (!srManager.mastershipService.isLocalMaster(sw.id())) {
log.debug("No mastership for {} .. skipping route optimization",
sw.id());
continue;
}
EcmpShortestPathGraph ecmpSpg = currentEcmpSpgMap.get(sw.id());
if (ecmpSpg == null) {
log.warn("No existing ECMP graph for switch {}. Aborting optimized"
+ " rerouting and opting for full-reroute", sw.id());
return null;
}
if (log.isDebugEnabled()) {
log.debug("Root switch: {}", sw.id());
log.debug(" Current/Existing SPG: {}", ecmpSpg);
log.debug(" New/Updated SPG: {}", updatedEcmpSpgMap.get(sw.id()));
}
HashMap<Integer, HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>>> switchVia =
ecmpSpg.getAllLearnedSwitchesAndVia();
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()) {
DeviceId rootSw = sw.id();
if (log.isTraceEnabled()) {
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>> changedRoutesBuilder =
ImmutableSet.builder();
for (Device sw : srManager.deviceService.getDevices()) {
DeviceId rootSw = sw.id();
log.debug("Computing the impacted routes for device {}", rootSw);
if (!srManager.mastershipService.isLocalMaster(rootSw)) {
log.debug("No mastership for {} ... skipping route optimization",
rootSw);
continue;
}
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);
changedRoutesBuilder.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
changedRoutesBuilder.addAll(compareGraphs(newEcmpSpg, currEcmpSpg, rootSw));
// then use the current/existing map to compare to updated/new map
// as switch may have been removed
changedRoutesBuilder.addAll(compareGraphs(currEcmpSpg, newEcmpSpg, rootSw));
}
Set<ArrayList<DeviceId>> changedRoutes = changedRoutesBuilder.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);
route.add(rootSw);
changedRoutesBuilder.add(route);
}
}
}
return changedRoutesBuilder.build();
}
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;
}
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;
}
/**
* Populate ECMP rules for subnets from all switches to destination.
*
* @param destSw Device ID of destination switch
* @param ecmpSPG ECMP shortest path graph
* @param subnets Subnets to be populated. If empty, populate all configured subnets.
* @return true if it succeeds in populating rules
*/
private boolean populateEcmpRoutingRules(DeviceId destSw,
EcmpShortestPathGraph ecmpSPG,
Set<IpPrefix> subnets) {
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 targetSw : swViaMap.keySet()) {
Set<DeviceId> nextHops = new HashSet<>();
log.debug("** Iter: {} root: {} target: {}", itrIdx, destSw, targetSw);
for (ArrayList<DeviceId> via : swViaMap.get(targetSw)) {
if (via.isEmpty()) {
nextHops.add(destSw);
} else {
nextHops.add(via.get(0));
}
}
if (!populateEcmpRoutingRulePartial(targetSw, destSw, nextHops, subnets)) {
return false;
}
}
}
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 destSw Device ID of final destination switch to which the rules will forward
* @param nextHops List of next hops via which destSw will be reached
* @param subnets Subnets to be populated. If empty, populate all configured subnets.
* @return true if it succees in populating rules
*/
private boolean populateEcmpRoutingRulePartial(DeviceId targetSw,
DeviceId destSw,
Set<DeviceId> nextHops,
Set<IpPrefix> subnets) {
boolean result;
if (nextHops.isEmpty()) {
nextHops.add(destSw);
}
// If both target switch and dest switch are edge routers, then set IP
// rule for both subnet and router IP.
boolean targetIsEdge;
boolean destIsEdge;
Ip4Address destRouterIpv4;
Ip6Address destRouterIpv6;
try {
targetIsEdge = config.isEdgeDevice(targetSw);
destIsEdge = config.isEdgeDevice(destSw);
destRouterIpv4 = config.getRouterIpv4(destSw);
destRouterIpv6 = config.getRouterIpv6(destSw);
} catch (DeviceConfigNotFoundException e) {
log.warn(e.getMessage() + " Aborting populateEcmpRoutingRulePartial.");
return false;
}
if (targetIsEdge && destIsEdge) {
subnets = (subnets != null && !subnets.isEmpty()) ? subnets
: config.getSubnets(destSw);
log.debug("* populateEcmpRoutingRulePartial in device {} towards {} "
+ "for subnets {}", targetSw, destSw, subnets);
result = rulePopulator.populateIpRuleForSubnet(targetSw, subnets,
destSw, nextHops);
if (!result) {
return false;
}
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 && destIsEdge) {
// MPLS rules in all non-edge target devices
log.debug("* populateEcmpRoutingRulePartial in device{} towards {} for "
+ "all MPLS rules", targetSw, destSw);
result = rulePopulator.populateMplsRule(targetSw, destSw, nextHops,
destRouterIpv4);
if (!result) {
return false;
}
if (destRouterIpv6 != null) {
result = rulePopulator.populateMplsRule(targetSw, destSw, nextHops,
destRouterIpv6);
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;
}
/**
* 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) {
rulePopulator.populateIpPunts(deviceId);
rulePopulator.populateArpNdpPunts(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);
}
/**
* 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) {
populationStatus = Status.STARTED;
populateAllRoutingRules();
} else {
log.warn("Not initiating startPopulationProcess as populationStatus is {}",
populationStatus);
}
} finally {
statusLock.unlock();
}
}
/**
* Resume the flow rule population process if it was aborted for any reason.
* Mostly the process is aborted when the groups required are not set yet.
* XXX is this called?
*
*/
public void resumePopulationProcess() {
statusLock.lock();
try {
if (populationStatus == Status.ABORTED) {
populationStatus = Status.STARTED;
// TODO: we need to restart from the point aborted instead of
// restarting.
populateAllRoutingRules();
}
} finally {
statusLock.unlock();
}
}
/**
* Populate rules of given subnet at given location.
*
* @param cp connect point of the subnet being added
* @param subnets subnet being added
* @return true if succeed
*/
protected boolean populateSubnet(ConnectPoint cp, Set<IpPrefix> subnets) {
statusLock.lock();
try {
EcmpShortestPathGraph ecmpSpg = currentEcmpSpgMap.get(cp.deviceId());
if (ecmpSpg == null) {
log.warn("Fail to populating subnet {}: {}", subnets, ECMPSPG_MISSING);
return false;
}
return populateEcmpRoutingRules(cp.deviceId(), ecmpSpg, subnets);
} finally {
statusLock.unlock();
}
}
/**
* Revoke rules of given subnet at given location.
*
* @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();
}
}
protected void purgeEcmpGraph(DeviceId deviceId) {
currentEcmpSpgMap.remove(deviceId);
if (updatedEcmpSpgMap != null) {
updatedEcmpSpgMap.remove(deviceId);
}
}
/**
* 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;
}
}
}