diff --git a/service/mdns/com/android/server/connectivity/mdns/MdnsServiceBrowserListener.java b/service/mdns/com/android/server/connectivity/mdns/MdnsServiceBrowserListener.java
index 7a8fcc0..7c19359 100644
--- a/service/mdns/com/android/server/connectivity/mdns/MdnsServiceBrowserListener.java
+++ b/service/mdns/com/android/server/connectivity/mdns/MdnsServiceBrowserListener.java
@@ -28,21 +28,24 @@
 public interface MdnsServiceBrowserListener {
 
     /**
-     * Called when an mDNS service instance is found.
+     * Called when an mDNS service instance is found. This method would be called only if all
+     * service records (PTR, SRV, TXT, A or AAAA) are received .
      *
      * @param serviceInfo The found mDNS service instance.
      */
     void onServiceFound(@NonNull MdnsServiceInfo serviceInfo);
 
     /**
-     * Called when an mDNS service instance is updated.
+     * Called when an mDNS service instance is updated. This method would be called only if all
+     * service records (PTR, SRV, TXT, A or AAAA) are received before.
      *
      * @param serviceInfo The updated mDNS service instance.
      */
     void onServiceUpdated(@NonNull MdnsServiceInfo serviceInfo);
 
     /**
-     * Called when an mDNS service instance is no longer valid and removed.
+     * Called when a mDNS service instance is no longer valid and removed. This method would be
+     * called only if all service records (PTR, SRV, TXT, A or AAAA) are received before.
      *
      * @param serviceInfo The service instance of the removed mDNS service.
      */
@@ -75,4 +78,19 @@
      * @param errorCode            The error code, defined in {@link MdnsResponseErrorCode}.
      */
     void onFailedToParseMdnsResponse(int receivedPacketNumber, int errorCode);
+
+    /**
+     * Called when a mDNS service instance is discovered. This method would be called if the PTR
+     * record has been received.
+     *
+     * @param serviceInfo The discovered mDNS service instance.
+     */
+    void onServiceNameDiscovered(@NonNull MdnsServiceInfo serviceInfo);
+
+    /**
+     * Called when a discovered mDNS service instance is no longer valid and removed.
+     *
+     * @param serviceInfo The service instance of the removed mDNS service.
+     */
+    void onServiceNameRemoved(@NonNull MdnsServiceInfo serviceInfo);
 }
\ No newline at end of file
diff --git a/service/mdns/com/android/server/connectivity/mdns/MdnsServiceTypeClient.java b/service/mdns/com/android/server/connectivity/mdns/MdnsServiceTypeClient.java
index 0fd6025..dd4ff9b 100644
--- a/service/mdns/com/android/server/connectivity/mdns/MdnsServiceTypeClient.java
+++ b/service/mdns/com/android/server/connectivity/mdns/MdnsServiceTypeClient.java
@@ -148,10 +148,11 @@
             this.searchOptions = searchOptions;
             if (listeners.add(listener)) {
                 for (MdnsResponse existingResponse : instanceNameToResponse.values()) {
+                    final MdnsServiceInfo info =
+                            buildMdnsServiceInfoFromResponse(existingResponse, serviceTypeLabels);
+                    listener.onServiceNameDiscovered(info);
                     if (existingResponse.isComplete()) {
-                        listener.onServiceFound(
-                                buildMdnsServiceInfoFromResponse(existingResponse,
-                                        serviceTypeLabels));
+                        listener.onServiceFound(info);
                     }
                 }
             }
@@ -226,6 +227,7 @@
 
         boolean newServiceFound = false;
         boolean existingServiceChanged = false;
+        boolean serviceBecomesComplete = false;
         if (currentResponse == null) {
             newServiceFound = true;
             currentResponse = response;
@@ -233,10 +235,13 @@
             if (serviceInstanceName != null) {
                 instanceNameToResponse.put(serviceInstanceName, currentResponse);
             }
-        } else if (currentResponse.mergeRecordsFrom(response)) {
-            existingServiceChanged = true;
+        } else {
+            boolean before = currentResponse.isComplete();
+            existingServiceChanged = currentResponse.mergeRecordsFrom(response);
+            boolean after = currentResponse.isComplete();
+            serviceBecomesComplete = !before && after;
         }
-        if (!currentResponse.isComplete() || (!newServiceFound && !existingServiceChanged)) {
+        if (!newServiceFound && !existingServiceChanged) {
             return;
         }
         MdnsServiceInfo serviceInfo =
@@ -244,9 +249,15 @@
 
         for (MdnsServiceBrowserListener listener : listeners) {
             if (newServiceFound) {
-                listener.onServiceFound(serviceInfo);
-            } else {
-                listener.onServiceUpdated(serviceInfo);
+                listener.onServiceNameDiscovered(serviceInfo);
+            }
+
+            if (currentResponse.isComplete()) {
+                if (newServiceFound || serviceBecomesComplete) {
+                    listener.onServiceFound(serviceInfo);
+                } else {
+                    listener.onServiceUpdated(serviceInfo);
+                }
             }
         }
     }
@@ -259,7 +270,10 @@
         for (MdnsServiceBrowserListener listener : listeners) {
             final MdnsServiceInfo serviceInfo =
                     buildMdnsServiceInfoFromResponse(response, serviceTypeLabels);
-            listener.onServiceRemoved(serviceInfo);
+            if (response.isComplete()) {
+                listener.onServiceRemoved(serviceInfo);
+            }
+            listener.onServiceNameRemoved(serviceInfo);
         }
     }
 
@@ -423,7 +437,7 @@
                     Iterator<MdnsResponse> iter = instanceNameToResponse.values().iterator();
                     while (iter.hasNext()) {
                         MdnsResponse existingResponse = iter.next();
-                        if (existingResponse.isComplete()
+                        if (existingResponse.hasServiceRecord()
                                 && existingResponse
                                 .getServiceRecord()
                                 .getRemainingTTL(SystemClock.elapsedRealtime())
@@ -436,7 +450,10 @@
                                     final MdnsServiceInfo serviceInfo =
                                             buildMdnsServiceInfoFromResponse(
                                                     existingResponse, serviceTypeLabels);
-                                    listener.onServiceRemoved(serviceInfo);
+                                    if (existingResponse.isComplete()) {
+                                        listener.onServiceRemoved(serviceInfo);
+                                    }
+                                    listener.onServiceNameRemoved(serviceInfo);
                                 }
                             }
                         }
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 6f8b85a..462685a 100644
--- a/tests/unit/java/com/android/server/connectivity/mdns/MdnsServiceTypeClientTests.java
+++ b/tests/unit/java/com/android/server/connectivity/mdns/MdnsServiceTypeClientTests.java
@@ -18,6 +18,7 @@
 
 import static com.android.testutils.DevSdkIgnoreRuleKt.SC_V2;
 
+import static org.junit.Assert.assertArrayEquals;
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertFalse;
 import static org.junit.Assert.assertNull;
@@ -26,16 +27,18 @@
 import static org.mockito.ArgumentMatchers.anyLong;
 import static org.mockito.ArgumentMatchers.argThat;
 import static org.mockito.Mockito.doReturn;
+import static org.mockito.Mockito.inOrder;
 import static org.mockito.Mockito.mock;
 import static org.mockito.Mockito.never;
 import static org.mockito.Mockito.spy;
-import static org.mockito.Mockito.times;
 import static org.mockito.Mockito.verify;
 import static org.mockito.Mockito.when;
 
 import static java.nio.charset.StandardCharsets.UTF_8;
 
 import android.annotation.NonNull;
+import android.annotation.Nullable;
+import android.net.InetAddresses;
 import android.text.TextUtils;
 
 import com.android.server.connectivity.mdns.MdnsServiceInfo.TextEntry;
@@ -49,6 +52,7 @@
 import org.junit.runner.RunWith;
 import org.mockito.ArgumentCaptor;
 import org.mockito.Captor;
+import org.mockito.InOrder;
 import org.mockito.Mock;
 import org.mockito.Mockito;
 import org.mockito.MockitoAnnotations;
@@ -72,7 +76,7 @@
 @RunWith(DevSdkIgnoreRunner.class)
 @DevSdkIgnoreRule.IgnoreUpTo(SC_V2)
 public class MdnsServiceTypeClientTests {
-
+    private static final int INTERFACE_INDEX = 999;
     private static final String SERVICE_TYPE = "_googlecast._tcp.local";
     private static final String[] SERVICE_TYPE_LABELS = TextUtils.split(SERVICE_TYPE, "\\.");
 
@@ -379,15 +383,41 @@
         assertNull(currentThreadExecutor.getAndClearLastScheduledRunnable());
     }
 
+    private static void verifyServiceInfo(MdnsServiceInfo serviceInfo, String serviceName,
+            String[] serviceType, String ipv4Address, String ipv6Address, int port,
+            List<String> subTypes, Map<String, String> attributes, int interfaceIndex) {
+        assertEquals(serviceName, serviceInfo.getServiceInstanceName());
+        assertArrayEquals(serviceType, serviceInfo.getServiceType());
+        assertEquals(ipv4Address, serviceInfo.getIpv4Address());
+        assertEquals(ipv6Address, serviceInfo.getIpv6Address());
+        assertEquals(port, serviceInfo.getPort());
+        assertEquals(subTypes, serviceInfo.getSubtypes());
+        for (String key : attributes.keySet()) {
+            assertEquals(attributes.get(key), serviceInfo.getAttributeByKey(key));
+        }
+        assertEquals(interfaceIndex, serviceInfo.getInterfaceIndex());
+    }
+
     @Test
     public void processResponse_incompleteResponse() {
         client.startSendAndReceive(mockListenerOne, MdnsSearchOptions.getDefaultOptions());
 
         MdnsResponse response = mock(MdnsResponse.class);
         when(response.getServiceInstanceName()).thenReturn("service-instance-1");
+        doReturn(INTERFACE_INDEX).when(response).getInterfaceIndex();
         when(response.isComplete()).thenReturn(false);
 
         client.processResponse(response);
+        verify(mockListenerOne).onServiceNameDiscovered(serviceInfoCaptor.capture());
+        verifyServiceInfo(serviceInfoCaptor.getAllValues().get(0),
+                "service-instance-1",
+                SERVICE_TYPE_LABELS,
+                null /* ipv4Address */,
+                null /* ipv6Address */,
+                0 /* port */,
+                List.of() /* subTypes */,
+                Collections.singletonMap("key", null) /* attributes */,
+                INTERFACE_INDEX);
 
         verify(mockListenerOne, never()).onServiceFound(any(MdnsServiceInfo.class));
         verify(mockListenerOne, never()).onServiceUpdated(any(MdnsServiceInfo.class));
@@ -404,7 +434,7 @@
                         "service-instance-1",
                         ipV4Address,
                         5353,
-                        Collections.singletonList("ABCDE"),
+                        /* subtype= */ "ABCDE",
                         Collections.emptyMap(),
                         /* interfaceIndex= */ 20);
         client.processResponse(initialResponse);
@@ -415,14 +445,26 @@
                         "service-instance-1",
                         ipV4Address,
                         5354,
-                        Collections.singletonList("ABCDE"),
+                        /* subtype= */ "ABCDE",
                         Collections.singletonMap("key", "value"),
                         /* interfaceIndex= */ 20);
         client.processResponse(secondResponse);
 
+        // Verify onServiceNameDiscovered was called once for the initial response.
+        verify(mockListenerOne).onServiceNameDiscovered(serviceInfoCaptor.capture());
+        verifyServiceInfo(serviceInfoCaptor.getAllValues().get(0),
+                "service-instance-1",
+                SERVICE_TYPE_LABELS,
+                ipV4Address /* ipv4Address */,
+                null /* ipv6Address */,
+                5353 /* port */,
+                Collections.singletonList("ABCDE") /* subTypes */,
+                Collections.singletonMap("key", null) /* attributes */,
+                20 /* interfaceIndex */);
+
         // Verify onServiceFound was called once for the initial response.
         verify(mockListenerOne).onServiceFound(serviceInfoCaptor.capture());
-        MdnsServiceInfo initialServiceInfo = serviceInfoCaptor.getAllValues().get(0);
+        MdnsServiceInfo initialServiceInfo = serviceInfoCaptor.getAllValues().get(1);
         assertEquals(initialServiceInfo.getServiceInstanceName(), "service-instance-1");
         assertEquals(initialServiceInfo.getIpv4Address(), ipV4Address);
         assertEquals(initialServiceInfo.getPort(), 5353);
@@ -432,7 +474,7 @@
 
         // Verify onServiceUpdated was called once for the second response.
         verify(mockListenerOne).onServiceUpdated(serviceInfoCaptor.capture());
-        MdnsServiceInfo updatedServiceInfo = serviceInfoCaptor.getAllValues().get(1);
+        MdnsServiceInfo updatedServiceInfo = serviceInfoCaptor.getAllValues().get(2);
         assertEquals(updatedServiceInfo.getServiceInstanceName(), "service-instance-1");
         assertEquals(updatedServiceInfo.getIpv4Address(), ipV4Address);
         assertEquals(updatedServiceInfo.getPort(), 5354);
@@ -453,7 +495,7 @@
                         "service-instance-1",
                         ipV6Address,
                         5353,
-                        Collections.singletonList("ABCDE"),
+                        /* subtype= */ "ABCDE",
                         Collections.emptyMap(),
                         /* interfaceIndex= */ 20);
         client.processResponse(initialResponse);
@@ -464,7 +506,7 @@
                         "service-instance-1",
                         ipV6Address,
                         5354,
-                        Collections.singletonList("ABCDE"),
+                        /* subtype= */ "ABCDE",
                         Collections.singletonMap("key", "value"),
                         /* interfaceIndex= */ 20);
         client.processResponse(secondResponse);
@@ -472,9 +514,21 @@
         System.out.println("secondResponses ip"
                 + secondResponse.getInet6AddressRecord().getInet6Address().getHostAddress());
 
+        // Verify onServiceNameDiscovered was called once for the initial response.
+        verify(mockListenerOne).onServiceNameDiscovered(serviceInfoCaptor.capture());
+        verifyServiceInfo(serviceInfoCaptor.getAllValues().get(0),
+                "service-instance-1",
+                SERVICE_TYPE_LABELS,
+                null /* ipv4Address */,
+                ipV6Address /* ipv6Address */,
+                5353 /* port */,
+                Collections.singletonList("ABCDE") /* subTypes */,
+                Collections.singletonMap("key", null) /* attributes */,
+                20 /* interfaceIndex */);
+
         // Verify onServiceFound was called once for the initial response.
         verify(mockListenerOne).onServiceFound(serviceInfoCaptor.capture());
-        MdnsServiceInfo initialServiceInfo = serviceInfoCaptor.getAllValues().get(0);
+        MdnsServiceInfo initialServiceInfo = serviceInfoCaptor.getAllValues().get(1);
         assertEquals(initialServiceInfo.getServiceInstanceName(), "service-instance-1");
         assertEquals(initialServiceInfo.getIpv6Address(), ipV6Address);
         assertEquals(initialServiceInfo.getPort(), 5353);
@@ -484,7 +538,7 @@
 
         // Verify onServiceUpdated was called once for the second response.
         verify(mockListenerOne).onServiceUpdated(serviceInfoCaptor.capture());
-        MdnsServiceInfo updatedServiceInfo = serviceInfoCaptor.getAllValues().get(1);
+        MdnsServiceInfo updatedServiceInfo = serviceInfoCaptor.getAllValues().get(2);
         assertEquals(updatedServiceInfo.getServiceInstanceName(), "service-instance-1");
         assertEquals(updatedServiceInfo.getIpv6Address(), ipV6Address);
         assertEquals(updatedServiceInfo.getPort(), 5354);
@@ -494,6 +548,23 @@
         assertEquals(updatedServiceInfo.getInterfaceIndex(), 20);
     }
 
+    private void verifyServiceRemovedNoCallback(MdnsServiceBrowserListener listener) {
+        verify(listener, never()).onServiceRemoved(any());
+        verify(listener, never()).onServiceNameRemoved(any());
+    }
+
+    private void verifyServiceRemovedCallback(MdnsServiceBrowserListener listener,
+            String serviceName, String[] serviceType, int interfaceIndex) {
+        verify(listener).onServiceRemoved(argThat(
+                info -> serviceName.equals(info.getServiceInstanceName())
+                        && Arrays.equals(serviceType, info.getServiceType())
+                        && info.getInterfaceIndex() == interfaceIndex));
+        verify(listener).onServiceNameRemoved(argThat(
+                info -> serviceName.equals(info.getServiceInstanceName())
+                        && Arrays.equals(serviceType, info.getServiceType())
+                        && info.getInterfaceIndex() == interfaceIndex));
+    }
+
     @Test
     public void processResponse_goodBye() throws Exception {
         client.startSendAndReceive(mockListenerOne, MdnsSearchOptions.getDefaultOptions());
@@ -501,37 +572,32 @@
 
         final String serviceName = "service-instance-1";
         final String ipV6Address = "2000:3333::da6c:63ff:fe7c:7483";
-        final int interfaceIndex = 999;
         // Process the initial response.
         final MdnsResponse initialResponse =
                 createResponse(
                         serviceName,
                         ipV6Address,
                         5353 /* port */,
-                        Collections.singletonList("ABCDE"),
+                        /* subtype= */ "ABCDE",
                         Collections.emptyMap(),
-                        interfaceIndex);
+                        INTERFACE_INDEX);
         client.processResponse(initialResponse);
         MdnsResponse response = mock(MdnsResponse.class);
         doReturn("goodbye-service").when(response).getServiceInstanceName();
-        doReturn(interfaceIndex).when(response).getInterfaceIndex();
+        doReturn(INTERFACE_INDEX).when(response).getInterfaceIndex();
         doReturn(true).when(response).isGoodbye();
         client.processResponse(response);
-        // Verify onServiceRemoved won't be called if the service is not existed.
-        verify(mockListenerOne, never()).onServiceRemoved(any());
-        verify(mockListenerTwo, never()).onServiceRemoved(any());
+        // Verify removed callback won't be called if the service is not existed.
+        verifyServiceRemovedNoCallback(mockListenerOne);
+        verifyServiceRemovedNoCallback(mockListenerTwo);
 
-        // Verify onServiceRemoved would be called.
+        // Verify removed callback would be called.
         doReturn(serviceName).when(response).getServiceInstanceName();
         client.processResponse(response);
-        verify(mockListenerOne).onServiceRemoved(argThat(
-                info -> serviceName.equals(info.getServiceInstanceName())
-                        && Arrays.equals(SERVICE_TYPE_LABELS, info.getServiceType())
-                        && info.getInterfaceIndex() == interfaceIndex));
-        verify(mockListenerTwo).onServiceRemoved(argThat(
-                info -> serviceName.equals(info.getServiceInstanceName())
-                        && Arrays.equals(SERVICE_TYPE_LABELS, info.getServiceType())
-                        && info.getInterfaceIndex() == interfaceIndex));
+        verifyServiceRemovedCallback(
+                mockListenerOne, serviceName, SERVICE_TYPE_LABELS, INTERFACE_INDEX);
+        verifyServiceRemovedCallback(
+                mockListenerTwo, serviceName, SERVICE_TYPE_LABELS, INTERFACE_INDEX);
     }
 
     @Test
@@ -542,15 +608,28 @@
                         "service-instance-1",
                         "192.168.1.1",
                         5353,
-                        Collections.singletonList("ABCDE"),
-                        Collections.emptyMap());
+                        /* subtype= */ "ABCDE",
+                        Collections.emptyMap(),
+                        INTERFACE_INDEX);
         client.processResponse(initialResponse);
 
         client.startSendAndReceive(mockListenerOne, MdnsSearchOptions.getDefaultOptions());
 
+        // Verify onServiceNameDiscovered was called once for the existing response.
+        verify(mockListenerOne).onServiceNameDiscovered(serviceInfoCaptor.capture());
+        verifyServiceInfo(serviceInfoCaptor.getAllValues().get(0),
+                "service-instance-1",
+                SERVICE_TYPE_LABELS,
+                "192.168.1.1" /* ipv4Address */,
+                null /* ipv6Address */,
+                5353 /* port */,
+                Collections.singletonList("ABCDE") /* subTypes */,
+                Collections.singletonMap("key", null) /* attributes */,
+                INTERFACE_INDEX);
+
         // Verify onServiceFound was called once for the existing response.
         verify(mockListenerOne).onServiceFound(serviceInfoCaptor.capture());
-        MdnsServiceInfo existingServiceInfo = serviceInfoCaptor.getAllValues().get(0);
+        MdnsServiceInfo existingServiceInfo = serviceInfoCaptor.getAllValues().get(1);
         assertEquals(existingServiceInfo.getServiceInstanceName(), "service-instance-1");
         assertEquals(existingServiceInfo.getIpv4Address(), "192.168.1.1");
         assertEquals(existingServiceInfo.getPort(), 5353);
@@ -567,6 +646,7 @@
 
         // Verify onServiceFound was not called on the newly registered listener after the existing
         // response is gone.
+        verify(mockListenerTwo, never()).onServiceNameDiscovered(any(MdnsServiceInfo.class));
         verify(mockListenerTwo, never()).onServiceFound(any(MdnsServiceInfo.class));
     }
 
@@ -580,9 +660,9 @@
 
         // Process the initial response.
         MdnsResponse initialResponse =
-                createResponse(
+                createMockResponse(
                         serviceInstanceName, "192.168.1.1", 5353, List.of("ABCDE"),
-                        Map.of());
+                        Map.of(), INTERFACE_INDEX);
         client.processResponse(initialResponse);
 
         // Clear the scheduled runnable.
@@ -592,8 +672,8 @@
         when(initialResponse.getServiceRecord().getRemainingTTL(anyLong())).thenReturn((long) 0);
         firstMdnsTask.run();
 
-        // Verify onServiceRemoved was not called.
-        verify(mockListenerOne, never()).onServiceRemoved(any());
+        // Verify removed callback was not called.
+        verifyServiceRemovedNoCallback(mockListenerOne);
     }
 
     @Test
@@ -614,9 +694,9 @@
 
         // Process the initial response.
         MdnsResponse initialResponse =
-                createResponse(
+                createMockResponse(
                         serviceInstanceName, "192.168.1.1", 5353, List.of("ABCDE"),
-                        Map.of(), 999 /* interfaceIndex */);
+                        Map.of(), INTERFACE_INDEX);
         client.processResponse(initialResponse);
 
         // Clear the scheduled runnable.
@@ -626,18 +706,16 @@
         when(initialResponse.getServiceRecord().getRemainingTTL(anyLong())).thenReturn((long) 1000);
         firstMdnsTask.run();
 
-        // Verify onServiceRemoved was not called.
-        verify(mockListenerOne, never()).onServiceRemoved(any());
+        // Verify removed callback was not called.
+        verifyServiceRemovedNoCallback(mockListenerOne);
 
         // Simulate the case where the response is after TTL.
         when(initialResponse.getServiceRecord().getRemainingTTL(anyLong())).thenReturn((long) 0);
         firstMdnsTask.run();
 
-        // Verify onServiceRemoved was called.
-        verify(mockListenerOne, times(1)).onServiceRemoved(argThat(
-                info -> serviceInstanceName.equals(info.getServiceInstanceName())
-                        && Arrays.equals(SERVICE_TYPE_LABELS, info.getServiceType())
-                        && info.getInterfaceIndex() == 999));
+        // Verify removed callback was called.
+        verifyServiceRemovedCallback(
+                mockListenerOne, serviceInstanceName, SERVICE_TYPE_LABELS, INTERFACE_INDEX);
     }
 
     @Test
@@ -656,9 +734,9 @@
 
         // Process the initial response.
         MdnsResponse initialResponse =
-                createResponse(
+                createMockResponse(
                         serviceInstanceName, "192.168.1.1", 5353, List.of("ABCDE"),
-                        Map.of());
+                        Map.of(), INTERFACE_INDEX);
         client.processResponse(initialResponse);
 
         // Clear the scheduled runnable.
@@ -668,8 +746,8 @@
         when(initialResponse.getServiceRecord().getRemainingTTL(anyLong())).thenReturn((long) 0);
         firstMdnsTask.run();
 
-        // Verify onServiceRemoved was not called.
-        verify(mockListenerOne, never()).onServiceRemoved(any());
+        // Verify removed callback was not called.
+        verifyServiceRemovedNoCallback(mockListenerOne);
     }
 
     @Test
@@ -690,9 +768,9 @@
 
         // Process the initial response.
         MdnsResponse initialResponse =
-                createResponse(
+                createMockResponse(
                         serviceInstanceName, "192.168.1.1", 5353, List.of("ABCDE"),
-                        Map.of(), 999 /* interfaceIndex */);
+                        Map.of(), INTERFACE_INDEX);
         client.processResponse(initialResponse);
 
         // Clear the scheduled runnable.
@@ -702,11 +780,117 @@
         when(initialResponse.getServiceRecord().getRemainingTTL(anyLong())).thenReturn((long) 0);
         firstMdnsTask.run();
 
-        // Verify onServiceRemoved was called.
-        verify(mockListenerOne, times(1)).onServiceRemoved(argThat(
-                info -> serviceInstanceName.equals(info.getServiceInstanceName())
-                        && Arrays.equals(SERVICE_TYPE_LABELS, info.getServiceType())
-                        && info.getInterfaceIndex() == 999));
+        // Verify removed callback was called.
+        verifyServiceRemovedCallback(
+                mockListenerOne, serviceInstanceName, SERVICE_TYPE_LABELS, INTERFACE_INDEX);
+    }
+
+    @Test
+    public void testProcessResponse_InOrder() throws Exception {
+        final String serviceName = "service-instance";
+        final String ipV4Address = "192.0.2.0";
+        final String ipV6Address = "2001:db8::";
+        client.startSendAndReceive(mockListenerOne, MdnsSearchOptions.getDefaultOptions());
+        InOrder inOrder = inOrder(mockListenerOne);
+
+        // Process the initial response which is incomplete.
+        final MdnsResponse initialResponse =
+                createResponse(
+                        serviceName,
+                        null,
+                        5353,
+                        "ABCDE" /* subtype */,
+                        Collections.emptyMap(),
+                        INTERFACE_INDEX);
+        client.processResponse(initialResponse);
+
+        // Process a second response which has ip address to make response become complete.
+        final MdnsResponse secondResponse =
+                createResponse(
+                        serviceName,
+                        ipV4Address,
+                        5353,
+                        "ABCDE" /* subtype */,
+                        Collections.emptyMap(),
+                        INTERFACE_INDEX);
+        client.processResponse(secondResponse);
+
+        // Process a third response with a different ip address, port and updated text attributes.
+        final MdnsResponse thirdResponse =
+                createResponse(
+                        serviceName,
+                        ipV6Address,
+                        5354,
+                        "ABCDE" /* subtype */,
+                        Collections.singletonMap("key", "value"),
+                        INTERFACE_INDEX);
+        client.processResponse(thirdResponse);
+
+        // Process the last response which is goodbye message.
+        final MdnsResponse lastResponse = mock(MdnsResponse.class);
+        doReturn(serviceName).when(lastResponse).getServiceInstanceName();
+        doReturn(true).when(lastResponse).isGoodbye();
+        client.processResponse(lastResponse);
+
+        // Verify onServiceNameDiscovered was first called for the initial response.
+        inOrder.verify(mockListenerOne).onServiceNameDiscovered(serviceInfoCaptor.capture());
+        verifyServiceInfo(serviceInfoCaptor.getAllValues().get(0),
+                serviceName,
+                SERVICE_TYPE_LABELS,
+                null /* ipv4Address */,
+                null /* ipv6Address */,
+                5353 /* port */,
+                Collections.singletonList("ABCDE") /* subTypes */,
+                Collections.singletonMap("key", null) /* attributes */,
+                INTERFACE_INDEX);
+
+        // Verify onServiceFound was second called for the second response.
+        inOrder.verify(mockListenerOne).onServiceFound(serviceInfoCaptor.capture());
+        verifyServiceInfo(serviceInfoCaptor.getAllValues().get(1),
+                serviceName,
+                SERVICE_TYPE_LABELS,
+                ipV4Address /* ipv4Address */,
+                null /* ipv6Address */,
+                5353 /* port */,
+                Collections.singletonList("ABCDE") /* subTypes */,
+                Collections.singletonMap("key", null) /* attributes */,
+                INTERFACE_INDEX);
+
+        // Verify onServiceUpdated was third called for the third response.
+        inOrder.verify(mockListenerOne).onServiceUpdated(serviceInfoCaptor.capture());
+        verifyServiceInfo(serviceInfoCaptor.getAllValues().get(2),
+                serviceName,
+                SERVICE_TYPE_LABELS,
+                ipV4Address /* ipv4Address */,
+                ipV6Address /* ipv6Address */,
+                5354 /* port */,
+                Collections.singletonList("ABCDE") /* subTypes */,
+                Collections.singletonMap("key", "value") /* attributes */,
+                INTERFACE_INDEX);
+
+        // Verify onServiceRemoved was called for the last response.
+        inOrder.verify(mockListenerOne).onServiceRemoved(serviceInfoCaptor.capture());
+        verifyServiceInfo(serviceInfoCaptor.getAllValues().get(3),
+                serviceName,
+                SERVICE_TYPE_LABELS,
+                ipV4Address /* ipv4Address */,
+                ipV6Address /* ipv6Address */,
+                5354 /* port */,
+                Collections.singletonList("ABCDE") /* subTypes */,
+                Collections.singletonMap("key", "value") /* attributes */,
+                INTERFACE_INDEX);
+
+        // Verify onServiceNameRemoved was called for the last response.
+        inOrder.verify(mockListenerOne).onServiceNameRemoved(serviceInfoCaptor.capture());
+        verifyServiceInfo(serviceInfoCaptor.getAllValues().get(4),
+                serviceName,
+                SERVICE_TYPE_LABELS,
+                ipV4Address /* ipv4Address */,
+                ipV6Address /* ipv6Address */,
+                5354 /* port */,
+                Collections.singletonList("ABCDE") /* subTypes */,
+                Collections.singletonMap("key", "value") /* attributes */,
+                INTERFACE_INDEX);
     }
 
     // verifies that the right query was enqueued with the right delay, and send query by executing
@@ -771,19 +955,8 @@
         }
     }
 
-    private MdnsResponse createResponse(
-            @NonNull String serviceInstanceName,
-            @NonNull String host,
-            int port,
-            @NonNull List<String> subtypes,
-            @NonNull Map<String, String> textAttributes)
-            throws Exception {
-        return createResponse(serviceInstanceName, host, port, subtypes, textAttributes,
-                /* interfaceIndex= */ -1);
-    }
-
-    // Creates a complete mDNS response.
-    private MdnsResponse createResponse(
+    // Creates a mock mDNS response.
+    private MdnsResponse createMockResponse(
             @NonNull String serviceInstanceName,
             @NonNull String host,
             int port,
@@ -830,4 +1003,73 @@
         doReturn(new ArrayList<>(subtypes)).when(response).getSubtypes();
         return response;
     }
+
+    // Creates a mDNS response.
+    private MdnsResponse createResponse(
+            @NonNull String serviceInstanceName,
+            @Nullable String host,
+            int port,
+            @NonNull String subtype,
+            @NonNull Map<String, String> textAttributes,
+            int interfaceIndex)
+            throws Exception {
+        MdnsResponse response = new MdnsResponse(0);
+        response.setInterfaceIndex(interfaceIndex);
+
+        // Set PTR record
+        final MdnsPointerRecord pointerRecord = new MdnsPointerRecord(
+                new String[]{subtype, MdnsConstants.SUBTYPE_LABEL, "test"} /* name */,
+                0L /* receiptTimeMillis */,
+                false /* cacheFlush */,
+                120000L /* ttlMillis */,
+                new String[]{serviceInstanceName});
+        response.addPointerRecord(pointerRecord);
+
+        // Set SRV record.
+        final MdnsServiceRecord serviceRecord = new MdnsServiceRecord(
+                new String[] {"service"} /* name */,
+                0L /* receiptTimeMillis */,
+                false /* cacheFlush */,
+                120000L /* ttlMillis */,
+                0 /* servicePriority */,
+                0 /* serviceWeight */,
+                port,
+                new String[]{"hostname"});
+        response.setServiceRecord(serviceRecord);
+
+        // Set A/AAAA record.
+        if (host != null) {
+            if (InetAddresses.parseNumericAddress(host) instanceof Inet6Address) {
+                final MdnsInetAddressRecord inetAddressRecord = new MdnsInetAddressRecord(
+                        new String[] {"address"} /* name */,
+                        0L /* receiptTimeMillis */,
+                        false /* cacheFlush */,
+                        120000L /* ttlMillis */,
+                        Inet6Address.getByName(host));
+                response.setInet6AddressRecord(inetAddressRecord);
+            } else {
+                final MdnsInetAddressRecord inetAddressRecord = new MdnsInetAddressRecord(
+                        new String[] {"address"} /* name */,
+                        0L /* receiptTimeMillis */,
+                        false /* cacheFlush */,
+                        120000L /* ttlMillis */,
+                        Inet4Address.getByName(host));
+                response.setInet4AddressRecord(inetAddressRecord);
+            }
+        }
+
+        // Set TXT record.
+        final List<TextEntry> textEntries = new ArrayList<>();
+        for (Map.Entry<String, String> kv : textAttributes.entrySet()) {
+            textEntries.add(new TextEntry(kv.getKey(), kv.getValue().getBytes(UTF_8)));
+        }
+        final MdnsTextRecord textRecord = new MdnsTextRecord(
+                new String[] {"text"} /* name */,
+                0L /* receiptTimeMillis */,
+                false /* cacheFlush */,
+                120000L /* ttlMillis */,
+                textEntries);
+        response.setTextRecord(textRecord);
+        return response;
+    }
 }
\ No newline at end of file