diff --git a/server/NetworkController.cpp b/server/NetworkController.cpp
index a32dd67..f5739e9 100644
--- a/server/NetworkController.cpp
+++ b/server/NetworkController.cpp
@@ -250,17 +250,17 @@
     }
 
     Permission permission = mPermissionsController->getPermissionForNetwork(netId);
-    if (!mRouteController->removeInterfaceFromNetwork(netId, interface, permission)) {
-        ALOGE("failed to remove interface %s from netId %u", interface, netId);
-        status = false;
-    }
-
     if (netId == getDefaultNetwork() &&
             !mRouteController->removeFromDefaultNetwork(interface, permission)) {
         ALOGE("failed to remove interface %s from default netId %u", interface, netId);
         status = false;
     }
 
+    if (!mRouteController->removeInterfaceFromNetwork(netId, interface, permission)) {
+        ALOGE("failed to remove interface %s from netId %u", interface, netId);
+        status = false;
+    }
+
     return status;
 }
 
diff --git a/server/RouteController.cpp b/server/RouteController.cpp
index 592dc35..a4086d9 100644
--- a/server/RouteController.cpp
+++ b/server/RouteController.cpp
@@ -21,6 +21,7 @@
 
 #include <linux/rtnetlink.h>
 #include <logwrap/logwrap.h>
+#include <map>
 #include <net/if.h>
 
 namespace {
@@ -41,8 +42,19 @@
 const int ROUTE_TABLE_PRIVILEGED_LEGACY = RouteController::ROUTE_TABLE_OFFSET_FROM_INDEX - 901;
 const int ROUTE_TABLE_LEGACY            = RouteController::ROUTE_TABLE_OFFSET_FROM_INDEX - 902;
 
+std::map<std::string, uint32_t> interfaceToIndex;
+
 uint32_t getRouteTableForInterface(const char* interface) {
     uint32_t index = if_nametoindex(interface);
+    if (index) {
+        interfaceToIndex[interface] = index;
+    } else {
+        // If the interface goes away if_nametoindex() will return 0 but we still need to know
+        // the index so we can remove the rules and routes.
+        std::map<std::string, uint32_t>::iterator it = interfaceToIndex.find(interface);
+        if (it != interfaceToIndex.end())
+            index = it->second;
+    }
     return index ? index + RouteController::ROUTE_TABLE_OFFSET_FROM_INDEX : 0;
 }
 
@@ -257,6 +269,7 @@
     if (!table) {
         return false;
     }
+    interfaceToIndex.erase(interface);
 
     return runIpRouteCommand("flush", table, NULL, NULL, NULL);
 }