blob: 358fa75c3a08b33e577aa2cae4d7c269ba6d9072 [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
Charles Chanc22cef32016-04-29 14:38:22 -070018import com.google.common.collect.ImmutableSet;
sanghofb7c7292015-04-13 15:15:58 -070019import com.google.common.collect.Maps;
20import com.google.common.collect.Sets;
sangho9b169e32015-04-14 16:27:13 -070021import org.onlab.packet.Ip4Address;
Srikanth Vavilapalli37a461b2015-04-07 15:12:32 -070022import org.onlab.packet.Ip4Prefix;
sangho80f11cb2015-04-01 13:05:26 -070023import org.onlab.packet.IpPrefix;
Charles Chanc22cef32016-04-29 14:38:22 -070024import org.onosproject.net.ConnectPoint;
sangho80f11cb2015-04-01 13:05:26 -070025import org.onosproject.net.Device;
26import org.onosproject.net.DeviceId;
sanghofb7c7292015-04-13 15:15:58 -070027import org.onosproject.net.Link;
Charles Chan319d1a22015-11-03 10:42:14 -080028import org.onosproject.segmentrouting.config.DeviceConfigNotFoundException;
29import org.onosproject.segmentrouting.config.DeviceConfiguration;
sangho80f11cb2015-04-01 13:05:26 -070030import org.slf4j.Logger;
31import org.slf4j.LoggerFactory;
32
33import java.util.ArrayList;
34import java.util.HashMap;
35import java.util.HashSet;
36import java.util.Set;
Saurav Das07c74602016-04-27 18:35:50 -070037import java.util.concurrent.Executors;
38import java.util.concurrent.ScheduledExecutorService;
39import java.util.concurrent.TimeUnit;
HIGUCHI Yuta16d8fd52015-09-08 16:16:31 +090040import java.util.concurrent.locks.Lock;
41import java.util.concurrent.locks.ReentrantLock;
sangho80f11cb2015-04-01 13:05:26 -070042
43import static com.google.common.base.Preconditions.checkNotNull;
44
Charles Chanb7f75ac2016-01-11 18:28:54 -080045/**
46 * Default routing handler that is responsible for route computing and
47 * routing rule population.
48 */
sangho80f11cb2015-04-01 13:05:26 -070049public class DefaultRoutingHandler {
Saurav Dase0237a32016-05-27 13:54:07 -070050 private static final int MAX_RETRY_ATTEMPTS = 25;
Charles Chanc22cef32016-04-29 14:38:22 -070051 private static final String ECMPSPG_MISSING = "ECMP shortest path graph not found";
52 private static Logger log = LoggerFactory.getLogger(DefaultRoutingHandler.class);
sangho80f11cb2015-04-01 13:05:26 -070053
54 private SegmentRoutingManager srManager;
55 private RoutingRulePopulator rulePopulator;
Shashikanth VH0637b162015-12-11 01:32:44 +053056 private HashMap<DeviceId, EcmpShortestPathGraph> currentEcmpSpgMap;
57 private HashMap<DeviceId, EcmpShortestPathGraph> updatedEcmpSpgMap;
sangho9b169e32015-04-14 16:27:13 -070058 private DeviceConfiguration config;
HIGUCHI Yuta16d8fd52015-09-08 16:16:31 +090059 private final Lock statusLock = new ReentrantLock();
60 private volatile Status populationStatus;
Saurav Das07c74602016-04-27 18:35:50 -070061 private ScheduledExecutorService executorService = Executors.newScheduledThreadPool(1);
sangho80f11cb2015-04-01 13:05:26 -070062
63 /**
64 * Represents the default routing population status.
65 */
66 public enum Status {
67 // population process is not started yet.
68 IDLE,
69
70 // population process started.
71 STARTED,
72
Srikanth Vavilapalli64505482015-04-21 13:04:13 -070073 // population process was aborted due to errors, mostly for groups not
74 // found.
sangho80f11cb2015-04-01 13:05:26 -070075 ABORTED,
76
77 // population process was finished successfully.
78 SUCCEEDED
79 }
80
81 /**
82 * Creates a DefaultRoutingHandler object.
83 *
84 * @param srManager SegmentRoutingManager object
85 */
86 public DefaultRoutingHandler(SegmentRoutingManager srManager) {
87 this.srManager = srManager;
88 this.rulePopulator = checkNotNull(srManager.routingRulePopulator);
sangho9b169e32015-04-14 16:27:13 -070089 this.config = checkNotNull(srManager.deviceConfiguration);
sangho80f11cb2015-04-01 13:05:26 -070090 this.populationStatus = Status.IDLE;
sanghofb7c7292015-04-13 15:15:58 -070091 this.currentEcmpSpgMap = Maps.newHashMap();
sangho80f11cb2015-04-01 13:05:26 -070092 }
93
94 /**
95 * Populates all routing rules to all connected routers, including default
96 * routing rules, adjacency rules, and policy rules if any.
97 *
98 * @return true if it succeeds in populating all rules, otherwise false
99 */
100 public boolean populateAllRoutingRules() {
101
HIGUCHI Yuta16d8fd52015-09-08 16:16:31 +0900102 statusLock.lock();
103 try {
104 populationStatus = Status.STARTED;
105 rulePopulator.resetCounter();
Saurav Das88979182015-10-19 14:37:36 -0700106 log.info("Starting to populate segment-routing rules");
HIGUCHI Yuta16d8fd52015-09-08 16:16:31 +0900107 log.debug("populateAllRoutingRules: populationStatus is STARTED");
sangho80f11cb2015-04-01 13:05:26 -0700108
HIGUCHI Yuta16d8fd52015-09-08 16:16:31 +0900109 for (Device sw : srManager.deviceService.getDevices()) {
Charles Chan77277672015-10-20 16:24:19 -0700110 if (!srManager.mastershipService.isLocalMaster(sw.id())) {
HIGUCHI Yuta16d8fd52015-09-08 16:16:31 +0900111 log.debug("populateAllRoutingRules: skipping device {}...we are not master",
112 sw.id());
113 continue;
114 }
115
Shashikanth VH0637b162015-12-11 01:32:44 +0530116 EcmpShortestPathGraph ecmpSpg = new EcmpShortestPathGraph(sw.id(), srManager);
Charles Chanc22cef32016-04-29 14:38:22 -0700117 if (!populateEcmpRoutingRules(sw.id(), ecmpSpg, ImmutableSet.of())) {
HIGUCHI Yuta16d8fd52015-09-08 16:16:31 +0900118 log.debug("populateAllRoutingRules: populationStatus is ABORTED");
119 populationStatus = Status.ABORTED;
120 log.debug("Abort routing rule population");
121 return false;
122 }
123 currentEcmpSpgMap.put(sw.id(), ecmpSpg);
124
125 // TODO: Set adjacency routing rule for all switches
sangho80f11cb2015-04-01 13:05:26 -0700126 }
127
HIGUCHI Yuta16d8fd52015-09-08 16:16:31 +0900128 log.debug("populateAllRoutingRules: populationStatus is SUCCEEDED");
129 populationStatus = Status.SUCCEEDED;
Saurav Das88979182015-10-19 14:37:36 -0700130 log.info("Completed routing rule population. Total # of rules pushed : {}",
HIGUCHI Yuta16d8fd52015-09-08 16:16:31 +0900131 rulePopulator.getCounter());
132 return true;
133 } finally {
134 statusLock.unlock();
sangho80f11cb2015-04-01 13:05:26 -0700135 }
sangho80f11cb2015-04-01 13:05:26 -0700136 }
137
sanghofb7c7292015-04-13 15:15:58 -0700138 /**
139 * Populates the routing rules according to the route changes due to the link
140 * failure or link add. It computes the routes changed due to the link changes and
141 * repopulates the rules only for the routes.
142 *
143 * @param linkFail link failed, null for link added
144 * @return true if it succeeds to populate all rules, false otherwise
145 */
146 public boolean populateRoutingRulesForLinkStatusChange(Link linkFail) {
147
HIGUCHI Yuta16d8fd52015-09-08 16:16:31 +0900148 statusLock.lock();
149 try {
sanghofb7c7292015-04-13 15:15:58 -0700150
151 if (populationStatus == Status.STARTED) {
sanghodf0153f2015-05-05 14:13:34 -0700152 log.warn("Previous rule population is not finished.");
sanghofb7c7292015-04-13 15:15:58 -0700153 return true;
154 }
155
sangho28d0b6d2015-05-07 13:30:57 -0700156 // Take the snapshots of the links
157 updatedEcmpSpgMap = new HashMap<>();
158 for (Device sw : srManager.deviceService.getDevices()) {
Charles Chan77277672015-10-20 16:24:19 -0700159 if (!srManager.mastershipService.isLocalMaster(sw.id())) {
sangho28d0b6d2015-05-07 13:30:57 -0700160 continue;
161 }
Shashikanth VH0637b162015-12-11 01:32:44 +0530162 EcmpShortestPathGraph ecmpSpgUpdated =
163 new EcmpShortestPathGraph(sw.id(), srManager);
sangho28d0b6d2015-05-07 13:30:57 -0700164 updatedEcmpSpgMap.put(sw.id(), ecmpSpgUpdated);
165 }
166
sanghodf0153f2015-05-05 14:13:34 -0700167 log.info("Starts rule population from link change");
168
sanghofb7c7292015-04-13 15:15:58 -0700169 Set<ArrayList<DeviceId>> routeChanges;
Srikanth Vavilapalli7cd16712015-05-04 09:48:09 -0700170 log.trace("populateRoutingRulesForLinkStatusChange: "
171 + "populationStatus is STARTED");
sanghofb7c7292015-04-13 15:15:58 -0700172 populationStatus = Status.STARTED;
Saurav Dasb149be12016-06-07 10:08:06 -0700173 // optimized re-routing
sanghofb7c7292015-04-13 15:15:58 -0700174 if (linkFail == null) {
175 // Compare all routes of existing ECMP SPG with the new ones
176 routeChanges = computeRouteChange();
177 } else {
178 // Compare existing ECMP SPG only with the link removed
179 routeChanges = computeDamagedRoutes(linkFail);
180 }
181
Saurav Dasb149be12016-06-07 10:08:06 -0700182 // null routeChanges indicates that full re-routing is required
183 if (routeChanges == null) {
184 return populateAllRoutingRules();
185 }
186
sanghofb7c7292015-04-13 15:15:58 -0700187 if (routeChanges.isEmpty()) {
sanghodf0153f2015-05-05 14:13:34 -0700188 log.info("No route changes for the link status change");
Srikanth Vavilapalli7cd16712015-05-04 09:48:09 -0700189 log.debug("populateRoutingRulesForLinkStatusChange: populationStatus is SUCCEEDED");
sanghofb7c7292015-04-13 15:15:58 -0700190 populationStatus = Status.SUCCEEDED;
191 return true;
192 }
193
194 if (repopulateRoutingRulesForRoutes(routeChanges)) {
Srikanth Vavilapalli7cd16712015-05-04 09:48:09 -0700195 log.debug("populateRoutingRulesForLinkStatusChange: populationStatus is SUCCEEDED");
sanghofb7c7292015-04-13 15:15:58 -0700196 populationStatus = Status.SUCCEEDED;
197 log.info("Complete to repopulate the rules. # of rules populated : {}",
198 rulePopulator.getCounter());
199 return true;
200 } else {
Srikanth Vavilapalli7cd16712015-05-04 09:48:09 -0700201 log.debug("populateRoutingRulesForLinkStatusChange: populationStatus is ABORTED");
sanghofb7c7292015-04-13 15:15:58 -0700202 populationStatus = Status.ABORTED;
203 log.warn("Failed to repopulate the rules.");
204 return false;
205 }
HIGUCHI Yuta16d8fd52015-09-08 16:16:31 +0900206 } finally {
207 statusLock.unlock();
sanghofb7c7292015-04-13 15:15:58 -0700208 }
209 }
210
211 private boolean repopulateRoutingRulesForRoutes(Set<ArrayList<DeviceId>> routes) {
212 rulePopulator.resetCounter();
Srikanth Vavilapalli64d96c12015-05-14 20:22:47 -0700213 HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>> routesBydevice =
214 new HashMap<>();
sanghofb7c7292015-04-13 15:15:58 -0700215 for (ArrayList<DeviceId> link: routes) {
sangho2165d222015-05-01 09:38:25 -0700216 // When only the source device is defined, reinstall routes to all other devices
sanghofb7c7292015-04-13 15:15:58 -0700217 if (link.size() == 1) {
Srikanth Vavilapalli7cd16712015-05-04 09:48:09 -0700218 log.trace("repopulateRoutingRulesForRoutes: running ECMP graph for device {}", link.get(0));
Shashikanth VH0637b162015-12-11 01:32:44 +0530219 EcmpShortestPathGraph ecmpSpg = new EcmpShortestPathGraph(link.get(0), srManager);
Charles Chanc22cef32016-04-29 14:38:22 -0700220 if (populateEcmpRoutingRules(link.get(0), ecmpSpg, ImmutableSet.of())) {
Saurav Dase0237a32016-05-27 13:54:07 -0700221 log.debug("Populating flow rules from all to dest:{} is successful",
Srikanth Vavilapalli64d96c12015-05-14 20:22:47 -0700222 link.get(0));
sanghofb7c7292015-04-13 15:15:58 -0700223 currentEcmpSpgMap.put(link.get(0), ecmpSpg);
sanghodf0153f2015-05-05 14:13:34 -0700224 } else {
Saurav Dase0237a32016-05-27 13:54:07 -0700225 log.warn("Failed to populate the flow rules from all to dest:{}", link.get(0));
sanghodf0153f2015-05-05 14:13:34 -0700226 return false;
sanghofb7c7292015-04-13 15:15:58 -0700227 }
sangho28d0b6d2015-05-07 13:30:57 -0700228 } else {
Srikanth Vavilapalli64d96c12015-05-14 20:22:47 -0700229 ArrayList<ArrayList<DeviceId>> deviceRoutes =
230 routesBydevice.get(link.get(1));
231 if (deviceRoutes == null) {
232 deviceRoutes = new ArrayList<>();
233 routesBydevice.put(link.get(1), deviceRoutes);
234 }
235 deviceRoutes.add(link);
236 }
237 }
238
239 for (DeviceId impactedDevice : routesBydevice.keySet()) {
240 ArrayList<ArrayList<DeviceId>> deviceRoutes =
241 routesBydevice.get(impactedDevice);
242 for (ArrayList<DeviceId> link: deviceRoutes) {
243 log.debug("repopulate RoutingRules For Routes {} -> {}",
244 link.get(0), link.get(1));
sangho28d0b6d2015-05-07 13:30:57 -0700245 DeviceId src = link.get(0);
246 DeviceId dst = link.get(1);
Shashikanth VH0637b162015-12-11 01:32:44 +0530247 EcmpShortestPathGraph ecmpSpg = updatedEcmpSpgMap.get(dst);
sangho28d0b6d2015-05-07 13:30:57 -0700248 HashMap<Integer, HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>>> switchVia =
249 ecmpSpg.getAllLearnedSwitchesAndVia();
250 for (Integer itrIdx : switchVia.keySet()) {
251 HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>> swViaMap =
252 switchVia.get(itrIdx);
253 for (DeviceId targetSw : swViaMap.keySet()) {
254 if (!targetSw.equals(src)) {
255 continue;
256 }
257 Set<DeviceId> nextHops = new HashSet<>();
258 for (ArrayList<DeviceId> via : swViaMap.get(targetSw)) {
259 if (via.isEmpty()) {
260 nextHops.add(dst);
261 } else {
262 nextHops.add(via.get(0));
263 }
264 }
Charles Chanc22cef32016-04-29 14:38:22 -0700265 if (!populateEcmpRoutingRulePartial(targetSw, dst,
266 nextHops, ImmutableSet.of())) {
sangho28d0b6d2015-05-07 13:30:57 -0700267 return false;
sanghofb7c7292015-04-13 15:15:58 -0700268 }
Srikanth Vavilapalli64d96c12015-05-14 20:22:47 -0700269 log.debug("Populating flow rules from {} to {} is successful",
270 targetSw, dst);
sanghofb7c7292015-04-13 15:15:58 -0700271 }
sanghofb7c7292015-04-13 15:15:58 -0700272 }
Srikanth Vavilapalli64d96c12015-05-14 20:22:47 -0700273 //currentEcmpSpgMap.put(dst, ecmpSpg);
sanghofb7c7292015-04-13 15:15:58 -0700274 }
Srikanth Vavilapalli64d96c12015-05-14 20:22:47 -0700275 //Only if all the flows for all impacted routes to a
276 //specific target are pushed successfully, update the
277 //ECMP graph for that target. (Or else the next event
278 //would not see any changes in the ECMP graphs)
279 currentEcmpSpgMap.put(impactedDevice,
280 updatedEcmpSpgMap.get(impactedDevice));
sanghofb7c7292015-04-13 15:15:58 -0700281 }
282 return true;
283 }
284
Saurav Dasb149be12016-06-07 10:08:06 -0700285 /**
286 * Computes set of affected ECMP routes due to failed link. Assumes
287 * previous ecmp shortest-path graph exists for a switch in order to compute
288 * affected routes. If such a graph does not exist, the method returns null.
289 *
290 * @param linkFail the failed link
291 * @return the set of affected routes which may be empty if no routes were
292 * affected, or null if no previous ecmp spg was found for comparison
293 */
sanghofb7c7292015-04-13 15:15:58 -0700294 private Set<ArrayList<DeviceId>> computeDamagedRoutes(Link linkFail) {
295
296 Set<ArrayList<DeviceId>> routes = new HashSet<>();
297
298 for (Device sw : srManager.deviceService.getDevices()) {
Srikanth Vavilapalli64d96c12015-05-14 20:22:47 -0700299 log.debug("Computing the impacted routes for device {} due to link fail",
300 sw.id());
Charles Chan77277672015-10-20 16:24:19 -0700301 if (!srManager.mastershipService.isLocalMaster(sw.id())) {
Saurav Dasb149be12016-06-07 10:08:06 -0700302 log.debug("No mastership for {} .. skipping route optimization",
303 sw.id());
sanghofb7c7292015-04-13 15:15:58 -0700304 continue;
305 }
Shashikanth VH0637b162015-12-11 01:32:44 +0530306 EcmpShortestPathGraph ecmpSpg = currentEcmpSpgMap.get(sw.id());
sanghofb7c7292015-04-13 15:15:58 -0700307 if (ecmpSpg == null) {
Saurav Dasb149be12016-06-07 10:08:06 -0700308 log.warn("No existing ECMP graph for switch {}. Aborting optimized"
309 + " rerouting and opting for full-reroute", sw.id());
310 return null;
sanghofb7c7292015-04-13 15:15:58 -0700311 }
312 HashMap<Integer, HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>>> switchVia =
313 ecmpSpg.getAllLearnedSwitchesAndVia();
314 for (Integer itrIdx : switchVia.keySet()) {
Saurav Dasb149be12016-06-07 10:08:06 -0700315 log.trace("Iterindex# {}", itrIdx);
sanghofb7c7292015-04-13 15:15:58 -0700316 HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>> swViaMap =
317 switchVia.get(itrIdx);
318 for (DeviceId targetSw : swViaMap.keySet()) {
319 DeviceId destSw = sw.id();
Saurav Dasb149be12016-06-07 10:08:06 -0700320 if (log.isTraceEnabled()) {
321 log.trace("TargetSwitch {} --> RootSwitch {}", targetSw, destSw);
322 for (ArrayList<DeviceId> via : swViaMap.get(targetSw)) {
323 log.trace(" Via:");
324 via.forEach(e -> { log.trace(" {}", e); });
325 }
326 }
sanghofb7c7292015-04-13 15:15:58 -0700327 Set<ArrayList<DeviceId>> subLinks =
328 computeLinks(targetSw, destSw, swViaMap);
329 for (ArrayList<DeviceId> alink: subLinks) {
Srikanth Vavilapalli64d96c12015-05-14 20:22:47 -0700330 if ((alink.get(0).equals(linkFail.src().deviceId()) &&
331 alink.get(1).equals(linkFail.dst().deviceId()))
332 ||
333 (alink.get(0).equals(linkFail.dst().deviceId()) &&
334 alink.get(1).equals(linkFail.src().deviceId()))) {
335 log.debug("Impacted route:{}->{}", targetSw, destSw);
sanghofb7c7292015-04-13 15:15:58 -0700336 ArrayList<DeviceId> aRoute = new ArrayList<>();
337 aRoute.add(targetSw);
338 aRoute.add(destSw);
339 routes.add(aRoute);
340 break;
341 }
342 }
343 }
344 }
sangho28d0b6d2015-05-07 13:30:57 -0700345
sanghofb7c7292015-04-13 15:15:58 -0700346 }
347
348 return routes;
349 }
350
351 private Set<ArrayList<DeviceId>> computeRouteChange() {
352
353 Set<ArrayList<DeviceId>> routes = new HashSet<>();
354
355 for (Device sw : srManager.deviceService.getDevices()) {
Saurav Dasb149be12016-06-07 10:08:06 -0700356 log.debug("Computing the impacted routes for device {}", sw.id());
Charles Chan77277672015-10-20 16:24:19 -0700357 if (!srManager.mastershipService.isLocalMaster(sw.id())) {
Saurav Dasb149be12016-06-07 10:08:06 -0700358 log.debug("No mastership for {} ... skipping route optimization",
Srikanth Vavilapalli64d96c12015-05-14 20:22:47 -0700359 sw.id());
sanghofb7c7292015-04-13 15:15:58 -0700360 continue;
361 }
Saurav Dasb149be12016-06-07 10:08:06 -0700362 if (log.isTraceEnabled()) {
363 log.trace("link of {} - ", sw.id());
364 for (Link link: srManager.linkService.getDeviceLinks(sw.id())) {
365 log.trace("{} -> {} ", link.src().deviceId(), link.dst().deviceId());
366 }
sangho28d0b6d2015-05-07 13:30:57 -0700367 }
Shashikanth VH0637b162015-12-11 01:32:44 +0530368 EcmpShortestPathGraph ecmpSpg = currentEcmpSpgMap.get(sw.id());
sanghofb7c7292015-04-13 15:15:58 -0700369 if (ecmpSpg == null) {
Srikanth Vavilapalli7cd16712015-05-04 09:48:09 -0700370 log.debug("No existing ECMP graph for device {}", sw.id());
sanghofb7c7292015-04-13 15:15:58 -0700371 ArrayList<DeviceId> route = new ArrayList<>();
372 route.add(sw.id());
373 routes.add(route);
374 continue;
375 }
Shashikanth VH0637b162015-12-11 01:32:44 +0530376 EcmpShortestPathGraph newEcmpSpg = updatedEcmpSpgMap.get(sw.id());
Srikanth Vavilapalli64d96c12015-05-14 20:22:47 -0700377 //currentEcmpSpgMap.put(sw.id(), newEcmpSpg);
sanghofb7c7292015-04-13 15:15:58 -0700378 HashMap<Integer, HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>>> switchVia =
379 ecmpSpg.getAllLearnedSwitchesAndVia();
380 HashMap<Integer, HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>>> switchViaUpdated =
381 newEcmpSpg.getAllLearnedSwitchesAndVia();
382
sangho28d0b6d2015-05-07 13:30:57 -0700383 for (Integer itrIdx : switchViaUpdated.keySet()) {
384 HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>> swViaMapUpdated =
385 switchViaUpdated.get(itrIdx);
386 for (DeviceId srcSw : swViaMapUpdated.keySet()) {
387 ArrayList<ArrayList<DeviceId>> viaUpdated = swViaMapUpdated.get(srcSw);
388 ArrayList<ArrayList<DeviceId>> via = getVia(switchVia, srcSw);
Srikanth Vavilapalli64d96c12015-05-14 20:22:47 -0700389 if ((via == null) || !viaUpdated.equals(via)) {
Saurav Dasb149be12016-06-07 10:08:06 -0700390 log.debug("Impacted route:{} -> {}", srcSw, sw.id());
sanghofb7c7292015-04-13 15:15:58 -0700391 ArrayList<DeviceId> route = new ArrayList<>();
392 route.add(srcSw);
393 route.add(sw.id());
394 routes.add(route);
395 }
396 }
397 }
sangho28d0b6d2015-05-07 13:30:57 -0700398 }
sanghofb7c7292015-04-13 15:15:58 -0700399
Saurav Dasb149be12016-06-07 10:08:06 -0700400 if (log.isTraceEnabled()) {
401 for (ArrayList<DeviceId> link: routes) {
402 log.trace("Route changes - ");
403 if (link.size() == 1) {
404 log.trace(" : all -> {}", link.get(0));
405 } else {
406 log.trace(" : {} -> {}", link.get(0), link.get(1));
407 }
sangho28d0b6d2015-05-07 13:30:57 -0700408 }
sanghofb7c7292015-04-13 15:15:58 -0700409 }
sanghofb7c7292015-04-13 15:15:58 -0700410 return routes;
411 }
412
413 private ArrayList<ArrayList<DeviceId>> getVia(HashMap<Integer, HashMap<DeviceId,
414 ArrayList<ArrayList<DeviceId>>>> switchVia, DeviceId srcSw) {
415 for (Integer itrIdx : switchVia.keySet()) {
416 HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>> swViaMap =
417 switchVia.get(itrIdx);
418 if (swViaMap.get(srcSw) == null) {
419 continue;
420 } else {
421 return swViaMap.get(srcSw);
422 }
423 }
424
Srikanth Vavilapalli64d96c12015-05-14 20:22:47 -0700425 return null;
sanghofb7c7292015-04-13 15:15:58 -0700426 }
427
428 private Set<ArrayList<DeviceId>> computeLinks(DeviceId src,
429 DeviceId dst,
430 HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>> viaMap) {
431 Set<ArrayList<DeviceId>> subLinks = Sets.newHashSet();
432 for (ArrayList<DeviceId> via : viaMap.get(src)) {
433 DeviceId linkSrc = src;
434 DeviceId linkDst = dst;
435 for (DeviceId viaDevice: via) {
436 ArrayList<DeviceId> link = new ArrayList<>();
437 linkDst = viaDevice;
438 link.add(linkSrc);
439 link.add(linkDst);
440 subLinks.add(link);
441 linkSrc = viaDevice;
442 }
443 ArrayList<DeviceId> link = new ArrayList<>();
444 link.add(linkSrc);
445 link.add(dst);
446 subLinks.add(link);
447 }
448
449 return subLinks;
450 }
451
Charles Chanc22cef32016-04-29 14:38:22 -0700452 /**
453 * Populate ECMP rules for subnets from all switches to destination.
454 *
455 * @param destSw Device ID of destination switch
456 * @param ecmpSPG ECMP shortest path graph
457 * @param subnets Subnets to be populated. If empty, populate all configured subnets.
458 * @return true if succeed
459 */
sanghofb7c7292015-04-13 15:15:58 -0700460 private boolean populateEcmpRoutingRules(DeviceId destSw,
Charles Chanc22cef32016-04-29 14:38:22 -0700461 EcmpShortestPathGraph ecmpSPG,
462 Set<Ip4Prefix> subnets) {
sangho80f11cb2015-04-01 13:05:26 -0700463
Srikanth Vavilapalli64505482015-04-21 13:04:13 -0700464 HashMap<Integer, HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>>> switchVia = ecmpSPG
465 .getAllLearnedSwitchesAndVia();
sangho80f11cb2015-04-01 13:05:26 -0700466 for (Integer itrIdx : switchVia.keySet()) {
Srikanth Vavilapalli64505482015-04-21 13:04:13 -0700467 HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>> swViaMap = switchVia
468 .get(itrIdx);
sangho80f11cb2015-04-01 13:05:26 -0700469 for (DeviceId targetSw : swViaMap.keySet()) {
sangho80f11cb2015-04-01 13:05:26 -0700470 Set<DeviceId> nextHops = new HashSet<>();
Saurav Das88979182015-10-19 14:37:36 -0700471 log.debug("** Iter: {} root: {} target: {}", itrIdx, destSw, targetSw);
sangho80f11cb2015-04-01 13:05:26 -0700472 for (ArrayList<DeviceId> via : swViaMap.get(targetSw)) {
473 if (via.isEmpty()) {
474 nextHops.add(destSw);
475 } else {
476 nextHops.add(via.get(0));
477 }
478 }
Charles Chanc22cef32016-04-29 14:38:22 -0700479 if (!populateEcmpRoutingRulePartial(targetSw, destSw, nextHops, subnets)) {
sangho80f11cb2015-04-01 13:05:26 -0700480 return false;
481 }
482 }
483 }
484
485 return true;
486 }
487
Charles Chanc22cef32016-04-29 14:38:22 -0700488 /**
489 * Populate ECMP rules for subnets from target to destination via nexthops.
490 *
Saurav Dase0237a32016-05-27 13:54:07 -0700491 * @param targetSw Device ID of target switch in which rules will be programmed
492 * @param destSw Device ID of final destination switch to which the rules will forward
493 * @param nextHops List of next hops via which destSw will be reached
Charles Chanc22cef32016-04-29 14:38:22 -0700494 * @param subnets Subnets to be populated. If empty, populate all configured subnets.
495 * @return true if succeed
496 */
Srikanth Vavilapalli64505482015-04-21 13:04:13 -0700497 private boolean populateEcmpRoutingRulePartial(DeviceId targetSw,
498 DeviceId destSw,
Charles Chanc22cef32016-04-29 14:38:22 -0700499 Set<DeviceId> nextHops,
500 Set<Ip4Prefix> subnets) {
sangho80f11cb2015-04-01 13:05:26 -0700501 boolean result;
502
503 if (nextHops.isEmpty()) {
504 nextHops.add(destSw);
505 }
Srikanth Vavilapalli64505482015-04-21 13:04:13 -0700506 // If both target switch and dest switch are edge routers, then set IP
sanghodf0153f2015-05-05 14:13:34 -0700507 // rule for both subnet and router IP.
Charles Chan319d1a22015-11-03 10:42:14 -0800508 boolean targetIsEdge;
509 boolean destIsEdge;
510 Ip4Address destRouterIp;
511
512 try {
513 targetIsEdge = config.isEdgeDevice(targetSw);
514 destIsEdge = config.isEdgeDevice(destSw);
515 destRouterIp = config.getRouterIp(destSw);
516 } catch (DeviceConfigNotFoundException e) {
517 log.warn(e.getMessage() + " Aborting populateEcmpRoutingRulePartial.");
518 return false;
519 }
520
521 if (targetIsEdge && destIsEdge) {
Charles Chanc22cef32016-04-29 14:38:22 -0700522 subnets = (subnets != null && !subnets.isEmpty()) ? subnets : config.getSubnets(destSw);
Saurav Das88979182015-10-19 14:37:36 -0700523 log.debug("* populateEcmpRoutingRulePartial in device {} towards {} for subnets {}",
Saurav Das4c35fc42015-11-20 15:27:53 -0800524 targetSw, destSw, subnets);
Charles Chanc22cef32016-04-29 14:38:22 -0700525 result = rulePopulator.populateIpRuleForSubnet(targetSw, subnets,
526 destSw, nextHops);
sangho80f11cb2015-04-01 13:05:26 -0700527 if (!result) {
528 return false;
529 }
530
Charles Chan319d1a22015-11-03 10:42:14 -0800531 Ip4Address routerIp = destRouterIp;
sangho9b169e32015-04-14 16:27:13 -0700532 IpPrefix routerIpPrefix = IpPrefix.valueOf(routerIp, IpPrefix.MAX_INET_MASK_LENGTH);
Saurav Das88979182015-10-19 14:37:36 -0700533 log.debug("* populateEcmpRoutingRulePartial in device {} towards {} for router IP {}",
Saurav Das4c35fc42015-11-20 15:27:53 -0800534 targetSw, destSw, routerIpPrefix);
sangho9b169e32015-04-14 16:27:13 -0700535 result = rulePopulator.populateIpRuleForRouter(targetSw, routerIpPrefix, destSw, nextHops);
sangho80f11cb2015-04-01 13:05:26 -0700536 if (!result) {
537 return false;
538 }
539
Charles Chan319d1a22015-11-03 10:42:14 -0800540 } else if (targetIsEdge) {
Saurav Das4c35fc42015-11-20 15:27:53 -0800541 // If the target switch is an edge router, then set IP rules for the router IP.
Charles Chan319d1a22015-11-03 10:42:14 -0800542 Ip4Address routerIp = destRouterIp;
sangho9b169e32015-04-14 16:27:13 -0700543 IpPrefix routerIpPrefix = IpPrefix.valueOf(routerIp, IpPrefix.MAX_INET_MASK_LENGTH);
Saurav Das88979182015-10-19 14:37:36 -0700544 log.debug("* populateEcmpRoutingRulePartial in device {} towards {} for router IP {}",
Saurav Das4c35fc42015-11-20 15:27:53 -0800545 targetSw, destSw, routerIpPrefix);
sangho9b169e32015-04-14 16:27:13 -0700546 result = rulePopulator.populateIpRuleForRouter(targetSw, routerIpPrefix, destSw, nextHops);
sangho80f11cb2015-04-01 13:05:26 -0700547 if (!result) {
548 return false;
549 }
sanghodf0153f2015-05-05 14:13:34 -0700550 }
sanghodf0153f2015-05-05 14:13:34 -0700551 // Populates MPLS rules to all routers
Saurav Das88979182015-10-19 14:37:36 -0700552 log.debug("* populateEcmpRoutingRulePartial in device{} towards {} for all MPLS rules",
Srikanth Vavilapalli7cd16712015-05-04 09:48:09 -0700553 targetSw, destSw);
sanghodf0153f2015-05-05 14:13:34 -0700554 result = rulePopulator.populateMplsRule(targetSw, destSw, nextHops);
555 if (!result) {
556 return false;
sangho80f11cb2015-04-01 13:05:26 -0700557 }
sangho80f11cb2015-04-01 13:05:26 -0700558 return true;
559 }
560
561 /**
Saurav Das9f1c42e2015-10-23 10:51:11 -0700562 * Populates filtering rules for permitting Router DstMac and VLAN.
sangho80f11cb2015-04-01 13:05:26 -0700563 *
564 * @param deviceId Switch ID to set the rules
565 */
Saurav Das9f1c42e2015-10-23 10:51:11 -0700566 public void populatePortAddressingRules(DeviceId deviceId) {
Saurav Das9f1c42e2015-10-23 10:51:11 -0700567 rulePopulator.populateRouterIpPunts(deviceId);
Saurav Das07c74602016-04-27 18:35:50 -0700568
569 // Although device is added, sometimes device store does not have the
570 // ports for this device yet. It results in missing filtering rules in the
571 // switch. We will attempt it a few times. If it still does not work,
572 // user can manually repopulate using CLI command sr-reroute-network
573 boolean success = rulePopulator.populateRouterMacVlanFilters(deviceId);
574 if (!success) {
575 executorService.schedule(new RetryFilters(deviceId), 200, TimeUnit.MILLISECONDS);
576 }
sangho80f11cb2015-04-01 13:05:26 -0700577 }
578
579 /**
Srikanth Vavilapalli64505482015-04-21 13:04:13 -0700580 * Start the flow rule population process if it was never started. The
581 * process finishes successfully when all flow rules are set and stops with
582 * ABORTED status when any groups required for flows is not set yet.
sangho80f11cb2015-04-01 13:05:26 -0700583 */
584 public void startPopulationProcess() {
HIGUCHI Yuta16d8fd52015-09-08 16:16:31 +0900585 statusLock.lock();
586 try {
Srikanth Vavilapalli64505482015-04-21 13:04:13 -0700587 if (populationStatus == Status.IDLE
Srikanth Vavilapalli7cd16712015-05-04 09:48:09 -0700588 || populationStatus == Status.SUCCEEDED
589 || populationStatus == Status.ABORTED) {
sangho80f11cb2015-04-01 13:05:26 -0700590 populationStatus = Status.STARTED;
591 populateAllRoutingRules();
Srikanth Vavilapalli7cd16712015-05-04 09:48:09 -0700592 } else {
593 log.warn("Not initiating startPopulationProcess as populationStatus is {}",
594 populationStatus);
sangho80f11cb2015-04-01 13:05:26 -0700595 }
HIGUCHI Yuta16d8fd52015-09-08 16:16:31 +0900596 } finally {
597 statusLock.unlock();
sangho80f11cb2015-04-01 13:05:26 -0700598 }
599 }
600
601 /**
602 * Resume the flow rule population process if it was aborted for any reason.
603 * Mostly the process is aborted when the groups required are not set yet.
Saurav Das88979182015-10-19 14:37:36 -0700604 * XXX is this called?
605 *
sangho80f11cb2015-04-01 13:05:26 -0700606 */
607 public void resumePopulationProcess() {
HIGUCHI Yuta16d8fd52015-09-08 16:16:31 +0900608 statusLock.lock();
609 try {
sangho80f11cb2015-04-01 13:05:26 -0700610 if (populationStatus == Status.ABORTED) {
611 populationStatus = Status.STARTED;
Srikanth Vavilapalli64505482015-04-21 13:04:13 -0700612 // TODO: we need to restart from the point aborted instead of
613 // restarting.
sangho80f11cb2015-04-01 13:05:26 -0700614 populateAllRoutingRules();
615 }
HIGUCHI Yuta16d8fd52015-09-08 16:16:31 +0900616 } finally {
617 statusLock.unlock();
sangho80f11cb2015-04-01 13:05:26 -0700618 }
619 }
Saurav Dasc3604f12016-03-23 11:22:49 -0700620
Charles Chanc22cef32016-04-29 14:38:22 -0700621 /**
622 * Populate rules of given subnet at given location.
623 *
624 * @param cp connect point of the subnet being added
625 * @param subnets subnet being added
626 * @return true if succeed
627 */
628 protected boolean populateSubnet(ConnectPoint cp, Set<Ip4Prefix> subnets) {
629 statusLock.lock();
630 try {
631 EcmpShortestPathGraph ecmpSpg = currentEcmpSpgMap.get(cp.deviceId());
632 if (ecmpSpg == null) {
633 log.warn("Fail to populating subnet {}: {}", subnets, ECMPSPG_MISSING);
634 return false;
635 }
636 return populateEcmpRoutingRules(cp.deviceId(), ecmpSpg, subnets);
637 } finally {
638 statusLock.unlock();
639 }
640 }
641
642 /**
643 * Revoke rules of given subnet at given location.
644 *
645 * @param subnets subnet being removed
646 * @return true if succeed
647 */
648 protected boolean revokeSubnet(Set<Ip4Prefix> subnets) {
649 statusLock.lock();
650 try {
651 return srManager.routingRulePopulator.revokeIpRuleForSubnet(subnets);
652 } finally {
653 statusLock.unlock();
654 }
655 }
656
657 protected void purgeEcmpGraph(DeviceId deviceId) {
Saurav Dasc3604f12016-03-23 11:22:49 -0700658 currentEcmpSpgMap.remove(deviceId);
Saurav Das52d4ed72016-03-28 19:00:18 -0700659 if (updatedEcmpSpgMap != null) {
660 updatedEcmpSpgMap.remove(deviceId);
661 }
Saurav Dasc3604f12016-03-23 11:22:49 -0700662 }
Saurav Das07c74602016-04-27 18:35:50 -0700663
Charles Chanc22cef32016-04-29 14:38:22 -0700664 private final class RetryFilters implements Runnable {
Saurav Das07c74602016-04-27 18:35:50 -0700665 int attempts = MAX_RETRY_ATTEMPTS;
666 DeviceId devId;
667
Charles Chanc22cef32016-04-29 14:38:22 -0700668 private RetryFilters(DeviceId deviceId) {
Saurav Das07c74602016-04-27 18:35:50 -0700669 devId = deviceId;
670 }
671
672 @Override
673 public void run() {
Saurav Dase0237a32016-05-27 13:54:07 -0700674 log.info("RETRY FILTER ATTEMPT# {} for dev:{}",
675 MAX_RETRY_ATTEMPTS - attempts, devId);
Saurav Das07c74602016-04-27 18:35:50 -0700676 boolean success = rulePopulator.populateRouterMacVlanFilters(devId);
677 if (!success && --attempts > 0) {
678 executorService.schedule(this, 200, TimeUnit.MILLISECONDS);
679 } else if (attempts == 0) {
680 log.error("Unable to populate MacVlan filters in dev:{}", devId);
681 }
682 }
683
684 }
685
sangho80f11cb2015-04-01 13:05:26 -0700686}