blob: 85ac6b8446eecb1594e861535b348fb8f57a00e4 [file] [log] [blame]
Umesh Krishnaswamy345ee992012-12-13 20:29:48 -08001package net.floodlightcontroller.topology;
2
3import java.util.ArrayList;
4import java.util.HashMap;
5import java.util.HashSet;
6import java.util.Iterator;
7import java.util.LinkedList;
8import java.util.List;
9import java.util.Map;
10import java.util.PriorityQueue;
11import java.util.Set;
12
13
14import org.slf4j.Logger;
15import org.slf4j.LoggerFactory;
16
17import net.floodlightcontroller.util.ClusterDFS;
18import net.floodlightcontroller.core.annotations.LogMessageCategory;
19import net.floodlightcontroller.core.annotations.LogMessageDoc;
20import net.floodlightcontroller.routing.BroadcastTree;
21import net.floodlightcontroller.routing.Link;
22import net.floodlightcontroller.routing.Route;
23import net.floodlightcontroller.routing.RouteId;
24import net.floodlightcontroller.util.LRUHashMap;
25
26/**
27 * A representation of a network topology. Used internally by
28 * {@link TopologyManager}
29 */
30@LogMessageCategory("Network Topology")
31public class TopologyInstance {
32
33 public static final short LT_SH_LINK = 1;
34 public static final short LT_BD_LINK = 2;
35 public static final short LT_TUNNEL = 3;
36
37 public static final int MAX_LINK_WEIGHT = 10000;
38 public static final int MAX_PATH_WEIGHT = Integer.MAX_VALUE - MAX_LINK_WEIGHT - 1;
39 public static final int PATH_CACHE_SIZE = 1000;
40
41 protected static Logger log = LoggerFactory.getLogger(TopologyInstance.class);
42
43 protected Map<Long, Set<Short>> switchPorts; // Set of ports for each switch
44 /** Set of switch ports that are marked as blocked. A set of blocked
45 * switch ports may be provided at the time of instantiation. In addition,
46 * we may add additional ports to this set.
47 */
48 protected Set<NodePortTuple> blockedPorts;
49 protected Map<NodePortTuple, Set<Link>> switchPortLinks; // Set of links organized by node port tuple
50 /** Set of links that are blocked. */
51 protected Set<Link> blockedLinks;
52
53 protected Set<Long> switches;
54 protected Set<NodePortTuple> broadcastDomainPorts;
55 protected Set<NodePortTuple> tunnelPorts;
56
57 protected Set<Cluster> clusters; // set of openflow domains
58 protected Map<Long, Cluster> switchClusterMap; // switch to OF domain map
59
60 // States for routing
61 protected Map<Long, BroadcastTree> destinationRootedTrees;
62 protected Map<Long, Set<NodePortTuple>> clusterBroadcastNodePorts;
63 protected Map<Long, BroadcastTree> clusterBroadcastTrees;
64 protected LRUHashMap<RouteId, Route> pathcache;
65
66 public TopologyInstance() {
67 this.switches = new HashSet<Long>();
68 this.switchPorts = new HashMap<Long, Set<Short>>();
69 this.switchPortLinks = new HashMap<NodePortTuple, Set<Link>>();
70 this.broadcastDomainPorts = new HashSet<NodePortTuple>();
71 this.tunnelPorts = new HashSet<NodePortTuple>();
72 this.blockedPorts = new HashSet<NodePortTuple>();
73 this.blockedLinks = new HashSet<Link>();
74 }
75
76 public TopologyInstance(Map<Long, Set<Short>> switchPorts,
77 Map<NodePortTuple, Set<Link>> switchPortLinks)
78 {
79 this.switches = new HashSet<Long>(switchPorts.keySet());
80 this.switchPorts = new HashMap<Long, Set<Short>>(switchPorts);
81 this.switchPortLinks = new HashMap<NodePortTuple,
82 Set<Link>>(switchPortLinks);
83 this.broadcastDomainPorts = new HashSet<NodePortTuple>();
84 this.tunnelPorts = new HashSet<NodePortTuple>();
85 this.blockedPorts = new HashSet<NodePortTuple>();
86 this.blockedLinks = new HashSet<Link>();
87
88 clusters = new HashSet<Cluster>();
89 switchClusterMap = new HashMap<Long, Cluster>();
90 }
91 public TopologyInstance(Map<Long, Set<Short>> switchPorts,
92 Set<NodePortTuple> blockedPorts,
93 Map<NodePortTuple, Set<Link>> switchPortLinks,
94 Set<NodePortTuple> broadcastDomainPorts,
95 Set<NodePortTuple> tunnelPorts){
96
97 // copy these structures
98 this.switches = new HashSet<Long>(switchPorts.keySet());
99 this.switchPorts = new HashMap<Long, Set<Short>>();
100 for(long sw: switchPorts.keySet()) {
101 this.switchPorts.put(sw, new HashSet<Short>(switchPorts.get(sw)));
102 }
103
104 this.blockedPorts = new HashSet<NodePortTuple>(blockedPorts);
105 this.switchPortLinks = new HashMap<NodePortTuple, Set<Link>>();
106 for(NodePortTuple npt: switchPortLinks.keySet()) {
107 this.switchPortLinks.put(npt,
108 new HashSet<Link>(switchPortLinks.get(npt)));
109 }
110 this.broadcastDomainPorts = new HashSet<NodePortTuple>(broadcastDomainPorts);
111 this.tunnelPorts = new HashSet<NodePortTuple>(tunnelPorts);
112
113 blockedLinks = new HashSet<Link>();
114 clusters = new HashSet<Cluster>();
115 switchClusterMap = new HashMap<Long, Cluster>();
116 destinationRootedTrees = new HashMap<Long, BroadcastTree>();
117 clusterBroadcastTrees = new HashMap<Long, BroadcastTree>();
118 clusterBroadcastNodePorts = new HashMap<Long, Set<NodePortTuple>>();
119 pathcache = new LRUHashMap<RouteId, Route>(PATH_CACHE_SIZE);
120 }
121
122 public void compute() {
123
124 // Step 1: Compute clusters ignoring broadcast domain links
125 // Create nodes for clusters in the higher level topology
126 // Must ignore blocked links.
127 identifyOpenflowDomains();
128
129 // Step 0: Remove all links connected to blocked ports.
130 // removeLinksOnBlockedPorts();
131
132
133 // Step 1.1: Add links to clusters
134 // Avoid adding blocked links to clusters
135 addLinksToOpenflowDomains();
136
137 // Step 2. Compute shortest path trees in each cluster for
138 // unicast routing. The trees are rooted at the destination.
139 // Cost for tunnel links and direct links are the same.
140 calculateShortestPathTreeInClusters();
141
142 // Step 3. Compute broadcast tree in each cluster.
143 // Cost for tunnel links are high to discourage use of
144 // tunnel links. The cost is set to the number of nodes
145 // in the cluster + 1, to use as minimum number of
146 // clusters as possible.
147 calculateBroadcastNodePortsInClusters();
148
149 // Step 4. print topology.
150 // printTopology();
151 }
152
153 public void printTopology() {
154 log.trace("-----------------------------------------------");
155 log.trace("Links: {}",this.switchPortLinks);
156 log.trace("broadcastDomainPorts: {}", broadcastDomainPorts);
157 log.trace("tunnelPorts: {}", tunnelPorts);
158 log.trace("clusters: {}", clusters);
159 log.trace("destinationRootedTrees: {}", destinationRootedTrees);
160 log.trace("clusterBroadcastNodePorts: {}", clusterBroadcastNodePorts);
161 log.trace("-----------------------------------------------");
162 }
163
164 protected void addLinksToOpenflowDomains() {
165 for(long s: switches) {
166 if (switchPorts.get(s) == null) continue;
167 for (short p: switchPorts.get(s)) {
168 NodePortTuple np = new NodePortTuple(s, p);
169 if (switchPortLinks.get(np) == null) continue;
170 if (isBroadcastDomainPort(np)) continue;
171 for(Link l: switchPortLinks.get(np)) {
172 if (isBlockedLink(l)) continue;
173 if (isBroadcastDomainLink(l)) continue;
174 Cluster c1 = switchClusterMap.get(l.getSrc());
175 Cluster c2 = switchClusterMap.get(l.getDst());
176 if (c1 ==c2) {
177 c1.addLink(l);
178 }
179 }
180 }
181 }
182 }
183
184 /**
185 * @author Srinivasan Ramasubramanian
186 *
187 * This function divides the network into clusters. Every cluster is
188 * a strongly connected component. The network may contain unidirectional
189 * links. The function calls dfsTraverse for performing depth first
190 * search and cluster formation.
191 *
192 * The computation of strongly connected components is based on
193 * Tarjan's algorithm. For more details, please see the Wikipedia
194 * link below.
195 *
196 * http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
197 */
198 @LogMessageDoc(level="ERROR",
199 message="No DFS object for switch {} found.",
200 explanation="The internal state of the topology module is corrupt",
201 recommendation=LogMessageDoc.REPORT_CONTROLLER_BUG)
202 public void identifyOpenflowDomains() {
203 Map<Long, ClusterDFS> dfsList = new HashMap<Long, ClusterDFS>();
204
205 if (switches == null) return;
206
207 for (Long key: switches) {
208 ClusterDFS cdfs = new ClusterDFS();
209 dfsList.put(key, cdfs);
210 }
211 Set<Long> currSet = new HashSet<Long>();
212
213 for (Long sw: switches) {
214 ClusterDFS cdfs = dfsList.get(sw);
215 if (cdfs == null) {
216 log.error("No DFS object for switch {} found.", sw);
217 }else if (!cdfs.isVisited()) {
218 dfsTraverse(0, 1, sw, dfsList, currSet);
219 }
220 }
221 }
222
223
224 /**
225 * @author Srinivasan Ramasubramanian
226 *
227 * This algorithm computes the depth first search (DFS) traversal of the
228 * switches in the network, computes the lowpoint, and creates clusters
229 * (of strongly connected components).
230 *
231 * The computation of strongly connected components is based on
232 * Tarjan's algorithm. For more details, please see the Wikipedia
233 * link below.
234 *
235 * http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
236 *
237 * The initialization of lowpoint and the check condition for when a
238 * cluster should be formed is modified as we do not remove switches that
239 * are already part of a cluster.
240 *
241 * A return value of -1 indicates that dfsTraverse failed somewhere in the middle
242 * of computation. This could happen when a switch is removed during the cluster
243 * computation procedure.
244 *
245 * @param parentIndex: DFS index of the parent node
246 * @param currIndex: DFS index to be assigned to a newly visited node
247 * @param currSw: ID of the current switch
248 * @param dfsList: HashMap of DFS data structure for each switch
249 * @param currSet: Set of nodes in the current cluster in formation
250 * @return long: DSF index to be used when a new node is visited
251 */
252
253 private long dfsTraverse (long parentIndex, long currIndex, long currSw,
254 Map<Long, ClusterDFS> dfsList, Set <Long> currSet) {
255
256 //Get the DFS object corresponding to the current switch
257 ClusterDFS currDFS = dfsList.get(currSw);
258 // Get all the links corresponding to this switch
259
260
261 //Assign the DFS object with right values.
262 currDFS.setVisited(true);
263 currDFS.setDfsIndex(currIndex);
264 currDFS.setParentDFSIndex(parentIndex);
265 currIndex++;
266
267 // Traverse the graph through every outgoing link.
268 if (switchPorts.get(currSw) != null){
269 for(Short p: switchPorts.get(currSw)) {
270 Set<Link> lset = switchPortLinks.get(new NodePortTuple(currSw, p));
271 if (lset == null) continue;
272 for(Link l:lset) {
273 long dstSw = l.getDst();
274
275 // ignore incoming links.
276 if (dstSw == currSw) continue;
277
278 // ignore if the destination is already added to
279 // another cluster
280 if (switchClusterMap.get(dstSw) != null) continue;
281
282 // ignore the link if it is blocked.
283 if (isBlockedLink(l)) continue;
284
285 // ignore this link if it is in broadcast domain
286 if (isBroadcastDomainLink(l)) continue;
287
288 // Get the DFS object corresponding to the dstSw
289 ClusterDFS dstDFS = dfsList.get(dstSw);
290
291 if (dstDFS.getDfsIndex() < currDFS.getDfsIndex()) {
292 // could be a potential lowpoint
293 if (dstDFS.getDfsIndex() < currDFS.getLowpoint())
294 currDFS.setLowpoint(dstDFS.getDfsIndex());
295
296 } else if (!dstDFS.isVisited()) {
297 // make a DFS visit
298 currIndex = dfsTraverse(currDFS.getDfsIndex(), currIndex, dstSw,
299 dfsList, currSet);
300
301 if (currIndex < 0) return -1;
302
303 // update lowpoint after the visit
304 if (dstDFS.getLowpoint() < currDFS.getLowpoint())
305 currDFS.setLowpoint(dstDFS.getLowpoint());
306 }
307 // else, it is a node already visited with a higher
308 // dfs index, just ignore.
309 }
310 }
311 }
312
313 // Add current node to currSet.
314 currSet.add(currSw);
315
316 // Cluster computation.
317 // If the node's lowpoint is greater than its parent's DFS index,
318 // we need to form a new cluster with all the switches in the
319 // currSet.
320 if (currDFS.getLowpoint() > currDFS.getParentDFSIndex()) {
321 // The cluster thus far forms a strongly connected component.
322 // create a new switch cluster and the switches in the current
323 // set to the switch cluster.
324 Cluster sc = new Cluster();
325 for(long sw: currSet){
326 sc.add(sw);
327 switchClusterMap.put(sw, sc);
328 }
329 // delete all the nodes in the current set.
330 currSet.clear();
331 // add the newly formed switch clusters to the cluster set.
332 clusters.add(sc);
333 }
334
335 return currIndex;
336 }
337
338 /**
339 * Go through every link and identify it is a blocked link or not.
340 * If blocked, remove it from the switchport links and put them in the
341 * blocked link category.
342 *
343 * Note that we do not update the tunnel ports and broadcast domain
344 * port structures. We need those to still answer the question if the
345 * ports are tunnel or broadcast domain ports.
346 *
347 * If we add additional ports to blocked ports later on, we may simply
348 * call this method again to remove the links on the newly blocked ports.
349 */
350 protected void removeLinksOnBlockedPorts() {
351 Iterator<NodePortTuple> nptIter;
352 Iterator<Link> linkIter;
353
354 // Iterate through all the links and all the switch ports
355 // and move the links on blocked switch ports to blocked links
356 nptIter = this.switchPortLinks.keySet().iterator();
357 while (nptIter.hasNext()) {
358 NodePortTuple npt = nptIter.next();
359 linkIter = switchPortLinks.get(npt).iterator();
360 while (linkIter.hasNext()) {
361 Link link = linkIter.next();
362 if (isBlockedLink(link)) {
363 this.blockedLinks.add(link);
364 linkIter.remove();
365 }
366 }
367 // Note that at this point, the switchport may have
368 // no links in it. We could delete the switch port,
369 // but we will leave it as is.
370 }
371 }
372
373 public Set<NodePortTuple> getBlockedPorts() {
374 return this.blockedPorts;
375 }
376
377 protected Set<Link> getBlockedLinks() {
378 return this.blockedLinks;
379 }
380
381 /** Returns true if a link has either one of its switch ports
382 * blocked.
383 * @param l
384 * @return
385 */
386 protected boolean isBlockedLink(Link l) {
387 NodePortTuple n1 = new NodePortTuple(l.getSrc(), l.getSrcPort());
388 NodePortTuple n2 = new NodePortTuple(l.getDst(), l.getDstPort());
389 return (isBlockedPort(n1) || isBlockedPort(n2));
390 }
391
392 protected boolean isBlockedPort(NodePortTuple npt) {
393 return blockedPorts.contains(npt);
394 }
395
396 protected boolean isTunnelPort(NodePortTuple npt) {
397 return tunnelPorts.contains(npt);
398 }
399
400 protected boolean isTunnelLink(Link l) {
401 NodePortTuple n1 = new NodePortTuple(l.getSrc(), l.getSrcPort());
402 NodePortTuple n2 = new NodePortTuple(l.getDst(), l.getDstPort());
403 return (isTunnelPort(n1) || isTunnelPort(n2));
404 }
405
406 public boolean isBroadcastDomainLink(Link l) {
407 NodePortTuple n1 = new NodePortTuple(l.getSrc(), l.getSrcPort());
408 NodePortTuple n2 = new NodePortTuple(l.getDst(), l.getDstPort());
409 return (isBroadcastDomainPort(n1) || isBroadcastDomainPort(n2));
410 }
411
412 public boolean isBroadcastDomainPort(NodePortTuple npt) {
413 return broadcastDomainPorts.contains(npt);
414 }
415
416 class NodeDist implements Comparable<NodeDist> {
417 private Long node;
418 public Long getNode() {
419 return node;
420 }
421
422 private int dist;
423 public int getDist() {
424 return dist;
425 }
426
427 public NodeDist(Long node, int dist) {
428 this.node = node;
429 this.dist = dist;
430 }
431
432 public int compareTo(NodeDist o) {
433 if (o.dist == this.dist) {
434 return (int)(o.node - this.node);
435 }
436 return o.dist - this.dist;
437 }
438 }
439
440 protected BroadcastTree dijkstra(Cluster c, Long root,
441 Map<Link, Integer> linkCost,
442 boolean isDstRooted) {
443 HashMap<Long, Link> nexthoplinks = new HashMap<Long, Link>();
444 //HashMap<Long, Long> nexthopnodes = new HashMap<Long, Long>();
445 HashMap<Long, Integer> cost = new HashMap<Long, Integer>();
446 int w;
447
448 for (Long node: c.links.keySet()) {
449 nexthoplinks.put(node, null);
450 //nexthopnodes.put(node, null);
451 cost.put(node, MAX_PATH_WEIGHT);
452 }
453
454 HashMap<Long, Boolean> seen = new HashMap<Long, Boolean>();
455 PriorityQueue<NodeDist> nodeq = new PriorityQueue<NodeDist>();
456 nodeq.add(new NodeDist(root, 0));
457 cost.put(root, 0);
458 while (nodeq.peek() != null) {
459 NodeDist n = nodeq.poll();
460 Long cnode = n.getNode();
461 int cdist = n.getDist();
462 if (cdist >= MAX_PATH_WEIGHT) break;
463 if (seen.containsKey(cnode)) continue;
464 seen.put(cnode, true);
465
466 for (Link link: c.links.get(cnode)) {
467 Long neighbor;
468
469 if (isDstRooted == true) neighbor = link.getSrc();
470 else neighbor = link.getDst();
471
472 // links directed toward cnode will result in this condition
473 // if (neighbor == cnode) continue;
474
475 if (linkCost == null || linkCost.get(link)==null) w = 1;
476 else w = linkCost.get(link);
477
478 int ndist = cdist + w; // the weight of the link, always 1 in current version of floodlight.
479 if (ndist < cost.get(neighbor)) {
480 cost.put(neighbor, ndist);
481 nexthoplinks.put(neighbor, link);
482 //nexthopnodes.put(neighbor, cnode);
483 nodeq.add(new NodeDist(neighbor, ndist));
484 }
485 }
486 }
487
488 BroadcastTree ret = new BroadcastTree(nexthoplinks, cost);
489 return ret;
490 }
491
492 protected void calculateShortestPathTreeInClusters() {
493 pathcache.clear();
494 destinationRootedTrees.clear();
495
496 Map<Link, Integer> linkCost = new HashMap<Link, Integer>();
497 int tunnel_weight = switchPorts.size() + 1;
498
499 for(NodePortTuple npt: tunnelPorts) {
500 if (switchPortLinks.get(npt) == null) continue;
501 for(Link link: switchPortLinks.get(npt)) {
502 if (link == null) continue;
503 linkCost.put(link, tunnel_weight);
504 }
505 }
506
507 for(Cluster c: clusters) {
508 for (Long node : c.links.keySet()) {
509 BroadcastTree tree = dijkstra(c, node, linkCost, true);
510 destinationRootedTrees.put(node, tree);
511 }
512 }
513 }
514
515 protected void calculateBroadcastTreeInClusters() {
516 for(Cluster c: clusters) {
517 // c.id is the smallest node that's in the cluster
518 BroadcastTree tree = destinationRootedTrees.get(c.id);
519 clusterBroadcastTrees.put(c.id, tree);
520 }
521 }
522
523 protected void calculateBroadcastNodePortsInClusters() {
524
525 clusterBroadcastTrees.clear();
526
527 calculateBroadcastTreeInClusters();
528
529 for(Cluster c: clusters) {
530 // c.id is the smallest node that's in the cluster
531 BroadcastTree tree = clusterBroadcastTrees.get(c.id);
532 //log.info("Broadcast Tree {}", tree);
533
534 Set<NodePortTuple> nptSet = new HashSet<NodePortTuple>();
535 Map<Long, Link> links = tree.getLinks();
536 if (links == null) continue;
537 for(long nodeId: links.keySet()) {
538 Link l = links.get(nodeId);
539 if (l == null) continue;
540 NodePortTuple npt1 = new NodePortTuple(l.getSrc(), l.getSrcPort());
541 NodePortTuple npt2 = new NodePortTuple(l.getDst(), l.getDstPort());
542 nptSet.add(npt1);
543 nptSet.add(npt2);
544 }
545 clusterBroadcastNodePorts.put(c.id, nptSet);
546 }
547 }
548
549 protected Route buildroute(RouteId id, long srcId, long dstId) {
550 NodePortTuple npt;
551
552 LinkedList<NodePortTuple> switchPorts =
553 new LinkedList<NodePortTuple>();
554
555 if (destinationRootedTrees == null) return null;
556 if (destinationRootedTrees.get(dstId) == null) return null;
557
558 Map<Long, Link> nexthoplinks =
559 destinationRootedTrees.get(dstId).getLinks();
560
561 if (!switches.contains(srcId) || !switches.contains(dstId)) {
562 // This is a switch that is not connected to any other switch
563 // hence there was no update for links (and hence it is not
564 // in the network)
565 log.debug("buildroute: Standalone switch: {}", srcId);
566
567 // The only possible non-null path for this case is
568 // if srcId equals dstId --- and that too is an 'empty' path []
569
570 } else if ((nexthoplinks!=null) && (nexthoplinks.get(srcId)!=null)) {
571 while (srcId != dstId) {
572 Link l = nexthoplinks.get(srcId);
573
574 npt = new NodePortTuple(l.getSrc(), l.getSrcPort());
575 switchPorts.addLast(npt);
576 npt = new NodePortTuple(l.getDst(), l.getDstPort());
577 switchPorts.addLast(npt);
578 srcId = nexthoplinks.get(srcId).getDst();
579 }
580 }
581 // else, no path exists, and path equals null
582
583 Route result = null;
584 if (switchPorts != null && !switchPorts.isEmpty())
585 result = new Route(id, switchPorts);
586 if (log.isTraceEnabled()) {
587 log.trace("buildroute: {}", result);
588 }
589 return result;
590 }
591
592 protected int getCost(long srcId, long dstId) {
593 BroadcastTree bt = destinationRootedTrees.get(dstId);
594 if (bt == null) return -1;
595 return (bt.getCost(srcId));
596 }
597
598 /*
599 * Getter Functions
600 */
601
602 protected Set<Cluster> getClusters() {
603 return clusters;
604 }
605
606 // IRoutingEngineService interfaces
607 protected boolean routeExists(long srcId, long dstId) {
608 BroadcastTree bt = destinationRootedTrees.get(dstId);
609 if (bt == null) return false;
610 Link link = bt.getLinks().get(srcId);
611 if (link == null) return false;
612 return true;
613 }
614
615 protected Route getRoute(long srcId, short srcPort,
616 long dstId, short dstPort) {
617
618
619 // Return null the route source and desitnation are the
620 // same switchports.
621 if (srcId == dstId && srcPort == dstPort)
622 return null;
623
624 List<NodePortTuple> nptList;
625 NodePortTuple npt;
626 Route r = getRoute(srcId, dstId);
627 if (r == null && srcId != dstId) return null;
628
629 if (r != null) {
630 nptList= new ArrayList<NodePortTuple>(r.getPath());
631 } else {
632 nptList = new ArrayList<NodePortTuple>();
633 }
634 npt = new NodePortTuple(srcId, srcPort);
635 nptList.add(0, npt); // add src port to the front
636 npt = new NodePortTuple(dstId, dstPort);
637 nptList.add(npt); // add dst port to the end
638
639 RouteId id = new RouteId(srcId, dstId);
640 r = new Route(id, nptList);
641 return r;
642 }
643
644 protected Route getRoute(long srcId, long dstId) {
645 RouteId id = new RouteId(srcId, dstId);
646 Route result = null;
647 if (pathcache.containsKey(id)) {
648 result = pathcache.get(id);
649 } else {
650 result = buildroute(id, srcId, dstId);
651 pathcache.put(id, result);
652 }
653 if (log.isTraceEnabled()) {
654 log.trace("getRoute: {} -> {}", id, result);
655 }
656 return result;
657 }
658
659 protected BroadcastTree getBroadcastTreeForCluster(long clusterId){
660 Cluster c = switchClusterMap.get(clusterId);
661 if (c == null) return null;
662 return clusterBroadcastTrees.get(c.id);
663 }
664
665 //
666 // ITopologyService interface method helpers.
667 //
668
669 protected boolean isInternalToOpenflowDomain(long switchid, short port) {
670 return !isAttachmentPointPort(switchid, port);
671 }
672
673 public boolean isAttachmentPointPort(long switchid, short port) {
674 NodePortTuple npt = new NodePortTuple(switchid, port);
675 if (switchPortLinks.containsKey(npt)) return false;
676 return true;
677 }
678
679 protected long getOpenflowDomainId(long switchId) {
680 Cluster c = switchClusterMap.get(switchId);
681 if (c == null) return switchId;
682 return c.getId();
683 }
684
685 protected long getL2DomainId(long switchId) {
686 return getOpenflowDomainId(switchId);
687 }
688
689 protected Set<Long> getSwitchesInOpenflowDomain(long switchId) {
690 Cluster c = switchClusterMap.get(switchId);
691 if (c == null) return null;
692 return (c.getNodes());
693 }
694
695 protected boolean inSameOpenflowDomain(long switch1, long switch2) {
696 Cluster c1 = switchClusterMap.get(switch1);
697 Cluster c2 = switchClusterMap.get(switch2);
698 if (c1 != null && c2 != null)
699 return (c1.getId() == c2.getId());
700 return (switch1 == switch2);
701 }
702
703 public boolean isAllowed(long sw, short portId) {
704 return true;
705 }
706
707 protected boolean
708 isIncomingBroadcastAllowedOnSwitchPort(long sw, short portId) {
709 if (isInternalToOpenflowDomain(sw, portId)) {
710 long clusterId = getOpenflowDomainId(sw);
711 NodePortTuple npt = new NodePortTuple(sw, portId);
712 if (clusterBroadcastNodePorts.get(clusterId).contains(npt))
713 return true;
714 else return false;
715 }
716 return true;
717 }
718
719 public boolean isConsistent(long oldSw, short oldPort, long newSw,
720 short newPort) {
721 if (isInternalToOpenflowDomain(newSw, newPort)) return true;
722 return (oldSw == newSw && oldPort == newPort);
723 }
724
725 protected Set<NodePortTuple>
726 getBroadcastNodePortsInCluster(long sw) {
727 long clusterId = getOpenflowDomainId(sw);
728 return clusterBroadcastNodePorts.get(clusterId);
729 }
730
731 public boolean inSameBroadcastDomain(long s1, short p1, long s2, short p2) {
732 return false;
733 }
734
735 public boolean inSameL2Domain(long switch1, long switch2) {
736 return inSameOpenflowDomain(switch1, switch2);
737 }
738
739 public NodePortTuple getOutgoingSwitchPort(long src, short srcPort,
740 long dst, short dstPort) {
741 // Use this function to redirect traffic if needed.
742 return new NodePortTuple(dst, dstPort);
743 }
744
745 public NodePortTuple getIncomingSwitchPort(long src, short srcPort,
746 long dst, short dstPort) {
747 // Use this function to reinject traffic from a different port if needed.
748 return new NodePortTuple(src, srcPort);
749 }
750
751 public Set<Long> getSwitches() {
752 return switches;
753 }
754
755 public Set<Short> getPortsWithLinks(long sw) {
756 return switchPorts.get(sw);
757 }
758
759 public Set<Short> getBroadcastPorts(long targetSw, long src, short srcPort) {
760 Set<Short> result = new HashSet<Short>();
761 long clusterId = getOpenflowDomainId(targetSw);
762 for(NodePortTuple npt: clusterBroadcastNodePorts.get(clusterId)) {
763 if (npt.getNodeId() == targetSw) {
764 result.add(npt.getPortId());
765 }
766 }
767 return result;
768 }
769
770 public NodePortTuple
771 getAllowedOutgoingBroadcastPort(long src, short srcPort, long dst,
772 short dstPort) {
773 // TODO Auto-generated method stub
774 return null;
775 }
776
777 public NodePortTuple
778 getAllowedIncomingBroadcastPort(long src, short srcPort) {
779 // TODO Auto-generated method stub
780 return null;
781 }
782}