diff --git a/controller/binding.c b/controller/binding.c
index 3c102dc7f..0397e145a 100644
--- a/controller/binding.c
+++ b/controller/binding.c
@@ -1349,8 +1349,16 @@ build_local_bindings(struct binding_ctx_in *b_ctx_in,
                 }
 
                 update_local_lports(iface_id, b_ctx_out);
-                smap_replace(b_ctx_out->local_iface_ids, iface_rec->name,
-                             iface_id);
+
+                struct local_iface_node *iface_node =
+                    xmalloc(sizeof *iface_node);
+                iface_node->iface_id = xstrdup(iface_id);
+                iface_node = shash_replace(b_ctx_out->local_ifaces,
+                                           iface_rec->name, iface_node);
+                if (iface_node) {
+                    free(iface_node->iface_id);
+                    free(iface_node);
+                }
             }
 
             /* Check if this is a tunnel interface. */
@@ -1689,7 +1697,15 @@ consider_iface_claim(const struct ovsrec_interface *iface_rec,
                      struct hmap *qos_map)
 {
     update_local_lports(iface_id, b_ctx_out);
-    smap_replace(b_ctx_out->local_iface_ids, iface_rec->name, iface_id);
+
+    struct local_iface_node *iface_node = xmalloc(sizeof *iface_node);
+    iface_node->iface_id = xstrdup(iface_id);
+    iface_node = shash_replace(b_ctx_out->local_ifaces,
+                               iface_rec->name, iface_node);
+    if (iface_node) {
+        free(iface_node->iface_id);
+        free(iface_node);
+    }
 
     struct local_binding *lbinding =
         local_binding_find(b_ctx_out->local_bindings, iface_id);
@@ -1783,7 +1799,13 @@ consider_iface_release(const struct ovsrec_interface *iface_rec,
     }
 
     remove_local_lports(iface_id, b_ctx_out);
-    smap_remove(b_ctx_out->local_iface_ids, iface_rec->name);
+    struct local_iface_node *iface_node = shash_find_and_delete(
+            b_ctx_out->local_ifaces,
+            iface_rec->name);
+    if (iface_node) {
+        free(iface_node->iface_id);
+        free(iface_node);
+    }
 
     return true;
 }
@@ -1822,11 +1844,11 @@ binding_handle_ovs_interface_changes(struct binding_ctx_in *b_ctx_in,
      *   2. external_ids:iface-id is cleared in which case we need to
      *      release the port binding corresponding to the previously set
      *      'old-iface-id' (which is stored in the smap
-     *      'b_ctx_out->local_iface_ids').
+     *      'b_ctx_out->local_ifaces').
      *   3. external_ids:iface-id is updated with a different value
      *      in which case we need to release the port binding corresponding
      *      to the previously set 'old-iface-id' (which is stored in the smap
-     *      'b_ctx_out->local_iface_ids').
+     *      'b_ctx_out->local_ifaces').
      *   4. ofport of the OVS interface is 0.
      *
      */
@@ -1842,8 +1864,10 @@ binding_handle_ovs_interface_changes(struct binding_ctx_in *b_ctx_in,
         }
 
         const char *iface_id = smap_get(&iface_rec->external_ids, "iface-id");
-        const char *old_iface_id = smap_get(b_ctx_out->local_iface_ids,
-                                            iface_rec->name);
+
+        struct local_iface_node *iface_node = shash_find_data(
+                b_ctx_out->local_ifaces, iface_rec->name);
+        const char *old_iface_id = iface_node ? iface_node->iface_id : NULL;
         const char *cleared_iface_id = NULL;
         if (!ovsrec_interface_is_deleted(iface_rec)) {
             int64_t ofport = iface_rec->n_ofport ? *iface_rec->ofport : 0;
diff --git a/controller/binding.h b/controller/binding.h
index c9740560f..a1e0f1ccf 100644
--- a/controller/binding.h
+++ b/controller/binding.h
@@ -54,6 +54,10 @@ struct binding_ctx_in {
     const struct ovsrec_interface_table *iface_table;
 };
 
+struct local_iface_node {
+    char *iface_id;
+};
+
 struct binding_ctx_out {
     struct hmap *local_datapaths;
     struct shash *local_bindings;
@@ -77,7 +81,7 @@ struct binding_ctx_out {
     struct sset *egress_ifaces;
     /* smap of OVS interface name as key and
      * OVS interface external_ids:iface-id as value. */
-    struct smap *local_iface_ids;
+    struct shash *local_ifaces;
 
     /* hmap of 'struct tracked_binding_datapath' which the
      * callee (binding_handle_ovs_interface_changes and
diff --git a/controller/ovn-controller.c b/controller/ovn-controller.c
index 8d8c678e5..0a6f171be 100644
--- a/controller/ovn-controller.c
+++ b/controller/ovn-controller.c
@@ -35,6 +35,7 @@
 #include "fatal-signal.h"
 #include "ip-mcast.h"
 #include "openvswitch/hmap.h"
+#include "openvswitch/shash.h"
 #include "lflow.h"
 #include "lib/vswitch-idl.h"
 #include "lport.h"
@@ -1033,7 +1034,7 @@ struct ed_type_runtime_data {
 
     /* runtime data engine private data. */
     struct sset egress_ifaces;
-    struct smap local_iface_ids;
+    struct shash local_ifaces;
 
     /* Tracked data. See below for more details and comments. */
     bool tracked;
@@ -1085,7 +1086,7 @@ struct ed_type_runtime_data {
  * | local_bindings   | the @tracked_dp_bindings indirectly and hence it |
  * | local_lport_ids  | is not tracked explicitly.                       |
  *  ---------------------------------------------------------------------
- * | local_iface_ids  | This is used internally within the runtime data  |
+ * | local_ifaces     | This is used internally within the runtime data  |
  * | egress_ifaces    | engine (used only in binding.c) and hence there  |
  * |                  | there is no need to track.                       |
  *  ---------------------------------------------------------------------
@@ -1124,7 +1125,7 @@ en_runtime_data_init(struct engine_node *node OVS_UNUSED,
     sset_init(&data->local_lport_ids);
     sset_init(&data->active_tunnels);
     sset_init(&data->egress_ifaces);
-    smap_init(&data->local_iface_ids);
+    shash_init(&data->local_ifaces);
     local_bindings_init(&data->local_bindings);
 
     /* Init the tracked data. */
@@ -1142,7 +1143,19 @@ en_runtime_data_cleanup(void *data)
     sset_destroy(&rt_data->local_lport_ids);
     sset_destroy(&rt_data->active_tunnels);
     sset_destroy(&rt_data->egress_ifaces);
-    smap_destroy(&rt_data->local_iface_ids);
+
+    struct shash_node *sh_node, *sh_node_next;
+    SHASH_FOR_EACH_SAFE (sh_node, sh_node_next,
+                         &rt_data->local_ifaces) {
+        struct local_iface_node *iface_node = sh_node->data;
+        hmap_remove(&rt_data->local_ifaces.map, &sh_node->node);
+        free(iface_node->iface_id);
+        free(sh_node->data);
+        free(sh_node->name);
+        free(sh_node);
+    }
+    hmap_destroy(&rt_data->local_ifaces.map);
+
     struct local_datapath *cur_node, *next_node;
     HMAP_FOR_EACH_SAFE (cur_node, next_node, hmap_node,
                         &rt_data->local_datapaths) {
@@ -1234,7 +1247,7 @@ init_binding_ctx(struct engine_node *node,
     b_ctx_out->non_vif_ports_changed = false;
     b_ctx_out->egress_ifaces = &rt_data->egress_ifaces;
     b_ctx_out->local_bindings = &rt_data->local_bindings;
-    b_ctx_out->local_iface_ids = &rt_data->local_iface_ids;
+    b_ctx_out->local_ifaces = &rt_data->local_ifaces;
     b_ctx_out->tracked_dp_bindings = NULL;
     b_ctx_out->local_lports_changed = NULL;
 }
@@ -1282,12 +1295,24 @@ en_runtime_data_run(struct engine_node *node, void *data)
         sset_destroy(local_lport_ids);
         sset_destroy(active_tunnels);
         sset_destroy(&rt_data->egress_ifaces);
-        smap_destroy(&rt_data->local_iface_ids);
+
+        struct shash_node *sh_node, *sh_node_next;
+        SHASH_FOR_EACH_SAFE (sh_node, sh_node_next,
+                             &rt_data->local_ifaces) {
+            struct local_iface_node *iface_node = sh_node->data;
+            hmap_remove(&rt_data->local_ifaces.map, &sh_node->node);
+            free(iface_node->iface_id);
+            free(sh_node->data);
+            free(sh_node->name);
+            free(sh_node);
+        }
+        hmap_destroy(&rt_data->local_ifaces.map);
+
         sset_init(local_lports);
         sset_init(local_lport_ids);
         sset_init(active_tunnels);
         sset_init(&rt_data->egress_ifaces);
-        smap_init(&rt_data->local_iface_ids);
+        shash_init(&rt_data->local_ifaces);
         local_bindings_init(&rt_data->local_bindings);
     }
 
