search

justincpresley / ndn-sync

ndn-sync: A Go Library for NDN Distributed Dataset Synchronization "Sync" Protocols.
https://pkg.go.dev/github.com/justincpresley/ndn-sync
ISC License
3 stars 1 forks source link

StateVector entry ordering #1

Closed yoursunny closed 7 months ago

yoursunny commented 1 year ago

I'm reading the source code of StateVector type, and noticed two related issues.

specification branch

SVS spec revision 2021-12-15 states:

Node names in the encoded version vector are ordered in NDN canonical order to allow for Interest aggregation.

The entries are stored in a entries map[string]uint64 where each key is the semi-canonical URI representation of the node name. The encoding function is for range loop over this map, without specific ordering.

Go language spec states:

The iteration order over maps is not specified and is not guaranteed to be the same from one iteration to the next.

Hence, looping over the map would emit the entries in unspecified order. It does not generate the name order as expected in SVS spec.

production branch

Documentation states a difference is:

StateVectors are ordered by Latest Entries.

In OrderedMap type, the latest entry of a StateVector is at the front, not at the back. Hence, the actual order is better described as "reverse latest entries" or "latest entry first" or "descending order of last update time".

I have concerns on how this changed ordering impacts the effectiveness of in-network Interest aggregation. This should be explained in the library documentation.

justincpresley commented 1 year ago

Thank you for your observations.

Your points will be addressed in the following way. Please let me know if I misunderstood any concern or did not fully address a concern.

[summary] Specification StateVectors do not follow NDN canonical order (required by the technical specification) due to Go maps not guaranteeing order.

  • I have made note of this and will keep this issue open until this is fixed.

[summary] The phrase "sorted by Latest Entries" is vague as it does not indicated descending/ascending behavior. This can be misunderstood to be ascending in update time.

I have concerns on how this changed ordering impacts the effectiveness of in-network Interest aggregation.

  • I also shared those concerns. While Scalability will be tackled with the changed ordering, I do have plans to re-introduce in-network Interest aggregation.