diff --git a/framework-t/src/android/net/nsd/NsdManager.java b/framework-t/src/android/net/nsd/NsdManager.java
index d119db6..2930cbd 100644
--- a/framework-t/src/android/net/nsd/NsdManager.java
+++ b/framework-t/src/android/net/nsd/NsdManager.java
@@ -429,6 +429,10 @@
             private final DiscoveryListener mWrapped;
             private final Executor mWrappedExecutor;
             private final ArraySet<TrackedNsdInfo> mFoundInfo = new ArraySet<>();
+            // When this flag is set to true, no further service found or lost callbacks should be
+            // handled. This flag indicates that the network for this DelegatingDiscoveryListener is
+            // lost, and any further callbacks would be redundant.
+            private boolean mAllServicesLost = false;
 
             private DelegatingDiscoveryListener(Network network, DiscoveryListener listener,
                     Executor executor) {
@@ -445,6 +449,7 @@
                     serviceInfo.setNetwork(mNetwork);
                     mWrappedExecutor.execute(() -> mWrapped.onServiceLost(serviceInfo));
                 }
+                mAllServicesLost = true;
             }
 
             @Override
@@ -486,12 +491,22 @@
 
             @Override
             public void onServiceFound(NsdServiceInfo serviceInfo) {
+                if (mAllServicesLost) {
+                    // This DelegatingDiscoveryListener no longer has a network connection. Ignore
+                    // the callback.
+                    return;
+                }
                 mFoundInfo.add(new TrackedNsdInfo(serviceInfo));
                 mWrappedExecutor.execute(() -> mWrapped.onServiceFound(serviceInfo));
             }
 
             @Override
             public void onServiceLost(NsdServiceInfo serviceInfo) {
+                if (mAllServicesLost) {
+                    // This DelegatingDiscoveryListener no longer has a network connection. Ignore
+                    // the callback.
+                    return;
+                }
                 mFoundInfo.remove(new TrackedNsdInfo(serviceInfo));
                 mWrappedExecutor.execute(() -> mWrapped.onServiceLost(serviceInfo));
             }
diff --git a/service-t/src/com/android/server/NsdService.java b/service-t/src/com/android/server/NsdService.java
index c136d4c..4af4c6a 100644
--- a/service-t/src/com/android/server/NsdService.java
+++ b/service-t/src/com/android/server/NsdService.java
@@ -55,6 +55,7 @@
 import android.os.UserHandle;
 import android.text.TextUtils;
 import android.util.Log;
+import android.util.Pair;
 import android.util.SparseArray;
 
 import com.android.internal.annotations.VisibleForTesting;
@@ -599,7 +600,10 @@
 
                         final NsdServiceInfo info = args.serviceInfo;
                         id = getUniqueId();
-                        final String serviceType = constructServiceType(info.getServiceType());
+                        final Pair<String, String> typeAndSubtype =
+                                parseTypeAndSubtype(info.getServiceType());
+                        final String serviceType = typeAndSubtype == null
+                                ? null : typeAndSubtype.first;
                         if (clientInfo.mUseJavaBackend
                                 || mDeps.isMdnsDiscoveryManagerEnabled(mContext)
                                 || useDiscoveryManagerForType(serviceType)) {
@@ -613,12 +617,17 @@
                             maybeStartMonitoringSockets();
                             final MdnsListener listener =
                                     new DiscoveryListener(clientId, id, info, listenServiceType);
-                            final MdnsSearchOptions options = MdnsSearchOptions.newBuilder()
-                                    .setNetwork(info.getNetwork())
-                                    .setIsPassiveMode(true)
-                                    .build();
+                            final MdnsSearchOptions.Builder optionsBuilder =
+                                    MdnsSearchOptions.newBuilder()
+                                            .setNetwork(info.getNetwork())
+                                            .setIsPassiveMode(true);
+                            if (typeAndSubtype.second != null) {
+                                // The parsing ensures subtype starts with an underscore.
+                                // MdnsSearchOptions expects the underscore to not be present.
+                                optionsBuilder.addSubtype(typeAndSubtype.second.substring(1));
+                            }
                             mMdnsDiscoveryManager.registerListener(
-                                    listenServiceType, listener, options);
+                                    listenServiceType, listener, optionsBuilder.build());
                             storeDiscoveryManagerRequestMap(clientId, id, listener, clientInfo);
                             clientInfo.onDiscoverServicesStarted(clientId, info);
                             clientInfo.log("Register a DiscoveryListener " + id
@@ -697,7 +706,9 @@
                         id = getUniqueId();
                         final NsdServiceInfo serviceInfo = args.serviceInfo;
                         final String serviceType = serviceInfo.getServiceType();
-                        final String registerServiceType = constructServiceType(serviceType);
+                        final Pair<String, String> typeSubtype = parseTypeAndSubtype(serviceType);
+                        final String registerServiceType = typeSubtype == null
+                                ? null : typeSubtype.first;
                         if (clientInfo.mUseJavaBackend
                                 || mDeps.isMdnsAdvertiserEnabled(mContext)
                                 || useAdvertiserForType(registerServiceType)) {
@@ -712,7 +723,11 @@
                                     serviceInfo.getServiceName()));
 
                             maybeStartMonitoringSockets();
-                            mAdvertiser.addService(id, serviceInfo);
+                            // TODO: pass in the subtype as well. Including the subtype in the
+                            // service type would generate service instance names like
+                            // Name._subtype._sub._type._tcp, which is incorrect
+                            // (it should be Name._type._tcp).
+                            mAdvertiser.addService(id, serviceInfo, typeSubtype.second);
                             storeAdvertiserRequestMap(clientId, id, clientInfo);
                         } else {
                             maybeStartDaemon();
@@ -778,7 +793,10 @@
 
                         final NsdServiceInfo info = args.serviceInfo;
                         id = getUniqueId();
-                        final String serviceType = constructServiceType(info.getServiceType());
+                        final Pair<String, String> typeSubtype =
+                                parseTypeAndSubtype(info.getServiceType());
+                        final String serviceType = typeSubtype == null
+                                ? null : typeSubtype.first;
                         if (clientInfo.mUseJavaBackend
                                 ||  mDeps.isMdnsDiscoveryManagerEnabled(mContext)
                                 || useDiscoveryManagerForType(serviceType)) {
@@ -871,7 +889,10 @@
 
                         final NsdServiceInfo info = args.serviceInfo;
                         id = getUniqueId();
-                        final String serviceType = constructServiceType(info.getServiceType());
+                        final Pair<String, String> typeAndSubtype =
+                                parseTypeAndSubtype(info.getServiceType());
+                        final String serviceType = typeAndSubtype == null
+                                ? null : typeAndSubtype.first;
                         if (serviceType == null) {
                             clientInfo.onServiceInfoCallbackRegistrationFailed(clientId,
                                     NsdManager.FAILURE_BAD_PARAMETERS);
@@ -1315,28 +1336,39 @@
      * Check the given service type is valid and construct it to a service type
      * which can use for discovery / resolution service.
      *
-     * <p> The valid service type should be 2 labels, or 3 labels if the query is for a
+     * <p>The valid service type should be 2 labels, or 3 labels if the query is for a
      * subtype (see RFC6763 7.1). Each label is up to 63 characters and must start with an
      * underscore; they are alphanumerical characters or dashes or underscore, except the
      * last one that is just alphanumerical. The last label must be _tcp or _udp.
      *
+     * <p>The subtype may also be specified with a comma after the service type, for example
+     * _type._tcp,_subtype.
+     *
      * @param serviceType the request service type for discovery / resolution service
      * @return constructed service type or null if the given service type is invalid.
      */
     @Nullable
-    public static String constructServiceType(String serviceType) {
+    public static Pair<String, String> parseTypeAndSubtype(String serviceType) {
         if (TextUtils.isEmpty(serviceType)) return null;
 
+        final String typeOrSubtypePattern = "_[a-zA-Z0-9-_]{1,61}[a-zA-Z0-9]";
         final Pattern serviceTypePattern = Pattern.compile(
-                "^(_[a-zA-Z0-9-_]{1,61}[a-zA-Z0-9]\\.)?"
-                        + "(_[a-zA-Z0-9-_]{1,61}[a-zA-Z0-9]\\._(?:tcp|udp))"
+                // Optional leading subtype (_subtype._type._tcp)
+                // (?: xxx) is a non-capturing parenthesis, don't capture the dot
+                "^(?:(" + typeOrSubtypePattern + ")\\.)?"
+                        // Actual type (_type._tcp.local)
+                        + "(" + typeOrSubtypePattern + "\\._(?:tcp|udp))"
                         // Drop '.' at the end of service type that is compatible with old backend.
-                        + "\\.?$");
+                        // e.g. allow "_type._tcp.local."
+                        + "\\.?"
+                        // Optional subtype after comma, for "_type._tcp,_subtype" format
+                        + "(?:,(" + typeOrSubtypePattern + "))?"
+                        + "$");
         final Matcher matcher = serviceTypePattern.matcher(serviceType);
         if (!matcher.matches()) return null;
-        return matcher.group(1) == null
-                ? matcher.group(2)
-                : matcher.group(1) + "_sub." + matcher.group(2);
+        // Use the subtype either at the beginning or after the comma
+        final String subtype = matcher.group(1) != null ? matcher.group(1) : matcher.group(3);
+        return new Pair<>(matcher.group(2), subtype);
     }
 
     @VisibleForTesting
diff --git a/service-t/src/com/android/server/connectivity/mdns/MdnsAdvertiser.java b/service-t/src/com/android/server/connectivity/mdns/MdnsAdvertiser.java
index 655c364..cc08ea1 100644
--- a/service-t/src/com/android/server/connectivity/mdns/MdnsAdvertiser.java
+++ b/service-t/src/com/android/server/connectivity/mdns/MdnsAdvertiser.java
@@ -270,7 +270,8 @@
             mPendingRegistrations.put(id, registration);
             for (int i = 0; i < mAdvertisers.size(); i++) {
                 try {
-                    mAdvertisers.valueAt(i).addService(id, registration.getServiceInfo());
+                    mAdvertisers.valueAt(i).addService(
+                            id, registration.getServiceInfo(), registration.getSubtype());
                 } catch (NameConflictException e) {
                     Log.wtf(TAG, "Name conflict adding services that should have unique names", e);
                 }
@@ -298,9 +299,10 @@
             }
             mAdvertisers.put(socket, advertiser);
             for (int i = 0; i < mPendingRegistrations.size(); i++) {
+                final Registration registration = mPendingRegistrations.valueAt(i);
                 try {
                     advertiser.addService(mPendingRegistrations.keyAt(i),
-                            mPendingRegistrations.valueAt(i).getServiceInfo());
+                            registration.getServiceInfo(), registration.getSubtype());
                 } catch (NameConflictException e) {
                     Log.wtf(TAG, "Name conflict adding services that should have unique names", e);
                 }
@@ -329,10 +331,13 @@
         private int mConflictCount;
         @NonNull
         private NsdServiceInfo mServiceInfo;
+        @Nullable
+        private final String mSubtype;
 
-        private Registration(@NonNull NsdServiceInfo serviceInfo) {
+        private Registration(@NonNull NsdServiceInfo serviceInfo, @Nullable String subtype) {
             this.mOriginalName = serviceInfo.getServiceName();
             this.mServiceInfo = serviceInfo;
+            this.mSubtype = subtype;
         }
 
         /**
@@ -387,6 +392,11 @@
         public NsdServiceInfo getServiceInfo() {
             return mServiceInfo;
         }
+
+        @Nullable
+        public String getSubtype() {
+            return mSubtype;
+        }
     }
 
     /**
@@ -443,8 +453,9 @@
      * Add a service to advertise.
      * @param id A unique ID for the service.
      * @param service The service info to advertise.
+     * @param subtype An optional subtype to advertise the service with.
      */
-    public void addService(int id, NsdServiceInfo service) {
+    public void addService(int id, NsdServiceInfo service, @Nullable String subtype) {
         checkThread();
         if (mRegistrations.get(id) != null) {
             Log.e(TAG, "Adding duplicate registration for " + service);
@@ -453,10 +464,10 @@
             return;
         }
 
-        mSharedLog.i("Adding service " + service + " with ID " + id);
+        mSharedLog.i("Adding service " + service + " with ID " + id + " and subtype " + subtype);
 
         final Network network = service.getNetwork();
-        final Registration registration = new Registration(service);
+        final Registration registration = new Registration(service, subtype);
         final BiPredicate<Network, InterfaceAdvertiserRequest> checkConflictFilter;
         if (network == null) {
             // If registering on all networks, no advertiser must have conflicts
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 849eac1..6455044 100644
--- a/service-t/src/com/android/server/connectivity/mdns/MdnsDiscoveryManager.java
+++ b/service-t/src/com/android/server/connectivity/mdns/MdnsDiscoveryManager.java
@@ -135,18 +135,36 @@
             }
         }
         // Request the network for discovery.
-        socketClient.notifyNetworkRequested(listener, searchOptions.getNetwork(), network -> {
-            synchronized (this) {
-                // All listeners of the same service types shares the same MdnsServiceTypeClient.
-                MdnsServiceTypeClient serviceTypeClient =
-                        perNetworkServiceTypeClients.get(serviceType, network);
-                if (serviceTypeClient == null) {
-                    serviceTypeClient = createServiceTypeClient(serviceType, network);
-                    perNetworkServiceTypeClients.put(serviceType, network, serviceTypeClient);
-                }
-                serviceTypeClient.startSendAndReceive(listener, searchOptions);
-            }
-        });
+        socketClient.notifyNetworkRequested(listener, searchOptions.getNetwork(),
+                new MdnsSocketClientBase.SocketCreationCallback() {
+                    @Override
+                    public void onSocketCreated(@Nullable Network network) {
+                        synchronized (MdnsDiscoveryManager.this) {
+                            // All listeners of the same service types shares the same
+                            // MdnsServiceTypeClient.
+                            MdnsServiceTypeClient serviceTypeClient =
+                                    perNetworkServiceTypeClients.get(serviceType, network);
+                            if (serviceTypeClient == null) {
+                                serviceTypeClient = createServiceTypeClient(serviceType, network);
+                                perNetworkServiceTypeClients.put(serviceType, network,
+                                        serviceTypeClient);
+                            }
+                            serviceTypeClient.startSendAndReceive(listener, searchOptions);
+                        }
+                    }
+
+                    @Override
+                    public void onSocketDestroyed(@Nullable Network network) {
+                        synchronized (MdnsDiscoveryManager.this) {
+                            final MdnsServiceTypeClient serviceTypeClient =
+                                    perNetworkServiceTypeClients.get(serviceType, network);
+                            if (serviceTypeClient == null) return;
+                            // Notify all listeners that all services are removed from this socket.
+                            serviceTypeClient.notifyAllServicesRemoved();
+                            perNetworkServiceTypeClients.remove(serviceTypeClient);
+                        }
+                    }
+                });
     }
 
     /**
diff --git a/service-t/src/com/android/server/connectivity/mdns/MdnsInterfaceAdvertiser.java b/service-t/src/com/android/server/connectivity/mdns/MdnsInterfaceAdvertiser.java
index 4e09515..724a704 100644
--- a/service-t/src/com/android/server/connectivity/mdns/MdnsInterfaceAdvertiser.java
+++ b/service-t/src/com/android/server/connectivity/mdns/MdnsInterfaceAdvertiser.java
@@ -212,8 +212,9 @@
      *
      * @throws NameConflictException There is already a service being advertised with that name.
      */
-    public void addService(int id, NsdServiceInfo service) throws NameConflictException {
-        final int replacedExitingService = mRecordRepository.addService(id, service);
+    public void addService(int id, NsdServiceInfo service, @Nullable String subtype)
+            throws NameConflictException {
+        final int replacedExitingService = mRecordRepository.addService(id, service, subtype);
         // Cancel announcements for the existing service. This only happens for exiting services
         // (so cancelling exiting announcements), as per RecordRepository.addService.
         if (replacedExitingService >= 0) {
diff --git a/service-t/src/com/android/server/connectivity/mdns/MdnsMultinetworkSocketClient.java b/service-t/src/com/android/server/connectivity/mdns/MdnsMultinetworkSocketClient.java
index 4504bb6..6414453 100644
--- a/service-t/src/com/android/server/connectivity/mdns/MdnsMultinetworkSocketClient.java
+++ b/service-t/src/com/android/server/connectivity/mdns/MdnsMultinetworkSocketClient.java
@@ -90,6 +90,7 @@
                 @NonNull MdnsInterfaceSocket socket) {
             mSocketPacketHandlers.remove(socket);
             mActiveNetworkSockets.remove(socket);
+            mSocketCreationCallback.onSocketDestroyed(network);
         }
     }
 
diff --git a/service-t/src/com/android/server/connectivity/mdns/MdnsRecordRepository.java b/service-t/src/com/android/server/connectivity/mdns/MdnsRecordRepository.java
index 1329172..f756459 100644
--- a/service-t/src/com/android/server/connectivity/mdns/MdnsRecordRepository.java
+++ b/service-t/src/com/android/server/connectivity/mdns/MdnsRecordRepository.java
@@ -69,6 +69,8 @@
 
     // Top-level domain for link-local queries, as per RFC6762 3.
     private static final String LOCAL_TLD = "local";
+    // Subtype separator as per RFC6763 7.1 (_printer._sub._http._tcp.local)
+    private static final String SUBTYPE_SEPARATOR = "_sub";
 
     // Service type for service enumeration (RFC6763 9.)
     private static final String[] DNS_SD_SERVICE_TYPE =
@@ -156,13 +158,15 @@
         @NonNull
         public final List<RecordInfo<?>> allRecords;
         @NonNull
-        public final RecordInfo<MdnsPointerRecord> ptrRecord;
+        public final List<RecordInfo<MdnsPointerRecord>> ptrRecords;
         @NonNull
         public final RecordInfo<MdnsServiceRecord> srvRecord;
         @NonNull
         public final RecordInfo<MdnsTextRecord> txtRecord;
         @NonNull
         public final NsdServiceInfo serviceInfo;
+        @Nullable
+        public final String subtype;
 
         /**
          * Whether the service is sending exit announcements and will be destroyed soon.
@@ -175,14 +179,16 @@
          * @param deviceHostname Hostname of the device (for the interface used)
          * @param serviceInfo Service to advertise
          */
-        ServiceRegistration(@NonNull String[] deviceHostname, @NonNull NsdServiceInfo serviceInfo) {
+        ServiceRegistration(@NonNull String[] deviceHostname, @NonNull NsdServiceInfo serviceInfo,
+                @Nullable String subtype) {
             this.serviceInfo = serviceInfo;
+            this.subtype = subtype;
 
             final String[] serviceType = splitServiceType(serviceInfo);
             final String[] serviceName = splitFullyQualifiedName(serviceInfo, serviceType);
 
             // Service PTR record
-            ptrRecord = new RecordInfo<>(
+            final RecordInfo<MdnsPointerRecord> ptrRecord = new RecordInfo<>(
                     serviceInfo,
                     new MdnsPointerRecord(
                             serviceType,
@@ -192,6 +198,26 @@
                             serviceName),
                     true /* sharedName */, true /* probing */);
 
+            if (subtype == null) {
+                this.ptrRecords = Collections.singletonList(ptrRecord);
+            } else {
+                final String[] subtypeName = new String[serviceType.length + 2];
+                System.arraycopy(serviceType, 0, subtypeName, 2, serviceType.length);
+                subtypeName[0] = subtype;
+                subtypeName[1] = SUBTYPE_SEPARATOR;
+                final RecordInfo<MdnsPointerRecord> subtypeRecord = new RecordInfo<>(
+                        serviceInfo,
+                        new MdnsPointerRecord(
+                                subtypeName,
+                                0L /* receiptTimeMillis */,
+                                false /* cacheFlush */,
+                                NON_NAME_RECORDS_TTL_MILLIS,
+                                serviceName),
+                        true /* sharedName */, true /* probing */);
+
+                this.ptrRecords = List.of(ptrRecord, subtypeRecord);
+            }
+
             srvRecord = new RecordInfo<>(
                     serviceInfo,
                     new MdnsServiceRecord(serviceName,
@@ -211,8 +237,8 @@
                             attrsToTextEntries(serviceInfo.getAttributes())),
                     false /* sharedName */, true /* probing */);
 
-            final ArrayList<RecordInfo<?>> allRecords = new ArrayList<>(4);
-            allRecords.add(ptrRecord);
+            final ArrayList<RecordInfo<?>> allRecords = new ArrayList<>(5);
+            allRecords.addAll(ptrRecords);
             allRecords.add(srvRecord);
             allRecords.add(txtRecord);
             // Service type enumeration record (RFC6763 9.)
@@ -275,7 +301,8 @@
      *         ID of the replaced service.
      * @throws NameConflictException There is already a (non-exiting) service using the name.
      */
-    public int addService(int serviceId, NsdServiceInfo serviceInfo) throws NameConflictException {
+    public int addService(int serviceId, NsdServiceInfo serviceInfo, @Nullable String subtype)
+            throws NameConflictException {
         if (mServices.contains(serviceId)) {
             throw new IllegalArgumentException(
                     "Service ID must not be reused across registrations: " + serviceId);
@@ -288,7 +315,7 @@
         }
 
         final ServiceRegistration registration = new ServiceRegistration(
-                mDeviceHostname, serviceInfo);
+                mDeviceHostname, serviceInfo, subtype);
         mServices.put(serviceId, registration);
 
         // Remove existing exiting service
@@ -344,24 +371,25 @@
         if (registration == null) return null;
         if (registration.exiting) return null;
 
-        // Send exit (TTL 0) for the PTR record, if the record was sent (in particular don't send
+        // Send exit (TTL 0) for the PTR records, if at least one was sent (in particular don't send
         // if still probing)
-        if (registration.ptrRecord.lastSentTimeMs == 0L) {
+        if (CollectionUtils.all(registration.ptrRecords, r -> r.lastSentTimeMs == 0L)) {
             return null;
         }
 
         registration.exiting = true;
-        final MdnsPointerRecord expiredRecord = new MdnsPointerRecord(
-                registration.ptrRecord.record.getName(),
-                0L /* receiptTimeMillis */,
-                true /* cacheFlush */,
-                0L /* ttlMillis */,
-                registration.ptrRecord.record.getPointer());
+        final List<MdnsRecord> expiredRecords = CollectionUtils.map(registration.ptrRecords,
+                r -> new MdnsPointerRecord(
+                        r.record.getName(),
+                        0L /* receiptTimeMillis */,
+                        true /* cacheFlush */,
+                        0L /* ttlMillis */,
+                        r.record.getPointer()));
 
         // Exit should be skipped if the record is still advertised by another service, but that
         // would be a conflict (2 service registrations with the same service name), so it would
         // not have been allowed by the repository.
-        return new MdnsAnnouncer.ExitAnnouncementInfo(id, Collections.singletonList(expiredRecord));
+        return new MdnsAnnouncer.ExitAnnouncementInfo(id, expiredRecords);
     }
 
     public void removeService(int id) {
@@ -442,7 +470,7 @@
             for (int i = 0; i < mServices.size(); i++) {
                 final ServiceRegistration registration = mServices.valueAt(i);
                 if (registration.exiting) continue;
-                addReplyFromService(question, registration.allRecords, registration.ptrRecord,
+                addReplyFromService(question, registration.allRecords, registration.ptrRecords,
                         registration.srvRecord, registration.txtRecord, replyUnicast, now,
                         answerInfo, additionalAnswerRecords);
             }
@@ -499,7 +527,7 @@
      */
     private void addReplyFromService(@NonNull MdnsRecord question,
             @NonNull List<RecordInfo<?>> serviceRecords,
-            @Nullable RecordInfo<MdnsPointerRecord> servicePtrRecord,
+            @Nullable List<RecordInfo<MdnsPointerRecord>> servicePtrRecords,
             @Nullable RecordInfo<MdnsServiceRecord> serviceSrvRecord,
             @Nullable RecordInfo<MdnsTextRecord> serviceTxtRecord,
             boolean replyUnicast, long now, @NonNull List<RecordInfo<?>> answerInfo,
@@ -531,7 +559,8 @@
             }
 
             hasKnownAnswer = true;
-            hasDnsSdPtrRecordAnswer |= (info == servicePtrRecord);
+            hasDnsSdPtrRecordAnswer |= (servicePtrRecords != null
+                    && CollectionUtils.any(servicePtrRecords, r -> info == r));
             hasDnsSdSrvRecordAnswer |= (info == serviceSrvRecord);
 
             // TODO: responses to probe queries should bypass this check and only ensure the
@@ -791,10 +820,11 @@
      */
     @Nullable
     public MdnsProber.ProbingInfo renameServiceForConflict(int serviceId, NsdServiceInfo newInfo) {
-        if (!mServices.contains(serviceId)) return null;
+        final ServiceRegistration existing = mServices.get(serviceId);
+        if (existing == null) return null;
 
         final ServiceRegistration newService = new ServiceRegistration(
-                mDeviceHostname, newInfo);
+                mDeviceHostname, newInfo, existing.subtype);
         mServices.put(serviceId, newService);
         return makeProbingInfo(serviceId, newService.srvRecord.record);
     }
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 6585d44..4e6571f 100644
--- a/service-t/src/com/android/server/connectivity/mdns/MdnsServiceTypeClient.java
+++ b/service-t/src/com/android/server/connectivity/mdns/MdnsServiceTypeClient.java
@@ -28,13 +28,16 @@
 
 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;
+import com.android.server.connectivity.mdns.util.MdnsUtils;
 
 import java.net.Inet4Address;
 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;
@@ -175,6 +178,7 @@
             @NonNull MdnsSearchOptions searchOptions) {
         synchronized (lock) {
             this.searchOptions = searchOptions;
+            boolean hadReply = false;
             if (listeners.put(listener, searchOptions) == null) {
                 for (MdnsResponse existingResponse : instanceNameToResponse.values()) {
                     if (!responseMatchesOptions(existingResponse, searchOptions)) continue;
@@ -183,6 +187,7 @@
                     listener.onServiceNameDiscovered(info);
                     if (existingResponse.isComplete()) {
                         listener.onServiceFound(info);
+                        hadReply = true;
                     }
                 }
             }
@@ -192,22 +197,37 @@
             }
             // Keep tracking the ScheduledFuture for the task so we can cancel it if caller is not
             // interested anymore.
-            requestTaskFuture =
-                    executor.submit(
-                            new QueryTask(
-                                    new QueryTaskConfig(
-                                            searchOptions.getSubtypes(),
-                                            searchOptions.isPassiveMode(),
-                                            ++currentSessionId,
-                                            searchOptions.getNetwork())));
+            final QueryTaskConfig taskConfig = new QueryTaskConfig(
+                    searchOptions.getSubtypes(),
+                    searchOptions.isPassiveMode(),
+                    ++currentSessionId,
+                    searchOptions.getNetwork());
+            if (hadReply) {
+                requestTaskFuture = scheduleNextRunLocked(taskConfig);
+            } else {
+                requestTaskFuture = executor.submit(new QueryTask(taskConfig));
+            }
         }
     }
 
     private boolean responseMatchesOptions(@NonNull MdnsResponse response,
             @NonNull MdnsSearchOptions options) {
-        if (options.getResolveInstanceName() == null) return true;
-        // DNS is case-insensitive, so ignore case in the comparison
-        return options.getResolveInstanceName().equalsIgnoreCase(response.getServiceInstanceName());
+        final boolean matchesInstanceName = options.getResolveInstanceName() == null
+                // DNS is case-insensitive, so ignore case in the comparison
+                || MdnsUtils.equalsIgnoreDnsCase(options.getResolveInstanceName(),
+                        response.getServiceInstanceName());
+
+        // If discovery is requiring some subtypes, the response must have one that matches a
+        // requested one.
+        final List<String> responseSubtypes = response.getSubtypes() == null
+                ? Collections.emptyList() : response.getSubtypes();
+        final boolean matchesSubtype = options.getSubtypes().size() == 0
+                || CollectionUtils.any(options.getSubtypes(), requiredSub ->
+                CollectionUtils.any(responseSubtypes, actualSub ->
+                        MdnsUtils.equalsIgnoreDnsCase(
+                                MdnsConstants.SUBTYPE_PREFIX + requiredSub, actualSub)));
+
+        return matchesInstanceName && matchesSubtype;
     }
 
     /**
@@ -263,6 +283,28 @@
         }
     }
 
+    /** Notify all services are removed because the socket is destroyed. */
+    public void notifyAllServicesRemoved() {
+        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);
+                }
+            }
+        }
+    }
+
     private void onResponseModified(@NonNull MdnsResponse response) {
         final String serviceInstanceName = response.getServiceInstanceName();
         final MdnsResponse currentResponse =
@@ -552,11 +594,14 @@
                         }
                     }
                 }
-                QueryTaskConfig config = this.config.getConfigForNextRun();
-                requestTaskFuture =
-                        executor.schedule(
-                                new QueryTask(config), config.timeToRunNextTaskInMs, MILLISECONDS);
+                requestTaskFuture = scheduleNextRunLocked(this.config);
             }
         }
     }
+
+    @NonNull
+    private Future<?> scheduleNextRunLocked(@NonNull QueryTaskConfig lastRunConfig) {
+        QueryTaskConfig config = lastRunConfig.getConfigForNextRun();
+        return executor.schedule(new QueryTask(config), config.timeToRunNextTaskInMs, MILLISECONDS);
+    }
 }
\ No newline at end of file
diff --git a/service-t/src/com/android/server/connectivity/mdns/MdnsSocketClientBase.java b/service-t/src/com/android/server/connectivity/mdns/MdnsSocketClientBase.java
index ebafc49..6bcad01 100644
--- a/service-t/src/com/android/server/connectivity/mdns/MdnsSocketClientBase.java
+++ b/service-t/src/com/android/server/connectivity/mdns/MdnsSocketClientBase.java
@@ -86,5 +86,8 @@
     interface SocketCreationCallback {
         /*** Notify requested socket is created */
         void onSocketCreated(@Nullable Network network);
+
+        /*** Notify requested socket is destroyed */
+        void onSocketDestroyed(@Nullable Network network);
     }
 }
diff --git a/tests/unit/java/com/android/server/NsdServiceTest.java b/tests/unit/java/com/android/server/NsdServiceTest.java
index 5ca3934..b3e8cc8 100644
--- a/tests/unit/java/com/android/server/NsdServiceTest.java
+++ b/tests/unit/java/com/android/server/NsdServiceTest.java
@@ -23,7 +23,7 @@
 import static android.net.nsd.NsdManager.FAILURE_INTERNAL_ERROR;
 import static android.net.nsd.NsdManager.FAILURE_OPERATION_NOT_RUNNING;
 
-import static com.android.server.NsdService.constructServiceType;
+import static com.android.server.NsdService.parseTypeAndSubtype;
 import static com.android.testutils.ContextUtils.mockService;
 
 import static libcore.junit.util.compat.CoreCompatChangeRule.DisableCompatChanges;
@@ -77,6 +77,7 @@
 import android.os.Looper;
 import android.os.Message;
 import android.os.RemoteException;
+import android.util.Pair;
 
 import androidx.annotation.NonNull;
 import androidx.test.filters.SmallTest;
@@ -84,6 +85,7 @@
 import com.android.server.NsdService.Dependencies;
 import com.android.server.connectivity.mdns.MdnsAdvertiser;
 import com.android.server.connectivity.mdns.MdnsDiscoveryManager;
+import com.android.server.connectivity.mdns.MdnsSearchOptions;
 import com.android.server.connectivity.mdns.MdnsServiceBrowserListener;
 import com.android.server.connectivity.mdns.MdnsServiceInfo;
 import com.android.server.connectivity.mdns.MdnsSocketProvider;
@@ -104,6 +106,7 @@
 
 import java.net.InetAddress;
 import java.net.UnknownHostException;
+import java.util.Collections;
 import java.util.LinkedList;
 import java.util.List;
 import java.util.Objects;
@@ -969,6 +972,34 @@
     }
 
     @Test
+    @EnableCompatChanges(ENABLE_PLATFORM_MDNS_BACKEND)
+    public void testDiscoveryWithMdnsDiscoveryManager_UsesSubtypes() {
+        final String typeWithSubtype = SERVICE_TYPE + ",_subtype";
+        final NsdManager client = connectClient(mService);
+        final NsdServiceInfo regInfo = new NsdServiceInfo("Instance", typeWithSubtype);
+        final Network network = new Network(999);
+        regInfo.setHostAddresses(List.of(parseNumericAddress("192.0.2.123")));
+        regInfo.setPort(12345);
+        regInfo.setNetwork(network);
+
+        final RegistrationListener regListener = mock(RegistrationListener.class);
+        client.registerService(regInfo, NsdManager.PROTOCOL_DNS_SD, Runnable::run, regListener);
+        waitForIdle();
+        verify(mAdvertiser).addService(anyInt(), argThat(s ->
+                "Instance".equals(s.getServiceName())
+                        && SERVICE_TYPE.equals(s.getServiceType())), eq("_subtype"));
+
+        final DiscoveryListener discListener = mock(DiscoveryListener.class);
+        client.discoverServices(typeWithSubtype, PROTOCOL, network, Runnable::run, discListener);
+        waitForIdle();
+        final ArgumentCaptor<MdnsSearchOptions> optionsCaptor =
+                ArgumentCaptor.forClass(MdnsSearchOptions.class);
+        verify(mDiscoveryManager).registerListener(eq(SERVICE_TYPE + ".local"), any(),
+                optionsCaptor.capture());
+        assertEquals(Collections.singletonList("subtype"), optionsCaptor.getValue().getSubtypes());
+    }
+
+    @Test
     public void testResolutionWithMdnsDiscoveryManager() throws UnknownHostException {
         setMdnsDiscoveryManagerEnabled();
 
@@ -976,7 +1007,7 @@
         final ResolveListener resolveListener = mock(ResolveListener.class);
         final Network network = new Network(999);
         final String serviceType = "_nsd._service._tcp";
-        final String constructedServiceType = "_nsd._sub._service._tcp.local";
+        final String constructedServiceType = "_service._tcp.local";
         final ArgumentCaptor<MdnsServiceBrowserListener> listenerCaptor =
                 ArgumentCaptor.forClass(MdnsServiceBrowserListener.class);
         final NsdServiceInfo request = new NsdServiceInfo(SERVICE_NAME, serviceType);
@@ -984,12 +1015,14 @@
         client.resolveService(request, resolveListener);
         waitForIdle();
         verify(mSocketProvider).startMonitoringSockets();
-        // TODO(b/266167702): this is a bug, as registerListener should be done _service._tcp, and
-        // _sub should be in the list of subtypes in the options.
+        final ArgumentCaptor<MdnsSearchOptions> optionsCaptor =
+                ArgumentCaptor.forClass(MdnsSearchOptions.class);
         verify(mDiscoveryManager).registerListener(eq(constructedServiceType),
-                listenerCaptor.capture(), argThat(options ->
-                        network.equals(options.getNetwork())
-                                && SERVICE_NAME.equals(options.getResolveInstanceName())));
+                listenerCaptor.capture(),
+                optionsCaptor.capture());
+        assertEquals(network, optionsCaptor.getValue().getNetwork());
+        // Subtypes are not used for resolution, only for discovery
+        assertEquals(Collections.emptyList(), optionsCaptor.getValue().getSubtypes());
 
         final MdnsServiceBrowserListener listener = listenerCaptor.getValue();
         final MdnsServiceInfo mdnsServiceInfo = new MdnsServiceInfo(
@@ -1013,8 +1046,7 @@
         verify(resolveListener, timeout(TIMEOUT_MS)).onServiceResolved(infoCaptor.capture());
         final NsdServiceInfo info = infoCaptor.getValue();
         assertEquals(SERVICE_NAME, info.getServiceName());
-        // TODO(b/266167702): this should be ._service._tcp (as per legacy behavior)
-        assertEquals("._nsd._sub._service._tcp", info.getServiceType());
+        assertEquals("._service._tcp", info.getServiceType());
         assertEquals(PORT, info.getPort());
         assertTrue(info.getAttributes().containsKey("key"));
         assertEquals(1, info.getAttributes().size());
@@ -1057,7 +1089,7 @@
 
         final ArgumentCaptor<Integer> serviceIdCaptor = ArgumentCaptor.forClass(Integer.class);
         verify(mAdvertiser).addService(serviceIdCaptor.capture(),
-                argThat(info -> matches(info, regInfo)));
+                argThat(info -> matches(info, regInfo)), eq(null) /* subtype */);
 
         client.unregisterService(regListenerWithoutFeature);
         waitForIdle();
@@ -1114,8 +1146,10 @@
         waitForIdle();
 
         // The advertiser is enabled for _type2 but not _type1
-        verify(mAdvertiser, never()).addService(anyInt(), argThat(info -> matches(info, service1)));
-        verify(mAdvertiser).addService(anyInt(), argThat(info -> matches(info, service2)));
+        verify(mAdvertiser, never()).addService(
+                anyInt(), argThat(info -> matches(info, service1)), eq(null) /* subtype */);
+        verify(mAdvertiser).addService(
+                anyInt(), argThat(info -> matches(info, service2)), eq(null) /* subtype */);
     }
 
     @Test
@@ -1140,7 +1174,7 @@
         verify(mSocketProvider).startMonitoringSockets();
         final ArgumentCaptor<Integer> idCaptor = ArgumentCaptor.forClass(Integer.class);
         verify(mAdvertiser).addService(idCaptor.capture(), argThat(info ->
-                matches(info, regInfo)));
+                matches(info, regInfo)), eq(null) /* subtype */);
 
         // Verify onServiceRegistered callback
         final MdnsAdvertiser.AdvertiserCallback cb = cbCaptor.getValue();
@@ -1176,7 +1210,7 @@
 
         client.registerService(regInfo, NsdManager.PROTOCOL_DNS_SD, Runnable::run, regListener);
         waitForIdle();
-        verify(mAdvertiser, never()).addService(anyInt(), any());
+        verify(mAdvertiser, never()).addService(anyInt(), any(), any());
 
         verify(regListener, timeout(TIMEOUT_MS)).onRegistrationFailed(
                 argThat(info -> matches(info, regInfo)), eq(FAILURE_INTERNAL_ERROR));
@@ -1204,7 +1238,8 @@
         final ArgumentCaptor<Integer> idCaptor = ArgumentCaptor.forClass(Integer.class);
         // Service name is truncated to 63 characters
         verify(mAdvertiser).addService(idCaptor.capture(),
-                argThat(info -> info.getServiceName().equals("a".repeat(63))));
+                argThat(info -> info.getServiceName().equals("a".repeat(63))),
+                eq(null) /* subtype */);
 
         // Verify onServiceRegistered callback
         final MdnsAdvertiser.AdvertiserCallback cb = cbCaptor.getValue();
@@ -1222,7 +1257,7 @@
         final ResolveListener resolveListener = mock(ResolveListener.class);
         final Network network = new Network(999);
         final String serviceType = "_nsd._service._tcp";
-        final String constructedServiceType = "_nsd._sub._service._tcp.local";
+        final String constructedServiceType = "_service._tcp.local";
         final ArgumentCaptor<MdnsServiceBrowserListener> listenerCaptor =
                 ArgumentCaptor.forClass(MdnsServiceBrowserListener.class);
         final NsdServiceInfo request = new NsdServiceInfo(SERVICE_NAME, serviceType);
@@ -1230,8 +1265,14 @@
         client.resolveService(request, resolveListener);
         waitForIdle();
         verify(mSocketProvider).startMonitoringSockets();
+        final ArgumentCaptor<MdnsSearchOptions> optionsCaptor =
+                ArgumentCaptor.forClass(MdnsSearchOptions.class);
         verify(mDiscoveryManager).registerListener(eq(constructedServiceType),
-                listenerCaptor.capture(), argThat(options -> network.equals(options.getNetwork())));
+                listenerCaptor.capture(),
+                optionsCaptor.capture());
+        assertEquals(network, optionsCaptor.getValue().getNetwork());
+        // Subtypes are not used for resolution, only for discovery
+        assertEquals(Collections.emptyList(), optionsCaptor.getValue().getSubtypes());
 
         client.stopServiceResolution(resolveListener);
         waitForIdle();
@@ -1246,16 +1287,22 @@
     }
 
     @Test
-    public void testConstructServiceType() {
+    public void testParseTypeAndSubtype() {
         final String serviceType1 = "test._tcp";
         final String serviceType2 = "_test._quic";
-        final String serviceType3 = "_123._udp.";
-        final String serviceType4 = "_TEST._999._tcp.";
+        final String serviceType3 = "_test._quic,_test1,_test2";
+        final String serviceType4 = "_123._udp.";
+        final String serviceType5 = "_TEST._999._tcp.";
+        final String serviceType6 = "_998._tcp.,_TEST";
+        final String serviceType7 = "_997._tcp,_TEST";
 
-        assertEquals(null, constructServiceType(serviceType1));
-        assertEquals(null, constructServiceType(serviceType2));
-        assertEquals("_123._udp", constructServiceType(serviceType3));
-        assertEquals("_TEST._sub._999._tcp", constructServiceType(serviceType4));
+        assertNull(parseTypeAndSubtype(serviceType1));
+        assertNull(parseTypeAndSubtype(serviceType2));
+        assertNull(parseTypeAndSubtype(serviceType3));
+        assertEquals(new Pair<>("_123._udp", null), parseTypeAndSubtype(serviceType4));
+        assertEquals(new Pair<>("_999._tcp", "_TEST"), parseTypeAndSubtype(serviceType5));
+        assertEquals(new Pair<>("_998._tcp", "_TEST"), parseTypeAndSubtype(serviceType6));
+        assertEquals(new Pair<>("_997._tcp", "_TEST"), parseTypeAndSubtype(serviceType7));
     }
 
     @Test
@@ -1274,7 +1321,7 @@
         client.registerService(regInfo, NsdManager.PROTOCOL_DNS_SD, Runnable::run, regListener);
         waitForIdle();
         verify(mSocketProvider).startMonitoringSockets();
-        verify(mAdvertiser).addService(anyInt(), any());
+        verify(mAdvertiser).addService(anyInt(), any(), any());
 
         // Verify the discovery uses MdnsDiscoveryManager
         final DiscoveryListener discListener = mock(DiscoveryListener.class);
diff --git a/tests/unit/java/com/android/server/connectivity/mdns/MdnsAdvertiserTest.kt b/tests/unit/java/com/android/server/connectivity/mdns/MdnsAdvertiserTest.kt
index 3bb08a6..b539fe0 100644
--- a/tests/unit/java/com/android/server/connectivity/mdns/MdnsAdvertiserTest.kt
+++ b/tests/unit/java/com/android/server/connectivity/mdns/MdnsAdvertiserTest.kt
@@ -57,6 +57,7 @@
 private val TEST_NETWORK_1 = mock(Network::class.java)
 private val TEST_NETWORK_2 = mock(Network::class.java)
 private val TEST_HOSTNAME = arrayOf("Android_test", "local")
+private const val TEST_SUBTYPE = "_subtype"
 
 private val SERVICE_1 = NsdServiceInfo("TestServiceName", "_advertisertest._tcp").apply {
     port = 12345
@@ -130,7 +131,7 @@
     @Test
     fun testAddService_OneNetwork() {
         val advertiser = MdnsAdvertiser(thread.looper, socketProvider, cb, mockDeps, sharedlog)
-        postSync { advertiser.addService(SERVICE_ID_1, SERVICE_1) }
+        postSync { advertiser.addService(SERVICE_ID_1, SERVICE_1, null /* subtype */) }
 
         val socketCbCaptor = ArgumentCaptor.forClass(SocketCallback::class.java)
         verify(socketProvider).requestSocket(eq(TEST_NETWORK_1), socketCbCaptor.capture())
@@ -161,7 +162,7 @@
     @Test
     fun testAddService_AllNetworks() {
         val advertiser = MdnsAdvertiser(thread.looper, socketProvider, cb, mockDeps, sharedlog)
-        postSync { advertiser.addService(SERVICE_ID_1, ALL_NETWORKS_SERVICE) }
+        postSync { advertiser.addService(SERVICE_ID_1, ALL_NETWORKS_SERVICE, TEST_SUBTYPE) }
 
         val socketCbCaptor = ArgumentCaptor.forClass(SocketCallback::class.java)
         verify(socketProvider).requestSocket(eq(ALL_NETWORKS_SERVICE.network),
@@ -179,6 +180,10 @@
         verify(mockDeps).makeAdvertiser(eq(mockSocket2), eq(listOf(TEST_LINKADDR)),
                 eq(thread.looper), any(), intAdvCbCaptor2.capture(), eq(TEST_HOSTNAME), any()
         )
+        verify(mockInterfaceAdvertiser1).addService(
+                anyInt(), eq(ALL_NETWORKS_SERVICE), eq(TEST_SUBTYPE))
+        verify(mockInterfaceAdvertiser2).addService(
+                anyInt(), eq(ALL_NETWORKS_SERVICE), eq(TEST_SUBTYPE))
 
         doReturn(false).`when`(mockInterfaceAdvertiser1).isProbing(SERVICE_ID_1)
         postSync { intAdvCbCaptor1.value.onRegisterServiceSucceeded(
@@ -207,20 +212,21 @@
     @Test
     fun testAddService_Conflicts() {
         val advertiser = MdnsAdvertiser(thread.looper, socketProvider, cb, mockDeps, sharedlog)
-        postSync { advertiser.addService(SERVICE_ID_1, SERVICE_1) }
+        postSync { advertiser.addService(SERVICE_ID_1, SERVICE_1, null /* subtype */) }
 
         val oneNetSocketCbCaptor = ArgumentCaptor.forClass(SocketCallback::class.java)
         verify(socketProvider).requestSocket(eq(TEST_NETWORK_1), oneNetSocketCbCaptor.capture())
         val oneNetSocketCb = oneNetSocketCbCaptor.value
 
         // Register a service with the same name on all networks (name conflict)
-        postSync { advertiser.addService(SERVICE_ID_2, ALL_NETWORKS_SERVICE) }
+        postSync { advertiser.addService(SERVICE_ID_2, ALL_NETWORKS_SERVICE, null /* subtype */) }
         val allNetSocketCbCaptor = ArgumentCaptor.forClass(SocketCallback::class.java)
         verify(socketProvider).requestSocket(eq(null), allNetSocketCbCaptor.capture())
         val allNetSocketCb = allNetSocketCbCaptor.value
 
-        postSync { advertiser.addService(LONG_SERVICE_ID_1, LONG_SERVICE_1) }
-        postSync { advertiser.addService(LONG_SERVICE_ID_2, LONG_ALL_NETWORKS_SERVICE) }
+        postSync { advertiser.addService(LONG_SERVICE_ID_1, LONG_SERVICE_1, null /* subtype */) }
+        postSync { advertiser.addService(LONG_SERVICE_ID_2, LONG_ALL_NETWORKS_SERVICE,
+                null /* subtype */) }
 
         // Callbacks for matching network and all networks both get the socket
         postSync {
@@ -248,13 +254,13 @@
                 eq(thread.looper), any(), intAdvCbCaptor.capture(), eq(TEST_HOSTNAME), any()
         )
         verify(mockInterfaceAdvertiser1).addService(eq(SERVICE_ID_1),
-                argThat { it.matches(SERVICE_1) })
+                argThat { it.matches(SERVICE_1) }, eq(null))
         verify(mockInterfaceAdvertiser1).addService(eq(SERVICE_ID_2),
-                argThat { it.matches(expectedRenamed) })
+                argThat { it.matches(expectedRenamed) }, eq(null))
         verify(mockInterfaceAdvertiser1).addService(eq(LONG_SERVICE_ID_1),
-                argThat { it.matches(LONG_SERVICE_1) })
+                argThat { it.matches(LONG_SERVICE_1) }, eq(null))
         verify(mockInterfaceAdvertiser1).addService(eq(LONG_SERVICE_ID_2),
-            argThat { it.matches(expectedLongRenamed) })
+            argThat { it.matches(expectedLongRenamed) }, eq(null))
 
         doReturn(false).`when`(mockInterfaceAdvertiser1).isProbing(SERVICE_ID_1)
         postSync { intAdvCbCaptor.value.onRegisterServiceSucceeded(
@@ -278,7 +284,7 @@
     fun testRemoveService_whenAllServiceRemoved_thenUpdateHostName() {
         val advertiser = MdnsAdvertiser(thread.looper, socketProvider, cb, mockDeps, sharedlog)
         verify(mockDeps, times(1)).generateHostname()
-        postSync { advertiser.addService(SERVICE_ID_1, SERVICE_1) }
+        postSync { advertiser.addService(SERVICE_ID_1, SERVICE_1, null /* subtype */) }
         postSync { advertiser.removeService(SERVICE_ID_1) }
         verify(mockDeps, times(2)).generateHostname()
     }
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 0a23ba5..63357f1 100644
--- a/tests/unit/java/com/android/server/connectivity/mdns/MdnsDiscoveryManagerTests.java
+++ b/tests/unit/java/com/android/server/connectivity/mdns/MdnsDiscoveryManagerTests.java
@@ -20,6 +20,7 @@
 
 import static org.mockito.Mockito.eq;
 import static org.mockito.Mockito.never;
+import static org.mockito.Mockito.times;
 import static org.mockito.Mockito.verify;
 import static org.mockito.Mockito.when;
 
@@ -193,6 +194,60 @@
         verify(mockServiceTypeClientTwo2).processResponse(responseForSubtype, ifIndex, NETWORK_2);
     }
 
+    @Test
+    public void testSocketCreatedAndDestroyed() throws IOException {
+        // Create a ServiceTypeClient for SERVICE_TYPE_1 and NETWORK_1
+        final MdnsSearchOptions options1 =
+                MdnsSearchOptions.newBuilder().setNetwork(NETWORK_1).build();
+        final SocketCreationCallback callback = expectSocketCreationCallback(
+                SERVICE_TYPE_1, mockListenerOne, options1);
+        callback.onSocketCreated(NETWORK_1);
+        verify(mockServiceTypeClientOne1).startSendAndReceive(mockListenerOne, options1);
+
+        // Create a ServiceTypeClient for SERVICE_TYPE_2 and NETWORK_2
+        final MdnsSearchOptions options2 =
+                MdnsSearchOptions.newBuilder().setNetwork(NETWORK_2).build();
+        final SocketCreationCallback callback2 = expectSocketCreationCallback(
+                SERVICE_TYPE_2, mockListenerTwo, options2);
+        callback2.onSocketCreated(NETWORK_2);
+        verify(mockServiceTypeClientTwo2).startSendAndReceive(mockListenerTwo, options2);
+
+        // Receive a response, it should be processed on both clients.
+        final MdnsPacket response = createMdnsPacket(SERVICE_TYPE_1);
+        final int ifIndex = 1;
+        discoveryManager.onResponseReceived(response, ifIndex, null /* network */);
+        verify(mockServiceTypeClientOne1).processResponse(response, ifIndex, null /* network */);
+        verify(mockServiceTypeClientTwo2).processResponse(response, ifIndex, null /* network */);
+
+        // The client for NETWORK_1 receives the callback that the NETWORK_1 has been destroyed,
+        // mockServiceTypeClientOne1 should send service removed notifications and remove from the
+        // list of clients.
+        callback.onSocketDestroyed(NETWORK_1);
+        verify(mockServiceTypeClientOne1).notifyAllServicesRemoved();
+
+        // Receive a response again, it should be processed only on mockServiceTypeClientTwo2.
+        // Because the mockServiceTypeClientOne1 is removed from the list of clients, it is no
+        // longer able to process responses.
+        discoveryManager.onResponseReceived(response, ifIndex, null /* network */);
+        verify(mockServiceTypeClientOne1, times(1))
+                .processResponse(response, ifIndex, null /* network */);
+        verify(mockServiceTypeClientTwo2, times(2))
+                .processResponse(response, ifIndex, null /* network */);
+
+        // The client for NETWORK_2 receives the callback that the NETWORK_1 has been destroyed,
+        // mockServiceTypeClientTwo2 shouldn't send any notifications.
+        callback2.onSocketDestroyed(NETWORK_1);
+        verify(mockServiceTypeClientTwo2, never()).notifyAllServicesRemoved();
+
+        // Receive a response again, mockServiceTypeClientTwo2 is still in the list of clients, it's
+        // still able to process responses.
+        discoveryManager.onResponseReceived(response, ifIndex, null /* network */);
+        verify(mockServiceTypeClientOne1, times(1))
+                .processResponse(response, ifIndex, null /* network */);
+        verify(mockServiceTypeClientTwo2, times(3))
+                .processResponse(response, ifIndex, null /* network */);
+    }
+
     private MdnsPacket createMdnsPacket(String serviceType) {
         final String[] type = TextUtils.split(serviceType, "\\.");
         final ArrayList<String> name = new ArrayList<>(type.length + 1);
diff --git a/tests/unit/java/com/android/server/connectivity/mdns/MdnsInterfaceAdvertiserTest.kt b/tests/unit/java/com/android/server/connectivity/mdns/MdnsInterfaceAdvertiserTest.kt
index ee190af..dd458b8 100644
--- a/tests/unit/java/com/android/server/connectivity/mdns/MdnsInterfaceAdvertiserTest.kt
+++ b/tests/unit/java/com/android/server/connectivity/mdns/MdnsInterfaceAdvertiserTest.kt
@@ -117,7 +117,7 @@
             knownServices.add(inv.getArgument(0))
 
             -1
-        }.`when`(repository).addService(anyInt(), any())
+        }.`when`(repository).addService(anyInt(), any(), any())
         doAnswer { inv ->
             knownServices.remove(inv.getArgument(0))
             null
@@ -278,8 +278,8 @@
         doReturn(serviceId).`when`(testProbingInfo).serviceId
         doReturn(testProbingInfo).`when`(repository).setServiceProbing(serviceId)
 
-        advertiser.addService(serviceId, serviceInfo)
-        verify(repository).addService(serviceId, serviceInfo)
+        advertiser.addService(serviceId, serviceInfo, null /* subtype */)
+        verify(repository).addService(serviceId, serviceInfo, null /* subtype */)
         verify(prober).startProbing(testProbingInfo)
 
         // Simulate probing success: continues to announcing
diff --git a/tests/unit/java/com/android/server/connectivity/mdns/MdnsRecordRepositoryTest.kt b/tests/unit/java/com/android/server/connectivity/mdns/MdnsRecordRepositoryTest.kt
index 44e0d08..4a39b93 100644
--- a/tests/unit/java/com/android/server/connectivity/mdns/MdnsRecordRepositoryTest.kt
+++ b/tests/unit/java/com/android/server/connectivity/mdns/MdnsRecordRepositoryTest.kt
@@ -44,6 +44,7 @@
 private const val TEST_SERVICE_ID_1 = 42
 private const val TEST_SERVICE_ID_2 = 43
 private const val TEST_PORT = 12345
+private const val TEST_SUBTYPE = "_subtype"
 private val TEST_HOSTNAME = arrayOf("Android_000102030405060708090A0B0C0D0E0F", "local")
 private val TEST_ADDRESSES = listOf(
         LinkAddress(parseNumericAddress("192.0.2.111"), 24),
@@ -86,7 +87,8 @@
     fun testAddServiceAndProbe() {
         val repository = MdnsRecordRepository(thread.looper, deps, TEST_HOSTNAME)
         assertEquals(0, repository.servicesCount)
-        assertEquals(-1, repository.addService(TEST_SERVICE_ID_1, TEST_SERVICE_1))
+        assertEquals(-1, repository.addService(TEST_SERVICE_ID_1, TEST_SERVICE_1,
+                null /* subtype */))
         assertEquals(1, repository.servicesCount)
 
         val probingInfo = repository.setServiceProbing(TEST_SERVICE_ID_1)
@@ -118,18 +120,18 @@
     @Test
     fun testAddAndConflicts() {
         val repository = MdnsRecordRepository(thread.looper, deps, TEST_HOSTNAME)
-        repository.addService(TEST_SERVICE_ID_1, TEST_SERVICE_1)
+        repository.addService(TEST_SERVICE_ID_1, TEST_SERVICE_1, null /* subtype */)
         assertFailsWith(NameConflictException::class) {
-            repository.addService(TEST_SERVICE_ID_2, TEST_SERVICE_1)
+            repository.addService(TEST_SERVICE_ID_2, TEST_SERVICE_1, null /* subtype */)
         }
     }
 
     @Test
     fun testInvalidReuseOfServiceId() {
         val repository = MdnsRecordRepository(thread.looper, deps, TEST_HOSTNAME)
-        repository.addService(TEST_SERVICE_ID_1, TEST_SERVICE_1)
+        repository.addService(TEST_SERVICE_ID_1, TEST_SERVICE_1, null /* subtype */)
         assertFailsWith(IllegalArgumentException::class) {
-            repository.addService(TEST_SERVICE_ID_1, TEST_SERVICE_2)
+            repository.addService(TEST_SERVICE_ID_1, TEST_SERVICE_2, null /* subtype */)
         }
     }
 
@@ -138,7 +140,7 @@
         val repository = MdnsRecordRepository(thread.looper, deps, TEST_HOSTNAME)
         assertFalse(repository.hasActiveService(TEST_SERVICE_ID_1))
 
-        repository.addService(TEST_SERVICE_ID_1, TEST_SERVICE_1)
+        repository.addService(TEST_SERVICE_ID_1, TEST_SERVICE_1, null /* subtype */)
         assertTrue(repository.hasActiveService(TEST_SERVICE_ID_1))
 
         val probingInfo = repository.setServiceProbing(TEST_SERVICE_ID_1)
@@ -180,13 +182,49 @@
     }
 
     @Test
+    fun testExitAnnouncements_WithSubtype() {
+        val repository = MdnsRecordRepository(thread.looper, deps, TEST_HOSTNAME)
+        repository.initWithService(TEST_SERVICE_ID_1, TEST_SERVICE_1, TEST_SUBTYPE)
+        repository.onAdvertisementSent(TEST_SERVICE_ID_1)
+
+        val exitAnnouncement = repository.exitService(TEST_SERVICE_ID_1)
+        assertNotNull(exitAnnouncement)
+        assertEquals(1, repository.servicesCount)
+        val packet = exitAnnouncement.getPacket(0)
+
+        assertEquals(0x8400 /* response, authoritative */, packet.flags)
+        assertEquals(0, packet.questions.size)
+        assertEquals(0, packet.authorityRecords.size)
+        assertEquals(0, packet.additionalRecords.size)
+
+        assertContentEquals(listOf(
+                MdnsPointerRecord(
+                        arrayOf("_testservice", "_tcp", "local"),
+                        0L /* receiptTimeMillis */,
+                        true /* cacheFlush */,
+                        0L /* ttlMillis */,
+                        arrayOf("MyTestService", "_testservice", "_tcp", "local")),
+                MdnsPointerRecord(
+                        arrayOf("_subtype", "_sub", "_testservice", "_tcp", "local"),
+                        0L /* receiptTimeMillis */,
+                        true /* cacheFlush */,
+                        0L /* ttlMillis */,
+                        arrayOf("MyTestService", "_testservice", "_tcp", "local")),
+        ), packet.answers)
+
+        repository.removeService(TEST_SERVICE_ID_1)
+        assertEquals(0, repository.servicesCount)
+    }
+
+    @Test
     fun testExitingServiceReAdded() {
         val repository = MdnsRecordRepository(thread.looper, deps, TEST_HOSTNAME)
         repository.initWithService(TEST_SERVICE_ID_1, TEST_SERVICE_1)
         repository.onAdvertisementSent(TEST_SERVICE_ID_1)
         repository.exitService(TEST_SERVICE_ID_1)
 
-        assertEquals(TEST_SERVICE_ID_1, repository.addService(TEST_SERVICE_ID_2, TEST_SERVICE_1))
+        assertEquals(TEST_SERVICE_ID_1,
+                repository.addService(TEST_SERVICE_ID_2, TEST_SERVICE_1, null /* subtype */))
         assertEquals(1, repository.servicesCount)
 
         repository.removeService(TEST_SERVICE_ID_2)
@@ -196,7 +234,8 @@
     @Test
     fun testOnProbingSucceeded() {
         val repository = MdnsRecordRepository(thread.looper, deps, TEST_HOSTNAME)
-        val announcementInfo = repository.initWithService(TEST_SERVICE_ID_1, TEST_SERVICE_1)
+        val announcementInfo = repository.initWithService(TEST_SERVICE_ID_1, TEST_SERVICE_1,
+                TEST_SUBTYPE)
         repository.onAdvertisementSent(TEST_SERVICE_ID_1)
         val packet = announcementInfo.getPacket(0)
 
@@ -205,6 +244,7 @@
         assertEquals(0, packet.authorityRecords.size)
 
         val serviceType = arrayOf("_testservice", "_tcp", "local")
+        val serviceSubtype = arrayOf(TEST_SUBTYPE, "_sub", "_testservice", "_tcp", "local")
         val serviceName = arrayOf("MyTestService", "_testservice", "_tcp", "local")
         val v4AddrRev = getReverseDnsAddress(TEST_ADDRESSES[0].address)
         val v6Addr1Rev = getReverseDnsAddress(TEST_ADDRESSES[1].address)
@@ -250,6 +290,13 @@
                         false /* cacheFlush */,
                         4500000L /* ttlMillis */,
                         serviceName),
+                MdnsPointerRecord(
+                        serviceSubtype,
+                        0L /* receiptTimeMillis */,
+                        // Not a unique name owned by the announcer, so cacheFlush=false
+                        false /* cacheFlush */,
+                        4500000L /* ttlMillis */,
+                        serviceName),
                 MdnsServiceRecord(
                         serviceName,
                         0L /* receiptTimeMillis */,
@@ -319,9 +366,21 @@
 
     @Test
     fun testGetReply() {
+        doGetReplyTest(subtype = null)
+    }
+
+    @Test
+    fun testGetReply_WithSubtype() {
+        doGetReplyTest(TEST_SUBTYPE)
+    }
+
+    private fun doGetReplyTest(subtype: String?) {
         val repository = MdnsRecordRepository(thread.looper, deps, TEST_HOSTNAME)
-        repository.initWithService(TEST_SERVICE_ID_1, TEST_SERVICE_1)
-        val questions = listOf(MdnsPointerRecord(arrayOf("_testservice", "_tcp", "local"),
+        repository.initWithService(TEST_SERVICE_ID_1, TEST_SERVICE_1, subtype)
+        val queriedName = if (subtype == null) arrayOf("_testservice", "_tcp", "local")
+        else arrayOf(subtype, "_sub", "_testservice", "_tcp", "local")
+
+        val questions = listOf(MdnsPointerRecord(queriedName,
                 0L /* receiptTimeMillis */,
                 false /* cacheFlush */,
                 // TTL and data is empty for a question
@@ -344,7 +403,7 @@
 
         assertEquals(listOf(
                 MdnsPointerRecord(
-                        arrayOf("_testservice", "_tcp", "local"),
+                        queriedName,
                         0L /* receiptTimeMillis */,
                         false /* cacheFlush */,
                         longTtl,
@@ -405,8 +464,8 @@
     @Test
     fun testGetConflictingServices() {
         val repository = MdnsRecordRepository(thread.looper, deps, TEST_HOSTNAME)
-        repository.addService(TEST_SERVICE_ID_1, TEST_SERVICE_1)
-        repository.addService(TEST_SERVICE_ID_2, TEST_SERVICE_2)
+        repository.addService(TEST_SERVICE_ID_1, TEST_SERVICE_1, null /* subtype */)
+        repository.addService(TEST_SERVICE_ID_2, TEST_SERVICE_2, null /* subtype */)
 
         val packet = MdnsPacket(
                 0 /* flags */,
@@ -433,8 +492,8 @@
     @Test
     fun testGetConflictingServices_IdenticalService() {
         val repository = MdnsRecordRepository(thread.looper, deps, TEST_HOSTNAME)
-        repository.addService(TEST_SERVICE_ID_1, TEST_SERVICE_1)
-        repository.addService(TEST_SERVICE_ID_2, TEST_SERVICE_2)
+        repository.addService(TEST_SERVICE_ID_1, TEST_SERVICE_1, null /* subtype */)
+        repository.addService(TEST_SERVICE_ID_2, TEST_SERVICE_2, null /* subtype */)
 
         val otherTtlMillis = 1234L
         val packet = MdnsPacket(
@@ -460,10 +519,13 @@
     }
 }
 
-private fun MdnsRecordRepository.initWithService(serviceId: Int, serviceInfo: NsdServiceInfo):
-        AnnouncementInfo {
+private fun MdnsRecordRepository.initWithService(
+    serviceId: Int,
+    serviceInfo: NsdServiceInfo,
+    subtype: String? = null
+): AnnouncementInfo {
     updateAddresses(TEST_ADDRESSES)
-    addService(serviceId, serviceInfo)
+    addService(serviceId, serviceInfo, subtype)
     val probingInfo = setServiceProbing(serviceId)
     assertNotNull(probingInfo)
     return onProbingSucceeded(probingInfo)
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 34b44fc..bd59156 100644
--- a/tests/unit/java/com/android/server/connectivity/mdns/MdnsServiceTypeClientTests.java
+++ b/tests/unit/java/com/android/server/connectivity/mdns/MdnsServiceTypeClientTests.java
@@ -21,6 +21,7 @@
 import static org.junit.Assert.assertArrayEquals;
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertNotNull;
 import static org.junit.Assert.assertNull;
 import static org.junit.Assert.assertTrue;
 import static org.mockito.ArgumentMatchers.any;
@@ -41,6 +42,7 @@
 import android.net.Network;
 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;
@@ -52,6 +54,7 @@
 import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.mockito.ArgumentCaptor;
+import org.mockito.ArgumentMatcher;
 import org.mockito.Captor;
 import org.mockito.InOrder;
 import org.mockito.Mock;
@@ -422,6 +425,34 @@
         assertNull(currentThreadExecutor.getAndClearLastScheduledRunnable());
     }
 
+    @Test
+    public void testQueryScheduledWhenAnsweredFromCache() {
+        final MdnsSearchOptions searchOptions = MdnsSearchOptions.getDefaultOptions();
+        client.startSendAndReceive(mockListenerOne, searchOptions);
+        assertNotNull(currentThreadExecutor.getAndClearSubmittedRunnable());
+
+        client.processResponse(createResponse(
+                "service-instance-1", "192.0.2.123", 5353,
+                SERVICE_TYPE_LABELS,
+                Collections.emptyMap(), TEST_TTL), /* interfaceIndex= */ 20, mockNetwork);
+
+        verify(mockListenerOne).onServiceNameDiscovered(any());
+        verify(mockListenerOne).onServiceFound(any());
+
+        // File another identical query
+        client.startSendAndReceive(mockListenerTwo, searchOptions);
+
+        verify(mockListenerTwo).onServiceNameDiscovered(any());
+        verify(mockListenerTwo).onServiceFound(any());
+
+        // 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());
+    }
+
     private static void verifyServiceInfo(MdnsServiceInfo serviceInfo, String serviceName,
             String[] serviceType, List<String> ipv4Addresses, List<String> ipv6Addresses, int port,
             List<String> subTypes, Map<String, String> attributes, int interfaceIndex,
@@ -1056,6 +1087,142 @@
         inOrder.verify(mockListenerTwo).onServiceRemoved(matchServiceName(otherInstance));
     }
 
+    @Test
+    public void testProcessResponse_SubtypeDiscoveryLimitedToSubtype() {
+        client = new MdnsServiceTypeClient(
+                SERVICE_TYPE, mockSocketClient, currentThreadExecutor, mockNetwork, mockSharedLog);
+
+        final String matchingInstance = "instance1";
+        final String subtype = "_subtype";
+        final String otherInstance = "instance2";
+        final String ipV4Address = "192.0.2.0";
+        final String ipV6Address = "2001:db8::";
+
+        final MdnsSearchOptions options = MdnsSearchOptions.newBuilder()
+                // Search with different case. Note MdnsSearchOptions subtype doesn't start with "_"
+                .addSubtype("Subtype").build();
+
+        client.startSendAndReceive(mockListenerOne, options);
+        client.startSendAndReceive(mockListenerTwo, MdnsSearchOptions.getDefaultOptions());
+
+        // Complete response from instanceName
+        final MdnsPacket packetWithoutSubtype = createResponse(
+                matchingInstance, ipV4Address, 5353, SERVICE_TYPE_LABELS,
+                Collections.emptyMap() /* textAttributes */, TEST_TTL);
+        final MdnsPointerRecord originalPtr = (MdnsPointerRecord) CollectionUtils.findFirst(
+                packetWithoutSubtype.answers, r -> r instanceof MdnsPointerRecord);
+
+        // Add a subtype PTR record
+        final ArrayList<MdnsRecord> newAnswers = new ArrayList<>(packetWithoutSubtype.answers);
+        newAnswers.add(new MdnsPointerRecord(
+                // PTR should be _subtype._sub._type._tcp.local -> instance1._type._tcp.local
+                Stream.concat(Stream.of(subtype, "_sub"), Arrays.stream(SERVICE_TYPE_LABELS))
+                        .toArray(String[]::new),
+                originalPtr.getReceiptTime(), originalPtr.getCacheFlush(), originalPtr.getTtl(),
+                originalPtr.getPointer()));
+        final MdnsPacket packetWithSubtype = new MdnsPacket(
+                packetWithoutSubtype.flags,
+                packetWithoutSubtype.questions,
+                newAnswers,
+                packetWithoutSubtype.authorityRecords,
+                packetWithoutSubtype.additionalRecords);
+        client.processResponse(packetWithSubtype, INTERFACE_INDEX, mockNetwork);
+
+        // Complete response from otherInstanceName, without subtype
+        client.processResponse(createResponse(
+                        otherInstance, ipV4Address, 5353, SERVICE_TYPE_LABELS,
+                        Collections.emptyMap() /* textAttributes */, TEST_TTL),
+                INTERFACE_INDEX, mockNetwork);
+
+        // Address update from otherInstanceName
+        client.processResponse(createResponse(
+                otherInstance, ipV6Address, 5353, SERVICE_TYPE_LABELS,
+                Collections.emptyMap(), TEST_TTL), INTERFACE_INDEX, mockNetwork);
+
+        // Goodbye from otherInstanceName
+        client.processResponse(createResponse(
+                otherInstance, ipV6Address, 5353, SERVICE_TYPE_LABELS,
+                Collections.emptyMap(), 0L /* ttl */), INTERFACE_INDEX, mockNetwork);
+
+        // mockListenerOne gets notified for the requested instance
+        final ArgumentMatcher<MdnsServiceInfo> subtypeInstanceMatcher = info ->
+                info.getServiceInstanceName().equals(matchingInstance)
+                        && info.getSubtypes().equals(Collections.singletonList(subtype));
+        verify(mockListenerOne).onServiceNameDiscovered(argThat(subtypeInstanceMatcher));
+        verify(mockListenerOne).onServiceFound(argThat(subtypeInstanceMatcher));
+
+        // ...but does not get any callback for the other instance
+        verify(mockListenerOne, never()).onServiceFound(matchServiceName(otherInstance));
+        verify(mockListenerOne, never()).onServiceNameDiscovered(matchServiceName(otherInstance));
+        verify(mockListenerOne, never()).onServiceUpdated(matchServiceName(otherInstance));
+        verify(mockListenerOne, never()).onServiceRemoved(matchServiceName(otherInstance));
+
+        // mockListenerTwo gets notified for both though
+        final InOrder inOrder = inOrder(mockListenerTwo);
+        inOrder.verify(mockListenerTwo).onServiceNameDiscovered(argThat(subtypeInstanceMatcher));
+        inOrder.verify(mockListenerTwo).onServiceFound(argThat(subtypeInstanceMatcher));
+
+        inOrder.verify(mockListenerTwo).onServiceNameDiscovered(matchServiceName(otherInstance));
+        inOrder.verify(mockListenerTwo).onServiceFound(matchServiceName(otherInstance));
+        inOrder.verify(mockListenerTwo).onServiceUpdated(matchServiceName(otherInstance));
+        inOrder.verify(mockListenerTwo).onServiceRemoved(matchServiceName(otherInstance));
+    }
+
+    @Test
+    public void testNotifyAllServicesRemoved() {
+        client = new MdnsServiceTypeClient(
+                SERVICE_TYPE, mockSocketClient, currentThreadExecutor, mockNetwork, mockSharedLog);
+
+        final String requestedInstance = "instance1";
+        final String otherInstance = "instance2";
+        final String ipV4Address = "192.0.2.0";
+
+        final MdnsSearchOptions resolveOptions = MdnsSearchOptions.newBuilder()
+                // Use different case in the options
+                .setResolveInstanceName("Instance1").build();
+
+        client.startSendAndReceive(mockListenerOne, resolveOptions);
+        client.startSendAndReceive(mockListenerTwo, MdnsSearchOptions.getDefaultOptions());
+
+        // Complete response from instanceName
+        client.processResponse(createResponse(
+                        requestedInstance, ipV4Address, 5353, SERVICE_TYPE_LABELS,
+                        Collections.emptyMap() /* textAttributes */, TEST_TTL),
+                INTERFACE_INDEX, mockNetwork);
+
+        // Complete response from otherInstanceName
+        client.processResponse(createResponse(
+                        otherInstance, ipV4Address, 5353, SERVICE_TYPE_LABELS,
+                        Collections.emptyMap() /* textAttributes */, TEST_TTL),
+                INTERFACE_INDEX, mockNetwork);
+
+        client.notifyAllServicesRemoved();
+
+        // mockListenerOne gets notified for the requested instance
+        final InOrder inOrder1 = inOrder(mockListenerOne);
+        inOrder1.verify(mockListenerOne).onServiceNameDiscovered(
+                matchServiceName(requestedInstance));
+        inOrder1.verify(mockListenerOne).onServiceFound(matchServiceName(requestedInstance));
+        inOrder1.verify(mockListenerOne).onServiceRemoved(matchServiceName(requestedInstance));
+        inOrder1.verify(mockListenerOne).onServiceNameRemoved(matchServiceName(requestedInstance));
+        verify(mockListenerOne, never()).onServiceFound(matchServiceName(otherInstance));
+        verify(mockListenerOne, never()).onServiceNameDiscovered(matchServiceName(otherInstance));
+        verify(mockListenerOne, never()).onServiceRemoved(matchServiceName(otherInstance));
+        verify(mockListenerOne, never()).onServiceNameRemoved(matchServiceName(otherInstance));
+
+        // mockListenerTwo gets notified for both though
+        final InOrder inOrder2 = inOrder(mockListenerTwo);
+        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));
+    }
+
     private static MdnsServiceInfo matchServiceName(String name) {
         return argThat(info -> info.getServiceInstanceName().equals(name));
     }