SimpleGetShortestPath.java

Go to the documentation of this file.

/* Copyright 2018 Telstra Open Source
 *
 *   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.openkilda.pce.algo;

import org.openkilda.messaging.model.SwitchId;
import org.openkilda.pce.model.AvailableNetwork;
import org.openkilda.pce.model.SimpleIsl;
import org.openkilda.pce.model.SimpleSwitch;

import com.google.common.collect.Lists;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

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

public class SimpleGetShortestPath {

    private static final Logger logger = LoggerFactory.getLogger(SimpleGetShortestPath.class);

    private AvailableNetwork network;
    private SimpleSwitch start;
    private SimpleSwitch end;
    private int allowedDepth;
    private int bestCost = Integer.MAX_VALUE;
    private SearchNode bestPath = null;

    public SimpleGetShortestPath(AvailableNetwork network, SwitchId srcDpid, SwitchId dstDpid, int allowedDepth) {
        this.network = network;
        this.start = network.getSwitches().get(srcDpid);
        this.end = network.getSwitches().get(dstDpid);
        this.allowedDepth = allowedDepth;
        if (this.start == null) {
            logger.warn("SOURCE node doesn't exist. It isn't in the AVAILABLE network: {}", srcDpid);
        }
        if (this.end == null) {
            logger.warn("DESTINATION node doesn't exist. It isn't in the AVAILABLE network: {}", dstDpid);
        }
    }


    public LinkedList<SimpleIsl> getPath() {
        HashMap<SimpleSwitch, SearchNode> toVisitLookup = new HashMap<>();  // constant lookup
        LinkedList<SearchNode> toVisit = new LinkedList<>();                // working list
        HashMap<SimpleSwitch, SearchNode> visited = new HashMap<>();

        if (start != null && end != null) {
            toVisitLookup.put(start, new SearchNode(allowedDepth, 0, start));
            toVisit.add(toVisitLookup.get(start));
        }

        while (toVisit.size() > 0) {
            SearchNode current = toVisit.pop();

            // Determine if this node is the destination node.
            if (current.dstSw.equals(end)) {
                // We found the destination
                if (current.parentCost < bestCost) {
                    // We found a best path. If we don't get here, then the entire graph will be
                    // searched until we run out of nodes or the depth is reached.
                    bestCost = current.parentCost;
                    bestPath = current;
                }
                // We found dest, no need to keep processing
                continue;
            }

            // Otherwise, if we've been here before, see if this path is better
            SearchNode prior = visited.get(current.dstSw);
            if (prior != null) {
                // We've already visited this one .. keep going only if this is cheaper
                if (current.parentCost >= prior.parentCost) {
                    continue;
                }
            }
            // Either this is the first time, or this is cheaper .. either way, this node should
            // be the one in the visited list
            visited.put(current.dstSw, current);

            // Stop processing entirely if we've gone too far, or over bestCost
            if (current.allowedDepth < 0 || current.parentCost > bestCost) {
                continue;
            }

            // At this stage .. haven't found END, haven't gone too deep, and we are not over cost.
            // So, add the outbound isls.
            for (Set<SimpleIsl> isls: current.dstSw.outbound.values()) {
                for (SimpleIsl isl : isls) {
                    toVisit.add(current.addNode(isl));
                }
            }
        }

        return (bestPath != null) ? bestPath.parentPath : new LinkedList<>();
    }


    public LinkedList<SimpleIsl> getPath(List<SimpleIsl> hint) {
        // First, see if the first and last nodes match our start and end, or whether the list
        // needs to be reversed
        if (hint != null && hint.size() > 0) {
            SimpleSwitch from = network.getSimpleSwitch(hint.get(0).getSrcDpid());
            SimpleSwitch to = network.getSimpleSwitch(hint.get(hint.size() - 1).getDstDpid());
            if (start.equals(to) && end.equals(from)) {
                logger.trace("getPath w/ Hint: Reversing the path from {}->{} to {}->{}", from, to, to, from);
                // looks like hint wasn't reversed .. revers the order, and swap src/dst.
                hint = swapSrcDst(Lists.reverse(hint));
                // re-run from and to .. it should now match.
                from = network.getSimpleSwitch(hint.get(0).getSrcDpid());
                to = network.getSimpleSwitch(hint.get(hint.size() - 1).getDstDpid());
            }

            // If the start/end equals from/to, then confirm the path and see if we can use it.
            if (start.equals(from) && end.equals(to)) {
                logger.trace("getPath w/ Hint: hint matches start/ed {}->{}", from, to);
                // need to validate that the path exists .. and if so .. set bestCost and bestPath
                SearchNode best = confirmIsls(hint);
                if (best != null) {
                    logger.debug("getPath w/ Hint: the hint path EXISTS for {}->{}", from, to);
                    bestCost = best.parentCost;
                    bestPath = best;
                } else {
                    logger.info("getPath w/ Hint: the hint path DOES NOT EXIST for {}->{}, will find new path",
                            from, to);
                }
            }
        }
        return getPath();
    }

    private List<SimpleIsl> swapSrcDst(List<SimpleIsl> originalIsls) {
        List<SimpleIsl> mirrorIsls = new ArrayList<>();
        for (SimpleIsl original : originalIsls) {
            // this swaps the src and dst fields
            mirrorIsls.add(new SimpleIsl(original.getDstDpid(), original.getSrcDpid(), original.getDstPort(),
                    original.getSrcPort(), original.getCost(), original.getLatency()));
        }
        return mirrorIsls;
    }

    private static final Set<SimpleIsl> safeSet(Set<SimpleIsl> other) {
        return other == null ? Collections.EMPTY_SET : other;
    }

    private SearchNode confirmIsls(List<SimpleIsl> srcIsls) {
        int totalCost = 0;
        LinkedList<SimpleIsl> confirmedIsls = new LinkedList<>();

        boolean validPath = true;
        for (SimpleIsl i : srcIsls) {
            boolean foundThisOne = false;
            SimpleSwitch srcSwitch =  network.getSimpleSwitch(i.getSrcDpid());
            if (srcSwitch != null) {
                Set<SimpleIsl> pathsToDst = safeSet(srcSwitch.outbound.get(i.getDstDpid()));
                if (pathsToDst.equals(Collections.EMPTY_SET)) {
                    logger.debug("No ISLS from {} to {}", i.getSrcDpid(), i.getDstDpid());
                }
                for (SimpleIsl orig : pathsToDst) {
                    if (i.equals(orig)) {
                        foundThisOne = true;
                        confirmedIsls.add(orig);
                        totalCost += orig.getCost();
                        break; // stop looking, we found the isl
                    }
                }
            } else {
                logger.warn("confirmIsls: Found a null switch during getPath(hint): {}", i.getSrcDpid());
            }
            if (!foundThisOne) {
                validPath = false;
                break; // found an isl that doesn't exist, stop looking for others
            }
        }

        if (validPath) {
            return new SearchNode(this.allowedDepth - confirmedIsls.size(), totalCost,
                    network.getSimpleSwitch(confirmedIsls.peekLast().getDstDpid()), confirmedIsls);
        }
        return null;
    }


    private class SearchNode implements Cloneable {
        SimpleSwitch dstSw;
        int allowedDepth;
        int parentCost;
        LinkedList<SimpleIsl> parentPath;
        // NB: We could consider tracking the child path as well .. to facilitate
        //     re-calc if we find a better parentPath.

        public SearchNode(int allowedDepth, int parentCost, SimpleSwitch dstSw) {
            this(allowedDepth, parentCost, dstSw, new LinkedList<SimpleIsl>());
        }

        public SearchNode(int allowedDepth, int parentCost, SimpleSwitch dstSw, LinkedList<SimpleIsl> parentPath) {
            this.dstSw = dstSw;
            this.allowedDepth = allowedDepth;
            this.parentCost = parentCost;
            this.parentPath = parentPath;
        }

        public SearchNode addNode(SimpleIsl nextIsl) {
            SearchNode newNode = this.clone();
            newNode.parentPath.add(nextIsl);
            newNode.dstSw = network.getSimpleSwitch(nextIsl.getDstDpid());
            newNode.allowedDepth--;
            newNode.parentCost += nextIsl.getCost();
            return newNode;
        }

        @Override
        @SuppressWarnings("unchecked")
        protected SearchNode clone() {
            return new SearchNode(allowedDepth, parentCost, dstSw, (LinkedList<SimpleIsl>) parentPath.clone());
        }
    }

    private void createSearchNode() {

    }
}