commit 0a5f335a2201319a6e2b6a27e17a6fa8a22dce33
parent c8fbe56b5cb606a1b7be2e401cb9c4b0fb5c8d1b
Author: Elias Summermatter <elias.summermatter@seccom.ch>
Date: Mon, 21 Dec 2020 11:40:01 +0100
Added some graphics
Diffstat:
1 file changed, 121 insertions(+), 8 deletions(-)
diff --git a/draft-summermatter-set-union.xml b/draft-summermatter-set-union.xml
@@ -143,16 +143,21 @@
<section anchor="ibf_format" numbered="true" toc="default">
<name>Format</name>
<t>
- The storage format of an IBF is a "two-component data structure" that stores a value
+ The storage format of an IBF is a "two-component data structure" that stores a hash value
and a signed counter in a bucket. For every bit of the defined output length of the used hash functions
there is a value and a count stored.
- The count component is increased by one if on the given bit has been hit by the #### ANSCHAUEN REDUNDANT
- insert operation and is decreased by one if an bit has been hit by the delete operation. #### ILUSTRATONEN
- If the bucket is pure (|counter| = 1) the value contains the hash value of an element otherwise in the
- value field is empty (counter= 0) or a XOR product of all previously written hashes of elements
- (|counter| > 1)
- ### SOME GRAPHIC OF THE FORMAT ###
</t>
+ <figure anchor="figure_ibf_format">
+ <artwork name="" type="" align="left" alt=""><![CDATA[
+ bit-1 bit-2 bit-3 bit-4
+ +-------------+-------------+-------------+-------------+-------
+ count | COUNTER | COUNTER | COUNTER | COUNTER | C...
+ +-------------+-------------+-------------+-------------+------
+ value | HASH VALUE | HASH VALUE | HASH VALUE | HASH VALUE | H...
+ +-------------+-------------+-------------+-------------+-------
+ ]]></artwork>
+ </figure>
+
</section>
<section anchor="ibv_operations" numbered="true" toc="default">
<name>Operations</name>
@@ -164,6 +169,43 @@
bit positions with a one of the hash output the counter is increased by one and the value
field is updated with the XOR product of the new hash and the previously stored value.
</t>
+ <t>
+ In the following example the insert operation for the element [0101] with the hash 4242 and
+ the element [1100] with the hash 0101 is demonstrated.
+ </t>
+ <t>Empty IBF:</t>
+ <figure anchor="figure_ibf_insert_0">
+ <artwork name="" type="" align="left" alt=""><![CDATA[
+ bit-1 bit-2 bit-3 bit-4
+ +-------------+-------------+-------------+-------------+
+ count | 0 | 0 | 0 | 0 |
+ +-------------+-------------+-------------+-------------+
+ value | 0000 | 0000 | 0000 | 0000 |
+ +-------------+-------------+-------------+-------------+
+ ]]></artwork>
+ </figure>
+ <t>Insert first element: [0101] with hash 4242:</t>
+ <figure anchor="figure_ibf_insert_1">
+ <artwork name="" type="" align="left" alt=""><![CDATA[
+ bit-1 bit-2 bit-3 bit-4
+ +-------------+-------------+-------------+-------------+
+ count | 0 | 1 | 0 | 1 |
+ +-------------+-------------+-------------+-------------+
+ value | 0000 | 4242 | 0000 | 4242 |
+ +-------------+-------------+-------------+-------------+
+ ]]></artwork>
+ </figure>
+ <t>Insert second element: [1100] with hash 0101:</t>
+ <figure anchor="figure_ibf_insert_2">
+ <artwork name="" type="" align="left" alt=""><![CDATA[
+ bit-1 bit-2 bit-3 bit-4
+ +-------------+-------------+-------------+-------------+
+ count | 1 | 2 | 0 | 1 |
+ +-------------+-------------+-------------+-------------+
+ value | 0101 | 4343 | 0000 | 4242 |
+ +-------------+-------------+-------------+-------------+
+ ]]></artwork>
+ </figure>
</section>
<section anchor="ibv_operations_remove" numbered="true" toc="default">
<name>Remove Element</name>
@@ -173,6 +215,31 @@
two-component data structure is reduced by one and the resulting hash is XORed with the value field
and is written to the value field again.
</t>
+ <t>
+ In the following example the insert operation for the element [1100] with the hash 0101 is demonstrated.
+ </t>
+ <t>IBF with encoded elements:</t>
+ <figure anchor="figure_ibf_remove_0">
+ <artwork name="" type="" align="left" alt=""><![CDATA[
+ bit-1 bit-2 bit-3 bit-4
+ +-------------+-------------+-------------+-------------+
+ count | 1 | 2 | 0 | 1 |
+ +-------------+-------------+-------------+-------------+
+ value | 0101 | 4343 | 0000 | 4242 |
+ +-------------+-------------+-------------+-------------+
+ ]]></artwork>
+ </figure>
+ <t>Remove element [1100] with hash 0101 from the IBF:</t>
+ <figure anchor="figure_ibf_remove_1">
+ <artwork name="" type="" align="left" alt=""><![CDATA[
+ bit-1 bit-2 bit-3 bit-4
+ +-------------+-------------+-------------+-------------+
+ count | 0 | 1 | 0 | 1 |
+ +-------------+-------------+-------------+-------------+
+ value | 0000 | 4242 | 0000 | 4242 |
+ +-------------+-------------+-------------+-------------+
+ ]]></artwork>
+ </figure>
</section>
<section anchor="ibv_operations_decode" numbered="true" toc="default">
<name>Decode IBF</name>
@@ -184,6 +251,52 @@
in the section "Remove Element" from the pure buckets from the filter creating new pure buckets
until the IBF is completely empty and all elements have been decoded.
</t>
+ <t>
+ In the following example the successful decoding of an IBF containing the two elements previously
+ added.
+ </t>
+ <t>
+ IBF with the two encoded elements:
+ </t>
+ <figure anchor="figure_ibf_decode_0">
+ <artwork name="" type="" align="left" alt=""><![CDATA[
+ bit-1 bit-2 bit-3 bit-4
+ +-------------+-------------+-------------+-------------+
+ count | 1 | 2 | 0 | 1 |
+ +-------------+-------------+-------------+-------------+
+ value | 0101 | 4343 | 0000 | 4242 |
+ +-------------+-------------+-------------+-------------+
+ ]]></artwork>
+ </figure>
+ <t>
+ In the IBF are two pure buckets to decode (bit-1 and bit-4) we choose to start with decoding bucket 1,
+ we decode the element with the hash 1010 and we see that there is a new pure bucket created (bit-2)
+ </t>
+ <figure anchor="figure_ibf_decode_1">
+ <artwork name="" type="" align="left" alt=""><![CDATA[
+ bit-1 bit-2 bit-3 bit-4
+ +-------------+-------------+-------------+-------------+
+ count | 0 | 1 | 0 | 1 |
+ +-------------+-------------+-------------+-------------+
+ value | 0000 | 4242 | 0000 | 4242 |
+ +-------------+-------------+-------------+-------------+
+ ]]></artwork>
+ </figure>
+ <t>
+ In the IBF only pure buckets are left, we choose to continue decoding bucket 2 and decode element
+ with the hash 4242. Now the IBF is empty (all buckets have count 0) that means the IBF has successfully
+ decoded.
+ </t>
+ <figure anchor="figure_ibf_decode_2">
+ <artwork name="" type="" align="left" alt=""><![CDATA[
+ bit-1 bit-2 bit-3 bit-4
+ +-------------+-------------+-------------+-------------+
+ count | 0 | 0 | 0 | 0 |
+ +-------------+-------------+-------------+-------------+
+ value | 0000 | 0000 | 0000 | 0000 |
+ +-------------+-------------+-------------+-------------+
+ ]]></artwork>
+ </figure>
</section>
<section anchor="ibv_operations_setdiff" numbered="true" toc="default">
<name>Set difference</name>
@@ -262,7 +375,7 @@
<t>
In full synchronisation mode, if the set of the initiating peer is bigger than the set of the receiving peer, the initiating ### Nachrichten und states ander darstellen
- peer sends a "Request Full" message and change from "Expecting SE" in "Full Receiving" State. ### Refferenz auf nachrichten & all elements = message type anstat beschreibung
+ peer sends a "Request Full" message and change from "Expecting SE" in "Full Receiving" State. ### Refferenz auf nachrichten und all elements = message type anstat beschreibung
In all other cases the initiating peer sends all set elements to the other peer
followed by the "Full Done" message and changes into "Full Sending" State.
</t>
