commit a6efc4c296f43ac1df5eb86c441f3aa380389fc1
parent f7cabaeda33f191044bae0fcd1090c77028ba6ee
Author: Elias Summermatter <elias.summermatter@seccom.ch>
Date: Sun, 13 Jun 2021 17:19:33 +0200
Fixed some code formatig stuff
Diffstat:
1 file changed, 96 insertions(+), 64 deletions(-)
diff --git a/draft-summermatter-set-union.xml b/draft-summermatter-set-union.xml
@@ -2000,6 +2000,8 @@ FUNCTION decide_operation_mode(avg_element_size,
est_local_set_diff
est_remote_set_diff,
rtt_tradeoff)
+
+ # If a set size is zero always do full sync
IF (0 == remote_set_size)
RETURN FULL_SYNC_LOCAL_SENDING_FIRST
IF END
@@ -2007,56 +2009,66 @@ FUNCTION decide_operation_mode(avg_element_size,
RETURN FULL_SYNC_REMOTE_SENDING_FIRST
IF END
+ # Estimate required transferred bytes when doing a full synchronisation
+ # and transmitting local set first.
estimated_total_diff = est_set_diff_remote + est_local_set_diff
-
- total_elements_to_send_local_send_first = est_remote_set_diff + local_set_size
-
- total_bytes_full_local_send_first = (avg_element_size * total_elements_to_send_local_send_first)
- + (total_elements_to_send_local_send_first * sizeof(ELEMENT_MSG_HEADER))
- + (sizeof(FULL_DONE_MSG_HEADER) * 2)
- + RTT_MIN_FULL * rtt_tradeoff
-
- total_elements_to_send_remote_send_first = est_local_set_diff + remote_set_size
-
- total_bytes_full_remote_send_first = (avg_element_size * total_elements_to_send_remote_send_first)
- + ( total_elements_to_send_remote_send_first * sizeof(ELEMENT_MSG_HEADER))
- + (sizeof(FULL_DONE_MSG_HEADER) * 2)
- + (RTT_MIN_FULL + 0.5) * rtt_tradeoff
- + sizeof(REQUEST_FULL_MSG)
-
+ total_elements_local_send = est_remote_set_diff + local_set_size
+ total_bytes_local_send = (avg_element_size * total_elements_local_send)
+ + (total_elements_local_send * sizeof(ELEMENT_MSG_HEADER))
+ + (sizeof(FULL_DONE_MSG_HEADER) * 2)
+ + RTT_MIN_FULL * rtt_tradeoff
+
+ # Estimate required transferred bytes when doing a full synchronisation
+ # and transmitting remote set first.
+ total_elements_remote_send = est_local_set_diff + remote_set_size
+ total_bytes_remote_send = (avg_element_size * total_elements_remote_send)
+ + ( total_elements_remote_send * sizeof(ELEMENT_MSG_HEADER))
+ + (sizeof(FULL_DONE_MSG_HEADER) * 2)
+ + (RTT_MIN_FULL + 0.5) * rtt_tradeoff
+ + sizeof(REQUEST_FULL_MSG)
+
+ # Estimate required transferred bytes when doing a differential synchronisation
+
+ # Estimate messages required to transfer IBF
ibf_bucket_count = estimated_total_diff * IBF_BUCKET_NUMBER_FACTOR
-
IF (ibf_bucket_count <= IBF_MIN_SIZE)
ibf_bucket_count = IBF_MIN_SIZE
END IF
-
ibf_message_count = ceil ( ibf_bucket_count / MAX_BUCKETS_PER_MESSAGE)
+ # Estimate average counter length with variable counter
estimated_counter_size = MIN (
2 * LOG2(local_set_size / ibf_bucket_count),
LOG2(local_set_size)
)
counter_bytes = estimated_counter_size / 8
+ # Sum up all messages required to do differential synchronisation
ibf_bytes = sizeof(IBF_MESSAGE) * ibf_message_count * 1.2
- + ibf_bucket_count * sizeof(IBF_KEY) * 1.2
- + ibf_bucket_count * sizeof(IBF_KEYHASH) * 1.2
- + ibf_bucket_count * counter_bytes * 1.2
+ + ibf_bucket_count * sizeof(IBF_KEY) * 1.2
+ + ibf_bucket_count * sizeof(IBF_KEYHASH) * 1.2
+ + ibf_bucket_count * counter_bytes * 1.2
- element_size = (avg_element_size + sizeof(ELEMENT_MSG_HEADER)) * estimated_total_diff
done_size = sizeof(DONE_HEADER)
- inquery_size = (sizeof(IBF_KEY) + sizeof(INQUERY_MSG_HEADER)) * estimated_total_diff
- demand_size = (sizeof(HASHCODE) + sizeof(DEMAND_MSG_HEADER)) * estimated_total_diff
- offer_size = (sizeof(HASHCODE) + sizeof(OFFER_MSG_HEADER)) * estimated_total_diff
+ element_size = (avg_element_size + sizeof(ELEMENT_MSG_HEADER))
+ * estimated_total_diff
+ inquery_size = (sizeof(IBF_KEY) + sizeof(INQUERY_MSG_HEADER))
+ * estimated_total_diff
+ demand_size = (sizeof(HASHCODE) + sizeof(DEMAND_MSG_HEADER))
+ * estimated_total_diff
+ offer_size = (sizeof(HASHCODE) + sizeof(OFFER_MSG_HEADER))
+ * estimated_total_diff
total_bytes_diff = (element_size + done_size + inquery_size
- + demand_size + offer_size + ibf_bytes)
- + DIFFERENTIAL_RTT_MEAN * rtt_tradeoff
+ + demand_size + offer_size + ibf_bytes)
+ + DIFFERENTIAL_RTT_MEAN * rtt_tradeoff
+
+ # Decide for a optimal mode of operation
- full_min = MIN (total_bytes_full_local_send_first,
- total_bytes_full_local_send_first)
+ full_min = MIN (total_bytes_local_send,
+ total_bytes_local_send)
IF (full_min < total_bytes_diff)
- IF (total_bytes_full_remote_send_first > total_bytes_full_local_send_first)
+ IF (total_bytes_remote_send > total_bytes_local_send)
RETURN FULL_SYNC_LOCAL_SENDING_FIRST
ELSE
RETURN FULL_SYNC_REMOTE_SENDING_FIRST
@@ -2128,18 +2140,18 @@ FUNCTION END
Since the optimal number of bytes a counter in the IBF contains is very variable and varies
due to different parameters. Details are described in the BSC thesis
by Summermatter <xref target="byzantine_fault_tolerant_set_reconciliation" format="default"/>.
- Therefore a compression algorithm has been implemented, which always creates the IBF counter in optimal size.
+ Therefore a packing algorithm has been implemented, which always creates the IBF counter in optimal size.
and thus minimizes the bandwidth needed to transmit the IBF.
</t>
<t>
- A simple algorithm is used for the compression. In a first step it is determined, which is the largest counter
+ A simple algorithm is used for the packing. In a first step it is determined, which is the largest counter
and how many bits are needed to store it. In a second step for every counter of every bucket, the counter
is stored in the bit length, determined in the first step and these are concatenated.
</t>
<t>
Three individual functions are used for this purpose. The first one is a function that iterates over each bucket of
the IBF to get the maximum counter in the IBF. As second it needs
- a function that compresses the counter of the IBF and thirdly a function that decompresses the counter.
+ a function that pack the counter of the IBF and thirdly a function that unpack the counter.
</t>
<figure anchor="performance_counter_variable_size_code">
<artwork name="" type="" align="left" alt=""><![CDATA[
@@ -2155,14 +2167,16 @@ FUNCTION ibf_get_max_counter(ibf)
IF bucket.counter > max_counter
max_counter = bucket.counter
- RETURN CEILING( log2 ( max_counter ) ) # next bigger discrete number of the binary logarithm of the max counter
+ # next bigger discrete number of the binary logarithm of the max counter
+ RETURN CEILING( log2 ( max_counter ) )
# INPUTS:
# ibf: The IBF
-# offset: The offset which defines the starting point from which bucket the compress operation starts
-# count: The number of buckets in the array that will be compressed
+# offset: The offset which defines the starting point from which bucket the
+# pack operation starts
+# count: The number of buckets in the array that will be packed
# OUTPUTS:
-# returns: A byte array of compressed counters to send over the network
+# returns: A byte array of packed counters to send over the network
FUNCTION pack_counter(ibf, offset, count)
counter_bytes = ibf_get_max_counter(ibf)
@@ -2206,7 +2220,7 @@ FUNCTION pack_counter(ibf, offset, count)
byte_ctr++
NEXT_BUCKET
- # Write the last partial compressed byte to the buffer
+ # Write the last partial packed byte to the buffer
buffer[byte_ctr] = store << (8 - store_bits)
byte_ctr++
@@ -2214,10 +2228,13 @@ FUNCTION pack_counter(ibf, offset, count)
# INPUTS:
# ibf: The IBF
-# offset: The offset which defines the starting point from which bucket the compress operation starts
-# count: The number of buckets in the array that will be compressed
-# counter_bit_length: The bit length of the counter can be found in the ibf message in the ibf_counter_bit_length field
-# packed_data: A byte array which contains the data packed with the pack_counter function
+# offset: The offset which defines the starting point from which bucket
+ the packed operation starts
+# count: The number of buckets in the array that will be packed
+# counter_bit_length: The bit length of the counter can be found in the
+ ibf message in the ibf_counter_bit_length field
+# packed_data: A byte array which contains the data packed with the pack_counter
+ function
# OUTPUTS:
# returns: Nothing because the unpacked counter is saved directly into the IBF
@@ -2675,7 +2692,7 @@ FUNCTION END
# rd: Number of duplicated elements received
# rf: Number of fresh elements received
# Output:
-# Returns TRUE if full syncronisation is plausible and FALSE otherwise
+# Returns TRUE if full synchronisation is plausible and FALSE otherwise
FUNCTION full_sync_plausibility_check (state,rs,lis,rd,rf)
security_level_lb = 1 / SECURITY_LEVEL
@@ -2900,8 +2917,8 @@ FUNCTION END
which means within the byzantine boundaries described in section <xref target="security_generic_functions_check_byzantine_boundaries" format="title" />.
</t>
<t>
- In case of compressed strata estimators the decompression algorithm needs to
- be protected against decompression memory corruption (memory overflow).
+ In case of compressed strata estimators the unpacking algorithm needs to
+ be protected against unpacking memory corruption (memory overflow).
</t>
</dd>
</dl>
@@ -3014,19 +3031,25 @@ FUNCTION END
Name | Value | Description
----------------------------+------------+--------------------------
SE_STRATA_COUNT | 32 | Number of IBFs in a strata estimator
-IBF_HASH_NUM* | 3 | Number of times an element is hashed to an IBF
-IBF_FACTOR* | 2 | The factor by which the size of the IBF is increased
- in case of decoding failure or initially from the
- set difference
-MAX_BUCKETS_PER_MESSAGE | 1120 | Maximum bucket of an IBF that are transmitted in single message
+IBF_HASH_NUM* | 3 | Number of times an element is hashed to an
+ IBF
+IBF_FACTOR* | 2 | The factor by which the size of the IBF is
+ increased in case of decoding failure or
+ initially from the set difference
+MAX_BUCKETS_PER_MESSAGE | 1120 | Maximum bucket of an IBF that are
+ transmitted in single message
IBF_MIN_SIZE* | 37 | Minimal number of buckets in an IBF
-DIFFERENTIAL_RTT_MEAN* | 3.65145 | The average RTT that is needed for a differential synchronisation
-SECURITY_LEVEL* | 2^80 | Security level for probabilistic security algorithms
-PROBABILITY_FOR_NEW_ROUND* | 0.15 | The probability for a IBF decoding failure in the differential
- synchronisation mode
-DIFFERENTIAL_RTT_MEAN* | 3.65145 | The average RTT that is needed for a differential synchronisation
+DIFFERENTIAL_RTT_MEAN* | 3.65145 | The average RTT that is needed for a
+ differential synchronisation
+SECURITY_LEVEL* | 2^80 | Security level for probabilistic security
+ algorithms
+PROBABILITY_FOR_NEW_ROUND* | 0.15 | The probability for a IBF decoding failure
+ in the differential synchronisation mode
+DIFFERENTIAL_RTT_MEAN* | 3.65145 | The average RTT that is needed for a
+ differential synchronisation
MAX_IBF_SIZE | 1048576 | Maximal number of buckets in an IBF
-AVG_BYTE_SIZE_SE* | 4221 | Average byte size of a single strata estimator
+AVG_BYTE_SIZE_SE* | 4221 | Average byte size of a single strata
+ estimator
VALID_NUMBER_SE* | [1,2,4,8] | Valid number of SE in
]]></artwork>
@@ -3043,20 +3066,29 @@ VALID_NUMBER_SE* | [1,2,4,8] | Valid number of SE in
<artwork name="" type="" align="left" alt=""><![CDATA[
Type | Name | References | Description
--------+----------------------------+------------+--------------------------
- 559 | SETU_P2P_REQUEST_FULL | [This.I-D] | Request the full set of the other peer
- 710 | SETU_P2P_SEND_FULL | [This.I-D] | Signals to send the full set to the other peer
- 560 | SETU_P2P_DEMAND | [This.I-D] | Demand the whole element from the other peer, given only the hash code.
- 561 | SETU_P2P_INQUIRY | [This.I-D] | Tell the other peer to send a list of hashes that match an IBF key.
- 562 | SETU_P2P_OFFER | [This.I-D] | Tell the other peer which hashes match a given IBF key.
- 563 | SETU_P2P_OPERATION_REQUEST | [This.I-D] | Request a set union operation from a remote peer.
+ 559 | SETU_P2P_REQUEST_FULL | [This.I-D] | Request the full set of the other
+ peer
+ 710 | SETU_P2P_SEND_FULL | [This.I-D] | Signals to send the full set to the
+ other peer
+ 560 | SETU_P2P_DEMAND | [This.I-D] | Demand the whole element from the
+ other peer, given only the hash
+ code.
+ 561 | SETU_P2P_INQUIRY | [This.I-D] | Tell the other peer to send a list
+ of hashes that match an IBF key.
+ 562 | SETU_P2P_OFFER | [This.I-D] | Tell the other peer which hashes
+ match a given IBF key.
+ 563 | SETU_P2P_OPERATION_REQUEST | [This.I-D] | Request a set union operation from
+ a remote peer.
564 | SETU_P2P_SE | [This.I-D] | Strata Estimator uncompressed
565 | SETU_P2P_IBF | [This.I-D] | Invertible Bloom Filter slices.
566 | SETU_P2P_ELEMENTS | [This.I-D] | Actual set elements.
567 | SETU_P2P_IBF_LAST | [This.I-D] | Invertible Bloom Filter Last Slice.
568 | SETU_P2P_DONE | [This.I-D] | Set operation is done.
569 | SETU_P2P_SEC | [This.I-D] | Strata Estimator compressed
- 570 | SETU_P2P_FULL_DONE | [This.I-D] | All elements in full synchronisation mode have been sent is done.
- 571 | SETU_P2P_FULL_ELEMENT | [This.I-D] | Send an actual element in full synchronisation mode.
+ 570 | SETU_P2P_FULL_DONE | [This.I-D] | All elements in full synchronisation
+ mode have been sent is done.
+ 571 | SETU_P2P_FULL_ELEMENT | [This.I-D] | Send an actual element in full
+ synchronisation mode.
]]></artwork>
</figure>
