sssimulator / overlay.c @ 743e659d
History  View  Annotate  Download (7.5 KB)
1 
/*


2 
* This is SSSim: the Simple & Stupid Simulator

3 
*

4 
* Copyright (c) 2015 Luca Baldesi

5 
*

6 
* This is free software; see gpl3.0.txt

7 
*/

8  
9 
#include <malloc.h> 
10 
#include <math.h> 
11 
#include <string.h> 
12 
#include <stdlib.h> 
13  
14 
#include <tokens.h> 
15  
16 
#include "overlay.h" 
17 
#include "graph.h" 
18 
#include "sched.h" 
19 
#include "wuli.h" 
20  
21 
extern float netload; 
22  
23 
void overlay_matrix_optimize(struct matrix ** A, struct matrix ** x) 
24 
{ 
25 
struct matrix * s, *IDx, *IDs, *Ds, *u, *tmp, *M, *t;

26 

27 
IDx = matrix_invdiag(*x); 
28 
u = matrix_ones(1, matrix_num_rows(*A));

29 
tmp = matrix_multiply(IDx, *A); 
30 
s = matrix_multiply(u, tmp); 
31  
32 
IDs = matrix_invdiag(s); 
33 
M = matrix_multiply(tmp, IDs); 
34 
Ds = matrix_diag(s); 
35 
t = matrix_multiply(Ds, *x); 
36  
37 
matrix_destroy(&IDx); 
38 
matrix_destroy(&u); 
39 
matrix_destroy(&tmp); 
40 
matrix_destroy(&s); 
41 
matrix_destroy(&IDs); 
42 
matrix_destroy(&Ds); 
43  
44 
matrix_destroy(A); 
45 
matrix_destroy(x); 
46 
*A = M; 
47 
*x = t; 
48 
} 
49  
50 
void overlay_matrix_set_neighbourhood(const struct matrix * A,struct peer * peers, int n) 
51 
{ 
52 
matsize i, neigh_cnt = 0;

53  
54 
for(i = 0; i < matrix_num_rows(A); i++) 
55 
if (matrix_element_get(A, i, n) > 0) 
56 
neigh_cnt++; 
57  
58 
peers[n].neigh_size = neigh_cnt; 
59 
peers[n].neighbour = malloc(neigh_cnt * sizeof(struct peer *)); 
60 
peers[n].neighbour_prob = malloc(neigh_cnt * sizeof(double)); 
61  
62 
// fprintf(stderr, "[DEBUG] set neigh of %d:%p, of size %d\n", peers[n].id, &(peers[n]), neigh_cnt);

63 
neigh_cnt = 0;

64 
for(i = 0; i < matrix_num_rows(A); i++) 
65 
if (matrix_element_get(A, i, n) > 0) 
66 
{ 
67 
peers[n].neighbour[neigh_cnt] = &(peers[i]); 
68 
peers[n].neighbour_prob[neigh_cnt] = matrix_element_get(A, i, n); 
69 
// fprintf(stderr, "[DEBUG] neigh: %p, neigh_prob: %f\n", &(peers[i]), matrix_element_get(A, i, n));

70 
neigh_cnt++; 
71 
} 
72 
} 
73  
74 
void overlay_matrix_set_source(const struct matrix * A, struct peer * source, struct peer * peers, int source_id) 
75 
{ 
76 
matsize i, j, neigh_cnt = 0;

77  
78 
source>id = 1;

79 
for(i = 0; i < matrix_num_rows(A); i++) 
80 
if (matrix_element_get(A, i, source_id) > 0) 
81 
neigh_cnt++; 
82  
83 
source>neigh_size = neigh_cnt; 
84 
source>neighbour = malloc(neigh_cnt * sizeof(struct peer *)); 
85 
source>neighbour_prob = malloc(neigh_cnt * sizeof(double)); 
86  
87 
// fprintf(stderr, "[DEBUG] set neigh of %d, of size %d\n", source>id, neigh_cnt);

88 
neigh_cnt = 0;

89 
for(i = 0; i < matrix_num_rows(A); i++) 
90 
if (matrix_element_get(A, i, source_id) > 0) 
91 
{ 
92 
j = i <= source_id ? i : i  1;

93 
source>neighbour[neigh_cnt] = &(peers[j]); 
94 
source>neighbour_prob[neigh_cnt] = matrix_element_get(A, i, source_id); 
95 
// fprintf(stderr, "[DEBUG] neigh: %p, prob: %f\n", &(peers[j]), matrix_element_get(A, i, source_id));

96 
// fprintf(stderr, "[DEBUG] neigh_prob: %f\n", matrix_element_get(A, i, source_id));

97 
neigh_cnt++; 
98 
} 
99 
} 
100  
101 
struct peer * overlay_from_edgefile(const char * graphfile, int * npeers, int * neigh_size, int nchunks, int * buffer, int * playout_delay, struct peer * source) 
102 
{ 
103 
struct matrix * A, *offers;

104 
char ** inputfile;

105 
char input[200]; 
106 
uint32_t ntok; 
107 
struct peer * peers = NULL; 
108 
int n, c, source_id;

109  
110 
strcpy(input, graphfile); 
111 
inputfile = tokens_create(input, ',', &ntok);

112 
A = matrix_from_edgefile(inputfile[0]);

113 
if (A)

114 
{ 
115 
*npeers = matrix_num_rows(A); 
116 
source_id = tokens_check(inputfile, ntok, "random_source") >= 0 ? (rand() % *npeers) : 0; 
117 
matrix_make_bidir(A); 
118  
119 
matrix_stochastify(A); 
120 
if (tokens_check(inputfile, ntok, "optimize") >= 0) 
121 
{ 
122 
printf("Optimizing overlay..\n");

123 
offers = matrix_eigencentrality(A, NULL);

124 
overlay_matrix_optimize(&A, &offers); 
125 
} else

126 
if (tokens_check(inputfile, ntok, "wuli") >= 0) 
127 
{ 
128 
printf("Applying WuLi optimization...\n");

129 
offers = matrix_ones(matrix_num_rows(A), 1);

130 
overlay_matrix_wuli(&A, &offers, source_id); 
131 
} 
132 
else

133 
{ 
134 
// fprintf(stderr, "[DEBUG] uniform overlay..\n");

135 
offers = matrix_ones(matrix_num_rows(A), 1);

136 
} 
137 
matrix_shrink(&offers, source_id); 
138 
matrix_divide(offers, matrix_sum_values(offers)/((*npeers  1)*netload));

139 
// printf("Total number of offers: %f\n", matrix_sum_values(offers));

140 
tokens_destroy(&inputfile, ntok); 
141  
142 
(*npeers) = 1; // we take off one peer to be used as source 
143 
peers = malloc((*npeers) * sizeof(struct peer)); 
144 
if (peers == NULL) { 
145 
perror("MAlloc");

146 
return NULL; 
147 
} 
148 
memset(peers, 0, (*npeers) * sizeof(struct peer)); 
149  
150 
overlay_matrix_set_source(A, source, peers, source_id); 
151 
source_set(source>neighbour, source>neigh_size, source>neighbour_prob, nchunks); 
152  
153 
matrix_shrink(&A, source_id); 
154  
155 
*neigh_size = 1;

156 
*playout_delay = ilogb(2*(*npeers)1)+1; 
157 
#ifdef NO_BUFFER

158 
*buffer = nchunks; 
159 
#else

160 
if (*buffer == 0) { 
161 
*buffer = pow(2, 1 + ilogb(2*(*playout_delay)1)); 
162 
} 
163 
#endif

164 
for (n = 0; n < *npeers; n++) { 
165 
peers[n].chunks = malloc((*buffer) * sizeof(struct chunk_instance *)); 
166 
peers[n].recv_chunks = malloc((*buffer) * sizeof(struct chunk_instance *)); 
167 
peers[n].num_chunks = nchunks; 
168 
peers[n].buf_size = *buffer; 
169 
peers[n].buf_mask = peers[n].buf_size  1;

170 
for (c = 0; c < *buffer; c++) { 
171 
peers[n].chunks[c] = NULL;

172 
peers[n].recv_chunks[c] = NULL;

173 
peers[n].latest_not_needed = 1; //CACHE latest_not_needed 
174 
} 
175 
peers[n].id = n; 
176 
peers[n].offer_rate = 1.0/matrix_element_get(offers, n, 0); 
177 
//fprintf(stderr, "[DEBUG] offer_rate: %f\n", matrix_element_get(offers, n, 0));

178 
overlay_matrix_set_neighbourhood(A, peers, n); 
179 
} 
180  
181 
printf("N=%d\n", *npeers); // one is the source.. 
182 
if (trace) fprintf(trace,"\n N=%d\n", *npeers); 
183 
matrix_destroy(&A); 
184 
matrix_destroy(&offers); 
185 
} 
186 
return peers;

187 
} 
188  
189 
struct peer * overlay_from_parameters(int * npeers, int * neigh_size, int nchunks, int * buffer, int * playout_delay, struct peer * source) 
190 
{ 
191 
int n, c;

192 
struct peer * peers;

193 
printf("N=%d\n", *npeers);

194 
if (trace) fprintf(trace,"\n N=%d\n", *npeers); 
195 
peers = malloc((*npeers) * sizeof(struct peer)); 
196 
if (peers == NULL) { 
197 
perror("MAlloc");

198 
return NULL; 
199 
} 
200 
memset(peers, 0, (*npeers) * sizeof(struct peer)); 
201  
202 
*playout_delay = ilogb(2*(*npeers)1)+1; 
203 
#ifdef NO_BUFFER

204 
*buffer = nchunks; 
205 
#else

206 
if (*buffer == 0) { 
207 
*buffer = pow(2, 1 + ilogb(2*(*playout_delay)1)); 
208 
} 
209 
#endif

210 
for (n = 0; n < *npeers; n++) { 
211 
peers[n].chunks = malloc((*buffer) * sizeof(struct chunk_instance *)); 
212 
peers[n].recv_chunks = malloc((*buffer) * sizeof(struct chunk_instance *)); 
213 
peers[n].num_chunks = nchunks; 
214 
peers[n].buf_size = *buffer; 
215 
peers[n].buf_mask = peers[n].buf_size  1;

216 
for (c = 0; c < /*num_chunks*/ *buffer; c++) { 
217 
peers[n].chunks[c] = NULL;

218 
peers[n].recv_chunks[c] = NULL;

219 
peers[n].latest_not_needed = 1; //CACHE latest_not_needed 
220 
} 
221 
peers[n].id = n; 
222 
peers[n].offer_rate = 1;

223 
peers[n].neighbour = neighbourhood_generate(*neigh_size, peers, *npeers, n); 
224 
peers[n].neighbour_prob = malloc((*neigh_size) *sizeof(double)); 
225 
for(c = 0; c < *neigh_size; c++) 
226 
{ 
227 
(peers[n].neighbour_prob)[c] = 1.0/(*neigh_size); 
228 
//fprintf(stderr, "[DEBUG]: loading prob for peer %d > %f\n", peers[n].id, (peers[n].neighbour_prob)[c]);

229 
} 
230 
peers[n].neigh_size = *neigh_size; 
231 
} 
232 
source>neighbour = neighbourhood_generate(*neigh_size, peers, *npeers, 1);

233 
source>neigh_size = *neigh_size; 
234 
source>neighbour_prob = malloc((*neigh_size) *sizeof(double)); 
235 
for(c = 0; c < *neigh_size; c++) 
236 
{ 
237 
(source>neighbour_prob)[c] = 1.0/(*neigh_size); 
238 
//fprintf(stderr, "[DEBUG]: loading prob for source %d > %f\n", source>id, (source>neighbour_prob)[c]);

239 
} 
240 
source_set(source>neighbour, source>neigh_size, source>neighbour_prob, nchunks); 
241 
return peers;

242 
} 