aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorElias Summermatter <elias.summermatter@seccom.ch>2021-06-16 21:14:50 +0200
committerElias Summermatter <elias.summermatter@seccom.ch>2021-06-16 21:14:50 +0200
commit32feaf1121b83e0bb9f4efa1f1e1feafbc242db2 (patch)
tree565a517063c374d0cc7661a95b5a42fc94362b3a
parentaa3d59625b1cf688c268c56caaee65494996cd35 (diff)
downloadlsd0003-32feaf1121b83e0bb9f4efa1f1e1feafbc242db2.tar.gz
lsd0003-32feaf1121b83e0bb9f4efa1f1e1feafbc242db2.zip
Fixed more line length stuff
-rw-r--r--draft-summermatter-set-union-01.xml274
-rw-r--r--draft-summermatter-set-union.xml50
2 files changed, 181 insertions, 143 deletions
diff --git a/draft-summermatter-set-union-01.xml b/draft-summermatter-set-union-01.xml
index 6261c39..98b2a3b 100644
--- a/draft-summermatter-set-union-01.xml
+++ b/draft-summermatter-set-union-01.xml
@@ -1215,7 +1215,7 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
1215 | MSG SIZE | MSG TYPE | ELEMENT COUNT | 1215 | MSG SIZE | MSG TYPE | ELEMENT COUNT |
1216 +-----+-----+-----+-----+-----+-----+-----+-----+ 1216 +-----+-----+-----+-----+-----+-----+-----+-----+
1217 | APX 1217 | APX
1218 +-----+-----+-----+-----+-----+-----+-----+-----+ / 1218 +-----+-----+-----+-----+-----+-----+-----+-----+
1219 / APPLICATION DATA / 1219 / APPLICATION DATA /
1220 / / 1220 / /
1221 ]]></artwork> 1221 ]]></artwork>
@@ -1274,7 +1274,7 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
1274 | OFFSET | SALT | IMCS | 1274 | OFFSET | SALT | IMCS |
1275 +-----+-----+-----+-----+-----+-----+-----+-----+ 1275 +-----+-----+-----+-----+-----+-----+-----+-----+
1276 | IBF-SLICE 1276 | IBF-SLICE
1277 +-----+-----+-----+-----+-----+-----+-----+-----+ / 1277 +-----+-----+-----+-----+-----+-----+-----+-----+
1278 / / 1278 / /
1279 / / 1279 / /
1280 ]]></artwork> 1280 ]]></artwork>
@@ -1417,7 +1417,7 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
1417 | MSG SIZE | MSG TYPE | E TYPE | PADDING | 1417 | MSG SIZE | MSG TYPE | E TYPE | PADDING |
1418 +-----+-----+-----+-----+-----+-----+-----+-----+ 1418 +-----+-----+-----+-----+-----+-----+-----+-----+
1419 | E SIZE | DATA 1419 | E SIZE | DATA
1420 +-----+-----+ / 1420 +-----+-----+-----+-----+-----+-----+-----+-----+
1421 / / 1421 / /
1422 / / 1422 / /
1423 ]]></artwork> 1423 ]]></artwork>
@@ -1482,11 +1482,11 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
1482 +-----+-----+-----+-----+-----+-----+-----+-----+ 1482 +-----+-----+-----+-----+-----+-----+-----+-----+
1483 ... ... 1483 ... ...
1484 +-----+-----+-----+-----+-----+-----+-----+-----+ 1484 +-----+-----+-----+-----+-----+-----+-----+-----+
1485 | HASH 1 | HASH 2 1485 HASH 1 | HASH 2
1486 +-----+-----+-----+-----+-----+-----+-----+-----+ 1486 +-----+-----+-----+-----+-----+-----+-----+-----+
1487 ... ... 1487 ... ...
1488 +-----+-----+-----+-----+-----+-----+-----+-----+ 1488 +-----+-----+-----+-----+-----+-----+-----+-----+
1489 | HASH 2 | HASH n 1489 HASH 2 | HASH n
1490 +-----+-----+-----+-----+-----+-----+-----+-----+ 1490 +-----+-----+-----+-----+-----+-----+-----+-----+
1491 / / 1491 / /
1492 / / 1492 / /
@@ -1502,9 +1502,9 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
1502 <dd> 1502 <dd>
1503 is SETU_P2P_OFFER as registered in <xref target="gana" format="title" /> in network byte order. 1503 is SETU_P2P_OFFER as registered in <xref target="gana" format="title" /> in network byte order.
1504 </dd> 1504 </dd>
1505 <dt>HASHES</dt> 1505 <dt>HASH n</dt>
1506 <dd> 1506 <dd>
1507 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. 1507 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.
1508 </dd> 1508 </dd>
1509 </dl> 1509 </dl>
1510 </section> 1510 </section>
@@ -1533,13 +1533,13 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
1533 +-----+-----+-----+-----+-----+-----+-----+-----+ 1533 +-----+-----+-----+-----+-----+-----+-----+-----+
1534 | MSG SIZE | MSG TYPE | SALT | 1534 | MSG SIZE | MSG TYPE | SALT |
1535 +-----+-----+-----+-----+-----+-----+-----+-----+ 1535 +-----+-----+-----+-----+-----+-----+-----+-----+
1536 | IBF KEY 1 | 1536 | IBF KEY 1 |
1537 +-----+-----+-----+-----+-----+-----+-----+-----+ 1537 +-----+-----+-----+-----+-----+-----+-----+-----+
1538 | IBF KEY 2 | 1538 | IBF KEY 2 |
1539 +-----+-----+-----+-----+-----+-----+-----+-----+ 1539 +-----+-----+-----+-----+-----+-----+-----+-----+
1540 ... ... 1540 ... ...
1541 +-----+-----+-----+-----+-----+-----+-----+-----+ 1541 +-----+-----+-----+-----+-----+-----+-----+-----+
1542 | IBF KEY n | 1542 | IBF KEY n |
1543 +-----+-----+-----+-----+-----+-----+-----+-----+ 1543 +-----+-----+-----+-----+-----+-----+-----+-----+
1544 / / 1544 / /
1545 / / 1545 / /
@@ -1557,7 +1557,7 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
1557 </dd> 1557 </dd>
1558 <dt>IBF KEY</dt> 1558 <dt>IBF KEY</dt>
1559 <dd> 1559 <dd>
1560 contains one or more successive ibf keys (64-bit unsigned integer) for which the inquiry is sent. 1560 contains n (one or more) successive ibf keys (64-bit unsigned integer) for which the inquiry is sent.
1561 </dd> 1561 </dd>
1562 </dl> 1562 </dl>
1563 </section> 1563 </section>
@@ -1585,15 +1585,15 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
1585 <artwork name="" type="" align="left" alt=""><![CDATA[ 1585 <artwork name="" type="" align="left" alt=""><![CDATA[
1586 0 8 16 24 32 40 48 56 1586 0 8 16 24 32 40 48 56
1587 +-----+-----+-----+-----+-----+-----+-----+-----+ 1587 +-----+-----+-----+-----+-----+-----+-----+-----+
1588 | MSG SIZE | MSG TYPE | HASH 1588 | MSG SIZE | MSG TYPE | HASH 1
1589 +-----+-----+-----+-----+ 1589 +-----+-----+-----+-----+-----+-----+-----+-----+
1590 ... ... 1590 ... ...
1591 +-----+-----+-----+-----+-----+-----+-----+-----+ 1591 +-----+-----+-----+-----+-----+-----+-----+-----+
1592 | HASH 1 | HASH 2 1592 HASH 1 | HASH 2
1593 +-----+-----+-----+-----+-----+-----+-----+-----+ 1593 +-----+-----+-----+-----+-----+-----+-----+-----+
1594 ... ... 1594 ... ...
1595 +-----+-----+-----+-----+-----+-----+-----+-----+ 1595 +-----+-----+-----+-----+-----+-----+-----+-----+
1596 | HASH 2 | HASH n 1596 HASH 2 | HASH n
1597 +-----+-----+-----+-----+-----+-----+-----+-----+ 1597 +-----+-----+-----+-----+-----+-----+-----+-----+
1598 / / 1598 / /
1599 / / 1599 / /
@@ -1609,9 +1609,9 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
1609 <dd> 1609 <dd>
1610 the type of SETU_P2P_DEMAND as registered in <xref target="gana" format="title" /> in network byte order. 1610 the type of SETU_P2P_DEMAND as registered in <xref target="gana" format="title" /> in network byte order.
1611 </dd> 1611 </dd>
1612 <dt>HASH</dt> 1612 <dt>HASH n</dt>
1613 <dd> 1613 <dd>
1614 contains one or more successive SHA 512-bit hashes of the elements that are being demanded. 1614 contains n (one or more) successive SHA 512-bit hashes of the elements that are being demanded.
1615 </dd> 1615 </dd>
1616 </dl> 1616 </dl>
1617 </section> 1617 </section>
@@ -1636,8 +1636,10 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
1636 <artwork name="" type="" align="left" alt=""><![CDATA[ 1636 <artwork name="" type="" align="left" alt=""><![CDATA[
1637 0 8 16 24 32 40 48 56 1637 0 8 16 24 32 40 48 56
1638 +-----+-----+-----+-----+-----+-----+-----+-----+ 1638 +-----+-----+-----+-----+-----+-----+-----+-----+
1639 | MSG SIZE | MSG TYPE | 1639 | MSG SIZE | MSG TYPE | FINAL CHECKSUM
1640 +-----+-----+-----+-----+-----+-----+-----+-----+ 1640 +-----+-----+-----+-----+-----+-----+-----+-----+
1641 / /
1642 / /
1641 1643
1642 ]]></artwork> 1644 ]]></artwork>
1643 </figure> 1645 </figure>
@@ -1653,7 +1655,7 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
1653 </dd> 1655 </dd>
1654 <dt>FINAL CHECKSUM</dt> 1656 <dt>FINAL CHECKSUM</dt>
1655 <dd> 1657 <dd>
1656 a SHA-512 bit hash of the full set after synchronization. This should ensure that the sets are identical in the end! 1658 a SHA-512 hash XOR sum of the full set after synchronization. This should ensure that the sets are identical in the end!
1657 </dd> 1659 </dd>
1658 </dl> 1660 </dl>
1659 </section> 1661 </section>
@@ -1680,7 +1682,7 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
1680 0 8 16 24 32 40 48 56 1682 0 8 16 24 32 40 48 56
1681 +-----+-----+-----+-----+-----+-----+-----+-----+ 1683 +-----+-----+-----+-----+-----+-----+-----+-----+
1682 | MSG SIZE | MSG TYPE | FINAL CHECKSUM 1684 | MSG SIZE | MSG TYPE | FINAL CHECKSUM
1683 +-----+-----+-----+-----+ 1685 +-----+-----+-----+-----+-----+-----+-----+-----+
1684 / / 1686 / /
1685 / / 1687 / /
1686 ]]></artwork> 1688 ]]></artwork>
@@ -1697,7 +1699,7 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
1697 </dd> 1699 </dd>
1698 <dt> FINAL CHECKSUM</dt> 1700 <dt> FINAL CHECKSUM</dt>
1699 <dd> 1701 <dd>
1700 a SHA-512 bit hash of the full set after synchronization. This should ensure that the sets are identical in the end! 1702 a SHA-512 hash XOR sum of the full set after synchronization. This should ensure that the sets are identical in the end!
1701 </dd> 1703 </dd>
1702 </dl> 1704 </dl>
1703 </section> 1705 </section>
@@ -1855,8 +1857,8 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
1855 +-----+-----+-----+-----+-----+-----+-----+-----+ 1857 +-----+-----+-----+-----+-----+-----+-----+-----+
1856 | MSG SIZE | MSG TYPE | SEC | SETSIZE 1858 | MSG SIZE | MSG TYPE | SEC | SETSIZE
1857 +-----+-----+-----+-----+-----+-----+-----+-----+ 1859 +-----+-----+-----+-----+-----+-----+-----+-----+
1858 SETSIZE | SE-SLICES 1860 SETSIZE | SE-SLICES
1859 +-----+-----+-----+-----+ 1861 +-----+-----+-----+-----+-----+-----+-----+-----+
1860 / / 1862 / /
1861 / / 1863 / /
1862 ]]></artwork> 1864 ]]></artwork>
@@ -1873,7 +1875,7 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
1873 </dd> 1875 </dd>
1874 <dt>SEC</dt> 1876 <dt>SEC</dt>
1875 <dd> 1877 <dd>
1876 is a 8-bit unsigned integer in networkf byte order, which indicates how many strata estimators 1878 is a 8-bit unsigned integer in network byte order, which indicates how many strata estimators
1877 with different salts are attached to the message. Valid values are 1,2,4 or 8, more details can be found 1879 with different salts are attached to the message. Valid values are 1,2,4 or 8, more details can be found
1878 in the section <xref target="performance_multi_se" format="title" />. 1880 in the section <xref target="performance_multi_se" format="title" />.
1879 </dd> 1881 </dd>
@@ -1902,13 +1904,13 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
1902 SE-SLICE 1904 SE-SLICE
1903 0 8 16 24 32 40 48 56 1905 0 8 16 24 32 40 48 56
1904 +-----+-----+-----+-----+-----+-----+-----+-----+ 1906 +-----+-----+-----+-----+-----+-----+-----+-----+
1905 | SE_1->IBF_1 | 1907 | SE_1 -> IBF_1
1906 +-----+-----+-----+-----+-----+-----+-----+-----+ 1908 +-----+-----+-----+-----+-----+-----+-----+-----+
1907 ... ... 1909 ... ...
1908 +-----+-----+-----+-----+-----+-----+-----+-----+ 1910 +-----+-----+-----+-----+-----+-----+-----+-----+
1909 | SE_1->IBF_30 | 1911 | SE_1 -> IBF_30
1910 +-----+-----+-----+-----+-----+-----+-----+-----+ 1912 +-----+-----+-----+-----+-----+-----+-----+-----+
1911 | SE_2->IBF_1 | 1913 | SE_2 -> IBF_1
1912 +-----+-----+-----+-----+-----+-----+-----+-----+ 1914 +-----+-----+-----+-----+-----+-----+-----+-----+
1913 ... ... 1915 ... ...
1914 / / 1916 / /
@@ -1973,8 +1975,8 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
1973 +-----+-----+-----+-----+-----+-----+-----+-----+ 1975 +-----+-----+-----+-----+-----+-----+-----+-----+
1974 | MSG SIZE | MSG TYPE | E TYPE | PADDING | 1976 | MSG SIZE | MSG TYPE | E TYPE | PADDING |
1975 +-----+-----+-----+-----+-----+-----+-----+-----+ 1977 +-----+-----+-----+-----+-----+-----+-----+-----+
1976 | SIZE | AE TYPE | DATA 1978 | SIZE | AE TYPE | DATA
1977 +-----+-----+-----+-----+ 1979 +-----+-----+-----+-----+-----+-----+-----+-----+
1978 / / 1980 / /
1979 / / 1981 / /
1980 ]]></artwork> 1982 ]]></artwork>
@@ -2042,10 +2044,12 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
2042 <figure anchor="performance_formulas_operationmode_code"> 2044 <figure anchor="performance_formulas_operationmode_code">
2043 <artwork name="" type="" align="left" alt=""><![CDATA[ 2045 <artwork name="" type="" align="left" alt=""><![CDATA[
2044# CONSTANTS: 2046# CONSTANTS:
2045# IBF_BUCKET_NUMBER_FACTOR = 2: The amount the IBF gets increased if decoding fails 2047# IBF_BUCKET_NUMBER_FACTOR = 2: The amount the IBF gets increased if
2046# RTT_MIN_FULL = 2: Minimal round trips used for full syncronisation (always 2 or 2.5) 2048# decoding fails
2049# RTT_MIN_FULL = 2: Minimal round trips used for full Synchronisation
2047# IBF_MIN_SIZE = 37: The minimal size of an IBF 2050# IBF_MIN_SIZE = 37: The minimal size of an IBF
2048# MAX_BUCKETS_PER_MESSAGE: Custom value depending on the underlying protocol 2051# MAX_BUCKETS_PER_MESSAGE: Custom value depending on the underlying
2052# protocol
2049# INPUTS: 2053# INPUTS:
2050# avg_es: The average element size 2054# avg_es: The average element size
2051# lss: The initial local set size 2055# lss: The initial local set size
@@ -2054,7 +2058,8 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
2054# rsd: the estimated remote set difference calculated by the SE 2058# rsd: the estimated remote set difference calculated by the SE
2055# rtt: the tradeoff between round trips and bandwidth 2059# rtt: the tradeoff between round trips and bandwidth
2056# OUTPUT: 2060# OUTPUT:
2057# FULL_SYNC_REMOTE_SENDING_FIRST, FULL_SYNC_LOCAL_SENDING_FIRST or DIFFERENTIAL_SYNC 2061# FULL_SYNC_REMOTE_SENDING_FIRST, FULL_SYNC_LOCAL_SENDING_FIRST or
2062# DIFFERENTIAL_SYNC
2058 2063
2059FUNCTION decide_operation_mode(avg_es, 2064FUNCTION decide_operation_mode(avg_es,
2060 lss, 2065 lss,
@@ -2064,11 +2069,6 @@ FUNCTION decide_operation_mode(avg_es,
2064 rtt) 2069 rtt)
2065 2070
2066 # If a set size is zero always do full sync 2071 # If a set size is zero always do full sync
2067 # TODO: check if these two conditions are
2068 # actually meaningful, I suspect even without
2069 # this check at the beginning the logic below
2070 # should always yield the same result for these
2071 # extreme cases, allowing us to omit this code.
2072 IF 0 == rss THEN 2072 IF 0 == rss THEN
2073 RETURN FULL_SYNC_LOCAL_SENDING_FIRST 2073 RETURN FULL_SYNC_LOCAL_SENDING_FIRST
2074 END IF 2074 END IF
@@ -2076,25 +2076,27 @@ FUNCTION decide_operation_mode(avg_es,
2076 RETURN FULL_SYNC_REMOTE_SENDING_FIRST 2076 RETURN FULL_SYNC_REMOTE_SENDING_FIRST
2077 END IF 2077 END IF
2078 2078
2079 # Estimate required transferred bytes when doing a full synchronisation 2079 # Estimate required transferred bytes when doing a full
2080 # and transmitting local set first. 2080 # synchronisation and transmitting local set first.
2081 semh = sizeof(ELEMENT_MSG_HEADER)
2081 estimated_total_diff = rsd + lsd 2082 estimated_total_diff = rsd + lsd
2082 total_elements_local_send = rsd + lss 2083 total_elements_local_send = rsd + lss
2083 cost_local_full_sync = avg_es * total_elements_local_send 2084 cost_local_full_sync = avg_es * total_elements_local_send
2084 + total_elements_local_send * sizeof(ELEMENT_MSG_HEADER) 2085 + total_elements_local_send * semh
2085 + sizeof(FULL_DONE_MSG_HEADER) * 2 2086 + sizeof(FULL_DONE_MSG_HEADER) * 2
2086 + RTT_MIN_FULL * rtt 2087 + RTT_MIN_FULL * rtt
2087 2088
2088 # Estimate required transferred bytes when doing a full synchronisation 2089 # Estimate required transferred bytes when doing a full
2089 # and transmitting remote set first. 2090 # synchronisation and transmitting remote set first.
2090 total_elements_remote_send = lsd + rss 2091 total_elements_remote_send = lsd + rss
2091 cost_remote_full_sync = avg_es * total_elements_remote_send 2092 cost_remote_full_sync = avg_es * total_elements_remote_send
2092 + total_elements_remote_send * sizeof(ELEMENT_MSG_HEADER) 2093 + total_elements_remote_send * semh
2093 + sizeof(FULL_DONE_MSG_HEADER) * 2 2094 + sizeof(FULL_DONE_MSG_HEADER) * 2
2094 + (RTT_MIN_FULL + 0.5) * rtt 2095 + (RTT_MIN_FULL + 0.5) * rtt
2095 + sizeof(REQUEST_FULL_MSG) 2096 + sizeof(REQUEST_FULL_MSG)
2096 2097
2097 # Estimate required transferred bytes when doing a differential synchronisation 2098 # Estimate required transferred bytes when doing a differential
2099 # synchronisation
2098 2100
2099 # Estimate messages required to transfer IBF 2101 # Estimate messages required to transfer IBF
2100 ibf_bucket_count = estimated_total_diff * IBF_BUCKET_NUMBER_FACTOR 2102 ibf_bucket_count = estimated_total_diff * IBF_BUCKET_NUMBER_FACTOR
@@ -2165,7 +2167,8 @@ END FUNCTION
2165 <figure anchor="performance_formula_ibf_parameters_code"> 2167 <figure anchor="performance_formula_ibf_parameters_code">
2166 <artwork name="" type="" align="left" alt=""><![CDATA[ 2168 <artwork name="" type="" align="left" alt=""><![CDATA[
2167# CONSTANTS: 2169# CONSTANTS:
2168# IBF_BUCKET_NUMBER_FACTOR = 2: The amount the IBF gets increased if decoding fails 2170# IBF_BUCKET_NUMBER_FACTOR = 2: The amount the IBF gets increased
2171 if decoding fails
2169# Inputs: 2172# Inputs:
2170# sd: Estimated set difference 2173# sd: Estimated set difference
2171# Output: 2174# Output:
@@ -2253,22 +2256,23 @@ FUNCTION ibf_get_max_counter(ibf)
2253 max_counter = bucket.counter 2256 max_counter = bucket.counter
2254 END IF 2257 END IF
2255 END FOR 2258 END FOR
2256 # next bigger discrete number of the binary logarithm of the max counter 2259 # next bigger discrete number of the binary logarithm of the
2260 # max counter
2257 RETURN CEILING( LOG2( max_counter ) ) 2261 RETURN CEILING( LOG2( max_counter ) )
2258END FUNCTION 2262END FUNCTION
2259 2263
2260# INPUTS: 2264# INPUTS:
2261# ibf: The IBF 2265# ibf: The IBF
2262# offset: The offset which defines the starting point from which bucket the 2266# offset: The offset which defines the starting point from which bucket
2263# pack operation starts 2267# the pack operation starts
2264# count: The number of buckets in the array that will be packed 2268# count: The number of buckets in the array that will be packed
2265# OUTPUTS: 2269# OUTPUTS:
2266# returns: A byte array of packed counters to send over the network 2270# returns: A byte array of packed counters to send over the network
2267 2271
2268# INPUTS: 2272# INPUTS:
2269# ibf: The IBF 2273# ibf: The IBF
2270# offset: The offset which defines the starting point from which bucket the 2274# offset: The offset which defines the starting point from which bucket
2271# pack operation starts 2275# the pack operation starts
2272# count: The number of buckets in the array that will be packed 2276# count: The number of buckets in the array that will be packed
2273# OUTPUTS: 2277# OUTPUTS:
2274# returns: A byte array of packed counters to send over the network 2278# returns: A byte array of packed counters to send over the network
@@ -2278,7 +2282,7 @@ FUNCTION pack_counter(ibf, offset, count)
2278 store_bits = 0 2282 store_bits = 0
2279 store = 0 2283 store = 0
2280 byte_ctr = 0 2284 byte_ctr = 0
2281 buffer=[] 2285 buf=[]
2282 2286
2283 FOR bucket IN ibf[offset] TO ibf[count] DO 2287 FOR bucket IN ibf[offset] TO ibf[count] DO
2284 counter = bucket.counter 2288 counter = bucket.counter
@@ -2292,7 +2296,7 @@ FUNCTION pack_counter(ibf, offset, count)
2292 bit_to_shift = byte_len - bit_free 2296 bit_to_shift = byte_len - bit_free
2293 store = store << bit_free 2297 store = store << bit_free
2294 END IF 2298 END IF
2295 buffer[byte_ctr] = (( counter >> bit_to_shift) | store) & 0xFF 2299 buf[byte_ctr] = (( counter >> bit_to_shift) | store) & 0xFF
2296 byte_ctr = byte_ctr + 1 2300 byte_ctr = byte_ctr + 1
2297 byte_len -= 8 - store_bits 2301 byte_len -= 8 - store_bits
2298 counter = counter & ((1 << byte_len) - 1) 2302 counter = counter & ((1 << byte_len) - 1)
@@ -2306,24 +2310,25 @@ FUNCTION pack_counter(ibf, offset, count)
2306 2310
2307 # Write the last partial packed byte to the buffer 2311 # Write the last partial packed byte to the buffer
2308 IF store_bits > 0 THEN 2312 IF store_bits > 0 THEN
2309 buffer[byte_ctr] = store << (8 - store_bits) 2313 buf[byte_ctr] = store << (8 - store_bits)
2310 byte_ctr = byte_ctr + 1 2314 byte_ctr = byte_ctr + 1
2311 END IF 2315 END IF
2312 2316
2313 RETURN buffer 2317 RETURN buf
2314FUNCTION END 2318FUNCTION END
2315 2319
2316# INPUTS: 2320# INPUTS:
2317# ibf: The IBF 2321# ibf: The IBF
2318# offset: The offset which defines the starting point from which bucket 2322# offset: The offset which defines the starting point from which bucket
2319 the packed operation starts 2323 the packed operation starts
2320# count: The number of buckets in the array that will be packed 2324# count: The number of buckets in the array that will be packed
2321# cbl: The bit length of the counter can be found in the 2325# cbl: The bit length of the counter can be found in the
2322 ibf message in the ibf_counter_bit_length field 2326 ibf message in the ibf_counter_bit_length field
2323# pd: A byte array which contains the data packed with the pack_counter 2327# pd: A byte array which contains the data packed with the pack_counter
2324 function 2328 function
2325# OUTPUTS: 2329# OUTPUTS:
2326# returns: Nothing because the unpacked counter is saved directly into the IBF 2330# returns: Nothing because the unpacked counter is saved directly
2331 into the IBF
2327 2332
2328FUNCTION unpack_counter(ibf, offset, count, cbl, pd) 2333FUNCTION unpack_counter(ibf, offset, count, cbl, pd)
2329 ibf_bucket_ctr = 0 2334 ibf_bucket_ctr = 0
@@ -2332,7 +2337,7 @@ FUNCTION unpack_counter(ibf, offset, count, cbl, pd)
2332 byte_ctr = 0 2337 byte_ctr = 0
2333 2338
2334 WHILE TRUE 2339 WHILE TRUE
2335 byte_to_read = pd[byte_ctr] 2340 byte_read = pd[byte_ctr]
2336 bit_to_pack_left = 8 2341 bit_to_pack_left = 8
2337 byte_ctr++ 2342 byte_ctr++
2338 2343
@@ -2350,10 +2355,10 @@ FUNCTION unpack_counter(ibf, offset, count, cbl, pd)
2350 store = store << bit_use 2355 store = store << bit_use
2351 END IF 2356 END IF
2352 bytes_to_shift = bit_to_pack_left - bit_use 2357 bytes_to_shift = bit_to_pack_left - bit_use
2353 counter_partial = byte_to_read >> bytes_to_shift 2358 counter_partial = byte_read >> bytes_to_shift
2354 store = store | counter_partial 2359 store = store | counter_partial
2355 ibf.counter[ibf_bucket_ctr + offset] = store 2360 ibf.counter[ibf_bucket_ctr + offset] = store
2356 byte_to_read = byte_to_read & (( 1 << bytes_to_shift ) - 1) 2361 byte_read = byte_read & (( 1 << bytes_to_shift ) - 1)
2357 2362
2358 bit_to_pack_left -= bit_use 2363 bit_to_pack_left -= bit_use
2359 ibf_bucket_ctr++ 2364 ibf_bucket_ctr++
@@ -2363,10 +2368,10 @@ FUNCTION unpack_counter(ibf, offset, count, cbl, pd)
2363 store_bits = store_bits + bit_to_pack_left 2368 store_bits = store_bits + bit_to_pack_left
2364 2369
2365 IF 0 == store_bits THEN 2370 IF 0 == store_bits THEN
2366 store = byte_to_read 2371 store = byte_read
2367 ELSE 2372 ELSE
2368 store = store << bit_to_pack_left 2373 store = store << bit_to_pack_left
2369 store = store | byte_to_read 2374 store = store | byte_read
2370 END IF 2375 END IF
2371 BREAK 2376 BREAK
2372 END IF 2377 END IF
@@ -2408,7 +2413,8 @@ END FUNCTION
2408 2413
2409# Inputs: 2414# Inputs:
2410# value: Input value to salt (needs to be 64 bit unsigned) 2415# value: Input value to salt (needs to be 64 bit unsigned)
2411# salt: Salt to salt value with; Should always be ascending and start at zero 2416# salt: Salt to salt value with; Should always be ascending and start
2417# at zero
2412 i.e. SE1 = Salt 0; SE2 = Salt 1 etc. 2418 i.e. SE1 = Salt 0; SE2 = Salt 1 etc.
2413# Output: 2419# Output:
2414# Returns: Salted value 2420# Returns: Salted value
@@ -2531,15 +2537,20 @@ END FUNCTION
2531 <artwork name="" type="" align="left" alt=""><![CDATA[ 2537 <artwork name="" type="" align="left" alt=""><![CDATA[
2532 2538
2533 2539
2534Chain for elements +---------+ +---------+ +---------+ +---------+ 2540Chain for
2535NOT in IBF decoding | INQUIRY | ---> | OFFER | ===> | DEMAND | ===> | ELEMENT | 2541elements +---------+ +---------+ +---------+ +---------+
2536peers set +---------+ +---------+ +---------+ +---------+ 2542NOT in IBF | INQUIRY |--->| OFFER |===>| DEMAND |===>| ELEMENT |
2543decoding +---------+ +---------+ +---------+ +---------+
2544peers set
2545
2546Chain for
2547elements +---------+ +---------+ +---------+
2548in IBF | OFFER |--->| DEMAND |===>| ELEMENT |
2549decoding +---------+ +---------+ +---------+
2550peers set
2537 2551
2538Chain for elements +---------+ +---------+ +---------+ 2552 --->: Answer not mandatory
2539in IBF decoding | OFFER | ---> | DEMAND | ===> | ELEMENT | 2553 ===>: Always answer needed.
2540peers set +---------+ +---------+ +---------+
2541 --->: Answer not mandatory
2542 ===>: Always answer needed.
2543 ]]></artwork> 2554 ]]></artwork>
2544 </figure> 2555 </figure>
2545 <t> 2556 <t>
@@ -3029,33 +3040,44 @@ END FUNCTION
3029 <figure anchor="figure_constants"> 3040 <figure anchor="figure_constants">
3030 <artwork name="" type="" align="left" alt=""><![CDATA[ 3041 <artwork name="" type="" align="left" alt=""><![CDATA[
3031Name | Value | Description 3042Name | Value | Description
3032----------------------------+------------+-------------------------- 3043----------------------------+------------+-------------------------------
3033SE_STRATA_COUNT | 32 | Number of IBFs in a strata estimator 3044SE_STRATA_COUNT | 32 | Number of IBFs in a strata
3034IBF_HASH_NUM* | 3 | Number of times an element is hashed to an 3045 estimator.
3035 IBF (from section 4.5.2) 3046IBF_HASH_NUM* | 3 | Number of times an element is
3036IBF_FACTOR* | 2 | The factor by which the size of the IBF is 3047 hashed to an IBF.
3037 increased in case of decoding failure or
3038 initially from the set difference.
3039 (from section 4.5.2) 3048 (from section 4.5.2)
3040MAX_BUCKETS_PER_MESSAGE | 1120 | Maximum bucket of an IBF that are 3049IBF_FACTOR* | 2 | The factor by which the size
3041 transmitted in single message 3050 of the IBF is increased in
3042IBF_MIN_SIZE* | 37 | Minimal number of buckets in an IBF 3051 case of decoding failure or
3043 (from section 3.8) 3052 initially from the set
3044DIFFERENTIAL_RTT_MEAN* | 3.65145 | The average RTT that is needed for a 3053 difference.
3054 (from section 4.5.2)
3055MAX_BUCKETS_PER_MESSAGE | 1120 | Maximum bucket of an IBF
3056 that are transmitted in
3057 single message.
3058IBF_MIN_SIZE* | 37 | Minimal number of buckets
3059 in an IBF. (from section 3.8)
3060DIFFERENTIAL_RTT_MEAN* | 3.65145 | The average RTT that is
3061 needed for a differential
3062 synchronisation.
3063SECURITY_LEVEL* | 2^80 | Security level for
3064 probabilistic security
3065 algorithms. (from section 5.8)
3066PROBABILITY_FOR_NEW_ROUND* | 0.15 | The probability for a IBF
3067 decoding failure in the
3045 differential synchronisation 3068 differential synchronisation
3046SECURITY_LEVEL* | 2^80 | Security level for probabilistic security 3069 mode. (from section 5.4)
3047 algorithms (from section 5.8) 3070DIFFERENTIAL_RTT_MEAN* | 3.65145 | The average RTT that is needed
3048PROBABILITY_FOR_NEW_ROUND* | 0.15 | The probability for a IBF decoding failure 3071 for a differential
3049 in the differential synchronisation mode 3072 synchronisation.
3050 (from section 5.4)
3051DIFFERENTIAL_RTT_MEAN* | 3.65145 | The average RTT that is needed for a
3052 differential synchronisation.
3053 (from section 4.5.3) 3073 (from section 4.5.3)
3054MAX_IBF_SIZE | 1048576 | Maximal number of buckets in an IBF 3074MAX_IBF_SIZE | 1048576 | Maximal number of buckets in
3055AVG_BYTE_SIZE_SE* | 4221 | Average byte size of a single strata 3075 an IBF.
3056 estimator (from section 3.4.3) 3076AVG_BYTE_SIZE_SE* | 4221 | Average byte size of a single
3057VALID_NUMBER_SE* | [1,2,4,8] | Valid number of SE in (from section 3.4) 3077 strata estimator.
3058 3078 (from section 3.4.3)
3079VALID_NUMBER_SE* | [1,2,4,8] | Valid number of SE's
3080 (from section 3.4)
3059 ]]></artwork> 3081 ]]></artwork>
3060 </figure> 3082 </figure>
3061 3083
@@ -3069,29 +3091,43 @@ VALID_NUMBER_SE* | [1,2,4,8] | Valid number of SE in (from section 3
3069 <figure anchor="figure_purposenums"> 3091 <figure anchor="figure_purposenums">
3070 <artwork name="" type="" align="left" alt=""><![CDATA[ 3092 <artwork name="" type="" align="left" alt=""><![CDATA[
3071Type | Name | References | Description 3093Type | Name | References | Description
3072--------+----------------------------+------------+----------------------------------- 3094--------+----------------------------+------------+----------------------
3073 559 | SETU_P2P_REQUEST_FULL | [This.I-D] | Request the full set of the other 3095 559 | SETU_P2P_REQUEST_FULL | [This.I-D] | Request the full set
3074 peer 3096 of the other peer.
3075 710 | SETU_P2P_SEND_FULL | [This.I-D] | Signals to send the full set to the 3097 710 | SETU_P2P_SEND_FULL | [This.I-D] | Signals to send the
3076 other peer 3098 full set to the other
3077 560 | SETU_P2P_DEMAND | [This.I-D] | Demand the whole element from the 3099 peer.
3078 other peer, given only the hash 3100 560 | SETU_P2P_DEMAND | [This.I-D] | Demand the whole
3079 code. 3101 element from the
3080 561 | SETU_P2P_INQUIRY | [This.I-D] | Tell the other peer to send a list 3102 otherpeer, given
3081 of hashes that match an IBF key. 3103 only the hash code.
3082 562 | SETU_P2P_OFFER | [This.I-D] | Tell the other peer which hashes 3104 561 | SETU_P2P_INQUIRY | [This.I-D] | Tell the other peer
3083 match a given IBF key. 3105 to send a list of
3084 563 | SETU_P2P_OPERATION_REQUEST | [This.I-D] | Request a set union operation from 3106 hashes that match
3085 a remote peer. 3107 an IBF key.
3086 564 | SETU_P2P_SE | [This.I-D] | Strata Estimator uncompressed 3108 562 | SETU_P2P_OFFER | [This.I-D] | Tell the other peer
3087 565 | SETU_P2P_IBF | [This.I-D] | Invertible Bloom Filter slices. 3109 which hashes match
3110 a given IBF key.
3111 563 | SETU_P2P_OPERATION_REQUEST | [This.I-D] | Request a set union
3112 operation from a
3113 remote peer.
3114 564 | SETU_P2P_SE | [This.I-D] | Strata Estimator
3115 uncompressed.
3116 565 | SETU_P2P_IBF | [This.I-D] | Invertible Bloom
3117 Filter slices.
3088 566 | SETU_P2P_ELEMENTS | [This.I-D] | Actual set elements. 3118 566 | SETU_P2P_ELEMENTS | [This.I-D] | Actual set elements.
3089 567 | SETU_P2P_IBF_LAST | [This.I-D] | Invertible Bloom Filter Last Slice. 3119 567 | SETU_P2P_IBF_LAST | [This.I-D] | Invertible Bloom
3090 568 | SETU_P2P_DONE | [This.I-D] | Set operation is done. 3120 Filter Last Slices.
3091 569 | SETU_P2P_SEC | [This.I-D] | Strata Estimator compressed 3121 568 | SETU_P2P_DONE | [This.I-D] | Set operation is
3092 570 | SETU_P2P_FULL_DONE | [This.I-D] | All elements in full synchronisation 3122 done.
3093 mode have been sent is done. 3123 569 | SETU_P2P_SEC | [This.I-D] | Strata Estimator
3094 571 | SETU_P2P_FULL_ELEMENT | [This.I-D] | Send an actual element in full 3124 compressed.
3125 570 | SETU_P2P_FULL_DONE | [This.I-D] | All elements in
3126 full synchronisation
3127 mode have been sent
3128 is done.
3129 571 | SETU_P2P_FULL_ELEMENT | [This.I-D] | Send an actual
3130 element in full
3095 synchronisation mode. 3131 synchronisation mode.
3096 3132
3097 ]]></artwork> 3133 ]]></artwork>
diff --git a/draft-summermatter-set-union.xml b/draft-summermatter-set-union.xml
index 3548fa9..98b2a3b 100644
--- a/draft-summermatter-set-union.xml
+++ b/draft-summermatter-set-union.xml
@@ -2044,10 +2044,12 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
2044 <figure anchor="performance_formulas_operationmode_code"> 2044 <figure anchor="performance_formulas_operationmode_code">
2045 <artwork name="" type="" align="left" alt=""><![CDATA[ 2045 <artwork name="" type="" align="left" alt=""><![CDATA[
2046# CONSTANTS: 2046# CONSTANTS:
2047# IBF_BUCKET_NUMBER_FACTOR = 2: The amount the IBF gets increased if decoding fails 2047# IBF_BUCKET_NUMBER_FACTOR = 2: The amount the IBF gets increased if
2048# RTT_MIN_FULL = 2: Minimal round trips used for full syncronisation (always 2 or 2.5) 2048# decoding fails
2049# RTT_MIN_FULL = 2: Minimal round trips used for full Synchronisation
2049# IBF_MIN_SIZE = 37: The minimal size of an IBF 2050# IBF_MIN_SIZE = 37: The minimal size of an IBF
2050# MAX_BUCKETS_PER_MESSAGE: Custom value depending on the underlying protocol 2051# MAX_BUCKETS_PER_MESSAGE: Custom value depending on the underlying
2052# protocol
2051# INPUTS: 2053# INPUTS:
2052# avg_es: The average element size 2054# avg_es: The average element size
2053# lss: The initial local set size 2055# lss: The initial local set size
@@ -2056,7 +2058,8 @@ hashSum | 0x0101 | 0x5151 | 0x5050 | 0x0000 |
2056# rsd: the estimated remote set difference calculated by the SE 2058# rsd: the estimated remote set difference calculated by the SE
2057# rtt: the tradeoff between round trips and bandwidth 2059# rtt: the tradeoff between round trips and bandwidth
2058# OUTPUT: 2060# OUTPUT:
2059# FULL_SYNC_REMOTE_SENDING_FIRST, FULL_SYNC_LOCAL_SENDING_FIRST or DIFFERENTIAL_SYNC 2061# FULL_SYNC_REMOTE_SENDING_FIRST, FULL_SYNC_LOCAL_SENDING_FIRST or
2062# DIFFERENTIAL_SYNC
2060 2063
2061FUNCTION decide_operation_mode(avg_es, 2064FUNCTION decide_operation_mode(avg_es,
2062 lss, 2065 lss,
@@ -2066,11 +2069,6 @@ FUNCTION decide_operation_mode(avg_es,
2066 rtt) 2069 rtt)
2067 2070
2068 # If a set size is zero always do full sync 2071 # If a set size is zero always do full sync
2069 # TODO: check if these two conditions are
2070 # actually meaningful, I suspect even without
2071 # this check at the beginning the logic below
2072 # should always yield the same result for these
2073 # extreme cases, allowing us to omit this code.
2074 IF 0 == rss THEN 2072 IF 0 == rss THEN
2075 RETURN FULL_SYNC_LOCAL_SENDING_FIRST 2073 RETURN FULL_SYNC_LOCAL_SENDING_FIRST
2076 END IF 2074 END IF
@@ -2078,25 +2076,27 @@ FUNCTION decide_operation_mode(avg_es,
2078 RETURN FULL_SYNC_REMOTE_SENDING_FIRST 2076 RETURN FULL_SYNC_REMOTE_SENDING_FIRST
2079 END IF 2077 END IF
2080 2078
2081 # Estimate required transferred bytes when doing a full synchronisation 2079 # Estimate required transferred bytes when doing a full
2082 # and transmitting local set first. 2080 # synchronisation and transmitting local set first.
2081 semh = sizeof(ELEMENT_MSG_HEADER)
2083 estimated_total_diff = rsd + lsd 2082 estimated_total_diff = rsd + lsd
2084 total_elements_local_send = rsd + lss 2083 total_elements_local_send = rsd + lss
2085 cost_local_full_sync = avg_es * total_elements_local_send 2084 cost_local_full_sync = avg_es * total_elements_local_send
2086 + total_elements_local_send * sizeof(ELEMENT_MSG_HEADER) 2085 + total_elements_local_send * semh
2087 + sizeof(FULL_DONE_MSG_HEADER) * 2 2086 + sizeof(FULL_DONE_MSG_HEADER) * 2
2088 + RTT_MIN_FULL * rtt 2087 + RTT_MIN_FULL * rtt
2089 2088
2090 # Estimate required transferred bytes when doing a full synchronisation 2089 # Estimate required transferred bytes when doing a full
2091 # and transmitting remote set first. 2090 # synchronisation and transmitting remote set first.
2092 total_elements_remote_send = lsd + rss 2091 total_elements_remote_send = lsd + rss
2093 cost_remote_full_sync = avg_es * total_elements_remote_send 2092 cost_remote_full_sync = avg_es * total_elements_remote_send
2094 + total_elements_remote_send * sizeof(ELEMENT_MSG_HEADER) 2093 + total_elements_remote_send * semh
2095 + sizeof(FULL_DONE_MSG_HEADER) * 2 2094 + sizeof(FULL_DONE_MSG_HEADER) * 2
2096 + (RTT_MIN_FULL + 0.5) * rtt 2095 + (RTT_MIN_FULL + 0.5) * rtt
2097 + sizeof(REQUEST_FULL_MSG) 2096 + sizeof(REQUEST_FULL_MSG)
2098 2097
2099 # Estimate required transferred bytes when doing a differential synchronisation 2098 # Estimate required transferred bytes when doing a differential
2099 # synchronisation
2100 2100
2101 # Estimate messages required to transfer IBF 2101 # Estimate messages required to transfer IBF
2102 ibf_bucket_count = estimated_total_diff * IBF_BUCKET_NUMBER_FACTOR 2102 ibf_bucket_count = estimated_total_diff * IBF_BUCKET_NUMBER_FACTOR
@@ -2167,7 +2167,8 @@ END FUNCTION
2167 <figure anchor="performance_formula_ibf_parameters_code"> 2167 <figure anchor="performance_formula_ibf_parameters_code">
2168 <artwork name="" type="" align="left" alt=""><![CDATA[ 2168 <artwork name="" type="" align="left" alt=""><![CDATA[
2169# CONSTANTS: 2169# CONSTANTS:
2170# IBF_BUCKET_NUMBER_FACTOR = 2: The amount the IBF gets increased if decoding fails 2170# IBF_BUCKET_NUMBER_FACTOR = 2: The amount the IBF gets increased
2171 if decoding fails
2171# Inputs: 2172# Inputs:
2172# sd: Estimated set difference 2173# sd: Estimated set difference
2173# Output: 2174# Output:
@@ -2319,14 +2320,15 @@ FUNCTION END
2319# INPUTS: 2320# INPUTS:
2320# ibf: The IBF 2321# ibf: The IBF
2321# offset: The offset which defines the starting point from which bucket 2322# offset: The offset which defines the starting point from which bucket
2322 the packed operation starts 2323 the packed operation starts
2323# count: The number of buckets in the array that will be packed 2324# count: The number of buckets in the array that will be packed
2324# cbl: The bit length of the counter can be found in the 2325# cbl: The bit length of the counter can be found in the
2325 ibf message in the ibf_counter_bit_length field 2326 ibf message in the ibf_counter_bit_length field
2326# pd: A byte array which contains the data packed with the pack_counter 2327# pd: A byte array which contains the data packed with the pack_counter
2327 function 2328 function
2328# OUTPUTS: 2329# OUTPUTS:
2329# returns: Nothing because the unpacked counter is saved directly into the IBF 2330# returns: Nothing because the unpacked counter is saved directly
2331 into the IBF
2330 2332
2331FUNCTION unpack_counter(ibf, offset, count, cbl, pd) 2333FUNCTION unpack_counter(ibf, offset, count, cbl, pd)
2332 ibf_bucket_ctr = 0 2334 ibf_bucket_ctr = 0
@@ -3096,9 +3098,9 @@ Type | Name | References | Description
3096 full set to the other 3098 full set to the other
3097 peer. 3099 peer.
3098 560 | SETU_P2P_DEMAND | [This.I-D] | Demand the whole 3100 560 | SETU_P2P_DEMAND | [This.I-D] | Demand the whole
3099 element from the other 3101 element from the
3100 peer, given only the 3102 otherpeer, given
3101 hash code. 3103 only the hash code.
3102 561 | SETU_P2P_INQUIRY | [This.I-D] | Tell the other peer 3104 561 | SETU_P2P_INQUIRY | [This.I-D] | Tell the other peer
3103 to send a list of 3105 to send a list of
3104 hashes that match 3106 hashes that match