aboutsummaryrefslogtreecommitdiffstats
path: root/framework/src/onos/apps/segmentrouting/src/main/java/org/onosproject/segmentrouting/ECMPShortestPathGraph.java
diff options
context:
space:
mode:
Diffstat (limited to 'framework/src/onos/apps/segmentrouting/src/main/java/org/onosproject/segmentrouting/ECMPShortestPathGraph.java')
-rw-r--r--framework/src/onos/apps/segmentrouting/src/main/java/org/onosproject/segmentrouting/ECMPShortestPathGraph.java370
1 files changed, 0 insertions, 370 deletions
diff --git a/framework/src/onos/apps/segmentrouting/src/main/java/org/onosproject/segmentrouting/ECMPShortestPathGraph.java b/framework/src/onos/apps/segmentrouting/src/main/java/org/onosproject/segmentrouting/ECMPShortestPathGraph.java
deleted file mode 100644
index e9a59bae..00000000
--- a/framework/src/onos/apps/segmentrouting/src/main/java/org/onosproject/segmentrouting/ECMPShortestPathGraph.java
+++ /dev/null
@@ -1,370 +0,0 @@
-/*
- * Copyright 2015 Open Networking Laboratory
- *
- * 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 java.util.ArrayList;
-import java.util.HashMap;
-import java.util.LinkedList;
-import java.util.List;
-
-/**
- * This class creates bandwidth constrained breadth first tree and returns paths
- * from root Device to leaf Devices which satisfies the bandwidth condition. If
- * bandwidth parameter is not specified, the normal breadth first tree will be
- * calculated. 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 linkListToAvoid link list to avoid
- * @param deviceIdListToAvoid device list to avoid
- */
- public ECMPShortestPathGraph(DeviceId rootDevice, List<String> deviceIdListToAvoid,
- List<Link> linkListToAvoid) {
- this.rootDevice = rootDevice;
- calcECMPShortestPathGraph(deviceIdListToAvoid, linkListToAvoid);
- }
-
- /**
- * 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 using any provided constraints and Intents.
- */
- private void calcECMPShortestPathGraph() {
- deviceQueue.add(rootDevice);
- int currDistance = 0;
- distanceQueue.add(currDistance);
- deviceSearched.put(rootDevice, currDistance);
- while (!deviceQueue.isEmpty()) {
- DeviceId sw = deviceQueue.poll();
- DeviceId prevSw = null;
- currDistance = distanceQueue.poll();
-
- for (Link link : srManager.linkService.getDeviceEgressLinks(sw)) {
- DeviceId reachedDevice = link.dst().deviceId();
- if ((prevSw != null)
- && (prevSw.equals(reachedDevice))) {
- /* Ignore LAG links between the same set of Devicees */
- continue;
- } else {
- prevSw = 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));
- }
- }
- }
- }
-
- /**
- * Calculates the BFS tree using any provided constraints and Intents.
- */
- private void calcECMPShortestPathGraph(List<String> deviceIdListToAvoid, List<Link> linksToAvoid) {
- deviceQueue.add(rootDevice);
- int currDistance = 0;
- distanceQueue.add(currDistance);
- deviceSearched.put(rootDevice, currDistance);
- boolean foundLinkToAvoid = false;
- while (!deviceQueue.isEmpty()) {
- DeviceId sw = deviceQueue.poll();
- DeviceId prevSw = null;
- currDistance = distanceQueue.poll();
- for (Link link : srManager.linkService.getDeviceEgressLinks(sw)) {
- for (Link linkToAvoid: linksToAvoid) {
- // TODO: equls should work
- //if (link.equals(linkToAvoid)) {
- if (linkContains(link, linksToAvoid)) {
- foundLinkToAvoid = true;
- break;
- }
- }
- if (foundLinkToAvoid) {
- foundLinkToAvoid = false;
- continue;
- }
- DeviceId reachedDevice = link.dst().deviceId();
- if (deviceIdListToAvoid.contains(reachedDevice.toString())) {
- continue;
- }
- if ((prevSw != null)
- && (prevSw.equals(reachedDevice))) {
- /* Ignore LAG links between the same set of Devicees */
- continue;
- } else {
- prevSw = 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));
- upstreamLinks.put(reachedDevice, upstreamLinkArray);
- } else {
- /* ECMP links */
- upstreamLinkArray.add(copyDefaultLink(link));
- }
- }
- }
- }
-
-
- private boolean linkContains(Link link, List<Link> links) {
-
- DeviceId srcDevice1 = link.src().deviceId();
- DeviceId dstDevice1 = link.dst().deviceId();
- long srcPort1 = link.src().port().toLong();
- long dstPort1 = link.dst().port().toLong();
-
- for (Link link2: links) {
- DeviceId srcDevice2 = link2.src().deviceId();
- DeviceId dstDevice2 = link2.dst().deviceId();
- long srcPort2 = link2.src().port().toLong();
- long dstPort2 = link2.dst().port().toLong();
-
- if (srcDevice1.toString().equals(srcDevice2.toString())
- && dstDevice1.toString().equals(dstDevice2.toString())
- && srcPort1 == srcPort2 && dstPort1 == dstPort2) {
- return true;
- }
- }
-
- return false;
- }
-
- 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;
- }
-
- /**
- * 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 in terms of Devices to
- * be traversed to it from the root 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 = new DefaultLink(src.providerId(), src.src(),
- src.dst(), src.type(), src.annotations());
-
- return defaultLink;
- }
-
- @Override
- public String toString() {
- StringBuilder sBuilder = new StringBuilder();
- for (Device device: srManager.deviceService.getDevices()) {
- if (device.id() != rootDevice) {
- sBuilder.append("Paths from" + rootDevice + " to " + device.id() + "\r\n");
- ArrayList<Path> paths = getECMPPaths(device.id());
- if (paths != null) {
- for (Path path : paths) {
- for (Link link : path.links()) {
- sBuilder.append(" : " + link.src() + " -> " + link.dst());
- }
- }
- }
- }
- }
- return sBuilder.toString();
- }
-}
-