Primitive support to save the topology coordinates and cleanup of some unused tiering...
[controller.git] / opendaylight / hosttracker / implementation / src / main / java / org / opendaylight / controller / hosttracker / internal / HostTracker.java
1 /*
2  * Copyright (c) 2013 Cisco Systems, Inc. and others.  All rights reserved.
3  *
4  * This program and the accompanying materials are made available under the
5  * terms of the Eclipse Public License v1.0 which accompanies this distribution,
6  * and is available at http://www.eclipse.org/legal/epl-v10.html
7  */
8
9 package org.opendaylight.controller.hosttracker.internal;
10
11 import java.net.InetAddress;
12 import java.net.UnknownHostException;
13 import java.util.ArrayList;
14 import java.util.Collections;
15 import java.util.Dictionary;
16 import java.util.EnumSet;
17 import java.util.HashSet;
18 import java.util.List;
19 import java.util.Map;
20 import java.util.Map.Entry;
21 import java.util.Set;
22 import java.util.Timer;
23 import java.util.TimerTask;
24 import java.util.concurrent.Callable;
25 import java.util.concurrent.ConcurrentHashMap;
26 import java.util.concurrent.ConcurrentMap;
27 import java.util.concurrent.ExecutorService;
28 import java.util.concurrent.Executors;
29 import java.util.concurrent.Future;
30
31 import org.apache.felix.dm.Component;
32 import org.opendaylight.controller.clustering.services.CacheConfigException;
33 import org.opendaylight.controller.clustering.services.CacheExistException;
34 import org.opendaylight.controller.clustering.services.IClusterContainerServices;
35 import org.opendaylight.controller.clustering.services.IClusterServices;
36 import org.opendaylight.controller.hosttracker.hostAware.HostNodeConnector;
37 import org.opendaylight.controller.hosttracker.hostAware.IHostFinder;
38 import org.opendaylight.controller.hosttracker.IfHostListener;
39 import org.opendaylight.controller.hosttracker.IfIptoHost;
40 import org.opendaylight.controller.hosttracker.IfNewHostNotify;
41 import org.opendaylight.controller.sal.core.ConstructionException;
42 import org.opendaylight.controller.sal.core.Edge;
43 import org.opendaylight.controller.sal.core.Host;
44 import org.opendaylight.controller.sal.core.Node;
45 import org.opendaylight.controller.sal.core.NodeConnector;
46 import org.opendaylight.controller.sal.core.Property;
47 import org.opendaylight.controller.sal.core.State;
48 import org.opendaylight.controller.sal.core.Tier;
49 import org.opendaylight.controller.sal.core.UpdateType;
50 import org.opendaylight.controller.sal.packet.address.DataLinkAddress;
51 import org.opendaylight.controller.sal.packet.address.EthernetAddress;
52 import org.opendaylight.controller.sal.topology.TopoEdgeUpdate;
53 import org.opendaylight.controller.sal.utils.GlobalConstants;
54 import org.opendaylight.controller.sal.utils.HexEncode;
55 import org.opendaylight.controller.sal.utils.NodeCreator;
56 import org.opendaylight.controller.sal.utils.Status;
57 import org.opendaylight.controller.sal.utils.StatusCode;
58 import org.opendaylight.controller.switchmanager.IInventoryListener;
59 import org.opendaylight.controller.switchmanager.ISwitchManager;
60 import org.opendaylight.controller.switchmanager.ISwitchManagerAware;
61 import org.opendaylight.controller.switchmanager.Subnet;
62 import org.opendaylight.controller.topologymanager.ITopologyManager;
63 import org.opendaylight.controller.topologymanager.ITopologyManagerAware;
64 import org.slf4j.Logger;
65 import org.slf4j.LoggerFactory;
66
67 /**
68  * @file HostTracker.java This class tracks the location of IP Hosts as to which
69  *       Switch, Port, VLAN, they are connected to, as well as their MAC
70  *       address. This is done dynamically as well as statically. The dynamic
71  *       mechanism consists of listening to ARP messages as well sending ARP
72  *       requests. Static mechanism consists of Northbound APIs to add or remove
73  *       the hosts from the local database. ARP aging is also implemented to age
74  *       out dynamically learned hosts. Interface methods are provided for other
75  *       applications to 1. Query the local database for a single host 2. Get a
76  *       list of all hosts 3. Get notification if a host is learned/added or
77  *       removed the database
78  */
79
80 public class HostTracker implements IfIptoHost, IfHostListener,
81         ISwitchManagerAware, IInventoryListener, ITopologyManagerAware {
82     private static final Logger logger = LoggerFactory
83             .getLogger(HostTracker.class);
84     private IHostFinder hostFinder;
85     private ConcurrentMap<InetAddress, HostNodeConnector> hostsDB;
86     /*
87      * Following is a list of hosts which have been requested by NB APIs to be
88      * added, but either the switch or the port is not sup, so they will be
89      * added here until both come up
90      */
91     private ConcurrentMap<NodeConnector, HostNodeConnector> inactiveStaticHosts;
92     private Set<IfNewHostNotify> newHostNotify = Collections
93             .synchronizedSet(new HashSet<IfNewHostNotify>());
94
95     private ITopologyManager topologyManager;
96     private IClusterContainerServices clusterContainerService = null;
97     private ISwitchManager switchManager = null;
98     private Timer timer;
99     private Timer arp_refresh_timer;
100     private String containerName = null;
101
102     private static class ARPPending {
103         protected InetAddress hostIP;
104         protected short sent_count;
105         protected HostTrackerCallable hostTrackerCallable;
106
107         public InetAddress getHostIP() {
108             return hostIP;
109         }
110
111         public short getSent_count() {
112             return sent_count;
113         }
114
115         public HostTrackerCallable getHostTrackerCallable() {
116             return hostTrackerCallable;
117         }
118
119         public void setHostIP(InetAddress networkAddr) {
120             this.hostIP = networkAddr;
121         }
122
123         public void setSent_count(short count) {
124             this.sent_count = count;
125         }
126
127         public void setHostTrackerCallable(HostTrackerCallable callable) {
128             hostTrackerCallable = callable;
129         }
130     }
131
132     // This list contains the hosts for which ARP requests are being sent
133     // periodically
134     private List<ARPPending> ARPPendingList = new ArrayList<HostTracker.ARPPending>();
135     /*
136      * This list below contains the hosts which were initially in ARPPendingList
137      * above, but ARP response didn't come from there hosts after multiple
138      * attempts over 8 seconds. The assumption is that the response didn't come
139      * back due to one of the following possibilities: 1. The L3 interface
140      * wasn't created for this host in the controller. This would cause
141      * arphandler not to know where to send the ARP 2. The host facing port is
142      * down 3. The IP host doesn't exist or is not responding to ARP requests
143      * 
144      * Conditions 1 and 2 above can be recovered if ARP is sent when the
145      * relevant L3 interface is added or the port facing host comes up. Whenever
146      * L3 interface is added or host facing port comes up, ARP will be sent to
147      * hosts in this list.
148      * 
149      * We can't recover from condition 3 above
150      */
151     private ArrayList<ARPPending> failedARPReqList = new ArrayList<HostTracker.ARPPending>();
152
153     public HostTracker() {
154     }
155
156     private void startUp() {
157         allocateCache();
158         retrieveCache();
159
160         timer = new Timer();
161         timer.schedule(new OutStandingARPHandler(), 4000, 4000);
162
163         /* ARP Refresh Timer to go off every 5 seconds to implement ARP aging */
164         arp_refresh_timer = new Timer();
165         arp_refresh_timer.schedule(new ARPRefreshHandler(), 5000, 5000);
166         logger.debug("startUp: Caches created, timers started");
167     }
168
169     @SuppressWarnings("deprecation")
170     private void allocateCache() {
171         if (this.clusterContainerService == null) {
172             logger.error("un-initialized clusterContainerService, can't create cache");
173             return;
174         }
175         logger.debug("Creating Cache for HostTracker");
176         try {
177             this.clusterContainerService.createCache("hostTrackerAH",
178                     EnumSet.of(IClusterServices.cacheMode.NON_TRANSACTIONAL));
179             this.clusterContainerService.createCache("hostTrackerIH",
180                     EnumSet.of(IClusterServices.cacheMode.NON_TRANSACTIONAL));
181         } catch (CacheConfigException cce) {
182             logger.error("Cache couldn't be created for HostTracker -  check cache mode");
183         } catch (CacheExistException cce) {
184             logger.error("Cache for HostTracker already exists, destroy and recreate");
185         }
186         logger.debug("Cache successfully created for HostTracker");
187     }
188
189     @SuppressWarnings({ "unchecked", "deprecation" })
190     private void retrieveCache() {
191         if (this.clusterContainerService == null) {
192             logger.error("un-initialized clusterContainerService, can't retrieve cache");
193             return;
194         }
195         logger.debug("Retrieving cache for HostTrackerAH");
196         hostsDB = (ConcurrentMap<InetAddress, HostNodeConnector>) this.clusterContainerService
197                 .getCache("hostTrackerAH");
198         if (hostsDB == null) {
199             logger.error("Cache couldn't be retrieved for HostTracker");
200         }
201         logger.debug("Cache was successfully retrieved for HostTracker");
202         logger.debug("Retrieving cache for HostTrackerIH");
203         inactiveStaticHosts = (ConcurrentMap<NodeConnector, HostNodeConnector>) this.clusterContainerService
204                 .getCache("hostTrackerIH");
205         if (inactiveStaticHosts == null) {
206             logger.error("Cache couldn't be retrieved for HostTrackerIH");
207         }
208         logger.debug("Cache was successfully retrieved for HostTrackerIH");
209     }
210
211     public void nonClusterObjectCreate() {
212         hostsDB = new ConcurrentHashMap<InetAddress, HostNodeConnector>();
213         inactiveStaticHosts = new ConcurrentHashMap<NodeConnector, HostNodeConnector>();
214     }
215
216     @SuppressWarnings("deprecation")
217     private void destroyCache() {
218         if (this.clusterContainerService == null) {
219             logger.error("un-initialized clusterMger, can't destroy cache");
220             return;
221         }
222         logger.debug("Destroying Cache for HostTracker");
223         this.clusterContainerService.destroyCache("hostTrackerAH");
224         this.clusterContainerService.destroyCache("hostTrackerIH");
225         nonClusterObjectCreate();
226     }
227
228     public void shutDown() {
229     }
230
231     public void setnewHostNotify(IfNewHostNotify obj) {
232         this.newHostNotify.add(obj);
233     }
234
235     public void unsetnewHostNotify(IfNewHostNotify obj) {
236         this.newHostNotify.remove(obj);
237     }
238
239     public void setArpHandler(IHostFinder hostFinder) {
240         this.hostFinder = hostFinder;
241     }
242
243     public void unsetArpHandler(IHostFinder hostFinder) {
244         if (this.hostFinder == hostFinder) {
245             logger.debug("Arp Handler Service removed!");
246             this.hostFinder = null;
247         }
248     }
249
250     public void setTopologyManager(ITopologyManager s) {
251         this.topologyManager = s;
252     }
253
254     public void unsetTopologyManager(ITopologyManager s) {
255         if (this.topologyManager == s) {
256             logger.debug("Topology Manager Service removed!");
257             this.topologyManager = null;
258         }
259     }
260
261     private boolean hostExists(HostNodeConnector host) {
262         HostNodeConnector lhost = hostsDB.get(host.getNetworkAddress());
263         return host.equals(lhost);
264     }
265
266     private HostNodeConnector getHostFromOnActiveDB(InetAddress networkAddress) {
267         return hostsDB.get(networkAddress);
268     }
269
270     private Entry<NodeConnector, HostNodeConnector> getHostFromInactiveDB(
271             InetAddress networkAddress) {
272         for (Entry<NodeConnector, HostNodeConnector> entry : inactiveStaticHosts
273                 .entrySet()) {
274             if (entry.getValue().equalsByIP(networkAddress)) {
275                 logger.debug(
276                         "getHostFromInactiveDB(): Inactive Host found for IP:{} ",
277                         networkAddress.getHostAddress());
278                 return entry;
279             }
280         }
281         logger.debug(
282                 "getHostFromInactiveDB() Inactive Host Not found for IP: {}",
283                 networkAddress.getHostAddress());
284         return null;
285     }
286
287     private void removeHostFromInactiveDB(InetAddress networkAddress) {
288         NodeConnector nodeConnector = null;
289         for (Entry<NodeConnector, HostNodeConnector> entry : inactiveStaticHosts
290                 .entrySet()) {
291             if (entry.getValue().equalsByIP(networkAddress)) {
292                 nodeConnector = entry.getKey();
293                 break;
294             }
295         }
296         if (nodeConnector != null) {
297             inactiveStaticHosts.remove(nodeConnector);
298             logger.debug("removeHostFromInactiveDB(): Host Removed for IP: {}",
299                     networkAddress.getHostAddress());
300             return;
301         }
302         logger.debug("removeHostFromInactiveDB(): Host Not found for IP: {}",
303                 networkAddress.getHostAddress());
304     }
305
306     protected boolean hostMoved(HostNodeConnector host) {
307         if (hostQuery(host.getNetworkAddress()) != null) {
308             return true;
309         }
310         return false;
311     }
312
313     public HostNodeConnector hostQuery(InetAddress networkAddress) {
314         return hostsDB.get(networkAddress);
315     }
316
317     public Future<HostNodeConnector> discoverHost(InetAddress networkAddress) {
318         ExecutorService executor = Executors.newFixedThreadPool(1);
319         if (executor == null) {
320             logger.error("discoverHost: Null executor");
321             return null;
322         }
323         Callable<HostNodeConnector> worker = new HostTrackerCallable(this,
324                 networkAddress);
325         Future<HostNodeConnector> submit = executor.submit(worker);
326         return submit;
327     }
328
329     public HostNodeConnector hostFind(InetAddress networkAddress) {
330         /*
331          * Sometimes at boot with containers configured in the startup we hit
332          * this path (from TIF) when hostFinder has not been set yet Caller
333          * already handles the null return
334          */
335
336         if (hostFinder == null) {
337             logger.debug("Exiting hostFind, null hostFinder");
338             return null;
339         }
340
341         HostNodeConnector host = hostQuery(networkAddress);
342         if (host != null) {
343             logger.debug("hostFind(): Host found for IP: {}",
344                     networkAddress.getHostAddress());
345             return host;
346         }
347         /* host is not found, initiate a discovery */
348         hostFinder.find(networkAddress);
349         /* Also add this host to ARPPending List for any potential retries */
350         AddtoARPPendingList(networkAddress);
351         logger.debug(
352                 "hostFind(): Host Not Found for IP: {}, Inititated Host Discovery ...",
353                 networkAddress.getHostAddress());
354         return null;
355     }
356
357     public Set<HostNodeConnector> getAllHosts() {
358         Set<HostNodeConnector> allHosts = new HashSet<HostNodeConnector>();
359         for (Entry<InetAddress, HostNodeConnector> entry : hostsDB.entrySet()) {
360             HostNodeConnector host = entry.getValue();
361             allHosts.add(host);
362         }
363         logger.debug("Exiting getAllHosts, Found {} Hosts", allHosts.size());
364         return allHosts;
365     }
366
367     @Override
368     public Set<HostNodeConnector> getActiveStaticHosts() {
369         Set<HostNodeConnector> list = new HashSet<HostNodeConnector>();
370         for (Entry<InetAddress, HostNodeConnector> entry : hostsDB.entrySet()) {
371             HostNodeConnector host = entry.getValue();
372             if (host.isStaticHost()) {
373                 list.add(host);
374             }
375         }
376         logger.debug("getActiveStaticHosts(): Found {} Hosts", list.size());
377         return list;
378     }
379
380     @Override
381     public Set<HostNodeConnector> getInactiveStaticHosts() {
382         Set<HostNodeConnector> list = new HashSet<HostNodeConnector>();
383         for (Entry<NodeConnector, HostNodeConnector> entry : inactiveStaticHosts
384                 .entrySet()) {
385             list.add(entry.getValue());
386         }
387         logger.debug("getInactiveStaticHosts(): Found {} Hosts", list.size());
388         return list;
389     }
390
391     private void AddtoARPPendingList(InetAddress networkAddr) {
392         ARPPending arphost = new ARPPending();
393
394         arphost.setHostIP(networkAddr);
395         arphost.setSent_count((short) 1);
396         ARPPendingList.add(arphost);
397         logger.debug("Host Added to ARPPending List, IP: {}",
398                 networkAddr.toString());
399     }
400
401     private void removePendingARPFromList(int index) {
402         if (index >= ARPPendingList.size()) {
403             logger.warn(
404                     "removePendingARPFromList(): index greater than the List. Size:{}, Index:{}",
405                     ARPPendingList.size(), index);
406             return;
407         }
408         ARPPending arphost = ARPPendingList.remove(index);
409         HostTrackerCallable htCallable = arphost.getHostTrackerCallable();
410         if (htCallable != null)
411             htCallable.wakeup();
412     }
413
414     public void setCallableOnPendingARP(InetAddress networkAddr,
415             HostTrackerCallable callable) {
416         ARPPending arphost;
417         for (int i = 0; i < ARPPendingList.size(); i++) {
418             arphost = ARPPendingList.get(i);
419             if (arphost.getHostIP().equals(networkAddr)) {
420                 arphost.setHostTrackerCallable(callable);
421             }
422         }
423     }
424
425     private void ProcPendingARPReqs(InetAddress networkAddr) {
426         ARPPending arphost;
427
428         for (int i = 0; i < ARPPendingList.size(); i++) {
429             arphost = ARPPendingList.get(i);
430             if (arphost.getHostIP().equals(networkAddr)) {
431                 /*
432                  * An ARP was sent for this host. The address is learned, remove
433                  * the request
434                  */
435                 removePendingARPFromList(i);
436                 logger.debug("Host Removed from ARPPending List, IP: {}",
437                         networkAddr.toString());
438                 return;
439             }
440         }
441
442         /*
443          * It could have been a host from the FailedARPReqList
444          */
445
446         for (int i = 0; i < failedARPReqList.size(); i++) {
447             arphost = failedARPReqList.get(i);
448             if (arphost.getHostIP().equals(networkAddr)) {
449                 /*
450                  * An ARP was sent for this host. The address is learned, remove
451                  * the request
452                  */
453                 failedARPReqList.remove(i);
454                 logger.debug("Host Removed from FailedARPReqList List, IP: {}",
455                         networkAddr.toString());
456                 return;
457             }
458         }
459     }
460
461     // Learn a new Host
462     private void learnNewHost(HostNodeConnector host) {
463         host.initArpSendCountDown();
464         hostsDB.put(host.getNetworkAddress(), host);
465         logger.debug("New Host Learned: MAC: {}  IP: {}",
466                 HexEncode.bytesToHexString(host.getDataLayerAddressBytes()),
467                 host.getNetworkAddress().getHostAddress());
468     }
469
470     // Remove known Host
471     private void removeKnownHost(InetAddress key) {
472         HostNodeConnector host = hostsDB.get(key);
473         if (host != null) {
474             logger.debug("Removing Host: IP:{}", host.getNetworkAddress()
475                     .getHostAddress());
476             hostsDB.remove(key);
477         } else {
478             logger.error(
479                     "removeKnownHost(): Host for IP address {} not found in hostsDB",
480                     key.getHostAddress());
481         }
482     }
483
484     private class NotifyHostThread extends Thread {
485
486         private HostNodeConnector host;
487
488         public NotifyHostThread(HostNodeConnector h) {
489             this.host = h;
490         }
491
492         public void run() {
493             /* Check for Host Move case */
494             if (hostMoved(host)) {
495                 /*
496                  * Host has been moved from one location (switch,port, MAC, or
497                  * VLAN). Remove the existing host with its previous location
498                  * parameters, inform the applications, and add it as a new Host
499                  */
500                 HostNodeConnector removedHost = hostsDB.get(host
501                         .getNetworkAddress());
502                 removeKnownHost(host.getNetworkAddress());
503                 if (removedHost != null) {
504                     notifyHostLearnedOrRemoved(removedHost, false);
505                     logger.debug(
506                             "Host move occurred. Old Host:{}, New Host: {}",
507                             removedHost, host);
508                 } else {
509                     logger.error(
510                             "Host to be removed not found in hostsDB. Host {}",
511                             removedHost);
512                 }
513             }
514
515             /* check if there is an outstanding request for this host */
516             InetAddress networkAddr = host.getNetworkAddress();
517
518             // add and notify
519             learnNewHost(host);
520             ProcPendingARPReqs(networkAddr);
521             notifyHostLearnedOrRemoved(host, true);
522         }
523     }
524
525     public void hostListener(HostNodeConnector host) {
526
527         if (hostExists(host)) {
528             logger.debug("ARP received for Host: {}", host);
529             HostNodeConnector existinghost = hostsDB.get(host
530                     .getNetworkAddress());
531             existinghost.initArpSendCountDown();
532             return;
533         }
534         new NotifyHostThread(host).start();
535     }
536
537     // Notify whoever is interested that a new host was learned (dynamically or
538     // statically)
539     private void notifyHostLearnedOrRemoved(HostNodeConnector host, boolean add) {
540         // Update listeners if any
541         if (newHostNotify != null) {
542             synchronized (this.newHostNotify) {
543                 for (IfNewHostNotify ta : newHostNotify) {
544                     try {
545                         if (add) {
546                             ta.notifyHTClient(host);
547                         } else {
548                             ta.notifyHTClientHostRemoved(host);
549                         }
550                     } catch (Exception e) {
551                         logger.error("Exception on callback", e);
552                     }
553                 }
554             }
555         } else {
556             logger.error("notifyHostLearnedOrRemoved(): New host notify is null");
557         }
558
559         // Topology update is for some reason outside of listeners registry
560         // logic
561         Node node = host.getnodeconnectorNode();
562         Host h = null;
563         NodeConnector p = host.getnodeConnector();
564         try {
565             DataLinkAddress dla = new EthernetAddress(
566                     host.getDataLayerAddressBytes());
567             h = new org.opendaylight.controller.sal.core.Host(dla,
568                     host.getNetworkAddress());
569         } catch (ConstructionException ce) {
570             p = null;
571             h = null;
572         }
573
574         if (topologyManager != null && p != null && h != null) {
575             if (add == true) {
576                 Tier tier = new Tier(1);
577                 switchManager.setNodeProp(node, tier);
578                 topologyManager.updateHostLink(p, h, UpdateType.ADDED, null);
579             } else {
580                 // No need to reset the tiering if no other hosts are currently
581                 // connected
582                 // If this switch was discovered to be an access switch, it
583                 // still is even if the host is down
584                 Tier tier = new Tier(0);
585                 switchManager.setNodeProp(node, tier);
586                 topologyManager.updateHostLink(p, h, UpdateType.REMOVED, null);
587             }
588         }
589     }
590
591     /**
592      * When a new Host is learnt by the hosttracker module, it places the
593      * directly connected Node in Tier-1 & using this function, updates the Tier
594      * value for all other Nodes in the network hierarchy.
595      * 
596      * This is a recursive function and it takes care of updating the Tier value
597      * for all the connected and eligible Nodes.
598      * 
599      * @param n
600      *            Node that represents one of the Vertex in the Topology Graph.
601      * @param currentTier
602      *            The Tier on which n belongs
603      */
604     private void updateSwitchTiers(Node n, int currentTier) {
605         Map<Node, Set<Edge>> ndlinks = topologyManager.getNodeEdges();
606         if (ndlinks == null) {
607             logger.debug(
608                     "updateSwitchTiers(): ndlinks null for Node: {}, Tier:{}",
609                     n, currentTier);
610             return;
611         }
612         Set<Edge> links = ndlinks.get(n);
613         if (links == null) {
614             logger.debug("updateSwitchTiers(): links null for ndlinks:{}",
615                     ndlinks);
616             return;
617         }
618         ArrayList<Node> needsVisiting = new ArrayList<Node>();
619         for (Edge lt : links) {
620             if (!lt.getHeadNodeConnector().getType()
621                     .equals(NodeConnector.NodeConnectorIDType.OPENFLOW)) {
622                 // We don't want to work on Node that are not openflow
623                 // for now
624                 continue;
625             }
626             Node dstNode = lt.getHeadNodeConnector().getNode();
627             if (switchNeedsTieringUpdate(dstNode, currentTier + 1)) {
628                 Tier t = new Tier(currentTier + 1);
629                 switchManager.setNodeProp(dstNode, t);
630                 needsVisiting.add(dstNode);
631             }
632         }
633
634         /*
635          * Due to the nature of the problem, having a separate loop for nodes
636          * that needs visiting provides a decent walk optimization.
637          */
638         for (Node node : needsVisiting) {
639             updateSwitchTiers(node, currentTier + 1);
640         }
641     }
642
643     /**
644      * Internal convenience routine to check the eligibility of a Switch for a
645      * Tier update. Any Node with Tier=0 or a Tier value that is greater than
646      * the new Tier Value is eligible for the update.
647      * 
648      * @param n
649      *            Node for which the Tier update eligibility is checked
650      * @param tier
651      *            new Tier Value
652      * @return <code>true</code> if the Node is eligible for Tier Update
653      *         <code>false</code> otherwise
654      */
655
656     private boolean switchNeedsTieringUpdate(Node n, int tier) {
657         if (n == null) {
658             logger.error("switchNeedsTieringUpdate(): Null node for tier: {}",
659                     tier);
660             return false;
661         }
662         /*
663          * Node could have gone down
664          */
665         if (!switchManager.getNodes().contains(n)) {
666             return false;
667         }
668         // This is the case where Tier was never set for this node
669         Tier t = (Tier) switchManager.getNodeProp(n, Tier.TierPropName);
670         if (t == null)
671             return true;
672         if (t.getValue() == 0)
673             return true;
674         else if (t.getValue() > tier)
675             return true;
676         return false;
677     }
678
679     /**
680      * Internal convenience routine to clear all the Tier values to 0. This
681      * cleanup is performed during cases such as Topology Change where the
682      * existing Tier values might become incorrect
683      */
684     private void clearTiers() {
685         Set<Node> nodes = null;
686         if (switchManager == null) {
687             logger.error("clearTiers(): Null switchManager");
688             return;
689         }
690         nodes = switchManager.getNodes();
691
692         for (Node n : nodes) {
693             Tier t = new Tier(0);
694             switchManager.setNodeProp(n, t);
695         }
696     }
697
698     /**
699      * Internal convenience routine to print the hierarchies of switches.
700      */
701     @SuppressWarnings("unused")
702     private void logHierarchies(ArrayList<ArrayList<String>> hierarchies) {
703         String hierarchyString = null;
704         int num = 1;
705         for (ArrayList<String> hierarchy : hierarchies) {
706             StringBuffer buf = new StringBuffer();
707             buf.append("Hierarchy#" + num + " : ");
708             for (String switchName : hierarchy) {
709                 buf.append(switchName + "/");
710             }
711             logger.debug("{} -> {}", getContainerName(), buf.toString());
712             num++;
713         }
714     }
715
716     /**
717      * getHostNetworkHierarchy is the Back-end routine for the North-Bound API
718      * that returns the Network Hierarchy for a given Host. This API is
719      * typically used by applications like Hadoop for Rack Awareness
720      * functionality.
721      * 
722      * @param hostAddress
723      *            IP-Address of the host/node.
724      * @return Network Hierarchies represented by an Array of Array (of
725      *         Switch-Ids as String).
726      */
727     public List<List<String>> getHostNetworkHierarchy(InetAddress hostAddress) {
728         HostNodeConnector host = hostQuery(hostAddress);
729         if (host == null)
730             return null;
731
732         List<List<String>> hierarchies = new ArrayList<List<String>>();
733         ArrayList<String> currHierarchy = new ArrayList<String>();
734         hierarchies.add(currHierarchy);
735
736         Node node = host.getnodeconnectorNode();
737         updateCurrentHierarchy(node, currHierarchy, hierarchies);
738         return hierarchies;
739     }
740
741     /**
742      * dpidToHostNameHack is a hack function for Cisco Live Hadoop Demo. Mininet
743      * is used as the network for Hadoop Demos & in order to give a meaningful
744      * rack-awareness switch names, the DPID is organized in ASCII Characters
745      * and retrieved as string.
746      * 
747      * @param dpid
748      *            Switch DataPath Id
749      * @return Ascii String represented by the DPID.
750      */
751     private String dpidToHostNameHack(long dpid) {
752         String hex = Long.toHexString(dpid);
753
754         StringBuffer sb = new StringBuffer();
755         int result = 0;
756         for (int i = 0; i < hex.length(); i++) {
757             result = (int) ((dpid >> (i * 8)) & 0xff);
758             if (result == 0)
759                 continue;
760             if (result < 0x30)
761                 result += 0x40;
762             sb.append(String.format("%c", result));
763         }
764         return sb.reverse().toString();
765     }
766
767     /**
768      * A convenient recursive routine to obtain the Hierarchy of Switches.
769      * 
770      * @param node
771      *            Current Node in the Recursive routine.
772      * @param currHierarchy
773      *            Array of Nodes that make this hierarchy on which the Current
774      *            Switch belong
775      * @param fullHierarchy
776      *            Array of multiple Hierarchies that represent a given host.
777      */
778     @SuppressWarnings("unchecked")
779     private void updateCurrentHierarchy(Node node,
780             ArrayList<String> currHierarchy, List<List<String>> fullHierarchy) {
781         // currHierarchy.add(String.format("%x", currSw.getId()));
782         currHierarchy.add(dpidToHostNameHack((Long) node.getID()));
783         ArrayList<String> currHierarchyClone = (ArrayList<String>) currHierarchy
784                 .clone(); // Shallow copy as required
785
786         Map<Node, Set<Edge>> ndlinks = topologyManager.getNodeEdges();
787         if (ndlinks == null) {
788             logger.debug(
789                     "updateCurrentHierarchy(): topologyManager returned null ndlinks for node: {}",
790                     node);
791             return;
792         }
793         Node n = NodeCreator.createOFNode((Long) node.getID());
794         Set<Edge> links = ndlinks.get(n);
795         if (links == null) {
796             logger.debug("updateCurrentHierarchy(): Null links for ndlinks");
797             return;
798         }
799         for (Edge lt : links) {
800             if (!lt.getHeadNodeConnector().getType()
801                     .equals(NodeConnector.NodeConnectorIDType.OPENFLOW)) {
802                 // We don't want to work on Node that are not openflow
803                 // for now
804                 continue;
805             }
806             Node dstNode = lt.getHeadNodeConnector().getNode();
807
808             Tier nodeTier = (Tier) switchManager.getNodeProp(node,
809                     Tier.TierPropName);
810             Tier dstNodeTier = (Tier) switchManager.getNodeProp(dstNode,
811                     Tier.TierPropName);
812             if (dstNodeTier.getValue() > nodeTier.getValue()) {
813                 ArrayList<String> buildHierarchy = currHierarchy;
814                 if (currHierarchy.size() > currHierarchyClone.size()) {
815                     buildHierarchy = (ArrayList<String>) currHierarchyClone
816                             .clone(); // Shallow copy as required
817                     fullHierarchy.add(buildHierarchy);
818                 }
819                 updateCurrentHierarchy(dstNode, buildHierarchy, fullHierarchy);
820             }
821         }
822     }
823
824     private void edgeUpdate(Edge e, UpdateType type, Set<Property> props) {
825         Long srcNid = null;
826         Short srcPort = null;
827         Long dstNid = null;
828         Short dstPort = null;
829         boolean added = false;
830         String srcType = null;
831         String dstType = null;
832
833         if (e == null || type == null) {
834             logger.error("Edge or Update type are null!");
835             return;
836         } else {
837             srcType = e.getTailNodeConnector().getType();
838             dstType = e.getHeadNodeConnector().getType();
839
840             if (srcType.equals(NodeConnector.NodeConnectorIDType.PRODUCTION)) {
841                 logger.debug("Skip updates for {}", e);
842                 return;
843             }
844
845             if (!srcType.equals(NodeConnector.NodeConnectorIDType.OPENFLOW)) {
846                 logger.error("For now we cannot handle updates for "
847                         + "non-openflow nodes");
848                 return;
849             }
850
851             if (dstType.equals(NodeConnector.NodeConnectorIDType.PRODUCTION)) {
852                 logger.debug("Skip updates for {}", e);
853                 return;
854             }
855
856             if (!dstType.equals(NodeConnector.NodeConnectorIDType.OPENFLOW)) {
857                 logger.error("For now we cannot handle updates for "
858                         + "non-openflow nodes");
859                 return;
860             }
861
862             // At this point we know we got an openflow update, so
863             // lets fill everything accordingly.
864             srcNid = (Long) e.getTailNodeConnector().getNode().getID();
865             srcPort = (Short) e.getTailNodeConnector().getID();
866             dstNid = (Long) e.getHeadNodeConnector().getNode().getID();
867             dstPort = (Short) e.getHeadNodeConnector().getID();
868
869             // Now lets update the added flag
870             switch (type) {
871             case ADDED:
872             case CHANGED:
873                 added = true;
874                 break;
875             case REMOVED:
876                 added = false;
877             }
878         }
879
880         logger.debug(
881                 "HostTracker Topology linkUpdate handling src:{}[port {}] dst:{}[port {}] added: {}",
882                 new Object[] { srcNid, srcPort, dstNid, dstPort, added });
883     }
884
885     @Override
886     public void edgeUpdate(List<TopoEdgeUpdate> topoedgeupdateList) {
887         for (int i = 0; i < topoedgeupdateList.size(); i++) {
888             Edge e = topoedgeupdateList.get(i).getEdge();
889             Set<Property> p = topoedgeupdateList.get(i).getProperty();
890             UpdateType type = topoedgeupdateList.get(i).getUpdateType();
891             edgeUpdate(e, type, p);
892         }
893     }
894
895     public void subnetNotify(Subnet sub, boolean add) {
896         logger.debug("Received subnet notification: {}  add={}", sub, add);
897         if (add) {
898             for (int i = 0; i < failedARPReqList.size(); i++) {
899                 ARPPending arphost;
900                 arphost = failedARPReqList.get(i);
901                 logger.debug(
902                         "Sending the ARP from FailedARPReqList fors IP: {}",
903                         arphost.getHostIP().getHostAddress());
904                 hostFinder.find(arphost.getHostIP());
905             }
906         }
907     }
908
909     class OutStandingARPHandler extends TimerTask {
910         public void run() {
911             ARPPending arphost;
912             /* This routine runs every 4 seconds */
913             // logger.info ("ARP Handler called");
914             for (int i = 0; i < ARPPendingList.size(); i++) {
915                 arphost = ARPPendingList.get(i);
916                 if (arphost.getSent_count() < switchManager.getHostRetryCount()) {
917                     /*
918                      * No reply has been received of first ARP Req, send the
919                      * next one
920                      */
921                     hostFinder.find(arphost.getHostIP());
922                     arphost.sent_count++;
923                     logger.debug("ARP Sent from ARPPending List, IP: {}",
924                             arphost.getHostIP().getHostAddress());
925                 } else if (arphost.getSent_count() >= switchManager
926                         .getHostRetryCount()) {
927                     /*
928                      * Two ARP requests have been sent without receiving a
929                      * reply, remove this from the pending list
930                      */
931                     removePendingARPFromList(i);
932                     logger.debug(
933                             "ARP reply not received after two attempts, removing from Pending List IP: {}",
934                             arphost.getHostIP().getHostAddress());
935                     /*
936                      * Add this host to a different list which will be processed
937                      * on link up events
938                      */
939                     logger.debug("Adding the host to FailedARPReqList IP: {}",
940                             arphost.getHostIP().getHostAddress());
941                     failedARPReqList.add(arphost);
942
943                 } else {
944                     logger.error(
945                             "Inavlid arp_sent count for entery at index: {}", i);
946                 }
947             }
948         }
949     }
950
951     private class ARPRefreshHandler extends TimerTask {
952         @SuppressWarnings("deprecation")
953         public void run() {
954             if ((clusterContainerService != null)
955                     && !clusterContainerService.amICoordinator()) {
956                 return;
957             }
958             if ((switchManager != null)
959                     && !switchManager.isHostRefreshEnabled()) {
960                 /*
961                  * The host probe procedure was disabled by CLI
962                  */
963                 return;
964             }
965             if (hostsDB == null) {
966                 /* hostsDB is not allocated yet */
967                 logger.error("ARPRefreshHandler(): hostsDB is not allocated yet:");
968                 return;
969             }
970             for (Entry<InetAddress, HostNodeConnector> entry : hostsDB
971                     .entrySet()) {
972                 HostNodeConnector host = entry.getValue();
973                 if (host.isStaticHost()) {
974                     /* this host was learned via API3, don't age it out */
975                     continue;
976                 }
977
978                 short arp_cntdown = host.getArpSendCountDown();
979                 arp_cntdown--;
980                 if (arp_cntdown > switchManager.getHostRetryCount()) {
981                     host.setArpSendCountDown(arp_cntdown);
982                 } else if (arp_cntdown <= 0) {
983                     /*
984                      * No ARP Reply received in last 2 minutes, remove this host
985                      * and inform applications
986                      */
987                     removeKnownHost(entry.getKey());
988                     notifyHostLearnedOrRemoved(host, false);
989                 } else if (arp_cntdown <= switchManager.getHostRetryCount()) {
990                     /*
991                      * Use the services of arphandler to check if host is still
992                      * there
993                      */
994                     logger.trace(
995                             "ARP Probing ({}) for {}({})",
996                             new Object[] {
997                                     arp_cntdown,
998                                     host.getNetworkAddress().getHostAddress(),
999                                     HexEncode.bytesToHexString(host
1000                                             .getDataLayerAddressBytes()) });
1001                     host.setArpSendCountDown(arp_cntdown);
1002                     hostFinder.probe(host);
1003                 }
1004             }
1005         }
1006     }
1007
1008     /**
1009      * Inform the controller IP to MAC binding of a host and its connectivity to
1010      * an openflow switch in terms of Node, port, and VLAN.
1011      * 
1012      * @param networkAddr
1013      *            IP address of the host
1014      * @param dataLayer
1015      *            Address MAC address of the host
1016      * @param nc
1017      *            NodeConnector to which host is connected
1018      * @param port
1019      *            Port of the switch to which host is connected
1020      * @param vlan
1021      *            Vlan of which this host is member of
1022      * 
1023      * @return Status The status object as described in {@code Status}
1024      *         indicating the result of this action.
1025      */
1026
1027     public Status addStaticHostReq(InetAddress networkAddr,
1028             byte[] dataLayerAddress, NodeConnector nc, short vlan) {
1029         if (dataLayerAddress.length != 6) {
1030             return new Status(StatusCode.BADREQUEST, "Invalid MAC address");
1031         }
1032
1033         HostNodeConnector host = null;
1034         try {
1035             host = new HostNodeConnector(dataLayerAddress, networkAddr, nc,
1036                     vlan);
1037             if (hostExists(host)) {
1038                 // This host is already learned either via ARP or through a
1039                 // northbound request
1040                 HostNodeConnector transHost = hostsDB.get(networkAddr);
1041                 transHost.setStaticHost(true);
1042                 return new Status(StatusCode.SUCCESS, null);
1043             }
1044             host.setStaticHost(true);
1045             /*
1046              * Before adding host, Check if the switch and the port have already
1047              * come up
1048              */
1049             if (switchManager.isNodeConnectorEnabled(nc)) {
1050                 learnNewHost(host);
1051                 notifyHostLearnedOrRemoved(host, true);
1052             } else {
1053                 inactiveStaticHosts.put(nc, host);
1054                 logger.debug(
1055                         "Switch or switchport is not up, adding host {} to inactive list",
1056                         networkAddr.getHostName());
1057             }
1058             return new Status(StatusCode.SUCCESS, null);
1059         } catch (ConstructionException e) {
1060             return new Status(StatusCode.INTERNALERROR,
1061                     "Host could not be created");
1062         }
1063
1064     }
1065
1066     /**
1067      * Update the controller IP to MAC binding of a host and its connectivity to
1068      * an openflow switch in terms of switch id, switch port, and VLAN.
1069      * 
1070      * @param networkAddr
1071      *            IP address of the host
1072      * @param dataLayer
1073      *            Address MAC address of the host
1074      * @param nc
1075      *            NodeConnector to which host is connected
1076      * @param port
1077      *            Port of the switch to which host is connected
1078      * @param vlan
1079      *            Vlan of which this host is member of
1080      * 
1081      * @return boolean true if the host was added successfully, false otherwise
1082      */
1083     public boolean updateHostReq(InetAddress networkAddr,
1084             byte[] dataLayerAddress, NodeConnector nc, short vlan) {
1085         if (nc == null) {
1086             return false;
1087         }
1088         HostNodeConnector host = null;
1089         try {
1090             host = new HostNodeConnector(dataLayerAddress, networkAddr, nc,
1091                     vlan);
1092             if (!hostExists(host)) {
1093                 if ((inactiveStaticHosts.get(nc)) != null) {
1094                     inactiveStaticHosts.replace(nc, host);
1095                     return true;
1096                 }
1097                 return false;
1098             }
1099             hostsDB.replace(networkAddr, host);
1100             return true;
1101         } catch (ConstructionException e) {
1102         }
1103         return false;
1104     }
1105
1106     /**
1107      * Remove from the controller IP to MAC binding of a host and its
1108      * connectivity to an openflow switch
1109      * 
1110      * @param networkAddr
1111      *            IP address of the host
1112      * 
1113      * @return boolean true if the host was removed successfully, false
1114      *         otherwise
1115      */
1116
1117     public Status removeStaticHostReq(InetAddress networkAddress) {
1118         // Check if host is in active hosts database
1119         HostNodeConnector host = getHostFromOnActiveDB(networkAddress);
1120         if (host != null) {
1121             // Validation check
1122             if (!host.isStaticHost()) {
1123                 return new Status(StatusCode.FORBIDDEN, "Host "
1124                         + networkAddress.getHostName() + " is not static");
1125             }
1126             // Remove and notify
1127             notifyHostLearnedOrRemoved(host, false);
1128             removeKnownHost(networkAddress);
1129             return new Status(StatusCode.SUCCESS, null);
1130         }
1131
1132         // Check if host is in inactive hosts database
1133         Entry<NodeConnector, HostNodeConnector> entry = getHostFromInactiveDB(networkAddress);
1134         if (entry != null) {
1135             host = entry.getValue();
1136             // Validation check
1137             if (!host.isStaticHost()) {
1138                 return new Status(StatusCode.FORBIDDEN, "Host "
1139                         + networkAddress.getHostName() + " is not static");
1140             }
1141             this.removeHostFromInactiveDB(networkAddress);
1142             return new Status(StatusCode.SUCCESS, null);
1143         }
1144
1145         // Host is neither in active nor inactive hosts database
1146         return new Status(StatusCode.NOTFOUND, "Host does not exist");
1147     }
1148
1149     @Override
1150     public void modeChangeNotify(Node node, boolean proactive) {
1151         logger.debug("Set Switch {} Mode to {}", node.getID(), proactive);
1152     }
1153
1154     @Override
1155     public void notifyNode(Node node, UpdateType type,
1156             Map<String, Property> propMap) {
1157         if (node == null)
1158             return;
1159
1160         switch (type) {
1161         case REMOVED:
1162             long sid = (Long) node.getID();
1163             logger.debug("Received removedSwitch for sw id {}",
1164                     HexEncode.longToHexString(sid));
1165             for (Entry<InetAddress, HostNodeConnector> entry : hostsDB
1166                     .entrySet()) {
1167                 HostNodeConnector host = entry.getValue();
1168                 if (host.getnodeconnectornodeId() == sid) {
1169                     logger.debug("Switch: {} is down, remove from Hosts_DB",
1170                             sid);
1171                     removeKnownHost(entry.getKey());
1172                     notifyHostLearnedOrRemoved(host, false);
1173                 }
1174             }
1175             break;
1176         default:
1177             break;
1178         }
1179     }
1180
1181     @Override
1182     public void notifyNodeConnector(NodeConnector nodeConnector,
1183             UpdateType type, Map<String, Property> propMap) {
1184         if (nodeConnector == null)
1185             return;
1186
1187         boolean up = false;
1188         switch (type) {
1189         case ADDED:
1190             up = true;
1191             break;
1192         case REMOVED:
1193             break;
1194         case CHANGED:
1195             State state = (State) propMap.get(State.StatePropName);
1196             if ((state != null) && (state.getValue() == State.EDGE_UP)) {
1197                 up = true;
1198             }
1199             break;
1200         default:
1201             return;
1202         }
1203
1204         if (up) {
1205             handleNodeConnectorStatusUp(nodeConnector);
1206         } else {
1207             handleNodeConnectorStatusDown(nodeConnector);
1208         }
1209     }
1210
1211     @Override
1212     public Status addStaticHost(String networkAddress, String dataLayerAddress,
1213             NodeConnector nc, String vlan) {
1214         try {
1215             InetAddress ip = InetAddress.getByName(networkAddress);
1216             if (nc == null) {
1217                 return new Status(StatusCode.BADREQUEST, "Invalid NodeId");
1218             }
1219             return addStaticHostReq(ip,
1220                     HexEncode.bytesFromHexString(dataLayerAddress), nc,
1221                     Short.valueOf(vlan));
1222         } catch (UnknownHostException e) {
1223             logger.error("", e);
1224             return new Status(StatusCode.BADREQUEST, "Invalid Address");
1225         }
1226     }
1227
1228     @Override
1229     public Status removeStaticHost(String networkAddress) {
1230         InetAddress address;
1231         try {
1232             address = InetAddress.getByName(networkAddress);
1233             return removeStaticHostReq(address);
1234         } catch (UnknownHostException e) {
1235             logger.error("", e);
1236             return new Status(StatusCode.BADREQUEST, "Invalid Address");
1237         }
1238     }
1239
1240     private void handleNodeConnectorStatusUp(NodeConnector nodeConnector) {
1241         ARPPending arphost;
1242
1243         logger.debug("handleNodeConnectorStatusUp {}", nodeConnector);
1244
1245         for (int i = 0; i < failedARPReqList.size(); i++) {
1246             arphost = failedARPReqList.get(i);
1247             logger.debug("Sending the ARP from FailedARPReqList fors IP: {}",
1248                     arphost.getHostIP().getHostAddress());
1249             hostFinder.find(arphost.getHostIP());
1250         }
1251         HostNodeConnector host = inactiveStaticHosts.get(nodeConnector);
1252         if (host != null) {
1253             inactiveStaticHosts.remove(nodeConnector);
1254             learnNewHost(host);
1255             notifyHostLearnedOrRemoved(host, true);
1256         }
1257     }
1258
1259     private void handleNodeConnectorStatusDown(NodeConnector nodeConnector) {
1260         long sid = (Long) nodeConnector.getNode().getID();
1261         short port = (Short) nodeConnector.getID();
1262
1263         logger.debug("handleNodeConnectorStatusDown {}", nodeConnector);
1264
1265         for (Entry<InetAddress, HostNodeConnector> entry : hostsDB.entrySet()) {
1266             HostNodeConnector host = entry.getValue();
1267             if ((host.getnodeconnectornodeId() == sid)
1268                     && (host.getnodeconnectorportId() == port)) {
1269                 logger.debug(
1270                         "Switch: {}, Port: {} is down, remove from Hosts_DB",
1271                         sid, port);
1272                 removeKnownHost(entry.getKey());
1273                 notifyHostLearnedOrRemoved(host, false);
1274             }
1275         }
1276     }
1277
1278     void setClusterContainerService(IClusterContainerServices s) {
1279         logger.debug("Cluster Service set");
1280         this.clusterContainerService = s;
1281     }
1282
1283     void unsetClusterContainerService(IClusterContainerServices s) {
1284         if (this.clusterContainerService == s) {
1285             logger.debug("Cluster Service removed!");
1286             this.clusterContainerService = null;
1287         }
1288     }
1289
1290     void setSwitchManager(ISwitchManager s) {
1291         logger.debug("SwitchManager set");
1292         this.switchManager = s;
1293     }
1294
1295     void unsetSwitchManager(ISwitchManager s) {
1296         if (this.switchManager == s) {
1297             logger.debug("SwitchManager removed!");
1298             this.switchManager = null;
1299         }
1300     }
1301
1302     public String getContainerName() {
1303         if (containerName == null)
1304             return GlobalConstants.DEFAULT.toString();
1305         return containerName;
1306     }
1307
1308     /**
1309      * Function called by the dependency manager when all the required
1310      * dependencies are satisfied
1311      * 
1312      */
1313     void init(Component c) {
1314         Dictionary<?, ?> props = c.getServiceProperties();
1315         if (props != null) {
1316             this.containerName = (String) props.get("containerName");
1317             logger.debug("Running containerName: {}", this.containerName);
1318         } else {
1319             // In the Global instance case the containerName is empty
1320             this.containerName = "";
1321         }
1322         startUp();
1323     }
1324
1325     /**
1326      * Function called by the dependency manager when at least one dependency
1327      * become unsatisfied or when the component is shutting down because for
1328      * example bundle is being stopped.
1329      * 
1330      */
1331     void destroy() {
1332         destroyCache();
1333     }
1334
1335     /**
1336      * Function called by dependency manager after "init ()" is called and after
1337      * the services provided by the class are registered in the service registry
1338      * 
1339      */
1340     void start() {
1341     }
1342
1343     /**
1344      * Function called by the dependency manager before the services exported by
1345      * the component are unregistered, this will be followed by a "destroy ()"
1346      * calls
1347      * 
1348      */
1349     void stop() {
1350     }
1351
1352     @Override
1353     public void edgeOverUtilized(Edge edge) {
1354         // TODO Auto-generated method stub
1355
1356     }
1357
1358     @Override
1359     public void edgeUtilBackToNormal(Edge edge) {
1360         // TODO Auto-generated method stub
1361
1362     }
1363
1364 }