diff options
author | Julius Bünger <buenger@mytum.de> | 2018-04-08 23:49:45 +0200 |
---|---|---|
committer | Julius Bünger <buenger@mytum.de> | 2018-04-08 23:50:24 +0200 |
commit | 4309ab299a58f07d9624a170219672f49a8db459 (patch) | |
tree | 0e99506adb87f3bf790d686a7c36098670ae8ebe /src/rps/test_rps.c | |
parent | e0d9869415af5a5752e3b27ea14b249a52ac9877 (diff) | |
download | gnunet-4309ab299a58f07d9624a170219672f49a8db459.tar.gz gnunet-4309ab299a58f07d9624a170219672f49a8db459.zip |
rps profiler: log probabilities of selecting peer
Diffstat (limited to 'src/rps/test_rps.c')
-rw-r--r-- | src/rps/test_rps.c | 190 |
1 files changed, 179 insertions, 11 deletions
diff --git a/src/rps/test_rps.c b/src/rps/test_rps.c index 6ee665ad5..4c10133d2 100644 --- a/src/rps/test_rps.c +++ b/src/rps/test_rps.c | |||
@@ -257,7 +257,12 @@ struct RPSPeer | |||
257 | /** | 257 | /** |
258 | * @brief File name of the file the stats are finally written to | 258 | * @brief File name of the file the stats are finally written to |
259 | */ | 259 | */ |
260 | char *file_name_stats; | 260 | const char *file_name_stats; |
261 | |||
262 | /** | ||
263 | * @brief File name of the file the stats are finally written to | ||
264 | */ | ||
265 | const char *file_name_probs; | ||
261 | 266 | ||
262 | /** | 267 | /** |
263 | * @brief The current view | 268 | * @brief The current view |
@@ -1823,20 +1828,26 @@ static int ensure_folder_exist (void) | |||
1823 | return GNUNET_YES; | 1828 | return GNUNET_YES; |
1824 | } | 1829 | } |
1825 | 1830 | ||
1826 | static void | 1831 | static const char * |
1827 | store_stats_file_name (struct RPSPeer *rps_peer) | 1832 | store_prefix_file_name (struct RPSPeer *rps_peer, const char *prefix) |
1828 | { | 1833 | { |
1829 | unsigned int len_file_name; | 1834 | unsigned int len_file_name; |
1830 | unsigned int out_size; | 1835 | unsigned int out_size; |
1831 | char *file_name; | 1836 | char *file_name; |
1832 | 1837 | const char *pid_long; | |
1833 | if (GNUNET_SYSERR == ensure_folder_exist()) return; | 1838 | |
1834 | len_file_name = (14 + strlen (GNUNET_i2s_full (rps_peer->peer_id)) + 1) * sizeof (char); | 1839 | if (GNUNET_SYSERR == ensure_folder_exist()) return NULL; |
1840 | pid_long = GNUNET_i2s_full (rps_peer->peer_id); | ||
1841 | len_file_name = (strlen (prefix) + | ||
1842 | strlen (pid_long) + | ||
1843 | 11) | ||
1844 | * sizeof (char); | ||
1835 | file_name = GNUNET_malloc (len_file_name); | 1845 | file_name = GNUNET_malloc (len_file_name); |
1836 | out_size = GNUNET_snprintf (file_name, | 1846 | out_size = GNUNET_snprintf (file_name, |
1837 | len_file_name, | 1847 | len_file_name, |
1838 | "/tmp/rps/stat-%s", | 1848 | "/tmp/rps/%s-%s", |
1839 | GNUNET_i2s_full (rps_peer->peer_id)); | 1849 | prefix, |
1850 | pid_long); | ||
1840 | if (len_file_name < out_size || | 1851 | if (len_file_name < out_size || |
1841 | 0 > out_size) | 1852 | 0 > out_size) |
1842 | { | 1853 | { |
@@ -1845,7 +1856,161 @@ store_stats_file_name (struct RPSPeer *rps_peer) | |||
1845 | len_file_name, | 1856 | len_file_name, |
1846 | out_size); | 1857 | out_size); |
1847 | } | 1858 | } |
1848 | rps_peer->file_name_stats = file_name; | 1859 | return file_name; |
1860 | } | ||
1861 | |||
1862 | static uint32_t fac (uint32_t x) | ||
1863 | { | ||
1864 | if (1 >= x) | ||
1865 | { | ||
1866 | return x; | ||
1867 | } | ||
1868 | return x * fac (x - 1); | ||
1869 | } | ||
1870 | |||
1871 | static uint32_t binom (uint32_t n, uint32_t k) | ||
1872 | { | ||
1873 | GNUNET_assert (n >= k); | ||
1874 | if (0 == k) return 1; | ||
1875 | return fac (n) | ||
1876 | / | ||
1877 | fac(k) * fac(n - k); | ||
1878 | } | ||
1879 | |||
1880 | /** | ||
1881 | * @brief is b in view of a? | ||
1882 | * | ||
1883 | * @param a | ||
1884 | * @param b | ||
1885 | * | ||
1886 | * @return | ||
1887 | */ | ||
1888 | static int is_in_view (uint32_t a, uint32_t b) | ||
1889 | { | ||
1890 | uint32_t i; | ||
1891 | for (i = 0; i < rps_peers[a].cur_view_count; i++) | ||
1892 | { | ||
1893 | if (0 == memcmp (rps_peers[b].peer_id, | ||
1894 | &rps_peers[a].cur_view[i], | ||
1895 | sizeof (struct GNUNET_PeerIdentity))) | ||
1896 | { | ||
1897 | return GNUNET_YES; | ||
1898 | } | ||
1899 | } | ||
1900 | return GNUNET_NO; | ||
1901 | } | ||
1902 | |||
1903 | static uint32_t get_idx_of_pid (const struct GNUNET_PeerIdentity *pid) | ||
1904 | { | ||
1905 | uint32_t i; | ||
1906 | |||
1907 | for (i = 0; i < num_peers; i++) | ||
1908 | { | ||
1909 | if (0 == memcmp (pid, | ||
1910 | rps_peers[i].peer_id, | ||
1911 | sizeof (struct GNUNET_PeerIdentity))) | ||
1912 | { | ||
1913 | return i; | ||
1914 | } | ||
1915 | } | ||
1916 | //return 0; /* Should not happen - make compiler happy */ | ||
1917 | GNUNET_assert (0); | ||
1918 | } | ||
1919 | |||
1920 | /** | ||
1921 | * @brief Counts number of peers in view of a that have b in their view | ||
1922 | * | ||
1923 | * @param a | ||
1924 | * @param uint32_tb | ||
1925 | * | ||
1926 | * @return | ||
1927 | */ | ||
1928 | static uint32_t count_containing_views (uint32_t a, uint32_t b) | ||
1929 | { | ||
1930 | uint32_t i; | ||
1931 | uint32_t peer_idx; | ||
1932 | uint32_t count = 0; | ||
1933 | |||
1934 | for (i = 0; i < rps_peers[a].cur_view_count; i++) | ||
1935 | { | ||
1936 | peer_idx = get_idx_of_pid (&rps_peers[a].cur_view[i]); | ||
1937 | if (GNUNET_YES == is_in_view (peer_idx, b)) | ||
1938 | { | ||
1939 | count++; | ||
1940 | } | ||
1941 | } | ||
1942 | return count; | ||
1943 | } | ||
1944 | |||
1945 | /** | ||
1946 | * @brief Computes the probability for each other peer to be selected by the | ||
1947 | * sampling process based on the views of all peers | ||
1948 | * | ||
1949 | * @param peer_idx index of the peer that is about to sample | ||
1950 | */ | ||
1951 | static void compute_probabilities (uint32_t peer_idx) | ||
1952 | { | ||
1953 | //double probs[num_peers] = { 0 }; | ||
1954 | double probs[num_peers]; | ||
1955 | size_t probs_as_str_size = (num_peers * 6 + 1) * sizeof (char); | ||
1956 | char *probs_as_str = GNUNET_malloc (probs_as_str_size); | ||
1957 | char *probs_as_str_cpy; | ||
1958 | uint32_t i; | ||
1959 | double prob_push; | ||
1960 | double prob_pull; | ||
1961 | uint32_t view_size; | ||
1962 | uint32_t cont_views; | ||
1963 | int tmp; | ||
1964 | uint32_t count_non_zero_prob = 0; | ||
1965 | |||
1966 | /* Firstly without knowledge of old views */ | ||
1967 | for (i = 0; i < num_peers; i++) | ||
1968 | { | ||
1969 | view_size = rps_peers[i].cur_view_count; | ||
1970 | /* For peer i the probability of being sampled is | ||
1971 | * evenly distributed among all possibly observed peers. */ | ||
1972 | /* We could have observed a peer in three cases: | ||
1973 | * 1. peer sent a push | ||
1974 | * 2. peer was contained in a pull reply | ||
1975 | * 3. peer was in history (sampler) - ignored for now */ | ||
1976 | /* 1. Probability of having received a push from peer i */ | ||
1977 | if ((GNUNET_YES == is_in_view (i, peer_idx)) && | ||
1978 | (1 <= (0.45 * view_size))) | ||
1979 | { | ||
1980 | prob_push = 1.0 * binom (0.45 * view_size, 1) | ||
1981 | / | ||
1982 | binom (view_size, 0.45 * view_size); | ||
1983 | } else { | ||
1984 | prob_push = 0; | ||
1985 | } | ||
1986 | /* 2. Probability of peer i being contained in pulls */ | ||
1987 | // FIXME this computation is not yet correct | ||
1988 | view_size = rps_peers[peer_idx].cur_view_count; | ||
1989 | cont_views = count_containing_views (i, peer_idx); | ||
1990 | prob_pull = 1.0 - | ||
1991 | (1.0 / binom (view_size, 0.45 * view_size)); | ||
1992 | probs[i] = prob_push + prob_pull - (prob_push * prob_pull); | ||
1993 | |||
1994 | if (0 != probs[i]) count_non_zero_prob++; | ||
1995 | } | ||
1996 | /* normalize */ | ||
1997 | for (i = 0; i < num_peers; i++) | ||
1998 | { | ||
1999 | probs[i] = probs[i] * (1.0 / count_non_zero_prob); | ||
2000 | } | ||
2001 | /* str repr */ | ||
2002 | for (i = 0; i < num_peers; i++) | ||
2003 | { | ||
2004 | probs_as_str_cpy = GNUNET_strndup (probs_as_str, probs_as_str_size); | ||
2005 | tmp = GNUNET_snprintf (probs_as_str, | ||
2006 | probs_as_str_size, | ||
2007 | "%s %3.2f ", probs_as_str_cpy, probs[i]); | ||
2008 | GNUNET_free (probs_as_str_cpy); | ||
2009 | GNUNET_assert (0 <= tmp); | ||
2010 | } | ||
2011 | |||
2012 | to_file (rps_peers[peer_idx].file_name_probs, probs_as_str); | ||
2013 | GNUNET_free (probs_as_str); | ||
1849 | } | 2014 | } |
1850 | 2015 | ||
1851 | /** | 2016 | /** |
@@ -2015,12 +2180,14 @@ void view_update_cb (void *cls, | |||
2015 | 1.0 /view_size, /* prob of occurrence in view slot */ | 2180 | 1.0 /view_size, /* prob of occurrence in view slot */ |
2016 | (1.0/view_size) * (view_sizes/view_size) /* expected fraction of repr in views */ | 2181 | (1.0/view_size) * (view_sizes/view_size) /* expected fraction of repr in views */ |
2017 | ); | 2182 | ); |
2183 | compute_probabilities (rps_peer->index); | ||
2018 | all_views_updated_cb(); | 2184 | all_views_updated_cb(); |
2019 | } | 2185 | } |
2020 | 2186 | ||
2021 | static void | 2187 | static void |
2022 | pre_profiler (struct RPSPeer *rps_peer, struct GNUNET_RPS_Handle *h) | 2188 | pre_profiler (struct RPSPeer *rps_peer, struct GNUNET_RPS_Handle *h) |
2023 | { | 2189 | { |
2190 | rps_peer->file_name_probs = store_prefix_file_name (rps_peer, "probs"); | ||
2024 | GNUNET_RPS_view_request (h, 0, view_update_cb, rps_peer); | 2191 | GNUNET_RPS_view_request (h, 0, view_update_cb, rps_peer); |
2025 | } | 2192 | } |
2026 | 2193 | ||
@@ -2093,9 +2260,10 @@ post_test_shutdown_ready_cb (void *cls, | |||
2093 | GNUNET_TESTBED_operation_done (rps_peer->stat_op); | 2260 | GNUNET_TESTBED_operation_done (rps_peer->stat_op); |
2094 | } | 2261 | } |
2095 | 2262 | ||
2263 | write_final_stats (); | ||
2096 | if (GNUNET_YES == check_statistics_collect_completed()) | 2264 | if (GNUNET_YES == check_statistics_collect_completed()) |
2097 | { | 2265 | { |
2098 | write_final_stats (); | 2266 | //write_final_stats (); |
2099 | GNUNET_free (stat_cls); | 2267 | GNUNET_free (stat_cls); |
2100 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | 2268 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, |
2101 | "Shutting down\n"); | 2269 | "Shutting down\n"); |
@@ -2342,7 +2510,7 @@ void post_profiler (struct RPSPeer *rps_peer) | |||
2342 | stat_cls = GNUNET_malloc (sizeof (struct STATcls)); | 2510 | stat_cls = GNUNET_malloc (sizeof (struct STATcls)); |
2343 | stat_cls->rps_peer = rps_peer; | 2511 | stat_cls->rps_peer = rps_peer; |
2344 | stat_cls->stat_type = stat_type; | 2512 | stat_cls->stat_type = stat_type; |
2345 | store_stats_file_name (rps_peer); | 2513 | rps_peer->file_name_stats = store_prefix_file_name (rps_peer, "stats"); |
2346 | GNUNET_STATISTICS_get (rps_peer->stats_h, | 2514 | GNUNET_STATISTICS_get (rps_peer->stats_h, |
2347 | "rps", | 2515 | "rps", |
2348 | stat_type_2_str (stat_type), | 2516 | stat_type_2_str (stat_type), |