2  * Copyright 2015 Open Networking Laboratory
 
   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
 
   8  *     http://www.apache.org/licenses/LICENSE-2.0
 
  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.
 
  16 package org.onosproject.segmentrouting.grouphandler;
 
  18 import static com.google.common.base.Preconditions.checkNotNull;
 
  19 import static org.slf4j.LoggerFactory.getLogger;
 
  22 import java.util.ArrayList;
 
  23 import java.util.Collections;
 
  24 import java.util.HashMap;
 
  25 import java.util.HashSet;
 
  26 import java.util.List;
 
  29 import java.util.stream.Collectors;
 
  31 import org.onlab.packet.Ip4Prefix;
 
  32 import org.onlab.packet.IpPrefix;
 
  33 import org.onlab.packet.MacAddress;
 
  34 import org.onlab.packet.MplsLabel;
 
  35 import org.onlab.util.KryoNamespace;
 
  36 import org.onosproject.core.ApplicationId;
 
  37 import org.onosproject.net.DeviceId;
 
  38 import org.onosproject.net.Link;
 
  39 import org.onosproject.net.PortNumber;
 
  40 import org.onosproject.net.flow.DefaultTrafficTreatment;
 
  41 import org.onosproject.net.flow.TrafficTreatment;
 
  42 import org.onosproject.net.flowobjective.DefaultNextObjective;
 
  43 import org.onosproject.net.flowobjective.FlowObjectiveService;
 
  44 import org.onosproject.net.flowobjective.NextObjective;
 
  45 import org.onosproject.net.flowobjective.Objective;
 
  46 import org.onosproject.net.flowobjective.ObjectiveContext;
 
  47 import org.onosproject.net.flowobjective.ObjectiveError;
 
  48 import org.onosproject.net.group.DefaultGroupKey;
 
  49 import org.onosproject.net.group.GroupKey;
 
  50 import org.onosproject.net.link.LinkService;
 
  51 import org.onosproject.segmentrouting.config.DeviceConfigNotFoundException;
 
  52 import org.onosproject.segmentrouting.config.DeviceProperties;
 
  53 import org.onosproject.store.service.EventuallyConsistentMap;
 
  54 import org.slf4j.Logger;
 
  57  * Default ECMP group handler creation module. This component creates a set of
 
  58  * ECMP groups for every neighbor that this device is connected to based on
 
  59  * whether the current device is an edge device or a transit device.
 
  61 public class DefaultGroupHandler {
 
  62     protected static final Logger log = getLogger(DefaultGroupHandler.class);
 
  64     protected final DeviceId deviceId;
 
  65     protected final ApplicationId appId;
 
  66     protected final DeviceProperties deviceConfig;
 
  67     protected final List<Integer> allSegmentIds;
 
  68     protected int nodeSegmentId = -1;
 
  69     protected boolean isEdgeRouter = false;
 
  70     protected MacAddress nodeMacAddr = null;
 
  71     protected LinkService linkService;
 
  72     protected FlowObjectiveService flowObjectiveService;
 
  74     protected HashMap<DeviceId, Set<PortNumber>> devicePortMap = new HashMap<>();
 
  75     protected HashMap<PortNumber, DeviceId> portDeviceMap = new HashMap<>();
 
  76     //protected HashMap<NeighborSet, Integer> deviceNextObjectiveIds =
 
  77     //        new HashMap<NeighborSet, Integer>();
 
  78     protected EventuallyConsistentMap<
 
  79         NeighborSetNextObjectiveStoreKey, Integer> nsNextObjStore = null;
 
  80     protected EventuallyConsistentMap<
 
  81             SubnetNextObjectiveStoreKey, Integer> subnetNextObjStore = null;
 
  83     protected KryoNamespace.Builder kryo = new KryoNamespace.Builder()
 
  84             .register(URI.class).register(HashSet.class)
 
  85             .register(DeviceId.class).register(PortNumber.class)
 
  86             .register(NeighborSet.class).register(PolicyGroupIdentifier.class)
 
  87             .register(PolicyGroupParams.class)
 
  88             .register(GroupBucketIdentifier.class)
 
  89             .register(GroupBucketIdentifier.BucketOutputType.class);
 
  91     protected DefaultGroupHandler(DeviceId deviceId, ApplicationId appId,
 
  92                                   DeviceProperties config,
 
  93                                   LinkService linkService,
 
  94                                   FlowObjectiveService flowObjService,
 
  95                                   EventuallyConsistentMap<
 
  96                                           NeighborSetNextObjectiveStoreKey,
 
  97                                           Integer> nsNextObjStore,
 
  98                                   EventuallyConsistentMap<SubnetNextObjectiveStoreKey,
 
  99                                           Integer> subnetNextObjStore) {
 
 100         this.deviceId = checkNotNull(deviceId);
 
 101         this.appId = checkNotNull(appId);
 
 102         this.deviceConfig = checkNotNull(config);
 
 103         this.linkService = checkNotNull(linkService);
 
 104         this.allSegmentIds = checkNotNull(config.getAllDeviceSegmentIds());
 
 106             this.nodeSegmentId = config.getSegmentId(deviceId);
 
 107             this.isEdgeRouter = config.isEdgeDevice(deviceId);
 
 108             this.nodeMacAddr = checkNotNull(config.getDeviceMac(deviceId));
 
 109         } catch (DeviceConfigNotFoundException e) {
 
 110             log.warn(e.getMessage()
 
 111                     + " Skipping value assignment in DefaultGroupHandler");
 
 113         this.flowObjectiveService = flowObjService;
 
 114         this.nsNextObjStore = nsNextObjStore;
 
 115         this.subnetNextObjStore = subnetNextObjStore;
 
 117         populateNeighborMaps();
 
 121      * Creates a group handler object based on the type of device. If device is
 
 122      * of edge type it returns edge group handler, else it returns transit group
 
 125      * @param deviceId device identifier
 
 126      * @param appId application identifier
 
 127      * @param config interface to retrieve the device properties
 
 128      * @param linkService link service object
 
 129      * @param flowObjService flow objective service object
 
 130      * @param nsNextObjStore NeighborSet next objective store map
 
 131      * @param subnetNextObjStore subnet next objective store map
 
 132      * @throws DeviceConfigNotFoundException if the device configuration is not found
 
 133      * @return default group handler type
 
 135     public static DefaultGroupHandler createGroupHandler(DeviceId deviceId,
 
 137                                                          DeviceProperties config,
 
 138                                                          LinkService linkService,
 
 139                                                          FlowObjectiveService flowObjService,
 
 140                                                          EventuallyConsistentMap<
 
 141                                                                  NeighborSetNextObjectiveStoreKey,
 
 142                                                                  Integer> nsNextObjStore,
 
 143                                                          EventuallyConsistentMap<SubnetNextObjectiveStoreKey,
 
 144                                                                  Integer> subnetNextObjStore)
 
 145                                                          throws DeviceConfigNotFoundException {
 
 146         // handle possible exception in the caller
 
 147         if (config.isEdgeDevice(deviceId)) {
 
 148             return new DefaultEdgeGroupHandler(deviceId, appId, config,
 
 154             return new DefaultTransitGroupHandler(deviceId, appId, config,
 
 163      * Creates the auto created groups for this device based on the current
 
 164      * snapshot of the topology.
 
 166     // Empty implementations to be overridden by derived classes
 
 167     public void createGroups() {
 
 171      * Performs group creation or update procedures when a new link is
 
 172      * discovered on this device.
 
 174      * @param newLink new neighbor link
 
 176     public void linkUp(Link newLink) {
 
 178         if (newLink.type() != Link.Type.DIRECT) {
 
 179             log.warn("linkUp: unknown link type");
 
 183         if (!newLink.src().deviceId().equals(deviceId)) {
 
 184             log.warn("linkUp: deviceId{} doesn't match with link src{}",
 
 185                      deviceId, newLink.src().deviceId());
 
 191             dstMac = deviceConfig.getDeviceMac(newLink.dst().deviceId());
 
 192         } catch (DeviceConfigNotFoundException e) {
 
 193             log.warn(e.getMessage() + " Aborting linkUp.");
 
 197         log.debug("Device {} linkUp at local port {} to neighbor {}", deviceId,
 
 198                   newLink.src().port(), newLink.dst().deviceId());
 
 199         addNeighborAtPort(newLink.dst().deviceId(),
 
 200                           newLink.src().port());
 
 201         /*if (devicePortMap.get(newLink.dst().deviceId()) == null) {
 
 203             newNeighbor(newLink);
 
 206             newPortToExistingNeighbor(newLink);
 
 208         Set<NeighborSet> nsSet = nsNextObjStore.keySet()
 
 210                 .filter((nsStoreEntry) -> (nsStoreEntry.deviceId().equals(deviceId)))
 
 211                 .map((nsStoreEntry) -> (nsStoreEntry.neighborSet()))
 
 212                 .filter((ns) -> (ns.getDeviceIds()
 
 213                         .contains(newLink.dst().deviceId())))
 
 214                 .collect(Collectors.toSet());
 
 215         log.trace("linkUp: nsNextObjStore contents for device {}:",
 
 218         for (NeighborSet ns : nsSet) {
 
 219             // Create the new bucket to be updated
 
 220             TrafficTreatment.Builder tBuilder =
 
 221                     DefaultTrafficTreatment.builder();
 
 222             tBuilder.setOutput(newLink.src().port())
 
 224                     .setEthSrc(nodeMacAddr);
 
 225             if (ns.getEdgeLabel() != NeighborSet.NO_EDGE_LABEL) {
 
 228                                  mplsLabel(ns.getEdgeLabel()));
 
 231             Integer nextId = nsNextObjStore.
 
 232                     get(new NeighborSetNextObjectiveStoreKey(deviceId, ns));
 
 233             if (nextId != null) {
 
 234                 NextObjective.Builder nextObjBuilder = DefaultNextObjective
 
 235                         .builder().withId(nextId)
 
 236                         .withType(NextObjective.Type.HASHED).fromApp(appId);
 
 238                 nextObjBuilder.addTreatment(tBuilder.build());
 
 240                 log.debug("linkUp in device {}: Adding Bucket "
 
 241                         + "with Port {} to next object id {}",
 
 243                         newLink.src().port(),
 
 245                 NextObjective nextObjective = nextObjBuilder.
 
 246                         add(new SRNextObjectiveContext(deviceId));
 
 247                 flowObjectiveService.next(deviceId, nextObjective);
 
 253      * Performs group recovery procedures when a port goes down on this device.
 
 255      * @param port port number that has gone down
 
 257     public void portDown(PortNumber port) {
 
 258         if (portDeviceMap.get(port) == null) {
 
 259             log.warn("portDown: unknown port");
 
 265             dstMac = deviceConfig.getDeviceMac(portDeviceMap.get(port));
 
 266         } catch (DeviceConfigNotFoundException e) {
 
 267             log.warn(e.getMessage() + " Aborting portDown.");
 
 271         log.debug("Device {} portDown {} to neighbor {}", deviceId, port,
 
 272                   portDeviceMap.get(port));
 
 273         /*Set<NeighborSet> nsSet = computeImpactedNeighborsetForPortEvent(portDeviceMap
 
 277         Set<NeighborSet> nsSet = nsNextObjStore.keySet()
 
 279                 .filter((nsStoreEntry) -> (nsStoreEntry.deviceId().equals(deviceId)))
 
 280                 .map((nsStoreEntry) -> (nsStoreEntry.neighborSet()))
 
 281                 .filter((ns) -> (ns.getDeviceIds()
 
 282                         .contains(portDeviceMap.get(port))))
 
 283                 .collect(Collectors.toSet());
 
 284         log.trace("portDown: nsNextObjStore contents for device {}:",
 
 287         for (NeighborSet ns : nsSet) {
 
 288             // Create the bucket to be removed
 
 289             TrafficTreatment.Builder tBuilder = DefaultTrafficTreatment
 
 291             tBuilder.setOutput(port)
 
 293                     .setEthSrc(nodeMacAddr);
 
 294             if (ns.getEdgeLabel() != NeighborSet.NO_EDGE_LABEL) {
 
 295                 tBuilder.pushMpls().setMpls(MplsLabel.mplsLabel(ns
 
 299             Integer nextId = nsNextObjStore.
 
 300                     get(new NeighborSetNextObjectiveStoreKey(deviceId, ns));
 
 301             if (nextId != null) {
 
 302                 NextObjective.Builder nextObjBuilder = DefaultNextObjective
 
 303                         .builder().withType(NextObjective.Type.SIMPLE).withId(nextId).fromApp(appId);
 
 305                 nextObjBuilder.addTreatment(tBuilder.build());
 
 307                 log.debug("portDown in device {}: Removing Bucket "
 
 308                         + "with Port {} to next object id {}",
 
 312                 NextObjective nextObjective = nextObjBuilder.
 
 313                         remove(new SRNextObjectiveContext(deviceId));
 
 315                 flowObjectiveService.next(deviceId, nextObjective);
 
 320         devicePortMap.get(portDeviceMap.get(port)).remove(port);
 
 321         portDeviceMap.remove(port);
 
 325      * Returns the next objective associated with the neighborset.
 
 326      * If there is no next objective for this neighborset, this API
 
 327      * would create a next objective and return.
 
 329      * @param ns neighborset
 
 330      * @return int if found or -1
 
 332     public int getNextObjectiveId(NeighborSet ns) {
 
 333         Integer nextId = nsNextObjStore.
 
 334                 get(new NeighborSetNextObjectiveStoreKey(deviceId, ns));
 
 335         if (nextId == null) {
 
 336             log.trace("getNextObjectiveId in device{}: Next objective id "
 
 337                     + "not found for {} and creating", deviceId, ns);
 
 338             log.trace("getNextObjectiveId: nsNextObjStore contents for device {}: {}",
 
 340                       nsNextObjStore.entrySet()
 
 342                       .filter((nsStoreEntry) ->
 
 343                       (nsStoreEntry.getKey().deviceId().equals(deviceId)))
 
 344                       .collect(Collectors.toList()));
 
 345             createGroupsFromNeighborsets(Collections.singleton(ns));
 
 346             nextId = nsNextObjStore.
 
 347                     get(new NeighborSetNextObjectiveStoreKey(deviceId, ns));
 
 348             if (nextId == null) {
 
 349                 log.warn("getNextObjectiveId: unable to create next objective");
 
 352                 log.debug("getNextObjectiveId in device{}: Next objective id {} "
 
 353                     + "created for {}", deviceId, nextId, ns);
 
 356             log.trace("getNextObjectiveId in device{}: Next objective id {} "
 
 357                     + "found for {}", deviceId, nextId, ns);
 
 363      * Returns the next objective associated with the subnet.
 
 364      * If there is no next objective for this subnet, this API
 
 365      * would create a next objective and return.
 
 367      * @param prefix subnet information
 
 368      * @return int if found or -1
 
 370     public int getSubnetNextObjectiveId(IpPrefix prefix) {
 
 371         Integer nextId = subnetNextObjStore.
 
 372                 get(new SubnetNextObjectiveStoreKey(deviceId, prefix));
 
 374         return (nextId != null) ? nextId : -1;
 
 378      * Checks if the next objective ID (group) for the neighbor set exists or not.
 
 380      * @param ns neighbor set to check
 
 381      * @return true if it exists, false otherwise
 
 383     public boolean hasNextObjectiveId(NeighborSet ns) {
 
 384         Integer nextId = nsNextObjStore.
 
 385                 get(new NeighborSetNextObjectiveStoreKey(deviceId, ns));
 
 386         if (nextId == null) {
 
 393     // Empty implementation
 
 394     protected void newNeighbor(Link newLink) {
 
 397     // Empty implementation
 
 398     protected void newPortToExistingNeighbor(Link newLink) {
 
 401     // Empty implementation
 
 402     protected Set<NeighborSet>
 
 403         computeImpactedNeighborsetForPortEvent(DeviceId impactedNeighbor,
 
 404                                                Set<DeviceId> updatedNeighbors) {
 
 408     private void populateNeighborMaps() {
 
 409         Set<Link> outgoingLinks = linkService.getDeviceEgressLinks(deviceId);
 
 410         for (Link link : outgoingLinks) {
 
 411             if (link.type() != Link.Type.DIRECT) {
 
 414             addNeighborAtPort(link.dst().deviceId(), link.src().port());
 
 418     protected void addNeighborAtPort(DeviceId neighborId,
 
 419                                      PortNumber portToNeighbor) {
 
 420         // Update DeviceToPort database
 
 421         log.debug("Device {} addNeighborAtPort: neighbor {} at port {}",
 
 422                   deviceId, neighborId, portToNeighbor);
 
 423         if (devicePortMap.get(neighborId) != null) {
 
 424             devicePortMap.get(neighborId).add(portToNeighbor);
 
 426             Set<PortNumber> ports = new HashSet<>();
 
 427             ports.add(portToNeighbor);
 
 428             devicePortMap.put(neighborId, ports);
 
 431         // Update portToDevice database
 
 432         if (portDeviceMap.get(portToNeighbor) == null) {
 
 433             portDeviceMap.put(portToNeighbor, neighborId);
 
 437     protected Set<Set<DeviceId>> getPowerSetOfNeighbors(Set<DeviceId> neighbors) {
 
 438         List<DeviceId> list = new ArrayList<>(neighbors);
 
 439         Set<Set<DeviceId>> sets = new HashSet<>();
 
 440         // get the number of elements in the neighbors
 
 441         int elements = list.size();
 
 442         // the number of members of a power set is 2^n
 
 443         // including the empty set
 
 444         int powerElements = (1 << elements);
 
 446         // run a binary counter for the number of power elements
 
 447         // NOTE: Exclude empty set
 
 448         for (long i = 1; i < powerElements; i++) {
 
 449             Set<DeviceId> neighborSubSet = new HashSet<>();
 
 450             for (int j = 0; j < elements; j++) {
 
 451                 if ((i >> j) % 2 == 1) {
 
 452                     neighborSubSet.add(list.get(j));
 
 455             sets.add(neighborSubSet);
 
 460     private boolean isSegmentIdSameAsNodeSegmentId(DeviceId deviceId, int sId) {
 
 463             segmentId = deviceConfig.getSegmentId(deviceId);
 
 464         } catch (DeviceConfigNotFoundException e) {
 
 465             log.warn(e.getMessage() + " Aborting isSegmentIdSameAsNodeSegmentId.");
 
 469         return segmentId == sId;
 
 472     protected List<Integer> getSegmentIdsTobePairedWithNeighborSet(Set<DeviceId> neighbors) {
 
 474         List<Integer> nsSegmentIds = new ArrayList<>();
 
 476         // Always pair up with no edge label
 
 477         // If (neighbors.size() == 1) {
 
 478         nsSegmentIds.add(-1);
 
 481         // Filter out SegmentIds matching with the
 
 482         // nodes in the combo
 
 483         for (Integer sId : allSegmentIds) {
 
 484             if (sId.equals(nodeSegmentId)) {
 
 487             boolean filterOut = false;
 
 488             // Check if the edge label being set is of
 
 489             // any node in the Neighbor set
 
 490             for (DeviceId deviceId : neighbors) {
 
 491                 if (isSegmentIdSameAsNodeSegmentId(deviceId, sId)) {
 
 497                 nsSegmentIds.add(sId);
 
 504      * Creates Groups from a set of NeighborSet given.
 
 506      * @param nsSet a set of NeighborSet
 
 508     public void createGroupsFromNeighborsets(Set<NeighborSet> nsSet) {
 
 509         for (NeighborSet ns : nsSet) {
 
 510             int nextId = flowObjectiveService.allocateNextId();
 
 511             NextObjective.Builder nextObjBuilder = DefaultNextObjective
 
 512                     .builder().withId(nextId)
 
 513                     .withType(NextObjective.Type.HASHED).fromApp(appId);
 
 514             for (DeviceId d : ns.getDeviceIds()) {
 
 515                 if (devicePortMap.get(d) == null) {
 
 516                     log.warn("Device {} is not in the port map yet", d);
 
 518                 } else if (devicePortMap.get(d).size() == 0) {
 
 519                     log.warn("There are no ports for "
 
 520                             + "the Device {} in the port map yet", d);
 
 524                 MacAddress deviceMac;
 
 526                     deviceMac = deviceConfig.getDeviceMac(d);
 
 527                 } catch (DeviceConfigNotFoundException e) {
 
 528                     log.warn(e.getMessage() + " Aborting createGroupsFromNeighborsets.");
 
 532                 for (PortNumber sp : devicePortMap.get(d)) {
 
 533                     TrafficTreatment.Builder tBuilder = DefaultTrafficTreatment
 
 535                     tBuilder.setOutput(sp)
 
 536                             .setEthDst(deviceMac)
 
 537                             .setEthSrc(nodeMacAddr);
 
 538                     if (ns.getEdgeLabel() != NeighborSet.NO_EDGE_LABEL) {
 
 539                         tBuilder.pushMpls().setMpls(MplsLabel.mplsLabel(ns
 
 542                     nextObjBuilder.addTreatment(tBuilder.build());
 
 546             NextObjective nextObj = nextObjBuilder.
 
 547                     add(new SRNextObjectiveContext(deviceId));
 
 548             flowObjectiveService.next(deviceId, nextObj);
 
 549             log.debug("createGroupsFromNeighborsets: Submited "
 
 550                             + "next objective {} in device {}",
 
 552             nsNextObjStore.put(new NeighborSetNextObjectiveStoreKey(deviceId, ns),
 
 557     public void createGroupsFromSubnetConfig() {
 
 558         Map<Ip4Prefix, List<PortNumber>> subnetPortMap =
 
 559                 this.deviceConfig.getSubnetPortsMap(this.deviceId);
 
 561         // Construct a broadcast group for each subnet
 
 562         subnetPortMap.forEach((subnet, ports) -> {
 
 563             SubnetNextObjectiveStoreKey key =
 
 564                     new SubnetNextObjectiveStoreKey(deviceId, subnet);
 
 566             if (subnetNextObjStore.containsKey(key)) {
 
 567                 log.debug("Broadcast group for device {} and subnet {} exists",
 
 572             int nextId = flowObjectiveService.allocateNextId();
 
 574             NextObjective.Builder nextObjBuilder = DefaultNextObjective
 
 575                     .builder().withId(nextId)
 
 576                     .withType(NextObjective.Type.BROADCAST).fromApp(appId);
 
 578             ports.forEach(port -> {
 
 579                 TrafficTreatment.Builder tBuilder = DefaultTrafficTreatment.builder();
 
 581                 tBuilder.setOutput(port);
 
 582                 nextObjBuilder.addTreatment(tBuilder.build());
 
 585             NextObjective nextObj = nextObjBuilder.add();
 
 586             flowObjectiveService.next(deviceId, nextObj);
 
 587             log.debug("createGroupFromSubnetConfig: Submited "
 
 588                               + "next objective {} in device {}",
 
 591             subnetNextObjStore.put(key, nextId);
 
 595     public GroupKey getGroupKey(Object obj) {
 
 596         return new DefaultGroupKey(kryo.build().serialize(obj));
 
 600      * Removes groups for the next objective ID given.
 
 602      * @param objectiveId next objective ID to remove
 
 603      * @return true if succeeds, false otherwise
 
 605     public boolean removeGroup(int objectiveId) {
 
 607         if (nsNextObjStore.containsValue(objectiveId)) {
 
 608             NextObjective.Builder nextObjBuilder = DefaultNextObjective
 
 609                     .builder().withId(objectiveId)
 
 610                     .withType(NextObjective.Type.HASHED).fromApp(appId);
 
 611             NextObjective nextObjective = nextObjBuilder.
 
 612                     remove(new SRNextObjectiveContext(deviceId));
 
 613             flowObjectiveService.next(deviceId, nextObjective);
 
 615             for (Map.Entry<NeighborSetNextObjectiveStoreKey, Integer> entry: nsNextObjStore.entrySet()) {
 
 616                 if (entry.getValue().equals(objectiveId)) {
 
 617                     nsNextObjStore.remove(entry.getKey());
 
 627     protected static class SRNextObjectiveContext implements ObjectiveContext {
 
 628         final DeviceId deviceId;
 
 630         SRNextObjectiveContext(DeviceId deviceId) {
 
 631             this.deviceId = deviceId;
 
 634         public void onSuccess(Objective objective) {
 
 635             log.debug("Next objective operation successful in device {}",
 
 640         public void onError(Objective objective, ObjectiveError error) {
 
 641             log.warn("Next objective {} operation failed with error: {} in device {}",
 
 642                      objective, error, deviceId);