diff --git a/lib/ovn-util.c b/lib/ovn-util.c
index 6ef9cac7f2..c8b89cc216 100644
--- a/lib/ovn-util.c
+++ b/lib/ovn-util.c
@@ -385,7 +385,7 @@ extract_sbrec_binding_first_mac(const struct sbrec_port_binding *binding,
 }
 
 bool
-lport_addresses_is_empty(struct lport_addresses *laddrs)
+lport_addresses_is_empty(const struct lport_addresses *laddrs)
 {
     return !laddrs->n_ipv4_addrs && !laddrs->n_ipv6_addrs;
 }
@@ -395,6 +395,10 @@ destroy_lport_addresses(struct lport_addresses *laddrs)
 {
     free(laddrs->ipv4_addrs);
     free(laddrs->ipv6_addrs);
+    laddrs->ipv4_addrs = NULL;
+    laddrs->ipv6_addrs = NULL;
+    laddrs->n_ipv4_addrs = 0;
+    laddrs->n_ipv6_addrs = 0;
 }
 
 /* Returns a string of the IP address of 'laddrs' that overlaps with 'ip_s'.
diff --git a/lib/ovn-util.h b/lib/ovn-util.h
index aa0b3b2fb4..d245d57d56 100644
--- a/lib/ovn-util.h
+++ b/lib/ovn-util.h
@@ -112,7 +112,7 @@ bool extract_sbrec_binding_first_mac(const struct sbrec_port_binding *binding,
 bool extract_lrp_networks__(char *mac, char **networks, size_t n_networks,
                             struct lport_addresses *laddrs);
 
-bool lport_addresses_is_empty(struct lport_addresses *);
+bool lport_addresses_is_empty(const struct lport_addresses *);
 void destroy_lport_addresses(struct lport_addresses *);
 const char *find_lport_address(const struct lport_addresses *laddrs,
                                const char *ip_s);
diff --git a/lib/stopwatch-names.h b/lib/stopwatch-names.h
index 4e93c1dc14..782d64320a 100644
--- a/lib/stopwatch-names.h
+++ b/lib/stopwatch-names.h
@@ -29,5 +29,6 @@
 #define LFLOWS_TO_SB_STOPWATCH_NAME "lflows_to_sb"
 #define PORT_GROUP_RUN_STOPWATCH_NAME "port_group_run"
 #define SYNC_METERS_RUN_STOPWATCH_NAME "sync_meters_run"
+#define LR_NAT_RUN_STOPWATCH_NAME "lr_nat_run"
 
 #endif
diff --git a/northd/automake.mk b/northd/automake.mk
index 5d77ca67b7..a477105470 100644
--- a/northd/automake.mk
+++ b/northd/automake.mk
@@ -24,6 +24,8 @@ northd_ovn_northd_SOURCES = \
 	northd/en-sync-from-sb.h \
 	northd/en-lb-data.c \
 	northd/en-lb-data.h \
+	northd/en-lr-nat.c \
+	northd/en-lr-nat.h \
 	northd/inc-proc-northd.c \
 	northd/inc-proc-northd.h \
 	northd/ipam.c \
diff --git a/northd/en-lflow.c b/northd/en-lflow.c
index 6ba26006e0..e4f875ef7c 100644
--- a/northd/en-lflow.c
+++ b/northd/en-lflow.c
@@ -19,6 +19,7 @@
 #include <stdio.h>
 
 #include "en-lflow.h"
+#include "en-lr-nat.h"
 #include "en-northd.h"
 #include "en-meters.h"
 
@@ -40,6 +41,9 @@ lflow_get_input_data(struct engine_node *node,
         engine_get_input_data("port_group", node);
     struct sync_meters_data *sync_meters_data =
         engine_get_input_data("sync_meters", node);
+    struct ed_type_lr_nat_data *lr_nat_data =
+        engine_get_input_data("lr_nat", node);
+
     lflow_input->nbrec_bfd_table =
         EN_OVSDB_GET(engine_get_input("NB_bfd", node));
     lflow_input->sbrec_bfd_table =
@@ -61,6 +65,7 @@ lflow_get_input_data(struct engine_node *node,
     lflow_input->ls_ports = &northd_data->ls_ports;
     lflow_input->lr_ports = &northd_data->lr_ports;
     lflow_input->ls_port_groups = &pg_data->ls_port_groups;
+    lflow_input->lr_nats = &lr_nat_data->lr_nats;
     lflow_input->meter_groups = &sync_meters_data->meter_groups;
     lflow_input->lb_datapaths_map = &northd_data->lb_datapaths_map;
     lflow_input->svc_monitor_map = &northd_data->svc_monitor_map;
diff --git a/northd/en-lr-nat.c b/northd/en-lr-nat.c
new file mode 100644
index 0000000000..273c5be34b
--- /dev/null
+++ b/northd/en-lr-nat.c
@@ -0,0 +1,423 @@
+/*
+ * Copyright (c) 2023, Red Hat, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at:
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <config.h>
+
+#include <getopt.h>
+#include <stdlib.h>
+#include <stdio.h>
+
+/* OVS includes */
+#include "include/openvswitch/hmap.h"
+#include "openvswitch/util.h"
+#include "openvswitch/vlog.h"
+#include "stopwatch.h"
+
+/* OVN includes */
+#include "en-lr-nat.h"
+#include "lib/inc-proc-eng.h"
+#include "lib/lb.h"
+#include "lib/ovn-nb-idl.h"
+#include "lib/ovn-sb-idl.h"
+#include "lib/ovn-util.h"
+#include "lib/stopwatch-names.h"
+#include "northd.h"
+
+VLOG_DEFINE_THIS_MODULE(en_lr_nat);
+
+/* Static function declarations. */
+static void lr_nat_table_init(struct lr_nat_table *);
+static void lr_nat_table_clear(struct lr_nat_table *);
+static void lr_nat_table_destroy(struct lr_nat_table *);
+static void lr_nat_table_build(struct lr_nat_table *,
+                               const struct ovn_datapaths *lr_datapaths);
+static struct lr_nat_record *lr_nat_table_find_(const struct lr_nat_table *,
+                                         const struct nbrec_logical_router *);
+static struct lr_nat_record *lr_nat_table_find_by_index_(
+    const struct lr_nat_table *, size_t od_index);
+
+static struct lr_nat_record *lr_nat_record_create(
+    struct lr_nat_table *, const struct ovn_datapath *);
+static void lr_nat_record_init(struct lr_nat_record *);
+static void lr_nat_record_reinit(struct lr_nat_record *);
+static void lr_nat_record_destroy(struct lr_nat_record *);
+
+static void lr_nat_entries_init(struct lr_nat_record *);
+static void lr_nat_entries_destroy(struct lr_nat_record *);
+static void lr_nat_external_ips_init(struct lr_nat_record *);
+static void lr_nat_external_ips_destroy(struct lr_nat_record *);
+static bool get_force_snat_ip(struct lr_nat_record *, const char *key_type,
+                              struct lport_addresses *);
+
+const struct lr_nat_record *
+lr_nat_table_find_by_index(const struct lr_nat_table *table,
+                           size_t od_index)
+{
+    return lr_nat_table_find_by_index_(table, od_index);
+}
+
+/* 'lr_nat' engine node manages the NB logical router NAT data.
+ */
+void *
+en_lr_nat_init(struct engine_node *node OVS_UNUSED,
+               struct engine_arg *arg OVS_UNUSED)
+{
+    struct ed_type_lr_nat_data *data = xzalloc(sizeof *data);
+    lr_nat_table_init(&data->lr_nats);
+    hmapx_init(&data->trk_data.crupdated);
+    return data;
+}
+
+void
+en_lr_nat_cleanup(void *data_)
+{
+    struct ed_type_lr_nat_data *data = (struct ed_type_lr_nat_data *) data_;
+    lr_nat_table_destroy(&data->lr_nats);
+    hmapx_destroy(&data->trk_data.crupdated);
+}
+
+void
+en_lr_nat_clear_tracked_data(void *data_)
+{
+    struct ed_type_lr_nat_data *data = (struct ed_type_lr_nat_data *) data_;
+    hmapx_clear(&data->trk_data.crupdated);
+}
+
+void
+en_lr_nat_run(struct engine_node *node, void *data_)
+{
+    struct northd_data *northd_data = engine_get_input_data("northd", node);
+    struct ed_type_lr_nat_data *data = data_;
+
+    stopwatch_start(LR_NAT_RUN_STOPWATCH_NAME, time_msec());
+    lr_nat_table_clear(&data->lr_nats);
+    lr_nat_table_build(&data->lr_nats, &northd_data->lr_datapaths);
+
+    stopwatch_stop(LR_NAT_RUN_STOPWATCH_NAME, time_msec());
+    engine_set_node_state(node, EN_UPDATED);
+}
+
+/* Handler functions. */
+bool
+lr_nat_northd_handler(struct engine_node *node, void *data_)
+{
+    struct northd_data *northd_data = engine_get_input_data("northd", node);
+    if (!northd_has_tracked_data(&northd_data->trk_data)) {
+        return false;
+    }
+
+    if (!northd_has_lr_nats_in_tracked_data(&northd_data->trk_data)) {
+        return true;
+    }
+
+    struct ed_type_lr_nat_data *data = data_;
+    struct lr_nat_record *lrnat_rec;
+    const struct ovn_datapath *od;
+    struct hmapx_node *hmapx_node;
+
+    HMAPX_FOR_EACH (hmapx_node, &northd_data->trk_data.lr_with_changed_nats) {
+        od = hmapx_node->data;
+        lrnat_rec = lr_nat_table_find_(&data->lr_nats, od->nbr);
+        ovs_assert(lrnat_rec);
+        lr_nat_record_reinit(lrnat_rec);
+
+        /* Add the lrnet rec to the tracking data. */
+        hmapx_add(&data->trk_data.crupdated, lrnat_rec);
+    }
+
+    if (lr_nat_has_tracked_data(&data->trk_data)) {
+        engine_set_node_state(node, EN_UPDATED);
+    }
+
+    return true;
+}
+
+/* static functions. */
+static void
+lr_nat_table_init(struct lr_nat_table *table)
+{
+    *table = (struct lr_nat_table) {
+        .entries = HMAP_INITIALIZER(&table->entries),
+    };
+}
+
+static void
+lr_nat_table_clear(struct lr_nat_table *table)
+{
+    struct lr_nat_record *lrnat_rec;
+    HMAP_FOR_EACH_POP (lrnat_rec, key_node, &table->entries) {
+        lr_nat_record_destroy(lrnat_rec);
+    }
+
+    free(table->array);
+    table->array = NULL;
+}
+
+static void
+lr_nat_table_build(struct lr_nat_table *table,
+                   const struct ovn_datapaths *lr_datapaths)
+{
+    table->array = xrealloc(table->array,
+                            ods_size(lr_datapaths) * sizeof *table->array);
+
+    const struct ovn_datapath *od;
+    HMAP_FOR_EACH (od, key_node, &lr_datapaths->datapaths) {
+        lr_nat_record_create(table, od);
+    }
+}
+
+static void
+lr_nat_table_destroy(struct lr_nat_table *table)
+{
+    lr_nat_table_clear(table);
+    hmap_destroy(&table->entries);
+}
+
+struct lr_nat_record *
+lr_nat_table_find_(const struct lr_nat_table *table,
+                   const struct nbrec_logical_router *nbr)
+{
+    struct lr_nat_record *lrnat_rec;
+
+    HMAP_FOR_EACH_WITH_HASH (lrnat_rec, key_node,
+                             uuid_hash(&nbr->header_.uuid), &table->entries) {
+        if (nbr == lrnat_rec->od->nbr) {
+            return lrnat_rec;
+        }
+    }
+    return NULL;
+}
+
+
+struct lr_nat_record *
+lr_nat_table_find_by_index_(const struct lr_nat_table *table,
+                            size_t od_index)
+{
+    ovs_assert(od_index <= hmap_count(&table->entries));
+
+    return table->array[od_index];
+}
+
+static struct lr_nat_record *
+lr_nat_record_create(struct lr_nat_table *table,
+                     const struct ovn_datapath *od)
+{
+    ovs_assert(od->nbr);
+
+    struct lr_nat_record *lrnat_rec = xzalloc(sizeof *lrnat_rec);
+    lrnat_rec->od = od;
+    lr_nat_record_init(lrnat_rec);
+
+    hmap_insert(&table->entries, &lrnat_rec->key_node,
+                uuid_hash(&od->nbr->header_.uuid));
+    table->array[od->index] = lrnat_rec;
+    return lrnat_rec;
+}
+
+static void
+lr_nat_record_init(struct lr_nat_record *lrnat_rec)
+{
+    lr_nat_entries_init(lrnat_rec);
+    lr_nat_external_ips_init(lrnat_rec);
+}
+
+static void
+lr_nat_record_reinit(struct lr_nat_record *lrnat_rec)
+{
+    lr_nat_entries_destroy(lrnat_rec);
+    lr_nat_external_ips_destroy(lrnat_rec);
+    lr_nat_record_init(lrnat_rec);
+}
+
+static void
+lr_nat_record_destroy(struct lr_nat_record *lrnat_rec)
+{
+    lr_nat_entries_destroy(lrnat_rec);
+    lr_nat_external_ips_destroy(lrnat_rec);
+    free(lrnat_rec);
+}
+
+static void
+lr_nat_external_ips_init(struct lr_nat_record *lrnat_rec)
+{
+    sset_init(&lrnat_rec->external_ips);
+    for (size_t i = 0; i < lrnat_rec->od->nbr->n_nat; i++) {
+        sset_add(&lrnat_rec->external_ips,
+                 lrnat_rec->od->nbr->nat[i]->external_ip);
+    }
+}
+
+static void
+lr_nat_external_ips_destroy(struct lr_nat_record *lrnat_rec)
+{
+    sset_destroy(&lrnat_rec->external_ips);
+}
+
+static void
+snat_ip_add(struct lr_nat_record *lrnat_rec, const char *ip,
+            struct ovn_nat *nat_entry)
+{
+    struct ovn_snat_ip *snat_ip = shash_find_data(&lrnat_rec->snat_ips, ip);
+
+    if (!snat_ip) {
+        snat_ip = xzalloc(sizeof *snat_ip);
+        ovs_list_init(&snat_ip->snat_entries);
+        shash_add(&lrnat_rec->snat_ips, ip, snat_ip);
+    }
+
+    if (nat_entry) {
+        ovs_list_push_back(&snat_ip->snat_entries,
+                           &nat_entry->ext_addr_list_node);
+    }
+}
+
+static void
+lr_nat_entries_init(struct lr_nat_record *lrnat_rec)
+{
+    shash_init(&lrnat_rec->snat_ips);
+    sset_init(&lrnat_rec->external_macs);
+    lrnat_rec->has_distributed_nat = false;
+
+    if (get_force_snat_ip(lrnat_rec, "dnat",
+                          &lrnat_rec->dnat_force_snat_addrs)) {
+        if (lrnat_rec->dnat_force_snat_addrs.n_ipv4_addrs) {
+            snat_ip_add(lrnat_rec,
+                        lrnat_rec->dnat_force_snat_addrs.ipv4_addrs[0].addr_s,
+                        NULL);
+        }
+        if (lrnat_rec->dnat_force_snat_addrs.n_ipv6_addrs) {
+            snat_ip_add(lrnat_rec,
+                        lrnat_rec->dnat_force_snat_addrs.ipv6_addrs[0].addr_s,
+                        NULL);
+        }
+    }
+
+    /* Check if 'lb_force_snat_ip' is configured with 'router_ip'. */
+    const char *lb_force_snat =
+        smap_get(&lrnat_rec->od->nbr->options, "lb_force_snat_ip");
+    if (lb_force_snat && !strcmp(lb_force_snat, "router_ip")
+            && smap_get(&lrnat_rec->od->nbr->options, "chassis")) {
+
+        /* Set it to true only if its gateway router and
+         * options:lb_force_snat_ip=router_ip. */
+        lrnat_rec->lb_force_snat_router_ip = true;
+    } else {
+        lrnat_rec->lb_force_snat_router_ip = false;
+
+        /* Check if 'lb_force_snat_ip' is configured with a set of
+         * IP address(es). */
+        if (get_force_snat_ip(lrnat_rec, "lb",
+                              &lrnat_rec->lb_force_snat_addrs)) {
+            if (lrnat_rec->lb_force_snat_addrs.n_ipv4_addrs) {
+                snat_ip_add(lrnat_rec,
+                        lrnat_rec->lb_force_snat_addrs.ipv4_addrs[0].addr_s,
+                        NULL);
+            }
+            if (lrnat_rec->lb_force_snat_addrs.n_ipv6_addrs) {
+                snat_ip_add(lrnat_rec,
+                        lrnat_rec->lb_force_snat_addrs.ipv6_addrs[0].addr_s,
+                        NULL);
+            }
+        }
+    }
+
+    if (!lrnat_rec->od->nbr->n_nat) {
+        return;
+    }
+
+    lrnat_rec->nat_entries =
+        xmalloc(lrnat_rec->od->nbr->n_nat * sizeof *lrnat_rec->nat_entries);
+
+    for (size_t i = 0; i < lrnat_rec->od->nbr->n_nat; i++) {
+        const struct nbrec_nat *nat = lrnat_rec->od->nbr->nat[i];
+        struct ovn_nat *nat_entry = &lrnat_rec->nat_entries[i];
+
+        nat_entry->nb = nat;
+        if (!extract_ip_addresses(nat->external_ip,
+                                  &nat_entry->ext_addrs) ||
+                !nat_entry_is_valid(nat_entry)) {
+            static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(5, 1);
+
+            VLOG_WARN_RL(&rl,
+                         "Bad ip address %s in nat configuration "
+                         "for router %s", nat->external_ip,
+                         lrnat_rec->od->nbr->name);
+            continue;
+        }
+
+        /* If this is a SNAT rule add the IP to the set of unique SNAT IPs. */
+        if (!strcmp(nat->type, "snat")) {
+            if (!nat_entry_is_v6(nat_entry)) {
+                snat_ip_add(lrnat_rec,
+                            nat_entry->ext_addrs.ipv4_addrs[0].addr_s,
+                            nat_entry);
+            } else {
+                snat_ip_add(lrnat_rec,
+                            nat_entry->ext_addrs.ipv6_addrs[0].addr_s,
+                            nat_entry);
+            }
+        } else {
+            if (!strcmp(nat->type, "dnat_and_snat")
+                    && nat->logical_port && nat->external_mac) {
+                lrnat_rec->has_distributed_nat = true;
+            }
+
+            if (nat->external_mac) {
+                sset_add(&lrnat_rec->external_macs, nat->external_mac);
+            }
+        }
+    }
+    lrnat_rec->n_nat_entries = lrnat_rec->od->nbr->n_nat;
+}
+
+static bool
+get_force_snat_ip(struct lr_nat_record *lrnat_rec, const char *key_type,
+                  struct lport_addresses *laddrs)
+{
+    char *key = xasprintf("%s_force_snat_ip", key_type);
+    const char *addresses = smap_get(&lrnat_rec->od->nbr->options, key);
+    free(key);
+
+    if (!addresses) {
+        return false;
+    }
+
+    if (!extract_ip_address(addresses, laddrs)) {
+        static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(5, 1);
+        VLOG_WARN_RL(&rl, "bad ip %s in options of router "UUID_FMT"",
+                     addresses, UUID_ARGS(&lrnat_rec->od->nbr->header_.uuid));
+        return false;
+    }
+
+    return true;
+}
+
+static void
+lr_nat_entries_destroy(struct lr_nat_record *lrnat_rec)
+{
+    shash_destroy_free_data(&lrnat_rec->snat_ips);
+    destroy_lport_addresses(&lrnat_rec->dnat_force_snat_addrs);
+    destroy_lport_addresses(&lrnat_rec->lb_force_snat_addrs);
+
+    for (size_t i = 0; i < lrnat_rec->n_nat_entries; i++) {
+        destroy_lport_addresses(&lrnat_rec->nat_entries[i].ext_addrs);
+    }
+
+    free(lrnat_rec->nat_entries);
+    lrnat_rec->nat_entries = NULL;
+    lrnat_rec->n_nat_entries = 0;
+    sset_destroy(&lrnat_rec->external_macs);
+}
diff --git a/northd/en-lr-nat.h b/northd/en-lr-nat.h
new file mode 100644
index 0000000000..3ec4c7b506
--- /dev/null
+++ b/northd/en-lr-nat.h
@@ -0,0 +1,127 @@
+/*
+ * Copyright (c) 2023, Red Hat, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at:
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+#ifndef EN_LR_NAT_H
+#define EN_LR_NAT_H 1
+
+#include <stdint.h>
+
+/* OVS includes. */
+#include "lib/hmapx.h"
+#include "openvswitch/hmap.h"
+#include "sset.h"
+
+/* OVN includes. */
+#include "lib/inc-proc-eng.h"
+#include "lib/ovn-nb-idl.h"
+#include "lib/ovn-sb-idl.h"
+#include "lib/ovn-util.h"
+
+/* Contains a NAT entry with the external addresses pre-parsed. */
+struct ovn_nat {
+    const struct nbrec_nat *nb;
+    struct lport_addresses ext_addrs;
+    struct ovs_list ext_addr_list_node; /* Linkage in the per-external IP
+                                         * list of nat entries. Currently
+                                         * only used for SNAT.
+                                         */
+};
+
+/* Stores the list of SNAT entries referencing a unique SNAT IP address.
+ * The 'snat_entries' list will be empty if the SNAT IP is used only for
+ * dnat_force_snat_ip or lb_force_snat_ip.
+ */
+struct ovn_snat_ip {
+    struct ovs_list snat_entries;
+};
+
+struct lr_nat_record {
+    struct hmap_node key_node;  /* Index on 'nbr->header_.uuid'. */
+
+    const struct ovn_datapath *od;
+
+    struct ovn_nat *nat_entries;
+    size_t n_nat_entries;
+
+    bool has_distributed_nat;
+
+    /* Set of nat external ips on the router. */
+    struct sset external_ips;
+
+    /* Set of nat external macs on the router. */
+    struct sset external_macs;
+
+    /* SNAT IPs owned by the router (shash of 'struct ovn_snat_ip'). */
+    struct shash snat_ips;
+
+    struct lport_addresses dnat_force_snat_addrs;
+    struct lport_addresses lb_force_snat_addrs;
+    bool lb_force_snat_router_ip;
+};
+
+struct lr_nat_tracked_data {
+    /* Created or updated logical router with NAT data. */
+    struct hmapx crupdated;
+};
+
+struct lr_nat_table {
+    struct hmap entries; /* Stores struct lr_nat_record. */
+
+    /* The array index of each element in 'entries'. */
+    struct lr_nat_record **array;
+};
+
+const struct lr_nat_record * lr_nat_table_find_by_index(
+    const struct lr_nat_table *, size_t od_index);
+
+struct ed_type_lr_nat_data {
+    struct lr_nat_table lr_nats;
+
+    struct lr_nat_tracked_data trk_data;
+};
+
+void *en_lr_nat_init(struct engine_node *, struct engine_arg *);
+void en_lr_nat_cleanup(void *data);
+void en_lr_nat_clear_tracked_data(void *data);
+void en_lr_nat_run(struct engine_node *, void *data);
+
+bool lr_nat_logical_router_handler(struct engine_node *, void *data);
+bool lr_nat_northd_handler(struct engine_node *, void *data);
+
+/* Returns true if a 'nat_entry' is valid, i.e.:
+ * - parsing was successful.
+ * - the string yielded exactly one IPv4 address or exactly one IPv6 address.
+ */
+static inline bool
+nat_entry_is_valid(const struct ovn_nat *nat_entry)
+{
+    const struct lport_addresses *ext_addrs = &nat_entry->ext_addrs;
+
+    return (ext_addrs->n_ipv4_addrs == 1 && ext_addrs->n_ipv6_addrs == 0) ||
+        (ext_addrs->n_ipv4_addrs == 0 && ext_addrs->n_ipv6_addrs == 1);
+}
+
+static inline bool
+nat_entry_is_v6(const struct ovn_nat *nat_entry)
+{
+    return nat_entry->ext_addrs.n_ipv6_addrs > 0;
+}
+
+static inline bool
+lr_nat_has_tracked_data(struct lr_nat_tracked_data *trk_data) {
+    return !hmapx_is_empty(&trk_data->crupdated);
+}
+
+#endif /* EN_LR_NAT_H */
\ No newline at end of file
diff --git a/northd/en-northd.c b/northd/en-northd.c
index 677b2b1ab0..546397f3dc 100644
--- a/northd/en-northd.c
+++ b/northd/en-northd.c
@@ -209,6 +209,10 @@ northd_nb_logical_router_handler(struct engine_node *node,
         return false;
     }
 
+    if (northd_has_lr_nats_in_tracked_data(&nd->trk_data)) {
+        engine_set_node_state(node, EN_UPDATED);
+    }
+
     return true;
 }
 
diff --git a/northd/en-sync-sb.c b/northd/en-sync-sb.c
index 45be7ddbcb..11e12428f7 100644
--- a/northd/en-sync-sb.c
+++ b/northd/en-sync-sb.c
@@ -21,6 +21,7 @@
 #include "lib/svec.h"
 #include "openvswitch/util.h"
 
+#include "en-lr-nat.h"
 #include "en-sync-sb.h"
 #include "lib/inc-proc-eng.h"
 #include "lib/lb.h"
@@ -287,9 +288,10 @@ en_sync_to_sb_pb_run(struct engine_node *node, void *data OVS_UNUSED)
 {
     const struct engine_context *eng_ctx = engine_get_context();
     struct northd_data *northd_data = engine_get_input_data("northd", node);
-
+    struct ed_type_lr_nat_data *lr_nat_data =
+        engine_get_input_data("lr_nat", node);
     sync_pbs(eng_ctx->ovnsb_idl_txn, &northd_data->ls_ports,
-             &northd_data->lr_ports);
+             &northd_data->lr_ports, &lr_nat_data->lr_nats);
     engine_set_node_state(node, EN_UPDATED);
 }
 
diff --git a/northd/inc-proc-northd.c b/northd/inc-proc-northd.c
index 04df0b06c2..1f211b278e 100644
--- a/northd/inc-proc-northd.c
+++ b/northd/inc-proc-northd.c
@@ -31,6 +31,7 @@
 #include "openvswitch/vlog.h"
 #include "inc-proc-northd.h"
 #include "en-lb-data.h"
+#include "en-lr-nat.h"
 #include "en-northd.h"
 #include "en-lflow.h"
 #include "en-northd-output.h"
@@ -146,6 +147,7 @@ static ENGINE_NODE(fdb_aging_waker, "fdb_aging_waker");
 static ENGINE_NODE(sync_to_sb_lb, "sync_to_sb_lb");
 static ENGINE_NODE(sync_to_sb_pb, "sync_to_sb_pb");
 static ENGINE_NODE_WITH_CLEAR_TRACK_DATA(lb_data, "lb_data");
+static ENGINE_NODE_WITH_CLEAR_TRACK_DATA(lr_nat, "lr_nat");
 
 void inc_proc_northd_init(struct ovsdb_idl_loop *nb,
                           struct ovsdb_idl_loop *sb)
@@ -189,6 +191,8 @@ void inc_proc_northd_init(struct ovsdb_idl_loop *nb,
                      northd_nb_logical_router_handler);
     engine_add_input(&en_northd, &en_lb_data, northd_lb_data_handler);
 
+    engine_add_input(&en_lr_nat, &en_northd, lr_nat_northd_handler);
+
     engine_add_input(&en_mac_binding_aging, &en_nb_nb_global, NULL);
     engine_add_input(&en_mac_binding_aging, &en_sb_mac_binding, NULL);
     engine_add_input(&en_mac_binding_aging, &en_northd, NULL);
@@ -212,6 +216,7 @@ void inc_proc_northd_init(struct ovsdb_idl_loop *nb,
     engine_add_input(&en_lflow, &en_sb_igmp_group, NULL);
     engine_add_input(&en_lflow, &en_northd, lflow_northd_handler);
     engine_add_input(&en_lflow, &en_port_group, lflow_port_group_handler);
+    engine_add_input(&en_lflow, &en_lr_nat, NULL);
 
     engine_add_input(&en_sync_to_sb_addr_set, &en_nb_address_set,
                      sync_to_sb_addr_set_nb_address_set_handler);
@@ -235,6 +240,7 @@ void inc_proc_northd_init(struct ovsdb_idl_loop *nb,
 
     engine_add_input(&en_sync_to_sb_pb, &en_northd,
                      sync_to_sb_pb_northd_handler);
+    engine_add_input(&en_sync_to_sb_pb, &en_lr_nat, NULL);
 
     /* en_sync_to_sb engine node syncs the SB database tables from
      * the NB database tables.
diff --git a/northd/northd.c b/northd/northd.c
index 23f2dae26b..e5e86326e3 100644
--- a/northd/northd.c
+++ b/northd/northd.c
@@ -44,6 +44,7 @@
 #include "memory.h"
 #include "northd.h"
 #include "en-lb-data.h"
+#include "en-lr-nat.h"
 #include "lib/ovn-parallel-hmap.h"
 #include "ovn/actions.h"
 #include "ovn/features.h"
@@ -556,184 +557,6 @@ ovn_mcast_group_allocate_key(struct mcast_info *mcast_info)
                               &mcast_info->group_tnlid_hint);
 }
 
-/* Contains a NAT entry with the external addresses pre-parsed. */
-struct ovn_nat {
-    const struct nbrec_nat *nb;
-    struct lport_addresses ext_addrs;
-    struct ovs_list ext_addr_list_node; /* Linkage in the per-external IP
-                                         * list of nat entries. Currently
-                                         * only used for SNAT.
-                                         */
-};
-
-/* Stores the list of SNAT entries referencing a unique SNAT IP address.
- * The 'snat_entries' list will be empty if the SNAT IP is used only for
- * dnat_force_snat_ip or lb_force_snat_ip.
- */
-struct ovn_snat_ip {
-    struct ovs_list snat_entries;
-};
-
-static bool
-get_force_snat_ip(struct ovn_datapath *od, const char *key_type,
-                  struct lport_addresses *laddrs);
-
-/* Returns true if a 'nat_entry' is valid, i.e.:
- * - parsing was successful.
- * - the string yielded exactly one IPv4 address or exactly one IPv6 address.
- */
-static bool
-nat_entry_is_valid(const struct ovn_nat *nat_entry)
-{
-    const struct lport_addresses *ext_addrs = &nat_entry->ext_addrs;
-
-    return (ext_addrs->n_ipv4_addrs == 1 && ext_addrs->n_ipv6_addrs == 0) ||
-        (ext_addrs->n_ipv4_addrs == 0 && ext_addrs->n_ipv6_addrs == 1);
-}
-
-static bool
-nat_entry_is_v6(const struct ovn_nat *nat_entry)
-{
-    return nat_entry->ext_addrs.n_ipv6_addrs > 0;
-}
-
-static void
-snat_ip_add(struct ovn_datapath *od, const char *ip, struct ovn_nat *nat_entry)
-{
-    struct ovn_snat_ip *snat_ip = shash_find_data(&od->snat_ips, ip);
-
-    if (!snat_ip) {
-        snat_ip = xzalloc(sizeof *snat_ip);
-        ovs_list_init(&snat_ip->snat_entries);
-        shash_add(&od->snat_ips, ip, snat_ip);
-    }
-
-    if (nat_entry) {
-        ovs_list_push_back(&snat_ip->snat_entries,
-                           &nat_entry->ext_addr_list_node);
-    }
-}
-
-static void
-init_nat_entries(struct ovn_datapath *od)
-{
-    ovs_assert(od->nbr);
-
-    shash_init(&od->snat_ips);
-    if (get_force_snat_ip(od, "dnat", &od->dnat_force_snat_addrs)) {
-        if (od->dnat_force_snat_addrs.n_ipv4_addrs) {
-            snat_ip_add(od, od->dnat_force_snat_addrs.ipv4_addrs[0].addr_s,
-                        NULL);
-        }
-        if (od->dnat_force_snat_addrs.n_ipv6_addrs) {
-            snat_ip_add(od, od->dnat_force_snat_addrs.ipv6_addrs[0].addr_s,
-                        NULL);
-        }
-    }
-
-    /* Check if 'lb_force_snat_ip' is configured with 'router_ip'. */
-    const char *lb_force_snat =
-        smap_get(&od->nbr->options, "lb_force_snat_ip");
-    if (lb_force_snat && !strcmp(lb_force_snat, "router_ip")
-            && smap_get(&od->nbr->options, "chassis")) {
-        /* Set it to true only if its gateway router and
-         * options:lb_force_snat_ip=router_ip. */
-        od->lb_force_snat_router_ip = true;
-    } else {
-        od->lb_force_snat_router_ip = false;
-
-        /* Check if 'lb_force_snat_ip' is configured with a set of
-         * IP address(es). */
-        if (get_force_snat_ip(od, "lb", &od->lb_force_snat_addrs)) {
-            if (od->lb_force_snat_addrs.n_ipv4_addrs) {
-                snat_ip_add(od, od->lb_force_snat_addrs.ipv4_addrs[0].addr_s,
-                            NULL);
-            }
-            if (od->lb_force_snat_addrs.n_ipv6_addrs) {
-                snat_ip_add(od, od->lb_force_snat_addrs.ipv6_addrs[0].addr_s,
-                            NULL);
-            }
-        }
-    }
-
-    if (!od->nbr->n_nat) {
-        return;
-    }
-
-    od->nat_entries = xmalloc(od->nbr->n_nat * sizeof *od->nat_entries);
-
-    for (size_t i = 0; i < od->nbr->n_nat; i++) {
-        const struct nbrec_nat *nat = od->nbr->nat[i];
-        struct ovn_nat *nat_entry = &od->nat_entries[i];
-
-        nat_entry->nb = nat;
-        if (!extract_ip_addresses(nat->external_ip,
-                                  &nat_entry->ext_addrs) ||
-                !nat_entry_is_valid(nat_entry)) {
-            static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(5, 1);
-
-            VLOG_WARN_RL(&rl,
-                         "Bad ip address %s in nat configuration "
-                         "for router %s", nat->external_ip, od->nbr->name);
-            continue;
-        }
-
-        /* If this is a SNAT rule add the IP to the set of unique SNAT IPs. */
-        if (!strcmp(nat->type, "snat")) {
-            if (!nat_entry_is_v6(nat_entry)) {
-                snat_ip_add(od, nat_entry->ext_addrs.ipv4_addrs[0].addr_s,
-                            nat_entry);
-            } else {
-                snat_ip_add(od, nat_entry->ext_addrs.ipv6_addrs[0].addr_s,
-                            nat_entry);
-            }
-        }
-
-        if (!strcmp(nat->type, "dnat_and_snat")
-            && nat->logical_port && nat->external_mac) {
-            od->has_distributed_nat = true;
-        }
-    }
-    od->n_nat_entries = od->nbr->n_nat;
-}
-
-static void
-destroy_nat_entries(struct ovn_datapath *od)
-{
-    if (!od->nbr) {
-        return;
-    }
-
-    shash_destroy_free_data(&od->snat_ips);
-    destroy_lport_addresses(&od->dnat_force_snat_addrs);
-    destroy_lport_addresses(&od->lb_force_snat_addrs);
-
-    for (size_t i = 0; i < od->n_nat_entries; i++) {
-        destroy_lport_addresses(&od->nat_entries[i].ext_addrs);
-    }
-}
-
-static void
-init_router_external_ips(struct ovn_datapath *od)
-{
-    ovs_assert(od->nbr);
-
-    sset_init(&od->external_ips);
-    for (size_t i = 0; i < od->nbr->n_nat; i++) {
-        sset_add(&od->external_ips, od->nbr->nat[i]->external_ip);
-    }
-}
-
-static void
-destroy_router_external_ips(struct ovn_datapath *od)
-{
-    if (!od->nbr) {
-        return;
-    }
-
-    sset_destroy(&od->external_ips);
-}
-
 static bool
 lb_has_vip(const struct nbrec_load_balancer *lb)
 {
@@ -854,10 +677,7 @@ ovn_datapath_destroy(struct hmap *datapaths, struct ovn_datapath *od)
         destroy_ipam_info(&od->ipam_info);
         free(od->router_ports);
         free(od->ls_peers);
-        destroy_nat_entries(od);
-        destroy_router_external_ips(od);
         destroy_lb_for_datapath(od);
-        free(od->nat_entries);
         free(od->localnet_ports);
         free(od->l3dgw_ports);
         destroy_mcast_info_for_datapath(od);
@@ -874,8 +694,8 @@ ovn_datapath_get_type(const struct ovn_datapath *od)
 }
 
 static struct ovn_datapath *
-ovn_datapath_find(const struct hmap *datapaths,
-                  const struct uuid *uuid)
+ovn_datapath_find_(const struct hmap *datapaths,
+                   const struct uuid *uuid)
 {
     struct ovn_datapath *od;
 
@@ -887,6 +707,13 @@ ovn_datapath_find(const struct hmap *datapaths,
     return NULL;
 }
 
+const struct ovn_datapath *
+ovn_datapath_find(const struct hmap *datapaths,
+                  const struct uuid *uuid)
+{
+    return ovn_datapath_find_(datapaths, uuid);
+}
+
 static struct ovn_datapath *
 ovn_datapath_find_by_key(struct hmap *datapaths, uint32_t dp_key)
 {
@@ -925,7 +752,7 @@ ovn_datapath_from_sbrec(const struct hmap *ls_datapaths,
     if (!dps) {
         return NULL;
     }
-    struct ovn_datapath *od = ovn_datapath_find(dps, &key);
+    struct ovn_datapath *od = ovn_datapath_find_(dps, &key);
     if (od && (od->sb == sb)) {
         return od;
     }
@@ -1213,7 +1040,7 @@ join_datapaths(const struct nbrec_logical_switch_table *nbrec_ls_table,
             continue;
         }
 
-        if (ovn_datapath_find(datapaths, &key)) {
+        if (ovn_datapath_find_(datapaths, &key)) {
             static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(5, 1);
             VLOG_INFO_RL(
                 &rl, "deleting Datapath_Binding "UUID_FMT" with "
@@ -1230,8 +1057,8 @@ join_datapaths(const struct nbrec_logical_switch_table *nbrec_ls_table,
 
     const struct nbrec_logical_switch *nbs;
     NBREC_LOGICAL_SWITCH_TABLE_FOR_EACH (nbs, nbrec_ls_table) {
-        struct ovn_datapath *od = ovn_datapath_find(datapaths,
-                                                    &nbs->header_.uuid);
+        struct ovn_datapath *od = ovn_datapath_find_(datapaths,
+                                                     &nbs->header_.uuid);
         if (od) {
             od->nbs = nbs;
             ovs_list_remove(&od->list);
@@ -1254,8 +1081,8 @@ join_datapaths(const struct nbrec_logical_switch_table *nbrec_ls_table,
             continue;
         }
 
-        struct ovn_datapath *od = ovn_datapath_find(datapaths,
-                                                    &nbr->header_.uuid);
+        struct ovn_datapath *od = ovn_datapath_find_(datapaths,
+                                                     &nbr->header_.uuid);
         if (od) {
             if (!od->nbs) {
                 od->nbr = nbr;
@@ -1276,8 +1103,6 @@ join_datapaths(const struct nbrec_logical_switch_table *nbrec_ls_table,
             ovs_list_push_back(nb_only, &od->list);
         }
         init_mcast_info_for_datapath(od);
-        init_nat_entries(od);
-        init_router_external_ips(od);
         init_lb_for_datapath(od);
         if (smap_get(&od->nbr->options, "chassis")) {
             od->is_gw_router = true;
@@ -1361,12 +1186,6 @@ ovn_datapath_assign_requested_tnl_id(
     }
 }
 
-static inline size_t
-ods_size(const struct ovn_datapaths *datapaths)
-{
-    return hmap_count(&datapaths->datapaths);
-}
-
 static void
 ods_build_array_index(struct ovn_datapaths *datapaths)
 {
@@ -4859,7 +4678,7 @@ sync_pb_for_lsp(struct ovn_port *op)
  * Caller should make sure that the OVN SB IDL txn is not NULL.  Presently it
  * only sets the port binding options column for the router ports */
 static void
-sync_pb_for_lrp(struct ovn_port *op)
+sync_pb_for_lrp(struct ovn_port *op, const struct lr_nat_table *lr_nats)
 {
     ovs_assert(op->nbrp);
 
@@ -4868,10 +4687,14 @@ sync_pb_for_lrp(struct ovn_port *op)
 
     const char *chassis_name = smap_get(&op->od->nbr->options, "chassis");
     if (is_cr_port(op)) {
+        const struct lr_nat_record *lrnat_rec =
+            lr_nat_table_find_by_index(lr_nats, op->od->index);
+        ovs_assert(lrnat_rec);
+
         smap_add(&new, "distributed-port", op->nbrp->name);
 
         bool always_redirect =
-            !op->od->has_distributed_nat &&
+            !lrnat_rec->has_distributed_nat &&
             !l3dgw_port_has_associated_vtep_lports(op->l3dgw_port);
 
         const char *redirect_type = smap_get(&op->nbrp->options,
@@ -4921,7 +4744,7 @@ static void ovn_update_ipv6_opt_for_op(struct ovn_port *op);
  * the logical switch ports. */
 void
 sync_pbs(struct ovsdb_idl_txn *ovnsb_idl_txn, struct hmap *ls_ports,
-         struct hmap *lr_ports)
+         struct hmap *lr_ports, const struct lr_nat_table *lr_nats)
 {
     ovs_assert(ovnsb_idl_txn);
 
@@ -4931,7 +4754,7 @@ sync_pbs(struct ovsdb_idl_txn *ovnsb_idl_txn, struct hmap *ls_ports,
     }
 
     HMAP_FOR_EACH (op, key_node, lr_ports) {
-        sync_pb_for_lrp(op);
+        sync_pb_for_lrp(op, lr_nats);
     }
 
     ovn_update_ipv6_options(lr_ports);
@@ -4940,7 +4763,7 @@ sync_pbs(struct ovsdb_idl_txn *ovnsb_idl_txn, struct hmap *ls_ports,
 /* Sync the SB Port bindings for the added and updated logical switch ports
  * of the tracked northd engine data. */
 bool
-sync_pbs_for_northd_changed_ovn_ports( struct tracked_ovn_ports *trk_ovn_ports)
+sync_pbs_for_northd_changed_ovn_ports(struct tracked_ovn_ports *trk_ovn_ports)
 {
     struct hmapx_node *hmapx_node;
     struct ovn_port *op;
@@ -5192,6 +5015,7 @@ destroy_northd_data_tracked_changes(struct northd_data *nd)
     struct northd_tracked_data *trk_changes = &nd->trk_data;
     destroy_tracked_ovn_ports(&trk_changes->trk_lsps);
     destroy_tracked_lbs(&trk_changes->trk_lbs);
+    hmapx_clear(&trk_changes->lr_with_changed_nats);
     nd->trk_data.type = NORTHD_TRACKED_NONE;
 }
 
@@ -5205,6 +5029,7 @@ init_northd_tracked_data(struct northd_data *nd)
     hmapx_init(&trk_data->trk_lsps.deleted);
     hmapx_init(&trk_data->trk_lbs.crupdated);
     hmapx_init(&trk_data->trk_lbs.deleted);
+    hmapx_init(&trk_data->lr_with_changed_nats);
 }
 
 static void
@@ -5217,6 +5042,7 @@ destroy_northd_tracked_data(struct northd_data *nd)
     hmapx_destroy(&trk_data->trk_lsps.deleted);
     hmapx_destroy(&trk_data->trk_lbs.crupdated);
     hmapx_destroy(&trk_data->trk_lbs.deleted);
+    hmapx_destroy(&trk_data->lr_with_changed_nats);
 }
 
 /* Check if a changed LSP can be handled incrementally within the I-P engine
@@ -5577,7 +5403,7 @@ northd_handle_ls_changes(struct ovsdb_idl_txn *ovnsb_idl_txn,
             nbrec_logical_switch_is_deleted(changed_ls)) {
             goto fail;
         }
-        struct ovn_datapath *od = ovn_datapath_find(
+        struct ovn_datapath *od = ovn_datapath_find_(
                                     &nd->ls_datapaths.datapaths,
                                     &changed_ls->header_.uuid);
         if (!od) {
@@ -5616,6 +5442,7 @@ fail:
  * incrementally handled.
  * Presently supports i-p for the below changes:
  *    - load balancers and load balancer groups.
+ *    - NAT changes
  */
 static bool
 lr_changes_can_be_handled(
@@ -5625,8 +5452,9 @@ lr_changes_can_be_handled(
     enum nbrec_logical_router_column_id col;
     for (col = 0; col < NBREC_LOGICAL_ROUTER_N_COLUMNS; col++) {
         if (nbrec_logical_router_is_updated(lr, col)) {
-            if (col == NBREC_LOGICAL_ROUTER_COL_LOAD_BALANCER ||
-                col == NBREC_LOGICAL_ROUTER_COL_LOAD_BALANCER_GROUP) {
+            if (col == NBREC_LOGICAL_ROUTER_COL_LOAD_BALANCER
+                || col == NBREC_LOGICAL_ROUTER_COL_LOAD_BALANCER_GROUP
+                || col == NBREC_LOGICAL_ROUTER_COL_NAT) {
                 continue;
             }
             return false;
@@ -5645,12 +5473,6 @@ lr_changes_can_be_handled(
                                 OVSDB_IDL_CHANGE_MODIFY) > 0) {
         return false;
     }
-    for (size_t i = 0; i < lr->n_nat; i++) {
-        if (nbrec_nat_row_get_seqno(lr->nat[i],
-                                OVSDB_IDL_CHANGE_MODIFY) > 0) {
-            return false;
-        }
-    }
     for (size_t i = 0; i < lr->n_policies; i++) {
         if (nbrec_logical_router_policy_row_get_seqno(lr->policies[i],
                                 OVSDB_IDL_CHANGE_MODIFY) > 0) {
@@ -5666,6 +5488,39 @@ lr_changes_can_be_handled(
     return true;
 }
 
+static bool
+is_lr_nats_seqno_changed(const struct nbrec_logical_router *nbr)
+{
+    for (size_t i = 0; i < nbr->n_nat; i++) {
+        if (nbrec_nat_row_get_seqno(nbr->nat[i],
+                                    OVSDB_IDL_CHANGE_MODIFY) > 0) {
+            return true;
+        }
+    }
+
+    return false;
+}
+
+static bool
+is_lr_nats_changed(const struct nbrec_logical_router *nbr) {
+    return (nbrec_logical_router_is_updated(nbr,
+                                            NBREC_LOGICAL_ROUTER_COL_NAT)
+            || nbrec_logical_router_is_updated(
+                nbr, NBREC_LOGICAL_ROUTER_COL_OPTIONS)
+            || is_lr_nats_seqno_changed(nbr));
+}
+
+static bool
+lr_has_routable_nats(const struct nbrec_logical_router *nbr) {
+    for (size_t i = 0; i < nbr->n_nat; i++) {
+        if (smap_get_bool(&nbr->nat[i]->options, "add_route", false)) {
+            return true;
+        }
+    }
+
+    return false;
+}
+
 /* Return true if changes are handled incrementally, false otherwise.
  *
  * Note: Changes to load balancer and load balancer groups associated with
@@ -5685,11 +5540,37 @@ northd_handle_lr_changes(const struct northd_input *ni,
             goto fail;
         }
 
-        /* Presently only able to handle load balancer and
-         * load balancer group changes. */
+        /* Presently only able to handle load balancer,
+         * load balancer group changes and NAT changes. */
         if (!lr_changes_can_be_handled(changed_lr)) {
             goto fail;
         }
+
+        if (is_lr_nats_changed(changed_lr)) {
+            if (lr_has_routable_nats(changed_lr)) {
+                /* router has routable NATs.  We can't handle these changes
+                 * incrementally yet.  Fall back to recompute. */
+                goto fail;
+            }
+
+            struct ovn_datapath *od = ovn_datapath_find_(
+                                    &nd->lr_datapaths.datapaths,
+                                    &changed_lr->header_.uuid);
+
+            if (!od) {
+                static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(1, 1);
+                VLOG_WARN_RL(&rl, "Internal error: a tracked updated LR "
+                            "doesn't exist in lr_datapaths: "UUID_FMT,
+                            UUID_ARGS(&changed_lr->header_.uuid));
+                goto fail;
+            }
+
+            hmapx_add(&nd->trk_data.lr_with_changed_nats, od);
+        }
+    }
+
+    if (!hmapx_is_empty(&nd->trk_data.lr_with_changed_nats)) {
+        nd->trk_data.type |= NORTHD_TRACKED_LR_NATS;
     }
 
     return true;
@@ -5907,7 +5788,7 @@ northd_handle_lb_data_changes(struct tracked_lb_data *trk_lb_data,
 
     struct crupdated_od_lb_data *codlb;
     LIST_FOR_EACH (codlb, list_node, &trk_lb_data->crupdated_ls_lbs) {
-        od = ovn_datapath_find(&ls_datapaths->datapaths, &codlb->od_uuid);
+        od = ovn_datapath_find_(&ls_datapaths->datapaths, &codlb->od_uuid);
         ovs_assert(od);
 
         struct uuidset_node *uuidnode;
@@ -5944,7 +5825,7 @@ northd_handle_lb_data_changes(struct tracked_lb_data *trk_lb_data,
     }
 
     LIST_FOR_EACH (codlb, list_node, &trk_lb_data->crupdated_lr_lbs) {
-        od = ovn_datapath_find(&lr_datapaths->datapaths, &codlb->od_uuid);
+        od = ovn_datapath_find_(&lr_datapaths->datapaths, &codlb->od_uuid);
         ovs_assert(od);
 
         struct uuidset_node *uuidnode;
@@ -9291,31 +9172,15 @@ static void
 build_lswitch_rport_arp_req_self_orig_flow(struct ovn_port *op,
                                            uint32_t priority,
                                            struct ovn_datapath *od,
+                                           const struct lr_nat_table *lr_nats,
                                            struct hmap *lflows)
 {
-    struct sset all_eth_addrs = SSET_INITIALIZER(&all_eth_addrs);
     struct ds eth_src = DS_EMPTY_INITIALIZER;
     struct ds match = DS_EMPTY_INITIALIZER;
 
-    sset_add(&all_eth_addrs, op->lrp_networks.ea_s);
-
-    for (size_t i = 0; i < op->od->nbr->n_nat; i++) {
-        struct ovn_nat *nat_entry = &op->od->nat_entries[i];
-        const struct nbrec_nat *nat = nat_entry->nb;
-
-        if (!nat_entry_is_valid(nat_entry)) {
-            continue;
-        }
-
-        if (!strcmp(nat->type, "snat")) {
-            continue;
-        }
-
-        if (!nat->external_mac) {
-            continue;
-        }
-        sset_add(&all_eth_addrs, nat->external_mac);
-    }
+    const struct lr_nat_record *lrnat_rec = lr_nat_table_find_by_index(
+            lr_nats, op->od->index);
+    ovs_assert(lrnat_rec);
 
     /* Self originated ARP requests/RARP/ND need to be flooded to the L2 domain
      * (except on router ports).  Determine that packets are self originated
@@ -9325,8 +9190,8 @@ build_lswitch_rport_arp_req_self_orig_flow(struct ovn_port *op,
      */
     const char *eth_addr;
 
-    ds_put_cstr(&eth_src, "{");
-    SSET_FOR_EACH (eth_addr, &all_eth_addrs) {
+    ds_put_format(&eth_src, "{%s, ", op->lrp_networks.ea_s);
+    SSET_FOR_EACH (eth_addr, &lrnat_rec->external_macs) {
         ds_put_format(&eth_src, "%s, ", eth_addr);
     }
     ds_chomp(&eth_src, ' ');
@@ -9339,7 +9204,6 @@ build_lswitch_rport_arp_req_self_orig_flow(struct ovn_port *op,
     ovn_lflow_add(lflows, od, S_SWITCH_IN_L2_LKUP, priority, ds_cstr(&match),
                   "outport = \""MC_FLOOD_L2"\"; output;");
 
-    sset_destroy(&all_eth_addrs);
     ds_destroy(&eth_src);
     ds_destroy(&match);
 }
@@ -9445,6 +9309,7 @@ static void
 build_lswitch_rport_arp_req_flows(struct ovn_port *op,
                                   struct ovn_datapath *sw_od,
                                   struct ovn_port *sw_op,
+                                  const struct lr_nat_table *lr_nats,
                                   struct hmap *lflows,
                                   const struct ovsdb_idl_row *stage_hint)
 {
@@ -9489,8 +9354,38 @@ build_lswitch_rport_arp_req_flows(struct ovn_port *op,
         }
     }
 
-    for (size_t i = 0; i < op->od->nbr->n_nat; i++) {
-        struct ovn_nat *nat_entry = &op->od->nat_entries[i];
+    for (size_t i = 0; i < op->lrp_networks.n_ipv4_addrs; i++) {
+        build_lswitch_rport_arp_req_flow(
+            op->lrp_networks.ipv4_addrs[i].addr_s, AF_INET, sw_op, sw_od, 80,
+            lflows, stage_hint);
+    }
+    for (size_t i = 0; i < op->lrp_networks.n_ipv6_addrs; i++) {
+        build_lswitch_rport_arp_req_flow(
+            op->lrp_networks.ipv6_addrs[i].addr_s, AF_INET6, sw_op, sw_od, 80,
+            lflows, stage_hint);
+    }
+
+    /* Self originated ARP requests/RARP/ND need to be flooded as usual.
+     *
+     * However, if the switch doesn't have any non-router ports we shouldn't
+     * even try to flood.
+     *
+     * Priority: 75.
+     */
+    if (sw_od->n_router_ports != sw_od->nbs->n_ports) {
+        build_lswitch_rport_arp_req_self_orig_flow(op, 75, sw_od, lr_nats,
+                                                   lflows);
+    }
+
+    const struct lr_nat_record *lrnat_rec =
+        lr_nat_table_find_by_index(lr_nats, op->od->index);
+
+    if (!lrnat_rec) {
+        return;
+    }
+
+    for (size_t i = 0; i < lrnat_rec->n_nat_entries; i++) {
+        struct ovn_nat *nat_entry = &lrnat_rec->nat_entries[i];
         const struct nbrec_nat *nat = nat_entry->nb;
 
         if (!nat_entry_is_valid(nat_entry)) {
@@ -9520,7 +9415,7 @@ build_lswitch_rport_arp_req_flows(struct ovn_port *op,
     }
 
     struct shash_node *snat_snode;
-    SHASH_FOR_EACH (snat_snode, &op->od->snat_ips) {
+    SHASH_FOR_EACH (snat_snode, &lrnat_rec->snat_ips) {
         struct ovn_snat_ip *snat_ip = snat_snode->data;
 
         if (ovs_list_is_empty(&snat_ip->snat_entries)) {
@@ -9549,28 +9444,6 @@ build_lswitch_rport_arp_req_flows(struct ovn_port *op,
             }
         }
     }
-
-    for (size_t i = 0; i < op->lrp_networks.n_ipv4_addrs; i++) {
-        build_lswitch_rport_arp_req_flow(
-            op->lrp_networks.ipv4_addrs[i].addr_s, AF_INET, sw_op, sw_od, 80,
-            lflows, stage_hint);
-    }
-    for (size_t i = 0; i < op->lrp_networks.n_ipv6_addrs; i++) {
-        build_lswitch_rport_arp_req_flow(
-            op->lrp_networks.ipv6_addrs[i].addr_s, AF_INET6, sw_op, sw_od, 80,
-            lflows, stage_hint);
-    }
-
-    /* Self originated ARP requests/RARP/ND need to be flooded as usual.
-     *
-     * However, if the switch doesn't have any non-router ports we shouldn't
-     * even try to flood.
-     *
-     * Priority: 75.
-     */
-    if (sw_od->n_router_ports != sw_od->nbs->n_ports) {
-        build_lswitch_rport_arp_req_self_orig_flow(op, 75, sw_od, lflows);
-    }
 }
 
 static void
@@ -10604,6 +10477,7 @@ build_lswitch_ip_mcast_igmp_mld(struct ovn_igmp_group *igmp_group,
 /* Ingress table 25: Destination lookup, unicast handling (priority 50), */
 static void
 build_lswitch_ip_unicast_lookup(struct ovn_port *op,
+                                const struct lr_nat_table *lr_nats,
                                 struct hmap *lflows,
                                 struct ds *actions,
                                 struct ds *match)
@@ -10618,8 +10492,8 @@ build_lswitch_ip_unicast_lookup(struct ovn_port *op,
      * requests only to the router port that owns the IP address.
      */
     if (lsp_is_router(op->nbsp)) {
-        build_lswitch_rport_arp_req_flows(op->peer, op->od, op, lflows,
-                                          &op->nbsp->header_);
+        build_lswitch_rport_arp_req_flows(op->peer, op->od, op, lr_nats,
+                                          lflows, &op->nbsp->header_);
     }
 
     for (size_t i = 0; i < op->nbsp->n_addresses; i++) {
@@ -11982,27 +11856,6 @@ op_put_v6_networks(struct ds *ds, const struct ovn_port *op)
     ds_put_cstr(ds, "}");
 }
 
-static bool
-get_force_snat_ip(struct ovn_datapath *od, const char *key_type,
-                  struct lport_addresses *laddrs)
-{
-    char *key = xasprintf("%s_force_snat_ip", key_type);
-    const char *addresses = smap_get(&od->nbr->options, key);
-    free(key);
-
-    if (!addresses) {
-        return false;
-    }
-
-    if (!extract_ip_address(addresses, laddrs)) {
-        static struct vlog_rate_limit rl = VLOG_RATE_LIMIT_INIT(5, 1);
-        VLOG_WARN_RL(&rl, "bad ip %s in options of router "UUID_FMT"",
-                     addresses, UUID_ARGS(&od->key));
-        return false;
-    }
-
-    return true;
-}
 
 enum lrouter_nat_lb_flow_type {
     LROUTER_NAT_LB_FLOW_NORMAL = 0,
@@ -12154,6 +12007,7 @@ build_lrouter_nat_flows_for_lb(struct ovn_lb_vip *lb_vip,
                                struct ovn_lb_datapaths *lb_dps,
                                struct ovn_northd_lb_vip *vips_nb,
                                const struct ovn_datapaths *lr_datapaths,
+                               const struct lr_nat_table *lr_nats,
                                struct hmap *lflows,
                                struct ds *match, struct ds *action,
                                const struct shash *meter_groups,
@@ -12259,10 +12113,13 @@ build_lrouter_nat_flows_for_lb(struct ovn_lb_vip *lb_vip,
         struct ovn_datapath *od = lr_datapaths->array[index];
         enum lrouter_nat_lb_flow_type type;
 
+        const struct lr_nat_record *lrnat_rec =
+            lr_nat_table_find_by_index(lr_nats, od->index);
+        ovs_assert(lrnat_rec);
         if (lb->skip_snat) {
             type = LROUTER_NAT_LB_FLOW_SKIP_SNAT;
-        } else if (!lport_addresses_is_empty(&od->lb_force_snat_addrs) ||
-                   od->lb_force_snat_router_ip) {
+        } else if (!lport_addresses_is_empty(&lrnat_rec->lb_force_snat_addrs)
+                   || lrnat_rec->lb_force_snat_router_ip) {
             type = LROUTER_NAT_LB_FLOW_FORCE_SNAT;
         } else {
             type = LROUTER_NAT_LB_FLOW_NORMAL;
@@ -12278,7 +12135,7 @@ build_lrouter_nat_flows_for_lb(struct ovn_lb_vip *lb_vip,
             bitmap_set1(aff_dp_bitmap[type], index);
         }
 
-        if (sset_contains(&od->external_ips, lb_vip->vip_str)) {
+        if (sset_contains(&lrnat_rec->external_ips, lb_vip->vip_str)) {
             /* The load balancer vip is also present in the NAT entries.
              * So add a high priority lflow to advance the the packet
              * destined to the vip (and the vip port if defined)
@@ -12408,6 +12265,7 @@ build_lrouter_flows_for_lb(struct ovn_lb_datapaths *lb_dps,
                            struct hmap *lflows,
                            const struct shash *meter_groups,
                            const struct ovn_datapaths *lr_datapaths,
+                           const struct lr_nat_table *lr_nats,
                            const struct chassis_features *features,
                            const struct hmap *svc_monitor_map,
                            struct ds *match, struct ds *action)
@@ -12423,8 +12281,8 @@ build_lrouter_flows_for_lb(struct ovn_lb_datapaths *lb_dps,
         struct ovn_lb_vip *lb_vip = &lb->vips[i];
 
         build_lrouter_nat_flows_for_lb(lb_vip, lb_dps, &lb->vips_nb[i],
-                                       lr_datapaths, lflows, match, action,
-                                       meter_groups, features,
+                                       lr_datapaths, lr_nats, lflows, match,
+                                       action, meter_groups, features,
                                        svc_monitor_map);
 
         if (!build_empty_lb_event_flow(lb_vip, lb, match, action)) {
@@ -12823,7 +12681,9 @@ build_lrouter_port_nat_arp_nd_flow(struct ovn_port *op,
 }
 
 static void
-build_lrouter_drop_own_dest(struct ovn_port *op, enum ovn_stage stage,
+build_lrouter_drop_own_dest(struct ovn_port *op,
+                            const struct lr_nat_record *lrnat_rec,
+                            enum ovn_stage stage,
                             uint16_t priority, bool drop_snat_ip,
                             struct hmap *lflows)
 {
@@ -12833,7 +12693,8 @@ build_lrouter_drop_own_dest(struct ovn_port *op, enum ovn_stage stage,
         for (size_t i = 0; i < op->lrp_networks.n_ipv4_addrs; i++) {
             const char *ip = op->lrp_networks.ipv4_addrs[i].addr_s;
 
-            bool router_ip_in_snat_ips = !!shash_find(&op->od->snat_ips, ip);
+            bool router_ip_in_snat_ips = !!shash_find(&lrnat_rec->snat_ips,
+                                                      ip);
             bool router_ip_in_lb_ips =
                     !!sset_find(&op->od->lb_ips->ips_v4, ip);
             bool drop_router_ip = (drop_snat_ip == (router_ip_in_snat_ips ||
@@ -12862,7 +12723,8 @@ build_lrouter_drop_own_dest(struct ovn_port *op, enum ovn_stage stage,
         for (size_t i = 0; i < op->lrp_networks.n_ipv6_addrs; i++) {
             const char *ip = op->lrp_networks.ipv6_addrs[i].addr_s;
 
-            bool router_ip_in_snat_ips = !!shash_find(&op->od->snat_ips, ip);
+            bool router_ip_in_snat_ips = !!shash_find(&lrnat_rec->snat_ips,
+                                                      ip);
             bool router_ip_in_lb_ips =
                     !!sset_find(&op->od->lb_ips->ips_v6, ip);
             bool drop_router_ip = (drop_snat_ip == (router_ip_in_snat_ips ||
@@ -12915,11 +12777,12 @@ build_lrouter_force_snat_flows(struct hmap *lflows, struct ovn_datapath *od,
 
 static void
 build_lrouter_force_snat_flows_op(struct ovn_port *op,
+                                  const struct lr_nat_record *lrnat_rec,
                                   struct hmap *lflows,
                                   struct ds *match, struct ds *actions)
 {
     ovs_assert(op->nbrp);
-    if (!op->peer || !op->od->lb_force_snat_router_ip) {
+    if (!op->peer || !lrnat_rec->lb_force_snat_router_ip) {
         return;
     }
 
@@ -13872,8 +13735,8 @@ routable_addresses_to_lflows(struct hmap *lflows, struct ovn_port *router_port,
 /* This function adds ARP resolve flows related to a LRP. */
 static void
 build_arp_resolve_flows_for_lrp(
-        struct ovn_port *op, struct hmap *lflows,
-        struct ds *match, struct ds *actions)
+        struct ovn_port *op, const struct lr_nat_record *lrnat_rec,
+        struct hmap *lflows, struct ds *match, struct ds *actions)
 {
     ovs_assert(op->nbrp);
     /* This is a logical router port. If next-hop IP address in
@@ -13949,8 +13812,8 @@ build_arp_resolve_flows_for_lrp(
      *
      * Priority 2.
      */
-    build_lrouter_drop_own_dest(op, S_ROUTER_IN_ARP_RESOLVE, 2, true,
-                                lflows);
+    build_lrouter_drop_own_dest(op, lrnat_rec, S_ROUTER_IN_ARP_RESOLVE, 2,
+                                true, lflows);
 }
 
 /* This function adds ARP resolve flows related to a LSP. */
@@ -14280,6 +14143,7 @@ build_check_pkt_len_flows_for_lrouter(
 static void
 build_gateway_redirect_flows_for_lrouter(
         struct ovn_datapath *od, struct hmap *lflows,
+        const struct lr_nat_table *lr_nats,
         struct ds *match, struct ds *actions)
 {
     ovs_assert(od->nbr);
@@ -14315,8 +14179,16 @@ build_gateway_redirect_flows_for_lrouter(
         ovn_lflow_add_with_hint(lflows, od, S_ROUTER_IN_GW_REDIRECT, 50,
                                 ds_cstr(match), ds_cstr(actions),
                                 stage_hint);
-        for (int j = 0; j < od->n_nat_entries; j++) {
-            const struct ovn_nat *nat = &od->nat_entries[j];
+
+        const struct lr_nat_record *lrnat_rec = lr_nat_table_find_by_index(
+            lr_nats, od->index);
+
+        if (!lrnat_rec) {
+            continue;
+        }
+
+        for (int j = 0; j < lrnat_rec->n_nat_entries; j++) {
+            const struct ovn_nat *nat = &lrnat_rec->nat_entries[j];
 
             if (!lrouter_dnat_and_snat_is_stateless(nat->nb) ||
                 (!nat->nb->allowed_ext_ips && !nat->nb->exempted_ext_ips)) {
@@ -14754,10 +14626,15 @@ build_ipv6_input_flows_for_lrouter_port(
 
 static void
 build_lrouter_arp_nd_for_datapath(struct ovn_datapath *od,
+                                  const struct lr_nat_table *lr_nats,
                                   struct hmap *lflows,
                                   const struct shash *meter_groups)
 {
     ovs_assert(od->nbr);
+    if (!od->nbr->n_nat) {
+        return;
+    }
+
     /* Priority-90-92 flows handle ARP requests and ND packets. Most are
      * per logical port but DNAT addresses can be handled per datapath
      * for non gateway router ports.
@@ -14766,8 +14643,12 @@ build_lrouter_arp_nd_for_datapath(struct ovn_datapath *od,
      * port to handle the special cases. In case we get the packet
      * on a regular port, just reply with the port's ETH address.
      */
-    for (int i = 0; i < od->nbr->n_nat; i++) {
-        struct ovn_nat *nat_entry = &od->nat_entries[i];
+    const struct lr_nat_record *lrnat_rec = lr_nat_table_find_by_index(
+        lr_nats, od->index);
+    ovs_assert(lrnat_rec);
+
+    for (int i = 0; i < lrnat_rec->n_nat_entries; i++) {
+        struct ovn_nat *nat_entry = &lrnat_rec->nat_entries[i];
 
         /* Skip entries we failed to parse. */
         if (!nat_entry_is_valid(nat_entry)) {
@@ -14775,8 +14656,8 @@ build_lrouter_arp_nd_for_datapath(struct ovn_datapath *od,
         }
 
         /* Skip SNAT entries for now, we handle unique SNAT IPs separately
-         * below.
-         */
+        * below.
+        */
         if (!strcmp(nat_entry->nb->type, "snat")) {
             continue;
         }
@@ -14785,7 +14666,7 @@ build_lrouter_arp_nd_for_datapath(struct ovn_datapath *od,
 
     /* Now handle SNAT entries too, one per unique SNAT IP. */
     struct shash_node *snat_snode;
-    SHASH_FOR_EACH (snat_snode, &od->snat_ips) {
+    SHASH_FOR_EACH (snat_snode, &lrnat_rec->snat_ips) {
         struct ovn_snat_ip *snat_ip = snat_snode->data;
 
         if (ovs_list_is_empty(&snat_ip->snat_entries)) {
@@ -14803,6 +14684,7 @@ build_lrouter_arp_nd_for_datapath(struct ovn_datapath *od,
 static void
 build_lrouter_ipv4_ip_input(struct ovn_port *op,
                             struct hmap *lflows,
+                            const struct lr_nat_record *lrnat_rec,
                             struct ds *match, struct ds *actions,
                             const struct shash *meter_groups)
 {
@@ -15039,14 +14921,14 @@ build_lrouter_ipv4_ip_input(struct ovn_port *op,
      * also a SNAT IP. Those are dropped later, in stage
      * "lr_in_arp_resolve", if unSNAT was unsuccessful.
      *
-     * If op->od->lb_force_snat_router_ip is true, it means the IP of the
+     * If lrnat_rec->lb_force_snat_router_ip is true, it means the IP of the
      * router port is also SNAT IP.
      *
      * Priority 60.
      */
-    if (!op->od->lb_force_snat_router_ip) {
-        build_lrouter_drop_own_dest(op, S_ROUTER_IN_IP_INPUT, 60, false,
-                                    lflows);
+    if (!lrnat_rec->lb_force_snat_router_ip) {
+        build_lrouter_drop_own_dest(op, lrnat_rec, S_ROUTER_IN_IP_INPUT, 60,
+                                    false, lflows);
     }
     /* ARP / ND handling for external IP addresses.
      *
@@ -15061,8 +14943,8 @@ build_lrouter_ipv4_ip_input(struct ovn_port *op,
         return;
     }
 
-    for (size_t i = 0; i < op->od->nbr->n_nat; i++) {
-        struct ovn_nat *nat_entry = &op->od->nat_entries[i];
+    for (int i = 0; i < lrnat_rec->n_nat_entries; i++) {
+        struct ovn_nat *nat_entry = &lrnat_rec->nat_entries[i];
 
         /* Skip entries we failed to parse. */
         if (!nat_entry_is_valid(nat_entry)) {
@@ -15070,18 +14952,18 @@ build_lrouter_ipv4_ip_input(struct ovn_port *op,
         }
 
         /* Skip SNAT entries for now, we handle unique SNAT IPs separately
-         * below.
-         */
+        * below.
+        */
         if (!strcmp(nat_entry->nb->type, "snat")) {
             continue;
         }
         build_lrouter_port_nat_arp_nd_flow(op, nat_entry, lflows,
-                                           meter_groups);
+                                        meter_groups);
     }
 
     /* Now handle SNAT entries too, one per unique SNAT IP. */
     struct shash_node *snat_snode;
-    SHASH_FOR_EACH (snat_snode, &op->od->snat_ips) {
+    SHASH_FOR_EACH (snat_snode, &lrnat_rec->snat_ips) {
         struct ovn_snat_ip *snat_ip = snat_snode->data;
 
         if (ovs_list_is_empty(&snat_ip->snat_entries)) {
@@ -15090,9 +14972,9 @@ build_lrouter_ipv4_ip_input(struct ovn_port *op,
 
         struct ovn_nat *nat_entry =
             CONTAINER_OF(ovs_list_front(&snat_ip->snat_entries),
-                         struct ovn_nat, ext_addr_list_node);
+                        struct ovn_nat, ext_addr_list_node);
         build_lrouter_port_nat_arp_nd_flow(op, nat_entry, lflows,
-                                           meter_groups);
+                                        meter_groups);
     }
 }
 
@@ -15201,6 +15083,7 @@ build_lrouter_in_unsnat_flow(struct hmap *lflows, struct ovn_datapath *od,
 
 static void
 build_lrouter_in_dnat_flow(struct hmap *lflows, struct ovn_datapath *od,
+                           const struct lr_nat_record *lrnat_rec,
                            const struct nbrec_nat *nat, struct ds *match,
                            struct ds *actions, bool distributed_nat,
                            int cidr_bits, bool is_v6,
@@ -15224,7 +15107,7 @@ build_lrouter_in_dnat_flow(struct hmap *lflows, struct ovn_datapath *od,
                   nat->external_ip);
 
     if (od->is_gw_router) {
-        if (!lport_addresses_is_empty(&od->dnat_force_snat_addrs)) {
+        if (!lport_addresses_is_empty(&lrnat_rec->dnat_force_snat_addrs)) {
             /* Indicate to the future tables that a DNAT has taken
              * place and a force SNAT needs to be done in the
              * Egress SNAT table. */
@@ -15780,6 +15663,7 @@ static void
 build_lrouter_nat_defrag_and_lb(struct ovn_datapath *od, struct hmap *lflows,
                                 const struct hmap *ls_ports,
                                 const struct hmap *lr_ports,
+                                const struct lr_nat_table *lr_nats,
                                 struct ds *match,
                                 struct ds *actions,
                                 const struct shash *meter_groups,
@@ -15890,14 +15774,18 @@ build_lrouter_nat_defrag_and_lb(struct ovn_datapath *od, struct hmap *lflows,
     }
 
     struct sset nat_entries = SSET_INITIALIZER(&nat_entries);
+    const struct lr_nat_record *lrnat_rec = lr_nat_table_find_by_index(lr_nats,
+                                                                    od->index);
+    ovs_assert(lrnat_rec);
 
     bool dnat_force_snat_ip =
-        !lport_addresses_is_empty(&od->dnat_force_snat_addrs);
+        !lport_addresses_is_empty(&lrnat_rec->dnat_force_snat_addrs);
     bool lb_force_snat_ip =
-        !lport_addresses_is_empty(&od->lb_force_snat_addrs);
+        !lport_addresses_is_empty(&lrnat_rec->lb_force_snat_addrs);
 
-    for (int i = 0; i < od->nbr->n_nat; i++) {
-        const struct nbrec_nat *nat = od->nbr->nat[i];
+    for (int i = 0; i < lrnat_rec->n_nat_entries; i++) {
+        struct ovn_nat *nat_entry = &lrnat_rec->nat_entries[i];
+        const struct nbrec_nat *nat = nat_entry->nb;
         struct eth_addr mac = eth_addr_broadcast;
         bool is_v6, distributed_nat;
         ovs_be32 mask;
@@ -15935,7 +15823,7 @@ build_lrouter_nat_defrag_and_lb(struct ovn_datapath *od, struct hmap *lflows,
                                          distributed_nat, is_v6, l3dgw_port);
         }
         /* S_ROUTER_IN_DNAT */
-        build_lrouter_in_dnat_flow(lflows, od, nat, match, actions,
+        build_lrouter_in_dnat_flow(lflows, od, lrnat_rec, nat, match, actions,
                                    distributed_nat, cidr_bits, is_v6,
                                    l3dgw_port, stateless);
 
@@ -16144,25 +16032,25 @@ build_lrouter_nat_defrag_and_lb(struct ovn_datapath *od, struct hmap *lflows,
     /* Handle force SNAT options set in the gateway router. */
     if (od->is_gw_router) {
         if (dnat_force_snat_ip) {
-            if (od->dnat_force_snat_addrs.n_ipv4_addrs) {
+            if (lrnat_rec->dnat_force_snat_addrs.n_ipv4_addrs) {
                 build_lrouter_force_snat_flows(lflows, od, "4",
-                    od->dnat_force_snat_addrs.ipv4_addrs[0].addr_s,
+                    lrnat_rec->dnat_force_snat_addrs.ipv4_addrs[0].addr_s,
                     "dnat");
             }
-            if (od->dnat_force_snat_addrs.n_ipv6_addrs) {
+            if (lrnat_rec->dnat_force_snat_addrs.n_ipv6_addrs) {
                 build_lrouter_force_snat_flows(lflows, od, "6",
-                    od->dnat_force_snat_addrs.ipv6_addrs[0].addr_s,
+                    lrnat_rec->dnat_force_snat_addrs.ipv6_addrs[0].addr_s,
                     "dnat");
             }
         }
         if (lb_force_snat_ip) {
-            if (od->lb_force_snat_addrs.n_ipv4_addrs) {
+            if (lrnat_rec->lb_force_snat_addrs.n_ipv4_addrs) {
                 build_lrouter_force_snat_flows(lflows, od, "4",
-                    od->lb_force_snat_addrs.ipv4_addrs[0].addr_s, "lb");
+                    lrnat_rec->lb_force_snat_addrs.ipv4_addrs[0].addr_s, "lb");
             }
-            if (od->lb_force_snat_addrs.n_ipv6_addrs) {
+            if (lrnat_rec->lb_force_snat_addrs.n_ipv6_addrs) {
                 build_lrouter_force_snat_flows(lflows, od, "6",
-                    od->lb_force_snat_addrs.ipv6_addrs[0].addr_s, "lb");
+                    lrnat_rec->lb_force_snat_addrs.ipv6_addrs[0].addr_s, "lb");
             }
         }
     }
@@ -16178,6 +16066,7 @@ struct lswitch_flow_build_info {
     const struct hmap *ls_ports;
     const struct hmap *lr_ports;
     const struct ls_port_group_table *ls_port_groups;
+    const struct lr_nat_table *lr_nats;
     struct hmap *lflows;
     struct hmap *igmp_groups;
     const struct shash *meter_groups;
@@ -16243,14 +16132,15 @@ build_lswitch_and_lrouter_iterate_by_lr(struct ovn_datapath *od,
     build_check_pkt_len_flows_for_lrouter(od, lsi->lflows, lsi->lr_ports,
                                           &lsi->match, &lsi->actions,
                                           lsi->meter_groups);
-    build_gateway_redirect_flows_for_lrouter(od, lsi->lflows, &lsi->match,
-                                             &lsi->actions);
+    build_gateway_redirect_flows_for_lrouter(od, lsi->lflows, lsi->lr_nats,
+                                             &lsi->match, &lsi->actions);
     build_arp_request_flows_for_lrouter(od, lsi->lflows, &lsi->match,
                                         &lsi->actions, lsi->meter_groups);
     build_misc_local_traffic_drop_flows_for_lrouter(od, lsi->lflows);
-    build_lrouter_arp_nd_for_datapath(od, lsi->lflows, lsi->meter_groups);
+    build_lrouter_arp_nd_for_datapath(od, lsi->lr_nats, lsi->lflows,
+                                      lsi->meter_groups);
     build_lrouter_nat_defrag_and_lb(od, lsi->lflows, lsi->ls_ports,
-                                    lsi->lr_ports, &lsi->match,
+                                    lsi->lr_ports,lsi->lr_nats, &lsi->match,
                                     &lsi->actions, lsi->meter_groups,
                                     lsi->features);
     build_lrouter_lb_affinity_default_flows(od, lsi->lflows);
@@ -16263,6 +16153,7 @@ static void
 build_lswitch_and_lrouter_iterate_by_lsp(struct ovn_port *op,
                                          const struct hmap *ls_ports,
                                          const struct hmap *lr_ports,
+                                         const struct lr_nat_table *lr_nats,
                                          const struct shash *meter_groups,
                                          struct ds *match,
                                          struct ds *actions,
@@ -16279,7 +16170,7 @@ build_lswitch_and_lrouter_iterate_by_lsp(struct ovn_port *op,
                                              meter_groups, actions, match);
     build_lswitch_dhcp_options_and_response(op, lflows, meter_groups);
     build_lswitch_external_port(op, lflows);
-    build_lswitch_ip_unicast_lookup(op, lflows, actions, match);
+    build_lswitch_ip_unicast_lookup(op, lr_nats, lflows, actions, match);
 
     /* Build Logical Router Flows. */
     build_ip_routing_flows_for_router_type_lsp(op, lr_ports, lflows);
@@ -16297,6 +16188,11 @@ build_lswitch_and_lrouter_iterate_by_lrp(struct ovn_port *op,
                                          struct lswitch_flow_build_info *lsi)
 {
     ovs_assert(op->nbrp);
+
+    const struct lr_nat_record *lrnet_rec = lr_nat_table_find_by_index(
+        lsi->lr_nats, op->od->index);
+    ovs_assert(lrnet_rec);
+
     build_adm_ctrl_flows_for_lrouter_port(op, lsi->lflows, &lsi->match,
                                           &lsi->actions);
     build_neigh_learning_flows_for_lrouter_port(op, lsi->lflows, &lsi->match,
@@ -16304,7 +16200,7 @@ build_lswitch_and_lrouter_iterate_by_lrp(struct ovn_port *op,
     build_ip_routing_flows_for_lrp(op, lsi->lflows);
     build_ND_RA_flows_for_lrouter_port(op, lsi->lflows, &lsi->match,
                                        &lsi->actions, lsi->meter_groups);
-    build_arp_resolve_flows_for_lrp(op, lsi->lflows, &lsi->match,
+    build_arp_resolve_flows_for_lrp(op, lrnet_rec, lsi->lflows, &lsi->match,
                                     &lsi->actions);
     build_egress_delivery_flows_for_lrouter_port(op, lsi->lflows, &lsi->match,
                                                  &lsi->actions);
@@ -16312,9 +16208,9 @@ build_lswitch_and_lrouter_iterate_by_lrp(struct ovn_port *op,
     build_ipv6_input_flows_for_lrouter_port(op, lsi->lflows,
                                             &lsi->match, &lsi->actions,
                                             lsi->meter_groups);
-    build_lrouter_ipv4_ip_input(op, lsi->lflows,
+    build_lrouter_ipv4_ip_input(op, lsi->lflows, lrnet_rec,
                                 &lsi->match, &lsi->actions, lsi->meter_groups);
-    build_lrouter_force_snat_flows_op(op, lsi->lflows, &lsi->match,
+    build_lrouter_force_snat_flows_op(op, lrnet_rec, lsi->lflows, &lsi->match,
                                       &lsi->actions);
 }
 
@@ -16374,6 +16270,7 @@ build_lflows_thread(void *arg)
                     }
                     build_lswitch_and_lrouter_iterate_by_lsp(op, lsi->ls_ports,
                                                              lsi->lr_ports,
+                                                             lsi->lr_nats,
                                                              lsi->meter_groups,
                                                              &lsi->match,
                                                              &lsi->actions,
@@ -16412,6 +16309,7 @@ build_lflows_thread(void *arg)
                     build_lrouter_flows_for_lb(lb_dps, lsi->lflows,
                                                lsi->meter_groups,
                                                lsi->lr_datapaths,
+                                               lsi->lr_nats,
                                                lsi->features,
                                                lsi->svc_monitor_map,
                                                &lsi->match, &lsi->actions);
@@ -16482,6 +16380,7 @@ build_lswitch_and_lrouter_flows(const struct ovn_datapaths *ls_datapaths,
                                 const struct hmap *ls_ports,
                                 const struct hmap *lr_ports,
                                 const struct ls_port_group_table *ls_pgs,
+                                const struct lr_nat_table *lr_nats,
                                 struct hmap *lflows,
                                 struct hmap *igmp_groups,
                                 const struct shash *meter_groups,
@@ -16511,6 +16410,7 @@ build_lswitch_and_lrouter_flows(const struct ovn_datapaths *ls_datapaths,
             lsiv[index].ls_ports = ls_ports;
             lsiv[index].lr_ports = lr_ports;
             lsiv[index].ls_port_groups = ls_pgs;
+            lsiv[index].lr_nats = lr_nats;
             lsiv[index].igmp_groups = igmp_groups;
             lsiv[index].meter_groups = meter_groups;
             lsiv[index].lb_dps_map = lb_dps_map;
@@ -16545,6 +16445,7 @@ build_lswitch_and_lrouter_flows(const struct ovn_datapaths *ls_datapaths,
             .ls_ports = ls_ports,
             .lr_ports = lr_ports,
             .ls_port_groups = ls_pgs,
+            .lr_nats = lr_nats,
             .lflows = lflows,
             .igmp_groups = igmp_groups,
             .meter_groups = meter_groups,
@@ -16572,6 +16473,7 @@ build_lswitch_and_lrouter_flows(const struct ovn_datapaths *ls_datapaths,
         HMAP_FOR_EACH (op, key_node, ls_ports) {
             build_lswitch_and_lrouter_iterate_by_lsp(op, lsi.ls_ports,
                                                      lsi.lr_ports,
+                                                     lsi.lr_nats,
                                                      lsi.meter_groups,
                                                      &lsi.match, &lsi.actions,
                                                      lsi.lflows);
@@ -16588,8 +16490,8 @@ build_lswitch_and_lrouter_flows(const struct ovn_datapaths *ls_datapaths,
             build_lrouter_defrag_flows_for_lb(lb_dps, lsi.lflows,
                                               lsi.lr_datapaths, &lsi.match);
             build_lrouter_flows_for_lb(lb_dps, lsi.lflows, lsi.meter_groups,
-                                       lsi.lr_datapaths, lsi.features,
-                                       lsi.svc_monitor_map,
+                                       lsi.lr_datapaths, lsi.lr_nats,
+                                       lsi.features, lsi.svc_monitor_map,
                                        &lsi.match, &lsi.actions);
             build_lswitch_flows_for_lb(lb_dps, lsi.lflows, lsi.meter_groups,
                                        lsi.ls_datapaths, lsi.features,
@@ -16692,6 +16594,7 @@ void build_lflows(struct ovsdb_idl_txn *ovnsb_txn,
                                     input_data->ls_ports,
                                     input_data->lr_ports,
                                     input_data->ls_port_groups,
+                                    input_data->lr_nats,
                                     lflows,
                                     &igmp_groups,
                                     input_data->meter_groups,
@@ -17169,6 +17072,7 @@ lflow_handle_northd_port_changes(struct ovsdb_idl_txn *ovnsb_txn,
         struct ds actions = DS_EMPTY_INITIALIZER;
         build_lswitch_and_lrouter_iterate_by_lsp(op, lflow_input->ls_ports,
                                                  lflow_input->lr_ports,
+                                                 lflow_input->lr_nats,
                                                  lflow_input->meter_groups,
                                                  &match, &actions,
                                                  lflows);
@@ -17205,6 +17109,7 @@ lflow_handle_northd_port_changes(struct ovsdb_idl_txn *ovnsb_txn,
         struct ds actions = DS_EMPTY_INITIALIZER;
         build_lswitch_and_lrouter_iterate_by_lsp(op, lflow_input->ls_ports,
                                                     lflow_input->lr_ports,
+                                                    lflow_input->lr_nats,
                                                     lflow_input->meter_groups,
                                                     &match, &actions,
                                                     lflows);
diff --git a/northd/northd.h b/northd/northd.h
index 233dca8084..4dd260761e 100644
--- a/northd/northd.h
+++ b/northd/northd.h
@@ -83,6 +83,12 @@ struct ovn_datapaths {
     struct ovn_datapath **array;
 };
 
+static inline size_t
+ods_size(const struct ovn_datapaths *datapaths)
+{
+    return hmap_count(&datapaths->datapaths);
+}
+
 struct tracked_ovn_ports {
     /* tracked created ports.
      * hmapx node data is 'struct ovn_port *' */
@@ -109,8 +115,9 @@ struct tracked_lbs {
 
 enum northd_tracked_data_type {
     NORTHD_TRACKED_NONE,
-    NORTHD_TRACKED_PORTS = (1 << 0),
-    NORTHD_TRACKED_LBS   = (1 << 1),
+    NORTHD_TRACKED_PORTS    = (1 << 0),
+    NORTHD_TRACKED_LBS      = (1 << 1),
+    NORTHD_TRACKED_LR_NATS  = (1 << 2),
 };
 
 /* Track what's changed in the northd engine node.
@@ -121,6 +128,10 @@ struct northd_tracked_data {
     enum northd_tracked_data_type type;
     struct tracked_ovn_ports trk_lsps;
     struct tracked_lbs trk_lbs;
+
+    /* Tracked logical routers whose NATs have changed.
+     * hmapx node is 'struct ovn_datapath *'. */
+    struct hmapx lr_with_changed_nats;
 };
 
 struct northd_data {
@@ -148,6 +159,8 @@ struct lflow_data {
 void lflow_data_init(struct lflow_data *);
 void lflow_data_destroy(struct lflow_data *);
 
+struct lr_nat_table;
+
 struct lflow_input {
     /* Northbound table references */
     const struct nbrec_bfd_table *nbrec_bfd_table;
@@ -166,6 +179,7 @@ struct lflow_input {
     const struct hmap *ls_ports;
     const struct hmap *lr_ports;
     const struct ls_port_group_table *ls_port_groups;
+    const struct lr_nat_table *lr_nats;
     const struct shash *meter_groups;
     const struct hmap *lb_datapaths_map;
     const struct hmap *bfd_connections;
@@ -302,24 +316,9 @@ struct ovn_datapath {
     struct ovn_port **l3dgw_ports;
     size_t n_l3dgw_ports;
 
-    /* NAT entries configured on the router. */
-    struct ovn_nat *nat_entries;
-    size_t n_nat_entries;
-
-    bool has_distributed_nat;
     /* router datapath has a logical port with redirect-type set to bridged. */
     bool redirect_bridged;
 
-    /* Set of nat external ips on the router. */
-    struct sset external_ips;
-
-    /* SNAT IPs owned by the router (shash of 'struct ovn_snat_ip'). */
-    struct shash snat_ips;
-
-    struct lport_addresses dnat_force_snat_addrs;
-    struct lport_addresses lb_force_snat_addrs;
-    bool lb_force_snat_router_ip;
-
     /* Load Balancer vIPs relevant for this datapath. */
     struct ovn_lb_ip_set *lb_ips;
 
@@ -336,6 +335,9 @@ struct ovn_datapath {
     struct hmap ports;
 };
 
+const struct ovn_datapath *ovn_datapath_find(const struct hmap *datapaths,
+                                             const struct uuid *uuid);
+
 void ovnnb_db_run(struct northd_input *input_data,
                   struct northd_data *data,
                   struct ovsdb_idl_txn *ovnnb_txn,
@@ -396,8 +398,8 @@ void sync_lbs(struct ovsdb_idl_txn *, const struct sbrec_load_balancer_table *,
 bool check_sb_lb_duplicates(const struct sbrec_load_balancer_table *);
 
 void sync_pbs(struct ovsdb_idl_txn *, struct hmap *ls_ports,
-              struct hmap *lr_ports);
-bool sync_pbs_for_northd_changed_ovn_ports( struct tracked_ovn_ports *);
+              struct hmap *lr_ports, const struct lr_nat_table *);
+bool sync_pbs_for_northd_changed_ovn_ports(struct tracked_ovn_ports *);
 
 static inline bool
 northd_has_tracked_data(struct northd_tracked_data *trk_nd_changes) {
@@ -416,4 +418,10 @@ northd_has_lsps_in_tracked_data(struct northd_tracked_data *trk_nd_changes)
     return (trk_nd_changes->type & NORTHD_TRACKED_PORTS);
 }
 
+static inline bool
+northd_has_lr_nats_in_tracked_data(struct northd_tracked_data *trk_nd_changes)
+{
+    return (trk_nd_changes->type & NORTHD_TRACKED_LR_NATS);
+}
+
 #endif /* NORTHD_H */
diff --git a/northd/ovn-northd.c b/northd/ovn-northd.c
index f3868068d3..40f9764b3a 100644
--- a/northd/ovn-northd.c
+++ b/northd/ovn-northd.c
@@ -870,6 +870,7 @@ main(int argc, char *argv[])
     stopwatch_create(LFLOWS_TO_SB_STOPWATCH_NAME, SW_MS);
     stopwatch_create(PORT_GROUP_RUN_STOPWATCH_NAME, SW_MS);
     stopwatch_create(SYNC_METERS_RUN_STOPWATCH_NAME, SW_MS);
+    stopwatch_create(LR_NAT_RUN_STOPWATCH_NAME, SW_MS);
 
     /* Initialize incremental processing engine for ovn-northd */
     inc_proc_northd_init(&ovnnb_idl_loop, &ovnsb_idl_loop);
diff --git a/tests/ovn-northd.at b/tests/ovn-northd.at
index 4edad24e53..ef8c6a616b 100644
--- a/tests/ovn-northd.at
+++ b/tests/ovn-northd.at
@@ -11240,6 +11240,7 @@ check ovn-nbctl --wait=sb lsp-add sw0 sw0p1 -- lsp-set-addresses sw0p1 "00:00:20
 check as northd ovn-appctl -t ovn-northd inc-engine/clear-stats
 check ovn-nbctl --wait=sb lr-add lr0
 check_engine_stats northd recompute nocompute
+check_engine_stats lr_nat recompute nocompute
 check_engine_stats sync_to_sb_pb recompute nocompute
 check_engine_stats lflow recompute nocompute
 CHECK_NO_CHANGE_AFTER_RECOMPUTE
@@ -11251,6 +11252,7 @@ check ovn-nbctl lrp-add lr0 lr0-sw0 00:00:00:00:ff:01 10.0.0.1/24
 # first it will be recompute to handle lr0-sw0 and then a compute
 # for the SB port binding change.
 check_engine_stats northd recompute compute
+check_engine_stats lr_nat recompute nocompute
 check_engine_stats sync_to_sb_pb recompute nocompute
 check_engine_stats lflow recompute nocompute
 CHECK_NO_CHANGE_AFTER_RECOMPUTE
@@ -11261,6 +11263,7 @@ ovn-nbctl lsp-set-addresses sw0-lr0 00:00:00:00:ff:01
 check as northd ovn-appctl -t ovn-northd inc-engine/clear-stats
 check ovn-nbctl --wait=sb lsp-set-options sw0-lr0 router-port=lr0-sw0
 check_engine_stats northd recompute compute
+check_engine_stats lr_nat recompute nocompute
 check_engine_stats sync_to_sb_pb recompute nocompute
 check_engine_stats lflow recompute nocompute
 CHECK_NO_CHANGE_AFTER_RECOMPUTE
@@ -11285,16 +11288,18 @@ ovn-nbctl --wait=hv lrp-set-gateway-chassis lr0-public hv1 20
 check as northd ovn-appctl -t ovn-northd inc-engine/clear-stats
 check ovn-nbctl set logical_router_port lr0-sw0 options:foo=bar
 check_engine_stats northd recompute nocompute
+check_engine_stats lr_nat recompute nocompute
 check_engine_stats sync_to_sb_pb recompute nocompute
 check_engine_stats lflow recompute nocompute
 CHECK_NO_CHANGE_AFTER_RECOMPUTE
 
 # Do checks for NATs.
-# Add a NAT. This should not result in recompute of both northd and lflow
-# engine nodes.
+# Add a NAT. This should not result in recompute of northd, but
+# recompute of lflow node.
 check as northd ovn-appctl -t ovn-northd inc-engine/clear-stats
 check ovn-nbctl --wait=sb lr-nat-add lr0 dnat_and_snat  172.168.0.110 10.0.0.4
-check_engine_stats northd recompute nocompute
+check_engine_stats northd norecompute compute
+check_engine_stats lr_nat norecompute compute
 check_engine_stats lflow recompute nocompute
 check_engine_stats sync_to_sb_pb recompute nocompute
 CHECK_NO_CHANGE_AFTER_RECOMPUTE
@@ -11302,7 +11307,8 @@ CHECK_NO_CHANGE_AFTER_RECOMPUTE
 # Update the NAT options column
 check as northd ovn-appctl -t ovn-northd inc-engine/clear-stats
 check ovn-nbctl --wait=sb set NAT . options:foo=bar
-check_engine_stats northd recompute nocompute
+check_engine_stats northd norecompute compute
+check_engine_stats lr_nat norecompute compute
 check_engine_stats lflow recompute nocompute
 check_engine_stats sync_to_sb_pb recompute nocompute
 CHECK_NO_CHANGE_AFTER_RECOMPUTE
@@ -11310,7 +11316,8 @@ CHECK_NO_CHANGE_AFTER_RECOMPUTE
 # Update the NAT external_ip column
 check as northd ovn-appctl -t ovn-northd inc-engine/clear-stats
 check ovn-nbctl --wait=sb set NAT . external_ip=172.168.0.120
-check_engine_stats northd recompute nocompute
+check_engine_stats northd norecompute compute
+check_engine_stats lr_nat norecompute compute
 check_engine_stats lflow recompute nocompute
 check_engine_stats sync_to_sb_pb recompute nocompute
 CHECK_NO_CHANGE_AFTER_RECOMPUTE
@@ -11318,7 +11325,8 @@ CHECK_NO_CHANGE_AFTER_RECOMPUTE
 # Update the NAT logical_ip column
 check as northd ovn-appctl -t ovn-northd inc-engine/clear-stats
 check ovn-nbctl --wait=sb set NAT . logical_ip=10.0.0.10
-check_engine_stats northd recompute nocompute
+check_engine_stats northd norecompute compute
+check_engine_stats lr_nat norecompute compute
 check_engine_stats lflow recompute nocompute
 check_engine_stats sync_to_sb_pb recompute nocompute
 CHECK_NO_CHANGE_AFTER_RECOMPUTE
@@ -11326,7 +11334,8 @@ CHECK_NO_CHANGE_AFTER_RECOMPUTE
 # Update the NAT type
 check as northd ovn-appctl -t ovn-northd inc-engine/clear-stats
 check ovn-nbctl --wait=sb set NAT . type=snat
-check_engine_stats northd recompute nocompute
+check_engine_stats northd norecompute compute
+check_engine_stats lr_nat norecompute compute
 check_engine_stats lflow recompute nocompute
 check_engine_stats sync_to_sb_pb recompute nocompute
 CHECK_NO_CHANGE_AFTER_RECOMPUTE
@@ -11334,7 +11343,8 @@ CHECK_NO_CHANGE_AFTER_RECOMPUTE
 # Create a dnat_and_snat NAT with external_mac and logical_port
 check as northd ovn-appctl -t ovn-northd inc-engine/clear-stats
 check ovn-nbctl --wait=sb lr-nat-add lr0 dnat_and_snat 172.168.0.110 10.0.0.4 sw0p1 30:54:00:00:00:03
-check_engine_stats northd recompute compute
+check_engine_stats northd norecompute compute
+check_engine_stats lr_nat norecompute compute
 check_engine_stats lflow recompute nocompute
 check_engine_stats sync_to_sb_pb recompute nocompute
 CHECK_NO_CHANGE_AFTER_RECOMPUTE
@@ -11343,7 +11353,8 @@ nat2_uuid=$(ovn-nbctl --bare --columns _uuid find nat logical_ip=10.0.0.4)
 
 check as northd ovn-appctl -t ovn-northd inc-engine/clear-stats
 check ovn-nbctl --wait=sb set NAT $nat2_uuid external_mac='"30:54:00:00:00:04"'
-check_engine_stats northd recompute nocompute
+check_engine_stats northd norecompute compute
+check_engine_stats lr_nat norecompute compute
 check_engine_stats lflow recompute nocompute
 check_engine_stats sync_to_sb_pb recompute nocompute
 CHECK_NO_CHANGE_AFTER_RECOMPUTE
@@ -11358,28 +11369,32 @@ check ovn-nbctl lr-lb-add lr0 lb2
 # is a lb vip.
 check as northd ovn-appctl -t ovn-northd inc-engine/clear-stats
 check ovn-nbctl --wait=sb lr-nat-add lr0 dnat_and_snat 172.168.0.140 10.0.0.20
-check_engine_stats northd recompute nocompute
+check_engine_stats northd norecompute compute
+check_engine_stats lr_nat norecompute compute
 check_engine_stats sync_to_sb_pb recompute nocompute
 check_engine_stats lflow recompute nocompute
 CHECK_NO_CHANGE_AFTER_RECOMPUTE
 
 check as northd ovn-appctl -t ovn-northd inc-engine/clear-stats
 check ovn-nbctl --wait=sb lr-nat-add lr0 dnat_and_snat 172.168.0.150 10.0.0.41
-check_engine_stats northd recompute nocompute
+check_engine_stats northd norecompute compute
+check_engine_stats lr_nat norecompute compute
 check_engine_stats sync_to_sb_pb recompute nocompute
 check_engine_stats lflow recompute nocompute
 CHECK_NO_CHANGE_AFTER_RECOMPUTE
 
 check as northd ovn-appctl -t ovn-northd inc-engine/clear-stats
 check ovn-nbctl --wait=sb lr-nat-del lr0 dnat_and_snat 172.168.0.150
-check_engine_stats northd recompute nocompute
+check_engine_stats northd norecompute compute
+check_engine_stats lr_nat norecompute compute
 check_engine_stats sync_to_sb_pb recompute nocompute
 check_engine_stats lflow recompute nocompute
 CHECK_NO_CHANGE_AFTER_RECOMPUTE
 
 check as northd ovn-appctl -t ovn-northd inc-engine/clear-stats
 check ovn-nbctl --wait=sb lr-nat-del lr0 dnat_and_snat 172.168.0.140
-check_engine_stats northd recompute nocompute
+check_engine_stats northd norecompute compute
+check_engine_stats lr_nat norecompute compute
 check_engine_stats sync_to_sb_pb recompute nocompute
 check_engine_stats lflow recompute nocompute
 CHECK_NO_CHANGE_AFTER_RECOMPUTE
@@ -11387,7 +11402,8 @@ CHECK_NO_CHANGE_AFTER_RECOMPUTE
 # Delete the NAT
 check as northd ovn-appctl -t ovn-northd inc-engine/clear-stats
 check ovn-nbctl --wait=sb clear logical_router lr0 nat
-check_engine_stats northd recompute compute
+check_engine_stats northd norecompute compute
+check_engine_stats lr_nat norecompute compute
 check_engine_stats lflow recompute nocompute
 check_engine_stats sync_to_sb_pb recompute nocompute
 CHECK_NO_CHANGE_AFTER_RECOMPUTE
@@ -11396,6 +11412,7 @@ CHECK_NO_CHANGE_AFTER_RECOMPUTE
 check as northd ovn-appctl -t ovn-northd inc-engine/clear-stats
 check ovn-nbctl --wait=sb lr-policy-add lr0  10 "ip4.src == 10.0.0.3" reroute 172.168.0.101,172.168.0.102
 check_engine_stats northd recompute nocompute
+check_engine_stats lr_nat recompute nocompute
 check_engine_stats sync_to_sb_pb recompute nocompute
 check_engine_stats lflow recompute nocompute
 CHECK_NO_CHANGE_AFTER_RECOMPUTE
@@ -11403,6 +11420,7 @@ CHECK_NO_CHANGE_AFTER_RECOMPUTE
 check as northd ovn-appctl -t ovn-northd inc-engine/clear-stats
 check ovn-nbctl --wait=sb lr-policy-del lr0  10 "ip4.src == 10.0.0.3"
 check_engine_stats northd recompute nocompute
+check_engine_stats lr_nat recompute nocompute
 check_engine_stats sync_to_sb_pb recompute nocompute
 check_engine_stats lflow recompute nocompute
 CHECK_NO_CHANGE_AFTER_RECOMPUTE
