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 -- [email protected]
To unsubscribe send an email to [email protected]
