diff --git a/service-t/src/com/android/server/mdns/MdnsNsecRecord.java b/service-t/src/com/android/server/mdns/MdnsNsecRecord.java
index 06fdd5e..6ec2f99 100644
--- a/service-t/src/com/android/server/mdns/MdnsNsecRecord.java
+++ b/service-t/src/com/android/server/mdns/MdnsNsecRecord.java
@@ -17,12 +17,14 @@
 package com.android.server.connectivity.mdns;
 
 import android.net.DnsResolver;
+import android.text.TextUtils;
 
 import com.android.net.module.util.CollectionUtils;
 
 import java.io.IOException;
 import java.util.ArrayList;
 import java.util.Arrays;
+import java.util.Objects;
 
 /**
  * A mDNS "NSEC" record, used in particular for negative responses (RFC6762 6.1).
@@ -140,4 +142,30 @@
         writer.writeUInt8(bytesInBlock);
         writer.writeBytes(bytes);
     }
+
+    @Override
+    public String toString() {
+        return "NSEC: NextDomain: " + TextUtils.join(".", mNextDomain)
+                + " Types " + Arrays.toString(mTypes);
+    }
+
+    @Override
+    public int hashCode() {
+        return Objects.hash(super.hashCode(),
+                Arrays.hashCode(mNextDomain), Arrays.hashCode(mTypes));
+    }
+
+    @Override
+    public boolean equals(Object other) {
+        if (this == other) {
+            return true;
+        }
+        if (!(other instanceof MdnsNsecRecord)) {
+            return false;
+        }
+
+        return super.equals(other)
+                && Arrays.equals(mNextDomain, ((MdnsNsecRecord) other).mNextDomain)
+                && Arrays.equals(mTypes, ((MdnsNsecRecord) other).mTypes);
+    }
 }
diff --git a/service-t/src/com/android/server/mdns/MdnsRecordRepository.java b/service-t/src/com/android/server/mdns/MdnsRecordRepository.java
index bb9c751..5915f8b 100644
--- a/service-t/src/com/android/server/mdns/MdnsRecordRepository.java
+++ b/service-t/src/com/android/server/mdns/MdnsRecordRepository.java
@@ -18,21 +18,31 @@
 
 import android.annotation.NonNull;
 import android.annotation.Nullable;
+import android.annotation.TargetApi;
 import android.net.LinkAddress;
 import android.net.nsd.NsdServiceInfo;
+import android.os.Build;
 import android.os.Looper;
+import android.util.ArraySet;
 import android.util.SparseArray;
 
 import com.android.internal.annotations.VisibleForTesting;
+import com.android.net.module.util.CollectionUtils;
+import com.android.net.module.util.HexDump;
 
 import java.io.IOException;
+import java.net.Inet4Address;
 import java.net.InetAddress;
 import java.net.NetworkInterface;
 import java.util.ArrayList;
+import java.util.Arrays;
 import java.util.Collections;
 import java.util.Enumeration;
+import java.util.Iterator;
 import java.util.List;
 import java.util.Map;
+import java.util.Set;
+import java.util.TreeMap;
 import java.util.UUID;
 import java.util.concurrent.TimeUnit;
 
@@ -41,6 +51,7 @@
  *
  * Must be used on a consistent looper thread.
  */
+@TargetApi(Build.VERSION_CODES.TIRAMISU) // Allow calling T+ APIs; this is only loaded on T+
 public class MdnsRecordRepository {
     // TTLs as per RFC6762 10.
     // TTL for records with a host name as the resource record's name (e.g., A, AAAA, HINFO) or a
@@ -61,6 +72,8 @@
     @NonNull
     private final SparseArray<ServiceRegistration> mServices = new SparseArray<>();
     @NonNull
+    private final List<RecordInfo<?>> mGeneralRecords = new ArrayList<>();
+    @NonNull
     private final Looper mLooper;
     @NonNull
     private String[] mDeviceHostname;
@@ -221,7 +234,29 @@
      * Inform the repository of the latest interface addresses.
      */
     public void updateAddresses(@NonNull List<LinkAddress> newAddresses) {
-        // TODO: implement to update addresses in records
+        mGeneralRecords.clear();
+        for (LinkAddress addr : newAddresses) {
+            final String[] revDnsAddr = getReverseDnsAddress(addr.getAddress());
+            mGeneralRecords.add(new RecordInfo<>(
+                    null /* serviceInfo */,
+                    new MdnsPointerRecord(
+                            revDnsAddr,
+                            0L /* receiptTimeMillis */,
+                            true /* cacheFlush */,
+                            NAME_RECORDS_TTL_MILLIS,
+                            mDeviceHostname),
+                    false /* sharedName */, false /* probing */));
+
+            mGeneralRecords.add(new RecordInfo<>(
+                    null /* serviceInfo */,
+                    new MdnsInetAddressRecord(
+                            mDeviceHostname,
+                            0L /* receiptTimeMillis */,
+                            true /* cacheFlush */,
+                            NAME_RECORDS_TTL_MILLIS,
+                            addr.getAddress()),
+                    false /* sharedName */, false /* probing */));
+        }
     }
 
     /**
@@ -338,14 +373,109 @@
     }
 
     /**
+     * Add NSEC records indicating that the response records are unique.
+     *
+     * Following RFC6762 6.1:
+     * "On receipt of a question for a particular name, rrtype, and rrclass, for which a responder
+     * does have one or more unique answers, the responder MAY also include an NSEC record in the
+     * Additional Record Section indicating the nonexistence of other rrtypes for that name and
+     * rrclass."
+     * @param destinationList List to add the NSEC records to.
+     * @param answerRecords Lists of answered records based on which to add NSEC records (typically
+     *                      answer and additionalAnswer sections)
+     */
+    @SafeVarargs
+    private static void addNsecRecordsForUniqueNames(
+            List<MdnsRecord> destinationList,
+            Iterator<RecordInfo<?>>... answerRecords) {
+        // Group unique records by name. Use a TreeMap with comparator as arrays don't implement
+        // equals / hashCode.
+        final Map<String[], List<MdnsRecord>> nsecByName = new TreeMap<>(Arrays::compare);
+        // But keep the list of names in added order, otherwise records would be sorted in
+        // alphabetical order instead of the order of the original records, which would look like
+        // inconsistent behavior depending on service name.
+        final List<String[]> namesInAddedOrder = new ArrayList<>();
+        for (Iterator<RecordInfo<?>> answers : answerRecords) {
+            addNonSharedRecordsToMap(answers, nsecByName, namesInAddedOrder);
+        }
+
+        for (String[] nsecName : namesInAddedOrder) {
+            final List<MdnsRecord> entryRecords = nsecByName.get(nsecName);
+            long minTtl = Long.MAX_VALUE;
+            final Set<Integer> types = new ArraySet<>(entryRecords.size());
+            for (MdnsRecord record : entryRecords) {
+                if (minTtl > record.getTtl()) minTtl = record.getTtl();
+                types.add(record.getType());
+            }
+
+            destinationList.add(new MdnsNsecRecord(
+                    nsecName,
+                    0L /* receiptTimeMillis */,
+                    true /* cacheFlush */,
+                    minTtl,
+                    nsecName,
+                    CollectionUtils.toIntArray(types)));
+        }
+    }
+
+    /**
+     * Add non-shared records to a map listing them by record name, and to a list of names that
+     * remembers the adding order.
+     *
+     * In the destination map records are grouped by name; so the map has one key per record name,
+     * and the values are the lists of different records that share the same name.
+     * @param records Records to scan.
+     * @param dest Map to add the records to.
+     * @param namesInAddedOrder List of names to add the names in order, keeping the first
+     *                          occurrence of each name.
+     */
+    private static void addNonSharedRecordsToMap(
+            Iterator<RecordInfo<?>> records,
+            Map<String[], List<MdnsRecord>> dest,
+            List<String[]> namesInAddedOrder) {
+        while (records.hasNext()) {
+            final RecordInfo<?> record = records.next();
+            if (record.isSharedName) continue;
+            final List<MdnsRecord> recordsForName = dest.computeIfAbsent(record.record.name,
+                    key -> {
+                        namesInAddedOrder.add(key);
+                        return new ArrayList<>();
+                    });
+            recordsForName.add(record.record);
+        }
+    }
+
+    /**
      * Called to indicate that probing succeeded for a service.
      * @param probeSuccessInfo The successful probing info.
      * @return The {@link MdnsAnnouncer.AnnouncementInfo} to send, now that probing has succeeded.
      */
     public MdnsAnnouncer.AnnouncementInfo onProbingSucceeded(
-            MdnsProber.ProbingInfo probeSuccessInfo) throws IOException {
-        // TODO: implement: set service as not probing anymore and generate announcements
-        throw new IOException("Announcements not implemented");
+            MdnsProber.ProbingInfo probeSuccessInfo)
+            throws IOException {
+
+        final ServiceRegistration registration = mServices.get(probeSuccessInfo.getServiceId());
+        if (registration == null) throw new IOException(
+                "Service is not registered: " + probeSuccessInfo.getServiceId());
+        registration.setProbing(false);
+
+        final ArrayList<MdnsRecord> answers = new ArrayList<>();
+        final ArrayList<MdnsRecord> additionalAnswers = new ArrayList<>();
+
+        // Interface address records in general records
+        for (RecordInfo<?> record : mGeneralRecords) {
+            answers.add(record.record);
+        }
+
+        // All service records
+        for (RecordInfo<?> info : registration.allRecords) {
+            answers.add(info.record);
+        }
+
+        addNsecRecordsForUniqueNames(additionalAnswers,
+                mGeneralRecords.iterator(), registration.allRecords.iterator());
+
+        return new MdnsAnnouncer.AnnouncementInfo(answers, additionalAnswers);
     }
 
     /**
@@ -371,6 +501,37 @@
         return registration.srvRecord.isProbing;
     }
 
+    /**
+     * Compute:
+     * 2001:db8::1 --> 1.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.8.B.D.1.0.0.2.ip6.arpa
+     *
+     * Or:
+     * 192.0.2.123 --> 123.2.0.192.in-addr.arpa
+     */
+    @VisibleForTesting
+    public static String[] getReverseDnsAddress(@NonNull InetAddress addr) {
+        // xxx.xxx.xxx.xxx.in-addr.arpa (up to 28 characters)
+        // or 32 hex characters separated by dots + .ip6.arpa
+        final byte[] addrBytes = addr.getAddress();
+        final List<String> out = new ArrayList<>();
+        if (addr instanceof Inet4Address) {
+            for (int i = addrBytes.length - 1; i >= 0; i--) {
+                out.add(String.valueOf(Byte.toUnsignedInt(addrBytes[i])));
+            }
+            out.add("in-addr");
+        } else {
+            final String hexAddr = HexDump.toHexString(addrBytes);
+
+            for (int i = hexAddr.length() - 1; i >= 0; i--) {
+                out.add(String.valueOf(hexAddr.charAt(i)));
+            }
+            out.add("ip6");
+        }
+        out.add("arpa");
+
+        return out.toArray(new String[0]);
+    }
+
     private static String[] splitFullyQualifiedName(
             @NonNull NsdServiceInfo info, @NonNull String[] serviceType) {
         final String[] split = new String[serviceType.length + 1];
diff --git a/tests/unit/java/com/android/server/connectivity/mdns/MdnsAnnouncerTest.kt b/tests/unit/java/com/android/server/connectivity/mdns/MdnsAnnouncerTest.kt
index 961f0f0..abb2627 100644
--- a/tests/unit/java/com/android/server/connectivity/mdns/MdnsAnnouncerTest.kt
+++ b/tests/unit/java/com/android/server/connectivity/mdns/MdnsAnnouncerTest.kt
@@ -22,11 +22,10 @@
 import android.os.SystemClock
 import com.android.internal.util.HexDump
 import com.android.server.connectivity.mdns.MdnsAnnouncer.AnnouncementInfo
+import com.android.server.connectivity.mdns.MdnsRecordRepository.getReverseDnsAddress
 import com.android.testutils.DevSdkIgnoreRule.IgnoreUpTo
 import com.android.testutils.DevSdkIgnoreRunner
 import java.net.DatagramPacket
-import java.net.Inet6Address
-import java.net.InetAddress
 import kotlin.test.assertEquals
 import kotlin.test.assertTrue
 import org.junit.After
@@ -150,8 +149,8 @@
         val v6Addr1 = parseNumericAddress("2001:DB8::123")
         val v6Addr2 = parseNumericAddress("2001:DB8::456")
         val v4AddrRev = arrayOf("123", "0", "2", "192", "in-addr", "arpa")
-        val v6Addr1Rev = getReverseV6AddressName(v6Addr1)
-        val v6Addr2Rev = getReverseV6AddressName(v6Addr2)
+        val v6Addr1Rev = getReverseDnsAddress(v6Addr1)
+        val v6Addr2Rev = getReverseDnsAddress(v6Addr2)
 
         val announcedRecords = listOf(
                 // Reverse address records
@@ -267,13 +266,3 @@
         }
     }
 }
-
-/**
- * Compute 2001:db8::1 --> 1.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.8.B.D.1.0.0.2.ip6.arpa
- */
-private fun getReverseV6AddressName(addr: InetAddress): Array<String> {
-    assertTrue(addr is Inet6Address)
-    return addr.address.flatMapTo(mutableListOf("arpa", "ip6")) {
-        HexDump.toHexString(it).toCharArray().map(Char::toString)
-    }.reversed().toTypedArray()
-}
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 ad22305..bcfcf1d 100644
--- a/tests/unit/java/com/android/server/connectivity/mdns/MdnsInterfaceAdvertiserTest.kt
+++ b/tests/unit/java/com/android/server/connectivity/mdns/MdnsInterfaceAdvertiserTest.kt
@@ -121,6 +121,8 @@
         doReturn(testExitInfo).`when`(repository).exitService(TEST_SERVICE_ID_1)
         advertiser.removeService(TEST_SERVICE_ID_1)
 
+        verify(prober).stop(TEST_SERVICE_ID_1)
+        verify(announcer).stop(TEST_SERVICE_ID_1)
         verify(announcer).startSending(TEST_SERVICE_ID_1, testExitInfo, EXIT_ANNOUNCEMENT_DELAY_MS)
 
         // TODO: after exit announcements are implemented, verify that announceCb.onFinished causes
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 502a36a..aa249e5 100644
--- a/tests/unit/java/com/android/server/connectivity/mdns/MdnsRecordRepositoryTest.kt
+++ b/tests/unit/java/com/android/server/connectivity/mdns/MdnsRecordRepositoryTest.kt
@@ -17,10 +17,12 @@
 package com.android.server.connectivity.mdns
 
 import android.net.InetAddresses.parseNumericAddress
+import android.net.LinkAddress
 import android.net.nsd.NsdServiceInfo
 import android.os.Build
 import android.os.HandlerThread
 import com.android.server.connectivity.mdns.MdnsRecordRepository.Dependencies
+import com.android.server.connectivity.mdns.MdnsRecordRepository.getReverseDnsAddress
 import com.android.testutils.DevSdkIgnoreRule
 import com.android.testutils.DevSdkIgnoreRunner
 import java.net.NetworkInterface
@@ -39,10 +41,10 @@
 private const val TEST_SERVICE_ID_2 = 43
 private const val TEST_PORT = 12345
 private val TEST_HOSTNAME = arrayOf("Android_000102030405060708090A0B0C0D0E0F", "local")
-private val TEST_ADDRESSES = arrayOf(
-        parseNumericAddress("192.0.2.111"),
-        parseNumericAddress("2001:db8::111"),
-        parseNumericAddress("2001:db8::222"))
+private val TEST_ADDRESSES = listOf(
+        LinkAddress(parseNumericAddress("192.0.2.111"), 24),
+        LinkAddress(parseNumericAddress("2001:db8::111"), 64),
+        LinkAddress(parseNumericAddress("2001:db8::222"), 64))
 
 private val TEST_SERVICE_1 = NsdServiceInfo().apply {
     serviceType = "_testservice._tcp"
@@ -50,6 +52,12 @@
     port = TEST_PORT
 }
 
+private val TEST_SERVICE_2 = NsdServiceInfo().apply {
+    serviceType = "_testservice._tcp"
+    serviceName = "MyOtherTestService"
+    port = TEST_PORT
+}
+
 @RunWith(DevSdkIgnoreRunner::class)
 @DevSdkIgnoreRule.IgnoreUpTo(Build.VERSION_CODES.S_V2)
 class MdnsRecordRepositoryTest {
@@ -57,7 +65,7 @@
     private val deps = object : Dependencies() {
         override fun getHostname() = TEST_HOSTNAME
         override fun getInterfaceInetAddresses(iface: NetworkInterface) =
-                Collections.enumeration(TEST_ADDRESSES.toList())
+                Collections.enumeration(TEST_ADDRESSES.map { it.address })
     }
 
     @Before
@@ -113,6 +121,15 @@
     }
 
     @Test
+    fun testInvalidReuseOfServiceId() {
+        val repository = MdnsRecordRepository(thread.looper, deps)
+        repository.addService(TEST_SERVICE_ID_1, TEST_SERVICE_1)
+        assertFailsWith(IllegalArgumentException::class) {
+            repository.addService(TEST_SERVICE_ID_1, TEST_SERVICE_2)
+        }
+    }
+
+    @Test
     fun testExitingServiceReAdded() {
         val repository = MdnsRecordRepository(thread.looper, deps)
         repository.addService(TEST_SERVICE_ID_1, TEST_SERVICE_1)
@@ -124,4 +141,131 @@
         repository.removeService(TEST_SERVICE_ID_2)
         assertEquals(0, repository.servicesCount)
     }
+
+    @Test
+    fun testOnProbingSucceeded() {
+        val repository = MdnsRecordRepository(thread.looper, deps)
+        repository.updateAddresses(TEST_ADDRESSES)
+
+        repository.addService(TEST_SERVICE_ID_1, TEST_SERVICE_1)
+        val probingInfo = repository.setServiceProbing(TEST_SERVICE_ID_1)
+        val announcementInfo = repository.onProbingSucceeded(probingInfo)
+        val packet = announcementInfo.getPacket(0)
+
+        assertEquals(0x8400 /* response, authoritative */, packet.flags)
+        assertEquals(0, packet.questions.size)
+        assertEquals(0, packet.authorityRecords.size)
+
+        val serviceType = arrayOf("_testservice", "_tcp", "local")
+        val serviceName = arrayOf("MyTestService", "_testservice", "_tcp", "local")
+        val v4AddrRev = getReverseDnsAddress(TEST_ADDRESSES[0].address)
+        val v6Addr1Rev = getReverseDnsAddress(TEST_ADDRESSES[1].address)
+        val v6Addr2Rev = getReverseDnsAddress(TEST_ADDRESSES[2].address)
+
+        assertContentEquals(listOf(
+                // Reverse address and address records for the hostname
+                MdnsPointerRecord(v4AddrRev,
+                        0L /* receiptTimeMillis */,
+                        true /* cacheFlush */,
+                        120000L /* ttlMillis */,
+                        TEST_HOSTNAME),
+                MdnsInetAddressRecord(TEST_HOSTNAME,
+                        0L /* receiptTimeMillis */,
+                        true /* cacheFlush */,
+                        120000L /* ttlMillis */,
+                        TEST_ADDRESSES[0].address),
+                MdnsPointerRecord(v6Addr1Rev,
+                        0L /* receiptTimeMillis */,
+                        true /* cacheFlush */,
+                        120000L /* ttlMillis */,
+                        TEST_HOSTNAME),
+                MdnsInetAddressRecord(TEST_HOSTNAME,
+                        0L /* receiptTimeMillis */,
+                        true /* cacheFlush */,
+                        120000L /* ttlMillis */,
+                        TEST_ADDRESSES[1].address),
+                MdnsPointerRecord(v6Addr2Rev,
+                        0L /* receiptTimeMillis */,
+                        true /* cacheFlush */,
+                        120000L /* ttlMillis */,
+                        TEST_HOSTNAME),
+                MdnsInetAddressRecord(TEST_HOSTNAME,
+                        0L /* receiptTimeMillis */,
+                        true /* cacheFlush */,
+                        120000L /* ttlMillis */,
+                        TEST_ADDRESSES[2].address),
+                // Service registration records (RFC6763)
+                MdnsPointerRecord(
+                        serviceType,
+                        0L /* receiptTimeMillis */,
+                        // Not a unique name owned by the announcer, so cacheFlush=false
+                        false /* cacheFlush */,
+                        4500000L /* ttlMillis */,
+                        serviceName),
+                MdnsServiceRecord(
+                        serviceName,
+                        0L /* receiptTimeMillis */,
+                        true /* cacheFlush */,
+                        120000L /* ttlMillis */,
+                        0 /* servicePriority */,
+                        0 /* serviceWeight */,
+                        TEST_PORT /* servicePort */,
+                        TEST_HOSTNAME),
+                MdnsTextRecord(
+                        serviceName,
+                        0L /* receiptTimeMillis */,
+                        true /* cacheFlush */,
+                        4500000L /* ttlMillis */,
+                        emptyList() /* entries */),
+                // Service type enumeration record (RFC6763 9.)
+                MdnsPointerRecord(
+                        arrayOf("_services", "_dns-sd", "_udp", "local"),
+                        0L /* receiptTimeMillis */,
+                        false /* cacheFlush */,
+                        4500000L /* ttlMillis */,
+                        serviceType)
+        ), packet.answers)
+
+        assertContentEquals(listOf(
+                MdnsNsecRecord(v4AddrRev,
+                        0L /* receiptTimeMillis */,
+                        true /* cacheFlush */,
+                        120000L /* ttlMillis */,
+                        v4AddrRev,
+                        intArrayOf(MdnsRecord.TYPE_PTR)),
+                MdnsNsecRecord(TEST_HOSTNAME,
+                        0L /* receiptTimeMillis */,
+                        true /* cacheFlush */,
+                        120000L /* ttlMillis */,
+                        TEST_HOSTNAME,
+                        intArrayOf(MdnsRecord.TYPE_A, MdnsRecord.TYPE_AAAA)),
+                MdnsNsecRecord(v6Addr1Rev,
+                        0L /* receiptTimeMillis */,
+                        true /* cacheFlush */,
+                        120000L /* ttlMillis */,
+                        v6Addr1Rev,
+                        intArrayOf(MdnsRecord.TYPE_PTR)),
+                MdnsNsecRecord(v6Addr2Rev,
+                        0L /* receiptTimeMillis */,
+                        true /* cacheFlush */,
+                        120000L /* ttlMillis */,
+                        v6Addr2Rev,
+                        intArrayOf(MdnsRecord.TYPE_PTR)),
+                MdnsNsecRecord(serviceName,
+                        0L /* receiptTimeMillis */,
+                        true /* cacheFlush */,
+                        4500000L /* ttlMillis */,
+                        serviceName,
+                        intArrayOf(MdnsRecord.TYPE_TXT, MdnsRecord.TYPE_SRV))
+        ), packet.additionalRecords)
+    }
+
+    @Test
+    fun testGetReverseDnsAddress() {
+        val expectedV6 = "1.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.8.B.D.1.0.0.2.ip6.arpa"
+                .split(".").toTypedArray()
+        assertContentEquals(expectedV6, getReverseDnsAddress(parseNumericAddress("2001:db8::1")))
+        val expectedV4 = "123.2.0.192.in-addr.arpa".split(".").toTypedArray()
+        assertContentEquals(expectedV4, getReverseDnsAddress(parseNumericAddress("192.0.2.123")))
+    }
 }