search

OpenCyphal / pycyphal

Python implementation of the Cyphal protocol stack.
https://pycyphal.readthedocs.io/
MIT License
123 stars 106 forks source link

Synchronous multi-subject subscriber #65

Closed pavel-kirienko closed 2 years ago

pavel-kirienko commented 5 years ago

Context: https://forum.uavcan.org/t/si-namespace-design/207/5?u=pavel.kirienko This feature will be needed for https://github.com/UAVCAN/pyuavcan/issues/56 (specifically for the subscriber tool)

pavel-kirienko commented 5 years ago

State-of-the-art: http://wiki.ros.org/message_filters/ApproximateTime

pavel-kirienko commented 5 years ago

I think that this component should be implemented directly at the Presentation layer (under pyuavcan.presentation) as a new class whose API should be in the spirit of pyuavcan.presentation.Subscriber. The new class need not be integrated with the Presentation layer controller (the latter does not need to be involved with it at all). I propose to let the user construct multi-subject subscribers manually, by building separate subscribers first and then feeding them together into the multi-subject sub as necessary.

pavel-kirienko commented 2 years ago

On an embedded system, an O(log n) synchronizer with an arbitrary tolerance can be easily constructed based on a search tree like https://github.com/pavel-kirienko/cavl. Tree nodes are to be ordered by the reception timestamp (from the message field timestamp, if available for all subjects, otherwise from the transport layer) rounded according to the tolerance setting. Each tree node is to contain a set of messages received with its timestamp (rounded). Once a specific set is full, it is forwarded to the application for processing, and then this and all older tree nodes are discarded.

If the maximum synchronization latency expressed as the message count n is limited (which also limits the size of the tree), then the worst-case memory consumption is bounded as (n * number of synchronized messages).

A near-optimal tolerance can be established automatically as ~half of the message arrival period.