[Lsr] Re: draft-prz-lsr-hierarchical-snps - Partitioning

[Tony Przygienda <[e-mail]>]

Bruno, sorry it took so long ;-) I was taking a couple days off and
additionally running lots of simulations etc so it is kind of evolving my
thinking with the experience coming in ;-)

I came off the concept of any "level hierarchy" of hashes completely by now
having implemented a good amount of stuff and playing with it. It looks
much more that keeping a simple stats about 'what changed recently' and
'what did this node disagreed on recently' allows for dynamic change of
"hashing depth" (which is better than rigid levels) that will lead to lower
amount of ping-ponging.

So yes, what you suggest would be one approach but it looks like the draft
will go into the direction of "fluid ranges" in next version rather than
trying to somehow synchronize partition schemes.

I'm updating the draft as we speak so expect something maybe next week.

-- tony



On Fri, Nov 21, 2025 at 2:32 PM <[e-mail]> wrote:

> Hi Tony, Tony,
>
>
>
> As a follow up of your presentation @ IETF 124 [1], you mentioned that the
> hard part is the partitioning.
>
>
>
> Although there are tradeoffs, I was wondering whether we could use a
> configured (or hardcoded for simplicity) partitioning schema which would
> therefore be consistent on all nodes in the flooding zone.
>
>
>
> For example, assuming:
>
>    - System ID size: 7 octets
>    - 1500 bytes PDU size
>
> -  Hash: 4 octets  à 256 hashes consume 1024 octets hence fits in one PDU
>
>
>
>
>
> We could use a 7 levels HSNP hierarchy.
>
>    - Level 6 covers 256 /8 systems ID : 00/8 up to FF/8 with a single
>    HSNP.
>       - 256 hashes, each one covering systems ID XX/8
>    - Level 5 covers 256^2 /16 systems ID  : 0000/16 up to FFFF/8 with 256
>    HSNPs (from 0000/16 to 00FF/16)
>       - HSNP XX covers XX/8. One of its hash ( YY) covers  XXYY/16
>    - Level 4 covers 256^3 /24 systems ID : 000000/16 up to FFFFFF/16 with
>    65536 HSNPs (from 000000/16 to 0000FF/16)
>    - …
>
>
>
> With an example:
>
> Top level (level 6) HSNP advertises full range of System ID
>
>    - Start System ID: 0000.0000.0000.00
>    - End System ID:   FFFF.FFFF.FFFF.FF
>    - HSNP Level: 6
>    - 256 hashes, covering all 255 level 5
>       - 0000.0000.0000.00 – 00FF.FFFF.FFFF.FF
>       - 0100.0000.0000– 01FF.FFFF.FFFF.FF
>       - …
>       - FF00.0000.0000– FFFF.FFFF.FFFF.FF
>
>
>
> Each level 5 HSNP advertises a 1/256th of the full range of System ID.
>
> E.g. for the first one (00)
>
>    - Start System ID: 0000.0000.0000.00
>    - End System ID:   00FF.FFFF.FFFF.FF
>    - HSNP Level: 5
>    - 256 hashes, covering all 255 HSNP level 4
>       - 0000.0000.0000.00 – 0000.FFFF.FFFF.FF
>       - 0001.0000.0000– 0001.FFFF.FFFF.FF
>       - …
>       - 00FF.0000.0000– 00FF.FFFF.FFFF.FF
>
>
>
>
>
> Obviously, the number of HSNPs required seems huge/intractable.
>
> However, the point is that they are mostly never sent as:
>
>    - The level 6 HSNP typically mostly contains null hashes (unless
>    Systems ID are randomly picked). Each null hash indicates the absence of
>    system ID in its /8 range. Hence all the lower levels HSNP do not need to
>    be sent nor computed.
>    - A level N-1 HSNP only needs to be send if there is an inconsistent
>    hash with the neighbor.
>       - In the best case, LSDB are in sync and hence level 5 to level 0
>       do not need to be sent.
>       - In general, LSDB are mostly in sync and only a few fragments are
>       missing. Hence only the few HSNP in levels 5, 4, 3, 2, 1 needs to be sent
>       using “Recursive “ping pong””
>       - At worst, the LSDB (or one of its partitions, at any level) is
>       completely out of sync. In this case, forget about HSNP/CSNP and flood all
>       fragments of this partition since fragments needs to be flooded anyway.
>       Possibly a field in the HSNP could be added to indicate the number of
>       fragments in this range, to better evaluate the tradeoff.
>
>
>
> Regards,
>
> --Bruno
>
> For the references (as non-trivial)
>
> [1]
> https://datatracker.ietf.org/meeting/124/materials/slides-124-lsr-hsnp-updated-a-bit-00
>
> [2] https://datatracker.ietf.org/doc/draft-prz-lsr-hierarchical-snps/
>
> ____________________________________________________________________________________________________________
> Ce message et ses pieces jointes peuvent contenir des informations confidentielles ou privilegiees et ne doivent donc
> pas etre diffuses, exploites ou copies sans autorisation. Si vous avez recu ce message par erreur, veuillez le signaler
> a l'expediteur et le detruire ainsi que les pieces jointes. Les messages electroniques etant susceptibles d'alteration,
> Orange decline toute responsabilite si ce message a ete altere, deforme ou falsifie. Merci.
>
> This message and its attachments may contain confidential or privileged information that may be protected by law;
> they should not be distributed, used or copied without authorisation.
> If you have received this email in error, please notify the sender and delete this message and its attachments.
> As emails may be altered, Orange is not liable for messages that have been modified, changed or falsified.
> Thank you.
>
> _______________________________________________
> Lsr mailing list -- [e-mail]
> To unsubscribe send an email to [e-mail]
>