diff --git a/apps/openstacknetworking/app/src/main/java/org/onosproject/openstacknetworking/impl/OpenstackRoutingArpHandler.java b/apps/openstacknetworking/app/src/main/java/org/onosproject/openstacknetworking/impl/OpenstackRoutingArpHandler.java
index e938a90..3667d7c 100644
--- a/apps/openstacknetworking/app/src/main/java/org/onosproject/openstacknetworking/impl/OpenstackRoutingArpHandler.java
+++ b/apps/openstacknetworking/app/src/main/java/org/onosproject/openstacknetworking/impl/OpenstackRoutingArpHandler.java
@@ -144,10 +144,10 @@
     protected OpenstackNetworkService osNetworkService;
 
     @Reference(cardinality = ReferenceCardinality.MANDATORY_UNARY)
-    protected ComponentConfigService configService;
+    protected HostService hostService;
 
     @Reference(cardinality = ReferenceCardinality.MANDATORY_UNARY)
-    protected HostService hostService;
+    protected ComponentConfigService configService;
 
     // TODO: need to find a way to unify aprMode and gatewayMac variables with
     // that in SwitchingArpHandler
@@ -163,7 +163,8 @@
 
     private ApplicationId appId;
     private NodeId localNodeId;
-    private Map<String, String> floatingIpMacMap = Maps.newConcurrentMap();
+    private Map<String, MacAddress> floatingIpMacMap = Maps.newConcurrentMap();
+    private Map<MacAddress, InstancePort> removedPorts = Maps.newConcurrentMap();
 
     private final ExecutorService eventExecutor = newSingleThreadExecutor(
             groupedThreads(this.getClass().getSimpleName(), "event-handler", log));
@@ -175,8 +176,8 @@
         appId = coreService.registerApplication(OPENSTACK_NETWORKING_APP_ID);
         configService.registerProperties(getClass());
         localNodeId = clusterService.getLocalNode().id();
-        osRouterService.addListener(osRouterListener);
         hostService.addListener(hostListener);
+        osRouterService.addListener(osRouterListener);
         osNodeService.addListener(osNodeListener);
         leadershipService.runForLeadership(appId.name());
         packetService.addProcessor(packetProcessor, PacketProcessor.director(1));
@@ -342,13 +343,13 @@
                 .anyMatch(ip -> IpAddress.valueOf(ip.getIpAddress()).equals(targetIp));
     }
 
-    // FIXME: need to find a way to invoke this method during node initialization
     private void initFloatingIpMacMap() {
         osRouterService.floatingIps().forEach(f -> {
             if (f.getPortId() != null && f.getFloatingIpAddress() != null) {
                 Port port = osNetworkAdminService.port(f.getPortId());
                 if (port != null && port.getMacAddress() != null) {
-                    floatingIpMacMap.put(f.getFloatingIpAddress(), port.getMacAddress());
+                    floatingIpMacMap.put(f.getFloatingIpAddress(),
+                            MacAddress.valueOf(port.getMacAddress()));
                 }
             }
         });
@@ -429,23 +430,30 @@
                 return;
             }
 
-            String macString;
+            MacAddress targetMac;
+            InstancePort instPort;
 
             if (install) {
                 if (fip.getPortId() != null) {
-                    macString = osNetworkAdminService.port(fip.getPortId()).getMacAddress();
-                    floatingIpMacMap.put(fip.getFloatingIpAddress(), macString);
+                    String macString = osNetworkAdminService.port(fip.getPortId()).getMacAddress();
+                    targetMac = MacAddress.valueOf(macString);
+                    floatingIpMacMap.put(fip.getFloatingIpAddress(), targetMac);
                 } else {
                     log.trace("Unknown target ARP request for {}, ignore it",
                             fip.getFloatingIpAddress());
                     return;
                 }
             } else {
-                macString = floatingIpMacMap.get(fip.getFloatingIpAddress());
+                targetMac = floatingIpMacMap.get(fip.getFloatingIpAddress());
             }
 
-            MacAddress targetMac = MacAddress.valueOf(macString);
-            InstancePort instPort = instancePortService.instancePort(targetMac);
+            instPort = instancePortService.instancePort(targetMac);
+
+            // in VM purge case, we will have null instance port
+            if (instPort == null) {
+                instPort = removedPorts.get(targetMac);
+                removedPorts.remove(targetMac);
+            }
 
             OpenstackNode gw = getGwByInstancePort(gateways, instPort);
 
@@ -652,7 +660,7 @@
             InstancePort instPort = HostBasedInstancePort.of(event.subject());
             switch (event.type()) {
                 case HOST_REMOVED:
-                    removeArpRuleByInstancePort(instPort);
+                    storeTempInstPort(instPort);
                     break;
                 case HOST_UPDATED:
                 case HOST_ADDED:
@@ -661,7 +669,7 @@
             }
         }
 
-        private void removeArpRuleByInstancePort(InstancePort port) {
+        private void storeTempInstPort(InstancePort port) {
             Set<NetFloatingIP> ips = osRouterService.floatingIps();
             for (NetFloatingIP fip : ips) {
                 if (Strings.isNullOrEmpty(fip.getFixedIpAddress())) {
@@ -671,10 +679,7 @@
                     continue;
                 }
                 if (fip.getFixedIpAddress().equals(port.ipAddress().toString())) {
-                    eventExecutor.execute(() ->
-                        setFloatingIpArpRule(fip,
-                                osNodeService.completeNodes(GATEWAY), false)
-                    );
+                    removedPorts.put(port.macAddress(), port);
                 }
             }
         }
@@ -704,6 +709,9 @@
                     setDefaultArpRule(osNode, true);
                     setFloatingIpArpRuleForGateway(osNode, true);
 
+                    // initialize FloatingIp to Mac map
+                    initFloatingIpMacMap();
+
                     break;
                 case OPENSTACK_NODE_INCOMPLETE:
                     setDefaultArpRule(osNode, false);
diff --git a/apps/openstacknetworking/app/src/main/java/org/onosproject/openstacknetworking/impl/OpenstackRoutingFloatingIpHandler.java b/apps/openstacknetworking/app/src/main/java/org/onosproject/openstacknetworking/impl/OpenstackRoutingFloatingIpHandler.java
index 6493fc8..3976e5c 100644
--- a/apps/openstacknetworking/app/src/main/java/org/onosproject/openstacknetworking/impl/OpenstackRoutingFloatingIpHandler.java
+++ b/apps/openstacknetworking/app/src/main/java/org/onosproject/openstacknetworking/impl/OpenstackRoutingFloatingIpHandler.java
@@ -49,9 +49,9 @@
 import org.onosproject.openstacknetworking.api.InstancePortService;
 import org.onosproject.openstacknetworking.api.OpenstackFlowRuleService;
 import org.onosproject.openstacknetworking.api.OpenstackNetworkService;
+import org.onosproject.openstacknetworking.api.OpenstackRouterAdminService;
 import org.onosproject.openstacknetworking.api.OpenstackRouterEvent;
 import org.onosproject.openstacknetworking.api.OpenstackRouterListener;
-import org.onosproject.openstacknetworking.api.OpenstackRouterService;
 import org.onosproject.openstacknode.api.OpenstackNode;
 import org.onosproject.openstacknode.api.OpenstackNodeEvent;
 import org.onosproject.openstacknode.api.OpenstackNodeListener;
@@ -64,6 +64,7 @@
 import org.openstack4j.model.network.Router;
 import org.openstack4j.model.network.RouterInterface;
 import org.openstack4j.model.network.Subnet;
+import org.openstack4j.openstack.networking.domain.NeutronFloatingIP;
 import org.slf4j.Logger;
 import org.slf4j.LoggerFactory;
 
@@ -119,7 +120,7 @@
     protected InstancePortService instancePortService;
 
     @Reference(cardinality = ReferenceCardinality.MANDATORY_UNARY)
-    protected OpenstackRouterService osRouterService;
+    protected OpenstackRouterAdminService osRouterAdminService;
 
     @Reference(cardinality = ReferenceCardinality.MANDATORY_UNARY)
     protected OpenstackNetworkService osNetworkService;
@@ -143,7 +144,7 @@
         localNodeId = clusterService.getLocalNode().id();
         leadershipService.runForLeadership(appId.name());
         hostService.addListener(hostListener);
-        osRouterService.addListener(floatingIpLisener);
+        osRouterAdminService.addListener(floatingIpLisener);
         osNodeService.addListener(osNodeListener);
 
         log.info("Started");
@@ -153,7 +154,7 @@
     protected void deactivate() {
         hostService.removeListener(hostListener);
         osNodeService.removeListener(osNodeListener);
-        osRouterService.removeListener(floatingIpLisener);
+        osRouterAdminService.removeListener(floatingIpLisener);
         leadershipService.withdraw(appId.name());
         eventExecutor.shutdown();
 
@@ -564,14 +565,14 @@
             return null;
         }
 
-        RouterInterface osRouterIface = osRouterService.routerInterfaces().stream()
+        RouterInterface osRouterIface = osRouterAdminService.routerInterfaces().stream()
                 .filter(i -> Objects.equals(i.getSubnetId(), subnet.getId()))
                 .findAny().orElse(null);
         if (osRouterIface == null) {
             return null;
         }
 
-        Router osRouter = osRouterService.router(osRouterIface.getId());
+        Router osRouter = osRouterAdminService.router(osRouterIface.getId());
         if (osRouter == null) {
             return null;
         }
@@ -692,7 +693,7 @@
             switch (event.type()) {
                 case OPENSTACK_NODE_COMPLETE:
                     eventExecutor.execute(() -> {
-                        for (NetFloatingIP fip : osRouterService.floatingIps()) {
+                        for (NetFloatingIP fip : osRouterAdminService.floatingIps()) {
                             if (Strings.isNullOrEmpty(fip.getPortId())) {
                                 continue;
                             }
@@ -707,7 +708,7 @@
                     break;
                 case OPENSTACK_NODE_INCOMPLETE:
                     eventExecutor.execute(() -> {
-                        for (NetFloatingIP fip : osRouterService.floatingIps()) {
+                        for (NetFloatingIP fip : osRouterAdminService.floatingIps()) {
                             if (Strings.isNullOrEmpty(fip.getPortId())) {
                                 continue;
                             }
@@ -781,7 +782,7 @@
         }
 
         private void storeTempInstPort(InstancePort port) {
-            Set<NetFloatingIP> ips = osRouterService.floatingIps();
+            Set<NetFloatingIP> ips = osRouterAdminService.floatingIps();
             for (NetFloatingIP fip : ips) {
                 if (Strings.isNullOrEmpty(fip.getFixedIpAddress())) {
                     continue;
@@ -791,11 +792,13 @@
                 }
                 if (fip.getFixedIpAddress().equals(port.ipAddress().toString())) {
                     removedPorts.put(port.macAddress(), port);
-                    eventExecutor.execute(() -> {
-                        disassociateFloatingIp(fip, port.portId());
-                        log.info("Disassociated floating IP {}:{}",
-                                fip.getFloatingIpAddress(), fip.getFixedIpAddress());
-                    });
+                    NeutronFloatingIP neutronFip = (NeutronFloatingIP) fip;
+                    // invalidate bound fixed IP and port
+                    neutronFip.setFixedIpAddress(null);
+                    neutronFip.setPortId(null);
+                    osRouterAdminService.updateFloatingIp(neutronFip);
+                    log.info("Updated floating IP {}, due to host removal",
+                            neutronFip.getFloatingIpAddress());
                 }
             }
         }