commit b492d44ea06c6a00f3f8ba8608bfe7438bf7827a
parent 6f51c7007332c3ead16616f5638980f179659511
Author: Christian Grothoff <christian@grothoff.org>
Date: Mon, 14 Jun 2021 13:39:46 +0200
review 7.1.1
Diffstat:
1 file changed, 28 insertions(+), 24 deletions(-)
diff --git a/draft-summermatter-set-union.xml b/draft-summermatter-set-union.xml
@@ -2050,6 +2050,11 @@ 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)
RETURN FULL_SYNC_LOCAL_SENDING_FIRST
IF END
@@ -2061,7 +2066,7 @@ FUNCTION decide_operation_mode(avg_es,
# and transmitting local set first.
estimated_total_diff = rsd + lsd
total_elements_local_send = rsd + lss
- total_bytes_local_send = avg_es * total_elements_local_send
+ cost_local_full_sync = avg_es * total_elements_local_send
+ total_elements_local_send * sizeof(ELEMENT_MSG_HEADER)
+ sizeof(FULL_DONE_MSG_HEADER) * 2
+ RTT_MIN_FULL * rtt
@@ -2069,14 +2074,12 @@ FUNCTION decide_operation_mode(avg_es,
# Estimate required transferred bytes when doing a full synchronisation
# and transmitting remote set first.
total_elements_remote_send = lsd + rss
- total_bytes_remote_send = avg_es * total_elements_remote_send
+ cost_remote_full_sync = avg_es * total_elements_remote_send
+ total_elements_remote_send * sizeof(ELEMENT_MSG_HEADER)
+ sizeof(FULL_DONE_MSG_HEADER) * 2
+ (RTT_MIN_FULL + 0.5) * rtt
+ sizeof(REQUEST_FULL_MSG)
- total_cost_local_send =
-
# Estimate required transferred bytes when doing a differential synchronisation
# Estimate messages required to transfer IBF
@@ -2087,16 +2090,22 @@ FUNCTION decide_operation_mode(avg_es,
ibf_message_count = ceil (ibf_bucket_count / MAX_BUCKETS_PER_MESSAGE)
# Estimate average counter length with variable counter
- estimated_counter_size = MIN (2 * LOG2(lss / ibf_bucket_count),
+ estimated_counter_bits = MIN (2 * LOG2(lss / ibf_bucket_count),
LOG2(lss))
- counter_bytes = estimated_counter_size / 8
+ estimated_counter_bytes = estimated_counter_bits / 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_bytes = sizeof(IBF_MESSAGE) * ibf_message_count
+ + ibf_bucket_count * sizeof(IBF_KEY)
+ + ibf_bucket_count * sizeof(IBF_KEYHASH)
+ + ibf_bucket_count * estimated_counter_bytes
+ # Add 20% overhead to cover IBF retries due to decoding failures
+ total_ibf_bytes = ibf_bytes * 1.2
+
+ # Estimate other message sizes to be transfered in diff sync
+ # Note that we simplify by adding the header each time;
+ # if the implementation combines multiple INQUIRY/DEMAND/OFFER
+ # requests in one message, the bandwidth would be lower.
done_size = sizeof(DONE_HEADER)
element_size = (avg_es + sizeof(ELEMENT_MSG_HEADER))
* estimated_total_diff
@@ -2107,16 +2116,16 @@ FUNCTION decide_operation_mode(avg_es,
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
+ # Estimate total cost
+ diff_cost = element_size + done_size + inquery_size
+ + demand_size + offer_size + total_ibf_bytes
+ + DIFFERENTIAL_RTT_MEAN * rtt
# Decide for a optimal mode of operation
-
- full_min = MIN (total_bytes_local_send,
- total_bytes_remote_send)
- IF (full_min < total_bytes_diff)
- IF (total_bytes_remote_send > total_bytes_local_send)
+ full_cost_min = MIN (cost_local_full_sync,
+ cost_remote_full_sync)
+ IF (full_cost_min < diff_cost)
+ IF (cost_remote_full_sync > cost_local_full_sync)
RETURN FULL_SYNC_LOCAL_SENDING_FIRST
ELSE
RETURN FULL_SYNC_REMOTE_SENDING_FIRST
@@ -2125,11 +2134,6 @@ FUNCTION decide_operation_mode(avg_es,
RETURN DIFFERENTIAL_SYNC
IF END
]]></artwork>
-<!-- FIXME: the above algorithm is a mess, starting with formatting; @Better now?
- please begin by using shorter variable names and formatting so
- that it renders properly in the HTML. Then, add some comments.
- Also note that I switched the first two conditions, which
- matters in case both sizes have set size of 0. -->
</figure>
</section>
<section anchor="performance_formula_ibf_parameters" numbered="true" toc="default">
