Srikanth Vavilapalli | 9338f9d | 2014-09-18 07:37:09 -0700 | [diff] [blame] | 1 | package net.onrc.onos.apps.segmentrouting; |
| 2 | |
| 3 | import java.util.HashMap; |
Srikanth Vavilapalli | 9338f9d | 2014-09-18 07:37:09 -0700 | [diff] [blame] | 4 | import java.util.LinkedList; |
Srikanth Vavilapalli | 174e67c | 2014-09-19 07:27:17 -0700 | [diff] [blame] | 5 | import java.util.ArrayList; |
| 6 | |
| 7 | import org.projectfloodlight.openflow.util.HexString; |
Srikanth Vavilapalli | 9338f9d | 2014-09-18 07:37:09 -0700 | [diff] [blame] | 8 | |
| 9 | import net.onrc.onos.core.topology.Link; |
| 10 | import net.onrc.onos.core.topology.LinkData; |
| 11 | import net.onrc.onos.core.topology.Switch; |
| 12 | import net.onrc.onos.core.util.Dpid; |
| 13 | import net.onrc.onos.core.intent.Path; |
| 14 | |
Srikanth Vavilapalli | 174e67c | 2014-09-19 07:27:17 -0700 | [diff] [blame] | 15 | import org.slf4j.Logger; |
| 16 | import org.slf4j.LoggerFactory; |
| 17 | |
Srikanth Vavilapalli | 9338f9d | 2014-09-18 07:37:09 -0700 | [diff] [blame] | 18 | /** |
| 19 | * This class creates bandwidth constrained breadth first tree and returns paths |
| 20 | * from root switch to leaf switches which satisfies the bandwidth condition. If |
| 21 | * bandwidth parameter is not specified, the normal breadth first tree will be |
| 22 | * calculated. The paths are snapshot paths at the point of the class |
| 23 | * instantiation. |
| 24 | */ |
| 25 | public class ECMPShortestPathGraph { |
| 26 | LinkedList<Switch> switchQueue = new LinkedList<>(); |
Srikanth Vavilapalli | 174e67c | 2014-09-19 07:27:17 -0700 | [diff] [blame] | 27 | LinkedList<Integer> distanceQueue = new LinkedList<>(); |
| 28 | HashMap<Dpid, Integer> switchSearched = new HashMap<>(); |
| 29 | HashMap<Dpid, ArrayList<LinkData>> upstreamLinks = new HashMap<>(); |
| 30 | HashMap<Dpid, ArrayList<Path>> paths = new HashMap<>(); |
| 31 | HashMap<Integer, ArrayList<Switch>> distanceSwitchMap = new HashMap<>(); |
Srikanth Vavilapalli | 9338f9d | 2014-09-18 07:37:09 -0700 | [diff] [blame] | 32 | Switch rootSwitch; |
Srikanth Vavilapalli | 174e67c | 2014-09-19 07:27:17 -0700 | [diff] [blame] | 33 | private static final Logger log = LoggerFactory |
| 34 | .getLogger(SegmentRoutingManager.class); |
| 35 | |
Srikanth Vavilapalli | 9338f9d | 2014-09-18 07:37:09 -0700 | [diff] [blame] | 36 | /** |
| 37 | * Constructor. |
| 38 | * |
| 39 | * @param rootSwitch root of the BFS tree |
| 40 | */ |
| 41 | public ECMPShortestPathGraph(Switch rootSwitch) { |
| 42 | this.rootSwitch = rootSwitch; |
| 43 | calcECMPShortestPathGraph(); |
| 44 | } |
| 45 | |
| 46 | /** |
| 47 | * Calculates the BFS tree using any provided constraints and Intents. |
| 48 | */ |
| 49 | private void calcECMPShortestPathGraph() { |
| 50 | switchQueue.add(rootSwitch); |
Srikanth Vavilapalli | 174e67c | 2014-09-19 07:27:17 -0700 | [diff] [blame] | 51 | int currDistance = 0; |
| 52 | distanceQueue.add(currDistance); |
| 53 | switchSearched.put(rootSwitch.getDpid(),currDistance); |
Srikanth Vavilapalli | 9338f9d | 2014-09-18 07:37:09 -0700 | [diff] [blame] | 54 | while (!switchQueue.isEmpty()) { |
| 55 | Switch sw = switchQueue.poll(); |
Srikanth Vavilapalli | 174e67c | 2014-09-19 07:27:17 -0700 | [diff] [blame] | 56 | Switch prevSw = null; |
| 57 | currDistance = distanceQueue.poll(); |
Srikanth Vavilapalli | 9338f9d | 2014-09-18 07:37:09 -0700 | [diff] [blame] | 58 | for (Link link : sw.getOutgoingLinks()) { |
| 59 | Switch reachedSwitch = link.getDstPort().getSwitch(); |
Srikanth Vavilapalli | 878dad1 | 2014-09-19 21:02:10 -0700 | [diff] [blame] | 60 | if ((prevSw != null) && (prevSw.getDpid().equals(reachedSwitch.getDpid()))) |
Srikanth Vavilapalli | 174e67c | 2014-09-19 07:27:17 -0700 | [diff] [blame] | 61 | { |
Srikanth Vavilapalli | 878dad1 | 2014-09-19 21:02:10 -0700 | [diff] [blame] | 62 | /* Ignore LAG links between the same set of switches */ |
| 63 | continue; |
Srikanth Vavilapalli | 174e67c | 2014-09-19 07:27:17 -0700 | [diff] [blame] | 64 | } |
Srikanth Vavilapalli | 878dad1 | 2014-09-19 21:02:10 -0700 | [diff] [blame] | 65 | else |
Srikanth Vavilapalli | 174e67c | 2014-09-19 07:27:17 -0700 | [diff] [blame] | 66 | { |
Srikanth Vavilapalli | 878dad1 | 2014-09-19 21:02:10 -0700 | [diff] [blame] | 67 | prevSw = reachedSwitch; |
Srikanth Vavilapalli | 174e67c | 2014-09-19 07:27:17 -0700 | [diff] [blame] | 68 | } |
Srikanth Vavilapalli | 878dad1 | 2014-09-19 21:02:10 -0700 | [diff] [blame] | 69 | |
Srikanth Vavilapalli | 174e67c | 2014-09-19 07:27:17 -0700 | [diff] [blame] | 70 | Integer distance = switchSearched.get(reachedSwitch.getDpid()); |
| 71 | if ((distance != null) && (distance.intValue() < (currDistance+1))) { |
Srikanth Vavilapalli | 9338f9d | 2014-09-18 07:37:09 -0700 | [diff] [blame] | 72 | continue; |
| 73 | } |
Srikanth Vavilapalli | 174e67c | 2014-09-19 07:27:17 -0700 | [diff] [blame] | 74 | if (distance == null){ |
Srikanth Vavilapalli | 878dad1 | 2014-09-19 21:02:10 -0700 | [diff] [blame] | 75 | /* First time visiting this switch node */ |
| 76 | switchQueue.add(reachedSwitch); |
| 77 | distanceQueue.add(currDistance+1); |
| 78 | switchSearched.put(reachedSwitch.getDpid(),currDistance+1); |
| 79 | |
| 80 | ArrayList<Switch> distanceSwArray = distanceSwitchMap.get(currDistance+1); |
| 81 | if (distanceSwArray == null) |
| 82 | { |
| 83 | distanceSwArray = new ArrayList<Switch>(); |
| 84 | distanceSwArray.add(reachedSwitch); |
| 85 | distanceSwitchMap.put(currDistance+1, distanceSwArray); |
| 86 | } |
| 87 | else |
| 88 | distanceSwArray.add(reachedSwitch); |
Srikanth Vavilapalli | 174e67c | 2014-09-19 07:27:17 -0700 | [diff] [blame] | 89 | } |
Srikanth Vavilapalli | 878dad1 | 2014-09-19 21:02:10 -0700 | [diff] [blame] | 90 | |
| 91 | ArrayList<LinkData> upstreamLinkArray = |
| 92 | upstreamLinks.get(reachedSwitch.getDpid()); |
| 93 | if (upstreamLinkArray == null) |
| 94 | { |
| 95 | upstreamLinkArray = new ArrayList<LinkData>(); |
| 96 | upstreamLinkArray.add(new LinkData(link)); |
| 97 | upstreamLinks.put(reachedSwitch.getDpid(), upstreamLinkArray); |
| 98 | } |
| 99 | else |
| 100 | /* ECMP links */ |
| 101 | upstreamLinkArray.add(new LinkData(link)); |
Srikanth Vavilapalli | 9338f9d | 2014-09-18 07:37:09 -0700 | [diff] [blame] | 102 | } |
| 103 | } |
Srikanth Vavilapalli | 174e67c | 2014-09-19 07:27:17 -0700 | [diff] [blame] | 104 | |
| 105 | log.debug("ECMPShortestPathGraph:switchSearched for switch {} is {}", |
| 106 | HexString.toHexString(rootSwitch.getDpid().value()), switchSearched); |
| 107 | log.debug("ECMPShortestPathGraph:upstreamLinks for switch {} is {}", |
| 108 | HexString.toHexString(rootSwitch.getDpid().value()), upstreamLinks); |
| 109 | log.debug("ECMPShortestPathGraph:distanceSwitchMap for switch {} is {}", |
| 110 | HexString.toHexString(rootSwitch.getDpid().value()), distanceSwitchMap); |
| 111 | /* |
| 112 | for (Integer distance: distanceSwitchMap.keySet()){ |
| 113 | for (Switch sw: distanceSwitchMap.get(distance)){ |
| 114 | ArrayList<Path> path = getPath(sw); |
| 115 | log.debug("ECMPShortestPathGraph:Paths in Pass{} from switch {} to switch {} is {}", |
| 116 | distance, |
| 117 | HexString.toHexString(rootSwitch.getDpid().value()), |
| 118 | HexString.toHexString(sw.getDpid().value()), path); |
| 119 | } |
| 120 | }*/ |
| 121 | } |
| 122 | |
| 123 | private void getDFSPaths(Dpid dstSwitchDpid, Path path, ArrayList<Path> paths) { |
| 124 | Dpid rootSwitchDpid = rootSwitch.getDpid(); |
| 125 | for (LinkData upstreamLink : upstreamLinks.get(dstSwitchDpid)) { |
Srikanth Vavilapalli | 878dad1 | 2014-09-19 21:02:10 -0700 | [diff] [blame] | 126 | /* Deep clone the path object */ |
| 127 | Path sofarPath = new Path(); |
| 128 | if (!path.isEmpty()) |
| 129 | sofarPath.addAll(path.subList(0, path.size())); |
| 130 | sofarPath.add(upstreamLink); |
| 131 | if (upstreamLink.getSrc().getDpid().equals(rootSwitchDpid)) |
| 132 | { |
| 133 | paths.add(sofarPath); |
| 134 | return; |
| 135 | } |
| 136 | else |
| 137 | getDFSPaths(upstreamLink.getSrc().getDpid(),sofarPath, paths); |
Srikanth Vavilapalli | 174e67c | 2014-09-19 07:27:17 -0700 | [diff] [blame] | 138 | } |
Srikanth Vavilapalli | 9338f9d | 2014-09-18 07:37:09 -0700 | [diff] [blame] | 139 | } |
| 140 | |
| 141 | /** |
| 142 | * Return the computed path from the root switch to the leaf switch. |
| 143 | * |
| 144 | * @param leafSwitch the leaf switch |
| 145 | * @return the Path from the root switch to the leaf switch |
| 146 | */ |
Srikanth Vavilapalli | 174e67c | 2014-09-19 07:27:17 -0700 | [diff] [blame] | 147 | public ArrayList<Path> getPath(Switch leafSwitch) { |
| 148 | ArrayList<Path> pathArray = paths.get(leafSwitch.getDpid()); |
| 149 | if (pathArray == null && switchSearched.containsKey(leafSwitch.getDpid())) { |
Srikanth Vavilapalli | 878dad1 | 2014-09-19 21:02:10 -0700 | [diff] [blame] | 150 | pathArray = new ArrayList<>(); |
Srikanth Vavilapalli | 174e67c | 2014-09-19 07:27:17 -0700 | [diff] [blame] | 151 | Path path = new Path(); |
Srikanth Vavilapalli | 9338f9d | 2014-09-18 07:37:09 -0700 | [diff] [blame] | 152 | Dpid sw = leafSwitch.getDpid(); |
Srikanth Vavilapalli | 174e67c | 2014-09-19 07:27:17 -0700 | [diff] [blame] | 153 | getDFSPaths(sw, path, pathArray); |
| 154 | paths.put(leafSwitch.getDpid(), pathArray); |
Srikanth Vavilapalli | 9338f9d | 2014-09-18 07:37:09 -0700 | [diff] [blame] | 155 | } |
Srikanth Vavilapalli | 174e67c | 2014-09-19 07:27:17 -0700 | [diff] [blame] | 156 | return pathArray; |
Srikanth Vavilapalli | 9338f9d | 2014-09-18 07:37:09 -0700 | [diff] [blame] | 157 | } |
| 158 | } |