diff --git a/service/mdns/com/android/server/connectivity/mdns/MdnsNsecRecord.java b/service/mdns/com/android/server/connectivity/mdns/MdnsNsecRecord.java
new file mode 100644
index 0000000..57c3c03
--- /dev/null
+++ b/service/mdns/com/android/server/connectivity/mdns/MdnsNsecRecord.java
@@ -0,0 +1,142 @@
+/*
+ * Copyright (C) 2022 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.server.connectivity.mdns;
+
+import android.net.DnsResolver;
+
+import com.android.net.module.util.CollectionUtils;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.Arrays;
+
+/**
+ * A mDNS "NSEC" record, used in particular for negative responses (RFC6762 6.1).
+ */
+public class MdnsNsecRecord extends MdnsRecord {
+    private String[] mNextDomain;
+    private int[] mTypes;
+
+    public MdnsNsecRecord(String[] name, MdnsPacketReader reader) throws IOException {
+        this(name, reader, false);
+    }
+
+    public MdnsNsecRecord(String[] name, MdnsPacketReader reader, boolean isQuestion)
+            throws IOException {
+        super(name, TYPE_NSEC, reader, isQuestion);
+    }
+
+    public MdnsNsecRecord(String[] name, long receiptTimeMillis, boolean cacheFlush, long ttlMillis,
+            String[] nextDomain, int[] types) {
+        super(name, TYPE_NSEC, DnsResolver.CLASS_IN, receiptTimeMillis, cacheFlush, ttlMillis);
+        mNextDomain = nextDomain;
+        final int[] sortedTypes = Arrays.copyOf(types, types.length);
+        Arrays.sort(sortedTypes);
+        mTypes = sortedTypes;
+    }
+
+    public String[] getNextDomain() {
+        return mNextDomain;
+    }
+
+    public int[] getTypes() {
+        return mTypes;
+    }
+
+    @Override
+    protected void readData(MdnsPacketReader reader) throws IOException {
+        mNextDomain = reader.readLabels();
+        mTypes = readTypes(reader);
+    }
+
+    private int[] readTypes(MdnsPacketReader reader) throws IOException {
+        // See RFC3845 #2.1.2
+        final ArrayList<Integer> types = new ArrayList<>();
+        int prevBlockNumber = -1;
+        while (reader.getRemaining() > 0) {
+            final int blockNumber = reader.readUInt8();
+            if (blockNumber <= prevBlockNumber) {
+                throw new IOException(
+                        "Unordered block number: " + blockNumber + " after " + prevBlockNumber);
+            }
+            prevBlockNumber = blockNumber;
+            final int bitmapLength = reader.readUInt8();
+            if (bitmapLength > 32 || bitmapLength <= 0) {
+                throw new IOException("Invalid bitmap length: " + bitmapLength);
+            }
+            final byte[] bitmap = new byte[bitmapLength];
+            reader.readBytes(bitmap);
+
+            for (int bitmapIndex = 0; bitmapIndex < bitmap.length; bitmapIndex++) {
+                final byte bitmapByte = bitmap[bitmapIndex];
+                for (int bit = 0; bit < 8; bit++) {
+                    if ((bitmapByte & (1 << (7 - bit))) != 0) {
+                        types.add(blockNumber * 256 + bitmapIndex * 8 + bit);
+                    }
+                }
+            }
+        }
+
+        return CollectionUtils.toIntArray(types);
+    }
+
+    @Override
+    protected void writeData(MdnsPacketWriter writer) throws IOException {
+        // No compression as per RFC3845 2.1.1
+        writer.writeLabelsNoCompression(mNextDomain);
+
+        // type bitmaps: RFC3845 2.1.2
+        int typesBlockStart = 0;
+        int pendingBlockNumber = -1;
+        int blockLength = 0;
+        // Loop on types (which are sorted in increasing order) to find each block and determine
+        // their length; use writeTypeBlock once the length of each block has been found.
+        for (int i = 0; i < mTypes.length; i++) {
+            final int blockNumber = mTypes[i] / 256;
+            final int typeLowOrder = mTypes[i] % 256;
+            // If the low-order 8 bits are e.g. 0x10, bit number 16 (=0x10) will be set in the
+            // bitmap; this is the first bit of byte 2 (byte 0 is 0-7, 1 is 8-15, etc.)
+            final int byteIndex = typeLowOrder / 8;
+
+            if (pendingBlockNumber >= 0 && blockNumber != pendingBlockNumber) {
+                // Just reached a new block; write the previous one
+                writeTypeBlock(writer, typesBlockStart, i - 1, blockLength);
+                typesBlockStart = i;
+                blockLength = 0;
+            }
+            blockLength = Math.max(blockLength, byteIndex + 1);
+            pendingBlockNumber = blockNumber;
+        }
+
+        if (pendingBlockNumber >= 0) {
+            writeTypeBlock(writer, typesBlockStart, mTypes.length - 1, blockLength);
+        }
+    }
+
+    private void writeTypeBlock(MdnsPacketWriter writer,
+            int typesStart, int typesEnd, int bytesInBlock) throws IOException {
+        final int blockNumber = mTypes[typesStart] / 256;
+        final byte[] bytes = new byte[bytesInBlock];
+        for (int i = typesStart; i <= typesEnd; i++) {
+            final int typeLowOrder = mTypes[i] % 256;
+            bytes[typeLowOrder / 8] |= 1 << (7 - (typeLowOrder % 8));
+        }
+        writer.writeUInt8(blockNumber);
+        writer.writeUInt8(bytesInBlock);
+        writer.writeBytes(bytes);
+    }
+}
diff --git a/service/mdns/com/android/server/connectivity/mdns/MdnsPacketWriter.java b/service/mdns/com/android/server/connectivity/mdns/MdnsPacketWriter.java
index b78aa5d..611787f 100644
--- a/service/mdns/com/android/server/connectivity/mdns/MdnsPacketWriter.java
+++ b/service/mdns/com/android/server/connectivity/mdns/MdnsPacketWriter.java
@@ -190,12 +190,7 @@
             }
             writePointer(suffixPointer);
         } else {
-            int[] offsets = new int[labels.length];
-            for (int i = 0; i < labels.length; ++i) {
-                offsets[i] = getWritePosition();
-                writeString(labels[i]);
-            }
-            writeUInt8(0); // NUL terminator
+            int[] offsets = writeLabelsNoCompression(labels);
 
             // Add entries to the label dictionary for each suffix of the label list, including
             // the whole list itself.
@@ -207,6 +202,21 @@
         }
     }
 
+    /**
+     * Write a series a labels, without using name compression.
+     *
+     * @return The offsets where each label was written to.
+     */
+    public int[] writeLabelsNoCompression(String[] labels) throws IOException {
+        int[] offsets = new int[labels.length];
+        for (int i = 0; i < labels.length; ++i) {
+            offsets[i] = getWritePosition();
+            writeString(labels[i]);
+        }
+        writeUInt8(0); // NUL terminator
+        return offsets;
+    }
+
     /** Returns the number of bytes that can still be written. */
     public int getRemaining() {
         return data.length - pos;
diff --git a/service/mdns/com/android/server/connectivity/mdns/MdnsRecord.java b/service/mdns/com/android/server/connectivity/mdns/MdnsRecord.java
index c0481a4..10b8825 100644
--- a/service/mdns/com/android/server/connectivity/mdns/MdnsRecord.java
+++ b/service/mdns/com/android/server/connectivity/mdns/MdnsRecord.java
@@ -39,6 +39,7 @@
     public static final int TYPE_PTR = 0x000C;
     public static final int TYPE_SRV = 0x0021;
     public static final int TYPE_TXT = 0x0010;
+    public static final int TYPE_NSEC = 0x002f;
     public static final int TYPE_ANY = 0x00ff;
 
     private static final int FLAG_CACHE_FLUSH = 0x8000;
diff --git a/tests/unit/java/com/android/server/connectivity/mdns/MdnsRecordTests.java b/tests/unit/java/com/android/server/connectivity/mdns/MdnsRecordTests.java
index 9746a35..7d800d8 100644
--- a/tests/unit/java/com/android/server/connectivity/mdns/MdnsRecordTests.java
+++ b/tests/unit/java/com/android/server/connectivity/mdns/MdnsRecordTests.java
@@ -18,11 +18,13 @@
 
 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.assertNotNull;
 import static org.junit.Assert.assertNull;
 import static org.junit.Assert.assertThrows;
+import static org.junit.Assert.assertTrue;
 
 import android.util.Log;
 
@@ -270,6 +272,55 @@
     }
 
     @Test
+    public void testNsecRecord() throws IOException {
+        final byte[] dataIn = HexDump.hexStringToByteArray(
+                // record.android.com
+                "067265636F726407616E64726F696403636F6D00"
+                        // Type 0x002f (NSEC), cache flush set on class IN (0x8001)
+                        + "002F8001"
+                        // TTL 0x0000003c (60 secs)
+                        + "0000003C"
+                        // Data length
+                        + "003C"
+                        // nextdomain.android.com
+                        + "0A6E657874646F6D61696E07616E64726F696403636F6D00"
+                        // Type bitmaps: window block 0x00, bitmap length 0x05,
+                        // bits 16 (TXT) and 33 (SRV) set: 0x0000800040
+                        + "00050000800040"
+                        // For 1234, 4*256 + 210 = 1234, so window block 0x04, bitmap length 27/0x1B
+                        // (26*8 + 2 = 210, need 27 bytes to set bit 210),
+                        // bit 2 set on byte 27 (0x20).
+                        + "041B000000000000000000000000000000000000000000000000000020");
+        assertNotNull(dataIn);
+        String dataInText = HexDump.dumpHexString(dataIn, 0, dataIn.length);
+
+        // Decode
+        DatagramPacket packet = new DatagramPacket(dataIn, dataIn.length);
+        MdnsPacketReader reader = new MdnsPacketReader(packet);
+
+        String[] name = reader.readLabels();
+        assertNotNull(name);
+        assertEquals(3, name.length);
+        String fqdn = MdnsRecord.labelsToString(name);
+        assertEquals("record.android.com", fqdn);
+
+        int type = reader.readUInt16();
+        assertEquals(MdnsRecord.TYPE_NSEC, type);
+
+        MdnsNsecRecord record = new MdnsNsecRecord(name, reader);
+        assertTrue(record.getCacheFlush());
+        assertEquals(60_000L, record.getTtl());
+        assertEquals("nextdomain.android.com", MdnsRecord.labelsToString(record.getNextDomain()));
+        assertArrayEquals(new int[] { MdnsRecord.TYPE_TXT,
+                MdnsRecord.TYPE_SRV,
+                // Non-existing record type, > 256
+                1234 }, record.getTypes());
+
+        String dataOutText = toHex(record);
+        assertEquals(dataInText, dataOutText);
+    }
+
+    @Test
     public void testTextRecord() throws IOException {
         final byte[] dataIn = HexDump.hexStringToByteArray(
                 "0474657374000010"