blob: 5396f54905caca7527b1fa004fc4bf0a60ea5052 [file] [log] [blame]
sangho80f11cb2015-04-01 13:05:26 -07001/*
Brian O'Connor43b53542016-04-09 01:19:45 -07002 * Copyright 2015-present Open Networking Laboratory
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;
Charles Chanc22cef32016-04-29 14:38:22 -070019import com.google.common.collect.ImmutableSet;
Saurav Das1b391d52016-11-29 14:27:25 -080020import com.google.common.collect.Lists;
sanghofb7c7292015-04-13 15:15:58 -070021import com.google.common.collect.Maps;
22import com.google.common.collect.Sets;
sangho9b169e32015-04-14 16:27:13 -070023import org.onlab.packet.Ip4Address;
Srikanth Vavilapalli37a461b2015-04-07 15:12:32 -070024import org.onlab.packet.Ip4Prefix;
sangho80f11cb2015-04-01 13:05:26 -070025import org.onlab.packet.IpPrefix;
Charles Chanc22cef32016-04-29 14:38:22 -070026import org.onosproject.net.ConnectPoint;
sangho80f11cb2015-04-01 13:05:26 -070027import org.onosproject.net.Device;
28import org.onosproject.net.DeviceId;
sanghofb7c7292015-04-13 15:15:58 -070029import org.onosproject.net.Link;
Charles Chan319d1a22015-11-03 10:42:14 -080030import org.onosproject.segmentrouting.config.DeviceConfigNotFoundException;
31import org.onosproject.segmentrouting.config.DeviceConfiguration;
sangho80f11cb2015-04-01 13:05:26 -070032import org.slf4j.Logger;
33import org.slf4j.LoggerFactory;
34
Yuta HIGUCHIebee2f12016-07-21 16:54:33 -070035import static java.util.concurrent.Executors.newScheduledThreadPool;
36import static org.onlab.util.Tools.groupedThreads;
37
sangho80f11cb2015-04-01 13:05:26 -070038import java.util.ArrayList;
39import java.util.HashMap;
40import java.util.HashSet;
Saurav Dasd1872b02016-12-02 15:43:47 -080041import java.util.Objects;
sangho80f11cb2015-04-01 13:05:26 -070042import java.util.Set;
Saurav Das07c74602016-04-27 18:35:50 -070043import java.util.concurrent.ScheduledExecutorService;
44import java.util.concurrent.TimeUnit;
HIGUCHI Yuta16d8fd52015-09-08 16:16:31 +090045import java.util.concurrent.locks.Lock;
46import java.util.concurrent.locks.ReentrantLock;
sangho80f11cb2015-04-01 13:05:26 -070047
48import static com.google.common.base.Preconditions.checkNotNull;
Saurav Dasd1872b02016-12-02 15:43:47 -080049import static com.google.common.base.MoreObjects.toStringHelper;
sangho80f11cb2015-04-01 13:05:26 -070050
Charles Chanb7f75ac2016-01-11 18:28:54 -080051/**
52 * Default routing handler that is responsible for route computing and
53 * routing rule population.
54 */
sangho80f11cb2015-04-01 13:05:26 -070055public class DefaultRoutingHandler {
Saurav Dasd1872b02016-12-02 15:43:47 -080056 private static final int MAX_CONSTANT_RETRY_ATTEMPTS = 4;
57 private static final int RETRY_INTERVAL_MS = 500;
Charles Chanc22cef32016-04-29 14:38:22 -070058 private static final String ECMPSPG_MISSING = "ECMP shortest path graph not found";
59 private static Logger log = LoggerFactory.getLogger(DefaultRoutingHandler.class);
sangho80f11cb2015-04-01 13:05:26 -070060
61 private SegmentRoutingManager srManager;
62 private RoutingRulePopulator rulePopulator;
Shashikanth VH0637b162015-12-11 01:32:44 +053063 private HashMap<DeviceId, EcmpShortestPathGraph> currentEcmpSpgMap;
64 private HashMap<DeviceId, EcmpShortestPathGraph> updatedEcmpSpgMap;
sangho9b169e32015-04-14 16:27:13 -070065 private DeviceConfiguration config;
HIGUCHI Yuta16d8fd52015-09-08 16:16:31 +090066 private final Lock statusLock = new ReentrantLock();
67 private volatile Status populationStatus;
Yuta HIGUCHIebee2f12016-07-21 16:54:33 -070068 private ScheduledExecutorService executorService
Saurav Dasd1872b02016-12-02 15:43:47 -080069 = newScheduledThreadPool(1, groupedThreads("retryftr", "retry-%d", log));
sangho80f11cb2015-04-01 13:05:26 -070070
71 /**
72 * Represents the default routing population status.
73 */
74 public enum Status {
75 // population process is not started yet.
76 IDLE,
77
78 // population process started.
79 STARTED,
80
Srikanth Vavilapalli64505482015-04-21 13:04:13 -070081 // population process was aborted due to errors, mostly for groups not
82 // found.
sangho80f11cb2015-04-01 13:05:26 -070083 ABORTED,
84
85 // population process was finished successfully.
86 SUCCEEDED
87 }
88
89 /**
90 * Creates a DefaultRoutingHandler object.
91 *
92 * @param srManager SegmentRoutingManager object
93 */
94 public DefaultRoutingHandler(SegmentRoutingManager srManager) {
95 this.srManager = srManager;
96 this.rulePopulator = checkNotNull(srManager.routingRulePopulator);
sangho9b169e32015-04-14 16:27:13 -070097 this.config = checkNotNull(srManager.deviceConfiguration);
sangho80f11cb2015-04-01 13:05:26 -070098 this.populationStatus = Status.IDLE;
sanghofb7c7292015-04-13 15:15:58 -070099 this.currentEcmpSpgMap = Maps.newHashMap();
sangho80f11cb2015-04-01 13:05:26 -0700100 }
101
102 /**
103 * Populates all routing rules to all connected routers, including default
104 * routing rules, adjacency rules, and policy rules if any.
105 *
106 * @return true if it succeeds in populating all rules, otherwise false
107 */
108 public boolean populateAllRoutingRules() {
109
HIGUCHI Yuta16d8fd52015-09-08 16:16:31 +0900110 statusLock.lock();
111 try {
112 populationStatus = Status.STARTED;
113 rulePopulator.resetCounter();
Saurav Das88979182015-10-19 14:37:36 -0700114 log.info("Starting to populate segment-routing rules");
HIGUCHI Yuta16d8fd52015-09-08 16:16:31 +0900115 log.debug("populateAllRoutingRules: populationStatus is STARTED");
sangho80f11cb2015-04-01 13:05:26 -0700116
HIGUCHI Yuta16d8fd52015-09-08 16:16:31 +0900117 for (Device sw : srManager.deviceService.getDevices()) {
Charles Chan77277672015-10-20 16:24:19 -0700118 if (!srManager.mastershipService.isLocalMaster(sw.id())) {
HIGUCHI Yuta16d8fd52015-09-08 16:16:31 +0900119 log.debug("populateAllRoutingRules: skipping device {}...we are not master",
120 sw.id());
121 continue;
122 }
123
Shashikanth VH0637b162015-12-11 01:32:44 +0530124 EcmpShortestPathGraph ecmpSpg = new EcmpShortestPathGraph(sw.id(), srManager);
Charles Chanc22cef32016-04-29 14:38:22 -0700125 if (!populateEcmpRoutingRules(sw.id(), ecmpSpg, ImmutableSet.of())) {
HIGUCHI Yuta16d8fd52015-09-08 16:16:31 +0900126 log.debug("populateAllRoutingRules: populationStatus is ABORTED");
127 populationStatus = Status.ABORTED;
128 log.debug("Abort routing rule population");
129 return false;
130 }
131 currentEcmpSpgMap.put(sw.id(), ecmpSpg);
132
133 // TODO: Set adjacency routing rule for all switches
sangho80f11cb2015-04-01 13:05:26 -0700134 }
135
HIGUCHI Yuta16d8fd52015-09-08 16:16:31 +0900136 log.debug("populateAllRoutingRules: populationStatus is SUCCEEDED");
137 populationStatus = Status.SUCCEEDED;
Saurav Das88979182015-10-19 14:37:36 -0700138 log.info("Completed routing rule population. Total # of rules pushed : {}",
HIGUCHI Yuta16d8fd52015-09-08 16:16:31 +0900139 rulePopulator.getCounter());
140 return true;
141 } finally {
142 statusLock.unlock();
sangho80f11cb2015-04-01 13:05:26 -0700143 }
sangho80f11cb2015-04-01 13:05:26 -0700144 }
145
sanghofb7c7292015-04-13 15:15:58 -0700146 /**
147 * Populates the routing rules according to the route changes due to the link
148 * failure or link add. It computes the routes changed due to the link changes and
Saurav Das1b391d52016-11-29 14:27:25 -0800149 * repopulates the rules only for these routes. Note that when a switch goes
150 * away, all of its links fail as well, but this is handled as a single
151 * switch removal event.
sanghofb7c7292015-04-13 15:15:58 -0700152 *
Saurav Das1b391d52016-11-29 14:27:25 -0800153 * @param failedLink the single failed link, or null for other conditions
154 * such as an added link or a removed switch
sanghofb7c7292015-04-13 15:15:58 -0700155 * @return true if it succeeds to populate all rules, false otherwise
156 */
Saurav Das1b391d52016-11-29 14:27:25 -0800157 public boolean populateRoutingRulesForLinkStatusChange(Link failedLink) {
sanghofb7c7292015-04-13 15:15:58 -0700158
HIGUCHI Yuta16d8fd52015-09-08 16:16:31 +0900159 statusLock.lock();
160 try {
sanghofb7c7292015-04-13 15:15:58 -0700161
162 if (populationStatus == Status.STARTED) {
sanghodf0153f2015-05-05 14:13:34 -0700163 log.warn("Previous rule population is not finished.");
sanghofb7c7292015-04-13 15:15:58 -0700164 return true;
165 }
166
sangho28d0b6d2015-05-07 13:30:57 -0700167 // Take the snapshots of the links
168 updatedEcmpSpgMap = new HashMap<>();
169 for (Device sw : srManager.deviceService.getDevices()) {
Charles Chan77277672015-10-20 16:24:19 -0700170 if (!srManager.mastershipService.isLocalMaster(sw.id())) {
sangho28d0b6d2015-05-07 13:30:57 -0700171 continue;
172 }
Shashikanth VH0637b162015-12-11 01:32:44 +0530173 EcmpShortestPathGraph ecmpSpgUpdated =
174 new EcmpShortestPathGraph(sw.id(), srManager);
sangho28d0b6d2015-05-07 13:30:57 -0700175 updatedEcmpSpgMap.put(sw.id(), ecmpSpgUpdated);
176 }
177
sanghodf0153f2015-05-05 14:13:34 -0700178 log.info("Starts rule population from link change");
179
sanghofb7c7292015-04-13 15:15:58 -0700180 Set<ArrayList<DeviceId>> routeChanges;
Srikanth Vavilapalli7cd16712015-05-04 09:48:09 -0700181 log.trace("populateRoutingRulesForLinkStatusChange: "
182 + "populationStatus is STARTED");
sanghofb7c7292015-04-13 15:15:58 -0700183 populationStatus = Status.STARTED;
Saurav Das1b391d52016-11-29 14:27:25 -0800184 // try optimized re-routing
185 if (failedLink == null) {
186 // Compare all routes of existing ECMP SPG to new ECMP SPG
sanghofb7c7292015-04-13 15:15:58 -0700187 routeChanges = computeRouteChange();
188 } else {
189 // Compare existing ECMP SPG only with the link removed
Saurav Das1b391d52016-11-29 14:27:25 -0800190 routeChanges = computeDamagedRoutes(failedLink);
sanghofb7c7292015-04-13 15:15:58 -0700191 }
192
Saurav Das1b391d52016-11-29 14:27:25 -0800193 // do full re-routing if optimized routing returns null routeChanges
Saurav Dasb149be12016-06-07 10:08:06 -0700194 if (routeChanges == null) {
195 return populateAllRoutingRules();
196 }
197
sanghofb7c7292015-04-13 15:15:58 -0700198 if (routeChanges.isEmpty()) {
sanghodf0153f2015-05-05 14:13:34 -0700199 log.info("No route changes for the link status change");
Srikanth Vavilapalli7cd16712015-05-04 09:48:09 -0700200 log.debug("populateRoutingRulesForLinkStatusChange: populationStatus is SUCCEEDED");
sanghofb7c7292015-04-13 15:15:58 -0700201 populationStatus = Status.SUCCEEDED;
202 return true;
203 }
204
205 if (repopulateRoutingRulesForRoutes(routeChanges)) {
Srikanth Vavilapalli7cd16712015-05-04 09:48:09 -0700206 log.debug("populateRoutingRulesForLinkStatusChange: populationStatus is SUCCEEDED");
sanghofb7c7292015-04-13 15:15:58 -0700207 populationStatus = Status.SUCCEEDED;
208 log.info("Complete to repopulate the rules. # of rules populated : {}",
209 rulePopulator.getCounter());
210 return true;
211 } else {
Srikanth Vavilapalli7cd16712015-05-04 09:48:09 -0700212 log.debug("populateRoutingRulesForLinkStatusChange: populationStatus is ABORTED");
sanghofb7c7292015-04-13 15:15:58 -0700213 populationStatus = Status.ABORTED;
214 log.warn("Failed to repopulate the rules.");
215 return false;
216 }
HIGUCHI Yuta16d8fd52015-09-08 16:16:31 +0900217 } finally {
218 statusLock.unlock();
sanghofb7c7292015-04-13 15:15:58 -0700219 }
220 }
221
222 private boolean repopulateRoutingRulesForRoutes(Set<ArrayList<DeviceId>> routes) {
223 rulePopulator.resetCounter();
Srikanth Vavilapalli64d96c12015-05-14 20:22:47 -0700224 HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>> routesBydevice =
225 new HashMap<>();
sanghofb7c7292015-04-13 15:15:58 -0700226 for (ArrayList<DeviceId> link: routes) {
sangho2165d222015-05-01 09:38:25 -0700227 // When only the source device is defined, reinstall routes to all other devices
sanghofb7c7292015-04-13 15:15:58 -0700228 if (link.size() == 1) {
Srikanth Vavilapalli7cd16712015-05-04 09:48:09 -0700229 log.trace("repopulateRoutingRulesForRoutes: running ECMP graph for device {}", link.get(0));
Shashikanth VH0637b162015-12-11 01:32:44 +0530230 EcmpShortestPathGraph ecmpSpg = new EcmpShortestPathGraph(link.get(0), srManager);
Charles Chanc22cef32016-04-29 14:38:22 -0700231 if (populateEcmpRoutingRules(link.get(0), ecmpSpg, ImmutableSet.of())) {
Saurav Dase0237a32016-05-27 13:54:07 -0700232 log.debug("Populating flow rules from all to dest:{} is successful",
Srikanth Vavilapalli64d96c12015-05-14 20:22:47 -0700233 link.get(0));
sanghofb7c7292015-04-13 15:15:58 -0700234 currentEcmpSpgMap.put(link.get(0), ecmpSpg);
sanghodf0153f2015-05-05 14:13:34 -0700235 } else {
Saurav Dase0237a32016-05-27 13:54:07 -0700236 log.warn("Failed to populate the flow rules from all to dest:{}", link.get(0));
sanghodf0153f2015-05-05 14:13:34 -0700237 return false;
sanghofb7c7292015-04-13 15:15:58 -0700238 }
sangho28d0b6d2015-05-07 13:30:57 -0700239 } else {
Srikanth Vavilapalli64d96c12015-05-14 20:22:47 -0700240 ArrayList<ArrayList<DeviceId>> deviceRoutes =
241 routesBydevice.get(link.get(1));
242 if (deviceRoutes == null) {
243 deviceRoutes = new ArrayList<>();
244 routesBydevice.put(link.get(1), deviceRoutes);
245 }
246 deviceRoutes.add(link);
247 }
248 }
249
250 for (DeviceId impactedDevice : routesBydevice.keySet()) {
251 ArrayList<ArrayList<DeviceId>> deviceRoutes =
252 routesBydevice.get(impactedDevice);
253 for (ArrayList<DeviceId> link: deviceRoutes) {
254 log.debug("repopulate RoutingRules For Routes {} -> {}",
255 link.get(0), link.get(1));
sangho28d0b6d2015-05-07 13:30:57 -0700256 DeviceId src = link.get(0);
257 DeviceId dst = link.get(1);
Shashikanth VH0637b162015-12-11 01:32:44 +0530258 EcmpShortestPathGraph ecmpSpg = updatedEcmpSpgMap.get(dst);
sangho28d0b6d2015-05-07 13:30:57 -0700259 HashMap<Integer, HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>>> switchVia =
260 ecmpSpg.getAllLearnedSwitchesAndVia();
261 for (Integer itrIdx : switchVia.keySet()) {
262 HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>> swViaMap =
263 switchVia.get(itrIdx);
264 for (DeviceId targetSw : swViaMap.keySet()) {
265 if (!targetSw.equals(src)) {
266 continue;
267 }
268 Set<DeviceId> nextHops = new HashSet<>();
269 for (ArrayList<DeviceId> via : swViaMap.get(targetSw)) {
270 if (via.isEmpty()) {
271 nextHops.add(dst);
272 } else {
273 nextHops.add(via.get(0));
274 }
275 }
Charles Chanc22cef32016-04-29 14:38:22 -0700276 if (!populateEcmpRoutingRulePartial(targetSw, dst,
277 nextHops, ImmutableSet.of())) {
sangho28d0b6d2015-05-07 13:30:57 -0700278 return false;
sanghofb7c7292015-04-13 15:15:58 -0700279 }
Srikanth Vavilapalli64d96c12015-05-14 20:22:47 -0700280 log.debug("Populating flow rules from {} to {} is successful",
281 targetSw, dst);
sanghofb7c7292015-04-13 15:15:58 -0700282 }
sanghofb7c7292015-04-13 15:15:58 -0700283 }
Srikanth Vavilapalli64d96c12015-05-14 20:22:47 -0700284 //currentEcmpSpgMap.put(dst, ecmpSpg);
sanghofb7c7292015-04-13 15:15:58 -0700285 }
Srikanth Vavilapalli64d96c12015-05-14 20:22:47 -0700286 //Only if all the flows for all impacted routes to a
287 //specific target are pushed successfully, update the
Saurav Das1b391d52016-11-29 14:27:25 -0800288 //ECMP graph for that target. Or else the next event
289 //would not see any changes in the ECMP graphs.
290 //In another case, the target switch has gone away, so
291 //routes can't be installed. In that case, the current map
292 //is updated here, without any flows being pushed.
Srikanth Vavilapalli64d96c12015-05-14 20:22:47 -0700293 currentEcmpSpgMap.put(impactedDevice,
294 updatedEcmpSpgMap.get(impactedDevice));
sanghofb7c7292015-04-13 15:15:58 -0700295 }
296 return true;
297 }
298
Saurav Dasb149be12016-06-07 10:08:06 -0700299 /**
Saurav Das1b391d52016-11-29 14:27:25 -0800300 * Computes set of affected routes due to failed link. Assumes
Saurav Dasb149be12016-06-07 10:08:06 -0700301 * previous ecmp shortest-path graph exists for a switch in order to compute
302 * affected routes. If such a graph does not exist, the method returns null.
303 *
304 * @param linkFail the failed link
305 * @return the set of affected routes which may be empty if no routes were
306 * affected, or null if no previous ecmp spg was found for comparison
307 */
sanghofb7c7292015-04-13 15:15:58 -0700308 private Set<ArrayList<DeviceId>> computeDamagedRoutes(Link linkFail) {
309
310 Set<ArrayList<DeviceId>> routes = new HashSet<>();
311
312 for (Device sw : srManager.deviceService.getDevices()) {
Srikanth Vavilapalli64d96c12015-05-14 20:22:47 -0700313 log.debug("Computing the impacted routes for device {} due to link fail",
314 sw.id());
Charles Chan77277672015-10-20 16:24:19 -0700315 if (!srManager.mastershipService.isLocalMaster(sw.id())) {
Saurav Dasb149be12016-06-07 10:08:06 -0700316 log.debug("No mastership for {} .. skipping route optimization",
317 sw.id());
sanghofb7c7292015-04-13 15:15:58 -0700318 continue;
319 }
Shashikanth VH0637b162015-12-11 01:32:44 +0530320 EcmpShortestPathGraph ecmpSpg = currentEcmpSpgMap.get(sw.id());
sanghofb7c7292015-04-13 15:15:58 -0700321 if (ecmpSpg == null) {
Saurav Dasb149be12016-06-07 10:08:06 -0700322 log.warn("No existing ECMP graph for switch {}. Aborting optimized"
323 + " rerouting and opting for full-reroute", sw.id());
324 return null;
sanghofb7c7292015-04-13 15:15:58 -0700325 }
326 HashMap<Integer, HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>>> switchVia =
327 ecmpSpg.getAllLearnedSwitchesAndVia();
328 for (Integer itrIdx : switchVia.keySet()) {
Saurav Dasb149be12016-06-07 10:08:06 -0700329 log.trace("Iterindex# {}", itrIdx);
sanghofb7c7292015-04-13 15:15:58 -0700330 HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>> swViaMap =
331 switchVia.get(itrIdx);
332 for (DeviceId targetSw : swViaMap.keySet()) {
Saurav Das1b391d52016-11-29 14:27:25 -0800333 DeviceId rootSw = sw.id();
Saurav Dasb149be12016-06-07 10:08:06 -0700334 if (log.isTraceEnabled()) {
Saurav Das1b391d52016-11-29 14:27:25 -0800335 log.trace("TargetSwitch {} --> RootSwitch {}", targetSw, rootSw);
Saurav Dasb149be12016-06-07 10:08:06 -0700336 for (ArrayList<DeviceId> via : swViaMap.get(targetSw)) {
337 log.trace(" Via:");
338 via.forEach(e -> { log.trace(" {}", e); });
339 }
340 }
sanghofb7c7292015-04-13 15:15:58 -0700341 Set<ArrayList<DeviceId>> subLinks =
Saurav Das1b391d52016-11-29 14:27:25 -0800342 computeLinks(targetSw, rootSw, swViaMap);
sanghofb7c7292015-04-13 15:15:58 -0700343 for (ArrayList<DeviceId> alink: subLinks) {
Srikanth Vavilapalli64d96c12015-05-14 20:22:47 -0700344 if ((alink.get(0).equals(linkFail.src().deviceId()) &&
345 alink.get(1).equals(linkFail.dst().deviceId()))
346 ||
347 (alink.get(0).equals(linkFail.dst().deviceId()) &&
348 alink.get(1).equals(linkFail.src().deviceId()))) {
Saurav Das1b391d52016-11-29 14:27:25 -0800349 log.debug("Impacted route:{}->{}", targetSw, rootSw);
sanghofb7c7292015-04-13 15:15:58 -0700350 ArrayList<DeviceId> aRoute = new ArrayList<>();
351 aRoute.add(targetSw);
Saurav Das1b391d52016-11-29 14:27:25 -0800352 aRoute.add(rootSw);
sanghofb7c7292015-04-13 15:15:58 -0700353 routes.add(aRoute);
354 break;
355 }
356 }
357 }
358 }
sangho28d0b6d2015-05-07 13:30:57 -0700359
sanghofb7c7292015-04-13 15:15:58 -0700360 }
361
362 return routes;
363 }
364
Saurav Das1b391d52016-11-29 14:27:25 -0800365 /**
366 * Computes set of affected routes due to new links or failed switches.
367 *
368 * @return the set of affected routes which may be empty if no routes were
369 * affected
370 */
sanghofb7c7292015-04-13 15:15:58 -0700371 private Set<ArrayList<DeviceId>> computeRouteChange() {
372
Saurav Das1b391d52016-11-29 14:27:25 -0800373 ImmutableSet.Builder<ArrayList<DeviceId>> changedRoutesBuilder =
374 ImmutableSet.builder();
sanghofb7c7292015-04-13 15:15:58 -0700375
376 for (Device sw : srManager.deviceService.getDevices()) {
Saurav Das1b391d52016-11-29 14:27:25 -0800377 DeviceId rootSw = sw.id();
378 log.debug("Computing the impacted routes for device {}", rootSw);
379 if (!srManager.mastershipService.isLocalMaster(rootSw)) {
Saurav Dasb149be12016-06-07 10:08:06 -0700380 log.debug("No mastership for {} ... skipping route optimization",
Saurav Das1b391d52016-11-29 14:27:25 -0800381 rootSw);
sanghofb7c7292015-04-13 15:15:58 -0700382 continue;
383 }
Saurav Dasb149be12016-06-07 10:08:06 -0700384 if (log.isTraceEnabled()) {
Saurav Das1b391d52016-11-29 14:27:25 -0800385 log.trace("link of {} - ", rootSw);
386 for (Link link: srManager.linkService.getDeviceLinks(rootSw)) {
Saurav Dasb149be12016-06-07 10:08:06 -0700387 log.trace("{} -> {} ", link.src().deviceId(), link.dst().deviceId());
388 }
sangho28d0b6d2015-05-07 13:30:57 -0700389 }
Saurav Das1b391d52016-11-29 14:27:25 -0800390 EcmpShortestPathGraph currEcmpSpg = currentEcmpSpgMap.get(rootSw);
391 if (currEcmpSpg == null) {
392 log.debug("No existing ECMP graph for device {}", rootSw);
393 changedRoutesBuilder.add(Lists.newArrayList(rootSw));
sanghofb7c7292015-04-13 15:15:58 -0700394 continue;
395 }
Saurav Das1b391d52016-11-29 14:27:25 -0800396 EcmpShortestPathGraph newEcmpSpg = updatedEcmpSpgMap.get(rootSw);
397 if (log.isTraceEnabled()) {
398 log.trace("Root switch: {}", rootSw);
399 log.trace(" Current/Existing SPG: {}", currEcmpSpg);
400 log.trace(" New/Updated SPG: {}", newEcmpSpg);
401 }
402 // first use the updated/new map to compare to current/existing map
403 // as new links may have come up
404 changedRoutesBuilder.addAll(compareGraphs(newEcmpSpg, currEcmpSpg, rootSw));
405 // then use the current/existing map to compare to updated/new map
406 // as switch may have been removed
407 changedRoutesBuilder.addAll(compareGraphs(currEcmpSpg, newEcmpSpg, rootSw));
408 }
sanghofb7c7292015-04-13 15:15:58 -0700409
Saurav Das1b391d52016-11-29 14:27:25 -0800410 Set<ArrayList<DeviceId>> changedRoutes = changedRoutesBuilder.build();
411 for (ArrayList<DeviceId> route: changedRoutes) {
412 log.debug("Route changes Target -> Root");
413 if (route.size() == 1) {
414 log.debug(" : all -> {}", route.get(0));
415 } else {
416 log.debug(" : {} -> {}", route.get(0), route.get(1));
417 }
418 }
419 return changedRoutes;
420 }
421
422 /**
423 * For the root switch, searches all the target nodes reachable in the base
424 * graph, and compares paths to the ones in the comp graph.
425 *
426 * @param base the graph that is indexed for all reachable target nodes
427 * from the root node
428 * @param comp the graph that the base graph is compared to
429 * @param rootSw both ecmp graphs are calculated for the root node
430 * @return all the routes that have changed in the base graph
431 */
432 private Set<ArrayList<DeviceId>> compareGraphs(EcmpShortestPathGraph base,
433 EcmpShortestPathGraph comp,
434 DeviceId rootSw) {
435 ImmutableSet.Builder<ArrayList<DeviceId>> changedRoutesBuilder =
436 ImmutableSet.builder();
437 HashMap<Integer, HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>>> baseMap =
438 base.getAllLearnedSwitchesAndVia();
439 HashMap<Integer, HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>>> compMap =
440 comp.getAllLearnedSwitchesAndVia();
441 for (Integer itrIdx : baseMap.keySet()) {
442 HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>> baseViaMap =
443 baseMap.get(itrIdx);
444 for (DeviceId targetSw : baseViaMap.keySet()) {
445 ArrayList<ArrayList<DeviceId>> basePath = baseViaMap.get(targetSw);
446 ArrayList<ArrayList<DeviceId>> compPath = getVia(compMap, targetSw);
447 if ((compPath == null) || !basePath.equals(compPath)) {
448 log.debug("Impacted route:{} -> {}", targetSw, rootSw);
449 ArrayList<DeviceId> route = new ArrayList<>();
450 route.add(targetSw);
451 route.add(rootSw);
452 changedRoutesBuilder.add(route);
sanghofb7c7292015-04-13 15:15:58 -0700453 }
454 }
sangho28d0b6d2015-05-07 13:30:57 -0700455 }
Saurav Das1b391d52016-11-29 14:27:25 -0800456 return changedRoutesBuilder.build();
sanghofb7c7292015-04-13 15:15:58 -0700457 }
458
459 private ArrayList<ArrayList<DeviceId>> getVia(HashMap<Integer, HashMap<DeviceId,
Saurav Das1b391d52016-11-29 14:27:25 -0800460 ArrayList<ArrayList<DeviceId>>>> switchVia, DeviceId targetSw) {
sanghofb7c7292015-04-13 15:15:58 -0700461 for (Integer itrIdx : switchVia.keySet()) {
462 HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>> swViaMap =
463 switchVia.get(itrIdx);
Saurav Das1b391d52016-11-29 14:27:25 -0800464 if (swViaMap.get(targetSw) == null) {
sanghofb7c7292015-04-13 15:15:58 -0700465 continue;
466 } else {
Saurav Das1b391d52016-11-29 14:27:25 -0800467 return swViaMap.get(targetSw);
sanghofb7c7292015-04-13 15:15:58 -0700468 }
469 }
470
Srikanth Vavilapalli64d96c12015-05-14 20:22:47 -0700471 return null;
sanghofb7c7292015-04-13 15:15:58 -0700472 }
473
474 private Set<ArrayList<DeviceId>> computeLinks(DeviceId src,
475 DeviceId dst,
476 HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>> viaMap) {
477 Set<ArrayList<DeviceId>> subLinks = Sets.newHashSet();
478 for (ArrayList<DeviceId> via : viaMap.get(src)) {
479 DeviceId linkSrc = src;
480 DeviceId linkDst = dst;
481 for (DeviceId viaDevice: via) {
482 ArrayList<DeviceId> link = new ArrayList<>();
483 linkDst = viaDevice;
484 link.add(linkSrc);
485 link.add(linkDst);
486 subLinks.add(link);
487 linkSrc = viaDevice;
488 }
489 ArrayList<DeviceId> link = new ArrayList<>();
490 link.add(linkSrc);
491 link.add(dst);
492 subLinks.add(link);
493 }
494
495 return subLinks;
496 }
497
Charles Chanc22cef32016-04-29 14:38:22 -0700498 /**
499 * Populate ECMP rules for subnets from all switches to destination.
500 *
501 * @param destSw Device ID of destination switch
502 * @param ecmpSPG ECMP shortest path graph
503 * @param subnets Subnets to be populated. If empty, populate all configured subnets.
504 * @return true if succeed
505 */
sanghofb7c7292015-04-13 15:15:58 -0700506 private boolean populateEcmpRoutingRules(DeviceId destSw,
Charles Chanc22cef32016-04-29 14:38:22 -0700507 EcmpShortestPathGraph ecmpSPG,
508 Set<Ip4Prefix> subnets) {
sangho80f11cb2015-04-01 13:05:26 -0700509
Srikanth Vavilapalli64505482015-04-21 13:04:13 -0700510 HashMap<Integer, HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>>> switchVia = ecmpSPG
511 .getAllLearnedSwitchesAndVia();
sangho80f11cb2015-04-01 13:05:26 -0700512 for (Integer itrIdx : switchVia.keySet()) {
Srikanth Vavilapalli64505482015-04-21 13:04:13 -0700513 HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>> swViaMap = switchVia
514 .get(itrIdx);
sangho80f11cb2015-04-01 13:05:26 -0700515 for (DeviceId targetSw : swViaMap.keySet()) {
sangho80f11cb2015-04-01 13:05:26 -0700516 Set<DeviceId> nextHops = new HashSet<>();
Saurav Das88979182015-10-19 14:37:36 -0700517 log.debug("** Iter: {} root: {} target: {}", itrIdx, destSw, targetSw);
sangho80f11cb2015-04-01 13:05:26 -0700518 for (ArrayList<DeviceId> via : swViaMap.get(targetSw)) {
519 if (via.isEmpty()) {
520 nextHops.add(destSw);
521 } else {
522 nextHops.add(via.get(0));
523 }
524 }
Charles Chanc22cef32016-04-29 14:38:22 -0700525 if (!populateEcmpRoutingRulePartial(targetSw, destSw, nextHops, subnets)) {
sangho80f11cb2015-04-01 13:05:26 -0700526 return false;
527 }
528 }
529 }
530
531 return true;
532 }
533
Charles Chanc22cef32016-04-29 14:38:22 -0700534 /**
535 * Populate ECMP rules for subnets from target to destination via nexthops.
536 *
Saurav Dase0237a32016-05-27 13:54:07 -0700537 * @param targetSw Device ID of target switch in which rules will be programmed
538 * @param destSw Device ID of final destination switch to which the rules will forward
539 * @param nextHops List of next hops via which destSw will be reached
Charles Chanc22cef32016-04-29 14:38:22 -0700540 * @param subnets Subnets to be populated. If empty, populate all configured subnets.
541 * @return true if succeed
542 */
Srikanth Vavilapalli64505482015-04-21 13:04:13 -0700543 private boolean populateEcmpRoutingRulePartial(DeviceId targetSw,
544 DeviceId destSw,
Charles Chanc22cef32016-04-29 14:38:22 -0700545 Set<DeviceId> nextHops,
546 Set<Ip4Prefix> subnets) {
sangho80f11cb2015-04-01 13:05:26 -0700547 boolean result;
548
549 if (nextHops.isEmpty()) {
550 nextHops.add(destSw);
551 }
Srikanth Vavilapalli64505482015-04-21 13:04:13 -0700552 // If both target switch and dest switch are edge routers, then set IP
sanghodf0153f2015-05-05 14:13:34 -0700553 // rule for both subnet and router IP.
Charles Chan319d1a22015-11-03 10:42:14 -0800554 boolean targetIsEdge;
555 boolean destIsEdge;
556 Ip4Address destRouterIp;
557
558 try {
559 targetIsEdge = config.isEdgeDevice(targetSw);
560 destIsEdge = config.isEdgeDevice(destSw);
561 destRouterIp = config.getRouterIp(destSw);
562 } catch (DeviceConfigNotFoundException e) {
563 log.warn(e.getMessage() + " Aborting populateEcmpRoutingRulePartial.");
564 return false;
565 }
566
567 if (targetIsEdge && destIsEdge) {
Charles Chanc22cef32016-04-29 14:38:22 -0700568 subnets = (subnets != null && !subnets.isEmpty()) ? subnets : config.getSubnets(destSw);
Saurav Das88979182015-10-19 14:37:36 -0700569 log.debug("* populateEcmpRoutingRulePartial in device {} towards {} for subnets {}",
Saurav Das4c35fc42015-11-20 15:27:53 -0800570 targetSw, destSw, subnets);
Charles Chanc22cef32016-04-29 14:38:22 -0700571 result = rulePopulator.populateIpRuleForSubnet(targetSw, subnets,
572 destSw, nextHops);
sangho80f11cb2015-04-01 13:05:26 -0700573 if (!result) {
574 return false;
575 }
576
Charles Chan319d1a22015-11-03 10:42:14 -0800577 Ip4Address routerIp = destRouterIp;
sangho9b169e32015-04-14 16:27:13 -0700578 IpPrefix routerIpPrefix = IpPrefix.valueOf(routerIp, IpPrefix.MAX_INET_MASK_LENGTH);
Saurav Das88979182015-10-19 14:37:36 -0700579 log.debug("* populateEcmpRoutingRulePartial in device {} towards {} for router IP {}",
Saurav Das4c35fc42015-11-20 15:27:53 -0800580 targetSw, destSw, routerIpPrefix);
sangho9b169e32015-04-14 16:27:13 -0700581 result = rulePopulator.populateIpRuleForRouter(targetSw, routerIpPrefix, destSw, nextHops);
sangho80f11cb2015-04-01 13:05:26 -0700582 if (!result) {
583 return false;
584 }
585
Charles Chan319d1a22015-11-03 10:42:14 -0800586 } else if (targetIsEdge) {
Saurav Das4c35fc42015-11-20 15:27:53 -0800587 // If the target switch is an edge router, then set IP rules for the router IP.
Charles Chan319d1a22015-11-03 10:42:14 -0800588 Ip4Address routerIp = destRouterIp;
sangho9b169e32015-04-14 16:27:13 -0700589 IpPrefix routerIpPrefix = IpPrefix.valueOf(routerIp, IpPrefix.MAX_INET_MASK_LENGTH);
Saurav Das88979182015-10-19 14:37:36 -0700590 log.debug("* populateEcmpRoutingRulePartial in device {} towards {} for router IP {}",
Saurav Das4c35fc42015-11-20 15:27:53 -0800591 targetSw, destSw, routerIpPrefix);
sangho9b169e32015-04-14 16:27:13 -0700592 result = rulePopulator.populateIpRuleForRouter(targetSw, routerIpPrefix, destSw, nextHops);
sangho80f11cb2015-04-01 13:05:26 -0700593 if (!result) {
594 return false;
595 }
sanghodf0153f2015-05-05 14:13:34 -0700596 }
sanghodf0153f2015-05-05 14:13:34 -0700597 // Populates MPLS rules to all routers
Saurav Das88979182015-10-19 14:37:36 -0700598 log.debug("* populateEcmpRoutingRulePartial in device{} towards {} for all MPLS rules",
Srikanth Vavilapalli7cd16712015-05-04 09:48:09 -0700599 targetSw, destSw);
sanghodf0153f2015-05-05 14:13:34 -0700600 result = rulePopulator.populateMplsRule(targetSw, destSw, nextHops);
601 if (!result) {
602 return false;
sangho80f11cb2015-04-01 13:05:26 -0700603 }
sangho80f11cb2015-04-01 13:05:26 -0700604 return true;
605 }
606
607 /**
Saurav Das9f1c42e2015-10-23 10:51:11 -0700608 * Populates filtering rules for permitting Router DstMac and VLAN.
sangho80f11cb2015-04-01 13:05:26 -0700609 *
610 * @param deviceId Switch ID to set the rules
611 */
Saurav Das9f1c42e2015-10-23 10:51:11 -0700612 public void populatePortAddressingRules(DeviceId deviceId) {
Saurav Das9f1c42e2015-10-23 10:51:11 -0700613 rulePopulator.populateRouterIpPunts(deviceId);
Pier Luigib9632ba2017-01-12 18:14:58 -0800614 rulePopulator.populateArpNdpPunts(deviceId);
Saurav Das07c74602016-04-27 18:35:50 -0700615
616 // Although device is added, sometimes device store does not have the
617 // ports for this device yet. It results in missing filtering rules in the
618 // switch. We will attempt it a few times. If it still does not work,
619 // user can manually repopulate using CLI command sr-reroute-network
Saurav Dasd1872b02016-12-02 15:43:47 -0800620 PortFilterInfo firstRun = rulePopulator.populateRouterMacVlanFilters(deviceId);
621 if (firstRun == null) {
622 firstRun = new PortFilterInfo(0, 0, 0);
Saurav Das07c74602016-04-27 18:35:50 -0700623 }
Saurav Dasd1872b02016-12-02 15:43:47 -0800624 executorService.schedule(new RetryFilters(deviceId, firstRun),
625 RETRY_INTERVAL_MS, TimeUnit.MILLISECONDS);
sangho80f11cb2015-04-01 13:05:26 -0700626 }
627
628 /**
Srikanth Vavilapalli64505482015-04-21 13:04:13 -0700629 * Start the flow rule population process if it was never started. The
630 * process finishes successfully when all flow rules are set and stops with
631 * ABORTED status when any groups required for flows is not set yet.
sangho80f11cb2015-04-01 13:05:26 -0700632 */
633 public void startPopulationProcess() {
HIGUCHI Yuta16d8fd52015-09-08 16:16:31 +0900634 statusLock.lock();
635 try {
Srikanth Vavilapalli64505482015-04-21 13:04:13 -0700636 if (populationStatus == Status.IDLE
Srikanth Vavilapalli7cd16712015-05-04 09:48:09 -0700637 || populationStatus == Status.SUCCEEDED
638 || populationStatus == Status.ABORTED) {
sangho80f11cb2015-04-01 13:05:26 -0700639 populationStatus = Status.STARTED;
640 populateAllRoutingRules();
Srikanth Vavilapalli7cd16712015-05-04 09:48:09 -0700641 } else {
642 log.warn("Not initiating startPopulationProcess as populationStatus is {}",
643 populationStatus);
sangho80f11cb2015-04-01 13:05:26 -0700644 }
HIGUCHI Yuta16d8fd52015-09-08 16:16:31 +0900645 } finally {
646 statusLock.unlock();
sangho80f11cb2015-04-01 13:05:26 -0700647 }
648 }
649
650 /**
651 * Resume the flow rule population process if it was aborted for any reason.
652 * Mostly the process is aborted when the groups required are not set yet.
Saurav Das88979182015-10-19 14:37:36 -0700653 * XXX is this called?
654 *
sangho80f11cb2015-04-01 13:05:26 -0700655 */
656 public void resumePopulationProcess() {
HIGUCHI Yuta16d8fd52015-09-08 16:16:31 +0900657 statusLock.lock();
658 try {
sangho80f11cb2015-04-01 13:05:26 -0700659 if (populationStatus == Status.ABORTED) {
660 populationStatus = Status.STARTED;
Srikanth Vavilapalli64505482015-04-21 13:04:13 -0700661 // TODO: we need to restart from the point aborted instead of
662 // restarting.
sangho80f11cb2015-04-01 13:05:26 -0700663 populateAllRoutingRules();
664 }
HIGUCHI Yuta16d8fd52015-09-08 16:16:31 +0900665 } finally {
666 statusLock.unlock();
sangho80f11cb2015-04-01 13:05:26 -0700667 }
668 }
Saurav Dasc3604f12016-03-23 11:22:49 -0700669
Charles Chanc22cef32016-04-29 14:38:22 -0700670 /**
671 * Populate rules of given subnet at given location.
672 *
673 * @param cp connect point of the subnet being added
674 * @param subnets subnet being added
675 * @return true if succeed
676 */
677 protected boolean populateSubnet(ConnectPoint cp, Set<Ip4Prefix> subnets) {
678 statusLock.lock();
679 try {
680 EcmpShortestPathGraph ecmpSpg = currentEcmpSpgMap.get(cp.deviceId());
681 if (ecmpSpg == null) {
682 log.warn("Fail to populating subnet {}: {}", subnets, ECMPSPG_MISSING);
683 return false;
684 }
685 return populateEcmpRoutingRules(cp.deviceId(), ecmpSpg, subnets);
686 } finally {
687 statusLock.unlock();
688 }
689 }
690
691 /**
692 * Revoke rules of given subnet at given location.
693 *
694 * @param subnets subnet being removed
695 * @return true if succeed
696 */
697 protected boolean revokeSubnet(Set<Ip4Prefix> subnets) {
698 statusLock.lock();
699 try {
700 return srManager.routingRulePopulator.revokeIpRuleForSubnet(subnets);
701 } finally {
702 statusLock.unlock();
703 }
704 }
705
706 protected void purgeEcmpGraph(DeviceId deviceId) {
Saurav Dasc3604f12016-03-23 11:22:49 -0700707 currentEcmpSpgMap.remove(deviceId);
Saurav Das52d4ed72016-03-28 19:00:18 -0700708 if (updatedEcmpSpgMap != null) {
709 updatedEcmpSpgMap.remove(deviceId);
710 }
Pier Ventre6d593892016-09-13 21:33:40 -0700711 this.populateRoutingRulesForLinkStatusChange(null);
Saurav Dasc3604f12016-03-23 11:22:49 -0700712 }
Saurav Das07c74602016-04-27 18:35:50 -0700713
Saurav Dasd1872b02016-12-02 15:43:47 -0800714 /**
715 * Utility class used to temporarily store information about the ports on a
716 * device processed for filtering objectives.
717 *
718 */
719 public final class PortFilterInfo {
720 int disabledPorts = 0, suppressedPorts = 0, filteredPorts = 0;
Saurav Das07c74602016-04-27 18:35:50 -0700721
Saurav Dasd1872b02016-12-02 15:43:47 -0800722 public PortFilterInfo(int disabledPorts, int suppressedPorts,
723 int filteredPorts) {
724 this.disabledPorts = disabledPorts;
725 this.filteredPorts = filteredPorts;
726 this.suppressedPorts = suppressedPorts;
727 }
728
729 @Override
730 public int hashCode() {
731 return Objects.hash(disabledPorts, filteredPorts, suppressedPorts);
732 }
733
734 @Override
735 public boolean equals(Object obj) {
736 if (this == obj) {
737 return true;
738 }
739 if ((obj == null) || (!(obj instanceof PortFilterInfo))) {
740 return false;
741 }
742 PortFilterInfo other = (PortFilterInfo) obj;
743 return ((disabledPorts == other.disabledPorts) &&
744 (filteredPorts == other.filteredPorts) &&
745 (suppressedPorts == other.suppressedPorts));
746 }
747
748 @Override
749 public String toString() {
750 MoreObjects.ToStringHelper helper = toStringHelper(this)
751 .add("disabledPorts", disabledPorts)
752 .add("suppressedPorts", suppressedPorts)
753 .add("filteredPorts", filteredPorts);
754 return helper.toString();
755 }
756 }
757
758 /**
759 * RetryFilters populates filtering objectives for a device and keeps retrying
760 * till the number of ports filtered are constant for a predefined number
761 * of attempts.
762 */
763 protected final class RetryFilters implements Runnable {
764 int constantAttempts = MAX_CONSTANT_RETRY_ATTEMPTS;
765 DeviceId devId;
766 int counter;
767 PortFilterInfo prevRun;
768
769 private RetryFilters(DeviceId deviceId, PortFilterInfo previousRun) {
Saurav Das07c74602016-04-27 18:35:50 -0700770 devId = deviceId;
Saurav Dasd1872b02016-12-02 15:43:47 -0800771 prevRun = previousRun;
772 counter = 0;
Saurav Das07c74602016-04-27 18:35:50 -0700773 }
774
775 @Override
776 public void run() {
Saurav Dasd1872b02016-12-02 15:43:47 -0800777 log.info("RETRY FILTER ATTEMPT {} ** dev:{}", ++counter, devId);
778 PortFilterInfo thisRun = rulePopulator.populateRouterMacVlanFilters(devId);
779 boolean sameResult = prevRun.equals(thisRun);
780 log.debug("dev:{} prevRun:{} thisRun:{} sameResult:{}", devId, prevRun,
781 thisRun, sameResult);
782 if (thisRun == null || !sameResult || (sameResult && --constantAttempts > 0)) {
783 executorService.schedule(this, RETRY_INTERVAL_MS, TimeUnit.MILLISECONDS);
784 if (!sameResult) {
785 constantAttempts = MAX_CONSTANT_RETRY_ATTEMPTS; //reset
786 }
Saurav Das07c74602016-04-27 18:35:50 -0700787 }
Saurav Dasd1872b02016-12-02 15:43:47 -0800788 prevRun = (thisRun == null) ? prevRun : thisRun;
Saurav Das07c74602016-04-27 18:35:50 -0700789 }
Saurav Das07c74602016-04-27 18:35:50 -0700790 }
791
sangho80f11cb2015-04-01 13:05:26 -0700792}