ISIS Hierarchical SNPs

Status of This Memo

This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.¶

Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet-Drafts is at https://datatracker.ietf.org/drafts/current/.¶

Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."¶

This Internet-Draft will expire on 10 August 2026.¶

Copyright Notice

Copyright (c) 2026 IETF Trust and the persons identified as the document authors. All rights reserved.¶

This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Revised BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Revised BSD License.¶

Table of Contents

2. Dynamic Partitioning

In practical terms, the most interesting problem is figuring out how to divide the database into groups of leaf nodes (each representing a set of fragments) that both compress the data effectively compared to standard CSNPs and remain as stable as possible. If the fragment boundaries within each hash keep changing, neighboring systems will need to recalculate their hashes instead of reusing cached ones from their own Merkle tree, which adds unnecessary computation. The subdivision should also create enough "bins" to handle any distribution of fragment IDs across the network. This helps avoid pathological cases where all fragments might end up in a single hash, such as when e.g. a hashing function degrades. Ideally, when a hash mismatch occurs, it should take only one or two packets, with hashes for smaller fragment groups or regular CSNPs, to fix the difference. Reducing I/O and/or computation directly improves how quickly the systems synchronize.¶

To begin, in IS-IS networks we can fit just under 100 PSNP entries into the typical 1500-byte MTU frame. This is the consequence of each CSNP entry including the Node ID, Fragment number, Sequence number, Checksum, and Lifetime fields -- totaling 7 + 1 + 4 + 2 + 2 = 16 bytes per entry.¶

Fletcher hashes, as shown in Figure 2, take up 6 + 6 + 6 = 18 bytes each, which means that about 70 such hashes fit into a single packet. A more detailed explanation of why a 48-bit Fletcher checksum and the resulting hash sizes were chosen is provided in Section 9.2.¶

These limits form the basis for the recommended partitioning and packing strategies discussed later.¶

At the lowest compression level, it is optimal to generate a single CSNP packet on a mismatch in a hash. To achieve this, the first-level hashes should initially group about 80 LSP fragments together, with exceptions handled later. There is no need to maximize this initial packing.¶

As the LSDB grows, it is better to leave some flexibility ("slack") in how fragments are grouped. This increases the likelihood that both sides of an adjacency will maintain the same leaf-level packing, even during flooding transitions, and prevents the ranges from shifting constantly.¶

The packing process always places all fragments belonging to the same system and its pseudonodes within a single node Merkle hash. This hash may occasionally exceed the recommended size of 80 fragments. When it comes to node range hashes a hash is considered "full" when adding the next system's fragments would go beyond this limit. Unless, of course, the leaf is still empty.¶

At that point, any range hash can be folded into a higher-level, less specific range hash. However, whenever a mismatch occurs at any level, the process must disaggregate the hash and send the corresponding smaller, more specific range or node hash instead.¶

4. Fast, Incremental, Self-Inverse Hashing Function for Fragment Ranges

Since large-scale deployments must compute significant numbers of hashes over sets of frequently changing fragments, it is highly desirable to use a specialized hash function that supports fast incremental updates when fragments are added, removed, or when their checksums change.¶

Once hashes are built over sets of fragments, it is desirable to support very fast splitting and merging of such sets, especially when two hashes differ in which fragments they contain.¶

Deeper considerations on such hashes can be found in [HASHES] but our design space is simplified due to irrelevance of security involved.¶

The hash for a set of fragments is computed using a very fast XOR over their Fletcher hashes. This makes it straightforward to update the hash when a leaf is added, removed, or its checksum changes. As a result, less specific ranges can quickly derive their hash by XOR'ing the hashes of all included, more specific ranges, when those are available.¶

6. HSNP PDU Format

The HSNP PDU format closely follows the CSNP format. Instead of CSNP entries, it carries the corresponding Merkle hashes - which cover exactly the same fragments that would appear in CSNP packets. The Start and End System IDs exclude pseudonode bytes, as those are implicitly included within the ranges.¶

        ...

+--------------------------------------------+
|              PDU Length                    |
+--------------------------------------------+
|              Source ID                     |
+--------------------------------------------+
|              Start System ID               |
+--------------------------------------------+
|              End System ID                 |
+--------------------------------------------+
|           Variable Length Fields           |
+--------------------------------------------+

The Start and End System IDs use the standard ID length and indicate the range of fragments covered by the HSNP, just like CSNPs do. The key difference is that all pseudonodes of the systems within this range are implicitly included. Both the Start and End System IDs are inclusive, meaning fragments from both endpoints are part of the range.¶

The variable length fields are a sorted sequence of Node Range Hash Entries in the following format.¶

+--------------------------------------------+
|              Range Start System ID         |
+--------------------------------------------+
|              Range End System ID           |
+--------------------------------------------+
|              Merkle Hash                   |
+--------------------------------------------+

Range of LSPs that are included in the hash. Range Start and Range End System ID are inclusive, i.e. the fragments of both the start and the end system ID are contained within the range.¶

Merkle hash consists of 6 bytes of the 48-bit computed hash of all fragments covered by the range.¶

This makes an entry in typical deployment scenarios 6 + 6 + 6 = 18 bytes long and hence about 70 hashes fit into a typical MTU .¶

Ranges MUST be sorted on Start System ID.¶

8. IS-IS Scale Envelope Considerations

HSNPs provide negligible benefit in small networks with only tens of nodes and hundreds of fragments. Perfect flooding would theoretically suffice at any scale (though history shows this is too optimistic), and even CSNPs represent under such assumptions protocol overhead only - yet they have significantly contributed to IS-IS stability in real deployments.¶

As networks grow larger, the costs of link flaps, node restarts, and periodic CSNP exchanges increase substantially. HSNPs can significantly extend IS-IS scalability in these scenarios.¶

To push IS-IS to its practical limits, we must account for flooding rates driven by fragment refreshes and LSDB synchronization. Path computation impacts can be deferred - bare pathological scenarios - by using dampening and parallelization, and thus we focus on realistic scenarios in the order of 50,000 nodes and 1 million fragments.¶

At maximum configured lifetime, this generates ~15 packets/second per interface from refreshes (1M/65K fragments/second), plus ~10,000 CSNP packets for full LSDB sync.¶

Achieving a modest 120-second sync requires ~80 CSNPs/second, and across 16,000 interfaces, that represents a peak of 1.5 million packets/second - far beyond current fast-flooding capabilities. We disregard here further techniques like [ID.draft-ietf-lsr-distoptflood-11], especially since they do not improve CSNP scale.¶

With maximum HSNP compression, however, sync overhead drops to roughly one additional packet beyond refresh flooding, leaving ~250,000 packets/second (15 * 16K) to be handled by fast flooding and flood reduction techniques - a challenging but feasible target.¶

The considerations above make it clear that combining fast flooding, flood reduction, and HSNP features will be essential in extending IS-IS scalability as deployments continue to grow larger.¶

9. Further Considerations

11. IANA Section

TBD¶

Appendix A. Reference Implementation of Fragment Hashing

<CODE BEGINS>
pub fn fletcher_hash(fragmentid: &SharedFragmentID, fragmentcontent: &FragmentContent) -> HSNPHash {

    let nid = fragmentid.node.node_id().0;
    let pnodebe = fragmentid.pnode.0.to_be_bytes();
    let seqnrbe = fragmentcontent.seqnr.0.to_be_bytes();
    let fragmentnrbe = fragmentid.fragmentnr.0.to_be_bytes();
    let csumbe = fragmentcontent.isis_checksum.0.to_be_bytes();
    let lenbe = fragmentcontent.isis_pdu_length.0.to_be_bytes();

    let rotate_in_primary = nid.iter().chain(
        csumbe.iter().chain(
            seqnrbe.iter().chain(
                fragmentnrbe
                    .iter()
                    .chain(lenbe.iter().chain(pnodebe.iter())),
            ),
        ),
    );

    // takes an iterator over u8 slice and return BE u16 stream padded with a final zero if
    // not. necessary for fletcher to work
    pub struct U8ToU24BePadded<'a, I>
    where
        I: Iterator<Item = &'a u8>,
    {
        iter: I,
    }

    impl<'a, I> U8ToU24BePadded<'a, I>
    where
        I: Iterator<Item = &'a u8>,
    {
        pub fn new(iter: I) -> Self {
            U8ToU24BePadded { iter }
        }
    }

    impl<'a, I> Iterator for U8ToU24BePadded<'a, I>
    where
        I: Iterator<Item = &'a u8>,
    {
        type Item = ux::u24;

        fn next(&mut self) -> Option<Self::Item> {
            let b0 = self.iter.next()?;
            let b1 = self.iter.next().unwrap_or(&0);
            let b2 = self.iter.next().unwrap_or(&0);
            let v = u32::from(*b0) | (u32::from(*b1) << 8) | (u32::from(*b2) << 16);
            Some(ux::u24::new(v))
        }
    }


    match LIBRARY_HSNP_SIZE {
        HSNPSize::_48Bits => {
            let mut u24buffer: [ux::u24; 6] = [ux::u24::MIN; 6];
            U8ToU24BePadded::new(rotate_in_primary).collect_slice_checked(&mut u24buffer[..]);
            fletcher::calc_fletcher48(&u24buffer).into()
        }

<CODE ENDS>

Authors' Addresses