diff options
author | Elias Summermatter <elias.summermatter@seccom.ch> | 2021-06-16 21:14:50 +0200 |
---|---|---|
committer | Elias Summermatter <elias.summermatter@seccom.ch> | 2021-06-16 21:14:50 +0200 |
commit | 32feaf1121b83e0bb9f4efa1f1e1feafbc242db2 (patch) | |
tree | 565a517063c374d0cc7661a95b5a42fc94362b3a | |
parent | aa3d59625b1cf688c268c56caaee65494996cd35 (diff) | |
download | lsd0003-32feaf1121b83e0bb9f4efa1f1e1feafbc242db2.tar.gz lsd0003-32feaf1121b83e0bb9f4efa1f1e1feafbc242db2.zip |
Fixed more line length stuff
-rw-r--r-- | draft-summermatter-set-union-01.xml | 274 | ||||
-rw-r--r-- | draft-summermatter-set-union.xml | 50 |
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 | ||
2059 | FUNCTION decide_operation_mode(avg_es, | 2064 | FUNCTION 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 ) ) |
2258 | END FUNCTION | 2262 | END 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 |
2314 | FUNCTION END | 2318 | FUNCTION 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 | ||
2328 | FUNCTION unpack_counter(ibf, offset, count, cbl, pd) | 2333 | FUNCTION 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 | ||
2534 | Chain for elements +---------+ +---------+ +---------+ +---------+ | 2540 | Chain for |
2535 | NOT in IBF decoding | INQUIRY | ---> | OFFER | ===> | DEMAND | ===> | ELEMENT | | 2541 | elements +---------+ +---------+ +---------+ +---------+ |
2536 | peers set +---------+ +---------+ +---------+ +---------+ | 2542 | NOT in IBF | INQUIRY |--->| OFFER |===>| DEMAND |===>| ELEMENT | |
2543 | decoding +---------+ +---------+ +---------+ +---------+ | ||
2544 | peers set | ||
2545 | |||
2546 | Chain for | ||
2547 | elements +---------+ +---------+ +---------+ | ||
2548 | in IBF | OFFER |--->| DEMAND |===>| ELEMENT | | ||
2549 | decoding +---------+ +---------+ +---------+ | ||
2550 | peers set | ||
2537 | 2551 | ||
2538 | Chain for elements +---------+ +---------+ +---------+ | 2552 | --->: Answer not mandatory |
2539 | in IBF decoding | OFFER | ---> | DEMAND | ===> | ELEMENT | | 2553 | ===>: Always answer needed. |
2540 | peers 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[ |
3031 | Name | Value | Description | 3042 | Name | Value | Description |
3032 | ----------------------------+------------+-------------------------- | 3043 | ----------------------------+------------+------------------------------- |
3033 | SE_STRATA_COUNT | 32 | Number of IBFs in a strata estimator | 3044 | SE_STRATA_COUNT | 32 | Number of IBFs in a strata |
3034 | IBF_HASH_NUM* | 3 | Number of times an element is hashed to an | 3045 | estimator. |
3035 | IBF (from section 4.5.2) | 3046 | IBF_HASH_NUM* | 3 | Number of times an element is |
3036 | IBF_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) |
3040 | MAX_BUCKETS_PER_MESSAGE | 1120 | Maximum bucket of an IBF that are | 3049 | IBF_FACTOR* | 2 | The factor by which the size |
3041 | transmitted in single message | 3050 | of the IBF is increased in |
3042 | IBF_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 |
3044 | DIFFERENTIAL_RTT_MEAN* | 3.65145 | The average RTT that is needed for a | 3053 | difference. |
3054 | (from section 4.5.2) | ||
3055 | MAX_BUCKETS_PER_MESSAGE | 1120 | Maximum bucket of an IBF | ||
3056 | that are transmitted in | ||
3057 | single message. | ||
3058 | IBF_MIN_SIZE* | 37 | Minimal number of buckets | ||
3059 | in an IBF. (from section 3.8) | ||
3060 | DIFFERENTIAL_RTT_MEAN* | 3.65145 | The average RTT that is | ||
3061 | needed for a differential | ||
3062 | synchronisation. | ||
3063 | SECURITY_LEVEL* | 2^80 | Security level for | ||
3064 | probabilistic security | ||
3065 | algorithms. (from section 5.8) | ||
3066 | PROBABILITY_FOR_NEW_ROUND* | 0.15 | The probability for a IBF | ||
3067 | decoding failure in the | ||
3045 | differential synchronisation | 3068 | differential synchronisation |
3046 | SECURITY_LEVEL* | 2^80 | Security level for probabilistic security | 3069 | mode. (from section 5.4) |
3047 | algorithms (from section 5.8) | 3070 | DIFFERENTIAL_RTT_MEAN* | 3.65145 | The average RTT that is needed |
3048 | PROBABILITY_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) | ||
3051 | DIFFERENTIAL_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) |
3054 | MAX_IBF_SIZE | 1048576 | Maximal number of buckets in an IBF | 3074 | MAX_IBF_SIZE | 1048576 | Maximal number of buckets in |
3055 | AVG_BYTE_SIZE_SE* | 4221 | Average byte size of a single strata | 3075 | an IBF. |
3056 | estimator (from section 3.4.3) | 3076 | AVG_BYTE_SIZE_SE* | 4221 | Average byte size of a single |
3057 | VALID_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) | |
3079 | VALID_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[ |
3071 | Type | Name | References | Description | 3093 | Type | 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 | ||
2061 | FUNCTION decide_operation_mode(avg_es, | 2064 | FUNCTION 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 | ||
2331 | FUNCTION unpack_counter(ibf, offset, count, cbl, pd) | 2333 | FUNCTION 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 |