Internet-Draft IS-IS Aggregated SNP Hash Packets October 2026
Przygienda, et al. Expires 3 May 2027 [Page]
Workgroup:
Network Working Group
Internet-Draft:
draft-prz-lsr-ash-packets-08
Published:
Intended Status:
Experimental
Expires:
Authors:
T. Przygienda
HPE Juniper Networking
T. Li
HPE Juniper Networking
J. Halpern
HPE Juniper Networking

IS-IS Aggregated SNP Hash Packets

Abstract

The document presents an optional new type of database synchronization packet called an Aggregated SNP Hash (ASH). When feasible, it compresses traditional SNP exchanges into a dynamic Merkle tree-like structure, which speeds up synchronization of large databases and adjacency numbers while reducing the load from regular CSNP exchanges during normal operation. Just like CSNPs and PSNPs, ASH packets come in two flavors, called Complete ASH (CASH) and Partial ASH (PASH).

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 3 May 2027.

▲

Table of Contents

1. Introduction

The document introduces an optional new type of database synchronization packet called the Aggregated SNP Hash (ASH). It compresses and enhances traditional CSNP and SNP exchanges with a structure somewhat similar to a dynamic Merkle tree [MERKLE], enabling faster synchronization of large databases and adjacency information while reducing the overhead of regular CSNP exchanges during steady state operation. By combining parallel flooding, SNP and ASH exchanges, database resynchronization can be accelerated because fewer packets (and not the entire CSNP set) are used to fix inconsistencies. Using ASHs also reduces unnecessary flooding and communication overhead, while still detecting mismatched fragments more efficiently than full CSNP exchanges.

To maintain the Merkle analogy, we initially treat each SNP entry for an LSP as equivalent to an "as good as perfect" - though rather long - Merkle hash. In other words, the LSP ID, sequence number, and checksum act as a "collision-free fragment hash". We include the fragment's PDU length in this perfect hash to add more entropy in the next step. Lifetime is not used since it is not compared except in purge cases. The SNP entries then serve as the conceptual "bottom" of the Merkle tree.

In the following step we compute a [SIPHASH] over the SNP entry data to create a shorter Merkle hash for each fragment. Somewhat surprisingly, these per-fragment hashes are never transmitted in packets, since doing so would effectively duplicate SNP functionality. However, the hash that aggregates all fragment hashes of a node becomes a "node Merkle hash". Groups of node hashes can then be summarized into a "node range Merkle hash" by combining the individual node hashes together. For the node and node range hashes, we switch from [SIPHASH] to a different hashing method, as explained in Section 4.2.

The resulting hierarchy of hashes enables large LSDB synchronizations using far fewer packets than CSNPs alone. Although the hashes summarize ranges recursively, the actual exchange resembles a [SKIP]-like process rather than maintaining a fixed tree structure, since the packets and ranges exchanged vary depending on where mismatches are found.

This document limits itself to LSDB sizes on the order of 1E6 fragments and addresses considerations necessary to prevent overly garrulous exchanges of hashes covering progressively smaller sets of fragments. More details on the targeted IS-IS scale envelope can be found in Section 9.2, and further considerations are summarized in Section 9.

ASH also changes the architecture of graceful restart to address the scaling limitations of [RFC8706]. Instead of concentrating overlapping database transfers and their reconciliation at the restarting router, ASH distributes recovery work among helpers under the restarting router's orchestration. This reduces redundant transfers and central processing as database size and the number of helpers grow, while retaining the existing adjacency-preservation and restart-signaling semantics. Additionally, it introduces an epoch based protection against overlapping restarts.

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here.

1.1. Glossary

Since all confusion starts in language, we begin with a precise glossary to express the solution space in unambiguous terms.

CASH terminology is defined first; corresponding CSNP terms refer to those definitions. Coverage, agreement, terminal repair, and restart completion describe separate properties.

1.1.1. Database Objects and Scope

Invalid System ID:
The all-ones System ID (FFFF.FFFF.FFFF with the standard six-octet length) is not a valid IS-IS node identifier. It serves as an end marker: an all-ones End System ID identifies C-CASH; an all-ones End LSP ID identifies C-CSNP. Neither identifies a node to reconcile. These endpoint values are distinct from the reserved 64-bit all-ones hash value.
LSDB (Link State Database):
A database of LSP fragments maintained for one IS-IS level. ASH summarizes the non-purged fragments visible on the circuit, using the same scope as ordinary CSNPs.
LSP (Link State PDU):
A link-state advertisement identified by an LSP ID. Its sequence number and checksum distinguish instances with the same LSP ID.
Fragment:
One individually identified LSP carrying part of an originator's link-state information.
System ID:
A router identifier forming the system portion of an LSP ID.
Node:
The ASH aggregation unit comprising all fragments associated with one System ID, including its pseudonodes.
Pseudonode:
An IS-IS representation of a broadcast network whose LSPs are originated by the DIS. Its identifier distinguishes it from the router's non-pseudonode information under the same System ID.
LSP ID:
A fragment identifier consisting of a System ID, pseudonode identifier, and fragment number. Unlike a System ID alone, it identifies one fragment rather than the whole ASH node.
Purge:
An LSP instance with zero remaining lifetime. Purges use ordinary flooding and are excluded from ASH hash computations.
Active level:
An IS-IS protocol level, Level 1 or Level 2, participating on the adjacency. A common active level is one at which both neighbors participate; database summaries and reconciliation remain separate per level.

1.1.2. Packets, Entries, and Capabilities

PDU (Protocol Data Unit):
A protocol packet.
TLV (Type-Length-Value):
A typed, length-delimited element carried within a PDU.
ASH (Aggregated SNP Hash):
A database-reconciliation mechanism describing node ranges with hashes. An ASH PDU is either a CASH or a PASH.
CASH (Complete ASH):
An ASH PDU with Start and End System IDs delimiting its coverage. Within those bounds, gaps between advertised ranges indicate absence. Describing the whole database may require more than one CASH PDU. See Section 6. Analogous in behavior to CSNP.
PASH (Partial ASH):
An ASH PDU carrying independent node-range entries without an enclosing packet coverage range. Unlike CASH, gaps between its entries have no absence semantics. It carries refinement hashes or terminal repair directives. See Section 7. Analogous in behavior to PSNP.
SNP (Sequence Number PDU):
An IS-IS database-reconciliation PDU describing individual LSPs through LSP entries. Its two forms are CSNP and PSNP.
CSNP (Complete Sequence Number PDU):
The SNP equivalent of CASH, describing individual LSPs rather than node-range hashes. Its coverage is delimited by Start and End LSP IDs. Describing the whole database may require more than one CSNP PDU. It is part of the existing and deployed IS-IS standard.
PSNP (Partial Sequence Number PDU):
The SNP equivalent of PASH, carrying individual LSP entries used to request or acknowledge fragments. Gaps between entries have no absence semantics. It is part of the existing and deployed IS-IS standard.
Node Range Hash Entry:
A wire record containing inclusive Start and End System IDs and a 64-bit hash field.
Node Range Hash TLV:
A TLV containing one or more Node Range Hash Entries. A CASH or PASH can carry multiple such TLVs.
IIH (IS-IS Hello):
An adjacency-management PDU carrying, among other information, ASH capability and restart signaling. IIH is part of the existing and deployed IS-IS standard.
ASH_RX:
A Hello Capability flag advertising willingness and ability to receive ASH. Carried in [ID.draft-ginsberg-lsr-hello-capability-00].
ASH_TX:
A Hello Capability flag advertising that the router may originate ASH. It is independent of ASH_RX. Carried in [ID.draft-ginsberg-lsr-hello-capability-00].

1.1.3. Ranges, Hashes, and Repair

Node range:
An inclusive interval of System IDs, covering all pseudonodes and fragments of each included system for ASH comparison purposes.
Singleton range:
A node range with equal endpoints, covering exactly one System ID and all its fragments for ASH comparison purposes.
More specific range:
A proper subrange of another node range.
Less specific range:
A node range containing another range as a proper subrange.
Fragment Population:
An advisory, one-octet encoded estimate of the number of LSP fragments held by the sender in the advertised node range. Zero denotes an empty range; nonzero values give a logarithmic estimate no greater than the actual population. It describes local holdings independently of the advertised hash, including when that hash is zero. See Section 6.
Zero population:
An advertised node range whose Fragment Population field is zero, indicating that the sender holds no LSP fragments in that range.
Fragment hash:
A 64-bit fingerprint computed from one fragment's SNP description using siphash-1-3 [SIPHASH].
Node hash:
A fingerprint aggregating the fragment hashes of one node (singleton range) using XOR (exclusive OR).
Node range hash:
A fingerprint aggregating the fragment hashes within a node range using XOR. Reserved-value handling is specified in Section 4.2.
Merkle hash:
The name used in this document for a node or node range hash in the aggregation hierarchy.
Zero hash (zero-hash directive):
The hash-field value 0 in a valid Node Range Hash Entry, directing terminal repair. It is a control value, not a computed fingerprint: it is never compared and establishes neither hash agreement nor hash mismatch, even when the local range is empty. On point-to-point circuits and from the DIS it requests direct flooding; from a non-DIS to the DIS it requests range-CSNP repair. Range validity is checked before interpreting the directive. See Section 5.4.
Reserved all-ones hash:
The 64-bit all-ones hash-field value, reserved and excluded from transmission and hash comparison.
Hash agreement:
Equality between a valid advertised fingerprint and the locally computed fingerprint for the same range, after reserved-value handling. The zero-hash directive is excluded from comparison. During graceful restart, a matching hash for the restarting router's isolated System ID retains its ordinary meaning; a difference on that singleton is ignored as specified in Section 5.6.4.
Hash mismatch:
Inequality between a valid advertised fingerprint and the locally computed fingerprint for the same range, after reserved-value handling. The zero-hash directive is excluded from comparison. During graceful restart, a difference confined to the restarting router's isolated System ID is excluded from mismatch processing, as specified in Section 5.6.4.
Hash collision:
Hash agreement despite different hashed contents. Hash agreement therefore provides probabilistic evidence of database agreement.
Refinement:
A reconciliation step that subdivides a mismatching range into two or more more-specific ranges that together cover the entire original range. Each subrange is described by a hash or handled by terminal repair.
Terminal range:
A node range selected for terminal repair following a hash mismatch or a zero-hash directive. It can cover any number of valid System IDs.
Terminal repair threshold:
An implementation's criterion for selecting a mismatching range as terminal.
Terminal repair:
A reconciliation step that resolves a terminal range using ordinary IS-IS LSP and SNP procedures rather than further hash subdivision. The circuit role and graceful-restart helper exception determine which repair actions apply. See Section 5.4.1 and Section 5.5.
Range CSNP (terminal-repair range CSNP):
A CSNP, or series of CSNPs, used to repair a selected terminal range. Its distinguishing property is its repair purpose, not necessarily narrow coverage. It does not signal a complete CSNP set for graceful restart: its End LSP ID excludes the all-ones complete-set marker, even when the selected range includes the last valid System ID. See Section 5.4.1, Paragraph 7.
Flooding:
Transmission of LSPs to neighbors using IS-IS database-distribution procedures.
Acknowledgement:
Confirmation of receipt of an LSP instance.
Retransmission:
Repeated transmission of an unacknowledged LSP instance.

1.1.4. Coverage, Trains, and Agreement

CASH train:
A set of CASHes describing the database at one IS-IS level.
C-CASH:
A CASH with an all-ones End System ID, terminating a CASH train. This name introduces no new PDU type or flag bit.
Complete CASH train:
A CASH train whose PDU header ranges together cover the entire System ID space without gaps, from the all-zero Start System ID through the all-ones End System ID of its closing C-CASH, including unpopulated ranges. Receipt of C-CASH alone does not prove receipt of the complete train. Completeness describes coverage, not hash agreement.
CSNP train:
The CSNP equivalent of a CASH train.
C-CSNP:
The CSNP equivalent of C-CASH, identified by an all-ones End LSP ID.
Complete CSNP train (complete CSNP set):
The CSNP equivalent of a complete CASH train, terminating with a C-CSNP.
Database coverage:
The portion of the System ID or LSP ID space described by an advertisement at one level, including unpopulated ranges. Whole-database coverage describes every valid node. Coverage is independent of hash agreement and of whether a mismatching range is terminal.
Complete matching CASH train:
A complete CASH train received and compared in full, whose comparisons establish agreement over every covered range under the applicable procedures, including the restarter singleton exception during graceful restart. A zero-hash directive supplies no agreement for its range.
Inventory:
The database contents described by a CASH train. The term applies equivalently to a CSNP train.

1.1.5. Adjacency Roles and Restart State

DIS (Designated Intermediate System):
The router elected per level on a broadcast circuit to originate the pseudonode LSP, periodic CASH advertisements, and terminal-repair range CSNPs.
Non-DIS:
Any other router on that broadcast circuit at that level.
GR (Graceful Restart):
The IS-IS restart procedure of [RFC8706], preserving adjacencies while the restarting router recovers protocol state.
ASH graceful restart:
The point-to-point GR variant defined here, using CASH trains and helper snapshot completion.
Restarting router (restarter):
The router rebuilding its database during a restart exchange.
Helper:
A neighbor retaining its database and providing assistance to a restarting router.
RR (Restart Request):
The Restart TLV flag requesting restart assistance. It is defined in [RFC8706] and retains its semantics under ASH graceful restart.
RA (Restart Acknowledgement):
The Restart TLV flag acknowledging a restart request. It is defined in [RFC8706] and retains its semantics under ASH graceful restart.
SA (Suppress Adjacency):
The Restart TLV flag requesting suppression of adjacency advertisement. ASH graceful restart here applies to RR with SA clear.
Restart epoch:
A four-bit identifier associating restart signaling and successive CASH trains with one restart exchange.
ASH GR Suggested Epoch TLV:
The IIH TLV carrying the restart epoch alongside RR or RA.
GR Control octet:
The CASH header field carrying the restart epoch and S bit. See Section 5.6.2.
S (Snapshot Served):
The GR Control bit indicating that the helper's snapshot has been served and its first CASH train has finished. See Section 5.6.2.
Helper snapshot:
The logical set of LSPs captured by a helper when acknowledging restart, per adjacency and level, excluding fragments originated under the restarter's System ID. It defines the helper's assistance work.
Snapshot obligation:
The requirement for a helper to transmit a snapshot LSP toward the restarter or obtain validated evidence that the restarter holds it. Queuing the LSP does not satisfy the obligation.
Snapshot sealing:
Finalization of the helper's snapshot obligation accounting when its first complete CASH train has been transmitted. Sealing does not establish that the obligations have been satisfied.
Recovering database:
The restarter's changing LSDB as it acquires LSPs from its helpers and ordinary flooding.
Snapshot served (snapshot completion):
The helper-side condition in which every snapshot obligation has been satisfied.
Initial handshake completion:
The restart stage requiring both RA and receipt of a complete CASH train or complete CSNP set for every active level. A complete CASH train can satisfy receipt despite hash mismatches; a range CSNP cannot. This stage permits RR to clear but does not establish synchronization or end helper assistance.
Restart synchronization completion:
The restart stage requiring the reconciliation conditions on every participating adjacency and level. For ASH, a complete matching helper train or valid S supplies the reconciliation condition, without bypassing the initial handshake; ordinary CSNP fallback follows [RFC8706]. It is distinct from both train receipt and a single helper's snapshot completion. See Section 5.6.4.
T1:
The [RFC8706] timer governing restart-request retransmission and the initial handshake.
T2:
The [RFC8706] timer bounding database resynchronization.
T3:
The [RFC8706] timer bounding adjacency retention during restart.

2. Examples

2.1. Plain ASH

Before diving into precise technical details, an example will help introduce the concepts involved and demonstrate the behavior of an exchange.

The exchange consists of initial CASH packets (analogous to CSNPs but carrying node range hashes) followed by PASH packets (analogous to PSNPs) that omit matching ranges and exchange hashes over progressively smaller ranges. Once a range reaches an implementation's terminal repair threshold, a range CSNP (or, when the node holds nothing in the range, a zero-hash PASH directive) synchronizes the databases in the traditional IS-IS manner, see Section 5.4.1. On broadcast circuits, the DIS sends the range CSNP, with non-DIS systems requesting it using a zero-hash PASH as specified in Section 5.5. A terminal range can cover one or more system IDs. ASH operates at the resolution of a system ID (including its pseudonodes), not individual fragments.

The details of packet formats are provided later in Section 7 and Section 6, and the procedures are defined in Section 5.4, but the example can be understood intuitively without those details. For the sake of readability the example encompasses only a database of roughly 3000 fragments over 100 nodes with about 10% of the database not synchronized on start. Details of PSNP packets exchanged are omitted for the same reason. The exact fragment counts shown are explanatory annotations; the wire format carries low-balling encoded population estimates as specified in Section 6.

Initially, both nodes generate and exchange a CASH packet. Node 1 sends to Node 2 the CASH shown in Figure 1, containing node range hashes, some of which will disagree with the peer. An asterisk marks a range whose hash differs from the peer's.

Node1->Node2 (initial CASH) -> 1 CASH packet(s)
Pkt   1 [0000.0000.0000 - FFFF.FFFF.FFFF] (  35 hashes):
1010.0000.0000 - 1010.0000.0001:   47 frags, hash=$ED6174261B52A218
1010.0000.0002 - 1010.0000.0002:  150 frags, hash=$BA8EC0FA6F86557A
1010.0000.0003 - 1010.0000.0006:   87 frags, hash=$2A7D5B4045D54F14
1010.0000.0007 - 1010.0000.0008:   34 frags, hash=$B15068FC7C4F044B
1010.0000.0009 - 1010.0000.000A:   85 frags, hash=$4396112BEAB62D20
1010.0000.000B - 1010.0000.000E:   88 frags, hash=$CCA15999A8BAA5E8 *
1010.0000.000F - 1010.0000.0014:   91 frags, hash=$04CA3A21161464F9 *
1010.0000.0015 - 1010.0000.0017:   79 frags, hash=$82039367F94F611C *
1010.0000.0018 - 1010.0000.001A:   61 frags, hash=$65D4C194A433D2A7
1010.0000.001B - 1010.0000.001C:   92 frags, hash=$5F8701B08AE39C2C
1010.0000.001D - 1010.0000.001F:   75 frags, hash=$0123DD370E42720C *
1010.0000.0020 - 1010.0000.0021:   39 frags, hash=$9CFF63C97F8C86D0
1010.0000.0022 - 1010.0000.0022:  155 frags, hash=$D1513B30C1F1D21D
1010.0000.0023 - 1010.0000.0026:   91 frags, hash=$51B443F4FE1B20DA *
1010.0000.0027 - 1010.0000.0029:   83 frags, hash=$44CEC7E1452B1855
1010.0000.002A - 1010.0000.002E:   86 frags, hash=$8F1B907E974094F3
1010.0000.002F - 1010.0000.0032:   89 frags, hash=$E2A31EC91DB1C4C3 *
1010.0000.0033 - 1010.0000.0036:   85 frags, hash=$E4D0AF41BA0BBDF1 *
1010.0000.0037 - 1010.0000.003B:   82 frags, hash=$13A40B0A950D7694
1010.0000.003C - 1010.0000.003C:   23 frags, hash=$DA7335371FB231CD
1010.0000.003D - 1010.0000.003D:   99 frags, hash=$D14266119B1003CD
1010.0000.003E - 1010.0000.003E:   34 frags, hash=$91D8522BD2EB0523
1010.0000.003F - 1010.0000.003F:   91 frags, hash=$9F206FAF8432046E
1010.0000.0040 - 1010.0000.0040:   88 frags, hash=$79441DDEE60A1F89
1010.0000.0041 - 1010.0000.0044:   87 frags, hash=$ED7F3899858D61EE
1010.0000.0045 - 1010.0000.0046:   22 frags, hash=$382CF99A031E42DE
1010.0000.0047 - 1010.0000.0047:  101 frags, hash=$10B9E7D282B7B8EF
1010.0000.0048 - 1010.0000.004B:   83 frags, hash=$AC0C721830474E1C
1010.0000.004C - 1010.0000.004D:   25 frags, hash=$501B59AE9A65ABC9 *
1010.0000.004E - 1010.0000.004E:  166 frags, hash=$4EF46668F1DD1A7B
1010.0000.004F - 1010.0000.0054:   90 frags, hash=$64362751D60995DA
1010.0000.0055 - 1010.0000.0059:   87 frags, hash=$2771634B6A78AACE
1010.0000.005A - 1010.0000.005C:   91 frags, hash=$E3F65D19CC13C7ED
1010.0000.005D - 1010.0000.0060:   84 frags, hash=$C3205BB177BB816E
1010.0000.0061 - 1010.0000.0063:   52 frags, hash=$D3500D0875EC4B66
Figure 1

Analogously, Node 2 sends an initial CASH with 33 hashes as shown in Figure 2. It may seem counter-intuitive that the ranges do not align, but this is natural since the databases themselves differ. Section 3 addresses this effect in more detail.

Node2->Node1 (initial CASH) -> 1 CASH packet(s)
Pkt   1 [0000.0000.0000 - FFFF.FFFF.FFFF] (  33 hashes):
1010.0000.0000 - 1010.0000.0001:   47 frags, hash=$ED6174261B52A218
1010.0000.0002 - 1010.0000.0002:  150 frags, hash=$B312CA61CDDAF08F
1010.0000.0003 - 1010.0000.0006:   87 frags, hash=$2A7D5B4045D54F14
1010.0000.0007 - 1010.0000.0008:   34 frags, hash=$B15068FC7C4F044B
1010.0000.0009 - 1010.0000.000A:   85 frags, hash=$134574F1DF91FBE5
1010.0000.000B - 1010.0000.000E:   88 frags, hash=$41DA43916CC90C52 *
1010.0000.000F - 1010.0000.0014:   91 frags, hash=$866969306096FD29 *
1010.0000.0015 - 1010.0000.0017:   79 frags, hash=$C2CEDFBA88080A3B *
1010.0000.0018 - 1010.0000.001A:   61 frags, hash=$65D4C194A433D2A7
1010.0000.001B - 1010.0000.001C:   92 frags, hash=$0BA9276510EE03CB
1010.0000.001D - 1010.0000.0021:   92 frags, hash=$4F5A632B673697BA *
1010.0000.0022 - 1010.0000.0022:  155 frags, hash=$6EDDFD41D8C4E0A6
1010.0000.0023 - 1010.0000.0026:   91 frags, hash=$2C2B89EF96A7C7C8 *
1010.0000.0027 - 1010.0000.0029:   83 frags, hash=$878C86D658B81FAD
1010.0000.002A - 1010.0000.002E:   86 frags, hash=$8F1B907E974094F3
1010.0000.002F - 1010.0000.0034:   81 frags, hash=$2684E1CAA3FB8EB7 *
1010.0000.0035 - 1010.0000.0038:   90 frags, hash=$6D1FAC454620D6BB
1010.0000.0039 - 1010.0000.003C:   67 frags, hash=$ADB300A6365F6360
1010.0000.003D - 1010.0000.003D:   99 frags, hash=$CDF517B289695626
1010.0000.003E - 1010.0000.003E:   34 frags, hash=$0365ED0461CA3EDC
1010.0000.003F - 1010.0000.003F:   91 frags, hash=$1EA9199FB3A12017
1010.0000.0040 - 1010.0000.0040:   88 frags, hash=$761D4D297B4BFA45
1010.0000.0041 - 1010.0000.0044:   87 frags, hash=$1C97513E233AD431
1010.0000.0045 - 1010.0000.0046:   22 frags, hash=$382CF99A031E42DE
1010.0000.0047 - 1010.0000.0047:  101 frags, hash=$022CA678714C04D5
1010.0000.0048 - 1010.0000.004B:   83 frags, hash=$AC0C721830474E1C
1010.0000.004C - 1010.0000.004D:   25 frags, hash=$AA9C89D8384E152E *
1010.0000.004E - 1010.0000.004E:  166 frags, hash=$D82B8A40F2F6B75D
1010.0000.004F - 1010.0000.0054:   90 frags, hash=$64362751D60995DA
1010.0000.0055 - 1010.0000.0059:   87 frags, hash=$2771634B6A78AACE
1010.0000.005A - 1010.0000.005C:   91 frags, hash=$10DAD5C8C452DDCB
1010.0000.005D - 1010.0000.0060:   84 frags, hash=$9316E89831EE599B
1010.0000.0061 - 1010.0000.0063:   52 frags, hash=$D3500D0875EC4B66
Figure 2

At this point both nodes take the range mismatches they detected and split them into smaller ranges. Ranges selected for terminal repair are resolved using range CSNPs and ordinary PSNP and LSP processing, or the zero-hash directive when locally empty, as specified in Section 5.4.1. This synchronization proceeds in parallel, independent of any further ASH exchanges. Figure 3 shows an excerpt of a PASH that subdivides Node 2's mismatching range 1010.0000.001D through 1010.0000.0021. The two subranges cover that entire range; other refinement branches and terminal repairs are omitted.

Node1 -> Node2 (after cuts) -> 1 PASH packet(s)
1010.0000.001D - 1010.0000.001F:   75 frags, hash=$0123DD370E42720C *
1010.0000.0020 - 1010.0000.0021:   39 frags, hash=$9CFF63C97F8C86D0
Figure 3

Further mismatches are refined until they match or reach terminal repair. A singleton mismatch requires terminal repair because ASH cannot subdivide a System ID into individual fragments.

Only mismatching ranges require further exchange; matching ranges need no per-fragment inventory. The number of repair packets depends on the selected terminal ranges and their fragment populations.

2.2. ASH GR

This example shows the simplest form of ASH graceful restart, with one restarting router Restarter and two helpers Helper1 and Helper2, each on a point-to-point adjacency with Restarter and with ASH fully negotiated. The helpers hold the same database: sixteen systems, each with one non-purged LSP fragment. Restarter's System ID is 0000.0000.0002. We assume no packet loss or database changes during the exchange. Restarter's System ID is isolated as specified in Section 5.6. Many optimizations in ASH GR are possible but not discussed or shown here for the sake of simplicity.

Restarter sends an IIH with RR set, SA clear, and its restart epoch. Each helper acknowledges with RA and the same epoch and captures its helper snapshot. The example uses epoch 3. RR, RA, and the epoch signaling are explained in Section 5.6.2. Each CASH train fits in one PDU with header bounds 0000.0000.0000 through FFFF.FFFF.FFFF; with that each PDU is also a C-CASH.

Each helper sends its first complete CASH train with S clear. Sending its closing C-CASH seals that helper's snapshot obligation accounting, as explained in Section 5.6.1.3. The S (Snapshot Served) bit is explained in Section 5.6.2. In this example, both helpers queue their remaining snapshot LSPs for normal flooding and begin transmitting them to Restarter. Receipt of RA and a complete train from each helper satisfies Restarter's initial handshake requirements, but the mismatching hashes do not establish synchronization; these separate conditions are defined in Section 5.6.4. PEER MISMATCH below marks a hash differing from Restarter's local inventory. NO COMPARE marks Restarter's isolated System ID, whose hash difference is ignored during restart.

Helper1 -> Restarter: CASH / C-CASH, epoch=3, S=0
Header range: 0000.0000.0000 .. FFFF.FFFF.FFFF
Start           End             Hash
0000.0000.0001  0000.0000.0001   $8C3A6D21F907B45E  PEER MISMATCH
0000.0000.0002  0000.0000.0002   $52E8A1C73B9046DF  NO COMPARE
0000.0000.0003  0000.0000.0004   $6EB348F808C9AE4E  PEER MISMATCH
0000.0000.0005  0000.0000.0006   $A72D193C54E60B81  PEER MISMATCH
0000.0000.0007  0000.0000.0008   $D18F42A76C0935BE  PEER MISMATCH
0000.0000.0009  0000.0000.000A   $39C6B871E2A40F5D  PEER MISMATCH
0000.0000.000B  0000.0000.000D   $B4057E2D9A61C38F  PEER MISMATCH
0000.0000.000E  0000.0000.0010   $71DA03F6C82B954E  PEER MISMATCH

Restarter initially holds only its own fragment and sends the following nearly empty complete CASH train to each helper. Gaps within the CASH header bounds describe absent inventory, as specified in Section 6; no entries for the other systems are needed.

Restarter -> Helper1, Helper2: CASH / C-CASH, epoch=3, S=0
Header range: 0000.0000.0000 .. FFFF.FFFF.FFFF
Start           End             Hash
0000.0000.0002  0000.0000.0002   $E94B60D28A173CF5  NO COMPARE

Restarter's own hash differs from the helpers' copy. The difference is confined to Restarter's isolated singleton range, so neither side treats it as a mismatch requiring repair or preventing agreement analogous to normal GR. The other fifteen systems are absent at Restarter and remain subject to ordinary reconciliation. Repair requests for LSPs already queued by a helper add no further flooding work; helper-side terminal repair is explained in Section 5.6.1.3.

While flooding continues, Restarter receives the fragments for systems 0003 through 0006 from Helper1 and systems 0007 through 000A from Helper2. In this simple example, Restarter has drained its own pending reconciliation work toward each helper and sends another periodic CASH, without waiting for the helpers' flooding to finish, as specified in Section 5.4.2. This train describes its recovering database:

Restarter -> Helper1, Helper2: CASH / C-CASH, epoch=3, S=0
Header range: 0000.0000.0000 .. FFFF.FFFF.FFFF
Start           End             Hash
0000.0000.0002  0000.0000.0002   $E94B60D28A173CF5  NO COMPARE
0000.0000.0003  0000.0000.0006   $C99E51C45C2FA5CF  PEER MATCH
0000.0000.0007  0000.0000.000A   $E849FAD68EAD3AE3  PEER MATCH

At Helper1, the hash for systems 0007 through 000A now matches, although Helper1 has not yet transmitted those fragments to Restarter. This evidence of possession satisfies their snapshot obligations and cancels Helper1's pending flooding for them. Likewise, Helper2 can cancel pending copies of systems 0003 through 0006. Satisfaction of snapshot obligations by evidence of possession is explained in Section 5.6.1.3. The differences for system 0001 and systems 000B through 0010 still require repair, but their LSPs are already queued. Their existing transmission resolves those terminal ranges. LSP acknowledgements and any required retransmissions follow ordinary IS-IS procedures.

Once Helper1 transmits its last required snapshot LSP, all its snapshot obligations have been satisfied by transmission or evidence of possession. Helper1 sends a CASH notification with S set and the same restart epoch. Helper2 likewise signals S when its snapshot obligations have been satisfied. Neither helper waits for acknowledgements or retransmissions to finish before signaling Snapshot Served. Restarter accepts each helper's S and considers that adjacency synchronized. Restarter sends each helper a complete CASH train describing its database for final reconciliation. Helper's S signaling and the final CASH response are explained in Section 5.6.2 and Section 5.6.1.4, respectively.

Helper1 -> Restarter: CASH / C-CASH, epoch=3, S=1
Header range: 0000.0000.0000 .. FFFF.FFFF.FFFF
Start           End             Hash
0000.0000.0001  0000.0000.0001   $8C3A6D21F907B45E
0000.0000.0002  0000.0000.0002   $52E8A1C73B9046DF  NO COMPARE
0000.0000.0003  0000.0000.0004   $6EB348F808C9AE4E
0000.0000.0005  0000.0000.0006   $A72D193C54E60B81
0000.0000.0007  0000.0000.0008   $D18F42A76C0935BE
0000.0000.0009  0000.0000.000A   $39C6B871E2A40F5D
0000.0000.000B  0000.0000.000D   $B4057E2D9A61C38F
0000.0000.000E  0000.0000.0010   $71DA03F6C82B954E

3. Node Ranges

When nodes advertise node range hashes to each other, it would obviously be useful for cache-based implementations to agree on which ranges to use, as this would make caching much more effective. However, while this seems viable in theory, implementing it across many interfaces would effectively require a global synchronization protocol - something impractical in a network where nodes constantly add, remove, and update fragments asynchronously. These ongoing changes continually shift what the "optimal" hash ranges are, and with enough churn, such a range negotiation protocol might never converge.

Alternatively, providing a fast way to reconstruct the Merkle hash for a "mismatched" range reduces the need for perfect range alignment. Since hashes are built on system ID boundaries, maintaining a Merkle hash per system ID allows a node to quickly recompute the required hashes whenever received ranges differ from cached ones.

As a second consideration, even though a fully stable network could in theory be represented by a single hash covering the entire LSDB, doing so is neither desirable nor beneficial. Since an ASH packet must be sent anyway, it is much better to fill it with as many range hashes as possible. This limits the work required when a collision occurs within one of the ranges and also reduces the risk of hash collisions, as discussed in Section 9.4.

In summary, a node should avoid compressing beyond the point where a single CASH covers the entire database. Ideally, one ASH should contain at most about (MTU / Node Range Hash Entry Size) hashes to keep collision probabilities low, as described in Section 9.4. Due to the efficiency of recomputing node range hashes on the fly, there is no need to negotiate or agree on ranges with peers.

4. Hash Functions

4.1. Hash Function for a Fragment

Each fragment generates a 64-bit siphash-1-3 [SIPHASH] from its full SNP description. The salt key is given in Appendix A.

If a fragment hash computes to zero or to the 64-bit all-ones value, the value MUST be replaced with the constant 1.

To validate implementation correctness, a reference hash is provided in Figure 4.

Hash Variant: Siphash-1-3:64Bits
Fragment ID: 0101:0101:0000.01-01
Seq# $0001
Csum: $0001
Len: 0512
Hash $6EB348F808C9AE4E
Figure 4

4.2. Fast, Incremental, Self-Inverse Hashing Function for 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 also beneficial to support very fast splitting and merging of such sets, especially when two hashes differ in which fragments they contain.

Further discussion of such hashes can be found in [HASHES], but the design space is simplified here since cryptographic security is not a concern.

The hash for a set of fragments is computed by XOR'ing their individual fragment hashes. This makes it straightforward and very fast to update the hash when a fragment is added, removed, or its checksum changes. As a result, less specific ranges can quickly derive their raw aggregate by XOR'ing the raw aggregates of disjoint more specific ranges that together cover them, when those are available.

Each fragment hash has already undergone reserved-value replacement. XOR'ing such hashes can nevertheless produce zero or all-ones, so the completed range hash requires a separate replacement step.

Range aggregation, splitting, and incremental updates MUST use raw XOR aggregates of the fragment hashes defined above, before range-level reserved-value replacement. The replacement below applies only to the final range value used for comparison or advertisement. A remapped node or range value MUST NOT be used in place of its raw aggregate when computing another range.

For a non-empty range, if a node range hash computes to zero or to the 64-bit all-ones value, the value MUST be replaced with the constant 1. Zero is reserved for the terminal wire directive described in Section 5.4. The all-ones value is reserved and MUST NOT be transmitted.

5. Procedures

5.1. ASH Support Negotiation

Rather than defining a new, dedicated IIH TLV, support for ASH is negotiated using the generic Hello Capability TLV defined in [ID.draft-ginsberg-lsr-hello-capability-00]. This document requests allocation of two bits (Bits TBD) from the "IS-IS Bit Values for Hello Capability TLV Flags" registry created by that document; see Section 11:

A single combined "ASH capable" bit was considered and rejected in favor of these two independent bits: implementations commonly wish to enable ASH asymmetrically, for example decoding and verifying received ASH packets from a peer while still originating ordinary CSNPs/PSNPs itself (a conservative or "canary" rollout of newly written decode logic), or the converse. A single bit cannot convey to the peer which direction(s) are actually safe or expected, whereas two independent bits let each side advertise exactly what it will accept and what it may send.

A node MUST NOT originate CASH/PASH packets on an adjacency unless the peer has most recently advertised ASH_RX on that adjacency. A node MUST treat an adjacency as not ASH capable for reception and fall back to ordinary CSNP/PSNP processing whenever it has not itself advertised ASH_RX, regardless of what the peer sends. Receipt of a CASH/PASH packet while ASH_RX is not being advertised is anomalous input and MUST NOT be treated as fatal to the adjacency. The implementation SHOULD log the event and fall back to requesting a full CSNP/LSP resynchronization on that adjacency. Loss of the peer's Hello Capability TLV (adjacency restart, or a peer that does not implement [ID.draft-ginsberg-lsr-hello-capability-00] at all) is equivalent to both bits being clear.

On broadcast circuits, each level's IIH is a distinct PDU, so the two bits are advertised, and can differ, independently per level. On point-to-point circuits a single IIH is shared by whichever levels are enabled on that circuit; the Hello Capability TLV of [ID.draft-ginsberg-lsr-hello-capability-00] is not level-scoped, so on a point-to-point circuit running both Level 1 and Level 2, ASH_RX and ASH_TX necessarily apply identically to both levels; an implementation MUST NOT attempt to advertise or negotiate them differently per level on such a circuit.

No additional capability information (sub-TLVs) is defined by this document at this time; future extensions may make use of the sub-TLV mechanism of [ID.draft-ginsberg-lsr-hello-capability-00] to advertise additional ASH-related capability information.

5.2. Advertising and Receiving CASHes

Advertising of standard CSNPs is extended or replaced with CASH advertisements when this feature is supported. Analogous to CSNPs, CASHes are sent periodically at a configured interval. Since both CSNPs and CASHes carry range information in their headers, they can be freely mixed, depending on which level of fragment "compression" best fits the situation. In practice, sufficiently specific range mismatches will naturally fall back to SNP exchanges or flooding to resolve remaining differences.

5.3. Advertising and Receiving PASHes

Where PSNPs are used, PASHes may extend or substitute the exchange as long as the rules of Section 5.4 are followed.

5.4. Refinement Rules

ASH exchanges are per-level, analogous to CSNP/PSNP exchanges. CASH and PASH packets are scoped to the IS-IS level (Level 1 or Level 2) of the adjacency on which they are sent, just as CSNPs are.

Fragments in purge state (remaining lifetime of zero) are NOT included in ASH hash computations, consistent with the treatment of purges in CSNP exchanges. Purges are handled through normal IS-IS flooding procedures independently of ASH.

The set of fragments covered by the ASHes sent on a circuit MUST be the same set that a CSNP sent on that circuit would describe. An implementation that restricts per circuit which LSPs it floods and advertises in CSNPs (e.g., by area address) MUST either compute the ASHes over that restricted set or MUST NOT send ASHes on that circuit.

When a node receives an ASH where any of the contained hashes does not match after recomputation or comparison, it MUST send PASHes with Merkle hashes covering the mismatched ranges. These new hashes MUST be more specific than the range where the mismatch occurred.

Alternatively, instead of more specific PASH hashes, a node MAY treat the mismatched range as a terminal range and repair it immediately as specified in Section 5.4.1. This may be preferable when the mismatch affects only a small number of LSPs.

When refinement reaches a range that has no matching non-purged fragments in the local database, silence is not sufficient: independently selected range boundaries can prevent the remote node from reaching the same terminal range. The node MUST therefore send a PASH entry for the valid, non-inverted range with its hash set to zero on a point-to-point circuit. Broadcast circuits instead follow the role-directed procedures in Section 5.5.

A zero hash in a CASH or PASH entry is a terminal repair directive, not a hash mismatch to refine further. Range validity is checked before interpreting the hash: an entry whose Range End is smaller than its Range Start MUST be discarded even when its hash is zero. For a valid zero-hash entry, a receiver MUST NOT compare or subdivide the range. If it holds non-purged fragments in the indicated range, it MUST send every such fragment using normal IS-IS flooding procedures. It MUST NOT answer the directive only with a PSNP, because that would add a redundant request/response round before the same fragments are flooded. If it holds no such fragments, it MUST silently ignore the directive: it MUST NOT answer with a PASH entry for the range, including a zero-hash entry, and MUST NOT refine the range further. It MAY instead send an empty range CSNP covering the range, following Section 5.4.1, Paragraph 7. On broadcast circuits, a zero-hash entry from a non-DIS to the DIS is a range-CSNP request instead, handled as specified in Section 5.5.

The value zero is reserved and MUST NOT be emitted as the result of any fragment-hash computation or any non-empty range-hash computation. In a valid Node Range Hash Entry, zero is a terminal repair directive, never a computed hash. On a point-to-point circuit, and when sent by the DIS on a broadcast circuit, it requests direct flooding by the receiver, independently of the sender's holdings indicated by Fragment Population. When sent by a non-DIS to the DIS, it requests range-CSNP repair as specified in Section 5.5, regardless of the non-DIS's holdings. It does not make an otherwise malformed range valid.

The all-ones value is reserved and MUST NOT be transmitted.

An implementation MAY stop refinement when a mismatching range contains sufficiently few locally held fragments, even when the range covers more than one system ID. Broadcast circuits follow Section 5.5. On a point-to-point circuit, if it holds none of the fragments in that terminal range, it MUST send the zero-hash directive specified above. If it holds fragments in the range, it MUST repair the range as specified in Section 5.4.1.

5.4.1. Terminal Range Repair on Point-to-Point Circuits

On a point-to-point circuit, when a valid received CASH or PASH entry explicitly advertises zero Fragment Population for a mismatching range, the receiver MAY omit the range CSNP and directly flood its locally held, non-purged fragments within that range. The peer has no inventory to contribute for the advertised range. This exception does not apply to broadcast circuits or to ranges outside the advertised boundaries. A zero population accompanied by a nonzero hash MUST be treated as a zero hash, and the receiver SHOULD report the inconsistency. This exception does not suppress required ordinary flooding, acknowledgements, or retransmissions.

A gap within valid CASH header bounds supplies the same empty-inventory information implicitly, as specified in Section 6. It receives the same zero-hash directive processing; no explicit wire entry is needed to trigger direct flooding.

An empty-population advertisement does not satisfy graceful-restart snapshot obligations. If repair omits the range CSNP and directly floods local fragments, every required snapshot LSP MUST still have actually been transmitted toward the restarter, or be covered by validated evidence of possession, before the helper signals Snapshot Served (S). Neither the empty advertisement nor merely queuing the resulting flood is such evidence. The restart epoch and completion requirements in Section 5.6 remain unchanged.

These procedures apply except for the helper-side graceful-restart exception in Section 5.6.

Only one neighbor may select a range for terminal repair, so its action must reconcile both directions. Except for an explicitly empty peer range as specified above, a range CSNP reveals locally absent fragments as well as those held; PSNPs or flooding alone do not.

When a node performs terminal repair for a range in which it holds non-purged fragments, it MUST send a range CSNP covering the terminal range and listing every non-purged fragment it holds in that range, unless it uses the zero-population entry exception above. Otherwise, it MUST NOT repair such a range with PSNPs or by flooding its own fragments alone. It MAY additionally flood its fragments in the range. If it holds none, it MUST send the zero-hash PASH directive specified in Section 5.4.

The following rules apply to range CSNPs:

  • The Start and End LSP IDs MUST lie within, or on the boundaries of, the terminal range: the first LSP ID of its lowest system ID through the last LSP ID of its highest system ID. When the listed fragments do not fit into one PDU, the range is covered by a series of CSNPs with consecutive, non-overlapping LSP ID ranges, as for periodic CSNPs.
  • A node MAY combine terminal ranges that are contiguous or overlapping into one range CSNP or series. It SHOULD NOT extend a range CSNP over system IDs outside the ranges found mismatching.
  • A sender MUST NOT use C-CSNP for terminal repair. If the range reaches the all-ones End LSP ID, it ends at the preceding LSP ID instead and directly floods the excluded fragment if held. A receiver MUST NOT treat a range CSNP as completing the [RFC8706] database-summary receipt requirement.
  • Range CSNPs are sent only on adjacencies using ASH and processed using ordinary IS-IS CSNP procedures.

Broadcast circuits follow Section 5.5.

5.4.2. Reconciliation Pacing and Amplification Avoidance

A node that detects a mismatch in a received CASH refines the disputed range with progressively more specific PASHes until the hashes match or refinement reaches a range that requires normal SNP exchange or flooding (see Section 5.4). The PASH refinement and the subsequent repair form one reconciliation attempt. For a sender, a reconciliation remains pending while it has PASHes or PSNPs to send to that peer, or while its own LSP transmissions or retransmissions toward that peer resulting from that reconciliation remain outstanding.

A new periodic CASH sent while a previous reconciliation remains pending typically rediscovers the same disagreement and starts an overlapping refinement. Two overlapping attempts can produce roughly twice the PASH, PSNP, and LSP traffic of one; additional attempts increase the traffic further without a natural bound. In a ~6,700-fragment/40-node experiment, overlapping attempts generated PSNP requests equal to roughly five times the total fragment count, with the count still increasing when observed. The amplification resulted from overlapping reconciliation attempts rather than from the topology scale or hash function.

For each peer and level, a node MUST limit reconciliation to one attempt at a time. The node MUST NOT send a new periodic CASH while its own PASHes or PSNPs from the previous attempt remain to be sent to that peer, or while its own LSP transmissions or retransmissions toward that peer resulting from that attempt remain outstanding. The next periodic CASH can start after all such local work has completed. This rule applies equally to helpers and restarters during graceful restart. It does not require the sender to determine whether the peer has pending work or to wait for the peer's flooding to finish. This requirement bounds the traffic caused by each divergence while delaying only a redundant probe.

Before a peer session completes its initial full-coverage CASH exchange, a node MAY use ordinary CSNP framing as a conservative fallback. After that exchange completes, deferring a periodic CASH does not require the node to introduce a CSNP. Implementations SHOULD expose a counter for deferred CASH cycles. Such a counter identifies peers that do not complete reconciliation and helps determine whether the periodic interval is shorter than the time required to exchange the necessary PASHes, PSNPs, and LSPs.

When refinement reaches a range that requires normal SNP exchange or flooding, the node MUST initiate that repair without waiting for another periodic CASH. Transitioning from PASH refinement to SNP exchange or flooding does not complete the reconciliation attempt; completion occurs only after the required PASHes, PSNPs, and resulting LSP transmissions and retransmissions have completed.

ASH repair can generate a large number of PSNP entries while received repair LSPs simultaneously require acknowledgment. When an implementation schedules both classes of entry through the same PSNP transmission mechanism, it SHOULD transmit acknowledgments for received LSPs before PSNP entries generated to request or describe further reconciliation. Delaying those acknowledgments behind a reconciliation backlog can cause the sender's retransmission timer to expire, adding duplicate LSP traffic and extending convergence. A PSNP can use any space remaining after the acknowledgments for reconciliation entries.

5.5. Broadcast Circuit Operation

Graceful restart on broadcast circuits uses traditional procedures, not ASH, as specified in Section 5.6.

On a broadcast circuit, only the Designated Intermediate System (DIS) for a level MAY originate periodic CASHes for that level. The DIS MUST NOT replace a CSNP with a CASH unless every Up adjacency at that level has advertised ASH_RX. Otherwise it MUST send an ordinary CSNP.

PASH refinement on a broadcast circuit is performed between the DIS and the non-DIS systems. The DIS processes PASHes originated by non-DIS systems. A non-DIS processes PASHes originated by the current DIS, but MUST NOT process a PASH originated by another non-DIS.

PASHes that would generate the same SNP requests or flooding MAY be reconciled by the DIS before it reacts.

Terminal repair on a broadcast circuit has the same requirement as point-to-point repair: flooding locally held fragments or listing them in PSNPs alone cannot reveal fragments held only by the other system. The other system need not independently reach the same terminal range. Only the DIS originates the range CSNPs used for this repair; a non-DIS MUST NOT originate a range CSNP.

When the DIS decides that a received mismatching range is terminal, it MUST send a range CSNP covering that range and listing its locally held non-purged fragments. It MUST do so even when it holds no such fragments: an empty range CSNP makes non-DIS systems flood fragments they hold in that range.

When a non-DIS decides that a received mismatching range is terminal, it MUST schedule its locally held non-purged fragments in that range for normal flooding and send a zero-hash PASH entry for the same range to the DIS. It MUST send this entry even when it holds no such fragments. In this direction the zero hash requests a range CSNP from the DIS; it does not assert that the non-DIS has an empty database in the range.

On receiving a valid zero-hash CASH or PASH entry from the DIS, a non-DIS MUST schedule its locally held non-purged fragments in that range for normal flooding. It MUST NOT answer the directive with a PASH entry for the range, including a zero-hash entry, and MUST NOT refine the range further. When it holds no such fragments it ignores the directive. A non-DIS MUST NOT send a range CSNP in either case.

On receiving a valid zero-hash CASH or PASH entry from a non-DIS, the DIS MUST schedule its locally held non-purged fragments in the range for normal flooding and send a range CSNP covering the range, even when the range is locally empty. It MUST NOT return a zero-hash PASH directive in response. The range CSNP exposes fragments held only by a non-DIS and allows non-DIS systems to request fragments held only by the DIS through normal PSNP processing. This is role-directed terminal repair, not another hash comparison or subdivision step, and does not create directive loops.

Range CSNP coverage, segmentation, and merging follow Section 5.4.1, Paragraph 7. A range CSNP is processed by all receiving systems using normal broadcast-circuit CSNP procedures, including systems that did not participate in the PASH exchange.

When the DIS on a broadcast circuit changes, every system on that circuit MUST discard any in-flight CASH origination state and any PASH refinement state associated with the prior DIS for that level, and the new DIS MUST begin CASH origination afresh rather than resuming a sequence started by its predecessor. A PASH received from a system after that system has ceased to be the current DIS MUST NOT be processed, consistent with the role rules above.

A DIS change MUST NOT by itself be treated as invalidating database synchronization already achieved for ranges other than the pseudonode LSP whose content changes as a result of the election. In particular, a DIS change alone is not sufficient reason to re-run terminal repair, or to fall back to a full CSNP exchange of the entire node-ID space, for ranges where CASH/PASH refinement had already converged; an implementation SHOULD resume refinement from a clean, empty CASH/PASH state rather than discarding and recomputing synchronization status for the whole circuit.

5.6. Graceful Restart on Point-to-Point Circuits

On a point-to-point adjacency eligible for graceful restart under [RFC8706], ASH negotiation is complete when both neighbors advertise both ASH_RX and ASH_TX and have ASH transmission and reception enabled at every common active level, with at least one common active level. When ASH negotiation is complete, both neighbors MUST use ASH graceful restart on that adjacency. Otherwise, both neighbors MUST use traditional graceful restart as specified in [RFC8706] and MUST NOT use ASH graceful restart on that adjacency. An ineligible adjacency does not participate in graceful restart. ASH graceful restart is inherent in ASH support, with no separate capability. Adjacency preservation, restart acknowledgement, and remaining holding time retain their meanings from [RFC8706].

These procedures are initiated by a restarting router sending RR set and Suppress Adjacency (SA) clear. They do not change the procedures for SA or planned restart in [RFC8706]. Broadcast circuits continue to use the graceful-restart procedures of that specification. On a broadcast circuit, the restarter and its helpers MUST use traditional CSNP, PSNP, and LSP procedures for the restart exchange, regardless of ASH capabilities. They MUST NOT substitute CASH or PASH for required restart inventory or repair, or use ASH signaling to establish restart state or satisfy restart completion conditions. ASH-specific restart signaling MUST be ignored on broadcast circuits.

5.6.1. Theory of Operation

The restarting router requests complete CASH trains instead of complete CSNP sets from its helpers. Only helpers set the S (Snapshot Served) bit. The restarter MUST NOT set S in any CASH PDU it sends for this restart exchange. A helper MUST ignore the value of S in every CASH PDU received from the restarter.

5.6.1.1. Initiation and Snapshot Capture

The restarting router conveys its restart epoch with RR, and each helper echoes it in its CASH trains. Successive trains and repeated RR hellos belonging to the same restart retain that epoch.

The restarter MAY store the epoch in persistent memory and increment it on restart. If no epoch history is available, the restarter MUST choose it uniformly at random on restart. When recent epoch history is available, it SHOULD avoid reusing a recent value.

Epoch validation follows Section 5.6.3. Epoch matching does not by itself establish train completeness or database synchronization, and does not replace authentication.

On receipt of RR, a helper MUST respond with a complete CASH train for each active level on the adjacency, with the epoch indicated by the Suggested Epoch TLV accompanying RR. This requirement also applies to repeated RR hellos with the same epoch; an in-progress train MAY serve that request. It MUST acknowledge RR with RA according to [RFC8706]. CASH reconciliation replaces the complete CSNP set and unconditional setting of SRMflags in Section 3.2.1 of that specification: the helper MUST NOT initiate a full database flood solely because it received RR.

Each helper captures its helper snapshot when acknowledging the restart with RA. Its live database and ordinary flooding continue independently.

5.6.1.2. Restarter Reconciliation

As ASH packets arrive, the restarting router MUST compare their advertised hashes with its recovering database. To reconcile differences, it MUST use PASHes and/or terminal repair to solicit missing or mismatched LSPs from the helper.

The restarting router SHOULD send a complete CASH train describing its recovering database when requesting restart with RR.

The restarter's own LSPs can legitimately differ from the pre-restart copies held by helpers. Both the helper and the restarter MUST isolate the restarter's System ID as a separate singleton range in CASH and PASH hash advertisements covering that ID throughout the restart exchange. A hash mismatch confined to that singleton MUST NOT trigger refinement or terminal repair, or prevent CASH agreement. All other System IDs remain subject to ordinary comparison and reconciliation. This exemption applies only to a hash mismatch on that exact singleton, not to a wider range containing it. Matching hashes and zero-hash repair directives retain their ordinary meanings. The helper's own System ID requires no special isolation.

The restarting router SHOULD periodically advertise its recovering database in CASH trains. These advertisements let helpers learn which fragments the restarting router has already acquired, including those supplied by other helpers, rather than all continuing to flood the same fragments. It MUST pace these advertisements according to Section 5.4.2 and MUST NOT substitute a full-database CSNP of its partially recovered database for a deferred CASH advertisement. Terminal-repair range CSNPs remain permitted.

5.6.1.3. Helper Snapshot Service

Completion of the helper's first full CASH train transmission seals its snapshot obligation accounting at that level. Snapshot sealing does not establish that the snapshot has been served. When sending a complete CASH train, the helper SHOULD queue its remaining snapshot LSPs for normal flooding. The helper MUST NOT infer possession from silence or the omission of a range from a PASH. On receiving a CASH or PASH from the restarter, the helper MUST process mismatching ranges through refinement or terminal repair. Terminal repair uses ordinary IS-IS CSNP, PSNP, and LSP flooding procedures, subject to the helper-side exception below; resulting LSP transmissions MUST be queued without requiring receipt of a complete CASH train from the restarter.

During this exchange, a helper performing terminal repair MAY send its locally held non-purged fragments in the terminal range directly, without sending a range CSNP or an empty-range directive to solicit the restarter's inventory. This is an exception to Section 5.4.1 for the helper only. The restarter continues to use ordinary terminal repair. Neither this exception nor snapshot completion suppresses required LSP acknowledgements or retransmissions.

While a snapshot LSP still awaits transmission or validated evidence of possession by the restarter, a newer accepted instance of that LSP MUST replace the version required by the snapshot. Transmission or validated possession of that version, or a newer one, satisfies the snapshot obligation for that LSP.

Once that obligation has been satisfied, a later instance of the same LSP is ordinary flooding work: it MUST NOT reopen the satisfied obligation or delay snapshot completion. New LSP IDs likewise MUST NOT extend the snapshot. These rules bound restart assistance to the snapshot; they MUST NOT suppress ordinary flooding, acknowledgements, or required retransmissions of newer or newly learned LSPs toward the restarter.

Once a helper has completed the reconciliation work resulting from that exchange, it MUST present its database again in another complete CASH train, without requiring a CASH advertisement from the restarter first. The restarter compares it against its recovering database and continues reconciliation as needed.

Helpers MUST continue periodic CASH advertisements and required reconciliation responses while providing restart assistance, including after RR clears. Clearing RR indicates completion of the initial handshake, not database synchronization.

5.6.1.4. Snapshot Completion and Final Response

Before signaling snapshot completion, each required LSP MUST have actually been transmitted, unless validated evidence demonstrates that the restarter already possesses it. Queuing or scheduling does not satisfy this requirement, and deferred refinement does not remove fragments from it. Acknowledgements and retransmissions need not have completed. Subsequent flooding does not delay snapshot completion. The helper signals completion with S as specified in Section 5.6.2.

For example, a helper can transmit version 1 of a snapshot LSP, satisfying its obligation, and then learn version 2 and flood it normally. A CASH comparison made between those events can mismatch. Such a mismatch does not invalidate the served snapshot or prevent completion through the helper's S indication, subject to the initial handshake requirements in Section 5.6.4. S does not assert that version 2 has been received; its delivery remains ordinary flooding and retransmission work.

On receiving a complete matching helper CASH train, the restarter SHOULD respond with a complete CASH train describing its recovering database at that level, even if it has already accepted that helper as synchronized.

When the restarter accepts an S indication from a helper for the current restart epoch, it MUST send that helper a complete CASH train describing its database at that level, even if it already considers the helper synchronized. Every CASH PDU in this train MUST carry the epoch of that restart exchange. The restarter may use one such train to answer repeated S indications from the same helper on the same adjacency and level for that epoch. This transmission MUST NOT delay graceful restart completion. If restart completes before the train has been fully sent, the restarter MUST still finish sending it. Adjacency teardown, withdrawal of ASH negotiation, or a subsequent restart cancels this transmission requirement for the old exchange.

Completion is determined independently for each adjacency and active level by the conditions in Section 5.6.4.

5.6.2. Restart Signaling and CASH Encoding

The Restart TLV (Type 211) remains unchanged from [RFC8706]. A router with ASH transmission and reception enabled at every locally active level on a point-to-point circuit MUST accompany its RR with an ASH GR Suggested Epoch TLV, without waiting to learn its neighbor's capabilities. This separate IIH TLV has Type TBD-ASH-GR, Length 1, and the following Value:

                                           No. of octets
             +---------------------------+
             | Reserved (4) | Epoch (4)  |     1
             +---------------------------+

The TLV applies only to RR or RA in the Restart TLV in the same IIH, irrespective of TLV order. Senders MUST NOT include it without RR or RA. A receiver MUST NOT infer a restart request or acknowledgement from this TLV alone.

The low-order four bits of the Epoch octet encode the restart epoch, with all values 0 through 15 valid. Its high-order four bits are reserved: senders MUST transmit them as zero and receivers MUST ignore them. The restarter MUST put its current epoch in the TLV accompanying RR. A helper accepting ASH graceful restart MUST echo that epoch in the TLV accompanying RA. The RA MUST identify the restarter as required by [RFC8706]. Selection and validation MUST follow IIH authentication and account for all Hello Capability TLVs, independently of their order. For a selected ASH exchange, missing, malformed, or duplicate Suggested Epoch TLVs, an invalid or duplicate Restart TLV, or an RA with a mismatched target, MUST cause the associated restart signaling to be ignored without restart-related state changes or fallback to ordinary restart processing of that signaling; other IIH contents are processed normally. An RA with a mismatched epoch is handled as specified in Section 5.6.3.

The Suggested Epoch TLV offers ASH graceful restart; it does not by itself select it. If the eligibility rule above is not met, a receiver MUST ignore this TLV and process the unchanged Restart TLV using ordinary procedures, including RA and a complete CSNP set when eligible. Such an RA does not echo the Suggested Epoch TLV. The restarter MUST accept that ordinary exchange rather than requiring CASH or an epoch-bearing RA. Peers unaware of the new TLV can ignore it without encountering a modified Type 211 format.

The formerly reserved octet at offset 6 in the CASH fixed header is the GR Control octet:

                7   6   5   4   3   2   1   0
              +---------------+-----------+---+
              | Restart Epoch | Reserved  | S |
              +---------------+-----------+---+

Bits 7 through 4 carry the epoch, using the same numeric value as the Suggested Epoch TLV. Bit 0 is S (Snapshot Served). Bits 3 through 1 are reserved and MUST be transmitted as zero and ignored on receipt. Except for retained completion signaling described below, the octet MUST be zero outside a restart exchange. It MUST NOT establish restart state on receipt. The corresponding PASH octet remains reserved and is transmitted as zero.

Each CASH in an active exchange MUST carry its restart epoch. The restarter MUST transmit S clear; only a helper can signal snapshot completion. Every PDU in the helper's first CASH train for a new restart exchange MUST have S clear, even if the snapshot is served before that train finishes. The helper MUST NOT set S merely because the snapshot's LSPs have been queued. It MUST set S only after the snapshot transmission work has drained onto the wire as specified in Section 5.6.1.4 and the first CASH train has finished, and send a paced CASH notification. It MUST retain S on subsequent CASH for that exchange and MAY continue sending S with the completed epoch until the next restart request; it need not determine when the restarter finishes. A new exchange starts with S clear. Clearing RR or receiving S clear MUST NOT revoke accepted completion.

A receiver MUST validate and authenticate the CASH and associate it with the current neighbor, adjacency, level, and epoch before accepting S. An indication received before initial inventory completion MAY be retained for that same exchange. A repeated RR with the same epoch MUST NOT reset the snapshot or its earned completion indication. Adjacency replacement, exchange timeout, or abort MUST invalidate pending receiver completion state; retained helper signaling does not create a new exchange. Numerical epoch values do not establish ordering; reuse of a four-bit value can make delayed signaling indistinguishable from the current exchange.

5.6.3. Epoch Mismatch

During an active exchange, a receiver MUST discard any CASH whose epoch differs from that exchange's epoch, including its S indication. It MUST NOT compare the hashes, initiate repair, or update inventory or completion state from that CASH.

The restarter MUST ignore restart acknowledgement signaling in an RA carrying a different epoch, without falling back to ordinary restart processing of that signaling. Other IIH contents are processed normally.

A wrong-epoch helper response MUST NOT change the restarter's current exchange, reset its restart timers, or revoke previously accepted synchronization. The restarter continues waiting for valid responses under the existing restart timers. Timer expiry and unsuccessful restart follow [RFC8706].

When a helper accepts RR from the restarting router with an epoch different from the exchange it is currently assisting, it MUST replace that exchange with the new one and invalidate the previous exchange's pending completion indications.

5.6.4. Initial Handshake and Synchronization Completion

For T1 processing, receipt of either a complete CASH train or a complete CSNP set satisfies the initial database-summary receipt requirement for that level. The restarting router MUST receive both RA and either a complete CASH train or a complete CSNP set from the helper for every active level before considering the initial handshake complete. A complete CASH train satisfies this receipt requirement even if its hashes mismatch. Receipt does not require retaining a separate inventory or snapshot at the restarting router and does not by itself establish database synchronization. A range CSNP used for terminal repair does not satisfy this requirement, regardless of the size of the range being repaired. It cannot be a C-CSNP because it excludes the complete-set end marker as specified in Section 5.4.1, Paragraph 7.

The initial database-summary receipt and synchronization requirements MUST apply to every participating ASH adjacency and active level, independently of whether a CASH has arrived from that helper. Silence or a lost train MUST NOT remove a helper's requirement. A detected mismatch MUST prevent agreement for that train even when its repair is deferred.

The restarting router MUST receive either a complete matching CASH train from the helper or the helper's S indication for the current restart epoch at each active level before considering that adjacency synchronized. The S indication MUST NOT bypass the initial database-summary receipt or the RA handshake requirement. If a helper falls back to a complete CSNP set, synchronization with that helper follows the ordinary procedures of [RFC8706]; receipt of the set alone does not establish synchronization. The restarting router MUST satisfy this reconciliation condition on all required ASH graceful-restart adjacencies and active levels, together with the synchronization conditions of any participating ordinary graceful-restart adjacencies, before declaring restart synchronization complete. The T2 and T3 limits and unsuccessful-restart procedures of [RFC8706] continue to apply. Repeated RR hellos or additional CASH trains MUST NOT extend the restart holding period.

6. CASH PDU Format

The CASH 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.

                                       No. of Octets
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Intradomain Routing Protocol        |     1
| Discriminator                       |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Length Indicator                    |     1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Version/Protocol ID Extension (1)   |     1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ID Length                           |     1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| R R R   PDU Type                    |     1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Version (1)                         |     1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| GR Control                          |     1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Max Area Addresses                  |     1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| PDU Length                          |     2
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Source ID                           |  ID Length + 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Start System ID                     |  ID Length
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| End System ID                       |  ID Length
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Node Range Hash TLVs                |  Variable
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

The Start and End System IDs use the standard ID length and indicate the range of fragments covered by the ASH, just like CSNPs do. The key difference is that all pseudonodes of the systems within this range are implicitly included (implying as well that all fragments of the range are included). Both the Start and End System IDs are inclusive, meaning fragments from both endpoints are part of the range. All Node Range Hash Entries MUST fall within the bounds defined by the header's Start and End System IDs.

Unlike CSNPs, which place LSP Entries directly in a dedicated LSP Entries TLV (type 9) whose value is itself just a flat sequence of entries, ASH packets carry their Node Range Hash Entries inside a new Node Range Hash TLV (type TBD), following the standard IS-IS TLV convention of a 1-octet Type, 1-octet Length, and Value:

                                       No. of Octets
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type = Node Range Hash TLV (TBD)    |     1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Length                              |     1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Node Range Hash Entries             |  Variable
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

The Value of a Node Range Hash TLV is a sorted sequence of Node Range Hash Entries in the following format.

A CASH MAY contain no Node Range Hash TLVs. In that case, its entire header range describes absent inventory, and the receiver processes that absence as specified below. An empty database is described by one such CASH with an all-zero Start System ID and an all-ones End System ID. Other required TLVs, including authentication, remain present. No zero-hash entry is needed: a zero hash is a terminal repair directive, not an empty-database fingerprint.

                                       No. of Octets
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Range Start System ID               |  ID Length
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Range End System ID                 |  ID Length
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Merkle Hash                         |     8
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Fragment Population                 |     1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

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

The Merkle hash field is 8 octets containing the 64-bit computed hash of all fragments covered by the range. A computed value MUST NOT be zero. In both CASH and PASH entries, zero is the terminal repair directive specified in Section 5.4, including the role-directed broadcast behavior in Section 5.5. The all-ones value is reserved and MUST NOT be transmitted.

The Fragment Population field encodes the number N of LSP fragments in the inclusive range in the sender's local database. A sender MUST encode an empty range as zero. For a nonempty range, it MUST low-ball N by encoding the highest possible represented value not exceeding N. To read a nonzero wire code C, subtract one and split the result into the four exponent bits E and four fraction bits F shown below. The represented value is 2^E * 2^(F/16); the receiver MUST decode it as floor(2^E * 2^(F/16)). Codes 1, 17, 97, and 129 represent 1, 2, 64, and 256 fragments. Code 0xff is the last available step and decodes to 60096; it also represents larger populations. This field is advisory and, except for the inconsistent zero-population/nonzero-hash handling in Section 5.4.1, does not alter hash comparison or the meaning of a zero hash. It MUST describe the sender's local population even when the Merkle Hash field is zero.

For nonzero wire code C, let L = C - 1:

       7   6   5   4   3   2   1   0
     +---------------+---------------+
 L = | Integer part E| Fraction F    |
     +---------------+---------------+

       represented value   = 2^E * 2^(F/16)
       population estimate = floor(2^E * 2^(F/16))

Wire code 0 means empty; the split above applies to C - 1,
not directly to C.

With the standard ID Length of 6, each entry is 6 + 6 + 8 + 1 = 21 octets. Since a TLV's Length field is a single octet, a single Node Range Hash TLV can carry at most 12 entries (12 * 21 = 252 octets, leaving room within the 255-octet maximum TLV value size). Since Node Range Hash Entries are treated as a single logical sequence regardless of which TLV they appear in, a CASH or PASH PDU MAY, and typically will, carry multiple Node Range Hash TLVs to fit the roughly 70 entries that fit into a standard 1500-byte MTU, exactly as CSNPs carry multiple LSP Entries TLVs when needed.

The ranges in a CASH MUST be sorted by Range Start System ID across the concatenation of all Node Range Hash TLVs in the PDU, in the order the TLVs appear. The ranges MUST NOT overlap. A receiver encountering overlapping ranges MUST treat the union of those ranges as a single range with a zero hash. Its Fragment Population MUST be obtained by adding the decoded populations of the contributing entries, without subtracting for overlap, and encoding the sum using the Fragment Population encoding above, including saturation at the largest code. Any range exceeding the CASH header bounds MUST be clamped to fit within the CASH range and treated as a zero hash. Clamping MUST NOT change its Fragment Population. A range whose end equals its start is valid and covers the fragments of that single system ID. Any range whose end is smaller than its start MUST be discarded. A node SHOULD log such events since they most likely indicate protocol implementation problems or attacks.

Any node IDs that are not covered by the ranges in a CASH - either because there are gaps between the advertised ranges, or between those ranges and the ASH's Start and End System IDs - MUST be treated as missing. Consequently, if a node detects that it holds Merkle hashes for LSPs that are not covered by a received CASH, it MUST behave as it would in the same situation with a CSNP, namely by flooding the missing LSPs.

A gap within the CASH header bounds is therefore semantically equivalent to an implicit entry covering that gap with hash zero and Fragment Population zero. An explicit zero-hash entry requests the same terminal repair but can advertise a nonzero population; the directive alone does not assert empty inventory. Neither form provides hash agreement. Ranges outside the CASH header bounds are not described by that PDU.

As with CSNPs, a CASH whose first range covers the first node in the database MUST use 0000.0000.0000 as the start system ID in its packet header so that missing nodes can be detected. The same rule applies at the other end: a CASH whose range covers the last node MUST indicate this so that any missing trailing nodes are detectable.

As with PASHes (Section 7), deployments combining ASH with [RFC9681] fast flooding SHOULD reserve sufficient space within the PDU for a Flooding Parameters TLV, along with any other TLVs that may need to coexist in the same PDU, when computing how many Node Range Hash TLVs and entries fit within the MTU, as described in Section 9.2 and Section 9.3.

7. PASH PDU Format

PASH uses the CASH format in Section 6, with the PASH PDU Type for the applicable level and without the Start and End System ID header fields. The octet corresponding to CASH's GR Control remains reserved: it MUST be transmitted as zero and ignored on receipt.

Node Range Hash TLV and entry encoding, Fragment Population, and reserved hash values are the same as for CASH. Additional TLVs and PDU space reservation follow Section 8.

PASHes are equivalent to PSNPs in that entries are treated independently: gaps between entries have no semantics, entries need not be sorted, and may overlap. Unlike CASH gaps, PASH gaps do not imply zero-hash, zero-population entries. A range whose end equals its start is valid and covers the fragments of that single system ID. Any range whose end is smaller than its start MUST be discarded before its hash is interpreted, including when the hash is zero. A node SHOULD log such events since they most likely indicate protocol implementation problems or attacks.

8. Additional TLVs in CASH and PASH PDUs

A CASH replaces a CSNP and a PASH replaces a PSNP; neither may be less capable than the PDU it replaces. Except for the LSP Entries TLV (type 9), whose inventory representation is replaced by Node Range Hash TLVs, every TLV type that an implementation supports in CSNPs MUST equally be supported in CASHes, and every TLV type it supports in PSNPs MUST equally be supported in PASHes, with the same semantics, the same configuration and the same receive processing. This includes, but is not limited to, the Authentication TLV ([RFC5304], [RFC5310]), the Checksum TLV, the Instance Identifier TLV, and the Flooding Parameters TLV of [RFC9681]. Deployments therefore do not have to give up any of these features, and in particular do not have to disable SNP authentication, in order to use ASH. Senders MUST NOT include an LSP Entries TLV in CASH or PASH; receivers MUST ignore such a TLV if present.

Such TLVs MAY appear anywhere in the PDU, before, between or after the Node Range Hash TLVs, exactly as they may in CSNPs/PSNPs. A receiver MUST ignore their position when collecting Node Range Hash Entries.

Where a TLV is computed over the PDU, it is computed over the complete CASH or PASH PDU, in the same order and with the same field treatment as for CSNPs/PSNPs. In particular the authentication digest of [RFC5304] and [RFC5310] covers the whole PDU including all Node Range Hash TLVs, and is computed with the PDU Length field already carrying the final length. The authentication configuration (keys, key chains, algorithms and any per PDU type exemptions) that applies to CSNPs MUST apply to CASHes, and the one that applies to PSNPs MUST apply to PASHes.

A receiver MUST perform the same validation of these TLVs that it performs for a CSNP (for a CASH) or a PSNP (for a PASH), and MUST do so before any Node Range Hash Entry is compared or triggers any PASH, PSNP or flooding. A PDU failing that validation MUST be discarded exactly as a CSNP/PSNP failing it would be.

The space these TLVs need MUST be reserved when computing how many Node Range Hash TLVs and entries fit within the MTU (Section 9.2, Section 9.3), so that adding them never requires dropping or re-splitting entries. If the space needed on a circuit exceeds what the implementation has reserved, it MUST NOT send CASHes or PASHes without those TLVs on that circuit; it MUST instead fall back to CSNPs/PSNPs there until sufficient space is reserved.

9. Further Considerations

9.1. Graceful Restart Epoch Reuse

The four-bit ASH graceful-restart epoch distinguishes exchanges with different epoch values, but its sixteen values can be reused. A sufficiently delayed packet from an earlier exchange with the same epoch can then be indistinguishable from current signaling, even after the neighbor, adjacency, level, and authentication checks succeed. In particular, an old Snapshot Served indication could be accepted for the current exchange. Authentication alone does not establish freshness.

The epoch-selection and state-invalidation rules in Section 5.6 reduce this exposure but do not eliminate it. This is a residual risk accepted by this design for viable ASH graceful-restart operation, not a guarantee against arbitrarily delayed or replayed signaling.

Traditional graceful restart in [RFC8706] does not carry an explicit per-restart epoch in its Restart TLV or CSNP exchange. Its adjacency, timer, and database-synchronization procedures provide other checks, but do not supply an equivalent exchange identifier for rejecting old signaling solely because it belongs to an earlier restart. ASH adds that discrimination for different epochs; finite epoch reuse remains a limitation. This comparison does not imply identical completion procedures or failure consequences in the two protocols.

9.2. IS-IS Scale Envelope

ASHs 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 CSNPs under such assumptions represent 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. ASHs 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 - barring pathological scenarios - through dampening and parallelization, so we focus on realistic scenarios on the order of 50,000 nodes and 1 million fragments. We assume an outer envelope of 16K peers, which provides some margin over the largest deployments realized today.

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

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

With maximum ASH 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 above makes it clear that combining fast flooding, flood reduction, and ASH will be essential for extending IS-IS scalability as deployments continue to grow.

9.3. Maximum Advisable Hash Coverage

Although the mechanism can theoretically use a single Merkle hash to represent an arbitrarily large database, such an approach is not advisable. Instead, it is far preferable to limit hash coverage so that at minimum one full ASH packet is required.

In practice, limiting compression so that a maximum of about a dozen ASH packets covers the entire database is usually sufficient. For example, a single maximally compressed ASH packet for a 10,000 - fragment database covers ~140 fragments per hash. Allowing for more ASH packets (e.g., 10 instead of 100 CSNPs) still provides a 10x compression factor, reduces disaggregation needs during LSDB changes, and further lowers the already negligible collision risk (which in 10K sized LSDB is however vanishingly small with a single hash already).

9.4. Hash Collision Probabilities

Even with CSNPs or PSNPs, IS-IS has a corner case where LSDB synchronization can fail - particularly during node restarts. In simple terms, if a new fragment has the same sequence number and different content but an identical 16-bit Fletcher checksum, the collision goes undetected until the fragment expires.

Assuming Fletcher checksums are uniformly distributed (even with minor content changes), the collision probability for that case is 1/2**16 ~ 0.0015%. This baseline enables meaningful comparisons with ASH hash collision probabilities.

ASH uses 64-bit [SIPHASH] over what is essentially PSNP data for a fragment plus its IS-IS PDU length. One concern is the probability that two fragments covered by the same hash produce identical hashes simultaneously. This would cause both fragments to "cancel out" due to the XOR nature. Collisions between fragments in different node range hashes are irrelevant.

Distinct sets of fragment hashes can also produce the same XOR even when no individual fragment hashes collide. Hash agreement therefore remains probabilistic, including for singleton ranges containing multiple fragments. The simulations below examine individual fragment-hash collisions, not all possible aggregate collisions.

Collision probability analysis is complex for the general case, though the birthday paradox gives a rough estimate of 0.18% collision likelihood for 48-bit hashes in a 1M-sized set. For 64-bit hashes this reduces to ~0.000,002,7%. Rather than relying solely on statistical assumptions, we use extensive simulations that mirror real-world conditions.

These simulations model 50,000-node networks with 1M fragments, assuming node IDs differ by only 3 bytes, maximum fragment lifetimes, random protocol checksums on fragment refresh, and packet length changes in just 5% of refreshes to reflect network stability. Results are derived from 32 networks running for 2 years each.

Across 64 years of simulated time and the resulting 36E9 fragment refreshes, we observed 142 collisions for the 48-bit variant of [SIPHASH] across the whole set, or roughly ~0.000,000,4% - much lower than the birthday paradox prediction. However, assuming a single maximum-size ASH packet covering the entire database, only 3 of those collisions matter - a probability of ~0.000,000,008%, or roughly 1 occurrence per 20 years. These collisions have an average lifetime of about 10 hours. The rates are orders of magnitude lower than birthday paradox predictions, likely because node IDs act as a consistent "salt" that effectively pre-partitions the probability space. This is arguably "good enough" by a wide margin.

Nevertheless, further investigation using the standard 64-bit SipHash 1-3 variant over the same scenario produces *no* detectable collisions. Measuring the CPU cost of the 48-bit variant vs. the 64-bit variant (or even 64-bit traditional Fletcher checksum) shows negligible differences of low single-digit percent with modern implementation techniques. Thus, 64-bit [SIPHASH] 1-3 has been chosen and should provide a very safe margin even for much larger databases.

Ultimately, a highly conservative (not to say paranoid) implementation can simply monitor the LSDB for colliding fragment hashes and exclude them from the same ASH hash. This forces receiving nodes to compare separate range hashes instead, where System ID boundaries permit. Such an approach reduces the risk of synchronization misses to the highest extent possible with this partitioning. It does not eliminate collisions: distinct sets of fragment hashes can have the same XOR, and fragments belonging to one System ID cannot be separated into different ASH ranges.

Other techniques are possible, such as slowly walking the database and sending CSNPs. However, for a 1M-fragment database that generates 10,000 such CSNP packets, the chance of this detecting a collision during its 10-hour window is rather unlikely.

9.5. Impact of Packet Losses

Hashes covering large numbers of fragments are more vulnerable to packet losses, as each lost packet affects a much larger portion of the LSDB during synchronization. Implementations can choose ASH node ranges freely, but should balance maximum compression against "good enough" compression that reduces both collision risk and vulnerability to possible packet drops.

9.6. Decompression and Caching/Comparison Optimizations

As mentioned earlier, nodes can use various strategies to accelerate decompression. For example, LSPs missing from CASHes (those not covered by any ranges) are clearly absent and can be immediately reflooded. Similarly, small mismatched ranges can trigger immediate CSNPs, PSNPs, or direct flooding.

Caching of hashes can be applied at many levels. The simplest and most useful approach is maintaining a raw XOR aggregate for all fragments of a node and its pseudonodes, though other granularities work equally well. Even when adjusting for changes - such as receiving a range < A - B > while having cached < A - B & next-after-B > - the cached hash can be quickly updated by simply XOR'ing out the next-after-B node's raw aggregate. Range-level reserved-value replacement is applied only to the final comparison or advertisement value, as specified in Section 4.2, not to the cached aggregates used for this calculation.

Implementations that adapt ASH compression from observed comparison results should distinguish positive evidence from negative evidence. A matching range hash is strong evidence that every node covered by that range matched and can therefore justify maintaining or increasing compression for those nodes. In contrast, a mismatching coarse range proves only that at least one covered node differs; it does not identify which node or nodes caused the mismatch. Implementations should therefore avoid assigning that negative result to every node in the range. Instead, they should use progressively finer PASH comparisons, and ultimately SNP comparison or flooding, to obtain sufficiently specific evidence before reducing compression for individual nodes. Otherwise, a small localized change can incorrectly drive an entire coarse range toward little or no compression.

10. Security Considerations

ASH security relies on the same mechanisms protecting IS-IS PDU integrity. As required in Section 8, CASHes and PASHes are authenticated with the same mechanisms ([RFC5304], [RFC5310]) and configuration as the CSNPs and PSNPs they replace, so enabling ASH neither weakens nor removes SNP authentication.

A received hash drives more work than a received CSNP entry: a mismatch triggers further PASHes, PSNPs and flooding. Validating authentication before any of this happens is therefore required, so that an unauthenticated PDU cannot trigger that work.

11. IANA Considerations

IANA is requested to allocate Type TBD-ASH-GR from the "IS-IS TLV Codepoints" registry for the ASH GR Suggested Epoch TLV, permitted in point-to-point IIHs as defined in Section 5.6.2.

IANA is requested to allocate two bits from the "IS-IS Bit Values for Hello Capability TLV Flags" registry defined in [ID.draft-ginsberg-lsr-hello-capability-00], named "ASH_RX" and "ASH_TX", indicating respectively that the advertising node is willing to receive and process, and/or may originate, ASH (CASH/PASH) packets on that adjacency in place of CSNPs/PSNPs.

IANA is requested to allocate a codepoint (type TBD) from the "IS-IS TLV Codepoints" registry for the Node Range Hash TLV, valid within CASH and PASH PDUs as defined in Section 6 and Section 7.

IANA is requested to allocate four new codepoints from the "PDU Types" registry under "Intermediate System to Intermediate System (IS-IS) Parameters", one for each combination of CASH or PASH and Level 1 or Level 2, analogous to the existing Level 1 and Level 2 Complete/Partial SNP codepoints, as follows:

Table 1
Value Description
TBD1 Level 1 CASH
TBD2 Level 2 CASH
TBD3 Level 1 PASH
TBD4 Level 2 PASH

As with existing SNP PDU types, separate Level 1 and Level 2 codepoints are requested for both CASH and PASH so that the PDU Type field alone identifies both the packet's function and the level it applies to.

12. Contributors

TBD

13. Acknowledgement

People have been talking about "compressing CSNPs" for a very long time, reportedly going back to when Radia Perlman and an insomniac Dave Katz were walking the halls discussing it. Recent attempts to scale the protocol much further have made it worthwhile to turn this idea into a standardized, practical engineering solution.

Les Ginsberg identified several unresolved issues and contributed alternative ideas to the draft.

Job Snijders initiated the discussion of [SIPHASH] as a likely better solution than traditional Fletcher checksumming of fragments.

Claude (Anthropic) [CLAUDE] and GPT (OpenAI) [GPT] assisted in reviewing the draft specification, identifying ambiguities in zero-hash semantics, overlap handling, PDU header-to-entry range relationships, and many intricacies of ASH GR.

14. References

14.1. Normative References

[ID.draft-ginsberg-lsr-hello-capability-00]
Ginsberg et al., L., "IS-IS Hello Capability", , <https://www.ietf.org/id/draft-ginsberg-lsr-hello-capability-00.txt>.
[RFC2119]
Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, , <https://www.rfc-editor.org/rfc/rfc2119>.
[RFC5304]
Li, T. and R. Atkinson, "IS-IS Cryptographic Authentication", RFC 5304, DOI 10.17487/RFC5304, , <https://www.rfc-editor.org/rfc/rfc5304>.
[RFC5310]
Bhatia, M., Manral, V., Li, T., Atkinson, R., White, R., and M. Fanto, "IS-IS Generic Cryptographic Authentication", RFC 5310, DOI 10.17487/RFC5310, , <https://www.rfc-editor.org/rfc/rfc5310>.
[RFC8174]
Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, , <https://www.rfc-editor.org/rfc/rfc8174>.
[RFC8706]
Ginsberg et al., L., "Restart Signaling for IS-IS", RFC 8706, DOI 10.17487/RFC8706, , <https://www.rfc-editor.org/rfc/rfc8706>.
[SIPHASH]
Aumasson, J.-P. and D. J. Bernstein, "SipHash: A Fast Short-Input PRF", Lecture Notes in Computer Science Vol. 7668, INDOCRYPT 2012, pp. 489-508, , <https://131002.net/siphash/>.

14.2. Informative References

[CLAUDE]
Anthropic, "Claude: AI Assistant", , <https://www.anthropic.com/claude>.
[GPT]
OpenAI, "GPT-4 Technical Report", arXiv 2303.08774, DOI 10.48550/arXiv.2303.08774, , <https://arxiv.org/abs/2303.08774>.
[HASHES]
Phan, C.-W., "Security considerations for incremental hash functions based on pair block chaining", .
[ID.draft-ietf-lsr-distoptflood-11]
White et al., R., "IS-IS Distributed Flooding Reduction", , <https://www.ietf.org/id/draft-ietf-lsr-distoptflood-11.txt>.
[MERKLE]
Merkle, R.C., "A Digital Signature Based on a Conventional Encryption Function", .
[RFC9681]
Decraene et al., B., "IS-IS Fast Flooding", RFC 9681, DOI 10.17487/RFC9681, , <https://www.rfc-editor.org/rfc/rfc9681>.
[SKIP]
Pugh, W., "Skip lists: A probabilistic alternative to balanced trees", .

Appendix A. Reference Implementation of SIP Fragment Hashing 

<CODE BEGINS>
pub fn fragment_hash(
    fragmentid: &SharedFragmentID,
    fragmentcontent: &FragmentContent,
) -> ASHHash {
    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())),
            ),
        ),
    );

    let key = [
        1, 2, 3, 4, 5, 6, 7, 8,
        9, 10, 11, 12, 13, 14, 15, 16u8,
    ];
    let mut hasher = SipHasher13::new_with_key(&key);
    let mut sl = [0u8; 16];
    rotate_in_primary
        .copied()
        .collect_slice_checked(&mut sl[..]);
    hasher.write(&sl);
    let hash = ASHHash(hasher.finish());

    if hash == EMPTY_ASHHASH || hash == ASHHash(u64::MAX) {
        ASHHash(1)
    } else {
        hash
    }
}

<CODE ENDS>

Authors' Addresses

Tony Przygienda
HPE Juniper Networking
Tony Li
HPE Juniper Networking
Joel Halpern
HPE Juniper Networking