diff --git a/core/api/src/main/java/org/onosproject/store/primitives/DefaultConsistentTreeMap.java b/core/api/src/main/java/org/onosproject/store/primitives/DefaultConsistentTreeMap.java
index e858fc0..782a1ec 100644
--- a/core/api/src/main/java/org/onosproject/store/primitives/DefaultConsistentTreeMap.java
+++ b/core/api/src/main/java/org/onosproject/store/primitives/DefaultConsistentTreeMap.java
@@ -27,6 +27,7 @@
 
 import java.util.Collection;
 import java.util.Map;
+import java.util.NavigableMap;
 import java.util.NavigableSet;
 import java.util.Set;
 import java.util.concurrent.CompletableFuture;
@@ -41,14 +42,16 @@
 /**
  * Implementation of the {@link ConsistentTreeMap} interface.
  */
-public class DefaultConsistentTreeMap<K, V> extends Synchronous<AsyncConsistentTreeMap<K, V>>
-        implements ConsistentTreeMap<K, V> {
+public class DefaultConsistentTreeMap<V>
+        extends Synchronous<AsyncConsistentTreeMap<V>>
+        implements ConsistentTreeMap<V> {
     private static final int MAX_DELAY_BETWEEN_RETRY_MILLIS = 50;
-    private final AsyncConsistentTreeMap<K, V> treeMap;
+    private final AsyncConsistentTreeMap<V> treeMap;
     private final long operationTimeoutMillis;
-    private Map<K, V> javaMap;
+    private Map<String, V> javaMap;
 
-    public DefaultConsistentTreeMap(AsyncConsistentTreeMap<K, V> treeMap, long operationTimeoutMillis) {
+    public DefaultConsistentTreeMap(AsyncConsistentTreeMap<V> treeMap,
+                                    long operationTimeoutMillis) {
         super(treeMap);
         this.treeMap = treeMap;
         this.operationTimeoutMillis = operationTimeoutMillis;
@@ -69,72 +72,72 @@
     }
 
     @Override
-    public K firstKey() {
+    public String firstKey() {
         return complete(treeMap.firstKey());
     }
 
     @Override
-    public K lastKey() {
+    public String lastKey() {
         return complete(treeMap.lastKey());
     }
 
     @Override
-    public Map.Entry<K, Versioned<V>> ceilingEntry(K key) {
+    public Map.Entry<String, Versioned<V>> ceilingEntry(String key) {
         return complete(treeMap.ceilingEntry(key));
     }
 
     @Override
-    public Map.Entry<K, Versioned<V>> floorEntry(K key) {
+    public Map.Entry<String, Versioned<V>> floorEntry(String key) {
         return complete(treeMap.floorEntry(key));
     }
 
     @Override
-    public Map.Entry<K, Versioned<V>> higherEntry(K key) {
+    public Map.Entry<String, Versioned<V>> higherEntry(String key) {
         return complete(treeMap.higherEntry(key));
     }
 
     @Override
-    public Map.Entry<K, Versioned<V>> lowerEntry(K key) {
+    public Map.Entry<String, Versioned<V>> lowerEntry(String key) {
         return complete(treeMap.lowerEntry(key));
     }
 
     @Override
-    public Map.Entry<K, Versioned<V>> firstEntry() {
+    public Map.Entry<String, Versioned<V>> firstEntry() {
         return complete(treeMap.firstEntry());
     }
 
     @Override
-    public Map.Entry<K, Versioned<V>> lastEntry() {
+    public Map.Entry<String, Versioned<V>> lastEntry() {
         return complete(treeMap.lastEntry());
     }
 
     @Override
-    public Map.Entry<K, Versioned<V>> pollFirstEntry() {
+    public Map.Entry<String, Versioned<V>> pollFirstEntry() {
         return complete(treeMap.pollFirstEntry());
     }
 
     @Override
-    public Map.Entry<K, Versioned<V>> pollLastEntry() {
+    public Map.Entry<String, Versioned<V>> pollLastEntry() {
         return complete(treeMap.pollLastEntry());
     }
 
     @Override
-    public K lowerKey(K key) {
+    public String lowerKey(String key) {
         return complete(treeMap.lowerKey(key));
     }
 
     @Override
-    public K floorKey(K key) {
+    public String floorKey(String key) {
         return complete(treeMap.floorKey(key));
     }
 
     @Override
-    public K ceilingKey(K key) {
+    public String ceilingKey(String key) {
         return complete(treeMap.ceilingKey(key));
     }
 
     @Override
-    public K higherKey(K key) {
+    public String higherKey(String key) {
         return complete(treeMap.higherKey(key));
     }
 
@@ -144,7 +147,7 @@
      * {@inheritDoc}
      * <p>This may be a long operation with greater risk of timeout.</p>
      */
-    public NavigableSet<K> navigableKeySet() {
+    public NavigableSet<String> navigableKeySet() {
         return complete(treeMap.navigableKeySet());
     }
 
@@ -159,7 +162,7 @@
     }
 
     @Override
-    public boolean containsKey(K key) {
+    public boolean containsKey(String key) {
         return complete(treeMap.containsKey(key));
     }
 
@@ -169,43 +172,54 @@
     }
 
     @Override
-    public Versioned<V> get(K key) {
+    public Versioned<V> get(String key) {
         return complete(treeMap.get(key));
     }
 
     @Override
-    public Versioned<V> computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
+    public Versioned<V> computeIfAbsent(String key,
+                                        Function<? super String,
+                                                ? extends V> mappingFunction) {
         return complete(treeMap.computeIfAbsent(key, mappingFunction));
     }
 
     @Override
-    public Versioned<V> compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
+    public Versioned<V> compute(String key,
+                                BiFunction<? super String,
+                                        ? super V,
+                                        ? extends V> remappingFunction) {
         return complete(treeMap.compute(key, remappingFunction));
     }
 
     @Override
-    public Versioned<V> computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
+    public Versioned<V> computeIfPresent(
+            String key,
+            BiFunction<? super String,
+                    ? super V,
+                    ? extends V> remappingFunction) {
         return complete(treeMap.computeIfPresent(key, remappingFunction));
     }
 
     @Override
-    public Versioned<V> computeIf(K key, Predicate<? super V> condition,
-                                  BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
+    public Versioned<V> computeIf(String key, Predicate<? super V> condition,
+                                  BiFunction<? super String,
+                                          ? super V,
+                                          ? extends V> remappingFunction) {
         return complete(treeMap.computeIf(key, condition, remappingFunction));
     }
 
     @Override
-    public Versioned<V> put(K key, V value) {
+    public Versioned<V> put(String key, V value) {
         return complete(treeMap.put(key, value));
     }
 
     @Override
-    public Versioned<V> putAndGet(K key, V value) {
+    public Versioned<V> putAndGet(String key, V value) {
         return complete(treeMap.putAndGet(key, value));
     }
 
     @Override
-    public Versioned<V> remove(K key) {
+    public Versioned<V> remove(String key) {
         return complete(treeMap.remove(key));
     }
 
@@ -215,7 +229,7 @@
     }
 
     @Override
-    public Set<K> keySet() {
+    public Set<String> keySet() {
         return complete(treeMap.keySet());
     }
 
@@ -225,52 +239,53 @@
     }
 
     @Override
-    public Set<Map.Entry<K, Versioned<V>>> entrySet() {
+    public Set<Map.Entry<String, Versioned<V>>> entrySet() {
         return complete(treeMap.entrySet());
     }
 
     @Override
-    public Versioned<V> putIfAbsent(K key, V value) {
+    public Versioned<V> putIfAbsent(String key, V value) {
         return complete(treeMap.putIfAbsent(key, value));
     }
 
     @Override
-    public boolean remove(K key, V value) {
+    public boolean remove(String key, V value) {
         return complete(treeMap.remove(key, value));
     }
 
     @Override
-    public boolean remove(K key, long version) {
+    public boolean remove(String key, long version) {
         return complete(treeMap.remove(key, version));
     }
 
     @Override
-    public Versioned<V> replace(K key, V value) {
+    public Versioned<V> replace(String key, V value) {
         return complete(treeMap.replace(key, value));
     }
 
     @Override
-    public boolean replace(K key, V oldValue, V newValue) {
+    public boolean replace(String key, V oldValue, V newValue) {
         return complete(treeMap.replace(key, oldValue, newValue));
     }
 
     @Override
-    public boolean replace(K key, long oldVersion, V newValue) {
+    public boolean replace(String key, long oldVersion, V newValue) {
         return complete(treeMap.replace(key, oldVersion, newValue));
     }
 
     @Override
-    public void addListener(MapEventListener<K, V> listener, Executor executor) {
+    public void addListener(MapEventListener<String, V> listener,
+                            Executor executor) {
         complete(treeMap.addListener(listener, executor));
     }
 
     @Override
-    public void removeListener(MapEventListener<K, V> listener) {
+    public void removeListener(MapEventListener<String, V> listener) {
         complete(treeMap.removeListener(listener));
     }
 
     @Override
-    public Map<K, V> asJavaMap() {
+    public Map<String, V> asJavaMap() {
         synchronized (this) {
             if (javaMap == null) {
                 javaMap = new ConsistentMapBackedJavaMap<>(this);
@@ -278,4 +293,13 @@
         }
         return javaMap;
     }
+
+    @Override
+    public NavigableMap<String, V> subMap(String upperKey,
+                                          String lowerKey,
+                                          boolean inclusiveUpper,
+                                          boolean inclusiveLower) {
+        return complete(treeMap.subMap(upperKey, lowerKey,
+                                       inclusiveUpper, inclusiveLower));
+    }
 }
diff --git a/core/api/src/main/java/org/onosproject/store/service/AsyncConsistentTreeMap.java b/core/api/src/main/java/org/onosproject/store/service/AsyncConsistentTreeMap.java
index 5c60b19..87386ed 100644
--- a/core/api/src/main/java/org/onosproject/store/service/AsyncConsistentTreeMap.java
+++ b/core/api/src/main/java/org/onosproject/store/service/AsyncConsistentTreeMap.java
@@ -23,24 +23,27 @@
 import java.util.NavigableSet;
 import java.util.concurrent.CompletableFuture;
 
+import static org.onosproject.store.service.DistributedPrimitive.DEFAULT_OPERTATION_TIMEOUT_MILLIS;
+
 /**
  * API for a distributed tree map implementation.
  */
-public interface AsyncConsistentTreeMap<K, V> extends AsyncConsistentMap<K, V> {
+public interface AsyncConsistentTreeMap<V>
+        extends AsyncConsistentMap<String, V> {
 
     /**
      * Return the lowest key in the map.
      *
      * @return the key or null if none exist
      */
-    CompletableFuture<K> firstKey();
+    CompletableFuture<String> firstKey();
 
     /**
      * Return the highest key in the map.
      *
      * @return the key or null if none exist
      */
-    CompletableFuture<K> lastKey();
+    CompletableFuture<String> lastKey();
 
     /**
      * Returns the entry associated with the least key greater than or equal to
@@ -49,7 +52,8 @@
      * @param key the key
      * @return the entry or null if no suitable key exists
      */
-    CompletableFuture<Map.Entry<K, Versioned<V>>> ceilingEntry(K key);
+    CompletableFuture<Map.Entry<String, Versioned<V>>> ceilingEntry(
+            String key);
 
     /**
      * Returns the entry associated with the greatest key less than or equal
@@ -58,7 +62,7 @@
      * @param key the key
      * @return the entry or null if no suitable key exists
      */
-    CompletableFuture<Map.Entry<K, Versioned<V>>> floorEntry(K key);
+    CompletableFuture<Map.Entry<String, Versioned<V>>> floorEntry(String key);
 
     /**
      * Returns the entry associated with the least key greater than key.
@@ -66,7 +70,7 @@
      * @param key the key
      * @return the entry or null if no suitable key exists
      */
-    CompletableFuture<Map.Entry<K, Versioned<V>>> higherEntry(K key);
+    CompletableFuture<Map.Entry<String, Versioned<V>>> higherEntry(String key);
 
     /**
      * Returns the entry associated with the largest key less than key.
@@ -74,35 +78,35 @@
      * @param key the key
      * @return the entry or null if no suitable key exists
      */
-    CompletableFuture<Map.Entry<K, Versioned<V>>> lowerEntry(K key);
+    CompletableFuture<Map.Entry<String, Versioned<V>>> lowerEntry(String key);
 
     /**
      * Return the entry associated with the lowest key in the map.
      *
      * @return the entry or null if none exist
      */
-    CompletableFuture<Map.Entry<K, Versioned<V>>> firstEntry();
+    CompletableFuture<Map.Entry<String, Versioned<V>>> firstEntry();
 
     /**
      * Return the entry associated with the highest key in the map.
      *
      * @return the entry or null if none exist
      */
-    CompletableFuture<Map.Entry<K, Versioned<V>>> lastEntry();
+    CompletableFuture<Map.Entry<String, Versioned<V>>> lastEntry();
 
     /**
      * Return and remove the entry associated with the lowest key.
      *
      * @return the entry or null if none exist
      */
-    CompletableFuture<Map.Entry<K, Versioned<V>>> pollFirstEntry();
+    CompletableFuture<Map.Entry<String, Versioned<V>>> pollFirstEntry();
 
     /**
      * Return and remove the entry associated with the highest key.
      *
      * @return the entry or null if none exist
      */
-    CompletableFuture<Map.Entry<K, Versioned<V>>> pollLastEntry();
+    CompletableFuture<Map.Entry<String, Versioned<V>>> pollLastEntry();
 
     /**
      * Return the entry associated with the greatest key less than key.
@@ -110,7 +114,7 @@
      * @param key the key
      * @return the entry or null if no suitable key exists
      */
-    CompletableFuture<K> lowerKey(K key);
+    CompletableFuture<String> lowerKey(String key);
 
     /**
      * Return the highest key less than or equal to key.
@@ -118,7 +122,7 @@
      * @param key the key
      * @return the entry or null if no suitable key exists
      */
-    CompletableFuture<K> floorKey(K key);
+    CompletableFuture<String> floorKey(String key);
 
     /**
      * Return the lowest key greater than or equal to key.
@@ -126,7 +130,7 @@
      * @param key the key
      * @return the entry or null if no suitable key exists
      */
-    CompletableFuture<K> ceilingKey(K key);
+    CompletableFuture<String> ceilingKey(String key);
 
     /**
      * Return the lowest key greater than key.
@@ -134,14 +138,14 @@
      * @param key the key
      * @return the entry or null if no suitable key exists
      */
-    CompletableFuture<K> higherKey(K key);
+    CompletableFuture<String> higherKey(String key);
 
     /**
      * Returns a navigable set of the keys in this map.
      *
      * @return a navigable key set (this may be empty)
      */
-    CompletableFuture<NavigableSet<K>> navigableKeySet();
+    CompletableFuture<NavigableSet<String>> navigableKeySet();
 
     /**
      * Returns a navigable map containing the entries from the original map
@@ -157,15 +161,16 @@
      * @return a navigable map containing entries in the specified range (this
      * may be empty)
      */
-    CompletableFuture<NavigableMap<K, V>> subMap(K upperKey, K lowerKey,
-                                                 boolean inclusiveUpper,
-                                                 boolean inclusiveLower);
+    CompletableFuture<NavigableMap<String, V>> subMap(String upperKey,
+                                                      String lowerKey,
+                                                      boolean inclusiveUpper,
+                                                      boolean inclusiveLower);
 
-    default ConsistentTreeMap<K, V> asTreeMap() {
-        return asTreeMap(DistributedPrimitive.DEFAULT_OPERTATION_TIMEOUT_MILLIS);
+    default ConsistentTreeMap<V> asTreeMap() {
+        return asTreeMap(DEFAULT_OPERTATION_TIMEOUT_MILLIS);
     }
 
-    default ConsistentTreeMap<K, V> asTreeMap(long timeoutMillis) {
+    default ConsistentTreeMap<V> asTreeMap(long timeoutMillis) {
         return new DefaultConsistentTreeMap<>(this, timeoutMillis);
     }
 
diff --git a/core/api/src/main/java/org/onosproject/store/service/ConsistentTreeMap.java b/core/api/src/main/java/org/onosproject/store/service/ConsistentTreeMap.java
index 18a3410..eb62cac 100644
--- a/core/api/src/main/java/org/onosproject/store/service/ConsistentTreeMap.java
+++ b/core/api/src/main/java/org/onosproject/store/service/ConsistentTreeMap.java
@@ -17,26 +17,27 @@
 package org.onosproject.store.service;
 
 import java.util.Map;
+import java.util.NavigableMap;
 import java.util.NavigableSet;
 
 /**
  * Tree map interface counterpart to {@link AsyncConsistentTreeMap}.
  */
- public interface ConsistentTreeMap<K, V> extends ConsistentMap<K, V> {
+ public interface ConsistentTreeMap<V> extends ConsistentMap<String, V> {
 
     /**
      * Returns the lowest key in the map.
      *
      * @return the key or null if none exist
      */
-     K firstKey();
+     String firstKey();
 
     /**
      * Returns the highest key in the map.
      *
      * @return the key or null if none exist
      */
-     K lastKey();
+     String lastKey();
 
     /**
      * Returns the entry associated with the least key greater than or equal to the key.
@@ -44,7 +45,7 @@
      * @param key the key
      * @return the entry or null
      */
-     Map.Entry<K, Versioned<V>> ceilingEntry(K key);
+     Map.Entry<String, Versioned<V>> ceilingEntry(String key);
 
     /**
      * Returns the entry associated with the greatest key less than or equal to key.
@@ -52,7 +53,7 @@
      * @param key the key
      * @return the entry or null
      */
-     Map.Entry<K, Versioned<V>> floorEntry(K key);
+     Map.Entry<String, Versioned<V>> floorEntry(String key);
 
     /**
      * Returns the entry associated with the lest key greater than key.
@@ -60,7 +61,7 @@
      * @param key the key
      * @return the entry or null
      */
-     Map.Entry<K, Versioned<V>> higherEntry(K key);
+     Map.Entry<String, Versioned<V>> higherEntry(String key);
 
     /**
      * Returns the entry associated with the largest key less than key.
@@ -68,35 +69,35 @@
      * @param key the key
      * @return the entry or null
      */
-     Map.Entry<K, Versioned<V>> lowerEntry(K key);
+     Map.Entry<String, Versioned<V>> lowerEntry(String key);
 
     /**
      * Returns the entry associated with the lowest key in the map.
      *
      * @return the entry or null
      */
-     Map.Entry<K, Versioned<V>> firstEntry();
+     Map.Entry<String, Versioned<V>> firstEntry();
 
     /**
      * Returns the entry associated with the highest key in the map.
      *
      * @return the entry or null
      */
-     Map.Entry<K, Versioned<V>> lastEntry();
+     Map.Entry<String, Versioned<V>> lastEntry();
 
     /**
      * Returns and removes the entry associated with the lowest key.
      *
      * @return the entry or null
      */
-     Map.Entry<K, Versioned<V>> pollFirstEntry();
+     Map.Entry<String, Versioned<V>> pollFirstEntry();
 
     /**
      * Returns and removes the entry associated with the highest key.
      *
      * @return the entry or null
      */
-     Map.Entry<K, Versioned<V>> pollLastEntry();
+     Map.Entry<String, Versioned<V>> pollLastEntry();
 
     /**
      * Returns the entry associated with the greatest key less than key.
@@ -104,7 +105,7 @@
      * @param key the key
      * @return the entry or null
      */
-     K lowerKey(K key);
+     String lowerKey(String key);
 
     /**
      * Returns the entry associated with the highest key less than or equal to key.
@@ -112,7 +113,7 @@
      * @param key the key
      * @return the entry or null
      */
-     K floorKey(K key);
+     String floorKey(String key);
 
     /**
      * Returns the lowest key greater than or equal to key.
@@ -120,7 +121,7 @@
      * @param key the key
      * @return the key or null
      */
-     K ceilingKey(K key);
+     String ceilingKey(String key);
 
     /**
      * Returns the lowest key greater than key.
@@ -128,13 +129,32 @@
      * @param key the key
      * @return the key or null
      */
-     K higherKey(K key);
+     String higherKey(String key);
 
     /**
      * Returns a navigable set of the keys in this map.
      *
      * @return a navigable key set
      */
-     NavigableSet<K> navigableKeySet();
+     NavigableSet<String> navigableKeySet();
+
+    /**
+     * Returns a navigable map containing the entries from the original map
+     * which are larger than (or if specified equal to) {@code lowerKey} AND
+     * less than (or if specified equal to) {@code upperKey}.
+     *
+     * @param upperKey the upper bound for the keys in this map
+     * @param lowerKey the lower bound for the keys in this map
+     * @param inclusiveUpper whether keys equal to the upperKey should be
+     *                       included
+     * @param inclusiveLower whether keys equal to the lowerKey should be
+     *                       included
+     * @return a navigable map containing entries in the specified range (this
+     * may be empty)
+     */
+    NavigableMap<String, V> subMap(String upperKey,
+                                   String lowerKey,
+                                   boolean inclusiveUpper,
+                                   boolean inclusiveLower);
 
 }
diff --git a/core/store/primitives/src/main/java/org/onosproject/store/primitives/resources/impl/AtomixConsistentTreeMap.java b/core/store/primitives/src/main/java/org/onosproject/store/primitives/resources/impl/AtomixConsistentTreeMap.java
index 3baadde..758a36c 100644
--- a/core/store/primitives/src/main/java/org/onosproject/store/primitives/resources/impl/AtomixConsistentTreeMap.java
+++ b/core/store/primitives/src/main/java/org/onosproject/store/primitives/resources/impl/AtomixConsistentTreeMap.java
@@ -74,7 +74,7 @@
  */
 @ResourceTypeInfo(id = -155, factory = AtomixConsistentTreeMapFactory.class)
 public class AtomixConsistentTreeMap extends AbstractResource<AtomixConsistentTreeMap>
-        implements AsyncConsistentTreeMap<String, byte[]> {
+        implements AsyncConsistentTreeMap<byte[]> {
 
     private final Map<MapEventListener<String, byte[]>, Executor>
             mapEventListeners = Maps.newConcurrentMap();