blob: 50b0cd218ef6a52eaa55303910d9041e8b23bbd7 [file] [log] [blame]
sangho80f11cb2015-04-01 13:05:26 -07001/*
Brian O'Connor0947d7e2017-08-03 21:12:30 -07002 * Copyright 2015-present Open Networking Foundation
sangho80f11cb2015-04-01 13:05:26 -07003 *
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 */
16package org.onosproject.segmentrouting;
17
Saurav Dasd1872b02016-12-02 15:43:47 -080018import com.google.common.base.MoreObjects;
Saurav Das62ae6792017-05-15 15:34:25 -070019import com.google.common.collect.ImmutableMap;
20import com.google.common.collect.ImmutableMap.Builder;
Charles Chanc22cef32016-04-29 14:38:22 -070021import com.google.common.collect.ImmutableSet;
Saurav Das1b391d52016-11-29 14:27:25 -080022import com.google.common.collect.Lists;
sanghofb7c7292015-04-13 15:15:58 -070023import com.google.common.collect.Maps;
24import com.google.common.collect.Sets;
Saurav Dasfbe74572017-08-03 18:30:35 -070025
26import org.joda.time.DateTime;
sangho9b169e32015-04-14 16:27:13 -070027import org.onlab.packet.Ip4Address;
Pier Ventreadb4ae62016-11-23 09:57:42 -080028import org.onlab.packet.Ip6Address;
sangho80f11cb2015-04-01 13:05:26 -070029import org.onlab.packet.IpPrefix;
Saurav Das261c3002017-06-13 15:35:54 -070030import org.onosproject.cluster.NodeId;
Charles Chanc22cef32016-04-29 14:38:22 -070031import org.onosproject.net.ConnectPoint;
sangho80f11cb2015-04-01 13:05:26 -070032import org.onosproject.net.Device;
33import org.onosproject.net.DeviceId;
sanghofb7c7292015-04-13 15:15:58 -070034import org.onosproject.net.Link;
Charles Chan319d1a22015-11-03 10:42:14 -080035import org.onosproject.segmentrouting.config.DeviceConfigNotFoundException;
36import org.onosproject.segmentrouting.config.DeviceConfiguration;
Saurav Das62ae6792017-05-15 15:34:25 -070037import org.onosproject.segmentrouting.grouphandler.DefaultGroupHandler;
sangho80f11cb2015-04-01 13:05:26 -070038import org.slf4j.Logger;
39import org.slf4j.LoggerFactory;
40
41import java.util.ArrayList;
42import java.util.HashMap;
43import java.util.HashSet;
Saurav Das261c3002017-06-13 15:35:54 -070044import java.util.Iterator;
45import java.util.Map;
Saurav Dasd1872b02016-12-02 15:43:47 -080046import java.util.Objects;
sangho80f11cb2015-04-01 13:05:26 -070047import java.util.Set;
Saurav Das07c74602016-04-27 18:35:50 -070048import java.util.concurrent.ScheduledExecutorService;
49import java.util.concurrent.TimeUnit;
HIGUCHI Yuta16d8fd52015-09-08 16:16:31 +090050import java.util.concurrent.locks.Lock;
51import java.util.concurrent.locks.ReentrantLock;
sangho80f11cb2015-04-01 13:05:26 -070052
Saurav Dasd1872b02016-12-02 15:43:47 -080053import static com.google.common.base.MoreObjects.toStringHelper;
Pier Ventreadb4ae62016-11-23 09:57:42 -080054import static com.google.common.base.Preconditions.checkNotNull;
55import static java.util.concurrent.Executors.newScheduledThreadPool;
56import static org.onlab.util.Tools.groupedThreads;
sangho80f11cb2015-04-01 13:05:26 -070057
Charles Chanb7f75ac2016-01-11 18:28:54 -080058/**
59 * Default routing handler that is responsible for route computing and
60 * routing rule population.
61 */
sangho80f11cb2015-04-01 13:05:26 -070062public class DefaultRoutingHandler {
Saurav Dasf9332192017-02-18 14:05:44 -080063 private static final int MAX_CONSTANT_RETRY_ATTEMPTS = 5;
64 private static final int RETRY_INTERVAL_MS = 250;
65 private static final int RETRY_INTERVAL_SCALE = 1;
Saurav Dasfbe74572017-08-03 18:30:35 -070066 private static final long STABLITY_THRESHOLD = 10; //secs
Saurav Dasfe0b05e2017-08-14 16:44:43 -070067 private static final int UPDATE_INTERVAL = 5; //secs
Charles Chanc22cef32016-04-29 14:38:22 -070068 private static Logger log = LoggerFactory.getLogger(DefaultRoutingHandler.class);
sangho80f11cb2015-04-01 13:05:26 -070069
70 private SegmentRoutingManager srManager;
71 private RoutingRulePopulator rulePopulator;
Shashikanth VH0637b162015-12-11 01:32:44 +053072 private HashMap<DeviceId, EcmpShortestPathGraph> currentEcmpSpgMap;
73 private HashMap<DeviceId, EcmpShortestPathGraph> updatedEcmpSpgMap;
sangho9b169e32015-04-14 16:27:13 -070074 private DeviceConfiguration config;
HIGUCHI Yuta16d8fd52015-09-08 16:16:31 +090075 private final Lock statusLock = new ReentrantLock();
76 private volatile Status populationStatus;
Yuta HIGUCHIebee2f12016-07-21 16:54:33 -070077 private ScheduledExecutorService executorService
Saurav Dasd1872b02016-12-02 15:43:47 -080078 = newScheduledThreadPool(1, groupedThreads("retryftr", "retry-%d", log));
Saurav Dasfbe74572017-08-03 18:30:35 -070079 private DateTime lastRoutingChange;
sangho80f11cb2015-04-01 13:05:26 -070080
81 /**
82 * Represents the default routing population status.
83 */
84 public enum Status {
85 // population process is not started yet.
86 IDLE,
87
88 // population process started.
89 STARTED,
90
Srikanth Vavilapalli64505482015-04-21 13:04:13 -070091 // population process was aborted due to errors, mostly for groups not
92 // found.
sangho80f11cb2015-04-01 13:05:26 -070093 ABORTED,
94
95 // population process was finished successfully.
96 SUCCEEDED
97 }
98
99 /**
100 * Creates a DefaultRoutingHandler object.
101 *
102 * @param srManager SegmentRoutingManager object
103 */
104 public DefaultRoutingHandler(SegmentRoutingManager srManager) {
105 this.srManager = srManager;
106 this.rulePopulator = checkNotNull(srManager.routingRulePopulator);
sangho9b169e32015-04-14 16:27:13 -0700107 this.config = checkNotNull(srManager.deviceConfiguration);
sangho80f11cb2015-04-01 13:05:26 -0700108 this.populationStatus = Status.IDLE;
sanghofb7c7292015-04-13 15:15:58 -0700109 this.currentEcmpSpgMap = Maps.newHashMap();
sangho80f11cb2015-04-01 13:05:26 -0700110 }
111
112 /**
Saurav Das62ae6792017-05-15 15:34:25 -0700113 * Returns an immutable copy of the current ECMP shortest-path graph as
114 * computed by this controller instance.
115 *
Saurav Das261c3002017-06-13 15:35:54 -0700116 * @return immutable copy of the current ECMP graph
Saurav Das62ae6792017-05-15 15:34:25 -0700117 */
118 public ImmutableMap<DeviceId, EcmpShortestPathGraph> getCurrentEmcpSpgMap() {
119 Builder<DeviceId, EcmpShortestPathGraph> builder = ImmutableMap.builder();
120 currentEcmpSpgMap.entrySet().forEach(entry -> {
121 if (entry.getValue() != null) {
122 builder.put(entry.getKey(), entry.getValue());
123 }
124 });
125 return builder.build();
126 }
127
Saurav Dasfbe74572017-08-03 18:30:35 -0700128 /**
129 * Acquires the lock used when making routing changes.
130 */
131 public void acquireRoutingLock() {
132 statusLock.lock();
133 }
134
135 /**
136 * Releases the lock used when making routing changes.
137 */
138 public void releaseRoutingLock() {
139 statusLock.unlock();
140 }
141
142 /**
143 * Determines if routing in the network has been stable in the last
144 * STABLITY_THRESHOLD seconds, by comparing the current time to the last
145 * routing change timestamp.
146 *
147 * @return true if stable
148 */
149 public boolean isRoutingStable() {
150 long last = (long) (lastRoutingChange.getMillis() / 1000.0);
151 long now = (long) (DateTime.now().getMillis() / 1000.0);
Saurav Dasfe0b05e2017-08-14 16:44:43 -0700152 log.trace("Routing stable since {}s", now - last);
Saurav Dasfbe74572017-08-03 18:30:35 -0700153 return (now - last) > STABLITY_THRESHOLD;
154 }
155
156
Saurav Das261c3002017-06-13 15:35:54 -0700157 //////////////////////////////////////
158 // Route path handling
159 //////////////////////////////////////
160
161 /* The following three methods represent the three major ways in routing
162 * is triggered in the network
163 * a) due to configuration change
164 * b) due to route-added event
165 * c) due to change in the topology
166 */
167
Saurav Das62ae6792017-05-15 15:34:25 -0700168 /**
Saurav Das261c3002017-06-13 15:35:54 -0700169 * Populates all routing rules to all switches. Typically triggered at
170 * startup or after a configuration event.
sangho80f11cb2015-04-01 13:05:26 -0700171 */
Saurav Das62ae6792017-05-15 15:34:25 -0700172 public void populateAllRoutingRules() {
Saurav Dasfbe74572017-08-03 18:30:35 -0700173 lastRoutingChange = DateTime.now();
HIGUCHI Yuta16d8fd52015-09-08 16:16:31 +0900174 statusLock.lock();
175 try {
Saurav Das261c3002017-06-13 15:35:54 -0700176 if (populationStatus == Status.STARTED) {
177 log.warn("Previous rule population is not finished. Cannot"
178 + " proceed with populateAllRoutingRules");
179 return;
180 }
181
HIGUCHI Yuta16d8fd52015-09-08 16:16:31 +0900182 populationStatus = Status.STARTED;
183 rulePopulator.resetCounter();
Saurav Das261c3002017-06-13 15:35:54 -0700184 log.info("Starting to populate all routing rules");
HIGUCHI Yuta16d8fd52015-09-08 16:16:31 +0900185 log.debug("populateAllRoutingRules: populationStatus is STARTED");
sangho80f11cb2015-04-01 13:05:26 -0700186
Saurav Das261c3002017-06-13 15:35:54 -0700187 // take a snapshot of the topology
188 updatedEcmpSpgMap = new HashMap<>();
189 Set<EdgePair> edgePairs = new HashSet<>();
190 Set<ArrayList<DeviceId>> routeChanges = new HashSet<>();
191 for (Device dstSw : srManager.deviceService.getDevices()) {
192 EcmpShortestPathGraph ecmpSpgUpdated =
193 new EcmpShortestPathGraph(dstSw.id(), srManager);
194 updatedEcmpSpgMap.put(dstSw.id(), ecmpSpgUpdated);
195 DeviceId pairDev = getPairDev(dstSw.id());
196 if (pairDev != null) {
197 // pairDev may not be available yet, but we still need to add
198 ecmpSpgUpdated = new EcmpShortestPathGraph(pairDev, srManager);
199 updatedEcmpSpgMap.put(pairDev, ecmpSpgUpdated);
200 edgePairs.add(new EdgePair(dstSw.id(), pairDev));
201 }
202 DeviceId ret = shouldHandleRouting(dstSw.id());
203 if (ret == null) {
HIGUCHI Yuta16d8fd52015-09-08 16:16:31 +0900204 continue;
205 }
Saurav Das261c3002017-06-13 15:35:54 -0700206 Set<DeviceId> devsToProcess = Sets.newHashSet(dstSw.id(), ret);
207 // To do a full reroute, assume all routes have changed
208 for (DeviceId dev : devsToProcess) {
209 for (Device targetSw : srManager.deviceService.getDevices()) {
210 if (targetSw.id().equals(dev)) {
211 continue;
212 }
213 routeChanges.add(Lists.newArrayList(targetSw.id(), dev));
214 }
HIGUCHI Yuta16d8fd52015-09-08 16:16:31 +0900215 }
Saurav Das261c3002017-06-13 15:35:54 -0700216 }
HIGUCHI Yuta16d8fd52015-09-08 16:16:31 +0900217
Saurav Das261c3002017-06-13 15:35:54 -0700218 if (!redoRouting(routeChanges, edgePairs, null)) {
219 log.debug("populateAllRoutingRules: populationStatus is ABORTED");
220 populationStatus = Status.ABORTED;
221 log.warn("Failed to repopulate all routing rules.");
222 return;
sangho80f11cb2015-04-01 13:05:26 -0700223 }
224
HIGUCHI Yuta16d8fd52015-09-08 16:16:31 +0900225 log.debug("populateAllRoutingRules: populationStatus is SUCCEEDED");
226 populationStatus = Status.SUCCEEDED;
Saurav Das261c3002017-06-13 15:35:54 -0700227 log.info("Completed all routing rule population. Total # of rules pushed : {}",
HIGUCHI Yuta16d8fd52015-09-08 16:16:31 +0900228 rulePopulator.getCounter());
Saurav Das62ae6792017-05-15 15:34:25 -0700229 return;
HIGUCHI Yuta16d8fd52015-09-08 16:16:31 +0900230 } finally {
231 statusLock.unlock();
sangho80f11cb2015-04-01 13:05:26 -0700232 }
sangho80f11cb2015-04-01 13:05:26 -0700233 }
234
sanghofb7c7292015-04-13 15:15:58 -0700235 /**
Saurav Das261c3002017-06-13 15:35:54 -0700236 * Populate rules from all other edge devices to the connect-point(s)
237 * specified for the given subnets.
238 *
239 * @param cpts connect point(s) of the subnets being added
240 * @param subnets subnets being added
241 */ //XXX refactor
242 protected void populateSubnet(Set<ConnectPoint> cpts, Set<IpPrefix> subnets) {
Saurav Dasfbe74572017-08-03 18:30:35 -0700243 lastRoutingChange = DateTime.now();
Saurav Das261c3002017-06-13 15:35:54 -0700244 statusLock.lock();
245 try {
246 if (populationStatus == Status.STARTED) {
247 log.warn("Previous rule population is not finished. Cannot"
248 + " proceed with routing rules for added routes");
249 return;
250 }
251 populationStatus = Status.STARTED;
252 rulePopulator.resetCounter();
253 log.info("Starting to populate routing rules for added routes");
254 // Take snapshots of the topology
255 updatedEcmpSpgMap = new HashMap<>();
256 Set<EdgePair> edgePairs = new HashSet<>();
257 Set<ArrayList<DeviceId>> routeChanges = new HashSet<>();
258 boolean handleRouting = false;
259
260 if (cpts.size() == 2) {
261 // ensure connect points are edge-pairs
262 Iterator<ConnectPoint> iter = cpts.iterator();
263 DeviceId dev1 = iter.next().deviceId();
264 DeviceId pairDev = getPairDev(dev1);
265 if (iter.next().deviceId().equals(pairDev)) {
266 edgePairs.add(new EdgePair(dev1, pairDev));
267 } else {
268 log.warn("Connectpoints {} for subnets {} not on "
269 + "pair-devices.. aborting populateSubnet", cpts, subnets);
270 populationStatus = Status.ABORTED;
271 return;
272 }
273 for (ConnectPoint cp : cpts) {
274 EcmpShortestPathGraph ecmpSpgUpdated =
275 new EcmpShortestPathGraph(cp.deviceId(), srManager);
276 updatedEcmpSpgMap.put(cp.deviceId(), ecmpSpgUpdated);
277 DeviceId retId = shouldHandleRouting(cp.deviceId());
278 if (retId == null) {
279 continue;
280 }
281 handleRouting = true;
282 }
283 } else {
284 // single connect point
285 DeviceId dstSw = cpts.iterator().next().deviceId();
286 EcmpShortestPathGraph ecmpSpgUpdated =
287 new EcmpShortestPathGraph(dstSw, srManager);
288 updatedEcmpSpgMap.put(dstSw, ecmpSpgUpdated);
289 if (srManager.mastershipService.isLocalMaster(dstSw)) {
290 handleRouting = true;
291 }
292 }
293
294 if (!handleRouting) {
295 log.debug("This instance is not handling ecmp routing to the "
296 + "connectPoint(s) {}", cpts);
297 populationStatus = Status.ABORTED;
298 return;
299 }
300
301 // if it gets here, this instance should handle routing for the
302 // connectpoint(s). Assume all route-paths have to be updated to
303 // the connectpoint(s) with the following exceptions
304 // 1. if target is non-edge no need for routing rules
305 // 2. if target is one of the connectpoints
306 for (ConnectPoint cp : cpts) {
307 DeviceId dstSw = cp.deviceId();
308 for (Device targetSw : srManager.deviceService.getDevices()) {
309 boolean isEdge = false;
310 try {
311 isEdge = config.isEdgeDevice(targetSw.id());
312 } catch (DeviceConfigNotFoundException e) {
313 log.warn(e.getMessage() + "aborting populateSubnet");
314 populationStatus = Status.ABORTED;
315 return;
316 }
317 if (dstSw.equals(targetSw.id()) || !isEdge ||
318 (cpts.size() == 2 &&
319 targetSw.id().equals(getPairDev(dstSw)))) {
320 continue;
321 }
322 routeChanges.add(Lists.newArrayList(targetSw.id(), dstSw));
323 }
324 }
325
326 if (!redoRouting(routeChanges, edgePairs, subnets)) {
327 log.debug("populateSubnet: populationStatus is ABORTED");
328 populationStatus = Status.ABORTED;
329 log.warn("Failed to repopulate the rules for subnet.");
330 return;
331 }
332
333 log.debug("populateSubnet: populationStatus is SUCCEEDED");
334 populationStatus = Status.SUCCEEDED;
335 log.info("Completed subnet population. Total # of rules pushed : {}",
336 rulePopulator.getCounter());
337 return;
338
339 } finally {
340 statusLock.unlock();
341 }
342 }
343
344 /**
Saurav Das62ae6792017-05-15 15:34:25 -0700345 * Populates the routing rules or makes hash group changes according to the
346 * route-path changes due to link failure, switch failure or link up. This
347 * method should only be called for one of these three possible event-types.
348 * Note that when a switch goes away, all of its links fail as well,
349 * but this is handled as a single switch removal event.
sanghofb7c7292015-04-13 15:15:58 -0700350 *
Saurav Das62ae6792017-05-15 15:34:25 -0700351 * @param linkDown the single failed link, or null for other conditions
352 * such as link-up or a removed switch
353 * @param linkUp the single link up, or null for other conditions such as
354 * link-down or a removed switch
355 * @param switchDown the removed switch, or null for other conditions such as
356 * link-down or link-up
Saurav Das261c3002017-06-13 15:35:54 -0700357 */ // refactor
Saurav Das62ae6792017-05-15 15:34:25 -0700358 public void populateRoutingRulesForLinkStatusChange(Link linkDown,
359 Link linkUp,
360 DeviceId switchDown) {
361 if ((linkDown != null && (linkUp != null || switchDown != null)) ||
362 (linkUp != null && (linkDown != null || switchDown != null)) ||
363 (switchDown != null && (linkUp != null || linkDown != null))) {
364 log.warn("Only one event can be handled for link status change .. aborting");
365 return;
366 }
Saurav Dasfbe74572017-08-03 18:30:35 -0700367 lastRoutingChange = DateTime.now();
Saurav Dasfe0b05e2017-08-14 16:44:43 -0700368 executorService.schedule(new UpdateMaps(), UPDATE_INTERVAL,
369 TimeUnit.SECONDS);
HIGUCHI Yuta16d8fd52015-09-08 16:16:31 +0900370 statusLock.lock();
371 try {
sanghofb7c7292015-04-13 15:15:58 -0700372
373 if (populationStatus == Status.STARTED) {
Saurav Das261c3002017-06-13 15:35:54 -0700374 log.warn("Previous rule population is not finished. Cannot"
375 + " proceeed with routingRules for Link Status change");
Saurav Das62ae6792017-05-15 15:34:25 -0700376 return;
sanghofb7c7292015-04-13 15:15:58 -0700377 }
378
Saurav Das261c3002017-06-13 15:35:54 -0700379 // Take snapshots of the topology
sangho28d0b6d2015-05-07 13:30:57 -0700380 updatedEcmpSpgMap = new HashMap<>();
Saurav Das261c3002017-06-13 15:35:54 -0700381 Set<EdgePair> edgePairs = new HashSet<>();
sangho28d0b6d2015-05-07 13:30:57 -0700382 for (Device sw : srManager.deviceService.getDevices()) {
Shashikanth VH0637b162015-12-11 01:32:44 +0530383 EcmpShortestPathGraph ecmpSpgUpdated =
384 new EcmpShortestPathGraph(sw.id(), srManager);
sangho28d0b6d2015-05-07 13:30:57 -0700385 updatedEcmpSpgMap.put(sw.id(), ecmpSpgUpdated);
Saurav Das261c3002017-06-13 15:35:54 -0700386 DeviceId pairDev = getPairDev(sw.id());
387 if (pairDev != null) {
388 // pairDev may not be available yet, but we still need to add
389 ecmpSpgUpdated = new EcmpShortestPathGraph(pairDev, srManager);
390 updatedEcmpSpgMap.put(pairDev, ecmpSpgUpdated);
391 edgePairs.add(new EdgePair(sw.id(), pairDev));
392 }
sangho28d0b6d2015-05-07 13:30:57 -0700393 }
394
Saurav Das261c3002017-06-13 15:35:54 -0700395 log.info("Starting to populate routing rules from link status change");
sanghodf0153f2015-05-05 14:13:34 -0700396
sanghofb7c7292015-04-13 15:15:58 -0700397 Set<ArrayList<DeviceId>> routeChanges;
Saurav Das62ae6792017-05-15 15:34:25 -0700398 log.debug("populateRoutingRulesForLinkStatusChange: "
Srikanth Vavilapalli7cd16712015-05-04 09:48:09 -0700399 + "populationStatus is STARTED");
sanghofb7c7292015-04-13 15:15:58 -0700400 populationStatus = Status.STARTED;
Saurav Das261c3002017-06-13 15:35:54 -0700401 rulePopulator.resetCounter();
Saurav Das1b391d52016-11-29 14:27:25 -0800402 // try optimized re-routing
Saurav Das62ae6792017-05-15 15:34:25 -0700403 if (linkDown == null) {
404 // either a linkUp or a switchDown - compute all route changes by
405 // comparing all routes of existing ECMP SPG to new ECMP SPG
sanghofb7c7292015-04-13 15:15:58 -0700406 routeChanges = computeRouteChange();
Saurav Das62ae6792017-05-15 15:34:25 -0700407
Saurav Dasfe0b05e2017-08-14 16:44:43 -0700408 // deal with linkUp of a seen-before link
409 if (linkUp != null && srManager.isSeenLink(linkUp)) {
410 if (!srManager.isBidirectional(linkUp)) {
411 log.warn("Not a bidirectional link yet .. not "
412 + "processing link {}", linkUp);
413 srManager.updateSeenLink(linkUp, true);
414 populationStatus = Status.ABORTED;
415 return;
Saurav Das62ae6792017-05-15 15:34:25 -0700416 }
Saurav Dasfe0b05e2017-08-14 16:44:43 -0700417 // link previously seen before
418 // do hash-bucket changes instead of a re-route
419 processHashGroupChange(routeChanges, false, null);
420 // clear out routesChanges so a re-route is not attempted
421 routeChanges = ImmutableSet.of();
Saurav Das62ae6792017-05-15 15:34:25 -0700422 }
Saurav Dasfe0b05e2017-08-14 16:44:43 -0700423 // for a linkUp of a never-seen-before link
424 // let it fall through to a reroute of the routeChanges
Saurav Das62ae6792017-05-15 15:34:25 -0700425
426 // now that we are past the check for a previously seen link
427 // it is safe to update the store for the linkUp
428 if (linkUp != null) {
429 srManager.updateSeenLink(linkUp, true);
430 }
431
Saurav Dasfe0b05e2017-08-14 16:44:43 -0700432 //deal with switchDown
433 if (switchDown != null) {
434 processHashGroupChange(routeChanges, true, switchDown);
435 // clear out routesChanges so a re-route is not attempted
436 routeChanges = ImmutableSet.of();
437 }
sanghofb7c7292015-04-13 15:15:58 -0700438 } else {
Saurav Das62ae6792017-05-15 15:34:25 -0700439 // link has gone down
440 // Compare existing ECMP SPG only with the link that went down
441 routeChanges = computeDamagedRoutes(linkDown);
442 if (routeChanges != null) {
443 processHashGroupChange(routeChanges, true, null);
444 // clear out routesChanges so a re-route is not attempted
445 routeChanges = ImmutableSet.of();
446 }
sanghofb7c7292015-04-13 15:15:58 -0700447 }
448
Saurav Das1b391d52016-11-29 14:27:25 -0800449 // do full re-routing if optimized routing returns null routeChanges
Saurav Dasb149be12016-06-07 10:08:06 -0700450 if (routeChanges == null) {
Saurav Das261c3002017-06-13 15:35:54 -0700451 log.info("Optimized routing failed... opting for full reroute");
452 populationStatus = Status.ABORTED;
Saurav Das62ae6792017-05-15 15:34:25 -0700453 populateAllRoutingRules();
454 return;
Saurav Dasb149be12016-06-07 10:08:06 -0700455 }
456
sanghofb7c7292015-04-13 15:15:58 -0700457 if (routeChanges.isEmpty()) {
Saurav Das62ae6792017-05-15 15:34:25 -0700458 log.info("No re-route attempted for the link status change");
Srikanth Vavilapalli7cd16712015-05-04 09:48:09 -0700459 log.debug("populateRoutingRulesForLinkStatusChange: populationStatus is SUCCEEDED");
sanghofb7c7292015-04-13 15:15:58 -0700460 populationStatus = Status.SUCCEEDED;
Saurav Das62ae6792017-05-15 15:34:25 -0700461 return;
sanghofb7c7292015-04-13 15:15:58 -0700462 }
463
Saurav Das62ae6792017-05-15 15:34:25 -0700464 // reroute of routeChanges
Saurav Das261c3002017-06-13 15:35:54 -0700465 if (redoRouting(routeChanges, edgePairs, null)) {
Srikanth Vavilapalli7cd16712015-05-04 09:48:09 -0700466 log.debug("populateRoutingRulesForLinkStatusChange: populationStatus is SUCCEEDED");
sanghofb7c7292015-04-13 15:15:58 -0700467 populationStatus = Status.SUCCEEDED;
Saurav Das261c3002017-06-13 15:35:54 -0700468 log.info("Completed repopulation of rules for link-status change."
469 + " # of rules populated : {}", rulePopulator.getCounter());
Saurav Das62ae6792017-05-15 15:34:25 -0700470 return;
sanghofb7c7292015-04-13 15:15:58 -0700471 } else {
Srikanth Vavilapalli7cd16712015-05-04 09:48:09 -0700472 log.debug("populateRoutingRulesForLinkStatusChange: populationStatus is ABORTED");
sanghofb7c7292015-04-13 15:15:58 -0700473 populationStatus = Status.ABORTED;
Saurav Das261c3002017-06-13 15:35:54 -0700474 log.warn("Failed to repopulate the rules for link status change.");
Saurav Das62ae6792017-05-15 15:34:25 -0700475 return;
sanghofb7c7292015-04-13 15:15:58 -0700476 }
HIGUCHI Yuta16d8fd52015-09-08 16:16:31 +0900477 } finally {
478 statusLock.unlock();
sanghofb7c7292015-04-13 15:15:58 -0700479 }
480 }
481
Saurav Dasfe0b05e2017-08-14 16:44:43 -0700482
Saurav Das62ae6792017-05-15 15:34:25 -0700483 /**
Saurav Das261c3002017-06-13 15:35:54 -0700484 * Processes a set a route-path changes by reprogramming routing rules and
485 * creating new hash-groups or editing them if necessary. This method also
486 * determines the next-hops for the route-path from the src-switch (target)
487 * of the path towards the dst-switch of the path.
Saurav Das62ae6792017-05-15 15:34:25 -0700488 *
Saurav Das261c3002017-06-13 15:35:54 -0700489 * @param routeChanges a set of route-path changes, where each route-path is
490 * a list with its first element the src-switch (target)
491 * of the path, and the second element the dst-switch of
492 * the path.
493 * @param edgePairs a set of edge-switches that are paired by configuration
494 * @param subnets a set of prefixes that need to be populated in the routing
495 * table of the target switch in the route-path. Can be null,
496 * in which case all the prefixes belonging to the dst-switch
497 * will be populated in the target switch
498 * @return true if successful in repopulating all routes
Saurav Das62ae6792017-05-15 15:34:25 -0700499 */
Saurav Das261c3002017-06-13 15:35:54 -0700500 private boolean redoRouting(Set<ArrayList<DeviceId>> routeChanges,
501 Set<EdgePair> edgePairs, Set<IpPrefix> subnets) {
502 // first make every entry two-elements
503 Set<ArrayList<DeviceId>> changedRoutes = new HashSet<>();
504 for (ArrayList<DeviceId> route : routeChanges) {
505 if (route.size() == 1) {
506 DeviceId dstSw = route.get(0);
507 EcmpShortestPathGraph ec = updatedEcmpSpgMap.get(dstSw);
508 if (ec == null) {
509 log.warn("No graph found for {} .. aborting redoRouting", dstSw);
510 return false;
511 }
512 ec.getAllLearnedSwitchesAndVia().keySet().forEach(key -> {
513 ec.getAllLearnedSwitchesAndVia().get(key).keySet().forEach(target -> {
514 changedRoutes.add(Lists.newArrayList(target, dstSw));
515 });
516 });
517 } else {
518 DeviceId targetSw = route.get(0);
519 DeviceId dstSw = route.get(1);
520 changedRoutes.add(Lists.newArrayList(targetSw, dstSw));
521 }
522 }
523
524 // now process changedRoutes according to edgePairs
525 if (!redoRoutingEdgePairs(edgePairs, subnets, changedRoutes)) {
526 return false; //abort routing and fail fast
527 }
528
529 // whatever is left in changedRoutes is now processed for individual dsts.
530 if (!redoRoutingIndividualDests(subnets, changedRoutes)) {
531 return false; //abort routing and fail fast
532 }
533
Saurav Das261c3002017-06-13 15:35:54 -0700534 // update ecmpSPG for all edge-pairs
535 for (EdgePair ep : edgePairs) {
536 currentEcmpSpgMap.put(ep.dev1, updatedEcmpSpgMap.get(ep.dev1));
537 currentEcmpSpgMap.put(ep.dev2, updatedEcmpSpgMap.get(ep.dev2));
538 log.debug("Updating ECMPspg for edge-pair:{}-{}", ep.dev1, ep.dev2);
539 }
540 return true;
541 }
542
543 /**
544 * Programs targetSw in the changedRoutes for given prefixes reachable by
545 * an edgePair. If no prefixes are given, the method will use configured
546 * subnets/prefixes. If some configured subnets belong only to a specific
547 * destination in the edgePair, then the target switch will be programmed
548 * only to that destination.
549 *
550 * @param edgePairs set of edge-pairs for which target will be programmed
551 * @param subnets a set of prefixes that need to be populated in the routing
552 * table of the target switch in the changedRoutes. Can be null,
553 * in which case all the configured prefixes belonging to the
554 * paired switches will be populated in the target switch
555 * @param changedRoutes a set of route-path changes, where each route-path is
556 * a list with its first element the src-switch (target)
557 * of the path, and the second element the dst-switch of
558 * the path.
559 * @return true if successful
560 */
561 private boolean redoRoutingEdgePairs(Set<EdgePair> edgePairs,
562 Set<IpPrefix> subnets,
563 Set<ArrayList<DeviceId>> changedRoutes) {
564 for (EdgePair ep : edgePairs) {
565 // temp store for a target's changedRoutes to this edge-pair
566 Map<DeviceId, Set<ArrayList<DeviceId>>> targetRoutes = new HashMap<>();
567 Iterator<ArrayList<DeviceId>> i = changedRoutes.iterator();
568 while (i.hasNext()) {
569 ArrayList<DeviceId> route = i.next();
570 DeviceId dstSw = route.get(1);
571 if (ep.includes(dstSw)) {
572 // routeChange for edge pair found
573 // sort by target iff target is edge and remove from changedRoutes
574 DeviceId targetSw = route.get(0);
575 try {
576 if (!srManager.deviceConfiguration.isEdgeDevice(targetSw)) {
577 continue;
578 }
579 } catch (DeviceConfigNotFoundException e) {
580 log.warn(e.getMessage() + "aborting redoRouting");
581 return false;
582 }
583 // route is from another edge to this edge-pair
584 if (targetRoutes.containsKey(targetSw)) {
585 targetRoutes.get(targetSw).add(route);
586 } else {
587 Set<ArrayList<DeviceId>> temp = new HashSet<>();
588 temp.add(route);
589 targetRoutes.put(targetSw, temp);
590 }
591 i.remove();
592 }
593 }
594 // so now for this edgepair we have a per target set of routechanges
595 // process target->edgePair route
596 for (Map.Entry<DeviceId, Set<ArrayList<DeviceId>>> entry :
597 targetRoutes.entrySet()) {
598 log.debug("* redoRoutingDstPair Target:{} -> edge-pair {}",
599 entry.getKey(), ep);
600 DeviceId targetSw = entry.getKey();
601 Map<DeviceId, Set<DeviceId>> perDstNextHops = new HashMap<>();
602 entry.getValue().forEach(route -> {
603 Set<DeviceId> nhops = getNextHops(route.get(0), route.get(1));
604 log.debug("route: target {} -> dst {} found with next-hops {}",
605 route.get(0), route.get(1), nhops);
606 perDstNextHops.put(route.get(1), nhops);
607 });
608 Set<IpPrefix> ipDev1 = (subnets == null) ? config.getSubnets(ep.dev1)
609 : subnets;
610 Set<IpPrefix> ipDev2 = (subnets == null) ? config.getSubnets(ep.dev2)
611 : subnets;
612 ipDev1 = (ipDev1 == null) ? Sets.newHashSet() : ipDev1;
613 ipDev2 = (ipDev2 == null) ? Sets.newHashSet() : ipDev2;
614 // handle routing to subnets common to edge-pair
615 // only if the targetSw is not part of the edge-pair
616 if (!ep.includes(targetSw)) {
617 if (!populateEcmpRoutingRulePartial(
618 targetSw,
619 ep.dev1, ep.dev2,
620 perDstNextHops,
621 Sets.intersection(ipDev1, ipDev2))) {
622 return false; // abort everything and fail fast
623 }
624 }
625 // handle routing to subnets that only belong to dev1
626 Set<IpPrefix> onlyDev1Subnets = Sets.difference(ipDev1, ipDev2);
627 if (!onlyDev1Subnets.isEmpty() && perDstNextHops.get(ep.dev1) != null) {
628 Map<DeviceId, Set<DeviceId>> onlyDev1NextHops = new HashMap<>();
629 onlyDev1NextHops.put(ep.dev1, perDstNextHops.get(ep.dev1));
630 if (!populateEcmpRoutingRulePartial(
631 targetSw,
632 ep.dev1, null,
633 onlyDev1NextHops,
634 onlyDev1Subnets)) {
635 return false; // abort everything and fail fast
636 }
637 }
638 // handle routing to subnets that only belong to dev2
639 Set<IpPrefix> onlyDev2Subnets = Sets.difference(ipDev2, ipDev1);
640 if (!onlyDev2Subnets.isEmpty() && perDstNextHops.get(ep.dev2) != null) {
641 Map<DeviceId, Set<DeviceId>> onlyDev2NextHops = new HashMap<>();
642 onlyDev2NextHops.put(ep.dev2, perDstNextHops.get(ep.dev2));
643 if (!populateEcmpRoutingRulePartial(
644 targetSw,
645 ep.dev2, null,
646 onlyDev2NextHops,
647 onlyDev2Subnets)) {
648 return false; // abort everything and fail fast
649 }
650 }
651 }
652 // if it gets here it has succeeded for all targets to this edge-pair
653 }
654 return true;
655 }
656
657 /**
658 * Programs targetSw in the changedRoutes for given prefixes reachable by
659 * a destination switch that is not part of an edge-pair.
660 * If no prefixes are given, the method will use configured subnets/prefixes.
661 *
662 * @param subnets a set of prefixes that need to be populated in the routing
663 * table of the target switch in the changedRoutes. Can be null,
664 * in which case all the configured prefixes belonging to the
665 * paired switches will be populated in the target switch
666 * @param changedRoutes a set of route-path changes, where each route-path is
667 * a list with its first element the src-switch (target)
668 * of the path, and the second element the dst-switch of
669 * the path.
670 * @return true if successful
671 */
672 private boolean redoRoutingIndividualDests(Set<IpPrefix> subnets,
673 Set<ArrayList<DeviceId>> changedRoutes) {
674 // aggregate route-path changes for each dst device
675 HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>> routesBydevice =
676 new HashMap<>();
677 for (ArrayList<DeviceId> route: changedRoutes) {
678 DeviceId dstSw = route.get(1);
679 ArrayList<ArrayList<DeviceId>> deviceRoutes =
680 routesBydevice.get(dstSw);
681 if (deviceRoutes == null) {
682 deviceRoutes = new ArrayList<>();
683 routesBydevice.put(dstSw, deviceRoutes);
684 }
685 deviceRoutes.add(route);
686 }
687 for (DeviceId impactedDstDevice : routesBydevice.keySet()) {
688 ArrayList<ArrayList<DeviceId>> deviceRoutes =
689 routesBydevice.get(impactedDstDevice);
690 for (ArrayList<DeviceId> route: deviceRoutes) {
691 log.debug("* redoRoutingIndiDst Target: {} -> dst: {}",
692 route.get(0), route.get(1));
693 DeviceId targetSw = route.get(0);
694 DeviceId dstSw = route.get(1); // same as impactedDstDevice
695 Set<DeviceId> nextHops = getNextHops(targetSw, dstSw);
696 Map<DeviceId, Set<DeviceId>> nhops = new HashMap<>();
697 nhops.put(dstSw, nextHops);
698 if (!populateEcmpRoutingRulePartial(targetSw, dstSw, null, nhops,
699 (subnets == null) ? Sets.newHashSet() : subnets)) {
700 return false; // abort routing and fail fast
701 }
702 log.debug("Populating flow rules from target: {} to dst: {}"
703 + " is successful", targetSw, dstSw);
704 }
705 //Only if all the flows for all impacted routes to a
706 //specific target are pushed successfully, update the
707 //ECMP graph for that target. Or else the next event
708 //would not see any changes in the ECMP graphs.
709 //In another case, the target switch has gone away, so
710 //routes can't be installed. In that case, the current map
711 //is updated here, without any flows being pushed.
712 currentEcmpSpgMap.put(impactedDstDevice,
713 updatedEcmpSpgMap.get(impactedDstDevice));
714 log.debug("Updating ECMPspg for impacted dev:{}", impactedDstDevice);
715 }
716 return true;
717 }
718
719 /**
720 * Populate ECMP rules for subnets from target to destination via nexthops.
721 *
722 * @param targetSw Device ID of target switch in which rules will be programmed
723 * @param destSw1 Device ID of final destination switch to which the rules will forward
724 * @param destSw2 Device ID of paired destination switch to which the rules will forward
725 * A null deviceId indicates packets should only be sent to destSw1
726 * @param nextHops Map indication a list of next hops per destSw
727 * @param subnets Subnets to be populated. If empty, populate all configured subnets.
728 * @return true if it succeeds in populating rules
729 */ // refactor
730 private boolean populateEcmpRoutingRulePartial(DeviceId targetSw,
731 DeviceId destSw1,
732 DeviceId destSw2,
733 Map<DeviceId, Set<DeviceId>> nextHops,
734 Set<IpPrefix> subnets) {
735 boolean result;
736 // If both target switch and dest switch are edge routers, then set IP
737 // rule for both subnet and router IP.
738 boolean targetIsEdge;
739 boolean dest1IsEdge;
740 Ip4Address dest1RouterIpv4, dest2RouterIpv4 = null;
741 Ip6Address dest1RouterIpv6, dest2RouterIpv6 = null;
742
743 try {
744 targetIsEdge = config.isEdgeDevice(targetSw);
745 dest1IsEdge = config.isEdgeDevice(destSw1);
746 dest1RouterIpv4 = config.getRouterIpv4(destSw1);
747 dest1RouterIpv6 = config.getRouterIpv6(destSw1);
748 if (destSw2 != null) {
749 dest2RouterIpv4 = config.getRouterIpv4(destSw2);
750 dest2RouterIpv6 = config.getRouterIpv6(destSw2);
751 }
752 } catch (DeviceConfigNotFoundException e) {
753 log.warn(e.getMessage() + " Aborting populateEcmpRoutingRulePartial.");
Saurav Das62ae6792017-05-15 15:34:25 -0700754 return false;
755 }
Saurav Das261c3002017-06-13 15:35:54 -0700756
757 if (targetIsEdge && dest1IsEdge) {
758 subnets = (subnets != null && !subnets.isEmpty())
759 ? Sets.newHashSet(subnets)
760 : Sets.newHashSet(config.getSubnets(destSw1));
761 // XXX - Rethink this
762 /*subnets.add(dest1RouterIpv4.toIpPrefix());
763 if (dest1RouterIpv6 != null) {
764 subnets.add(dest1RouterIpv6.toIpPrefix());
765 }
766 if (destSw2 != null && dest2RouterIpv4 != null) {
767 subnets.add(dest2RouterIpv4.toIpPrefix());
768 if (dest2RouterIpv6 != null) {
769 subnets.add(dest2RouterIpv6.toIpPrefix());
770 }
771 }*/
772 log.debug(". populateEcmpRoutingRulePartial in device {} towards {} {} "
773 + "for subnets {}", targetSw, destSw1,
774 (destSw2 != null) ? ("& " + destSw2) : "",
775 subnets);
776 result = rulePopulator.populateIpRuleForSubnet(targetSw, subnets,
777 destSw1, destSw2,
778 nextHops);
779 if (!result) {
780 return false;
781 }
782 /* XXX rethink this
783 IpPrefix routerIpPrefix = destRouterIpv4.toIpPrefix();
784 log.debug("* populateEcmpRoutingRulePartial in device {} towards {} "
785 + "for router IP {}", targetSw, destSw, routerIpPrefix);
786 result = rulePopulator.populateIpRuleForRouter(targetSw, routerIpPrefix,
787 destSw, nextHops);
788 if (!result) {
789 return false;
790 }
791 // If present we deal with IPv6 loopback.
792 if (destRouterIpv6 != null) {
793 routerIpPrefix = destRouterIpv6.toIpPrefix();
794 log.debug("* populateEcmpRoutingRulePartial in device {} towards {}"
795 + " for v6 router IP {}", targetSw, destSw, routerIpPrefix);
796 result = rulePopulator.populateIpRuleForRouter(targetSw, routerIpPrefix,
797 destSw, nextHops);
798 if (!result) {
799 return false;
800 }
801 }*/
Saurav Das62ae6792017-05-15 15:34:25 -0700802 }
Saurav Das261c3002017-06-13 15:35:54 -0700803
804 if (!targetIsEdge && dest1IsEdge) {
805 // MPLS rules in all non-edge target devices. These rules are for
806 // individual destinations, even if the dsts are part of edge-pairs.
807 log.debug(". populateEcmpRoutingRulePartial in device{} towards {} for "
808 + "all MPLS rules", targetSw, destSw1);
809 result = rulePopulator.populateMplsRule(targetSw, destSw1,
810 nextHops.get(destSw1),
811 dest1RouterIpv4);
812 if (!result) {
813 return false;
814 }
815 if (dest1RouterIpv6 != null) {
816 result = rulePopulator.populateMplsRule(targetSw, destSw1,
817 nextHops.get(destSw1),
818 dest1RouterIpv6);
819 if (!result) {
820 return false;
821 }
822 }
823 }
824
825 // To save on ECMP groups
826 // avoid MPLS rules in non-edge-devices to non-edge-devices
827 // avoid MPLS transit rules in edge-devices
828 // avoid loopback IP rules in edge-devices to non-edge-devices
829 return true;
Saurav Das62ae6792017-05-15 15:34:25 -0700830 }
831
832 /**
833 * Processes a set a route-path changes by editing hash groups.
834 *
835 * @param routeChanges a set of route-path changes, where each route-path is
836 * a list with its first element the src-switch of the path
837 * and the second element the dst-switch of the path.
838 * @param linkOrSwitchFailed true if the route changes are for a failed
839 * switch or linkDown event
840 * @param failedSwitch the switchId if the route changes are for a failed switch,
841 * otherwise null
842 */
843 private void processHashGroupChange(Set<ArrayList<DeviceId>> routeChanges,
844 boolean linkOrSwitchFailed,
845 DeviceId failedSwitch) {
Saurav Dasfe0b05e2017-08-14 16:44:43 -0700846 Set<ArrayList<DeviceId>> changedRoutes = new HashSet<>();
847 // first, ensure each routeChanges entry has two elements
Saurav Das62ae6792017-05-15 15:34:25 -0700848 for (ArrayList<DeviceId> route : routeChanges) {
Saurav Dasfe0b05e2017-08-14 16:44:43 -0700849 if (route.size() == 1) {
850 // route-path changes are from everyone else to this switch
851 DeviceId dstSw = route.get(0);
852 srManager.deviceService.getAvailableDevices().forEach(sw -> {
853 if (!sw.id().equals(dstSw)) {
854 changedRoutes.add(Lists.newArrayList(sw.id(), dstSw));
855 }
856 });
857 } else {
858 changedRoutes.add(route);
Saurav Das62ae6792017-05-15 15:34:25 -0700859 }
Saurav Dasfe0b05e2017-08-14 16:44:43 -0700860 }
Saurav Das62ae6792017-05-15 15:34:25 -0700861
Saurav Dasfe0b05e2017-08-14 16:44:43 -0700862 for (ArrayList<DeviceId> route : changedRoutes) {
863 DeviceId targetSw = route.get(0);
864 DeviceId dstSw = route.get(1);
Saurav Das62ae6792017-05-15 15:34:25 -0700865 if (linkOrSwitchFailed) {
Saurav Dasfe0b05e2017-08-14 16:44:43 -0700866 boolean success = fixHashGroupsForRoute(route, true);
Saurav Das62ae6792017-05-15 15:34:25 -0700867 // it's possible that we cannot fix hash groups for a route
868 // if the target switch has failed. Nevertheless the ecmp graph
869 // for the impacted switch must still be updated.
Saurav Dasfe0b05e2017-08-14 16:44:43 -0700870 if (!success && failedSwitch != null && targetSw.equals(failedSwitch)) {
Saurav Das62ae6792017-05-15 15:34:25 -0700871 currentEcmpSpgMap.put(dstSw, updatedEcmpSpgMap.get(dstSw));
872 currentEcmpSpgMap.remove(targetSw);
Saurav Dasfe0b05e2017-08-14 16:44:43 -0700873 log.debug("Updating ECMPspg for dst:{} removing failed switch "
Saurav Das62ae6792017-05-15 15:34:25 -0700874 + "target:{}", dstSw, targetSw);
Saurav Dasfe0b05e2017-08-14 16:44:43 -0700875 continue;
Saurav Das62ae6792017-05-15 15:34:25 -0700876 }
877 //linkfailed - update both sides
Saurav Das62ae6792017-05-15 15:34:25 -0700878 if (success) {
879 currentEcmpSpgMap.put(targetSw, updatedEcmpSpgMap.get(targetSw));
Saurav Dasfe0b05e2017-08-14 16:44:43 -0700880 currentEcmpSpgMap.put(dstSw, updatedEcmpSpgMap.get(dstSw));
881 log.debug("Updating ECMPspg for dst:{} and target:{} for linkdown",
882 dstSw, targetSw);
883 }
884 } else {
885 //linkup of seen before link
886 boolean success = fixHashGroupsForRoute(route, false);
887 if (success) {
888 currentEcmpSpgMap.put(targetSw, updatedEcmpSpgMap.get(targetSw));
889 currentEcmpSpgMap.put(dstSw, updatedEcmpSpgMap.get(dstSw));
890 log.debug("Updating ECMPspg for target:{} and dst:{} for linkup",
Saurav Das62ae6792017-05-15 15:34:25 -0700891 targetSw, dstSw);
892 }
893 }
894 }
895 }
896
897 /**
898 * Edits hash groups in the src-switch (targetSw) of a route-path by
899 * calling the groupHandler to either add or remove buckets in an existing
900 * hash group.
901 *
902 * @param route a single list representing a route-path where the first element
903 * is the src-switch (targetSw) of the route-path and the
904 * second element is the dst-switch
905 * @param revoke true if buckets in the hash-groups need to be removed;
906 * false if buckets in the hash-groups need to be added
907 * @return true if the hash group editing is successful
908 */
909 private boolean fixHashGroupsForRoute(ArrayList<DeviceId> route,
910 boolean revoke) {
911 DeviceId targetSw = route.get(0);
912 if (route.size() < 2) {
913 log.warn("Cannot fixHashGroupsForRoute - no dstSw in route {}", route);
914 return false;
915 }
916 DeviceId destSw = route.get(1);
Saurav Dasfe0b05e2017-08-14 16:44:43 -0700917 log.debug("* processing fixHashGroupsForRoute: Target {} -> Dest {}",
Saurav Das62ae6792017-05-15 15:34:25 -0700918 targetSw, destSw);
Saurav Das62ae6792017-05-15 15:34:25 -0700919 // figure out the new next hops at the targetSw towards the destSw
Saurav Dasfe0b05e2017-08-14 16:44:43 -0700920 Set<DeviceId> nextHops = getNextHops(targetSw, destSw);
Saurav Das62ae6792017-05-15 15:34:25 -0700921 // call group handler to change hash group at targetSw
922 DefaultGroupHandler grpHandler = srManager.getGroupHandler(targetSw);
923 if (grpHandler == null) {
924 log.warn("Cannot find grouphandler for dev:{} .. aborting"
925 + " {} hash group buckets for route:{} ", targetSw,
926 (revoke) ? "revoke" : "repopulate", route);
927 return false;
928 }
929 log.debug("{} hash-groups buckets For Route {} -> {} to next-hops {}",
930 (revoke) ? "revoke" : "repopulating",
931 targetSw, destSw, nextHops);
932 return (revoke) ? grpHandler.fixHashGroups(targetSw, nextHops,
933 destSw, true)
934 : grpHandler.fixHashGroups(targetSw, nextHops,
935 destSw, false);
936 }
937
938 /**
Saurav Das261c3002017-06-13 15:35:54 -0700939 * Start the flow rule population process if it was never started. The
940 * process finishes successfully when all flow rules are set and stops with
941 * ABORTED status when any groups required for flows is not set yet.
Saurav Das62ae6792017-05-15 15:34:25 -0700942 */
Saurav Das261c3002017-06-13 15:35:54 -0700943 public void startPopulationProcess() {
944 statusLock.lock();
945 try {
946 if (populationStatus == Status.IDLE
947 || populationStatus == Status.SUCCEEDED
948 || populationStatus == Status.ABORTED) {
949 populateAllRoutingRules();
sangho28d0b6d2015-05-07 13:30:57 -0700950 } else {
Saurav Das261c3002017-06-13 15:35:54 -0700951 log.warn("Not initiating startPopulationProcess as populationStatus is {}",
952 populationStatus);
Srikanth Vavilapalli64d96c12015-05-14 20:22:47 -0700953 }
Saurav Das261c3002017-06-13 15:35:54 -0700954 } finally {
955 statusLock.unlock();
Srikanth Vavilapalli64d96c12015-05-14 20:22:47 -0700956 }
sanghofb7c7292015-04-13 15:15:58 -0700957 }
958
Saurav Dasb149be12016-06-07 10:08:06 -0700959 /**
Saurav Das261c3002017-06-13 15:35:54 -0700960 * Revoke rules of given subnet in all edge switches.
961 *
962 * @param subnets subnet being removed
963 * @return true if succeed
964 */
965 protected boolean revokeSubnet(Set<IpPrefix> subnets) {
966 statusLock.lock();
967 try {
968 return srManager.routingRulePopulator.revokeIpRuleForSubnet(subnets);
969 } finally {
970 statusLock.unlock();
971 }
972 }
973
974 /**
975 * Remove ECMP graph entry for the given device. Typically called when
976 * device is no longer available.
977 *
978 * @param deviceId the device for which graphs need to be purged
979 */
980 protected void purgeEcmpGraph(DeviceId deviceId) {
Saurav Dasfe0b05e2017-08-14 16:44:43 -0700981 currentEcmpSpgMap.remove(deviceId); // XXX reconsider
Saurav Das261c3002017-06-13 15:35:54 -0700982 if (updatedEcmpSpgMap != null) {
983 updatedEcmpSpgMap.remove(deviceId);
984 }
985 }
986
987 //////////////////////////////////////
988 // Routing helper methods and classes
989 //////////////////////////////////////
990
991 /**
Saurav Das1b391d52016-11-29 14:27:25 -0800992 * Computes set of affected routes due to failed link. Assumes
Saurav Dasb149be12016-06-07 10:08:06 -0700993 * previous ecmp shortest-path graph exists for a switch in order to compute
994 * affected routes. If such a graph does not exist, the method returns null.
995 *
996 * @param linkFail the failed link
997 * @return the set of affected routes which may be empty if no routes were
998 * affected, or null if no previous ecmp spg was found for comparison
999 */
sanghofb7c7292015-04-13 15:15:58 -07001000 private Set<ArrayList<DeviceId>> computeDamagedRoutes(Link linkFail) {
sanghofb7c7292015-04-13 15:15:58 -07001001 Set<ArrayList<DeviceId>> routes = new HashSet<>();
1002
1003 for (Device sw : srManager.deviceService.getDevices()) {
Srikanth Vavilapalli64d96c12015-05-14 20:22:47 -07001004 log.debug("Computing the impacted routes for device {} due to link fail",
1005 sw.id());
Saurav Dasfe0b05e2017-08-14 16:44:43 -07001006 DeviceId retId = shouldHandleRouting(sw.id());
1007 if (retId == null) {
sanghofb7c7292015-04-13 15:15:58 -07001008 continue;
1009 }
Saurav Dasfe0b05e2017-08-14 16:44:43 -07001010 Set<DeviceId> devicesToProcess = Sets.newHashSet(retId, sw.id());
1011 for (DeviceId rootSw : devicesToProcess) {
1012 EcmpShortestPathGraph ecmpSpg = currentEcmpSpgMap.get(rootSw);
1013 if (ecmpSpg == null) {
1014 log.warn("No existing ECMP graph for switch {}. Aborting optimized"
1015 + " rerouting and opting for full-reroute", rootSw);
1016 return null;
1017 }
1018 if (log.isDebugEnabled()) {
1019 log.debug("Root switch: {}", rootSw);
1020 log.debug(" Current/Existing SPG: {}", ecmpSpg);
1021 log.debug(" New/Updated SPG: {}", updatedEcmpSpgMap.get(rootSw));
1022 }
1023 HashMap<Integer, HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>>>
1024 switchVia = ecmpSpg.getAllLearnedSwitchesAndVia();
1025 // figure out if the broken link affected any route-paths in this graph
1026 for (Integer itrIdx : switchVia.keySet()) {
1027 log.trace("Current/Exiting SPG Iterindex# {}", itrIdx);
1028 HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>> swViaMap =
1029 switchVia.get(itrIdx);
1030 for (DeviceId targetSw : swViaMap.keySet()) {
1031 log.trace("TargetSwitch {} --> RootSwitch {}",
1032 targetSw, rootSw);
Saurav Dasb149be12016-06-07 10:08:06 -07001033 for (ArrayList<DeviceId> via : swViaMap.get(targetSw)) {
1034 log.trace(" Via:");
Pier Ventreadb4ae62016-11-23 09:57:42 -08001035 via.forEach(e -> log.trace(" {}", e));
Saurav Dasb149be12016-06-07 10:08:06 -07001036 }
Saurav Dasfe0b05e2017-08-14 16:44:43 -07001037 Set<ArrayList<DeviceId>> subLinks =
1038 computeLinks(targetSw, rootSw, swViaMap);
1039 for (ArrayList<DeviceId> alink: subLinks) {
1040 if ((alink.get(0).equals(linkFail.src().deviceId()) &&
1041 alink.get(1).equals(linkFail.dst().deviceId()))
1042 ||
1043 (alink.get(0).equals(linkFail.dst().deviceId()) &&
1044 alink.get(1).equals(linkFail.src().deviceId()))) {
1045 log.debug("Impacted route:{}->{}", targetSw, rootSw);
1046 ArrayList<DeviceId> aRoute = new ArrayList<>();
1047 aRoute.add(targetSw); // switch with rules to populate
1048 aRoute.add(rootSw); // towards this destination
1049 routes.add(aRoute);
1050 break;
1051 }
sanghofb7c7292015-04-13 15:15:58 -07001052 }
1053 }
1054 }
Saurav Dasfe0b05e2017-08-14 16:44:43 -07001055
sanghofb7c7292015-04-13 15:15:58 -07001056 }
sangho28d0b6d2015-05-07 13:30:57 -07001057
sanghofb7c7292015-04-13 15:15:58 -07001058 }
sanghofb7c7292015-04-13 15:15:58 -07001059 return routes;
1060 }
1061
Saurav Das1b391d52016-11-29 14:27:25 -08001062 /**
1063 * Computes set of affected routes due to new links or failed switches.
1064 *
1065 * @return the set of affected routes which may be empty if no routes were
1066 * affected
1067 */
sanghofb7c7292015-04-13 15:15:58 -07001068 private Set<ArrayList<DeviceId>> computeRouteChange() {
Saurav Das261c3002017-06-13 15:35:54 -07001069 ImmutableSet.Builder<ArrayList<DeviceId>> changedRtBldr =
Saurav Das1b391d52016-11-29 14:27:25 -08001070 ImmutableSet.builder();
sanghofb7c7292015-04-13 15:15:58 -07001071
1072 for (Device sw : srManager.deviceService.getDevices()) {
Saurav Das261c3002017-06-13 15:35:54 -07001073 log.debug("Computing the impacted routes for device {}", sw.id());
1074 DeviceId retId = shouldHandleRouting(sw.id());
1075 if (retId == null) {
sanghofb7c7292015-04-13 15:15:58 -07001076 continue;
1077 }
Saurav Das261c3002017-06-13 15:35:54 -07001078 Set<DeviceId> devicesToProcess = Sets.newHashSet(retId, sw.id());
1079 for (DeviceId rootSw : devicesToProcess) {
1080 if (log.isTraceEnabled()) {
1081 log.trace("Device links for dev: {}", rootSw);
1082 for (Link link: srManager.linkService.getDeviceLinks(rootSw)) {
1083 log.trace("{} -> {} ", link.src().deviceId(),
1084 link.dst().deviceId());
1085 }
Saurav Dasb149be12016-06-07 10:08:06 -07001086 }
Saurav Das261c3002017-06-13 15:35:54 -07001087 EcmpShortestPathGraph currEcmpSpg = currentEcmpSpgMap.get(rootSw);
1088 if (currEcmpSpg == null) {
1089 log.debug("No existing ECMP graph for device {}.. adding self as "
1090 + "changed route", rootSw);
1091 changedRtBldr.add(Lists.newArrayList(rootSw));
1092 continue;
1093 }
1094 EcmpShortestPathGraph newEcmpSpg = updatedEcmpSpgMap.get(rootSw);
1095 if (log.isDebugEnabled()) {
1096 log.debug("Root switch: {}", rootSw);
1097 log.debug(" Current/Existing SPG: {}", currEcmpSpg);
1098 log.debug(" New/Updated SPG: {}", newEcmpSpg);
1099 }
1100 // first use the updated/new map to compare to current/existing map
1101 // as new links may have come up
1102 changedRtBldr.addAll(compareGraphs(newEcmpSpg, currEcmpSpg, rootSw));
1103 // then use the current/existing map to compare to updated/new map
1104 // as switch may have been removed
1105 changedRtBldr.addAll(compareGraphs(currEcmpSpg, newEcmpSpg, rootSw));
sangho28d0b6d2015-05-07 13:30:57 -07001106 }
Saurav Das1b391d52016-11-29 14:27:25 -08001107 }
sanghofb7c7292015-04-13 15:15:58 -07001108
Saurav Das261c3002017-06-13 15:35:54 -07001109 Set<ArrayList<DeviceId>> changedRoutes = changedRtBldr.build();
Saurav Das1b391d52016-11-29 14:27:25 -08001110 for (ArrayList<DeviceId> route: changedRoutes) {
1111 log.debug("Route changes Target -> Root");
1112 if (route.size() == 1) {
1113 log.debug(" : all -> {}", route.get(0));
1114 } else {
1115 log.debug(" : {} -> {}", route.get(0), route.get(1));
1116 }
1117 }
1118 return changedRoutes;
1119 }
1120
1121 /**
1122 * For the root switch, searches all the target nodes reachable in the base
1123 * graph, and compares paths to the ones in the comp graph.
1124 *
1125 * @param base the graph that is indexed for all reachable target nodes
1126 * from the root node
1127 * @param comp the graph that the base graph is compared to
1128 * @param rootSw both ecmp graphs are calculated for the root node
1129 * @return all the routes that have changed in the base graph
1130 */
1131 private Set<ArrayList<DeviceId>> compareGraphs(EcmpShortestPathGraph base,
1132 EcmpShortestPathGraph comp,
1133 DeviceId rootSw) {
1134 ImmutableSet.Builder<ArrayList<DeviceId>> changedRoutesBuilder =
1135 ImmutableSet.builder();
1136 HashMap<Integer, HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>>> baseMap =
1137 base.getAllLearnedSwitchesAndVia();
1138 HashMap<Integer, HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>>> compMap =
1139 comp.getAllLearnedSwitchesAndVia();
1140 for (Integer itrIdx : baseMap.keySet()) {
1141 HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>> baseViaMap =
1142 baseMap.get(itrIdx);
1143 for (DeviceId targetSw : baseViaMap.keySet()) {
1144 ArrayList<ArrayList<DeviceId>> basePath = baseViaMap.get(targetSw);
1145 ArrayList<ArrayList<DeviceId>> compPath = getVia(compMap, targetSw);
1146 if ((compPath == null) || !basePath.equals(compPath)) {
Saurav Das62ae6792017-05-15 15:34:25 -07001147 log.trace("Impacted route:{} -> {}", targetSw, rootSw);
Saurav Das1b391d52016-11-29 14:27:25 -08001148 ArrayList<DeviceId> route = new ArrayList<>();
Saurav Das261c3002017-06-13 15:35:54 -07001149 route.add(targetSw); // switch with rules to populate
1150 route.add(rootSw); // towards this destination
Saurav Das1b391d52016-11-29 14:27:25 -08001151 changedRoutesBuilder.add(route);
sanghofb7c7292015-04-13 15:15:58 -07001152 }
1153 }
sangho28d0b6d2015-05-07 13:30:57 -07001154 }
Saurav Das1b391d52016-11-29 14:27:25 -08001155 return changedRoutesBuilder.build();
sanghofb7c7292015-04-13 15:15:58 -07001156 }
1157
Saurav Das261c3002017-06-13 15:35:54 -07001158 /**
1159 * Returns the ECMP paths traversed to reach the target switch.
1160 *
1161 * @param switchVia a per-iteration view of the ECMP graph for a root switch
1162 * @param targetSw the switch to reach from the root switch
1163 * @return the nodes traversed on ECMP paths to the target switch
1164 */
sanghofb7c7292015-04-13 15:15:58 -07001165 private ArrayList<ArrayList<DeviceId>> getVia(HashMap<Integer, HashMap<DeviceId,
Saurav Das1b391d52016-11-29 14:27:25 -08001166 ArrayList<ArrayList<DeviceId>>>> switchVia, DeviceId targetSw) {
sanghofb7c7292015-04-13 15:15:58 -07001167 for (Integer itrIdx : switchVia.keySet()) {
1168 HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>> swViaMap =
1169 switchVia.get(itrIdx);
Saurav Das1b391d52016-11-29 14:27:25 -08001170 if (swViaMap.get(targetSw) == null) {
sanghofb7c7292015-04-13 15:15:58 -07001171 continue;
1172 } else {
Saurav Das1b391d52016-11-29 14:27:25 -08001173 return swViaMap.get(targetSw);
sanghofb7c7292015-04-13 15:15:58 -07001174 }
1175 }
1176
Srikanth Vavilapalli64d96c12015-05-14 20:22:47 -07001177 return null;
sanghofb7c7292015-04-13 15:15:58 -07001178 }
1179
Saurav Das261c3002017-06-13 15:35:54 -07001180 /**
1181 * Utility method to break down a path from src to dst device into a collection
1182 * of links.
1183 *
1184 * @param src src device of the path
1185 * @param dst dst device of the path
1186 * @param viaMap path taken from src to dst device
1187 * @return collection of links in the path
1188 */
sanghofb7c7292015-04-13 15:15:58 -07001189 private Set<ArrayList<DeviceId>> computeLinks(DeviceId src,
1190 DeviceId dst,
1191 HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>> viaMap) {
1192 Set<ArrayList<DeviceId>> subLinks = Sets.newHashSet();
1193 for (ArrayList<DeviceId> via : viaMap.get(src)) {
1194 DeviceId linkSrc = src;
1195 DeviceId linkDst = dst;
1196 for (DeviceId viaDevice: via) {
1197 ArrayList<DeviceId> link = new ArrayList<>();
1198 linkDst = viaDevice;
1199 link.add(linkSrc);
1200 link.add(linkDst);
1201 subLinks.add(link);
1202 linkSrc = viaDevice;
1203 }
1204 ArrayList<DeviceId> link = new ArrayList<>();
1205 link.add(linkSrc);
1206 link.add(dst);
1207 subLinks.add(link);
1208 }
1209
1210 return subLinks;
1211 }
1212
Charles Chanc22cef32016-04-29 14:38:22 -07001213 /**
Saurav Das261c3002017-06-13 15:35:54 -07001214 * Determines whether this controller instance should handle routing for the
1215 * given {@code deviceId}, based on mastership and pairDeviceId if one exists.
1216 * Returns null if this instance should not handle routing for given {@code deviceId}.
1217 * Otherwise the returned value could be the given deviceId itself, or the
1218 * deviceId for the paired edge device. In the latter case, this instance
1219 * should handle routing for both the given device and the paired device.
Charles Chanc22cef32016-04-29 14:38:22 -07001220 *
Saurav Das261c3002017-06-13 15:35:54 -07001221 * @param deviceId device identifier to consider for routing
1222 * @return null or deviceId which could be the same as the given deviceId
1223 * or the deviceId of a paired edge device
Charles Chanc22cef32016-04-29 14:38:22 -07001224 */
Saurav Das261c3002017-06-13 15:35:54 -07001225 private DeviceId shouldHandleRouting(DeviceId deviceId) {
1226 if (!srManager.mastershipService.isLocalMaster(deviceId)) {
1227 log.debug("Not master for dev:{} .. skipping routing, may get handled "
1228 + "elsewhere as part of paired devices", deviceId);
1229 return null;
1230 }
1231 NodeId myNode = srManager.mastershipService.getMasterFor(deviceId);
1232 DeviceId pairDev = getPairDev(deviceId);
sangho80f11cb2015-04-01 13:05:26 -07001233
Saurav Das261c3002017-06-13 15:35:54 -07001234 if (pairDev != null) {
1235 if (!srManager.deviceService.isAvailable(pairDev)) {
1236 log.warn("pairedDev {} not available .. routing this dev:{} "
1237 + "without mastership check",
1238 pairDev, deviceId);
1239 return pairDev; // handle both temporarily
1240 }
1241 NodeId pairMasterNode = srManager.mastershipService.getMasterFor(pairDev);
1242 if (myNode.compareTo(pairMasterNode) <= 0) {
1243 log.debug("Handling routing for both dev:{} pair-dev:{}; myNode: {}"
1244 + " pairMaster:{} compare:{}", deviceId, pairDev,
1245 myNode, pairMasterNode,
1246 myNode.compareTo(pairMasterNode));
1247 return pairDev; // handle both
1248 } else {
1249 log.debug("PairDev node: {} should handle routing for dev:{} and "
1250 + "pair-dev:{}", pairMasterNode, deviceId, pairDev);
1251 return null; // handle neither
sangho80f11cb2015-04-01 13:05:26 -07001252 }
1253 }
Saurav Das261c3002017-06-13 15:35:54 -07001254 return deviceId; // not paired, just handle given device
sangho80f11cb2015-04-01 13:05:26 -07001255 }
1256
Charles Chanc22cef32016-04-29 14:38:22 -07001257 /**
Saurav Das261c3002017-06-13 15:35:54 -07001258 * Returns the configured paired DeviceId for the given Device, or null
1259 * if no such paired device has been configured.
Charles Chanc22cef32016-04-29 14:38:22 -07001260 *
Saurav Das261c3002017-06-13 15:35:54 -07001261 * @param deviceId
1262 * @return configured pair deviceId or null
Charles Chanc22cef32016-04-29 14:38:22 -07001263 */
Saurav Das261c3002017-06-13 15:35:54 -07001264 private DeviceId getPairDev(DeviceId deviceId) {
1265 DeviceId pairDev;
Charles Chan319d1a22015-11-03 10:42:14 -08001266 try {
Saurav Das261c3002017-06-13 15:35:54 -07001267 pairDev = srManager.deviceConfiguration.getPairDeviceId(deviceId);
Charles Chan319d1a22015-11-03 10:42:14 -08001268 } catch (DeviceConfigNotFoundException e) {
Saurav Das261c3002017-06-13 15:35:54 -07001269 log.warn(e.getMessage() + " .. cannot continue routing for dev: {}");
1270 return null;
Charles Chan319d1a22015-11-03 10:42:14 -08001271 }
Saurav Das261c3002017-06-13 15:35:54 -07001272 return pairDev;
sangho80f11cb2015-04-01 13:05:26 -07001273 }
1274
1275 /**
Saurav Das261c3002017-06-13 15:35:54 -07001276 * Returns the set of deviceIds which are the next hops from the targetSw
1277 * to the dstSw according to the latest ECMP spg.
1278 *
1279 * @param targetSw the switch for which the next-hops are desired
1280 * @param dstSw the switch to which the next-hops lead to from the targetSw
1281 * @return set of next hop deviceIds, could be empty if no next hops are found
1282 */
1283 private Set<DeviceId> getNextHops(DeviceId targetSw, DeviceId dstSw) {
1284 boolean targetIsEdge = false;
1285 try {
1286 targetIsEdge = srManager.deviceConfiguration.isEdgeDevice(targetSw);
1287 } catch (DeviceConfigNotFoundException e) {
1288 log.warn(e.getMessage() + "Cannot determine if targetIsEdge {}.. "
1289 + "continuing to getNextHops", targetSw);
1290 }
1291
1292 EcmpShortestPathGraph ecmpSpg = updatedEcmpSpgMap.get(dstSw);
1293 if (ecmpSpg == null) {
1294 log.debug("No ecmpSpg found for dstSw: {}", dstSw);
1295 return ImmutableSet.of();
1296 }
1297 HashMap<Integer,
1298 HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>>> switchVia =
1299 ecmpSpg.getAllLearnedSwitchesAndVia();
1300 for (Integer itrIdx : switchVia.keySet()) {
1301 HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>> swViaMap =
1302 switchVia.get(itrIdx);
1303 for (DeviceId target : swViaMap.keySet()) {
1304 if (!target.equals(targetSw)) {
1305 continue;
1306 }
1307 if (!targetIsEdge && itrIdx > 1) {
1308 // optimization for spines to not use other leaves to get
1309 // to a leaf to avoid loops
1310 log.debug("Avoiding {} hop path for non-edge targetSw:{}"
1311 + " --> dstSw:{}", itrIdx, targetSw, dstSw);
1312 break;
1313 }
1314 Set<DeviceId> nextHops = new HashSet<>();
1315 for (ArrayList<DeviceId> via : swViaMap.get(targetSw)) {
1316 if (via.isEmpty()) {
1317 // the dstSw is the next-hop from the targetSw
1318 nextHops.add(dstSw);
1319 } else {
1320 // first elem is next-hop in each ECMP path
1321 nextHops.add(via.get(0));
1322 }
1323 }
1324 return nextHops;
1325 }
1326 }
1327 return ImmutableSet.of(); //no next-hops found
1328 }
1329
1330 /**
1331 * Represents two devices that are paired by configuration. An EdgePair for
1332 * (dev1, dev2) is the same as as EdgePair for (dev2, dev1)
1333 */
1334 protected final class EdgePair {
1335 DeviceId dev1;
1336 DeviceId dev2;
1337
1338 EdgePair(DeviceId dev1, DeviceId dev2) {
1339 this.dev1 = dev1;
1340 this.dev2 = dev2;
1341 }
1342
1343 boolean includes(DeviceId dev) {
1344 return dev1.equals(dev) || dev2.equals(dev);
1345 }
1346
1347 @Override
1348 public boolean equals(Object o) {
1349 if (this == o) {
1350 return true;
1351 }
1352 if (!(o instanceof EdgePair)) {
1353 return false;
1354 }
1355 EdgePair that = (EdgePair) o;
1356 return ((this.dev1.equals(that.dev1) && this.dev2.equals(that.dev2)) ||
1357 (this.dev1.equals(that.dev2) && this.dev2.equals(that.dev1)));
1358 }
1359
1360 @Override
1361 public int hashCode() {
1362 if (dev1.toString().compareTo(dev2.toString()) <= 0) {
1363 return Objects.hash(dev1, dev2);
1364 } else {
1365 return Objects.hash(dev2, dev1);
1366 }
1367 }
1368
1369 @Override
1370 public String toString() {
1371 return toStringHelper(this)
1372 .add("Dev1", dev1)
1373 .add("Dev2", dev2)
1374 .toString();
1375 }
1376 }
1377
Saurav Dasfe0b05e2017-08-14 16:44:43 -07001378 /**
1379 * Updates the currentEcmpSpgGraph for all devices.
1380 */
1381 private void updateEcmpSpgMaps() {
1382 for (Device sw : srManager.deviceService.getDevices()) {
1383 EcmpShortestPathGraph ecmpSpgUpdated =
1384 new EcmpShortestPathGraph(sw.id(), srManager);
1385 currentEcmpSpgMap.put(sw.id(), ecmpSpgUpdated);
1386 }
1387 }
1388
1389 /**
1390 * Ensures routing is stable before updating all ECMP SPG graphs.
1391 *
1392 * TODO: CORD-1843 will ensure maps are updated faster, potentially while
1393 * topology/routing is still unstable
1394 */
1395 private final class UpdateMaps implements Runnable {
1396 @Override
1397 public void run() {
1398 if (isRoutingStable()) {
1399 updateEcmpSpgMaps();
1400 } else {
1401 executorService.schedule(new UpdateMaps(), UPDATE_INTERVAL,
1402 TimeUnit.SECONDS);
1403 }
1404 }
1405 }
1406
Saurav Das261c3002017-06-13 15:35:54 -07001407 //////////////////////////////////////
1408 // Filtering rule creation
1409 //////////////////////////////////////
1410
1411 /**
Saurav Dasf9332192017-02-18 14:05:44 -08001412 * Populates filtering rules for port, and punting rules
1413 * for gateway IPs, loopback IPs and arp/ndp traffic.
1414 * Should only be called by the master instance for this device/port.
sangho80f11cb2015-04-01 13:05:26 -07001415 *
1416 * @param deviceId Switch ID to set the rules
1417 */
Saurav Das9f1c42e2015-10-23 10:51:11 -07001418 public void populatePortAddressingRules(DeviceId deviceId) {
Saurav Das07c74602016-04-27 18:35:50 -07001419 // Although device is added, sometimes device store does not have the
1420 // ports for this device yet. It results in missing filtering rules in the
1421 // switch. We will attempt it a few times. If it still does not work,
1422 // user can manually repopulate using CLI command sr-reroute-network
Charles Chan18fa4252017-02-08 16:10:40 -08001423 PortFilterInfo firstRun = rulePopulator.populateVlanMacFilters(deviceId);
Saurav Dasd1872b02016-12-02 15:43:47 -08001424 if (firstRun == null) {
1425 firstRun = new PortFilterInfo(0, 0, 0);
Saurav Das07c74602016-04-27 18:35:50 -07001426 }
Saurav Dasd1872b02016-12-02 15:43:47 -08001427 executorService.schedule(new RetryFilters(deviceId, firstRun),
1428 RETRY_INTERVAL_MS, TimeUnit.MILLISECONDS);
sangho80f11cb2015-04-01 13:05:26 -07001429 }
1430
1431 /**
Saurav Dasd1872b02016-12-02 15:43:47 -08001432 * Utility class used to temporarily store information about the ports on a
1433 * device processed for filtering objectives.
Saurav Dasd1872b02016-12-02 15:43:47 -08001434 */
1435 public final class PortFilterInfo {
Saurav Dasf9332192017-02-18 14:05:44 -08001436 int disabledPorts = 0, errorPorts = 0, filteredPorts = 0;
Saurav Das07c74602016-04-27 18:35:50 -07001437
Saurav Dasf9332192017-02-18 14:05:44 -08001438 public PortFilterInfo(int disabledPorts, int errorPorts,
Saurav Dasd1872b02016-12-02 15:43:47 -08001439 int filteredPorts) {
1440 this.disabledPorts = disabledPorts;
1441 this.filteredPorts = filteredPorts;
Saurav Dasf9332192017-02-18 14:05:44 -08001442 this.errorPorts = errorPorts;
Saurav Dasd1872b02016-12-02 15:43:47 -08001443 }
1444
1445 @Override
1446 public int hashCode() {
Saurav Dasf9332192017-02-18 14:05:44 -08001447 return Objects.hash(disabledPorts, filteredPorts, errorPorts);
Saurav Dasd1872b02016-12-02 15:43:47 -08001448 }
1449
1450 @Override
1451 public boolean equals(Object obj) {
1452 if (this == obj) {
1453 return true;
1454 }
1455 if ((obj == null) || (!(obj instanceof PortFilterInfo))) {
1456 return false;
1457 }
1458 PortFilterInfo other = (PortFilterInfo) obj;
1459 return ((disabledPorts == other.disabledPorts) &&
1460 (filteredPorts == other.filteredPorts) &&
Saurav Dasf9332192017-02-18 14:05:44 -08001461 (errorPorts == other.errorPorts));
Saurav Dasd1872b02016-12-02 15:43:47 -08001462 }
1463
1464 @Override
1465 public String toString() {
1466 MoreObjects.ToStringHelper helper = toStringHelper(this)
1467 .add("disabledPorts", disabledPorts)
Saurav Dasf9332192017-02-18 14:05:44 -08001468 .add("errorPorts", errorPorts)
Saurav Dasd1872b02016-12-02 15:43:47 -08001469 .add("filteredPorts", filteredPorts);
1470 return helper.toString();
1471 }
1472 }
1473
1474 /**
1475 * RetryFilters populates filtering objectives for a device and keeps retrying
1476 * till the number of ports filtered are constant for a predefined number
1477 * of attempts.
1478 */
1479 protected final class RetryFilters implements Runnable {
1480 int constantAttempts = MAX_CONSTANT_RETRY_ATTEMPTS;
1481 DeviceId devId;
1482 int counter;
1483 PortFilterInfo prevRun;
1484
1485 private RetryFilters(DeviceId deviceId, PortFilterInfo previousRun) {
Saurav Das07c74602016-04-27 18:35:50 -07001486 devId = deviceId;
Saurav Dasd1872b02016-12-02 15:43:47 -08001487 prevRun = previousRun;
1488 counter = 0;
Saurav Das07c74602016-04-27 18:35:50 -07001489 }
1490
1491 @Override
1492 public void run() {
Charles Chan077314e2017-06-22 14:27:17 -07001493 log.debug("RETRY FILTER ATTEMPT {} ** dev:{}", ++counter, devId);
Charles Chan18fa4252017-02-08 16:10:40 -08001494 PortFilterInfo thisRun = rulePopulator.populateVlanMacFilters(devId);
Saurav Dasd1872b02016-12-02 15:43:47 -08001495 boolean sameResult = prevRun.equals(thisRun);
1496 log.debug("dev:{} prevRun:{} thisRun:{} sameResult:{}", devId, prevRun,
1497 thisRun, sameResult);
1498 if (thisRun == null || !sameResult || (sameResult && --constantAttempts > 0)) {
Saurav Dasf9332192017-02-18 14:05:44 -08001499 // exponentially increasing intervals for retries
1500 executorService.schedule(this,
1501 RETRY_INTERVAL_MS * (int) Math.pow(counter, RETRY_INTERVAL_SCALE),
1502 TimeUnit.MILLISECONDS);
Saurav Dasd1872b02016-12-02 15:43:47 -08001503 if (!sameResult) {
1504 constantAttempts = MAX_CONSTANT_RETRY_ATTEMPTS; //reset
1505 }
Saurav Das07c74602016-04-27 18:35:50 -07001506 }
Saurav Dasd1872b02016-12-02 15:43:47 -08001507 prevRun = (thisRun == null) ? prevRun : thisRun;
Saurav Das07c74602016-04-27 18:35:50 -07001508 }
Saurav Das07c74602016-04-27 18:35:50 -07001509 }
1510
sangho80f11cb2015-04-01 13:05:26 -07001511}