apps/segmentrouting/src/main/java/org/onosproject/segmentrouting/EcmpShortestPathGraph.java

/*
 * Copyright 2015-present Open Networking Foundation
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.onosproject.segmentrouting;

import org.onosproject.net.DefaultLink;
import org.onosproject.net.DefaultPath;
import org.onosproject.net.Device;
import org.onosproject.net.DeviceId;
import org.onosproject.net.Link;
import org.onosproject.net.Path;
import org.onosproject.net.provider.ProviderId;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import com.google.common.collect.Sets;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Set;

/**
 * This class creates breadth-first-search (BFS) tree for a given root device
 * and returns paths from the root Device to leaf Devices (target devices).
 * The paths are snapshot paths at the point of the class instantiation.
 */
public class EcmpShortestPathGraph {
    LinkedList<DeviceId> deviceQueue = new LinkedList<>();
    LinkedList<Integer> distanceQueue = new LinkedList<>();
    HashMap<DeviceId, Integer> deviceSearched = new HashMap<>();
    HashMap<DeviceId, ArrayList<Link>> upstreamLinks = new HashMap<>();
    HashMap<DeviceId, ArrayList<Path>> paths = new HashMap<>();
    HashMap<Integer, ArrayList<DeviceId>> distanceDeviceMap = new HashMap<>();
    DeviceId rootDevice;
    private SegmentRoutingManager srManager;
    private static final Logger log = LoggerFactory.getLogger(EcmpShortestPathGraph.class);

    /**
     * Constructor.
     *
     * @param rootDevice root of the BFS tree
     * @param srManager SegmentRoutingManager object
     */
    public EcmpShortestPathGraph(DeviceId rootDevice, SegmentRoutingManager srManager) {
        this.rootDevice = rootDevice;
        this.srManager = srManager;
        calcECMPShortestPathGraph();
    }

    /**
     * Calculates the BFS tree.
     */
   private void calcECMPShortestPathGraph() {
        deviceQueue.add(rootDevice);
        int currDistance = 0;
        distanceQueue.add(currDistance);
        deviceSearched.put(rootDevice, currDistance);
        while (!deviceQueue.isEmpty()) {
            DeviceId sw = deviceQueue.poll();
            Set<DeviceId> prevSw = Sets.newHashSet();
            currDistance = distanceQueue.poll();

            for (Link link : srManager.linkService.getDeviceEgressLinks(sw)) {
                if (srManager.linkHandler.avoidLink(link)) {
                    continue;
                }
                DeviceId reachedDevice = link.dst().deviceId();
                if (prevSw.contains(reachedDevice)) {
                    // Ignore LAG links between the same set of Devices
                    continue;
                } else  {
                    prevSw.add(reachedDevice);
                }

                Integer distance = deviceSearched.get(reachedDevice);
                if ((distance != null) && (distance < (currDistance + 1))) {
                    continue;
                }
                if (distance == null) {
                    // First time visiting this Device node
                    deviceQueue.add(reachedDevice);
                    distanceQueue.add(currDistance + 1);
                    deviceSearched.put(reachedDevice, currDistance + 1);

                    ArrayList<DeviceId> distanceSwArray = distanceDeviceMap
                            .get(currDistance + 1);
                    if (distanceSwArray == null) {
                        distanceSwArray = new ArrayList<>();
                        distanceSwArray.add(reachedDevice);
                        distanceDeviceMap.put(currDistance + 1, distanceSwArray);
                    } else {
                        distanceSwArray.add(reachedDevice);
                    }
                }

                ArrayList<Link> upstreamLinkArray =
                        upstreamLinks.get(reachedDevice);
                if (upstreamLinkArray == null) {
                    upstreamLinkArray = new ArrayList<>();
                    upstreamLinkArray.add(copyDefaultLink(link));
                    //upstreamLinkArray.add(link);
                    upstreamLinks.put(reachedDevice, upstreamLinkArray);
                } else {
                    // ECMP links
                    upstreamLinkArray.add(copyDefaultLink(link));
                }
            }
        }
    }

    private void getDFSPaths(DeviceId dstDeviceDeviceId, Path path, ArrayList<Path> paths) {
        DeviceId rootDeviceDeviceId = rootDevice;
        for (Link upstreamLink : upstreamLinks.get(dstDeviceDeviceId)) {
            /* Deep clone the path object */
            Path sofarPath;
            ArrayList<Link> sofarLinks = new ArrayList<>();
            if (path != null && !path.links().isEmpty()) {
                sofarLinks.addAll(path.links());
            }
            sofarLinks.add(upstreamLink);
            sofarPath = new DefaultPath(ProviderId.NONE, sofarLinks, 0);
            if (upstreamLink.src().deviceId().equals(rootDeviceDeviceId)) {
                paths.add(sofarPath);
                return;
            } else {
                getDFSPaths(upstreamLink.src().deviceId(), sofarPath, paths);
            }
        }
    }

    /**
     * Return root Device for the graph.
     *
     * @return root Device
     */
    public DeviceId getRootDevice() {
        return rootDevice;
    }

    /**
     * Return the computed ECMP paths from the root Device to a given Device in
     * the network.
     *
     * @param targetDevice the target Device
     * @return the list of ECMP Paths from the root Device to the target Device
     */
    public ArrayList<Path> getECMPPaths(DeviceId targetDevice) {
        ArrayList<Path> pathArray = paths.get(targetDevice);
        if (pathArray == null && deviceSearched.containsKey(
                targetDevice)) {
            pathArray = new ArrayList<>();
            DeviceId sw = targetDevice;
            getDFSPaths(sw, null, pathArray);
            paths.put(targetDevice, pathArray);
        }
        return pathArray;
    }

    /**
     * Return the complete info of the computed ECMP paths for each Device
     * learned in multiple iterations from the root Device.
     *
     * @return the hash table of Devices learned in multiple Dijkstra
     *         iterations and corresponding ECMP paths to it from the root
     *         Device
     */
    public HashMap<Integer, HashMap<DeviceId,
            ArrayList<Path>>> getCompleteLearnedDeviceesAndPaths() {

        HashMap<Integer, HashMap<DeviceId, ArrayList<Path>>> pathGraph = new HashMap<>();

        for (Integer itrIndx : distanceDeviceMap.keySet()) {
            HashMap<DeviceId, ArrayList<Path>> swMap = new HashMap<>();
            for (DeviceId sw : distanceDeviceMap.get(itrIndx)) {
                swMap.put(sw, getECMPPaths(sw));
            }
            pathGraph.put(itrIndx, swMap);
        }

        return pathGraph;
    }

    /**
     * Returns the complete info of the computed ECMP paths for each target device
     * learned in multiple iterations from the root Device. The computed info
     * returned is per iteration (Integer key of outer HashMap). In each
     * iteration, for the target devices reached (DeviceId key of inner HashMap),
     * the ECMP paths are detailed (2D array).
     *
     * @return the hash table of target Devices learned in multiple Dijkstra
     *         iterations and corresponding ECMP paths in terms of Devices to
     *         be traversed (via) from the root Device to the target Device
     */
    public HashMap<Integer, HashMap<DeviceId,
            ArrayList<ArrayList<DeviceId>>>> getAllLearnedSwitchesAndVia() {

        HashMap<Integer, HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>>> deviceViaMap = new HashMap<>();

        for (Integer itrIndx : distanceDeviceMap.keySet()) {
            HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>> swMap = new HashMap<>();

            for (DeviceId sw : distanceDeviceMap.get(itrIndx)) {
                ArrayList<ArrayList<DeviceId>> swViaArray = new ArrayList<>();
                for (Path path : getECMPPaths(sw)) {
                    ArrayList<DeviceId> swVia = new ArrayList<>();
                    for (Link link : path.links()) {
                        if (link.src().deviceId().equals(rootDevice)) {
                            /* No need to add the root Device again in
                             * the Via list
                             */
                            continue;
                        }
                        swVia.add(link.src().deviceId());
                    }
                    swViaArray.add(swVia);
                }
                swMap.put(sw, swViaArray);
            }
            deviceViaMap.put(itrIndx, swMap);
        }
        return deviceViaMap;
    }


    private Link copyDefaultLink(Link link) {
        DefaultLink src = (DefaultLink) link;
        DefaultLink defaultLink = DefaultLink.builder()
                .providerId(src.providerId())
                .src(src.src())
                .dst(src.dst())
                .type(src.type())
                .annotations(src.annotations())
                .build();

        return defaultLink;
    }

    @Override
    public String toString() {
        StringBuilder sBuilder = new StringBuilder();
        for (Device device: srManager.deviceService.getDevices()) {
            if (!device.id().equals(rootDevice)) {
                sBuilder.append("\r\n  Paths from " + rootDevice + " to "
                                + device.id());
                ArrayList<Path> paths = getECMPPaths(device.id());
                if (paths != null) {
                    for (Path path : paths) {
                        sBuilder.append("\r\n       == "); // equal cost paths delimiter
                        for (int i = path.links().size() - 1; i >= 0; i--) {
                            Link link = path.links().get(i);
                            sBuilder.append(" : " + link.src() + " -> " + link.dst());
                        }
                    }
                } else {
                    sBuilder.append("\r\n       == no paths");
                }
            }
        }
        return sBuilder.toString();
    }
}