diff --git a/ovn/controller/ovn-controller.c b/ovn/controller/ovn-controller.c
index 8471f64..28ee13e 100644
--- a/ovn/controller/ovn-controller.c
+++ b/ovn/controller/ovn-controller.c
@@ -251,8 +251,8 @@ update_ct_zones(struct sset *lports, struct hmap *patched_datapaths,
             continue;
         }
 
-        char *dnat = alloc_nat_zone_key(pd->port_binding, "dnat");
-        char *snat = alloc_nat_zone_key(pd->port_binding, "snat");
+        char *dnat = alloc_nat_zone_key(pd->key, "dnat");
+        char *snat = alloc_nat_zone_key(pd->key, "snat");
         sset_add(&all_users, dnat);
         sset_add(&all_users, snat);
         free(dnat);
diff --git a/ovn/controller/ovn-controller.h b/ovn/controller/ovn-controller.h
index f3edc43..470b1f5 100644
--- a/ovn/controller/ovn-controller.h
+++ b/ovn/controller/ovn-controller.h
@@ -51,7 +51,7 @@ struct local_datapath *get_local_datapath(const struct hmap *,
  * with at least one logical patch port binding. */
 struct patched_datapath {
     struct hmap_node hmap_node;
-    const struct sbrec_port_binding *port_binding;
+    char *key;  /* Holds the uuid of the corresponding datapath. */
     bool local; /* 'True' if the datapath is for gateway router. */
     bool stale; /* 'True' if the datapath is not referenced by any patch
                  * port. */
diff --git a/ovn/controller/patch.c b/ovn/controller/patch.c
index 3825f31..9a5c96f 100644
--- a/ovn/controller/patch.c
+++ b/ovn/controller/patch.c
@@ -263,7 +263,8 @@ add_patched_datapath(struct hmap *patched_datapaths,
 
     pd = xzalloc(sizeof *pd);
     pd->local = local;
-    pd->port_binding = binding_rec;
+    pd->key = xasprintf(UUID_FMT,
+                        UUID_ARGS(&binding_rec->datapath->header_.uuid));
     /* stale is set to false. */
     hmap_insert(patched_datapaths, &pd->hmap_node,
                 binding_rec->datapath->tunnel_key);
@@ -291,6 +292,7 @@ add_logical_patch_ports_postprocess(struct hmap *patched_datapaths)
                         patched_datapaths) {
         if (pd_cur_node->stale == true) {
             hmap_remove(patched_datapaths, &pd_cur_node->hmap_node);
+            free(pd_cur_node->key);
             free(pd_cur_node);
         }
     }
diff --git a/ovn/controller/physical.c b/ovn/controller/physical.c
index f7389ea..d1b40c2 100644
--- a/ovn/controller/physical.c
+++ b/ovn/controller/physical.c
@@ -297,8 +297,12 @@ consider_port_binding(struct hmap *flow_table,
         }
 
         int zone_id_dnat, zone_id_snat;
-        char *dnat = alloc_nat_zone_key(binding, "dnat");
-        char *snat = alloc_nat_zone_key(binding, "snat");
+        char *key = xasprintf(UUID_FMT,
+                              UUID_ARGS(&binding->datapath->header_.uuid));
+        char *dnat = alloc_nat_zone_key(key, "dnat");
+        char *snat = alloc_nat_zone_key(key, "snat");
+        free(key);
+
         zone_id_dnat = simap_get(ct_zones, dnat);
         if (zone_id_dnat) {
             put_load(zone_id_dnat, MFF_LOG_DNAT_ZONE, 0, 32, ofpacts_p);
diff --git a/ovn/lib/ovn-util.c b/ovn/lib/ovn-util.c
index 6113087..6e94083 100644
--- a/ovn/lib/ovn-util.c
+++ b/ovn/lib/ovn-util.c
@@ -105,13 +105,11 @@ extract_lsp_addresses(char *address, struct lport_addresses *laddrs,
 }
 
 /* Allocates a key for NAT conntrack zone allocation for a provided
- * 'port_binding' record and a 'type'.
+ * 'key' record and a 'type'.
  *
  * It is the caller's responsibility to free the allocated memory. */
 char *
-alloc_nat_zone_key(const struct sbrec_port_binding *port_binding,
-                   const char *type)
+alloc_nat_zone_key(const char *key, const char *type)
 {
-    return xasprintf(UUID_FMT"_%s",
-                     UUID_ARGS(&port_binding->datapath->header_.uuid), type);
+    return xasprintf("%s_%s", key, type);
 }
diff --git a/ovn/lib/ovn-util.h b/ovn/lib/ovn-util.h
index d23f4af..98b1426 100644
--- a/ovn/lib/ovn-util.h
+++ b/ovn/lib/ovn-util.h
@@ -43,6 +43,5 @@ extract_lsp_addresses(char *address, struct lport_addresses *laddrs,
                       bool store_ipv6);
 
 char *
-alloc_nat_zone_key(const struct sbrec_port_binding *port_binding,
-                   const char *type);
+alloc_nat_zone_key(const char *key, const char *type);
 #endif
