diff --git a/Cronet/OWNERS b/Cronet/OWNERS
index 62c5737..c24680e 100644
--- a/Cronet/OWNERS
+++ b/Cronet/OWNERS
@@ -1,2 +1,2 @@
 set noparent
-file:platform/packages/modules/Connectivity:master:/OWNERS_core_networking
+file:platform/packages/modules/Connectivity:main:/OWNERS_core_networking
diff --git a/Cronet/tests/OWNERS b/Cronet/tests/OWNERS
index acb6ee6..a35a789 100644
--- a/Cronet/tests/OWNERS
+++ b/Cronet/tests/OWNERS
@@ -1,7 +1,7 @@
 # Bug component: 31808
 
 set noparent
-file:platform/packages/modules/Connectivity:master:/OWNERS_core_networking_xts
+file:platform/packages/modules/Connectivity:main:/OWNERS_core_networking_xts
 
 # TODO: Temp ownership to develop cronet CTS
 colibie@google.com #{LAST_RESORT_SUGGESTION}
diff --git a/Cronet/tests/cts/src/android/net/http/cts/BidirectionalStreamTest.kt b/Cronet/tests/cts/src/android/net/http/cts/BidirectionalStreamTest.kt
index 0885f4f..464862d 100644
--- a/Cronet/tests/cts/src/android/net/http/cts/BidirectionalStreamTest.kt
+++ b/Cronet/tests/cts/src/android/net/http/cts/BidirectionalStreamTest.kt
@@ -27,12 +27,14 @@
 import androidx.test.core.app.ApplicationProvider
 import com.android.testutils.DevSdkIgnoreRule
 import com.android.testutils.DevSdkIgnoreRunner
+import com.android.testutils.SkipPresubmit
 import com.google.common.truth.Truth.assertThat
 import kotlin.test.Test
 import kotlin.test.assertEquals
 import org.hamcrest.MatcherAssert
 import org.hamcrest.Matchers
 import org.junit.After
+import org.junit.AssumptionViolatedException
 import org.junit.Before
 import org.junit.runner.RunWith
 
@@ -58,11 +60,6 @@
     @After
     @Throws(Exception::class)
     fun tearDown() {
-        // cancel active requests to enable engine shutdown.
-        stream?.let {
-            it.cancel()
-            callback.blockForDone()
-        }
         httpEngine.shutdown()
     }
 
@@ -72,10 +69,21 @@
 
     @Test
     @Throws(Exception::class)
+    @SkipPresubmit(reason = "b/293141085 Confirm non-flaky and move to presubmit after SLO")
     fun testBidirectionalStream_GetStream_CompletesSuccessfully() {
         stream = createBidirectionalStreamBuilder(URL).setHttpMethod("GET").build()
         stream!!.start()
-        callback.assumeCallback(ResponseStep.ON_SUCCEEDED)
+        // We call to a real server and hence the server may not be reachable, cancel this stream
+        // and rethrow the exception before tearDown,
+        // otherwise shutdown would fail with active request error.
+        try {
+            callback.assumeCallback(ResponseStep.ON_SUCCEEDED)
+        } catch (e: AssumptionViolatedException) {
+            stream!!.cancel()
+            callback.blockForDone()
+            throw e
+        }
+
         val info = callback.mResponseInfo
         assumeOKStatusCode(info)
         MatcherAssert.assertThat(
@@ -190,5 +198,4 @@
         stream = builder.build()
         assertThat(stream!!.isDelayRequestHeadersUntilFirstFlushEnabled()).isTrue()
     }
-
 }
diff --git a/Cronet/tests/mts/Android.bp b/Cronet/tests/mts/Android.bp
index 4e4251c..63905c8 100644
--- a/Cronet/tests/mts/Android.bp
+++ b/Cronet/tests/mts/Android.bp
@@ -38,7 +38,11 @@
 // tests need to inherit the NetHttpTests manifest.
 android_library {
     name: "NetHttpTestsLibPreJarJar",
-    static_libs: ["cronet_java_tests"],
+    static_libs: [
+        "cronet_aml_api_java",
+        "cronet_aml_java__testing",
+        "cronet_java_tests",
+    ],
     sdk_version: "module_current",
     min_sdk_version: "30",
 }
@@ -51,7 +55,8 @@
      static_libs: ["NetHttpTestsLibPreJarJar"],
      jarjar_rules: ":net-http-test-jarjar-rules",
      jni_libs: [
-        "cronet_aml_components_cronet_android_cronet_tests__testing"
+        "cronet_aml_components_cronet_android_cronet__testing",
+        "cronet_aml_components_cronet_android_cronet_tests__testing",
      ],
      test_suites: [
          "general-tests",
diff --git a/Cronet/tests/mts/jarjar_excludes.txt b/Cronet/tests/mts/jarjar_excludes.txt
index a3e86de..e8fd39b 100644
--- a/Cronet/tests/mts/jarjar_excludes.txt
+++ b/Cronet/tests/mts/jarjar_excludes.txt
@@ -1,5 +1,8 @@
-# It's prohibited to jarjar androidx packages
+# jarjar-gen can't handle some kotlin object expression, exclude packages that include them
 androidx\..+
+kotlin\.test\..+
+kotlin\.reflect\..+
+org\.mockito\..+
 # Do not jarjar the api classes
 android\.net\..+
 # cronet_tests.so is not jarjared and uses base classes. We can remove this when there's a
diff --git a/OWNERS b/OWNERS
index 07a775e..649efda 100644
--- a/OWNERS
+++ b/OWNERS
@@ -1,4 +1,4 @@
 set noparent
-file:platform/packages/modules/Connectivity:master:/OWNERS_core_networking
+file:platform/packages/modules/Connectivity:main:/OWNERS_core_networking
 
-per-file **IpSec* = file:platform/frameworks/base:master:/services/core/java/com/android/server/vcn/OWNERS
\ No newline at end of file
+per-file **IpSec* = file:platform/frameworks/base:main:/services/core/java/com/android/server/vcn/OWNERS
diff --git a/TEST_MAPPING b/TEST_MAPPING
index 0326bf2..3384f7b 100644
--- a/TEST_MAPPING
+++ b/TEST_MAPPING
@@ -100,6 +100,9 @@
       "name": "NetHttpCoverageTests",
       "options": [
         {
+          "exclude-annotation": "com.android.testutils.SkipPresubmit"
+        },
+        {
           // These sometimes take longer than 1 min which is the presubmit timeout
           "exclude-annotation": "androidx.test.filters.LargeTest"
         }
@@ -180,6 +183,9 @@
         },
         {
           "exclude-annotation": "com.android.testutils.ConnectivityModuleTest"
+        },
+        {
+          "exclude-annotation": "com.android.testutils.DnsResolverModuleTest"
         }
       ]
     },
@@ -195,6 +201,9 @@
         },
         {
           "exclude-annotation": "androidx.test.filters.RequiresDevice"
+        },
+        {
+          "exclude-annotation": "com.android.testutils.DnsResolverModuleTest"
         }
       ]
     },
@@ -220,6 +229,9 @@
       "name": "NetHttpCoverageTests[CaptivePortalLoginGoogle.apk+NetworkStackGoogle.apk+com.google.android.resolv.apex+com.google.android.tethering.apex]",
       "options": [
         {
+          "exclude-annotation": "com.android.testutils.SkipPresubmit"
+        },
+        {
           // These sometimes take longer than 1 min which is the presubmit timeout
           "exclude-annotation": "androidx.test.filters.LargeTest"
         }
diff --git a/bpf_progs/clatd.c b/bpf_progs/clatd.c
index 905b8fa..a104084 100644
--- a/bpf_progs/clatd.c
+++ b/bpf_progs/clatd.c
@@ -138,10 +138,11 @@
     }
 
     switch (proto) {
-        case IPPROTO_TCP:  // For TCP & UDP the checksum neutrality of the chosen IPv6
-        case IPPROTO_UDP:  // address means there is no need to update their checksums.
-        case IPPROTO_GRE:  // We do not need to bother looking at GRE/ESP headers,
-        case IPPROTO_ESP:  // since there is never a checksum to update.
+        case IPPROTO_TCP:      // For TCP, UDP & UDPLITE the checksum neutrality of the chosen
+        case IPPROTO_UDP:      // IPv6 address means there is no need to update their checksums.
+        case IPPROTO_UDPLITE:  //
+        case IPPROTO_GRE:      // We do not need to bother looking at GRE/ESP headers,
+        case IPPROTO_ESP:      // since there is never a checksum to update.
             break;
 
         default:  // do not know how to handle anything else
@@ -328,12 +329,13 @@
     if (ip4->frag_off & ~htons(IP_DF)) return TC_ACT_PIPE;
 
     switch (ip4->protocol) {
-        case IPPROTO_TCP:  // For TCP & UDP the checksum neutrality of the chosen IPv6
-        case IPPROTO_GRE:  // address means there is no need to update their checksums.
-        case IPPROTO_ESP:  // We do not need to bother looking at GRE/ESP headers,
-            break;         // since there is never a checksum to update.
+        case IPPROTO_TCP:      // For TCP, UDP & UDPLITE the checksum neutrality of the chosen
+        case IPPROTO_UDPLITE:  // IPv6 address means there is no need to update their checksums.
+        case IPPROTO_GRE:      // We do not need to bother looking at GRE/ESP headers,
+        case IPPROTO_ESP:      // since there is never a checksum to update.
+            break;
 
-        case IPPROTO_UDP:  // See above comment, but must also have UDP header...
+        case IPPROTO_UDP:      // See above comment, but must also have UDP header...
             if (data + sizeof(*ip4) + sizeof(struct udphdr) > data_end) return TC_ACT_PIPE;
             const struct udphdr* uh = (const struct udphdr*)(ip4 + 1);
             // If IPv4/UDP checksum is 0 then fallback to clatd so it can calculate the
diff --git a/framework/Android.bp b/framework/Android.bp
index 123f02a..cab11ae 100644
--- a/framework/Android.bp
+++ b/framework/Android.bp
@@ -109,8 +109,8 @@
         "framework-connectivity-defaults",
     ],
     static_libs: [
-        "cronet_aml_api_java",
-        "cronet_aml_java",
+        "httpclient_api",
+        "httpclient_impl",
     ],
     libs: [
         // This cannot be in the defaults clause above because if it were, it would be used
@@ -125,12 +125,12 @@
 
 java_defaults {
     name: "CronetJavaDefaults",
-    srcs: [":cronet_aml_api_sources"],
+    srcs: [":httpclient_api_sources"],
     libs: [
         "androidx.annotation_annotation",
     ],
     impl_only_static_libs: [
-        "cronet_aml_java",
+        "httpclient_impl",
     ],
 }
 
diff --git a/framework/src/android/net/LinkAddress.java b/framework/src/android/net/LinkAddress.java
index 90f55b3..8376963 100644
--- a/framework/src/android/net/LinkAddress.java
+++ b/framework/src/android/net/LinkAddress.java
@@ -37,6 +37,8 @@
 import android.os.SystemClock;
 import android.util.Pair;
 
+import com.android.net.module.util.ConnectivityUtils;
+
 import java.net.Inet4Address;
 import java.net.Inet6Address;
 import java.net.InetAddress;
@@ -146,11 +148,7 @@
      * Per RFC 4193 section 8, fc00::/7 identifies these addresses.
      */
     private boolean isIpv6ULA() {
-        if (isIpv6()) {
-            byte[] bytes = address.getAddress();
-            return ((bytes[0] & (byte)0xfe) == (byte)0xfc);
-        }
-        return false;
+        return ConnectivityUtils.isIPv6ULA(address);
     }
 
     /**
diff --git a/framework/src/android/net/NetworkCapabilities.java b/framework/src/android/net/NetworkCapabilities.java
index 92e9599..8e219a6 100644
--- a/framework/src/android/net/NetworkCapabilities.java
+++ b/framework/src/android/net/NetworkCapabilities.java
@@ -690,17 +690,10 @@
      */
     public static final int NET_CAPABILITY_PRIORITIZE_BANDWIDTH = 35;
 
-    private static final int MIN_NET_CAPABILITY = NET_CAPABILITY_MMS;
     private static final int MAX_NET_CAPABILITY = NET_CAPABILITY_PRIORITIZE_BANDWIDTH;
 
-    private static final int ALL_VALID_CAPABILITIES;
-    static {
-        int caps = 0;
-        for (int i = MIN_NET_CAPABILITY; i <= MAX_NET_CAPABILITY; ++i) {
-            caps |= 1 << i;
-        }
-        ALL_VALID_CAPABILITIES = caps;
-    }
+    // Set all bits up to the MAX_NET_CAPABILITY-th bit
+    private static final long ALL_VALID_CAPABILITIES = (2L << MAX_NET_CAPABILITY) - 1;
 
     /**
      * Network capabilities that are expected to be mutable, i.e., can change while a particular
@@ -2519,7 +2512,7 @@
     }
 
     private static boolean isValidCapability(@NetworkCapabilities.NetCapability int capability) {
-        return capability >= MIN_NET_CAPABILITY && capability <= MAX_NET_CAPABILITY;
+        return capability >= 0 && capability <= MAX_NET_CAPABILITY;
     }
 
     private static void checkValidCapability(@NetworkCapabilities.NetCapability int capability) {
diff --git a/remote_auth/OWNERS b/remote_auth/OWNERS
new file mode 100644
index 0000000..25a32b9
--- /dev/null
+++ b/remote_auth/OWNERS
@@ -0,0 +1,14 @@
+# Bug component: 1145231
+# Bug template url: http://b/new?component=1145231&template=1715387
+billyhuang@google.com
+boetger@google.com
+casbor@google.com
+derekjedral@google.com
+dlm@google.com
+igorzas@google.com
+jacobhobbie@google.com
+jasonsun@google.com
+jianbing@google.com
+jinjiechen@google.com
+justinmcclain@google.com
+salilr@google.com
diff --git a/remote_auth/README.md b/remote_auth/README.md
new file mode 100644
index 0000000..384fcf7
--- /dev/null
+++ b/remote_auth/README.md
@@ -0,0 +1,47 @@
+# RemoteAuth Mainline Module
+
+This directory contains code for the RemoteAuth module.
+
+## Directory Structure
+
+`framework`
+ - Contains client side APIs and AIDL files.
+
+`jni`
+ - JNI wrapper for invoking Android APIs from native code.
+
+`native`
+ - Native code implementation for RemoteAuth module services.
+
+`service`
+ - Server side implementation for RemoteAuth module services.
+
+`tests`
+ - Unit/Multi devices tests for RemoteAuth module (both Java and native code).
+
+## IDE setup
+
+### AIDEGen
+
+AIDEGen is deprecated, prefer ASfP [go/asfp](http://go/asfp)
+```sh
+$ source build/envsetup.sh && lunch <TARGET>
+$ cd packages/modules/Connectivity
+$ aidegen .
+# This will launch Intellij project for RemoteAuth module.
+```
+
+### ASfP
+
+See full instructions for ASfP at [go/asfp-getting-started](http://go/asfp-getting-started)
+
+## Build and Install
+
+```sh
+$ source build/envsetup.sh && lunch <TARGET>
+$ m com.google.android.tethering deapexer
+$ $ANDROID_BUILD_TOP/out/host/linux-x86/bin/deapexer decompress --input \
+    ${ANDROID_PRODUCT_OUT}/system/apex/com.google.android.tethering.capex \
+    --output /tmp/tethering.apex
+$ adb install -r /tmp/tethering.apex
+```
diff --git a/service-t/native/libs/libnetworkstats/NetworkTraceHandler.cpp b/service-t/native/libs/libnetworkstats/NetworkTraceHandler.cpp
index c5f9631..ec63e41 100644
--- a/service-t/native/libs/libnetworkstats/NetworkTraceHandler.cpp
+++ b/service-t/native/libs/libnetworkstats/NetworkTraceHandler.cpp
@@ -119,7 +119,14 @@
       // the session and delegates writing. The corresponding handler will write
       // with the setting specified in the trace config.
       NetworkTraceHandler::Trace([&](NetworkTraceHandler::TraceContext ctx) {
-        ctx.GetDataSourceLocked()->Write(packets, ctx);
+        perfetto::LockedHandle<NetworkTraceHandler> handle =
+            ctx.GetDataSourceLocked();
+        // The underlying handle can be invalidated between when Trace starts
+        // and GetDataSourceLocked is called, but not while the LockedHandle
+        // exists and holds the lock. Check validity prior to use.
+        if (handle.valid()) {
+          handle->Write(packets, ctx);
+        }
       });
     });
 
diff --git a/service-t/src/com/android/metrics/NetworkNsdReportedMetrics.java b/service-t/src/com/android/metrics/NetworkNsdReportedMetrics.java
new file mode 100644
index 0000000..bcedbef
--- /dev/null
+++ b/service-t/src/com/android/metrics/NetworkNsdReportedMetrics.java
@@ -0,0 +1,125 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * 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 com.android.metrics;
+
+import static com.android.metrics.NetworkNsdReported.Builder;
+
+import android.stats.connectivity.MdnsQueryResult;
+import android.stats.connectivity.NsdEventType;
+
+import com.android.internal.annotations.VisibleForTesting;
+import com.android.server.ConnectivityStatsLog;
+
+/**
+ * Class to record the NetworkNsdReported into statsd. Each client should create this class to
+ * report its data.
+ */
+public class NetworkNsdReportedMetrics {
+    // Whether this client is using legacy backend.
+    private final boolean mIsLegacy;
+    // The client id.
+    private final int mClientId;
+    private final Dependencies mDependencies;
+
+    public NetworkNsdReportedMetrics(boolean isLegacy, int clientId) {
+        this(isLegacy, clientId, new Dependencies());
+    }
+
+    @VisibleForTesting
+    NetworkNsdReportedMetrics(boolean isLegacy, int clientId, Dependencies dependencies) {
+        mIsLegacy = isLegacy;
+        mClientId = clientId;
+        mDependencies = dependencies;
+    }
+
+    /**
+     * Dependencies of NetworkNsdReportedMetrics, for injection in tests.
+     */
+    public static class Dependencies {
+
+        /**
+         * @see ConnectivityStatsLog
+         */
+        public void statsWrite(NetworkNsdReported event) {
+            ConnectivityStatsLog.write(ConnectivityStatsLog.NETWORK_NSD_REPORTED,
+                    event.getIsLegacy(),
+                    event.getClientId(),
+                    event.getTransactionId(),
+                    event.getIsKnownService(),
+                    event.getType().getNumber(),
+                    event.getEventDurationMillisec(),
+                    event.getQueryResult().getNumber(),
+                    event.getFoundServiceCount(),
+                    event.getFoundCallbackCount(),
+                    event.getLostCallbackCount(),
+                    event.getRepliedRequestsCount());
+        }
+    }
+
+    private Builder makeReportedBuilder() {
+        final Builder builder = NetworkNsdReported.newBuilder();
+        builder.setIsLegacy(mIsLegacy);
+        builder.setClientId(mClientId);
+        return builder;
+    }
+
+    /**
+     * Report service registration succeeded metric data.
+     *
+     * @param transactionId The transaction id of service registration.
+     * @param durationMs The duration of service registration success.
+     */
+    public void reportServiceRegistrationSucceeded(int transactionId, long durationMs) {
+        final Builder builder = makeReportedBuilder();
+        builder.setTransactionId(transactionId);
+        builder.setType(NsdEventType.NET_REGISTER);
+        builder.setQueryResult(MdnsQueryResult.MQR_SERVICE_REGISTERED);
+        builder.setEventDurationMillisec(durationMs);
+        mDependencies.statsWrite(builder.build());
+    }
+
+    /**
+     * Report service registration failed metric data.
+     *
+     * @param transactionId The transaction id of service registration.
+     * @param durationMs The duration of service registration failed.
+     */
+    public void reportServiceRegistrationFailed(int transactionId, long durationMs) {
+        final Builder builder = makeReportedBuilder();
+        builder.setTransactionId(transactionId);
+        builder.setType(NsdEventType.NET_REGISTER);
+        builder.setQueryResult(MdnsQueryResult.MQR_SERVICE_REGISTRATION_FAILED);
+        builder.setEventDurationMillisec(durationMs);
+        mDependencies.statsWrite(builder.build());
+    }
+
+    /**
+     * Report service unregistration success metric data.
+     *
+     * @param transactionId The transaction id of service registration.
+     * @param durationMs The duration of service stayed registered.
+     */
+    public void reportServiceUnregistration(int transactionId, long durationMs) {
+        final Builder builder = makeReportedBuilder();
+        builder.setTransactionId(transactionId);
+        builder.setType(NsdEventType.NET_REGISTER);
+        builder.setQueryResult(MdnsQueryResult.MQR_SERVICE_UNREGISTERED);
+        builder.setEventDurationMillisec(durationMs);
+        // TODO: Report repliedRequestsCount
+        mDependencies.statsWrite(builder.build());
+    }
+}
diff --git a/service-t/src/com/android/server/NsdService.java b/service-t/src/com/android/server/NsdService.java
index b06e9cb..745c5bc 100644
--- a/service-t/src/com/android/server/NsdService.java
+++ b/service-t/src/com/android/server/NsdService.java
@@ -26,6 +26,7 @@
 
 import static com.android.modules.utils.build.SdkLevel.isAtLeastU;
 import static com.android.server.connectivity.mdns.MdnsRecord.MAX_LABEL_LENGTH;
+import static com.android.server.connectivity.mdns.util.MdnsUtils.Clock;
 
 import android.annotation.NonNull;
 import android.annotation.Nullable;
@@ -68,6 +69,7 @@
 import com.android.internal.util.IndentingPrintWriter;
 import com.android.internal.util.State;
 import com.android.internal.util.StateMachine;
+import com.android.metrics.NetworkNsdReportedMetrics;
 import com.android.net.module.util.CollectionUtils;
 import com.android.net.module.util.DeviceConfigUtils;
 import com.android.net.module.util.InetAddressUtils;
@@ -160,6 +162,7 @@
     public static final boolean DBG = Log.isLoggable(TAG, Log.DEBUG);
     private static final long CLEANUP_DELAY_MS = 10000;
     private static final int IFACE_IDX_ANY = 0;
+    private static final int NO_TRANSACTION = -1;
     private static final SharedLog LOGGER = new SharedLog("serviceDiscovery");
 
     private final Context mContext;
@@ -176,6 +179,8 @@
     private final MdnsSocketProvider mMdnsSocketProvider;
     @NonNull
     private final MdnsAdvertiser mAdvertiser;
+    @NonNull
+    private final Clock mClock;
     private final SharedLog mServiceLogs = LOGGER.forSubComponent(TAG);
     // WARNING : Accessing these values in any thread is not safe, it must only be changed in the
     // state machine thread. If change this outside state machine, it will need to introduce
@@ -528,8 +533,11 @@
                         try {
                             cb.asBinder().linkToDeath(arg.connector, 0);
                             final String tag = "Client" + arg.uid + "-" + mClientNumberId++;
+                            final NetworkNsdReportedMetrics metrics =
+                                    mDeps.makeNetworkNsdReportedMetrics(
+                                            !arg.useJavaBackend, (int) mClock.elapsedRealtime());
                             cInfo = new ClientInfo(cb, arg.uid, arg.useJavaBackend,
-                                    mServiceLogs.forSubComponent(tag));
+                                    mServiceLogs.forSubComponent(tag), metrics);
                             mClients.put(arg.connector, cInfo);
                         } catch (RemoteException e) {
                             Log.w(TAG, "Client request id " + clientRequestId
@@ -565,7 +573,7 @@
                     case NsdManager.REGISTER_SERVICE:
                         cInfo = getClientInfoForReply(msg);
                         if (cInfo != null) {
-                            cInfo.onRegisterServiceFailed(
+                            cInfo.onRegisterServiceFailedImmediately(
                                     clientRequestId, NsdManager.FAILURE_INTERNAL_ERROR);
                         }
                         break;
@@ -647,8 +655,8 @@
 
             private void storeLegacyRequestMap(int clientRequestId, int transactionId,
                     ClientInfo clientInfo, int what) {
-                clientInfo.mClientRequests.put(
-                        clientRequestId, new LegacyClientRequest(transactionId, what));
+                clientInfo.mClientRequests.put(clientRequestId, new LegacyClientRequest(
+                        transactionId, what, mClock, mClock.elapsedRealtime()));
                 mTransactionIdToClientInfoMap.put(transactionId, clientInfo);
                 // Remove the cleanup event because here comes a new request.
                 cancelStop();
@@ -656,8 +664,8 @@
 
             private void storeAdvertiserRequestMap(int clientRequestId, int transactionId,
                     ClientInfo clientInfo, @Nullable Network requestedNetwork) {
-                clientInfo.mClientRequests.put(clientRequestId,
-                        new AdvertiserClientRequest(transactionId, requestedNetwork));
+                clientInfo.mClientRequests.put(clientRequestId, new AdvertiserClientRequest(
+                        transactionId, requestedNetwork, mClock, mClock.elapsedRealtime()));
                 mTransactionIdToClientInfoMap.put(transactionId, clientInfo);
                 updateMulticastLock();
             }
@@ -680,8 +688,9 @@
             private void storeDiscoveryManagerRequestMap(int clientRequestId, int transactionId,
                     MdnsListener listener, ClientInfo clientInfo,
                     @Nullable Network requestedNetwork) {
-                clientInfo.mClientRequests.put(clientRequestId,
-                        new DiscoveryManagerRequest(transactionId, listener, requestedNetwork));
+                clientInfo.mClientRequests.put(clientRequestId, new DiscoveryManagerRequest(
+                        transactionId, listener, requestedNetwork, mClock,
+                        mClock.elapsedRealtime()));
                 mTransactionIdToClientInfoMap.put(transactionId, clientInfo);
                 updateMulticastLock();
             }
@@ -834,7 +843,7 @@
                         }
 
                         if (requestLimitReached(clientInfo)) {
-                            clientInfo.onRegisterServiceFailed(
+                            clientInfo.onRegisterServiceFailedImmediately(
                                     clientRequestId, NsdManager.FAILURE_MAX_LIMIT);
                             break;
                         }
@@ -850,8 +859,8 @@
                                 || useAdvertiserForType(registerServiceType)) {
                             if (registerServiceType == null) {
                                 Log.e(TAG, "Invalid service type: " + serviceType);
-                                clientInfo.onRegisterServiceFailed(clientRequestId,
-                                        NsdManager.FAILURE_INTERNAL_ERROR);
+                                clientInfo.onRegisterServiceFailedImmediately(
+                                        clientRequestId, NsdManager.FAILURE_INTERNAL_ERROR);
                                 break;
                             }
                             serviceInfo.setServiceType(registerServiceType);
@@ -878,7 +887,7 @@
                                 // Return success after mDns reports success
                             } else {
                                 unregisterService(transactionId);
-                                clientInfo.onRegisterServiceFailed(
+                                clientInfo.onRegisterServiceFailedImmediately(
                                         clientRequestId, NsdManager.FAILURE_INTERNAL_ERROR);
                             }
 
@@ -910,10 +919,12 @@
                         // instead of looking at the flag value.
                         if (request instanceof AdvertiserClientRequest) {
                             mAdvertiser.removeService(transactionId);
-                            clientInfo.onUnregisterServiceSucceeded(clientRequestId);
+                            clientInfo.onUnregisterServiceSucceeded(clientRequestId, transactionId,
+                                    request.calculateRequestDurationMs());
                         } else {
                             if (unregisterService(transactionId)) {
-                                clientInfo.onUnregisterServiceSucceeded(clientRequestId);
+                                clientInfo.onUnregisterServiceSucceeded(clientRequestId,
+                                        transactionId, request.calculateRequestDurationMs());
                             } else {
                                 clientInfo.onUnregisterServiceFailed(
                                         clientRequestId, NsdManager.FAILURE_INTERNAL_ERROR);
@@ -1177,12 +1188,18 @@
                         final RegistrationInfo info = (RegistrationInfo) obj;
                         final String name = info.serviceName;
                         servInfo = new NsdServiceInfo(name, null /* serviceType */);
-                        clientInfo.onRegisterServiceSucceeded(clientRequestId, servInfo);
+                        final ClientRequest request =
+                                clientInfo.mClientRequests.get(clientRequestId);
+                        clientInfo.onRegisterServiceSucceeded(clientRequestId, servInfo,
+                                transactionId, request.calculateRequestDurationMs());
                         break;
                     }
                     case IMDnsEventListener.SERVICE_REGISTRATION_FAILED:
-                        clientInfo.onRegisterServiceFailed(
-                                clientRequestId, NsdManager.FAILURE_INTERNAL_ERROR);
+                        final ClientRequest request =
+                                clientInfo.mClientRequests.get(clientRequestId);
+                        clientInfo.onRegisterServiceFailed(clientRequestId,
+                                NsdManager.FAILURE_INTERNAL_ERROR, transactionId,
+                                request.calculateRequestDurationMs());
                         break;
                     case IMDnsEventListener.SERVICE_RESOLVED: {
                         final ResolutionInfo info = (ResolutionInfo) obj;
@@ -1562,6 +1579,7 @@
         handler.post(() -> mMdnsSocketClient.setCallback(mMdnsDiscoveryManager));
         mAdvertiser = deps.makeMdnsAdvertiser(handler.getLooper(), mMdnsSocketProvider,
                 new AdvertiserCallback(), LOGGER.forSubComponent("MdnsAdvertiser"));
+        mClock = deps.makeClock();
     }
 
     /**
@@ -1651,6 +1669,21 @@
         public int getCallingUid() {
             return Binder.getCallingUid();
         }
+
+        /**
+         * @see NetworkNsdReportedMetrics
+         */
+        public NetworkNsdReportedMetrics makeNetworkNsdReportedMetrics(
+                boolean isLegacy, int clientId) {
+            return new NetworkNsdReportedMetrics(isLegacy, clientId);
+        }
+
+        /**
+         * @see MdnsUtils.Clock
+         */
+        public Clock makeClock() {
+            return new Clock();
+        }
     }
 
     /**
@@ -1751,7 +1784,9 @@
             // onRegisterServiceSucceeded only has the service name in its info. This aligns with
             // historical behavior.
             final NsdServiceInfo cbInfo = new NsdServiceInfo(registeredInfo.getServiceName(), null);
-            clientInfo.onRegisterServiceSucceeded(clientRequestId, cbInfo);
+            final ClientRequest request = clientInfo.mClientRequests.get(clientRequestId);
+            clientInfo.onRegisterServiceSucceeded(
+                    clientRequestId, cbInfo, transactionId, request.calculateRequestDurationMs());
         }
 
         @Override
@@ -1761,8 +1796,9 @@
 
             final int clientRequestId = getClientRequestIdOrLog(clientInfo, transactionId);
             if (clientRequestId < 0) return;
-
-            clientInfo.onRegisterServiceFailed(clientRequestId, errorCode);
+            final ClientRequest request = clientInfo.mClientRequests.get(clientRequestId);
+            clientInfo.onRegisterServiceFailed(clientRequestId, errorCode, transactionId,
+                    request.calculateRequestDurationMs());
         }
 
         private ClientInfo getClientInfoOrLog(int transactionId) {
@@ -2022,17 +2058,27 @@
 
     private abstract static class ClientRequest {
         private final int mTransactionId;
+        private final Clock mClock;
+        private final long mStartTimeMs;
 
-        private ClientRequest(int transactionId) {
+        private ClientRequest(int transactionId, @NonNull Clock clock, long startTimeMs) {
             mTransactionId = transactionId;
+            mClock = clock;
+            mStartTimeMs = startTimeMs;
+        }
+
+        public long calculateRequestDurationMs() {
+            final long stopTimeMs = mClock.elapsedRealtime();
+            return stopTimeMs - mStartTimeMs;
         }
     }
 
     private static class LegacyClientRequest extends ClientRequest {
         private final int mRequestCode;
 
-        private LegacyClientRequest(int transactionId, int requestCode) {
-            super(transactionId);
+        private LegacyClientRequest(int transactionId, int requestCode, @NonNull Clock clock,
+                long startTimeMs) {
+            super(transactionId, clock, startTimeMs);
             mRequestCode = requestCode;
         }
     }
@@ -2041,8 +2087,9 @@
         @Nullable
         private final Network mRequestedNetwork;
 
-        private JavaBackendClientRequest(int transactionId, @Nullable Network requestedNetwork) {
-            super(transactionId);
+        private JavaBackendClientRequest(int transactionId, @Nullable Network requestedNetwork,
+                @NonNull Clock clock, long startTimeMs) {
+            super(transactionId, clock, startTimeMs);
             mRequestedNetwork = requestedNetwork;
         }
 
@@ -2053,8 +2100,9 @@
     }
 
     private static class AdvertiserClientRequest extends JavaBackendClientRequest {
-        private AdvertiserClientRequest(int transactionId, @Nullable Network requestedNetwork) {
-            super(transactionId, requestedNetwork);
+        private AdvertiserClientRequest(int transactionId, @Nullable Network requestedNetwork,
+                @NonNull Clock clock, long startTimeMs) {
+            super(transactionId, requestedNetwork, clock, startTimeMs);
         }
     }
 
@@ -2063,8 +2111,8 @@
         private final MdnsListener mListener;
 
         private DiscoveryManagerRequest(int transactionId, @NonNull MdnsListener listener,
-                @Nullable Network requestedNetwork) {
-            super(transactionId, requestedNetwork);
+                @Nullable Network requestedNetwork, @NonNull Clock clock, long startTimeMs) {
+            super(transactionId, requestedNetwork, clock, startTimeMs);
             mListener = listener;
         }
     }
@@ -2087,14 +2135,17 @@
         private final boolean mUseJavaBackend;
         // Store client logs
         private final SharedLog mClientLogs;
+        // Report the nsd metrics data
+        private final NetworkNsdReportedMetrics mMetrics;
 
         private ClientInfo(INsdManagerCallback cb, int uid, boolean useJavaBackend,
-                SharedLog sharedLog) {
+                SharedLog sharedLog, NetworkNsdReportedMetrics metrics) {
             mCb = cb;
             mUid = uid;
             mUseJavaBackend = useJavaBackend;
             mClientLogs = sharedLog;
             mClientLogs.log("New client. useJavaBackend=" + useJavaBackend);
+            mMetrics = metrics;
         }
 
         @Override
@@ -2154,6 +2205,8 @@
 
                 if (request instanceof AdvertiserClientRequest) {
                     mAdvertiser.removeService(transactionId);
+                    mMetrics.reportServiceUnregistration(
+                            transactionId, request.calculateRequestDurationMs());
                     continue;
                 }
 
@@ -2170,6 +2223,8 @@
                         break;
                     case NsdManager.REGISTER_SERVICE:
                         unregisterService(transactionId);
+                        mMetrics.reportServiceUnregistration(
+                                transactionId, request.calculateRequestDurationMs());
                         break;
                     default:
                         break;
@@ -2261,7 +2316,13 @@
             }
         }
 
-        void onRegisterServiceFailed(int listenerKey, int error) {
+        void onRegisterServiceFailedImmediately(int listenerKey, int error) {
+            onRegisterServiceFailed(listenerKey, error, NO_TRANSACTION, 0 /* durationMs */);
+        }
+
+        void onRegisterServiceFailed(int listenerKey, int error, int transactionId,
+                long durationMs) {
+            mMetrics.reportServiceRegistrationFailed(transactionId, durationMs);
             try {
                 mCb.onRegisterServiceFailed(listenerKey, error);
             } catch (RemoteException e) {
@@ -2269,7 +2330,9 @@
             }
         }
 
-        void onRegisterServiceSucceeded(int listenerKey, NsdServiceInfo info) {
+        void onRegisterServiceSucceeded(int listenerKey, NsdServiceInfo info, int transactionId,
+                long durationMs) {
+            mMetrics.reportServiceRegistrationSucceeded(transactionId, durationMs);
             try {
                 mCb.onRegisterServiceSucceeded(listenerKey, info);
             } catch (RemoteException e) {
@@ -2285,7 +2348,8 @@
             }
         }
 
-        void onUnregisterServiceSucceeded(int listenerKey) {
+        void onUnregisterServiceSucceeded(int listenerKey, int transactionId, long durationMs) {
+            mMetrics.reportServiceUnregistration(transactionId, durationMs);
             try {
                 mCb.onUnregisterServiceSucceeded(listenerKey);
             } catch (RemoteException e) {
diff --git a/service-t/src/com/android/server/connectivity/mdns/EnqueueMdnsQueryCallable.java b/service-t/src/com/android/server/connectivity/mdns/EnqueueMdnsQueryCallable.java
index bd4ec20..b7417ed 100644
--- a/service-t/src/com/android/server/connectivity/mdns/EnqueueMdnsQueryCallable.java
+++ b/service-t/src/com/android/server/connectivity/mdns/EnqueueMdnsQueryCallable.java
@@ -16,8 +16,9 @@
 
 package com.android.server.connectivity.mdns;
 
+import static com.android.server.connectivity.mdns.MdnsServiceTypeClient.INVALID_TRANSACTION_ID;
+
 import android.annotation.NonNull;
-import android.annotation.Nullable;
 import android.text.TextUtils;
 import android.util.Log;
 import android.util.Pair;
@@ -75,7 +76,7 @@
     @NonNull
     private final List<MdnsResponse> servicesToResolve;
     @NonNull
-    private final MdnsResponseDecoder.Clock clock;
+    private final MdnsUtils.Clock clock;
     private final boolean onlyUseIpv6OnIpv6OnlyNetworks;
 
     EnqueueMdnsQueryCallable(
@@ -89,7 +90,7 @@
             boolean onlyUseIpv6OnIpv6OnlyNetworks,
             boolean sendDiscoveryQueries,
             @NonNull Collection<MdnsResponse> servicesToResolve,
-            @NonNull MdnsResponseDecoder.Clock clock) {
+            @NonNull MdnsUtils.Clock clock) {
         weakRequestSender = new WeakReference<>(requestSender);
         this.packetWriter = packetWriter;
         serviceTypeLabels = TextUtils.split(serviceType, "\\.");
@@ -103,15 +104,19 @@
         this.clock = clock;
     }
 
+    /**
+     * Call to execute the mdns query.
+     *
+     * @return The pair of transaction id and the subtypes for the query.
+     */
     // Incompatible return type for override of Callable#call().
     @SuppressWarnings("nullness:override.return.invalid")
     @Override
-    @Nullable
     public Pair<Integer, List<String>> call() {
         try {
             MdnsSocketClientBase requestSender = weakRequestSender.get();
             if (requestSender == null) {
-                return null;
+                return Pair.create(INVALID_TRANSACTION_ID, new ArrayList<>());
             }
 
             int numQuestions = 0;
@@ -158,7 +163,7 @@
 
             if (numQuestions == 0) {
                 // No query to send
-                return null;
+                return Pair.create(INVALID_TRANSACTION_ID, new ArrayList<>());
             }
 
             // Header.
@@ -197,7 +202,7 @@
         } catch (IOException e) {
             LOGGER.e(String.format("Failed to create mDNS packet for subtype: %s.",
                     TextUtils.join(",", subtypes)), e);
-            return null;
+            return Pair.create(INVALID_TRANSACTION_ID, new ArrayList<>());
         }
     }
 
diff --git a/service-t/src/com/android/server/connectivity/mdns/ExecutorProvider.java b/service-t/src/com/android/server/connectivity/mdns/ExecutorProvider.java
index 0eebc61..161669b 100644
--- a/service-t/src/com/android/server/connectivity/mdns/ExecutorProvider.java
+++ b/service-t/src/com/android/server/connectivity/mdns/ExecutorProvider.java
@@ -16,6 +16,7 @@
 
 package com.android.server.connectivity.mdns;
 
+import android.annotation.NonNull;
 import android.util.ArraySet;
 
 import java.util.Set;
@@ -47,5 +48,17 @@
             }
             executor.shutdownNow();
         }
+        serviceTypeClientSchedulerExecutors.clear();
+    }
+
+    /**
+     * Shutdown one executor service and remove the executor service from the set.
+     * @param executorService the executorService to be shutdown
+     */
+    public void shutdownExecutorService(@NonNull ScheduledExecutorService executorService) {
+        if (!executorService.isShutdown()) {
+            executorService.shutdownNow();
+        }
+        serviceTypeClientSchedulerExecutors.remove(executorService);
     }
 }
\ No newline at end of file
diff --git a/service-t/src/com/android/server/connectivity/mdns/MdnsConfigs.java b/service-t/src/com/android/server/connectivity/mdns/MdnsConfigs.java
index f5e7790..d4aeacf 100644
--- a/service-t/src/com/android/server/connectivity/mdns/MdnsConfigs.java
+++ b/service-t/src/com/android/server/connectivity/mdns/MdnsConfigs.java
@@ -50,14 +50,6 @@
         return false;
     }
 
-    public static boolean useSessionIdToScheduleMdnsTask() {
-        return true;
-    }
-
-    public static boolean shouldCancelScanTaskWhenFutureIsNull() {
-        return false;
-    }
-
     public static long sleepTimeForSocketThreadMs() {
         return 20_000L;
     }
diff --git a/service-t/src/com/android/server/connectivity/mdns/MdnsConstants.java b/service-t/src/com/android/server/connectivity/mdns/MdnsConstants.java
index ce5f540..0c32cf1 100644
--- a/service-t/src/com/android/server/connectivity/mdns/MdnsConstants.java
+++ b/service-t/src/com/android/server/connectivity/mdns/MdnsConstants.java
@@ -16,18 +16,13 @@
 
 package com.android.server.connectivity.mdns;
 
-import static com.android.internal.annotations.VisibleForTesting.Visibility.PACKAGE;
-
 import static java.nio.charset.StandardCharsets.UTF_8;
 
-import com.android.internal.annotations.VisibleForTesting;
-
 import java.net.InetAddress;
 import java.net.UnknownHostException;
 import java.nio.charset.Charset;
 
 /** mDNS-related constants. */
-@VisibleForTesting(visibility = PACKAGE)
 public final class MdnsConstants {
     public static final int MDNS_PORT = 5353;
     // Flags word format is:
diff --git a/service-t/src/com/android/server/connectivity/mdns/MdnsDiscoveryManager.java b/service-t/src/com/android/server/connectivity/mdns/MdnsDiscoveryManager.java
index dfaec75..d55098c 100644
--- a/service-t/src/com/android/server/connectivity/mdns/MdnsDiscoveryManager.java
+++ b/service-t/src/com/android/server/connectivity/mdns/MdnsDiscoveryManager.java
@@ -51,6 +51,7 @@
     @NonNull private final PerSocketServiceTypeClients perSocketServiceTypeClients;
     @NonNull private final Handler handler;
     @Nullable private final HandlerThread handlerThread;
+    @NonNull private final MdnsServiceCache serviceCache;
 
     private static class PerSocketServiceTypeClients {
         private final ArrayMap<Pair<String, SocketKey>, MdnsServiceTypeClient> clients =
@@ -119,10 +120,12 @@
         if (socketClient.getLooper() != null) {
             this.handlerThread = null;
             this.handler = new Handler(socketClient.getLooper());
+            this.serviceCache = new MdnsServiceCache(socketClient.getLooper());
         } else {
             this.handlerThread = new HandlerThread(MdnsDiscoveryManager.class.getSimpleName());
             this.handlerThread.start();
             this.handler = new Handler(handlerThread.getLooper());
+            this.serviceCache = new MdnsServiceCache(handlerThread.getLooper());
         }
     }
 
@@ -201,6 +204,7 @@
                         if (serviceTypeClient == null) return;
                         // Notify all listeners that all services are removed from this socket.
                         serviceTypeClient.notifySocketDestroyed();
+                        executorProvider.shutdownExecutorService(serviceTypeClient.getExecutor());
                         perSocketServiceTypeClients.remove(serviceTypeClient);
                     }
                 });
@@ -235,6 +239,7 @@
             if (serviceTypeClient.stopSendAndReceive(listener)) {
                 // No listener is registered for the service type anymore, remove it from the list
                 // of the service type clients.
+                executorProvider.shutdownExecutorService(serviceTypeClient.getExecutor());
                 perSocketServiceTypeClients.remove(serviceTypeClient);
             }
         }
@@ -289,6 +294,6 @@
         return new MdnsServiceTypeClient(
                 serviceType, socketClient,
                 executorProvider.newServiceTypeClientSchedulerExecutor(), socketKey,
-                sharedLog.forSubComponent(tag), handler.getLooper());
+                sharedLog.forSubComponent(tag), handler.getLooper(), serviceCache);
     }
 }
\ No newline at end of file
diff --git a/service-t/src/com/android/server/connectivity/mdns/MdnsResponseDecoder.java b/service-t/src/com/android/server/connectivity/mdns/MdnsResponseDecoder.java
index eff1880..a0a538e 100644
--- a/service-t/src/com/android/server/connectivity/mdns/MdnsResponseDecoder.java
+++ b/service-t/src/com/android/server/connectivity/mdns/MdnsResponseDecoder.java
@@ -19,7 +19,6 @@
 import android.annotation.NonNull;
 import android.annotation.Nullable;
 import android.net.Network;
-import android.os.SystemClock;
 import android.util.ArrayMap;
 import android.util.ArraySet;
 import android.util.Pair;
@@ -40,10 +39,10 @@
     private final boolean allowMultipleSrvRecordsPerHost =
             MdnsConfigs.allowMultipleSrvRecordsPerHost();
     @Nullable private final String[] serviceType;
-    private final Clock clock;
+    private final MdnsUtils.Clock clock;
 
     /** Constructs a new decoder that will extract responses for the given service type. */
-    public MdnsResponseDecoder(@NonNull Clock clock, @Nullable String[] serviceType) {
+    public MdnsResponseDecoder(@NonNull MdnsUtils.Clock clock, @Nullable String[] serviceType) {
         this.clock = clock;
         this.serviceType = serviceType;
     }
@@ -330,10 +329,4 @@
         }
         return result == null ? List.of() : result;
     }
-
-    public static class Clock {
-        public long elapsedRealtime() {
-            return SystemClock.elapsedRealtime();
-        }
-    }
 }
\ No newline at end of file
diff --git a/service-t/src/com/android/server/connectivity/mdns/MdnsServiceCache.java b/service-t/src/com/android/server/connectivity/mdns/MdnsServiceCache.java
index dc99e49..ec6af9b 100644
--- a/service-t/src/com/android/server/connectivity/mdns/MdnsServiceCache.java
+++ b/service-t/src/com/android/server/connectivity/mdns/MdnsServiceCache.java
@@ -96,7 +96,14 @@
                 : Collections.emptyList();
     }
 
-    private MdnsResponse findMatchedResponse(@NonNull List<MdnsResponse> responses,
+    /**
+     * Find a matched response for given service name
+     *
+     * @param responses the responses to be searched.
+     * @param serviceName the target service name
+     * @return the response which matches the given service name or null if not found.
+     */
+    public static MdnsResponse findMatchedResponse(@NonNull List<MdnsResponse> responses,
             @NonNull String serviceName) {
         for (MdnsResponse response : responses) {
             if (equalsIgnoreDnsCase(serviceName, response.getServiceInstanceName())) {
diff --git a/service-t/src/com/android/server/connectivity/mdns/MdnsServiceTypeClient.java b/service-t/src/com/android/server/connectivity/mdns/MdnsServiceTypeClient.java
index 9c49b8f..b5fd8a0 100644
--- a/service-t/src/com/android/server/connectivity/mdns/MdnsServiceTypeClient.java
+++ b/service-t/src/com/android/server/connectivity/mdns/MdnsServiceTypeClient.java
@@ -16,20 +16,20 @@
 
 package com.android.server.connectivity.mdns;
 
+import static com.android.server.connectivity.mdns.MdnsServiceCache.findMatchedResponse;
+import static com.android.server.connectivity.mdns.util.MdnsUtils.Clock;
 import static com.android.server.connectivity.mdns.util.MdnsUtils.ensureRunningOnHandlerThread;
 
-import static java.util.concurrent.TimeUnit.MILLISECONDS;
-
 import android.annotation.NonNull;
 import android.annotation.Nullable;
 import android.os.Handler;
 import android.os.Looper;
+import android.os.Message;
 import android.text.TextUtils;
 import android.util.ArrayMap;
 import android.util.ArraySet;
 import android.util.Pair;
 
-import com.android.internal.annotations.GuardedBy;
 import com.android.internal.annotations.VisibleForTesting;
 import com.android.net.module.util.CollectionUtils;
 import com.android.net.module.util.SharedLog;
@@ -39,13 +39,9 @@
 import java.net.Inet6Address;
 import java.util.ArrayList;
 import java.util.Arrays;
-import java.util.Collection;
 import java.util.Collections;
-import java.util.HashMap;
 import java.util.Iterator;
 import java.util.List;
-import java.util.Map;
-import java.util.concurrent.Future;
 import java.util.concurrent.ScheduledExecutorService;
 
 /**
@@ -56,6 +52,10 @@
 
     private static final String TAG = MdnsServiceTypeClient.class.getSimpleName();
     private static final int DEFAULT_MTU = 1500;
+    @VisibleForTesting
+    static final int EVENT_START_QUERYTASK = 1;
+    static final int EVENT_QUERY_RESULT = 2;
+    static final int INVALID_TRANSACTION_ID = -1;
 
     private final String serviceType;
     private final String[] serviceTypeLabels;
@@ -65,15 +65,16 @@
     @NonNull private final SocketKey socketKey;
     @NonNull private final SharedLog sharedLog;
     @NonNull private final Handler handler;
-    private final Object lock = new Object();
+    @NonNull private final Dependencies dependencies;
+    /**
+     * The service caches for each socket. It should be accessed from looper thread only.
+     */
+    @NonNull private final MdnsServiceCache serviceCache;
     private final ArrayMap<MdnsServiceBrowserListener, MdnsSearchOptions> listeners =
             new ArrayMap<>();
-    // TODO: change instanceNameToResponse to TreeMap with case insensitive comparator.
-    @GuardedBy("lock")
-    private final Map<String, MdnsResponse> instanceNameToResponse = new HashMap<>();
     private final boolean removeServiceAfterTtlExpires =
             MdnsConfigs.removeServiceAfterTtlExpires();
-    private final MdnsResponseDecoder.Clock clock;
+    private final Clock clock;
 
     @Nullable private MdnsSearchOptions searchOptions;
 
@@ -82,17 +83,102 @@
     // new subtypes. It stays the same between packets for same subtypes.
     private long currentSessionId = 0;
 
-    @GuardedBy("lock")
     @Nullable
-    private Future<?> nextQueryTaskFuture;
-
-    @GuardedBy("lock")
-    @Nullable
-    private QueryTask lastScheduledTask;
-
-    @GuardedBy("lock")
+    private ScheduledQueryTaskArgs lastScheduledQueryTaskArgs;
     private long lastSentTime;
 
+    private class QueryTaskHandler extends Handler {
+        QueryTaskHandler(Looper looper) {
+            super(looper);
+        }
+
+        @Override
+        @SuppressWarnings("FutureReturnValueIgnored")
+        public void handleMessage(Message msg) {
+            switch (msg.what) {
+                case EVENT_START_QUERYTASK: {
+                    final ScheduledQueryTaskArgs taskArgs = (ScheduledQueryTaskArgs) msg.obj;
+                    // QueryTask should be run immediately after being created (not be scheduled in
+                    // advance). Because the result of "makeResponsesForResolve" depends on answers
+                    // that were received before it is called, so to take into account all answers
+                    // before sending the query, it needs to be called just before sending it.
+                    final List<MdnsResponse> servicesToResolve = makeResponsesForResolve(socketKey);
+                    final QueryTask queryTask = new QueryTask(taskArgs, servicesToResolve,
+                            servicesToResolve.size() < listeners.size() /* sendDiscoveryQueries */);
+                    executor.submit(queryTask);
+                    break;
+                }
+                case EVENT_QUERY_RESULT: {
+                    final QuerySentArguments sentResult = (QuerySentArguments) msg.obj;
+                    // If a task is cancelled while the Executor is running it, EVENT_QUERY_RESULT
+                    // will still be sent when it ends. So use session ID to check if this task
+                    // should continue to schedule more.
+                    if (sentResult.taskArgs.sessionId != currentSessionId) {
+                        break;
+                    }
+
+                    if ((sentResult.transactionId != INVALID_TRANSACTION_ID)) {
+                        for (int i = 0; i < listeners.size(); i++) {
+                            listeners.keyAt(i).onDiscoveryQuerySent(
+                                    sentResult.subTypes, sentResult.transactionId);
+                        }
+                    }
+
+                    tryRemoveServiceAfterTtlExpires();
+
+                    final QueryTaskConfig nextRunConfig =
+                            sentResult.taskArgs.config.getConfigForNextRun();
+                    final long now = clock.elapsedRealtime();
+                    lastSentTime = now;
+                    final long minRemainingTtl = getMinRemainingTtl(now);
+                    final long timeToRun = calculateTimeToRun(lastScheduledQueryTaskArgs,
+                            nextRunConfig, now, minRemainingTtl, lastSentTime);
+                    scheduleNextRun(nextRunConfig, minRemainingTtl, now, timeToRun,
+                            lastScheduledQueryTaskArgs.sessionId);
+                    break;
+                }
+                default:
+                    sharedLog.e("Unrecognized event " + msg.what);
+                    break;
+            }
+        }
+    }
+
+    /**
+     * Dependencies of MdnsServiceTypeClient, for injection in tests.
+     */
+    @VisibleForTesting
+    public static class Dependencies {
+        /**
+         * @see Handler#sendMessageDelayed(Message, long)
+         */
+        public void sendMessageDelayed(@NonNull Handler handler, @NonNull Message message,
+                long delayMillis) {
+            handler.sendMessageDelayed(message, delayMillis);
+        }
+
+        /**
+         * @see Handler#removeMessages(int)
+         */
+        public void removeMessages(@NonNull Handler handler, int what) {
+            handler.removeMessages(what);
+        }
+
+        /**
+         * @see Handler#hasMessages(int)
+         */
+        public boolean hasMessages(@NonNull Handler handler, int what) {
+            return handler.hasMessages(what);
+        }
+
+        /**
+         * @see Handler#post(Runnable)
+         */
+        public void sendMessage(@NonNull Handler handler, @NonNull Message message) {
+            handler.sendMessage(message);
+        }
+    }
+
     /**
      * Constructor of {@link MdnsServiceTypeClient}.
      *
@@ -105,9 +191,10 @@
             @NonNull ScheduledExecutorService executor,
             @NonNull SocketKey socketKey,
             @NonNull SharedLog sharedLog,
-            @NonNull Looper looper) {
-        this(serviceType, socketClient, executor, new MdnsResponseDecoder.Clock(), socketKey,
-                sharedLog, looper);
+            @NonNull Looper looper,
+            @NonNull MdnsServiceCache serviceCache) {
+        this(serviceType, socketClient, executor, new Clock(), socketKey, sharedLog, looper,
+                new Dependencies(), serviceCache);
     }
 
     @VisibleForTesting
@@ -115,10 +202,12 @@
             @NonNull String serviceType,
             @NonNull MdnsSocketClientBase socketClient,
             @NonNull ScheduledExecutorService executor,
-            @NonNull MdnsResponseDecoder.Clock clock,
+            @NonNull Clock clock,
             @NonNull SocketKey socketKey,
             @NonNull SharedLog sharedLog,
-            @NonNull Looper looper) {
+            @NonNull Looper looper,
+            @NonNull Dependencies dependencies,
+            @NonNull MdnsServiceCache serviceCache) {
         this.serviceType = serviceType;
         this.socketClient = socketClient;
         this.executor = executor;
@@ -127,7 +216,9 @@
         this.clock = clock;
         this.socketKey = socketKey;
         this.sharedLog = sharedLog;
-        this.handler = new Handler(looper);
+        this.handler = new QueryTaskHandler(looper);
+        this.dependencies = dependencies;
+        this.serviceCache = serviceCache;
     }
 
     private static MdnsServiceInfo buildMdnsServiceInfoFromResponse(
@@ -187,69 +278,70 @@
      * @param listener      The {@link MdnsServiceBrowserListener} to register.
      * @param searchOptions {@link MdnsSearchOptions} contains the list of subtypes to discover.
      */
+    @SuppressWarnings("FutureReturnValueIgnored")
     public void startSendAndReceive(
             @NonNull MdnsServiceBrowserListener listener,
             @NonNull MdnsSearchOptions searchOptions) {
         ensureRunningOnHandlerThread(handler);
-        synchronized (lock) {
-            this.searchOptions = searchOptions;
-            boolean hadReply = false;
-            if (listeners.put(listener, searchOptions) == null) {
-                for (MdnsResponse existingResponse : instanceNameToResponse.values()) {
-                    if (!responseMatchesOptions(existingResponse, searchOptions)) continue;
-                    final MdnsServiceInfo info =
-                            buildMdnsServiceInfoFromResponse(existingResponse, serviceTypeLabels);
-                    listener.onServiceNameDiscovered(info);
-                    if (existingResponse.isComplete()) {
-                        listener.onServiceFound(info);
-                        hadReply = true;
-                    }
+        this.searchOptions = searchOptions;
+        boolean hadReply = false;
+        if (listeners.put(listener, searchOptions) == null) {
+            for (MdnsResponse existingResponse :
+                    serviceCache.getCachedServices(serviceType, socketKey)) {
+                if (!responseMatchesOptions(existingResponse, searchOptions)) continue;
+                final MdnsServiceInfo info =
+                        buildMdnsServiceInfoFromResponse(existingResponse, serviceTypeLabels);
+                listener.onServiceNameDiscovered(info);
+                if (existingResponse.isComplete()) {
+                    listener.onServiceFound(info);
+                    hadReply = true;
                 }
             }
-            // Cancel the next scheduled periodical task.
-            if (nextQueryTaskFuture != null) {
-                cancelRequestTaskLocked();
-            }
-            // Keep tracking the ScheduledFuture for the task so we can cancel it if caller is not
-            // interested anymore.
-            final QueryTaskConfig taskConfig = new QueryTaskConfig(
-                    searchOptions.getSubtypes(),
-                    searchOptions.isPassiveMode(),
-                    searchOptions.onlyUseIpv6OnIpv6OnlyNetworks(),
-                    searchOptions.numOfQueriesBeforeBackoff(),
-                    socketKey);
-            final long now = clock.elapsedRealtime();
-            if (lastSentTime == 0) {
-                lastSentTime = now;
-            }
-            if (hadReply) {
-                final QueryTaskConfig queryTaskConfig = taskConfig.getConfigForNextRun();
-                final long minRemainingTtl = getMinRemainingTtlLocked(now);
-                final long timeToRun = now + queryTaskConfig.delayUntilNextTaskWithoutBackoffMs;
-                nextQueryTaskFuture = scheduleNextRunLocked(queryTaskConfig,
-                        minRemainingTtl, now, timeToRun, currentSessionId);
-            } else {
-                lastScheduledTask = new QueryTask(taskConfig,
-                        now /* timeToRun */,
-                        now + getMinRemainingTtlLocked(now)/* minTtlExpirationTimeWhenScheduled */,
-                        currentSessionId);
-                nextQueryTaskFuture = executor.submit(lastScheduledTask);
-            }
+        }
+        // Remove the next scheduled periodical task.
+        removeScheduledTask();
+        // Keep tracking the ScheduledFuture for the task so we can cancel it if caller is not
+        // interested anymore.
+        final QueryTaskConfig taskConfig = new QueryTaskConfig(
+                searchOptions.getSubtypes(),
+                searchOptions.isPassiveMode(),
+                searchOptions.onlyUseIpv6OnIpv6OnlyNetworks(),
+                searchOptions.numOfQueriesBeforeBackoff(),
+                socketKey);
+        final long now = clock.elapsedRealtime();
+        if (lastSentTime == 0) {
+            lastSentTime = now;
+        }
+        if (hadReply) {
+            final QueryTaskConfig queryTaskConfig = taskConfig.getConfigForNextRun();
+            final long minRemainingTtl = getMinRemainingTtl(now);
+            final long timeToRun = now + queryTaskConfig.delayUntilNextTaskWithoutBackoffMs;
+            scheduleNextRun(
+                    queryTaskConfig, minRemainingTtl, now, timeToRun, currentSessionId);
+        } else {
+            final List<MdnsResponse> servicesToResolve = makeResponsesForResolve(socketKey);
+            lastScheduledQueryTaskArgs = new ScheduledQueryTaskArgs(taskConfig, now /* timeToRun */,
+                    now + getMinRemainingTtl(now)/* minTtlExpirationTimeWhenScheduled */,
+                    currentSessionId);
+            final QueryTask queryTask = new QueryTask(lastScheduledQueryTaskArgs, servicesToResolve,
+                    servicesToResolve.size() < listeners.size() /* sendDiscoveryQueries */);
+            executor.submit(queryTask);
         }
     }
 
-    @GuardedBy("lock")
-    private void cancelRequestTaskLocked() {
-        final boolean canceled = nextQueryTaskFuture.cancel(true);
-        sharedLog.log("task canceled:" + canceled + ", current session: " + currentSessionId
-                + " task hashcode: " + getHexString(nextQueryTaskFuture));
-        ++currentSessionId;
-        nextQueryTaskFuture = null;
-        lastScheduledTask = null;
+    /**
+     * Get the executor service.
+     */
+    public ScheduledExecutorService getExecutor() {
+        return executor;
     }
 
-    private static String getHexString(Object o) {
-        return Integer.toHexString(System.identityHashCode(o));
+    private void removeScheduledTask() {
+        dependencies.removeMessages(handler, EVENT_START_QUERYTASK);
+        sharedLog.log("Remove EVENT_START_QUERYTASK"
+                + ", current session: " + currentSessionId);
+        ++currentSessionId;
+        lastScheduledQueryTaskArgs = null;
     }
 
     private boolean responseMatchesOptions(@NonNull MdnsResponse response,
@@ -281,15 +373,13 @@
      */
     public boolean stopSendAndReceive(@NonNull MdnsServiceBrowserListener listener) {
         ensureRunningOnHandlerThread(handler);
-        synchronized (lock) {
-            if (listeners.remove(listener) == null) {
-                return listeners.isEmpty();
-            }
-            if (listeners.isEmpty() && nextQueryTaskFuture != null) {
-                cancelRequestTaskLocked();
-            }
+        if (listeners.remove(listener) == null) {
             return listeners.isEmpty();
         }
+        if (listeners.isEmpty()) {
+            removeScheduledTask();
+        }
+        return listeners.isEmpty();
     }
 
     /**
@@ -298,50 +388,51 @@
     public synchronized void processResponse(@NonNull MdnsPacket packet,
             @NonNull SocketKey socketKey) {
         ensureRunningOnHandlerThread(handler);
-        synchronized (lock) {
-            // Augment the list of current known responses, and generated responses for resolve
-            // requests if there is no known response
-            final List<MdnsResponse> currentList = new ArrayList<>(instanceNameToResponse.values());
-            List<MdnsResponse> additionalResponses = makeResponsesForResolve(socketKey);
-            for (MdnsResponse additionalResponse : additionalResponses) {
-                if (!instanceNameToResponse.containsKey(
-                        additionalResponse.getServiceInstanceName())) {
-                    currentList.add(additionalResponse);
-                }
+        // Augment the list of current known responses, and generated responses for resolve
+        // requests if there is no known response
+        final List<MdnsResponse> cachedList =
+                serviceCache.getCachedServices(serviceType, socketKey);
+        final List<MdnsResponse> currentList = new ArrayList<>(cachedList);
+        List<MdnsResponse> additionalResponses = makeResponsesForResolve(socketKey);
+        for (MdnsResponse additionalResponse : additionalResponses) {
+            if (findMatchedResponse(
+                    cachedList, additionalResponse.getServiceInstanceName()) == null) {
+                currentList.add(additionalResponse);
             }
-            final Pair<ArraySet<MdnsResponse>, ArrayList<MdnsResponse>> augmentedResult =
-                    responseDecoder.augmentResponses(packet, currentList,
-                            socketKey.getInterfaceIndex(), socketKey.getNetwork());
+        }
+        final Pair<ArraySet<MdnsResponse>, ArrayList<MdnsResponse>> augmentedResult =
+                responseDecoder.augmentResponses(packet, currentList,
+                        socketKey.getInterfaceIndex(), socketKey.getNetwork());
 
-            final ArraySet<MdnsResponse> modifiedResponse = augmentedResult.first;
-            final ArrayList<MdnsResponse> allResponses = augmentedResult.second;
+        final ArraySet<MdnsResponse> modifiedResponse = augmentedResult.first;
+        final ArrayList<MdnsResponse> allResponses = augmentedResult.second;
 
-            for (MdnsResponse response : allResponses) {
-                if (modifiedResponse.contains(response)) {
-                    if (response.isGoodbye()) {
-                        onGoodbyeReceivedLocked(response.getServiceInstanceName());
-                    } else {
-                        onResponseModifiedLocked(response);
-                    }
-                } else if (instanceNameToResponse.containsKey(response.getServiceInstanceName())) {
-                    // If the response is not modified and already in the cache. The cache will
-                    // need to be updated to refresh the last receipt time.
-                    instanceNameToResponse.put(response.getServiceInstanceName(), response);
+        for (MdnsResponse response : allResponses) {
+            final String serviceInstanceName = response.getServiceInstanceName();
+            if (modifiedResponse.contains(response)) {
+                if (response.isGoodbye()) {
+                    onGoodbyeReceived(serviceInstanceName);
+                } else {
+                    onResponseModified(response);
                 }
+            } else if (findMatchedResponse(cachedList, serviceInstanceName) != null) {
+                // If the response is not modified and already in the cache. The cache will
+                // need to be updated to refresh the last receipt time.
+                serviceCache.addOrUpdateService(serviceType, socketKey, response);
             }
-            if (nextQueryTaskFuture != null && lastScheduledTask != null
-                    && lastScheduledTask.config.shouldUseQueryBackoff()) {
-                final long now = clock.elapsedRealtime();
-                final long minRemainingTtl = getMinRemainingTtlLocked(now);
-                final long timeToRun = calculateTimeToRun(lastScheduledTask,
-                        lastScheduledTask.config, now,
-                        minRemainingTtl, lastSentTime);
-                if (timeToRun > lastScheduledTask.timeToRun) {
-                    QueryTaskConfig lastTaskConfig = lastScheduledTask.config;
-                    cancelRequestTaskLocked();
-                    nextQueryTaskFuture = scheduleNextRunLocked(lastTaskConfig, minRemainingTtl,
-                            now, timeToRun, currentSessionId);
-                }
+        }
+        if (dependencies.hasMessages(handler, EVENT_START_QUERYTASK)
+                && lastScheduledQueryTaskArgs != null
+                && lastScheduledQueryTaskArgs.config.shouldUseQueryBackoff()) {
+            final long now = clock.elapsedRealtime();
+            final long minRemainingTtl = getMinRemainingTtl(now);
+            final long timeToRun = calculateTimeToRun(lastScheduledQueryTaskArgs,
+                    lastScheduledQueryTaskArgs.config, now,
+                    minRemainingTtl, lastSentTime);
+            if (timeToRun > lastScheduledQueryTaskArgs.timeToRun) {
+                QueryTaskConfig lastTaskConfig = lastScheduledQueryTaskArgs.config;
+                removeScheduledTask();
+                scheduleNextRun(lastTaskConfig, minRemainingTtl, now, timeToRun, currentSessionId);
             }
         }
     }
@@ -356,46 +447,40 @@
     /** Notify all services are removed because the socket is destroyed. */
     public void notifySocketDestroyed() {
         ensureRunningOnHandlerThread(handler);
-        synchronized (lock) {
-            for (MdnsResponse response : instanceNameToResponse.values()) {
-                final String name = response.getServiceInstanceName();
-                if (name == null) continue;
-                for (int i = 0; i < listeners.size(); i++) {
-                    if (!responseMatchesOptions(response, listeners.valueAt(i))) continue;
-                    final MdnsServiceBrowserListener listener = listeners.keyAt(i);
-                    final MdnsServiceInfo serviceInfo =
-                            buildMdnsServiceInfoFromResponse(response, serviceTypeLabels);
-                    if (response.isComplete()) {
-                        sharedLog.log("Socket destroyed. onServiceRemoved: " + name);
-                        listener.onServiceRemoved(serviceInfo);
-                    }
-                    sharedLog.log("Socket destroyed. onServiceNameRemoved: " + name);
-                    listener.onServiceNameRemoved(serviceInfo);
+        for (MdnsResponse response : serviceCache.getCachedServices(serviceType, socketKey)) {
+            final String name = response.getServiceInstanceName();
+            if (name == null) continue;
+            for (int i = 0; i < listeners.size(); i++) {
+                if (!responseMatchesOptions(response, listeners.valueAt(i))) continue;
+                final MdnsServiceBrowserListener listener = listeners.keyAt(i);
+                final MdnsServiceInfo serviceInfo =
+                        buildMdnsServiceInfoFromResponse(response, serviceTypeLabels);
+                if (response.isComplete()) {
+                    sharedLog.log("Socket destroyed. onServiceRemoved: " + name);
+                    listener.onServiceRemoved(serviceInfo);
                 }
-            }
-
-            if (nextQueryTaskFuture != null) {
-                cancelRequestTaskLocked();
+                sharedLog.log("Socket destroyed. onServiceNameRemoved: " + name);
+                listener.onServiceNameRemoved(serviceInfo);
             }
         }
+        removeScheduledTask();
     }
 
-    @GuardedBy("lock")
-    private void onResponseModifiedLocked(@NonNull MdnsResponse response) {
+    private void onResponseModified(@NonNull MdnsResponse response) {
         final String serviceInstanceName = response.getServiceInstanceName();
         final MdnsResponse currentResponse =
-                instanceNameToResponse.get(serviceInstanceName);
+                serviceCache.getCachedService(serviceInstanceName, serviceType, socketKey);
 
         boolean newServiceFound = false;
         boolean serviceBecomesComplete = false;
         if (currentResponse == null) {
             newServiceFound = true;
             if (serviceInstanceName != null) {
-                instanceNameToResponse.put(serviceInstanceName, response);
+                serviceCache.addOrUpdateService(serviceType, socketKey, response);
             }
         } else {
             boolean before = currentResponse.isComplete();
-            instanceNameToResponse.put(serviceInstanceName, response);
+            serviceCache.addOrUpdateService(serviceType, socketKey, response);
             boolean after = response.isComplete();
             serviceBecomesComplete = !before && after;
         }
@@ -427,9 +512,9 @@
         }
     }
 
-    @GuardedBy("lock")
-    private void onGoodbyeReceivedLocked(@Nullable String serviceInstanceName) {
-        final MdnsResponse response = instanceNameToResponse.remove(serviceInstanceName);
+    private void onGoodbyeReceived(@Nullable String serviceInstanceName) {
+        final MdnsResponse response =
+                serviceCache.removeService(serviceInstanceName, serviceType, socketKey);
         if (response == null) {
             return;
         }
@@ -459,145 +544,6 @@
         return new MdnsPacketWriter(DEFAULT_MTU);
     }
 
-    // A configuration for the PeriodicalQueryTask that contains parameters to build a query packet.
-    // Call to getConfigForNextRun returns a config that can be used to build the next query task.
-    @VisibleForTesting
-    static class QueryTaskConfig {
-
-        private static final int INITIAL_TIME_BETWEEN_BURSTS_MS =
-                (int) MdnsConfigs.initialTimeBetweenBurstsMs();
-        private static final int TIME_BETWEEN_BURSTS_MS = (int) MdnsConfigs.timeBetweenBurstsMs();
-        private static final int QUERIES_PER_BURST = (int) MdnsConfigs.queriesPerBurst();
-        private static final int TIME_BETWEEN_QUERIES_IN_BURST_MS =
-                (int) MdnsConfigs.timeBetweenQueriesInBurstMs();
-        private static final int QUERIES_PER_BURST_PASSIVE_MODE =
-                (int) MdnsConfigs.queriesPerBurstPassive();
-        private static final int UNSIGNED_SHORT_MAX_VALUE = 65536;
-        // The following fields are used by QueryTask so we need to test them.
-        @VisibleForTesting
-        final List<String> subtypes;
-        private final boolean alwaysAskForUnicastResponse =
-                MdnsConfigs.alwaysAskForUnicastResponseInEachBurst();
-        private final boolean usePassiveMode;
-        private final boolean onlyUseIpv6OnIpv6OnlyNetworks;
-        private final int numOfQueriesBeforeBackoff;
-        @VisibleForTesting
-        final int transactionId;
-        @VisibleForTesting
-        final boolean expectUnicastResponse;
-        private final int queriesPerBurst;
-        private final int timeBetweenBurstsInMs;
-        private final int burstCounter;
-        private final long delayUntilNextTaskWithoutBackoffMs;
-        private final boolean isFirstBurst;
-        private final long queryCount;
-        @NonNull private final SocketKey socketKey;
-
-
-        QueryTaskConfig(@NonNull QueryTaskConfig other, long queryCount, int transactionId,
-                boolean expectUnicastResponse, boolean isFirstBurst, int burstCounter,
-                int queriesPerBurst, int timeBetweenBurstsInMs,
-                long delayUntilNextTaskWithoutBackoffMs) {
-            this.subtypes = new ArrayList<>(other.subtypes);
-            this.usePassiveMode = other.usePassiveMode;
-            this.onlyUseIpv6OnIpv6OnlyNetworks = other.onlyUseIpv6OnIpv6OnlyNetworks;
-            this.numOfQueriesBeforeBackoff = other.numOfQueriesBeforeBackoff;
-            this.transactionId = transactionId;
-            this.expectUnicastResponse = expectUnicastResponse;
-            this.queriesPerBurst = queriesPerBurst;
-            this.timeBetweenBurstsInMs = timeBetweenBurstsInMs;
-            this.burstCounter = burstCounter;
-            this.delayUntilNextTaskWithoutBackoffMs = delayUntilNextTaskWithoutBackoffMs;
-            this.isFirstBurst = isFirstBurst;
-            this.queryCount = queryCount;
-            this.socketKey = other.socketKey;
-        }
-        QueryTaskConfig(@NonNull Collection<String> subtypes,
-                boolean usePassiveMode,
-                boolean onlyUseIpv6OnIpv6OnlyNetworks,
-                int numOfQueriesBeforeBackoff,
-                @Nullable SocketKey socketKey) {
-            this.usePassiveMode = usePassiveMode;
-            this.onlyUseIpv6OnIpv6OnlyNetworks = onlyUseIpv6OnIpv6OnlyNetworks;
-            this.numOfQueriesBeforeBackoff = numOfQueriesBeforeBackoff;
-            this.subtypes = new ArrayList<>(subtypes);
-            this.queriesPerBurst = QUERIES_PER_BURST;
-            this.burstCounter = 0;
-            this.transactionId = 1;
-            this.expectUnicastResponse = true;
-            this.isFirstBurst = true;
-            // Config the scan frequency based on the scan mode.
-            if (this.usePassiveMode) {
-                // In passive scan mode, sends a single burst of QUERIES_PER_BURST queries, and then
-                // in each TIME_BETWEEN_BURSTS interval, sends QUERIES_PER_BURST_PASSIVE_MODE
-                // queries.
-                this.timeBetweenBurstsInMs = TIME_BETWEEN_BURSTS_MS;
-            } else {
-                // In active scan mode, sends a burst of QUERIES_PER_BURST queries,
-                // TIME_BETWEEN_QUERIES_IN_BURST_MS apart, then waits for the scan interval, and
-                // then repeats. The scan interval starts as INITIAL_TIME_BETWEEN_BURSTS_MS and
-                // doubles until it maxes out at TIME_BETWEEN_BURSTS_MS.
-                this.timeBetweenBurstsInMs = INITIAL_TIME_BETWEEN_BURSTS_MS;
-            }
-            this.socketKey = socketKey;
-            this.queryCount = 0;
-            this.delayUntilNextTaskWithoutBackoffMs = TIME_BETWEEN_QUERIES_IN_BURST_MS;
-        }
-
-        QueryTaskConfig getConfigForNextRun() {
-            long newQueryCount = queryCount + 1;
-            int newTransactionId = transactionId + 1;
-            if (newTransactionId > UNSIGNED_SHORT_MAX_VALUE) {
-                newTransactionId = 1;
-            }
-            boolean newExpectUnicastResponse = false;
-            boolean newIsFirstBurst = isFirstBurst;
-            int newQueriesPerBurst = queriesPerBurst;
-            int newBurstCounter = burstCounter + 1;
-            long newDelayUntilNextTaskWithoutBackoffMs = delayUntilNextTaskWithoutBackoffMs;
-            int newTimeBetweenBurstsInMs = timeBetweenBurstsInMs;
-            // Only the first query expects uni-cast response.
-            if (newBurstCounter == queriesPerBurst) {
-                newBurstCounter = 0;
-
-                if (alwaysAskForUnicastResponse) {
-                    newExpectUnicastResponse = true;
-                }
-                // In passive scan mode, sends a single burst of QUERIES_PER_BURST queries, and
-                // then in each TIME_BETWEEN_BURSTS interval, sends QUERIES_PER_BURST_PASSIVE_MODE
-                // queries.
-                if (isFirstBurst) {
-                    newIsFirstBurst = false;
-                    if (usePassiveMode) {
-                        newQueriesPerBurst = QUERIES_PER_BURST_PASSIVE_MODE;
-                    }
-                }
-                // In active scan mode, sends a burst of QUERIES_PER_BURST queries,
-                // TIME_BETWEEN_QUERIES_IN_BURST_MS apart, then waits for the scan interval, and
-                // then repeats. The scan interval starts as INITIAL_TIME_BETWEEN_BURSTS_MS and
-                // doubles until it maxes out at TIME_BETWEEN_BURSTS_MS.
-                newDelayUntilNextTaskWithoutBackoffMs = timeBetweenBurstsInMs;
-                if (timeBetweenBurstsInMs < TIME_BETWEEN_BURSTS_MS) {
-                    newTimeBetweenBurstsInMs = Math.min(timeBetweenBurstsInMs * 2,
-                            TIME_BETWEEN_BURSTS_MS);
-                }
-            } else {
-                newDelayUntilNextTaskWithoutBackoffMs = TIME_BETWEEN_QUERIES_IN_BURST_MS;
-            }
-            return new QueryTaskConfig(this, newQueryCount, newTransactionId,
-                    newExpectUnicastResponse, newIsFirstBurst, newBurstCounter, newQueriesPerBurst,
-                    newTimeBetweenBurstsInMs, newDelayUntilNextTaskWithoutBackoffMs);
-        }
-
-        private boolean shouldUseQueryBackoff() {
-            // Don't enable backoff mode during the burst or in the first burst
-            if (burstCounter != 0 || isFirstBurst) {
-                return false;
-            }
-            return queryCount > numOfQueriesBeforeBackoff;
-        }
-    }
-
     private List<MdnsResponse> makeResponsesForResolve(@NonNull SocketKey socketKey) {
         final List<MdnsResponse> resolveResponses = new ArrayList<>();
         for (int i = 0; i < listeners.size(); i++) {
@@ -605,7 +551,8 @@
             if (resolveName == null) {
                 continue;
             }
-            MdnsResponse knownResponse = instanceNameToResponse.get(resolveName);
+            MdnsResponse knownResponse =
+                    serviceCache.getCachedService(resolveName, serviceType, socketKey);
             if (knownResponse == null) {
                 final ArrayList<String> instanceFullName = new ArrayList<>(
                         serviceTypeLabels.length + 1);
@@ -620,34 +567,82 @@
         return resolveResponses;
     }
 
-    // A FutureTask that enqueues a single query, and schedule a new FutureTask for the next task.
-    private class QueryTask implements Runnable {
+    private void tryRemoveServiceAfterTtlExpires() {
+        if (!shouldRemoveServiceAfterTtlExpires()) return;
 
+        Iterator<MdnsResponse> iter =
+                serviceCache.getCachedServices(serviceType, socketKey).iterator();
+        while (iter.hasNext()) {
+            MdnsResponse existingResponse = iter.next();
+            final String serviceInstanceName = existingResponse.getServiceInstanceName();
+            if (existingResponse.hasServiceRecord()
+                    && existingResponse.getServiceRecord()
+                    .getRemainingTTL(clock.elapsedRealtime()) == 0) {
+                serviceCache.removeService(serviceInstanceName, serviceType, socketKey);
+                for (int i = 0; i < listeners.size(); i++) {
+                    if (!responseMatchesOptions(existingResponse, listeners.valueAt(i))) {
+                        continue;
+                    }
+                    final MdnsServiceBrowserListener listener = listeners.keyAt(i);
+                    if (serviceInstanceName != null) {
+                        final MdnsServiceInfo serviceInfo = buildMdnsServiceInfoFromResponse(
+                                existingResponse, serviceTypeLabels);
+                        if (existingResponse.isComplete()) {
+                            sharedLog.log("TTL expired. onServiceRemoved: " + serviceInfo);
+                            listener.onServiceRemoved(serviceInfo);
+                        }
+                        sharedLog.log("TTL expired. onServiceNameRemoved: " + serviceInfo);
+                        listener.onServiceNameRemoved(serviceInfo);
+                    }
+                }
+            }
+        }
+    }
+
+    private static class ScheduledQueryTaskArgs {
         private final QueryTaskConfig config;
         private final long timeToRun;
         private final long minTtlExpirationTimeWhenScheduled;
         private final long sessionId;
 
-        QueryTask(@NonNull QueryTaskConfig config, long timeToRun,
-                long minTtlExpirationTimeWhenScheduled,
-                long sessionId) {
+        ScheduledQueryTaskArgs(@NonNull QueryTaskConfig config, long timeToRun,
+                long minTtlExpirationTimeWhenScheduled, long sessionId) {
             this.config = config;
             this.timeToRun = timeToRun;
             this.minTtlExpirationTimeWhenScheduled = minTtlExpirationTimeWhenScheduled;
             this.sessionId = sessionId;
         }
+    }
+
+    private static class QuerySentArguments {
+        private final int transactionId;
+        private final List<String> subTypes = new ArrayList<>();
+        private final ScheduledQueryTaskArgs taskArgs;
+
+        QuerySentArguments(int transactionId, @NonNull List<String> subTypes,
+                @NonNull ScheduledQueryTaskArgs taskArgs) {
+            this.transactionId = transactionId;
+            this.subTypes.addAll(subTypes);
+            this.taskArgs = taskArgs;
+        }
+    }
+
+    // A FutureTask that enqueues a single query, and schedule a new FutureTask for the next task.
+    private class QueryTask implements Runnable {
+
+        private final ScheduledQueryTaskArgs taskArgs;
+        private final List<MdnsResponse> servicesToResolve = new ArrayList<>();
+        private final boolean sendDiscoveryQueries;
+
+        QueryTask(@NonNull ScheduledQueryTaskArgs taskArgs,
+                @NonNull List<MdnsResponse> servicesToResolve, boolean sendDiscoveryQueries) {
+            this.taskArgs = taskArgs;
+            this.servicesToResolve.addAll(servicesToResolve);
+            this.sendDiscoveryQueries = sendDiscoveryQueries;
+        }
 
         @Override
         public void run() {
-            final List<MdnsResponse> servicesToResolve;
-            final boolean sendDiscoveryQueries;
-            synchronized (lock) {
-                // The listener is requesting to resolve a service that has no info in
-                // cache. Use the provided name to generate a minimal response, so other records are
-                // queried to complete it.
-                servicesToResolve = makeResponsesForResolve(config.socketKey);
-                sendDiscoveryQueries = servicesToResolve.size() < listeners.size();
-            }
             Pair<Integer, List<String>> result;
             try {
                 result =
@@ -655,88 +650,27 @@
                                 socketClient,
                                 createMdnsPacketWriter(),
                                 serviceType,
-                                config.subtypes,
-                                config.expectUnicastResponse,
-                                config.transactionId,
-                                config.socketKey,
-                                config.onlyUseIpv6OnIpv6OnlyNetworks,
+                                taskArgs.config.subtypes,
+                                taskArgs.config.expectUnicastResponse,
+                                taskArgs.config.transactionId,
+                                taskArgs.config.socketKey,
+                                taskArgs.config.onlyUseIpv6OnIpv6OnlyNetworks,
                                 sendDiscoveryQueries,
                                 servicesToResolve,
                                 clock)
                                 .call();
             } catch (RuntimeException e) {
                 sharedLog.e(String.format("Failed to run EnqueueMdnsQueryCallable for subtype: %s",
-                        TextUtils.join(",", config.subtypes)), e);
-                result = null;
+                        TextUtils.join(",", taskArgs.config.subtypes)), e);
+                result = Pair.create(INVALID_TRANSACTION_ID, new ArrayList<>());
             }
-            synchronized (lock) {
-                if (MdnsConfigs.useSessionIdToScheduleMdnsTask()) {
-                    // In case that the task is not canceled successfully, use session ID to check
-                    // if this task should continue to schedule more.
-                    if (sessionId != currentSessionId) {
-                        return;
-                    }
-                }
-
-                if (MdnsConfigs.shouldCancelScanTaskWhenFutureIsNull()) {
-                    if (nextQueryTaskFuture == null) {
-                        // If requestTaskFuture is set to null, the task is cancelled. We can't use
-                        // isCancelled() here because this QueryTask is different from the future
-                        // that is returned from executor.schedule(). See b/71646910.
-                        return;
-                    }
-                }
-                if ((result != null)) {
-                    for (int i = 0; i < listeners.size(); i++) {
-                        listeners.keyAt(i).onDiscoveryQuerySent(result.second, result.first);
-                    }
-                }
-                if (shouldRemoveServiceAfterTtlExpires()) {
-                    Iterator<MdnsResponse> iter = instanceNameToResponse.values().iterator();
-                    while (iter.hasNext()) {
-                        MdnsResponse existingResponse = iter.next();
-                        if (existingResponse.hasServiceRecord()
-                                && existingResponse
-                                .getServiceRecord()
-                                .getRemainingTTL(clock.elapsedRealtime())
-                                == 0) {
-                            iter.remove();
-                            for (int i = 0; i < listeners.size(); i++) {
-                                if (!responseMatchesOptions(existingResponse,
-                                        listeners.valueAt(i)))  {
-                                    continue;
-                                }
-                                final MdnsServiceBrowserListener listener = listeners.keyAt(i);
-                                if (existingResponse.getServiceInstanceName() != null) {
-                                    final MdnsServiceInfo serviceInfo =
-                                            buildMdnsServiceInfoFromResponse(
-                                                    existingResponse, serviceTypeLabels);
-                                    if (existingResponse.isComplete()) {
-                                        sharedLog.log("TTL expired. onServiceRemoved: "
-                                                + serviceInfo);
-                                        listener.onServiceRemoved(serviceInfo);
-                                    }
-                                    sharedLog.log("TTL expired. onServiceNameRemoved: "
-                                            + serviceInfo);
-                                    listener.onServiceNameRemoved(serviceInfo);
-                                }
-                            }
-                        }
-                    }
-                }
-                QueryTaskConfig nextRunConfig = this.config.getConfigForNextRun();
-                final long now = clock.elapsedRealtime();
-                lastSentTime = now;
-                final long minRemainingTtl = getMinRemainingTtlLocked(now);
-                final long timeToRun = calculateTimeToRun(this, nextRunConfig, now,
-                        minRemainingTtl, lastSentTime);
-                nextQueryTaskFuture = scheduleNextRunLocked(nextRunConfig,
-                        minRemainingTtl, now, timeToRun, lastScheduledTask.sessionId);
-            }
+            dependencies.sendMessage(
+                    handler, handler.obtainMessage(EVENT_QUERY_RESULT,
+                            new QuerySentArguments(result.first, result.second, taskArgs)));
         }
     }
 
-    private static long calculateTimeToRun(@NonNull QueryTask lastScheduledTask,
+    private static long calculateTimeToRun(@NonNull ScheduledQueryTaskArgs taskArgs,
             QueryTaskConfig queryTaskConfig, long now, long minRemainingTtl, long lastSentTime) {
         final long baseDelayInMs = queryTaskConfig.delayUntilNextTaskWithoutBackoffMs;
         if (!queryTaskConfig.shouldUseQueryBackoff()) {
@@ -749,18 +683,17 @@
         }
         // If the next TTL expiration time hasn't changed, then use previous calculated timeToRun.
         if (lastSentTime < now
-                && lastScheduledTask.minTtlExpirationTimeWhenScheduled == now + minRemainingTtl) {
+                && taskArgs.minTtlExpirationTimeWhenScheduled == now + minRemainingTtl) {
             // Use the original scheduling time if the TTL has not changed, to avoid continuously
             // rescheduling to 80% of the remaining TTL as time passes
-            return lastScheduledTask.timeToRun;
+            return taskArgs.timeToRun;
         }
         return Math.max(now + (long) (0.8 * minRemainingTtl), lastSentTime + baseDelayInMs);
     }
 
-    @GuardedBy("lock")
-    private long getMinRemainingTtlLocked(long now) {
+    private long getMinRemainingTtl(long now) {
         long minRemainingTtl = Long.MAX_VALUE;
-        for (MdnsResponse response : instanceNameToResponse.values()) {
+        for (MdnsResponse response : serviceCache.getCachedServices(serviceType, socketKey)) {
             if (!response.isComplete()) {
                 continue;
             }
@@ -777,19 +710,19 @@
         return minRemainingTtl == Long.MAX_VALUE ? 0 : minRemainingTtl;
     }
 
-    @GuardedBy("lock")
     @NonNull
-    private Future<?> scheduleNextRunLocked(@NonNull QueryTaskConfig nextRunConfig,
+    private void scheduleNextRun(@NonNull QueryTaskConfig nextRunConfig,
             long minRemainingTtl,
             long timeWhenScheduled, long timeToRun, long sessionId) {
-        lastScheduledTask = new QueryTask(nextRunConfig, timeToRun,
+        lastScheduledQueryTaskArgs = new ScheduledQueryTaskArgs(nextRunConfig, timeToRun,
                 minRemainingTtl + timeWhenScheduled, sessionId);
         // The timeWhenScheduled could be greater than the timeToRun if the Runnable is delayed.
         long timeToNextTasksWithBackoffInMs = Math.max(timeToRun - timeWhenScheduled, 0);
-        sharedLog.log(
-                String.format("Next run: sessionId: %d, in %d ms", lastScheduledTask.sessionId,
-                        timeToNextTasksWithBackoffInMs));
-        return executor.schedule(lastScheduledTask, timeToNextTasksWithBackoffInMs,
-                MILLISECONDS);
+        sharedLog.log(String.format("Next run: sessionId: %d, in %d ms",
+                lastScheduledQueryTaskArgs.sessionId, timeToNextTasksWithBackoffInMs));
+        dependencies.sendMessageDelayed(
+                handler,
+                handler.obtainMessage(EVENT_START_QUERYTASK, lastScheduledQueryTaskArgs),
+                timeToNextTasksWithBackoffInMs);
     }
 }
\ No newline at end of file
diff --git a/service-t/src/com/android/server/connectivity/mdns/QueryTaskConfig.java b/service-t/src/com/android/server/connectivity/mdns/QueryTaskConfig.java
new file mode 100644
index 0000000..19282b0
--- /dev/null
+++ b/service-t/src/com/android/server/connectivity/mdns/QueryTaskConfig.java
@@ -0,0 +1,172 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * 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 com.android.server.connectivity.mdns;
+
+import android.annotation.NonNull;
+import android.annotation.Nullable;
+
+import com.android.internal.annotations.VisibleForTesting;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.List;
+
+/**
+ * A configuration for the PeriodicalQueryTask that contains parameters to build a query packet.
+ * Call to getConfigForNextRun returns a config that can be used to build the next query task.
+ */
+public class QueryTaskConfig {
+
+    private static final int INITIAL_TIME_BETWEEN_BURSTS_MS =
+            (int) MdnsConfigs.initialTimeBetweenBurstsMs();
+    private static final int TIME_BETWEEN_BURSTS_MS = (int) MdnsConfigs.timeBetweenBurstsMs();
+    private static final int QUERIES_PER_BURST = (int) MdnsConfigs.queriesPerBurst();
+    private static final int TIME_BETWEEN_QUERIES_IN_BURST_MS =
+            (int) MdnsConfigs.timeBetweenQueriesInBurstMs();
+    private static final int QUERIES_PER_BURST_PASSIVE_MODE =
+            (int) MdnsConfigs.queriesPerBurstPassive();
+    private static final int UNSIGNED_SHORT_MAX_VALUE = 65536;
+    // The following fields are used by QueryTask so we need to test them.
+    @VisibleForTesting
+    final List<String> subtypes;
+    private final boolean alwaysAskForUnicastResponse =
+            MdnsConfigs.alwaysAskForUnicastResponseInEachBurst();
+    private final boolean usePassiveMode;
+    final boolean onlyUseIpv6OnIpv6OnlyNetworks;
+    private final int numOfQueriesBeforeBackoff;
+    @VisibleForTesting
+    final int transactionId;
+    @VisibleForTesting
+    final boolean expectUnicastResponse;
+    private final int queriesPerBurst;
+    private final int timeBetweenBurstsInMs;
+    private final int burstCounter;
+    final long delayUntilNextTaskWithoutBackoffMs;
+    private final boolean isFirstBurst;
+    private final long queryCount;
+    @NonNull
+    final SocketKey socketKey;
+
+    QueryTaskConfig(@NonNull QueryTaskConfig other, long queryCount, int transactionId,
+            boolean expectUnicastResponse, boolean isFirstBurst, int burstCounter,
+            int queriesPerBurst, int timeBetweenBurstsInMs,
+            long delayUntilNextTaskWithoutBackoffMs) {
+        this.subtypes = new ArrayList<>(other.subtypes);
+        this.usePassiveMode = other.usePassiveMode;
+        this.onlyUseIpv6OnIpv6OnlyNetworks = other.onlyUseIpv6OnIpv6OnlyNetworks;
+        this.numOfQueriesBeforeBackoff = other.numOfQueriesBeforeBackoff;
+        this.transactionId = transactionId;
+        this.expectUnicastResponse = expectUnicastResponse;
+        this.queriesPerBurst = queriesPerBurst;
+        this.timeBetweenBurstsInMs = timeBetweenBurstsInMs;
+        this.burstCounter = burstCounter;
+        this.delayUntilNextTaskWithoutBackoffMs = delayUntilNextTaskWithoutBackoffMs;
+        this.isFirstBurst = isFirstBurst;
+        this.queryCount = queryCount;
+        this.socketKey = other.socketKey;
+    }
+    QueryTaskConfig(@NonNull Collection<String> subtypes,
+            boolean usePassiveMode,
+            boolean onlyUseIpv6OnIpv6OnlyNetworks,
+            int numOfQueriesBeforeBackoff,
+            @Nullable SocketKey socketKey) {
+        this.usePassiveMode = usePassiveMode;
+        this.onlyUseIpv6OnIpv6OnlyNetworks = onlyUseIpv6OnIpv6OnlyNetworks;
+        this.numOfQueriesBeforeBackoff = numOfQueriesBeforeBackoff;
+        this.subtypes = new ArrayList<>(subtypes);
+        this.queriesPerBurst = QUERIES_PER_BURST;
+        this.burstCounter = 0;
+        this.transactionId = 1;
+        this.expectUnicastResponse = true;
+        this.isFirstBurst = true;
+        // Config the scan frequency based on the scan mode.
+        if (this.usePassiveMode) {
+            // In passive scan mode, sends a single burst of QUERIES_PER_BURST queries, and then
+            // in each TIME_BETWEEN_BURSTS interval, sends QUERIES_PER_BURST_PASSIVE_MODE
+            // queries.
+            this.timeBetweenBurstsInMs = TIME_BETWEEN_BURSTS_MS;
+        } else {
+            // In active scan mode, sends a burst of QUERIES_PER_BURST queries,
+            // TIME_BETWEEN_QUERIES_IN_BURST_MS apart, then waits for the scan interval, and
+            // then repeats. The scan interval starts as INITIAL_TIME_BETWEEN_BURSTS_MS and
+            // doubles until it maxes out at TIME_BETWEEN_BURSTS_MS.
+            this.timeBetweenBurstsInMs = INITIAL_TIME_BETWEEN_BURSTS_MS;
+        }
+        this.socketKey = socketKey;
+        this.queryCount = 0;
+        this.delayUntilNextTaskWithoutBackoffMs = TIME_BETWEEN_QUERIES_IN_BURST_MS;
+    }
+
+    /**
+     * Get new QueryTaskConfig for next run.
+     */
+    public QueryTaskConfig getConfigForNextRun() {
+        long newQueryCount = queryCount + 1;
+        int newTransactionId = transactionId + 1;
+        if (newTransactionId > UNSIGNED_SHORT_MAX_VALUE) {
+            newTransactionId = 1;
+        }
+        boolean newExpectUnicastResponse = false;
+        boolean newIsFirstBurst = isFirstBurst;
+        int newQueriesPerBurst = queriesPerBurst;
+        int newBurstCounter = burstCounter + 1;
+        long newDelayUntilNextTaskWithoutBackoffMs = delayUntilNextTaskWithoutBackoffMs;
+        int newTimeBetweenBurstsInMs = timeBetweenBurstsInMs;
+        // Only the first query expects uni-cast response.
+        if (newBurstCounter == queriesPerBurst) {
+            newBurstCounter = 0;
+
+            if (alwaysAskForUnicastResponse) {
+                newExpectUnicastResponse = true;
+            }
+            // In passive scan mode, sends a single burst of QUERIES_PER_BURST queries, and
+            // then in each TIME_BETWEEN_BURSTS interval, sends QUERIES_PER_BURST_PASSIVE_MODE
+            // queries.
+            if (isFirstBurst) {
+                newIsFirstBurst = false;
+                if (usePassiveMode) {
+                    newQueriesPerBurst = QUERIES_PER_BURST_PASSIVE_MODE;
+                }
+            }
+            // In active scan mode, sends a burst of QUERIES_PER_BURST queries,
+            // TIME_BETWEEN_QUERIES_IN_BURST_MS apart, then waits for the scan interval, and
+            // then repeats. The scan interval starts as INITIAL_TIME_BETWEEN_BURSTS_MS and
+            // doubles until it maxes out at TIME_BETWEEN_BURSTS_MS.
+            newDelayUntilNextTaskWithoutBackoffMs = timeBetweenBurstsInMs;
+            if (timeBetweenBurstsInMs < TIME_BETWEEN_BURSTS_MS) {
+                newTimeBetweenBurstsInMs = Math.min(timeBetweenBurstsInMs * 2,
+                        TIME_BETWEEN_BURSTS_MS);
+            }
+        } else {
+            newDelayUntilNextTaskWithoutBackoffMs = TIME_BETWEEN_QUERIES_IN_BURST_MS;
+        }
+        return new QueryTaskConfig(this, newQueryCount, newTransactionId,
+                newExpectUnicastResponse, newIsFirstBurst, newBurstCounter, newQueriesPerBurst,
+                newTimeBetweenBurstsInMs, newDelayUntilNextTaskWithoutBackoffMs);
+    }
+
+    /**
+     * Determine if the query backoff should be used.
+     */
+    public boolean shouldUseQueryBackoff() {
+        // Don't enable backoff mode during the burst or in the first burst
+        if (burstCounter != 0 || isFirstBurst) {
+            return false;
+        }
+        return queryCount > numOfQueriesBeforeBackoff;
+    }
+}
diff --git a/service-t/src/com/android/server/connectivity/mdns/util/MdnsUtils.java b/service-t/src/com/android/server/connectivity/mdns/util/MdnsUtils.java
index 3180a6f..df3bde8 100644
--- a/service-t/src/com/android/server/connectivity/mdns/util/MdnsUtils.java
+++ b/service-t/src/com/android/server/connectivity/mdns/util/MdnsUtils.java
@@ -20,6 +20,7 @@
 import android.annotation.Nullable;
 import android.net.Network;
 import android.os.Handler;
+import android.os.SystemClock;
 import android.util.ArraySet;
 
 import com.android.server.connectivity.mdns.MdnsConstants;
@@ -173,4 +174,14 @@
         return mdnsRecord.getTtl() > 0
                 && mdnsRecord.getRemainingTTL(now) <= mdnsRecord.getTtl() / 2;
     }
+
+    /** A wrapper class of {@link SystemClock} to be mocked in unit tests. */
+    public static class Clock {
+        /**
+         * @see SystemClock#elapsedRealtime
+         */
+        public long elapsedRealtime() {
+            return SystemClock.elapsedRealtime();
+        }
+    }
 }
\ No newline at end of file
diff --git a/service-t/src/com/android/server/ethernet/EthernetTracker.java b/service-t/src/com/android/server/ethernet/EthernetTracker.java
index 1f22b02..8141350 100644
--- a/service-t/src/com/android/server/ethernet/EthernetTracker.java
+++ b/service-t/src/com/android/server/ethernet/EthernetTracker.java
@@ -431,7 +431,7 @@
             for (String iface : getClientModeInterfaces(canUseRestrictedNetworks)) {
                 unicastInterfaceStateChange(listener, iface);
             }
-            if (mTetheringInterfaceMode == INTERFACE_MODE_SERVER) {
+            if (mTetheringInterface != null && mTetheringInterfaceMode == INTERFACE_MODE_SERVER) {
                 unicastInterfaceStateChange(listener, mTetheringInterface);
             }
 
diff --git a/service/src/com/android/server/BpfNetMaps.java b/service/src/com/android/server/BpfNetMaps.java
index ec168dd..7aff6a4 100644
--- a/service/src/com/android/server/BpfNetMaps.java
+++ b/service/src/com/android/server/BpfNetMaps.java
@@ -40,6 +40,7 @@
 import android.app.StatsManager;
 import android.content.Context;
 import android.net.INetd;
+import android.os.Build;
 import android.os.RemoteException;
 import android.os.ServiceSpecificException;
 import android.provider.DeviceConfig;
@@ -51,6 +52,8 @@
 import android.util.Pair;
 import android.util.StatsEvent;
 
+import androidx.annotation.RequiresApi;
+
 import com.android.internal.annotations.VisibleForTesting;
 import com.android.modules.utils.BackgroundThread;
 import com.android.modules.utils.build.SdkLevel;
@@ -1140,19 +1143,48 @@
         }
     }
 
+    @RequiresApi(Build.VERSION_CODES.UPSIDE_DOWN_CAKE)
     private static native void native_init(boolean startSkDestroyListener);
+
+    @RequiresApi(Build.VERSION_CODES.TIRAMISU)
     private native int native_addNaughtyApp(int uid);
+
+    @RequiresApi(Build.VERSION_CODES.TIRAMISU)
     private native int native_removeNaughtyApp(int uid);
+
+    @RequiresApi(Build.VERSION_CODES.TIRAMISU)
     private native int native_addNiceApp(int uid);
+
+    @RequiresApi(Build.VERSION_CODES.TIRAMISU)
     private native int native_removeNiceApp(int uid);
+
+    @RequiresApi(Build.VERSION_CODES.TIRAMISU)
     private native int native_setChildChain(int childChain, boolean enable);
+
+    @RequiresApi(Build.VERSION_CODES.TIRAMISU)
     private native int native_replaceUidChain(String name, boolean isAllowlist, int[] uids);
+
+    @RequiresApi(Build.VERSION_CODES.TIRAMISU)
     private native int native_setUidRule(int childChain, int uid, int firewallRule);
+
+    @RequiresApi(Build.VERSION_CODES.TIRAMISU)
     private native int native_addUidInterfaceRules(String ifName, int[] uids);
+
+    @RequiresApi(Build.VERSION_CODES.TIRAMISU)
     private native int native_removeUidInterfaceRules(int[] uids);
+
+    @RequiresApi(Build.VERSION_CODES.TIRAMISU)
     private native int native_updateUidLockdownRule(int uid, boolean add);
+
+    @RequiresApi(Build.VERSION_CODES.TIRAMISU)
     private native int native_swapActiveStatsMap();
+
+    @RequiresApi(Build.VERSION_CODES.TIRAMISU)
     private native void native_setPermissionForUids(int permissions, int[] uids);
+
+    @RequiresApi(Build.VERSION_CODES.TIRAMISU)
     private static native void native_dump(FileDescriptor fd, boolean verbose);
+
+    @RequiresApi(Build.VERSION_CODES.TIRAMISU)
     private static native int native_synchronizeKernelRCU();
 }
diff --git a/tests/benchmark/Android.bp b/tests/benchmark/Android.bp
new file mode 100644
index 0000000..77383ad
--- /dev/null
+++ b/tests/benchmark/Android.bp
@@ -0,0 +1,42 @@
+//
+// Copyright (C) 2023 The Android Open Source Project
+//
+// 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 {
+    // See: http://go/android-license-faq
+    default_applicable_licenses: ["Android-Apache-2.0"],
+}
+
+android_test {
+    name: "ConnectivityBenchmarkTests",
+    defaults: [
+        "framework-connectivity-internal-test-defaults",
+    ],
+    platform_apis: true,
+    srcs: [
+        "src/**/*.kt",
+        "src/**/*.aidl",
+    ],
+    static_libs: [
+        "androidx.test.rules",
+        "mockito-target-minus-junit4",
+        "net-tests-utils",
+        "service-connectivity-pre-jarjar",
+        "service-connectivity-tiramisu-pre-jarjar",
+    ],
+    test_suites: ["device-tests"],
+    jarjar_rules: ":connectivity-jarjar-rules",
+}
+
diff --git a/tests/benchmark/AndroidManifest.xml b/tests/benchmark/AndroidManifest.xml
new file mode 100644
index 0000000..bd2fce5
--- /dev/null
+++ b/tests/benchmark/AndroidManifest.xml
@@ -0,0 +1,26 @@
+<?xml version="1.0" encoding="utf-8"?>
+<!-- Copyright (C) 2023 The Android Open Source Project
+
+     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.
+-->
+
+<manifest xmlns:android="http://schemas.android.com/apk/res/android"
+        package="com.android.server.connectivity.benchmarktests">
+    <application>
+        <uses-library android:name="android.test.runner" />
+    </application>
+
+    <instrumentation android:name="androidx.test.runner.AndroidJUnitRunner"
+         android:targetPackage="com.android.server.connectivity.benchmarktests"
+         android:label="Connectivity Benchmark Tests" />
+</manifest>
diff --git a/tests/benchmark/OWNERS b/tests/benchmark/OWNERS
new file mode 100644
index 0000000..3101da5
--- /dev/null
+++ b/tests/benchmark/OWNERS
@@ -0,0 +1,2 @@
+# Bug template url: http://b/new?component=31808
+# TODO: move bug template config to common owners file once b/226427845 is resolved
\ No newline at end of file
diff --git a/tests/benchmark/res/raw/netstats-many-uids-zip b/tests/benchmark/res/raw/netstats-many-uids-zip
new file mode 100644
index 0000000..22e8254
--- /dev/null
+++ b/tests/benchmark/res/raw/netstats-many-uids-zip
Binary files differ
diff --git a/tests/benchmark/src/android/net/netstats/benchmarktests/NetworkStatsTest.kt b/tests/benchmark/src/android/net/netstats/benchmarktests/NetworkStatsTest.kt
new file mode 100644
index 0000000..8492268
--- /dev/null
+++ b/tests/benchmark/src/android/net/netstats/benchmarktests/NetworkStatsTest.kt
@@ -0,0 +1,142 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * 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 com.android.server.net.benchmarktests
+
+import android.net.NetworkStats.NonMonotonicObserver
+import android.net.NetworkStatsCollection
+import android.net.netstats.NetworkStatsDataMigrationUtils.PREFIX_UID
+import android.os.DropBoxManager
+import androidx.test.InstrumentationRegistry
+import com.android.internal.util.FileRotator
+import com.android.internal.util.FileRotator.Reader
+import com.android.server.connectivity.benchmarktests.R
+import com.android.server.net.NetworkStatsRecorder
+import java.io.BufferedInputStream
+import java.io.DataInputStream
+import java.io.File
+import java.io.FileInputStream
+import java.io.FileOutputStream
+import java.nio.file.Files
+import java.util.concurrent.TimeUnit
+import java.util.zip.ZipInputStream
+import kotlin.test.assertTrue
+import org.junit.BeforeClass
+import org.junit.Test
+import org.junit.runner.RunWith
+import org.junit.runners.JUnit4
+import org.mockito.Mockito.mock
+
+@RunWith(JUnit4::class)
+class NetworkStatsTest {
+    companion object {
+        private val DEFAULT_BUFFER_SIZE = 8192
+        private val UID_COLLECTION_BUCKET_DURATION_MS = TimeUnit.HOURS.toMillis(2)
+        private val UID_RECORDER_ROTATE_AGE_MS = TimeUnit.DAYS.toMillis(15)
+        private val UID_RECORDER_DELETE_AGE_MS = TimeUnit.DAYS.toMillis(90)
+
+        private val testFilesDir by lazy {
+            // These file generated by using real user dataset which has many uid records
+            // and agreed to share the dataset for testing purpose. These dataset can be
+            // extracted from rooted devices by using
+            // "adb pull /data/misc/apexdata/com.android.tethering/netstats" command.
+            val zipInputStream =
+                ZipInputStream(getInputStreamForResource(R.raw.netstats_many_uids_zip))
+            unzipToTempDir(zipInputStream)
+        }
+
+        private val uidTestFiles: List<File> by lazy {
+            getSortedListForPrefix(testFilesDir, "uid")
+        }
+
+        // Test results shows the test cases who read the file first will take longer time to
+        // execute, and reading time getting shorter each time. Read files several times prior to
+        // tests to minimize the impact. This cannot live in setUp() since the time
+        // spent on the file reading will be attributed to the time spent on the individual
+        // test case.
+        @JvmStatic
+        @BeforeClass
+        fun setUpOnce() {
+            for (i in 1..10) {
+                val collection = NetworkStatsCollection(UID_COLLECTION_BUCKET_DURATION_MS)
+                for (file in uidTestFiles) {
+                    readFile(file, collection)
+                }
+            }
+        }
+
+        private fun getInputStreamForResource(resourceId: Int): DataInputStream {
+            return DataInputStream(
+                InstrumentationRegistry.getContext()
+                    .getResources().openRawResource(resourceId)
+            )
+        }
+
+        private fun unzipToTempDir(zis: ZipInputStream): File {
+            val statsDir =
+                Files.createTempDirectory(NetworkStatsTest::class.simpleName).toFile()
+            while (true) {
+                val entryName = zis.nextEntry?.name ?: break
+                val file = File(statsDir, entryName)
+                FileOutputStream(file).use { zis.copyTo(it, DEFAULT_BUFFER_SIZE) }
+            }
+            return statsDir
+        }
+
+        // List [xt|uid|uid_tag].<start>-<end> files under the given directory.
+        private fun getSortedListForPrefix(statsDir: File, prefix: String): List<File> {
+            assertTrue(statsDir.exists())
+            return (statsDir.list() ?: arrayOf()).mapNotNull {
+                if (it.startsWith("$prefix.")) File(statsDir, it) else null
+            }.sorted()
+        }
+
+        private fun readFile(file: File, reader: Reader) =
+            BufferedInputStream(FileInputStream(file)).use {
+                reader.read(it)
+            }
+    }
+
+    @Test
+    fun testReadCollection_manyUids() {
+        for (i in 1..10) {
+            val collection = NetworkStatsCollection(UID_COLLECTION_BUCKET_DURATION_MS)
+            for (file in uidTestFiles) {
+                readFile(file, collection)
+            }
+        }
+    }
+
+    @Test
+    fun testReadFromRecorder_manyUids() {
+        for (i in 1..10) {
+            val recorder = NetworkStatsRecorder(
+                FileRotator(
+                    testFilesDir, PREFIX_UID, UID_RECORDER_ROTATE_AGE_MS, UID_RECORDER_DELETE_AGE_MS
+                ),
+                mock<NonMonotonicObserver<String>>(),
+                mock(DropBoxManager::class.java),
+                PREFIX_UID,
+                UID_COLLECTION_BUCKET_DURATION_MS,
+                false /* includeTags */,
+                false /* wipeOnError */
+            )
+            recorder.orLoadCompleteLocked
+        }
+    }
+
+    inline fun <reified T : Any> mock(): T = mock(T::class.java)
+}
diff --git a/tests/common/java/android/net/NattKeepalivePacketDataTest.kt b/tests/common/java/android/net/NattKeepalivePacketDataTest.kt
index dde1d86..e5806a6 100644
--- a/tests/common/java/android/net/NattKeepalivePacketDataTest.kt
+++ b/tests/common/java/android/net/NattKeepalivePacketDataTest.kt
@@ -28,6 +28,7 @@
 import com.android.testutils.assertEqualBothWays
 import com.android.testutils.assertParcelingIsLossless
 import com.android.testutils.parcelingRoundTrip
+import java.net.Inet6Address
 import java.net.InetAddress
 import kotlin.test.assertFailsWith
 import org.junit.Assert.assertEquals
@@ -44,10 +45,33 @@
 
     private val TEST_PORT = 4243
     private val TEST_PORT2 = 4244
+    // ::FFFF:1.2.3.4
+    private val SRC_V4_MAPPED_V6_ADDRESS_BYTES = byteArrayOf(
+        0x00.toByte(),
+        0x00.toByte(),
+        0x00.toByte(),
+        0x00.toByte(),
+        0x00.toByte(),
+        0x00.toByte(),
+        0x00.toByte(),
+        0x00.toByte(),
+        0x00.toByte(),
+        0x00.toByte(),
+        0xff.toByte(),
+        0xff.toByte(),
+        0x01.toByte(),
+        0x02.toByte(),
+        0x03.toByte(),
+        0x04.toByte()
+    )
     private val TEST_SRC_ADDRV4 = "198.168.0.2".address()
     private val TEST_DST_ADDRV4 = "198.168.0.1".address()
     private val TEST_ADDRV6 = "2001:db8::1".address()
-    private val TEST_ADDRV4MAPPEDV6 = "::ffff:1.2.3.4".address()
+    // This constant requires to be an Inet6Address, but InetAddresses.parseNumericAddress() will
+    // convert v4 mapped v6 address into an Inet4Address. So use Inet6Address.getByAddress() to
+    // create the address.
+    private val TEST_ADDRV4MAPPEDV6 = Inet6Address.getByAddress(null /* host */,
+        SRC_V4_MAPPED_V6_ADDRESS_BYTES, -1 /* scope_id */)
     private val TEST_ADDRV4 = "1.2.3.4".address()
 
     private fun String.address() = InetAddresses.parseNumericAddress(this)
diff --git a/tests/cts/OWNERS b/tests/cts/OWNERS
index 8c2408b..286f9c8 100644
--- a/tests/cts/OWNERS
+++ b/tests/cts/OWNERS
@@ -1,7 +1,7 @@
 # Bug template url: http://b/new?component=31808
 # TODO: move bug template config to common owners file once b/226427845 is resolved
 set noparent
-file:platform/packages/modules/Connectivity:master:/OWNERS_core_networking_xts
+file:platform/packages/modules/Connectivity:main:/OWNERS_core_networking_xts
 
 # IPsec
 per-file **IpSec* = benedictwong@google.com, nharold@google.com
diff --git a/tests/cts/hostside/app/src/com/android/cts/net/hostside/AbstractExpeditedJobTest.java b/tests/cts/hostside/app/src/com/android/cts/net/hostside/AbstractExpeditedJobTest.java
index a850e3b..7cac2af 100644
--- a/tests/cts/hostside/app/src/com/android/cts/net/hostside/AbstractExpeditedJobTest.java
+++ b/tests/cts/hostside/app/src/com/android/cts/net/hostside/AbstractExpeditedJobTest.java
@@ -74,6 +74,7 @@
     @RequiredProperties({APP_STANDBY_MODE})
     public void testNetworkAccess_appIdleState() throws Exception {
         turnBatteryOn();
+        setAppIdle(false);
         assertBackgroundNetworkAccess(true);
         assertExpeditedJobHasNetworkAccess();
 
diff --git a/tests/cts/hostside/app/src/com/android/cts/net/hostside/DumpOnFailureRule.java b/tests/cts/hostside/app/src/com/android/cts/net/hostside/DumpOnFailureRule.java
index 78ae7b8..07434b1 100644
--- a/tests/cts/hostside/app/src/com/android/cts/net/hostside/DumpOnFailureRule.java
+++ b/tests/cts/hostside/app/src/com/android/cts/net/hostside/DumpOnFailureRule.java
@@ -64,6 +64,8 @@
                     "dumpsys usagestats appstandby",
                     "dumpsys connectivity trafficcontroller",
                     "dumpsys netd trafficcontroller",
+                    "dumpsys platform_compat", // TODO (b/279829773): Remove this dump
+                    "dumpsys jobscheduler " + TEST_APP2_PKG, // TODO (b/288220398): Remove this dump
             }) {
                 dumpCommandOutput(out, cmd);
             }
diff --git a/tests/cts/hostside/app/src/com/android/cts/net/hostside/RestrictedModeTest.java b/tests/cts/hostside/app/src/com/android/cts/net/hostside/RestrictedModeTest.java
index 4266aad..35f1f1c 100644
--- a/tests/cts/hostside/app/src/com/android/cts/net/hostside/RestrictedModeTest.java
+++ b/tests/cts/hostside/app/src/com/android/cts/net/hostside/RestrictedModeTest.java
@@ -57,14 +57,18 @@
     @Test
     public void testNetworkAccess_withBatterySaver() throws Exception {
         setBatterySaverMode(true);
-        addPowerSaveModeWhitelist(TEST_APP2_PKG);
-        assertBackgroundNetworkAccess(true);
+        try {
+            addPowerSaveModeWhitelist(TEST_APP2_PKG);
+            assertBackgroundNetworkAccess(true);
 
-        setRestrictedNetworkingMode(true);
-        // App would be denied network access since Restricted mode is on.
-        assertBackgroundNetworkAccess(false);
-        setRestrictedNetworkingMode(false);
-        // Given that Restricted mode is turned off, app should be able to access network again.
-        assertBackgroundNetworkAccess(true);
+            setRestrictedNetworkingMode(true);
+            // App would be denied network access since Restricted mode is on.
+            assertBackgroundNetworkAccess(false);
+            setRestrictedNetworkingMode(false);
+            // Given that Restricted mode is turned off, app should be able to access network again.
+            assertBackgroundNetworkAccess(true);
+        } finally {
+            setBatterySaverMode(false);
+        }
     }
 }
diff --git a/tests/cts/hostside/src/com/android/cts/net/HostsideConnOnActivityStartTest.java b/tests/cts/hostside/src/com/android/cts/net/HostsideConnOnActivityStartTest.java
index a7d5590..69eba41 100644
--- a/tests/cts/hostside/src/com/android/cts/net/HostsideConnOnActivityStartTest.java
+++ b/tests/cts/hostside/src/com/android/cts/net/HostsideConnOnActivityStartTest.java
@@ -18,25 +18,24 @@
 
 import android.platform.test.annotations.FlakyTest;
 
-import org.junit.After;
-import org.junit.Before;
+import com.android.tradefed.device.DeviceNotAvailableException;
+import com.android.tradefed.invoker.TestInformation;
+import com.android.tradefed.testtype.junit4.AfterClassWithInfo;
+import com.android.tradefed.testtype.junit4.BeforeClassWithInfo;
+
 import org.junit.Test;
 
 public class HostsideConnOnActivityStartTest extends HostsideNetworkTestCase {
     private static final String TEST_CLASS = TEST_PKG + ".ConnOnActivityStartTest";
-    @Before
-    public void setUp() throws Exception {
-        super.setUp();
-
-        uninstallPackage(TEST_APP2_PKG, false);
-        installPackage(TEST_APP2_APK);
+    @BeforeClassWithInfo
+    public static void setUpOnce(TestInformation testInfo) throws Exception {
+        uninstallPackage(testInfo, TEST_APP2_PKG, false);
+        installPackage(testInfo, TEST_APP2_APK);
     }
 
-    @After
-    public void tearDown() throws Exception {
-        super.tearDown();
-
-        uninstallPackage(TEST_APP2_PKG, true);
+    @AfterClassWithInfo
+    public static void tearDownOnce(TestInformation testInfo) throws DeviceNotAvailableException {
+        uninstallPackage(testInfo, TEST_APP2_PKG, true);
     }
 
     @Test
diff --git a/tests/cts/hostside/src/com/android/cts/net/HostsideNetworkCallbackTests.java b/tests/cts/hostside/src/com/android/cts/net/HostsideNetworkCallbackTests.java
index 5d7ad62..d8e7a2c 100644
--- a/tests/cts/hostside/src/com/android/cts/net/HostsideNetworkCallbackTests.java
+++ b/tests/cts/hostside/src/com/android/cts/net/HostsideNetworkCallbackTests.java
@@ -23,14 +23,12 @@
 
     @Before
     public void setUp() throws Exception {
-        super.setUp();
         uninstallPackage(TEST_APP2_PKG, false);
         installPackage(TEST_APP2_APK);
     }
 
     @After
     public void tearDown() throws Exception {
-        super.tearDown();
         uninstallPackage(TEST_APP2_PKG, true);
     }
 
diff --git a/tests/cts/hostside/src/com/android/cts/net/HostsideNetworkPolicyManagerTests.java b/tests/cts/hostside/src/com/android/cts/net/HostsideNetworkPolicyManagerTests.java
index 40f5f59..3ddb88b 100644
--- a/tests/cts/hostside/src/com/android/cts/net/HostsideNetworkPolicyManagerTests.java
+++ b/tests/cts/hostside/src/com/android/cts/net/HostsideNetworkPolicyManagerTests.java
@@ -23,14 +23,12 @@
 public class HostsideNetworkPolicyManagerTests extends HostsideNetworkTestCase {
     @Before
     public void setUp() throws Exception {
-        super.setUp();
         uninstallPackage(TEST_APP2_PKG, false);
         installPackage(TEST_APP2_APK);
     }
 
     @After
     public void tearDown() throws Exception {
-        super.tearDown();
         uninstallPackage(TEST_APP2_PKG, true);
     }
 
diff --git a/tests/cts/hostside/src/com/android/cts/net/HostsideNetworkTestCase.java b/tests/cts/hostside/src/com/android/cts/net/HostsideNetworkTestCase.java
index c896168..b89ab1f 100644
--- a/tests/cts/hostside/src/com/android/cts/net/HostsideNetworkTestCase.java
+++ b/tests/cts/hostside/src/com/android/cts/net/HostsideNetworkTestCase.java
@@ -16,16 +16,21 @@
 
 package com.android.cts.net;
 
+import static org.junit.Assert.assertNotNull;
 import static org.junit.Assert.assertNull;
 import static org.junit.Assert.fail;
 
 import com.android.ddmlib.Log;
 import com.android.modules.utils.build.testing.DeviceSdkLevel;
 import com.android.tradefed.device.DeviceNotAvailableException;
+import com.android.tradefed.invoker.TestInformation;
+import com.android.tradefed.targetprep.BuildError;
 import com.android.tradefed.targetprep.TargetSetupError;
+import com.android.tradefed.targetprep.suite.SuiteApkInstaller;
 import com.android.tradefed.testtype.DeviceJUnit4ClassRunner;
+import com.android.tradefed.testtype.junit4.AfterClassWithInfo;
 import com.android.tradefed.testtype.junit4.BaseHostJUnit4Test;
-import com.android.tradefed.testtype.junit4.DeviceTestRunOptions;
+import com.android.tradefed.testtype.junit4.BeforeClassWithInfo;
 import com.android.tradefed.util.RunUtil;
 
 import org.junit.runner.RunWith;
@@ -40,34 +45,62 @@
     protected static final String TEST_APP2_PKG = "com.android.cts.net.hostside.app2";
     protected static final String TEST_APP2_APK = "CtsHostsideNetworkTestsApp2.apk";
 
-    protected void setUp() throws Exception {
-        DeviceSdkLevel deviceSdkLevel = new DeviceSdkLevel(getDevice());
-        String testApk = deviceSdkLevel.isDeviceAtLeastT() ? TEST_APK_NEXT
-                : TEST_APK;
+    @BeforeClassWithInfo
+    public static void setUpOnceBase(TestInformation testInfo) throws Exception {
+        DeviceSdkLevel deviceSdkLevel = new DeviceSdkLevel(testInfo.getDevice());
+        String testApk = deviceSdkLevel.isDeviceAtLeastT() ? TEST_APK_NEXT : TEST_APK;
 
-        uninstallPackage(TEST_PKG, false);
-        installPackage(testApk);
+        uninstallPackage(testInfo, TEST_PKG, false);
+        installPackage(testInfo, testApk);
     }
 
-    protected void tearDown() throws Exception {
-        uninstallPackage(TEST_PKG, true);
+    @AfterClassWithInfo
+    public static void tearDownOnceBase(TestInformation testInfo)
+            throws DeviceNotAvailableException {
+        uninstallPackage(testInfo, TEST_PKG, true);
+    }
+
+    // Custom static method to install the specified package, this is used to bypass auto-cleanup
+    // per test in BaseHostJUnit4.
+    protected static void installPackage(TestInformation testInfo, String apk)
+            throws DeviceNotAvailableException, TargetSetupError {
+        assertNotNull(testInfo);
+        final int userId = testInfo.getDevice().getCurrentUser();
+        final SuiteApkInstaller installer = new SuiteApkInstaller();
+        // Force the apk clean up
+        installer.setCleanApk(true);
+        installer.addTestFileName(apk);
+        installer.setUserId(userId);
+        installer.setShouldGrantPermission(true);
+        installer.addInstallArg("-t");
+        try {
+            installer.setUp(testInfo);
+        } catch (BuildError e) {
+            throw new TargetSetupError(
+                    e.getMessage(), e, testInfo.getDevice().getDeviceDescriptor(), e.getErrorId());
+        }
     }
 
     protected void installPackage(String apk) throws DeviceNotAvailableException, TargetSetupError {
-        final DeviceTestRunOptions installOptions = new DeviceTestRunOptions(
-                null /* packageName */);
-        final int userId = getDevice().getCurrentUser();
-        installPackageAsUser(apk, true /* grantPermission */, userId, "-t");
+        installPackage(getTestInformation(), apk);
     }
 
-    protected void uninstallPackage(String packageName, boolean shouldSucceed)
+    protected static void uninstallPackage(TestInformation testInfo, String packageName,
+            boolean shouldSucceed)
             throws DeviceNotAvailableException {
-        final String result = uninstallPackage(packageName);
+        assertNotNull(testInfo);
+        final String result = testInfo.getDevice().uninstallPackage(packageName);
         if (shouldSucceed) {
             assertNull("uninstallPackage(" + packageName + ") failed: " + result, result);
         }
     }
 
+    protected void uninstallPackage(String packageName,
+            boolean shouldSucceed)
+            throws DeviceNotAvailableException {
+        uninstallPackage(getTestInformation(), packageName, shouldSucceed);
+    }
+
     protected void assertPackageUninstalled(String packageName) throws DeviceNotAvailableException,
             InterruptedException {
         final String command = "cmd package list packages " + packageName;
diff --git a/tests/cts/hostside/src/com/android/cts/net/HostsideRestrictBackgroundNetworkTests.java b/tests/cts/hostside/src/com/android/cts/net/HostsideRestrictBackgroundNetworkTests.java
index 0977deb..57b26bd 100644
--- a/tests/cts/hostside/src/com/android/cts/net/HostsideRestrictBackgroundNetworkTests.java
+++ b/tests/cts/hostside/src/com/android/cts/net/HostsideRestrictBackgroundNetworkTests.java
@@ -32,16 +32,12 @@
 
     @Before
     public void setUp() throws Exception {
-        super.setUp();
-
         uninstallPackage(TEST_APP2_PKG, false);
         installPackage(TEST_APP2_APK);
     }
 
     @After
     public void tearDown() throws Exception {
-        super.tearDown();
-
         uninstallPackage(TEST_APP2_PKG, true);
     }
 
diff --git a/tests/cts/hostside/src/com/android/cts/net/HostsideVpnTests.java b/tests/cts/hostside/src/com/android/cts/net/HostsideVpnTests.java
index 242fd5d..691ac90 100644
--- a/tests/cts/hostside/src/com/android/cts/net/HostsideVpnTests.java
+++ b/tests/cts/hostside/src/com/android/cts/net/HostsideVpnTests.java
@@ -26,16 +26,12 @@
 
     @Before
     public void setUp() throws Exception {
-        super.setUp();
-
         uninstallPackage(TEST_APP2_PKG, false);
         installPackage(TEST_APP2_APK);
     }
 
     @After
     public void tearDown() throws Exception {
-        super.tearDown();
-
         uninstallPackage(TEST_APP2_PKG, true);
     }
 
diff --git a/tests/cts/net/src/android/net/cts/DnsResolverTest.java b/tests/cts/net/src/android/net/cts/DnsResolverTest.java
index 3821cea..308aead 100644
--- a/tests/cts/net/src/android/net/cts/DnsResolverTest.java
+++ b/tests/cts/net/src/android/net/cts/DnsResolverTest.java
@@ -59,6 +59,7 @@
 import com.android.net.module.util.DnsPacket;
 import com.android.testutils.DevSdkIgnoreRule;
 import com.android.testutils.DevSdkIgnoreRule.IgnoreUpTo;
+import com.android.testutils.DnsResolverModuleTest;
 import com.android.testutils.SkipPresubmit;
 
 import org.junit.After;
@@ -317,51 +318,61 @@
     }
 
     @Test
+    @DnsResolverModuleTest
     public void testRawQuery() throws Exception {
         doTestRawQuery(mExecutor);
     }
 
     @Test
+    @DnsResolverModuleTest
     public void testRawQueryInline() throws Exception {
         doTestRawQuery(mExecutorInline);
     }
 
     @Test
+    @DnsResolverModuleTest
     public void testRawQueryBlob() throws Exception {
         doTestRawQueryBlob(mExecutor);
     }
 
     @Test
+    @DnsResolverModuleTest
     public void testRawQueryBlobInline() throws Exception {
         doTestRawQueryBlob(mExecutorInline);
     }
 
     @Test
+    @DnsResolverModuleTest
     public void testRawQueryRoot() throws Exception {
         doTestRawQueryRoot(mExecutor);
     }
 
     @Test
+    @DnsResolverModuleTest
     public void testRawQueryRootInline() throws Exception {
         doTestRawQueryRoot(mExecutorInline);
     }
 
     @Test
+    @DnsResolverModuleTest
     public void testRawQueryNXDomain() throws Exception {
         doTestRawQueryNXDomain(mExecutor);
     }
 
     @Test
+    @DnsResolverModuleTest
     public void testRawQueryNXDomainInline() throws Exception {
         doTestRawQueryNXDomain(mExecutorInline);
     }
 
     @Test
+    @DnsResolverModuleTest
     public void testRawQueryNXDomainWithPrivateDns() throws Exception {
         doTestRawQueryNXDomainWithPrivateDns(mExecutor);
     }
 
     @Test
+    @DnsResolverModuleTest
     public void testRawQueryNXDomainInlineWithPrivateDns() throws Exception {
         doTestRawQueryNXDomainWithPrivateDns(mExecutorInline);
     }
@@ -610,41 +621,49 @@
     }
 
     @Test
+    @DnsResolverModuleTest
     public void testQueryForInetAddress() throws Exception {
         doTestQueryForInetAddress(mExecutor);
     }
 
     @Test
+    @DnsResolverModuleTest
     public void testQueryForInetAddressInline() throws Exception {
         doTestQueryForInetAddress(mExecutorInline);
     }
 
     @Test
+    @DnsResolverModuleTest
     public void testQueryForInetAddressIpv4() throws Exception {
         doTestQueryForInetAddressIpv4(mExecutor);
     }
 
     @Test
+    @DnsResolverModuleTest
     public void testQueryForInetAddressIpv4Inline() throws Exception {
         doTestQueryForInetAddressIpv4(mExecutorInline);
     }
 
     @Test
+    @DnsResolverModuleTest
     public void testQueryForInetAddressIpv6() throws Exception {
         doTestQueryForInetAddressIpv6(mExecutor);
     }
 
     @Test
+    @DnsResolverModuleTest
     public void testQueryForInetAddressIpv6Inline() throws Exception {
         doTestQueryForInetAddressIpv6(mExecutorInline);
     }
 
     @Test
+    @DnsResolverModuleTest
     public void testContinuousQueries() throws Exception {
         doTestContinuousQueries(mExecutor);
     }
 
     @Test
+    @DnsResolverModuleTest
     @SkipPresubmit(reason = "Flaky: b/159762682; add to presubmit after fixing")
     public void testContinuousQueriesInline() throws Exception {
         doTestContinuousQueries(mExecutorInline);
diff --git a/tests/cts/net/src/android/net/cts/NetworkStatsManagerTest.java b/tests/cts/net/src/android/net/cts/NetworkStatsManagerTest.java
index 83b9b81..7bccbde 100644
--- a/tests/cts/net/src/android/net/cts/NetworkStatsManagerTest.java
+++ b/tests/cts/net/src/android/net/cts/NetworkStatsManagerTest.java
@@ -82,9 +82,9 @@
 import org.junit.Test;
 import org.junit.runner.RunWith;
 
+import java.io.BufferedInputStream;
 import java.io.IOException;
 import java.io.InputStream;
-import java.io.InputStreamReader;
 import java.net.HttpURLConnection;
 import java.net.URL;
 import java.net.UnknownHostException;
@@ -220,7 +220,7 @@
         } else {
             Log.w(LOG_TAG, "Network: " + networkInfo.toString());
         }
-        InputStreamReader in = null;
+        BufferedInputStream in = null;
         HttpURLConnection urlc = null;
         String originalKeepAlive = System.getProperty("http.keepAlive");
         System.setProperty("http.keepAlive", "false");
@@ -236,10 +236,10 @@
             urlc.connect();
             boolean ping = urlc.getResponseCode() == 200;
             if (ping) {
-                in = new InputStreamReader((InputStream) urlc.getContent());
-                // Since the test doesn't really care about the precise amount of data, instead
-                // of reading all contents, just read few bytes at the beginning.
-                in.read();
+                in = new BufferedInputStream((InputStream) urlc.getContent());
+                while (in.read() != -1) {
+                    // Comments to suppress lint error.
+                }
             }
         } catch (Exception e) {
             Log.i(LOG_TAG, "Badness during exercising remote server: " + e);
@@ -377,9 +377,14 @@
                 .addCapability(NetworkCapabilities.NET_CAPABILITY_INTERNET)
                 .build(), callback);
         synchronized (this) {
-            try {
-                wait((int) (TIMEOUT_MILLIS * 2.4));
-            } catch (InterruptedException e) {
+            long now = System.currentTimeMillis();
+            final long deadline = (long) (now + TIMEOUT_MILLIS * 2.4);
+            while (!callback.success && now < deadline) {
+                try {
+                    wait(deadline - now);
+                } catch (InterruptedException e) {
+                }
+                now = System.currentTimeMillis();
             }
         }
         if (callback.success) {
diff --git a/tests/cts/net/src/android/net/cts/NsdManagerTest.kt b/tests/cts/net/src/android/net/cts/NsdManagerTest.kt
index 6c411cf..49620b0 100644
--- a/tests/cts/net/src/android/net/cts/NsdManagerTest.kt
+++ b/tests/cts/net/src/android/net/cts/NsdManagerTest.kt
@@ -80,8 +80,6 @@
 import com.android.modules.utils.build.SdkLevel.isAtLeastU
 import com.android.net.module.util.ArrayTrackRecord
 import com.android.net.module.util.TrackRecord
-import com.android.networkstack.apishim.NsdShimImpl
-import com.android.networkstack.apishim.common.NsdShim
 import com.android.testutils.ConnectivityModuleTest
 import com.android.testutils.DevSdkIgnoreRule
 import com.android.testutils.DevSdkIgnoreRule.IgnoreUpTo
@@ -133,8 +131,6 @@
 private const val DBG = false
 private const val TEST_PORT = 12345
 
-private val nsdShim = NsdShimImpl.newInstance()
-
 @AppModeFull(reason = "Socket cannot bind in instant app mode")
 @RunWith(DevSdkIgnoreRunner::class)
 @SmallTest
@@ -293,7 +289,7 @@
             val serviceFound = expectCallbackEventually<ServiceFound> {
                 it.serviceInfo.serviceName == serviceName &&
                         (expectedNetwork == null ||
-                                expectedNetwork == nsdShim.getNetwork(it.serviceInfo))
+                                expectedNetwork == it.serviceInfo.network)
             }.serviceInfo
             // Discovered service types have a dot at the end
             assertEquals("$serviceType.", serviceFound.serviceType)
@@ -331,7 +327,7 @@
         }
     }
 
-    private class NsdServiceInfoCallbackRecord : NsdShim.ServiceInfoCallbackShim,
+    private class NsdServiceInfoCallbackRecord : NsdManager.ServiceInfoCallback,
             NsdRecord<NsdServiceInfoCallbackRecord.ServiceInfoCallbackEvent>() {
         sealed class ServiceInfoCallbackEvent : NsdEvent {
             data class RegisterCallbackFailed(val errorCode: Int) : ServiceInfoCallbackEvent()
@@ -361,11 +357,9 @@
     fun setUp() {
         handlerThread.start()
 
-        if (TestUtils.shouldTestTApis()) {
-            runAsShell(MANAGE_TEST_NETWORKS) {
-                testNetwork1 = createTestNetwork()
-                testNetwork2 = createTestNetwork()
-            }
+        runAsShell(MANAGE_TEST_NETWORKS) {
+            testNetwork1 = createTestNetwork()
+            testNetwork2 = createTestNetwork()
         }
     }
 
@@ -450,12 +444,10 @@
 
     @After
     fun tearDown() {
-        if (TestUtils.shouldTestTApis()) {
-            runAsShell(MANAGE_TEST_NETWORKS) {
-                // Avoid throwing here if initializing failed in setUp
-                if (this::testNetwork1.isInitialized) testNetwork1.close(cm)
-                if (this::testNetwork2.isInitialized) testNetwork2.close(cm)
-            }
+        runAsShell(MANAGE_TEST_NETWORKS) {
+            // Avoid throwing here if initializing failed in setUp
+            if (this::testNetwork1.isInitialized) testNetwork1.close(cm)
+            if (this::testNetwork2.isInitialized) testNetwork2.close(cm)
         }
         handlerThread.waitForIdle(TIMEOUT_MS)
         handlerThread.quitSafely()
@@ -601,9 +593,6 @@
 
     @Test
     fun testNsdManager_DiscoverOnNetwork() {
-        // This test requires shims supporting T+ APIs (discovering on specific network)
-        assumeTrue(TestUtils.shouldTestTApis())
-
         val si = NsdServiceInfo()
         si.serviceType = serviceType
         si.serviceName = this.serviceName
@@ -614,19 +603,19 @@
 
         tryTest {
             val discoveryRecord = NsdDiscoveryRecord()
-            nsdShim.discoverServices(nsdManager, serviceType, NsdManager.PROTOCOL_DNS_SD,
+            nsdManager.discoverServices(serviceType, NsdManager.PROTOCOL_DNS_SD,
                     testNetwork1.network, Executor { it.run() }, discoveryRecord)
 
             val foundInfo = discoveryRecord.waitForServiceDiscovered(
                     serviceName, serviceType, testNetwork1.network)
-            assertEquals(testNetwork1.network, nsdShim.getNetwork(foundInfo))
+            assertEquals(testNetwork1.network, foundInfo.network)
 
             // Rewind to ensure the service is not found on the other interface
             discoveryRecord.nextEvents.rewind(0)
             assertNull(discoveryRecord.nextEvents.poll(timeoutMs = 100L) {
                 it is ServiceFound &&
                         it.serviceInfo.serviceName == registeredInfo.serviceName &&
-                        nsdShim.getNetwork(it.serviceInfo) != testNetwork1.network
+                        it.serviceInfo.network != testNetwork1.network
             }, "The service should not be found on this network")
         } cleanup {
             nsdManager.unregisterService(registrationRecord)
@@ -635,9 +624,6 @@
 
     @Test
     fun testNsdManager_DiscoverWithNetworkRequest() {
-        // This test requires shims supporting T+ APIs (discovering on network request)
-        assumeTrue(TestUtils.shouldTestTApis())
-
         val si = NsdServiceInfo()
         si.serviceType = serviceType
         si.serviceName = this.serviceName
@@ -652,7 +638,7 @@
 
         tryTest {
             val specifier = TestNetworkSpecifier(testNetwork1.iface.interfaceName)
-            nsdShim.discoverServices(nsdManager, serviceType, NsdManager.PROTOCOL_DNS_SD,
+            nsdManager.discoverServices(serviceType, NsdManager.PROTOCOL_DNS_SD,
                     NetworkRequest.Builder()
                             .removeCapability(NET_CAPABILITY_TRUSTED)
                             .addTransportType(TRANSPORT_TEST)
@@ -667,27 +653,27 @@
             assertEquals(registeredInfo1.serviceName, serviceDiscovered.serviceInfo.serviceName)
             // Discovered service types have a dot at the end
             assertEquals("$serviceType.", serviceDiscovered.serviceInfo.serviceType)
-            assertEquals(testNetwork1.network, nsdShim.getNetwork(serviceDiscovered.serviceInfo))
+            assertEquals(testNetwork1.network, serviceDiscovered.serviceInfo.network)
 
             // Unregister, then register the service back: it should be lost and found again
             nsdManager.unregisterService(registrationRecord)
             val serviceLost1 = discoveryRecord.expectCallback<ServiceLost>()
             assertEquals(registeredInfo1.serviceName, serviceLost1.serviceInfo.serviceName)
-            assertEquals(testNetwork1.network, nsdShim.getNetwork(serviceLost1.serviceInfo))
+            assertEquals(testNetwork1.network, serviceLost1.serviceInfo.network)
 
             registrationRecord.expectCallback<ServiceUnregistered>()
             val registeredInfo2 = registerService(registrationRecord, si, executor)
             val serviceDiscovered2 = discoveryRecord.expectCallback<ServiceFound>()
             assertEquals(registeredInfo2.serviceName, serviceDiscovered2.serviceInfo.serviceName)
             assertEquals("$serviceType.", serviceDiscovered2.serviceInfo.serviceType)
-            assertEquals(testNetwork1.network, nsdShim.getNetwork(serviceDiscovered2.serviceInfo))
+            assertEquals(testNetwork1.network, serviceDiscovered2.serviceInfo.network)
 
             // Teardown, then bring back up a network on the test interface: the service should
             // go away, then come back
             testNetwork1.agent.unregister()
             val serviceLost = discoveryRecord.expectCallback<ServiceLost>()
             assertEquals(registeredInfo2.serviceName, serviceLost.serviceInfo.serviceName)
-            assertEquals(testNetwork1.network, nsdShim.getNetwork(serviceLost.serviceInfo))
+            assertEquals(testNetwork1.network, serviceLost.serviceInfo.network)
 
             val newAgent = runAsShell(MANAGE_TEST_NETWORKS) {
                 registerTestNetworkAgent(testNetwork1.iface.interfaceName)
@@ -696,7 +682,7 @@
             val serviceDiscovered3 = discoveryRecord.expectCallback<ServiceFound>()
             assertEquals(registeredInfo2.serviceName, serviceDiscovered3.serviceInfo.serviceName)
             assertEquals("$serviceType.", serviceDiscovered3.serviceInfo.serviceType)
-            assertEquals(newNetwork, nsdShim.getNetwork(serviceDiscovered3.serviceInfo))
+            assertEquals(newNetwork, serviceDiscovered3.serviceInfo.network)
         } cleanupStep {
             nsdManager.stopServiceDiscovery(discoveryRecord)
             discoveryRecord.expectCallback<DiscoveryStopped>()
@@ -707,9 +693,6 @@
 
     @Test
     fun testNsdManager_DiscoverWithNetworkRequest_NoMatchingNetwork() {
-        // This test requires shims supporting T+ APIs (discovering on network request)
-        assumeTrue(TestUtils.shouldTestTApis())
-
         val si = NsdServiceInfo()
         si.serviceType = serviceType
         si.serviceName = this.serviceName
@@ -722,7 +705,7 @@
         val specifier = TestNetworkSpecifier(testNetwork1.iface.interfaceName)
 
         tryTest {
-            nsdShim.discoverServices(nsdManager, serviceType, NsdManager.PROTOCOL_DNS_SD,
+            nsdManager.discoverServices(serviceType, NsdManager.PROTOCOL_DNS_SD,
                     NetworkRequest.Builder()
                             .removeCapability(NET_CAPABILITY_TRUSTED)
                             .addTransportType(TRANSPORT_TEST)
@@ -754,9 +737,6 @@
 
     @Test
     fun testNsdManager_ResolveOnNetwork() {
-        // This test requires shims supporting T+ APIs (NsdServiceInfo.network)
-        assumeTrue(TestUtils.shouldTestTApis())
-
         val si = NsdServiceInfo()
         si.serviceType = serviceType
         si.serviceName = this.serviceName
@@ -772,21 +752,21 @@
 
             val foundInfo1 = discoveryRecord.waitForServiceDiscovered(
                     serviceName, serviceType, testNetwork1.network)
-            assertEquals(testNetwork1.network, nsdShim.getNetwork(foundInfo1))
+            assertEquals(testNetwork1.network, foundInfo1.network)
             // Rewind as the service could be found on each interface in any order
             discoveryRecord.nextEvents.rewind(0)
             val foundInfo2 = discoveryRecord.waitForServiceDiscovered(
                     serviceName, serviceType, testNetwork2.network)
-            assertEquals(testNetwork2.network, nsdShim.getNetwork(foundInfo2))
+            assertEquals(testNetwork2.network, foundInfo2.network)
 
-            nsdShim.resolveService(nsdManager, foundInfo1, Executor { it.run() }, resolveRecord)
+            nsdManager.resolveService(foundInfo1, Executor { it.run() }, resolveRecord)
             val cb = resolveRecord.expectCallback<ServiceResolved>()
             cb.serviceInfo.let {
                 // Resolved service type has leading dot
                 assertEquals(".$serviceType", it.serviceType)
                 assertEquals(registeredInfo.serviceName, it.serviceName)
                 assertEquals(si.port, it.port)
-                assertEquals(testNetwork1.network, nsdShim.getNetwork(it))
+                assertEquals(testNetwork1.network, it.network)
                 checkAddressScopeId(testNetwork1.iface, it.hostAddresses)
             }
             // TODO: check that MDNS packets are sent only on testNetwork1.
@@ -799,9 +779,6 @@
 
     @Test
     fun testNsdManager_RegisterOnNetwork() {
-        // This test requires shims supporting T+ APIs (NsdServiceInfo.network)
-        assumeTrue(TestUtils.shouldTestTApis())
-
         val si = NsdServiceInfo()
         si.serviceType = serviceType
         si.serviceName = this.serviceName
@@ -817,27 +794,27 @@
 
         tryTest {
             // Discover service on testNetwork1.
-            nsdShim.discoverServices(nsdManager, serviceType, NsdManager.PROTOCOL_DNS_SD,
+            nsdManager.discoverServices(serviceType, NsdManager.PROTOCOL_DNS_SD,
                 testNetwork1.network, Executor { it.run() }, discoveryRecord)
             // Expect that service is found on testNetwork1
             val foundInfo = discoveryRecord.waitForServiceDiscovered(
                 serviceName, serviceType, testNetwork1.network)
-            assertEquals(testNetwork1.network, nsdShim.getNetwork(foundInfo))
+            assertEquals(testNetwork1.network, foundInfo.network)
 
             // Discover service on testNetwork2.
-            nsdShim.discoverServices(nsdManager, serviceType, NsdManager.PROTOCOL_DNS_SD,
+            nsdManager.discoverServices(serviceType, NsdManager.PROTOCOL_DNS_SD,
                 testNetwork2.network, Executor { it.run() }, discoveryRecord2)
             // Expect that discovery is started then no other callbacks.
             discoveryRecord2.expectCallback<DiscoveryStarted>()
             discoveryRecord2.assertNoCallback()
 
             // Discover service on all networks (not specify any network).
-            nsdShim.discoverServices(nsdManager, serviceType, NsdManager.PROTOCOL_DNS_SD,
+            nsdManager.discoverServices(serviceType, NsdManager.PROTOCOL_DNS_SD,
                 null as Network? /* network */, Executor { it.run() }, discoveryRecord3)
             // Expect that service is found on testNetwork1
             val foundInfo3 = discoveryRecord3.waitForServiceDiscovered(
                     serviceName, serviceType, testNetwork1.network)
-            assertEquals(testNetwork1.network, nsdShim.getNetwork(foundInfo3))
+            assertEquals(testNetwork1.network, foundInfo3.network)
         } cleanupStep {
             nsdManager.stopServiceDiscovery(discoveryRecord2)
             discoveryRecord2.expectCallback<DiscoveryStopped>()
@@ -970,9 +947,6 @@
 
     @Test
     fun testStopServiceResolution() {
-        // This test requires shims supporting U+ APIs (NsdManager.stopServiceResolution)
-        assumeTrue(TestUtils.shouldTestUApis())
-
         val si = NsdServiceInfo()
         si.serviceType = this@NsdManagerTest.serviceType
         si.serviceName = this@NsdManagerTest.serviceName
@@ -981,8 +955,8 @@
         val resolveRecord = NsdResolveRecord()
         // Try to resolve an unknown service then stop it immediately.
         // Expected ResolutionStopped callback.
-        nsdShim.resolveService(nsdManager, si, { it.run() }, resolveRecord)
-        nsdShim.stopServiceResolution(nsdManager, resolveRecord)
+        nsdManager.resolveService(si, { it.run() }, resolveRecord)
+        nsdManager.stopServiceResolution(resolveRecord)
         val stoppedCb = resolveRecord.expectCallback<ResolutionStopped>()
         assertEquals(si.serviceName, stoppedCb.serviceInfo.serviceName)
         assertEquals(si.serviceType, stoppedCb.serviceInfo.serviceType)
@@ -990,9 +964,6 @@
 
     @Test
     fun testRegisterServiceInfoCallback() {
-        // This test requires shims supporting U+ APIs (NsdManager.registerServiceInfoCallback)
-        assumeTrue(TestUtils.shouldTestUApis())
-
         val lp = cm.getLinkProperties(testNetwork1.network)
         assertNotNull(lp)
         val addresses = lp.addresses
@@ -1013,13 +984,13 @@
         val cbRecord = NsdServiceInfoCallbackRecord()
         tryTest {
             // Discover service on the network.
-            nsdShim.discoverServices(nsdManager, serviceType, NsdManager.PROTOCOL_DNS_SD,
+            nsdManager.discoverServices(serviceType, NsdManager.PROTOCOL_DNS_SD,
                     testNetwork1.network, Executor { it.run() }, discoveryRecord)
             val foundInfo = discoveryRecord.waitForServiceDiscovered(
                     serviceName, serviceType, testNetwork1.network)
 
             // Register service callback and check the addresses are the same as network addresses
-            nsdShim.registerServiceInfoCallback(nsdManager, foundInfo, { it.run() }, cbRecord)
+            nsdManager.registerServiceInfoCallback(foundInfo, { it.run() }, cbRecord)
             val serviceInfoCb = cbRecord.expectCallback<ServiceUpdated>()
             assertEquals(foundInfo.serviceName, serviceInfoCb.serviceInfo.serviceName)
             val hostAddresses = serviceInfoCb.serviceInfo.hostAddresses
@@ -1035,7 +1006,7 @@
             cbRecord.expectCallback<ServiceUpdatedLost>()
         } cleanupStep {
             // Cancel subscription and check stop callback received.
-            nsdShim.unregisterServiceInfoCallback(nsdManager, cbRecord)
+            nsdManager.unregisterServiceInfoCallback(cbRecord)
             cbRecord.expectCallback<UnregisterCallbackSucceeded>()
         } cleanup {
             nsdManager.stopServiceDiscovery(discoveryRecord)
@@ -1045,9 +1016,6 @@
 
     @Test
     fun testStopServiceResolutionFailedCallback() {
-        // This test requires shims supporting U+ APIs (NsdManager.stopServiceResolution)
-        assumeTrue(TestUtils.shouldTestUApis())
-
         // It's not possible to make ResolutionListener#onStopResolutionFailed callback sending
         // because it is only sent in very edge-case scenarios when the legacy implementation is
         // used, and the legacy implementation is never used in the current AOSP builds. Considering
@@ -1115,7 +1083,7 @@
         si: NsdServiceInfo,
         executor: Executor = Executor { it.run() }
     ): NsdServiceInfo {
-        nsdShim.registerService(nsdManager, si, NsdManager.PROTOCOL_DNS_SD, executor, record)
+        nsdManager.registerService(si, NsdManager.PROTOCOL_DNS_SD, executor, record)
         // We may not always get the name that we tried to register;
         // This events tells us the name that was registered.
         val cb = record.expectCallback<ServiceRegistered>(REGISTRATION_TIMEOUT_MS)
@@ -1124,7 +1092,7 @@
 
     private fun resolveService(discoveredInfo: NsdServiceInfo): NsdServiceInfo {
         val record = NsdResolveRecord()
-        nsdShim.resolveService(nsdManager, discoveredInfo, Executor { it.run() }, record)
+        nsdManager.resolveService(discoveredInfo, Executor { it.run() }, record)
         val resolvedCb = record.expectCallback<ServiceResolved>()
         assertEquals(discoveredInfo.serviceName, resolvedCb.serviceInfo.serviceName)
 
diff --git a/tests/native/connectivity_native_test/OWNERS b/tests/native/connectivity_native_test/OWNERS
index fbfcf92..c9bfc40 100644
--- a/tests/native/connectivity_native_test/OWNERS
+++ b/tests/native/connectivity_native_test/OWNERS
@@ -1,4 +1,4 @@
 # Bug template url: http://b/new?component=31808
 # TODO: move bug template config to common owners file once b/226427845 is resolved
 set noparent
-file:platform/packages/modules/Connectivity:master:/OWNERS_core_networking_xts
+file:platform/packages/modules/Connectivity:main:/OWNERS_core_networking_xts
diff --git a/tests/unit/java/com/android/metrics/NetworkNsdReportedMetricsTest.kt b/tests/unit/java/com/android/metrics/NetworkNsdReportedMetricsTest.kt
new file mode 100644
index 0000000..961c422
--- /dev/null
+++ b/tests/unit/java/com/android/metrics/NetworkNsdReportedMetricsTest.kt
@@ -0,0 +1,97 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * 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 com.android.metrics
+
+import android.os.Build
+import android.stats.connectivity.MdnsQueryResult
+import android.stats.connectivity.NsdEventType
+import com.android.testutils.DevSdkIgnoreRule
+import com.android.testutils.DevSdkIgnoreRunner
+import kotlin.test.assertEquals
+import kotlin.test.assertFalse
+import kotlin.test.assertTrue
+import org.junit.Test
+import org.junit.runner.RunWith
+import org.mockito.ArgumentCaptor
+import org.mockito.Mockito.mock
+import org.mockito.Mockito.verify
+
+@RunWith(DevSdkIgnoreRunner::class)
+@DevSdkIgnoreRule.IgnoreUpTo(Build.VERSION_CODES.TIRAMISU)
+class NetworkNsdReportedMetricsTest {
+    private val deps = mock(NetworkNsdReportedMetrics.Dependencies::class.java)
+
+    @Test
+    fun testReportServiceRegistrationSucceeded() {
+        val clientId = 99
+        val transactionId = 100
+        val durationMs = 10L
+        val metrics = NetworkNsdReportedMetrics(true /* isLegacy */, clientId, deps)
+        metrics.reportServiceRegistrationSucceeded(transactionId, durationMs)
+
+        val eventCaptor = ArgumentCaptor.forClass(NetworkNsdReported::class.java)
+        verify(deps).statsWrite(eventCaptor.capture())
+        eventCaptor.value.let {
+            assertTrue(it.isLegacy)
+            assertEquals(clientId, it.clientId)
+            assertEquals(transactionId, it.transactionId)
+            assertEquals(NsdEventType.NET_REGISTER, it.type)
+            assertEquals(MdnsQueryResult.MQR_SERVICE_REGISTERED, it.queryResult)
+            assertEquals(durationMs, it.eventDurationMillisec)
+        }
+    }
+
+    @Test
+    fun testReportServiceRegistrationFailed() {
+        val clientId = 99
+        val transactionId = 100
+        val durationMs = 10L
+        val metrics = NetworkNsdReportedMetrics(false /* isLegacy */, clientId, deps)
+        metrics.reportServiceRegistrationFailed(transactionId, durationMs)
+
+        val eventCaptor = ArgumentCaptor.forClass(NetworkNsdReported::class.java)
+        verify(deps).statsWrite(eventCaptor.capture())
+        eventCaptor.value.let {
+            assertFalse(it.isLegacy)
+            assertEquals(clientId, it.clientId)
+            assertEquals(transactionId, it.transactionId)
+            assertEquals(NsdEventType.NET_REGISTER, it.type)
+            assertEquals(MdnsQueryResult.MQR_SERVICE_REGISTRATION_FAILED, it.queryResult)
+            assertEquals(durationMs, it.eventDurationMillisec)
+        }
+    }
+
+    @Test
+    fun testReportServiceUnregistration() {
+        val clientId = 99
+        val transactionId = 100
+        val durationMs = 10L
+        val metrics = NetworkNsdReportedMetrics(true /* isLegacy */, clientId, deps)
+        metrics.reportServiceUnregistration(transactionId, durationMs)
+
+        val eventCaptor = ArgumentCaptor.forClass(NetworkNsdReported::class.java)
+        verify(deps).statsWrite(eventCaptor.capture())
+        eventCaptor.value.let {
+            assertTrue(it.isLegacy)
+            assertEquals(clientId, it.clientId)
+            assertEquals(transactionId, it.transactionId)
+            assertEquals(NsdEventType.NET_REGISTER, it.type)
+            assertEquals(MdnsQueryResult.MQR_SERVICE_UNREGISTERED, it.queryResult)
+            assertEquals(durationMs, it.eventDurationMillisec)
+        }
+    }
+}
diff --git a/tests/unit/java/com/android/server/NsdServiceTest.java b/tests/unit/java/com/android/server/NsdServiceTest.java
index f51b28d..55384b3 100644
--- a/tests/unit/java/com/android/server/NsdServiceTest.java
+++ b/tests/unit/java/com/android/server/NsdServiceTest.java
@@ -43,7 +43,9 @@
 import static org.junit.Assert.assertNull;
 import static org.junit.Assert.assertThrows;
 import static org.junit.Assert.assertTrue;
+import static org.mockito.ArgumentMatchers.anyBoolean;
 import static org.mockito.ArgumentMatchers.anyInt;
+import static org.mockito.ArgumentMatchers.anyLong;
 import static org.mockito.ArgumentMatchers.anyString;
 import static org.mockito.ArgumentMatchers.argThat;
 import static org.mockito.Mockito.any;
@@ -95,6 +97,7 @@
 import androidx.annotation.NonNull;
 import androidx.test.filters.SmallTest;
 
+import com.android.metrics.NetworkNsdReportedMetrics;
 import com.android.server.NsdService.Dependencies;
 import com.android.server.connectivity.mdns.MdnsAdvertiser;
 import com.android.server.connectivity.mdns.MdnsDiscoveryManager;
@@ -104,6 +107,7 @@
 import com.android.server.connectivity.mdns.MdnsServiceInfo;
 import com.android.server.connectivity.mdns.MdnsSocketProvider;
 import com.android.server.connectivity.mdns.MdnsSocketProvider.SocketRequestMonitor;
+import com.android.server.connectivity.mdns.util.MdnsUtils;
 import com.android.testutils.DevSdkIgnoreRule;
 import com.android.testutils.DevSdkIgnoreRunner;
 import com.android.testutils.HandlerUtils;
@@ -138,6 +142,7 @@
     static final int PROTOCOL = NsdManager.PROTOCOL_DNS_SD;
     private static final long CLEANUP_DELAY_MS = 500;
     private static final long TIMEOUT_MS = 500;
+    private static final long TEST_TIME_MS = 123L;
     private static final String SERVICE_NAME = "a_name";
     private static final String SERVICE_TYPE = "_test._tcp";
     private static final String SERVICE_FULL_NAME = SERVICE_NAME + "." + SERVICE_TYPE;
@@ -164,6 +169,8 @@
     @Mock WifiManager mWifiManager;
     @Mock WifiManager.MulticastLock mMulticastLock;
     @Mock ActivityManager mActivityManager;
+    @Mock NetworkNsdReportedMetrics mMetrics;
+    @Mock MdnsUtils.Clock mClock;
     SocketRequestMonitor mSocketRequestMonitor;
     OnUidImportanceListener mUidImportanceListener;
     HandlerThread mThread;
@@ -210,6 +217,9 @@
         doReturn(DEFAULT_RUNNING_APP_ACTIVE_IMPORTANCE_CUTOFF).when(mDeps).getDeviceConfigInt(
                 eq(NsdService.MDNS_CONFIG_RUNNING_APP_ACTIVE_IMPORTANCE_CUTOFF), anyInt());
         doReturn(mAdvertiser).when(mDeps).makeMdnsAdvertiser(any(), any(), any(), any());
+        doReturn(mMetrics).when(mDeps).makeNetworkNsdReportedMetrics(anyBoolean(), anyInt());
+        doReturn(mClock).when(mDeps).makeClock();
+        doReturn(TEST_TIME_MS).when(mClock).elapsedRealtime();
         mService = makeService();
         final ArgumentCaptor<SocketRequestMonitor> cbMonitorCaptor =
                 ArgumentCaptor.forClass(SocketRequestMonitor.class);
@@ -512,14 +522,16 @@
                 eq(SERVICE_NAME), eq(SERVICE_TYPE), eq(PORT), any(), eq(IFACE_IDX_ANY));
 
         // Register service successfully.
+        final int regId = regIdCaptor.getValue();
         final RegistrationInfo registrationInfo = new RegistrationInfo(
-                regIdCaptor.getValue(),
+                regId,
                 IMDnsEventListener.SERVICE_REGISTERED,
                 SERVICE_NAME,
                 SERVICE_TYPE,
                 PORT,
                 new byte[0] /* txtRecord */,
                 IFACE_IDX_ANY);
+        doReturn(TEST_TIME_MS + 10L).when(mClock).elapsedRealtime();
         eventListener.onServiceRegistrationStatus(registrationInfo);
 
         final ArgumentCaptor<NsdServiceInfo> registeredInfoCaptor =
@@ -528,19 +540,22 @@
                 .onServiceRegistered(registeredInfoCaptor.capture());
         final NsdServiceInfo registeredInfo = registeredInfoCaptor.getValue();
         assertEquals(SERVICE_NAME, registeredInfo.getServiceName());
+        verify(mMetrics).reportServiceRegistrationSucceeded(regId, 10L /* durationMs */);
 
         // Fail to register service.
         final RegistrationInfo registrationFailedInfo = new RegistrationInfo(
-                regIdCaptor.getValue(),
+                regId,
                 IMDnsEventListener.SERVICE_REGISTRATION_FAILED,
                 null /* serviceName */,
                 null /* registrationType */,
                 0 /* port */,
                 new byte[0] /* txtRecord */,
                 IFACE_IDX_ANY);
+        doReturn(TEST_TIME_MS + 20L).when(mClock).elapsedRealtime();
         eventListener.onServiceRegistrationStatus(registrationFailedInfo);
         verify(regListener, timeout(TIMEOUT_MS))
                 .onRegistrationFailed(any(), eq(FAILURE_INTERNAL_ERROR));
+        verify(mMetrics).reportServiceRegistrationFailed(regId, 20L /* durationMs */);
     }
 
     @Test
@@ -1215,17 +1230,22 @@
 
         // Verify onServiceRegistered callback
         final MdnsAdvertiser.AdvertiserCallback cb = cbCaptor.getValue();
-        cb.onRegisterServiceSucceeded(idCaptor.getValue(), regInfo);
+        final int regId = idCaptor.getValue();
+        doReturn(TEST_TIME_MS + 10L).when(mClock).elapsedRealtime();
+        cb.onRegisterServiceSucceeded(regId, regInfo);
 
         verify(regListener, timeout(TIMEOUT_MS)).onServiceRegistered(argThat(info -> matches(info,
                 new NsdServiceInfo(regInfo.getServiceName(), null))));
+        verify(mMetrics).reportServiceRegistrationSucceeded(regId, 10L /* durationMs */);
 
+        doReturn(TEST_TIME_MS + 100L).when(mClock).elapsedRealtime();
         client.unregisterService(regListener);
         waitForIdle();
         verify(mAdvertiser).removeService(idCaptor.getValue());
         verify(regListener, timeout(TIMEOUT_MS)).onServiceUnregistered(
                 argThat(info -> matches(info, regInfo)));
         verify(mSocketProvider, timeout(TIMEOUT_MS)).requestStopWhenInactive();
+        verify(mMetrics).reportServiceUnregistration(regId, 100L /* durationMs */);
     }
 
     @Test
@@ -1251,6 +1271,7 @@
 
         verify(regListener, timeout(TIMEOUT_MS)).onRegistrationFailed(
                 argThat(info -> matches(info, regInfo)), eq(FAILURE_INTERNAL_ERROR));
+        verify(mMetrics).reportServiceRegistrationFailed(anyInt(), anyLong());
     }
 
     @Test
@@ -1280,10 +1301,13 @@
 
         // Verify onServiceRegistered callback
         final MdnsAdvertiser.AdvertiserCallback cb = cbCaptor.getValue();
-        cb.onRegisterServiceSucceeded(idCaptor.getValue(), regInfo);
+        final int regId = idCaptor.getValue();
+        doReturn(TEST_TIME_MS + 10L).when(mClock).elapsedRealtime();
+        cb.onRegisterServiceSucceeded(regId, regInfo);
 
         verify(regListener, timeout(TIMEOUT_MS)).onServiceRegistered(
                 argThat(info -> matches(info, new NsdServiceInfo(regInfo.getServiceName(), null))));
+        verify(mMetrics).reportServiceRegistrationSucceeded(regId, 10L /* durationMs */);
     }
 
     @Test
diff --git a/tests/unit/java/com/android/server/connectivity/AutomaticOnOffKeepaliveTrackerTest.java b/tests/unit/java/com/android/server/connectivity/AutomaticOnOffKeepaliveTrackerTest.java
index b30c9ce..f4d3915 100644
--- a/tests/unit/java/com/android/server/connectivity/AutomaticOnOffKeepaliveTrackerTest.java
+++ b/tests/unit/java/com/android/server/connectivity/AutomaticOnOffKeepaliveTrackerTest.java
@@ -408,22 +408,22 @@
     @Test
     public void testIsAnyTcpSocketConnected_withTargetNetId() throws Exception {
         setupResponseWithSocketExisting();
-        mTestHandler.post(
-                () -> assertTrue(mAOOKeepaliveTracker.isAnyTcpSocketConnected(TEST_NETID)));
+        assertTrue(visibleOnHandlerThread(mTestHandler,
+                () -> mAOOKeepaliveTracker.isAnyTcpSocketConnected(TEST_NETID)));
     }
 
     @Test
     public void testIsAnyTcpSocketConnected_withIncorrectNetId() throws Exception {
         setupResponseWithSocketExisting();
-        mTestHandler.post(
-                () -> assertFalse(mAOOKeepaliveTracker.isAnyTcpSocketConnected(OTHER_NETID)));
+        assertFalse(visibleOnHandlerThread(mTestHandler,
+                () -> mAOOKeepaliveTracker.isAnyTcpSocketConnected(OTHER_NETID)));
     }
 
     @Test
     public void testIsAnyTcpSocketConnected_noSocketExists() throws Exception {
         setupResponseWithoutSocketExisting();
-        mTestHandler.post(
-                () -> assertFalse(mAOOKeepaliveTracker.isAnyTcpSocketConnected(TEST_NETID)));
+        assertFalse(visibleOnHandlerThread(mTestHandler,
+                () -> mAOOKeepaliveTracker.isAnyTcpSocketConnected(TEST_NETID)));
     }
 
     private void triggerEventKeepalive(int slot, int reason) {
@@ -500,9 +500,7 @@
         final AlarmManager.OnAlarmListener listener = listenerCaptor.getValue();
 
         // For realism, the listener should be posted on the handler
-        mTestHandler.post(() -> listener.onAlarm());
-        // Wait for the listener to be called. The listener enqueues a message to the handler.
-        HandlerUtils.waitForIdle(mTestHandler, TIMEOUT_MS);
+        visibleOnHandlerThread(mTestHandler, () -> listener.onAlarm());
         // Wait for the message posted by the listener to be processed.
         HandlerUtils.waitForIdle(mTestHandler, TIMEOUT_MS);
 
@@ -525,8 +523,7 @@
 
         doReturn(METRICS_COLLECTION_DURATION_MS).when(mDependencies).getElapsedRealtime();
         // For realism, the listener should be posted on the handler
-        mTestHandler.post(() -> listener.onAlarm());
-        HandlerUtils.waitForIdle(mTestHandler, TIMEOUT_MS);
+        visibleOnHandlerThread(mTestHandler, () -> listener.onAlarm());
 
         verify(mKeepaliveStatsTracker).writeAndResetMetrics();
         // Alarm is rescheduled.
diff --git a/tests/unit/java/com/android/server/connectivity/NetworkNotificationManagerTest.java b/tests/unit/java/com/android/server/connectivity/NetworkNotificationManagerTest.java
index 967083e..b319c30 100644
--- a/tests/unit/java/com/android/server/connectivity/NetworkNotificationManagerTest.java
+++ b/tests/unit/java/com/android/server/connectivity/NetworkNotificationManagerTest.java
@@ -50,6 +50,7 @@
 import android.content.Intent;
 import android.content.pm.ApplicationInfo;
 import android.content.pm.PackageManager;
+import android.content.pm.ResolveInfo;
 import android.content.res.Resources;
 import android.net.NetworkCapabilities;
 import android.net.NetworkInfo;
@@ -60,6 +61,7 @@
 import android.telephony.TelephonyManager;
 import android.testing.PollingCheck;
 import android.util.DisplayMetrics;
+import android.util.Log;
 import android.widget.TextView;
 
 import androidx.annotation.NonNull;
@@ -428,6 +430,22 @@
 
         // UiDevice.getLauncherPackageName() requires the test manifest to have a <queries> tag for
         // the launcher intent.
+        // Attempted workaround for b/286550950 where Settings is reported as the launcher
+        PollingCheck.check(
+                "Launcher package name was still settings after " + TEST_TIMEOUT_MS + "ms",
+                TEST_TIMEOUT_MS,
+                () -> {
+                    if ("com.android.settings".equals(uiDevice.getLauncherPackageName())) {
+                        final Intent intent = new Intent(Intent.ACTION_MAIN);
+                        intent.addCategory(Intent.CATEGORY_HOME);
+                        final List<ResolveInfo> acts = ctx.getPackageManager()
+                                .queryIntentActivities(intent, PackageManager.MATCH_DEFAULT_ONLY);
+                        Log.e(NetworkNotificationManagerTest.class.getSimpleName(),
+                                "Got settings as launcher name; launcher activities: " + acts);
+                        return false;
+                    }
+                    return true;
+                });
         final String launcherPackageName = uiDevice.getLauncherPackageName();
         assertTrue(String.format("Launcher (%s) is not shown", launcherPackageName),
                 uiDevice.wait(Until.hasObject(By.pkg(launcherPackageName)),
diff --git a/tests/unit/java/com/android/server/connectivity/mdns/MdnsDiscoveryManagerTests.java b/tests/unit/java/com/android/server/connectivity/mdns/MdnsDiscoveryManagerTests.java
index 1a4ae5d..e869b91 100644
--- a/tests/unit/java/com/android/server/connectivity/mdns/MdnsDiscoveryManagerTests.java
+++ b/tests/unit/java/com/android/server/connectivity/mdns/MdnsDiscoveryManagerTests.java
@@ -53,6 +53,7 @@
 import java.util.Arrays;
 import java.util.Collections;
 import java.util.List;
+import java.util.concurrent.ScheduledExecutorService;
 
 /** Tests for {@link MdnsDiscoveryManager}. */
 @RunWith(DevSdkIgnoreRunner.class)
@@ -80,6 +81,7 @@
     private static final Pair<String, SocketKey> PER_SOCKET_SERVICE_TYPE_2_NETWORK_2 =
             Pair.create(SERVICE_TYPE_2, SOCKET_KEY_NETWORK_2);
     @Mock private ExecutorProvider executorProvider;
+    @Mock private ScheduledExecutorService mockExecutorService;
     @Mock private MdnsSocketClientBase socketClient;
     @Mock private MdnsServiceTypeClient mockServiceTypeClientType1NullNetwork;
     @Mock private MdnsServiceTypeClient mockServiceTypeClientType1Network1;
@@ -128,6 +130,7 @@
                         return null;
                     }
                 };
+        doReturn(mockExecutorService).when(mockServiceTypeClientType1NullNetwork).getExecutor();
     }
 
     @After
@@ -165,11 +168,25 @@
         when(mockServiceTypeClientType1NullNetwork.stopSendAndReceive(mockListenerOne))
                 .thenReturn(true);
         runOnHandler(() -> discoveryManager.unregisterListener(SERVICE_TYPE_1, mockListenerOne));
+        verify(executorProvider).shutdownExecutorService(mockExecutorService);
         verify(mockServiceTypeClientType1NullNetwork).stopSendAndReceive(mockListenerOne);
         verify(socketClient).stopDiscovery();
     }
 
     @Test
+    public void onSocketDestroy_shutdownExecutorService() throws IOException {
+        final MdnsSearchOptions options =
+                MdnsSearchOptions.newBuilder().setNetwork(null /* network */).build();
+        final SocketCreationCallback callback = expectSocketCreationCallback(
+                SERVICE_TYPE_1, mockListenerOne, options);
+        runOnHandler(() -> callback.onSocketCreated(SOCKET_KEY_NULL_NETWORK));
+        verify(mockServiceTypeClientType1NullNetwork).startSendAndReceive(mockListenerOne, options);
+
+        runOnHandler(() -> callback.onSocketDestroyed(SOCKET_KEY_NULL_NETWORK));
+        verify(executorProvider).shutdownExecutorService(mockExecutorService);
+    }
+
+    @Test
     public void registerMultipleListeners() throws IOException {
         final MdnsSearchOptions options =
                 MdnsSearchOptions.newBuilder().setNetwork(null /* network */).build();
diff --git a/tests/unit/java/com/android/server/connectivity/mdns/MdnsResponseDecoderTests.java b/tests/unit/java/com/android/server/connectivity/mdns/MdnsResponseDecoderTests.java
index 05eca84..d71bea4 100644
--- a/tests/unit/java/com/android/server/connectivity/mdns/MdnsResponseDecoderTests.java
+++ b/tests/unit/java/com/android/server/connectivity/mdns/MdnsResponseDecoderTests.java
@@ -18,7 +18,7 @@
 
 import static android.net.InetAddresses.parseNumericAddress;
 
-import static com.android.server.connectivity.mdns.MdnsResponseDecoder.Clock;
+import static com.android.server.connectivity.mdns.util.MdnsUtils.Clock;
 import static com.android.testutils.DevSdkIgnoreRuleKt.SC_V2;
 
 import static org.junit.Assert.assertArrayEquals;
diff --git a/tests/unit/java/com/android/server/connectivity/mdns/MdnsServiceTypeClientTests.java b/tests/unit/java/com/android/server/connectivity/mdns/MdnsServiceTypeClientTests.java
index cf6275f..1fdfe09 100644
--- a/tests/unit/java/com/android/server/connectivity/mdns/MdnsServiceTypeClientTests.java
+++ b/tests/unit/java/com/android/server/connectivity/mdns/MdnsServiceTypeClientTests.java
@@ -16,6 +16,7 @@
 
 package com.android.server.connectivity.mdns;
 
+import static com.android.server.connectivity.mdns.MdnsServiceTypeClient.EVENT_START_QUERYTASK;
 import static com.android.testutils.DevSdkIgnoreRuleKt.SC_V2;
 
 import static org.junit.Assert.assertArrayEquals;
@@ -26,8 +27,10 @@
 import static org.junit.Assert.assertTrue;
 import static org.mockito.ArgumentMatchers.any;
 import static org.mockito.ArgumentMatchers.anyInt;
+import static org.mockito.ArgumentMatchers.anyLong;
 import static org.mockito.ArgumentMatchers.argThat;
 import static org.mockito.ArgumentMatchers.eq;
+import static org.mockito.Mockito.doAnswer;
 import static org.mockito.Mockito.doReturn;
 import static org.mockito.Mockito.inOrder;
 import static org.mockito.Mockito.never;
@@ -43,12 +46,13 @@
 import android.net.Network;
 import android.os.Handler;
 import android.os.HandlerThread;
+import android.os.Message;
 import android.text.TextUtils;
 
 import com.android.net.module.util.CollectionUtils;
 import com.android.net.module.util.SharedLog;
 import com.android.server.connectivity.mdns.MdnsServiceInfo.TextEntry;
-import com.android.server.connectivity.mdns.MdnsServiceTypeClient.QueryTaskConfig;
+import com.android.server.connectivity.mdns.util.MdnsUtils;
 import com.android.testutils.DevSdkIgnoreRule;
 import com.android.testutils.DevSdkIgnoreRunner;
 import com.android.testutils.HandlerUtils;
@@ -88,6 +92,7 @@
     private static final int INTERFACE_INDEX = 999;
     private static final long DEFAULT_TIMEOUT = 2000L;
     private static final String SERVICE_TYPE = "_googlecast._tcp.local";
+    private static final String SUBTYPE = "_subtype";
     private static final String[] SERVICE_TYPE_LABELS = TextUtils.split(SERVICE_TYPE, "\\.");
     private static final InetSocketAddress IPV4_ADDRESS = new InetSocketAddress(
             MdnsConstants.getMdnsIPv4Address(), MdnsConstants.MDNS_PORT);
@@ -109,9 +114,11 @@
     @Mock
     private Network mockNetwork;
     @Mock
-    private MdnsResponseDecoder.Clock mockDecoderClock;
+    private MdnsUtils.Clock mockDecoderClock;
     @Mock
     private SharedLog mockSharedLog;
+    @Mock
+    private MdnsServiceTypeClient.Dependencies mockDeps;
     @Captor
     private ArgumentCaptor<MdnsServiceInfo> serviceInfoCaptor;
 
@@ -119,13 +126,16 @@
 
     private DatagramPacket[] expectedIPv4Packets;
     private DatagramPacket[] expectedIPv6Packets;
-    private ScheduledFuture<?>[] expectedSendFutures;
     private FakeExecutor currentThreadExecutor = new FakeExecutor();
 
     private MdnsServiceTypeClient client;
     private SocketKey socketKey;
     private HandlerThread thread;
     private Handler handler;
+    private MdnsServiceCache serviceCache;
+    private long latestDelayMs = 0;
+    private Message delayMessage = null;
+    private Handler realHandler = null;
 
     @Before
     @SuppressWarnings("DoNotMock")
@@ -135,15 +145,13 @@
 
         expectedIPv4Packets = new DatagramPacket[16];
         expectedIPv6Packets = new DatagramPacket[16];
-        expectedSendFutures = new ScheduledFuture<?>[16];
         socketKey = new SocketKey(mockNetwork, INTERFACE_INDEX);
 
-        for (int i = 0; i < expectedSendFutures.length; ++i) {
+        for (int i = 0; i < expectedIPv4Packets.length; ++i) {
             expectedIPv4Packets[i] = new DatagramPacket(buf, 0 /* offset */, 5 /* length */,
                     MdnsConstants.getMdnsIPv4Address(), MdnsConstants.MDNS_PORT);
             expectedIPv6Packets[i] = new DatagramPacket(buf, 0 /* offset */, 5 /* length */,
                     MdnsConstants.getMdnsIPv6Address(), MdnsConstants.MDNS_PORT);
-            expectedSendFutures[i] = Mockito.mock(ScheduledFuture.class);
         }
         when(mockPacketWriter.getPacket(IPV4_ADDRESS))
                 .thenReturn(expectedIPv4Packets[0])
@@ -184,9 +192,32 @@
         thread = new HandlerThread("MdnsServiceTypeClientTests");
         thread.start();
         handler = new Handler(thread.getLooper());
+        serviceCache = new MdnsServiceCache(thread.getLooper());
+
+        doAnswer(inv -> {
+            latestDelayMs = 0;
+            delayMessage = null;
+            return true;
+        }).when(mockDeps).removeMessages(any(Handler.class), eq(EVENT_START_QUERYTASK));
+
+        doAnswer(inv -> {
+            realHandler = (Handler) inv.getArguments()[0];
+            delayMessage = (Message) inv.getArguments()[1];
+            latestDelayMs = (long) inv.getArguments()[2];
+            return true;
+        }).when(mockDeps).sendMessageDelayed(any(Handler.class), any(Message.class), anyLong());
+
+        doAnswer(inv -> {
+            final Handler handler = (Handler) inv.getArguments()[0];
+            final Message message = (Message) inv.getArguments()[1];
+            runOnHandler(() -> handler.dispatchMessage(message));
+            return true;
+        }).when(mockDeps).sendMessage(any(Handler.class), any(Message.class));
+
         client =
                 new MdnsServiceTypeClient(SERVICE_TYPE, mockSocketClient, currentThreadExecutor,
-                        mockDecoderClock, socketKey, mockSharedLog, thread.getLooper()) {
+                        mockDecoderClock, socketKey, mockSharedLog, thread.getLooper(), mockDeps,
+                        serviceCache) {
                     @Override
                     MdnsPacketWriter createMdnsPacketWriter() {
                         return mockPacketWriter;
@@ -223,11 +254,18 @@
         runOnHandler(() -> client.notifySocketDestroyed());
     }
 
+    private void dispatchMessage() {
+        runOnHandler(() -> realHandler.dispatchMessage(delayMessage));
+        delayMessage = null;
+    }
+
     @Test
     public void sendQueries_activeScanMode() {
         MdnsSearchOptions searchOptions =
-                MdnsSearchOptions.newBuilder().addSubtype("12345").setIsPassiveMode(false).build();
+                MdnsSearchOptions.newBuilder().addSubtype(SUBTYPE).setIsPassiveMode(false).build();
         startSendAndReceive(mockListenerOne, searchOptions);
+        // Always try to remove the task.
+        verify(mockDeps, times(1)).removeMessages(any(), eq(EVENT_START_QUERYTASK));
 
         // First burst, 3 queries.
         verifyAndSendQuery(0, 0, /* expectsUnicastResponse= */ true);
@@ -265,17 +303,21 @@
                 13, MdnsConfigs.timeBetweenQueriesInBurstMs(), /* expectsUnicastResponse= */ false);
         verifyAndSendQuery(
                 14, MdnsConfigs.timeBetweenQueriesInBurstMs(), /* expectsUnicastResponse= */ false);
+        // Verify that Task is not removed before stopSendAndReceive was called.
+        verify(mockDeps, times(1)).removeMessages(any(), eq(EVENT_START_QUERYTASK));
 
         // Stop sending packets.
         stopSendAndReceive(mockListenerOne);
-        verify(expectedSendFutures[15]).cancel(true);
+        verify(mockDeps, times(2)).removeMessages(any(), eq(EVENT_START_QUERYTASK));
     }
 
     @Test
     public void sendQueries_reentry_activeScanMode() {
         MdnsSearchOptions searchOptions =
-                MdnsSearchOptions.newBuilder().addSubtype("12345").setIsPassiveMode(false).build();
+                MdnsSearchOptions.newBuilder().addSubtype(SUBTYPE).setIsPassiveMode(false).build();
         startSendAndReceive(mockListenerOne, searchOptions);
+        // Always try to remove the task.
+        verify(mockDeps, times(1)).removeMessages(any(), eq(EVENT_START_QUERYTASK));
 
         // First burst, first query is sent.
         verifyAndSendQuery(0, 0, /* expectsUnicastResponse= */ true);
@@ -283,13 +325,13 @@
         // After the first query is sent, change the subtypes, and restart.
         searchOptions =
                 MdnsSearchOptions.newBuilder()
-                        .addSubtype("12345")
-                        .addSubtype("abcde")
+                        .addSubtype(SUBTYPE)
+                        .addSubtype("_subtype2")
                         .setIsPassiveMode(false)
                         .build();
         startSendAndReceive(mockListenerOne, searchOptions);
         // The previous scheduled task should be canceled.
-        verify(expectedSendFutures[1]).cancel(true);
+        verify(mockDeps, times(2)).removeMessages(any(), eq(EVENT_START_QUERYTASK));
 
         // Queries should continue to be sent.
         verifyAndSendQuery(1, 0, /* expectsUnicastResponse= */ true);
@@ -300,14 +342,16 @@
 
         // Stop sending packets.
         stopSendAndReceive(mockListenerOne);
-        verify(expectedSendFutures[5]).cancel(true);
+        verify(mockDeps, times(3)).removeMessages(any(), eq(EVENT_START_QUERYTASK));
     }
 
     @Test
     public void sendQueries_passiveScanMode() {
         MdnsSearchOptions searchOptions =
-                MdnsSearchOptions.newBuilder().addSubtype("12345").setIsPassiveMode(true).build();
+                MdnsSearchOptions.newBuilder().addSubtype(SUBTYPE).setIsPassiveMode(true).build();
         startSendAndReceive(mockListenerOne, searchOptions);
+        // Always try to remove the task.
+        verify(mockDeps, times(1)).removeMessages(any(), eq(EVENT_START_QUERYTASK));
 
         // First burst, 3 query.
         verifyAndSendQuery(0, 0, /* expectsUnicastResponse= */ true);
@@ -324,15 +368,17 @@
 
         // Stop sending packets.
         stopSendAndReceive(mockListenerOne);
-        verify(expectedSendFutures[5]).cancel(true);
+        verify(mockDeps, times(2)).removeMessages(any(), eq(EVENT_START_QUERYTASK));
     }
 
     @Test
     public void sendQueries_activeScanWithQueryBackoff() {
         MdnsSearchOptions searchOptions =
-                MdnsSearchOptions.newBuilder().addSubtype("12345").setIsPassiveMode(
+                MdnsSearchOptions.newBuilder().addSubtype(SUBTYPE).setIsPassiveMode(
                         false).setNumOfQueriesBeforeBackoff(11).build();
         startSendAndReceive(mockListenerOne, searchOptions);
+        // Always try to remove the task.
+        verify(mockDeps, times(1)).removeMessages(any(), eq(EVENT_START_QUERYTASK));
 
         // First burst, 3 queries.
         verifyAndSendQuery(0, 0, /* expectsUnicastResponse= */ true);
@@ -367,47 +413,59 @@
         // 0.8 * smallestRemainingTtl is larger than time to next run.
         long currentTime = TEST_TTL / 2 + TEST_ELAPSED_REALTIME;
         doReturn(currentTime).when(mockDecoderClock).elapsedRealtime();
+        doReturn(true).when(mockDeps).hasMessages(any(), eq(EVENT_START_QUERYTASK));
         processResponse(createResponse(
                 "service-instance-1", "192.0.2.123", 5353,
                 SERVICE_TYPE_LABELS,
                 Collections.emptyMap(), TEST_TTL), socketKey);
-        verifyAndSendQuery(12, (long) (TEST_TTL / 2 * 0.8), /* expectsUnicastResponse= */
-                false);
+        verify(mockDeps, times(2)).removeMessages(any(), eq(EVENT_START_QUERYTASK));
+        assertNotNull(delayMessage);
+        verifyAndSendQuery(12 /* index */, (long) (TEST_TTL / 2 * 0.8) /* timeInMs */,
+                false /* expectsUnicastResponse */, true /* multipleSocketDiscovery */,
+                14 /* scheduledCount */);
         currentTime += (long) (TEST_TTL / 2 * 0.8);
         doReturn(currentTime).when(mockDecoderClock).elapsedRealtime();
-        verifyAndSendQuery(
-                13, MdnsConfigs.timeBetweenQueriesInBurstMs(), /* expectsUnicastResponse= */ false);
+        verifyAndSendQuery(13 /* index */, MdnsConfigs.timeBetweenQueriesInBurstMs(),
+                false /* expectsUnicastResponse */, true /* multipleSocketDiscovery */,
+                15 /* scheduledCount */);
     }
 
     @Test
     public void sendQueries_passiveScanWithQueryBackoff() {
         MdnsSearchOptions searchOptions =
-                MdnsSearchOptions.newBuilder().addSubtype("12345").setIsPassiveMode(
+                MdnsSearchOptions.newBuilder().addSubtype(SUBTYPE).setIsPassiveMode(
                         true).setNumOfQueriesBeforeBackoff(3).build();
         startSendAndReceive(mockListenerOne, searchOptions);
-        verifyAndSendQuery(0, 0, /* expectsUnicastResponse= */ true);
-        verifyAndSendQuery(
-                1, MdnsConfigs.timeBetweenQueriesInBurstMs(), /* expectsUnicastResponse= */ false);
-        verifyAndSendQuery(
-                2, MdnsConfigs.timeBetweenQueriesInBurstMs(), /* expectsUnicastResponse= */ false);
-        verifyAndSendQuery(3, MdnsConfigs.timeBetweenBurstsMs(), /* expectsUnicastResponse= */
-                false);
-        assertEquals(4, currentThreadExecutor.getNumOfScheduledFuture());
+        // Always try to remove the task.
+        verify(mockDeps, times(1)).removeMessages(any(), eq(EVENT_START_QUERYTASK));
+
+        verifyAndSendQuery(0 /* index */, 0 /* timeInMs */, true /* expectsUnicastResponse */,
+                true /* multipleSocketDiscovery */, 1 /* scheduledCount */);
+        verifyAndSendQuery(1 /* index */, MdnsConfigs.timeBetweenQueriesInBurstMs(),
+                false /* expectsUnicastResponse */, true /* multipleSocketDiscovery */,
+                2 /* scheduledCount */);
+        verifyAndSendQuery(2 /* index */, MdnsConfigs.timeBetweenQueriesInBurstMs(),
+                false /* expectsUnicastResponse */, true /* multipleSocketDiscovery */,
+                3 /* scheduledCount */);
+        verifyAndSendQuery(3 /* index */, MdnsConfigs.timeBetweenBurstsMs(),
+                false /* expectsUnicastResponse */, true /* multipleSocketDiscovery */,
+                4 /* scheduledCount */);
 
         // In backoff mode, the current scheduled task will be canceled and reschedule if the
         // 0.8 * smallestRemainingTtl is larger than time to next run.
         doReturn(TEST_ELAPSED_REALTIME + 20000).when(mockDecoderClock).elapsedRealtime();
+        doReturn(true).when(mockDeps).hasMessages(any(), eq(EVENT_START_QUERYTASK));
         processResponse(createResponse(
                 "service-instance-1", "192.0.2.123", 5353,
                 SERVICE_TYPE_LABELS,
                 Collections.emptyMap(), TEST_TTL), socketKey);
-        verify(expectedSendFutures[4]).cancel(true);
-        assertEquals(5, currentThreadExecutor.getNumOfScheduledFuture());
-        verifyAndSendQuery(4, 80000 /* timeInMs */, false /* expectsUnicastResponse */);
-        assertEquals(6, currentThreadExecutor.getNumOfScheduledFuture());
+        verify(mockDeps, times(2)).removeMessages(any(), eq(EVENT_START_QUERYTASK));
+        assertNotNull(delayMessage);
+        verifyAndSendQuery(4 /* index */, 80000 /* timeInMs */, false /* expectsUnicastResponse */,
+                true /* multipleSocketDiscovery */, 6 /* scheduledCount */);
         // Next run should also be scheduled in 0.8 * smallestRemainingTtl
-        verifyAndSendQuery(5, 80000 /* timeInMs */, false /* expectsUnicastResponse */);
-        assertEquals(7, currentThreadExecutor.getNumOfScheduledFuture());
+        verifyAndSendQuery(5 /* index */, 80000 /* timeInMs */, false /* expectsUnicastResponse */,
+                true /* multipleSocketDiscovery */, 7 /* scheduledCount */);
 
         // If the records is not refreshed, the current scheduled task will not be canceled.
         doReturn(TEST_ELAPSED_REALTIME + 20001).when(mockDecoderClock).elapsedRealtime();
@@ -416,7 +474,7 @@
                 SERVICE_TYPE_LABELS,
                 Collections.emptyMap(), TEST_TTL,
                 TEST_ELAPSED_REALTIME - 1), socketKey);
-        verify(expectedSendFutures[7], never()).cancel(true);
+        verify(mockDeps, times(2)).removeMessages(any(), eq(EVENT_START_QUERYTASK));
 
         // In backoff mode, the current scheduled task will not be canceled if the
         // 0.8 * smallestRemainingTtl is smaller than time to next run.
@@ -425,17 +483,19 @@
                 "service-instance-1", "192.0.2.123", 5353,
                 SERVICE_TYPE_LABELS,
                 Collections.emptyMap(), TEST_TTL), socketKey);
-        verify(expectedSendFutures[7], never()).cancel(true);
+        verify(mockDeps, times(2)).removeMessages(any(), eq(EVENT_START_QUERYTASK));
 
         stopSendAndReceive(mockListenerOne);
-        verify(expectedSendFutures[7]).cancel(true);
+        verify(mockDeps, times(3)).removeMessages(any(), eq(EVENT_START_QUERYTASK));
     }
 
     @Test
     public void sendQueries_reentry_passiveScanMode() {
         MdnsSearchOptions searchOptions =
-                MdnsSearchOptions.newBuilder().addSubtype("12345").setIsPassiveMode(true).build();
+                MdnsSearchOptions.newBuilder().addSubtype(SUBTYPE).setIsPassiveMode(true).build();
         startSendAndReceive(mockListenerOne, searchOptions);
+        // Always try to remove the task.
+        verify(mockDeps, times(1)).removeMessages(any(), eq(EVENT_START_QUERYTASK));
 
         // First burst, first query is sent.
         verifyAndSendQuery(0, 0, /* expectsUnicastResponse= */ true);
@@ -443,13 +503,13 @@
         // After the first query is sent, change the subtypes, and restart.
         searchOptions =
                 MdnsSearchOptions.newBuilder()
-                        .addSubtype("12345")
-                        .addSubtype("abcde")
+                        .addSubtype(SUBTYPE)
+                        .addSubtype("_subtype2")
                         .setIsPassiveMode(true)
                         .build();
         startSendAndReceive(mockListenerOne, searchOptions);
         // The previous scheduled task should be canceled.
-        verify(expectedSendFutures[1]).cancel(true);
+        verify(mockDeps, times(2)).removeMessages(any(), eq(EVENT_START_QUERYTASK));
 
         // Queries should continue to be sent.
         verifyAndSendQuery(1, 0, /* expectsUnicastResponse= */ true);
@@ -460,7 +520,7 @@
 
         // Stop sending packets.
         stopSendAndReceive(mockListenerOne);
-        verify(expectedSendFutures[5]).cancel(true);
+        verify(mockDeps, times(3)).removeMessages(any(), eq(EVENT_START_QUERYTASK));
     }
 
     @Test
@@ -468,7 +528,7 @@
     public void testQueryTaskConfig_alwaysAskForUnicastResponse() {
         //MdnsConfigsFlagsImpl.alwaysAskForUnicastResponseInEachBurst.override(true);
         MdnsSearchOptions searchOptions =
-                MdnsSearchOptions.newBuilder().addSubtype("12345").setIsPassiveMode(false).build();
+                MdnsSearchOptions.newBuilder().addSubtype(SUBTYPE).setIsPassiveMode(false).build();
         QueryTaskConfig config = new QueryTaskConfig(
                 searchOptions.getSubtypes(), searchOptions.isPassiveMode(),
                 false /* onlyUseIpv6OnIpv6OnlyNetworks */, 3 /* numOfQueriesBeforeBackoff */,
@@ -499,7 +559,7 @@
     @Test
     public void testQueryTaskConfig_askForUnicastInFirstQuery() {
         MdnsSearchOptions searchOptions =
-                MdnsSearchOptions.newBuilder().addSubtype("12345").setIsPassiveMode(false).build();
+                MdnsSearchOptions.newBuilder().addSubtype(SUBTYPE).setIsPassiveMode(false).build();
         QueryTaskConfig config = new QueryTaskConfig(
                 searchOptions.getSubtypes(), searchOptions.isPassiveMode(),
                 false /* onlyUseIpv6OnIpv6OnlyNetworks */, 3 /* numOfQueriesBeforeBackoff */,
@@ -530,15 +590,15 @@
     @Test
     public void testIfPreviousTaskIsCanceledWhenNewSessionStarts() {
         MdnsSearchOptions searchOptions =
-                MdnsSearchOptions.newBuilder().addSubtype("12345").setIsPassiveMode(true).build();
+                MdnsSearchOptions.newBuilder().addSubtype(SUBTYPE).setIsPassiveMode(true).build();
         startSendAndReceive(mockListenerOne, searchOptions);
         Runnable firstMdnsTask = currentThreadExecutor.getAndClearSubmittedRunnable();
 
         // Change the sutypes and start a new session.
         searchOptions =
                 MdnsSearchOptions.newBuilder()
-                        .addSubtype("12345")
-                        .addSubtype("abcde")
+                        .addSubtype(SUBTYPE)
+                        .addSubtype("_subtype2")
                         .setIsPassiveMode(true)
                         .build();
         startSendAndReceive(mockListenerOne, searchOptions);
@@ -559,7 +619,7 @@
     public void testIfPreviousTaskIsCanceledWhenSessionStops() {
         //MdnsConfigsFlagsImpl.shouldCancelScanTaskWhenFutureIsNull.override(true);
         MdnsSearchOptions searchOptions =
-                MdnsSearchOptions.newBuilder().addSubtype("12345").setIsPassiveMode(true).build();
+                MdnsSearchOptions.newBuilder().addSubtype(SUBTYPE).setIsPassiveMode(true).build();
         startSendAndReceive(mockListenerOne, searchOptions);
         // Change the sutypes and start a new session.
         stopSendAndReceive(mockListenerOne);
@@ -596,10 +656,9 @@
 
         // This time no query is submitted, only scheduled
         assertNull(currentThreadExecutor.getAndClearSubmittedRunnable());
-        assertNotNull(currentThreadExecutor.getAndClearLastScheduledRunnable());
         // This just skips the first query of the first burst
-        assertEquals(MdnsConfigs.timeBetweenQueriesInBurstMs(),
-                currentThreadExecutor.getAndClearLastScheduledDelayInMs());
+        verify(mockDeps).sendMessageDelayed(
+                any(), any(), eq(MdnsConfigs.timeBetweenQueriesInBurstMs()));
     }
 
     private static void verifyServiceInfo(MdnsServiceInfo serviceInfo, String serviceName,
@@ -649,14 +708,12 @@
 
         // Process the initial response.
         processResponse(createResponse(
-                "service-instance-1", ipV4Address, 5353,
-                /* subtype= */ "ABCDE",
+                "service-instance-1", ipV4Address, 5353, SUBTYPE,
                 Collections.emptyMap(), TEST_TTL), socketKey);
 
         // Process a second response with a different port and updated text attributes.
         processResponse(createResponse(
-                        "service-instance-1", ipV4Address, 5354,
-                        /* subtype= */ "ABCDE",
+                        "service-instance-1", ipV4Address, 5354, SUBTYPE,
                         Collections.singletonMap("key", "value"), TEST_TTL),
                 socketKey);
 
@@ -668,7 +725,7 @@
                 List.of(ipV4Address) /* ipv4Address */,
                 List.of() /* ipv6Address */,
                 5353 /* port */,
-                Collections.singletonList("ABCDE") /* subTypes */,
+                Collections.singletonList(SUBTYPE) /* subTypes */,
                 Collections.singletonMap("key", null) /* attributes */,
                 socketKey);
 
@@ -678,7 +735,7 @@
         assertEquals(initialServiceInfo.getServiceInstanceName(), "service-instance-1");
         assertEquals(initialServiceInfo.getIpv4Address(), ipV4Address);
         assertEquals(initialServiceInfo.getPort(), 5353);
-        assertEquals(initialServiceInfo.getSubtypes(), Collections.singletonList("ABCDE"));
+        assertEquals(initialServiceInfo.getSubtypes(), Collections.singletonList(SUBTYPE));
         assertNull(initialServiceInfo.getAttributeByKey("key"));
         assertEquals(socketKey.getInterfaceIndex(), initialServiceInfo.getInterfaceIndex());
         assertEquals(socketKey.getNetwork(), initialServiceInfo.getNetwork());
@@ -690,7 +747,7 @@
         assertEquals(updatedServiceInfo.getIpv4Address(), ipV4Address);
         assertEquals(updatedServiceInfo.getPort(), 5354);
         assertTrue(updatedServiceInfo.hasSubtypes());
-        assertEquals(updatedServiceInfo.getSubtypes(), Collections.singletonList("ABCDE"));
+        assertEquals(updatedServiceInfo.getSubtypes(), Collections.singletonList(SUBTYPE));
         assertEquals(updatedServiceInfo.getAttributeByKey("key"), "value");
         assertEquals(socketKey.getInterfaceIndex(), updatedServiceInfo.getInterfaceIndex());
         assertEquals(socketKey.getNetwork(), updatedServiceInfo.getNetwork());
@@ -703,14 +760,12 @@
 
         // Process the initial response.
         processResponse(createResponse(
-                "service-instance-1", ipV6Address, 5353,
-                /* subtype= */ "ABCDE",
+                "service-instance-1", ipV6Address, 5353, SUBTYPE,
                 Collections.emptyMap(), TEST_TTL), socketKey);
 
         // Process a second response with a different port and updated text attributes.
         processResponse(createResponse(
-                        "service-instance-1", ipV6Address, 5354,
-                        /* subtype= */ "ABCDE",
+                        "service-instance-1", ipV6Address, 5354, SUBTYPE,
                         Collections.singletonMap("key", "value"), TEST_TTL),
                 socketKey);
 
@@ -722,7 +777,7 @@
                 List.of() /* ipv4Address */,
                 List.of(ipV6Address) /* ipv6Address */,
                 5353 /* port */,
-                Collections.singletonList("ABCDE") /* subTypes */,
+                Collections.singletonList(SUBTYPE) /* subTypes */,
                 Collections.singletonMap("key", null) /* attributes */,
                 socketKey);
 
@@ -732,7 +787,7 @@
         assertEquals(initialServiceInfo.getServiceInstanceName(), "service-instance-1");
         assertEquals(initialServiceInfo.getIpv6Address(), ipV6Address);
         assertEquals(initialServiceInfo.getPort(), 5353);
-        assertEquals(initialServiceInfo.getSubtypes(), Collections.singletonList("ABCDE"));
+        assertEquals(initialServiceInfo.getSubtypes(), Collections.singletonList(SUBTYPE));
         assertNull(initialServiceInfo.getAttributeByKey("key"));
         assertEquals(socketKey.getInterfaceIndex(), initialServiceInfo.getInterfaceIndex());
         assertEquals(socketKey.getNetwork(), initialServiceInfo.getNetwork());
@@ -744,7 +799,7 @@
         assertEquals(updatedServiceInfo.getIpv6Address(), ipV6Address);
         assertEquals(updatedServiceInfo.getPort(), 5354);
         assertTrue(updatedServiceInfo.hasSubtypes());
-        assertEquals(updatedServiceInfo.getSubtypes(), Collections.singletonList("ABCDE"));
+        assertEquals(updatedServiceInfo.getSubtypes(), Collections.singletonList(SUBTYPE));
         assertEquals(updatedServiceInfo.getAttributeByKey("key"), "value");
         assertEquals(socketKey.getInterfaceIndex(), updatedServiceInfo.getInterfaceIndex());
         assertEquals(socketKey.getNetwork(), updatedServiceInfo.getNetwork());
@@ -806,8 +861,7 @@
     public void reportExistingServiceToNewlyRegisteredListeners() throws Exception {
         // Process the initial response.
         processResponse(createResponse(
-                "service-instance-1", "192.168.1.1", 5353,
-                /* subtype= */ "ABCDE",
+                "service-instance-1", "192.168.1.1", 5353, SUBTYPE,
                 Collections.emptyMap(), TEST_TTL), socketKey);
 
         startSendAndReceive(mockListenerOne, MdnsSearchOptions.getDefaultOptions());
@@ -820,7 +874,7 @@
                 List.of("192.168.1.1") /* ipv4Address */,
                 List.of() /* ipv6Address */,
                 5353 /* port */,
-                Collections.singletonList("ABCDE") /* subTypes */,
+                Collections.singletonList(SUBTYPE) /* subTypes */,
                 Collections.singletonMap("key", null) /* attributes */,
                 socketKey);
 
@@ -830,7 +884,7 @@
         assertEquals(existingServiceInfo.getServiceInstanceName(), "service-instance-1");
         assertEquals(existingServiceInfo.getIpv4Address(), "192.168.1.1");
         assertEquals(existingServiceInfo.getPort(), 5353);
-        assertEquals(existingServiceInfo.getSubtypes(), Collections.singletonList("ABCDE"));
+        assertEquals(existingServiceInfo.getSubtypes(), Collections.singletonList(SUBTYPE));
         assertNull(existingServiceInfo.getAttributeByKey("key"));
 
         // Process a goodbye message for the existing response.
@@ -853,7 +907,8 @@
         final String serviceInstanceName = "service-instance-1";
         client =
                 new MdnsServiceTypeClient(SERVICE_TYPE, mockSocketClient, currentThreadExecutor,
-                        mockDecoderClock, socketKey, mockSharedLog, thread.getLooper()) {
+                        mockDecoderClock, socketKey, mockSharedLog, thread.getLooper(), mockDeps,
+                        serviceCache) {
                     @Override
                     MdnsPacketWriter createMdnsPacketWriter() {
                         return mockPacketWriter;
@@ -868,7 +923,7 @@
 
         // Process the initial response.
         processResponse(createResponse(
-                serviceInstanceName, "192.168.1.1", 5353, /* subtype= */ "ABCDE",
+                serviceInstanceName, "192.168.1.1", 5353, SUBTYPE,
                 Collections.emptyMap(), TEST_TTL), socketKey);
 
         // Clear the scheduled runnable.
@@ -877,6 +932,7 @@
         // Simulate the case where the response is under TTL.
         doReturn(TEST_ELAPSED_REALTIME + TEST_TTL - 1L).when(mockDecoderClock).elapsedRealtime();
         firstMdnsTask.run();
+        verify(mockDeps, times(1)).sendMessage(any(), any(Message.class));
 
         // Verify removed callback was not called.
         verifyServiceRemovedNoCallback(mockListenerOne);
@@ -884,6 +940,7 @@
         // Simulate the case where the response is after TTL.
         doReturn(TEST_ELAPSED_REALTIME + TEST_TTL + 1L).when(mockDecoderClock).elapsedRealtime();
         firstMdnsTask.run();
+        verify(mockDeps, times(2)).sendMessage(any(), any(Message.class));
 
         // Verify removed callback was called.
         verifyServiceRemovedCallback(
@@ -896,7 +953,8 @@
         final String serviceInstanceName = "service-instance-1";
         client =
                 new MdnsServiceTypeClient(SERVICE_TYPE, mockSocketClient, currentThreadExecutor,
-                        mockDecoderClock, socketKey, mockSharedLog, thread.getLooper()) {
+                        mockDecoderClock, socketKey, mockSharedLog, thread.getLooper(), mockDeps,
+                        serviceCache) {
                     @Override
                     MdnsPacketWriter createMdnsPacketWriter() {
                         return mockPacketWriter;
@@ -907,7 +965,7 @@
 
         // Process the initial response.
         processResponse(createResponse(
-                serviceInstanceName, "192.168.1.1", 5353, /* subtype= */ "ABCDE",
+                serviceInstanceName, "192.168.1.1", 5353, SUBTYPE,
                 Collections.emptyMap(), TEST_TTL), socketKey);
 
         // Clear the scheduled runnable.
@@ -929,7 +987,8 @@
         final String serviceInstanceName = "service-instance-1";
         client =
                 new MdnsServiceTypeClient(SERVICE_TYPE, mockSocketClient, currentThreadExecutor,
-                        mockDecoderClock, socketKey, mockSharedLog, thread.getLooper()) {
+                        mockDecoderClock, socketKey, mockSharedLog, thread.getLooper(), mockDeps,
+                        serviceCache) {
                     @Override
                     MdnsPacketWriter createMdnsPacketWriter() {
                         return mockPacketWriter;
@@ -940,7 +999,7 @@
 
         // Process the initial response.
         processResponse(createResponse(
-                serviceInstanceName, "192.168.1.1", 5353, /* subtype= */ "ABCDE",
+                serviceInstanceName, "192.168.1.1", 5353, SUBTYPE,
                 Collections.emptyMap(), TEST_TTL), socketKey);
 
         // Clear the scheduled runnable.
@@ -964,19 +1023,18 @@
         InOrder inOrder = inOrder(mockListenerOne);
 
         // Process the initial response which is incomplete.
-        final String subtype = "ABCDE";
         processResponse(createResponse(
-                serviceName, null, 5353, subtype,
+                serviceName, null, 5353, SUBTYPE,
                 Collections.emptyMap(), TEST_TTL), socketKey);
 
         // Process a second response which has ip address to make response become complete.
         processResponse(createResponse(
-                serviceName, ipV4Address, 5353, subtype,
+                serviceName, ipV4Address, 5353, SUBTYPE,
                 Collections.emptyMap(), TEST_TTL), socketKey);
 
         // Process a third response with a different ip address, port and updated text attributes.
         processResponse(createResponse(
-                serviceName, ipV6Address, 5354, subtype,
+                serviceName, ipV6Address, 5354, SUBTYPE,
                 Collections.singletonMap("key", "value"), TEST_TTL), socketKey);
 
         // Process the last response which is goodbye message (with the main type, not subtype).
@@ -993,7 +1051,7 @@
                 List.of() /* ipv4Address */,
                 List.of() /* ipv6Address */,
                 5353 /* port */,
-                Collections.singletonList(subtype) /* subTypes */,
+                Collections.singletonList(SUBTYPE) /* subTypes */,
                 Collections.singletonMap("key", null) /* attributes */,
                 socketKey);
 
@@ -1005,7 +1063,7 @@
                 List.of(ipV4Address) /* ipv4Address */,
                 List.of() /* ipv6Address */,
                 5353 /* port */,
-                Collections.singletonList(subtype) /* subTypes */,
+                Collections.singletonList(SUBTYPE) /* subTypes */,
                 Collections.singletonMap("key", null) /* attributes */,
                 socketKey);
 
@@ -1017,7 +1075,7 @@
                 List.of(ipV4Address) /* ipv4Address */,
                 List.of(ipV6Address) /* ipv6Address */,
                 5354 /* port */,
-                Collections.singletonList(subtype) /* subTypes */,
+                Collections.singletonList(SUBTYPE) /* subTypes */,
                 Collections.singletonMap("key", "value") /* attributes */,
                 socketKey);
 
@@ -1029,7 +1087,7 @@
                 List.of(ipV4Address) /* ipv4Address */,
                 List.of(ipV6Address) /* ipv6Address */,
                 5354 /* port */,
-                Collections.singletonList("ABCDE") /* subTypes */,
+                Collections.singletonList(SUBTYPE) /* subTypes */,
                 Collections.singletonMap("key", "value") /* attributes */,
                 socketKey);
 
@@ -1041,7 +1099,7 @@
                 List.of(ipV4Address) /* ipv4Address */,
                 List.of(ipV6Address) /* ipv6Address */,
                 5354 /* port */,
-                Collections.singletonList("ABCDE") /* subTypes */,
+                Collections.singletonList(SUBTYPE) /* subTypes */,
                 Collections.singletonMap("key", "value") /* attributes */,
                 socketKey);
     }
@@ -1049,7 +1107,8 @@
     @Test
     public void testProcessResponse_Resolve() throws Exception {
         client = new MdnsServiceTypeClient(SERVICE_TYPE, mockSocketClient, currentThreadExecutor,
-                socketKey, mockSharedLog, thread.getLooper());
+                mockDecoderClock, socketKey, mockSharedLog, thread.getLooper(), mockDeps,
+                serviceCache);
 
         final String instanceName = "service-instance";
         final String[] hostname = new String[] { "testhost "};
@@ -1070,6 +1129,8 @@
         inOrder.verify(mockSocketClient, times(2)).sendPacketRequestingUnicastResponse(
                 srvTxtQueryCaptor.capture(),
                 eq(socketKey), eq(false));
+        verify(mockDeps, times(1)).sendMessage(any(), any(Message.class));
+        assertNotNull(delayMessage);
 
         final MdnsPacket srvTxtQueryPacket = MdnsPacket.parse(
                 new MdnsPacketReader(srvTxtQueryCaptor.getValue()));
@@ -1095,6 +1156,7 @@
         processResponse(srvTxtResponse, socketKey);
 
         // Expect a query for A/AAAA
+        dispatchMessage();
         final ArgumentCaptor<DatagramPacket> addressQueryCaptor =
                 ArgumentCaptor.forClass(DatagramPacket.class);
         currentThreadExecutor.getAndClearLastScheduledRunnable().run();
@@ -1139,7 +1201,8 @@
     @Test
     public void testRenewTxtSrvInResolve() throws Exception {
         client = new MdnsServiceTypeClient(SERVICE_TYPE, mockSocketClient, currentThreadExecutor,
-                mockDecoderClock, socketKey, mockSharedLog, thread.getLooper());
+                mockDecoderClock, socketKey, mockSharedLog, thread.getLooper(), mockDeps,
+                serviceCache);
 
         final String instanceName = "service-instance";
         final String[] hostname = new String[] { "testhost "};
@@ -1160,6 +1223,8 @@
         inOrder.verify(mockSocketClient, times(2)).sendPacketRequestingUnicastResponse(
                 srvTxtQueryCaptor.capture(),
                 eq(socketKey), eq(false));
+        verify(mockDeps, times(1)).sendMessage(any(), any(Message.class));
+        assertNotNull(delayMessage);
 
         final MdnsPacket srvTxtQueryPacket = MdnsPacket.parse(
                 new MdnsPacketReader(srvTxtQueryCaptor.getValue()));
@@ -1187,6 +1252,7 @@
                 Collections.emptyList() /* authorityRecords */,
                 Collections.emptyList() /* additionalRecords */);
         processResponse(srvTxtResponse, socketKey);
+        dispatchMessage();
         inOrder.verify(mockListenerOne).onServiceNameDiscovered(any());
         inOrder.verify(mockListenerOne).onServiceFound(any());
 
@@ -1197,6 +1263,9 @@
         // Advance time so 75% of TTL passes and re-execute
         doReturn(TEST_ELAPSED_REALTIME + (long) (TEST_TTL * 0.75))
                 .when(mockDecoderClock).elapsedRealtime();
+        verify(mockDeps, times(2)).sendMessage(any(), any(Message.class));
+        assertNotNull(delayMessage);
+        dispatchMessage();
         currentThreadExecutor.getAndClearLastScheduledRunnable().run();
 
         // Expect a renewal query
@@ -1206,6 +1275,8 @@
         inOrder.verify(mockSocketClient, times(2)).sendPacketRequestingMulticastResponse(
                 renewalQueryCaptor.capture(),
                 eq(socketKey), eq(false));
+        verify(mockDeps, times(3)).sendMessage(any(), any(Message.class));
+        assertNotNull(delayMessage);
         inOrder.verify(mockListenerOne).onDiscoveryQuerySent(any(), anyInt());
         final MdnsPacket renewalPacket = MdnsPacket.parse(
                 new MdnsPacketReader(renewalQueryCaptor.getValue()));
@@ -1232,6 +1303,7 @@
                 Collections.emptyList() /* authorityRecords */,
                 Collections.emptyList() /* additionalRecords */);
         processResponse(refreshedSrvTxtResponse, socketKey);
+        dispatchMessage();
 
         // Advance time to updatedReceiptTime + 1, expected no refresh query because the cache
         // should contain the record that have update last receipt time.
@@ -1243,7 +1315,8 @@
     @Test
     public void testProcessResponse_ResolveExcludesOtherServices() {
         client = new MdnsServiceTypeClient(SERVICE_TYPE, mockSocketClient, currentThreadExecutor,
-                socketKey, mockSharedLog, thread.getLooper());
+                mockDecoderClock, socketKey, mockSharedLog, thread.getLooper(), mockDeps,
+                serviceCache);
 
         final String requestedInstance = "instance1";
         final String otherInstance = "instance2";
@@ -1307,7 +1380,8 @@
     @Test
     public void testProcessResponse_SubtypeDiscoveryLimitedToSubtype() {
         client = new MdnsServiceTypeClient(SERVICE_TYPE, mockSocketClient, currentThreadExecutor,
-                socketKey, mockSharedLog, thread.getLooper());
+                mockDecoderClock, socketKey, mockSharedLog, thread.getLooper(), mockDeps,
+                serviceCache);
 
         final String matchingInstance = "instance1";
         final String subtype = "_subtype";
@@ -1388,7 +1462,8 @@
     @Test
     public void testNotifySocketDestroyed() throws Exception {
         client = new MdnsServiceTypeClient(SERVICE_TYPE, mockSocketClient, currentThreadExecutor,
-                socketKey, mockSharedLog, thread.getLooper());
+                mockDecoderClock, socketKey, mockSharedLog, thread.getLooper(), mockDeps,
+                serviceCache);
 
         final String requestedInstance = "instance1";
         final String otherInstance = "instance2";
@@ -1399,6 +1474,8 @@
                 .setResolveInstanceName("instance1").build();
 
         startSendAndReceive(mockListenerOne, resolveOptions);
+        // Always try to remove the task.
+        verify(mockDeps, times(1)).removeMessages(any(), eq(EVENT_START_QUERYTASK));
         // Ensure the first task is executed so it schedules a future task
         currentThreadExecutor.getAndClearSubmittedFuture().get(
                 TEST_TIMEOUT_MS, TimeUnit.MILLISECONDS);
@@ -1407,7 +1484,7 @@
                         Integer.MAX_VALUE).build());
 
         // Filing the second request cancels the first future
-        verify(expectedSendFutures[0]).cancel(true);
+        verify(mockDeps, times(2)).removeMessages(any(), eq(EVENT_START_QUERYTASK));
 
         // Ensure it gets executed too
         currentThreadExecutor.getAndClearSubmittedFuture().get(
@@ -1425,9 +1502,8 @@
                         Collections.emptyMap() /* textAttributes */, TEST_TTL),
                 socketKey);
 
-        verify(expectedSendFutures[1], never()).cancel(true);
         notifySocketDestroyed();
-        verify(expectedSendFutures[1]).cancel(true);
+        verify(mockDeps, times(3)).removeMessages(any(), eq(EVENT_START_QUERYTASK));
 
         // mockListenerOne gets notified for the requested instance
         final InOrder inOrder1 = inOrder(mockListenerOne);
@@ -1446,12 +1522,106 @@
         inOrder2.verify(mockListenerTwo).onServiceNameDiscovered(
                 matchServiceName(requestedInstance));
         inOrder2.verify(mockListenerTwo).onServiceFound(matchServiceName(requestedInstance));
-        inOrder2.verify(mockListenerTwo).onServiceNameDiscovered(matchServiceName(otherInstance));
-        inOrder2.verify(mockListenerTwo).onServiceFound(matchServiceName(otherInstance));
-        inOrder2.verify(mockListenerTwo).onServiceRemoved(matchServiceName(otherInstance));
-        inOrder2.verify(mockListenerTwo).onServiceNameRemoved(matchServiceName(otherInstance));
         inOrder2.verify(mockListenerTwo).onServiceRemoved(matchServiceName(requestedInstance));
         inOrder2.verify(mockListenerTwo).onServiceNameRemoved(matchServiceName(requestedInstance));
+        verify(mockListenerTwo).onServiceNameDiscovered(matchServiceName(otherInstance));
+        verify(mockListenerTwo).onServiceFound(matchServiceName(otherInstance));
+        verify(mockListenerTwo).onServiceRemoved(matchServiceName(otherInstance));
+        verify(mockListenerTwo).onServiceNameRemoved(matchServiceName(otherInstance));
+    }
+
+    @Test
+    public void testServicesAreCached() throws Exception {
+        final String serviceName = "service-instance";
+        final String ipV4Address = "192.0.2.0";
+        // Register a listener
+        startSendAndReceive(mockListenerOne, MdnsSearchOptions.getDefaultOptions());
+        verify(mockDeps, times(1)).removeMessages(any(), eq(EVENT_START_QUERYTASK));
+        InOrder inOrder = inOrder(mockListenerOne);
+
+        // Process a response which has ip address to make response become complete.
+
+        processResponse(createResponse(
+                        serviceName, ipV4Address, 5353, SUBTYPE,
+                        Collections.emptyMap(), TEST_TTL),
+                socketKey);
+
+        // Verify that onServiceNameDiscovered is called.
+        inOrder.verify(mockListenerOne).onServiceNameDiscovered(serviceInfoCaptor.capture());
+        verifyServiceInfo(serviceInfoCaptor.getAllValues().get(0),
+                serviceName,
+                SERVICE_TYPE_LABELS,
+                List.of(ipV4Address) /* ipv4Address */,
+                List.of() /* ipv6Address */,
+                5353 /* port */,
+                Collections.singletonList(SUBTYPE) /* subTypes */,
+                Collections.singletonMap("key", null) /* attributes */,
+                socketKey);
+
+        // Verify that onServiceFound is called.
+        inOrder.verify(mockListenerOne).onServiceFound(serviceInfoCaptor.capture());
+        verifyServiceInfo(serviceInfoCaptor.getAllValues().get(1),
+                serviceName,
+                SERVICE_TYPE_LABELS,
+                List.of(ipV4Address) /* ipv4Address */,
+                List.of() /* ipv6Address */,
+                5353 /* port */,
+                Collections.singletonList(SUBTYPE) /* subTypes */,
+                Collections.singletonMap("key", null) /* attributes */,
+                socketKey);
+
+        // Unregister the listener
+        stopSendAndReceive(mockListenerOne);
+        verify(mockDeps, times(2)).removeMessages(any(), eq(EVENT_START_QUERYTASK));
+
+        // Register another listener.
+        startSendAndReceive(mockListenerTwo, MdnsSearchOptions.getDefaultOptions());
+        verify(mockDeps, times(3)).removeMessages(any(), eq(EVENT_START_QUERYTASK));
+        InOrder inOrder2 = inOrder(mockListenerTwo);
+
+        // The services are cached in MdnsServiceCache, verify that onServiceNameDiscovered is
+        // called immediately.
+        inOrder2.verify(mockListenerTwo).onServiceNameDiscovered(serviceInfoCaptor.capture());
+        verifyServiceInfo(serviceInfoCaptor.getAllValues().get(2),
+                serviceName,
+                SERVICE_TYPE_LABELS,
+                List.of(ipV4Address) /* ipv4Address */,
+                List.of() /* ipv6Address */,
+                5353 /* port */,
+                Collections.singletonList(SUBTYPE) /* subTypes */,
+                Collections.singletonMap("key", null) /* attributes */,
+                socketKey);
+
+        // The services are cached in MdnsServiceCache, verify that onServiceFound is
+        // called immediately.
+        inOrder2.verify(mockListenerTwo).onServiceFound(serviceInfoCaptor.capture());
+        verifyServiceInfo(serviceInfoCaptor.getAllValues().get(3),
+                serviceName,
+                SERVICE_TYPE_LABELS,
+                List.of(ipV4Address) /* ipv4Address */,
+                List.of() /* ipv6Address */,
+                5353 /* port */,
+                Collections.singletonList(SUBTYPE) /* subTypes */,
+                Collections.singletonMap("key", null) /* attributes */,
+                socketKey);
+
+        // Process a response with a different ip address, port and updated text attributes.
+        final String ipV6Address = "2001:db8::";
+        processResponse(createResponse(
+                serviceName, ipV6Address, 5354, SUBTYPE,
+                Collections.singletonMap("key", "value"), TEST_TTL), socketKey);
+
+        // Verify the onServiceUpdated is called.
+        inOrder2.verify(mockListenerTwo).onServiceUpdated(serviceInfoCaptor.capture());
+        verifyServiceInfo(serviceInfoCaptor.getAllValues().get(4),
+                serviceName,
+                SERVICE_TYPE_LABELS,
+                List.of(ipV4Address) /* ipv4Address */,
+                List.of(ipV6Address) /* ipv6Address */,
+                5354 /* port */,
+                Collections.singletonList(SUBTYPE) /* subTypes */,
+                Collections.singletonMap("key", "value") /* attributes */,
+                socketKey);
     }
 
     private static MdnsServiceInfo matchServiceName(String name) {
@@ -1461,13 +1631,17 @@
     // verifies that the right query was enqueued with the right delay, and send query by executing
     // the runnable.
     private void verifyAndSendQuery(int index, long timeInMs, boolean expectsUnicastResponse) {
-        verifyAndSendQuery(
-                index, timeInMs, expectsUnicastResponse, true /* multipleSocketDiscovery */);
+        verifyAndSendQuery(index, timeInMs, expectsUnicastResponse,
+                true /* multipleSocketDiscovery */, index + 1 /* scheduledCount */);
     }
 
     private void verifyAndSendQuery(int index, long timeInMs, boolean expectsUnicastResponse,
-            boolean multipleSocketDiscovery) {
-        assertEquals(timeInMs, currentThreadExecutor.getAndClearLastScheduledDelayInMs());
+            boolean multipleSocketDiscovery, int scheduledCount) {
+        // Dispatch the message
+        if (delayMessage != null && realHandler != null) {
+            dispatchMessage();
+        }
+        assertEquals(timeInMs, latestDelayMs);
         currentThreadExecutor.getAndClearLastScheduledRunnable().run();
         if (expectsUnicastResponse) {
             verify(mockSocketClient).sendPacketRequestingUnicastResponse(
@@ -1484,6 +1658,11 @@
                         expectedIPv6Packets[index], socketKey, false);
             }
         }
+        verify(mockDeps, times(index + 1))
+                .sendMessage(any(Handler.class), any(Message.class));
+        // Verify the task has been scheduled.
+        verify(mockDeps, times(scheduledCount))
+                .sendMessageDelayed(any(Handler.class), any(Message.class), anyLong());
     }
 
     private static String[] getTestServiceName(String instanceName) {
@@ -1528,7 +1707,7 @@
         public ScheduledFuture<?> schedule(Runnable command, long delay, TimeUnit unit) {
             lastScheduledDelayInMs = delay;
             lastScheduledRunnable = command;
-            return expectedSendFutures[futureIndex++];
+            return Mockito.mock(ScheduledFuture.class);
         }
 
         // Returns the delay of the last scheduled task, and clear it.
@@ -1556,10 +1735,6 @@
             lastSubmittedFuture = null;
             return val;
         }
-
-        public int getNumOfScheduledFuture() {
-            return futureIndex - 1;
-        }
     }
 
     private MdnsPacket createResponse(