gerrit.opnfv Code Review - onosfw.git/blob

   1 /*
   2  * Copyright 2015 Open Networking Laboratory
   3  *
   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  */
  16 package org.onosproject.segmentrouting;
  17
  18 import org.onosproject.net.DefaultLink;
  19 import org.onosproject.net.DefaultPath;
  20 import org.onosproject.net.Device;
  21 import org.onosproject.net.DeviceId;
  22 import org.onosproject.net.Link;
  23 import org.onosproject.net.Path;
  24 import org.onosproject.net.provider.ProviderId;
  25 import org.slf4j.Logger;
  26 import org.slf4j.LoggerFactory;
  27 import java.util.ArrayList;
  28 import java.util.HashMap;
  29 import java.util.LinkedList;
  30 import java.util.List;
  31
  32 /**
  33  * This class creates bandwidth constrained breadth first tree and returns paths
  34  * from root Device to leaf Devicees which satisfies the bandwidth condition. If
  35  * bandwidth parameter is not specified, the normal breadth first tree will be
  36  * calculated. The paths are snapshot paths at the point of the class
  37  * instantiation.
  38  */
  39 public class ECMPShortestPathGraph {
  40     LinkedList<DeviceId> deviceQueue = new LinkedList<>();
  41     LinkedList<Integer> distanceQueue = new LinkedList<>();
  42     HashMap<DeviceId, Integer> deviceSearched = new HashMap<>();
  43     HashMap<DeviceId, ArrayList<Link>> upstreamLinks = new HashMap<>();
  44     HashMap<DeviceId, ArrayList<Path>> paths = new HashMap<>();
  45     HashMap<Integer, ArrayList<DeviceId>> distanceDeviceMap = new HashMap<>();
  46     DeviceId rootDevice;
  47     private SegmentRoutingManager srManager;
  48     private static final Logger log = LoggerFactory
  49             .getLogger(ECMPShortestPathGraph.class);
  50
  51     /**
  52      * Constructor.
  53      *
  54      * @param rootDevice root of the BFS tree
  55      * @param linkListToAvoid link list to avoid
  56      * @param deviceIdListToAvoid device list to avoid
  57      */
  58     public ECMPShortestPathGraph(DeviceId rootDevice, List<String> deviceIdListToAvoid,
  59                                  List<Link> linkListToAvoid) {
  60         this.rootDevice = rootDevice;
  61         calcECMPShortestPathGraph(deviceIdListToAvoid, linkListToAvoid);
  62     }
  63
  64     /**
  65      * Constructor.
  66      *
  67      * @param rootDevice root of the BFS tree
  68      * @param srManager SegmentRoutingManager object
  69      */
  70     public ECMPShortestPathGraph(DeviceId rootDevice, SegmentRoutingManager srManager) {
  71         this.rootDevice = rootDevice;
  72         this.srManager = srManager;
  73         calcECMPShortestPathGraph();
  74     }
  75
  76     /**
  77      * Calculates the BFS tree using any provided constraints and Intents.
  78      */
  79     private void calcECMPShortestPathGraph() {
  80         deviceQueue.add(rootDevice);
  81         int currDistance = 0;
  82         distanceQueue.add(currDistance);
  83         deviceSearched.put(rootDevice, currDistance);
  84         while (!deviceQueue.isEmpty()) {
  85             DeviceId sw = deviceQueue.poll();
  86             DeviceId prevSw = null;
  87             currDistance = distanceQueue.poll();
  88
  89             for (Link link : srManager.linkService.getDeviceEgressLinks(sw)) {
  90                 DeviceId reachedDevice = link.dst().deviceId();
  91                 if ((prevSw != null)
  92                         && (prevSw.equals(reachedDevice))) {
  93                     /* Ignore LAG links between the same set of Devicees */
  94                     continue;
  95                 } else  {
  96                     prevSw = reachedDevice;
  97                 }
  98
  99                 Integer distance = deviceSearched.get(reachedDevice);
 100                 if ((distance != null) && (distance < (currDistance + 1))) {
 101                     continue;
 102                 }
 103                 if (distance == null) {
 104                     /* First time visiting this Device node */
 105                     deviceQueue.add(reachedDevice);
 106                     distanceQueue.add(currDistance + 1);
 107                     deviceSearched.put(reachedDevice, currDistance + 1);
 108
 109                     ArrayList<DeviceId> distanceSwArray = distanceDeviceMap
 110                             .get(currDistance + 1);
 111                     if (distanceSwArray == null) {
 112                         distanceSwArray = new ArrayList<>();
 113                         distanceSwArray.add(reachedDevice);
 114                         distanceDeviceMap.put(currDistance + 1, distanceSwArray);
 115                     } else {
 116                         distanceSwArray.add(reachedDevice);
 117                     }
 118                 }
 119
 120                 ArrayList<Link> upstreamLinkArray =
 121                         upstreamLinks.get(reachedDevice);
 122                 if (upstreamLinkArray == null) {
 123                     upstreamLinkArray = new ArrayList<>();
 124                     upstreamLinkArray.add(copyDefaultLink(link));
 125                     //upstreamLinkArray.add(link);
 126                     upstreamLinks.put(reachedDevice, upstreamLinkArray);
 127                 } else {
 128                     /* ECMP links */
 129                     upstreamLinkArray.add(copyDefaultLink(link));
 130                 }
 131             }
 132         }
 133     }
 134
 135     /**
 136      * Calculates the BFS tree using any provided constraints and Intents.
 137      */
 138     private void calcECMPShortestPathGraph(List<String> deviceIdListToAvoid, List<Link> linksToAvoid) {
 139         deviceQueue.add(rootDevice);
 140         int currDistance = 0;
 141         distanceQueue.add(currDistance);
 142         deviceSearched.put(rootDevice, currDistance);
 143         boolean foundLinkToAvoid = false;
 144         while (!deviceQueue.isEmpty()) {
 145             DeviceId sw = deviceQueue.poll();
 146             DeviceId prevSw = null;
 147             currDistance = distanceQueue.poll();
 148             for (Link link : srManager.linkService.getDeviceEgressLinks(sw)) {
 149                 for (Link linkToAvoid: linksToAvoid) {
 150                     // TODO: equls should work
 151                     //if (link.equals(linkToAvoid)) {
 152                     if (linkContains(link, linksToAvoid)) {
 153                         foundLinkToAvoid = true;
 154                         break;
 155                     }
 156                 }
 157                 if (foundLinkToAvoid) {
 158                     foundLinkToAvoid = false;
 159                     continue;
 160                 }
 161                 DeviceId reachedDevice = link.dst().deviceId();
 162                 if (deviceIdListToAvoid.contains(reachedDevice.toString())) {
 163                     continue;
 164                 }
 165                 if ((prevSw != null)
 166                         && (prevSw.equals(reachedDevice))) {
 167                     /* Ignore LAG links between the same set of Devicees */
 168                     continue;
 169                 } else {
 170                     prevSw = reachedDevice;
 171                 }
 172
 173                 Integer distance = deviceSearched.get(reachedDevice);
 174                 if ((distance != null) && (distance < (currDistance + 1))) {
 175                     continue;
 176                 }
 177                 if (distance == null) {
 178                     /* First time visiting this Device node */
 179                     deviceQueue.add(reachedDevice);
 180                     distanceQueue.add(currDistance + 1);
 181                     deviceSearched.put(reachedDevice, currDistance + 1);
 182
 183                     ArrayList<DeviceId> distanceSwArray = distanceDeviceMap
 184                             .get(currDistance + 1);
 185                     if (distanceSwArray == null) {
 186                         distanceSwArray = new ArrayList<>();
 187                         distanceSwArray.add(reachedDevice);
 188                         distanceDeviceMap.put(currDistance + 1, distanceSwArray);
 189                     } else {
 190                         distanceSwArray.add(reachedDevice);
 191                     }
 192                 }
 193
 194                 ArrayList<Link> upstreamLinkArray =
 195                         upstreamLinks.get(reachedDevice);
 196                 if (upstreamLinkArray == null) {
 197                     upstreamLinkArray = new ArrayList<>();
 198                     upstreamLinkArray.add(copyDefaultLink(link));
 199                     upstreamLinks.put(reachedDevice, upstreamLinkArray);
 200                 } else {
 201                     /* ECMP links */
 202                     upstreamLinkArray.add(copyDefaultLink(link));
 203                 }
 204             }
 205         }
 206     }
 207
 208
 209     private boolean linkContains(Link link, List<Link> links) {
 210
 211         DeviceId srcDevice1 = link.src().deviceId();
 212         DeviceId dstDevice1 = link.dst().deviceId();
 213         long srcPort1 = link.src().port().toLong();
 214         long dstPort1 = link.dst().port().toLong();
 215
 216         for (Link link2: links) {
 217             DeviceId srcDevice2 = link2.src().deviceId();
 218             DeviceId dstDevice2 = link2.dst().deviceId();
 219             long srcPort2 = link2.src().port().toLong();
 220             long dstPort2 = link2.dst().port().toLong();
 221
 222             if (srcDevice1.toString().equals(srcDevice2.toString())
 223                     && dstDevice1.toString().equals(dstDevice2.toString())
 224                     && srcPort1 == srcPort2 && dstPort1 == dstPort2) {
 225                 return true;
 226             }
 227         }
 228
 229         return false;
 230     }
 231
 232     private void getDFSPaths(DeviceId dstDeviceDeviceId, Path path, ArrayList<Path> paths) {
 233         DeviceId rootDeviceDeviceId = rootDevice;
 234         for (Link upstreamLink : upstreamLinks.get(dstDeviceDeviceId)) {
 235             /* Deep clone the path object */
 236             Path sofarPath;
 237             ArrayList<Link> sofarLinks = new ArrayList<>();
 238             if (path != null && !path.links().isEmpty()) {
 239                 sofarLinks.addAll(path.links());
 240             }
 241             sofarLinks.add(upstreamLink);
 242             sofarPath = new DefaultPath(ProviderId.NONE, sofarLinks, 0);
 243             if (upstreamLink.src().deviceId().equals(rootDeviceDeviceId)) {
 244                 paths.add(sofarPath);
 245                 return;
 246             } else {
 247                 getDFSPaths(upstreamLink.src().deviceId(), sofarPath, paths);
 248             }
 249         }
 250     }
 251
 252     /**
 253      * Return root Device for the graph.
 254      *
 255      * @return root Device
 256      */
 257     public DeviceId getRootDevice() {
 258         return rootDevice;
 259     }
 260
 261     /**
 262      * Return the computed ECMP paths from the root Device to a given Device in
 263      * the network.
 264      *
 265      * @param targetDevice the target Device
 266      * @return the list of ECMP Paths from the root Device to the target Device
 267      */
 268     public ArrayList<Path> getECMPPaths(DeviceId targetDevice) {
 269         ArrayList<Path> pathArray = paths.get(targetDevice);
 270         if (pathArray == null && deviceSearched.containsKey(
 271                 targetDevice)) {
 272             pathArray = new ArrayList<>();
 273             DeviceId sw = targetDevice;
 274             getDFSPaths(sw, null, pathArray);
 275             paths.put(targetDevice, pathArray);
 276         }
 277         return pathArray;
 278     }
 279
 280     /**
 281      * Return the complete info of the computed ECMP paths for each Device
 282      * learned in multiple iterations from the root Device.
 283      *
 284      * @return the hash table of Devicees learned in multiple Dijkstra
 285      *         iterations and corresponding ECMP paths to it from the root
 286      *         Device
 287      */
 288     public HashMap<Integer, HashMap<DeviceId,
 289             ArrayList<Path>>> getCompleteLearnedDeviceesAndPaths() {
 290
 291         HashMap<Integer, HashMap<DeviceId, ArrayList<Path>>> pathGraph = new HashMap<>();
 292
 293         for (Integer itrIndx : distanceDeviceMap.keySet()) {
 294             HashMap<DeviceId, ArrayList<Path>> swMap = new HashMap<>();
 295             for (DeviceId sw : distanceDeviceMap.get(itrIndx)) {
 296                 swMap.put(sw, getECMPPaths(sw));
 297             }
 298             pathGraph.put(itrIndx, swMap);
 299         }
 300
 301         return pathGraph;
 302     }
 303
 304     /**
 305      * Return the complete info of the computed ECMP paths for each Device
 306      * learned in multiple iterations from the root Device.
 307      *
 308      * @return the hash table of Devicees learned in multiple Dijkstra
 309      *         iterations and corresponding ECMP paths in terms of Devicees to
 310      *         be traversed to it from the root Device
 311      */
 312     public HashMap<Integer, HashMap<DeviceId,
 313             ArrayList<ArrayList<DeviceId>>>> getAllLearnedSwitchesAndVia() {
 314
 315         HashMap<Integer, HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>>> deviceViaMap = new HashMap<>();
 316
 317         for (Integer itrIndx : distanceDeviceMap.keySet()) {
 318             HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>> swMap = new HashMap<>();
 319
 320             for (DeviceId sw : distanceDeviceMap.get(itrIndx)) {
 321                 ArrayList<ArrayList<DeviceId>> swViaArray = new ArrayList<>();
 322                 for (Path path : getECMPPaths(sw)) {
 323                     ArrayList<DeviceId> swVia = new ArrayList<>();
 324                     for (Link link : path.links()) {
 325                         if (link.src().deviceId().equals(rootDevice)) {
 326                             /* No need to add the root Device again in
 327                              * the Via list
 328                              */
 329                             continue;
 330                         }
 331                         swVia.add(link.src().deviceId());
 332                     }
 333                     swViaArray.add(swVia);
 334                 }
 335                 swMap.put(sw, swViaArray);
 336             }
 337             deviceViaMap.put(itrIndx, swMap);
 338         }
 339         return deviceViaMap;
 340     }
 341
 342
 343     private Link copyDefaultLink(Link link) {
 344         DefaultLink src = (DefaultLink) link;
 345         DefaultLink defaultLink = new DefaultLink(src.providerId(), src.src(),
 346                 src.dst(), src.type(), src.annotations());
 347
 348         return defaultLink;
 349     }
 350
 351     @Override
 352     public String toString() {
 353         StringBuilder sBuilder = new StringBuilder();
 354         for (Device device: srManager.deviceService.getDevices()) {
 355             if (device.id() != rootDevice) {
 356                 sBuilder.append("Paths from" + rootDevice + " to " + device.id() + "\r\n");
 357                 ArrayList<Path> paths = getECMPPaths(device.id());
 358                 if (paths != null) {
 359                     for (Path path : paths) {
 360                         for (Link link : path.links()) {
 361                             sBuilder.append(" : " + link.src() + " -> " + link.dst());
 362                         }
 363                     }
 364                 }
 365             }
 366         }
 367         return sBuilder.toString();
 368     }
 369 }
 370