sssimulator / sched.c @ 4123e0f7
History | View | Annotate | Download (21.1 KB)
1 |
/*
|
---|---|
2 |
* This is SSSim: the Simple & Stupid Simulator
|
3 |
*
|
4 |
* Copyright (c) 2008 Luca Abeni
|
5 |
* Copyright (c) 2008 Csaba Kiraly
|
6 |
*
|
7 |
* This is free software; see gpl-3.0.txt
|
8 |
*/
|
9 |
|
10 |
#include <limits.h> |
11 |
#include <stdlib.h> |
12 |
#include <stdio.h> |
13 |
|
14 |
#include "config.h" |
15 |
#include "core.h" |
16 |
#include "sched.h" |
17 |
|
18 |
FILE *trace; //trace file
|
19 |
static struct peer source; |
20 |
|
21 |
#define SCHED __attribute__ ((unused)) static inline |
22 |
|
23 |
///==========================================================
|
24 |
/// helper functions
|
25 |
///==========================================================
|
26 |
//avoiding duplicate transactions
|
27 |
int needs(int k, const struct peer *p) |
28 |
{ |
29 |
#ifdef NO_BUFFER
|
30 |
return (!p->chunks[k] && !p->recv_chunks[k]);
|
31 |
#else
|
32 |
register unsigned int idx = k & p->buf_mask; |
33 |
|
34 |
return ((!p->chunks[idx] || (p->chunks[idx]->chunk < k)) && !p->recv_chunks[idx]);
|
35 |
#endif
|
36 |
} |
37 |
|
38 |
|
39 |
//latest chunk not needed by the given peer (owned or in arrival)
|
40 |
// it is almost a "latest chunk", but it also contains the ones in arrival
|
41 |
// we use it as a prediction for the destination node!
|
42 |
// returns: -1 if the node has no chunks, not even arriving
|
43 |
// parameters: "t" is passed only to speed up search
|
44 |
static int latest_not_needed(struct peer *p, int t) |
45 |
{ |
46 |
//CACHE latest_not_needed
|
47 |
return p->latest_not_needed;
|
48 |
} |
49 |
|
50 |
//LUCA style utility
|
51 |
static int utility(struct peer *p, int t) |
52 |
{ |
53 |
int i, c, u;
|
54 |
|
55 |
u = 0;
|
56 |
for (c = win_left(p, t); c < win_right(p, t); c++) {
|
57 |
if (p->recv_chunks[win_idx(p, c)] || p->chunks[win_idx(p, c)]) {
|
58 |
for (i = 0; i < p->neigh_size; i++) { |
59 |
u += needs(c, p->neighbour[i]); |
60 |
} |
61 |
} |
62 |
} |
63 |
|
64 |
return u;
|
65 |
} |
66 |
|
67 |
/*
|
68 |
static int utility_luca(struct peer *p)
|
69 |
{
|
70 |
int c, u;
|
71 |
|
72 |
u = 0;
|
73 |
for (c = win_left(p, t); c < win_right(p, t); c++) {
|
74 |
if (p->recv_chunks[win_idx(p, c)] || p->chunks[win_idx(p, c)]) {
|
75 |
u += N - chunks[win_idx(p, c)].received;
|
76 |
}
|
77 |
}
|
78 |
|
79 |
return u;
|
80 |
}
|
81 |
*/
|
82 |
|
83 |
//number of useful chunks owned by a peer
|
84 |
static int num_chunks(struct peer *p, int t) |
85 |
{ |
86 |
int i, tot;
|
87 |
|
88 |
tot = 0;
|
89 |
for (i = 0; i < p->num_chunks; i++) { |
90 |
if (p->chunks[i] || p->recv_chunks[i]) tot++;
|
91 |
// if (!comp(i)) tot += (p->chunks[i] != NULL);
|
92 |
// if (!comp(i)) tot += (p->recv_chunks[i] != NULL);
|
93 |
} |
94 |
|
95 |
return tot;
|
96 |
} |
97 |
|
98 |
static void order_chunks(struct chunk_instance *c[], int *ordered, int num_chunks) |
99 |
{ |
100 |
int i;
|
101 |
|
102 |
//for (i = 0; i < num_chunks; i++) chunks[i].key = (i + 1) * (chunks[i].received + 1);
|
103 |
//for (i = 0; i < num_chunks; i++) chunks[i].key = i + chunks[i].received;
|
104 |
for (i = 0; i < num_chunks; i++) { |
105 |
if (c[i]) {
|
106 |
c[i]->key = /*i + chunks[c[i]->chunk].received */ c[i]->dl;
|
107 |
//c[i]->key = i + chunks[c[i]->chunk].received;
|
108 |
//c[i]->key = num_chunks - i;
|
109 |
} |
110 |
} |
111 |
|
112 |
for (i = 0; i < num_chunks; i++) { |
113 |
int j, k, min;
|
114 |
|
115 |
min = INT_MAX; k = -1;
|
116 |
for (j = 0; j < num_chunks; j++) { |
117 |
if (c[j] && (c[j]->key >= 0) && (c[j]->key < min)) { |
118 |
min = c[j]->key; k = j; |
119 |
} |
120 |
} |
121 |
ordered[i] = k; |
122 |
if (k != -1) { |
123 |
c[k]->key = -1;
|
124 |
} |
125 |
} |
126 |
} |
127 |
|
128 |
int is_useful(int c, struct peer *p) |
129 |
{ |
130 |
int i;
|
131 |
|
132 |
for (i = 0; i < p->neigh_size; i++) { |
133 |
if (needs(c, p->neighbour[i])) {
|
134 |
return 1; |
135 |
} |
136 |
} |
137 |
|
138 |
return 0; |
139 |
} |
140 |
|
141 |
///==========================================================
|
142 |
/// chunk selection algorithms
|
143 |
///==========================================================
|
144 |
|
145 |
SCHED int ordered_sched(struct peer *p, int t, struct peer *dummy) |
146 |
{ |
147 |
int i, ii;
|
148 |
int ordered_chunks[p->num_chunks];
|
149 |
|
150 |
order_chunks(p->chunks, ordered_chunks, p->num_chunks); |
151 |
for (ii = win_left(p, t); ii < win_right(p, t); ii++) {
|
152 |
i = ordered_chunks[ii]; |
153 |
if ((i >= 0) && p->chunks[i] && is_useful(i, p)) { |
154 |
return i;
|
155 |
} |
156 |
} |
157 |
|
158 |
/* No useful chunk... */
|
159 |
return -1; |
160 |
} |
161 |
|
162 |
SCHED int dl_sched(struct peer *p, int t, struct peer *dummy) |
163 |
{ |
164 |
int i;
|
165 |
int max = INT_MAX, winner = -1; |
166 |
|
167 |
for (i = win_left(p, t); i < win_right(p, t); i++) {
|
168 |
if (p->chunks[win_idx(p, i)] &&
|
169 |
in_buffer(p, i, t) && |
170 |
is_useful(i, p) && (p->chunks[win_idx(p, i)]->dl < max)) { |
171 |
max = p->chunks[win_idx(p, i)]->dl; |
172 |
winner = i; |
173 |
} |
174 |
} |
175 |
|
176 |
return winner;
|
177 |
} |
178 |
|
179 |
//latest useful chunk
|
180 |
SCHED int latest_useful_chunk(struct peer *p, int t, struct peer *target) |
181 |
{ |
182 |
int c, j;
|
183 |
for (c = win_right(p, t) - 1; c >= win_left(p, t); c--) { //c:chunk to send |
184 |
if (p->chunks[win_idx(p, c)] && in_buffer(p, c, t)) {
|
185 |
for (j = 0; j < p->neigh_size; j++) { //j:destination node; TODO: neighbour set |
186 |
if (needs(c, p->neighbour[j])) {
|
187 |
return c;
|
188 |
} |
189 |
} |
190 |
} |
191 |
} |
192 |
//we don't have a useful chunk
|
193 |
return -1; |
194 |
} |
195 |
|
196 |
//peer already selected, latest useful chunk
|
197 |
SCHED int dest_latest_useful_chunk(struct peer *p, int t, struct peer *target) |
198 |
{ |
199 |
int c;
|
200 |
for (c = win_right(p, t) - 1; c >= win_left(p, t); c--) { //c:chunk to send |
201 |
if (p->chunks[win_idx(p, c)] && in_buffer(p, c, t)) {
|
202 |
if (needs(c, target)) {
|
203 |
return c;
|
204 |
} |
205 |
} |
206 |
} |
207 |
//we don't have a useful chunk
|
208 |
return -1; |
209 |
} |
210 |
|
211 |
|
212 |
//latest blind chunk
|
213 |
SCHED int latest_blind_chunk(struct peer *p, int t, struct peer *target) |
214 |
{ |
215 |
int c;
|
216 |
for (c = win_right(p, t) - 1; c >= win_left(p, t); c--) { //c:chunk to send |
217 |
if (p->chunks[win_idx(p, c)] && in_buffer(p, c, t)) {
|
218 |
return c;
|
219 |
} |
220 |
} |
221 |
//we don't have a chunk
|
222 |
return -1; |
223 |
} |
224 |
|
225 |
//earliest useful chunk
|
226 |
SCHED int earliest_useful_chunk(struct peer *p, int t) |
227 |
{ |
228 |
int c, j;
|
229 |
for (c = win_left(p, t); c < win_right(p, t); c++) { //c:chunk to send |
230 |
if (p->chunks[win_idx(p, c)] && in_buffer(p, c, t)) {
|
231 |
for (j = 0; j < p->neigh_size; j++) { //j:destination node; TODO: neighbour set |
232 |
if (needs(c, p->neighbour[j])) {
|
233 |
return c;
|
234 |
} |
235 |
} |
236 |
} |
237 |
} |
238 |
//we don't have a useful chunk
|
239 |
return -1; |
240 |
} |
241 |
|
242 |
//peer already selected, earliest useful chunk
|
243 |
SCHED int dest_earliest_useful_chunk(struct peer *p, int t, struct peer *target) |
244 |
{ |
245 |
int c;
|
246 |
for (c = win_left(p, t); c < win_right(p, t); c++) { //c:chunk to send |
247 |
if (p->chunks[win_idx(p, c)] && in_buffer(p, c, t)) {
|
248 |
if (needs(c, target)) {
|
249 |
return c;
|
250 |
} |
251 |
} |
252 |
} |
253 |
//we don't have a useful chunk
|
254 |
return -1; |
255 |
} |
256 |
|
257 |
//peer already selected, random useful chunk
|
258 |
SCHED int random_useful_chunk(struct peer *p, int t, struct peer *target) |
259 |
{ |
260 |
int c;
|
261 |
int useful[p->num_chunks];
|
262 |
int usefuls = 0; |
263 |
|
264 |
for (c = win_left(p, t); c < win_right(p, t); c++) { //c:chunk to send |
265 |
if (p->chunks[win_idx(p, c)] && in_buffer(p, c, t)) {
|
266 |
if (is_useful(c, p)) {
|
267 |
useful[usefuls++] = c; |
268 |
} |
269 |
} |
270 |
} |
271 |
if (!usefuls) {
|
272 |
return -1; |
273 |
} else {
|
274 |
return useful[(int) (usefuls * (rand() / (RAND_MAX + 1.0)))]; |
275 |
} |
276 |
} |
277 |
|
278 |
SCHED int dest_random_useful_chunk(struct peer *p, int t, struct peer *target) |
279 |
{ |
280 |
int c;
|
281 |
int useful[p->num_chunks];
|
282 |
int usefuls = 0; |
283 |
|
284 |
for (c = win_left(p, t); c < win_right(p, t); c++) { //c:chunk to send |
285 |
if (p->chunks[win_idx(p, c)] && in_buffer(p, c, t)) {
|
286 |
if (needs(c, target)) {
|
287 |
useful[usefuls++] = c; |
288 |
} |
289 |
} |
290 |
} |
291 |
if (!usefuls) {
|
292 |
return -1; |
293 |
} else {
|
294 |
return useful[(int) (usefuls * (rand() / (RAND_MAX + 1.0)))]; |
295 |
} |
296 |
} |
297 |
|
298 |
//only chunk to send
|
299 |
SCHED int only_intime_chunk(struct peer *p, int t) |
300 |
{ |
301 |
int c, c2 = -1; |
302 |
for (c = min(t, p->num_chunks - 1); c >= max(t-PO_DELAY,0); c--) { //c:chunk to send |
303 |
//printf("\t time %d: peer %d checking chunk %d\n", t, p, c);
|
304 |
if (p->chunks[c]) {
|
305 |
return c;
|
306 |
//if (c2 >= 0)
|
307 |
// printf("Warning: time %d: peer %d has more chunks to send: %d and %d\n", t, p, c2, c);
|
308 |
//else
|
309 |
// c2 = c;
|
310 |
} |
311 |
} |
312 |
return c2;
|
313 |
} |
314 |
|
315 |
|
316 |
///==========================================================
|
317 |
/// peer selection algorithms
|
318 |
///==========================================================
|
319 |
|
320 |
//random peer
|
321 |
SCHED struct peer *random_peer(struct peer *p, int t) |
322 |
{ |
323 |
return p->neighbour[(int)(p->neigh_size * (rand() / (RAND_MAX + 1.0)))]; |
324 |
} |
325 |
|
326 |
//most deprived peer
|
327 |
SCHED struct peer *most_deprived_peer(struct peer *p, int t) |
328 |
{ |
329 |
int n, k, i;
|
330 |
n = p->num_chunks * p->neigh_size + 1; k = -1; |
331 |
|
332 |
for (i = 0; i < p->neigh_size; i++) { |
333 |
if (num_chunks(p->neighbour[i], t) < n) {
|
334 |
n = num_chunks(p->neighbour[i], t); |
335 |
k = i; |
336 |
} |
337 |
} |
338 |
|
339 |
return p->neighbour[k];
|
340 |
} |
341 |
|
342 |
//most deprived peer
|
343 |
SCHED struct peer *most_deprived_peer_random(struct peer *p, int t) |
344 |
{ |
345 |
int n, i, j, r;
|
346 |
n = p->num_chunks * p->neigh_size + 1; j = 0; |
347 |
|
348 |
for (i = 0; i < p->neigh_size; i++) { |
349 |
if (num_chunks(p->neighbour[i], t) == n) j++; //j: number of peers on being most deprived |
350 |
if (num_chunks(p->neighbour[i], t) < n) {
|
351 |
n = num_chunks(p->neighbour[i], t); |
352 |
j = 1;
|
353 |
} |
354 |
} |
355 |
|
356 |
r = (int) (j * (rand() / (RAND_MAX + 1.0))); //r: random choice |
357 |
|
358 |
for (i = 0, j = 0; i < p->neigh_size; i++) { |
359 |
if (num_chunks(p->neighbour[i], t) == n && j++ == r ) {
|
360 |
return p->neighbour[i];
|
361 |
} |
362 |
} |
363 |
exit(-1);
|
364 |
} |
365 |
|
366 |
//chunk already selected, peer that needs it
|
367 |
SCHED struct peer *ch_useful_peer(struct peer *p, int t, int c) |
368 |
{ |
369 |
int i;
|
370 |
|
371 |
for (i = 0; i < p->neigh_size; i++) { |
372 |
if (needs(c, p->neighbour[i])) {
|
373 |
return p->neighbour[i];
|
374 |
} |
375 |
} |
376 |
//fprintf(stderr, "Warning: chunk %d was selected but no neighbours of %d need it in time %d!\n", c, p, t);
|
377 |
//exit(-1);
|
378 |
return NULL; |
379 |
} |
380 |
|
381 |
//chunk already selected, weighted random choice between peers that need it
|
382 |
SCHED struct peer *ch_useful_peer_weighted_random(struct peer *p, int t, int c) |
383 |
{ |
384 |
int i;
|
385 |
double tot_prob, cum_prob;
|
386 |
double rand_value;
|
387 |
struct peer * neigh = NULL; |
388 |
|
389 |
for (tot_prob = 0, i = 0; i < p->neigh_size; i++) { |
390 |
if (needs(c, p->neighbour[i])) {
|
391 |
// fprintf(stderr, "[DEBUG]: %d,%d -> %f\n", c, p->id, (p->neighbour_prob)[i]);
|
392 |
tot_prob += (p->neighbour_prob)[i]; |
393 |
} |
394 |
} |
395 |
|
396 |
rand_value = ((rand() / (RAND_MAX + 1.0)) * tot_prob); |
397 |
// fprintf(stderr, "[DEBUG]: rand is: %f\n", rand_value);
|
398 |
|
399 |
i = 0;
|
400 |
cum_prob = 0;
|
401 |
while(tot_prob && i < p->neigh_size && neigh == NULL) |
402 |
{ |
403 |
if (needs(c, p->neighbour[i]))
|
404 |
cum_prob += (p->neighbour_prob)[i]; |
405 |
if (cum_prob >= rand_value)
|
406 |
neigh = (p->neighbour)[i]; |
407 |
i++; |
408 |
} |
409 |
|
410 |
if (!tot_prob)
|
411 |
fprintf(stderr, "[WARNING]: chunk %d was selected but no neighbours of %d need it in time %d!\n", c, p->id, t);
|
412 |
else if (!neigh) |
413 |
fprintf(stderr, "[WARNING]: chunk %d was selected but no neighbours of %d can been selected!!\n", c, p->id);
|
414 |
|
415 |
return neigh;
|
416 |
} |
417 |
|
418 |
//chunk already selected, random choice between peers that need it
|
419 |
SCHED struct peer *ch_useful_peer_random(struct peer *p, int t, int c) |
420 |
{ |
421 |
int i, j, r;
|
422 |
|
423 |
for (i = 0, j = 0; i < p->neigh_size; i++) { |
424 |
if (needs(c, p->neighbour[i])) {
|
425 |
j++; |
426 |
} |
427 |
} |
428 |
|
429 |
if (!j) {
|
430 |
//fprintf(stderr, "Warning: chunk %d was selected but no neighbours of %d need it in time %d!\n", c, p, t);
|
431 |
//exit(-1);
|
432 |
return NULL; |
433 |
} |
434 |
|
435 |
r = (int) (j * (rand() / (RAND_MAX + 1.0))); //r: random choice |
436 |
|
437 |
for (i = 0, j = 0; i < p->neigh_size; i++) { |
438 |
if (needs(c, p->neighbour[i]) && j++ == r ) {
|
439 |
return p->neighbour[i];
|
440 |
} |
441 |
} |
442 |
|
443 |
return NULL; |
444 |
} |
445 |
|
446 |
//chunk already selected, most deprived peer that needs it
|
447 |
SCHED struct peer *ch_most_deprived_peer(struct peer *p, int t, int c) |
448 |
{ |
449 |
int n, k, i;
|
450 |
n = p->num_chunks * p->neigh_size + 1; k = -1; |
451 |
|
452 |
for (i = 0; i < p->neigh_size; i++) { |
453 |
if (needs(c, p->neighbour[i]) && num_chunks(p->neighbour[i], t) < n) {
|
454 |
n = num_chunks(p->neighbour[i], t); |
455 |
k = i; |
456 |
} |
457 |
} |
458 |
if ( k==-1 ){ |
459 |
//fprintf(stderr, "Warning: chunk %d was selected but no neighbours of %d need it in time %d!\n", c, p, t);
|
460 |
//exit(-1);
|
461 |
} |
462 |
return p->neighbour[k];
|
463 |
} |
464 |
|
465 |
//chunk already selected, random choice between most deprived peers that need it
|
466 |
SCHED struct peer *ch_most_deprived_peer_random(struct peer *p, int t, int c) |
467 |
{ |
468 |
int n, i, j, r;
|
469 |
n = p->num_chunks * p->neigh_size + 1;
|
470 |
|
471 |
for (i = 0, j = 0; i < p->neigh_size; i++) { |
472 |
if (needs(c, p->neighbour[i]) && num_chunks(p->neighbour[i], t) == n) j++;
|
473 |
if (needs(c, p->neighbour[i]) && num_chunks(p->neighbour[i], t) < n) {
|
474 |
n = num_chunks(p->neighbour[i], t); |
475 |
j = 1;
|
476 |
} |
477 |
} |
478 |
|
479 |
if ( j==0 ){ |
480 |
//fprintf(stderr, "Warning: chunk %d was selected but no neighbours of %d need it in time %d!\n", c, p, t);
|
481 |
//exit(-1);
|
482 |
return NULL; |
483 |
} |
484 |
|
485 |
r = (int) (j * (rand() / (RAND_MAX + 1.0))); //r: random choice |
486 |
|
487 |
for (i = 0, j = 0; i < p->neigh_size; i++) { |
488 |
if (needs(c, p->neighbour[i]) && num_chunks(p->neighbour[i], t) == n && j++ == r ) {
|
489 |
return p->neighbour[i];
|
490 |
} |
491 |
} |
492 |
|
493 |
return NULL; |
494 |
} |
495 |
|
496 |
//node that has nothing to do in the next turn
|
497 |
SCHED struct peer *free_peer(struct peer *p, int t) |
498 |
{ |
499 |
int n, j, busy;
|
500 |
|
501 |
for (n = 0; n < p->neigh_size; n++) { |
502 |
busy = 0;
|
503 |
for (j = min(t, p->num_chunks - 1); j >= max(t-PO_DELAY+2,0); j--) { |
504 |
//fprintf(trace,"\ttime %d: peer %d needs chunk %d? %d\n", t, n, j, needs(n,j));
|
505 |
if (!needs(j,p->neighbour[n])) {
|
506 |
//fprintf(trace,"\ttime %d: peer %d busy because of chunk %d\n", t, n, j);
|
507 |
busy = 1;
|
508 |
break;
|
509 |
} |
510 |
} |
511 |
if (!busy) {
|
512 |
return p->neighbour[n];
|
513 |
} |
514 |
} |
515 |
return NULL; |
516 |
} |
517 |
|
518 |
//node that has nothing to do in the next turn
|
519 |
SCHED struct peer *ch_free_peer_or_deadline(struct peer *p, int t, int c) |
520 |
{ |
521 |
int n, n0, j, n_busy;
|
522 |
|
523 |
//see if there is a node who will have nothing to send
|
524 |
for (n0 = 0; n0 < p->neigh_size; n0++) { |
525 |
n = (p->id + n0) % p->neigh_size; |
526 |
n=n0; |
527 |
n_busy = 0;
|
528 |
for (j = min(t, p->num_chunks - 1); j >= max(t-PO_DELAY+2,0); j--) { |
529 |
//fprintf(trace,"\t\ttime %d: peer %d needs chunk %d? %d\n", t, n, j, needs(j,n));
|
530 |
if (!needs(j,p->neighbour[n])) {
|
531 |
//fprintf(trace,"\t\ttime %d: peer %d busy because of chunk %d\n", t, n, j);
|
532 |
n_busy = 1;
|
533 |
break; // cycle for chunks |
534 |
} |
535 |
} |
536 |
if (!n_busy && needs (c,p->neighbour[n])) {
|
537 |
return p->neighbour[n];
|
538 |
} |
539 |
} |
540 |
|
541 |
//see if there is a node who has only the oldest chunk to send
|
542 |
for (n0 = 0; n0 < p->neigh_size; n0++) { |
543 |
n = (p->id + n0) % p->neigh_size; |
544 |
n=n0; |
545 |
n_busy = 0;
|
546 |
for (j = min(t, p->num_chunks - 1); j > max(t-PO_DELAY+2,0); j--) { |
547 |
//fprintf(trace,"\t\ttime %d: peer %d needs chunk %d? %d\n", t, n, j, needs(j,n));
|
548 |
if (!needs(j,p->neighbour[n])) {
|
549 |
//fprintf(trace,"\t\ttime %d: peer %d busy because of chunk %d\n", t, n, j);
|
550 |
n_busy = 1;
|
551 |
break; // cycle for chunks |
552 |
} |
553 |
} |
554 |
if (!n_busy && needs (c,p->neighbour[n])) {
|
555 |
return p->neighbour[n];
|
556 |
} |
557 |
} |
558 |
|
559 |
for (n0 = 0; n0 < p->neigh_size; n0++) { |
560 |
n = (p->id + n0) % p->neigh_size; |
561 |
if (needs(c,p->neighbour[n])) {
|
562 |
return p->neighbour[n];
|
563 |
} |
564 |
} |
565 |
|
566 |
return NULL; |
567 |
} |
568 |
|
569 |
|
570 |
//node that has nothing to do in the next turn
|
571 |
SCHED struct peer *ch_free_peer_or_deadline2(struct peer *p, int t, int c) |
572 |
{ |
573 |
int n, j, n_busy;
|
574 |
|
575 |
//otherwise, search for someone who needs it and has nothing to do in the next turn
|
576 |
for (n = 0; n < p->neigh_size; n++) { |
577 |
n_busy = 0;
|
578 |
for (j = min(t, p->num_chunks - 1); j >= max(t-PO_DELAY+2,0); j--) { |
579 |
if (!needs(j,p->neighbour[n])) {
|
580 |
n_busy = 1;
|
581 |
break; // cycle for chunks |
582 |
} |
583 |
} |
584 |
if (!n_busy && needs (c,p->neighbour[n])) {
|
585 |
if (trace) fprintf(trace,"\tPeer %d: (chunk %d,%d) ---> %d, reason: nothing to do in t+1\n", p->id, c, c-t, n); |
586 |
return p->neighbour[n];
|
587 |
} |
588 |
} |
589 |
|
590 |
//otherwise, search for someone who needs it and has nothing to do in t+2
|
591 |
for (n = 0; n < p->neigh_size; n++) { |
592 |
n_busy = 0;
|
593 |
for (j = min(t, p->num_chunks - 1); j >= max(t-PO_DELAY+3,0); j--) { |
594 |
if (!needs(j,p->neighbour[n])) {
|
595 |
n_busy = 1;
|
596 |
break; // cycle for chunks |
597 |
} |
598 |
} |
599 |
if (!n_busy && needs (c,p->neighbour[n])) {
|
600 |
if (trace) fprintf(trace,"\tPeer %d: (chunk %d,%d) ---> %d, reason: nothing to do in t+2 \n", p->id, c, c-t, n); |
601 |
return p->neighbour[n];
|
602 |
} |
603 |
} |
604 |
|
605 |
// send to anyone who needs it
|
606 |
for (n = 0; n < p->neigh_size; n++) { |
607 |
if (needs(c,p->neighbour[n])) {
|
608 |
if (trace) fprintf(trace,"\ttime %d: peer %d -(chunk %d,%d)-> %d, reason: remaining \n", t, p->id, c, c-t, n); |
609 |
return p->neighbour[n];
|
610 |
} |
611 |
} |
612 |
|
613 |
return NULL; |
614 |
} |
615 |
|
616 |
//node that has nothing to do in the next turn
|
617 |
SCHED struct peer *ch_almost_free_peer(struct peer *p, int t, int c) |
618 |
{ |
619 |
int n;
|
620 |
|
621 |
//send to the one who has nothing to send in the next turn (t+1)
|
622 |
for (n = 0; n < p->neigh_size; n++) { |
623 |
if (needs (c,p->neighbour[n]) && latest_not_needed(p->neighbour[n], t) < max(t-PO_DELAY+2,0)) { |
624 |
if (trace) fprintf(trace,"\tPeer %d: (chunk %d,%d) ---> %d, reason: node has nothing to send \n", p->id, c, c-t, n); |
625 |
return p->neighbour[n];
|
626 |
} |
627 |
} |
628 |
|
629 |
//has nothing to send in the turn after the next one (t+2)
|
630 |
for (n = 0; n < p->neigh_size; n++) { |
631 |
if (needs (c,p->neighbour[n]) && latest_not_needed(p->neighbour[n],t) < max(t-PO_DELAY+3,0)) { |
632 |
if (trace) fprintf(trace,"\tPeer %d: (chunk %d,%d) ---> %d, reason: node has nothing to send in t+2 \n", p->id, c, c-t, n); |
633 |
return p->neighbour[n];
|
634 |
} |
635 |
} |
636 |
|
637 |
// send to anyone who needs it
|
638 |
for (n = 0; n < p->neigh_size; n++) { |
639 |
if (needs(c,p->neighbour[n])) {
|
640 |
if (trace) fprintf(trace,"\tPeer %d: (chunk %d,%d) ---> %d, reason: send anyway \n", p->id, c, c-t, n); |
641 |
return p->neighbour[n];
|
642 |
} |
643 |
} |
644 |
|
645 |
return NULL; |
646 |
} |
647 |
|
648 |
SCHED struct peer *least_utility(struct peer *p, int t, int c) |
649 |
{ |
650 |
int n = INT_MAX, winner = -1; |
651 |
int i;
|
652 |
|
653 |
for (i = 0; i < p->neigh_size; i++) { |
654 |
if (needs(c, p->neighbour[i])) {
|
655 |
int u = utility(p->neighbour[i], t);
|
656 |
if (u < n) {
|
657 |
n = u; |
658 |
winner = i; |
659 |
} |
660 |
} |
661 |
} |
662 |
|
663 |
if (winner >= 0) { |
664 |
return p->neighbour[winner];
|
665 |
} |
666 |
|
667 |
return NULL; |
668 |
} |
669 |
|
670 |
//nodes in order of when they will be free
|
671 |
SCHED struct peer *ch_earliest_free_peer(struct peer *p, int t, int c) |
672 |
{ |
673 |
int n, winner;
|
674 |
int min_latest_not_needed = p->num_chunks;
|
675 |
int l; //cache latest_not_needed(n,t) |
676 |
|
677 |
winner = -1; //the winner node |
678 |
for (n = 0; n < p->neigh_size; n++) { |
679 |
if (needs (c,p->neighbour[n])) {
|
680 |
l = latest_not_needed(p->neighbour[n],t); |
681 |
if (l < min_latest_not_needed) {
|
682 |
//if (trace) fprintf(trace,"\t\tPeer %d: (chunk %d,%d) latest_not_needed=%d \n", n, c, c-t, l);
|
683 |
min_latest_not_needed = l; |
684 |
winner = n; |
685 |
} |
686 |
} |
687 |
} |
688 |
if (winner >= 0) { |
689 |
if (trace) fprintf(trace,"\tPeer %d, t: %d: (chunk %d,%d) ---> %d\n", p->id, t, c, c-t, p->neighbour[winner]->id); |
690 |
return p->neighbour[winner];
|
691 |
} |
692 |
|
693 |
return NULL; |
694 |
} |
695 |
|
696 |
|
697 |
|
698 |
///==========================================================
|
699 |
/// peer & chunk selection algorithms
|
700 |
///==========================================================
|
701 |
|
702 |
//node: destination peer & chunk selection algorithm at peer p (push)
|
703 |
void peer_send_c_p(struct peer *p, int t, int *chunk, struct peer **target) |
704 |
{ |
705 |
*chunk = chunk_sched(p, t, NULL);
|
706 |
if (*chunk < 0) { |
707 |
if (trace) fprintf(trace, "\tPeer %d: Idle (no chunk to send)\n", p->id); |
708 |
*target = NULL;
|
709 |
|
710 |
return;
|
711 |
} |
712 |
|
713 |
*target = peer_sched(p, t, *chunk); |
714 |
if (*target == NULL) { |
715 |
if (trace) fprintf(trace, "\tPeer %d: Idle (no peer that needs chunk %d)\n", p->id, *chunk); |
716 |
return;
|
717 |
} |
718 |
|
719 |
if (trace) fprintf(trace, "\tPeer %d: %d ---> %d\n", p->id, *chunk, (*target)->id); |
720 |
} |
721 |
|
722 |
//node: destination peer & chunk selection algorithm at peer p (push)
|
723 |
void peer_send_p_c(struct peer *p, int t, int *chunk, struct peer **target) |
724 |
{ |
725 |
*target = peer_sched(p, t, t); |
726 |
if (*target < 0) { |
727 |
if (trace) fprintf(trace, "\tPeer %d: Idle (no peer to send to)\n", p->id); |
728 |
return;
|
729 |
} |
730 |
|
731 |
*chunk = chunk_sched(p, t, *target); |
732 |
if (*chunk < 0) { |
733 |
if (trace) fprintf(trace, "\tPeer %d: Idle (no chunk that %d needs)\n", p->id, (*target)->id); |
734 |
*target = NULL;
|
735 |
return;
|
736 |
} |
737 |
|
738 |
if (trace) fprintf(trace, "\tPeer %d: %d ---> %d\n", p->id, *chunk, (*target)->id); |
739 |
} |
740 |
|
741 |
void peer_send_chunk(struct peer *p, int t, int *chunk, struct peer *target) |
742 |
{ |
743 |
*chunk = chunk_sched(p, t, target); |
744 |
if (*chunk < 0) { |
745 |
if (trace) fprintf(trace, "\tPeer %d: Idle (no chunk that %d needs)\n", p->id, (target)->id); |
746 |
return;
|
747 |
} |
748 |
|
749 |
if (trace) fprintf(trace, "\tPeer %d: %d ---> %d\n", p->id, *chunk, (target)->id); |
750 |
} |
751 |
|
752 |
/* Should be probably merged with peer_send_c_p */
|
753 |
void peer_send_utility(struct peer *p, int t, int *chunk, struct peer **target) |
754 |
{ |
755 |
int i, ii;
|
756 |
int ordered_chunks[p->num_chunks];
|
757 |
|
758 |
*target = NULL;
|
759 |
order_chunks(p->chunks, ordered_chunks, p->num_chunks); |
760 |
for (ii = 0; ii < p->num_chunks; ii++) { |
761 |
i = ordered_chunks[ii]; |
762 |
if ((i >= 0) && p->chunks[i]) { |
763 |
*target = least_utility(p, t, i); |
764 |
if (*target != NULL) { |
765 |
if (trace) fprintf(trace, "\tPeer %d: %d ---> %d\n", p->id, i, (*target)->id); |
766 |
*chunk = i; |
767 |
break;
|
768 |
} else {
|
769 |
} |
770 |
} |
771 |
} |
772 |
|
773 |
if (*target == NULL) { |
774 |
if (trace) fprintf(trace, "\tPeer %d: Idle\n", p->id); |
775 |
} |
776 |
} |
777 |
|
778 |
|
779 |
///==========================================================
|
780 |
/// source: chunk & peer selection algorithms
|
781 |
///==========================================================
|
782 |
//source: destination peer & chunk selection algorithm
|
783 |
//latest chunk, generic (with 3 parameter dest case "ch_")
|
784 |
void source_send(int t, struct peer **peer) |
785 |
{ |
786 |
*peer = NULL;
|
787 |
if (t >= source.num_chunks) {
|
788 |
return;
|
789 |
} |
790 |
|
791 |
*peer = peer_sched(&source, t, t); //use N as source's peer ID. hope it works
|
792 |
|
793 |
if (trace) fprintf(trace, "\tSource: %d ---> %d\n", t, (*peer)->id); |
794 |
} |
795 |
|
796 |
void source_set(struct peer **neigh, int size, double * neigh_prob, int num_chunks) |
797 |
{ |
798 |
source.neighbour = neigh; |
799 |
source.neigh_size = size; |
800 |
source.id = -1;
|
801 |
source.num_chunks = num_chunks; |
802 |
source.neighbour_prob = neigh_prob; |
803 |
} |