commit 32feaf1121b83e0bb9f4efa1f1e1feafbc242db2
parent aa3d59625b1cf688c268c56caaee65494996cd35
Author: Elias Summermatter <elias.summermatter@seccom.ch>
Date: Wed, 16 Jun 2021 21:14:50 +0200
Fixed more line length stuff
Diffstat:
2 files changed, 181 insertions(+), 143 deletions(-)
diff --git a/draft-summermatter-set-union-01.xml b/draft-summermatter-set-union-01.xml
@@ -1215,7 +1215,7 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
| MSG SIZE | MSG TYPE | ELEMENT COUNT |
+-----+-----+-----+-----+-----+-----+-----+-----+
| APX
- +-----+-----+-----+-----+-----+-----+-----+-----+ /
+ +-----+-----+-----+-----+-----+-----+-----+-----+
/ APPLICATION DATA /
/ /
]]></artwork>
@@ -1274,7 +1274,7 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
| OFFSET | SALT | IMCS |
+-----+-----+-----+-----+-----+-----+-----+-----+
| IBF-SLICE
- +-----+-----+-----+-----+-----+-----+-----+-----+ /
+ +-----+-----+-----+-----+-----+-----+-----+-----+
/ /
/ /
]]></artwork>
@@ -1417,7 +1417,7 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
| MSG SIZE | MSG TYPE | E TYPE | PADDING |
+-----+-----+-----+-----+-----+-----+-----+-----+
| E SIZE | DATA
- +-----+-----+ /
+ +-----+-----+-----+-----+-----+-----+-----+-----+
/ /
/ /
]]></artwork>
@@ -1482,11 +1482,11 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
+-----+-----+-----+-----+-----+-----+-----+-----+
... ...
+-----+-----+-----+-----+-----+-----+-----+-----+
- | HASH 1 | HASH 2
+ HASH 1 | HASH 2
+-----+-----+-----+-----+-----+-----+-----+-----+
... ...
+-----+-----+-----+-----+-----+-----+-----+-----+
- | HASH 2 | HASH n
+ HASH 2 | HASH n
+-----+-----+-----+-----+-----+-----+-----+-----+
/ /
/ /
@@ -1502,9 +1502,9 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
<dd>
is SETU_P2P_OFFER as registered in <xref target="gana" format="title" /> in network byte order.
</dd>
- <dt>HASHES</dt>
+ <dt>HASH n</dt>
<dd>
- contains one or more successive SHA 512-bit hashes of the elements that are being requested with <em><xref target="messages_inquiry" format="title" /></em> messages.
+ contains n (one or more) successive SHA 512-bit hashes of the elements that are being requested with <em><xref target="messages_inquiry" format="title" /></em> messages.
</dd>
</dl>
</section>
@@ -1533,13 +1533,13 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
+-----+-----+-----+-----+-----+-----+-----+-----+
| MSG SIZE | MSG TYPE | SALT |
+-----+-----+-----+-----+-----+-----+-----+-----+
- | IBF KEY 1 |
+ | IBF KEY 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
- | IBF KEY 2 |
+ | IBF KEY 2 |
+-----+-----+-----+-----+-----+-----+-----+-----+
... ...
+-----+-----+-----+-----+-----+-----+-----+-----+
- | IBF KEY n |
+ | IBF KEY n |
+-----+-----+-----+-----+-----+-----+-----+-----+
/ /
/ /
@@ -1557,7 +1557,7 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
</dd>
<dt>IBF KEY</dt>
<dd>
- contains one or more successive ibf keys (64-bit unsigned integer) for which the inquiry is sent.
+ contains n (one or more) successive ibf keys (64-bit unsigned integer) for which the inquiry is sent.
</dd>
</dl>
</section>
@@ -1585,15 +1585,15 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
<artwork name="" type="" align="left" alt=""><![CDATA[
0 8 16 24 32 40 48 56
+-----+-----+-----+-----+-----+-----+-----+-----+
- | MSG SIZE | MSG TYPE | HASH
- +-----+-----+-----+-----+
+ | MSG SIZE | MSG TYPE | HASH 1
+ +-----+-----+-----+-----+-----+-----+-----+-----+
... ...
+-----+-----+-----+-----+-----+-----+-----+-----+
- | HASH 1 | HASH 2
+ HASH 1 | HASH 2
+-----+-----+-----+-----+-----+-----+-----+-----+
... ...
+-----+-----+-----+-----+-----+-----+-----+-----+
- | HASH 2 | HASH n
+ HASH 2 | HASH n
+-----+-----+-----+-----+-----+-----+-----+-----+
/ /
/ /
@@ -1609,9 +1609,9 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
<dd>
the type of SETU_P2P_DEMAND as registered in <xref target="gana" format="title" /> in network byte order.
</dd>
- <dt>HASH</dt>
+ <dt>HASH n</dt>
<dd>
- contains one or more successive SHA 512-bit hashes of the elements that are being demanded.
+ contains n (one or more) successive SHA 512-bit hashes of the elements that are being demanded.
</dd>
</dl>
</section>
@@ -1636,8 +1636,10 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
<artwork name="" type="" align="left" alt=""><![CDATA[
0 8 16 24 32 40 48 56
+-----+-----+-----+-----+-----+-----+-----+-----+
- | MSG SIZE | MSG TYPE |
+ | MSG SIZE | MSG TYPE | FINAL CHECKSUM
+-----+-----+-----+-----+-----+-----+-----+-----+
+ / /
+ / /
]]></artwork>
</figure>
@@ -1653,7 +1655,7 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
</dd>
<dt>FINAL CHECKSUM</dt>
<dd>
- a SHA-512 bit hash of the full set after synchronization. This should ensure that the sets are identical in the end!
+ a SHA-512 hash XOR sum of the full set after synchronization. This should ensure that the sets are identical in the end!
</dd>
</dl>
</section>
@@ -1680,7 +1682,7 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
0 8 16 24 32 40 48 56
+-----+-----+-----+-----+-----+-----+-----+-----+
| MSG SIZE | MSG TYPE | FINAL CHECKSUM
- +-----+-----+-----+-----+
+ +-----+-----+-----+-----+-----+-----+-----+-----+
/ /
/ /
]]></artwork>
@@ -1697,7 +1699,7 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
</dd>
<dt> FINAL CHECKSUM</dt>
<dd>
- a SHA-512 bit hash of the full set after synchronization. This should ensure that the sets are identical in the end!
+ a SHA-512 hash XOR sum of the full set after synchronization. This should ensure that the sets are identical in the end!
</dd>
</dl>
</section>
@@ -1855,8 +1857,8 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
+-----+-----+-----+-----+-----+-----+-----+-----+
| MSG SIZE | MSG TYPE | SEC | SETSIZE
+-----+-----+-----+-----+-----+-----+-----+-----+
- SETSIZE | SE-SLICES
- +-----+-----+-----+-----+
+ SETSIZE | SE-SLICES
+ +-----+-----+-----+-----+-----+-----+-----+-----+
/ /
/ /
]]></artwork>
@@ -1873,7 +1875,7 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
</dd>
<dt>SEC</dt>
<dd>
- is a 8-bit unsigned integer in networkf byte order, which indicates how many strata estimators
+ is a 8-bit unsigned integer in network byte order, which indicates how many strata estimators
with different salts are attached to the message. Valid values are 1,2,4 or 8, more details can be found
in the section <xref target="performance_multi_se" format="title" />.
</dd>
@@ -1902,13 +1904,13 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
SE-SLICE
0 8 16 24 32 40 48 56
+-----+-----+-----+-----+-----+-----+-----+-----+
- | SE_1->IBF_1 |
+ | SE_1 -> IBF_1
+-----+-----+-----+-----+-----+-----+-----+-----+
... ...
+-----+-----+-----+-----+-----+-----+-----+-----+
- | SE_1->IBF_30 |
+ | SE_1 -> IBF_30
+-----+-----+-----+-----+-----+-----+-----+-----+
- | SE_2->IBF_1 |
+ | SE_2 -> IBF_1
+-----+-----+-----+-----+-----+-----+-----+-----+
... ...
/ /
@@ -1973,8 +1975,8 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
+-----+-----+-----+-----+-----+-----+-----+-----+
| MSG SIZE | MSG TYPE | E TYPE | PADDING |
+-----+-----+-----+-----+-----+-----+-----+-----+
- | SIZE | AE TYPE | DATA
- +-----+-----+-----+-----+
+ | SIZE | AE TYPE | DATA
+ +-----+-----+-----+-----+-----+-----+-----+-----+
/ /
/ /
]]></artwork>
@@ -2042,10 +2044,12 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
<figure anchor="performance_formulas_operationmode_code">
<artwork name="" type="" align="left" alt=""><![CDATA[
# CONSTANTS:
-# IBF_BUCKET_NUMBER_FACTOR = 2: The amount the IBF gets increased if decoding fails
-# RTT_MIN_FULL = 2: Minimal round trips used for full syncronisation (always 2 or 2.5)
+# IBF_BUCKET_NUMBER_FACTOR = 2: The amount the IBF gets increased if
+# decoding fails
+# RTT_MIN_FULL = 2: Minimal round trips used for full Synchronisation
# IBF_MIN_SIZE = 37: The minimal size of an IBF
-# MAX_BUCKETS_PER_MESSAGE: Custom value depending on the underlying protocol
+# MAX_BUCKETS_PER_MESSAGE: Custom value depending on the underlying
+# protocol
# INPUTS:
# avg_es: The average element size
# lss: The initial local set size
@@ -2054,7 +2058,8 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
# rsd: the estimated remote set difference calculated by the SE
# rtt: the tradeoff between round trips and bandwidth
# OUTPUT:
-# FULL_SYNC_REMOTE_SENDING_FIRST, FULL_SYNC_LOCAL_SENDING_FIRST or DIFFERENTIAL_SYNC
+# FULL_SYNC_REMOTE_SENDING_FIRST, FULL_SYNC_LOCAL_SENDING_FIRST or
+# DIFFERENTIAL_SYNC
FUNCTION decide_operation_mode(avg_es,
lss,
@@ -2064,11 +2069,6 @@ FUNCTION decide_operation_mode(avg_es,
rtt)
# If a set size is zero always do full sync
- # TODO: check if these two conditions are
- # actually meaningful, I suspect even without
- # this check at the beginning the logic below
- # should always yield the same result for these
- # extreme cases, allowing us to omit this code.
IF 0 == rss THEN
RETURN FULL_SYNC_LOCAL_SENDING_FIRST
END IF
@@ -2076,25 +2076,27 @@ FUNCTION decide_operation_mode(avg_es,
RETURN FULL_SYNC_REMOTE_SENDING_FIRST
END IF
- # Estimate required transferred bytes when doing a full synchronisation
- # and transmitting local set first.
+ # Estimate required transferred bytes when doing a full
+ # synchronisation and transmitting local set first.
+ semh = sizeof(ELEMENT_MSG_HEADER)
estimated_total_diff = rsd + lsd
total_elements_local_send = rsd + lss
cost_local_full_sync = avg_es * total_elements_local_send
- + total_elements_local_send * sizeof(ELEMENT_MSG_HEADER)
+ + total_elements_local_send * semh
+ sizeof(FULL_DONE_MSG_HEADER) * 2
+ RTT_MIN_FULL * rtt
- # Estimate required transferred bytes when doing a full synchronisation
- # and transmitting remote set first.
+ # Estimate required transferred bytes when doing a full
+ # synchronisation and transmitting remote set first.
total_elements_remote_send = lsd + rss
cost_remote_full_sync = avg_es * total_elements_remote_send
- + total_elements_remote_send * sizeof(ELEMENT_MSG_HEADER)
+ + total_elements_remote_send * semh
+ sizeof(FULL_DONE_MSG_HEADER) * 2
+ (RTT_MIN_FULL + 0.5) * rtt
+ sizeof(REQUEST_FULL_MSG)
- # Estimate required transferred bytes when doing a differential synchronisation
+ # 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
@@ -2165,7 +2167,8 @@ END FUNCTION
<figure anchor="performance_formula_ibf_parameters_code">
<artwork name="" type="" align="left" alt=""><![CDATA[
# CONSTANTS:
-# IBF_BUCKET_NUMBER_FACTOR = 2: The amount the IBF gets increased if decoding fails
+# IBF_BUCKET_NUMBER_FACTOR = 2: The amount the IBF gets increased
+ if decoding fails
# Inputs:
# sd: Estimated set difference
# Output:
@@ -2253,22 +2256,23 @@ FUNCTION ibf_get_max_counter(ibf)
max_counter = bucket.counter
END IF
END FOR
- # 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 ) )
END FUNCTION
# INPUTS:
# ibf: The IBF
-# offset: The offset which defines the starting point from which bucket the
-# pack operation starts
+# 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 packed counters to send over the network
# INPUTS:
# ibf: The IBF
-# offset: The offset which defines the starting point from which bucket the
-# pack operation starts
+# 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 packed counters to send over the network
@@ -2278,7 +2282,7 @@ FUNCTION pack_counter(ibf, offset, count)
store_bits = 0
store = 0
byte_ctr = 0
- buffer=[]
+ buf=[]
FOR bucket IN ibf[offset] TO ibf[count] DO
counter = bucket.counter
@@ -2292,7 +2296,7 @@ FUNCTION pack_counter(ibf, offset, count)
bit_to_shift = byte_len - bit_free
store = store << bit_free
END IF
- buffer[byte_ctr] = (( counter >> bit_to_shift) | store) & 0xFF
+ buf[byte_ctr] = (( counter >> bit_to_shift) | store) & 0xFF
byte_ctr = byte_ctr + 1
byte_len -= 8 - store_bits
counter = counter & ((1 << byte_len) - 1)
@@ -2306,24 +2310,25 @@ FUNCTION pack_counter(ibf, offset, count)
# Write the last partial packed byte to the buffer
IF store_bits > 0 THEN
- buffer[byte_ctr] = store << (8 - store_bits)
+ buf[byte_ctr] = store << (8 - store_bits)
byte_ctr = byte_ctr + 1
END IF
- RETURN buffer
+ RETURN buf
FUNCTION END
# INPUTS:
# ibf: The IBF
# offset: The offset which defines the starting point from which bucket
- the packed operation starts
+ the packed operation starts
# count: The number of buckets in the array that will be packed
# cbl: The bit length of the counter can be found in the
- ibf message in the ibf_counter_bit_length field
+ ibf message in the ibf_counter_bit_length field
# pd: A byte array which contains the data packed with the pack_counter
- function
+ function
# OUTPUTS:
-# returns: Nothing because the unpacked counter is saved directly into the IBF
+# returns: Nothing because the unpacked counter is saved directly
+ into the IBF
FUNCTION unpack_counter(ibf, offset, count, cbl, pd)
ibf_bucket_ctr = 0
@@ -2332,7 +2337,7 @@ FUNCTION unpack_counter(ibf, offset, count, cbl, pd)
byte_ctr = 0
WHILE TRUE
- byte_to_read = pd[byte_ctr]
+ byte_read = pd[byte_ctr]
bit_to_pack_left = 8
byte_ctr++
@@ -2350,10 +2355,10 @@ FUNCTION unpack_counter(ibf, offset, count, cbl, pd)
store = store << bit_use
END IF
bytes_to_shift = bit_to_pack_left - bit_use
- counter_partial = byte_to_read >> bytes_to_shift
+ counter_partial = byte_read >> bytes_to_shift
store = store | counter_partial
ibf.counter[ibf_bucket_ctr + offset] = store
- byte_to_read = byte_to_read & (( 1 << bytes_to_shift ) - 1)
+ byte_read = byte_read & (( 1 << bytes_to_shift ) - 1)
bit_to_pack_left -= bit_use
ibf_bucket_ctr++
@@ -2363,10 +2368,10 @@ FUNCTION unpack_counter(ibf, offset, count, cbl, pd)
store_bits = store_bits + bit_to_pack_left
IF 0 == store_bits THEN
- store = byte_to_read
+ store = byte_read
ELSE
store = store << bit_to_pack_left
- store = store | byte_to_read
+ store = store | byte_read
END IF
BREAK
END IF
@@ -2408,7 +2413,8 @@ END FUNCTION
# Inputs:
# value: Input value to salt (needs to be 64 bit unsigned)
-# salt: Salt to salt value with; Should always be ascending and start at zero
+# salt: Salt to salt value with; Should always be ascending and start
+# at zero
i.e. SE1 = Salt 0; SE2 = Salt 1 etc.
# Output:
# Returns: Salted value
@@ -2531,15 +2537,20 @@ END FUNCTION
<artwork name="" type="" align="left" alt=""><![CDATA[
-Chain for elements +---------+ +---------+ +---------+ +---------+
-NOT in IBF decoding | INQUIRY | ---> | OFFER | ===> | DEMAND | ===> | ELEMENT |
-peers set +---------+ +---------+ +---------+ +---------+
+Chain for
+elements +---------+ +---------+ +---------+ +---------+
+NOT in IBF | INQUIRY |--->| OFFER |===>| DEMAND |===>| ELEMENT |
+decoding +---------+ +---------+ +---------+ +---------+
+peers set
+
+Chain for
+elements +---------+ +---------+ +---------+
+in IBF | OFFER |--->| DEMAND |===>| ELEMENT |
+decoding +---------+ +---------+ +---------+
+peers set
-Chain for elements +---------+ +---------+ +---------+
-in IBF decoding | OFFER | ---> | DEMAND | ===> | ELEMENT |
-peers set +---------+ +---------+ +---------+
- --->: Answer not mandatory
- ===>: Always answer needed.
+ --->: Answer not mandatory
+ ===>: Always answer needed.
]]></artwork>
</figure>
<t>
@@ -3029,33 +3040,44 @@ END FUNCTION
<figure anchor="figure_constants">
<artwork name="" type="" align="left" alt=""><![CDATA[
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 (from section 4.5.2)
-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.
+----------------------------+------------+-------------------------------
+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.
(from section 4.5.2)
-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
- (from section 3.8)
-DIFFERENTIAL_RTT_MEAN* | 3.65145 | The average RTT that is needed for a
+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.
+ (from section 4.5.2)
+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. (from section 3.8)
+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. (from section 5.8)
+PROBABILITY_FOR_NEW_ROUND* | 0.15 | The probability for a IBF
+ decoding failure in the
differential synchronisation
-SECURITY_LEVEL* | 2^80 | Security level for probabilistic security
- algorithms (from section 5.8)
-PROBABILITY_FOR_NEW_ROUND* | 0.15 | The probability for a IBF decoding failure
- in the differential synchronisation mode
- (from section 5.4)
-DIFFERENTIAL_RTT_MEAN* | 3.65145 | The average RTT that is needed for a
- differential synchronisation.
+ mode. (from section 5.4)
+DIFFERENTIAL_RTT_MEAN* | 3.65145 | The average RTT that is needed
+ for a differential
+ synchronisation.
(from section 4.5.3)
-MAX_IBF_SIZE | 1048576 | Maximal number of buckets in an IBF
-AVG_BYTE_SIZE_SE* | 4221 | Average byte size of a single strata
- estimator (from section 3.4.3)
-VALID_NUMBER_SE* | [1,2,4,8] | Valid number of SE in (from section 3.4)
-
+MAX_IBF_SIZE | 1048576 | Maximal number of buckets in
+ an IBF.
+AVG_BYTE_SIZE_SE* | 4221 | Average byte size of a single
+ strata estimator.
+ (from section 3.4.3)
+VALID_NUMBER_SE* | [1,2,4,8] | Valid number of SE's
+ (from section 3.4)
]]></artwork>
</figure>
@@ -3069,29 +3091,43 @@ VALID_NUMBER_SE* | [1,2,4,8] | Valid number of SE in (from section 3
<figure anchor="figure_purposenums">
<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.
- 564 | SETU_P2P_SE | [This.I-D] | Strata Estimator uncompressed
- 565 | SETU_P2P_IBF | [This.I-D] | Invertible Bloom Filter slices.
+--------+----------------------------+------------+----------------------
+ 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
+ otherpeer, 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
+ 567 | SETU_P2P_IBF_LAST | [This.I-D] | Invertible Bloom
+ Filter Last Slices.
+ 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.
]]></artwork>
diff --git a/draft-summermatter-set-union.xml b/draft-summermatter-set-union.xml
@@ -2044,10 +2044,12 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
<figure anchor="performance_formulas_operationmode_code">
<artwork name="" type="" align="left" alt=""><![CDATA[
# CONSTANTS:
-# IBF_BUCKET_NUMBER_FACTOR = 2: The amount the IBF gets increased if decoding fails
-# RTT_MIN_FULL = 2: Minimal round trips used for full syncronisation (always 2 or 2.5)
+# IBF_BUCKET_NUMBER_FACTOR = 2: The amount the IBF gets increased if
+# decoding fails
+# RTT_MIN_FULL = 2: Minimal round trips used for full Synchronisation
# IBF_MIN_SIZE = 37: The minimal size of an IBF
-# MAX_BUCKETS_PER_MESSAGE: Custom value depending on the underlying protocol
+# MAX_BUCKETS_PER_MESSAGE: Custom value depending on the underlying
+# protocol
# INPUTS:
# avg_es: The average element size
# lss: The initial local set size
@@ -2056,7 +2058,8 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
# rsd: the estimated remote set difference calculated by the SE
# rtt: the tradeoff between round trips and bandwidth
# OUTPUT:
-# FULL_SYNC_REMOTE_SENDING_FIRST, FULL_SYNC_LOCAL_SENDING_FIRST or DIFFERENTIAL_SYNC
+# FULL_SYNC_REMOTE_SENDING_FIRST, FULL_SYNC_LOCAL_SENDING_FIRST or
+# DIFFERENTIAL_SYNC
FUNCTION decide_operation_mode(avg_es,
lss,
@@ -2066,11 +2069,6 @@ FUNCTION decide_operation_mode(avg_es,
rtt)
# If a set size is zero always do full sync
- # TODO: check if these two conditions are
- # actually meaningful, I suspect even without
- # this check at the beginning the logic below
- # should always yield the same result for these
- # extreme cases, allowing us to omit this code.
IF 0 == rss THEN
RETURN FULL_SYNC_LOCAL_SENDING_FIRST
END IF
@@ -2078,25 +2076,27 @@ FUNCTION decide_operation_mode(avg_es,
RETURN FULL_SYNC_REMOTE_SENDING_FIRST
END IF
- # Estimate required transferred bytes when doing a full synchronisation
- # and transmitting local set first.
+ # Estimate required transferred bytes when doing a full
+ # synchronisation and transmitting local set first.
+ semh = sizeof(ELEMENT_MSG_HEADER)
estimated_total_diff = rsd + lsd
total_elements_local_send = rsd + lss
cost_local_full_sync = avg_es * total_elements_local_send
- + total_elements_local_send * sizeof(ELEMENT_MSG_HEADER)
+ + total_elements_local_send * semh
+ sizeof(FULL_DONE_MSG_HEADER) * 2
+ RTT_MIN_FULL * rtt
- # Estimate required transferred bytes when doing a full synchronisation
- # and transmitting remote set first.
+ # Estimate required transferred bytes when doing a full
+ # synchronisation and transmitting remote set first.
total_elements_remote_send = lsd + rss
cost_remote_full_sync = avg_es * total_elements_remote_send
- + total_elements_remote_send * sizeof(ELEMENT_MSG_HEADER)
+ + total_elements_remote_send * semh
+ sizeof(FULL_DONE_MSG_HEADER) * 2
+ (RTT_MIN_FULL + 0.5) * rtt
+ sizeof(REQUEST_FULL_MSG)
- # Estimate required transferred bytes when doing a differential synchronisation
+ # 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
@@ -2167,7 +2167,8 @@ END FUNCTION
<figure anchor="performance_formula_ibf_parameters_code">
<artwork name="" type="" align="left" alt=""><![CDATA[
# CONSTANTS:
-# IBF_BUCKET_NUMBER_FACTOR = 2: The amount the IBF gets increased if decoding fails
+# IBF_BUCKET_NUMBER_FACTOR = 2: The amount the IBF gets increased
+ if decoding fails
# Inputs:
# sd: Estimated set difference
# Output:
@@ -2319,14 +2320,15 @@ FUNCTION END
# INPUTS:
# ibf: The IBF
# offset: The offset which defines the starting point from which bucket
- the packed operation starts
+ the packed operation starts
# count: The number of buckets in the array that will be packed
# cbl: The bit length of the counter can be found in the
- ibf message in the ibf_counter_bit_length field
+ ibf message in the ibf_counter_bit_length field
# pd: A byte array which contains the data packed with the pack_counter
- function
+ function
# OUTPUTS:
-# returns: Nothing because the unpacked counter is saved directly into the IBF
+# returns: Nothing because the unpacked counter is saved directly
+ into the IBF
FUNCTION unpack_counter(ibf, offset, count, cbl, pd)
ibf_bucket_ctr = 0
@@ -3096,9 +3098,9 @@ Type | Name | References | Description
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.
+ element from the
+ otherpeer, given
+ only the hash code.
561 | SETU_P2P_INQUIRY | [This.I-D] | Tell the other peer
to send a list of
hashes that match
