[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[lsd0003] branch master updated: Fixed some code formatig stuff
|
From: |
gnunet |
|
Subject: |
[lsd0003] branch master updated: Fixed some code formatig stuff |
|
Date: |
Sun, 13 Jun 2021 17:22:25 +0200 |
This is an automated email from the git hooks/post-receive script.
elias-summermatter pushed a commit to branch master
in repository lsd0003.
The following commit(s) were added to refs/heads/master by this push:
new a6efc4c Fixed some code formatig stuff
a6efc4c is described below
commit a6efc4c296f43ac1df5eb86c441f3aa380389fc1
Author: Elias Summermatter <elias.summermatter@seccom.ch>
AuthorDate: Sun Jun 13 17:19:33 2021 +0200
Fixed some code formatig stuff
---
draft-summermatter-set-union.xml | 160 +++++++++++++++++++++++----------------
1 file changed, 96 insertions(+), 64 deletions(-)
diff --git a/draft-summermatter-set-union.xml b/draft-summermatter-set-union.xml
index 003cbce..50dcad0 100644
--- 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>
--
To stop receiving notification emails like this one, please contact
gnunet@gnunet.org.
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- [lsd0003] branch master updated: Fixed some code formatig stuff,
gnunet <=