diff --git a/server/PhysicalNetwork.cpp b/server/PhysicalNetwork.cpp
index ccac323..579d0bd 100644
--- a/server/PhysicalNetwork.cpp
+++ b/server/PhysicalNetwork.cpp
@@ -86,6 +86,18 @@
     return 0;
 }
 
+void PhysicalNetwork::invalidateRouteCache(const std::string& interface) {
+    for (const auto& dst : { "0.0.0.0/0", "::/0" }) {
+        // If any of these operations fail, there's no point in logging because RouteController will
+        // have already logged a message. There's also no point returning an error since there's
+        // nothing we can do.
+        (void) RouteController::addRoute(interface.c_str(), dst, "throw",
+                                         RouteController::INTERFACE);
+        (void) RouteController::removeRoute(interface.c_str(), dst, "throw",
+                                         RouteController::INTERFACE);
+    }
+}
+
 int PhysicalNetwork::setPermission(Permission permission) {
     if (permission == mPermission) {
         return 0;
@@ -103,6 +115,7 @@
                   interface.c_str(), mNetId, mPermission, permission);
             return ret;
         }
+        invalidateRouteCache(interface);
     }
     if (mIsDefault) {
         for (const std::string& interface : mInterfaces) {
diff --git a/server/PhysicalNetwork.h b/server/PhysicalNetwork.h
index 9200955..89c9443 100644
--- a/server/PhysicalNetwork.h
+++ b/server/PhysicalNetwork.h
@@ -50,6 +50,7 @@
     int addInterface(const std::string& interface) override WARN_UNUSED_RESULT;
     int removeInterface(const std::string& interface) override WARN_UNUSED_RESULT;
     int destroySocketsLackingPermission(Permission permission);
+    void invalidateRouteCache(const std::string& interface);
 
     Delegate* const mDelegate;
     Permission mPermission;
diff --git a/server/RouteController.cpp b/server/RouteController.cpp
index d7ab796..376dd9d 100644
--- a/server/RouteController.cpp
+++ b/server/RouteController.cpp
@@ -81,6 +81,14 @@
 const char* const ROUTE_TABLE_NAME_LOCAL = "local";
 const char* const ROUTE_TABLE_NAME_MAIN  = "main";
 
+// None of our routes specify priority, which causes them to have the default
+// priority. For throw routes, we use a fixed priority of 100000. This is
+// because we use throw routes either for maximum-length routes (/32 for IPv4,
+// /128 for IPv6), which we never create with any other priority, or for
+// purposely-low-priority default routes that should never match if there is
+// any other route in the table.
+uint32_t PRIO_THROW = 100000;
+
 // These values are upstream, but not yet in our headers.
 // TODO: delete these definitions when updating the headers.
 const uint16_t FRA_UID_RANGE = 20;
@@ -118,6 +126,7 @@
 
 rtattr RTATTR_TABLE     = { U16_RTA_LENGTH(sizeof(uint32_t)),           RTA_TABLE };
 rtattr RTATTR_OIF       = { U16_RTA_LENGTH(sizeof(uint32_t)),           RTA_OIF };
+rtattr RTATTR_PRIO      = { U16_RTA_LENGTH(sizeof(uint32_t)),           RTA_PRIORITY };
 
 uint8_t PADDING_BUFFER[RTA_ALIGNTO] = {0, 0, 0, 0};
 
@@ -371,6 +380,8 @@
         }
     }
 
+    bool isDefaultThrowRoute = (type == RTN_THROW && prefixLength == 0);
+
     // Assemble a rtmsg and put it in an array of iovec structures.
     rtmsg route = {
         .rtm_protocol = RTPROT_STATIC,
@@ -394,6 +405,8 @@
         { &ifindex,      interface != OIF_NONE ? sizeof(ifindex) : 0 },
         { &rtaGateway,   nexthop ? sizeof(rtaGateway) : 0 },
         { rawNexthop,    nexthop ? static_cast<size_t>(rawLength) : 0 },
+        { &RTATTR_PRIO,  isDefaultThrowRoute ? sizeof(RTATTR_PRIO) : 0 },
+        { &PRIO_THROW,   isDefaultThrowRoute ? sizeof(PRIO_THROW) : 0 },
     };
 
     uint16_t flags = (action == RTM_NEWROUTE) ? NETLINK_CREATE_REQUEST_FLAGS :