diff --git a/apps/segmentrouting/app/src/main/java/org/onosproject/segmentrouting/HostHandler.java b/apps/segmentrouting/app/src/main/java/org/onosproject/segmentrouting/HostHandler.java
index f71c1d0..3982731 100644
--- a/apps/segmentrouting/app/src/main/java/org/onosproject/segmentrouting/HostHandler.java
+++ b/apps/segmentrouting/app/src/main/java/org/onosproject/segmentrouting/HostHandler.java
@@ -27,8 +27,8 @@
 import org.onosproject.net.HostLocation;
 import org.onosproject.net.PortNumber;
 import org.onosproject.net.host.HostEvent;
-import org.onosproject.net.host.HostLocationProbingService.ProbeMode;
 import org.onosproject.net.host.HostService;
+import org.onosproject.net.host.ProbeMode;
 import org.slf4j.Logger;
 import org.slf4j.LoggerFactory;
 
@@ -185,6 +185,9 @@
 
         // For each old location
         Sets.difference(prevLocations, newLocations).forEach(prevLocation -> {
+            // First of all, verify each old location
+            srManager.probingService.probeHost(host, prevLocation, ProbeMode.VERIFY);
+
             // Remove routing rules for old IPs
             Sets.difference(prevIps, newIps).forEach(ip -> {
                 if (doubleTaggedHost) {
@@ -392,7 +395,7 @@
             srManager.getPairDeviceId(cp.deviceId())
                     .ifPresent(pairDeviceId -> srManager.hostService.getConnectedHosts(pairDeviceId).stream()
                             .filter(host -> isHostInVlanOfPort(host, pairDeviceId, cp))
-                            .forEach(host -> srManager.probingService.probeHostLocation(host, cp, ProbeMode.DISCOVER))
+                            .forEach(host -> srManager.probingService.probeHost(host, cp, ProbeMode.DISCOVER))
                     );
         }
     }
@@ -435,7 +438,7 @@
                 .filter(i -> !i.connectPoint().port().equals(pairRemotePort))
                 .forEach(i -> {
                     log.debug("Probing host {} on pair device {}", host.id(), i.connectPoint());
-                    srManager.probingService.probeHostLocation(host, i.connectPoint(), ProbeMode.DISCOVER);
+                    srManager.probingService.probeHost(host, i.connectPoint(), ProbeMode.DISCOVER);
                 });
     }
 
diff --git a/apps/segmentrouting/app/src/main/java/org/onosproject/segmentrouting/SegmentRoutingManager.java b/apps/segmentrouting/app/src/main/java/org/onosproject/segmentrouting/SegmentRoutingManager.java
index 317e7f4..52ca18e 100644
--- a/apps/segmentrouting/app/src/main/java/org/onosproject/segmentrouting/SegmentRoutingManager.java
+++ b/apps/segmentrouting/app/src/main/java/org/onosproject/segmentrouting/SegmentRoutingManager.java
@@ -77,7 +77,7 @@
 import org.onosproject.net.flowobjective.FlowObjectiveService;
 import org.onosproject.net.host.HostEvent;
 import org.onosproject.net.host.HostListener;
-import org.onosproject.net.host.HostLocationProbingService;
+import org.onosproject.net.host.HostProbingService;
 import org.onosproject.net.host.HostService;
 import org.onosproject.net.host.InterfaceIpAddress;
 import org.onosproject.net.intent.WorkPartitionService;
@@ -186,7 +186,7 @@
     HostService hostService;
 
     @Reference(cardinality = ReferenceCardinality.MANDATORY_UNARY)
-    HostLocationProbingService probingService;
+    HostProbingService probingService;
 
     @Reference(cardinality = ReferenceCardinality.MANDATORY_UNARY)
     public DeviceService deviceService;
diff --git a/apps/segmentrouting/app/src/test/java/org/onosproject/segmentrouting/HostHandlerTest.java b/apps/segmentrouting/app/src/test/java/org/onosproject/segmentrouting/HostHandlerTest.java
index 26420ac..6783da3 100644
--- a/apps/segmentrouting/app/src/test/java/org/onosproject/segmentrouting/HostHandlerTest.java
+++ b/apps/segmentrouting/app/src/test/java/org/onosproject/segmentrouting/HostHandlerTest.java
@@ -28,7 +28,7 @@
 import org.onlab.packet.MacAddress;
 import org.onlab.packet.VlanId;
 import org.onosproject.net.config.ConfigApplyDelegate;
-import org.onosproject.net.host.HostLocationProbingService;
+import org.onosproject.net.host.ProbeMode;
 import org.onosproject.net.intf.Interface;
 import org.onosproject.net.ConnectPoint;
 import org.onosproject.net.DefaultHost;
@@ -182,7 +182,7 @@
     private static final Set<Interface> INTERFACES = Sets.newHashSet(INTF11, INTF12, INTF13, INTF21,
             INTF22, INTF31, INTF32, INTF39, INTF41, INTF49);
 
-    private MockLocationProbingService mockLocationProbingService;
+    private MockHostProbingService mockLocationProbingService;
 
     @Before
     public void setUp() throws Exception {
@@ -218,7 +218,7 @@
         srManager.mastershipService = new MockMastershipService(LOCAL_DEVICES);
         srManager.hostService = new MockHostService(HOSTS);
         srManager.cfgService = mockNetworkConfigRegistry;
-        mockLocationProbingService = new MockLocationProbingService();
+        mockLocationProbingService = new MockHostProbingService();
         srManager.probingService = mockLocationProbingService;
         srManager.linkHandler = new MockLinkHandler(srManager);
 
@@ -351,7 +351,7 @@
         assertEquals(P1, BRIDGING_TABLE.get(new MockBridgingTableKey(DEV3, HOST_MAC, INTF_VLAN_UNTAGGED)).portNumber);
         assertEquals(P9, BRIDGING_TABLE.get(new MockBridgingTableKey(DEV4, HOST_MAC, INTF_VLAN_UNTAGGED)).portNumber);
         // Expect probe to be sent out on pair device
-        assertTrue(mockLocationProbingService.verifyProbe(host1, CP41, HostLocationProbingService.ProbeMode.DISCOVER));
+        assertTrue(mockLocationProbingService.verifyProbe(host1, CP41, ProbeMode.DISCOVER));
 
         // Add the second location of dual-homed host
         // Expect: no longer use the pair link
@@ -753,7 +753,7 @@
         assertEquals(P1, BRIDGING_TABLE.get(new MockBridgingTableKey(DEV3, HOST_MAC, INTF_VLAN_UNTAGGED)).portNumber);
         assertEquals(P9, BRIDGING_TABLE.get(new MockBridgingTableKey(DEV4, HOST_MAC, INTF_VLAN_UNTAGGED)).portNumber);
         // Expect probe to be sent out on pair device
-        assertTrue(mockLocationProbingService.verifyProbe(host2, CP41, HostLocationProbingService.ProbeMode.DISCOVER));
+        assertTrue(mockLocationProbingService.verifyProbe(host2, CP41, ProbeMode.DISCOVER));
 
         // Discover location
         // Expect: cancel all redirections
diff --git a/apps/segmentrouting/app/src/test/java/org/onosproject/segmentrouting/MockLocationProbingService.java b/apps/segmentrouting/app/src/test/java/org/onosproject/segmentrouting/MockHostProbingService.java
similarity index 88%
rename from apps/segmentrouting/app/src/test/java/org/onosproject/segmentrouting/MockLocationProbingService.java
rename to apps/segmentrouting/app/src/test/java/org/onosproject/segmentrouting/MockHostProbingService.java
index b0cdf43..807db0c 100644
--- a/apps/segmentrouting/app/src/test/java/org/onosproject/segmentrouting/MockLocationProbingService.java
+++ b/apps/segmentrouting/app/src/test/java/org/onosproject/segmentrouting/MockHostProbingService.java
@@ -19,12 +19,13 @@
 import com.google.common.collect.Lists;
 import org.onosproject.net.ConnectPoint;
 import org.onosproject.net.Host;
-import org.onosproject.net.host.HostLocationProbingService;
+import org.onosproject.net.host.HostProbingService;
+import org.onosproject.net.host.ProbeMode;
 
 import java.util.List;
 import java.util.Objects;
 
-public class MockLocationProbingService implements HostLocationProbingService {
+public class MockHostProbingService implements HostProbingService {
     List<Probe> probes;
 
     private class Probe {
@@ -58,7 +59,7 @@
         }
     }
 
-    MockLocationProbingService() {
+    MockHostProbingService() {
         probes = Lists.newArrayList();
     }
 
@@ -68,7 +69,7 @@
     }
 
     @Override
-    public void probeHostLocation(Host host, ConnectPoint connectPoint, ProbeMode probeMode) {
+    public void probeHost(Host host, ConnectPoint connectPoint, ProbeMode probeMode) {
         probes.add(new Probe(host, connectPoint, probeMode));
     }
 }
diff --git a/core/api/src/main/java/org/onosproject/net/host/HostLocationProbingService.java b/core/api/src/main/java/org/onosproject/net/host/HostLocationProbingService.java
index 56d056c..66f1266 100644
--- a/core/api/src/main/java/org/onosproject/net/host/HostLocationProbingService.java
+++ b/core/api/src/main/java/org/onosproject/net/host/HostLocationProbingService.java
@@ -1,5 +1,5 @@
 /*
- * Copyright 2017-present Open Networking Foundation
+ * Copyright 2018-present Open Networking Foundation
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -18,31 +18,21 @@
 import org.onosproject.net.ConnectPoint;
 import org.onosproject.net.Host;
 
+/**
+ * Service for interacting with the host probing entities.
+ *
+ * @deprecated in ONOS 1.12, replaced by {@link HostProbingService}
+ */
+@Deprecated
 public interface HostLocationProbingService {
     /**
-     * Mode of host location probing.
-     */
-    enum ProbeMode {
-        /**
-         * Append probed host location if reply is received before timeout. Otherwise, do nothing.
-         * Typically used to discover secondary locations.
-         */
-        DISCOVER,
-
-        /**
-         * Remove probed host location if reply is received after timeout. Otherwise, do nothing.
-         * Typically used to verify previous locations.
-         */
-        VERIFY
-    }
-
-    /**
      * Probes given host on given location.
      *
      * @param host the host to be probed
      * @param connectPoint the location of host to be probed
      * @param probeMode probe mode
+     * @deprecated in ONOS 1.12, replaced by {@link HostProbingService#probeHost(Host, ConnectPoint, ProbeMode)}
      */
-    void probeHostLocation(Host host, ConnectPoint connectPoint, ProbeMode probeMode);
-
+    @Deprecated
+    void probeHost(Host host, ConnectPoint connectPoint, ProbeMode probeMode);
 }
diff --git a/core/api/src/main/java/org/onosproject/net/host/HostProbe.java b/core/api/src/main/java/org/onosproject/net/host/HostProbe.java
new file mode 100644
index 0000000..7303a3d
--- /dev/null
+++ b/core/api/src/main/java/org/onosproject/net/host/HostProbe.java
@@ -0,0 +1,58 @@
+/*
+ * Copyright 2018-present Open Networking Foundation
+ *
+ * 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.
+ */
+package org.onosproject.net.host;
+
+import org.onlab.packet.MacAddress;
+import org.onosproject.net.ConnectPoint;
+import org.onosproject.net.Host;
+
+/**
+ * Information related to the host being probed.
+ */
+public interface HostProbe extends Host {
+    /**
+     * Gets connect point of this entry.
+     *
+     * @return connect point
+     */
+    ConnectPoint connectPoint();
+
+    /**
+     * Gets retry counter of this entry.
+     *
+     * @return retry
+     */
+    int retry();
+
+    /**
+     * Decrease retry counter of this entry by one.
+     */
+    void decreaseRetry();
+
+    /**
+     * Gets mode of this entry.
+     *
+     * @return mode
+     */
+    ProbeMode mode();
+
+    /**
+     * Gets probe MAC of this entry.
+     *
+     * @return probe mac
+     */
+    MacAddress probeMac();
+}
diff --git a/core/api/src/main/java/org/onosproject/net/host/HostProbeStore.java b/core/api/src/main/java/org/onosproject/net/host/HostProbeStore.java
new file mode 100644
index 0000000..ba1217d
--- /dev/null
+++ b/core/api/src/main/java/org/onosproject/net/host/HostProbeStore.java
@@ -0,0 +1,49 @@
+/*
+ * Copyright 2018-present Open Networking Foundation
+ *
+ * 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.
+ */
+package org.onosproject.net.host;
+
+import org.onlab.packet.MacAddress;
+import org.onosproject.net.ConnectPoint;
+import org.onosproject.net.Host;
+import org.onosproject.store.Store;
+
+/**
+ * Manages inventory of pending host probes.
+ */
+public interface HostProbeStore extends Store<HostProbingEvent, HostProbingStoreDelegate> {
+
+    /**
+     * Notifies HostProbeStore the beginning of pending host location verification and
+     * retrieves the unique MAC address for the probe.
+     *
+     * @param host host to be probed
+     * @param connectPoint the connect point that is under verification
+     * @param probeMode probe mode
+     * @param probeMac probeMac if this is a retry.
+     *                 Null if this is the very first probe and the probeMac is to-be-generated
+     * @param retry max retry times
+     * @return probeMac, the source MAC address ONOS uses to probe the host
+     */
+    MacAddress addProbingHost(Host host, ConnectPoint connectPoint, ProbeMode probeMode,
+                                      MacAddress probeMac, int retry);
+
+    /**
+     * Notifies HostProbeStore the end of pending host location verification.
+     *
+     * @param probeMac the source MAC address ONOS uses to probe the host
+     */
+    void removeProbingHost(MacAddress probeMac);
+}
diff --git a/core/api/src/main/java/org/onosproject/net/host/HostProbingEvent.java b/core/api/src/main/java/org/onosproject/net/host/HostProbingEvent.java
new file mode 100644
index 0000000..b77334a
--- /dev/null
+++ b/core/api/src/main/java/org/onosproject/net/host/HostProbingEvent.java
@@ -0,0 +1,123 @@
+/*
+ * Copyright 2014-present Open Networking Foundation
+ *
+ * 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.
+ */
+package org.onosproject.net.host;
+
+import org.onlab.util.Tools;
+import org.onosproject.event.AbstractEvent;
+
+import static com.google.common.base.MoreObjects.toStringHelper;
+
+/**
+ * Describes host probing event.
+ */
+public class HostProbingEvent extends AbstractEvent<HostProbingEvent.Type, HostProbe> {
+
+    /**
+     * Type of host probing events.
+     */
+    public enum Type {
+        /**
+         * Probe has been requested.
+         */
+        PROBE_REQUESTED,
+
+        /**
+         * Probe timed out but still have not reach max retry.
+         */
+        PROBE_TIMEOUT,
+
+        /**
+         * Probe timed out and reach max retry.
+         */
+        PROBE_FAIL,
+
+        /**
+         * Probe has been complete normally.
+         */
+        PROBE_COMPLETED
+    }
+
+    private HostProbe prevSubject;
+
+    /**
+     * Creates an event of a given type and for the specified host probe and the
+     * current time.
+     *
+     * @param type probing host event type
+     * @param subject event subject
+     */
+    public HostProbingEvent(Type type, HostProbe subject) {
+        super(type, subject);
+    }
+
+    /**
+     * Creates an event of a given type and for the specified host probe and time.
+     *
+     * @param type probing host event type
+     * @param subject event subject
+     * @param time occurrence time
+     */
+    public HostProbingEvent(Type type, HostProbe subject, long time) {
+        super(type, subject, time);
+    }
+
+    /**
+     * Creates an event with previous subject.
+     * The previous subject is ignored if the type is not PROBE_TIMEOUT
+     *
+     * @param type host event type
+     * @param subject event subject
+     * @param prevSubject previous host subject
+     */
+    public HostProbingEvent(Type type, HostProbe subject, HostProbe prevSubject) {
+        super(type, subject);
+        this.prevSubject = prevSubject;
+    }
+
+    /**
+     * Creates an event with previous subject and specified time.
+     * The previous subject is ignored if the type is not PROBE_TIMEOUT
+     *
+     * @param type host event type
+     * @param subject event subject
+     * @param prevSubject previous host subject
+     * @param time occurrence time
+     */
+    public HostProbingEvent(Type type, HostProbe subject, HostProbe prevSubject, long time) {
+        super(type, subject, time);
+        this.prevSubject = prevSubject;
+    }
+
+    /**
+     * Gets the previous subject in this host probe event.
+     *
+     * @return the previous subject, or null if previous subject is not
+     *         specified.
+     */
+    public HostProbe prevSubject() {
+        return this.prevSubject;
+    }
+
+    @Override
+    public String toString() {
+        return toStringHelper(this)
+                .add("time", Tools.defaultOffsetDataTime(time()))
+                .add("type", type())
+                .add("subject", subject())
+                .add("prevSubject", prevSubject())
+                .toString();
+    }
+}
diff --git a/core/api/src/main/java/org/onosproject/net/host/HostProbingListener.java b/core/api/src/main/java/org/onosproject/net/host/HostProbingListener.java
new file mode 100644
index 0000000..25fd1ea
--- /dev/null
+++ b/core/api/src/main/java/org/onosproject/net/host/HostProbingListener.java
@@ -0,0 +1,24 @@
+/*
+ * Copyright 2018-present Open Networking Foundation
+ *
+ * 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.
+ */
+package org.onosproject.net.host;
+
+import org.onosproject.event.EventListener;
+
+/**
+ * Entity capable of receiving host probing related events.
+ */
+public interface HostProbingListener extends EventListener<HostProbingEvent> {
+}
diff --git a/core/api/src/main/java/org/onosproject/net/host/HostProbingProvider.java b/core/api/src/main/java/org/onosproject/net/host/HostProbingProvider.java
new file mode 100644
index 0000000..f126013
--- /dev/null
+++ b/core/api/src/main/java/org/onosproject/net/host/HostProbingProvider.java
@@ -0,0 +1,42 @@
+/*
+ * Copyright 2018-present Open Networking Foundation
+ *
+ * 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.
+ */
+package org.onosproject.net.host;
+
+import org.onosproject.net.ConnectPoint;
+import org.onosproject.net.Host;
+import org.onosproject.net.provider.Provider;
+
+/**
+ * Provider of host probing.
+ */
+public interface HostProbingProvider extends Provider {
+
+    /**
+     * Probe given host on the given connectPoint with given probeMode.
+     *
+     * @param host host to be probed
+     * @param connectPoint connect point on which the probe is sent
+     * @param probeMode probe mode
+     */
+    void probeHost(Host host, ConnectPoint connectPoint, ProbeMode probeMode);
+
+    /**
+     * Process host probing events.
+     *
+     * @param event host probing event
+     */
+    void processEvent(HostProbingEvent event);
+}
diff --git a/core/api/src/main/java/org/onosproject/net/host/HostProbingProviderRegistry.java b/core/api/src/main/java/org/onosproject/net/host/HostProbingProviderRegistry.java
new file mode 100644
index 0000000..915df6c
--- /dev/null
+++ b/core/api/src/main/java/org/onosproject/net/host/HostProbingProviderRegistry.java
@@ -0,0 +1,25 @@
+/*
+ * Copyright 2014-present Open Networking Foundation
+ *
+ * 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.
+ */
+package org.onosproject.net.host;
+
+import org.onosproject.net.provider.ProviderRegistry;
+
+/**
+ * Abstraction of a host probing provider registry.
+ */
+public interface HostProbingProviderRegistry
+        extends ProviderRegistry<HostProbingProvider, HostProbingProviderService> {
+}
diff --git a/core/api/src/main/java/org/onosproject/net/host/HostProbingProviderService.java b/core/api/src/main/java/org/onosproject/net/host/HostProbingProviderService.java
new file mode 100644
index 0000000..d9c7c16
--- /dev/null
+++ b/core/api/src/main/java/org/onosproject/net/host/HostProbingProviderService.java
@@ -0,0 +1,49 @@
+/*
+ * Copyright 2014-present Open Networking Foundation
+ *
+ * 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.
+ */
+package org.onosproject.net.host;
+
+import org.onlab.packet.MacAddress;
+import org.onosproject.net.ConnectPoint;
+import org.onosproject.net.Host;
+import org.onosproject.net.provider.ProviderService;
+
+/**
+ * Means of conveying host probing information to the core.
+ */
+public interface HostProbingProviderService extends ProviderService<HostProbingProvider> {
+
+    /**
+     * Notifies HostProbeStore the beginning of pending host location verification and
+     * retrieves the unique MAC address for the probe.
+     *
+     * @param host host to be probed
+     * @param connectPoint the connect point that is under verification
+     * @param probeMode probe mode
+     * @param probeMac probeMac if this is a retry.
+     *                 Null if this is the very first probe and the probeMac is to-be-generated
+     * @param retry max retry times
+     * @return probeMac, the source MAC address ONOS uses to probe the host
+     */
+     MacAddress addProbingHost(Host host, ConnectPoint connectPoint, ProbeMode probeMode,
+                                      MacAddress probeMac, int retry);
+
+    /**
+     * Notifies HostProbeStore the end of pending host location verification.
+     *
+     * @param probeMac the source MAC address ONOS uses to probe the host
+     */
+     void removeProbingHost(MacAddress probeMac);
+}
diff --git a/core/api/src/main/java/org/onosproject/net/host/HostProbingService.java b/core/api/src/main/java/org/onosproject/net/host/HostProbingService.java
new file mode 100644
index 0000000..6113dd4
--- /dev/null
+++ b/core/api/src/main/java/org/onosproject/net/host/HostProbingService.java
@@ -0,0 +1,33 @@
+/*
+ * Copyright 2018-present Open Networking Foundation
+ *
+ * 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.
+ */
+package org.onosproject.net.host;
+
+import org.onosproject.net.ConnectPoint;
+import org.onosproject.net.Host;
+
+/**
+ * Service for interacting with the host probing entities.
+ */
+public interface HostProbingService {
+    /**
+     * Probes given host on given location.
+     *
+     * @param host the host to be probed
+     * @param connectPoint the location of host to be probed
+     * @param probeMode probe mode
+     */
+    void probeHost(Host host, ConnectPoint connectPoint, ProbeMode probeMode);
+}
diff --git a/core/api/src/main/java/org/onosproject/net/host/HostProbingStoreDelegate.java b/core/api/src/main/java/org/onosproject/net/host/HostProbingStoreDelegate.java
new file mode 100644
index 0000000..5221951
--- /dev/null
+++ b/core/api/src/main/java/org/onosproject/net/host/HostProbingStoreDelegate.java
@@ -0,0 +1,24 @@
+/*
+ * Copyright 2018-present Open Networking Foundation
+ *
+ * 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.
+ */
+package org.onosproject.net.host;
+
+import org.onosproject.store.StoreDelegate;
+
+/**
+ * Host probing store delegate abstraction.
+ */
+public interface HostProbingStoreDelegate extends StoreDelegate<HostProbingEvent> {
+}
diff --git a/core/api/src/main/java/org/onosproject/net/host/HostProviderService.java b/core/api/src/main/java/org/onosproject/net/host/HostProviderService.java
index d9aeff5..f3dc7ab 100644
--- a/core/api/src/main/java/org/onosproject/net/host/HostProviderService.java
+++ b/core/api/src/main/java/org/onosproject/net/host/HostProviderService.java
@@ -15,12 +15,12 @@
  */
 package org.onosproject.net.host;
 
+import org.apache.commons.lang3.NotImplementedException;
 import org.onlab.packet.IpAddress;
 import org.onlab.packet.MacAddress;
 import org.onosproject.net.ConnectPoint;
 import org.onosproject.net.HostId;
 import org.onosproject.net.HostLocation;
-import org.onosproject.net.host.HostLocationProbingService.ProbeMode;
 import org.onosproject.net.provider.ProviderService;
 
 /**
@@ -54,6 +54,16 @@
     void removeIpFromHost(HostId hostId, IpAddress ipAddress);
 
     /**
+     * Notifies the core when a location is associated with a host.
+     *
+     * @param hostId id of the host
+     * @param location location of host that gets discovered
+     */
+    default void addLocationToHost(HostId hostId, HostLocation location) {
+        throw new NotImplementedException("addLocationToHost is not implemented");
+    }
+
+    /**
      * Notifies the core when a location is no longer associated with a host.
      *
      * @param hostId id of the host
@@ -69,7 +79,9 @@
      * @param connectPoint the connect point that is under verification
      * @param probeMode probe mode
      * @return probeMac, the source MAC address ONOS uses to probe the host
+     * @deprecated in ONOS 1.12, replaced by {@link HostProbingProviderService}
      */
+    @Deprecated
     default MacAddress addPendingHostLocation(HostId hostId, ConnectPoint connectPoint, ProbeMode probeMode) {
         return MacAddress.NONE;
     }
@@ -78,6 +90,8 @@
      * Notifies HostProviderService the end of pending host location verification.
      *
      * @param probeMac the source MAC address ONOS uses to probe the host
+     * @deprecated in ONOS 1.12, replaced by {@link HostProbingProviderService}
      */
+    @Deprecated
     default void removePendingHostLocation(MacAddress probeMac) {}
 }
diff --git a/core/api/src/main/java/org/onosproject/net/host/HostStore.java b/core/api/src/main/java/org/onosproject/net/host/HostStore.java
index 96d3c31..0b6238b 100644
--- a/core/api/src/main/java/org/onosproject/net/host/HostStore.java
+++ b/core/api/src/main/java/org/onosproject/net/host/HostStore.java
@@ -23,7 +23,6 @@
 import org.onosproject.net.Host;
 import org.onosproject.net.HostId;
 import org.onosproject.net.HostLocation;
-import org.onosproject.net.host.HostLocationProbingService.ProbeMode;
 import org.onosproject.net.provider.ProviderId;
 import org.onosproject.store.Store;
 
diff --git a/core/api/src/main/java/org/onosproject/net/host/ProbeMode.java b/core/api/src/main/java/org/onosproject/net/host/ProbeMode.java
new file mode 100644
index 0000000..bc3efbf
--- /dev/null
+++ b/core/api/src/main/java/org/onosproject/net/host/ProbeMode.java
@@ -0,0 +1,33 @@
+/*
+ * Copyright 2018-present Open Networking Foundation
+ *
+ * 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.
+ */
+package org.onosproject.net.host;
+
+/**
+ * Mode of host location probing.
+ */
+public enum ProbeMode {
+    /**
+     * Append probed host location if reply is received before timeout. Otherwise, do nothing.
+     * Typically used to discover secondary locations.
+     */
+    DISCOVER,
+
+    /**
+     * Remove probed host location if reply is received after timeout. Otherwise, do nothing.
+     * Typically used to verify previous locations.
+     */
+    VERIFY
+}
diff --git a/core/net/src/main/java/org/onosproject/net/host/impl/HostManager.java b/core/net/src/main/java/org/onosproject/net/host/impl/HostManager.java
index 998f7df..31e8904 100644
--- a/core/net/src/main/java/org/onosproject/net/host/impl/HostManager.java
+++ b/core/net/src/main/java/org/onosproject/net/host/impl/HostManager.java
@@ -29,7 +29,6 @@
 import org.onlab.packet.VlanId;
 import org.onlab.util.Tools;
 import org.onosproject.cfg.ComponentConfigService;
-import org.onosproject.net.host.HostLocationProbingService.ProbeMode;
 import org.onosproject.net.intf.Interface;
 import org.onosproject.net.intf.InterfaceService;
 import org.onosproject.net.HostLocation;
@@ -442,6 +441,20 @@
         }
 
         @Override
+        public void addLocationToHost(HostId hostId, HostLocation location) {
+            checkNotNull(hostId, HOST_ID_NULL);
+            checkValidity();
+
+            if (!allowedToChange(hostId)) {
+                log.info("Request to remove {} from {} is ignored due to provider mismatch",
+                        location, hostId);
+                return;
+            }
+
+            store.appendLocation(hostId, location);
+        }
+
+        @Override
         public void removeLocationFromHost(HostId hostId, HostLocation location) {
             checkNotNull(hostId, HOST_ID_NULL);
             checkValidity();
@@ -455,16 +468,6 @@
             store.removeLocation(hostId, location);
         }
 
-        @Override
-        public MacAddress addPendingHostLocation(HostId hostId, ConnectPoint connectPoint, ProbeMode probeMode) {
-            return store.addPendingHostLocation(hostId, connectPoint, probeMode);
-        }
-
-        @Override
-        public void removePendingHostLocation(MacAddress probeMac) {
-            store.removePendingHostLocation(probeMac);
-        }
-
         /**
          * Providers should only be able to remove a host that is provided by itself,
          * or a host that is not configured.
diff --git a/core/net/src/main/java/org/onosproject/net/host/impl/HostProbingManager.java b/core/net/src/main/java/org/onosproject/net/host/impl/HostProbingManager.java
new file mode 100644
index 0000000..648e200
--- /dev/null
+++ b/core/net/src/main/java/org/onosproject/net/host/impl/HostProbingManager.java
@@ -0,0 +1,105 @@
+/*
+ * Copyright 2018-present Open Networking Foundation
+ *
+ * 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.
+ */
+
+package org.onosproject.net.host.impl;
+
+import org.apache.felix.scr.annotations.Activate;
+import org.apache.felix.scr.annotations.Component;
+import org.apache.felix.scr.annotations.Deactivate;
+import org.apache.felix.scr.annotations.Reference;
+import org.apache.felix.scr.annotations.ReferenceCardinality;
+import org.apache.felix.scr.annotations.Service;
+import org.onlab.packet.MacAddress;
+import org.onosproject.net.ConnectPoint;
+import org.onosproject.net.Host;
+import org.onosproject.net.host.HostLocationProbingService;
+import org.onosproject.net.host.HostProbingEvent;
+import org.onosproject.net.host.ProbeMode;
+import org.onosproject.net.host.HostProbingListener;
+import org.onosproject.net.host.HostProbingProvider;
+import org.onosproject.net.host.HostProbingProviderService;
+import org.onosproject.net.host.HostProbingService;
+import org.onosproject.net.host.HostProbeStore;
+import org.onosproject.net.host.HostProbingProviderRegistry;
+import org.onosproject.net.host.HostProbingStoreDelegate;
+import org.onosproject.net.provider.AbstractListenerProviderRegistry;
+import org.onosproject.net.provider.AbstractProviderService;
+import org.slf4j.Logger;
+
+import static org.slf4j.LoggerFactory.getLogger;
+
+@Component(immediate = true)
+@Service
+public class HostProbingManager extends
+        AbstractListenerProviderRegistry<HostProbingEvent, HostProbingListener, HostProbingProvider,
+                HostProbingProviderService>
+        implements HostProbingService, HostProbingProviderRegistry, HostLocationProbingService {
+    private final Logger log = getLogger(getClass());
+
+    @Reference(cardinality = ReferenceCardinality.MANDATORY_UNARY)
+    private HostProbeStore hostProbeStore;
+
+    private static final String SCHEME = "hostprobing";
+
+    private HostProbingStoreDelegate delegate = event -> {
+        getProvider(SCHEME).processEvent(event);
+    };
+
+    @Activate
+    public void activate() {
+        hostProbeStore.setDelegate(delegate);
+    }
+
+    @Deactivate
+    public void deactivate() {
+        hostProbeStore.unsetDelegate(delegate);
+    }
+
+    @Override
+    public void probeHost(Host host, ConnectPoint connectPoint, ProbeMode probeMode) {
+        HostProbingProvider provider = getProvider(SCHEME);
+        if (provider == null) {
+            log.warn("Unable to find host probing provider. Cannot {} {} at {}",
+                    probeMode, host, connectPoint);
+            return;
+        }
+        provider.probeHost(host, connectPoint, probeMode);
+    }
+
+    @Override
+    protected HostProbingProviderService createProviderService(HostProbingProvider provider) {
+        return new InternalHostProbingProviderService(provider);
+    }
+
+    private class InternalHostProbingProviderService
+            extends AbstractProviderService<HostProbingProvider>
+            implements HostProbingProviderService {
+        InternalHostProbingProviderService(HostProbingProvider provider) {
+            super(provider);
+        }
+
+        @Override
+        public MacAddress addProbingHost(Host host, ConnectPoint connectPoint, ProbeMode mode,
+                                         MacAddress probeMac, int retry) {
+            return hostProbeStore.addProbingHost(host, connectPoint, mode, probeMac, retry);
+        }
+
+        @Override
+        public void removeProbingHost(MacAddress probeMac) {
+            hostProbeStore.removeProbingHost(probeMac);
+        }
+    }
+}
diff --git a/core/store/dist/src/main/java/org/onosproject/store/host/impl/DefaultHostProbe.java b/core/store/dist/src/main/java/org/onosproject/store/host/impl/DefaultHostProbe.java
new file mode 100644
index 0000000..5ab72fc
--- /dev/null
+++ b/core/store/dist/src/main/java/org/onosproject/store/host/impl/DefaultHostProbe.java
@@ -0,0 +1,113 @@
+/*
+ * Copyright 2017-present Open Networking Foundation
+ *
+ * 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.
+ */
+
+package org.onosproject.store.host.impl;
+
+import org.onlab.packet.MacAddress;
+import org.onosproject.net.ConnectPoint;
+import org.onosproject.net.DefaultHost;
+import org.onosproject.net.Host;
+import org.onosproject.net.host.ProbeMode;
+import org.onosproject.net.host.HostProbe;
+
+import java.util.Objects;
+
+import static com.google.common.base.MoreObjects.toStringHelper;
+
+/**
+ * Internal data structure to record the info of a host with location that is under verification.
+ */
+class DefaultHostProbe extends DefaultHost implements HostProbe {
+    private ConnectPoint connectPoint;
+    private int retry;
+    private ProbeMode mode;
+    private MacAddress probeMac;
+
+    /**
+     * Constructs DefaultHostProbe with given retry.
+     *
+     * @param host host to be probed
+     * @param connectPoint location to be verified
+     * @param probeMac source MAC address of the probe
+     * @param mode probe mode
+     * @param retry number of retry
+     */
+    DefaultHostProbe(Host host, ConnectPoint connectPoint, ProbeMode mode, MacAddress probeMac, int retry) {
+        super(host.providerId(), host.id(), host.mac(), host.vlan(), host.locations(), host.ipAddresses(),
+                host.configured());
+
+        this.connectPoint = connectPoint;
+        this.mode = mode;
+        this.probeMac = probeMac;
+        this.retry = retry;
+    }
+
+    @Override
+    public ConnectPoint connectPoint() {
+        return connectPoint;
+    }
+
+    @Override
+    public int retry() {
+        return retry;
+    }
+
+    @Override
+    public void decreaseRetry() {
+        this.retry -= 1;
+    }
+
+    @Override
+    public ProbeMode mode() {
+        return mode;
+    }
+
+    @Override
+    public MacAddress probeMac() {
+        return probeMac;
+    }
+
+    @Override
+    public boolean equals(Object o) {
+        if (this == o) {
+            return true;
+        }
+        if (!(o instanceof DefaultHostProbe)) {
+            return false;
+        }
+        DefaultHostProbe that = (DefaultHostProbe) o;
+        return (super.equals(o) &&
+                Objects.equals(this.connectPoint, that.connectPoint) &&
+                Objects.equals(this.retry, that.retry) &&
+                Objects.equals(this.mode, that.mode)) &&
+                Objects.equals(this.probeMac, that.probeMac);
+    }
+    @Override
+    public int hashCode() {
+        return Objects.hash(super.hashCode(), connectPoint, retry, mode, probeMac);
+    }
+
+    @Override
+    public String toString() {
+        return toStringHelper(getClass())
+                .add("host", super.toString())
+                .add("location", connectPoint)
+                .add("retry", retry)
+                .add("mode", mode)
+                .add("probeMac", probeMac)
+                .toString();
+    }
+}
diff --git a/core/store/dist/src/main/java/org/onosproject/store/host/impl/DefaultHostProbeStore.java b/core/store/dist/src/main/java/org/onosproject/store/host/impl/DefaultHostProbeStore.java
new file mode 100644
index 0000000..33cb7ad
--- /dev/null
+++ b/core/store/dist/src/main/java/org/onosproject/store/host/impl/DefaultHostProbeStore.java
@@ -0,0 +1,199 @@
+/*
+ * Copyright 2018-present Open Networking Foundation
+ *
+ * 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.
+ */
+package org.onosproject.store.host.impl;
+
+import com.google.common.cache.Cache;
+import com.google.common.cache.CacheBuilder;
+import com.google.common.cache.RemovalNotification;
+import org.apache.felix.scr.annotations.Activate;
+import org.apache.felix.scr.annotations.Component;
+import org.apache.felix.scr.annotations.Deactivate;
+import org.apache.felix.scr.annotations.Reference;
+import org.apache.felix.scr.annotations.ReferenceCardinality;
+import org.apache.felix.scr.annotations.Service;
+import org.onlab.packet.MacAddress;
+import org.onlab.util.KryoNamespace;
+import org.onosproject.net.ConnectPoint;
+import org.onosproject.net.Host;
+import org.onosproject.net.host.HostProbe;
+import org.onosproject.net.host.HostProbeStore;
+import org.onosproject.net.host.HostProbingEvent;
+import org.onosproject.net.host.ProbeMode;
+import org.onosproject.net.host.HostProbingStoreDelegate;
+import org.onosproject.store.AbstractStore;
+import org.onosproject.store.serializers.KryoNamespaces;
+import org.onosproject.store.service.AtomicCounter;
+import org.onosproject.store.service.ConsistentMap;
+import org.onosproject.store.service.MapEvent;
+import org.onosproject.store.service.MapEventListener;
+import org.onosproject.store.service.Serializer;
+import org.onosproject.store.service.StorageService;
+import org.onosproject.store.service.Versioned;
+import org.slf4j.Logger;
+
+import java.util.Map;
+import java.util.concurrent.ScheduledExecutorService;
+import java.util.concurrent.TimeUnit;
+
+import static java.util.concurrent.Executors.newSingleThreadScheduledExecutor;
+import static org.onlab.util.Tools.groupedThreads;
+import static org.slf4j.LoggerFactory.getLogger;
+
+@Component(immediate = true)
+@Service
+public class DefaultHostProbeStore extends AbstractStore<HostProbingEvent, HostProbingStoreDelegate>
+        implements HostProbeStore {
+    @Reference(cardinality = ReferenceCardinality.MANDATORY_UNARY)
+    protected StorageService storageService;
+
+    private final Logger log = getLogger(getClass());
+
+    // TODO make this configurable
+    private static final int PROBE_TIMEOUT_MS = 3000;
+
+    private AtomicCounter hostProbeIndex;
+    private Cache<MacAddress, HostProbe> probingHostsCache;
+    private ConsistentMap<MacAddress, HostProbe> probingHostsConsistentMap;
+    private Map<MacAddress, HostProbe> probingHosts;
+    private MapEventListener<MacAddress, HostProbe> probingHostListener = new ProbingHostListener();
+    private ScheduledExecutorService cacheCleaner;
+    private ScheduledExecutorService locationRemover;
+
+    @Activate
+    public void activate() {
+        KryoNamespace.Builder pendingHostSerializer = KryoNamespace.newBuilder()
+                .register(KryoNamespaces.API)
+                .register(DefaultHostProbe.class)
+                .register(ProbeMode.class);
+        probingHostsConsistentMap = storageService.<MacAddress, HostProbe>consistentMapBuilder()
+                .withName("onos-hosts-pending")
+                .withRelaxedReadConsistency()
+                .withSerializer(Serializer.using(pendingHostSerializer.build()))
+                .build();
+        probingHostsConsistentMap.addListener(probingHostListener);
+        probingHosts = probingHostsConsistentMap.asJavaMap();
+
+        hostProbeIndex = storageService.atomicCounterBuilder()
+                .withName("onos-hosts-probe-index")
+                .build()
+                .asAtomicCounter();
+
+        probingHostsCache = CacheBuilder.newBuilder()
+                .expireAfterWrite(PROBE_TIMEOUT_MS, TimeUnit.MILLISECONDS)
+                .removalListener((RemovalNotification<MacAddress, HostProbe> notification) -> {
+                    MacAddress probeMac = notification.getKey();
+                    switch (notification.getCause()) {
+                        case EXPIRED:
+                        case REPLACED:
+                            probingHosts.computeIfPresent(probeMac, (k, v) -> {
+                                v.decreaseRetry();
+                                return v;
+                            });
+                            break;
+                        case EXPLICIT:
+                            break;
+                        default:
+                            log.warn("Remove {} from pendingHostLocations for unexpected reason {}",
+                                    notification.getKey(), notification.getCause());
+                    }
+                }).build();
+
+        cacheCleaner = newSingleThreadScheduledExecutor(
+                groupedThreads("onos/host/hostprobestore", "cache-cleaner", log));
+        cacheCleaner.scheduleAtFixedRate(probingHostsCache::cleanUp, 0, PROBE_TIMEOUT_MS, TimeUnit.MILLISECONDS);
+        locationRemover = newSingleThreadScheduledExecutor(
+                groupedThreads("onos/host/hostprobestore", "loc-remover", log));
+
+        log.info("Started");
+    }
+
+    @Deactivate
+    public void deactivate() {
+        cacheCleaner.shutdown();
+        locationRemover.shutdown();
+        probingHostsCache.cleanUp();
+
+        log.info("Stopped");
+    }
+
+    @Override
+    public MacAddress addProbingHost(Host host, ConnectPoint connectPoint, ProbeMode probeMode,
+                                     MacAddress probeMac, int retry) {
+        if (probeMac == null) {
+            probeMac = generateProbeMac();
+        }
+        DefaultHostProbe probingHost = new DefaultHostProbe(host, connectPoint, probeMode, probeMac, retry);
+        probingHostsCache.put(probeMac, probingHost);
+        probingHosts.put(probeMac, probingHost);
+        return probeMac;
+    }
+
+    @Override
+    public void removeProbingHost(MacAddress probeMac) {
+        probingHostsCache.invalidate(probeMac);
+        probingHosts.remove(probeMac);
+    }
+
+    private MacAddress generateProbeMac() {
+        // Use ONLab OUI (3 bytes) + atomic counter (3 bytes) as the source MAC of the probe
+        long nextIndex = hostProbeIndex.incrementAndGet();
+        return MacAddress.valueOf(MacAddress.NONE.toLong() + nextIndex);
+    }
+
+    private class ProbingHostListener implements MapEventListener<MacAddress, HostProbe> {
+        @Override
+        public void event(MapEvent<MacAddress, HostProbe> event) {
+            HostProbe newValue = Versioned.valueOrNull(event.newValue());
+            HostProbe oldValue = Versioned.valueOrNull(event.oldValue());
+
+            HostProbingEvent hostProbingEvent;
+            switch (event.type()) {
+                case INSERT:
+                    hostProbingEvent = new HostProbingEvent(HostProbingEvent.Type.PROBE_REQUESTED, newValue);
+                    notifyDelegate(hostProbingEvent);
+                    break;
+                case UPDATE:
+                    // Fail VERIFY probe immediately. Only allow DISCOVER probe to retry.
+                    if (newValue.retry() > 0) {
+                        if (newValue.mode() == ProbeMode.DISCOVER) {
+                            hostProbingEvent = new HostProbingEvent(HostProbingEvent.Type.PROBE_TIMEOUT,
+                                    newValue, oldValue);
+                            notifyDelegate(hostProbingEvent);
+                        } else {
+                            hostProbingEvent = new HostProbingEvent(HostProbingEvent.Type.PROBE_FAIL,
+                                    newValue, oldValue);
+                            notifyDelegate(hostProbingEvent);
+                        }
+                    } else {
+                        // Remove from pendingHost and let the remove listener generates the event
+                        locationRemover.execute(() -> probingHosts.remove(event.key()));
+                    }
+                    break;
+                case REMOVE:
+                    if (oldValue.retry() > 0) {
+                        hostProbingEvent = new HostProbingEvent(HostProbingEvent.Type.PROBE_COMPLETED, oldValue);
+                        notifyDelegate(hostProbingEvent);
+                    } else {
+                        hostProbingEvent = new HostProbingEvent(HostProbingEvent.Type.PROBE_FAIL, oldValue);
+                        notifyDelegate(hostProbingEvent);
+                    }
+                    break;
+                default:
+                    log.warn("Unknown map event type: {}", event.type());
+            }
+        }
+    }
+}
diff --git a/core/store/dist/src/main/java/org/onosproject/store/host/impl/DistributedHostStore.java b/core/store/dist/src/main/java/org/onosproject/store/host/impl/DistributedHostStore.java
index aa811ba..d179288 100644
--- a/core/store/dist/src/main/java/org/onosproject/store/host/impl/DistributedHostStore.java
+++ b/core/store/dist/src/main/java/org/onosproject/store/host/impl/DistributedHostStore.java
@@ -15,9 +15,6 @@
  */
 package org.onosproject.store.host.impl;
 
-import com.google.common.cache.Cache;
-import com.google.common.cache.CacheBuilder;
-import com.google.common.cache.RemovalNotification;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Sets;
 
@@ -43,18 +40,15 @@
 import org.onosproject.net.host.HostEvent;
 import org.onosproject.net.host.HostStore;
 import org.onosproject.net.host.HostStoreDelegate;
-import org.onosproject.net.host.HostLocationProbingService.ProbeMode;
 import org.onosproject.net.provider.ProviderId;
 import org.onosproject.store.AbstractStore;
 import org.onosproject.store.serializers.KryoNamespaces;
-import org.onosproject.store.service.AtomicCounter;
 import org.onosproject.store.service.ConsistentMap;
 import org.onosproject.store.service.MapEvent;
 import org.onosproject.store.service.MapEventListener;
 import org.onosproject.store.service.Serializer;
 import org.onosproject.store.service.StorageService;
 import org.onosproject.store.service.DistributedPrimitive.Status;
-import org.onosproject.store.service.Versioned;
 import org.slf4j.Logger;
 
 import java.util.Collection;
@@ -62,11 +56,9 @@
 import java.util.Iterator;
 import java.util.Map;
 import java.util.Objects;
-import java.util.Optional;
 import java.util.Set;
 import java.util.concurrent.ConcurrentHashMap;
 import java.util.concurrent.ScheduledExecutorService;
-import java.util.concurrent.TimeUnit;
 import java.util.function.Consumer;
 import java.util.function.Predicate;
 import java.util.stream.Collectors;
@@ -93,47 +85,16 @@
     @Reference(cardinality = ReferenceCardinality.MANDATORY_UNARY)
     protected StorageService storageService;
 
-    private AtomicCounter hostProbeIndex;
     private ConsistentMap<HostId, DefaultHost> hostsConsistentMap;
     private Map<HostId, DefaultHost> hosts;
     private Map<IpAddress, Set<Host>> hostsByIp;
     private MapEventListener<HostId, DefaultHost> hostLocationTracker =
             new HostLocationTracker();
 
-    private ConsistentMap<MacAddress, PendingHostLocation> pendingHostsConsistentMap;
-    private Map<MacAddress, PendingHostLocation> pendingHosts;
-    private MapEventListener<MacAddress, PendingHostLocation> pendingHostListener =
-            new PendingHostListener();
-
     private ScheduledExecutorService executor;
-    private ScheduledExecutorService cacheCleaner;
-    private ScheduledExecutorService locationRemover;
 
     private Consumer<Status> statusChangeListener;
 
-    // TODO make this configurable
-    private static final int PROBE_TIMEOUT_MS = 3000;
-
-    private Cache<MacAddress, PendingHostLocation> pendingHostsCache = CacheBuilder.newBuilder()
-            .expireAfterWrite(PROBE_TIMEOUT_MS, TimeUnit.MILLISECONDS)
-            .removalListener((RemovalNotification<MacAddress, PendingHostLocation> notification) -> {
-                switch (notification.getCause()) {
-                    case EXPIRED:
-                        PendingHostLocation expired = notification.getValue();
-                        if (expired != null) {
-                            if (timeoutPendingHostLocation(notification.getKey())) {
-                                log.info("Evict {} from pendingHosts due to probe timeout", notification.getValue());
-                            }
-                        }
-                        break;
-                    case EXPLICIT:
-                        break;
-                    default:
-                        log.warn("Remove {} from pendingHostLocations for unexpected reason {}",
-                                notification.getKey(), notification.getCause());
-                }
-            }).build();
-
     @Activate
     public void activate() {
         KryoNamespace.Builder hostSerializer = KryoNamespace.newBuilder()
@@ -146,28 +107,6 @@
         hostsConsistentMap.addListener(hostLocationTracker);
         hosts = hostsConsistentMap.asJavaMap();
 
-        KryoNamespace.Builder pendingHostSerializer = KryoNamespace.newBuilder()
-                .register(KryoNamespaces.API)
-                .register(PendingHostLocation.class)
-                .register(ProbeMode.class);
-        pendingHostsConsistentMap = storageService.<MacAddress, PendingHostLocation>consistentMapBuilder()
-                .withName("onos-hosts-pending")
-                .withRelaxedReadConsistency()
-                .withSerializer(Serializer.using(pendingHostSerializer.build()))
-                .build();
-        pendingHostsConsistentMap.addListener(pendingHostListener);
-        pendingHosts = pendingHostsConsistentMap.asJavaMap();
-
-        hostProbeIndex = storageService.atomicCounterBuilder()
-            .withName("onos-hosts-probe-index")
-            .build()
-            .asAtomicCounter();
-
-        cacheCleaner = newSingleThreadScheduledExecutor(groupedThreads("onos/hosts", "cache-cleaner", log));
-        cacheCleaner.scheduleAtFixedRate(pendingHostsCache::cleanUp, 0, PROBE_TIMEOUT_MS, TimeUnit.MILLISECONDS);
-
-        locationRemover = newSingleThreadScheduledExecutor(groupedThreads("onos/hosts", "loc-remover", log));
-
         executor = newSingleThreadScheduledExecutor(groupedThreads("onos/hosts", "status-listener", log));
         statusChangeListener = status -> {
             if (status == Status.ACTIVE) {
@@ -182,9 +121,6 @@
     @Deactivate
     public void deactivate() {
         hostsConsistentMap.removeListener(hostLocationTracker);
-
-        cacheCleaner.shutdown();
-        locationRemover.shutdown();
         executor.shutdown();
 
         log.info("Stopped");
@@ -425,41 +361,6 @@
         return ImmutableSet.copyOf(filtered);
     }
 
-    @Override
-    public MacAddress addPendingHostLocation(HostId hostId, ConnectPoint connectPoint, ProbeMode probeMode) {
-        // Use ONLab OUI (3 bytes) + atomic counter (3 bytes) as the source MAC of the probe
-        long nextIndex = hostProbeIndex.getAndIncrement();
-        MacAddress probeMac = MacAddress.valueOf(MacAddress.NONE.toLong() + nextIndex);
-        PendingHostLocation phl = new PendingHostLocation(hostId, connectPoint, probeMode);
-
-        pendingHostsCache.put(probeMac, phl);
-        pendingHosts.put(probeMac, phl);
-
-        return probeMac;
-    }
-
-    @Override
-    public void removePendingHostLocation(MacAddress probeMac) {
-        // Add the host location if probe replied in-time in DISCOVER mode
-        Optional.ofNullable(pendingHosts.get(probeMac)).ifPresent(phl -> {
-            if (phl.probeMode() == ProbeMode.DISCOVER) {
-                HostLocation newLocation = new HostLocation(phl.connectPoint(), System.currentTimeMillis());
-                appendLocation(phl.hostId(), newLocation);
-            }
-        });
-
-        pendingHostsCache.invalidate(probeMac);
-        pendingHosts.remove(probeMac);
-    }
-
-    private boolean timeoutPendingHostLocation(MacAddress probeMac) {
-        PendingHostLocation phl = pendingHosts.computeIfPresent(probeMac, (k, v) -> {
-            v.setExpired(true);
-            return v;
-        });
-        return phl != null;
-    }
-
     private Set<Host> filter(Collection<DefaultHost> collection, Predicate<DefaultHost> predicate) {
         return collection.stream().filter(predicate).collect(Collectors.toSet());
     }
@@ -543,29 +444,4 @@
             }
         }
     }
-
-    private class PendingHostListener implements MapEventListener<MacAddress, PendingHostLocation> {
-        @Override
-        public void event(MapEvent<MacAddress, PendingHostLocation> event) {
-            Versioned<PendingHostLocation> newValue = event.newValue();
-            switch (event.type()) {
-                case INSERT:
-                    break;
-                case UPDATE:
-                    // Remove the host location if probe timeout in VERIFY mode
-                    if (newValue.value().expired() && newValue.value().probeMode() == ProbeMode.VERIFY) {
-                        locationRemover.execute(() -> {
-                            pendingHosts.remove(event.key());
-                            removeLocation(newValue.value().hostId(),
-                                    new HostLocation(newValue.value().connectPoint(), 0L));
-                        });
-                    }
-                    break;
-                case REMOVE:
-                    break;
-                default:
-                    log.warn("Unknown map event type: {}", event.type());
-            }
-        }
-    }
 }
diff --git a/core/store/dist/src/main/java/org/onosproject/store/host/impl/PendingHostLocation.java b/core/store/dist/src/main/java/org/onosproject/store/host/impl/PendingHostLocation.java
deleted file mode 100644
index dc10507..0000000
--- a/core/store/dist/src/main/java/org/onosproject/store/host/impl/PendingHostLocation.java
+++ /dev/null
@@ -1,123 +0,0 @@
-/*
- * Copyright 2017-present Open Networking Foundation
- *
- * 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.
- */
-
-package org.onosproject.store.host.impl;
-
-import org.onosproject.net.ConnectPoint;
-import org.onosproject.net.HostId;
-import org.onosproject.net.host.HostLocationProbingService.ProbeMode;
-
-import java.util.Objects;
-
-import static com.google.common.base.MoreObjects.toStringHelper;
-
-/**
- * Internal data structure to record the info of a host with location that is under verification.
- */
-class PendingHostLocation {
-    private HostId hostId;
-    private ConnectPoint connectPoint;
-    private boolean expired;
-    private ProbeMode probeMode;
-
-    /**
-     * Constructs PendingHostLocation.
-     *
-     * @param hostId Host ID
-     * @param connectPoint location to be verified
-     * @param probeMode probe mode
-     */
-    PendingHostLocation(HostId hostId, ConnectPoint connectPoint, ProbeMode probeMode) {
-        this.hostId = hostId;
-        this.connectPoint = connectPoint;
-        this.expired = false;
-        this.probeMode = probeMode;
-    }
-
-    /**
-     * Gets HostId of this entry.
-     *
-     * @return host id
-     */
-    HostId hostId() {
-        return hostId;
-    }
-
-    /**
-     * Gets connect point of this entry.
-     *
-     * @return connect point
-     */
-    ConnectPoint connectPoint() {
-        return connectPoint;
-    }
-
-    /**
-     * Determine whether this probe is expired or not.
-     *
-     * @return true if this entry is expired and waiting to be removed from the cache
-     */
-    boolean expired() {
-        return expired;
-    }
-
-    /**
-     * Sets whether this probe is expired or not.
-     *
-     * @param expired true if this entry is expired and waiting to be removed from the cache
-     */
-    void setExpired(boolean expired) {
-        this.expired = expired;
-    }
-
-    /**
-     * Gets probe mode of this entry.
-     *
-     * @return probe mode
-     */
-    ProbeMode probeMode() {
-        return probeMode;
-    }
-
-    @Override
-    public boolean equals(Object o) {
-        if (this == o) {
-            return true;
-        }
-        if (!(o instanceof PendingHostLocation)) {
-            return false;
-        }
-        PendingHostLocation that = (PendingHostLocation) o;
-        return (Objects.equals(this.hostId, that.hostId) &&
-                Objects.equals(this.connectPoint, that.connectPoint) &&
-                Objects.equals(this.expired, that.expired) &&
-                Objects.equals(this.probeMode, that.probeMode));
-    }
-    @Override
-    public int hashCode() {
-        return Objects.hash(hostId, connectPoint, expired, probeMode);
-    }
-
-    @Override
-    public String toString() {
-        return toStringHelper(getClass())
-                .add("hostId", hostId)
-                .add("location", connectPoint)
-                .add("expired", expired)
-                .add("probeMode", probeMode)
-                .toString();
-    }
-}
diff --git a/modules.defs b/modules.defs
index 3c96b1a..dabd5f9 100644
--- a/modules.defs
+++ b/modules.defs
@@ -126,6 +126,7 @@
     '//providers/bgp:onos-providers-bgp-oar',
     '//providers/bgpcep:onos-providers-bgpcep-oar',
     '//providers/host:onos-providers-host-oar',
+    '//providers/hostprobing:onos-providers-hostprobing-oar',
     '//providers/lldp:onos-providers-lldp-oar',
     '//providers/netcfghost:onos-providers-netcfghost-oar',
     '//providers/netcfglinks:onos-providers-netcfglinks-oar',
diff --git a/providers/host/src/main/java/org/onosproject/provider/host/impl/HostLocationProvider.java b/providers/host/src/main/java/org/onosproject/provider/host/impl/HostLocationProvider.java
index dc58dcc..40e67b5 100644
--- a/providers/host/src/main/java/org/onosproject/provider/host/impl/HostLocationProvider.java
+++ b/providers/host/src/main/java/org/onosproject/provider/host/impl/HostLocationProvider.java
@@ -54,7 +54,6 @@
 import org.onosproject.cfg.ComponentConfigService;
 import org.onosproject.core.ApplicationId;
 import org.onosproject.core.CoreService;
-import org.onosproject.net.host.HostLocationProbingService;
 import org.onosproject.net.intf.InterfaceService;
 import org.onosproject.net.ConnectPoint;
 import org.onosproject.net.Device;
@@ -93,12 +92,9 @@
 import java.util.Objects;
 import java.util.Optional;
 import java.util.concurrent.ExecutorService;
-import java.util.concurrent.ScheduledExecutorService;
-import java.util.concurrent.TimeUnit;
 import java.util.stream.Stream;
 import java.util.Set;
 
-import static java.util.concurrent.Executors.newScheduledThreadPool;
 import static java.util.concurrent.Executors.newSingleThreadScheduledExecutor;
 import static org.onlab.util.Tools.groupedThreads;
 import static org.slf4j.LoggerFactory.getLogger;
@@ -109,7 +105,7 @@
  */
 @Component(immediate = true)
 @Service
-public class HostLocationProvider extends AbstractProvider implements HostProvider, HostLocationProbingService {
+public class HostLocationProvider extends AbstractProvider implements HostProvider {
     private final Logger log = getLogger(getClass());
 
     @Reference(cardinality = ReferenceCardinality.MANDATORY_UNARY)
@@ -136,8 +132,6 @@
     @Reference(cardinality = ReferenceCardinality.MANDATORY_UNARY)
     protected InterfaceService interfaceService;
 
-    private HostProviderService providerService;
-
     private final InternalHostProvider processor = new InternalHostProvider();
     private final DeviceListener deviceListener = new InternalDeviceListener();
 
@@ -173,11 +167,11 @@
             label = "Allow hosts to be multihomed")
     private boolean multihomingEnabled = false;
 
-    private int probeInitDelayMs = 1000;
+    private HostProviderService providerService;
 
-    ExecutorService eventHandler;
+    ExecutorService deviceEventHandler;
+    private ExecutorService probeEventHandler;
     private ExecutorService packetHandler;
-    private ScheduledExecutorService hostProber;
 
     /**
      * Creates an OpenFlow host provider.
@@ -190,10 +184,12 @@
     public void activate(ComponentContext context) {
         cfgService.registerProperties(getClass());
         appId = coreService.registerApplication("org.onosproject.provider.host");
-        eventHandler = newSingleThreadScheduledExecutor(groupedThreads("onos/host-loc-provider", "event-handler", log));
+        deviceEventHandler = newSingleThreadScheduledExecutor(groupedThreads("onos/host-loc-provider",
+                "device-event-handler", log));
+        probeEventHandler = newSingleThreadScheduledExecutor(groupedThreads("onos/host-loc-provider",
+                "probe-event-handler", log));
         packetHandler = newSingleThreadScheduledExecutor(groupedThreads("onos/host-loc-provider",
                 "packet-handler", log));
-        hostProber = newScheduledThreadPool(32, groupedThreads("onos/host-loc-probe", "%d", log));
         providerService = providerRegistry.register(this);
         packetService.addProcessor(processor, PacketProcessor.advisor(1));
         deviceService.addListener(deviceListener);
@@ -212,9 +208,9 @@
         providerRegistry.unregister(this);
         packetService.removeProcessor(processor);
         deviceService.removeListener(deviceListener);
-        eventHandler.shutdown();
+        deviceEventHandler.shutdown();
+        probeEventHandler.shutdown();
         packetHandler.shutdown();
-        hostProber.shutdown();
         providerService = null;
         log.info("Stopped");
     }
@@ -354,47 +350,6 @@
     }
 
     @Override
-    public void probeHostLocation(Host host, ConnectPoint connectPoint, ProbeMode probeMode) {
-        host.ipAddresses().stream().findFirst().ifPresent(ip -> {
-            MacAddress probeMac = providerService.addPendingHostLocation(host.id(), connectPoint, probeMode);
-            log.debug("Constructing {} probe for host {} with {}", probeMode, host.id(), ip);
-            Ethernet probe;
-            if (ip.isIp4()) {
-                probe = ARP.buildArpRequest(probeMac.toBytes(), Ip4Address.ZERO.toOctets(),
-                        host.id().mac().toBytes(), ip.toOctets(),
-                        host.id().mac().toBytes(), host.id().vlanId().toShort());
-            } else {
-                probe = NeighborSolicitation.buildNdpSolicit(
-                        ip.getIp6Address(),
-                        Ip6Address.valueOf(IPv6.getLinkLocalAddress(probeMac.toBytes())),
-                        ip.getIp6Address(),
-                        probeMac,
-                        host.id().mac(),
-                        host.id().vlanId());
-            }
-
-            // NOTE: delay the probe a little bit to wait for the store synchronization is done
-            hostProber.schedule(() ->
-                    sendLocationProbe(probe, connectPoint), probeInitDelayMs, TimeUnit.MILLISECONDS);
-        });
-    }
-
-    /**
-     * Send the probe packet on given port.
-     *
-     * @param probe the probe packet
-     * @param connectPoint the port we want to probe
-     */
-    private void sendLocationProbe(Ethernet probe, ConnectPoint connectPoint) {
-        log.debug("Sending probe for host {} on location {} with probeMac {}",
-                probe.getDestinationMAC(), connectPoint, probe.getSourceMAC());
-        TrafficTreatment treatment = DefaultTrafficTreatment.builder().setOutput(connectPoint.port()).build();
-        OutboundPacket outboundPacket = new DefaultOutboundPacket(connectPoint.deviceId(),
-                treatment, ByteBuffer.wrap(probe.serialize()));
-        packetService.emit(outboundPacket);
-    }
-
-    @Override
     public void triggerProbe(Host host) {
         //log.info("Triggering probe on device {} ", host);
 
@@ -465,10 +420,8 @@
 
                     if (prevLocations.stream().noneMatch(loc -> loc.deviceId().equals(hloc.deviceId()))) {
                         // New location is on a device that we haven't seen before
-                        // Could be a dual-home host. Append new location and send out the probe
+                        // Could be a dual-home host.
                         newLocations.addAll(prevLocations);
-                        prevLocations.forEach(prevLocation ->
-                                probeHostLocation(existingHost, prevLocation, ProbeMode.VERIFY));
                     } else {
                         // Move within the same switch
                         // Simply replace old location that is on the same device
@@ -559,10 +512,8 @@
             HostId hid = HostId.hostId(eth.getSourceMAC(), vlan);
             MacAddress destMac = eth.getDestinationMAC();
 
-            // Receives a location probe. Invalid entry from the cache
+            // Ignore location probes
             if (multihomingEnabled && destMac.isOnos() && !MacAddress.NONE.equals(destMac)) {
-                log.debug("Receives probe for {}/{} on {}", srcMac, vlan, heardOn);
-                providerService.removePendingHostLocation(destMac);
                 return;
             }
 
@@ -762,7 +713,7 @@
     private class InternalDeviceListener implements DeviceListener {
         @Override
         public void event(DeviceEvent event) {
-            eventHandler.execute(() -> handleEvent(event));
+            deviceEventHandler.execute(() -> handleEvent(event));
         }
 
         private void handleEvent(DeviceEvent event) {
diff --git a/providers/host/src/test/java/org/onosproject/provider/host/impl/HostLocationProviderTest.java b/providers/host/src/test/java/org/onosproject/provider/host/impl/HostLocationProviderTest.java
index e00617d..89a6ef8 100644
--- a/providers/host/src/test/java/org/onosproject/provider/host/impl/HostLocationProviderTest.java
+++ b/providers/host/src/test/java/org/onosproject/provider/host/impl/HostLocationProviderTest.java
@@ -236,7 +236,7 @@
 
         provider.activate(CTX_FOR_NO_REMOVE);
 
-        provider.eventHandler = MoreExecutors.newDirectExecutorService();
+        provider.deviceEventHandler = MoreExecutors.newDirectExecutorService();
     }
 
     @Test
diff --git a/providers/hostprobing/BUCK b/providers/hostprobing/BUCK
new file mode 100644
index 0000000..21bf493
--- /dev/null
+++ b/providers/hostprobing/BUCK
@@ -0,0 +1,22 @@
+COMPILE_DEPS = [
+    '//lib:CORE_DEPS',
+    '//incubator/api:onos-incubator-api',
+]
+
+TEST_DEPS = [
+    '//lib:TEST_ADAPTERS',
+    '//utils/osgi:onlab-osgi-tests',
+]
+
+osgi_jar_with_tests (
+    deps = COMPILE_DEPS,
+    test_deps = TEST_DEPS,
+)
+
+onos_app (
+    app_name = 'org.onosproject.hostprobingprovider',
+    title = 'Host Probing Provider',
+    category = 'Provider',
+    url = 'http://onosproject.org',
+    description = 'Provides host probing mechanism that discovers or verifies the existence of a host at specific location',
+)
diff --git a/providers/hostprobing/pom.xml b/providers/hostprobing/pom.xml
new file mode 100644
index 0000000..3f3c001
--- /dev/null
+++ b/providers/hostprobing/pom.xml
@@ -0,0 +1,72 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<!--
+  ~ Copyright 2014-present Open Networking Foundation
+  ~
+  ~ 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.
+  -->
+<project xmlns="http://maven.apache.org/POM/4.0.0"
+         xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
+         xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd">
+    <modelVersion>4.0.0</modelVersion>
+
+    <parent>
+        <groupId>org.onosproject</groupId>
+        <artifactId>onos-providers</artifactId>
+        <version>1.12.1-SNAPSHOT</version>
+    </parent>
+
+    <artifactId>onos-host-provider</artifactId>
+    <packaging>bundle</packaging>
+
+    <properties>
+        <onos.app.name>org.onosproject.hostprobingprovider</onos.app.name>
+        <onos.app.title>Host Probing Provider</onos.app.title>
+        <onos.app.origin>ONF</onos.app.origin>
+        <onos.app.category>Provider</onos.app.category>
+        <onos.app.url>http://onosproject.org</onos.app.url>
+        <onos.app.readme>Provides host probing mechanism that discovers or verifies the existence of a host at specific location</onos.app.readme>
+    </properties>
+
+    <description>ONOS host probing provider</description>
+    <dependencies>
+        <dependency>
+            <groupId>org.onosproject</groupId>
+            <artifactId>onos-api</artifactId>
+            <classifier>tests</classifier>
+            <scope>test</scope>
+        </dependency>
+        <dependency>
+            <groupId>org.osgi</groupId>
+            <artifactId>org.osgi.core</artifactId>
+        </dependency>
+        <dependency>
+            <groupId>org.osgi</groupId>
+            <artifactId>org.osgi.compendium</artifactId>
+        </dependency>
+        <dependency>
+            <groupId>org.onosproject</groupId>
+            <artifactId>onlab-osgi</artifactId>
+            <classifier>tests</classifier>
+            <scope>test</scope>
+        </dependency>
+        <dependency>
+            <groupId>org.easymock</groupId>
+            <artifactId>easymock</artifactId>
+            <scope>test</scope>
+        </dependency>
+        <dependency>
+            <groupId>org.onosproject</groupId>
+            <artifactId>onos-incubator-api</artifactId>
+        </dependency>
+    </dependencies>
+</project>
diff --git a/providers/hostprobing/src/main/java/org/onosproject/provider/hostprobing/impl/DefaultHostProbingProvider.java b/providers/hostprobing/src/main/java/org/onosproject/provider/hostprobing/impl/DefaultHostProbingProvider.java
new file mode 100644
index 0000000..dfcbf0b
--- /dev/null
+++ b/providers/hostprobing/src/main/java/org/onosproject/provider/hostprobing/impl/DefaultHostProbingProvider.java
@@ -0,0 +1,252 @@
+/*
+ * Copyright 2018-present Open Networking Foundation
+ *
+ * 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.
+ */
+
+package org.onosproject.provider.hostprobing.impl;
+
+import org.apache.felix.scr.annotations.Activate;
+import org.apache.felix.scr.annotations.Component;
+import org.apache.felix.scr.annotations.Deactivate;
+import org.apache.felix.scr.annotations.Reference;
+import org.apache.felix.scr.annotations.ReferenceCardinality;
+import org.apache.felix.scr.annotations.Service;
+import org.onlab.packet.ARP;
+import org.onlab.packet.Ethernet;
+import org.onlab.packet.IPv6;
+import org.onlab.packet.Ip4Address;
+import org.onlab.packet.Ip6Address;
+import org.onlab.packet.IpAddress;
+import org.onlab.packet.MacAddress;
+import org.onlab.packet.VlanId;
+import org.onlab.packet.ndp.NeighborSolicitation;
+import org.onosproject.mastership.MastershipService;
+import org.onosproject.net.ConnectPoint;
+import org.onosproject.net.Host;
+import org.onosproject.net.HostLocation;
+import org.onosproject.net.flow.DefaultTrafficTreatment;
+import org.onosproject.net.flow.TrafficTreatment;
+import org.onosproject.net.host.HostProbe;
+import org.onosproject.net.host.HostProbingEvent;
+import org.onosproject.net.host.HostProbingProvider;
+import org.onosproject.net.host.HostProbingProviderRegistry;
+import org.onosproject.net.host.HostProbingProviderService;
+import org.onosproject.net.host.HostProvider;
+import org.onosproject.net.host.HostProviderRegistry;
+import org.onosproject.net.host.HostProviderService;
+import org.onosproject.net.host.ProbeMode;
+import org.onosproject.net.packet.DefaultOutboundPacket;
+import org.onosproject.net.packet.OutboundPacket;
+import org.onosproject.net.packet.PacketProcessor;
+import org.onosproject.net.packet.PacketService;
+import org.onosproject.net.provider.AbstractProvider;
+import org.onosproject.net.provider.ProviderId;
+import org.osgi.service.component.ComponentContext;
+import org.slf4j.Logger;
+
+import java.nio.ByteBuffer;
+import java.util.Optional;
+import java.util.concurrent.ExecutorService;
+import java.util.concurrent.ScheduledExecutorService;
+import java.util.concurrent.TimeUnit;
+
+import static java.util.concurrent.Executors.newScheduledThreadPool;
+import static java.util.concurrent.Executors.newSingleThreadScheduledExecutor;
+import static org.onlab.util.Tools.groupedThreads;
+import static org.slf4j.LoggerFactory.getLogger;
+
+/**
+ * Provider which sends host location probes to discover or verify a host at specific location.
+ */
+@Component(immediate = true)
+@Service
+public class DefaultHostProbingProvider extends AbstractProvider implements HostProvider, HostProbingProvider {
+    private final Logger log = getLogger(getClass());
+
+    @Reference(cardinality = ReferenceCardinality.MANDATORY_UNARY)
+    private HostProviderRegistry providerRegistry;
+
+    @Reference(cardinality = ReferenceCardinality.MANDATORY_UNARY)
+    private HostProbingProviderRegistry hostProbingProviderRegistry;
+
+    @Reference(cardinality = ReferenceCardinality.MANDATORY_UNARY)
+    private PacketService packetService;
+
+    @Reference(cardinality = ReferenceCardinality.MANDATORY_UNARY)
+    private MastershipService mastershipService;
+
+    private HostProviderService providerService;
+    private HostProbingProviderService hostProbingProviderService;
+    private ExecutorService packetHandler;
+    private ExecutorService probeEventHandler;
+    private ScheduledExecutorService hostProber;
+
+    private final PacketProcessor packetProcessor = context ->
+        packetHandler.execute(() -> {
+            Ethernet eth = context.inPacket().parsed();
+            if (eth == null) {
+                return;
+            }
+            MacAddress srcMac = eth.getSourceMAC();
+            MacAddress destMac = eth.getDestinationMAC();
+            VlanId vlan = VlanId.vlanId(eth.getVlanID());
+            ConnectPoint heardOn = context.inPacket().receivedFrom();
+
+            // Receives a location probe. Invalid entry from the cache
+            if (destMac.isOnos() && !MacAddress.NONE.equals(destMac)) {
+                log.debug("Receives probe for {}/{} on {}", srcMac, vlan, heardOn);
+                hostProbingProviderService.removeProbingHost(destMac);
+            }
+        });
+
+    // TODO Make this configurable
+    private static final int PROBE_INIT_DELAY_MS = 1000;
+    private static final int DEFAULT_RETRY = 5;
+
+    /**
+     * Creates an OpenFlow host provider.
+     */
+    public DefaultHostProbingProvider() {
+        super(new ProviderId("hostprobing", "org.onosproject.provider.hostprobing"));
+    }
+
+    @Activate
+    public void activate(ComponentContext context) {
+        providerService = providerRegistry.register(this);
+        hostProbingProviderService = hostProbingProviderRegistry.register(this);
+
+        packetHandler = newSingleThreadScheduledExecutor(groupedThreads("onos/host-loc-provider",
+                "packet-handler", log));
+        probeEventHandler = newSingleThreadScheduledExecutor(groupedThreads("onos/host-loc-provider",
+                "probe-handler", log));
+        hostProber = newScheduledThreadPool(32, groupedThreads("onos/host-loc-probe", "%d", log));
+
+        packetService.addProcessor(packetProcessor, PacketProcessor.advisor(1));
+    }
+
+    @Deactivate
+    public void deactivate() {
+        providerRegistry.unregister(this);
+        hostProbingProviderRegistry.unregister(this);
+        providerService = null;
+
+        packetService.removeProcessor(packetProcessor);
+
+        packetHandler.shutdown();
+        probeEventHandler.shutdown();
+        hostProber.shutdown();
+    }
+
+    @Override
+    public void triggerProbe(Host host) {
+        // Not doing anything at this moment...
+    }
+
+    @Override
+    public void processEvent(HostProbingEvent event) {
+        probeEventHandler.execute(() -> {
+            log.debug("Receiving HostProbingEvent {}", event);
+            HostProbe hostProbe = event.subject();
+
+            switch (event.type()) {
+                case PROBE_REQUESTED:
+                    // Do nothing
+                    break;
+                case PROBE_TIMEOUT:
+                    // Retry probe until PROBE_FAIL
+                    // TODO Only retry DISCOVER probes
+                    probeHostInternal(hostProbe, hostProbe.connectPoint(),
+                            hostProbe.mode(), hostProbe.probeMac(), hostProbe.retry());
+                    break;
+                case PROBE_FAIL:
+                    // Remove this location if this is a verify probe.
+                    if (hostProbe.mode() == ProbeMode.VERIFY) {
+                        providerService.removeLocationFromHost(hostProbe.id(),
+                                (HostLocation) hostProbe.connectPoint());
+                    }
+                    break;
+                case PROBE_COMPLETED:
+                    // Add this location if this is a discover probe.
+                    if (hostProbe.mode() == ProbeMode.DISCOVER) {
+                        HostLocation newLocation = new HostLocation(hostProbe.connectPoint(),
+                                System.currentTimeMillis());
+                        providerService.addLocationToHost(hostProbe.id(), newLocation);
+                    }
+                    break;
+                default:
+                    log.warn("Unknown HostProbingEvent type: {}", event.type());
+            }
+        });
+    }
+
+    @Override
+    public void probeHost(Host host, ConnectPoint connectPoint, ProbeMode probeMode) {
+        probeHostInternal(host, connectPoint, probeMode, null, DEFAULT_RETRY);
+    }
+
+    // probeMac can be null if this is the very first probe and the mac is to-be-generated.
+    private void probeHostInternal(Host host, ConnectPoint connectPoint, ProbeMode probeMode,
+                                   MacAddress probeMac, int retry) {
+        if (!mastershipService.isLocalMaster(connectPoint.deviceId())) {
+            log.debug("Current node is not master of {}, abort probing {}", connectPoint.deviceId(), host);
+            return;
+        }
+
+        log.debug("probeHostInternal host={}, cp={}, mode={}, probeMac={}, retry={}", host, connectPoint,
+                probeMode, probeMac, retry);
+        Optional<IpAddress> ipOptional = host.ipAddresses().stream().findFirst();
+
+        if (ipOptional.isPresent()) {
+            probeMac = hostProbingProviderService.addProbingHost(host, connectPoint, probeMode, probeMac, retry);
+
+            IpAddress ip = ipOptional.get();
+            log.debug("Constructing {} probe for host {} with {}", probeMode, host.id(), ip);
+            Ethernet probe;
+            if (ip.isIp4()) {
+                probe = ARP.buildArpRequest(probeMac.toBytes(), Ip4Address.ZERO.toOctets(),
+                        host.id().mac().toBytes(), ip.toOctets(),
+                        host.id().mac().toBytes(), host.id().vlanId().toShort());
+            } else {
+                probe = NeighborSolicitation.buildNdpSolicit(
+                        ip.getIp6Address(),
+                        Ip6Address.valueOf(IPv6.getLinkLocalAddress(probeMac.toBytes())),
+                        ip.getIp6Address(),
+                        probeMac,
+                        host.id().mac(),
+                        host.id().vlanId());
+            }
+
+            // NOTE: delay the probe a little bit to wait for the store synchronization is done
+            hostProber.schedule(() ->
+                    sendLocationProbe(probe, connectPoint), PROBE_INIT_DELAY_MS, TimeUnit.MILLISECONDS);
+        } else {
+            log.debug("Host {} has no IP address yet. Skip probing.", host);
+        }
+    }
+
+    /**
+     * Send the probe packet on given port.
+     *
+     * @param probe the probe packet
+     * @param connectPoint the port we want to probe
+     */
+    private void sendLocationProbe(Ethernet probe, ConnectPoint connectPoint) {
+        log.debug("Sending probe for host {} on location {} with probeMac {}",
+                probe.getDestinationMAC(), connectPoint, probe.getSourceMAC());
+        TrafficTreatment treatment = DefaultTrafficTreatment.builder().setOutput(connectPoint.port()).build();
+        OutboundPacket outboundPacket = new DefaultOutboundPacket(connectPoint.deviceId(),
+                treatment, ByteBuffer.wrap(probe.serialize()));
+        packetService.emit(outboundPacket);
+    }
+}
\ No newline at end of file
diff --git a/providers/hostprobing/src/main/java/org/onosproject/provider/hostprobing/impl/package-info.java b/providers/hostprobing/src/main/java/org/onosproject/provider/hostprobing/impl/package-info.java
new file mode 100644
index 0000000..60ef748
--- /dev/null
+++ b/providers/hostprobing/src/main/java/org/onosproject/provider/hostprobing/impl/package-info.java
@@ -0,0 +1,20 @@
+/*
+ * Copyright 2018-present Open Networking Foundation
+ *
+ * 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.
+ */
+
+/**
+ * Provider that uses packet service as a means of host discovery and tracking.
+ */
+package org.onosproject.provider.hostprobing.impl;
diff --git a/providers/pom.xml b/providers/pom.xml
index 5e030df..7cfca17 100644
--- a/providers/pom.xml
+++ b/providers/pom.xml
@@ -33,6 +33,7 @@
     <modules>
         <module>openflow</module>
         <module>host</module>
+        <module>hostprobing</module>
         <module>netcfghost</module>
         <module>netconf</module>
         <module>null</module>