summaryrefslogtreecommitdiff
path: root/src/rps/test_rps.c
diff options
context:
space:
mode:
authorJulius Bünger <buenger@mytum.de>2018-04-08 23:49:45 +0200
committerJulius Bünger <buenger@mytum.de>2018-04-08 23:50:24 +0200
commit4309ab299a58f07d9624a170219672f49a8db459 (patch)
tree0e99506adb87f3bf790d686a7c36098670ae8ebe /src/rps/test_rps.c
parente0d9869415af5a5752e3b27ea14b249a52ac9877 (diff)
downloadgnunet-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.c190
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
1826static void 1831static const char *
1827store_stats_file_name (struct RPSPeer *rps_peer) 1832store_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
1862static uint32_t fac (uint32_t x)
1863{
1864 if (1 >= x)
1865 {
1866 return x;
1867 }
1868 return x * fac (x - 1);
1869}
1870
1871static 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 */
1888static 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
1903static 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 */
1928static 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 */
1951static 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
2021static void 2187static void
2022pre_profiler (struct RPSPeer *rps_peer, struct GNUNET_RPS_Handle *h) 2188pre_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),